[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

207

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

166

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

215

Shouldn't we call canModifyAllDescendants recursively?

227

238

Could you add tests for deepCopy returning nullptr?

[eduucaldas]

clang/lib/Tooling/Syntax/Synthesis.cpp

207

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.

236

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

207

WDYT about deepCopyExpandingMacros?

That could be a useful operation that we can provide.

236

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

220

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);
 
 // Synthesis of Syntax Nodes
 syntax::EmptyStatement *createEmptyStatement(syntax::Arena &A);
 
+/// Creates a completely independent copy of `N` (a deep copy).
+///
+/// The copy is:
+/// * Detached, i.e. `Parent == NextSibling == nullptr` and
+/// `Role == Detached`.
+/// * Synthesized, i.e. `Original == false`.
+///
+/// `N` might be backed by source code but if any descendants of `N` are
+/// unmodifiable returns `nullptr`.
+syntax::Node *deepCopy(syntax::Arena &A, const syntax::Node *N);
+
 } // namespace syntax
 } // namespace clang
 #endif

clang/lib/Tooling/Syntax/Synthesis.cpp

public:
   }
 
   static std::pair<FileID, ArrayRef<Token>>
   lexBuffer(syntax::Arena &A, std::unique_ptr<llvm::MemoryBuffer> Buffer) {
     return A.lexBuffer(std::move(Buffer));
   }
 };
 
+// FIXME: `createLeaf` is based on `syntax::tokenize` internally, as such it
+// doesn't support digraphs or line continuations.
 syntax::Leaf *clang::syntax::createLeaf(syntax::Arena &A, tok::TokenKind K,
                                         StringRef Spelling) {
   auto Tokens =
-      FactoryImpl::lexBuffer(A, llvm::MemoryBuffer::getMemBuffer(Spelling))
+      FactoryImpl::lexBuffer(A, llvm::MemoryBuffer::getMemBufferCopy(Spelling))
           .second;
   assert(Tokens.size() == 1);
   assert(Tokens.front().kind() == K &&
          "spelling is not lexed into the expected kind of token");
 
   auto *Leaf = new (A.getAllocator()) syntax::Leaf(Tokens.begin());
   syntax::FactoryImpl::setCanModify(Leaf);
   Leaf->assertInvariants();

 } // namespace
 
 syntax::Tree *clang::syntax::createTree(
     syntax::Arena &A,
     std::vector<std::pair<syntax::Node *, syntax::NodeRole>> Children,
     syntax::NodeKind K) {
   auto *T = allocateTree(A, K);
   FactoryImpl::setCanModify(T);
-  for (auto ChildIt = Children.rbegin(); ChildIt != Children.rend();
-       std::advance(ChildIt, 1))
+  for (auto ChildIt = Children.rbegin(); ChildIt != Children.rend(); ++ChildIt)
     FactoryImpl::prependChildLowLevel(T, ChildIt->first, ChildIt->second);
 
   T->assertInvariants();
   return T;
 }
 
+namespace {
+bool canModifyAllDescendants(const syntax::Node *N) {
+  if (const auto *L = dyn_cast<syntax::Leaf>(N))
+    return L->canModify();
+
+  const auto *T = cast<syntax::Tree>(N);
+
+  if (!T->canModify())
+    return false;
+  for (const auto *Child = T->getFirstChild(); Child;
+       Child = Child->getNextSibling())
+    if (!canModifyAllDescendants(Child))
+      return false;
+
+  return true;
+}
+
+syntax::Node *deepCopyImpl(syntax::Arena &A, const syntax::Node *N) {
+  if (const auto *L = dyn_cast<syntax::Leaf>(N))
+    return createLeaf(A, L->getToken()->kind(),
+                      L->getToken()->text(A.getSourceManager()));
+
+  const auto *T = cast<syntax::Tree>(N);
+  std::vector<std::pair<syntax::Node *, syntax::NodeRole>> Children;
+  for (const auto *Child = T->getFirstChild(); Child;
+       Child = Child->getNextSibling())
+    Children.push_back({deepCopyImpl(A, Child), Child->getRole()});
+
+  return createTree(A, Children, N->getKind());
+}
+} // namespace
+
+syntax::Node *clang::syntax::deepCopy(syntax::Arena &A, const Node *N) {
+  if (!canModifyAllDescendants(N))
+    return nullptr;
+
+  return deepCopyImpl(A, N);
+}
+
 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, DeepCopy_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, DeepCopy_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, DeepCopy_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, DeepCopy_Macro) {
+  auto *OriginalTree = buildTree(R"cpp(
+#define HALF_IF if (1+
+#define HALF_IF_2 1) {}
+void test() {
+  HALF_IF HALF_IF_2 else {}
+})cpp",
+                                 GetParam());
+
+  auto *Copy = deepCopy(*Arena, OriginalTree);
+  EXPECT_TRUE(Copy == nullptr);
+}
+
 TEST_P(SynthesisTest, Statement_EmptyStatement) {
   buildTree("", GetParam());
 
   auto *S = createEmptyStatement(*Arena);
   EXPECT_TRUE(treeDumpEqual(S, R"txt(
 EmptyStatement Detached synthesized
 `-';' synthesized
   )txt"));
 }
 } // namespace