class_name SimulationDigest
extends RefCounted

## Produces a stable SHA-256 digest for snapshot-shaped Variant data.
##
## Dictionary insertion order never affects the result. Type tags and byte
## lengths make the canonical form unambiguous, and Array order remains
## significant. Runtime Objects and other process-local values are rejected;
## callers must first export them to Dictionaries, Arrays and value types.

const FORMAT_VERSION := 1
const MAX_NESTING_DEPTH := 128

# A single digest owns these caches; nothing survives a call or retains snapshot
# values. Only private arrays of immutable, homogeneous keys become cache keys.
# Separate buckets preserve the distinct String / StringName canonical tags.
const MAX_CACHED_LAYOUTS := 256
const MAX_CACHED_LAYOUT_KEYS := 32
const MAX_CACHED_KEY_LENGTH := 128

class KeyLayouts:
	extends RefCounted
	var strings: Dictionary = {}
	var names: Dictionary = {}
	# Bounded per-call immutable scalar encodings; never retain mutable containers.
	var integers: Dictionary = {}
	var text_values: Dictionary = {}
	var name_values: Dictionary = {}



static func compute(value: Variant) -> String:
	var canonical := canonical_bytes(value)
	if canonical.is_empty():
		return ""
	var context := HashingContext.new()
	if context.start(HashingContext.HASH_SHA256) != OK:
		push_error("Could not initialize the simulation digest hash")
		return ""
	context.update(canonical)
	return context.finish().hex_encode()


static func canonical_bytes(value: Variant) -> PackedByteArray:
	var output := PackedByteArray()
	_append_ascii(output, "the-tree:simulation-digest:v%d;" % FORMAT_VERSION)
	if not _encode_value(value, output, 0, KeyLayouts.new()):
		return PackedByteArray()
	return output


static func _encode_value(value: Variant, output: PackedByteArray, depth: int, layouts: KeyLayouts) -> bool:
	if depth > MAX_NESTING_DEPTH:
		push_error("SimulationDigest data exceeds the maximum nesting depth")
		return false

	match typeof(value):
		TYPE_NIL:
			_append_ascii(output, "n")
		TYPE_BOOL:
			_append_ascii(output, "b1" if bool(value) else "b0")
		TYPE_INT:
			if layouts.integers.has(value):
				output.append_array(layouts.integers[value])
			else:
				var encoded := ("i%d;" % int(value)).to_utf8_buffer()
				output.append_array(encoded)
				if layouts.integers.size() < 512: layouts.integers[value] = encoded
		TYPE_FLOAT:
			_append_ascii(output, "f")
			return _append_float64(output, float(value))
		TYPE_STRING:
			_append_cached_text(output, "s", String(value), layouts.text_values)
		TYPE_STRING_NAME:
			_append_cached_text(output, "q", String(value), layouts.name_values)
		TYPE_VECTOR2:
			var vector: Vector2 = value
			_append_ascii(output, "v2")
			return _append_float64(output, vector.x) and _append_float64(output, vector.y)
		TYPE_VECTOR2I:
			var vector: Vector2i = value
			_append_ascii(output, "w2")
			_append_ascii(output, "i%d;i%d;" % [vector.x, vector.y])
		TYPE_RECT2:
			var rect: Rect2 = value
			_append_ascii(output, "r2")
			return (
				_append_float64(output, rect.position.x)
				and _append_float64(output, rect.position.y)
				and _append_float64(output, rect.size.x)
				and _append_float64(output, rect.size.y)
			)
		TYPE_RECT2I:
			var rect: Rect2i = value
			_append_ascii(output, "x2")
			_append_ascii(output, "i%d;i%d;i%d;i%d;" % [rect.position.x, rect.position.y, rect.size.x, rect.size.y])
		TYPE_VECTOR3:
			var vector: Vector3 = value
			_append_ascii(output, "v3")
			return (
				_append_float64(output, vector.x)
				and _append_float64(output, vector.y)
				and _append_float64(output, vector.z)
			)
		TYPE_VECTOR3I:
			var vector: Vector3i = value
			_append_ascii(output, "w3")
			_append_ascii(output, "i%d;i%d;i%d;" % [vector.x, vector.y, vector.z])
		TYPE_VECTOR4:
			var vector: Vector4 = value
			_append_ascii(output, "v4")
			return (
				_append_float64(output, vector.x)
				and _append_float64(output, vector.y)
				and _append_float64(output, vector.z)
				and _append_float64(output, vector.w)
			)
		TYPE_VECTOR4I:
			var vector: Vector4i = value
			_append_ascii(output, "w4")
			_append_ascii(output, "i%d;i%d;i%d;i%d;" % [vector.x, vector.y, vector.z, vector.w])
		TYPE_COLOR:
			var color: Color = value
			_append_ascii(output, "c")
			return (
				_append_float64(output, color.r)
				and _append_float64(output, color.g)
				and _append_float64(output, color.b)
				and _append_float64(output, color.a)
			)
		TYPE_ARRAY:
			return _encode_array(value, output, depth, layouts)
		TYPE_DICTIONARY:
			return _encode_dictionary(value, output, depth, layouts)
		TYPE_PACKED_BYTE_ARRAY:
			_append_sized_bytes(output, "pb", value)
		TYPE_PACKED_INT32_ARRAY, TYPE_PACKED_INT64_ARRAY:
			return _encode_packed_int_array(value, output)
		TYPE_PACKED_FLOAT32_ARRAY, TYPE_PACKED_FLOAT64_ARRAY:
			return _encode_packed_float_array(value, output)
		TYPE_PACKED_STRING_ARRAY:
			return _encode_packed_string_array(value, output)
		TYPE_PACKED_VECTOR2_ARRAY:
			return _encode_packed_vector2_array(value, output)
		TYPE_PACKED_VECTOR3_ARRAY:
			return _encode_packed_vector3_array(value, output)
		TYPE_PACKED_COLOR_ARRAY:
			return _encode_packed_color_array(value, output)
		_:
			push_error("SimulationDigest does not support Variant type %s" % type_string(typeof(value)))
			return false
	return true


static func _encode_array(value: Array, output: PackedByteArray, depth: int, layouts: KeyLayouts) -> bool:
	_append_ascii(output, "a%d:" % value.size())
	# Event IDs and several saved histories are typed string arrays. Their element
	# type is guaranteed by Godot, so avoid the recursive Variant dispatch for each
	# entry while keeping the same depth limit and exact bytes.
	if value.is_typed() and value.get_typed_builtin() in [TYPE_STRING, TYPE_STRING_NAME]:
		if not value.is_empty() and depth >= MAX_NESTING_DEPTH:
			push_error("SimulationDigest data exceeds the maximum nesting depth")
			return false
		var tag := "s" if value.get_typed_builtin() == TYPE_STRING else "q"
		for item in value:
			_append_sized_bytes(output, tag, String(item).to_utf8_buffer())
		return true
	for item in value:
		if not _encode_value(item, output, depth + 1, layouts):
			return false
	return true


static func _encode_dictionary(value: Dictionary, output: PackedByteArray, depth: int, layouts: KeyLayouts) -> bool:
	if not value.is_empty() and depth >= MAX_NESTING_DEPTH:
		push_error("SimulationDigest data exceeds the maximum nesting depth")
		return false
	var keys := value.keys()
	var cached_layouts := _layout_bucket(keys, layouts)
	var entries: Array = []
	if not cached_layouts.is_empty() and cached_layouts.has(keys):
		entries = cached_layouts[keys]
	else:
		for key in keys:
			var encoded_key := PackedByteArray()
			if not _encode_value(key, encoded_key, depth + 1, layouts):
				return false
			entries.append([key, encoded_key, encoded_key.hex_encode()])
		entries.sort_custom(func(left: Array, right: Array) -> bool:
			return String(left[2]) < String(right[2])
		)
		if _can_cache_keys(keys) and cached_layouts.size() < MAX_CACHED_LAYOUTS:
			# keys is a fresh private array from Dictionary.keys(). It and entries
			# are never mutated once stored. Native Dictionary lookup compares full
			# array contents after hashing, so hash collisions cannot alias layouts.
			cached_layouts[keys] = entries

	_append_ascii(output, "d%d:" % entries.size())
	for entry: Array in entries:
		output.append_array(entry[1])
		# Read each value live. A reused key layout never caches child containers
		# or their bytes, including when several dictionaries share the schema.
		if not _encode_value(value[entry[0]], output, depth + 1, layouts):
			return false
	return true


static func _layout_bucket(keys: Array, layouts: KeyLayouts) -> Dictionary:
	if _can_cache_keys(keys):
		return layouts.strings if typeof(keys[0]) == TYPE_STRING else layouts.names
	return {}


static func _can_cache_keys(keys: Array) -> bool:
	if keys.is_empty() or keys.size() > MAX_CACHED_LAYOUT_KEYS:
		return false
	var key_type := typeof(keys[0])
	if key_type != TYPE_STRING and key_type != TYPE_STRING_NAME:
		return false
	for key in keys:
		if typeof(key) != key_type or String(key).length() > MAX_CACHED_KEY_LENGTH:
			return false
	return true


static func _encode_packed_int_array(value: Variant, output: PackedByteArray) -> bool:
	var tag := "pi32" if typeof(value) == TYPE_PACKED_INT32_ARRAY else "pi64"
	_append_ascii(output, "%s%d:" % [tag, value.size()])
	for item in value:
		_append_ascii(output, "i%d;" % int(item))
	return true


static func _encode_packed_float_array(value: Variant, output: PackedByteArray) -> bool:
	var tag := "pf32" if typeof(value) == TYPE_PACKED_FLOAT32_ARRAY else "pf64"
	_append_ascii(output, "%s%d:" % [tag, value.size()])
	for item in value:
		if not _append_float64(output, float(item)):
			return false
	return true


static func _encode_packed_string_array(value: PackedStringArray, output: PackedByteArray) -> bool:
	_append_ascii(output, "ps%d:" % value.size())
	for item in value:
		_append_sized_bytes(output, "s", item.to_utf8_buffer())
	return true


static func _encode_packed_vector2_array(value: PackedVector2Array, output: PackedByteArray) -> bool:
	_append_ascii(output, "pv2%d:" % value.size())
	for item in value:
		if not _append_float64(output, item.x) or not _append_float64(output, item.y):
			return false
	return true


static func _encode_packed_vector3_array(value: PackedVector3Array, output: PackedByteArray) -> bool:
	_append_ascii(output, "pv3%d:" % value.size())
	for item in value:
		if (
			not _append_float64(output, item.x)
			or not _append_float64(output, item.y)
			or not _append_float64(output, item.z)
		):
			return false
	return true


static func _encode_packed_color_array(value: PackedColorArray, output: PackedByteArray) -> bool:
	_append_ascii(output, "pc%d:" % value.size())
	for item in value:
		if (
			not _append_float64(output, item.r)
			or not _append_float64(output, item.g)
			or not _append_float64(output, item.b)
			or not _append_float64(output, item.a)
		):
			return false
	return true


static func _append_float64(output: PackedByteArray, value: float) -> bool:
	if is_nan(value) or is_inf(value):
		push_error("SimulationDigest rejects NaN and infinite float values")
		return false
	var normalized := 0.0 if value == 0.0 else value
	var encoded := PackedByteArray()
	encoded.resize(8)
	encoded.encode_double(0, normalized)
	output.append_array(encoded)
	return true


static func _append_sized_bytes(output: PackedByteArray, tag: String, value: PackedByteArray) -> void:
	_append_ascii(output, "%s%d:" % [tag, value.size()])
	output.append_array(value)


static func _append_ascii(output: PackedByteArray, value: String) -> void:
	output.append_array(value.to_utf8_buffer())


static func _append_cached_text(output: PackedByteArray, tag: String, value: String, cache: Dictionary) -> void:
	if cache.has(value):
		output.append_array(cache[value])
		return
	var bytes := value.to_utf8_buffer()
	var encoded := ("%s%d:" % [tag, bytes.size()]).to_utf8_buffer()
	encoded.append_array(bytes)
	output.append_array(encoded)
	if value.length() <= 128 and cache.size() < 256:
		cache[value] = encoded