nom_recursive/
lib.rs

1//! `nom-recursive` is an extension of [nom](https://docs.rs/nom) to handle left recursion.
2//!
3//! ## Examples
4//!
5//! The following example show a quick example.
6//! If `#[recursive_parser]` is removed, stack overflow will occur because of infinite recursion.
7//!
8//! ```
9//! use nom::branch::*;
10//! use nom::character::complete::*;
11//! use nom::IResult;
12//! use nom_locate::LocatedSpan;
13//! use nom_recursive::{recursive_parser, RecursiveInfo};
14//!
15//! // Input type must implement trait HasRecursiveInfo
16//! // nom_locate::LocatedSpan<T, RecursiveInfo> implements it.
17//! type Span<'a> = LocatedSpan<&'a str, RecursiveInfo>;
18//!
19//! pub fn expr(s: Span) -> IResult<Span, String> {
20//!     alt((expr_binary, term))(s)
21//! }
22//!
23//! // Apply recursive_parser by custom attribute
24//! #[recursive_parser]
25//! pub fn expr_binary(s: Span) -> IResult<Span, String> {
26//!     let (s, x) = expr(s)?;
27//!     let (s, y) = char('+')(s)?;
28//!     let (s, z) = expr(s)?;
29//!     let ret = format!("{}{}{}", x, y, z);
30//!     Ok((s, ret))
31//! }
32//!
33//! pub fn term(s: Span) -> IResult<Span, String> {
34//!     let (s, x) = char('1')(s)?;
35//!     Ok((s, x.to_string()))
36//! }
37//!
38//! fn main() {
39//!     let ret = expr(LocatedSpan::new_extra("1+1", RecursiveInfo::new()));
40//!     println!("{:?}", ret.unwrap().1);
41//! }
42//! ```
43
44pub use nom_recursive_macros::recursive_parser;
45use std::collections::HashMap;
46
47#[cfg(all(not(feature = "tracer128"), not(feature = "tracer256"),))]
48const RECURSIVE_FLAG_WORDS: usize = 1;
49#[cfg(all(feature = "tracer128", not(feature = "tracer256"),))]
50const RECURSIVE_FLAG_WORDS: usize = 2;
51#[cfg(feature = "tracer256")]
52const RECURSIVE_FLAG_WORDS: usize = 4;
53
54pub struct RecursiveIndexes {
55    indexes: HashMap<&'static str, usize>,
56    next: usize,
57}
58
59impl RecursiveIndexes {
60    pub fn new() -> Self {
61        RecursiveIndexes {
62            indexes: HashMap::new(),
63            next: 0,
64        }
65    }
66
67    pub fn get(&mut self, key: &'static str) -> usize {
68        if let Some(x) = self.indexes.get(key) {
69            *x
70        } else {
71            let new_index = self.next;
72            assert!(new_index < RECURSIVE_FLAG_WORDS * 64, "Recursive tracers exceed the maximum number({}). Consider use feature `tracer128` or `tracer256` to extend it.", RECURSIVE_FLAG_WORDS * 64);
73            self.next += 1;
74            self.indexes.insert(key, new_index);
75            new_index
76        }
77    }
78}
79
80thread_local!(
81    pub static RECURSIVE_STORAGE: core::cell::RefCell<crate::RecursiveIndexes> = {
82        core::cell::RefCell::new(crate::RecursiveIndexes::new())
83    }
84);
85
86/// The type of payload used by recursive tracer
87#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
88pub struct RecursiveInfo {
89    flag: [u64; RECURSIVE_FLAG_WORDS],
90    ptr: *const u8,
91}
92
93impl Default for RecursiveInfo {
94    fn default() -> Self {
95        Self::new()
96    }
97}
98
99impl RecursiveInfo {
100    pub fn new() -> Self {
101        RecursiveInfo {
102            flag: [0; RECURSIVE_FLAG_WORDS],
103            ptr: std::ptr::null(),
104        }
105    }
106
107    pub fn check_flag(&self, id: usize) -> bool {
108        let upper = id / 64;
109        let lower = id % 64;
110        ((self.flag[upper] >> lower) & 1) == 1
111    }
112
113    pub fn set_flag(&mut self, id: usize) {
114        let upper = id / 64;
115        let lower = id % 64;
116
117        let val = 1u64 << lower;
118        let mask = !(1u64 << lower);
119
120        self.flag[upper] = (self.flag[upper] & mask) | val;
121    }
122
123    pub fn clear_flags(&mut self) {
124        for i in 0..self.flag.len() {
125            self.flag[i] = 0u64;
126        }
127    }
128
129    pub fn get_ptr(&self) -> *const u8 {
130        self.ptr
131    }
132
133    pub fn set_ptr(&mut self, ptr: *const u8) {
134        self.ptr = ptr;
135    }
136}
137
138/// Trait for recursive tracer
139///
140/// The input type of nom parser must implement this.
141pub trait HasRecursiveInfo {
142    fn get_recursive_info(&self) -> RecursiveInfo;
143    fn set_recursive_info(self, info: RecursiveInfo) -> Self;
144}
145
146impl HasRecursiveInfo for RecursiveInfo {
147    fn get_recursive_info(&self) -> RecursiveInfo {
148        *self
149    }
150
151    fn set_recursive_info(self, info: RecursiveInfo) -> Self {
152        info
153    }
154}
155
156impl<T, U> HasRecursiveInfo for nom_locate::LocatedSpan<T, U>
157where
158    U: HasRecursiveInfo,
159{
160    fn get_recursive_info(&self) -> RecursiveInfo {
161        self.extra.get_recursive_info()
162    }
163
164    fn set_recursive_info(mut self, info: RecursiveInfo) -> Self {
165        self.extra = self.extra.set_recursive_info(info);
166        self
167    }
168}
nom_recursive/lib.rs

nom_recursive/
lib.rs
