accidental.cc
offline-first, p2p synced, atproto enabled, feed reader
1import {afterEach, beforeEach, describe, expect, it, vi} from 'vitest'
2
3import {IdentBrand} from '#realm/schema/brands'
4import {Timestamp, compare, explode, generate} from '#realm/schema/timestamp'
5
6import {LogicalClock} from './logical-clock'
7
8type TickListener = (evt: CustomEvent<Timestamp>) => void
9
10describe('LogicalClock', () => {
11 let identAlice: ReturnType<typeof IdentBrand.generate>
12 let identBob: ReturnType<typeof IdentBrand.generate>
13
14 beforeEach(() => {
15 identAlice = IdentBrand.generate()
16 identBob = IdentBrand.generate()
17 })
18
19 describe('constructor', () => {
20 it('creates a clock with no initial timestamp', () => {
21 const clock = new LogicalClock(identAlice)
22
23 expect(clock.actor).toBe(identAlice)
24 expect(clock.latest()).toBeNull()
25 })
26
27 it('creates a clock with an initial timestamp', () => {
28 const initialTimestamp = generate(identAlice, 1000, 0)
29 const clock = new LogicalClock(identAlice, initialTimestamp)
30
31 expect(clock.actor).toBe(identAlice)
32 expect(clock.latest()).toBe(initialTimestamp)
33 })
34 })
35
36 describe('actor', () => {
37 it('returns the identity of the clock owner', () => {
38 const clock = new LogicalClock(identAlice)
39
40 expect(clock.actor).toBe(identAlice)
41 })
42 })
43
44 describe('latest', () => {
45 it('returns null initially when no timestamp is set', () => {
46 const clock = new LogicalClock(identAlice)
47
48 expect(clock.latest()).toBeNull()
49 })
50
51 it('returns the latest timestamp after generating one', () => {
52 const clock = new LogicalClock(identAlice)
53 const timestamp = clock.now()
54
55 expect(clock.latest()).toBe(timestamp)
56 })
57
58 it('returns the bootstrapped timestamp', () => {
59 const initialTimestamp = generate(identAlice, 1000, 0)
60 const clock = new LogicalClock(identAlice, initialTimestamp)
61
62 expect(clock.latest()).toBe(initialTimestamp)
63 })
64 })
65
66 describe('now', () => {
67 it('generates a monotonically increasing timestamp', () => {
68 const clock = new LogicalClock(identAlice)
69
70 const ts1 = clock.now()
71 const ts2 = clock.now()
72 const ts3 = clock.now()
73
74 expect(compare(ts1, ts2)).toBeLessThan(0)
75 expect(compare(ts2, ts3)).toBeLessThan(0)
76 })
77
78 it('increments counter for timestamps in same second', () => {
79 const clock = new LogicalClock(identAlice)
80
81 const ts1 = clock.now()
82 const ts2 = clock.now()
83
84 const {seconds: s1, counter: c1} = explode(ts1)
85 const {seconds: s2, counter: c2} = explode(ts2)
86
87 if (s1 === s2) {
88 expect(c2).toBe(c1 + 1)
89 }
90 })
91
92 it('uses the clock actor identity', () => {
93 const clock = new LogicalClock(identAlice)
94 const timestamp = clock.now()
95
96 const {identid} = explode(timestamp)
97 expect(identid).toBe(identAlice)
98 })
99
100 it('updates latest timestamp', () => {
101 const clock = new LogicalClock(identAlice)
102
103 expect(clock.latest()).toBeNull()
104
105 const ts1 = clock.now()
106 expect(clock.latest()).toBe(ts1)
107
108 const ts2 = clock.now()
109 expect(clock.latest()).toBe(ts2)
110 })
111
112 it('handles rapid successive calls', () => {
113 const clock = new LogicalClock(identAlice)
114 const timestamps = []
115
116 for (let i = 0; i < 100; i++) {
117 timestamps.push(clock.now())
118 }
119
120 // All timestamps should be strictly ordered
121 for (let i = 0; i < timestamps.length - 1; i++) {
122 expect(compare(timestamps[i], timestamps[i + 1])).toBeLessThan(0)
123 }
124 })
125
126 it('generates timestamps with current physical time', () => {
127 const clock = new LogicalClock(identAlice)
128 const beforeSeconds = Math.round(Date.now() / 1000)
129
130 const timestamp = clock.now()
131
132 const afterSeconds = Math.round(Date.now() / 1000)
133 const {seconds} = explode(timestamp)
134
135 // Timestamp seconds should be within the test execution window
136 expect(seconds).toBeGreaterThanOrEqual(beforeSeconds)
137 expect(seconds).toBeLessThanOrEqual(afterSeconds)
138 })
139 })
140
141 describe('tick', () => {
142 it('advances clock with newer timestamp', () => {
143 const clock = new LogicalClock(identAlice)
144 const ts1 = generate(identAlice, 1000, 0)
145
146 const result = clock.tick(ts1)
147
148 expect(result).toBe(ts1)
149 expect(clock.latest()).toBe(ts1)
150 })
151
152 it('does not regress clock with older timestamp', () => {
153 const clock = new LogicalClock(identAlice)
154 const ts1 = generate(identAlice, 2000, 0)
155 const ts2 = generate(identAlice, 1000, 0)
156
157 clock.tick(ts1)
158 const result = clock.tick(ts2)
159
160 expect(result).toBe(ts1)
161 expect(clock.latest()).toBe(ts1)
162 })
163
164 it('accepts timestamp from different actor', () => {
165 const clock = new LogicalClock(identAlice)
166 const bobTimestamp = generate(identBob, 1000, 0)
167
168 const result = clock.tick(bobTimestamp)
169
170 expect(result).toBe(bobTimestamp)
171 expect(clock.latest()).toBe(bobTimestamp)
172 })
173
174 it('maintains monotonicity when mixing now() and tick()', () => {
175 const clock = new LogicalClock(identAlice)
176
177 const ts1 = clock.now()
178 const externalTs = generate(identBob, 9999999999, 0) // Far future
179 clock.tick(externalTs)
180 const ts2 = clock.now()
181
182 expect(compare(ts1, externalTs)).toBeLessThan(0)
183 expect(compare(externalTs, ts2)).toBeLessThanOrEqual(0)
184 })
185
186 it('returns latest timestamp even when not advancing', () => {
187 const clock = new LogicalClock(identAlice)
188 const ts1 = generate(identAlice, 2000, 0)
189 const ts2 = generate(identAlice, 1000, 0)
190
191 clock.tick(ts1)
192 const result = clock.tick(ts2)
193
194 expect(result).toBe(ts1)
195 })
196
197 it('handles equal timestamps idempotently', () => {
198 const clock = new LogicalClock(identAlice)
199 const timestamp = generate(identAlice, 1000, 0)
200
201 const result1 = clock.tick(timestamp)
202 const result2 = clock.tick(timestamp)
203
204 expect(result1).toBe(timestamp)
205 expect(result2).toBe(timestamp)
206 expect(clock.latest()).toBe(timestamp)
207 })
208 })
209
210 describe('tick event', () => {
211 it('dispatches tick event when clock advances', () => {
212 const clock = new LogicalClock(identAlice)
213 const listener = vi.fn<TickListener>()
214
215 clock.addEventListener('tick', listener)
216
217 const timestamp = generate(identAlice, 1000, 0)
218 clock.tick(timestamp)
219
220 expect(listener).toHaveBeenCalledTimes(1)
221 expect(listener).toHaveBeenCalledWith(
222 expect.objectContaining({
223 type: 'tick',
224 detail: timestamp,
225 }),
226 )
227 })
228
229 it('does not dispatch event when clock does not advance', () => {
230 const clock = new LogicalClock(identAlice)
231 const listener = vi.fn<TickListener>()
232
233 const ts1 = generate(identAlice, 2000, 0)
234 const ts2 = generate(identAlice, 1000, 0)
235
236 clock.tick(ts1)
237 clock.addEventListener('tick', listener)
238 clock.tick(ts2) // Older, should not trigger event
239
240 expect(listener).not.toHaveBeenCalled()
241 })
242
243 it('dispatches event on each now() call', () => {
244 const clock = new LogicalClock(identAlice)
245 const listener = vi.fn<TickListener>()
246
247 clock.addEventListener('tick', listener)
248
249 clock.now()
250 clock.now()
251 clock.now()
252
253 expect(listener).toHaveBeenCalledTimes(3)
254 })
255
256 it('allows multiple listeners', () => {
257 const clock = new LogicalClock(identAlice)
258 const listener1 = vi.fn<TickListener>()
259 const listener2 = vi.fn<TickListener>()
260
261 clock.addEventListener('tick', listener1)
262 clock.addEventListener('tick', listener2)
263
264 const timestamp = generate(identAlice, 1000, 0)
265 clock.tick(timestamp)
266
267 expect(listener1).toHaveBeenCalledTimes(1)
268 expect(listener2).toHaveBeenCalledTimes(1)
269 })
270
271 it('can remove listeners', () => {
272 const clock = new LogicalClock(identAlice)
273 const listener = vi.fn<TickListener>()
274
275 clock.addEventListener('tick', listener)
276 clock.tick(generate(identAlice, 1000, 0))
277
278 expect(listener).toHaveBeenCalledTimes(1)
279
280 clock.removeEventListener('tick', listener)
281 clock.tick(generate(identAlice, 2000, 0))
282
283 expect(listener).toHaveBeenCalledTimes(1) // Still only once
284 })
285 })
286
287 describe('clock synchronization scenarios', () => {
288 it('handles receiving timestamp from faster clock', () => {
289 const clock = new LogicalClock(identAlice)
290
291 // Local clock generates some timestamps
292 clock.now()
293 clock.now()
294
295 // Receive timestamp from remote peer with faster clock
296 const futureTimestamp = generate(identBob, 9999999999, 100)
297 clock.tick(futureTimestamp)
298
299 // Subsequent local timestamps should be after the remote one
300 const nextLocal = clock.now()
301 expect(compare(futureTimestamp, nextLocal)).toBeLessThanOrEqual(0)
302 })
303
304 it('handles receiving timestamp from slower clock', () => {
305 const clock = new LogicalClock(identAlice)
306
307 // Advance local clock significantly
308 const localTs = generate(identAlice, 5000, 0)
309 clock.tick(localTs)
310
311 // Receive old timestamp from slow peer
312 const oldTimestamp = generate(identBob, 1000, 0)
313 clock.tick(oldTimestamp)
314
315 // Clock should not regress
316 expect(clock.latest()).toBe(localTs)
317 })
318
319 it('merges concurrent timestamps by identity', () => {
320 const clock = new LogicalClock(identAlice)
321
322 const ts1 = generate(identAlice, 1000, 0)
323 const ts2 = generate(identBob, 1000, 0)
324
325 clock.tick(ts1)
326 clock.tick(ts2)
327
328 // Latest should be whichever is greater
329 const latest = clock.latest()
330 const ordering = compare(ts1, ts2)
331 if (ordering < 0) {
332 expect(latest).toBe(ts2)
333 } else if (ordering > 0) {
334 expect(latest).toBe(ts1)
335 } else {
336 // Should not be equal with different identities
337 expect(ordering).not.toBe(0)
338 }
339 })
340
341 it('maintains counter increments when physical time is behind logical time', () => {
342 const clock = new LogicalClock(identAlice)
343
344 // Receive timestamp from peer that's 1 hour ahead
345 const futureSeconds = Math.round(Date.now() / 1000) + 3600
346 const futureTimestamp = generate(identBob, futureSeconds, 5)
347 clock.tick(futureTimestamp)
348
349 // Generate several local timestamps - physical time is still "behind"
350 // but logical time should stay at futureSeconds with incrementing counters
351 const ts1 = clock.now()
352 const ts2 = clock.now()
353 const ts3 = clock.now()
354
355 const {seconds: s1, counter: c1} = explode(ts1)
356 const {seconds: s2, counter: c2} = explode(ts2)
357 const {seconds: s3, counter: c3} = explode(ts3)
358
359 // All timestamps should be in the "future" second
360 expect(s1).toBe(futureSeconds)
361 expect(s2).toBe(futureSeconds)
362 expect(s3).toBe(futureSeconds)
363
364 // Counters should increment monotonically (starting after Bob's counter)
365 expect(c1).toBeGreaterThan(5)
366 expect(c2).toBe(c1 + 1)
367 expect(c3).toBe(c2 + 1)
368
369 // All should be strictly ordered
370 expect(compare(futureTimestamp, ts1)).toBeLessThan(0)
371 expect(compare(ts1, ts2)).toBeLessThan(0)
372 expect(compare(ts2, ts3)).toBeLessThan(0)
373 })
374 })
375
376 describe('backward clock handling', () => {
377 beforeEach(() => vi.useFakeTimers())
378 afterEach(() => vi.useRealTimers())
379
380 it('maintains monotonicity when system clock goes backward', () => {
381 const clock = new LogicalClock(identAlice)
382
383 const ts1 = clock.now()
384 const {seconds: s1, counter: c1} = explode(ts1)
385
386 // go back a minute
387 const date = new Date(Date.now() - 60 * 1000)
388 vi.setSystemTime(date)
389
390 const ts2 = clock.now()
391 const {seconds: s2, counter: c2} = explode(ts2)
392
393 // new timestamp rolls the counter, not the date
394 expect(s1).toEqual(s2)
395 expect(c1).toEqual(c2 - 1)
396 })
397 })
398
399 describe('bootstrapping from existing timestamp', () => {
400 it('continues from bootstrapped timestamp', () => {
401 const existingTimestamp = generate(identAlice, 5000, 42)
402 const clock = new LogicalClock(identAlice, existingTimestamp)
403
404 const newTimestamp = clock.now()
405
406 // New timestamp should be after the bootstrapped one
407 expect(compare(existingTimestamp, newTimestamp)).toBeLessThanOrEqual(0)
408 })
409
410 it('bootstraps with timestamp from different identity', () => {
411 const bobTimestamp = generate(identBob, 5000, 42)
412 const clock = new LogicalClock(identAlice, bobTimestamp)
413
414 expect(clock.latest()).toBe(bobTimestamp)
415 expect(clock.actor).toBe(identAlice)
416
417 // New timestamps should use alice's identity
418 const newTimestamp = clock.now()
419 const {identid} = explode(newTimestamp)
420 expect(identid).toBe(identAlice)
421 })
422 })
423
424 describe('edge cases', () => {
425 it('handles counter overflow scenario', () => {
426 const clock = new LogicalClock(identAlice)
427 const timestamps = []
428
429 // Generate many timestamps rapidly
430 for (let i = 0; i < 1000; i++) {
431 timestamps.push(clock.now())
432 }
433
434 // All should be strictly ordered
435 for (let i = 0; i < timestamps.length - 1; i++) {
436 expect(compare(timestamps[i], timestamps[i + 1])).toBeLessThan(0)
437 }
438 })
439
440 it('handles timestamp at epoch zero', () => {
441 const clock = new LogicalClock(identAlice)
442 const zeroTimestamp = generate(identAlice, 0, 0)
443
444 clock.tick(zeroTimestamp)
445 expect(clock.latest()).toBe(zeroTimestamp)
446 })
447
448 it('handles very large timestamp values', () => {
449 const clock = new LogicalClock(identAlice)
450 const largeTimestamp = generate(identAlice, 9999999999, 999999)
451
452 clock.tick(largeTimestamp)
453 expect(clock.latest()).toBe(largeTimestamp)
454 })
455 })
456})