libara 0.1.0
libara: ^0.1.0 copied to clipboard
Attributed Range Algebra: overlapping markup as ranges over a persistent, editable sequence, with constructors, queries, layered documents, and JSON.
libara #
Attributed Range Algebra for Dart: markup as ranges over a sequence rather than as a tree inside it.
A document is a persistent sequence, such as the code points of a text. Its markup is a set of ranges over that sequence, each with scalar attributes. Ranges may overlap freely and are held by markers that move with every edit, so inserting or deleting text never requires adjusting an offset. Every edit returns a new version, and the previous one stays valid, which gives undo for free.
The library implements the Core Range Algebra and Attributed Range Algebra
papers, and the Range Constructors draft, and adds the persistent, editable
document and layered documents, whose layers of ranges over ranges a
caller's grammar derives. It is pure Dart, with one runtime dependency,
package:characters, for grapheme clusters, and runs on the VM and the
web.
Example #
import 'dart:convert';
import 'package:libara/libara.dart';
/// The value of [result]; an application would handle the failure instead.
T value<T>(Result<T> result) => switch (result) {
Success(:final value) => value,
Failure(:final message) => throw StateError(message),
};
void main() {
// A document holds a sequence, here the code points of a text, and every
// edit returns a new version.
final source = Text.of('The cat sat on the mat.');
var document = Document.of(source);
// A constructor finds ranges. Each word becomes an attributed range.
final words = regex(
RegExp('[a-z]+', caseSensitive: false),
attributes: {'type': Str(Text.of('word'))},
);
final found = value(words(source)).items.cast<ARange>().toList();
print('words: ${found.length}');
// Marking stores each range under a marker. A left-gravity end keeps a
// word from absorbing text typed right after it.
final marks = [
for (final range in found) Mark<int>(range, end: Gravity.left),
];
document = value(document.transact(marks));
// Edits move every range; the caller never adjusts an offset.
document = value(document.apply(Insert(4, Text.of('black '))));
print(String.fromCharCodes(document.items));
print('cat is now at ${document.resolve(marks[1].marker)}');
// Queries find the ranges at a position or across a span.
final view = value(Range.create(4, 9));
print('over "black cat": ${document.overlapping(view)}');
// Undo is a step back to the previous version.
print('undo: ${String.fromCharCodes(document.previous!.items)}');
// A document saves to JSON and loads back with fresh markers, in the
// order of document.markers.
final format = JSONFormat(text, history: true);
final json = jsonEncode(value(format.encode(document)));
final (loaded, markers) = value(format.restore(jsonDecode(json)));
print('loaded ${loaded.ranges.length} ranges, version ${loaded.version}');
print('first word: ${loaded.resolve(markers.first)}');
// A selector finds ranges by their attributes and by how they nest.
// Here a type selector reads the `type` attribute, and `phrase > word`
// selects the words whose innermost container is the phrase.
final phrase = Mark<int>(
value(ARange.create(4, 13, attributes: {'type': Str(Text.of('phrase'))})),
);
final selector = value(Selector.parse('phrase > word', type: 'type'));
final inside = value(loaded.apply(phrase)).select(selector);
print('in the phrase: ${[for (final (_, range) in inside) range]}');
// Replicas edit one document with no server. Each commit is an
// operation to send to the others, and concurrent edits converge.
var alice = value(Replica.create<int>('alice'));
var bob = value(Replica.create<int>('bob'));
final Operation<int> hello;
(alice, hello) = value(alice.commit([Insert(0, Text.of('hello'))]));
(bob, _) = value(bob.receive(hello));
final Operation<int> world;
(alice, world) = value(alice.commit([Insert(5, Text.of(' world'))]));
final Operation<int> oh;
(bob, oh) = value(bob.commit([Insert(0, Text.of('Oh, '))]));
// Operations travel as JSON, here bob's to alice.
final wire = OperationFormat(text);
final sent = jsonEncode(value(wire.encode(oh)));
(alice, _) = value(alice.receive(value(wire.decode(jsonDecode(sent)))));
(bob, _) = value(bob.receive(world));
print('alice: ${String.fromCharCodes(alice.document.items)}');
print('bob: ${String.fromCharCodes(bob.document.items)}');
}
It prints:
words: 6
The black cat sat on the mat.
cat is now at {10,3,type:word}
over "black cat": [{10,3,type:word}]
undo: The cat sat on the mat.
loaded 6 ranges, version 2
first word: {0,3,type:word}
in the phrase: [{10,3,type:word}, {14,3,type:word}]
alice: Oh, hello world
bob: Oh, hello world
Concepts #
- Sequences.
Sequence<T>is an immutable sequence with the algebra's operations.Items<T>is backed by a list;Textholds Unicode code points, so a position counts characters, not UTF-16 units. - Ranges. A
Rangeis a start and a length;ARangeadds attributes, whose values areStr,Num,Bool, orNil.Rangesadds ordering and the containment structure: ancestors, descendants, parent, children. - Constructors. A
Constructor<T>finds ranges in a sequence.regexmatches a pattern;union,concat, andlayercompose constructors, so overlapping interpretations can stand side by side. - Documents.
Document<T>is a persistent sequence carrying marked ranges. Commands (Insert,Delete,Replace,Mark,Unmark,Update) are applied withapply, or several at once withtransact, and each makes a new version linked throughprevious. Query a version withresolve,at,overlapping,ranges, andmarkers, or, with each range's marker,withina region andcrossinga position;mapcarries a position from an earlier version into a later one. - Gravity. Each endpoint of a marked range is left or right gravity, which decides only what happens when items are inserted exactly at it: a right endpoint moves past them, a left one stays before them. The default, right at both ends, grows a range at its end; a left end keeps a token from absorbing text typed after it.
- History. Every version keeps its predecessor alive.
compact()returns a fresh version 0 with the same ranges and markers, releasing the history and shortening internal labels. - Saving. A
Format<D, S>maps values to a serialized form and back.JSONFormatturns a document into a JSON value and back, optionally with its history, through an item format for its items;textis the item format for code points. - Layered documents.
Layered<T>holds layers 1 to n over one sequence: layer 1 is the sequence, and each layer above is a sequence of ranges over the items of the layer below, such as tokens over text and elements over tokens. Every layer is a persistentDocument, so an edit at one layer moves the ranges above it. A caller'sGrammar<T>says what the layers mean:derivegives a layer's ranges and diagnostics over a region of the one below,affectednames the region an edit touches, andeditcarries out structural edits. A grammar reads one region throughslice,within,crossing, andspan, so a keystroke costs time that follows nesting depth and the region, not the size of the document.compact()releases a layered document's history. - Layered edits. An
Edit(layer, command)reuses the document commands. At layer 1,Insert,Delete, andReplaceedit the items and are always accepted; the layers above are derived again over the affected region, and what does not parse becomes diagnostics. Above layer 1,Mark,Unmark,Update, andDeletego to the grammar, which refuses them or describes the edits one layer down that carry them out, so a structural edit never lexes text.applyandtransactreturn aChange: the new version and, per layer, the ranges created, removed, and updated.LayeredFormatreads and writes a layered document as its layer-1 sequence, so withtextit travels as its markup. - Selectors.
Selector.parsereads a CSS-like selector, andselectandmatchesapply it to a document's ranges, one layer of a layered document, or any list of keyed ranges. Containment plays the part of the element tree:section pis apinside asection, andsection > pone whose innermost container is thesection. Type, attribute, and structural selectors,:not,:is, and:haswork as in CSS;:overlapsand:crossesselect ranges by overlap, which a tree cannot express. A query costsO(m log m)per term overmranges. AScope, fromScope(pairs),document.scope(), orlayered.scope(layer), indexes its ranges once for many selections, andlayered.across(layers)projects several layers' ranges to base positions, so one selector relates them:p [type=text]over the XML example's layers 2 and 3 selects the text insidepelements. - Replicas.
Replica<T>lets several copies of one document edit concurrently with no server. Eachcommitreturns anOperation, stamped by a hybrid logical clock and naming the operations it had seen;receivemerges operations from any replica in any causal order, andsincegives what a peer lacks. Replicas holding the same operations hold equal documents, with each range under the sameKey: concurrent insertions do not interleave, updates are last writer wins by stamp, and an unmark wins over a concurrent update.OperationFormatcarries operations as JSON. - Coordinates.
Coordinates.of(text)converts code-point positions to what editors and language servers count: UTF-16 offsets (Unit), and lines and columns (Place), with columns in UTF-16 units, code points, or grapheme clusters. Over aDocument<int>every conversion isO(log n)in any version, from measures its tree caches when first asked. It also works in user-perceived characters:next,previous,boundary, andclustermove by grapheme cluster,graphemescounts them,snapwidens a range so it never splits one, andsnappeddoes the same for every range a constructor gives.
The repository's example/xml/ holds a grammar for a small subset of XML,
with tokens, elements, well-formedness diagnostics, and wrapping,
unwrapping, renaming, and deleting elements; dart run example/xml/main.dart
shows it at work. It reads tokens with package:petitparser, a development
dependency only. It is an example, not part of the library.
example/music/ treats a melody as a sequence of notes, not characters:
bars from the meter and phrases from the rests are two hierarchies that
overlap, queried together with selectors; dart run example/music/main.dart runs it.
Documentation #
doc/ explains the library in depth: the theory from
the reference papers, the architecture, the
algorithms, and the music example.
Things to know #
- Failures are values. Operations that can fail return a
Result, aSuccessor aFailurewith aKindand a message. The library does not throw for an expected failure. Two things can still throw: writing an item of the wrong runtime type into a covariant sequence, which is aTypeError, and a callback passed toResult.maporflatMap, whose exception is not caught. Code a caller plugs in is caught at its boundary:JSONFormatturns anything an item format throws into a failure, and a layered document does the same for its grammar, or records a diagnostic inLayered.of, which fails only for a grammar whose depth is below 1 or whosedepthgetter throws. - Some sequence operations drop markup. On a
Document,slice,diff,union, andintersectreturn plainItemswithout ranges or history;concatkeeps the receiver's ranges and not the argument's. - Equality. Sequences compare their items, so a
Documentequals anItemswith the same items regardless of ranges. TwoARanges are equal only with equal attributes;samecompares position alone. - Unicode. Positions are code points. A
RegExpwithoutunicode: truecan match half of a character outside the Basic Multilingual Plane; such a match is widened to the whole character. Thetextformat refuses to save a high surrogate followed by a low one, which would read back as one character. - Line ends.
Coordinatesends lines at\n,\r\n,\r, NEL, LINE SEPARATOR, and PARAGRAPH SEPARATOR. The LSP counts only the first three, so a server whose texts can hold the others numbers lines differently from its clients after them. - Graphemes follow
package:characters. Clusters are Unicode's extended grapheme clusters as that package finds them, so they change with its Unicode version. Segmentation starts at the start of a line, since clusters never cross a line end, so a grapheme query costs time in the width of its line. - The web. Integers beyond 2^53 are not exact in JavaScript, so very large positions do not survive saving and loading there.
- Layered ranges grow inward. A range in a layered document grows only
for items inserted strictly inside it; items inserted at either end lie
outside it until its layer is derived again. So a grammar's
affectedmust take in every range that starts or ends where the changed items do. The layered document itself widens the region over diagnostics that touch it and ranges that cross its ends. - Grammars must be pure. A layered document reads its grammar's
depthonce, but calls its other methods again whenever a version is edited, however old. A grammar whose answers depend on anything but its arguments, or whose configuration changes during a session, can derive an old version differently from how it was built. - History keeps what was deleted. Every version holds its
previous, and commands hold the items they inserted, so deleted items stay reachable, andJSONFormatwithhistory: truesaves them.compact()drops the history of the version it returns, but any older version still held keeps its own; it is not erasure. - Extension points are trusted. Sequence values are immutable only
as deeply as their items: a mutable item can change an old version and
its hash. A
Rangesubclass is read throughstartandlength, which must not change or fail, and a customSequencemust not throw from its getters.JSONFormatlimits what it reads withLimits; nothing bounds what such code does. - Regular expressions run synchronously. A backtracking pattern over untrusted text can take a long time, and nothing can interrupt it on the same isolate.
License #
BSD 3-Clause; see LICENSE.