Re: [vim/vim] u_read_undo(): use a sorted table to swizzle sequence numbers (PR #20942)

h-east left a comment (vim/vim#20942)

### Summary

The rewrite is semantically faithful to the code it replaces. Since
`unserialize_uhp()` rejects `uh_seq <= 0`, neither a link value of `0` (what
`put_header_ptr()` writes for a NULL pointer) nor `-1` (a truncated read) can
match a real header, so both versions leave `ptr` NULL; a self-referencing link
is excluded by `j != i` in both; the duplicate check moved from an all-pairs
scan to an adjacency scan over the sorted table and rejects the same files with
the same message. `seq_table` is NULL-initialized and freed on both paths.

One blocking bug below, plus a design alternative and some test and
commit-message points.

### Blocking: an undo file with zero headers now fails with E341

`seq_table = ALLOC_MULT(uhpseq_T, num_head)` is unconditional, and
`num_head == 0` is a legal undo file. `u_write_undo()` only skips writing when
*both* conditions hold:

    if (buf->b_u_numhead == 0 && buf->b_u_line_ptr.ul_line == NULL)

The `&&` is there because "no undo headers, but a line saved for the `U`
command" is worth persisting. `u_save()` calls `u_saveline()` before
`u_savecommon()`, and `u_savecommon()` returns early when
`get_undolevel() < 0`, so with `'undolevels'` -1 every single-line change sets
`b_u_line_ptr` while `b_u_numhead` stays 0.

`ALLOC_MULT(uhpseq_T, 0)` reaches `lalloc(0, ...)`, which clears `emsg_silent`,
raises `E341: Internal error: lalloc(0, )` and returns NULL, turning a working
`:rundo` into an internal error plus a silent abort. Checked against master
that such a file is produced and loads today:

    $ printf 'hello\nworld\n' > Xul.txt
    $ vim --clean -c 'set ul=-1' -c 'normal x' -c 'wundo! Xul.undo' -c 'qa!' Xul.txt
    $ xxd Xul.undo | sed -n 5p
    00000040: 0000 0000 0000 0000 0000 0000 0000 0000
                        ^^^^^^^^^ num_head == 0

    $ vim --clean -c 'set ul=-1' -c 'normal x' -c 'rundo Xul.undo' \
          -c 'normal U' -c 'echo getline(1)' Xul.txt
    hello        " v:errmsg empty

Mirroring the guard the neighbouring `uhp_table` allocation already uses is
enough; `seq_table_len` then stays 0 and both loops do nothing.

Nothing in the suite catches this, so CI stays green. Every `:rundo` in
`test_undo.vim`, `test_textprop2.vim` and `test_crypt.vim` runs on a file with
at least one header (`samples/test_undo.txt.undo` has `num_head` 3, the inline
blob in `Test_corrupted_undofile()` has 1), and the two tests that set
`'undolevels'` to -1 never write or read an undo file. A regression test for
the zero-header file is worth adding along with the guard.

### Alternative: sort `uhp_table` itself and drop the parallel table

At the point of the sort every `uhp_table[i]` is non-NULL, since
`unserialize_uhp()` returning NULL goes straight to `error` and
`num_read_uhps != num_head` is rejected just above. So `uhp_table` can be
sorted in place on `uh_seq` and binary-searched directly, removing `uhpseq_T`,
the `idx` field, the second allocation with its OOM path, and the bug above.
The `i`/`j` indices keep their meaning: they are only used for `j != i`,
`SET_FLAG()` and `old_idx`/`new_idx`/`cur_idx`, all computed after the sort,
and the error path walks `0 .. num_read_uhps`, which equals `num_head`. It
would also make the comment already sitting above that allocation true:

    // uhp_table will store the freshly created undo headers we allocate
    // until we insert them into curbuf. The table remains sorted by the
    // sequence numbers of the headers.

`qsort()` still wants a `num_head > 0` guard, since passing NULL with a count
of 0 is not strictly defined.

### Tests

**Missing feature guard.** Neither `Test_undofile_branches()` nor
`Test_undofile_duplicate_seq()` has `CheckFeature persistent_undo`.
`test_undo.vim` gates per test rather than at the top, and both new tests use
`:wundo` and `:rundo`.

**The header scan is fragile.** `Test_undofile_duplicate_seq()` looks for the
0x5f 0xd0 magic and requires all five following 4-byte fields to be 8 or less.
That holds for this three-header linear history, but it silently depends on the
seq numbers staying small, and `headers[0]`/`headers[1]` are used without
checking they are the headers intended. A mis-detection would corrupt unrelated
bytes and could still produce E825 for the wrong reason. Asserting the values
before patching them makes that fail loudly:

    call assert_equal(0z00000001, blob[first : first + 3])
    call assert_equal(0z00000002, blob[second : second + 3])

The file header is fixed-layout up to the first undo header, so computing the
offset outright is also possible, at the cost of coupling the test to the
format.

**Minor.** `UndotreeSeqs()` is a global name in the test namespace. The two
tests are also inconsistent about cleanup: one uses `writefile(..., 'D')`, the
other trailing `delete()` calls that are skipped if an assertion throws.
`defer delete(...)` at creation covers both.

### Style

`SWIZZLE_SEQ(link)` reads `i` and `j` from the enclosing scope without saying
so. `SET_FLAG()` is a precedent for a function-local macro here, but it is a
one-liner with an explicit argument. A static helper taking `(uhpseq_T *tab,
int tab_len, u_header_T **uhp_table, int i, u_header_ptr_T *link)` avoids the
hidden coupling; passing `i` and `j` as macro arguments is the cheaper version.

Two of the new loops have a braceless `for` whose body is an `if` with a
compound statement; braces on the `for` read better. `uhpseq_find()` has a
function comment, `uhpseq_cmp()` has none.

### Commit messages and scope

The subject line states the solution; `AGENTS.md` asks for a problem statement,
something closer to "reading an undo file is slow when there are many undo
headers".

The cost model belongs in the commit message: `b_u_numhead` is trimmed down to
`'undolevels'` in `u_savecommon()`, so at the default of 1000 the old loops are
about 4 million pointer comparisons and are not measurable. The 1.74s -> 0.12s
number needs `'undolevels'` in the tens of thousands, which is what justifies
the extra allocation and the `qsort()` on every undo file read.

Splitting the change and the tests into two commits means two patch numbers,
and the test commit is a standalone "tests are missing" patch since it passes
unpatched. A single commit is the usual shape for a change of this size.

-- 
Reply to this email directly or view it on GitHub:
https://github.com/vim/vim/pull/20942#issuecomment-5203377551
You are receiving this because you are subscribed to this thread.

Message ID: <vim/vim/pull/20942/[email protected]>

-- 
-- 
You received this message from the "vim_dev" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php

--- 
You received this message because you are subscribed to the Google Groups "vim_dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
To view this discussion visit https://groups.google.com/d/msgid/vim_dev/vim/vim/pull/20942/c5203377551%40github.com.