TortoiseProc/RevisionGraph/FullGraphFinalizer.cpp

   1 // TortoiseSVN - a Windows shell extension for easy version control\r
   2 \r
   3 // Copyright (C) 2003-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 "FullGraphFinalizer.h"\r
  21 #include "FullHistory.h"\r
  22 #include "FullGraph.h"\r
  23 #include "CachedLogInfo.h"\r
  24 #include "Registry.h"\r
  25 #include "UnicodeUtils.h"\r
  26 \r
  27 #ifdef _DEBUG\r
  28 #define new DEBUG_NEW\r
  29 #undef THIS_FILE\r
  30 static char THIS_FILE[] = __FILE__;\r
  31 #endif\r
  32 \r
  33 CFullGraphFinalizer::CFullGraphFinalizer \r
  34     ( const CFullHistory& history\r
  35     , CFullGraph& graph)\r
  36     : history (history)\r
  37     , graph (graph)\r
  38 {\r
  39     // initialize path classificator\r
  40 \r
  41     CRegStdString trunkPattern (_T("Software\\TortoiseSVN\\RevisionGraph\\TrunkPattern"), _T("trunk"));\r
  42     CRegStdString branchesPattern (_T("Software\\TortoiseSVN\\RevisionGraph\\BranchPattern"), _T("branches"));\r
  43     CRegStdString tagsPattern (_T("Software\\TortoiseSVN\\RevisionGraph\\TagsPattern"), _T("tags"));\r
  44 \r
  45     const CPathDictionary& paths = history.GetCache()->GetLogInfo().GetPaths();\r
  46     pathClassification.reset \r
  47         (new CPathClassificator ( paths\r
  48                                 , CUnicodeUtils::StdGetUTF8 (trunkPattern)\r
  49                                 , CUnicodeUtils::StdGetUTF8 (branchesPattern)\r
  50                                 , CUnicodeUtils::StdGetUTF8 (tagsPattern)));\r
  51 }\r
  52 \r
  53 CFullGraphFinalizer::~CFullGraphFinalizer(void)\r
  54 {\r
  55 }\r
  56 \r
  57 void CFullGraphFinalizer::Run()\r
  58 {\r
  59     // nothing to do for empty graphs\r
  60 \r
  61     if (graph.GetRoot() == NULL)\r
  62         return;\r
  63 \r
  64         // say "renamed" for "Deleted"/"Added" entries\r
  65 \r
  66     FindRenames (graph.GetRoot());\r
  67 \r
  68     // classify all nodes (needs to fully passes):\r
  69     // classify nodes on by one\r
  70 \r
  71     ForwardClassification (graph.GetRoot());\r
  72 \r
  73     // propagate classifation back along copy history\r
  74 \r
  75     BackwardClassification (graph.GetRoot());\r
  76 }\r
  77 \r
  78 void CFullGraphFinalizer::FindRenames (CFullGraphNode* node)\r
  79 {\r
  80         // say "renamed" for "Deleted"/"Added" entries\r
  81 \r
  82     for ( CFullGraphNode * next = node->GetNext()\r
  83         ; node != NULL\r
  84         ; node = next, next = (next == NULL ? NULL : next->GetNext()))\r
  85     {\r
  86         if (   (next != NULL) \r
  87             && (next->GetClassification().Is (CNodeClassification::IS_DELETED)))\r
  88             {\r
  89             // this line will be deleted. \r
  90                     // will it be continued exactly once under a different name?\r
  91 \r
  92             CFullGraphNode* renameTarget = NULL;\r
  93             CFullGraphNode::CCopyTarget** renameCopy = NULL;\r
  94 \r
  95             for ( CFullGraphNode::CCopyTarget** copy = &node->GetFirstCopyTarget()\r
  96                 ; *copy != NULL\r
  97                 ; copy = &(*copy)->next())\r
  98                     {\r
  99                 CFullGraphNode * target = (*copy)->value();\r
 100                 assert (target->GetClassification().Is (CNodeClassification::IS_COPY_TARGET));\r
 101 \r
 102                             if (target->GetRevision() == next->GetRevision())\r
 103                             {\r
 104                                     // that actually looks like a rename\r
 105 \r
 106                     if (renameTarget != NULL)\r
 107                     {\r
 108                         // there is more than one copy target \r
 109                         // -> display all individual deletion and additions \r
 110 \r
 111                         renameTarget = NULL;\r
 112                         break;\r
 113                     }\r
 114                     else\r
 115                     {\r
 116                         // remember the (potential) rename target\r
 117 \r
 118                         renameTarget = target;\r
 119                         renameCopy = copy;\r
 120                     }\r
 121                 }\r
 122             }\r
 123 \r
 124             // did we find a unambigous rename target?\r
 125 \r
 126             if (renameTarget != NULL)\r
 127             {\r
 128                 // optimize graph\r
 129 \r
 130                 graph.Replace ( node->GetNext()\r
 131                               , *renameCopy\r
 132                               , CNodeClassification::IS_RENAMED);\r
 133 \r
 134                 // "next" has just been destroyed\r
 135 \r
 136                 next = node->GetNext();\r
 137                     }\r
 138         }\r
 139 \r
 140         // recourse\r
 141 \r
 142         for ( const CFullGraphNode::CCopyTarget* copy = node->GetFirstCopyTarget()\r
 143             ; copy != NULL\r
 144             ; copy = copy->next())\r
 145             {\r
 146             FindRenames (copy->value());\r
 147         }\r
 148     }\r
 149 }\r
 150 \r
 151 // mark nodes according to local properties\r
 152 \r
 153 void CFullGraphFinalizer::MarkRoot (CFullGraphNode* node)\r
 154 {\r
 155     if (node == graph.GetRoot())\r
 156         node->AddClassification (CNodeClassification::IS_FIRST);\r
 157 }\r
 158 \r
 159 void CFullGraphFinalizer::MarkCopySource (CFullGraphNode* node)\r
 160 {\r
 161     if (node->GetFirstCopyTarget() != NULL)\r
 162         node->AddClassification (CNodeClassification::IS_COPY_SOURCE);\r
 163 }\r
 164 \r
 165 void CFullGraphFinalizer::MarkWCRevision (CFullGraphNode* node)\r
 166 {\r
 167     // if this the same revision and path as the WC?\r
 168 \r
 169     if (   (node->GetRevision() == history.GetWCRevision())\r
 170         && (node->GetPath().GetBasePath().Intersects \r
 171                 (history.GetWCPath()->GetBasePath())))\r
 172     {\r
 173         node->AddClassification (CNodeClassification::IS_WORKINGCOPY);\r
 174     }\r
 175 }\r
 176 \r
 177 void CFullGraphFinalizer::MarkHead (CFullGraphNode* node)\r
 178 {\r
 179         // scan all "latest" nodes \r
 180     // (they must be either HEADs or special nodes)\r
 181 \r
 182     if (   (node->GetNext() != NULL)\r
 183         || (node->GetClassification().IsAnyOf \r
 184                (CNodeClassification::SUBTREE_DELETED)))\r
 185         return;\r
 186 \r
 187     // look for the latest change\r
 188     // (there may be several "copy-source-only" nodes trailing HEAD\r
 189 \r
 190     while (node->GetClassification().Matches (0, CNodeClassification::IS_OPERATION_MASK))\r
 191         node = node->GetPrevious();\r
 192 \r
 193     node->AddClassification (CNodeClassification::IS_LAST);\r
 194 }\r
 195 \r
 196 // classify nodes on by one\r
 197 \r
 198 void CFullGraphFinalizer::ForwardClassification (CFullGraphNode* node)\r
 199 {\r
 200     do\r
 201     {\r
 202         // add local classification\r
 203 \r
 204         MarkRoot (node);\r
 205         MarkCopySource (node);\r
 206         MarkWCRevision (node);\r
 207         MarkHead (node);\r
 208 \r
 209         // add path-based classification\r
 210 \r
 211         node->AddClassification ((*pathClassification)[node->GetPath()]);\r
 212 \r
 213         // recourse\r
 214 \r
 215         for ( const CFullGraphNode::CCopyTarget* copy = node->GetFirstCopyTarget()\r
 216             ; copy != NULL\r
 217             ; copy = copy->next())\r
 218             {\r
 219             ForwardClassification (copy->value());\r
 220         }\r
 221 \r
 222         node = node->GetNext();\r
 223     }\r
 224     while (node != NULL);\r
 225 }\r
 226 \r
 227 // propagate classifation back along copy history\r
 228 \r
 229 DWORD CFullGraphFinalizer::BackwardClassification (CFullGraphNode* node)\r
 230 {\r
 231     // start at the end of this chain\r
 232 \r
 233     assert (node->GetPrevious()== NULL);\r
 234 \r
 235     while (node->GetNext())\r
 236         node = node->GetNext();\r
 237 \r
 238     // classify this branch\r
 239 \r
 240     DWORD branchClassification = 0;\r
 241 \r
 242     do\r
 243     {\r
 244         // set classification on copies first\r
 245 \r
 246         DWORD commonCopyClassfication = (DWORD)(-1);  // flags set in all copyies\r
 247         DWORD aggregatedCopyClassification = 0;      // flags set in at least one copy\r
 248 \r
 249         for ( const CFullGraphNode::CCopyTarget* copy = node->GetFirstCopyTarget()\r
 250             ; copy != NULL\r
 251             ; copy = copy->next())\r
 252             {\r
 253             DWORD classification = BackwardClassification (copy->value());\r
 254             commonCopyClassfication &= classification;\r
 255             aggregatedCopyClassification |= classification;\r
 256         }\r
 257 \r
 258         // construct the common classification\r
 259 \r
 260         DWORD classification // aggregate changes along the branch\r
 261             =   branchClassification \r
 262               & ~CNodeClassification::ALL_COPIES_MASK;\r
 263 \r
 264         classification      \r
 265             |=  (node->GetClassification().GetFlags() * CNodeClassification::PATH_ONLY_SHIFT)\r
 266               & CNodeClassification::PATH_ONLY_MASK;\r
 267 \r
 268         classification      // add what applies to all branches\r
 269             |=   commonCopyClassfication & branchClassification\r
 270                & CNodeClassification::ALL_COPIES_MASK;\r
 271 \r
 272         classification      // any change to this node applies to all copies as well\r
 273             |=  (node->GetClassification().GetFlags() * CNodeClassification::ALL_COPIES_SHIFT)\r
 274               & commonCopyClassfication\r
 275               & CNodeClassification::ALL_COPIES_MASK;\r
 276 \r
 277         classification      // add changes that occur in *any* sub-tree\r
 278             |=  (aggregatedCopyClassification * CNodeClassification::COPIES_TO_SHIFT)\r
 279               & CNodeClassification::COPIES_TO_MASK;\r
 280 \r
 281         // store and return the flags\r
 282 \r
 283         DWORD nodeClassification \r
 284             =   classification \r
 285               & (  CNodeClassification::ALL_COPIES_MASK \r
 286                  + CNodeClassification::COPIES_TO_MASK\r
 287                  + CNodeClassification::PATH_ONLY_MASK);\r
 288 \r
 289         node->AddClassification (nodeClassification);\r
 290 \r
 291         // current path classification\r
 292 \r
 293         branchClassification = classification | node->GetClassification().GetFlags();\r
 294         node = node->GetPrevious();\r
 295     }\r
 296     while (node != NULL);\r
 297 \r
 298     // done\r
 299 \r
 300     return branchClassification;\r
 301 }\r