OXYGENHUB
# 89a1d0243544 oxygen / crates / oxy-core / src / repo / inspect.rs
11.3 KiB · Rust · last changed Bare repositories and an embeddable protocol server for Oxygenhub 1 month ago source blame history raw
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.
25 
    Testing { heads: Vec<ChangeHash>, remaining: usize, steps_left: u32 },
26 
    /// The first change whose inclusion makes the state bad.
27 
    Found { culprit: ChangeHash },
28 
    /// Every remaining candidate was skipped.
29 
    Inconclusive { candidates: Vec<ChangeHash> },
30 
}
31
32 
#[derive(Clone, Debug, Default)]
33 
struct BisectState {
34 
    start: Vec<ChangeHash>,
35 
    good: Vec<ChangeHash>,
36 
    bad: Vec<ChangeHash>,
37 
    candidates: Vec<ChangeHash>,
38 
    lo: usize,
39 
    hi: usize,
40 
    /// The prefix length currently checked out for testing.
41 
    testing: Option<usize>,
42 
    skipped: Vec<usize>,
43 
}
44
45 
fn hashes_line(v: &[ChangeHash]) -> String {
46 
    v.iter().map(|h| h.to_hex()).collect::<Vec<_>>().join(" ")
47 
}
48 
fn hashes_from(s: &str) -> Vec<ChangeHash> {
49 
    s.split_whitespace().filter_map(ObjectRef::from_hex).collect()
50 
}
51
52 
impl Repo {
53 
    /// The introducing change, author, and date of every line of `path` in
54 
    /// the working copy's base state (spec §27).
55 
    pub fn blame(&self, path: &str) -> Result<Vec<BlameLine>> {
56 
        let snap = self.snapshot("oxy blame")?;
57 
        self.blame_state(path, &snap.base, &snap.base_snapshot, "the working copy's base state")
58 
    }
59
60 
    /// Blame `path` in the state with these heads (hosted repositories).
61 
    pub fn blame_in(&self, path: &str, heads: &[ChangeHash]) -> Result<Vec<BlameLine>> {
62 
        let state = self.load_state(heads)?;
63 
        let snapshot = state.materialize();
64 
        self.blame_state(path, &state, &snapshot, "that state")
65 
    }
66
67 
    fn blame_state(&self, path: &str, state: &crate::state::State, snapshot: &crate::state::Snapshot, what: &str) -> Result<Vec<BlameLine>> {
68 
        let Some(f) = snapshot.files.get(path) else { return fail(format!("{path} is not in {what}")) };
69 
        if !matches!(f.content, FileContent::Text { .. }) {
70 
            return fail(format!("{path} is not a text file"));
71 
        }
72 
        let mut out = Vec::new();
73 
        for (i, ((hash, index), text)) in state.live_lines(&f.node).into_iter().enumerate() {
74 
            let meta = state.get(&hash);
75 
            let author = match meta {
76 
                Some(m) if !m.author.is_zero() => self.store.get_identity(&m.author).map(|id| id.name).unwrap_or_else(|_| m.author.short(12)),
77 
                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()),
78 
                None => "unknown".into(),
79 
            };
80 
            out.push(BlameLine {
81 
                line: i + 1,
82 
                hash,
83 
                index,
84 
                change_id: meta.map(|m| m.change_id).unwrap_or(ChangeId([0; 16])),
85 
                author,
86 
                when_ms: meta.map(|m| m.hlc.wall_ms).unwrap_or(0),
87 
                text,
88 
            });
89 
        }
90 
        Ok(out)
91 
    }
92
93 
    // ------------------------------------------------------------ bisect
94
95 
    fn bisect_dir(&self) -> PathBuf {
96 
        self.oxy.join("bisect")
97 
    }
98
99 
    fn bisect_load(&self) -> Result<Option<BisectState>> {
100 
        let dir = self.bisect_dir();
101 
        if !dir.join("start").exists() {
102 
            return Ok(None);
103 
        }
104 
        let read = |name: &str| fs::read_to_string(dir.join(name)).unwrap_or_default();
105 
        let nums: Vec<usize> = read("range").split_whitespace().filter_map(|n| n.parse().ok()).collect();
106 
        Ok(Some(BisectState {
107 
            start: hashes_from(&read("start")),
108 
            good: hashes_from(&read("good")),
109 
            bad: hashes_from(&read("bad")),
110 
            candidates: hashes_from(&read("candidates")),
111 
            lo: nums.first().copied().unwrap_or(0),
112 
            hi: nums.get(1).copied().unwrap_or(0),
113 
            testing: nums.get(2).copied().filter(|_| nums.len() > 2),
114 
            skipped: read("skipped").split_whitespace().filter_map(|n| n.parse().ok()).collect(),
115 
        }))
116 
    }
117
118 
    fn bisect_save(&self, st: &BisectState) -> Result<()> {
119 
        let dir = self.bisect_dir();
120 
        fs::create_dir_all(&dir)?;
121 
        write_atomic(&dir.join("start"), hashes_line(&st.start).as_bytes())?;
122 
        write_atomic(&dir.join("good"), hashes_line(&st.good).as_bytes())?;
123 
        write_atomic(&dir.join("bad"), hashes_line(&st.bad).as_bytes())?;
124 
        write_atomic(&dir.join("candidates"), hashes_line(&st.candidates).as_bytes())?;
125 
        let mut range = format!("{} {}", st.lo, st.hi);
126 
        if let Some(t) = st.testing {
127 
            range.push_str(&format!(" {t}"));
128 
        }
129 
        write_atomic(&dir.join("range"), range.as_bytes())?;
130 
        write_atomic(&dir.join("skipped"), st.skipped.iter().map(|n| n.to_string()).collect::<Vec<_>>().join(" ").as_bytes())?;
131 
        Ok(())
132 
    }
133
134 
    /// Begin a bisect: remembers the working copy's base to restore later.
135 
    pub fn bisect_start(&self) -> Result<()> {
136 
        if self.bisect_load()?.is_some() {
137 
            return fail("a bisect is in progress; finish it or run `oxy bisect reset`");
138 
        }
139 
        let (_, wc) = self.working_copy()?;
140 
        let start = self.load_state(&wc.deps)?.maximal(&wc.deps);
141 
        self.bisect_save(&BisectState { start, ..Default::default() })
142 
    }
143
144 
    pub fn bisect_reset(&self) -> Result<()> {
145 
        let Some(st) = self.bisect_load()? else { return fail("no bisect in progress") };
146 
        self.checkout(&st.start, false, "oxy bisect reset")?;
147 
        fs::remove_dir_all(self.bisect_dir())?;
148 
        Ok(())
149 
    }
150
151 
    pub fn bisect_status(&self) -> Result<Option<BisectStep>> {
152 
        let Some(st) = self.bisect_load()? else { return Ok(None) };
153 
        Ok(Some(self.bisect_step(&st)))
154 
    }
155
156 
    fn bisect_step(&self, st: &BisectState) -> BisectStep {
157 
        if st.candidates.is_empty() {
158 
            return BisectStep::NeedMarks { good: st.good.len(), bad: st.bad.len() };
159 
        }
160 
        if st.hi <= st.lo + 1 {
161 
            return BisectStep::Found { culprit: st.candidates[st.lo] };
162 
        }
163 
        match st.testing {
164 
            Some(_) => {
165 
                let remaining = st.hi - st.lo;
166 
                BisectStep::Testing { heads: self.bisect_heads(st, st.testing.unwrap()), remaining, steps_left: (remaining as f64).log2().ceil() as u32 }
167 
            }
168 
            None => BisectStep::Inconclusive { candidates: st.candidates[st.lo..st.hi].to_vec() },
169 
        }
170 
    }
171
172 
    /// `good ∪ candidates[..k]`, as heads.
173 
    fn bisect_heads(&self, st: &BisectState, k: usize) -> Vec<ChangeHash> {
174 
        let mut all = st.good.clone();
175 
        all.extend(st.candidates[..k].iter().copied());
176 
        self.load_state(&all).map(|s| s.maximal(&all)).unwrap_or(all)
177 
    }
178
179 
    /// Check out the midpoint of the open range, skipping indices marked
180 
    /// untestable, and record it as the state under test.
181 
    fn bisect_advance(&self, st: &mut BisectState) -> Result<BisectStep> {
182 
        if st.hi <= st.lo + 1 {
183 
            st.testing = None;
184 
            self.bisect_save(st)?;
185 
            return Ok(BisectStep::Found { culprit: st.candidates[st.lo] });
186 
        }
187 
        let mid = st.lo + (st.hi - st.lo) / 2;
188 
        // Try mid, then the nearest untried indices on either side.
189 
        let mut order = vec![mid];
190 
        for d in 1..(st.hi - st.lo) {
191 
            if mid + d < st.hi {
192 
                order.push(mid + d);
193 
            }
194 
            if mid > st.lo + d {
195 
                order.push(mid - d);
196 
            }
197 
        }
198 
        let Some(k) = order.into_iter().find(|k| !st.skipped.contains(k)) else {
199 
            st.testing = None;
200 
            self.bisect_save(st)?;
201 
            return Ok(BisectStep::Inconclusive { candidates: st.candidates[st.lo..st.hi].to_vec() });
202 
        };
203 
        let heads = self.bisect_heads(st, k);
204 
        self.checkout(&heads, false, &format!("oxy bisect (testing {k} of {})", st.candidates.len()))?;
205 
        st.testing = Some(k);
206 
        self.bisect_save(st)?;
207 
        let remaining = st.hi - st.lo;
208 
        Ok(BisectStep::Testing { heads, remaining, steps_left: (remaining as f64).log2().ceil() as u32 })
209 
    }
210
211 
    /// Mark states good or bad. With `changes`, before the search starts,
212 
    /// they name known-good or known-bad states; without, the state under
213 
    /// test gets the verdict. `None` for `good` means skip (untestable).
214 
    pub fn bisect_mark(&self, good: Option<bool>, changes: &[ChangeHash]) -> Result<BisectStep> {
215 
        let Some(mut st) = self.bisect_load()? else { return fail("no bisect in progress; run `oxy bisect start`") };
216 
        if !changes.is_empty() {
217 
            if !st.candidates.is_empty() {
218 
                return fail("the search has started; mark the state under test with plain `oxy bisect good|bad`");
219 
            }
220 
            match good {
221 
                Some(true) => st.good.extend(changes.iter().copied()),
222 
                Some(false) => st.bad.extend(changes.iter().copied()),
223 
                None => return fail("skip applies to the state under test"),
224 
            }
225 
            if st.good.is_empty() || st.bad.is_empty() {
226 
                self.bisect_save(&st)?;
227 
                return Ok(BisectStep::NeedMarks { good: st.good.len(), bad: st.bad.len() });
228 
            }
229 
            let good_heads = self.load_state(&st.good)?.maximal(&st.good);
230 
            let bad_heads = self.load_state(&st.bad)?.maximal(&st.bad);
231 
            st.good = good_heads.clone();
232 
            st.bad = bad_heads.clone();
233 
            st.candidates = self.negotiate(&good_heads, &bad_heads)?;
234 
            if st.candidates.is_empty() {
235 
                return fail("the bad state adds nothing to the good state; nothing to bisect");
236 
            }
237 
            st.lo = 0;
238 
            st.hi = st.candidates.len();
239 
            return self.bisect_advance(&mut st);
240 
        }
241 
        let Some(k) = st.testing else {
242 
            return fail("no state is under test; give `oxy bisect good|bad` a change or bookmark to start with");
243 
        };
244 
        match good {
245 
            Some(true) => st.lo = k,
246 
            Some(false) => st.hi = k,
247 
            None => st.skipped.push(k),
248 
        }
249 
        self.bisect_advance(&mut st)
250 
    }
251
252 
    /// Automate with a command run in the working copy: exit 0 is good, 125
253 
    /// skips, anything else is bad.
254 
    pub fn bisect_run(&self, command: &[String]) -> Result<BisectStep> {
255 
        let Some(st) = self.bisect_load()? else { return fail("no bisect in progress; run `oxy bisect start`") };
256 
        if st.testing.is_none() {
257 
            return Ok(self.bisect_step(&st));
258 
        }
259 
        loop {
260 
            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])))?;
261 
            let verdict = match status.code() {
262 
                Some(0) => Some(true),
263 
                Some(125) => None,
264 
                _ => Some(false),
265 
            };
266 
            match self.bisect_mark(verdict, &[])? {
267 
                BisectStep::Testing { .. } => continue,
268 
                done => return Ok(done),
269 
            }
270 
        }
271 
    }
272 
}