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     # Branches that are rooted at the same revision are also
 185     # possible parents:
 186     for branch_id in parent_cvs_rev.branch_ids:
 187       parent_symbol = cvs_file_items[branch_id].symbol
 188       register(parent_symbol)
 189
 190   def is_ghost(self):
 191     """Return True iff this lod never really existed."""
 192
 193     return (
 194         not isinstance(self.lod, Trunk)
 195         and self.branch_commit_count == 0
 196         and not self.branch_blockers
 197         and not self.possible_parents
 198         )
 199
 200   def check_valid(self, symbol):
 201     """Check whether SYMBOL is a valid conversion of SELF.lod.
 202
 203     It is planned to convert SELF.lod as SYMBOL.  Verify that SYMBOL
 204     is a TypedSymbol and that the information that it contains is
 205     consistent with that stored in SELF.lod.  (This routine does not
 206     do higher-level tests of whether the chosen conversion is actually
 207     sensible.)  If there are any problems, raise a
 208     SymbolPlanException."""
 209
 210     if not isinstance(symbol, (Trunk, Branch, Tag, ExcludedSymbol)):
 211       raise IndeterminateSymbolException(self, symbol)
 212
 213     if symbol.id != self.lod.id:
 214       raise SymbolPlanException(self, symbol, 'IDs must match')
 215
 216     if symbol.project != self.lod.project:
 217       raise SymbolPlanException(self, symbol, 'Projects must match')
 218
 219     if isinstance(symbol, IncludedSymbol) and symbol.name != self.lod.name:
 220       raise SymbolPlanException(self, symbol, 'Names must match')
 221
 222   def check_preferred_parent_allowed(self, symbol):
 223     """Check that SYMBOL's preferred_parent_id is an allowed parent.
 224
 225     SYMBOL is the planned conversion of SELF.lod.  Verify that its
 226     preferred_parent_id is a possible parent of SELF.lod.  If not,
 227     raise a SymbolPlanException describing the problem."""
 228
 229     if isinstance(symbol, IncludedSymbol) \
 230            and symbol.preferred_parent_id is not None:
 231       for pp in self.possible_parents.keys():
 232         if pp.id == symbol.preferred_parent_id:
 233           return
 234       else:
 235         raise SymbolPlanException(
 236             self, symbol,
 237             'The selected parent is not among the symbol\'s '
 238             'possible parents.'
 239             )
 240
 241   def __str__(self):
 242     return (
 243         '\'%s\' is '
 244         'a tag in %d files, '
 245         'a branch in %d files, '
 246         'a trivial import in %d files, '
 247         'a pure import in %d files, '
 248         'and has commits in %d files'
 249         % (self.lod, self.tag_create_count, self.branch_create_count,
 250            self.trivial_import_count, self.pure_ntdb_count,
 251            self.branch_commit_count)
 252         )
 253
 254   def __repr__(self):
 255     retval = ['%s\n  possible parents:\n' % (self,)]
 256     parent_counts = self.possible_parents.items()
 257     parent_counts.sort(lambda a,b: - cmp(a[1], b[1]))
 258     for (symbol, count) in parent_counts:
 259       if isinstance(symbol, Trunk):
 260         retval.append('    trunk : %d\n' % count)
 261       else:
 262         retval.append('    \'%s\' : %d\n' % (symbol.name, count))
 263     if self.branch_blockers:
 264       blockers = list(self.branch_blockers)
 265       blockers.sort()
 266       retval.append('  blockers:\n')
 267       for blocker in blockers:
 268         retval.append('    \'%s\'\n' % (blocker,))
 269     return ''.join(retval)
 270
 271
 272 class SymbolStatisticsCollector:
 273   """Collect statistics about lines of development.
 274
 275   Record a summary of information about each line of development in
 276   the RCS files for later storage into a database.  The database is
 277   created in CollectRevsPass and it is used in CollateSymbolsPass (via
 278   the SymbolStatistics class).
 279
 280   collect_data._SymbolDataCollector inserts information into instances
 281   of this class by by calling its register_*() methods.
 282
 283   Its main purpose is to assist in the decisions about which symbols
 284   can be treated as branches and tags and which may be excluded.
 285
 286   The data collected by this class can be written to the file
 287   config.SYMBOL_STATISTICS."""
 288
 289   def __init__(self):
 290     # A map { lod -> _Stats } for all lines of development:
 291     self._stats = { }
 292
 293   def __getitem__(self, lod):
 294     """Return the _Stats record for line of development LOD.
 295
 296     Create and register a new one if necessary."""
 297
 298     try:
 299       return self._stats[lod]
 300     except KeyError:
 301       stats = _Stats(lod)
 302       self._stats[lod] = stats
 303       return stats
 304
 305   def register(self, cvs_file_items):
 306     """Register the statistics for each symbol in CVS_FILE_ITEMS."""
 307
 308     for lod_items in cvs_file_items.iter_lods():
 309       if lod_items.lod is not None:
 310         branch_stats = self[lod_items.lod]
 311
 312         branch_stats.register_branch_creation()
 313
 314         if lod_items.cvs_revisions:
 315           branch_stats.register_branch_commit()
 316
 317         if lod_items.is_trivial_import():
 318           branch_stats.register_trivial_import()
 319
 320         if lod_items.is_pure_ntdb():
 321           branch_stats.register_pure_ntdb()
 322
 323         for cvs_symbol in lod_items.iter_blockers():
 324           branch_stats.register_branch_blocker(cvs_symbol.symbol)
 325
 326         if lod_items.cvs_branch is not None:
 327           branch_stats.register_branch_possible_parents(
 328               lod_items.cvs_branch, cvs_file_items
 329               )
 330
 331       for cvs_tag in lod_items.cvs_tags:
 332         tag_stats = self[cvs_tag.symbol]
 333
 334         tag_stats.register_tag_creation()
 335
 336         tag_stats.register_tag_possible_parents(cvs_tag, cvs_file_items)
 337
 338   def purge_ghost_symbols(self):
 339     """Purge any symbols that don't have any activity.
 340
 341     Such ghost symbols can arise if a symbol was defined in an RCS
 342     file but pointed at a non-existent revision."""
 343
 344     for stats in self._stats.values():
 345       if stats.is_ghost():
 346         logger.warn('Deleting ghost symbol: %s' % (stats.lod,))
 347         del self._stats[stats.lod]
 348
 349   def close(self):
 350     """Store the stats database to the SYMBOL_STATISTICS file."""
 351
 352     f = open(artifact_manager.get_temp_file(config.SYMBOL_STATISTICS), 'wb')
 353     cPickle.dump(self._stats.values(), f, -1)
 354     f.close()
 355     self._stats = None
 356
 357
 358 class SymbolStatistics:
 359   """Read and handle line of development statistics.
 360
 361   The statistics are read from a database created by
 362   SymbolStatisticsCollector.  This class has methods to process the
 363   statistics information and help with decisions about:
 364
 365   1. What tags and branches should be processed/excluded
 366
 367   2. What tags should be forced to be branches and vice versa (this
 368      class maintains some statistics to help the user decide)
 369
 370   3. Are there inconsistencies?
 371
 372      - A symbol that is sometimes a branch and sometimes a tag
 373
 374      - A forced branch with commit(s) on it
 375
 376      - A non-excluded branch depends on an excluded branch
 377
 378   The data in this class is read from a pickle file."""
 379
 380   def __init__(self, filename):
 381     """Read the stats database from FILENAME."""
 382
 383     # A map { LineOfDevelopment -> _Stats } for all lines of
 384     # development:
 385     self._stats = { }
 386
 387     # A map { LineOfDevelopment.id -> _Stats } for all lines of
 388     # development:
 389     self._stats_by_id = { }
 390
 391     stats_list = cPickle.load(open(filename, 'rb'))
 392
 393     for stats in stats_list:
 394       self._stats[stats.lod] = stats
 395       self._stats_by_id[stats.lod.id] = stats
 396
 397   def __len__(self):
 398     return len(self._stats)
 399
 400   def __getitem__(self, lod_id):
 401     return self._stats_by_id[lod_id]
 402
 403   def get_stats(self, lod):
 404     """Return the _Stats object for LineOfDevelopment instance LOD.
 405
 406     Raise KeyError if no such lod exists."""
 407
 408     return self._stats[lod]
 409
 410   def __iter__(self):
 411     return self._stats.itervalues()
 412
 413   def _check_blocked_excludes(self, symbol_map):
 414     """Check for any excluded LODs that are blocked by non-excluded symbols.
 415
 416     If any are found, describe the problem to logger.error() and raise
 417     a FatalException."""
 418
 419     # A list of (lod,[blocker,...]) tuples for excludes that are
 420     # blocked by the specified non-excluded blockers:
 421     problems = []
 422
 423     for lod in symbol_map.itervalues():
 424       if isinstance(lod, ExcludedSymbol):
 425         # Symbol is excluded; make sure that its blockers are also
 426         # excluded:
 427         lod_blockers = []
 428         for blocker in self.get_stats(lod).branch_blockers:
 429           if isinstance(symbol_map.get(blocker, None), IncludedSymbol):
 430             lod_blockers.append(blocker)
 431         if lod_blockers:
 432           problems.append((lod, lod_blockers))
 433
 434     if problems:
 435       s = []
 436       for (lod, lod_blockers) in problems:
 437         s.append(
 438             '%s: %s cannot be excluded because the following symbols '
 439                 'depend on it:\n'
 440             % (error_prefix, lod,)
 441             )
 442         for blocker in lod_blockers:
 443           s.append('    %s\n' % (blocker,))
 444       s.append('\n')
 445       logger.error(''.join(s))
 446
 447       raise FatalException()
 448
 449   def _check_invalid_tags(self, symbol_map):
 450     """Check for commits on any symbols that are to be converted as tags.
 451
 452     SYMBOL_MAP is a map {AbstractSymbol : (Trunk|TypedSymbol)}
 453     indicating how each AbstractSymbol is to be converted.  If there
 454     is a commit on a symbol, then it cannot be converted as a tag.  If
 455     any tags with commits are found, output error messages describing
 456     the problems then raise a FatalException."""
 457
 458     logger.quiet("Checking for forced tags with commits...")
 459
 460     invalid_tags = [ ]
 461     for symbol in symbol_map.itervalues():
 462       if isinstance(symbol, Tag):
 463         stats = self.get_stats(symbol)
 464         if stats.branch_commit_count > 0:
 465           invalid_tags.append(symbol)
 466
 467     if not invalid_tags:
 468       # No problems found:
 469       return
 470
 471     s = []
 472     s.append(
 473         '%s: The following branches cannot be forced to be tags '
 474         'because they have commits:\n'
 475         % (error_prefix,)
 476         )
 477     for tag in invalid_tags:
 478       s.append('    %s\n' % (tag.name))
 479     s.append('\n')
 480     logger.error(''.join(s))
 481
 482     raise FatalException()
 483
 484   def check_consistency(self, symbol_map):
 485     """Check the plan for how to convert symbols for consistency.
 486
 487     SYMBOL_MAP is a map {AbstractSymbol : (Trunk|TypedSymbol)}
 488     indicating how each AbstractSymbol is to be converted.  If any
 489     problems are detected, describe the problem to logger.error() and
 490     raise a FatalException."""
 491
 492     # We want to do all of the consistency checks even if one of them
 493     # fails, so that the user gets as much feedback as possible.  Set
 494     # this variable to True if any errors are found.
 495     error_found = False
 496
 497     # Check that the planned preferred parents are OK for all
 498     # IncludedSymbols:
 499     for lod in symbol_map.itervalues():
 500       if isinstance(lod, IncludedSymbol):
 501         stats = self.get_stats(lod)
 502         try:
 503           stats.check_preferred_parent_allowed(lod)
 504         except SymbolPlanException, e:
 505           logger.error('%s\n' % (e,))
 506           error_found = True
 507
 508     try:
 509       self._check_blocked_excludes(symbol_map)
 510     except FatalException:
 511       error_found = True
 512
 513     try:
 514       self._check_invalid_tags(symbol_map)
 515     except FatalException:
 516       error_found = True
 517
 518     if error_found:
 519       raise FatalException(
 520           'Please fix the above errors and restart CollateSymbolsPass'
 521           )
 522
 523   def exclude_symbol(self, symbol):
 524     """SYMBOL has been excluded; remove it from our statistics."""
 525
 526     del self._stats[symbol]
 527     del self._stats_by_id[symbol.id]
 528
 529     # Remove references to this symbol from other statistics objects:
 530     for stats in self._stats.itervalues():
 531       stats.branch_blockers.discard(symbol)
 532       if symbol in stats.possible_parents:
 533         del stats.possible_parents[symbol]
 534
 535