Scintilla / Bugs / #2197 Off-by-one Error in EditView::LayoutLine()

Neil Hodgson - 2020-08-16

What is the actual problem here? Is the cached line incorrectly treated as valid or invalid under some circumstances?

If you would like to refer to this comment somewhere else in this project, copy and paste the following link:

Zufu Liu - 2020-08-16

It's incorrectly treated as invalid.

Assume caret line is very long, caret blinking and word wrapping is enabled, this cause the application unresponsive for very long (infinite?) time, without enough idle time to wrap other lines, because cache for caret line been treated as "invalid", then measure widths again and again, the while (bfLayout.More()) loop.

Last edit: Zufu Liu 2020-08-16

If you would like to refer to this comment somewhere else in this project, copy and paste the following link:

Zufu Liu - 2020-08-16

A reproducer:
Open your Visual Studio installer, click modify button, click Installation Location tab, open the download cache folder, for me this is D:\Program Files\Microsoft Visual Studio\Packages, there is a _Instances sub folder, with contains folders named with random hashes.
open one of them, there is a large (based on how many components you installed) catalog.json file.

Run following Python script to produce pretty.json and catalog2.json, then open the three JSON files with SciTE, catalog2.json is always unresponsive, while pretty.json can be opened quickly, and catalog2.json can be opened with some time.

import json path = r'D:\Program Files\Microsoft Visual Studio\Packages\_Instances\2980b637\catalog.json' catalog = open(path, encoding='utf-8').read() pretty = json.dumps(json.loads(catalog), ensure_ascii=False, indent='\t') with open('pretty.json', 'w', encoding='utf-8') as fd: fd.write(pretty) with open('catalog2.json', 'w', encoding='utf-8') as fd: fd.write(catalog) fd.write('\n') fd.write(pretty)
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:

Zufu Liu - 2020-08-17

A simple reproducer.
Add following line in EditView::LayoutLine()

allSame = allSame && (ll->styles[numCharsInLine] == styleByte); // For eolFilled printf("line=%zd, allSame=%d, styleByte=%d / %d\n", line + 1, allSame, styleByte, ll->styles[numCharsInLine]);

(on Windows) add lines in WinMain:

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE, LPSTR, int) { #if 1 if (AttachConsole(ATTACH_PARENT_PROCESS)) { freopen("CONOUT$", "w", stdout); freopen("CONOUT$", "w", stderr); fprintf(stdout, "\n%s:%d %s\n", __FILE__, __LINE__, __FUNCTION__); } #endif

build Scintilla and SciTE, open SciTEUser.properties, add cache.layout=2 (SC_CACHE_PAGE).
then open ILexer.h, delete last 'H' on line 9 #define ILEXER_H, watch console output; then scroll down, watch console output. you will see a lots of logs like line=58, allSame=0, styleByte=10 / 0.

using variables defined in if (ll->validity == LineLayout::ValidLevel::invalid) block:

const int lineLength = static_cast<int>(posLineEnd - posLineStart); const int numCharsBeforeEOL = static_cast<int>(model.pdoc->LineEnd(line) - posLineStart); const int numCharsInLine = (vstyle.viewEOL) ? lineLength : numCharsBeforeEOL; const unsigned char styleByteLast = (lineLength > 0) ? ll->styles[lineLength - 1] : 0; ll->styles[numCharsInLine] = styleByteLast; // For eolFilled

this check

allSame = allSame && (ll->styles[numCharsInLine] == styleByte);

is equivalent to following when viewEOL is false.

allSame = allSame && (ll->styles[numCharsBeforeEOL] == ll->styles[numCharsBeforeEOL - 1]); // ll->styles[numCharsBeforeEOL] = styleByteLast = style for last EOL character // ll->styles[numCharsBeforeEOL - 1] = style for last character before first EOL character // so the check most of the time failed

My suggested change (set styleByte to style for first EOL character):

+ if (!vstyle.viewEOL) { + styleByte = model.pdoc->StyleIndexAt(numCharsInLine + posLineStart); + }

Does not fix buggy lexers that color CRLF with different styles, several such lexers had been fixed in the past.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
- Zufu Liu - 2020-08-17
  
  Two patches fixed this bug.
  first change:
  
  - allSame = allSame && (ll->styles[numCharsInLine] == styleByte); // For eolFilled + if (!vstyle.viewEOL) { + // For eolFilled + allSame = allSame && (ll->styles[lineLength] == model.pdoc->CharAt(lineLength + posLineStart)); + }
  
  the eolFilled only tested for viewEOL is false, when viewEOL is true, whole line is already tested.
  
  second change:
  
  - const unsigned char styleByteLast = (lineLength > 0) ? ll->styles[lineLength - 1] : 0; + const unsigned char styleByteLast = (lineLength > 0) ? (vstyle.viewEOL ? ll->styles[lineLength - 1] : ll->styles[numCharsBeforeEOL]) : 0;
  
  , set styleByteLast to style for last EOL character when viewEOL is true and first EOL character when viewEOL is false.
  
  fix-opt.diff optimized the loop with xor and bitwise or, and added a separate loop for someStylesForceCase.
  
  At 2020-08-17 08:51:47, "Zufu Liu" zufuliu@users.sourceforge.net wrote:
  
  A simple reproducer.
  Add following line in EditView::LayoutLine()
  
  allSame=allSame&&(ll->styles[numCharsInLine]==styleByte);// For eolFilledprintf("line=%zd, allSame=%d, styleByte=%d / %d\n",line+1,allSame,styleByte,ll->styles[numCharsInLine]);
  
  (on Windows) add lines in WinMain:
  
  intWINAPIWinMain(HINSTANCEhInstance,HINSTANCE,LPSTR,int){#if 1if(AttachConsole(ATTACH_PARENT_PROCESS)){freopen("CONOUT$","w",stdout);freopen("CONOUT$","w",stderr);fprintf(stdout,"\n%s:%d %s\n",FILE,LINE,FUNCTION);}#endif
  
  build Scintilla and SciTE, open SciTEUser.properties, add cache.layout=2 (SC_CACHE_PAGE).
  then open ILexer.h, delete last 'H' on line 9 #define ILEXER_H, watch console output; then scroll down, watch console output. you will see a lots of logs like line=58, allSame=0, styleByte=10 / 0.
  
  using variables defined in if (ll->validity == LineLayout::ValidLevel::invalid) block:
  
  constintlineLength=static_cast<int>(posLineEnd-posLineStart);constintnumCharsBeforeEOL=static_cast<int>(model.pdoc->LineEnd(line)-posLineStart);constintnumCharsInLine=(vstyle.viewEOL)?lineLength:numCharsBeforeEOL;constunsignedcharstyleByteLast=(lineLength>0)?ll->styles[lineLength-1]:0;ll->styles[numCharsInLine]=styleByteLast;// For eolFilled</int></int>
  
  this check
  
  allSame=allSame&&(ll->styles[numCharsInLine]==styleByte);
  
  is equivalent to following when viewEOL is false.
  
  allSame=allSame&&(ll->styles[numCharsBeforeEOL]==ll->styles[numCharsBeforeEOL-1]);// ll->styles[numCharsBeforeEOL] = styleByteLast = style for last EOL character// ll->styles[numCharsBeforeEOL - 1] = style for last character before first EOL character// so the check most of the time failed
  
  My suggested change (set styleByte to style for first EOL character):
  
  if (!vstyle.viewEOL) {+ styleByte = model.pdoc->StyleIndexAt(numCharsInLine + posLineStart);+ }
  
  Does not fix buggy lexers that color CRLF with different styles, several such lexers had been fixed in the past.
  
  [bugs:#2197] Off-by-one Error in EditView::LayoutLine()
  
  Status: open
  Group: Bug
  Created: Sun Aug 16, 2020 05:35 PM UTC by Zufu Liu
  Last Updated: Sun Aug 16, 2020 10:59 PM UTC
  Owner: Neil Hodgson
  
  following code set ll->styles[numCharsInLine] to style value for last EOL character.
  
  // if (ll->validity == LineLayout::ValidLevel::invalid)constintlineLength=static_cast<int>(posLineEnd-posLineStart);constintnumCharsBeforeEOL=static_cast<int>(model.pdoc->LineEnd(line)-posLineStart);constintnumCharsInLine=(vstyle.viewEOL)?lineLength:numCharsBeforeEOL;constunsignedcharstyleByteLast=(lineLength>0)?ll->styles[lineLength-1]:0;ll->styles[numCharsInLine]=styleByteLast;// For eolFilled</int></int>
  
  assuming posLineStart is zero, i.e. first line.
  in validating loop inside if (ll->validity == LineLayout::ValidLevel::checkTextAndStyle) block,
  the statement styleByte = model.pdoc->StyleIndexAt(charInDoc); gives different results:
  
  when viewEOL is true, it's styleByte = model.pdoc->StyleIndexAt(lineLength - 1);, i.e. styleByteLast.
  
  when viewEOL is false, it's styleByte = model.pdoc->StyleIndexAt(numCharsBeforeEOL - 1);, i.e. style for last character before EOL character, which has nothing related to styleByteLast, unless it's colored same with EOL characters, like if (sc.atLineStart) { sc.SetState(SCE_XXX_DEFAULT); }. so the following test mostly failed, which make the cache useless.
  
  allSame=allSame&&(ll->styles[numCharsInLine]==styleByte);// For eolFilled
  
  a possible fix:
  
  if (!vstyle.viewEOL) {+ styleByte = model.pdoc->StyleIndexAt(numCharsInLine + posLineStart);+ }
  allSame = allSame && (ll->styles[numCharsInLine] == styleByte); // For eolFilled
  
  Sent from sourceforge.net because you indicated interest in https://sourceforge.net/p/scintilla/bugs/2197/
  
  To unsubscribe from further messages, please visit https://sourceforge.net/auth/subscriptions/
  
  Related
  
  Bugs: ~~#2197~~
  
  alternate
  
  fix-opt.diff
  
  fix.diff
  
  If you would like to refer to this comment somewhere else in this project, copy and paste the following link:

Neil Hodgson - 2020-08-20

A minimal change would be to mirror the effects from the ValidLevel::invalid case back up into the ValidLevel::checkTextAndStyle case, checking that the styles[numCharsInLine] eolfilled byte is the same as the last style byte of the line:

--- a/src/EditView.cxx Sun Aug 16 21:44:56 2020 -0400 +++ b/src/EditView.cxx Thu Aug 20 22:46:22 2020 +1000 @@ -410,7 +410,8 @@ chPrevious = chDoc; numCharsInLine++; } - allSame = allSame && (ll->styles[numCharsInLine] == styleByte); // For eolFilled + const int styleByteLast = (posLineEnd > posLineStart) ? model.pdoc->StyleIndexAt(posLineEnd - 1) : 0; + allSame = allSame && (ll->styles[numCharsInLine] == styleByteLast); // For eolFilled if (allSame) { ll->validity = LineLayout::ValidLevel::positions; } else {

(the non-empty check appears to never fail)

set styleByteLast to style for last EOL character when viewEOL is true and first EOL character when viewEOL is false.

This seems less stable to me with eolfilled lines potentially appearing different when view EOL is on/off. It could also be different to previous behaviour.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:

Zufu Liu - 2020-08-21

The change works.
After the change, styleByte can be moved into the loop, though the loop itself can be optimized with RangePointer + memcmp.

If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
- Neil Hodgson - 2020-08-21
  
  Committed with [aa1c85], [c10c2f].
  
  I am hesitant to potentially move the gap for read operations.
  
  Related
  
  Commit: [aa1c85]
  Commit: [c10c2f]
  
  If you would like to refer to this comment somewhere else in this project, copy and paste the following link:

Neil Hodgson - 2020-08-21

labels: --> scintilla, layout, cache

status: open --> open-fixed
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:

There need another change to fix repeated wrap when allSame is true.

The time by moving gap is smaller than changing RangePointer to returns two pointers like:

const T *RangePointer(ptrdiff_t position, ptrdiff_t &rangeLength, const T **range2 = nullptr) noexcept {
    const T *data = body.data() + position;
    if (position < part1Length) {
        if ((position + rangeLength) > part1Length) {
            // Range overlaps gap, so move gap to start of range.
            if (range2) {
                rangeLength = part1Length - position;
                *range2 = data + rangeLength + gapLength;
            } else {
                GapTo(position);
                data += gapLength;
            }
        }
    } else {
        data += gapLength;
    }
    return data;
}

LayoutLine-wrap.diff

What's wrong with LayoutLine-wrap.diff:

diff -r c10c2fd7dd1f src/EditView.cxx
--- a/src/EditView.cxx  Fri Aug 21 13:10:45 2020 +1000
+++ b/src/EditView.cxx  Sat Aug 22 09:42:04 2020 +0800
@@ -387,6 +387,9 @@
    if (posLineEnd >(posLineStart + ll->maxLineLength)) {
        posLineEnd = posLineStart + ll->maxLineLength;
    }

+   // Hard to cope when too narrow, so just assume there is space
+   width = std::max(width, 20);
+
    if (ll->validity == LineLayout::ValidLevel::checkTextAndStyle) {
        Sci::Position lineLength = posLineEnd - posLineStart;
        if (!vstyle.viewEOL) {
@@ -410,7 +413,7 @@
            const int styleByteLast = (posLineEnd > posLineStart) ? model.pdoc->StyleIndexAt(posLineEnd - 1) : 0;
            allSame = allSame && (ll->styles[lineLength] == styleByteLast); // For eolFilled
            if (allSame) {
-               ll->validity = LineLayout::ValidLevel::positions;
+               ll->validity = (ll->widthLine != width) ? LineLayout::ValidLevel::positions : LineLayout::ValidLevel::lines;
            } else {
                ll->validity = LineLayout::ValidLevel::invalid;
            }
@@ -504,10 +507,6 @@
        ll->numCharsBeforeEOL = numCharsBeforeEOL;
        ll->validity = LineLayout::ValidLevel::positions;
    }
-   // Hard to cope when too narrow, so just assume there is space
-   if (width < 20) {
-       width = 20;
-   }
    if ((ll->validity == LineLayout::ValidLevel::positions) || (ll->widthLine != width)) {
        ll->widthLine = width;
        if (width == LineLayout::wrapWidthInfinite) {

Neil Hodgson - 2020-08-27

Committed as [41fb5d].

Related

Commit: [41fb5d]

If you would like to refer to this comment somewhere else in this project, copy and paste the following link:

Neil Hodgson - 2020-09-11

status: open-fixed --> closed-fixed
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:

Off-by-one Error in EditView::LayoutLine()

Group

Searches

Help

#2197 Off-by-one Error in EditView::LayoutLine()

Related

Discussion

Related

Related

Related