Brunobkr/llama.cpp_AlgMor24_github

1import {2	DevalueError,3	enumerable_symbols,4	get_type,5	is_plain_object,6	is_primitive,7	stringify_key,8	stringify_string,9	valid_array_indices10} from './utils.js';11import {12	HOLE,13	NAN,14	NEGATIVE_INFINITY,15	NEGATIVE_ZERO,16	POSITIVE_INFINITY,17	SPARSE,18	UNDEFINED19} from './constants.js';20import { encode64 } from './base64.js';21 22/**23 * Turn a value into a JSON string that can be parsed with `devalue.parse`24 * @param {any} value25 * @param {Record<string, (value: any) => any>} [reducers]26 */27export function stringify(value, reducers) {28	const stringified = run(false, value, reducers);29	return typeof stringified === 'string' ? stringified : `[${stringified.join(',')}]`;30}31 32/**33 * Turn a value into a JSON string that can be parsed with `devalue.parse`34 * @param {any} value35 * @param {Record<string, (value: any) => any>} [reducers]36 */37export async function stringifyAsync(value, reducers) {38	const stringified = run(true, value, reducers);39 40	if (typeof stringified === 'string') {41		return stringified;42	}43 44	let out = '[';45 46	for (let i = 0; i < stringified.length; i += 1) {47		let value = stringified[i];48 49		if (typeof value !== 'string') {50			await value;51			value = stringified[i];52 53			if (i === 0 && value < 0) {54				return `${value}`;55			}56		}57 58		out += value;59 60		if (i < stringified.length - 1) {61			out += ',';62		}63	}64 65	out += ']';66 67	return out;68}69 70/**71 * @param {boolean} async72 * @param {any} value73 * @param {Record<string, (value: any) => any>} [reducers]74 */75function run(async, value, reducers) {76	/** @type {any[]} */77	const stringified = [];78 79	/** @type {Map<any, number>} */80	const indexes = new Map();81 82	/** @type {Array<{ key: string, fn: (value: any) => any }>} */83	const custom = [];84	if (reducers) {85		for (const key of Object.getOwnPropertyNames(reducers)) {86			custom.push({ key, fn: reducers[key] });87		}88	}89 90	/** @type {string[]} */91	const keys = [];92 93	let p = 0;94 95	/**96	 * @param {any} thing97	 * @param {number} [index]98	 */99	function flatten(thing, index) {100		if (thing === undefined) return UNDEFINED;101		if (Number.isNaN(thing)) return NAN;102		if (thing === Infinity) return POSITIVE_INFINITY;103		if (thing === -Infinity) return NEGATIVE_INFINITY;104		if (thing === 0 && 1 / thing < 0) return NEGATIVE_ZERO;105 106		if (indexes.has(thing)) return /** @type {number} */ (indexes.get(thing));107 108		index ??= p++;109		indexes.set(thing, index);110 111		for (const { key, fn } of custom) {112			const value = fn(thing);113			if (value) {114				stringified[index] = `["${key}",${flatten(value)}]`;115				return index;116			}117		}118 119		if (typeof thing === 'function') {120			throw new DevalueError(`Cannot stringify a function`, keys, thing, value);121		} else if (typeof thing === 'symbol') {122			throw new DevalueError(`Cannot stringify a Symbol primitive`, keys, thing, value);123		}124 125		/** @type {string | Promise<any>} */126		let str = '';127 128		if (is_primitive(thing)) {129			str = stringify_primitive(thing);130		} else if (typeof thing.then === 'function') {131			if (!async) {132				throw new DevalueError(133					`Cannot stringify a Promise or thenable — use stringifyAsync instead`,134					keys,135					thing,136					value137				);138			}139 140			str = Promise.resolve(thing).then((value) => {141				const i = flatten(value, index);142				if (i < 0) stringified[index] = i;143			});144		} else {145			const type = get_type(thing);146 147			switch (type) {148				case 'Number':149				case 'String':150				case 'Boolean':151				case 'BigInt':152					str = `["Object",${flatten(thing.valueOf())}]`;153					break;154 155				case 'Date':156					const valid = !isNaN(thing.getDate());157					str = `["Date","${valid ? thing.toISOString() : ''}"]`;158					break;159 160				case 'URL':161					str = `["URL",${stringify_string(thing.toString())}]`;162					break;163 164				case 'URLSearchParams':165					str = `["URLSearchParams",${stringify_string(thing.toString())}]`;166					break;167 168				case 'RegExp':169					const { source, flags } = thing;170					str = flags171						? `["RegExp",${stringify_string(source)},"${flags}"]`172						: `["RegExp",${stringify_string(source)}]`;173					break;174 175				case 'Array': {176					// For dense arrays (no holes), we iterate normally.177					// When we encounter the first hole, we call Object.keys178					// to determine the sparseness, then decide between:179					//   - HOLE encoding: [-2, val, -2, ...] (default)180					//   - Sparse encoding: [-7, length, idx, val, ...] (for very sparse arrays)181					// Only the sparse path avoids iterating every slot, which182					// is what protects against the DoS of e.g. `arr[1000000] = 1`.183					let mostly_dense = false;184 185					str = '[';186 187					for (let i = 0; i < thing.length; i += 1) {188						if (i > 0) str += ',';189 190						if (Object.hasOwn(thing, i)) {191							keys.push(`[${i}]`);192							str += flatten(thing[i]);193							keys.pop();194						} else if (mostly_dense) {195							// Use dense encoding. The heuristic guarantees the196							// array is only mildly sparse, so iterating over every197							// slot is fine.198							str += HOLE;199						} else {200							// Decide between HOLE encoding and sparse encoding.201							//202							// HOLE encoding: each hole is serialized as the HOLE203							// sentinel (-2). For example, [, "a", ,] becomes204							// [-2, 0, -2]. Each hole costs 3 chars ("-2" + comma).205							//206							// Sparse encoding: lists only populated indices.207							// For example, [, "a", ,] becomes [-7, 3, 1, 0] — the208							// -7 sentinel, the array length (3), then index-value209							// pairs. This avoids paying per-hole, but each element210							// costs extra chars to write its index.211							//212							// The values are the same size either way, so the213							// choice comes down to structural overhead:214							//215							//   HOLE overhead:216							//     3 chars per hole ("-2" + comma)217							//     = (L - P) * 3218							//219							//   Sparse overhead:220							//     "-7,"          — 3 chars (sparse sentinel + comma)221							//     + length + "," — (d + 1) chars (array length + comma)222							//     + per element: index + "," — (d + 1) chars223							//     = (4 + d) + P * (d + 1)224							//225							// where L is the array length, P is the number of226							// populated elements, and d is the number of digits227							// in L (an upper bound on the digits in any index).228							//229							// Sparse encoding is cheaper when:230							//   (4 + d) + P * (d + 1) < (L - P) * 3231							const populated_keys = valid_array_indices(/** @type {any[]} */ (thing));232							const population = populated_keys.length;233							const d = String(thing.length).length;234 235							const hole_cost = (thing.length - population) * 3;236							const sparse_cost = 4 + d + population * (d + 1);237 238							if (hole_cost > sparse_cost) {239								str = '[' + SPARSE + ',' + thing.length;240								for (let j = 0; j < populated_keys.length; j++) {241									const key = populated_keys[j];242									keys.push(`[${key}]`);243									str += ',' + key + ',' + flatten(thing[key]);244									keys.pop();245								}246								break;247							} else {248								mostly_dense = true;249								str += HOLE;250							}251						}252					}253 254					str += ']';255 256					break;257				}258 259				case 'Set':260					str = '["Set"';261 262					for (const value of thing) {263						str += `,${flatten(value)}`;264					}265 266					str += ']';267					break;268 269				case 'Map':270					str = '["Map"';271 272					for (const [key, value] of thing) {273						keys.push(`.get(${is_primitive(key) ? stringify_primitive(key) : '...'})`);274						str += `,${flatten(key)},${flatten(value)}`;275						keys.pop();276					}277 278					str += ']';279					break;280 281				case 'Int8Array':282				case 'Uint8Array':283				case 'Uint8ClampedArray':284				case 'Int16Array':285				case 'Uint16Array':286				case 'Float16Array':287				case 'Int32Array':288				case 'Uint32Array':289				case 'Float32Array':290				case 'Float64Array':291				case 'BigInt64Array':292				case 'BigUint64Array':293				case 'DataView': {294					/** @type {import("./types.js").TypedArray} */295					const typedArray = thing;296					str = '["' + type + '",' + flatten(typedArray.buffer);297 298					// handle subarrays299					if (typedArray.byteLength !== typedArray.buffer.byteLength) {300						// to be used with `new TypedArray(buffer, byteOffset, length)`301						str += `,${typedArray.byteOffset},${typedArray.length}`;302					}303 304					str += ']';305					break;306				}307 308				case 'ArrayBuffer': {309					/** @type {ArrayBuffer} */310					const arraybuffer = thing;311					const base64 = encode64(arraybuffer);312 313					str = `["ArrayBuffer","${base64}"]`;314					break;315				}316 317				case 'Temporal.Duration':318				case 'Temporal.Instant':319				case 'Temporal.PlainDate':320				case 'Temporal.PlainTime':321				case 'Temporal.PlainDateTime':322				case 'Temporal.PlainMonthDay':323				case 'Temporal.PlainYearMonth':324				case 'Temporal.ZonedDateTime':325					str = `["${type}",${stringify_string(thing.toString())}]`;326					break;327 328				default:329					if (!is_plain_object(thing)) {330						throw new DevalueError(`Cannot stringify arbitrary non-POJOs`, keys, thing, value);331					}332 333					if (enumerable_symbols(thing).length > 0) {334						throw new DevalueError(`Cannot stringify POJOs with symbolic keys`, keys, thing, value);335					}336 337					if (Object.getPrototypeOf(thing) === null) {338						str = '["null"';339						for (const key of Object.keys(thing)) {340							if (key === '__proto__') {341								throw new DevalueError(342									`Cannot stringify objects with __proto__ keys`,343									keys,344									thing,345									value346								);347							}348 349							keys.push(stringify_key(key));350							str += `,${stringify_string(key)},${flatten(thing[key])}`;351							keys.pop();352						}353						str += ']';354					} else {355						str = '{';356						let started = false;357						for (const key of Object.keys(thing)) {358							if (key === '__proto__') {359								throw new DevalueError(360									`Cannot stringify objects with __proto__ keys`,361									keys,362									thing,363									value364								);365							}366 367							if (started) str += ',';368							started = true;369							keys.push(stringify_key(key));370							str += `${stringify_string(key)}:${flatten(thing[key])}`;371							keys.pop();372						}373						str += '}';374					}375			}376		}377 378		stringified[index] = str;379		return index;380	}381 382	const index = flatten(value);383 384	// special case — value is represented as a negative index385	if (index < 0) return `${index}`;386 387	return stringified;388}389 390/**391 * @param {any} thing392 * @returns {string}393 */394function stringify_primitive(thing) {395	const type = typeof thing;396	if (type === 'string') return stringify_string(thing);397	if (thing === void 0) return UNDEFINED.toString();398	if (thing === 0 && 1 / thing < 0) return NEGATIVE_ZERO.toString();399	if (type === 'bigint') return `["BigInt","${thing}"]`;400	return String(thing);401}402