git-ents.gitmain
⌘K
foforge

crates/kernel/ents-query/src/eval.rs

eval.rs809 lines · 29.6 KB · rusthistorycomment on this file
1//! Query evaluation: full sets, incremental entry sets, and work sets
2//! (`query.incremental`, `query.monotone`, `query.workset`).
3//!
4//! # Evaluation model
5//!
6//! The evaluator is pure over the read half of the ref store plus
7//! gitoxide's object-find seam. A [`Transition`] carries both sides of
8//! one ref's movement; every internal read goes through a state view
9//! that overrides that one ref, so the same evaluator answers "was this
10//! commit in the set before?" and "is it now?" against a single store.
11//!
12//! # Incrementality (`query.incremental`)
13//!
14//! An entry set is computed from the transition frontier: candidate
15//! commits come only from the symmetric difference of the affected
16//! atoms (a generation-bounded paint-down walk between the old and new
17//! tips for `rev`, the one tested commit for `results`, the two tips
18//! for `meta`), then each candidate is membership-tested against the
19//! new and old states — reachability tests pruned by generation
20//! numbers, results tests by refname scan (`query.results`), never a
21//! walk of full history. Generation numbers are computed lazily and
22//! memoized per evaluator; a persistent commit-graph file is a later
23//! optimization with the same bound.
24//!
25//! # Monotonicity (`query.monotone`)
26//!
27//! Entry sets are additions only. A shrinking ref (force-push, branch
28//! deletion) produces an empty or smaller entry set; nothing is ever
29//! retracted, because the only durable record — a written result —
30//! lives in immutable history, and the work set subtracts it by
31//! refname scan.
32
33use std::cell::RefCell;
34use std::collections::{BTreeSet, BinaryHeap, HashMap, HashSet};
35use std::rc::Rc;
36
37use ents_model::{ResultRecord, Status};
38use gix::refs::FullName;
39use gix_hash::ObjectId;
40use gix_object::{CommitRef, Find, Kind};
41use gix_ref_store::RefStoreRead;
42
43use crate::ast::{Query, StatusFilter};
44use crate::error::{EvalError, EvalResult};
45use crate::rev::{RevExpr, RevTerm, dwim_candidates};
46
47/// One ref's movement, as `receive` observes it: the refname, the tip
48/// before, and the tip after (`None` on either side for creation and
49/// deletion).
50///
51/// # Examples
52///
53/// ```
54/// use ents_query::Transition;
55///
56/// let t = Transition {
57/// name: "refs/heads/main".try_into().expect("valid"),
58/// old: None,
59/// new: Some(gix_hash::ObjectId::null(gix_hash::Kind::Sha1)),
60/// };
61/// assert!(t.old.is_none());
62/// ```
63#[derive(Debug, Clone, PartialEq, Eq)]
64pub struct Transition {
65 /// The ref that moved.
66 pub name: FullName,
67 /// Its tip before the transition (`None`: the ref did not exist).
68 pub old: Option<ObjectId>,
69 /// Its tip after the transition (`None`: the ref was deleted).
70 pub new: Option<ObjectId>,
71}
72
73/// Which side of a [`Transition`] a read observes.
74#[derive(Debug, Clone, Copy, PartialEq, Eq)]
75enum Side {
76 Old,
77 New,
78}
79
80/// Cached structure of one commit: parents and generation number
81/// (1 + the maximum parent generation; roots are generation 1).
82#[derive(Debug)]
83struct CommitInfo {
84 parents: Vec<ObjectId>,
85 generation: u64,
86}
87
88/// A `CommitQuery` evaluator over one ref store and one object store.
89///
90/// Caches commit structure (parents, generation numbers) and result
91/// statuses across calls, so reusing one evaluator across many
92/// transitions amortizes history walks — the shape a long-lived
93/// `receive` process has.
94///
95/// # Examples
96///
97/// ```
98/// use ents_query::{Evaluator, Query};
99/// use ents_testutil::{MemRefStore, ObjectStore, advance_ref};
100///
101/// let refs = MemRefStore::default();
102/// let objects = ObjectStore::default();
103/// let commits = advance_ref(&refs, &objects, "refs/heads/main", 2, 100);
104///
105/// let query: Query = "rev(refs/heads/main)".parse().expect("valid");
106/// let evaluator = Evaluator::new(&refs, &objects);
107/// let set = evaluator.eval(&query).expect("evaluates");
108/// assert_eq!(set.len(), 2);
109/// assert!(set.contains(&commits[0]) && set.contains(&commits[1]));
110/// ```
111pub struct Evaluator<'a> {
112 refs: &'a dyn RefStoreRead,
113 objects: &'a dyn Find,
114 info: RefCell<HashMap<ObjectId, Rc<CommitInfo>>>,
115 status: RefCell<HashMap<ObjectId, Status>>,
116}
117
118impl std::fmt::Debug for Evaluator<'_> {
119 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
120 f.debug_struct("Evaluator")
121 .field("cached_commits", &self.info.borrow().len())
122 .finish_non_exhaustive()
123 }
124}
125
126impl<'a> Evaluator<'a> {
127 /// Build an evaluator over `refs` and `objects`.
128 pub fn new(refs: &'a dyn RefStoreRead, objects: &'a dyn Find) -> Self {
129 Self {
130 refs,
131 objects,
132 info: RefCell::new(HashMap::new()),
133 status: RefCell::new(HashMap::new()),
134 }
135 }
136
137 // -- public API ----------------------------------------------------
138
139 /// The full set `query` denotes against current ref state — the
140 /// reconciliation-grade evaluation (boot-time work-set scans);
141 /// steady-state consumers use [`Evaluator::entry_set`].
142 pub fn eval(&self, query: &Query) -> EvalResult<BTreeSet<ObjectId>> {
143 self.eval_side(query, None, Side::New)
144 }
145
146 /// Whether `oid` is in `query`'s set against current ref state.
147 ///
148 /// Reachability tests are pruned by generation numbers; results
149 /// tests are refname scans (`query.results`).
150 pub fn contains(&self, query: &Query, oid: ObjectId) -> EvalResult<bool> {
151 self.contains_side(query, oid, None, Side::New)
152 }
153
154 /// The commits that *enter* `query`'s set under `transition`,
155 /// computed incrementally from that frontier (`query.incremental`)
156 /// with entry-only semantics (`query.monotone`): an effect fires
157 /// once per commit in this set; commits leaving the set appear
158 /// nowhere and retract nothing.
159 ///
160 /// # Examples
161 ///
162 /// ```
163 /// use ents_query::{Evaluator, Query, Transition};
164 /// use ents_testutil::{MemRefStore, ObjectStore, advance_ref};
165 ///
166 /// let refs = MemRefStore::default();
167 /// let objects = ObjectStore::default();
168 /// let first = advance_ref(&refs, &objects, "refs/heads/main", 1, 100);
169 /// let second = advance_ref(&refs, &objects, "refs/heads/main", 1, 200);
170 ///
171 /// let query: Query = "rev(refs/heads/main)".parse().expect("valid");
172 /// let evaluator = Evaluator::new(&refs, &objects);
173 /// let entered = evaluator.entry_set(&query, &Transition {
174 /// name: "refs/heads/main".try_into().expect("valid"),
175 /// old: Some(first[0]),
176 /// new: Some(second[0]),
177 /// }).expect("evaluates");
178 /// assert_eq!(entered.into_iter().collect::<Vec<_>>(), vec![second[0]]);
179 /// ```
180 // @relation(query.incremental, query.monotone, scope=function)
181 pub fn entry_set(
182 &self,
183 query: &Query,
184 transition: &Transition,
185 ) -> EvalResult<BTreeSet<ObjectId>> {
186 if !query.footprint().matches(transition.name.as_ref()) {
187 return Ok(BTreeSet::new());
188 }
189 let mut candidates = HashSet::new();
190 self.collect_candidates(query, transition, &mut candidates)?;
191 let mut entered = BTreeSet::new();
192 for oid in candidates {
193 if self.contains_side(query, oid, Some(transition), Side::New)?
194 && !self.contains_side(query, oid, Some(transition), Side::Old)?
195 {
196 entered.insert(oid);
197 }
198 }
199 Ok(entered)
200 }
201
202 /// The work set for `effect` under `transition`:
203 /// `trigger − results(self, any)` with `self` substituted here, at
204 /// evaluation time — the entry set of the trigger minus every
205 /// commit already carrying any recorded result for `effect`, by
206 /// refname scan of the effect's results namespace, never a walk of
207 /// history (`query.workset`).
208 ///
209 /// The effect's own results ref is the sole materialization marker:
210 /// there is no pipeline state anywhere else to consult.
211 // @relation(query.workset, scope=function)
212 pub fn work_set(
213 &self,
214 effect: &str,
215 trigger: &Query,
216 transition: &Transition,
217 ) -> EvalResult<BTreeSet<ObjectId>> {
218 let entered = self.entry_set(trigger, transition)?;
219 self.subtract_results(effect, entered, Some(transition))
220 }
221
222 /// The full outstanding set for `effect` against current ref
223 /// state: `eval(trigger) − results(self, any)` — the boot-time
224 /// reconciliation form of [`Evaluator::work_set`], from which the
225 /// obligation queue is reconstructible (`query.workset`).
226 // @relation(query.workset, scope=function)
227 pub fn outstanding(&self, effect: &str, trigger: &Query) -> EvalResult<BTreeSet<ObjectId>> {
228 let full = self.eval(trigger)?;
229 self.subtract_results(effect, full, None)
230 }
231
232 fn subtract_results(
233 &self,
234 effect: &str,
235 set: BTreeSet<ObjectId>,
236 transition: Option<&Transition>,
237 ) -> EvalResult<BTreeSet<ObjectId>> {
238 let recorded = self.results_index(effect, StatusFilter::Any, transition, Side::New)?;
239 Ok(set
240 .into_iter()
241 .filter(|oid| !prefix_matches(&recorded, *oid))
242 .collect())
243 }
244
245 // -- state views ---------------------------------------------------
246
247 /// Resolve `name` in the given state: the transition overrides its
248 /// own ref on both sides, so the underlying store may hold either
249 /// the pre- or post-transition value.
250 fn resolve(
251 &self,
252 name: &str,
253 transition: Option<&Transition>,
254 side: Side,
255 ) -> EvalResult<Option<ObjectId>> {
256 if let Some(t) = transition
257 && t.name.as_bstr() == name
258 {
259 return Ok(match side {
260 Side::Old => t.old,
261 Side::New => t.new,
262 });
263 }
264 let Ok(full) = FullName::try_from(name.to_owned()) else {
265 return Ok(None);
266 };
267 Ok(self.refs.get(full.as_ref())?)
268 }
269
270 /// All refs under `prefix` in the given state, transition applied.
271 fn iter_refs(
272 &self,
273 prefix: &str,
274 transition: Option<&Transition>,
275 side: Side,
276 ) -> EvalResult<Vec<(String, ObjectId)>> {
277 let mut out = Vec::new();
278 for entry in self.refs.iter_prefix(prefix)? {
279 let (name, oid) = entry?;
280 out.push((name.as_bstr().to_string(), oid));
281 }
282 if let Some(t) = transition {
283 let name = t.name.as_bstr().to_string();
284 if name.starts_with(prefix) {
285 out.retain(|(n, _)| *n != name);
286 let value = match side {
287 Side::Old => t.old,
288 Side::New => t.new,
289 };
290 if let Some(oid) = value {
291 out.push((name, oid));
292 }
293 }
294 }
295 Ok(out)
296 }
297
298 // -- atoms ---------------------------------------------------------
299
300 /// The positive and negative tip sets of a rev expression in one
301 /// state. Short names resolve through the gitrevisions lookup
302 /// order; an unresolved name contributes nothing (a trigger over a
303 /// not-yet-created branch denotes the empty set); globs expand over
304 /// `refs/*` minus `refs/meta/*`, which is outside `rev()`'s domain
305 /// by definition (`query.rev`).
306 // @relation(query.rev, scope=function)
307 fn rev_tips(
308 &self,
309 expr: &RevExpr,
310 transition: Option<&Transition>,
311 side: Side,
312 ) -> EvalResult<(Vec<ObjectId>, Vec<ObjectId>)> {
313 let resolve_terms = |terms: &[RevTerm]| -> EvalResult<Vec<ObjectId>> {
314 let mut tips = Vec::new();
315 for term in terms {
316 match term {
317 RevTerm::Oid(oid) => tips.push(*oid),
318 RevTerm::Name(name) => {
319 for candidate in dwim_candidates(name) {
320 if let Some(oid) = self.resolve(&candidate, transition, side)? {
321 tips.push(oid);
322 break;
323 }
324 }
325 }
326 RevTerm::Glob(pattern) => {
327 for (name, oid) in self.iter_refs("refs/", transition, side)? {
328 if !name.starts_with("refs/meta/") && pattern.matches_str(&name) {
329 tips.push(oid);
330 }
331 }
332 }
333 }
334 }
335 Ok(tips)
336 };
337 Ok((
338 resolve_terms(expr.include())?,
339 resolve_terms(expr.exclude())?,
340 ))
341 }
342
343 /// The recorded-result index for one effect in one state: the
344 /// short-oid refname segments (hex prefixes of tested commits)
345 /// whose recorded status satisfies `filter` — a scan of refname
346 /// patterns under the effect's results namespace, never a walk of
347 /// commit history (`query.results`).
348 // @relation(query.results, scope=function)
349 fn results_index(
350 &self,
351 effect: &str,
352 filter: StatusFilter,
353 transition: Option<&Transition>,
354 side: Side,
355 ) -> EvalResult<Vec<String>> {
356 let prefix = format!("refs/meta/results/{effect}/");
357 let mut shorts = Vec::new();
358 for (name, tip) in self.iter_refs(&prefix, transition, side)? {
359 let Some(short) = name.strip_prefix(&prefix) else {
360 continue;
361 };
362 if short.contains('/') || short.is_empty() {
363 continue;
364 }
365 if filter == StatusFilter::Any || filter.admits(self.result_status(&name, tip)?) {
366 shorts.push(short.to_ascii_lowercase());
367 }
368 }
369 Ok(shorts)
370 }
371
372 /// The recorded status behind one results ref tip, cached: the tip
373 /// commit's tree deserialized as a [`ResultRecord`], of which the
374 /// status is one field (`model.result-identity`: the tree also carries
375 /// the effect and judged commit, so a signed status means something
376 /// with the refname stripped away).
377 fn result_status(&self, name: &str, tip: ObjectId) -> EvalResult<Status> {
378 if let Some(status) = self.status.borrow().get(&tip) {
379 return Ok(*status);
380 }
381 let tree = self.commit_tree(tip)?;
382 let record: ResultRecord =
383 facet_git_tree::deserialize(&tree, self.objects).map_err(|source| {
384 EvalError::Status {
385 name: name.to_owned(),
386 source,
387 }
388 })?;
389 self.status.borrow_mut().insert(tip, record.status);
390 Ok(record.status)
391 }
392
393 /// The tip commits of every author-written meta-ref matching the
394 /// glob (`query.meta`); the parser already guarantees the glob
395 /// cannot match an effect-written namespace.
396 // @relation(query.meta, scope=function)
397 fn meta_tips(
398 &self,
399 pattern: &crate::pattern::RefPattern,
400 transition: Option<&Transition>,
401 side: Side,
402 ) -> EvalResult<Vec<ObjectId>> {
403 let mut tips = Vec::new();
404 for (name, oid) in self.iter_refs("refs/meta/", transition, side)? {
405 if pattern.matches_str(&name) {
406 tips.push(oid);
407 }
408 }
409 Ok(tips)
410 }
411
412 // -- full evaluation ------------------------------------------------
413
414 fn eval_side(
415 &self,
416 query: &Query,
417 transition: Option<&Transition>,
418 side: Side,
419 ) -> EvalResult<BTreeSet<ObjectId>> {
420 match query {
421 Query::Rev(expr) => {
422 let (include, exclude) = self.rev_tips(expr, transition, side)?;
423 let reached = self.reachable(&include)?;
424 let excluded = self.reachable(&exclude)?;
425 Ok(reached.difference(&excluded).copied().collect())
426 }
427 Query::Results { effect, status } => {
428 let shorts = self.results_index(effect, *status, transition, side)?;
429 let universe = self.universe(transition, side)?;
430 Ok(universe
431 .into_iter()
432 .filter(|oid| prefix_matches(&shorts, *oid))
433 .collect())
434 }
435 Query::Meta(pattern) => Ok(self
436 .meta_tips(pattern, transition, side)?
437 .into_iter()
438 .collect()),
439 // @relation(query.set-ops, scope=function)
440 Query::Op { op, lhs, rhs } => {
441 let l = self.eval_side(lhs, transition, side)?;
442 let r = self.eval_side(rhs, transition, side)?;
443 Ok(match op {
444 crate::ast::SetOp::Union => l.union(&r).copied().collect(),
445 crate::ast::SetOp::Intersect => l.intersection(&r).copied().collect(),
446 crate::ast::SetOp::Difference => l.difference(&r).copied().collect(),
447 })
448 }
449 }
450 }
451
452 /// Every commit reachable from any ref in the given state — the
453 /// resolution universe for standalone `results()` evaluation, where
454 /// the refname scan yields hex prefixes that must name real
455 /// commits. Only full (reconciliation-grade) evaluation pays this;
456 /// membership tests compare prefixes directly.
457 fn universe(
458 &self,
459 transition: Option<&Transition>,
460 side: Side,
461 ) -> EvalResult<HashSet<ObjectId>> {
462 let tips: Vec<ObjectId> = self
463 .iter_refs("refs/", transition, side)?
464 .into_iter()
465 .map(|(_, oid)| oid)
466 .collect();
467 self.reachable(&tips)
468 }
469
470 // -- membership -----------------------------------------------------
471
472 fn contains_side(
473 &self,
474 query: &Query,
475 oid: ObjectId,
476 transition: Option<&Transition>,
477 side: Side,
478 ) -> EvalResult<bool> {
479 match query {
480 Query::Rev(expr) => {
481 let (include, exclude) = self.rev_tips(expr, transition, side)?;
482 Ok(self.reaches(&include, oid)? && !self.reaches(&exclude, oid)?)
483 }
484 Query::Results { effect, status } => {
485 let shorts = self.results_index(effect, *status, transition, side)?;
486 Ok(prefix_matches(&shorts, oid))
487 }
488 Query::Meta(pattern) => Ok(self.meta_tips(pattern, transition, side)?.contains(&oid)),
489 Query::Op { op, lhs, rhs } => {
490 let l = self.contains_side(lhs, oid, transition, side)?;
491 let r = self.contains_side(rhs, oid, transition, side)?;
492 Ok(match op {
493 crate::ast::SetOp::Union => l || r,
494 crate::ast::SetOp::Intersect => l && r,
495 crate::ast::SetOp::Difference => l && !r,
496 })
497 }
498 }
499 }
500
501 // -- candidates -----------------------------------------------------
502
503 /// Commits whose membership in some atom of `query` can have
504 /// changed under `transition` — the frontier the entry set is
505 /// filtered from. Everything else provably kept its membership in
506 /// every atom, so it cannot have entered the composite.
507 fn collect_candidates(
508 &self,
509 query: &Query,
510 transition: &Transition,
511 out: &mut HashSet<ObjectId>,
512 ) -> EvalResult<()> {
513 let moved = transition.name.as_bstr().to_string();
514 match query {
515 Query::Rev(expr) => {
516 if expr
517 .patterns()
518 .iter()
519 .any(|pattern| pattern.matches_str(&moved))
520 {
521 let old: Vec<_> = transition.old.into_iter().collect();
522 let new: Vec<_> = transition.new.into_iter().collect();
523 out.extend(self.ahead_of(&new, &old)?);
524 out.extend(self.ahead_of(&old, &new)?);
525 }
526 }
527 Query::Results { effect, .. } => {
528 let prefix = format!("refs/meta/results/{effect}/");
529 if let Some(short) = moved.strip_prefix(&prefix)
530 && !short.contains('/')
531 && let Some(tested) = self.resolve_short(short, transition)?
532 {
533 out.insert(tested);
534 }
535 }
536 Query::Meta(pattern) => {
537 if pattern.matches_str(&moved) {
538 out.extend(transition.old);
539 out.extend(transition.new);
540 }
541 }
542 Query::Op { lhs, rhs, .. } => {
543 self.collect_candidates(lhs, transition, out)?;
544 self.collect_candidates(rhs, transition, out)?;
545 }
546 }
547 Ok(())
548 }
549
550 /// Resolve a results refname's short-oid segment to the full tested
551 /// commit id, searching commits reachable from the post-transition
552 /// ref state. A prefix that resolves to nothing reachable yields no
553 /// candidate: an unreachable commit is not an actionable entry.
554 fn resolve_short(&self, short: &str, transition: &Transition) -> EvalResult<Option<ObjectId>> {
555 let short = short.to_ascii_lowercase();
556 let universe = self.universe(Some(transition), Side::New)?;
557 Ok(universe
558 .into_iter()
559 .find(|oid| oid.to_string().starts_with(&short)))
560 }
561
562 // -- commit walks ----------------------------------------------------
563
564 /// Structure of `oid`, cached: parents and generation number,
565 /// resolved iteratively so a long first-parent chain cannot
566 /// overflow the stack.
567 fn commit_info(&self, oid: ObjectId) -> EvalResult<Rc<CommitInfo>> {
568 if let Some(info) = self.info.borrow().get(&oid) {
569 return Ok(Rc::clone(info));
570 }
571 let mut pending: HashMap<ObjectId, Vec<ObjectId>> = HashMap::new();
572 let mut stack = vec![oid];
573 while let Some(&top) = stack.last() {
574 if self.info.borrow().contains_key(&top) {
575 stack.pop();
576 continue;
577 }
578 let parents = match pending.get(&top) {
579 Some(parents) => parents.clone(),
580 None => {
581 let parents = self.read_parents(top)?;
582 pending.insert(top, parents.clone());
583 parents
584 }
585 };
586 let unresolved: Vec<ObjectId> = {
587 let cache = self.info.borrow();
588 parents
589 .iter()
590 .filter(|p| !cache.contains_key(*p))
591 .copied()
592 .collect()
593 };
594 if unresolved.is_empty() {
595 let generation = {
596 let cache = self.info.borrow();
597 parents
598 .iter()
599 .filter_map(|p| cache.get(p).map(|i| i.generation))
600 .max()
601 .unwrap_or(0)
602 .saturating_add(1)
603 };
604 self.info.borrow_mut().insert(
605 top,
606 Rc::new(CommitInfo {
607 parents,
608 generation,
609 }),
610 );
611 stack.pop();
612 } else {
613 stack.extend(unresolved);
614 }
615 }
616 let cache = self.info.borrow();
617 cache
618 .get(&oid)
619 .map(Rc::clone)
620 .ok_or(EvalError::Missing { oid })
621 }
622
623 fn read_parents(&self, oid: ObjectId) -> EvalResult<Vec<ObjectId>> {
624 let mut buf = Vec::new();
625 let data = self
626 .objects
627 .try_find(&oid, &mut buf)
628 .map_err(|source| EvalError::Object { oid, source })?
629 .ok_or(EvalError::Missing { oid })?;
630 if data.kind != Kind::Commit {
631 return Err(EvalError::Decode {
632 oid,
633 detail: format!("expected a commit, found a {}", data.kind),
634 });
635 }
636 let commit =
637 CommitRef::from_bytes(data.data, oid.kind()).map_err(|e| EvalError::Decode {
638 oid,
639 detail: e.to_string(),
640 })?;
641 Ok(commit.parents().collect())
642 }
643
644 /// The tree of the commit at `oid`.
645 fn commit_tree(&self, oid: ObjectId) -> EvalResult<ObjectId> {
646 let mut buf = Vec::new();
647 let data = self
648 .objects
649 .try_find(&oid, &mut buf)
650 .map_err(|source| EvalError::Object { oid, source })?
651 .ok_or(EvalError::Missing { oid })?;
652 if data.kind != Kind::Commit {
653 return Err(EvalError::Decode {
654 oid,
655 detail: format!("expected a commit, found a {}", data.kind),
656 });
657 }
658 let commit =
659 CommitRef::from_bytes(data.data, oid.kind()).map_err(|e| EvalError::Decode {
660 oid,
661 detail: e.to_string(),
662 })?;
663 Ok(commit.tree())
664 }
665
666 /// Everything reachable from `tips` (inclusive) — full-walk
667 /// reachability, used by reconciliation-grade evaluation only.
668 fn reachable(&self, tips: &[ObjectId]) -> EvalResult<HashSet<ObjectId>> {
669 let mut seen = HashSet::new();
670 let mut queue: Vec<ObjectId> = tips.to_vec();
671 while let Some(oid) = queue.pop() {
672 if !seen.insert(oid) {
673 continue;
674 }
675 queue.extend(self.commit_info(oid)?.parents.iter().copied());
676 }
677 Ok(seen)
678 }
679
680 /// Whether any tip reaches `target` by parent edges, pruning every
681 /// path once its generation drops below `target`'s — the
682 /// generation-number bound of `query.incremental`.
683 fn reaches(&self, tips: &[ObjectId], target: ObjectId) -> EvalResult<bool> {
684 if tips.contains(&target) {
685 return Ok(true);
686 }
687 if tips.is_empty() {
688 return Ok(false);
689 }
690 let floor = self.commit_info(target)?.generation;
691 let mut heap = BinaryHeap::new();
692 let mut seen = HashSet::new();
693 for &tip in tips {
694 let info = self.commit_info(tip)?;
695 if info.generation >= floor && seen.insert(tip) {
696 heap.push((info.generation, tip));
697 }
698 }
699 while let Some((_, oid)) = heap.pop() {
700 if oid == target {
701 return Ok(true);
702 }
703 for parent in self.commit_info(oid)?.parents.iter().copied() {
704 if seen.insert(parent) {
705 let generation = self.commit_info(parent)?.generation;
706 if generation >= floor {
707 heap.push((generation, parent));
708 }
709 }
710 }
711 }
712 Ok(false)
713 }
714
715 /// Commits reachable from `new_tips` but not from `old_tips` — the
716 /// transition frontier, walked in descending generation order so
717 /// old-side paint stops at the frontier's own depth instead of
718 /// walking to the roots.
719 fn ahead_of(&self, new_tips: &[ObjectId], old_tips: &[ObjectId]) -> EvalResult<Vec<ObjectId>> {
720 const NEW: u8 = 1;
721 const OLD: u8 = 2;
722 if new_tips.is_empty() {
723 return Ok(Vec::new());
724 }
725 let mut flags: HashMap<ObjectId, u8> = HashMap::new();
726 let mut heap: BinaryHeap<(u64, ObjectId)> = BinaryHeap::new();
727 let mut queued: HashSet<ObjectId> = HashSet::new();
728 let mut new_only_queued = 0usize;
729
730 let push = |oid: ObjectId,
731 flag: u8,
732 flags: &mut HashMap<ObjectId, u8>,
733 heap: &mut BinaryHeap<(u64, ObjectId)>,
734 queued: &mut HashSet<ObjectId>,
735 new_only: &mut usize|
736 -> EvalResult<()> {
737 let entry = flags.entry(oid).or_insert(0);
738 let before = *entry;
739 *entry |= flag;
740 let after = *entry;
741 if queued.insert(oid) {
742 heap.push((self.commit_info(oid)?.generation, oid));
743 if after == NEW {
744 *new_only = new_only.saturating_add(1);
745 }
746 } else if before == NEW && after != NEW {
747 *new_only = new_only.saturating_sub(1);
748 }
749 Ok(())
750 };
751
752 for &tip in old_tips {
753 push(
754 tip,
755 OLD,
756 &mut flags,
757 &mut heap,
758 &mut queued,
759 &mut new_only_queued,
760 )?;
761 }
762 for &tip in new_tips {
763 push(
764 tip,
765 NEW,
766 &mut flags,
767 &mut heap,
768 &mut queued,
769 &mut new_only_queued,
770 )?;
771 }
772
773 let mut ahead = Vec::new();
774 while let Some((_, oid)) = heap.pop() {
775 // Descending generation order means every commit that could
776 // paint `oid` has already been processed, so its flag is
777 // final here.
778 let flag = flags.get(&oid).copied().unwrap_or(0);
779 queued.remove(&oid);
780 if flag == NEW {
781 new_only_queued = new_only_queued.saturating_sub(1);
782 ahead.push(oid);
783 }
784 for parent in self.commit_info(oid)?.parents.clone() {
785 push(
786 parent,
787 flag,
788 &mut flags,
789 &mut heap,
790 &mut queued,
791 &mut new_only_queued,
792 )?;
793 }
794 if new_only_queued == 0 {
795 // Nothing purely-new remains queued: everything deeper
796 // is reachable from the old tips too, so the frontier
797 // is complete — this is the generation bound.
798 break;
799 }
800 }
801 Ok(ahead)
802 }
803}
804
805/// Whether any short-oid hex prefix in `shorts` prefixes `oid`.
806fn prefix_matches(shorts: &[String], oid: ObjectId) -> bool {
807 let hex = oid.to_string();
808 shorts.iter().any(|short| hex.starts_with(short.as_str()))
809}