All files / json-crdt-diff JsonCrdtDiff.ts

94.11% Statements 160/170
81.81% Branches 54/66
100% Functions 17/17
97.88% Lines 139/142

Press n or j to go to the next uncovered block, b, p or k for the previous block.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216174x 174x 174x 174x 174x 174x 174x 174x 174x     174x   267x       174x     2304x 2304x       6696x 6696x 22x 22x     40x 26x         4x 4x 3x 3x     2x 2x         1968x 1968x 8394x   1968x 1968x 8370x 1968x 1968x 124x 124x 124x 124x 705x 705x   106x   163x 163x 163x 163x 163x     187x 187x 187x 187x     249x 249x 249x   8x 8x 8x 8x 8x 8x           124x 124x 124x 171x 171x     171x     124x       3712x 3712x 3712x   3712x 35003x 35003x 35003x   3712x 3712x 3712x 34990x 34990x 34990x 21056x 21056x 21056x 21056x 21034x   22x       13956x   3712x       8x 8x 8x 8x 8x 8x 8x 8x 2x 2x 2x 2x 2x 1x     7x 8x 8x 8x 8x 8x 7x   1x     1x   7x 7x       2494x 2494x   236x 236x 236x           26099x 11206x 11206x 14893x 6701x 6696x 8192x 3713x 3712x 4479x 2494x 1985x 1973x 1968x 12x 8x 8x 4x 4x 4x             2292x 2292x      
import {deepEqual} from '@jsonjoy.com/util/lib/json-equal/deepEqual';
import {cmpUint8Array} from '@jsonjoy.com/util/lib/buffers/cmpUint8Array';
import {type ITimespanStruct, type ITimestampStruct, type Patch, PatchBuilder} from '../json-crdt-patch';
import {ArrNode, BinNode, ConNode, ObjNode, StrNode, ValNode, VecNode, type JsonNode} from '../json-crdt/nodes';
import * as str from '../util/diff/str';
import * as bin from '../util/diff/bin';
import * as line from '../util/diff/line';
import {structHashCrdt} from '../json-hash/structHashCrdt';
import {structHash} from '../json-hash';
import type {Model} from '../json-crdt/model';
 
export class DiffError extends Error {
  constructor(message: string = 'DIFF') {
    super(message);
  }
}
 
export class JsonCrdtDiff {
  protected builder: PatchBuilder;
 
  public constructor(protected readonly model: Model<any>) {
    this.builder = new PatchBuilder(model.clock.clone());
  }
 
  protected diffStr(src: StrNode, dst: string): void {
    const view = src.view();
    if (view === dst) return;
    const builder = this.builder;
    str.apply(
      str.diff(view, dst),
      view.length,
      (pos, txt) => builder.insStr(src.id, !pos ? src.id : src.find(pos - 1)!, txt),
      (pos, len) => builder.del(src.id, src.findInterval(pos, len)),
    );
  }
 
  protected diffBin(src: BinNode, dst: Uint8Array): void {
    const view = src.view();
    if (cmpUint8Array(view, dst)) return;
    const builder = this.builder;
    bin.apply(
      bin.diff(view, dst),
      view.length,
      (pos, txt) => builder.insBin(src.id, !pos ? src.id : src.find(pos - 1)!, txt),
      (pos, len) => builder.del(src.id, src.findInterval(pos, len)),
    );
  }
 
  protected diffArr(src: ArrNode, dst: unknown[]): void {
    const srcLines: string[] = [];
    src.children((node) => {
      srcLines.push(structHashCrdt(node));
    });
    const dstLines: string[] = [];
    const dstLength = dst.length;
    for (let i = 0; i < dstLength; i++) dstLines.push(structHash(dst[i]));
    const linePatch = line.diff(srcLines, dstLines);
    if (!linePatch.length) return;
    const inserts: [after: ITimestampStruct, views: unknown[]][] = [];
    const deletes: ITimespanStruct[] = [];
    const patchLength = linePatch.length;
    for (let i = patchLength - 1; i >= 0; i--) {
      const [type, posSrc, posDst] = linePatch[i];
      switch (type) {
        case line.LINE_PATCH_OP_TYPE.EQL:
          break;
        case line.LINE_PATCH_OP_TYPE.INS: {
          const view = dst[posDst];
          const after = posSrc >= 0 ? src.find(posSrc) : src.id;
          Iif (!after) throw new DiffError();
          inserts.push([after, [view]]);
          break;
        }
        case line.LINE_PATCH_OP_TYPE.DEL: {
          const span = src.findInterval(posSrc, 1);
          Iif (!span || !span.length) throw new DiffError();
          deletes.push(...span);
          break;
        }
        case line.LINE_PATCH_OP_TYPE.MIX: {
          const view = dst[posDst];
          try {
            this.diffAny(src.getNode(posSrc)!, view);
          } catch (error) {
            if (error instanceof DiffError) {
              const span = src.findInterval(posSrc, 1)!;
              deletes.push(...span);
              const after = posSrc ? src.find(posSrc - 1) : src.id;
              Iif (!after) throw new DiffError();
              inserts.push([after, [view]]);
            } else Ethrow error;
          }
        }
      }
    }
    const builder = this.builder;
    const length = inserts.length;
    for (let i = 0; i < length; i++) {
      const [after, views] = inserts[i];
      builder.insArr(
        src.id,
        after,
        views.map((view) => builder.json(view)),
      );
    }
    if (deletes.length) builder.del(src.id, deletes);
  }
 
  protected diffObj(src: ObjNode, dst: Record<string, unknown>): void {
    const builder = this.builder;
    const inserts: [key: string, value: ITimestampStruct][] = [];
    const srcKeys = new Set<string>();
    // biome-ignore lint: .forEach is fastest here
    src.forEach((key) => {
      srcKeys.add(key);
      const dstValue = dst[key];
      if (dstValue === void 0) inserts.push([key, builder.con(undefined)]);
    });
    const keys = Object.keys(dst);
    const length = keys.length;
    for (let i = 0; i < length; i++) {
      const key = keys[i];
      const dstValue = dst[key];
      if (srcKeys.has(key)) {
        const child = src.get(key);
        if (child) {
          try {
            this.diffAny(child, dstValue);
            continue;
          } catch (error) {
            Iif (!(error instanceof DiffError)) throw error;
          }
        }
      }
      inserts.push([key, src.get(key) instanceof ConNode ? builder.con(dstValue) : builder.constOrJson(dstValue)]);
    }
    if (inserts.length) builder.insObj(src.id, inserts);
  }
 
  protected diffVec(src: VecNode, dst: unknown[]): void {
    const builder = this.builder;
    const edits: [key: number, value: ITimestampStruct][] = [];
    const elements = src.elements;
    const srcLength = elements.length;
    const dstLength = dst.length;
    const index = src.doc.index;
    const min = Math.min(srcLength, dstLength);
    for (let i = dstLength; i < srcLength; i++) {
      const id = elements[i];
      if (id) {
        const child = index.get(id);
        const isDeleted = !child || (child instanceof ConNode && child.val === void 0);
        if (isDeleted) return;
        edits.push([i, builder.con(void 0)]);
      }
    }
    for (let i = 0; i < min; i++) {
      const value = dst[i];
      const child = src.get(i);
      if (child) {
        try {
          this.diffAny(child, value);
          continue;
        } catch (error) {
          Iif (!(error instanceof DiffError)) throw error;
        }
      }
      edits.push([i, builder.constOrJson(value)]);
    }
    for (let i = srcLength; i < dstLength; i++) edits.push([i, builder.constOrJson(dst[i])]);
    if (edits.length) builder.insVec(src.id, edits);
  }
 
  protected diffVal(src: ValNode, dst: unknown): void {
    try {
      this.diffAny(src.node(), dst);
    } catch (error) {
      if (error instanceof DiffError) {
        const builder = this.builder;
        builder.setVal(src.id, builder.constOrJson(dst));
      } else Ethrow error;
    }
  }
 
  protected diffAny(src: JsonNode, dst: unknown): void {
    if (src instanceof ConNode) {
      const val = src.val;
      if (val !== dst && !deepEqual(src.val, dst)) throw new DiffError();
    } else if (src instanceof StrNode) {
      if (typeof dst !== 'string') throw new DiffError();
      this.diffStr(src, dst);
    } else if (src instanceof ObjNode) {
      if (!dst || typeof dst !== 'object' || Array.isArray(dst)) throw new DiffError();
      this.diffObj(src, dst as Record<string, unknown>);
    } else if (src instanceof ValNode) {
      this.diffVal(src, dst);
    } else if (src instanceof ArrNode) {
      if (!Array.isArray(dst)) throw new DiffError();
      this.diffArr(src, dst as unknown[]);
    } else if (src instanceof VecNode) {
      Iif (!Array.isArray(dst)) throw new DiffError();
      this.diffVec(src, dst as unknown[]);
    } else if (src instanceof BinNode) {
      Iif (!(dst instanceof Uint8Array)) throw new DiffError();
      this.diffBin(src, dst);
    } else E{
      throw new DiffError();
    }
  }
 
  public diff(src: JsonNode, dst: unknown): Patch {
    this.diffAny(src, dst);
    return this.builder.flush();
  }
}