--- /dev/null
+// TortoiseSVN - a Windows shell extension for easy version control\r
+\r
+// Copyright (C) 2003-2008 - TortoiseSVN\r
+\r
+// This program is free software; you can redistribute it and/or\r
+// modify it under the terms of the GNU General Public License\r
+// as published by the Free Software Foundation; either version 2\r
+// of the License, or (at your option) any later version.\r
+\r
+// This program is distributed in the hope that it will be useful,\r
+// but WITHOUT ANY WARRANTY; without even the implied warranty of\r
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
+// GNU General Public License for more details.\r
+\r
+// You should have received a copy of the GNU General Public License\r
+// along with this program; if not, write to the Free Software Foundation,\r
+// 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.\r
+//\r
+#include "StdAfx.h"\r
+#include "FullGraphBuilder.h"\r
+#include "CachedLogInfo.h"\r
+#include "RevisionIndex.h"\r
+#include "SearchPathTree.h"\r
+#include "FullHistory.h"\r
+#include "FullGraph.h"\r
+\r
+#ifdef _DEBUG\r
+#define new DEBUG_NEW\r
+#undef THIS_FILE\r
+static char THIS_FILE[] = __FILE__;\r
+#endif\r
+\r
+CFullGraphBuilder::CFullGraphBuilder (const CFullHistory& history, CFullGraph& graph)\r
+ : history (history)\r
+ , graph (graph)\r
+{\r
+}\r
+\r
+CFullGraphBuilder::~CFullGraphBuilder(void)\r
+{\r
+}\r
+\r
+void CFullGraphBuilder::Run()\r
+{\r
+ // special case: empty log\r
+\r
+ if (history.GetHeadRevision() == NO_REVISION)\r
+ return;\r
+\r
+ // frequently used objects\r
+\r
+ const CCachedLogInfo* cache = history.GetCache();\r
+ const CRevisionIndex& revisions = cache->GetRevisions();\r
+ const CRevisionInfoContainer& revisionInfo = cache->GetLogInfo();\r
+\r
+ // initialize the paths we have to search for\r
+\r
+ std::auto_ptr<CSearchPathTree> searchTree \r
+ (new CSearchPathTree (&revisionInfo.GetPaths()));\r
+ searchTree->Insert (*history.GetStartPath(), history.GetStartRevision());\r
+\r
+ // the range of copy-to info that applies to the current revision\r
+\r
+ SCopyInfo** lastFromCopy = history.GetFirstCopyFrom();\r
+ SCopyInfo** lastToCopy = history.GetFirstCopyTo();\r
+\r
+ // collect nodes to draw ... revision by revision\r
+\r
+ for ( revision_t revision = history.GetStartRevision()\r
+ , head = history.GetHeadRevision()\r
+ ; revision <= head\r
+ ; ++revision)\r
+ {\r
+ // any known changes in this revision?\r
+\r
+ index_t index = revisions[revision];\r
+ if (index == NO_INDEX)\r
+ continue;\r
+\r
+ CDictionaryBasedPath basePath = revisionInfo.GetRootPath (index);\r
+ if (!basePath.IsValid())\r
+ continue;\r
+\r
+ // collect search paths that have been deleted in this container\r
+ // (delay potential node deletion until we finished tree traversal)\r
+\r
+ std::vector<CSearchPathTree*> toRemove;\r
+\r
+ // special handling for replacements: \r
+ // we must delete the old branches first and *then* add (some of) these\r
+ // again in the same revision\r
+\r
+ if (( revisionInfo.GetSumChanges (index) \r
+ & CRevisionInfoContainer::ACTION_REPLACED) != 0)\r
+ {\r
+ CSearchPathTree* startNode \r
+ = searchTree->FindCommonParent (basePath.GetIndex());\r
+\r
+ // crawl (possibly) affected sub-tree\r
+\r
+ AnalyzeReplacements ( revision\r
+ , revisionInfo.GetChangesBegin (index)\r
+ , revisionInfo.GetChangesEnd (index)\r
+ , startNode\r
+ , toRemove);\r
+\r
+ // remove deleted search paths\r
+\r
+ for (size_t i = 0, count = toRemove.size(); i < count; ++i)\r
+ toRemove[i]->Remove();\r
+\r
+ toRemove.clear();\r
+ }\r
+\r
+ // handle remaining copy-to entries\r
+ // (some may have a fromRevision that does not touch the fromPath)\r
+\r
+ AddCopiedPaths ( revision\r
+ , searchTree.get()\r
+ , lastToCopy);\r
+\r
+ // we are looking for search paths that (may) overlap \r
+ // with the revisions' changes\r
+\r
+ // pre-order search-tree traversal\r
+\r
+ CSearchPathTree* startNode \r
+ = searchTree->FindCommonParent (basePath.GetIndex());\r
+\r
+ if (startNode->GetPath().IsSameOrChildOf (basePath))\r
+ {\r
+ CSearchPathTree* searchNode = startNode;\r
+\r
+ AnalyzeRevisions ( revision\r
+ , revisionInfo.GetChangesBegin (index)\r
+ , revisionInfo.GetChangesEnd (index)\r
+ , searchNode\r
+ , toRemove);\r
+\r
+ startNode = startNode->GetParent();\r
+ }\r
+ else\r
+ {\r
+ CDictionaryBasedPath commonRoot\r
+ = basePath.GetCommonRoot (startNode->GetPath().GetBasePath());\r
+ startNode = searchTree->FindCommonParent (commonRoot.GetIndex());\r
+ }\r
+\r
+ #ifdef _DEBUG\r
+ if (startNode != NULL)\r
+ {\r
+ // only valid for parents of the uppermost modified path\r
+\r
+ for (CRevisionInfoContainer::CChangesIterator iter = revisionInfo.GetChangesBegin (index)\r
+ , last = revisionInfo.GetChangesEnd (index)\r
+ ; iter != last\r
+ ; ++iter)\r
+ {\r
+ assert (startNode->GetPath().IsSameOrParentOf (iter->GetPathID()));\r
+ }\r
+ }\r
+ #endif\r
+\r
+ // mark changes on parent search nodes\r
+\r
+ assert (revisionInfo.GetChangesBegin (index) != revisionInfo.GetChangesEnd (index));\r
+\r
+ for ( CSearchPathTree* searchNode = startNode\r
+ ; searchNode != NULL\r
+ ; searchNode = searchNode->GetParent())\r
+ {\r
+ if (searchNode->IsActive())\r
+ AnalyzeAsChanges (revision, searchNode);\r
+ }\r
+\r
+ // remove deleted search paths\r
+\r
+ for (size_t i = 0, count = toRemove.size(); i < count; ++i)\r
+ toRemove[i]->Remove();\r
+\r
+ // handle remaining copy-to entries\r
+ // (some may have a fromRevision that does not touch the fromPath)\r
+\r
+ FillCopyTargets ( revision\r
+ , searchTree.get()\r
+ , lastFromCopy);\r
+ }\r
+}\r
+\r
+void CFullGraphBuilder::AnalyzeReplacements ( revision_t revision\r
+ , CRevisionInfoContainer::CChangesIterator first\r
+ , CRevisionInfoContainer::CChangesIterator last\r
+ , CSearchPathTree* startNode\r
+ , std::vector<CSearchPathTree*>& toRemove)\r
+{\r
+ typedef CRevisionInfoContainer::CChangesIterator IT;\r
+\r
+ CSearchPathTree* searchNode = startNode;\r
+ do\r
+ {\r
+ // in many cases, we want only to see additions, \r
+ // deletions and replacements\r
+\r
+ bool skipSubTree = true;\r
+\r
+ const CDictionaryBasedTempPath& path = searchNode->GetPath();\r
+\r
+ // we must not modify inactive nodes\r
+\r
+ if (searchNode->IsActive())\r
+ {\r
+ // looking for the closet change that affected the path\r
+\r
+ for (IT iter = first; iter != last; ++iter)\r
+ {\r
+ index_t changePathID = iter->GetPathID();\r
+\r
+ if ( (iter->GetAction() == CRevisionInfoContainer::ACTION_REPLACED)\r
+ && (path.GetBasePath().IsSameOrChildOf (changePathID)))\r
+ {\r
+ skipSubTree = false;\r
+\r
+ // create & init the new graph node\r
+\r
+ CFullGraphNode* newNode \r
+ = graph.Add ( path\r
+ , revision\r
+ , CNodeClassification::IS_DELETED\r
+ , searchNode->GetLastEntry());\r
+\r
+ // link entries for the same search path\r
+\r
+ searchNode->ChainEntries (newNode);\r
+\r
+ // end of path\r
+\r
+ toRemove.push_back (searchNode);\r
+\r
+ // we will create at most one node per path and revision\r
+\r
+ break;\r
+ }\r
+ }\r
+ }\r
+ else\r
+ {\r
+ // can we skip the whole sub-tree?\r
+\r
+ for (IT iter = first; iter != last; ++iter)\r
+ {\r
+ if (path.IsSameOrParentOf (iter->GetPathID()))\r
+ {\r
+ skipSubTree = false;\r
+ break;\r
+ }\r
+ }\r
+ }\r
+\r
+ // to the next node\r
+\r
+ searchNode = skipSubTree\r
+ ? searchNode->GetSkipSubTreeNext (startNode)\r
+ : searchNode->GetPreOrderNext (startNode);\r
+ }\r
+ while (searchNode != startNode);\r
+\r
+}\r
+\r
+void CFullGraphBuilder::AnalyzeRevisions ( revision_t revision\r
+ , CRevisionInfoContainer::CChangesIterator first\r
+ , CRevisionInfoContainer::CChangesIterator last\r
+ , CSearchPathTree* startNode\r
+ , std::vector<CSearchPathTree*>& toRemove)\r
+{\r
+ typedef CRevisionInfoContainer::CChangesIterator IT;\r
+\r
+ CSearchPathTree* searchNode = startNode;\r
+ do\r
+ {\r
+ // in many cases, we want only to see additions, \r
+ // deletions and replacements\r
+\r
+ bool skipSubTree = true;\r
+\r
+ const CDictionaryBasedTempPath& path = searchNode->GetPath();\r
+\r
+ // we must not modify inactive nodes\r
+\r
+ if (searchNode->IsActive())\r
+ {\r
+ // looking for the closet change that affected the path\r
+\r
+ for (IT iter = first; iter != last; ++iter)\r
+ {\r
+ index_t changePathID = iter->GetPathID();\r
+\r
+ if ( (path.IsSameOrParentOf (changePathID))\r
+ || ( (iter->GetAction() != CRevisionInfoContainer::ACTION_CHANGED)\r
+ && path.GetBasePath().IsSameOrChildOf (changePathID)))\r
+ {\r
+ skipSubTree = false;\r
+\r
+ CDictionaryBasedPath changePath = iter->GetPath();\r
+\r
+ // construct the classification member\r
+\r
+ // show modifications within the sub-tree as "modified"\r
+ // (otherwise, deletions would terminate the path)\r
+\r
+ CNodeClassification classification \r
+ = CNodeClassification::IS_MODIFIED;\r
+ if (path.GetBasePath().GetIndex() >= changePath.GetIndex())\r
+ {\r
+ switch (iter->GetRawChange())\r
+ {\r
+ case CRevisionInfoContainer::ACTION_CHANGED: \r
+ break;\r
+\r
+ case CRevisionInfoContainer::ACTION_DELETED: \r
+ classification = CNodeClassification::IS_DELETED;\r
+ break;\r
+\r
+ case CRevisionInfoContainer::ACTION_ADDED\r
+ + CRevisionInfoContainer::HAS_COPY_FROM: \r
+ case CRevisionInfoContainer::ACTION_REPLACED \r
+ + CRevisionInfoContainer::HAS_COPY_FROM: \r
+ classification = CNodeClassification::IS_ADDED \r
+ + CNodeClassification::IS_COPY_TARGET;\r
+ break;\r
+\r
+ case CRevisionInfoContainer::ACTION_ADDED: \r
+ case CRevisionInfoContainer::ACTION_REPLACED: \r
+ classification = CNodeClassification::IS_ADDED;\r
+ break;\r
+ }\r
+ }\r
+\r
+ // handle copy-from special case:\r
+\r
+ if ( (classification.Is (CNodeClassification::IS_ADDED))\r
+ && (searchNode->GetLastEntry() != NULL)\r
+ && !iter->HasFromPath())\r
+ {\r
+ // we may not add paths that already exist:\r
+ // D /trunk/OldSub\r
+ // A /trunk/New\r
+ // A /trunk/New/OldSub /trunk/OldSub@r-1\r
+ // don't add /trunk/New again\r
+\r
+ continue;\r
+ }\r
+\r
+ // create & init the new graph node\r
+\r
+ CFullGraphNode* newNode \r
+ = graph.Add (path, revision, classification, searchNode->GetLastEntry());\r
+\r
+ // link entries for the same search path\r
+\r
+ searchNode->ChainEntries (newNode);\r
+\r
+ // end of path?\r
+\r
+ if (classification.Is (CNodeClassification::IS_DELETED))\r
+ toRemove.push_back (searchNode);\r
+\r
+ // we will create at most one node per path and revision\r
+\r
+ break;\r
+ }\r
+ }\r
+ }\r
+ else\r
+ {\r
+ // can we skip the whole sub-tree?\r
+\r
+ for (IT iter = first; iter != last; ++iter)\r
+ {\r
+ index_t changePathID = iter->GetPathID();\r
+\r
+ if ( path.IsSameOrParentOf (changePathID)\r
+ || ( (iter->GetAction() != CRevisionInfoContainer::ACTION_CHANGED)\r
+ && path.GetBasePath().IsSameOrChildOf (changePathID)))\r
+ {\r
+ skipSubTree = false;\r
+ break;\r
+ }\r
+ }\r
+ }\r
+\r
+ // to the next node\r
+\r
+ searchNode = skipSubTree\r
+ ? searchNode->GetSkipSubTreeNext (startNode)\r
+ : searchNode->GetPreOrderNext (startNode);\r
+ }\r
+ while (searchNode != startNode);\r
+\r
+}\r
+\r
+void CFullGraphBuilder::AnalyzeAsChanges ( revision_t revision\r
+ , CSearchPathTree* searchNode)\r
+{\r
+ // create & init the new graph node\r
+\r
+ CFullGraphNode* newNode = graph.Add ( searchNode->GetPath()\r
+ , revision\r
+ , CNodeClassification::IS_MODIFIED\r
+ , searchNode->GetLastEntry());\r
+\r
+ // link entries for the same search path\r
+\r
+ searchNode->ChainEntries (newNode);\r
+}\r
+\r
+void CFullGraphBuilder::AddCopiedPaths ( revision_t revision\r
+ , CSearchPathTree* rootNode\r
+ , SCopyInfo**& lastToCopy)\r
+{\r
+ // find range of copies that point to this revision\r
+\r
+ SCopyInfo** firstToCopy = lastToCopy;\r
+ history.GetCopyToRange (firstToCopy, lastToCopy, revision);\r
+\r
+ // create search paths for all *relevant* paths added in this revision\r
+\r
+ for (SCopyInfo** iter = firstToCopy; iter != lastToCopy; ++iter)\r
+ {\r
+ const std::vector<SCopyInfo::STarget>& targets = (*iter)->targets;\r
+ for (size_t i = 0, count = targets.size(); i < count; ++i)\r
+ {\r
+ const SCopyInfo::STarget& target = targets[i];\r
+ CSearchPathTree* node = rootNode->Insert (target.path, revision);\r
+ node->ChainEntries (target.source);\r
+ }\r
+ }\r
+}\r
+\r
+void CFullGraphBuilder::FillCopyTargets ( revision_t revision\r
+ , CSearchPathTree* rootNode\r
+ , SCopyInfo**& lastFromCopy)\r
+{\r
+ // find range of copies that start from this revision\r
+\r
+ SCopyInfo** firstFromCopy = lastFromCopy;\r
+ history.GetCopyFromRange (firstFromCopy, lastFromCopy, revision);\r
+\r
+ // create search paths for all *relevant* paths added in this revision\r
+\r
+ for (SCopyInfo** iter = firstFromCopy; iter != lastFromCopy; ++iter)\r
+ {\r
+ SCopyInfo* copy = *iter;\r
+ std::vector<SCopyInfo::STarget>& targets = copy->targets;\r
+\r
+ // crawl the whole sub-tree for path matches\r
+\r
+ CSearchPathTree* startNode \r
+ = rootNode->FindCommonParent (copy->fromPathIndex);\r
+ if (!startNode->GetPath().IsSameOrChildOf (copy->fromPathIndex))\r
+ continue;\r
+\r
+ CSearchPathTree* searchNode = startNode;\r
+ do\r
+ {\r
+ const CDictionaryBasedTempPath& path = searchNode->GetPath();\r
+ assert (path.IsSameOrChildOf (copy->fromPathIndex));\r
+\r
+ // got this path copied?\r
+\r
+ if (searchNode->IsActive())\r
+ {\r
+ CDictionaryBasedPath fromPath ( path.GetDictionary()\r
+ , copy->fromPathIndex);\r
+\r
+ // is there a better match in that target revision?\r
+ // example log @r106:\r
+ // A /trunk/F /trunk/branches/b/F 100\r
+ // R /trunk/F/a /trunk/branches/b/F/a 105\r
+ // -> don't copy from r100 but from r105\r
+\r
+ if (IsLatestCopySource ( revision\r
+ , copy->toRevision\r
+ , fromPath\r
+ , path))\r
+ {\r
+ // check for another special case:\r
+ // A /branches/b /trunk 100\r
+ // D /branches/b/a\r
+ // -> don't add a path if we are following /trunk/a\r
+\r
+ CDictionaryBasedTempPath targetPath\r
+ = path.ReplaceParent ( fromPath\r
+ , CDictionaryBasedPath ( path.GetDictionary()\r
+ , copy->toPathIndex));\r
+\r
+ if (TargetPathExists (copy->toRevision, targetPath.GetBasePath()))\r
+ {\r
+ // o.k. this is actual a copy we have to add to the tree\r
+\r
+ CFullGraphNode* entry = searchNode->GetLastEntry();\r
+ if ((entry == NULL) || (entry->GetRevision() < revision))\r
+ {\r
+ // the copy source graph node has yet to be created\r
+\r
+ entry = graph.Add ( path\r
+ , revision\r
+ , CNodeClassification::IS_COPY_SOURCE\r
+ , entry);\r
+\r
+ // link entries for the same search path\r
+\r
+ searchNode->ChainEntries (entry);\r
+ }\r
+\r
+ // add & schedule the new search path\r
+\r
+ SCopyInfo::STarget target (entry, targetPath);\r
+ targets.push_back (target);\r
+ }\r
+ }\r
+ }\r
+\r
+ // select next node\r
+\r
+ searchNode = searchNode->GetPreOrderNext (startNode);\r
+ }\r
+ while (searchNode != startNode);\r
+ }\r
+}\r
+\r
+bool CFullGraphBuilder::IsLatestCopySource ( revision_t fromRevision\r
+ , revision_t toRevision\r
+ , const CDictionaryBasedPath& fromPath\r
+ , const CDictionaryBasedTempPath& currentPath)\r
+{\r
+ // try to find a "later" / "closer" copy source\r
+\r
+ // example log @r106 (toRevision):\r
+ // A /trunk/F /trunk/branches/b/F 100\r
+ // R /trunk/F/a /trunk/branches/b/F/a 105\r
+ // -> return r105\r
+\r
+ const CCachedLogInfo* cache = history.GetCache();\r
+ const CRevisionInfoContainer& logInfo = cache->GetLogInfo();\r
+ index_t index = cache->GetRevisions()[toRevision];\r
+\r
+ // search it\r
+\r
+ for ( CRevisionInfoContainer::CChangesIterator \r
+ iter = logInfo.GetChangesBegin (index)\r
+ , end = logInfo.GetChangesEnd (index)\r
+ ; iter != end\r
+ ; ++iter)\r
+ {\r
+ // is this a copy of the current path?\r
+\r
+ if ( iter->HasFromPath() \r
+ && currentPath.IsSameOrChildOf (iter->GetFromPathID()))\r
+ {\r
+ // a later change?\r
+\r
+ if (iter->GetFromRevision() > fromRevision)\r
+ return false;\r
+\r
+ // a closer sub-path?\r
+\r
+ if (iter->GetFromPathID() > fromPath.GetIndex())\r
+ return false;\r
+ }\r
+ }\r
+\r
+ // (fromRevision, fromGraph) is the best match\r
+\r
+ return true;\r
+}\r
+\r
+bool CFullGraphBuilder::TargetPathExists ( revision_t revision\r
+ , const CDictionaryBasedPath& path)\r
+{\r
+ // follow additions and deletions to determine whether the path exists\r
+ // after the given revision\r
+\r
+ // A /branches/b /trunk 100\r
+ // D /branches/b/a\r
+ // -> /branches/b/a does not exist\r
+\r
+ const CCachedLogInfo* cache = history.GetCache();\r
+ const CRevisionInfoContainer& logInfo = cache->GetLogInfo();\r
+ index_t index = cache->GetRevisions()[revision];\r
+\r
+ // short-cut: if there are no deletions, we should be fine\r
+\r
+ if (!(logInfo.GetSumChanges (index) & CRevisionInfoContainer::ACTION_DELETED))\r
+ return true;\r
+\r
+ // crawl changes and update this flag:\r
+\r
+ bool exists = false;\r
+ for ( CRevisionInfoContainer::CChangesIterator \r
+ iter = logInfo.GetChangesBegin (index)\r
+ , end = logInfo.GetChangesEnd (index)\r
+ ; iter != end\r
+ ; ++iter)\r
+ {\r
+ // does this change affect the path?\r
+\r
+ if (path.IsSameOrChildOf (iter->GetPathID()))\r
+ {\r
+ switch (iter->GetRawChange())\r
+ {\r
+ case CRevisionInfoContainer::ACTION_DELETED :\r
+ // deletion? -> does not exist\r
+\r
+ exists = false;\r
+ break;\r
+\r
+ case CRevisionInfoContainer::ACTION_ADDED\r
+ + CRevisionInfoContainer::HAS_COPY_FROM:\r
+ case CRevisionInfoContainer::ACTION_REPLACED\r
+ + CRevisionInfoContainer::HAS_COPY_FROM:\r
+ // copy? -> does exist\r
+\r
+ // We can safely assume here, that the source tree\r
+ // contains the path in question as this is why we\r
+ // called this function at all.\r
+\r
+ exists = true;\r
+ break;\r
+\r
+ case CRevisionInfoContainer::ACTION_ADDED:\r
+ // exact addition? -> does exist\r
+\r
+ if (iter->GetPathID() == path.GetIndex())\r
+ exists = true;\r
+\r
+ break;\r
+ }\r
+ }\r
+ }\r
+\r
+ return exists;\r
+}\r
+\r
OSDN Git Service
