系統設計

1type Op = { kind: "ins" | "del" | "noop"; pos: number; ch?: string; site: string };
2 
3// a, rewritten to apply after b, when both were made on the same text.
4function transform(a: Op, b: Op): Op {
5  if (a.kind === "noop" || b.kind === "noop") return a;
6  if (a.kind === "ins" && b.kind === "ins") {
7    const first = a.pos < b.pos || (a.pos === b.pos && a.site < b.site);
8    return first ? a : { ...a, pos: a.pos + 1 };
9  }
10  if (a.kind === "ins") return a.pos <= b.pos ? a : { ...a, pos: a.pos - 1 };
11  if (b.kind === "ins") return a.pos < b.pos ? a : { ...a, pos: a.pos + 1 };
12  if (a.pos === b.pos) return { ...a, kind: "noop" };
13  return a.pos < b.pos ? a : { ...a, pos: a.pos - 1 };
14}
15 
16type Id = [number, string];  // [counter, site]: unique, and ordered
17type Char = { id: Id; after: Id | null; ch: string; deleted: boolean };
18 
19const key = (id: Id | null) => id ? id[0] + "@" + id[1] : "root";
20const newer = (a: Id, b: Id) => a[0] > b[0] || (a[0] === b[0] && a[1] > b[1]);
21 
22class Replica {
23  chars = new Map<string, Char>();
24  children = new Map<string, Char[]>();
25  removed = new Set<string>(); // includes deletes received before inserts
26  clock = 0;
27  constructor(public site: string) {}
28 
29  text(): string {
30    return this.visible().map((c) => c.ch).join("");
31  }
32 
33  visible(): Char[] {
34    const out: Char[] = [];
35    const stack = [...(this.children.get("root") ?? [])].reverse();
36    while (stack.length) {
37      const c = stack.pop()!;
38      if (!c.deleted) out.push(c);
39      for (const child of [...(this.children.get(key(c.id)) ?? [])].reverse()) stack.push(child);
40    }
41    return out;
42  }
43 
44  insertAt(pos: number, ch: string): Char {
45    const visible = this.visible();
46    const after = pos > 0 ? visible[pos - 1].id : null;
47    this.clock += 1;
48    const c: Char = { id: [this.clock, this.site], after, ch, deleted: false };
49    this.integrate(c);
50    return { ...c };  // what gets sent to the other replicas
51  }
52 
53  // Anchor order is deterministic; deletion wins over duplicate inserts.
54  integrate(c: Char): void {
55    if (c.deleted) this.remove(c.id);
56    if (this.chars.has(key(c.id))) return;
57    this.clock = Math.max(this.clock, c.id[0]);
58    const copy = { ...c, deleted: c.deleted || this.removed.has(key(c.id)) };
59    this.chars.set(key(c.id), copy);
60    const list = this.children.get(key(c.after)) ?? [];
61    let i = 0;
62    while (i < list.length && newer(list[i].id, c.id)) i++;
63    list.splice(i, 0, copy); this.children.set(key(c.after), list);
64  }
65 
66  deleteAt(pos: number): Id {
67    const target = this.visible()[pos];
68    this.remove(target.id);
69    return target.id;
70  }
71 
72  remove(id: Id): void {
73    this.removed.add(key(id));
74    const c = this.chars.get(key(id));
75    if (c) c.deleted = true;
76  }
77}