cvs2svn_lib/svn_revision_range.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 contains the SVNRevisionRange class."""
  18
  19
  20 import bisect
  21
  22 from cvs2svn_lib.common import SVN_INVALID_REVNUM
  23
  24
  25 class SVNRevisionRange:
  26   """The range of subversion revision numbers from which a path can be
  27   copied.  self.opening_revnum is the number of the earliest such
  28   revision, and self.closing_revnum is one higher than the number of
  29   the last such revision.  If self.closing_revnum is None, then no
  30   closings were registered."""
  31
  32   def __init__(self, source_lod, opening_revnum):
  33     self.source_lod = source_lod
  34     self.opening_revnum = opening_revnum
  35     self.closing_revnum = None
  36
  37   def add_closing(self, closing_revnum):
  38     # When we have a non-trunk default branch, we may have multiple
  39     # closings--only register the first closing we encounter.
  40     if self.closing_revnum is None:
  41       self.closing_revnum = closing_revnum
  42
  43   def __contains__(self, revnum):
  44     """Return True iff REVNUM is contained in the range."""
  45
  46     return (
  47         self.opening_revnum <= revnum \
  48         and (self.closing_revnum is None or revnum < self.closing_revnum)
  49         )
  50
  51   def __str__(self):
  52     if self.closing_revnum is None:
  53       return '[%d:]' % (self.opening_revnum,)
  54     else:
  55       return '[%d:%d]' % (self.opening_revnum, self.closing_revnum,)
  56
  57   def __repr__(self):
  58     return str(self)
  59
  60
  61 class RevisionScores:
  62   """Represent the scores for a range of revisions."""
  63
  64   def __init__(self, svn_revision_ranges):
  65     """Initialize based on SVN_REVISION_RANGES.
  66
  67     SVN_REVISION_RANGES is a list of SVNRevisionRange objects.
  68
  69     The score of an svn source is defined to be the number of
  70     SVNRevisionRanges on that LOD that include the revision.  A score
  71     thus indicates that copying the corresponding revision (or any
  72     following revision up to the next revision in the list) of the
  73     object in question would yield that many correct paths at or
  74     underneath the object.  There may be other paths underneath it
  75     that are not correct and would need to be deleted or recopied;
  76     those can only be detected by descending and examining their
  77     scores.
  78
  79     If SVN_REVISION_RANGES is empty, then all scores are undefined."""
  80
  81     deltas_map = {}
  82
  83     for range in svn_revision_ranges:
  84       source_lod = range.source_lod
  85       try:
  86         deltas = deltas_map[source_lod]
  87       except:
  88         deltas = []
  89         deltas_map[source_lod] = deltas
  90       deltas.append((range.opening_revnum, +1))
  91       if range.closing_revnum is not None:
  92         deltas.append((range.closing_revnum, -1))
  93
  94     # A map:
  95     #
  96     #    {SOURCE_LOD : [(REV1 SCORE1), (REV2 SCORE2), (REV3 SCORE3), ...]}
  97     #
  98     # where the tuples are sorted by revision number and the revision
  99     # numbers are distinct.  Score is the number of correct paths that
 100     # would result from using the specified SOURCE_LOD and revision
 101     # number (or any other revision preceding the next revision
 102     # listed) as a source.  For example, the score of any revision REV
 103     # in the range REV2 <= REV < REV3 is equal to SCORE2.
 104     self._scores_map = {}
 105
 106     for (source_lod,deltas) in deltas_map.items():
 107       # Sort by revision number:
 108       deltas.sort()
 109
 110       # Initialize output list with zeroth element of deltas.  This
 111       # element must exist, because it was verified that
 112       # svn_revision_ranges (and therefore openings) is not empty.
 113       scores = [ deltas[0] ]
 114       total = deltas[0][1]
 115       for (rev, change) in deltas[1:]:
 116         total += change
 117         if rev == scores[-1][0]:
 118           # Same revision as last entry; modify last entry:
 119           scores[-1] = (rev, total)
 120         else:
 121           # Previously-unseen revision; create new entry:
 122           scores.append((rev, total))
 123       self._scores_map[source_lod] = scores
 124
 125   def get_score(self, range):
 126     """Return the score for RANGE's opening revision.
 127
 128     If RANGE doesn't appear explicitly in self.scores, use the score
 129     of the higest revision preceding RANGE.  If there are no preceding
 130     revisions, then the score for RANGE is unknown; in this case,
 131     return -1."""
 132
 133     try:
 134       scores = self._scores_map[range.source_lod]
 135     except KeyError:
 136       return -1
 137
 138     # Remember, according to the tuple sorting rules,
 139     #
 140     #    (revnum, anything,) < (revnum+1,) < (revnum+1, anything,)
 141     predecessor_index = bisect.bisect_right(
 142         scores, (range.opening_revnum + 1,)
 143         ) - 1
 144
 145     if predecessor_index < 0:
 146       return -1
 147
 148     return scores[predecessor_index][1]
 149
 150   def get_best_revnum(self):
 151     """Find the revnum with the highest score.
 152
 153     Return (revnum, score) for the revnum with the highest score.  If
 154     the highest score is shared by multiple revisions, select the
 155     oldest revision."""
 156
 157     best_source_lod = None
 158     best_revnum = SVN_INVALID_REVNUM
 159     best_score = 0
 160
 161     source_lods = self._scores_map.keys()
 162     source_lods.sort()
 163     for source_lod in source_lods:
 164       for revnum, score in self._scores_map[source_lod]:
 165         if score > best_score:
 166           best_source_lod = source_lod
 167           best_score = score
 168           best_revnum = revnum
 169     return best_source_lod, best_revnum, best_score
 170
 171