编码母题 / P0 / Node 与 JavaScript / 05

服务端推送与增量事件解析器

先读清题意与边界,独立尝试,再展开思路并对照可运行的参考代码。

重要程度高价值难度困难预计完成45–60 分钟

难度按 LeetCode 简单/中等/困难三档估计;工程题并非 LeetCode 官方题目。用时指独立编码并检查主要边界的参考时间,因经验而异。

题目是什么

实现 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"]

解题思路

展开思路、不变量与常见边界

关键切入点: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"]

复杂度分析

时间复杂度:最坏 O(B²)。若没有换行,逐块追加后反复扫描增长中的 buffer;B 为输入总长度。

空间复杂度:O(U)。只保留未完成事件及跨块残片,U 为其最大长度。

下载原始 JS 文件