litcheck_filecheck/check/
program.rs

1use std::collections::VecDeque;
2
3use crate::{
4    ast::*,
5    common::*,
6    errors::InvalidCheckFileError,
7    pattern::matcher::{MatchAll, MatchAny, SimpleMatcher},
8    rules::*,
9};
10
11/// A tree of patterns to match on the same region of input.
12///
13/// Once all patterns are matched, the matches are checked
14/// to ensure that they appear in the correct order.
15#[derive(Debug)]
16pub enum CheckTree<'a> {
17    /// The leaf node of this tree is a set of patterns to match as a group
18    Leaf(CheckGroup<'a>),
19    /// A two-way branch of the tree, rooted at a CHECK-NOT directive
20    Both {
21        /// Non-leaf nodes of the tree are rooted at a CHECK-NOT directive
22        root: MatchAny<'a>,
23        /// The patterns which must match before `root`
24        left: Box<CheckTree<'a>>,
25        /// The patterns which must match after `root`
26        right: Box<CheckTree<'a>>,
27    },
28    /// A single-branch node, rooted at a CHECK-NOT directive
29    Left {
30        /// Non-leaf nodes of the tree are rooted at a CHECK-NOT directive
31        root: MatchAny<'a>,
32        /// The patterns which must match before `root`
33        left: Box<CheckTree<'a>>,
34    },
35    /// A single-branch node, rooted at a CHECK-NOT directive
36    Right {
37        /// Non-leaf nodes of the tree are rooted at a CHECK-NOT directive
38        root: MatchAny<'a>,
39        /// The patterns which must match after `root`
40        right: Box<CheckTree<'a>>,
41    },
42}
43impl<'a> CheckTree<'a> {
44    pub fn leftmost(&self) -> Either<&CheckGroup<'a>, &MatchAny<'a>> {
45        match self {
46            Self::Leaf(ref group) => Left(group),
47            Self::Both { ref left, .. } | Self::Left { ref left, .. } => left.leftmost(),
48            Self::Right { ref root, .. } => Right(root),
49        }
50    }
51
52    pub fn rightmost(&self) -> Either<&CheckGroup<'a>, &MatchAny<'a>> {
53        match self {
54            Self::Leaf(ref group) => Left(group),
55            Self::Both { ref right, .. } | Self::Right { ref right, .. } => right.rightmost(),
56            Self::Left { ref root, .. } => Right(root),
57        }
58    }
59}
60
61#[derive(Debug)]
62pub enum CheckGroup<'a> {
63    /// This group type occurs when there are no patterns
64    /// except for a CHECK-NOT in a logical group. This is
65    /// a special case, but is preferable to representing
66    /// this using [CheckTree]
67    Never(MatchAny<'a>),
68    /// A group of rules that can be matched in any order,
69    /// but must not overlap each other, and must not extend
70    /// past any matches in subsequent groups. This latter
71    /// property is verified lazily, after the true bounds
72    /// of the group are known.
73    Unordered(Box<CheckDag<'a>>),
74    /// This is a special group type, used to anchor the search for
75    /// a CHECK-DAG rule to a following CHECK. This is purely used to
76    /// improve the accuracy of diagnostics related to match errors
77    /// involving this specific rule transition.
78    Bounded {
79        /// The CHECK-DAG rule to match
80        left: Box<CheckDag<'a>>,
81        /// The CHECK group to set the end of the searchable
82        /// region for the CHECK-DAG rule
83        right: Box<CheckGroup<'a>>,
84    },
85    /// A group of rules that must be matched consecutively,
86    /// and must not overlap.
87    Ordered(Vec<Box<dyn DynRule + 'a>>),
88    /// An implicit group formed by a rule that is repeated N times
89    Repeated {
90        rule: Box<dyn DynRule + 'a>,
91        count: usize,
92    },
93    /// A tree of patterns to match depth-first
94    ///
95    /// This group type occurs in the presence of CHECK-NOT directives
96    Tree(Box<CheckTree<'a>>),
97}
98impl<'a> CheckGroup<'a> {
99    pub fn first_pattern_span(&self) -> SourceSpan {
100        match self {
101            Self::Never(match_any) => match_any.first_pattern_span(),
102            Self::Unordered(check_dag) => check_dag.first_pattern_span(),
103            Self::Bounded { left, .. } => left.first_pattern_span(),
104            Self::Ordered(rules) => rules
105                .iter()
106                .map(|rule| rule.span())
107                .min_by_key(|span| span.start())
108                .unwrap(),
109            Self::Repeated { rule, .. } => rule.span(),
110            Self::Tree(tree) => match tree.leftmost() {
111                Left(group) => group.first_pattern_span(),
112                Right(match_any) => match_any.first_pattern_span(),
113            },
114        }
115    }
116
117    pub fn span(&self) -> SourceSpan {
118        match self {
119            Self::Never(match_any) => match_any.span(),
120            Self::Unordered(check_dag) => check_dag.span(),
121            Self::Bounded { left, right } => {
122                let start = left.span().start();
123                let end = right.span().end();
124                SourceSpan::from(start..end)
125            }
126            Self::Ordered(rules) => {
127                let start = rules[0].span().start();
128                let end = rules.last().unwrap().span().end();
129                SourceSpan::from(start..end)
130            }
131            Self::Repeated { rule, .. } => rule.span(),
132            Self::Tree(ref tree) => {
133                let leftmost_start = match tree.leftmost() {
134                    Left(left) => left.span().start(),
135                    Right(left) => left.span().start(),
136                };
137                let rightmost_end = match tree.rightmost() {
138                    Left(right) => right.span().end(),
139                    Right(right) => right.span().end(),
140                };
141                SourceSpan::from(leftmost_start..rightmost_end)
142            }
143        }
144    }
145}
146
147#[derive(Debug)]
148pub enum CheckSection<'a> {
149    /// Rules contained between two CHECK-LABEL directives, or between a CHECK-LABEL
150    /// directive and the end of the input, whichever comes first.
151    ///
152    /// The bounds of a block are known before evaluating the rules it contains,
153    /// so all searches in a block are automatically bounded to that block.
154    Block {
155        /// The input span which defines the bounds for searches in the block
156        label: SimpleMatcher<'a>,
157        body: Vec<CheckGroup<'a>>,
158    },
159    /// Rules which are part of a single logical group
160    ///
161    /// Groups are formed in one of the following ways:
162    ///
163    /// * Rules following a CHECK or CHECK-COUNT directive belong
164    /// to the same logical group, until a CHECK-NOT, CHECK-DAG,
165    /// or the next CHECK/CHECK-COUNT/CHECK-LABEL
166    ///
167    /// * A set of CHECK-NOT rules is its own special type of group,
168    /// see the Exclude* variants for details.
169    ///
170    /// * A set of CHECK-DAG rules is its own special type of group,
171    /// see the Unordered* variants for details.
172    Group { body: CheckGroup<'a> },
173}
174
175#[derive(Default, Debug)]
176pub struct CheckProgram<'a> {
177    pub sections: Vec<CheckSection<'a>>,
178}
179impl<'a> CheckProgram<'a> {
180    pub fn compile(
181        check_file: CheckFile<'a>,
182        config: &Config,
183        interner: &mut StringInterner,
184    ) -> DiagResult<Self> {
185        let lines = check_file.into_lines();
186        if lines.is_empty() {
187            return Err(Report::from(InvalidCheckFileError::Empty));
188        }
189
190        let mut program = Self::default();
191        program.compile_lines(lines, config, interner)?;
192
193        Ok(program)
194    }
195
196    /// Preprocess lines into blocks/groups
197    fn compile_lines(
198        &mut self,
199        lines: Vec<CheckLine<'a>>,
200        config: &Config,
201        interner: &mut StringInterner,
202    ) -> DiagResult<()> {
203        // Divide up input lines into blocks
204        let mut iter = lines.into_iter().peekable();
205        let mut label = None;
206        let mut block = vec![];
207        let mut blocks: VecDeque<(Option<CheckLine<'a>>, Vec<CheckLine<'a>>)> = VecDeque::default();
208        while let Some(next) = iter.peek() {
209            match next.kind() {
210                Check::Label => {
211                    if !block.is_empty() {
212                        blocks.push_back((label.take(), core::mem::take(&mut block)));
213                    }
214                    label = iter.next();
215                    while let Some(next) = iter.peek() {
216                        match next.kind() {
217                            Check::Label => {
218                                break;
219                            }
220                            _ => {
221                                block.push(iter.next().unwrap());
222                            }
223                        }
224                    }
225                }
226                Check::Empty | Check::Same | Check::Next if block.is_empty() && label.is_none() => {
227                    return Err(Report::from(InvalidCheckFileError::InvalidFirstCheck {
228                        kind: Check::Empty,
229                        line: next.span(),
230                    }));
231                }
232                Check::Plain
233                | Check::Count(_)
234                | Check::Next
235                | Check::Same
236                | Check::Not
237                | Check::Dag
238                | Check::Empty => {
239                    block.push(iter.next().unwrap());
240                }
241                _ => unreachable!(),
242            }
243        }
244
245        if !block.is_empty() {
246            blocks.push_back((label.take(), block));
247        }
248
249        self.compile_blocks(&mut blocks, config, interner)
250    }
251
252    /// Categorize and process blocks
253    fn compile_blocks(
254        &mut self,
255        blocks: &mut VecDeque<(Option<CheckLine<'a>>, Vec<CheckLine<'a>>)>,
256        config: &Config,
257        interner: &mut StringInterner,
258    ) -> DiagResult<()> {
259        let mut groups = vec![];
260        let mut pending_tree = None;
261
262        while let Some((maybe_label, body)) = blocks.pop_front() {
263            let mut body = VecDeque::from(body);
264            while let Some(line) = body.pop_front() {
265                match line.kind() {
266                    Check::Not => {
267                        assert!(pending_tree.is_none());
268                        let mut nots = vec![line];
269                        while let Some(next) = body.pop_front() {
270                            if matches!(next.kind(), Check::Not) {
271                                nots.push(next);
272                            } else {
273                                body.push_front(next);
274                                break;
275                            }
276                        }
277                        let matcher = MatchAny::from(MatchAll::compile(nots, config, interner)?);
278                        if body.is_empty() {
279                            match groups.pop() {
280                                Some(CheckGroup::Tree(left)) => {
281                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Left {
282                                        root: matcher,
283                                        left,
284                                    })))
285                                }
286                                Some(left @ CheckGroup::Unordered(_)) => {
287                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Left {
288                                        root: matcher,
289                                        left: Box::new(CheckTree::Leaf(left)),
290                                    })))
291                                }
292                                Some(group) => {
293                                    groups.push(group);
294                                    groups.push(CheckGroup::Never(matcher));
295                                }
296                                None => groups.push(CheckGroup::Never(matcher)),
297                            }
298                        } else {
299                            match groups.pop() {
300                                Some(CheckGroup::Tree(left)) => {
301                                    pending_tree = Some((Some(left), matcher));
302                                }
303                                Some(left @ CheckGroup::Unordered(_)) => {
304                                    let left = Box::new(CheckTree::Leaf(left));
305                                    pending_tree = Some((Some(left), matcher));
306                                }
307                                Some(group) => {
308                                    groups.push(group);
309                                    pending_tree = Some((None, matcher));
310                                }
311                                None => {
312                                    pending_tree = Some((None, matcher));
313                                }
314                            }
315                        }
316                    }
317                    Check::Dag => {
318                        let mut dags = vec![line];
319                        while let Some(next) = body.pop_front() {
320                            if matches!(next.kind(), Check::Dag) {
321                                dags.push(next);
322                            } else {
323                                body.push_front(next);
324                                break;
325                            }
326                        }
327                        let check_dag =
328                            Box::new(CheckDag::new(MatchAll::compile(dags, config, interner)?));
329
330                        let group = if matches!(
331                            body.front().map(|line| line.kind()),
332                            Some(Check::Plain | Check::Count(_))
333                        ) {
334                            let line = body.pop_front().unwrap();
335                            let bounding_group = match line.kind() {
336                                Check::Plain => CheckGroup::Ordered(vec![self.compile_rule(
337                                    line.ty,
338                                    line.pattern,
339                                    config,
340                                    interner,
341                                )?]),
342                                Check::Count(count) => CheckGroup::Repeated {
343                                    rule: self.compile_rule(
344                                        line.ty,
345                                        line.pattern,
346                                        config,
347                                        interner,
348                                    )?,
349                                    count,
350                                },
351                                _ => unsafe { std::hint::unreachable_unchecked() },
352                            };
353                            CheckGroup::Bounded {
354                                left: check_dag,
355                                right: Box::new(bounding_group),
356                            }
357                        } else {
358                            CheckGroup::Unordered(check_dag)
359                        };
360                        if let Some((maybe_left, root)) = pending_tree.take() {
361                            match maybe_left {
362                                Some(left) => {
363                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Both {
364                                        root,
365                                        left,
366                                        right: Box::new(CheckTree::Leaf(group)),
367                                    })));
368                                }
369                                None => {
370                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Right {
371                                        root,
372                                        right: Box::new(CheckTree::Leaf(group)),
373                                    })));
374                                }
375                            }
376                        } else {
377                            groups.push(group);
378                        }
379                    }
380                    Check::Count(count) => {
381                        let group = CheckGroup::Repeated {
382                            rule: self.compile_rule(line.ty, line.pattern, config, interner)?,
383                            count,
384                        };
385                        if let Some((maybe_left, root)) = pending_tree.take() {
386                            match maybe_left {
387                                Some(left) => {
388                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Both {
389                                        root,
390                                        left,
391                                        right: Box::new(CheckTree::Leaf(group)),
392                                    })));
393                                }
394                                None => {
395                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Right {
396                                        root,
397                                        right: Box::new(CheckTree::Leaf(group)),
398                                    })));
399                                }
400                            }
401                        } else {
402                            groups.push(group);
403                        }
404                    }
405                    _ => {
406                        body.push_front(line);
407                        let mut rules: Vec<Box<dyn DynRule + 'a>> = vec![];
408                        while let Some(next) = body.pop_front() {
409                            match next.kind() {
410                                Check::Not | Check::Dag | Check::Count(_) => {
411                                    body.push_front(next);
412                                    break;
413                                }
414                                Check::Empty => {
415                                    rules.push(Box::new(CheckEmpty::new(next.span())));
416                                }
417                                _ => {
418                                    rules.push(self.compile_rule(
419                                        next.ty,
420                                        next.pattern,
421                                        config,
422                                        interner,
423                                    )?);
424                                }
425                            }
426                        }
427                        let group = CheckGroup::Ordered(rules);
428                        if let Some((maybe_left, root)) = pending_tree.take() {
429                            match maybe_left {
430                                Some(left) => {
431                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Both {
432                                        root,
433                                        left,
434                                        right: Box::new(CheckTree::Leaf(group)),
435                                    })));
436                                }
437                                None => {
438                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Right {
439                                        root,
440                                        right: Box::new(CheckTree::Leaf(group)),
441                                    })));
442                                }
443                            }
444                        } else {
445                            groups.push(group);
446                        }
447                    }
448                }
449            }
450            assert!(pending_tree.is_none());
451            if let Some(label) = maybe_label {
452                let label = Pattern::compile_static(label.span, label.pattern, config, interner)?;
453                self.sections.push(CheckSection::Block {
454                    label,
455                    body: core::mem::take(&mut groups),
456                });
457            } else {
458                for body in core::mem::take(&mut groups).into_iter() {
459                    self.sections.push(CheckSection::Group { body });
460                }
461            }
462        }
463
464        Ok(())
465    }
466
467    fn compile_rule(
468        &mut self,
469        ty: CheckType,
470        pattern: CheckPattern<'a>,
471        config: &Config,
472        interner: &mut StringInterner,
473    ) -> DiagResult<Box<dyn DynRule + 'a>> {
474        let pattern = if ty.is_literal_match() {
475            Pattern::compile_literal(pattern, config)?
476        } else {
477            Pattern::compile(pattern, config, interner)?
478        };
479
480        match ty.kind {
481            Check::Plain | Check::Count(_) => {
482                Ok(Box::new(CheckPlain::new(pattern.into_matcher_mut())))
483            }
484            Check::Same => Ok(Box::new(CheckSame::new(pattern.into_matcher_mut()))),
485            Check::Next => Ok(Box::new(CheckNext::new(pattern.into_matcher_mut()))),
486            kind => unreachable!("we should never be compiling a rule for {kind} here"),
487        }
488    }
489}
litcheck_filecheck/check/program.rs

litcheck_filecheck/check/
program.rs
