Menu
▾
▴
#1129 Problems drawing very long lines
While testing Scintilla's ability to work with very large amount of text (very large SQL dumps are in question), besides the obvious speed issues, I noticed two problems with drawing very long lines.
1. If line consists only of characters (without any spaces, etc.) only first 64K of characters will be shown, the rest of characters won't appear on screen, but are added to the internal buffer. Don't enable UTF8 mode since it will mask this problem, by the second problem mentioned below.
2. When working in UTF8 mode, Scintilla is not able to move/scroll right past certain position. If you try to force scrolling, "garbage" will appear on screen. This problem doesn't appear when not in UTF8 mode.
In both situations SCI_SETSCROLLWIDTHTRACKING is enabled. Sample text file and example screenshots are attached.
There are some workarounds to platform limitations and bugs here that you could try to improve if this use-case is important enough to you.
I took a look at Win32 platform abstraction code, and found the limits in question:
maxWidthMeasure = IsNT() ? 1000000 : 30000;
maxLenText = IsNT() ? 65535 : 8192;
Why is maxWidthMeasure limited on NT? The second problem from my bug report could easily be fixed if it is changed to:
maxWidthMeasure = IsNT() ? INT_MAX : 30000;
According to MSDN GetTextExtentExPointW is not limited in string length. If you can think of a reason why maxWidthMeasure should be limited on NT, the code in MeasureWidths() method should be changed, so that in unicode part it loops over calling GetTextExtentExPointW multiple times until whole string is processed like it is done in the non unicode part of the same method, where GetTextExtentExPointA is called multiple times.
The first problem that's related to the limit set in maxLenText can also be fixed relatively easy. DrawTextCommon() method already has the ability to draw line in segments if first call to the ExtTextOut fails to draw all characters, but in non unicode mode, complete line is capped to the maxLenText before the first call to the ExtTextOutA. If you remove this (i.e. effectively make lenDraw = len), if the first call to the ExtTextOutA fails to draw complete line, the line will then be drawn in segments by the subsequent calls to the ExtTextOutA. And this would fix the first mentioned problem.
And that leaves us with WidthText() method, which also uses maxLenText to limit maximum string length in non unicode mode. I didn't look at all places where WidthText() is called in Scintilla, but at least on NT, it should not limit string length to the maxLenText, because GetTextExtentPoint32A is not limited either (I tried it on the same string as from my example, and it worked fine). It should probably only be limited on Win9x, but not to 8192, because that is only limit of ExtTextOutA, it should actually be limited to 65535 as it uses 16 bit integer as value. So that part of code in WidthText() should look something like:
if (IsNT())
::GetTextExtentPoint32A(hdc, s, len, &sz);
else
::GetTextExtentPoint32A(hdc, s, Platform::Minimum(len, maxLenText), &sz);
I can also provide you with a patch that does all of the above changes, but since they are pretty much one line changes, I guess that my comments are enough. Also, I didn't notice any ill effects after making mentioned changes, but YMMV as usual. :-)
While there aren't supposed to be limits on these calls, there have been reports (some of which I could reproduce) of various problems, including crashes, when given long strings to process. Problems may be restricted to particular Windows versions, drivers, fonts or character sets. There was a fairly common failure about 5 years ago where strings longer than 5K would not be visible. A contributing issue is that calls will sometimes fail without reporting failure, so since it was not possible to detect and work around, it was simpler to limit or segment.
The first level of segmentation is BreakFinder in PositionCache which is used by Editor::DrawLine to try to limit drawn segments to 300 bytes but it does this by breaking on spaces or punctuation as this avoids combining and multibyte characters. Its only when this is defeated (by something like (A-Z)+) that the limits in PlatWin come into play.
Combined patch with one line changes
First version of MeasureWidths() patch that breaks segments at maxLenText
Second version of MeasureWidths() patch using larger segments
After looking at the revision history of PlatWin.cxx, I'm fairly confident that my changes won't introduce any new problems. The code in PlatWin.cxx has changed significantly over time and now a lot of methods have the ability to draw segmented strings, which results in all these limits actually being pointless. However, since I don't have time to spend trying to prove that my changes are correct by checking all possible situations, only thing that I can propose is that you test this theory by making these changes in one of the next versions of Scintilla and if someone complains, they can easily be reverted. I created a combined patch with all these one line changes, so that you can see them all at one place.
As far as 5K problem is concerned, if I understood it correctly from the revision history, it appeared only in unicode related parts of code, so my changes to the maxLenText won't have any impact on it, because maxLenText is only used in non unicode parts of code. Also, with the introduction of segmented line drawing in DrawTextCommon() method, this 5K limit is no longer even enforced in PlatWin.cxx.
Although internal segmentation by BreakFinder will definitively help with drawing very long lines (in real life segments would almost always be less than 64K), maximum scrolling (and effectively maximum horizontal character position) would still be limited to the value set by maxWidthMeasure and this limits Scintilla's abilities on Windows at least (I can't give you my SQL dumps for testing because they contain confidential data, but trust me, even though text beyond 64K is drawn correctly, scrolling is still limited). On NT in unicode mode maximum scroll width will always be capped to the 1000000 pixels, and this is really not enough (plus as I mentioned before, if you try to force scrolling past this limit, "garbage" will appear). Fixing this is a must and would actually make Scintilla's unicode mode working properly, because non unicode part of the code repeatedly calls GetTextExtentExPointA until complete string is processed, compared to the single call to the GetTextExtentExPointW in unicode part of code. I tracked down when maxWidthMeasure limit was introduced and it was with this change: http://scintilla.hg.sourceforge.net/hgweb/scintilla/scintilla/rev/51ac762a99d5
It appears that the value of 1000000 pixels was not chosen in order to fix some problem, but rather as a value that's just larger than previously enforced limit of 30000 pixels, which made sense only on Win9x. Changing maxWidthMeasure to INT_MAX on NT would be the cleanest possible way to fix all problems related to the unnecessary enforcement of maximum width and should not introduce any new problems. However, if you still would like to have maxWidthMeasure limited to a lower value than INT_MAX, unicode part of code in MeasureWidths() must be fixed so that it can process complete string if it can't fit in width specified by maxWidthMeasure. I created two different patches that fix unicode part of MeasureWidths(), so that complete string is processed in segments. First version limits segments to the maxLenText length (like in non unicode part of code), while the second repeatedly calls GetTextExtentExPointW on complete string until all characters are processed (segments are limited to the number of characters that can fit in maxWidthMeasure). Although both versions are actually slower than simply changing maxWidthMeasure to INT_MAX and only using one call to the GetTextExtentExPointW, second version is somewhat faster than the first, because more than maxLenText characters can fit in width specified by maxWidthMeasure, resulting in less repeating. Both patches are heavily commented so that you can easily understand my code. I hope that you'll fix this problem using one of the proposed solutions (I vote for INT_MAX, but will also be happy with the second version of my patch).
Which now leaves us only with maxLenText limit in non unicode parts of code, but I really don't have any spare time that I could devote for testing if removing it like in combined patch would have any side effects (especially if at least unicode mode gets fixed by one of the above mentioned patches). So, I'll leave this last problem as is, for the time being...
Bugs often take a slow windy route back to the tracker. Sometimes the application maintainer can't reproduce the issue due to machine or software differences. I couldn't initially reproduce the 5K bug so it went untreated for some time. Making a far-reaching change and then waiting for failure reports can add work for all parties and leave Scintilla buggy for a period which can vary due to downstream latencies.
The 5K problem is supposed to be (mostly) solved by BreakFinder and the 512 character segmentation in DrawTextCommon is a 'last ditch' effort as it is unsafe for combining characters.
wxWidgets uses INT_MAX for their equivalent to maxWidthMeasure on NT+ so that is committed.
The platform layer is given text runs that are all in one style, so long strings rarely appear except for plain text and long lexemes. For SQL, I suppose blobs could be longer than 64K.
From the date and mailing list comments, it looks like making maxLenText 64K was for NT 4. Could have been badly ported drivers or a problem in the string fattening entry point.
Thanks for committing INT_MAX fix. The resolution for this bug should probably be changed from "won't fix", since it's at least partially fixed now. :-)
I also took a look at wxWidgets to see if they're limiting text length before calling ExtTextOut() and couldn't find any such limit. That's one more vote in my favor. :-) If the problem is only related to the older versions of Windows (you mentioned NT4), maybe you can enforce maxLenText limit only on versions of Windows prior to XP and ignore it on XP/Vista/7, for example.
While we're on the subject, I noticed bug #3165743. You mentioned there that the slow down is because GetTextExtentExPointW() fails to process the large line, resulting in failing over to the much slower character by character processing using GetTextExtentPoint32W() and that MeasureWidths() should be improved so it measures the widths in segments if that use case is important. I couldn't manage to reproduce GetTextExtentExPointW() failing with the example xml file from that bug report (neither with previous maxWidthMeasure limit, nor with INT_MAX), but if you can reproduce it failing again, instead of INT_MAX fix, you can apply one of the two proposed patches for MeasureWidths() that I previously attached here instead of increasing the limit to INT_MAX, which would make MeasureWidths() measure widths in segments and fix performance problems (which as I said, I couldn't reproduce) from that other bug report.
The online documentation (hope I have the correct page http://msdn.microsoft.com/en-us/library/dd162713%28v=vs.85%29.aspx\) says that the ExtTextOut length is limited to 8192. I thought this was a Windows 9x problem that was fixed in NT but apparently not as it is still in the documentation and 9x is no longer supported by Microsoft - Minimum supported client: Windows 2000 Professional.
ExtTextOut will start failing on arbitrary length values, that are even smaller than 8192 mentioned on MSDN. But that's not the main problem here. The problem lies in the fact that in non unicode parts of code you limit length of complete line before the first call to the ExtTextOut, which also prevents the fallback from going beyond that limit, compared to the unicode part of code where there's no such limit. Here's an example in pseudo code:
if not unicode then
{
lenDraw = Min(len, maxLenText);
if not ExtTextOutA(...) then
fallback
}
else
{
if not ExtTextOutW(...) then
fallback
}
As you can see there's no maxLenText limit in any unicode part of code in PlatWin unit. And my point is that this limit should be removed from non unicode parts of code in DrawTextCommon() and WidthText() as well (or enforced only on Win9x if necessary).
I'd be more inclined to add the check to the Unicode path to ensure it doesn't violate the documentation but I'm not seeing a great deal of motivation for a change.
Nobody reported any problems in the unicode parts of the code, so there's no need to cripple it by imposing the same limits as in ansi parts of the code. It should actually be the other way round, the ansi part should be made the same as unicode. :-))
I'm fairly sure (this was a long time ago) that adding the limit to the ANSI path did actually fix a problem by showing at least the start of the text rather than nothing at all.
Ah, the wonders of working with Windows API and its arbitrary behavior. :-))
BTW Did you take a look at a related bug #3165743 that I mentioned in one of my previous comments (does measuring using single call work correctly for you as it does for me or should segmented measuring be used instead).
Measuring in a single call doesn't help. It fails between 42.5K and 43K characters which is a width around 350K pixels. I'll probably add the same segmentation used in BreakFinder to measuring.
BreakFinder like segmentation would probably add a performance penalty since the segments are too small. Also in case that there's no sensible break point, whole length would be returned instead. It would be better to measure widths in fixed width segments like I did in PlatWin.cxx.patch-v1.txt patch. However, instead of using maxLenText as segment width, smaller value should be used instead (8192 or similar), so that GetTextExtentExPointW() doesn't fail at random.
One thing that may not be obvious since I didn't mention it explicitly in my MeasureWidths() patches is that I did not take UTF16 surrogates in consideration. The reason for this is twofold, none of the other unicode related code from PlatWin takes them in consideration when breaking UTF16 text in segments and GetTextExtentExPointW() doesn't support them by default either. Besides this, breaking text in segments in ansi parts of code doesn't take leadbytes in consideration, either (there is a kludge in MeasureWidths() to handle broken DBCS characters, but it isn't correct in all cases). All these corner cases should actually be fixed, but since default unicode support in Windows API is somewhat limited, I wonder if it would be better to spend time moving to Uniscribe or DirectWrite instead of trying to fix current code.
I'm tempted to propose to leave all current code as is and move all future efforts towards Uniscribe or DirectWrite.
Due to another platform taking quadratic time for MeasureWidths, I have implemented a more complete text segmenter that always chooses an encoding-safe segment when there are no good points to break for space or punctuation. Even the old BreakFinder avoids UTF-16 surrogate problems in Unicode mode since it breaks on whole Unicode characters.
Switching APIs says "new bugs" to me, not "no bugs" - writing similar code for .Net was problematic because the similar call sequence SetMeasurableCharacterRanges / MeasureCharacterRanges is limited to 32 positions and this was not documented at the time.
DirectWrite doesn't run on WIndows XP. It would be worthwhile implementing with DirectWrite as an option or alternate download but it can't be a replacement for quite a while.
The approximately 42.5K / 350K pixel limits are strange since they are not near any magic numbers and may be tied to particular font/size/device/version issues that could be avoided in other ways.
The reason for suggesting the new API was not to avoid bugs. There would probably be bugs inherited from the low level API (i.e. Uniscribe internally works with all methods that Scintilla already uses for drawing text and there were many fixes to the DirectWrite in Windows 7 SP1). The main reason was the fact that Windows API by default doesn't support working with UTF16 surrogates at all, so it is rather limited in its unicode capabilities and it's basically pointless to even take care when breaking UTF16 strings. Instead of trying to patch all corner cases, it would be much better to spend that time adding support for Uniscribe or DirectWrite instead, which would actually improve Scintilla's unicode support. All current code should be left as is, while any new unicode code (Uniscribe / DirectWrite) could be enabled either at compile time or at run-time depending on the implementation (notice that I did not say to completely replace current code here or in my previous comment).
The Windows API has quite good support for UTF-16 surrogates: try pasting the Osmanya character "𐒝" into Scintilla and watch what happens inside to MeasureWidths and DrawTextCommon. GetTextExtentExPointW is a little strange in that it spreads the width between the two surrogates but Scintilla just takes the full width.
See http://www.scintilla.org/nonBMP.txt