Colorer messes up when given a lexer that supplies nonzero backups

Start with gui-test/framework/tests/color-text.rkt, where the issue says the existing backing-up-lexer test lives and the proposed regression tests should be added. Read the colorer’s start-colorer behavior alongside those tests, then run the three proposed cases. Done when incremental token ranges and colors match the expected results for edits inside backed-up tokens and at token boundaries.

I found two related bugs while working on the color lexer for Punct, which kinda does need nonzero backups for some parts of Markdown syntax. The docs indicate that nonzero backups are a rare or unusual case, and the existing tests don't really exercise these cases, which may explain why this hasn't been encountered before.

I will submit a PR with tests to fix. Since the bugs are not trivial to explain I wanted to put the explanation in an issue first. I'm putting both bugs in one issue because their MVEs share a bunch of code.

What version of Racket are you using?

This is Racket 9.3 [CS] on macOS 27.0.1.

What program did you run?

The MVE for these is modest but not tiny, so I'll do my best to explain concisely.

I'm going off the color:text<%> start-colorer docs, which define the backup arg as "the maximum number of characters to back up (counting from the start of the token) and for re-parsing after a change to the editor within the token's region." The invariants list further down says:

A change to the stream must not change the tokenization of the stream prior to the token immediately preceding the change plus the backup distance.

The docs give an example case where " 1 2 3 (no closing quote) becomes " 1 2 3". They also say that a lexer can handle that case if it can "precisely track backup distances."

So if a lexer obeys these rules, the tokens after an incremental edit should be identical to the tokens a fresh colorer would produce from the same text. But, these bugs involve cases where an incremental edit causes the colorer to mess up the tokenization so that it differs from what that fresh result would be.

A simple lexer for reproducing these bugs is below.

#lang racket/gui
(require framework)

(define (lexer in offset mode)
  (define-values (_l col pos) (port-next-location in))
  (define (tok type rx)
    (define s (bytes->string/utf-8 (car (regexp-match rx in))))
    (define backup (if (regexp-match? #rx"\n" s) 0 col))
    (values s type #f pos (+ pos (string-length s)) backup 'line))
  (cond
    [(eof-object? (peek-char in)) (values eof 'eof #f #f #f 0 mode)]
    [(regexp-match-peek #rx"^\"[^\"\n]*\"" in) (tok 'string #rx"^\"[^\"\n]*\"")]
    [(regexp-match-peek #rx"^\"" in) (tok 'error #rx"^\"")]
    [(regexp-match-peek #rx"^[ \n]" in) (tok 'white-space #rx"^[ \n]+")]
    [else (tok 'symbol #rx"^[^ \n\"]+")]))

;; helper
(define (my-editor s)
  (define t (new (color:text-mixin text:basic%)))
  (send t insert s)
  (send t start-colorer symbol->string lexer '())
  (send t freeze-colorer)
  (send t thaw-colorer)
  t)

;; another helper: list tokens '(("text" type) ...)
;; or - if a position's token range doesn't contain it - (bad-range position start end)
(define (tokens t)
  (let loop ([p 0])
    (if (>= p (send t last-position))
        '()
        (let-values ([(s e) (send t get-token-range p)])
          (if (and s e (> e p))
              (cons (list (send t get-text s e) (send t classify-position p)) (loop e))
              (cons (list 'bad-range p s e) (loop (add1 p))))))))

Bug 1: after a change inside a token with a nonzero backup, the tokens no longer match the buffer

With the above example lexer, we take an editor with buffer contents x\naa bb cc\ndd\n and delete the second b:

(define (check t)
  (define fresh (my-editor (send t get-text)))
  (printf "incremental: ~s\n\nfresh: ~s\n" (tokens t) (tokens fresh)))

(define t1 (my-editor "x\naa bb cc\ndd\n"))
(send t1 delete 6 7)
(check t1)

What should have happened?

The “incremental” and “fresh” lists given by check should be identical. Instead we get:

incremental: (("x" symbol) ("\n" white-space) ("aa" symbol) (" b" symbol) (" " white-space) ("cc" symbol) ("\n" white-space) (bad-range 10 9 10) (bad-range 11 9 10) (bad-range 12 9 10))

fresh: (("x" symbol) ("\n" white-space) ("aa" symbol) (" " white-space) ("b" symbol) (" " white-space) ("cc" symbol) ("\n" white-space) ("dd" symbol) ("\n" white-space))

The colorer reports " b" as one symbol token, but that is not a token the lexer could ever produce. Also, the token list ends before the buffer ends: get-token-range at positions 10 to 12 gives the range 9–10, which does not contain them.

Bug 2: a change at the end of a token ignores that token's backup

This is actually the example given by the docs. The buffer is " 1 2 3\nz\n. The repro inserts " after the 3:

(define t2 (my-editor "\" 1 2 3\nz\n"))
(send t2 insert "\"" 7)
(check t2)

What should have happened?

Again, check should yield identical lists, but it doesn't:

incremental: (("\"" error) (" " white-space) ("1" symbol) (" " white-space) ("2" symbol) (" " white-space) ("3" symbol) ("\"" error) ("\n" white-space) ("z" symbol) ("\n" white-space))

fresh: (("\" 1 2 3\"" string) ("\n" white-space) ("z" symbol) ("\n" white-space))

3 is "the token immediately preceding the change" (from the docs), and its backup goes back to the start of the line. But the colorer uses only the backup of the token after the change, which is the newline with backup 0. So the opening " remains an error token.

Existing tests

The existing backing-up-lexer test doesn't catch bug 1 because its edit is in the last token of the buffer. Bug 1 is about where the colorer thinks the old tokens it keeps after the edit begin, and with the edit in the last token there are no old tokens to keep. If you give it some text after the edit, it reproduces shows bug 1 with no other changes. It can't catch bug 2 at all, because backing-up-lexer gives every token a backup of 2. After an edit at a token boundary, the token after the edit also has a positive backup, so the colorer backs up anyway. Bug 2 only shows when the token after the edit has a backup of 0, like the line-ending whitespace in the repro lexer above.

These tests would be added to the end of color-text.rkt. All three currently fail. The first one uses the existing backing-up-lexer but with the edit in the middle. The other two are for the cases above.

;; a change with old tokens after it, using a backup
(let ()
  (define t (new color:text%))
  (send t insert "aaabcaaabc")
  (start-backing-up-colorer t)
  (send t freeze-colorer)
  (send t thaw-colorer)
  (send t insert "a" 4 4)
  (send t freeze-colorer)
  (send t thaw-colorer)

  (check-equal? (get-colors t)
                '((symbol 0 1)
                  (parenthesis 1 2)
                  (symbol 2 3)
                  (constant 3 4)
                  (symbol 4 7)
                  (parenthesis 7 8)
                  (constant 8 9)
                  (no-color 9 11))))

;; Tokenizes a line as a "..." string when it has a closing quote and as a
;; lone " error token otherwise, so each token's backup reaches back to the
;; start of its line. Line-ending whitespace has no backup.
(define (line-backup-lexer port offset mode)
  (define-values (line col pos) (port-next-location port))
  (define (token type rx)
    (define s (bytes->string/utf-8 (car (regexp-match rx port))))
    (values s type #f pos (+ pos (string-length s))
            (if (regexp-match? #rx"\n" s) 0 col)
            'line))
  (cond
    [(eof-object? (peek-char port)) (values "eof" 'eof #f #f #f 0 mode)]
    [(regexp-match-peek #rx"^\"[^\"\n]*\"" port) (token 'string #rx"^\"[^\"\n]*\"")]
    [(regexp-match-peek #rx"^\"" port) (token 'error #rx"^\"")]
    [(regexp-match-peek #rx"^[ \n]" port) (token 'white-space #rx"^[ \n]+")]
    [else (token 'symbol #rx"^[^ \n\"]+")]))

(define (start-line-backup-colorer t)
  (send t start-colorer symbol->string line-backup-lexer '()))

;; a change inside a token with a backup
(let ()
  (define t (new color:text%))
  (send t insert "x\naa bb cc\ndd\n")
  (start-line-backup-colorer t)
  (send t freeze-colorer)
  (send t thaw-colorer)
  (send t delete 6 7)
  (send t freeze-colorer)
  (send t thaw-colorer)

  (check-equal? (get-colors t)
                '((symbol 0 1)
                  (white-space 1 2)
                  (symbol 2 4)
                  (white-space 4 5)
                  (symbol 5 6)
                  (white-space 6 7)
                  (symbol 7 9)
                  (white-space 9 10)
                  (symbol 10 12)
                  (white-space 12 13))))

;; a change at the end of a token with a backup
(let ()
  (define t (new color:text%))
  (send t insert "\" 1 2 3\nz\n")
  (start-line-backup-colorer t)
  (send t freeze-colorer)
  (send t thaw-colorer)
  (send t insert "\"" 7 7)
  (send t freeze-colorer)
  (send t thaw-colorer)

  (check-equal? (get-colors t)
                '((string 0 8)
                  (white-space 8 9)
                  (symbol 9 10)
                  (white-space 10 11))))

Again I have a PR which fixes these tests almost ready to go, and I'll open it as soon as I have time.

Disclosure, these issues were originally diagnosed by Claude. I’ve made a point of working through the docs and doing manual experiments to be sure I thoroughly understand them, and I wrote this issue myself. (It's been quite educational)