fastanim_diff/
script.rs

1//! Checking and applying edit scripts (§5.7).
2
3use std::fmt;
4use std::hash::Hash;
5
6use crate::Op;
7
8/// Why an edit script is not a valid transformation of `a` into `b`.
9#[derive(Debug, Clone, PartialEq, Eq)]
10pub enum ScriptError {
11    /// An index of `a` is used more than once or out of range.
12    BadA(usize),
13    /// An index of `b` is used more than once, out of range, or out of order.
14    BadB(usize),
15    /// An index of `a` is not accounted for.
16    MissingA(usize),
17    /// An index of `b` is not produced.
18    MissingB(usize),
19    /// `Equal` ops are not in increasing `a` order.
20    EqualOutOfOrder(usize),
21    /// An `Equal` or `Move` pairs items whose keys differ.
22    KeyMismatch {
23        /// Index into `a`.
24        a: usize,
25        /// Index into `b`.
26        b: usize,
27    },
28}
29
30impl fmt::Display for ScriptError {
31    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
32        match self {
33            Self::BadA(i) => write!(f, "a[{i}] is used twice or out of range"),
34            Self::BadB(j) => write!(f, "b[{j}] is used twice, out of range or out of order"),
35            Self::MissingA(i) => write!(f, "a[{i}] is not accounted for"),
36            Self::MissingB(j) => write!(f, "b[{j}] is not produced"),
37            Self::EqualOutOfOrder(i) => write!(f, "Equal for a[{i}] is out of order"),
38            Self::KeyMismatch { a, b } => write!(f, "a[{a}] and b[{b}] have different keys"),
39        }
40    }
41}
42
43impl std::error::Error for ScriptError {}
44
45/// Checks the structure of a script for inputs of length `n` and `m`: every index of each
46/// input is used exactly once, `b` indices appear in increasing order, and `Equal` ops keep
47/// `a` order.
48pub fn validate(ops: &[Op], n: usize, m: usize) -> Result<(), ScriptError> {
49    let mut seen_a = vec![false; n];
50    let mut use_a = |i: usize| match seen_a.get_mut(i) {
51        Some(s) if !*s => {
52            *s = true;
53            Ok(())
54        }
55        _ => Err(ScriptError::BadA(i)),
56    };
57    let mut next_b = 0;
58    let mut use_b = |j: usize| {
59        if j == next_b && j < m {
60            next_b += 1;
61            Ok(())
62        } else {
63            Err(ScriptError::BadB(j))
64        }
65    };
66    let mut last_equal_a = None;
67    for op in ops {
68        match op {
69            Op::Equal { a, b } => {
70                if last_equal_a.is_some_and(|l| l >= *a) {
71                    return Err(ScriptError::EqualOutOfOrder(*a));
72                }
73                last_equal_a = Some(*a);
74                use_a(*a)?;
75                use_b(*b)?;
76            }
77            Op::Move { a, b } => {
78                use_a(*a)?;
79                use_b(*b)?;
80            }
81            Op::Delete { a } => use_a(*a)?,
82            Op::Insert { b } => use_b(*b)?,
83            Op::Replace { a, b } => {
84                a.clone().try_for_each(&mut use_a)?;
85                b.clone().try_for_each(&mut use_b)?;
86            }
87        }
88    }
89    if let Some(i) = seen_a.iter().position(|s| !s) {
90        return Err(ScriptError::MissingA(i));
91    }
92    if next_b < m {
93        return Err(ScriptError::MissingB(next_b));
94    }
95    Ok(())
96}
97
98/// Applies a script to `a`, producing the new sequence. Kept and moved items are taken from
99/// `a`; inserted and replacement items from `b`. Fails if the script is invalid or pairs
100/// items whose keys differ, so on success the result's keys equal `b`'s.
101pub fn apply<T: Clone, K: Eq + Hash>(
102    a: &[T],
103    b: &[T],
104    ops: &[Op],
105    key: impl Fn(&T) -> K,
106) -> Result<Vec<T>, ScriptError> {
107    validate(ops, a.len(), b.len())?;
108    let mut out = Vec::with_capacity(b.len());
109    for op in ops {
110        match op {
111            Op::Equal { a: i, b: j } | Op::Move { a: i, b: j } => {
112                if key(&a[*i]) != key(&b[*j]) {
113                    return Err(ScriptError::KeyMismatch { a: *i, b: *j });
114                }
115                out.push(a[*i].clone());
116            }
117            Op::Delete { .. } => {}
118            Op::Insert { b: j } => out.push(b[*j].clone()),
119            Op::Replace { b: r, .. } => out.extend_from_slice(&b[r.clone()]),
120        }
121    }
122    Ok(out)
123}
124
125/// Number of items not kept in place: every `a` and `b` item outside an `Equal` counts once.
126/// For a core script (`Equal`/`Delete`/`Insert` only) this is the edit distance `D`.
127pub fn edit_cost(ops: &[Op]) -> usize {
128    ops.iter()
129        .map(|op| match op {
130            Op::Equal { .. } => 0,
131            Op::Delete { .. } | Op::Insert { .. } => 1,
132            Op::Move { .. } => 2,
133            Op::Replace { a, b } => a.len() + b.len(),
134        })
135        .sum()
136}
fastanim_diff/script.rs

fastanim_diff/
script.rs
