head	1.1;
branch	1.1.1;
access;
symbols
	netbsd-11-0-RC4:1.1.1.2
	netbsd-11-0-RC3:1.1.1.2
	netbsd-11-0-RC2:1.1.1.2
	netbsd-11-0-RC1:1.1.1.2
	perseant-exfatfs-base-20250801:1.1.1.2
	netbsd-11:1.1.1.2.0.8
	netbsd-11-base:1.1.1.2
	netbsd-10-1-RELEASE:1.1.1.2
	perseant-exfatfs-base-20240630:1.1.1.2
	perseant-exfatfs:1.1.1.2.0.6
	perseant-exfatfs-base:1.1.1.2
	netbsd-10-0-RELEASE:1.1.1.2
	netbsd-10-0-RC6:1.1.1.2
	netbsd-10-0-RC5:1.1.1.2
	netbsd-10-0-RC4:1.1.1.2
	netbsd-10-0-RC3:1.1.1.2
	netbsd-10-0-RC2:1.1.1.2
	netbsd-10-0-RC1:1.1.1.2
	netbsd-10:1.1.1.2.0.4
	netbsd-10-base:1.1.1.2
	cjep_sun2x-base1:1.1.1.2
	cjep_sun2x:1.1.1.2.0.2
	cjep_sun2x-base:1.1.1.2
	cjep_staticlib_x-base1:1.1.1.2
	LLVM-249b40b558955afe5ac2b549edcf2d7f859c8cc9:1.1.1.2
	cjep_staticlib_x:1.1.1.1.0.4
	cjep_staticlib_x-base:1.1.1.1
	phil-wifi-20200421:1.1.1.1
	phil-wifi-20200411:1.1.1.1
	is-mlppp:1.1.1.1.0.2
	is-mlppp-base:1.1.1.1
	phil-wifi-20200406:1.1.1.1
	phil-wifi-20191119:1.1.1.1
	LLVM-01f3a59fb3e2542fce74c768718f594d0debd0da:1.1.1.1
	LLVM:1.1.1;
locks; strict;
comment	@// @;


1.1
date	2019.11.08.14.29.42;	author joerg;	state Exp;
branches
	1.1.1.1;
next	;
commitid	lIv69tfiG0KHw3KB;

1.1.1.1
date	2019.11.08.14.29.42;	author joerg;	state Exp;
branches
	1.1.1.1.4.1;
next	1.1.1.2;
commitid	lIv69tfiG0KHw3KB;

1.1.1.2
date	2021.05.30.01.25.57;	author joerg;	state Exp;
branches;
next	;
commitid	uhgdinROdC6tU6VC;

1.1.1.1.4.1
date	2021.05.31.22.07.21;	author cjep;	state Exp;
branches;
next	;
commitid	eWz9SBW0XqKjJlVC;


desc
@@


1.1
log
@Initial revision
@
text
@//===- Tree.cpp -----------------------------------------------*- C++ -*-=====//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "clang/Tooling/Syntax/Tree.h"
#include "clang/Basic/TokenKinds.h"
#include "clang/Tooling/Syntax/Nodes.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Casting.h"

using namespace clang;

syntax::Arena::Arena(SourceManager &SourceMgr, const LangOptions &LangOpts,
                     TokenBuffer Tokens)
    : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(std::move(Tokens)) {}

const clang::syntax::TokenBuffer &syntax::Arena::tokenBuffer() const {
  return Tokens;
}

std::pair<FileID, llvm::ArrayRef<syntax::Token>>
syntax::Arena::lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Input) {
  auto FID = SourceMgr.createFileID(std::move(Input));
  auto It = ExtraTokens.try_emplace(FID, tokenize(FID, SourceMgr, LangOpts));
  assert(It.second && "duplicate FileID");
  return {FID, It.first->second};
}

syntax::Leaf::Leaf(const syntax::Token *Tok) : Node(NodeKind::Leaf), Tok(Tok) {
  assert(Tok != nullptr);
}

bool syntax::Leaf::classof(const Node *N) {
  return N->kind() == NodeKind::Leaf;
}

syntax::Node::Node(NodeKind Kind)
    : Parent(nullptr), NextSibling(nullptr), Kind(static_cast<unsigned>(Kind)),
      Role(static_cast<unsigned>(NodeRole::Detached)) {}

bool syntax::Tree::classof(const Node *N) { return N->kind() > NodeKind::Leaf; }

void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
  assert(Child->Parent == nullptr);
  assert(Child->NextSibling == nullptr);
  assert(Child->role() == NodeRole::Detached);
  assert(Role != NodeRole::Detached);

  Child->Parent = this;
  Child->NextSibling = this->FirstChild;
  Child->Role = static_cast<unsigned>(Role);
  this->FirstChild = Child;
}

namespace {
static void traverse(const syntax::Node *N,
                     llvm::function_ref<void(const syntax::Node *)> Visit) {
  if (auto *T = dyn_cast<syntax::Tree>(N)) {
    for (auto *C = T->firstChild(); C; C = C->nextSibling())
      traverse(C, Visit);
  }
  Visit(N);
}
static void dumpTokens(llvm::raw_ostream &OS, ArrayRef<syntax::Token> Tokens,
                       const SourceManager &SM) {
  assert(!Tokens.empty());
  bool First = true;
  for (const auto &T : Tokens) {
    if (!First)
      OS << " ";
    else
      First = false;
    // Handle 'eof' separately, calling text() on it produces an empty string.
    if (T.kind() == tok::eof) {
      OS << "<eof>";
      continue;
    }
    OS << T.text(SM);
  }
}

static void dumpTree(llvm::raw_ostream &OS, const syntax::Node *N,
                     const syntax::Arena &A, std::vector<bool> IndentMask) {
  if (N->role() != syntax::NodeRole::Unknown) {
    // FIXME: print the symbolic name of a role.
    if (N->role() == syntax::NodeRole::Detached)
      OS << "*: ";
    else
      OS << static_cast<int>(N->role()) << ": ";
  }
  if (auto *L = llvm::dyn_cast<syntax::Leaf>(N)) {
    dumpTokens(OS, *L->token(), A.sourceManager());
    OS << "\n";
    return;
  }

  auto *T = llvm::cast<syntax::Tree>(N);
  OS << T->kind() << "\n";

  for (auto It = T->firstChild(); It != nullptr; It = It->nextSibling()) {
    for (bool Filled : IndentMask) {
      if (Filled)
        OS << "| ";
      else
        OS << "  ";
    }
    if (!It->nextSibling()) {
      OS << "`-";
      IndentMask.push_back(false);
    } else {
      OS << "|-";
      IndentMask.push_back(true);
    }
    dumpTree(OS, It, A, IndentMask);
    IndentMask.pop_back();
  }
}
} // namespace

std::string syntax::Node::dump(const Arena &A) const {
  std::string Str;
  llvm::raw_string_ostream OS(Str);
  dumpTree(OS, this, A, /*IndentMask=*/{});
  return std::move(OS.str());
}

std::string syntax::Node::dumpTokens(const Arena &A) const {
  std::string Storage;
  llvm::raw_string_ostream OS(Storage);
  traverse(this, [&](const syntax::Node *N) {
    auto *L = llvm::dyn_cast<syntax::Leaf>(N);
    if (!L)
      return;
    ::dumpTokens(OS, *L->token(), A.sourceManager());
  });
  return OS.str();
}

syntax::Node *syntax::Tree::findChild(NodeRole R) {
  for (auto *C = FirstChild; C; C = C->nextSibling()) {
    if (C->role() == R)
      return C;
  }
  return nullptr;
}
@


1.1.1.1
log
@Import 01f3a59fb3e2542fce74c768718f594d0debd0da from the LLVM mono-repo:
clang (without test/, unittests/, www/)
llvm (without test/, unittests/)
@
text
@@


1.1.1.1.4.1
log
@sync with head
@
text
@a13 1
#include <cassert>
a16 17
namespace {
static void traverse(const syntax::Node *N,
                     llvm::function_ref<void(const syntax::Node *)> Visit) {
  if (auto *T = dyn_cast<syntax::Tree>(N)) {
    for (const syntax::Node &C : T->getChildren())
      traverse(&C, Visit);
  }
  Visit(N);
}
static void traverse(syntax::Node *N,
                     llvm::function_ref<void(syntax::Node *)> Visit) {
  traverse(static_cast<const syntax::Node *>(N), [&](const syntax::Node *N) {
    Visit(const_cast<syntax::Node *>(N));
  });
}
} // namespace

d18 2
a19 2
                     const TokenBuffer &Tokens)
    : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(Tokens) {}
d21 1
a21 1
const syntax::TokenBuffer &syntax::Arena::getTokenBuffer() const {
d25 1
a25 1
std::pair<FileID, ArrayRef<syntax::Token>>
d37 2
a38 5
syntax::Node::Node(NodeKind Kind)
    : Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
      Kind(static_cast<unsigned>(Kind)), Role(0), Original(false),
      CanModify(false) {
  this->setRole(NodeRole::Detached);
d41 3
a43 3
bool syntax::Node::isDetached() const {
  return getRole() == NodeRole::Detached;
}
d45 1
a45 3
void syntax::Node::setRole(NodeRole NR) {
  this->Role = static_cast<unsigned>(NR);
}
d47 1
a47 9
void syntax::Tree::appendChildLowLevel(Node *Child, NodeRole Role) {
  assert(Child->getRole() == NodeRole::Detached);
  assert(Role != NodeRole::Detached);

  Child->setRole(Role);
  appendChildLowLevel(Child);
}

void syntax::Tree::appendChildLowLevel(Node *Child) {
d50 1
a50 15
  assert(Child->PreviousSibling == nullptr);
  assert(Child->getRole() != NodeRole::Detached);

  Child->Parent = this;
  if (this->LastChild) {
    Child->PreviousSibling = this->LastChild;
    this->LastChild->NextSibling = Child;
  } else
    this->FirstChild = Child;

  this->LastChild = Child;
}

void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
  assert(Child->getRole() == NodeRole::Detached);
a52 10
  Child->setRole(Role);
  prependChildLowLevel(Child);
}

void syntax::Tree::prependChildLowLevel(Node *Child) {
  assert(Child->Parent == nullptr);
  assert(Child->NextSibling == nullptr);
  assert(Child->PreviousSibling == nullptr);
  assert(Child->getRole() != NodeRole::Detached);

d54 2
a55 6
  if (this->FirstChild) {
    Child->NextSibling = this->FirstChild;
    this->FirstChild->PreviousSibling = Child;
  } else
    this->LastChild = Child;

d59 6
a64 12
void syntax::Tree::replaceChildRangeLowLevel(Node *Begin, Node *End,
                                             Node *New) {
  assert((!Begin || Begin->Parent == this) &&
         "`Begin` is not a child of `this`.");
  assert((!End || End->Parent == this) && "`End` is not a child of `this`.");
  assert(canModify() && "Cannot modify `this`.");

#ifndef NDEBUG
  for (auto *N = New; N; N = N->NextSibling) {
    assert(N->Parent == nullptr);
    assert(N->getRole() != NodeRole::Detached && "Roles must be set");
    // FIXME: sanity-check the role.
d66 17
a82 36

  auto Reachable = [](Node *From, Node *N) {
    if (!N)
      return true;
    for (auto *It = From; It; It = It->NextSibling)
      if (It == N)
        return true;
    return false;
  };
  assert(Reachable(FirstChild, Begin) && "`Begin` is not reachable.");
  assert(Reachable(Begin, End) && "`End` is not after `Begin`.");
#endif

  if (!New && Begin == End)
    return;

  // Mark modification.
  for (auto *T = this; T && T->Original; T = T->Parent)
    T->Original = false;

  // Save the node before the range to be removed. Later we insert the `New`
  // range after this node.
  auto *BeforeBegin = Begin ? Begin->PreviousSibling : LastChild;

  // Detach old nodes.
  for (auto *N = Begin; N != End;) {
    auto *Next = N->NextSibling;

    N->setRole(NodeRole::Detached);
    N->Parent = nullptr;
    N->NextSibling = nullptr;
    N->PreviousSibling = nullptr;
    if (N->Original)
      traverse(N, [](Node *C) { C->Original = false; });

    N = Next;
d84 1
d86 8
a93 8
  // Attach new range.
  auto *&NewFirst = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
  auto *&NewLast = End ? End->PreviousSibling : LastChild;

  if (!New) {
    NewFirst = End;
    NewLast = BeforeBegin;
    return;
d95 2
a96 43

  New->PreviousSibling = BeforeBegin;
  NewFirst = New;

  Node *LastInNew;
  for (auto *N = New; N != nullptr; N = N->NextSibling) {
    LastInNew = N;
    N->Parent = this;
  }
  LastInNew->NextSibling = End;
  NewLast = LastInNew;
}

namespace {
static void dumpLeaf(raw_ostream &OS, const syntax::Leaf *L,
                     const SourceManager &SM) {
  assert(L);
  const auto *Token = L->getToken();
  assert(Token);
  // Handle 'eof' separately, calling text() on it produces an empty string.
  if (Token->kind() == tok::eof)
    OS << "<eof>";
  else
    OS << Token->text(SM);
}

static void dumpNode(raw_ostream &OS, const syntax::Node *N,
                     const SourceManager &SM, std::vector<bool> IndentMask) {
  auto DumpExtraInfo = [&OS](const syntax::Node *N) {
    if (N->getRole() != syntax::NodeRole::Unknown)
      OS << " " << N->getRole();
    if (!N->isOriginal())
      OS << " synthesized";
    if (!N->canModify())
      OS << " unmodifiable";
  };

  assert(N);
  if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
    OS << "'";
    dumpLeaf(OS, L, SM);
    OS << "'";
    DumpExtraInfo(N);
d101 2
a102 4
  const auto *T = cast<syntax::Tree>(N);
  OS << T->getKind();
  DumpExtraInfo(N);
  OS << "\n";
d104 1
a104 1
  for (const syntax::Node &It : T->getChildren()) {
d111 1
a111 1
    if (!It.getNextSibling()) {
d118 1
a118 1
    dumpNode(OS, &It, SM, IndentMask);
d124 1
a124 1
std::string syntax::Node::dump(const SourceManager &SM) const {
d127 1
a127 1
  dumpNode(OS, this, SM, /*IndentMask=*/{});
d131 1
a131 1
std::string syntax::Node::dumpTokens(const SourceManager &SM) const {
d135 4
a138 4
    if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
      dumpLeaf(OS, L, SM);
      OS << " ";
    }
d143 4
a146 49
void syntax::Node::assertInvariants() const {
#ifndef NDEBUG
  if (isDetached())
    assert(getParent() == nullptr);
  else
    assert(getParent() != nullptr);

  const auto *T = dyn_cast<Tree>(this);
  if (!T)
    return;
  for (const Node &C : T->getChildren()) {
    if (T->isOriginal())
      assert(C.isOriginal());
    assert(!C.isDetached());
    assert(C.getParent() == T);
    const auto *Next = C.getNextSibling();
    assert(!Next || &C == Next->getPreviousSibling());
    if (!C.getNextSibling())
      assert(&C == T->getLastChild() &&
             "Last child is reachable by advancing from the first child.");
  }

  const auto *L = dyn_cast<List>(T);
  if (!L)
    return;
  for (const Node &C : T->getChildren()) {
    assert(C.getRole() == NodeRole::ListElement ||
           C.getRole() == NodeRole::ListDelimiter);
    if (C.getRole() == NodeRole::ListDelimiter) {
      assert(isa<Leaf>(C));
      assert(cast<Leaf>(C).getToken()->kind() == L->getDelimiterTokenKind());
    }
  }

#endif
}

void syntax::Node::assertInvariantsRecursive() const {
#ifndef NDEBUG
  traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
#endif
}

const syntax::Leaf *syntax::Tree::findFirstLeaf() const {
  for (const Node &C : getChildren()) {
    if (const auto *L = dyn_cast<syntax::Leaf>(&C))
      return L;
    if (const auto *L = cast<syntax::Tree>(C).findFirstLeaf())
      return L;
a149 150

const syntax::Leaf *syntax::Tree::findLastLeaf() const {
  for (const auto *C = getLastChild(); C; C = C->getPreviousSibling()) {
    if (const auto *L = dyn_cast<syntax::Leaf>(C))
      return L;
    if (const auto *L = cast<syntax::Tree>(C)->findLastLeaf())
      return L;
  }
  return nullptr;
}

const syntax::Node *syntax::Tree::findChild(NodeRole R) const {
  for (const Node &C : getChildren()) {
    if (C.getRole() == R)
      return &C;
  }
  return nullptr;
}

std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
syntax::List::getElementsAsNodesAndDelimiters() {
  if (!getFirstChild())
    return {};

  std::vector<syntax::List::ElementAndDelimiter<Node>> Children;
  syntax::Node *ElementWithoutDelimiter = nullptr;
  for (Node &C : getChildren()) {
    switch (C.getRole()) {
    case syntax::NodeRole::ListElement: {
      if (ElementWithoutDelimiter) {
        Children.push_back({ElementWithoutDelimiter, nullptr});
      }
      ElementWithoutDelimiter = &C;
      break;
    }
    case syntax::NodeRole::ListDelimiter: {
      Children.push_back({ElementWithoutDelimiter, cast<syntax::Leaf>(&C)});
      ElementWithoutDelimiter = nullptr;
      break;
    }
    default:
      llvm_unreachable(
          "A list can have only elements and delimiters as children.");
    }
  }

  switch (getTerminationKind()) {
  case syntax::List::TerminationKind::Separated: {
    Children.push_back({ElementWithoutDelimiter, nullptr});
    break;
  }
  case syntax::List::TerminationKind::Terminated:
  case syntax::List::TerminationKind::MaybeTerminated: {
    if (ElementWithoutDelimiter) {
      Children.push_back({ElementWithoutDelimiter, nullptr});
    }
    break;
  }
  }

  return Children;
}

// Almost the same implementation of `getElementsAsNodesAndDelimiters` but
// ignoring delimiters
std::vector<syntax::Node *> syntax::List::getElementsAsNodes() {
  if (!getFirstChild())
    return {};

  std::vector<syntax::Node *> Children;
  syntax::Node *ElementWithoutDelimiter = nullptr;
  for (Node &C : getChildren()) {
    switch (C.getRole()) {
    case syntax::NodeRole::ListElement: {
      if (ElementWithoutDelimiter) {
        Children.push_back(ElementWithoutDelimiter);
      }
      ElementWithoutDelimiter = &C;
      break;
    }
    case syntax::NodeRole::ListDelimiter: {
      Children.push_back(ElementWithoutDelimiter);
      ElementWithoutDelimiter = nullptr;
      break;
    }
    default:
      llvm_unreachable("A list has only elements or delimiters.");
    }
  }

  switch (getTerminationKind()) {
  case syntax::List::TerminationKind::Separated: {
    Children.push_back(ElementWithoutDelimiter);
    break;
  }
  case syntax::List::TerminationKind::Terminated:
  case syntax::List::TerminationKind::MaybeTerminated: {
    if (ElementWithoutDelimiter) {
      Children.push_back(ElementWithoutDelimiter);
    }
    break;
  }
  }

  return Children;
}

clang::tok::TokenKind syntax::List::getDelimiterTokenKind() const {
  switch (this->getKind()) {
  case NodeKind::NestedNameSpecifier:
    return clang::tok::coloncolon;
  case NodeKind::CallArguments:
  case NodeKind::ParameterDeclarationList:
  case NodeKind::DeclaratorList:
    return clang::tok::comma;
  default:
    llvm_unreachable("This is not a subclass of List, thus "
                     "getDelimiterTokenKind() cannot be called");
  }
}

syntax::List::TerminationKind syntax::List::getTerminationKind() const {
  switch (this->getKind()) {
  case NodeKind::NestedNameSpecifier:
    return TerminationKind::Terminated;
  case NodeKind::CallArguments:
  case NodeKind::ParameterDeclarationList:
  case NodeKind::DeclaratorList:
    return TerminationKind::Separated;
  default:
    llvm_unreachable("This is not a subclass of List, thus "
                     "getTerminationKind() cannot be called");
  }
}

bool syntax::List::canBeEmpty() const {
  switch (this->getKind()) {
  case NodeKind::NestedNameSpecifier:
    return false;
  case NodeKind::CallArguments:
    return true;
  case NodeKind::ParameterDeclarationList:
    return true;
  case NodeKind::DeclaratorList:
    return true;
  default:
    llvm_unreachable("This is not a subclass of List, thus canBeEmpty() "
                     "cannot be called");
  }
}
@


1.1.1.2
log
@Import clang 249b40b558955afe5ac2b549edcf2d7f859c8cc9.
@
text
@a13 1
#include <cassert>
a16 17
namespace {
static void traverse(const syntax::Node *N,
                     llvm::function_ref<void(const syntax::Node *)> Visit) {
  if (auto *T = dyn_cast<syntax::Tree>(N)) {
    for (const syntax::Node &C : T->getChildren())
      traverse(&C, Visit);
  }
  Visit(N);
}
static void traverse(syntax::Node *N,
                     llvm::function_ref<void(syntax::Node *)> Visit) {
  traverse(static_cast<const syntax::Node *>(N), [&](const syntax::Node *N) {
    Visit(const_cast<syntax::Node *>(N));
  });
}
} // namespace

d18 2
a19 2
                     const TokenBuffer &Tokens)
    : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(Tokens) {}
d21 1
a21 1
const syntax::TokenBuffer &syntax::Arena::getTokenBuffer() const {
d25 1
a25 1
std::pair<FileID, ArrayRef<syntax::Token>>
d37 2
a38 5
syntax::Node::Node(NodeKind Kind)
    : Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
      Kind(static_cast<unsigned>(Kind)), Role(0), Original(false),
      CanModify(false) {
  this->setRole(NodeRole::Detached);
d41 3
a43 3
bool syntax::Node::isDetached() const {
  return getRole() == NodeRole::Detached;
}
d45 1
a45 3
void syntax::Node::setRole(NodeRole NR) {
  this->Role = static_cast<unsigned>(NR);
}
d47 1
a47 9
void syntax::Tree::appendChildLowLevel(Node *Child, NodeRole Role) {
  assert(Child->getRole() == NodeRole::Detached);
  assert(Role != NodeRole::Detached);

  Child->setRole(Role);
  appendChildLowLevel(Child);
}

void syntax::Tree::appendChildLowLevel(Node *Child) {
d50 1
a50 15
  assert(Child->PreviousSibling == nullptr);
  assert(Child->getRole() != NodeRole::Detached);

  Child->Parent = this;
  if (this->LastChild) {
    Child->PreviousSibling = this->LastChild;
    this->LastChild->NextSibling = Child;
  } else
    this->FirstChild = Child;

  this->LastChild = Child;
}

void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
  assert(Child->getRole() == NodeRole::Detached);
a52 10
  Child->setRole(Role);
  prependChildLowLevel(Child);
}

void syntax::Tree::prependChildLowLevel(Node *Child) {
  assert(Child->Parent == nullptr);
  assert(Child->NextSibling == nullptr);
  assert(Child->PreviousSibling == nullptr);
  assert(Child->getRole() != NodeRole::Detached);

d54 2
a55 6
  if (this->FirstChild) {
    Child->NextSibling = this->FirstChild;
    this->FirstChild->PreviousSibling = Child;
  } else
    this->LastChild = Child;

d59 6
a64 12
void syntax::Tree::replaceChildRangeLowLevel(Node *Begin, Node *End,
                                             Node *New) {
  assert((!Begin || Begin->Parent == this) &&
         "`Begin` is not a child of `this`.");
  assert((!End || End->Parent == this) && "`End` is not a child of `this`.");
  assert(canModify() && "Cannot modify `this`.");

#ifndef NDEBUG
  for (auto *N = New; N; N = N->NextSibling) {
    assert(N->Parent == nullptr);
    assert(N->getRole() != NodeRole::Detached && "Roles must be set");
    // FIXME: sanity-check the role.
d66 17
a82 36

  auto Reachable = [](Node *From, Node *N) {
    if (!N)
      return true;
    for (auto *It = From; It; It = It->NextSibling)
      if (It == N)
        return true;
    return false;
  };
  assert(Reachable(FirstChild, Begin) && "`Begin` is not reachable.");
  assert(Reachable(Begin, End) && "`End` is not after `Begin`.");
#endif

  if (!New && Begin == End)
    return;

  // Mark modification.
  for (auto *T = this; T && T->Original; T = T->Parent)
    T->Original = false;

  // Save the node before the range to be removed. Later we insert the `New`
  // range after this node.
  auto *BeforeBegin = Begin ? Begin->PreviousSibling : LastChild;

  // Detach old nodes.
  for (auto *N = Begin; N != End;) {
    auto *Next = N->NextSibling;

    N->setRole(NodeRole::Detached);
    N->Parent = nullptr;
    N->NextSibling = nullptr;
    N->PreviousSibling = nullptr;
    if (N->Original)
      traverse(N, [](Node *C) { C->Original = false; });

    N = Next;
d84 1
d86 8
a93 8
  // Attach new range.
  auto *&NewFirst = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
  auto *&NewLast = End ? End->PreviousSibling : LastChild;

  if (!New) {
    NewFirst = End;
    NewLast = BeforeBegin;
    return;
d95 2
a96 43

  New->PreviousSibling = BeforeBegin;
  NewFirst = New;

  Node *LastInNew;
  for (auto *N = New; N != nullptr; N = N->NextSibling) {
    LastInNew = N;
    N->Parent = this;
  }
  LastInNew->NextSibling = End;
  NewLast = LastInNew;
}

namespace {
static void dumpLeaf(raw_ostream &OS, const syntax::Leaf *L,
                     const SourceManager &SM) {
  assert(L);
  const auto *Token = L->getToken();
  assert(Token);
  // Handle 'eof' separately, calling text() on it produces an empty string.
  if (Token->kind() == tok::eof)
    OS << "<eof>";
  else
    OS << Token->text(SM);
}

static void dumpNode(raw_ostream &OS, const syntax::Node *N,
                     const SourceManager &SM, std::vector<bool> IndentMask) {
  auto DumpExtraInfo = [&OS](const syntax::Node *N) {
    if (N->getRole() != syntax::NodeRole::Unknown)
      OS << " " << N->getRole();
    if (!N->isOriginal())
      OS << " synthesized";
    if (!N->canModify())
      OS << " unmodifiable";
  };

  assert(N);
  if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
    OS << "'";
    dumpLeaf(OS, L, SM);
    OS << "'";
    DumpExtraInfo(N);
d101 2
a102 4
  const auto *T = cast<syntax::Tree>(N);
  OS << T->getKind();
  DumpExtraInfo(N);
  OS << "\n";
d104 1
a104 1
  for (const syntax::Node &It : T->getChildren()) {
d111 1
a111 1
    if (!It.getNextSibling()) {
d118 1
a118 1
    dumpNode(OS, &It, SM, IndentMask);
d124 1
a124 1
std::string syntax::Node::dump(const SourceManager &SM) const {
d127 1
a127 1
  dumpNode(OS, this, SM, /*IndentMask=*/{});
d131 1
a131 1
std::string syntax::Node::dumpTokens(const SourceManager &SM) const {
d135 4
a138 4
    if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
      dumpLeaf(OS, L, SM);
      OS << " ";
    }
d143 4
a146 49
void syntax::Node::assertInvariants() const {
#ifndef NDEBUG
  if (isDetached())
    assert(getParent() == nullptr);
  else
    assert(getParent() != nullptr);

  const auto *T = dyn_cast<Tree>(this);
  if (!T)
    return;
  for (const Node &C : T->getChildren()) {
    if (T->isOriginal())
      assert(C.isOriginal());
    assert(!C.isDetached());
    assert(C.getParent() == T);
    const auto *Next = C.getNextSibling();
    assert(!Next || &C == Next->getPreviousSibling());
    if (!C.getNextSibling())
      assert(&C == T->getLastChild() &&
             "Last child is reachable by advancing from the first child.");
  }

  const auto *L = dyn_cast<List>(T);
  if (!L)
    return;
  for (const Node &C : T->getChildren()) {
    assert(C.getRole() == NodeRole::ListElement ||
           C.getRole() == NodeRole::ListDelimiter);
    if (C.getRole() == NodeRole::ListDelimiter) {
      assert(isa<Leaf>(C));
      assert(cast<Leaf>(C).getToken()->kind() == L->getDelimiterTokenKind());
    }
  }

#endif
}

void syntax::Node::assertInvariantsRecursive() const {
#ifndef NDEBUG
  traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
#endif
}

const syntax::Leaf *syntax::Tree::findFirstLeaf() const {
  for (const Node &C : getChildren()) {
    if (const auto *L = dyn_cast<syntax::Leaf>(&C))
      return L;
    if (const auto *L = cast<syntax::Tree>(C).findFirstLeaf())
      return L;
a149 150

const syntax::Leaf *syntax::Tree::findLastLeaf() const {
  for (const auto *C = getLastChild(); C; C = C->getPreviousSibling()) {
    if (const auto *L = dyn_cast<syntax::Leaf>(C))
      return L;
    if (const auto *L = cast<syntax::Tree>(C)->findLastLeaf())
      return L;
  }
  return nullptr;
}

const syntax::Node *syntax::Tree::findChild(NodeRole R) const {
  for (const Node &C : getChildren()) {
    if (C.getRole() == R)
      return &C;
  }
  return nullptr;
}

std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
syntax::List::getElementsAsNodesAndDelimiters() {
  if (!getFirstChild())
    return {};

  std::vector<syntax::List::ElementAndDelimiter<Node>> Children;
  syntax::Node *ElementWithoutDelimiter = nullptr;
  for (Node &C : getChildren()) {
    switch (C.getRole()) {
    case syntax::NodeRole::ListElement: {
      if (ElementWithoutDelimiter) {
        Children.push_back({ElementWithoutDelimiter, nullptr});
      }
      ElementWithoutDelimiter = &C;
      break;
    }
    case syntax::NodeRole::ListDelimiter: {
      Children.push_back({ElementWithoutDelimiter, cast<syntax::Leaf>(&C)});
      ElementWithoutDelimiter = nullptr;
      break;
    }
    default:
      llvm_unreachable(
          "A list can have only elements and delimiters as children.");
    }
  }

  switch (getTerminationKind()) {
  case syntax::List::TerminationKind::Separated: {
    Children.push_back({ElementWithoutDelimiter, nullptr});
    break;
  }
  case syntax::List::TerminationKind::Terminated:
  case syntax::List::TerminationKind::MaybeTerminated: {
    if (ElementWithoutDelimiter) {
      Children.push_back({ElementWithoutDelimiter, nullptr});
    }
    break;
  }
  }

  return Children;
}

// Almost the same implementation of `getElementsAsNodesAndDelimiters` but
// ignoring delimiters
std::vector<syntax::Node *> syntax::List::getElementsAsNodes() {
  if (!getFirstChild())
    return {};

  std::vector<syntax::Node *> Children;
  syntax::Node *ElementWithoutDelimiter = nullptr;
  for (Node &C : getChildren()) {
    switch (C.getRole()) {
    case syntax::NodeRole::ListElement: {
      if (ElementWithoutDelimiter) {
        Children.push_back(ElementWithoutDelimiter);
      }
      ElementWithoutDelimiter = &C;
      break;
    }
    case syntax::NodeRole::ListDelimiter: {
      Children.push_back(ElementWithoutDelimiter);
      ElementWithoutDelimiter = nullptr;
      break;
    }
    default:
      llvm_unreachable("A list has only elements or delimiters.");
    }
  }

  switch (getTerminationKind()) {
  case syntax::List::TerminationKind::Separated: {
    Children.push_back(ElementWithoutDelimiter);
    break;
  }
  case syntax::List::TerminationKind::Terminated:
  case syntax::List::TerminationKind::MaybeTerminated: {
    if (ElementWithoutDelimiter) {
      Children.push_back(ElementWithoutDelimiter);
    }
    break;
  }
  }

  return Children;
}

clang::tok::TokenKind syntax::List::getDelimiterTokenKind() const {
  switch (this->getKind()) {
  case NodeKind::NestedNameSpecifier:
    return clang::tok::coloncolon;
  case NodeKind::CallArguments:
  case NodeKind::ParameterDeclarationList:
  case NodeKind::DeclaratorList:
    return clang::tok::comma;
  default:
    llvm_unreachable("This is not a subclass of List, thus "
                     "getDelimiterTokenKind() cannot be called");
  }
}

syntax::List::TerminationKind syntax::List::getTerminationKind() const {
  switch (this->getKind()) {
  case NodeKind::NestedNameSpecifier:
    return TerminationKind::Terminated;
  case NodeKind::CallArguments:
  case NodeKind::ParameterDeclarationList:
  case NodeKind::DeclaratorList:
    return TerminationKind::Separated;
  default:
    llvm_unreachable("This is not a subclass of List, thus "
                     "getTerminationKind() cannot be called");
  }
}

bool syntax::List::canBeEmpty() const {
  switch (this->getKind()) {
  case NodeKind::NestedNameSpecifier:
    return false;
  case NodeKind::CallArguments:
    return true;
  case NodeKind::ParameterDeclarationList:
    return true;
  case NodeKind::DeclaratorList:
    return true;
  default:
    llvm_unreachable("This is not a subclass of List, thus canBeEmpty() "
                     "cannot be called");
  }
}
@