perf: stateful O(N) object/array enumeration (avoid O(N²) entry-at walk)

[membphis]

Motivation

qjson.pairs(obj) on a LazyObject currently calls qjson_cursor_object_entry_at(cursor, i, ...) with an incrementing index. Under the hood, Document::nth_object_entry (src/doc.rs:118) walks from the container's opening brace to the i-th child every time. Enumerating all N keys costs O(N²).

This is the single biggest performance cliff in the library: the moment a user iterates all fields (logging, schema validation, re-encoding), they hit quadratic behavior. Fixing it makes lua-qjson a viable full replacement for lua-cjson in "touch every field" workloads.

Solution approach

Introduce a stateful object iterator exposed as a small POD struct through the FFI. The iterator remembers its current position in the indices array and advances one key/value pair per next call via find_value_span — no re-walk from the container opener.

Key design decisions:

1. Object only. Array iteration already goes through qjson_cursor_index → walk_children → skip-cache, which is O(N) after the first access. No array iterator needed.
2. Stack-allocated POD struct. The iterator state is ~12 bytes (doc pointer + idx_current + idx_end). Lua side allocates with ffi.new("qjson_iter[1]") — no heap allocation, no free, no GC leak on early break.
3. Multiple iterators safe. Each iterator holds its own position. The scratch buffer conflict is handled by the existing contract: Lua calls ffi.string(ptr, len) immediately after each next, before any other doc operation.

Spec

Rust-side additions

New struct (src/ffi.rs)

// C-visible layout
typedef struct {
    const qjson_doc *doc;
    uint32_t         idx_current;  // next index position to read
    uint32_t         idx_end;      // container closer position in indices[]
} qjson_iter;

#[repr(C)], Copy, Clone. No heap resources — pure positional state.

New FFI functions (src/ffi.rs)

// Initialize an iterator over the object at cursor `c`.
// Returns QJSON_OK on success, QJSON_TYPE_MISMATCH if `c` is not an object.
// On success, `it` is filled and ready for the first qjson_iter_next call.
// For an empty object, the first qjson_iter_next returns QJSON_NOT_FOUND.
int qjson_iter_init(const qjson_cursor *c, qjson_iter *it);

// Advance to the next key/value pair.
// Returns QJSON_OK while entries remain; QJSON_NOT_FOUND when exhausted.
// On QJSON_OK: *key_ptr / *key_len point to the decoded key (scratch-lifetime),
// *value_out is a cursor to the value.
int qjson_iter_next(qjson_iter *it,
                    const char **key_ptr, size_t *key_len,
                    qjson_cursor *value_out);

Both wrapped in ffi_catch! per the panic-barrier convention.

Internal implementation

qjson_iter_init:

• Validate cursor points at {
• Skip whitespace after opener; if immediately }, set idx_current = idx_end (empty sentinel)
• Otherwise set idx_current = cursor.idx_start + 1 (first key position)

qjson_iter_next:

• If idx_current >= idx_end → return QJSON_NOT_FOUND
• Key is at indices[idx_current] (open quote) and indices[idx_current + 1] (close quote)
• Colon at indices[idx_current + 2]
• Value starts at idx_current + 3
• Call find_value_span(doc, idx_current + 3) → (cursor_end, skip_end)
• Decode key via decode_string into scratch → set key_ptr, key_len
• Set value_out cursor to (idx_current + 3, cursor_end)
• Advance: check buf[indices[skip_end]] — if , then idx_current = skip_end + 1; if } then idx_current = idx_end (exhausted)
• Return QJSON_OK

C header update (include/qjson.h)

Add qjson_iter struct typedef and both function declarations.

Lua wrapper update (lua/qjson/table.lua)

Replace lazy_object_iter internals:

local function lazy_object_iter(state, _prev_key)
    local rc = C.qjson_iter_next(state.it, strp_box, size_box, child_box)
    if rc == QJSON_NOT_FOUND then return nil end
    check(rc)
    local k = ffi.string(strp_box[0], size_box[0])
    -- ... existing duplicate-key / cache logic unchanged ...
    return k, v
end

function LazyObject.__pairs(t)
    local keys = rawget(t, ORDER_KEYS)
    if keys then ... end  -- materialized fast-path unchanged
    local it = ffi.new("qjson_iter[1]")
    local rc = C.qjson_iter_init(t._cur, it)
    check(rc)
    return lazy_object_iter, { it = it, view = t, seen = {} }, nil
end

The materialize_object_contents helper (line ~290) should also switch to the iterator.

ffi.cdef update (lua/qjson.lua or lua/qjson/lib.lua)

Add qjson_iter struct and both function declarations to the ffi.cdef block.

Pointer lifetime contract

key_ptr returned by qjson_iter_next points into doc.scratch (or the original buffer for non-escaped keys). It is invalidated by the next call to any *_get_str, *_iter_next, or *_object_entry_at on the same document. Lua wrapper must ffi.string() immediately — this matches the existing pattern.

Scope exclusions

• No qjson_iter_free — struct is POD, nothing to free.
• No array iterator — array path is already O(N).
• No changes to qjson_cursor_object_entry_at — it stays for random-access use cases.

Testing

1. Rust unit test: iterate objects with 0, 1, many keys; verify all keys/values returned in source order; verify NOT_FOUND after exhaustion.
2. Rust unit test: nested iteration (two iterators on different objects of the same doc simultaneously).
3. Rust integration test (tests/ffi_smoke.rs): call qjson_iter_init + qjson_iter_next through the C ABI.
4. Lua busted test: qjson.pairs on objects with 1, 10, 100 keys; verify key order matches source; verify early break doesn't leak.
5. Benchmark: compare qjson.pairs on a 500-key object before/after; expect wall-time improvement proportional to N.

Verification

make build && make test    # all Rust + Lua tests pass
make bench                 # confirm pairs performance improvement
cargo test --release --no-default-features  # scalar-only gate