cvs2svn_lib/changeset_graph_link.py

   1 # (Be in -*- python -*- mode.)
   2 #
   3 # ====================================================================
   4 # Copyright (c) 2006-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 """Keep track of counts of different types of changeset links."""
  18
  19
  20
  21 # A cvs_item doesn't depend on any cvs_items in either pred or succ:
  22 LINK_NONE = 0
  23
  24 # A cvs_item depends on one or more cvs_items in pred but none in succ:
  25 LINK_PRED = 1
  26
  27 # A cvs_item depends on one or more cvs_items in succ but none in pred:
  28 LINK_SUCC = 2
  29
  30 # A cvs_item depends on one or more cvs_items in both pred and succ:
  31 LINK_PASSTHRU = LINK_PRED | LINK_SUCC
  32
  33
  34 class ChangesetGraphLink(object):
  35   def __init__(self, pred, changeset, succ):
  36     """Represent a link in a loop in a changeset graph.
  37
  38     This is the link that goes from PRED -> CHANGESET -> SUCC.
  39
  40     We are mainly concerned with how many CVSItems have LINK_PRED,
  41     LINK_SUCC, and LINK_PASSTHRU type links to the neighboring
  42     commitsets.  If necessary, this class can also break up CHANGESET
  43     into multiple changesets."""
  44
  45     self.pred = pred
  46     self.pred_ids = set(pred.cvs_item_ids)
  47
  48     self.changeset = changeset
  49
  50     self.succ_ids = set(succ.cvs_item_ids)
  51     self.succ = succ
  52
  53     # A count of each type of link for cvs_items in changeset
  54     # (indexed by LINK_* constants):
  55     link_counts = [0] * 4
  56
  57     for cvs_item in list(changeset.iter_cvs_items()):
  58       link_counts[self.get_link_type(cvs_item)] += 1
  59
  60     [self.pred_links, self.succ_links, self.passthru_links] = link_counts[1:]
  61
  62   def get_link_type(self, cvs_item):
  63     """Return the type of links from CVS_ITEM to self.PRED and self.SUCC.
  64
  65     The return value is one of LINK_NONE, LINK_PRED, LINK_SUCC, or
  66     LINK_PASSTHRU."""
  67
  68     retval = LINK_NONE
  69
  70     if cvs_item.get_pred_ids() & self.pred_ids:
  71       retval |= LINK_PRED
  72     if cvs_item.get_succ_ids() & self.succ_ids:
  73       retval |= LINK_SUCC
  74
  75     return retval
  76
  77   def get_links_to_move(self):
  78     """Return the number of items that would be moved to split changeset."""
  79
  80     return min(self.pred_links, self.succ_links) \
  81            or max(self.pred_links, self.succ_links)
  82
  83   def is_breakable(self):
  84     """Return True iff breaking the changeset will do any good."""
  85
  86     return self.pred_links != 0 or self.succ_links != 0
  87
  88   def __cmp__(self, other):
  89     """Compare SELF with OTHER in terms of which would be better to break.
  90
  91     The one that is better to break is considered the lesser."""
  92
  93     return (
  94         - cmp(int(self.is_breakable()), int(other.is_breakable()))
  95         or cmp(self.passthru_links, other.passthru_links)
  96         or cmp(self.get_links_to_move(), other.get_links_to_move())
  97         )
  98
  99   def break_changeset(self, changeset_key_generator):
 100     """Break up self.changeset and return the fragments.
 101
 102     Break it up in such a way that the link is weakened as efficiently
 103     as possible."""
 104
 105     if not self.is_breakable():
 106       raise ValueError('Changeset is not breakable: %r' % self.changeset)
 107
 108     pred_items = []
 109     succ_items = []
 110
 111     # For each link type, should such CVSItems be moved to the
 112     # changeset containing the predecessor items or the one containing
 113     # the successor items?
 114     destination = {
 115         LINK_PRED : pred_items,
 116         LINK_SUCC : succ_items,
 117         }
 118
 119     if self.pred_links == 0:
 120       destination[LINK_NONE] = pred_items
 121       destination[LINK_PASSTHRU] = pred_items
 122     elif self.succ_links == 0:
 123       destination[LINK_NONE] = succ_items
 124       destination[LINK_PASSTHRU] = succ_items
 125     elif self.pred_links < self.succ_links:
 126       destination[LINK_NONE] = succ_items
 127       destination[LINK_PASSTHRU] = succ_items
 128     else:
 129       destination[LINK_NONE] = pred_items
 130       destination[LINK_PASSTHRU] = pred_items
 131
 132     for cvs_item in self.changeset.iter_cvs_items():
 133       link_type = self.get_link_type(cvs_item)
 134       destination[link_type].append(cvs_item.id)
 135
 136     # Create new changesets of the same type as the old one:
 137     return [
 138         self.changeset.create_split_changeset(
 139             changeset_key_generator.gen_id(), pred_items),
 140         self.changeset.create_split_changeset(
 141             changeset_key_generator.gen_id(), succ_items),
 142         ]
 143
 144   def __str__(self):
 145     return 'Link<%x>(%d, %d, %d)' % (
 146         self.changeset.id,
 147         self.pred_links, self.succ_links, self.passthru_links)
 148
 149