cvs2svn_lib/symbol_statistics.py

   1 # (Be in -*- python -*- mode.)
   2 #
   3 # ====================================================================
   4 # Copyright (c) 2000-2008 CollabNet.  All rights reserved.
   5 #
   6 # This software is licensed as described in the file COPYING, which
   7 # you should have received as part of this distribution.  The terms
   8 # are also available at http://subversion.tigris.org/license-1.html.
   9 # If newer versions of this license are posted there, you may use a
  10 # newer version instead, at your option.
  11 #
  12 # This software consists of voluntary contributions made by many
  13 # individuals.  For exact contribution history, see the revision
  14 # history and logs, available at http://cvs2svn.tigris.org/.
  15 # ====================================================================
  16
  17 """This module gathers and processes statistics about lines of development."""
  18
  19 import cPickle
  20
  21 from cvs2svn_lib import config
  22 from cvs2svn_lib.common import error_prefix
  23 from cvs2svn_lib.common import FatalException
  24 from cvs2svn_lib.log import logger
  25 from cvs2svn_lib.artifact_manager import artifact_manager
  26 from cvs2svn_lib.symbol import Trunk
  27 from cvs2svn_lib.symbol import IncludedSymbol
  28 from cvs2svn_lib.symbol import Branch
  29 from cvs2svn_lib.symbol import Tag
  30 from cvs2svn_lib.symbol import ExcludedSymbol
  31
  32
  33 class SymbolPlanError(FatalException):
  34   pass
  35
  36
  37 class SymbolPlanException(SymbolPlanError):
  38   def __init__(self, stats, symbol, msg):
  39     self.stats = stats
  40     self.symbol = symbol
  41     SymbolPlanError.__init__(
  42         self,
  43         'Cannot convert the following symbol to %s: %s\n    %s'
  44         % (symbol, msg, self.stats,)
  45         )
  46
  47
  48 class IndeterminateSymbolException(SymbolPlanException):
  49   def __init__(self, stats, symbol):
  50     SymbolPlanException.__init__(self, stats, symbol, 'Indeterminate type')
  51
  52
  53 class _Stats:
  54   """A summary of information about a symbol (tag or branch).
  55
  56   Members:
  57
  58     lod -- the LineOfDevelopment instance of the lod being described
  59
  60     tag_create_count -- the number of files in which this lod appears
  61         as a tag
  62
  63     branch_create_count -- the number of files in which this lod
  64         appears as a branch
  65
  66     branch_commit_count -- the number of files in which there were
  67         commits on this lod
  68
  69     trivial_import_count -- the number of files in which this branch
  70         was purely a non-trunk default branch containing exactly one
  71         revision.
  72
  73     pure_ntdb_count -- the number of files in which this branch was
  74         purely a non-trunk default branch (consisting only of
  75         non-trunk default branch revisions).
  76
  77     branch_blockers -- a set of Symbol instances for any symbols that
  78         sprout from a branch with this name.
  79
  80     possible_parents -- a map {LineOfDevelopment : count} indicating
  81         in how many files each LOD could have served as the parent of
  82         self.lod."""
  83
  84   def __init__(self, lod):
  85     self.lod = lod
  86     self.tag_create_count = 0
  87     self.branch_create_count = 0
  88     self.branch_commit_count = 0
  89     self.branch_blockers = set()
  90     self.trivial_import_count = 0
  91     self.pure_ntdb_count = 0
  92     self.possible_parents = { }
  93
  94   def register_tag_creation(self):
  95     """Register the creation of this lod as a tag."""
  96
  97     self.tag_create_count += 1
  98
  99   def register_branch_creation(self):
 100     """Register the creation of this lod as a branch."""
 101
 102     self.branch_create_count += 1
 103
 104   def register_branch_commit(self):
 105     """Register that there were commit(s) on this branch in one file."""
 106
 107     self.branch_commit_count += 1
 108
 109   def register_branch_blocker(self, blocker):
 110     """Register BLOCKER as preventing this symbol from being deleted.
 111
 112     BLOCKER is a tag or a branch that springs from a revision on this
 113     symbol."""
 114
 115     self.branch_blockers.add(blocker)
 116
 117   def register_trivial_import(self):
 118     """Register that this branch is a trivial import branch in one file."""
 119
 120     self.trivial_import_count += 1
 121
 122   def register_pure_ntdb(self):
 123     """Register that this branch is a pure import branch in one file."""
 124
 125     self.pure_ntdb_count += 1
 126
 127   def register_possible_parent(self, lod):
 128     """Register that LOD was a possible parent for SELF.lod in a file."""
 129
 130     self.possible_parents[lod] = self.possible_parents.get(lod, 0) + 1
 131
 132   def register_branch_possible_parents(self, cvs_branch, cvs_file_items):
 133     """Register any possible parents of this symbol from CVS_BRANCH."""
 134
 135     # This routine is a bottleneck.  So we define some local variables
 136     # to speed up access to frequently-needed variables.
 137     register = self.register_possible_parent
 138     parent_cvs_rev = cvs_file_items[cvs_branch.source_id]
 139
 140     # The "obvious" parent of a branch is the branch holding the
 141     # revision where the branch is rooted:
 142     register(parent_cvs_rev.lod)
 143
 144     # If the parent revision is a non-trunk default (vendor) branch
 145     # revision, then count trunk as a possible parent.  In particular,
 146     # the symbol could be grafted to the post-commit that copies the
 147     # vendor branch changes to trunk.  On the other hand, our vendor
 148     # branch handling is currently too stupid to do so.  On the other
 149     # other hand, when the vendor branch is being excluded from the
 150     # conversion, then the vendor branch revision will be moved to
 151     # trunk, again making trunk a possible parent--and *this* our code
 152     # can handle.  In the end, considering trunk a possible parent can
 153     # never affect the correctness of the conversion, and on balance
 154     # seems to improve the selection of symbol parents.
 155     if parent_cvs_rev.ntdbr:
 156       register(cvs_file_items.trunk)
 157
 158     # Any other branches that are rooted at the same revision and
 159     # were committed earlier than the branch are also possible
 160     # parents:
 161     symbol = cvs_branch.symbol
 162     for branch_id in parent_cvs_rev.branch_ids:
 163       parent_symbol = cvs_file_items[branch_id].symbol
 164       # A branch cannot be its own parent, nor can a branch's
 165       # parent be a branch that was created after it.  So we stop
 166       # iterating when we reached the branch whose parents we are
 167       # collecting:
 168       if parent_symbol == symbol:
 169         break
 170       register(parent_symbol)
 171
 172   def register_tag_possible_parents(self, cvs_tag, cvs_file_items):
 173     """Register any possible parents of this symbol from CVS_TAG."""
 174
 175     # This routine is a bottleneck.  So use local variables to speed
 176     # up access to frequently-needed objects.
 177     register = self.register_possible_parent
 178     parent_cvs_rev = cvs_file_items[cvs_tag.source_id]
 179
 180     # The "obvious" parent of a tag is the branch holding the
 181     # revision where the branch is rooted:
 182     register(parent_cvs_rev.lod)
 183
 184     # If the parent revision is a non-trunk default (vendor) branch
 185     # revision, then count trunk as a possible parent.  See the
 186     # comment by the analogous code in
 187     # register_branch_possible_parents() for more details.
 188     if parent_cvs_rev.ntdbr:
 189       register(cvs_file_items.trunk)
 190
 191     # Branches that are rooted at the same revision are also
 192     # possible parents:
 193     for branch_id in parent_cvs_rev.branch_ids:
 194       parent_symbol = cvs_file_items[branch_id].symbol
 195       register(parent_symbol)
 196
 197   def is_ghost(self):
 198     """Return True iff this lod never really existed."""
 199
 200     return (
 201         not isinstance(self.lod, Trunk)
 202         and self.branch_commit_count == 0
 203         and not self.branch_blockers
 204         and not self.possible_parents
 205         )
 206
 207   def check_valid(self, symbol):
 208     """Check whether SYMBOL is a valid conversion of SELF.lod.
 209
 210     It is planned to convert SELF.lod as SYMBOL.  Verify that SYMBOL
 211     is a TypedSymbol and that the information that it contains is
 212     consistent with that stored in SELF.lod.  (This routine does not
 213     do higher-level tests of whether the chosen conversion is actually
 214     sensible.)  If there are any problems, raise a
 215     SymbolPlanException."""
 216
 217     if not isinstance(symbol, (Trunk, Branch, Tag, ExcludedSymbol)):
 218       raise IndeterminateSymbolException(self, symbol)
 219
 220     if symbol.id != self.lod.id:
 221       raise SymbolPlanException(self, symbol, 'IDs must match')
 222
 223     if symbol.project != self.lod.project:
 224       raise SymbolPlanException(self, symbol, 'Projects must match')
 225
 226     if isinstance(symbol, IncludedSymbol) and symbol.name != self.lod.name:
 227       raise SymbolPlanException(self, symbol, 'Names must match')
 228
 229   def check_preferred_parent_allowed(self, symbol):
 230     """Check that SYMBOL's preferred_parent_id is an allowed parent.
 231
 232     SYMBOL is the planned conversion of SELF.lod.  Verify that its
 233     preferred_parent_id is a possible parent of SELF.lod.  If not,
 234     raise a SymbolPlanException describing the problem."""
 235
 236     if isinstance(symbol, IncludedSymbol) \
 237            and symbol.preferred_parent_id is not None:
 238       for pp in self.possible_parents.keys():
 239         if pp.id == symbol.preferred_parent_id:
 240           return
 241       else:
 242         raise SymbolPlanException(
 243             self, symbol,
 244             'The selected parent is not among the symbol\'s '
 245             'possible parents.'
 246             )
 247
 248   def __str__(self):
 249     return (
 250         '\'%s\' is '
 251         'a tag in %d files, '
 252         'a branch in %d files, '
 253         'a trivial import in %d files, '
 254         'a pure import in %d files, '
 255         'and has commits in %d files'
 256         % (self.lod, self.tag_create_count, self.branch_create_count,
 257            self.trivial_import_count, self.pure_ntdb_count,
 258            self.branch_commit_count)
 259         )
 260
 261   def __repr__(self):
 262     retval = ['%s\n  possible parents:\n' % (self,)]
 263     parent_counts = self.possible_parents.items()
 264     parent_counts.sort(lambda a,b: - cmp(a[1], b[1]))
 265     for (symbol, count) in parent_counts:
 266       if isinstance(symbol, Trunk):
 267         retval.append('    trunk : %d\n' % count)
 268       else:
 269         retval.append('    \'%s\' : %d\n' % (symbol.name, count))
 270     if self.branch_blockers:
 271       blockers = list(self.branch_blockers)
 272       blockers.sort()
 273       retval.append('  blockers:\n')
 274       for blocker in blockers:
 275         retval.append('    \'%s\'\n' % (blocker,))
 276     return ''.join(retval)
 277
 278
 279 class SymbolStatisticsCollector:
 280   """Collect statistics about lines of development.
 281
 282   Record a summary of information about each line of development in
 283   the RCS files for later storage into a database.  The database is
 284   created in CollectRevsPass and it is used in CollateSymbolsPass (via
 285   the SymbolStatistics class).
 286
 287   collect_data._SymbolDataCollector inserts information into instances
 288   of this class by by calling its register_*() methods.
 289
 290   Its main purpose is to assist in the decisions about which symbols
 291   can be treated as branches and tags and which may be excluded.
 292
 293   The data collected by this class can be written to the file
 294   config.SYMBOL_STATISTICS."""
 295
 296   def __init__(self):
 297     # A map { lod -> _Stats } for all lines of development:
 298     self._stats = { }
 299
 300   def __getitem__(self, lod):
 301     """Return the _Stats record for line of development LOD.
 302
 303     Create and register a new one if necessary."""
 304
 305     try:
 306       return self._stats[lod]
 307     except KeyError:
 308       stats = _Stats(lod)
 309       self._stats[lod] = stats
 310       return stats
 311
 312   def register(self, cvs_file_items):
 313     """Register the statistics for each symbol in CVS_FILE_ITEMS."""
 314
 315     for lod_items in cvs_file_items.iter_lods():
 316       if lod_items.lod is not None:
 317         branch_stats = self[lod_items.lod]
 318
 319         branch_stats.register_branch_creation()
 320
 321         if lod_items.cvs_revisions:
 322           branch_stats.register_branch_commit()
 323
 324         if lod_items.is_trivial_import():
 325           branch_stats.register_trivial_import()
 326
 327         if lod_items.is_pure_ntdb():
 328           branch_stats.register_pure_ntdb()
 329
 330         for cvs_symbol in lod_items.iter_blockers():
 331           branch_stats.register_branch_blocker(cvs_symbol.symbol)
 332
 333         if lod_items.cvs_branch is not None:
 334           branch_stats.register_branch_possible_parents(
 335               lod_items.cvs_branch, cvs_file_items
 336               )
 337
 338       for cvs_tag in lod_items.cvs_tags:
 339         tag_stats = self[cvs_tag.symbol]
 340
 341         tag_stats.register_tag_creation()
 342
 343         tag_stats.register_tag_possible_parents(cvs_tag, cvs_file_items)
 344
 345   def purge_ghost_symbols(self):
 346     """Purge any symbols that don't have any activity.
 347
 348     Such ghost symbols can arise if a symbol was defined in an RCS
 349     file but pointed at a non-existent revision."""
 350
 351     for stats in self._stats.values():
 352       if stats.is_ghost():
 353         logger.warn('Deleting ghost symbol: %s' % (stats.lod,))
 354         del self._stats[stats.lod]
 355
 356   def close(self):
 357     """Store the stats database to the SYMBOL_STATISTICS file."""
 358
 359     f = open(artifact_manager.get_temp_file(config.SYMBOL_STATISTICS), 'wb')
 360     cPickle.dump(self._stats.values(), f, -1)
 361     f.close()
 362     self._stats = None
 363
 364
 365 class SymbolStatistics:
 366   """Read and handle line of development statistics.
 367
 368   The statistics are read from a database created by
 369   SymbolStatisticsCollector.  This class has methods to process the
 370   statistics information and help with decisions about:
 371
 372   1. What tags and branches should be processed/excluded
 373
 374   2. What tags should be forced to be branches and vice versa (this
 375      class maintains some statistics to help the user decide)
 376
 377   3. Are there inconsistencies?
 378
 379      - A symbol that is sometimes a branch and sometimes a tag
 380
 381      - A forced branch with commit(s) on it
 382
 383      - A non-excluded branch depends on an excluded branch
 384
 385   The data in this class is read from a pickle file."""
 386
 387   def __init__(self, filename):
 388     """Read the stats database from FILENAME."""
 389
 390     # A map { LineOfDevelopment -> _Stats } for all lines of
 391     # development:
 392     self._stats = { }
 393
 394     # A map { LineOfDevelopment.id -> _Stats } for all lines of
 395     # development:
 396     self._stats_by_id = { }
 397
 398     f = open(filename, 'rb')
 399     stats_list = cPickle.load(f)
 400     f.close()
 401
 402     for stats in stats_list:
 403       self._stats[stats.lod] = stats
 404       self._stats_by_id[stats.lod.id] = stats
 405
 406   def __len__(self):
 407     return len(self._stats)
 408
 409   def __getitem__(self, lod_id):
 410     return self._stats_by_id[lod_id]
 411
 412   def get_stats(self, lod):
 413     """Return the _Stats object for LineOfDevelopment instance LOD.
 414
 415     Raise KeyError if no such lod exists."""
 416
 417     return self._stats[lod]
 418
 419   def __iter__(self):
 420     return self._stats.itervalues()
 421
 422   def _check_blocked_excludes(self, symbol_map):
 423     """Check for any excluded LODs that are blocked by non-excluded symbols.
 424
 425     If any are found, describe the problem to logger.error() and raise
 426     a FatalException."""
 427
 428     # A list of (lod,[blocker,...]) tuples for excludes that are
 429     # blocked by the specified non-excluded blockers:
 430     problems = []
 431
 432     for lod in symbol_map.itervalues():
 433       if isinstance(lod, ExcludedSymbol):
 434         # Symbol is excluded; make sure that its blockers are also
 435         # excluded:
 436         lod_blockers = []
 437         for blocker in self.get_stats(lod).branch_blockers:
 438           if isinstance(symbol_map.get(blocker, None), IncludedSymbol):
 439             lod_blockers.append(blocker)
 440         if lod_blockers:
 441           problems.append((lod, lod_blockers))
 442
 443     if problems:
 444       s = []
 445       for (lod, lod_blockers) in problems:
 446         s.append(
 447             '%s: %s cannot be excluded because the following symbols '
 448                 'depend on it:\n'
 449             % (error_prefix, lod,)
 450             )
 451         for blocker in lod_blockers:
 452           s.append('    %s\n' % (blocker,))
 453       s.append('\n')
 454       logger.error(''.join(s))
 455
 456       raise FatalException()
 457
 458   def _check_invalid_tags(self, symbol_map):
 459     """Check for commits on any symbols that are to be converted as tags.
 460
 461     SYMBOL_MAP is a map {AbstractSymbol : (Trunk|TypedSymbol)}
 462     indicating how each AbstractSymbol is to be converted.  If there
 463     is a commit on a symbol, then it cannot be converted as a tag.  If
 464     any tags with commits are found, output error messages describing
 465     the problems then raise a FatalException."""
 466
 467     logger.quiet("Checking for forced tags with commits...")
 468
 469     invalid_tags = [ ]
 470     for symbol in symbol_map.itervalues():
 471       if isinstance(symbol, Tag):
 472         stats = self.get_stats(symbol)
 473         if stats.branch_commit_count > 0:
 474           invalid_tags.append(symbol)
 475
 476     if not invalid_tags:
 477       # No problems found:
 478       return
 479
 480     s = []
 481     s.append(
 482         '%s: The following branches cannot be forced to be tags '
 483         'because they have commits:\n'
 484         % (error_prefix,)
 485         )
 486     for tag in invalid_tags:
 487       s.append('    %s\n' % (tag.name))
 488     s.append('\n')
 489     logger.error(''.join(s))
 490
 491     raise FatalException()
 492
 493   def check_consistency(self, symbol_map):
 494     """Check the plan for how to convert symbols for consistency.
 495
 496     SYMBOL_MAP is a map {AbstractSymbol : (Trunk|TypedSymbol)}
 497     indicating how each AbstractSymbol is to be converted.  If any
 498     problems are detected, describe the problem to logger.error() and
 499     raise a FatalException."""
 500
 501     # We want to do all of the consistency checks even if one of them
 502     # fails, so that the user gets as much feedback as possible.  Set
 503     # this variable to True if any errors are found.
 504     error_found = False
 505
 506     # Check that the planned preferred parents are OK for all
 507     # IncludedSymbols:
 508     for lod in symbol_map.itervalues():
 509       if isinstance(lod, IncludedSymbol):
 510         stats = self.get_stats(lod)
 511         try:
 512           stats.check_preferred_parent_allowed(lod)
 513         except SymbolPlanException, e:
 514           logger.error('%s\n' % (e,))
 515           error_found = True
 516
 517     try:
 518       self._check_blocked_excludes(symbol_map)
 519     except FatalException:
 520       error_found = True
 521
 522     try:
 523       self._check_invalid_tags(symbol_map)
 524     except FatalException:
 525       error_found = True
 526
 527     if error_found:
 528       raise FatalException(
 529           'Please fix the above errors and restart CollateSymbolsPass'
 530           )
 531
 532   def exclude_symbol(self, symbol):
 533     """SYMBOL has been excluded; remove it from our statistics."""
 534
 535     del self._stats[symbol]
 536     del self._stats_by_id[symbol.id]
 537
 538     # Remove references to this symbol from other statistics objects:
 539     for stats in self._stats.itervalues():
 540       stats.branch_blockers.discard(symbol)
 541       if symbol in stats.possible_parents:
 542         del stats.possible_parents[symbol]
 543
 544