1use pest::error::{Error, ErrorVariant, InputLocation};
2use pest::iterators::Pairs;
3use pest::{Parser as _, Position, Token};
4use pest_derive::Parser;
5
6#[derive(Parser)]
7#[grammar = "trilogy.pest"]
8pub struct TrilogyParser;
9
10pub const MAX_NESTING_DEPTH: usize = 256;
16
17pub const NESTING_LIMIT_MESSAGE: &str = "nesting depth limit reached";
19
20pub fn parse_bounded(text: &str) -> Result<Pairs<'_, Rule>, Box<Error<Rule>>> {
28 let pairs = TrilogyParser::parse(Rule::start, text).map_err(|e| match &e.variant {
29 ErrorVariant::CustomError { message } if message == "stack limit reached" => {
30 let pos = match e.location {
31 InputLocation::Pos(pos) | InputLocation::Span((pos, _)) => pos,
32 };
33 nesting_error(text, pos)
34 }
35 _ => Box::new(e),
36 })?;
37 match too_deep_at(pairs.clone()) {
38 Some(pos) => Err(nesting_error(text, pos)),
39 None => Ok(pairs),
40 }
41}
42
43fn too_deep_at(pairs: Pairs<'_, Rule>) -> Option<usize> {
44 let mut depth = 0usize;
45 for token in pairs.tokens() {
46 match token {
47 Token::Start { pos, .. } => {
48 depth += 1;
49 if depth > MAX_NESTING_DEPTH {
50 return Some(pos.pos());
51 }
52 }
53 Token::End { .. } => depth -= 1,
54 }
55 }
56 None
57}
58
59fn nesting_error(text: &str, pos: usize) -> Box<Error<Rule>> {
60 let message = format!(
61 "{NESTING_LIMIT_MESSAGE}: input is nested more than {MAX_NESTING_DEPTH} levels deep"
62 );
63 let pos = Position::new(text, pos).unwrap_or_else(|| Position::from_start(text));
64 Box::new(Error::new_from_pos(ErrorVariant::CustomError { message }, pos))
65}
66
67pub fn rule_calls(text: &str, max_calls: usize) -> Result<Option<usize>, Box<pest::error::Error<Rule>>> {
78 use pest::error::ErrorVariant;
79 use pest::Parser;
80 use std::num::NonZeroUsize;
81 use std::sync::Mutex;
82
83 static PROBE: Mutex<()> = Mutex::new(());
84 let _probe = PROBE.lock().unwrap_or_else(|e| e.into_inner());
85
86 let completes_within = |limit: usize| -> Result<bool, Box<pest::error::Error<Rule>>> {
87 pest::set_call_limit(NonZeroUsize::new(limit));
88 let result = TrilogyParser::parse(Rule::start, text);
89 pest::set_call_limit(None);
90 match result {
91 Ok(_) => Ok(true),
92 Err(e) => match &e.variant {
93 ErrorVariant::CustomError { message } if message == "call limit reached" => Ok(false),
94 _ => Err(Box::new(e)),
95 },
96 }
97 };
98 if !completes_within(max_calls)? {
99 return Ok(None);
100 }
101 let (mut low, mut high) = (1usize, max_calls);
102 while low < high {
103 let mid = low + (high - low) / 2;
104 if completes_within(mid)? {
105 high = mid;
106 } else {
107 low = mid + 1;
108 }
109 }
110 Ok(Some(low))
111}
112
113#[cfg(feature = "python")]
117mod python_impl {
118use super::Rule;
119use pest::iterators::Pair;
120use pyo3::prelude::*;
121use pyo3::types::{PyList, PyString, PyTuple};
122use std::collections::HashMap;
123use std::sync::Mutex;
124
125fn rename_rule(name: &str) -> &str {
126 match name {
127 "attr_access_paren" => "attr_access",
128 "_and_conditional" => "conditional",
129 other => other,
130 }
131}
132
133fn is_token_rule(name: &str) -> bool {
134 name.chars()
135 .find(|c| c.is_alphabetic())
136 .map(|c| c.is_ascii_uppercase())
137 .unwrap_or(false)
138}
139
140fn is_silent_token_rule(name: &str) -> bool {
144 name.starts_with('_')
145}
146
147struct RuleInfo {
148 name_py: Py<PyString>,
149 is_token: bool,
150 is_silent: bool,
151}
152
153static RULE_INFO_CACHE: Mutex<Option<HashMap<Rule, RuleInfo>>> = Mutex::new(None);
156
157fn rule_info(py: Python<'_>, rule: Rule) -> (Py<PyString>, bool, bool) {
158 let mut borrowed = RULE_INFO_CACHE.lock().unwrap();
159 let map = borrowed.get_or_insert_with(HashMap::new);
160 if let Some(info) = map.get(&rule) {
161 return (info.name_py.clone_ref(py), info.is_token, info.is_silent);
162 }
163 let raw = format!("{:?}", rule);
164 let renamed = rename_rule(&raw);
165 let is_token = is_token_rule(&raw);
166 let is_silent = is_token && is_silent_token_rule(&raw);
167 let name_py = PyString::intern(py, renamed).unbind();
168 let cloned = name_py.clone_ref(py);
169 map.insert(
170 rule,
171 RuleInfo {
172 name_py,
173 is_token,
174 is_silent,
175 },
176 );
177 (cloned, is_token, is_silent)
178}
179
180static STATIC_STR_CACHE: Mutex<Option<HashMap<&'static str, Py<PyString>>>> = Mutex::new(None);
183
184fn intern_static(py: Python<'_>, s: &'static str) -> Py<PyString> {
185 let mut borrowed = STATIC_STR_CACHE.lock().unwrap();
186 let map = borrowed.get_or_insert_with(HashMap::new);
187 if let Some(existing) = map.get(s) {
188 return existing.clone_ref(py);
189 }
190 let py_str = PyString::intern(py, s).unbind();
191 map.insert(s, py_str.clone_ref(py));
192 py_str
193}
194
195#[pyclass(module = "_preql_import_resolver")]
196pub struct PestNode {
197 data_py: Py<PyString>,
198 children_list: Py<PyList>,
199 #[pyo3(get)]
200 pub line: usize,
201 #[pyo3(get)]
202 pub column: usize,
203 #[pyo3(get)]
204 pub end_line: usize,
205 #[pyo3(get)]
206 pub end_column: usize,
207 #[pyo3(get)]
208 pub start_pos: usize,
209 #[pyo3(get)]
210 pub end_pos: usize,
211}
212
213#[pymethods]
214impl PestNode {
215 #[getter]
216 fn data(&self, py: Python<'_>) -> Py<PyString> {
217 self.data_py.clone_ref(py)
218 }
219
220 #[getter]
221 fn children<'py>(&self, py: Python<'py>) -> Bound<'py, PyList> {
222 self.children_list.bind(py).clone()
223 }
224
225 #[getter]
228 fn meta(slf: Py<Self>) -> Py<Self> {
229 slf
230 }
231
232 fn __repr__(&self, py: Python<'_>) -> String {
233 format!("PestNode({})", self.data_py.bind(py).to_string_lossy())
234 }
235}
236
237#[pyclass(module = "_preql_import_resolver")]
238pub struct PestToken {
239 type_name_py: Py<PyString>,
240 value_py: Py<PyString>,
241 #[pyo3(get)]
242 pub line: usize,
243 #[pyo3(get)]
244 pub column: usize,
245 #[pyo3(get)]
246 pub end_line: usize,
247 #[pyo3(get)]
248 pub end_column: usize,
249 #[pyo3(get)]
250 pub start_pos: usize,
251 #[pyo3(get)]
252 pub end_pos: usize,
253}
254
255#[pymethods]
256impl PestToken {
257 #[getter]
258 #[pyo3(name = "type")]
259 fn type_name(&self, py: Python<'_>) -> Py<PyString> {
260 self.type_name_py.clone_ref(py)
261 }
262
263 #[getter]
264 fn value(&self, py: Python<'_>) -> Py<PyString> {
265 self.value_py.clone_ref(py)
266 }
267
268 fn __repr__(&self, py: Python<'_>) -> String {
269 format!(
270 "PestToken({}={:?})",
271 self.type_name_py.bind(py).to_string_lossy(),
272 self.value_py.bind(py).to_string_lossy()
273 )
274 }
275
276 fn __str__(&self, py: Python<'_>) -> String {
277 self.value_py.bind(py).to_string_lossy().into_owned()
278 }
279}
280
281struct LineIndex {
287 char_byte_starts: Vec<usize>,
290 line_starts_char: Vec<usize>,
292}
293
294impl LineIndex {
295 fn new(text: &str) -> Self {
296 let mut char_byte_starts = Vec::with_capacity(text.len() + 1);
297 let mut line_starts_char = Vec::with_capacity(text.len() / 40 + 1);
298 line_starts_char.push(0);
299 let mut char_idx = 0usize;
300 for (byte_offset, ch) in text.char_indices() {
301 char_byte_starts.push(byte_offset);
302 if ch == '\n' {
303 line_starts_char.push(char_idx + 1);
304 }
305 char_idx += 1;
306 }
307 char_byte_starts.push(text.len());
308 Self {
309 char_byte_starts,
310 line_starts_char,
311 }
312 }
313
314 fn byte_to_char(&self, byte_pos: usize) -> usize {
315 match self.char_byte_starts.binary_search(&byte_pos) {
316 Ok(i) => i,
317 Err(i) => i - 1,
318 }
319 }
320
321 fn line_col(&self, byte_pos: usize) -> (usize, usize, usize) {
323 let char_pos = self.byte_to_char(byte_pos);
324 let idx = match self.line_starts_char.binary_search(&char_pos) {
325 Ok(i) => i,
326 Err(i) => i - 1,
327 };
328 let line_start = self.line_starts_char[idx];
329 (idx + 1, char_pos - line_start + 1, char_pos)
330 }
331}
332
333type SpanTuple = (usize, usize, usize, usize, usize, usize);
334
335fn span_positions(pair: &Pair<Rule>, idx: &LineIndex) -> SpanTuple {
336 let span = pair.as_span();
337 span_from_to(span.start(), span.end(), idx)
338}
339
340trait TreeBuilder {
344 fn node(&self, py: Python<'_>, name: Py<PyString>, children: Vec<Py<PyAny>>, span: SpanTuple) -> PyResult<Py<PyAny>>;
345 fn token(&self, py: Python<'_>, name: Py<PyString>, value: &str, span: SpanTuple) -> PyResult<Py<PyAny>>;
346}
347
348struct ClassBuilder;
349
350impl TreeBuilder for ClassBuilder {
351 fn node(&self, py: Python<'_>, name: Py<PyString>, children: Vec<Py<PyAny>>, span: SpanTuple) -> PyResult<Py<PyAny>> {
352 let (line, column, end_line, end_column, start_pos, end_pos) = span;
353 let node = PestNode {
354 data_py: name,
355 children_list: PyList::new(py, children)?.unbind(),
356 line,
357 column,
358 end_line,
359 end_column,
360 start_pos,
361 end_pos,
362 };
363 Ok(Py::new(py, node)?.into_any())
364 }
365
366 fn token(&self, py: Python<'_>, name: Py<PyString>, value: &str, span: SpanTuple) -> PyResult<Py<PyAny>> {
367 let (line, column, end_line, end_column, start_pos, end_pos) = span;
368 let token = PestToken {
369 type_name_py: name,
370 value_py: PyString::new(py, value).unbind(),
371 line,
372 column,
373 end_line,
374 end_column,
375 start_pos,
376 end_pos,
377 };
378 Ok(Py::new(py, token)?.into_any())
379 }
380}
381
382struct TupleBuilder;
388
389impl TreeBuilder for TupleBuilder {
390 fn node(&self, py: Python<'_>, name: Py<PyString>, children: Vec<Py<PyAny>>, span: SpanTuple) -> PyResult<Py<PyAny>> {
391 let (line, column, end_line, end_column, start_pos, end_pos) = span;
392 let children = PyTuple::new(py, children)?;
393 Ok((name, children, line, column, end_line, end_column, start_pos, end_pos)
394 .into_pyobject(py)?
395 .into_any()
396 .unbind())
397 }
398
399 fn token(&self, py: Python<'_>, name: Py<PyString>, value: &str, span: SpanTuple) -> PyResult<Py<PyAny>> {
400 let (line, column, end_line, end_column, start_pos, end_pos) = span;
401 let value_py = PyString::new(py, value).unbind();
402 Ok((name, value_py, line, column, end_line, end_column, start_pos, end_pos)
403 .into_pyobject(py)?
404 .into_any()
405 .unbind())
406 }
407}
408
409fn span_from_to(start_byte: usize, end_byte: usize, idx: &LineIndex) -> SpanTuple {
410 let (start_line, start_col, start_char) = idx.line_col(start_byte);
411 let (end_line, end_col, end_char) = idx.line_col(end_byte);
412 (start_line, start_col, end_line, end_col, start_char, end_char)
413}
414
415fn visible_children(pair: Pair<Rule>) -> Vec<Pair<Rule>> {
418 pair.into_inner()
419 .filter(|inner| {
420 let name = format!("{:?}", inner.as_rule());
421 !matches!(inner.as_rule(), Rule::EOI) && !(is_token_rule(&name) && is_silent_token_rule(&name))
422 })
423 .collect()
424}
425
426fn convert_children<B: TreeBuilder>(py: Python<'_>, pairs: Vec<Pair<Rule>>, idx: &LineIndex, b: &B) -> PyResult<Vec<Py<PyAny>>> {
427 pairs.into_iter().map(|p| convert_pair(py, p, idx, b)).collect()
428}
429
430fn paren_group_is_tuple(pair: &Pair<Rule>) -> bool {
435 let exprs: Vec<Pair<Rule>> = pair.clone().into_inner().collect();
436 if exprs.len() != 1 {
437 return true;
438 }
439 let text = pair.as_str();
440 let gap = &text[exprs[0].as_span().end() - pair.as_span().start()..];
441 let bytes = gap.as_bytes();
442 let mut i = 0;
443 while i < bytes.len() {
444 match bytes[i] {
445 b',' => return true,
446 b'#' => while i < bytes.len() && bytes[i] != b'\n' { i += 1 },
447 b'/' if bytes.get(i + 1) == Some(&b'/') => while i < bytes.len() && bytes[i] != b'\n' { i += 1 },
448 b'/' if bytes.get(i + 1) == Some(&b'*') => {
449 i += 2;
450 while i + 1 < bytes.len() && !(bytes[i] == b'*' && bytes[i + 1] == b'/') { i += 1 }
451 i += 1;
452 }
453 _ => {}
454 }
455 i += 1;
456 }
457 false
458}
459
460fn convert_paren_group<B: TreeBuilder>(py: Python<'_>, pair: Pair<Rule>, idx: &LineIndex, b: &B) -> PyResult<Py<PyAny>> {
461 let span = span_positions(&pair, idx);
462 let name = if paren_group_is_tuple(&pair) { "expr_tuple" } else { "parenthetical" };
463 let items = convert_children(py, visible_children(pair), idx, b)?;
464 b.node(py, intern_static(py, name), items, span)
465}
466
467fn convert_access_chain<B: TreeBuilder>(py: Python<'_>, pair: Pair<Rule>, idx: &LineIndex, b: &B) -> PyResult<Py<PyAny>> {
471 let span = span_positions(&pair, idx);
472 let mut inner = pair.into_inner();
473 let atom_pair = inner
474 .next()
475 .expect("access_chain must contain an atom as first child");
476
477 let mut inner = inner.peekable();
481 if matches!(inner.peek().map(|p| p.as_rule()), Some(Rule::conditional)) {
482 let conditional = inner.next().unwrap();
483 let bare = match atom_pair.as_rule() {
484 Rule::concept_lit => true,
485 Rule::paren_group => !paren_group_is_tuple(&atom_pair),
486 _ => false,
487 };
488 let head_pair = if bare {
489 atom_pair
490 .into_inner()
491 .next()
492 .expect("a parenthetical and a concept_lit each hold one child")
493 } else {
494 atom_pair
495 };
496 let head = convert_pair(py, head_pair, idx, b)?;
497 let cond = convert_pair(py, conditional, idx, b)?;
498 return b.node(py, intern_static(py, "filter_item"), vec![head, cond], span);
499 }
500
501 let mut tails: Vec<(Rule, Pair<Rule>)> = Vec::new();
502 for tail in inner {
503 let kind = tail.as_rule();
504 let payload = tail
505 .into_inner()
506 .next()
507 .expect("tail rule must have one payload child");
508 tails.push((kind, payload));
509 }
510
511 if tails.is_empty() {
512 return convert_pair(py, atom_pair, idx, b);
513 }
514
515 let atom_py = convert_pair(py, atom_pair, idx, b)?;
516
517 let tail_name = |kind: Rule, payload: &Pair<Rule>| -> &'static str {
518 match kind {
519 Rule::dot_tail => "attr_access",
520 Rule::bracket_tail => match payload.as_rule() {
521 Rule::int_lit => "index_access",
522 _ => "map_key_access",
523 },
524 Rule::dcolon_tail => "fcast",
525 _ => "chained_access",
526 }
527 };
528
529 let last_is_cast = matches!(tails.last().map(|(k, _)| *k), Some(Rule::dcolon_tail));
530
531 if tails.len() == 1 {
532 let (kind, payload) = tails.pop().unwrap();
533 let name = tail_name(kind, &payload);
534 let payload_py = convert_pair(py, payload, idx, b)?;
535 return b.node(py, intern_static(py, name), vec![atom_py, payload_py], span);
536 }
537
538 if last_is_cast {
539 let (_, cast_payload) = tails.pop().unwrap();
540 let inner_name: &'static str = if tails.len() == 1 {
541 let (k, p) = &tails[0];
542 tail_name(*k, p)
543 } else {
544 "chained_access"
545 };
546 let mut inner_items: Vec<Py<PyAny>> = Vec::with_capacity(tails.len() + 1);
547 inner_items.push(atom_py);
548 for (_, payload) in tails.into_iter() {
549 inner_items.push(convert_pair(py, payload, idx, b)?);
550 }
551 let inner_node = b.node(py, intern_static(py, inner_name), inner_items, span)?;
552 let cast_py = convert_pair(py, cast_payload, idx, b)?;
553 return b.node(py, intern_static(py, "fcast"), vec![inner_node, cast_py], span);
554 }
555
556 let mut items: Vec<Py<PyAny>> = Vec::with_capacity(tails.len() + 1);
557 items.push(atom_py);
558 for (_, payload) in tails.into_iter() {
559 items.push(convert_pair(py, payload, idx, b)?);
560 }
561 b.node(py, intern_static(py, "chained_access"), items, span)
562}
563
564fn convert_expr<B: TreeBuilder>(py: Python<'_>, pair: Pair<Rule>, idx: &LineIndex, b: &B) -> PyResult<Py<PyAny>> {
569 let span = span_positions(&pair, idx);
570 let children = visible_children(pair);
571 let is_between = children.len() == 3 && matches!(children[1].as_rule(), Rule::sum_operator);
572 let name = if is_between { "between_comparison" } else { "comparison" };
573 let items = convert_children(py, children, idx, b)?;
574 b.node(py, intern_static(py, name), items, span)
575}
576
577fn convert_select_chain<B: TreeBuilder>(py: Python<'_>, pair: Pair<Rule>, idx: &LineIndex, b: &B) -> PyResult<Py<PyAny>> {
581 let span = span_positions(&pair, idx);
582 let mut children = visible_children(pair);
583 if children.len() == 1 {
584 return convert_pair(py, children.pop().unwrap(), idx, b);
585 }
586 let items = convert_children(py, children, idx, b)?;
587 b.node(py, intern_static(py, "multi_select_statement"), items, span)
588}
589
590fn convert_aggregate_functions<B: TreeBuilder>(py: Python<'_>, pair: Pair<Rule>, idx: &LineIndex, b: &B) -> PyResult<Py<PyAny>> {
597 let (start_byte, end_byte) = (pair.as_span().start(), pair.as_span().end());
598 let (name_py, _, _) = rule_info(py, pair.as_rule());
599 let mut children = visible_children(pair);
600 let over_pair = match children.last().map(|c| c.as_rule()) {
601 Some(Rule::window_sql_over) => children.pop(),
602 _ => None,
603 };
604 let call_end = match (children.last(), &over_pair) {
605 (Some(last), _) if matches!(last.as_rule(), Rule::aggregate_over) => last.as_span().end(),
606 (_, Some(over)) => over.as_span().start(),
607 _ => end_byte,
608 };
609 let call_items = convert_children(py, children, idx, b)?;
610 let call = b.node(py, name_py, call_items, span_from_to(start_byte, call_end, idx))?;
611 let Some(over_pair) = over_pair else {
612 return Ok(call);
613 };
614 let span = span_from_to(start_byte, end_byte, idx);
615 let over = convert_pair(py, over_pair, idx, b)?;
616 let windowed = b.node(py, intern_static(py, "window_item_sql_aggregate"), vec![call, over], span)?;
617 b.node(py, intern_static(py, "window_item"), vec![windowed], span)
618}
619
620fn convert_pair<B: TreeBuilder>(py: Python<'_>, pair: Pair<Rule>, idx: &LineIndex, b: &B) -> PyResult<Py<PyAny>> {
621 match pair.as_rule() {
622 Rule::access_chain => return convert_access_chain(py, pair, idx, b),
623 Rule::expr => return convert_expr(py, pair, idx, b),
624 Rule::select_chain => return convert_select_chain(py, pair, idx, b),
625 Rule::aggregate_functions => return convert_aggregate_functions(py, pair, idx, b),
626 Rule::paren_group => return convert_paren_group(py, pair, idx, b),
627 _ => {}
628 }
629
630 let (name_py, is_token, _is_silent) = rule_info(py, pair.as_rule());
631 let span = span_positions(&pair, idx);
632
633 if is_token {
634 return b.token(py, name_py, pair.as_str(), span);
635 }
636 let mut items: Vec<Py<PyAny>> = Vec::new();
637 for inner in pair.into_inner() {
638 if matches!(inner.as_rule(), Rule::EOI) {
639 continue;
640 }
641 let (_, _, inner_silent) = rule_info(py, inner.as_rule());
642 if inner_silent {
643 continue;
644 }
645 items.push(convert_pair(py, inner, idx, b)?);
646 }
647 b.node(py, name_py, items, span)
648}
649
650fn parse_root<'i>(text: &'i str) -> PyResult<Pair<'i, Rule>> {
651 let mut pairs = super::parse_bounded(text).map_err(|e| {
652 PyErr::new::<pyo3::exceptions::PyValueError, _>(format!("{}", e))
653 })?;
654 pairs
655 .next()
656 .ok_or_else(|| PyErr::new::<pyo3::exceptions::PyValueError, _>("empty parse result"))
657}
658
659#[pyfunction]
662pub fn parse_trilogy_syntax(py: Python<'_>, text: &str) -> PyResult<Py<PyAny>> {
663 let idx = LineIndex::new(text);
664 let start = parse_root(text)?;
665 convert_pair(py, start, &idx, &ClassBuilder)
666}
667
668#[pyfunction]
670pub fn parse_trilogy_syntax_tuple(py: Python<'_>, text: &str) -> PyResult<Py<PyAny>> {
671 let idx = LineIndex::new(text);
672 let start = parse_root(text)?;
673 convert_pair(py, start, &idx, &TupleBuilder)
674}
675
676#[pyfunction]
680pub fn parse_trilogy_syntax_calls(text: &str, max_calls: usize) -> PyResult<usize> {
681 match super::rule_calls(text, max_calls) {
682 Ok(Some(calls)) => Ok(calls),
683 Ok(None) => Err(PyErr::new::<pyo3::exceptions::PyValueError, _>(format!(
684 "parse needs more than {max_calls} rule calls"
685 ))),
686 Err(e) => Err(PyErr::new::<pyo3::exceptions::PyValueError, _>(format!("{}", e))),
687 }
688}
689
690#[pyfunction]
694pub fn parse_trilogy_syntax_count(text: &str) -> PyResult<usize> {
695 let start = parse_root(text)?;
696 fn walk(pair: Pair<Rule>) -> usize {
697 let mut n = 1;
698 for inner in pair.into_inner() {
699 n += walk(inner);
700 }
701 n
702 }
703 Ok(walk(start))
704}
705}
706
707#[cfg(feature = "python")]
708pub use python_impl::{
709 parse_trilogy_syntax, parse_trilogy_syntax_calls, parse_trilogy_syntax_count,
710 parse_trilogy_syntax_tuple, PestNode, PestToken,
711};