Skip to content

Commit 1f9b4db

Browse files
authored
Merge pull request DeusData#2288 from JosephStarobinets/fix/lsp-surface-quadratic-array-access
fix(pipeline): decode persisted LSP surfaces with linear array iteration
2 parents 66d9c2b + d7eba5a commit 1f9b4db

2 files changed

Lines changed: 62 additions & 6 deletions

File tree

‎src/pipeline/lsp_surface.c‎

Lines changed: 18 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -250,9 +250,15 @@ static const char **arena_str_array(CBMArena *arena, yyjson_val *arr, bool null_
250250
if (!items) {
251251
return NULL;
252252
}
253-
for (int i = 0; i < count; i++) {
254-
const char *s = yyjson_get_str(yyjson_arr_get(arr, (size_t)i));
255-
items[i] = s ? cbm_arena_strdup(arena, s) : "?";
253+
/* Iterate instead of yyjson_arr_get(i): that call is a linear scan for
254+
* non-flat arrays (arrays of objects are not flat), which turns this loop
255+
* into O(n^2) in the element count. */
256+
yyjson_arr_iter iter = yyjson_arr_iter_with(arr);
257+
int i = 0;
258+
yyjson_val *item;
259+
while ((item = yyjson_arr_iter_next(&iter))) {
260+
const char *s = yyjson_get_str(item);
261+
items[i++] = s ? cbm_arena_strdup(arena, s) : "?";
256262
}
257263
if (null_terminated) {
258264
items[count] = NULL;
@@ -288,9 +294,15 @@ int cbm_lsp_surface_defs_from_json(CBMArena *arena, const char *defs_json, CBMLS
288294
return -1;
289295
}
290296
memset(defs, 0, (size_t)count * sizeof(CBMLSPDef));
291-
for (int i = 0; i < count; i++) {
292-
yyjson_val *o = yyjson_arr_get(lsp, (size_t)i);
293-
CBMLSPDef *d = &defs[i];
297+
/* Iterate instead of yyjson_arr_get(i). `lsp` is an array of objects, which
298+
* is not flat, so indexing rescans the preceding elements and the whole
299+
* decode becomes O(n^2). One generated data file with ~300k defs made this
300+
* step take minutes. */
301+
yyjson_arr_iter iter = yyjson_arr_iter_with(lsp);
302+
int i = 0;
303+
yyjson_val *o;
304+
while ((o = yyjson_arr_iter_next(&iter))) {
305+
CBMLSPDef *d = &defs[i++];
294306
d->qualified_name = arena_str_or_null(arena, yyjson_obj_get(o, "qn"));
295307
d->short_name = arena_str_or_null(arena, yyjson_obj_get(o, "sn"));
296308
d->label = arena_str_or_null(arena, yyjson_obj_get(o, "lb"));

‎tests/test_pipeline.c‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@
1010
#include "test_helpers.h"
1111
#include "foundation/mem.h" // cbm_mem_init/budget (back-pressure futile-nap test)
1212
#include "pipeline/pipeline.h"
13+
#include "pipeline/lsp_surface.h"
1314
#include "pipeline/pipeline_internal.h"
1415
#include "pipeline/artifact.h"
1516
#include "store/store.h"
@@ -14252,6 +14253,48 @@ TEST(pipeline_seq_ts_cross_uses_shared_registry) {
1425214253
PASS();
1425314254
}
1425414255

14256+
/* Object arrays are non-flat in yyjson. Exercise ordered decoding and arena
14257+
* ownership across a large surface, including nested string arrays. */
14258+
TEST(pipeline_lsp_surface_large_object_array_decode) {
14259+
const int count = 8192;
14260+
const size_t capacity = (size_t)count * 192 + 64;
14261+
char *json = malloc(capacity);
14262+
ASSERT_NOT_NULL(json);
14263+
size_t used = (size_t)snprintf(json, capacity, "{\"v\":1,\"lsp\":[");
14264+
for (int i = 0; i < count; i++) {
14265+
int n = snprintf(json + used, capacity - used,
14266+
"%s{\"qn\":\"pkg.f%d\",\"sn\":\"f%d\",\"lb\":\"Function\","
14267+
"\"spt\":[\"str\",\"int\"],\"dec\":[\"first\",\"second\"]}",
14268+
i ? "," : "", i, i);
14269+
ASSERT_TRUE(n > 0 && (size_t)n < capacity - used);
14270+
used += (size_t)n;
14271+
}
14272+
snprintf(json + used, capacity - used, "]}");
14273+
CBMArena arena;
14274+
cbm_arena_init(&arena);
14275+
CBMLSPDef *defs = NULL;
14276+
int decoded = cbm_lsp_surface_defs_from_json(&arena, json, &defs);
14277+
free(json);
14278+
ASSERT_EQ(decoded, count);
14279+
ASSERT_NOT_NULL(defs);
14280+
for (int i = 0; i < count; i++) {
14281+
char expected[64];
14282+
snprintf(expected, sizeof(expected), "pkg.f%d", i);
14283+
ASSERT_STR_EQ(defs[i].qualified_name, expected);
14284+
snprintf(expected, sizeof(expected), "f%d", i);
14285+
ASSERT_STR_EQ(defs[i].short_name, expected);
14286+
ASSERT_STR_EQ(defs[i].label, "Function");
14287+
ASSERT_EQ(defs[i].signature_param_count, 2);
14288+
ASSERT_STR_EQ(defs[i].signature_param_types[0], "str");
14289+
ASSERT_STR_EQ(defs[i].signature_param_types[1], "int");
14290+
ASSERT_STR_EQ(defs[i].decorators[0], "first");
14291+
ASSERT_STR_EQ(defs[i].decorators[1], "second");
14292+
ASSERT_NULL(defs[i].decorators[2]);
14293+
}
14294+
cbm_arena_destroy(&arena);
14295+
PASS();
14296+
}
14297+
1425514298
/* The closure-repair route lives and dies by two properties of the persisted
1425614299
* per-file LSP surface: a BODY edit must leave the surface_sha unchanged (the
1425714300
* early cutoff -- no dependent recomputation owed), while a SIGNATURE edit
@@ -15234,6 +15277,7 @@ TEST(pipeline_objectscript_export_range_join_keeps_one_trailing_marker) {
1523415277
#endif
1523515278

1523615279
SUITE(pipeline) {
15280+
RUN_TEST(pipeline_lsp_surface_large_object_array_decode);
1523715281
RUN_TEST(pipeline_lsp_surface_persisted_and_body_edit_invariant);
1523815282
/* Index lock */
1523915283
RUN_TEST(pipeline_lock_try_acquire);

0 commit comments

Comments
 (0)