Denebola

Persistent summary B+ trees and Unicode text ropes in pure Ruby

Features · Installation · Quick Start · Text Rope · Sparse Sheet · Summary Tree · Benchmarks

Denebola is a library for immutable, structurally shared data. It provides a generic summary B+ tree, a Unicode-aware text rope, bounded-memory file editing, and sparse two-dimensional sheets. Every edit returns a new value while reusing untouched subtrees, so retaining a snapshot is an ordinary assignment.

• Persistent text editing with structural sharing
• Persistent sparse 2D sheets with range summaries and batched cell updates
• Bounded-memory, file-backed editing for multi-gigabyte text
• UTF-8 byte, Unicode codepoint, UTF-16, and line-based indexing
• Batched edits and explicit anchor transformation
• LF, CRLF, CR, U+2028, and U+2029 line break support
• Generic summary B+ tree with dimension-based cursors
• Pure Ruby 3.1+ with no runtime dependencies
• RBS signatures for the public API

Add Denebola to your Gemfile:

gem "denebola"

Then install:

bundle install

Or install it directly:

gem install denebola

• Ruby 3.1 or later

require "denebola"

rope = Denebola::Rope.new("hello\nworld")
snapshot = rope
rope = rope.insert(5, ", there")

rope.line(0)  # => "hello, there"
rope.to_s     # => "hello, there\nworld"
snapshot.to_s # => "hello\nworld"

For files that should not be copied into memory, open a LazyRope:

text = Denebola::LazyRope.open("server.log")
text.line(1_000_000)                 # indexes only as far as needed
text.line_count                      # estimate until the index reaches EOF
text.line_count(exact: true)         # force an exact count
text.edit(0...5, "INFO:")           # untouched bytes remain file-backed
text.materialize(0...1024)           # an ordinary editable Rope
text.close

LazyRope reads 1 MiB chunks by default and keeps eight chunks in an LRU cache. byteslice, line access, byte/codepoint positions, UTF-16 positions, and anchors follow Rope semantics. edit, insert, delete, and replace mutate the open view; apply_edits returns a persistent view while storing only replacement text in memory. Views in that snapshot family share one backing-file lifetime, so closing any view closes the family. Call materialize for an independent Rope snapshot. A file changed, removed, or replaced after opening raises Denebola::Error. to_s and materialize without a range intentionally load the complete logical file.

rope = Denebola::Rope.new("hello\nworld")

rope.bytesize                         # => 11
rope.length                           # => 11 Unicode codepoints
rope.line_count                       # => 2
rope.byteslice(0, 5).to_s             # => "hello"
rope.delete(0...5).to_s               # => "\nworld"
rope.replace(0...5, "Hi").to_s       # => "Hi\nworld"
rope.each_chunk { |text| puts text }  # Frozen strings, without flattening

rope.apply_edits([[0...5, "Hi"], [6...11, "Ruby"]]).to_s
# => "Hi\nRuby"

Ranges passed to replace, apply_edits, and byteslice address bytes in UTF-8. Bounds and codepoint boundaries are checked. Inclusive, exclusive, beginless, and endless Ruby ranges are accepted; invalid encodings, split codepoints, and overlapping batch edits raise exceptions.

apply_edits applies nonoverlapping edits against one original snapshot, and Anchor#transform uses the same source order. Adjacent ranges are allowed; zero-length insertions at the same offset keep input order and precede a replacement beginning there. Input strings are copied or shared safely with Ruby's copy-on-write strings, so later mutation of the source cannot alter a rope.

Chunks preserve extended grapheme clusters when building or joining text. A single unusually long grapheme may exceed the configured chunk size; explicit byte slices and edits may operate between codepoints inside a grapheme.

rope = Denebola::Rope.new("😀\n日本")

rope.point_at(8)                              # => Point(row: 1, column: 1)
rope.offset_at(Denebola::Point.new(1, 1))     # => 8
rope.line_start(1)                            # => 5
rope.utf16_offset_at(8)                       # => 4
rope.offset_at_utf16(4)                       # => 8
rope.utf16_point_at(4)                        # => Point(row: 0, column: 2)
rope.offset_at_utf16_point(Denebola::Point.new(0, 2)) # => 4

Point accepts positional or keyword row and column. Unqualified offsets are UTF-8 byte offsets. Normal columns count Unicode codepoints, not screen cells or graphemes. UTF-16 methods count code units and reject offsets inside a surrogate pair. offset_at and offset_at_utf16_point require a column within the line's content.

line(row) omits the terminator. Rows are zero-based; empty text and a final empty row after a terminator each count as a line. A byte position between CR and LF normalizes to the following row, column zero; converting that point back returns the position after LF.

The optional adapter exposes a persistent Rope through Zaniah's line-addressed CodeEditor buffer interface. Denebola does not depend on Zaniah:

require "denebola/code_editor_buffer"
require "zaniah/ui"

buffer = Denebola::CodeEditorBuffer.new(Denebola::Rope.new("hello\nworld"))
editor = Zaniah::UI::CodeEditor.new(buffer: buffer)

line_count, line, line_start, and line_of use Rope indexes; offsets are UTF-8 byte positions. replace, undo, and redo keep structurally shared snapshots, and can_undo?/can_redo? control editor actions. to_s materializes the full document when CodeEditor requests its value. LazyRope is not accepted: its default line count is an estimate, whereas CodeEditor needs an exact count.

rope.summary exposes bytesize, length, utf16_length, break_count, longest_row (the earliest row with maximum width), longest_row_length, first_line_length, and last_line_length. TextSummary.zero is the identity, and summary + other_summary combines concatenated text, including CRLF across a boundary.

Anchors transform explicitly using the same finite byte ranges as an edit, without retaining the edit history:

rope = Denebola::Rope.new("hello")
anchor = rope.anchor(2, bias: :right)
edits = [[2...2, "XYZ"]]

anchor = anchor.transform(edits)
rope = rope.apply_edits(edits)

anchor.offset # => 5

:left keeps an anchor before text inserted at its position; :right keeps it after. Anchors covered by a replacement collapse to the corresponding side of the replacement. Offsets after an edit move by its byte-length delta. Transformation returns a new anchor; it does not mutate the original or automatically observe a rope.

Sheet stores only populated cells in persistent B+ trees. Empty row and column runs are represented by gaps, so the primary storage can split and join axis ranges without shifting cell nodes. Structural edits currently rebuild the derived 2D summary index from populated cells. Every update returns a new snapshot; snapshot returns the same immutable value in O(1).

sheet = Denebola::Sheet.new
sheet = sheet.set(0, 0, 12).set(4, 2, 30)
previous = sheet.snapshot

sheet[4, 2]                                  # => 30
sheet.summary(0, 0, 4, 2).sum               # => 42
sheet.each_in(0, 0, 4, 2).to_a              # => [[Denebola::Point.new(0, 0), 12], [Denebola::Point.new(4, 2), 30]]
sheet = sheet.insert_rows(2, 1).delete(0, 0)
previous[0, 0]                               # => 12

sheet = Denebola::Sheet.new.set_many([[0, 0, 12], [0, 1, 8], [1_000_000, 3, "far"]])
sheet[1_000_000, 3]                          # => "far"

Coordinates are zero-based, and each_in/summary use inclusive bounds. row_count and column_count describe the current grid extent: setting a distant cell and inserting an axis extend it, clearing a cell preserves it, and deleting rows or columns shrinks it. set(row, column, nil) is equivalent to delete. Strings are copied and frozen; other values should be immutable to preserve snapshots. summary counts populated cells, sums Numeric values, reports comparable Numeric minimum/maximum, and counts values by Ruby class in types.

each_in yields (Denebola::Point, value), so it can directly back a cell-source callback that accepts (reference, value).

set_many accepts an enumerable of [row, column, value] edits, uses the last edit for duplicate coordinates, and returns one persistent snapshot. It bulk-builds the row tree after sorting the batch, avoiding a row-tree path rebuild for every cell; multi-column sheets also update the derived range index, while single-column sheets need no index. Untouched row objects and older snapshots remain reusable. Use set for isolated edits.

Whole-row summaries use the outer row-tree summary without visiting rows or cells. Arbitrary rectangles use a persistent 2D range index: a partial-column query visits O(log rows × log columns) summary nodes and does not enumerate rows or cells. Single-column sheets need no 2D index because every valid column range is the full width. Wider sheets maintain the index, building it when first widened from one column; point edits copy affected paths, and maintaining exact numeric extrema after deletion adds a logarithmic value-index update. Structural row/column insertion and deletion still rebuild this auxiliary index from populated cells, even though the primary sheet trees retain sparse gaps.

Items expose summary. The summary class supplies .zero and #+, with associative addition and an identity. Items and their summaries must be immutable. A dimension is a summary attribute name, a callable, or an object with from_summary(summary); its projection must be monotone along the sequence.

Weight = Struct.new(:weight) do
  def self.zero = new(0).freeze
  def +(other) = self.class.new(weight + other.weight).freeze
  def summary = self
end

tree = Denebola::Tree.new(
  [Weight.new(2).freeze, Weight.new(3).freeze],
  summary: Weight
)
tree = tree.push(Weight.new(5).freeze)
cursor = tree.cursor(:weight).seek(2)

cursor.item.weight          # => 3
cursor.summary.weight       # => 2, the summary before the current item
cursor.next.weight          # => 5
cursor.prev.weight          # => 3
cursor.seek(2, bias: :left).item.weight # => 2

Tree.from(items, summary: ...) and Tree.new(items, summary: ...) bulk-build an ordered sequence. append joins another compatible tree or enumerable. tree[index], slice(index, count), and split_at(index) use item indexes. replace_at(index, items) replaces one item, or appends when index == size. Every update returns a new tree.

cursor.seek(value) chooses the item whose ending dimension exceeds the target; bias: :left also includes equality. At the end, item is nil, index == tree.size, and summary is the whole summary. cursor.read_until(value) returns complete items up to the target boundary and advances the cursor; it does not split an item. next and prev return the newly selected item or nil.

Text dimensions are available as Denebola::Dimensions::BYTES, CHARACTERS, UTF16, and LINE_BREAKS. B+ nodes hold cumulative summaries and item counts; navigation uses binary search. Editing copies touched chunks and ancestor paths, while splitting and joining preserve occupancy and equal leaf depth. Returning a string or a long line necessarily costs at least its output size.

check_invariants! checks occupancy, frozen nodes, depth, prefix counts, and summaries. It is intended for tests.

bundle exec rake bench

The sheet benchmark builds a sparse grid and reports build, snapshot, full-row summary, and partial-column summary times. bench/sheet_range_index.rb measures partial-column query scaling across sparse rows:

bundle exec ruby -Ilib bench/sheet_range_index.rb

Measured 2026-09-23 on arm64 macOS, Ruby 4.0.6 without YJIT: batches of 2,000 / 10,000 / 40,000 populated cells (1,000 / 5,000 / 20,000 occupied rows) built in 0.283 / 1.762 / 9.162 s. A one-column summary took 72.69 / 66.33 / 154.42 µs over 500 queries per size. Query time grows with tree depth rather than linearly with selected rows. This workload also shows the 2D index's material build/update cost; million-cell workloads have not yet been remeasured with the index enabled.

The benchmark compares fanouts 8/16/32/64 and chunk sizes 256/512/1024/2048 before exercising a 1,000,000-line ASCII document (11,000,000 bytes). Timings are five-batch medians after warmup. The defaults are fanout 16 and chunk size 1024 bytes: smaller chunks improve some edits but allocate more nodes, while these defaults meet the edit and retained-memory budgets together. Override them with Rope.new(text, branching: 8, chunk_size: 512).

Measured 2026-09-09 on arm64 macOS, Ruby 4.0.2 with YJIT:

Performance depends on document content, Ruby version, and hardware. Memory is measured with ObjectSpace after releasing the input and collecting garbage; it is not process RSS. rake bench:assert uses wider timing ceilings for shared CI hardware while retaining the 40 MiB memory ceiling.

bundle install
bundle exec rake test

The default suite includes 100,000 deterministic random Unicode edits compared with Ruby String, 5,000 summary monoid cases, immutable snapshots, split/join occupancy checks, all supported newline types, surrogate boundaries, and retained node counts after 10,000 edits. bundle exec rake test:oracle runs the property tests alone, and ruby tools/check_isolation.rb checks runtime independence.

CI tests Ruby 3.1, 3.2, 3.3, 3.4, and 4.0 on Linux, macOS, and Windows. See the RBS signatures for the public API and the changelog for release history.

Bug reports and pull requests are welcome at https://github.com/noxdea/denebola.

Released under the MIT License.