Repository navigation
Expand file tree
/
Copy pathreorderBuffer.ts
More file actions
147 lines (130 loc) · 4.81 KB
/
Copy pathreorderBuffer.ts
File metadata and controls
147 lines (130 loc) · 4.81 KB
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
// ─────────────────────────────────────────────────────────────
// Seq-based reordering buffer
//
// Handles out-of-order delivery, duplicates, and provides
// in-order emission. Used to process server messages that may
// arrive with shuffled seq values in chaos mode.
// ─────────────────────────────────────────────────────────────
import type { ServerMessage } from "./types";
/**
* A buffer that accepts messages with potentially out-of-order
* seq values and emits them in correct seq order.
*
* - Out-of-order messages are buffered until the gap is filled.
* - Duplicate seq values are dropped silently.
* - The buffer has a configurable max size to bound memory.
*/
export class ReorderBuffer {
private buffer: Map<number, ServerMessage> = new Map();
private nextExpectedSeq: number = 1;
private readonly maxSize: number;
constructor(maxSize: number = 200) {
this.maxSize = maxSize;
}
/**
* Reset the buffer (e.g. on new conversation turn).
*/
reset(nextSeq: number = 1): void {
this.buffer.clear();
this.nextExpectedSeq = nextSeq;
}
/**
* Accept a message. Returns an array of messages that can now
* be emitted in order (always at least the message itself if
* it fills the current gap, otherwise buffered).
*
* Duplicates (same seq already processed) return an empty array.
*/
accept(msg: ServerMessage): ServerMessage[] {
const seq = msg.seq;
// Duplicate check: if seq is below nextExpectedSeq, it's
// either already emitted or a duplicate of a buffered message.
if (seq < this.nextExpectedSeq) {
return []; // duplicate, silently drop
}
// If it's the next expected seq, emit it and flush any
// subsequent buffered messages.
if (seq === this.nextExpectedSeq) {
const emitted: ServerMessage[] = [msg];
this.nextExpectedSeq++;
// Flush contiguous buffered messages
while (this.buffer.has(this.nextExpectedSeq)) {
const next = this.buffer.get(this.nextExpectedSeq)!;
this.buffer.delete(this.nextExpectedSeq);
emitted.push(next);
this.nextExpectedSeq++;
}
return emitted;
}
// A duplicate of a message we are still holding is not a newer revision.
if (this.buffer.has(seq)) {
return [];
}
// Future message: buffer it if we have room
if (this.buffer.size >= this.maxSize) {
// Buffer full — drop the oldest buffered message to make room.
// This is safe because:
// 1. All buffered messages have seq > nextExpectedSeq
// 2. The oldest buffered message is the least likely to be
// needed soon (furthest behind in the sequence)
// 3. If it was actually next in order, a later flush will
// catch it — but in practice, with maxSize=200 and
// typical out-of-order windows of 3-5, this never fires.
const maxSeq = Math.max(...this.buffer.keys());
// Only drop if the new message is more important (higher seq)
// than the oldest. Otherwise drop the new one.
if (seq > maxSeq) {
// Drop the oldest (lowest seq) to make room for the new highest
const minSeq = Math.min(...this.buffer.keys());
this.buffer.delete(minSeq);
this.buffer.set(seq, msg);
}
// else: the new message is older than everything we have, drop it
return [];
}
// Buffer the out-of-order message
this.buffer.set(seq, msg);
return [];
}
/**
* Returns the count of currently buffered messages.
*/
get bufferedCount(): number {
return this.buffer.size;
}
/**
* Returns the next seq we're expecting.
*/
get expectedSeq(): number {
return this.nextExpectedSeq;
}
/**
* Force-flush all buffered messages in seq order (for stream end).
*/
flush(): ServerMessage[] {
if (this.buffer.size === 0) return [];
const sorted = [...this.buffer.keys()].sort((a, b) => a - b);
const emitted: ServerMessage[] = [];
for (const seq of sorted) {
if (seq >= this.nextExpectedSeq) {
emitted.push(this.buffer.get(seq)!);
}
}
this.buffer.clear();
this.nextExpectedSeq = sorted.length > 0
? (sorted[sorted.length - 1]! as number) + 1
: this.nextExpectedSeq;
return emitted;
}
}
/**
* Accept one wire event without allowing a terminal frame to bypass an
* outstanding sequence gap. Keeping this policy alongside the buffer makes
* the completion rule testable independently of the React message handler.
*/
export function acceptOrderedMessages(
buffer: ReorderBuffer,
message: ServerMessage,
): ServerMessage[] {
return buffer.accept(message);
}