"Paragraphs" -> Lines ?

[greghendershott]

Although this is maybe the wrong repo, hopefully that's OK because this is more of a quick question? Depending on answer I can close or move to drracket.

---

Could we:

• Add some methods like beginning-of-line and end-of-line that are position -> position.
• Document that drracket:indentation/drracket:range-indentation functions should use those.
• Document a text-like will not necessarily implement the "paragraph" methods (or if that's too drastic, document that they will always be available... but might be quite slow).

?

Why I ask:

• The "paragraphs" terminology has always been confusing to me. AFAICT in practice this actually means "lines".

• position-paragraph is a performance bottleneck. Effectively it's "give me a line number" -- which is inherently slow -- but AFAICT indenters only need it to give to paragraph-{start end}-position.

• If indenters have a position, they could give that to a {beginning end}-of-line which could efficiently just look backward/forward for a newline. No need to count "paragraph" numbers from the beginning to N, no need to maintain and smartly update some auxiliary data structure to make that less horribly slow.

• Some existing indenters might compare "paragraph numbers", but AFAICT they're really asking "are these two positions within the same line". Instead you could answer that comparing beginning-of-line for two positions.

• I'm thinking of this because in my "like like-text%" so far I've punted on attempting an update of "paragraphs" to be as smart/fast as that for the tokens. Although "dread" is too strong, I have a hunch this will be non-trivial -- probably a lot of effort/bugs vs. giving indenters line methods that directly answer what they want to ask?

[greghendershott]

p.s. I hope that didn't sound cranky/complainy! I don't know the history of this; there are probably good reasons for "paragraphs" terminology. And it makes sense than an editor object would supply line numbers. I'm just looking at indenters and lines and asking if that could be supplied more simply/directly.

[rfindler]

Mainly just commenting on the one bullet:

The "paragraphs" terminology has always been confusing to me. AFAICT in practice this actually means "lines".

I agree that the paragraphs/lines terminology in text% is confusing but if you look at it from the perspective of a WYSIWYG editor (where newlines terminate paragraphs and lines, at least in the GUI, are soft breaks inserted by some algorithm) those are reasonable terms.

I would suggest that, if we move away from the paragraph terminology, we pick a word that isn't "line" so as to avoid confusion with text%.

The rest of this sounds really great!

[greghendershott]

That's a great point about "paragraphs", and soft/visual line breaks vs. hard line breaks.

In the specific case of an identer, AFACIT it's only concerned with hard line breaks; "lines" in the sense of e.g. file->lines and #\newline.

Would it help if the method names were something like {beginning end}-of-hard-line? I don't have any better ideas atm, or strong opinions here.

[greghendershott]

To be clear I don't really care if the new methods have "paragraph" in the name.

So if you prefer (say) position->{start end}-of-paragraph I'd be fine.

The main point for me is the method signature position -> position (as opposed to paragraph-number -> position).

[mfelleisen]

It seems to me that “paragraph” means “visually-separated-block” (of hard and soft lines). A long name (not for @rfindler) but perhaps more intuitive than paragraph.

[greghendershott]

What I propose (though not necessarily the names) is really just this:

...

    ;; Faster alternative to the "paragraphs" methods, for use by indenters.

    (define/public (beginning-of-line pos)
      (define len (string-length str))
      (let loop ([pos pos])
        (cond [(<= pos 0) 0]
              [(<= len pos) (loop (sub1 len))]
              [(char=? #\newline (string-ref str (sub1 pos))) pos]
              [else (loop (sub1 pos))])))

    (define/public (end-of-line pos)
      (define len (string-length str))
      (let loop ([pos pos])
        (cond [(< pos 0) (loop 0)]
              [(<= len pos) (sub1 len)] ;implicit at end
              [(char=? #\newline (string-ref str pos)) pos]
              [else (loop (add1 pos))])))
...

(module+ test
  (let ()
    (define o (test-create "0\n234\n6\n8\n\n"))
    (check-equal? (send o beginning-of-line 0) 0)
    (check-equal? (send o beginning-of-line 1) 0)
    (check-equal? (send o beginning-of-line 2) 2)
    (check-equal? (send o beginning-of-line 3) 2)
    (check-equal? (send o beginning-of-line 4) 2)
    (check-equal? (send o beginning-of-line 5) 2)
    (check-equal? (send o beginning-of-line 6) 6)
    (check-equal? (send o beginning-of-line 7) 6)
    (check-equal? (send o beginning-of-line 8) 8)
    (check-equal? (send o beginning-of-line 9) 8)
    (check-equal? (send o beginning-of-line 10) 10)
    (check-equal? (send o beginning-of-line 11) 10)
    (check-equal? (send o beginning-of-line 1000) 10)
    (check-equal? (send o end-of-line -1) 1)
    (check-equal? (send o end-of-line 0) 1)
    (check-equal? (send o end-of-line 1) 1)
    (check-equal? (send o end-of-line 2) 5)
    (check-equal? (send o end-of-line 3) 5)
    (check-equal? (send o end-of-line 4) 5)
    (check-equal? (send o end-of-line 5) 5)
    (check-equal? (send o end-of-line 6) 7)
    (check-equal? (send o end-of-line 7) 7)
    (check-equal? (send o end-of-line 8) 9)
    (check-equal? (send o end-of-line 9) 9)
    (check-equal? (send o end-of-line 10) 10)
    (check-equal? (send o end-of-line 11) 10)
    (check-equal? (send o end-of-line 1000) 10)))

I'm not sure how to "port" this to an implementation for... I'm not even sure which class it is, editor%? If one of you knows how to do that in New York minute I'd be happy to let you. Otherwise glad to take a crack at it myself. Just tell me the method names please. 😄

[mflatt]

I think the change would be at color:text-mixin to add the methods there (implemented with the existing paragraph methods). They would also be added to color-textoid<%> while removing the three existing paragraph methods. The new synatx-color/racket-indentation function would need to be updated, as you probably already know.

For names, I would go with position-paragraph-start-position and position-paragraph-end-position to stick with the existing text% terminology, but if those are too long, I wouldn't object to different names.

I can make these changes, but I'd prefer to wait until later in the day so we can first deal with any fallout from the changes so far (as discovered by DrDr, for example).

[rfindler]

Any name is good for me, subject to the constraints discussed. I agree that the name isn't the main point and I also agree there appears to be performance benefits to the revised API (not when you are already in a text% object but c'est la vie). Robby

[mflatt]

I started looking at this, and now I'm not so sure. The existing navigation and indentation code could work in terms of line starts, but it's messy in at least once place (where the shrubbery indenter really does want to iterate over lines), and I worry about breaking things in other places. I think it would be a similar amount of work and tidier overall to help make position-paragraph and similar fast in "like like-text%".

[greghendershott]

Thank you for looking at this. I had planned to look at it myself, expecting it would be straightforward for the racket and at-exp indenters. But if I had gotten as far as the shrubbery indenter it sounds like I would have hit that thicket (pun kind of intended) you mention, and if you find it messy, I'd have been really challenged. That sounds discouraging.

I guess my intuition might be unduly influenced by things like text editors, where, AFAIK, people creating indenters historically don't want to rely on line numbers because it could be too slow.

So, for example, if someone wanted to create an indenter for a shrubbery lang for (say) neovim, and couldn't use syntax-color-lib directly or even indirectly via some LSP thing... they would probably be writing Lua code (I believe) to attempt the messy part you mentioned, probably without relying on line numbers. I think??

Even if that's correct, I don't know if that kind of scenario changes your opinion at all.

---

Assuming not: I can look at implementing line numbers with an efficient way to handle the case where I stop re-tokenizing because the new tokens have converged to be the old tokens merely shifted in position. I had started to do that, before pausing to ask "hey is this even really necessary", but I can resume that.

[mflatt]

If I understand, the "like like-text%" class is in charge of representing content, so it can intercept inserts and deletes to update a line map with a suitable data structure — right? I didn't find a suitable data structure immediately among our libraries, but I feel like I probably overlooked one. Meanwhile, I ended up playing with one (adapted from an AVL-tree implement), and I can provide it if that's helpful.

Overall, since at least one indenter needs line numbers, and since it's a general concept that seems likely useful elsewhere, I'm still in favor of having "like like-text%" support it so that there's one implementation.

It's surprising to me that a position<->line number lookup is not generally available in editors, so I can understand where you're starting from, but it doesn't seem like that has to drive our decision here.

[greghendershott]

Maybe position-paragraph doesn't need any special data structure to be updated. Maybe it just needs the content string.

;; A 5,000 line file, about 300,000 chars long
(define content
  (for/fold ([s ""])
            ([n (in-range 5000)])
    (string-append s "\nafd;lkajsdf;lkajsfd;lkajsdf;lakjdsfl;kajsdfadsfasdfasdfasfd")))

(define (position-paragraph pos)
  (define len (string-length content))
  (let loop ([ix 0] [num 0])
    (cond [(or (= ix pos)
               (= ix len))
           num]
          [(char=? (string-ref content ix) #\newline)
           (loop (add1 ix) (add1 num))]
          [else
           (loop (add1 ix) num)])))

(time (position-paragraph 4000))
;; cpu time: 0 real time: 0 gc time: 0
;; 67

(time (position-paragraph 30000))
;; cpu time: 0 real time: 0 gc time: 0
;; 500

(time (position-paragraph (sub1 (string-length content))))
;; cpu time: 2 real time: 2 gc time: 0
;; 5000

The second example is a style guide size file and the third is something like class-internal.rkt.

And then paragraph-{start end}-position can be the simple search backward/forward for a newline; effectively the {beginning end}-of-line I sketched out before.

[rfindler]

Just because I was curious, I adapted the code above to use racket:text% and upped the counts a bit and it seems that the text object does pretty well on this benchmark. So even if we discover a need for a better setup later on for this method, we'll probably be able to do it without changing the APIs.

#lang racket
(require framework)
;; A 5,000 line file, about 300,000 chars long
(define content
  (for/fold ([s ""])
            ([n (in-range 5000)])
    (string-append s "\nafd;lkajsdf;lkajsfd;lkajsdf;lakjdsfl;kajsdfadsfasdfasdfasfd")))

(define t (new racket:text%))
(send t insert content)
(send t freeze-colorer)
(send t thaw-colorer)

(define (position-paragraph.txt pos)
  (send t position-paragraph pos))

(define (position-paragraph.str pos)
  (define len (string-length content))
  (let loop ([ix 0] [num 0])
    (cond [(or (= ix pos)
               (= ix len))
           num]
          [(char=? (string-ref content ix) #\newline)
           (loop (add1 ix) (add1 num))]
          [else
           (loop (add1 ix) num)])))

(collect-garbage) (collect-garbage) (collect-garbage)

(define COUNT 1000)

(time (for ([x (in-range COUNT)]) (position-paragraph.str 4000)))
(time (for ([x (in-range COUNT)]) (position-paragraph.txt 4000)))
;; cpu time: 15 real time: 15 gc time: 0
;; cpu time: 0 real time: 0 gc time: 0

(time (for ([x (in-range COUNT)]) (position-paragraph.str 30000)))
(time (for ([x (in-range COUNT)]) (position-paragraph.txt 30000)))
;; cpu time: 96 real time: 96 gc time: 0
;; cpu time: 0 real time: 0 gc time: 0

(time (for ([x (in-range COUNT)]) (position-paragraph.str (sub1 (string-length content)))))
(time (for ([x (in-range COUNT)]) (position-paragraph.txt (sub1 (string-length content)))))
;; cpu time: 951 real time: 952 gc time: 0
;; cpu time: 0 real time: 0 gc time: 0