[vim/vim] transstr(): keep a tail pointer instead of appending with STRCAT() (PR #20925)

3 views

Skip to first unread message

Samuel Schlesinger

unread,

1:55 AM (14 hours ago) 1:55 AM

to vim/vim, Subscribed

Problem: transstr() builds its result with STRCAT()/STRNCAT(), which scans the part already built for every appended character. This makes strtrans() quadratic in the length of the string. I think this is most impactful in get_foldtext in fold.c, where it could conceivably impact user experience.

Solution: Remember the end of the result and append there.

You can view, comment on, or merge this pull request online at:

https://github.com/vim/vim/pull/20925

Commit Summary

fcf0f9c transstr(): keep a tail pointer instead of appending with STRCAT()

File Changes

(1 file)

M src/charset.c (22)

Patch Links:

—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS and Android. Download it today!
You are receiving this because you are subscribed to this thread.

h_east

unread,

11:14 AM (5 hours ago) 11:14 AM

to vim/vim, Subscribed

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

The change itself is correct. STRCAT() rescans the result from the start
for every appended character, so the loop was O(n^2) in the length of the
result, and keeping a tail pointer makes it linear. Moving the terminating
NUL to after the loop is safe here because the loop has no early exit. The
tests need work though.

The new test is not portable, Windows CI is red

Three assertions fail on the Windows runners. strtrans("\x01\x1f\x7f")
returns the 0x7f unchanged, and both cases expecting <9f> come back with a
literal 0x9f.

The cause is 'isprint'. vim_isprintc() decides printability of anything
below 0x100 from g_chartab, which is built from 'isprint', and the default
differs per platform: "@,~-255" on Win32 and VMS, "@,161-255" elsewhere.
So 0x7f and 0x9f are printable on Windows and transstr() correctly leaves
them alone there.

Two ways out. Either set 'isprint' in the test so the expectations hold
everywhere:

  let save_isprint = &isprint
  set isprint=@,161-255
  ...
  let &isprint = save_isprint

Or drop the sub-0x100 cases and rely on the nr2char(0x200b) and
nr2char(0xfeff) assertions, which go through utf_printable() and are not
affected by 'isprint'. Those two already pass on every runner.

The first option is better if you want to keep covering the two-digit
transchar_hex() output, since <200b> and <feff> only exercise the
four-digit branch.

Test coverage does not include the non-multi-byte path

The second commit says it covers all strtrans() code paths, but every test
runs with the default 'encoding'. transstr() branches on has_mbyte for
the size computation, and the else branch using vim_strsize() is never
reached.

test_functions.vim already switches encoding in several tests, so a block
like this would close the gap, with 'isprint' pinned for the same reason as
above:

  let save_isprint = &isprint
  set encoding=latin1
  set isprint=@,161-255
  call assert_equal('a^Mb', strtrans("a\rb"))
  ...
  set encoding=utf-8
  let &isprint = save_isprint

Please verify the expected strings on your side, the point is the branch
rather than the exact output.

Prefer the pattern already used in this file

For the single-byte case the patch does STRCPY() followed by STRLEN(d),
which walks the translated character twice. trans_characters() a few lines
above solves the same problem by taking the length first:

	    trs = transchar_byte(*p++);
	    trs_len = (int)STRLEN(trs);
	    mch_memmove(d, trs, (size_t)trs_len);
	    d += trs_len;

That is one scan instead of two and matches the surrounding code. The strings
are short so this is not about speed, it is about staying consistent with the
file.

Please add a measurement

The commit message says this could impact get_foldtext() in fold.c. The
complexity argument is sound on its own, but a before/after timing on a long
line would make the case concrete and would tell us whether this is a real
user-visible win or a theoretical one. Something like strtrans() on a
100000 byte line with a mix of control characters is enough.

Out of scope, but worth noting

transchar_hex() already knows how many bytes it wrote in its local i, and
it returns void. If it returned that length, both this function and the size
computation loop above could drop their STRLEN() calls. That touches other
callers, so it does not belong in this PR.