edn/
lib.rs

1// Copyright 2016-2018 Mozilla
2//
3// Licensed under the Apache License, Version 2.0 (the "License"); you may not use
4// this file except in compliance with the License. You may obtain a copy of the
5// License at http://www.apache.org/licenses/LICENSE-2.0
6// Unless required by applicable law or agreed to in writing, software distributed
7// under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
8// CONDITIONS OF ANY KIND, either express or implied. See the License for the
9// specific language governing permissions and limitations under the License.
10
11extern crate bytes;
12extern crate chrono;
13extern crate hex;
14extern crate itertools;
15extern crate num;
16extern crate ordered_float;
17extern crate peg;
18extern crate pretty;
19#[cfg(feature = "serde_support")]
20extern crate serde;
21#[cfg(feature = "serde_support")]
22#[macro_use]
23extern crate serde_derive;
24extern crate uuid;
25
26pub mod depth;
27pub use crate::depth::{check_nesting, MAX_NESTING};
28pub mod entities;
29pub mod intern_set;
30pub use crate::intern_set::InternSet;
31// Intentionally not pub.
32pub mod matcher;
33mod namespaceable_name;
34pub mod pretty_print;
35pub mod query;
36pub mod symbols;
37pub mod types;
38pub mod utils;
39pub mod value_rc;
40pub use crate::value_rc::{Cloned, FromRc, ValueRc};
41
42// Re-export the types we use.
43use bytes::Bytes;
44pub use chrono::{DateTime, Utc};
45use hex::decode;
46pub use num::BigInt;
47pub use ordered_float::OrderedFloat;
48pub use uuid::Uuid;
49
50// Export from our modules.
51pub use crate::types::{
52    FromMicros, FromMillis, Span, SpannedValue, ToMicros, ToMillis, Value, ValueAndSpan,
53};
54
55pub use crate::symbols::{Keyword, NamespacedSymbol, PlainSymbol};
56
57use std::collections::{BTreeMap, BTreeSet, LinkedList};
58use std::iter::FromIterator;
59
60use chrono::TimeZone;
61
62use crate::entities::*;
63use crate::query::FromValue;
64
65// Goal: Be able to parse https://github.com/edn-format/edn
66// Also extensible to help parse http://docs.datomic.com/query.html
67
68// Debugging hint: test using `cargo test --features peg/trace -- --nocapture`
69// to trace where the parser is failing
70
71// TODO: Support tagged elements
72// TODO: Support discard
73
74pub type ParseError = peg::error::ParseError<peg::str::LineCol>;
75
76/// One item of an `:in` clause: a source var (`$`, `$named`) or a binding form.
77/// The grammar partitions these into `in_sources` and `in_bindings`.
78enum InItem {
79    Source(query::SrcVar),
80    Binding(query::Binding),
81}
82
83peg::parser!(grammar grammar() for str {
84
85    pub rule nil() -> SpannedValue = "nil" { SpannedValue::Nil }
86    pub rule nan() -> SpannedValue = "#f" whitespace()+ "NaN" { SpannedValue::Float(OrderedFloat(f64::NAN)) }
87
88    pub rule infinity() -> SpannedValue = "#f" whitespace()+ s:$(sign()) "Infinity"
89        { SpannedValue::Float(OrderedFloat(if s == "+" { f64::INFINITY } else { f64::NEG_INFINITY })) }
90
91    pub rule boolean() -> SpannedValue
92        = "true"  { SpannedValue::Boolean(true) }
93        / "false" { SpannedValue::Boolean(false) }
94
95    rule digit() = ['0'..='9']
96    rule alphanumeric() = ['0'..='9' | 'a'..='z' | 'A'..='Z']
97    rule octaldigit() = ['0'..='7']
98    rule validbase() = ['3']['0'..='6'] / ['1' | '2']['0'..='9'] / ['2'..='9']
99    rule hex() = ['0'..='9' | 'a'..='f' | 'A'..='F']
100    rule sign() = ['+' | '-']
101
102    pub rule raw_bigint() -> BigInt = b:$( sign()? digit()+ ) "N"
103        { b.parse::<BigInt>().unwrap() }
104    pub rule raw_octalinteger() -> i64 = "0" i:$( octaldigit()+ )
105        { i64::from_str_radix(i, 8).unwrap() }
106    pub rule raw_hexinteger() -> i64 = "0x" i:$( hex()+ )
107        { i64::from_str_radix(i, 16).unwrap() }
108    pub rule raw_basedinteger() -> i64 = b:$( validbase() ) "r" i:$( alphanumeric()+ )
109        { i64::from_str_radix(i, b.parse::<u32>().unwrap()).unwrap() }
110    pub rule raw_integer() -> i64 = i:$( sign()? digit()+ ) !("." / (['e' | 'E']))
111        { i.parse::<i64>().unwrap() }
112    pub rule raw_float() -> OrderedFloat<f64> = f:$(sign()? digit()+ ("." digit()+)? (['e' | 'E'] sign()? digit()+)?)
113        { OrderedFloat(f.parse::<f64>().unwrap()) }
114
115    pub rule bigint() -> SpannedValue = v:raw_bigint() { SpannedValue::BigInteger(v) }
116    pub rule octalinteger() -> SpannedValue = v:raw_octalinteger() { SpannedValue::Integer(v) }
117    pub rule hexinteger() -> SpannedValue = v:raw_hexinteger() { SpannedValue::Integer(v) }
118    pub rule basedinteger() -> SpannedValue = v:raw_basedinteger() { SpannedValue::Integer(v) }
119    pub rule integer() -> SpannedValue = v:raw_integer() { SpannedValue::Integer(v) }
120    pub rule float() -> SpannedValue = v:raw_float() { SpannedValue::Float(v) }
121
122    rule number() -> SpannedValue = ( bigint() / basedinteger() / hexinteger() / octalinteger() / integer() / float() )
123
124    // TODO: standalone characters: \<char>, \newline, \return, \space and \tab.
125    // rule string_standalone_chars() ->
126    // The escape must be *translated*, not echoed: matching the backslash and
127    // returning the following character verbatim yields the LETTERS 'n'/'t'/'r'
128    // instead of the control characters they denote, so "a\nb" unescaped to
129    // "anb" -- silent data loss for any string carrying a newline or tab.
130    // `\\` and `\"` are their own translation, hence the passthrough arm.
131    rule string_special_char() -> &'input str = "\\" c:$(['\\' | '"' | 'n' | 't' | 'r']) {
132        match c {
133            "n" => "\n",
134            "t" => "\t",
135            "r" => "\r",
136            literal => literal,
137        }
138    }
139    rule string_normal_chars() -> &'input str = c:$((!['\"' | '\\'][_])+) { c }
140
141    // This is what we need to do in order to unescape. We can't just match the entire string slice:
142    // we get a Vec<&str> from rust-peg, where some parts might be unescaped special characters and
143    // we join it together to form an output string.
144    // E.g., input = r#"\"foo\\\\bar\""#
145    //      output = [quote, "foo", backslash, "bar", quote]
146    //      result = r#""foo\\bar""#
147    // For the typical case, string_normal_chars will match multiple, leading to a single-element vec.
148    pub rule raw_text() -> String = "\"" t:((string_special_char() / string_normal_chars())*) "\""
149        {  t.join("") }
150
151    pub rule text() -> SpannedValue
152        = v:raw_text() { SpannedValue::Text(v) }
153
154    // RFC 3339 timestamps. #inst "1985-04-12T23:20:50.52Z"
155    // We accept an arbitrary depth of decimals.
156    // TODO: Note that we discard the timezone information -- all times are translated to UTC.  Should we?
157    rule inst_string() -> DateTime<Utc> =
158        "#inst" whitespace()+ "\"" d:$( ['0'..='9']*<4> "-" ['0'..='2']['0'..='9'] "-" ['0'..='3']['0'..='9']
159                "T"
160                ['0'..='2']['0'..='9'] ":" ['0'..='5']['0'..='9'] ":" ['0'..='6']['0'..='9']
161                ("." ['0'..='9']+)?
162                ("Z" / (("+" / "-") ['0'..='2']['0'..='9'] ":" ['0'..='5']['0'..='9']))
163            )
164        "\"" {?
165            DateTime::parse_from_rfc3339(d)
166                .map(|t| t.with_timezone(&Utc))
167                .map_err(|_| "invalid datetime")        // TODO Oh, rustpeg.
168        }
169
170    rule inst_micros() -> DateTime<Utc> =
171        "#instmicros" whitespace()+ d:$( digit()+ ) {
172            let micros = d.parse::<i64>().unwrap();
173            let seconds: i64 = micros / 1_000_000;
174            let nanos: u32 = ((micros % 1_000_000).unsigned_abs() as u32) * 1000;
175            Utc.timestamp_opt(seconds, nanos).unwrap()
176        }
177
178    rule inst_millis() -> DateTime<Utc> =
179        "#instmillis" whitespace()+ d:$( digit()+ ) {
180            let millis = d.parse::<i64>().unwrap();
181            let seconds: i64 = millis / 1000;
182            let nanos: u32 = ((millis % 1000).unsigned_abs() as u32) * 1_000_000;
183            Utc.timestamp_opt(seconds, nanos).unwrap()
184        }
185
186    rule inst() -> SpannedValue = t:(inst_millis() / inst_micros() / inst_string())
187        { SpannedValue::Instant(t) }
188
189    rule uuid_string() -> Uuid =
190        "\"" u:$( ['a'..='f' | '0'..='9']*<8> "-" ['a'..='f' | '0'..='9']*<4> "-" ['a'..='f' | '0'..='9']*<4> "-" ['a'..='f' | '0'..='9']*<4> "-" ['a'..='f' | '0'..='9']*<12> ) "\"" {
191            Uuid::parse_str(u).expect("this is a valid UUID string")
192        }
193
194    pub rule uuid() -> SpannedValue = "#uuid" whitespace()+ u:uuid_string()
195        { SpannedValue::Uuid(u) }
196
197    rule byte_buffer() -> Bytes =
198        u:$( hex()+ ) {
199            let b = decode(u).expect("this is a valid hex byte string");
200            Bytes::copy_from_slice(&b)
201        }
202    pub rule bytes() -> SpannedValue = "#bytes" whitespace()+ u:byte_buffer()
203        { SpannedValue::Bytes(u) }
204
205    rule namespace_divider() = "."
206    rule namespace_separator() = "/"
207
208    // TODO: Be more picky here.
209    // Keywords follow the rules of symbols, except they can (and must) begin with :
210    // e.g. :fred or :my/fred. See https://github.com/edn-format/edn#keywords
211    rule symbol_char_initial() = ['a'..='z' | 'A'..='Z' | '0'..='9' | '*' | '!' | '_' | '?' | '$' | '%' | '&' | '=' | '<' | '>']
212    rule symbol_char_subsequent() = ['+' | 'a'..='z' | 'A'..='Z' | '0'..='9' | '*' | '!' | '_' | '?' | '$' | '%' | '&' | '=' | '<' | '>' | '-']
213
214    rule symbol_namespace() = symbol_char_initial() symbol_char_subsequent()* (namespace_divider() symbol_char_subsequent()+)*
215    rule symbol_name() = ( symbol_char_initial()+ symbol_char_subsequent()* )
216    // EDN: `+`, `-` and `/` are symbols, and so is `+x`/`-x` when the second
217    // character isn't a digit (`-5` stays an integer: value() tries number()
218    // first). Without this, `(+ ?a 1)` was a parse error.
219    rule sign_symbol_name() = ['+' | '-'] !['0'..='9'] symbol_char_subsequent()*
220    rule plain_symbol_name() = symbol_name() / "..." / "." / sign_symbol_name() / "/"
221
222    rule keyword_prefix() = ":"
223
224    pub rule symbol() -> SpannedValue =
225        ns:( sns:$(symbol_namespace()) namespace_separator() { sns })?
226        n:$(plain_symbol_name())
227        { SpannedValue::from_symbol(ns, n) }
228        / expected!("symbol")
229
230    pub rule keyword() -> SpannedValue =
231        keyword_prefix()
232        ns:( sns:$(symbol_namespace()) namespace_separator() { sns })?
233        n:$(symbol_name())
234        { SpannedValue::from_keyword(ns, n) }
235        / expected!("keyword")
236
237    pub rule list() -> SpannedValue = "(" __ v:(value())* __ ")"
238        { SpannedValue::List(LinkedList::from_iter(v)) }
239
240    pub rule vector() -> SpannedValue = "[" __ v:(value())* __ "]"
241        { SpannedValue::Vector(v) }
242
243    pub rule set() -> SpannedValue = "#{" __ v:(value())* __ "}"
244        { SpannedValue::Set(BTreeSet::from_iter(v)) }
245
246    pub rule pair() -> (ValueAndSpan, ValueAndSpan) =
247        k:(value()) v:(value()) {
248            (k, v)
249        }
250
251    pub rule map() -> SpannedValue = "{" __ v:(pair())* __ "}"
252        { SpannedValue::Map(BTreeMap::from_iter(v)) }
253
254    // Note: It's important that float comes before integer or the parser assumes that floats are integers and fails to parse.
255    pub rule value() -> ValueAndSpan =
256        __ start:position!() v:(nil() / nan() / infinity() / boolean() / number() / inst() / uuid() / bytes() / text() / keyword() / symbol() / list() / vector() / map() / set()  ) end:position!() __ {
257            ValueAndSpan {
258                inner: v,
259                span: Span::new(start, end)
260            }
261        }
262        / expected!("value")
263
264    rule atom() -> ValueAndSpan
265        = v:value() {? if v.is_atom() { Ok(v) } else { Err("expected atom") } }
266
267    // Clojure (and thus EDN) regards commas as whitespace, and thus the two-element vectors [1 2] and
268    // [1,,,,2] are equivalent, as are the maps {:a 1, :b 2} and {:a 1 :b 2}.
269    rule whitespace() = quiet!{[' ' | '\r' | '\n' | '\t' | ',']}
270    rule comment() = quiet!{";" (!['\r' | '\n'][_])* ['\r' | '\n']?}
271
272    rule __() = (whitespace() / comment())*
273
274    // Transaction entity parser starts here.
275
276    pub rule op() -> OpType
277        = ":db/add"     { OpType::Add }
278        / ":db/retract" { OpType::Retract }
279
280    // Recognize a built-in transaction-function keyword. Both the Datomic
281    // `:db.fn/*` spelling and the shorthand `:db/*` spelling are accepted.
282    rule builtin_tx_fn() -> BuiltinTxFn
283        = ":db.fn/cas"          { BuiltinTxFn::Cas }
284        / ":db/cas"             { BuiltinTxFn::Cas }
285        / ":db.fn/retractEntity" { BuiltinTxFn::RetractEntity }
286        / ":db/retractEntity"    { BuiltinTxFn::RetractEntity }
287
288    rule raw_keyword() -> Keyword =
289        keyword_prefix()
290        ns:( sns:$(symbol_namespace()) namespace_separator() { sns })?
291        n:$(symbol_name()) {
292            match ns {
293                Some(ns) => Keyword::namespaced(ns, n),
294                None => Keyword::plain(n),
295            }
296        }
297        / expected!("keyword")
298
299    rule raw_forward_keyword() -> Keyword
300        = v:raw_keyword() {? if v.is_forward() { Ok(v) } else { Err("expected :forward or :forward/keyword") } }
301
302    rule raw_backward_keyword() -> Keyword
303        = v:raw_keyword() {? if v.is_backward() { Ok(v) } else { Err("expected :_backward or :backward/_keyword") } }
304
305    rule raw_namespaced_keyword() -> Keyword
306        = keyword_prefix() ns:$(symbol_namespace()) namespace_separator() n:$(symbol_name()) { Keyword::namespaced(ns, n) }
307        / expected!("namespaced keyword")
308
309    rule raw_forward_namespaced_keyword() -> Keyword
310        = v:raw_namespaced_keyword() {? if v.is_forward() { Ok(v) } else { Err("expected namespaced :forward/keyword") } }
311
312    rule raw_backward_namespaced_keyword() -> Keyword
313        = v:raw_namespaced_keyword() {? if v.is_backward() { Ok(v) } else { Err("expected namespaced :backward/_keyword") } }
314
315    rule entid() -> EntidOrIdent
316        = v:( raw_basedinteger() / raw_hexinteger() / raw_octalinteger() / raw_integer() ) { EntidOrIdent::Entid(v) }
317        / v:raw_namespaced_keyword() { EntidOrIdent::Ident(v) }
318        / expected!("entid")
319
320    rule forward_entid() -> EntidOrIdent
321        = v:( raw_basedinteger() / raw_hexinteger() / raw_octalinteger() / raw_integer() ) { EntidOrIdent::Entid(v) }
322        / v:raw_forward_namespaced_keyword() { EntidOrIdent::Ident(v) }
323        / expected!("forward entid")
324
325    rule backward_entid() -> EntidOrIdent
326        = v:raw_backward_namespaced_keyword() { EntidOrIdent::Ident(v.to_reversed()) }
327        / expected!("backward entid")
328
329    rule lookup_ref() -> LookupRef<ValueAndSpan>
330        = "(" __ "lookup-ref" __ a:(entid()) __ v:(value()) __ ")" { LookupRef { a: AttributePlace::Entid(a), v } }
331        / expected!("lookup-ref")
332
333    // Datomic's `[a v]` lookup ref (#152). Only in entity position: in value position a
334    // vector may also be a list of values, so the transactor decides from the schema.
335    rule vector_lookup_ref() -> LookupRef<ValueAndSpan>
336        = "[" __ a:(raw_namespaced_keyword()) __ v:(atom()) __ "]" { LookupRef { a: AttributePlace::Entid(EntidOrIdent::Ident(a)), v } }
337
338    rule tx_function() -> TxFunction
339        = "(" __ n:$(symbol_name()) __ ")" { TxFunction { op: PlainSymbol::plain(n) } }
340
341    rule entity_place() -> EntityPlace<ValueAndSpan>
342        = v:raw_text() { EntityPlace::TempId(TempId::External(v).into()) }
343        / v:entid() { EntityPlace::Entid(v) }
344        / v:lookup_ref() { EntityPlace::LookupRef(v) }
345        / v:vector_lookup_ref() { EntityPlace::LookupRef(v) }
346        / v:tx_function() { EntityPlace::TxFunction(v) }
347
348    rule value_place_pair() -> (EntidOrIdent, ValuePlace<ValueAndSpan>)
349        = k:(entid()) __ v:(value_place()) { (k, v) }
350
351    rule map_notation() -> MapNotation<ValueAndSpan>
352        = "{" __ kvs:(value_place_pair()*) __ "}" { kvs.into_iter().collect() }
353
354    rule value_place() -> ValuePlace<ValueAndSpan>
355        = __ v:lookup_ref() __ { ValuePlace::LookupRef(v) }
356        / __ v:tx_function() __ { ValuePlace::TxFunction(v) }
357        / __ "[" __ vs:(value_place()*) __ "]" __ { ValuePlace::Vector(vs) }
358        / __ v:map_notation() __ { ValuePlace::MapNotation(v) }
359        / __ v:atom() __ { ValuePlace::Atom(v) }
360
361    pub rule entity() -> Entity<ValueAndSpan>
362        = __ "[" __ fun:(builtin_tx_fn()) __ args:(value_place()*) __ "]" __ { Entity::TxFunction { fun, args } }
363        / __ "[" __ op:(op()) __ e:(entity_place()) __ a:(forward_entid())  __ v:(value_place()) __  "]" __ { Entity::AddOrRetract { op, e, a: AttributePlace::Entid(a), v } }
364        / __ "[" __ op:(op()) __ e:(value_place())  __ a:(backward_entid()) __ v:(entity_place()) __ "]" __ { Entity::AddOrRetract { op, e: v, a: AttributePlace::Entid(a), v: e } }
365        / __ map:map_notation() __ { Entity::MapNotation(map) }
366        / expected!("entity")
367
368    pub rule entities() -> Vec<Entity<ValueAndSpan>>
369        = __ "[" __ es:(entity()*) __ "]" __ { es }
370
371    // Query parser starts here.
372    //
373    // We expect every rule except the `raw_*` rules to eat whitespace
374    // (with `__`) at its start and finish.  That means that every string
375    // pattern (say "[") should be bracketed on either side with either a
376    // whitespace-eating rule or an explicit whitespace eating `__`.
377
378    // `+`, `-` and `/` don't start like other symbols (symbol_char_initial);
379    // name them so the arithmetic where-fns [(+ ?a ?b) ?c] etc. parse.
380    rule query_function() -> query::QueryFunction
381        = __ n:$(symbol_name() / "+" / "-" / "/") __ {? query::QueryFunction::from_symbol(&PlainSymbol::plain(n)).ok_or("expected query function") }
382
383    rule fn_arg() -> query::FnArg
384        = v:value() {? query::FnArg::from_value(&v).ok_or("expected query function argument") }
385        / __ "[" args:fn_arg()+ "]" __ { query::FnArg::Vector(args) }
386
387    rule find_elem() -> query::Element
388        = __ v:variable() __ { query::Element::Variable(v) }
389        / __ "(" __ "the" v:variable() ")" __ { query::Element::Corresponding(v) }
390        / __ "(" __ "pull" var:variable() patterns:pull_pattern() ")" __ { query::Element::Pull(query::Pull { var, patterns }) }
391        / __ "(" func:query_function() args:fn_arg()* ")" __ { query::Element::Aggregate(query::Aggregate { func, args }) }
392
393    rule find_spec() -> query::FindSpec
394        = f:find_elem() "." __ { query::FindSpec::FindScalar(f) }
395        / fs:find_elem()+ { query::FindSpec::FindRel(fs) }
396        / __ "[" f:find_elem() __ "..." __ "]" __ { query::FindSpec::FindColl(f) }
397        / __ "[" fs:find_elem()+ "]" __ { query::FindSpec::FindTuple(fs) }
398
399    /// A pull pattern on its own, e.g. `[:person/name {:person/friend [*]}]`.
400    pub rule pull_pattern() -> Vec<query::PullAttributeSpec>
401        = __ "[" patterns:pull_attribute()+ "]" __ { patterns.into_iter().flatten().collect() }
402
403    // One pattern item; a map spec `{:a [..] :b [..]}` yields one spec per entry.
404    rule pull_attribute() -> Vec<query::PullAttributeSpec>
405        = __ "*" __ { vec![query::PullAttributeSpec::Wildcard] }
406        / a:pull_keyword() alias:(":as" __ alias:raw_forward_keyword() __ { alias })? {
407            vec![query::PullAttributeSpec::Attribute(query::NamedPullAttribute {
408                alias: alias.map(::std::rc::Rc::new),
409                ..a
410            })]
411        }
412        / __ "{" es:pull_map_entry()+ "}" __ { es }
413
414    rule pull_map_entry() -> query::PullAttributeSpec
415        = a:pull_keyword() p:pull_pattern() { query::PullAttributeSpec::Nested(a, p) }
416
417    rule pull_keyword() -> query::NamedPullAttribute
418        = __ k:raw_backward_namespaced_keyword() __ {
419            // Reverse pull, e.g. `:person/_friends`. Store the *forward* ident
420            // (k.to_reversed()) for schema lookup and mark it reverse.
421            query::NamedPullAttribute {
422                attribute: query::PullConcreteAttribute::Ident(::std::rc::Rc::new(k.to_reversed())),
423                alias: None,
424                reverse: true,
425            }
426        }
427        / __ k:raw_forward_namespaced_keyword() __ {
428            query::NamedPullAttribute {
429                attribute: query::PullConcreteAttribute::Ident(::std::rc::Rc::new(k)),
430                alias: None,
431                reverse: false,
432            }
433        }
434
435    rule limit() -> query::Limit
436        = __ v:variable() __ { query::Limit::Variable(v) }
437        / __ n:(raw_octalinteger() / raw_hexinteger() / raw_basedinteger() / raw_integer()) __ {?
438            if n > 0 {
439                Ok(query::Limit::Fixed(n as u64))
440            } else {
441                Err("expected positive integer")
442            }
443        }
444
445    rule offset() -> query::Offset
446        = __ v:variable() __ { query::Offset::Variable(v) }
447        / __ n:(raw_octalinteger() / raw_hexinteger() / raw_basedinteger() / raw_integer()) __ {?
448            if n >= 0 {
449                Ok(query::Offset::Fixed(n as u64))
450            } else {
451                Err("expected non-negative integer")
452            }
453        }
454
455    rule order() -> query::Order
456        = __ "(" __ "asc" v:variable() ")" __ { query::Order(query::Direction::Ascending, v) }
457        / __ "(" __ "desc" v:variable() ")" __ { query::Order(query::Direction::Descending, v) }
458        / v:variable() { query::Order(query::Direction::Ascending, v) }
459
460
461    rule pattern_value_place() -> query::PatternValuePlace
462        = v:value() {? query::PatternValuePlace::from_value(&v).ok_or("expected pattern_value_place") }
463
464    rule pattern_non_value_place() -> query::PatternNonValuePlace
465        = v:value() {? query::PatternNonValuePlace::from_value(&v).ok_or("expected pattern_non_value_place") }
466
467    rule pattern() -> query::WhereClause
468        = __ "["
469          src:src_var()?
470          e:pattern_non_value_place()
471          a:pattern_non_value_place()
472          v:pattern_value_place()?
473          tx:pattern_non_value_place()?
474          added:pattern_non_value_place()?
475        "]" __
476        {?
477            let v = v.unwrap_or(query::PatternValuePlace::Placeholder);
478            let tx = tx.unwrap_or(query::PatternNonValuePlace::Placeholder);
479            let added = added.unwrap_or(query::PatternNonValuePlace::Placeholder);
480
481            // Pattern::new takes care of reversal of reversed
482            // attributes: [?x :foo/_bar ?y] turns into
483            // [?y :foo/bar ?x].
484            //
485            // This is a bit messy: the inner conversion to a Pattern can
486            // fail if the input is something like
487            //
488            // ```edn
489            // [?x :foo/_reversed 23.4]
490            // ```
491            //
492            // because
493            //
494            // ```edn
495            // [23.4 :foo/reversed ?x]
496            // ```
497            //
498            // is nonsense. That leaves us with a nested optional, which we unwrap here.
499            query::Pattern::new(src, e, a, v, tx, added)
500                .map(query::WhereClause::Pattern)
501                .ok_or("expected pattern")
502        }
503
504    // TODO: This shouldn't be checked at parse time.
505    rule rule_vars() -> BTreeSet<query::Variable>
506        = vs:variable()+ {?
507            let given = vs.len();
508            let set: BTreeSet<query::Variable> = vs.into_iter().collect();
509            if given != set.len() {
510                Err("expected unique variables")
511            } else {
512                Ok(set)
513            }
514        }
515
516    rule or_pattern_clause() -> query::OrWhereClause
517        = clause:where_clause() { query::OrWhereClause::Clause(clause) }
518
519    rule or_and_clause() -> query::OrWhereClause
520        = __ "(" __ "and" clauses:where_clause()+ ")" __ { query::OrWhereClause::And(clauses) }
521
522    rule or_where_clause() -> query::OrWhereClause
523        = or_pattern_clause()
524        / or_and_clause()
525
526    rule or_clause() -> query::WhereClause
527        = __ "(" __ "or" clauses:or_where_clause()+ ")" __ {
528             query::WhereClause::OrJoin(query::OrJoin::new(query::UnifyVars::Implicit, clauses))
529        }
530
531    rule or_join_clause() -> query::WhereClause
532        = __ "(" __ "or-join" __ "[" vars:rule_vars() "]" clauses:or_where_clause()+ ")" __ {
533             query::WhereClause::OrJoin(query::OrJoin::new(query::UnifyVars::Explicit(vars), clauses))
534        }
535
536    rule not_clause() -> query::WhereClause
537        = __ "(" __ "not" clauses:where_clause()+ ")" __ {
538             query::WhereClause::NotJoin(query::NotJoin::new(query::UnifyVars::Implicit, clauses))
539        }
540
541    rule not_join_clause() -> query::WhereClause
542        = __ "(" __ "not-join" __ "[" vars:rule_vars() "]" clauses:where_clause()+ ")" __ {
543             query::WhereClause::NotJoin(query::NotJoin::new(query::UnifyVars::Explicit(vars), clauses))
544        }
545
546    rule type_annotation() -> query::WhereClause
547        = __ "[" __ "(" __ "type" var:variable() __ ty:raw_keyword() __ ")" __ "]" __ {
548            query::WhereClause::TypeAnnotation(
549                query::TypeAnnotation {
550                    value_type: ty,
551                    variable: var,
552                })
553        }
554
555    rule pred() -> query::WhereClause
556        = __ "[" __ "(" func:query_function() args:fn_arg()* ")" __ "]" __ {
557            query::WhereClause::Pred(
558                query::Predicate {
559                    operator: func.0,
560                    args,
561                })
562        }
563
564    pub rule where_fn() -> query::WhereClause
565        = __ "[" __ "(" func:query_function() args:fn_arg()* ")" __ binding:binding() "]" __ {
566            query::WhereClause::WhereFn(
567                query::WhereFn {
568                    operator: func.0,
569                    args,
570                    binding,
571                })
572        }
573
574    rule where_clause() -> query::WhereClause
575        // Right now we only support patterns and predicates. See #239 for more.
576        = pattern()
577        / or_join_clause()
578        / or_clause()
579        / not_join_clause()
580        / not_clause()
581        / type_annotation()
582        / pred()
583        / where_fn()
584        / rule_invocation()
585
586    // A rule invocation in a query body, e.g. `(ancestor ?x ?y)`. Ported from
587    // pg_mentat. Only matches names that are NOT reserved clause keywords
588    // (those are handled by their own rules above).
589    rule rule_invocation() -> query::WhereClause
590        = __ "(" __ n:$(symbol_name()) args:fn_arg()+ ")" __ {?
591            let name = n.to_string();
592            if name == "or" || name == "not" || name == "and"
593                || name == "or-join" || name == "not-join"
594                || name == "type" || name == "fulltext" || name == "ground"
595                || name == "get-else" || name == "missing?" {
596                Err("not a rule invocation")
597            } else {
598                Ok(query::WhereClause::RuleExpr(query::RuleInvocation {
599                    name: PlainSymbol::plain(&name),
600                    args,
601                }))
602            }
603        }
604
605    // A rule head: (rule-name ?arg1 ?arg2)
606    rule rule_head() -> query::RuleInvocation
607        = __ "(" __ n:$(symbol_name()) args:fn_arg()+ ")" __ {
608            query::RuleInvocation {
609                name: PlainSymbol::plain(n),
610                args,
611            }
612        }
613
614    // A rule clause: [(rule-name ?a ?b) body-patterns...]
615    rule rule_clause() -> query::RuleClause
616        = __ "[" head:rule_head() body:where_clause()+ "]" __ {
617            query::RuleClause { head, body }
618        }
619
620    // A set of rule clauses: [clause1 clause2 ...], grouped by rule name.
621    rule rule_definitions() -> Vec<query::Rule>
622        = __ "[" clauses:rule_clause()+ "]" __ {
623            let mut rule_map: std::collections::BTreeMap<String, Vec<query::RuleClause>> =
624                std::collections::BTreeMap::new();
625            for clause in clauses {
626                let name = clause.head.name.0.clone();
627                rule_map.entry(name).or_default().push(clause);
628            }
629            rule_map.into_iter().map(|(name, clauses)| {
630                query::Rule {
631                    name: PlainSymbol::plain(&name),
632                    clauses,
633                }
634            }).collect()
635        }
636
637    rule query_part() -> Vec<query::QueryPart>
638        = __ ":find" fs:find_spec() { vec![query::QueryPart::FindSpec(fs)] }
639        / __ ":in" parts:in_clause() { parts }
640        / __ ":limit" l:limit() { vec![query::QueryPart::Limit(l)] }
641        / __ ":offset" o:offset() { vec![query::QueryPart::Offset(o)] }
642        / __ ":order" os:order()+ { vec![query::QueryPart::Order(os)] }
643        / __ ":where" ws:where_clause()+ { vec![query::QueryPart::WhereClauses(ws)] }
644        / __ ":rules" rules:rule_definitions() { vec![query::QueryPart::Rules(rules)] }
645        / __ ":with" rules:rule_definitions() { vec![query::QueryPart::Rules(rules)] }
646        / __ ":with" with_vars:variable()+ { vec![query::QueryPart::WithVars(with_vars)] }
647        / __ ":distinct" { vec![query::QueryPart::Distinct] }
648
649    // `:in` accepts source vars (`$`, `$named`) and binding forms, in any mix.
650    // Sources go to InSources, everything else to InBindings; the scalar
651    // bindings are later derived into in_vars. Emits up to two parts.
652    rule in_clause() -> Vec<query::QueryPart>
653        = items:in_item()+ {
654            let mut sources = Vec::new();
655            let mut bindings = Vec::new();
656            for item in items {
657                match item {
658                    InItem::Source(s) => sources.push(s),
659                    InItem::Binding(b) => bindings.push(b),
660                }
661            }
662            let mut parts = Vec::new();
663            if !sources.is_empty() { parts.push(query::QueryPart::InSources(sources)); }
664            parts.push(query::QueryPart::InBindings(bindings));
665            parts
666        }
667
668    // A source var if it starts with `$`, else a binding. `src_var()` accepts
669    // any symbol, so try it only on `$`-led input to avoid swallowing `?vars`.
670    rule in_item() -> InItem
671        = __ &"$" s:src_var() { InItem::Source(s) }
672        / b:binding() { InItem::Binding(b) }
673
674    pub rule parse_query() -> query::ParsedQuery
675        = __ "[" qps:query_part()+ "]" __ {? query::ParsedQuery::from_parts(qps.into_iter().flatten().collect()) }
676
677    rule variable() -> query::Variable
678        = v:value() {? query::Variable::from_value(&v).ok_or("expected variable") }
679
680    rule src_var() -> query::SrcVar
681        = v:value() {? query::SrcVar::from_value(&v).ok_or("expected src_var") }
682
683    rule variable_or_placeholder() -> query::VariableOrPlaceholder
684        = v:variable() { query::VariableOrPlaceholder::Variable(v) }
685        / __ "_" __ { query::VariableOrPlaceholder::Placeholder }
686
687    rule binding() -> query::Binding
688        = __ "[" __ "[" vs:variable_or_placeholder()+ "]" __ "]" __ { query::Binding::BindRel(vs) }
689        / __ "[" v:variable() "..." __ "]" __ { query::Binding::BindColl(v) }
690        / __ "[" vs:variable_or_placeholder()+ "]" __ { query::Binding::BindTuple(vs) }
691        / v:variable() { query::Binding::BindScalar(v) }
692
693});
694
695/// The parser. Every entry point rejects input nested deeper than
696/// [`MAX_NESTING`] before the grammar runs; see [`depth`] for why.
697pub mod parse {
698    use super::*;
699    pub fn nil(input: &str) -> Result<SpannedValue, ParseError> {
700        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
701        grammar::nil(input)
702    }
703    pub fn nan(input: &str) -> Result<SpannedValue, ParseError> {
704        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
705        grammar::nan(input)
706    }
707    pub fn infinity(input: &str) -> Result<SpannedValue, ParseError> {
708        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
709        grammar::infinity(input)
710    }
711    pub fn boolean(input: &str) -> Result<SpannedValue, ParseError> {
712        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
713        grammar::boolean(input)
714    }
715    pub fn raw_bigint(input: &str) -> Result<BigInt, ParseError> {
716        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
717        grammar::raw_bigint(input)
718    }
719    pub fn raw_octalinteger(input: &str) -> Result<i64, ParseError> {
720        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
721        grammar::raw_octalinteger(input)
722    }
723    pub fn raw_hexinteger(input: &str) -> Result<i64, ParseError> {
724        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
725        grammar::raw_hexinteger(input)
726    }
727    pub fn raw_basedinteger(input: &str) -> Result<i64, ParseError> {
728        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
729        grammar::raw_basedinteger(input)
730    }
731    pub fn raw_integer(input: &str) -> Result<i64, ParseError> {
732        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
733        grammar::raw_integer(input)
734    }
735    pub fn raw_float(input: &str) -> Result<OrderedFloat<f64>, ParseError> {
736        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
737        grammar::raw_float(input)
738    }
739    pub fn bigint(input: &str) -> Result<SpannedValue, ParseError> {
740        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
741        grammar::bigint(input)
742    }
743    pub fn octalinteger(input: &str) -> Result<SpannedValue, ParseError> {
744        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
745        grammar::octalinteger(input)
746    }
747    pub fn hexinteger(input: &str) -> Result<SpannedValue, ParseError> {
748        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
749        grammar::hexinteger(input)
750    }
751    pub fn basedinteger(input: &str) -> Result<SpannedValue, ParseError> {
752        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
753        grammar::basedinteger(input)
754    }
755    pub fn integer(input: &str) -> Result<SpannedValue, ParseError> {
756        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
757        grammar::integer(input)
758    }
759    pub fn float(input: &str) -> Result<SpannedValue, ParseError> {
760        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
761        grammar::float(input)
762    }
763    pub fn raw_text(input: &str) -> Result<String, ParseError> {
764        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
765        grammar::raw_text(input)
766    }
767    pub fn text(input: &str) -> Result<SpannedValue, ParseError> {
768        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
769        grammar::text(input)
770    }
771    pub fn uuid(input: &str) -> Result<SpannedValue, ParseError> {
772        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
773        grammar::uuid(input)
774    }
775    pub fn bytes(input: &str) -> Result<SpannedValue, ParseError> {
776        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
777        grammar::bytes(input)
778    }
779    pub fn symbol(input: &str) -> Result<SpannedValue, ParseError> {
780        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
781        grammar::symbol(input)
782    }
783    pub fn keyword(input: &str) -> Result<SpannedValue, ParseError> {
784        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
785        grammar::keyword(input)
786    }
787    pub fn list(input: &str) -> Result<SpannedValue, ParseError> {
788        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
789        grammar::list(input)
790    }
791    pub fn vector(input: &str) -> Result<SpannedValue, ParseError> {
792        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
793        grammar::vector(input)
794    }
795    pub fn set(input: &str) -> Result<SpannedValue, ParseError> {
796        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
797        grammar::set(input)
798    }
799    pub fn pair(input: &str) -> Result<(ValueAndSpan, ValueAndSpan), ParseError> {
800        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
801        grammar::pair(input)
802    }
803    pub fn map(input: &str) -> Result<SpannedValue, ParseError> {
804        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
805        grammar::map(input)
806    }
807    pub fn value(input: &str) -> Result<ValueAndSpan, ParseError> {
808        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
809        grammar::value(input)
810    }
811    pub fn op(input: &str) -> Result<OpType, ParseError> {
812        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
813        grammar::op(input)
814    }
815    pub fn entity(input: &str) -> Result<Entity<ValueAndSpan>, ParseError> {
816        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
817        grammar::entity(input)
818    }
819    pub fn entities(input: &str) -> Result<Vec<Entity<ValueAndSpan>>, ParseError> {
820        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
821        grammar::entities(input)
822    }
823    pub fn where_fn(input: &str) -> Result<crate::query::WhereClause, ParseError> {
824        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
825        grammar::where_fn(input)
826    }
827    pub fn parse_query(input: &str) -> Result<crate::query::ParsedQuery, ParseError> {
828        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
829        grammar::parse_query(input)
830    }
831    pub fn pull_pattern(input: &str) -> Result<Vec<crate::query::PullAttributeSpec>, ParseError> {
832        crate::depth::check_nesting(input, crate::depth::MAX_NESTING)?;
833        grammar::pull_pattern(input)
834    }
835}
edn/lib.rs

edn/
lib.rs
