libpijul 0.12.0

use backend::*;
use graph;
use graph::Graph;
use patch;
use patch::{Change, ChangeContext, Record};
use {GenericTxn, Result};
use fs_representation::RepoPath;

use conflict;
use diffs;
use rand;
use record::is_text;
use sanakirja::value::Value;
use std;
use std::collections::{HashMap, HashSet};
use std::path::PathBuf;
use std::rc::Rc;

#[derive(Debug, PartialEq, Eq, Hash)]
struct Line<'a>(&'a [u8]);

struct Contents<'a, T: Transaction + 'a> {
    key: Key<PatchId>,
    contents: Value<'a, T>,
    before_conflict_line: bool,
}

impl<'a, T: Transaction + 'a> std::fmt::Debug for Contents<'a, T> {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(
            f,
            "Contents {{ key: {:?}, before_conflict_line: {:?}, {:?} }}",
            self.key,
            self.before_conflict_line,
            self.contents.into_cow()
        )
    }
}

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
enum Status {
    Begin,
    Next,
    End,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Algorithm {
    Myers,
    Patience,
}

impl Default for Algorithm {
    fn default() -> Self {
        Algorithm::Myers
    }
}

struct Diff<'a, 'b, T: Transaction + 'a> {
    conflicts_a: Vec<(usize, usize, bool)>,
    lines_a: Vec<Key<PatchId>>,
    contents_a: Vec<Contents<'a, T>>,
    lines_b: &'b [Line<'b>],
    conflict_starts: HashMap<usize, usize>,
    conflict_ends: HashMap<usize, usize>,
    conflict_down_contexts: HashMap<usize, Vec<LineId>>,
    status: HashMap<usize, Status>,
    conflict_stack: Vec<(usize, usize, bool)>,
    conflict_counter: usize,
    solved_conflicts: HashSet<usize>,
}

impl<'a, 'b, T: Transaction + 'a> graph::LineBuffer<'a, T> for Diff<'a, 'b, T> {
    fn output_line(&mut self, k: &Key<PatchId>, c: Value<'a, T>) -> Result<()> {
        if c.len() != 0 {
            self.conflicts_a.push(*self.conflict_stack.last().unwrap());
            self.lines_a.push(*k);
            self.contents_a.push(Contents {
                key: *k,
                contents: c,
                before_conflict_line: false,
            });
        }
        Ok(())
    }

    fn begin_conflict(&mut self) -> Result<()> {
        let len = self.contents_a.len();
        self.conflict_counter += 1;
        self.conflict_stack.push((self.conflict_counter, 0, false));
        self.conflict_starts.insert(self.conflict_counter, len);
        self.status.insert(len, Status::Begin);
        self.output_conflict_marker(conflict::START_MARKER)
    }

    fn begin_zombie_conflict(&mut self) -> Result<()> {
        let len = self.contents_a.len();
        self.conflict_counter += 1;
        self.conflict_stack.push((self.conflict_counter, 0, true));
        self.conflict_starts.insert(self.conflict_counter, len);
        self.status.insert(len, Status::Begin);
        self.output_conflict_marker(conflict::START_MARKER)
    }

    fn end_conflict(&mut self) -> Result<()> {
        let len = self.contents_a.len();
        self.output_conflict_marker(conflict::END_MARKER)?;
        self.status.insert(len, Status::End);
        let (conflict, _, _) = self.conflict_stack.pop().unwrap();
        self.conflict_ends.insert(conflict, len);
        Ok(())
    }

    fn conflict_next(&mut self) -> Result<()> {
        self.status.insert(self.contents_a.len(), Status::Next);
        if let Some((_, ref mut side, _)) = self.conflict_stack.last_mut() {
            *side += 1
        }
        self.output_conflict_marker(conflict::SEPARATOR)
    }

    fn output_conflict_marker(&mut self, marker: &'a str) -> Result<()> {
        let mut ends_with_newline = true;
        if self.contents_a.len() > 1 {
            for chunk in self.contents_a[self.contents_a.len() - 1].contents.clone() {
                debug!(
                    "chunk {:?} {:?}",
                    std::str::from_utf8(chunk),
                    chunk.ends_with(b"\n")
                );
                ends_with_newline = chunk.ends_with(b"\n")
            }
        };
        debug!("ends_with_newline {:?}", ends_with_newline);
        let (conflict, _, is_zombie) = *self.conflict_stack.last().unwrap();
        self.conflicts_a.push((conflict, 0, is_zombie));
        if let Some(l) = self.contents_a.last_mut() {
            l.before_conflict_line = true
        }
        if ends_with_newline {
            self.lines_a.push(ROOT_KEY);
            self.contents_a.push(Contents {
                key: ROOT_KEY,
                contents: Value::from_slice(&marker.as_bytes()[1..]),
                before_conflict_line: false,
            })
        } else {
            self.lines_a.push(ROOT_KEY);
            self.contents_a.push(Contents {
                key: ROOT_KEY,
                contents: Value::from_slice(marker.as_bytes()),
                before_conflict_line: false,
            });
        }
        Ok(())
    }
}

impl<'a, 'b, T: Transaction + 'b> PartialEq<Contents<'b, T>> for Line<'a> {
    fn eq(&self, b: &Contents<T>) -> bool {
        debug!("comparing {:?} {:?}", self, b);
        if self.0.last() == Some(&0xa) {
            if b.key.is_root() {
                // Conflict
                let b = b.contents.into_cow();
                if b[0] == 0xa {
                    (&self.0[..]).eq(&b[1..])
                } else {
                    (&self.0[..]).eq(&b[..])
                }
            } else if b.before_conflict_line {
                // We might have added an artificial line at the end
                // of a when we output it. Fix this.
                if self.0.len() as u64 - 1 == b.contents.len() {
                    (&self.0[..self.0.len() - 1]).eq(&b.contents)
                } else {
                    self.0.eq(&b.contents)
                }
            } else {
                self.0.eq(&b.contents)
            }
        } else {
            self.0.eq(&b.contents)
        }
    }
}

impl<'b, T: Transaction + 'b> PartialEq<Contents<'b, T>> for Contents<'b, T> {
    fn eq(&self, b: &Contents<T>) -> bool {
        self.contents == b.contents
    }
}
impl<'b, T: Transaction + 'b> Eq for Contents<'b, T> {}
impl<'b, T: Transaction + 'b> std::hash::Hash for Contents<'b, T> {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.contents.hash(state)
    }
}

struct Replace {
    old: usize,
    old_len: usize,
    new: usize,
    new_len: usize,
}
struct D {
    r: Vec<Replace>,
    deleted: HashMap<usize, bool>,
}
impl diffs::Diff for D {
    type Error = ();
    fn delete(&mut self, old: usize, old_len: usize) -> std::result::Result<(), ()> {
        for i in old..old + old_len {
            self.deleted.insert(i, false);
        }
        self.r.push(Replace {
            old,
            old_len,
            new: 0,
            new_len: 0,
        });
        Ok(())
    }
    fn insert(&mut self, old: usize, new: usize, new_len: usize) -> std::result::Result<(), ()> {
        self.r.push(Replace {
            old,
            old_len: 0,
            new,
            new_len,
        });
        Ok(())
    }
    fn replace(
        &mut self,
        old: usize,
        old_len: usize,
        new: usize,
        new_len: usize,
    ) -> std::result::Result<(), ()> {
        for i in old..old + old_len {
            self.deleted.insert(i, true);
        }
        self.r.push(Replace {
            old,
            old_len,
            new,
            new_len,
        });
        Ok(())
    }
}

struct DiffProducer<'a> {
    line_num: &'a mut LineId,
    inode: Key<Option<Hash>>,
    inode_internal: Key<Option<PatchId>>,
    file: Rc<RepoPath<PathBuf>>,
    conflict_insertions: HashMap<usize, LineId>,
}

impl<A: Transaction, R: rand::Rng> GenericTxn<A, R> {
    pub fn diff<'a>(
        &'a self,
        algorithm: Algorithm,
        inode: Key<Option<Hash>>,
        branch: &'a Branch,
        file: Rc<RepoPath<PathBuf>>,
        line_num: &mut LineId,
        actions: &mut Vec<Record<ChangeContext<PatchId>>>,
        redundant: &mut Vec<(Key<PatchId>, Edge)>,
        a: &mut Graph,
        lines_b: &[u8],
    ) -> Result<()> {
        // First outputting A
        let inode_internal = Key {
            patch: Some(
                self.get_internal(inode.patch.as_ref().unwrap().as_ref())
                    .unwrap(),
            ),
            line: inode.line,
        };
        let mut lines_b_ = Vec::new();
        let mut d = Diff {
            lines_a: Vec::with_capacity(2 * lines_b.len()),
            contents_a: Vec::with_capacity(2 * lines_b.len()),
            conflicts_a: Vec::with_capacity(2 * lines_b.len()),
            lines_b: &[],
            conflict_starts: HashMap::new(),
            conflict_ends: HashMap::new(),
            conflict_down_contexts: HashMap::new(),
            status: HashMap::new(),
            conflict_counter: 0,
            conflict_stack: vec![(0, 0, false)],
            solved_conflicts: HashSet::new(),
        };
        self.output_file(branch, &mut d, a, redundant)?;

        // Now cutting B
        if is_text(&lines_b) {
            let mut i = 0;
            let mut j = 0;

            while j < lines_b.len() {
                if lines_b[j] == 0xa {
                    lines_b_.push(Line(&lines_b[i..j + 1]));
                    i = j + 1
                }
                j += 1;
            }
            if i < j {
                lines_b_.push(Line(&lines_b[i..]))
            }
        } else {
            lines_b_.push(Line(&lines_b[..]))
        };
        d.lines_b = &lines_b_;

        // And finally diffing
        let contents_a = std::mem::replace(&mut d.contents_a, Vec::new());
        for line in d.lines_a.iter() {
            debug!("line: {:?}", line);
        }

        trace!(
            "contents_a {:?}",
            contents_a.iter().map(|x| &x.contents).collect::<Vec<_>>()
        );
        trace!("contents_b {:?}", lines_b_);
        let mut dd = diffs::Replace::new(D {
            r: Vec::with_capacity(d.lines_a.len() + lines_b_.len()),
            deleted: HashMap::new(),
        });
        match algorithm {
            Algorithm::Patience => {
                let a = contents_a.as_slice();
                diffs::patience::diff(&mut dd, a, 0, a.len(), &lines_b_, 0, lines_b_.len()).unwrap()
            }
            Algorithm::Myers => {
                let a = contents_a.as_slice();
                diffs::myers::diff(&mut dd, a, 0, a.len(), &lines_b_, 0, lines_b_.len()).unwrap()
            }
        }
        let dd = dd.into_inner();
        let mut diffprod = DiffProducer {
            line_num,
            inode,
            inode_internal,
            file,
            conflict_insertions: HashMap::new(),
        };
        for r in 0..dd.r.len() {
            if dd.r[r].new_len == 0 {
                let old = dd.r[r].old;
                let len = dd.r[r].old_len;
                self.diff_delete(branch, &mut diffprod, actions, &mut d, old, len)
            } else {
                self.diff_replace(branch, &mut diffprod, actions, &mut d, &dd, r)
            }
        }
        debug!("Diff ended");
        Ok(())
    }

    /// Insert epsilon-edges if we're deleting conflict markers.
    fn order_conflict_sides(
        &self,
        branch: &Branch,
        dp: &mut DiffProducer,
        actions: &mut Vec<Record<ChangeContext<PatchId>>>,
        diff: &mut Diff<A>,
        old: usize,
        len: usize,
    ) {
        if !diff.lines_a[old - 1].is_root()
            && !diff.lines_a[old + len].is_root()
            && !self.is_connected(branch, diff.lines_a[old - 1], diff.lines_a[old + len])
        {
            let mut is_conflict = false;
            for i in old..(old + len) {
                match diff.status.get(&i) {
                    Some(&Status::Next) => is_conflict = true,
                    Some(_) => return, // we're not reordering a conflict.
                    _ => {}
                }
            }
            if !is_conflict {
                return;
            }
            let from_patch = diff.lines_a[old - 1];
            let to_patch = diff.lines_a[old + len];
            debug!("Conflict reordering {:?} {:?}", from_patch, to_patch);
            actions.push(Record::Change {
                change: Change::NewNodes {
                    up_context: vec![Key {
                        patch: Some(from_patch.patch),
                        line: from_patch.line,
                    }],
                    down_context: vec![Key {
                        patch: Some(to_patch.patch),
                        line: to_patch.line,
                    }],
                    line_num: *dp.line_num,
                    flag: EdgeFlags::EPSILON_EDGE,
                    nodes: vec![Vec::new()],
                    inode: dp.inode.clone(),
                },
                replacement: None,
                old_line: old,
                new_line: 0,
                file: dp.file.clone(),
            });
            *dp.line_num += 1
        }
    }

    /// Actually delete the lines that need to be deleted.
    fn delete_lines(
        &self,
        branch: &Branch,
        dp: &mut DiffProducer,
        actions: &mut Vec<Record<ChangeContext<PatchId>>>,
        diff: &mut Diff<A>,
        old: usize,
        len: usize,
    ) {
        let mut edges = Vec::new();
        let flag0 = EdgeFlags::PARENT_EDGE;
        let flag1 = EdgeFlags::PARENT_EDGE | EdgeFlags::PSEUDO_EDGE | EdgeFlags::EPSILON_EDGE;

        debug!("Delete_lines {:?} {:?}", old, len);
        for (i, &key) in diff.lines_a[old..(old + len)].iter().enumerate() {
            debug!("status of {:?}: {:?}", old + i, diff.status.get(&(old + i)));
            match diff.status.get(&(old + i)) {
                Some(&Status::Begin) => {
                    diff.solved_conflicts.insert(diff.conflicts_a[old + i].0);
                    continue;
                }
                None => {}
                _ => continue,
            }
            let ext_hash = self.external_hash(key.patch);
            for v in self
                .iter_adjacent(&branch, key, flag0, flag1)
                .filter(|v| !v.flag.contains(EdgeFlags::EPSILON_EDGE))
            {
                if v.flag.contains(EdgeFlags::PSEUDO_EDGE) {
                    let mut edge = v.clone();
                    edge.flag = EdgeFlags::DELETED_EDGE | EdgeFlags::PARENT_EDGE;
                    edge.introduced_by = ROOT_PATCH_ID;
                    let mut edges = self.iter_nodes(&branch, Some((key, Some(edge))));
                    match edges.next() {
                        Some((k_, v_)) if k_ == key && v_.flag == edge.flag => {
                            // `key` has at least one deleted edge
                            // pointing to it, so key is a zombie. We
                            // need to confirm that it is actually
                            // deleted by deleting edge `v`.
                            debug!("zombie edge: {:?} {:?}", key, v);
                        }
                        x => {
                            // The target of this edge is not deleted,
                            // and not a zombie vertex.  We can ignore
                            // this pseudo-edge, as deleting all alive
                            // edges to the target will have the same
                            // effect.
                            debug!("not a zombie: {:?}", x);
                            continue;
                        }
                    }
                };
                debug!("delete: {:?} {:?}", key, v);
                debug!("actually deleting");
                edges.push(patch::NewEdge {
                    from: Key {
                        patch: Some(ext_hash.to_owned()),
                        line: key.line.clone(),
                    },
                    to: Key {
                        patch: Some(self.external_hash(v.dest.patch).to_owned()),
                        line: v.dest.line.clone(),
                    },
                    introduced_by: Some(self.external_hash(v.introduced_by).to_owned()),
                });
            }
        }

        if !edges.is_empty() {
            actions.push(Record::Change {
                change: Change::NewEdges {
                    edges,
                    previous: EdgeFlags::PARENT_EDGE,
                    flag: EdgeFlags::PARENT_EDGE | EdgeFlags::DELETED_EDGE,
                    inode: dp.inode.clone(),
                },
                replacement: None,
                old_line: old,
                new_line: 0,
                file: dp.file.clone(),
            })
        }
    }

    fn resurrect_zombies(
        &self,
        branch: &Branch,
        dp: &mut DiffProducer,
        actions: &mut Vec<Record<ChangeContext<PatchId>>>,
        diff: &mut Diff<A>,
        old: usize,
        len: usize,
    ) {
        // If the conflict markers of zombie lines have been deleted,
        // resurect the zombies.
        let mut i = old + len;
        let mut resurrections = Vec::new();
        let mut dead_parents = Vec::new();
        debug!("Resurrect_zombies {:?} {:?}", old, len);
        while i < diff.lines_a.len() {
            let key = diff.lines_a[i];
            let (conflict, _, is_zombie) = diff.conflicts_a[i];
            debug!("resurrecting {:?} {:?}", key, is_zombie);
            debug!("solved ? {:?} {:?}", conflict, diff.solved_conflicts);
            if is_zombie && !key.is_root() && diff.solved_conflicts.contains(&conflict) {
                // Resurect the zombie, i.e. remove its deleted edges.
                let flag0 = EdgeFlags::PARENT_EDGE | EdgeFlags::DELETED_EDGE;
                let ext_hash = self.external_hash(key.patch);
                for v in self.iter_adjacent(&branch, key, flag0, flag0) {
                    debug!("resurrecting {:?}: {:?}", key, v);
                    let v_hash = self.external_hash(v.dest.patch).to_owned();
                    resurrections.push(patch::NewEdge {
                        from: Key {
                            patch: Some(ext_hash.to_owned()),
                            line: key.line.clone(),
                        },
                        to: Key {
                            patch: Some(v_hash.clone()),
                            line: v.dest.line.clone(),
                        },
                        introduced_by: Some(self.external_hash(v.introduced_by).to_owned()),
                    });
                    // We must re-kill the parents to make sure they
                    // don't get context-fixed when we apply this
                    // patch.
                    for w in self.iter_adjacent(&branch, v.dest, flag0, flag0) {
                        dead_parents.push(patch::NewEdge {
                            from: Key {
                                patch: Some(v_hash.clone()),
                                line: v.dest.line.clone(),
                            },
                            to: Key {
                                patch: Some(self.external_hash(w.dest.patch).to_owned()),
                                line: w.dest.line.clone(),
                            },
                            introduced_by: Some(self.external_hash(w.introduced_by).to_owned()),
                        })
                    }
                }
                i += 1
            } else {
                break;
            }
        }
        if !resurrections.is_empty() {
            actions.push(Record::Change {
                change: Change::NewEdges {
                    edges: resurrections,
                    previous: EdgeFlags::PARENT_EDGE | EdgeFlags::DELETED_EDGE,
                    flag: EdgeFlags::PARENT_EDGE,
                    inode: dp.inode.clone(),
                },
                replacement: None,
                file: dp.file.clone(),
                old_line: old,
                new_line: 0,
            });
        }
        if !dead_parents.is_empty() {
            actions.push(Record::Change {
                change: Change::NewEdges {
                    edges: dead_parents,
                    previous: EdgeFlags::PARENT_EDGE | EdgeFlags::DELETED_EDGE,
                    flag: EdgeFlags::PARENT_EDGE | EdgeFlags::DELETED_EDGE,
                    inode: dp.inode.clone(),
                },
                replacement: None,
                file: dp.file.clone(),
                old_line: old,
                new_line: 0,
            });
        }
    }

    fn diff_delete(
        &self,
        branch: &Branch,
        dp: &mut DiffProducer,
        actions: &mut Vec<Record<ChangeContext<PatchId>>>,
        diff: &mut Diff<A>,
        old: usize,
        len: usize,
    ) {
        debug!("diff_delete {:?} {:?}", old, len);
        if old > 0 && old + len < diff.lines_a.len() {
            self.order_conflict_sides(branch, dp, actions, diff, old, len)
        }

        self.delete_lines(branch, dp, actions, diff, old, len);
        self.resurrect_zombies(branch, dp, actions, diff, old, len);
    }

    fn get_up_context(
        &self,
        dp: &mut DiffProducer,
        diff: &mut Diff<A>,
        old: usize,
    ) -> Vec<Key<Option<PatchId>>> {
        if old == 0 {
            vec![dp.inode_internal]
        } else {
            let mut up_context_idx = old - 1;
            loop {
                debug!(
                    "up_context_idx = {:?} ({:?})",
                    up_context_idx, diff.lines_a[up_context_idx]
                );
                match diff.status.get(&up_context_idx) {
                    None => {
                        break vec![Key {
                            patch: Some(diff.lines_a[up_context_idx].patch),
                            line: diff.lines_a[up_context_idx].line,
                        }];
                    }
                    Some(&Status::Begin) => {
                        let conflict = diff.conflicts_a[up_context_idx].0;
                        if let Some(&line) = dp.conflict_insertions.get(&conflict) {
                            break vec![Key { patch: None, line }];
                        } else if up_context_idx == 0 {
                            break vec![dp.inode_internal];
                        } else {
                            up_context_idx -= 1
                        }
                    }
                    Some(&Status::Next) => {
                        let conflict = diff.conflicts_a[up_context_idx].0;
                        if let Some(&line) = dp.conflict_insertions.get(&conflict) {
                            break vec![Key { patch: None, line }];
                        } else {
                            let conflict = diff.conflicts_a[up_context_idx].0;
                            up_context_idx = *diff.conflict_starts.get(&conflict).unwrap();
                        }
                    }
                    Some(&Status::End) => {
                        // The up context is all the sides above this end marker
                        let conflict = diff.conflicts_a[up_context_idx].0;
                        let conflict_start = *diff.conflict_starts.get(&conflict).unwrap();
                        let mut up_context = Vec::new();

                        if let Some(ref up) = diff.conflict_down_contexts.get(&up_context_idx) {
                            up_context.extend(up.iter().map(|&x| Key {
                                patch: None,
                                line: x,
                            }));
                        }

                        let mut on = true;
                        while up_context_idx > conflict_start {
                            on |= diff.status.get(&up_context_idx).is_some()
                                && diff.conflicts_a[up_context_idx].0 == conflict;
                            if on && diff.status.get(&up_context_idx).is_none() {
                                // This is a real line, add it
                                up_context.push(Key {
                                    patch: Some(diff.lines_a[up_context_idx].patch),
                                    line: diff.lines_a[up_context_idx].line,
                                });
                                on = false
                            }
                            up_context_idx -= 1
                        }
                        assert!(!up_context.is_empty());
                        break up_context;
                    }
                }
            }
        }
    }

    fn get_down_context(
        &self,
        dp: &mut DiffProducer,
        diff: &mut Diff<A>,
        dd: &D,
        old: usize,
        old_len: usize,
        len: usize,
    ) -> Vec<Key<Option<PatchId>>> {
        let mut down_context_idx = old + old_len;
        loop {
            debug!("down_context_idx = {:?}", down_context_idx);
            if down_context_idx >= diff.lines_a.len() {
                break Vec::new();
            }
            debug!(
                "down_context_idx = {:?} ({:?})",
                down_context_idx, diff.lines_a[down_context_idx]
            );
            match diff.status.get(&down_context_idx) {
                None => {
                    break vec![Key {
                        patch: Some(diff.lines_a[down_context_idx].patch),
                        line: diff.lines_a[down_context_idx].line,
                    }];
                }
                Some(&Status::End) => {
                    let mut e = diff
                        .conflict_down_contexts
                        .entry(down_context_idx)
                        .or_insert(Vec::new());
                    e.push(*dp.line_num + (len - 1));
                    down_context_idx += 1
                }
                Some(&Status::Next) => {
                    let conflict = diff.conflicts_a[down_context_idx].0;
                    down_context_idx = *diff.conflict_ends.get(&conflict).unwrap();
                }
                Some(&Status::Begin) => {
                    // The down context is all the sides below this beginning marker
                    let conflict = diff.conflicts_a[down_context_idx].0;
                    dp.conflict_insertions
                        .insert(conflict, *dp.line_num + (len - 1));
                    let conflict_end = *diff.conflict_ends.get(&conflict).unwrap();
                    let mut down_context = Vec::new();
                    let mut on = true;
                    while down_context_idx < conflict_end {
                        on |= diff.status.get(&down_context_idx).is_some()
                            && diff.conflicts_a[down_context_idx].0 == conflict;
                        if on && diff.status.get(&down_context_idx).is_none() {
                            match dd.deleted.get(&down_context_idx) {
                                Some(true) => {
                                    // If the down context line has
                                    // been replaced, we'll insert the
                                    // edge later (when dealing with
                                    // the replacement).
                                    on = false
                                }
                                Some(false) => {
                                    // If the line has been
                                    // deleted, wait for the next
                                    // appropriate down context
                                    // line.
                                }
                                None => {
                                    // If the down context has not
                                    // been deleted, just add it
                                    // as a down context.
                                    down_context.push(Key {
                                        patch: Some(diff.lines_a[down_context_idx].patch),
                                        line: diff.lines_a[down_context_idx].line,
                                    });
                                    on = false
                                }
                            }
                        }
                        down_context_idx += 1
                    }
                    assert!(!down_context.is_empty());
                    break down_context;
                }
            }
        }
    }

    fn diff_replace(
        &self,
        branch: &Branch,
        dp: &mut DiffProducer,
        actions: &mut Vec<Record<ChangeContext<PatchId>>>,
        diff: &mut Diff<A>,
        dd: &D,
        r: usize,
    ) {
        let old = dd.r[r].old;
        let old_len = dd.r[r].old_len;
        let from_new = dd.r[r].new;
        let len = dd.r[r].new_len;
        debug!("replace {:?} {:?} {:?} {:?}", old, old_len, from_new, len);
        if old_len > 0 {
            self.diff_delete(branch, dp, actions, diff, old, old_len);
        }
        // Inserting between old and old+1. Both might be conflict
        // markers.
        let up_context = self.get_up_context(dp, diff, old);
        let down_context = self.get_down_context(dp, diff, dd, old, old_len, len);

        for i in &diff.lines_b[from_new..(from_new + len)] {
            debug!("{:?}", std::str::from_utf8(&i.0));
        }

        let change = Change::NewNodes {
            up_context,
            down_context,
            line_num: *dp.line_num,
            flag: EdgeFlags::empty(),
            nodes: (&diff.lines_b[from_new..(from_new + len)])
                .iter()
                .map(|x| x.0.to_vec())
                .collect(),
            inode: dp.inode.clone(),
        };
        *dp.line_num += len;
        debug!("insert done");

        if old_len > 0 {
            // this is a replacement
            match actions.last_mut() {
                Some(Record::Change {
                    old_line,
                    ref mut replacement,
                    ..
                }) => {
                    if *old_line == old {
                        *replacement = Some(change);
                        return;
                    }
                }
                None => {
                    debug!("We're in a replacement, but no deletion occurred. Conflict solved?");
                }
                e => {
                    error!("{:?}", e);
                    unreachable!()
                }
            }
        }
        // If we didn't include `change` in a replacement, let's
        // include it now.
        actions.push(Record::Change {
            file: dp.file.clone(),
            old_line: old,
            new_line: from_new,
            change,
            replacement: None,
        })
    }
}