Ast Merging

Experimenting with merging ASTs to preserve the object IDs of the nodes which might help with far more efficient caching techniques.
dantleech · Dec 6, 2025 · Dec 7, 2025 · Dec 7, 2025 · Dec 7, 2025 · Dec 7, 2025
commit bc42d7682d015fd45b22d322bf2afcf86e44a2cc
diff --git a/lib/TolerantAstDiff/AstDiff.php b/lib/TolerantAstDiff/AstDiff.php
@@ -0,0 +1,219 @@
+<?php
+
+namespace Phpactor\TolerantAstDiff;
+
+use Microsoft\PhpParser\Node;
+use Microsoft\PhpParser\Node\SourceFileNode;
+use Microsoft\PhpParser\Token;
+use Phpactor\TextDocument\TextEdit;
+use Phpactor\TextDocument\TextEdits;
+use ReflectionClass;
+use ReflectionProperty;
+use RuntimeException;
+use function Amp\Promise\wait;
+
+final class AstDiff
+{
+    private SourceFileNode $fileSource1;
+    private SourceFileNode $fileSource2;
+
+    public function merge(Node $node1, Node $node2): void
+    {
+        $this->fileSource1 = $node1->getRoot();
+        $this->fileSource2 = $node2->getRoot();
+
+        $this->doMerge($node1, $node2);
+    }
+
+    private function doMerge(Node $node1, Node $node2): void
+    {
+        if ($node1::class !== $node2::class) {
+            throw new RuntimeException(sprintf(
+                'Can only compare nodes of the same type, got: %s vs %s',
+                $node1::class,
+                $node2::class
+            ));
+        }
+
+
+        if ($this->isSame($node1, $node2)) {
+            return;
+        }
+
+        $this->mapNode($node1, $node2);
+
+        $node1ChildNames = $node1->getChildNames();
+        $node2ChildNames = $node2->getChildNames();
+
+        foreach ($node1ChildNames as $childName) {
+
+            $node1Prop = $node1->$childName;
+            $node2Prop = $node2->$childName;
+
+            if (is_array($node1Prop)) {
+                assert(is_array($node2Prop));
+                $offset = -1;
+                foreach (array_keys($node1Prop) as $offset) {
+                    $node1Child = $node1Prop[$offset];
+                    $node2Child = $node2Prop[$offset] ?? null;
+
+                    if ($node2Child === null) {
+                        $this->removeChildFrom($node1, $childName, $offset);
+                        break;
+                    }
+
+                    if ($node1Child instanceof Token) {
+                        continue;
+                    }
+
+                    if (!$node1Child instanceof Node || !$node2Child instanceof Node) {
+                        // should never happen
+                        continue;
+                    }
+
+                    if ($node1Child::class !== $node2Child::class) {
+                        $node1->$childName[$offset] = $node2Child;
+                        $this->applyEdit($node1, TextEdit::create(
+                            $node1Child->getFullStartPosition(),
+                            $node1Child->getFullWidth(),
+                            $node2Child->getFullText(),
+                        ));
+                        continue;
+                    }
+
+                    $this->doMerge($node1Child, $node2Child);
+                }
+
+                $this->appendChildren($node1, $childName, array_slice($node2Prop, ++$offset));
+                continue;
+            }
+
+            if ($node1Prop instanceof Node) {
+                $this->doMerge($node1Prop, $node2Prop);
+            }
+        }
+
+        return;
+    }
+
+    /**
+     * Compare the inner node content
+     */
+    private static function isSame(Node $node1, Node $node2): bool
+    {
+        return $node1->getFullText() === $node2->getFullText();
+    }
+
+    private function removeChildFrom(Node $parent, string $childName, int $offset): void
+    {
+        /** @var list<Node> */
+        $keepNodes = $parent->$childName;
+        $removedNodes = array_slice($keepNodes, $offset);
+
+        if (count($removedNodes) === 0) {
+            return;
+        }
+
+        $firstRemovedNode = $removedNodes[0];
+        $keepNodes = array_slice($keepNodes, 0, $offset);
+
+        $parent->$childName = $keepNodes;
+
+        $removeLength = array_sum(array_map(fn (Node|Token $node) => $node->getFullWidth(), $removedNodes));
+        $this->applyEdit(
+            $parent,
+            TextEdit::create($firstRemovedNode->getFullStartPosition(), $removeLength, '')
+        );
+    }
+
+    /**
+     * @param list<Node> $newNodes
+     */
+    private function appendChildren(Node $parent, string $childName, array $newNodes): void
+    {
+        if (empty($newNodes)) {
+            return;
+        }
+        $firstNewNode = $newNodes[array_key_first($newNodes)];
+
+        /** @var Node[] */
+        $existingNodes = $parent->$childName;
+        $lastExistingNode = $newNodes[array_key_last($newNodes)];
+        $parent->$childName = array_merge($existingNodes, $newNodes);
+
+        $addLength = array_sum(array_map(
+            fn (Node|Token $node) => $node->getFullWidth(),
+            $newNodes
+        ));
+
+        $addContent = substr(
+            $this->fileSource2->getFileContents(),
+            $firstNewNode->getFullStartPosition(),
+            $addLength,
+        );
+
+        $this->applyEdit(
+            $parent,
+            TextEdit::create(
+                $lastExistingNode->getFullStartPosition(),
+                0,
+                $addContent,
+            ),
+        );
+
+    }
+
+    private function applyEdit(Node $node, TextEdit $edit): void
+    {
+        $source = $this->fileSource1;
+        $distance = strlen($edit->replacement()) - $edit->length();
+
+        foreach ($source->getDescendantTokens() as $token) {
+            if ($token->getFullStartPosition() <= $edit->start()->toInt()) {
+                continue;
+            }
+            $token->start += $distance;
+            $token->fullStart += $distance;
+        }
+
+        $source->fileContents = TextEdits::one($edit)->apply($source->getFileContents());
+    }
+
+    private function mapNode(Node $node1, Node $node2): void
+    {
+        if ($node2::class !== $node1::class) {
+            throw new \RuntimeException(sprintf(
+                'Can only map nodes of the same type to eachother, got %s and %s',
+                $node2::class, $node1::class
+            ));
+        }
+
+        $lastPosition = $node1->getFullStartPosition();
+        foreach ($node1->getChildNames() as $childName) {
+            $member1 = $node1->$childName;
+            $member2 = $node2->$childName;
+
+            if (is_array($member1)) {
+                //foreach ($member1 as $member) {
+                //    $lastPosition = $member->getFullStartPosition();
+                //}
+                continue;
+            }
+
+            if ($member1 !== null) {
+                $lastPosition = $member1->getFullStartPosition();
+            }
+
+            if ($member2 instanceof Token || $member2 === null) {
+                $node1->$childName = $member2;
+
+                $this->applyEdit($node1, TextEdit::create(
+                    $lastPosition,
+                    $member1?->getFullWidth() ?? 0,
+                    $member2?->getFullText($this->fileSource2->getFileContents()) ?? '',
+                ));
+                continue;
+            }
+        }
+    }
+}
diff --git a/lib/TolerantAstDiff/Tests/Unit/AstDiffTest.php b/lib/TolerantAstDiff/Tests/Unit/AstDiffTest.php
@@ -0,0 +1,110 @@
+<?php
+
+namespace Phpactor\TolerantAstDiff\Tests\Unit;
+
+use Generator;
+use Microsoft\PhpParser\Parser;
+use PHPUnit\Framework\Attributes\DataProvider;
+use Phpactor\ConfigLoader\Tests\TestCase;
+use Phpactor\TolerantAstDiff\AstDiff;
+use Phpactor\WorseReflection\Core\Util\NodeUtil;
+
+final class AstDiffTest extends TestCase
+{
+    #[DataProvider('provideDiffTree')]
+    public function testDiffTree(string $source1, string $source2): void
+    {
+        $parser = new Parser();
+        $ast1 = $parser->parseSourceFile($source1);
+        $ast2 = $parser->parseSourceFile($source2);
+
+        $diff = (new AstDiff());
+        $diff->merge($ast1, $ast2);
+
+        self::assertEquals($ast2->getText(), $ast1->getText());
+    }
+    /**
+     * @return Generator<string,array{string,string}>
+     */
+    public static function provideDiffTree(): Generator
+    {
+        yield 'same' => [
+            '<?php function hello(): string { echo "hello"; }',
+            '<?php function hello(): string { echo "hello"; }',
+        ];
+
+        yield 'remove 1' => [
+            '<?php function hello(): string {echo "hello";}',
+            '<?php function hello(): string {}',
+        ];
+        yield 'remove 2' => [
+            <<<'PHP'
+                <?php
+                class Foo
+                {
+                    public function bar()
+                    {
+                        echo 'foobar';
+                    }
+
+                    public function foo()
+                    {
+                    }
+                }
+                PHP,
+            <<<'PHP'
+                <?php
+                class Foo
+                {
+                    public function bar()
+                    {
+                        echo 'foobar';
+                    }
+                }
+                PHP
+        ];
+
+        yield 'add 1 node' => [
+            '<?php function hello(): string {echo "hello";}',
+            '<?php function hello(): string {echo "hello";echo 2;}',
+        ];
+
+        yield 'change 1 node' => [
+            '<?php function hello(): string {echo "hello";echo 2;}',
+            '<?php function hello(): string {echo "hello";echo 3;}',
+        ];
+
+        yield 'update array' => [
+            '<?php function hello(): string { $foo = [1, 2, 3]; }',
+            '<?php function hello(): string { $foo = [5, 10]; }',
+        ];
+
+        yield 'replace node' => [
+            '<?php function hello(): string {echo "hello";echo 2;}',
+            '<?php class Bar {}',
+        ];
+
+        yield 'artbitrary change' => [
+            <<<'PHP'
+                <?php
+                class Foo
+                {
+                    public function bar()
+                    {
+                        echo 'foobar';
+                    }
+                }
+                PHP,
+            <<<'PHP'
+                <?php
+                class Foo
+                {
+                    public function baz()
+                    {
+                        echo 'baz';
+                    }
+                }
+                PHP
+        ];
+    }
+}
diff --git a/lib/WorseReflection/Core/Util/NodeUtil.php b/lib/WorseReflection/Core/Util/NodeUtil.php
@@ -51,7 +51,7 @@
        if (count($nameParts) === 0) {
            return null;
        }
        $base = $nameParts[0]->getText($content);

        if (isset($importTable[$base])) {
            $resolvedName = $importTable[$base];
@@ -181,24 +181,33 @@
     /**
      * For debugging: pretty print the AST
      */
-    public static function dump(Node $node, int $level = 0): string
+    public static function dump(array|Node $nodes, int $level = 0): string
     {
-        $out = [
-            sprintf(
-                '%s %d:%d - %s',
-                str_repeat('  ', $level) . $node->getNodeKindName(),
-                $node->getStartPosition(),
-                $node->getEndPosition(),
-                str_replace("\n", '\\n', $node->getText()),
-            )
-        ];
-
-        $level++;
-        foreach ($node->getChildNodes() as $child) {
-            $out[] = self::dump($child, $level);
-        }
-
-        return implode("\n", $out);
+        if (!is_array($nodes)) {
+            $nodes = [$nodes];
+        }
+
+        $dumps = [];
+        foreach ($nodes as $node) {
+            $out = [
+                sprintf(
+                    '%s %d:%d - %s',
+                    str_repeat('  ', $level) . $node->getNodeKindName(),
+                    $node->getStartPosition(),
+                    $node->getEndPosition(),
+                    str_replace("\n", '\\n', $node->getText()),
+                )
+            ];
+
+            $level++;
+            foreach ($node->getChildNodes() as $child) {
+                $out[] = self::dump($child, $level);
+            }
+
+            $dumps[]= implode("\n", $out);
+        }
+
+        return implode("\n", $dumps);
     }
 
     /**

diff --git a/phpunit.xml.dist b/phpunit.xml.dist
@@ -4,7 +4,7 @@
     xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
     colors="true" 
     bootstrap="vendor/autoload.php" 
-    displayDetailsOnPhpunitDeprecations="false"
+    displayDetailsOnPhpunitDeprecations="true"
     displayDetailsOnTestsThatTriggerDeprecations="true"
 
     xsi:noNamespaceSchemaLocation="vendor/phpunit/phpunit/phpunit.xsd"