identity_diff/
vec.rs

1// Copyright 2020-2021 IOTA Stiftung
2// SPDX-License-Identifier: Apache-2.0
3
4use crate::Diff;
5use serde::Deserialize;
6use serde::Serialize;
7use std::fmt::Debug;
8use std::fmt::Formatter;
9
10/// The Diff Type for `Vec`.
11#[derive(Clone, PartialEq, Serialize, Deserialize)]
12#[serde(transparent)]
13pub struct DiffVec<T: Diff>(pub Vec<InnerVec<T>>);
14
15/// The Inner value for the `DiffVec` type.  Is `untagged` by default for `serde`.
16#[derive(Clone, PartialEq, Serialize, Deserialize)]
17#[serde(untagged)]
18pub enum InnerVec<T: Diff> {
19  /// logs a change in a `Vec` type.
20  Change { index: usize, item: <T as Diff>::Type },
21  /// Logs a remove event in a `Vec` type.
22  Remove { count: usize },
23  /// logs an Add event in a `Vec` type.
24  Add(<T as Diff>::Type),
25}
26
27/// `Diff` trait implementation for `Vec<T>`
28impl<T> Diff for Vec<T>
29where
30  T: Clone + Debug + PartialEq + Diff + for<'de> Deserialize<'de> + Serialize,
31{
32  /// Corresponding Diff Type for `Vec<T>`
33  type Type = DiffVec<T>;
34
35  /// Compares two `Vec<T>` types; `self`, `other` and returns a `DiffVec<T>` type.
36  fn diff(&self, other: &Self) -> crate::Result<Self::Type> {
37    let (l_len, r_len) = (self.len(), other.len());
38    let max = usize::max(l_len, r_len);
39    let mut changes: Vec<InnerVec<T>> = vec![];
40
41    for index in 0..max {
42      match (self.get(index), other.get(index)) {
43        (None, None) => panic!("No data to match"),
44        (Some(x), Some(y)) if x == y => {}
45        (Some(x), Some(y)) => changes.push(InnerVec::Change {
46          index,
47          item: x.diff(y)?,
48        }),
49        (None, Some(x)) => changes.push(InnerVec::Add(x.clone().into_diff()?)),
50        (Some(_), None) => match changes.last_mut() {
51          Some(InnerVec::Remove { ref mut count }) => *count += 1,
52          _ => changes.push(InnerVec::Remove { count: 1 }),
53        },
54      }
55    }
56
57    Ok(DiffVec(changes))
58  }
59
60  /// Merges a `DiffVec<T>`; `diff` with `self`; a `Vec<T>` to create a new `Vec<T>`.
61  fn merge(&self, diff: Self::Type) -> crate::Result<Self> {
62    let mut vec: Self = self.clone();
63
64    for change in diff.0.into_iter() {
65      match change {
66        InnerVec::Add(d) => vec.push(<T>::from_diff(d)?),
67        InnerVec::Change { index, item } => vec[index] = self[index].merge(item)?,
68        InnerVec::Remove { count } => {
69          for _ in 0..count {
70            vec
71              .pop()
72              .ok_or_else(|| crate::Error::MergeError("Unable to pop value".into()))?;
73          }
74        }
75      }
76    }
77
78    Ok(vec)
79  }
80
81  /// Converts a `DiffVec<T>`; `diff` into a `Vec<T>`.
82  fn from_diff(diff: Self::Type) -> crate::Result<Self> {
83    let mut vec: Vec<T> = vec![];
84
85    for (_idx, elm) in diff.0.into_iter().enumerate() {
86      match elm {
87        InnerVec::Add(add) => vec.push(<T>::from_diff(add)?),
88        InnerVec::Change { index: _, item } => {
89          vec.push(<T>::from_diff(item)?);
90        }
91        _ => {}
92      }
93    }
94
95    Ok(vec)
96  }
97
98  /// Converts a `Vec<T>` into a `DiffVec<T>`
99  fn into_diff(self) -> crate::Result<Self::Type> {
100    let mut changes: Vec<InnerVec<T>> = vec![];
101    for inner in self {
102      changes.push(InnerVec::Add(inner.into_diff()?));
103    }
104    Ok(DiffVec(changes))
105  }
106}
107
108/// Debug trait for `DiffVec<T>`
109impl<T: Diff> Debug for DiffVec<T> {
110  fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
111    write!(f, "DiffVec ")?;
112    f.debug_list().entries(self.0.iter()).finish()
113  }
114}
115
116/// Debug trait for `InnerVec<T>`
117impl<T: Diff> Debug for InnerVec<T> {
118  fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
119    match &self {
120      Self::Change { index, item } => f
121        .debug_struct("Change")
122        .field("index", index)
123        .field("item", item)
124        .finish(),
125      Self::Remove { count } => f.debug_struct("Remove").field("count", count).finish(),
126      Self::Add(diff) => f.debug_tuple("Add").field(diff).finish(),
127    }
128  }
129}
130
131/// Default trait for `DiffVec<T>`
132impl<T: Diff> Default for DiffVec<T> {
133  fn default() -> Self {
134    DiffVec(Vec::new())
135  }
136}
137
138#[cfg(test)]
139mod tests {
140  use super::*;
141
142  #[test]
143  fn test_diff_same_val() {
144    let vec_a: Vec<i32> = vec![1, 2, 3];
145    let vec_b: Vec<i32> = vec![1, 2, 3];
146
147    assert_eq!(vec_a, vec_b);
148
149    let diff = vec_a.diff(&vec_b).unwrap();
150
151    assert_eq!(diff, DiffVec(vec![]));
152
153    let vec_c = vec_a.merge(diff).unwrap();
154
155    assert_eq!(vec_b, vec_c);
156
157    let diff = vec_b.diff(&vec_a).unwrap();
158
159    assert_eq!(diff, DiffVec(vec![]));
160
161    let vec_c = vec_b.merge(diff).unwrap();
162
163    assert_eq!(vec_a, vec_c);
164  }
165
166  #[test]
167  fn test_different_vals() {
168    let vec_a = vec![1, 2, 3, 4, 5];
169    let vec_b = vec![4, 2, 3, 4, 6];
170
171    let diff = vec_a.diff(&vec_b).unwrap();
172
173    assert_eq!(
174      diff,
175      DiffVec(vec![
176        InnerVec::Change {
177          index: 0,
178          item: 4i32.into_diff().unwrap(),
179        },
180        InnerVec::Change {
181          index: 4,
182          item: 6i32.into_diff().unwrap(),
183        }
184      ])
185    );
186
187    let vec_c = vec_a.merge(diff).unwrap();
188
189    assert_eq!(vec_b, vec_c);
190
191    let diff = vec_b.diff(&vec_a).unwrap();
192
193    assert_eq!(
194      diff,
195      DiffVec(vec![
196        InnerVec::Change {
197          index: 0,
198          item: 1i32.into_diff().unwrap(),
199        },
200        InnerVec::Change {
201          index: 4,
202          item: 5i32.into_diff().unwrap(),
203        }
204      ])
205    );
206
207    let vec_c = vec_b.merge(diff).unwrap();
208
209    assert_eq!(vec_a, vec_c);
210  }
211
212  #[test]
213  fn test_diff_lengths() {
214    let vec_a = vec![1, 2, 3, 4, 5, 6];
215    let vec_b = vec![1, 2, 3, 4, 6, 7, 8];
216
217    let diff = vec_a.diff(&vec_b).unwrap();
218
219    assert_eq!(
220      diff,
221      DiffVec(vec![
222        InnerVec::Change {
223          index: 4,
224          item: 6i32.into_diff().unwrap(),
225        },
226        InnerVec::Change {
227          index: 5,
228          item: 7i32.into_diff().unwrap(),
229        },
230        InnerVec::Add(8.into_diff().unwrap())
231      ])
232    );
233
234    let vec_c = vec_a.merge(diff).unwrap();
235
236    assert_eq!(vec_b, vec_c);
237
238    let diff = vec_b.diff(&vec_a).unwrap();
239
240    assert_eq!(
241      diff,
242      DiffVec(vec![
243        InnerVec::Change {
244          index: 4,
245          item: 5i32.into_diff().unwrap(),
246        },
247        InnerVec::Change {
248          index: 5,
249          item: 6i32.into_diff().unwrap(),
250        },
251        InnerVec::Remove { count: 1 },
252      ])
253    );
254
255    let vec_c = vec_b.merge(diff).unwrap();
256
257    assert_eq!(vec_a, vec_c);
258  }
259}
260
261#[test]
262fn test_into_from_diff() {
263  let vec_a = vec![1, 2, 3, 4, 5, 6];
264  let vec_b = vec![2, 3, 4, 3, 2, 1, 10, 20];
265
266  let diff = vec_a.diff(&vec_b).unwrap();
267
268  let vec = Vec::from_diff(diff).unwrap();
269
270  assert_eq!(vec, vec_b);
271}
identity_diff/vec.rs

identity_diff/
vec.rs
