src/TortoiseProc/RevisionGraph/PathClassificator.cpp

   1 // TortoiseSVN - a Windows shell extension for easy version control\r
   2 \r
   3 // Copyright (C) 2007-2008 - TortoiseSVN\r
   4 \r
   5 // This program is free software; you can redistribute it and/or\r
   6 // modify it under the terms of the GNU General Public License\r
   7 // as published by the Free Software Foundation; either version 2\r
   8 // of the License, or (at your option) any later version.\r
   9 \r
  10 // This program is distributed in the hope that it will be useful,\r
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  13 // GNU General Public License for more details.\r
  14 \r
  15 // You should have received a copy of the GNU General Public License\r
  16 // along with this program; if not, write to the Free Software Foundation,\r
  17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.\r
  18 //\r
  19 #include "StdAfx.h"\r
  20 #include "PathClassificator.h"\r
  21 \r
  22 static inline bool CompareCI (char lhs, char rhs)\r
  23 {\r
  24     // lower 5 bits must be equal if same or only different in case\r
  25 \r
  26     char diffs = lhs ^ rhs;\r
  27     if ((diffs & 0x1f) != 0)\r
  28         return false;\r
  29 \r
  30     // maybe the same, different in case or just a mismatch in bits 5..7\r
  31 \r
  32     if (diffs != 0)\r
  33     {\r
  34         // not the same but maybe only different in case\r
  35 \r
  36         char lowLhs = lhs;\r
  37         if ((lowLhs >= 'A') && (lowLhs <= 'Z'))\r
  38             lowLhs += 'a' - 'A';\r
  39 \r
  40         // rhs must be normalized to lower case\r
  41 \r
  42         assert ((rhs < 'A') || (rhs > 'Z'));\r
  43 \r
  44         // mismatch?\r
  45 \r
  46         if (lowLhs != rhs)\r
  47             return false;\r
  48     }\r
  49 \r
  50     return true;\r
  51 }\r
  52 \r
  53 bool CPathClassificator::CWildCardPattern::WildCardMatch \r
  54     (const char* s, const char* pattern) const\r
  55 {\r
  56 #pragma warning(push)\r
  57 #pragma warning(disable: 4127)  // conditional expression is constant\r
  58     while (1)\r
  59 #pragma warning(pop)\r
  60     {\r
  61         // consume one pattern char per loop\r
  62 \r
  63         char c = *s;\r
  64         char p = *pattern;\r
  65 \r
  66         ++pattern;\r
  67         switch (p)\r
  68         {\r
  69         case '*':\r
  70             {\r
  71                 // asterisk at the end of a pattern matches everything\r
  72 \r
  73                 if (*pattern == 0)\r
  74                     return true;\r
  75 \r
  76                 // try to find a matching position\r
  77 \r
  78                 while (c != 0)\r
  79                 {\r
  80                     if (WildCardMatch (s, pattern))\r
  81                         return true;\r
  82 \r
  83                     c = *(++s);\r
  84                 }\r
  85 \r
  86                 // end of string -> failed\r
  87 \r
  88                 return false;\r
  89             }\r
  90         case '?':\r
  91             {\r
  92                 // string must contain at least one char\r
  93 \r
  94                 if (c == 0)\r
  95                     return false;\r
  96 \r
  97                 break;\r
  98             }\r
  99         case 0:\r
 100             {\r
 101                 // end of pattern\r
 102 \r
 103                 return c == 0;\r
 104             }\r
 105         default:\r
 106             {\r
 107                 // ordinary char vs. char match\r
 108 \r
 109                 if (CompareCI (c, p) == false)\r
 110                     return false;\r
 111             }\r
 112         }\r
 113         \r
 114         // next source char\r
 115 \r
 116         ++s;\r
 117     }\r
 118 \r
 119     // we should never get here\r
 120 \r
 121     assert (0);\r
 122     return false;\r
 123 }\r
 124 \r
 125 bool CPathClassificator::CWildCardPattern::StraightMatch \r
 126     (const char* s, size_t length) const\r
 127 {\r
 128     // that will short-cut most comparisons\r
 129 \r
 130     if (pattern.length() != length)\r
 131         return false;\r
 132 \r
 133     // compare all chars until we either find a mismatch or run out of chars\r
 134 \r
 135     for (const char* p = pattern.c_str(); *p != 0; ++p, ++s)\r
 136         if (CompareCI (*s, *p) == false)\r
 137             return false;\r
 138 \r
 139     // no mismatch found\r
 140 \r
 141     return true;\r
 142 }\r
 143 \r
 144 // construction utility\r
 145 \r
 146 void CPathClassificator::CWildCardPattern::NormalizePattern()\r
 147 {\r
 148     // normalize case\r
 149 \r
 150     for (size_t i = 0, count = pattern.length(); i < count; ++i)\r
 151     {\r
 152         char& c = pattern[i];\r
 153         if ((c >= 'A') && (c <= 'Z'))\r
 154             c += 'a' - 'A';\r
 155     }\r
 156 \r
 157     // replace all "**", "*?" by "*"\r
 158 \r
 159     size_t i = 0;\r
 160     while (i+1 < pattern.length())\r
 161     {\r
 162         if ((pattern[i] == '*') && (   (pattern[i+1] == '*') \r
 163                                     || (pattern[i+1] == '?')))\r
 164             pattern.erase (i+1);\r
 165         else \r
 166             ++i;\r
 167     }\r
 168 }\r
 169 \r
 170 // construction\r
 171 \r
 172 CPathClassificator::CWildCardPattern::CWildCardPattern \r
 173     ( const std::string& pattern)\r
 174     : pattern (pattern)\r
 175     , hasWildCards (pattern.find_first_of ("?*") != std::string::npos)\r
 176 {\r
 177     if (hasWildCards)\r
 178         NormalizePattern();\r
 179 }\r
 180 \r
 181 // match s against the pattern\r
 182 \r
 183 bool CPathClassificator::CWildCardPattern::Match \r
 184     (const char* s, size_t length) const\r
 185 {\r
 186     return hasWildCards\r
 187         ? WildCardMatch (s, pattern.c_str())\r
 188         : StraightMatch (s, length);\r
 189 };\r
 190 \r
 191 // construction utility\r
 192 \r
 193 CPathClassificator::TPatterns \r
 194 CPathClassificator::ParsePatterns (const std::string& patterns) const\r
 195 {\r
 196     TPatterns result;\r
 197 \r
 198     for (size_t start = 0; start < patterns.length();)\r
 199     {\r
 200         // find next delimiter\r
 201 \r
 202         size_t end = patterns.find (';', start);\r
 203         if (end == std::string::npos)\r
 204             end = patterns.length();\r
 205 \r
 206         // extract pattern and add it to the list\r
 207 \r
 208         std::string pattern = patterns.substr (start, end - start);\r
 209         result.push_back (CWildCardPattern (pattern));\r
 210 \r
 211         // to next pattern\r
 212 \r
 213         start = end+1;\r
 214     }\r
 215 \r
 216     return result;\r
 217 }\r
 218 \r
 219 bool CPathClassificator::Matches \r
 220     ( TPatterns::const_iterator firstPattern\r
 221     , TPatterns::const_iterator lastPattern\r
 222     , const char* element\r
 223     , size_t length) const\r
 224 {\r
 225     for ( TPatterns::const_iterator iter = firstPattern\r
 226         ; iter != lastPattern\r
 227         ; ++iter)\r
 228     {\r
 229         if (iter->Match (element, length))\r
 230             return true;\r
 231     }\r
 232 \r
 233     return false;\r
 234 }\r
 235 \r
 236 void CPathClassificator::ClassifyPathElements \r
 237     ( const LogCache::CStringDictionary& elements\r
 238     , const TPatterns& patterns\r
 239     , unsigned char classification)\r
 240 {\r
 241     TPatterns::const_iterator firstPattern = patterns.begin();\r
 242     TPatterns::const_iterator lastPattern = patterns.end();\r
 243 \r
 244     // classify\r
 245 \r
 246         for (LogCache::index_t i = 0, count = elements.size(); i < count; ++i)\r
 247         if (Matches (firstPattern, lastPattern, elements[i], elements.GetLength(i)))\r
 248             pathElementClassification[i] |= classification;\r
 249 }\r
 250 \r
 251 void CPathClassificator::ClassifyPathElements \r
 252     (const LogCache::CStringDictionary& elements)\r
 253 {\r
 254     // initialize\r
 255 \r
 256     pathElementClassification.clear();\r
 257     pathElementClassification.insert ( pathElementClassification.end()\r
 258                                      , elements.size()\r
 259                                      , 0);\r
 260 \r
 261     // one class at a time\r
 262 \r
 263     ClassifyPathElements (elements, trunkPatterns, CNodeClassification::IS_TRUNK);\r
 264     ClassifyPathElements (elements, branchesPatterns, CNodeClassification::IS_BRANCH);\r
 265     ClassifyPathElements (elements, tagsPatterns, CNodeClassification::IS_TAG);\r
 266 }\r
 267 \r
 268 void CPathClassificator::ClassifyPaths (const LogCache::CPathDictionary& paths)\r
 269 {\r
 270     // initialize\r
 271 \r
 272     pathClassification.clear();\r
 273     pathClassification.insert ( pathClassification.end()\r
 274                               , paths.size()\r
 275                               , 0);\r
 276 \r
 277     // fill (root is always "other")\r
 278 \r
 279     for (LogCache::index_t i = 1, count = paths.size(); i < count; ++i)\r
 280     {\r
 281         LogCache::index_t parentID = paths.GetParent(i);\r
 282         LogCache::index_t elementID = paths.GetPathElementID(i);\r
 283 \r
 284         // let topmost classification win\r
 285 \r
 286         unsigned char parentClassification = pathClassification [parentID];\r
 287         pathClassification[i] = parentClassification != 0\r
 288                               ? parentClassification \r
 289                               : pathElementClassification [elementID];\r
 290     }\r
 291 \r
 292     // set "other" classification where there is no classification, yet\r
 293 \r
 294     typedef std::vector<unsigned char>::iterator IT;\r
 295     for ( IT iter = pathClassification.begin(), end = pathClassification.end()\r
 296         ; iter != end\r
 297         ; ++iter)\r
 298     {\r
 299         if (*iter == 0)\r
 300             *iter = CNodeClassification::IS_OTHER;\r
 301     }\r
 302 }\r
 303 \r
 304 // construction / destruction\r
 305 \r
 306 CPathClassificator::CPathClassificator ( const LogCache::CPathDictionary& paths\r
 307                                        , const std::string& trunkPatterns\r
 308                                        , const std::string& branchesPatterns\r
 309                                        , const std::string& tagsPatterns)\r
 310     : trunkPatterns (ParsePatterns (trunkPatterns))\r
 311     , branchesPatterns (ParsePatterns (branchesPatterns))\r
 312     , tagsPatterns (ParsePatterns (tagsPatterns))\r
 313 {\r
 314     // match all paths against all patterns\r
 315 \r
 316     ClassifyPathElements (paths.GetPathElements());\r
 317     ClassifyPaths (paths);\r
 318 }\r
 319 \r
 320 CPathClassificator::~CPathClassificator(void)\r
 321 {\r
 322 }\r
 323 \r
 324 // get the classification for a given path\r
 325 \r
 326 unsigned char CPathClassificator::GetClassification \r
 327     (const LogCache::CDictionaryBasedTempPath& path) const\r
 328 {\r
 329     // use the path classification we already have\r
 330 \r
 331     unsigned char result = GetClassification (path.GetBasePath().GetIndex());\r
 332     if (path.IsFullyCachedPath())\r
 333         return result;\r
 334 \r
 335     // let topmost classification win\r
 336 \r
 337     if (result != CNodeClassification::IS_OTHER)\r
 338         return result;\r
 339     else\r
 340         result = 0;\r
 341 \r
 342     // try to classify the remaining elements as efficient as possible\r
 343 \r
 344     const std::vector<std::string>& relPathElements \r
 345         = path.GetRelPathElements();\r
 346     const LogCache::CStringDictionary& pathElements \r
 347         = path.GetDictionary()->GetPathElements();\r
 348 \r
 349     for ( size_t i = 0, count = relPathElements.size()\r
 350         ; (i < count) && (result == 0)\r
 351         ; ++i)\r
 352     {\r
 353         // we should have a classification for this element\r
 354         // (this may not be true, if part of the log history is missing)\r
 355 \r
 356         const std::string& relPathElement = relPathElements[i];\r
 357         const char* element = relPathElement.c_str();\r
 358 \r
 359         LogCache::index_t elementID = pathElements.Find (element);\r
 360         if (elementID != LogCache::NO_INDEX)\r
 361         {\r
 362             result |= pathElementClassification[elementID];\r
 363         }\r
 364         else\r
 365         {\r
 366             size_t length = relPathElement.length();\r
 367             if (Matches (trunkPatterns.begin(), trunkPatterns.end(), element, length))\r
 368                 result |= CNodeClassification::IS_TRUNK;\r
 369             if (Matches (branchesPatterns.begin(), branchesPatterns.end(), element, length))\r
 370                 result |= CNodeClassification::IS_BRANCH;\r
 371             if (Matches (tagsPatterns.begin(), tagsPatterns.end(), element, length))\r
 372                 result |= CNodeClassification::IS_TAG;\r
 373         }\r
 374     }\r
 375 \r
 376     // say "other" only if no classification was made\r
 377 \r
 378     return result == 0 \r
 379         ? (unsigned char)CNodeClassification::IS_OTHER \r
 380         : result;\r
 381 }\r