memoization/
memoization.rs

1//! Memoization example demonstrating performance benefits.
2//!
3//! This example shows how memoization can improve parsing performance
4//! for recursive grammars by caching parse results.
5//!
6//! Run with: cargo run --example memoization
7
8use sipha_core::{span::Span, token::Token as TokenStruct, traits::TokenKind};
9use sipha_error::ParseError;
10use sipha_memo::MemoTable;
11use sipha_parse::{helpers, Parser, ParserState};
12use sipha_tree::{NodeArena, RawNodeId};
13
14#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
15#[allow(dead_code)]
16enum Token {
17    Ident,
18    Plus,
19    LParen,
20    RParen,
21    Whitespace,
22}
23
24impl TokenKind for Token {
25    fn is_trivia(&self) -> bool {
26        matches!(self, Token::Whitespace)
27    }
28}
29
30#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
31enum Rule {
32    Expr,
33    Term,
34}
35
36fn main() {
37    let mut parser = Parser::create();
38
39    // Define a recursive expression grammar
40    parser.register_rule(
41        Rule::Term,
42        helpers::choice(vec![
43            helpers::token(Token::Ident),
44            helpers::delimited(Token::LParen, helpers::rule(Rule::Expr), Token::RParen),
45        ]),
46    );
47
48    parser.register_rule(
49        Rule::Expr,
50        helpers::seq(vec![
51            helpers::rule(Rule::Term),
52            helpers::many(helpers::seq(vec![
53                helpers::token(Token::Plus),
54                helpers::rule(Rule::Term),
55            ])),
56        ]),
57    );
58
59    // Create a token stream
60    let tokens = vec![
61        TokenStruct::create(Token::LParen, Span::new(0, 1), "(", Vec::new(), Vec::new()),
62        TokenStruct::create(Token::Ident, Span::new(1, 2), "a", Vec::new(), Vec::new()),
63        TokenStruct::create(Token::Plus, Span::new(2, 3), "+", Vec::new(), Vec::new()),
64        TokenStruct::create(Token::Ident, Span::new(3, 4), "b", Vec::new(), Vec::new()),
65        TokenStruct::create(Token::RParen, Span::new(4, 5), ")", Vec::new(), Vec::new()),
66    ];
67
68    // Parse normally
69    let mut arena: NodeArena<Token, Rule, RawNodeId> = NodeArena::new();
70    let mut state = ParserState::new(&tokens, &mut arena, false, ());
71
72    match parser.parse_rule(Rule::Expr, &mut state) {
73        Ok(_) => {
74            println!("✓ Successfully parsed!");
75        }
76        Err(e) => {
77            println!("✗ Parse error: {:?}", e);
78            return;
79        }
80    }
81
82    // Demonstrate memoization statistics API
83    let mut memo = MemoTable::<Token, Rule, RawNodeId>::new();
84
85    // Simulate some cache entries (in real usage, these would be populated during parsing)
86    memo.store_success(Rule::Term, 0, RawNodeId(0), 1);
87    memo.store_success(Rule::Expr, 0, RawNodeId(1), 3);
88    memo.store_failure(
89        Rule::Term,
90        5,
91        ParseError::UnexpectedEof {
92            span: Span::new(5, 5),
93            rule_context: Some(Rule::Term),
94            context_stack: vec![],
95        },
96        0,
97    );
98
99    // Get memoization statistics
100    let stats = memo.statistics();
101    println!("\nMemoization Statistics:");
102    println!("  Total entries: {}", stats.total_entries);
103    println!("  Success count: {}", stats.success_count);
104    println!("  Failure count: {}", stats.failure_count);
105    println!(
106        "  Estimated memory: {} bytes",
107        stats.estimated_memory_bytes()
108    );
109    println!("  Enabled: {}", stats.enabled);
110}
memoization/memoization.rs

memoization/
memoization.rs
