rlm@1: // Common/Wildcard.cpp
rlm@1: 
rlm@1: #include "StdAfx.h"
rlm@1: 
rlm@1: #include "Wildcard.h"
rlm@1: 
rlm@1: bool g_CaseSensitive =
rlm@1:   #ifdef _WIN32
rlm@1:     false;
rlm@1:   #else
rlm@1:     true;
rlm@1:   #endif
rlm@1: 
rlm@1: static const wchar_t kAnyCharsChar = L'*';
rlm@1: static const wchar_t kAnyCharChar = L'?';
rlm@1: 
rlm@1: #ifdef _WIN32
rlm@1: static const wchar_t kDirDelimiter1 = L'\\';
rlm@1: #endif
rlm@1: static const wchar_t kDirDelimiter2 = L'/';
rlm@1: 
rlm@1: static const UString kWildCardCharSet = L"?*";
rlm@1: 
rlm@1: static const UString kIllegalWildCardFileNameChars=
rlm@1:   L"\x1\x2\x3\x4\x5\x6\x7\x8\x9\xA\xB\xC\xD\xE\xF"
rlm@1:   L"\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F"
rlm@1:   L"\"/:<>\\|";
rlm@1: 
rlm@1: 
rlm@1: static inline bool IsCharDirLimiter(wchar_t c)
rlm@1: {
rlm@1:   return (
rlm@1:     #ifdef _WIN32
rlm@1:     c == kDirDelimiter1 ||
rlm@1:     #endif
rlm@1:     c == kDirDelimiter2);
rlm@1: }
rlm@1: 
rlm@1: int CompareFileNames(const UString &s1, const UString &s2)
rlm@1: {
rlm@1:   if (g_CaseSensitive)
rlm@1:     return s1.Compare(s2);
rlm@1:   return s1.CompareNoCase(s2);
rlm@1: }
rlm@1: 
rlm@1: // -----------------------------------------
rlm@1: // this function compares name with mask
rlm@1: // ? - any char
rlm@1: // * - any char or empty
rlm@1: 
rlm@1: static bool EnhancedMaskTest(const wchar_t *mask, const wchar_t *name)
rlm@1: {
rlm@1:   for (;;)
rlm@1:   {
rlm@1:     wchar_t m = *mask;
rlm@1:     wchar_t c = *name;
rlm@1:     if (m == 0)
rlm@1:       return (c == 0);
rlm@1:     if (m == kAnyCharsChar)
rlm@1:     {
rlm@1:       if (EnhancedMaskTest(mask + 1, name))
rlm@1:         return true;
rlm@1:       if (c == 0)
rlm@1:         return false;
rlm@1:     }
rlm@1:     else
rlm@1:     {
rlm@1:       if (m == kAnyCharChar)
rlm@1:       {
rlm@1:         if (c == 0)
rlm@1:           return false;
rlm@1:       }
rlm@1:       else if (m != c)
rlm@1:         if (g_CaseSensitive || MyCharUpper(m) != MyCharUpper(c))
rlm@1:           return false;
rlm@1:       mask++;
rlm@1:     }
rlm@1:     name++;
rlm@1:   }
rlm@1: }
rlm@1: 
rlm@1: // --------------------------------------------------
rlm@1: // Splits path to strings
rlm@1: 
rlm@1: void SplitPathToParts(const UString &path, UStringVector &pathParts)
rlm@1: {
rlm@1:   pathParts.Clear();
rlm@1:   UString name;
rlm@1:   int len = path.Length();
rlm@1:   if (len == 0)
rlm@1:     return;
rlm@1:   for (int i = 0; i < len; i++)
rlm@1:   {
rlm@1:     wchar_t c = path[i];
rlm@1:     if (IsCharDirLimiter(c))
rlm@1:     {
rlm@1:       pathParts.Add(name);
rlm@1:       name.Empty();
rlm@1:     }
rlm@1:     else
rlm@1:       name += c;
rlm@1:   }
rlm@1:   pathParts.Add(name);
rlm@1: }
rlm@1: 
rlm@1: void SplitPathToParts(const UString &path, UString &dirPrefix, UString &name)
rlm@1: {
rlm@1:   int i;
rlm@1:   for (i = path.Length() - 1; i >= 0; i--)
rlm@1:     if (IsCharDirLimiter(path[i]))
rlm@1:       break;
rlm@1:   dirPrefix = path.Left(i + 1);
rlm@1:   name = path.Mid(i + 1);
rlm@1: }
rlm@1: 
rlm@1: UString ExtractDirPrefixFromPath(const UString &path)
rlm@1: {
rlm@1:   int i;
rlm@1:   for (i = path.Length() - 1; i >= 0; i--)
rlm@1:     if (IsCharDirLimiter(path[i]))
rlm@1:       break;
rlm@1:   return path.Left(i + 1);
rlm@1: }
rlm@1: 
rlm@1: UString ExtractFileNameFromPath(const UString &path)
rlm@1: {
rlm@1:   int i;
rlm@1:   for (i = path.Length() - 1; i >= 0; i--)
rlm@1:     if (IsCharDirLimiter(path[i]))
rlm@1:       break;
rlm@1:   return path.Mid(i + 1);
rlm@1: }
rlm@1: 
rlm@1: 
rlm@1: bool CompareWildCardWithName(const UString &mask, const UString &name)
rlm@1: {
rlm@1:   return EnhancedMaskTest(mask, name);
rlm@1: }
rlm@1: 
rlm@1: bool DoesNameContainWildCard(const UString &path)
rlm@1: {
rlm@1:   return (path.FindOneOf(kWildCardCharSet) >= 0);
rlm@1: }
rlm@1: 
rlm@1: 
rlm@1: // ----------------------------------------------------------'
rlm@1: // NWildcard
rlm@1: 
rlm@1: namespace NWildcard {
rlm@1: 
rlm@1: 
rlm@1: /*
rlm@1: M = MaskParts.Size();
rlm@1: N = TestNameParts.Size();
rlm@1: 
rlm@1:                            File                          Dir
rlm@1: ForFile     req   M<=N  [N-M, N)                          -
rlm@1:          nonreq   M=N   [0, M)                            -
rlm@1:  
rlm@1: ForDir      req   M<N   [0, M) ... [N-M-1, N-1)  same as ForBoth-File
rlm@1:          nonreq         [0, M)                   same as ForBoth-File
rlm@1: 
rlm@1: ForBoth     req   m<=N  [0, M) ... [N-M, N)      same as ForBoth-File
rlm@1:          nonreq         [0, M)                   same as ForBoth-File
rlm@1: 
rlm@1: */
rlm@1: 
rlm@1: bool CItem::CheckPath(const UStringVector &pathParts, bool isFile) const
rlm@1: {
rlm@1:   if (!isFile && !ForDir)
rlm@1:     return false;
rlm@1:   int delta = (int)pathParts.Size() - (int)PathParts.Size();
rlm@1:   if (delta < 0)
rlm@1:     return false;
rlm@1:   int start = 0;
rlm@1:   int finish = 0;
rlm@1:   if (isFile)
rlm@1:   {
rlm@1:     if (!ForDir && !Recursive && delta !=0)
rlm@1:       return false;
rlm@1:     if (!ForFile && delta == 0)
rlm@1:       return false;
rlm@1:     if (!ForDir && Recursive)
rlm@1:       start = delta;
rlm@1:   }
rlm@1:   if (Recursive)
rlm@1:   {
rlm@1:     finish = delta;
rlm@1:     if (isFile && !ForFile)
rlm@1:       finish = delta - 1;
rlm@1:   }
rlm@1:   for (int d = start; d <= finish; d++)
rlm@1:   {
rlm@1:     int i;
rlm@1:     for (i = 0; i < PathParts.Size(); i++)
rlm@1:       if (!CompareWildCardWithName(PathParts[i], pathParts[i + d]))
rlm@1:         break;
rlm@1:     if (i == PathParts.Size())
rlm@1:       return true;
rlm@1:   }
rlm@1:   return false;
rlm@1: }
rlm@1: 
rlm@1: int CCensorNode::FindSubNode(const UString &name) const
rlm@1: {
rlm@1:   for (int i = 0; i < SubNodes.Size(); i++)
rlm@1:     if (CompareFileNames(SubNodes[i].Name, name) == 0)
rlm@1:       return i;
rlm@1:   return -1;
rlm@1: }
rlm@1: 
rlm@1: void CCensorNode::AddItemSimple(bool include, CItem &item)
rlm@1: {
rlm@1:   if (include)
rlm@1:     IncludeItems.Add(item);
rlm@1:   else
rlm@1:     ExcludeItems.Add(item);
rlm@1: }
rlm@1: 
rlm@1: void CCensorNode::AddItem(bool include, CItem &item)
rlm@1: {
rlm@1:   if (item.PathParts.Size() <= 1)
rlm@1:   {
rlm@1:     AddItemSimple(include, item);
rlm@1:     return;
rlm@1:   }
rlm@1:   const UString &front = item.PathParts.Front();
rlm@1:   if (DoesNameContainWildCard(front))
rlm@1:   {
rlm@1:     AddItemSimple(include, item);
rlm@1:     return;
rlm@1:   }
rlm@1:   int index = FindSubNode(front);
rlm@1:   if (index < 0)
rlm@1:     index = SubNodes.Add(CCensorNode(front, this));
rlm@1:   item.PathParts.Delete(0);
rlm@1:   SubNodes[index].AddItem(include, item);
rlm@1: }
rlm@1: 
rlm@1: void CCensorNode::AddItem(bool include, const UString &path, bool recursive, bool forFile, bool forDir)
rlm@1: {
rlm@1:   CItem item;
rlm@1:   SplitPathToParts(path, item.PathParts);
rlm@1:   item.Recursive = recursive;
rlm@1:   item.ForFile = forFile;
rlm@1:   item.ForDir = forDir;
rlm@1:   AddItem(include, item);
rlm@1: }
rlm@1: 
rlm@1: bool CCensorNode::NeedCheckSubDirs() const
rlm@1: {
rlm@1:   for (int i = 0; i < IncludeItems.Size(); i++)
rlm@1:   {
rlm@1:     const CItem &item = IncludeItems[i];
rlm@1:     if (item.Recursive || item.PathParts.Size() > 1)
rlm@1:       return true;
rlm@1:   }
rlm@1:   return false;
rlm@1: }
rlm@1: 
rlm@1: bool CCensorNode::AreThereIncludeItems() const
rlm@1: {
rlm@1:   if (IncludeItems.Size() > 0)
rlm@1:     return true;
rlm@1:   for (int i = 0; i < SubNodes.Size(); i++)
rlm@1:     if (SubNodes[i].AreThereIncludeItems())
rlm@1:       return true;
rlm@1:   return false;
rlm@1: }
rlm@1: 
rlm@1: bool CCensorNode::CheckPathCurrent(bool include, const UStringVector &pathParts, bool isFile) const
rlm@1: {
rlm@1:   const CObjectVector<CItem> &items = include ? IncludeItems : ExcludeItems;
rlm@1:   for (int i = 0; i < items.Size(); i++)
rlm@1:     if (items[i].CheckPath(pathParts, isFile))
rlm@1:       return true;
rlm@1:   return false;
rlm@1: }
rlm@1: 
rlm@1: bool CCensorNode::CheckPath(UStringVector &pathParts, bool isFile, bool &include) const
rlm@1: {
rlm@1:   if (CheckPathCurrent(false, pathParts, isFile))
rlm@1:   {
rlm@1:     include = false;
rlm@1:     return true;
rlm@1:   }
rlm@1:   include = true;
rlm@1:   bool finded = CheckPathCurrent(true, pathParts, isFile);
rlm@1:   if (pathParts.Size() == 1)
rlm@1:     return finded;
rlm@1:   int index = FindSubNode(pathParts.Front());
rlm@1:   if (index >= 0)
rlm@1:   {
rlm@1:     UStringVector pathParts2 = pathParts;
rlm@1:     pathParts2.Delete(0);
rlm@1:     if (SubNodes[index].CheckPath(pathParts2, isFile, include))
rlm@1:       return true;
rlm@1:   }
rlm@1:   return finded;
rlm@1: }
rlm@1: 
rlm@1: bool CCensorNode::CheckPath(const UString &path, bool isFile, bool &include) const
rlm@1: {
rlm@1:   UStringVector pathParts;
rlm@1:   SplitPathToParts(path, pathParts);
rlm@1:   return CheckPath(pathParts, isFile, include);
rlm@1: }
rlm@1: 
rlm@1: bool CCensorNode::CheckPath(const UString &path, bool isFile) const
rlm@1: {
rlm@1:   bool include;
rlm@1:   if (CheckPath(path, isFile, include))
rlm@1:     return include;
rlm@1:   return false;
rlm@1: }
rlm@1: 
rlm@1: bool CCensorNode::CheckPathToRoot(bool include, UStringVector &pathParts, bool isFile) const
rlm@1: {
rlm@1:   if (CheckPathCurrent(include, pathParts, isFile))
rlm@1:     return true;
rlm@1:   if (Parent == 0)
rlm@1:     return false;
rlm@1:   pathParts.Insert(0, Name);
rlm@1:   return Parent->CheckPathToRoot(include, pathParts, isFile);
rlm@1: }
rlm@1: 
rlm@1: /*
rlm@1: bool CCensorNode::CheckPathToRoot(bool include, const UString &path, bool isFile) const
rlm@1: {
rlm@1:   UStringVector pathParts;
rlm@1:   SplitPathToParts(path, pathParts);
rlm@1:   return CheckPathToRoot(include, pathParts, isFile);
rlm@1: }
rlm@1: */
rlm@1: 
rlm@1: void CCensorNode::AddItem2(bool include, const UString &path, bool recursive)
rlm@1: {
rlm@1:   if (path.IsEmpty())
rlm@1:     return;
rlm@1:   bool forFile = true;
rlm@1:   bool forFolder = true;
rlm@1:   UString path2 = path;
rlm@1:   if (IsCharDirLimiter(path[path.Length() - 1]))
rlm@1:   {
rlm@1:     path2.Delete(path.Length() - 1);
rlm@1:     forFile = false;
rlm@1:   }
rlm@1:   AddItem(include, path2, recursive, forFile, forFolder);
rlm@1: }
rlm@1: 
rlm@1: void CCensorNode::ExtendExclude(const CCensorNode &fromNodes)
rlm@1: {
rlm@1:   ExcludeItems += fromNodes.ExcludeItems;
rlm@1:   for (int i = 0; i < fromNodes.SubNodes.Size(); i++)
rlm@1:   {
rlm@1:     const CCensorNode &node = fromNodes.SubNodes[i];
rlm@1:     int subNodeIndex = FindSubNode(node.Name);
rlm@1:     if (subNodeIndex < 0)
rlm@1:       subNodeIndex = SubNodes.Add(CCensorNode(node.Name, this));
rlm@1:     SubNodes[subNodeIndex].ExtendExclude(node);
rlm@1:   }
rlm@1: }
rlm@1: 
rlm@1: int CCensor::FindPrefix(const UString &prefix) const
rlm@1: {
rlm@1:   for (int i = 0; i < Pairs.Size(); i++)
rlm@1:     if (CompareFileNames(Pairs[i].Prefix, prefix) == 0)
rlm@1:       return i;
rlm@1:   return -1;
rlm@1: }
rlm@1: 
rlm@1: void CCensor::AddItem(bool include, const UString &path, bool recursive)
rlm@1: {
rlm@1:   UStringVector pathParts;
rlm@1:   SplitPathToParts(path, pathParts);
rlm@1:   bool forFile = true;
rlm@1:   if (pathParts.Back().IsEmpty())
rlm@1:   {
rlm@1:     forFile = false;
rlm@1:     pathParts.DeleteBack();
rlm@1:   }
rlm@1:   const UString &front = pathParts.Front();
rlm@1:   bool isAbs = false;
rlm@1:   if (front.IsEmpty())
rlm@1:     isAbs = true;
rlm@1:   else if (front.Length() == 2 && front[1] == L':')
rlm@1:     isAbs = true;
rlm@1:   else
rlm@1:   {
rlm@1:     for (int i = 0; i < pathParts.Size(); i++)
rlm@1:     {
rlm@1:       const UString &part = pathParts[i];
rlm@1:       if (part == L".." || part == L".")
rlm@1:       {
rlm@1:         isAbs = true;
rlm@1:         break;
rlm@1:       }
rlm@1:     }
rlm@1:   }
rlm@1:   int numAbsParts = 0;
rlm@1:   if (isAbs)
rlm@1:     if (pathParts.Size() > 1)
rlm@1:       numAbsParts = pathParts.Size() - 1;
rlm@1:     else
rlm@1:       numAbsParts = 1;
rlm@1:   UString prefix;
rlm@1:   for (int i = 0; i < numAbsParts; i++)
rlm@1:   {
rlm@1:     const UString &front = pathParts.Front();
rlm@1:     if (DoesNameContainWildCard(front))
rlm@1:       break;
rlm@1:     prefix += front;
rlm@1:     prefix += WCHAR_PATH_SEPARATOR;
rlm@1:     pathParts.Delete(0);
rlm@1:   }
rlm@1:   int index = FindPrefix(prefix);
rlm@1:   if (index < 0)
rlm@1:     index = Pairs.Add(CPair(prefix));
rlm@1: 
rlm@1:   CItem item;
rlm@1:   item.PathParts = pathParts;
rlm@1:   item.ForDir = true;
rlm@1:   item.ForFile = forFile;
rlm@1:   item.Recursive = recursive;
rlm@1:   Pairs[index].Head.AddItem(include, item);
rlm@1: }
rlm@1: 
rlm@1: bool CCensor::CheckPath(const UString &path, bool isFile) const
rlm@1: {
rlm@1:   bool finded = false;
rlm@1:   for (int i = 0; i < Pairs.Size(); i++)
rlm@1:   {
rlm@1:     bool include;
rlm@1:     if (Pairs[i].Head.CheckPath(path, isFile, include))
rlm@1:     {
rlm@1:       if (!include)
rlm@1:         return false;
rlm@1:       finded = true;
rlm@1:     }
rlm@1:   }
rlm@1:   return finded;
rlm@1: }
rlm@1: 
rlm@1: void CCensor::ExtendExclude()
rlm@1: {
rlm@1:   int i;
rlm@1:   for (i = 0; i < Pairs.Size(); i++)
rlm@1:     if (Pairs[i].Prefix.IsEmpty())
rlm@1:       break;
rlm@1:   if (i == Pairs.Size())
rlm@1:     return;
rlm@1:   int index = i;
rlm@1:   for (i = 0; i < Pairs.Size(); i++)
rlm@1:     if (index != i)
rlm@1:       Pairs[i].Head.ExtendExclude(Pairs[index].Head);
rlm@1: }
rlm@1: 
rlm@1: }