zincite_syntax/

lib.rs

//! Source-preserving syntax for MiniZinc 2.10.1.
//!
//! Lexing retains trivia and erroneous input. It does not check model or data
//! grammar, resolve names, or evaluate literals. Interpolated strings retain
//! literal chunks and embedded expression tokens in the same source buffer.
//! Parsing supports scalar and ordinary collection declarations, domains,
//! indexed and matrix literals, dependent indices, cardinalities, array access,
//! operator expressions, calls, interpolated strings, annotations, constraints
//! with optional string labels, comprehensions, generator calls, conditional and let
//! expressions, callable/annotation declarations with generic types and parameter
//! defaults, enums and constructors, type aliases and type-inst concatenation,
//! includes, output items and all solve modes.
//! Compiler-supported extensions include deprecated function declarations without
//! `function`, anonymous `_(expression)` constructors in assignments, identifier
//! equality items without `constraint`, and predicate `ann: name` capture bindings.
//! These retain their written tokens and expose ordinary callable, call and
//! constraint nodes, plus a distinct annotation-capture binding in the signature.
//! Tuple/record types and literals and chained field access share the CST.
//! Data mode accepts only top-level assignments. Reserved variant_record/case
//! syntax remains unsupported.

use std::ops::Range;
use std::path::Path;
use std::sync::OnceLock;

mod bytes;
pub mod inputs;
mod lexer;
mod parser;

pub use bytes::{
    ByteParsedFile, byte_line_column, is_utf8_boundary, parse_bytes, parse_bytes_with_mode,
};

/// Parse the supported model subset, retaining all tokens even after an error.
///
/// This checks syntax only: it does not resolve names, require a solve item, or
/// check types. Unsupported syntax produces diagnostics rather than opaque items.
pub fn parse(source: impl Into<String>) -> ParsedFile {
    parse_with_mode(source, FileMode::Model)
}

/// The syntax permitted at the top level of a source file.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum FileMode {
    Model,
    Data,
}

impl FileMode {
    /// `.dzn` selects data syntax case-insensitively; other paths use model syntax.
    pub fn from_path(path: impl AsRef<Path>) -> Self {
        if path
            .as_ref()
            .extension()
            .and_then(|ext| ext.to_str())
            .is_some_and(|ext| ext.eq_ignore_ascii_case("dzn"))
        {
            Self::Data
        } else {
            Self::Model
        }
    }
}

/// Parse model syntax or assignment-only data syntax without resolving names.
/// Calls in data expressions are retained: determining whether an operation is
/// user-defined requires the model and is outside syntax checking.
pub fn parse_with_mode(source: impl Into<String>, mode: FileMode) -> ParsedFile {
    parse_lexed(lex(source), mode)
}

/// Parse FlatZinc text with its broader variable names and string escapes.
/// The shared CST supplies syntax; callers validate the FlatZinc item grammar.
/// Model parsing continues to treat `_` as an anonymous variable.
pub fn parse_flatzinc(source: impl Into<String>, mode: FileMode) -> ParsedFile {
    let source = source.into();
    let (tokens, diagnostics) = lexer::scan_flatzinc(&source);
    parse_lexed(
        LexedSource {
            source,
            tokens,
            diagnostics,
        },
        mode,
    )
}

fn parse_lexed(mut lexed: LexedSource, mode: FileMode) -> ParsedFile {
    // Finish large token buffers before constructing the CST. Small files keep
    // their existing allocation path; token indices and owned source stay exact.
    if lexed.tokens.len() >= 65_536 {
        lexed.tokens.shrink_to_fit();
    }
    let (tree, diagnostics) = parser::parse(&lexed.tokens, &lexed.source, mode);
    lexed.diagnostics.extend(diagnostics);
    ParsedFile {
        lexed,
        tree,
        line_positions: OnceLock::new(),
    }
}

/// Owned source, its lossless tree, and lexical/parser diagnostics.
#[derive(Debug)]
pub struct ParsedFile {
    lexed: LexedSource,
    tree: SyntaxNode,
    line_positions: OnceLock<LinePositions>,
}

#[derive(Debug)]
struct LinePositions {
    starts: Vec<usize>,
    utf8_extra_bytes: Vec<(usize, usize)>,
}

impl ParsedFile {
    pub fn source(&self) -> &str {
        self.lexed.source()
    }

    /// Return the one-based line and Unicode scalar column at a byte offset.
    /// CR and LF each end a line; CRLF is one break, including an offset between
    /// its two bytes. Line boundaries are indexed on demand and owned by this
    /// parsed source. Parsing or formatting alone does not build them.
    ///
    /// Panics if the offset exceeds the source length or is not a UTF-8 boundary,
    /// just as slicing the source at that offset does.
    pub fn line_column(&self, byte_offset: usize) -> (usize, usize) {
        let source = self.source();
        let prefix = &source[..byte_offset];
        if byte_offset == 0 {
            return (1, 1);
        }
        let positions = self.line_positions.get_or_init(|| {
            let mut starts = vec![0];
            let mut utf8_extra_bytes = Vec::new();
            let mut extra_bytes = 0;
            let bytes = source.as_bytes();
            for (index, character) in source.char_indices() {
                if character == '\r'
                    || (character == '\n' && (index == 0 || bytes[index - 1] != b'\r'))
                {
                    starts.push(index + 1);
                }
                let width = character.len_utf8();
                if width > 1 {
                    extra_bytes += width - 1;
                    utf8_extra_bytes.push((index + width, extra_bytes));
                }
            }
            LinePositions {
                starts,
                utf8_extra_bytes,
            }
        });
        let line = positions
            .starts
            .partition_point(|&start| start <= prefix.len());
        let mut start = positions.starts[line - 1];
        // A CR already counts as a break before its following LF is consumed.
        if start < byte_offset
            && start > 0
            && source.as_bytes()[start - 1] == b'\r'
            && source.as_bytes()[start] == b'\n'
        {
            start += 1;
        }
        let extra_bytes_at = |offset| {
            let count = positions
                .utf8_extra_bytes
                .partition_point(|&(end, _)| end <= offset);
            positions.utf8_extra_bytes[..count]
                .last()
                .map_or(0, |&(_, extra)| extra)
        };
        let column =
            byte_offset - start - (extra_bytes_at(byte_offset) - extra_bytes_at(start)) + 1;
        (line, column)
    }

    pub fn tokens(&self) -> &[Token] {
        self.lexed.tokens()
    }

    pub fn tree(&self) -> &SyntaxNode {
        &self.tree
    }

    pub fn diagnostics(&self) -> &[Diagnostic] {
        self.lexed.diagnostics()
    }
}

/// A node's children retain source order. Each token occurs in exactly one leaf.
#[derive(Debug)]
pub struct SyntaxNode {
    data: Box<NodeData>,
}

#[derive(Debug)]
struct NodeData {
    kind: NodeKind,
    range: Range<usize>,
    children: NodeChildren,
}

enum NodeChildren {
    One(SyntaxElement),
    Slice(Box<[SyntaxElement]>),
}

impl NodeChildren {
    fn as_slice(&self) -> &[SyntaxElement] {
        match self {
            Self::One(child) => std::slice::from_ref(child),
            Self::Slice(children) => children,
        }
    }
}

impl std::fmt::Debug for NodeChildren {
    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        std::fmt::Debug::fmt(self.as_slice(), formatter)
    }
}

impl SyntaxNode {
    fn new(kind: NodeKind, range: Range<usize>, children: Box<[SyntaxElement]>) -> Self {
        Self {
            data: Box::new(NodeData {
                kind,
                range,
                children: NodeChildren::Slice(children),
            }),
        }
    }

    fn with_child(kind: NodeKind, range: Range<usize>, child: SyntaxElement) -> Self {
        Self {
            data: Box::new(NodeData {
                kind,
                range,
                children: NodeChildren::One(child),
            }),
        }
    }

    pub fn kind(&self) -> NodeKind {
        self.data.kind
    }

    pub fn range(&self) -> Range<usize> {
        self.data.range.clone()
    }

    pub fn children(&self) -> &[SyntaxElement] {
        self.data.children.as_slice()
    }

    /// Borrow the direct child nodes in source order, excluding token leaves.
    pub fn child_nodes(&self) -> impl Iterator<Item = &SyntaxNode> {
        self.children().iter().filter_map(|child| match child {
            SyntaxElement::Node(node) => Some(node),
            SyntaxElement::Token(_) => None,
        })
    }
}

#[derive(Debug)]
pub enum SyntaxElement {
    Node(SyntaxNode),
    /// Index into the parse result's retained token buffer.
    Token(usize),
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum NodeKind {
    Root,
    /// Direct name token, annotations, and an optional EnumDefinition child.
    EnumDeclaration,
    /// Direct name token, annotations, and the target type child.
    TypeAlias,
    /// Ordered case lists and constructors, separated by written `++` tokens.
    EnumDefinition,
    /// Braces containing EnumCase children in written order.
    EnumCases,
    /// The direct identifier token declares an enum member.
    EnumCase,
    /// A direct declaration name (or anonymous `_`) and a parenthesized expression.
    EnumConstructor,
    /// Left type and right base type, separated by a written `++` token.
    TypeInstConcatenation,
    /// The first child node is the type; later nodes are annotations/initializer.
    Declaration,
    /// Return type child, direct name token, and optional parameter list,
    /// annotations and body expression. Deprecated omitted-keyword declarations
    /// contain no `function` token.
    FunctionDeclaration,
    /// Direct name token, optional parameter list, annotation capture, annotations and body.
    PredicateDeclaration,
    /// Written `ann`, colon and direct binding name; captures contextual annotations
    /// in a predicate signature, separate from its formal ParameterList.
    AnnotationCapture,
    /// Direct name token, optional parameter list, annotations and body.
    TestDeclaration,
    /// Direct name token, optional parameter list and body; no annotations.
    AnnotationDeclaration,
    /// Parentheses and ordered Parameter children; omitted lists have no node.
    ParameterList,
    /// The type child, optional direct name token, ordered Annotation children,
    /// and optional default expression child. Unnamed parameters contain only a
    /// type; annotations after a default belong to that expression.
    Parameter,
    /// Generic variable spelling, with any/var/par/opt qualifiers retained.
    TypeInstVariable,
    ScalarType,
    /// Ordered type children within written tuple parentheses.
    TupleType,
    /// Ordered RecordField children within written record parentheses.
    RecordType,
    /// Type child and direct declaration name token with its precise range.
    RecordField,
    /// Parentheses and ordered value children; the first comma is required.
    TupleLiteral,
    /// Ordered RecordLiteralField children; the first comma is required.
    RecordLiteral,
    /// Direct field name token and value child; names label values, not declarations.
    RecordLiteralField,
    /// Subject child followed by a dot and direct reference name or integer token.
    FieldAccessExpression,
    /// Contains one domain expression, with any qualifiers retained as tokens.
    DomainType,
    /// Contains an optional cardinality followed by the element type.
    /// Qualifiers and `set of` remain tokens.
    SetType,
    /// Parentheses containing the written cardinality expression.
    SetCardinality,
    /// Child nodes are index types or bindings followed by the element type.
    ArrayType,
    /// Direct tokens retain the binding name and `in`; the child is its index type.
    ArrayIndexBinding,
    /// Contains the element type.
    ListType,
    Assignment,
    /// A keyword/optional label and expression, or a keyword-free identifier equality.
    Constraint,
    /// Contains the written string literal path; no include resolution is performed.
    Include,
    /// Optional direct Annotation child followed by the output expression.
    Output,
    /// A satisfy item, with direct Annotation children and no objective.
    Solve,
    /// Direct Annotation children followed by the minimization objective expression.
    SolveMinimize,
    /// Direct Annotation children followed by the maximization objective expression.
    SolveMaximize,
    /// A literal or identifier atom, including anonymous and absent values.
    Expression,
    /// Exact string chunks alternate with embedded expression child nodes.
    InterpolatedString,
    UnaryExpression,
    BinaryExpression,
    ParenthesizedExpression,
    /// A callable invocation or anonymous `_(expression)` enum constructor.
    CallExpression,
    /// Written call name/header tokens, an ordered generator list, then a
    /// parenthesized body expression.
    GeneratorCallExpression,
    /// Ordered if/elseif branches, an optional else branch, and the endif token.
    ConditionalExpression,
    /// The keyword, condition expression, then token, and body expression.
    ConditionalBranch,
    /// The else token and its body expression.
    ElseBranch,
    /// The let token, local block, in token, and greedy body expression.
    LetExpression,
    /// Ordered Declaration/Constraint children with written separators. Local
    /// declarations expose names and their ranges as direct token leaves, just
    /// like top-level declarations; the first child node is their type.
    LetBlock,
    /// Child nodes are the head expression and ordered generator list.
    SetComprehension,
    ArrayComprehension,
    /// Child nodes are an indexed entry (key/value) and ordered generator list.
    IndexedArrayComprehension,
    /// Child nodes are generators in written order; commas remain token leaves.
    GeneratorList,
    /// Direct tokens retain binding names and `in` or `=`. Child nodes are the
    /// source/value expression followed by an optional attached WhereFilter.
    Generator,
    /// The written `where` token followed by its expression child.
    WhereFilter,
    /// Child nodes are the entries; empty literals have no child nodes.
    SetLiteral,
    /// Child nodes are bare expressions or indexed entries, in written order.
    ArrayLiteral,
    /// Child nodes are the written key and value, separated by a colon token.
    IndexedArrayEntry,
    /// Parenthesized key components; only supported in indexed-entry keys.
    IndexTuple,
    /// Contains an optional column header and rows, with written pipe delimiters.
    MatrixLiteral,
    /// Child nodes are column indices, each followed by a colon token.
    MatrixColumnIndices,
    /// Child nodes are cells, preceded by an index child when a colon is present.
    /// Empty written rows have a zero-width range at their pipe delimiter.
    MatrixRow,
    /// Child nodes are the subject followed by one or more index expressions.
    ArrayAccessExpression,
    NamedArgument,
    AnnotatedExpression,
    /// An annotation marker and its atom; distinct from the annotated subject.
    Annotation,
    /// Children contain the written bounds and marker; either bound may be omitted.
    RangeExpression,
    Error,
}

/// Tokenize an owned UTF-8 source, retaining every byte in source order.
///
/// Tokens have nonempty, contiguous, half-open byte ranges at UTF-8 boundaries.
/// Errors produce diagnostics and retained tokens rather than stopping lexing.
pub fn lex(source: impl Into<String>) -> LexedSource {
    let source = source.into();
    let (tokens, diagnostics) = lexer::scan(&source);
    LexedSource {
        source,
        tokens,
        diagnostics,
    }
}

/// Validate the complete source and return byte ranges of comments and string
/// chunks, including interpolated literals, without retaining every token.
/// Expressions inside interpolation remain editable. Lexical errors, including
/// unterminated interpolation at EOF, reject the complete result.
pub fn lexical_protected_ranges(source: &str) -> Result<Vec<Range<usize>>, Vec<Diagnostic>> {
    lexer::protected_ranges(source)
}

/// Source text and its tokens. Read-only access keeps their ranges valid.
#[derive(Debug)]
pub struct LexedSource {
    source: String,
    tokens: Vec<Token>,
    diagnostics: Vec<Diagnostic>,
}

impl LexedSource {
    pub fn source(&self) -> &str {
        &self.source
    }

    /// Return the owned source, releasing its tokens and diagnostics.
    pub fn into_source(self) -> String {
        self.source
    }

    pub fn tokens(&self) -> &[Token] {
        &self.tokens
    }

    pub fn diagnostics(&self) -> &[Diagnostic] {
        &self.diagnostics
    }
}

/// A source spelling is available by slicing the source with this byte range.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Token {
    pub kind: TokenKind,
    pub range: Range<usize>,
}

/// A lexical/parser error or an explicitly unsupported syntax form.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Diagnostic {
    pub range: Range<usize>,
    pub message: String,
}

/// Lexical distinctions for a parser. Unicode operators share their ASCII
/// equivalent's kind; spelling is always retained in the source.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TokenKind {
    Whitespace,
    LineComment,
    BlockComment,
    Identifier,
    QuotedIdentifier,
    InfixIdentifier,
    TypeInstVariable,
    IntegerLiteral,
    FloatLiteral,
    StringLiteral,
    /// Opening quote, literal contents and the first written `\(` delimiter.
    StringHead,
    /// Written `)`, literal contents and the next written `\(` delimiter.
    StringMiddle,
    /// Written `)`, remaining literal contents and closing quote.
    StringTail,
    Error,

    Ann,
    Annotation,
    Any,
    Array,
    Bool,
    Case,
    Constraint,
    Default,
    Diff,
    Div,
    Else,
    ElseIf,
    EndIf,
    Enum,
    False,
    Float,
    Function,
    If,
    In,
    Include,
    Infinity,
    Int,
    Intersect,
    Let,
    List,
    Maximize,
    Minimize,
    Mod,
    Not,
    Of,
    Opt,
    Output,
    Par,
    Predicate,
    Record,
    Satisfy,
    Set,
    Solve,
    String,
    Subset,
    Superset,
    SymDiff,
    Test,
    Then,
    True,
    Tuple,
    Type,
    Union,
    Var,
    VariantRecord,
    Where,
    Xor,

    LeftParen,
    RightParen,
    LeftBracket,
    RightBracket,
    LeftBrace,
    RightBrace,
    MatrixStart,
    MatrixEnd,
    Comma,
    Colon,
    Semicolon,
    Dot,
    Pipe,
    Anonymous,
    Absent,
    AnnotationMarker,
    Equivalence,
    Implies,
    ReverseImplies,
    Or,
    And,
    Less,
    Greater,
    LessEqual,
    GreaterEqual,
    Equal,
    DoubleEqual,
    NotEqual,
    WeakEqual,
    WeakNotEqual,
    RangeInclusive,
    RangeExclusiveStart,
    RangeExclusiveEnd,
    RangeExclusive,
    Plus,
    Minus,
    Star,
    Slash,
    Power,
    Concat,
    WeakPlus,
    WeakMinus,
    WeakStar,
    WeakSlash,
    WeakDiv,
    /// The Unicode inverse spelling `⁻¹`, equivalent to the sequence `^-1`.
    Inverse,
}

/// Decode a literal include path as bytes without loading files or evaluating
/// interpolations. Unsupported paths return None; source spelling is untouched.
pub fn literal_include_path(parsed: &ParsedFile, item: &SyntaxNode) -> Option<Vec<u8>> {
    if item.kind() != NodeKind::Include {
        return None;
    }
    let path = item.child_nodes().next()?;
    if path.kind() == NodeKind::InterpolatedString {
        // Evaluating interpolations would require model semantics. Keep these
        // includes in place as group boundaries instead.
        return None;
    }
    let text = path.children().iter().find_map(|child| match child {
        SyntaxElement::Token(index) if parsed.tokens()[*index].kind == TokenKind::StringLiteral => {
            Some(&parsed.source()[parsed.tokens()[*index].range.clone()])
        }
        _ => None,
    })?;
    let mut decoded = Vec::new();
    let mut bytes = text[1..text.len() - 1].bytes().peekable();
    while let Some(byte) = bytes.next() {
        if byte != b'\\' {
            decoded.push(byte);
            continue;
        }
        let escaped = bytes.next()?;
        decoded.push(match escaped {
            b'n' => b'\n',
            b't' => b'\t',
            b'"' | b'\'' | b'\\' => escaped,
            b'x' | b'0'..=b'7' => {
                let radix = if escaped == b'x' { 16 } else { 8 };
                let mut value = if radix == 8 {
                    u32::from(escaped - b'0')
                } else {
                    0
                };
                for _ in 0..2 {
                    let Some(digit) = bytes
                        .peek()
                        .and_then(|byte| char::from(*byte).to_digit(radix))
                    else {
                        break;
                    };
                    bytes.next();
                    value = value * radix + digit;
                }
                value as u8
            }
            _ => return None,
        });
    }
    // Escapes insert UTF-8 bytes, not Unicode code points; byte ordering agrees
    // with scalar ordering for UTF-8. Preserve the written spelling in output.
    // https://docs.minizinc.dev/en/2.10.1/spec.html#string-literals-and-string-interpolation
    Some(decoded)
}