adnv 1.5.0

//! An upper bound, computed without recursing, on how deep the parser will go.
//!
//! `hcl.pest` is mutually recursive and pest generates a recursive descent, so
//! a deep enough input exhausts the stack — and a stack overflow aborts the
//! process, it is not something we could catch and report. Measured on a debug
//! build with the 2 MiB stack a Tokio worker thread gets, `a = [[[[…` aborts
//! between 300 and 400 levels of brackets, about 7 KiB of stack each, and
//! `a = 1-1-1-…` between 800 and 1600, about 1.7 KiB each. Both shapes fit in
//! well under 3 KiB of input, so [`super::MAX_INPUT_BYTES`] protects nothing on
//! its own.
//!
//! Every descent in the grammar is gated on one of two tokens:
//!
//! * an opening bracket — `Tuple`, `Object`, `Parenthesis`, `Arguments`,
//!   `Index`, `BlockBody`, `ForExpr` and `TemplateInterpolation` all open one
//!   before recursing into `Expression` or `Body`;
//! * a binary operator, or the `?`/`:` of a ternary, which `Expression`
//!   recurses on directly with no bracket in between.
//!
//! Counting both, per enclosing group, therefore bounds the descent from above,
//! and bounds the AST builder — whose own `Object::process` ⇄
//! `Expression::process` cycle walks the pairs the parser produced — with it.
//!
//! The scan deliberately over-counts rather than under-counts: budget spent on
//! an operator that was not really one only costs a false rejection, while an
//! operator missed costs the guarantee. The one place it must not guess is a
//! construct whose body is literal text — a comment, a quoted string, a
//! heredoc — because those routinely hold brackets and dashes that the parser
//! never descends into. Those are skipped, except for the `${…}` and `%{…}`
//! interpolations inside strings and heredocs, which are real expressions.

use super::Error;

/// Ceiling on the bound returned by the scan.
///
/// A real Terraform file sits around a dozen: nesting runs six to ten levels
/// and expressions chain one or two operators. 96 leaves that four times over,
/// and caps the worst case at roughly 96 × 7 KiB ≈ 670 KiB of stack, a third of
/// the smallest stack the parser runs on.
const MAX_DEPTH: usize = 96;

pub(super) fn check(input: &str) -> Result<(), Error> {
    let bytes = input.as_bytes();

    let mut budget = Budget::default();
    let mut mode = Mode::Code;
    let mut run = Run::None;
    let mut i = 0;

    while i < bytes.len() {
        match mode {
            Mode::Code => {
                let (consumed, event) = code_token(bytes, i, run);
                run = run.after(bytes[i], &event);
                i += consumed;

                match event {
                    Event::Open => budget.open(None)?,
                    Event::Close => {
                        if let Some(previous) = budget.close() {
                            mode = previous;
                        }
                    }
                    Event::Operator => budget.operator()?,
                    Event::EndOfExpression => budget.end_expression(),
                    Event::EnterString => mode = Mode::Quoted,
                    Event::EnterHeredoc { end, tag_len } => {
                        mode = Mode::Heredoc { end, tag_len };
                    }
                    Event::None => {}
                }
            }
            Mode::Heredoc { end, tag_len } if i >= end => {
                mode = Mode::Code;
                run = Run::None;
                i = end + tag_len;
            }
            Mode::Quoted | Mode::Heredoc { .. } => match literal_token(bytes, i) {
                LiteralToken::Interpolation(len) => {
                    budget.open(Some(mode))?;
                    mode = Mode::Code;
                    run = Run::None;
                    i += len;
                }
                LiteralToken::Other(len) => {
                    if matches!(mode, Mode::Quoted) && bytes[i] == b'"' {
                        mode = Mode::Code;
                        run = Run::None;
                    }
                    i += len;
                }
            },
        }
    }

    Ok(())
}

/// The running bound: one level per enclosing group, plus one per operator the
/// innermost expression of each has chained so far.
#[derive(Default)]
struct Budget {
    groups: Vec<Group>,
    /// Kept in step with `groups.len() + groups.iter().map(|g| g.ops).sum()`.
    depth: usize,
}

impl Budget {
    fn spend(&mut self) -> Result<(), Error> {
        self.depth += 1;
        if self.depth > MAX_DEPTH {
            return Err(Error::TooDeep {
                depth: self.depth,
                max: MAX_DEPTH,
            });
        }

        Ok(())
    }

    /// `interpolated` carries the literal mode a `${…}` has to return to.
    fn open(&mut self, interpolated: Option<Mode>) -> Result<(), Error> {
        self.groups.push(Group {
            ops: 0,
            interpolated,
        });

        self.spend()
    }

    fn close(&mut self) -> Option<Mode> {
        let group = self.groups.pop()?;
        self.depth -= 1 + group.ops;

        group.interpolated
    }

    fn operator(&mut self) -> Result<(), Error> {
        if let Some(group) = self.groups.last_mut() {
            group.ops += 1;
        }

        self.spend()
    }

    /// A `,` or an `=` ends the expression the chain belonged to: what follows
    /// is its sibling, not nested inside it.
    fn end_expression(&mut self) {
        if let Some(group) = self.groups.last_mut() {
            self.depth -= group.ops;
            group.ops = 0;
        }
    }
}

struct Group {
    /// Operators counted in this group since the last expression boundary.
    ops: usize,
    /// `Some` when the group is a `${…}`/`%{…}`, carrying the literal mode to
    /// return to once it closes.
    interpolated: Option<Mode>,
}

#[derive(Debug, Clone, Copy)]
enum Mode {
    Code,
    Quoted,
    /// A heredoc whose terminator was already located: `end` is where the tag
    /// closing it starts. The scan only enters this mode once the terminator is
    /// known, so it can never swallow the rest of the file.
    Heredoc {
        end: usize,
        tag_len: usize,
    },
}

/// Whether the bytes just scanned belong to an identifier, which is what tells
/// a `-` operator from the `-` of `tf-modules`: `IdentChar` accepts `-` and
/// digits, but an identifier cannot *start* with a digit.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Run {
    None,
    Ident,
    Number,
}

impl Run {
    fn after(self, first: u8, event: &Event) -> Self {
        match event {
            Event::None if is_ident_char(first) => match self {
                Self::None if first.is_ascii_digit() => Self::Number,
                Self::None => Self::Ident,
                run => run,
            },
            _ => Self::None,
        }
    }
}

enum Event {
    Open,
    Close,
    Operator,
    EndOfExpression,
    EnterString,
    EnterHeredoc { end: usize, tag_len: usize },
    None,
}

/// Classify the token at `at` in code context, returning how many bytes it
/// spans. A comment is reported as `None` over its whole length, which is how
/// its contents stay out of the count.
fn code_token(bytes: &[u8], at: usize, run: Run) -> (usize, Event) {
    let next = bytes.get(at + 1).copied();

    match bytes[at] {
        b'(' | b'[' | b'{' => (1, Event::Open),
        b')' | b']' | b'}' => (1, Event::Close),
        b'"' => (1, Event::EnterString),
        b'#' => (line_len(bytes, at), Event::None),
        b'/' if next == Some(b'/') => (line_len(bytes, at), Event::None),
        b'/' if next == Some(b'*') => (block_comment_len(bytes, at), Event::None),
        // `==` is a comparison; a lone `=` opens an attribute or an object
        // entry and `=>` the value half of a `for` object, and a `,` separates
        // two entries — all three end the expression the chain belonged to.
        b'=' if next == Some(b'=') => (2, Event::Operator),
        b',' | b'=' => (1, Event::EndOfExpression),
        b'<' if next == Some(b'<') => match heredoc(bytes, at) {
            Some((len, end, tag_len)) => (len, Event::EnterHeredoc { end, tag_len }),
            None => (1, Event::Operator),
        },
        b'!' | b'<' | b'>' if next == Some(b'=') => (2, Event::Operator),
        b'&' if next == Some(b'&') => (2, Event::Operator),
        b'|' if next == Some(b'|') => (2, Event::Operator),
        // `-` continues an identifier when one is already open: pest reads
        // `a-1-1` as a single `Identifier` and never recurses on it.
        b'-' if run == Run::Ident && next.is_some_and(is_ident_char) => (1, Event::None),
        b'+' | b'-' | b'*' | b'/' | b'%' | b'<' | b'>' | b'?' | b':' => (1, Event::Operator),
        _ => (1, Event::None),
    }
}

enum LiteralToken {
    Interpolation(usize),
    Other(usize),
}

/// Classify the token at `at` inside a quoted string or a heredoc body.
fn literal_token(bytes: &[u8], at: usize) -> LiteralToken {
    let rest = &bytes[at..];

    // `$${` and `%%{` are the escapes for a literal `${` and `%{`.
    if rest.starts_with(b"$${") || rest.starts_with(b"%%{") {
        return LiteralToken::Other(3);
    }
    if rest.starts_with(b"${") || rest.starts_with(b"%{") {
        // `${~` strips whitespace and is still one interpolation.
        let len = if rest.get(2) == Some(&b'~') { 3 } else { 2 };
        return LiteralToken::Interpolation(len);
    }
    if rest.starts_with(b"\\") {
        return LiteralToken::Other(2.min(rest.len()));
    }

    LiteralToken::Other(1)
}

/// Match `<<TAG` or `<<-TAG` at `at` and locate the line that closes it.
///
/// Returns the length of the introducer, the offset of the closing tag and its
/// length, or `None` when the shape is not a heredoc or never terminates — in
/// which case the parser will fail the `Heredoc` rule and retry the same text
/// through the other `ExprTerm` alternatives, so it must stay in the count.
fn heredoc(bytes: &[u8], at: usize) -> Option<(usize, usize, usize)> {
    let mut cursor = at + 2;
    if bytes.get(cursor) == Some(&b'-') {
        cursor += 1;
    }

    let tag_start = cursor;
    if !bytes.get(cursor).copied().is_some_and(is_ident_first) {
        return None;
    }
    while bytes.get(cursor).copied().is_some_and(is_ident_char) {
        cursor += 1;
    }
    let tag = &bytes[tag_start..cursor];

    // The introducer must be alone on its line.
    while matches!(bytes.get(cursor), Some(b' ' | b'\t' | b'\r')) {
        cursor += 1;
    }
    if bytes.get(cursor) != Some(&b'\n') {
        return None;
    }
    let body = cursor + 1;

    let mut line = body;
    while line <= bytes.len() {
        let mut probe = line;
        while matches!(bytes.get(probe), Some(b' ' | b'\t')) {
            probe += 1;
        }
        if bytes[probe..].starts_with(tag) {
            return Some((body - at, probe, tag.len()));
        }
        match bytes[line..].iter().position(|b| *b == b'\n') {
            Some(offset) => line += offset + 1,
            None => break,
        }
    }

    None
}

fn line_len(bytes: &[u8], at: usize) -> usize {
    bytes[at..]
        .iter()
        .position(|b| *b == b'\n')
        .unwrap_or(bytes.len() - at)
}

fn block_comment_len(bytes: &[u8], at: usize) -> usize {
    bytes[at + 2..]
        .windows(2)
        .position(|pair| pair == b"*/")
        .map_or(bytes.len() - at, |offset| offset + 4)
}

fn is_ident_first(b: u8) -> bool {
    b.is_ascii_alphabetic() || b == b'_'
}

fn is_ident_char(b: u8) -> bool {
    b.is_ascii_alphanumeric() || b == b'_' || b == b'-'
}

#[cfg(test)]
mod tests {
    use super::{MAX_DEPTH, check};
    use crate::parsers::hcl::Error;

    #[track_caller]
    fn accepts(input: &str) {
        assert!(
            check(input).is_ok(),
            "rejected an input the parser handles: {input:?}"
        );
    }

    #[track_caller]
    fn rejects(input: &str) {
        assert!(
            matches!(check(input), Err(Error::TooDeep { .. })),
            "accepted an input that would overflow the stack: {input:?}"
        );
    }

    /// The two shapes measured to abort the process, at depths well below the
    /// ones that did it: `[[[[…` around 300 levels and `1-1-1-…` around 800.
    #[test]
    fn rejects_the_shapes_that_overflow_the_stack() {
        let deep = MAX_DEPTH + 1;

        rejects(&format!("a = {}1{}\n", "[".repeat(deep), "]".repeat(deep)));
        // Unterminated: pest descends just as far before failing.
        rejects(&format!("a = {}1\n", "[".repeat(deep)));
        rejects(&format!("a = 1{}\n", "-1".repeat(deep)));
        rejects(&format!("a = 1{}\n", "+1".repeat(deep)));
        // Through a string interpolation, which `StringLit` cannot match, so
        // `TemplateExpr` takes over and recurses into `Expression`.
        rejects(&format!(
            "a = \"${{{}1{}}}\"\n",
            "[".repeat(deep),
            "]".repeat(deep)
        ));
        // Nested blocks, which recurse through `Body` rather than `Expression`.
        rejects(&format!("{}\n{}", "b {".repeat(deep), "}".repeat(deep)));
    }

    /// Everything here is text the parser never descends into, and all of it
    /// shows up in real Terraform: a dash in a module name, a `/` in a URL, a
    /// shell script in a heredoc, a commented-out block.
    #[test]
    fn literal_text_does_not_spend_the_budget() {
        let many = MAX_DEPTH * 4;

        accepts(&format!(
            "module \"m\" {{\n  source = \"gitlab.com/vigigloo/tf-modules/{}\"\n}}\n",
            "a-b-".repeat(many)
        ));
        accepts(&format!("# {}\na = 1\n", "[".repeat(many)));
        accepts(&format!("// {}\na = 1\n", "-1".repeat(many)));
        accepts(&format!("/* {} */\na = 1\n", "{(-".repeat(many)));
        accepts(&format!(
            "a = <<-EOT\n{}\nEOT\na = 1\n",
            "echo --flag --other {{[\n".repeat(many)
        ));
        // `a-1-1-…` is one `Identifier`, not a chain of subtractions.
        accepts(&format!("a = b{}\n", "-1".repeat(many)));
    }

    /// An interpolation inside a heredoc is a real expression, and the scan has
    /// to come back out of it into the heredoc body rather than into code.
    #[test]
    fn interpolations_nest_without_losing_the_enclosing_literal() {
        let many = MAX_DEPTH * 4;

        accepts(&format!(
            "a = <<-EOT\n${{var.x}} {}\n${{var.y}}\nEOT\n",
            "--- {{{ [[[ ".repeat(many)
        ));
        rejects(&format!(
            "a = <<-EOT\ntext ${{{}1{}}}\nEOT\n",
            "[".repeat(MAX_DEPTH + 1),
            "]".repeat(MAX_DEPTH + 1)
        ));
        // `$${` is the escape for a literal `${`, so what follows is text.
        accepts(&format!("a = \"$${{{}}}\"\n", "[".repeat(many)));
    }

    /// A heredoc that never closes must not let the scan skip the rest of the
    /// file: pest fails `Heredoc` and retries the same bytes as an expression.
    #[test]
    fn an_unterminated_heredoc_is_still_counted() {
        let deep = MAX_DEPTH + 1;

        rejects(&format!(
            "a = <<EOT\n{}1{}\n",
            "[".repeat(deep),
            "]".repeat(deep)
        ));
    }

    /// Siblings are not nested in one another, so a file wide enough to hold
    /// thousands of them still parses.
    #[test]
    fn breadth_is_not_depth() {
        let many = MAX_DEPTH * 10;

        accepts(&format!("a = [{}]\n", "1 + 1, ".repeat(many)));
        accepts(&format!("a = {{\n{}}}\n", "  k = 1 + 1\n".repeat(many)));
        accepts(&"module \"m\" {\n  source = \"x\"\n}\n".repeat(many));
    }

    /// The fixtures the rest of the suite parses, plus the sample the repository
    /// ships, have to stay under the limit — that is the whole false-positive
    /// risk of over-counting.
    #[test]
    fn the_repository_own_files_stay_well_under_the_limit() {
        for path in [
            "main.sample.tf",
            "tests/sources/parse/main.sample.test.tf",
            "tests/sources/parse/subdir/child.sample.test.tf",
            "tests/sources/parse/.hidden.sample.test.tf",
        ] {
            let input = std::fs::read_to_string(path).unwrap();
            assert!(check(&input).is_ok(), "{path} was rejected");
        }
    }
}

#[cfg(test)]
mod corpus {
    /// Run the bound over every file listed in `$HCL_CORPUS`, one path per line,
    /// and report the worst one. Not a fixture test: it exists to be pointed at
    /// a real Terraform estate when the limit is changed.
    #[test]
    #[ignore = "needs HCL_CORPUS"]
    fn worst_case_over_a_corpus() {
        let list = std::env::var("HCL_CORPUS").expect("HCL_CORPUS");
        let paths = std::fs::read_to_string(list).unwrap();

        let mut rejected = vec![];
        let mut count = 0;
        for path in paths.lines().filter(|line| !line.is_empty()) {
            let Ok(input) = std::fs::read_to_string(path) else {
                continue;
            };
            count += 1;
            if let Err(err) = super::check(&input) {
                rejected.push(format!("{path}: {err}"));
            }
        }

        eprintln!("{count} files scanned, {} rejected", rejected.len());
        for line in &rejected {
            eprintln!("  {line}");
        }
        assert!(
            rejected.is_empty(),
            "{} of {count} files rejected",
            rejected.len()
        );
    }
}