doc/symbol-notes.txt

   1 This is a description of how symbols (tags and branches) are handled
   2 by cvs2svn, determined by reading the code.
   3
   4
   5 Notation
   6 ========
   7
   8     CVSFile -- a single file within the CVS repository.  This object
   9         basically only records the filename of the corresponding RCS
  10         file, and the relative filename that this file will have
  11         within the SVN repository.  A single CVSFile object is used
  12         for all of the CVSItems on all lines of development related to
  13         that file.
  14
  15
  16 The following terms and the corresponding classes represent
  17 project-wide concepts.  For example, a project will only have a single
  18 Branch named "foo" even if many files appear on that branch.  Each of
  19 these objects is assigned a unique integer ID during CollectRevsPass
  20 which is preserved during the entire conversion (even if, say, a
  21 Branch is mutated into a Tag).
  22
  23     Trunk -- the main line of development for a particular Project in
  24         CVS.  The Trunk class inherits from LineOfDevelopment.
  25
  26     Symbol -- a Branch or a Tag within a particular Project (see
  27         below).  Instances of this class are also used to represent
  28         symbols early in the conversion, before it has been decided
  29         whether to convert the symbol as a Branch or as a Tag.  A
  30         Symbol contains an id, a Project, and a name.
  31
  32     Branch -- a symbol within a particular Project that will be
  33         treated as a branch in SVN.  Usually corresponds to a branch
  34         tag in CVS, but might be a non-branch tag that was mutated in
  35         CollateSymbolsPass.  In SVN, this will correspond to a
  36         subdirectory of the project's "branches" directory.  The
  37         Branch class inherits from Symbol and from LineOfDevelopment.
  38
  39     Tag -- a symbol within a particular Project that will be treated
  40         as a tag in SVN.  Usually corresponds to a non-branch tag in
  41         CVS, but might be a branch tag that was mutated in
  42         CollateSymbolsPass.  In SVN, this will correspond to a
  43         subdirectory of the project's "tags" directory.  The Tags
  44         class inherits from Symbol and from LineOfDevelopment.
  45
  46     ExcludedSymbol -- a CVS symbol that will be excluded from the
  47         cvs2svn output.
  48
  49     LineOfDevelopment -- a Trunk, Branch, or Tag.
  50
  51
  52 The following terms and the corresponding classes represent particular
  53 CVS events in particular CVS files.  For example, the CVSBranch
  54 representing the creation of Branch "foo" in one file will be distinct
  55 from the CVSBranch representing the creation of branch "foo" in
  56 another file, even if the two files are in the same Project.  Each
  57 CVSItem is assigned a unique integer ID during CollectRevsPass which
  58 is preserved during the entire conversion (even if, say, a CVSBranch
  59 is mutated into a CVSTag).
  60
  61     CVSItem -- abstract base class representing any discernible event
  62         within a single RCS file, for example the creation of revision
  63         1.6, or the tagging of the file with tag "bar".  Each CVSItem
  64         has a unique integer ID.
  65
  66     CVSRevision -- a particular revision within a particular file
  67         (e.g., file.txt:1.6).  A CVSRevision occurs on a particular
  68         LineOfDevelopment.  CVSRevision inherits from CVSItem.
  69
  70     CVSSymbol -- a CVSBranch or CVSTag (see below).  CVSSymbol
  71         inherits from CVSItem.
  72
  73     CVSBranch -- the creation of a particular Branch on a particular
  74         file.  A CVSBranch has a Symbol instance telling the Symbol
  75         associated with the branch, and also records the
  76         LineOfDevelopment from which the branch was created.  In the
  77         SVN repository, a CVSBranch corresponds to an "svn copy" of a
  78         file to a subdirectory of the project's "branches" directory.
  79         CVSBranch inherits from CVSSymbol.
  80
  81     CVSTag -- the creation of a particular Tag on a particular file.
  82         A CVSTag has a Symbol instance telling the Symbol associated
  83         with the tag, and also records the LineOfDevelopment from
  84         which the tag was created.  In the SVN repository, a CVSTag
  85         corresponds to an "svn copy" of a file to a subdirectory of
  86         the project's "tags" directory.  CVSTag inherits from
  87         CVSSymbol.
  88
  89
  90 CollectRevsPass
  91 ===============
  92
  93 Collect all information about CVS tags and branches from the CVS
  94 repository.
  95
  96 For each project, create a Trunk object to represent the trunk line of
  97 development for that project.  The Trunk object for one Project is
  98 distinct from the Trunk objects for other Projects.  For each symbol
  99 name seen in each project, create a Symbol object.  The Symbol object
 100 contains its id, project, and name.
 101
 102 The very first thing that is done when a symbol is read is that the
 103 Project's symbol transform rules are given a chance to transform the
 104 symbol name (or even cause it to be discarded).  The result of the
 105 transformation is used as the symbol name in the rest of the program.
 106 Because this transformation process is so low-level, it is capable of
 107 making a more fundamental kind of change than the symbol strategy
 108 rules that come later:
 109
 110   * Symbols can be renamed.
 111
 112   * Symbols can be fully discarded, as if they never appeared in the
 113     CVS repository.  This can even be done for a malformed symbol or
 114     for a branch symbol that refers to the same branch as another
 115     branch symbol (which would otherwise be a fatal error).
 116
 117   * Two distinct symbols in different files within the same project
 118     can be transformed to the same name, in which case they are
 119     treated as a single symbol.
 120
 121   * Two distinct symbols within a single file can be transformed to
 122     the same name, provided they refer to the same revision number.
 123     This effectively discards one of the symbols.
 124
 125   * Two symbols with the same name in different files can be given
 126     distinct names, in which case they are treated as completely
 127     separate symbols.
 128
 129 For each Symbol object, collect the following statistics:
 130
 131   * In how many files was the symbol used as a branch and in how many
 132     was it used as a tag.
 133
 134   * In how many files was there a commit on a branch with that name.
 135
 136   * Which other symbols branched off of a branch with that name.
 137
 138   * In how many files could each other line of development have served
 139     as the source of this symbol.  These are called the "possible
 140     parents" of the symbol.
 141
 142 These statistics are used in CollateSymbolsPass to determine which
 143 symbols can be excluded or converted from tags to branches or vice
 144 versa.
 145
 146 The possible parents information is important because CVS is ambiguous
 147 about what line of development was the source of a branch.  A branch
 148 numbered 1.3.6 might have been created from trunk (revision 1.3), from
 149 branch 1.3.2, or from branch 1.3.4; it is simply impossible to tell
 150 based on the information in a single RCS file.
 151
 152 [Actually, the situation is even more confusing.  If a branch tag is
 153 deleted from CVS, the branch number is recycled.  So it is even
 154 possible that branch 1.3.6 was created from branch 1.3.8 or 1.3.10 or
 155 ...  We address this confusion by noting the order that the branches
 156 were listed in the RCS file header.  It appears that CVS lists
 157 branches in the header in reverse chronological order of creation.]
 158
 159 For each tag seen within each file, create a CVSTag object recording
 160 its id, CVSFile, Symbol, and the id of the CVSRevision being tagged.
 161
 162 For each branch seen within each file, create a CVSBranch object
 163 recording an id, CVSFile, Symbol, the branch number (e.g., '1.4.2'),
 164 the id of the CVSRevision from which the branch sprouts, and the id of
 165 the first CVSRevision on the branch (if any).
 166
 167 For each revision seen within each file, create a CVSRevision object
 168 recording (among other things) and id, the line of development (trunk
 169 or branch) on which the revision appeared, a list of ids of CVSTags
 170 tagging the revision, and a list of ids of CVSBranches sprouting from
 171 the revision.
 172
 173 This pass also adjusts the CVS dependency tree to work around some CVS
 174 quirks.  (See design-notes.txt for the details.)  These adjustments
 175 can result in CVSBranches being deleted, for example, if a file was
 176 added on a branch.  In such a case, any CVSRevisions that were
 177 previously on the branch will be created by adding the file to the
 178 branch directory, rather than copying the file from the source
 179 directory to the branch directory.
 180
 181
 182 CollateSymbolsPass
 183 ==================
 184
 185 Allow the project's symbol strategy rules to affect how symbols are
 186 converted:
 187
 188   * A symbol can be excluded from the conversion output (as long as
 189     there are no other non-excluded symbols that depend on it).  In
 190     this case, the Symbol will be converted into an ExcludedSymbol
 191     instance.
 192
 193   * A tag symbol can be converted as a branch.  In this case, the
 194     Symbol will be converted into a Branch instance.
 195
 196   * A branch symbol can be converted as a tag, provided there were
 197     never any commits on the branch.  In this case, the Symbol will be
 198     converted into a Tag instance.
 199
 200   * The SVN path where a symbol will be placed is determined.
 201     Typically, symbols are laid out in the standard
 202     trunk/branches/tags Subversion repository layout, but strategy
 203     rules can in fact place symbols arbitrarily.
 204
 205   * The preferred parent of each symbol is determined.  The preferred
 206     parent of a Symbol is chosen to be the line of development that
 207     appeared as a possible parent of this symbol in the most CVSFiles.
 208
 209 This pass creates the symbol database, SYMBOL_DB, which is accessed in
 210 later passes via the SymbolDatabase class.  The SymbolDatabase
 211 contains TypedSymbol (Branch, Tag, or ExcludedSymbol) instances
 212 indicating how each symbol should be processed in the conversion.  The
 213 ID used for a TypedSymbol is the same as the ID allocated to the
 214 corresponding symbol in CollectRevsPass, so references in CVSItems do
 215 not have to be updated.
 216
 217
 218 FilterSymbolsPass
 219 =================
 220
 221 Iterate through all of the CVSItems, mutating CVSTags to CVSBranches
 222 and vice versa and excluding other CVSSymbols as specified by the
 223 types of the TypedSymbols in the SymbolDatabase.  Additionally, filter
 224 out any CVSRevisions that reside on excluded CVSBranches.
 225
 226 Write a line of text to CVS_SYMBOLS_DATAFILE for each surviving
 227 CVSSymbol, containing its Symbol id and a pickled version of the
 228 CVSSymbol.  (This file will be sorted in SortSymbolSummaryPass then
 229 used in InitializeChangesetsPass to create SymbolChangesets.)
 230
 231 Also adjust the file's dependency tree by grafting CVSSymbols onto
 232 their preferred parents.  This is not always possible; if not, leave
 233 the CVSSymbol where it was.
 234
 235 Finally, record symbol "openings" and "closings".  A CVSSymbol is
 236 considered "opened" by the CVSRevision or CVSBranch from which the
 237 CVSSymbol sprouts.  A CVSSymbol is considered "closed" by the
 238 CVSRevision that overwrites or deletes the CVSSymbol's opening.
 239 (Every CVSSymbol has an opening, but not all of them have closings;
 240 for example, the opening CVSRevision might still exist at HEAD.)
 241 Record in each CVSRevision and CVSBranch a list of all of the
 242 CVSSymbols that it opens.  Record in each CVSRevision a list of all of
 243 the CVSSymbols that it closes (CVSBranches cannot close CVSSymbols).
 244
 245
 246 SortRevisionSummaryPass
 247 =======================
 248
 249 N/A
 250
 251
 252 SortSymbolSummaryPass
 253 =====================
 254
 255 Sort CVS_SYMBOLS_DATAFILE, creating CVS_SYMBOLS_SORTED_DATAFILE.  The
 256 sort groups together symbol items that might be added to the same
 257 SymbolChangeset.
 258
 259
 260 InitializeChangesetsPass
 261 ========================
 262
 263 Read CVS_SYMBOLS_SORTED_DATAFILE, grouping CVSSymbol items with the
 264 same Symbol id into SymbolChangesets.
 265
 266
 267 BreakCVSRevisionChangesetCyclesPass
 268 ==================================
 269
 270 N/A
 271
 272
 273 RevisionTopologicalSortPass
 274 ===========================
 275
 276 N/A
 277
 278
 279 BreakCVSSymbolChangesetCyclesPass
 280 ================================
 281
 282 Read in the changeset graph consisting only of SymbolChangesets and
 283 break any cycles that are found by breaking up symbol changesets.
 284
 285
 286 BreakAllChangesetCyclesPass
 287 ================================
 288
 289 Read in the entire changeset graph and break any cycles that are found
 290 by breaking up symbol changesets.
 291
 292
 293 TopologicalSortPass
 294 ===================
 295
 296 Update the conversion statistics with excluded symbols omitted.
 297
 298
 299 CreateRevsPass
 300 ==============
 301
 302 Create SVNCommits and assign svn revision numbers to each one.  Create
 303 a database (SVN_COMMITS_DB) to map svn revision numbers to SVNCommits
 304 and another (CVS_REVS_TO_SVN_REVNUMS) to map each CVSRevision id to
 305 the number of the svn revision containing it.
 306
 307 Also, SymbolingsLogger writes a line to SYMBOL_OPENINGS_CLOSINGS for
 308 each opening or closing for each CVSSymbol, noting in what SVN
 309 revision the opening or closing occurred.
 310
 311
 312 SortSymbolsPass
 313 ===============
 314
 315 This pass sorts SYMBOL_OPENINGS_CLOSINGS into
 316 SYMBOL_OPENINGS_CLOSINGS_SORTED.  This orders the file first by symbol
 317 ID, and second by Subversion revision number, thus grouping all
 318 openings and closings for each symbolic name together.
 319
 320
 321 IndexSymbolsPass
 322 ================
 323
 324 Iterate through all the lines in SYMBOL_OPENINGS_CLOSINGS_SORTED,
 325 writing out a pickled map to SYMBOL_OFFSETS_DB telling at what offset
 326 in SYMBOL_OPENINGS_CLOSINGS_SORTED the lines corresponding to each
 327 Symbol begin.  This will allow us to seek to the various offsets in
 328 the file and sequentially read only the openings and closings that we
 329 need.
 330
 331
 332 OutputPass
 333 ==========
 334
 335 The filling of a symbol is triggered when SVNSymbolCommit.commit()
 336 calls SVNRepositoryMirror.fill_symbol().  The SVNSymbolCommit contains
 337 the list of CVSSymbols that have to be copied to a symbol directory in
 338 this revision.  However, we still have to do a lot of work to figure
 339 out what SVN revision number to use as the source of these copies, and
 340 also to group file copies together into directory copies when
 341 possible.
 342
 343 The SYMBOL_OPENINGS_CLOSINGS_SORTED file lists the opening and closing
 344 SVN revision of each revision that has to be copied to the symbol
 345 directory.  We use this information to try to find SVN revision
 346 numbers that can serve as the source for as many files as possible, to
 347 avoid having to pick and choose sources from many SVN revisions.
 348
 349 Furthermore, when a bunch of files in a directory have to be copied at
 350 the same time, it is cheaper to copy the directory as a whole.  But if
 351 not *all* of the files within the directory had to be copied, then the
 352 unneeded files have to be deleted again from the copied directory.  Or
 353 if some of the files have to be copied from different source SVN
 354 revision numbers, then those files have to be overwritten in the
 355 copied directory with the correct versions.
 356
 357 Finally, it can happen that a single Symbol has to be filled multiple
 358 times (because the initial SymbolChangeset had to be broken up).  In
 359 this case, the first fill can copy the source directory to the
 360 destination directory (maybe with fixups), but subsequent copies have
 361 to copy individual files to avoid overwriting content that is already
 362 present in the destination directory.
 363
 364 To figure all of this out, we need to know all of the files that
 365 existed in every previous SVN revision, in every line of development.
 366 This is done using the SVNRepositoryMirror class, which keeps a
 367 skeleton record of the entire SVN history in a database using data
 368 structures similar to those used by SVN itself.
 369
 370