sparse-revlog: stop using a heap to track selected gap
Same logic as for 'gapsheap', we don't actually need a heap.
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.