1 //===- TreeTest.cpp -------------------------------------------------------===//
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 //===----------------------------------------------------------------------===//
8 
9 #include "clang/Tooling/Syntax/Tree.h"
10 #include "clang/AST/ASTConsumer.h"
11 #include "clang/AST/Decl.h"
12 #include "clang/AST/Stmt.h"
13 #include "clang/Basic/LLVM.h"
14 #include "clang/Basic/TokenKinds.h"
15 #include "clang/Frontend/CompilerInstance.h"
16 #include "clang/Frontend/CompilerInvocation.h"
17 #include "clang/Frontend/FrontendAction.h"
18 #include "clang/Lex/PreprocessorOptions.h"
19 #include "clang/Tooling/Core/Replacement.h"
20 #include "clang/Tooling/Syntax/BuildTree.h"
21 #include "clang/Tooling/Syntax/Mutations.h"
22 #include "clang/Tooling/Syntax/Nodes.h"
23 #include "clang/Tooling/Syntax/Tokens.h"
24 #include "clang/Tooling/Tooling.h"
25 #include "llvm/ADT/ArrayRef.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/ADT/StringRef.h"
28 #include "llvm/Support/Casting.h"
29 #include "llvm/Support/Error.h"
30 #include "llvm/Testing/Support/Annotations.h"
31 #include "gmock/gmock.h"
32 #include "gtest/gtest.h"
33 #include <cstdlib>
34 
35 using namespace clang;
36 
37 namespace {
38 static llvm::ArrayRef<syntax::Token> tokens(syntax::Node *N) {
39   assert(N->isOriginal() && "tokens of modified nodes are not well-defined");
40   if (auto *L = dyn_cast<syntax::Leaf>(N))
41     return llvm::makeArrayRef(L->token(), 1);
42   auto *T = cast<syntax::Tree>(N);
43   return llvm::makeArrayRef(T->firstLeaf()->token(),
44                             T->lastLeaf()->token() + 1);
45 }
46 
47 class SyntaxTreeTest : public ::testing::Test {
48 protected:
49   // Build a syntax tree for the code.
50   syntax::TranslationUnit *buildTree(llvm::StringRef Code) {
51     // FIXME: this code is almost the identical to the one in TokensTest. Share
52     //        it.
53     class BuildSyntaxTree : public ASTConsumer {
54     public:
55       BuildSyntaxTree(syntax::TranslationUnit *&Root,
56                       std::unique_ptr<syntax::Arena> &Arena,
57                       std::unique_ptr<syntax::TokenCollector> Tokens)
58           : Root(Root), Arena(Arena), Tokens(std::move(Tokens)) {
59         assert(this->Tokens);
60       }
61 
62       void HandleTranslationUnit(ASTContext &Ctx) override {
63         Arena = std::make_unique<syntax::Arena>(Ctx.getSourceManager(),
64                                                 Ctx.getLangOpts(),
65                                                 std::move(*Tokens).consume());
66         Tokens = nullptr; // make sure we fail if this gets called twice.
67         Root = syntax::buildSyntaxTree(*Arena, *Ctx.getTranslationUnitDecl());
68       }
69 
70     private:
71       syntax::TranslationUnit *&Root;
72       std::unique_ptr<syntax::Arena> &Arena;
73       std::unique_ptr<syntax::TokenCollector> Tokens;
74     };
75 
76     class BuildSyntaxTreeAction : public ASTFrontendAction {
77     public:
78       BuildSyntaxTreeAction(syntax::TranslationUnit *&Root,
79                             std::unique_ptr<syntax::Arena> &Arena)
80           : Root(Root), Arena(Arena) {}
81 
82       std::unique_ptr<ASTConsumer>
83       CreateASTConsumer(CompilerInstance &CI, StringRef InFile) override {
84         // We start recording the tokens, ast consumer will take on the result.
85         auto Tokens =
86             std::make_unique<syntax::TokenCollector>(CI.getPreprocessor());
87         return std::make_unique<BuildSyntaxTree>(Root, Arena,
88                                                  std::move(Tokens));
89       }
90 
91     private:
92       syntax::TranslationUnit *&Root;
93       std::unique_ptr<syntax::Arena> &Arena;
94     };
95 
96     constexpr const char *FileName = "./input.cpp";
97     FS->addFile(FileName, time_t(), llvm::MemoryBuffer::getMemBufferCopy(""));
98     if (!Diags->getClient())
99       Diags->setClient(new IgnoringDiagConsumer);
100     // Prepare to run a compiler.
101     std::vector<const char *> Args = {"syntax-test", "-std=c++11",
102                                       "-fsyntax-only", FileName};
103     Invocation = createInvocationFromCommandLine(Args, Diags, FS);
104     assert(Invocation);
105     Invocation->getFrontendOpts().DisableFree = false;
106     Invocation->getPreprocessorOpts().addRemappedFile(
107         FileName, llvm::MemoryBuffer::getMemBufferCopy(Code).release());
108     CompilerInstance Compiler;
109     Compiler.setInvocation(Invocation);
110     Compiler.setDiagnostics(Diags.get());
111     Compiler.setFileManager(FileMgr.get());
112     Compiler.setSourceManager(SourceMgr.get());
113 
114     syntax::TranslationUnit *Root = nullptr;
115     BuildSyntaxTreeAction Recorder(Root, this->Arena);
116     if (!Compiler.ExecuteAction(Recorder)) {
117       ADD_FAILURE() << "failed to run the frontend";
118       std::abort();
119     }
120     return Root;
121   }
122 
123   // Adds a file to the test VFS.
124   void addFile(llvm::StringRef Path, llvm::StringRef Contents) {
125     if (!FS->addFile(Path, time_t(),
126                      llvm::MemoryBuffer::getMemBufferCopy(Contents))) {
127       ADD_FAILURE() << "could not add a file to VFS: " << Path;
128     }
129   }
130 
131   /// Finds the deepest node in the tree that covers exactly \p R.
132   /// FIXME: implement this efficiently and move to public syntax tree API.
133   syntax::Node *nodeByRange(llvm::Annotations::Range R, syntax::Node *Root) {
134     llvm::ArrayRef<syntax::Token> Toks = tokens(Root);
135 
136     if (Toks.front().location().isFileID() &&
137         Toks.back().location().isFileID() &&
138         syntax::Token::range(*SourceMgr, Toks.front(), Toks.back()) ==
139             syntax::FileRange(SourceMgr->getMainFileID(), R.Begin, R.End))
140       return Root;
141 
142     auto *T = dyn_cast<syntax::Tree>(Root);
143     if (!T)
144       return nullptr;
145     for (auto *C = T->firstChild(); C != nullptr; C = C->nextSibling()) {
146       if (auto *Result = nodeByRange(R, C))
147         return Result;
148     }
149     return nullptr;
150   }
151 
152   // Data fields.
153   llvm::IntrusiveRefCntPtr<DiagnosticsEngine> Diags =
154       new DiagnosticsEngine(new DiagnosticIDs, new DiagnosticOptions);
155   IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> FS =
156       new llvm::vfs::InMemoryFileSystem;
157   llvm::IntrusiveRefCntPtr<FileManager> FileMgr =
158       new FileManager(FileSystemOptions(), FS);
159   llvm::IntrusiveRefCntPtr<SourceManager> SourceMgr =
160       new SourceManager(*Diags, *FileMgr);
161   std::shared_ptr<CompilerInvocation> Invocation;
162   // Set after calling buildTree().
163   std::unique_ptr<syntax::Arena> Arena;
164 };
165 
166 TEST_F(SyntaxTreeTest, Basic) {
167   std::pair</*Input*/ std::string, /*Expected*/ std::string> Cases[] = {
168       {
169           R"cpp(
170 int main() {}
171 void foo() {}
172     )cpp",
173           R"txt(
174 *: TranslationUnit
175 |-SimpleDeclaration
176 | |-int
177 | |-SimpleDeclarator
178 | | |-main
179 | | `-ParametersAndQualifiers
180 | |   |-(
181 | |   `-)
182 | `-CompoundStatement
183 |   |-{
184 |   `-}
185 `-SimpleDeclaration
186   |-void
187   |-SimpleDeclarator
188   | |-foo
189   | `-ParametersAndQualifiers
190   |   |-(
191   |   `-)
192   `-CompoundStatement
193     |-{
194     `-}
195 )txt"},
196       // if.
197       {
198           R"cpp(
199 int main() {
200   if (true) {}
201   if (true) {} else if (false) {}
202 }
203         )cpp",
204           R"txt(
205 *: TranslationUnit
206 `-SimpleDeclaration
207   |-int
208   |-SimpleDeclarator
209   | |-main
210   | `-ParametersAndQualifiers
211   |   |-(
212   |   `-)
213   `-CompoundStatement
214     |-{
215     |-IfStatement
216     | |-if
217     | |-(
218     | |-UnknownExpression
219     | | `-true
220     | |-)
221     | `-CompoundStatement
222     |   |-{
223     |   `-}
224     |-IfStatement
225     | |-if
226     | |-(
227     | |-UnknownExpression
228     | | `-true
229     | |-)
230     | |-CompoundStatement
231     | | |-{
232     | | `-}
233     | |-else
234     | `-IfStatement
235     |   |-if
236     |   |-(
237     |   |-UnknownExpression
238     |   | `-false
239     |   |-)
240     |   `-CompoundStatement
241     |     |-{
242     |     `-}
243     `-}
244         )txt"},
245       // for.
246       {R"cpp(
247 void test() {
248   for (;;)  {}
249 }
250 )cpp",
251        R"txt(
252 *: TranslationUnit
253 `-SimpleDeclaration
254   |-void
255   |-SimpleDeclarator
256   | |-test
257   | `-ParametersAndQualifiers
258   |   |-(
259   |   `-)
260   `-CompoundStatement
261     |-{
262     |-ForStatement
263     | |-for
264     | |-(
265     | |-;
266     | |-;
267     | |-)
268     | `-CompoundStatement
269     |   |-{
270     |   `-}
271     `-}
272         )txt"},
273       // declaration statement.
274       {"void test() { int a = 10; }",
275        R"txt(
276 *: TranslationUnit
277 `-SimpleDeclaration
278   |-void
279   |-SimpleDeclarator
280   | |-test
281   | `-ParametersAndQualifiers
282   |   |-(
283   |   `-)
284   `-CompoundStatement
285     |-{
286     |-DeclarationStatement
287     | |-SimpleDeclaration
288     | | |-int
289     | | `-SimpleDeclarator
290     | |   |-a
291     | |   |-=
292     | |   `-UnknownExpression
293     | |     `-10
294     | `-;
295     `-}
296 )txt"},
297       {"void test() { ; }", R"txt(
298 *: TranslationUnit
299 `-SimpleDeclaration
300   |-void
301   |-SimpleDeclarator
302   | |-test
303   | `-ParametersAndQualifiers
304   |   |-(
305   |   `-)
306   `-CompoundStatement
307     |-{
308     |-EmptyStatement
309     | `-;
310     `-}
311 )txt"},
312       // switch, case and default.
313       {R"cpp(
314 void test() {
315   switch (true) {
316     case 0:
317     default:;
318   }
319 }
320 )cpp",
321        R"txt(
322 *: TranslationUnit
323 `-SimpleDeclaration
324   |-void
325   |-SimpleDeclarator
326   | |-test
327   | `-ParametersAndQualifiers
328   |   |-(
329   |   `-)
330   `-CompoundStatement
331     |-{
332     |-SwitchStatement
333     | |-switch
334     | |-(
335     | |-UnknownExpression
336     | | `-true
337     | |-)
338     | `-CompoundStatement
339     |   |-{
340     |   |-CaseStatement
341     |   | |-case
342     |   | |-UnknownExpression
343     |   | | `-0
344     |   | |-:
345     |   | `-DefaultStatement
346     |   |   |-default
347     |   |   |-:
348     |   |   `-EmptyStatement
349     |   |     `-;
350     |   `-}
351     `-}
352 )txt"},
353       // while.
354       {R"cpp(
355 void test() {
356   while (true) { continue; break; }
357 }
358 )cpp",
359        R"txt(
360 *: TranslationUnit
361 `-SimpleDeclaration
362   |-void
363   |-SimpleDeclarator
364   | |-test
365   | `-ParametersAndQualifiers
366   |   |-(
367   |   `-)
368   `-CompoundStatement
369     |-{
370     |-WhileStatement
371     | |-while
372     | |-(
373     | |-UnknownExpression
374     | | `-true
375     | |-)
376     | `-CompoundStatement
377     |   |-{
378     |   |-ContinueStatement
379     |   | |-continue
380     |   | `-;
381     |   |-BreakStatement
382     |   | |-break
383     |   | `-;
384     |   `-}
385     `-}
386 )txt"},
387       // return.
388       {R"cpp(
389 int test() { return 1; }
390       )cpp",
391        R"txt(
392 *: TranslationUnit
393 `-SimpleDeclaration
394   |-int
395   |-SimpleDeclarator
396   | |-test
397   | `-ParametersAndQualifiers
398   |   |-(
399   |   `-)
400   `-CompoundStatement
401     |-{
402     |-ReturnStatement
403     | |-return
404     | |-UnknownExpression
405     | | `-1
406     | `-;
407     `-}
408 )txt"},
409       // Range-based for.
410       {R"cpp(
411 void test() {
412   int a[3];
413   for (int x : a) ;
414 }
415       )cpp",
416        R"txt(
417 *: TranslationUnit
418 `-SimpleDeclaration
419   |-void
420   |-SimpleDeclarator
421   | |-test
422   | `-ParametersAndQualifiers
423   |   |-(
424   |   `-)
425   `-CompoundStatement
426     |-{
427     |-DeclarationStatement
428     | |-SimpleDeclaration
429     | | |-int
430     | | `-SimpleDeclarator
431     | |   |-a
432     | |   `-ArraySubscript
433     | |     |-[
434     | |     |-UnknownExpression
435     | |     | `-3
436     | |     `-]
437     | `-;
438     |-RangeBasedForStatement
439     | |-for
440     | |-(
441     | |-SimpleDeclaration
442     | | |-int
443     | | |-SimpleDeclarator
444     | | | `-x
445     | | `-:
446     | |-UnknownExpression
447     | | `-a
448     | |-)
449     | `-EmptyStatement
450     |   `-;
451     `-}
452        )txt"},
453       // Unhandled statements should end up as 'unknown statement'.
454       // This example uses a 'label statement', which does not yet have a syntax
455       // counterpart.
456       {"void main() { foo: return 100; }", R"txt(
457 *: TranslationUnit
458 `-SimpleDeclaration
459   |-void
460   |-SimpleDeclarator
461   | |-main
462   | `-ParametersAndQualifiers
463   |   |-(
464   |   `-)
465   `-CompoundStatement
466     |-{
467     |-UnknownStatement
468     | |-foo
469     | |-:
470     | `-ReturnStatement
471     |   |-return
472     |   |-UnknownExpression
473     |   | `-100
474     |   `-;
475     `-}
476 )txt"},
477       // expressions should be wrapped in 'ExpressionStatement' when they appear
478       // in a statement position.
479       {R"cpp(
480 void test() {
481   test();
482   if (true) test(); else test();
483 }
484     )cpp",
485        R"txt(
486 *: TranslationUnit
487 `-SimpleDeclaration
488   |-void
489   |-SimpleDeclarator
490   | |-test
491   | `-ParametersAndQualifiers
492   |   |-(
493   |   `-)
494   `-CompoundStatement
495     |-{
496     |-ExpressionStatement
497     | |-UnknownExpression
498     | | |-test
499     | | |-(
500     | | `-)
501     | `-;
502     |-IfStatement
503     | |-if
504     | |-(
505     | |-UnknownExpression
506     | | `-true
507     | |-)
508     | |-ExpressionStatement
509     | | |-UnknownExpression
510     | | | |-test
511     | | | |-(
512     | | | `-)
513     | | `-;
514     | |-else
515     | `-ExpressionStatement
516     |   |-UnknownExpression
517     |   | |-test
518     |   | |-(
519     |   | `-)
520     |   `-;
521     `-}
522 )txt"},
523       // Multiple declarators group into a single SimpleDeclaration.
524       {R"cpp(
525       int *a, b;
526   )cpp",
527        R"txt(
528 *: TranslationUnit
529 `-SimpleDeclaration
530   |-int
531   |-SimpleDeclarator
532   | |-*
533   | `-a
534   |-,
535   |-SimpleDeclarator
536   | `-b
537   `-;
538   )txt"},
539       {R"cpp(
540     typedef int *a, b;
541   )cpp",
542        R"txt(
543 *: TranslationUnit
544 `-SimpleDeclaration
545   |-typedef
546   |-int
547   |-SimpleDeclarator
548   | |-*
549   | `-a
550   |-,
551   |-SimpleDeclarator
552   | `-b
553   `-;
554   )txt"},
555       // Multiple declarators inside a statement.
556       {R"cpp(
557 void foo() {
558       int *a, b;
559       typedef int *ta, tb;
560 }
561   )cpp",
562        R"txt(
563 *: TranslationUnit
564 `-SimpleDeclaration
565   |-void
566   |-SimpleDeclarator
567   | |-foo
568   | `-ParametersAndQualifiers
569   |   |-(
570   |   `-)
571   `-CompoundStatement
572     |-{
573     |-DeclarationStatement
574     | |-SimpleDeclaration
575     | | |-int
576     | | |-SimpleDeclarator
577     | | | |-*
578     | | | `-a
579     | | |-,
580     | | `-SimpleDeclarator
581     | |   `-b
582     | `-;
583     |-DeclarationStatement
584     | |-SimpleDeclaration
585     | | |-typedef
586     | | |-int
587     | | |-SimpleDeclarator
588     | | | |-*
589     | | | `-ta
590     | | |-,
591     | | `-SimpleDeclarator
592     | |   `-tb
593     | `-;
594     `-}
595   )txt"},
596       {R"cpp(
597 namespace a { namespace b {} }
598 namespace a::b {}
599 namespace {}
600 
601 namespace foo = a;
602     )cpp",
603        R"txt(
604 *: TranslationUnit
605 |-NamespaceDefinition
606 | |-namespace
607 | |-a
608 | |-{
609 | |-NamespaceDefinition
610 | | |-namespace
611 | | |-b
612 | | |-{
613 | | `-}
614 | `-}
615 |-NamespaceDefinition
616 | |-namespace
617 | |-a
618 | |-::
619 | |-b
620 | |-{
621 | `-}
622 |-NamespaceDefinition
623 | |-namespace
624 | |-{
625 | `-}
626 `-NamespaceAliasDefinition
627   |-namespace
628   |-foo
629   |-=
630   |-a
631   `-;
632 )txt"},
633       // Free-standing classes, must live inside a SimpleDeclaration.
634       {R"cpp(
635 sturct X;
636 struct X {};
637 
638 struct Y *y1;
639 struct Y {} *y2;
640 
641 struct {} *a1;
642     )cpp",
643        R"txt(
644 *: TranslationUnit
645 |-SimpleDeclaration
646 | |-sturct
647 | |-X
648 | `-;
649 |-SimpleDeclaration
650 | |-struct
651 | |-X
652 | |-{
653 | |-}
654 | `-;
655 |-SimpleDeclaration
656 | |-struct
657 | |-Y
658 | |-SimpleDeclarator
659 | | |-*
660 | | `-y1
661 | `-;
662 |-SimpleDeclaration
663 | |-struct
664 | |-Y
665 | |-{
666 | |-}
667 | |-SimpleDeclarator
668 | | |-*
669 | | `-y2
670 | `-;
671 `-SimpleDeclaration
672   |-struct
673   |-{
674   |-}
675   |-SimpleDeclarator
676   | |-*
677   | `-a1
678   `-;
679 )txt"},
680       {R"cpp(
681 namespace ns {}
682 using namespace ::ns;
683     )cpp",
684        R"txt(
685 *: TranslationUnit
686 |-NamespaceDefinition
687 | |-namespace
688 | |-ns
689 | |-{
690 | `-}
691 `-UsingNamespaceDirective
692   |-using
693   |-namespace
694   |-::
695   |-ns
696   `-;
697        )txt"},
698       {R"cpp(
699 namespace ns { int a; }
700 using ns::a;
701     )cpp",
702        R"txt(
703 *: TranslationUnit
704 |-NamespaceDefinition
705 | |-namespace
706 | |-ns
707 | |-{
708 | |-SimpleDeclaration
709 | | |-int
710 | | |-SimpleDeclarator
711 | | | `-a
712 | | `-;
713 | `-}
714 `-UsingDeclaration
715   |-using
716   |-ns
717   |-::
718   |-a
719   `-;
720        )txt"},
721       {R"cpp(
722 template <class T> struct X {
723   using T::foo;
724   using typename T::bar;
725 };
726     )cpp",
727        R"txt(
728 *: TranslationUnit
729 `-UnknownDeclaration
730   |-template
731   |-<
732   |-UnknownDeclaration
733   | |-class
734   | `-T
735   |->
736   `-SimpleDeclaration
737     |-struct
738     |-X
739     |-{
740     |-UsingDeclaration
741     | |-using
742     | |-T
743     | |-::
744     | |-foo
745     | `-;
746     |-UsingDeclaration
747     | |-using
748     | |-typename
749     | |-T
750     | |-::
751     | |-bar
752     | `-;
753     |-}
754     `-;
755        )txt"},
756       {R"cpp(
757 using type = int;
758     )cpp",
759        R"txt(
760 *: TranslationUnit
761 `-TypeAliasDeclaration
762   |-using
763   |-type
764   |-=
765   |-int
766   `-;
767        )txt"},
768       {R"cpp(
769 ;
770     )cpp",
771        R"txt(
772 *: TranslationUnit
773 `-EmptyDeclaration
774   `-;
775        )txt"},
776       {R"cpp(
777 static_assert(true, "message");
778 static_assert(true);
779     )cpp",
780        R"txt(
781 *: TranslationUnit
782 |-StaticAssertDeclaration
783 | |-static_assert
784 | |-(
785 | |-UnknownExpression
786 | | `-true
787 | |-,
788 | |-UnknownExpression
789 | | `-"message"
790 | |-)
791 | `-;
792 `-StaticAssertDeclaration
793   |-static_assert
794   |-(
795   |-UnknownExpression
796   | `-true
797   |-)
798   `-;
799        )txt"},
800       {R"cpp(
801 extern "C" int a;
802 extern "C" { int b; int c; }
803     )cpp",
804        R"txt(
805 *: TranslationUnit
806 |-LinkageSpecificationDeclaration
807 | |-extern
808 | |-"C"
809 | `-SimpleDeclaration
810 |   |-int
811 |   |-SimpleDeclarator
812 |   | `-a
813 |   `-;
814 `-LinkageSpecificationDeclaration
815   |-extern
816   |-"C"
817   |-{
818   |-SimpleDeclaration
819   | |-int
820   | |-SimpleDeclarator
821   | | `-b
822   | `-;
823   |-SimpleDeclaration
824   | |-int
825   | |-SimpleDeclarator
826   | | `-c
827   | `-;
828   `-}
829        )txt"},
830       // Some nodes are non-modifiable, they are marked with 'I:'.
831       {R"cpp(
832 #define HALF_IF if (1+
833 #define HALF_IF_2 1) {}
834 void test() {
835   HALF_IF HALF_IF_2 else {}
836 })cpp",
837        R"txt(
838 *: TranslationUnit
839 `-SimpleDeclaration
840   |-void
841   |-SimpleDeclarator
842   | |-test
843   | `-ParametersAndQualifiers
844   |   |-(
845   |   `-)
846   `-CompoundStatement
847     |-{
848     |-IfStatement
849     | |-I: if
850     | |-I: (
851     | |-I: UnknownExpression
852     | | |-I: 1
853     | | |-I: +
854     | | `-I: 1
855     | |-I: )
856     | |-I: CompoundStatement
857     | | |-I: {
858     | | `-I: }
859     | |-else
860     | `-CompoundStatement
861     |   |-{
862     |   `-}
863     `-}
864        )txt"},
865       // All nodes can be mutated.
866       {R"cpp(
867 #define OPEN {
868 #define CLOSE }
869 
870 void test() {
871   OPEN
872     1;
873   CLOSE
874 
875   OPEN
876     2;
877   }
878 }
879 )cpp",
880        R"txt(
881 *: TranslationUnit
882 `-SimpleDeclaration
883   |-void
884   |-SimpleDeclarator
885   | |-test
886   | `-ParametersAndQualifiers
887   |   |-(
888   |   `-)
889   `-CompoundStatement
890     |-{
891     |-CompoundStatement
892     | |-{
893     | |-ExpressionStatement
894     | | |-UnknownExpression
895     | | | `-1
896     | | `-;
897     | `-}
898     |-CompoundStatement
899     | |-{
900     | |-ExpressionStatement
901     | | |-UnknownExpression
902     | | | `-2
903     | | `-;
904     | `-}
905     `-}
906        )txt"},
907       // Array subscripts in declarators.
908       {R"cpp(
909 int a[10];
910 int b[1][2][3];
911 int c[] = {1,2,3};
912 void f(int xs[static 10]);
913     )cpp",
914        R"txt(
915 *: TranslationUnit
916 |-SimpleDeclaration
917 | |-int
918 | |-SimpleDeclarator
919 | | |-a
920 | | `-ArraySubscript
921 | |   |-[
922 | |   |-UnknownExpression
923 | |   | `-10
924 | |   `-]
925 | `-;
926 |-SimpleDeclaration
927 | |-int
928 | |-SimpleDeclarator
929 | | |-b
930 | | |-ArraySubscript
931 | | | |-[
932 | | | |-UnknownExpression
933 | | | | `-1
934 | | | `-]
935 | | |-ArraySubscript
936 | | | |-[
937 | | | |-UnknownExpression
938 | | | | `-2
939 | | | `-]
940 | | `-ArraySubscript
941 | |   |-[
942 | |   |-UnknownExpression
943 | |   | `-3
944 | |   `-]
945 | `-;
946 |-SimpleDeclaration
947 | |-int
948 | |-SimpleDeclarator
949 | | |-c
950 | | |-ArraySubscript
951 | | | |-[
952 | | | `-]
953 | | |-=
954 | | `-UnknownExpression
955 | |   |-{
956 | |   |-1
957 | |   |-,
958 | |   |-2
959 | |   |-,
960 | |   |-3
961 | |   `-}
962 | `-;
963 `-SimpleDeclaration
964   |-void
965   |-SimpleDeclarator
966   | |-f
967   | `-ParametersAndQualifiers
968   |   |-(
969   |   |-SimpleDeclaration
970   |   | |-int
971   |   | `-SimpleDeclarator
972   |   |   |-xs
973   |   |   `-ArraySubscript
974   |   |     |-[
975   |   |     |-static
976   |   |     |-UnknownExpression
977   |   |     | `-10
978   |   |     `-]
979   |   `-)
980   `-;
981        )txt"},
982       // Parameter lists in declarators.
983       {R"cpp(
984 int a() const;
985 int b() volatile;
986 int c() &;
987 int d() &&;
988 int foo(int a, int b);
989 int foo(
990   const int a,
991   volatile int b,
992   const volatile int c,
993   int* d,
994   int& e,
995   int&& f
996 );
997     )cpp",
998        R"txt(
999 *: TranslationUnit
1000 |-SimpleDeclaration
1001 | |-int
1002 | |-SimpleDeclarator
1003 | | |-a
1004 | | `-ParametersAndQualifiers
1005 | |   |-(
1006 | |   |-)
1007 | |   `-const
1008 | `-;
1009 |-SimpleDeclaration
1010 | |-int
1011 | |-SimpleDeclarator
1012 | | |-b
1013 | | `-ParametersAndQualifiers
1014 | |   |-(
1015 | |   |-)
1016 | |   `-volatile
1017 | `-;
1018 |-SimpleDeclaration
1019 | |-int
1020 | |-SimpleDeclarator
1021 | | |-c
1022 | | `-ParametersAndQualifiers
1023 | |   |-(
1024 | |   |-)
1025 | |   `-&
1026 | `-;
1027 |-SimpleDeclaration
1028 | |-int
1029 | |-SimpleDeclarator
1030 | | |-d
1031 | | `-ParametersAndQualifiers
1032 | |   |-(
1033 | |   |-)
1034 | |   `-&&
1035 | `-;
1036 |-SimpleDeclaration
1037 | |-int
1038 | |-SimpleDeclarator
1039 | | |-foo
1040 | | `-ParametersAndQualifiers
1041 | |   |-(
1042 | |   |-SimpleDeclaration
1043 | |   | |-int
1044 | |   | `-SimpleDeclarator
1045 | |   |   `-a
1046 | |   |-,
1047 | |   |-SimpleDeclaration
1048 | |   | |-int
1049 | |   | `-SimpleDeclarator
1050 | |   |   `-b
1051 | |   `-)
1052 | `-;
1053 `-SimpleDeclaration
1054   |-int
1055   |-SimpleDeclarator
1056   | |-foo
1057   | `-ParametersAndQualifiers
1058   |   |-(
1059   |   |-SimpleDeclaration
1060   |   | |-const
1061   |   | |-int
1062   |   | `-SimpleDeclarator
1063   |   |   `-a
1064   |   |-,
1065   |   |-SimpleDeclaration
1066   |   | |-volatile
1067   |   | |-int
1068   |   | `-SimpleDeclarator
1069   |   |   `-b
1070   |   |-,
1071   |   |-SimpleDeclaration
1072   |   | |-const
1073   |   | |-volatile
1074   |   | |-int
1075   |   | `-SimpleDeclarator
1076   |   |   `-c
1077   |   |-,
1078   |   |-SimpleDeclaration
1079   |   | |-int
1080   |   | `-SimpleDeclarator
1081   |   |   |-*
1082   |   |   `-d
1083   |   |-,
1084   |   |-SimpleDeclaration
1085   |   | |-int
1086   |   | `-SimpleDeclarator
1087   |   |   |-&
1088   |   |   `-e
1089   |   |-,
1090   |   |-SimpleDeclaration
1091   |   | |-int
1092   |   | `-SimpleDeclarator
1093   |   |   |-&&
1094   |   |   `-f
1095   |   `-)
1096   `-;
1097        )txt"},
1098       // Trailing const qualifier.
1099       {R"cpp(
1100 struct X {
1101   int foo() const;
1102 }
1103     )cpp",
1104        R"txt(
1105 *: TranslationUnit
1106 `-SimpleDeclaration
1107   |-struct
1108   |-X
1109   |-{
1110   |-SimpleDeclaration
1111   | |-int
1112   | |-SimpleDeclarator
1113   | | |-foo
1114   | | `-ParametersAndQualifiers
1115   | |   |-(
1116   | |   |-)
1117   | |   `-const
1118   | `-;
1119   `-}
1120     )txt"},
1121       // Trailing return type in parameter lists.
1122       {R"cpp(
1123 auto foo() -> int;
1124     )cpp",
1125        R"txt(
1126 *: TranslationUnit
1127 `-SimpleDeclaration
1128   |-auto
1129   |-SimpleDeclarator
1130   | |-foo
1131   | `-ParametersAndQualifiers
1132   |   |-(
1133   |   |-)
1134   |   `-TrailingReturnType
1135   |     |-->
1136   |     `-int
1137   `-;
1138        )txt"},
1139       // Exception specification in parameter lists.
1140       {R"cpp(
1141 int a() noexcept;
1142 int b() noexcept(true);
1143 int c() throw();
1144     )cpp",
1145        R"txt(
1146 *: TranslationUnit
1147 |-SimpleDeclaration
1148 | |-int
1149 | |-SimpleDeclarator
1150 | | |-a
1151 | | `-ParametersAndQualifiers
1152 | |   |-(
1153 | |   |-)
1154 | |   `-noexcept
1155 | `-;
1156 |-SimpleDeclaration
1157 | |-int
1158 | |-SimpleDeclarator
1159 | | |-b
1160 | | `-ParametersAndQualifiers
1161 | |   |-(
1162 | |   |-)
1163 | |   |-noexcept
1164 | |   |-(
1165 | |   |-UnknownExpression
1166 | |   | `-true
1167 | |   `-)
1168 | `-;
1169 `-SimpleDeclaration
1170   |-int
1171   |-SimpleDeclarator
1172   | |-c
1173   | `-ParametersAndQualifiers
1174   |   |-(
1175   |   |-)
1176   |   |-throw
1177   |   |-(
1178   |   `-)
1179   `-;
1180        )txt"},
1181       // Declarators in parentheses.
1182       {R"cpp(
1183 int (a);
1184 int *(b);
1185 int (*c)(int);
1186 int *(d)(int);
1187     )cpp",
1188        R"txt(
1189 *: TranslationUnit
1190 |-SimpleDeclaration
1191 | |-int
1192 | |-SimpleDeclarator
1193 | | `-ParenDeclarator
1194 | |   |-(
1195 | |   |-a
1196 | |   `-)
1197 | `-;
1198 |-SimpleDeclaration
1199 | |-int
1200 | |-SimpleDeclarator
1201 | | |-*
1202 | | `-ParenDeclarator
1203 | |   |-(
1204 | |   |-b
1205 | |   `-)
1206 | `-;
1207 |-SimpleDeclaration
1208 | |-int
1209 | |-SimpleDeclarator
1210 | | |-ParenDeclarator
1211 | | | |-(
1212 | | | |-*
1213 | | | |-c
1214 | | | `-)
1215 | | `-ParametersAndQualifiers
1216 | |   |-(
1217 | |   |-SimpleDeclaration
1218 | |   | `-int
1219 | |   `-)
1220 | `-;
1221 `-SimpleDeclaration
1222   |-int
1223   |-SimpleDeclarator
1224   | |-*
1225   | |-ParenDeclarator
1226   | | |-(
1227   | | |-d
1228   | | `-)
1229   | `-ParametersAndQualifiers
1230   |   |-(
1231   |   |-SimpleDeclaration
1232   |   | `-int
1233   |   `-)
1234   `-;
1235        )txt"},
1236       // CV qualifiers.
1237       {R"cpp(
1238 const int west = -1;
1239 int const east = 1;
1240 const int const universal = 0;
1241 const int const *const *volatile b;
1242     )cpp",
1243        R"txt(
1244 *: TranslationUnit
1245 |-SimpleDeclaration
1246 | |-const
1247 | |-int
1248 | |-SimpleDeclarator
1249 | | |-west
1250 | | |-=
1251 | | `-UnknownExpression
1252 | |   |--
1253 | |   `-1
1254 | `-;
1255 |-SimpleDeclaration
1256 | |-int
1257 | |-const
1258 | |-SimpleDeclarator
1259 | | |-east
1260 | | |-=
1261 | | `-UnknownExpression
1262 | |   `-1
1263 | `-;
1264 |-SimpleDeclaration
1265 | |-const
1266 | |-int
1267 | |-const
1268 | |-SimpleDeclarator
1269 | | |-universal
1270 | | |-=
1271 | | `-UnknownExpression
1272 | |   `-0
1273 | `-;
1274 `-SimpleDeclaration
1275   |-const
1276   |-int
1277   |-const
1278   |-SimpleDeclarator
1279   | |-*
1280   | |-const
1281   | |-*
1282   | |-volatile
1283   | `-b
1284   `-;
1285        )txt"},
1286       // Ranges of declarators with trailing return types.
1287       {R"cpp(
1288 auto foo() -> auto(*)(int) -> double*;
1289     )cpp",
1290        R"txt(
1291 *: TranslationUnit
1292 `-SimpleDeclaration
1293   |-auto
1294   |-SimpleDeclarator
1295   | |-foo
1296   | `-ParametersAndQualifiers
1297   |   |-(
1298   |   |-)
1299   |   `-TrailingReturnType
1300   |     |-->
1301   |     |-auto
1302   |     `-SimpleDeclarator
1303   |       |-ParenDeclarator
1304   |       | |-(
1305   |       | |-*
1306   |       | `-)
1307   |       `-ParametersAndQualifiers
1308   |         |-(
1309   |         |-SimpleDeclaration
1310   |         | `-int
1311   |         |-)
1312   |         `-TrailingReturnType
1313   |           |-->
1314   |           |-double
1315   |           `-SimpleDeclarator
1316   |             `-*
1317   `-;
1318        )txt"},
1319       // Member pointers.
1320       {R"cpp(
1321 struct X {};
1322 int X::* a;
1323 const int X::* b;
1324     )cpp",
1325        R"txt(
1326 *: TranslationUnit
1327 |-SimpleDeclaration
1328 | |-struct
1329 | |-X
1330 | |-{
1331 | |-}
1332 | `-;
1333 |-SimpleDeclaration
1334 | |-int
1335 | |-SimpleDeclarator
1336 | | |-MemberPointer
1337 | | | |-X
1338 | | | |-::
1339 | | | `-*
1340 | | `-a
1341 | `-;
1342 `-SimpleDeclaration
1343   |-const
1344   |-int
1345   |-SimpleDeclarator
1346   | |-MemberPointer
1347   | | |-X
1348   | | |-::
1349   | | `-*
1350   | `-b
1351   `-;
1352        )txt"},
1353       // All-in-one tests.
1354       {R"cpp(
1355 void x(char a, short (*b)(int));
1356     )cpp",
1357        R"txt(
1358 *: TranslationUnit
1359 `-SimpleDeclaration
1360   |-void
1361   |-SimpleDeclarator
1362   | |-x
1363   | `-ParametersAndQualifiers
1364   |   |-(
1365   |   |-SimpleDeclaration
1366   |   | |-char
1367   |   | `-SimpleDeclarator
1368   |   |   `-a
1369   |   |-,
1370   |   |-SimpleDeclaration
1371   |   | |-short
1372   |   | `-SimpleDeclarator
1373   |   |   |-ParenDeclarator
1374   |   |   | |-(
1375   |   |   | |-*
1376   |   |   | |-b
1377   |   |   | `-)
1378   |   |   `-ParametersAndQualifiers
1379   |   |     |-(
1380   |   |     |-SimpleDeclaration
1381   |   |     | `-int
1382   |   |     `-)
1383   |   `-)
1384   `-;
1385        )txt"},
1386       {R"cpp(
1387 void x(char a, short (*b)(int), long (**c)(long long));
1388     )cpp",
1389        R"txt(
1390 *: TranslationUnit
1391 `-SimpleDeclaration
1392   |-void
1393   |-SimpleDeclarator
1394   | |-x
1395   | `-ParametersAndQualifiers
1396   |   |-(
1397   |   |-SimpleDeclaration
1398   |   | |-char
1399   |   | `-SimpleDeclarator
1400   |   |   `-a
1401   |   |-,
1402   |   |-SimpleDeclaration
1403   |   | |-short
1404   |   | `-SimpleDeclarator
1405   |   |   |-ParenDeclarator
1406   |   |   | |-(
1407   |   |   | |-*
1408   |   |   | |-b
1409   |   |   | `-)
1410   |   |   `-ParametersAndQualifiers
1411   |   |     |-(
1412   |   |     |-SimpleDeclaration
1413   |   |     | `-int
1414   |   |     `-)
1415   |   |-,
1416   |   |-SimpleDeclaration
1417   |   | |-long
1418   |   | `-SimpleDeclarator
1419   |   |   |-ParenDeclarator
1420   |   |   | |-(
1421   |   |   | |-*
1422   |   |   | |-*
1423   |   |   | |-c
1424   |   |   | `-)
1425   |   |   `-ParametersAndQualifiers
1426   |   |     |-(
1427   |   |     |-SimpleDeclaration
1428   |   |     | |-long
1429   |   |     | `-long
1430   |   |     `-)
1431   |   `-)
1432   `-;
1433        )txt"},
1434   };
1435 
1436   for (const auto &T : Cases) {
1437     SCOPED_TRACE(T.first);
1438 
1439     auto *Root = buildTree(T.first);
1440     std::string Expected = llvm::StringRef(T.second).trim().str();
1441     std::string Actual =
1442         std::string(llvm::StringRef(Root->dump(*Arena)).trim());
1443     EXPECT_EQ(Expected, Actual) << "the resulting dump is:\n" << Actual;
1444   }
1445 }
1446 
1447 TEST_F(SyntaxTreeTest, Mutations) {
1448   using Transformation = std::function<void(
1449       const llvm::Annotations & /*Input*/, syntax::TranslationUnit * /*Root*/)>;
1450   auto CheckTransformation = [this](std::string Input, std::string Expected,
1451                                     Transformation Transform) -> void {
1452     llvm::Annotations Source(Input);
1453     auto *Root = buildTree(Source.code());
1454 
1455     Transform(Source, Root);
1456 
1457     auto Replacements = syntax::computeReplacements(*Arena, *Root);
1458     auto Output = tooling::applyAllReplacements(Source.code(), Replacements);
1459     if (!Output) {
1460       ADD_FAILURE() << "could not apply replacements: "
1461                     << llvm::toString(Output.takeError());
1462       return;
1463     }
1464 
1465     EXPECT_EQ(Expected, *Output) << "input is:\n" << Input;
1466   };
1467 
1468   // Removes the selected statement. Input should have exactly one selected
1469   // range and it should correspond to a single statement.
1470   auto RemoveStatement = [this](const llvm::Annotations &Input,
1471                                 syntax::TranslationUnit *TU) {
1472     auto *S = cast<syntax::Statement>(nodeByRange(Input.range(), TU));
1473     ASSERT_TRUE(S->canModify()) << "cannot remove a statement";
1474     syntax::removeStatement(*Arena, S);
1475     EXPECT_TRUE(S->isDetached());
1476     EXPECT_FALSE(S->isOriginal())
1477         << "node removed from tree cannot be marked as original";
1478   };
1479 
1480   std::vector<std::pair<std::string /*Input*/, std::string /*Expected*/>>
1481       Cases = {
1482           {"void test() { [[100+100;]] test(); }", "void test() {  test(); }"},
1483           {"void test() { if (true) [[{}]] else {} }",
1484            "void test() { if (true) ; else {} }"},
1485           {"void test() { [[;]] }", "void test() {  }"}};
1486   for (const auto &C : Cases)
1487     CheckTransformation(C.first, C.second, RemoveStatement);
1488 }
1489 
1490 TEST_F(SyntaxTreeTest, SynthesizedNodes) {
1491   buildTree("");
1492 
1493   auto *C = syntax::createPunctuation(*Arena, tok::comma);
1494   ASSERT_NE(C, nullptr);
1495   EXPECT_EQ(C->token()->kind(), tok::comma);
1496   EXPECT_TRUE(C->canModify());
1497   EXPECT_FALSE(C->isOriginal());
1498   EXPECT_TRUE(C->isDetached());
1499 
1500   auto *S = syntax::createEmptyStatement(*Arena);
1501   ASSERT_NE(S, nullptr);
1502   EXPECT_TRUE(S->canModify());
1503   EXPECT_FALSE(S->isOriginal());
1504   EXPECT_TRUE(S->isDetached());
1505 }
1506 
1507 } // namespace
1508