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