cfgrammar/
markmap.rs

1use std::borrow::Borrow;
2
3// MarkMap is a key value data structure that uses an API similar to that of
4// `std::collections::HashMap` and `std::collections::BTreeMap`.
5//
6// The current implementation is based on a sorted `Vec` is not optimized for
7// storing large number of items.
8//
9// On top of the familiar `std::collections` API it has a few additions:
10//
11// * Marking a key with a condition.
12// * Marking a key with a merge behavior.
13// * A merge operator.
14//
15// The current *conditions* are [`Used`](MarkMap::mark_used) and [`Required`](MarkMap::mark_required).
16//
17// The available merge behaviors are [`Theirs`](MergeBehavior::Theirs), [`Ours`](MergeBehavior::Ours),
18// and [`MutuallyExclusive`](MergeBehavior::MutuallyExclusive).
19//
20// Merge behaviors configure how the merge operator handles cases where both `MarkMaps` being merged
21// contain a particular key.
22#[derive(Debug, PartialEq, Eq)]
23pub struct MarkMap<K, V> {
24    contents: Vec<(K, u16, Option<V>)>,
25}
26
27/// Defines the merge behavior for a single key in the markmap.
28#[repr(u8)]
29#[derive(Clone, Copy)]
30#[doc(hidden)]
31pub enum MergeBehavior {
32    /// The value in `self` takes precedence.
33    Theirs = 1 << 0,
34    /// The value in `other` takes precedence.
35    Ours = 1 << 1,
36    /// It is an error if the key is present in both `MarkMaps`.
37    /// This is the default if no merge behavior is set.
38    MutuallyExclusive = 1 << 2,
39}
40
41/// Conflicting values were present while merging, and the
42/// merge behavior did not specify a means to resolve them.
43#[derive(Debug)]
44#[doc(hidden)]
45pub enum MergeError<K, V> {
46    // Contains the key which was present in both, and the value which was present in `Theirs`.
47    Exclusivity(K, V),
48}
49
50/// A view into a single entry in a `MarkMap`, which may either be vacant or occupied.
51#[doc(hidden)]
52pub enum Entry<'a, K, V> {
53    Occupied(OccupiedEntry<'a, K, V>),
54    Vacant(VacantEntry<'a, K, V>),
55}
56
57#[repr(u8)]
58#[derive(Clone, Copy)]
59#[doc(hidden)]
60enum Mark {
61    // There are some other interesting marks that could be added based on row polymorphic records.
62    // Marks such as `Prohibited` could be used to prove disjointedness.
63    Used,
64    Required,
65    MergeBehavior(MergeBehavior),
66}
67
68impl Mark {
69    fn repr(self) -> u16 {
70        match self {
71            Self::Used => 1 << 0,
72            Self::Required => 1 << 1,
73            Self::MergeBehavior(mb) => (1 << 2) | ((mb as u16) << 8),
74        }
75    }
76}
77
78impl<'a, K: Ord + Clone, V> VacantEntry<'a, K, V> {
79    /// Inserts a value into a vacant entry.
80    /// Returns a mutable reference to value inserted.
81    pub fn insert(self, val: V) -> &'a mut V {
82        match self.pos {
83            Ok(pos) => {
84                self.map.contents[pos].2 = Some(val);
85                self.map.contents[pos].2.as_mut().unwrap()
86            }
87            Err(pos) => {
88                self.map.contents.insert(pos, (self.key, 0, Some(val)));
89                self.map.contents[pos].2.as_mut().unwrap()
90            }
91        }
92    }
93
94    /// Inserts a value into a vacant entry.
95    /// Returns an occupied entry.
96    pub fn insert_entry(self, val: V) -> OccupiedEntry<'a, K, V> {
97        match self.pos {
98            Ok(pos) => {
99                self.map.contents[pos].2 = Some(val);
100                OccupiedEntry { pos, map: self.map }
101            }
102            Err(pos) => {
103                self.map.contents.insert(pos, (self.key, 0, Some(val)));
104                OccupiedEntry { pos, map: self.map }
105            }
106        }
107    }
108
109    /// Inserts the key into the `MarkMap`.
110    ///
111    /// If you want to insert a value into the `MarkMap` use `insert` or `insert_entry` instead.
112    /// This function can be used if you want to mark a vacant key as `required` or `used`.
113    pub fn occupied_entry(self) -> OccupiedEntry<'a, K, V> {
114        match self.pos {
115            Ok(pos) => {
116                self.map.contents[pos].2 = None;
117                OccupiedEntry { pos, map: self.map }
118            }
119            Err(pos) => {
120                self.map.contents.insert(pos, (self.key, 0, None));
121                OccupiedEntry { pos, map: self.map }
122            }
123        }
124    }
125
126    /// Returns the key associated with this entry.
127    pub fn key(&self) -> &K {
128        &self.key
129    }
130}
131
132impl<K: Ord, V> OccupiedEntry<'_, K, V> {
133    /// Returns the value associated with this entry.
134    pub fn get(&self) -> &V {
135        self.map.contents[self.pos].2.as_ref().unwrap()
136    }
137
138    /// Sets the value of the entry, and returns the entry’s old value.
139    pub fn insert(self, val: V) -> V {
140        let v: Option<V> = self.map.contents[self.pos].2.take();
141        self.map.contents[self.pos].2 = Some(val);
142        v.unwrap()
143    }
144
145    /// Gets the mark associated with the key of this entry.
146    pub fn get_mark(&self) -> u16 {
147        self.map.contents[self.pos].1
148    }
149
150    /// Marks the key associated with this entry as used.
151    pub fn mark_used(&mut self) {
152        let repr = self.map.contents[self.pos].1 | Mark::Used.repr();
153        self.map.contents[self.pos].1 = repr;
154    }
155
156    /// Returns whether the key associated with this entry is used.
157    pub fn is_used(&self) -> bool {
158        self.map.contents[self.pos].1 & Mark::Used.repr() != 0
159    }
160
161    /// Marks the key associated with this entry as required.
162    pub fn mark_required(&mut self) {
163        let repr = self.map.contents[self.pos].1 | Mark::Required.repr();
164        self.map.contents[self.pos].1 = repr;
165    }
166
167    /// Returns whether the key associated with this entry is required.
168    pub fn is_required(&self) -> bool {
169        self.map.contents[self.pos].1 & Mark::Required.repr() != 0
170    }
171
172    /// Sets the merge behavior for the key associated with this entry.
173    pub fn set_merge_behavior(&mut self, mb: MergeBehavior) {
174        let mut repr = self.map.contents[self.pos].1;
175        let merge_reprs = Mark::MergeBehavior(MergeBehavior::MutuallyExclusive).repr()
176            | Mark::MergeBehavior(MergeBehavior::Ours).repr()
177            | Mark::MergeBehavior(MergeBehavior::Theirs).repr();
178        // Zap just the MergeBehavior bits.
179        repr ^= repr & merge_reprs;
180        repr |= Mark::MergeBehavior(mb).repr();
181        self.map.contents[self.pos].1 = repr;
182    }
183}
184
185/// A view into an occupied entry in a `MarkMap`. It is part of the `Entry` enum.
186#[doc(hidden)]
187pub struct OccupiedEntry<'a, K, V> {
188    pos: usize,
189    map: &'a mut MarkMap<K, V>,
190}
191
192/// A view into a vacant entry in a `MarkMap`. It is part of the `Entry` enum.
193#[doc(hidden)]
194pub struct VacantEntry<'a, K, V> {
195    pos: Result<usize, usize>,
196    key: K,
197    map: &'a mut MarkMap<K, V>,
198}
199
200impl<K: Ord + Clone, V> MarkMap<K, V> {
201    /// Returns a new `MarkMap`.
202    #[allow(clippy::new_without_default)]
203    pub fn new() -> Self {
204        MarkMap { contents: vec![] }
205    }
206
207    /// Inserts a `key` `value` pair.
208    #[doc(hidden)]
209    pub fn insert(&mut self, key: K, val: V) -> Option<V> {
210        let pos = self.contents.binary_search_by(|(k, _, _)| k.cmp(&key));
211        match pos {
212            Ok(pos) => {
213                let ret = self.contents[pos].2.take();
214                self.contents[pos].2 = Some(val);
215                ret
216            }
217            Err(pos) => {
218                self.contents.insert(pos, (key, 0, Some(val)));
219                None
220            }
221        }
222    }
223
224    /// Gets the raw mark value, for testing purposes.
225    #[cfg(test)]
226    pub(crate) fn get_mark(&mut self, key: &K) -> Option<u16> {
227        let pos = self.contents.binary_search_by(|(k, _, _)| k.cmp(key));
228        match pos {
229            Ok(pos) => Some(self.contents[pos].1),
230            Err(_) => None,
231        }
232    }
233
234    /// Marks `key` as used.
235    #[doc(hidden)]
236    pub fn mark_used(&mut self, key: &K) {
237        let pos = self.contents.binary_search_by(|(k, _, _)| k.cmp(key));
238        match pos {
239            Ok(pos) => {
240                let mut repr = self.contents[pos].1;
241                repr |= Mark::Used.repr();
242                self.contents[pos].1 = repr;
243            }
244            Err(pos) => {
245                self.contents
246                    .insert(pos, (key.to_owned(), Mark::Used.repr(), None));
247            }
248        }
249    }
250
251    /// Marks `key` as a required value.
252    #[doc(hidden)]
253    pub fn mark_required(&mut self, key: &K) {
254        let pos = self.contents.binary_search_by(|(k, _, _)| k.cmp(key));
255        match pos {
256            Ok(pos) => {
257                let mut repr = self.contents[pos].1;
258                repr |= Mark::Required.repr();
259                self.contents[pos].1 = repr;
260            }
261            Err(pos) => {
262                self.contents
263                    .insert(pos, (key.to_owned(), Mark::Required.repr(), None));
264            }
265        }
266    }
267
268    /// Returns whether `key` is required.
269    #[doc(hidden)]
270    pub fn is_required(&self, key: &K) -> bool {
271        let pos = self.contents.binary_search_by(|(k, _, _)| k.cmp(key));
272        match pos {
273            Ok(pos) => self.contents[pos].1 & Mark::Required.repr() != 0,
274            _ => false,
275        }
276    }
277
278    /// Sets the merge behavior for `key`.
279    #[doc(hidden)]
280    pub fn set_merge_behavior(&mut self, key: &K, mb: MergeBehavior) {
281        let pos = self.contents.binary_search_by(|(k, _, _)| k.cmp(key));
282        match pos {
283            Ok(pos) => {
284                let mut repr = self.contents[pos].1;
285                let merge_reprs = Mark::MergeBehavior(MergeBehavior::MutuallyExclusive).repr()
286                    | Mark::MergeBehavior(MergeBehavior::Ours).repr()
287                    | Mark::MergeBehavior(MergeBehavior::Theirs).repr();
288                // Zap just the MergeBehavior bits.
289                repr ^= repr & merge_reprs;
290                repr |= Mark::MergeBehavior(mb).repr();
291                self.contents[pos].1 = repr;
292            }
293            Err(pos) => {
294                self.contents
295                    .insert(pos, (key.to_owned(), Mark::MergeBehavior(mb).repr(), None));
296            }
297        }
298    }
299
300    /// Returns a `Some(value)` associated with `key` if present otherwise `None`.
301    #[doc(hidden)]
302    pub fn get<Q>(&self, key: &Q) -> Option<&V>
303    where
304        K: Borrow<Q>,
305        Q: Ord + ?Sized,
306    {
307        let pos = self.contents.binary_search_by(|(k, _, _)| {
308            let q: &Q = k.borrow();
309            q.cmp(key)
310        });
311        match pos {
312            Err(_) => None,
313            Ok(pos) => self.contents[pos].2.as_ref(),
314        }
315    }
316
317    /// Returns true if the `MarkMap` contains `key` otherwise false.
318    #[doc(hidden)]
319    pub fn contains_key<Q>(&self, key: &Q) -> bool
320    where
321        K: Borrow<Q>,
322        Q: Ord + ?Sized,
323    {
324        self.get(key).is_some()
325    }
326
327    /// Removes `key` from the `MarkMap` and returns the previous value when present.
328    #[doc(hidden)]
329    pub fn remove(&mut self, key: &K) -> Option<V> {
330        let pos = self.contents.binary_search_by(|(k, _, _)| k.cmp(key));
331        match pos {
332            Err(_) => None,
333            Ok(pos) => self.contents.remove(pos).2,
334        }
335    }
336
337    /// Returns an `Entry` for `key`.
338    #[doc(hidden)]
339    pub fn entry(&mut self, key: K) -> Entry<K, V> {
340        let pos = self.contents.binary_search_by(|(k, _, _)| k.cmp(&key));
341        match pos {
342            Err(pos) => Entry::Vacant(VacantEntry {
343                pos: Err(pos),
344                key,
345                map: self,
346            }),
347            Ok(pos) => {
348                if self.contents[pos].2.is_some() {
349                    Entry::Occupied(OccupiedEntry { pos, map: self })
350                } else {
351                    Entry::Vacant(VacantEntry {
352                        pos: Ok(pos),
353                        key,
354                        map: self,
355                    })
356                }
357            }
358        }
359    }
360
361    /// Merges items from `other` into `self`, for each value it checks the `MergeBehavior` of self.
362    /// The `MergeBehavior` of other is not considered.
363    ///
364    /// * `MergeBehavior::Ours`: If a value is set in `other`, a value set in self takes precedence.
365    /// * `MergeBehavior::Theirs`: if a value in `other` `is_some()`, then it will overwrite values in self.
366    /// * `MergeBehavior::MutuallyExclusive` If a value is set in `other`, that value should be `None` in self.
367    /// * If `MergeBehavior` is unset, defaults to `MergeBehavior::MutuallyExclusive`.
368    ///
369    /// For the behavior of exclusive or mark the behavior as also `Mark::Required`, then after merge call `missing()`
370    /// to check all required values.
371    #[doc(hidden)]
372    pub fn merge_from(&mut self, mut other: Self) -> Result<(), MergeError<K, Box<V>>> {
373        for (their_key, their_mark, their_val) in other.contents.drain(..) {
374            let pos = self.contents.binary_search_by(|x| x.0.cmp(&their_key));
375            match pos {
376                Ok(pos) => {
377                    let (_, my_mark, my_val) = &mut self.contents[pos];
378                    let theirs_mark = Mark::MergeBehavior(MergeBehavior::Theirs).repr();
379                    let ours_mark = Mark::MergeBehavior(MergeBehavior::Ours).repr();
380                    let exclusive_mark =
381                        Mark::MergeBehavior(MergeBehavior::MutuallyExclusive).repr();
382                    let merge_behavior = (*my_mark & exclusive_mark)
383                        | (*my_mark & ours_mark)
384                        | (*my_mark & theirs_mark);
385                    if merge_behavior == exclusive_mark || merge_behavior == 0 {
386                        // If only clippy could convince me and the borrow checker this is actually unnecessary.
387                        #[allow(clippy::unnecessary_unwrap)]
388                        if my_val.is_some() && their_val.is_some() {
389                            return Err(MergeError::Exclusivity(
390                                their_key,
391                                Box::new(their_val.unwrap()),
392                            ));
393                        } else if my_val.is_none() {
394                            *my_val = their_val;
395                        }
396                    } else if merge_behavior == theirs_mark && their_val.is_some()
397                        || merge_behavior == ours_mark && my_val.is_none()
398                    {
399                        *my_mark = their_mark;
400                        *my_val = their_val;
401                    }
402                }
403                Err(pos) => {
404                    self.contents
405                        .insert(pos, (their_key, their_mark, their_val));
406                }
407            }
408        }
409        Ok(())
410    }
411
412    /// Returns whether `key` has been marked as used.
413    #[doc(hidden)]
414    pub fn is_used<Q>(&self, key: &Q) -> bool
415    where
416        K: Borrow<Q>,
417        Q: Ord + ?Sized,
418    {
419        if let Ok(pos) = self.contents.binary_search_by(|x| {
420            let k: &Q = x.0.borrow();
421            k.borrow().cmp(key)
422        }) {
423            self.contents[pos].1 & Mark::Used.repr() != 0
424        } else {
425            false
426        }
427    }
428
429    /// Returns a `Vec` containing all the keys that are not marked as used.
430    #[doc(hidden)]
431    pub fn unused(&self) -> Vec<K> {
432        let mut ret = Vec::new();
433        for (k, mark, v) in &self.contents {
434            let used_mark = Mark::Used.repr();
435            if v.is_some() && mark & used_mark == 0 {
436                ret.push(k.to_owned())
437            }
438        }
439        ret
440    }
441
442    /// Returns a `Vec` containing all the keys that are marked as required,
443    /// but have values that are not present in the `MarkMap`.
444    #[doc(hidden)]
445    pub fn missing(&self) -> Vec<&K> {
446        let mut ret = Vec::new();
447        for (k, mark, v) in &self.contents {
448            let required_mark = Mark::Required.repr();
449            if v.is_none() && mark & required_mark != 0 {
450                ret.push(k)
451            }
452        }
453        ret
454    }
455
456    /// Returns an `Iterator` over all the keys of the `MarkMap`.
457    #[doc(hidden)]
458    pub fn keys(&self) -> Keys<'_, K, V> {
459        Keys { pos: 0, map: self }
460    }
461}
462
463/// Iterator over the owned keys and values of a `MarkMap`.
464#[doc(hidden)]
465pub struct MarkMapIter<K, V> {
466    map: MarkMap<K, V>,
467}
468
469#[doc(hidden)]
470impl<K, V> Iterator for MarkMapIter<K, V> {
471    type Item = (K, V);
472
473    fn next(&mut self) -> Option<Self::Item> {
474        if !self.map.contents.is_empty() {
475            let (k, _, v) = self.map.contents.swap_remove(0);
476            v.map(|v| (k, v))
477        } else {
478            None
479        }
480    }
481}
482
483/// Iterator over references to keys and values of a `MarkMap`.
484#[doc(hidden)]
485pub struct MarkMapIterRef<'a, K, V> {
486    pos: usize,
487    map: &'a MarkMap<K, V>,
488}
489
490#[doc(hidden)]
491impl<'a, K, V> Iterator for MarkMapIterRef<'a, K, V> {
492    type Item = (&'a K, &'a V);
493
494    fn next(&mut self) -> Option<Self::Item> {
495        if let Some((k, _, v)) = self.map.contents.get(self.pos) {
496            self.pos += 1;
497            v.as_ref().map(|v| (k, v))
498        } else {
499            None
500        }
501    }
502}
503
504#[doc(hidden)]
505impl<'a, K, V> IntoIterator for &'a MarkMap<K, V> {
506    type Item = (&'a K, &'a V);
507    type IntoIter = MarkMapIterRef<'a, K, V>;
508    fn into_iter(self) -> Self::IntoIter {
509        MarkMapIterRef { pos: 0, map: self }
510    }
511}
512
513/// Iterator over references to keys and values of a `MarkMap`.
514#[doc(hidden)]
515pub struct Keys<'a, K, V> {
516    pos: usize,
517    map: &'a MarkMap<K, V>,
518}
519
520impl<'a, K, V> Iterator for Keys<'a, K, V> {
521    type Item = &'a K;
522
523    fn next(&mut self) -> Option<Self::Item> {
524        loop {
525            if self.pos >= self.map.contents.len() {
526                return None;
527            }
528            let pos = self.pos;
529            self.pos += 1;
530            if self.map.contents[pos].2.is_some() {
531                return Some(&self.map.contents[pos].0);
532            }
533        }
534    }
535}
536
537#[cfg(test)]
538mod test {
539    use super::*;
540    #[test]
541    fn test_insert_get_remove() {
542        let mut mm = MarkMap::new();
543        mm.insert("a", "test");
544        assert_eq!(mm.get(&"a"), Some(&"test"));
545        assert_eq!(mm.remove(&"a"), Some("test"));
546        assert_eq!(mm.get(&"a"), None);
547    }
548
549    #[test]
550    fn test_entry_occupied() {
551        let mut mm = MarkMap::new();
552        mm.insert("a", "test");
553        assert!(!mm.is_required(&"a"));
554        assert!(!mm.is_used(&"a"));
555        let ent = mm.entry("a");
556        match ent {
557            Entry::Occupied(mut o) => {
558                assert!(!o.is_required());
559                assert!(!o.is_used());
560                o.mark_used();
561                assert!(o.is_used());
562                assert!(!o.is_required());
563                o.mark_required();
564                assert!(o.is_required());
565                assert!(o.is_used());
566            }
567            Entry::Vacant(_) => {
568                panic!("Expected occupied entry");
569            }
570        }
571        assert!(mm.is_required(&"a"));
572        assert!(mm.is_used(&"a"));
573    }
574
575    #[test]
576    fn test_entry_vacant() {
577        let mut mm = MarkMap::new();
578        mm.insert("a", "test");
579        let ent = mm.entry("b");
580        match ent {
581            Entry::Occupied(_) => {
582                panic!("Expected vacant entry");
583            }
584            Entry::Vacant(v) => {
585                v.insert("test b");
586            }
587        }
588    }
589
590    #[test]
591    fn test_mark() {
592        let mut mm = MarkMap::new();
593        assert!(mm.insert("a", "test").is_none());
594        mm.mark_used(&"a");
595        mm.set_merge_behavior(&"b", MergeBehavior::MutuallyExclusive);
596        assert_eq!(mm.get_mark(&"a"), Some(Mark::Used.repr()));
597        assert_eq!(
598            mm.get_mark(&"b"),
599            Some(Mark::MergeBehavior(MergeBehavior::MutuallyExclusive).repr())
600        );
601        assert_eq!(mm.get_mark(&"c"), None);
602        assert_eq!(mm.get(&"a"), Some(&"test"));
603        assert_eq!(mm.insert("a", "changed"), Some("test"));
604        assert_eq!(mm.get(&"b"), None);
605        assert_eq!(mm.insert("b", "added"), None);
606        assert_eq!(
607            mm.get_mark(&"b"),
608            Some(Mark::MergeBehavior(MergeBehavior::MutuallyExclusive).repr())
609        );
610        assert_eq!(mm.get(&"a"), Some(&"changed"));
611        assert_eq!(mm.get(&"c"), None);
612    }
613
614    #[test]
615    fn test_mark_stable() {
616        let mut mm: MarkMap<&str, &str> = MarkMap::new();
617        mm.mark_used(&"a");
618        assert_eq!(mm.get_mark(&"a"), Some(Mark::Used.repr()));
619        mm.mark_required(&"a");
620        assert_eq!(
621            mm.get_mark(&"a"),
622            Some(Mark::Used.repr() | Mark::Required.repr())
623        );
624        mm.set_merge_behavior(&"a", MergeBehavior::MutuallyExclusive);
625        assert_eq!(
626            mm.get_mark(&"a"),
627            Some(
628                Mark::Used.repr()
629                    | Mark::Required.repr()
630                    | Mark::MergeBehavior(MergeBehavior::MutuallyExclusive).repr()
631            )
632        );
633        mm.set_merge_behavior(&"a", MergeBehavior::Theirs);
634        assert_eq!(
635            mm.get_mark(&"a"),
636            Some(
637                Mark::Used.repr()
638                    | Mark::Required.repr()
639                    | Mark::MergeBehavior(MergeBehavior::Theirs).repr()
640            )
641        );
642        mm.set_merge_behavior(&"a", MergeBehavior::Ours);
643        assert_eq!(
644            mm.get_mark(&"a"),
645            Some(
646                Mark::Used.repr()
647                    | Mark::Required.repr()
648                    | Mark::MergeBehavior(MergeBehavior::Ours).repr()
649            )
650        );
651    }
652
653    #[test]
654    fn test_unused() {
655        {
656            let mut mm = MarkMap::new();
657            assert!(mm.insert("a", "test").is_none());
658            mm.mark_used(&"a");
659            assert_eq!(mm.get_mark(&"a"), Some(Mark::Used.repr()));
660            let empty: &[&String] = &[];
661            assert_eq!(mm.unused().as_slice(), empty);
662        }
663
664        {
665            let mut mm = MarkMap::new();
666            assert!(mm.insert("a", "test").is_none());
667            mm.mark_used(&"a");
668            assert!(mm.insert("b", "unused").is_none());
669            assert_eq!(mm.get_mark(&"a"), Some(Mark::Used.repr()));
670            assert_eq!(mm.get_mark(&"b"), Some(0));
671            assert_eq!(mm.unused().as_slice(), &["b"]);
672        }
673    }
674
675    #[test]
676    fn test_required() {
677        {
678            let mut mm = MarkMap::new();
679            let empty: &[&String] = &[];
680            mm.mark_required(&"a");
681            assert!(mm.insert("a", "test").is_none());
682            assert_eq!(mm.get_mark(&"a"), Some(Mark::Required.repr()));
683            assert_eq!(mm.missing().as_slice(), empty);
684        }
685
686        {
687            let mut mm = MarkMap::new();
688            mm.mark_required(&"a");
689            mm.insert("for", "inference");
690            assert_eq!(mm.get_mark(&"a"), Some(Mark::Required.repr()));
691            assert_eq!(mm.missing().as_slice(), &[&"a"]);
692        }
693    }
694
695    #[test]
696    fn test_merge_empty() {
697        {
698            let mut ours: MarkMap<&str, &str> = MarkMap::new();
699            let theirs = MarkMap::new();
700            assert!(ours.merge_from(theirs).is_ok());
701        }
702        {
703            let mut ours: MarkMap<&str, &str> = MarkMap::new();
704            let theirs: MarkMap<&str, &str> = MarkMap::new();
705            ours.mark_required(&"a");
706            assert!(ours.merge_from(theirs).is_ok());
707            assert_eq!(ours.missing().as_slice(), &[&"a"]);
708        }
709
710        {
711            let mut ours: MarkMap<&str, &str> = MarkMap::new();
712            let theirs: MarkMap<&str, &str> = MarkMap::new();
713            ours.mark_required(&"a");
714            ours.set_merge_behavior(&"a", MergeBehavior::Ours);
715            assert!(ours.merge_from(theirs).is_ok());
716            assert_eq!(ours.missing().as_slice(), &[&"a"]);
717        }
718
719        {
720            let mut ours: MarkMap<&str, &str> = MarkMap::new();
721            let theirs: MarkMap<&str, &str> = MarkMap::new();
722            ours.mark_required(&"a");
723            ours.set_merge_behavior(&"a", MergeBehavior::Theirs);
724            assert!(ours.merge_from(theirs).is_ok());
725            assert_eq!(ours.missing().as_slice(), &[&"a"]);
726        }
727    }
728
729    #[test]
730    fn test_merge_conflict() {
731        {
732            let mut ours = MarkMap::new();
733            let mut theirs = MarkMap::new();
734            ours.insert("a", "ours");
735            ours.set_merge_behavior(&"a", MergeBehavior::MutuallyExclusive);
736            theirs.insert("a", "theirs");
737            assert!(ours.merge_from(theirs).is_err());
738            assert_eq!(ours.get(&"a"), Some(&"ours"));
739        }
740        {
741            // Default behavior should match `MutuallyExclusive`
742            let mut ours = MarkMap::new();
743            let mut theirs = MarkMap::new();
744            ours.insert("a", "ours");
745            theirs.insert("a", "theirs");
746            assert!(ours.merge_from(theirs).is_err());
747            assert_eq!(ours.get(&"a"), Some(&"ours"));
748        }
749    }
750
751    #[test]
752    fn test_merge_ours() {
753        {
754            let mut ours: MarkMap<&str, &str> = MarkMap::new();
755            let mut theirs: MarkMap<&str, &str> = MarkMap::new();
756            ours.insert("a", "ours");
757            theirs.set_merge_behavior(&"a", MergeBehavior::MutuallyExclusive);
758            assert!(ours.merge_from(theirs).is_ok());
759            assert_eq!(ours.get(&"a"), Some(&"ours"));
760        }
761        {
762            // Default behavior should match MutuallyExclusive
763            let mut ours: MarkMap<&str, &str> = MarkMap::new();
764            let theirs: MarkMap<&str, &str> = MarkMap::new();
765            ours.insert("a", "ours");
766            assert!(ours.merge_from(theirs).is_ok());
767            assert_eq!(ours.get(&"a"), Some(&"ours"));
768        }
769
770        {
771            let mut ours: MarkMap<&str, &str> = MarkMap::new();
772            let theirs: MarkMap<&str, &str> = MarkMap::new();
773            ours.insert("a", "ours");
774            ours.set_merge_behavior(&"a", MergeBehavior::MutuallyExclusive);
775            assert!(ours.merge_from(theirs).is_ok());
776            assert_eq!(ours.get(&"a"), Some(&"ours"));
777        }
778        {
779            let mut ours = MarkMap::new();
780            let mut theirs = MarkMap::new();
781            ours.insert("a", "ours");
782            ours.set_merge_behavior(&"a", MergeBehavior::Ours);
783            theirs.insert("a", "theirs");
784            assert!(ours.merge_from(theirs).is_ok());
785            assert_eq!(ours.get(&"a"), Some(&"ours"));
786        }
787    }
788
789    #[test]
790    fn test_merge_theirs() {
791        {
792            let mut ours: MarkMap<&str, &str> = MarkMap::new();
793            let mut theirs: MarkMap<&str, &str> = MarkMap::new();
794            ours.set_merge_behavior(&"a", MergeBehavior::MutuallyExclusive);
795            theirs.insert("a", "theirs");
796            assert!(ours.merge_from(theirs).is_ok());
797            assert_eq!(ours.get(&"a"), Some(&"theirs"));
798        }
799
800        {
801            // Should match default behavior.
802            let mut ours: MarkMap<&str, &str> = MarkMap::new();
803            let mut theirs: MarkMap<&str, &str> = MarkMap::new();
804            theirs.insert("a", "theirs");
805            assert!(ours.merge_from(theirs).is_ok());
806            assert_eq!(ours.get(&"a"), Some(&"theirs"));
807        }
808        {
809            let mut ours = MarkMap::new();
810            let mut theirs = MarkMap::new();
811            ours.insert("a", "ours");
812            ours.set_merge_behavior(&"a", MergeBehavior::Theirs);
813            theirs.insert("a", "theirs");
814            assert!(ours.merge_from(theirs).is_ok());
815            assert_eq!(ours.get(&"a"), Some(&"theirs"));
816        }
817    }
818
819    #[test]
820    fn test_merge_both() {
821        {
822            let mut ours = MarkMap::new();
823            let mut theirs = MarkMap::new();
824            ours.insert("a", "ours");
825            ours.set_merge_behavior(&"a", MergeBehavior::MutuallyExclusive);
826            theirs.insert("b", "theirs");
827            theirs.set_merge_behavior(&"b", MergeBehavior::MutuallyExclusive);
828            assert!(ours.merge_from(theirs).is_ok());
829            assert_eq!(ours.get(&"a"), Some(&"ours"));
830            assert_eq!(ours.get(&"b"), Some(&"theirs"));
831        }
832    }
833
834    #[test]
835    fn test_vacant() {
836        let mut mm = MarkMap::new();
837        let v = mm.entry("a");
838        match v {
839            Entry::Occupied(_) => {
840                panic!("Expected vacant entry");
841            }
842            Entry::Vacant(v) => {
843                let mut o = v.insert_entry("ours");
844                o.mark_required();
845                o.mark_used();
846                assert_eq!(o.get(), &"ours");
847                assert!(o.is_required());
848                assert!(o.is_used());
849            }
850        }
851
852        assert_eq!(mm.get(&"a"), Some(&"ours"));
853        assert!(mm.is_required(&"a"));
854        assert!(mm.is_used(&"a"));
855    }
856
857    #[test]
858    fn test_merge_many() {
859        let mut mm = MarkMap::new();
860        mm.insert("a", ());
861        mm.insert("b", ());
862
863        let mut mm2 = MarkMap::new();
864        mm2.insert("x", ());
865        mm2.insert("y", ());
866
867        mm.merge_from(mm2).unwrap();
868        assert_eq!(
869            mm.keys().cloned().collect::<Vec<_>>(),
870            vec!["a", "b", "x", "y"]
871        );
872    }
873}
cfgrammar/markmap.rs

cfgrammar/
markmap.rs
