Minor corrections

notes.txt

@@ -1,158 +1,158 b''
 Some notes about Mercurial's design
 
 Revlogs:
 
 The fundamental storage type in Mercurial is a "revlog". A revlog is
 the set of all revisions to a file. Each revision is either stored
 compressed in its entirety or as a compressed binary delta against the
 previous version. The decision of when to store a full version is made
 based on how much data would be needed to reconstruct the file. This
 lets us ensure that we never need to read huge amounts of data to
 reconstruct a file, regardless of how many revisions of it we store.
 
 In fact, we should always be able to do it with a single read,
 provided we know when and where to read. This is where the index comes
 in. Each revlog has an index containing a special hash (nodeid) of the
 text, hashes for its parents, and where and how much of the revlog
 data we need to read to reconstruct it. Thus, with one read of the
 index and one read of the data, we can reconstruct any version in time
 proportional to the file size.
 
 Similarly, revlogs and their indices are append-only. This means that
 adding a new version is also O(1) seeks.
 
 Generally revlogs are used to represent revisions of files, but they
 also are used to represent manifests and changesets.
 
 Manifests:
 
 A manifest is simply a list of all files in a given revision of a
 project along with the nodeids of the corresponding file revisions. So
 grabbing a given version of the project means simply looking up its
 manifest and reconstruction all the file revisions pointed to by it.
 
 Changesets:
 
 A changeset is a list of all files changed in a check-in along with a
 change description and some metadata like user and date. It also
 contains a nodeid to the relevent revision of the manifest. Changesets
 and manifests are one-to-one, but contain different data for
 convenience.
 
 Nodeids:
 
 Nodeids are unique ids that are used to represent the contents of a
 file AND its position in the project history. That is, if you change a
 file and then change it back, the result will have a different nodeid
 because it has different history. This is accomplished by including
 the parents of a given revision's nodeids with the revision's text
 when calculating the hash.
 
 Graph merging:
 
 Nodeids are implemented as they are to simplify merging. Merging a
 pair of directed acyclic graphs (aka "the family tree" of the file
 history) requires some method of determining if nodes in different
 graphs correspond. Simply comparing the contents of the node (by
 comparing text of given revisions or their hashes) can get confused by
 identical revisions in the tree.
 
 The nodeid approach makes it trivial - the hash uniquely describes a
 revision's contents and its graph position relative to the root, so
 merge is simply checking whether each nodeid in graph A is in the hash
 table of graph B. If not, we pull them in, adding them sequentially to
 the revlog.
 
 Graph resolving:
 
 Mercurial does branching by copying (or COWing) a repository and thus
 keeps everything nice and linear within a repository. However, when a
 merge of repositories (a "pull") is done, we may often have two head
 revisions in a given graph. To keep things simple, Mercurial forces
 the head revisions to be merged.
 
 It first finds the closest common ancestor of the two heads. If one is
 a child of the other, it becomes the new head. Otherwise, we call out
 to a user-specified 3-way merge tool.
 
 Merging files, manifests, and changesets:
 
 We begin by comparing changeset DAGs, pulling all nodes we don't have
 in our DAG from the other repository. As we do so, we collect a list
 of changed files to merge.
 
 Then for each file, we perform a graph merge and resolve as above.
 It's important to merge files using per-file DAGs rather than just
 changeset level DAGs as this diagram illustrates: 
 
 M   M1   M2
 
 AB
  |`-------v     M2 clones M
 aB       AB     file A is change in mainline
  |`---v  AB'    file B is changed in M2
  |   aB / |     M1 clones M
  |   ab/  |     M1 changes B
  |   ab'  |     M1 merges from M2, changes to B conflict
  |    |  A'B'   M2 changes A
   `---+--.|
       |  a'B'   M2 merges from mainline, changes to A conflict
       `--.|
          ???    depending on which ancestor we choose, we will have
 	        to redo A hand-merge, B hand-merge, or both
                 but if we look at the files independently, everything
 		is fine
 
 After we've merged files, we merge the manifest log DAG and resolve
 additions and deletions. Then we are ready to resolve the changeset
 DAG - if our merge required any changes (the new head is not a
 decendent of our tip), we must create a new changeset describing all
 of the changes needed to merge it into the tip.
 
 Merge performance:
 
 The I/O operations for performing a merge are O(changed files), not
 O(total changes) and in many cases, we needn't even unpack the deltas
 to add them to our repository (though this optimization isn't
 necessary).
 
 Rollback:
 
 When performing a commit or a merge, we order things so that the
 changeset entry gets added last. We keep a transaction log of the name
 of each file touched and its length prior to the transaction. On
 abort, we simply truncate each file to its prior length. This is one
 of the nice properties of the append-only structure of the revlogs.
 
 Remote access:
 
 Mercurial currently supports pulling from "serverless" repositories.
 Simply making the repo directory accessibly via the web and pointing
 hg at it can accomplish a pull. This is relatively bandwidth efficient
 but no effort has been spent on pipelining, so it won't work
 especially well over LAN yet.
 
 It's also quite amenable to rsync, if you don't mind keeping an intact
 copy of the master around locally.
 
 Also note the append-only and ordering properties of the commit
 guarantee that readers will always see a repository in a consistent
 state and no special locking is necessary. As there is generally only
 one writer to an hg repository, there is in fact no exclusion
 implemented yet. 
 
 
 Some comparisons to git:
 
 Most notably, Mercurial uses delta compression and repositories
 created with it will grow much more slowly over time. This also allows
 it to be much more bandwidth efficient. I expect repos sizes and sync
 speeds to be similar to or better than BK, given the use of binary diffs.
 
-Mercurial is roughly the same performance as git and is faster in
-others as it keeps around more metadata. One example is listing and
-retrieving past versions of a file, which it can do without reading
-all the changesets. This metadata will also allow it to perform better
-merges as described above.
+Mercurial is roughly the same performance as git in some areas and is
+faster in others as it keeps around more metadata. One example is
+listing and retrieving past versions of a file, which it can do
+without reading all the changesets. This metadata will also allow it
+to perform better merges as described above.