[SyntaxTree][Synthesis] Implement `deepCopy`

[eduucaldas]

Remove extraneous qualifiers in createTree

[eduucaldas]

Rebase

[gribozavr2]

clang/include/clang/Tooling/Syntax/BuildTree.h

45

"Creates a completely independent copy of N (a deep copy)."

clang/lib/Tooling/Syntax/Synthesis.cpp

205

Since we are creating new leaves, why prohibit their mutation sometimes?

I also don't quite understand the implications of having multiple leaves in a tree that are backed by the same token. I think the algorithm that produces edits can be confused by that.

If you agree, please change the implementation to use createLeaf (or call it directly from deepCopy).

clang/unittests/Tooling/Syntax/SynthesisTest.cpp

140

Copy => DeepCopy? (also in other tests)

[eduucaldas]

• deepCopy returns nullptr if copy code with Macro expansions.
• deepCopy also deep copies the Tokens.

[gribozavr2]

clang/lib/Tooling/Syntax/Synthesis.cpp

213

Shouldn't we call canModifyAllDescendants recursively?

225

236

Could you add tests for deepCopy returning nullptr?

[eduucaldas]

clang/lib/Tooling/Syntax/Synthesis.cpp

205

Since we are creating new leaves, why prohibit their mutation sometimes?

The canModify says whether the leaf is backed by a macro.

Since the tokens coming from macros are expanded they would be expanded in the deepCopy as well. We agreed that this shouldn't be the default behaviour. We can have deepCopyExpandingMacros, if the user wants this behaviour, but I think deepCopy should simply forbid macros.

WDYT about deepCopyExpandingMacros?

having multiple leaves in a tree that are backed by the same token

We think the current algorithm wouldn't be confused by that.
However it's easier to reason about Leafs each with their Token, and we don't think creating additional Leaf nodes would affect performance largely.

So we'll call createLeaf instead to create a fresh Leaf with the same Token as the previous one.

234

We are ignoring nullability of pointers.

The casting machinery asserts that on dyn_cast we don't have nullptr. So this code crashes on nullptr.

From what I understand dyn_cast et al. are intended to be used on pointers. Are there other alternatives to this approach? I would like to encode the non-nullability in types instead of in asserts....

[eduucaldas]

Fix canModifyAllDescendants, add tests for it

[eduucaldas]

.

[gribozavr2]

clang/lib/Tooling/Syntax/Synthesis.cpp

205

WDYT about deepCopyExpandingMacros?

That could be a useful operation that we can provide.

234

I don't think it is idiomatic in the LLVM/Clang style to use references for AST nodes and similar things. Beyond that, there is the issue that references are non-rebindable.

clang/unittests/Tooling/Syntax/SynthesisTest.cpp

194

Does EXPECT_EQ work?

clang/include/clang/Tooling/Syntax/BuildTree.h

 // Synthesis of Trees
 /// Creates the concrete syntax node according to the specified `NodeKind` `K`.
 /// Returns it as a pointer to the base class `Tree`.
 syntax::Tree *
 createTree(syntax::Arena &A,
            std::vector<std::pair<syntax::Node *, syntax::NodeRole>> Children,
            syntax::NodeKind K);
 
+/// Deep copies `N`.
+///
+/// The copy is detached, i.e. `Parent == NextSibling == nullptr` and
+/// `Role == Detached`.
+/// The copy is synthesized, i.e. `Original == false`.
+syntax::Node *deepCopy(syntax::Arena &A, const syntax::Node *N);
+
 // Synthesis of Syntax Nodes
 syntax::EmptyStatement *createEmptyStatement(syntax::Arena &A);
 
 } // namespace syntax
 } // namespace clang
 #endif

clang/lib/Tooling/Syntax/Synthesis.cpp

syntax::Tree *clang::syntax::createTree(
   for (auto ChildIt = Children.rbegin(); ChildIt != Children.rend();
        std::advance(ChildIt, 1))
     FactoryImpl::prependChildLowLevel(T, ChildIt->first, ChildIt->second);
 
   T->assertInvariants();
   return T;
 }
 
+static syntax::Leaf *copyLeaf(syntax::Arena &A, const syntax::Leaf *L) {
+  auto *Leaf = new (A.getAllocator()) syntax::Leaf(L->getToken());
+  if (L->canModify())
+    syntax::FactoryImpl::setCanModify(Leaf);
+
+  return Leaf;
+}
+
+syntax::Node *clang::syntax::deepCopy(syntax::Arena &A, const Node *N) {
+  if (const auto *L = dyn_cast<Leaf>(N)) {
+    return copyLeaf(A, L);
+  }
+
+  const auto *T = cast<Tree>(N);
+  auto Children = std::vector<std::pair<Node *, NodeRole>>();
+  for (const auto *C = T->getFirstChild(); C; C = C->getNextSibling()) {
+    Children.push_back({deepCopy(A, C), C->getRole()});
+  }
+  return createTree(A, Children, N->getKind());
+}
+
 syntax::EmptyStatement *clang::syntax::createEmptyStatement(syntax::Arena &A) {
   return cast<EmptyStatement>(
       createTree(A, {{createLeaf(A, tok::semi), NodeRole::Unknown}},
                  NodeKind::EmptyStatement));
 }

clang/unittests/Tooling/Syntax/SynthesisTest.cpp

 |-IntegerLiteralExpression LeftHandSide synthesized
 | `-'1' LiteralToken synthesized
 |-'+' OperatorToken synthesized
 `-IntegerLiteralExpression RightHandSide synthesized
   `-'2' LiteralToken synthesized
   )txt"));
 }
 
+TEST_P(SynthesisTest, Copy_Synthesized) {
+  buildTree("", GetParam());
+
+  auto *LeafContinue = createLeaf(*Arena, tok::kw_continue);
+  auto *LeafSemiColon = createLeaf(*Arena, tok::semi);
+  auto *StatementContinue = createTree(*Arena,
+                                       {{LeafContinue, NodeRole::LiteralToken},
+                                        {LeafSemiColon, NodeRole::Unknown}},
+                                       NodeKind::ContinueStatement);
+
+  auto *Copy = deepCopy(*Arena, StatementContinue);
+  EXPECT_TRUE(
+      treeDumpEqual(Copy, StatementContinue->dump(Arena->getSourceManager())));
+  // FIXME: Test that copy is independent of original, once the Mutations API is
+  // more developed.
+}
+
+TEST_P(SynthesisTest, Copy_Original) {
+  auto *OriginalTree = buildTree("int a;", GetParam());
+
+  auto *Copy = deepCopy(*Arena, OriginalTree);
+  EXPECT_TRUE(treeDumpEqual(Copy, R"txt(
+TranslationUnit Detached synthesized
+`-SimpleDeclaration synthesized
+  |-'int' synthesized
+  |-SimpleDeclarator Declarator synthesized
+  | `-'a' synthesized
+  `-';' synthesized
+  )txt"));
+}
+
+TEST_P(SynthesisTest, Copy_Child) {
+  auto *OriginalTree = buildTree("int a;", GetParam());
+
+  auto *Copy = deepCopy(*Arena, OriginalTree->getFirstChild());
+  EXPECT_TRUE(treeDumpEqual(Copy, R"txt(
+SimpleDeclaration Detached synthesized
+|-'int' synthesized
+|-SimpleDeclarator Declarator synthesized
+| `-'a' synthesized
+`-';' synthesized
+  )txt"));
+}
+
 TEST_P(SynthesisTest, Statement_EmptyStatement) {
   buildTree("", GetParam());
 
   auto *S = createEmptyStatement(*Arena);
   EXPECT_TRUE(treeDumpEqual(S, R"txt(
 EmptyStatement Detached synthesized
 `-';' synthesized
   )txt"));
 }
 } // namespace