libpijul_compat/optimal_diff/
delete.rs

1use super::*;
2use backend::*;
3
4impl<A: Transaction, R: rand::Rng> GenericTxn<A, R> {
5    fn delete_edges(
6        &self,
7        branch: &Branch,
8        edges: &mut Vec<patch::NewEdge>,
9        key: Option<Key<PatchId>>,
10        flag: EdgeFlags,
11    ) {
12        debug!("deleting edges");
13        match key {
14            Some(key) => {
15                debug!("key: {:?}", key);
16                debug_assert!(
17                    self.get_patch(&branch.patches, key.patch).is_some() || key.is_root()
18                );
19                let ext_hash = self.external_hash(key.patch);
20                let edge = Edge::zero(flag);
21                // For all alive edges from `key` with flag `flag`
22                // (remember that `flag` contains `PARENT_EDGE`).
23                for (k, v) in self.iter_nodes(&branch, Some((key, Some(&edge))))
24                    .take_while(|&(k, v)| {
25                        k == key
26                            && v.flag <= flag | EdgeFlags::PSEUDO_EDGE | EdgeFlags::EPSILON_EDGE
27                    }) {
28                    if v.flag.contains(EdgeFlags::EPSILON_EDGE) {
29                        // We cannot "unresolve" a conflict by recording a patch.
30                        continue;
31                    }
32
33                    if v.flag.contains(EdgeFlags::PSEUDO_EDGE) {
34                        let mut edge = v.clone();
35                        edge.flag = EdgeFlags::DELETED_EDGE | EdgeFlags::PARENT_EDGE;
36                        edge.introduced_by = ROOT_PATCH_ID;
37                        let mut edges = self.iter_nodes(&branch, Some((key, Some(&edge))));
38                        match edges.next() {
39                            Some((k_, v_)) if k_ == key && v_.flag == edge.flag => {
40                                // `key` has at least one deleted edge
41                                // pointing to it, so key is either
42                                // dead or a zombie. We need to
43                                // confirm that it is actually deleted
44                                // by deleting edge `v`.
45                                debug!("zombie edge: {:?} {:?}", k, v);
46                            }
47                            x => {
48                                // The target of this edge is not deleted,
49                                // and not a zombie vertex.  We can ignore
50                                // this pseudo-edge, as deleting all alive
51                                // edges to the target will have the same
52                                // effect.
53                                debug!("not a zombie: {:?}", x);
54                                continue;
55                            }
56                        }
57                    };
58                    debug!("delete: {:?} {:?}", k, v);
59                    debug!("actually deleting");
60                    edges.push(patch::NewEdge {
61                        from: Key {
62                            patch: Some(ext_hash.to_owned()),
63                            line: key.line.clone(),
64                        },
65                        to: Key {
66                            patch: Some(self.external_hash(v.dest.patch).to_owned()),
67                            line: v.dest.line.clone(),
68                        },
69                        introduced_by: Some(self.external_hash(v.introduced_by).to_owned()),
70                    });
71                }
72            }
73            None => {}
74        }
75    }
76
77    // i0: index of the first deleted line.
78    // i > i0: index of the first non-deleted line (might or might not exist).
79    pub(in optimal_diff) fn delete_lines(
80        &self,
81        branch: &Branch,
82        diff: &mut Diff<A>,
83        i0: usize,
84        i1: usize,
85    ) -> Deletion {
86        debug!("delete_lines: {:?}", i1 - i0);
87        let mut edges = Vec::with_capacity(i1 - i0);
88        let mut contains_conflict = None;
89        for i in i0..i1 {
90            debug!("deleting line {:?}", diff.lines_a[i]);
91            if diff.lines_a[i] == ROOT_KEY {
92                // We've deleted a conflict marker.
93                contains_conflict = diff.conflicts_ancestors.get(&i)
94            } else {
95                self.delete_edges(
96                    branch,
97                    &mut edges,
98                    Some(diff.lines_a[i]),
99                    EdgeFlags::PARENT_EDGE,
100                );
101            }
102        }
103
104        let mut conflict_ordering = Vec::new();
105
106        // If this is an ordering conflict, add the relevant edges.
107        if contains_conflict.is_some() {
108            if i0 > 0 && i1 < diff.lines_a.len() {
109                let from_patch = diff.lines_a[i0 - 1].patch;
110                let to_patch = diff.lines_a[i1].patch;
111                if !self.is_connected(branch, diff.lines_a[i0 - 1], diff.lines_a[i1]) {
112                    debug!("conflict ordering between {:?} and {:?}", i0 - 1, i1);
113                    conflict_ordering.push(Change::NewNodes {
114                        up_context: Rc::new(RefCell::new(vec![
115                            Key {
116                                patch: Some(from_patch.to_owned()),
117                                line: diff.lines_a[i0 - 1].line.clone(),
118                            },
119                        ])),
120                        down_context: Rc::new(RefCell::new(vec![
121                            Key {
122                                patch: Some(to_patch.to_owned()),
123                                line: diff.lines_a[i1].line.clone(),
124                            },
125                        ])),
126                        line_num: diff.line_num.clone(),
127                        flag: EdgeFlags::EPSILON_EDGE,
128                        nodes: vec![Vec::new()],
129                        inode: diff.inode.clone(),
130                    });
131                    *diff.line_num += 1
132                }
133            }
134        }
135
136        // Deletion
137        Deletion {
138            del: if edges.len() > 0 {
139                Some(Change::NewEdges {
140                    edges: edges,
141                    previous: EdgeFlags::PARENT_EDGE,
142                    flag: EdgeFlags::PARENT_EDGE | EdgeFlags::DELETED_EDGE,
143                    inode: diff.inode.clone(),
144                })
145            } else {
146                None
147            },
148            conflict_ordering,
149        }
150    }
151
152    /// Remove the deleted edges of a zombie.
153    pub(in optimal_diff) fn confirm_zombie(
154        &self,
155        branch: &Branch,
156        diff: &Diff<A>,
157        actions: &mut Vec<Record<Rc<RefCell<ChangeContext<PatchId>>>>>,
158        key: Key<PatchId>,
159    ) {
160        debug!("confirm_zombie: {:?}", key);
161        let mut zombie_edges = Vec::new();
162        self.delete_edges(
163            branch,
164            &mut zombie_edges,
165            Some(key),
166            EdgeFlags::DELETED_EDGE | EdgeFlags::PARENT_EDGE,
167        );
168        if !zombie_edges.is_empty() {
169            actions.push(Record::Change {
170                change: Change::NewEdges {
171                    edges: zombie_edges,
172                    previous: EdgeFlags::PARENT_EDGE | EdgeFlags::DELETED_EDGE,
173                    flag: EdgeFlags::PARENT_EDGE,
174                    inode: diff.inode.clone(),
175                },
176                file: diff.file.clone(),
177                conflict_reordering: Vec::new(),
178            })
179        }
180    }
181}
libpijul_compat/optimal_diff/delete.rs

libpijul_compat/optimal_diff/
delete.rs
