# Color lexer backup distances and \`dont-stop\` **URL:** \ **Category:** Questions & Answers\ **Tags:** question\ **Created:** [July 28, 2023, 5:02pm UTC](https://racket.discourse.group/t/color-lexer-backup-distances-and-dont-stop/2170 "2023-07-28T17:02:50Z")\ **Posts on this page:** 9\ **Page:** 1
**Author:** ![LiberalArtist](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/liberalartist/32/151_2.png) [@LiberalArtist](https://racket.discourse.group/u/LiberalArtist)\ **Post date:** [July 28, 2023, 5:02pm UTC](https://racket.discourse.group/t/color-lexer-backup-distances-and-dont-stop/2170/1 "2023-07-28T17:02:50Z")
I'm trying to implement a [color lexer](https://docs.racket-lang.org/framework/Color.html#%28meth._%28%28%28lib._framework%2Fmain..rkt%29._color~3atext~3c~25~3e%29._start-colorer%29%29) for the syntax of `.gitignore` files. For reasons I'll explain, I think I need non-zero backup distances and `dont-stop`, which have always confused me, and I want to check my understanding. 1. The docs say: 2. Does the rule that: 3. Is it reasonable to simplify the implementation by using a conservative approximation of backup distances and `dont-stop`, rather than the precise minimum? Some specifics might be helpful. The `.gitignore` syntax is [defined](https://git-scm.com/docs/gitignore#_pattern_format) in terms of the [POSIX](https://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3_chap02.html#tag_18_13) function `fnmatch` and [globbing](https://manpages.debian.org/bookworm/manpages/glob.7.en.html). I want to implement the syntax and semantics of standard `.gitignore`, so I need to handle ranges in square brackets: the relevant parts are almost the same as for `regexp`, but also support the `‹posix›` character classes like `pregexp`. (They're not a subset of `pregexp`, either, though.) The syntax has some confusing subtleties. For example: - `[[:alpha:]]b` matches `ab`, but `[[:alpha]]b` matches `:]b` - `[a-y]z` matches `xz`, but `[a-]z` matches `-z` Because I find this deeply confusing, I want to color these cases differently. I need at least one character of look-ahead to distinguish `-` as range syntax vs. a literal character, and a bunch of look-ahead for the POSIX character classes. But all of these cases can only occur in the `mode` for lexing the tail of a bracketed form, so I'm hoping I can just track the backup distance to the beginning of that mode and use `dont-stop` until the end of it, rather than tracking specific backup distances within the mode. * * * ETA, for posterity: > [@LiberalArtist](#): > > The `.gitignore` syntax is [defined](https://git-scm.com/docs/gitignore#_pattern_format) in terms of the [POSIX](https://pubs.opengroup.org/onlinepubs/9699919799/utilities/V3_chap02.html#tag_18_13) function `fnmatch` and [globbing](https://manpages.debian.org/bookworm/manpages/glob.7.en.html). Despite what `gitignore(5)` currently says, Git has not used `fnmatch` at all since v 2.0.0 (May 2014) and not by default since v1.8.4 (August 2013): see upstream commit [70a8fc9](https://git.kernel.org/pub/scm/git/git.git/commit/?id=70a8fc999d9f0afbc793b21bbb911ecde4e24367). Instead, they use an implementation called `wildmatch` inherited from `rsync`, which is under a variant of the BSD license (I haven't figured out the specific SPDX identifier, but see [Replace fnmatch with wildmatch by pks-t · Pull Request #5110 · libgit2/libgit2 · GitHub](https://github.com/libgit2/libgit2/pull/5110) for details). It has similar but different semantics than `fnmatch`, generally simplified (e.g. no `LC_CTYPE` sensitivity, no POSIX collating symbols (i.e. `[.`_name_`.]`) or equivalence class expressions (i.e. `[=`_name_`=]`)). On the one hand, the semantics are basically implementation-defined; on the other hand, and least they are defined by _one_ implementation. ---
**Author:** ![greghendershott](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/greghendershott/32/98_2.png) [@greghendershott](https://racket.discourse.group/u/greghendershott)\ **Post date:** [July 29, 2023, 2:33pm UTC](https://racket.discourse.group/t/color-lexer-backup-distances-and-dont-stop/2170/2 "2023-07-29T14:33:30Z")
While waiting for someone like @robby or @mflatt to give a more-informed answer, in case it helps I can share an example of code using this interface: [https://github.com/greghendershott/racket-mode/blob/hash-lang/racket/hash-lang.rkt#L280-L404](https://github.com/greghendershott/racket-mode/blob/hash-lang/racket/hash-lang.rkt#L280-L404) On the downside: - This is from the `hash-lang` branch not yet merged to main, so it's beta quality. - Although "it works" I may have misunderstood the intent. - The `token-tree%` and `paren-tree%` API somewhat obscure things. On the upside, compared the to the equivalent (ish?) code in DrRacket, I think the logic is _maybe_ easier to follow, because the code: - is more centralized - is less concerned with editor change coordination - has more comments explaining the intent (although, again, my intent might be wrong) * * * p.s. In your specific case, because a `.gitignore` file is line-oriented, some back-up/look-ahead strategy involving whitespace tokens for newlines might suffice? (That might re-tokenize more than necessary, but probably won't be so inefficient to matter in practice?) ---
**Author:** ![robby](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/robby/32/7_2.png) [@robby](https://racket.discourse.group/u/robby)\ **Post date:** [July 30, 2023, 12:08am UTC](https://racket.discourse.group/t/color-lexer-backup-distances-and-dont-stop/2170/3 "2023-07-30T00:08:03Z")
It sounds to me like you understand @LiberalArtist . 1. I would say that `dont-stop` is useful when you want to color some region in two (or more) different colors but you cannot parse them independently. So, you parse them both then return the first token with a dont-stop and then return the second one. It is shoehorning the ability to return lists of tokens into a flat-style API. (Hope this makes sense.) 2. I think that the backup distance is a separate thing from the dont-stop result. It may be that you can use one to get the same effect as the other, tho, I'm not sure. Maybe if you have a specific example I can answer this one better. (@mflatt added the backup distance to support the scribble lexer, tho, so he may have a better answer here.) 3. Sure. The main thing is to keep tokens relatively small; they don't have to be tiny (for example, strings are single tokens in `#lang racket` and then can, in principle, span a giant file) but the size of the token controls the interactivity when editing the files in DrRacket. Smaller and more tokens means more opportunities for DrRacket to respond to the user's editing events, as DrRacket won't interrupt the colorer in the middle of computing a single token. I think @greghendershott 's advice is good, tho. Processing an entire line at once and putting the processing result into the mode and then returning a sequence of tokens via `dont-stop` until the end of the line seems like a (relatively?) easy way to get something going. hth! ---
**Author:** ![LiberalArtist](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/liberalartist/32/151_2.png) [@LiberalArtist](https://racket.discourse.group/u/LiberalArtist)\ **Post date:** [August 5, 2023, 7:11pm UTC](https://racket.discourse.group/t/color-lexer-backup-distances-and-dont-stop/2170/4 "2023-08-05T19:11:43Z")
Thanks @greghendershott and @robby. > [@robby](#): > > 1. I would say that `dont-stop` is useful when you want to color some region in two (or more) different colors but you cannot parse them independently. So, you parse them both then return the first token with a dont-stop and then return the second one. It is shoehorning the ability to return lists of tokens into a flat-style API. (Hope this makes sense.) This makes a lot of sense! (I think.) > [@LiberalArtist](#): > > 1. Does the rule that: > [@robby](#): > > 1. I think that the backup distance is a separate thing from the dont-stop result. It may be that you can use one to get the same effect as the other, tho, I'm not sure. Maybe if you have a specific example I can answer this one better. (@mflatt added the backup distance to support the scribble lexer, tho, so he may have a better answer here.) Trying to write an example left me feeling even more shaky about my understanding here, but here's an attempt based on the `" 1 2 3` example from the [`start-colorer` docs](https://docs.racket-lang.org/framework/Color.html#%28meth._%28%28%28lib._framework%2Fmain..rkt%29._color~3atext~3c~25~3e%29._start-colorer%29%29). Imagine that, if a buffer contains: ```scheme [ 1 2 3 ``` we want to color `[` as an error token, but if it is edited to contain: ```scheme [1 2 3] ``` then we instead want to color `[` as a parenthesis token. As the docs explain, since that would "change the tokenization of the stream prior to the token immediately preceding the change", we would need a non-zero backup distance. But do we also need a `dont-stop`? It seems like we "cannot parse … independently" the opening `[`, since we need to peek ahead to see if there is a matching `]`. Per the docs, "that read-ahead will be inconsistent if an edit happens, so a [`dont-stop`](https://docs.racket-lang.org/syntax-color/dont-stop.html#%28def._%28%28lib._syntax-color%2Flexer-contract..rkt%29._dont-stop%29%29) structure ensures that no changes to the buffer happen between calls." If you only need to peek into the next token, as with `[a-]` vs. `[a-z]`, IIUC you need `dont-stop` but don't need a backup distance. I know that `syntax-color/scribble-lexer` tracks backup distances but doesn't use `dont-stop`, so I gather that's a possible set of circumstances, but I don't understand how or why. (When I wrote that these "have always confused me", I had `scribble-lexer` especially in mind. I think it would help to have an example of "a change later [that] could turn the non-match into a match".) ``` ;; If we don't match rx:opener in a place where we might otherwise ;; match, and there is a "|" at that point, then a change later ;; could turn the non-match into a match, AND there could be ;; arbitrarily many Scheme tokens in between. So we carry the backup ;; position, use it as necessary (from places that might be between a "|" ;; and a potential match creator), and cancel it when it's clearly ;; not needed anymore (which includes after any token that isn't a ;; Scheme token). ``` > [@robby](#): > > 1. I think @greghendershott 's advice is good, tho. Processing an entire line at once and putting the processing result into the mode and then returning a sequence of tokens via `dont-stop` until the end of the line seems like a (relatively?) easy way to get something going. This is a very appealing idea. As it happens, I got the skeleton of an incremental lexer for the actual patterns (by closely imitating `racket/src/regexp/parse/range.rkt`), but it would work very well for the first line: since the whole `#lang` line counts as a comment for Git, it could contain some optional Racket tokens, e.g. to have: ```scheme #lang foo/gitignore #:skip-bad-patterns [[:ctrl:]] ``` implement the strictly Git-compatible behavior of a pattern that never matches, instead of telling you at `read` or `compile` time that you misspelled `[[:cntrl:]]`. Would I need to peek the line rather than read it, though? I'm not sure if anything explicitly says this—maybe [`check-colorer-results-match-port-before-and-afters`](https://docs.racket-lang.org/syntax-color/dont-stop.html#%28def._%28%28lib._syntax-color%2Flexer-contract..rkt%29._check-colorer-results-match-port-before-and-afters%29%29)?—but I was under the impression that you need to keep the position of the input port consistent with the token positions. ---
**Author:** ![mflatt](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/mflatt/32/6_2.png) [@mflatt](https://racket.discourse.group/u/mflatt)\ **Post date:** [August 7, 2023, 7:24pm UTC](https://racket.discourse.group/t/color-lexer-backup-distances-and-dont-stop/2170/5 "2023-08-07T19:24:09Z")
Using backup without `dont-stop` in `scribble-lexer` is probably a bug. I think the history is that the need for backup was noticed before the need for something like `dont-stop`. When `dont-stop` was added later, it wasn't immediately obvious that the two always need to go together. As far as I can tell now, they need to be used in tandem. A problem with `dont-stop` as implemented currently is that it makes the editor less interactive, because `dont-stop` forces the colorer to keep going before editing is allowed again. The problem with backup is that it doesn't tell the colorer to expect backup information in the future, so the colorer doesn't know that editing after the current coloring frontier may need to move the coloring frontier backward. The combination of backup information with `dont-stop` gives the colorer the information that it needs, although not in a great form. Even without improving the interface, though, maybe the colorer could be improved by treating `dont-stop` to mean that editing later needs to rewind coloring to the point where `dont-stop`s started. ---
**Author:** ![LiberalArtist](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/liberalartist/32/151_2.png) [@LiberalArtist](https://racket.discourse.group/u/LiberalArtist)\ **Post date:** [August 9, 2023, 12:09am UTC](https://racket.discourse.group/t/color-lexer-backup-distances-and-dont-stop/2170/6 "2023-08-09T00:09:11Z")
> [@mflatt](#): > > I think the history is that the need for backup was noticed before the need for something like `dont-stop`. When `dont-stop` was added later, it wasn't immediately obvious that the two always need to go together. As far as I can tell now, they need to be used in tandem. I'm persuaded that needing a backup distance always implies needing `dont-stop`, but I thought the following was an example of needing `dont-stop` _not_ necessarily implying the need for a non-zero backup distance (I could be wrong, though!): > [@LiberalArtist](#): > > If you only need to peek into the next token, as with `[a-]` vs. `[a-z]`, IIUC you need `dont-stop` but don't need a backup distance. (I'm assuming that in `[a-]` you want to color `-` as a literal character, but in `[a-z]` you want to color it as an infix operator.) In the course of looking into this, I had also come across @greghendershott's call for an example of `dont-stop` in use: > [@Example of a lang lexer that returns a \`dont-stop\` struct?](https://racket.discourse.group/t/example-of-a-lang-lexer-that-returns-a-dont-stop-struct/438): > > A lang's [module lexer can return a dont-stop struct](https://docs.racket-lang.org/syntax-color/index.html#%28def._%28%28lib._syntax-color%2Flexer-contract..rkt%29._dont-stop%29%29). I would like to test my handling of that. But so far (with e.g. langs racket, rhombus, and scribble/manual) I'm never seeing a dont-stop. What's an example of such a #lang? What's some minimal example program in that #lang eliciting the dont-stop value? Since no one came up with an example, it might be that there's more ability to make changes without causing problems in practice than I would otherwise assume. ---
**Author:** ![mflatt](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/mflatt/32/6_2.png) [@mflatt](https://racket.discourse.group/u/mflatt)\ **Post date:** [August 10, 2023, 3:55pm UTC](https://racket.discourse.group/t/color-lexer-backup-distances-and-dont-stop/2170/7 "2023-08-10T15:55:07Z")
> [@LiberalArtist](#): > > I thought the following was an example of needing `dont-stop` _not_ necessarily implying the need for a non-zero backup distance: I'm not sure why you'd need `dont-stop` in that case. If I understand correctly, no backup is needed because any change to the next character will restart lexing at the token that ends at the edited position. But it seems like that would also avoid the need for `dont-stop`. Maybe my conclusion is based more on what `dont-stop` does than how it's documented. > [@LiberalArtist](#): > > n the course of looking into this, I had also come across @greghendershott's call for an example of `dont-stop` in use: Not sure whether I missed that message or just forgot to answer, but the shrubbery lexer does produce `dont-stop` any time it's going to produce a non-zero backup next: ```scheme (require shrubbery/syntax-color) (define in (open-input-string "@/{}")) ;; extra "/" would change "@" treatment (shrubbery-lexer in 0 #f) ;; last result is `(dont-stop '#s(pending-backup-mode 1 initial))` ``` ---
**Author:** ![LiberalArtist](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/liberalartist/32/151_2.png) [@LiberalArtist](https://racket.discourse.group/u/LiberalArtist)\ **Post date:** [August 10, 2023, 9:10pm UTC](https://racket.discourse.group/t/color-lexer-backup-distances-and-dont-stop/2170/8 "2023-08-10T21:10:06Z")
> [@mflatt](#): > > > [@LiberalArtist](#): > > > > I thought the following was an example of needing `dont-stop` _not_ necessarily implying the need for a non-zero backup distance: > > I'm not sure why you'd need `dont-stop` in that case. If I understand correctly, no backup is needed because any change to the next character will restart lexing at the token that ends at the edited position. But it seems like that would also avoid the need for `dont-stop`. Maybe my conclusion is based more on what `dont-stop` does than how it's documented. That makes sense. The documentation does say, albeit indirectly, that "the token immediately preceding" a change to the input stream _may_ change even if the backup distance is 0. It does seem that, to implement that behavior, the caller of a `lexer/c` would need to, as you say, "restart lexing at the token that ends at the edited position" (or, IIUC, if the edited position were in the middle of a token spanning more than one position, the token before the one containing the edited position). So I understand why that scenario would work out without `dont-stop`. But I don't think the docs explicitly say that it will. > [@LiberalArtist](#): > > > [@robby](#): > > > > 1. I think @greghendershott 's advice is good, tho. Processing an entire line at once and putting the processing result into the mode and then returning a sequence of tokens via `dont-stop` until the end of the line seems like a (relatively?) easy way to get something going. > > […] > > Would I need to peek the line rather than read it, though? I'm not sure if anything explicitly says this—maybe [`check-colorer-results-match-port-before-and-afters`](https://docs.racket-lang.org/syntax-color/dont-stop.html#%28def._%28%28lib._syntax-color%2Flexer-contract..rkt%29._check-colorer-results-match-port-before-and-afters%29%29)?—but I was under the impression that you need to keep the position of the input port consistent with the token positions. Is there ever a case when the fourth result of a lexer, i.e.: > _start_ — The starting position of the token (or `#f` for an end-of-file). This number is relative to the third result of `(port-next-location input-port)`. may licitly be something other than `#f` or exactly the third result of `(port-next-location input-port)`? The documentation for [`check-colorer-results-match-port-before-and-afters`](https://docs.racket-lang.org/syntax-color/dont-stop.html#%28def._%28%28lib._syntax-color%2Flexer-contract..rkt%29._lexer%2A%2Fc%29%29) says the following must hold: ```scheme (or (equal? type 'eof) (and (<= pos-before new-token-start pos-after) (<= pos-before new-token-end pos-after))) ``` Setting aside `'eof`, we could rewrite this as a system of four inequalities: ```scheme (and (<= pos-before new-token-start) ;[1] (<= new-token-start pos-after) ;[2] (<= pos-before new-token-end) ;[3] (<= new-token-end pos-after)) ;[4] ``` The `start-colorer` documentation states the invariant that: > Every position in the buffer must be accounted for in exactly one token, and every token must have a non-zero width. This seems to add a fifth requirement: ```scheme (< new-token-start new-token-end) ;[5] ``` Assuming re `[1]` that `(< pos-before new-token-start)` were true, the positions between `pos-before` and `new-token-start` would not be part of the current token. They must be part of some token ("every position in the buffer must be accounted for in exactly one token"), so they would have to be part of the token preceding the current token. But if the positions were part of the proceeding token, the preceding call would have violated `[4]`. So, by contradiction, `[1]` really requires `(= pos-before new-token-start)`. The same logic seems to apply to `[4]`, changing it to `(= new-token-end pos-after)`. If so, `[5]` would imply `[2]` and `[3]` by substitution. So I think the system reduces to: ```scheme (and (= pos-before new-token-start) ;[1] (< new-token-start new-token-end) ;[5] (= new-token-end pos-after)) ;[4] ``` ---
**Author:** ![robby](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/robby/32/7_2.png) [@robby](https://racket.discourse.group/u/robby)\ **Post date:** [August 12, 2023, 5:46am UTC](https://racket.discourse.group/t/color-lexer-backup-distances-and-dont-stop/2170/9 "2023-08-12T05:46:47Z")
> [@LiberalArtist](#): > > [...] > > So I think the system reduces to: > > ```scheme > (and (= pos-before new-token-start) ;[1] > (< new-token-start new-token-end) ;[5] > (= new-token-end pos-after)) ;[4] > > ``` This logic is compelling to me. I also tried changing the contract and running the tests (and opened up a few big files in DrRacket to see them color properly) and didn't find any counterexamples, so I've [pushed the change to master](https://github.com/racket/syntax-color/commit/025ae973d55fe2f77fa0d5f54f9cb7ce70411917) in the syntax color package. Since a release is imminent, we'll have a good amount of time to see if something pops up before the next release.