comparison src/win32/7zip/7z/CPP/Common/Wildcard.cpp @ 1:f9f4f1b99eed

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