Module functional_tests::checker::matcher

source ·
Expand description

This module implements a matcher that checks if an evaluation log matches the patterns specified by a list of directives.

The directives first get divided into groups, where each group consists of 0 or more negative directives, followed by an optional positive directive.

// Directives:
//     not: 1
//     not: 2
//     check: 3
//     not: 4
//     check: bar
//     not : 6

// Groups:
//     group 1:
//         not: 1
//         not: 2
//         check: 3
//     group 2:
//         not: 4
//         check: bar
//     group 3:
//         not: 6

Then in order, we take one group at a time and match it against the evaluation log. Recall that the (stringified) evaluation log is essentially a list of string entries that look like this:

// [1] abc de
// [2] foo 3
// [3] bar 6
// [4] 7

For each group, we find the earliest place in the current entry where any of the directives matches. - If the matched directive is negative, abort and report error. - If the matched directive is positive, move on to the next group and start a new match right after the last matched location. - If no match is found, retry the current group with the next entry in the log.

Example matches:

// [1] abc de
// [2] foo 3
//         ^
//         check: 3
// [3] bar 6
//     ^^^ ^
//     |   not 6
//     check: bar
// [4] 7

Note: the group matching procedure above requires searching for multiple string patterns simultatenously. Right now this is implemented using the Aho-Corasick algorithm, achieving an overall time complexity of O(n), where n is the length of the log + the total length of the string patterns in the directives.

In order for the match to succeed, it is required that: 1) All positive directives are matched. 2) No negative directives are matched. 3) All error entries in the log are matched.

The example above would fail with a negative match.

Structs

  • Match
    A single match consisting of the index of the log entry, the start location and the end location (in bytes).
  • MatchResult
    The result of matching the directives against the evaluation log.

Enums

Functions

  • match_output
    Matches the directives against the evaluation log.