1	import Base
2	import entity_key.bend as K
3	import ./relation_types.bend as G
4	import ./relation_graph.bend as Graph
5	
6	# Raw graph helpers are trusted setup, not gameplay authority. Valid hierarchy
7	# edges have one parent per source and no cycle; traversal uses E+1 small fuel.
8	# Unsupported forged cyclic graph traversal remains an incomplete diagnostic.
9	type Order is Data:
10	  Depth{}
11	  Breadth{}
12	type Walk is Data:
13	  Complete{ids:List<&2,K.Key>}
14	  Incomplete{ids:List<&2,K.Key>,pending:List<&2,K.Key>}
15	def budget(~S:Data,graph:G.Graph<S>) -> Nat:
16	  match graph:
17	    case G.Graph{edges,_}: 1n+List.length(&2,G.Edge<S>,edges)
18	def finished(acc:List<&2,K.Key>,pending:List<&2,K.Key>) -> Walk:
19	  match pending:
20	    case []: Complete{List.reverse(&2,K.Key,acc)}
21	    case pending: Incomplete{List.reverse(&2,K.Key,acc),pending}
22	def enqueue(order:Order,children:List<&2,K.Key>,rest:List<&2,K.Key>) -> List<&2,K.Key>:
23	  match order:
24	    case Depth{}: List.append(&2,K.Key,children,rest)
25	    case Breadth{}: List.append(&2,K.Key,rest,children)
26	def next_desc(~S:Data,graph:G.Graph<S>,descriptor:G.Descriptor<S>,order:Order,state:List<&2,K.Key> & List<&2,K.Key>) -> List<&2,K.Key> & List<&2,K.Key>:
27	  match state:
28	    case ([],acc): ([],acc)
29	    case (+id <> rest,acc): (enqueue(order,Graph.inverse(~S,graph,descriptor,id),rest),id <> acc)
30	def descendants_loop(~S:Data,n:Nat,state:List<&2,K.Key> & List<&2,K.Key>,+graph:G.Graph<S>,+descriptor:G.Descriptor<S>,+order:Order) -> Walk:
31	  match n state:
32	    case 0n Tuple{pending,acc}: finished(acc,pending)
33	    case 1n+rest Tuple{[],acc}: Complete{List.reverse(&2,K.Key,acc)}
34	    case 1n+rest state: descendants_loop(~S,rest,next_desc(~S,graph,descriptor,order,state),graph,descriptor,order)
35	def descendants(~S:Data,+graph:G.Graph<S>,+descriptor:G.Descriptor<S>,target:K.Key,order:Order) -> Walk:
36	  descendants_loop(~S,budget(~S,graph),(Graph.inverse(~S,graph,descriptor,target),[]),graph,descriptor,order)
37	def next_ancestor(~S:Data,graph:G.Graph<S>,descriptor:G.Descriptor<S>,state:Maybe<&2,K.Key> & List<&2,K.Key>) -> Maybe<&2,K.Key> & List<&2,K.Key>:
38	  match state:
39	    case (None{},acc): (None{},acc)
40	    case (Some{+id},acc): (Graph.target(~S,graph,descriptor,id),id <> acc)
41	def ancestor_finished(state:Maybe<&2,K.Key> & List<&2,K.Key>) -> Walk:
42	  match state:
43	    case (None{},acc): Complete{List.reverse(&2,K.Key,acc)}
44	    case (Some{id},acc): Incomplete{List.reverse(&2,K.Key,acc),[id]}
45	def ancestors_loop(~S:Data,n:Nat,state:Maybe<&2,K.Key> & List<&2,K.Key>,+graph:G.Graph<S>,+descriptor:G.Descriptor<S>) -> Walk:
46	  match n state:
47	    case 0n state: ancestor_finished(state)
48	    case 1n+rest Tuple{None{},acc}: Complete{List.reverse(&2,K.Key,acc)}
49	    case 1n+rest state: ancestors_loop(~S,rest,next_ancestor(~S,graph,descriptor,state),graph,descriptor)
50	def ancestors(~S:Data,+graph:G.Graph<S>,+descriptor:G.Descriptor<S>,target:K.Key) -> Walk:
51	  ancestors_loop(~S,budget(~S,graph),(Graph.target(~S,graph,descriptor,target),[]),graph,descriptor)
52	def root_ids(ids:List<&2,K.Key>,current:K.Key) -> K.Key:
53	  match ids:
54	    case []: current
55	    case id <> rest: root_ids(rest,id)
56	def root(walk:Walk,target:K.Key) -> Maybe<&2,K.Key>:
57	  match walk:
58	    case Complete{ids}: Some{root_ids(ids,target)}
59	    case _: None{}