kyte/
compose.rs

1use std::fmt::Debug;
2use std::mem::take;
3
4use arbitrary::Arbitrary;
5
6use super::op::split;
7use super::ops::{Delete, Insert, Retain};
8use super::{Delta, Op, Seq};
9
10/// Implemented by types that can apply a series of operations in sequence.
11///
12/// The table below contains links to the implementation notes of [`Compose`]
13/// for each pair of [`Op`]. The rows represent Alice's operations (i.e. the
14/// first) and the columns represent Bob's operations (i.e. the second), e.g.
15/// bottom left means Alice's delete followed by Bob's insert.
16///
17/// | ↱      | Insert    | Retain    | Delete    |
18/// |:-------|:----------|:----------|:----------|
19/// | Insert | [Impl][1] | [Impl][4] | [Impl][7] |
20/// | Retain | [Impl][2] | [Impl][5] | [Impl][8] |
21/// | Delete | [Impl][3] | [Impl][6] | [Impl][9] |
22///
23/// [1]: #impl-Compose<%26mut+Insert<T,+A>>-for-U
24/// [2]: #impl-Compose<%26mut+Insert<T,+A>>-for-U
25/// [3]: #impl-Compose<%26mut+Insert<T,+A>>-for-U
26/// [4]: #impl-Compose<%26mut+Retain<A>>-for-%26mut+Insert<T,+A>
27/// [5]: #impl-Compose<%26mut+Retain<A>>-for-%26mut+Retain<A>
28/// [6]: #impl-Compose<%26mut+Retain<A>>-for-%26mut+Delete
29/// [7]: #impl-Compose<%26mut+Delete>-for-%26mut+Insert<T,+A>
30/// [8]: #impl-Compose<%26mut+Delete>-for-%26mut+Retain<A>
31/// [9]: #impl-Compose<%26mut+Delete>-for-%26mut+Delete
32pub trait Compose<Rhs> {
33    /// Output type that applying a series of operations to this type produces.
34    type Output;
35
36    /// Applies the given series of operations to the receiver and returns the
37    /// result.
38    fn compose(self, rhs: Rhs) -> Self::Output;
39}
40
41#[doc(hidden)]
42#[derive(Arbitrary, Clone, Debug, Default, PartialEq, Eq)]
43pub struct LastWriteWins<T>(pub T);
44
45impl<T> Compose<LastWriteWins<T>> for LastWriteWins<T> {
46    type Output = LastWriteWins<T>;
47
48    fn compose(self, rhs: LastWriteWins<T>) -> Self::Output {
49        rhs
50    }
51}
52
53impl Compose<()> for () {
54    type Output = ();
55
56    fn compose(self, _rhs: ()) -> Self::Output {
57        self
58    }
59}
60
61impl<T> Compose<Option<T>> for Option<T>
62where
63    T: Compose<T, Output = T>,
64{
65    type Output = Option<T>;
66
67    fn compose(self, rhs: Option<T>) -> Self::Output {
68        match (self, rhs) {
69            (Some(lhs), Some(rhs)) => Some(lhs.compose(rhs)),
70            (Some(lhs), None) => Some(lhs),
71            (None, Some(rhs)) => Some(rhs),
72            (None, None) => None,
73        }
74    }
75}
76
77impl<T, A> Compose<&mut Retain<A>> for &mut Insert<T, A>
78where
79    T: Seq,
80    A: Clone + Compose<A, Output = A>,
81{
82    type Output = Insert<T, A>;
83
84    fn compose(self, rhs: &mut Retain<A>) -> Self::Output {
85        let (lhs, rhs) = split(self, rhs);
86
87        Insert {
88            insert: lhs.insert,
89            attributes: lhs.attributes.compose(rhs.attributes),
90        }
91    }
92}
93
94impl<T, A> Compose<&mut Delete> for &mut Insert<T, A>
95where
96    T: Seq,
97    A: Clone,
98{
99    type Output = Delete;
100
101    fn compose(self, rhs: &mut Delete) -> Self::Output {
102        let (_, _) = split(self, rhs);
103
104        Default::default()
105    }
106}
107
108impl<A> Compose<&mut Retain<A>> for &mut Retain<A>
109where
110    A: Clone + Compose<A, Output = A>,
111{
112    type Output = Retain<A>;
113
114    fn compose(self, rhs: &mut Retain<A>) -> Self::Output {
115        let (lhs, rhs) = split(self, rhs);
116
117        Retain {
118            retain: lhs.retain,
119            attributes: lhs.attributes.compose(rhs.attributes),
120        }
121    }
122}
123
124impl<A> Compose<&mut Delete> for &mut Retain<A>
125where
126    A: Clone,
127{
128    type Output = Delete;
129
130    fn compose(self, rhs: &mut Delete) -> Self::Output {
131        let (_lhs, rhs) = split(self, rhs);
132
133        rhs.into()
134    }
135}
136
137impl<A, T, U> Compose<&mut Insert<T, A>> for U
138where
139    T: Default,
140    A: Default,
141{
142    type Output = Insert<T, A>;
143
144    fn compose(self, rhs: &mut Insert<T, A>) -> Self::Output {
145        take(rhs)
146    }
147}
148
149impl<A> Compose<&mut Retain<A>> for &mut Delete {
150    type Output = Delete;
151
152    fn compose(self, _rhs: &mut Retain<A>) -> Self::Output {
153        take(self)
154    }
155}
156
157impl Compose<&mut Delete> for &mut Delete {
158    type Output = Delete;
159
160    fn compose(self, _rhs: &mut Delete) -> Self::Output {
161        take(self)
162    }
163}
164
165impl<T, A> Compose<&mut Op<T, A>> for &mut Op<T, A>
166where
167    T: Default + Clone + Seq + Extend<T>,
168    A: Default + Clone + PartialEq + Compose<A, Output = A>,
169{
170    type Output = Op<T, A>;
171
172    fn compose(self, rhs: &mut Op<T, A>) -> Self::Output {
173        match self {
174            Op::Insert(lhs) => match rhs {
175                Op::Insert(rhs) => lhs.compose(rhs).into(),
176                Op::Retain(rhs) => lhs.compose(rhs).into(),
177                Op::Delete(rhs) => lhs.compose(rhs).into(),
178            },
179            Op::Retain(lhs) => match rhs {
180                Op::Insert(rhs) => lhs.compose(rhs).into(),
181                Op::Retain(rhs) => lhs.compose(rhs).into(),
182                Op::Delete(rhs) => lhs.compose(rhs).into(),
183            },
184            Op::Delete(lhs) => match rhs {
185                Op::Insert(rhs) => lhs.compose(rhs).into(),
186                Op::Retain(rhs) => lhs.compose(rhs).into(),
187                Op::Delete(rhs) => lhs.compose(rhs).into(),
188            },
189        }
190    }
191}
192
193impl<T, A> Compose<Delta<T, A>> for Delta<T, A>
194where
195    T: Default + Clone + Seq + Extend<T> + Debug,
196    A: Default + Clone + PartialEq + Debug + Compose<A, Output = A>,
197{
198    type Output = Self;
199
200    fn compose(self, rhs: Delta<T, A>) -> Self {
201        let mut self_iter = self.into_iter();
202        let mut other_iter = rhs.into_iter();
203
204        let mut result = Delta::new();
205
206        result.extend(self_iter.zip_mut(&mut other_iter, |a, b| a.compose(b)));
207        result.extend(self_iter.chain(other_iter));
208
209        result.chop()
210    }
211}
212
213#[cfg(test)]
214mod tests {
215    use super::{Compose, Delta};
216
217    #[derive(Clone, Debug, Default, PartialEq, Eq)]
218    pub struct Attributes {
219        bold: Option<bool>,
220    }
221
222    impl Attributes {
223        pub fn bold() -> Attributes {
224            Attributes { bold: Some(true) }
225        }
226    }
227
228    impl Compose<Attributes> for Attributes {
229        type Output = Attributes;
230
231        fn compose(self, rhs: Attributes) -> Self::Output {
232            Attributes {
233                bold: rhs.bold.or(self.bold),
234            }
235        }
236    }
237
238    #[test]
239    fn test_insert_insert() {
240        let a = Delta::new().insert("A".to_owned(), ());
241        let b = Delta::new().insert("B".to_owned(), ());
242
243        assert_eq!(a.compose(b), Delta::new().insert("BA".to_owned(), ()));
244    }
245
246    #[test]
247    fn test_insert_retain() {
248        let a = Delta::new().insert("A".to_owned(), ());
249        let b = Delta::new().retain(1, ());
250
251        assert_eq!(a.compose(b), Delta::new().insert("A".to_owned(), ()));
252    }
253
254    #[test]
255    fn test_insert_delete() {
256        let a = Delta::new().insert("A".to_owned(), ());
257        let b = Delta::new().delete(1);
258
259        assert_eq!(a.compose(b), Delta::new());
260    }
261
262    #[test]
263    fn test_retain_insert() {
264        let a = Delta::new().retain(1, Attributes::bold());
265        let b = Delta::new().insert("A".to_owned(), None);
266
267        assert_eq!(
268            a.compose(b),
269            Delta::new()
270                .insert("A".to_owned(), None)
271                .retain(1, Attributes::bold())
272        );
273    }
274
275    #[test]
276    fn test_retain_retain() {
277        let a = Delta::<String, _>::new().retain(1, None);
278        let b = Delta::new().retain(2, Attributes::bold());
279
280        assert_eq!(a.compose(b), Delta::new().retain(2, Attributes::bold()));
281    }
282
283    #[test]
284    fn test_retain_delete() {
285        let a = Delta::<String, _>::new().retain(1, ());
286        let b = Delta::new().delete(1);
287
288        assert_eq!(a.compose(b), Delta::new().delete(1));
289    }
290
291    #[test]
292    fn test_delete_insert() {
293        let a = Delta::new().delete(1);
294        let b = Delta::new().insert("B".to_owned(), ());
295
296        assert_eq!(
297            a.compose(b),
298            Delta::new().insert("B".to_owned(), ()).delete(1)
299        );
300    }
301
302    #[test]
303    fn test_delete_retain() {
304        let a = Delta::<String, _>::new().delete(1);
305        let b = Delta::new().retain(1, Attributes::bold());
306
307        assert_eq!(
308            a.compose(b),
309            Delta::new().delete(1).retain(1, Attributes::bold())
310        );
311    }
312
313    #[test]
314    fn test_delete_delete() {
315        let a = Delta::<String, ()>::new().delete(1);
316        let b = Delta::new().delete(2);
317
318        assert_eq!(a.compose(b), Delta::new().delete(3));
319    }
320
321    #[test]
322    fn test_insert_mid() {
323        let a = Delta::new().insert("Hello".to_owned(), ());
324        let b = Delta::new().retain(3, ()).insert("X".to_owned(), ());
325
326        assert_eq!(a.compose(b), Delta::new().insert("HelXlo".to_owned(), ()));
327    }
328
329    #[test]
330    fn test_delete_all() {
331        let a = Delta::new().retain(4, ()).insert("Hello".to_owned(), ());
332        let b = Delta::new().delete(9);
333
334        assert_eq!(a.compose(b), Delta::new().delete(4));
335    }
336
337    #[test]
338    fn test_over_retain() {
339        let a = Delta::<_, ()>::new().insert("Hello".to_owned(), None);
340        let b = Delta::new().retain(10, None);
341
342        assert_eq!(a.compose(b), Delta::new().insert("Hello".to_owned(), None));
343    }
344
345    #[test]
346    fn test_retain_start_optimization() {
347        let a = Delta::new()
348            .insert("A".to_owned(), Attributes::bold())
349            .insert("B".to_owned(), None)
350            .insert("C".to_owned(), Attributes::bold())
351            .delete(1);
352        let b = Delta::new().retain(3, None).insert("D".to_owned(), None);
353
354        assert_eq!(
355            a.compose(b),
356            Delta::new()
357                .insert("A".to_owned(), Attributes::bold())
358                .insert("B".to_owned(), None)
359                .insert("C".to_owned(), Attributes::bold())
360                .insert("D".to_owned(), None)
361                .delete(1)
362        );
363    }
364
365    #[test]
366    fn test_retain_start_optimization_split() {
367        let a = Delta::new()
368            .insert("A".to_owned(), Attributes::bold())
369            .insert("B".to_owned(), None)
370            .insert("C".to_owned(), Attributes::bold())
371            .retain(5, None)
372            .delete(1);
373        let b = Delta::new().retain(4, None).insert("D".to_owned(), None);
374
375        assert_eq!(
376            a.compose(b),
377            Delta::new()
378                .insert("A".to_owned(), Attributes::bold())
379                .insert("B".to_owned(), None)
380                .insert("C".to_owned(), Attributes::bold())
381                .retain(1, None)
382                .insert("D".to_owned(), None)
383                .retain(4, None)
384                .delete(1)
385        );
386    }
387
388    #[test]
389    fn test_retain_end_optimization() {
390        let a = Delta::new()
391            .insert("A".to_owned(), Attributes::bold())
392            .insert("B".to_owned(), None)
393            .insert("C".to_owned(), Attributes::bold());
394        let b = Delta::new().delete(1);
395
396        assert_eq!(
397            a.compose(b),
398            Delta::new()
399                .insert("B".to_owned(), None)
400                .insert("C".to_owned(), Attributes::bold())
401        );
402    }
403
404    #[test]
405    fn test_retain_end_optimization_join() {
406        let a = Delta::new()
407            .insert("A".to_owned(), Attributes::bold())
408            .insert("B".to_owned(), None)
409            .insert("C".to_owned(), Attributes::bold())
410            .insert("D".to_owned(), None)
411            .insert("E".to_owned(), Attributes::bold())
412            .insert("F".to_owned(), None);
413        let b = Delta::new().retain(1, None).delete(1);
414
415        assert_eq!(
416            a.compose(b),
417            Delta::new()
418                .insert("AC".to_owned(), Attributes::bold())
419                .insert("D".to_owned(), None)
420                .insert("E".to_owned(), Attributes::bold())
421                .insert("F".to_owned(), None)
422        );
423    }
424}
kyte/compose.rs

kyte/
compose.rs
