Dogcows Code - chaz/yoink/blob - src/stlplus/portability/wildcard.cpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2
   3 //   Author:    Andy Rushton
   4 //   Copyright: (c) Southampton University 1999-2004
   5 //              (c) Andy Rushton           2004-2009
   6 //   License:   BSD License, see ../docs/license.html
   7
   8 //   Simple wildcard matching function.
   9
  10 //   WARNING: wheel re-invention follows
  11 //   Given that all shells perform wildcard matching, why don't the library writers put it in the C run-time????????
  12
  13 ////////////////////////////////////////////////////////////////////////////////
  14 #include "wildcard.hpp"
  15
  16 namespace stlplus
  17 {
  18
  19   // function for testing whether a character matches a set
  20   // I can't remember the exact rules and I have no definitive references but:
  21   // a set contains characters, escaped characters (I think) and ranges in the form a-z
  22   // The character '-' can only appear at the start of the set where it is not interpreted as a range
  23   // This is a horrible mess - blame the Unix folks for making a hash of wildcards
  24   // first expand any ranges and remove escape characters to make life more palatable
  25
  26   static bool match_set (const std::string& set, char match)
  27   {
  28     std::string simple_set;
  29     for (std::string::const_iterator i = set.begin(); i != set.end(); ++i)
  30     {
  31       switch(*i)
  32       {
  33       case '-':
  34       {
  35         if (i == set.begin())
  36         {
  37           simple_set += *i;
  38         }
  39         else if (i+1 == set.end())
  40         {
  41           return false;
  42         }
  43         else
  44         {
  45           // found a set. The first character is already in the result, so first remove it (the set might be empty)
  46           simple_set.erase(simple_set.end()-1);
  47           char last = *++i;
  48           for (char ch = *(i-2); ch <= last; ch++)
  49           {
  50             simple_set += ch;
  51           }
  52         }
  53         break;
  54       }
  55       case '\\':
  56         if (i+1 == set.end()) {return false;}
  57         simple_set += *++i;
  58         break;
  59       default:
  60         simple_set += *i;
  61         break;
  62       }
  63     }
  64     std::string::size_type result = simple_set.find(match);
  65     return result != std::string::npos;
  66   }
  67
  68   // the recursive bit - basically whenever a * is found you recursively call this for each candidate substring match
  69   // until either it succeeds or you run out of string to match
  70   // for each * in the wildcard another level of recursion is created
  71
  72   static bool match_remainder (const std::string& wild, std::string::const_iterator wildi, const std::string& match, std::string::const_iterator matchi)
  73   {
  74     //cerr << "match_remainder called at " << *matchi << " with wildcard " << *wildi << endl;
  75     while (wildi != wild.end() && matchi != match.end())
  76     {
  77       //cerr << "trying to match " << *matchi << " with wildcard " << *wildi << endl;
  78       switch(*wildi)
  79       {
  80       case '*':
  81       {
  82         ++wildi;
  83         ++matchi;
  84         for (std::string::const_iterator i = matchi; i != match.end(); ++i)
  85         {
  86           // deal with * at the end of the wildcard - there is no remainder then
  87           if (wildi == wild.end())
  88           {
  89             if (i == match.end()-1)
  90               return true;
  91           }
  92           else if (match_remainder(wild, wildi, match, i))
  93           {
  94             return true;
  95           }
  96         }
  97         return false;
  98       }
  99       case '[':
 100       {
 101         // scan for the end of the set using a similar method for avoiding escaped characters
 102         bool found = false;
 103         std::string::const_iterator end = wildi + 1;
 104         for (; !found && end != wild.end(); ++end)
 105         {
 106           switch(*end)
 107           {
 108           case ']':
 109           {
 110             // found the set, now match with its contents excluding the brackets
 111             if (!match_set(wild.substr(wildi - wild.begin() + 1, end - wildi - 1), *matchi))
 112               return false;
 113             found = true;
 114             break;
 115           }
 116           case '\\':
 117             if (end == wild.end()-1)
 118               return false;
 119             ++end;
 120             break;
 121           default:
 122             break;
 123           }
 124         }
 125         if (!found)
 126           return false;
 127         ++matchi;
 128         wildi = end;
 129         break;
 130       }
 131       case '?':
 132         ++wildi;
 133         ++matchi;
 134         break;
 135       case '\\':
 136         if (wildi == wild.end()-1)
 137           return false;
 138         ++wildi;
 139         if (*wildi != *matchi)
 140           return false;
 141         ++wildi;
 142         ++matchi;
 143         break;
 144       default:
 145         if (*wildi != *matchi)
 146           return false;
 147         ++wildi;
 148         ++matchi;
 149         break;
 150       }
 151     }
 152     bool result = wildi == wild.end() && matchi == match.end();
 153     return result;
 154   }
 155
 156   // like all recursions the exported function has a simpler interface than the
 157   // recursive function and is just a 'seed' to the recursion itself
 158
 159   bool wildcard(const std::string& wild, const std::string& match)
 160   {
 161     return match_remainder(wild, wild.begin(), match, match.begin());
 162   }
 163
 164 } // end namespace stlplus