stb_textedit.h crash bug in stb_textedit_discard_redo()

[ocornut]

As pointed on twitter, just posting here for reminder/reference.

In stb_textedit_discard_redo()

-         STB_TEXTEDIT_memmove(state->undo_char + state->redo_char_point, state->undo_char + state->redo_char_point-n, (size_t) ((size_t)(STB_TEXTEDIT_UNDOSTATECOUNT - state->redo_char_point)*sizeof(STB_TEXTEDIT_CHARTYPE)));
+         STB_TEXTEDIT_memmove(state->undo_char + state->redo_char_point, state->undo_char + state->redo_char_point-n, (size_t) ((size_t)(STB_TEXTEDIT_UNDOCHARCOUNT - state->redo_char_point)*sizeof(STB_TEXTEDIT_CHARTYPE)));

This would haven't triggered so much as stb_textedit_discard_redo() is rather infrequently called (it does get called when we consume more than STB_TEXTEDIT_UNDOCHARCOUNT characters worth of undo records.

[chrisws]

Hi,

I found the same issue and this was my fix:

     short count = state->redo_char_point > STB_TEXTEDIT_UNDOSTATECOUNT ? STB_TEXTEDIT_UNDOSTATECOUNT : state->redo_char_point;
     STB_TEXTEDIT_memmove(state->undo_char + state->redo_char_point, state->undo_char + state->redo_char_point-n, (size_t) ((STB_TEXTEDIT_UNDOSTATECOUNT - count)*sizeof(STB_TEXTEDIT_CHARTYPE)));

This avoid passing a negative size value to memmove. Not sure whether this is the full correct fix or just masking some other issue.

[ocornut]

TL;DR; you might already have the same fix locally in your version at work. Might be easier to just check for that before engaging with that bug.

@chrisws That will prevent your software from crashing but still incorrect.

@nothings Following the twitter conversation 3 weeks ago I had another bug reported
ocornut/imgui#715

Basically the test sequence that is natural to repro within the ImGui demo is:

• STB_TEXTEDIT_UNDOCHARCOUNT = 999
• initial text buffer is 350 long
• copy and paste 3 times, buffer is now 350*4 = 1400 char long, not using the undo char buffer yet.
• undo 2 times, ok, 350x2 chars used in the undo char buffer
• undo a 3rd time: we don't have enough room in char buffer, stb_textedit_discard_redo is called and state becomes incorrect.
• calling redo there likely to lead to unexpected result.

This is merely an example and of course it is just a case of discard_redo being broken.

I'm quite confused by the undo-stack code but I think I came up with two fixes.

A. In stb_text_redo

   if (r.insert_length) {
      // easy case: need to insert n characters
      STB_TEXTEDIT_INSERTCHARS(str, r.where, &s->undo_char[r.char_storage], r.insert_length);
++      s->redo_char_point += r.insert_length;
   }

Without this fix, a simple sequence of Paste, Undo/Redo/Undo/Redo/... would exhaust the character buffer.

B. in stb_textedit_discard_redo
Replace

++state->redo_point;
STB_TEXTEDIT_memmove(state->undo_rec + state->redo_point-1, state->undo_rec + state->redo_point, (size_t) ((size_t)(STB_TEXTEDIT_UNDOSTATECOUNT - state->redo_point)*sizeof(state->undo_rec[0])));

By

STB_TEXTEDIT_memmove(state->undo_rec + state->redo_point, state->undo_rec + state->redo_point-1, (size_t) ((size_t)(STB_TEXTEDIT_UNDOSTATECOUNT - state->redo_point)*sizeof(state->undo_rec[0])));
++state->redo_point;

This is coming from tracing into the code and displaying the state on screen. This is the sequence being executed BEFORE the fix:

Select all, copy, unselect, paste 3 times, undo 3 times, redo
The third undo calls stb_textedit_discard_redo and you can see the entries at the bottom looking invalid.

The final redo triggers character insertion at an invalid position. Note that the assert at the end is the code in my STB_TEXTEDIT_INSERTCHARS implementation asserting that pos <= STB_TEXTEDIT_STRINGLEN(obj). Some other implementation of the INSERTCHARS function may silently return and then the bug wouldn't be so noticeable (but undo/redo stack still appears broken).

And AFTER the fix:

Basically as I understand stb_textedit_discard_redo was just very wrong. It's very easy to overlook because STB_TEXTEDIT_UNDOCHARCOUNT can be increased,STB_TEXTEDIT_INSERTCHARS can silently fail, and it requires exhausting the buffer AND using undo+redo.

[chrisws]

I finally got around to testing the suggested fixes - Fix A (In stb_text_redo) works for me and seems most logically correct.

[ocornut]

My wording was perhaps ambiguous, but I meant that both fixes are desirable and required.

PS: dear imgui has been running with those fixes since I posted it, so I presume by now it is relatively safe. But then the bug discussed here took a longer time to find..

[chrisws]

Hi,

Thanks so much for your kind update.

I think there may be one more bug in stb_textedit_discard_redo() - in this line:
STB_TEXTEDIT_memmove(state->undo_char + state->redo_char_point, state->undo_char + state->redo_char_point-n, (size_t) ((STB_TEXTEDIT_UNDOSTATECOUNT - state->redo_char_point)*sizeof(STB_TEXTEDIT_CHARTYPE)));

shouldn't STB_TEXTEDIT_UNDOSTATECOUNT instead be STB_TEXTEDIT_UNDOCHARCOUNT ?

This is with both of your changes applied to version 1.11. On my system it makes the difference between crashing or not.

[ocornut]

Correct. This is actually what the first post of this thread discusses.

For what it is worth, my modified version is located here:
https://github.com/ocornut/imgui/blob/master/stb_textedit.h

[nothings]

I believe the correct fix for B is

  STB_TEXTEDIT_memmove(state->undo_rec + state->redo_point+1, state->undo_rec + state->redo_point, (size_t) ((STB_TEXTEDIT_UNDOSTATECOUNT - state->redo_point)*sizeof(state->undo_rec[0])));

The range of redo records is [redo_point, STATECOUNT). After deleting the last one, we want to move all the remaining ones down towards the end (because it's a stack growing downwards). So @ocornut's fix moves one extra item (the item at redo_point-1, to redo_point). Most of the time this is harmless because the slot at redo_point WAS just being used by redo, but is about to be unused, so moving something into it should have no effect.

However, if you ever got redo_point to 0 (which I think is possible), it would be moving from outside the array, undo_rec[-1]. This will access earlier fields in the TexteditState struct, so should be harmless, but might as well fix it right.

(I suspect the original memmove was backwards because I sometimes get fooled by 'move foo.txt bar.txt' being left-to-right and forget that memmove() is still right-to-left. Probably this code should be cleaned up to be clearer.)

Other than that the fixes look right to me. I haven't tested them, though.

[nothings]

Fixed (untested!) in next version.

[ocornut]

I believe the correct fix for B is

I forgot to answer this earlier (hadn't updated to latest vanilla stb_textedit.h until now).
Your modified line has another corruption:

  STB_TEXTEDIT_memmove(state->undo_rec + state->redo_point+1, state->undo_rec + state->redo_point, (size_t) ((STB_TEXTEDIT_UNDOSTATECOUNT - state->redo_point)*sizeof(state->undo_rec[0])));

Should be:

  STB_TEXTEDIT_memmove(state->undo_rec + state->redo_point+1, state->undo_rec + state->redo_point, (size_t) ((STB_TEXTEDIT_UNDOSTATECOUNT - state->redo_point - 1)*sizeof(state->undo_rec[0])));

(Size to copy is 1 record less, otherwise we are corrupting undo_char[]).

I suggest reopening the Issue so it's not forgotten - then it can be looked at later.

[ocornut]

FYI Sean (as you are on a stb_ streak right now :)
I realize this thread is overally quite confusing with no clear call-to-action.

I worked on this two days ago and thought I fixed the last issue and was about to submit a "definitive report" but a user is still reporting an issue with some static analyzer. Will report back when I know more. You may want to skip this right now if it is too confusing.

[nothings]

No worries, as I'm only doing PRs not issues as that was enough of a workload :(

[chrisws]

If I can help in anyway let me know (testing etc)

…

On Fri, Feb 8, 2019 at 3:27 AM Sean Barrett ***@***.***> wrote: No worries, as I'm only doing PRs not issues as that was enough of a workload :( — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#321 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAv64bz84AHU6-HtdM9ZoPNjgMlg-_Dwks5vLGISgaJpZM4IuWHy> .

[rygorous]

The crash appears to be fixed by Omar's PR and the discussion thread for the PR notes that static analysis appears to be overly picky here, so I don't think there's anything left to do on this. Closing.

[ocornut]

FYI (may or not be related to this)
There was another bug report on our end which I haven't investigated yet:
ocornut/imgui#4038
As our version has various mods it may be our issue or may be a stock stb_textedit issue.
I'll try to investigate the linked issue and report here (this or new issue depending on result).

Issues I was referring to seems reported as a separate issue #734