3 ms·

All the containers store the metrics (line endings, unicode codepoints, UTF-16 codepoints, etc) in a tree. The tree stores the value of all it's children summed

All the containers store the metrics (line endings, unicode codepoints, UTF-16 codepoints, etc) in a tree. The tree stores the value of all it's children summed up. So if if you do an insert at the start you only need to update a single branch. When calculating the line count you have to walk down the tree summing all the children as you go. But this means updating and lookup are both logn instead of having to update N nodes. These benchmarks include that time.

ahefner 3y ago
A neat trick with gap buffers is you can track the line boundaries as indices into the gap buffer itself rather than 'real' indices into the document. In this way the indices of line starts seldom change except when the gap buffer is resized. You can then keep a second gap buffer, this one recording the start of line indices, and keep its gap in sync with cursor movement in the text gap buffer, making insertion cheap and giving a trivial way to map from line numbers to a position in the gap buffer. No trees necessary.
- celeritascelery 3y ago
  hmm. What happens when you move the gap from the front to the end of the text (or vice versa)? wouldn't that require you to update all the line boundaries? And wouldn't finding the position of the Nth line be O(n).
  - ahefner 3y ago
    Moving the gap from front to end - it takes O(n) time to do that both on the text (gap) buffer and the line-tracking (gap) buffer, so you're only a small constant factor worse. Find the position of the Nth line is O(1) because N is either before the gap, in which case you just look up the Nth entry in the line-tracking buffer to get the position in the text buffer (which can be similarly mapped back to a position not including the gap in constant time if that's what you need), or N after the gap and you adjust the arithmetic to include the size of the gap.
    - celeritascelery 3y ago
      This does seem like a really neat trick I have not heard of before. I am still confused about moving the gap in the line-tracking buffer. It seems to me the only way you could make look-up O(1) is if you updated all the line indexes you passed over when you moved the gap. Because they are pointing to absolute positions (right?). So moving the line-tracking gap would technically be O(n), but you couldn't use memmove, and instead would need to iterate over one and add or subtract the gap size. Am I misunderstanding?
      - ahefner 3y ago
        The contents of the line-tracking buffer (ignoring its gap for a moment, which you could move anywhere) only change when the text-buffer's gap moves. When that happens, each time a line break moves across the gap, you need to update its index in the line tracking buffer. It doesn't directly matter where the gap is in the line-tracking buffer except ideally it's positioned consistent with the user's cursor so that if they insert a bunch of new lines, they're inserted into the line-tracking gap. The position of the line-tracking gap doesn't effect the values stored on either side of it gap, so you can still use memmove there.
      - teo_zero 3y ago
        The trick is to decouple the concept of 'position' in the text, that is independent of the gap, from 'pointer' into the buffer. If you keep track of line beginnings as positions, you can immediately get the pointers: ptr = pos if pos<=gapstart else pos + gapsize
        teo_zero 3y ago
        Replying to myself: it's actually a bad idea because you have to update all indices at each inserted char! Forget about it...
scotty79 3y ago
Could you describe your implementation of this tree in more detail in the repo? I think it's really interesting part of your project.
- celeritascelery 3y ago
  It is actually not very novel. It is just a Fenwick tree[1]. And a Fenwick tree is basically a rope where the leafs don't store any text. basically every leaf holds some metrics (say bytes and line endings) for some chunk of text. By just looking at the leaf we don't know which chunk it points to. But since the leafs are all in order, we can calculate their byte position and line ending by adding them up. If we add all the leaf we should get the total number of bytes and lines in the text. In order to avoid O(n) cost of summing every leaf, we store them in a tree, where each parent holds the sums of it's children. So when we want to find the byte position[2] of a particular line ending we can just walk down the tree and see if the line ending we are searching for is greater then the left child or not. If it is, we add the left child's sum to our running total and go to the right. Otherwise we go to the left. By the time we get to the leaf, we have summed all the chunks before it in O(logn) time. Insertion/deletion are similar, except when we update the leaf, we also go and update each parent on the way back up. [1] https://www.baeldung.com/cs/fenwick-tree https://www.baeldung.com/cs/fenwick-tree [2] https://github.com/CeleritasCelery/rune/blob/be243ea2bd385ec2ed8aab32fa6f0b70114c892f/crates/text-buffer/src/metric.rs#L858 https://github.com/CeleritasCelery/rune/blob/be243ea2bd385ec...

ahefner 3y ago

A neat trick with gap buffers is you can track the line boundaries as indices into the gap buffer itself rather than 'real' indices into the document. In this way the indices of line starts seldom change except when the gap buffer is resized. You can then keep a second gap buffer, this one recording the start of line indices, and keep its gap in sync with cursor movement in the text gap buffer, making insertion cheap and giving a trivial way to map from line numbers to a position in the gap buffer. No trees necessary.

celeritascelery 3y ago
hmm. What happens when you move the gap from the front to the end of the text (or vice versa)? wouldn't that require you to update all the line boundaries? And wouldn't finding the position of the Nth line be O(n).
- ahefner 3y ago
  Moving the gap from front to end - it takes O(n) time to do that both on the text (gap) buffer and the line-tracking (gap) buffer, so you're only a small constant factor worse. Find the position of the Nth line is O(1) because N is either before the gap, in which case you just look up the Nth entry in the line-tracking buffer to get the position in the text buffer (which can be similarly mapped back to a position not including the gap in constant time if that's what you need), or N after the gap and you adjust the arithmetic to include the size of the gap.
  - celeritascelery 3y ago
    This does seem like a really neat trick I have not heard of before. I am still confused about moving the gap in the line-tracking buffer. It seems to me the only way you could make look-up O(1) is if you updated all the line indexes you passed over when you moved the gap. Because they are pointing to absolute positions (right?). So moving the line-tracking gap would technically be O(n), but you couldn't use memmove, and instead would need to iterate over one and add or subtract the gap size. Am I misunderstanding?
    - ahefner 3y ago
      The contents of the line-tracking buffer (ignoring its gap for a moment, which you could move anywhere) only change when the text-buffer's gap moves. When that happens, each time a line break moves across the gap, you need to update its index in the line tracking buffer. It doesn't directly matter where the gap is in the line-tracking buffer except ideally it's positioned consistent with the user's cursor so that if they insert a bunch of new lines, they're inserted into the line-tracking gap. The position of the line-tracking gap doesn't effect the values stored on either side of it gap, so you can still use memmove there.
    - teo_zero 3y ago
      The trick is to decouple the concept of 'position' in the text, that is independent of the gap, from 'pointer' into the buffer. If you keep track of line beginnings as positions, you can immediately get the pointers: ptr = pos if pos<=gapstart else pos + gapsize
      - teo_zero 3y ago
        Replying to myself: it's actually a bad idea because you have to update all indices at each inserted char! Forget about it...

scotty79 3y ago

Could you describe your implementation of this tree in more detail in the repo? I think it's really interesting part of your project.

celeritascelery 3y ago
It is actually not very novel. It is just a Fenwick tree[1]. And a Fenwick tree is basically a rope where the leafs don't store any text. basically every leaf holds some metrics (say bytes and line endings) for some chunk of text. By just looking at the leaf we don't know which chunk it points to. But since the leafs are all in order, we can calculate their byte position and line ending by adding them up. If we add all the leaf we should get the total number of bytes and lines in the text. In order to avoid O(n) cost of summing every leaf, we store them in a tree, where each parent holds the sums of it's children. So when we want to find the byte position[2] of a particular line ending we can just walk down the tree and see if the line ending we are searching for is greater then the left child or not. If it is, we add the left child's sum to our running total and go to the right. Otherwise we go to the left. By the time we get to the leaf, we have summed all the chunks before it in O(logn) time. Insertion/deletion are similar, except when we update the leaf, we also go and update each parent on the way back up. [1] https://www.baeldung.com/cs/fenwick-tree https://www.baeldung.com/cs/fenwick-tree [2] https://github.com/CeleritasCelery/rune/blob/be243ea2bd385ec2ed8aab32fa6f0b70114c892f/crates/text-buffer/src/metric.rs#L858 https://github.com/CeleritasCelery/rune/blob/be243ea2bd385ec...