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 MyStringCompare(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 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
EnhancedMaskTest(const wchar_t * mask,const wchar_t * name)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
SplitPathToParts(const UString & path,UStringVector & pathParts)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
SplitPathToParts_2(const UString & path,UString & dirPrefix,UString & name)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
SplitPathToParts_Smart(const UString & path,UString & dirPrefix,UString & name)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
ExtractFileNameFromPath(const UString & path)132 UString ExtractFileNameFromPath(const UString &path)
133 {
134 return UString(path.Ptr(path.ReverseFind_PathSepar() + 1));
135 }
136
137
DoesWildcardMatchName(const UString & mask,const UString & name)138 bool DoesWildcardMatchName(const UString &mask, const UString &name)
139 {
140 return EnhancedMaskTest(mask, name);
141 }
142
DoesNameContainWildcard(const UString & path)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
AreAllAllowed() const177 bool CItem::AreAllAllowed() const
178 {
179 return ForFile && ForDir && WildcardMatching && PathParts.Size() == 1 && PathParts.Front() == L"*";
180 }
181
CheckPath(const UStringVector & pathParts,bool isFile) const182 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
AreAllAllowed() const247 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
FindSubNode(const UString & name) const257 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
AddItemSimple(bool include,CItem & item)265 void CCensorNode::AddItemSimple(bool include, CItem &item)
266 {
267 if (include)
268 IncludeItems.Add(item);
269 else
270 ExcludeItems.Add(item);
271 }
272
AddItem(bool include,CItem & item,int ignoreWildcardIndex)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
AddItem(bool include,const UString & path,bool recursive,bool forFile,bool forDir,bool wildcardMatching)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
NeedCheckSubDirs() const313 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
AreThereIncludeItems() const324 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
CheckPathCurrent(bool include,const UStringVector & pathParts,bool isFile) const334 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
CheckPathVect(const UStringVector & pathParts,bool isFile,bool & include) const343 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
CheckPathToRoot(bool include,UStringVector & pathParts,bool isFile) const397 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
AddItem2(bool include,const UString & path,bool recursive,bool wildcardMatching)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
ExtendExclude(const CCensorNode & fromNodes)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
FindPrefix(const UString & prefix) const444 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
IsDriveColonName(const wchar_t * s)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
GetNumPrefixParts_if_DrivePath(UStringVector & pathParts)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
GetNumPrefixParts(const UStringVector & pathParts)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
AddItem(ECensorPathMode pathMode,bool include,const UString & path,bool recursive,bool wildcardMatching)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
ExtendExclude()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
AddPathsToCensor(ECensorPathMode censorPathMode)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
AddPreItem(bool include,const UString & path,bool recursive,bool wildcardMatching)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 }
677