编码母题 / P0 / Node 与 JavaScript / 05
服务端推送与增量事件解析器
先读清题意与边界,独立尝试,再展开思路并对照可运行的参考代码。
重要程度高价值难度困难预计完成45–60 分钟
题目是什么
实现 SSE 编码与增量解析。网络块可截断 UTF-8 字符、行结束符、字段名和事件;连续 data 行拼接,空行才提交事件。
输入输出示例
先收到 data: a 后半个 CRLF,下一块继续到 data: b,最终只应产生 data 为 a\nb 的一个事件。
练习起手式与验证
复制代码后补全空方法,再运行下方三组验证;复杂题所需的辅助类型与输入准备一并放在代码块中。
/*
* 题目:服务端推送与增量事件解析器
* 要求:实现 SSE 编码与增量解析。网络块可截断 UTF-8 字符、行结束符、字段名和事件;
* 连续 data 行拼接,空行才提交事件。
* 示例:先收到 data: a 后半个 CRLF,下一块继续到 data: b,最终只应产生
* data 为 a\nb 的一个事件。
*/
function encodeSSE({ event, data, id, retry }) {}
class SSEParser {
constructor(onEvent) {}
reset() {}
push(chunk) {}
finish() {}
consumeLines(final = false) {}
processLine(line) {}
}
const events = [];
const parser = new SSEParser((event) => events.push(event));
const bytes = new TextEncoder().encode(
encodeSSE({ event: "token", data: "你\n好", id: 7, retry: 1000 }),
);
parser.push(bytes.slice(0, 5));
parser.push(bytes.slice(5, 17));
parser.push(bytes.slice(17));
parser.finish();
console.log(events); // 预期:[ { event: "token", data: "你\n好", id: "7", retry: 1000 }, ]
const comments = [];
const p2 = new SSEParser((e) => comments.push(e));
p2.push(": ping\n\ndata: ok\n\n");
console.log(comments[0].data); // 预期:"ok"
const splitEvents = [];
const p3 = new SSEParser((event) => splitEvents.push(event));
p3.push("data: a\r");
p3.push("\ndata: b\r\n\r\n");
console.log(splitEvents.map((event) => event.data)); // 预期:["a\nb"]
/*
* 题目:服务端推送与增量事件解析器
* 要求:实现 SSE 编码与增量解析。网络块可截断 UTF-8 字符、行结束符、字段名和事件;
* 连续 data 行拼接,空行才提交事件。
* 示例:先收到 data: a 后半个 CRLF,下一块继续到 data: b,最终只应产生
* data 为 a\nb 的一个事件。
*/
function encodeSSE({ event, data, id, retry }) {}
class SSEParser {
constructor(onEvent) {}
reset() {}
push(chunk) {}
finish() {}
consumeLines(final = false) {}
processLine(line) {}
}
const events = [];
const parser = new SSEParser((event) => events.push(event));
const bytes = new TextEncoder().encode(
encodeSSE({ event: "token", data: "你\n好", id: 7, retry: 1000 }),
);
parser.push(bytes.slice(0, 5));
parser.push(bytes.slice(5, 17));
parser.push(bytes.slice(17));
parser.finish();
console.log(events); // 预期:[ { event: "token", data: "你\n好", id: "7", retry: 1000 }, ]
const comments = [];
const p2 = new SSEParser((e) => comments.push(e));
p2.push(": ping\n\ndata: ok\n\n");
console.log(comments[0].data); // 预期:"ok"
const splitEvents = [];
const p3 = new SSEParser((event) => splitEvents.push(event));
p3.push("data: a\r");
p3.push("\ndata: b\r\n\r\n");
console.log(splitEvents.map((event) => event.data)); // 预期:["a\nb"]解题思路
展开思路、不变量与常见边界
关键切入点:TextDecoder 保存半个字符,文本缓冲保存半行,事件状态保存多行字段;跨块 CRLF 只算一次换行。
核心模型:TextDecoder({stream:true}) 保留不完整字节;文本缓冲按换行消费;事件 状态跨行保存。finish 时刷新 decoder,但没有空行终止的残缺事件不提交。 不变量:每个字节只解码一次;只在完整空行边界产生事件;未知字段忽略。 当前实现的完整行解析按缓冲区扫描;极端无换行且每块很小时会重复扫描。 迁移:LLM Token、Agent Step、进度通知。
参考代码与验证
“关键机制”注释用于解释实现,下载链接提供未经页面注释修改的原始 JS 文件。
// 关键机制:TextDecoder 保存半个字符,文本缓冲保存半行,事件状态保存多行字段;跨块 CRLF 只算一次换行。
function encodeSSE({ event, data, id, retry }) {
const lines = [];
if (id !== undefined) lines.push(`id: ${String(id).replace(/[\r\n]/g, "")}`);
if (event) lines.push(`event: ${event}`);
if (retry !== undefined) lines.push(`retry: ${retry}`);
for (const line of String(data ?? "").split(/\r?\n/))
lines.push(`data: ${line}`);
return `${lines.join("\n")}\n\n`;
}
class SSEParser {
constructor(onEvent) {
if (typeof onEvent !== "function") throw new TypeError("onEvent required");
this.onEvent = onEvent;
this.decoder = new TextDecoder();
this.buffer = "";
this.reset();
}
reset() {
this.event = { data: [] };
}
push(chunk) {
this.buffer +=
typeof chunk === "string"
? chunk
: this.decoder.decode(chunk, { stream: true });
this.consumeLines();
}
finish() {
this.buffer += this.decoder.decode();
this.consumeLines(true);
}
consumeLines(final = false) {
while (true) {
const match = this.buffer.match(/\r\n|\r|\n/);
if (!match) return;
// 留下末尾的 CR,等待下一个 chunk 判断它是否与 LF 构成同一行结束符。
if (!final && match[0] === "\r" && match.index === this.buffer.length - 1)
return;
const line = this.buffer.slice(0, match.index);
this.buffer = this.buffer.slice(match.index + match[0].length);
this.processLine(line);
}
}
processLine(line) {
if (line === "") {
if (this.event.data.length)
this.onEvent({
event: this.event.event || "message",
data: this.event.data.join("\n"),
id: this.event.id,
retry: this.event.retry,
});
this.reset();
return;
}
if (line.startsWith(":")) return;
const separator = line.indexOf(":");
const field = separator < 0 ? line : line.slice(0, separator);
let value = separator < 0 ? "" : line.slice(separator + 1);
if (value.startsWith(" ")) value = value.slice(1);
if (field === "data") this.event.data.push(value);
else if (field === "event") this.event.event = value;
else if (field === "id" && !value.includes("\0")) this.event.id = value;
else if (field === "retry" && /^\d+$/.test(value))
this.event.retry = Number(value);
}
}
// 三组以上可直接运行的验证。
const events = [];
const parser = new SSEParser((event) => events.push(event));
const bytes = new TextEncoder().encode(
encodeSSE({ event: "token", data: "你\n好", id: 7, retry: 1000 }),
);
parser.push(bytes.slice(0, 5));
parser.push(bytes.slice(5, 17));
parser.push(bytes.slice(17));
parser.finish();
console.log(events); // 预期:[ { event: "token", data: "你\n好", id: "7", retry: 1000 }, ]
const comments = [];
const p2 = new SSEParser((e) => comments.push(e));
p2.push(": ping\n\ndata: ok\n\n");
console.log(comments[0].data); // 预期:"ok"
const splitEvents = [];
const p3 = new SSEParser((event) => splitEvents.push(event));
p3.push("data: a\r");
p3.push("\ndata: b\r\n\r\n");
console.log(splitEvents.map((event) => event.data)); // 预期:["a\nb"]
const loneCR = [];
const p4 = new SSEParser((event) => loneCR.push(event));
p4.push("data: c\r\r");
p4.finish();
console.log(loneCR.map((event) => event.data)); // 预期:["c"]
// 关键机制:TextDecoder 保存半个字符,文本缓冲保存半行,事件状态保存多行字段;跨块 CRLF 只算一次换行。
function encodeSSE({ event, data, id, retry }) {
const lines = [];
if (id !== undefined) lines.push(`id: ${String(id).replace(/[\r\n]/g, "")}`);
if (event) lines.push(`event: ${event}`);
if (retry !== undefined) lines.push(`retry: ${retry}`);
for (const line of String(data ?? "").split(/\r?\n/))
lines.push(`data: ${line}`);
return `${lines.join("\n")}\n\n`;
}
class SSEParser {
constructor(onEvent) {
if (typeof onEvent !== "function") throw new TypeError("onEvent required");
this.onEvent = onEvent;
this.decoder = new TextDecoder();
this.buffer = "";
this.reset();
}
reset() {
this.event = { data: [] };
}
push(chunk) {
this.buffer +=
typeof chunk === "string"
? chunk
: this.decoder.decode(chunk, { stream: true });
this.consumeLines();
}
finish() {
this.buffer += this.decoder.decode();
this.consumeLines(true);
}
consumeLines(final = false) {
while (true) {
const match = this.buffer.match(/\r\n|\r|\n/);
if (!match) return;
// 留下末尾的 CR,等待下一个 chunk 判断它是否与 LF 构成同一行结束符。
if (!final && match[0] === "\r" && match.index === this.buffer.length - 1)
return;
const line = this.buffer.slice(0, match.index);
this.buffer = this.buffer.slice(match.index + match[0].length);
this.processLine(line);
}
}
processLine(line) {
if (line === "") {
if (this.event.data.length)
this.onEvent({
event: this.event.event || "message",
data: this.event.data.join("\n"),
id: this.event.id,
retry: this.event.retry,
});
this.reset();
return;
}
if (line.startsWith(":")) return;
const separator = line.indexOf(":");
const field = separator < 0 ? line : line.slice(0, separator);
let value = separator < 0 ? "" : line.slice(separator + 1);
if (value.startsWith(" ")) value = value.slice(1);
if (field === "data") this.event.data.push(value);
else if (field === "event") this.event.event = value;
else if (field === "id" && !value.includes("\0")) this.event.id = value;
else if (field === "retry" && /^\d+$/.test(value))
this.event.retry = Number(value);
}
}
// 三组以上可直接运行的验证。
const events = [];
const parser = new SSEParser((event) => events.push(event));
const bytes = new TextEncoder().encode(
encodeSSE({ event: "token", data: "你\n好", id: 7, retry: 1000 }),
);
parser.push(bytes.slice(0, 5));
parser.push(bytes.slice(5, 17));
parser.push(bytes.slice(17));
parser.finish();
console.log(events); // 预期:[ { event: "token", data: "你\n好", id: "7", retry: 1000 }, ]
const comments = [];
const p2 = new SSEParser((e) => comments.push(e));
p2.push(": ping\n\ndata: ok\n\n");
console.log(comments[0].data); // 预期:"ok"
const splitEvents = [];
const p3 = new SSEParser((event) => splitEvents.push(event));
p3.push("data: a\r");
p3.push("\ndata: b\r\n\r\n");
console.log(splitEvents.map((event) => event.data)); // 预期:["a\nb"]
const loneCR = [];
const p4 = new SSEParser((event) => loneCR.push(event));
p4.push("data: c\r\r");
p4.finish();
console.log(loneCR.map((event) => event.data)); // 预期:["c"]
复杂度分析
时间复杂度:最坏 O(B²)。若没有换行,逐块追加后反复扫描增长中的 buffer;B 为输入总长度。
空间复杂度:O(U)。只保留未完成事件及跨块残片,U 为其最大长度。