Skip to content

Instantly share code, notes, and snippets.

@jcmoore

jcmoore/index.html

Created June 13, 2022 23:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jcmoore/b2ec580255f6ad3fb6a9e2bea836b765 to your computer and use it in GitHub Desktop.
Save jcmoore/b2ec580255f6ad3fb6a9e2bea836b765 to your computer and use it in GitHub Desktop.
Download ZIP
SuperbList -- starter kit for client-side database synchronization patterns
Raw
index.html
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="https://cdn.quilljs.com/1.3.6/quill.snow.css" rel="stylesheet">
<script src="https://cdn.quilljs.com/1.3.6/quill.js"></script>
<script type="module">
import { createSignal, onCleanup, onMount } from "https://cdn.skypack.dev/solid-js";
import { render } from "https://cdn.skypack.dev/solid-js/web";
import html from "https://cdn.skypack.dev/solid-js/html";
import { SuperbMerge, SuperbUnicode, UnicodeLeaf } from "./superblist.js";
Promise.resolve().then(() => render(App, document.body));
const App = () => {
const merge = window.merge = new SuperbMerge();
const unicode = window.list = new SuperbUnicode();
unicode.insertText(0, '[ "B","O","X" ]');
merge.insertIds(0, unicode.size(), true);
const { 0: text, 1: setText } = createSignal(unicode.getUTF16());
const sliceIds1 = [
merge.getId(2, true),
merge.getId(unicode.size() - 3, true),
];
const { 0: slice1, 1: setSlice1 } = createSignal(getSlice(sliceIds1));
const sliceIds2 = [
merge.getId(0, true),
merge.getId(2, true),
];
const { 0: slice2, 1: setSlice2 } = createSignal(getSlice(sliceIds2));
const sliceIds3 = [
merge.getId(unicode.size() - 3, true),
merge.getId(unicode.size() - 1, true),
];
const { 0: slice3, 1: setSlice3 } = createSignal(getSlice(sliceIds3));
let quill;
onMount(() => {
quill = new Quill('#editor', {
theme: 'snow'
});
quill.on('text-change', onQuillDelta);
})
return html`
<div>
<div>
<span id="slice1">${slice1}</span>
</div>
<div>
<span id="slice2">${slice2}</span>
</div>
<div>
<span id="slice3">${slice3}</span>
</div>
<div id="editor" style="height">
${text()}
</div>
</div>
`;
function onQuillDelta (delta, oldDelta, source) {
let offset = 0;
for (let index = 0; index < delta.ops.length; index += 1) {
const { retain, delete: backspace, insert } = delta.ops[index];
// TODO: make unicode-aware
offset += 0|retain;
offset += 0|backspace;
if (backspace) merge.backspaceIds(offset, backspace, true);
if (backspace) unicode.backspaceText(offset, backspace);
if (insert) merge.insertIds(offset, insert.length, true);
if (insert) unicode.insertText(offset, insert);
offset += insert ? insert.length : 0;
}
setText(unicode.getUTF16());
setSlice1(getSlice(sliceIds1));
setSlice2(getSlice(sliceIds2));
setSlice3(getSlice(sliceIds3));
}
function getSlice({ 0: begin, 1: finish }) {
const start = merge.getOffset(begin, true);
const end = 1 + merge.getOffset(finish, true);
let utf16 = unicode.getUTF16();
utf16 = utf16.slice(UnicodeLeaf.offset(utf16, start));
utf16 = utf16.slice(0, UnicodeLeaf.offset(utf16, end - start));
return utf16;
}
// designed for central server
// lazy/partial/async loading-friendly
// snapshot isolation and time-travel queries
// flexible data model -- list, map, queue, probably more...
// conditional edits with range-centric constraints
// range-based change-detection within a single object or across adjacent objects
// composable "structure of arrays"
// "mostly" e2e-encryptable
// not a library, nor a framework -- a pattern and a forkable starter kit
// aspirations of understandability
};
</script>
</head>
<body>
</body>
</html>
Raw
superblist.js
export {
ShiftingFrame,
LogicalTime,
MergeId,
MergeDeviation,
IdTimeline,
IdGraph,
IdHandle,
IdNode,
IdBranch,
IdLeaf,
MergeHandle,
MergeNode,
RefLeaf,
RefBranch,
RefHandle,
RefNode,
MergeJuncture,
SuperbMerge,
UnicodeLeaf,
UnicodeBranch,
UnicodeHandle,
UnicodeNode,
SuperbUnicode,
};
class ShiftingFrame {
constructor({
restricted = 0,
appendable = 0,
enqueuing = 0,
dequeuing = 0,
} = {}) {
if (restricted > appendable) {
throw new Error("Invalid frame striping.");
} else if (enqueuing >= restricted && enqueuing < appendable) {
throw new Error("Invalid enqueuing point.");
} else if (dequeuing < restricted || dequeuing >= appendable) {
if (dequeuing > enqueuing) throw new Error("Invalid dequeuing point.");
}
this.restricted = restricted;
this.appendable = appendable;
this.dequeuing = dequeuing;
this.enqueuing = enqueuing;
}
}
class LogicalTime {
constructor({
coarse = "",
fine = 0,
} = {}) {
this.coarse = coarse;
this.fine = fine; // generally run-length encoding friendly
}
}
class MergeId extends LogicalTime {}
class MergeDeviation extends LogicalTime {}
// to find the haystack/graph of a node/leaf, match the level of its deviation to juncture of the list being searched
// MUTABLE
class IdTimeline {
constructor({
// TODO: _frame = new ShiftingFrame({}),
_points = [new LogicalTime({})],
_graphs = [new IdGraph({})],
} = {}) {
// until properly queuing, IdNode/RefNode trees are practically immutable but not practically peresistent
this._points = _points;
this._graphs = _graphs;
}
reset(
graph = new IdGraph({}),
around = this.now(),
) {
this._graphs = [graph];
this._points = [around];
}
now() {
return this._points[0];
}
getGraph(
around = this.now(),
shortcut = this.getShortcut(around),
coarse = around.coarse,
fine = around.fine,
) {
// TODO: need queue index mapping to properly support shortcuts
// if (shortcut >= 0 && shortcut < this._points.length) {
// let pt = this._points[shortcut];
// if (pt.coarse < coarse || pt.coarse === coarse && pt.fine <= fine) {
// }
// if (point.coarse === around.coarse && point.fine === around.fine) {
// return this._graphs[shortcut];
// }
// }
return this._graphs[0];
}
getShortcut(
around = this.now(),
coarse = around.coarse,
fine = around.fine,
) {
// TODO: binary search the queue
return -1;
}
}
class IdGraph {
constructor({
haystack = null,
} = {
haystack: new IdHandle(undefined),
}) {
this.haystack = haystack;
}
}
class IdHandle {
constructor({
// TODO: address = "",
_node = null,
} = {
_node: new IdNode({}),
}) {
this._node = _node;
}
node() {
return this._node;
}
}
class IdNode {
constructor({
merge = new MergeHandle(undefined),
branches = [],
leaves = [],
} = {
branches: [new IdBranch({})],
leaves: [new IdLeaf({})],
}) {
let backspaces = 0;
let width = 0;
if (branches.length) {
// calculate backspaces/width from sum total of branches
for (let index = 0; index < branches.length; index += 1) {
backspaces += branches[index].backspaces;
width += branches[index].width;
}
} else if (leaves) {
// calculate backspaces/width from sum total of leaves
for (let index = 0; index < leaves.length; index += 1) {
backspaces += leaves[index].backspaces;
width += leaves[index].width;
}
}
this.backspaces = backspaces;
this.width = width;
this.merge = merge;
this.branches = branches;
this.leaves = leaves;
}
}
class IdBranch {
constructor({
backspaces = -1,
width = -1,
handle = null,
} = {
handle: new IdHandle(undefined),
}) {
const node = handle ? handle.node() : null;
this.backspaces = node ? node.backspaces : backspaces;
this.width = node ? node.width : width;
this.handle = handle;
}
}
class IdLeaf {
constructor({
backspaces = 0,
width = 1,
id = null,
merge = null,
} = {
id: new MergeId({}),
merge: new MergeHandle(undefined),
}) {
this.backspaces = backspaces;
this.width = width;
this.id = id;
this.merge = merge;
}
}
class MergeHandle {
constructor({
// TODO: address = "",
_node = null,
} = {
_node: new MergeNode({}),
}) {
this._node = _node;
}
node() {
return this._node;
}
}
class MergeNode {
constructor({
deviation = new MergeDeviation({}),
// MUTABLE
_timelines = [{ [String("")]: new IdTimeline({}) }],
} = {}) {
this.deviation = deviation;
this._timelines = _timelines;
}
}
// each IdLeaf instance has exactly one RefLeaf instance that notes the deviation of its instantiation
// each reference/containment of an IdLeaf has an entry in the MergeNode timelines to associate a point with its graph (haystack)
class RefLeaf extends IdLeaf {}
class RefBranch {
constructor({
start = null,
end = null,
handle = null,
} = {
start: new MergeId({}),
end: new MergeId({}),
handle: new RefHandle(undefined),
}) {
this.start = start;
this.end = end;
this.handle = handle;
}
}
class RefHandle {
constructor({
// TODO: address = "",
_node = null,
} = {
_node: new RefNode({}),
}) {
this._node = _node;
}
node() {
return this._node;
}
}
class RefNode {
constructor({
// TODO: derivation || juncture = null,
branches = [],
leaves = [],
} = {
branches: [new RefBranch({})],
leaves: [new RefLeaf({})],
}) {
this.branches = branches;
this.leaves = leaves;
}
}
// MUTABLE
class MergeJuncture {
constructor({
deviation = new MergeDeviation({}),
_point = new LogicalTime({}),
} = {}) {
this.deviation = deviation;
this._point = _point;
}
}
class SuperbMerge {
// insertIds(
// offset = 0,
// width = 1,
// exclusive = false,
// id = this._usable,
// at = this._tick(),
// ) {}
// backspaceIds(
// offset = 1, // always exclusive -- backspaces are not consumed by already "deleted" content
// width = 1,
// at = this._tick(),
// ) {}
fork(
timeline = "",
at = this._now(),
) {
const result = new SuperbMerge(this);
const fine = result._junctures.length;
const deviation = new MergeDeviation({ coarse: timeline, fine });
const juncture = new MergeJuncture({ deviation, _point: at });
result._junctures.push(juncture);
return result;
}
constructor({
ordering = null,
sorted = null,
// MUTABLE
_junctures = [new MergeJuncture({})],
_clock = new LogicalTime({}),
_usable = new MergeId({}),
} = {
ordering: new IdHandle(undefined),
sorted: new RefHandle(undefined),
}) {
this.ordering = ordering;
this.sorted = sorted;
const mutable = _junctures.slice();
mutable[mutable.length - 1] = new MergeJuncture({
deviation: mutable[mutable.length - 1].deviation,
_point: new LogicalTime(mutable[mutable.length - 1]._point),
});
this._junctures = mutable;
this._clock = _clock;
this._usable = _usable;
}
_deviation() {
return this._junctures[this._junctures.length - 1].deviation;
}
_now() {
return this._junctures[this._junctures.length - 1]._point;
}
_tock() {
this._junctures[this._junctures.length - 1]._point = this._clock;
this._clock = new LogicalTime(this._clock);
}
_tick() {
this._clock.fine += 1;
return this._clock;
}
now(
result = new LogicalTime({}),
) {
const point = this._now();
result.coarse = point.coarse;
result.fine = point.fine;
return result;
}
deviation(
result = new MergeDeviation({}),
) {
const deviation = this._deviation();
result.coarse = deviation.coarse;
result.fine = deviation.fine;
return result;
}
_writeRef(
ref = new RefLeaf({}),
) {
const mutable = [ref];
const vals = this._nodeWrite(this.sorted, mutable);
if (vals.length === 2) {
const limb = this._nestSorted(vals[0]);
const sibling = this._nestSorted(vals[1]);
this.sorted = this._partitionSorted([limb, sibling], [], at)[0];
} else if (vals.length === 1) {
this.sorted = vals[0];
} else {
throw new Error("Unexpected insertion root change.");
}
return mutable;
}
_nodeWrite(
handle = this.sorted,
mutable = [new RefLeaf({})],
) {
const temp = handle.node();
const branches = temp.branches.slice();
if (!branches.length) {
return this._leafWrite(handle, mutable);
}
const coarse = mutable[0].id.coarse;
const fine = mutable[0].id.fine;
let index = 0;
for (; index < branches.length; index += 1) {
const limb = temp.branches[index];
if (coarse > limb.end.coarse) continue;
if (coarse === limb.end.coarse && fine >= limb.end.fine) continue;
const vals = this._nodeWrite(limb.handle, mutable);
if (vals.length === 2) {
const sibling = this._nestSorted(vals[1]);
branches.splice(index, 1, this._nestSorted(vals[0]), sibling);
} else if (vals.length === 1) {
branches.splice(index, 1, this._nestSorted(vals[0]));
} else {
throw new Error("Unexpected write branch change.");
}
break;
}
if (index >= branches.length) throw new Error("Did not write.");
else return this._partitionSorted(branches, []);
}
_leafWrite(
handle = this.sorted,
mutable = [new RefLeaf({})],
) {
const temp = handle.node();
const leaves = temp.leaves.slice();
while (mutable.length > 1) mutable.pop();
const ref = mutable.pop();
const coarse = ref.id.coarse;
const fine = ref.id.fine;
let index = 0;
for (; index < leaves.length; index += 1) {
const stem = temp.leaves[index];
if (coarse < stem.id.coarse) break;
if (coarse > stem.id.coarse) continue;
if (fine >= stem.id.fine + stem.width) continue;
if (fine < stem.id.fine) throw new Error("Ref writes must be monotonic.");
if (fine !== stem.id.fine) throw new Error("Ref writes must be aligned.");
if (ref.width >= stem.width) {
leaves[index] = ref;
} else {
const width = stem.width - ref.width;
const backspaces = stem.backspaces > width ? width : stem.backspaces;
leaves.splice(index, 0, ref);
leaves[index + 1] = new RefLeaf({
backspaces,
width,
id: new MergeId({ coarse, fine: fine + ref.width }),
merge: this._makeMerge(),
});
mutable[0] = leaves[index + 1];
}
index = -1;
break;
}
if (index >= leaves.length) leaves.push(ref);
else if (index > -1) leaves.splice(index, 0, ref);
if (mutable.length === 0) mutable[0] = null;
return this._partitionSorted([], leaves);
}
_partitionSorted(
branches = [new RefBranch({})],
leaves = [new RefLeaf({})],
) {
const LIMIT = 64;
const count = branches.length > 0 ? branches.length : leaves.length;
const handle = count <= LIMIT
? this._makeSorted(branches, leaves) // no need to split node
: this._makeSorted( // split node
branches.splice(count >> 1, 1 / 0),
leaves.splice(count >> 1, 1 / 0),
);
const results = count <= LIMIT
? [handle] // no need to split node
: [this._makeSorted(branches, leaves), handle]; // split node
return results;
}
_makeSorted(
branches = [new RefBranch({})],
leaves = [new RefLeaf({})],
) {
const _node = new RefNode({ branches, leaves });
const handle = new RefHandle({ _node });
return handle;
}
_nestSorted(
handle = new RefHandle(undefined),
) {
const node = handle.node();
const start = node.branches.length > 0
? node.branches[0].start
: node.leaves[0].id;
const end = node.branches.length > 0
? node.branches[node.branches.length - 1].end
: node.leaves[node.leaves.length - 1].id;
const branch = new RefBranch({ start, end, handle });
return branch;
}
getRef(
needle = new MergeId({}),
coarse = needle.coarse,
fine = needle.fine,
) {
let temp = this.sorted.node();
// "recursively" search b+tree branches for leafy-haystack by needle
while (temp.branches.length > 0) {
for (let index = 0; index < temp.branches.length; index += 1) {
const limb = temp.branches[index];
if (coarse > limb.end.coarse) continue;
if (coarse === limb.end.coarse && fine >= limb.end.fine) continue;
temp = limb.handle.node();
break;
}
}
// search b+tree leaves for leafy-haystack by needle
for (let index = 0; index < temp.leaves.length; index += 1) {
const stem = temp.leaves[index];
if (coarse < stem.id.coarse) break;
if (coarse > stem.id.coarse) continue;
if (fine >= stem.id.fine + stem.width) continue;
if (fine < stem.id.fine) break;
return stem;
}
return null;
}
getSnapshot(
point = new LogicalTime({}),
handle = new MergeHandle(undefined),
timeline = this._deviation().coarse,
merge = handle.node(),
) {
const deviation = merge.deviation;
let around = point;
let label = timeline;
let index = this._junctures.length - 1 - deviation.fine;
if (index < 0) throw new Error("Cannot use resource from the future.");
for (; index > -1; index -= 1) {
if (merge._timelines.length > index && merge._timelines[index][label]) {
return merge._timelines[index][label].getGraph(around);
}
const juncture = this._junctures[index + deviation.fine];
label = juncture.deviation.coarse;
around = juncture._point;
}
throw new Error("Could not find snapshot.");
}
getOffset(
needle = new MergeId({}),
exclusive = false, // exclude backspaces in offset distance
point = this._now(),
coarse = needle.coarse,
fine = needle.fine,
) {
const ref = this.getRef(needle, coarse, fine);
if (!ref) return -1;
let graph = this.getSnapshot(point, ref.merge);
let haystack = graph.haystack.node();
let offset = 0;
// search leafy-haystack for needle
if (!exclusive || haystack.width > haystack.backspaces) {
for (let index = 0; index < haystack.leaves.length; index += 1) {
const stem = haystack.leaves[index];
const quantity = stem.width - stem.backspaces;
if (
coarse !== stem.id.coarse || fine < stem.id.fine ||
fine >= stem.id.fine + stem.width
) {
offset += exclusive ? quantity : stem.width;
continue;
}
if (exclusive && quantity < fine - stem.id.fine) offset += quantity;
else offset += fine - stem.id.fine;
break;
}
}
// "recursively" search for target haystack in branchy-haystacks
graph = this.getSnapshot(point, haystack.merge);
while (graph.haystack) {
const target = haystack;
haystack = graph.haystack.node();
for (let index = 0; index < haystack.branches.length; index += 1) {
const limb = haystack.branches[index];
const quantity = limb.width - limb.backspaces;
if (limb.node() === target) break;
offset += exclusive ? quantity : limb.width;
}
if (exclusive && haystack.width <= haystack.backspaces) offset = 0;
if (index >= haystack.branches.length) throw new Error("Offset unknown.");
graph = this.getSnapshot(point, haystack.merge);
}
if (haystack !== this.ordering.node()) throw new Error("Root not found.");
return offset;
}
getBackspaces(
offset = 0,
) {
let count = offset;
let node = this.ordering.node();
let backspaces = 0;
// "recursively" skip over branches seeking to offset
while (node.branches.length > 0) {
for (let index = 0; index < node.branches.length; index += 1) {
const limb = node.branches[index];
if (count >= limb.width) {
count -= limb.width;
backspaces += limb.backspaces
continue;
}
node = limb.handle.node();
break;
}
}
// skip over leaves seeking to remaining offset
for (let index = 0; index < node.leaves.length; index += 1) {
const stem = node.leaves[index];
if (count >= stem.width) {
count -= stem.width;
backspaces += stem.backspaces;
continue;
}
backspaces += count - (stem.width - stem.backspaces);
break;
}
return backspaces;
}
getId(
offset = 0,
exclusive = false,
result = new MergeId({}),
) {
let count = offset;
let node = this.ordering.node();
if (offset < 0) return null;
else if (!exclusive && offset >= node.width) return null;
else if (exclusive && offset >= node.width - node.backspaces) return null;
// "recursively" skip over branches seeking to offset
while (node.branches.length > 0) {
for (let index = 0; index < node.branches.length; index += 1) {
const limb = node.branches[index];
const quantity = limb.width - limb.backspaces;
const delta = exclusive ? quantity : limb.width;
if (count >= delta) {
count -= delta;
continue;
}
node = limb.handle.node();
break;
}
}
// skip over leaves seeking to remaining offset
for (let index = 0; index < node.leaves.length; index += 1) {
const stem = node.leaves[index];
const quantity = stem.width - stem.backspaces;
const delta = exclusive ? quantity : stem.width;
if (count >= delta) {
count -= delta;
continue;
}
result.coarse = stem.id.coarse;
result.fine = stem.id.fine + count;
return result;
}
return null;
}
_makeMerge(
deviation = this._deviation(),
) {
const timeline = new IdTimeline({
_points: [null],
_graphs: [null],
});
const merge = new MergeHandle({
_node: new MergeNode({
deviation,
_timelines: [{ [deviation.coarse]: timeline }],
}),
});
return merge;
}
_makeOrdering(
branches = [new IdBranch({})],
leaves = [new IdLeaf({})],
deviation = this._deviation(),
) {
const merge = this._makeMerge(deviation);
const _node = new IdNode({ merge, branches, leaves });
const handle = new IdHandle({ _node });
return handle;
}
_nestOrdering(
handle = new IdHandle(undefined),
) {
const node = handle.node();
const width = node.width;
const branch = new IdBranch({ backspaces: node.backspaces, width, handle });
return branch;
}
insertIds(
offset = 0,
width = 1,
exclusive = false,
id = this._usable,
at = this._tick(),
) {
const handle = this.ordering;
const node = handle.node();
if (offset < 0) {
throw new Error("Offset must be non-negative.");
} else if (!exclusive && offset > node.width) {
throw new Error("Offset out of bounds.");
} else if (exclusive && offset > node.width - node.backspaces) {
throw new Error("Offset out of bounds.");
} else if (this.getRef(id)) {
throw new Error("Insert must be unique.");
}
const vals = this._nodeInsert(handle, offset, width, exclusive, id, at);
if (vals.length === 2) {
const limb = this._nestOrdering(vals[0]);
const sibling = this._nestOrdering(vals[1]);
this.ordering = this._partitionOrdering([limb, sibling], [], at)[0];
} else if (vals.length === 1) {
this.ordering = vals[0];
} else {
throw new Error("Unexpected insertion root change.");
}
const deviation = this._deviation();
const graph = new IdGraph({ haystack: null });
const root = this.ordering.node();
// root.merge = this._makeMerge();
root.merge.node()._timelines[0][deviation.coarse].reset(graph, at);
this._usable = new MergeId(id);
this._usable.fine += width;
this._tock();
}
_nodeInsert(
handle = this.ordering,
offset = 0,
width = 1,
exclusive = false,
id = this._usable,
at = this._tick(),
zero = false,
) {
const node = handle.node();
const branches = node.branches.slice();
if (!branches.length) {
// insert id into leaf node
return exclusive && node.backspaces === node.width
? this._leafInsert(handle, offset, width, exclusive, id, at, true)
: this._leafInsert(handle, offset, width, exclusive, id, at, zero);
}
let index = 0;
if (zero) {
for (index = 0; index < branches.length; index += 1) {
branches[index] = new IdBranch(branches[index]);
branches[index].backspaces = branches[index].width;
}
}
let count = offset;
// recursively insert id into branches covering offset
for (index = 0; index < branches.length; index += 1) {
const limb = branches[index];
const quantity = limb.width - limb.backspaces;
const delta = exclusive ? quantity : limb.width;
if (count > delta || count === delta && index < branches.length - 1) {
count -= delta;
continue;
}
const vals = exclusive && !quantity
? this._nodeInsert(limb.handle, count, width, exclusive, id, at, true)
: this._nodeInsert(limb.handle, count, width, exclusive, id, at, zero);
if (vals.length === 2) {
const sibling = this._nestOrdering(vals[1]);
branches.splice(index, 1, this._nestOrdering(vals[0]), sibling);
} else if (vals.length === 1) {
branches.splice(index, 1, this._nestOrdering(vals[0]));
} else {
throw new Error("Unexpected insertion branch change.");
}
break;
}
if (index >= branches.length) throw new Error("Did not insert.");
else return this._partitionOrdering(branches, [], at);
}
_leafInsert(
handle = this.ordering,
offset = 0,
width = 1,
exclusive = false,
id = this._usable,
at = this._tick(),
zero = false,
) {
let count = offset;
const leaves = handle.node().leaves.slice();
if (zero) {
for (let index = 0; index < leaves.length; index += 1) {
const ref = new RefLeaf(leaves[index]);
ref.merge = this._makeMerge();
ref.backspaces = ref.width;
leaves[index] = new IdLeaf(ref);
this._writeRef(ref);
}
}
if (count === 0) {
// insert before all existing leaves
const ref = new RefLeaf({ width, id, merge: this._makeMerge() });
leaves.splice(0, 0, new IdLeaf(ref));
this._writeRef(ref);
} else {
for (let index = 0; index < leaves.length; index += 1) {
const stem = leaves[index];
const quantity = stem.width - stem.backspaces;
const delta = exclusive ? quantity : stem.width;
if (count < delta || exclusive && stem.backspaces && count === delta) {
// split existing leaf and insert inbetween
leaves.splice(
index,
0,
new IdLeaf({
backspaces: exclusive || count < quantity ? 0 : count - quantity,
width: count,
id: stem.id,
merge: this._makeMerge(),
}),
stem,
);
const ref = this._writeRef(new RefLeaf(leaves[index + 0]))[0];
if (ref.id.coarse !== stem.id.coarse) {
throw new Error("Mismatched leaf slice.");
} else if (stem.width - ref.width !== ref.id.fine - stem.id.fine) {
throw new Error("Misaligned leaf slice.");
}
// ref.merge = this._makeMerge();
leaves[index + 2] = new IdLeaf(ref);
const merge = this._makeMerge();
leaves[index + 1] = new IdLeaf({ width, id, merge });
this._writeRef(new RefLeaf(leaves[index + 1]));
break;
}
if (count === delta) {
const fusible = id.coarse === stem.id.coarse &&
id.fine === stem.id.fine + stem.width &&
!stem.backspaces;
if (!fusible) {
// insert after existing leaf
const ref = new RefLeaf({ width, id, merge: this._makeMerge() });
leaves.splice(index + 1, 0, new IdLeaf(ref));
this._writeRef(ref);
} else {
// extend existing leaf
leaves[index] = new IdLeaf({
backspaces: 0,
width: stem.width + width,
id: stem.id,
merge: this._makeMerge(),
});
this._writeRef(new RefLeaf(leaves[index]));
}
break;
}
count -= delta;
}
}
return this._partitionOrdering([], leaves, at);
}
_partitionOrdering(
branches = [new IdBranch({})],
leaves = [new IdLeaf({})],
at = this._tick(),
) {
const LIMIT = 64;
const deviation = this._deviation();
const count = branches.length > 0 ? branches.length : leaves.length;
const handle = count <= LIMIT
? this._makeOrdering(branches, leaves, deviation) // no need to split node
: this._makeOrdering( // split node
branches.splice(count >> 1, 1 / 0),
leaves.splice(count >> 1, 1 / 0),
deviation,
);
const results = count <= LIMIT
? [handle] // no need to split node
: [this._makeOrdering(branches, leaves, deviation), handle]; // split node
for (let offset = 0; offset < results.length; offset += 1) {
const haystack = results[offset];
const graph = new IdGraph({ haystack });
const node = haystack.node();
for (let index = 0; index < count; index += 1) {
// node.branches[index].handle.node().merge = this._makeMerge();
// node.leaves[index].merge = this._makeMerge();
const merge = branches.length > 0
? node.branches[index].handle.node().merge.node()
: node.leaves[index].merge.node();
const forks = deviation.fine - merge.deviation.fine;
if (forks < 0) throw new Error("Should never see future deviation.");
while (merge._timelines.length <= forks) merge._timelines.push({});
merge._timelines[forks][deviation.coarse].reset(graph, at);
}
}
return results;
}
_zeroOrdering(
results = [new IdHandle(undefined)],
) {
for (let offset = 0; offset < results.length; offset += 1) {
const node = results[offset].node();
node.backspaces = node.width;
}
return results;
}
backspaceIds(
offset = 1, // always exclusive -- backspaces are not consumed by already "deleted" content
width = 1,
at = this._tick(),
) {
const handle = this.ordering;
const node = handle.node();
if (offset < 0) {
throw new Error("Offset must be non-negative.");
} else if (offset > node.width - node.backspaces) {
throw new Error("Offset out of bounds.");
} else if (width > offset) {
throw new Error("Backspace underflow.");
}
const vals = this._nodeBackspace(handle, offset, width, at);
if (vals.length === 2) {
const limb = this._nestOrdering(vals[0]);
const sibling = this._nestOrdering(vals[1]);
this.ordering = this._partitionOrdering([limb, sibling], [], at)[0];
} else if (vals.length === 1) {
this.ordering = vals[0];
} else {
throw new Error("Unexpected backspace root change.");
}
const deviation = this._deviation();
const graph = new IdGraph({ haystack: null });
const root = this.ordering.node();
// root.merge = this._makeMerge();
root.merge.node()._timelines[0][deviation.coarse].reset(graph, at);
this._tock();
}
_nodeBackspace(
handle = this.ordering,
offset = 1,
width = 1,
at = this._tick(),
) {
const node = handle.node();
const branches = node.branches.slice();
if (!branches.length) {
return this._leafBackspace(handle, offset, width, at);
}
if (offset === width && width === node.width - node.backspaces) {
return this._zeroOrdering(this._partitionOrdering(branches, [], at));
}
let index = 0;
let total = width;
let count = offset;
// recursively insert id into branches covering offset
for (index = 0; index < branches.length; index += 1) {
const limb = branches[index];
const quantity = limb.width - limb.backspaces;
if (count > quantity) {
count -= quantity;
continue;
}
const vals = total > quantity
? this._nodeBackspace(limb.handle, count, quantity, at)
: this._nodeBackspace(limb.handle, count, total, at);
total -= quantity;
if (vals.length === 2) {
const sibling = this._nestOrdering(vals[1]);
branches.splice(index, 1, this._nestOrdering(vals[0]), sibling);
} else if (vals.length === 1) {
branches.splice(index, 1, this._nestOrdering(vals[0]));
} else {
throw new Error("Unexpected backspacing branch change.");
}
break;
}
for (--index; total > 0 && index > -1; index -= 1) {
const limb = branches[index];
const quantity = limb.width - limb.backspaces;
const vals = total > quantity
? this._nodeBackspace(limb.handle, quantity, quantity, at)
: this._nodeBackspace(limb.handle, quantity, total, at);
total -= quantity;
if (vals.length === 2) {
const sibling = this._nestOrdering(vals[1]);
branches.splice(index, 1, this._nestOrdering(vals[0]), sibling);
} else if (vals.length === 1) {
branches.splice(index, 1, this._nestOrdering(vals[0]));
} else {
throw new Error("Unexpected backspacing branch change.");
}
}
return this._partitionOrdering(branches, [], at);
}
_leafBackspace(
handle = this.ordering,
offset = 1,
width = 1,
at = this._tick(),
) {
const node = handle.node();
const leaves = node.leaves.slice();
if (offset === width && width === node.width - node.backspaces) {
return this._zeroOrdering(this._partitionOrdering(leaves, [], at));
}
let index = 0;
let total = width;
let count = offset;
for (index = 0; index < leaves.length; index += 1) {
const stem = leaves[index];
const quantity = stem.width - stem.backspaces;
if (count > quantity) {
count -= quantity;
continue;
}
if (count === quantity) {
const ref = new RefLeaf({
backspaces: quantity > total ? stem.backspaces + total : stem.width,
width: stem.width,
id: stem.id,
merge: this._makeMerge(),
});
leaves[index] = new IdLeaf(ref);
this._writeRef(ref);
} else if (total >= count) {
let ref = new RefLeaf({
backspaces: count,
width: count,
id: stem.id,
merge: this._makeMerge(),
});
leaves.splice(index, 0, new IdLeaf(ref));
ref = this._writeRef(ref)[0];
leaves[index + 1] = new IdLeaf(ref);
} else {
let ref = new RefLeaf({
backspaces: 0,
width: count - total,
id: stem.id,
merge: this._makeMerge(),
});
leaves.splice(index, 0, new IdLeaf(ref), stem);
ref = this._writeRef(ref)[0];
ref = new RefLeaf({
backspaces: total,
width: total,
id: ref.id,
merge: this._makeMerge(),
});
leaves[index + 1] = new IdLeaf(ref);
ref = this._writeRef(ref)[0];
leaves[index + 2] = new IdLeaf(ref);
}
total -= quantity;
break;
}
for (--index; total > 0 && index > -1; index -= 1) {
const stem = leaves[index];
const quantity = stem.width - stem.backspaces;
const ref = new RefLeaf({
backspaces: total > quantity ? stem.width : stem.backspaces + total,
width: stem.width,
id: stem.id,
merge: this._makeMerge(),
});
total -= quantity;
leaves[index] = new IdLeaf(ref);
this._writeRef(ref);
}
return this._partitionOrdering([], leaves, at);
}
// TODO: compactSpace() {}
}
class UnicodeLeaf {
static offset(
utf16 = "",
size = 0,
) {
let count = 0;
let index = 0;
while (index < utf16.length && count < size) {
index += utf16.codePointAt(index) > 0xffff ? 2 : 1;
count += 1;
}
return index;
}
static amount(
utf16 = "",
) {
let count = 0;
let index = 0;
while (index < utf16.length) {
index += utf16.codePointAt(index) > 0xffff ? 2 : 1;
count += 1;
}
return count;
}
constructor({
size = 0,
utf16 = "",
} = {}) {
const count = UnicodeLeaf.amount(utf16);
if (size && size !== count) throw new Error("Unicode length incorrect.");
this.size = count;
this.utf16 = utf16;
}
static sizeReduce(
total = 0,
each = new UnicodeLeaf({}),
) {
return total + each.size;
}
static utf16Map(
each = new UnicodeLeaf({}),
) {
return each.utf16;
}
}
class UnicodeBranch {
constructor({
size = 1,
_utf16 = "",
handle = null,
} = {
handle: new UnicodeHandle(undefined),
}) {
this.size = size;
this._utf16 = String(_utf16);
this.handle = handle;
}
static sizeReduce(
total = 0,
each = new UnicodeBranch({}),
) {
return total + each.size;
}
static utf16Map(
each = new UnicodeBranch({}),
) {
if (each.size < 1) return "";
if (each._utf16.length > 0) return each._utf16;
each._utf16 = each.handle.node().utf16();
return each._utf16;
}
}
class UnicodeHandle {
constructor({
_node = null,
} = {
_node: new UnicodeNode({}),
}) {
this._node = _node;
}
node() {
return this._node;
}
}
class UnicodeNode {
constructor({
branches = [],
leaves = [],
} = {
branches: [new UnicodeBranch({})],
leaves: [new UnicodeLeaf({})],
}) {
const size = branches.length > 0
? 0|branches.reduce(UnicodeBranch.sizeReduce, 0)
: 0|leaves.reduce(UnicodeLeaf.sizeReduce, 0);
this.size = size;
this.utf16 = branches.length > 0
? size && String(branches.map(UnicodeBranch.utf16Map).join("")) || ""
: size && String(leaves.map(UnicodeLeaf.utf16Map).join("")) || "";
this.branches = branches;
this.leaves = leaves;
}
}
class SuperbUnicode {
constructor({
root = null,
} = {
root: new UnicodeHandle(undefined),
}) {
this.root = root;
}
getUTF16(
// start = 0,
// end = this.size,
) {
// if (start === 0 && end === size)
return String(this.root.node().utf16);
// TODO: compose from tree structure
}
size () {
return 0|this.root.node().size;
}
_partitionText(
branches = [new UnicodeBranch({})],
leaves = [new UnicodeLeaf({})],
) {
const LIMIT = 64;
const count = branches.length > 0 ? branches.length : leaves.length;
const handle = count <= LIMIT
? this._makeText(branches, leaves) // no need to split node
: this._makeText( // split node
branches.splice(count >> 1, 1 / 0),
leaves.splice(count >> 1, 1 / 0),
);
const results = count <= LIMIT
? [handle] // no need to split node
: [this._makeText(branches, leaves), handle]; // split node
return results;
}
_makeText(
branches = [new UnicodeBranch({})],
leaves = [new UnicodeLeaf({})],
) {
const _node = new UnicodeNode({ branches, leaves });
const handle = new UnicodeHandle({ _node });
return handle;
}
_nestText(
handle = new UnicodeHandle(undefined),
) {
const node = handle.node();
const size = node.branches.length > 0
? node.branches.reduce(UnicodeBranch.sizeReduce, 0)
: node.leaves.reduce(UnicodeLeaf.sizeReduce, 0);
const branch = new UnicodeBranch({ size, handle });
return branch;
}
insertText(
offset = 0,
text = "",
) {
if (!text) return;
const handle = this.root;
const node = handle.node();
if (offset < 0) {
throw new Error("Offset must be non-negative.");
} else if (offset > node.size) {
throw new Error("Offset out of bounds.");
}
const vals = this._nodeInsert(handle, offset, text);
if (vals.length === 2) {
const limb = this._nestText(vals[0]);
const sibling = this._nestText(vals[1]);
this.root = this._partitionText([limb, sibling], [])[0];
} else if (vals.length === 1) {
this.root = vals[0];
} else {
throw new Error("Unexpected insertion root change.");
}
}
_nodeInsert(
handle = this.root,
offset = 0,
text = "",
) {
const node = handle.node();
const branches = node.branches.slice();
if (!branches.length) {
return this._leafInsert(handle, offset, text);
}
let index = 0;
let count = offset;
// recursively insert id into branches covering offset
for (index = 0; index < branches.length; index += 1) {
const limb = branches[index];
const delta = limb.size;
if (count > delta || count === delta && index < branches.length - 1) {
count -= delta;
continue;
}
const vals = this._nodeInsert(limb.handle, count, text);
if (vals.length === 2) {
const sibling = this._nestText(vals[1]);
branches.splice(index, 1, this._nestText(vals[0]), sibling);
} else if (vals.length === 1) {
branches.splice(index, 1, this._nestText(vals[0]));
} else {
throw new Error("Unexpected insertion branch change.");
}
break;
}
if (index >= branches.length) throw new Error("Did not insert.");
else return this._partitionText(branches, [], at);
}
_leafInsert(
handle = this.root,
offset = 0,
text = "",
) {
const LIMIT = 64;
let count = offset;
const leaves = handle.node().leaves.slice();
if (count === 0) {
// insert before all existing leaves
leaves.splice(0, 0, new UnicodeLeaf({ utf16: text }));
} else {
for (let index = 0; index < leaves.length; index += 1) {
const stem = leaves[index];
if (count > stem.size) {
count -= stem.size;
continue;
}
if (stem.size < LIMIT) {
const utf16 = stem.utf16;
const at = UnicodeLeaf.offset(utf16, count);
leaves[index] = new UnicodeLeaf({
utf16: utf16.slice(0, at) + text + utf16.slice(at),
});
} else if (count !== stem.size) {
const utf16 = stem.utf16;
const at = UnicodeLeaf.offset(utf16, count);
leaves.splice(
index,
0,
new UnicodeLeaf({ utf16: utf16.slice(0, at) }),
new UnicodeLeaf({ utf16: text }),
);
leaves[index + 2] = new UnicodeLeaf({ utf16: utf16.slice(at) });
} else {
leaves.splice(index + 1, 0, new UnicodeLeaf({ utf16: text }));
}
break;
}
}
return this._partitionText([], leaves);
}
backspaceText(
offset = 1,
size = 1,
) {
if (size < 1) return;
const handle = this.root;
const node = handle.node();
if (offset < 0) {
throw new Error("Offset must be non-negative.");
} else if (offset > node.size) {
throw new Error("Offset out of bounds.");
} else if (size > offset) {
throw new Error("Backspace underflow.");
}
const vals = this._nodeBackspace(handle, offset, size);
if (vals.length === 2) {
const limb = this._nestText(vals[0]);
const sibling = this._nestText(vals[1]);
this.root = this._partitionText([limb, sibling], [])[0];
} else if (vals.length === 1) {
this.root = vals[0];
} else {
throw new Error("Unexpected backspace root change.");
}
}
_nodeBackspace(
handle = this.root,
offset = 1,
size = 1,
) {
const node = handle.node();
const branches = node.branches.slice();
if (!branches.length) {
return this._leafBackspace(handle, offset, size);
}
if (offset === size && size === node.size) {
return this._partitionText([], []);
}
let index = 0;
let total = size;
let count = offset;
// recursively insert id into branches covering offset
for (index = 0; index < branches.length; index += 1) {
const limb = branches[index];
if (count > limb.size) {
count -= limb.size;
continue;
}
const vals = total > limb.size
? this._nodeBackspace(limb.handle, count, limb.size)
: this._nodeBackspace(limb.handle, count, total);
total -= limb.size;
if (vals.length === 2) {
const sibling = this._nestText(vals[1]);
branches.splice(index, 1, this._nestText(vals[0]), sibling);
} else if (vals.length === 1) {
branches.splice(index, 1, this._nestText(vals[0]));
} else {
throw new Error("Unexpected backspacing branch change.");
}
break;
}
for (--index; total > 0 && index > -1; index -= 1) {
const limb = branches[index];
const vals = total > limb.size
? this._nodeBackspace(limb.handle, limb.size, limb.size)
: this._nodeBackspace(limb.handle, limb.size, total);
total -= limb.size;
if (vals.length === 2) {
const sibling = this._nestText(vals[1]);
branches.splice(index, 1, this._nestText(vals[0]), sibling);
} else if (vals.length === 1) {
branches.splice(index, 1, this._nestText(vals[0]));
} else {
throw new Error("Unexpected backspacing branch change.");
}
}
return this._partitionText(branches, []);
}
_leafBackspace(
handle = this.root,
offset = 1,
size = 1,
) {
const node = handle.node();
const leaves = node.leaves.slice();
if (offset === size && size === node.size) {
return this._partitionText([], []);
}
let index = 0;
let total = size;
let count = offset;
for (index = 0; index < leaves.length; index += 1) {
const stem = leaves[index];
if (count > stem.size) {
count -= stem.size;
continue;
}
if (count === stem.size) {
const utf16 = stem.utf16;
const at = stem.size > total
? UnicodeLeaf.offset(utf16, stem.size - total)
: 0;
if (at < 1) leaves.splice(index, 1); // TODO: merge nodes...
else leaves[index] = new UnicodeLeaf({ utf16: utf16.slice(0, at) });
} else if (total >= count) {
const utf16 = stem.utf16;
const at = UnicodeLeaf.offset(utf16, count);
if (at > 0) leaves[index] = new UnicodeLeaf({ utf16: utf16.slice(at) });
} else {
let utf16 = stem.utf16;
let at = UnicodeLeaf.offset(utf16, count - total);
leaves.splice(
index,
0,
new UnicodeLeaf({ utf16: utf16.slice(0, at) }),
);
utf16 = utf16.slice(at);
at = UnicodeLeaf.offset(utf16, total);
leaves[index + 1] = new UnicodeLeaf({ utf16: utf16.slice(at) });
}
total -= stem.size;
break;
}
index -= 1;
const end = index;
for (; index > -1; index -= 1) {
const stem = leaves[index];
if (stem.size > total) break;
total -= stem.size;
}
leaves.splice(index + 1, end); // TODO: merge nodes...
if (index > -1) {
const stem = leaves[index];
const utf16 = stem.utf16;
const at = UnicodeLeaf.offset(utf16, stem.size - total);
leaves[index] = new UnicodeLeaf({ utf16: utf16.slice(0, at) });
}
return this._partitionText([], leaves);
}
}
// exclusive-range: [exclusive, null, null, exclusive]
// inclusive-range: [null, inclusive, inclusive, null]
class Mutation {
XOR = {
preferences: [
{
when: [
{
zone: "#map",
assertions: [],
},
{
zone: "#queuing",
assertions: [{}],
},
],
make: [
{
zone: "#queuing",
edits: [{
from: "",
splicings: [[0, 2, 0, 0]], // [[retains, deletes, inserts, updates]] -negatives go the "left"
contents: [3, -1], // put, get, or swap index from contents array (-negative means "do not put")
}],
},
{
zone: "#map",
edits: [{
from: "id",
splicings: [[0, 0, 3, 0]],
contents: [2, 1, 0],
}],
},
],
then: [{
zone: "#queuing",
assertions: [{}],
}],
},
{
when: [{
zone: "#map",
assertions: [],
}],
make: [
{
zone: "#map",
edits: [{
from: "id",
splicings: [[0, 0, 3, 0]],
contents: [2, 1, 0],
}],
},
],
then: [{
zone: "#queuing",
assertions: [{}],
}],
},
{
when: [],
make: [{
zone: "#queuing",
edits: [{
from: "",
splicings: [[0, 0, 1, 0]],
contents: [4],
}],
}],
},
],
zones: [
"#queuing",
"#map",
],
contents: [
{ key: "", value: {} && "scalar", width: 1 },
{ key: "", value: new Uint8Array(), width: 2 } && "base64scalar",
{ key: "", value: null, width: 1 },
null,
{ key: "intent", value: {} },
],
};
}
class ValueLeaf {
constructor({
width = 1,
// [created, updated, left_altered, right_altered, left_deleted, right_deleted]
moments = [new LogicalTime({})],
value = null,
} = {}) {}
}
class ValueBranch {
constructor({
width = 0,
floors = [new LogicalTime({})],
ceilings = [new LogicalTime({})],
} = {}) {}
}
class KeyLeaf {
constructor({
width = 1, // run-length encoding-friendly
key = [""],
} = {}) {}
}
class KeyBranch {
constructor({
width = 0,
ascendding = false,
start = [""],
end = [""],
} = {}) {}
}
class TrifixLeaf {
constructor({
prefix = "",
infix = [null],
suffix = "",
} = {}) {}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment