From 685507922b0b75da5935076395a5b1ec1ef58356 Mon Sep 17 00:00:00 2001 From: Robin Haberkorn Date: Sat, 25 Jul 2026 01:55:28 +0200 Subject: revised and improved the Unicode glyph-to-byte conversion heuristics Previously almost all glyph-to-byte offset conversions consulted Scintilla's line index and counted characters on the resulting line. For instance a simple expression like `.+1J` would scan the same line twice completely, which would be very slow on pathologically long lines. Even insertions did that due to having to update the ^Y ranges. If you repeat such an operation over all characters as in `<.+1:J;>` you would have complexity O(n^2) for n = line length. Only commands with an explicit relative nature like `C` and `A` would use teco_view_glyph2bytes_relative() which scans beginning at dot as long as the relative movement is less than 1024 glyphs. Wit the new heuristics almost all glyph-to-byte and byte-to-glyph conversions can make use of that optimization. This requires that dot must at all times be known in glyphs as well - the byte position is managed by Scintilla (SCI_GETCURRENTPOS). We therefore introduced teco_current_doc_set_dot() and teco_current_doc_get_dot() to update dot in the current buffer or Q-Register -- it cannot be stored along with the view since Q-Registers share a single view. A number of auxiliary functions have been introduced for converting relative to a known (glyphs,bytes) offset pair and for converting absolute and relative positions with regard to the current doc and SCI_GETCURRENTPOS position. Of course this is error-prone since the glyph and dot positions are interdependant - they must always be kept in sync. With these new optimizations even pathologically long lines can (usually) be managed even in UTF-8 documents. It does not address slow-downs in Scintilla's line layout, yet. grosciteco.tes for instance runs twice as fast now. --- src/view.c | 113 +++++++++++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 83 insertions(+), 30 deletions(-) (limited to 'src/view.c') diff --git a/src/view.c b/src/view.c index 8094186..7a9e0cc 100644 --- a/src/view.c +++ b/src/view.c @@ -644,27 +644,19 @@ teco_view_save_to_stdout(teco_view_t *ctx, GError **error) /** * Convert a glyph index to a byte offset as used by Scintilla. * - * This is optimized with the "line character index", + * This function is only for UTF-8 documents. + * It is optimized with the "line character index", * which must always be enabled in UTF-8 documents. * - * It is also used to validate glyph indexes. - * * @param ctx The view to operate on. * @param pos Position in glyphs/characters. * @return Position in bytes or -1 if pos is out of bounds. */ -gssize -teco_view_glyphs2bytes(teco_view_t *ctx, teco_int_t pos) +static gssize +teco_view_glyphs2bytes_unicode(teco_view_t *ctx, teco_int_t pos) { if (pos < 0) - return -1; /* invalid position */ - if (!pos) - return 0; - - if (!(teco_view_ssm(ctx, SCI_GETLINECHARACTERINDEX, 0, 0) & - SC_LINECHARACTERINDEX_UTF32)) - /* assume single-byte encoding */ - return pos <= teco_view_ssm(ctx, SCI_GETLENGTH, 0, 0) ? pos : -1; + return -1; sptr_t line = teco_view_ssm(ctx, SCI_LINEFROMINDEXPOSITION, pos, SC_LINECHARACTERINDEX_UTF32); @@ -675,19 +667,16 @@ teco_view_glyphs2bytes(teco_view_t *ctx, teco_int_t pos) } /** - * Convert byte offset to glyph/character index without bounds checking. + * Convert a bytes index to a glyph offset. + * + * This function is only for UTF-8 documents. + * It is optimized with the "line character index", + * which must always be enabled in UTF-8 documents. + * This function does \b not check for invalid positions. */ -teco_int_t -teco_view_bytes2glyphs(teco_view_t *ctx, gsize pos) +static teco_int_t +teco_view_bytes2glyphs_unicode(teco_view_t *ctx, gsize pos) { - if (!pos) - return 0; - - if (!(teco_view_ssm(ctx, SCI_GETLINECHARACTERINDEX, 0, 0) & - SC_LINECHARACTERINDEX_UTF32)) - /* assume single-byte encoding */ - return pos; - sptr_t line = teco_view_ssm(ctx, SCI_LINEFROMPOSITION, pos, 0); sptr_t line_bytes = teco_view_ssm(ctx, SCI_POSITIONFROMLINE, line, 0); return teco_view_ssm(ctx, SCI_INDEXPOSITIONFROMLINE, line, @@ -698,7 +687,7 @@ teco_view_bytes2glyphs(teco_view_t *ctx, gsize pos) #define TECO_RELATIVE_LIMIT 1024 /** - * Convert a glyph index relative to a byte position to + * Convert a glyph index relative to a position to * a byte position. * * Can be used to implement commands with relative character @@ -709,23 +698,87 @@ teco_view_bytes2glyphs(teco_view_t *ctx, gsize pos) * (as on exceedingly long lines). * * @param ctx The view to operate on. + * @param pos_glyphs Glyph position to start. + * It must be the same position as specified by pos. * @param pos Byte position to start. * @param n Number of glyphs/characters to the left (negative) or - * right (positive) of pos. + * right (positive) of pos_glyphs and pos. * @return Position in bytes or -1 if the resulting position is out of bounds. */ gssize -teco_view_glyphs2bytes_relative(teco_view_t *ctx, gsize pos, teco_int_t n) +teco_view_glyphs2bytes_rel(teco_view_t *ctx, teco_int_t pos_glyphs, gsize pos, teco_int_t n) { - if (!n) + if (n == 0) return pos; + if (pos_glyphs == -n) + return 0; + + if (!(teco_view_ssm(ctx, SCI_GETLINECHARACTERINDEX, 0, 0) & + SC_LINECHARACTERINDEX_UTF32)) { + /* assume single-byte encoding */ + g_assert(pos_glyphs == pos); + + sptr_t len = teco_view_ssm(ctx, SCI_GETLENGTH, 0, 0); + if (0 > (gssize)pos+n || (gssize)pos+n > len) + return -1; + + return pos+n; + } + /* NOTE: Does not work for n == G_MININT64. */ if (ABS(n) > TECO_RELATIVE_LIMIT) - return teco_view_glyphs2bytes(ctx, teco_view_bytes2glyphs(ctx, pos) + n); + return teco_view_glyphs2bytes_unicode(ctx, pos_glyphs+n); sptr_t res = teco_view_ssm(ctx, SCI_POSITIONRELATIVE, pos, n); /* SCI_POSITIONRELATIVE may return 0 even if the offset is valid */ - return res ? : n > 0 ? -1 : teco_view_bytes2glyphs(ctx, pos)+n >= 0 ? 0 : -1; + return res ? : n > 0 ? -1 : pos_glyphs + n >= 0 ? 0 : -1; +} + +/** + * Convert a byte index relative to a known position to + * a glyph position. + * + * Can be used to implement commands with relative character + * ranges. + * As an optimization, this always counts characters for deltas + * smaller than TECO_RELATIVE_LIMIT, so it will be fast + * even where the character-index based lookup is too slow + * (as on exceedingly long lines). + * + * @param ctx The view to operate on. + * @param pos_glyphs Glyph position to start. + * It must be the same position as specified by pos. + * @param pos Byte position to start. + * @param n Number of bytes to the left (negative) or + * right (positive) of pos_glyphs and pos. + * @return Position in glyphs or -1 if the resulting position is out of bounds. + */ +teco_int_t +teco_view_bytes2glyphs_rel(teco_view_t *ctx, teco_int_t pos_glyphs, gsize pos, gssize n) +{ + if (n == 0) + return pos_glyphs; + if (pos == -n) + return 0; + + sptr_t len = teco_view_ssm(ctx, SCI_GETLENGTH, 0, 0); + + if (0 > (gssize)pos+n || (gssize)pos+n > len) + return -1; + + if (!(teco_view_ssm(ctx, SCI_GETLINECHARACTERINDEX, 0, 0) & + SC_LINECHARACTERINDEX_UTF32)) { + /* assume single-byte encoding */ + g_assert(pos_glyphs == pos); + return pos_glyphs+n; + } + + /* NOTE: Does not work for n == G_MINSSIZE. */ + if (ABS(n) > TECO_RELATIVE_LIMIT) + return teco_view_bytes2glyphs_unicode(ctx, pos+n); + + return n < 0 ? pos_glyphs - teco_view_ssm(ctx, SCI_COUNTCHARACTERS, pos+n, pos) + : pos_glyphs + teco_view_ssm(ctx, SCI_COUNTCHARACTERS, pos, pos+n); } /** -- cgit v1.2.3