[SyntaxTree] Test `findFirstLeaf` and `findLastLeaf`

[eduucaldas]

Summary

• Introduce TreeTest.cpp to unit test Tree.h
• Add generateAllTreesWithShape to generating test cases
• Add tests for findFirstLeaf and findLastLeaf
• Fix implementations of findFirstLeaf and findLastLeaf that had been broken when empty Tree were present.

Builds upon https://reviews.llvm.org/D87749

[gribozavr2]

clang/unittests/Tooling/Syntax/TreeTest.cpp

10

Please elaborate what "base API" covers -- specifically, what classes and such. However, I'm not sure it is necessary to have this comment at all. Up to you.

40

Is this copied from somewhere? I feel like other tests have this function already. Can we share?

53

under => into?

[eduucaldas]

• Answer Review
• Change names in generateAllTreesWithShape
• auto x = vector() -> vector x;

[eduucaldas]

Comment generateAllTreesWithShape

clang/lib/Tooling/Syntax/Tree.cpp

 
 void syntax::Node::assertInvariantsRecursive() const {
 #ifndef NDEBUG
   traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
 #endif
 }
 
 syntax::Leaf *syntax::Tree::findFirstLeaf() {
-  auto *T = this;
-  while (auto *C = T->getFirstChild()) {
+  for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
     if (auto *L = dyn_cast<syntax::Leaf>(C))
       return L;
-    T = cast<syntax::Tree>(C);
+    if (auto *L = cast<syntax::Tree>(C)->findFirstLeaf())
+      return L;
   }
   return nullptr;
 }
 
 syntax::Leaf *syntax::Tree::findLastLeaf() {
-  auto *T = this;
-  while (auto *C = T->getFirstChild()) {
-    // Find the last child.
-    while (auto *Next = C->getNextSibling())
-      C = Next;
-
+  syntax::Leaf *Last = nullptr;
+  for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
     if (auto *L = dyn_cast<syntax::Leaf>(C))
-      return L;
-    T = cast<syntax::Tree>(C);
+      Last = L;
+    else if (auto *L = cast<syntax::Tree>(C)->findLastLeaf())
+      Last = L;
   }
-  return nullptr;
+  return Last;
 }
 
 syntax::Node *syntax::Tree::findChild(NodeRole R) {
   for (auto *C = FirstChild; C; C = C->getNextSibling()) {
     if (C->getRole() == R)
       return C;
   }
   return nullptr;

clang/unittests/Tooling/Syntax/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_clang_unittest(SyntaxTests
   TreeTestBase.cpp
   BuildTreeTest.cpp
   MutationsTest.cpp
   SynthesisTest.cpp
+  TreeTest.cpp
   TokensTest.cpp
 )
 
 clang_target_link_libraries(SyntaxTests
   PRIVATE
   clangAST
   clangBasic
   clangFrontend

clang/unittests/Tooling/Syntax/TreeTest.cpp

+//===- TreeTest.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 "TreeTestBase.h"
+#include "clang/Tooling/Syntax/BuildTree.h"
+#include "gtest/gtest.h"
+
+using namespace clang;
+using namespace clang::syntax;
+
+namespace {
+
+class TreeTest : public SyntaxTreeTest {
+private:
+  Tree *createTree(ArrayRef<const Node *> Children) {
+    std::vector<std::pair<Node *, NodeRole>> ChildrenWithRoles;
+    ChildrenWithRoles.reserve(Children.size());
+    for (const auto *Child : Children) {
+      ChildrenWithRoles.push_back(
+          std::make_pair(deepCopy(*Arena, Child), NodeRole::Unknown));
+    }
+    return clang::syntax::createTree(*Arena, ChildrenWithRoles,
+                                     NodeKind::UnknownExpression);
+  }
+
+  // Generate Forests by combining `Children` into `ParentCount` Trees.
+  //
+  // We do this recursively.
+  std::vector<std::vector<const Tree *>>
+  generateAllForests(ArrayRef<const Node *> Children, unsigned ParentCount) {
+    assert(ParentCount > 0);
+    // If there is only one Parent node, then combine `Children` under
+    // this Parent.
+    if (ParentCount == 1)
+      return {{createTree(Children)}};
+
+    // Otherwise, combine `ChildrenCount` children under the last parent and
+    // solve the smaller problem without these children and this parent. Do this
+    // for every `ChildrenCount` and combine the results.
+    std::vector<std::vector<const Tree *>> AllForests;
+    for (unsigned ChildrenCount = 0; ChildrenCount <= Children.size();
+         ++ChildrenCount) {
+      auto *LastParent = createTree(Children.take_back(ChildrenCount));
+      for (auto &Forest : generateAllForests(Children.drop_back(ChildrenCount),
+                                             ParentCount - 1)) {
+        Forest.push_back(LastParent);
+        AllForests.push_back(Forest);
+      }
+    }
+    return AllForests;
+  }
+
+protected:
+  // Generates all trees with a `Base` of `Node`s and `NodeCountPerLayer`
+  // `Node`s per layer. An example of Tree with `Base` = {`(`, `)`} and
+  // `NodeCountPerLayer` = {2, 2}:
+  //  Tree
+  //  |-Tree
+  //  `-Tree
+  //    |-Tree
+  //    | `-'('
+  //    `-Tree
+  //      `-')'
+  std::vector<const Tree *>
+  generateAllTreesWithShape(ArrayRef<const Node *> Base,
+                            ArrayRef<unsigned> NodeCountPerLayer) {
+    // We compute the solution per layer. A layer is a collection of bases,
+    // where each base has the same number of nodes, given by
+    // `NodeCountPerLayer`.
+    auto GenerateNextLayer = [this](ArrayRef<std::vector<const Node *>> Layer,
+                                    unsigned NextLayerNodeCount) {
+      std::vector<std::vector<const Node *>> NextLayer;
+      for (const auto &Base : Layer) {
+        for (const auto &NextBase :
+             generateAllForests(Base, NextLayerNodeCount)) {
+          NextLayer.push_back(
+              std::vector<const Node *>(NextBase.begin(), NextBase.end()));
+        }
+      }
+      return NextLayer;
+    };
+
+    std::vector<std::vector<const Node *>> Layer = {Base};
+    for (auto NodeCount : NodeCountPerLayer)
+      Layer = GenerateNextLayer(Layer, NodeCount);
+
+    std::vector<const Tree *> AllTrees;
+    AllTrees.reserve(Layer.size());
+    for (const auto &Base : Layer)
+      AllTrees.push_back(createTree(Base));
+
+    return AllTrees;
+  }
+};
+
+INSTANTIATE_TEST_CASE_P(TreeTests, TreeTest,
+                        ::testing::ValuesIn(allTestClangConfigs()), );
+
+TEST_P(TreeTest, FirstLeaf) {
+  buildTree("", GetParam());
+  std::vector<const Node *> Leafs = {createLeaf(*Arena, tok::l_paren),
+                                     createLeaf(*Arena, tok::r_paren)};
+  for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) {
+    ASSERT_TRUE(Tree->findFirstLeaf() != nullptr);
+    EXPECT_EQ(Tree->findFirstLeaf()->getToken()->kind(), tok::l_paren);
+  }
+}
+
+TEST_P(TreeTest, LastLeaf) {
+  buildTree("", GetParam());
+  std::vector<const Node *> Leafs = {createLeaf(*Arena, tok::l_paren),
+                                     createLeaf(*Arena, tok::r_paren)};
+  for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) {
+    ASSERT_TRUE(Tree->findLastLeaf() != nullptr);
+    EXPECT_EQ(Tree->findLastLeaf()->getToken()->kind(), tok::r_paren);
+  }
+}
+
+} // namespace