const require_types = require("./serde/types.cjs");
const require_base = require("./base.cjs");
//#region src/memory.ts
/**
* Keys that, when written into a plain JavaScript object via bracket
* notation, traverse the prototype chain and mutate `Object.prototype`
* (or the constructor) instead of creating a new own property. Any of
* the three reaches `Object.prototype` and pollutes every object in
* the running process. CWE-1321 (Prototype Pollution).
*/
const POLLUTION_KEYS = new Set([
	"__proto__",
	"constructor",
	"prototype"
]);
/**
* Asserts that a value sourced from {@link RunnableConfig.configurable} (or
* any other caller-influenced position) is safe to use as a property key
* on the in-memory checkpoint store.
*
* `MemorySaver` keeps state in two nested plain objects (`storage` and
* `writes`) and writes to them with bracket notation:
*
*     this.storage[threadId][checkpointNamespace][checkpoint.id] = ...
*
* Without this guard a `threadId` of `"__proto__"` (or `"constructor"`)
* resolves through the prototype chain, and the subsequent assignment
* mutates `Object.prototype`. From that point every plain object in the
* process inherits the injected property: `for...in` loops over unrelated
* objects iterate it, framework code that does `if (obj[x])` short-circuits
* unexpectedly, and downstream serializers may emit it. In a Node.js
* server this is a stepping stone to remote code execution.
*
* `MemorySaver` is the default saver used by every quickstart, every
* tutorial, and most test fixtures, so this guard runs in the hot path
* for the most common LangGraph configuration.
*
* @param field Name of the configurable field, used in the error message.
* @param value Value to validate. Must be a non-empty string that is not
*              one of the three prototype-pollution keys.
* @param options.allowEmpty When true the empty string is accepted, used
*                            for the documented empty `checkpoint_ns`
*                            default; otherwise an empty string is
*                            rejected the same way as a non-string.
*/
function assertSafeStorageKey(field, value, options = {}) {
	const { allowEmpty = false } = options;
	if (typeof value !== "string") {
		const observed = value === null ? "null" : value === void 0 ? "undefined" : Array.isArray(value) ? "array" : typeof value;
		throw new Error(`Invalid configurable value for key "${field}": expected a string identifier (got ${observed}). This guard protects MemorySaver from prototype pollution.`);
	}
	if (!allowEmpty && value === "") throw new Error(`Invalid configurable value for key "${field}": empty string is not permitted as an in-memory storage key.`);
	if (POLLUTION_KEYS.has(value)) throw new Error(`Invalid configurable value for key "${field}": value "${value}" is reserved (would mutate Object.prototype). This guard protects MemorySaver from prototype pollution.`);
}
function _generateKey(threadId, checkpointNamespace, checkpointId) {
	return JSON.stringify([
		threadId,
		checkpointNamespace,
		checkpointId
	]);
}
function _parseKey(key) {
	const [threadId, checkpointNamespace, checkpointId] = JSON.parse(key);
	return {
		threadId,
		checkpointNamespace,
		checkpointId
	};
}
var MemorySaver = class extends require_base.BaseCheckpointSaver {
	storage = Object.create(null);
	writes = Object.create(null);
	constructor(serde) {
		super(serde);
	}
	/** @internal */
	async _migratePendingSends(mutableCheckpoint, threadId, checkpointNs, parentCheckpointId) {
		const deseriablizableCheckpoint = mutableCheckpoint;
		const parentKey = _generateKey(threadId, checkpointNs, parentCheckpointId);
		const pendingSends = await Promise.all(Object.values(this.writes[parentKey] ?? {}).filter(([_taskId, channel]) => channel === require_types.TASKS).map(async ([_taskId, _channel, writes]) => await this.serde.loadsTyped("json", writes)));
		deseriablizableCheckpoint.channel_values ??= {};
		deseriablizableCheckpoint.channel_values[require_types.TASKS] = pendingSends;
		deseriablizableCheckpoint.channel_versions ??= {};
		deseriablizableCheckpoint.channel_versions[require_types.TASKS] = Object.keys(deseriablizableCheckpoint.channel_versions).length > 0 ? require_base.maxChannelVersion(...Object.values(deseriablizableCheckpoint.channel_versions)) : this.getNextVersion(void 0);
	}
	async getTuple(config) {
		const thread_id = config.configurable?.thread_id;
		const checkpoint_ns = config.configurable?.checkpoint_ns ?? "";
		let checkpoint_id = require_base.getCheckpointId(config);
		if (thread_id !== void 0) assertSafeStorageKey("thread_id", thread_id);
		assertSafeStorageKey("checkpoint_ns", checkpoint_ns, { allowEmpty: true });
		if (checkpoint_id) assertSafeStorageKey("checkpoint_id", checkpoint_id);
		if (checkpoint_id) {
			const saved = this.storage[thread_id]?.[checkpoint_ns]?.[checkpoint_id];
			if (saved !== void 0) {
				const [checkpoint, metadata, parentCheckpointId] = saved;
				const key = _generateKey(thread_id, checkpoint_ns, checkpoint_id);
				const deserializedCheckpoint = await this.serde.loadsTyped("json", checkpoint);
				if (deserializedCheckpoint.v < 4 && parentCheckpointId !== void 0) await this._migratePendingSends(deserializedCheckpoint, thread_id, checkpoint_ns, parentCheckpointId);
				const pendingWrites = await Promise.all(Object.values(this.writes[key] || {}).map(async ([taskId, channel, value]) => {
					return [
						taskId,
						channel,
						await this.serde.loadsTyped("json", value)
					];
				}));
				const checkpointTuple = {
					config,
					checkpoint: deserializedCheckpoint,
					metadata: await this.serde.loadsTyped("json", metadata),
					pendingWrites
				};
				if (parentCheckpointId !== void 0) checkpointTuple.parentConfig = { configurable: {
					thread_id,
					checkpoint_ns,
					checkpoint_id: parentCheckpointId
				} };
				return checkpointTuple;
			}
		} else {
			const checkpoints = this.storage[thread_id]?.[checkpoint_ns];
			if (checkpoints !== void 0) {
				checkpoint_id = Object.keys(checkpoints).sort((a, b) => b.localeCompare(a))[0];
				const [checkpoint, metadata, parentCheckpointId] = checkpoints[checkpoint_id];
				const key = _generateKey(thread_id, checkpoint_ns, checkpoint_id);
				const deserializedCheckpoint = await this.serde.loadsTyped("json", checkpoint);
				if (deserializedCheckpoint.v < 4 && parentCheckpointId !== void 0) await this._migratePendingSends(deserializedCheckpoint, thread_id, checkpoint_ns, parentCheckpointId);
				const pendingWrites = await Promise.all(Object.values(this.writes[key] || {}).map(async ([taskId, channel, value]) => {
					return [
						taskId,
						channel,
						await this.serde.loadsTyped("json", value)
					];
				}));
				const checkpointTuple = {
					config: { configurable: {
						thread_id,
						checkpoint_id,
						checkpoint_ns
					} },
					checkpoint: deserializedCheckpoint,
					metadata: await this.serde.loadsTyped("json", metadata),
					pendingWrites
				};
				if (parentCheckpointId !== void 0) checkpointTuple.parentConfig = { configurable: {
					thread_id,
					checkpoint_ns,
					checkpoint_id: parentCheckpointId
				} };
				return checkpointTuple;
			}
		}
	}
	async *list(config, options) {
		let { before, limit, filter } = options ?? {};
		if (config.configurable?.thread_id !== void 0) assertSafeStorageKey("thread_id", config.configurable.thread_id);
		if (config.configurable?.checkpoint_ns !== void 0) assertSafeStorageKey("checkpoint_ns", config.configurable.checkpoint_ns, { allowEmpty: true });
		if (config.configurable?.checkpoint_id) assertSafeStorageKey("checkpoint_id", config.configurable.checkpoint_id);
		if (before?.configurable?.checkpoint_id) assertSafeStorageKey("checkpoint_id", before.configurable.checkpoint_id);
		const threadIds = config.configurable?.thread_id ? [config.configurable?.thread_id] : Object.keys(this.storage);
		const configCheckpointNamespace = config.configurable?.checkpoint_ns;
		const configCheckpointId = config.configurable?.checkpoint_id;
		for (const threadId of threadIds) for (const checkpointNamespace of Object.keys(this.storage[threadId] ?? {})) {
			if (configCheckpointNamespace !== void 0 && checkpointNamespace !== configCheckpointNamespace) continue;
			const checkpoints = this.storage[threadId]?.[checkpointNamespace] ?? {};
			const sortedCheckpoints = Object.entries(checkpoints).sort((a, b) => b[0].localeCompare(a[0]));
			for (const [checkpointId, [checkpoint, metadataStr, parentCheckpointId]] of sortedCheckpoints) {
				if (configCheckpointId && checkpointId !== configCheckpointId) continue;
				if (before && before.configurable?.checkpoint_id && checkpointId >= before.configurable.checkpoint_id) continue;
				const metadata = await this.serde.loadsTyped("json", metadataStr);
				if (filter && !Object.entries(filter).every(([key, value]) => metadata[key] === value)) continue;
				if (limit !== void 0) {
					if (limit <= 0) break;
					limit -= 1;
				}
				const key = _generateKey(threadId, checkpointNamespace, checkpointId);
				const writes = Object.values(this.writes[key] || {});
				const pendingWrites = await Promise.all(writes.map(async ([taskId, channel, value]) => {
					return [
						taskId,
						channel,
						await this.serde.loadsTyped("json", value)
					];
				}));
				const deserializedCheckpoint = await this.serde.loadsTyped("json", checkpoint);
				if (deserializedCheckpoint.v < 4 && parentCheckpointId !== void 0) await this._migratePendingSends(deserializedCheckpoint, threadId, checkpointNamespace, parentCheckpointId);
				const checkpointTuple = {
					config: { configurable: {
						thread_id: threadId,
						checkpoint_ns: checkpointNamespace,
						checkpoint_id: checkpointId
					} },
					checkpoint: deserializedCheckpoint,
					metadata,
					pendingWrites
				};
				if (parentCheckpointId !== void 0) checkpointTuple.parentConfig = { configurable: {
					thread_id: threadId,
					checkpoint_ns: checkpointNamespace,
					checkpoint_id: parentCheckpointId
				} };
				yield checkpointTuple;
			}
		}
	}
	async put(config, checkpoint, metadata) {
		const preparedCheckpoint = require_base.copyCheckpoint(checkpoint);
		const threadId = config.configurable?.thread_id;
		const checkpointNamespace = config.configurable?.checkpoint_ns ?? "";
		if (threadId === void 0) throw new Error("Failed to put checkpoint. The passed RunnableConfig is missing a required \"thread_id\" field in its \"configurable\" property. When using a checkpointer, you must pass a \"thread_id\" so the checkpointer knows which conversation thread to persist state for. Example: graph.stream(input, { configurable: { thread_id: \"my-thread-id\" } })");
		assertSafeStorageKey("thread_id", threadId);
		assertSafeStorageKey("checkpoint_ns", checkpointNamespace, { allowEmpty: true });
		assertSafeStorageKey("checkpoint_id", checkpoint.id);
		if (!this.storage[threadId]) this.storage[threadId] = Object.create(null);
		if (!this.storage[threadId][checkpointNamespace]) this.storage[threadId][checkpointNamespace] = Object.create(null);
		const [[, serializedCheckpoint], [, serializedMetadata]] = await Promise.all([this.serde.dumpsTyped(preparedCheckpoint), this.serde.dumpsTyped(metadata)]);
		this.storage[threadId][checkpointNamespace][checkpoint.id] = [
			serializedCheckpoint,
			serializedMetadata,
			config.configurable?.checkpoint_id
		];
		return { configurable: {
			thread_id: threadId,
			checkpoint_ns: checkpointNamespace,
			checkpoint_id: checkpoint.id
		} };
	}
	async putWrites(config, writes, taskId) {
		const threadId = config.configurable?.thread_id;
		const checkpointNamespace = config.configurable?.checkpoint_ns;
		const checkpointId = config.configurable?.checkpoint_id;
		if (threadId === void 0) throw new Error("Failed to put writes. The passed RunnableConfig is missing a required \"thread_id\" field in its \"configurable\" property. When using a checkpointer, you must pass a \"thread_id\" so the checkpointer knows which conversation thread to persist state for. Example: graph.stream(input, { configurable: { thread_id: \"my-thread-id\" } })");
		if (checkpointId === void 0) throw new Error(`Failed to put writes. The passed RunnableConfig is missing a required "checkpoint_id" field in its "configurable" property.`);
		assertSafeStorageKey("thread_id", threadId);
		assertSafeStorageKey("checkpoint_ns", checkpointNamespace, { allowEmpty: true });
		assertSafeStorageKey("checkpoint_id", checkpointId);
		assertSafeStorageKey("task_id", taskId);
		const outerKey = _generateKey(threadId, checkpointNamespace, checkpointId);
		const outerWrites_ = this.writes[outerKey];
		if (this.writes[outerKey] === void 0) this.writes[outerKey] = Object.create(null);
		await Promise.all(writes.map(async ([channel, value], idx) => {
			const [, serializedValue] = await this.serde.dumpsTyped(value);
			const innerKey = [taskId, require_base.WRITES_IDX_MAP[channel] || idx];
			const innerKeyStr = `${innerKey[0]},${innerKey[1]}`;
			if (innerKey[1] >= 0 && outerWrites_ && innerKeyStr in outerWrites_) return;
			this.writes[outerKey][innerKeyStr] = [
				taskId,
				channel,
				serializedValue
			];
		}));
	}
	async deleteThread(threadId) {
		assertSafeStorageKey("thread_id", threadId);
		delete this.storage[threadId];
		for (const key of Object.keys(this.writes)) if (_parseKey(key).threadId === threadId) delete this.writes[key];
	}
	/**
	* Override: walk the parent chain ONCE for all requested channels using
	* direct storage access.
	*
	* Each channel terminates independently at the nearest ancestor whose
	* stored `channel_values[ch]` is populated. Other channels keep walking
	* until they find their own terminator or hit the root.
	*
	* The seed value (whether a `DeltaSnapshot` or a plain pre-delta migration
	* blob) is the value AT that ancestor, prior to its own pending writes that
	* produce the child. Those on-path writes — including the ones stored on the
	* terminating ancestor — are always collected and replayed on top of the
	* seed, so a thread migrated from a pre-delta channel does not drop the
	* writes saved under the migration boundary checkpoint.
	*
	* @remarks Beta. See {@link BaseCheckpointSaver.getDeltaChannelHistory}.
	*/
	async getDeltaChannelHistory(options) {
		const { config, channels } = options;
		if (channels.length === 0) return {};
		const threadId = config.configurable?.thread_id;
		const checkpointNs = config.configurable?.checkpoint_ns ?? "";
		const checkpointId = require_base.getCheckpointId(config);
		if (threadId !== void 0) assertSafeStorageKey("thread_id", threadId);
		assertSafeStorageKey("checkpoint_ns", checkpointNs, { allowEmpty: true });
		const nsStorage = this.storage[threadId]?.[checkpointNs] ?? {};
		const chain = [];
		let current = (checkpointId ? nsStorage[checkpointId] : void 0)?.[2];
		while (current !== void 0) {
			const entry = nsStorage[current];
			if (entry === void 0) break;
			chain.push(current);
			current = entry[2];
		}
		const collectedByCh = {};
		const seedByCh = {};
		const remaining = new Set(channels);
		for (const ch of channels) collectedByCh[ch] = [];
		for (const cpId of chain) {
			if (remaining.size === 0) break;
			const entry = nsStorage[cpId];
			const ckpt = entry !== void 0 ? await this.serde.loadsTyped("json", entry[0]) : void 0;
			const blobValueByCh = {};
			const terminatedHere = /* @__PURE__ */ new Set();
			if (ckpt !== void 0) {
				for (const ch of remaining) if (Object.prototype.hasOwnProperty.call(ckpt.channel_values, ch) && ckpt.channel_values[ch] !== void 0) {
					blobValueByCh[ch] = ckpt.channel_values[ch];
					terminatedHere.add(ch);
				}
			}
			const stepWritesKey = _generateKey(threadId, checkpointNs, cpId);
			const stepWrites = Object.entries(this.writes[stepWritesKey] ?? {});
			stepWrites.sort(([a], [b]) => {
				const [aTask, aIdx] = a.split(",");
				const [bTask, bIdx] = b.split(",");
				if (aTask !== bTask) return aTask < bTask ? 1 : -1;
				return Number(bIdx) - Number(aIdx);
			});
			for (const [, [tid, ch, serialized]] of stepWrites) {
				if (!remaining.has(ch)) continue;
				collectedByCh[ch].push([
					tid,
					ch,
					await this.serde.loadsTyped("json", serialized)
				]);
			}
			for (const ch of terminatedHere) {
				seedByCh[ch] = blobValueByCh[ch];
				remaining.delete(ch);
			}
		}
		const result = {};
		for (const ch of channels) {
			const entryH = { writes: collectedByCh[ch].slice().reverse() };
			if (Object.prototype.hasOwnProperty.call(seedByCh, ch)) entryH.seed = seedByCh[ch];
			result[ch] = entryH;
		}
		return result;
	}
};
//#endregion
exports.MemorySaver = MemorySaver;

//# sourceMappingURL=memory.cjs.map