linelog is a storage format inspired by the "Interleaved deltas" idea. See

https://en.wikipedia.org/wiki/Interleaved_deltas for its introduction.

0. SCCS Weave

  To understand what linelog is, first we have a quick look at a simplified

  (with header removed) SCCS weave format, which is an implementation of the

  "Interleaved deltas" idea.

0.1 Basic SCCS Weave File Format

  A SCCS weave file consists of plain text lines. Each line is either a

  special instruction starting with "^A" or part of the content of the real

  file the weave tracks. There are 3 important operations, where REV denotes

  the revision number:

    ^AI REV, marking the beginning of an insertion block introduced by REV

    ^AD REV, marking the beginning of a deletion block introduced by REV

    ^AE REV, marking the end of the block started by "^AI REV" or "^AD REV"

  Note on revision numbers: For any two different revision numbers, one must

  be an ancestor of the other to make them comparable. This enforces linear

  history. Besides, the comparison functions (">=", "<") should be efficient.

  This means, if revisions are strings like git or hg, an external map is

  required to convert them into integers.

  For example, to represent the following changes:

    REV 1 | REV 2 | REV 3

    ------+-------+-------

    a     | a     | a

    b     | b     | 2

    c     | 1     | c

          | 2     |

          | c     |

  A possible weave file looks like:

    ^AI 1

    a

    ^AD 3

    b

    ^AI 2

    1

    ^AE 3

    2

    ^AE 2

    c

    ^AE 1

  An "^AE" does not always match its nearest operation ("^AI" or "^AD"). In

  the above example, "^AE 3" does not match the nearest "^AI 2" but "^AD 3".

  Therefore we need some extra information for "^AE". The SCCS weave uses a

  revision number. It could also be a boolean value about whether it is an

  insertion or a deletion (see section 0.4).

0.2 Checkout

  The "checkout" operation is to retrieve file content at a given revision,

  say X. It's doable by going through the file line by line and:

    - If meet ^AI rev, and rev > X, find the corresponding ^AE and jump there

    - If meet ^AD rev, and rev <= X, find the corresponding ^AE and jump there

    - Ignore ^AE

    - For normal lines, just output them

0.3 Annotate

  The "annotate" operation is to show extra metadata like the revision number

  and the original line number a line comes from.

  It's basically just a "Checkout". For the extra metadata, they can be stored

  side by side with the line contents. Alternatively, we can infer the

  revision number from "^AI"s.

  Some SCM tools have to calculate diffs on the fly and thus are much slower

  on this operation.

0.4 Tree Structure

  The word "interleaved" is used because "^AI" .. "^AE" and "^AD" .. "^AE"

  blocks can be interleaved.

  If we consider insertions and deletions separately, they can form tree

  structures, respectively.

    +--- ^AI 1        +--- ^AD 3

    | +- ^AI 2        | +- ^AD 2

    | |               | |

    | +- ^AE 2        | +- ^AE 2

    |                 |

    +--- ^AE 1        +--- ^AE 3

  More specifically, it's possible to build a tree for all insertions, where

  the tree node has the structure "(rev, startline, endline)". "startline" is

  the line number of "^AI" and "endline" is the line number of the matched

  "^AE".  The tree will have these properties:

    1. child.rev > parent.rev

    2. child.startline > parent.startline

    3. child.endline < parent.endline

  A similar tree for all deletions can also be built with the first property

  changed to:

    1. child.rev < parent.rev

0.5 Malformed Cases

  The following cases are considered malformed in our implementation:

    1. Interleaved insertions, or interleaved deletions.

       It can be rewritten to a non-interleaved tree structure.

       Take insertions as example, deletions are similar:

       ^AI x         ^AI x

       a             a

       ^AI x + 1  -> ^AI x + 1

       b             b

       ^AE x         ^AE x + 1

       c             ^AE x

       ^AE x + 1     ^AI x + 1

                     c

                     ^AE x + 1

    2. Nested insertions, where the inner one has a smaller revision number.

       Or nested deletions, where the inner one has a larger revision number.

       It can be rewritten to a non-nested form.

       Take insertions as example, deletions are similar:

       ^AI x + 1     ^AI x + 1

       a             a

       ^AI x      -> ^AE x + 1

       b             ^AI x

       ^AE x         b

       c             ^AE x

       ^AE x + 1     ^AI x + 1

                     c

                     ^AE x + 1

    3. Insertion inside deletion with a smaller revision number.

       Rewrite by duplicating the content inserted:

       ^AD x          ^AD x

       a              a

       ^AI x + 1  ->  b

       b              c

       ^AE x + 1      ^AE x

       c              ^AI x + 1

       ^AE x          b

                      ^AE x + 1

       Note: If "annotate" purely depends on "^AI" information, then the

       duplication content will lose track of where "b" is originally from.

  Some of them may be valid in other implementations for special purposes. For

  example, to "revive" a previously deleted block in a newer revision.

0.6 Cases Can Be Optimized

  It's always better to get things nested. For example, the left is more

  efficient than the right while they represent the same content:

    +--- ^AD 2          +- ^AD 1

    | +- ^AD 1          |   LINE A

    | |   LINE A        +- ^AE 1

    | +- ^AE 1          +- ^AD 2

    |     LINE B        |   LINE B

    +--- ^AE 2          +- ^AE 2

  Our implementation sometimes generates the less efficient data. To always

  get the optimal form, it requires extra code complexity that seems unworthy.

0.7 Inefficiency

  The file format can be slow because:

  - Inserting a new line at position P requires rewriting all data after P.

  - Finding "^AE" requires walking through the content (O(N), where N is the

    number of lines between "^AI/D" and "^AE").

1. Linelog

  The linelog is a binary format that dedicates to speed up mercurial (or

  git)'s "annotate" operation. It's designed to avoid issues mentioned in

  section 0.7.

1.1 Content Stored

  Linelog is not another storage for file contents. It only stores line

  numbers and corresponding revision numbers, instead of actual line content.

  This is okay for the "annotate" operation because usually the external

  source is fast to checkout the content of a file at a specific revision.

  A typical SCCS weave is also fast on the "grep" operation, which needs

  random accesses to line contents from different revisions of a file. This

  can be slow with linelog's no-line-content design. However we could use

  an extra map ((rev, line num) -> line content) to speed it up.

  Note the revision numbers in linelog should be independent from mercurial

  integer revision numbers. There should be some mapping between linelog rev

  and hg hash stored side by side, to make the files reusable after being

  copied to another machine.

1.2 Basic Format

  A linelog file consists of "instruction"s. An "instruction" can be either:

    - JGE  REV ADDR     # jump to ADDR if rev >= REV

    - JL   REV ADDR     # jump to ADDR if rev < REV

    - LINE REV LINENUM  # append the (LINENUM+1)-th line in revision REV

  For example, here is the example linelog representing the same file with

  3 revisions mentioned in section 0.1:

    SCCS  |    Linelog

    Weave | Addr : Instruction

    ------+------+-------------

    ^AI 1 |    0 : JL   1 8

    a     |    1 : LINE 1 0

    ^AD 3 |    2 : JGE  3 6

    b     |    3 : LINE 1 1

    ^AI 2 |    4 : JL   2 7

    1     |    5 : LINE 2 2

    ^AE 3 |

    2     |    6 : LINE 2 3

    ^AE 2 |

    c     |    7 : LINE 1 2

    ^AE 1 |

          |    8 : END

  This way, "find ^AE" is O(1) because we just jump there. And we can insert

  new lines without rewriting most part of the file by appending new lines and

  changing a single instruction to jump to them.

  The current implementation uses 64 bits for an instruction: The opcode (JGE,

  JL or LINE) takes 2 bits, REV takes 30 bits and ADDR or LINENUM takes 32

  bits. It also stores the max revision number and buffer size at the first

  64 bits for quick access to these values.

1.3 Comparing with Mercurial's revlog format

  Apparently, linelog is very different from revlog: linelog stores rev and

  line numbers, while revlog has line contents and other metadata (like

  parents, flags). However, the revlog format could also be used to store rev

  and line numbers. For example, to speed up the annotate operation, we could

  also pre-calculate annotate results and just store them using the revlog

  format.

  Therefore, linelog is actually somehow similar to revlog, with the important

  trade-off that it only supports linear history (mentioned in section 0.1).

  Essentially, the differences are:

    a) Linelog is full of deltas, while revlog could contain full file

       contents sometimes. So linelog is smaller. Revlog could trade

       reconstruction speed for file size - best case, revlog is as small as

       linelog.

    b) The interleaved delta structure allows skipping large portion of

       uninteresting deltas so linelog's content reconstruction is faster than

       the delta-only version of revlog (however it's possible to construct

       a case where interleaved deltas degrade to plain deltas, so linelog

       worst case would be delta-only revlog). Revlog could trade file size

       for reconstruction speed.

    c) Linelog implicitly maintains the order of all lines it stores. So it

       could dump all the lines from all revisions, with a reasonable order.

       While revlog could also dump all line additions, it requires extra

       computation to figure out the order putting those lines - that's some

       kind of "merge".

  "c" makes "hg absorb" easier to implement and makes it possible to do

  "annotate --deleted".

1.4 Malformed Cases Handling

  The following "case 1", "case 2", and "case 3" refer to cases mentioned

  in section 0.5.

  Using the exposed API (replacelines), case 1 is impossible to generate,

  although it's possible to generate it by constructing rawdata and load that

  via linelog.fromdata.

  Doing annotate(maxrev) before replacelines (aka. a1, a2 passed to

  replacelines are related to the latest revision) eliminates the possibility

  of case 3. That makes sense since usually you'd like to make edits on top of

  the latest revision. Practically, both absorb and fastannotate do this.

  Doing annotate(maxrev), plus replacelines(rev, ...) where rev >= maxrev

  eliminates the possibility of case 2. That makes sense since usually the

  edits belong to "new revisions", not "old revisions". Practically,

  fastannotate does this. Absorb calls replacelines with rev < maxrev to edit

  past revisions. So it needs some extra care to not generate case 2.

  If case 1 occurs, that probably means linelog file corruption (assuming

  linelog is edited via public APIs) the checkout or annotate result could

  be less meaningful or even error out, but linelog wouldn't enter an infinite

  loop.

  If either case 2 or 3 occurs, linelog works as if the inner "^AI/D" and "^AE"

  operations on the left side are silently ignored.