Line data Source code
1 : //! A statement-level semantic diff between two parsed scripts.
2 : //!
3 : //! A modified patience diff over the statements of two parsed scripts: statements are mapped by
4 : //! structural equality (order-insensitive), the longest common subsequence of unambiguous pairs is
5 : //! kept, and the remaining statements are classified as MOVE / UPDATE / DELETE / INSERT.
6 : //!
7 : //! AST spans are token-index based and are resolved through the scanned script before touching
8 : //! text. Object attribute lists are not sorted by key, the traversals sort a scratch copy.
9 :
10 : use dashql_buffers::diff::{ScriptDiffOpCode, ScriptDiffOpT, ScriptDiffT};
11 : use dashql_buffers::parser::{Node, NodeType, TextSpanT};
12 : use dashql_parser::parser::context::resolve_text_span;
13 : use dashql_parser::parser::{ParsedScript, Statement};
14 : use dashql_parser::span::TextSpan;
15 :
16 : /// The fraction of nodes that must be equal between statements to emit an UPDATE (instead of
17 : /// DELETE + INSERT)
18 : const UPDATE_SIMILARITY_THRESHOLD: f64 = 0.75;
19 :
20 : /// A single diff operation
21 : #[derive(Clone, Debug, PartialEq)]
22 : pub struct DiffOp {
23 : /// The operation: MOVE, UPDATE, DELETE, INSERT or KEEP
24 : pub code: ScriptDiffOpCode,
25 : /// The source (old) statement index, None for INSERT
26 : pub source_statement: Option<u32>,
27 : /// The target (new) statement index, None for DELETE
28 : pub target_statement: Option<u32>,
29 : /// The resolved text span of the source statement root (empty if no source)
30 : pub source_span: TextSpan,
31 : /// The resolved text span of the target statement root (empty if no target)
32 : pub target_span: TextSpan,
33 : /// The changed sub-ranges within the target statement (UPDATE only, coalesced)
34 : pub target_changes: Vec<TextSpan>,
35 : }
36 :
37 : /// A fast similarity estimate for two statements
38 : #[derive(Clone, Copy, Debug, PartialEq, Eq)]
39 : enum SimilarityEstimate {
40 : NotEqual,
41 : Similar,
42 : Equal,
43 : }
44 :
45 : /// A statement similarity score (matching nodes / total nodes)
46 : #[derive(Clone, Copy, Debug, Default)]
47 : struct StatementSimilarity {
48 : /// The number of nodes that match in both statements
49 : matching_nodes: usize,
50 : /// The node count of the larger statement
51 : total_nodes: usize,
52 : }
53 :
54 : impl StatementSimilarity {
55 21 : fn score(&self) -> f64 {
56 21 : if self.total_nodes == 0 {
57 0 : 0.0
58 : } else {
59 21 : self.matching_nodes as f64 / self.total_nodes as f64
60 : }
61 21 : }
62 : }
63 :
64 : /// A statement mapping (source id, target id)
65 : type StatementMapping = (usize, usize);
66 :
67 : /// The emitted operations and statements while computing a diff
68 : struct Emitter {
69 : /// The emitted operations
70 : ops: Vec<DiffOp>,
71 : /// Whether a source statement was emitted, by statement index
72 : source_emitted: Vec<bool>,
73 : /// Whether a target statement was emitted, by statement index
74 : target_emitted: Vec<bool>,
75 : }
76 :
77 : /// Is the node type an enum? Enums live between ENUM_KEYS_ and OBJECT_KEYS_.
78 33 : fn is_enum_type(t: NodeType) -> bool {
79 33 : let id = t.0;
80 33 : id > NodeType::ENUM_KEYS_.0 && id < NodeType::OBJECT_KEYS_.0
81 33 : }
82 :
83 : /// Is the node type an object? Objects live above OBJECT_KEYS_.
84 955 : fn is_object_type(t: NodeType) -> bool {
85 955 : t.0 > NodeType::OBJECT_KEYS_.0
86 955 : }
87 :
88 : /// Does the node type have child nodes (as opposed to an inline value)?
89 752 : fn has_children(t: NodeType) -> bool {
90 752 : t == NodeType::ARRAY || is_object_type(t)
91 752 : }
92 :
93 1464 : fn key_id(n: &Node) -> u16 {
94 1464 : n.attribute_key().0
95 1464 : }
96 :
97 : /// The text of a span, read as if the text were followed by two padding NUL bytes. Spans of EOF errors
98 : /// end one byte past the text (see docs/design/core_quirks.md).
99 134 : fn padded_text(script: &ParsedScript, span: TextSpan) -> std::borrow::Cow<'_, [u8]> {
100 134 : let text = script.scanned.text.as_bytes();
101 134 : let begin = (span.offset as usize).min(text.len() + 2);
102 134 : let end = (span.end() as usize).min(text.len() + 2);
103 134 : if end <= text.len() {
104 134 : return std::borrow::Cow::Borrowed(&text[begin..end]);
105 0 : }
106 0 : let mut out = text[begin.min(text.len())..].to_vec();
107 0 : out.resize(end - begin, 0);
108 0 : std::borrow::Cow::Owned(out)
109 134 : }
110 :
111 : /// The resolved text of a node (for operators and literals)
112 56 : fn node_text<'a>(script: &'a ParsedScript, node: &Node) -> std::borrow::Cow<'a, [u8]> {
113 56 : padded_text(script, resolve(script, node))
114 56 : }
115 :
116 : /// The registered name text of a NAME node
117 306 : fn name_text<'a>(script: &'a ParsedScript, node: &Node) -> &'a str {
118 306 : &script.scanned.names.get(node.children_begin_or_value()).text
119 306 : }
120 :
121 317 : fn resolve(script: &ParsedScript, node: &Node) -> TextSpan {
122 317 : resolve_text_span(&script.scanned.text, &script.scanned.symbols, *node.symbol_span())
123 317 : }
124 :
125 : /// The text span of a statement root (empty if the root is invalid)
126 82 : fn resolve_statement_span(script: &ParsedScript, statement: &Statement) -> TextSpan {
127 82 : match script.nodes.get(statement.root as usize) {
128 82 : Some(root) => resolve(script, root),
129 0 : None => TextSpan::default(),
130 : }
131 82 : }
132 :
133 : /// An object's child node indices sorted (stably) by attribute key
134 770 : fn collect_sorted_children(script: &ParsedScript, node: &Node, out: &mut Vec<u32>) {
135 770 : out.clear();
136 770 : let begin = node.children_begin_or_value();
137 770 : out.extend(begin..begin + node.children_count());
138 770 : out.sort_by_key(|&i| key_id(&script.nodes[i as usize]));
139 770 : }
140 :
141 : /// The diff between two parsed scripts
142 : pub struct ScriptDiff<'a> {
143 : /// The source (old) script
144 : source: &'a ParsedScript,
145 : /// The target (new) script
146 : target: &'a ParsedScript,
147 : /// Memoized subtree sizes (0 = not computed yet)
148 : source_subtree_sizes: Vec<usize>,
149 : /// Memoized subtree sizes of the target (0 = not computed yet)
150 : target_subtree_sizes: Vec<usize>,
151 : /// The computed operations
152 : ops: Vec<DiffOp>,
153 : /// Whether the operations were computed
154 : computed: bool,
155 : }
156 :
157 : impl<'a> ScriptDiff<'a> {
158 33 : pub fn new(source: &'a ParsedScript, target: &'a ParsedScript) -> Self {
159 33 : Self {
160 33 : source,
161 33 : target,
162 33 : source_subtree_sizes: Vec::new(),
163 33 : target_subtree_sizes: Vec::new(),
164 33 : ops: Vec::new(),
165 33 : computed: false,
166 33 : }
167 33 : }
168 :
169 : /// The size of the subtree rooted at `root` (memoized iterative DFS)
170 42 : fn compute_tree_size(script: &ParsedScript, root: usize, sizes: &mut Vec<usize>) -> usize {
171 42 : if root >= script.nodes.len() {
172 0 : return 0;
173 42 : }
174 42 : if sizes.len() != script.nodes.len() {
175 30 : *sizes = vec![0; script.nodes.len()];
176 30 : } else if sizes[root] > 0 {
177 7 : return sizes[root];
178 5 : }
179 : // (node, parent, visited)
180 35 : let mut pending: Vec<(usize, usize, bool)> = Vec::with_capacity(32);
181 35 : pending.push((root, root, false));
182 35 : let mut node_count = 0;
183 1504 : while let Some(&(node_id, parent, visited)) = pending.last() {
184 1504 : if visited {
185 752 : if pending.len() == 1 {
186 35 : node_count = sizes[node_id];
187 35 : break;
188 717 : }
189 717 : sizes[parent] += sizes[node_id];
190 717 : pending.pop();
191 717 : continue;
192 752 : }
193 752 : sizes[node_id] = 1;
194 752 : pending.last_mut().unwrap().2 = true;
195 752 : let node = &script.nodes[node_id];
196 752 : if has_children(node.node_type()) {
197 541 : let begin = node.children_begin_or_value() as usize;
198 717 : for i in begin..begin + node.children_count() as usize {
199 717 : pending.push((i, node_id, false));
200 717 : }
201 211 : }
202 : }
203 35 : node_count
204 42 : }
205 :
206 : /// Estimate the similarity of two statements (O(1) for unchanged statements)
207 83 : fn estimate_similarity(&self, source: &Statement, target: &Statement) -> SimilarityEstimate {
208 83 : let (Some(s), Some(t)) = (self.source.nodes.get(source.root as usize), self.target.nodes.get(target.root as usize))
209 : else {
210 0 : return SimilarityEstimate::NotEqual;
211 : };
212 83 : if s.node_type() != t.node_type() {
213 2 : return SimilarityEstimate::NotEqual;
214 81 : }
215 : // Compare the text if the statements are equal in size and number of root attributes.
216 81 : let s_span = resolve(self.source, s);
217 81 : let t_span = resolve(self.target, t);
218 81 : if s.children_count() == t.children_count() && s_span.length == t_span.length {
219 39 : if padded_text(self.source, s_span) == padded_text(self.target, t_span) {
220 20 : return SimilarityEstimate::Equal;
221 19 : }
222 42 : }
223 61 : SimilarityEstimate::Similar
224 83 : }
225 :
226 : /// Do two nodes of the same type match without looking at their children?
227 865 : fn leaf_match(&self, s: &Node, t: &Node) -> Option<bool> {
228 865 : Some(match s.node_type() {
229 0 : NodeType::NONE => true,
230 0 : NodeType::BOOL => s.children_begin_or_value() == t.children_begin_or_value(),
231 153 : NodeType::NAME => name_text(self.source, s) == name_text(self.target, t),
232 : NodeType::OPERATOR
233 : | NodeType::LITERAL_NULL
234 : | NodeType::LITERAL_INTEGER
235 : | NodeType::LITERAL_FLOAT
236 : | NodeType::LITERAL_STRING
237 28 : | NodeType::LITERAL_INTERVAL => node_text(self.source, s) == node_text(self.target, t),
238 684 : _ => return None,
239 : })
240 865 : }
241 :
242 : /// Compute the similarity of two statements (lockstep DFS over the subtrees)
243 21 : fn compute_similarity(&mut self, source: &Statement, target: &Statement) -> StatementSimilarity {
244 21 : let source_size = Self::compute_tree_size(self.source, source.root as usize, &mut self.source_subtree_sizes);
245 21 : let target_size = Self::compute_tree_size(self.target, target.root as usize, &mut self.target_subtree_sizes);
246 21 : let node_count = source_size.max(target_size);
247 21 : if node_count == 0 {
248 0 : return StatementSimilarity::default();
249 21 : }
250 : /// A pair of nodes on the stack of the lockstep DFS
251 : struct Entry {
252 : /// The node in the source script
253 : source_node: usize,
254 : /// The node in the target script
255 : target_node: usize,
256 : /// The stack index of the parent entry
257 : parent_entry: usize,
258 : /// The number of matching nodes in the subtree
259 : matching_nodes: usize,
260 : /// Whether the children were pushed
261 : visited: bool,
262 : }
263 21 : let mut pending = Vec::with_capacity(32);
264 21 : pending.push(Entry {
265 21 : source_node: source.root as usize,
266 21 : target_node: target.root as usize,
267 21 : parent_entry: 0,
268 21 : matching_nodes: 0,
269 21 : visited: false,
270 21 : });
271 21 : let mut src_children = Vec::new();
272 21 : let mut tgt_children = Vec::new();
273 21 : let mut sim = StatementSimilarity::default();
274 752 : while !pending.is_empty() {
275 752 : let idx = pending.len() - 1;
276 752 : if pending[idx].visited {
277 376 : if idx == 0 {
278 21 : sim.total_nodes = node_count;
279 21 : sim.matching_nodes = pending[0].matching_nodes;
280 21 : break;
281 355 : }
282 355 : let entry = pending.pop().unwrap();
283 355 : pending[entry.parent_entry].matching_nodes += entry.matching_nodes;
284 355 : continue;
285 376 : }
286 376 : pending[idx].visited = true;
287 376 : let s = self.source.nodes[pending[idx].source_node];
288 376 : let t = self.target.nodes[pending[idx].target_node];
289 376 : let mut matched = true;
290 376 : if s.node_type() != t.node_type() {
291 7 : matched = false;
292 369 : } else if let Some(m) = self.leaf_match(&s, &t) {
293 83 : matched = m;
294 286 : } else if s.node_type() == NodeType::ARRAY {
295 111 : let (sc, tc) = (s.children_count(), t.children_count());
296 111 : matched = sc == tc;
297 111 : let (sb, tb) = (s.children_begin_or_value(), t.children_begin_or_value());
298 159 : for i in 0..sc.min(tc) {
299 159 : pending.push(Entry {
300 159 : source_node: (sb + i) as usize,
301 159 : target_node: (tb + i) as usize,
302 159 : parent_entry: idx,
303 159 : matching_nodes: 0,
304 159 : visited: false,
305 159 : });
306 159 : }
307 175 : } else if is_object_type(s.node_type()) {
308 : // Attribute lists are unsorted; sort scratch copies by key, then merge-join.
309 161 : collect_sorted_children(self.source, &s, &mut src_children);
310 161 : collect_sorted_children(self.target, &t, &mut tgt_children);
311 161 : matched = s.children_count() == t.children_count();
312 161 : let (mut i, mut j) = (0, 0);
313 363 : while i < src_children.len() && j < tgt_children.len() {
314 202 : let sk = key_id(&self.source.nodes[src_children[i] as usize]);
315 202 : let tk = key_id(&self.target.nodes[tgt_children[j] as usize]);
316 202 : if sk < tk {
317 3 : i += 1;
318 3 : matched = false;
319 199 : } else if sk > tk {
320 3 : j += 1;
321 3 : matched = false;
322 196 : } else {
323 196 : pending.push(Entry {
324 196 : source_node: src_children[i] as usize,
325 196 : target_node: tgt_children[j] as usize,
326 196 : parent_entry: idx,
327 196 : matching_nodes: 0,
328 196 : visited: false,
329 196 : });
330 196 : i += 1;
331 196 : j += 1;
332 196 : }
333 : }
334 14 : } else if is_enum_type(s.node_type()) {
335 14 : matched = s.children_begin_or_value() == t.children_begin_or_value();
336 14 : }
337 376 : if matched {
338 353 : pending[idx].matching_nodes += 1;
339 353 : }
340 : }
341 21 : sim
342 21 : }
343 :
344 : /// Check two statements for deep equality
345 40 : fn check_deep_equality(&self, source: &Statement, target: &Statement) -> bool {
346 40 : let source_valid = (source.root as usize) < self.source.nodes.len();
347 40 : let target_valid = (target.root as usize) < self.target.nodes.len();
348 40 : if !source_valid || !target_valid {
349 0 : return !source_valid && !target_valid;
350 40 : }
351 40 : let mut pending = vec![(source.root as usize, target.root as usize)];
352 40 : let mut src_children = Vec::new();
353 40 : let mut tgt_children = Vec::new();
354 169 : while let Some((source_id, target_id)) = pending.pop() {
355 168 : let s = self.source.nodes[source_id];
356 168 : let t = self.target.nodes[target_id];
357 168 : if s.node_type() != t.node_type() {
358 12 : return false;
359 156 : }
360 156 : if let Some(m) = self.leaf_match(&s, &t) {
361 19 : if !m {
362 13 : return false;
363 6 : }
364 137 : } else if s.node_type() == NodeType::ARRAY {
365 49 : if s.children_count() != t.children_count() {
366 7 : return false;
367 42 : }
368 42 : let (sb, tb) = (s.children_begin_or_value(), t.children_begin_or_value());
369 57 : for i in 0..s.children_count() {
370 57 : pending.push(((sb + i) as usize, (tb + i) as usize));
371 57 : }
372 88 : } else if is_object_type(s.node_type()) {
373 83 : if s.children_count() != t.children_count() {
374 6 : return false;
375 77 : }
376 77 : collect_sorted_children(self.source, &s, &mut src_children);
377 77 : collect_sorted_children(self.target, &t, &mut tgt_children);
378 106 : for (&si, &ti) in src_children.iter().zip(&tgt_children) {
379 106 : if key_id(&self.source.nodes[si as usize]) != key_id(&self.target.nodes[ti as usize]) {
380 1 : return false;
381 105 : }
382 105 : pending.push((si as usize, ti as usize));
383 : }
384 5 : } else if is_enum_type(s.node_type()) && s.children_begin_or_value() != t.children_begin_or_value() {
385 0 : return false;
386 5 : }
387 : }
388 1 : true
389 40 : }
390 :
391 : /// Map statements between the two scripts (unique + equal pairs, with ambiguity handling)
392 33 : fn map_statements(&self) -> (Vec<StatementMapping>, Vec<StatementMapping>) {
393 33 : let source_count = self.source.statements.len();
394 33 : let target_count = self.target.statements.len();
395 33 : let mut source_ambiguous = vec![false; source_count];
396 33 : let mut target_ambiguous = vec![false; target_count];
397 33 : let mut target_mapping: Vec<Option<usize>> = vec![None; target_count];
398 33 : let mut unique_pairs = Vec::new();
399 33 : let mut equal_pairs = Vec::new();
400 :
401 40 : for source_id in 0..source_count {
402 40 : let source_stmt = &self.source.statements[source_id];
403 40 : let mut matched: Option<usize> = None;
404 61 : for target_id in 0..target_count {
405 61 : let target_stmt = &self.target.statements[target_id];
406 61 : let equal = match self.estimate_similarity(source_stmt, target_stmt) {
407 1 : SimilarityEstimate::NotEqual => false,
408 40 : SimilarityEstimate::Similar => self.check_deep_equality(source_stmt, target_stmt),
409 20 : SimilarityEstimate::Equal => true,
410 : };
411 61 : if !equal {
412 40 : continue;
413 21 : }
414 21 : equal_pairs.push((source_id, target_id));
415 21 : if let Some(existing) = target_mapping[target_id] {
416 : // Two source statements map to the same target statement
417 2 : source_ambiguous[source_id] = true;
418 2 : source_ambiguous[existing] = true;
419 2 : target_ambiguous[target_id] = true;
420 2 : continue;
421 19 : } else if let Some(m) = matched {
422 : // The source statement maps to two target statements
423 2 : source_ambiguous[source_id] = true;
424 2 : target_ambiguous[m] = true;
425 2 : target_ambiguous[target_id] = true;
426 2 : continue;
427 17 : }
428 17 : target_mapping[target_id] = Some(source_id);
429 17 : matched = Some(target_id);
430 : }
431 : }
432 :
433 42 : for (target_id, &source_id) in target_mapping.iter().enumerate() {
434 42 : let Some(source_id) = source_id else { continue };
435 17 : if source_ambiguous[source_id] || target_ambiguous[target_id] {
436 4 : continue;
437 13 : }
438 13 : unique_pairs.push((source_id, target_id));
439 : }
440 33 : unique_pairs.sort_by_key(|p| p.0);
441 33 : equal_pairs.sort();
442 33 : (unique_pairs, equal_pairs)
443 33 : }
444 :
445 : /// The longest common subsequence among the unique pairs (patience sort)
446 33 : fn find_lcs(unique_pairs: &[StatementMapping]) -> Vec<StatementMapping> {
447 : // (source id, target id, size of the previous pile)
448 33 : let mut piles: Vec<Vec<(usize, usize, usize)>> = Vec::new();
449 33 : for &(source_id, target_id) in unique_pairs {
450 13 : match piles.iter().position(|pile| pile.last().unwrap().1 >= target_id) {
451 2 : Some(p) => {
452 2 : let prev_pile_id = p.max(1) - 1;
453 2 : let prev_pile_size = piles[prev_pile_id].len();
454 2 : piles[p].push((source_id, target_id, prev_pile_size));
455 2 : }
456 11 : None => {
457 11 : piles.push(Vec::new());
458 11 : let prev_pile_id = piles.len().max(2) - 2;
459 11 : let prev_pile_size = piles[prev_pile_id].len();
460 11 : piles.last_mut().unwrap().push((source_id, target_id, prev_pile_size));
461 11 : }
462 : }
463 : }
464 33 : let mut lcs = Vec::new();
465 33 : if piles.is_empty() {
466 23 : return lcs;
467 10 : }
468 10 : let mut pile_id = piles.len() - 1;
469 10 : let mut entry_id = piles[pile_id].len() - 1;
470 : loop {
471 11 : let (source_id, target_id, prev_pile_size) = piles[pile_id][entry_id];
472 11 : lcs.push((source_id, target_id));
473 11 : if pile_id == 0 {
474 10 : break;
475 1 : }
476 1 : entry_id = prev_pile_size - 1;
477 1 : pile_id -= 1;
478 : }
479 10 : lcs.reverse();
480 10 : lcs
481 33 : }
482 :
483 : /// The changed sub-ranges within an UPDATE target statement (target-side highlighting)
484 16 : fn collect_target_changes(&self, source: &Statement, target: &Statement) -> Vec<TextSpan> {
485 16 : let mut changes = Vec::new();
486 16 : if source.root as usize >= self.source.nodes.len() || target.root as usize >= self.target.nodes.len() {
487 0 : return changes;
488 16 : }
489 17 : let record = |changes: &mut Vec<TextSpan>, target_node_id: usize| {
490 17 : let span = resolve(self.target, &self.target.nodes[target_node_id]);
491 17 : if span.length > 0 {
492 17 : changes.push(span);
493 17 : }
494 17 : };
495 16 : let mut pending = vec![(source.root as usize, target.root as usize)];
496 16 : let mut src_children = Vec::new();
497 16 : let mut tgt_children = Vec::new();
498 360 : while let Some((source_id, target_id)) = pending.pop() {
499 344 : let s = self.source.nodes[source_id];
500 344 : let t = self.target.nodes[target_id];
501 : // Different node type: the entire target subtree changed
502 344 : if s.node_type() != t.node_type() {
503 4 : record(&mut changes, target_id);
504 4 : continue;
505 340 : }
506 340 : if let Some(m) = self.leaf_match(&s, &t) {
507 79 : if !m {
508 7 : record(&mut changes, target_id);
509 74 : }
510 261 : } else if s.node_type() == NodeType::ARRAY {
511 100 : let (sc, tc) = (s.children_count(), t.children_count());
512 100 : let (sb, tb) = (s.children_begin_or_value(), t.children_begin_or_value());
513 100 : let common = sc.min(tc);
514 148 : for i in 0..common {
515 148 : pending.push(((sb + i) as usize, (tb + i) as usize));
516 148 : }
517 : // Extra target children are additions
518 100 : for i in common..tc {
519 3 : record(&mut changes, (tb + i) as usize);
520 3 : }
521 161 : } else if is_object_type(s.node_type()) {
522 147 : collect_sorted_children(self.source, &s, &mut src_children);
523 147 : collect_sorted_children(self.target, &t, &mut tgt_children);
524 147 : let (mut i, mut j) = (0, 0);
525 333 : while i < src_children.len() && j < tgt_children.len() {
526 186 : let sk = key_id(&self.source.nodes[src_children[i] as usize]);
527 186 : let tk = key_id(&self.target.nodes[tgt_children[j] as usize]);
528 186 : if sk < tk {
529 3 : i += 1;
530 183 : } else if sk > tk {
531 3 : record(&mut changes, tgt_children[j] as usize);
532 3 : j += 1;
533 180 : } else {
534 180 : pending.push((src_children[i] as usize, tgt_children[j] as usize));
535 180 : i += 1;
536 180 : j += 1;
537 180 : }
538 : }
539 147 : for &child in &tgt_children[j..] {
540 0 : record(&mut changes, child as usize);
541 0 : }
542 14 : } else if is_enum_type(s.node_type()) && s.children_begin_or_value() != t.children_begin_or_value() {
543 0 : record(&mut changes, target_id);
544 14 : }
545 : }
546 : // Sort and coalesce overlapping or adjacent spans
547 16 : if changes.len() > 1 {
548 2 : changes.sort_by_key(|c| c.offset);
549 2 : let mut coalesced: Vec<TextSpan> = Vec::with_capacity(changes.len());
550 2 : coalesced.push(changes[0]);
551 2 : for change in &changes[1..] {
552 2 : let last = coalesced.last_mut().unwrap();
553 2 : let last_end = last.end();
554 2 : if change.offset <= last_end {
555 0 : let new_end = last_end.max(change.end());
556 0 : *last = TextSpan::new(last.offset, new_end - last.offset);
557 2 : } else {
558 2 : coalesced.push(*change);
559 2 : }
560 : }
561 2 : changes = coalesced;
562 14 : }
563 16 : changes
564 16 : }
565 :
566 : /// Emit a diff operation
567 49 : fn emit(&self, out: &mut Emitter, code: ScriptDiffOpCode, source_id: Option<usize>, target_id: Option<usize>) {
568 49 : let mut op = DiffOp {
569 49 : code,
570 49 : source_statement: None,
571 49 : target_statement: None,
572 49 : source_span: TextSpan::default(),
573 49 : target_span: TextSpan::default(),
574 49 : target_changes: Vec::new(),
575 49 : };
576 49 : if let Some(s) = source_id {
577 40 : op.source_statement = Some(s as u32);
578 40 : op.source_span = resolve_statement_span(self.source, &self.source.statements[s]);
579 40 : out.source_emitted[s] = true;
580 40 : }
581 49 : if let Some(t) = target_id {
582 42 : op.target_statement = Some(t as u32);
583 42 : op.target_span = resolve_statement_span(self.target, &self.target.statements[t]);
584 42 : out.target_emitted[t] = true;
585 42 : }
586 49 : if let (ScriptDiffOpCode::UPDATE, Some(s), Some(t)) = (code, source_id, target_id) {
587 16 : op.target_changes = self.collect_target_changes(&self.source.statements[s], &self.target.statements[t]);
588 34 : }
589 49 : out.ops.push(op);
590 49 : }
591 :
592 : /// Compute the diff (memoized)
593 33 : pub fn compute(&mut self) -> &[DiffOp] {
594 33 : if self.computed {
595 0 : return &self.ops;
596 33 : }
597 33 : self.computed = true;
598 33 : let source_count = self.source.statements.len();
599 33 : let target_count = self.target.statements.len();
600 33 : let (unique_pairs, equal_pairs) = self.map_statements();
601 33 : let lcs = Self::find_lcs(&unique_pairs);
602 33 : let mut out = Emitter {
603 33 : ops: Vec::new(),
604 33 : source_emitted: vec![false; source_count],
605 33 : target_emitted: vec![false; target_count],
606 33 : };
607 :
608 : // Iterate over the sections between LCS entries
609 33 : let mut next: StatementMapping = (0, 0);
610 44 : for lcs_index in 0..=lcs.len() {
611 44 : let prev = next;
612 44 : next = lcs.get(lcs_index).copied().unwrap_or((source_count, target_count));
613 44 : let (prev_source_id, prev_target_id) = prev;
614 44 : let (next_source_id, next_target_id) = next;
615 :
616 44 : for source_id in prev_source_id..next_source_id {
617 : // Emit equal pairs that are ambiguous or cross section boundaries (MOVE)
618 40 : let begin = equal_pairs.partition_point(|p| p.0 < source_id);
619 40 : let end = begin + equal_pairs[begin..].partition_point(|p| p.0 <= source_id);
620 40 : for &(_, target_id) in &equal_pairs[begin..end] {
621 19 : if out.target_emitted[target_id] {
622 13 : continue;
623 6 : }
624 6 : self.emit(&mut out, ScriptDiffOpCode::MOVE, Some(source_id), Some(target_id));
625 6 : break;
626 : }
627 40 : if out.source_emitted[source_id] {
628 17 : continue;
629 23 : }
630 23 : let source_stmt = self.source.statements[source_id];
631 : // The highest-scoring remaining target in the section above the threshold (a
632 : // deliberate divergence from the legacy heap, which picked the smallest score)
633 23 : let mut best_target = None;
634 23 : let mut best_score = -1.0;
635 28 : for target_id in prev_target_id..next_target_id {
636 28 : if out.target_emitted[target_id] {
637 6 : continue;
638 22 : }
639 22 : let target_stmt = self.target.statements[target_id];
640 22 : match self.estimate_similarity(&source_stmt, &target_stmt) {
641 1 : SimilarityEstimate::NotEqual => continue,
642 : SimilarityEstimate::Equal => {
643 0 : self.emit(&mut out, ScriptDiffOpCode::KEEP, Some(source_id), Some(target_id));
644 0 : break;
645 : }
646 21 : SimilarityEstimate::Similar => {}
647 : }
648 21 : let score = self.compute_similarity(&source_stmt, &target_stmt).score();
649 21 : if score >= UPDATE_SIMILARITY_THRESHOLD && score > best_score {
650 16 : best_score = score;
651 16 : best_target = Some(target_id);
652 16 : }
653 : }
654 : // An equal match emitted a KEEP
655 23 : if out.source_emitted[source_id] {
656 0 : continue;
657 23 : }
658 23 : match best_target {
659 16 : Some(t) => self.emit(&mut out, ScriptDiffOpCode::UPDATE, Some(source_id), Some(t)),
660 7 : None => self.emit(&mut out, ScriptDiffOpCode::DELETE, Some(source_id), None),
661 : }
662 : }
663 : // Insert the new statements of the section
664 44 : for target_id in prev_target_id..next_target_id {
665 42 : if !out.target_emitted[target_id] {
666 9 : self.emit(&mut out, ScriptDiffOpCode::INSERT, None, Some(target_id));
667 33 : }
668 : }
669 44 : if lcs_index < lcs.len() {
670 11 : self.emit(&mut out, ScriptDiffOpCode::KEEP, Some(next_source_id), Some(next_target_id));
671 33 : }
672 : }
673 33 : self.ops = out.ops;
674 33 : &self.ops
675 33 : }
676 :
677 : /// Pack the diff into the FlatBuffers object API
678 4 : pub fn pack(&mut self) -> ScriptDiffT {
679 12 : let span = |s: &TextSpan| TextSpanT { offset: s.offset, length: s.length };
680 4 : let ops = self
681 4 : .compute()
682 4 : .iter()
683 5 : .map(|op| {
684 5 : let mut out = ScriptDiffOpT::default();
685 5 : out.code = op.code;
686 5 : out.source_statement = op.source_statement.unwrap_or(u32::MAX);
687 5 : out.target_statement = op.target_statement.unwrap_or(u32::MAX);
688 5 : out.source_span = op.source_statement.map(|_| span(&op.source_span));
689 5 : out.target_span = op.target_statement.map(|_| span(&op.target_span));
690 5 : out.target_changes = (!op.target_changes.is_empty()).then(|| op.target_changes.iter().map(span).collect());
691 5 : out
692 5 : })
693 4 : .collect();
694 4 : let mut diff = ScriptDiffT::default();
695 4 : diff.ops = Some(ops);
696 4 : diff
697 4 : }
698 : }
|
