You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Karl Fogel <kf...@newton.ch.collab.net> on 2003/03/07 21:34:41 UTC
cvs2svn and branches (long)
For a while now, I've been pondering the problem of how cvs2svn should
map CVS tags/branches to Subversion tags/branches. It's definitely
time to come out of the closet and discuss this on the list :-).
Marko, I know you've been thinking about this problem too, and that
much of this mail is old news to you. You probably even have some
solutions already. But let's nail down the desired behavior in prose,
before making any further code changes. This problem is complex
enough that we should make sure we all agree on the goals, before
writing code to meet those goals.
All examples below use the standard Greek tree, as described in
subversion/tests/greek-tree.txt. Also, the text below just talks
about branches, for simplicity, but I think all the same arguments
apply to tags.
First let's take the simple case of branching a single file:
Single File:
============
Suppose the user does this:
$ cvs tag -b SMALL_BRANCH A/D/G/pi
In Subversion, it's reasonable for that to appear in the repository
like this:
/branches/SMALL_BRANCH/A/D/G/pi
This will require the intermediate directories to be made in the txn
first. In the txn, the intermediate directories should be done with
mkdir, not copy. This is because the CVS user did not do anything to
indicate directoryish intentions, so to speak. Only pi itself would
be the result of a copy.
Note also that pi would be the only leaf node under that branch. For
example, these would *not* exist:
/branches/SMALL_BRANCH/iota
/branches/SMALL_BRANCH/A/D/H
/branches/SMALL_BRANCH/A/D/G/rho
/branches/SMALL_BRANCH/A/D/G/tau
... etc ...
(Unless, of course, someone had branched another file using the same
branch name, coincidentally or otherwise.)
Anyway, I think the above is the most reasonable result for the single
file case, since CVS doesn't version directories, and Subversion can
only represent a branch by means of a corresponding path under the
'/branches' directory.
Multiple Files:
===============
The logic for branching a set of files is similar to the single-file
logic. Of course, in CVS, you can't distinguish between a directory
being branched and the files in it *individually* being branched, or
some subset of them being branched... which leads us to some
interesting choices. Plus there's the issue of mixed-revision
branches (possible when the user did 'cvs tag' instead of 'cvs rtag').
Ideally, when we can detect that a majority of files in a given
directory have all been branched to the same branch, and that it
happened on revisions which were all in HEAD together at some point in
time, then we would create the parent directory using copy instead of
mkdir. For example
$ cvs tag -b MEDIUM_BRANCH A/D/G
should cause G and all its children to exist in the repository:
/branches/SMALL_BRANCH/A/D/G/
/branches/SMALL_BRANCH/A/D/G/pi
/branches/SMALL_BRANCH/A/D/G/rho
/branches/SMALL_BRANCH/A/D/G/tau
In the Subversion txn, this would look something like
$ svn mkdir /trunk /branches/MEDIUM_BRANCH
$ svn mkdir /trunk/A /branches/MEDIUM_BRANCH/A
$ svn mkdir /trunk/A/D /branches/MEDIUM_BRANCH/A/D
$ svn cp /trunk/A/D/G /branches/MEDIUM_BRANCH/A/D/G
It's possible that /branches/MEDIUM_BRANCH might already exist, say,
because someone did 'cvs tag -b MEDIUM_BRANCH A/D/H'. That's okay; we
only create the directories we need to create. The deeper copies will
override the higher ones in 'svn log' and such.
The real trickiness starts when we try to deduce the revision/date
that will catch the largest possible set of files that belong in the
initial branch creation. Files in that set can be copied implicitly,
by being under the highest relevant directory (from that rev/date),
which gets copied to the appropriate place in /branches/PATH.../. All
files not in that set must be manually copied into the new branch, of
course.
It's also possible to have situations where all but a few files are
branched (in CVS, maybe the list of files was given explicitly, or
maybe someone deleted the branch tag from certain files later). In
such cases, we probably want to copy the highest possible parent
directory, as usual, then *delete* the unbranched files from the new
copy, before committing the txn.
All of this implies that before committing anything to Subversion,
we'll need to gather the full set of CVS commits. (Is that where
you're heading in your patches, re a "cvs2svn-data.commits" file?).
And we'll have to consider the *creation* of branches and tags to be
like CVS commits, in the sense that they map to Subversion commits,
even though in CVS these actions do not involve running 'cvs ci'.
In other words, there will be more commits in the Subversion
repository than there were in CVS. Thus, the total number of
Subversion commits will be roughly the number times someone typed 'cvs
ci' *plus* the number of unique symbolic names in the CVS repository.
But for the latter kind of commit, we can't use our usual method of
deducing the atomic commit group, because the relevant file revisions
can be arbitrarily far apart and may not share author and log message.
So when in the revision history does a particular branch's creation
get inserted? To answer this question, we have to find all the
files/revs on which the branch was created. Each file/rev pair maps
to a range of Subversion revisions... "But wait! I thought we don't
know the Subversion revisions yet, because we haven't finished
deducing the branch creations?"
Okay, so let me roughly describe an algorithm here :-). I'm doing
this more as an indirect way of describing the problem itself, though
our solution may look something like this. But please don't take it
as anything but a tentative proposal -- there's probably a better way
to do it.
In the first pass, cvs2svn.py doesn't try to deduce any
branch-creation commits. It just groups 'cvs ci' commits, the same
way it already does. We already remember symbolic names as we parse
each RCS file -- that is, we remember what revision each branch is
rooted in. This information is recorded in cvs2svn-data.*revs.
Now suppose that branch B was created on revision X.Y for /A/D/G/pi.
What we need is a table indicating that for file /A/D/G/pi, revision
X.Y was committed in Subversion revision N, and that later on, X.(Y+1)
was committed in revision M. This range, N->M, is the range of
possible Subversion revisions from which branch B can be copied, for
this file.
Obviously, we can't have this table by the time we're done parsing
/A/D/G/pi, because we won't have any Subversion commits grouped until
we've parsed *all* the RCS files. We also can't accumulate the
information in memory by making a pass over 'cvs2svn-data.s-revs',
because there might be an arbitrary amount of time and data separating
X.Y from X.(Y+1), for a given file.
My solution to this is to use Python's `anydbm' interface as a backing
store for what would otherwise be an in-memory operation. Pass 4
would now become
Run over cvs2svn-data.s-revs. For each line that claims a branch
creation, make an entry in a new working file
cvs2svn-branches/BRANCH_NAME.dbm
The entry maps file paths to revision ranges
filepath --> (N M)
where N is the Subversion revision corresponding to the CVS revision
X.Y in which the branch was created for that filepath, and M is the
Subversion revision corresponding to X.(Y+1).
As we're running over cvs2svn-data.s-revs, we also remember every
unique branch name. (It's okay to hold all branch names in memory;
even the nastiest CVS repository will only have a few thousand
branches. We just can't hold every file path or every revision in
memory.)
At the end of this pass, we have every branch name in memory, and we
have a dbm file for each branch, indicating, for each filepath in the
repository, the range of Subversion revisions from which that branch
*could* be copied.
Now we just have to loop over the branches, finding the "ideal"
Subversion revision, that is, the revision which if used to create the
branch, will necessitate the smallest number of manual secondary
copies, perhaps even zero.
My off-the-top-of-my-head suggestion for that algorithm would be:
Map each branch name to a list of pairs, each pair mapping a
Subversion revision range to the number of files available to the
branch from those revisions:
BRANCH_NAME ==> [ ((N, M), COUNT), ...]
Where (N, M) is the revision range, and COUNT is the number of files
that could be gotten from that range.
The list of pairs starts out empty. To fill it, iterate over all the
entries in cvs2svn-copies/BRANCH_NAME.dbm. For the first file, add
((N, M), 1)
For the next file, increment the count if N and M are the same as the
previous entry, or else splice it in in the obvious way, keeping the
list of pairs ordered by N and M, such that a lower N comes first, and
within a given N, a higher M comes first (i.e., ranges are ordered,
with wider ranges earlier).
Notice that a given file may be counted in more than one pair; the
total of all COUNTs may be much higher than the total number of files
recorded in the .dbm file.
When all files have been processed, run over the list of pairs,
choosing one with the highest available count. We'll use a revision
from that range to make the branch copy, and then deal with missing
items and wrong-revision items by manually deleting and/or copying.
(If these lists get too big to store in memory, we can write them out
to cvs2svn-copies/BRANCH_NAME.ranges or something.)
Of course, once we start inserting these new branch-creation revisions
into the revision history, the revision ranges recorded in the .dbm
files will be wrong :-). So before we can commit anything, we have to
run over cvs2svn-data.s-revs again, now that we have the branch
creation information, and write out 'cvs2svn-data.commits or whatever,
which includes lines describing the branch commits. This means that
each time we insert a branch commit, we increment an accumulator, and
as we're writing out *next* branch commit, we add the current
accumulator value to the "source revision" for the copy. Otherwise,
we'll get further and further "off" as we go.
When it's all done, we have a .commits file. The final pass runs over
that file, making commits to the Subversion repository.
I've hand-waved on some details, of course, such as exact information
recorded in the .commits file. Or: sometimes the same name is tag in
one place but a branch in another, and Subversion has to correctly
split such trees between /tags and /branches. Etc. But I hope the
general idea is clear here.
Greg Stein also described a two-pass algorithm for discovering the
best-copy-revision during a phone call; I'm embarrassed to say I don't
remember it well enough to describe it here :-), but it wasn't
entirely dissimilar to the above.
So Marko: am I on the right page with all this? And is this stuff
you've already started, or were you going about things differently?
Thanks,
-Karl
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: cvs2svn and branches (long)
Posted by Benjamin Pflugmann <be...@pflugmann.de>.
On Fri 2003-03-07 at 15:52:59 -0800, Greg Stein wrote:
[...]
> Let's say that you isolated the branch creation down to two source
> revisions:
>
> (A) rev 103, picking up 1000 items
> (B) rev 107, picking up 10 items
>
> Let's also say that /trunk/some/dir is a directory with 11 items in it --
> one item from bucket (A) (named "fname0") and the other ten ("fname1"
> through "fname10") are all (B). The algorithm would perform the following
> operations:
>
> svn cp /trunk@103 /branches/BRANCH
> svn cp /trunk/some/dir/fname1@107 /branches/BRANCH/some/dir
> ...
> svn cp /trunk/some/dir/fname10@107
>
> But the ideal behavior is:
>
> svn cp /trunk@103 /branches/BRANCH
> svn cp /trunk/some/dir@107 /branches/BRANCH/some/dir
> svn cp /trunk/some/dir/fname0@103 /branches/BRANCH/some/dir
>
> Beats the crap out of me how to do *that* algorithm :-), but I wanted to
> describe the scenario so that we can document the potential occurrence.
Probably I am missing the point, or more precisely, the greater
picture (wouldn't be the first time ;), but what is wrong with going
up the path bottom-up and building majorities this way. Example:
Look at longest path, here .../some/dir, and group by revisions:
10 from /trunk/some/dir@107
1 from /trunk/some/dir@103
-> choose /trunk/some/dir@107 as main source
Drop trailing dir, look at .../some, and group by revisions:
(let's pretend that it only has one item)
1 from /trunk/some@107 (the /trunk/some/dir@107 we just choose)
-> choose /trunk/some@107
Drop trailing dir, look at .../, and group by revisions:
990 from /trunk@103 (or whatever is left of the 1000)
1 from /trunk@107 (the /trunk/some@107 we just choose)
-> choose /trunk@103 as main source
and so on.
Some further comments:
- As you can see, having a lot of sub-directories from a certain
revision would make the parent to be from the same revision.
- Of course, you would only generate an "svn cp" for a sub-directory
if a different revision had been chosen for the revision, i.e. you
don't want to do step #2 of
1 svn cp /trunk@103 /branches/BRANCH
2 svn cp /trunk/some@103 /branches/BRANCH/some
3 svn cp /trunk/some/dir@107 /branches/BRANCH/some/dir
- Items being in the trunk (for the given revision), but not in the
branch could/should to be counted in negatively for the belonging
group. If sums for all groups are negative, choose an empty dir as
"main source" (by using "svn mkdir") proceed for all sub-items as
usual. Example:
If you there are 20 other items in each of both,
/trunk/some/dir@107 and /trunk/some/dir@103, you would get:
Look at longest path, here .../some/dir, and group by revisions:
-10 from /trunk/some/dir@107 (result of 10-20)
-19 from /trunk/some/dir@103 (result of 1-20)
-> choose empty dir as main source (via "svn mkdir")
- In other words, the algorithm effectively counts "number of
commands to be saved" (off by one).
- The algorithm presumes that the "cost" is linear to the "number of
commands" and the "cost" for all commands (cp, mkdir, rm) is the
same. Tweaking for different costs is easy. Tweaking for
non-linearity isn't.
- One should consider using some threshold. If there are 20 different
revisions from each of which we can copy 1 file and 1 revision
(say, C) we can copy 2 files from, we probably don't want start
with C (which has max. count) as main source, but with an empty
dir. In other words, the main source we choose probably should
contain some (relative?) majority of the items.
Well, I hope I did not bore anyone to death. I choose to be more
explicit as I often tend to explain things in a way which other find
non-intuitive (and my technical writing skills for English don't help
at that).
Bye,
Benjamin.
Re: cvs2svn and branches (long)
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Greg Stein <gs...@lyra.org> writes:
> > At the end of this pass, we have every branch name in memory, and we
> > have a dbm file for each branch, indicating, for each filepath in the
> > repository, the range of Subversion revisions from which that branch
> > *could* be copied.
> >
> > Now we just have to loop over the branches, finding the "ideal"
> > Subversion revision, that is, the revision which if used to create the
> > branch, will necessitate the smallest number of manual secondary
> > copies, perhaps even zero.
>
> Yup, and this algorithm is independent of the file names, which is why I
> suggest losing that part of the data structure and the need for the dbm.
We don't need the paths at this final stage; but we need them in order
to build up the information to get to this stage. To determine the
range of Subversion revisions in which a given CVS file qrevision
lives, we have to keep track of the individual file changes -- because
it's the arrival of the "next" CVS commit on that file that allows us
to fix the endpoint of the range.
Sure, after we have all these ranges, we can determine the "best"
Subversion revision for the copy. But to get the ranges, we need to
essentially use the paths as keys in a hash table.
(I can explain the process in more detail, if it's not clear.)
> Your algorithm increases the count in all appropriate ranges for a given
> file. In mine, a file would only go into one range. This implies that the
> algorithm might select the "wrong" one (it went into a range referring to 20
> items rather than the big 1000 item range). The second pass would shift
> items into the larger range. Your algorithm does it in one pass.
Yah. The two-pass might still be faster than the one-pass, though.
Can you describe it briefly in writing? That will probably be enough
to stimulate my memory. I tried to re-derive it, but I was unable to
come up with something that would work correctly. Probably I was
forgetting some crucial step.
> Let's also say that /trunk/some/dir is a directory with 11 items in it --
> one item from bucket (A) (named "fname0") and the other ten ("fname1"
> through "fname10") are all (B). The algorithm would perform the following
> operations:
>
> svn cp /trunk@103 /branches/BRANCH
> svn cp /trunk/some/dir/fname1@107 /branches/BRANCH/some/dir
> ...
> svn cp /trunk/some/dir/fname10@107
>
> But the ideal behavior is:
>
> svn cp /trunk@103 /branches/BRANCH
> svn cp /trunk/some/dir@107 /branches/BRANCH/some/dir
> svn cp /trunk/some/dir/fname0@103 /branches/BRANCH/some/dir
>
> Beats the crap out of me how to do *that* algorithm :-), but I wanted to
> describe the scenario so that we can document the potential occurrence.
Yup :-). There will probably always be incremental improvements
possible. But in the meantime, a few extra copies won't hurt so much,
as long as we get the big initial copy right.
-K
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: cvs2svn and branches (long)
Posted by Greg Stein <gs...@lyra.org>.
On Fri, Mar 07, 2003 at 03:34:41PM -0600, Karl Fogel wrote:
>...
> The logic for branching a set of files is similar to the single-file
> logic. Of course, in CVS, you can't distinguish between a directory
> being branched and the files in it *individually* being branched, or
> some subset of them being branched... which leads us to some
> interesting choices. Plus there's the issue of mixed-revision
> branches (possible when the user did 'cvs tag' instead of 'cvs rtag').
(or the user moved a tag manually)
>...
> And we'll have to consider the *creation* of branches and tags to be
> like CVS commits, in the sense that they map to Subversion commits,
> even though in CVS these actions do not involve running 'cvs ci'.
Right.
I just thought of something, too. You'll want to watch out for the case
where a branch appears to be created *after* a commit on the branch occurs.
There are a couple ways that this can happen:
1) They are logically separate branches. The second branch was constructed
after the first was set up and received some commits.
2) Somebody manually moved the branch base for some item to a revision of
that item which occurs after a commit to some of the other branch items.
I'm not sure what the solution would be (beyond flagging an error and
ignoring the branch). You could probably just create two branches,
partitioned between the "original" branch and the items that created the
second branch. For case (2), this implies that a given commit (after the
second branch was created) might actually occur on both branches.
>...
> In the first pass, cvs2svn.py doesn't try to deduce any
> branch-creation commits. It just groups 'cvs ci' commits, the same
> way it already does. We already remember symbolic names as we parse
> each RCS file -- that is, we remember what revision each branch is
> rooted in. This information is recorded in cvs2svn-data.*revs.
Don't get pegged in by that. Storing the information in a different form,
different file, with different info, or a different sort order is all open
for change.
> Now suppose that branch B was created on revision X.Y for /A/D/G/pi.
> What we need is a table indicating that for file /A/D/G/pi, revision
I'm not sure this assumption is valid. While trying to figure out when a
branch is created, it doesn't feel like you actually need to know
information about the files -- only what source revisions you'll need. It
may be that when you go to construct the branch, the processing will be some
streamy thing that scans over the inputs and figures out "for file
/A/D/G/pi, I'll get it from revision R."
> X.Y was committed in Subversion revision N, and that later on, X.(Y+1)
> was committed in revision M. This range, N->M, is the range of
> possible Subversion revisions from which branch B can be copied, for
> this file.
Right.
> Obviously, we can't have this table by the time we're done parsing
> /A/D/G/pi, because we won't have any Subversion commits grouped until
> we've parsed *all* the RCS files. We also can't accumulate the
> information in memory by making a pass over 'cvs2svn-data.s-revs',
> because there might be an arbitrary amount of time and data separating
> X.Y from X.(Y+1), for a given file.
If you lose the file assocations, and only keep the range sets for each
branch, then you might be able to keep this in memory.
(but the question about restartable passes will arise; if you compute info
in pass 3, to be used in pass 4, then you break the ability to rerun cvs2svn
starting at pass 4)
> My solution to this is to use Python's `anydbm' interface as a backing
> store for what would otherwise be an in-memory operation. Pass 4
> would now become
I do not see a need for anydbm, for a couple reasons:
1) I'm not sure you need the file assocations
2) I don't see the need for data lookup based on the filename
e.g. a flat, streamy file could probably work here, too
>...
> As we're running over cvs2svn-data.s-revs, we also remember every
> unique branch name. (It's okay to hold all branch names in memory;
Except for the restartable thing. It may be that at the end of a pass, you
dump the memory to a disk file. If you start at a later pass, then you can
simply restore from that disk file.
> even the nastiest CVS repository will only have a few thousand
> branches. We just can't hold every file path or every revision in
> memory.)
Right on every file path. Not sure what you have in mind with "every
revision" however.
> At the end of this pass, we have every branch name in memory, and we
> have a dbm file for each branch, indicating, for each filepath in the
> repository, the range of Subversion revisions from which that branch
> *could* be copied.
>
> Now we just have to loop over the branches, finding the "ideal"
> Subversion revision, that is, the revision which if used to create the
> branch, will necessitate the smallest number of manual secondary
> copies, perhaps even zero.
Yup, and this algorithm is independent of the file names, which is why I
suggest losing that part of the data structure and the need for the dbm.
>...
> I've hand-waved on some details, of course, such as exact information
> recorded in the .commits file. Or: sometimes the same name is tag in
> one place but a branch in another, and Subversion has to correctly
> split such trees between /tags and /branches. Etc. But I hope the
> general idea is clear here.
Yup.
> Greg Stein also described a two-pass algorithm for discovering the
> best-copy-revision during a phone call; I'm embarrassed to say I don't
> remember it well enough to describe it here :-), but it wasn't
> entirely dissimilar to the above.
Your algorithm increases the count in all appropriate ranges for a given
file. In mine, a file would only go into one range. This implies that the
algorithm might select the "wrong" one (it went into a range referring to 20
items rather than the big 1000 item range). The second pass would shift
items into the larger range. Your algorithm does it in one pass.
It should also be said that the ideal branching would account for directory
copies. In the following scenario, I'll show how the proposed algorithm
could perform the wrong branch assembly operations. I think we should stick
with the algorith, though, as it will *generally* work well, but I believe
we should also consider how the algorithm could be replaceable by somebody
with way too much time on their hands to correct it :-)
Let's say that you isolated the branch creation down to two source
revisions:
(A) rev 103, picking up 1000 items
(B) rev 107, picking up 10 items
Let's also say that /trunk/some/dir is a directory with 11 items in it --
one item from bucket (A) (named "fname0") and the other ten ("fname1"
through "fname10") are all (B). The algorithm would perform the following
operations:
svn cp /trunk@103 /branches/BRANCH
svn cp /trunk/some/dir/fname1@107 /branches/BRANCH/some/dir
...
svn cp /trunk/some/dir/fname10@107
But the ideal behavior is:
svn cp /trunk@103 /branches/BRANCH
svn cp /trunk/some/dir@107 /branches/BRANCH/some/dir
svn cp /trunk/some/dir/fname0@103 /branches/BRANCH/some/dir
Beats the crap out of me how to do *that* algorithm :-), but I wanted to
describe the scenario so that we can document the potential occurrence.
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: cvs2svn and branches (long)
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Marko Macek <Ma...@gmx.net> writes:
> I was trying to separate the actual commit step that creates the
> repository from the heuristics that generate the commit sets.
> It is also easier to test/develop things if one can diff the
Great! Yes, I totally agree.
> > The entry maps file paths to revision ranges
> > filepath --> (N M)
> > where N is the Subversion revision corresponding to the CVS revision
> > X.Y in which the branch was created for that filepath, and M is the
> > Subversion revision corresponding to X.(Y+1).
>
> I suggest we ignore the memory usage problem for now because practice
> it's not a problem except for extremely large repositories. We should
> get the algorithm right first.
We can ignore it for a bit, but I know of several specific large
repositories out there that will want to convert. They will simply
grind to a halt if we do stuff like this in memory; we're talking
about a decade of revision history and thousands of branches/tags :-).
> One thing to be aware of: for nested branches or tags on branches, the
> decision of when to copy the branch will affect the revisions above.
> It may be necessary to run the algorithm several times, for each level
> of tags. what complicates things is that tags (and therefore branches)
> can tag files of different branches.
Yes. We may have to get all branches first, then do all tags in a
separate pass?
I had some trouble understanding your algorithm description:
> But my current algorithm works differently, mainly because I wanted to
> avoid delete operations when doing a tag copy and also reduce memory
> usage. And because it is simpler (but in current implementation,
> pretty slow).
>
> It goes like this:
>
> pass4: go over the .s-revs file and make a set of CVS (f,r) for each
> tag/branch. Also separates tags from branches and determines the
> branch /tag dependencies (for now it incorrectly assumes it is a
> tree). This is kept in memory for now.
>
> pass5: Generates a commits file like exactly like current cvs2svn. This
> should probably be careful not to combine files/revs that are only
> partially tagged, but it isn't yet.
>
> pass6: Read the commits file and keep track of the current repository
> state. After each commit, compare the state to all tags. We then have
> several cases:
>
> a) perfect match. Mark this tag as having a possible perfect copy.
> This handles things like files being and then removed.
"being and then removed" ... is the missing word "added"?
> b) partial match. We have a match which has some files, but no extra
> files. Remember the match if it's better than previous partial match.
Is "extra" really "all"? I guess I don't understand this part with
precision.
> c) no match. If there is no partial or perfect match, the tag will be
> copied file by file.
I understand step (c), but am unclear on the exact circumstances that
cause it to be invoked.
> b) Branch must be copied before there is any commit to it.
Yes :-).
> Also, it should be resonably easy (but slower) to organize the files
> into a directory tree instead of a list). This would make it possible
> to handle subtree copies instead failing back to file-by-file copies.
That sounds like a good idea.
> I haven't actually decided which algorithm I prefer.
> Initially, the second one would be made of simpler building
> blocks and there easier to debug and more bulletproof (like the
> current file-by-file is), but it didn't exactly turn out to be.
> I'd still prefer not to do any deletes when copying branches/tags.
> I'm also not exactly a fan of using dbm (text files would be more
> debuggable).
When it's a simple use, like tying to a DBM to get basically a
persistent hash, they're really no problem. They behave predictably
and (in my experience) don't interfere with development and debugging.
I'm not saying we absolutely must use this method, just that
debuggability shouldn't be a big concern if we do.
> 1. If one adds a file on the trunk and then adds the file with the
> same name on the branch, the CVS revisions will be 1.1 for trunk, and
> 1.1.1.1 for branch. This looks like the file was branched, but
> actually it wasn't. (This needs to be added in the test suite).
It's the same 1.1.1.1 if you branch the existing file but don't commit
any changes on the branch, right? (In other words, the two cases
can't be distinguished.)
> 2. cvs import-ed repositories. When a cvs repository has been created
> with CVS import, all the tags on unmodified files will be created for
> revision 1.1.1.1, not revision 1.1. This is a major complication. My
> code currently has a hack to remap version 1.1.1.1 to 1.1 and skip
> vendor branch conversion, but this could be wrong if vendor branch was
> imported later. (I have a test repository where someone imported his
> own working copy... :)
Are you talking only about repeated vendor branch imports, or all
imports?
My understanding is that if a file is at 1.1 (i.e., its initial
state), and someone creates a branches on that revision, then the
branch's initial revision will be 1.1.1.1, before anything is
committed on the branch. Could be misremembering.
When you dig up (or write) patches, can you try to make them as
complete, self-contained, and small as possible :-)? For example,
maybe first let's add the separate `.commits' file, without any tag or
branch changes. It'll make it much easier for me to review the
patches in a timely manner, if I can grok exactly what each change
does.
I realize this makes the communication/code ratio go up, but I think
it's worth it. Hope you agree...
-K
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: cvs2svn and branches (long)
Posted by Marko Macek <Ma...@gmx.net>.
Karl Fogel wrote:
> For a while now, I've been pondering the problem of how cvs2svn should
> map CVS tags/branches to Subversion tags/branches. It's definitely
> time to come out of the closet and discuss this on the list :-).
[...]
> Single File:
> ============
> $ cvs tag -b SMALL_BRANCH A/D/G/pi
> /branches/SMALL_BRANCH/A/D/G/pi
[...]
Agreed. And non-branch should go to /tags/.
> Multiple Files:
> ===============
>
[...]
> $ cvs tag -b MEDIUM_BRANCH A/D/G
[...]
> $ svn mkdir /trunk /branches/MEDIUM_BRANCH
> $ svn mkdir /trunk/A /branches/MEDIUM_BRANCH/A
> $ svn mkdir /trunk/A/D /branches/MEDIUM_BRANCH/A/D
> $ svn cp /trunk/A/D/G /branches/MEDIUM_BRANCH/A/D/G
[...]
Agreed.
> It's also possible to have situations where all but a few files are
> branched (in CVS, maybe the list of files was given explicitly, or
> maybe someone deleted the branch tag from certain files later). In
> such cases, we probably want to copy the highest possible parent
> directory, as usual, then *delete* the unbranched files from the new
> copy, before committing the txn.
In my current code, I decided not to do any deletes,
because it doesn't seem very clean. But it could work.
> All of this implies that before committing anything to Subversion,
> we'll need to gather the full set of CVS commits. (Is that where
> you're heading in your patches, re a "cvs2svn-data.commits" file?).
I was trying to separate the actual commit step that creates the
repository from the heuristics that generate the commit sets.
It is also easier to test/develop things if one can diff the
.commits files.
[...]
> So when in the revision history does a particular branch's creation
> get inserted? To answer this question, we have to find all the
> files/revs on which the branch was created. Each file/rev pair maps
> to a range of Subversion revisions... "But wait! I thought we don't
> know the Subversion revisions yet, because we haven't finished
> deducing the branch creations?"
Renumbering is easy, once you know where to insert the
copy operations. ;)
[...]
> In the first pass, cvs2svn.py doesn't try to deduce any
> branch-creation commits. It just groups 'cvs ci' commits, the same
> way it already does. We already remember symbolic names as we parse
> each RCS file -- that is, we remember what revision each branch is
> rooted in. This information is recorded in cvs2svn-data.*revs.
Yes
> The entry maps file paths to revision ranges
>
> filepath --> (N M)
>
> where N is the Subversion revision corresponding to the CVS revision
> X.Y in which the branch was created for that filepath, and M is the
> Subversion revision corresponding to X.(Y+1).
I suggest we ignore the memory usage problem for now because practice
it's not a problem except for extremely large repositories. We should
get the algorithm right first.
> At the end of this pass, we have every branch name in memory, and we
> have a dbm file for each branch, indicating, for each filepath in the
> repository, the range of Subversion revisions from which that branch
> *could* be copied.
>
> Now we just have to loop over the branches, finding the "ideal"
> Subversion revision, that is, the revision which if used to create the
> branch, will necessitate the smallest number of manual secondary
> copies, perhaps even zero.
>
> My off-the-top-of-my-head suggestion for that algorithm would be:
>
> Map each branch name to a list of pairs, each pair mapping a
> Subversion revision range to the number of files available to the
> branch from those revisions:
>
> BRANCH_NAME ==> [ ((N, M), COUNT), ...]
>
> Where (N, M) is the revision range, and COUNT is the number of files
> that could be gotten from that range.
> The list of pairs starts out empty. To fill it, iterate over all the
> entries in cvs2svn-copies/BRANCH_NAME.dbm. For the first file, add
>
> ((N, M), 1)
>
> For the next file, increment the count if N and M are the same as the
> previous entry, or else splice it in in the obvious way, keeping the
> list of pairs ordered by N and M, such that a lower N comes first, and
> within a given N, a higher M comes first (i.e., ranges are ordered,
> with wider ranges earlier).
One thing to be aware of: for nested branches or tags on branches, the
decision of when to copy the branch will affect the revisions above.
It may be necessary to run the algorithm several times, for each level
of tags. what complicates things is that tags (and therefore branches)
can tag files of different branches.
> Notice that a given file may be counted in more than one pair; the
> total of all COUNTs may be much higher than the total number of files
> recorded in the .dbm file.
>
> When all files have been processed, run over the list of pairs,
> choosing one with the highest available count. We'll use a revision
> from that range to make the branch copy, and then deal with missing
> items and wrong-revision items by manually deleting and/or copying.
You should also track the number of files which are in the revision but
must not be copied to the branch.
> (If these lists get too big to store in memory, we can write them out
> to cvs2svn-copies/BRANCH_NAME.ranges or something.)
>
> Of course, once we start inserting these new branch-creation revisions
> into the revision history, the revision ranges recorded in the .dbm
> files will be wrong :-). So before we can commit anything, we have to
> run over cvs2svn-data.s-revs again, now that we have the branch
> creation information, and write out 'cvs2svn-data.commits or whatever,
> which includes lines describing the branch commits. This means that
> each time we insert a branch commit, we increment an accumulator, and
> as we're writing out *next* branch commit, we add the current
> accumulator value to the "source revision" for the copy. Otherwise,
> we'll get further and further "off" as we go.
>
> When it's all done, we have a .commits file. The final pass runs over
> that file, making commits to the Subversion repository.
>
> I've hand-waved on some details, of course, such as exact information
> recorded in the .commits file. Or: sometimes the same name is tag in
> one place but a branch in another, and Subversion has to correctly
> split such trees between /tags and /branches. Etc. But I hope the
> general idea is clear here.
> Greg Stein also described a two-pass algorithm for discovering the
> best-copy-revision during a phone call; I'm embarrassed to say I don't
> remember it well enough to describe it here :-), but it wasn't
> entirely dissimilar to the above.
>
> So Marko: am I on the right page with all this? And is this stuff
> you've already started, or were you going about things differently?
I actually had something like the above, I'll see if I can find a
version that is in reasonably workable state. It does it all in memory
though.
But my current algorithm works differently, mainly because I wanted to
avoid delete operations when doing a tag copy and also reduce memory
usage. And because it is simpler (but in current implementation, pretty
slow).
It goes like this:
pass4: go over the .s-revs file and make a set of CVS (f,r) for each
tag/branch. Also separates tags from branches and determines the branch
/tag dependencies (for now it incorrectly assumes it is a tree). This is
kept in memory for now.
pass5: Generates a commits file like exactly like current cvs2svn. This
should probably be careful not to combine files/revs that are only
partially tagged, but it isn't yet.
pass6: Read the commits file and keep track of the current repository
state. After each commit, compare the state to all tags. We then have
several cases:
a) perfect match. Mark this tag as having a possible perfect copy.
This handles things like files being and then removed.
b) partial match. We have a match which has some files, but no extra
files. Remember the match if it's better than previous partial match.
c) no match. If there is no partial or perfect match, the tag will be
copied file by file.
pass7: Read the commits file again, now doing actual SVN commits.
a) Once a branch has been perfectly/partially copied, any extra files
are copied file by file.
b) Branch must be copied before there is any commit to it.
Right now it's pretty slow, because the matching is all brute force.
Caching some matching state would make it much faster.
Memory usage could be optimized by splitting pass6 and doing pass5 and
6.1 for each tag separately and store the results to a file.
Also, it should be resonably easy (but slower) to organize the files
into a directory tree instead of a list). This would make it possible
to handle subtree copies instead failing back to file-by-file copies.
I haven't actually decided which algorithm I prefer.
Initially, the second one would be made of simpler building
blocks and there easier to debug and more bulletproof (like the
current file-by-file is), but it didn't exactly turn out to be.
I'd still prefer not to do any deletes when copying branches/tags.
I'm also not exactly a fan of using dbm (text files would be more
debuggable).
Now on to some more technical CVS issues:
1. If one adds a file on the trunk and then adds the file with the same
name on the branch, the CVS revisions will be 1.1 for trunk, and 1.1.1.1
for branch. This looks like the file was branched, but actually it
wasn't. (This needs to be added in the test suite).
2. cvs import-ed repositories. When a cvs repository has been created
with CVS import, all the tags on unmodified files will be created for
revision 1.1.1.1, not revision 1.1. This is a major complication. My
code currently has a hack to remap version 1.1.1.1 to 1.1 and skip
vendor branch conversion, but this could be wrong if vendor branch was
imported later. (I have a test repository where someone imported his own
working copy... :)
Regards,
MArk
Mark
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org