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     stats_list = cPickle.load(open(filename, 'rb'))
 399
 400     for stats in stats_list:
 401       self._stats[stats.lod] = stats
 402       self._stats_by_id[stats.lod.id] = stats
 403
 404   def __len__(self):
 405     return len(self._stats)
 406
 407   def __getitem__(self, lod_id):
 408     return self._stats_by_id[lod_id]
 409
 410   def get_stats(self, lod):
 411     """Return the _Stats object for LineOfDevelopment instance LOD.
 412
 413     Raise KeyError if no such lod exists."""
 414
 415     return self._stats[lod]
 416
 417   def __iter__(self):
 418     return self._stats.itervalues()
 419
 420   def _check_blocked_excludes(self, symbol_map):
 421     """Check for any excluded LODs that are blocked by non-excluded symbols.
 422
 423     If any are found, describe the problem to logger.error() and raise
 424     a FatalException."""
 425
 426     # A list of (lod,[blocker,...]) tuples for excludes that are
 427     # blocked by the specified non-excluded blockers:
 428     problems = []
 429
 430     for lod in symbol_map.itervalues():
 431       if isinstance(lod, ExcludedSymbol):
 432         # Symbol is excluded; make sure that its blockers are also
 433         # excluded:
 434         lod_blockers = []
 435         for blocker in self.get_stats(lod).branch_blockers:
 436           if isinstance(symbol_map.get(blocker, None), IncludedSymbol):
 437             lod_blockers.append(blocker)
 438         if lod_blockers:
 439           problems.append((lod, lod_blockers))
 440
 441     if problems:
 442       s = []
 443       for (lod, lod_blockers) in problems:
 444         s.append(
 445             '%s: %s cannot be excluded because the following symbols '
 446                 'depend on it:\n'
 447             % (error_prefix, lod,)
 448             )
 449         for blocker in lod_blockers:
 450           s.append('    %s\n' % (blocker,))
 451       s.append('\n')
 452       logger.error(''.join(s))
 453
 454       raise FatalException()
 455
 456   def _check_invalid_tags(self, symbol_map):
 457     """Check for commits on any symbols that are to be converted as tags.
 458
 459     SYMBOL_MAP is a map {AbstractSymbol : (Trunk|TypedSymbol)}
 460     indicating how each AbstractSymbol is to be converted.  If there
 461     is a commit on a symbol, then it cannot be converted as a tag.  If
 462     any tags with commits are found, output error messages describing
 463     the problems then raise a FatalException."""
 464
 465     logger.quiet("Checking for forced tags with commits...")
 466
 467     invalid_tags = [ ]
 468     for symbol in symbol_map.itervalues():
 469       if isinstance(symbol, Tag):
 470         stats = self.get_stats(symbol)
 471         if stats.branch_commit_count > 0:
 472           invalid_tags.append(symbol)
 473
 474     if not invalid_tags:
 475       # No problems found:
 476       return
 477
 478     s = []
 479     s.append(
 480         '%s: The following branches cannot be forced to be tags '
 481         'because they have commits:\n'
 482         % (error_prefix,)
 483         )
 484     for tag in invalid_tags:
 485       s.append('    %s\n' % (tag.name))
 486     s.append('\n')
 487     logger.error(''.join(s))
 488
 489     raise FatalException()
 490
 491   def check_consistency(self, symbol_map):
 492     """Check the plan for how to convert symbols for consistency.
 493
 494     SYMBOL_MAP is a map {AbstractSymbol : (Trunk|TypedSymbol)}
 495     indicating how each AbstractSymbol is to be converted.  If any
 496     problems are detected, describe the problem to logger.error() and
 497     raise a FatalException."""
 498
 499     # We want to do all of the consistency checks even if one of them
 500     # fails, so that the user gets as much feedback as possible.  Set
 501     # this variable to True if any errors are found.
 502     error_found = False
 503
 504     # Check that the planned preferred parents are OK for all
 505     # IncludedSymbols:
 506     for lod in symbol_map.itervalues():
 507       if isinstance(lod, IncludedSymbol):
 508         stats = self.get_stats(lod)
 509         try:
 510           stats.check_preferred_parent_allowed(lod)
 511         except SymbolPlanException, e:
 512           logger.error('%s\n' % (e,))
 513           error_found = True
 514
 515     try:
 516       self._check_blocked_excludes(symbol_map)
 517     except FatalException:
 518       error_found = True
 519
 520     try:
 521       self._check_invalid_tags(symbol_map)
 522     except FatalException:
 523       error_found = True
 524
 525     if error_found:
 526       raise FatalException(
 527           'Please fix the above errors and restart CollateSymbolsPass'
 528           )
 529
 530   def exclude_symbol(self, symbol):
 531     """SYMBOL has been excluded; remove it from our statistics."""
 532
 533     del self._stats[symbol]
 534     del self._stats_by_id[symbol.id]
 535
 536     # Remove references to this symbol from other statistics objects:
 537     for stats in self._stats.itervalues():
 538       stats.branch_blockers.discard(symbol)
 539       if symbol in stats.possible_parents:
 540         del stats.possible_parents[symbol]
 541
 542