Revsets: oxy log -r selects changes by set algebra over history 47ce8b8e2d4b

//! Evaluating revsets (docs/revset_query_language.md §4) over a repository.

//!

//! The graph is the change metadata the state index already holds: a

//! symbol loads the closure of the heads it names, and `all()`, `X::`,

//! `dependents()` and `roots()` load every bookmark, remote bookmark, tag

//! and the working copy. Evaluation is read-only and has a time budget;

//! a query past it fails and says what to narrow.

use super::*;

use crate::ids::NodeId;

use crate::revset::{self, Expr};

use crate::state::ChangeMeta;

use std::time::{Duration, Instant};

type Set = BTreeSet<ChangeHash>;

/// The default budget for a command-line evaluation.

pub const REVSET_BUDGET: Duration = Duration::from_secs(10);

/// A revset's result with the metadata of every change it names.

#[derive(Clone, Debug)]

pub struct Revset {

    /// Newest first, as a log is ordered.

    pub hashes: Vec<ChangeHash>,

    pub metas: HashMap<ChangeHash, ChangeMeta>,

}

struct Eval<'a> {

    repo: &'a Repo,

    graph: HashMap<ChangeHash, ChangeMeta>,

    /// Which heads have had their closure loaded.

    loaded: HashSet<ChangeHash>,

    all_loaded: bool,

    dependents: Option<HashMap<ChangeHash, Vec<ChangeHash>>>,

    names: HashMap<KeyId, Option<(String, String)>>,

    deadline: Instant,

    budget: Duration,

    now_ms: u64,

    depth: usize,

}

fn err(msg: impl Into<String>) -> RepoError {

    RepoError::Msg(msg.into())

}

impl<'a> Eval<'a> {

    fn tick(&self) -> Result<()> {

        if Instant::now() > self.deadline {

            return Err(err(format!(

                "the revset went past its budget of {:.0} s; narrow it with a range such as main.. or a date()",

                self.budget.as_secs_f64()

            )));

        }

        Ok(())

    }

    /// Load the closure of `heads` into the graph.

    fn ensure(&mut self, heads: &[ChangeHash]) -> Result<()> {

        let fresh: Vec<ChangeHash> = heads

            .iter()

            .copied()

            .filter(|h| !self.loaded.contains(h))

            .collect();

        if fresh.is_empty() {

            return Ok(());

        }

        for (h, m) in self.repo.metas_of(&fresh)? {

            self.graph.insert(h, m);

        }

        self.loaded.extend(fresh);

        self.dependents = None;

        self.tick()

    }

    /// Load every change the repository names: bookmarks, remote

    /// bookmarks, tags, and the working copy.

    fn load_all(&mut self) -> Result<()> {

        if self.all_loaded {

            return Ok(());

        }

        let view = self.repo.view()?;

        let mut heads: Vec<ChangeHash> = Vec::new();

        for st in view.bookmarks.values() {

            heads.extend(self.repo.store().get_state(st)?.heads);

        }

        for bookmarks in view.remotes.values() {

            for st in bookmarks.values() {

                heads.extend(self.repo.store().get_state(st)?.heads);

            }

        }

        for st in view.tags.values() {

            heads.extend(self.repo.store().get_state(st)?.heads);

        }

        if let Some(wc) = self.working_copy() {

            heads.push(wc);

        }

        heads.sort();

        heads.dedup();

        self.ensure(&heads)?;

        self.all_loaded = true;

        Ok(())

    }

    fn working_copy(&self) -> Option<ChangeHash> {

        if self.repo.is_bare() {

            None

        } else {

            self.repo.working_copy().ok().map(|(h, _)| h)

        }

    }

    fn all(&mut self) -> Result<Set> {

        self.load_all()?;

        Ok(self.graph.keys().copied().collect())

    }

    fn dependents_map(&mut self) -> Result<&HashMap<ChangeHash, Vec<ChangeHash>>> {

        self.load_all()?;

        if self.dependents.is_none() {

            let mut map: HashMap<ChangeHash, Vec<ChangeHash>> = HashMap::new();

            for (h, m) in &self.graph {

                for d in &m.deps {

                    map.entry(*d).or_default().push(*h);

                }

            }

            self.dependents = Some(map);

        }

        Ok(self.dependents.as_ref().unwrap())

    }

    /// `::X`: the members and their dependency closures.

    fn ancestors(&mut self, set: &Set) -> Result<Set> {

        let mut out = set.clone();

        let mut stack: Vec<ChangeHash> = set.iter().copied().collect();

        let mut n = 0usize;

        while let Some(h) = stack.pop() {

            if let Some(m) = self.graph.get(&h) {

                for d in &m.deps {

                    if out.insert(*d) {

                        stack.push(*d);

                    }

                }

            }

            n += 1;

            if n.is_multiple_of(4096) {

                self.tick()?;

            }

        }

        Ok(out)

    }

    /// `X::`: the members and everything that transitively depends on them.

    fn descendants(&mut self, set: &Set) -> Result<Set> {

        let mut out = set.clone();

        let mut stack: Vec<ChangeHash> = set.iter().copied().collect();

        let deps = self.dependents_map()?;

        while let Some(h) = stack.pop() {

            if let Some(ds) = deps.get(&h) {

                for d in ds {

                    if out.insert(*d) {

                        stack.push(*d);

                    }

                }

            }

        }

        Ok(out)

    }

    /// Members no other member depends on, directly or through others.

    fn heads(&mut self, set: &Set) -> Result<Set> {

        let mut below: HashSet<ChangeHash> = HashSet::new();

        let mut stack: Vec<ChangeHash> = set

            .iter()

            .filter_map(|h| self.graph.get(h))

            .flat_map(|m| m.deps.iter().copied())

            .collect();

        while let Some(h) = stack.pop() {

            if below.insert(h) {

                if let Some(m) = self.graph.get(&h) {

                    stack.extend(m.deps.iter().copied());

                }

            }

        }

        Ok(set.iter().copied().filter(|h| !below.contains(h)).collect())

    }

    /// Members that depend on no other member, directly or through others.

    fn roots(&mut self, set: &Set) -> Result<Set> {

        let deps = self.dependents_map()?;

        let mut above: HashSet<ChangeHash> = HashSet::new();

        let mut stack: Vec<ChangeHash> = set

            .iter()

            .filter_map(|h| deps.get(h))

            .flat_map(|ds| ds.iter().copied())

            .collect();

        while let Some(h) = stack.pop() {

            if above.insert(h) {

                if let Some(ds) = deps.get(&h) {

                    stack.extend(ds.iter().copied());

                }

            }

        }

        Ok(set.iter().copied().filter(|h| !above.contains(h)).collect())

    }

    fn symbol(&mut self, name: &str) -> Result<Set> {

        if name == "@" {

            let Some(wc) = self.working_copy() else {

                return Err(err(

                    "@ names the working copy, and a bare repository has none",

                ));

            };

            self.ensure(&[wc])?;

            return Ok([wc].into_iter().collect());

        }

        let heads = self.repo.resolve_heads(name)?;

        self.ensure(&heads)?;

        Ok(heads.into_iter().collect())

    }

    /// The identity's name and email, if its object is known.

    fn who(&mut self, key: &KeyId) -> Option<(String, String)> {

        if let Some(w) = self.names.get(key) {

            return w.clone();

        }

        let w = self.repo.identity(key).ok().map(|id| (id.name, id.email));

        self.names.insert(*key, w.clone());

        w

    }

    /// The set a predicate ranges over: what it is intersected with when

    /// that is known, else everything.

    fn universe(&mut self, within: Option<&Set>) -> Result<Set> {

        match within {

            Some(s) => Ok(s.clone()),

            None => self.all(),

        }

    }

    fn filter_metas(

        &mut self,

        within: Option<&Set>,

        mut keep: impl FnMut(&ChangeHash, &ChangeMeta) -> bool,

    ) -> Result<Set> {

        let candidates = self.universe(within)?;

        let mut out = Set::new();

        for (i, h) in candidates.iter().enumerate() {

            if let Some(m) = self.graph.get(h) {

                if keep(h, m) {

                    out.insert(*h);

                }

            }

            if i % 8192 == 8191 {

                self.tick()?;

            }

        }

        Ok(out)

    }

    /// Changes touching any node whose path matches `glob` in the

    /// evaluation state: the working copy's base, or the bookmark's state

    /// in a bare repository. Nodes keep their identity through renames.

    fn touches(&mut self, within: Option<&Set>, glob: &str) -> Result<Set> {

        let matcher = globset::GlobBuilder::new(glob)

            .literal_separator(false)

            .build()

            .map_err(|e| err(format!("touches({glob:?}): {e}")))?

            .compile_matcher();

        let heads = match self.working_copy() {

            Some(wc) => self

                .graph

                .get(&wc)

                .map(|m| m.deps.clone())

                .or_else(|| self.repo.working_copy().ok().map(|(_, c)| c.deps))

                .unwrap_or_default(),

            None => self.repo.bookmark_heads()?,

        };

        let state = self.repo.load_state(&heads)?;

        let nodes: HashSet<NodeId> = state

            .tree()

            .view()

            .entries

            .iter()

            .filter(|(path, _)| matcher.is_match(path))

            .map(|(_, e)| e.node)

            .collect();

        if nodes.is_empty() {

            return Ok(Set::new());

        }

        let candidates = self.universe(within)?;

        let mut out = Set::new();

        for (i, h) in candidates.iter().enumerate() {

            let Ok(c) = self.repo.store().get_change(h) else {

                continue;

            };

            if c.tree_ops.iter().any(|o| nodes.contains(&o.node()))

                || c.edits.iter().any(|e| nodes.contains(&e.node()))

            {

                out.insert(*h);

            }

            if i % 256 == 255 {

                self.tick()?;

            }

        }

        Ok(out)

    }

    fn text_arg<'e>(&self, name: &str, args: &'e [Expr], i: usize) -> Result<&'e str> {

        match args.get(i) {

            Some(Expr::Symbol(s)) => Ok(s),

            _ => Err(err(format!("{name}() takes text, quoted if it has spaces"))),

        }

    }

    fn arity(&self, name: &str, args: &[Expr], n: usize) -> Result<()> {

        if args.len() != n {

            return Err(err(format!(

                "{name}() takes {n} argument{}, not {}",

                if n == 1 { "" } else { "s" },

                args.len()

            )));

        }

        Ok(())

    }

    fn call(&mut self, name: &str, args: &[Expr], within: Option<&Set>) -> Result<Set> {

        match name {

            "all" => {

                self.arity(name, args, 0)?;

                self.universe(within)

            }

            "none" => {

                self.arity(name, args, 0)?;

                Ok(Set::new())

            }

            "deps" => {

                self.arity(name, args, 1)?;

                let x = self.eval(&args[0], None)?;

                let mut out = Set::new();

                for h in &x {

                    if let Some(m) = self.graph.get(h) {

                        out.extend(m.deps.iter().copied());

                    }

                }

                Ok(out)

            }

            "dependents" => {

                self.arity(name, args, 1)?;

                let x = self.eval(&args[0], None)?;

                let deps = self.dependents_map()?;

                let mut out = Set::new();

                for h in &x {

                    if let Some(ds) = deps.get(h) {

                        out.extend(ds.iter().copied());

                    }

                }

                Ok(out)

            }

            "heads" => {

                self.arity(name, args, 1)?;

                let x = self.eval(&args[0], None)?;

                self.heads(&x)

            }

            "roots" => {

                self.arity(name, args, 1)?;

                let x = self.eval(&args[0], None)?;

                self.roots(&x)

            }

            "latest" => {

                self.arity(name, args, 2)?;

                let x = self.eval(&args[0], None)?;

                let n: usize = self

                    .text_arg(name, args, 1)?

                    .parse()

                    .map_err(|_| err("latest(X, n) takes a count"))?;

                let mut members: Vec<ChangeHash> = x.into_iter().collect();

                self.sort_newest_first(&mut members);

                Ok(members.into_iter().take(n).collect())

            }

            "author" => {

                self.arity(name, args, 1)?;

                let who = self.text_arg(name, args, 0)?.to_string();

                let me = self.repo.config.author_key;

                let needle = who.to_lowercase();

                let mut matches: HashMap<KeyId, bool> = HashMap::new();

                self.filter_metas_with(within, |ev, _, m| {

                    if let Some(hit) = matches.get(&m.author) {

                        return *hit;

                    }

                    let hit = (who == "me" && Some(m.author) == me)

                        || m.author.starts_with_hex(&who)

                        || ev.who(&m.author).is_some_and(|(n, e)| {

                            n.to_lowercase().contains(&needle) || e.to_lowercase().contains(&needle)

                        });

                    matches.insert(m.author, hit);

                    hit

                })

            }

            "description" => {

                self.arity(name, args, 1)?;

                let text = self.text_arg(name, args, 0)?.to_string();

                if text.starts_with("re:") {

                    return Err(err(

                        "description(re:…) is not supported yet; give a substring",

                    ));

                }

                let needle = text.to_lowercase();

                self.filter_metas(within, |_, m| m.message.to_lowercase().contains(&needle))

            }

            "date" => {

                self.arity(name, args, 1)?;

                let range = revset::parse_date_range(self.text_arg(name, args, 0)?, self.now_ms)

                    .map_err(err)?;

                self.filter_metas(within, |_, m| range.contains(m.hlc.wall_ms))

            }

            "kind" => {

                self.arity(name, args, 1)?;

                let kind = match self.text_arg(name, args, 0)? {

                    "normal" => ChangeKind::Normal,

                    "resolution" => ChangeKind::Resolution,

                    "working-copy" | "working_copy" => ChangeKind::WorkingCopy,

                    other => {

                        return Err(err(format!(

                            "kind({other:?}): use normal, resolution or working-copy"

                        )))

                    }

                };

                self.filter_metas(within, |_, m| m.kind == kind)

            }

            "touches" => {

                self.arity(name, args, 1)?;

                let glob = self.text_arg(name, args, 0)?.to_string();

                self.touches(within, &glob)

            }

            other => {

                // A saved revset: `oxy config revset.NAME 'EXPR'` makes NAME().

                if let Some(saved) = self.repo.config.revsets.get(other).cloned() {

                    self.arity(name, args, 0)?;

                    if self.depth >= 16 {

                        return Err(err(format!("revset.{other} refers to itself")));

                    }

                    let e = revset::parse(&saved)

                        .map_err(|e| err(format!("revset.{other} = {saved:?}: {e}")))?;

                    self.depth += 1;

                    let r = self.eval(&e, within);

                    self.depth -= 1;

                    return r;

                }

                Err(err(format!(

                    "unknown function {other}(); see docs/revset_query_language.md"

                )))

            }

        }

    }

    /// `filter_metas` for a test that needs the evaluator (identity lookups).

    fn filter_metas_with(

        &mut self,

        within: Option<&Set>,

        mut keep: impl FnMut(&mut Eval<'a>, &ChangeHash, &ChangeMeta) -> bool,

    ) -> Result<Set> {

        let candidates = self.universe(within)?;

        let mut out = Set::new();

        for (i, h) in candidates.iter().enumerate() {

            if let Some(m) = self.graph.get(h).cloned() {

                if keep(self, h, &m) {

                    out.insert(*h);

                }

            }

            if i % 8192 == 8191 {

                self.tick()?;

            }

        }

        Ok(out)

    }

    /// Whether an expression selects by a property, so that evaluating it

    /// within the other side of an intersection saves scanning everything.

    fn is_predicate(e: &Expr) -> bool {

        match e {

            Expr::Call(name, _) => matches!(

                name.as_str(),

                "author" | "description" | "date" | "kind" | "touches" | "all"

            ),

            Expr::Intersection(a, b) => Self::is_predicate(a) || Self::is_predicate(b),

            Expr::Union(a, b) => Self::is_predicate(a) && Self::is_predicate(b),

            Expr::Difference(a, _) => Self::is_predicate(a),

            _ => false,

        }

    }

    fn eval(&mut self, e: &Expr, within: Option<&Set>) -> Result<Set> {

        self.tick()?;

        match e {

            Expr::Symbol(s) => self.symbol(s),

            Expr::Ancestors(x) => {

                let x = self.eval(x, None)?;

                self.ancestors(&x)

            }

            Expr::Descendants(x) => {

                let x = self.eval(x, None)?;

                self.descendants(&x)

            }

            Expr::Between(x, y) => {

                let x = self.eval(x, None)?;

                let y = self.eval(y, None)?;

                let down = self.descendants(&x)?;

                let up = self.ancestors(&y)?;

                Ok(down.intersection(&up).copied().collect())

            }

            Expr::Range(x, y) => {

                let x = self.eval(x, None)?;

                let y = self.eval(y, None)?;

                let from = self.ancestors(&x)?;

                let to = self.ancestors(&y)?;

                Ok(to.difference(&from).copied().collect())

            }

            Expr::Union(a, b) => {

                let mut a = self.eval(a, within)?;

                a.extend(self.eval(b, within)?);

                Ok(a)

            }

            Expr::Intersection(a, b) => {

                let (first, second) = if Self::is_predicate(a) && !Self::is_predicate(b) {

                    (b, a)

                } else {

                    (a, b)

                };

                let left = self.eval(first, within)?;

                let right = self.eval(second, Some(&left))?;

                Ok(left.intersection(&right).copied().collect())

            }

            Expr::Difference(a, b) => {

                let left = self.eval(a, within)?;

                let right = self.eval(b, Some(&left))?;

                Ok(left.difference(&right).copied().collect())

            }

            Expr::Call(name, args) => self.call(name, args, within),

        }

    }

    fn sort_newest_first(&self, hashes: &mut [ChangeHash]) {

        hashes.sort_by(|a, b| {

            let (ma, mb) = (self.graph.get(a), self.graph.get(b));

            mb.map(|m| m.hlc).cmp(&ma.map(|m| m.hlc)).then(b.cmp(a))

        });

    }

}

impl Repo {

    /// Evaluate a revset within [`REVSET_BUDGET`].

    pub fn revset(&self, src: &str) -> Result<Revset> {

        self.revset_with_budget(src, REVSET_BUDGET)

    }

    /// Evaluate a revset: the changes it selects, newest first, with

    /// their metadata. Read-only. Fails past `budget`.

    pub fn revset_with_budget(&self, src: &str, budget: Duration) -> Result<Revset> {

        let expr = revset::parse(src).map_err(|e| err(format!("revset {src:?}: {e}")))?;

        let mut ev = Eval {

            repo: self,

            graph: HashMap::new(),

            loaded: HashSet::new(),

            all_loaded: false,

            dependents: None,

            names: HashMap::new(),

            deadline: Instant::now() + budget,

            budget,

            now_ms: Hlc::now().wall_ms,

            depth: 0,

        };

        let set = ev.eval(&expr, None)?;

        let mut hashes: Vec<ChangeHash> = set.into_iter().collect();

        ev.sort_newest_first(&mut hashes);

        let metas = hashes

            .iter()

            .filter_map(|h| ev.graph.get(h).map(|m| (*h, m.clone())))

            .collect();

        Ok(Revset { hashes, metas })

    }

    /// The log entries a revset selects, newest first. A head of the

    /// current bookmark is marked as in `log`.

    pub fn log_revset(&self, src: &str) -> Result<Vec<LogEntry>> {

        let r = self.revset(src)?;

        let heads: BTreeSet<ChangeHash> = self.bookmark_heads()?.into_iter().collect();

        let wc = if self.is_bare() {

            None

        } else {

            self.working_copy().ok().map(|(h, _)| h)

        };

        let mut entries: Vec<LogEntry> = r

            .hashes

            .iter()

            .filter_map(|h| {

                r.metas.get(h).map(|m| LogEntry {

                    hash: *h,

                    change: m.clone(),

                    is_working_copy: Some(*h) == wc,

                    is_head: heads.contains(h),

                })

            })

            .collect();

        // The working copy first, as `log` shows it.

        entries.sort_by_key(|e| !e.is_working_copy);

        Ok(entries)

    }

}

//! Revsets: expressions that select a set of changes (docs/revset_query_language.md).

//!

//! This module parses the language; [`crate::repo::Repo::revset`] evaluates

//! it over a repository. Grammar, from loosest to tightest:

//!

//! ```text

//! union      = inter ('|' inter)*

//! inter      = diff ('&' diff)*

//! diff       = range ('~' range)*            -- set difference, as in Jujutsu

//! range      = '::' primary | primary '::' primary? | primary '..' primary? | '..' primary | primary

//! primary    = '(' union ')' | name '(' args ')' | symbol | string

//! ```

//!

//! A symbol is a bookmark, `REMOTE/NAME`, a tag, a ChangeId prefix, a

//! `#hash` prefix or `@`; a quoted string is a function argument.

use std::fmt;

#[derive(Clone, Debug, PartialEq, Eq)]

pub enum Expr {

    /// A bookmark, tag, change prefix or `@`: the heads it names.

    Symbol(String),

    /// `::X`: X and its dependency closure.

    Ancestors(Box<Expr>),

    /// `X::`: X and everything depending on it.

    Descendants(Box<Expr>),

    /// `X::Y`: in both `X::` and `::Y`.

    Between(Box<Expr>, Box<Expr>),

    /// `X..Y`: `::Y ~ ::X`.

    Range(Box<Expr>, Box<Expr>),

    Union(Box<Expr>, Box<Expr>),

    Intersection(Box<Expr>, Box<Expr>),

    Difference(Box<Expr>, Box<Expr>),

    /// `name(args)`; a string argument is an `Expr::Symbol` holding its text.

    Call(String, Vec<Expr>),

}

impl fmt::Display for Expr {

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {

        match self {

            Expr::Symbol(s) => {

                if s.is_empty() || s.chars().any(|c| !is_symbol_char(c)) {

                    write!(f, "{s:?}")

                } else {

                    f.write_str(s)

                }

            }

            Expr::Ancestors(x) => write!(f, "::{x}"),

            Expr::Descendants(x) => write!(f, "{x}::"),

            Expr::Between(x, y) => write!(f, "{x}::{y}"),

            Expr::Range(x, y) => write!(f, "{x}..{y}"),

            Expr::Union(x, y) => write!(f, "({x} | {y})"),

            Expr::Intersection(x, y) => write!(f, "({x} & {y})"),

            Expr::Difference(x, y) => write!(f, "({x} ~ {y})"),

            Expr::Call(name, args) => {

                write!(f, "{name}(")?;

                for (i, a) in args.iter().enumerate() {

                    if i > 0 {

                        f.write_str(", ")?;

                    }

                    write!(f, "{a}")?;

                }

                f.write_str(")")

            }

        }

    }

}

#[derive(Clone, Debug, PartialEq, Eq)]

pub struct ParseError {

    pub at: usize,

    pub message: String,

}

impl fmt::Display for ParseError {

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {

        write!(f, "{} (at character {})", self.message, self.at + 1)

    }

}

impl std::error::Error for ParseError {}

#[derive(Clone, Debug, PartialEq, Eq)]

enum Tok {

    Symbol(String),

    Str(String),

    ColonColon,

    DotDot,

    Tilde,

    Amp,

    Pipe,

    LParen,

    RParen,

    Comma,

}

fn is_symbol_char(c: char) -> bool {

    c.is_alphanumeric() || matches!(c, '_' | '.' | '/' | '@' | '#' | '-' | '+')

}

fn lex(src: &str) -> Result<Vec<(usize, Tok)>, ParseError> {

    let mut out = Vec::new();

    let chars: Vec<(usize, char)> = src.char_indices().collect();

    let mut i = 0;

    while i < chars.len() {

        let (at, c) = chars[i];

        match c {

            c if c.is_whitespace() => i += 1,

            ':' => {

                if chars.get(i + 1).map(|x| x.1) == Some(':') {

                    out.push((at, Tok::ColonColon));

                    i += 2;

                } else {

                    return Err(ParseError {

                        at,

                        message: "expected `::`".into(),

                    });

                }

            }

            '.' if chars.get(i + 1).map(|x| x.1) == Some('.') => {

                out.push((at, Tok::DotDot));

                i += 2;

            }

            '~' => {

                out.push((at, Tok::Tilde));

                i += 1;

            }

            '&' => {

                out.push((at, Tok::Amp));

                i += 1;

            }

            '|' => {

                out.push((at, Tok::Pipe));

                i += 1;

            }

            '(' => {

                out.push((at, Tok::LParen));

                i += 1;

            }

            ')' => {

                out.push((at, Tok::RParen));

                i += 1;

            }

            ',' => {

                out.push((at, Tok::Comma));

                i += 1;

            }

            '"' | '\'' => {

                let quote = c;

                let mut s = String::new();

                let mut j = i + 1;

                loop {

                    match chars.get(j) {

                        None => {

                            return Err(ParseError {

                                at,

                                message: "unterminated string".into(),

                            })

                        }

                        Some((_, ch)) if *ch == quote => break,

                        Some((_, '\\')) => {

                            if let Some((_, next)) = chars.get(j + 1) {

                                s.push(*next);

                                j += 2;

                            } else {

                                j += 1;

                            }

                        }

                        Some((_, ch)) => {

                            s.push(*ch);

                            j += 1;

                        }

                    }

                }

                out.push((at, Tok::Str(s)));

                i = j + 1;

            }

            c if is_symbol_char(c) => {

                let mut s = String::new();

                let mut j = i;

                // `..` ends a symbol: `main..feature`.

                while let Some((_, ch)) = chars.get(j) {

                    if !is_symbol_char(*ch) {

                        break;

                    }

                    if *ch == '.' && chars.get(j + 1).map(|x| x.1) == Some('.') {

                        break;

                    }

                    s.push(*ch);

                    j += 1;

                }

                out.push((at, Tok::Symbol(s)));

                i = j;

            }

            other => {

                return Err(ParseError {

                    at,

                    message: format!("unexpected character {other:?}"),

                })

            }

        }

    }

    Ok(out)

}

struct Parser {

    src: String,

    toks: Vec<(usize, Tok)>,

    pos: usize,

    end: usize,

}

/// Functions whose argument is taken as written, not parsed: a date range

/// such as `-7d..` would otherwise read as a revset range.

const RAW_ARGS: [&str; 1] = ["date"];

impl Parser {

    fn peek(&self) -> Option<&Tok> {

        self.toks.get(self.pos).map(|t| &t.1)

    }

    fn at(&self) -> usize {

        self.toks.get(self.pos).map(|t| t.0).unwrap_or(self.end)

    }

    fn eat(&mut self, t: &Tok) -> bool {

        if self.peek() == Some(t) {

            self.pos += 1;

            true

        } else {

            false

        }

    }

    fn err<T>(&self, message: impl Into<String>) -> Result<T, ParseError> {

        Err(ParseError {

            at: self.at(),

            message: message.into(),

        })

    }

    fn union(&mut self) -> Result<Expr, ParseError> {

        let mut left = self.inter()?;

        while self.eat(&Tok::Pipe) {

            let right = self.inter()?;

            left = Expr::Union(Box::new(left), Box::new(right));

        }

        Ok(left)

    }

    fn inter(&mut self) -> Result<Expr, ParseError> {

        let mut left = self.diff()?;

        while self.eat(&Tok::Amp) {

            let right = self.diff()?;

            left = Expr::Intersection(Box::new(left), Box::new(right));

        }

        Ok(left)

    }

    fn diff(&mut self) -> Result<Expr, ParseError> {

        let mut left = self.range()?;

        while self.eat(&Tok::Tilde) {

            let right = self.range()?;

            left = Expr::Difference(Box::new(left), Box::new(right));

        }

        Ok(left)

    }

    /// Whether the next token starts a primary expression.

    fn starts_primary(&self) -> bool {

        matches!(

            self.peek(),

            Some(Tok::Symbol(_) | Tok::Str(_) | Tok::LParen)

        )

    }

    fn range(&mut self) -> Result<Expr, ParseError> {

        if self.eat(&Tok::ColonColon) {

            let x = self.primary()?;

            return Ok(Expr::Ancestors(Box::new(x)));

        }

        if self.eat(&Tok::DotDot) {

            let y = self.primary()?;

            return Ok(Expr::Ancestors(Box::new(y)));

        }

        let x = self.primary()?;

        if self.eat(&Tok::ColonColon) {

            if self.starts_primary() {

                let y = self.primary()?;

                return Ok(Expr::Between(Box::new(x), Box::new(y)));

            }

            return Ok(Expr::Descendants(Box::new(x)));

        }

        if self.eat(&Tok::DotDot) {

            if self.starts_primary() {

                let y = self.primary()?;

                return Ok(Expr::Range(Box::new(x), Box::new(y)));

            }

            // `X..`: what the repository has beyond X.

            return Ok(Expr::Range(

                Box::new(x),

                Box::new(Expr::Call("all".into(), vec![])),

            ));

        }

        Ok(x)

    }

    fn primary(&mut self) -> Result<Expr, ParseError> {

        match self.peek().cloned() {

            Some(Tok::LParen) => {

                self.pos += 1;

                let e = self.union()?;

                if !self.eat(&Tok::RParen) {

                    return self.err("expected `)`");

                }

                Ok(e)

            }

            Some(Tok::Str(s)) => {

                self.pos += 1;

                Ok(Expr::Symbol(s))

            }

            Some(Tok::Symbol(s)) => {

                self.pos += 1;

                if self.eat(&Tok::LParen) {

                    if RAW_ARGS.contains(&s.as_str()) {

                        return self.raw_call(s);

                    }

                    let mut args = Vec::new();

                    if !self.eat(&Tok::RParen) {

                        loop {

                            args.push(self.union()?);

                            if self.eat(&Tok::Comma) {

                                continue;

                            }

                            if self.eat(&Tok::RParen) {

                                break;

                            }

                            return self.err("expected `,` or `)` in the arguments");

                        }

                    }

                    return Ok(Expr::Call(s, args));

                }

                Ok(Expr::Symbol(s))

            }

            Some(Tok::RParen) => self.err("unexpected `)`"),

            Some(_) => self.err("expected a change, bookmark, tag or function here"),

            None => self.err("the expression ends too soon"),

        }

    }

}

impl Parser {

    /// `name(` has been consumed: the text up to the matching `)` is the

    /// one argument, or a quoted string is.

    fn raw_call(&mut self, name: String) -> Result<Expr, ParseError> {

        if let (Some(Tok::Str(s)), Some(Tok::RParen)) = (

            self.peek().cloned(),

            self.toks.get(self.pos + 1).map(|t| &t.1),

        ) {

            self.pos += 2;

            return Ok(Expr::Call(name, vec![Expr::Symbol(s)]));

        }

        let start = self.at();

        let mut depth = 0usize;

        while let Some(t) = self.peek() {

            match t {

                Tok::LParen => depth += 1,

                Tok::RParen if depth == 0 => {

                    let end = self.at();

                    self.pos += 1;

                    let raw = self.src[start..end].trim().to_string();

                    return Ok(Expr::Call(name, vec![Expr::Symbol(raw)]));

                }

                Tok::RParen => depth -= 1,

                _ => {}

            }

            self.pos += 1;

        }

        self.err(format!("expected `)` to end {name}(…)"))

    }

}

/// Parse a revset expression.

pub fn parse(src: &str) -> Result<Expr, ParseError> {

    let toks = lex(src)?;

    if toks.is_empty() {

        return Err(ParseError {

            at: 0,

            message: "empty revset".into(),

        });

    }

    let mut p = Parser {

        src: src.to_string(),

        toks,

        pos: 0,

        end: src.len(),

    };

    let e = p.union()?;

    if p.pos < p.toks.len() {

        return p.err("unexpected input after the expression");

    }

    Ok(e)

}

/// A date range for `date(RANGE)`: wall-clock milliseconds, inclusive at

/// both ends, either end open.

#[derive(Clone, Copy, Debug, PartialEq, Eq)]

pub struct DateRange {

    pub from: Option<u64>,

    pub to: Option<u64>,

}

impl DateRange {

    pub fn contains(&self, ms: u64) -> bool {

        self.from.is_none_or(|f| ms >= f) && self.to.is_none_or(|t| ms <= t)

    }

}

/// `2026-10-01..`, `..2026-09-30`, `2026-09-01..2026-09-30`, `-7d..`,

/// `-12h..-1h`, or a single point, which means that day (or, for a

/// relative time, from then on). Dates are UTC; a time of day may follow

/// as `T13:45` or `T13:45:00`, with an optional `Z`.

pub fn parse_date_range(s: &str, now_ms: u64) -> Result<DateRange, String> {

    let s = s.trim();

    let (a, b, dotted) = match s.find("..") {

        Some(i) => (&s[..i], &s[i + 2..], true),

        None => (s, "", false),

    };

    let from = if a.is_empty() {

        None

    } else {

        Some(parse_point(a, now_ms)?.0)

    };

    let to = if dotted {

        if b.is_empty() {

            None

        } else {

            Some(parse_point(b, now_ms)?.1)

        }

    } else if a.starts_with('-') {

        None

    } else {

        Some(parse_point(a, now_ms)?.1)

    };

    if let (Some(f), Some(t)) = (from, to) {

        if f > t {

            return Err(format!("date range {s:?} ends before it starts"));

        }

    }

    Ok(DateRange { from, to })

}

/// A point in time as the (start, end) of what it names: a day spans its

/// 24 hours, a minute its 60 seconds, a relative time is an instant.

fn parse_point(s: &str, now_ms: u64) -> Result<(u64, u64), String> {

    let s = s.trim();

    if let Some(rel) = s.strip_prefix('-') {

        let (n, unit) = rel.split_at(rel.find(|c: char| !c.is_ascii_digit()).unwrap_or(rel.len()));

        let n: u64 = n

            .parse()

            .map_err(|_| format!("{s:?}: a relative time is -7d, -12h or -30m"))?;

        let ms = match unit {

            "d" => n * 86_400_000,

            "h" => n * 3_600_000,

            "m" => n * 60_000,

            "w" => n * 7 * 86_400_000,

            _ => return Err(format!("{s:?}: a relative time is -7d, -12h or -30m")),

        };

        let at = now_ms.saturating_sub(ms);

        return Ok((at, at));

    }

    let (date, time) = match s.split_once('T') {

        Some((d, t)) => (d, Some(t.trim_end_matches('Z'))),

        None => (s, None),

    };

    let mut parts = date.split('-');

    let bad = || format!("{s:?}: a date is YYYY-MM-DD, with an optional THH:MM[:SS]");

    let y: i64 = parts.next().and_then(|p| p.parse().ok()).ok_or_else(bad)?;

    let m: i64 = parts.next().and_then(|p| p.parse().ok()).ok_or_else(bad)?;

    let d: i64 = parts.next().and_then(|p| p.parse().ok()).ok_or_else(bad)?;

    if parts.next().is_some() || !(1..=12).contains(&m) || !(1..=31).contains(&d) {

        return Err(bad());

    }

    let day_ms = days_from_civil(y, m, d) * 86_400_000;

    if day_ms < 0 {

        return Err(bad());

    }

    let day_ms = day_ms as u64;

    match time {

        None => Ok((day_ms, day_ms + 86_400_000 - 1)),

        Some(t) => {

            let mut hms = t.split(':');

            let h: u64 = hms.next().and_then(|p| p.parse().ok()).ok_or_else(bad)?;

            let mi: u64 = hms.next().and_then(|p| p.parse().ok()).ok_or_else(bad)?;

            let sec: Option<u64> = match hms.next() {

                Some(p) => Some(p.parse().map_err(|_| bad())?),

                None => None,

            };

            if hms.next().is_some() || h > 23 || mi > 59 || sec.is_some_and(|x| x > 59) {

                return Err(bad());

            }

            let start = day_ms + h * 3_600_000 + mi * 60_000 + sec.unwrap_or(0) * 1000;

            let span = if sec.is_some() { 1000 } else { 60_000 };

            Ok((start, start + span - 1))

        }

    }

}

/// Days since 1970-01-01 of a civil date (Howard Hinnant's algorithm).

fn days_from_civil(y: i64, m: i64, d: i64) -> i64 {

    let y = if m <= 2 { y - 1 } else { y };

    let era = y.div_euclid(400);

    let yoe = y - era * 400;

    let mp = (m + 9) % 12;

    let doy = (153 * mp + 2) / 5 + d - 1;

    let doe = yoe * 365 + yoe / 4 - yoe / 100 + doy;

    era * 146_097 + doe - 719_468

}

#[cfg(test)]

mod tests {

    use super::*;

    fn p(s: &str) -> String {

        parse(s).unwrap().to_string()

    }

    #[test]

    fn precedence_and_ranges() {

        assert_eq!(p("a | b & c ~ d"), "(a | (b & (c ~ d)))");

        assert_eq!(p("a ~ b & c"), "((a ~ b) & c)");

        assert_eq!(p("(a | b) & c"), "((a | b) & c)");

        assert_eq!(p("::main"), "::main");

        assert_eq!(p("main::"), "main::");

        assert_eq!(p("a::b"), "a::b");

        assert_eq!(p("main..feature"), "main..feature");

        assert_eq!(p("..feature"), "::feature");

        assert_eq!(p("main.."), "main..all()");

        assert_eq!(p("origin/main..@"), "origin/main..@");

        assert_eq!(p("#fc68459c & v0.3.1"), "(#fc68459c & v0.3.1)");

        assert_eq!(p("a ~ b ~ c"), "((a ~ b) ~ c)");

    }

    #[test]

    fn calls_and_strings() {

        assert_eq!(

            p("touches(\"src/**\") & date(-7d..)"),

            "(touches(\"src/**\") & date(-7d..))"

        );

        assert_eq!(p("author('Andy McCall')"), "author(\"Andy McCall\")");

        assert_eq!(p("latest(main.., 5)"), "latest(main..all(), 5)");

        assert_eq!(

            p("date(2026-09-01..2026-09-30)"),

            "date(2026-09-01..2026-09-30)"

        );

        assert_eq!(p("date(\"..-1h\")"), "date(..-1h)");

        assert_eq!(p("all() ~ ::main"), "(all() ~ ::main)");

        assert_eq!(p("heads(a | b)"), "heads((a | b))");

        assert_eq!(p("none()"), "none()");

    }

    #[test]

    fn errors_point_at_the_problem() {

        assert!(parse("").is_err());

        assert_eq!(parse("a &").unwrap_err().at, 3);

        assert!(parse("a & )").is_err());

        assert!(parse("f(a, ").is_err());

        assert!(parse("'open").is_err());

        assert!(parse("a : b").is_err());

        assert!(parse("a b").is_err());

    }

    #[test]

    fn dates() {

        let now = 1_790_000_000_000; // 2026-09-21T06:13:20Z

        let r = parse_date_range("2026-09-01..2026-09-30", now).unwrap();

        assert_eq!(

            r.from,

            Some(days_from_civil(2026, 9, 1) as u64 * 86_400_000)

        );

        assert_eq!(

            r.to,

            Some(days_from_civil(2026, 9, 30) as u64 * 86_400_000 + 86_399_999)

        );

        assert!(r.contains(days_from_civil(2026, 9, 15) as u64 * 86_400_000 + 1));

        let r = parse_date_range("-7d..", now).unwrap();

        assert_eq!(

            r,

            DateRange {

                from: Some(now - 7 * 86_400_000),

                to: None

            }

        );

        let r = parse_date_range("..2026-01-01", now).unwrap();

        assert!(r.from.is_none() && r.to.is_some());

        let day = parse_date_range("2026-10-03", now).unwrap();

        assert_eq!(day.to.unwrap() - day.from.unwrap(), 86_399_999);

        let minute = parse_date_range("2026-10-03T09:30Z", now).unwrap();

        assert_eq!(minute.to.unwrap() - minute.from.unwrap(), 59_999);

        assert!(parse_date_range("2026-13-01", now).is_err());

        assert!(parse_date_range("yesterday", now).is_err());

        assert!(parse_date_range("2026-09-30..2026-09-01", now).is_err());

        assert_eq!(days_from_civil(1970, 1, 1), 0);

        assert_eq!(days_from_civil(2000, 3, 1), 11_017);

    }

}

oxy log -r 'v0.3.1..main & author(me)'   # a revset: set algebra over history

pub mod revset;

    /// `revset.<name>`: a saved revset, used as `name()`.

    pub revsets: BTreeMap<String, String>,

            revsets: BTreeMap::new(),

            k if k.starts_with("revset.") => {

                let name = &k["revset.".len()..];

                if name.is_empty()

                    || !name

                        .chars()

                        .all(|c| c.is_ascii_alphanumeric() || c == '_' || c == '-')

                {

                    return fail(format!(

                        "a revset's name is letters, digits, _ and -: {key:?}"

                    ));

                }

                if value.is_empty() {

                    self.revsets.remove(name);

                } else {

                    crate::revset::parse(value)

                        .map_err(|e| RepoError::Msg(format!("{key} = {value:?}: {e}")))?;

                    self.revsets.insert(name.to_string(), value.into());

                }

            }

mod revset;

pub use revset::{Revset, REVSET_BUDGET};

/// Revsets (docs/revset_query_language.md): symbols, relations, set

/// operators and the predicates, over a small graph with two heads and

/// a rename.

#[test]

fn revsets_select_changes_by_relation_author_text_date_and_path() {

    hermetic();

    let dir = tempfile::tempdir().unwrap();

    let root = dir.path();

    let mut repo = Repo::init(root).unwrap().with_home(root.join("home"));

    repo.create_identity("Ada", "[email protected]", IdentityScope::User)

        .unwrap();

    write(root, "src/a.rs", b"one\n");