// Copyright Epic Games, Inc. All Rights Reserved.

"use strict";

////////////////////////////////////////////////////////////////////////////////
// constants & helpers

export function css_var(name)
{
	return getComputedStyle(document.documentElement).getPropertyValue(name).trim();
}

export const NODE_PAD = 14;
export const NODE_H = 26;
export const NODE_R = 8;
export const DOT_SPACE = 10;
export const MAX_VISIBLE_DEPS = 50;

const _measure_canvas = document.createElement("canvas");
const _measure_ctx = _measure_canvas.getContext("2d");
_measure_ctx.font = "11px consolas, monospace";

export function short_name(opkey)
{
	const parts = opkey.replace(/\/$/, "").split("/");
	return parts[parts.length - 1] || opkey;
}

export function measure_node_width(label)
{
	return _measure_ctx.measureText(label).width + NODE_PAD * 2 + DOT_SPACE;
}

export function lerp_color(a, b, t)
{
	const pa = [parseInt(a.slice(1,3),16), parseInt(a.slice(3,5),16), parseInt(a.slice(5,7),16)];
	const pb = [parseInt(b.slice(1,3),16), parseInt(b.slice(3,5),16), parseInt(b.slice(5,7),16)];
	const r = Math.round(pa[0] + (pb[0] - pa[0]) * t);
	const g = Math.round(pa[1] + (pb[1] - pa[1]) * t);
	const bl = Math.round(pa[2] + (pb[2] - pa[2]) * t);
	return "rgb(" + r + "," + g + "," + bl + ")";
}

function friendly_kib(n)
{
	if (typeof n === "bigint")
		n = Number(n);
	if (n < 1024) return n + " B";
	if (n < 1024 * 1024) return (n / 1024).toFixed(1) + " KiB";
	if (n < 1024 * 1024 * 1024) return (n / (1024 * 1024)).toFixed(1) + " MiB";
	return (n / (1024 * 1024 * 1024)).toFixed(2) + " GiB";
}

////////////////////////////////////////////////////////////////////////////////
// Barnes-Hut quadtree for O(n log n) repulsion

class QuadTree
{
	constructor(x, y, size)
	{
		this.x = x;            // center x
		this.y = y;            // center y
		this.size = size;       // half-width
		this.mass = 0;
		this.com_x = 0;        // center of mass x
		this.com_y = 0;        // center of mass y
		this.node = null;       // leaf node (if single)
		this.children = null;   // [NW, NE, SW, SE] or null
	}

	insert(node)
	{
		if (this.mass === 0)
		{
			this.node = node;
			this.mass = 1;
			this.com_x = node.x;
			this.com_y = node.y;
			return;
		}

		// update center of mass
		const new_mass = this.mass + 1;
		this.com_x = (this.com_x * this.mass + node.x) / new_mass;
		this.com_y = (this.com_y * this.mass + node.y) / new_mass;
		this.mass = new_mass;

		if (!this.children)
		{
			this.children = [null, null, null, null];
			if (this.node)
			{
				this._insert_child(this.node);
				this.node = null;
			}
		}
		this._insert_child(node);
	}

	_insert_child(node)
	{
		const hs = this.size / 2;
		const idx = (node.x >= this.x ? 1 : 0) + (node.y >= this.y ? 2 : 0);
		const cx = this.x + (idx & 1 ? hs : -hs);
		const cy = this.y + (idx & 2 ? hs : -hs);

		if (!this.children[idx])
			this.children[idx] = new QuadTree(cx, cy, hs);
		this.children[idx].insert(node);
	}

	compute_force(node, repulsion, theta)
	{
		if (this.mass === 0) return [0, 0];

		var dx = node.x - this.com_x;
		var dy = node.y - this.com_y;
		var dist_sq = dx * dx + dy * dy;
		if (dist_sq < 1) dist_sq = 1;

		// leaf with single node — direct calculation
		if (!this.children && this.node)
		{
			if (this.node === node) return [0, 0];
			const f = repulsion / dist_sq;
			const dist = Math.sqrt(dist_sq);
			return [f * dx / dist, f * dy / dist];
		}

		// Barnes-Hut approximation: if node is far enough, treat as single body
		const s = this.size * 2;
		if ((s * s) / dist_sq < theta * theta)
		{
			const f = repulsion * this.mass / dist_sq;
			const dist = Math.sqrt(dist_sq);
			return [f * dx / dist, f * dy / dist];
		}

		// recurse into children
		var fx = 0, fy = 0;
		if (this.children)
		{
			for (const child of this.children)
			{
				if (!child) continue;
				const [cfx, cfy] = child.compute_force(node, repulsion, theta);
				fx += cfx;
				fy += cfy;
			}
		}
		return [fx, fy];
	}
}

function build_quadtree(nodes)
{
	var min_x = Infinity, min_y = Infinity;
	var max_x = -Infinity, max_y = -Infinity;
	for (const n of nodes)
	{
		if (n.x < min_x) min_x = n.x;
		if (n.y < min_y) min_y = n.y;
		if (n.x > max_x) max_x = n.x;
		if (n.y > max_y) max_y = n.y;
	}
	const cx = (min_x + max_x) / 2;
	const cy = (min_y + max_y) / 2;
	const hs = Math.max(max_x - min_x, max_y - min_y) / 2 + 1;
	const tree = new QuadTree(cx, cy, hs);
	for (const n of nodes)
		tree.insert(n);
	return tree;
}

////////////////////////////////////////////////////////////////////////////////
// overlap removal

export function remove_overlaps(nodes, iterations, padding)
{
	for (var iter = 0; iter < iterations; ++iter)
	{
		for (var i = 0; i < nodes.length; ++i)
		{
			for (var j = i + 1; j < nodes.length; ++j)
			{
				const a = nodes[i];
				const b = nodes[j];
				const hw = (a.w + b.w) / 2 + padding;
				const hh = (a.h + b.h) / 2 + padding;
				const dx = b.x - a.x;
				const dy = b.y - a.y;
				const ox = hw - Math.abs(dx);
				const oy = hh - Math.abs(dy);
				if (ox <= 0 || oy <= 0) continue;

				// push apart along axis of minimum penetration
				if (ox < oy)
				{
					const sx = dx >= 0 ? 1 : -1;
					if (a.pinned && b.pinned) continue;
					if (a.pinned)
						b.x += sx * ox;
					else if (b.pinned)
						a.x -= sx * ox;
					else
					{
						const push = ox / 2;
						a.x -= sx * push;
						b.x += sx * push;
					}
				}
				else
				{
					const sy = dy >= 0 ? 1 : -1;
					if (a.pinned && b.pinned) continue;
					if (a.pinned)
						b.y += sy * oy;
					else if (b.pinned)
						a.y -= sy * oy;
					else
					{
						const push = oy / 2;
						a.y -= sy * push;
						b.y += sy * push;
					}
				}
			}
		}
	}
}

////////////////////////////////////////////////////////////////////////////////
// layout

function layout_step(nodes, edges, cx, cy)
{
	const n = nodes.length;
	const repulsion = 80000 + n * 2000;
	const spring_rest = 120 + n * 2;
	const spring_k = 0.004;
	const gravity = 0.01;
	const damping = 0.85;

	// repulsion: use Barnes-Hut when > 100 nodes, naive O(n^2) otherwise
	if (n > 100)
	{
		const qt = build_quadtree(nodes);
		for (var i = 0; i < n; ++i)
		{
			const [rfx, rfy] = qt.compute_force(nodes[i], repulsion, 0.8);
			nodes[i].fx = rfx + (cx - nodes[i].x) * gravity;
			nodes[i].fy = rfy + (cy - nodes[i].y) * gravity;
		}
	}
	else
	{
		for (var i = 0; i < n; ++i)
		{
			var fx = 0, fy = 0;
			for (var j = 0; j < n; ++j)
			{
				if (i == j) continue;
				var dx = nodes[i].x - nodes[j].x;
				var dy = nodes[i].y - nodes[j].y;
				var dist_sq = dx * dx + dy * dy;
				if (dist_sq < 1) dist_sq = 1;
				var f = repulsion / dist_sq;
				var dist = Math.sqrt(dist_sq);
				fx += f * dx / dist;
				fy += f * dy / dist;
			}
			fx += (cx - nodes[i].x) * gravity;
			fy += (cy - nodes[i].y) * gravity;
			nodes[i].fx = fx;
			nodes[i].fy = fy;
		}
	}

	for (const edge of edges)
	{
		const a = edge.source;
		const b = edge.target;
		var dx = b.x - a.x;
		var dy = b.y - a.y;
		var dist = Math.sqrt(dx * dx + dy * dy);
		if (dist < 1) dist = 1;
		var f = spring_k * (dist - spring_rest);
		var fx = f * dx / dist;
		var fy = f * dy / dist;
		a.fx += fx;
		a.fy += fy;
		b.fx -= fx;
		b.fy -= fy;
	}

	for (const node of nodes)
	{
		if (node.pinned) continue;
		node.vx = (node.vx + node.fx) * damping;
		node.vy = (node.vy + node.fy) * damping;
		node.x += node.vx;
		node.y += node.vy;
	}
}

export function layout_run(nodes, edges, cx, cy, n)
{
	for (var i = 0; i < n; ++i)
		layout_step(nodes, edges, cx, cy);
}

////////////////////////////////////////////////////////////////////////////////
// GraphEngine

export class GraphEngine
{
	constructor(options)
	{
		this._canvas = options.canvas;
		this._ctx = this._canvas.getContext("2d");
		this._size_map = options.size_map || {};
		this._on_expand = options.on_expand || null;
		this._on_navigate = options.on_navigate || null;
		this._on_hover = options.on_hover || null;
		this._empty_message = options.empty_message || "empty graph";
		this._friendly_kib = options.friendly_kib || friendly_kib;

		this._nodes = [];
		this._edges = [];
		this._node_map = {};
		this._expanded = new Set();
		this._hidden_dep_types = new Set();

		this._edge_index = new Map();
		this._ctxmenu = null;
		this._ctxmenu_node = null;
		this._visible_set = null;
		this._compression_fill = false;
		this._compression_max = 1.0;     // compression filter threshold (1.0 = show all)
		this._reachable = null;          // null = all reachable, Set = only these nodes
		this._fade_raf = null;           // requestAnimationFrame handle for fade animation

		this._quick_filters = new Set();  // active quick-filter names
		this._large_threshold = 0;       // computed 80th-percentile raw_size
		this._breadcrumb_el = null;           // breadcrumb container element
		this._breadcrumb_prefix = null;       // current path filter (null = no filter)
		this._breadcrumb_on_navigate = null;  // callback when breadcrumb segment clicked

		this._search_el = null;          // search overlay DOM
		this._search_matches = null;     // array of matching nodes
		this._search_match_set = null;   // Set for O(1) lookup during render
		this._search_index = -1;         // current focused match

		this._transform = { x: 0, y: 0, scale: 1.0 };
		this._drag = null;
		this._hover_node = null;
		this._resizing = false;

		this._init_colors();
		this._bind_events();
		if (options.splitter)
			this._bind_splitter(options.splitter);
	}

	// -- read-only properties --------------------------------------------------

	get nodes()       { return this._nodes; }
	get edges()       { return this._edges; }
	get node_map()    { return this._node_map; }
	get expanded()    { return this._expanded; }
	get edge_index()  { return this._edge_index; }
	get transform()   { return this._transform; }
	get hover_node()  { return this._hover_node; }
	get canvas()      { return this._canvas; }
	get visible_set() { return this._visible_set; }

	// -- colors ----------------------------------------------------------------

	_init_colors()
	{
		this._colors = {
			p0: css_var("--theme_p0"),
			p1: css_var("--theme_p1"),
			p2: css_var("--theme_p2"),
			p3: css_var("--theme_p3"),
			p4: css_var("--theme_p4"),
			g0: css_var("--theme_g0"),
			g1: css_var("--theme_g1"),
			g2: css_var("--theme_g2"),
			g3: css_var("--theme_g3"),
			g4: css_var("--theme_g4"),
		};
		this._dep_colors = {
			"imported":	{ color: this._colors.p0, dash: [] },
			"native":	{ color: "#496",           dash: [] },
			"soft":		{ color: "#c84",           dash: [6, 4] },
		};
		this._dep_default = { color: this._colors.g1, dash: [] };
		this._ratio_colors = ["#482878", "#2d708e", "#20a386", "#75d054", "#fde725"];
	}

	// -- graph data methods ----------------------------------------------------

	add_node(opkey, x, y, is_root, label)
	{
		if (this._node_map[opkey])
			return this._node_map[opkey];

		if (!label)
			label = short_name(opkey);
		const node = {
			opkey: opkey,
			label: label,
			w: measure_node_width(label),
			h: NODE_H,
			x: x, y: y,
			vx: 0, vy: 0,
			fx: 0, fy: 0,
			is_root: is_root || false,
			expanded: false,
			pinned: is_root || false,
			dep_count: 0,
			truncated: false,
		};
		this._nodes.push(node);
		this._node_map[opkey] = node;
		return node;
	}

	add_group_node(opkey, label, x, y, data)
	{
		if (this._node_map[opkey])
			return this._node_map[opkey];

		const w = measure_node_width(label) + 10;
		const node = {
			opkey: opkey,
			label: label,
			w: w,
			h: NODE_H + 6,
			x: x, y: y,
			vx: 0, vy: 0,
			fx: 0, fy: 0,
			is_root: false,
			is_group: true,
			expanded: false,
			pinned: false,
			dep_count: 0,
			truncated: false,
			prefix_path: opkey,
			prefix_node: data,
		};
		this._nodes.push(node);
		this._node_map[opkey] = node;
		return node;
	}

	add_edge(source, target, dep_type)
	{
		for (const e of this._edges)
			if (e.source === source && e.target === target)
				return;
		this._edges.push({ source: source, target: target, dep_type: dep_type });
	}

	reset()
	{
		this._nodes = [];
		this._edges = [];
		this._node_map = {};
		this._expanded = new Set();
		this._edge_index = new Map();
		this._visible_set = null;
		this._breadcrumb_prefix = null;
		this._render_breadcrumb();
		this._transform = { x: 0, y: 0, scale: 1.0 };
		this._hover_node = null;
		this._hide_context_menu();
		this.render();
	}

	layout(cx, cy, iterations)
	{
		layout_run(this._nodes, this._edges, cx, cy, iterations);
	}

	remove_overlaps(iterations, padding)
	{
		remove_overlaps(this._nodes, iterations, padding);
	}

	rebuild_edge_index()
	{
		this._edge_index = new Map();
		for (const node of this._nodes)
			this._edge_index.set(node, { incoming: [], outgoing: [] });
		for (const edge of this._edges)
		{
			const si = this._edge_index.get(edge.source);
			const ti = this._edge_index.get(edge.target);
			if (si) si.outgoing.push(edge);
			if (ti) ti.incoming.push(edge);
		}
	}

	// -- node operations -------------------------------------------------------

	async expand_node(node)
	{
		if (this._expanded.has(node.opkey))
			return;
		if (!this._on_expand)
			return;

		this._expanded.add(node.opkey);
		node.expanded = true;
		node.loading = true;
		this.render();

		const pulse_raf = setInterval(() => this.render(), 50);

		try
		{
			const deps = await this._on_expand(node.opkey);
			if (!deps || deps.length == 0)
				return;

			// count dep types
			const dep_types = {};
			var dep_total = 0;
			for (const dep of deps)
			{
				dep_types[dep.dep_type] = (dep_types[dep.dep_type] || 0) + 1;
				dep_total++;
			}
			node.dep_count = dep_total;
			node.dep_types = dep_types;

			// snapshot existing nodes before adding children
			const existing = new Set(this._nodes);

			// ripple placement: concentric rings around the expanded node
			const parent = this._find_parent(node);
			const outward_angle = parent
				? Math.atan2(node.y - parent.y, node.x - parent.x)
				: 0;

			// small push to clear immediate area (only on first expand)
			if (parent && !node._skip_push && !node._was_pushed)
			{
				const push_dist = 80;
				node.x += Math.cos(outward_angle) * push_dist;
				node.y += Math.sin(outward_angle) * push_dist;
				node.pinned = true;
				node._was_pushed = true;
			}

			var arc_start, arc_span;
			if (node.is_root)
			{
				arc_start = 0;
				arc_span = 2 * Math.PI;
			}
			else
			{
				arc_start = outward_angle - Math.PI / 2;
				arc_span = Math.PI;
			}

			// place children in concentric elliptical rings (ripples)
			// ellipse: wider horizontally to match rectangular node shape
			const base_radius = 50;
			const ring_gap = 32;
			const min_node_gap = 45;
			const ellipse_ratio = 2.0;  // horizontal / vertical
			var added = 0;
			var ring = 0;

			while (added < deps.length && added < MAX_VISIBLE_DEPS)
			{
				const r = base_radius + ring * ring_gap;
				const rx = r * ellipse_ratio;
				const ry = r;
				const arc_len = arc_span * rx;
				const capacity = Math.max(1, Math.floor(arc_len / min_node_gap));
				const remaining = Math.min(deps.length, MAX_VISIBLE_DEPS) - added;
				const batch = Math.min(capacity, remaining);

				for (var j = 0; j < batch; ++j)
				{
					const dep = deps[added];
					const t = batch > 1 ? j / (batch - 1) : 0.5;
					const angle = arc_start + t * arc_span;
					const jitter = (Math.random() - 0.5) * 10;
					const dep_node = this.add_node(
						dep.opkey,
						node.x + Math.cos(angle) * (rx + jitter),
						node.y + Math.sin(angle) * (ry + jitter),
						false
					);
					dep_node.unresolved = dep.unresolved || false;
					this.add_edge(node, dep_node, dep.dep_type);
					added++;
				}
				ring++;
			}
			if (added < deps.length)
				node.truncated = true;

			// pin existing nodes during layout so only new children move
			for (const n of existing)
			{
				n._was_pinned = n.pinned;
				n.pinned = true;
			}

			layout_run(this._nodes, this._edges, node.x, node.y, 80);
			remove_overlaps(this._nodes, 10, 8);

			for (const n of existing)
			{
				n.pinned = n._was_pinned;
				delete n._was_pinned;
			}
			remove_overlaps(this._nodes, 15, 20);

			this.rebuild_edge_index();
			this.fit_subtree(node);
		}
		finally
		{
			node.loading = false;
			clearInterval(pulse_raf);
			this.render();
		}
	}

	collapse_node(node)
	{
		if (!this._expanded.has(node.opkey))
			return;

		const to_remove = new Set();
		const collect = (n) => {
			const idx = this._edge_index.get(n);
			if (!idx) return;
			for (const edge of idx.outgoing)
			{
				const child = edge.target;
				if (to_remove.has(child)) continue;
				to_remove.add(child);
				if (child.expanded)
					this.collapse_node(child);
				collect(child);
			}
		};
		collect(node);

		this._nodes = this._nodes.filter(n => !to_remove.has(n));
		this._edges = this._edges.filter(e => !to_remove.has(e.source) && !to_remove.has(e.target));
		for (const n of to_remove)
			delete this._node_map[n.opkey];

		this._expanded.delete(node.opkey);
		node.expanded = false;
		node.dep_count = 0;
		node.dep_types = null;
		node.truncated = false;
	}

	async reexpand_node(node)
	{
		if (!this._expanded.has(node.opkey))
			return;

		// keep expanded children (+ their subtrees) and pinned children in place
		const keep = new Set();
		const idx = this._edge_index.get(node);
		if (idx)
		{
			const mark_keep = (n) => {
				if (keep.has(n)) return;
				keep.add(n);
				const ci = this._edge_index.get(n);
				if (!ci) return;
				for (const e of ci.outgoing)
					mark_keep(e.target);
			};
			for (const edge of idx.outgoing)
			{
				const child = edge.target;
				if (child.expanded || child.pinned)
					mark_keep(child);
			}
		}

		// collect non-kept descendants to remove
		const to_remove = new Set();
		const collect = (n) => {
			const ni = this._edge_index.get(n);
			if (!ni) return;
			for (const edge of ni.outgoing)
			{
				const child = edge.target;
				if (to_remove.has(child) || keep.has(child)) continue;
				to_remove.add(child);
				collect(child);
			}
		};
		collect(node);

		// remove only non-kept descendants
		this._nodes = this._nodes.filter(n => !to_remove.has(n));
		this._edges = this._edges.filter(e => !to_remove.has(e.source) && !to_remove.has(e.target));
		for (const n of to_remove)
			delete this._node_map[n.opkey];

		this._expanded.delete(node.opkey);
		node.expanded = false;
		node.dep_count = 0;
		node.dep_types = null;
		node.truncated = false;
		this.rebuild_edge_index();

		node._skip_push = true;
		await this.expand_node(node);
		delete node._skip_push;
	}

	_find_parent(node)
	{
		const parents = [];
		for (const e of this._edges)
			if (e.target === node)
				parents.push(e.source);

		if (parents.length === 0) return null;
		if (parents.length === 1) return parents[0];

		// multiple parents: pick shortest path to root
		const depth_of = (n) => {
			const visited = new Set();
			var cur = n;
			var d = 0;
			while (cur && !cur.is_root)
			{
				if (visited.has(cur)) return Infinity;
				visited.add(cur);
				var found = null;
				for (const e of this._edges)
				{
					if (e.target === cur) { found = e.source; break; }
				}
				cur = found;
				d++;
			}
			return cur ? d : Infinity;
		};
		var best_depth = Infinity;
		const candidates = [];
		for (const p of parents)
		{
			const d = depth_of(p);
			if (d < best_depth)
			{
				best_depth = d;
				candidates.length = 0;
				candidates.push(p);
			}
			else if (d === best_depth)
				candidates.push(p);
		}
		return candidates[Math.floor(Math.random() * candidates.length)];
	}

	mark_has_deps(opkey_set)
	{
		for (const node of this._nodes)
		{
			if (node.is_root)
				continue;
			if (opkey_set.has(node.opkey))
				node.has_deps = true;
			else if (!node.unresolved && node.has_deps === undefined)
				node.has_deps = false;
		}
		this.render();
	}

	// -- view operations -------------------------------------------------------

	fit_view()
	{
		if (this._nodes.length == 0)
			return;

		var min_x = Infinity, min_y = Infinity;
		var max_x = -Infinity, max_y = -Infinity;
		const vs = this._visible_set;
		for (const n of this._nodes)
		{
			if (vs && !vs.has(n)) continue;
			const hw = n.w / 2, hh = n.h / 2;
			if (n.x - hw < min_x) min_x = n.x - hw;
			if (n.y - hh < min_y) min_y = n.y - hh;
			if (n.x + hw > max_x) max_x = n.x + hw;
			if (n.y + hh > max_y) max_y = n.y + hh;
		}

		const pad = 40;
		const w = max_x - min_x + pad * 2;
		const h = max_y - min_y + pad * 2;
		const scale = Math.min(this._canvas.width / w, this._canvas.height / h, 4.0);
		const cx = (min_x + max_x) / 2;
		const cy = (min_y + max_y) / 2;

		this._transform.scale = Math.max(scale, 0.2);
		this._transform.x = this._canvas.width / 2 - cx * this._transform.scale;
		this._transform.y = this._canvas.height / 2 - cy * this._transform.scale;
		this.render();
	}

	fit_subtree(node)
	{
		const collected = [node];
		const visited = new Set();
		visited.add(node);
		const collect = (n) => {
			const idx = this._edge_index.get(n);
			if (!idx) return;
			for (const edge of idx.outgoing)
			{
				const child = edge.target;
				if (visited.has(child)) continue;
				visited.add(child);
				collected.push(child);
				collect(child);
			}
		};
		collect(node);

		var min_x = Infinity, min_y = Infinity;
		var max_x = -Infinity, max_y = -Infinity;
		for (const n of collected)
		{
			const hw = n.w / 2, hh = n.h / 2;
			if (n.x - hw < min_x) min_x = n.x - hw;
			if (n.y - hh < min_y) min_y = n.y - hh;
			if (n.x + hw > max_x) max_x = n.x + hw;
			if (n.y + hh > max_y) max_y = n.y + hh;
		}

		const pad = 40;
		const w = max_x - min_x + pad * 2;
		const h = max_y - min_y + pad * 2;
		const scale = Math.min(this._canvas.width / w, this._canvas.height / h, 4.0);
		const cx = (min_x + max_x) / 2;
		const cy = (min_y + max_y) / 2;

		this._transform.scale = Math.max(scale, 0.2);
		this._transform.x = this._canvas.width / 2 - cx * this._transform.scale;
		this._transform.y = this._canvas.height / 2 - cy * this._transform.scale;
		this.render();
	}

	trace_to_root(node)
	{
		const visible = new Set();
		const queue = [node];
		visible.add(node);
		while (queue.length > 0)
		{
			const n = queue.shift();
			const idx = this._edge_index.get(n);
			if (!idx) continue;
			for (const edge of idx.incoming)
			{
				if (!visible.has(edge.source))
				{
					visible.add(edge.source);
					queue.push(edge.source);
				}
			}
		}
		this._visible_set = visible;
		this.fit_view();
	}

	clear_trace()
	{
		this._visible_set = null;
		this.render();
	}

	set_compression_fill(enabled)
	{
		this._compression_fill = enabled;
		this.render();
	}

	set_canvas_size(w, h)
	{
		this._canvas.width = w;
		this._canvas.height = h;
		this.render();
	}

	// -- rendering -------------------------------------------------------------

	_node_color(node)
	{
		const sizes = this._size_map[node.opkey];
		if (!sizes || sizes.raw_size == 0n)
			return this._colors.g1;
		const ratio = 1.0 - Number(sizes.size) / Number(sizes.raw_size);
		const stops = this._ratio_colors;
		const t = Math.max(0, Math.min(1, 1.0 - ratio)) * (stops.length - 1);
		const i = Math.min(Math.floor(t), stops.length - 2);
		return lerp_color(stops[i], stops[i + 1], t - i);
	}

	_is_edge_hidden(edge)
	{
		const dep_type = edge.dep_type;
		if (this._dep_colors[dep_type])
			return this._hidden_dep_types.has(dep_type);
		return this._hidden_dep_types.has("$other");
	}

	render()
	{
		const ctx = this._ctx;
		if (!ctx) return;

		// recompute reachable set: nodes reachable from roots via non-hidden edges
		if (this._hidden_dep_types.size > 0)
		{
			const reachable = new Set();
			const queue = [];
			for (const n of this._nodes)
				if (n.is_root) { reachable.add(n); queue.push(n); }
			while (queue.length > 0)
			{
				const n = queue.shift();
				const idx = this._edge_index.get(n);
				if (idx)
				{
					for (const edge of idx.outgoing)
					{
						if (this._is_edge_hidden(edge)) continue;
						if (reachable.has(edge.target)) continue;
						reachable.add(edge.target);
						queue.push(edge.target);
					}
				}
				else
				{
					for (const edge of this._edges)
					{
						if (edge.source !== n) continue;
						if (this._is_edge_hidden(edge)) continue;
						if (reachable.has(edge.target)) continue;
						reachable.add(edge.target);
						queue.push(edge.target);
					}
				}
			}
			this._reachable = reachable;
		}
		else
			this._reachable = null;

		// animate reachable alpha: fade nodes in/out when edge types toggle
		const fade_step = 0.08;
		var needs_fade_frame = false;
		for (const n of this._nodes)
		{
			const target = (!this._reachable || this._reachable.has(n)) ? 1.0 : 0.0;
			if (n._reachable_alpha === undefined) n._reachable_alpha = target;
			if (n._reachable_alpha !== target)
			{
				if (Math.abs(n._reachable_alpha - target) < fade_step * 1.5)
					n._reachable_alpha = target;
				else
				{
					n._reachable_alpha += target > n._reachable_alpha ? fade_step : -fade_step;
					needs_fade_frame = true;
				}
			}
		}
		if (needs_fade_frame && !this._fade_raf)
		{
			this._fade_raf = requestAnimationFrame(() => {
				this._fade_raf = null;
				this.render();
			});
		}

		const c = this._colors;
		const canvas = this._canvas;
		const scale = this._transform.scale;
		ctx.clearRect(0, 0, canvas.width, canvas.height);

		// viewport culling: compute visible world-space rect
		const vp_pad = 100 / scale;
		const vp_x0 = -this._transform.x / scale - vp_pad;
		const vp_y0 = -this._transform.y / scale - vp_pad;
		const vp_x1 = (canvas.width - this._transform.x) / scale + vp_pad;
		const vp_y1 = (canvas.height - this._transform.y) / scale + vp_pad;

		// drawable = includes fading-out nodes (for smooth transitions)
		const is_node_drawable = (n) => {
			if (this._visible_set && !this._visible_set.has(n)) return false;
			if (this._node_compression_alpha(n) <= 0) return false;
			if (n._reachable_alpha !== undefined && n._reachable_alpha <= 0) return false;
			return true;
		};

		// viewport culling on top of drawable check
		const is_node_visible = (n) => {
			if (!is_node_drawable(n)) return false;
			const hw = n.w / 2, hh = n.h / 2;
			return n.x + hw >= vp_x0 && n.x - hw <= vp_x1 &&
			       n.y + hh >= vp_y0 && n.y - hh <= vp_y1;
		};

		const is_edge_visible = (e) => {
			if (!is_node_drawable(e.source) || !is_node_drawable(e.target)) return false;
			return is_node_visible(e.source) || is_node_visible(e.target);
		};

		// text LOD thresholds
		const node_screen_h = NODE_H * scale;
		const show_labels = node_screen_h >= 8;
		const show_dots = node_screen_h >= 14;

		ctx.save();
		ctx.translate(this._transform.x, this._transform.y);
		ctx.scale(scale, scale);

		const rect_edge = (cx, cy, hw, hh, sx, sy) => {
			var dx = sx - cx;
			var dy = sy - cy;
			if (dx == 0 && dy == 0) dx = 1;
			const sx_t = hw / (Math.abs(dx) || 1);
			const sy_t = hh / (Math.abs(dy) || 1);
			const t = Math.min(sx_t, sy_t);
			return [cx + dx * t, cy + dy * t];
		};

		const draw_edge = (edge, color, width) => {
			const dep = this._dep_colors[edge.dep_type] || this._dep_default;
			const ec = color || dep.color;
			const lw = width || 1.5;
			ctx.strokeStyle = ec;
			ctx.lineWidth = lw / scale;
			ctx.setLineDash(dep.dash.map(v => v / scale));

			const s = edge.source;
			const t = edge.target;
			const [sx, sy] = rect_edge(s.x, s.y, s.w / 2, s.h / 2, t.x, t.y);
			const [tx, ty] = rect_edge(t.x, t.y, t.w / 2, t.h / 2, s.x, s.y);

			ctx.beginPath();
			ctx.moveTo(sx, sy);
			ctx.lineTo(tx, ty);
			ctx.stroke();

			const dx = tx - sx;
			const dy = ty - sy;
			const dist = Math.sqrt(dx * dx + dy * dy);
			if (dist > 0)
			{
				const ux = dx / dist;
				const uy = dy / dist;
				const arrow_size = 8 / scale;
				ctx.setLineDash([]);
				ctx.beginPath();
				ctx.moveTo(tx, ty);
				ctx.lineTo(tx - ux * arrow_size - uy * arrow_size * 0.5,
				           ty - uy * arrow_size + ux * arrow_size * 0.5);
				ctx.lineTo(tx - ux * arrow_size + uy * arrow_size * 0.5,
				           ty - uy * arrow_size - ux * arrow_size * 0.5);
				ctx.closePath();
				ctx.fillStyle = ec;
				ctx.fill();
			}
		};

		// search and filter state (used by both edge and node drawing)
		const search_active = this._search_match_set && this._search_match_set.size >= 0
			&& this._search_matches !== null;

		// draw edges
		const hover = this._hover_node;
		const do_highlight = hover && !hover.is_root;

		const filter_dim = 0.15;
		const has_quick_filter = this._quick_filters.size > 0;

		const edge_alpha = (e) => {
			var a = Math.min(
				this._node_compression_alpha(e.source),
				this._node_compression_alpha(e.target));
			const ra = e.source._reachable_alpha;
			const rb = e.target._reachable_alpha;
			if (ra !== undefined) a *= ra;
			if (rb !== undefined) a *= rb;
			if (search_active)
			{
				const sm = this._search_match_set;
				if (!sm.has(e.source) && !sm.has(e.target)) a *= filter_dim;
			}
			if (has_quick_filter)
			{
				if (!this._quick_filter_match(e.source) && !this._quick_filter_match(e.target))
					a *= filter_dim;
			}
			return a;
		};

		for (const edge of this._edges)
		{
			if (this._is_edge_hidden(edge))
				continue;
			if (!is_edge_visible(edge))
				continue;
			if (do_highlight && (edge.source === hover || edge.target === hover))
				continue;
			const ea = edge_alpha(edge);
			if (ea <= 0) continue;
			if (do_highlight)
			{
				ctx.globalAlpha = 0.2 * ea;
				draw_edge(edge);
				ctx.globalAlpha = 1.0;
			}
			else
			{
				if (ea < 1.0) ctx.globalAlpha = ea;
				draw_edge(edge);
				if (ea < 1.0) ctx.globalAlpha = 1.0;
			}
		}

		if (do_highlight)
		{
			const path_edges = new Set();
			const visited = new Set();
			const trace = (node) => {
				if (visited.has(node)) return;
				visited.add(node);
				const idx = this._edge_index.get(node);
				if (idx)
				{
					for (const edge of idx.incoming)
					{
						if (this._is_edge_hidden(edge)) continue;
						path_edges.add(edge);
						trace(edge.source);
					}
				}
				else
				{
					for (const edge of this._edges)
					{
						if (this._is_edge_hidden(edge)) continue;
						if (edge.target === node)
						{
							path_edges.add(edge);
							trace(edge.source);
						}
					}
				}
			};
			trace(hover);
			const hover_idx = this._edge_index.get(hover);
			if (hover_idx)
			{
				for (const edge of hover_idx.outgoing)
					if (!this._is_edge_hidden(edge))
						path_edges.add(edge);
			}
			else
			{
				for (const edge of this._edges)
					if (edge.source === hover && !this._is_edge_hidden(edge))
						path_edges.add(edge);
			}
			for (const edge of path_edges)
			{
				const ea = edge_alpha(edge);
				if (ea <= 0) continue;
				if (ea < 1.0) ctx.globalAlpha = ea;
				draw_edge(edge, c.p0, 3);
				if (ea < 1.0) ctx.globalAlpha = 1.0;
			}
		}
		ctx.setLineDash([]);

		// draw nodes
		const font_size = 11;
		ctx.font = font_size + "px consolas, monospace";
		ctx.textBaseline = "middle";
		ctx.textAlign = "center";

		const draw_node = (node) => {
			const nw = node.w;
			const nh = node.h;
			const x = node.x - nw / 2;
			const y = node.y - nh / 2;
			const lw = 1 / scale;

			ctx.beginPath();
			ctx.roundRect(x, y, nw, nh, NODE_R);

			// group nodes: distinct fill + dashed border
			if (node.is_group)
			{
				ctx.fillStyle = node === this._hover_node ? c.p2 : c.p3;
				ctx.fill();
				ctx.setLineDash([4 / scale, 3 / scale]);
				ctx.strokeStyle = c.p1;
				ctx.lineWidth = 1.5 * lw;
				ctx.stroke();
				ctx.setLineDash([]);
			}
			else
			{
				// fill
				if (node === this._hover_node)
					ctx.fillStyle = c.p2;
				else if (this._compression_fill)
					ctx.fillStyle = this._node_color(node);
				else
					ctx.fillStyle = c.g3;
				ctx.fill();

				// border
				if (node === this._hover_node)
				{
					ctx.strokeStyle = c.p0;
					ctx.lineWidth = 1.5 * lw;
				}
				else if (node.is_root)
				{
					ctx.strokeStyle = c.p0;
					ctx.lineWidth = 2 * lw;
				}
				else if (node.has_deps)
				{
					ctx.strokeStyle = c.p1;
					ctx.lineWidth = 1.5 * lw;
				}
				else
				{
					ctx.strokeStyle = c.g2;
					ctx.lineWidth = lw;
				}
				ctx.stroke();
			}

			// loading state: pulsing border
			if (node.loading)
			{
				const pulse = 0.4 + 0.6 * Math.abs(Math.sin(Date.now() / 300));
				ctx.strokeStyle = c.p0;
				ctx.lineWidth = 2.5 * lw;
				ctx.globalAlpha = pulse;
				ctx.beginPath();
				ctx.roundRect(x, y, nw, nh, NODE_R);
				ctx.stroke();
				ctx.globalAlpha = 1.0;
			}

			// text LOD: skip labels when zoomed out far
			if (!show_labels)
				return;

			const node_sizes = this._size_map[node.opkey];
			const has_size = !node.is_group && node_sizes && node_sizes.raw_size > 0n;
			const text_x = has_size ? node.x + DOT_SPACE / 2 : node.x;
			const has_dot = show_dots && has_size && !this._compression_fill;

			if (node.unresolved && !this._compression_fill)
				ctx.fillStyle = c.g1;
			else if (this._compression_fill)
				ctx.fillStyle = c.g4;
			else
				ctx.fillStyle = c.g0;
			ctx.fillText(node.label, text_x, node.y);

			// compression ratio dot
			if (has_dot)
			{
				const dot_r = 3;
				const label_w = _measure_ctx.measureText(node.label).width;
				const dot_x = text_x - label_w / 2 - dot_r - 4;
				ctx.beginPath();
				ctx.arc(dot_x, node.y, dot_r, 0, Math.PI * 2);
				ctx.fillStyle = this._node_color(node);
				ctx.fill();
			}

			if (node.truncated)
			{
				const extra = node.dep_count - MAX_VISIBLE_DEPS;
				ctx.fillStyle = c.g1;
				ctx.font = (font_size * 0.8) + "px consolas, monospace";
				ctx.fillText("+" + extra + " more", node.x, node.y + node.h / 2 + font_size * 0.7);
				ctx.font = font_size + "px consolas, monospace";
			}
		};

		const draw_node_with_alpha = (node) => {
			var a = this._node_compression_alpha(node);
			if (node._reachable_alpha !== undefined) a *= node._reachable_alpha;
			if (search_active && !this._search_match_set.has(node)) a *= filter_dim;
			if (has_quick_filter && !this._quick_filter_match(node)) a *= filter_dim;
			if (a <= 0) return;
			if (a < 1.0) ctx.globalAlpha = a;
			draw_node(node);
			if (a < 1.0) ctx.globalAlpha = 1.0;
		};

		// pass 1: leaf nodes
		for (const node of this._nodes)
			if (!node.expanded && node !== this._hover_node && is_node_visible(node))
				draw_node_with_alpha(node);
		// pass 2: expanded nodes
		for (const node of this._nodes)
			if (node.expanded && node !== this._hover_node && is_node_visible(node))
				draw_node_with_alpha(node);
		// pass 3: hovered node
		if (this._hover_node && scale >= 0.6 && this._is_node_filtered(this._hover_node))
			draw_node_with_alpha(this._hover_node);

		// pass 4: search match highlight rings
		if (search_active && this._search_matches.length > 0)
		{
			for (var si = 0; si < this._search_matches.length; ++si)
			{
				const node = this._search_matches[si];
				if (!is_node_visible(node)) continue;
				const is_current = si === this._search_index;
				const ring_pad = 4 / scale;
				ctx.beginPath();
				ctx.roundRect(
					node.x - node.w / 2 - ring_pad,
					node.y - node.h / 2 - ring_pad,
					node.w + ring_pad * 2,
					node.h + ring_pad * 2,
					NODE_R + ring_pad);
				ctx.strokeStyle = is_current ? c.p0 : c.p1;
				ctx.lineWidth = (is_current ? 3 : 2) / scale;
				ctx.stroke();
			}
		}

		ctx.restore();

		// zoomed-out hover: draw in screen space at readable size
		if (this._hover_node && scale < 0.6 && this._is_node_filtered(this._hover_node))
		{
			const node = this._hover_node;
			const sx = node.x * scale + this._transform.x;
			const sy = node.y * scale + this._transform.y;
			ctx.font = "11px consolas, monospace";
			ctx.textBaseline = "middle";
			ctx.textAlign = "center";

			const node_sizes = this._size_map[node.opkey];
			const has_size = !node.is_group && node_sizes && node_sizes.raw_size > 0n;
			const tw = ctx.measureText(node.label).width + NODE_PAD * 2 + (has_size ? DOT_SPACE : 0);
			const text_x = has_size ? sx + DOT_SPACE / 2 : sx;
			const has_dot = has_size && !this._compression_fill;
			const th = NODE_H;
			ctx.beginPath();
			ctx.roundRect(sx - tw / 2, sy - th / 2, tw, th, NODE_R);
			ctx.fillStyle = c.p2;
			ctx.fill();
			ctx.fillStyle = c.g4;
			ctx.fillText(node.label, text_x, sy);

			if (has_dot)
			{
				const dot_r = 4;
				const label_w = ctx.measureText(node.label).width;
				const dot_x = text_x - label_w / 2 - dot_r - 4;
				ctx.beginPath();
				ctx.arc(dot_x, sy, dot_r, 0, Math.PI * 2);
				ctx.fillStyle = this._node_color(node);
				ctx.fill();
				ctx.strokeStyle = c.g0;
				ctx.lineWidth = 1;
				ctx.stroke();
			}
		}

		// tooltip
		if (this._hover_node)
		{
			const node = this._hover_node;
			ctx.font = "11px consolas, monospace";
			ctx.textAlign = "left";
			ctx.textBaseline = "top";

			const lines = [node.opkey];
			if (node.is_group && node.prefix_node)
			{
				lines.push("entries: " + node.prefix_node.count.toLocaleString());
			}
			else
			{
				const sizes = this._size_map[node.opkey];
				if (sizes)
				{
					var size_line = "size: " + this._friendly_kib(sizes.size) +
						"  raw: " + this._friendly_kib(sizes.raw_size);
					if (sizes.raw_size > 0n)
					{
						const pct = (100 * (1.0 - Number(sizes.size) / Number(sizes.raw_size))).toFixed(0);
						size_line += "  (" + pct + "% compressed)";
					}
					lines.push(size_line);
				}
			}
			if (node.dep_count > 0)
			{
				var dep_str = "deps: " + node.dep_count;
				if (node.dep_types)
				{
					const parts = [];
					for (const t in node.dep_types)
						parts.push(t + ": " + node.dep_types[t]);
					dep_str += " (" + parts.join(", ") + ")";
				}
				lines.push(dep_str);
			}
			else if (node.expanded)
				lines.push("deps: none");

			const tags = [];
			if (node.is_root) tags.push("root");
			if (node.is_group) tags.push("group");
			if (node.expanded) tags.push("expanded");
			if (node.truncated) tags.push("truncated");
			if (node.has_deps === true) tags.push("has deps");
			else if (node.has_deps === false) tags.push("leaf");
			if (tags.length > 0)
				lines.push("[" + tags.join(", ") + "]");

			const line_h = 15;
			const pad = 6;
			var tw = 0;
			for (const line of lines)
			{
				const w = ctx.measureText(line).width;
				if (w > tw) tw = w;
			}
			tw += pad * 2;
			const th = lines.length * line_h + pad * 2;

			const node_sx = node.x * scale + this._transform.x;
			const node_sy = node.y * scale + this._transform.y;
			const node_sh = node.h * scale;
			var tx = node_sx - tw / 2;
			var ty = node_sy + node_sh / 2 + 16;

			if (tx < 4) tx = 4;
			if (tx + tw > canvas.width - 4) tx = canvas.width - tw - 4;
			if (ty + th > canvas.height - 4) ty = node_sy - node_sh / 2 - th - 16;

			ctx.shadowColor = "rgba(0,0,0,0.3)";
			ctx.shadowBlur = 8;
			ctx.shadowOffsetX = 2;
			ctx.shadowOffsetY = 2;
			ctx.fillStyle = c.g3;
			ctx.fillRect(tx, ty, tw, th);
			ctx.shadowColor = "transparent";
			ctx.shadowBlur = 0;
			ctx.shadowOffsetX = 0;
			ctx.shadowOffsetY = 0;
			ctx.strokeStyle = c.g2;
			ctx.lineWidth = 1;
			ctx.strokeRect(tx, ty, tw, th);

			ctx.fillStyle = c.g0;
			for (var i = 0; i < lines.length; ++i)
				ctx.fillText(lines[i], tx + pad, ty + pad + i * line_h);
		}

		// empty state
		if (this._nodes.length == 0)
		{
			ctx.fillStyle = c.g1;
			ctx.font = "14px consolas, monospace";
			ctx.textAlign = "center";
			ctx.textBaseline = "middle";
			ctx.fillText(this._empty_message, canvas.width / 2, canvas.height / 2);
		}
	}

	// -- hit testing -----------------------------------------------------------

	_node_compression_alpha(n)
	{
		if (this._compression_max >= 1.0) return 1.0;
		const sizes = this._size_map[n.opkey];
		if (!sizes || !(sizes.raw_size > 0n)) return 1.0;
		const ratio = 1.0 - Number(sizes.size) / Number(sizes.raw_size);
		const fade = 0.1;
		return Math.max(0, Math.min(1, (this._compression_max - ratio) / fade));
	}

	_is_node_filtered(n)
	{
		if (this._visible_set && !this._visible_set.has(n)) return false;
		if (this._reachable && !this._reachable.has(n)) return false;
		return this._node_compression_alpha(n) > 0;
	}

	_quick_filter_match(n)
	{
		if (this._quick_filters.size === 0) return true;
		if (this._quick_filters.has("leaves") && !n.expanded && !n.is_group) return true;
		if (this._quick_filters.has("unresolved") && n.unresolved) return true;
		if (this._quick_filters.has("large"))
		{
			const sizes = this._size_map[n.opkey];
			if (sizes && Number(sizes.raw_size) >= this._large_threshold) return true;
		}
		return false;
	}

	_compute_large_threshold()
	{
		const values = [];
		for (const node of this._nodes)
		{
			const s = this._size_map[node.opkey];
			if (s && s.raw_size > 0n)
				values.push(Number(s.raw_size));
		}
		values.sort((a, b) => a - b);
		this._large_threshold = values.length > 0 ? values[Math.floor(values.length * 0.8)] : 0;
	}

	_hit_test(mx, my)
	{
		const gx = (mx - this._transform.x) / this._transform.scale;
		const gy = (my - this._transform.y) / this._transform.scale;

		// expand hit area when zoomed out so nodes are easier to click
		const pad = Math.max(0, 8 / this._transform.scale - 8);

		for (var i = this._nodes.length - 1; i >= 0; --i)
		{
			const n = this._nodes[i];
			if (!this._is_node_filtered(n)) continue;
			const hw = n.w / 2 + pad, hh = n.h / 2 + pad;
			if (gx >= n.x - hw && gx <= n.x + hw &&
				gy >= n.y - hh && gy <= n.y + hh)
				return n;
		}
		return null;
	}

	// -- property panel --------------------------------------------------------

	// -- context menu ----------------------------------------------------------

	_show_context_menu(mx, my, node)
	{
		this._hide_context_menu();

		const menu = document.createElement("div");
		menu.className = "graph_ctxmenu";
		this._ctxmenu = menu;
		this._ctxmenu_node = node;

		const add_item = (label, action) => {
			const item = document.createElement("div");
			item.className = "graph_ctxmenu_item";
			item.textContent = label;
			item.addEventListener("click", (e) => {
				e.stopPropagation();
				action();
				this._hide_context_menu();
			});
			menu.appendChild(item);
		};

		if (node)
		{
			if (!node.expanded && !node.unresolved && node.has_deps !== false)
				add_item("Expand", () => this.expand_node(node));

			if (node.expanded && !node.is_root)
			{
				add_item("Collapse", () => {
					this.collapse_node(node);
					this.rebuild_edge_index();
					this.render();
				});
				add_item("Re-expand", () => this.reexpand_node(node));
			}

			if (node.expanded)
				add_item("Fit subtree", () => this.fit_subtree(node));
			if (!node.is_root)
				add_item("Trace to root", () => this.trace_to_root(node));
		}
		if (this._visible_set)
			add_item("Show all", () => this.clear_trace());
		if (node)
		{
			add_item(node.pinned ? "Unpin" : "Pin", () => {
				node.pinned = !node.pinned;
				this.render();
			});
		}

		// position: append first to measure, then clamp
		this._canvas.parentElement.appendChild(menu);
		const canvas_rect = this._canvas.getBoundingClientRect();
		var left = mx - canvas_rect.left;
		var top = my - canvas_rect.top;
		if (left + menu.offsetWidth > canvas_rect.width)
			left = canvas_rect.width - menu.offsetWidth;
		if (top + menu.offsetHeight > canvas_rect.height)
			top = canvas_rect.height - menu.offsetHeight;
		if (left < 0) left = 0;
		if (top < 0) top = 0;
		menu.style.left = left + "px";
		menu.style.top = top + "px";
		menu.addEventListener("mouseleave", () => this._hide_context_menu());
	}

	_hide_context_menu()
	{
		if (this._ctxmenu)
		{
			this._ctxmenu.remove();
			this._ctxmenu = null;
			this._ctxmenu_node = null;
		}
	}

	// -- search overlay --------------------------------------------------------

	show_search()
	{
		if (this._search_el) return;

		const overlay = document.createElement("div");
		overlay.className = "graph_search_overlay";

		const input = document.createElement("input");
		input.type = "text";
		input.placeholder = "search nodes...";

		const count = document.createElement("span");
		count.className = "graph_search_count";

		const prev_btn = document.createElement("button");
		prev_btn.textContent = "\u25B2";
		prev_btn.title = "previous match (Shift+Enter)";

		const next_btn = document.createElement("button");
		next_btn.textContent = "\u25BC";
		next_btn.title = "next match (Enter)";

		const close_btn = document.createElement("button");
		close_btn.textContent = "\u2715";
		close_btn.title = "close (Escape)";

		overlay.appendChild(input);
		overlay.appendChild(count);
		overlay.appendChild(prev_btn);
		overlay.appendChild(next_btn);
		overlay.appendChild(close_btn);

		// position overlay centered over the canvas (80% of canvas width)
		const cw = this._canvas.clientWidth;
		const cl = this._canvas.offsetLeft;
		overlay.style.left = (cl + cw * 0.1) + "px";
		overlay.style.width = (cw * 0.8) + "px";

		this._canvas.parentElement.appendChild(overlay);
		this._search_el = overlay;
		this._search_count_el = count;

		input.addEventListener("input", () => this._update_search(input.value));
		input.addEventListener("keydown", (e) => {
			if (e.key === "Escape")
			{
				this.hide_search();
				e.preventDefault();
			}
			else if (e.key === "Enter" && e.shiftKey)
			{
				this._navigate_search(-1);
				e.preventDefault();
			}
			else if (e.key === "Enter")
			{
				this._navigate_search(1);
				e.preventDefault();
			}
		});
		prev_btn.addEventListener("click", () => this._navigate_search(-1));
		next_btn.addEventListener("click", () => this._navigate_search(1));
		close_btn.addEventListener("click", () => this.hide_search());

		input.focus();
	}

	hide_search()
	{
		const was_active = this._search_matches !== null;
		if (this._search_el)
		{
			this._search_el.remove();
			this._search_el = null;
			this._search_count_el = null;
		}
		this._search_matches = null;
		this._search_match_set = null;
		this._search_index = -1;
		if (was_active)
			this.render();
	}

	_update_search(query)
	{
		const q = query.trim().toLowerCase();
		if (q.length === 0)
		{
			this._search_matches = null;
			this._search_match_set = null;
			this._search_index = -1;
			if (this._search_count_el)
				this._search_count_el.textContent = "";
			this.render();
			return;
		}

		const matches = [];
		for (const node of this._nodes)
		{
			if (!this._is_node_filtered(node)) continue;
			if (node.opkey.toLowerCase().indexOf(q) >= 0 ||
				node.label.toLowerCase().indexOf(q) >= 0)
				matches.push(node);
		}

		this._search_matches = matches;
		this._search_match_set = new Set(matches);
		this._search_index = matches.length > 0 ? 0 : -1;

		if (this._search_count_el)
		{
			if (matches.length > 0)
				this._search_count_el.textContent = "1/" + matches.length;
			else
				this._search_count_el.textContent = "0 matches";
		}

		if (matches.length > 0)
			this._focus_search_match();
		else
			this.render();
	}

	_navigate_search(delta)
	{
		if (!this._search_matches || this._search_matches.length === 0)
			return;

		this._search_index += delta;
		const len = this._search_matches.length;
		if (this._search_index < 0) this._search_index = len - 1;
		if (this._search_index >= len) this._search_index = 0;

		if (this._search_count_el)
			this._search_count_el.textContent = (this._search_index + 1) + "/" + len;

		this._focus_search_match();
	}

	_focus_search_match()
	{
		const node = this._search_matches[this._search_index];
		if (!node) return;

		// center view on the match with some padding
		const pad = 200;
		const w = node.w + pad * 2;
		const h = node.h + pad * 2;
		const scale = Math.min(this._canvas.width / w, this._canvas.height / h, 2.0);
		this._transform.scale = Math.max(scale, 0.5);
		this._transform.x = this._canvas.width / 2 - node.x * this._transform.scale;
		this._transform.y = this._canvas.height / 2 - node.y * this._transform.scale;
		this.render();
	}

	// -- legend ----------------------------------------------------------------

	build_legend(container_el)
	{
		if (!container_el) return;

		const make = (tag) => document.createElement(tag || "div");
		const swatch = (bg, w) => {
			const s = make("span");
			s.className = "legend_swatch";
			if (w) s.style.width = w;
			s.style.backgroundImage = bg;
			return s;
		};

		const toggle_dep = (name, item) => {
			if (this._hidden_dep_types.has(name))
			{
				this._hidden_dep_types.delete(name);
				item.classList.remove("legend_disabled");
			}
			else
			{
				this._hidden_dep_types.add(name);
				item.classList.add("legend_disabled");
			}
			this.render();
		};

		// edge type swatches (clickable toggles)
		for (const name in this._dep_colors)
		{
			const dep = this._dep_colors[name];
			const item = make();
			item.className = "legend_toggle";
			if (dep.dash.length)
				item.appendChild(swatch("repeating-linear-gradient(90deg, " + dep.color + " 0 6px, transparent 6px 10px)"));
			else
			{
				const s = swatch("none");
				s.style.backgroundColor = dep.color;
				item.appendChild(s);
			}
			const label = make("span");
			label.textContent = name;
			item.appendChild(label);
			item.addEventListener("click", () => toggle_dep(name, item));
			container_el.appendChild(item);
		}

		// "other" edge type
		{
			const item = make();
			item.className = "legend_toggle";
			const s = swatch("none");
			s.style.backgroundColor = this._colors.g1;
			item.appendChild(s);
			const label = make("span");
			label.textContent = "other";
			item.appendChild(label);
			item.addEventListener("click", () => toggle_dep("$other", item));
			container_el.appendChild(item);
		}

		// separator
		{
			const sep = make("span");
			sep.className = "zen_toolbar_sep";
			sep.textContent = "|";
			container_el.appendChild(sep);
		}

		// compression ratio gradient + fill pill (in one item div)
		{
			const item = make();
			const label = make("span");
			label.textContent = "compression";
			item.appendChild(label);
			const scale_wrap = make();
			scale_wrap.className = "legend_scale_wrap";
			const scale = make("span");
			scale.className = "legend_scale";
			const stops = [...this._ratio_colors].reverse();
			scale.style.backgroundImage =
				"linear-gradient(90deg, " + stops.join(", ") + ")";
			const lo = make("span");
			lo.className = "legend_scale_lo";
			lo.textContent = "low";
			scale.appendChild(lo);
			const hi = make("span");
			hi.className = "legend_scale_hi";
			hi.textContent = "high";
			scale.appendChild(hi);
			scale_wrap.appendChild(scale);
			const slider = make("input");
			slider.type = "range";
			slider.min = "0";
			slider.max = "100";
			slider.value = "100";
			slider.className = "legend_compression_slider";
			slider.title = "filter by compression ratio";
			slider.addEventListener("input", () => {
				this._compression_max = parseInt(slider.value) / 100;
				scale.style.setProperty("--filter-pos", slider.value + "%");
				this.render();
			});
			scale_wrap.appendChild(slider);
			item.appendChild(scale_wrap);
			const pill = make("span");
			pill.className = "legend_pill";
			pill.textContent = "fill";
			pill.addEventListener("click", () => {
				this._compression_fill = !this._compression_fill;
				pill.classList.toggle("active", this._compression_fill);
				this.render();
			});
			item.appendChild(pill);
			container_el.appendChild(item);
		}

		// separator
		{
			const sep = make("span");
			sep.className = "zen_toolbar_sep";
			sep.textContent = "|";
			container_el.appendChild(sep);
		}

		// quick-filter pills
		{
			const add_pill = (name, label) => {
				const pill = make("span");
				pill.className = "legend_pill";
				pill.textContent = label;
				pill.addEventListener("click", () => {
					if (this._quick_filters.has(name))
					{
						this._quick_filters.delete(name);
						pill.classList.remove("active");
					}
					else
					{
						this._quick_filters.add(name);
						pill.classList.add("active");
						if (name === "large")
							this._compute_large_threshold();
					}
					this.render();
				});
				container_el.appendChild(pill);
			};
			add_pill("leaves", "leaves");
			add_pill("unresolved", "unresolved");
			add_pill("large", "large");
		}
	}

	// -- breadcrumb path filter ------------------------------------------------

	build_breadcrumb(container_el)
	{
		if (!container_el) return;
		this._breadcrumb_el = container_el;
		this._render_breadcrumb();
	}

	set_breadcrumb_prefix(prefix, on_navigate)
	{
		this._breadcrumb_prefix = prefix;
		this._breadcrumb_on_navigate = on_navigate || this._breadcrumb_on_navigate;
		this._render_breadcrumb();
		this.render();
	}

	_render_breadcrumb()
	{
		const el = this._breadcrumb_el;
		if (!el) return;

		el.innerHTML = "";
		if (!this._breadcrumb_prefix) return;

		const parts = this._breadcrumb_prefix.split("/").filter(p => p.length > 0);
		if (parts.length === 0) return;

		const make_seg = (text, onclick, is_active) => {
			const span = document.createElement("span");
			span.className = "graph_breadcrumb_seg" + (is_active ? " active" : "");
			span.textContent = text;
			if (onclick) span.addEventListener("click", onclick);
			return span;
		};

		const make_sep = () => {
			const span = document.createElement("span");
			span.className = "graph_breadcrumb_sep";
			span.textContent = "\u203A";
			return span;
		};

		// root "/"
		el.appendChild(make_seg("/", () => this._breadcrumb_navigate(null), false));
		el.appendChild(make_sep());

		// path segments
		for (var i = 0; i < parts.length; ++i)
		{
			const prefix = "/" + parts.slice(0, i + 1).join("/");
			const is_last = i === parts.length - 1;
			el.appendChild(make_seg(parts[i], () => {
				this._breadcrumb_navigate(is_last ? null : prefix);
			}, is_last));
			if (!is_last)
				el.appendChild(make_sep());
		}
	}

	_breadcrumb_navigate(prefix)
	{
		this._breadcrumb_prefix = prefix;
		this._render_breadcrumb();
		this.render();
		if (this._breadcrumb_on_navigate)
			this._breadcrumb_on_navigate(prefix);
	}

	// -- splitter --------------------------------------------------------------

	_bind_splitter(splitter_el)
	{
		if (!splitter_el) return;
		this._splitter = splitter_el;
		// the panel to resize is the element right after the splitter in the flex layout
		const resize_target = splitter_el.nextElementSibling;

		const on_mousemove = (e) => {
			const dx = e.clientX - this._resize_start_x;
			var new_w = this._resize_start_w - dx;
			const container_w = this._canvas.parentElement.clientWidth;
			new_w = Math.max(80, Math.min(new_w, container_w - 200));
			resize_target.style.width = new_w + "px";
			this._canvas.width = this._canvas.clientWidth;
			this._canvas.height = this._canvas.clientHeight;
			this.render();
		};

		const on_mouseup = () => {
			this._resizing = false;
			this._splitter.classList.remove("active");
			document.removeEventListener("mousemove", on_mousemove);
			document.removeEventListener("mouseup", on_mouseup);
		};

		this._splitter_mousedown_fn = (e) => {
			e.preventDefault();
			this._resizing = true;
			this._resize_start_x = e.clientX;
			this._resize_start_w = resize_target.offsetWidth;
			this._splitter.classList.add("active");
			document.addEventListener("mousemove", on_mousemove);
			document.addEventListener("mouseup", on_mouseup);
		};

		splitter_el.addEventListener("mousedown", this._splitter_mousedown_fn);
	}

	// -- mouse interaction -----------------------------------------------------

	_bind_events()
	{
		this._on_mousedown_fn = (e) => this._on_mousedown(e);
		this._on_mousemove_fn = (e) => this._on_mousemove(e);
		this._on_mouseup_fn   = (e) => this._on_mouseup(e);
		this._on_dblclick_fn  = (e) => this._on_dblclick(e);
		this._on_wheel_fn     = (e) => this._on_wheel(e);
		this._on_contextmenu_fn = (e) => this._on_contextmenu(e);
		this._on_doc_click_fn = (e) => {
			if (this._ctxmenu && !this._ctxmenu.contains(e.target))
				this._hide_context_menu();
		};
		this._on_keydown_fn = (e) => {
			if (e.key === "f" && (e.ctrlKey || e.metaKey))
			{
				// only activate if canvas is visible
				const rect = this._canvas.getBoundingClientRect();
				if (rect.width > 0 && rect.height > 0)
				{
					e.preventDefault();
					this.show_search();
				}
			}
		};

		this._canvas.addEventListener("mousedown",   this._on_mousedown_fn);
		this._canvas.addEventListener("mousemove",   this._on_mousemove_fn);
		this._canvas.addEventListener("mouseup",     this._on_mouseup_fn);
		this._canvas.addEventListener("mouseleave",  this._on_mouseup_fn);
		this._canvas.addEventListener("dblclick",    this._on_dblclick_fn);
		this._canvas.addEventListener("wheel",       this._on_wheel_fn, { passive: false });
		this._canvas.addEventListener("contextmenu", this._on_contextmenu_fn);
		document.addEventListener("click", this._on_doc_click_fn);
		document.addEventListener("keydown", this._on_keydown_fn);
	}

	_on_contextmenu(e)
	{
		e.preventDefault();
		const rect = this._canvas.getBoundingClientRect();
		const mx = e.clientX - rect.left;
		const my = e.clientY - rect.top;
		const node = this._hit_test(mx, my);
		this._hide_context_menu();
		if (node)
			this._show_context_menu(e.clientX, e.clientY, node);
		else if (this._visible_set)
			this._show_context_menu(e.clientX, e.clientY, null);
	}

	_on_mousedown(e)
	{
		this._hide_context_menu();
		if (this._resizing) return;
		if (e.button !== 0) return;

		const rect = this._canvas.getBoundingClientRect();
		const mx = e.clientX - rect.left;
		const my = e.clientY - rect.top;
		const node = this._hit_test(mx, my);

		if (node)
		{
			// collect non-expanded descendants via outgoing edges so they move together
			const descendants = [];
			const visited = new Set();
			const collect = (n) => {
				if (visited.has(n)) return;
				visited.add(n);
				const idx = this._edge_index.get(n);
				if (!idx) return;
				for (const edge of idx.outgoing)
				{
					const child = edge.target;
					if (visited.has(child)) continue;
					if (child.expanded) continue;
					if (child.pinned) continue;
					descendants.push({ node: child, dx: child.x - node.x, dy: child.y - node.y });
					collect(child);
				}
			};
			collect(node);

			this._drag = {
				type: "node",
				node: node,
				start_x: mx,
				start_y: my,
				node_start_x: node.x,
				node_start_y: node.y,
				descendants: descendants,
				moved: false,
			};
			node.pinned = true;
		}
		else
		{
			this._drag = {
				type: "pan",
				start_x: mx,
				start_y: my,
				tx: this._transform.x,
				ty: this._transform.y,
			};
		}
	}

	_on_mousemove(e)
	{
		if (this._resizing) return;
		const rect = this._canvas.getBoundingClientRect();
		const mx = e.clientX - rect.left;
		const my = e.clientY - rect.top;

		if (this._drag)
		{
			const dx = mx - this._drag.start_x;
			const dy = my - this._drag.start_y;

			if (Math.abs(dx) > 3 || Math.abs(dy) > 3)
				this._drag.moved = true;

			if (this._drag.type == "pan")
			{
				this._transform.x = this._drag.tx + dx;
				this._transform.y = this._drag.ty + dy;
				this.render();
			}
			else if (this._drag.type == "node")
			{
				const node = this._drag.node;
				node.x = this._drag.node_start_x + dx / this._transform.scale;
				node.y = this._drag.node_start_y + dy / this._transform.scale;
				if (this._drag.descendants)
				{
					for (const d of this._drag.descendants)
					{
						d.node.x = node.x + d.dx;
						d.node.y = node.y + d.dy;
					}
				}
				this.render();
			}
			return;
		}

		const node = this._hit_test(mx, my);
		if (node !== this._hover_node)
		{
			this._hover_node = node;
			this._canvas.style.cursor = node ? "pointer" : "grab";
			if (this._on_hover)
				this._on_hover(node);
			this.render();
		}
	}

	_on_mouseup(e)
	{
		if (!this._drag)
			return;

		const drag = this._drag;
		this._drag = null;

		if (drag.type == "node" && !drag.moved)
		{
			const node = drag.node;
			if (!node.expanded && !node.unresolved && node.has_deps !== false)
				this.expand_node(node);
		}
	}

	_on_dblclick(e)
	{
		const rect = this._canvas.getBoundingClientRect();
		const mx = e.clientX - rect.left;
		const my = e.clientY - rect.top;
		const node = this._hit_test(mx, my);

		if (node && node.expanded && !node.is_root)
			this.reexpand_node(node);
		else if (node && node.opkey && this._on_navigate)
			this._on_navigate(node.opkey);
	}

	_on_wheel(e)
	{
		e.preventDefault();
		const rect = this._canvas.getBoundingClientRect();
		const mx = e.clientX - rect.left;
		const my = e.clientY - rect.top;

		const old_scale = this._transform.scale;
		const factor = e.deltaY < 0 ? 1.1 : 1 / 1.1;
		var new_scale = old_scale * factor;
		new_scale = Math.max(0.05, Math.min(4.0, new_scale));

		this._transform.x = mx - (mx - this._transform.x) * (new_scale / old_scale);
		this._transform.y = my - (my - this._transform.y) * (new_scale / old_scale);
		this._transform.scale = new_scale;
		this.render();
	}

	// -- lifecycle -------------------------------------------------------------

	destroy()
	{
		this._canvas.removeEventListener("mousedown",   this._on_mousedown_fn);
		this._canvas.removeEventListener("mousemove",   this._on_mousemove_fn);
		this._canvas.removeEventListener("mouseup",     this._on_mouseup_fn);
		this._canvas.removeEventListener("mouseleave",  this._on_mouseup_fn);
		this._canvas.removeEventListener("dblclick",    this._on_dblclick_fn);
		this._canvas.removeEventListener("wheel",       this._on_wheel_fn);
		this._canvas.removeEventListener("contextmenu", this._on_contextmenu_fn);
		document.removeEventListener("click", this._on_doc_click_fn);
		document.removeEventListener("keydown", this._on_keydown_fn);
		if (this._splitter)
			this._splitter.removeEventListener("mousedown", this._splitter_mousedown_fn);
		this._hide_context_menu();
		this.hide_search();
		if (this._fade_raf)
		{
			cancelAnimationFrame(this._fade_raf);
			this._fade_raf = null;
		}
		this._ctx = null;
	}
}