Semantic Diff for SQL
Motivation
Software is constantly changing and evolving, and identifying what has changed and reviewing those changes is an integral part of the development process. SQL code is no exception to this.
Text-based diff tools such as git diff
, when applied to a code base, have certain limitations. First, they can only detect insertions and deletions, not movements or updates of individual pieces of code. Second, such tools can only detect changes between lines of text, which is too coarse for something as granular and detailed as source code. Additionally, the outcome of such a diff is dependent on the underlying code formatting, and yields different results if the formatting should change.
Consider the following diff generated by Git:
Semantically the query hasn’t changed. The two arguments b
and c
have been swapped (moved), posing no impact on the output of the query. Yet Git replaced the whole affected expression alongside a bulk of unrelated elements.
The alternative to text-based diffing is to compare Abstract Syntax Trees (AST) instead. The main advantage of ASTs are that they are a direct product of code parsing, which represents the underlying code structure at any desired level of granularity. Comparing ASTs may yield extremely precise diffs; changes such as code movements and updates can also be detected. Even more importantly, this approach facilitates additional use cases beyond eyeballing two versions of source code side by side.
The use cases I had in mind for SQL when I decided to embark on this journey of semantic diffing were the following:
- Query similarity score. Identifying which parts the two queries have in common to automatically suggest opportunities for consolidation, creation of intermediate/staging tables, and so on.
- Differentiating between cosmetic / structural changes and functional ones. For example when a nested query is refactored into a common table expression (CTE), this kind of change doesn’t have any functional impact on either a query or its outcome.
- Automatic suggestions about the need to retroactively backfill data. This is especially important for pipelines that populate very large tables for which restatement is a runtime-intensive procedure. The ability to discern between simple code movements and actual modifications can help assess the impact of a change and make suggestions accordingly.
The implementation discussed in this post is now a part of the SQLGlot library. You can find a complete source code in the diff.py module. The choice of SQLglot was an obvious one due to its simple but powerful API, lack of external dependencies and, more importantly, extensive list of supported SQL dialects.
The Search for a Solution
When it comes to any diffing tool (not just a semantic one), the primary challenge is to match as many elements of compared entities as possible. Once such a set of matching elements is available, deriving a sequence of changes becomes an easy task.
If our elements have unique identifiers associated with them (for example, an element’s ID in DOM), the matching problem is trivial. However, the SQL syntax trees that we are comparing have neither unique keys nor object identifiers that can be used for the purposes of matching. So, how do we suppose to find pairs of nodes that are related?
To better illustrate the problem, consider comparing the following SQL expressions: SELECT a + b + c, d, e
and SELECT a - b + c, e, f
. Matching individual nodes from respective syntax trees can be visualized as follows:
Figure 1: Example of node matching for two SQL expression trees.
By looking at the figure of node matching for two SQL expression trees above, we conclude that the following changes should be captured by our solution:
- Inserted nodes:
Sub
andf
. These are the nodes from the target AST which do not have a matching node in the source AST. - Removed nodes:
Add
andd
. These are the nodes from the source AST which do not have a counterpart in the target AST. - Remaining nodes must be identified as unchanged.
It should be clear at this point that if we manage to match nodes in the source tree with their counterparts in the target tree, then computing the diff becomes a trivial matter.
Naïve Brute-Force
The naïve solution would be to try all different permutations of node pair combinations, and see which set of pairs performs the best based on some type of heuristics. The runtime cost of such a solution quickly reaches the escape velocity; if both trees had only 10 nodes each, the number of such sets would approximately be 10! ^ 2 = 3.6M ^ 2 ~= 13 * 10^12. This is a very bad case of factorial complexity (to be precise, it’s actually much worse - O(n! ^ 2) - but I couldn’t come up with a name for it), so there is little need to explore this approach any further.
Myers Algorithm
After the naïve approach was proven to be infeasible, the next question I asked myself was “how does git diff work?”. This question led me to discover the Myers diff algorithm [1]. This algorithm has been designed to compare sequences of strings. At its core, it’s looking for the shortest path on a graph of possible edits that transform the first sequence into the second one, while heavily rewarding those paths that lead to longest subsequences of unchanged elements. There’s a lot of material out there describing this algorithm in greater detail. I found James Coglan’s series of blog posts to be the most comprehensive.
Therefore, I had this “brilliant” (actually not) idea to transform trees into sequences by traversing them in topological order, and then applying the Myers algorithm on resulting sequences while using a custom heuristics when checking the equality of two nodes. Unsurprisingly, comparing sequences of strings is quite different from comparing hierarchical tree structures, and by flattening trees into sequences, we lose a lot of relevant context. This resulted in a terrible performance of this algorithm on ASTs. It often matched completely unrelated nodes, even when the two trees were mostly the same, and produced extremely inaccurate lists of changes overall. After playing around with it a little and tweaking my equality heuristics to improve accuracy, I ultimately scrapped the whole implementation and went back to the drawing board.
Change Distiller
The algorithm I settled on at the end was Change Distiller, created by Fluri et al. [2], which in turn is an improvement over the core idea described by Chawathe et al. [3].
The algorithm consists of two high-level steps:
- Finding appropriate matchings between pairs of nodes that are part of compared ASTs. Identifying what is meant by “appropriate” matching is also a part of this step.
- Generating the so-called “edit script” from the matching set built in the 1st step. The edit script is a sequence of edit operations (for example, insert, remove, update, etc.) on individual tree nodes, such that when applied as transformations on the source AST, it eventually becomes the target AST. In general, the shorter the sequence, the better. The length of the edit script can be used to compare the performance of different algorithms, though this is not the only metric that matters.
The rest of this section is dedicated to the Python implementation of the steps above using the AST implementation provided by the SQLGlot library.
Building the Matching Set
Matching Leaves
We begin composing the matching set by matching the leaf nodes. Leaf nodes are the nodes that do not have any children nodes (such as literals, identifiers, etc.). In order to match them, we gather all the leaf nodes from the source tree and generate a cartesian product with all the leaves from the target tree, while comparing pairs created this way and assigning them a similarity score. During this stage, we also exclude pairs that don’t pass basic matching criteria. Then, we pick pairs that scored the highest while making sure that each node is matched no more than once.
Using the example provided at the beginning of the post, the process of building an initial set of candidate matchings can be seen on Figure 2.
Figure 2: Building a set of candidate matchings between leaf nodes. The third item in each triplet represents a similarity score between two nodes.
First, let’s analyze the similarity score. Then, we’ll discuss matching criteria.
The similarity score proposed by Fluri et al. [2] is a dice coefficient applied to bigrams of respective node values. A bigram is a sequence of two adjacent elements from a string computed in a sliding window fashion:
def bigram(string):
count = max(0, len(string) - 1)
return [string[i : i + 2] for i in range(count)]
For reasons that will become clear shortly, we actually need to compute bigram histograms rather than just sequences:
from collections import defaultdict
def bigram_histo(string):
count = max(0, len(string) - 1)
bigram_histo = defaultdict(int)
for i in range(count):
bigram_histo[string[i : i + 2]] += 1
return bigram_histo
The dice coefficient formula looks like following:
Where X is a bigram of the source node and Y is a bigram of the second one. What this essentially does is count the number of bigram elements the two nodes have in common, multiply it by 2, and then divide by the total number of elements in both bigrams. This is where bigram histograms come in handy:
def dice_coefficient(source, target):
source_histo = bigram_histo(source.sql())
target_histo = bigram_histo(target.sql())
total_grams = (
sum(source_histo.values()) + sum(target_histo.values())
)
if not total_grams:
return 1.0 if source == target else 0.0
overlap_len = 0
overlapping_grams = set(source_histo) & set(target_histo)
for g in overlapping_grams:
overlap_len += min(source_histo[g], target_histo[g])
return 2 * overlap_len / total_grams
To compute a bigram given a tree node, we first transform the node into its canonical SQL representation,so that the Literal(123)
node becomes just “123” and the Identifier(“a”)
node becomes just “a”. We also handle a scenario when strings are too short to derive bigrams. In this case, we fallback to checking the two nodes for equality.
Now when we know how to compute the similarity score, we can take care of the matching criteria for leaf nodes. In the original paper [2], the matching criteria is formalized as follows:
The two nodes are matched if two conditions are met:
- The node labels match (in our case labels are just node types).
- The similarity score for node values is greater than or equal to some threshold “f”. The authors of the paper recommend setting the value of “f” to 0.6.
With building blocks in place, we can now build a matching set for leaf nodes. First, we generate a list of candidates for matching:
from heapq import heappush, heappop
candidate_matchings = []
source_leaves = _get_leaves(self._source)
target_leaves = _get_leaves(self._target)
for source_leaf in source_leaves:
for target_leaf in target_leaves:
if _is_same_type(source_leaf, target_leaf):
similarity_score = dice_coefficient(
source_leaf, target_leaf
)
if similarity_score >= 0.6:
heappush(
candidate_matchings,
(
-similarity_score,
len(candidate_matchings),
source_leaf,
target_leaf,
),
)
In the implementation above, we push each matching pair onto the heap to automatically maintain the correct order based on the assigned similarity score.
Finally, we build the initial matching set by picking leaf pairs with the highest score:
matching_set = set()
while candidate_matchings:
_, _, source_leaf, target_leaf = heappop(candidate_matchings)
if (
source_leaf in unmatched_source_nodes
and target_leaf in unmatched_target_nodes
):
matching_set.add((source_leaf, target_leaf))
unmatched_source_nodes.remove(source_leaf)
unmatched_target_nodes.remove(target_leaf)
To finalize the matching set, we should now proceed with matching inner nodes.
Matching Inner Nodes
Matching inner nodes is quite similar to matching leaf nodes, with the following two distinctions:
- Rather than ranking a set of possible candidates, we pick the first node pair that passes the matching criteria.
- The matching criteria itself has been extended to account for the number of leaf nodes the pair of inner nodes have in common.
Figure 3: Matching inner nodes based on their type as well as how many of their leaf nodes have been previously matched.
Let’s start with the matching criteria. The criteria is formalized as follows:
Alongside already familiar similarity score and node type criteria, there is a new one in the middle: the ratio of leaf nodes that the two nodes have in common must exceed some threshold “t”. The recommended value for “t” is also 0.6. Counting the number of common leaf nodes is pretty straightforward, since we already have the complete matching set for leaves. All we need to do is count how many matching pairs do leaf nodes from the two compared inner nodes form.
There are two additional heuristics associated with this matching criteria:
- Inner node similarity weighting: if the similarity score between the node values doesn’t pass the threshold “f” but the ratio of common leaf nodes (“t”) is greater than or equal to 0.8, then the matching is considered successful.
- The threshold “t” is reduced to 0.4 for inner nodes with the number of leaf nodes equal to 4 or less, in order to decrease the false negative rate for small subtrees.
We now only have to iterate through the remaining unmatched nodes and form matching pairs based on the outlined criteria:
leaves_matching_set = matching_set.copy()
for source_node in unmatched_source_nodes.copy():
for target_node in unmatched_target_nodes:
if _is_same_type(source_node, target_node):
source_leaves = set(_get_leaves(source_node))
target_leaves = set(_get_leaves(target_node))
max_leaves_num = max(len(source_leaves), len(target_leaves))
if max_leaves_num:
common_leaves_num = sum(
1 if s in source_leaves and t in target_leaves else 0
for s, t in leaves_matching_set
)
leaf_similarity_score = common_leaves_num / max_leaves_num
else:
leaf_similarity_score = 0.0
adjusted_t = (
0.6
if min(len(source_leaves), len(target_leaves)) > 4
else 0.4
)
if leaf_similarity_score >= 0.8 or (
leaf_similarity_score >= adjusted_t
and dice_coefficient(source_node, target_node) >= 0.6
):
matching_set.add((source_node, target_node))
unmatched_source_nodes.remove(source_node)
unmatched_target_nodes.remove(target_node)
break
After the matching set is formed, we can proceed with generation of the edit script, which will be the algorithm’s output.
Generating the Edit Script
At this point, we should have the following 3 sets at our disposal:
- The set of matched node pairs.
- The set of remaining unmatched nodes from the source tree.
- The set of remaining unmatched nodes from the target tree.
We can derive 3 kinds of edits from the matching set: either the node’s value was updated (Update), the node was moved to a different position within the tree (Move), or the node remained unchanged (Keep). Note that the Move case is not mutually exclusive with the other two. The node could have been updated or could have remained the same while at the same time its position within its parent node or the parent node itself could have changed. All unmatched nodes from the source tree are the ones that were removed (Remove), while unmatched nodes from the target tree are the ones that were inserted (Insert).
The latter two cases are pretty straightforward to implement:
edit_script = []
for removed_node in unmatched_source_nodes:
edit_script.append(Remove(removed_node))
for inserted_node in unmatched_target_nodes:
edit_script.append(Insert(inserted_node))
Traversing the matching set requires a little more thought:
for source_node, target_node in matching_set:
if (
not isinstance(source_node, LEAF_EXPRESSION_TYPES)
or source_node == target_node
):
move_edits = generate_move_edits(
source_node, target_node, matching_set
)
edit_script.extend(move_edits)
edit_script.append(Keep(source_node, target_node))
else:
edit_script.append(Update(source_node, target_node))
If a matching pair represents a pair of leaf nodes, we check if they are the same to decide whether an update took place. For inner node pairs, we also need to compare the positions of their respective children to detect node movements. Chawathe et al. [3] suggest applying the longest common subsequence (LCS) algorithm which, no surprise here, was described by Myers himself [1]. There is a small catch, however: instead of checking the equality of two children nodes, we need to check whether the two nodes form a pair that is a part of our matching set.
Now with this knowledge, the implementation becomes straightforward:
def generate_move_edits(source, target, matching_set):
source_children = _get_child_nodes(source)
target_children = _get_child_nodes(target)
lcs = set(
_longest_common_subsequence(
source_children,
target_children,
lambda l, r: (l, r) in matching_set
)
)
move_edits = []
for node in source_children:
if node not in lcs and node not in unmatched_source_nodes:
move_edits.append(Move(node))
return move_edits
I left out the implementation of the LCS algorithm itself here, but there are plenty of implementation choices out there that can be easily looked up.
Output
The implemented algorithm produces the output that resembles the following:
>>> from sqlglot import parse_one, diff
>>> diff(parse_one("SELECT a + b + c, d, e"), parse_one("SELECT a - b + c, e, f"))
Remove(Add)
Remove(Column(d))
Remove(Identifier(d))
Insert(Sub)
Insert(Column(f))
Insert(Identifier(f))
Keep(Select, Select)
Keep(Add, Add)
Keep(Column(a), Column(a))
Keep(Identifier(a), Identifier(a))
Keep(Column(b), Column(b))
Keep(Identifier(b), Identifier(b))
Keep(Column(c), Column(c))
Keep(Identifier(c), Identifier(c))
Keep(Column(e), Column(e))
Keep(Identifier(e), Identifier(e))
Note that the output above is abbreviated. The string representation of actual AST nodes is significantly more verbose.
The implementation works especially well when coupled with the SQLGlot’s query optimizer which can be used to produce canonical representations of compared queries:
>>> schema={"t": {"a": "INT", "b": "INT", "c": "INT", "d": "INT"}}
>>> source = """
... SELECT 1 + 1 + a
... FROM t
... WHERE b = 1 OR (c = 2 AND d = 3)
... """
>>> target = """
... SELECT 2 + a
... FROM t
... WHERE (b = 1 OR c = 2) AND (b = 1 OR d = 3)
... """
>>> optimized_source = optimize(parse_one(source), schema=schema)
>>> optimized_target = optimize(parse_one(target), schema=schema)
>>> edit_script = diff(optimized_source, optimized_target)
>>> sum(0 if isinstance(e, Keep) else 1 for e in edit_script)
0
Optimizations
The worst case runtime complexity of this algorithm is not exactly stellar: O(n^2 * log n^2). This is because of the leaf matching process, which involves ranking a cartesian product between all leaf nodes of compared trees. Unsurprisingly, the algorithm takes a considerable time to finish for bigger queries.
There are still a few basic things we can do in our implementation to help improve performance:
- Refer to individual node objects using their identifiers (Python’s id()) instead of direct references in sets. This helps avoid costly recursive hash calculations and equality checks.
- Cache bigram histograms to avoid computing them more than once for the same node.
- Compute the canonical SQL string representation for each tree once while caching string representations of all inner nodes. This prevents redundant tree traversals when bigrams are computed.
At the time of writing only the first two optimizations have been implemented, so there is an opportunity to contribute for anyone who’s interested.
Alternative Solutions
This section is dedicated to solutions that I’ve investigated, but haven’t tried.
First, this section wouldn’t be complete without Tristan Hume’s blog post. Tristan’s solution has a lot in common with the Myers algorithm plus heuristics that is much more clever than what I came up with. The implementation relies on a combination of dynamic programming and A* search algorithm to explore the space of possible matchings and pick the best ones. It seemed to have worked well for Tistan’s specific use case, but after my negative experience with the Myers algorithm, I decided to try something different.
Another notable approach is the Gumtree algorithm by Falleri et al. [4]. I discovered this paper after I’d already implemented the algorithm that is the main focus of this post. In sections 5.2 and 5.3 of their paper, the authors compare the two algorithms side by side and claim that Gumtree is significantly better in terms of both runtime performance and accuracy when evaluated on 12 792 pairs of Java source files. This doesn’t surprise me, as the algorithm takes the height of subtrees into account. In my tests, I definitely saw scenarios in which this context would have helped. On top of that, the authors promise O(n^2) runtime complexity in the worst case which, given the Change Distiller's O(n^2 * log n^2), looks particularly tempting. I hope to try this algorithm out at some point, and there is a good chance you see me writing about it in my future posts.
Conclusion
The Change Distiller algorithm yielded quite satisfactory results in most of my tests. The scenarios in which it fell short mostly concerned identical (or very similar) subtrees located in different parts of the AST. In those cases, node mismatches were frequent and, as a result, edit scripts were somewhat suboptimal.
Additionally, the runtime performance of the algorithm leaves a lot to be desired. On trees with 1000 leaf nodes each, the algorithm takes a little under 2 seconds to complete. My implementation still has room for improvement, but this should give you a rough idea of what to expect. It appears that the Gumtree algorithm [4] can help address both of these points. I hope to find bandwidth to work on it soon and then compare the two algorithms side-by-side to find out which one performs better on SQL specifically. In the meantime, Change Distiller definitely gets the job done, and I can now proceed with applying it to some of the use cases I mentioned at the beginning of this post.
I’m also curious to learn whether other folks in the industry faced a similar problem, and how they approached it. If you did something similar, I’m interested to hear about your experience.
References
[1] Eugene W. Myers. An O(ND) Difference Algorithm and Its Variations. Algorithmica 1(2): 251-266 (1986)
[2] B. Fluri, M. Wursch, M. Pinzger, and H. Gall. Change Distilling: Tree differencing for fine-grained source code change extraction. IEEE Trans. Software Eng., 33(11):725–743, 2007.
[3] S.S. Chawathe, A. Rajaraman, H. Garcia-Molina, and J. Widom. Change Detection in Hierarchically Structured Information. Proc. ACM Sigmod Int’l Conf. Management of Data, pp. 493-504, June 1996
[4] Jean-Rémy Falleri, Floréal Morandat, Xavier Blanc, Matias Martinez, Martin Monperrus. Fine-grained and Accurate Source Code Differencing. Proceedings of the International Conference on Automated Software Engineering, 2014, Västeras, Sweden. pp.313-324, 10.1145/2642937.2642982. hal-01054552
1""" 2.. include:: ../posts/sql_diff.md 3 4---- 5""" 6 7from __future__ import annotations 8 9import typing as t 10from collections import defaultdict 11from dataclasses import dataclass 12from heapq import heappop, heappush 13 14from sqlglot import Dialect, expressions as exp 15from sqlglot.helper import seq_get 16 17if t.TYPE_CHECKING: 18 from sqlglot.dialects.dialect import DialectType 19 20 21@dataclass(frozen=True) 22class Insert: 23 """Indicates that a new node has been inserted""" 24 25 expression: exp.Expression 26 27 28@dataclass(frozen=True) 29class Remove: 30 """Indicates that an existing node has been removed""" 31 32 expression: exp.Expression 33 34 35@dataclass(frozen=True) 36class Move: 37 """Indicates that an existing node's position within the tree has changed""" 38 39 source: exp.Expression 40 target: exp.Expression 41 42 43@dataclass(frozen=True) 44class Update: 45 """Indicates that an existing node has been updated""" 46 47 source: exp.Expression 48 target: exp.Expression 49 50 51@dataclass(frozen=True) 52class Keep: 53 """Indicates that an existing node hasn't been changed""" 54 55 source: exp.Expression 56 target: exp.Expression 57 58 59if t.TYPE_CHECKING: 60 from sqlglot._typing import T 61 62 Edit = t.Union[Insert, Remove, Move, Update, Keep] 63 64 65def diff( 66 source: exp.Expression, 67 target: exp.Expression, 68 matchings: t.List[t.Tuple[exp.Expression, exp.Expression]] | None = None, 69 delta_only: bool = False, 70 copy: bool = True, 71 **kwargs: t.Any, 72) -> t.List[Edit]: 73 """ 74 Returns the list of changes between the source and the target expressions. 75 76 Examples: 77 >>> diff(parse_one("a + b"), parse_one("a + c")) 78 [ 79 Remove(expression=(COLUMN this: (IDENTIFIER this: b, quoted: False))), 80 Insert(expression=(COLUMN this: (IDENTIFIER this: c, quoted: False))), 81 Keep( 82 source=(ADD this: ...), 83 target=(ADD this: ...) 84 ), 85 Keep( 86 source=(COLUMN this: (IDENTIFIER this: a, quoted: False)), 87 target=(COLUMN this: (IDENTIFIER this: a, quoted: False)) 88 ), 89 ] 90 91 Args: 92 source: the source expression. 93 target: the target expression against which the diff should be calculated. 94 matchings: the list of pre-matched node pairs which is used to help the algorithm's 95 heuristics produce better results for subtrees that are known by a caller to be matching. 96 Note: expression references in this list must refer to the same node objects that are 97 referenced in the source / target trees. 98 delta_only: excludes all `Keep` nodes from the diff. 99 copy: whether to copy the input expressions. 100 Note: if this is set to false, the caller must ensure that there are no shared references 101 in the two trees, otherwise the diffing algorithm may produce unexpected behavior. 102 kwargs: additional arguments to pass to the ChangeDistiller instance. 103 104 Returns: 105 the list of Insert, Remove, Move, Update and Keep objects for each node in the source and the 106 target expression trees. This list represents a sequence of steps needed to transform the source 107 expression tree into the target one. 108 """ 109 matchings = matchings or [] 110 matching_ids = {id(n) for pair in matchings for n in pair} 111 112 def compute_node_mappings( 113 original: exp.Expression, copy: exp.Expression 114 ) -> t.Dict[int, exp.Expression]: 115 return { 116 id(old_node): new_node 117 for old_node, new_node in zip(original.walk(), copy.walk()) 118 if id(old_node) in matching_ids 119 } 120 121 source_copy = source.copy() if copy else source 122 target_copy = target.copy() if copy else target 123 124 node_mappings = { 125 **compute_node_mappings(source, source_copy), 126 **compute_node_mappings(target, target_copy), 127 } 128 matchings_copy = [(node_mappings[id(s)], node_mappings[id(t)]) for s, t in matchings] 129 130 return ChangeDistiller(**kwargs).diff( 131 source_copy, 132 target_copy, 133 matchings=matchings_copy, 134 delta_only=delta_only, 135 ) 136 137 138# The expression types for which Update edits are allowed. 139UPDATABLE_EXPRESSION_TYPES = ( 140 exp.Alias, 141 exp.Boolean, 142 exp.Column, 143 exp.DataType, 144 exp.Lambda, 145 exp.Literal, 146 exp.Table, 147 exp.Window, 148) 149 150IGNORED_LEAF_EXPRESSION_TYPES = (exp.Identifier,) 151 152 153class ChangeDistiller: 154 """ 155 The implementation of the Change Distiller algorithm described by Beat Fluri and Martin Pinzger in 156 their paper https://ieeexplore.ieee.org/document/4339230, which in turn is based on the algorithm by 157 Chawathe et al. described in http://ilpubs.stanford.edu:8090/115/1/1995-46.pdf. 158 """ 159 160 def __init__(self, f: float = 0.6, t: float = 0.6, dialect: DialectType = None) -> None: 161 self.f = f 162 self.t = t 163 self._sql_generator = Dialect.get_or_raise(dialect).generator() 164 165 def diff( 166 self, 167 source: exp.Expression, 168 target: exp.Expression, 169 matchings: t.List[t.Tuple[exp.Expression, exp.Expression]] | None = None, 170 delta_only: bool = False, 171 ) -> t.List[Edit]: 172 matchings = matchings or [] 173 pre_matched_nodes = {id(s): id(t) for s, t in matchings} 174 if len({n for pair in pre_matched_nodes.items() for n in pair}) != 2 * len(matchings): 175 raise ValueError("Each node can be referenced at most once in the list of matchings") 176 177 self._source = source 178 self._target = target 179 self._source_index = { 180 id(n): n for n in self._source.bfs() if not isinstance(n, IGNORED_LEAF_EXPRESSION_TYPES) 181 } 182 self._target_index = { 183 id(n): n for n in self._target.bfs() if not isinstance(n, IGNORED_LEAF_EXPRESSION_TYPES) 184 } 185 self._unmatched_source_nodes = set(self._source_index) - set(pre_matched_nodes) 186 self._unmatched_target_nodes = set(self._target_index) - set(pre_matched_nodes.values()) 187 self._bigram_histo_cache: t.Dict[int, t.DefaultDict[str, int]] = {} 188 189 matching_set = self._compute_matching_set() | set(pre_matched_nodes.items()) 190 return self._generate_edit_script(dict(matching_set), delta_only) 191 192 def _generate_edit_script(self, matchings: t.Dict[int, int], delta_only: bool) -> t.List[Edit]: 193 edit_script: t.List[Edit] = [] 194 for removed_node_id in self._unmatched_source_nodes: 195 edit_script.append(Remove(self._source_index[removed_node_id])) 196 for inserted_node_id in self._unmatched_target_nodes: 197 edit_script.append(Insert(self._target_index[inserted_node_id])) 198 for kept_source_node_id, kept_target_node_id in matchings.items(): 199 source_node = self._source_index[kept_source_node_id] 200 target_node = self._target_index[kept_target_node_id] 201 202 if ( 203 not isinstance(source_node, UPDATABLE_EXPRESSION_TYPES) 204 or source_node == target_node 205 ): 206 edit_script.extend(self._generate_move_edits(source_node, target_node, matchings)) 207 208 source_non_expression_leaves = dict(_get_non_expression_leaves(source_node)) 209 target_non_expression_leaves = dict(_get_non_expression_leaves(target_node)) 210 211 if source_non_expression_leaves != target_non_expression_leaves: 212 edit_script.append(Update(source_node, target_node)) 213 elif not delta_only: 214 edit_script.append(Keep(source_node, target_node)) 215 else: 216 edit_script.append(Update(source_node, target_node)) 217 218 return edit_script 219 220 def _generate_move_edits( 221 self, source: exp.Expression, target: exp.Expression, matchings: t.Dict[int, int] 222 ) -> t.List[Move]: 223 source_args = [id(e) for e in _expression_only_args(source)] 224 target_args = [id(e) for e in _expression_only_args(target)] 225 226 args_lcs = set( 227 _lcs(source_args, target_args, lambda l, r: matchings.get(t.cast(int, l)) == r) 228 ) 229 230 move_edits = [] 231 for a in source_args: 232 if a not in args_lcs and a not in self._unmatched_source_nodes: 233 move_edits.append( 234 Move(source=self._source_index[a], target=self._target_index[matchings[a]]) 235 ) 236 237 return move_edits 238 239 def _compute_matching_set(self) -> t.Set[t.Tuple[int, int]]: 240 leaves_matching_set = self._compute_leaf_matching_set() 241 matching_set = leaves_matching_set.copy() 242 243 ordered_unmatched_source_nodes = { 244 id(n): None for n in self._source.bfs() if id(n) in self._unmatched_source_nodes 245 } 246 ordered_unmatched_target_nodes = { 247 id(n): None for n in self._target.bfs() if id(n) in self._unmatched_target_nodes 248 } 249 250 for source_node_id in ordered_unmatched_source_nodes: 251 for target_node_id in ordered_unmatched_target_nodes: 252 source_node = self._source_index[source_node_id] 253 target_node = self._target_index[target_node_id] 254 if _is_same_type(source_node, target_node): 255 source_leaf_ids = {id(l) for l in _get_expression_leaves(source_node)} 256 target_leaf_ids = {id(l) for l in _get_expression_leaves(target_node)} 257 258 max_leaves_num = max(len(source_leaf_ids), len(target_leaf_ids)) 259 if max_leaves_num: 260 common_leaves_num = sum( 261 1 if s in source_leaf_ids and t in target_leaf_ids else 0 262 for s, t in leaves_matching_set 263 ) 264 leaf_similarity_score = common_leaves_num / max_leaves_num 265 else: 266 leaf_similarity_score = 0.0 267 268 adjusted_t = ( 269 self.t if min(len(source_leaf_ids), len(target_leaf_ids)) > 4 else 0.4 270 ) 271 272 if leaf_similarity_score >= 0.8 or ( 273 leaf_similarity_score >= adjusted_t 274 and self._dice_coefficient(source_node, target_node) >= self.f 275 ): 276 matching_set.add((source_node_id, target_node_id)) 277 self._unmatched_source_nodes.remove(source_node_id) 278 self._unmatched_target_nodes.remove(target_node_id) 279 ordered_unmatched_target_nodes.pop(target_node_id, None) 280 break 281 282 return matching_set 283 284 def _compute_leaf_matching_set(self) -> t.Set[t.Tuple[int, int]]: 285 candidate_matchings: t.List[t.Tuple[float, int, int, exp.Expression, exp.Expression]] = [] 286 source_expression_leaves = list(_get_expression_leaves(self._source)) 287 target_expression_leaves = list(_get_expression_leaves(self._target)) 288 for source_leaf in source_expression_leaves: 289 for target_leaf in target_expression_leaves: 290 if _is_same_type(source_leaf, target_leaf): 291 similarity_score = self._dice_coefficient(source_leaf, target_leaf) 292 if similarity_score >= self.f: 293 heappush( 294 candidate_matchings, 295 ( 296 -similarity_score, 297 -_parent_similarity_score(source_leaf, target_leaf), 298 len(candidate_matchings), 299 source_leaf, 300 target_leaf, 301 ), 302 ) 303 304 # Pick best matchings based on the highest score 305 matching_set = set() 306 while candidate_matchings: 307 _, _, _, source_leaf, target_leaf = heappop(candidate_matchings) 308 if ( 309 id(source_leaf) in self._unmatched_source_nodes 310 and id(target_leaf) in self._unmatched_target_nodes 311 ): 312 matching_set.add((id(source_leaf), id(target_leaf))) 313 self._unmatched_source_nodes.remove(id(source_leaf)) 314 self._unmatched_target_nodes.remove(id(target_leaf)) 315 316 return matching_set 317 318 def _dice_coefficient(self, source: exp.Expression, target: exp.Expression) -> float: 319 source_histo = self._bigram_histo(source) 320 target_histo = self._bigram_histo(target) 321 322 total_grams = sum(source_histo.values()) + sum(target_histo.values()) 323 if not total_grams: 324 return 1.0 if source == target else 0.0 325 326 overlap_len = 0 327 overlapping_grams = set(source_histo) & set(target_histo) 328 for g in overlapping_grams: 329 overlap_len += min(source_histo[g], target_histo[g]) 330 331 return 2 * overlap_len / total_grams 332 333 def _bigram_histo(self, expression: exp.Expression) -> t.DefaultDict[str, int]: 334 if id(expression) in self._bigram_histo_cache: 335 return self._bigram_histo_cache[id(expression)] 336 337 expression_str = self._sql_generator.generate(expression) 338 count = max(0, len(expression_str) - 1) 339 bigram_histo: t.DefaultDict[str, int] = defaultdict(int) 340 for i in range(count): 341 bigram_histo[expression_str[i : i + 2]] += 1 342 343 self._bigram_histo_cache[id(expression)] = bigram_histo 344 return bigram_histo 345 346 347def _get_expression_leaves(expression: exp.Expression) -> t.Iterator[exp.Expression]: 348 has_child_exprs = False 349 350 for node in expression.iter_expressions(): 351 if not isinstance(node, IGNORED_LEAF_EXPRESSION_TYPES): 352 has_child_exprs = True 353 yield from _get_expression_leaves(node) 354 355 if not has_child_exprs: 356 yield expression 357 358 359def _get_non_expression_leaves(expression: exp.Expression) -> t.Iterator[t.Tuple[str, t.Any]]: 360 for arg, value in expression.args.items(): 361 if isinstance(value, exp.Expression) or ( 362 isinstance(value, list) and isinstance(seq_get(value, 0), exp.Expression) 363 ): 364 continue 365 366 yield (arg, value) 367 368 369def _is_same_type(source: exp.Expression, target: exp.Expression) -> bool: 370 if type(source) is type(target): 371 if isinstance(source, exp.Join): 372 return source.args.get("side") == target.args.get("side") 373 374 if isinstance(source, exp.Anonymous): 375 return source.this == target.this 376 377 return True 378 379 return False 380 381 382def _parent_similarity_score( 383 source: t.Optional[exp.Expression], target: t.Optional[exp.Expression] 384) -> int: 385 if source is None or target is None or type(source) is not type(target): 386 return 0 387 388 return 1 + _parent_similarity_score(source.parent, target.parent) 389 390 391def _expression_only_args(expression: exp.Expression) -> t.Iterator[exp.Expression]: 392 yield from ( 393 arg 394 for arg in expression.iter_expressions() 395 if not isinstance(arg, IGNORED_LEAF_EXPRESSION_TYPES) 396 ) 397 398 399def _lcs( 400 seq_a: t.Sequence[T], seq_b: t.Sequence[T], equal: t.Callable[[T, T], bool] 401) -> t.Sequence[t.Optional[T]]: 402 """Calculates the longest common subsequence""" 403 404 len_a = len(seq_a) 405 len_b = len(seq_b) 406 lcs_result = [[None] * (len_b + 1) for i in range(len_a + 1)] 407 408 for i in range(len_a + 1): 409 for j in range(len_b + 1): 410 if i == 0 or j == 0: 411 lcs_result[i][j] = [] # type: ignore 412 elif equal(seq_a[i - 1], seq_b[j - 1]): 413 lcs_result[i][j] = lcs_result[i - 1][j - 1] + [seq_a[i - 1]] # type: ignore 414 else: 415 lcs_result[i][j] = ( 416 lcs_result[i - 1][j] 417 if len(lcs_result[i - 1][j]) > len(lcs_result[i][j - 1]) # type: ignore 418 else lcs_result[i][j - 1] 419 ) 420 421 return lcs_result[len_a][len_b] # type: ignore
22@dataclass(frozen=True) 23class Insert: 24 """Indicates that a new node has been inserted""" 25 26 expression: exp.Expression
Indicates that a new node has been inserted
29@dataclass(frozen=True) 30class Remove: 31 """Indicates that an existing node has been removed""" 32 33 expression: exp.Expression
Indicates that an existing node has been removed
36@dataclass(frozen=True) 37class Move: 38 """Indicates that an existing node's position within the tree has changed""" 39 40 source: exp.Expression 41 target: exp.Expression
Indicates that an existing node's position within the tree has changed
44@dataclass(frozen=True) 45class Update: 46 """Indicates that an existing node has been updated""" 47 48 source: exp.Expression 49 target: exp.Expression
Indicates that an existing node has been updated
52@dataclass(frozen=True) 53class Keep: 54 """Indicates that an existing node hasn't been changed""" 55 56 source: exp.Expression 57 target: exp.Expression
Indicates that an existing node hasn't been changed
66def diff( 67 source: exp.Expression, 68 target: exp.Expression, 69 matchings: t.List[t.Tuple[exp.Expression, exp.Expression]] | None = None, 70 delta_only: bool = False, 71 copy: bool = True, 72 **kwargs: t.Any, 73) -> t.List[Edit]: 74 """ 75 Returns the list of changes between the source and the target expressions. 76 77 Examples: 78 >>> diff(parse_one("a + b"), parse_one("a + c")) 79 [ 80 Remove(expression=(COLUMN this: (IDENTIFIER this: b, quoted: False))), 81 Insert(expression=(COLUMN this: (IDENTIFIER this: c, quoted: False))), 82 Keep( 83 source=(ADD this: ...), 84 target=(ADD this: ...) 85 ), 86 Keep( 87 source=(COLUMN this: (IDENTIFIER this: a, quoted: False)), 88 target=(COLUMN this: (IDENTIFIER this: a, quoted: False)) 89 ), 90 ] 91 92 Args: 93 source: the source expression. 94 target: the target expression against which the diff should be calculated. 95 matchings: the list of pre-matched node pairs which is used to help the algorithm's 96 heuristics produce better results for subtrees that are known by a caller to be matching. 97 Note: expression references in this list must refer to the same node objects that are 98 referenced in the source / target trees. 99 delta_only: excludes all `Keep` nodes from the diff. 100 copy: whether to copy the input expressions. 101 Note: if this is set to false, the caller must ensure that there are no shared references 102 in the two trees, otherwise the diffing algorithm may produce unexpected behavior. 103 kwargs: additional arguments to pass to the ChangeDistiller instance. 104 105 Returns: 106 the list of Insert, Remove, Move, Update and Keep objects for each node in the source and the 107 target expression trees. This list represents a sequence of steps needed to transform the source 108 expression tree into the target one. 109 """ 110 matchings = matchings or [] 111 matching_ids = {id(n) for pair in matchings for n in pair} 112 113 def compute_node_mappings( 114 original: exp.Expression, copy: exp.Expression 115 ) -> t.Dict[int, exp.Expression]: 116 return { 117 id(old_node): new_node 118 for old_node, new_node in zip(original.walk(), copy.walk()) 119 if id(old_node) in matching_ids 120 } 121 122 source_copy = source.copy() if copy else source 123 target_copy = target.copy() if copy else target 124 125 node_mappings = { 126 **compute_node_mappings(source, source_copy), 127 **compute_node_mappings(target, target_copy), 128 } 129 matchings_copy = [(node_mappings[id(s)], node_mappings[id(t)]) for s, t in matchings] 130 131 return ChangeDistiller(**kwargs).diff( 132 source_copy, 133 target_copy, 134 matchings=matchings_copy, 135 delta_only=delta_only, 136 )
Returns the list of changes between the source and the target expressions.
Examples:
>>> diff(parse_one("a + b"), parse_one("a + c")) [ Remove(expression=(COLUMN this: (IDENTIFIER this: b, quoted: False))), Insert(expression=(COLUMN this: (IDENTIFIER this: c, quoted: False))), Keep( source=(ADD this: ...), target=(ADD this: ...) ), Keep( source=(COLUMN this: (IDENTIFIER this: a, quoted: False)), target=(COLUMN this: (IDENTIFIER this: a, quoted: False)) ), ]
Arguments:
- source: the source expression.
- target: the target expression against which the diff should be calculated.
- matchings: the list of pre-matched node pairs which is used to help the algorithm's heuristics produce better results for subtrees that are known by a caller to be matching. Note: expression references in this list must refer to the same node objects that are referenced in the source / target trees.
- delta_only: excludes all
Keep
nodes from the diff. - copy: whether to copy the input expressions. Note: if this is set to false, the caller must ensure that there are no shared references in the two trees, otherwise the diffing algorithm may produce unexpected behavior.
- kwargs: additional arguments to pass to the ChangeDistiller instance.
Returns:
the list of Insert, Remove, Move, Update and Keep objects for each node in the source and the target expression trees. This list represents a sequence of steps needed to transform the source expression tree into the target one.
154class ChangeDistiller: 155 """ 156 The implementation of the Change Distiller algorithm described by Beat Fluri and Martin Pinzger in 157 their paper https://ieeexplore.ieee.org/document/4339230, which in turn is based on the algorithm by 158 Chawathe et al. described in http://ilpubs.stanford.edu:8090/115/1/1995-46.pdf. 159 """ 160 161 def __init__(self, f: float = 0.6, t: float = 0.6, dialect: DialectType = None) -> None: 162 self.f = f 163 self.t = t 164 self._sql_generator = Dialect.get_or_raise(dialect).generator() 165 166 def diff( 167 self, 168 source: exp.Expression, 169 target: exp.Expression, 170 matchings: t.List[t.Tuple[exp.Expression, exp.Expression]] | None = None, 171 delta_only: bool = False, 172 ) -> t.List[Edit]: 173 matchings = matchings or [] 174 pre_matched_nodes = {id(s): id(t) for s, t in matchings} 175 if len({n for pair in pre_matched_nodes.items() for n in pair}) != 2 * len(matchings): 176 raise ValueError("Each node can be referenced at most once in the list of matchings") 177 178 self._source = source 179 self._target = target 180 self._source_index = { 181 id(n): n for n in self._source.bfs() if not isinstance(n, IGNORED_LEAF_EXPRESSION_TYPES) 182 } 183 self._target_index = { 184 id(n): n for n in self._target.bfs() if not isinstance(n, IGNORED_LEAF_EXPRESSION_TYPES) 185 } 186 self._unmatched_source_nodes = set(self._source_index) - set(pre_matched_nodes) 187 self._unmatched_target_nodes = set(self._target_index) - set(pre_matched_nodes.values()) 188 self._bigram_histo_cache: t.Dict[int, t.DefaultDict[str, int]] = {} 189 190 matching_set = self._compute_matching_set() | set(pre_matched_nodes.items()) 191 return self._generate_edit_script(dict(matching_set), delta_only) 192 193 def _generate_edit_script(self, matchings: t.Dict[int, int], delta_only: bool) -> t.List[Edit]: 194 edit_script: t.List[Edit] = [] 195 for removed_node_id in self._unmatched_source_nodes: 196 edit_script.append(Remove(self._source_index[removed_node_id])) 197 for inserted_node_id in self._unmatched_target_nodes: 198 edit_script.append(Insert(self._target_index[inserted_node_id])) 199 for kept_source_node_id, kept_target_node_id in matchings.items(): 200 source_node = self._source_index[kept_source_node_id] 201 target_node = self._target_index[kept_target_node_id] 202 203 if ( 204 not isinstance(source_node, UPDATABLE_EXPRESSION_TYPES) 205 or source_node == target_node 206 ): 207 edit_script.extend(self._generate_move_edits(source_node, target_node, matchings)) 208 209 source_non_expression_leaves = dict(_get_non_expression_leaves(source_node)) 210 target_non_expression_leaves = dict(_get_non_expression_leaves(target_node)) 211 212 if source_non_expression_leaves != target_non_expression_leaves: 213 edit_script.append(Update(source_node, target_node)) 214 elif not delta_only: 215 edit_script.append(Keep(source_node, target_node)) 216 else: 217 edit_script.append(Update(source_node, target_node)) 218 219 return edit_script 220 221 def _generate_move_edits( 222 self, source: exp.Expression, target: exp.Expression, matchings: t.Dict[int, int] 223 ) -> t.List[Move]: 224 source_args = [id(e) for e in _expression_only_args(source)] 225 target_args = [id(e) for e in _expression_only_args(target)] 226 227 args_lcs = set( 228 _lcs(source_args, target_args, lambda l, r: matchings.get(t.cast(int, l)) == r) 229 ) 230 231 move_edits = [] 232 for a in source_args: 233 if a not in args_lcs and a not in self._unmatched_source_nodes: 234 move_edits.append( 235 Move(source=self._source_index[a], target=self._target_index[matchings[a]]) 236 ) 237 238 return move_edits 239 240 def _compute_matching_set(self) -> t.Set[t.Tuple[int, int]]: 241 leaves_matching_set = self._compute_leaf_matching_set() 242 matching_set = leaves_matching_set.copy() 243 244 ordered_unmatched_source_nodes = { 245 id(n): None for n in self._source.bfs() if id(n) in self._unmatched_source_nodes 246 } 247 ordered_unmatched_target_nodes = { 248 id(n): None for n in self._target.bfs() if id(n) in self._unmatched_target_nodes 249 } 250 251 for source_node_id in ordered_unmatched_source_nodes: 252 for target_node_id in ordered_unmatched_target_nodes: 253 source_node = self._source_index[source_node_id] 254 target_node = self._target_index[target_node_id] 255 if _is_same_type(source_node, target_node): 256 source_leaf_ids = {id(l) for l in _get_expression_leaves(source_node)} 257 target_leaf_ids = {id(l) for l in _get_expression_leaves(target_node)} 258 259 max_leaves_num = max(len(source_leaf_ids), len(target_leaf_ids)) 260 if max_leaves_num: 261 common_leaves_num = sum( 262 1 if s in source_leaf_ids and t in target_leaf_ids else 0 263 for s, t in leaves_matching_set 264 ) 265 leaf_similarity_score = common_leaves_num / max_leaves_num 266 else: 267 leaf_similarity_score = 0.0 268 269 adjusted_t = ( 270 self.t if min(len(source_leaf_ids), len(target_leaf_ids)) > 4 else 0.4 271 ) 272 273 if leaf_similarity_score >= 0.8 or ( 274 leaf_similarity_score >= adjusted_t 275 and self._dice_coefficient(source_node, target_node) >= self.f 276 ): 277 matching_set.add((source_node_id, target_node_id)) 278 self._unmatched_source_nodes.remove(source_node_id) 279 self._unmatched_target_nodes.remove(target_node_id) 280 ordered_unmatched_target_nodes.pop(target_node_id, None) 281 break 282 283 return matching_set 284 285 def _compute_leaf_matching_set(self) -> t.Set[t.Tuple[int, int]]: 286 candidate_matchings: t.List[t.Tuple[float, int, int, exp.Expression, exp.Expression]] = [] 287 source_expression_leaves = list(_get_expression_leaves(self._source)) 288 target_expression_leaves = list(_get_expression_leaves(self._target)) 289 for source_leaf in source_expression_leaves: 290 for target_leaf in target_expression_leaves: 291 if _is_same_type(source_leaf, target_leaf): 292 similarity_score = self._dice_coefficient(source_leaf, target_leaf) 293 if similarity_score >= self.f: 294 heappush( 295 candidate_matchings, 296 ( 297 -similarity_score, 298 -_parent_similarity_score(source_leaf, target_leaf), 299 len(candidate_matchings), 300 source_leaf, 301 target_leaf, 302 ), 303 ) 304 305 # Pick best matchings based on the highest score 306 matching_set = set() 307 while candidate_matchings: 308 _, _, _, source_leaf, target_leaf = heappop(candidate_matchings) 309 if ( 310 id(source_leaf) in self._unmatched_source_nodes 311 and id(target_leaf) in self._unmatched_target_nodes 312 ): 313 matching_set.add((id(source_leaf), id(target_leaf))) 314 self._unmatched_source_nodes.remove(id(source_leaf)) 315 self._unmatched_target_nodes.remove(id(target_leaf)) 316 317 return matching_set 318 319 def _dice_coefficient(self, source: exp.Expression, target: exp.Expression) -> float: 320 source_histo = self._bigram_histo(source) 321 target_histo = self._bigram_histo(target) 322 323 total_grams = sum(source_histo.values()) + sum(target_histo.values()) 324 if not total_grams: 325 return 1.0 if source == target else 0.0 326 327 overlap_len = 0 328 overlapping_grams = set(source_histo) & set(target_histo) 329 for g in overlapping_grams: 330 overlap_len += min(source_histo[g], target_histo[g]) 331 332 return 2 * overlap_len / total_grams 333 334 def _bigram_histo(self, expression: exp.Expression) -> t.DefaultDict[str, int]: 335 if id(expression) in self._bigram_histo_cache: 336 return self._bigram_histo_cache[id(expression)] 337 338 expression_str = self._sql_generator.generate(expression) 339 count = max(0, len(expression_str) - 1) 340 bigram_histo: t.DefaultDict[str, int] = defaultdict(int) 341 for i in range(count): 342 bigram_histo[expression_str[i : i + 2]] += 1 343 344 self._bigram_histo_cache[id(expression)] = bigram_histo 345 return bigram_histo
The implementation of the Change Distiller algorithm described by Beat Fluri and Martin Pinzger in their paper https://ieeexplore.ieee.org/document/4339230, which in turn is based on the algorithm by Chawathe et al. described in http://ilpubs.stanford.edu:8090/115/1/1995-46.pdf.
166 def diff( 167 self, 168 source: exp.Expression, 169 target: exp.Expression, 170 matchings: t.List[t.Tuple[exp.Expression, exp.Expression]] | None = None, 171 delta_only: bool = False, 172 ) -> t.List[Edit]: 173 matchings = matchings or [] 174 pre_matched_nodes = {id(s): id(t) for s, t in matchings} 175 if len({n for pair in pre_matched_nodes.items() for n in pair}) != 2 * len(matchings): 176 raise ValueError("Each node can be referenced at most once in the list of matchings") 177 178 self._source = source 179 self._target = target 180 self._source_index = { 181 id(n): n for n in self._source.bfs() if not isinstance(n, IGNORED_LEAF_EXPRESSION_TYPES) 182 } 183 self._target_index = { 184 id(n): n for n in self._target.bfs() if not isinstance(n, IGNORED_LEAF_EXPRESSION_TYPES) 185 } 186 self._unmatched_source_nodes = set(self._source_index) - set(pre_matched_nodes) 187 self._unmatched_target_nodes = set(self._target_index) - set(pre_matched_nodes.values()) 188 self._bigram_histo_cache: t.Dict[int, t.DefaultDict[str, int]] = {} 189 190 matching_set = self._compute_matching_set() | set(pre_matched_nodes.items()) 191 return self._generate_edit_script(dict(matching_set), delta_only)