Skip to main content

harn_vm/orchestration/records/
diff.rs

1//! Myers diff primitives, unified-diff rendering, and the `diff_run_records` comparator.
2
3use std::collections::{BTreeMap, BTreeSet};
4use std::path::Path;
5
6use super::action_graph::derive_run_observability;
7use super::types::{
8    RunDiffReport, RunObservabilityDiffRecord, RunRecord, RunStageDiffRecord, RunStageRecord,
9    ToolCallDiffRecord, ToolCallRecord,
10};
11
12/// Edit operation in a diff sequence.
13#[derive(Clone, Copy, PartialEq, Eq, Debug)]
14pub(crate) enum DiffOp {
15    Equal,
16    Delete,
17    Insert,
18}
19
20/// Compute the shortest edit script using Myers' O(nd) algorithm.
21/// Returns a sequence of (DiffOp, line_index_in_before_or_after).
22/// Time: O(nd) where d = edit distance. Space: O(d * n).
23pub(crate) fn myers_diff(a: &[&str], b: &[&str]) -> Vec<(DiffOp, usize)> {
24    let n = a.len() as isize;
25    let m = b.len() as isize;
26    if n == 0 && m == 0 {
27        return Vec::new();
28    }
29    if n == 0 {
30        return (0..m as usize).map(|j| (DiffOp::Insert, j)).collect();
31    }
32    if m == 0 {
33        return (0..n as usize).map(|i| (DiffOp::Delete, i)).collect();
34    }
35
36    let max_d = (n + m) as usize;
37    let offset = max_d as isize;
38    let v_size = 2 * max_d + 1;
39    let mut v = vec![0isize; v_size];
40    // trace[d] holds the `v` snapshot BEFORE step d ran — required for backtrack.
41    let mut trace: Vec<Vec<isize>> = Vec::new();
42
43    'outer: for d in 0..=max_d as isize {
44        trace.push(v.clone());
45        let mut new_v = v.clone();
46        for k in (-d..=d).step_by(2) {
47            let ki = (k + offset) as usize;
48            let mut x = if k == -d || (k != d && v[ki - 1] < v[ki + 1]) {
49                v[ki + 1]
50            } else {
51                v[ki - 1] + 1
52            };
53            let mut y = x - k;
54            while x < n && y < m && a[x as usize] == b[y as usize] {
55                x += 1;
56                y += 1;
57            }
58            new_v[ki] = x;
59            if x >= n && y >= m {
60                let _ = new_v;
61                break 'outer;
62            }
63        }
64        v = new_v;
65    }
66
67    let mut ops: Vec<(DiffOp, usize)> = Vec::new();
68    let mut x = n;
69    let mut y = m;
70    for d in (1..trace.len() as isize).rev() {
71        let k = x - y;
72        let v_prev = &trace[d as usize];
73        let prev_k = if k == -d
74            || (k != d && v_prev[(k - 1 + offset) as usize] < v_prev[(k + 1 + offset) as usize])
75        {
76            k + 1
77        } else {
78            k - 1
79        };
80        let prev_x = v_prev[(prev_k + offset) as usize];
81        let prev_y = prev_x - prev_k;
82
83        while x > prev_x && y > prev_y {
84            x -= 1;
85            y -= 1;
86            ops.push((DiffOp::Equal, x as usize));
87        }
88        if prev_k < k {
89            x -= 1;
90            ops.push((DiffOp::Delete, x as usize));
91        } else {
92            y -= 1;
93            ops.push((DiffOp::Insert, y as usize));
94        }
95    }
96    while x > 0 && y > 0 {
97        x -= 1;
98        y -= 1;
99        ops.push((DiffOp::Equal, x as usize));
100    }
101    ops.reverse();
102    ops
103}
104
105pub fn render_unified_diff(path: Option<&str>, before: &str, after: &str) -> String {
106    let before_lines: Vec<&str> = before.lines().collect();
107    let after_lines: Vec<&str> = after.lines().collect();
108    let ops = myers_diff(&before_lines, &after_lines);
109
110    let mut diff = String::new();
111    let file = path.unwrap_or("artifact");
112    diff.push_str(&format!("--- a/{file}\n+++ b/{file}\n"));
113    for &(op, idx) in &ops {
114        match op {
115            DiffOp::Equal => diff.push_str(&format!(" {}\n", before_lines[idx])),
116            DiffOp::Delete => diff.push_str(&format!("-{}\n", before_lines[idx])),
117            DiffOp::Insert => diff.push_str(&format!("+{}\n", after_lines[idx])),
118        }
119    }
120    diff
121}
122
123pub fn diff_run_records(left: &RunRecord, right: &RunRecord) -> RunDiffReport {
124    let mut stage_diffs = Vec::new();
125    let mut all_node_ids = BTreeSet::new();
126    let left_by_id: BTreeMap<&str, &RunStageRecord> = left
127        .stages
128        .iter()
129        .map(|s| (s.node_id.as_str(), s))
130        .collect();
131    let right_by_id: BTreeMap<&str, &RunStageRecord> = right
132        .stages
133        .iter()
134        .map(|s| (s.node_id.as_str(), s))
135        .collect();
136    all_node_ids.extend(left_by_id.keys().copied());
137    all_node_ids.extend(right_by_id.keys().copied());
138
139    for node_id in all_node_ids {
140        let left_stage = left_by_id.get(node_id).copied();
141        let right_stage = right_by_id.get(node_id).copied();
142        match (left_stage, right_stage) {
143            (Some(_), None) => stage_diffs.push(RunStageDiffRecord {
144                node_id: node_id.to_string(),
145                change: "removed".to_string(),
146                details: vec!["stage missing from right run".to_string()],
147            }),
148            (None, Some(_)) => stage_diffs.push(RunStageDiffRecord {
149                node_id: node_id.to_string(),
150                change: "added".to_string(),
151                details: vec!["stage missing from left run".to_string()],
152            }),
153            (Some(left_stage), Some(right_stage)) => {
154                let mut details = Vec::new();
155                if left_stage.status != right_stage.status {
156                    details.push(format!(
157                        "status: {} -> {}",
158                        left_stage.status, right_stage.status
159                    ));
160                }
161                if left_stage.outcome != right_stage.outcome {
162                    details.push(format!(
163                        "outcome: {} -> {}",
164                        left_stage.outcome, right_stage.outcome
165                    ));
166                }
167                if left_stage.branch != right_stage.branch {
168                    details.push(format!(
169                        "branch: {:?} -> {:?}",
170                        left_stage.branch, right_stage.branch
171                    ));
172                }
173                if left_stage.produced_artifact_ids.len() != right_stage.produced_artifact_ids.len()
174                {
175                    details.push(format!(
176                        "produced_artifacts: {} -> {}",
177                        left_stage.produced_artifact_ids.len(),
178                        right_stage.produced_artifact_ids.len()
179                    ));
180                }
181                if left_stage.artifacts.len() != right_stage.artifacts.len() {
182                    details.push(format!(
183                        "artifact_records: {} -> {}",
184                        left_stage.artifacts.len(),
185                        right_stage.artifacts.len()
186                    ));
187                }
188                if !details.is_empty() {
189                    stage_diffs.push(RunStageDiffRecord {
190                        node_id: node_id.to_string(),
191                        change: "changed".to_string(),
192                        details,
193                    });
194                }
195            }
196            (None, None) => {}
197        }
198    }
199
200    let mut tool_diffs = Vec::new();
201    let left_tools: std::collections::BTreeMap<(String, String), &ToolCallRecord> = left
202        .tool_recordings
203        .iter()
204        .map(|r| ((r.tool_name.clone(), r.args_hash.clone()), r))
205        .collect();
206    let right_tools: std::collections::BTreeMap<(String, String), &ToolCallRecord> = right
207        .tool_recordings
208        .iter()
209        .map(|r| ((r.tool_name.clone(), r.args_hash.clone()), r))
210        .collect();
211    let all_tool_keys: std::collections::BTreeSet<_> = left_tools
212        .keys()
213        .chain(right_tools.keys())
214        .cloned()
215        .collect();
216    for key in &all_tool_keys {
217        let l = left_tools.get(key);
218        let r = right_tools.get(key);
219        let result_changed = match (l, r) {
220            (Some(a), Some(b)) => a.result != b.result,
221            _ => true,
222        };
223        if result_changed {
224            tool_diffs.push(ToolCallDiffRecord {
225                tool_name: key.0.clone(),
226                args_hash: key.1.clone(),
227                result_changed,
228                left_result: l.map(|t| t.result.clone()),
229                right_result: r.map(|t| t.result.clone()),
230            });
231        }
232    }
233
234    let left_observability = left.observability.clone().unwrap_or_else(|| {
235        derive_run_observability(left, left.persisted_path.as_deref().map(Path::new))
236    });
237    let right_observability = right.observability.clone().unwrap_or_else(|| {
238        derive_run_observability(right, right.persisted_path.as_deref().map(Path::new))
239    });
240    let mut observability_diffs = Vec::new();
241
242    let left_workers = left_observability
243        .worker_lineage
244        .iter()
245        .map(|worker| {
246            (
247                worker.worker_id.clone(),
248                (
249                    worker.status.clone(),
250                    worker.run_id.clone(),
251                    worker.run_path.clone(),
252                ),
253            )
254        })
255        .collect::<BTreeMap<_, _>>();
256    let right_workers = right_observability
257        .worker_lineage
258        .iter()
259        .map(|worker| {
260            (
261                worker.worker_id.clone(),
262                (
263                    worker.status.clone(),
264                    worker.run_id.clone(),
265                    worker.run_path.clone(),
266                ),
267            )
268        })
269        .collect::<BTreeMap<_, _>>();
270    let worker_ids = left_workers
271        .keys()
272        .chain(right_workers.keys())
273        .cloned()
274        .collect::<BTreeSet<_>>();
275    for worker_id in worker_ids {
276        match (left_workers.get(&worker_id), right_workers.get(&worker_id)) {
277            (Some(_), None) => observability_diffs.push(RunObservabilityDiffRecord {
278                section: "worker_lineage".to_string(),
279                label: worker_id,
280                details: vec!["worker missing from right run".to_string()],
281            }),
282            (None, Some(_)) => observability_diffs.push(RunObservabilityDiffRecord {
283                section: "worker_lineage".to_string(),
284                label: worker_id,
285                details: vec!["worker missing from left run".to_string()],
286            }),
287            (Some(left_worker), Some(right_worker)) if left_worker != right_worker => {
288                let mut details = Vec::new();
289                if left_worker.0 != right_worker.0 {
290                    details.push(format!("status: {} -> {}", left_worker.0, right_worker.0));
291                }
292                if left_worker.1 != right_worker.1 {
293                    details.push(format!(
294                        "run_id: {:?} -> {:?}",
295                        left_worker.1, right_worker.1
296                    ));
297                }
298                if left_worker.2 != right_worker.2 {
299                    details.push(format!(
300                        "run_path: {:?} -> {:?}",
301                        left_worker.2, right_worker.2
302                    ));
303                }
304                observability_diffs.push(RunObservabilityDiffRecord {
305                    section: "worker_lineage".to_string(),
306                    label: worker_id,
307                    details,
308                });
309            }
310            _ => {}
311        }
312    }
313
314    let left_rounds = left_observability
315        .planner_rounds
316        .iter()
317        .map(|round| (round.stage_id.clone(), round))
318        .collect::<BTreeMap<_, _>>();
319    let right_rounds = right_observability
320        .planner_rounds
321        .iter()
322        .map(|round| (round.stage_id.clone(), round))
323        .collect::<BTreeMap<_, _>>();
324    let round_ids = left_rounds
325        .keys()
326        .chain(right_rounds.keys())
327        .cloned()
328        .collect::<BTreeSet<_>>();
329    for stage_id in round_ids {
330        match (left_rounds.get(&stage_id), right_rounds.get(&stage_id)) {
331            (Some(_), None) => observability_diffs.push(RunObservabilityDiffRecord {
332                section: "planner_rounds".to_string(),
333                label: stage_id,
334                details: vec!["planner summary missing from right run".to_string()],
335            }),
336            (None, Some(_)) => observability_diffs.push(RunObservabilityDiffRecord {
337                section: "planner_rounds".to_string(),
338                label: stage_id,
339                details: vec!["planner summary missing from left run".to_string()],
340            }),
341            (Some(left_round), Some(right_round)) => {
342                let mut details = Vec::new();
343                if left_round.iteration_count != right_round.iteration_count {
344                    details.push(format!(
345                        "iterations: {} -> {}",
346                        left_round.iteration_count, right_round.iteration_count
347                    ));
348                }
349                if left_round.tool_execution_count != right_round.tool_execution_count {
350                    details.push(format!(
351                        "tool_executions: {} -> {}",
352                        left_round.tool_execution_count, right_round.tool_execution_count
353                    ));
354                }
355                if left_round.native_text_tool_fallback_count
356                    != right_round.native_text_tool_fallback_count
357                {
358                    details.push(format!(
359                        "native_text_tool_fallbacks: {} -> {}",
360                        left_round.native_text_tool_fallback_count,
361                        right_round.native_text_tool_fallback_count
362                    ));
363                }
364                if left_round.native_text_tool_fallback_rejection_count
365                    != right_round.native_text_tool_fallback_rejection_count
366                {
367                    details.push(format!(
368                        "native_text_tool_fallback_rejections: {} -> {}",
369                        left_round.native_text_tool_fallback_rejection_count,
370                        right_round.native_text_tool_fallback_rejection_count
371                    ));
372                }
373                if left_round.empty_completion_retry_count
374                    != right_round.empty_completion_retry_count
375                {
376                    details.push(format!(
377                        "empty_completion_retries: {} -> {}",
378                        left_round.empty_completion_retry_count,
379                        right_round.empty_completion_retry_count
380                    ));
381                }
382                if left_round.research_facts != right_round.research_facts {
383                    details.push(format!(
384                        "research_facts: {:?} -> {:?}",
385                        left_round.research_facts, right_round.research_facts
386                    ));
387                }
388                let left_deliverables = left_round
389                    .task_ledger
390                    .as_ref()
391                    .map(|ledger| {
392                        ledger
393                            .deliverables
394                            .iter()
395                            .map(|item| format!("{}:{}", item.id, item.status))
396                            .collect::<Vec<_>>()
397                    })
398                    .unwrap_or_default();
399                let right_deliverables = right_round
400                    .task_ledger
401                    .as_ref()
402                    .map(|ledger| {
403                        ledger
404                            .deliverables
405                            .iter()
406                            .map(|item| format!("{}:{}", item.id, item.status))
407                            .collect::<Vec<_>>()
408                    })
409                    .unwrap_or_default();
410                if left_deliverables != right_deliverables {
411                    details.push(format!(
412                        "deliverables: {:?} -> {:?}",
413                        left_deliverables, right_deliverables
414                    ));
415                }
416                if left_round.successful_tools != right_round.successful_tools {
417                    details.push(format!(
418                        "successful_tools: {:?} -> {:?}",
419                        left_round.successful_tools, right_round.successful_tools
420                    ));
421                }
422                if !details.is_empty() {
423                    observability_diffs.push(RunObservabilityDiffRecord {
424                        section: "planner_rounds".to_string(),
425                        label: left_round.node_id.clone(),
426                        details,
427                    });
428                }
429            }
430            _ => {}
431        }
432    }
433
434    let left_pointers = left_observability
435        .transcript_pointers
436        .iter()
437        .map(|pointer| {
438            (
439                pointer.id.clone(),
440                (
441                    pointer.available,
442                    pointer.path.clone(),
443                    pointer.location.clone(),
444                ),
445            )
446        })
447        .collect::<BTreeMap<_, _>>();
448    let right_pointers = right_observability
449        .transcript_pointers
450        .iter()
451        .map(|pointer| {
452            (
453                pointer.id.clone(),
454                (
455                    pointer.available,
456                    pointer.path.clone(),
457                    pointer.location.clone(),
458                ),
459            )
460        })
461        .collect::<BTreeMap<_, _>>();
462    let pointer_ids = left_pointers
463        .keys()
464        .chain(right_pointers.keys())
465        .cloned()
466        .collect::<BTreeSet<_>>();
467    for pointer_id in pointer_ids {
468        match (
469            left_pointers.get(&pointer_id),
470            right_pointers.get(&pointer_id),
471        ) {
472            (Some(_), None) => observability_diffs.push(RunObservabilityDiffRecord {
473                section: "transcript_pointers".to_string(),
474                label: pointer_id,
475                details: vec!["pointer missing from right run".to_string()],
476            }),
477            (None, Some(_)) => observability_diffs.push(RunObservabilityDiffRecord {
478                section: "transcript_pointers".to_string(),
479                label: pointer_id,
480                details: vec!["pointer missing from left run".to_string()],
481            }),
482            (Some(left_pointer), Some(right_pointer)) if left_pointer != right_pointer => {
483                observability_diffs.push(RunObservabilityDiffRecord {
484                    section: "transcript_pointers".to_string(),
485                    label: pointer_id,
486                    details: vec![format!(
487                        "pointer: {:?} -> {:?}",
488                        left_pointer, right_pointer
489                    )],
490                });
491            }
492            _ => {}
493        }
494    }
495
496    let left_compactions = left_observability
497        .compaction_events
498        .iter()
499        .map(|event| {
500            (
501                event.id.clone(),
502                (
503                    event.strategy.clone(),
504                    event.archived_messages,
505                    event.snapshot_asset_id.clone(),
506                    event.available,
507                ),
508            )
509        })
510        .collect::<BTreeMap<_, _>>();
511    let right_compactions = right_observability
512        .compaction_events
513        .iter()
514        .map(|event| {
515            (
516                event.id.clone(),
517                (
518                    event.strategy.clone(),
519                    event.archived_messages,
520                    event.snapshot_asset_id.clone(),
521                    event.available,
522                ),
523            )
524        })
525        .collect::<BTreeMap<_, _>>();
526    let compaction_ids = left_compactions
527        .keys()
528        .chain(right_compactions.keys())
529        .cloned()
530        .collect::<BTreeSet<_>>();
531    for compaction_id in compaction_ids {
532        match (
533            left_compactions.get(&compaction_id),
534            right_compactions.get(&compaction_id),
535        ) {
536            (Some(_), None) => observability_diffs.push(RunObservabilityDiffRecord {
537                section: "compaction_events".to_string(),
538                label: compaction_id,
539                details: vec!["compaction event missing from right run".to_string()],
540            }),
541            (None, Some(_)) => observability_diffs.push(RunObservabilityDiffRecord {
542                section: "compaction_events".to_string(),
543                label: compaction_id,
544                details: vec!["compaction event missing from left run".to_string()],
545            }),
546            (Some(left_event), Some(right_event)) if left_event != right_event => {
547                observability_diffs.push(RunObservabilityDiffRecord {
548                    section: "compaction_events".to_string(),
549                    label: compaction_id,
550                    details: vec![format!("event: {:?} -> {:?}", left_event, right_event)],
551                });
552            }
553            _ => {}
554        }
555    }
556
557    let left_daemons = left_observability
558        .daemon_events
559        .iter()
560        .map(|event| {
561            (
562                (event.daemon_id.clone(), event.kind, event.timestamp.clone()),
563                (
564                    event.name.clone(),
565                    event.persist_path.clone(),
566                    event.payload_summary.clone(),
567                ),
568            )
569        })
570        .collect::<BTreeMap<_, _>>();
571    let right_daemons = right_observability
572        .daemon_events
573        .iter()
574        .map(|event| {
575            (
576                (event.daemon_id.clone(), event.kind, event.timestamp.clone()),
577                (
578                    event.name.clone(),
579                    event.persist_path.clone(),
580                    event.payload_summary.clone(),
581                ),
582            )
583        })
584        .collect::<BTreeMap<_, _>>();
585    let daemon_keys = left_daemons
586        .keys()
587        .chain(right_daemons.keys())
588        .cloned()
589        .collect::<BTreeSet<_>>();
590    for daemon_key in daemon_keys {
591        let label = format!("{}:{:?}:{}", daemon_key.0, daemon_key.1, daemon_key.2);
592        match (
593            left_daemons.get(&daemon_key),
594            right_daemons.get(&daemon_key),
595        ) {
596            (Some(_), None) => observability_diffs.push(RunObservabilityDiffRecord {
597                section: "daemon_events".to_string(),
598                label,
599                details: vec!["daemon event missing from right run".to_string()],
600            }),
601            (None, Some(_)) => observability_diffs.push(RunObservabilityDiffRecord {
602                section: "daemon_events".to_string(),
603                label,
604                details: vec!["daemon event missing from left run".to_string()],
605            }),
606            (Some(left_event), Some(right_event)) if left_event != right_event => {
607                observability_diffs.push(RunObservabilityDiffRecord {
608                    section: "daemon_events".to_string(),
609                    label,
610                    details: vec![format!("event: {:?} -> {:?}", left_event, right_event)],
611                });
612            }
613            _ => {}
614        }
615    }
616
617    let left_verification = left_observability
618        .verification_outcomes
619        .iter()
620        .map(|item| (item.stage_id.clone(), item))
621        .collect::<BTreeMap<_, _>>();
622    let right_verification = right_observability
623        .verification_outcomes
624        .iter()
625        .map(|item| (item.stage_id.clone(), item))
626        .collect::<BTreeMap<_, _>>();
627    let verification_ids = left_verification
628        .keys()
629        .chain(right_verification.keys())
630        .cloned()
631        .collect::<BTreeSet<_>>();
632    for stage_id in verification_ids {
633        match (
634            left_verification.get(&stage_id),
635            right_verification.get(&stage_id),
636        ) {
637            (Some(_), None) => observability_diffs.push(RunObservabilityDiffRecord {
638                section: "verification".to_string(),
639                label: stage_id,
640                details: vec!["verification missing from right run".to_string()],
641            }),
642            (None, Some(_)) => observability_diffs.push(RunObservabilityDiffRecord {
643                section: "verification".to_string(),
644                label: stage_id,
645                details: vec!["verification missing from left run".to_string()],
646            }),
647            (Some(left_item), Some(right_item)) if left_item != right_item => {
648                let mut details = Vec::new();
649                if left_item.passed != right_item.passed {
650                    details.push(format!(
651                        "passed: {:?} -> {:?}",
652                        left_item.passed, right_item.passed
653                    ));
654                }
655                if left_item.summary != right_item.summary {
656                    details.push(format!(
657                        "summary: {:?} -> {:?}",
658                        left_item.summary, right_item.summary
659                    ));
660                }
661                observability_diffs.push(RunObservabilityDiffRecord {
662                    section: "verification".to_string(),
663                    label: left_item.node_id.clone(),
664                    details,
665                });
666            }
667            _ => {}
668        }
669    }
670
671    let left_graph = (
672        left_observability.action_graph_nodes.len(),
673        left_observability.action_graph_edges.len(),
674    );
675    let right_graph = (
676        right_observability.action_graph_nodes.len(),
677        right_observability.action_graph_edges.len(),
678    );
679    if left_graph != right_graph {
680        observability_diffs.push(RunObservabilityDiffRecord {
681            section: "action_graph".to_string(),
682            label: "shape".to_string(),
683            details: vec![format!(
684                "nodes/edges: {}/{} -> {}/{}",
685                left_graph.0, left_graph.1, right_graph.0, right_graph.1
686            )],
687        });
688    }
689
690    let status_changed = left.status != right.status;
691    let identical = !status_changed
692        && stage_diffs.is_empty()
693        && tool_diffs.is_empty()
694        && observability_diffs.is_empty()
695        && left.transitions.len() == right.transitions.len()
696        && left.artifacts.len() == right.artifacts.len()
697        && left.checkpoints.len() == right.checkpoints.len();
698
699    RunDiffReport {
700        left_run_id: left.id.clone(),
701        right_run_id: right.id.clone(),
702        identical,
703        status_changed,
704        left_status: left.status.clone(),
705        right_status: right.status.clone(),
706        stage_diffs,
707        tool_diffs,
708        observability_diffs,
709        transition_count_delta: right.transitions.len() as isize - left.transitions.len() as isize,
710        artifact_count_delta: right.artifacts.len() as isize - left.artifacts.len() as isize,
711        checkpoint_count_delta: right.checkpoints.len() as isize - left.checkpoints.len() as isize,
712    }
713}