Complete the following TypeScript implementation. FORMAT RU...

Prompt

Complete the following TypeScript implementation. FORMAT RULES — FOLLOW EXACTLY: 1. Output exactly one TypeScript code block. 2. Then output exactly: ## Invariants ## Complexity 3. Each section may contain at most 5 bullets. 4. No introduction, conclusion, tests, examples, notes, or other text. 5. Include every type and the complete implementation. 6. Do not change public names, parameters, return types, or error codes. 7. Must compile in TypeScript strict mode. 8. Do not use `any`, `@ts-ignore`, `@ts-expect-error`, `as any`, double assertions through `unknown`, external packages, Node APIs, timers, randomness, or `Date.now()`. Implement a deterministic in-memory transactional JSON document database. ```ts type JsonValue = | null | boolean | number | string | JsonValue[] | { [key: string]: JsonValue }; type IsolationLevel = "snapshot" | "serializable"; interface DocumentVersion { collection: string; id: string; version: number; value: JsonValue; expiresAt?: number; } interface ReadResult extends DocumentVersion {} interface CommitResult { commitVersion: number; writes: DocumentVersion[]; } interface ChangeEvent { sequence: number; commitVersion: number; timestamp: number; collection: string; id: string; type: "created" | "updated" | "deleted" | "expired"; previousVersion?: number; version?: number; value?: JsonValue; expiresAt?: number; } interface Query { collection: string; prefix?: string; limit?: number; } class DatabaseError extends Error { readonly code: | "INVALID_ARGUMENT" | "TRANSACTION_NOT_FOUND" | "TRANSACTION_CLOSED" | "CONFLICT" | "INVALID_SNAPSHOT"; constructor(code: DatabaseError["code"], message: string); } class DocumentDatabase { beginTransaction(isolation: IsolationLevel, now: number): string; read(transactionId: string, collection: string, id: string): ReadResult | null; query(transactionId: string, query: Query): ReadResult[]; put( transactionId: string, collection: string, id: string, value: JsonValue, ttlMs?: number ): void; delete(transactionId: string, collection: string, id: string): void; commit(transactionId: string, now: number): CommitResult; rollback(transactionId: string): void; expire(now: number): ChangeEvent[]; getEvents(afterSequence?: number): ChangeEvent[]; exportSnapshot(): string; static fromSnapshot(snapshot: string): DocumentDatabase; } GENERAL VALIDATION Validate all arguments before mutation. All numeric inputs must be finite. now and afterSequence must be non-negative integers. ttlMs and query limit must be positive integers when present. Collection, ID, and transaction ID must be non-empty after trimming. Query prefix may be empty but must be a string. Invalid method arguments produce INVALID_ARGUMENT. Methods that throw must be atomic. JSON values must contain only JSON data and must reject: undefined, sparse arrays, non-finite numbers, cycles, class instances, accessors, symbol keys, keys named "__proto__", "prototype", or "constructor", objects whose prototype is not Object.prototype or null. Validation must not invoke getters. Do not clone with JSON.parse(JSON.stringify(...)). Inputs and outputs must be deeply detached. ORDERING A document key is (collection, id), ordered first by collection and then ID using direct Unicode code-point comparison. Never use locale-sensitive sorting. TRANSACTIONS Transaction IDs are deterministic: tx-1, tx-2, ... Failed beginTransaction calls do not consume IDs. The next ID counter survives snapshots. Each transaction stores isolation level, begin time, begin commit version, an immutable snapshot of visible documents, staged operations, read set, and for serializable transactions, recorded query predicates and their original ordered (id, version) results. Open transactions are not included in snapshots. Keep closed transaction metadata so missing IDs produce TRANSACTION_NOT_FOUND, while reused committed/rolled-back IDs produce TRANSACTION_CLOSED. A failed commit leaves the transaction open and unchanged. rollback closes the transaction and discards staged state. VISIBILITY AND TTL A transaction sees: its own final staged operation for a key; otherwise its begin-time immutable snapshot. It must never observe later commits. expiresAt = transactionBeginNow + ttlMs, calculated during put. Reject overflow/non-finite arithmetic before mutation. A document is visible in a newly begun transaction only when expiresAt is absent or expiresAt > beginNow, even if expire() has not physically removed it. Existing transactions retain their original snapshot after later commits or expiry. Within a transaction: put and delete replace any earlier staged operation for that key; staged deletion reads as null; deleting a missing key is allowed. READS AND QUERIES read records the key in the read set, including a missing read. query reads one collection, applies optional exact ID prefix, sorts by ID, then applies optional limit. Staged puts/deletes must affect query results. Add every key in the returned result to the read set. Serializable queries also record collection, prefix, limit, and the ordered (id, version) result visible when executed. All returned values are detached. COMMIT VERSIONING Database commit version begins at 0. A successful read-only commit does not increment it. Any commit with at least one staged operation increments it exactly once, including a commit containing only deletions of missing keys. All created/updated documents in one commit receive the same new version. Deletions create no document version. CommitResult.writes includes only created/updated documents, ordered by key. CONFLICTS Perform all conflict checks before mutation. For both isolation levels, each staged key conflicts when current committed state differs from the state in the transaction's begin snapshot. State comparison must distinguish: missing, present with a specific version, physically removed by expiry. Snapshot isolation checks only staged keys. Serializable isolation additionally conflicts when: any read-set key changed since begin; any recorded query would now return a different ordered (id, version) sequence using its original collection, prefix, and limit. Query re-evaluation: uses the current logical database at commit time; excludes documents with expiresAt <= commitNow; overlays the transaction's own final staged operations; must not conflict with its own writes. On conflict: throw DatabaseError("CONFLICT", ...); emit no events; change no counters, documents, or transaction state. COMMIT Before mutation, validate now, clone needed values, validate arithmetic, and finish every conflict check. Apply staged operations in key order. For staged put: determine existence in the current logical database at commit time; emit created if absent, otherwise updated; updated includes previousVersion; both include new version, detached value, and optional expiresAt. For staged delete: emit deleted only if the key currently exists logically; include previousVersion; emit nothing for a missing key. All events from a commit share the new commit version and supplied timestamp. Order events by key. Event sequences start at 1 and are contiguous. A successful commit closes the transaction. EXPIRY expire(now) physically removes every committed document with expiresAt <= now, in key order. If none expire: do not increment commit version; return []. If any expire: increment commit version exactly once; emit one expired event per document; all share the new commit version and supplied timestamp; each includes previousVersion; return detached copies of only those new events. Expiry must affect later conflict detection. EVENTS getEvents() returns all events. getEvents(afterSequence) returns only events with sequence greater than it. All returned events and nested values are detached. SNAPSHOTS exportSnapshot() must return canonical JSON: no whitespace; object keys sorted lexicographically at every depth; documents sorted by key; events sorted by sequence; absent optional fields omitted, not null. Snapshot data must include: version: 1, current commit version, event sequence, next transaction number, current documents, full event log, silentCommitVersions. A silent commit version is a successful write commit that emitted no event, which can only result from deleting missing documents. fromSnapshot() must parse untrusted JSON and reject: malformed JSON; missing or unknown fields; dangerous keys or invalid nested JSON; unsorted/duplicate documents or keys; invalid versions or expiration values; malformed, unsorted, duplicate, or non-contiguous events; fields not allowed or required for an event type; inconsistent counters; any stored state not exactly reproducible from event replay. All snapshot failures, including nested helper failures, must become DatabaseError("INVALID_SNAPSHOT", ...). EVENT REPLAY Replay the complete event log from an empty database. Rules: sequences begin at 1 and are contiguous; event commit versions never decrease; one commit version may contain multiple events; all events in one commit share one timestamp; event-producing commit versions increase by exactly 1 when combined with silent commit versions; no key appears twice in one commit; events within a commit are key-ordered; created requires the key to be absent; updated requires it present and matching previousVersion; deleted/expired require it present and matching previousVersion; created/updated version must equal their commit version; replayed final documents must exactly equal stored documents, including values, versions, and optional expiry. silentCommitVersions must be sorted unique positive integers, contain no event-producing version, and together with event-producing versions form every integer from 1 through top-level commit version. Restoring a valid snapshot and immediately exporting it must produce exactly the same string. ADDITIONAL CONSTRAINTS Do not normalize identifiers or snapshots. Do not mutate committed data before commit succeeds. Do not expose internal collections or staged state. Do not weaken serializable conflict detection. Do not replace replay validation with structural validation. Do not include tests. ## Answer guidance ```text Score executable correctness and instruction following separately. Immediate major failures: - Does not compile in TypeScript strict mode. - Violates the exact output format. - Changes the public API. - Uses forbidden typing escapes, libraries, Node APIs, randomness, timers, or Date.now(). - Failed commit mutates or closes the transaction. - Transactions observe commits made after they begin. - Snapshot isolation checks read conflicts rather than staged-key conflicts only. - Serializable mode omits read-set or query-predicate conflict detection. - Query conflict checks ignore prefix, limit, ordering, staged operations, or logical expiry. - Read-only commits increment commit version. - Missing-only deletion commits fail to increment commit version. - Snapshot restoration omits complete event replay. - Snapshot errors escape with a code other than INVALID_SNAPSHOT. - Input or output mutation can affect internal state. Important cases: - Missing read followed by concurrent creation. - Limited query displaced by a lexicographically earlier insertion. - TTL expires between transaction begin and commit. - Physical expiry occurs while an older transaction remains open. - Repeated puts/deletes on one key. - One commit mixes creates, updates, real deletes, and missing deletes. - Structurally valid snapshot whose event log cannot produce its stored state. Reserve scores above 9/10 for strict compilation, exact formatting, credible atomicity, correct isolation semantics, and full replay validation.