1 // TortoiseSVN - a Windows shell extension for easy version control
\r
3 // Copyright (C) 2007-2008 - TortoiseSVN
\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
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
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
20 #include "PathClassificator.h"
\r
22 static inline bool CompareCI (char lhs, char rhs)
\r
24 // lower 5 bits must be equal if same or only different in case
\r
26 char diffs = lhs ^ rhs;
\r
27 if ((diffs & 0x1f) != 0)
\r
30 // maybe the same, different in case or just a mismatch in bits 5..7
\r
34 // not the same but maybe only different in case
\r
37 if ((lowLhs >= 'A') && (lowLhs <= 'Z'))
\r
38 lowLhs += 'a' - 'A';
\r
40 // rhs must be normalized to lower case
\r
42 assert ((rhs < 'A') || (rhs > 'Z'));
\r
53 bool CPathClassificator::CWildCardPattern::WildCardMatch
\r
54 (const char* s, const char* pattern) const
\r
56 #pragma warning(push)
\r
57 #pragma warning(disable: 4127) // conditional expression is constant
\r
59 #pragma warning(pop)
\r
61 // consume one pattern char per loop
\r
71 // asterisk at the end of a pattern matches everything
\r
76 // try to find a matching position
\r
80 if (WildCardMatch (s, pattern))
\r
86 // end of string -> failed
\r
92 // string must contain at least one char
\r
107 // ordinary char vs. char match
\r
109 if (CompareCI (c, p) == false)
\r
114 // next source char
\r
119 // we should never get here
\r
125 bool CPathClassificator::CWildCardPattern::StraightMatch
\r
126 (const char* s, size_t length) const
\r
128 // that will short-cut most comparisons
\r
130 if (pattern.length() != length)
\r
133 // compare all chars until we either find a mismatch or run out of chars
\r
135 for (const char* p = pattern.c_str(); *p != 0; ++p, ++s)
\r
136 if (CompareCI (*s, *p) == false)
\r
139 // no mismatch found
\r
144 // construction utility
\r
146 void CPathClassificator::CWildCardPattern::NormalizePattern()
\r
150 for (size_t i = 0, count = pattern.length(); i < count; ++i)
\r
152 char& c = pattern[i];
\r
153 if ((c >= 'A') && (c <= 'Z'))
\r
157 // replace all "**", "*?" by "*"
\r
160 while (i+1 < pattern.length())
\r
162 if ((pattern[i] == '*') && ( (pattern[i+1] == '*')
\r
163 || (pattern[i+1] == '?')))
\r
164 pattern.erase (i+1);
\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
178 NormalizePattern();
\r
181 // match s against the pattern
\r
183 bool CPathClassificator::CWildCardPattern::Match
\r
184 (const char* s, size_t length) const
\r
186 return hasWildCards
\r
187 ? WildCardMatch (s, pattern.c_str())
\r
188 : StraightMatch (s, length);
\r
191 // construction utility
\r
193 CPathClassificator::TPatterns
\r
194 CPathClassificator::ParsePatterns (const std::string& patterns) const
\r
198 for (size_t start = 0; start < patterns.length();)
\r
200 // find next delimiter
\r
202 size_t end = patterns.find (';', start);
\r
203 if (end == std::string::npos)
\r
204 end = patterns.length();
\r
206 // extract pattern and add it to the list
\r
208 std::string pattern = patterns.substr (start, end - start);
\r
209 result.push_back (CWildCardPattern (pattern));
\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
225 for ( TPatterns::const_iterator iter = firstPattern
\r
226 ; iter != lastPattern
\r
229 if (iter->Match (element, length))
\r
236 void CPathClassificator::ClassifyPathElements
\r
237 ( const LogCache::CStringDictionary& elements
\r
238 , const TPatterns& patterns
\r
239 , unsigned char classification)
\r
241 TPatterns::const_iterator firstPattern = patterns.begin();
\r
242 TPatterns::const_iterator lastPattern = patterns.end();
\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
251 void CPathClassificator::ClassifyPathElements
\r
252 (const LogCache::CStringDictionary& elements)
\r
256 pathElementClassification.clear();
\r
257 pathElementClassification.insert ( pathElementClassification.end()
\r
261 // one class at a time
\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
268 void CPathClassificator::ClassifyPaths (const LogCache::CPathDictionary& paths)
\r
272 pathClassification.clear();
\r
273 pathClassification.insert ( pathClassification.end()
\r
277 // fill (root is always "other")
\r
279 for (LogCache::index_t i = 1, count = paths.size(); i < count; ++i)
\r
281 LogCache::index_t parentID = paths.GetParent(i);
\r
282 LogCache::index_t elementID = paths.GetPathElementID(i);
\r
284 // let topmost classification win
\r
286 unsigned char parentClassification = pathClassification [parentID];
\r
287 pathClassification[i] = parentClassification != 0
\r
288 ? parentClassification
\r
289 : pathElementClassification [elementID];
\r
292 // set "other" classification where there is no classification, yet
\r
294 typedef std::vector<unsigned char>::iterator IT;
\r
295 for ( IT iter = pathClassification.begin(), end = pathClassification.end()
\r
300 *iter = CNodeClassification::IS_OTHER;
\r
304 // construction / destruction
\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
314 // match all paths against all patterns
\r
316 ClassifyPathElements (paths.GetPathElements());
\r
317 ClassifyPaths (paths);
\r
320 CPathClassificator::~CPathClassificator(void)
\r
324 // get the classification for a given path
\r
326 unsigned char CPathClassificator::GetClassification
\r
327 (const LogCache::CDictionaryBasedTempPath& path) const
\r
329 // use the path classification we already have
\r
331 unsigned char result = GetClassification (path.GetBasePath().GetIndex());
\r
332 if (path.IsFullyCachedPath())
\r
335 // let topmost classification win
\r
337 if (result != CNodeClassification::IS_OTHER)
\r
342 // try to classify the remaining elements as efficient as possible
\r
344 const std::vector<std::string>& relPathElements
\r
345 = path.GetRelPathElements();
\r
346 const LogCache::CStringDictionary& pathElements
\r
347 = path.GetDictionary()->GetPathElements();
\r
349 for ( size_t i = 0, count = relPathElements.size()
\r
350 ; (i < count) && (result == 0)
\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
356 const std::string& relPathElement = relPathElements[i];
\r
357 const char* element = relPathElement.c_str();
\r
359 LogCache::index_t elementID = pathElements.Find (element);
\r
360 if (elementID != LogCache::NO_INDEX)
\r
362 result |= pathElementClassification[elementID];
\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
376 // say "other" only if no classification was made
\r
378 return result == 0
\r
379 ? (unsigned char)CNodeClassification::IS_OTHER
\r