1 // Common/Wildcard.cpp
2
3 #include "StdAfx.h"
4
5 #include "../../C/Types.h"
6
7 #include "Wildcard.h"
8
9 bool g_CaseSensitive =
10 #ifdef _WIN32
11 false;
12 #else
13 true;
14 #endif
15
16 static const wchar_t kAnyCharsChar = L'*';
17 static const wchar_t kAnyCharChar = L'?';
18
19 #ifdef _WIN32
20 static const wchar_t kDirDelimiter1 = L'\\';
21 #endif
22 static const wchar_t kDirDelimiter2 = L'/';
23
24 static const UString kWildCardCharSet = L"?*";
25
26 static const UString kIllegalWildCardFileNameChars=
27 L"\x1\x2\x3\x4\x5\x6\x7\x8\x9\xA\xB\xC\xD\xE\xF"
28 L"\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F"
29 L"\"/:<>\\|";
30
31
IsCharDirLimiter(wchar_t c)32 static inline bool IsCharDirLimiter(wchar_t c)
33 {
34 return (
35 #ifdef _WIN32
36 c == kDirDelimiter1 ||
37 #endif
38 c == kDirDelimiter2);
39 }
40
CompareFileNames(const UString & s1,const UString & s2)41 int CompareFileNames(const UString &s1, const UString &s2)
42 {
43 if (g_CaseSensitive)
44 return s1.Compare(s2);
45 return s1.CompareNoCase(s2);
46 }
47
48 // -----------------------------------------
49 // this function compares name with mask
50 // ? - any char
51 // * - any char or empty
52
EnhancedMaskTest(const wchar_t * mask,const wchar_t * name)53 static bool EnhancedMaskTest(const wchar_t *mask, const wchar_t *name)
54 {
55 for (;;)
56 {
57 wchar_t m = *mask;
58 wchar_t c = *name;
59 if (m == 0)
60 return (c == 0);
61 if (m == kAnyCharsChar)
62 {
63 if (EnhancedMaskTest(mask + 1, name))
64 return true;
65 if (c == 0)
66 return false;
67 }
68 else
69 {
70 if (m == kAnyCharChar)
71 {
72 if (c == 0)
73 return false;
74 }
75 else if (m != c)
76 if (g_CaseSensitive || MyCharUpper(m) != MyCharUpper(c))
77 return false;
78 mask++;
79 }
80 name++;
81 }
82 }
83
84 // --------------------------------------------------
85 // Splits path to strings
86
SplitPathToParts(const UString & path,UStringVector & pathParts)87 void SplitPathToParts(const UString &path, UStringVector &pathParts)
88 {
89 pathParts.Clear();
90 UString name;
91 int len = path.Length();
92 if (len == 0)
93 return;
94 for (int i = 0; i < len; i++)
95 {
96 wchar_t c = path[i];
97 if (IsCharDirLimiter(c))
98 {
99 pathParts.Add(name);
100 name.Empty();
101 }
102 else
103 name += c;
104 }
105 pathParts.Add(name);
106 }
107
SplitPathToParts(const UString & path,UString & dirPrefix,UString & name)108 void SplitPathToParts(const UString &path, UString &dirPrefix, UString &name)
109 {
110 int i;
111 for (i = path.Length() - 1; i >= 0; i--)
112 if (IsCharDirLimiter(path[i]))
113 break;
114 dirPrefix = path.Left(i + 1);
115 name = path.Mid(i + 1);
116 }
117
ExtractDirPrefixFromPath(const UString & path)118 UString ExtractDirPrefixFromPath(const UString &path)
119 {
120 int i;
121 for (i = path.Length() - 1; i >= 0; i--)
122 if (IsCharDirLimiter(path[i]))
123 break;
124 return path.Left(i + 1);
125 }
126
ExtractFileNameFromPath(const UString & path)127 UString ExtractFileNameFromPath(const UString &path)
128 {
129 int i;
130 for (i = path.Length() - 1; i >= 0; i--)
131 if (IsCharDirLimiter(path[i]))
132 break;
133 return path.Mid(i + 1);
134 }
135
136
CompareWildCardWithName(const UString & mask,const UString & name)137 bool CompareWildCardWithName(const UString &mask, const UString &name)
138 {
139 return EnhancedMaskTest(mask, name);
140 }
141
DoesNameContainWildCard(const UString & path)142 bool DoesNameContainWildCard(const UString &path)
143 {
144 return (path.FindOneOf(kWildCardCharSet) >= 0);
145 }
146
147
148 // ----------------------------------------------------------'
149 // NWildcard
150
151 namespace NWildcard {
152
153
154 /*
155 M = MaskParts.Size();
156 N = TestNameParts.Size();
157
158 File Dir
159 ForFile req M<=N [N-M, N) -
160 nonreq M=N [0, M) -
161
162 ForDir req M<N [0, M) ... [N-M-1, N-1) same as ForBoth-File
163 nonreq [0, M) same as ForBoth-File
164
165 ForBoth req m<=N [0, M) ... [N-M, N) same as ForBoth-File
166 nonreq [0, M) same as ForBoth-File
167
168 */
169
CheckPath(const UStringVector & pathParts,bool isFile) const170 bool CItem::CheckPath(const UStringVector &pathParts, bool isFile) const
171 {
172 if (!isFile && !ForDir)
173 return false;
174 int delta = (int)pathParts.Size() - (int)PathParts.Size();
175 if (delta < 0)
176 return false;
177 int start = 0;
178 int finish = 0;
179 if (isFile)
180 {
181 if (!ForDir && !Recursive && delta !=0)
182 return false;
183 if (!ForFile && delta == 0)
184 return false;
185 if (!ForDir && Recursive)
186 start = delta;
187 }
188 if (Recursive)
189 {
190 finish = delta;
191 if (isFile && !ForFile)
192 finish = delta - 1;
193 }
194 for (int d = start; d <= finish; d++)
195 {
196 int i;
197 for (i = 0; i < PathParts.Size(); i++)
198 if (!CompareWildCardWithName(PathParts[i], pathParts[i + d]))
199 break;
200 if (i == PathParts.Size())
201 return true;
202 }
203 return false;
204 }
205
FindSubNode(const UString & name) const206 int CCensorNode::FindSubNode(const UString &name) const
207 {
208 for (int i = 0; i < SubNodes.Size(); i++)
209 if (CompareFileNames(SubNodes[i].Name, name) == 0)
210 return i;
211 return -1;
212 }
213
AddItemSimple(bool include,CItem & item)214 void CCensorNode::AddItemSimple(bool include, CItem &item)
215 {
216 if (include)
217 IncludeItems.Add(item);
218 else
219 ExcludeItems.Add(item);
220 }
221
AddItem(bool include,CItem & item)222 void CCensorNode::AddItem(bool include, CItem &item)
223 {
224 if (item.PathParts.Size() <= 1)
225 {
226 AddItemSimple(include, item);
227 return;
228 }
229 const UString &front = item.PathParts.Front();
230 if (DoesNameContainWildCard(front))
231 {
232 AddItemSimple(include, item);
233 return;
234 }
235 int index = FindSubNode(front);
236 if (index < 0)
237 index = SubNodes.Add(CCensorNode(front, this));
238 item.PathParts.Delete(0);
239 SubNodes[index].AddItem(include, item);
240 }
241
AddItem(bool include,const UString & path,bool recursive,bool forFile,bool forDir)242 void CCensorNode::AddItem(bool include, const UString &path, bool recursive, bool forFile, bool forDir)
243 {
244 CItem item;
245 SplitPathToParts(path, item.PathParts);
246 item.Recursive = recursive;
247 item.ForFile = forFile;
248 item.ForDir = forDir;
249 AddItem(include, item);
250 }
251
NeedCheckSubDirs() const252 bool CCensorNode::NeedCheckSubDirs() const
253 {
254 for (int i = 0; i < IncludeItems.Size(); i++)
255 {
256 const CItem &item = IncludeItems[i];
257 if (item.Recursive || item.PathParts.Size() > 1)
258 return true;
259 }
260 return false;
261 }
262
AreThereIncludeItems() const263 bool CCensorNode::AreThereIncludeItems() const
264 {
265 if (IncludeItems.Size() > 0)
266 return true;
267 for (int i = 0; i < SubNodes.Size(); i++)
268 if (SubNodes[i].AreThereIncludeItems())
269 return true;
270 return false;
271 }
272
CheckPathCurrent(bool include,const UStringVector & pathParts,bool isFile) const273 bool CCensorNode::CheckPathCurrent(bool include, const UStringVector &pathParts, bool isFile) const
274 {
275 const CObjectVector<CItem> &items = include ? IncludeItems : ExcludeItems;
276 for (int i = 0; i < items.Size(); i++)
277 if (items[i].CheckPath(pathParts, isFile))
278 return true;
279 return false;
280 }
281
CheckPath(UStringVector & pathParts,bool isFile,bool & include) const282 bool CCensorNode::CheckPath(UStringVector &pathParts, bool isFile, bool &include) const
283 {
284 if (CheckPathCurrent(false, pathParts, isFile))
285 {
286 include = false;
287 return true;
288 }
289 include = true;
290 bool finded = CheckPathCurrent(true, pathParts, isFile);
291 if (pathParts.Size() == 1)
292 return finded;
293 int index = FindSubNode(pathParts.Front());
294 if (index >= 0)
295 {
296 UStringVector pathParts2 = pathParts;
297 pathParts2.Delete(0);
298 if (SubNodes[index].CheckPath(pathParts2, isFile, include))
299 return true;
300 }
301 return finded;
302 }
303
CheckPath(const UString & path,bool isFile,bool & include) const304 bool CCensorNode::CheckPath(const UString &path, bool isFile, bool &include) const
305 {
306 UStringVector pathParts;
307 SplitPathToParts(path, pathParts);
308 return CheckPath(pathParts, isFile, include);
309 }
310
CheckPath(const UString & path,bool isFile) const311 bool CCensorNode::CheckPath(const UString &path, bool isFile) const
312 {
313 bool include;
314 if (CheckPath(path, isFile, include))
315 return include;
316 return false;
317 }
318
CheckPathToRoot(bool include,UStringVector & pathParts,bool isFile) const319 bool CCensorNode::CheckPathToRoot(bool include, UStringVector &pathParts, bool isFile) const
320 {
321 if (CheckPathCurrent(include, pathParts, isFile))
322 return true;
323 if (Parent == 0)
324 return false;
325 pathParts.Insert(0, Name);
326 return Parent->CheckPathToRoot(include, pathParts, isFile);
327 }
328
329 /*
330 bool CCensorNode::CheckPathToRoot(bool include, const UString &path, bool isFile) const
331 {
332 UStringVector pathParts;
333 SplitPathToParts(path, pathParts);
334 return CheckPathToRoot(include, pathParts, isFile);
335 }
336 */
337
AddItem2(bool include,const UString & path,bool recursive)338 void CCensorNode::AddItem2(bool include, const UString &path, bool recursive)
339 {
340 if (path.IsEmpty())
341 return;
342 bool forFile = true;
343 bool forFolder = true;
344 UString path2 = path;
345 if (IsCharDirLimiter(path[path.Length() - 1]))
346 {
347 path2.Delete(path.Length() - 1);
348 forFile = false;
349 }
350 AddItem(include, path2, recursive, forFile, forFolder);
351 }
352
ExtendExclude(const CCensorNode & fromNodes)353 void CCensorNode::ExtendExclude(const CCensorNode &fromNodes)
354 {
355 ExcludeItems += fromNodes.ExcludeItems;
356 for (int i = 0; i < fromNodes.SubNodes.Size(); i++)
357 {
358 const CCensorNode &node = fromNodes.SubNodes[i];
359 int subNodeIndex = FindSubNode(node.Name);
360 if (subNodeIndex < 0)
361 subNodeIndex = SubNodes.Add(CCensorNode(node.Name, this));
362 SubNodes[subNodeIndex].ExtendExclude(node);
363 }
364 }
365
FindPrefix(const UString & prefix) const366 int CCensor::FindPrefix(const UString &prefix) const
367 {
368 for (int i = 0; i < Pairs.Size(); i++)
369 if (CompareFileNames(Pairs[i].Prefix, prefix) == 0)
370 return i;
371 return -1;
372 }
373
AddItem(bool include,const UString & path,bool recursive)374 void CCensor::AddItem(bool include, const UString &path, bool recursive)
375 {
376 UStringVector pathParts;
377 if (path.IsEmpty())
378 throw "Empty file path";
379 SplitPathToParts(path, pathParts);
380 bool forFile = true;
381 if (pathParts.Back().IsEmpty())
382 {
383 forFile = false;
384 pathParts.DeleteBack();
385 }
386 const UString &front = pathParts.Front();
387 bool isAbs = false;
388 if (front.IsEmpty())
389 isAbs = true;
390 else if (front.Length() == 2 && front[1] == L':')
391 isAbs = true;
392 else
393 {
394 for (int i = 0; i < pathParts.Size(); i++)
395 {
396 const UString &part = pathParts[i];
397 if (part == L".." || part == L".")
398 {
399 isAbs = true;
400 break;
401 }
402 }
403 }
404 int numAbsParts = 0;
405 if (isAbs)
406 if (pathParts.Size() > 1)
407 numAbsParts = pathParts.Size() - 1;
408 else
409 numAbsParts = 1;
410 UString prefix;
411 for (int i = 0; i < numAbsParts; i++)
412 {
413 const UString &front = pathParts.Front();
414 if (DoesNameContainWildCard(front))
415 break;
416 prefix += front;
417 prefix += WCHAR_PATH_SEPARATOR;
418 pathParts.Delete(0);
419 }
420 int index = FindPrefix(prefix);
421 if (index < 0)
422 index = Pairs.Add(CPair(prefix));
423
424 CItem item;
425 item.PathParts = pathParts;
426 item.ForDir = true;
427 item.ForFile = forFile;
428 item.Recursive = recursive;
429 Pairs[index].Head.AddItem(include, item);
430 }
431
CheckPath(const UString & path,bool isFile) const432 bool CCensor::CheckPath(const UString &path, bool isFile) const
433 {
434 bool finded = false;
435 for (int i = 0; i < Pairs.Size(); i++)
436 {
437 bool include;
438 if (Pairs[i].Head.CheckPath(path, isFile, include))
439 {
440 if (!include)
441 return false;
442 finded = true;
443 }
444 }
445 return finded;
446 }
447
ExtendExclude()448 void CCensor::ExtendExclude()
449 {
450 int i;
451 for (i = 0; i < Pairs.Size(); i++)
452 if (Pairs[i].Prefix.IsEmpty())
453 break;
454 if (i == Pairs.Size())
455 return;
456 int index = i;
457 for (i = 0; i < Pairs.Size(); i++)
458 if (index != i)
459 Pairs[i].Head.ExtendExclude(Pairs[index].Head);
460 }
461
462 }
463