OXYGENHUB
# 47ce8b8e2d4b oxygen / crates / oxy-core / src / repo / revset.rs
21.3 KiB · Rust · last changed Revsets: oxy log -r selects changes by set algebra over history 1 month ago source blame history raw
1 
//! Evaluating revsets (docs/revset_query_language.md §4) over a repository.
2 
//!
3 
//! The graph is the change metadata the state index already holds: a
4 
//! symbol loads the closure of the heads it names, and `all()`, `X::`,
5 
//! `dependents()` and `roots()` load every bookmark, remote bookmark, tag
6 
//! and the working copy. Evaluation is read-only and has a time budget;
7 
//! a query past it fails and says what to narrow.
8
9 
use super::*;
10 
use crate::ids::NodeId;
11 
use crate::revset::{self, Expr};
12 
use crate::state::ChangeMeta;
13 
use std::time::{Duration, Instant};
14
15 
type Set = BTreeSet<ChangeHash>;
16
17 
/// The default budget for a command-line evaluation.
18 
pub const REVSET_BUDGET: Duration = Duration::from_secs(10);
19
20 
/// A revset's result with the metadata of every change it names.
21 
#[derive(Clone, Debug)]
22 
pub struct Revset {
23 
    /// Newest first, as a log is ordered.
24 
    pub hashes: Vec<ChangeHash>,
25 
    pub metas: HashMap<ChangeHash, ChangeMeta>,
26 
}
27
28 
struct Eval<'a> {
29 
    repo: &'a Repo,
30 
    graph: HashMap<ChangeHash, ChangeMeta>,
31 
    /// Which heads have had their closure loaded.
32 
    loaded: HashSet<ChangeHash>,
33 
    all_loaded: bool,
34 
    dependents: Option<HashMap<ChangeHash, Vec<ChangeHash>>>,
35 
    names: HashMap<KeyId, Option<(String, String)>>,
36 
    deadline: Instant,
37 
    budget: Duration,
38 
    now_ms: u64,
39 
    depth: usize,
40 
}
41
42 
fn err(msg: impl Into<String>) -> RepoError {
43 
    RepoError::Msg(msg.into())
44 
}
45
46 
impl<'a> Eval<'a> {
47 
    fn tick(&self) -> Result<()> {
48 
        if Instant::now() > self.deadline {
49 
            return Err(err(format!(
50 
                "the revset went past its budget of {:.0} s; narrow it with a range such as main.. or a date()",
51 
                self.budget.as_secs_f64()
52 
            )));
53 
        }
54 
        Ok(())
55 
    }
56
57 
    /// Load the closure of `heads` into the graph.
58 
    fn ensure(&mut self, heads: &[ChangeHash]) -> Result<()> {
59 
        let fresh: Vec<ChangeHash> = heads
60 
            .iter()
61 
            .copied()
62 
            .filter(|h| !self.loaded.contains(h))
63 
            .collect();
64 
        if fresh.is_empty() {
65 
            return Ok(());
66 
        }
67 
        for (h, m) in self.repo.metas_of(&fresh)? {
68 
            self.graph.insert(h, m);
69 
        }
70 
        self.loaded.extend(fresh);
71 
        self.dependents = None;
72 
        self.tick()
73 
    }
74
75 
    /// Load every change the repository names: bookmarks, remote
76 
    /// bookmarks, tags, and the working copy.
77 
    fn load_all(&mut self) -> Result<()> {
78 
        if self.all_loaded {
79 
            return Ok(());
80 
        }
81 
        let view = self.repo.view()?;
82 
        let mut heads: Vec<ChangeHash> = Vec::new();
83 
        for st in view.bookmarks.values() {
84 
            heads.extend(self.repo.store().get_state(st)?.heads);
85 
        }
86 
        for bookmarks in view.remotes.values() {
87 
            for st in bookmarks.values() {
88 
                heads.extend(self.repo.store().get_state(st)?.heads);
89 
            }
90 
        }
91 
        for st in view.tags.values() {
92 
            heads.extend(self.repo.store().get_state(st)?.heads);
93 
        }
94 
        if let Some(wc) = self.working_copy() {
95 
            heads.push(wc);
96 
        }
97 
        heads.sort();
98 
        heads.dedup();
99 
        self.ensure(&heads)?;
100 
        self.all_loaded = true;
101 
        Ok(())
102 
    }
103
104 
    fn working_copy(&self) -> Option<ChangeHash> {
105 
        if self.repo.is_bare() {
106 
            None
107 
        } else {
108 
            self.repo.working_copy().ok().map(|(h, _)| h)
109 
        }
110 
    }
111
112 
    fn all(&mut self) -> Result<Set> {
113 
        self.load_all()?;
114 
        Ok(self.graph.keys().copied().collect())
115 
    }
116
117 
    fn dependents_map(&mut self) -> Result<&HashMap<ChangeHash, Vec<ChangeHash>>> {
118 
        self.load_all()?;
119 
        if self.dependents.is_none() {
120 
            let mut map: HashMap<ChangeHash, Vec<ChangeHash>> = HashMap::new();
121 
            for (h, m) in &self.graph {
122 
                for d in &m.deps {
123 
                    map.entry(*d).or_default().push(*h);
124 
                }
125 
            }
126 
            self.dependents = Some(map);
127 
        }
128 
        Ok(self.dependents.as_ref().unwrap())
129 
    }
130
131 
    /// `::X`: the members and their dependency closures.
132 
    fn ancestors(&mut self, set: &Set) -> Result<Set> {
133 
        let mut out = set.clone();
134 
        let mut stack: Vec<ChangeHash> = set.iter().copied().collect();
135 
        let mut n = 0usize;
136 
        while let Some(h) = stack.pop() {
137 
            if let Some(m) = self.graph.get(&h) {
138 
                for d in &m.deps {
139 
                    if out.insert(*d) {
140 
                        stack.push(*d);
141 
                    }
142 
                }
143 
            }
144 
            n += 1;
145 
            if n.is_multiple_of(4096) {
146 
                self.tick()?;
147 
            }
148 
        }
149 
        Ok(out)
150 
    }
151
152 
    /// `X::`: the members and everything that transitively depends on them.
153 
    fn descendants(&mut self, set: &Set) -> Result<Set> {
154 
        let mut out = set.clone();
155 
        let mut stack: Vec<ChangeHash> = set.iter().copied().collect();
156 
        let deps = self.dependents_map()?;
157 
        while let Some(h) = stack.pop() {
158 
            if let Some(ds) = deps.get(&h) {
159 
                for d in ds {
160 
                    if out.insert(*d) {
161 
                        stack.push(*d);
162 
                    }
163 
                }
164 
            }
165 
        }
166 
        Ok(out)
167 
    }
168
169 
    /// Members no other member depends on, directly or through others.
170 
    fn heads(&mut self, set: &Set) -> Result<Set> {
171 
        let mut below: HashSet<ChangeHash> = HashSet::new();
172 
        let mut stack: Vec<ChangeHash> = set
173 
            .iter()
174 
            .filter_map(|h| self.graph.get(h))
175 
            .flat_map(|m| m.deps.iter().copied())
176 
            .collect();
177 
        while let Some(h) = stack.pop() {
178 
            if below.insert(h) {
179 
                if let Some(m) = self.graph.get(&h) {
180 
                    stack.extend(m.deps.iter().copied());
181 
                }
182 
            }
183 
        }
184 
        Ok(set.iter().copied().filter(|h| !below.contains(h)).collect())
185 
    }
186
187 
    /// Members that depend on no other member, directly or through others.
188 
    fn roots(&mut self, set: &Set) -> Result<Set> {
189 
        let deps = self.dependents_map()?;
190 
        let mut above: HashSet<ChangeHash> = HashSet::new();
191 
        let mut stack: Vec<ChangeHash> = set
192 
            .iter()
193 
            .filter_map(|h| deps.get(h))
194 
            .flat_map(|ds| ds.iter().copied())
195 
            .collect();
196 
        while let Some(h) = stack.pop() {
197 
            if above.insert(h) {
198 
                if let Some(ds) = deps.get(&h) {
199 
                    stack.extend(ds.iter().copied());
200 
                }
201 
            }
202 
        }
203 
        Ok(set.iter().copied().filter(|h| !above.contains(h)).collect())
204 
    }
205
206 
    fn symbol(&mut self, name: &str) -> Result<Set> {
207 
        if name == "@" {
208 
            let Some(wc) = self.working_copy() else {
209 
                return Err(err(
210 
                    "@ names the working copy, and a bare repository has none",
211 
                ));
212 
            };
213 
            self.ensure(&[wc])?;
214 
            return Ok([wc].into_iter().collect());
215 
        }
216 
        let heads = self.repo.resolve_heads(name)?;
217 
        self.ensure(&heads)?;
218 
        Ok(heads.into_iter().collect())
219 
    }
220
221 
    /// The identity's name and email, if its object is known.
222 
    fn who(&mut self, key: &KeyId) -> Option<(String, String)> {
223 
        if let Some(w) = self.names.get(key) {
224 
            return w.clone();
225 
        }
226 
        let w = self.repo.identity(key).ok().map(|id| (id.name, id.email));
227 
        self.names.insert(*key, w.clone());
228 
        w
229 
    }
230
231 
    /// The set a predicate ranges over: what it is intersected with when
232 
    /// that is known, else everything.
233 
    fn universe(&mut self, within: Option<&Set>) -> Result<Set> {
234 
        match within {
235 
            Some(s) => Ok(s.clone()),
236 
            None => self.all(),
237 
        }
238 
    }
239
240 
    fn filter_metas(
241 
        &mut self,
242 
        within: Option<&Set>,
243 
        mut keep: impl FnMut(&ChangeHash, &ChangeMeta) -> bool,
244 
    ) -> Result<Set> {
245 
        let candidates = self.universe(within)?;
246 
        let mut out = Set::new();
247 
        for (i, h) in candidates.iter().enumerate() {
248 
            if let Some(m) = self.graph.get(h) {
249 
                if keep(h, m) {
250 
                    out.insert(*h);
251 
                }
252 
            }
253 
            if i % 8192 == 8191 {
254 
                self.tick()?;
255 
            }
256 
        }
257 
        Ok(out)
258 
    }
259
260 
    /// Changes touching any node whose path matches `glob` in the
261 
    /// evaluation state: the working copy's base, or the bookmark's state
262 
    /// in a bare repository. Nodes keep their identity through renames.
263 
    fn touches(&mut self, within: Option<&Set>, glob: &str) -> Result<Set> {
264 
        let matcher = globset::GlobBuilder::new(glob)
265 
            .literal_separator(false)
266 
            .build()
267 
            .map_err(|e| err(format!("touches({glob:?}): {e}")))?
268 
            .compile_matcher();
269 
        let heads = match self.working_copy() {
270 
            Some(wc) => self
271 
                .graph
272 
                .get(&wc)
273 
                .map(|m| m.deps.clone())
274 
                .or_else(|| self.repo.working_copy().ok().map(|(_, c)| c.deps))
275 
                .unwrap_or_default(),
276 
            None => self.repo.bookmark_heads()?,
277 
        };
278 
        let state = self.repo.load_state(&heads)?;
279 
        let nodes: HashSet<NodeId> = state
280 
            .tree()
281 
            .view()
282 
            .entries
283 
            .iter()
284 
            .filter(|(path, _)| matcher.is_match(path))
285 
            .map(|(_, e)| e.node)
286 
            .collect();
287 
        if nodes.is_empty() {
288 
            return Ok(Set::new());
289 
        }
290 
        let candidates = self.universe(within)?;
291 
        let mut out = Set::new();
292 
        for (i, h) in candidates.iter().enumerate() {
293 
            let Ok(c) = self.repo.store().get_change(h) else {
294 
                continue;
295 
            };
296 
            if c.tree_ops.iter().any(|o| nodes.contains(&o.node()))
297 
                || c.edits.iter().any(|e| nodes.contains(&e.node()))
298 
            {
299 
                out.insert(*h);
300 
            }
301 
            if i % 256 == 255 {
302 
                self.tick()?;
303 
            }
304 
        }
305 
        Ok(out)
306 
    }
307
308 
    fn text_arg<'e>(&self, name: &str, args: &'e [Expr], i: usize) -> Result<&'e str> {
309 
        match args.get(i) {
310 
            Some(Expr::Symbol(s)) => Ok(s),
311 
            _ => Err(err(format!("{name}() takes text, quoted if it has spaces"))),
312 
        }
313 
    }
314
315 
    fn arity(&self, name: &str, args: &[Expr], n: usize) -> Result<()> {
316 
        if args.len() != n {
317 
            return Err(err(format!(
318 
                "{name}() takes {n} argument{}, not {}",
319 
                if n == 1 { "" } else { "s" },
320 
                args.len()
321 
            )));
322 
        }
323 
        Ok(())
324 
    }
325
326 
    fn call(&mut self, name: &str, args: &[Expr], within: Option<&Set>) -> Result<Set> {
327 
        match name {
328 
            "all" => {
329 
                self.arity(name, args, 0)?;
330 
                self.universe(within)
331 
            }
332 
            "none" => {
333 
                self.arity(name, args, 0)?;
334 
                Ok(Set::new())
335 
            }
336 
            "deps" => {
337 
                self.arity(name, args, 1)?;
338 
                let x = self.eval(&args[0], None)?;
339 
                let mut out = Set::new();
340 
                for h in &x {
341 
                    if let Some(m) = self.graph.get(h) {
342 
                        out.extend(m.deps.iter().copied());
343 
                    }
344 
                }
345 
                Ok(out)
346 
            }
347 
            "dependents" => {
348 
                self.arity(name, args, 1)?;
349 
                let x = self.eval(&args[0], None)?;
350 
                let deps = self.dependents_map()?;
351 
                let mut out = Set::new();
352 
                for h in &x {
353 
                    if let Some(ds) = deps.get(h) {
354 
                        out.extend(ds.iter().copied());
355 
                    }
356 
                }
357 
                Ok(out)
358 
            }
359 
            "heads" => {
360 
                self.arity(name, args, 1)?;
361 
                let x = self.eval(&args[0], None)?;
362 
                self.heads(&x)
363 
            }
364 
            "roots" => {
365 
                self.arity(name, args, 1)?;
366 
                let x = self.eval(&args[0], None)?;
367 
                self.roots(&x)
368 
            }
369 
            "latest" => {
370 
                self.arity(name, args, 2)?;
371 
                let x = self.eval(&args[0], None)?;
372 
                let n: usize = self
373 
                    .text_arg(name, args, 1)?
374 
                    .parse()
375 
                    .map_err(|_| err("latest(X, n) takes a count"))?;
376 
                let mut members: Vec<ChangeHash> = x.into_iter().collect();
377 
                self.sort_newest_first(&mut members);
378 
                Ok(members.into_iter().take(n).collect())
379 
            }
380 
            "author" => {
381 
                self.arity(name, args, 1)?;
382 
                let who = self.text_arg(name, args, 0)?.to_string();
383 
                let me = self.repo.config.author_key;
384 
                let needle = who.to_lowercase();
385 
                let mut matches: HashMap<KeyId, bool> = HashMap::new();
386 
                self.filter_metas_with(within, |ev, _, m| {
387 
                    if let Some(hit) = matches.get(&m.author) {
388 
                        return *hit;
389 
                    }
390 
                    let hit = (who == "me" && Some(m.author) == me)
391 
                        || m.author.starts_with_hex(&who)
392 
                        || ev.who(&m.author).is_some_and(|(n, e)| {
393 
                            n.to_lowercase().contains(&needle) || e.to_lowercase().contains(&needle)
394 
                        });
395 
                    matches.insert(m.author, hit);
396 
                    hit
397 
                })
398 
            }
399 
            "description" => {
400 
                self.arity(name, args, 1)?;
401 
                let text = self.text_arg(name, args, 0)?.to_string();
402 
                if text.starts_with("re:") {
403 
                    return Err(err(
404 
                        "description(re:…) is not supported yet; give a substring",
405 
                    ));
406 
                }
407 
                let needle = text.to_lowercase();
408 
                self.filter_metas(within, |_, m| m.message.to_lowercase().contains(&needle))
409 
            }
410 
            "date" => {
411 
                self.arity(name, args, 1)?;
412 
                let range = revset::parse_date_range(self.text_arg(name, args, 0)?, self.now_ms)
413 
                    .map_err(err)?;
414 
                self.filter_metas(within, |_, m| range.contains(m.hlc.wall_ms))
415 
            }
416 
            "kind" => {
417 
                self.arity(name, args, 1)?;
418 
                let kind = match self.text_arg(name, args, 0)? {
419 
                    "normal" => ChangeKind::Normal,
420 
                    "resolution" => ChangeKind::Resolution,
421 
                    "working-copy" | "working_copy" => ChangeKind::WorkingCopy,
422 
                    other => {
423 
                        return Err(err(format!(
424 
                            "kind({other:?}): use normal, resolution or working-copy"
425 
                        )))
426 
                    }
427 
                };
428 
                self.filter_metas(within, |_, m| m.kind == kind)
429 
            }
430 
            "touches" => {
431 
                self.arity(name, args, 1)?;
432 
                let glob = self.text_arg(name, args, 0)?.to_string();
433 
                self.touches(within, &glob)
434 
            }
435 
            other => {
436 
                // A saved revset: `oxy config revset.NAME 'EXPR'` makes NAME().
437 
                if let Some(saved) = self.repo.config.revsets.get(other).cloned() {
438 
                    self.arity(name, args, 0)?;
439 
                    if self.depth >= 16 {
440 
                        return Err(err(format!("revset.{other} refers to itself")));
441 
                    }
442 
                    let e = revset::parse(&saved)
443 
                        .map_err(|e| err(format!("revset.{other} = {saved:?}: {e}")))?;
444 
                    self.depth += 1;
445 
                    let r = self.eval(&e, within);
446 
                    self.depth -= 1;
447 
                    return r;
448 
                }
449 
                Err(err(format!(
450 
                    "unknown function {other}(); see docs/revset_query_language.md"
451 
                )))
452 
            }
453 
        }
454 
    }
455
456 
    /// `filter_metas` for a test that needs the evaluator (identity lookups).
457 
    fn filter_metas_with(
458 
        &mut self,
459 
        within: Option<&Set>,
460 
        mut keep: impl FnMut(&mut Eval<'a>, &ChangeHash, &ChangeMeta) -> bool,
461 
    ) -> Result<Set> {
462 
        let candidates = self.universe(within)?;
463 
        let mut out = Set::new();
464 
        for (i, h) in candidates.iter().enumerate() {
465 
            if let Some(m) = self.graph.get(h).cloned() {
466 
                if keep(self, h, &m) {
467 
                    out.insert(*h);
468 
                }
469 
            }
470 
            if i % 8192 == 8191 {
471 
                self.tick()?;
472 
            }
473 
        }
474 
        Ok(out)
475 
    }
476
477 
    /// Whether an expression selects by a property, so that evaluating it
478 
    /// within the other side of an intersection saves scanning everything.
479 
    fn is_predicate(e: &Expr) -> bool {
480 
        match e {
481 
            Expr::Call(name, _) => matches!(
482 
                name.as_str(),
483 
                "author" | "description" | "date" | "kind" | "touches" | "all"
484 
            ),
485 
            Expr::Intersection(a, b) => Self::is_predicate(a) || Self::is_predicate(b),
486 
            Expr::Union(a, b) => Self::is_predicate(a) && Self::is_predicate(b),
487 
            Expr::Difference(a, _) => Self::is_predicate(a),
488 
            _ => false,
489 
        }
490 
    }
491
492 
    fn eval(&mut self, e: &Expr, within: Option<&Set>) -> Result<Set> {
493 
        self.tick()?;
494 
        match e {
495 
            Expr::Symbol(s) => self.symbol(s),
496 
            Expr::Ancestors(x) => {
497 
                let x = self.eval(x, None)?;
498 
                self.ancestors(&x)
499 
            }
500 
            Expr::Descendants(x) => {
501 
                let x = self.eval(x, None)?;
502 
                self.descendants(&x)
503 
            }
504 
            Expr::Between(x, y) => {
505 
                let x = self.eval(x, None)?;
506 
                let y = self.eval(y, None)?;
507 
                let down = self.descendants(&x)?;
508 
                let up = self.ancestors(&y)?;
509 
                Ok(down.intersection(&up).copied().collect())
510 
            }
511 
            Expr::Range(x, y) => {
512 
                let x = self.eval(x, None)?;
513 
                let y = self.eval(y, None)?;
514 
                let from = self.ancestors(&x)?;
515 
                let to = self.ancestors(&y)?;
516 
                Ok(to.difference(&from).copied().collect())
517 
            }
518 
            Expr::Union(a, b) => {
519 
                let mut a = self.eval(a, within)?;
520 
                a.extend(self.eval(b, within)?);
521 
                Ok(a)
522 
            }
523 
            Expr::Intersection(a, b) => {
524 
                let (first, second) = if Self::is_predicate(a) && !Self::is_predicate(b) {
525 
                    (b, a)
526 
                } else {
527 
                    (a, b)
528 
                };
529 
                let left = self.eval(first, within)?;
530 
                let right = self.eval(second, Some(&left))?;
531 
                Ok(left.intersection(&right).copied().collect())
532 
            }
533 
            Expr::Difference(a, b) => {
534 
                let left = self.eval(a, within)?;
535 
                let right = self.eval(b, Some(&left))?;
536 
                Ok(left.difference(&right).copied().collect())
537 
            }
538 
            Expr::Call(name, args) => self.call(name, args, within),
539 
        }
540 
    }
541
542 
    fn sort_newest_first(&self, hashes: &mut [ChangeHash]) {
543 
        hashes.sort_by(|a, b| {
544 
            let (ma, mb) = (self.graph.get(a), self.graph.get(b));
545 
            mb.map(|m| m.hlc).cmp(&ma.map(|m| m.hlc)).then(b.cmp(a))
546 
        });
547 
    }
548 
}
549
550 
impl Repo {
551 
    /// Evaluate a revset within [`REVSET_BUDGET`].
552 
    pub fn revset(&self, src: &str) -> Result<Revset> {
553 
        self.revset_with_budget(src, REVSET_BUDGET)
554 
    }
555
556 
    /// Evaluate a revset: the changes it selects, newest first, with
557 
    /// their metadata. Read-only. Fails past `budget`.
558 
    pub fn revset_with_budget(&self, src: &str, budget: Duration) -> Result<Revset> {
559 
        let expr = revset::parse(src).map_err(|e| err(format!("revset {src:?}: {e}")))?;
560 
        let mut ev = Eval {
561 
            repo: self,
562 
            graph: HashMap::new(),
563 
            loaded: HashSet::new(),
564 
            all_loaded: false,
565 
            dependents: None,
566 
            names: HashMap::new(),
567 
            deadline: Instant::now() + budget,
568 
            budget,
569 
            now_ms: Hlc::now().wall_ms,
570 
            depth: 0,
571 
        };
572 
        let set = ev.eval(&expr, None)?;
573 
        let mut hashes: Vec<ChangeHash> = set.into_iter().collect();
574 
        ev.sort_newest_first(&mut hashes);
575 
        let metas = hashes
576 
            .iter()
577 
            .filter_map(|h| ev.graph.get(h).map(|m| (*h, m.clone())))
578 
            .collect();
579 
        Ok(Revset { hashes, metas })
580 
    }
581
582 
    /// The log entries a revset selects, newest first. A head of the
583 
    /// current bookmark is marked as in `log`.
584 
    pub fn log_revset(&self, src: &str) -> Result<Vec<LogEntry>> {
585 
        let r = self.revset(src)?;
586 
        let heads: BTreeSet<ChangeHash> = self.bookmark_heads()?.into_iter().collect();
587 
        let wc = if self.is_bare() {
588 
            None
589 
        } else {
590 
            self.working_copy().ok().map(|(h, _)| h)
591 
        };
592 
        let mut entries: Vec<LogEntry> = r
593 
            .hashes
594 
            .iter()
595 
            .filter_map(|h| {
596 
                r.metas.get(h).map(|m| LogEntry {
597 
                    hash: *h,
598 
                    change: m.clone(),
599 
                    is_working_copy: Some(*h) == wc,
600 
                    is_head: heads.contains(h),
601 
                })
602 
            })
603 
            .collect();
604 
        // The working copy first, as `log` shows it.
605 
        entries.sort_by_key(|e| !e.is_working_copy);
606 
        Ok(entries)
607 
    }
608 
}