langlang_syntax/
ast.rs

1use std::collections::HashMap;
2use std::fmt::Debug;
3use std::string::{String as StdString, ToString};
4
5use langlang_value::source_map::Span;
6
7/// Grammar is the top-level AST node for the input grammar language.
8#[derive(Debug)]
9pub struct Grammar {
10    pub span: Span,
11    pub imports: Vec<Import>,
12    pub definition_names: Vec<StdString>,
13    pub definitions: HashMap<StdString, Definition>,
14}
15
16impl Grammar {
17    pub fn new(
18        span: Span,
19        imports: Vec<Import>,
20        definition_names: Vec<StdString>,
21        definitions: HashMap<StdString, Definition>,
22    ) -> Self {
23        Self {
24            span,
25            imports,
26            definition_names,
27            definitions,
28        }
29    }
30
31    pub fn add_definition(&mut self, d: &Definition) {
32        if self.definitions.get(&d.name).is_none() {
33            self.definition_names.push(d.name.clone());
34            self.definitions.insert(d.name.clone(), d.clone());
35        }
36    }
37}
38
39impl ToString for Grammar {
40    fn to_string(&self) -> StdString {
41        let mut output = StdString::new();
42        for i in &self.imports {
43            output.push_str(&i.to_string());
44            output.push('\n');
45        }
46        output.push('\n');
47        for name in &self.definition_names {
48            let d = &self.definitions[name];
49            output.push_str(&d.to_string());
50            output.push('\n');
51        }
52        output
53    }
54}
55
56/// Import represents an import node and contains both names to be
57/// imported and the path to import the names from.
58#[derive(Clone, Debug)]
59pub struct Import {
60    pub span: Span,
61    pub path: StdString,
62    pub names: Vec<StdString>,
63}
64
65impl ToString for Import {
66    fn to_string(&self) -> StdString {
67        format!(
68            "@import {} from \"{}\"",
69            fmtlistsep(", ", &self.names),
70            self.path
71        )
72    }
73}
74
75impl Import {
76    pub fn new(span: Span, path: StdString, names: Vec<StdString>) -> Self {
77        Self { span, path, names }
78    }
79}
80
81/// Definition represents a single production definition.  It stores
82/// both the name and the expression associated with the production.
83#[derive(Clone, Debug)]
84pub struct Definition {
85    pub span: Span,
86    pub name: StdString,
87    pub expr: Expression,
88}
89
90impl Definition {
91    pub fn new(span: Span, name: StdString, expr: Expression) -> Self {
92        Self { span, name, expr }
93    }
94}
95
96impl ToString for Definition {
97    fn to_string(&self) -> StdString {
98        format!("{} <- {}", self.name, self.expr.to_string())
99    }
100}
101
102pub trait IsSyntactic {
103    fn is_syntactic(&self) -> bool {
104        false
105    }
106}
107
108fn is_syntactic_list<T: IsSyntactic>(items: &[T]) -> bool {
109    items
110        .iter()
111        .map(|i| i.is_syntactic())
112        .reduce(|acc, i| acc && i)
113        .unwrap_or(false)
114}
115
116#[derive(Clone, Debug, PartialEq)]
117pub enum Expression {
118    Sequence(Sequence),
119    Choice(Choice),
120    Lex(Lex),
121    And(And),
122    Not(Not),
123    Optional(Optional),
124    ZeroOrMore(ZeroOrMore),
125    OneOrMore(OneOrMore),
126    Precedence(Precedence),
127    Label(Label),
128    List(List),
129    Node(Node),
130    Identifier(Identifier),
131    Literal(Literal),
132    Empty(Empty),
133}
134
135impl IsSyntactic for Expression {
136    fn is_syntactic(&self) -> bool {
137        match self {
138            Expression::Choice(v) => is_syntactic_list(&v.items),
139            Expression::Sequence(v) => v.is_syntactic(),
140            Expression::Lex(_) => true,
141            Expression::And(v) => v.expr.is_syntactic(),
142            Expression::Not(v) => v.expr.is_syntactic(),
143            Expression::Optional(v) => v.expr.is_syntactic(),
144            Expression::ZeroOrMore(v) => v.expr.is_syntactic(),
145            Expression::OneOrMore(v) => v.expr.is_syntactic(),
146            Expression::Precedence(v) => v.expr.is_syntactic(),
147            Expression::Label(v) => v.expr.is_syntactic(),
148            Expression::List(v) => is_syntactic_list(&v.items),
149            Expression::Node(v) => v.expr.is_syntactic(),
150            Expression::Identifier(_) => false,
151            Expression::Literal(_) => true,
152            Expression::Empty(_) => true,
153        }
154    }
155}
156
157impl ToString for Expression {
158    fn to_string(&self) -> StdString {
159        match self {
160            Expression::Choice(v) => format!("({})", fmtlistsep(" / ", &v.items)),
161            Expression::Sequence(v) => fmtlistsep(" ", &v.items),
162            Expression::Lex(v) => fmtprefix("#", &v.expr),
163            Expression::And(v) => fmtprefix("&", &v.expr),
164            Expression::Not(v) => fmtprefix("!", &v.expr),
165            Expression::Optional(v) => fmtsuffix("?", &v.expr),
166            Expression::ZeroOrMore(v) => fmtsuffix("*", &v.expr),
167            Expression::OneOrMore(v) => fmtsuffix("+", &v.expr),
168            Expression::Precedence(v) => format!("{}{}", v.expr.to_string(), v.precedence),
169            Expression::Label(v) => format!("{}^{}", v.expr.to_string(), v.label),
170            Expression::List(v) => format!("[{}]", fmtlistsep(", ", &v.items)),
171            Expression::Node(v) => format!("{} {{{}}}", v.name, v.expr.to_string()),
172            Expression::Identifier(v) => v.name.to_string(),
173            Expression::Literal(v) => v.to_string(),
174            Expression::Empty(_) => "".to_string(),
175        }
176    }
177}
178
179#[derive(Clone, Debug, PartialEq)]
180pub struct Sequence {
181    pub span: Span,
182    pub items: Vec<Expression>,
183}
184
185impl Sequence {
186    pub fn new_expr(span: Span, items: Vec<Expression>) -> Expression {
187        Expression::Sequence(Self { span, items })
188    }
189}
190
191impl IsSyntactic for Sequence {
192    fn is_syntactic(&self) -> bool {
193        is_syntactic_list(&self.items)
194    }
195}
196
197#[derive(Clone, Debug, PartialEq)]
198pub struct Choice {
199    pub span: Span,
200    pub items: Vec<Expression>,
201}
202
203impl Choice {
204    pub fn new_expr(span: Span, items: Vec<Expression>) -> Expression {
205        Expression::Choice(Choice::new(span, items))
206    }
207
208    pub fn new(span: Span, items: Vec<Expression>) -> Self {
209        Self { span, items }
210    }
211}
212
213#[derive(Clone, Debug, PartialEq)]
214pub struct Lex {
215    pub span: Span,
216    pub expr: Box<Expression>,
217}
218
219impl Lex {
220    pub fn new_expr(span: Span, expr: Box<Expression>) -> Expression {
221        Expression::Lex(Lex::new(span, expr))
222    }
223
224    pub fn new(span: Span, expr: Box<Expression>) -> Self {
225        Self { span, expr }
226    }
227}
228
229#[derive(Clone, Debug, PartialEq)]
230pub struct And {
231    pub span: Span,
232    pub expr: Box<Expression>,
233}
234
235impl And {
236    pub fn new_expr(span: Span, expr: Box<Expression>) -> Expression {
237        Expression::And(Self::new(span, expr))
238    }
239
240    pub fn new(span: Span, expr: Box<Expression>) -> Self {
241        Self { span, expr }
242    }
243}
244
245#[derive(Clone, Debug, PartialEq)]
246pub struct Not {
247    pub span: Span,
248    pub expr: Box<Expression>,
249}
250
251impl Not {
252    pub fn new_expr(span: Span, expr: Box<Expression>) -> Expression {
253        Expression::Not(Self { span, expr })
254    }
255
256    pub fn new(span: Span, expr: Box<Expression>) -> Self {
257        Self { span, expr }
258    }
259}
260
261#[derive(Clone, Debug, PartialEq)]
262pub struct Optional {
263    pub span: Span,
264    pub expr: Box<Expression>,
265}
266
267impl Optional {
268    pub fn new_expr(span: Span, expr: Box<Expression>) -> Expression {
269        Expression::Optional(Self { span, expr })
270    }
271}
272
273#[derive(Clone, Debug, PartialEq)]
274pub struct ZeroOrMore {
275    pub span: Span,
276    pub expr: Box<Expression>,
277}
278
279impl ZeroOrMore {
280    pub fn new_expr(span: Span, expr: Box<Expression>) -> Expression {
281        Expression::ZeroOrMore(Self { span, expr })
282    }
283}
284
285#[derive(Clone, Debug, PartialEq)]
286pub struct OneOrMore {
287    pub span: Span,
288    pub expr: Box<Expression>,
289}
290
291impl OneOrMore {
292    pub fn new_expr(span: Span, expr: Box<Expression>) -> Expression {
293        Expression::OneOrMore(Self { span, expr })
294    }
295}
296
297#[derive(Clone, Debug, PartialEq)]
298pub struct Precedence {
299    pub span: Span,
300    pub expr: Box<Expression>,
301    pub precedence: usize,
302}
303
304impl Precedence {
305    pub fn new_expr(span: Span, expr: Box<Expression>, precedence: usize) -> Expression {
306        Expression::Precedence(Self {
307            span,
308            expr,
309            precedence,
310        })
311    }
312}
313
314#[derive(Clone, Debug, PartialEq)]
315pub struct Label {
316    pub span: Span,
317    pub label: StdString,
318    pub expr: Box<Expression>,
319}
320
321impl Label {
322    pub fn new_expr(span: Span, label: StdString, expr: Box<Expression>) -> Expression {
323        Expression::Label(Self { span, label, expr })
324    }
325}
326
327#[derive(Clone, Debug, PartialEq)]
328pub struct List {
329    pub span: Span,
330    pub items: Vec<Expression>,
331}
332
333impl List {
334    pub fn new_expr(span: Span, items: Vec<Expression>) -> Expression {
335        Expression::List(Self { span, items })
336    }
337}
338
339#[derive(Clone, Debug, PartialEq)]
340pub struct Node {
341    pub span: Span,
342    pub name: StdString,
343    pub expr: Box<Expression>,
344}
345
346impl Node {
347    pub fn new_expr(span: Span, name: StdString, expr: Box<Expression>) -> Expression {
348        Expression::Node(Self { span, name, expr })
349    }
350}
351
352#[derive(Clone, Debug, PartialEq)]
353pub struct Identifier {
354    pub span: Span,
355    pub name: StdString,
356}
357
358impl Identifier {
359    pub fn new_expr(span: Span, name: StdString) -> Expression {
360        Expression::Identifier(Self::new(span, name))
361    }
362
363    pub fn new(span: Span, name: StdString) -> Self {
364        Self { span, name }
365    }
366}
367
368#[derive(Clone, Debug, PartialEq)]
369pub enum Literal {
370    String(String),
371    Class(Class),
372    Range(Range),
373    Char(Char),
374    Any(Any),
375}
376
377impl ToString for Literal {
378    fn to_string(&self) -> StdString {
379        match self {
380            Literal::String(v) => format!("\"{}\"", v.to_string()),
381            Literal::Class(v) => v.to_string(),
382            Literal::Range(v) => format!("{}-{}", v.start, v.end),
383            Literal::Char(v) => v.to_string(),
384            Literal::Any(_) => ".".to_string(),
385        }
386    }
387}
388
389#[derive(Clone, Debug, PartialEq)]
390pub struct String {
391    pub span: Span,
392    pub value: StdString,
393}
394
395impl String {
396    pub fn new_expr(span: Span, value: StdString) -> Expression {
397        Expression::Literal(Literal::String(Self { span, value }))
398    }
399}
400
401impl ToString for String {
402    fn to_string(&self) -> StdString {
403        self.value
404            .chars()
405            .flat_map(|c| c.escape_default())
406            .collect()
407    }
408}
409
410#[derive(Clone, Debug, PartialEq)]
411pub struct Class {
412    pub span: Span,
413    pub literals: Vec<Literal>,
414}
415
416impl Class {
417    pub fn new_expr(span: Span, literals: Vec<Literal>) -> Expression {
418        Expression::Literal(Literal::Class(Self { span, literals }))
419    }
420}
421
422impl ToString for Class {
423    fn to_string(&self) -> StdString {
424        let mut output = StdString::new();
425        output.push('[');
426        for l in &self.literals {
427            output.push_str(&l.to_string());
428        }
429        output.push(']');
430        output
431    }
432}
433
434#[derive(Clone, Debug, PartialEq)]
435pub struct Range {
436    pub span: Span,
437    pub start: char,
438    pub end: char,
439}
440
441impl Range {
442    pub fn new(span: Span, start: char, end: char) -> Self {
443        Self { span, start, end }
444    }
445}
446
447/// Char stores the position and value of a single character matcher
448#[derive(Clone, Debug, PartialEq)]
449pub struct Char {
450    pub span: Span,
451    pub value: char,
452}
453
454impl Char {
455    pub fn new(span: Span, value: char) -> Self {
456        Self { span, value }
457    }
458}
459
460impl ToString for Char {
461    fn to_string(&self) -> StdString {
462        self.value.escape_default().collect()
463    }
464}
465
466/// Any is the operator that matches anything but EOF
467#[derive(Clone, Debug, PartialEq)]
468pub struct Any {
469    pub span: Span,
470}
471
472impl Any {
473    pub fn new_expr(span: Span) -> Expression {
474        Expression::Literal(Literal::Any(Self { span }))
475    }
476}
477
478/// Empty represents the empty alternative of an ordered choice
479/// operator.  Both start and end of such span are the same as no
480/// input is consumed.
481#[derive(Clone, Debug, PartialEq)]
482pub struct Empty {
483    pub span: Span,
484}
485
486impl Empty {
487    pub fn new_expr(span: Span) -> Expression {
488        Expression::Empty(Self { span })
489    }
490}
491
492// formatting functions
493
494fn fmtlistsep<T: ToString>(sep: &str, items: &Vec<T>) -> StdString {
495    let mut output = StdString::new();
496    let len = items.len();
497
498    for (index, item) in items.iter().enumerate() {
499        output.push_str(&item.to_string());
500        if index < len - 1 {
501            output.push_str(sep);
502        }
503    }
504
505    output
506}
507
508fn fmtprefix(prefix: &str, node: &Expression) -> StdString {
509    if tree_height(node) > 1 {
510        return format!("{}({})", prefix, node.to_string());
511    }
512    if let Expression::Sequence(seq) = node {
513        if seq.items.len() > 1 {
514            return format!("{}({})", prefix, node.to_string());
515        }
516    }
517    format!("{}{}", prefix, node.to_string())
518}
519
520fn fmtsuffix(suffix: &str, node: &Expression) -> StdString {
521    if tree_height(node) > 1 {
522        return format!("({}){}", node.to_string(), suffix);
523    }
524    if let Expression::Sequence(seq) = node {
525        if seq.items.len() > 1 {
526            return format!("({}){}", node.to_string(), suffix);
527        }
528    }
529    format!("{}{}", node.to_string(), suffix)
530}
531
532fn tree_height(n: &Expression) -> usize {
533    match n {
534        Expression::Sequence(v) => items_height(&v.items),
535        Expression::Choice(v) => items_height(&v.items) + 1,
536        Expression::Lex(v) => tree_height(&v.expr) + 1,
537        Expression::And(v) => tree_height(&v.expr) + 1,
538        Expression::Not(v) => tree_height(&v.expr) + 1,
539        Expression::Optional(v) => tree_height(&v.expr) + 1,
540        Expression::ZeroOrMore(v) => tree_height(&v.expr) + 1,
541        Expression::OneOrMore(v) => tree_height(&v.expr) + 1,
542        Expression::Precedence(v) => tree_height(&v.expr) + 1,
543        Expression::Label(v) => tree_height(&v.expr) + 1,
544        Expression::List(v) => items_height(&v.items) + 1,
545        Expression::Node(v) => tree_height(&v.expr) + 1,
546        Expression::Identifier(_) => 1,
547        Expression::Literal(_) => 1,
548        Expression::Empty(_) => 1,
549    }
550}
551
552fn items_height(items: &[Expression]) -> usize {
553    items
554        .iter()
555        .map(tree_height)
556        .fold(usize::MIN, |a, b| a.max(b))
557}
langlang_syntax/ast.rs

langlang_syntax/
ast.rs
