oxy log draws a graph: lanes, bookmarks inline, unique ID prefixes (closes #50) 2bf22305bc48

- **`oxy log` is a graph (#50).** Each change takes two lines: its ID (the shortest unique prefix bright), author, time, bookmarks and tags, hash and signature, then its subject. Lanes follow the change each one most directly builds on, and join where two lines of work meet, so independent work shows side by side. A dependency further than twelve rows down is marked `~`, which keeps the graph to a few lanes even on a long history. `--json` is unchanged.

/// One cell of a graph row's lower line, the line under the change.

#[derive(Clone, Copy, Debug, PartialEq, Eq)]

pub enum Cell {

    /// Nothing in this column.

    Blank,

    /// A lane carries on down.

    Line,

    /// The change's lane ends at a dependency not drawn (too far down, or

    /// not in the list): `~`.

    Elided,

    /// The left end of a join: this lane carries on, and the lane to its

    /// right turns into it (`├`).

    JoinLeft,

    /// A join passes a column with no lane (`─`).

    JoinPass,

    /// A join crosses a lane that carries on (`┼`).

    JoinCross,

    /// The right end of a join: this lane turns left and ends (`╯`).

    JoinRight,

}

/// A row of the drawn graph: the change's column, which other columns

/// carry a lane past it, and the line under it.

#[derive(Clone, Debug, PartialEq, Eq)]

pub struct GraphRow {

    pub column: usize,

    /// Columns with a lane on the change's own line, besides its own.

    pub passing: Vec<usize>,

    /// The line under the change, one cell per column.

    pub below: Vec<Cell>,

}

/// Lay out `changes` (newest first, as `(hash, deps)`) for a terminal

/// graph. A change's dependencies form a wide graph, since a change builds

/// on whatever last touched the lines it edits, so only one edge is drawn

/// per change: to its newest dependency, the change it most directly

/// builds on. An edge longer than `max_edge` rows, or to a change not in

/// the list, is elided (`~`), as are the other dependencies, so the

/// picture keeps to a few lanes. Two lanes heading for the same change

/// join into the left one.

pub fn graph(changes: &[(ChangeHash, Vec<ChangeHash>)], max_edge: usize) -> Vec<GraphRow> {

    let index: HashMap<&ChangeHash, usize> = changes

        .iter()

        .enumerate()

        .map(|(i, (h, _))| (h, i))

        .collect();

    let mut active: Vec<Option<ChangeHash>> = Vec::new();

    let mut rows = Vec::with_capacity(changes.len());

    for (i, (hash, deps)) in changes.iter().enumerate() {

        let column = match active.iter().position(|a| a.as_ref() == Some(hash)) {

            Some(c) => c,

            None => match active.iter().position(Option::is_none) {

                Some(c) => {

                    active[c] = Some(*hash);

                    c

                }

                None => {

                    active.push(Some(*hash));

                    active.len() - 1

                }

            },

        };

        let passing: Vec<usize> = active

            .iter()

            .enumerate()

            .filter(|(c, a)| *c != column && a.is_some())

            .map(|(c, _)| c)

            .collect();

        // The newest dependency below this row (the list is newest first).

        let nearest = deps

            .iter()

            .filter_map(|d| index.get(d).copied())

            .filter(|&j| j > i)

            .min();

        let parent = nearest.filter(|&j| j - i <= max_edge).map(|j| changes[j].0);

        active[column] = None;

        let mut join: Option<(usize, usize)> = None;

        if let Some(p) = parent {

            match active.iter().position(|a| a.as_ref() == Some(&p)) {

                // Another lane already heads there: join the two, leftwards.

                Some(other) => {

                    let (left, right) = (other.min(column), other.max(column));

                    active[right] = None;

                    active[left] = Some(p);

                    join = Some((left, right));

                }

                None => active[column] = Some(p),

            }

        }

        let width = active.len().max(column + 1);

        let mut below = vec![Cell::Blank; width];

        for (c, a) in active.iter().enumerate() {

            if a.is_some() {

                below[c] = Cell::Line;

            }

        }

        if let Some((left, right)) = join {

            below[left] = Cell::JoinLeft;

            for cell in below.iter_mut().take(right).skip(left + 1) {

                *cell = if *cell == Cell::Line {

                    Cell::JoinCross

                } else {

                    Cell::JoinPass

                };

            }

            below[right] = Cell::JoinRight;

        } else if parent.is_none() && !deps.is_empty() {

            below[column] = Cell::Elided;

        }

        while below.len() > 1 && below.last() == Some(&Cell::Blank) {

            below.pop();

        }

        rows.push(GraphRow {

            column,

            passing,

            below,

        });

        while active.last().is_some_and(Option::is_none) {

            active.pop();

        }

    }

    rows

}

    }

    #[test]

    fn the_graph_draws_the_newest_dependency_and_joins_lanes_left() {

        // 4 and 3 both build on 2; 2 on 1; 3 also depends on 1 (not drawn).

        let rows = graph(

            &[

                (h(4), vec![h(2)]),

                (h(3), vec![h(1), h(2)]),

                (h(2), vec![h(1)]),

                (h(1), vec![]),

            ],

            12,

        );

        assert_eq!(rows[0].column, 0);

        assert_eq!(rows[0].below, vec![Cell::Line]);

        assert_eq!(rows[1].column, 1, "a second head takes a new lane");

        assert_eq!(rows[1].passing, vec![0]);

        assert_eq!(rows[1].below, vec![Cell::JoinLeft, Cell::JoinRight]);

        assert_eq!(rows[2].column, 0);

        assert_eq!(rows[3].below, vec![Cell::Blank], "a root ends its lane");

    }

    #[test]

    fn a_long_edge_is_elided() {

        let mut changes = vec![(h(100), vec![h(1)])];

        for n in (2..=20).rev() {

            changes.push((h(n), vec![]));

        }

        changes.push((h(1), vec![]));

        let rows = graph(&changes, 5);

        assert_eq!(rows[0].below, vec![Cell::Elided]);

        assert!(

            rows.iter().all(|r| r.below.len() == 1),

            "one lane all the way"

        );

        let rows = graph(&changes, 100);

        assert_eq!(rows[0].below, vec![Cell::Line], "drawn when short enough");

`oxy log` draws the history as a graph, newest first, two lines per change:

```

◉  2f8518c0 Andy McCall just now

│  (working copy, clean)

●  1b5888b1 Andy McCall 2 minutes ago main #cc23b999 ✔ signed

│  Edit b

│ ●  d6f52eca Andy McCall 3 minutes ago main #ec6a7dc4 ✔ signed

├─╯  Edit a

○  c0593116 Andy McCall 5 minutes ago #eeac7940 ✔ signed

   Both files

```

The bright start of each ID is the shortest prefix that names it. `●` marks

a head, `◉` the working copy. Bookmarks and tags show beside their heads,

unless they have more than three. A lane follows the change each one most

directly builds on, its newest dependency. Two edits that build on the same

change take two lanes, which join above it, so independent work shows side

by side. `~` means the change builds on something further down than the

graph draws, or not shown; `-v` lists every dependency.

    author_name, deps_line, deps_of, plural, short_id, signature_line, signature_mark, subject_of,

    when,

    // Lay out a little past what is shown, so edges into the cut are drawn.

    let window: Vec<(ChangeHash, Vec<ChangeHash>)> = entries

        .iter()

        .take((shown + MAX_EDGE).min(total))

        .map(|e| (e.hash, e.change.deps.clone()))

        .collect();

    let rows = oxy_core::lanes::graph(&window, MAX_EDGE);

    // Highlight the shortest prefix that names each change: against the

    // whole log, which is what `resolve_change` searches.

    let everything;

    let all = if path.is_some() || lines.is_some() {

        everything = repo.log()?;

        &everything

    } else {

        &entries

    };

    let id_prefix = unique_prefixes(all.iter().map(|e| e.change.change_id.to_hex()));

    let labels = reference_labels(&repo)?;

    for (e, row) in entries.iter().take(shown).zip(&rows) {

        let id = c.change_id.to_hex();

        let n = id_prefix.get(&id).copied().unwrap_or(8).min(8);

        let mut head = vec![format!("{}{}", ui::id(&id[..n]), ui::dim(&id[n..8]))];

        head.push(ui::author(author_name(&repo, c)));

        head.push(ui::dim(ui::ago(c.hlc.wall_ms)));

        if let Some(names) = labels.get(&e.hash) {

            head.push(names.join(" "));

            head.push(ui::warn("resolution"));

        if !e.is_working_copy {

            head.push(ui::hash(format!("#{}", e.hash.short(8))));

            head.push(signature_mark(&repo, &e.hash, Some(c))?);

        }

        println!("{}{}", node_line(row, &bullet), head.join(" "));

                "(working copy, clean)"

                "(working copy, uncommitted changes)"

        } else if c.message.trim().is_empty() {

            ui::dim("(no description)")

            subject_of(&c.message).to_string()

        println!("{}{subject}", below_line(row));

            let rail = continuation(row);

            for line in body {

                println!("{rail}  {line}");

        if let Some(last) = rows.get(shown.saturating_sub(1)) {

            let cut: String = last

                .below

                .iter()

                .map(|c| match c {

                    Cell::Blank | Cell::Elided | Cell::JoinRight => "  ",

                    _ => "~ ",

                })

                .collect();

            if cut.trim().is_empty() {

                println!("{}", ui::dim("~"));

            } else {

                println!("{}", ui::dim(cut.trim_end()));

            }

        }

}

/// Rows a drawn edge may span in `oxy log`; a longer one is elided (`~`).

const MAX_EDGE: usize = 12;

use oxy_core::hash::ChangeHash;

use oxy_core::lanes::{Cell, GraphRow};

/// A graph cell, two columns wide.

fn cell(c: Cell) -> &'static str {

    match c {

        Cell::Blank => "  ",

        Cell::Line => ui::glyph("│ ", "| "),

        Cell::Elided => "~ ",

        Cell::JoinLeft => ui::glyph("├─", "|-"),

        Cell::JoinPass => ui::glyph("──", "--"),

        Cell::JoinCross => ui::glyph("┼─", "+-"),

        Cell::JoinRight => ui::glyph("╯ ", "' "),

    }

}

/// The graph part of a change's own line, its bullet in its column.

fn node_line(row: &GraphRow, bullet: &str) -> String {

    let width = row

        .passing

        .iter()

        .copied()

        .max()

        .unwrap_or(0)

        .max(row.column)

        + 1;

    let mut out = String::new();

    for c in 0..width {

        if c == row.column {

            out.push_str(bullet);

            out.push(' ');

        } else if row.passing.contains(&c) {

            out.push_str(&ui::dim(cell(Cell::Line)));

        } else {

            out.push_str("  ");

        }

    }

    out.push(' ');

    out

}

/// The graph part of the line under a change: lanes carrying on, a join,

/// or `~` for an elided edge.

fn below_line(row: &GraphRow) -> String {

    let g: String = row.below.iter().map(|c| cell(*c)).collect();

    format!("{} ", ui::dim(g))

}

/// The graph part of any further line of a change (`-v`).

fn continuation(row: &GraphRow) -> String {

    let g: String = row

        .below

        .iter()

        .map(|c| match c {

            Cell::Line | Cell::JoinLeft | Cell::JoinCross => cell(Cell::Line),

            _ => "  ",

        })

        .collect();

    format!("{} ", ui::dim(g))

}

/// For each hex ID, the length of its shortest prefix no other ID shares.

fn unique_prefixes(ids: impl Iterator<Item = String>) -> std::collections::HashMap<String, usize> {

    let mut v: Vec<String> = ids.collect();

    v.sort();

    v.dedup();

    let common = |a: &str, b: &str| a.bytes().zip(b.bytes()).take_while(|(x, y)| x == y).count();

    let mut out = std::collections::HashMap::with_capacity(v.len());

    for i in 0..v.len() {

        let before = if i > 0 { common(&v[i - 1], &v[i]) } else { 0 };

        let after = if i + 1 < v.len() {

            common(&v[i], &v[i + 1])

        } else {

            0

        };

        out.insert(v[i].clone(), before.max(after) + 1);

    }

    out

}

/// Bookmark, remote bookmark and tag names to show beside the changes they

/// point at. A name is shown on each head of its state; one with more than

/// three heads names too much of the log to help, so it is left out (oxy

/// bookmark list shows it). A remote bookmark at the same state as the

/// local one of that name is not repeated.

fn reference_labels(repo: &Repo) -> Result<std::collections::HashMap<ChangeHash, Vec<String>>> {

    const MAX_HEADS: usize = 3;

    let view = repo.view()?;

    let mut out: std::collections::HashMap<ChangeHash, Vec<String>> = Default::default();

    let mut add = |heads: Vec<ChangeHash>, label: String| {

        if heads.len() <= MAX_HEADS {

            for h in heads {

                out.entry(h).or_default().push(label.clone());

            }

        }

    };

    for (name, st) in &view.bookmarks {

        add(repo.store().get_state(st)?.heads, ui::bookmark(name));

    }

    for (remote, bookmarks) in &view.remotes {

        for (name, st) in bookmarks {

            if view.bookmarks.get(name) == Some(st) {

                continue;

            }

            add(

                repo.store().get_state(st)?.heads,

                ui::dim(format!("{remote}/{name}")),

            );

        }

    }

    for t in repo.tags()? {

        add(t.heads.clone(), ui::warn(&t.name));

    }

    Ok(out)

/// oxygen#50: the log is a graph. Two changes that build on the same one

/// take two lanes that join above it; each change shows its ID, author,

/// time and hash on one line and its subject on the next.

#[test]

fn the_log_draws_lanes_that_join() {

    let tmp = tempfile::tempdir().unwrap();

    let home = tmp.path().join("home");

    std::fs::create_dir_all(&home).unwrap();

    let repo = tmp.path().join("r");

    assert_eq!(oxy(tmp.path(), &home, &["init", repo.to_str().unwrap()]).0, 0);

    write(&repo, "a.txt", "a\n");

    write(&repo, "b.txt", "b\n");

    assert_eq!(oxy(&repo, &home, &["commit", "-m", "both files"]).0, 0);

    write(&repo, "a.txt", "a\na2\n");

    assert_eq!(oxy(&repo, &home, &["commit", "-m", "edit a"]).0, 0);

    write(&repo, "b.txt", "b\nb2\n");

    assert_eq!(oxy(&repo, &home, &["commit", "-m", "edit b"]).0, 0);

    let (code, out, err) = oxy(&repo, &home, &["log"]);

    assert_eq!(code, 0, "{err}");

    let out = String::from_utf8_lossy(&out);

    let lines: Vec<&str> = out.lines().collect();

    // The working copy, then "edit b", "edit a" beside it, then their base.

    assert!(lines[0].starts_with('@'), "{out}");

    assert!(lines.iter().any(|l| l.starts_with("|-'") && l.contains("edit a")), "{out}");

    assert!(lines.iter().any(|l| l.starts_with("| *") || l.starts_with("| o")), "{out}");

    let base = lines.iter().position(|l| l.contains("both files")).unwrap();

    assert!(lines[base - 1].contains('#'), "the header line carries the hash: {out}");

}