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

nextest_filtering/
expression.rs
