Re: Possible bug in selecting the best revision as base for a tag or branch

On Fri, Jan 28, 2011 at 5:32 PM, Michael Haggerty <[email protected]> wrote:
> On 01/28/2011 01:36 PM, Anders Pilegaard wrote:
>> I've come across some tags and branches that are getting fixup commits
>> - where it shouldn't be necessary.  One example was a tag that was
>> created with a fixup commit deleting one file.  That would have been
>> fine if the tag hadn't been set on the complete repository - but in
>> this case it had.  And looking at the history there was actually
>> another commit which would have been a perfect match - because the
>> "missing" file was actually deleted in a later commit.
>
> Yes, this is a known bug:
>
> http://cvs2svn.tigris.org/issues/show_bug.cgi?id=139

Ouch ... I should have caught that - sorry ... :-(

>> After looking a bit at the code my guess is that the problem lies in
>> the functions that try to select the best SVN revision to use.  For a
>> given tag the code loops through all files touched by the tag, finding
>> the range of SVN revisions that have that particular CVS revision on
>> this file.  If things are simple the intersection of these ranges is
>> non-empty, and the lowest numbered SVN revision in the range is
>> selected.
>
> Yes.  For files that were actually tagged, this is pretty
> straightforward, because the revision that was tagged has a single,
> contiguous range of SVN revisions where it existed.  Recording these
> ranges is straightforward and requires a foreseeable amount of space.

Maybe this is just a matter of words, but AFAICT there is no guarantee
that all SVN revisions inside a range will refer to the tagged CVS
revision.  There can easily be SVN commits on other branches in that
range?  For a given range I guess we can be sure that the first and
last SVN revision in the range will refer to the given CVS revision -
and that should be enough to guarantee that the code works ...

>> To further debug this I created a small test repository, which I have
>> attached (both the repository 'ex3.tar.gz' and the script creating it
>> 'create_ex3.sh').  As can also be seen from the script, the tag 'tag2'
>> and the branch 'branch2' should both have a perfect match - namely the
>> commit with the message "branch1 delta3".  Instead both are created
>> via fixup tags.  And not only that - they are also created off the
>> main trunk instead of off branch1 where they should belong!
>
> Yes, the presence of a file that shouldn't be in a tag is also
> disregarded when choosing a tag's preferred parent.
>
>> [...] Here the range for #3 becomes [2:7].
>> This is better - but the revision it really belongs to is r8, which is
>> still not in the range.  (Unless of course I'm confusing a 0-based and
>> a 1-based numbering ... :-) ...)
>
> Your interpretation is correct; these numbers correspond directly to SVN
> revision numbers.

In that case I don't see why r8 shouldn't be in the range.  Since it
is the perfect match it should at least be inside the range ...

Is this a further consequence of deleting a file - or is it a separate issue?

I'm guessing that this is related to selection of LOD?

>> So why do the tags get so low revision numbers?  I haven't tracked it
>> down, but I'm guessing it's due to some timestamp sorting.  Since tags
>> (and branches) don't have timestamps in CVS, the conversion is forced
>> to guess a timestamp.  The easiest guess would be to use the highest
>> timestamp of the tagged revisions.  But for the above sort to work it
>> should really be the lowest timestamp of the *next* revision after the
>> tagged.
>
> When commits are being formed in CreateRevsPass, tag commits are created
> as soon as all of the file revisions that appear within the tag have
> been committed.  This is done based on the topological ordering, not on
> guessing a timestamp.  Only in OutputPass are timestamps chosen for tag
> commits, simply by setting the timestamp equal to the timestamp of the
> previous commit.
>
> So tags get low revision numbers because cvs2svn isn't aware of the
> reason to give them higher revision numbers, because it doesn't even
> collect information about file deletions.

Hmm - I have an idea for this part.  Getting tags (and branches) later
in the SVN commit order seems to be necessary to allow better
selection of tag points.  So how about this:

If I've understood it correctly, then the ordering is done in the
topological pass (thanks for pointing me in the right direction!).  A
directed graph is made of all changesets, where edges indicate
dependencies between changesets.  SymbolChangeset's depend on the CVS
revisions they tag - which also means that the symbol will be created
at the earliest possible time - just after the referenced CVS
revisions.  And therefore likely before the CVS commit the symbol was
originally meant to reference.

My idea is to get the symbols as late as possible instead, by creating
some additional dependencies.  For every CVS revision in the symbol we
take all the predecessors of the successor, and add them as
dependencies to the tag.  Use the "last" real change if there is no
successor.

The "last" real change is a non-symbol changeset which has no
non-symbol successors ...  Hmm - if there are more, maybe it should be
the one with the latest timestamp instead of just the first found ...

If there is more than one successor this would become more complicated
- but can there be?  A plain tag changeset shouldn't ever have a
successor, so they are no problem.  Can branch tag changesets have
more than one successor?  I wouldn't think so, since multiple
successors would indicate a branch on the branch - but that second
branch changeset would have been created off a non-symbol changeset?

At this stage in the conversion there shouldn't be any cycles left.
And as long as the original graph had no cycles, this change shouldn't
create any.

For the example I sent, the graph for the topological sort is normally:

0.263612: ChangesetGraph:
0.263612:   1; pred=[3]; succ=[4]
0.263612:   2; pred=[]; succ=[8,3,6,7]
0.263612:   3; pred=[2,6]; succ=[1]
0.263612:   4; pred=[1]; succ=[5]
0.263612:   5; pred=[8,4]; succ=[]
0.263612:   6; pred=[2]; succ=[3]
0.263612:   7; pred=[2]; succ=[]
0.263612:   8; pred=[2]; succ=[5]

After adding extra dependencies it becomes:

0.262455: ChangesetGraph:
0.262455:   1; pred=[3]; succ=[4]
0.262455:   2; pred=[]; succ=[8,3,6,7]
0.262455:   3; pred=[2,6]; succ=[1]
0.262455:   4; pred=[1]; succ=[8,5]
0.262455:   5; pred=[8,4]; succ=[7]
0.262455:   6; pred=[2]; succ=[3]
0.262455:   7; pred=[2,5]; succ=[]
0.262455:   8; pred=[2,4]; succ=[5]

chg8 (creating branch2) now depends on chg4 which is last before chg5
- so it gets created just before chg5.  And chg7 which had no
successor gets the "last" change - chg5 - as predecessor, so it gets
created after the last real change.

The change is an extra function in changeset_graph.py, and a line
calling it in TopologicalSortPass.get_changesets in passes.py.  I've
attached a patch as proof-of-concept.  And no, I haven't really made
it release ready yet ... :-)

> I don't have time to write more now, but let me know if you have more
> questions.  If you want to work on improvements here, I'd be happy to
> share some thoughts about how this area could be improved.

I have some ideas, but I'll put it in a separate mail.

Best regards,
  Anders Pilegaard

------------------------------------------------------
http://cvs2svn.tigris.org/ds/viewMessage.do?dsForumId=1667&dsMessageId=2701915

To unsubscribe from this discussion, e-mail: [[email protected]].

Index: cvs2svn_lib/changeset_graph.py
===================================================================
--- cvs2svn_lib/changeset_graph.py	(revision 5318)
+++ cvs2svn_lib/changeset_graph.py	(working copy)
@@ -22,6 +22,7 @@
 from cvs2svn_lib.log import logger
 from cvs2svn_lib.changeset import RevisionChangeset
 from cvs2svn_lib.changeset import OrderedChangeset
+from cvs2svn_lib.changeset import SymbolChangeset
 from cvs2svn_lib.changeset import BranchChangeset
 from cvs2svn_lib.changeset import TagChangeset
 
@@ -370,6 +371,39 @@
       else:
         raise CycleInGraphException(cycle)
 
+  def delay_syms(self):
+    """Make all syms depend on the predecessors of their successor"""
+    
+    # Find "last" non-symbol change.  Ie. a non-symbol node with no
+    # non-symbol successors ...
+    for node in self.nodes.itervalues():
+      chg = self._changeset_db[node.id]
+      if isinstance(chg, SymbolChangeset):  continue
+      nonsymsucc = [id for id in node.succ_ids if not isinstance(self._changeset_db[id], SymbolChangeset)]
+      if not nonsymsucc:  break
+
+    lastnode = node
+    logger.quiet("Found last %s" % (lastnode,)) # FIXME
+
+    for node in self.nodes.itervalues():
+      chg = self._changeset_db[node.id]
+      if isinstance(chg, SymbolChangeset):
+        assert(len(node.succ_ids) <= 1)
+        n_successors = len(node.succ_ids)
+        if n_successors == 0:
+          # No successor - delay until last
+          node.pred_ids.add(lastnode.id)
+          lastnode.succ_ids.add(node.id)
+
+        elif n_successors == 1:
+          succ_node = self.nodes.get(list(node.succ_ids)[0])
+          for id in succ_node.pred_ids:
+            if id == node.id:  continue
+            node.pred_ids.add(id)
+            self.nodes[id].succ_ids.add(node.id)
+        else:
+          assert(0)
+
   def __repr__(self):
     """For convenience only.  The format is subject to change at any time."""
 
Index: cvs2svn_lib/passes.py
===================================================================
--- cvs2svn_lib/passes.py	(revision 5318)
+++ cvs2svn_lib/passes.py	(working copy)
@@ -1500,6 +1500,11 @@
       if isinstance(changeset, SymbolChangeset):
         symbol_changeset_ids.add(changeset.id)
 
+    ## Delay syms to the last possible moment
+    logger.quiet("Graph before delaying syms:\n" + str(changeset_graph)) # FIXME
+    #changeset_graph.delay_syms()
+    #logger.quiet("Graph after delaying syms:\n" + str(changeset_graph)) # FIXME
+
     # Ensure a monotonically-increasing timestamp series by keeping
     # track of the previous timestamp and ensuring that the following
     # one is larger.