TexelTree

A persistent data structure for rich text documents. Four element types and five principles are sufficient for the full range of rich text applications — from simple editors to word processors with embedded formulas and tables.

TexelTree is the foundation for wxtextview (a wxPython text widget), PyNotebook (a Jupyter-like notebook), and MiniWord (a WYSIWYG word processor).

Core Concepts

Four element types

Five principles

Index preservation. Every position in a document has a unique integer index. All operations preserve the invariant:

length(result) == length(root) + length(inserted) # insert
length(rest) + (i2 - i1) == length(root) # takeout

Immutability. Texels are never modified in place. Every operation returns a new tree; old trees remain intact.

Structural sharing. Unchanged subtrees are reused across versions. Storing 1000 edited versions of a large document costs far less than ×ばつ the original memory.

Balanced tree. The tree is an n-ary balanced tree (all leaves at the same depth). This guarantees O(log n) for all core operations.

Minimal element types. G is semantically invisible — it exists only to keep the tree balanced. Two trees that differ only in grouping describe the same document. This is what makes the canonical serialization format clean.

RichText — the standard interface

RichText is a mutable, document-level wrapper around the TexelTree. It is the normal way to work with documents in application code.

from texeltree.richtext import RichText

Building a document

rt = RichText("Hello, world!\nSecond paragraph.\n")
print(len(rt)) # 33
print(rt.nlines()) # 3
print(rt.get_text()) # 'Hello, world!\nSecond paragraph.\n'

Inserting and removing text

rt.insert_text(5, ", beautiful")
print(rt.get_text(0, 25)) # 'Hello, beautiful, world!'
rt.remove(5, 17) # remove ", beautiful"
print(rt.get_text(0, 13)) # 'Hello, world!'

insert takes a RichText object; insert_text is the convenience wrapper for plain strings:

rt.insert(5, RichText(" dear"))

Slicing

snippet = rt[0:5] # returns a new RichText
print(snippet.get_text()) # 'Hello'

Line navigation

row, col = rt.index2position(20) # index → (row, col)
i = rt.position2index(1, 3) # (row, col) → index
start = rt.linestart(1)
end = rt.lineend(1)
length = rt.linelength(1) # includes the trailing newline

Character styles

Styles are dictionaries of arbitrary key-value pairs. Common keys: bold, italic, fontsize, textcolor, bgcolor, underline, code.

rt = RichText("Hello, world!")
# Apply style to a range
rt.set_properties(0, 5, bold=True, fontsize=16)
# Query style at a position
s = rt.get_style(0) # {'bold': True, 'fontsize': 16}
# Get all style runs in a range
from texeltree.styles import get_styles
runs = get_styles(rt.texel, 0, len(rt))
# [(5, {'bold': True, 'fontsize': 16}), (8, {})]

Overlapping set_properties calls produce fine-grained runs:

rt.set_properties(2, 8, italic=True)
runs = get_styles(rt.texel, 0, len(rt))
# [(2, {bold, size}), (3, {bold, italic, size}), (3, {italic}), (5, {})]

Paragraph styles

Paragraph style is stored on the NL element that ends each paragraph. Common keys: base (role: h1–h6, body, blockquote, codeblock, bullet, ordered), indent.

rt = RichText("Title\nBody text.\n")
end_of_title = rt.lineend(0)
rt.set_parproperties(0, end_of_title + 1, base="h1")
print(rt.get_parstyle(0)) # {'base': 'h1'}

Style undo

Every set_properties and set_parproperties call returns a memo that captures the previous state. Pass it back to restore:

memo = rt.set_properties(0, 5, bold=True)
rt.set_styles(0, memo) # undo character style
memo_par = rt.set_parproperties(0, end + 1, base="h1")
rt.set_parstyles(0, memo_par) # undo paragraph style

Style interning

Identical styles share the same object in memory. Equality checking uses is instead of == — order of magnitude faster for frequent comparisons:

from texeltree.styles import create_style
s1 = create_style(bold=True, fontsize=14)
s2 = create_style(fontsize=14, bold=True) # different order, same content
assert s1 is s2 # True

Serialization

s = rt.serialize() # canonical text format (.txl)
root, endmark = RichText.deserialize(s)

Low-level API

The low-level API works directly with immutable Texel objects. Use it when you need full control — custom containers, performance-critical code, or when building your own document layer.

from texeltree.texeltree import T, NL, ENDMARK, grouped, insert, takeout, \
 length, get_text, as_style

Building a tree

h1 = as_style({'base': 'h1'})
root = grouped([
 T("TexelTree"),
 NL.set_parstyle(h1),
 T("A persistent document data structure."),
])
print(length(root)) # 50
print(get_text(root)) # 'TexelTree\nA persistent document data structure.'

Insert and takeout

Both return new objects; the original is unchanged:

new_root = grouped(insert(root, 9, [T(" (basics)")]))
assert length(new_root) == length(root) + 9 # index preservation
rest, kernel = takeout(root, 0, 9)
assert length(grouped(rest)) + 9 == length(root)

Undo

Because the original tree is never modified, undo is a variable assignment:

state0 = root
state1 = grouped(insert(root, 0, [T("X")]))
current = state1
current = state0 # undo — no inverse operation needed

Containers

Containers are structured elements with named slots. Each slot is surrounded by immutable separator elements (TAB or NL) that protect the document structure from accidental editing.

Define a container by subclassing Container:

from texeltree.texeltree import Container, TAB, T, grouped, insert, spans
class Fraction(Container):
 def __init__(self, numerator, denominator):
 self.childs = [TAB, numerator, TAB, denominator, TAB]
 self.compute_weights()
frac = Fraction(T("sin(x)"), T("cos(x)"))
print(spans(frac)) # mutable slots: [(1, 7), (8, 14)]

Insert into a slot:

frac2 = grouped(insert(frac, 1, [T("arc")]))
# numerator is now "arcsin(x)"

Attempting to delete a separator raises IndexError:

takeout(frac, 0, 1) # IndexError: immutable separator

get_text() on a container produces TAB/NL-separated plain text:

from texeltree.texeltree import get_text
print(get_text(frac)) # '\tsin(x)\tcos(x)\t'

Canonical Format

TexelTree documents can be serialized to a line-oriented text format (.txl). G elements are dissolved; the format uses only three types.

T('TexelTree')
NL({base="h1"})
T('A persistent document data structure.')
ENDMARK

Style flags: T('text', {bold, italic, fontsize=14}) Container: C("Fraction", T('a'), T('b'))

from texeltree.serialize import serialize, parse
s = serialize(root, endmark)
root2, endmark2 = parse(s)

Examples

All examples run from the examples/ directory:

cd examples
python demo_basics.py # index preservation, immutability, undo, roundtrip
python demo_containers.py # Fraction, Sqrt, Integral, Table, structural protection
python demo_styles.py # character/paragraph styles, interning, style undo
python demo_scale.py # Moby Dick (~1.2 MB), O(log n) benchmarks

Running the tests

python runtests.py texeltree/texeltree.py
python runtests.py texeltree/styles.py
python runtests.py texeltree/serialize.py
python runtests.py texeltree/richtext.py

Related Projects

• PyNotebook — Jupyter-like notebook with editable rich text cells
• MiniWord — WYSIWYG word processor using Cairo rendering