Skip to content

Commit c07f175

Browse files
andris9claude
andris9
and
claude
committed
fix(addressparser): parse comment-joined addresses in linear time
The join check read the accumulator's last character back with parts[parts.length - 1].slice(-1). That flattens the whole growing run on every token, so an address built from many comment-joined atoms, such as 'a@b(c)@b(c)...', parsed in O(n^2): 1.5MB of address blocked the event loop for about 10 seconds. The run only ever grows by the token appended in that same branch, so its last character is now carried alongside it per state rather than re-read off the accumulator. Parse output is unchanged, verified by a 80k input differential fuzz against the previous implementation. Reachable without authentication anywhere inbound headers are parsed with this module, mailparser being the notable case. Reordering the operands so the cheap token.value.charAt(0) test runs first was not enough: it only short-circuits when the atom after the comment starts with '@', and 'a@(c)b@(c)b@...' stays quadratic. Both shapes are covered by tests. Fixes GHSA-prgh-xp8r-p3m5 Co-Authored-By: Claude Opus 5 (1M context) <[email protected]> Claude-Session: https://claude.ai/code/session_01QWP5uaVCxv26wEFF3uE1J1
1 parent ad54add commit c07f175

2 files changed

Lines changed: 41 additions & 2 deletions

File tree

‎src/addressparser/index.ts‎

Lines changed: 17 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,11 @@ interface AddressParts {
5555
textWasQuoted: boolean[];
5656
}
5757

58+
/**
59+
* The run of an address the token walk is collecting into at a given point
60+
*/
61+
type AddressPartsState = 'text' | 'address' | 'comment' | 'group';
62+
5863
/**
5964
* Restores the quoting of a local part that was read out of a quoted string.
6065
*
@@ -193,7 +198,7 @@ function _recoverAddrSpec(data: { address: string; text: string }): void {
193198
*/
194199
function _handleAddress(tokens: Token[], depth: number): Address[] {
195200
let isGroup = false;
196-
let state: 'text' | 'address' | 'comment' | 'group' = 'text';
201+
let state: AddressPartsState = 'text';
197202
const addresses: Address[] = [];
198203
const data: AddressParts = {
199204
address: [],
@@ -203,6 +208,12 @@ function _handleAddress(tokens: Token[], depth: number): Address[] {
203208
textWasQuoted: []
204209
};
205210
let insideQuotes = false;
211+
// Last character of the run each state is currently accumulating. Reading it back off
212+
// the accumulator with slice(-1) makes the engine flatten the whole growing string on
213+
// every token, which is quadratic over an address built from many comment-joined atoms
214+
// (GHSA-prgh-xp8r-p3m5). A run only ever grows by the token appended below, so the
215+
// character is carried along instead of re-read.
216+
const lastChars: Record<AddressPartsState, string> = { address: '', comment: '', group: '', text: '' };
206217

207218
// Filter out <addresses>, (comments) and regular text
208219
for (let i = 0, len = tokens.length; i < len; i++) {
@@ -248,15 +259,19 @@ function _handleAddress(tokens: Token[], depth: number): Address[] {
248259
prevToken &&
249260
prevToken.noBreak &&
250261
parts.length &&
251-
(prevToken.value !== ')' || parts[parts.length - 1].slice(-1) === '@' || token.value.charAt(0) === '@');
262+
(prevToken.value !== ')' || lastChars[state] === '@' || token.value.charAt(0) === '@');
252263

253264
if (joins) {
254265
data[state][data[state].length - 1] += token.value;
266+
if (token.value) {
267+
lastChars[state] = token.value.charAt(token.value.length - 1);
268+
}
255269
if (state === 'text' && insideQuotes) {
256270
data.textWasQuoted[data.textWasQuoted.length - 1] = true;
257271
}
258272
} else {
259273
data[state].push(token.value);
274+
lastChars[state] = token.value.charAt(token.value.length - 1);
260275
if (state === 'text') {
261276
data.textWasQuoted.push(insideQuotes);
262277
}

‎test/addressparser/addressparser-test.ts‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1179,6 +1179,30 @@ describe('#addressparser', () => {
11791179
assert.ok(elapsed < 5000, `merging ${count} fragments took ${elapsed}ms`);
11801180
});
11811181

1182+
// The join check read the accumulator's last character back with slice(-1), which
1183+
// flattens the growing run on every token. An address made of many comment-joined
1184+
// atoms is one run, so the parse went quadratic: 1.5MB took ~10s of blocked event
1185+
// loop, reachable unauthenticated through anything that parses inbound headers
1186+
// (GHSA-prgh-xp8r-p3m5). Both shapes are covered because the atom after the comment
1187+
// opening with '@' and the run ending with '@' are separate arms of that check.
1188+
for (const [label, build] of [
1189+
['comment-joined atoms', (count: number) => 'a' + '@b(c)'.repeat(count)],
1190+
['comment-separated atoms', (count: number) => 'a@' + '(c)b@'.repeat(count)]
1191+
] as [string, (count: number) => string][]) {
1192+
it(`should parse an address built from ${label} in linear time`, () => {
1193+
// ~1.5MB, where the quadratic parse took ~10s and the linear one takes ~80ms
1194+
const count = 320000;
1195+
const input = build(count);
1196+
1197+
const started = Date.now();
1198+
const result = addressparser(input);
1199+
const elapsed = Date.now() - started;
1200+
1201+
assert.strictEqual(result.length, 1);
1202+
assert.ok(elapsed < 5000, `parsing a ${input.length} byte address took ${elapsed}ms`);
1203+
});
1204+
}
1205+
11821206
it('should keep fragment merging identical to the previous implementation', () => {
11831207
assert.deepStrictEqual(addressparser('Joe Foo, PhD <[email protected]>'), [{ address: '[email protected]', name: 'Joe Foo, PhD' }]);
11841208
assert.deepStrictEqual(addressparser('a, b, c <[email protected]>'), [{ address: '[email protected]', name: 'a, b, c' }]);

0 commit comments

Comments
 (0)