nextest_filtering/
expression.rs

1// Copyright (c) The nextest Contributors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4use crate::{
5    errors::{FiltersetParseErrors, ParseSingleError},
6    parsing::{
7        DisplayParsedRegex, DisplayParsedString, ExprResult, GenericGlob, ParsedExpr, ParsedLeaf,
8        new_span, parse,
9    },
10};
11use guppy::{
12    PackageId,
13    graph::{BuildTargetId, PackageGraph, PackageMetadata, cargo::BuildPlatform},
14};
15use miette::SourceSpan;
16use nextest_metadata::{RustBinaryId, RustTestBinaryKind};
17use recursion::{Collapsible, CollapsibleExt, MappableFrame, PartiallyApplied};
18use smol_str::SmolStr;
19use std::{collections::HashSet, fmt, sync::OnceLock};
20
21/// Matcher for name
22///
23/// Used both for package name and test name
24#[derive(Debug, Clone)]
25pub enum NameMatcher {
26    /// Exact value
27    Equal { value: String, implicit: bool },
28    /// Simple contains test
29    Contains { value: String, implicit: bool },
30    /// Test against a glob
31    Glob { glob: GenericGlob, implicit: bool },
32    /// Test against a regex
33    Regex(regex::Regex),
34}
35
36impl NameMatcher {
37    pub(crate) fn implicit_equal(value: String) -> Self {
38        Self::Equal {
39            value,
40            implicit: true,
41        }
42    }
43
44    pub(crate) fn implicit_contains(value: String) -> Self {
45        Self::Contains {
46            value,
47            implicit: true,
48        }
49    }
50}
51
52impl PartialEq for NameMatcher {
53    fn eq(&self, other: &Self) -> bool {
54        match (self, other) {
55            (
56                Self::Contains {
57                    value: s1,
58                    implicit: default1,
59                },
60                Self::Contains {
61                    value: s2,
62                    implicit: default2,
63                },
64            ) => s1 == s2 && default1 == default2,
65            (
66                Self::Equal {
67                    value: s1,
68                    implicit: default1,
69                },
70                Self::Equal {
71                    value: s2,
72                    implicit: default2,
73                },
74            ) => s1 == s2 && default1 == default2,
75            (Self::Regex(r1), Self::Regex(r2)) => r1.as_str() == r2.as_str(),
76            (Self::Glob { glob: g1, .. }, Self::Glob { glob: g2, .. }) => {
77                g1.regex().as_str() == g2.regex().as_str()
78            }
79            _ => false,
80        }
81    }
82}
83
84impl Eq for NameMatcher {}
85
86impl fmt::Display for NameMatcher {
87    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
88        match self {
89            Self::Equal { value, implicit } => write!(
90                f,
91                "{}{}",
92                if *implicit { "" } else { "=" },
93                DisplayParsedString(value)
94            ),
95            Self::Contains { value, implicit } => write!(
96                f,
97                "{}{}",
98                if *implicit { "" } else { "~" },
99                DisplayParsedString(value)
100            ),
101            Self::Glob { glob, implicit } => write!(
102                f,
103                "{}{}",
104                if *implicit { "" } else { "#" },
105                DisplayParsedString(glob.as_str())
106            ),
107            Self::Regex(r) => write!(f, "/{}/", DisplayParsedRegex(r)),
108        }
109    }
110}
111
112/// A leaf node in a filterset expression tree.
113#[derive(Debug, Clone, PartialEq, Eq)]
114pub enum FiltersetLeaf {
115    /// All tests in packages
116    Packages(HashSet<PackageId>),
117    /// All tests present in this kind of binary.
118    Kind(NameMatcher, SourceSpan),
119    /// The platform a test is built for.
120    Platform(BuildPlatform, SourceSpan),
121    /// All binaries matching a name
122    Binary(NameMatcher, SourceSpan),
123    /// All binary IDs matching a name
124    BinaryId(NameMatcher, SourceSpan),
125    /// All tests matching a name
126    Test(NameMatcher, SourceSpan),
127    /// The default set of tests to run.
128    Default,
129    /// All tests
130    All,
131    /// No tests
132    None,
133}
134
135impl FiltersetLeaf {
136    /// Returns true if this leaf can only be evaluated at runtime, i.e. it
137    /// requires test names to be available.
138    ///
139    /// Currently, this also returns true (conservatively) for the `Default`
140    /// leaf, which is used to represent the default set of tests to run.
141    pub fn is_runtime_only(&self) -> bool {
142        matches!(self, Self::Test(_, _) | Self::Default)
143    }
144}
145
146/// A query for a binary, passed into [`Filterset::matches_binary`].
147#[derive(Copy, Clone, Debug, Eq, PartialEq)]
148pub struct BinaryQuery<'a> {
149    /// The package ID.
150    pub package_id: &'a PackageId,
151
152    /// The binary ID.
153    pub binary_id: &'a RustBinaryId,
154
155    /// The name of the binary.
156    pub binary_name: &'a str,
157
158    /// The kind of binary this test is (lib, test etc).
159    pub kind: &'a RustTestBinaryKind,
160
161    /// The platform this test is built for.
162    pub platform: BuildPlatform,
163}
164
165/// A query for a specific test, passed into [`Filterset::matches_test`].
166#[derive(Copy, Clone, Debug, Eq, PartialEq)]
167pub struct TestQuery<'a> {
168    /// The binary query.
169    pub binary_query: BinaryQuery<'a>,
170
171    /// The name of the test.
172    pub test_name: &'a str,
173}
174
175/// A filterset that has been parsed and compiled.
176///
177/// Used to filter tests to run.
178#[derive(Debug, Clone, PartialEq, Eq)]
179pub struct Filterset {
180    /// The raw expression passed in.
181    pub input: String,
182
183    /// The parsed-but-not-compiled expression.
184    pub parsed: ParsedExpr,
185
186    /// The compiled expression.
187    pub compiled: CompiledExpr,
188}
189
190#[derive(Debug, Clone, PartialEq, Eq)]
191pub enum CompiledExpr {
192    /// Accepts every test not in the given expression
193    Not(Box<CompiledExpr>),
194    /// Accepts every test in either given expression
195    Union(Box<CompiledExpr>, Box<CompiledExpr>),
196    /// Accepts every test in both given expressions
197    Intersection(Box<CompiledExpr>, Box<CompiledExpr>),
198    /// Accepts every test in a set
199    Set(FiltersetLeaf),
200}
201
202impl CompiledExpr {
203    /// Returns a value indicating all tests are accepted by this filterset.
204    pub const ALL: Self = CompiledExpr::Set(FiltersetLeaf::All);
205
206    /// Returns a value indicating if the given binary is accepted by this filterset.
207    ///
208    /// The value is:
209    /// * `Some(true)` if this binary is definitely accepted by this filterset.
210    /// * `Some(false)` if this binary is definitely not accepted.
211    /// * `None` if this binary might or might not be accepted.
212    pub fn matches_binary(&self, query: &BinaryQuery<'_>, cx: &EvalContext<'_>) -> Option<bool> {
213        use ExprFrame::*;
214        Wrapped(self).collapse_frames(|layer: ExprFrame<&FiltersetLeaf, Option<bool>>| {
215            match layer {
216                Set(set) => set.matches_binary(query, cx),
217                Not(a) => a.logic_not(),
218                // TODO: or_else/and_then?
219                Union(a, b) => a.logic_or(b),
220                Intersection(a, b) => a.logic_and(b),
221                Difference(a, b) => a.logic_and(b.logic_not()),
222                Parens(a) => a,
223            }
224        })
225    }
226
227    /// Returns true if the given test is accepted by this filterset.
228    pub fn matches_test(&self, query: &TestQuery<'_>, cx: &EvalContext<'_>) -> bool {
229        use ExprFrame::*;
230        Wrapped(self).collapse_frames(|layer: ExprFrame<&FiltersetLeaf, bool>| match layer {
231            Set(set) => set.matches_test(query, cx),
232            Not(a) => !a,
233            Union(a, b) => a || b,
234            Intersection(a, b) => a && b,
235            Difference(a, b) => a && !b,
236            Parens(a) => a,
237        })
238    }
239}
240
241impl NameMatcher {
242    pub(crate) fn is_match(&self, input: &str) -> bool {
243        match self {
244            Self::Equal { value, .. } => value == input,
245            Self::Contains { value, .. } => input.contains(value),
246            Self::Glob { glob, .. } => glob.is_match(input),
247            Self::Regex(reg) => reg.is_match(input),
248        }
249    }
250}
251
252impl FiltersetLeaf {
253    fn matches_test(&self, query: &TestQuery<'_>, cx: &EvalContext) -> bool {
254        match self {
255            Self::All => true,
256            Self::None => false,
257            Self::Default => cx.default_filter.matches_test(query, cx),
258            Self::Test(matcher, _) => matcher.is_match(query.test_name),
259            Self::Binary(matcher, _) => matcher.is_match(query.binary_query.binary_name),
260            Self::BinaryId(matcher, _) => matcher.is_match(query.binary_query.binary_id.as_str()),
261            Self::Platform(platform, _) => query.binary_query.platform == *platform,
262            Self::Kind(matcher, _) => matcher.is_match(query.binary_query.kind.as_str()),
263            Self::Packages(packages) => packages.contains(query.binary_query.package_id),
264        }
265    }
266
267    fn matches_binary(&self, query: &BinaryQuery<'_>, cx: &EvalContext) -> Option<bool> {
268        match self {
269            Self::All => Logic::top(),
270            Self::None => Logic::bottom(),
271            Self::Default => cx.default_filter.matches_binary(query, cx),
272            Self::Test(_, _) => None,
273            Self::Binary(matcher, _) => Some(matcher.is_match(query.binary_name)),
274            Self::BinaryId(matcher, _) => Some(matcher.is_match(query.binary_id.as_str())),
275            Self::Platform(platform, _) => Some(query.platform == *platform),
276            Self::Kind(matcher, _) => Some(matcher.is_match(query.kind.as_str())),
277            Self::Packages(packages) => Some(packages.contains(query.package_id)),
278        }
279    }
280}
281
282/// Inputs to filterset parsing.
283#[derive(Debug)]
284pub struct ParseContext<'g> {
285    /// The package graph.
286    graph: &'g PackageGraph,
287
288    /// Cached data computed on first access.
289    cache: OnceLock<ParseContextCache<'g>>,
290}
291
292impl<'g> ParseContext<'g> {
293    /// Creates a new `ParseContext`.
294    #[inline]
295    pub fn new(graph: &'g PackageGraph) -> Self {
296        Self {
297            graph,
298            cache: OnceLock::new(),
299        }
300    }
301
302    /// Returns the package graph.
303    #[inline]
304    pub fn graph(&self) -> &'g PackageGraph {
305        self.graph
306    }
307
308    pub(crate) fn make_cache(&self) -> &ParseContextCache<'g> {
309        self.cache
310            .get_or_init(|| ParseContextCache::new(self.graph))
311    }
312}
313
314#[derive(Debug)]
315pub(crate) struct ParseContextCache<'g> {
316    pub(crate) workspace_packages: Vec<PackageMetadata<'g>>,
317    // Ordinarily we'd store RustBinaryId here, but that wouldn't allow looking
318    // up a string.
319    pub(crate) binary_ids: HashSet<SmolStr>,
320    pub(crate) binary_names: HashSet<&'g str>,
321}
322
323impl<'g> ParseContextCache<'g> {
324    fn new(graph: &'g PackageGraph) -> Self {
325        let workspace_packages: Vec<_> = graph
326            .resolve_workspace()
327            .packages(guppy::graph::DependencyDirection::Forward)
328            .collect();
329        let (binary_ids, binary_names) = workspace_packages
330            .iter()
331            .flat_map(|pkg| {
332                pkg.build_targets().filter_map(|bt| {
333                    let kind = compute_kind(&bt.id())?;
334                    let binary_id = RustBinaryId::from_parts(pkg.name(), &kind, bt.name());
335                    Some((SmolStr::new(binary_id.as_str()), bt.name()))
336                })
337            })
338            .unzip();
339
340        Self {
341            workspace_packages,
342            binary_ids,
343            binary_names,
344        }
345    }
346}
347
348fn compute_kind(id: &BuildTargetId<'_>) -> Option<RustTestBinaryKind> {
349    match id {
350        // Note this covers both libraries and proc macros, but we treat
351        // libraries the same as proc macros while constructing a `RustBinaryId`
352        // anyway.
353        BuildTargetId::Library => Some(RustTestBinaryKind::LIB),
354        BuildTargetId::Benchmark(_) => Some(RustTestBinaryKind::BENCH),
355        BuildTargetId::Example(_) => Some(RustTestBinaryKind::EXAMPLE),
356        BuildTargetId::BuildScript => {
357            // Build scripts don't have tests in them.
358            None
359        }
360        BuildTargetId::Binary(_) => Some(RustTestBinaryKind::BIN),
361        BuildTargetId::Test(_) => Some(RustTestBinaryKind::TEST),
362        _ => panic!("unknown build target id: {id:?}"),
363    }
364}
365
366/// The kind of filterset being parsed.
367#[derive(Copy, Clone, Debug, PartialEq, Eq)]
368pub enum FiltersetKind {
369    /// A test filterset.
370    Test,
371
372    /// A default-filter filterset.
373    ///
374    /// To prevent recursion, default-filter expressions cannot contain `default()` themselves.
375    /// (This is a limited kind of the infinite recursion checking we'll need to do in the future.)
376    DefaultFilter,
377}
378
379impl fmt::Display for FiltersetKind {
380    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
381        match self {
382            Self::Test => write!(f, "test"),
383            Self::DefaultFilter => write!(f, "default-filter"),
384        }
385    }
386}
387
388/// Inputs to filterset evaluation functions.
389#[derive(Copy, Clone, Debug)]
390pub struct EvalContext<'a> {
391    /// The default set of tests to run.
392    pub default_filter: &'a CompiledExpr,
393}
394
395impl Filterset {
396    /// Parse a filterset.
397    pub fn parse(
398        input: String,
399        cx: &ParseContext<'_>,
400        kind: FiltersetKind,
401    ) -> Result<Self, FiltersetParseErrors> {
402        let mut errors = Vec::new();
403        match parse(new_span(&input, &mut errors)) {
404            Ok(parsed_expr) => {
405                if !errors.is_empty() {
406                    return Err(FiltersetParseErrors::new(input.clone(), errors));
407                }
408
409                match parsed_expr {
410                    ExprResult::Valid(parsed) => {
411                        let compiled = crate::compile::compile(&parsed, cx, kind)
412                            .map_err(|errors| FiltersetParseErrors::new(input.clone(), errors))?;
413                        Ok(Self {
414                            input,
415                            parsed,
416                            compiled,
417                        })
418                    }
419                    _ => {
420                        // should not happen
421                        // If an ParsedExpr::Error is produced, we should also have an error inside
422                        // errors and we should already have returned
423                        // IMPROVE this is an internal error => add log to suggest opening an bug ?
424                        Err(FiltersetParseErrors::new(
425                            input,
426                            vec![ParseSingleError::Unknown],
427                        ))
428                    }
429                }
430            }
431            Err(_) => {
432                // should not happen
433                // According to our parsing strategy we should never produce an Err(_)
434                // IMPROVE this is an internal error => add log to suggest opening an bug ?
435                Err(FiltersetParseErrors::new(
436                    input,
437                    vec![ParseSingleError::Unknown],
438                ))
439            }
440        }
441    }
442
443    /// Returns a value indicating if the given binary is accepted by this filterset.
444    ///
445    /// The value is:
446    /// * `Some(true)` if this binary is definitely accepted by this filterset.
447    /// * `Some(false)` if this binary is definitely not accepted.
448    /// * `None` if this binary might or might not be accepted.
449    pub fn matches_binary(&self, query: &BinaryQuery<'_>, cx: &EvalContext<'_>) -> Option<bool> {
450        self.compiled.matches_binary(query, cx)
451    }
452
453    /// Returns true if the given test is accepted by this filterset.
454    pub fn matches_test(&self, query: &TestQuery<'_>, cx: &EvalContext<'_>) -> bool {
455        self.compiled.matches_test(query, cx)
456    }
457
458    /// Returns true if the given expression needs dependencies information to work
459    pub fn needs_deps(raw_expr: &str) -> bool {
460        // the expression needs dependencies expression if it uses deps(..) or rdeps(..)
461        raw_expr.contains("deps")
462    }
463}
464
465/// A propositional logic used to evaluate `Expression` instances.
466///
467/// An `Expression` consists of some predicates and the `any`, `all` and `not` operators. An
468/// implementation of `Logic` defines how the `any`, `all` and `not` operators should be evaluated.
469trait Logic {
470    /// The result of an `all` operation with no operands, akin to Boolean `true`.
471    fn top() -> Self;
472
473    /// The result of an `any` operation with no operands, akin to Boolean `false`.
474    fn bottom() -> Self;
475
476    /// `AND`, which corresponds to the `all` operator.
477    fn logic_and(self, other: Self) -> Self;
478
479    /// `OR`, which corresponds to the `any` operator.
480    fn logic_or(self, other: Self) -> Self;
481
482    /// `NOT`, which corresponds to the `not` operator.
483    fn logic_not(self) -> Self;
484}
485
486/// A boolean logic.
487impl Logic for bool {
488    #[inline]
489    fn top() -> Self {
490        true
491    }
492
493    #[inline]
494    fn bottom() -> Self {
495        false
496    }
497
498    #[inline]
499    fn logic_and(self, other: Self) -> Self {
500        self && other
501    }
502
503    #[inline]
504    fn logic_or(self, other: Self) -> Self {
505        self || other
506    }
507
508    #[inline]
509    fn logic_not(self) -> Self {
510        !self
511    }
512}
513
514/// A three-valued logic -- `None` stands for the value being unknown.
515///
516/// The truth tables for this logic are described on
517/// [Wikipedia](https://en.wikipedia.org/wiki/Three-valued_logic#Kleene_and_Priest_logics).
518impl Logic for Option<bool> {
519    #[inline]
520    fn top() -> Self {
521        Some(true)
522    }
523
524    #[inline]
525    fn bottom() -> Self {
526        Some(false)
527    }
528
529    #[inline]
530    fn logic_and(self, other: Self) -> Self {
531        match (self, other) {
532            // If either is false, the expression is false.
533            (Some(false), _) | (_, Some(false)) => Some(false),
534            // If both are true, the expression is true.
535            (Some(true), Some(true)) => Some(true),
536            // One or both are unknown -- the result is unknown.
537            _ => None,
538        }
539    }
540
541    #[inline]
542    fn logic_or(self, other: Self) -> Self {
543        match (self, other) {
544            // If either is true, the expression is true.
545            (Some(true), _) | (_, Some(true)) => Some(true),
546            // If both are false, the expression is false.
547            (Some(false), Some(false)) => Some(false),
548            // One or both are unknown -- the result is unknown.
549            _ => None,
550        }
551    }
552
553    #[inline]
554    fn logic_not(self) -> Self {
555        self.map(|v| !v)
556    }
557}
558
559pub(crate) enum ExprFrame<Set, A> {
560    Not(A),
561    Union(A, A),
562    Intersection(A, A),
563    Difference(A, A),
564    Parens(A),
565    Set(Set),
566}
567
568impl<Set> MappableFrame for ExprFrame<Set, PartiallyApplied> {
569    type Frame<Next> = ExprFrame<Set, Next>;
570
571    fn map_frame<A, B>(input: Self::Frame<A>, mut f: impl FnMut(A) -> B) -> Self::Frame<B> {
572        use ExprFrame::*;
573        match input {
574            Not(a) => Not(f(a)),
575            // Note: reverse the order because the recursion crate processes
576            // entries via a stack, as LIFO. Calling f(b) before f(a) means
577            // error messages for a show up before those for b.
578            Union(a, b) => {
579                let b = f(b);
580                let a = f(a);
581                Union(a, b)
582            }
583            Intersection(a, b) => {
584                let b = f(b);
585                let a = f(a);
586                Intersection(a, b)
587            }
588            Difference(a, b) => {
589                let b = f(b);
590                let a = f(a);
591                Difference(a, b)
592            }
593            Parens(a) => Parens(f(a)),
594            Set(f) => Set(f),
595        }
596    }
597}
598
599// Wrapped struct to prevent trait impl leakages.
600pub(crate) struct Wrapped<T>(pub(crate) T);
601
602impl<'a> Collapsible for Wrapped<&'a CompiledExpr> {
603    type FrameToken = ExprFrame<&'a FiltersetLeaf, PartiallyApplied>;
604
605    fn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self> {
606        match self.0 {
607            CompiledExpr::Not(a) => ExprFrame::Not(Wrapped(a.as_ref())),
608            CompiledExpr::Union(a, b) => ExprFrame::Union(Wrapped(a.as_ref()), Wrapped(b.as_ref())),
609            CompiledExpr::Intersection(a, b) => {
610                ExprFrame::Intersection(Wrapped(a.as_ref()), Wrapped(b.as_ref()))
611            }
612            CompiledExpr::Set(f) => ExprFrame::Set(f),
613        }
614    }
615}
616
617impl<'a> Collapsible for Wrapped<&'a ParsedExpr> {
618    type FrameToken = ExprFrame<&'a ParsedLeaf, PartiallyApplied>;
619
620    fn into_frame(self) -> <Self::FrameToken as MappableFrame>::Frame<Self> {
621        match self.0 {
622            ParsedExpr::Not(_, a) => ExprFrame::Not(Wrapped(a.as_ref())),
623            ParsedExpr::Union(_, a, b) => {
624                ExprFrame::Union(Wrapped(a.as_ref()), Wrapped(b.as_ref()))
625            }
626            ParsedExpr::Intersection(_, a, b) => {
627                ExprFrame::Intersection(Wrapped(a.as_ref()), Wrapped(b.as_ref()))
628            }
629            ParsedExpr::Difference(_, a, b) => {
630                ExprFrame::Difference(Wrapped(a.as_ref()), Wrapped(b.as_ref()))
631            }
632            ParsedExpr::Parens(a) => ExprFrame::Parens(Wrapped(a.as_ref())),
633            ParsedExpr::Set(f) => ExprFrame::Set(f),
634        }
635    }
636}
nextest_filtering/expression.rs

nextest_filtering/
expression.rs
