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