crates/oxy-core/src/repo/inspect.rs at v0.2.0 · andymccall/oxygen

◆ v0.2.0 oxygen / crates / oxy-core / src / repo / inspect.rs

16.9 KiB · Rust · last changed Blame from the state index, each author's name read once (refs #41) 1 month ago source blame history raw

//! Inspection (spec §27): blame from atom keys, and bisect over
//! dependency-closed prefixes of the candidates between a good and a bad
//! state.

use super::*;

/// One line of `oxy blame`.
#[derive(Clone, Debug)]
pub struct BlameLine {
    pub line: usize,
    pub hash: ChangeHash,
    pub index: u32,
    pub change_id: ChangeId,
    pub author: String,
    pub when_ms: u64,
    pub text: Vec<u8>,
}

/// Where a bisect stands.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum BisectStep {
    /// More `good`/`bad` marks are needed before the search can start.
    NeedMarks { good: usize, bad: usize },
    /// A state is checked out for testing.
    Testing {
        heads: Vec<ChangeHash>,
        remaining: usize,
        steps_left: u32,
    },
    /// The first change whose inclusion makes the state bad.
    Found { culprit: ChangeHash },
    /// Every remaining candidate was skipped.
    Inconclusive { candidates: Vec<ChangeHash> },
}

#[derive(Clone, Debug, Default)]
struct BisectState {
    start: Vec<ChangeHash>,
    good: Vec<ChangeHash>,
    bad: Vec<ChangeHash>,
    candidates: Vec<ChangeHash>,
    lo: usize,
    hi: usize,
    /// The prefix length currently checked out for testing.
    testing: Option<usize>,
    skipped: Vec<usize>,
}

fn hashes_line(v: &[ChangeHash]) -> String {
    v.iter().map(|h| h.to_hex()).collect::<Vec<_>>().join(" ")
}
fn hashes_from(s: &str) -> Vec<ChangeHash> {
    s.split_whitespace()
        .filter_map(ObjectRef::from_hex)
        .collect()
}

impl Repo {
    /// The introducing change, author, and date of every line of `path` in
    /// the working copy's base state (spec §27).
    pub fn blame(&self, path: &str) -> Result<Vec<BlameLine>> {
        let (_, wc) = self.working_copy()?;
        // The working copy's base is what the state index holds.
        let mut state = self.load_state_indexed(&wc.deps)?;
        let tree = state.tree().view();
        if let Some(e) = tree.entries.get(path) {
            self.load_graphs_of(&mut state, &[e.node])?;
        }
        self.blame_state(path, &state, &tree, "the working copy's base state")
    }

    /// Blame `path` in the state with these heads (hosted repositories).
    pub fn blame_in(&self, path: &str, heads: &[ChangeHash]) -> Result<Vec<BlameLine>> {
        self.blame_heads(path, heads, "that state")
    }

    /// Blame `path` in the state with these heads, building only its graph.
    fn blame_heads(&self, path: &str, heads: &[ChangeHash], what: &str) -> Result<Vec<BlameLine>> {
        let mut state = self.load_state_history(heads)?;
        let tree = state.tree().view();
        if let Some(e) = tree.entries.get(path) {
            self.load_graphs_of(&mut state, &[e.node])?;
        }
        self.blame_state(path, &state, &tree, what)
    }

    /// Blame `path` in a loaded state whose tree view the caller holds; no
    /// file other than `path` is rendered.
    pub fn blame_of(
        &self,
        state: &crate::state::State,
        tree: &crate::tree::TreeView,
        path: &str,
    ) -> Result<Vec<BlameLine>> {
        self.blame_state(path, state, tree, "that state")
    }

    fn blame_state(
        &self,
        path: &str,
        state: &crate::state::State,
        tree: &crate::tree::TreeView,
        what: &str,
    ) -> Result<Vec<BlameLine>> {
        let Some(f) = tree.entries.get(path) else {
            return fail(format!("{path} is not in {what}"));
        };
        if f.kind != crate::objects::NodeKind::File || f.mode.opaque {
            return fail(format!("{path} is not a text file"));
        }
        let mut out = Vec::new();
        // Each author's name read once, not once per line.
        let mut names: HashMap<crate::hash::KeyId, String> = HashMap::new();
        for (i, ((hash, index), text)) in state.live_lines(&f.node).into_iter().enumerate() {
            let meta = state.get(&hash);
            let author = match meta {
                Some(m) if !m.author.is_zero() => names
                    .entry(m.author)
                    .or_insert_with(|| {
                        self.store
                            .get_identity(&m.author)
                            .map(|id| id.name)
                            .unwrap_or_else(|_| m.author.short(12))
                    })
                    .clone(),
                Some(m) => m
                    .message
                    .lines()
                    .rev()
                    .find_map(|l| l.strip_prefix("Git-Author: "))
                    .map(|a| a.split('<').next().unwrap_or(a).trim().to_string())
                    .unwrap_or_else(|| "unknown".into()),
                None => "unknown".into(),
            };
            out.push(BlameLine {
                line: i + 1,
                hash,
                index,
                change_id: meta.map(|m| m.change_id).unwrap_or(ChangeId([0; 16])),
                author,
                when_ms: meta.map(|m| m.hlc.wall_ms).unwrap_or(0),
                text,
            });
        }
        Ok(out)
    }

    // ------------------------------------------------------------ bisect

    fn bisect_dir(&self) -> PathBuf {
        self.oxy.join("bisect")
    }

    fn bisect_load(&self) -> Result<Option<BisectState>> {
        let dir = self.bisect_dir();
        if !dir.join("start").exists() {
            return Ok(None);
        }
        let read = |name: &str| fs::read_to_string(dir.join(name)).unwrap_or_default();
        let nums: Vec<usize> = read("range")
            .split_whitespace()
            .filter_map(|n| n.parse().ok())
            .collect();
        Ok(Some(BisectState {
            start: hashes_from(&read("start")),
            good: hashes_from(&read("good")),
            bad: hashes_from(&read("bad")),
            candidates: hashes_from(&read("candidates")),
            lo: nums.first().copied().unwrap_or(0),
            hi: nums.get(1).copied().unwrap_or(0),
            testing: nums.get(2).copied().filter(|_| nums.len() > 2),
            skipped: read("skipped")
                .split_whitespace()
                .filter_map(|n| n.parse().ok())
                .collect(),
        }))
    }

    fn bisect_save(&self, st: &BisectState) -> Result<()> {
        let dir = self.bisect_dir();
        fs::create_dir_all(&dir)?;
        write_atomic(&dir.join("start"), hashes_line(&st.start).as_bytes())?;
        write_atomic(&dir.join("good"), hashes_line(&st.good).as_bytes())?;
        write_atomic(&dir.join("bad"), hashes_line(&st.bad).as_bytes())?;
        write_atomic(
            &dir.join("candidates"),
            hashes_line(&st.candidates).as_bytes(),
        )?;
        let mut range = format!("{} {}", st.lo, st.hi);
        if let Some(t) = st.testing {
            range.push_str(&format!(" {t}"));
        }
        write_atomic(&dir.join("range"), range.as_bytes())?;
        write_atomic(
            &dir.join("skipped"),
            st.skipped
                .iter()
                .map(|n| n.to_string())
                .collect::<Vec<_>>()
                .join(" ")
                .as_bytes(),
        )?;
        Ok(())
    }

    /// Begin a bisect: remembers the working copy's base to restore later.
    pub fn bisect_start(&self) -> Result<()> {
        if self.bisect_load()?.is_some() {
            return fail("a bisect is in progress; finish it or run `oxy bisect reset`");
        }
        let (_, wc) = self.working_copy()?;
        let start = self.load_state_history(&wc.deps)?.maximal(&wc.deps);
        self.bisect_save(&BisectState {
            start,
            ..Default::default()
        })
    }

    pub fn bisect_reset(&self) -> Result<()> {
        let Some(st) = self.bisect_load()? else {
            return fail("no bisect in progress");
        };
        self.checkout(&st.start, false, "oxy bisect reset")?;
        fs::remove_dir_all(self.bisect_dir())?;
        Ok(())
    }

    pub fn bisect_status(&self) -> Result<Option<BisectStep>> {
        let Some(st) = self.bisect_load()? else {
            return Ok(None);
        };
        Ok(Some(self.bisect_step(&st)))
    }

    fn bisect_step(&self, st: &BisectState) -> BisectStep {
        if st.candidates.is_empty() {
            return BisectStep::NeedMarks {
                good: st.good.len(),
                bad: st.bad.len(),
            };
        }
        if st.hi <= st.lo + 1 {
            return BisectStep::Found {
                culprit: st.candidates[st.lo],
            };
        }
        match st.testing {
            Some(_) => {
                let remaining = st.hi - st.lo;
                BisectStep::Testing {
                    heads: self.bisect_heads(st, st.testing.unwrap()),
                    remaining,
                    steps_left: (remaining as f64).log2().ceil() as u32,
                }
            }
            None => BisectStep::Inconclusive {
                candidates: st.candidates[st.lo..st.hi].to_vec(),
            },
        }
    }

    /// `good ∪ candidates[..k]`, as heads.
    fn bisect_heads(&self, st: &BisectState, k: usize) -> Vec<ChangeHash> {
        let mut all = st.good.clone();
        all.extend(st.candidates[..k].iter().copied());
        self.load_state_history(&all)
            .map(|s| s.maximal(&all))
            .unwrap_or(all)
    }

    /// Check out the midpoint of the open range, skipping indices marked
    /// untestable, and record it as the state under test.
    fn bisect_advance(&self, st: &mut BisectState) -> Result<BisectStep> {
        if st.hi <= st.lo + 1 {
            st.testing = None;
            self.bisect_save(st)?;
            return Ok(BisectStep::Found {
                culprit: st.candidates[st.lo],
            });
        }
        let mid = st.lo + (st.hi - st.lo) / 2;
        // Try mid, then the nearest untried indices on either side.
        let mut order = vec![mid];
        for d in 1..(st.hi - st.lo) {
            if mid + d < st.hi {
                order.push(mid + d);
            }
            if mid > st.lo + d {
                order.push(mid - d);
            }
        }
        let Some(k) = order.into_iter().find(|k| !st.skipped.contains(k)) else {
            st.testing = None;
            self.bisect_save(st)?;
            return Ok(BisectStep::Inconclusive {
                candidates: st.candidates[st.lo..st.hi].to_vec(),
            });
        };
        let heads = self.bisect_heads(st, k);
        self.checkout(
            &heads,
            false,
            &format!("oxy bisect (testing {k} of {})", st.candidates.len()),
        )?;
        st.testing = Some(k);
        self.bisect_save(st)?;
        let remaining = st.hi - st.lo;
        Ok(BisectStep::Testing {
            heads,
            remaining,
            steps_left: (remaining as f64).log2().ceil() as u32,
        })
    }

    /// Mark states good or bad. With `changes`, before the search starts,
    /// they name known-good or known-bad states; without, the state under
    /// test gets the verdict. `None` for `good` means skip (untestable).
    pub fn bisect_mark(&self, good: Option<bool>, changes: &[ChangeHash]) -> Result<BisectStep> {
        let Some(mut st) = self.bisect_load()? else {
            return fail("no bisect in progress; run `oxy bisect start`");
        };
        if !changes.is_empty() {
            if !st.candidates.is_empty() {
                return fail("the search has started; mark the state under test with plain `oxy bisect good|bad`");
            }
            match good {
                Some(true) => st.good.extend(changes.iter().copied()),
                Some(false) => st.bad.extend(changes.iter().copied()),
                None => return fail("skip applies to the state under test"),
            }
            if st.good.is_empty() || st.bad.is_empty() {
                self.bisect_save(&st)?;
                return Ok(BisectStep::NeedMarks {
                    good: st.good.len(),
                    bad: st.bad.len(),
                });
            }
            let good_heads = self.load_state_history(&st.good)?.maximal(&st.good);
            let bad_heads = self.load_state_history(&st.bad)?.maximal(&st.bad);
            st.good = good_heads.clone();
            st.bad = bad_heads.clone();
            st.candidates = self.negotiate(&good_heads, &bad_heads)?;
            if st.candidates.is_empty() {
                return fail("the bad state adds nothing to the good state; nothing to bisect");
            }
            st.lo = 0;
            st.hi = st.candidates.len();
            return self.bisect_advance(&mut st);
        }
        let Some(k) = st.testing else {
            return fail("no state is under test; give `oxy bisect good|bad` a change or bookmark to start with");
        };
        match good {
            Some(true) => st.lo = k,
            Some(false) => st.hi = k,
            None => st.skipped.push(k),
        }
        self.bisect_advance(&mut st)
    }

    /// Automate with a command run in the working copy: exit 0 is good, 125
    /// skips, anything else is bad.
    pub fn bisect_run(&self, command: &[String]) -> Result<BisectStep> {
        let Some(st) = self.bisect_load()? else {
            return fail("no bisect in progress; run `oxy bisect start`");
        };
        if st.testing.is_none() {
            return Ok(self.bisect_step(&st));
        }
        loop {
            let status = std::process::Command::new(&command[0])
                .args(&command[1..])
                .current_dir(&self.root)
                .status()
                .map_err(|e| RepoError::Msg(format!("running {}: {e}", command[0])))?;
            let verdict = match status.code() {
                Some(0) => Some(true),
                Some(125) => None,
                _ => Some(false),
            };
            match self.bisect_mark(verdict, &[])? {
                BisectStep::Testing { .. } => continue,
                done => return Ok(done),
            }
        }
    }
}

/// What `oxy describe` reports about the working copy (spec §10.1).
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Description {
    /// The tag of the base state, or the nearest tag below it.
    pub tag: Option<String>,
    /// Changes in the base state that the tag's state lacks (0: exact).
    pub distance: usize,
    pub bookmark: String,
    /// The base's newest head.
    pub change: ChangeId,
    pub hash: ChangeHash,
    /// Whether the working copy has uncommitted changes.
    pub dirty: bool,
}

impl Description {
    /// `v1.2`, `v1.2-3-8c5ea12a`, or `develop-8c5ea12a`, and `-dirty`.
    pub fn line(&self) -> String {
        let short = self.change.short(8);
        let base = match (&self.tag, self.distance) {
            (Some(t), 0) => t.clone(),
            (Some(t), n) => format!("{t}-{n}-{short}"),
            (None, _) => format!("{}-{short}", self.bookmark),
        };
        if self.dirty {
            format!("{base}-dirty")
        } else {
            base
        }
    }
}

impl Repo {
    /// Name the working copy for builds (`oxy describe`, like `git
    /// describe`): the tag of its base state; else the nearest tag whose
    /// state the base contains, with how many changes it adds and its
    /// newest head; else the bookmark and that head. `dirty` when the
    /// working copy has uncommitted changes.
    pub fn describe_working_copy(&self) -> Result<Description> {
        let snap = self.snapshot_status("oxy describe")?;
        let dirty = !snap.statuses.is_empty();
        let base = snap.base.maximal(&snap.wc.deps);
        let Some(&newest) = base
            .iter()
            .max_by_key(|h| snap.base.get(h).map(|c| (c.hlc, **h)))
        else {
            return fail("the working copy sits on no change yet");
        };
        let Some(change) = snap.base.get(&newest).map(|m| m.change_id) else {
            return fail("the working copy's base is not loaded");
        };
        let mut sorted = base.clone();
        sorted.sort();
        let mut best: Option<(usize, String)> = None;
        for t in self.tags()? {
            if !t.heads.iter().all(|h| snap.base.contains(h)) {
                continue;
            }
            let mut tagged: std::collections::HashSet<ChangeHash> =
                t.heads.iter().copied().collect();
            for h in &t.heads {
                tagged.extend(snap.base.closure(h).iter().copied());
            }
            let mut heads = t.heads.clone();
            heads.sort();
            let distance = if heads == sorted {
                0
            } else {
                snap.base.len().saturating_sub(tagged.len()).max(1)
            };
            if best
                .as_ref()
                .is_none_or(|(d, n)| distance < *d || (distance == *d && t.name < *n))
            {
                best = Some((distance, t.name));
            }
        }
        let (distance, tag) = match best {
            Some((d, t)) => (d, Some(t)),
            None => (0, None),
        };
        Ok(Description {
            tag,
            distance,
            bookmark: self.config.bookmark.clone(),
            change,
            hash: newest,
            dirty,
        })
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

957fee30 Andy McCall 1 month ago ↶	1	//! Inspection (spec §27): blame from atom keys, and bisect over
	2	//! dependency-closed prefixes of the candidates between a good and a bad
	3	//! state.
	4
	5	use super::*;
	6
	7	/// One line of `oxy blame`.
	8	#[derive(Clone, Debug)]
	9	pub struct BlameLine {
	10	pub line: usize,
	11	pub hash: ChangeHash,
	12	pub index: u32,
	13	pub change_id: ChangeId,
	14	pub author: String,
	15	pub when_ms: u64,
	16	pub text: Vec<u8>,
	17	}
	18
	19	/// Where a bisect stands.
	20	#[derive(Clone, Debug, PartialEq, Eq)]
	21	pub enum BisectStep {
	22	/// More `good`/`bad` marks are needed before the search can start.
	23	NeedMarks { good: usize, bad: usize },
	24	/// A state is checked out for testing.
75167672 Andy McCall 1 month ago	25	Testing {
	26	heads: Vec<ChangeHash>,
	27	remaining: usize,
	28	steps_left: u32,
	29	},
957fee30 Andy McCall 1 month ago ↶	30	/// The first change whose inclusion makes the state bad.
	31	Found { culprit: ChangeHash },
	32	/// Every remaining candidate was skipped.
	33	Inconclusive { candidates: Vec<ChangeHash> },
	34	}
	35
	36	#[derive(Clone, Debug, Default)]
	37	struct BisectState {
	38	start: Vec<ChangeHash>,
	39	good: Vec<ChangeHash>,
	40	bad: Vec<ChangeHash>,
	41	candidates: Vec<ChangeHash>,
	42	lo: usize,
	43	hi: usize,
	44	/// The prefix length currently checked out for testing.
	45	testing: Option<usize>,
	46	skipped: Vec<usize>,
	47	}
	48
	49	fn hashes_line(v: &[ChangeHash]) -> String {
	50	v.iter().map(\|h\| h.to_hex()).collect::<Vec<_>>().join(" ")
	51	}
	52	fn hashes_from(s: &str) -> Vec<ChangeHash> {
75167672 Andy McCall 1 month ago	53	s.split_whitespace()
	54	.filter_map(ObjectRef::from_hex)
	55	.collect()
957fee30 Andy McCall 1 month ago ↶	56	}
	57
	58	impl Repo {
	59	/// The introducing change, author, and date of every line of `path` in
	60	/// the working copy's base state (spec §27).
	61	pub fn blame(&self, path: &str) -> Result<Vec<BlameLine>> {
69816d68 Andy McCall 1 month ago ↶	62	let (_, wc) = self.working_copy()?;
073a2115 Andy McCall 1 month ago ↶	63	// The working copy's base is what the state index holds.
	64	let mut state = self.load_state_indexed(&wc.deps)?;
	65	let tree = state.tree().view();
	66	if let Some(e) = tree.entries.get(path) {
	67	self.load_graphs_of(&mut state, &[e.node])?;
	68	}
	69	self.blame_state(path, &state, &tree, "the working copy's base state")
e02bf0cd Andy McCall 1 month ago ↶	70	}
	71
	72	/// Blame `path` in the state with these heads (hosted repositories).
	73	pub fn blame_in(&self, path: &str, heads: &[ChangeHash]) -> Result<Vec<BlameLine>> {
69816d68 Andy McCall 1 month ago ↶	74	self.blame_heads(path, heads, "that state")
	75	}
	76
	77	/// Blame `path` in the state with these heads, building only its graph.
	78	fn blame_heads(&self, path: &str, heads: &[ChangeHash], what: &str) -> Result<Vec<BlameLine>> {
e8d38e47 Andy McCall 1 month ago ↶	79	let mut state = self.load_state_history(heads)?;
	80	let tree = state.tree().view();
	81	if let Some(e) = tree.entries.get(path) {
	82	self.load_graphs_of(&mut state, &[e.node])?;
	83	}
69816d68 Andy McCall 1 month ago ↶	84	self.blame_state(path, &state, &tree, what)
bc489b6c Andy McCall 1 month ago ↶	85	}
	86
	87	/// Blame `path` in a loaded state whose tree view the caller holds; no
	88	/// file other than `path` is rendered.
	89	pub fn blame_of(
	90	&self,
	91	state: &crate::state::State,
	92	tree: &crate::tree::TreeView,
	93	path: &str,
	94	) -> Result<Vec<BlameLine>> {
	95	self.blame_state(path, state, tree, "that state")
e02bf0cd Andy McCall 1 month ago ↶	96	}
e02bf0cd Andy McCall 1 month ago ↶	97
75167672 Andy McCall 1 month ago	98	fn blame_state(
	99	&self,
	100	path: &str,
	101	state: &crate::state::State,
bc489b6c Andy McCall 1 month ago ↶	102	tree: &crate::tree::TreeView,
75167672 Andy McCall 1 month ago	103	what: &str,
75167672 Andy McCall 1 month ago	104	) -> Result<Vec<BlameLine>> {
bc489b6c Andy McCall 1 month ago ↶	105	let Some(f) = tree.entries.get(path) else {
75167672 Andy McCall 1 month ago	106	return fail(format!("{path} is not in {what}"));
75167672 Andy McCall 1 month ago	107	};
bc489b6c Andy McCall 1 month ago ↶	108	if f.kind != crate::objects::NodeKind::File \|\| f.mode.opaque {
957fee30 Andy McCall 1 month ago ↶	109	return fail(format!("{path} is not a text file"));
	110	}
	111	let mut out = Vec::new();
073a2115 Andy McCall 1 month ago ↶	112	// Each author's name read once, not once per line.
073a2115 Andy McCall 1 month ago ↶	113	let mut names: HashMap<crate::hash::KeyId, String> = HashMap::new();
e02bf0cd Andy McCall 1 month ago ↶	114	for (i, ((hash, index), text)) in state.live_lines(&f.node).into_iter().enumerate() {
e02bf0cd Andy McCall 1 month ago ↶	115	let meta = state.get(&hash);
957fee30 Andy McCall 1 month ago ↶	116	let author = match meta {
073a2115 Andy McCall 1 month ago ↶	117	Some(m) if !m.author.is_zero() => names
	118	.entry(m.author)
	119	.or_insert_with(\|\| {
	120	self.store
	121	.get_identity(&m.author)
	122	.map(\|id\| id.name)
	123	.unwrap_or_else(\|_\| m.author.short(12))
	124	})
	125	.clone(),
75167672 Andy McCall 1 month ago	126	Some(m) => m
	127	.message
	128	.lines()
	129	.rev()
	130	.find_map(\|l\| l.strip_prefix("Git-Author: "))
	131	.map(\|a\| a.split('<').next().unwrap_or(a).trim().to_string())
	132	.unwrap_or_else(\|\| "unknown".into()),
957fee30 Andy McCall 1 month ago ↶	133	None => "unknown".into(),
	134	};
	135	out.push(BlameLine {
	136	line: i + 1,
	137	hash,
	138	index,
	139	change_id: meta.map(\|m\| m.change_id).unwrap_or(ChangeId([0; 16])),
	140	author,
	141	when_ms: meta.map(\|m\| m.hlc.wall_ms).unwrap_or(0),
	142	text,
	143	});
	144	}
	145	Ok(out)
	146	}
	147
	148	// ------------------------------------------------------------ bisect
	149
	150	fn bisect_dir(&self) -> PathBuf {
	151	self.oxy.join("bisect")
	152	}
	153
	154	fn bisect_load(&self) -> Result<Option<BisectState>> {
	155	let dir = self.bisect_dir();
	156	if !dir.join("start").exists() {
	157	return Ok(None);
	158	}
	159	let read = \|name: &str\| fs::read_to_string(dir.join(name)).unwrap_or_default();
75167672 Andy McCall 1 month ago	160	let nums: Vec<usize> = read("range")
	161	.split_whitespace()
	162	.filter_map(\|n\| n.parse().ok())
	163	.collect();
957fee30 Andy McCall 1 month ago ↶	164	Ok(Some(BisectState {
	165	start: hashes_from(&read("start")),
	166	good: hashes_from(&read("good")),
	167	bad: hashes_from(&read("bad")),
	168	candidates: hashes_from(&read("candidates")),
	169	lo: nums.first().copied().unwrap_or(0),
	170	hi: nums.get(1).copied().unwrap_or(0),
	171	testing: nums.get(2).copied().filter(\|_\| nums.len() > 2),
75167672 Andy McCall 1 month ago	172	skipped: read("skipped")
	173	.split_whitespace()
	174	.filter_map(\|n\| n.parse().ok())
	175	.collect(),
957fee30 Andy McCall 1 month ago ↶	176	}))
	177	}
	178
	179	fn bisect_save(&self, st: &BisectState) -> Result<()> {
	180	let dir = self.bisect_dir();
	181	fs::create_dir_all(&dir)?;
	182	write_atomic(&dir.join("start"), hashes_line(&st.start).as_bytes())?;
	183	write_atomic(&dir.join("good"), hashes_line(&st.good).as_bytes())?;
	184	write_atomic(&dir.join("bad"), hashes_line(&st.bad).as_bytes())?;
75167672 Andy McCall 1 month ago	185	write_atomic(
	186	&dir.join("candidates"),
	187	hashes_line(&st.candidates).as_bytes(),
	188	)?;
957fee30 Andy McCall 1 month ago ↶	189	let mut range = format!("{} {}", st.lo, st.hi);
	190	if let Some(t) = st.testing {
	191	range.push_str(&format!(" {t}"));
	192	}
	193	write_atomic(&dir.join("range"), range.as_bytes())?;
75167672 Andy McCall 1 month ago	194	write_atomic(
	195	&dir.join("skipped"),
	196	st.skipped
	197	.iter()
	198	.map(\|n\| n.to_string())
	199	.collect::<Vec<_>>()
	200	.join(" ")
	201	.as_bytes(),
	202	)?;
957fee30 Andy McCall 1 month ago ↶	203	Ok(())
	204	}
	205
	206	/// Begin a bisect: remembers the working copy's base to restore later.
	207	pub fn bisect_start(&self) -> Result<()> {
	208	if self.bisect_load()?.is_some() {
	209	return fail("a bisect is in progress; finish it or run `oxy bisect reset`");
	210	}
	211	let (_, wc) = self.working_copy()?;
57eaac91 Andy McCall 1 month ago ↶	212	let start = self.load_state_history(&wc.deps)?.maximal(&wc.deps);
75167672 Andy McCall 1 month ago	213	self.bisect_save(&BisectState {
	214	start,
	215	..Default::default()
	216	})
957fee30 Andy McCall 1 month ago ↶	217	}
	218
	219	pub fn bisect_reset(&self) -> Result<()> {
75167672 Andy McCall 1 month ago	220	let Some(st) = self.bisect_load()? else {
	221	return fail("no bisect in progress");
	222	};
957fee30 Andy McCall 1 month ago ↶	223	self.checkout(&st.start, false, "oxy bisect reset")?;
	224	fs::remove_dir_all(self.bisect_dir())?;
	225	Ok(())
	226	}
	227
	228	pub fn bisect_status(&self) -> Result<Option<BisectStep>> {
75167672 Andy McCall 1 month ago	229	let Some(st) = self.bisect_load()? else {
	230	return Ok(None);
	231	};
957fee30 Andy McCall 1 month ago ↶	232	Ok(Some(self.bisect_step(&st)))
	233	}
	234
	235	fn bisect_step(&self, st: &BisectState) -> BisectStep {
	236	if st.candidates.is_empty() {
75167672 Andy McCall 1 month ago	237	return BisectStep::NeedMarks {
	238	good: st.good.len(),
	239	bad: st.bad.len(),
	240	};
957fee30 Andy McCall 1 month ago ↶	241	}
957fee30 Andy McCall 1 month ago ↶	242	if st.hi <= st.lo + 1 {
75167672 Andy McCall 1 month ago	243	return BisectStep::Found {
	244	culprit: st.candidates[st.lo],
	245	};
957fee30 Andy McCall 1 month ago ↶	246	}
	247	match st.testing {
	248	Some(_) => {
	249	let remaining = st.hi - st.lo;
75167672 Andy McCall 1 month ago	250	BisectStep::Testing {
	251	heads: self.bisect_heads(st, st.testing.unwrap()),
	252	remaining,
	253	steps_left: (remaining as f64).log2().ceil() as u32,
	254	}
957fee30 Andy McCall 1 month ago ↶	255	}
75167672 Andy McCall 1 month ago	256	None => BisectStep::Inconclusive {
	257	candidates: st.candidates[st.lo..st.hi].to_vec(),
	258	},
957fee30 Andy McCall 1 month ago ↶	259	}
	260	}
	261
	262	/// `good ∪ candidates[..k]`, as heads.
	263	fn bisect_heads(&self, st: &BisectState, k: usize) -> Vec<ChangeHash> {
	264	let mut all = st.good.clone();
	265	all.extend(st.candidates[..k].iter().copied());
57eaac91 Andy McCall 1 month ago ↶	266	self.load_state_history(&all)
75167672 Andy McCall 1 month ago	267	.map(\|s\| s.maximal(&all))
75167672 Andy McCall 1 month ago	268	.unwrap_or(all)
957fee30 Andy McCall 1 month ago ↶	269	}
	270
	271	/// Check out the midpoint of the open range, skipping indices marked
	272	/// untestable, and record it as the state under test.
	273	fn bisect_advance(&self, st: &mut BisectState) -> Result<BisectStep> {
	274	if st.hi <= st.lo + 1 {
	275	st.testing = None;
	276	self.bisect_save(st)?;
75167672 Andy McCall 1 month ago	277	return Ok(BisectStep::Found {
	278	culprit: st.candidates[st.lo],
	279	});
957fee30 Andy McCall 1 month ago ↶	280	}
	281	let mid = st.lo + (st.hi - st.lo) / 2;
	282	// Try mid, then the nearest untried indices on either side.
	283	let mut order = vec![mid];
	284	for d in 1..(st.hi - st.lo) {
	285	if mid + d < st.hi {
	286	order.push(mid + d);
	287	}
	288	if mid > st.lo + d {
	289	order.push(mid - d);
	290	}
	291	}
	292	let Some(k) = order.into_iter().find(\|k\| !st.skipped.contains(k)) else {
	293	st.testing = None;
	294	self.bisect_save(st)?;
75167672 Andy McCall 1 month ago	295	return Ok(BisectStep::Inconclusive {
	296	candidates: st.candidates[st.lo..st.hi].to_vec(),
	297	});
957fee30 Andy McCall 1 month ago ↶	298	};
957fee30 Andy McCall 1 month ago ↶	299	let heads = self.bisect_heads(st, k);
75167672 Andy McCall 1 month ago	300	self.checkout(
	301	&heads,
	302	false,
	303	&format!("oxy bisect (testing {k} of {})", st.candidates.len()),
	304	)?;
957fee30 Andy McCall 1 month ago ↶	305	st.testing = Some(k);
	306	self.bisect_save(st)?;
	307	let remaining = st.hi - st.lo;
75167672 Andy McCall 1 month ago	308	Ok(BisectStep::Testing {
	309	heads,
	310	remaining,
	311	steps_left: (remaining as f64).log2().ceil() as u32,
	312	})
957fee30 Andy McCall 1 month ago ↶	313	}
	314
	315	/// Mark states good or bad. With `changes`, before the search starts,
	316	/// they name known-good or known-bad states; without, the state under
	317	/// test gets the verdict. `None` for `good` means skip (untestable).
	318	pub fn bisect_mark(&self, good: Option<bool>, changes: &[ChangeHash]) -> Result<BisectStep> {
75167672 Andy McCall 1 month ago	319	let Some(mut st) = self.bisect_load()? else {
	320	return fail("no bisect in progress; run `oxy bisect start`");
	321	};
957fee30 Andy McCall 1 month ago ↶	322	if !changes.is_empty() {
	323	if !st.candidates.is_empty() {
	324	return fail("the search has started; mark the state under test with plain `oxy bisect good\|bad`");
	325	}
	326	match good {
	327	Some(true) => st.good.extend(changes.iter().copied()),
	328	Some(false) => st.bad.extend(changes.iter().copied()),
	329	None => return fail("skip applies to the state under test"),
	330	}
	331	if st.good.is_empty() \|\| st.bad.is_empty() {
	332	self.bisect_save(&st)?;
75167672 Andy McCall 1 month ago	333	return Ok(BisectStep::NeedMarks {
	334	good: st.good.len(),
	335	bad: st.bad.len(),
	336	});
957fee30 Andy McCall 1 month ago ↶	337	}
57eaac91 Andy McCall 1 month ago ↶	338	let good_heads = self.load_state_history(&st.good)?.maximal(&st.good);
57eaac91 Andy McCall 1 month ago ↶	339	let bad_heads = self.load_state_history(&st.bad)?.maximal(&st.bad);
957fee30 Andy McCall 1 month ago ↶	340	st.good = good_heads.clone();
	341	st.bad = bad_heads.clone();
	342	st.candidates = self.negotiate(&good_heads, &bad_heads)?;
	343	if st.candidates.is_empty() {
	344	return fail("the bad state adds nothing to the good state; nothing to bisect");
	345	}
	346	st.lo = 0;
	347	st.hi = st.candidates.len();
	348	return self.bisect_advance(&mut st);
	349	}
	350	let Some(k) = st.testing else {
	351	return fail("no state is under test; give `oxy bisect good\|bad` a change or bookmark to start with");
	352	};
	353	match good {
	354	Some(true) => st.lo = k,
	355	Some(false) => st.hi = k,
	356	None => st.skipped.push(k),
	357	}
	358	self.bisect_advance(&mut st)
	359	}
	360
	361	/// Automate with a command run in the working copy: exit 0 is good, 125
	362	/// skips, anything else is bad.
	363	pub fn bisect_run(&self, command: &[String]) -> Result<BisectStep> {
75167672 Andy McCall 1 month ago	364	let Some(st) = self.bisect_load()? else {
	365	return fail("no bisect in progress; run `oxy bisect start`");
	366	};
957fee30 Andy McCall 1 month ago ↶	367	if st.testing.is_none() {
	368	return Ok(self.bisect_step(&st));
	369	}
	370	loop {
75167672 Andy McCall 1 month ago	371	let status = std::process::Command::new(&command[0])
	372	.args(&command[1..])
	373	.current_dir(&self.root)
	374	.status()
	375	.map_err(\|e\| RepoError::Msg(format!("running {}: {e}", command[0])))?;
957fee30 Andy McCall 1 month ago ↶	376	let verdict = match status.code() {
	377	Some(0) => Some(true),
	378	Some(125) => None,
	379	_ => Some(false),
	380	};
	381	match self.bisect_mark(verdict, &[])? {
	382	BisectStep::Testing { .. } => continue,
	383	done => return Ok(done),
	384	}
	385	}
	386	}
	387	}
6a81dbab Andy McCall 1 month ago ↶	388
	389	/// What `oxy describe` reports about the working copy (spec §10.1).
	390	#[derive(Clone, Debug, PartialEq, Eq)]
	391	pub struct Description {
	392	/// The tag of the base state, or the nearest tag below it.
	393	pub tag: Option<String>,
	394	/// Changes in the base state that the tag's state lacks (0: exact).
	395	pub distance: usize,
	396	pub bookmark: String,
	397	/// The base's newest head.
	398	pub change: ChangeId,
	399	pub hash: ChangeHash,
	400	/// Whether the working copy has uncommitted changes.
	401	pub dirty: bool,
	402	}
	403
	404	impl Description {
	405	/// `v1.2`, `v1.2-3-8c5ea12a`, or `develop-8c5ea12a`, and `-dirty`.
	406	pub fn line(&self) -> String {
	407	let short = self.change.short(8);
	408	let base = match (&self.tag, self.distance) {
	409	(Some(t), 0) => t.clone(),
	410	(Some(t), n) => format!("{t}-{n}-{short}"),
	411	(None, _) => format!("{}-{short}", self.bookmark),
	412	};
	413	if self.dirty {
	414	format!("{base}-dirty")
	415	} else {
	416	base
	417	}
	418	}
	419	}
	420
	421	impl Repo {
	422	/// Name the working copy for builds (`oxy describe`, like `git
	423	/// describe`): the tag of its base state; else the nearest tag whose
	424	/// state the base contains, with how many changes it adds and its
	425	/// newest head; else the bookmark and that head. `dirty` when the
	426	/// working copy has uncommitted changes.
	427	pub fn describe_working_copy(&self) -> Result<Description> {
	428	let snap = self.snapshot_status("oxy describe")?;
	429	let dirty = !snap.statuses.is_empty();
	430	let base = snap.base.maximal(&snap.wc.deps);
	431	let Some(&newest) = base
	432	.iter()
	433	.max_by_key(\|h\| snap.base.get(h).map(\|c\| (c.hlc, **h)))
	434	else {
	435	return fail("the working copy sits on no change yet");
	436	};
	437	let Some(change) = snap.base.get(&newest).map(\|m\| m.change_id) else {
	438	return fail("the working copy's base is not loaded");
	439	};
	440	let mut sorted = base.clone();
	441	sorted.sort();
	442	let mut best: Option<(usize, String)> = None;
	443	for t in self.tags()? {
	444	if !t.heads.iter().all(\|h\| snap.base.contains(h)) {
	445	continue;
	446	}
	447	let mut tagged: std::collections::HashSet<ChangeHash> =
	448	t.heads.iter().copied().collect();
	449	for h in &t.heads {
	450	tagged.extend(snap.base.closure(h).iter().copied());
	451	}
452	let mut heads = t.heads.clone();
453	heads.sort();
454	let distance = if heads == sorted {
455	0
456	} else {
457	snap.base.len().saturating_sub(tagged.len()).max(1)
458	};
459	if best
460	.as_ref()
461	.is_none_or(\|(d, n)\| distance < d \|\| (distance == d && t.name < *n))
462	{
463	best = Some((distance, t.name));
464	}
465	}
466	let (distance, tag) = match best {
467	Some((d, t)) => (d, Some(t)),
468	None => (0, None),
469	};
470	Ok(Description {
471	tag,
472	distance,
473	bookmark: self.config.bookmark.clone(),
474	change,
475	hash: newest,
476	dirty,
477	})
478	}
479	}

Keyboard