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