snomed_ecl_engine/
ecl.rs

1//! ECL 2.3 parsing. Unsupported constructs fail before evaluation.
2use std::fmt;
3mod descriptions;
4mod filters;
5pub use descriptions::{DescriptionFilter, Dialect};
6mod history;
7mod identifiers;
8mod members;
9mod refinement;
10mod search;
11pub use filters::ConceptFilter;
12pub use history::History;
13pub use members::{MemberFilter, MemberPredicate, MemberQuery};
14pub use refinement::{AttributeConstraint, AttributeValue, Cardinality, Comparison, Refinement};
15pub use search::SearchTerm;
16
17#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18pub enum Hierarchy {
19    Descendant,
20    DescendantOrSelf,
21    Child,
22    ChildOrSelf,
23    Ancestor,
24    AncestorOrSelf,
25    Parent,
26    ParentOrSelf,
27}
28
29impl Hierarchy {
30    pub fn ancestors(self) -> bool {
31        matches!(
32            self,
33            Self::Ancestor | Self::AncestorOrSelf | Self::Parent | Self::ParentOrSelf
34        )
35    }
36    pub fn direct(self) -> bool {
37        matches!(
38            self,
39            Self::Child | Self::ChildOrSelf | Self::Parent | Self::ParentOrSelf
40        )
41    }
42    pub fn include_self(self) -> bool {
43        matches!(
44            self,
45            Self::DescendantOrSelf | Self::ChildOrSelf | Self::AncestorOrSelf | Self::ParentOrSelf
46        )
47    }
48}
49
50#[derive(Clone, Debug, PartialEq, Eq)]
51pub enum Expr {
52    Concept(u64),
53    AlternateIdentifier { scheme: String, code: String },
54    DialectAlias(String),
55    All,
56    Hierarchy(Hierarchy, Box<Expr>),
57    And(Vec<Expr>),
58    Or(Vec<Expr>),
59    Minus(Box<Expr>, Box<Expr>),
60    Refined(Box<Expr>, Box<Refinement>),
61    Dotted(Box<Expr>, Vec<Expr>),
62    Extremum { top: bool, inner: Box<Expr> },
63    MemberOf(Box<Expr>),
64    Members(MemberQuery),
65    History(Box<Expr>, History),
66    RefsetContainingAny(Box<Expr>),
67    ConceptFiltered(Box<Expr>, Vec<ConceptFilter>),
68    DescriptionFiltered(Box<Expr>, Vec<DescriptionFilter>),
69}
70
71#[derive(Clone, Copy, Debug, PartialEq, Eq)]
72pub enum ParseErrorKind {
73    Syntax,
74    /// The engine does not implement this valid ECL form yet.
75    Unsupported,
76    /// A recognised combination is refused because of its semantic rules or unresolved meaning.
77    Semantic,
78    Limit,
79}
80
81#[derive(Clone, Debug, PartialEq, Eq)]
82pub struct ParseError {
83    pub kind: ParseErrorKind,
84    pub offset: usize,
85    pub message: &'static str,
86}
87impl fmt::Display for ParseError {
88    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
89        write!(
90            f,
91            "{:?} at byte {}: {}",
92            self.kind, self.offset, self.message
93        )
94    }
95}
96impl std::error::Error for ParseError {}
97type Result<T> = std::result::Result<T, ParseError>;
98
99pub const MAX_QUERY_BYTES: usize = 65536;
100pub const MAX_DEPTH: usize = 64;
101pub const MAX_NODES: usize = 4096;
102
103pub fn parse(text: &str) -> Result<Expr> {
104    let mut parser = Parser {
105        text,
106        pos: 0,
107        nodes: 0,
108        refused: None,
109    };
110    if text.len() > MAX_QUERY_BYTES {
111        return Err(parser.error(ParseErrorKind::Limit, "Query exceeds 65536 bytes"));
112    }
113    let expression = parser.expression(0)?;
114    parser.ws()?;
115    if parser.pos != text.len() {
116        return Err(parser.unexpected());
117    }
118    // A grammatical expression the engine refuses for its meaning. Reported
119    // only once the whole text parses, so malformed text is a syntax error.
120    if let Some(refusal) = parser.refused {
121        return Err(refusal);
122    }
123    Ok(expression)
124}
125
126#[derive(Clone, Copy, PartialEq, Eq)]
127enum Boolean {
128    And,
129    Or,
130    Minus,
131}
132
133struct Parser<'a> {
134    text: &'a str,
135    pos: usize,
136    nodes: usize,
137    /// The first semantic refusal, held until the text is known to parse.
138    refused: Option<ParseError>,
139}
140
141/// Where the parser was, to return to after an alternative fails.
142#[derive(Clone)]
143struct Mark {
144    pos: usize,
145    nodes: usize,
146    refused: Option<ParseError>,
147}
148
149impl Parser<'_> {
150    fn mark(&self) -> Mark {
151        Mark {
152            pos: self.pos,
153            nodes: self.nodes,
154            refused: self.refused.clone(),
155        }
156    }
157    fn reset(&mut self, mark: Mark) {
158        self.pos = mark.pos;
159        self.nodes = mark.nodes;
160        self.refused = mark.refused;
161    }
162    /// Records a grammatical form refused for its meaning, and parses on.
163    fn refuse(&mut self, at: usize, message: &'static str) {
164        self.refused.get_or_insert(ParseError {
165            kind: ParseErrorKind::Semantic,
166            offset: at,
167            message,
168        });
169    }
170    fn error(&self, kind: ParseErrorKind, message: &'static str) -> ParseError {
171        ParseError {
172            kind,
173            offset: self.pos,
174            message,
175        }
176    }
177    fn rest(&self) -> &str {
178        &self.text[self.pos..]
179    }
180    fn take(&mut self, value: &str) -> bool {
181        if self.rest().starts_with(value) {
182            self.pos += value.len();
183            true
184        } else {
185            false
186        }
187    }
188    fn ws(&mut self) -> Result<bool> {
189        let start = self.pos;
190        loop {
191            while self.rest().starts_with([' ', '\t', '\r', '\n']) {
192                self.pos += 1;
193            }
194            if !self.take("/*") {
195                break;
196            }
197            let end = self
198                .rest()
199                .find("*/")
200                .ok_or_else(|| self.error(ParseErrorKind::Syntax, "Unclosed comment"))?;
201            if self.rest()[..end]
202                .chars()
203                .any(|c| c.is_ascii_control() && !matches!(c, '\t' | '\r' | '\n'))
204            {
205                return Err(self.error(ParseErrorKind::Syntax, "Invalid comment character"));
206            }
207            self.pos += end + 2;
208        }
209        Ok(self.pos != start)
210    }
211    fn word(&self) -> &str {
212        let end = self
213            .rest()
214            .bytes()
215            .take_while(u8::is_ascii_alphabetic)
216            .count();
217        &self.rest()[..end]
218    }
219    fn required_ws(&mut self) -> Result<()> {
220        if self.ws()? {
221            Ok(())
222        } else {
223            Err(self.error(
224                ParseErrorKind::Syntax,
225                "Keyword requires following whitespace or comment",
226            ))
227        }
228    }
229    fn node(&mut self, expression: Expr) -> Result<Expr> {
230        self.nodes += 1;
231        if self.nodes > MAX_NODES {
232            return Err(self.error(ParseErrorKind::Limit, "Too many expression nodes"));
233        }
234        Ok(expression)
235    }
236    fn boolean(&mut self) -> Result<Option<Boolean>> {
237        self.ws()?;
238        if self.take(",") {
239            return Ok(Some(Boolean::And));
240        }
241        let word = self.word();
242        let op = if word.eq_ignore_ascii_case("and") {
243            Boolean::And
244        } else if word.eq_ignore_ascii_case("or") {
245            Boolean::Or
246        } else if word.eq_ignore_ascii_case("minus") {
247            Boolean::Minus
248        } else {
249            return Ok(None);
250        };
251        self.pos += word.len();
252        self.required_ws()?;
253        Ok(Some(op))
254    }
255    fn term(&mut self) -> Result<()> {
256        let original = self.pos;
257        let after_ws = match self.ws() {
258            Ok(_) => self.pos,
259            Err(_) => original,
260        };
261        // A comment can also be literal annotation text. Try both interpretations.
262        for start in [after_ws, original] {
263            self.pos = start;
264            let mut last_non_space = false;
265            while let Some(character) = self.rest().chars().next() {
266                if last_non_space {
267                    let saved = self.pos;
268                    if self.ws().is_ok() && self.take("|") {
269                        return Ok(());
270                    }
271                    self.pos = saved;
272                }
273                if character == '|' || character.is_ascii_control() {
274                    break;
275                }
276                last_non_space = character != ' ';
277                self.pos += character.len_utf8();
278            }
279        }
280        self.pos = original;
281        Err(self.error(ParseErrorKind::Syntax, "Invalid or unclosed concept term"))
282    }
283    fn expression(&mut self, depth: usize) -> Result<Expr> {
284        if depth > MAX_DEPTH {
285            return Err(self.error(ParseErrorKind::Limit, "Expression nesting exceeds 64"));
286        }
287        let left = self.subexpression(depth)?;
288        if self.take(":") {
289            let refinement = self.refinement(depth + 1)?;
290            return self.node(Expr::Refined(Box::new(left), Box::new(refinement)));
291        }
292        if self.take(".") {
293            let mut attributes = vec![self.subexpression(depth + 1)?];
294            while self.take(".") {
295                attributes.push(self.subexpression(depth + 1)?);
296            }
297            return self.node(Expr::Dotted(Box::new(left), attributes));
298        }
299        let Some(op) = self.boolean()? else {
300            return Ok(left);
301        };
302        let right = self.subexpression(depth)?;
303        if op == Boolean::Minus {
304            if self.boolean()?.is_some() {
305                return Err(self.error(
306                    ParseErrorKind::Syntax,
307                    "Parentheses required around mixed or repeated exclusion",
308                ));
309            }
310            return self.node(Expr::Minus(Box::new(left), Box::new(right)));
311        }
312        let mut operands = vec![left, right];
313        while let Some(next) = self.boolean()? {
314            if next != op {
315                return Err(self.error(
316                    ParseErrorKind::Syntax,
317                    "Mixed Boolean operators require parentheses",
318                ));
319            }
320            operands.push(self.subexpression(depth)?);
321        }
322        self.node(if op == Boolean::And {
323            Expr::And(operands)
324        } else {
325            Expr::Or(operands)
326        })
327    }
328    fn subexpression(&mut self, depth: usize) -> Result<Expr> {
329        self.ws()?;
330        if depth > MAX_DEPTH {
331            return Err(self.error(ParseErrorKind::Limit, "Expression nesting exceeds 64"));
332        }
333        let extremum = if self.take("!!>") {
334            Some(true)
335        } else if self.take("!!<") {
336            Some(false)
337        } else if !self.starts_alternate() && self.keyword("top") {
338            self.required_ws()?;
339            Some(true)
340        } else if !self.starts_alternate() && self.keyword("bottom") {
341            self.required_ws()?;
342            Some(false)
343        } else {
344            None
345        };
346        self.ws()?;
347        let mut hierarchy = None;
348        for (symbol, op) in [
349            ("<<!", Hierarchy::ChildOrSelf),
350            (">>!", Hierarchy::ParentOrSelf),
351            ("<<", Hierarchy::DescendantOrSelf),
352            (">>", Hierarchy::AncestorOrSelf),
353            ("<!", Hierarchy::Child),
354            (">!", Hierarchy::Parent),
355            ("<", Hierarchy::Descendant),
356            (">", Hierarchy::Ancestor),
357        ] {
358            if self.take(symbol) {
359                hierarchy = Some(op);
360                break;
361            }
362        }
363        if hierarchy.is_none() && !self.starts_alternate() {
364            let word = self.word();
365            for (name, op) in [
366                ("descendantof", Hierarchy::Descendant),
367                ("descendantorselfof", Hierarchy::DescendantOrSelf),
368                ("childof", Hierarchy::Child),
369                ("childorselfof", Hierarchy::ChildOrSelf),
370                ("ancestorof", Hierarchy::Ancestor),
371                ("ancestororselfof", Hierarchy::AncestorOrSelf),
372                ("parentof", Hierarchy::Parent),
373                ("parentorselfof", Hierarchy::ParentOrSelf),
374            ] {
375                if word.eq_ignore_ascii_case(name) {
376                    hierarchy = Some(op);
377                    self.pos += word.len();
378                    self.required_ws()?;
379                    break;
380                }
381            }
382        }
383        self.ws()?;
384        if extremum.is_some() && hierarchy.is_some() {
385            return Err(self.error(
386                ParseErrorKind::Syntax,
387                "Unary operators require a parenthesised operand",
388            ));
389        }
390        // ABNF quoted strings are case-insensitive (RFC 5234 2.3) and the parsing guidance
391        // says keywords are case-insensitive, so "^R" admits ^r; only ECL.g4 restricts it to CAP_R.
392        // `^R#x` and `^R-#x` are memberOf over the alternate identifiers `R#x` and
393        // `R-#x`: a scheme alias starts with a letter, so `^R` then `#x` or `-#x`
394        // has no reading.
395        let alternate_scheme_r = {
396            let bytes = self.rest().as_bytes();
397            bytes.len() > 2
398                && bytes[..2].eq_ignore_ascii_case(b"^r")
399                && !bytes[2].is_ascii_alphabetic()
400                && bytes[2..]
401                    .iter()
402                    .find(|b| !(b.is_ascii_alphanumeric() || **b == b'-'))
403                    == Some(&b'#')
404        };
405        let refset_operator = if !alternate_scheme_r && (self.take("^R") || self.take("^r")) {
406            Some(true)
407        } else if self.take("^") {
408            Some(false)
409        } else if !self.starts_alternate() && self.operator_keyword("memberOf") {
410            self.ws()?;
411            Some(false)
412        } else if !self.starts_alternate() && self.operator_keyword("refsetContainingAny") {
413            self.ws()?;
414            Some(true)
415        } else {
416            None
417        };
418        self.ws()?;
419        let fields = if refset_operator == Some(false) && self.rest().starts_with('[') {
420            Some(self.member_fields()?)
421        } else {
422            None
423        };
424        let mut expression = if self.take("(") {
425            let inner = self.expression(depth + 1)?;
426            self.ws()?;
427            if !self.take(")") {
428                return Err(self.unexpected());
429            }
430            inner
431        } else if self.starts_alternate() {
432            self.alternate_identifier()?
433        } else if self.take("*") || self.value_keyword("any") {
434            self.node(Expr::All)?
435        } else if self.rest().starts_with(|c: char| c.is_ascii_digit()) {
436            let start = self.pos;
437            while self.rest().starts_with(|c: char| c.is_ascii_digit()) {
438                self.pos += 1;
439            }
440            let code = &self.text[start..self.pos];
441            if !(6..=18).contains(&code.len()) || code.starts_with('0') {
442                return Err(self.error(
443                    ParseErrorKind::Syntax,
444                    "SCTID must contain 6 to 18 digits without a leading zero",
445                ));
446            }
447            let code = code
448                .parse()
449                .map_err(|_| self.error(ParseErrorKind::Syntax, "Invalid SCTID"))?;
450            self.ws()?;
451            if self.take("|") {
452                self.term()?;
453            }
454            self.node(Expr::Concept(code))?
455        } else {
456            return Err(self.unexpected());
457        };
458        self.ws()?;
459        let mut member_filters = Vec::new();
460        while self.starts_member_filter()? {
461            if refset_operator.is_none() {
462                // Logical model 4: member filters apply to results of the memberOf function.
463                self.refuse(
464                    self.pos,
465                    "Member filters require a refset operator (^ or ^R); ECL defines them only over memberOf rows",
466                );
467            }
468            member_filters.extend(self.member_filters(depth + 1)?);
469            self.ws()?;
470        }
471        if let Some(reverse) = refset_operator {
472            expression = self.node(if fields.is_some() || !member_filters.is_empty() {
473                Expr::Members(MemberQuery {
474                    source: Box::new(expression),
475                    reverse,
476                    fields,
477                    filters: member_filters,
478                })
479            } else if reverse {
480                Expr::RefsetContainingAny(Box::new(expression))
481            } else {
482                Expr::MemberOf(Box::new(expression))
483            })?;
484        }
485        if let Some(op) = hierarchy {
486            expression = self.node(Expr::Hierarchy(op, Box::new(expression)))?;
487        }
488        if let Some(top) = extremum {
489            expression = self.node(Expr::Extremum {
490                top,
491                inner: Box::new(expression),
492            })?;
493        }
494        while self.rest().starts_with("{{") {
495            let saved = self.pos;
496            self.take("{{");
497            self.ws()?;
498            let concept = self.rest().starts_with(['C', 'c']);
499            let history = self.rest().starts_with('+');
500            self.pos = saved;
501            if history {
502                let supplement = self.history(depth + 1)?;
503                expression = self.node(Expr::History(Box::new(expression), supplement))?;
504                self.ws()?;
505                break;
506            } else if concept {
507                let filters = self.concept_filters(depth + 1)?;
508                expression = self.node(Expr::ConceptFiltered(Box::new(expression), filters))?;
509            } else {
510                // A filter that names no type is a description filter (6.8), so
511                // `{{moduleId = x}}` is never the member filter `m oduleId`.
512                let filters = self.description_filters(depth + 1)?;
513                expression = self.node(Expr::DescriptionFiltered(Box::new(expression), filters))?;
514            }
515            self.ws()?;
516        }
517        Ok(expression)
518    }
519    /// A long-syntax operator that the grammar lets run into `ANY`, as in
520    /// `memberOfANY`.
521    fn operator_keyword(&mut self, word: &str) -> bool {
522        let found = self.word();
523        let joined = found.len() == word.len() + 3
524            && found[..word.len()].eq_ignore_ascii_case(word)
525            && found[word.len()..].eq_ignore_ascii_case("any");
526        if found.eq_ignore_ascii_case(word) || joined {
527            self.pos += word.len();
528            true
529        } else {
530            false
531        }
532    }
533    fn unexpected(&self) -> ParseError {
534        self.error(
535            ParseErrorKind::Syntax,
536            "Unexpected token or missing operand",
537        )
538    }
539}
snomed_ecl_engine/ecl.rs

snomed_ecl_engine/
ecl.rs
