Line data    Source code

       1             : #include "glob.h"
       2             : 
       3             : #include <cstdint>
       4             : 
       5             : namespace datadog {
       6             : namespace tracing {
       7             : 
       8          48 : bool glob_match(StringView pattern, StringView subject) {
       9             :   // This is a backtracking implementation of the glob matching algorithm.
      10             :   // The glob pattern language supports `*` and `?`, but no escape sequences.
      11             :   //
      12             :   // Based off of a Go example in <https://research.swtch.com/glob> accessed
      13             :   // February 3, 2022.
      14             : 
      15             :   using Index = std::size_t;
      16          48 :   Index p = 0;       // [p]attern index
      17          48 :   Index s = 0;       // [s]ubject index
      18          48 :   Index next_p = 0;  // next [p]attern index
      19          48 :   Index next_s = 0;  // next [s]ubject index
      20             : 
      21         518 :   while (p < pattern.size() || s < subject.size()) {
      22         489 :     if (p < pattern.size()) {
      23         428 :       const char pattern_char = pattern[p];
      24         428 :       switch (pattern_char) {
      25         125 :         case '*':
      26             :           // Try to match at `s`.  If that doesn't work out, restart at
      27             :           // `s + 1` next.
      28         125 :           next_p = p;
      29         125 :           next_s = s + 1;
      30         125 :           ++p;
      31         125 :           continue;
      32           8 :         case '?':
      33           8 :           if (s < subject.size()) {
      34           7 :             ++p;
      35           7 :             ++s;
      36           7 :             continue;
      37             :           }
      38           1 :           break;
      39         295 :         default:
      40         295 :           if (s < subject.size() && subject[s] == pattern_char) {
      41         233 :             ++p;
      42         233 :             ++s;
      43         233 :             continue;
      44             :           }
      45             :       }
      46             :     }
      47             :     // Mismatch.  Maybe restart.
      48         124 :     if (0 < next_s && next_s <= subject.size()) {
      49         105 :       p = next_p;
      50         105 :       s = next_s;
      51         105 :       continue;
      52             :     }
      53          19 :     return false;
      54             :   }
      55          29 :   return true;
      56             : }
      57             : 
      58             : }  // namespace tracing
      59             : }  // namespace datadog