revset.rs 93.4%

394 of 422 lines run, 35 of 73 functions · run #298 on main · run missed

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

Coverage / crates/oxy-core/src/revset.rs 93.4%

Keyboard