xref: /third_party/lzma/CPP/Common/Wildcard.cpp (revision 370b324c) 
1// Common/Wildcard.cpp
2
3#include "StdAfx.h"
4
5#include "Wildcard.h"
6
7extern
8bool g_CaseSensitive;
9bool g_CaseSensitive =
10  #ifdef _WIN32
11    false;
12  #elif defined (__APPLE__)
13    #ifdef TARGET_OS_IPHONE
14      true;
15    #else
16      false;
17    #endif
18  #else
19    true;
20  #endif
21
22
23bool IsPath1PrefixedByPath2(const wchar_t *s1, const wchar_t *s2)
24{
25  if (g_CaseSensitive)
26    return IsString1PrefixedByString2(s1, s2);
27  return IsString1PrefixedByString2_NoCase(s1, s2);
28}
29
30// #include <stdio.h>
31
32/*
33static int MyStringCompare_PathLinux(const wchar_t *s1, const wchar_t *s2) throw()
34{
35  for (;;)
36  {
37    wchar_t c1 = *s1++;
38    wchar_t c2 = *s2++;
39    if (c1 != c2)
40    {
41      if (c1 == 0) return -1;
42      if (c2 == 0) return 1;
43      if (c1 == '/') c1 = 0;
44      if (c2 == '/') c2 = 0;
45      if (c1 < c2) return -1;
46      if (c1 > c2) return 1;
47      continue;
48    }
49    if (c1 == 0) return 0;
50  }
51}
52*/
53
54static int MyStringCompare_Path(const wchar_t *s1, const wchar_t *s2) throw()
55{
56  for (;;)
57  {
58    wchar_t c1 = *s1++;
59    wchar_t c2 = *s2++;
60    if (c1 != c2)
61    {
62      if (c1 == 0) return -1;
63      if (c2 == 0) return 1;
64      if (IS_PATH_SEPAR(c1)) c1 = 0;
65      if (IS_PATH_SEPAR(c2)) c2 = 0;
66      if (c1 < c2) return -1;
67      if (c1 > c2) return 1;
68      continue;
69    }
70    if (c1 == 0) return 0;
71  }
72}
73
74static int MyStringCompareNoCase_Path(const wchar_t *s1, const wchar_t *s2) throw()
75{
76  for (;;)
77  {
78    wchar_t c1 = *s1++;
79    wchar_t c2 = *s2++;
80    if (c1 != c2)
81    {
82      if (c1 == 0) return -1;
83      if (c2 == 0) return 1;
84      if (IS_PATH_SEPAR(c1)) c1 = 0;
85      if (IS_PATH_SEPAR(c2)) c2 = 0;
86      c1 = MyCharUpper(c1);
87      c2 = MyCharUpper(c2);
88      if (c1 < c2) return -1;
89      if (c1 > c2) return 1;
90      continue;
91    }
92    if (c1 == 0) return 0;
93  }
94}
95
96int CompareFileNames(const wchar_t *s1, const wchar_t *s2) STRING_UNICODE_THROW
97{
98  /*
99  printf("\nCompareFileNames");
100  printf("\n S1: %ls", s1);
101  printf("\n S2: %ls", s2);
102  printf("\n");
103  */
104  // 21.07 : we parse PATH_SEPARATOR so: 0 < PATH_SEPARATOR < 1
105  if (g_CaseSensitive)
106    return MyStringCompare_Path(s1, s2);
107  return MyStringCompareNoCase_Path(s1, s2);
108}
109
110#ifndef USE_UNICODE_FSTRING
111int CompareFileNames(const char *s1, const char *s2)
112{
113  const UString u1 = fs2us(s1);
114  const UString u2 = fs2us(s2);
115  return CompareFileNames(u1, u2);
116}
117#endif
118
119// -----------------------------------------
120// this function compares name with mask
121// ? - any char
122// * - any char or empty
123
124static bool EnhancedMaskTest(const wchar_t *mask, const wchar_t *name)
125{
126  for (;;)
127  {
128    const wchar_t m = *mask;
129    const wchar_t c = *name;
130    if (m == 0)
131      return (c == 0);
132    if (m == '*')
133    {
134      if (EnhancedMaskTest(mask + 1, name))
135        return true;
136      if (c == 0)
137        return false;
138    }
139    else
140    {
141      if (m == '?')
142      {
143        if (c == 0)
144          return false;
145      }
146      else if (m != c)
147        if (g_CaseSensitive || MyCharUpper(m) != MyCharUpper(c))
148          return false;
149      mask++;
150    }
151    name++;
152  }
153}
154
155// --------------------------------------------------
156// Splits path to strings
157
158void SplitPathToParts(const UString &path, UStringVector &pathParts)
159{
160  pathParts.Clear();
161  unsigned len = path.Len();
162  if (len == 0)
163    return;
164  UString name;
165  unsigned prev = 0;
166  for (unsigned i = 0; i < len; i++)
167    if (IsPathSepar(path[i]))
168    {
169      name.SetFrom(path.Ptr(prev), i - prev);
170      pathParts.Add(name);
171      prev = i + 1;
172    }
173  name.SetFrom(path.Ptr(prev), len - prev);
174  pathParts.Add(name);
175}
176
177void SplitPathToParts_2(const UString &path, UString &dirPrefix, UString &name)
178{
179  const wchar_t *start = path;
180  const wchar_t *p = start + path.Len();
181  for (; p != start; p--)
182    if (IsPathSepar(*(p - 1)))
183      break;
184  dirPrefix.SetFrom(path, (unsigned)(p - start));
185  name = p;
186}
187
188void SplitPathToParts_Smart(const UString &path, UString &dirPrefix, UString &name)
189{
190  const wchar_t *start = path;
191  const wchar_t *p = start + path.Len();
192  if (p != start)
193  {
194    if (IsPathSepar(*(p - 1)))
195      p--;
196    for (; p != start; p--)
197      if (IsPathSepar(*(p - 1)))
198        break;
199  }
200  dirPrefix.SetFrom(path, (unsigned)(p - start));
201  name = p;
202}
203
204/*
205UString ExtractDirPrefixFromPath(const UString &path)
206{
207  return path.Left(path.ReverseFind_PathSepar() + 1));
208}
209*/
210
211UString ExtractFileNameFromPath(const UString &path)
212{
213  return UString(path.Ptr((unsigned)(path.ReverseFind_PathSepar() + 1)));
214}
215
216
217bool DoesWildcardMatchName(const UString &mask, const UString &name)
218{
219  return EnhancedMaskTest(mask, name);
220}
221
222bool DoesNameContainWildcard(const UString &path)
223{
224  for (unsigned i = 0; i < path.Len(); i++)
225  {
226    wchar_t c = path[i];
227    if (c == '*' || c == '?')
228      return true;
229  }
230  return false;
231}
232
233
234// ----------------------------------------------------------'
235// NWildcard
236
237namespace NWildcard {
238
239/*
240
241M = MaskParts.Size();
242N = TestNameParts.Size();
243
244                           File                          Dir
245ForFile     rec   M<=N  [N-M, N)                          -
246!ForDir  nonrec   M=N   [0, M)                            -
247
248ForDir      rec   M<N   [0, M) ... [N-M-1, N-1)  same as ForBoth-File
249!ForFile nonrec         [0, M)                   same as ForBoth-File
250
251ForFile     rec   m<=N  [0, M) ... [N-M, N)      same as ForBoth-File
252ForDir   nonrec         [0, M)                   same as ForBoth-File
253
254*/
255
256bool CItem::AreAllAllowed() const
257{
258  return ForFile && ForDir && WildcardMatching && PathParts.Size() == 1 && PathParts.Front() == L"*";
259}
260
261bool CItem::CheckPath(const UStringVector &pathParts, bool isFile) const
262{
263  if (!isFile && !ForDir)
264    return false;
265
266  /*
267  if (PathParts.IsEmpty())
268  {
269    // PathParts.IsEmpty() means all items (universal wildcard)
270    if (!isFile)
271      return true;
272    if (pathParts.Size() <= 1)
273      return ForFile;
274    return (ForDir || Recursive && ForFile);
275  }
276  */
277
278  int delta = (int)pathParts.Size() - (int)PathParts.Size();
279  if (delta < 0)
280    return false;
281  int start = 0;
282  int finish = 0;
283
284  if (isFile)
285  {
286    if (!ForDir)
287    {
288      if (Recursive)
289        start = delta;
290      else if (delta !=0)
291        return false;
292    }
293    if (!ForFile && delta == 0)
294      return false;
295  }
296
297  if (Recursive)
298  {
299    finish = delta;
300    if (isFile && !ForFile)
301      finish = delta - 1;
302  }
303
304  for (int d = start; d <= finish; d++)
305  {
306    unsigned i;
307    for (i = 0; i < PathParts.Size(); i++)
308    {
309      if (WildcardMatching)
310      {
311        if (!DoesWildcardMatchName(PathParts[i], pathParts[i + (unsigned)d]))
312          break;
313      }
314      else
315      {
316        if (CompareFileNames(PathParts[i], pathParts[i + (unsigned)d]) != 0)
317          break;
318      }
319    }
320    if (i == PathParts.Size())
321      return true;
322  }
323  return false;
324}
325
326bool CCensorNode::AreAllAllowed() const
327{
328  if (!Name.IsEmpty() ||
329      !SubNodes.IsEmpty() ||
330      !ExcludeItems.IsEmpty() ||
331      IncludeItems.Size() != 1)
332    return false;
333  return IncludeItems.Front().AreAllAllowed();
334}
335
336int CCensorNode::FindSubNode(const UString &name) const
337{
338  FOR_VECTOR (i, SubNodes)
339    if (CompareFileNames(SubNodes[i].Name, name) == 0)
340      return (int)i;
341  return -1;
342}
343
344void CCensorNode::AddItemSimple(bool include, CItem &item)
345{
346  CObjectVector<CItem> &items = include ? IncludeItems : ExcludeItems;
347  items.Add(item);
348}
349
350void CCensorNode::AddItem(bool include, CItem &item, int ignoreWildcardIndex)
351{
352  if (item.PathParts.Size() <= 1)
353  {
354    if (item.PathParts.Size() != 0 && item.WildcardMatching)
355    {
356      if (!DoesNameContainWildcard(item.PathParts.Front()))
357        item.WildcardMatching = false;
358    }
359    AddItemSimple(include, item);
360    return;
361  }
362
363  const UString &front = item.PathParts.Front();
364
365  // WIN32 doesn't support wildcards in file names
366  if (item.WildcardMatching
367      && ignoreWildcardIndex != 0
368      && DoesNameContainWildcard(front))
369  {
370    AddItemSimple(include, item);
371    return;
372  }
373  CCensorNode &subNode = Find_SubNode_Or_Add_New(front);
374  item.PathParts.Delete(0);
375  subNode.AddItem(include, item, ignoreWildcardIndex - 1);
376}
377
378/*
379void CCensorNode::AddItem(bool include, const UString &path, const CCensorPathProps &props)
380{
381  CItem item;
382  SplitPathToParts(path, item.PathParts);
383  item.Recursive = props.Recursive;
384  item.ForFile = props.ForFile;
385  item.ForDir = props.ForDir;
386  item.WildcardMatching = props.WildcardMatching;
387  AddItem(include, item);
388}
389*/
390
391bool CCensorNode::NeedCheckSubDirs() const
392{
393  FOR_VECTOR (i, IncludeItems)
394  {
395    const CItem &item = IncludeItems[i];
396    if (item.Recursive || item.PathParts.Size() > 1)
397      return true;
398  }
399  return false;
400}
401
402bool CCensorNode::AreThereIncludeItems() const
403{
404  if (IncludeItems.Size() > 0)
405    return true;
406  FOR_VECTOR (i, SubNodes)
407    if (SubNodes[i].AreThereIncludeItems())
408      return true;
409  return false;
410}
411
412bool CCensorNode::CheckPathCurrent(bool include, const UStringVector &pathParts, bool isFile) const
413{
414  const CObjectVector<CItem> &items = include ? IncludeItems : ExcludeItems;
415  FOR_VECTOR (i, items)
416    if (items[i].CheckPath(pathParts, isFile))
417      return true;
418  return false;
419}
420
421bool CCensorNode::CheckPathVect(const UStringVector &pathParts, bool isFile, bool &include) const
422{
423  if (CheckPathCurrent(false, pathParts, isFile))
424  {
425    include = false;
426    return true;
427  }
428  if (pathParts.Size() > 1)
429  {
430    int index = FindSubNode(pathParts.Front());
431    if (index >= 0)
432    {
433      UStringVector pathParts2 = pathParts;
434      pathParts2.Delete(0);
435      if (SubNodes[(unsigned)index].CheckPathVect(pathParts2, isFile, include))
436        return true;
437    }
438  }
439  bool finded = CheckPathCurrent(true, pathParts, isFile);
440  include = finded; // if (!finded), then (true) is allowed also
441  return finded;
442}
443
444/*
445bool CCensorNode::CheckPath2(bool isAltStream, const UString &path, bool isFile, bool &include) const
446{
447  UStringVector pathParts;
448  SplitPathToParts(path, pathParts);
449  if (CheckPathVect(pathParts, isFile, include))
450  {
451    if (!include || !isAltStream)
452      return true;
453  }
454  if (isAltStream && !pathParts.IsEmpty())
455  {
456    UString &back = pathParts.Back();
457    int pos = back.Find(L':');
458    if (pos > 0)
459    {
460      back.DeleteFrom(pos);
461      return CheckPathVect(pathParts, isFile, include);
462    }
463  }
464  return false;
465}
466
467bool CCensorNode::CheckPath(bool isAltStream, const UString &path, bool isFile) const
468{
469  bool include;
470  if (CheckPath2(isAltStream, path, isFile, include))
471    return include;
472  return false;
473}
474*/
475
476bool CCensorNode::CheckPathToRoot_Change(bool include, UStringVector &pathParts, bool isFile) const
477{
478  if (CheckPathCurrent(include, pathParts, isFile))
479    return true;
480  if (!Parent)
481    return false;
482  pathParts.Insert(0, Name);
483  return Parent->CheckPathToRoot_Change(include, pathParts, isFile);
484}
485
486bool CCensorNode::CheckPathToRoot(bool include, const UStringVector &pathParts, bool isFile) const
487{
488  if (CheckPathCurrent(include, pathParts, isFile))
489    return true;
490  if (!Parent)
491    return false;
492  UStringVector pathParts2;
493  pathParts2.Add(Name);
494  pathParts2 += pathParts;
495  return Parent->CheckPathToRoot_Change(include, pathParts2, isFile);
496}
497
498/*
499bool CCensorNode::CheckPathToRoot(bool include, const UString &path, bool isFile) const
500{
501  UStringVector pathParts;
502  SplitPathToParts(path, pathParts);
503  return CheckPathToRoot(include, pathParts, isFile);
504}
505*/
506
507void CCensorNode::ExtendExclude(const CCensorNode &fromNodes)
508{
509  ExcludeItems += fromNodes.ExcludeItems;
510  FOR_VECTOR (i, fromNodes.SubNodes)
511  {
512    const CCensorNode &node = fromNodes.SubNodes[i];
513    Find_SubNode_Or_Add_New(node.Name).ExtendExclude(node);
514  }
515}
516
517int CCensor::FindPairForPrefix(const UString &prefix) const
518{
519  FOR_VECTOR (i, Pairs)
520    if (CompareFileNames(Pairs[i].Prefix, prefix) == 0)
521      return (int)i;
522  return -1;
523}
524
525#ifdef _WIN32
526
527bool IsDriveColonName(const wchar_t *s)
528{
529  unsigned c = s[0];
530  c |= 0x20;
531  c -= 'a';
532  return c <= (unsigned)('z' - 'a') && s[1] == ':' && s[2] == 0;
533}
534
535unsigned GetNumPrefixParts_if_DrivePath(UStringVector &pathParts)
536{
537  if (pathParts.IsEmpty())
538    return 0;
539
540  unsigned testIndex = 0;
541  if (pathParts[0].IsEmpty())
542  {
543    if (pathParts.Size() < 4
544        || !pathParts[1].IsEmpty()
545        || pathParts[2] != L"?")
546      return 0;
547    testIndex = 3;
548  }
549  if (NWildcard::IsDriveColonName(pathParts[testIndex]))
550    return testIndex + 1;
551  return 0;
552}
553
554#endif
555
556static unsigned GetNumPrefixParts(const UStringVector &pathParts)
557{
558  if (pathParts.IsEmpty())
559    return 0;
560
561  /* empty last part could be removed already from (pathParts),
562     if there was tail path separator (slash) in original full path string. */
563
564  #ifdef _WIN32
565
566  if (IsDriveColonName(pathParts[0]))
567    return 1;
568  if (!pathParts[0].IsEmpty())
569    return 0;
570
571  if (pathParts.Size() == 1)
572    return 1;
573  if (!pathParts[1].IsEmpty())
574    return 1;
575  if (pathParts.Size() == 2)
576    return 2;
577  if (pathParts[2] == L".")
578    return 3;
579
580  unsigned networkParts = 2;
581  if (pathParts[2] == L"?")
582  {
583    if (pathParts.Size() == 3)
584      return 3;
585    if (IsDriveColonName(pathParts[3]))
586      return 4;
587    if (!pathParts[3].IsEqualTo_Ascii_NoCase("UNC"))
588      return 3;
589    networkParts = 4;
590  }
591
592  networkParts +=
593      // 2; // server/share
594      1; // server
595  if (pathParts.Size() <= networkParts)
596    return pathParts.Size();
597  return networkParts;
598
599  #else
600
601  return pathParts[0].IsEmpty() ? 1 : 0;
602
603  #endif
604}
605
606void CCensor::AddItem(ECensorPathMode pathMode, bool include, const UString &path,
607    const CCensorPathProps &props)
608{
609  if (path.IsEmpty())
610    throw "Empty file path";
611
612  UStringVector pathParts;
613  SplitPathToParts(path, pathParts);
614
615  CCensorPathProps props2 = props;
616
617  bool forFile = true;
618  bool forDir = true;
619  const UString &back = pathParts.Back();
620  if (back.IsEmpty())
621  {
622    // we have tail path separator. So it's directory.
623    // we delete tail path separator here even for "\" and "c:\"
624    forFile = false;
625    pathParts.DeleteBack();
626  }
627  else
628  {
629    if (props.MarkMode == kMark_StrictFile
630        || (props.MarkMode == kMark_StrictFile_IfWildcard
631            && DoesNameContainWildcard(back)))
632      forDir = false;
633  }
634
635
636  UString prefix;
637
638  int ignoreWildcardIndex = -1;
639
640  // #ifdef _WIN32
641  // we ignore "?" wildcard in "\\?\" prefix.
642  if (pathParts.Size() >= 3
643      && pathParts[0].IsEmpty()
644      && pathParts[1].IsEmpty()
645      && pathParts[2] == L"?")
646    ignoreWildcardIndex = 2;
647  // #endif
648
649  if (pathMode != k_AbsPath)
650  {
651    // detection of the number of Skip Parts for prefix
652    ignoreWildcardIndex = -1;
653
654    const unsigned numPrefixParts = GetNumPrefixParts(pathParts);
655    unsigned numSkipParts = numPrefixParts;
656
657    if (pathMode != k_FullPath)
658    {
659      // if absolute path, then all parts before last part will be in prefix
660      if (numPrefixParts != 0 && pathParts.Size() > numPrefixParts)
661        numSkipParts = pathParts.Size() - 1;
662    }
663    {
664      int dotsIndex = -1;
665      for (unsigned i = numPrefixParts; i < pathParts.Size(); i++)
666      {
667        const UString &part = pathParts[i];
668        if (part == L".." || part == L".")
669          dotsIndex = (int)i;
670      }
671
672      if (dotsIndex >= 0)
673      {
674        if (dotsIndex == (int)pathParts.Size() - 1)
675          numSkipParts = pathParts.Size();
676        else
677          numSkipParts = pathParts.Size() - 1;
678      }
679    }
680
681    // we split (pathParts) to (prefix) and (pathParts).
682    for (unsigned i = 0; i < numSkipParts; i++)
683    {
684      {
685        const UString &front = pathParts.Front();
686        // WIN32 doesn't support wildcards in file names
687        if (props.WildcardMatching)
688          if (i >= numPrefixParts && DoesNameContainWildcard(front))
689            break;
690        prefix += front;
691        prefix.Add_PathSepar();
692      }
693      pathParts.Delete(0);
694    }
695  }
696
697  int index = FindPairForPrefix(prefix);
698  if (index < 0)
699  {
700    index = (int)Pairs.Size();
701    Pairs.AddNew().Prefix = prefix;
702  }
703
704  if (pathMode != k_AbsPath)
705  {
706    if (pathParts.IsEmpty() || (pathParts.Size() == 1 && pathParts[0].IsEmpty()))
707    {
708      // we create universal item, if we skip all parts as prefix (like \ or L:\ )
709      pathParts.Clear();
710      pathParts.Add(UString("*"));
711      forFile = true;
712      forDir = true;
713      props2.WildcardMatching = true;
714      props2.Recursive = false;
715    }
716  }
717
718  /*
719  // not possible now
720  if (!forDir && !forFile)
721  {
722    UString s ("file path was blocked for files and directories: ");
723    s += path;
724    throw s;
725    // return; // for debug : ignore item (don't create Item)
726  }
727  */
728
729  CItem item;
730  item.PathParts = pathParts;
731  item.ForDir = forDir;
732  item.ForFile = forFile;
733  item.Recursive = props2.Recursive;
734  item.WildcardMatching = props2.WildcardMatching;
735  Pairs[(unsigned)index].Head.AddItem(include, item, ignoreWildcardIndex);
736}
737
738/*
739bool CCensor::CheckPath(bool isAltStream, const UString &path, bool isFile) const
740{
741  bool finded = false;
742  FOR_VECTOR (i, Pairs)
743  {
744    bool include;
745    if (Pairs[i].Head.CheckPath2(isAltStream, path, isFile, include))
746    {
747      if (!include)
748        return false;
749      finded = true;
750    }
751  }
752  return finded;
753}
754*/
755
756void CCensor::ExtendExclude()
757{
758  unsigned i;
759  for (i = 0; i < Pairs.Size(); i++)
760    if (Pairs[i].Prefix.IsEmpty())
761      break;
762  if (i == Pairs.Size())
763    return;
764  unsigned index = i;
765  for (i = 0; i < Pairs.Size(); i++)
766    if (index != i)
767      Pairs[i].Head.ExtendExclude(Pairs[index].Head);
768}
769
770void CCensor::AddPathsToCensor(ECensorPathMode censorPathMode)
771{
772  FOR_VECTOR(i, CensorPaths)
773  {
774    const CCensorPath &cp = CensorPaths[i];
775    AddItem(censorPathMode, cp.Include, cp.Path, cp.Props);
776  }
777  CensorPaths.Clear();
778}
779
780void CCensor::AddPreItem(bool include, const UString &path, const CCensorPathProps &props)
781{
782  CCensorPath &cp = CensorPaths.AddNew();
783  cp.Path = path;
784  cp.Include = include;
785  cp.Props = props;
786}
787
788}
789