Feature: accessing and slicing Ropes by byte offset and grapheme cluster offset.

[phronmophobic]

I'm working on a code editor that uses tree-sitter for syntax highlighting and supporting text like "👻👩‍👩‍👦‍👦" is a design goal.

Tree sitter's API references all text snippets by their byte offsets. For example, if tree sitter parses the clojure code (declare foo), it will tell you there's a list literal starting at byte offset 0, a symbol declare at byte offset 1, and a symbol foo at byte offset 9. To construct a view of the syntax highlighted text, I then need to grab chunks of text by their byte offsets.

On the UI side, the cursor needs to move forward and backwards by grapheme cluster. As an example, 👩‍👩‍👦‍👦is 1 grapheme cluster or 25 utf-8 bytes or 7 code points or 11 java characters. It's really convenient that Bifurcan's Ropes already deals with the discrepancy between code points and java characters 😄.

I'm not sure if there's interest in extending Bifurcan's Rope book keeping to also support lookup by byte offset and/or grapheme cluster offset.

Thanks for the great library!

[ztellman]

Hi, I had also intended Rope for my own little IDE project, so I'm glad someone's getting use out of it. My plan for grapheme clusters was to add an iterator, but not random access lookups (it would add a lot of bookkeeping for a fairly niche use case). Random access lookups on the UTF-8 bytes, however, seem like a pretty reasonable feature request.

I've been meaning to cut an 0.2.0 release in the next month or so. If you want to take a stab at a PR before then, feel free, otherwise it's 50/50 that I'll have the time and energy myself.

[phronmophobic]

Awesome! I've made quite a bit of progress on my code editor and hope to have an initial release soon. I'm still figuring what features are important. Here are some thoughts so far:

Indexing

I've assembled a few libraries to build the text editor and they each keep track of offsets in different ways:

Bifurcan Rope: code points
tree-sitter (syntax highlighting, code navigation): bytes
icu4j BreakIterator (grapheme clusters): code units
java String and Regex: code units
Skia (text rendering): code units
text editing (my library): grapheme clusters, lines, rows, columns

I know Rope does a lot of work to make indexing by codepoint first class, but I haven't found that feature useful. I've implemented slicing by byte index on my own fork (this implementation probably isn't ready to be included in Bifurcan, but I can clean it up if you're interested). You can do some indexing by code unit by using Rope's .toCharSequence. I may also implement slicing by code unit index. I think it would also be convenient to track line offsets in Rope. A lot of the code in the editor is just keeping track of the offsets by byte, code unit, code point, row, column, and grapheme cluster. Being able to translate between coordinates with Rope would be really helpful.

Tracking grapheme clusters may be useful, but isn't required

As I've gotten a little farther along, keeping track of grapheme cluster offsets hasn't been required. As far as I can tell, the best way to iterate over grapheme clusters is icu4j's com.ibm.icu.text.BreakIterator. You can iterate forward and backwards by passing Rope's CharSequence to the BreakIterator:

(let [rope my-rope
      cs (.toCharSequence rope)
      bi (doto (BreakIterator/getCharacterInstance)
           (.setText cs))

      next-codeunit-index (.following bi cursor-codeunit-index)])

The java sdk also has a BreakIterator that can iterate over grapheme clusters, but it currently needs to analyze the full string to do any iteration which is really slow for text editing.

---

tldr: After I publish my text editing library, I'll make a summary of changes that I made to Rope to see which changes you might be interested in.

[phronmophobic]

I've implemented some Rope operations that accept byte indexes, Rope/sliceBytes and Rope/insertAtByte. I also changed the Rope class to implement CharSequence which is a backwards incompatible change due to the existing implementations of chars and codePoints. It really simplifies my usage of Rope to be able to treat it as a CharSequence.

It would be helpful to know if you would be interested in these kinds of changes. If so, I'm happy to work on a more comprehensive PR. Otherwise, I'll move the changes you're not interested in to a fork.

If you want to see Rope in action, you can see it at https://www.youtube.com/watch?v=kRd4JYIiWb0 and https://github.com/phronmophobic/clobber.

Thanks!