lace_sans_io/logic/lacegram/
parser.rs

1//! Lacegram surface syntax parsing and canonical rendering.
2
3use crate::types::{
4    BodyAtom, OrderingExpression, RelOp, Rule, Term, Value, Variable, is_canonical_unsigned_decimal,
5};
6
7pub(super) fn head_name(line: &str) -> &str {
8    line.split_once('(').map(|(name, _)| name).unwrap_or(line)
9}
10
11pub fn render_rule_line(rule: &Rule) -> String {
12    let body = if rule.body.is_empty()
13        || (rule.body.len() == 1 && matches!(rule.body[0], BodyAtom::True))
14    {
15        "true".to_string()
16    } else {
17        rule.body
18            .iter()
19            .map(render_body_atom)
20            .collect::<Vec<_>>()
21            .join(", ")
22    };
23    format!(
24        "{}({}) :- {}.",
25        rule.head_predicate,
26        rule.head_terms
27            .iter()
28            .map(render_term)
29            .collect::<Vec<_>>()
30            .join(","),
31        body
32    )
33}
34
35fn render_body_atom(atom: &BodyAtom) -> String {
36    match atom {
37        BodyAtom::Positive { predicate, terms } => format!(
38            "{}({})",
39            predicate,
40            terms.iter().map(render_term).collect::<Vec<_>>().join(",")
41        ),
42        BodyAtom::Negated { predicate, terms } => format!(
43            "not {}({})",
44            predicate,
45            terms.iter().map(render_term).collect::<Vec<_>>().join(",")
46        ),
47        BodyAtom::NotEqual(a, b) => format!("{} != {}", render_term(a), render_term(b)),
48        BodyAtom::Compare { left, op, right } => format!(
49            "Compare({},'{}',{})",
50            render_ordering_expression(left),
51            render_relop(*op),
52            render_ordering_expression(right)
53        ),
54        BodyAtom::TextMatch { text, pattern } => format!(
55            "TextMatch({},'{}')",
56            render_term(text),
57            escape_constant(pattern)
58        ),
59        BodyAtom::TextShape {
60            text,
61            start,
62            delims,
63            end,
64        } => format!(
65            "TextShape({},{},'{}',{})",
66            render_term(text),
67            render_term(start),
68            escape_constant(delims),
69            render_term(end)
70        ),
71        BodyAtom::Cardinality {
72            predicate,
73            terms,
74            op,
75            num,
76        } => format!(
77            "Cardinality({}({}),'{}','{}')",
78            predicate,
79            terms.iter().map(render_term).collect::<Vec<_>>().join(","),
80            render_relop(*op),
81            escape_constant(num)
82        ),
83        BodyAtom::TopK {
84            predicate,
85            terms,
86            partition,
87            order,
88            direction,
89            limit,
90        } => format!(
91            "TopK({}({}),PartitionBy({}),{},'{}','{}')",
92            predicate,
93            terms.iter().map(render_term).collect::<Vec<_>>().join(","),
94            partition
95                .iter()
96                .map(|variable| variable.name())
97                .collect::<Vec<_>>()
98                .join(","),
99            render_ordering_expression(order),
100            render_relop(*direction),
101            escape_constant(limit),
102        ),
103        BodyAtom::True => "true".to_string(),
104    }
105}
106
107fn render_ordering_expression(expression: &OrderingExpression) -> String {
108    let (name, term) = match expression {
109        OrderingExpression::Lex(term) => ("Lex", term),
110        OrderingExpression::Int(term) => ("Int", term),
111        OrderingExpression::AdmitOrder(term) => ("AdmitOrder", term),
112    };
113    format!("{name}({})", render_term(term))
114}
115
116pub(super) fn render_term(term: &Term) -> String {
117    match term {
118        Term::Var(v) => v.name().to_string(),
119        Term::Anonymous => "_".to_string(),
120        Term::Const(c) => format!("'{}'", escape_constant(c)),
121    }
122}
123
124fn render_relop(op: RelOp) -> &'static str {
125    match op {
126        RelOp::Lt => "<",
127        RelOp::Le => "<=",
128        RelOp::Gt => ">",
129        RelOp::Ge => ">=",
130    }
131}
132
133fn escape_constant(value: &str) -> String {
134    value.replace('\\', "\\\\").replace('\'', "\\'")
135}
136
137/// Parse a single rule line.
138///
139/// Syntax: `Head(Term, ...) :- BodyAtom, BodyAtom.`
140/// or:     `Head(Term, ...) :- true.`
141pub fn parse_rule(line: &str) -> Result<Rule, String> {
142    let separator = find_top_level(line, " :- ").ok_or("missing ' :- '")?;
143    let head_str = line[..separator].trim();
144    let body_str = line[separator + 4..].trim();
145
146    // Strip trailing period
147    let body_str = body_str.strip_suffix('.').ok_or("rule must end with '.'")?;
148
149    // Parse head: Predicate(Term, ...)
150    let (head_pred, head_terms) =
151        parse_atom(head_str).map_err(|e| format!("invalid head: {}", e))?;
152
153    // Parse body atoms (comma-separated)
154    let body = if body_str.trim() == "true" {
155        vec![BodyAtom::True]
156    } else {
157        let mut atoms = Vec::new();
158        for atom_str in split_body_atoms(body_str) {
159            let atom = parse_body_atom(atom_str.trim())
160                .map_err(|e| format!("invalid body atom '{}': {}", atom_str, e))?;
161            atoms.push(atom);
162        }
163        atoms
164    };
165
166    Ok(Rule {
167        head_predicate: head_pred,
168        head_terms,
169        body,
170    })
171}
172
173/// Parse a predicate atom: `Name(Term, ...)`.
174/// Returns (predicate_name, terms).
175fn parse_atom(s: &str) -> Result<(Value, Vec<Term>), String> {
176    let s = s.trim();
177    let paren = s.find('(').ok_or("missing '(' in atom")?;
178    if !s.ends_with(')') {
179        return Err("atom must end with ')'".into());
180    }
181    let name = &s[..paren];
182    if is_reserved_logic_word(name) {
183        return Err(format!(
184            "`{name}` is reserved logic syntax, not a predicate name"
185        ));
186    }
187    if !is_valid_predicate_name(name) {
188        return Err(format!("invalid predicate name: {name}"));
189    }
190    let args_str = &s[paren + 1..s.len() - 1];
191
192    let terms = if args_str.is_empty() {
193        Vec::new()
194    } else {
195        let mut terms = Vec::new();
196        for arg in split_args(args_str) {
197            let term = parse_term(arg.trim())?;
198            terms.push(term);
199        }
200        terms
201    };
202
203    Ok((name.into(), terms))
204}
205
206/// Parse a body atom.
207fn parse_body_atom(s: &str) -> Result<BodyAtom, String> {
208    let s = s.trim();
209
210    // not Pred(...)
211    if let Some(rest) = s.strip_prefix("not ") {
212        let (pred, terms) = parse_atom(rest)?;
213        return Ok(BodyAtom::Negated {
214            predicate: pred,
215            terms,
216        });
217    }
218
219    if s == "true" {
220        return Ok(BodyAtom::True);
221    }
222
223    // Compare(OrderingExpression, Op, OrderingExpression)
224    if let Some(inner) = s.strip_prefix("Compare(") {
225        let inner = inner.strip_suffix(')').ok_or("Compare missing ')'")?;
226        let parts: Vec<&str> = split_args(inner);
227        if parts.len() != 3 {
228            return Err("Compare needs 3 args".into());
229        }
230        let left = parse_ordering_expression(parts[0].trim())?;
231        let op_str = strip_quotes(parts[1].trim())?;
232        let op = RelOp::parse(&op_str).ok_or("invalid compare op")?;
233        let right = parse_ordering_expression(parts[2].trim())?;
234        if std::mem::discriminant(&left) != std::mem::discriminant(&right) {
235            return Err("Compare ordering expression kinds must match".into());
236        }
237        return Ok(BodyAtom::Compare { left, op, right });
238    }
239
240    // TopK(Pred(...), PartitionBy(...), OrderingExpression, Direction, K)
241    if let Some(inner) = s.strip_prefix("TopK(") {
242        let inner = inner.strip_suffix(')').ok_or("TopK missing ')'")?;
243        let parts: Vec<&str> = split_args(inner);
244        if parts.len() != 5 {
245            return Err("TopK needs 5 args".into());
246        }
247        let (predicate, terms) = parse_atom(parts[0].trim())?;
248        let partition = parse_partition(parts[1].trim())?;
249        let mut seen = std::collections::HashSet::new();
250        for variable in &partition {
251            if !seen.insert(variable) {
252                return Err("TopK PartitionBy variables must be distinct".into());
253            }
254            if !terms
255                .iter()
256                .any(|term| term == &Term::Var(variable.clone()))
257            {
258                return Err("TopK PartitionBy variable must occur in the candidate atom".into());
259            }
260        }
261        let order = parse_ordering_expression(parts[2].trim())?;
262        let direction_text = strip_quotes(parts[3].trim())?;
263        let direction = match RelOp::parse(&direction_text) {
264            Some(RelOp::Lt) => RelOp::Lt,
265            Some(RelOp::Gt) => RelOp::Gt,
266            _ => return Err("TopK direction must be '<' or '>'".into()),
267        };
268        let limit = strip_quotes(parts[4].trim())?;
269        if !is_canonical_unsigned_decimal(&limit) {
270            return Err("TopK limit must be canonical unsigned decimal text".into());
271        }
272        if order.term().is_anonymous() || !terms.iter().any(|term| term == order.term()) {
273            return Err(
274                "TopK ordering term must occur in the candidate atom and must not be anonymous"
275                    .into(),
276            );
277        }
278        return Ok(BodyAtom::TopK {
279            predicate,
280            terms,
281            partition,
282            order,
283            direction,
284            limit: limit.into(),
285        });
286    }
287
288    // Cardinality(Pred(...), Op, N)
289    if let Some(inner) = s.strip_prefix("Cardinality(") {
290        let inner = inner.strip_suffix(')').ok_or("Cardinality missing ')'")?;
291        let parts: Vec<&str> = split_args(inner);
292        if parts.len() != 3 {
293            return Err("Cardinality needs 3 args".into());
294        }
295        let (predicate, terms) = parse_atom(parts[0].trim())?;
296        let op_str = strip_quotes(parts[1].trim())?;
297        let op = RelOp::parse(&op_str).ok_or("invalid compare op")?;
298        let num = strip_quotes(parts[2].trim())?;
299        if !is_canonical_unsigned_decimal(&num) {
300            return Err("Cardinality bound must be canonical unsigned decimal text".into());
301        }
302        return Ok(BodyAtom::Cardinality {
303            predicate,
304            terms,
305            op,
306            num: num.into(),
307        });
308    }
309
310    if let Some(inner) = s.strip_prefix("TextMatch(") {
311        let inner = inner.strip_suffix(')').ok_or("TextMatch missing ')'")?;
312        let parts = split_args(inner);
313        if parts.len() != 2 {
314            return Err("TextMatch needs 2 args".into());
315        }
316        return Ok(BodyAtom::TextMatch {
317            text: parse_term(parts[0].trim())?,
318            pattern: strip_quotes(parts[1].trim())?,
319        });
320    }
321
322    // TextShape(Text, Start, Delims, End)
323    if let Some(inner) = s.strip_prefix("TextShape(") {
324        let inner = inner.strip_suffix(')').ok_or("TextShape missing ')'")?;
325        let parts: Vec<&str> = split_args(inner);
326        if parts.len() != 4 {
327            return Err("TextShape needs 4 args".into());
328        }
329        let text = parse_term(parts[0].trim())?;
330        let start = parse_term(parts[1].trim())?;
331        let delims = strip_quotes(parts[2].trim())?;
332        let end = parse_term(parts[3].trim())?;
333        return Ok(BodyAtom::TextShape {
334            text,
335            start,
336            delims: delims.into(),
337            end,
338        });
339    }
340
341    // Inequality: X != Y
342    if let Some(pos) = find_top_level(s, " != ") {
343        let left = parse_term(&s[..pos])?;
344        let right = parse_term(&s[pos + 4..])?;
345        return Ok(BodyAtom::NotEqual(left, right));
346    }
347
348    // Equality is not Lace Datalog.
349    if find_top_level(s, " = ").is_some() {
350        return Err("Lace Datalog must not contain equality".into());
351    }
352
353    // Positive predicate: Name(Term, ...)
354    let (pred, terms) = parse_atom(s)?;
355    Ok(BodyAtom::Positive {
356        predicate: pred,
357        terms,
358    })
359}
360
361fn parse_partition(s: &str) -> Result<Vec<Variable>, String> {
362    let inner = s
363        .strip_prefix("PartitionBy(")
364        .and_then(|value| value.strip_suffix(')'))
365        .ok_or("TopK second argument must be PartitionBy(variable, ...)")?;
366    if inner.is_empty() {
367        return Ok(Vec::new());
368    }
369    split_args(inner)
370        .into_iter()
371        .map(|source| match parse_term(source.trim())? {
372            Term::Var(variable) => Ok(variable),
373            _ => Err("TopK PartitionBy entries must be named variables".into()),
374        })
375        .collect()
376}
377
378fn parse_ordering_expression(s: &str) -> Result<OrderingExpression, String> {
379    for (name, constructor) in [
380        (
381            "Lex",
382            OrderingExpression::Lex as fn(Term) -> OrderingExpression,
383        ),
384        ("Int", OrderingExpression::Int),
385        ("AdmitOrder", OrderingExpression::AdmitOrder),
386    ] {
387        if let Some(inner) = s.strip_prefix(&format!("{name}(")) {
388            let inner = inner
389                .strip_suffix(')')
390                .ok_or_else(|| format!("{name} missing ')'"))?;
391            return Ok(constructor(parse_term(inner)?));
392        }
393    }
394    Err("Compare operands must be Lex(term), Int(term), or AdmitOrder(record-term)".into())
395}
396
397/// Parse a term: anonymous `_`, uppercase record-reference variable,
398/// lowercase text variable, or quoted constant.
399fn parse_term(s: &str) -> Result<Term, String> {
400    let s = s.trim();
401    if s.is_empty() {
402        return Err("empty term".into());
403    }
404    if s == "_" {
405        return Ok(Term::Anonymous);
406    }
407    // Quoted constant: '...'
408    if s.starts_with('\'') {
409        let unescaped = strip_quotes(s)?;
410        crate::types::validate_fact_value(&unescaped)?;
411        return Ok(Term::Const(unescaped.into()));
412    }
413    if is_reserved_logic_word(s) {
414        return Err(format!("`{s}` is reserved logic syntax, not a term"));
415    }
416    if is_record_reference_variable_name(s) {
417        return Ok(Term::Var(Variable::record(s)));
418    }
419    if is_text_variable_name(s) {
420        return Ok(Term::Var(Variable::text(s)));
421    }
422    Err(format!("invalid term: {}", s))
423}
424
425pub(super) fn is_record_reference_variable_name(name: &str) -> bool {
426    let mut chars = name.chars();
427    let Some(first) = chars.next() else {
428        return false;
429    };
430    first.is_ascii_uppercase() && chars.all(|c| c.is_ascii_alphanumeric() || c == '_')
431}
432
433pub(super) fn is_text_variable_name(name: &str) -> bool {
434    let mut chars = name.chars();
435    let Some(first) = chars.next() else {
436        return false;
437    };
438    first.is_ascii_lowercase()
439        && chars.all(|c| c.is_ascii_lowercase() || c.is_ascii_digit() || c == '_')
440}
441
442pub(super) fn is_reserved_logic_word(name: &str) -> bool {
443    matches!(name, "true" | "not")
444}
445
446pub(super) fn is_valid_predicate_name(name: &str) -> bool {
447    let mut chars = name.chars();
448    let Some(first) = chars.next() else {
449        return false;
450    };
451    if first == '_' {
452        let Some(second) = chars.next() else {
453            return false;
454        };
455        second.is_ascii_alphabetic()
456            && chars.all(|c| c.is_ascii_alphanumeric() || c == '_' || c == '~' || c == '-')
457    } else {
458        is_record_reference_variable_name(name) || is_text_variable_name(name)
459    }
460}
461
462/// Strip single quotes from a quoted constant.
463fn strip_quotes(s: &str) -> Result<String, String> {
464    if let Some(inner) = s.strip_prefix('\'').and_then(|s| s.strip_suffix('\'')) {
465        unescape_constant(inner)
466    } else {
467        Err(format!("expected quoted constant, got: {}", s))
468    }
469}
470
471/// Unescape a constant: `\\` → `\`, `\'` → `'`.
472fn unescape_constant(s: &str) -> Result<String, String> {
473    let mut out = String::with_capacity(s.len());
474    let mut chars = s.chars();
475    while let Some(c) = chars.next() {
476        if c == '\\' {
477            match chars.next() {
478                Some('\\') => out.push('\\'),
479                Some('\'') => out.push('\''),
480                Some(other) => return Err(format!("invalid escape \\{}", other)),
481                None => return Err("trailing backslash".into()),
482            }
483        } else if c == '\'' {
484            return Err("constant contains unescaped quote".into());
485        } else if c == '\n' || c == '\r' {
486            return Err("constant contains newline".into());
487        } else {
488            out.push(c);
489        }
490    }
491    Ok(out)
492}
493
494fn find_top_level(source: &str, delimiter: &str) -> Option<usize> {
495    let mut quoted = false;
496    let mut escaped = false;
497    let mut depth = 0isize;
498    for (offset, ch) in source.char_indices() {
499        if quoted {
500            if escaped {
501                escaped = false;
502            } else if ch == '\\' {
503                escaped = true;
504            } else if ch == '\'' {
505                quoted = false;
506            }
507            continue;
508        }
509        if depth == 0 && source[offset..].starts_with(delimiter) {
510            return Some(offset);
511        }
512        match ch {
513            '\'' => quoted = true,
514            '(' => depth += 1,
515            ')' => depth -= 1,
516            _ => {}
517        }
518    }
519    None
520}
521
522/// Split comma-separated body atoms, respecting strings and parenthesization.
523fn split_body_atoms(s: &str) -> Vec<&str> {
524    let mut parts = Vec::new();
525    let mut depth = 0;
526    let mut start = 0;
527    let mut quoted = false;
528    let mut escaped = false;
529    for (i, c) in s.char_indices() {
530        if quoted {
531            if escaped {
532                escaped = false;
533            } else if c == '\\' {
534                escaped = true;
535            } else if c == '\'' {
536                quoted = false;
537            }
538            continue;
539        }
540        match c {
541            '\'' => quoted = true,
542            '(' => depth += 1,
543            ')' => depth -= 1,
544            ',' if depth == 0 => {
545                parts.push(&s[start..i]);
546                start = i + 1;
547            }
548            _ => {}
549        }
550    }
551    parts.push(&s[start..]);
552    parts
553}
554
555/// Split comma-separated arguments, respecting parenthesization.
556fn split_args(s: &str) -> Vec<&str> {
557    split_body_atoms(s)
558}
lace_sans_io/logic/lacegram/parser.rs

lace_sans_io/logic/lacegram/
parser.rs
