Re-update to rcsparse r2495 to get all the goodness of the new update script.
[cvs2svn.git] / doc / design-notes.txt
blob904cdd03a168b45e0c33d43dc0a609adf3bcb4b5
1                          How cvs2svn Works
2                          =================
4                        Theory and requirements
5                        ------ --- ------------
7 There are two main problem converting a CVS repository to SVN:
9 - CVS does not record enough information to determine what actually
10   happened to a repository.  For example, CVS does not record:
12   - Which file modifications were part of the same commit
14   - The timestamp of tag and branch creations
16   - Exactly which revision was the base of a branch (there is
17     ambiguity between x.y, x.y.2.0, x.y.4.0, etc.)
19   - When the default branch was changed (for example, from a vendor
20     branch back to trunk).
22 - The timestamps in a CVS archive are not reliable.  It can easily
23   happen that timestamps are not even monotonic, and large errors (for
24   example due to a failing server clock battery) are not unusual.
26 The absolutely crucial, sine qua non requirement of a conversion is
27 that the dependency relationships within a file be honored, mainly:
29 - A revision depends on its predecessor
31 - A branch creation depends on the revision from which it branched,
32   and commits on the branch depend on the branch creation
34 - A tag creation depends on the revision being tagged
36 These dependencies are reliably defined in the CVS repository, and
37 they trump all others, so they are the scaffolding of the conversion.
39 Moreover, it is highly desirable that the timestamps of the SVN
40 commits be monotonically increasing.
42 Within these constraints we also want the results of the conversion to
43 resemble the history of the CVS repository as closely as possible.
44 For example, the set of file changes grouped together in an SVN commit
45 should be the same as the files changed within the corresponding CVS
46 commit, insofar as that can be achieved in a manner that is consistent
47 with the dependency requirements.  And the SVN commit timestamps
48 should recreate the time of the CVS commit as far as possible without
49 violating the monotonicity requirement.
51 The basic idea of the conversion is this: create the largest
52 conceivable changesets, then split up changesets as necessary to break
53 any cycles in the graph of changeset dependencies.  When all cycles
54 have been removed, then do a topological sort of the changesets (with
55 ambiguities resolved using CVS timestamps) to determine a
56 self-consistent changeset commit order.
58 The quality of the conversion (not in terms of correctness, but in
59 terms of minimizing the number of svn commits) is mostly determined by
60 the cleverness of the heuristics used to split up cycles.  And all of
61 this has to be affordable, especially in terms of conversion time and
62 RAM usage, for even the largest CVS repositories.
65                             Implementation
66                             --------------
68 A cvs2svn run consists of a number of passes.  Each pass saves the
69 data it produces to files on disk, so that a) we don't hold huge
70 amounts of state in memory, and b) the conversion process is
71 resumable.
73 The intermediate files are referred to here by the symbolic constants
74 holding their filenames in config.py.
77 CollectRevsPass (formerly called pass1)
78 ===============
80 The goal of this pass is to collect from the CVS files all of the data
81 that will be required for the conversion.  If the --use-internal-co
82 option was used, this pass also collects the file delta data; for
83 -use-rcs or -use-cvs, the actual file contents are read again in
84 OutputPass.
86 To collect this data, we walk over the repository, collecting data
87 about the RCS files into an instance of CollectData.  Each RCS file is
88 processed with rcsparse.parse(), which invokes callbacks from an
89 instance of cvs2svn's _FileDataCollector class (which is a subclass of
90 rcsparse.Sink).
92 While a file is being processed, all of the data for the file (except
93 for contents and log messages) is held in memory.  When the file has
94 been read completely, its data is converted into an instance of
95 CVSFileItems, and this instance is manipulated a bit then pickled and
96 stored to CVS_ITEMS_STORE.
98 For each RCS file, the first thing the parser encounters is the
99 administrative header, including the head revision, the principal
100 branch, symbolic names, RCS comments, etc.  The main thing that
101 happens here is that _FileDataCollector.define_tag() is invoked on
102 each symbolic name and its attached revision, so all the tags and
103 branches of this file get collected.
105 Next, the parser hits the revision summary section.  That's the part
106 of the RCS file that looks like this:
108    1.6
109    date 2002.06.12.04.54.12;    author captnmark;       state Exp;
110    branches
111         1.6.2.1;
112    next 1.5;
114    1.5
115    date 2002.05.28.18.02.11;    author captnmark;       state Exp;
116    branches;
117    next 1.4;
119    [...]
121 For each revision summary, _FileDataCollector.define_revision() is
122 invoked, recording that revision's metadata in various variables of
123 the _FileDataCollector class instance.
125 Next, the parser encounters the *real* revision data, which has the
126 log messages and file contents.  For each revision, it invokes
127 _FileDataCollector.set_revision_info(), which sets some more fields in
128 _RevisionData.
130 When the parser is done with the file, _ProjectDataCollector takes the
131 resulting CVSFileItems object and manipulates it to handle some CVS
132 features:
134    - If the file had a vendor branch, make some adjustments to the
135      file dependency graph to reflect implicit dependencies related to
136      the vendor branch.  Also delete the 1.1 revision in the usual
137      case that it doesn't contain any useful information.
139    - If the file was added on a branch rather than on trunk, then
140      delete the "dead" 1.1 revision on trunk in the usual case that it
141      doesn't contain any useful information.
143    - If the file was added on a branch after it already existed on
144      trunk, then recent versions of CVS add an extra "dead" revision
145      on the branch.  Remove this revision in the usual case that it
146      doesn't contain any useful information, and sever the branch from
147      trunk (since the branch version is independent of the trunk
148      version).
150    - If the conversion was started with the --trunk-only option, then
152      1. graft any non-trunk default branch revisions onto trunk
153         (because they affect the history of the default branch), and
155      2. delete all branches and tags and all remaining branch
156         revisions.
158 Finally, the CVSFileItems instance is stored to a database and
159 statistics about how symbols were used in the file are recorded.
161 That's it -- the RCS file is done.
163 When every CVS file is done, CollectRevsPass is complete, and:
165    - The basic information about each project is stored to PROJECTS.
167    - The basic information about each file and directory (filename,
168      path, etc) is written as a pickled CVSPath instance to
169      CVS_PATHS_DB.
171    - Information about each symbol seen, along with statistics like
172      how often it was used as a branch or tag, is written as a pickled
173      symbol_statistics._Stat object to SYMBOL_STATISTICS.  This
174      includes the following information:
176          ID -- a unique positive identifying integer
178          NAME -- the symbol name
180          TAG_CREATE_COUNT -- the number of times the symbol was used
181              as a tag
183          BRANCH_CREATE_COUNT -- the number of times the symbol was
184              used as a branch
186          BRANCH_COMMIT_COUNT -- the number of files in which there was
187              a commit on a branch with this name.
189          BRANCH_BLOCKERS -- the set of other symbols that ever
190              sprouted from a branch with this name.  (A symbol cannot
191              be excluded from the conversion unless all of its
192              blockers are also excluded.)
194          POSSIBLE_PARENTS -- a count of in how many files each other
195              branch could have served as the symbol's source.
197      These data are used to look for inconsistencies in the use of
198      symbols under CVS and to decide which symbols can be excluded or
199      forced to be branches and/or tags.  The POSSIBLE_PARENTS data is
200      used to pick the "optimum" parent from which the symbol should
201      sprout in as many files as possible.
203      For a multiproject conversion, distinct symbol records (and IDs)
204      are created for symbols in separate projects, even if they have
205      the same name.  This is to prevent symbols in separate projects
206      from being filled at the same time.
208    - Information about each CVS event is converted into a CVSItem
209      instance and stored to CVS_ITEMS_STORE.  There are several types
210      of CVSItems:
212          CVSRevision -- A specific revision of a specific CVS file.
214          CVSBranch -- The creation of a branch tag in a specific CVS
215              file.
217          CVSTag -- The creation of a non-branch tag in a specific CVS
218              file.
220      The CVSItems are grouped into CVSFileItems instances, one per
221      CVSFile.  But a multi-file commit will still be scattered all
222      over the place.
224    - Selected metadata for each CVS revision, including the author and
225      log message, is written to METADATA_INDEX_TABLE and
226      METADATA_STORE.  The purpose is twofold: first, to save space by
227      not having to save this information multiple times, and second
228      because CVSRevisions that have the same metadata are candidates
229      to be combined into an SVN changeset.
231      First, an SHA digest is created for each set of metadata.  The
232      digest is constructed so that CVSRevisions that can be combined
233      are all mapped to the same digest.  CVSRevisions that were part
234      of a single CVS commit always have a common author and log
235      message, therefore these fields are always included in the
236      digest.  Moreover:
238      - if ctx.cross_project_commits is False, we avoid combining CVS
239        revisions from separate projects by including the project.id in
240        the digest.
242      - if ctx.cross_branch_commits is False, we avoid combining CVS
243        revisions from different branches by including the branch name
244        in the digest.
246      During the database creation phase, the database keeps track of a
247      map
249        digest (20-byte string) -> metadata_id (int)
251      to allow the record for a set of metadata to be located
252      efficiently.  As data are collected, it stores a map
254        metadata_id (int) -> (author, log_msg,) (tuple)
256      into the database for use in future passes.  CVSRevision records
257      include the metadata_id.
259 During this run, each CVSFile, Symbol, CVSItem, and metadata record is
260 assigned an arbitrary unique ID that is used throughout the conversion
261 to refer to it.
264 CleanMetadataPass
265 =================
267 Encode the cvs revision metadata as UTF-8, ensuring that all entries
268 can be decoded using the chosen encodings.  Output the results to
269 METADATA_CLEAN_INDEX_TABLE and METADATA_CLEAN_STORE.
272 CollateSymbolsPass
273 ==================
275 Use the symbol statistics collected in CollectRevsPass and any runtime
276 options to determine which symbols should be treated as branches,
277 which as tags, and which should be excluded from the conversion
278 altogether.
280 Create SYMBOL_DB, which contains a pickle of a list of TypedSymbol
281 (Branch, Tag, or ExcludedSymbol) instances indicating how each symbol
282 should be processed in the conversion.  The IDs used for a TypedSymbol
283 is the same as the ID allocated to the corresponding symbol in
284 CollectRevsPass, so references in CVSItems do not have to be updated.
287 FilterSymbolsPass
288 =================
290 This pass works through the CVSFileItems instances stored in
291 CVS_ITEMS_STORE, processing all of the items from each file as a
292 group.  (This is the last pass in which all of the CVSItems for a file
293 are in memory at once.)  It does the following things:
295    - Exclude any symbols that CollateSymbolsPass determined should be
296      excluded, and any revisions on such branches.  Also delete
297      references from other CVSItems to those that are being deleted.
299    - Transform any branches to tags or vice versa, also depending on
300      the results of CollateSymbolsPass, and fix up the references from
301      other CVSItems.
303    - Decide what line of development to use as the parent for each
304      symbol in the file, and adjust the file's dependency tree
305      accordingly.
307    - For each CVSRevision, record the list of symbols that the
308      revision opens and closes.
310    - Write each surviving CVSRevision to CVS_REVS_DATAFILE.  Each line
311      of the file has the format
313          METADATA_ID TIMESTAMP CVS_REVISION
315      where TIMESTAMP is a fixed-width timestamp, and CVS_REVISION is
316      the pickled CVSRevision in a format that does not contain any
317      newlines.  These summaries will be sorted in SortRevisionsPass
318      then used by InitializeChangesetsPass to create preliminary
319      RevisionChangesets.
321    - Write the CVSSymbols to CVS_SYMBOLS_DATAFILE.  Each line of the
322      file has the format
324          SYMBOL_ID CVS_SYMBOL
326      where CVS_SYMBOL is the pickled CVSSymbol in a format that does
327      not contain any newlines.  This information will be sorted by
328      SYMBOL_ID in SortSymbolsPass then used to create preliminary
329      SymbolChangesets.
331    - Invokes callback methods of the registered RevisionCollector.
332      The purpose of RevisionCollectors and RevisionReaders is
333      documented in the file revision-reader.txt.
336 SortRevisionsPass
337 =================
339 Sort CVS_REVS_DATAFILE (written by FilterSymbolsPass), creating
340 CVS_REVS_SORTED_DATAFILE.  The sort groups items that might be added
341 to the same changeset together and, within a group, sorts revisions by
342 timestamp.  This step makes it easy for InitializeChangesetsPass to
343 read the initial draft of RevisionChangesets straight from the file.
346 SortSymbolsPass
347 ===============
349 Sort CVS_SYMBOLS_DATAFILE (written by FilterSymbolsPass), creating
350 CVS_SYMBOLS_SORTED_DATAFILE.  The sort groups together symbol items
351 that might be added to the same changeset (though not in anything
352 resembling chronological order).  The output of this pass is used by
353 InitializeChangesetsPass.
356 InitializeChangesetsPass
357 ========================
359 This pass creates first-draft changesets, splitting them using
360 COMMIT_THRESHOLD and breaking up any revision changesets that have
361 internal dependencies.
363 The raw material for creating revision changesets is
364 CVS_REVS_SORTED_DATAFILE, which already has CVSRevisions sorted in
365 such a way that potential changesets are grouped together and sorted
366 by date.  The contents of this file are read line by line, and the
367 corresponding CVSRevisions are accumulated into a changeset.  Whenever
368 the metadata_id changes, or whenever there is a time gap of more than
369 COMMIT_THRESHOLD (currently set to 5 minutes) between CVSRevisions,
370 then a new changeset is started.
372 At this point a revision changeset can have internal dependencies if
373 two commits were made to the same file with the same log message
374 within COMMIT_THRESHOLD of each other.  The next job of this pass is
375 to split up changesets in such a way to break such internal
376 dependencies.  This is done by sorting the CVSRevisions within a
377 changeset by timestamp, then choosing the split point that breaks the
378 most internal dependencies.  This procedure is continued recursively
379 until there are no more dependencies internal to a single changeset.
381 Analogously, the CVSSymbol items from CVS_SYMBOLS_SORTED_DATAFILE are
382 grouped into symbol changesets.  (Symbol changesets cannot have
383 internal dependencies, so there is no need to break them up at this
384 stage.)
386 Finally, this pass writes a CVSItem database with the CVSItems written
387 in order grouped by the preliminary changeset to which they belong.
388 Even though the preliminary changesets still have to be split up to
389 form final changesets, grouping the CVSItems this way improves the
390 locality of disk accesses and thereby speeds up later passes.
392 The result of this pass is two databases:
394    - CVS_ITEM_TO_CHANGESET, which maps CVSItem ids to the id of the
395      changeset containing the item, and
397    - CHANGESETS_STORE and CHANGESETS_INDEX, which contain the
398      changeset objects themselves, indexed by changeset id.
400    - CVS_ITEMS_SORTED_STORE and CVS_ITEMS_SORTED_INDEX_TABLE, which
401      contain the pickled CVSItems ordered by changeset.
404 BreakRevisionChangesetCyclesPass
405 ================================
407 There can still be cycles in the dependency graph of
408 RevisionChangesets caused by:
410    - Interleaved commits.  Since CVS commits are not atomic, it can
411      happen that two commits are in progress at the same time and each
412      alters the same two files, but in different orders.  These should
413      be small cycles involving only a few revision changesets.  To
414      resolve these cycles, one or more of the RevisionChangesets have
415      to be split up (eventually becoming separate svn commits).
417    - Cycles involving a RevisionChangeset formed by the accidental
418      combination of unrelated items within a short period of time that
419      have the same author and log message.  These should also be small
420      cycles involving only a few changesets.
422 The job of this pass is to break up such cycles (those involving only
423 CVSRevisions).
425 This pass works by building up the graph of revision changesets and
426 their dependencies in memory, then attempting a topological sort of
427 the changesets.  Whenever the topological sort stalls, that implies
428 the existence of a cycle, one of which can easily be determined.  This
429 cycle is broken through the use of heuristics that try to determine an
430 "efficient" way of splitting one or more of the changesets that are
431 involved.
433 The new RevisionChangesets are written to
434 CVS_ITEM_TO_CHANGESET_REVBROKEN, CHANGESETS_REVBROKEN_STORE, and
435 CHANGESETS_REVBROKEN_INDEX, along with the unmodified
436 SymbolChangesets.  These files are in the same format as the analogous
437 files produced by InitializeChangesetsPass.
440 RevisionTopologicalSortPass
441 ===========================
443 Topologically sort the RevisionChangesets, thereby picking the order
444 in which the RevisionChangesets will be committed.  (Since the
445 previous pass eliminated any dependency cycles, this sort is
446 guaranteed to succeed.)  Ambiguities in the topological sort are
447 resolved using the changesets' timestamps.  Then simplify the
448 changeset graph into a linear chain by converting each
449 RevisionChangeset into an OrderedChangeset that stores dependency
450 links only to its commit-order predecessor and successor.  This
451 simplified graph enforces the commit order that resulted from the
452 topological sort, even after the SymbolChangesets are added back into
453 the graph later.  Store the OrderedChangesets into
454 CHANGESETS_REVSORTED_STORE and CHANGESETS_REVSORTED_INDEX along with
455 the unmodified SymbolChangesets.
458 BreakSymbolChangesetCyclesPass
459 ==============================
461 It is possible for there to be cycles in the graph of SymbolChangesets
462 caused by:
464    - Split creation of branches.  It is possible that branch A depends
465      on branch B in one file, but B depends on A in another file.
466      These cycles can be large, but they only involve
467      SymbolChangesets.
469 Break up such dependency loops.  Output the results to
470 CVS_ITEM_TO_CHANGESET_SYMBROKEN, CHANGESETS_SYMBROKEN_STORE, and
471 CHANGESETS_SYMBROKEN_INDEX.
474 BreakAllChangesetCyclesPass
475 ===========================
477 The complete changeset graph (including both RevisionChangesets and
478 BranchChangesets) can still have dependency cycles cause by:
480    - Split creation of branches.  The same branch tag can be added to
481      different files at completely different times.  It is possible
482      that the revision that was branched later depends on a
483      RevisionChangeset that involves a file on the branch that was
484      created earlier.  These cycles can be large, but they always
485      involve a SymbolChangeset.  To resolve these cycles, the
486      SymbolChangeset is split up into two changesets.
488 In fact, tag changesets do not have to be considered--CVSTags cannot
489 participate in dependency cycles because no other CVSItem can depend
490 on a CVSTag.
492 Since the input of this pass has been through
493 RevisionTopologicalSortPass, all revision cycles have already been
494 broken up and the order that the RevisionChangesets will be committed
495 has been determined.  In this pass, the complete changeset graph is
496 created in memory, including the linear list of OrderedChangesets from
497 RevisionTopologicalSortPass plus all of the symbol changesets.
498 Because this pass doesn't break up any OrderedChangesets, it is
499 constrained to finding places within the revision changeset sequence
500 in which the symbol changeset commits can be inserted.
502 The new changesets are written to CVS_ITEM_TO_CHANGESET_ALLBROKEN,
503 CHANGESETS_ALLBROKEN_STORE, and CHANGESETS_ALLBROKEN_INDEX, which are
504 in the same format as the analogous files produced by
505 InitializeChangesetsPass.
508 TopologicalSortPass
509 ===================
511 Now that the earlier passes have broken up any dependency cycles among
512 the changesets, it is possible to order all of the changesets in such
513 a way that all of a changeset's dependencies are committed before the
514 changeset itself.  This pass does so by again building up the graph of
515 changesets in memory, then at each step picking a changeset that has
516 no remaining dependencies and removing it from the graph.  Whenever
517 more than one dependency-free changeset is available, symbol
518 changesets are chosen before revision changesets.  As changesets are
519 processed, the timestamp sequence is ensured to be monotonic by the
520 simple expedient of adjusting retrograde timestamps to be later than
521 their predecessor.  Timestamps that lie in the future, on the other
522 hand, are assumed to be bogus and are adjusted backwards, also to be
523 just later than their predecessor.
525 This pass writes a line to CHANGESETS_SORTED_DATAFILE for each
526 RevisionChangeset, in the order that the changesets should be
527 committed.  Each lines contains
529     CHANGESET_ID TIMESTAMP
531 where CHANGESET_ID is the id of the changeset in the
532 CHANGESETS_ALLBROKEN_* databases and TIMESTAMP is the timstamp that
533 should be assigned to it when it is committed.  Both values are
534 written in hexadecimal.
537 CreateRevsPass (formerly called pass5)
538 ==============
540 This pass generates SVNCommits from Changesets and records symbol
541 openings and closings.  (One Changeset can result in multiple
542 SVNCommits, for example if it causes symbols to be filled or copies to
543 a vendor branch.)
545 This pass does the following:
547 1. Creates a database file to map Subversion revision numbers to
548    SVNCommit instances (SVN_COMMITS_STORE and
549    SVN_COMMITS_INDEX_TABLE).  Creates another database file to map CVS
550    Revisions to their Subversion Revision numbers
551    (CVS_REVS_TO_SVN_REVNUMS).
553 2. When a file is copied to a symbolic name in cvs2svn, it is copied
554    from a specific source: either a CVSRevision, or a copy created by
555    a previous CVSBranch of the file.  The copy has to be made from an
556    SVN revision that is during the lifetime of the source.  The SVN
557    revision when the source was created is called the symbol's
558    "opening", and the SVN revision when it was deleted or overwritten
559    is called the symbol's "closing".  In this pass, the
560    SymbolingsLogger class writes out a line to
561    SYMBOL_OPENINGS_CLOSINGS for each symbol opening or closing.  Note
562    that some openings do not have closings, namely if the
563    corresponding source is still present at the HEAD revision.
565    The format of each line is:
567        SYMBOL_ID SVN_REVNUM TYPE CVS_SYMBOL_ID
569    For example:
571        1c 234 O 1a7
572        34 245 O 1a9
573        18a 241 C 1a7
574        122 201 O 1b3
576    Here is what the columns mean:
578    SYMBOL_ID -- The id of the branch or tag that has an opening in
579        this SVN_REVNUM, in hexadecimal.
581    SVN_REVNUM -- The Subversion revision number in which the opening
582        or closing occurred.  (There can be multiple openings and
583        closings per SVN_REVNUM).
585    TYPE -- "O" for openings and "C" for closings.
587    CVS_SYMBOL_ID -- The id of the CVSSymbol instance whose opening or
588        closing is being described, in hexadecimal.
590    Each CVSSymbol that tags a non-dead file has exactly one opening
591    and either zero or one closing.  The closing, if it exists, always
592    occurs in a later SVN revision than the opening.
594    See SymbolingsLogger for more details.
597 SortSymbolOpeningsClosingsPass (formerly called pass6)
598 ==============================
600 This pass sorts SYMBOL_OPENINGS_CLOSINGS into
601 SYMBOL_OPENINGS_CLOSINGS_SORTED.  This orders the file first by symbol
602 ID, and second by Subversion revision number, thus grouping all
603 openings and closings for each symbolic name together.
606 IndexSymbolsPass (formerly called pass7)
607 ================
609 This pass iterates through all the lines in
610 SYMBOL_OPENINGS_CLOSINGS_SORTED, writing out a pickle file
611 (SYMBOL_OFFSETS_DB) mapping SYMBOL_ID to the file offset in
612 SYMBOL_OPENINGS_CLOSINGS_SORTED where SYMBOL_ID is first encountered.
613 This will allow us to seek to the various offsets in the file and
614 sequentially read only the openings and closings that we need.
617 OutputPass (formerly called pass8)
618 ==========
620 This pass opens the svn-commits database and sequentially plays out
621 all the commits to either a Subversion repository or to a dumpfile.
622 It also decides what sources to use to fill symbols.
624 In --dumpfile mode, the result of this pass is a Subversion repository
625 dumpfile (suitable for input to 'svnadmin load').  The dumpfile is the
626 data's last static stage: last chance to check over the data, run it
627 through svndumpfilter, move the dumpfile to another machine, etc.
629 When not in --dumpfile mode, no full dumpfile is created.  Instead,
630 miniature dumpfiles representing a single revisions are created,
631 loaded into the repository, and then removed.
633 In both modes, the dumpfile revisions are created by walking through
634 the SVN_COMMITS_* database.
636 The database in MIRROR_NODES_STORE and MIRROR_NODES_INDEX_TABLE holds
637 a skeletal mirror of the repository structure at each SVN revision.
638 This mirror keeps track of which files existed on each LOD, but does
639 not record any file contents.  cvs2svn requires this information to
640 decide which paths to copy when filling branches and tags.
642 When .cvsignore files are modified, cvs2svn computes the corresponding
643 svn:ignore properties and applies the properties to the parent
644 directory.  The .cvsignore files themselves are not included in the
645 output unless the --keep-cvsignore option was specified.  But in
646 either case, the .cvsignore files are recorded within the repository
647 mirror as if they were being written to disk, to ensure that the
648 containing directory is not pruned if the directory in CVS still
649 contained a .cvsignore file.
652                   ===============================
653                       Branches and Tags Plan.
654                   ===============================
656 This pass is also where tag and branch creation is done.  Since
657 subversion does tags and branches by copying from existing revisions
658 (then maybe editing the copy, making subcopies underneath, etc), the
659 big question for cvs2svn is how to achieve the minimum number of
660 operations per creation.  For example, if it's possible to get the
661 right tag by just copying revision 53, then it's better to do that
662 than, say, copying revision 51 and then sub-copying in bits of
663 revision 52 and 53.
665 Tags are created as soon as cvs2svn encounters the last CVS Revision
666 that is a source for that tag.  The whole tag is created in one
667 Subversion commit.
669 Branches are created as soon as all of their prerequisites are in
670 place.  If a branch creation had to be broken up due to dependency
671 cycles, then non-final parts are also created as soon as their
672 prerequisites are ready.  In such a case, the SymbolChangeset
673 specifies how much of the branch can be created in each step.
675 How just-in-time branch creation works:
677 In order to make the "best" set of copies/deletes when creating a
678 branch, cvs2svn keeps track of two sets of trees while it's making
679 commits:
681    1. A skeleton mirror of the subversion repository, that is, a
682       record of which file existed on which LOD for each SVN revision.
684    2. A tree for each CVS symbolic name, and the svn file/directory
685       revisions from which various parts of that tree could be copied.
687 Each LOD is recorded as a tree using the following schema: unique keys
688 map to marshal.dumps() representations of dictionaries, which in turn
689 map path component names to other unique keys:
691    root_key  ==> { entryname1 : entrykey1, entryname2 : entrykey2, ... }
692    entrykey1 ==> { entrynameX : entrykeyX, ... }
693    entrykey2 ==> { entrynameY : entrykeyY, ... }
694    entrykeyX ==> { etc, etc ...}
695    entrykeyY ==> { etc, etc ...}
697 (The leaf nodes -- files -- are represented by None.)
699 The repository mirror allows cvs2svn to remember what paths exist in
700 what revisions.
702 For details on how branches and tags are created, please see the
703 docstring the SymbolingsLogger class (and its methods).