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(Box<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 to the same logical group,
164    ///   until a  `CHECK-NOT`, `CHECK-DAG`, or the next `CHECK`/`CHECK-COUNT`/`CHECK-LABEL`
165    /// * A set of `CHECK-NOT` rules is its own special type of group, see the Exclude* variants for
166    ///   details.
167    /// * A set of `CHECK-DAG` rules is its own special type of group, see the Unordered* variants
168    ///   for details.
169    Group { body: CheckGroup<'a> },
170}
171
172#[derive(Default, Debug)]
173pub struct CheckProgram<'a> {
174    pub sections: Vec<CheckSection<'a>>,
175}
176impl<'a> CheckProgram<'a> {
177    pub fn compile(
178        check_file: CheckFile<'a>,
179        config: &Config,
180        interner: &mut StringInterner,
181    ) -> DiagResult<Self> {
182        let lines = check_file.into_lines();
183        if lines.is_empty() {
184            return Err(Report::from(InvalidCheckFileError::Empty));
185        }
186
187        let mut program = Self::default();
188        program.compile_lines(lines, config, interner)?;
189
190        Ok(program)
191    }
192
193    /// Preprocess lines into blocks/groups
194    fn compile_lines(
195        &mut self,
196        lines: Vec<CheckLine<'a>>,
197        config: &Config,
198        interner: &mut StringInterner,
199    ) -> DiagResult<()> {
200        // Divide up input lines into blocks
201        let mut iter = lines.into_iter().peekable();
202        let mut label = None;
203        let mut block = vec![];
204        let mut blocks: VecDeque<(Option<CheckLine<'a>>, Vec<CheckLine<'a>>)> = VecDeque::default();
205        while let Some(next) = iter.peek() {
206            match next.kind() {
207                Check::Label => {
208                    if !block.is_empty() {
209                        blocks.push_back((label.take(), core::mem::take(&mut block)));
210                    }
211                    label = iter.next();
212                    while let Some(next) = iter.peek() {
213                        match next.kind() {
214                            Check::Label => {
215                                break;
216                            }
217                            _ => {
218                                block.push(iter.next().unwrap());
219                            }
220                        }
221                    }
222                }
223                Check::Empty | Check::Same | Check::Next if block.is_empty() && label.is_none() => {
224                    return Err(Report::from(InvalidCheckFileError::InvalidFirstCheck {
225                        kind: Check::Empty,
226                        line: next.span(),
227                    }));
228                }
229                Check::Plain
230                | Check::Count(_)
231                | Check::Next
232                | Check::Same
233                | Check::Not
234                | Check::Dag
235                | Check::Empty => {
236                    block.push(iter.next().unwrap());
237                }
238                _ => unreachable!(),
239            }
240        }
241
242        if !block.is_empty() {
243            blocks.push_back((label.take(), block));
244        }
245
246        self.compile_blocks(&mut blocks, config, interner)
247    }
248
249    /// Categorize and process blocks
250    fn compile_blocks(
251        &mut self,
252        blocks: &mut VecDeque<(Option<CheckLine<'a>>, Vec<CheckLine<'a>>)>,
253        config: &Config,
254        interner: &mut StringInterner,
255    ) -> DiagResult<()> {
256        let mut groups = vec![];
257        let mut pending_tree = None;
258
259        while let Some((maybe_label, body)) = blocks.pop_front() {
260            let mut body = VecDeque::from(body);
261            while let Some(line) = body.pop_front() {
262                match line.kind() {
263                    Check::Not => {
264                        assert!(pending_tree.is_none());
265                        let mut nots = vec![line];
266                        while let Some(next) = body.pop_front() {
267                            if matches!(next.kind(), Check::Not) {
268                                nots.push(next);
269                            } else {
270                                body.push_front(next);
271                                break;
272                            }
273                        }
274                        let matcher = MatchAny::from(MatchAll::compile(nots, config, interner)?);
275                        if body.is_empty() {
276                            match groups.pop() {
277                                Some(CheckGroup::Tree(left)) => {
278                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Left {
279                                        root: matcher,
280                                        left,
281                                    })))
282                                }
283                                Some(left @ CheckGroup::Unordered(_)) => {
284                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Left {
285                                        root: matcher,
286                                        left: Box::new(CheckTree::Leaf(left)),
287                                    })))
288                                }
289                                Some(group) => {
290                                    groups.push(group);
291                                    groups.push(CheckGroup::Never(Box::new(matcher)));
292                                }
293                                None => groups.push(CheckGroup::Never(Box::new(matcher))),
294                            }
295                        } else {
296                            match groups.pop() {
297                                Some(CheckGroup::Tree(left)) => {
298                                    pending_tree = Some((Some(left), matcher));
299                                }
300                                Some(left @ CheckGroup::Unordered(_)) => {
301                                    let left = Box::new(CheckTree::Leaf(left));
302                                    pending_tree = Some((Some(left), matcher));
303                                }
304                                Some(group) => {
305                                    groups.push(group);
306                                    pending_tree = Some((None, matcher));
307                                }
308                                None => {
309                                    pending_tree = Some((None, matcher));
310                                }
311                            }
312                        }
313                    }
314                    Check::Dag => {
315                        let mut dags = vec![line];
316                        while let Some(next) = body.pop_front() {
317                            if matches!(next.kind(), Check::Dag) {
318                                dags.push(next);
319                            } else {
320                                body.push_front(next);
321                                break;
322                            }
323                        }
324                        let check_dag =
325                            Box::new(CheckDag::new(MatchAll::compile(dags, config, interner)?));
326
327                        let group = if matches!(
328                            body.front().map(|line| line.kind()),
329                            Some(Check::Plain | Check::Count(_))
330                        ) {
331                            let line = body.pop_front().unwrap();
332                            let bounding_group = match line.kind() {
333                                Check::Plain => CheckGroup::Ordered(vec![self.compile_rule(
334                                    line.ty,
335                                    line.pattern,
336                                    config,
337                                    interner,
338                                )?]),
339                                Check::Count(count) => CheckGroup::Repeated {
340                                    rule: self.compile_rule(
341                                        line.ty,
342                                        line.pattern,
343                                        config,
344                                        interner,
345                                    )?,
346                                    count,
347                                },
348                                _ => unsafe { std::hint::unreachable_unchecked() },
349                            };
350                            CheckGroup::Bounded {
351                                left: check_dag,
352                                right: Box::new(bounding_group),
353                            }
354                        } else {
355                            CheckGroup::Unordered(check_dag)
356                        };
357                        if let Some((maybe_left, root)) = pending_tree.take() {
358                            match maybe_left {
359                                Some(left) => {
360                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Both {
361                                        root,
362                                        left,
363                                        right: Box::new(CheckTree::Leaf(group)),
364                                    })));
365                                }
366                                None => {
367                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Right {
368                                        root,
369                                        right: Box::new(CheckTree::Leaf(group)),
370                                    })));
371                                }
372                            }
373                        } else {
374                            groups.push(group);
375                        }
376                    }
377                    Check::Count(count) => {
378                        let group = CheckGroup::Repeated {
379                            rule: self.compile_rule(line.ty, line.pattern, config, interner)?,
380                            count,
381                        };
382                        if let Some((maybe_left, root)) = pending_tree.take() {
383                            match maybe_left {
384                                Some(left) => {
385                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Both {
386                                        root,
387                                        left,
388                                        right: Box::new(CheckTree::Leaf(group)),
389                                    })));
390                                }
391                                None => {
392                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Right {
393                                        root,
394                                        right: Box::new(CheckTree::Leaf(group)),
395                                    })));
396                                }
397                            }
398                        } else {
399                            groups.push(group);
400                        }
401                    }
402                    _ => {
403                        body.push_front(line);
404                        let mut rules: Vec<Box<dyn DynRule + 'a>> = vec![];
405                        while let Some(next) = body.pop_front() {
406                            match next.kind() {
407                                Check::Not | Check::Dag | Check::Count(_) => {
408                                    body.push_front(next);
409                                    break;
410                                }
411                                Check::Empty => {
412                                    rules.push(Box::new(CheckEmpty::new(next.span())));
413                                }
414                                _ => {
415                                    rules.push(self.compile_rule(
416                                        next.ty,
417                                        next.pattern,
418                                        config,
419                                        interner,
420                                    )?);
421                                }
422                            }
423                        }
424                        let group = CheckGroup::Ordered(rules);
425                        if let Some((maybe_left, root)) = pending_tree.take() {
426                            match maybe_left {
427                                Some(left) => {
428                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Both {
429                                        root,
430                                        left,
431                                        right: Box::new(CheckTree::Leaf(group)),
432                                    })));
433                                }
434                                None => {
435                                    groups.push(CheckGroup::Tree(Box::new(CheckTree::Right {
436                                        root,
437                                        right: Box::new(CheckTree::Leaf(group)),
438                                    })));
439                                }
440                            }
441                        } else {
442                            groups.push(group);
443                        }
444                    }
445                }
446            }
447            assert!(pending_tree.is_none());
448            if let Some(label) = maybe_label {
449                let label = Pattern::compile_static(label.span, label.pattern, config, interner)?;
450                self.sections.push(CheckSection::Block {
451                    label,
452                    body: core::mem::take(&mut groups),
453                });
454            } else {
455                for body in core::mem::take(&mut groups).into_iter() {
456                    self.sections.push(CheckSection::Group { body });
457                }
458            }
459        }
460
461        Ok(())
462    }
463
464    fn compile_rule(
465        &mut self,
466        ty: CheckType,
467        pattern: CheckPattern<'a>,
468        config: &Config,
469        interner: &mut StringInterner,
470    ) -> DiagResult<Box<dyn DynRule + 'a>> {
471        let pattern = if ty.is_literal_match() {
472            Pattern::compile_literal(pattern, config)?
473        } else {
474            Pattern::compile(pattern, config, interner)?
475        };
476
477        match ty.kind {
478            Check::Plain | Check::Count(_) => {
479                Ok(Box::new(CheckPlain::new(pattern.into_matcher_mut())))
480            }
481            Check::Same => Ok(Box::new(CheckSame::new(pattern.into_matcher_mut()))),
482            Check::Next => Ok(Box::new(CheckNext::new(pattern.into_matcher_mut()))),
483            kind => unreachable!("we should never be compiling a rule for {kind} here"),
484        }
485    }
486}
litcheck_filecheck/check/program.rs

litcheck_filecheck/check/
program.rs
