Tree.cpp Source File (original) (raw)

11#include "llvm/ADT/BitVector.h"

12#include "llvm/Support/raw_ostream.h"

13#include "llvm/Support/Casting.h"

14#include

16using namespace clang;

18namespace {

20 llvm::function_ref<void(const syntax::Node *)> Visit) {

21 if (auto *T = dyn_castsyntax::Tree(N)) {

24 }

25 Visit(N);

26}

28 llvm::function_ref<void(syntax::Node *)> Visit) {

31 });

32}

33}

38 : Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),

39 Kind(static_cast<unsigned>(Kind)), Role(0), Original(false),

40 CanModify(false) {

42}

46}

48void syntax::Node::setRole(NodeRole NR) {

49 this->Role = static_cast<unsigned>(NR);

50}

52void syntax::Tree::appendChildLowLevel(Node *Child, NodeRole Role) {

56 Child->setRole(Role);

57 appendChildLowLevel(Child);

60void syntax::Tree::appendChildLowLevel(Node *Child) {

61 assert(Child->Parent == nullptr);

62 assert(Child->NextSibling == nullptr);

63 assert(Child->PreviousSibling == nullptr);

66 Child->Parent = this;

67 if (this->LastChild) {

68 Child->PreviousSibling = this->LastChild;

69 this->LastChild->NextSibling = Child;

70 } else

71 this->FirstChild = Child;

73 this->LastChild = Child;

74}

76void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {

80 Child->setRole(Role);

81 prependChildLowLevel(Child);

82}

84void syntax::Tree::prependChildLowLevel(Node *Child) {

85 assert(Child->Parent == nullptr);

86 assert(Child->NextSibling == nullptr);

87 assert(Child->PreviousSibling == nullptr);

90 Child->Parent = this;

91 if (this->FirstChild) {

92 Child->NextSibling = this->FirstChild;

93 this->FirstChild->PreviousSibling = Child;

94 } else

95 this->LastChild = Child;

97 this->FirstChild = Child;

98}

100void syntax::Tree::replaceChildRangeLowLevel(Node *Begin, Node *End,

101 Node *New) {

102 assert(( Begin || Begin->Parent == this) &&

103 "`Begin` is not a child of `this`.");

104 assert((!End || End->Parent == this) && "`End` is not a child of `this`.");

105 assert(canModify() && "Cannot modify `this`.");

106

107#ifndef NDEBUG

108 for (auto *N = New; N; N = N->NextSibling) {

109 assert(N->Parent == nullptr);

111

112 }

113

114 auto Reachable = [](Node *From, Node *N) {

115 if (!N)

116 return true;

117 for (auto *It = From; It; It = It->NextSibling)

118 if (It == N)

119 return true;

120 return false;

121 };

122 assert(Reachable(FirstChild, Begin) && "`Begin` is not reachable.");

123 assert(Reachable(Begin, End) && "`End` is not after `Begin`.");

124#endif

125

126 if (!New && Begin == End)

127 return;

128

129

130 for (auto *T = this; T && T->Original; T = T->Parent)

131 T->Original = false;

132

133

134

135 auto *BeforeBegin = Begin ? Begin->PreviousSibling : LastChild;

136

137

138 for (auto *N = Begin; N != End;) {

139 auto *Next = N->NextSibling;

140

142 N->Parent = nullptr;

143 N->NextSibling = nullptr;

144 N->PreviousSibling = nullptr;

145 if (N->Original)

146 traverse(N, [](Node *C) { C->Original = false; });

147

148 N = Next;

149 }

150

151

152 auto *&NewFirst = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;

153 auto *&NewLast = End ? End->PreviousSibling : LastChild;

154

155 if (!New) {

156 NewFirst = End;

157 NewLast = BeforeBegin;

158 return;

159 }

160

161 New->PreviousSibling = BeforeBegin;

162 NewFirst = New;

163

164 Node *LastInNew;

165 for (auto *N = New; N != nullptr; N = N->NextSibling) {

166 LastInNew = N;

167 N->Parent = this;

168 }

169 LastInNew->NextSibling = End;

170 NewLast = LastInNew;

171}

172

173namespace {

174static void dumpNode(raw_ostream &OS, const syntax::Node *N,

176 auto DumpExtraInfo = [&OS](const syntax::Node *N) {

178 OS << " " << N->getRole();

180 OS << " synthesized";

182 OS << " unmodifiable";

183 };

184

185 assert(N);

186 if (const auto *L = dyn_castsyntax::Leaf(N)) {

187 OS << "'";

188 OS << TM.getText(L->getTokenKey());

189 OS << "'";

190 DumpExtraInfo(N);

191 OS << "\n";

192 return;

193 }

194

195 const auto *T = castsyntax::Tree(N);

196 OS << T->getKind();

197 DumpExtraInfo(N);

198 OS << "\n";

199

200 for (const syntax::Node &It : T->getChildren()) {

201 for (unsigned Idx = 0; Idx < IndentMask.size(); ++Idx) {

202 if (IndentMask[Idx])

203 OS << "| ";

204 else

205 OS << " ";

206 }

207 if (!It.getNextSibling()) {

208 OS << "`-";

209 IndentMask.push_back(false);

210 } else {

211 OS << "|-";

212 IndentMask.push_back(true);

213 }

214 dumpNode(OS, &It, TM, IndentMask);

215 IndentMask.pop_back();

216 }

217}

218}

219

221 std::string Str;

222 llvm::raw_string_ostream OS(Str);

223 dumpNode(OS, this, TM, {});

224 return std::move(OS.str());

225}

226

228 std::string Storage;

229 llvm::raw_string_ostream OS(Storage);

231 if (const auto *L = dyn_castsyntax::Leaf(N)) {

232 OS << TM.getText(L->getTokenKey());

233 OS << " ";

234 }

235 });

236 return Storage;

237}

238

240#ifndef NDEBUG

241 if (isDetached())

242 assert(getParent() == nullptr);

243 else

244 assert(getParent() != nullptr);

245

246 const auto *T = dyn_cast(this);

247 if ()

248 return;

249 for (const Node &C : T->getChildren()) {

250 if (T->isOriginal())

251 assert(C.isOriginal());

252 assert(.isDetached());

253 assert(C.getParent() == T);

254 const auto *Next = C.getNextSibling();

255 assert(!Next || &C == Next->getPreviousSibling());

256 if (.getNextSibling())

257 assert(&C == T->getLastChild() &&

258 "Last child is reachable by advancing from the first child.");

259 }

260

261 const auto *L = dyn_cast(T);

262 if (!L)

263 return;

264 for (const Node &C : T->getChildren()) {

268 assert(isa(C));

269

270

271 }

272 }

273

274#endif

275}

276

278#ifndef NDEBUG

280#endif

281}

282

284 for (const Node &C : getChildren()) {

285 if (const auto *L = dyn_castsyntax::Leaf(&C))

286 return L;

287 if (const auto *L = castsyntax::Tree(C).findFirstLeaf())

288 return L;

289 }

290 return nullptr;

291}

292

294 for (const auto *C = getLastChild(); C; C = C->getPreviousSibling()) {

295 if (const auto *L = dyn_castsyntax::Leaf(C))

296 return L;

297 if (const auto *L = castsyntax::Tree(C)->findLastLeaf())

298 return L;

299 }

300 return nullptr;

301}

302

304 for (const Node &C : getChildren()) {

305 if (C.getRole() == R)

306 return &C;

307 }

308 return nullptr;

309}

310

311std::vector<syntax::List::ElementAndDelimitersyntax::Node>

313 if (!getFirstChild())

314 return {};

315

316 std::vector<syntax::List::ElementAndDelimiter> Children;

317 syntax::Node *ElementWithoutDelimiter = nullptr;

318 for (Node &C : getChildren()) {

319 switch (C.getRole()) {

321 if (ElementWithoutDelimiter) {

322 Children.push_back({ElementWithoutDelimiter, nullptr});

323 }

324 ElementWithoutDelimiter = &C;

325 break;

326 }

328 Children.push_back({ElementWithoutDelimiter, castsyntax::Leaf(&C)});

329 ElementWithoutDelimiter = nullptr;

330 break;

331 }

332 default:

333 llvm_unreachable(

334 "A list can have only elements and delimiters as children.");

335 }

336 }

337

338 switch (getTerminationKind()) {

340 Children.push_back({ElementWithoutDelimiter, nullptr});

341 break;

342 }

345 if (ElementWithoutDelimiter) {

346 Children.push_back({ElementWithoutDelimiter, nullptr});

347 }

348 break;

349 }

350 }

351

352 return Children;

353}

354

355

356

358 if (!getFirstChild())

359 return {};

360

361 std::vector<syntax::Node *> Children;

362 syntax::Node *ElementWithoutDelimiter = nullptr;

363 for (Node &C : getChildren()) {

364 switch (C.getRole()) {

366 if (ElementWithoutDelimiter) {

367 Children.push_back(ElementWithoutDelimiter);

368 }

369 ElementWithoutDelimiter = &C;

370 break;

371 }

373 Children.push_back(ElementWithoutDelimiter);

374 ElementWithoutDelimiter = nullptr;

375 break;

376 }

377 default:

378 llvm_unreachable("A list has only elements or delimiters.");

379 }

380 }

381

382 switch (getTerminationKind()) {

384 Children.push_back(ElementWithoutDelimiter);

385 break;

386 }

389 if (ElementWithoutDelimiter) {

390 Children.push_back(ElementWithoutDelimiter);

391 }

392 break;

393 }

394 }

395

396 return Children;

397}

398

400 switch (this->getKind()) {

401 case NodeKind::NestedNameSpecifier:

402 return clang::tok::coloncolon;

403 case NodeKind::CallArguments:

404 case NodeKind::ParameterDeclarationList:

405 case NodeKind::DeclaratorList:

406 return clang::tok::comma;

407 default:

408 llvm_unreachable("This is not a subclass of List, thus "

409 "getDelimiterTokenKind() cannot be called");

410 }

411}

412

414 switch (this->getKind()) {

415 case NodeKind::NestedNameSpecifier:

416 return TerminationKind::Terminated;

417 case NodeKind::CallArguments:

418 case NodeKind::ParameterDeclarationList:

419 case NodeKind::DeclaratorList:

420 return TerminationKind::Separated;

421 default:

422 llvm_unreachable("This is not a subclass of List, thus "

423 "getTerminationKind() cannot be called");

424 }

425}

426

428 switch (this->getKind()) {

429 case NodeKind::NestedNameSpecifier:

430 return false;

431 case NodeKind::CallArguments:

432 return true;

433 case NodeKind::ParameterDeclarationList:

434 return true;

435 case NodeKind::DeclaratorList:

436 return true;

437 default:

438 llvm_unreachable("This is not a subclass of List, thus canBeEmpty() "

439 "cannot be called");

440 }

441}

static Decl::Kind getKind(const Decl *D)

Defines the clang::TokenKind enum and support functions.

A leaf node points to a single token.

Leaf(TokenManager::Key K)

bool canBeEmpty() const

Whether this list can be empty in syntactically and semantically correct code.

std::vector< Node * > getElementsAsNodes()

Returns the elements of the list.

std::vector< ElementAndDelimiter< Node > > getElementsAsNodesAndDelimiters()

Returns the elements and corresponding delimiters.

TerminationKind getTerminationKind() const

clang::tok::TokenKind getDelimiterTokenKind() const

Returns the appropriate delimiter for this list.

void assertInvariants() const

Asserts invariants on this node of the tree and its immediate children.

bool canModify() const

If this function return false, the tree cannot be modified because there is no reasonable way to prod...

void assertInvariantsRecursive() const

Runs checkInvariants on all nodes in the subtree. No-op if NDEBUG is set.

Node(NodeKind Kind)

Newly created nodes are detached from a tree, parent and sibling links are set when the node is added...

std::string dump(const TokenManager &SM) const

Dumps the structure of a subtree. For debugging and testing purposes.

std::string dumpTokens(const TokenManager &SM) const

Dumps the tokens forming this subtree.

bool isOriginal() const

Whether the node was created from the AST backed by the source code rather than added later through m...

bool isDetached() const

Whether the node is detached from a tree, i.e. does not have a parent.

Defines interfaces for operating "Token" in the clang syntax-tree.

uintptr_t Key

A key to identify a specific token.

virtual llvm::StringRef getText(Key K) const =0

const Leaf * findLastLeaf() const

const Leaf * findFirstLeaf() const

const Node * findChild(NodeRole R) const

Find the first node with a corresponding role.

internal::Matcher< T > traverse(TraversalKind TK, const internal::Matcher< T > &InnerMatcher)

Causes all nested matchers to be matched with the specified traversal kind.

NodeRole

A relation between a parent and child node, e.g.

@ ListElement

List API roles.

@ Detached

A node without a parent.

@ Unknown

Children of an unknown semantic nature, e.g. skipped tokens, comments.

NodeKind

A kind of a syntax node, used for implementing casts.

TokenKind

Provides a simple uniform namespace for tokens from all C languages.

The JSON file list parser is used to communicate input to InstallAPI.

for(const auto &A :T->param_types())

const FunctionProtoType * T