asc_query/
rule.rs

1//! The rule syntax of `findrefs all` / `rules` and of call graph endpoints,
2//! one for both engines.
3//!
4//! ```text
5//! rule  := part ( '&' part )*
6//! part  := [ '!' ] KIND ':' value
7//! value := [ '=' | '*' ] '{' rule '}' TAIL       a set: kinds of Shape::Set only
8//!        | [ '=' | '*' ] '{' '@' PATH '}' TAIL   a set a file lists
9//!        | [ '=' | '*' ] '@' PATH                 the same, where the kind allows it bare
10//!        | TEXT                                   the kind's own syntax, e.g. a regex
11//! ```
12//!
13//! A `&` joins two parts only where `KIND:` or `!KIND:` follows it (blanks
14//! allowed), outside `{}` / `()`: anywhere else it is part of the value,
15//! as in record names (`&entry/src/main/ets/pages/Index&`) and regexes. A
16//! `\` keeps the next character from joining, opening or closing anything
17//! (`string:a\&literal:b` is one regex). TEXT, a PATH and a TAIL run to the
18//! next joining `&`, or to the `}` closing the enclosing set; blanks around
19//! them do not count.
20//!
21//! The grammar of an engine ([`Grammar`]) names the kinds and says which
22//! take sets; what a value means, a TAIL included, is the engine's to read.
23
24use std::fmt;
25use std::io;
26use std::marker::PhantomData;
27use std::path::Path;
28
29/// Sets inside sets deeper than this are a mistake or hostile: each level is
30/// another pass over the code, and the parser recurses per level.
31pub const MAX_DEPTH: usize = 8;
32
33/// The kinds of one engine.
34pub trait Grammar {
35    /// A kind, as the engine tells them apart.
36    type Kind: Copy;
37
38    /// The kinds, as an error that expects one lists them.
39    const KINDS: &'static str;
40
41    /// The kind `word` (the letters before the `:`) names.
42    ///
43    /// # Errors
44    /// What to say about a word that names no kind.
45    fn kind(word: &str) -> Result<Self::Kind, String>;
46
47    /// How the value of `kind` is written.
48    fn shape(kind: Self::Kind) -> Shape;
49}
50
51/// How the value of a kind is written.
52#[derive(Debug, Clone, Copy, PartialEq, Eq)]
53pub enum Shape {
54    /// TEXT only.
55    Text,
56    /// A set (`{RULE}`, `{@PATH}`) or TEXT.
57    Set {
58        /// `@PATH` without braces is a set too, not TEXT.
59        bare_file: bool,
60    },
61}
62
63/// What a `=` or `*` in front of a set asks for.
64#[derive(Debug, Clone, Copy, PartialEq, Eq)]
65pub enum Mode {
66    /// Nothing in front.
67    Plain,
68    /// `=`: the set's own members only.
69    Exact,
70    /// `*`: everything the set may stand for.
71    Every,
72}
73
74/// A piece of the rule: its text without the blanks around it, and where
75/// it starts.
76#[derive(Debug, Clone, Copy, PartialEq, Eq)]
77pub struct Text<'a> {
78    /// The trimmed text, borrowed from the rule.
79    pub text: &'a str,
80    /// Byte offset in the rule.
81    pub at: usize,
82}
83
84/// A parsed rule: its parts in the order written.
85#[derive(Debug, Clone, PartialEq, Eq)]
86pub struct Rule<'a, K> {
87    /// The parts joined by `&`; a parsed rule has at least one.
88    pub parts: Vec<Part<'a, K>>,
89}
90
91/// One `[!]KIND:VALUE`.
92#[derive(Debug, Clone, PartialEq, Eq)]
93pub struct Part<'a, K> {
94    /// Byte offset of the part (its `!`, else its kind) in the rule.
95    pub at: usize,
96    /// Written with `!`.
97    pub negated: bool,
98    /// The kind named before the `:`.
99    pub kind: K,
100    /// What follows the `:`.
101    pub value: Value<'a, K>,
102}
103
104/// The value of a part.
105#[derive(Debug, Clone, PartialEq, Eq)]
106pub enum Value<'a, K> {
107    /// TEXT, for the engine to read in the kind's own syntax.
108    Text(Text<'a>),
109    /// A set, with what is written around it.
110    Set {
111        /// The `=` or `*` in front, if any.
112        mode: Mode,
113        /// The set's members.
114        set: Set<'a, K>,
115        /// What follows the set up to the end of the part (empty when nothing).
116        tail: Text<'a>,
117    },
118}
119
120/// The members of a set.
121#[derive(Debug, Clone, PartialEq, Eq)]
122pub enum Set<'a, K> {
123    /// Those matching a rule.
124    Rule(Rule<'a, K>),
125    /// Those a file lists.
126    File(SetFile<'a>),
127}
128
129/// The file of `{@PATH}`.
130#[derive(Debug, Clone, Copy, PartialEq, Eq)]
131pub struct SetFile<'a> {
132    /// The PATH after the `@`, as written.
133    pub path: Text<'a>,
134}
135
136impl SetFile<'_> {
137    /// The file's text. A relative path is read in `dir` (the current
138    /// directory when `None`).
139    ///
140    /// # Errors
141    /// The file does not read as UTF-8 text.
142    pub fn read(&self, dir: Option<&Path>) -> io::Result<String> {
143        let path = Path::new(self.path.text);
144        // An absolute `path` replaces `dir` when joined.
145        std::fs::read_to_string(dir.map_or_else(|| path.to_path_buf(), |dir| dir.join(path)))
146    }
147}
148
149/// A rule that does not parse, or a value its engine does not take.
150#[derive(Debug, Clone, PartialEq, Eq)]
151pub struct SyntaxError {
152    rule: String,
153    at: usize,
154    message: String,
155}
156
157impl SyntaxError {
158    /// `message` about `rule` at byte offset `at`.
159    pub fn new(rule: &str, at: usize, message: impl Into<String>) -> SyntaxError {
160        SyntaxError { rule: rule.to_owned(), at, message: message.into() }
161    }
162
163    /// The column, from 1, the error is at.
164    pub fn column(&self) -> usize {
165        self.at + 1
166    }
167
168    /// What is wrong, without the rule and column.
169    pub fn message(&self) -> &str {
170        &self.message
171    }
172}
173
174impl fmt::Display for SyntaxError {
175    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
176        write!(f, "bad rule {:?}: {} at column {}", self.rule, self.message, self.column())
177    }
178}
179
180impl std::error::Error for SyntaxError {}
181
182impl<'a, K: Copy> Rule<'a, K> {
183    /// Parse `rule` with the kinds of `G`.
184    ///
185    /// # Errors
186    /// A part that is no `KIND:VALUE`, a kind `G` does not have, an empty
187    /// value, a set without its `}` or nested deeper than [`MAX_DEPTH`].
188    pub fn parse<G: Grammar<Kind = K>>(rule: &'a str) -> Result<Rule<'a, K>, SyntaxError> {
189        let mut parser = Parser::<G> { src: rule, pos: 0, depth: 0, grammar: PhantomData };
190        let parsed = parser.rule(false)?;
191        // At the top a value runs to a joining `&` or the end: nothing is left.
192        debug_assert_eq!(parser.peek(), None, "{rule:?}");
193        Ok(parsed)
194    }
195}
196
197/// The parts of `rule` as written, each with its `!`: what stands between
198/// the `&` that join them at the top. For a front end that looks at the
199/// kinds before an engine parses the rule.
200pub fn parts(rule: &str) -> Vec<&str> {
201    let mut parts = Vec::new();
202    let mut rest = rule;
203    loop {
204        let len = text_len(rest, false);
205        parts.push(rest[..len].trim());
206        match rest.get(len + 1..) {
207            Some(next) => rest = next,
208            None => return parts,
209        }
210    }
211}
212
213struct Parser<'a, G> {
214    src: &'a str,
215    pos: usize,
216    /// Sets open at the cursor.
217    depth: usize,
218    grammar: PhantomData<G>,
219}
220
221impl<'a, G: Grammar> Parser<'a, G> {
222    fn rest(&self) -> &'a str {
223        &self.src[self.pos..]
224    }
225
226    fn skip_blanks(&mut self) {
227        self.pos = self.src.len() - self.rest().trim_start().len();
228    }
229
230    /// The next non-blank character, not consumed.
231    fn peek(&mut self) -> Option<char> {
232        self.skip_blanks();
233        self.rest().chars().next()
234    }
235
236    fn eat(&mut self, c: char) -> bool {
237        let found = self.peek() == Some(c);
238        if found {
239            self.pos += c.len_utf8();
240        }
241        found
242    }
243
244    fn error(&self, message: impl Into<String>) -> SyntaxError {
245        SyntaxError::new(self.src, self.pos, message)
246    }
247
248    /// `part ('&' part)*`, up to the end or (`nested`) the closing `}`.
249    fn rule(&mut self, nested: bool) -> Result<Rule<'a, G::Kind>, SyntaxError> {
250        let mut parts = Vec::new();
251        loop {
252            self.skip_blanks();
253            let at = self.pos;
254            let negated = self.eat('!');
255            parts.push(self.part(at, negated, nested)?);
256            // A value ends at a joining `&`, a `}` or the end.
257            if !self.eat('&') {
258                return Ok(Rule { parts });
259            }
260        }
261    }
262
263    /// `KIND ':' value`, the `!` already eaten.
264    fn part(&mut self, at: usize, negated: bool, nested: bool) -> Result<Part<'a, G::Kind>, SyntaxError> {
265        self.skip_blanks();
266        let rest = self.rest();
267        let word = kind_word(rest);
268        if word == 0 || !rest[word..].starts_with(':') {
269            return Err(self.error(format!("expected KIND:VALUE, KIND one of {}", G::KINDS)));
270        }
271        let kind = G::kind(&rest[..word]).map_err(|message| self.error(message))?;
272        self.pos += word + 1;
273        let value = match G::shape(kind) {
274            Shape::Text => Value::Text(self.text(nested)?),
275            Shape::Set { bare_file } => self.set_or_text(nested, bare_file)?,
276        };
277        Ok(Part { at, negated, kind, value })
278    }
279
280    /// The value of a kind that takes sets.
281    fn set_or_text(&mut self, nested: bool, bare_file: bool) -> Result<Value<'a, G::Kind>, SyntaxError> {
282        self.skip_blanks();
283        let rest = self.rest();
284        let (mode, after) = match rest.as_bytes().first() {
285            Some(b'=') => (Mode::Exact, &rest[1..]),
286            Some(b'*') => (Mode::Every, &rest[1..]),
287            _ => (Mode::Plain, rest),
288        };
289        if after.starts_with('{') {
290            self.pos += rest.len() - after.len() + 1;
291            if self.depth >= MAX_DEPTH {
292                return Err(self.error(format!("bodies are nested deeper than {MAX_DEPTH} levels")));
293            }
294            self.depth += 1;
295            let set = if self.eat('@') { Set::File(SetFile { path: self.text(true)? }) } else { Set::Rule(self.rule(true)?) };
296            self.depth -= 1;
297            if !self.eat('}') {
298                return Err(self.error("expected `}`"));
299            }
300            return Ok(Value::Set { mode, set, tail: self.tail(nested) });
301        }
302        if bare_file && after.starts_with('@') {
303            self.pos += rest.len() - after.len() + 1;
304            let path = self.text(nested)?;
305            return Ok(Value::Set { mode, set: Set::File(SetFile { path }), tail: Text { text: "", at: self.pos } });
306        }
307        Ok(Value::Text(self.text(nested)?))
308    }
309
310    /// TEXT at the cursor; an error when there is none.
311    fn text(&mut self, nested: bool) -> Result<Text<'a>, SyntaxError> {
312        let text = self.tail(nested);
313        if text.text.is_empty() {
314            return Err(self.error("empty value"));
315        }
316        Ok(text)
317    }
318
319    /// TEXT at the cursor, maybe none.
320    fn tail(&mut self, nested: bool) -> Text<'a> {
321        self.skip_blanks();
322        let at = self.pos;
323        let len = text_len(self.rest(), nested);
324        self.pos += len;
325        Text { text: self.src[at..self.pos].trim_end(), at }
326    }
327}
328
329/// Bytes of the ASCII letters at the start of `s`.
330fn kind_word(s: &str) -> usize {
331    s.find(|c: char| !c.is_ascii_alphabetic()).unwrap_or(s.len())
332}
333
334/// Whether a `&` followed by `rest` joins two parts: `KIND:` or `!KIND:`
335/// comes next.
336fn joins(rest: &str) -> bool {
337    let rest = rest.trim_start();
338    let rest = rest.strip_prefix('!').unwrap_or(rest).trim_start();
339    let word = kind_word(rest);
340    word > 0 && rest[word..].starts_with(':')
341}
342
343/// Bytes of TEXT at the start of `s`: up to a joining `&` outside `{}` /
344/// `()`, or an unmatched `}` when `nested`. A `\` keeps the next character in.
345fn text_len(s: &str, nested: bool) -> usize {
346    let mut depth = 0usize;
347    let mut chars = s.char_indices();
348    while let Some((i, c)) = chars.next() {
349        match c {
350            '\\' => {
351                chars.next();
352            }
353            '{' | '(' => depth += 1,
354            '}' | ')' if depth > 0 => depth -= 1,
355            '}' if nested => return i,
356            '&' if depth == 0 && joins(&s[i + 1..]) => return i,
357            _ => {}
358        }
359    }
360    s.len()
361}
362
363#[cfg(test)]
364mod tests {
365    use super::*;
366
367    /// A grammar of three kinds: `text:` TEXT, `set:` a set, `bare:` a set
368    /// that also takes `@PATH`.
369    struct Test;
370
371    impl Grammar for Test {
372        type Kind = &'static str;
373        const KINDS: &'static str = "text, set, bare";
374
375        fn kind(word: &str) -> Result<&'static str, String> {
376            ["text", "set", "bare"].into_iter().find(|kind| *kind == word).ok_or_else(|| format!("unknown kind {word:?}"))
377        }
378
379        fn shape(kind: &'static str) -> Shape {
380            match kind {
381                "text" => Shape::Text,
382                "set" => Shape::Set { bare_file: false },
383                _ => Shape::Set { bare_file: true },
384            }
385        }
386    }
387
388    /// The rule as a compact string: `!kind:'text'`, `kind:={...}+'tail'`, `@'path'`.
389    fn shape(rule: &str) -> String {
390        fn of(rule: &Rule<'_, &str>) -> String {
391            let parts = rule.parts.iter().map(|part| {
392                let value = match &part.value {
393                    Value::Text(text) => format!("'{}'", text.text),
394                    Value::Set { mode, set, tail } => {
395                        let mode = match mode {
396                            Mode::Plain => "",
397                            Mode::Exact => "=",
398                            Mode::Every => "*",
399                        };
400                        let set = match set {
401                            Set::Rule(rule) => format!("{{{}}}", of(rule)),
402                            Set::File(file) => format!("@'{}'", file.path.text),
403                        };
404                        if tail.text.is_empty() { format!("{mode}{set}") } else { format!("{mode}{set}+'{}'", tail.text) }
405                    }
406                };
407                format!("{}{}:{value}", if part.negated { "!" } else { "" }, part.kind)
408            });
409            parts.collect::<Vec<_>>().join(" & ")
410        }
411        match Rule::parse::<Test>(rule) {
412            Ok(parsed) => of(&parsed),
413            Err(e) => format!("error: {e}"),
414        }
415    }
416
417    #[test]
418    fn an_ampersand_joins_only_ahead_of_a_kind() {
419        assert_eq!(shape("text:a & !text:b&text:c"), "text:'a' & !text:'b' & text:'c'");
420        assert_eq!(shape("text:a&b"), "text:'a&b'");
421        assert_eq!(shape("text:&a/b&->f & text:N&&&a/b&#x"), "text:'&a/b&->f' & text:'N&&&a/b&#x'");
422        assert_eq!(shape(r"text:a\&text:b"), r"text:'a\&text:b'");
423        assert_eq!(shape("text:a&! text:b"), "text:'a' & !text:'b'");
424        // Inside brackets a `&` is part of the value; a `\` keeps a bracket from counting.
425        assert_eq!(shape("text:(a&text:b) & text:c"), "text:'(a&text:b)' & text:'c'");
426        assert_eq!(shape(r"text:a\{ & text:b"), r"text:'a\{' & text:'b'");
427        assert_eq!(shape("text:^a{2,3}$ & text:b"), "text:'^a{2,3}$' & text:'b'");
428        // A dangling `&` is part of the value.
429        assert_eq!(shape("text:a & "), "text:'a &'");
430        assert_eq!(parts("set:{text:a & text:b} & !text:c"), ["set:{text:a & text:b}", "!text:c"]);
431        assert_eq!(parts("text:a&b"), ["text:a&b"]);
432        assert_eq!(parts("text:a & !text:b"), ["text:a", "!text:b"]);
433    }
434
435    #[test]
436    fn sets_nest_rules_and_files() {
437        assert_eq!(shape("set:{text:a & !text:b} & text:c"), "set:{text:'a' & !text:'b'} & text:'c'");
438        assert_eq!(shape("set:={set:*{text:a}}"), "set:={set:*{text:'a'}}");
439        assert_eq!(shape("set:{ @ dir/list.txt }"), "set:@'dir/list.txt'");
440        assert_eq!(shape("set:{text:a}[x=1] & text:b"), "set:{text:'a'}+'[x=1]' & text:'b'");
441        // `@` and `=` start no set by themselves where the kind does not say so.
442        assert_eq!(shape("set:@ohos:net"), "set:'@ohos:net'");
443        assert_eq!(shape("set:=name"), "set:'=name'");
444        assert_eq!(shape("bare:=@list.txt"), "bare:=@'list.txt'");
445        assert_eq!(shape("bare:@list.txt[x=1] & text:a"), "bare:@'list.txt[x=1]' & text:'a'");
446        // Braces only open a set at the start of the value, and only for kinds with sets.
447        assert_eq!(shape("text:{a}"), "text:'{a}'");
448        assert_eq!(shape("set:a{2}"), "set:'a{2}'");
449        // A regex brace inside a set stays in its value.
450        assert_eq!(shape("set:{text:a{2}}"), "set:{text:'a{2}'}");
451        // An unmatched `}` closes a set; at the top it is text.
452        assert_eq!(shape("set:{text:a}b}"), "set:{text:'a'}+'b}'");
453        assert_eq!(shape("text:a}"), "text:'a}'");
454    }
455
456    #[test]
457    fn errors_say_what_and_where() {
458        for (rule, message) in [
459            ("bogus", "bad rule \"bogus\": expected KIND:VALUE, KIND one of text, set, bare at column 1"),
460            ("text:a & other:b", "bad rule \"text:a & other:b\": unknown kind \"other\" at column 10"),
461            ("text:", "bad rule \"text:\": empty value at column 6"),
462            ("set:{text:a", "bad rule \"set:{text:a\": expected `}` at column 12"),
463            ("set:{@}", "bad rule \"set:{@}\": empty value at column 7"),
464        ] {
465            assert_eq!(shape(rule), format!("error: {message}"), "{rule}");
466        }
467        let e = Rule::parse::<Test>("text:").unwrap_err();
468        assert_eq!((e.column(), e.message()), (6, "empty value"));
469    }
470
471    #[test]
472    fn sets_nest_up_to_the_limit() {
473        let nest = |n: usize| format!("{}text:a{}", "set:{".repeat(n), "}".repeat(n));
474        assert!(Rule::parse::<Test>(&nest(MAX_DEPTH)).is_ok());
475        // Far past the limit is an error, not a stack overflow.
476        for n in [MAX_DEPTH + 1, 100_000] {
477            assert!(shape(&nest(n)).contains(&format!("nested deeper than {MAX_DEPTH} levels")), "{n}");
478        }
479        // Siblings do not add up.
480        let wide = vec![nest(MAX_DEPTH); 50].join(" & ");
481        assert!(Rule::parse::<Test>(&wide).is_ok());
482    }
483
484    #[test]
485    fn a_set_file_reads_relative_to_its_directory() {
486        let dir = std::env::temp_dir();
487        let name = format!("asc-query-set-{}.txt", std::process::id());
488        std::fs::write(dir.join(&name), "La;->m()V\n").unwrap();
489        let rule = format!("set:{{@{name}}}");
490        let parsed = Rule::parse::<Test>(&rule).unwrap();
491        let Value::Set { set: Set::File(file), .. } = &parsed.parts[0].value else { panic!("a file set") };
492        assert_eq!(file.read(Some(&dir)).unwrap(), "La;->m()V\n");
493        assert!(file.read(Some(Path::new("/nonexistent"))).is_err());
494        std::fs::remove_file(dir.join(&name)).unwrap();
495    }
496}
asc_query/rule.rs

asc_query/
rule.rs
