1// Common/Wildcard.cpp
2
3#include "StdAfx.h"
4
5#include "../../C/Types.h"
6
7#include "Wildcard.h"
8
9bool g_CaseSensitive =
10  #ifdef _WIN32
11    false;
12  #else
13    true;
14  #endif
15
16static const wchar_t kAnyCharsChar = L'*';
17static const wchar_t kAnyCharChar = L'?';
18
19#ifdef _WIN32
20static const wchar_t kDirDelimiter1 = L'\\';
21#endif
22static const wchar_t kDirDelimiter2 = L'/';
23
24static const UString kWildCardCharSet = L"?*";
25
26static 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
32static inline bool IsCharDirLimiter(wchar_t c)
33{
34  return (
35    #ifdef _WIN32
36    c == kDirDelimiter1 ||
37    #endif
38    c == kDirDelimiter2);
39}
40
41int 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
53static 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
87void 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
108void 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
118UString 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
127UString 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
137bool CompareWildCardWithName(const UString &mask, const UString &name)
138{
139  return EnhancedMaskTest(mask, name);
140}
141
142bool DoesNameContainWildCard(const UString &path)
143{
144  return (path.FindOneOf(kWildCardCharSet) >= 0);
145}
146
147
148// ----------------------------------------------------------'
149// NWildcard
150
151namespace NWildcard {
152
153
154/*
155M = MaskParts.Size();
156N = TestNameParts.Size();
157
158                           File                          Dir
159ForFile     req   M<=N  [N-M, N)                          -
160         nonreq   M=N   [0, M)                            -
161
162ForDir      req   M<N   [0, M) ... [N-M-1, N-1)  same as ForBoth-File
163         nonreq         [0, M)                   same as ForBoth-File
164
165ForBoth     req   m<=N  [0, M) ... [N-M, N)      same as ForBoth-File
166         nonreq         [0, M)                   same as ForBoth-File
167
168*/
169
170bool 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
206int 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
214void CCensorNode::AddItemSimple(bool include, CItem &item)
215{
216  if (include)
217    IncludeItems.Add(item);
218  else
219    ExcludeItems.Add(item);
220}
221
222void 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
242void 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
252bool 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
263bool 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
273bool 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
282bool 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
304bool 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
311bool 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
319bool 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/*
330bool 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
338void 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
353void 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
366int 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
374void 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
432bool 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
448void 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