Skip to main content

lexigram_lib/
lib.rs

1// Copyright (c) 2025 Redglyph (@gmail.com). All Rights Reserved.
2
3use std::collections::{BTreeSet, HashMap};
4use std::ops::Deref;
5use iter_index::IndexerIterator;
6use vectree::VecTree;
7
8// exposes lexigram-core:
9pub use lexigram_core;
10pub use lexigram_core::{AltId, TokenId, VarId};
11pub use lexigram_core::CollectJoin;
12pub use lexigram_core::alt;
13pub use lexigram_core::fixed_sym_table;
14pub use lexigram_core::log;
15pub use lexigram_core::char_reader;
16use lexigram_core::CharLen;
17pub use lexigram_core::segmap;
18pub use lexigram_core::seg;
19pub use lexigram_core::lexer;
20pub use lexigram_core::parser;
21
22mod macros;
23mod adaptors;
24mod cproduct;
25pub mod build;
26pub mod segments;
27pub mod dfa;
28pub mod lexergen;
29pub mod lexi;
30pub mod grammar;
31pub mod parsergen;
32pub mod file_utils;
33mod name_fixer;
34pub use name_fixer::{NameFixer, NameTransformer};
35mod symbol_table;
36pub mod rtsgen;
37mod tests;
38
39pub use symbol_table::SymbolTable;
40
41// package name & version
42pub const LIB_PKG_NAME: &str = env!("CARGO_PKG_NAME");
43pub const LIB_PKG_VERSION: &str = env!("CARGO_PKG_VERSION");
44
45// Regular expressions / DFA, See:
46// - https://blog.burntsushi.net/regex-internals/
47// - https://en.wikipedia.org/wiki/Tagged_Deterministic_Finite_Automaton
48// - https://arxiv.org/abs/2206.01398
49//
50// See also:
51// - Ref: https://en.wikipedia.org/wiki/Comparison_of_parser_generators
52//
53// UTF-8:
54// - https://www.ibm.com/docs/en/db2/11.5?topic=support-unicode-character-encoding
55// - std::char::encode_utf8_raw(...)
56//
57// Misc
58// - https://re2c.org/
59// - https://www.genivia.com/get-reflex.html
60// - https://nothings.org/computer/lexing.html
61// - https://github.com/maciejhirsz/logos
62// - https://alic.dev/blog/fast-lexing
63
64// ---------------------------------------------------------------------------------------------
65// Shared types
66
67/// Unit type used as generic parameter to indicate general, non-normalized form.
68///
69/// - `Dfa<General>` may have accepting states with IDs smaller than non-accepting states' IDs, or non-incremntal IDs.
70/// - `RuleTreeSet<General>` may include any operators like `*`, `+`, and `?`, and doesn't have a restriction on depth.
71/// - `ProdRuleSet<General>` may be ambiguous, left-recursive, and/or need left factorization, depending on the target.
72#[derive(Clone, Debug)]
73pub struct General;
74
75// `ProdRuleSet<LL>` has rules that aren't left-recursive and are left-factorized.
76// #[derive(Clone, Debug)]
77// pub struct LL1;
78pub use lexigram_core::LL1;
79
80/// `ProdRuleSet<LR>` is used to create bottom-up parsers.
81#[derive(Clone, Debug)]
82pub struct LR;
83
84// [`LRParserTables<LALR>`](parsergen::lr::LRParserTables<LALR>) is built from `ProdRuleSet<LR>`
85// #[derive(Clone, Debug)]
86// pub struct LALR;
87pub use lexigram_core::LALR;
88use lexigram_core::lexer::{CaretCol, Pos, PosSpan};
89use lexigram_core::parser::ParserToken;
90
91pub use make_stream::{make_stream, MakeStreamIterator};
92
93/// Unit type used as generic parameter to indicate normalized form.
94///
95/// - `Dfa<Normalized>` always has incremental state numbers, starting at 0, with all the accepting states at the end.
96/// - `RuleTreeSet<Normalized>` only has `|`, `&`, and symbols, and must have one of the 3 following patterns:
97///   - a symbol
98///   - a `&` with only symbols as children
99///   - a `|` with only `&(symbols)` or symbols as children
100#[derive(Clone, Debug)]
101pub struct Normalized;
102
103// ---------------------------------------------------------------------------------------------
104// General helper functions
105
106/// Gathers `iter_item` in a vector and pushes it into `v`.
107pub(crate) fn vaddi<I, T>(v: &mut Vec<Vec<T>>, iter_item: I) -> usize
108    where I: IntoIterator<Item=T> + Clone
109{
110    let new_index = v.len();
111    v.push(Vec::from_iter(iter_item));
112    new_index
113}
114
115/// Takes `lines` of columns and outputs lines of strings in which the columns
116/// are aligned. The minimum width of each column can be preset with the optional `min_widths` vector.
117///
118/// The final width of each column is the 1 + maximum number of characters - not bytes - of the strings
119/// representing that column in all the lines (the +1 makes sure columns are separated by at least one
120/// space). The last column is left as-is; no spaces are added to adjust its width.
121pub fn columns_to_str(cols: Vec<Vec<String>>, min_widths: Option<Vec<usize>>) -> Vec<String> {
122    let min_widths = min_widths.unwrap_or(vec![0; cols.first().map(|v| v.len()).unwrap_or(0)]);
123    let ncol = min_widths.len();
124    let mut width = cols.iter().fold(min_widths, |acc, s| {
125        assert_eq!(s.len(), ncol, "number of columns is not consistently {ncol}");
126        acc.into_iter().zip(s).map(|(a, s)| a.max(s.charlen() + 1)).collect()
127    });
128    if let Some(x) = width.last_mut() { *x = 0 };
129    cols.into_iter().map(|v| v.into_iter().zip(&width).map(|(mut s, w)| {
130        for _ in 0..w.saturating_sub(s.charlen()) { s.push(' ') }
131        s
132    }).collect::<String>()).collect()
133}
134
135pub fn indent_source(parts: Vec<Vec<String>>, indent: usize) -> String {
136    // SAFETY: ' ' is ASCII, and `indent` is >= 0
137    let s = unsafe { String::from_utf8_unchecked(vec![32; indent]) };
138    let mut source = String::new();
139    let mut first = true;
140    for part in parts {
141        if !first {
142            source.push('\n');
143        }
144        first = false;
145        for string in part {
146            for line in string.split("\n") {
147                let cured_line = line.trim_end();
148                if !cured_line.is_empty() {
149                    source.push_str(&s);
150                }
151                source.push_str(cured_line);
152                source.push('\n');
153            }
154        }
155    }
156    source
157}
158
159mod make_stream {
160    use std::str::SplitAsciiWhitespace;
161    use iter_index::Indexer;
162    use super::*;
163
164    /// Makes a stream for the parser from an input string and basic token information.
165    ///
166    /// For tests purposes only.
167    ///
168    /// The caret information is very crude:
169    /// the column increments on each token, and the line remains at 1. All space characters are discarded and used to separate tokens,
170    /// so there must be at least one space between each token.
171    ///
172    /// Arguments:
173    /// * [tokens]: Iterable of `(&str, Option<&str>)`, or something that can be converted to it; e.g. the `SYMBOLS_T` generated by
174    ///   Lexigram is fine.
175    ///   * The first `&str` is the **name** of the token used in the grammar,
176    ///   * the `Option<&str>` is the **fixed value** it scans (like a keyword) or `None` if it's variable (like an identifier or a number).
177    /// * [include_tnames]: When true, the token names are used to scan the input when the fixed value doesn't exist. When false,
178    ///   only the fixed values are used to scan the input.
179    /// * [id]: The [TokenId] of an identifier: anything that isn't in the `Option<&str>` items and which starts with a non-digit will
180    ///   be converted into that token. Put a very large number if not used.
181    /// * [num]: The [TokenId] of a number: anything starting with a digit which isn't in the `Option<&str>` items will be converted into
182    ///   that token. Put a very large number if not used.
183    /// * [verbose]: When true, prints out the tokens as they're issued.
184    ///
185    /// ## Example
186    ///
187    /// This example will stream tokens `A`, `Id(a)`, `Id(b)`, `Id(c)`, `C`:
188    /// ```ignore
189    /// use lexigram_lib::make_stream;
190    ///
191    /// static SYMBOLS_T: [(&str, Option<&str>); 3] = [("A", None), ("C", None), ("Id", None)];
192    /// // ...
193    ///
194    /// let stream = make_stream("A a b c C", SYMBOLS_T, true, 2, 9999, false);
195    /// let mut listener = Listener::new();
196    /// let mut wrapper = Wrapper::new(listener, false);
197    /// let result = parser.parse_stream(&mut wrapper, stream);
198    /// ```
199    pub fn make_stream<S, T>(
200        input: &str,
201        tokens: T,
202        include_tnames: bool,
203        id: Option<TokenId>,
204        num: Option<TokenId>,
205        verbose: bool
206    ) -> impl Iterator<Item=ParserToken>
207    where
208        S: std::hash::Hash + Eq + std::borrow::Borrow<str>,
209        T: IntoIterator<Item=(S, Option<S>)>,
210    {
211        MakeStreamIterator::new(input, tokens, include_tnames, id, num, verbose)
212    }
213
214    enum MakeStreamMode { Token, Error(String, PosSpan), Eof }
215
216    pub struct MakeStreamIterator<'s, S> {
217        items: Indexer<SplitAsciiWhitespace<'s>, CaretCol>,
218        mode: MakeStreamMode,
219        symbols: HashMap<S, TokenId>,
220        id: Option<TokenId>,
221        num: Option<TokenId>,
222        verbose: bool
223   }
224
225    impl<'s, S> MakeStreamIterator<'s, S>
226    where
227        S: std::hash::Hash + Eq + std::borrow::Borrow<str>,
228    {
229        pub fn new<T: IntoIterator<Item=(S, Option<S>)>> (
230            input: &'s str,
231            tokens: T,
232            include_tnames: bool,
233            id: Option<TokenId>,
234            num: Option<TokenId>,
235            verbose: bool
236        ) -> Self {
237            let symbols: HashMap<S, TokenId> = tokens.into_iter().index::<TokenId>()
238                .filter_map(|(t, (s, fixed_maybe))|
239                    if let Some(fixed) = fixed_maybe {
240                        Some((fixed, t))
241                    } else {
242                        if include_tnames {
243                            Some((s, t))
244                        } else {
245                            None
246                        }
247                    })
248                .collect::<HashMap<_, _>>();
249            MakeStreamIterator {
250                items: input.split_ascii_whitespace().index_start::<CaretCol>(1),
251                mode: MakeStreamMode::Token,
252                symbols,
253                id,
254                num,
255                verbose
256            }
257        }
258    }
259
260    impl<S> Iterator for MakeStreamIterator<'_, S>
261    where
262        S: std::hash::Hash + Eq + std::borrow::Borrow<str>,
263    {
264        type Item = ParserToken;
265
266        fn next(&mut self) -> Option<Self::Item> {
267            let next = match &mut self.mode {
268                MakeStreamMode::Token => {
269                    if let Some((pos, w)) = self.items.next() {
270                        let pos_span = PosSpan::new(Pos(1, pos), Pos(1, pos));
271                        if let Some(s) = self.symbols.get(w) {
272                            Some((*s, w.to_string(), pos_span))
273                        } else if let Some(num) = self.num && w.chars().next().unwrap().is_ascii_digit() {
274                            Some((num, w.to_string(), pos_span))
275                        } else if let Some(id) = self.id && w.chars().next().unwrap().is_ascii_alphabetic() {
276                            Some((id, w.to_string(), pos_span))
277                        } else {
278                            self.mode = MakeStreamMode::Error(
279                                format!("invalid character {w:?} at {pos_span}"),
280                                pos_span
281                            );
282                            None
283                        }
284                    } else {
285                        self.mode = MakeStreamMode::Eof;
286                        None
287                    }
288                }
289                MakeStreamMode::Error(msg, pos_span) => {
290                    let parser_token = (TokenId::MAX, std::mem::take(msg), std::mem::take(pos_span));
291                    self.mode = MakeStreamMode::Token;
292                    Some(parser_token)
293                }
294                MakeStreamMode::Eof => None,
295            };
296            if self.verbose {
297                if let Some((token, str, pos)) = &next {
298                    println!(">> token {token}: {str:?} at {pos}");
299                } else {
300                    println!(">> None");
301                }
302            }
303            next
304        }
305    }
306}
307
308// ---------------------------------------------------------------------------------------------
309// Source generation helper traits and types
310
311/// Adds empty lines between blocks of text
312pub trait SourceSpacer {
313    /// Adds an empty string to the vector, but only if the last vector string isn't empty. If the vector is
314    /// empty, doesn't add anything.
315    fn add_space(&mut self);
316}
317
318impl SourceSpacer for Vec<String> {
319    fn add_space(&mut self) {
320        if let Some(line) = self.last() {
321            if !line.is_empty() {
322                self.push("".to_string());
323            }
324        }
325    }
326}
327
328#[derive(Clone, Debug, Default)]
329pub struct StructLibs {
330    libs: BTreeSet<String>
331}
332
333impl StructLibs {
334    pub fn new() -> Self {
335        StructLibs::default()
336    }
337
338    pub fn add<T: Into<String>>(&mut self, lib: T) {
339        self.libs.insert(lib.into());
340    }
341
342    pub fn extend<I: IntoIterator<Item=T>, T: Into<String>>(&mut self, libs: I) {
343        self.libs.extend(libs.into_iter().map(|s| s.into()));
344    }
345
346    #[cfg(test)]
347    fn tree_to_string(t: &VecTree<String>, idx: usize) -> String {
348        let children = t.children(idx).iter().map(|child| {
349            if t.children(*child).len() > 0 {
350                format!("{}[{}]", t.get(*child), Self::tree_to_string(t, *child))
351            } else {
352                t.get(*child).to_string()
353            }
354        }).to_vec();
355        children.join(", ")
356    }
357
358    fn to_tree(&self) -> VecTree<String> {
359        let mut tree = VecTree::new();
360        let root = tree.add_root(String::new());
361        for lib in &self.libs {
362            let mut idx = root;
363            for md in lib.split("::") {
364                idx = tree.children(idx).iter()
365                    .find_map(|&i| {
366                        if tree.get(i) == md { Some(i) } else { None }
367                    })
368                    .unwrap_or_else(|| {
369                        tree.add(Some(idx), md.to_string())
370                    });
371            }
372            tree.add(Some(idx), "self".to_string());
373        }
374        tree
375    }
376
377    pub fn gen_source_code(&self) -> Vec<String> {
378        let mut stack = Vec::<Vec<String>>::new();
379        let tree = self.to_tree();
380        for node in tree.iter_post_depth_simple() {
381            if node.depth as usize >= stack.len() && node.depth > 0 {
382                while node.depth as usize > stack.len() {
383                    stack.push(vec![]);
384                }
385                stack.last_mut().unwrap().push(node.to_string())
386            } else if node.depth > 0 {
387                let sub = stack.pop().unwrap();
388                stack.last_mut().unwrap().push(
389                    if sub.len() > 1 {
390                        format!("{}::{{{}}}", node.deref(), sub.join(", "))
391                    } else if sub.last().unwrap() == "self" {
392                        node.deref().to_string()
393                    } else {
394                        format!("{}::{}", node.deref(), sub[0])
395                    });
396            }
397        }
398        stack.pop().unwrap_or(vec![]).into_iter().map(|s| format!("use {s};")).to_vec()
399    }
400}
401
402// ---------------------------------------------------------------------------------------------
403
404#[cfg(test)]
405mod libtests {
406    use lexigram_core::CharLen;
407    use super::*;
408    use lexigram_core::log::{BufLog, Logger};
409    use crate::build::{BuildError, BuildErrorSource};
410
411    #[test]
412    fn test_column_to_str() {
413        let a = vec![
414            vec!["1".to_string(), "2".to_string()],
415            vec!["◄10".to_string(), "20".to_string()],
416            vec!["100".to_string(), "200".to_string()],
417        ];
418        let b = vec![
419            vec!["1".to_string(), "◄20".to_string(), "3000".to_string()],
420            vec!["10".to_string(), "2000".to_string(), "3".to_string()],
421            vec!["1000".to_string(), "2".to_string(), "300".to_string()],
422        ];
423        let tests = vec![
424            (a.clone(), Some(vec![2, 0]), "1   2\n◄10 20\n100 200"),
425            (a, None, "1   2\n◄10 20\n100 200"),
426            (b.clone(), Some(vec![3, 2, 0]), "1    ◄20  3000\n10   2000 3\n1000 2    300"),
427            (b, Some(vec![8, 2, 0]), "1       ◄20  3000\n10      2000 3\n1000    2    300"),
428            (vec![], Some(vec![]), ""),
429            (vec![], Some(vec![1, 2, 3]), ""),
430            (vec![], None, ""),
431        ];
432        for (i, (v, w, expected)) in tests.into_iter().enumerate() {
433            let result_v = columns_to_str(v, w);
434            let result = result_v.join("\n");
435            assert_eq!(result, expected, "failed with test {i}")
436        }
437    }
438
439    #[test]
440    fn test_col_to_string() {
441        let x = std::collections::BTreeSet::<u32>::from([10, 20, 25]);
442        assert_eq!(x.iter().join(", "), "10, 20, 25");
443    }
444
445    #[test]
446    fn test_to_vec() {
447        assert_eq!((0..5).to_vec(), vec![0, 1, 2, 3, 4]);
448    }
449
450    #[test]
451    fn test_charlen() {
452        assert_eq!("".charlen(), 0);
453        assert_eq!("12345".charlen(), 5);
454        assert_eq!("◄123►".to_string().charlen(), 5);
455    }
456
457    #[test]
458    fn test_add_space() {
459        let mut src = Vec::<String>::new();
460        src.add_space();
461        assert!(src.is_empty());
462        src.push("1".to_string());
463        assert_eq!(src, vec!["1".to_string()]);
464        src.add_space();
465        assert_eq!(src, vec!["1".to_string(), "".to_string()]);
466        src.add_space();
467        assert_eq!(src, vec!["1".to_string(), "".to_string()]);
468        src.push("2".to_string());
469        assert_eq!(src, vec!["1".to_string(), "".to_string(), "2".to_string()]);
470        src.add_space();
471        assert_eq!(src, vec!["1".to_string(), "".to_string(), "2".to_string(), "".to_string()]);
472        src.add_space();
473        assert_eq!(src, vec!["1".to_string(), "".to_string(), "2".to_string(), "".to_string()]);
474    }
475
476    #[test]
477    fn test_struct_libs() {
478        const VERBOSE: bool = false;
479        let mut l = StructLibs::new();
480        let l1 = ["a", "a::a1", "a::b1", "a::a1::a2", "a::a1::b2"];
481        let l2 = vec!["a::a1::a2::a3"];
482        let l3 = vec!["a::c1::a2".to_string()];
483        l.extend(l1);
484        l.add("b");
485        l.extend(l2);
486        l.extend(l3);
487        let tree = l.to_tree();
488        if VERBOSE {
489            println!("{}", tree.iter_post_depth_simple().map(|n| format!("({}){}", n.depth, n.deref())).join(", "));
490            println!("{}", StructLibs::tree_to_string(&tree, tree.get_root().unwrap()));
491        }
492        let src = l.gen_source_code();
493        if VERBOSE {
494            println!("{}", src.join("\n"));
495        }
496        assert_eq!(src, ["use a::{self, a1::{self, a2::{self, a3}, b2}, b1, c1::a2};", "use b;"]);
497
498        let src_empty = StructLibs::new().gen_source_code();
499        assert_eq!(src_empty, Vec::<String>::new());
500    }
501
502    #[test]
503    fn test_build_error() {
504        fn build() -> Result<(), BuildError> {
505            let mut log = BufLog::new();
506            log.add_error("the test generated a fake error successfully");
507            Err(BuildError::new(log, BuildErrorSource::ParserGen))
508        }
509        let err = build().err().expect("build() should return an error");
510        assert_eq!(err.to_string(), "Errors have occurred in ParserGen:\n- ERROR  : the test generated a fake error successfully\n");
511    }
512}
513
514// ---------------------------------------------------------------------------------------------