let mut ws = Workspace::new();

    let mut ws = Workspace::default();

    repair_newvertex_contexts::<T, C>(txn, channel, &mut ws)?;

    repair_newvertex_contexts::<T, C>(txn, channel, &mut ws, change_id)?;

            remove_zombies::<T, C>(txn, channel, change_id, n)?;

            remove_zombies::<_, C>(txn, channel, &mut ws, change_id, n)?;

    crate::apply::clean_obsolete_pseudo_edges(txn, channel, &mut ws.apply)?;

    crate::apply::clean_obsolete_pseudo_edges(txn, channel, &mut ws.apply, change_id)?;
    crate::apply::repair_cyclic_paths(txn, channel, &mut ws.apply)?;

#[derive(Default)]

    down: HashMap<Vertex<ChangeId>, (Position<Option<Hash>>, bool)>,

    down: HashMap<Vertex<ChangeId>, Position<Option<Hash>>>,
    parents: HashSet<Vertex<ChangeId>>,

    stack: Vec<Vertex<ChangeId>>,
    del_edges: Vec<(Vertex<ChangeId>, Edge)>,

impl Workspace {
    fn new() -> Self {
        Workspace {
            up: HashMap::new(),
            down: HashMap::new(),
            del: Vec::new(),
            apply: crate::apply::Workspace::new(),
        }
    }
}

    while pos.pos <= new_vertex.end {
        debug!("pos = {:?}", pos);
        let vertex = if let Ok(v) = find_block(txn, channel, pos) {
            v
        } else {
            // This means that the only edges to this block were
            // removed from the graph, which can only happen if this
            // block is the bottommost vertex in the graph.
            if cfg!(debug_assertions) {
                while pos.pos <= new_vertex.end {
                    assert!(find_block(txn, channel, pos).is_err());
                    pos.pos = pos.pos + 1;
                }
            }
            break;
        };

    while let Ok(vertex) = find_block(txn, channel, pos) {

        for e in iter_adjacent(txn, channel, vertex, EdgeFlags::empty(), EdgeFlags::all()) {

        for e in iter_adj_all(txn, channel, vertex) {

            if !e.flag.contains(EdgeFlags::DELETED) {
                if e.flag.contains(EdgeFlags::PARENT) {
                    if !e.flag.contains(EdgeFlags::FOLDER) {

            if !e.flag.is_deleted() {
                if e.flag.is_parent() {
                    if !e.flag.is_folder() {

                    ws.down.insert(
                        down_v,
                        (new_vertex.inode, e.flag.contains(EdgeFlags::FOLDER)),
                    );

                    ws.down.insert(down_v, new_vertex.inode);
                    if e.flag.is_folder() {
                        ws.apply.missing_context.files.insert(down_v);
                    }

        ws.perform_del::<C, T>(txn, channel, vertex)?;
        if vertex.end < new_vertex.end {
            pos.pos = vertex.end
        }
    }
    Ok(())
}

        // Delete all in `del`.
        for e in ws.del.drain(..) {
            let (a, b) = if e.flag.contains(EdgeFlags::PARENT) {

impl Workspace {
    fn perform_del<C: ChangeStore, T: MutTxnT>(
        &mut self,
        txn: &mut T,
        channel: &mut Channel<T>,
        vertex: Vertex<ChangeId>,
    ) -> Result<(), UnrecordError<C::Error, T::Error>> {
        for e in self.del.drain(..) {
            let (a, b) = if e.flag.is_parent() {

        // Move on to the next split of ~new_vertex~.
        pos.pos = vertex.end

        Ok(())

    Ok(())

    change_id: ChangeId,

    let mut parents = HashSet::new();
    for (down, (inode, is_folder)) in ws.down.drain() {

    for (down, inode) in ws.down.drain() {

                parents.insert(parent);

                ws.parents.insert(parent);

        debug!("parents {:#?}", parents);
        for up in parents.drain() {

        debug!("parents {:#?}", ws.parents);
        for up in ws.parents.drain() {

                change_id,

                is_folder,

        // This is ok: since this change is applied, this can't fail.
        let int = internal(txn, &edge.introduced_by, change_id).unwrap();

        let intro = internal(txn, &edge.introduced_by, change_id).unwrap();

            int,

            intro,

            &NewEdge {
                previous: edge.flag,
                flag: edge.previous,
                from: edge.from,
                to: edge.to,
                introduced_by: Some(ext),
            },

            &edge.reverse(Some(ext)),

                must_reintroduce(
                    txn,
                    channel,
                    changes,
                    a,
                    b,
                    edge.introduced_by.unwrap(),
                    int,
                )

                must_reintroduce(txn, channel, changes, a, b, ext, intro, change_id)

    current_id: ChangeId,

    for e in iter_adjacent(txn, channel, a, EdgeFlags::empty(), EdgeFlags::all()).filter(|e| {
        !e.flag.contains(EdgeFlags::PARENT) && e.dest == b.start_pos() && !e.introduced_by.is_root()

    for e in iter_adj_all(txn, channel, a).filter(|e| {
        !e.flag.contains(EdgeFlags::PARENT)
            && e.dest == b.start_pos()
            && !e.introduced_by.is_root()
            && e.introduced_by != current_id

        // Optimisation to avoid opening change files
        // in the vast majority of cases: if there is
        // an edge `e` parallel to a -> b introduced
        // by the change that introduced a or b, don't
        // reinsert a -> b: that edge was removed by
        // `e`.
        if !cfg!(debug_assertions) && (a.change == intro_id || b.change == intro_id) {

        // Optimisation to avoid opening change files in the vast
        // majority of cases: if there is an edge `e` parallel to a ->
        // b introduced by the change that introduced a or b, don't
        // reinsert a -> b: that edge was removed by `e`.
        if a.change == intro_id || b.change == intro_id {

    ws: &mut Workspace,

    let mut del = Vec::new();
    let mut stack = vec![];
    let mut visited = HashSet::new();

        // Remove zombies caused by this EdgeMap.

        stack.push(find_block(txn, channel, to)?);
        visited.clear();
        while let Some(v) = stack.pop() {
            debug!("remove_zombies, v = {:?}", v);
            if !visited.insert(v) {
                continue;
            }
            for e in iter_adjacent(txn, channel, v, EdgeFlags::empty(), EdgeFlags::all()) {
                debug!("e = {:?}", e);
                // If the edge is a parent-non-block edge, go up.
                let mut follow =
                    e.flag.contains(EdgeFlags::DELETED) && e.introduced_by != change_id;
                follow |= e.flag & (EdgeFlags::BLOCK | EdgeFlags::PARENT) == EdgeFlags::PARENT;
                if !follow && e.introduced_by != change_id {
                    continue;
                }
                if e.flag.contains(EdgeFlags::PARENT) {
                    stack.push(find_block_end(txn, channel, e.dest)?)
                } else {
                    stack.push(find_block(txn, channel, e.dest)?)
                }
                if e.introduced_by == change_id {
                    del.push((v, e))
                }
            }
        }
        debug!("remove_zombies = {:#?}", del);
        for (v, e) in del.drain(..) {

        collect_zombies(txn, channel, change_id, to, ws)?;
        debug!("remove_zombies = {:#?}", ws.del_edges);
        for (v, mut e) in ws.del_edges.drain(..) {

                del_graph_with_rev(
                    txn,
                    channel,
                    e.flag - EdgeFlags::PARENT,
                    u,
                    v,
                    e.introduced_by,
                )
                .map_err(UnrecordError::Txn)?;
                if iter_adjacent(
                    txn,
                    channel,
                    u,
                    EdgeFlags::empty(),
                    EdgeFlags::all() - EdgeFlags::DELETED - EdgeFlags::PARENT,
                )
                .find(|e| e.dest == v.start_pos())
                .is_none()
                {
                    let f = if e.flag.contains(EdgeFlags::FOLDER) {
                        EdgeFlags::FOLDER
                    } else {
                        EdgeFlags::empty()
                    };
                    put_graph_with_rev(txn, channel, f, u, v, u.change)
                        .map_err(UnrecordError::Txn)?;
                }

                e.flag -= EdgeFlags::PARENT;
                del_graph_with_rev(txn, channel, e.flag, u, v, e.introduced_by)
                    .map_err(UnrecordError::Txn)?;

fn collect_zombies<T: TxnT>(
    txn: &mut T,
    channel: &mut Channel<T>,
    change_id: ChangeId,
    to: Position<ChangeId>,
    ws: &mut Workspace,
) -> Result<(), BlockError> {
    ws.stack.push(find_block(txn, channel, to)?);
    while let Some(v) = ws.stack.pop() {
        debug!("remove_zombies, v = {:?}", v);
        if !ws.parents.insert(v) {
            continue;
        }
        for e in iter_adj_all(txn, channel, v) {
            debug!("e = {:?}", e);
            if !(e.introduced_by == change_id || e.flag & EdgeFlags::bp() == EdgeFlags::PARENT) {
                continue;
            }
            if e.flag.contains(EdgeFlags::PARENT) {
                ws.stack.push(find_block_end(txn, channel, e.dest)?)
            } else {
                ws.stack.push(find_block(txn, channel, e.dest)?)
            }
            if e.introduced_by == change_id {
                ws.del_edges.push((v, e))
            }
        }
    }
    ws.stack.clear();
    ws.parents.clear();
    Ok(())
}

        let intro = internal(txn, &e.introduced_by, change_id).unwrap();
        let intro_ext = e.introduced_by.unwrap_or(change_hash);

            let e = NewEdge {
                previous: e.flag,
                flag: e.previous,
                from: e.from,
                to: e.to,
                introduced_by: Some(change_hash),
            };
            let intro = internal(txn, &e.introduced_by, change_id).unwrap();
            let intro_ext = e.introduced_by.unwrap_or(change_hash);

                &e,

                &e.reverse(Some(change_hash)),

            let intro = internal(txn, &e.introduced_by, change_id).unwrap();
            let intro_ext = e.introduced_by.unwrap_or(change_hash);

                &NewEdge {
                    previous: e.flag,
                    flag: e.previous,
                    from: e.from,
                    to: e.to,
                    introduced_by: Some(change_hash),
                },

                &e.reverse(Some(change_hash)),

                &"a\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\nx\n<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\ny\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\nz\n<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\nf\n"

                &"a\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\nx\n<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\ny\n<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\nz\n<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\nf\n"

            Ok(&">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\nx\n<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\ny\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\nz\n<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n"[..])

            Ok(&">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\nx\n<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\ny\n<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\nz\n<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<\n"[..])

    let files_charlie = repo_charlie.list_files();

    let mut files_charlie = repo_charlie.list_files();
    files_charlie.sort();
    // Two files with the same name (file), one of which also has another name (file3). This means that we don't know which one of the two names crate::output will pick, between "file3" and the conflicting name.
    // This depends on which file gets output first.
    assert_eq!(files_charlie[0], "file");
    assert!(files_charlie[1] == "file3" || files_charlie[1].starts_with("file."));

    repo_charlie.rename(&files_charlie[1], "file3")?;
    txn_charlie.move_file(&files_charlie[1], "file3")?;
    let _charlie_solution = record_all(
        &mut repo_charlie,
        &changes,
        &mut txn_charlie,
        &mut channel_charlie,
        "",
    )
    .unwrap();
    debug_to_file(&txn_charlie, &channel_charlie, "debug_charlie3")?;
    output::output_repository_no_pending(
        &mut repo_charlie,
        &changes,
        &mut txn_charlie,
        &mut channel_charlie,
        "",
        true,
    )?;
    let mut files_charlie = repo_charlie.list_files();
    files_charlie.sort();
    assert_eq!(files_charlie, &["file", "file3"]);

    let files_alice = repo_alice.list_files();

    let mut files_alice = repo_alice.list_files();
    files_alice.sort();

    // Bob applies Alice's change

    // Bob applies Alice's change and Charlie's change

    // Charlie applies Alice's move and deletes.

    // Charlie applies Alice's move and deletes (i.e. does the same as Bob).

    debug!("Charlie applies Bob's deletion");

    debug!("Charlie applies Bob's resolution");

    assert_eq!(conflicts.len(), 2);
    match (&conflicts[0], &conflicts[1]) {
        (Conflict::ZombieFile { ref path }, Conflict::MultipleNames { .. })
        | (Conflict::MultipleNames { .. }, Conflict::ZombieFile { ref path }) => {
            assert!(path == "a/b/c/alice" || path == "a/b/c/file")
        }

    assert_eq!(conflicts.len(), 1);
    match conflicts[0] {
        Conflict::ZombieFile { ref path } => assert_eq!(path, "a/b/c/alice"),

    debug!("Alice applies Charlie's deletion");

                    flag: EdgeFlags::empty(),

                    flag: EdgeFlags::BLOCK,

            if !moved.need_new_name {
                moved.resurrect.extend(moved.edges.drain(..));
            }

        if intro.len() > 1 {

        if intro.len() > 1 || !moved.resurrect.is_empty() {

    }
    /// Is this vertex of zero length?
    pub fn is_empty(&self) -> bool {
        self.end == self.start

    /// Is this vertex of zero length?
    pub fn is_empty(&self) -> bool {
        self.end == self.start
    }

    }
}
impl<T: MutTxnT> Channel<T> {
    pub(crate) fn touch(&mut self) {
        use std::time::SystemTime;
        if let Ok(duration) = SystemTime::now().duration_since(SystemTime::UNIX_EPOCH) {
            self.last_modified = duration.as_secs();
        }

}
pub(crate) fn iter_alive_children<'db, 'txn: 'db, T: TxnT>(
    txn: &'txn T,
    channel: &'db Channel<T>,
    key: Vertex<ChangeId>,
) -> AdjacentIterator<'txn, T> {
    iter_adjacent(
        txn,
        channel,
        key,
        EdgeFlags::empty(),
        EdgeFlags::alive_children(),
    )

pub(crate) fn iter_deleted_parents<'db, 'txn: 'db, T: TxnT>(
    txn: &'txn T,
    channel: &'db Channel<T>,
    key: Vertex<ChangeId>,
) -> AdjacentIterator<'txn, T> {
    iter_adjacent(
        txn,
        channel,
        key,
        EdgeFlags::DELETED | EdgeFlags::PARENT,
        EdgeFlags::all(),
    )
}
pub(crate) fn iter_adj_all<'db, 'txn: 'db, T: TxnT>(
    txn: &'txn T,
    channel: &'db Channel<T>,
    key: Vertex<ChangeId>,
) -> AdjacentIterator<'txn, T> {
    iter_adjacent(txn, channel, key, EdgeFlags::empty(), EdgeFlags::all())
}

        for e in iter_adjacent(txn, &channel, v, EdgeFlags::empty(), EdgeFlags::all()) {

        for e in iter_adj_all(txn, &channel, v) {

            for e in iter_adjacent(
                txn,
                &channel,
                vertex.inode_vertex(),
                EdgeFlags::empty(),
                EdgeFlags::all(),
            ) {

            for e in iter_adj_all(txn, &channel, vertex.inode_vertex()) {

/// Possible flags of edges.
#[derive(Serialize, Deserialize)]
pub struct EdgeFlags: u8 {
const BLOCK = 1;
/// A pseudo-edge, computed when applying the change to
/// restore connectivity, and/or mark conflicts.
const PSEUDO = 4;
/// An edge encoding file system hierarchy.
const FOLDER = 16;
/// A "reverse" edge (all edges in the graph have a reverse edge).
const PARENT = 32;
/// An edge whose target (if not also `PARENT`) or
/// source (if also `PARENT`) is marked as deleted.
const DELETED = 128;

    /// Possible flags of edges.
    #[derive(Serialize, Deserialize)]
    pub struct EdgeFlags: u8 {
        const BLOCK = 1;
        /// A pseudo-edge, computed when applying the change to
        /// restore connectivity, and/or mark conflicts.
        const PSEUDO = 4;
        /// An edge encoding file system hierarchy.
        const FOLDER = 16;
        /// A "reverse" edge (all edges in the graph have a reverse edge).
        const PARENT = 32;
        /// An edge whose target (if not also `PARENT`) or
        /// source (if also `PARENT`) is marked as deleted.
        const DELETED = 128;
    }

impl EdgeFlags {
    #[inline]
    pub(crate) fn db() -> Self {
        Self::DELETED | Self::BLOCK
    }
    #[inline]
    pub(crate) fn bp() -> Self {
        Self::BLOCK | Self::PARENT
    }
    #[inline]
    pub(crate) fn pseudof() -> Self {
        Self::PSEUDO | Self::FOLDER
    }
    #[inline]
    pub(crate) fn alive_children() -> Self {
        Self::BLOCK | Self::PSEUDO | Self::FOLDER
    }
    #[inline]
    pub(crate) fn parent_folder() -> Self {
        Self::PARENT | Self::FOLDER
    }
    #[inline]
    pub(crate) fn is_deleted(&self) -> bool {
        self.contains(EdgeFlags::DELETED)
    }
    #[inline]
    pub(crate) fn is_parent(&self) -> bool {
        self.contains(EdgeFlags::PARENT)
    }
    #[inline]
    pub(crate) fn is_folder(&self) -> bool {
        self.contains(EdgeFlags::FOLDER)
    }
    #[inline]
    pub(crate) fn is_block(&self) -> bool {
        self.contains(EdgeFlags::BLOCK)
    }

            b.sort_by(|u, v| {

            b.sort_unstable_by(|u, v| {

            match self.graphs.entry(inode) {

            match self.graphs.0.entry(inode) {

    change_id: ChangeId,

    d_is_folder: bool,

    let (mut alive, files) = find_alive_up(txn, channel, c)?;

    let mut alive = find_alive_up(txn, channel, &mut ws.files, c, change_id)?;

    debug!("repair_missing_up_context, files = {:?}", files);

        if let Some((graph, vids)) = ws.graphs.get(&inode) {

        if let Some((graph, vids)) = ws.graphs.0.get(&inode) {

        for &ancestor in alive.iter() {
            debug!("put_graph_with_rev {:?} -> {:?}", ancestor, d);
            if ancestor == d {
                info!(
                    "repair_missing_up_context, alive: {:?} == {:?}",
                    ancestor, d
                );
                continue;
            }
            debug!("repair_missing_up {:?} {:?}", ancestor, d);
            put_graph_with_rev(
                txn,
                channel,
                if d_is_folder {
                    EdgeFlags::PSEUDO | EdgeFlags::FOLDER
                } else {
                    EdgeFlags::PSEUDO
                },
                ancestor,
                d,
                ChangeId::ROOT,
            )
            .map_err(MissingError::Txn)?;
        }
        if d_is_folder && c != d {
            put_graph_with_rev(
                txn,
                channel,
                EdgeFlags::PSEUDO | EdgeFlags::FOLDER,
                c,
                d,
                ChangeId::ROOT,
            )
            .map_err(MissingError::Txn)?;
        }

        repair_regular_up(txn, channel, &alive, d, EdgeFlags::PSEUDO).map_err(MissingError::Txn)?;

    repair_files_up(txn, channel, &files, ws)?;

fn repair_files_up<T: MutTxnT>(

fn repair_regular_up<T: MutTxnT>(

    files: &[(Vertex<ChangeId>, Edge)],
    ws: &mut Workspace,
) -> Result<(), MissingError<T::Error>> {
    for &(a, b) in files {
        let b = if a.start == a.end {
            find_block_end(txn, channel, b.dest)?
        } else {
            b.dest.inode_vertex()
        };
        debug!("put_graph_with_rev (files) {:?} -> {:?}", b, a);
        assert_ne!(a, b);
        put_graph_with_rev(
            txn,
            channel,
            EdgeFlags::FOLDER | EdgeFlags::PSEUDO,
            b,
            a,
            ChangeId::ROOT,
        )
        .map_err(MissingError::Txn)?;
        ws.repaired.insert(a);

    alive: &HashSet<Vertex<ChangeId>>,
    d: Vertex<ChangeId>,
    flag: EdgeFlags,
) -> Result<(), T::Error> {
    for &ancestor in alive.iter() {
        debug!("put_graph_with_rev {:?} -> {:?}", ancestor, d);
        if ancestor == d {
            info!(
                "repair_missing_up_context, alive: {:?} == {:?}",
                ancestor, d
            );
            continue;
        }
        debug!("repair_missing_up {:?} {:?}", ancestor, d);
        put_graph_with_rev(txn, channel, flag, ancestor, d, ChangeId::ROOT)?;

    if let Some((graph, vids)) = ws.graphs.get(&inode) {

    if let Some((graph, vids)) = ws.graphs.0.get(&inode) {

        for &descendant in alive.iter() {
            if d == descendant {
                info!(
                    "repair_missing_down_context, alive: {:?} == {:?}",
                    d, descendant
                );

        for &desc in alive.iter() {
            if d == desc {
                info!("repair_missing_down_context, alive: {:?} == {:?}", d, desc);

            debug!("repair_missing_down {:?} {:?}", d, descendant);
            put_graph_with_rev(
                txn,
                channel,
                EdgeFlags::PSEUDO,
                d,
                descendant,
                ChangeId::ROOT,
            )
            .map_err(MissingError::Txn)?;

            debug!("repair_missing_down {:?} {:?}", d, desc);
            put_graph_with_rev(txn, channel, EdgeFlags::PSEUDO, d, desc, ChangeId::ROOT)
                .map_err(MissingError::Txn)?;

    let source = internal_pos(txn, &e.from, change_id)?;
    let source = find_block_end(txn, &channel, source)?;
    let target = internal_pos(txn, &e.to.start_pos(), change_id)?;
    let target = find_block(txn, &channel, target)?;
    debug!(
        "repair_context_nondeleted: source = {:?}, target: {:?}",
        source, target
    );
    // Fixing the connection from root to the source: if the source is
    // deleted by an unknown patch, or if the target is deleted
    // (necessarily by unknown patch), then `target` might be
    // disconnected from the alive graph, so we need to fix the context.
    let mut deleted_by_unknown = false;
    let mut target_is_folder = false;
    for v in iter_adjacent(txn, channel, source, EdgeFlags::empty(), EdgeFlags::all()) {
        if !v.flag.contains(EdgeFlags::PARENT) {
            target_is_folder = v.flag.contains(EdgeFlags::FOLDER);
            continue;
        }
        if !v.flag.contains(EdgeFlags::DELETED) {
            continue;
        }
        if v.introduced_by == change_id || v.dest.change.is_root() || v.introduced_by.is_root() {
            continue;
        }
        // This unwrap is ok, since `v` is in the channel.
        let intro = txn.get_external(v.introduced_by).unwrap();
        if known(intro) {
            // If a known change also delete the context, we're good.
            deleted_by_unknown = false;
            break;
        } else {
            // If an unknown change deletes the context, wait: maybe a
            // known change will delete it too.
            deleted_by_unknown = true;
        }

    if e.flag.contains(EdgeFlags::FOLDER) {
        return Ok(());

    debug!("deleted_by_unknown {:?}", deleted_by_unknown);
    if deleted_by_unknown {
        repair_missing_up_context(txn, channel, ws, inode, source, &[target], target_is_folder)?;

    let source = find_block_end(txn, &channel, internal_pos(txn, &e.from, change_id)?)?;
    let target = find_block(
        txn,
        &channel,
        internal_pos(txn, &e.to.start_pos(), change_id)?,
    )?;
    if deleted_by_unknown(txn, channel, source, change_id, &mut known) {
        repair_missing_up_context(txn, channel, ws, change_id, inode, source, &[target])?;

    reconnect_target_up(txn, channel, ws, inode, target, change_id)?;
    reconnect_target_down(txn, channel, ws, inode, target, change_id, &mut known)
}

    // Now, maybe ~source~ was deleted by known changes, but
    // accessibility to ~target~ was provided by other edges that got
    // deleted by unknown changes.

fn reconnect_target_up<T: MutTxnT>(
    txn: &mut T,
    channel: &mut Channel<T>,
    ws: &mut Workspace,
    inode: Position<Option<Hash>>,
    target: Vertex<ChangeId>,
    change_id: ChangeId,
) -> Result<(), MissingError<T::Error>> {

    for v in iter_adjacent(txn, channel, target, EdgeFlags::empty(), EdgeFlags::all()) {
        if !v.flag.contains(EdgeFlags::PARENT) || !v.flag.contains(EdgeFlags::DELETED) {

    for v in iter_deleted_parents(txn, channel, target) {
        if v.dest.change.is_root() || v.introduced_by.is_root() {

        if v.introduced_by == change_id || v.dest.change.is_root() || v.introduced_by.is_root() {
            continue;

        if v.introduced_by == change_id {
            unknown.clear();
            break;

        // since no change can create a conflict.

        // since no change can create a conflict with itself.

        repair_missing_up_context(txn, channel, ws, inode, up, &[target], target_is_folder)?;

        repair_missing_up_context(txn, channel, ws, change_id, inode, up, &[target])?;

    Ok(())
}

fn reconnect_target_down<T: MutTxnT, K>(
    txn: &mut T,
    channel: &mut Channel<T>,
    ws: &mut Workspace,
    inode: Position<Option<Hash>>,
    target: Vertex<ChangeId>,
    change_id: ChangeId,
    known: &mut K,
) -> Result<(), MissingError<T::Error>>
where
    K: FnMut(Hash) -> bool,
{

    for v in iter_adjacent(txn, channel, target, EdgeFlags::empty(), EdgeFlags::all()) {

    for v in iter_adj_all(txn, channel, target) {

}
fn deleted_by_unknown<T: TxnT, K>(
    txn: &T,
    channel: &Channel<T>,
    source: Vertex<ChangeId>,
    change_id: ChangeId,
    known: &mut K,
) -> bool
where
    K: FnMut(Hash) -> bool,
{
    let mut deleted_by_unknown = false;
    for v in iter_deleted_parents(txn, channel, source) {
        if v.dest.change.is_root() || v.introduced_by.is_root() {
            continue;
        }
        if v.introduced_by == change_id || known(txn.get_external(v.introduced_by).unwrap()) {
            // If a known change also delete the context, we're good.
            return false;
        } else {
            // If an unknown change deletes the context, wait: maybe a
            // known change will delete it too.
            deleted_by_unknown = true;
        }
    }
    deleted_by_unknown

    if e.flag.contains(EdgeFlags::FOLDER) {
        return Ok(());
    }

    let end_pos = internal_pos(txn, &e.to.end_pos(), change_id)?;

        if dest_vertex.end < end_pos.pos {

        if dest_vertex.end < e.to.end {

    pub(crate) graphs:
        HashMap<Position<Option<Hash>>, (Graph, HashMap<Vertex<ChangeId>, crate::alive::VertexId>)>,

    pub(crate) graphs: Graphs,

    pub(crate) files: HashSet<Vertex<ChangeId>>,

#[derive(Debug, Default)]
pub(crate) struct Graphs(
    pub HashMap<Position<Option<Hash>>, (Graph, HashMap<Vertex<ChangeId>, crate::alive::VertexId>)>,
);
impl Graphs {
    pub(crate) fn get(
        &self,
        inode: Position<Option<Hash>>,
    ) -> Result<&(Graph, HashMap<Vertex<ChangeId>, VertexId>), InconsistentChange> {
        if let Some(n) = self.0.get(&inode) {
            Ok(n)
        } else {
            Err(InconsistentChange {})
        }
    }
    pub fn split(
        &mut self,
        inode: Position<Option<Hash>>,
        vertex: Vertex<ChangeId>,
        mid: ChangePosition,
    ) {
        if let Some((_, vids)) = self.0.get_mut(&inode) {
            if let Some(vid) = vids.remove(&vertex) {
                vids.insert(Vertex { end: mid, ..vertex }, vid);
                vids.insert(
                    Vertex {
                        start: mid,
                        ..vertex
                    },
                    vid,
                );
            }
        }
    }
}

        self.graphs.clear();

        self.graphs.0.clear();

        assert!(self.graphs.is_empty());

        assert!(self.graphs.0.is_empty());

    for v in iter_adjacent(
        txn,
        channel,
        dest_vertex,
        EdgeFlags::empty(),
        EdgeFlags::all() - EdgeFlags::DELETED - EdgeFlags::PARENT,
    ) {

    for v in iter_alive_children(txn, channel, dest_vertex) {

        // If `dest_vertex` is not also deleted by the same change
        // that introduced unknown edge `v`, then `v` is really
        // a missing context.

            // This unwrap is ok, since `v` is in the channel.

    if unknown.is_empty() {
        trace!("unknown = []")
    } else {
        debug!("dest_vertex = {:?}, unknown = {:?}", dest_vertex, unknown)
    }

    debug!("dest_vertex = {:?}, unknown = {:?}", dest_vertex, unknown);

        if !edge.flag.contains(EdgeFlags::FOLDER) {
            debug!("dest_vertex {:?}, p {:?}", dest_vertex, p);
            put_graph_with_rev(
                txn,
                channel,
                EdgeFlags::DELETED | EdgeFlags::BLOCK,
                dest_vertex,
                p,
                change_id,
            )

        assert!(!edge.flag.contains(EdgeFlags::FOLDER));
        debug!("dest_vertex {:?}, p {:?}", dest_vertex, p);
        put_graph_with_rev(txn, channel, EdgeFlags::db(), dest_vertex, p, change_id)

            let mut u = p;
            while let Ok(v) = find_block(txn, channel, u.end_pos()) {
                if u != v {
                    debug!("repair_children_of_deleted: {:?} -> {:?}", u, v);
                    put_graph_with_rev(
                        txn,
                        channel,
                        EdgeFlags::DELETED | EdgeFlags::BLOCK,
                        u,
                        v,
                        change_id,
                    )

        let mut u = p;
        while let Ok(v) = find_block(txn, channel, u.end_pos()) {
            if u != v {
                debug!("repair_children_of_deleted: {:?} -> {:?}", u, v);
                put_graph_with_rev(txn, channel, EdgeFlags::db(), u, v, change_id)

                    u = v
                } else {
                    break;
                }

                u = v
            } else {
                break;

        if is_alive(txn, channel, p) || edge.flag.contains(EdgeFlags::FOLDER) {
            let p_is_folder = edge.flag.contains(EdgeFlags::FOLDER);
            repair_missing_up_context(txn, channel, ws, inode, dest_vertex, &[p], p_is_folder)?;

        if is_alive(txn, channel, p) {
            repair_missing_up_context(txn, channel, ws, change_id, inode, dest_vertex, &[p])?;

            repair_missing_up_context(txn, channel, ws, inode, dest_vertex, &alive, false)?;

            repair_missing_up_context(txn, channel, ws, change_id, inode, dest_vertex, &alive)?;

    for (dest_vertex, e) in ws.pseudo.drain(..) {

    for (dest_vertex, mut e) in ws.pseudo.drain(..) {

                    del_graph_with_rev(
                        txn,
                        channel,
                        e.flag - EdgeFlags::PARENT,
                        p,
                        dest_vertex,
                        e.introduced_by,
                    )
                    .map_err(MissingError::Txn)?;

                    e.flag -= EdgeFlags::PARENT;
                    del_graph_with_rev(txn, channel, e.flag, p, dest_vertex, e.introduced_by)
                        .map_err(MissingError::Txn)?;

        for v in iter_adjacent(txn, &channel, vertex, EdgeFlags::empty(), EdgeFlags::all()) {

        for v in iter_adj_all(txn, &channel, vertex) {

    files: &mut HashSet<Vertex<ChangeId>>,

) -> Result<(HashSet<Vertex<ChangeId>>, Vec<(Vertex<ChangeId>, Edge)>), BlockError> {

    change: ChangeId,
) -> Result<HashSet<Vertex<ChangeId>>, BlockError> {

    let mut files = Vec::new();

        let mut next_file = None;
        for v in iter_adjacent(txn, &channel, vertex, EdgeFlags::PARENT, EdgeFlags::all()) {

        let mut is_file = false;
        let mut it = iter_adj_all(txn, &channel, vertex);
        while let Some(v) = it.next() {

            if !v.flag.contains(EdgeFlags::PARENT) || v.flag.contains(EdgeFlags::PSEUDO) {

            if !v.flag.is_parent() {
                is_file |= !v.flag.is_folder();

            if !v.flag.contains(EdgeFlags::DELETED) {
                if v.flag.contains(EdgeFlags::FOLDER) {
                    // check whether `vertex` is a "file" inode,
                    // i.e. if it has non-folder children. We're never
                    // in the case of an empty file if we call this
                    // function.
                    if next_file.is_none()
                        && iter_adjacent(
                            txn,
                            &channel,
                            vertex,
                            EdgeFlags::empty(),
                            EdgeFlags::all(),
                        )
                        .any(|e| {
                            e.flag.contains(EdgeFlags::BLOCK)
                                && !e.flag.contains(EdgeFlags::PARENT)
                                && !e.flag.contains(EdgeFlags::FOLDER)
                        })
                    {

            if v.flag & EdgeFlags::pseudof() == EdgeFlags::PSEUDO {
                continue;
            }
            if !v.flag.is_deleted() {
                if v.flag.is_folder() {
                    is_file |= it.any(|e| !e.flag.intersects(EdgeFlags::parent_folder()));
                    if is_file {

                        files.insert(vertex);

                    next_file = None;

                    break;

                    if v.introduced_by != change {
                        stack.truncate(elt_index);
                        break;
                    }

                stack.truncate(elt_index);
                break;

            if v.flag.contains(EdgeFlags::FOLDER) {
                let v_age = txn
                    .get_changeset(&channel.changes, v.introduced_by, None)
                    .unwrap();
                if let Some((ref mut file, ref mut age)) = next_file {
                    if v_age > *age {
                        *age = v_age;
                        *file = (vertex, v)
                    }
                } else {
                    next_file = Some(((vertex, v), v_age));
                    // If `vertex` is a "file" inode (as opposed to a
                    // "folder" inode), mark it "alive".
                    if iter_adjacent(txn, &channel, vertex, EdgeFlags::empty(), EdgeFlags::all())
                        .any(|e| {
                            !e.flag.contains(EdgeFlags::PARENT)
                                && !e.flag.contains(EdgeFlags::FOLDER)
                        })
                    {
                        alive.insert(vertex);
                    }

            if v.flag.is_folder() {
                if is_file {
                    alive.insert(vertex);
                    files.insert(vertex);

                break;

        }
        if let Some((file, _)) = next_file {
            files.push(file);
            stack.push(file.1)

        debug!("is_file = {:?}", is_file);

    Ok((alive, files))

    Ok(alive)

            flag: previous | EdgeFlags::BLOCK | EdgeFlags::DELETED,

            flag: previous | EdgeFlags::DELETED,

}
impl<T: Clone> NewEdge<T> {
    pub(crate) fn reverse(&self, introduced_by: T) -> Self {
        NewEdge {
            previous: self.flag,
            flag: self.previous,
            from: self.from.clone(),
            to: self.to.clone(),
            introduced_by,
        }
    }

    for edge in iter_adjacent(txn, channel, from, EdgeFlags::empty(), EdgeFlags::all()) {

    for edge in iter_adj_all(txn, channel, from) {

        for edge in iter_adjacent(txn, channel, to, EdgeFlags::empty(), EdgeFlags::all()) {

        for edge in iter_adj_all(txn, channel, to) {

                            v.flag = EdgeFlags::BLOCK;

use crate::change::{Atom, Change, NewEdge, NewVertex};

use crate::change::{Atom, Change, EdgeMap, NewEdge, NewVertex};

impl<E: std::error::Error> LocalApplyError<E> {
    const INCONSISTENT: Self =
        LocalApplyError::InconsistentChange(crate::pristine::InconsistentChange {});
}

                            )?

                            )?;

    clean_obsolete_pseudo_edges(txn, channel, ws)?;

    clean_obsolete_pseudo_edges(txn, channel, ws, change_id)?;

    repair_cyclic_paths(txn, channel, ws, change_id, change)?;

    repair_cyclic_paths(txn, channel, ws)?;

    if let Ok(duration) =
        std::time::SystemTime::now().duration_since(std::time::SystemTime::UNIX_EPOCH)
    {
        channel.last_modified = duration.as_secs();
    }

    channel.touch();

        put_up_context(txn, channel, ch, n.inode, ws, up)?;

        if put_up_context(txn, channel, ch, ws, up)? && n.flag.contains(EdgeFlags::FOLDER) {
            return Err(LocalApplyError::INCONSISTENT);
        }

        put_down_context(txn, channel, ch, n.inode, ws, down)?;

        if down.change == change {
            return Err((InconsistentChange {}).into());
        }
        if put_down_context(txn, channel, ch, ws, down)? && !n.flag.contains(EdgeFlags::FOLDER) {
            return Err(LocalApplyError::INCONSISTENT);
        }

    let up_flag = n.flag | EdgeFlags::BLOCK | EdgeFlags::DELETED;

            for (change, _) in ws.deleted_by.iter() {
                let flag = n.flag | EdgeFlags::BLOCK | EdgeFlags::DELETED;
                put_graph_with_rev(txn, channel, flag, up, vertex, *change)

            for change in ws.deleted_by.iter() {
                put_graph_with_rev(txn, channel, up_flag, up, vertex, *change)

        debug!("put_graph_with_rev {:?} {:?}", up, vertex);
        let flag = if n.flag.contains(EdgeFlags::FOLDER) || !vertex.is_empty() {
            n.flag | EdgeFlags::BLOCK
        } else {
            n.flag - EdgeFlags::BLOCK
        };
        put_graph_with_rev(txn, channel, flag, up, vertex, change).map_err(LocalApplyError::Txn)?;

        put_graph_with_rev(txn, channel, n.flag | EdgeFlags::BLOCK, up, vertex, change)
            .map_err(LocalApplyError::Txn)?;

    let mut down_flag = n.flag;
    if !n.flag.is_folder() {
        down_flag -= EdgeFlags::BLOCK
    }

        if n.flag.contains(EdgeFlags::FOLDER) {
            put_graph_with_rev(
                txn,
                channel,
                n.flag | EdgeFlags::BLOCK,
                vertex,
                down,
                change,
            )

        put_graph_with_rev(txn, channel, down_flag, vertex, down, change)

        } else {
            put_graph_with_rev(
                txn,
                channel,
                n.flag - EdgeFlags::BLOCK,
                vertex,
                down,
                change,
            )
            .map_err(LocalApplyError::Txn)?;

        if n.flag.is_folder() {
            ws.missing_context.files.insert(down);

    inode: Position<Option<Hash>>,

) -> Result<(), LocalApplyError<T::Error>> {

) -> Result<bool, LocalApplyError<T::Error>> {

            if let Some((_, vids)) = ws.missing_context.graphs.get_mut(&inode) {
                if let Some(vid) = vids.remove(&k) {
                    vids.insert(Vertex { end: up.pos, ..k }, vid);
                    vids.insert(Vertex { start: up.pos, ..k }, vid);
                }
            }

            // The missing context "graphs" are only used at the
            // DELETION stage, check that:
            assert!(ws.missing_context.graphs.0.is_empty());

    let mut is_non_folder = false;

        is_non_folder |= parent.flag & (EdgeFlags::PARENT | EdgeFlags::FOLDER) == EdgeFlags::PARENT;

            // This unwrap is ok: `parent` is in the channel.

                ws.deleted_by
                    .insert((parent.introduced_by, parent.flag - EdgeFlags::PARENT));

                ws.deleted_by.insert(parent.introduced_by);

        } else if parent.flag.contains(EdgeFlags::PARENT | EdgeFlags::BLOCK) {
            // This vertex is alive, even if its parent is in conflict.
            debug!("up_context: alive {:?} {:?}", up_vertex, parent);
            break;

    Ok(())

    Ok(is_non_folder)

    inode: Position<Option<Hash>>,

) -> Result<Vertex<ChangeId>, LocalApplyError<T::Error>> {

) -> Result<bool, LocalApplyError<T::Error>> {

        if let Some((_, vids)) = ws.missing_context.graphs.get_mut(&inode) {
            if let Some(vid) = vids.remove(&k) {
                vids.insert(Vertex { end: down.pos, ..k }, vid);
                vids.insert(
                    Vertex {
                        start: down.pos,
                        ..k
                    },
                    vid,
                );
            }
        }

        // The missing context "graphs" are only used at the
        // DELETION stage, check that:
        assert!(ws.missing_context.graphs.0.is_empty());

    let mut is_folder = false;

        is_folder |= parent.flag.contains(EdgeFlags::PARENT | EdgeFlags::FOLDER);

                // This unwrap is ok: `parent` is in the channel.

                    ws.deleted_by
                        .insert((parent.introduced_by, parent.flag - EdgeFlags::PARENT));

                    ws.deleted_by.insert(parent.introduced_by);

            } else {
                // This parent is alive
                break;

    Ok(down_vertex)

    Ok(is_folder)

    deleted_by: HashSet<(ChangeId, EdgeFlags)>,

    deleted_by: HashSet<ChangeId>,

    debug!("put_newedge {:?} {:?}", n, change);

    if (n.previous.is_block() != n.flag.is_block())
        || (n.previous.is_folder() != n.flag.is_folder())
    {
        return Err(LocalApplyError::INCONSISTENT.into());
    }

    assert!(ws.children.is_empty());
    assert!(ws.parents.is_empty());
    debug!("put_newedge {:?} {:?}", n, change);

    debug_assert!(ws.children.is_empty());
    debug_assert!(ws.parents.is_empty());

        return Err(
            LocalApplyError::InconsistentChange(crate::pristine::InconsistentChange {}).into(),
        );

        return Err(LocalApplyError::INCONSISTENT.into());

    if n.flag.contains(EdgeFlags::FOLDER) {
        ws.missing_context.files.insert(target);
    }

            if let Some((_, vids)) = ws.missing_context.graphs.get_mut(&inode) {
                if let Some(vid) = vids.remove(&target) {
                    vids.insert(
                        Vertex {
                            end: n.to.end,
                            ..target
                        },
                        vid,
                    );
                    vids.insert(
                        Vertex {
                            start: n.to.end,
                            ..target
                        },
                        vid,
                    );
                }
            }

            ws.missing_context.graphs.split(inode, target, n.to.end);

            ws.parents.clear();

        debug!("deleting {:?} {:?}", n.previous, n.flag);
        let del = del_graph_with_rev(txn, channel, n.previous, source, target, n_introduced_by)

        del_graph_with_rev(txn, channel, n.previous, source, target, n_introduced_by)

        debug!("deleted: {:?}", del);
        debug!("put_graph {:?} {:?}, intro {:?}", source, target, change);
        assert_ne!(source, target);

            assert_eq!(target.end, n.to.end);

            debug!("{:?} {:?}", target, n.to);
            debug_assert_eq!(target.end, n.to.end);

        if let Some((_, vids)) = ws.missing_context.graphs.get_mut(&inode) {
            if let Some(vid) = vids.remove(&source) {
                vids.insert(
                    Vertex {
                        end: from.pos,
                        ..source
                    },
                    vid,
                );
                vids.insert(
                    Vertex {
                        start: from.pos,
                        ..source
                    },
                    vid,
                );
            }
        }

        ws.missing_context.graphs.split(inode, source, from.pos);

    debug!("find_target_vertex");

    debug!("find_target_vertex, to = {:?}", to);

        if let Some((_, vids)) = ws.missing_context.graphs.get_mut(&inode) {
            if let Some(vid) = vids.remove(&target) {
                vids.insert(
                    Vertex {
                        end: to.start,
                        ..target
                    },
                    vid,
                );
                vids.insert(
                    Vertex {
                        start: to.start,
                        ..target
                    },
                    vid,
                );
            }
        }

        ws.missing_context.graphs.split(inode, target, to.start);

    debug!(
        "reconnect: parents.len() = {:?} to children.len() = {:?}",
        ws.parents.len(),
        ws.children.len()
    );
    debug!(
        "reconnect: parents = {:#?} to children = {:#?}",
        ws.parents, ws.children
    );
    if ws.parents.is_empty() {
        ws.children.clear();

    if ws.parents.is_empty() || ws.children.is_empty() {

    if ws.children.is_empty() {
        ws.parents.clear();
        return Ok(());
    }

    let (graph, vids) = ws.missing_context.graphs.get(inode)?;

    let (graph, vids) = if let Some(n) = ws.missing_context.graphs.get(&inode) {
        n
    } else {
        return Err((InconsistentChange {}).into());
    };

    debug!(
        "reconnect (nonredundant) {:?} to {:?}",
        ws.parents, ws.children
    );

    for p in ws.parents.drain() {
        for c in ws.children.iter() {
            if p != *c && is_alive(txn, channel, p) && is_alive(txn, channel, *c) {
                put_graph_with_rev(txn, channel, EdgeFlags::PSEUDO, p, *c, ChangeId::ROOT)

    for &p in ws.parents.iter() {
        debug_assert!(is_alive(txn, channel, p));
        for &c in ws.children.iter() {
            if p != c {
                debug_assert!(is_alive(txn, channel, c));
                put_graph_with_rev(txn, channel, EdgeFlags::PSEUDO, p, c, ChangeId::ROOT)

    change_id: ChangeId,

    debug!("pseudo = {:#?}", ws.pseudo);

        // Reorder next_vertex and p.dest to reformulate this as an "a -> b" edge.
        debug!("{:?} {:?}", next_vertex, p);
        let (a, b) = if p.flag.contains(EdgeFlags::PARENT) {

        let (a, b) = if p.flag.is_parent() {

        debug!("{:?} {:?}", a_is_alive, b_is_alive);

        if a_is_alive && b_is_alive {
            continue;
        }
        del_graph_with_rev(
            txn,
            channel,
            p.flag - EdgeFlags::PARENT,
            a,
            b,
            p.introduced_by,
        )
        .map_err(LocalApplyError::Txn)?;

            if !b_is_alive {
                debug!("deleting {:?} -> {:?}", a, b);
                if del_graph_with_rev(
                    txn,
                    channel,
                    p.flag - EdgeFlags::PARENT,
                    a,
                    b,
                    p.introduced_by,
                )
                .map_err(LocalApplyError::Txn)?
                {
                    // repair down context.
                    crate::missing_context::repair_missing_down_context(
                        txn,
                        channel,
                        &mut ws.missing_context,
                        inode,
                        b,
                        &[a],
                    )
                    .map_err(LocalApplyError::from_missing)?
                }
            }
        } else if b_is_alive {
            debug!("deleting {:?} -> {:?}", a, b);
            if del_graph_with_rev(

            debug_assert!(!b_is_alive);
            crate::missing_context::repair_missing_down_context(

                p.flag - EdgeFlags::PARENT,
                a,

                &mut ws.missing_context,
                inode,

                p.introduced_by,

                &[a],

            .map_err(LocalApplyError::Txn)?
            {
                // repair up context.
                crate::missing_context::repair_missing_up_context(
                    txn,
                    channel,
                    &mut ws.missing_context,
                    inode,
                    a,
                    &[b],
                    p.flag.contains(EdgeFlags::FOLDER),
                )
                .map_err(LocalApplyError::from_missing)?
            }
        } else {
            del_graph_with_rev(

            .map_err(LocalApplyError::from_missing)?
        } else if !p.flag.is_folder() {
            crate::missing_context::repair_missing_up_context(

                p.flag - EdgeFlags::PARENT,

                &mut ws.missing_context,
                change_id,
                inode,

                b,
                p.introduced_by,

                &[b],

            .map_err(LocalApplyError::Txn)?;

            .map_err(LocalApplyError::from_missing)?

            Atom::NewVertex(ref n) => {

            Atom::NewVertex(ref n) if !n.flag.is_folder() => {

                debug!("repairing missing context for {:?}", vertex);
                for up in n.up_context.iter() {
                    let up = find_block_end(txn, channel, internal_pos(txn, &up, change_id)?)?;
                    if !is_alive(txn, channel, up) {
                        debug!("repairing missing up context {:?} {:?}", up, vertex);
                        repair_missing_up_context(
                            txn,
                            channel,
                            &mut ws.missing_context,
                            n.inode,
                            up,
                            &[vertex],
                            n.flag.contains(EdgeFlags::FOLDER),
                        )
                        .map_err(LocalApplyError::from_missing)?
                    }
                }
                if !n.flag.contains(EdgeFlags::FOLDER) {
                    for down in n.down_context.iter() {
                        let down = find_block(txn, channel, internal_pos(txn, &down, change_id)?)?;
                        if iter_adjacent(
                            txn,
                            channel,
                            down,
                            EdgeFlags::PARENT,
                            EdgeFlags::all() - EdgeFlags::DELETED,
                        )
                        .find(|e| e.introduced_by != change_id)
                        .is_none()
                        {
                            debug!("repairing missing down context {:?} {:?}", down, vertex);
                            repair_missing_down_context(
                                txn,
                                channel,
                                &mut ws.missing_context,
                                n.inode,
                                down,
                                &[vertex],
                            )
                            .map_err(LocalApplyError::from_missing)?
                        }
                    }
                }
                debug!("done repairing contexts for {:?}", vertex);

                repair_new_vertex_context_up(txn, channel, ws, change_id, n, vertex)?;
                repair_new_vertex_context_down(txn, channel, ws, change_id, n, vertex)?;

            Atom::NewVertex(_) => {}

                for e in n.edges.iter() {
                    assert!(!e.flag.contains(EdgeFlags::PARENT));
                    if !e.flag.contains(EdgeFlags::DELETED) {
                        trace!("repairing context nondeleted {:?}", e);
                        repair_context_nondeleted(
                            txn,
                            channel,
                            &mut ws.missing_context,
                            n.inode,
                            change_id,
                            |h| change.knows(&h),
                            e,
                        )
                        .map_err(LocalApplyError::from_missing)?
                    }
                }

                repair_edge_context(txn, channel, ws, change_id, change, n)?;

    for atom in change.changes.iter().flat_map(|r| r.iter()) {
        if let Atom::EdgeMap(ref n) = atom {
            for e in &n.edges {
                if e.flag.contains(EdgeFlags::DELETED) {
                    trace!("repairing context deleted {:?}", e);
                    repair_context_deleted(
                        txn,
                        channel,
                        &mut ws.missing_context,
                        n.inode,
                        change_id,
                        |h| change.knows(&h),
                        e,
                    )
                    .map_err(LocalApplyError::from_missing)?
                }
            }
        }
    }

fn repair_cyclic_paths<T: MutTxnT>(

fn repair_new_vertex_context_up<T: MutTxnT>(
    txn: &mut T,
    channel: &mut Channel<T>,
    ws: &mut Workspace,
    change_id: ChangeId,
    n: &NewVertex<Option<Hash>>,
    vertex: Vertex<ChangeId>,
) -> Result<(), LocalApplyError<T::Error>> {
    for up in n.up_context.iter() {
        let up = find_block_end(txn, channel, internal_pos(txn, &up, change_id)?)?;
        if !is_alive(txn, channel, up) {
            debug!("repairing missing up context {:?} {:?}", up, vertex);
            repair_missing_up_context(
                txn,
                channel,
                &mut ws.missing_context,
                change_id,
                n.inode,
                up,
                &[vertex],
            )
            .map_err(LocalApplyError::from_missing)?
        }
    }
    Ok(())
}
fn repair_new_vertex_context_down<T: MutTxnT>(
    txn: &mut T,
    channel: &mut Channel<T>,
    ws: &mut Workspace,
    change_id: ChangeId,
    n: &NewVertex<Option<Hash>>,
    vertex: Vertex<ChangeId>,
) -> Result<(), LocalApplyError<T::Error>> {
    debug!("repairing missing context for {:?}", vertex);
    if n.flag.contains(EdgeFlags::FOLDER) {
        return Ok(());
    }
    for down in n.down_context.iter() {
        let down = find_block(txn, channel, internal_pos(txn, &down, change_id)?)?;
        if iter_adjacent(
            txn,
            channel,
            down,
            EdgeFlags::PARENT,
            EdgeFlags::all() - EdgeFlags::DELETED,
        )
        .any(|e| e.introduced_by != change_id)
        {
            continue;
        }
        debug!("repairing missing down context {:?} {:?}", down, vertex);
        repair_missing_down_context(
            txn,
            channel,
            &mut ws.missing_context,
            n.inode,
            down,
            &[vertex],
        )
        .map_err(LocalApplyError::from_missing)?
    }
    Ok(())
}
fn repair_edge_context<T: MutTxnT>(

    n: &EdgeMap<Option<Hash>>,
) -> Result<(), LocalApplyError<T::Error>> {
    for e in n.edges.iter() {
        assert!(!e.flag.contains(EdgeFlags::PARENT));
        if e.flag.contains(EdgeFlags::DELETED) {
            trace!("repairing context deleted {:?}", e);
            repair_context_deleted(
                txn,
                channel,
                &mut ws.missing_context,
                n.inode,
                change_id,
                |h| change.knows(&h),
                e,
            )
            .map_err(LocalApplyError::from_missing)?
        } else {
            trace!("repairing context nondeleted {:?}", e);
            repair_context_nondeleted(
                txn,
                channel,
                &mut ws.missing_context,
                n.inode,
                change_id,
                |h| change.knows(&h),
                e,
            )
            .map_err(LocalApplyError::from_missing)?
        }
    }
    Ok(())
}
pub(crate) fn repair_cyclic_paths<T: MutTxnT>(
    txn: &mut T,
    channel: &mut Channel<T>,
    ws: &mut Workspace,

    for atom in change.changes.iter().flat_map(|r| r.iter()) {
        if let Atom::EdgeMap(ref n) = atom {
            for e in n.edges.iter() {
                assert!(!e.flag.contains(EdgeFlags::PARENT));
                if e.flag.contains(EdgeFlags::FOLDER | EdgeFlags::DELETED) && e.to.len() > 0 {
                    repair_edge(txn, channel, e, change_id, ws)?;

    let mut files = std::mem::replace(&mut ws.missing_context.files, HashSet::new());
    for file in files.drain() {
        if file.is_empty() {
            if !is_rooted(txn, channel, file, ws)? {
                repair_edge(txn, channel, file, ws)?
            }
        } else {
            let f0 = EdgeFlags::FOLDER;
            let f1 = EdgeFlags::FOLDER | EdgeFlags::BLOCK | EdgeFlags::PSEUDO;
            if let Some(ee) = iter_adjacent(txn, channel, file, f0, f1).next() {
                let dest = ee.dest.inode_vertex();
                if !is_rooted(txn, channel, dest, ws)? {
                    repair_edge(txn, channel, dest, ws)?

    ws.missing_context.files = files;

    e: &NewEdge<Option<Hash>>,
    change_id: ChangeId,

    to0: Vertex<ChangeId>,

    // If we're deleting a name and not a whole file.
    let h = if let Some(h) = e.to.change {
        h
    } else {
        return Ok(());
    };
    let to = Vertex {
        change: if let Some(h) = txn.get_internal(h) {
            h

    debug!("repair_edge {:?}", to0);
    let mut stack = vec![(to0, true, true, true)];
    ws.parents.clear();
    while let Some((current, _, al, anc_al)) = stack.pop() {
        if !ws.parents.insert(current) {
            continue;
        }
        debug!("repair_cyclic {:?}", current);
        if current != to0 {
            stack.push((current, true, al, anc_al));
        }
        if current.is_root() {
            debug!("root");
            break;
        }
        if let Some(&true) = ws.rooted.get(&current) {
            debug!("rooted");
            break;
        }
        let f = EdgeFlags::PARENT | EdgeFlags::FOLDER;
        let len = stack.len();
        for parent in iter_adjacent(txn, channel, current, f, EdgeFlags::all()) {
            if parent.flag.is_parent() {
                let anc = find_block_end(txn, channel, parent.dest)?;
                debug!("is_rooted, parent = {:?}", parent);
                let al = iter_adjacent(
                    txn,
                    channel,
                    anc,
                    f,
                    f | EdgeFlags::BLOCK | EdgeFlags::PSEUDO,
                )
                .next()
                .is_some();
                debug!("al = {:?}, flag = {:?}", al, parent.flag);
                stack.push((anc, false, parent.flag.is_deleted(), al));
            }
        }
        if stack.len() == len {
            stack.pop();

            return Err((crate::pristine::InconsistentChange {}).into());
        },
        start: e.to.start,
        end: e.to.end,
    };
    // Check that the inode descendant of this name is rooted.
    let mut unrooted = false;
    let f0 = EdgeFlags::FOLDER;
    let f1 = EdgeFlags::FOLDER | EdgeFlags::BLOCK | EdgeFlags::PSEUDO;
    for ee in iter_adjacent(txn, channel, to, f0, f1) {
        if !is_rooted(txn, channel, ee.dest.inode_vertex(), ws)? {
            unrooted = true;

            (&mut stack[len..]).sort_unstable_by(|a, b| a.3.cmp(&b.3))

    // If not, repair.
    if unrooted {
        let from = find_block_end(txn, channel, internal_pos(txn, &e.from, change_id)?)?;
        debug!("repairing unrooted: {:?} {:?}", from, to);
        put_graph_with_rev(
            txn,
            channel,
            EdgeFlags::FOLDER | EdgeFlags::PSEUDO,
            from,
            to,
            ChangeId::ROOT,
        )
        .map_err(LocalApplyError::Txn)?;

    let mut current = to0;
    for (next, on_path, del, _) in stack {
        if on_path {
            if del {
                put_graph_with_rev(
                    txn,
                    channel,
                    EdgeFlags::FOLDER | EdgeFlags::PSEUDO,
                    next,
                    current,
                    ChangeId::ROOT,
                )
                .map_err(LocalApplyError::Txn)?;
            }
            current = next
        }

    let mut alive = false;
    assert!(v.is_empty());
    for e in iter_adjacent(txn, channel, v, EdgeFlags::empty(), EdgeFlags::all()) {
        if e.flag.contains(EdgeFlags::PARENT) {
            if e.flag & (EdgeFlags::FOLDER | EdgeFlags::DELETED) == EdgeFlags::FOLDER {
                alive = true;
                break;
            }
        } else if !e.flag.is_deleted() {
            alive = true;
            break;
        }
    }
    if !alive {
        debug!("is_rooted, not alive");
        return Ok(true);
    }

            let parent = find_block_end(txn, channel, parent.dest)?;
            stack.push(parent)

            stack.push(find_block_end(txn, channel, parent.dest)?)