Skip to content
Source
Sign inSign up
TanStack/db
Open History to see the last commit

utils.ts

406 lines10.4 KB

1/**
2 * Simple assertion function for runtime checks.
3 * Throws an error if the condition is false.
4 */
5export function assert(
6 condition: unknown,
7 message?: string,
8): asserts condition {
9 if (!condition) {
10 throw new Error(message || `Assertion failed`)
11 }
13​
14/**
15 * A map that returns a default value for keys that are not present.
16 */
17export class DefaultMap<K, V> extends Map<K, V> {
18 constructor(
19 private defaultValue: () => V,
20 entries?: Iterable<[K, V]>,
21 ) {
22 super(entries)
23 }
24​
25 get(key: K): V {
26 if (!this.has(key)) {
27 // this.set(key, this.defaultValue())
28 return this.defaultValue()
29 }
30 return super.get(key)!
31 }
32​
33 /**
34 * Update the value for a key using a function.
35 */
36 update(key: K, updater: (value: V) => V): V {
37 const value = this.get(key)
38 const newValue = updater(value)
39 this.set(key, newValue)
40 return newValue
41 }
43​
44// JS engines have various limits on how many args can be passed to a function
45// with a spread operator, so we need to split the operation into chunks
46// 32767 is the max for Chrome 14, all others are higher
47// TODO: investigate the performance of this and other approaches
48const chunkSize = 30000
49export function chunkedArrayPush(array: Array<unknown>, other: Array<unknown>) {
50 if (other.length <= chunkSize) {
51 array.push(...other)
52 } else {
53 for (let i = 0; i < other.length; i += chunkSize) {
54 const chunk = other.slice(i, i + chunkSize)
55 array.push(...chunk)
56 }
57 }
59​
60export function binarySearch<T>(
61 array: Array<T>,
62 value: T,
63 comparator: (a: T, b: T) => number,
64): number {
65 let low = 0
66 let high = array.length
67 while (low < high) {
68 const mid = Math.floor((low + high) / 2)
69 const comparison = comparator(array[mid]!, value)
70 if (comparison < 0) {
71 low = mid + 1
72 } else if (comparison > 0) {
73 high = mid
74 } else {
75 return mid
76 }
77 }
78 return low
80​
81/**
82 * Utility for generating unique IDs for objects and values.
83 * Uses WeakMap for object reference tracking and consistent hashing for primitives.
84 */
85export class ObjectIdGenerator {
86 private objectIds = new WeakMap<object, number>()
87 private nextId = 0
88​
89 /**
90 * Get a unique identifier for any value.
91 * - Objects: Uses WeakMap for reference-based identity
92 * - Primitives: Uses consistent string-based hashing
93 */
94 getId(value: any): number {
95 // For primitives, use a simple hash of their string representation
96 if (typeof value !== `object` || value === null) {
97 const str = String(value)
98 let hashValue = 0
99 for (let i = 0; i < str.length; i++) {
100 const char = str.charCodeAt(i)
101 hashValue = (hashValue << 5) - hashValue + char
102 hashValue = hashValue & hashValue // Convert to 32-bit integer
103 }
104 return hashValue
105 }
106​
107 // For objects, use WeakMap to assign unique IDs
108 if (!this.objectIds.has(value)) {
109 this.objectIds.set(value, this.nextId++)
110 }
111 return this.objectIds.get(value)!
112 }
113​
114 /**
115 * Get a string representation of the ID for use in composite keys.
116 */
117 getStringId(value: any): string {
118 if (value === null) return `null`
119 if (value === undefined) return `undefined`
120 if (typeof value !== `object`) return `str_${String(value)}`
121​
122 return `obj_${this.getId(value)}`
123 }
125​
126/**
127 * Global instance for cases where a shared object ID space is needed.
128 */
129export const globalObjectIdGenerator = new ObjectIdGenerator()
130​
131export function* concatIterable<T>(
132 ...iterables: Array<Iterable<T>>
133): Iterable<T> {
134 for (const iterable of iterables) {
135 yield* iterable
136 }
138​
139export function* mapIterable<T, U>(
140 it: Iterable<T>,
141 fn: (t: T) => U,
142): Iterable<U> {
143 for (const t of it) {
144 yield fn(t)
145 }
147​
148export type HRange = [number, number] // half-open [start, end[ i.e. end is exclusive
149​
150/**
151 * Computes the difference between two half-open ranges.
152 * @param a - The first half-open range
153 * @param b - The second half-open range
154 * @returns The difference between the two ranges
155 */
156export function diffHalfOpen(a: HRange, b: HRange) {
157 const [a1, a2] = a
158 const [b1, b2] = b
159​
160 // A \ B can be up to two segments (left and right of the overlap)
161 const onlyInA: Array<number> = [
162 ...range(a1, Math.min(a2, b1)), // left side of A outside B
163 ...range(Math.max(a1, b2), a2), // right side of A outside B
164 ]
165​
166 // B \ A similarly
167 const onlyInB: Array<number> = [
168 ...range(b1, Math.min(b2, a1)),
169 ...range(Math.max(b1, a2), b2),
170 ]
171​
172 return { onlyInA, onlyInB }
174​
175function range(start: number, end: number): Array<number> {
176 const out: Array<number> = []
177 for (let i = start; i < end; i++) out.push(i)
178 return out
180​
181/**
182 * Compares two keys (string | number) in a consistent, deterministic way.
183 * Handles mixed types by ordering strings before numbers.
184 */
185export function compareKeys(a: string | number, b: string | number): number {
186 // Same type: compare directly
187 if (typeof a === typeof b) {
188 if (a < b) return -1
189 if (a > b) return 1
190 return 0
191 }
192 // Different types: strings come before numbers
193 return typeof a === `string` ? -1 : 1
195​
196type CanonicalValue =
197 | readonly [`undefined`]
198 | readonly [`null`]
199 | readonly [`boolean`, boolean]
200 | readonly [`number`, number | `NaN` | `Infinity` | `-Infinity`]
201 | readonly [`bigint`, string]
202 | readonly [`string`, string]
203 | readonly [`date`, number | `Invalid`]
204 | readonly [`regexp`, string, string]
205 | readonly [`bytes`, Array<number>]
206 | readonly [`array`, Array<CanonicalValue>]
207 | readonly [`map`, Array<readonly [CanonicalValue, CanonicalValue]>]
208 | readonly [`set`, Array<CanonicalValue>]
209 | readonly [`object`, Array<readonly [string, CanonicalValue]>]
210​
211/**
212 * Serializes a supported query value into one canonical key.
213 *
214 * JSON's native encoding is not suitable for relation keys: it merges BigInt
215 * with strings when a replacer is used, merges NaN with null, drops undefined,
216 * and depends on object insertion order. Ordinary JSON values keep their
217 * established wire form. Values that need richer types use a reserved prefix
218 * plus a structural, type-tagged encoding.
219 */
220export function serializeValue(value: unknown): string {
221 if (isJsonSafeStructuralValue(value, new Set())) {
222 return JSON.stringify(toStableJsonValue(value))
223 }
224​
225 return `~${JSON.stringify(toCanonicalValue(value, new Set()))}`
227​
228type JsonValue =
229 | null
230 | boolean
231 | number
232 | string
233 | Array<JsonValue>
234 | { [key: string]: JsonValue }
235​
236function isJsonSafeStructuralValue(
237 value: unknown,
238 ancestors: Set<object>,
239): boolean {
240 if (value === null) return true
241​
242 switch (typeof value) {
243 case `boolean`:
244 case `string`:
245 return true
246 case `number`:
247 return Number.isFinite(value)
248 case `undefined`:
249 case `bigint`:
250 case `symbol`:
251 case `function`:
252 return false
253 }
254​
255 return withAcyclicValue(value, ancestors, () => {
256 if (
257 value instanceof Date ||
258 value instanceof RegExp ||
259 value instanceof Uint8Array ||
260 value instanceof Map ||
261 value instanceof Set
262 ) {
263 return false
264 }
265​
266 return Array.isArray(value)
267 ? value.every((item) => isJsonSafeStructuralValue(item, ancestors))
268 : Object.keys(value).every((key) =>
269 isJsonSafeStructuralValue(
270 (value as Record<string, unknown>)[key],
271 ancestors,
272 ),
273 )
274 })
276​
277function toStableJsonValue(value: unknown): JsonValue {
278 if (
279 value === null ||
280 typeof value === `boolean` ||
281 typeof value === `number` ||
282 typeof value === `string`
283 ) {
284 return value
285 }
286​
287 if (Array.isArray(value)) {
288 return value.map(toStableJsonValue)
289 }
290​
291 return Object.fromEntries(
292 Object.keys(value as object)
293 .sort()
294 .map((key) => [
295 key,
296 toStableJsonValue((value as Record<string, unknown>)[key]),
297 ]),
298 )
300​
301function toCanonicalValue(
302 value: unknown,
303 ancestors: Set<object>,
304): CanonicalValue {
305 if (value === undefined) return [`undefined`]
306 if (value === null) return [`null`]
307​
308 switch (typeof value) {
309 case `boolean`:
310 return [`boolean`, value]
311 case `number`:
312 if (Number.isNaN(value)) return [`number`, `NaN`]
313 if (value === Infinity) return [`number`, `Infinity`]
314 if (value === -Infinity) return [`number`, `-Infinity`]
315 return [`number`, value === 0 ? 0 : value]
316 case `bigint`:
317 return [`bigint`, value.toString()]
318 case `string`:
319 return [`string`, value]
320 case `symbol`:
321 case `function`:
322 throw new TypeError(
323 `Cannot serialize ${typeof value} as a structural relation key`,
324 )
325 }
326​
327 return withAcyclicValue(value, ancestors, () => {
328 if (value instanceof Date) {
329 const timestamp = value.getTime()
330 return Number.isNaN(timestamp)
331 ? ([`date`, `Invalid`] as const)
332 : ([`date`, timestamp] as const)
333 }
334​
335 if (value instanceof RegExp) {
336 return [`regexp`, value.source, value.flags]
337 }
338​
339 if (value instanceof Uint8Array) {
340 return [`bytes`, Array.from(value)]
341 }
342​
343 if (Array.isArray(value)) {
344 return [`array`, value.map((item) => toCanonicalValue(item, ancestors))]
345 }
346​
347 if (value instanceof Map) {
348 const entries = [...value.entries()].map(
349 ([key, entryValue]) =>
350 [
351 toCanonicalValue(key, ancestors),
352 toCanonicalValue(entryValue, ancestors),
353 ] as const,
354 )
355 entries.sort((left, right) =>
356 compareSerializedValues(JSON.stringify(left), JSON.stringify(right)),
357 )
358 return [`map`, entries]
359 }
360​
361 if (value instanceof Set) {
362 const entries = [...value].map((entry) =>
363 toCanonicalValue(entry, ancestors),
364 )
365 entries.sort((left, right) =>
366 compareSerializedValues(JSON.stringify(left), JSON.stringify(right)),
367 )
368 return [`set`, entries]
369 }
370​
371 const entries = Object.keys(value)
372 .sort()
373 .map(
374 (key) =>
375 [
376 key,
377 toCanonicalValue(
378 (value as Record<string, unknown>)[key],
379 ancestors,
380 ),
381 ] as const,
382 )
383 return [`object`, entries]
384 })
386​
387function compareSerializedValues(left: string, right: string): number {
388 return left < right ? -1 : left > right ? 1 : 0
390​
391function withAcyclicValue<T>(
392 value: object,
393 ancestors: Set<object>,
394 encode: () => T,
395): T {
396 if (ancestors.has(value)) {
397 throw new TypeError(`Cannot serialize a cyclic structural relation key`)
398 }
399​
400 ancestors.add(value)
401 try {
402 return encode()
403 } finally {
404 ancestors.delete(value)
405 }