clang  10.0.0svn
Tree.cpp
Go to the documentation of this file.
1 //===- Tree.cpp -----------------------------------------------*- C++ -*-=====//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/Support/Casting.h"
14 
15 using namespace clang;
16 
17 syntax::Arena::Arena(SourceManager &SourceMgr, const LangOptions &LangOpts,
18  TokenBuffer Tokens)
19  : SourceMgr(SourceMgr), LangOpts(LangOpts), Tokens(std::move(Tokens)) {}
20 
22  return Tokens;
23 }
24 
25 std::pair<FileID, llvm::ArrayRef<syntax::Token>>
26 syntax::Arena::lexBuffer(std::unique_ptr<llvm::MemoryBuffer> Input) {
27  auto FID = SourceMgr.createFileID(std::move(Input));
28  auto It = ExtraTokens.try_emplace(FID, tokenize(FID, SourceMgr, LangOpts));
29  assert(It.second && "duplicate FileID");
30  return {FID, It.first->second};
31 }
32 
34  assert(Tok != nullptr);
35 }
36 
37 bool syntax::Leaf::classof(const Node *N) {
38  return N->kind() == NodeKind::Leaf;
39 }
40 
42  : Parent(nullptr), NextSibling(nullptr), Kind(static_cast<unsigned>(Kind)),
43  Role(static_cast<unsigned>(NodeRole::Detached)) {}
44 
45 bool syntax::Tree::classof(const Node *N) { return N->kind() > NodeKind::Leaf; }
46 
47 void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
48  assert(Child->Parent == nullptr);
49  assert(Child->NextSibling == nullptr);
50  assert(Child->role() == NodeRole::Detached);
51  assert(Role != NodeRole::Detached);
52 
53  Child->Parent = this;
54  Child->NextSibling = this->FirstChild;
55  Child->Role = static_cast<unsigned>(Role);
56  this->FirstChild = Child;
57 }
58 
59 namespace {
60 static void traverse(const syntax::Node *N,
61  llvm::function_ref<void(const syntax::Node *)> Visit) {
62  if (auto *T = dyn_cast<syntax::Tree>(N)) {
63  for (auto *C = T->firstChild(); C; C = C->nextSibling())
64  traverse(C, Visit);
65  }
66  Visit(N);
67 }
68 static void dumpTokens(llvm::raw_ostream &OS, ArrayRef<syntax::Token> Tokens,
69  const SourceManager &SM) {
70  assert(!Tokens.empty());
71  bool First = true;
72  for (const auto &T : Tokens) {
73  if (!First)
74  OS << " ";
75  else
76  First = false;
77  // Handle 'eof' separately, calling text() on it produces an empty string.
78  if (T.kind() == tok::eof) {
79  OS << "<eof>";
80  continue;
81  }
82  OS << T.text(SM);
83  }
84 }
85 
86 static void dumpTree(llvm::raw_ostream &OS, const syntax::Node *N,
87  const syntax::Arena &A, std::vector<bool> IndentMask) {
88  if (N->role() != syntax::NodeRole::Unknown) {
89  // FIXME: print the symbolic name of a role.
90  if (N->role() == syntax::NodeRole::Detached)
91  OS << "*: ";
92  else
93  OS << static_cast<int>(N->role()) << ": ";
94  }
95  if (auto *L = llvm::dyn_cast<syntax::Leaf>(N)) {
96  dumpTokens(OS, *L->token(), A.sourceManager());
97  OS << "\n";
98  return;
99  }
100 
101  auto *T = llvm::cast<syntax::Tree>(N);
102  OS << T->kind() << "\n";
103 
104  for (auto It = T->firstChild(); It != nullptr; It = It->nextSibling()) {
105  for (bool Filled : IndentMask) {
106  if (Filled)
107  OS << "| ";
108  else
109  OS << " ";
110  }
111  if (!It->nextSibling()) {
112  OS << "`-";
113  IndentMask.push_back(false);
114  } else {
115  OS << "|-";
116  IndentMask.push_back(true);
117  }
118  dumpTree(OS, It, A, IndentMask);
119  IndentMask.pop_back();
120  }
121 }
122 } // namespace
123 
124 std::string syntax::Node::dump(const Arena &A) const {
125  std::string Str;
126  llvm::raw_string_ostream OS(Str);
127  dumpTree(OS, this, A, /*IndentMask=*/{});
128  return std::move(OS.str());
129 }
130 
131 std::string syntax::Node::dumpTokens(const Arena &A) const {
132  std::string Storage;
133  llvm::raw_string_ostream OS(Storage);
134  traverse(this, [&](const syntax::Node *N) {
135  auto *L = llvm::dyn_cast<syntax::Leaf>(N);
136  if (!L)
137  return;
138  ::dumpTokens(OS, *L->token(), A.sourceManager());
139  });
140  return OS.str();
141 }
142 
144  for (auto *C = FirstChild; C; C = C->nextSibling()) {
145  if (C->role() == R)
146  return C;
147  }
148  return nullptr;
149 }
std::pair< FileID, llvm::ArrayRef< syntax::Token > > lexBuffer(std::unique_ptr< llvm::MemoryBuffer > Buffer)
Add Buffer to the underlying source manager, tokenize it and store the resulting tokens.
Definition: Tree.cpp:26
std::string dump(const Arena &A) const
Dumps the structure of a subtree. For debugging and testing purposes.
Definition: Tree.cpp:124
NodeRole role() const
Definition: Tree.h:80
A node in a syntax tree.
Definition: Tree.h:73
A token coming directly from a file or from a macro invocation.
Definition: Tokens.h:100
static bool classof(const Node *N)
Definition: Tree.cpp:45
static bool classof(const Node *N)
Definition: Tree.cpp:37
Definition: Format.h:2392
Node(NodeKind Kind)
Newly created nodes are detached from a tree, parent and sibling links are set when the node is added...
Definition: Tree.cpp:41
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:49
const FormatToken & Tok
const SourceManager & sourceManager() const
Definition: Tree.h:44
NodeId Parent
Definition: ASTDiff.cpp:191
const TokenBuffer & tokenBuffer() const
Definition: Tree.cpp:21
A memory arena for syntax trees.
Definition: Tree.h:39
FileID createFileID(const FileEntry *SourceFile, SourceLocation IncludePos, SrcMgr::CharacteristicKind FileCharacter, int LoadedID=0, unsigned LoadedOffset=0)
Create a new FileID that represents the specified file being #included from the specified IncludePosi...
const SourceManager & SM
Definition: Format.cpp:1667
NodeKind
A kind of a syntax node, used for implementing casts.
Definition: Nodes.h:25
Kind
NodeRole
A relation between a parent and child node. Used for implementing accessors.
Definition: Nodes.h:35
Dataflow Directional Tag Classes.
Arena(SourceManager &SourceMgr, const LangOptions &LangOpts, TokenBuffer Tokens)
Definition: Tree.cpp:17
A leaf node points to a single token inside the expanded token stream.
Definition: Tree.h:104
std::vector< syntax::Token > tokenize(FileID FID, const SourceManager &SM, const LangOptions &LO)
Lex the text buffer, corresponding to FID, in raw mode and record the resulting spelled tokens...
Definition: Tokens.cpp:250
Defines the clang::TokenKind enum and support functions.
Leaf(const syntax::Token *T)
Definition: Tree.cpp:33
NodeKind kind() const
Definition: Tree.h:79
std::string dumpTokens(const Arena &A) const
Dumps the tokens forming this subtree.
Definition: Tree.cpp:131
A list of tokens obtained by preprocessing a text buffer and operations to map between the expanded a...
Definition: Tokens.h:172
This class handles loading and caching of source files into memory.
syntax::Node * findChild(NodeRole R)
Find the first node with a corresponding role.
Definition: Tree.cpp:143