rdf_parsers/
lib.rs

1use std::borrow::Borrow;
2use std::fmt::Debug;
3use std::hash::Hash;
4use std::ops::{Deref, DerefMut};
5
6use logos::{Lexer, Logos};
7pub use parser::*;
8
9mod a_star;
10pub use a_star::Fingerprint;
11pub use a_star::ParseMode;
12pub use a_star::ParserTrait;
13pub mod list;
14pub mod model;
15pub mod format;
16pub mod jsonld;
17pub mod n3;
18pub mod ntriples;
19mod parser;
20pub mod sparql;
21pub mod trig;
22pub mod turtle;
23pub mod util;
24
25#[derive(Debug, Clone)]
26pub struct Spanned<T>(pub T, pub std::ops::Range<usize>);
27impl<T> Default for Spanned<T>
28where
29    T: Default,
30{
31    fn default() -> Self {
32        Self(T::default(), 0..1)
33    }
34}
35impl Borrow<str> for Spanned<String> {
36    #[inline]
37    fn borrow(&self) -> &str {
38        &self[..]
39    }
40}
41
42impl<T> Deref for Spanned<T> {
43    type Target = T;
44
45    fn deref(&self) -> &Self::Target {
46        &self.0
47    }
48}
49
50impl<T> DerefMut for Spanned<T> {
51    fn deref_mut(&mut self) -> &mut Self::Target {
52        &mut self.0
53    }
54}
55impl<T: PartialEq> PartialEq for Spanned<T> {
56    fn eq(&self, other: &Self) -> bool {
57        self.0.eq(&other.0)
58    }
59}
60impl<T: std::hash::Hash> std::hash::Hash for Spanned<T> {
61    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
62        self.0.hash(state)
63    }
64}
65impl<T: PartialEq> Eq for Spanned<T> {}
66
67impl<T> Spanned<T> {
68    pub fn into_value(self) -> T {
69        self.0
70    }
71    pub fn into_span(self) -> std::ops::Range<usize> {
72        self.1
73    }
74    pub fn value(&self) -> &T {
75        &self.0
76    }
77    pub fn value_mut(&mut self) -> &mut T {
78        &mut self.0
79    }
80    pub fn span(&self) -> &std::ops::Range<usize> {
81        &self.1
82    }
83
84    pub fn map<O>(self, f: impl Fn(T) -> O) -> Spanned<O> {
85        Spanned(f(self.0), self.1)
86    }
87    pub fn map_ref<'a, O: 'a>(&'a self, f: impl Fn(&'a T) -> O) -> Spanned<O> {
88        Spanned(f(&self.0), self.1.clone())
89    }
90    pub fn as_ref(&self) -> Spanned<&T> {
91        Spanned(&self.0, self.1.clone())
92    }
93    pub fn try_map_ref<'a, O>(&'a self, f: impl FnOnce(&'a T) -> Option<O>) -> Option<Spanned<O>> {
94        f(&self.0).map(|v| Spanned(v, self.1.clone()))
95    }
96    pub fn try_map<O>(self, f: impl FnOnce(T) -> Option<O>) -> Option<Spanned<O>> {
97        f(self.0).map(|v| Spanned(v, self.1))
98    }
99}
100
101impl<T> Spanned<Option<T>> {
102    pub fn transpose(self) -> Option<Spanned<T>> {
103        self.0.map(|inner| Spanned(inner, self.1))
104    }
105}
106
107pub fn spanned<T>(t: T, span: std::ops::Range<usize>) -> Spanned<T> {
108    Spanned(t, span)
109}
110
111pub trait TokenTrait:
112    Debug + Clone + Into<rowan::SyntaxKind> + From<rowan::SyntaxKind> + PartialEq + Eq + Hash + 'static
113{
114    const ERROR: Self;
115    const ROOT: Self;
116
117    fn branch(&self) -> u32;
118
119    fn skips(&self) -> bool;
120
121    fn starting_tokens(&self) -> &'static [Self];
122    fn ending_tokens(&self) -> &'static [Self];
123
124    /// Returns the minimum error cost this rule must incur when `tok` is the
125    /// current token.  Returns 0 if `tok` is reachable anywhere inside the
126    /// rule or the rule is nullable (can match zero tokens).  Returns a
127    /// positive value otherwise — the rule cannot make progress without
128    /// producing at least that much error cost.
129    ///
130    /// Used by `add_element_checked` to pre-charge elements before adding
131    /// them to the A* search.  Defaults to 0 (no pre-charging).
132    fn min_error_for_token(&self, _tok: &Self) -> isize {
133        0
134    }
135
136
137    /// Maximum `error_value` for this token kind across all grammar rules that
138    /// may match it.
139    ///
140    /// Must always return > 0: the A* cost model adds `error_value` on a miss
141    /// and nothing on a match, so matching is strictly cheaper when
142    /// `error_value > 0`.
143    /// Defaults to 2, matching the minimum terminal weight used in codegen.
144    fn max_error_value(&self) -> isize {
145        2
146    }
147
148    /// Minimum cost to complete this rule via insertions.  This is the sum of
149    /// error_values for all required terminals on the cheapest path through the
150    /// rule.  Used by `add_element_checked` to pre-charge elements that push
151    /// a rule the current token cannot start.  Defaults to `max_error_value()`.
152    fn min_completion_cost(&self) -> isize {
153        self.max_error_value()
154    }
155
156    /// Cost of deleting (skipping) this token during error recovery.
157    ///
158    /// Defaults to `5 × max_error_value()`.  Must be high enough that
159    /// matching tokens is always cheaper than deleting them, while still
160    /// cheaper than long cascades of error insertions.
161    fn deletion_cost(&self) -> isize {
162        self.max_error_value() * 5
163    }
164
165    /// Bracket nesting delta for this token kind.
166    ///
167    /// Returns +1 for opening brackets (`{`, `[`, `(`), -1 for closing
168    /// brackets (`}`, `]`, `)`), and 0 for all other tokens.  Used by the
169    /// incremental A* to track the bracket nesting depth at which each token
170    /// was parsed, enabling a one-time "context-shift" cost when a block of
171    /// tokens moves to a different nesting level between edits.
172    fn bracket_delta(&self) -> i8 {
173        0
174    }
175}
176
177pub fn tokenize<'a, K>(text: &'a str) -> Vec<FatToken<K>>
178where
179    K: TokenTrait + Logos<'a, Source = str>,
180    <K as Logos<'a>>::Extras: Default,
181{
182    let mut lexer: Lexer<'a, K> = Lexer::new(text);
183    let mut tokens: Vec<FatToken<K>> = Vec::new();
184    while let Some(t) = lexer.next() {
185        let kind = t.unwrap_or(K::ERROR);
186        let span = lexer.span();
187        if kind == K::ERROR {
188            if let Some(last) = tokens.last_mut() {
189                if last.kind == K::ERROR {
190                    let start = last.range.start;
191                    last.extend_to(span.end, text[start..span.end].to_string());
192                    continue;
193                }
194            }
195        }
196        tokens.push(FatToken::new(kind, span.clone(), text[span].to_string()));
197    }
198    tokens
199}
200
201pub fn parse<'a, T: a_star::ParserTrait + 'static>(
202    root: T,
203    text: &'a str,
204) -> (Parse, Vec<FatToken<T::Kind>>)
205where
206    T::Kind: Logos<'a, Source = str>,
207    <<T as a_star::ParserTrait>::Kind as Logos<'a>>::Extras: Default,
208{
209    let mut tokens = tokenize::<T::Kind>(text);
210    let list = a_star::a_star(
211        root,
212        &tokens,
213        IncrementalBias::default(),
214        a_star::DEFAULT_MAX_ITERATIONS,
215    );
216    let parse = Parse::from_steps(&mut tokens, list);
217    (parse, tokens)
218}
219
220/// Parses `text` in non-fault-tolerant fast mode.
221///
222/// Returns `Some((parse, tokens))` when the document is error-free, or `None`
223/// if any token could not be matched.  Use this when you know the document is
224/// correct and want maximum throughput — no error-recovery branches are
225/// explored, no prevInfo fingerprints are tracked, and no heuristic is
226/// precomputed.
227pub fn parse_fast<'a, T: a_star::ParserTrait + 'static>(
228    root: T,
229    text: &'a str,
230) -> Option<(Parse, Vec<FatToken<T::Kind>>)>
231where
232    T::Kind: Logos<'a, Source = str>,
233    <<T as a_star::ParserTrait>::Kind as Logos<'a>>::Extras: Default,
234{
235    let mut tokens = tokenize::<T::Kind>(text);
236    let list = a_star::a_star_fast(root, &tokens)?;
237    let parse = Parse::from_steps(&mut tokens, list);
238    Some((parse, tokens))
239}
240
241/// A single token from a previous parse, carrying the text, fingerprint, and
242/// bracket nesting depth needed for incremental re-parsing.
243pub struct PrevToken {
244    pub text: String,
245    pub fingerprint: Option<Fingerprint>,
246    /// Bracket nesting depth at which this token was parsed (0 = top level).
247    /// Used by the incremental A* to detect context-shifts (a block of tokens
248    /// moving to a different nesting level) and charge for them only once.
249    pub depth: u8,
250}
251
252/// Information from a previous parse needed for incremental re-parsing.
253pub struct PrevParseInfo {
254    pub tokens: Vec<PrevToken>,
255    /// Whether the previous parse produced any errors.  When true, stored
256    /// bracket depths are not used for conflict classification (they may be
257    /// misleading due to error-recovery changing the grammar context), so
258    /// fingerprint conflicts are treated as free-pass rather than +50 role
259    /// conflicts.
260    pub had_errors: bool,
261}
262
263/// Role-preservation bias applied in the A* search during incremental
264/// re-parsing.  When a token's previous `TermType` (Subject/Predicate/Object)
265/// agrees with the current parse context, cost is reduced by `strength`
266/// (a discount on the otherwise free match); when it conflicts, cost is
267/// increased by `strength` (a penalty).
268#[derive(Debug, Clone, Copy)]
269pub struct IncrementalBias {
270    /// Magnitude of the role-agreement bonus and role-conflict penalty.
271    /// Agreement: cost -= strength.  Conflict: cost += strength.
272    /// Must be > 0; use 0 to disable incremental bias entirely.
273    pub strength: isize,
274}
275
276impl Default for IncrementalBias {
277    fn default() -> Self {
278        Self { strength: 1 }
279    }
280}
281
282/// Like `parse_t_2` but, when `prev` is provided, diffs the token stream
283/// against the previous one and copies each old token's parse-time fingerprint
284/// onto the matching new token via `FatToken::set_old_kind`.  The A* scorer
285/// then uses `bias` to adjust scores for parses that agree or disagree with
286/// the previous token positions in the grammar rule stack.
287///
288/// Fast path: if the document is currently valid (fast parse succeeds), the
289/// fault-tolerant search and incremental diffing are skipped entirely.  The
290/// fast result is returned with a `PrevParseInfo` marked `had_errors = false`,
291/// so subsequent edits receive full incremental guidance.  This avoids the
292/// case where fingerprints from an error-recovery parse mislead the A* when
293/// the document later becomes valid again.
294pub fn parse_incremental<'a, T: a_star::ParserTrait + Clone + 'static>(
295    root: T,
296    text: &'a str,
297    prev: Option<&PrevParseInfo>,
298    bias: IncrementalBias,
299) -> (Parse, PrevParseInfo)
300where
301    T::Kind: Logos<'a, Source = str>,
302    <<T as a_star::ParserTrait>::Kind as Logos<'a>>::Extras: Default,
303{
304    // Fast path: document is currently valid — no error recovery needed.
305    if let Some((parse, tokens)) = parse_fast(root.clone(), text) {
306        let mut depth = 0i32;
307        let prev_info = PrevParseInfo {
308            tokens: tokens.iter().map(|t| {
309                let d = depth.clamp(0, 255) as u8;
310                depth += t.kind.bracket_delta() as i32;
311                t.to_prev_token(d)
312            }).collect(),
313            had_errors: false,
314        };
315        return (parse, prev_info);
316    }
317
318    let mut tokens = tokenize::<T::Kind>(text);
319
320    if let Some(prev) = prev {
321        // Build text slices for the differ.
322        let old_texts: Vec<&str> = prev.tokens.iter().map(|t| t.text.as_str()).collect();
323        let new_texts: Vec<&str> = tokens.iter().map(|t| t.text()).collect();
324
325        // Map new token index → old token index for Equal (unchanged) regions.
326        use similar::{Algorithm, DiffOp, capture_diff_slices};
327        let ops = capture_diff_slices(Algorithm::Myers, &old_texts, &new_texts);
328        let mut new_to_old = std::collections::HashMap::<usize, usize>::new();
329        for op in &ops {
330            if let DiffOp::Equal {
331                old_index,
332                new_index,
333                len,
334            } = op
335            {
336                for i in 0..*len {
337                    new_to_old.insert(new_index + i, old_index + i);
338                }
339            }
340        }
341
342        // Copy the old fingerprint and depth onto each unchanged new token.
343        // Depth is always copied: valid documents are handled by the fast
344        // path above, so fault-tolerant parses only reach this point for
345        // invalid documents.  In that case the previous depth information
346        // is still the best available guide for role-conflict detection.
347        for (new_idx, tok) in tokens.iter_mut().enumerate() {
348            if let Some(&old_idx) = new_to_old.get(&new_idx) {
349                if let Some(prev_tok) = prev.tokens.get(old_idx) {
350                    tok.set_old_kind(prev_tok.fingerprint);
351                    tok.set_old_depth(Some(prev_tok.depth));
352                }
353            }
354        }
355    }
356
357    let list = a_star::a_star(root, &tokens, bias, a_star::DEFAULT_MAX_ITERATIONS);
358    let parse = Parse::from_steps(&mut tokens, list);
359    let had_errors = parse.errors.len() > 0;
360    // Compute bracket depths for the new token sequence to populate PrevParseInfo.
361    let mut depth: i32 = 0;
362    let prev = PrevParseInfo {
363        tokens: tokens
364            .iter()
365            .map(|t| {
366                let d = depth.clamp(0, 255) as u8;
367                depth += t.kind.bracket_delta() as i32;
368                t.to_prev_token(d)
369            })
370            .collect(),
371        had_errors,
372    };
373    (parse, prev)
374}
rdf_parsers/lib.rs

rdf_parsers/
lib.rs
