cvs2svn_lib/symbolic_name_filling_guide.py

   1 # (Be in -*- python -*- mode.)
   2 #
   3 # ====================================================================
   4 # Copyright (c) 2000-2006 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 contains database facilities used by cvs2svn."""
  18
  19
  20 from boolean import *
  21 import common
  22 from common import FatalError
  23 from context import Ctx
  24 from svn_revision_range import SVNRevisionRange
  25 from fill_source import FillSource
  26
  27
  28 class SymbolicNameFillingGuide:
  29   """A node tree representing the source paths to be copied to fill
  30   self.symbolic_name in the current SVNCommit.
  31
  32   self._node_tree is the root of the directory tree, in the form {
  33   path_component : subnode }.  Leaf nodes are instances of
  34   SVNRevisionRange.  Intermediate (directory) nodes are dictionaries
  35   mapping relative names to subnodes.
  36
  37   By walking self._node_tree and calling self.get_best_revnum() on
  38   each node, the caller can determine what subversion revision number
  39   to copy the path corresponding to that node from.  self._node_tree
  40   should be treated as read-only.
  41
  42   The caller can then descend to sub-nodes to see if their "best
  43   revnum" differs from their parents' and if it does, take appropriate
  44   actions to "patch up" the subtrees."""
  45
  46   def __init__(self, openings_closings_map):
  47     """Initializes a SymbolicNameFillingGuide for SYMBOLIC_NAME and
  48     store into it the openings and closings from
  49     OPENINGS_CLOSINGS_MAP."""
  50
  51     self.name = openings_closings_map.name
  52
  53     # The dictionary that holds our node tree as a map { node_key :
  54     # node }.
  55     self._node_tree = { }
  56
  57     for svn_path, svn_revision_range in openings_closings_map.get_things():
  58       (head, tail) = common.path_split(svn_path)
  59       self._get_node_for_path(head)[tail] = svn_revision_range
  60
  61     #self.print_node_tree(self._node_tree)
  62
  63   def _get_node_for_path(self, svn_path):
  64     """Return the node key for svn_path, creating new nodes as needed."""
  65
  66     # Walk down the path, one node at a time.
  67     node = self._node_tree
  68     for component in svn_path.split('/'):
  69       if node.has_key(component):
  70         node = node[component]
  71       else:
  72         old_node = node
  73         node = {}
  74         old_node[component] = node
  75
  76     return node
  77
  78   def get_best_revnum(self, node, preferred_revnum):
  79     """Determine the best subversion revision number to use when
  80     copying the source tree beginning at NODE.  Returns a
  81     subversion revision number.
  82
  83     PREFERRED_REVNUM is passed to best_rev and used to calculate the
  84     best_revnum."""
  85
  86     def score_revisions(svn_revision_ranges):
  87       """Return a list of revisions and scores based on
  88       SVN_REVISION_RANGES.  The returned list looks like:
  89
  90          [(REV1 SCORE1), (REV2 SCORE2), ...]
  91
  92       where the tuples are sorted by revision number.
  93       SVN_REVISION_RANGES is a list of SVNRevisionRange objects.
  94
  95       For each svn revision that appears as either an opening_revnum
  96       or closing_revnum for one of the svn_revision_ranges, output a
  97       tuple indicating how many of the SVNRevisionRanges include that
  98       svn_revision in its range.  A score thus indicates that copying
  99       the corresponding revision (or any following revision up to the
 100       next revision in the list) of the object in question would yield
 101       that many correct paths at or underneath the object.  There may
 102       be other paths underneath it which are not correct and would
 103       need to be deleted or recopied; those can only be detected by
 104       descending and examining their scores.
 105
 106       If OPENINGS is empty, return the empty list."""
 107
 108       openings = [ x.opening_revnum
 109                    for x in svn_revision_ranges ]
 110       closings = [ x.closing_revnum
 111                    for x in svn_revision_ranges
 112                    if x.closing_revnum is not None ]
 113
 114       # First look for easy out.
 115       if not openings:
 116         return []
 117
 118       # Create a list with both openings (which increment the total)
 119       # and closings (which decrement the total):
 120       things = [(rev,1) for rev in openings] + [(rev,-1) for rev in closings]
 121       # Sort by revision number:
 122       things.sort()
 123       # Initialize output list with zeroth element of things.  This
 124       # element must exist, because it was already verified that
 125       # openings is not empty.
 126       scores = [ things[0] ]
 127       total = scores[-1][1]
 128       for (rev, change) in things[1:]:
 129         total += change
 130         if rev == scores[-1][0]:
 131           # Same revision as last entry; modify last entry:
 132           scores[-1] = (rev, total)
 133         else:
 134           # Previously-unseen revision; create new entry:
 135           scores.append((rev, total))
 136       return scores
 137
 138     def best_rev(scores, preferred_rev):
 139       """Return the revision with the highest score from SCORES, a list
 140       returned by score_revisions().  When the maximum score is shared
 141       by multiple revisions, the oldest revision is selected, unless
 142       PREFERRED_REV is one of the possibilities, in which case, it is
 143       selected."""
 144
 145       max_score = 0
 146       preferred_rev_score = -1
 147       rev = common.SVN_INVALID_REVNUM
 148       if preferred_rev is None:
 149         # Comparison order of different types is arbitrary.  Do not
 150         # expect None to compare less than int values below.
 151         preferred_rev = common.SVN_INVALID_REVNUM
 152       for revnum, count in scores:
 153         if count > max_score:
 154           max_score = count
 155           rev = revnum
 156         if revnum <= preferred_rev:
 157           preferred_rev_score = count
 158       if preferred_rev_score == max_score:
 159         rev = preferred_rev
 160       return rev, max_score
 161
 162     # Aggregate openings and closings from the rev tree
 163     svn_revision_ranges = self._list_revnums(node)
 164
 165     # Score the lists
 166     scores = score_revisions(svn_revision_ranges)
 167
 168     revnum, max_score = best_rev(scores, preferred_revnum)
 169
 170     if revnum == common.SVN_INVALID_REVNUM:
 171       raise FatalError(
 172           "failed to find a revision to copy from when copying %s"
 173           % self.name)
 174     return revnum, max_score
 175
 176   def _list_revnums(self, node):
 177     """Return a list of all the SVNRevisionRanges (including
 178     duplicates) for all leaf nodes at and under NODE."""
 179
 180     if isinstance(node, SVNRevisionRange):
 181       # It is a leaf node.
 182       return [ node ]
 183     else:
 184       # It is an intermediate node.
 185       revnums = []
 186       for key, subnode in node.items():
 187         revnums.extend(self._list_revnums(subnode))
 188       return revnums
 189
 190   def get_sources(self):
 191     """Return the list of sources for this symbolic name.
 192
 193     The Project instance defines what are legitimate sources.  Raise
 194     an exception if a change occurred outside of the source
 195     directories."""
 196
 197     return self._get_sub_sources('', self._node_tree)
 198
 199   def _get_sub_sources(self, start_svn_path, start_node):
 200     """Return the list of sources for this symbolic name, starting the
 201     search at path START_SVN_PATH, which is node START_NODE.  This is
 202     a helper method, called by get_sources() (see)."""
 203
 204     project = Ctx().project
 205     if isinstance(start_node, SVNRevisionRange):
 206       # This implies that a change was found outside of the
 207       # legitimate sources.  This should never happen.
 208       raise
 209     elif project.is_source(start_svn_path):
 210       # This is a legitimate source.  Add it to list.
 211       return [ FillSource(start_svn_path, start_node) ]
 212     else:
 213       # This is a directory that is not a legitimate source.  (That's
 214       # OK because it hasn't changed directly.)  But directories
 215       # within it have been changed, so we need to search recursively
 216       # to find their enclosing sources.
 217       sources = []
 218       for entry, node in start_node.items():
 219         svn_path = common.path_join(start_svn_path, entry)
 220         sources.extend(self._get_sub_sources(svn_path, node))
 221
 222     return sources
 223
 224   def print_node_tree(self, node, name='/', indent_depth=0):
 225     """For debugging purposes.  Prints all nodes in TREE that are
 226     rooted at NODE.  INDENT_DEPTH is used to indent the output of
 227     recursive calls."""
 228
 229     if not indent_depth:
 230       print "TREE", "=" * 75
 231     if isinstance(node, SVNRevisionRange):
 232       print "TREE:", " " * (indent_depth * 2), name, node
 233     else:
 234       print "TREE:", " " * (indent_depth * 2), name
 235       for key, value in node.items():
 236         self.print_node_tree(value, key, (indent_depth + 1))
 237
 238