pijul_core/
missing_context.rs

1use crate::alive::{Graph, VertexId};
2use crate::change::*;
3use crate::pristine::*;
4use crate::{HashMap, HashSet};
5use std::collections::hash_map::Entry;
6
7#[derive(Debug, Error)]
8pub enum MissingError<TxnError: std::error::Error + 'static> {
9    #[error(transparent)]
10    Txn(TxnError),
11    #[error(transparent)]
12    Block(#[from] BlockError<TxnError>),
13    #[error(transparent)]
14    Inconsistent(#[from] InconsistentChange<TxnError>),
15}
16
17impl<T: std::error::Error + 'static> std::convert::From<TxnErr<T>> for MissingError<T> {
18    fn from(e: TxnErr<T>) -> Self {
19        MissingError::Txn(e.0)
20    }
21}
22
23pub type LoadedGraph = (Graph, HashMap<Vertex<ChangeId>, VertexId>);
24impl Workspace {
25    pub fn load_graph<T: GraphTxnT>(
26        &mut self,
27        txn: &T,
28        channel: &T::Graph,
29        inode: Position<Option<Hash>>,
30    ) -> Result<Option<&LoadedGraph>, InconsistentChange<T::GraphError>> {
31        if let Some(change) = inode.change {
32            match self.graphs.0.entry(inode) {
33                Entry::Occupied(e) => Ok(Some(e.into_mut())),
34                Entry::Vacant(v) => {
35                    let pos = Position {
36                        change: if let Some(&i) = txn.get_internal(&change.into())? {
37                            i
38                        } else {
39                            return Err(InconsistentChange::UndeclaredDep);
40                        },
41                        pos: inode.pos,
42                    };
43                    let mut graph = crate::alive::retrieve(txn, channel, pos, false)?;
44                    graph.tarjan();
45                    let mut ids = HashMap::default();
46                    for (i, l) in graph.lines.iter().enumerate() {
47                        ids.insert(l.vertex, VertexId(i));
48                    }
49                    Ok(Some(v.insert((graph, ids))))
50                }
51            }
52        } else {
53            Ok(None)
54        }
55    }
56}
57
58pub(crate) fn has_missing_context_nondeleted<T: GraphMutTxnT>(
59    txn: &T,
60    channel: &T::Graph,
61    change_id: ChangeId,
62    e: &NewEdge<Option<Hash>>,
63) -> Result<bool, MissingError<T::GraphError>> {
64    if e.flag.contains(EdgeFlags::FOLDER) {
65        return Ok(false);
66    }
67    let source = *txn.find_block_end(channel, internal_pos(txn, &e.from, change_id)?)?;
68    let target = *txn.find_block(channel, internal_pos(txn, &e.to.start_pos(), change_id)?)?;
69    debug!(
70        "repair_context_nondeleted source {:?} target {:?} e {:?}",
71        source, target, e
72    );
73    if is_alive(txn, channel, &source)? && e.flag.contains(EdgeFlags::BLOCK) {
74        Ok(iter_adjacent(
75            txn,
76            channel,
77            target,
78            EdgeFlags::DELETED,
79            EdgeFlags::all() - EdgeFlags::PARENT,
80        )?
81        .next()
82        .is_some())
83    } else {
84        Ok(true)
85    }
86}
87
88pub(crate) fn has_missing_context_deleted<T: GraphMutTxnT, K>(
89    txn: &T,
90    channel: &T::Graph,
91    change_id: ChangeId,
92    mut known: K,
93    e: &NewEdge<Option<Hash>>,
94) -> Result<bool, MissingError<T::GraphError>>
95where
96    K: FnMut(Hash) -> bool,
97{
98    if e.flag.contains(EdgeFlags::FOLDER) {
99        return Ok(false);
100    }
101    debug!("repair_context_deleted {:?}", e);
102    let mut pos = internal_pos(txn, &e.to.start_pos(), change_id)?;
103    while let Ok(&dest_vertex) = txn.find_block(channel, pos) {
104        debug!("repair_context_deleted, dest_vertex = {:?}", dest_vertex);
105
106        if has_unknown_children(txn, channel, dest_vertex, change_id, &mut known)? {
107            return Ok(true);
108        }
109
110        if dest_vertex.end < e.to.end {
111            pos.pos = dest_vertex.end
112        } else {
113            break;
114        }
115    }
116    Ok(false)
117}
118
119/// If we're deleting a folder edge, there is a possibility that this
120/// solves a "zombie conflict", by removing the last child of a folder
121/// that was a zombie, in which case that parent folder can finally
122/// rest in peace.
123///
124/// This function takes care of this for the entire change, by
125/// removing all obsolete folder conflict edges.
126pub(crate) fn detect_folder_conflict_resolutions<T: GraphMutTxnT>(
127    txn: &mut T,
128    channel: &mut T::Graph,
129    ws: &mut Workspace,
130    change_id: ChangeId,
131    change: &Change,
132) -> Result<(), MissingError<T::GraphError>> {
133    for change_ in change.changes.iter() {
134        for change_ in change_.iter() {
135            if let Atom::EdgeMap(ref n) = *change_ {
136                for edge in n.edges.iter() {
137                    if !edge.flag.contains(EdgeFlags::DELETED) {
138                        continue;
139                    }
140                    detect_folder_conflict_resolution(txn, channel, ws, change_id, &n.inode, edge)?
141                }
142            }
143        }
144    }
145    Ok(())
146}
147
148fn detect_folder_conflict_resolution<T: GraphMutTxnT>(
149    txn: &mut T,
150    channel: &mut T::Graph,
151    ws: &mut Workspace,
152    change_id: ChangeId,
153    inode: &Position<Option<Hash>>,
154    e: &NewEdge<Option<Hash>>,
155) -> Result<(), MissingError<T::GraphError>> {
156    let mut stack = vec![if e.flag.contains(EdgeFlags::FOLDER) {
157        if e.to.is_empty() {
158            internal_pos(txn, &e.to.start_pos(), change_id)?
159        } else {
160            internal_pos(txn, &e.from, change_id)?
161        }
162    } else {
163        internal_pos(txn, inode, change_id)?
164    }];
165    let len = ws.pseudo.len();
166    while let Some(pos) = stack.pop() {
167        let dest_vertex = match txn.find_block_end(channel, pos) {
168            Ok(&dest_vertex) => {
169                if !dest_vertex.is_empty() {
170                    continue;
171                }
172                dest_vertex
173            }
174            _ => {
175                continue;
176            }
177        };
178        // Is `dest_vertex` alive? If so, stop this path.
179        let f0 = EdgeFlags::FOLDER | EdgeFlags::PARENT;
180        let f1 = EdgeFlags::FOLDER | EdgeFlags::PARENT | EdgeFlags::BLOCK;
181        if let Some(e) = iter_adjacent(txn, channel, dest_vertex, f0, f1)?
182            .filter_map(|e| e.ok())
183            .find(|e| !e.flag().contains(EdgeFlags::PSEUDO))
184        {
185            debug!("is_alive: {:?}", e);
186            continue;
187        }
188        // Does `dest_vertex` have alive or zombie descendants? If
189        // so, stop this path.
190        let f0 = EdgeFlags::empty();
191        let f1 = EdgeFlags::FOLDER | EdgeFlags::BLOCK | EdgeFlags::PSEUDO;
192        if let Some(e) = iter_adjacent(txn, channel, dest_vertex, f0, f1)?.next() {
193            debug!("child is_alive: {:?}", e);
194            continue;
195        }
196        // Else, `dest_vertex` is dead. We should remove its
197        // pseudo-parents.
198        let f = EdgeFlags::FOLDER | EdgeFlags::PARENT | EdgeFlags::PSEUDO;
199        for e in iter_adjacent(txn, channel, dest_vertex, f, f)? {
200            let e = e?;
201            ws.pseudo.push((dest_vertex, *e));
202            let gr = *txn.find_block_end(channel, e.dest()).unwrap();
203            for e in iter_adjacent(txn, channel, gr, f, f)? {
204                let e = e?;
205                ws.pseudo.push((gr, *e));
206                stack.push(e.dest())
207            }
208        }
209    }
210    // Finally, we were only squatting the `.pseudo` field of the
211    // workspace, since that field is normally used for missing
212    // children, and pseudo-edges from that field are treated in a
213    // special way (by `delete_pseudo_edges` in this module).
214    //
215    // Therefore, we need to delete our folder-pseudo-edges now.
216    for (v, e) in ws.pseudo.drain(len..) {
217        let p = *txn.find_block_end(channel, e.dest())?;
218        debug!(
219            "detect folder conflict resolution, deleting {:?} → {:?} {:?}",
220            v, e, p
221        );
222        del_graph_with_rev(
223            txn,
224            channel,
225            e.flag() - EdgeFlags::PARENT,
226            p,
227            v,
228            e.introduced_by(),
229        )?;
230    }
231    Ok(())
232}
233
234pub type UnknownParent = (
235    Vertex<ChangeId>,
236    Vertex<ChangeId>,
237    Position<Option<Hash>>,
238    EdgeFlags,
239);
240
241type AliveUp = (Option<HashSet<Vertex<ChangeId>>>, HashSet<Vertex<ChangeId>>);
242
243#[derive(Default)]
244pub struct Workspace {
245    pub unknown_parents: Vec<UnknownParent>,
246    unknown: Vec<SerializedEdge>,
247    pub parents: HashSet<SerializedEdge>,
248    pub pseudo: Vec<(Vertex<ChangeId>, SerializedEdge)>,
249    repaired: HashSet<Vertex<ChangeId>>,
250    pub graphs: Graphs,
251    pub covered_parents: HashSet<(Vertex<ChangeId>, Vertex<ChangeId>)>,
252    pub files: HashSet<Vertex<ChangeId>>,
253    alive_down_cache: HashMap<Vertex<ChangeId>, Option<HashSet<Vertex<ChangeId>>>>,
254    alive_up_cache: HashMap<Vertex<ChangeId>, AliveUp>,
255    missing_down: Vec<Vertex<ChangeId>>,
256}
257
258pub type GraphWithCache = (Graph, HashMap<Vertex<ChangeId>, crate::alive::VertexId>);
259
260#[derive(Debug, Default)]
261pub struct Graphs(pub HashMap<Position<Option<Hash>>, GraphWithCache>);
262
263impl Graphs {
264    pub(crate) fn get(&self, inode: Position<Option<Hash>>) -> Option<&GraphWithCache> {
265        self.0.get(&inode)
266    }
267
268    pub fn split(
269        &mut self,
270        inode: Position<Option<Hash>>,
271        vertex: Vertex<ChangeId>,
272        mid: ChangePosition,
273    ) {
274        if let Some((_, vids)) = self.0.get_mut(&inode)
275            && let Some(vid) = vids.remove(&vertex)
276        {
277            vids.insert(Vertex { end: mid, ..vertex }, vid);
278            vids.insert(
279                Vertex {
280                    start: mid,
281                    ..vertex
282                },
283                vid,
284            );
285        }
286    }
287}
288
289impl Workspace {
290    pub fn clear(&mut self) {
291        self.unknown.clear();
292        self.unknown_parents.clear();
293        self.pseudo.clear();
294        self.parents.clear();
295        self.graphs.0.clear();
296        self.repaired.clear();
297        self.covered_parents.clear();
298        self.alive_up_cache.clear();
299        self.alive_down_cache.clear();
300        self.missing_down.clear();
301    }
302    pub fn assert_empty(&self) {
303        assert!(self.unknown.is_empty());
304        assert!(self.unknown_parents.is_empty());
305        assert!(self.pseudo.is_empty());
306        assert!(self.parents.is_empty());
307        assert!(self.graphs.0.is_empty());
308        assert!(self.repaired.is_empty());
309        assert!(self.covered_parents.is_empty());
310        assert!(self.alive_up_cache.is_empty());
311        assert!(self.alive_down_cache.is_empty());
312        assert!(self.missing_down.is_empty());
313    }
314}
315
316fn has_unknown_children<T: GraphTxnT, K>(
317    txn: &T,
318    channel: &T::Graph,
319    dest_vertex: Vertex<ChangeId>,
320    change_id: ChangeId,
321    known: &mut K,
322) -> Result<bool, TxnErr<T::GraphError>>
323where
324    K: FnMut(Hash) -> bool,
325{
326    for v in iter_alive_children(txn, channel, dest_vertex)? {
327        let v = v?;
328        debug!(
329            "collect_unknown_children dest_vertex = {:?}, v = {:?}",
330            dest_vertex, v
331        );
332        if v.introduced_by() == change_id || v.dest().change.is_root() {
333            continue;
334        }
335        if v.introduced_by().is_root() {
336            continue;
337        }
338        let mut not_del_by_change = true;
339        for e in iter_adjacent(
340            txn,
341            channel,
342            dest_vertex,
343            EdgeFlags::PARENT | EdgeFlags::DELETED,
344            EdgeFlags::all(),
345        )? {
346            let e = e?;
347            if e.introduced_by() == v.introduced_by() {
348                not_del_by_change = false;
349                break;
350            }
351        }
352        if not_del_by_change {
353            let intro = txn
354                .get_external(&v.introduced_by())
355                .optional()?
356                .unwrap()
357                .into();
358            if !known(intro) {
359                return Ok(true);
360            }
361        }
362    }
363    Ok(false)
364}
pijul_core/missing_context.rs

pijul_core/
missing_context.rs
