[ tor-browser ].git.dasho

Wildcard.cpp (16062B)
      1 // Common/Wildcard.cpp
      2 
      3 #include "StdAfx.h"
      4 
      5 #include "Wildcard.h"
      6 
      7 bool g_CaseSensitive =
      8  #ifdef _WIN32
      9    false;
     10  #else
     11    true;
     12  #endif
     13 
     14 
     15 bool IsPath1PrefixedByPath2(const wchar_t *s1, const wchar_t *s2)
     16 {
     17  if (g_CaseSensitive)
     18    return IsString1PrefixedByString2(s1, s2);
     19  return IsString1PrefixedByString2_NoCase(s1, s2);
     20 }
     21 
     22 int CompareFileNames(const wchar_t *s1, const wchar_t *s2) STRING_UNICODE_THROW
     23 {
     24  if (g_CaseSensitive)
     25    return MyStringCompare(s1, s2);
     26  return MyStringCompareNoCase(s1, s2);
     27 }
     28 
     29 #ifndef USE_UNICODE_FSTRING
     30 int CompareFileNames(const char *s1, const char *s2)
     31 {
     32  const UString u1 = fs2us(s1);
     33  const UString u2 = fs2us(s2);
     34  if (g_CaseSensitive)
     35    return MyStringCompare(u1, u2);
     36  return MyStringCompareNoCase(u1, u2);
     37 }
     38 #endif
     39 
     40 // -----------------------------------------
     41 // this function compares name with mask
     42 // ? - any char
     43 // * - any char or empty
     44 
     45 static bool EnhancedMaskTest(const wchar_t *mask, const wchar_t *name)
     46 {
     47  for (;;)
     48  {
     49    wchar_t m = *mask;
     50    wchar_t c = *name;
     51    if (m == 0)
     52      return (c == 0);
     53    if (m == '*')
     54    {
     55      if (EnhancedMaskTest(mask + 1, name))
     56        return true;
     57      if (c == 0)
     58        return false;
     59    }
     60    else
     61    {
     62      if (m == '?')
     63      {
     64        if (c == 0)
     65          return false;
     66      }
     67      else if (m != c)
     68        if (g_CaseSensitive || MyCharUpper(m) != MyCharUpper(c))
     69          return false;
     70      mask++;
     71    }
     72    name++;
     73  }
     74 }
     75 
     76 // --------------------------------------------------
     77 // Splits path to strings
     78 
     79 void SplitPathToParts(const UString &path, UStringVector &pathParts)
     80 {
     81  pathParts.Clear();
     82  unsigned len = path.Len();
     83  if (len == 0)
     84    return;
     85  UString name;
     86  unsigned prev = 0;
     87  for (unsigned i = 0; i < len; i++)
     88    if (IsPathSepar(path[i]))
     89    {
     90      name.SetFrom(path.Ptr(prev), i - prev);
     91      pathParts.Add(name);
     92      prev = i + 1;
     93    }
     94  name.SetFrom(path.Ptr(prev), len - prev);
     95  pathParts.Add(name);
     96 }
     97 
     98 void SplitPathToParts_2(const UString &path, UString &dirPrefix, UString &name)
     99 {
    100  const wchar_t *start = path;
    101  const wchar_t *p = start + path.Len();
    102  for (; p != start; p--)
    103    if (IsPathSepar(*(p - 1)))
    104      break;
    105  dirPrefix.SetFrom(path, (unsigned)(p - start));
    106  name = p;
    107 }
    108 
    109 void SplitPathToParts_Smart(const UString &path, UString &dirPrefix, UString &name)
    110 {
    111  const wchar_t *start = path;
    112  const wchar_t *p = start + path.Len();
    113  if (p != start)
    114  {
    115    if (IsPathSepar(*(p - 1)))
    116      p--;
    117    for (; p != start; p--)
    118      if (IsPathSepar(*(p - 1)))
    119        break;
    120  }
    121  dirPrefix.SetFrom(path, (unsigned)(p - start));
    122  name = p;
    123 }
    124 
    125 /*
    126 UString ExtractDirPrefixFromPath(const UString &path)
    127 {
    128  return path.Left(path.ReverseFind_PathSepar() + 1));
    129 }
    130 */
    131 
    132 UString ExtractFileNameFromPath(const UString &path)
    133 {
    134  return UString(path.Ptr(path.ReverseFind_PathSepar() + 1));
    135 }
    136 
    137 
    138 bool DoesWildcardMatchName(const UString &mask, const UString &name)
    139 {
    140  return EnhancedMaskTest(mask, name);
    141 }
    142 
    143 bool DoesNameContainWildcard(const UString &path)
    144 {
    145  for (unsigned i = 0; i < path.Len(); i++)
    146  {
    147    wchar_t c = path[i];
    148    if (c == '*' || c == '?')
    149      return true;
    150  }
    151  return false;
    152 }
    153 
    154 
    155 // ----------------------------------------------------------'
    156 // NWildcard
    157 
    158 namespace NWildcard {
    159 
    160 /*
    161 
    162 M = MaskParts.Size();
    163 N = TestNameParts.Size();
    164 
    165                           File                          Dir
    166 ForFile     rec   M<=N  [N-M, N)                          -
    167 !ForDir  nonrec   M=N   [0, M)                            -
    168 
    169 ForDir      rec   M<N   [0, M) ... [N-M-1, N-1)  same as ForBoth-File
    170 !ForFile nonrec         [0, M)                   same as ForBoth-File
    171 
    172 ForFile     rec   m<=N  [0, M) ... [N-M, N)      same as ForBoth-File
    173 ForDir   nonrec         [0, M)                   same as ForBoth-File
    174 
    175 */
    176 
    177 bool CItem::AreAllAllowed() const
    178 {
    179  return ForFile && ForDir && WildcardMatching && PathParts.Size() == 1 && PathParts.Front() == L"*";
    180 }
    181 
    182 bool CItem::CheckPath(const UStringVector &pathParts, bool isFile) const
    183 {
    184  if (!isFile && !ForDir)
    185    return false;
    186 
    187  /*
    188  if (PathParts.IsEmpty())
    189  {
    190    // PathParts.IsEmpty() means all items (universal wildcard)
    191    if (!isFile)
    192      return true;
    193    if (pathParts.Size() <= 1)
    194      return ForFile;
    195    return (ForDir || Recursive && ForFile);
    196  }
    197  */
    198 
    199  int delta = (int)pathParts.Size() - (int)PathParts.Size();
    200  if (delta < 0)
    201    return false;
    202  int start = 0;
    203  int finish = 0;
    204  
    205  if (isFile)
    206  {
    207    if (!ForDir)
    208    {
    209      if (Recursive)
    210        start = delta;
    211      else if (delta !=0)
    212        return false;
    213    }
    214    if (!ForFile && delta == 0)
    215      return false;
    216  }
    217  
    218  if (Recursive)
    219  {
    220    finish = delta;
    221    if (isFile && !ForFile)
    222      finish = delta - 1;
    223  }
    224  
    225  for (int d = start; d <= finish; d++)
    226  {
    227    unsigned i;
    228    for (i = 0; i < PathParts.Size(); i++)
    229    {
    230      if (WildcardMatching)
    231      {
    232        if (!DoesWildcardMatchName(PathParts[i], pathParts[i + d]))
    233          break;
    234      }
    235      else
    236      {
    237        if (CompareFileNames(PathParts[i], pathParts[i + d]) != 0)
    238          break;
    239      }
    240    }
    241    if (i == PathParts.Size())
    242      return true;
    243  }
    244  return false;
    245 }
    246 
    247 bool CCensorNode::AreAllAllowed() const
    248 {
    249  if (!Name.IsEmpty() ||
    250      !SubNodes.IsEmpty() ||
    251      !ExcludeItems.IsEmpty() ||
    252      IncludeItems.Size() != 1)
    253    return false;
    254  return IncludeItems.Front().AreAllAllowed();
    255 }
    256 
    257 int CCensorNode::FindSubNode(const UString &name) const
    258 {
    259  FOR_VECTOR (i, SubNodes)
    260    if (CompareFileNames(SubNodes[i].Name, name) == 0)
    261      return i;
    262  return -1;
    263 }
    264 
    265 void CCensorNode::AddItemSimple(bool include, CItem &item)
    266 {
    267  if (include)
    268    IncludeItems.Add(item);
    269  else
    270    ExcludeItems.Add(item);
    271 }
    272 
    273 void CCensorNode::AddItem(bool include, CItem &item, int ignoreWildcardIndex)
    274 {
    275  if (item.PathParts.Size() <= 1)
    276  {
    277    if (item.PathParts.Size() != 0 && item.WildcardMatching)
    278    {
    279      if (!DoesNameContainWildcard(item.PathParts.Front()))
    280        item.WildcardMatching = false;
    281    }
    282    AddItemSimple(include, item);
    283    return;
    284  }
    285  const UString &front = item.PathParts.Front();
    286  
    287  // WIN32 doesn't support wildcards in file names
    288  if (item.WildcardMatching
    289      && ignoreWildcardIndex != 0
    290      && DoesNameContainWildcard(front))
    291  {
    292    AddItemSimple(include, item);
    293    return;
    294  }
    295  int index = FindSubNode(front);
    296  if (index < 0)
    297    index = SubNodes.Add(CCensorNode(front, this));
    298  item.PathParts.Delete(0);
    299  SubNodes[index].AddItem(include, item, ignoreWildcardIndex - 1);
    300 }
    301 
    302 void CCensorNode::AddItem(bool include, const UString &path, bool recursive, bool forFile, bool forDir, bool wildcardMatching)
    303 {
    304  CItem item;
    305  SplitPathToParts(path, item.PathParts);
    306  item.Recursive = recursive;
    307  item.ForFile = forFile;
    308  item.ForDir = forDir;
    309  item.WildcardMatching = wildcardMatching;
    310  AddItem(include, item);
    311 }
    312 
    313 bool CCensorNode::NeedCheckSubDirs() const
    314 {
    315  FOR_VECTOR (i, IncludeItems)
    316  {
    317    const CItem &item = IncludeItems[i];
    318    if (item.Recursive || item.PathParts.Size() > 1)
    319      return true;
    320  }
    321  return false;
    322 }
    323 
    324 bool CCensorNode::AreThereIncludeItems() const
    325 {
    326  if (IncludeItems.Size() > 0)
    327    return true;
    328  FOR_VECTOR (i, SubNodes)
    329    if (SubNodes[i].AreThereIncludeItems())
    330      return true;
    331  return false;
    332 }
    333 
    334 bool CCensorNode::CheckPathCurrent(bool include, const UStringVector &pathParts, bool isFile) const
    335 {
    336  const CObjectVector<CItem> &items = include ? IncludeItems : ExcludeItems;
    337  FOR_VECTOR (i, items)
    338    if (items[i].CheckPath(pathParts, isFile))
    339      return true;
    340  return false;
    341 }
    342 
    343 bool CCensorNode::CheckPathVect(const UStringVector &pathParts, bool isFile, bool &include) const
    344 {
    345  if (CheckPathCurrent(false, pathParts, isFile))
    346  {
    347    include = false;
    348    return true;
    349  }
    350  include = true;
    351  bool finded = CheckPathCurrent(true, pathParts, isFile);
    352  if (pathParts.Size() <= 1)
    353    return finded;
    354  int index = FindSubNode(pathParts.Front());
    355  if (index >= 0)
    356  {
    357    UStringVector pathParts2 = pathParts;
    358    pathParts2.Delete(0);
    359    if (SubNodes[index].CheckPathVect(pathParts2, isFile, include))
    360      return true;
    361  }
    362  return finded;
    363 }
    364 
    365 /*
    366 bool CCensorNode::CheckPath2(bool isAltStream, const UString &path, bool isFile, bool &include) const
    367 {
    368  UStringVector pathParts;
    369  SplitPathToParts(path, pathParts);
    370  if (CheckPathVect(pathParts, isFile, include))
    371  {
    372    if (!include || !isAltStream)
    373      return true;
    374  }
    375  if (isAltStream && !pathParts.IsEmpty())
    376  {
    377    UString &back = pathParts.Back();
    378    int pos = back.Find(L':');
    379    if (pos > 0)
    380    {
    381      back.DeleteFrom(pos);
    382      return CheckPathVect(pathParts, isFile, include);
    383    }
    384  }
    385  return false;
    386 }
    387 
    388 bool CCensorNode::CheckPath(bool isAltStream, const UString &path, bool isFile) const
    389 {
    390  bool include;
    391  if (CheckPath2(isAltStream, path, isFile, include))
    392    return include;
    393  return false;
    394 }
    395 */
    396 
    397 bool CCensorNode::CheckPathToRoot(bool include, UStringVector &pathParts, bool isFile) const
    398 {
    399  if (CheckPathCurrent(include, pathParts, isFile))
    400    return true;
    401  if (Parent == 0)
    402    return false;
    403  pathParts.Insert(0, Name);
    404  return Parent->CheckPathToRoot(include, pathParts, isFile);
    405 }
    406 
    407 /*
    408 bool CCensorNode::CheckPathToRoot(bool include, const UString &path, bool isFile) const
    409 {
    410  UStringVector pathParts;
    411  SplitPathToParts(path, pathParts);
    412  return CheckPathToRoot(include, pathParts, isFile);
    413 }
    414 */
    415 
    416 void CCensorNode::AddItem2(bool include, const UString &path, bool recursive, bool wildcardMatching)
    417 {
    418  if (path.IsEmpty())
    419    return;
    420  bool forFile = true;
    421  bool forFolder = true;
    422  UString path2 (path);
    423  if (IsPathSepar(path.Back()))
    424  {
    425    path2.DeleteBack();
    426    forFile = false;
    427  }
    428  AddItem(include, path2, recursive, forFile, forFolder, wildcardMatching);
    429 }
    430 
    431 void CCensorNode::ExtendExclude(const CCensorNode &fromNodes)
    432 {
    433  ExcludeItems += fromNodes.ExcludeItems;
    434  FOR_VECTOR (i, fromNodes.SubNodes)
    435  {
    436    const CCensorNode &node = fromNodes.SubNodes[i];
    437    int subNodeIndex = FindSubNode(node.Name);
    438    if (subNodeIndex < 0)
    439      subNodeIndex = SubNodes.Add(CCensorNode(node.Name, this));
    440    SubNodes[subNodeIndex].ExtendExclude(node);
    441  }
    442 }
    443 
    444 int CCensor::FindPrefix(const UString &prefix) const
    445 {
    446  FOR_VECTOR (i, Pairs)
    447    if (CompareFileNames(Pairs[i].Prefix, prefix) == 0)
    448      return i;
    449  return -1;
    450 }
    451 
    452 #ifdef _WIN32
    453 
    454 bool IsDriveColonName(const wchar_t *s)
    455 {
    456  wchar_t c = s[0];
    457  return c != 0 && s[1] == ':' && s[2] == 0 && (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z');
    458 }
    459 
    460 unsigned GetNumPrefixParts_if_DrivePath(UStringVector &pathParts)
    461 {
    462  if (pathParts.IsEmpty())
    463    return 0;
    464  
    465  unsigned testIndex = 0;
    466  if (pathParts[0].IsEmpty())
    467  {
    468    if (pathParts.Size() < 4
    469        || !pathParts[1].IsEmpty()
    470        || pathParts[2] != L"?")
    471      return 0;
    472    testIndex = 3;
    473  }
    474  if (NWildcard::IsDriveColonName(pathParts[testIndex]))
    475    return testIndex + 1;
    476  return 0;
    477 }
    478 
    479 #endif
    480 
    481 static unsigned GetNumPrefixParts(const UStringVector &pathParts)
    482 {
    483  if (pathParts.IsEmpty())
    484    return 0;
    485  
    486  #ifdef _WIN32
    487  
    488  if (IsDriveColonName(pathParts[0]))
    489    return 1;
    490  if (!pathParts[0].IsEmpty())
    491    return 0;
    492 
    493  if (pathParts.Size() == 1)
    494    return 1;
    495  if (!pathParts[1].IsEmpty())
    496    return 1;
    497  if (pathParts.Size() == 2)
    498    return 2;
    499  if (pathParts[2] == L".")
    500    return 3;
    501 
    502  unsigned networkParts = 2;
    503  if (pathParts[2] == L"?")
    504  {
    505    if (pathParts.Size() == 3)
    506      return 3;
    507    if (IsDriveColonName(pathParts[3]))
    508      return 4;
    509    if (!pathParts[3].IsEqualTo_Ascii_NoCase("UNC"))
    510      return 3;
    511    networkParts = 4;
    512  }
    513 
    514  networkParts +=
    515      // 2; // server/share
    516      1; // server
    517  if (pathParts.Size() <= networkParts)
    518    return pathParts.Size();
    519  return networkParts;
    520 
    521  #else
    522  
    523  return pathParts[0].IsEmpty() ? 1 : 0;
    524 
    525  #endif
    526 }
    527 
    528 void CCensor::AddItem(ECensorPathMode pathMode, bool include, const UString &path, bool recursive, bool wildcardMatching)
    529 {
    530  if (path.IsEmpty())
    531    throw "Empty file path";
    532 
    533  UStringVector pathParts;
    534  SplitPathToParts(path, pathParts);
    535 
    536  bool forFile = true;
    537  if (pathParts.Back().IsEmpty())
    538  {
    539    forFile = false;
    540    pathParts.DeleteBack();
    541  }
    542  
    543  UString prefix;
    544  
    545  int ignoreWildcardIndex = -1;
    546 
    547  // #ifdef _WIN32
    548  // we ignore "?" wildcard in "\\?\" prefix.
    549  if (pathParts.Size() >= 3
    550      && pathParts[0].IsEmpty()
    551      && pathParts[1].IsEmpty()
    552      && pathParts[2] == L"?")
    553    ignoreWildcardIndex = 2;
    554  // #endif
    555 
    556  if (pathMode != k_AbsPath)
    557  {
    558    ignoreWildcardIndex = -1;
    559 
    560    const unsigned numPrefixParts = GetNumPrefixParts(pathParts);
    561    unsigned numSkipParts = numPrefixParts;
    562 
    563    if (pathMode != k_FullPath)
    564    {
    565      if (numPrefixParts != 0 && pathParts.Size() > numPrefixParts)
    566        numSkipParts = pathParts.Size() - 1;
    567    }
    568    {
    569      int dotsIndex = -1;
    570      for (unsigned i = numPrefixParts; i < pathParts.Size(); i++)
    571      {
    572        const UString &part = pathParts[i];
    573        if (part == L".." || part == L".")
    574          dotsIndex = i;
    575      }
    576 
    577      if (dotsIndex >= 0)
    578        if (dotsIndex == (int)pathParts.Size() - 1)
    579          numSkipParts = pathParts.Size();
    580        else
    581          numSkipParts = pathParts.Size() - 1;
    582    }
    583 
    584    for (unsigned i = 0; i < numSkipParts; i++)
    585    {
    586      {
    587        const UString &front = pathParts.Front();
    588        // WIN32 doesn't support wildcards in file names
    589        if (wildcardMatching)
    590          if (i >= numPrefixParts && DoesNameContainWildcard(front))
    591            break;
    592        prefix += front;
    593        prefix.Add_PathSepar();
    594      }
    595      pathParts.Delete(0);
    596    }
    597  }
    598 
    599  int index = FindPrefix(prefix);
    600  if (index < 0)
    601    index = Pairs.Add(CPair(prefix));
    602 
    603  if (pathMode != k_AbsPath)
    604  {
    605    if (pathParts.IsEmpty() || pathParts.Size() == 1 && pathParts[0].IsEmpty())
    606    {
    607      // we create universal item, if we skip all parts as prefix (like \ or L:\ )
    608      pathParts.Clear();
    609      pathParts.Add(UString("*"));
    610      forFile = true;
    611      wildcardMatching = true;
    612      recursive = false;
    613    }
    614  }
    615 
    616  CItem item;
    617  item.PathParts = pathParts;
    618  item.ForDir = true;
    619  item.ForFile = forFile;
    620  item.Recursive = recursive;
    621  item.WildcardMatching = wildcardMatching;
    622  Pairs[index].Head.AddItem(include, item, ignoreWildcardIndex);
    623 }
    624 
    625 /*
    626 bool CCensor::CheckPath(bool isAltStream, const UString &path, bool isFile) const
    627 {
    628  bool finded = false;
    629  FOR_VECTOR (i, Pairs)
    630  {
    631    bool include;
    632    if (Pairs[i].Head.CheckPath2(isAltStream, path, isFile, include))
    633    {
    634      if (!include)
    635        return false;
    636      finded = true;
    637    }
    638  }
    639  return finded;
    640 }
    641 */
    642 
    643 void CCensor::ExtendExclude()
    644 {
    645  unsigned i;
    646  for (i = 0; i < Pairs.Size(); i++)
    647    if (Pairs[i].Prefix.IsEmpty())
    648      break;
    649  if (i == Pairs.Size())
    650    return;
    651  unsigned index = i;
    652  for (i = 0; i < Pairs.Size(); i++)
    653    if (index != i)
    654      Pairs[i].Head.ExtendExclude(Pairs[index].Head);
    655 }
    656 
    657 void CCensor::AddPathsToCensor(ECensorPathMode censorPathMode)
    658 {
    659  FOR_VECTOR(i, CensorPaths)
    660  {
    661    const CCensorPath &cp = CensorPaths[i];
    662    AddItem(censorPathMode, cp.Include, cp.Path, cp.Recursive, cp.WildcardMatching);
    663  }
    664  CensorPaths.Clear();
    665 }
    666 
    667 void CCensor::AddPreItem(bool include, const UString &path, bool recursive, bool wildcardMatching)
    668 {
    669  CCensorPath &cp = CensorPaths.AddNew();
    670  cp.Path = path;
    671  cp.Include = include;
    672  cp.Recursive = recursive;
    673  cp.WildcardMatching = wildcardMatching;
    674 }
    675 
    676 }
	tor-browser The Tor Browser
	git clone https://git.dasho.dev/tor-browser.git
	Log \| Files \| Refs \| README \| LICENSE