简体中文

Knot

A Kotlin/JVM rope library for editable text and sequences with reverse position lookup.

Knot grew out of a DSL language server that needed to keep syntax objects associated with changing line numbers. It now provides two structures backed by a metric-aware Treap:

• IndexedRope<E : Any>: a mutable list with direct element access and identity-based position lookup.
• CharRope: an editable CharSequence with character and line-start lookup.

When to use it

Inserting into the middle of an array-backed list or string buffer requires moving the remaining elements. Caching an object's index also requires updating later indices after an edit. A rope stores the sequence in a tree, so edits and position queries can follow tree paths instead.

This is useful for document editing, incremental analysis, and source indexing. For small collections or workloads dominated by sequential access, standard collections may be simpler and faster. There is no fixed document size at which a rope always wins.

IndexedRope

import moe.smileslime47.knot.rope.index.IndexedRope

class Entry(val text: String)

fun main() {
    val first = Entry("first")
    val second = Entry("second")
    val rope = IndexedRope<Entry>()
    rope.addAll(listOf(first, second))

    check(rope[1] === second)
    check(rope.indexOf(second) == 1)

    val view = rope.subList(1, 2)
    val inserted = Entry("inserted")
    view.add(0, inserted)
    check(rope.indexOf(second) == 2)

    view.clear()
    check(rope.size == 1)
    check(rope.indexOf(second) == -1)
}

Element and view semantics

• Elements are non-null and accessed directly through MutableList<E>. Position tracking stays in an internal identity map; no reference wrapper or base class is required.
• indexOf matches by object identity (===), not value equality. The same instance cannot appear twice in one rope; distinct instances with equal values are allowed. This is a deliberate difference from standard list indexOf semantics.
• Removing or replacing an element removes its old position mapping. Setting a slot to the same instance is a no-op.
• Both addAll overloads validate the batch for existing and duplicate references before insertion.
• subList(fromIndex, toIndex) returns a mutable backed view over a half-open range. Edits through a view update the rope and its ancestor views.
• Structural edits outside a view invalidate it, including edits through a sibling view. Access to an invalidated view throws ConcurrentModificationException.
• Iterators detect external structural edits. Iterator removal updates the tree and position map together. set is non-structural and does not invalidate views or iterators.

All positions are zero-based. These mutable structures are not thread-safe; modification detection does not provide synchronization.

CharRope

import moe.smileslime47.knot.rope.text.CharRope

fun main() {
    val text = CharRope().append("hello\nworld")
    text.insert(6, "Kotlin ")

    check(text.lineCount == 2)
    check(text.getLineStart(1) == 6)
    check(text.subSequence(6, 12).toString() == "Kotlin")

    text.delete(6, 13)
    check(text.toString() == "hello\nworld")
}

append, insert, and delete mutate the rope and return it for chaining. Deletion and subsequence ranges exclude the end position. subSequence produces a string snapshot, not a mutable view.

Character positions use Kotlin/JVM Char indices (UTF-16 code units). Lines are counted using \n: an empty rope has one line, and a trailing newline creates an additional empty line. getLineStart accepts a zero-based line index and returns a character offset.

Structure and complexity

Tree<E, M> and TreeMetric<E, M> separate tree operations from subtree metadata. IndexedRope uses CountMetric; CharRope uses StringMetric to aggregate text metadata. Both accept a tree factory, with Treap as the default implementation.

With the default randomized Treap, tree-path costs are expected, not worst-case guarantees:

Operation	Expected cost
IndexedRope get, set, single insertion/removal	O(log N), for N elements
IndexedRope indexOf	O(log N) for a present instance; expected O(1) if absent
IndexedRope full node iteration	O(N)
CharRope character lookup	O(log C), for C text chunks
CharRope line-start lookup	O(log C + B), with a scan inside a chunk of at most B = 512 code units
CharRope toString	O(L + C), for L code units and C chunks

Batch insertion must process the inserted data, and range removal must visit removed nodes. Text edits also split or measure chunks. These operations are not constant-cost O(log N) regardless of input size. CharRope.subSequence currently performs repeated chunk lookups as it copies the selected text.

Build and test

The project uses Kotlin 2.3.0, Gradle Wrapper 9.0.0, and a JDK 21 toolchain. The build targets JVM 1.8 bytecode.

./gradlew test
./gradlew assemble

On Windows PowerShell, use ./gradlew.bat. Correctness tests cover tree operations, rope edits, position lookup, nested views, iterator invalidation, and randomized consistency checks. Performance tests are skipped by default.

Performance tests

Start with a small workload:

./gradlew test --tests '*PerformanceTest' '-DrunPerf=true' '-DperfBaseSize=1000' '-DperfDocSize=1000' '-DperfOps=20' '-DperfLookupOps=100' '-DperfSeed=47'

Property	Default	Scope
runPerf	Disabled	Set to true to enable performance tests
perfBaseSize	10,000,000	IndexedRope initial element count
perfDocSize	100,000,000	CharRope requested text length; rounded up to whole generated lines
perfOps	10,000	Insertions in either benchmark
perfLookupOps	10,000	Lookup queries in either benchmark
perfSeed	20260215	IndexedRope workload seed

Gradle forwards these system properties to the test JVM. The default workloads are large; choose sizes appropriate for available memory and time. Test heap limits are configured in build.gradle.kts.

The IndexedRope insertion benchmark includes actual mutable line-number updates for the list. Its lookup benchmark compares cached list positions with rope reverse lookup. Data preparation and correctness checks are outside the timed regions. These are exploratory benchmarks without JVM warmup or repeated statistical measurements, so timing ratios are not general performance guarantees.

Historical benchmark charts

The following charts predate the current line-tracking benchmark methodology and are retained as historical results.

License

MIT