meant 0.1.0

use super::*;

/// Reject stack-hostile syntax before any recursive upstream parser or checker
/// sees it, counting two things against `max_source_nesting`.
///
/// **Comment runs**, first, by [`comment_run_preflight`]: the number of
/// consecutive comments between two real tokens. Comments are not free. The
/// pinned upstream `candid_parser::token::Tokenizer::next` skips a line or
/// block comment by calling itself, so a run of comments costs it one stack
/// frame each, and both the token loop below and the parser's own tokenizer
/// run that recursion (issue #219). The scan is a byte loop rather than a
/// `Tokenizer` pass for exactly that reason: the guard must not be built on
/// the thing it guards.
///
/// **Structural nesting**, second, over the token stream: open delimiters
/// plus a run of `opt`/`vec` constructors. Comment and string *contents*
/// never count here; what a comment costs is the comment-run bound above.
pub(super) fn check_source_nesting(
    source: &str,
    budget: &mut crate::budget::Budget<'_>,
) -> Result<(), CompileError> {
    let limits = budget.limits().clone();
    // Scan and tokenize exactly the text the parser will see. A leading BOM
    // left in would fail the first token, and the lexical-error early return
    // below would then skip this preflight for the whole source.
    let text = candid_text(source).0;
    // Before the first `Tokenizer` use, and over the whole text: the
    // tokenizer recurses through a comment run before it can report any
    // lexical error that follows it. So this refusal takes precedence over a
    // lexical diagnostic anywhere in the source, deliberately including one
    // *before* the run, where the parser would have stopped first: telling
    // the two apart would mean trusting a tokenizer pass over the prefix,
    // and the scan is what decides where that prefix ends.
    if let Err(observed) = comment_run_preflight(text.as_bytes(), limits.max_source_nesting) {
        return Err(CompileError::resource_limit(
            "source_nesting",
            limits.max_source_nesting,
            observed,
            format!(
                "Candid source has a run of {observed} consecutive comments, over the source nesting limit {}; a /* */ block counts as one comment",
                limits.max_source_nesting
            ),
        ));
    }
    let mut delimiters = 0usize;
    let mut unary = 0usize;
    for token in Tokenizer::new(text) {
        budget
            .checkpoint()
            .map_err(|error| budget_error(error, DiagnosticPhase::Parse, "source preflight"))?;
        let (_, token, _) = match token {
            Ok(token) => token,
            // Preserve the parser's established lexical diagnostic.
            Err(_) => return Ok(()),
        };
        match token {
            Token::Opt | Token::Vec => unary = unary.saturating_add(1),
            Token::LParen | Token::LBrace => {
                delimiters = delimiters.saturating_add(1);
                unary = 0;
            }
            Token::RParen | Token::RBrace => {
                delimiters = delimiters.saturating_sub(1);
                unary = 0;
            }
            _ => unary = 0,
        }
        let observed = delimiters.saturating_add(unary);
        if observed > limits.max_source_nesting {
            return Err(CompileError::resource_limit(
                "source_nesting",
                limits.max_source_nesting,
                observed,
                format!(
                    "Candid source nesting {observed} exceeds limit {}",
                    limits.max_source_nesting
                ),
            ));
        }
    }
    Ok(())
}

/// Refuse a record field whose id would be `u32::MAX` before the upstream
/// grammar sees it (issue #230).
///
/// The pinned `candid_parser` record rule computes the next positional id as
/// `id + 1` at **every** record field, labelled or not
/// (`grammar.lalrpop:174-175`). At `u32::MAX` that addition panics in a debug
/// build and wraps to 0 in a release build, so the next unnamed field silently
/// gets id 0. The upstream rule cannot be corrected from here, so the field is
/// refused in both builds alike, with the parser's own code. Variants compute
/// no next id and are not affected.
///
/// A field's id is its decimal or hex label, the Candid hash of its name, or,
/// unnamed, one more than the previous field's (0 for the first). The refusal
/// is reported when the record's closing brace arrives, which is when upstream
/// would reduce the record, so a lexical error inside the record keeps the
/// parser's own diagnostic: like [`check_source_nesting`], this returns `Ok`
/// at the first lexical error and leaves it to the parser. The message never
/// renders the label: a string-literal name can hold bytes that are not valid
/// UTF-8 (see `parse_error_message`), so the field is located by its span.
pub(super) fn refuse_record_field_id_overflow(
    text: &str,
    offset: usize,
    source_name: Option<&str>,
    budget: &crate::budget::Budget<'_>,
) -> Result<(), CompileError> {
    enum Frame {
        Record {
            next_id: u64,
            /// At the start of a field: after `{` or `;` at this level.
            at_field_start: bool,
            /// The first token of a field that may be a label, until the
            /// next token says whether it is (`:`) or starts a type.
            pending_label: Option<(Option<u64>, std::ops::Range<usize>)>,
            /// The first field whose id is `u32::MAX`.
            overflow: Option<(u64, std::ops::Range<usize>)>,
        },
        Other,
    }
    let mut frames: Vec<Frame> = Vec::new();
    let mut previous_was_record = false;
    for token in Tokenizer::new(text) {
        budget
            .checkpoint()
            .map_err(|error| budget_error(error, DiagnosticPhase::Parse, "source preflight"))?;
        let (start, token, end) = match token {
            Ok(token) => token,
            Err(_) => return Ok(()),
        };
        // Resolve a pending label at the token after it.
        if let Some(Frame::Record {
            next_id,
            pending_label,
            overflow,
            ..
        }) = frames.last_mut()
        {
            if let Some((label_id, range)) = pending_label.take() {
                let id = match (token == Token::Colon, label_id) {
                    (true, Some(id)) => Some(id),
                    // A label out of `u32` range: upstream reports it.
                    (true, None) => None,
                    // Not a label: the field is unnamed.
                    (false, _) => Some(*next_id),
                };
                if let Some(id) = id {
                    if id == u64::from(u32::MAX) && overflow.is_none() {
                        *overflow = Some((id, range));
                    }
                    *next_id = id.saturating_add(1);
                }
            }
        }
        if let Some(Frame::Record {
            at_field_start,
            pending_label,
            next_id,
            overflow,
        }) = frames.last_mut()
        {
            if *at_field_start && !matches!(token, Token::Semi | Token::RBrace) {
                *at_field_start = false;
                let label_id = match &token {
                    Token::Decimal(digits) => Some(digits.parse::<u32>().ok().map(u64::from)),
                    Token::Hex(digits) => Some(u32::from_str_radix(digits, 16).ok().map(u64::from)),
                    Token::Id(name) | Token::Text(name) => {
                        Some(Some(u64::from(crate::name_hash::candid_name_hash(name))))
                    }
                    _ => None,
                };
                match label_id {
                    Some(label_id) => *pending_label = Some((label_id, start..end)),
                    None => {
                        let id = *next_id;
                        if id == u64::from(u32::MAX) && overflow.is_none() {
                            *overflow = Some((id, start..end));
                        }
                        *next_id = id.saturating_add(1);
                    }
                }
            }
        }
        match token {
            Token::LBrace if previous_was_record => frames.push(Frame::Record {
                next_id: 0,
                at_field_start: true,
                pending_label: None,
                overflow: None,
            }),
            Token::LBrace | Token::LParen => frames.push(Frame::Other),
            Token::RBrace | Token::RParen => {
                if let Some(Frame::Record {
                    overflow: Some((id, range)),
                    ..
                }) = frames.pop()
                {
                    let start = range.start.saturating_add(offset);
                    let end = range.end.saturating_add(offset);
                    let mut diagnostic = Diagnostic::compiler(
                        "did_parse_error",
                        DiagnosticPhase::Parse,
                        format!(
                            "Candid parser error: record field id {id} is not supported at bytes {start}..{end}; \
                             the pinned candid_parser cannot number a record field after it"
                        ),
                    );
                    diagnostic.span = Some(SourceSpan::exact(
                        source_name.map(str::to_string),
                        start as u64,
                        end as u64,
                    ));
                    return Err(CompileError {
                        diagnostics: vec![diagnostic],
                    });
                }
            }
            Token::Semi => {
                if let Some(Frame::Record { at_field_start, .. }) = frames.last_mut() {
                    *at_field_start = true;
                }
            }
            _ => {}
        }
        previous_was_record = token == Token::Record;
    }
    Ok(())
}

/// Count consecutive comments between two real tokens, without recursion and
/// without the upstream tokenizer.
///
/// Returns `Ok(longest)`, the longest run in `text`, when no run exceeds
/// `limit`, and `Err(limit + 1)` at the first comment that does: like the
/// structural count, the refusal reports the count at which the limit was
/// crossed, and the scan stops there.
///
/// It reads the bytes with the lexical facts the pinned upstream `Token`
/// encodes, and no others:
///
/// - `//` opens a line comment that ends at the next `\n` (one comment);
/// - `/*` opens a block comment that nests and ends at its matching `*/`
///   (one comment however deeply it nests; an unclosed one still counts,
///   since upstream reports it from the frame that opened it);
/// - `"` opens a string that ends at the next `"` not consumed by a `\`
///   escape, and nothing inside it is a comment;
/// - space, tab, `\r` and `\n` are skipped and leave the run as it is, so
///   blank lines between comments do not end a run;
/// - every other byte starts a token or a lexical error, and either one makes
///   upstream return instead of recursing, so it ends the run.
///
/// Where a malformed source makes these rules and upstream disagree, the
/// disagreement starts at a lexical error, and both the parser and the token
/// loop stop at the first lexical error, so nothing after it is ever
/// tokenized. Linear in `text.len()`, constant stack, no allocation; it takes
/// no budget checkpoint of its own, being one pass over a source that
/// `max_source_bytes` has already bounded.
pub(super) fn comment_run_preflight(text: &[u8], limit: usize) -> Result<usize, usize> {
    let mut index = 0;
    let mut run = 0usize;
    let mut longest = 0usize;
    while let Some(&byte) = text.get(index) {
        match (byte, text.get(index + 1)) {
            (b' ' | b'\t' | b'\r' | b'\n', _) => index += 1,
            (b'/', Some(b'/' | b'*')) => {
                run += 1;
                if run > limit {
                    return Err(run);
                }
                longest = longest.max(run);
                let block = text[index + 1] == b'*';
                index += 2;
                if block {
                    let mut depth = 1usize;
                    while let Some(&byte) = text.get(index) {
                        match (byte, text.get(index + 1)) {
                            (b'/', Some(b'*')) => {
                                depth += 1;
                                index += 2;
                            }
                            (b'*', Some(b'/')) => {
                                depth -= 1;
                                index += 2;
                                if depth == 0 {
                                    break;
                                }
                            }
                            _ => index += 1,
                        }
                    }
                } else {
                    index = text[index..]
                        .iter()
                        .position(|&byte| byte == b'\n')
                        .map_or(text.len(), |offset| index + offset);
                }
            }
            (b'"', _) => {
                run = 0;
                index += 1;
                while let Some(&byte) = text.get(index) {
                    match byte {
                        b'\\' => index += 2,
                        b'"' => {
                            index += 1;
                            break;
                        }
                        _ => index += 1,
                    }
                }
            }
            _ => {
                run = 0;
                index += 1;
            }
        }
    }
    Ok(longest)
}

/// Charge one traversal step of the `max_type_depth` guard walks against the
/// shared `type_preflight_work` counter, so both depth guards fail closed and
/// stay interruptible on a budget with no deadline configured (issue #125).
pub(super) fn charge_type_preflight(
    budget: &mut crate::budget::Budget<'_>,
    limit: usize,
    amount: usize,
    phase: DiagnosticPhase,
    operation: &str,
) -> Result<(), CompileError> {
    budget
        .charge("type_preflight_work", limit, amount)
        .map(|_| ())
        .map_err(|error| budget_error(error, phase, operation))
}

/// The recursive declarations active on one expansion path, as interned
/// indices.
///
/// Shared rather than copied. A record or variant pushes one child state per
/// field and every one of them inherits the parent's set unchanged, so
/// copying would allocate `fields * set` entries in a single loop iteration —
/// *before* any of those children is popped and charged. That burst is
/// attacker-controlled on both factors (field count and cycle length) and the
/// parent's own charge does not cover it, which is the whole failure mode
/// `type_preflight_work` exists to prevent. Sharing means a child costs a
/// reference-count bump, so the memory a state can commit before its charge
/// is a constant.
///
/// The set is rebuilt only by [`ActiveNames::with`], on the one transition
/// that changes it — entering a recursive name — and that copy is bounded by
/// the charge already paid for the state making it.
#[derive(Clone, Default, PartialEq, Eq, PartialOrd, Ord)]
pub(super) struct ActiveNames(std::rc::Rc<BTreeSet<usize>>);

impl ActiveNames {
    pub(super) fn contains(&self, index: &usize) -> bool {
        self.0.contains(index)
    }

    pub(super) fn len(&self) -> usize {
        self.0.len()
    }

    /// This set plus `index`, as a new set. The only allocating operation.
    pub(super) fn with(&self, index: usize) -> Self {
        let mut next = (*self.0).clone();
        next.insert(index);
        Self(std::rc::Rc::new(next))
    }
}

/// Nodes of a directed graph that lie on at least one cycle: members of a
/// strongly connected component of size two or more, plus self-loops.
///
/// Iterative Kosaraju, because this runs on untrusted declaration graphs and
/// must not recurse. Nodes are dense indices `0..node_count`; both DFS passes
/// use explicit stacks and cost `O(node_count + edges.len())`, which the
/// caller has already charged by metering the walk that produced `edges`.
pub(super) fn cyclic_nodes(node_count: usize, edges: &[(usize, usize)]) -> Vec<bool> {
    let mut forward = vec![Vec::new(); node_count];
    let mut reverse = vec![Vec::new(); node_count];
    let mut cyclic = vec![false; node_count];
    for &(from, to) in edges {
        if from == to {
            cyclic[from] = true;
        } else {
            forward[from].push(to);
            reverse[to].push(from);
        }
    }

    let mut visited = vec![false; node_count];
    let mut order = Vec::with_capacity(node_count);
    for root in 0..node_count {
        if visited[root] {
            continue;
        }
        visited[root] = true;
        let mut stack = vec![(root, 0usize)];
        while let Some(&(node, next)) = stack.last() {
            if let Some(&child) = forward[node].get(next) {
                stack.last_mut().expect("frame just read").1 += 1;
                if !visited[child] {
                    visited[child] = true;
                    stack.push((child, 0));
                }
            } else {
                order.push(node);
                stack.pop();
            }
        }
    }

    let mut component = vec![usize::MAX; node_count];
    let mut component_size = Vec::new();
    for &root in order.iter().rev() {
        if component[root] != usize::MAX {
            continue;
        }
        let id = component_size.len();
        component_size.push(0usize);
        component[root] = id;
        let mut stack = vec![root];
        while let Some(node) = stack.pop() {
            component_size[id] += 1;
            for &previous in &reverse[node] {
                if component[previous] == usize::MAX {
                    component[previous] = id;
                    stack.push(previous);
                }
            }
        }
    }

    for node in 0..node_count {
        if component_size[component[node]] >= 2 {
            cyclic[node] = true;
        }
    }
    cyclic
}

/// Declarations that participate in a reference cycle, each mapped to a dense
/// index.
///
/// A name outside every cycle can never repeat on one expansion path, so the
/// depth walk need not track it in its per-path active set. That keeps active
/// sets to the (small, usually empty) recursive core, which is what lets
/// identical expansion states deduplicate instead of re-expanding a shared
/// subtree once per incoming edge.
///
/// The walk tracks the *index*, never the name. `type_preflight_work` charges
/// one unit per tracked name, so every operation that unit pays for has to
/// cost the same whatever the name is: comparing indices is a machine-word
/// compare, while comparing identifiers walks their bytes, and a Candid
/// identifier is bounded on this path only by `max_source_bytes`. Set
/// membership and the memo's ordering comparisons are both on this key, so
/// interning is what keeps the advertised bound covering the real cost rather
/// than a fixed multiple of an attacker-chosen length.
fn recursive_declaration_names<'a>(
    declarations: &BTreeMap<&'a str, &'a IDLType>,
    max_work: usize,
    budget: &mut crate::budget::Budget<'_>,
) -> Result<BTreeMap<&'a str, usize>, CompileError> {
    let names: Vec<&str> = declarations.keys().copied().collect();
    let index_of: BTreeMap<&str, usize> = names
        .iter()
        .enumerate()
        .map(|(index, name)| (*name, index))
        .collect();
    let mut edges = Vec::new();
    for (name, ty) in declarations {
        let from = index_of[name];
        let mut stack: Vec<&IDLType> = vec![ty];
        while let Some(ty) = stack.pop() {
            charge_type_preflight(
                budget,
                max_work,
                1,
                DiagnosticPhase::TypeCheck,
                "type-depth preflight",
            )?;
            match ty {
                IDLType::VarT(target) => {
                    if let Some(&to) = index_of.get(target.as_str()) {
                        edges.push((from, to));
                    }
                }
                IDLType::OptT(inner) | IDLType::VecT(inner) => stack.push(inner),
                IDLType::RecordT(fields) | IDLType::VariantT(fields) => {
                    stack.extend(fields.iter().map(|field| &field.typ));
                }
                IDLType::FuncT(function) => {
                    stack.extend(function.args.iter().chain(&function.rets).map(|ty| &ty.typ));
                }
                IDLType::ServT(methods) => {
                    stack.extend(methods.iter().map(|method| &method.typ));
                }
                IDLType::ClassT(init, service) => {
                    stack.push(service);
                    stack.extend(init.iter().map(|ty| &ty.typ));
                }
                IDLType::PrimT(_) | IDLType::PrincipalT => {}
            }
        }
    }
    let cyclic = cyclic_nodes(names.len(), &edges);
    Ok(names
        .into_iter()
        .zip(&cyclic)
        .filter(|(_, &in_cycle)| in_cycle)
        .enumerate()
        .map(|(index, (name, _))| (name, index))
        .collect())
}

/// Follow parsed declaration references across the complete resolved bundle
/// with an explicit stack before the upstream checker can recursively expand
/// a long chain of shallow aliases.
///
/// The walk is exact — the same states are refused at the same depths as a
/// full path-sensitive expansion — but shared subtrees are visited once per
/// distinct `(node, depth, active recursive names)` state rather than once
/// per path, and every state is charged against `type_preflight_work`, so a
/// record DAG with shared aliases costs linear work instead of O(2^n) and an
/// input that defeats deduplication fails closed instead of hanging
/// (issue #125).
pub(super) fn check_programs_type_depth<'a>(
    programs: impl IntoIterator<Item = &'a IDLProg>,
    budget: &mut crate::budget::Budget<'_>,
) -> Result<(), CompileError> {
    let limits = budget.limits().clone();
    let programs: Vec<_> = programs.into_iter().collect();
    let mut declarations = BTreeMap::new();
    for program in &programs {
        for declaration in &program.decs {
            if let Dec::TypD(binding) = declaration {
                declarations
                    .entry(binding.id.as_str())
                    .or_insert(&binding.typ);
            }
        }
    }
    let max_work = limits.max_type_preflight_work;
    let recursive = recursive_declaration_names(&declarations, max_work, budget)?;
    let mut pending: Vec<_> = declarations
        .values()
        .copied()
        .chain(
            programs
                .iter()
                .filter_map(|program| program.actor.as_ref().map(|actor| &actor.typ)),
        )
        .map(|ty| (ty, 0usize, ActiveNames::default()))
        .collect();

    let mut visited = BTreeSet::new();
    while let Some((ty, depth, active_names)) = pending.pop() {
        // One unit per state plus one per tracked recursive name: cloning and
        // comparing the path set below is what the extra units pay for.
        charge_type_preflight(
            budget,
            max_work,
            1usize.saturating_add(active_names.len()),
            DiagnosticPhase::TypeCheck,
            "type-depth preflight",
        )?;
        if depth > limits.max_type_depth {
            return Err(CompileError::resource_limit(
                "type_depth",
                limits.max_type_depth,
                depth,
                format!(
                    "Candid type depth {depth} exceeds limit {}",
                    limits.max_type_depth
                ),
            ));
        }
        if !visited.insert((ty as *const IDLType as usize, depth, active_names.clone())) {
            continue;
        }
        let next_depth = depth.saturating_add(1);
        match ty {
            IDLType::VarT(name) => {
                if let Some(resolved) = declarations.get(name.as_str()).copied() {
                    let recursive_index = recursive.get(name.as_str()).copied();
                    if !recursive_index.is_some_and(|index| active_names.contains(&index)) {
                        let next_names = match recursive_index {
                            // The one place the set actually changes, so the
                            // one place it is rebuilt. That copy is O(set),
                            // and this state's own charge already covered it.
                            Some(index) => active_names.with(index),
                            // A name outside every cycle cannot repeat on
                            // this path, so tracking it would only split
                            // otherwise-identical states.
                            None => active_names,
                        };
                        pending.push((resolved, depth, next_names));
                    }
                }
            }
            IDLType::OptT(inner) | IDLType::VecT(inner) => {
                pending.push((inner, next_depth, active_names));
            }
            IDLType::RecordT(fields) | IDLType::VariantT(fields) => {
                for field in fields {
                    pending.push((&field.typ, next_depth, active_names.clone()));
                }
            }
            IDLType::FuncT(function) => {
                for ty in function.args.iter().chain(&function.rets) {
                    pending.push((&ty.typ, next_depth, active_names.clone()));
                }
            }
            IDLType::ServT(methods) => {
                for method in methods {
                    pending.push((&method.typ, next_depth, active_names.clone()));
                }
            }
            IDLType::ClassT(init, service) => {
                pending.push((service, next_depth, active_names.clone()));
                for ty in init {
                    pending.push((&ty.typ, next_depth, active_names.clone()));
                }
            }
            IDLType::PrimT(_) | IDLType::PrincipalT => {}
        }
    }
    Ok(())
}

#[cfg(test)]
mod preflight_tests {
    use super::*;
    use crate::budget::Budget;
    use crate::Limits;

    fn preflight_work(source: &str) -> usize {
        let limits = Limits::default();
        let mut budget = Budget::from_limits(&limits);
        let program: IDLProg = source.parse().unwrap();
        check_programs_type_depth(std::iter::once(&program), &mut budget).unwrap();
        budget.consumed("type_preflight_work")
    }

    fn shared_fanout(levels: usize) -> String {
        let mut source = String::new();
        for index in 1..=levels {
            source.push_str(&format!(
                "type T{index} = record {{ a: T{}; b: T{} }};\n",
                index + 1,
                index + 1
            ));
        }
        source.push_str(&format!("type T{} = nat;\n", levels + 1));
        source.push_str("service : { go: (T1) -> () };");
        source
    }

    fn longest_comment_run(text: &str) -> usize {
        comment_run_preflight(text.as_bytes(), usize::MAX).unwrap()
    }

    /// Issue #219's counting rules: comments between two real tokens, line
    /// and block alike.
    #[test]
    fn comment_runs_count_line_and_block_comments_between_real_tokens() {
        assert_eq!(longest_comment_run(""), 0);
        assert_eq!(longest_comment_run("type T = nat;"), 0);
        assert_eq!(longest_comment_run("//\n//\n//\n"), 3);
        assert_eq!(longest_comment_run("// a\n// b\ntype T = nat;"), 2);
        // Trailing comments recurse upstream as much as leading ones.
        assert_eq!(longest_comment_run("type T = nat;\n// a\n// b\n// c"), 3);
        // Alternating line and block comments count both.
        assert_eq!(longest_comment_run("// a\n/* b */\n// c\n/* d */ x"), 4);
        assert_eq!(longest_comment_run("/* a *//* b *//* c */"), 3);
        // A real token resets the run; the longest run wins.
        assert_eq!(longest_comment_run("// a\n// b\nx\n// c\ny"), 2);
        assert_eq!(longest_comment_run("// a\nx // b\n// c\n// d\n"), 3);
        // Any byte that is not trivia starts a token or a lexical error, and
        // upstream returns on either, so it resets too.
        assert_eq!(longest_comment_run("// a\n@\n// b"), 1);
        assert_eq!(longest_comment_run("// a\n/ // b"), 1);
    }

    #[test]
    fn comment_runs_ignore_whitespace_nesting_and_string_contents() {
        // Blank lines and spaces neither count nor end a run.
        assert_eq!(longest_comment_run(&"\n".repeat(10_000)), 0);
        assert_eq!(longest_comment_run("// a\n\n\n   \t\r\n// b\n"), 2);
        // A line comment ends only at `\n`, as upstream's `//[^\n]*` does: a
        // bare `\r` (old Mac line endings) is part of the comment, so this
        // is one comment, while CRLF endings end each line comment.
        assert_eq!(longest_comment_run("// a\r// b\r// c"), 1);
        assert_eq!(longest_comment_run("// a\r\n// b\r\n"), 2);
        assert_eq!(longest_comment_run("// a\r\n// b\r\n// c\r\n"), 3);
        // `\r` and `\t` between block comments are whitespace.
        assert_eq!(longest_comment_run("/**/\r/**/\t/**/"), 3);
        // Non-ASCII bytes inside a comment or a string are its contents;
        // outside both they begin a token (or a lexical error) and reset.
        assert_eq!(longest_comment_run("// \u{e9}\n/* \u{1f600} */ // b"), 3);
        assert_eq!(longest_comment_run("\"\u{e9} // a\" x"), 0);
        assert_eq!(longest_comment_run("// a\n\u{e9}\n// b"), 1);
        // A nested block comment is one comment, however deep.
        assert_eq!(longest_comment_run("/* /* /* */ */ */"), 1);
        let deep = format!("{}{}", "/*".repeat(10_000), "*/".repeat(10_000));
        assert_eq!(longest_comment_run(&deep), 1);
        // Comment markers inside a block comment are its contents.
        assert_eq!(longest_comment_run("/* // */ x"), 1);
        assert_eq!(longest_comment_run("/* \" */ // b\n"), 2);
        // Block markers inside a line comment are its contents.
        assert_eq!(longest_comment_run("// /* \n x"), 1);
        // Comment markers inside a string count as nothing, and the string
        // is a real token.
        assert_eq!(longest_comment_run(r#""// /* */""#), 0);
        assert_eq!(longest_comment_run("// a\n\"//\"\n// b"), 1);
        // An escaped quote does not end the string; an escaped backslash
        // does not escape the quote after it.
        assert_eq!(longest_comment_run(r#""\" // a" x"#), 0);
        assert_eq!(longest_comment_run(r#""\\" // a"#), 1);
    }

    /// The edges where the upstream comment lexer's one-character error
    /// skipping decides the nesting: `//*` inside a block opens a level,
    /// `**/` closes one, and an unclosed block comment still counts.
    #[test]
    fn comment_runs_follow_the_upstream_block_comment_lexer() {
        assert_eq!(longest_comment_run("/* //* */ */ // a"), 2);
        assert_eq!(longest_comment_run("/* **/ // a"), 2);
        assert_eq!(longest_comment_run("/*/ x */ // a"), 2);
        assert_eq!(longest_comment_run("/**/ /***/ // a"), 3);
        assert_eq!(longest_comment_run("// a\n/* never closed // b"), 2);
        assert_eq!(longest_comment_run("x \"never closed // a"), 0);
    }

    #[test]
    fn comment_run_refusal_reports_the_crossing_count() {
        let run = "//\n".repeat(10);
        assert_eq!(comment_run_preflight(run.as_bytes(), 10), Ok(10));
        assert_eq!(comment_run_preflight(run.as_bytes(), 9), Err(10));
        assert_eq!(comment_run_preflight(run.as_bytes(), 3), Err(4));
        // Zero is a defined policy: any comment at all exceeds it.
        assert_eq!(comment_run_preflight(b"type T = nat;", 0), Ok(0));
        assert_eq!(comment_run_preflight(b"// a", 0), Err(1));
    }

    /// The scan against the pinned upstream lexer itself, over every source
    /// of up to seven bytes drawn from the lexically significant alphabet
    /// that upstream tokenizes without error: the longest run the scan
    /// reports equals the most comments upstream skips between two of the
    /// tokens it returns. The alphabet holds `\r` and `\t` as well as `\n`
    /// and space, so a scan that ended a line comment at a bare `\r`, or
    /// treated either as anything but whitespace, disagrees here.
    #[test]
    fn comment_runs_agree_with_the_upstream_tokenizer() {
        const ALPHABET: &[u8] = b"/*\"\\\n\r\t a";
        fn gap_comments(gap: &str) -> usize {
            let (mut rest, mut longest) = (gap, 0);
            loop {
                rest = rest.trim_start_matches([' ', '\t', '\r', '\n']);
                if rest.is_empty() {
                    return longest;
                }
                longest += 1;
                if let Some(line) = rest.strip_prefix("//") {
                    rest = line.find('\n').map_or("", |end| &line[end..]);
                } else {
                    let mut body = rest.strip_prefix("/*").expect("a gap holds only comments");
                    let mut depth = 1;
                    while depth > 0 {
                        let open = body.find("/*");
                        let close = body.find("*/").expect("a valid gap closes its comments");
                        if open.is_some_and(|open| open < close) {
                            depth += 1;
                            body = &body[open.unwrap() + 2..];
                        } else {
                            depth -= 1;
                            body = &body[close + 2..];
                        }
                    }
                    rest = body;
                }
            }
        }
        let mut compared = 0usize;
        let mut text = Vec::new();
        for length in 0..=7u32 {
            for mut code in 0..ALPHABET.len().pow(length) {
                text.clear();
                for _ in 0..length {
                    text.push(ALPHABET[code % ALPHABET.len()]);
                    code /= ALPHABET.len();
                }
                let source = std::str::from_utf8(&text).unwrap();
                let Ok(tokens) = Tokenizer::new(source).collect::<Result<Vec<_>, _>>() else {
                    continue;
                };
                let mut expected = 0;
                let mut gap_start = 0;
                for (start, _, end) in &tokens {
                    expected = expected.max(gap_comments(&source[gap_start..*start]));
                    gap_start = *end;
                }
                expected = expected.max(gap_comments(&source[gap_start..]));
                assert_eq!(longest_comment_run(source), expected, "{source:?}");
                compared += 1;
            }
        }
        // The corpus is not vacuous: this many sources lex cleanly.
        assert_eq!(compared, 392_192);
    }

    #[test]
    fn cyclic_nodes_marks_self_loops_and_cycle_members_only() {
        // A chain is acyclic.
        assert_eq!(cyclic_nodes(3, &[(0, 1), (1, 2)]), [false, false, false]);
        // A self-loop is a cycle of one.
        assert_eq!(cyclic_nodes(2, &[(0, 0), (0, 1)]), [true, false]);
        // A two-cycle with a tail: the tail stays acyclic.
        assert_eq!(
            cyclic_nodes(3, &[(0, 1), (1, 0), (1, 2)]),
            [true, true, false]
        );
        // Diamond with a back edge: 0→1→3, 0→2→3, 3→0. Every node lies on a
        // cycle — including 2, which naive back-edge marking of the DFS stack
        // misses because 2→3 is a cross edge to a finished node.
        assert_eq!(
            cyclic_nodes(4, &[(0, 1), (0, 2), (1, 3), (2, 3), (3, 0)]),
            [true, true, true, true]
        );
        // Duplicate edges do not fabricate a cycle.
        assert_eq!(cyclic_nodes(2, &[(0, 1), (0, 1)]), [false, false]);
    }

    /// Pins the charge model on a minimal program: one unit per
    /// recursion-map node (the `nat` body), then one per expansion state —
    /// the actor service, its method's func, the argument `VarT`, the
    /// resolved `nat`, and the declaration walked as its own root.
    #[test]
    fn minimal_program_charges_exactly_six_units() {
        assert_eq!(
            preflight_work("type T = nat; service : { f: (T) -> () };"),
            6
        );
    }

    /// Only names on a cycle are tracked per path, at one extra unit per
    /// state inside their expansion; sibling references to the recursive
    /// name still deduplicate.
    #[test]
    fn recursive_names_cost_one_extra_unit_per_state_inside_their_expansion() {
        assert_eq!(
            preflight_work("type L = opt L; type M = record { a: L; b: L }; service : {};"),
            19
        );
    }

    /// The issue #125 regression at the unit level: 2^24 states would dwarf
    /// any of these numbers.
    ///
    /// What remains grows about quadratically in the number of nested record
    /// levels, because each level adds a depth at which the shared tail is a
    /// distinct state. That factor is bounded by `max_type_depth`, since a
    /// level that does not add depth cannot add a depth to be distinct at —
    /// which is why a pure alias chain, below, is flatly linear.
    #[test]
    fn shared_subtrees_deduplicate_instead_of_doubling_per_level() {
        assert_eq!(preflight_work(&shared_fanout(6)), 138);
        assert_eq!(preflight_work(&shared_fanout(12)), 414);
        assert_eq!(preflight_work(&shared_fanout(24)), 1_398);
    }

    /// Aliases add no depth, so every reference to the chain's tail is the
    /// same `(node, depth, active names)` state and each declaration root
    /// contributes a constant: exactly four units per declaration, with no
    /// dependence on how many roots re-enter the chain. This is the linear
    /// bound issue #125 asks the guard to restore — the un-deduplicated walk
    /// re-walked the whole tail once per root.
    #[test]
    fn alias_chains_cost_a_constant_per_declaration() {
        let alias_chain = |length: usize| {
            let mut source = String::new();
            for index in 1..length {
                source.push_str(&format!("type A{index} = A{};\n", index + 1));
            }
            source.push_str(&format!("type A{length} = nat;\n"));
            source.push_str("service : { f: (A1) -> () };");
            source
        };
        assert_eq!(preflight_work(&alias_chain(100)), 402);
        assert_eq!(preflight_work(&alias_chain(500)), 2_002);
        assert_eq!(preflight_work(&alias_chain(1_000)), 4_002);
        assert_eq!(preflight_work(&alias_chain(2_000)), 8_002);
    }
}