deno.land / x / replicache@v10.0.0-beta.0 / btree / node.test.ts
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524import {expect, assert} from '@esm-bundle/chai';import * as dag from '../dag/mod';import {emptyHash, Hash} from '../hash';import {getSizeOfValue, ReadonlyJSONValue} from '../json';import { DataNode, findLeaf, InternalNode, partition, assertBTreeNode, Entry, DiffResult, DiffResultOp, NODE_LEVEL, NODE_ENTRIES, emptyDataNode, ReadonlyEntry,} from './node';import {BTreeWrite} from './write';import {makeTestChunkHasher} from '../dag/chunk';import {BTreeRead, NODE_HEADER_SIZE} from './read';
test('findLeaf', async () => { const dagStore = new dag.TestStore();
const leaf0: DataNode = [ 0, [ ['a', 0], ['b', 1], ['c', 2], ], ];
const leaf1: DataNode = [ 0, [ ['d', 3], ['e', 4], ['f', 5], ], ]; const leaf2: DataNode = [ 0, [ ['g', 6], ['h', 7], ['i', 8], ], ];
let h0: Hash, h1: Hash, h2: Hash;
let root: InternalNode; let rootHash: Hash;
await dagStore.withWrite(async dagWrite => { const c0 = dagWrite.createChunk(leaf0, []); const c1 = dagWrite.createChunk(leaf1, []); const c2 = dagWrite.createChunk(leaf2, []);
h0 = c0.hash; h1 = c1.hash; h2 = c2.hash;
root = [ 1, [ ['c', h0], ['f', h1], ['i', h2], ], ];
const rootChunk = dagWrite.createChunk(root, [h0, h1, h2]); rootHash = rootChunk.hash;
await dagWrite.putChunk(c0); await dagWrite.putChunk(c1); await dagWrite.putChunk(c2); await dagWrite.putChunk(rootChunk); await dagWrite.setHead('test', rootHash); await dagWrite.commit(); });
await dagStore.withRead(async dagRead => { const source = new BTreeRead( dagRead, rootHash, getEntrySize, chunkHeaderSize, );
const t = async ( key: string, hash: Hash, source: BTreeRead, expected: DataNode, ) => { const actual = await findLeaf(key, hash, source); expect(actual.level).to.deep.equal(expected[NODE_LEVEL]); expect(actual.entries).to.deep.equal(expected[NODE_ENTRIES]); };
await t('b', h0, source, leaf0); await t('a', h0, source, leaf0); await t('c', h0, source, leaf0);
await t('a', rootHash, source, leaf0); await t('b', rootHash, source, leaf0); await t('c', rootHash, source, leaf0); await t('d', rootHash, source, leaf1); await t('e', rootHash, source, leaf1); await t('f', rootHash, source, leaf1); await t('g', rootHash, source, leaf2); await t('h', rootHash, source, leaf2); await t('i', rootHash, source, leaf2); });});
type TreeData = { $level: number; [key: string]: TreeData | ReadonlyJSONValue;};
function makeTree(node: TreeData, dagStore: dag.Store): Promise<Hash> { return dagStore.withWrite(async dagWrite => { const [h] = await makeTreeInner(node, dagWrite); await dagWrite.setHead('test', h); await dagWrite.commit(); return h; });
async function makeTreeInner( node: TreeData, dagWrite: dag.Write, ): Promise<[Hash, number]> { const entries: [string, ReadonlyJSONValue | string][] = Object.entries( node, ).filter(e => e[0] !== '$level'); if (node.$level === 0) { const dataNode: DataNode = [0, entries]; const chunk = dagWrite.createChunk(dataNode, []); await dagWrite.putChunk(chunk); return [chunk.hash, 0]; }
let level = 0; const ps = entries.map(async ([key, child]) => { const [hash, lvl] = await makeTreeInner(child as TreeData, dagWrite); level = Math.max(level, lvl); return [key, hash] as [string, Hash]; }); const entries2 = await Promise.all(ps);
const internalNode: InternalNode = [level + 1, entries2]; const refs = entries2.map(pair => pair[1]); const chunk = dagWrite.createChunk(internalNode, refs); await dagWrite.putChunk(chunk); return [chunk.hash, level + 1]; }}
async function readTreeData( rootHash: Hash, dagRead: dag.Read,): Promise<Record<string, ReadonlyJSONValue>> { const chunk = await dagRead.getChunk(rootHash); const node = chunk?.data; assertBTreeNode(node); let lastKey: string | undefined; const rv: Record<string, ReadonlyJSONValue> = { $level: node[NODE_LEVEL], };
if (node[NODE_LEVEL] === 0) { for (const [k, v] of node[NODE_ENTRIES]) { if (lastKey !== undefined) { assert(lastKey < k); lastKey = k; } rv[k] = v; } return rv; }
for (const [k, hash] of (node as InternalNode)[NODE_ENTRIES]) { if (lastKey !== undefined) { expect(lastKey < k); lastKey = k; } rv[k] = await readTreeData(hash, dagRead); } return rv;}
async function expectTree( rootHash: Hash, dagStore: dag.Store, expected: TreeData,) { await dagStore.withRead(async dagRead => { expect(await readTreeData(rootHash, dagRead)).to.deep.equal(expected); });}
let minSize: number;let maxSize: number;let getEntrySize: <T>(e: Entry<T>) => number;let chunkHeaderSize: number;
setup(() => { minSize = 2; maxSize = 4; getEntrySize = () => 1; chunkHeaderSize = 0;});
function doRead<R>( rootHash: Hash, dagStore: dag.Store, fn: (r: BTreeRead) => R | Promise<R>,): Promise<R> { return dagStore.withRead(async dagWrite => { const r = new BTreeRead(dagWrite, rootHash, getEntrySize, chunkHeaderSize); return await fn(r); });}
function doWrite( rootHash: Hash, dagStore: dag.Store, fn: (w: BTreeWrite) => void | Promise<void>,): Promise<Hash> { return dagStore.withWrite(async dagWrite => { const w = new BTreeWrite( dagWrite, rootHash, minSize, maxSize, getEntrySize, chunkHeaderSize, ); await fn(w); const h = await w.flush(); await dagWrite.setHead('test', h); await dagWrite.commit(); return h; });}
async function asyncIterToArray<T>(iter: AsyncIterable<T>): Promise<T[]> { const rv: T[] = []; for await (const e of iter) { rv.push(e); } return rv;}
test('empty read tree', async () => { const dagStore = new dag.TestStore(); await dagStore.withRead(async dagRead => { const r = new BTreeRead(dagRead); expect(await r.get('a')).to.be.undefined; expect(await r.has('b')).to.be.false; expect(await asyncIterToArray(r.scan(''))).to.deep.equal([]); });});
test('empty write tree', async () => { const chunkHasher = makeTestChunkHasher('tree'); const dagStore = new dag.TestStore(undefined, chunkHasher);
const emptyTreeHash = chunkHasher(emptyDataNode);
await dagStore.withWrite(async dagWrite => { const w = new BTreeWrite( dagWrite, undefined, minSize, maxSize, getEntrySize, chunkHeaderSize, ); expect(await w.get('a')).to.be.undefined; expect(await w.has('b')).to.be.false; expect(await asyncIterToArray(w.scan(''))).to.deep.equal([]);
const h = await w.flush(); expect(h).to.equal(emptyTreeHash); }); let rootHash = await dagStore.withWrite(async dagWrite => { const w = new BTreeWrite( dagWrite, undefined, minSize, maxSize, getEntrySize, chunkHeaderSize, ); await w.put('a', 1); const h = await w.flush(); expect(h).to.not.equal(emptyHash); expect(h).to.not.equal(emptyTreeHash); await dagWrite.setHead('test', h); await dagWrite.commit(); return h; });
rootHash = await doWrite(rootHash, dagStore, async w => { expect(await w.del('a')).to.be.true; });
// We do not restore back to empty hash when empty. expect(rootHash).to.not.equal(emptyHash); expect(rootHash).to.equal(emptyTreeHash);});
test('get', async () => { const dagStore = new dag.TestStore();
const tree: TreeData = { $level: 1, f: { $level: 0, b: 0, d: 1, f: 2, }, l: { $level: 0, h: 3, j: 4, l: 5, }, r: { $level: 0, n: 6, p: 7, r: 8, }, };
const rootHash = await makeTree(tree, dagStore);
await dagStore.withRead(async dagRead => { const source = new BTreeRead( dagRead, rootHash, getEntrySize, chunkHeaderSize, );
expect(await source.get('b')).to.equal(0); expect(await source.get('d')).to.equal(1); expect(await source.get('f')).to.equal(2); expect(await source.get('h')).to.equal(3); expect(await source.get('j')).to.equal(4); expect(await source.get('l')).to.equal(5); expect(await source.get('n')).to.equal(6); expect(await source.get('p')).to.equal(7); expect(await source.get('r')).to.equal(8);
expect(await source.get('a')).to.equal(undefined); expect(await source.get('c')).to.equal(undefined); expect(await source.get('e')).to.equal(undefined); expect(await source.get('g')).to.equal(undefined); expect(await source.get('i')).to.equal(undefined); expect(await source.get('k')).to.equal(undefined); expect(await source.get('m')).to.equal(undefined); expect(await source.get('o')).to.equal(undefined); expect(await source.get('q')).to.equal(undefined); expect(await source.get('s')).to.equal(undefined); });});
test('has', async () => { const dagStore = new dag.TestStore();
const tree: TreeData = { $level: 1, f: { $level: 0, b: 0, d: 1, f: 2, }, l: { $level: 0, h: 3, j: 4, l: 5, }, r: { $level: 0, n: 6, p: 7, r: 8, }, };
const rootHash = await makeTree(tree, dagStore);
await dagStore.withRead(async dagRead => { const source = new BTreeRead( dagRead, rootHash, getEntrySize, chunkHeaderSize, );
expect(await source.has('b')).to.be.true; expect(await source.has('d')).to.be.true; expect(await source.has('f')).to.be.true; expect(await source.has('h')).to.be.true; expect(await source.has('j')).to.be.true; expect(await source.has('l')).to.be.true; expect(await source.has('n')).to.be.true; expect(await source.has('p')).to.be.true; expect(await source.has('r')).to.be.true;
expect(await source.has('a')).to.be.false; expect(await source.has('c')).to.be.false; expect(await source.has('e')).to.be.false; expect(await source.has('g')).to.be.false; expect(await source.has('i')).to.be.false; expect(await source.has('k')).to.be.false; expect(await source.has('m')).to.be.false; expect(await source.has('o')).to.be.false; expect(await source.has('q')).to.be.false; expect(await source.has('s')).to.be.false; });});
test('partition', () => { const getSize = (v: string) => v.length;
const t = (input: string[], expected: string[][]) => { expect(partition(input, getSize, 2, 4)).to.deep.equal(expected); };
t([], []); t(['a'], [['a']]); t(['a', 'b'], [['a', 'b']]); t(['a', 'b', 'c'], [['a', 'b', 'c']]); t( ['a', 'b', 'c', 'd'], [ ['a', 'b'], ['c', 'd'], ], ); t( ['a', 'b', 'c', 'd', 'e'], [ ['a', 'b'], ['c', 'd', 'e'], ], ); t( ['a', 'b', 'c', 'd', 'e', 'f'], [ ['a', 'b'], ['c', 'd'], ['e', 'f'], ], ); t(['ab'], [['ab']]); t(['ab', 'cd'], [['ab'], ['cd']]); t(['ab', 'cd', 'ef'], [['ab'], ['cd'], ['ef']]); t(['ab', 'cd', 'e'], [['ab'], ['cd', 'e']]); t(['ab', 'c', 'de'], [['ab'], ['c', 'de']]); t(['a', 'bc', 'de'], [['a', 'bc'], ['de']]); t(['abc', 'de'], [['abc'], ['de']]); t(['abc', 'def'], [['abc'], ['def']]); t(['a', 'bcd', 'e'], [['a', 'bcd'], ['e']]); t(['ab', 'cde', 'f'], [['ab'], ['cde', 'f']]); t(['abc', 'd', 'efg'], [['abc'], ['d', 'efg']]); t(['abcd', 'e', 'f'], [['abcd'], ['e', 'f']]); t(['a', 'bcde', 'f'], [['a'], ['bcde'], ['f']]); t(['a', 'bcdef', 'g'], [['a'], ['bcdef'], ['g']]);});
test('put', async () => { const dagStore = new dag.TestStore();
const tree: TreeData = { $level: 0, b: 0, d: 1, f: 2, };
let rootHash = await makeTree(tree, dagStore);
rootHash = await doWrite(rootHash, dagStore, async w => { await w.put('a', 'aaa');
expect(await w.get('a')).to.equal('aaa'); expect(await w.get('b')).to.equal(0); await w.put('b', 'bbb'); expect(await w.get('b')).to.equal('bbb'); });
await expectTree(rootHash, dagStore, { $level: 0, a: 'aaa', b: 'bbb', d: 1, f: 2, });
rootHash = await doWrite(rootHash, dagStore, async w => { await w.put('c', 'ccc'); expect(await w.get('a')).to.equal('aaa'); expect(await w.get('b')).to.equal('bbb'); expect(await w.get('c')).to.equal('ccc'); });
await expectTree(rootHash, dagStore, { $level: 1, b: { $level: 0, a: 'aaa', b: 'bbb', }, f: { $level: 0, c: 'ccc', d: 1, f: 2, }, });
async function write(data: Record<string, ReadonlyJSONValue>) { rootHash = await dagStore.withWrite(async dagWrite => { const w = new BTreeWrite( dagWrite, rootHash, minSize, maxSize, getEntrySize, chunkHeaderSize, ); for (const [k, v] of Object.entries(data)) { await w.put(k, v); expect(await w.get(k)).to.equal(v); expect(await w.has(k)).to.equal(true); } const h = await w.flush(); for (const [k, v] of Object.entries(data)) { expect(await w.get(k)).to.equal(v); expect(await w.has(k)).to.equal(true); }
await dagWrite.setHead('test', h); await dagWrite.commit();
for (const [k, v] of Object.entries(data)) { expect(await w.get(k)).to.equal(v); expect(await w.has(k)).to.equal(true); }
return h; }); }
await write({ e: 'eee', f: 'fff', g: 'ggg', h: 'hhh', i: 'iii', j: 'jjj', }); await expectTree(rootHash, dagStore, { $level: 1, b: { $level: 0, a: 'aaa', b: 'bbb', }, d: { $level: 0, c: 'ccc', d: 1, }, f: { $level: 0, e: 'eee', f: 'fff', }, j: { $level: 0, g: 'ggg', h: 'hhh', i: 'iii', j: 'jjj', }, });
await write({ k: 'kkk', }); await expectTree(rootHash, dagStore, { $level: 2, d: { $level: 1, b: { $level: 0, a: 'aaa', b: 'bbb', }, d: { $level: 0, c: 'ccc', d: 1, }, }, k: { $level: 1, f: { $level: 0, e: 'eee', f: 'fff', }, h: { $level: 0, g: 'ggg', h: 'hhh', }, k: { $level: 0, i: 'iii', j: 'jjj', k: 'kkk', }, }, });
await write({ q: 'qqq', m: 'mmm', l: 'lll', p: 'ppp', o: 'ooo', n: 'nnn', }); await expectTree(rootHash, dagStore, { $level: 2, d: { $level: 1, b: { $level: 0, a: 'aaa', b: 'bbb', }, d: { $level: 0, c: 'ccc', d: 1, }, }, h: { $level: 1, f: { $level: 0, e: 'eee', f: 'fff', }, h: { $level: 0, g: 'ggg', h: 'hhh', }, }, q: { $level: 1, j: { $level: 0, i: 'iii', j: 'jjj', }, l: { $level: 0, k: 'kkk', l: 'lll', }, n: { $level: 0, m: 'mmm', n: 'nnn', }, q: { $level: 0, o: 'ooo', p: 'ppp', q: 'qqq', }, }, });
await write({ boo: '👻', }); await expectTree(rootHash, dagStore, { $level: 2, d: { $level: 1, b: { $level: 0, a: 'aaa', b: 'bbb', }, d: { $level: 0, boo: '👻', c: 'ccc', d: 1, }, }, h: { $level: 1, f: { $level: 0, e: 'eee', f: 'fff', }, h: { $level: 0, g: 'ggg', h: 'hhh', }, }, q: { $level: 1, j: { $level: 0, i: 'iii', j: 'jjj', }, l: { $level: 0, k: 'kkk', l: 'lll', }, n: { $level: 0, m: 'mmm', n: 'nnn', }, q: { $level: 0, o: 'ooo', p: 'ppp', q: 'qqq', }, }, });
await write({ bx: true, bx2: false, }); await expectTree(rootHash, dagStore, { $level: 2, d: { $level: 1, b: { $level: 0, a: 'aaa', b: 'bbb', }, bx: { $level: 0, boo: '👻', bx: true, }, d: { $level: 0, bx2: false, c: 'ccc', d: 1, }, }, h: { $level: 1, f: { $level: 0, e: 'eee', f: 'fff', }, h: { $level: 0, g: 'ggg', h: 'hhh', }, }, q: { $level: 1, j: { $level: 0, i: 'iii', j: 'jjj', }, l: { $level: 0, k: 'kkk', l: 'lll', }, n: { $level: 0, m: 'mmm', n: 'nnn', }, q: { $level: 0, o: 'ooo', p: 'ppp', q: 'qqq', }, }, });});
test('del - single data node', async () => { const dagStore = new dag.TestStore();
const tree: TreeData = { $level: 0, b: 0, d: 1, f: 2, };
let rootHash = await makeTree(tree, dagStore);
rootHash = await doWrite(rootHash, dagStore, async w => { expect(await w.del('a')).to.equal(false); expect(await w.del('d')).to.equal(true); });
await expectTree(rootHash, dagStore, { $level: 0, b: 0, f: 2, });
rootHash = await doWrite(rootHash, dagStore, async w => { expect(await w.del('f')).to.equal(true); });
await expectTree(rootHash, dagStore, { $level: 0, b: 0, });
rootHash = await doWrite(rootHash, dagStore, async w => { expect(await w.del('b')).to.equal(true); });
await expectTree(rootHash, dagStore, { $level: 0, });});
test('del - flatten', async () => { const dagStore = new dag.TestStore();
// This tests that we can flatten "an invalid tree"
{ const tree: TreeData = { $level: 3, b: { $level: 2, b: { $level: 1, b: { $level: 0, a: 'aaa', b: 'bbb', }, }, }, };
let rootHash = await makeTree(tree, dagStore);
rootHash = await doWrite(rootHash, dagStore, async w => { expect(await w.del('a')).to.equal(true); });
await expectTree(rootHash, dagStore, { $level: 0, b: 'bbb', }); }
{ const tree: TreeData = { $level: 3, b: { $level: 2, b: { $level: 1, b: { $level: 0, a: 'aaa', b: 'bbb', }, }, }, };
let rootHash = await makeTree(tree, dagStore);
rootHash = await doWrite(rootHash, dagStore, async w => { expect(await w.del('b')).to.equal(true); });
await expectTree(rootHash, dagStore, { $level: 0, a: 'aaa', }); }});
test('del - with internal nodes', async () => { const dagStore = new dag.TestStore();
const tree: TreeData = { $level: 2, d: { $level: 1, b: { $level: 0, a: 'aaa', b: 'bbb', }, d: { $level: 0, c: 'ccc', d: 'ddd', }, }, k: { $level: 1, f: { $level: 0, e: 'eee', f: 'fff', }, h: { $level: 0, g: 'ggg', h: 'hhh', }, k: { $level: 0, i: 'iii', j: 'jjj', k: 'kkk', }, }, };
let rootHash = await makeTree(tree, dagStore);
rootHash = await doWrite(rootHash, dagStore, async w => { expect(await w.del('k')).to.equal(true); });
await expectTree(rootHash, dagStore, { $level: 2, d: { $level: 1, b: { $level: 0, a: 'aaa', b: 'bbb', }, d: { $level: 0, c: 'ccc', d: 'ddd', }, }, j: { $level: 1, f: { $level: 0, e: 'eee', f: 'fff', }, h: { $level: 0, g: 'ggg', h: 'hhh', }, j: { $level: 0, i: 'iii', j: 'jjj', }, }, });
rootHash = await doWrite(rootHash, dagStore, async w => { expect(await w.del('c')).to.equal(true); });
await expectTree(rootHash, dagStore, { $level: 2, f: { $level: 1, d: { $level: 0, a: 'aaa', b: 'bbb', d: 'ddd', }, f: { $level: 0, e: 'eee', f: 'fff', }, }, j: { $level: 1, h: { $level: 0, g: 'ggg', h: 'hhh', }, j: { $level: 0, i: 'iii', j: 'jjj', }, }, });
rootHash = await doWrite(rootHash, dagStore, async w => { expect(await w.del('e')).to.equal(true); expect(await w.del('f')).to.equal(true); expect(await w.del('g')).to.equal(true); expect(await w.del('h')).to.equal(true); });
await expectTree(rootHash, dagStore, { $level: 1, d: { $level: 0, a: 'aaa', b: 'bbb', d: 'ddd', }, j: { $level: 0, i: 'iii', j: 'jjj', }, });
rootHash = await doWrite(rootHash, dagStore, async w => { expect(await w.del('a')).to.equal(true); expect(await w.del('b')).to.equal(true); });
await expectTree(rootHash, dagStore, { $level: 0, d: 'ddd', i: 'iii', j: 'jjj', });
rootHash = await doWrite(rootHash, dagStore, async w => { expect(await w.del('i')).to.equal(true); expect(await w.del('j')).to.equal(true); });
await expectTree(rootHash, dagStore, { $level: 0, d: 'ddd', });
rootHash = await doWrite(rootHash, dagStore, async w => { expect(await w.del('d')).to.equal(true); });
await expectTree(rootHash, dagStore, { $level: 0, });});
test('put - invalid', async () => { const dagStore = new dag.TestStore();
// This tests that we can do puts on "an invalid tree"
const tree: TreeData = { $level: 2, b: { $level: 2, b: { $level: 0, b: 'bbb', }, }, };
let rootHash = await makeTree(tree, dagStore);
rootHash = await doWrite(rootHash, dagStore, async w => { await w.put('c', 'ccc'); });
await expectTree(rootHash, dagStore, { $level: 2, c: { $level: 1, c: { $level: 0, b: 'bbb', c: 'ccc', }, }, });});
test('put/del - getSize', async () => { minSize = 24; maxSize = minSize * 2; getEntrySize = getSizeOfValue;
const dagStore = new dag.TestStore();
// This tests that we can do puts on "an invalid tree"
const tree: TreeData = { $level: 0, };
let rootHash = await makeTree(tree, dagStore);
rootHash = await doWrite(rootHash, dagStore, async w => { await w.put('aaaa', 'a1'); });
expect(getSizeOfValue('aaaa')).to.equal(9); expect(getSizeOfValue('a1')).to.equal(7); expect(getEntrySize(['aaaa', 'a1'])).to.equal(22); await expectTree(rootHash, dagStore, { $level: 0, aaaa: 'a1', });
rootHash = await doWrite(rootHash, dagStore, async w => { await w.put('c', ''); }); expect(getEntrySize(['c', ''])).to.equal(17); await expectTree(rootHash, dagStore, { $level: 0, aaaa: 'a1', c: '', });
rootHash = await doWrite(rootHash, dagStore, async w => { await w.put('b', 'b234'); }); expect(getEntrySize(['b', 'b234'])).to.equal(21); await expectTree(rootHash, dagStore, { $level: 1,
b: { $level: 0, aaaa: 'a1', b: 'b234', }, c: { $level: 0, c: '', }, });
rootHash = await doWrite(rootHash, dagStore, async w => { await w.del('b'); }); await expectTree(rootHash, dagStore, { $level: 0, aaaa: 'a1', c: '', });});
test('scan', async () => { const t = async ( entries: Entry<ReadonlyJSONValue>[], fromKey = '', expectedEntries = entries, ) => { const dagStore = new dag.TestStore();
const tree: TreeData = { $level: 0, };
let rootHash = await makeTree(tree, dagStore);
rootHash = await doWrite(rootHash, dagStore, async w => { for (const [k, v] of entries) { await w.put(k, v); } });
await doRead(rootHash, dagStore, async r => { const res: ReadonlyEntry<ReadonlyJSONValue>[] = []; const scanResult = r.scan(fromKey); for await (const e of scanResult) { res.push(e); } expect(res).to.deep.equal(expectedEntries); }); };
await t([]); await t([['a', 1]]); await t([ ['a', 1], ['b', 2], ]); await t([ ['a', 1], ['b', 2], ['c', 3], ]); await t([ ['a', 1], ['b', 2], ['c', 3], ['d', 4], ]); await t([ ['a', 1], ['b', 2], ['c', 3], ['d', 4], ['e', 5], ]);
await t( [ ['a', 0], ['aa', 1], ['aaa', 2], ['aab', 3], ['ab', 4], ['b', 5], ], 'aa', [ ['aa', 1], ['aaa', 2], ['aab', 3], ['ab', 4], ['b', 5], ], );
await t( [ ['a', 1], ['b', 2], ['c', 3], ['d', 4], ['e', 5], ], 'f', [], );
await t( [ ['a', 1], ['b', 2], ['c', 3], ['d', 4], ['e', 5], ], 'e', [['e', 5]], );});
test('diff', async () => { const t = async ( oldEntries: Entry<ReadonlyJSONValue>[], newEntries: Entry<ReadonlyJSONValue>[], expectedDiff: DiffResult<ReadonlyJSONValue>[], ) => { const dagStore = new dag.TestStore();
const [oldHash, newHash] = await dagStore.withWrite(async dagWrite => { const oldTree = new BTreeWrite( dagWrite, undefined, minSize, maxSize, getEntrySize, chunkHeaderSize, ); for (const entry of oldEntries) { await oldTree.put(entry[0], entry[1]); }
const newTree = new BTreeWrite( dagWrite, undefined, minSize, maxSize, getEntrySize, chunkHeaderSize, ); for (const entry of newEntries) { await newTree.put(entry[0], entry[1]); }
const oldHash = await oldTree.flush(); const newHash = await newTree.flush();
await dagWrite.setHead('test/old', oldHash); await dagWrite.setHead('test/new', newHash); await dagWrite.commit();
return [oldHash, newHash]; });
await dagStore.withRead(async dagRead => { const oldTree = new BTreeRead( dagRead, oldHash, getEntrySize, chunkHeaderSize, ); const newTree = new BTreeRead( dagRead, newHash, getEntrySize, chunkHeaderSize, );
const actual = []; for await (const diffRes of newTree.diff(oldTree)) { actual.push(diffRes); } expect(actual).to.deep.equal(expectedDiff); }); };
await t([], [], []);
await t([['a', 0]], [], [{op: DiffResultOp.Delete, key: 'a', oldValue: 0}]); await t([], [['a', 0]], [{op: DiffResultOp.Add, key: 'a', newValue: 0}]); await t([['a', 0]], [['a', 0]], []); await t( [['a', 0]], [['a', 1]], [{op: DiffResultOp.Change, key: 'a', oldValue: 0, newValue: 1}], );
await t( [ ['b', 1], ['d', 2], ], [ ['d', 2], ['f', 3], ], [ {op: DiffResultOp.Delete, key: 'b', oldValue: 1}, {op: DiffResultOp.Add, key: 'f', newValue: 3}, ], );
await t( [ ['b', 1], ['d', 2], ['e', 4], ], [ ['d', 22], ['f', 3], ], [ {op: DiffResultOp.Delete, key: 'b', oldValue: 1}, {op: DiffResultOp.Change, key: 'd', oldValue: 2, newValue: 22}, {op: DiffResultOp.Delete, key: 'e', oldValue: 4}, {op: DiffResultOp.Add, key: 'f', newValue: 3}, ], );
await t( [ ['b', 1], ['d', 2], ['e', 4], ['h', 5], ['i', 6], ['j', 7], ['k', 8], ['l', 9], ], [ ['d', 22], ['f', 3], ], [ {op: DiffResultOp.Delete, key: 'b', oldValue: 1}, {op: DiffResultOp.Change, key: 'd', oldValue: 2, newValue: 22}, {op: DiffResultOp.Delete, key: 'e', oldValue: 4}, {op: DiffResultOp.Add, key: 'f', newValue: 3},
{op: DiffResultOp.Delete, key: 'h', oldValue: 5}, {op: DiffResultOp.Delete, key: 'i', oldValue: 6}, {op: DiffResultOp.Delete, key: 'j', oldValue: 7}, {op: DiffResultOp.Delete, key: 'k', oldValue: 8}, {op: DiffResultOp.Delete, key: 'l', oldValue: 9}, ], );
await t( [ ['b', 1], ['b1', 11], ['d', 2], ['d1', 12], ['e', 4], ['e1', 14], ['h', 5], ['h1', 15], ['i', 6], ['i1', 16], ['j', 7], ['j1', 17], ['k', 8], ['k1', 18], ['l', 9], ['l1', 19], ], [ ['l1', 19], ['l', 9], ['k1', 18], // ['k', 8], ['j1', 17], ['j', 7], ['i1', 16], ['i', 6], ['h1', 15], ['h', 5], ['e1', 141], ['e', 0], ['d1', 0], ['d', 0], ['b2', 0], ['b1', 0], ['b', 1], ], [ { key: 'b1', newValue: 0, oldValue: 11, op: DiffResultOp.Change, }, { key: 'b2', newValue: 0, op: DiffResultOp.Add, }, { key: 'd', newValue: 0, oldValue: 2, op: DiffResultOp.Change, }, { key: 'd1', newValue: 0, oldValue: 12, op: DiffResultOp.Change, }, { key: 'e', newValue: 0, oldValue: 4, op: DiffResultOp.Change, }, { key: 'e1', newValue: 141, oldValue: 14, op: DiffResultOp.Change, }, { key: 'k', oldValue: 8, op: DiffResultOp.Delete, }, ], );});
test('chunk header size', () => { // This just ensures that the constant is correct. const chunkData: DataNode = [0, []]; const entriesSize = getSizeOfValue(chunkData[NODE_ENTRIES]); const chunkSize = getSizeOfValue(chunkData); expect(chunkSize - entriesSize).to.equal(NODE_HEADER_SIZE);});
Version Info