LCOV - code coverage report
Current view: top level - lib/Support - GlobPattern.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 61 62 98.4 %
Date: 2018-10-20 13:21:21 Functions: 5 5 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- GlobPattern.cpp - Glob pattern matcher implementation -------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file implements a glob pattern matcher.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/Support/GlobPattern.h"
      15             : #include "llvm/ADT/ArrayRef.h"
      16             : #include "llvm/ADT/Optional.h"
      17             : #include "llvm/ADT/StringRef.h"
      18             : #include "llvm/Support/Errc.h"
      19             : 
      20             : using namespace llvm;
      21             : 
      22             : static bool hasWildcard(StringRef S) {
      23      372289 :   return S.find_first_of("?*[") != StringRef::npos;
      24             : }
      25             : 
      26             : // Expands character ranges and returns a bitmap.
      27             : // For example, "a-cf-hz" is expanded to "abcfghz".
      28          13 : static Expected<BitVector> expand(StringRef S, StringRef Original) {
      29          13 :   BitVector BV(256, false);
      30             : 
      31             :   // Expand X-Y.
      32             :   for (;;) {
      33          33 :     if (S.size() < 3)
      34             :       break;
      35             : 
      36          40 :     uint8_t Start = S[0];
      37          20 :     uint8_t End = S[2];
      38             : 
      39             :     // If it doesn't start with something like X-Y,
      40             :     // consume the first character and proceed.
      41          20 :     if (S[1] != '-') {
      42           4 :       BV[Start] = true;
      43           4 :       S = S.substr(1);
      44           4 :       continue;
      45             :     }
      46             : 
      47             :     // It must be in the form of X-Y.
      48             :     // Validate it and then interpret the range.
      49          16 :     if (Start > End)
      50           0 :       return make_error<StringError>("invalid glob pattern: " + Original,
      51             :                                      errc::invalid_argument);
      52             : 
      53          77 :     for (int C = Start; C <= End; ++C)
      54          61 :       BV[(uint8_t)C] = true;
      55          16 :     S = S.substr(3);
      56             :   }
      57             : 
      58          15 :   for (char C : S)
      59           2 :     BV[(uint8_t)C] = true;
      60             :   return BV;
      61             : }
      62             : 
      63             : // This is a scanner for the glob pattern.
      64             : // A glob pattern token is one of "*", "?", "[<chars>]", "[^<chars>]"
      65             : // (which is a negative form of "[<chars>]"), or a non-meta character.
      66             : // This function returns the first token in S.
      67         125 : static Expected<BitVector> scan(StringRef &S, StringRef Original) {
      68         250 :   switch (S[0]) {
      69          28 :   case '*':
      70          28 :     S = S.substr(1);
      71             :     // '*' is represented by an empty bitvector.
      72             :     // All other bitvectors are 256-bit long.
      73             :     return BitVector();
      74           3 :   case '?':
      75           3 :     S = S.substr(1);
      76           3 :     return BitVector(256, true);
      77          15 :   case '[': {
      78           2 :     size_t End = S.find(']', 1);
      79          13 :     if (End == StringRef::npos)
      80           2 :       return make_error<StringError>("invalid glob pattern: " + Original,
      81             :                                      errc::invalid_argument);
      82             : 
      83          13 :     StringRef Chars = S.substr(1, End - 1);
      84          26 :     S = S.substr(End + 1);
      85             :     if (Chars.startswith("^")) {
      86           6 :       Expected<BitVector> BV = expand(Chars.substr(1), Original);
      87           3 :       if (!BV)
      88             :         return BV.takeError();
      89           3 :       return BV->flip();
      90             :     }
      91          10 :     return expand(Chars, Original);
      92             :   }
      93          79 :   default:
      94          79 :     BitVector BV(256, false);
      95         158 :     BV[(uint8_t)S[0]] = true;
      96          79 :     S = S.substr(1);
      97             :     return BV;
      98             :   }
      99             : }
     100             : 
     101      371331 : Expected<GlobPattern> GlobPattern::create(StringRef S) {
     102             :   GlobPattern Pat;
     103             : 
     104             :   // S doesn't contain any metacharacter,
     105             :   // so the regular string comparison should work.
     106      371331 :   if (!hasWildcard(S)) {
     107             :     Pat.Exact = S;
     108             :     return Pat;
     109             :   }
     110             : 
     111             :   // S is something like "foo*". We can use startswith().
     112         930 :   if (S.endswith("*") && !hasWildcard(S.drop_back())) {
     113             :     Pat.Prefix = S.drop_back();
     114             :     return Pat;
     115             :   }
     116             : 
     117             :   // S is something like "*foo". We can use endswith().
     118          28 :   if (S.startswith("*") && !hasWildcard(S.drop_front())) {
     119             :     Pat.Suffix = S.drop_front();
     120             :     return Pat;
     121             :   }
     122             : 
     123             :   // Otherwise, we need to do real glob pattern matching.
     124             :   // Parse the pattern now.
     125          26 :   StringRef Original = S;
     126         149 :   while (!S.empty()) {
     127         248 :     Expected<BitVector> BV = scan(S, Original);
     128         125 :     if (!BV)
     129             :       return BV.takeError();
     130         123 :     Pat.Tokens.push_back(*BV);
     131             :   }
     132             :   return Pat;
     133             : }
     134             : 
     135      291428 : bool GlobPattern::match(StringRef S) const {
     136      291428 :   if (Exact)
     137             :     return S == *Exact;
     138      149412 :   if (Prefix)
     139             :     return S.startswith(*Prefix);
     140         573 :   if (Suffix)
     141             :     return S.endswith(*Suffix);
     142         216 :   return matchOne(Tokens, S);
     143             : }
     144             : 
     145             : // Runs glob pattern Pats against string S.
     146        3883 : bool GlobPattern::matchOne(ArrayRef<BitVector> Pats, StringRef S) const {
     147             :   for (;;) {
     148        4513 :     if (Pats.empty())
     149          17 :       return S.empty();
     150             : 
     151             :     // If Pats[0] is '*', try to match Pats[1..] against all possible
     152             :     // tail strings of S to see at least one pattern succeeds.
     153        4496 :     if (Pats[0].size() == 0) {
     154             :       Pats = Pats.slice(1);
     155         182 :       if (Pats.empty())
     156             :         // Fast path. If a pattern is '*', it matches anything.
     157             :         return true;
     158        3801 :       for (size_t I = 0, E = S.size(); I < E; ++I)
     159        3667 :         if (matchOne(Pats, S.substr(I)))
     160             :           return true;
     161             :       return false;
     162             :     }
     163             : 
     164             :     // If Pats[0] is not '*', it must consume one character.
     165        4314 :     if (S.empty() || !Pats[0][(uint8_t)S[0]])
     166             :       return false;
     167             :     Pats = Pats.slice(1);
     168         630 :     S = S.substr(1);
     169         630 :   }
     170             : }

Generated by: LCOV version 1.13