crates/oxy-core/src/revset.rs at c2e1d09047db · andymccall/oxygen

# c2e1d09047db oxygen / crates / oxy-core / src / revset.rs

19.7 KiB · Rust · last changed Revsets: oxy log -r selects changes by set algebra over history 1 month ago source blame history raw

//! 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);
    }
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

1	//! Revsets: expressions that select a set of changes (docs/revset_query_language.md).
2	//!
3	//! This module parses the language; [`crate::repo::Repo::revset`] evaluates
4	//! it over a repository. Grammar, from loosest to tightest:
5	//!
6	//! ```text
7	//! union = inter ('\|' inter)*
8	//! inter = diff ('&' diff)*
9	//! diff = range ('~' range)* -- set difference, as in Jujutsu
10	//! range = '::' primary \| primary '::' primary? \| primary '..' primary? \| '..' primary \| primary
11	//! primary = '(' union ')' \| name '(' args ')' \| symbol \| string
12	//! ```
13	//!
14	//! A symbol is a bookmark, `REMOTE/NAME`, a tag, a ChangeId prefix, a
15	//! `#hash` prefix or `@`; a quoted string is a function argument.
16
17	use std::fmt;
18
19	#[derive(Clone, Debug, PartialEq, Eq)]
20	pub enum Expr {
21	/// A bookmark, tag, change prefix or `@`: the heads it names.
22	Symbol(String),
23	/// `::X`: X and its dependency closure.
24	Ancestors(Box<Expr>),
25	/// `X::`: X and everything depending on it.
26	Descendants(Box<Expr>),
27	/// `X::Y`: in both `X::` and `::Y`.
28	Between(Box<Expr>, Box<Expr>),
29	/// `X..Y`: `::Y ~ ::X`.
30	Range(Box<Expr>, Box<Expr>),
31	Union(Box<Expr>, Box<Expr>),
32	Intersection(Box<Expr>, Box<Expr>),
33	Difference(Box<Expr>, Box<Expr>),
34	/// `name(args)`; a string argument is an `Expr::Symbol` holding its text.
35	Call(String, Vec<Expr>),
36	}
37
38	impl fmt::Display for Expr {
39	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
40	match self {
41	Expr::Symbol(s) => {
42	if s.is_empty() \|\| s.chars().any(\|c\| !is_symbol_char(c)) {
43	write!(f, "{s:?}")
44	} else {
45	f.write_str(s)
46	}
47	}
48	Expr::Ancestors(x) => write!(f, "::{x}"),
49	Expr::Descendants(x) => write!(f, "{x}::"),
50	Expr::Between(x, y) => write!(f, "{x}::{y}"),
51	Expr::Range(x, y) => write!(f, "{x}..{y}"),
52	Expr::Union(x, y) => write!(f, "({x} \| {y})"),
53	Expr::Intersection(x, y) => write!(f, "({x} & {y})"),
54	Expr::Difference(x, y) => write!(f, "({x} ~ {y})"),
55	Expr::Call(name, args) => {
56	write!(f, "{name}(")?;
57	for (i, a) in args.iter().enumerate() {
58	if i > 0 {
59	f.write_str(", ")?;
60	}
61	write!(f, "{a}")?;
62	}
63	f.write_str(")")
64	}
65	}
66	}
67	}
68
69	#[derive(Clone, Debug, PartialEq, Eq)]
70	pub struct ParseError {
71	pub at: usize,
72	pub message: String,
73	}
74
75	impl fmt::Display for ParseError {
76	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
77	write!(f, "{} (at character {})", self.message, self.at + 1)
78	}
79	}
80
81	impl std::error::Error for ParseError {}
82
83	#[derive(Clone, Debug, PartialEq, Eq)]
84	enum Tok {
85	Symbol(String),
86	Str(String),
87	ColonColon,
88	DotDot,
89	Tilde,
90	Amp,
91	Pipe,
92	LParen,
93	RParen,
94	Comma,
95	}
96
97	fn is_symbol_char(c: char) -> bool {
98	c.is_alphanumeric() \|\| matches!(c, '_' \| '.' \| '/' \| '@' \| '#' \| '-' \| '+')
99	}
100
101	fn lex(src: &str) -> Result<Vec<(usize, Tok)>, ParseError> {
102	let mut out = Vec::new();
103	let chars: Vec<(usize, char)> = src.char_indices().collect();
104	let mut i = 0;
105	while i < chars.len() {
106	let (at, c) = chars[i];
107	match c {
108	c if c.is_whitespace() => i += 1,
109	':' => {
110	if chars.get(i + 1).map(\|x\| x.1) == Some(':') {
111	out.push((at, Tok::ColonColon));
112	i += 2;
113	} else {
114	return Err(ParseError {
115	at,
116	message: "expected `::`".into(),
117	});
118	}
119	}
120	'.' if chars.get(i + 1).map(\|x\| x.1) == Some('.') => {
121	out.push((at, Tok::DotDot));
122	i += 2;
123	}
124	'~' => {
125	out.push((at, Tok::Tilde));
126	i += 1;
127	}
128	'&' => {
129	out.push((at, Tok::Amp));
130	i += 1;
131	}
132	'\|' => {
133	out.push((at, Tok::Pipe));
134	i += 1;
135	}
136	'(' => {
137	out.push((at, Tok::LParen));
138	i += 1;
139	}
140	')' => {
141	out.push((at, Tok::RParen));
142	i += 1;
143	}
144	',' => {
145	out.push((at, Tok::Comma));
146	i += 1;
147	}
148	'"' \| '\'' => {
149	let quote = c;
150	let mut s = String::new();
151	let mut j = i + 1;
152	loop {
153	match chars.get(j) {
154	None => {
155	return Err(ParseError {
156	at,
157	message: "unterminated string".into(),
158	})
159	}
160	Some((_, ch)) if *ch == quote => break,
161	Some((_, '\\')) => {
162	if let Some((_, next)) = chars.get(j + 1) {
163	s.push(*next);
164	j += 2;
165	} else {
166	j += 1;
167	}
168	}
169	Some((_, ch)) => {
170	s.push(*ch);
171	j += 1;
172	}
173	}
174	}
175	out.push((at, Tok::Str(s)));
176	i = j + 1;
177	}
178	c if is_symbol_char(c) => {
179	let mut s = String::new();
180	let mut j = i;
181	// `..` ends a symbol: `main..feature`.
182	while let Some((_, ch)) = chars.get(j) {
183	if !is_symbol_char(*ch) {
184	break;
185	}
186	if *ch == '.' && chars.get(j + 1).map(\|x\| x.1) == Some('.') {
187	break;
188	}
189	s.push(*ch);
190	j += 1;
191	}
192	out.push((at, Tok::Symbol(s)));
193	i = j;
194	}
195	other => {
196	return Err(ParseError {
197	at,
198	message: format!("unexpected character {other:?}"),
199	})
200	}
201	}
202	}
203	Ok(out)
204	}
205
206	struct Parser {
207	src: String,
208	toks: Vec<(usize, Tok)>,
209	pos: usize,
210	end: usize,
211	}
212
213	/// Functions whose argument is taken as written, not parsed: a date range
214	/// such as `-7d..` would otherwise read as a revset range.
215	const RAW_ARGS: [&str; 1] = ["date"];
216
217	impl Parser {
218	fn peek(&self) -> Option<&Tok> {
219	self.toks.get(self.pos).map(\|t\| &t.1)
220	}
221	fn at(&self) -> usize {
222	self.toks.get(self.pos).map(\|t\| t.0).unwrap_or(self.end)
223	}
224	fn eat(&mut self, t: &Tok) -> bool {
225	if self.peek() == Some(t) {
226	self.pos += 1;
227	true
228	} else {
229	false
230	}
231	}
232	fn err<T>(&self, message: impl Into<String>) -> Result<T, ParseError> {
233	Err(ParseError {
234	at: self.at(),
235	message: message.into(),
236	})
237	}
238
239	fn union(&mut self) -> Result<Expr, ParseError> {
240	let mut left = self.inter()?;
241	while self.eat(&Tok::Pipe) {
242	let right = self.inter()?;
243	left = Expr::Union(Box::new(left), Box::new(right));
244	}
245	Ok(left)
246	}
247
248	fn inter(&mut self) -> Result<Expr, ParseError> {
249	let mut left = self.diff()?;
250	while self.eat(&Tok::Amp) {
251	let right = self.diff()?;
252	left = Expr::Intersection(Box::new(left), Box::new(right));
253	}
254	Ok(left)
255	}
256
257	fn diff(&mut self) -> Result<Expr, ParseError> {
258	let mut left = self.range()?;
259	while self.eat(&Tok::Tilde) {
260	let right = self.range()?;
261	left = Expr::Difference(Box::new(left), Box::new(right));
262	}
263	Ok(left)
264	}
265
266	/// Whether the next token starts a primary expression.
267	fn starts_primary(&self) -> bool {
268	matches!(
269	self.peek(),
270	Some(Tok::Symbol(_) \| Tok::Str(_) \| Tok::LParen)
271	)
272	}
273
274	fn range(&mut self) -> Result<Expr, ParseError> {
275	if self.eat(&Tok::ColonColon) {
276	let x = self.primary()?;
277	return Ok(Expr::Ancestors(Box::new(x)));
278	}
279	if self.eat(&Tok::DotDot) {
280	let y = self.primary()?;
281	return Ok(Expr::Ancestors(Box::new(y)));
282	}
283	let x = self.primary()?;
284	if self.eat(&Tok::ColonColon) {
285	if self.starts_primary() {
286	let y = self.primary()?;
287	return Ok(Expr::Between(Box::new(x), Box::new(y)));
288	}
289	return Ok(Expr::Descendants(Box::new(x)));
290	}
291	if self.eat(&Tok::DotDot) {
292	if self.starts_primary() {
293	let y = self.primary()?;
294	return Ok(Expr::Range(Box::new(x), Box::new(y)));
295	}
296	// `X..`: what the repository has beyond X.
297	return Ok(Expr::Range(
298	Box::new(x),
299	Box::new(Expr::Call("all".into(), vec![])),
300	));
301	}
302	Ok(x)
303	}
304
305	fn primary(&mut self) -> Result<Expr, ParseError> {
306	match self.peek().cloned() {
307	Some(Tok::LParen) => {
308	self.pos += 1;
309	let e = self.union()?;
310	if !self.eat(&Tok::RParen) {
311	return self.err("expected `)`");
312	}
313	Ok(e)
314	}
315	Some(Tok::Str(s)) => {
316	self.pos += 1;
317	Ok(Expr::Symbol(s))
318	}
319	Some(Tok::Symbol(s)) => {
320	self.pos += 1;
321	if self.eat(&Tok::LParen) {
322	if RAW_ARGS.contains(&s.as_str()) {
323	return self.raw_call(s);
324	}
325	let mut args = Vec::new();
326	if !self.eat(&Tok::RParen) {
327	loop {
328	args.push(self.union()?);
329	if self.eat(&Tok::Comma) {
330	continue;
331	}
332	if self.eat(&Tok::RParen) {
333	break;
334	}
335	return self.err("expected `,` or `)` in the arguments");
336	}
337	}
338	return Ok(Expr::Call(s, args));
339	}
340	Ok(Expr::Symbol(s))
341	}
342	Some(Tok::RParen) => self.err("unexpected `)`"),
343	Some(_) => self.err("expected a change, bookmark, tag or function here"),
344	None => self.err("the expression ends too soon"),
345	}
346	}
347	}
348
349	impl Parser {
350	/// `name(` has been consumed: the text up to the matching `)` is the
351	/// one argument, or a quoted string is.
352	fn raw_call(&mut self, name: String) -> Result<Expr, ParseError> {
353	if let (Some(Tok::Str(s)), Some(Tok::RParen)) = (
354	self.peek().cloned(),
355	self.toks.get(self.pos + 1).map(\|t\| &t.1),
356	) {
357	self.pos += 2;
358	return Ok(Expr::Call(name, vec![Expr::Symbol(s)]));
359	}
360	let start = self.at();
361	let mut depth = 0usize;
362	while let Some(t) = self.peek() {
363	match t {
364	Tok::LParen => depth += 1,
365	Tok::RParen if depth == 0 => {
366	let end = self.at();
367	self.pos += 1;
368	let raw = self.src[start..end].trim().to_string();
369	return Ok(Expr::Call(name, vec![Expr::Symbol(raw)]));
370	}
371	Tok::RParen => depth -= 1,
372	_ => {}
373	}
374	self.pos += 1;
375	}
376	self.err(format!("expected `)` to end {name}(…)"))
377	}
378	}
379
380	/// Parse a revset expression.
381	pub fn parse(src: &str) -> Result<Expr, ParseError> {
382	let toks = lex(src)?;
383	if toks.is_empty() {
384	return Err(ParseError {
385	at: 0,
386	message: "empty revset".into(),
387	});
388	}
389	let mut p = Parser {
390	src: src.to_string(),
391	toks,
392	pos: 0,
393	end: src.len(),
394	};
395	let e = p.union()?;
396	if p.pos < p.toks.len() {
397	return p.err("unexpected input after the expression");
398	}
399	Ok(e)
400	}
401
402	/// A date range for `date(RANGE)`: wall-clock milliseconds, inclusive at
403	/// both ends, either end open.
404	#[derive(Clone, Copy, Debug, PartialEq, Eq)]
405	pub struct DateRange {
406	pub from: Option<u64>,
407	pub to: Option<u64>,
408	}
409
410	impl DateRange {
411	pub fn contains(&self, ms: u64) -> bool {
412	self.from.is_none_or(\|f\| ms >= f) && self.to.is_none_or(\|t\| ms <= t)
413	}
414	}
415
416	/// `2026-10-01..`, `..2026-09-30`, `2026-09-01..2026-09-30`, `-7d..`,
417	/// `-12h..-1h`, or a single point, which means that day (or, for a
418	/// relative time, from then on). Dates are UTC; a time of day may follow
419	/// as `T13:45` or `T13:45:00`, with an optional `Z`.
420	pub fn parse_date_range(s: &str, now_ms: u64) -> Result<DateRange, String> {
421	let s = s.trim();
422	let (a, b, dotted) = match s.find("..") {
423	Some(i) => (&s[..i], &s[i + 2..], true),
424	None => (s, "", false),
425	};
426	let from = if a.is_empty() {
427	None
428	} else {
429	Some(parse_point(a, now_ms)?.0)
430	};
431	let to = if dotted {
432	if b.is_empty() {
433	None
434	} else {
435	Some(parse_point(b, now_ms)?.1)
436	}
437	} else if a.starts_with('-') {
438	None
439	} else {
440	Some(parse_point(a, now_ms)?.1)
441	};
442	if let (Some(f), Some(t)) = (from, to) {
443	if f > t {
444	return Err(format!("date range {s:?} ends before it starts"));
445	}
446	}
447	Ok(DateRange { from, to })
448	}
449
450	/// A point in time as the (start, end) of what it names: a day spans its
451	/// 24 hours, a minute its 60 seconds, a relative time is an instant.
452	fn parse_point(s: &str, now_ms: u64) -> Result<(u64, u64), String> {
453	let s = s.trim();
454	if let Some(rel) = s.strip_prefix('-') {
455	let (n, unit) = rel.split_at(rel.find(\|c: char\| !c.is_ascii_digit()).unwrap_or(rel.len()));
456	let n: u64 = n
457	.parse()
458	.map_err(\|_\| format!("{s:?}: a relative time is -7d, -12h or -30m"))?;
459	let ms = match unit {
460	"d" => n * 86_400_000,
461	"h" => n * 3_600_000,
462	"m" => n * 60_000,
463	"w" => n * 7 * 86_400_000,
464	_ => return Err(format!("{s:?}: a relative time is -7d, -12h or -30m")),
465	};
466	let at = now_ms.saturating_sub(ms);
467	return Ok((at, at));
468	}
469	let (date, time) = match s.split_once('T') {
470	Some((d, t)) => (d, Some(t.trim_end_matches('Z'))),
471	None => (s, None),
472	};
473	let mut parts = date.split('-');
474	let bad = \|\| format!("{s:?}: a date is YYYY-MM-DD, with an optional THH:MM[:SS]");
475	let y: i64 = parts.next().and_then(\|p\| p.parse().ok()).ok_or_else(bad)?;
476	let m: i64 = parts.next().and_then(\|p\| p.parse().ok()).ok_or_else(bad)?;
477	let d: i64 = parts.next().and_then(\|p\| p.parse().ok()).ok_or_else(bad)?;
478	if parts.next().is_some() \|\| !(1..=12).contains(&m) \|\| !(1..=31).contains(&d) {
479	return Err(bad());
480	}
481	let day_ms = days_from_civil(y, m, d) * 86_400_000;
482	if day_ms < 0 {
483	return Err(bad());
484	}
485	let day_ms = day_ms as u64;
486	match time {
487	None => Ok((day_ms, day_ms + 86_400_000 - 1)),
488	Some(t) => {
489	let mut hms = t.split(':');
490	let h: u64 = hms.next().and_then(\|p\| p.parse().ok()).ok_or_else(bad)?;
491	let mi: u64 = hms.next().and_then(\|p\| p.parse().ok()).ok_or_else(bad)?;
492	let sec: Option<u64> = match hms.next() {
493	Some(p) => Some(p.parse().map_err(\|_\| bad())?),
494	None => None,
495	};
496	if hms.next().is_some() \|\| h > 23 \|\| mi > 59 \|\| sec.is_some_and(\|x\| x > 59) {
497	return Err(bad());
498	}
499	let start = day_ms + h * 3_600_000 + mi * 60_000 + sec.unwrap_or(0) * 1000;
500	let span = if sec.is_some() { 1000 } else { 60_000 };
501	Ok((start, start + span - 1))
502	}
503	}
504	}
505
506	/// Days since 1970-01-01 of a civil date (Howard Hinnant's algorithm).
507	fn days_from_civil(y: i64, m: i64, d: i64) -> i64 {
508	let y = if m <= 2 { y - 1 } else { y };
509	let era = y.div_euclid(400);
510	let yoe = y - era * 400;
511	let mp = (m + 9) % 12;
512	let doy = (153 * mp + 2) / 5 + d - 1;
513	let doe = yoe * 365 + yoe / 4 - yoe / 100 + doy;
514	era * 146_097 + doe - 719_468
515	}
516
517	#[cfg(test)]
518	mod tests {
519	use super::*;
520
521	fn p(s: &str) -> String {
522	parse(s).unwrap().to_string()
523	}
524
525	#[test]
526	fn precedence_and_ranges() {
527	assert_eq!(p("a \| b & c ~ d"), "(a \| (b & (c ~ d)))");
528	assert_eq!(p("a ~ b & c"), "((a ~ b) & c)");
529	assert_eq!(p("(a \| b) & c"), "((a \| b) & c)");
530	assert_eq!(p("::main"), "::main");
531	assert_eq!(p("main::"), "main::");
532	assert_eq!(p("a::b"), "a::b");
533	assert_eq!(p("main..feature"), "main..feature");
534	assert_eq!(p("..feature"), "::feature");
535	assert_eq!(p("main.."), "main..all()");
536	assert_eq!(p("origin/main..@"), "origin/main..@");
537	assert_eq!(p("#fc68459c & v0.3.1"), "(#fc68459c & v0.3.1)");
538	assert_eq!(p("a ~ b ~ c"), "((a ~ b) ~ c)");
539	}
540
541	#[test]
542	fn calls_and_strings() {
543	assert_eq!(
544	p("touches(\"src/**\") & date(-7d..)"),
545	"(touches(\"src/**\") & date(-7d..))"
546	);
547	assert_eq!(p("author('Andy McCall')"), "author(\"Andy McCall\")");
548	assert_eq!(p("latest(main.., 5)"), "latest(main..all(), 5)");
549	assert_eq!(
550	p("date(2026-09-01..2026-09-30)"),
551	"date(2026-09-01..2026-09-30)"
552	);
553	assert_eq!(p("date(\"..-1h\")"), "date(..-1h)");
554	assert_eq!(p("all() ~ ::main"), "(all() ~ ::main)");
555	assert_eq!(p("heads(a \| b)"), "heads((a \| b))");
556	assert_eq!(p("none()"), "none()");
557	}
558
559	#[test]
560	fn errors_point_at_the_problem() {
561	assert!(parse("").is_err());
562	assert_eq!(parse("a &").unwrap_err().at, 3);
563	assert!(parse("a & )").is_err());
564	assert!(parse("f(a, ").is_err());
565	assert!(parse("'open").is_err());
566	assert!(parse("a : b").is_err());
567	assert!(parse("a b").is_err());
568	}
569
570	#[test]
571	fn dates() {
572	let now = 1_790_000_000_000; // 2026-09-21T06:13:20Z
573	let r = parse_date_range("2026-09-01..2026-09-30", now).unwrap();
574	assert_eq!(
575	r.from,
576	Some(days_from_civil(2026, 9, 1) as u64 * 86_400_000)
577	);
578	assert_eq!(
579	r.to,
580	Some(days_from_civil(2026, 9, 30) as u64 * 86_400_000 + 86_399_999)
581	);
582	assert!(r.contains(days_from_civil(2026, 9, 15) as u64 * 86_400_000 + 1));
583	let r = parse_date_range("-7d..", now).unwrap();
584	assert_eq!(
585	r,
586	DateRange {
587	from: Some(now - 7 * 86_400_000),
588	to: None
589	}
590	);
591	let r = parse_date_range("..2026-01-01", now).unwrap();
592	assert!(r.from.is_none() && r.to.is_some());
593	let day = parse_date_range("2026-10-03", now).unwrap();
594	assert_eq!(day.to.unwrap() - day.from.unwrap(), 86_399_999);
595	let minute = parse_date_range("2026-10-03T09:30Z", now).unwrap();
596	assert_eq!(minute.to.unwrap() - minute.from.unwrap(), 59_999);
597	assert!(parse_date_range("2026-13-01", now).is_err());
598	assert!(parse_date_range("yesterday", now).is_err());
599	assert!(parse_date_range("2026-09-30..2026-09-01", now).is_err());
600	assert_eq!(days_from_civil(1970, 1, 1), 0);
601	assert_eq!(days_from_civil(2000, 3, 1), 11_017);
602	}
603	}

Keyboard