litcheck_filecheck/rules/
dag.rs

1use crate::{
2    common::*,
3    pattern::{matcher::MatchAll, search::PatternSetSearcher, visitors::*},
4};
5
6#[derive(Debug)]
7pub struct CheckDag<'a> {
8    patterns: MatchAll<'a>,
9}
10impl<'a> CheckDag<'a> {
11    pub fn new(patterns: MatchAll<'a>) -> Self {
12        Self { patterns }
13    }
14
15    #[inline]
16    pub fn first_pattern_span(&self) -> SourceSpan {
17        self.patterns.first_pattern_span()
18    }
19}
20impl<'check> Spanned for CheckDag<'check> {
21    fn span(&self) -> SourceSpan {
22        self.patterns.span()
23    }
24}
25impl<'check> Rule for CheckDag<'check> {
26    fn kind(&self) -> Check {
27        Check::Dag
28    }
29
30    fn apply<'input, 'context, C>(&self, context: &mut C) -> DiagResult<Matches<'input>>
31    where
32        C: Context<'input, 'context> + ?Sized,
33    {
34        let mut guard = context.protect();
35        let input = guard.search_block();
36        let result = match self.patterns {
37            MatchAll::Literal(ref matcher) => {
38                let mut searcher = matcher.search(input)?;
39                let mut visitor = StaticPatternSetVisitor::new(&mut searcher);
40                visitor.try_match_all(&mut guard)
41            }
42            MatchAll::Regex(ref matcher) => {
43                let mut searcher = matcher.search(input);
44                let mut visitor = StaticPatternSetVisitor::new(&mut searcher);
45                visitor.try_match_all(&mut guard)
46            }
47            MatchAll::RegexPrefix {
48                ref prefixes,
49                ref suffixes,
50                ..
51            } => {
52                let mut searcher = prefixes.search(input);
53                let mut visitor = DynamicPatternSetVisitor::new(&mut searcher, suffixes);
54                visitor.try_match_all(&mut guard)
55            }
56            MatchAll::SubstringPrefix {
57                ref prefixes,
58                ref suffixes,
59            } => {
60                let mut searcher = prefixes.search(input)?;
61                let mut visitor = DynamicPatternSetVisitor::new(&mut searcher, suffixes);
62                visitor.try_match_all(&mut guard)
63            }
64            MatchAll::AnyPrefix {
65                ref prefixes,
66                ref suffixes,
67            } => {
68                let mut searcher = PatternSetSearcher::new(input, prefixes)?;
69                let mut visitor = DynamicPatternSetVisitor::new(&mut searcher, suffixes);
70                visitor.try_match_all(&mut guard)
71            }
72        };
73        match result {
74            Ok(result) if result.is_ok() => {
75                guard.save();
76                Ok(result)
77            }
78            result => result,
79        }
80    }
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86    use crate::check::CheckSection;
87    use std::assert_matches::assert_matches;
88    use std::collections::VecDeque;
89
90    /// This test ensures that the ordering of CHECK-DAG patterns is not
91    /// significant even in the presence of a common prefix. The test can
92    /// only pass if this is true, as line matched by the first directive
93    /// appears after the line matched by the second.
94    #[test]
95    fn check_dag_common_prefix_non_overlapping_patterns_test() -> DiagResult<()> {
96        let mut context = TestContext::new();
97        context
98            .with_checks(
99                "
100CHECK-DAG: v[[#]] = add v9, v0
101CHECK-DAG: v[[#]] = add v6, v7
102",
103            )
104            .with_input(
105                "
106function foo(i32) -> i32 {
107block0(v0: i32):
108  v2 = const.i32 0
109  v1 = const.i32 1
110  br block2(v1, v2)
111
112block1(v6: i32, v7: i32):
113  v8 = add v6, v7
114  v9 = const.i32 0
115  v10 = add v9, v0
116  br block3(v8, v10)
117
118block2(v3: i32, v4: i32):
119  v5 = mul v3, v4
120  br block1
121
122block3(v11):
123  ret v11
124}
125",
126            );
127        let match_file = context.match_file();
128        let match_file_source = match_file.as_ref();
129        let check_file = context.parse(match_file_source)?;
130
131        let lines = check_file.into_lines();
132
133        let mut mctx = context.match_context();
134        let match_all = MatchAll::compile(lines, &mctx.config, mctx.env.interner())?;
135        let rule = CheckDag::new(match_all);
136        let result = rule
137            .apply(&mut mctx)
138            .expect("expected non-fatal application of rule");
139
140        let test_result = TestResult::from_matches(result, &mctx);
141        test_result.into_result()?;
142
143        Ok(())
144    }
145
146    #[test]
147    fn check_dag_common_prefix_regex_non_overlapping_patterns_test() -> DiagResult<()> {
148        let mut context = TestContext::new();
149        context
150            .with_checks(
151                r"
152CHECK-DAG: {{v[\d]+}} = add v9, v0
153CHECK-DAG: {{v[\d]+}} = add v6, v7
154",
155            )
156            .with_input(
157                "
158function foo(i32) -> i32 {
159block0(v0: i32):
160  v2 = const.i32 0
161  v1 = const.i32 1
162  br block2(v1, v2)
163
164block1(v6: i32, v7: i32):
165  v8 = add v6, v7
166  v9 = const.i32 0
167  v10 = add v9, v0
168  br block3(v8, v10)
169
170block2(v3: i32, v4: i32):
171  v5 = mul v3, v4
172  br block1
173
174block3(v11):
175  ret v11
176}
177",
178            );
179        let match_file = context.match_file();
180        let match_file_source = match_file.as_ref();
181        let check_file = context.parse(match_file_source)?;
182
183        let lines = check_file.into_lines();
184
185        let mut mctx = context.match_context();
186        let match_all = MatchAll::compile(lines, &mctx.config, mctx.env.interner())?;
187        let rule = CheckDag::new(match_all);
188        let result = rule
189            .apply(&mut mctx)
190            .expect("expected non-fatal application of rule");
191
192        let test_result = TestResult::from_matches(result, &mctx);
193        test_result.into_result()?;
194
195        Ok(())
196    }
197
198    /// In this test, the first of the two CHECK-DAG directives can match the
199    /// same content as the second, while the second only has one possible match.
200    /// This test can only succeed if the ordering of the directives is not significant,
201    /// at least in this specific case. However, the catch here is that the reason the
202    /// test does not fail is because we always take the longest match first, so even
203    /// though the first directive would match the only line that the second can match,
204    /// the second directive wins because it matches a longer span of input.
205    #[test]
206    fn check_dag_overlapping_test() -> DiagResult<()> {
207        let mut context = TestContext::new();
208        context
209            .with_checks(
210                "
211CHECK-LABEL: block0:
212CHECK-DAG: v[[#]] = {{[a-z]+[.][a-z]+}}
213CHECK-DAG: v[[#]] = const.i32 0
214CHECK-LABEL: block1(
215CHECK: br block2(v[[#]], v[[#]])
216",
217            )
218            .with_input(
219                "
220function foo(i32) -> i32 {
221block0(v0: i32):
222  v2 = const.i32 0
223  v1 = const.i32 1
224  br block2(v1, v2)
225
226block1(v6: i32, v7: i32):
227  v8 = add v6, v7
228  v9 = const.i32 0
229  v10 = add v9, v0
230  br block3(v8, v10)
231
232block2(v3: i32, v4: i32):
233  v5 = mul v3, v4
234  br block1
235
236block3(v11):
237  ret v11
238}
239",
240            );
241        let match_file = context.match_file();
242        let match_file_source = match_file.as_ref();
243        let check_file = context.parse(match_file_source)?;
244
245        let mut lines = VecDeque::from(check_file.into_lines());
246        lines.pop_back();
247        lines.pop_back();
248        lines.pop_front();
249        let lines = Vec::from(lines);
250
251        let mut mctx = context.match_context();
252        let match_all = MatchAll::compile(lines, &mctx.config, mctx.env.interner())?;
253        let rule = CheckDag::new(match_all);
254        let result = rule
255            .apply(&mut mctx)
256            .expect("expected non-fatal application of rule");
257        let test_result = TestResult::from_matches(result, &mctx);
258        test_result.into_result()?;
259
260        Ok(())
261    }
262
263    /// This test ensures that a CHECK-DAG does not consider matches successful
264    /// outside the current block
265    #[test]
266    fn check_dag_does_not_search_beyond_check_label_boundaries_test() -> DiagResult<()> {
267        let mut context = TestContext::new();
268        context
269            .with_checks(
270                "
271CHECK-LABEL: block0(
272CHECK-DAG: v1 = const.i32 1
273CHECK-DAG: v8 = add v6, v7
274CHECK-LABEL: block1(
275CHECK-DAG: v8 = add v6, v7
276",
277            )
278            .with_input(
279                "
280function foo(i32) -> i32 {
281block0(v0: i32):
282  v2 = const.i32 0
283  v1 = const.i32 1
284  br block2(v1, v2)
285
286block1(v6: i32, v7: i32):
287  v8 = add v6, v7
288  v9 = const.i32 0
289  v10 = add v9, v0
290  br block3(v8, v10)
291
292block2(v3: i32, v4: i32):
293  v5 = mul v3, v4
294  br block1
295
296block3(v11):
297  ret v11
298}
299",
300            );
301        let match_file = context.match_file();
302        let match_file_source = match_file.as_ref();
303        let check_file = context.parse(match_file_source)?;
304        let mut program = context.compile(check_file)?;
305
306        let mut mctx = context.match_context();
307        let mut blocks = crate::check::discover_blocks(&program, &mut mctx)?;
308        assert_eq!(blocks.len(), 2);
309
310        blocks.pop().unwrap();
311        let block = blocks.pop().unwrap();
312        assert!(block.start.is_some());
313        assert_eq!(block.sections, Some(Range::new(0, 1)));
314        assert!(!block.range().is_empty());
315
316        mctx.enter_block(block.range());
317        assert_matches!(&program.sections[0], CheckSection::Block { .. });
318        program.sections.pop();
319
320        let test_result = crate::check::check_blocks([block], &program, &mut mctx);
321        assert!(test_result.is_failed());
322        if let [CheckFailedError::MatchNoneButExpected { .. }] = test_result.errors() {
323            Ok(())
324        } else {
325            Ok(test_result.into_result().map(|_| ())?)
326        }
327    }
328
329    /// This test ensures that all of the successful matches are contained within
330    /// their respective blocks.
331    #[test]
332    fn check_dag_check_label_boundaries_test() -> DiagResult<()> {
333        let mut context = TestContext::new();
334        context
335            .with_checks(
336                "
337CHECK-LABEL: block0(
338CHECK-DAG: v1 = const.i32 1
339CHECK-DAG: v2 = const.i32 0
340CHECK-LABEL: block1(
341CHECK-DAG: v8 = add v6, v7
342",
343            )
344            .with_input(
345                "
346function foo(i32) -> i32 {
347block0(v0: i32):
348  v2 = const.i32 0
349  v1 = const.i32 1
350  br block2(v1, v2)
351
352block1(v6: i32, v7: i32):
353  v8 = add v6, v7
354  v9 = const.i32 0
355  v10 = add v9, v0
356  br block3(v8, v10)
357
358block2(v3: i32, v4: i32):
359  v5 = mul v3, v4
360  br block1
361
362block3(v11):
363  ret v11
364}
365",
366            );
367        let match_file = context.match_file();
368        let match_file_source = match_file.as_ref();
369        let check_file = context.parse(match_file_source)?;
370        let program = context.compile(check_file)?;
371
372        let mut mctx = context.match_context();
373        let blocks = crate::check::discover_blocks(&program, &mut mctx)?;
374        assert_eq!(blocks.len(), 2);
375
376        let block = &blocks[0];
377        assert!(block.start.is_some());
378        assert_eq!(block.sections, Some(Range::new(0, 1)));
379        assert!(!block.range().is_empty());
380
381        mctx.enter_block(block.range());
382        let block_ranges = blocks
383            .iter()
384            .map(|blk| blk.range())
385            .collect::<SmallVec<[_; 2]>>();
386        let matches = crate::check::check_blocks(blocks, &program, &mut mctx).into_result()?;
387
388        assert_eq!(matches.len(), 5);
389        assert!(matches[0].span.end() <= block_ranges[0].start); // CHECK-LABEL
390        assert!(matches[1].span.end() <= block_ranges[0].end);
391        assert!(matches[2].span.end() <= block_ranges[0].end);
392        let match3_span = matches[3].span; // CHECK-LABEL
393        assert!(
394            match3_span.start() >= block_ranges[0].end
395                && match3_span.end() <= block_ranges[1].start
396        );
397        let match4_span = matches[4].span;
398        assert!(
399            match4_span.start() >= block_ranges[1].start
400                && match4_span.end() <= block_ranges[1].end
401        );
402        let match5_span = matches[4].span;
403        assert!(
404            match5_span.start() >= block_ranges[1].start
405                && match5_span.end() <= block_ranges[1].end
406        );
407
408        Ok(())
409    }
410}
litcheck_filecheck/rules/dag.rs

litcheck_filecheck/rules/
dag.rs
