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