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 CleanMetadataPass
 183 =================
 184
 185 N/A
 186
 187
 188 CollateSymbolsPass
 189 ==================
 190
 191 Allow the project's symbol strategy rules to affect how symbols are
 192 converted:
 193
 194   * A symbol can be excluded from the conversion output (as long as
 195     there are no other non-excluded symbols that depend on it).  In
 196     this case, the Symbol will be converted into an ExcludedSymbol
 197     instance.
 198
 199   * A tag symbol can be converted as a branch.  In this case, the
 200     Symbol will be converted into a Branch instance.
 201
 202   * A branch symbol can be converted as a tag, provided there were
 203     never any commits on the branch.  In this case, the Symbol will be
 204     converted into a Tag instance.
 205
 206   * The SVN path where a symbol will be placed is determined.
 207     Typically, symbols are laid out in the standard
 208     trunk/branches/tags Subversion repository layout, but strategy
 209     rules can in fact place symbols arbitrarily.
 210
 211   * The preferred parent of each symbol is determined.  The preferred
 212     parent of a Symbol is chosen to be the line of development that
 213     appeared as a possible parent of this symbol in the most CVSFiles.
 214
 215 This pass creates the symbol database, SYMBOL_DB, which is accessed in
 216 later passes via the SymbolDatabase class.  The SymbolDatabase
 217 contains TypedSymbol (Branch, Tag, or ExcludedSymbol) instances
 218 indicating how each symbol should be processed in the conversion.  The
 219 ID used for a TypedSymbol is the same as the ID allocated to the
 220 corresponding symbol in CollectRevsPass, so references in CVSItems do
 221 not have to be updated.
 222
 223
 224 FilterSymbolsPass
 225 =================
 226
 227 Iterate through all of the CVSItems, mutating CVSTags to CVSBranches
 228 and vice versa and excluding other CVSSymbols as specified by the
 229 types of the TypedSymbols in the SymbolDatabase.  Additionally, filter
 230 out any CVSRevisions that reside on excluded CVSBranches.
 231
 232 Write a line of text to CVS_SYMBOLS_DATAFILE for each surviving
 233 CVSSymbol, containing its Symbol id and a pickled version of the
 234 CVSSymbol.  (This file will be sorted in SortSymbolsPass then used in
 235 InitializeChangesetsPass to create SymbolChangesets.)
 236
 237 Also adjust the file's dependency tree by grafting CVSSymbols onto
 238 their preferred parents.  This is not always possible; if not, leave
 239 the CVSSymbol where it was.
 240
 241 Finally, record symbol "openings" and "closings".  A CVSSymbol is
 242 considered "opened" by the CVSRevision or CVSBranch from which the
 243 CVSSymbol sprouts.  A CVSSymbol is considered "closed" by the
 244 CVSRevision that overwrites or deletes the CVSSymbol's opening.
 245 (Every CVSSymbol has an opening, but not all of them have closings;
 246 for example, the opening CVSRevision might still exist at HEAD.)
 247 Record in each CVSRevision and CVSBranch a list of all of the
 248 CVSSymbols that it opens.  Record in each CVSRevision a list of all of
 249 the CVSSymbols that it closes (CVSBranches cannot close CVSSymbols).
 250
 251
 252 SortRevisionsPass
 253 =================
 254
 255 N/A
 256
 257
 258 SortSymbolsPass
 259 ===============
 260
 261 Sort CVS_SYMBOLS_DATAFILE, creating CVS_SYMBOLS_SORTED_DATAFILE.  The
 262 sort groups together symbol items that might be added to the same
 263 SymbolChangeset.
 264
 265
 266 InitializeChangesetsPass
 267 ========================
 268
 269 Read CVS_SYMBOLS_SORTED_DATAFILE, grouping CVSSymbol items with the
 270 same Symbol id into SymbolChangesets.
 271
 272
 273 BreakRevisionChangesetCyclesPass
 274 ================================
 275
 276 N/A
 277
 278
 279 RevisionTopologicalSortPass
 280 ===========================
 281
 282 N/A
 283
 284
 285 BreakSymbolChangesetCyclesPass
 286 ==============================
 287
 288 Read in the changeset graph consisting only of SymbolChangesets and
 289 break up symbol changesets as necessary to break any cycles that are
 290 found.
 291
 292
 293 BreakAllChangesetCyclesPass
 294 ===========================
 295
 296 Read in the entire changeset graph and break up symbol changesets as
 297 necessary to break any cycles that are found.
 298
 299
 300 TopologicalSortPass
 301 ===================
 302
 303 Update the conversion statistics with excluded symbols omitted.
 304
 305
 306 CreateRevsPass
 307 ==============
 308
 309 Create SVNCommits and assign svn revision numbers to each one.  Create
 310 a database (SVN_COMMITS_*) to map svn revision numbers to SVNCommits
 311 and another (CVS_REVS_TO_SVN_REVNUMS) to map each CVSRevision id to
 312 the number of the svn revision containing it.
 313
 314 Also, SymbolingsLogger writes a line to SYMBOL_OPENINGS_CLOSINGS for
 315 each opening or closing for each CVSSymbol, noting in what SVN
 316 revision the opening or closing occurred.
 317
 318
 319 SortSymbolOpeningsClosingsPass
 320 ==============================
 321
 322 This pass sorts SYMBOL_OPENINGS_CLOSINGS into
 323 SYMBOL_OPENINGS_CLOSINGS_SORTED.  This orders the file first by symbol
 324 ID, and second by Subversion revision number, thus grouping all
 325 openings and closings for each symbolic name together.
 326
 327
 328 IndexSymbolsPass
 329 ================
 330
 331 Iterate through all the lines in SYMBOL_OPENINGS_CLOSINGS_SORTED,
 332 writing out a pickled map to SYMBOL_OFFSETS_DB telling at what offset
 333 in SYMBOL_OPENINGS_CLOSINGS_SORTED the lines corresponding to each
 334 Symbol begin.  This will allow us to seek to the various offsets in
 335 the file and sequentially read only the openings and closings that we
 336 need.
 337
 338
 339 OutputPass
 340 ==========
 341
 342 The filling of a symbol is triggered when SVNSymbolCommit.commit()
 343 calls SVNRepositoryMirror.fill_symbol().  The SVNSymbolCommit contains
 344 the list of CVSSymbols that have to be copied to a symbol directory in
 345 this revision.  However, we still have to do a lot of work to figure
 346 out what SVN revision number to use as the source of these copies, and
 347 also to group file copies together into directory copies when
 348 possible.
 349
 350 The SYMBOL_OPENINGS_CLOSINGS_SORTED file lists the opening and closing
 351 SVN revision of each revision that has to be copied to the symbol
 352 directory.  We use this information to try to find SVN revision
 353 numbers that can serve as the source for as many files as possible, to
 354 avoid having to pick and choose sources from many SVN revisions.
 355
 356 Furthermore, when a bunch of files in a directory have to be copied at
 357 the same time, it is cheaper to copy the directory as a whole.  But if
 358 not *all* of the files within the directory had to be copied, then the
 359 unneeded files have to be deleted again from the copied directory.  Or
 360 if some of the files have to be copied from different source SVN
 361 revision numbers, then those files have to be overwritten in the
 362 copied directory with the correct versions.
 363
 364 Finally, it can happen that a single Symbol has to be filled multiple
 365 times (because the initial SymbolChangeset had to be broken up).  In
 366 this case, the first fill can copy the source directory to the
 367 destination directory (maybe with fixups), but subsequent copies have
 368 to copy individual files to avoid overwriting content that is already
 369 present in the destination directory.
 370
 371 To figure all of this out, we need to know all of the files that
 372 existed in every previous SVN revision, in every line of development.
 373 This is done using the SVNRepositoryMirror class, which keeps a
 374 skeleton record of the entire SVN history in a database using data
 375 structures similar to those used by SVN itself.
 376
 377