1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

// Copyright 2018, 2019, 2020 Martin Pool.

//! Merge two trees by iterating them in lock step.
//!
//! This is a foundation for showing the diff between a stored and
//! live tree, or storing an incremental backup.

use std::cmp::Ordering;

use crate::*;

#[derive(Debug, PartialEq, Eq)]
pub enum MergedEntryKind {
    LeftOnly,
    RightOnly,
    Both,
    // TODO: Perhaps also include the tree-specific entry kind?
}

use self::MergedEntryKind::*;

#[derive(Debug, PartialEq, Eq)]
pub struct MergedEntry {
    // TODO: Add accessors rather than making these public?
    // TODO: Include the original entries from either side?
    pub apath: Apath,
    pub kind: MergedEntryKind,
}

/// Zip together entries from two trees, into an iterator of MergedEntryKind.
///
/// Note that at present this only says whether files are absent from either
/// side, not whether there is a content difference.
pub fn iter_merged_entries<AT, BT>(a: &AT, b: &BT) -> Result<MergeTrees<AT, BT>>
where
    AT: ReadTree,
    BT: ReadTree,
{
    Ok(MergeTrees {
        ait: a.iter_entries()?,
        bit: b.iter_entries()?,
        na: None,
        nb: None,
    })
}

pub struct MergeTrees<AT: ReadTree, BT: ReadTree> {
    ait: AT::I,
    bit: BT::I,

    // Read in advance entries from A and B.
    na: Option<AT::Entry>,
    nb: Option<BT::Entry>,
}

impl<AT, BT> Iterator for MergeTrees<AT, BT>
where
    AT: ReadTree,
    BT: ReadTree,
{
    type Item = MergedEntry;

    fn next(&mut self) -> Option<Self::Item> {
        // TODO: Stats about the merge.
        let ait = &mut self.ait;
        let bit = &mut self.bit;
        // Preload next-A and next-B, if they're not already
        // loaded.
        //
        // TODO: Perhaps use <https://doc.rust-lang.org/stable/core/iter/struct.Peekable.html> instead of keeping a
        // readahead here?
        if self.na.is_none() {
            self.na = ait.next();
        }
        if self.nb.is_none() {
            self.nb = bit.next();
        }
        if self.na.is_none() {
            if self.nb.is_none() {
                None
            } else {
                let tb = self.nb.take().unwrap();
                Some(MergedEntry {
                    apath: tb.apath().clone(),
                    kind: RightOnly,
                })
            }
        } else if self.nb.is_none() {
            Some(MergedEntry {
                apath: self.na.take().unwrap().apath().clone(),
                kind: LeftOnly,
            })
        } else {
            let pa = self.na.as_ref().unwrap().apath().clone();
            let pb = self.nb.as_ref().unwrap().apath().clone();
            match pa.cmp(&pb) {
                Ordering::Equal => {
                    self.na.take();
                    self.nb.take();
                    Some(MergedEntry {
                        apath: pa,
                        kind: Both,
                    })
                }
                Ordering::Less => {
                    self.na.take().unwrap();
                    Some(MergedEntry {
                        apath: pa,
                        kind: LeftOnly,
                    })
                }
                Ordering::Greater => {
                    self.nb.take().unwrap();
                    Some(MergedEntry {
                        apath: pb,
                        kind: RightOnly,
                    })
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::MergedEntry;
    use super::MergedEntryKind::*;
    use crate::test_fixtures::*;
    use crate::*;

    #[test]
    fn merge_entry_trees() {
        let ta = TreeFixture::new();
        let tb = TreeFixture::new();
        let di = iter_merged_entries(&ta.live_tree(), &tb.live_tree())
            .unwrap()
            .collect::<Vec<_>>();
        assert_eq!(di.len(), 1);
        assert_eq!(
            di[0],
            MergedEntry {
                apath: "/".into(),
                kind: Both,
            }
        );
    }

    // TODO: More tests of various diff situations.
}