A Git import commit costs what it changes 2306a4d24779

use std::collections::HashMap;

/// The lines `old` and `new` keep in common, as (old index, new index) in

/// order: a longest common subsequence, found by Myers' algorithm. A line

/// found on one side only cannot be in it, so such lines are set aside

/// before the diff, as Git's xdiff does: a file rewritten whole (every

/// line ending changed, say) then costs time linear in its length rather

/// than quadratic. Lines are compared as small numbers, not bytes.

fn kept_lines<'a>(old: &[&'a [u8]], new: &[&'a [u8]]) -> Vec<(usize, usize)> {

    let mut ids: HashMap<&'a [u8], u32> = HashMap::new();

    let mut intern = |l: &'a [u8]| -> u32 {

        let next = ids.len() as u32;

        *ids.entry(l).or_insert(next)

    };

    let o: Vec<u32> = old.iter().map(|l| intern(l)).collect();

    let n: Vec<u32> = new.iter().map(|l| intern(l)).collect();

    let mut in_old = vec![false; ids.len()];

    let mut in_new = vec![false; ids.len()];

    for &x in &o {

        in_old[x as usize] = true;

    }

    for &x in &n {

        in_new[x as usize] = true;

    }

    let oi: Vec<usize> = (0..o.len()).filter(|&i| in_new[o[i] as usize]).collect();

    let ni: Vec<usize> = (0..n.len()).filter(|&j| in_old[n[j] as usize]).collect();

    let os: Vec<u32> = oi.iter().map(|&i| o[i]).collect();

    let ns: Vec<u32> = ni.iter().map(|&j| n[j]).collect();

    let mut capture = similar::algorithms::Capture::new();

    let _ = similar::algorithms::myers::diff(&mut capture, &os, 0..os.len(), &ns, 0..ns.len());

    let mut kept = Vec::new();

    for op in capture.into_ops() {

        if let DiffOp::Equal {

            old_index,

            new_index,

            len,

        } = op

        {

            kept.extend((0..len).map(|k| (oi[old_index + k], ni[new_index + k])));

        }

    }

    kept

}

    let keys: Vec<AtomKey> = old.iter().map(|(k, _)| *k).collect();

    text_edits_of(node, &keys, &old_lines, new)

}

/// `text_edits` for live lines given as their atoms and, apart, their

/// text (`old[i]` is the text of `keys[i]`).

pub fn text_edits_of(node: NodeId, keys: &[AtomKey], old_lines: &[&[u8]], new: &[u8]) -> Vec<Edit> {

                change: keys[i - 1].0,

                index: keys[i - 1].1,

        let before = if i >= keys.len() {

                change: keys[i].0,

                index: keys[i].1,

    // Each run of lines between two kept ones is deleted, and the new

    // lines there are inserted where the first deleted line was.

    let (mut i, mut j) = (0, 0);

    let end = (old_lines.len(), new_lines.len());

    for (ki, kj) in kept_lines(old_lines, &new_lines).into_iter().chain([end]) {

        deleted.extend_from_slice(&keys[i..ki]);

        if kj > j {

            let (after, before) = anchor(i);

            inserts.push(Edit::Insert {

                node,

                after,

                before,

                lines: new_lines[j..kj].iter().copied().collect(),

            });

        (i, j) = (ki + 1, kj + 1);

/// One path a commit changes against its first parent: its new mode and

/// blob, or `None` when the commit deletes it.

type TreeDiff = Vec<(String, Option<(String, String)>)>;

/// A running `git diff-tree --stdin`, fed every `commit parent` pair up

/// front, whose diffs are read in the same order as they are needed: a

/// commit's tree is its first parent's plus its diff, at a cost that

/// follows what it changes rather than the whole tree (oxygen#25).

struct DiffTree {

    child: std::process::Child,

    stdout: std::io::BufReader<std::process::ChildStdout>,

    feeder: Option<std::thread::JoinHandle<()>>,

    /// The header read at the end of the previous diff.

    next: Option<String>,

}

impl DiffTree {

    fn start(git_dir: &Path, pairs: Vec<(String, String)>) -> Result<DiffTree> {

        let mut child = Command::new("git")

            .arg("-C")

            .arg(git_dir)

            .args([

                "diff-tree",

                "--stdin",

                "--always",

                "-r",

                "-z",

                "--no-renames",

            ])

            .stdin(Stdio::piped())

            .stdout(Stdio::piped())

            .stderr(Stdio::null())

            .spawn()

            .map_err(|e| RepoError::Msg(format!("running git diff-tree: {e}")))?;

        let mut stdin = child.stdin.take().unwrap();

        let stdout = std::io::BufReader::new(child.stdout.take().unwrap());

        // A thread writes, so git never waits on a full pipe for us to read.

        let feeder = std::thread::spawn(move || {

            let mut w = std::io::BufWriter::new(&mut stdin);

            for (c, p) in pairs {

                if writeln!(w, "{c} {p}").is_err() {

                    return;

                }

            }

            let _ = w.flush();

        });

        Ok(DiffTree {

            child,

            stdout,

            feeder: Some(feeder),

            next: None,

        })

    }

    fn field(&mut self) -> Result<Option<String>> {

        use std::io::BufRead;

        let mut buf = Vec::new();

        if self.stdout.read_until(0, &mut buf)? == 0 {

            return Ok(None);

        }

        if buf.last() == Some(&0) {

            buf.pop();

        }

        Ok(Some(String::from_utf8_lossy(&buf).into_owned()))

    }

    /// The diff of `sha` against the parent it was fed with.

    fn diff(&mut self, sha: &str) -> Result<TreeDiff> {

        let header = match self.next.take() {

            Some(h) => Some(h),

            None => self.field()?,

        };

        if header.as_deref() != Some(sha) {

            return fail(format!("git diff-tree: expected {sha}, got {header:?}"));

        }

        let mut out = Vec::new();

        while let Some(f) = self.field()? {

            let Some(meta) = f.strip_prefix(':') else {

                self.next = Some(f);

                break;

            };

            let Some(path) = self.field()? else {

                return fail("git diff-tree: record without a path");

            };

            // `oldmode newmode oldsha newsha status`

            let m: Vec<&str> = meta.split(' ').collect();

            if m.len() != 5 {

                return fail(format!("git diff-tree: bad record {f:?}"));

            }

            let entry = if m[4].starts_with('D') {

                None

            } else {

                Some((m[1].to_string(), m[3].to_string()))

            };

            out.push((path, entry));

        }

        Ok(out)

    }

}

impl Drop for DiffTree {

    fn drop(&mut self) {

        let _ = self.child.kill();

        let _ = self.child.wait();

        if let Some(f) = self.feeder.take() {

            let _ = f.join();

        }

    }

}

        // Every commit to import that has a parent, diffed against its first.

        let pairs: Vec<(String, String)> = commits

            .iter()

            .filter(|gc| {

                !known.imported.contains_key(&gc.sha) && !known.exported.contains_key(&gc.sha)

            })

            .filter_map(|gc| Some((gc.sha.clone(), gc.parents.first()?.clone())))

            .collect();

        let mut diffs = DiffTree::start(git_dir, pairs)?;

        let mut rebuilt = 0usize;

                            // The parent's tree, so this commit still

                            // renders only what it changes.

                            rebuilt += 1;

                            (st, Some(list_tree(git_dir, p1)?))

            // The commit's tree: its first parent's with the diff applied,

            // or listed whole when that tree is not kept.

            let diff = match gc.parents.first() {

                Some(_) => Some(diffs.diff(&gc.sha)?),

                None => None,

            };

            let (tree, changed) = match (prev_tree, diff) {

                (Some(mut t), Some(diff)) => {

                    let mut changed: HashSet<String> = HashSet::new();

                    for (path, entry) in diff {

                        match entry {

                            Some(v) => {

                                t.insert(path.clone(), v);

                            }

                            None => {

                                t.remove(&path);

                            }

                        }

                        changed.insert(path);

                    }

                    (t, Some(changed))

                }

                _ => (list_tree(git_dir, &gc.sha)?, None),

            };

            // Opaque files and symlinks likewise, when the base has one

            // blob for them: they are neither read nor stored again.

            let mut same_opaque: HashSet<&str> = HashSet::new();

            // An ordinary commit in a tree without submodules is built from

            // the paths it changes alone (oxygen#25): with the `.oxyattributes`

            // files that decide how they are stored, and the directories its

            // removals may leave empty. A merge, or a commit whose parent's

            // tree is not at hand, is built from its whole tree.

            let partial = changed.is_some()

                && gc.parents.len() == 1

                && !tree.values().any(|(mode, _)| mode == "160000");

            let mut rel: BTreeSet<&str> = BTreeSet::new();

            let base_snapshot = if let (true, Some(changed)) = (partial, &changed) {

                rel.extend(changed.iter().map(String::as_str));

                rel.extend(

                    tree.keys()

                        .map(String::as_str)

                        .filter(|p| *p == ".oxyattributes" || p.ends_with("/.oxyattributes")),

                );

                let mut dirs: BTreeSet<&str> = BTreeSet::new();

                for p in changed.iter().filter(|p| !tree.contains_key(*p)) {

                    let mut end = p.len();

                    while let Some(i) = p[..end].rfind('/') {

                        if !dirs.insert(&p[..i]) {

                            break;

                        }

                        end = i;

                }

                let need: Vec<NodeId> = rel

                    .iter()

                    .filter_map(|p| view.entries.get(*p))

                    .filter(|e| e.kind == NodeKind::File && !e.mode.opaque)

                    .map(|e| e.node)

                    .collect();

                crate::timing::add("render: same and need", clock.elapsed());

                let t = std::time::Instant::now();

                self.load_graphs_of(&mut base, &need)?;

                crate::timing::add("render: load graphs", t.elapsed());

                let t = std::time::Instant::now();

                let snap = base.materialize_paths(view, rel.iter().chain(dirs.iter()).copied());

                crate::timing::add("render: materialize", t.elapsed());

                snap

            } else {

                if let Some(changed) = &changed {

                    let view = base.tree().view();

                    for path in tree.keys() {

                        // Submodule handling reads these two whatever changed.

                        if changed.contains(path) || path == ".gitmodules" || path == ".oxymodules"

                            continue;

                        }

                        if let Some(e) = view.entries.get(path) {

                            if touched.contains(&e.node) {

                                continue;

                            }

                            let opaque = e.kind == NodeKind::Symlink

                                || (e.kind == NodeKind::File && e.mode.opaque);

                            if e.kind == NodeKind::File && !e.mode.opaque {

                                same.insert(path.as_str(), e.node);

                            } else if opaque && base.live_blobs(&e.node).len() == 1 {

                                same_opaque.insert(path.as_str());

                            }

                // Build the graphs of every text file the commit may change.

                let skip: HashSet<NodeId> = same.values().copied().collect();

                let need: Vec<NodeId> = base

                    .tree()

                    .view()

                    .entries

                    .values()

                    .filter(|e| {

                        e.kind == NodeKind::File && !e.mode.opaque && !skip.contains(&e.node)

                    })

                    .map(|e| e.node)

                    .collect();

                crate::timing::add("render: same and need", clock.elapsed());

                let t = std::time::Instant::now();

                self.load_graphs_of(&mut base, &need)?;

                crate::timing::add("render: load graphs", t.elapsed());

                let t = std::time::Instant::now();

                let snap = base.materialize_except(&skip);

                crate::timing::add("render: materialize", t.elapsed());

                snap

            };

            let listed: Box<dyn Iterator<Item = (&String, &(String, String))>> = if partial {

                Box::new(rel.iter().filter_map(|p| tree.get_key_value(*p)))

            } else {

                Box::new(tree.iter())

            };

            for (path, (mode, sha)) in listed {

                if same.contains_key(path.as_str()) || same_opaque.contains(path.as_str()) {

            let mut built = if partial {

                // Whether the new tree has anything under `dir`.

                let dir_needed = |dir: &str| {

                    let prefix = format!("{dir}/");

                    tree.range(prefix.clone()..)

                        .next()

                        .is_some_and(|(k, _)| k.starts_with(&prefix))

                };

                self.build_from_entries_seeded(

                    &base,

                    &base_snapshot,

                    &entries,

                    seed,

                    Some(&dir_needed),

                )?

            } else {

                self.build_from_entries_seeded(&base, &base_snapshot, &entries, seed, None)?

            };

            let t = std::time::Instant::now();

            crate::timing::add("store: referenced", t.elapsed());

            let t = std::time::Instant::now();

            crate::timing::add("store: add to state", t.elapsed());

            "git import: tree",

        }

        crate::timing::report_totals();

        if crate::timing::enabled() {

            eprintln!("timing git import: {rebuilt} bases rebuilt from history");

    ///

    /// With `dir_needed`, the snapshot and entries hold only the paths the

    /// import touches (and the directories a removal may leave empty); a

    /// directory stays while `dir_needed` says the new tree has something

    /// under it.

        dir_needed: Option<&dyn Fn(&str) -> bool>,

            Some(Import { seed, dir_needed }),

        import: Option<Import>,

        let seed = import.as_ref().map(|i| i.seed);

        let dir_needed = import.and_then(|i| i.dir_needed);

        let mut laps = crate::timing::Laps::start();

        laps.lap("build: builder");

        laps.lap("build: renames");

        laps.lap("build: paths");

            let still_needed = expected.kind == NodeKind::Dir

                && match dir_needed {

                    Some(f) => f(path),

                    None => needed_dirs.contains(path.as_str()),

                };

        laps.lap("build: removals");

        laps.lap("build: stray placements");

        for (p, e) in &base_snapshot.tree.entries {

            if e.kind == NodeKind::Dir {

                dir_nodes.insert(p.clone(), e.node);

                    let mut laps = crate::timing::Laps::start();

                    // The base's rendering holds its live atoms in order,

                    // one per line (it is not conflicted here).

                    let keys = materialized.live_atoms();

                    let lines = crate::diff::split_lines(bytes);

                    let edits = if keys.len() == lines.len() {

                        crate::diff::text_edits_of(node, &keys, &lines, &disk_text)

                    } else {

                        text_edits(node, &self.base.live_lines(&node), &disk_text)

                    };

                    laps.lap("build: text diff");

/// What a Git import adds to building a change: the seed its new nodes'

/// identifiers derive from, and, when it builds from part of the tree,

/// whether the new tree has anything under a directory.

struct Import<'a> {

    seed: [u8; 32],

    dir_needed: Option<&'a dyn Fn(&str) -> bool>,

}

    /// A snapshot of only `paths` (those `view` has), `view` being this

    /// state's tree view: for a caller that works from what changed. The

    /// graphs of those text files must be loaded.

    pub fn materialize_paths<'p>(

        &self,

        view: crate::tree::TreeView,

        paths: impl IntoIterator<Item = &'p str>,

    ) -> Snapshot {

        let files = paths

            .into_iter()

            .filter_map(|p| Some((p.to_string(), self.file_state(view.entries.get(p)?))))

            .collect();

        Snapshot {

            tree: view,

            files,

            unrendered: BTreeSet::new(),

        }

    }

static TOTALS: std::sync::Mutex<Vec<(&'static str, std::time::Duration)>> =

    std::sync::Mutex::new(Vec::new());

/// Add `d` to the running total for `name`, for a phase repeated many

/// times (once per imported commit, say); `report_totals` prints them.

pub fn add(name: &'static str, d: std::time::Duration) {

    if !enabled() {

        return;

    }

    let mut t = TOTALS.lock().unwrap_or_else(|e| e.into_inner());

    match t.iter_mut().find(|(n, _)| *n == name) {

        Some((_, total)) => *total += d,

        None => t.push((name, d)),

    }

}

/// Print and clear the totals `add` gathered.

pub fn report_totals() {

    if !enabled() {

        return;

    }

    let t = std::mem::take(&mut *TOTALS.lock().unwrap_or_else(|e| e.into_inner()));

    for (name, d) in t {

        record(name, d);

    }

}

/// Times from one point to the next, adding each interval to a total.

pub struct Laps(Option<Instant>);

impl Laps {

    pub fn start() -> Laps {

        Laps(enabled().then(Instant::now))

    }

    /// Add the time since the last lap to `name`'s total.

    pub fn lap(&mut self, name: &'static str) {

        if let Some(t) = &mut self.0 {

            let now = Instant::now();

            add(name, now - *t);

            *t = now;

        }

    }

}

    /// The live subsets of `placements_of` and `modes_of`, kept as changes

    /// apply, so the view walks what is live rather than all history.

    live_placements_of: HashMap<NodeId, BTreeSet<OpKey>>,

    live_modes_of: HashMap<NodeId, BTreeSet<OpKey>>,

                self.index_placement(key);

                    self.index_mode(key);

                self.index_placement(op_key(*placement));

                self.index_placement(op_key(*old));

                self.index_placement(key);

                self.index_mode(op_key(*old));

                self.index_mode(key);

            }

        }

    }

    /// Bring placement `k` in the live index up to date.

    fn index_placement(&mut self, k: OpKey) {

        let Some(node) = self.placements.get(&k).map(|p| p.node) else {

            return;

        };

        if self.placement_live(&k) {

            self.live_placements_of.entry(node).or_default().insert(k);

        } else if let Some(set) = self.live_placements_of.get_mut(&node) {

            set.remove(&k);

            if set.is_empty() {

                self.live_placements_of.remove(&node);

    /// Bring mode atom `k` in the live index up to date.

    fn index_mode(&mut self, k: OpKey) {

        let Some(node) = self.modes.get(&k).map(|(n, _)| *n) else {

            return;

        };

        if self.mode_live(&k) {

            self.live_modes_of.entry(node).or_default().insert(k);

        } else if let Some(set) = self.live_modes_of.get_mut(&node) {

            set.remove(&k);

            if set.is_empty() {

                self.live_modes_of.remove(&node);

            }

        }

    }

        self.live_placements_of

        self.live_modes_of

        self.live_placements_of.keys().copied()

        for ks in self.live_placements_of.values() {

            for k in ks {

                if let Some(p) = self.placements.get(k) {

                    children.entry(p.parent).or_default().push((*k, p));

                }

        // Only placed nodes: one with no live placement is not in the tree.

        let mut nodes: Vec<NodeId> = self.live_placements_of.keys().copied().collect();

        let keys: Vec<OpKey> = g.placements.keys().copied().collect();

        for k in keys {

            g.index_placement(k);

        }

        let keys: Vec<OpKey> = g.modes.keys().copied().collect();

        for k in keys {

            g.index_mode(k);

        }