anchor.diff:  % License for the specific language governing permissions and limitations under
   % the License.
   
  +%% @doc Data structure used to represent document edit histories.
  +
  +%% A key tree is used to represent the edit history of a document. Each node of
  +%% the tree represents a particular version. Relations between nodes represent
  +%% the order that these edits were applied. For instance, a set of three edits
  +%% would produce a tree of versions A->B->C indicating that edit C was based on
  +%% version B which was in turn based on A. In a world without replication (and
  +%% no ability to disable MVCC checks), all histories would be forced to be
  +%% linear lists of edits due to constraints imposed by MVCC (ie, new edits must
  +%% be based on the current version). However, we have replication, so we must
  +%% deal with not so easy cases, which lead to trees.
  +%%
  +%% Consider a document in state A. This doc is replicated to a second node. We
  +%% then edit the document on each node leaving it in two different states, B
  +%% and C. We now have two key trees, A->B and A->C. When we go to replicate a
  +%% second time, the key tree must combine these two trees which gives us
  +%% A->(B|C). This is how conflicts are introduced. In terms of the key tree, we
  +%% say that we have two leaves (B and C) that are not deleted. The presense of
  +%% the multiple leaves indicate conflict. To remove a conflict, one of the
  +%% edits (B or C) can be deleted, which results in, A->(B|C->D) where D is an
  +%% edit that is specially marked with the a deleted=true flag.
  +%%
  +%% What makes this a bit more complicated is that there is a limit to the
  +%% number of revisions kept, specified in couch_db.hrl (default is 1000). When
  +%% this limit is exceeded only the last 1000 are kept. This comes in to play
  +%% when branches are merged. The comparison has to begin at the same place in
  +%% the branches. A revision id is of the form N-XXXXXXX where N is the current
  +%% revision. So each path will have a start number, calculated in
  +%% couch_doc:to_path using the formula N - length(RevIds) + 1 So, .eg. if a doc
  +%% was edit 1003 times this start number would be 4, indicating that 3
  +%% revisions were truncated.
  +%%
  +%% This comes into play in @see merge_at/3 which recursively walks down one
  +%% tree or the other until they begin at the same revision.
  +
   -module(couch_key_tree).
   
   -export([merge/3, find_missing/2, get_key_leafs/2, get_full_key_paths/2, get/2]).
  
positive.code:     {MergedNextTree, Conflict2} = merge_simple(NextA, NextB),
      {[{Key, Value, MergedSubTree} | MergedNextTree], Conflict1 or Conflict2};
  merge_simple([{A, _, _} = Tree | Next], [{B, _, _} | _] = Insert) when A < B ->
      {Merged, _} = merge_simple(Next, Insert),
      {[Tree | Merged], true};
  merge_simple(Ours, [Tree | Next]) ->
      {Merged, _} = merge_simple(Ours, Next),
      {[Tree | Merged], true}.
  
  find_missing(_Tree, []) ->
      [];
  
negative.code:     {ok, Merged, Conflicts} ->
          {ok, [{Key, Value, Merged} | Sibs], Conflicts};
      no ->
          % first branch didn't merge, move to next branch
          case merge_at(Sibs, Place, InsertTree) of
          {ok, Merged, Conflicts} ->
              {ok, [{Key, Value, SubTree} | Merged], Conflicts};
  