1 // TortoiseSVN - a Windows shell extension for easy version control
\r
3 // Copyright (C) 2003-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 "FullGraphBuilder.h"
\r
21 #include "CachedLogInfo.h"
\r
22 #include "RevisionIndex.h"
\r
23 #include "SearchPathTree.h"
\r
24 #include "FullHistory.h"
\r
25 #include "FullGraph.h"
\r
28 #define new DEBUG_NEW
\r
30 static char THIS_FILE[] = __FILE__;
\r
33 CFullGraphBuilder::CFullGraphBuilder (const CFullHistory& history, CFullGraph& graph)
\r
39 CFullGraphBuilder::~CFullGraphBuilder(void)
\r
43 void CFullGraphBuilder::Run()
\r
45 // special case: empty log
\r
47 if (history.GetHeadRevision() == NO_REVISION)
\r
50 // frequently used objects
\r
52 const CCachedLogInfo* cache = history.GetCache();
\r
53 const CRevisionIndex& revisions = cache->GetRevisions();
\r
54 const CRevisionInfoContainer& revisionInfo = cache->GetLogInfo();
\r
56 // initialize the paths we have to search for
\r
58 std::auto_ptr<CSearchPathTree> searchTree
\r
59 (new CSearchPathTree (&revisionInfo.GetPaths()));
\r
60 searchTree->Insert (*history.GetStartPath(), history.GetStartRevision());
\r
62 // the range of copy-to info that applies to the current revision
\r
64 SCopyInfo** lastFromCopy = history.GetFirstCopyFrom();
\r
65 SCopyInfo** lastToCopy = history.GetFirstCopyTo();
\r
67 // collect nodes to draw ... revision by revision
\r
69 for ( revision_t revision = history.GetStartRevision()
\r
70 , head = history.GetHeadRevision()
\r
74 // any known changes in this revision?
\r
76 index_t index = revisions[revision];
\r
77 if (index == NO_INDEX)
\r
80 CDictionaryBasedPath basePath = revisionInfo.GetRootPath (index);
\r
81 if (!basePath.IsValid())
\r
84 // collect search paths that have been deleted in this container
\r
85 // (delay potential node deletion until we finished tree traversal)
\r
87 std::vector<CSearchPathTree*> toRemove;
\r
89 // special handling for replacements:
\r
90 // we must delete the old branches first and *then* add (some of) these
\r
91 // again in the same revision
\r
93 if (( revisionInfo.GetSumChanges (index)
\r
94 & CRevisionInfoContainer::ACTION_REPLACED) != 0)
\r
96 CSearchPathTree* startNode
\r
97 = searchTree->FindCommonParent (basePath.GetIndex());
\r
99 // crawl (possibly) affected sub-tree
\r
101 AnalyzeReplacements ( revision
\r
102 , revisionInfo.GetChangesBegin (index)
\r
103 , revisionInfo.GetChangesEnd (index)
\r
107 // remove deleted search paths
\r
109 for (size_t i = 0, count = toRemove.size(); i < count; ++i)
\r
110 toRemove[i]->Remove();
\r
115 // handle remaining copy-to entries
\r
116 // (some may have a fromRevision that does not touch the fromPath)
\r
118 AddCopiedPaths ( revision
\r
122 // we are looking for search paths that (may) overlap
\r
123 // with the revisions' changes
\r
125 // pre-order search-tree traversal
\r
127 CSearchPathTree* startNode
\r
128 = searchTree->FindCommonParent (basePath.GetIndex());
\r
130 if (startNode->GetPath().IsSameOrChildOf (basePath))
\r
132 CSearchPathTree* searchNode = startNode;
\r
134 AnalyzeRevisions ( revision
\r
135 , revisionInfo.GetChangesBegin (index)
\r
136 , revisionInfo.GetChangesEnd (index)
\r
140 startNode = startNode->GetParent();
\r
144 CDictionaryBasedPath commonRoot
\r
145 = basePath.GetCommonRoot (startNode->GetPath().GetBasePath());
\r
146 startNode = searchTree->FindCommonParent (commonRoot.GetIndex());
\r
150 if (startNode != NULL)
\r
152 // only valid for parents of the uppermost modified path
\r
154 for (CRevisionInfoContainer::CChangesIterator iter = revisionInfo.GetChangesBegin (index)
\r
155 , last = revisionInfo.GetChangesEnd (index)
\r
159 assert (startNode->GetPath().IsSameOrParentOf (iter->GetPathID()));
\r
164 // mark changes on parent search nodes
\r
166 assert (revisionInfo.GetChangesBegin (index) != revisionInfo.GetChangesEnd (index));
\r
168 for ( CSearchPathTree* searchNode = startNode
\r
169 ; searchNode != NULL
\r
170 ; searchNode = searchNode->GetParent())
\r
172 if (searchNode->IsActive())
\r
173 AnalyzeAsChanges (revision, searchNode);
\r
176 // remove deleted search paths
\r
178 for (size_t i = 0, count = toRemove.size(); i < count; ++i)
\r
179 toRemove[i]->Remove();
\r
181 // handle remaining copy-to entries
\r
182 // (some may have a fromRevision that does not touch the fromPath)
\r
184 FillCopyTargets ( revision
\r
190 void CFullGraphBuilder::AnalyzeReplacements ( revision_t revision
\r
191 , CRevisionInfoContainer::CChangesIterator first
\r
192 , CRevisionInfoContainer::CChangesIterator last
\r
193 , CSearchPathTree* startNode
\r
194 , std::vector<CSearchPathTree*>& toRemove)
\r
196 typedef CRevisionInfoContainer::CChangesIterator IT;
\r
198 CSearchPathTree* searchNode = startNode;
\r
201 // in many cases, we want only to see additions,
\r
202 // deletions and replacements
\r
204 bool skipSubTree = true;
\r
206 const CDictionaryBasedTempPath& path = searchNode->GetPath();
\r
208 // we must not modify inactive nodes
\r
210 if (searchNode->IsActive())
\r
212 // looking for the closet change that affected the path
\r
214 for (IT iter = first; iter != last; ++iter)
\r
216 index_t changePathID = iter->GetPathID();
\r
218 if ( (iter->GetAction() == CRevisionInfoContainer::ACTION_REPLACED)
\r
219 && (path.GetBasePath().IsSameOrChildOf (changePathID)))
\r
221 skipSubTree = false;
\r
223 // create & init the new graph node
\r
225 CFullGraphNode* newNode
\r
228 , CNodeClassification::IS_DELETED
\r
229 , searchNode->GetLastEntry());
\r
231 // link entries for the same search path
\r
233 searchNode->ChainEntries (newNode);
\r
237 toRemove.push_back (searchNode);
\r
239 // we will create at most one node per path and revision
\r
247 // can we skip the whole sub-tree?
\r
249 for (IT iter = first; iter != last; ++iter)
\r
251 if (path.IsSameOrParentOf (iter->GetPathID()))
\r
253 skipSubTree = false;
\r
259 // to the next node
\r
261 searchNode = skipSubTree
\r
262 ? searchNode->GetSkipSubTreeNext (startNode)
\r
263 : searchNode->GetPreOrderNext (startNode);
\r
265 while (searchNode != startNode);
\r
269 void CFullGraphBuilder::AnalyzeRevisions ( revision_t revision
\r
270 , CRevisionInfoContainer::CChangesIterator first
\r
271 , CRevisionInfoContainer::CChangesIterator last
\r
272 , CSearchPathTree* startNode
\r
273 , std::vector<CSearchPathTree*>& toRemove)
\r
275 typedef CRevisionInfoContainer::CChangesIterator IT;
\r
277 CSearchPathTree* searchNode = startNode;
\r
280 // in many cases, we want only to see additions,
\r
281 // deletions and replacements
\r
283 bool skipSubTree = true;
\r
285 const CDictionaryBasedTempPath& path = searchNode->GetPath();
\r
287 // we must not modify inactive nodes
\r
289 if (searchNode->IsActive())
\r
291 // looking for the closet change that affected the path
\r
293 for (IT iter = first; iter != last; ++iter)
\r
295 index_t changePathID = iter->GetPathID();
\r
297 if ( (path.IsSameOrParentOf (changePathID))
\r
298 || ( (iter->GetAction() != CRevisionInfoContainer::ACTION_CHANGED)
\r
299 && path.GetBasePath().IsSameOrChildOf (changePathID)))
\r
301 skipSubTree = false;
\r
303 CDictionaryBasedPath changePath = iter->GetPath();
\r
305 // construct the classification member
\r
307 // show modifications within the sub-tree as "modified"
\r
308 // (otherwise, deletions would terminate the path)
\r
310 CNodeClassification classification
\r
311 = CNodeClassification::IS_MODIFIED;
\r
312 if (path.GetBasePath().GetIndex() >= changePath.GetIndex())
\r
314 switch (iter->GetRawChange())
\r
316 case CRevisionInfoContainer::ACTION_CHANGED:
\r
319 case CRevisionInfoContainer::ACTION_DELETED:
\r
320 classification = CNodeClassification::IS_DELETED;
\r
323 case CRevisionInfoContainer::ACTION_ADDED
\r
324 + CRevisionInfoContainer::HAS_COPY_FROM:
\r
325 case CRevisionInfoContainer::ACTION_REPLACED
\r
326 + CRevisionInfoContainer::HAS_COPY_FROM:
\r
327 classification = CNodeClassification::IS_ADDED
\r
328 + CNodeClassification::IS_COPY_TARGET;
\r
331 case CRevisionInfoContainer::ACTION_ADDED:
\r
332 case CRevisionInfoContainer::ACTION_REPLACED:
\r
333 classification = CNodeClassification::IS_ADDED;
\r
338 // handle copy-from special case:
\r
340 if ( (classification.Is (CNodeClassification::IS_ADDED))
\r
341 && (searchNode->GetLastEntry() != NULL)
\r
342 && !iter->HasFromPath())
\r
344 // we may not add paths that already exist:
\r
347 // A /trunk/New/OldSub /trunk/OldSub@r-1
\r
348 // don't add /trunk/New again
\r
353 // create & init the new graph node
\r
355 CFullGraphNode* newNode
\r
356 = graph.Add (path, revision, classification, searchNode->GetLastEntry());
\r
358 // link entries for the same search path
\r
360 searchNode->ChainEntries (newNode);
\r
364 if (classification.Is (CNodeClassification::IS_DELETED))
\r
365 toRemove.push_back (searchNode);
\r
367 // we will create at most one node per path and revision
\r
375 // can we skip the whole sub-tree?
\r
377 for (IT iter = first; iter != last; ++iter)
\r
379 index_t changePathID = iter->GetPathID();
\r
381 if ( path.IsSameOrParentOf (changePathID)
\r
382 || ( (iter->GetAction() != CRevisionInfoContainer::ACTION_CHANGED)
\r
383 && path.GetBasePath().IsSameOrChildOf (changePathID)))
\r
385 skipSubTree = false;
\r
391 // to the next node
\r
393 searchNode = skipSubTree
\r
394 ? searchNode->GetSkipSubTreeNext (startNode)
\r
395 : searchNode->GetPreOrderNext (startNode);
\r
397 while (searchNode != startNode);
\r
401 void CFullGraphBuilder::AnalyzeAsChanges ( revision_t revision
\r
402 , CSearchPathTree* searchNode)
\r
404 // create & init the new graph node
\r
406 CFullGraphNode* newNode = graph.Add ( searchNode->GetPath()
\r
408 , CNodeClassification::IS_MODIFIED
\r
409 , searchNode->GetLastEntry());
\r
411 // link entries for the same search path
\r
413 searchNode->ChainEntries (newNode);
\r
416 void CFullGraphBuilder::AddCopiedPaths ( revision_t revision
\r
417 , CSearchPathTree* rootNode
\r
418 , SCopyInfo**& lastToCopy)
\r
420 // find range of copies that point to this revision
\r
422 SCopyInfo** firstToCopy = lastToCopy;
\r
423 history.GetCopyToRange (firstToCopy, lastToCopy, revision);
\r
425 // create search paths for all *relevant* paths added in this revision
\r
427 for (SCopyInfo** iter = firstToCopy; iter != lastToCopy; ++iter)
\r
429 const std::vector<SCopyInfo::STarget>& targets = (*iter)->targets;
\r
430 for (size_t i = 0, count = targets.size(); i < count; ++i)
\r
432 const SCopyInfo::STarget& target = targets[i];
\r
433 CSearchPathTree* node = rootNode->Insert (target.path, revision);
\r
434 node->ChainEntries (target.source);
\r
439 void CFullGraphBuilder::FillCopyTargets ( revision_t revision
\r
440 , CSearchPathTree* rootNode
\r
441 , SCopyInfo**& lastFromCopy)
\r
443 // find range of copies that start from this revision
\r
445 SCopyInfo** firstFromCopy = lastFromCopy;
\r
446 history.GetCopyFromRange (firstFromCopy, lastFromCopy, revision);
\r
448 // create search paths for all *relevant* paths added in this revision
\r
450 for (SCopyInfo** iter = firstFromCopy; iter != lastFromCopy; ++iter)
\r
452 SCopyInfo* copy = *iter;
\r
453 std::vector<SCopyInfo::STarget>& targets = copy->targets;
\r
455 // crawl the whole sub-tree for path matches
\r
457 CSearchPathTree* startNode
\r
458 = rootNode->FindCommonParent (copy->fromPathIndex);
\r
459 if (!startNode->GetPath().IsSameOrChildOf (copy->fromPathIndex))
\r
462 CSearchPathTree* searchNode = startNode;
\r
465 const CDictionaryBasedTempPath& path = searchNode->GetPath();
\r
466 assert (path.IsSameOrChildOf (copy->fromPathIndex));
\r
468 // got this path copied?
\r
470 if (searchNode->IsActive())
\r
472 CDictionaryBasedPath fromPath ( path.GetDictionary()
\r
473 , copy->fromPathIndex);
\r
475 // is there a better match in that target revision?
\r
476 // example log @r106:
\r
477 // A /trunk/F /trunk/branches/b/F 100
\r
478 // R /trunk/F/a /trunk/branches/b/F/a 105
\r
479 // -> don't copy from r100 but from r105
\r
481 if (IsLatestCopySource ( revision
\r
486 // check for another special case:
\r
487 // A /branches/b /trunk 100
\r
489 // -> don't add a path if we are following /trunk/a
\r
491 CDictionaryBasedTempPath targetPath
\r
492 = path.ReplaceParent ( fromPath
\r
493 , CDictionaryBasedPath ( path.GetDictionary()
\r
494 , copy->toPathIndex));
\r
496 if (TargetPathExists (copy->toRevision, targetPath.GetBasePath()))
\r
498 // o.k. this is actual a copy we have to add to the tree
\r
500 CFullGraphNode* entry = searchNode->GetLastEntry();
\r
501 if ((entry == NULL) || (entry->GetRevision() < revision))
\r
503 // the copy source graph node has yet to be created
\r
505 entry = graph.Add ( path
\r
507 , CNodeClassification::IS_COPY_SOURCE
\r
510 // link entries for the same search path
\r
512 searchNode->ChainEntries (entry);
\r
515 // add & schedule the new search path
\r
517 SCopyInfo::STarget target (entry, targetPath);
\r
518 targets.push_back (target);
\r
523 // select next node
\r
525 searchNode = searchNode->GetPreOrderNext (startNode);
\r
527 while (searchNode != startNode);
\r
531 bool CFullGraphBuilder::IsLatestCopySource ( revision_t fromRevision
\r
532 , revision_t toRevision
\r
533 , const CDictionaryBasedPath& fromPath
\r
534 , const CDictionaryBasedTempPath& currentPath)
\r
536 // try to find a "later" / "closer" copy source
\r
538 // example log @r106 (toRevision):
\r
539 // A /trunk/F /trunk/branches/b/F 100
\r
540 // R /trunk/F/a /trunk/branches/b/F/a 105
\r
543 const CCachedLogInfo* cache = history.GetCache();
\r
544 const CRevisionInfoContainer& logInfo = cache->GetLogInfo();
\r
545 index_t index = cache->GetRevisions()[toRevision];
\r
549 for ( CRevisionInfoContainer::CChangesIterator
\r
550 iter = logInfo.GetChangesBegin (index)
\r
551 , end = logInfo.GetChangesEnd (index)
\r
555 // is this a copy of the current path?
\r
557 if ( iter->HasFromPath()
\r
558 && currentPath.IsSameOrChildOf (iter->GetFromPathID()))
\r
562 if (iter->GetFromRevision() > fromRevision)
\r
565 // a closer sub-path?
\r
567 if (iter->GetFromPathID() > fromPath.GetIndex())
\r
572 // (fromRevision, fromGraph) is the best match
\r
577 bool CFullGraphBuilder::TargetPathExists ( revision_t revision
\r
578 , const CDictionaryBasedPath& path)
\r
580 // follow additions and deletions to determine whether the path exists
\r
581 // after the given revision
\r
583 // A /branches/b /trunk 100
\r
585 // -> /branches/b/a does not exist
\r
587 const CCachedLogInfo* cache = history.GetCache();
\r
588 const CRevisionInfoContainer& logInfo = cache->GetLogInfo();
\r
589 index_t index = cache->GetRevisions()[revision];
\r
591 // short-cut: if there are no deletions, we should be fine
\r
593 if (!(logInfo.GetSumChanges (index) & CRevisionInfoContainer::ACTION_DELETED))
\r
596 // crawl changes and update this flag:
\r
598 bool exists = false;
\r
599 for ( CRevisionInfoContainer::CChangesIterator
\r
600 iter = logInfo.GetChangesBegin (index)
\r
601 , end = logInfo.GetChangesEnd (index)
\r
605 // does this change affect the path?
\r
607 if (path.IsSameOrChildOf (iter->GetPathID()))
\r
609 switch (iter->GetRawChange())
\r
611 case CRevisionInfoContainer::ACTION_DELETED :
\r
612 // deletion? -> does not exist
\r
617 case CRevisionInfoContainer::ACTION_ADDED
\r
618 + CRevisionInfoContainer::HAS_COPY_FROM:
\r
619 case CRevisionInfoContainer::ACTION_REPLACED
\r
620 + CRevisionInfoContainer::HAS_COPY_FROM:
\r
621 // copy? -> does exist
\r
623 // We can safely assume here, that the source tree
\r
624 // contains the path in question as this is why we
\r
625 // called this function at all.
\r
630 case CRevisionInfoContainer::ACTION_ADDED:
\r
631 // exact addition? -> does exist
\r
633 if (iter->GetPathID() == path.GetIndex())
\r