1	import Base
2	
3	# Inputs are the already validated flattened DAG in topological order. The
4	# ordinary registry must derive hasDeferred from its owned command buffers.
5	type Node is Data:
6	  Node{id:U32,hasDeferred:Bool,explicit:Bool,conditional:Bool,exclusive:Bool}
7	type Edge is Data:
8	  Edge{before:U32,after:U32,ignoreDeferred:Bool}
9	type Position is Data:
10	  Position{id:U32,distance:Nat,pending:Bool}
11	type Explicit is Data:
12	  Explicit{distance:Nat,id:U32}
13	type State is Data:
14	  State{positions:List<&2,Position>,explicit:List<&2,Explicit>}
15	type Boundary is Data:
16	  Boundary{before:U32,after:U32,distance:Nat,reuse:Maybe<&2,U32>}
17	
18	def node_id(node:Node) -> U32:
19	  match node:
20	    case Node{id,_,_,_,_}:id
21	def explicit(node:Node) -> Bool:
22	  match node:
23	    case Node{_,_,isExplicit,conditional,_}:Bool.and(isExplicit,Bool.not(conditional))
24	def exclusive(node:Node) -> Bool:
25	  match node:
26	    case Node{_,_,_,_,isExclusive}:isExclusive
27	def deferred(node:Node) -> Bool:
28	  match node:
29	    case Node{_,hasDeferred,_,_,_}:hasDeferred
30	def find_choice(same:Bool,node:Node,rest:Node) -> Node:
31	  match same:
32	    case True{}:node
33	    case False{}:rest
34	def find(nodes:List<&2,Node>,+id:U32) -> Node:
35	  match nodes:
36	    case []:Node{id,False{},False{},False{},False{}}
37	    case +node <> rest:find_choice(U32.is_eq(node_id(node),id),node,find(rest,id))
38	def position_choice(same:Bool,value:Position,rest:Position) -> Position:
39	  match same:
40	    case True{}:value
41	    case False{}:rest
42	def position(positions:List<&2,Position>,+id:U32) -> Position:
43	  match positions:
44	    case []:Position{id,0n,False{}}
45	    case Position{+other,distance,pending} <> rest:position_choice(U32.is_eq(other,id),Position{other,distance,pending},position(rest,id))
46	def keep_position(same:Bool,value:Position,rest:List<&2,Position>) -> List<&2,Position>:
47	  match same:
48	    case True{}:rest
49	    case False{}:value <> rest
50	def without(positions:List<&2,Position>,+id:U32) -> List<&2,Position>:
51	  match positions:
52	    case []:[]
53	    case Position{+other,distance,pending} <> rest:keep_position(U32.is_eq(other,id),Position{other,distance,pending},without(rest,id))
54	def update(positions:List<&2,Position>,value:Position) -> List<&2,Position>:
55	  match value:
56	    case Position{+id,distance,pending}:Position{id,distance,pending} <> without(positions,id)
57	def weight(needsSync:Bool,target:Node) -> Nat:
58	  match needsSync:
59	    case True{}:1n
60	    case False{}:Bool.pick(Nat,explicit(target),1n,0n)
61	def target_updated(positions:List<&2,Position>,+distance:Nat,+needsSync:Bool,+ignored:Bool,target:Node,current:Position) -> List<&2,Position>:
62	  match current:
63	    case Position{id,oldDistance,pending}:update(positions,Position{id,Nat.max(oldDistance,Nat.add(distance,weight(Bool.and(needsSync,Bool.not(ignored)),target))),Bool.or(pending,Bool.and(needsSync,ignored))})
64	def outgoing_edge(positions:List<&2,Position>,distance:Nat,needsSync:Bool,ignoreDeferred:Bool,+target:Node,current:Position) -> List<&2,Position>:
65	  target_updated(positions,distance,needsSync,Bool.and(ignoreDeferred,Bool.not(exclusive(target))),target,current)
66	def selected_edge(positions:List<&2,Position>,distance:Nat,needsSync:Bool,ignoreDeferred:Bool,target:Node,current:Position,matches:Bool) -> List<&2,Position>:
67	  match matches:
68	    case False{}:positions
69	    case True{}:outgoing_edge(positions,distance,needsSync,ignoreDeferred,target,current)
70	def outgoing(edges:List<&2,Edge>,+nodes:List<&2,Node>,+id:U32,+distance:Nat,+needsSync:Bool,+positions:List<&2,Position>) -> List<&2,Position>:
71	  match edges:
72	    case []:positions
73	    case Edge{before,+after,ignoreDeferred} <> rest:outgoing(rest,nodes,id,distance,needsSync,selected_edge(positions,distance,needsSync,ignoreDeferred,find(nodes,after),position(positions,after),U32.is_eq(before,id)))
74	def syncs(isExplicit:Bool,id:U32,distance:Nat,explicitNodes:List<&2,Explicit>) -> List<&2,Explicit>:
75	  match isExplicit:
76	    case True{}:Explicit{distance,id} <> explicitNodes
77	    case False{}:explicitNodes
78	def visit_position(+node:Node,edges:List<&2,Edge>,nodes:List<&2,Node>,positions:List<&2,Position>,explicitNodes:List<&2,Explicit>,current:Position) -> State:
79	  match current:
80	    case Position{+id,+distance,pending}:State{outgoing(edges,nodes,id,distance,Bool.and(Bool.not(explicit(node)),Bool.or(pending,deferred(node))),positions),syncs(explicit(node),id,distance,explicitNodes)}
81	def visit(+node:Node,edges:List<&2,Edge>,nodes:List<&2,Node>,state:State) -> State:
82	  match state:
83	    case State{+positions,explicitNodes}:visit_position(node,edges,nodes,positions,explicitNodes,position(positions,node_id(node)))
84	def distances(order:List<&2,Node>,+nodes:List<&2,Node>,+edges:List<&2,Edge>,state:State) -> State:
85	  match order:
86	    case []:state
87	    case node <> rest:distances(rest,nodes,edges,visit(node,edges,nodes,state))
88	def explicit_choice(same:Bool,id:U32,rest:Maybe<&2,U32>) -> Maybe<&2,U32>:
89	  match same:
90	    case True{}:Some{id}
91	    case False{}:rest
92	def reuse(explicitNodes:List<&2,Explicit>,+distance:Nat) -> Maybe<&2,U32>:
93	  match explicitNodes:
94	    case []:None{}
95	    case Explicit{other,id} <> rest:explicit_choice(Nat.is_eq(other,distance),id,reuse(rest,distance))
96	def boundary_step(before:U32,after:U32,from:Position,to:Position,target:Node,explicitNodes:List<&2,Explicit>,+rest:List<&2,Boundary>) -> List<&2,Boundary>:
97	  match from to target:
98	    case Position{_,distance,_} Position{_,+next,_} Node{_,_,isExplicit,_,_}:Bool.pick(List<&2,Boundary>,Bool.or(Nat.is_eq(distance,next),isExplicit),rest,Boundary{before,after,next,reuse(explicitNodes,next)} <> rest)
99	def boundaries(edges:List<&2,Edge>,+nodes:List<&2,Node>,+positions:List<&2,Position>,+explicitNodes:List<&2,Explicit>) -> List<&2,Boundary>:
100	  match edges:
101	    case []:[]
102	    case Edge{+before,+after,_} <> rest:boundary_step(before,after,position(positions,before),position(positions,after),find(nodes,after),explicitNodes,boundaries(rest,nodes,positions,explicitNodes))
103	def planned(nodes:List<&2,Node>,edges:List<&2,Edge>,state:State) -> List<&2,Boundary>:
104	  match state:
105	    case State{positions,explicitNodes}:boundaries(edges,nodes,positions,explicitNodes)
106	
107	# Bevy ad678262, schedule/auto_insert_apply_deferred.rs build: distance rises
108	# for a needed sync or an unconditional explicit sync target. Ignored edges
109	# postpone deferred visibility through later nodes; exclusive targets override
110	# that suppression. Reuse one explicit boundary at the required distance.
111	# Final flushing is an executor setting, independent of this graph-build pass.
112	def plan(enabled:Bool,+order:List<&2,Node>,+edges:List<&2,Edge>) -> List<&2,Boundary>:
113	  match enabled:
114	    case False{}:[]
115	    case True{}:planned(order,edges,distances(order,order,edges,State{[],[]}))