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