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