Krope — High-Performance Rope-Based Text Buffer for Kotlin Multiplatform

Krope is a Kotlin Multiplatform library providing an immutable, persistent text buffer backed by a Rope data structure. It's designed for applications that require efficient, memory-safe text manipulation on large strings — ideal for collaborative editors, code editors, IDEs, and reactive text processing pipelines.

---

Why Rope?

Unlike String or StringBuilder, a rope represents text as a balanced binary tree of character chunks. This offers significant benefits for editing large documents:

• O (log N) complexity for inserts, deletes, and substring extraction (vs. O (N) for flat strings)
• Structural sharing — editing returns a new tree without copying unchanged portions, reducing memory allocation
• Cached metadata at each node for O (1) access to total characters, bytes, lines, and maximum line length
• Automatic rebalancing using a red-black tree variant to maintain performance over thousands of edits

---

Features

• 📝 Efficient text editing — Insert, delete, replace, and batch operations in logarithmic time
• 📊 Line-aware indexing — Resolve line/column positions to character offsets and vice versa
• 🧵 Multi-encoding support — UTF-8, UTF-16 LE/BE, UTF-32 LE/BE with accurate byte offset calculations
• ⚡ Batch operations — Group multiple edits into a single structural update using withBatch for atomic, optimized mutations
• 🔄 Reactive & observable — Coroutine-based SharedFlow emits TextEdit.Data events on every change; immutable StateFlow snapshots provide consistent reads
• 🧠 Memory pooling — Optional string interning and node caching reduce heap pressure under repetitive edits
• 🌍 Cross-platform — Targets JVM, Android, iOS (x64, arm64, simulator), and WASM (browser) via Kotlin Multiplatform
• 📐 Line ending normalization — Automatically converts \r\n and \r to \n internally, restores on snapshot access

---

Architecture

library/
├── core/       → Rope data structure, node types, encoding, LRU caches, SoftReference
├── text/       → TextBuffer interface, RopeTextBuffer, TextPosition, TextRange, TextEdit
├── io/         → Serialization-ready module (kotlinx.serialization)
└── diff/       → Placeholder for future diff/comparison algorithms

Core Rope

The Rope class implements the full rope interface: insert, delete, split, concatenate, rebalance, and batch apply. It maintains internal caches for line offsets, byte offsets, and full-text retrieval. Metadata (byte count, line breaks, max line length) is aggregated efficiently at each node.

Text Buffer (TextBuffer)

The public API surface for end users. It wraps a Rope with a coroutine-safe mutex, a StateFlow<TextSnapshot> for querying current state, and a SharedFlow<TextEdit.Data> for observing edits.

Operations:

• insert(position, text)
• replace(range, text)
• delete(range)
• withBatch { ... }
• changeEncoding(encoding)
• changeLineEnding(lineEnding)

Text Snapshot

TextSnapshot provides consistent access to:

• Total lines, characters, bytes
• Maximum line length
• Line-by-line text and length
• Substring extraction by TextRange
• Conversion between line/column positions, character offsets, and byte offsets

Text Edit Data

Every mutation produces a TextEdit.Data subtype:

• Single.Insert — text inserted at a position
• Single.Delete — text removed from a range
• Single.Replace — text replaced in a range
• Batch — multiple singles grouped atomically

---

Example Usage

import io.github.numq.krope.core.Encoding
import io.github.numq.krope.text.*

// 1. Create buffer
val factory = RopeTextBufferFactory()
val buffer = factory.create(
    text = "Hello World",
    encoding = Encoding.UTF8,
    lineEnding = TextLineEnding.LF,
    enablePooling = true
).fold(
    onSuccess = { it },
    onFailure = { error -> /* handle error */ }
)

// 2. Observe edits
launch {
    buffer.data.collect { editData ->
        when (editData) {
            is TextEdit.Data.Single.Insert -> println("Inserted at ${editData.startPosition}")

            is TextEdit.Data.Single.Delete -> println("Deleted from ${editData.startPosition}")

            is TextEdit.Data.Single.Replace -> println("Replaced '${editData.oldText}' with '${editData.newText}'")

            is TextEdit.Data.Batch -> println("Batch of ${editData.singles.size} edits")
        }
    }
}

// 3. Read current snapshot
val snapshot = buffer.snapshot.value
println(snapshot.text) // "Hello World"
println(snapshot.lines) // 1
println(snapshot.maxLineLength) // 11

// 4. Edit
buffer.insert(TextPosition(0, 5), " Beautiful") // "Hello Beautiful World"
buffer.replace(TextRange(TextPosition(0, 6), TextPosition(0, 15)), "Wonderful") // "Hello Wonderful World"
buffer.delete(TextRange(TextPosition(0, 5), TextPosition(0, 16))) // "Hello World"

// 5. Batch edits
buffer.withBatch { batch ->
    batch.replace(TextRange(TextPosition(0, 0), TextPosition(0, 5)), "Hi")
    batch.insert(TextPosition(0, 2), "!")
} // "Hi! World"

// 6. Byte offsets (useful for interop with native file I/O)
val bytePos = snapshot.getBytePosition(TextPosition(0, 6)) // 6 (UTF-8)

For a full simulation of a collaborative editor with reactive events and batch refactoring, see example/src/commonMain/kotlin/io/github/numq/krope/example/EditorSimulation.kt.

---

Benchmark

How does Krope perform on large files compared to flat structures?

We ran JMH benchmarks on the JVM comparing pure data structure mutations across documents ranging from 100K to 100M characters.

Single Middle Insert (O (log N) vs O (N))

Document Size (chars)	Krope	StringBuilder	Krope Advantage
100,000	7.71 µs	8.93 µs	~1.2x faster
1,000,000	7.56 µs	109.66 µs	~14.5x faster
10,000,000	7.87 µs	1,305.68 µs (~1.31 ms)	~165x faster
100,000,000	8.28 µs	16,741.23 µs (~16.74 ms)	~2,020x faster

100 Consecutive Edits (Editing Session)

Document Size (chars)	Krope	StringBuilder	Krope Advantage
100,000	42.11 µs	164.21 µs	~3.9x faster
1,000,000	44.43 µs	1,662.33 µs (~1.66 ms)	~37x faster
10,000,000	119.66 µs (~0.12 ms)	17,205.79 µs (~17.21 ms)	~144x faster
100,000,000	424.18 µs (~0.42 ms)	177,660.85 µs (~177.66 ms)	~419x faster

Viewport Substring Read (1,000 characters)

Document Size (chars)	Krope (Viewport Read)	StringBuilder (Substring)
100,000	0.24 µs (~240 ns)	0.07 µs
1,000,000	0.25 µs (~250 ns)	0.07 µs
10,000,000	0.25 µs (~250 ns)	0.07 µs
100,000,000	0.26 µs (~260 ns)	0.08 µs

Why the massive difference?
StringBuilder requires copying megabytes of contiguous memory on every mutation ($O (N)$), leading to GC spikes and severe UI lag.
Krope performs non-destructive tree splits and pointer rotations ($O (\log N)$), keeping single edits under 10 microseconds and viewport extraction at ~250 nanoseconds even on a 100 MB document.

Krope uses a Red-Black tree and structural sharing. It simply splits a small leaf node and updates a few pointers up to the root ($O (\log N)$). Krope maintains incredibly flat, predictable latency regardless of file size, keeping your UI perfectly smooth while drastically reducing heap allocations.

Source

Supported Platforms

Platform	Status
JVM (17+)	✅
Android (API 24+)	✅
iOS (x64, arm64, simulator)	✅
WASM (browser)	✅

---

Dependencies

• kotlinx.atomicfu — for lock-free atomic state (internal)
• kotlinx.coroutines — for StateFlow, SharedFlow, and mutex-based synchronization
• kotlinx.serialization — for the io module's serialization support

---

Gradle Installation

The project is hosted on Maven Central. Make sure your project repositories include it:

repositories {
    mavenCentral()
}

Add the desired module to your build.gradle.kts dependencies block:

dependencies {
    // Core rope data structure
    implementation("io.github.numq.krope:core:1.1.0")

    // Full TextBuffer API (depends on core)
    implementation("io.github.numq.krope:text:1.1.0")
}

---

License

Apache-2.0 License - see LICENSE file for details.

---

Support Development: numq.github.io/support