Brunobkr/llama.cpp_AlgMor24_github

1import {2	DevalueError,3	enumerable_symbols,4	escaped,5	get_type,6	is_plain_object,7	is_primitive,8	stringify_key,9	stringify_string,10	valid_array_indices11} from './utils.js';12 13const chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_$';14const unsafe_chars = /[<\b\f\n\r\t\0\u2028\u2029]/g;15const reserved =16	/^(?:do|if|in|for|int|let|new|try|var|byte|case|char|else|enum|goto|long|this|void|with|await|break|catch|class|const|final|float|short|super|throw|while|yield|delete|double|export|import|native|return|switch|throws|typeof|boolean|default|extends|finally|package|private|abstract|continue|debugger|function|volatile|interface|protected|transient|implements|instanceof|synchronized)$/;17 18/**19 * Turn a value into the JavaScript that creates an equivalent value20 * @param {any} value21 * @param {(value: any, uneval: (value: any) => string) => string | void} [replacer]22 */23export function uneval(value, replacer) {24	const counts = new Map();25 26	/** @type {string[]} */27	const keys = [];28 29	const custom = new Map();30 31	/** @param {any} thing */32	function walk(thing) {33		if (!is_primitive(thing)) {34			if (counts.has(thing)) {35				counts.set(thing, counts.get(thing) + 1);36				return;37			}38 39			counts.set(thing, 1);40 41			if (replacer) {42				const str = replacer(thing, (value) => uneval(value, replacer));43 44				if (typeof str === 'string') {45					custom.set(thing, str);46					return;47				}48			}49 50			if (typeof thing === 'function') {51				throw new DevalueError(`Cannot stringify a function`, keys, thing, value);52			}53 54			const type = get_type(thing);55 56			switch (type) {57				case 'Number':58				case 'BigInt':59				case 'String':60				case 'Boolean':61				case 'Date':62				case 'RegExp':63				case 'URL':64				case 'URLSearchParams':65					return;66 67				case 'Array':68					/** @type {any[]} */ (thing).forEach((value, i) => {69						keys.push(`[${i}]`);70						walk(value);71						keys.pop();72					});73					break;74 75				case 'Set':76					Array.from(thing).forEach(walk);77					break;78 79				case 'Map':80					for (const [key, value] of thing) {81						keys.push(`.get(${is_primitive(key) ? stringify_primitive(key) : '...'})`);82						walk(value);83						keys.pop();84					}85					break;86 87				case 'Int8Array':88				case 'Uint8Array':89				case 'Uint8ClampedArray':90				case 'Int16Array':91				case 'Uint16Array':92				case 'Float16Array':93				case 'Int32Array':94				case 'Uint32Array':95				case 'Float32Array':96				case 'Float64Array':97				case 'BigInt64Array':98				case 'BigUint64Array':99				case 'DataView':100					walk(thing.buffer);101					return;102 103				case 'ArrayBuffer':104					return;105 106				case 'Temporal.Duration':107				case 'Temporal.Instant':108				case 'Temporal.PlainDate':109				case 'Temporal.PlainTime':110				case 'Temporal.PlainDateTime':111				case 'Temporal.PlainMonthDay':112				case 'Temporal.PlainYearMonth':113				case 'Temporal.ZonedDateTime':114					return;115 116				default:117					if (!is_plain_object(thing)) {118						throw new DevalueError(`Cannot stringify arbitrary non-POJOs`, keys, thing, value);119					}120 121					if (enumerable_symbols(thing).length > 0) {122						throw new DevalueError(`Cannot stringify POJOs with symbolic keys`, keys, thing, value);123					}124 125					for (const key of Object.keys(thing)) {126						if (key === '__proto__') {127							throw new DevalueError(128								`Cannot stringify objects with __proto__ keys`,129								keys,130								thing,131								value132							);133						}134 135						keys.push(stringify_key(key));136						walk(thing[key]);137						keys.pop();138					}139			}140		} else if (typeof thing === 'symbol') {141			throw new DevalueError(`Cannot stringify a Symbol primitive`, keys, thing, value);142		}143	}144 145	walk(value);146 147	const names = new Map();148 149	Array.from(counts)150		.filter((entry) => entry[1] > 1)151		.sort((a, b) => b[1] - a[1])152		.forEach((entry, i) => {153			names.set(entry[0], get_name(i));154		});155 156	/**157	 * @param {any} thing158	 * @returns {string}159	 */160	function stringify(thing) {161		if (names.has(thing)) {162			return names.get(thing);163		}164 165		if (is_primitive(thing)) {166			return stringify_primitive(thing);167		}168 169		if (custom.has(thing)) {170			return custom.get(thing);171		}172 173		const type = get_type(thing);174 175		switch (type) {176			case 'Number':177			case 'String':178			case 'Boolean':179			case 'BigInt':180				return `Object(${stringify(thing.valueOf())})`;181 182			case 'RegExp':183				const { source, flags } = thing;184				return flags185					? `new RegExp(${stringify_string(source)},"${flags}")`186					: `new RegExp(${stringify_string(source)})`;187 188			case 'Date':189				return `new Date(${thing.getTime()})`;190 191			case 'URL':192				return `new URL(${stringify_string(thing.toString())})`;193 194			case 'URLSearchParams':195				return `new URLSearchParams(${stringify_string(thing.toString())})`;196 197			case 'Array': {198				// For dense arrays (no holes), we iterate normally.199				// When we encounter the first hole, we call Object.keys200				// to determine the sparseness, then decide between:201				//   - Array literal with holes: [,"a",,] (default)202				//   - Object.assign: Object.assign(Array(n),{...}) (for very sparse arrays)203				// Only the Object.assign path avoids iterating every slot, which204				// is what protects against the DoS of e.g. `arr[1000000] = 1`.205				let has_holes = false;206 207				let result = '[';208 209				for (let i = 0; i < thing.length; i += 1) {210					if (i > 0) result += ',';211 212					if (Object.hasOwn(thing, i)) {213						result += stringify(thing[i]);214					} else if (!has_holes) {215						// Decide between array literal and Object.assign.216						//217						// Array literal: holes are consecutive commas.218						// For example, [, "a", ,] is written as [,"a",,].219						// Each hole costs 1 char (a comma).220						//221						// Object.assign: populated indices are listed explicitly.222						// For example, [, "a", ,] would be written as223						// Object.assign(Array(3),{1:"a"}). This avoids paying224						// per-hole, but has a large fixed overhead for the225						// "Object.assign(Array(n),{...})" wrapper, and each226						// element costs extra chars for its index and colon.227						//228						// The serialized values are the same size either way, so229						// the choice comes down to the structural overhead:230						//231						//   Array literal overhead:232						//     1 char per element or hole (comma separators)233						//     + 2 chars for "[" and "]"234						//     = L + 2235						//236						//   Object.assign overhead:237						//     "Object.assign(Array(" — 20 chars238						//     + length              — d chars239						//     + "),{"               — 3 chars240						//     + for each populated element:241						//       index + ":" + ","   — (d + 2) chars242						//     + "})"                — 2 chars243						//     = (25 + d) + P * (d + 2)244						//245						// where L is the array length, P is the number of246						// populated elements, and d is the number of digits247						// in L (an upper bound on the digits in any index).248						//249						// Object.assign is cheaper when:250						//   (25 + d) + P * (d + 2) < L + 2251						const populated_keys = valid_array_indices(/** @type {any[]} */ (thing));252						const population = populated_keys.length;253						const d = String(thing.length).length;254 255						const hole_cost = thing.length + 2;256						const sparse_cost = 25 + d + population * (d + 2);257 258						if (hole_cost > sparse_cost) {259							const entries = populated_keys.map((k) => `${k}:${stringify(thing[k])}`).join(',');260							return `Object.assign(Array(${thing.length}),{${entries}})`;261						}262 263						// Re-process this index as a hole in the array literal264						has_holes = true;265						i -= 1;266					}267					// else: already decided on array literal, hole is just an empty slot268					// (the comma separator is all we need — no content for this position)269				}270 271				const tail = thing.length === 0 || thing.length - 1 in thing ? '' : ',';272				return result + tail + ']';273			}274 275			case 'Set':276			case 'Map':277				return `new ${type}([${Array.from(thing).map(stringify).join(',')}])`;278 279			case 'Int8Array':280			case 'Uint8Array':281			case 'Uint8ClampedArray':282			case 'Int16Array':283			case 'Uint16Array':284			case 'Float16Array':285			case 'Int32Array':286			case 'Uint32Array':287			case 'Float32Array':288			case 'Float64Array':289			case 'BigInt64Array':290			case 'BigUint64Array': {291				let str = `new ${type}`;292 293				if (!names.has(thing.buffer)) {294					const array = new thing.constructor(thing.buffer);295					str += `([${array}])`;296				} else {297					str += `(${stringify(thing.buffer)})`;298				}299 300				// handle subarrays301				if (thing.byteLength !== thing.buffer.byteLength) {302					const start = thing.byteOffset / thing.BYTES_PER_ELEMENT;303					const end = start + thing.length;304					str += `.subarray(${start},${end})`;305				}306 307				return str;308			}309 310			case 'DataView': {311				let str = `new DataView`;312 313				if (!names.has(thing.buffer)) {314					str += `(new Uint8Array([${new Uint8Array(thing.buffer)}]).buffer`;315				} else {316					str += `(${stringify(thing.buffer)}`;317				}318 319				// handle subviews320				if (thing.byteLength !== thing.buffer.byteLength) {321					str += `,${thing.startOffset},${thing.byteLength}`;322				}323 324				return str + ')';325			}326 327			case 'ArrayBuffer': {328				const ui8 = new Uint8Array(thing);329				return `new Uint8Array([${ui8.toString()}]).buffer`;330			}331 332			case 'Temporal.Duration':333			case 'Temporal.Instant':334			case 'Temporal.PlainDate':335			case 'Temporal.PlainTime':336			case 'Temporal.PlainDateTime':337			case 'Temporal.PlainMonthDay':338			case 'Temporal.PlainYearMonth':339			case 'Temporal.ZonedDateTime':340				return `${type}.from(${stringify_string(thing.toString())})`;341 342			default:343				const keys = Object.keys(thing);344				const obj = keys.map((key) => `${safe_key(key)}:${stringify(thing[key])}`).join(',');345				const proto = Object.getPrototypeOf(thing);346				if (proto === null) {347					return keys.length > 0 ? `{${obj},__proto__:null}` : `{__proto__:null}`;348				}349 350				return `{${obj}}`;351		}352	}353 354	const str = stringify(value);355 356	if (names.size) {357		/** @type {string[]} */358		const params = [];359 360		/** @type {string[]} */361		const statements = [];362 363		/** @type {string[]} */364		const values = [];365 366		names.forEach((name, thing) => {367			params.push(name);368 369			if (custom.has(thing)) {370				values.push(/** @type {string} */ (custom.get(thing)));371				return;372			}373 374			if (is_primitive(thing)) {375				values.push(stringify_primitive(thing));376				return;377			}378 379			const type = get_type(thing);380 381			switch (type) {382				case 'Number':383				case 'String':384				case 'Boolean':385				case 'BigInt':386					values.push(`Object(${stringify(thing.valueOf())})`);387					break;388 389				case 'RegExp':390					const { source, flags } = thing;391					const regexp = flags392						? `new RegExp(${stringify_string(source)},"${flags}")`393						: `new RegExp(${stringify_string(source)})`394					values.push(regexp);395					break;396 397				case 'Date':398					values.push(`new Date(${thing.getTime()})`);399					break;400 401				case 'URL':402					values.push(`new URL(${stringify_string(thing.toString())})`);403					break;404 405				case 'URLSearchParams':406					values.push(`new URLSearchParams(${stringify_string(thing.toString())})`);407					break;408 409				case 'Array':410					values.push(`Array(${thing.length})`);411					/** @type {any[]} */ (thing).forEach((v, i) => {412						statements.push(`${name}[${i}]=${stringify(v)}`);413					});414					break;415 416				case 'Set':417					values.push(`new Set`);418					statements.push(419						`${name}.${Array.from(thing)420							.map((v) => `add(${stringify(v)})`)421							.join('.')}`422					);423					break;424 425				case 'Map':426					values.push(`new Map`);427					statements.push(428						`${name}.${Array.from(thing)429							.map(([k, v]) => `set(${stringify(k)}, ${stringify(v)})`)430							.join('.')}`431					);432					break;433 434				case 'Int8Array':435				case 'Uint8Array':436				case 'Uint8ClampedArray':437				case 'Int16Array':438				case 'Uint16Array':439				case 'Float16Array':440				case 'Int32Array':441				case 'Uint32Array':442				case 'Float32Array':443				case 'Float64Array':444				case 'BigInt64Array':445				case 'BigUint64Array': {446					let str = `new ${type}`;447 448					if (!names.has(thing.buffer)) {449						const array = new thing.constructor(thing.buffer);450						str += `([${array}])`;451					} else {452						str += `(${stringify(thing.buffer)})`;453					}454 455					// handle subarrays456					if (thing.byteLength !== thing.buffer.byteLength) {457						const start = thing.byteOffset / thing.BYTES_PER_ELEMENT;458						const end = start + thing.length;459						str += `.subarray(${start},${end})`;460					}461 462					values.push(`{}`);463					statements.push(`${name}=${str}`);464					break;465				}466 467				case 'DataView': {468					let str = `new DataView`;469 470					if (!names.has(thing.buffer)) {471						str += `(new Uint8Array([${new Uint8Array(thing.buffer)}]).buffer`;472					} else {473						str += `(${stringify(thing.buffer)}`;474					}475 476					// handle subviews477					if (thing.byteLength !== thing.buffer.byteLength) {478						str += `,${thing.byteOffset},${thing.byteLength}`;479					}480 481					str += ')';482 483					values.push(`{}`);484					statements.push(`${name}=${str}`);485					break;486				}487 488				case 'ArrayBuffer':489					values.push(`new Uint8Array([${new Uint8Array(thing)}]).buffer`);490					break;491 492				default:493					values.push(Object.getPrototypeOf(thing) === null ? 'Object.create(null)' : '{}');494					Object.keys(thing).forEach((key) => {495						statements.push(`${name}${safe_prop(key)}=${stringify(thing[key])}`);496					});497			}498		});499 500		statements.push(`return ${str}`);501 502		return `(function(${params.join(',')}){${statements.join(';')}}(${values.join(',')}))`;503	} else {504		return str;505	}506}507 508/** @param {number} num */509function get_name(num) {510	let name = '';511 512	do {513		name = chars[num % chars.length] + name;514		num = ~~(num / chars.length) - 1;515	} while (num >= 0);516 517	return reserved.test(name) ? `${name}0` : name;518}519 520/** @param {string} c */521function escape_unsafe_char(c) {522	return escaped[c] || c;523}524 525/** @param {string} str */526function escape_unsafe_chars(str) {527	return str.replace(unsafe_chars, escape_unsafe_char);528}529 530/** @param {string} key */531function safe_key(key) {532	return /^[_$a-zA-Z][_$a-zA-Z0-9]*$/.test(key) ? key : escape_unsafe_chars(JSON.stringify(key));533}534 535/** @param {string} key */536function safe_prop(key) {537	return /^[_$a-zA-Z][_$a-zA-Z0-9]*$/.test(key)538		? `.${key}`539		: `[${escape_unsafe_chars(JSON.stringify(key))}]`;540}541 542/** @param {any} thing */543function stringify_primitive(thing) {544	const type = typeof thing;545	if (type === 'string') return stringify_string(thing);546	if (thing === void 0) return 'void 0';547	if (thing === 0 && 1 / thing < 0) return '-0';548	const str = String(thing);549	if (type === 'number') return str.replace(/^(-)?0\./, '$1.');550	if (type === 'bigint') return thing + 'n';551	return str;552}553