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