1	import Base
2	
3	type Node<Requirement:Data> is Data:
4	  Node{id:U32,requirements:List<&2,Requirement>}
5	type Edge is Data:
6	  Edge{before:U32,after:U32}
7	type Invalid<Requirement:Data> is Data:
8	  Duplicate{id:U32}
9	  UnknownDependency{id:U32}
10	  Missing{id:U32,requirement:Requirement}
11	  Cycle{}
12	  InvalidCondition{id:U32}
13	type Build<Requirement:Data> is Data:
14	  Planned{order:List<&2,Node<Requirement>>,edges:List<&2,Edge>}
15	  Rejected{reason:Invalid<Requirement>}
16	
17	def node_id(~Requirement:Data,node:Node<Requirement>) -> U32:
18	  match node:
19	    case Node{id,_}:id
20	
21	def has(~Requirement:Data,nodes:List<&2,Node<Requirement>>,+id:U32) -> Bool:
22	  match nodes:
23	    case []:False{}
24	    case Node{other,_} <> rest:Bool.or(U32.is_eq(other,id),has(~Requirement,rest,id))
25	
26	def duplicate_step(~Requirement:Data,found:Bool,id:U32,next:Maybe<&2,Invalid<Requirement>>) -> Maybe<&2,Invalid<Requirement>>:
27	  match found:
28	    case True{}:Some{Duplicate{id}}
29	    case False{}:next
30	
31	def duplicates(~Requirement:Data,nodes:List<&2,Node<Requirement>>) -> Maybe<&2,Invalid<Requirement>>:
32	  match nodes:
33	    case []:None{}
34	    case Node{+id,_} <> +rest:duplicate_step(~Requirement,has(~Requirement,rest,id),id,duplicates(~Requirement,rest))
35	
36	def endpoint(~Requirement:Data,known:Bool,id:U32,next:Maybe<&2,Invalid<Requirement>>) -> Maybe<&2,Invalid<Requirement>>:
37	  match known:
38	    case False{}:Some{UnknownDependency{id}}
39	    case True{}:next
40	
41	def endpoints(~Requirement:Data,edges:List<&2,Edge>,+nodes:List<&2,Node<Requirement>>) -> Maybe<&2,Invalid<Requirement>>:
42	  match edges:
43	    case []:None{}
44	    case Edge{+before,+after} <> rest:endpoint(~Requirement,has(~Requirement,nodes,before),before,endpoint(~Requirement,has(~Requirement,nodes,after),after,endpoints(~Requirement,rest,nodes)))
45	
46	def requirement_step(~Requirement:Data,present:Bool,id:U32,requirement:Requirement,next:Maybe<&2,Invalid<Requirement>>) -> Maybe<&2,Invalid<Requirement>>:
47	  match present:
48	    case False{}:Some{Missing{id,requirement}}
49	    case True{}:next
50	
51	def requirements(~Requirement:Data,~available:Requirement -> Bool,needs:List<&2,Requirement>,+id:U32) -> Maybe<&2,Invalid<Requirement>>:
52	  match needs:
53	    case []:None{}
54	    case +first <> rest:requirement_step(~Requirement,available(first),id,first,requirements(~Requirement,~available,rest,id))
55	
56	def first_error(~Requirement:Data,first:Maybe<&2,Invalid<Requirement>>,next:Maybe<&2,Invalid<Requirement>>) -> Maybe<&2,Invalid<Requirement>>:
57	  match first:
58	    case None{}:next
59	    case Some{reason}:Some{reason}
60	
61	def provisioned(~Requirement:Data,~available:Requirement -> Bool,nodes:List<&2,Node<Requirement>>) -> Maybe<&2,Invalid<Requirement>>:
62	  match nodes:
63	    case []:None{}
64	    case Node{id,needs} <> rest:first_error(~Requirement,requirements(~Requirement,~available,needs,id),provisioned(~Requirement,~available,rest))
65	
66	def predecessor_pending(~Requirement:Data,edges:List<&2,Edge>,+pending:List<&2,Node<Requirement>>,+id:U32) -> Bool:
67	  match edges:
68	    case []:False{}
69	    case Edge{before,after} <> rest:Bool.or(Bool.and(U32.is_eq(after,id),has(~Requirement,pending,before)),predecessor_pending(~Requirement,rest,pending,id))
70	
71	def choose(~Requirement:Data,blocked:Bool,node:Node<Requirement>,next:Maybe<&2,Node<Requirement>>) -> Maybe<&2,Node<Requirement>>:
72	  match blocked:
73	    case False{}:Some{node}
74	    case True{}:next
75	
76	def next_ready(~Requirement:Data,candidates:List<&2,Node<Requirement>>,+pending:List<&2,Node<Requirement>>,+edges:List<&2,Edge>) -> Maybe<&2,Node<Requirement>>:
77	  match candidates:
78	    case []:None{}
79	    case +first <> rest:choose(~Requirement,predecessor_pending(~Requirement,edges,pending,node_id(~Requirement,first)),first,next_ready(~Requirement,rest,pending,edges))
80	
81	def keep_other(~Requirement:Data,same:Bool,node:Node<Requirement>,rest:List<&2,Node<Requirement>>) -> List<&2,Node<Requirement>>:
82	  match same:
83	    case True{}:rest
84	    case False{}:node <> rest
85	
86	def remove(~Requirement:Data,nodes:List<&2,Node<Requirement>>,+id:U32) -> List<&2,Node<Requirement>>:
87	  match nodes:
88	    case []:[]
89	    case +first <> rest:keep_other(~Requirement,U32.is_eq(node_id(~Requirement,first),id),first,remove(~Requirement,rest,id))
90	
91	def prepend(~Requirement:Data,node:Node<Requirement>,built:Build<Requirement>) -> Build<Requirement>:
92	  match built:
93	    case Rejected{reason}:Rejected{reason}
94	    case Planned{order,edges}:Planned{node <> order,edges}
95	
96	def selected(~Requirement:Data,choice:Maybe<&2,Node<Requirement>>,next:Node<Requirement> -> Build<Requirement>) -> Build<Requirement>:
97	  match choice:
98	    case None{}:Rejected{Cycle{}}
99	    case Some{node}:next(node)
100	
101	def exhausted(~Requirement:Data,pending:List<&2,Node<Requirement>>,edges:List<&2,Edge>) -> Build<Requirement>:
102	  match pending:
103	    case []:Planned{[],edges}
104	    case _ :Rejected{Cycle{}}
105	
106	def progress(~Requirement:Data,+pending:List<&2,Node<Requirement>>,+edges:List<&2,Edge>,next:List<&2,Node<Requirement>> -> Build<Requirement>) -> Build<Requirement>:
107	  match pending:
108	    case []:Planned{[],edges}
109	    case _ :selected(~Requirement,next_ready(~Requirement,pending,pending,edges),+node => prepend(~Requirement,node,next(remove(~Requirement,pending,node_id(~Requirement,node)))))
110	
111	def sort(~Requirement:Data,fuel:Nat,pending:List<&2,Node<Requirement>>,+edges:List<&2,Edge>) -> Build<Requirement>:
112	  match fuel:
113	    case 0n:exhausted(~Requirement,pending,edges)
114	    case 1n+prior:progress(~Requirement,pending,edges,remaining => sort(~Requirement,prior,remaining,edges))
115	
116	def validated(~Requirement:Data,invalid:Maybe<&2,Invalid<Requirement>>,+nodes:List<&2,Node<Requirement>>,edges:List<&2,Edge>) -> Build<Requirement>:
117	  match invalid:
118	    case Some{reason}:Rejected{reason}
119	    case None{}:sort(~Requirement,List.length(&2,Node<Requirement>,nodes),nodes,edges)
120	
121	# Metadata does not grant access. The ordinary registration constructor supplies
122	# these nodes from the declarations that also construct its confined capabilities.
123	def build(~Requirement:Data,~available:Requirement -> Bool,+nodes:List<&2,Node<Requirement>>,+edges:List<&2,Edge>) -> Build<Requirement>:
124	  validated(~Requirement,first_error(~Requirement,duplicates(~Requirement,nodes),first_error(~Requirement,endpoints(~Requirement,edges,nodes),provisioned(~Requirement,~available,nodes))),nodes,edges)
125	
126	def before(first:U32,second:U32) -> Edge:Edge{first,second}
127	def after(second:U32,first:U32) -> Edge:Edge{first,second}
128	def chain_from(ids:List<&2,U32>,+previous:U32) -> List<&2,Edge>:
129	  match ids:
130	    case []:[]
131	    case +next <> rest:Edge{previous,next} <> chain_from(rest,next)
132	def chain(ids:List<&2,U32>) -> List<&2,Edge>:
133	  match ids:
134	    case []:[]
135	    case first <> rest:chain_from(rest,first)
136	
137	def ready_member(~Requirement:Data,blocked:Bool,node:Node<Requirement>,rest:List<&2,Node<Requirement>>) -> List<&2,Node<Requirement>>:
138	  match blocked:
139	    case True{}:rest
140	    case False{}:node <> rest
141	
142	def ready_scan(~Requirement:Data,candidates:List<&2,Node<Requirement>>,+pending:List<&2,Node<Requirement>>,+edges:List<&2,Edge>) -> List<&2,Node<Requirement>>:
143	  match candidates:
144	    case []:[]
145	    case +first <> rest:ready_member(~Requirement,predecessor_pending(~Requirement,edges,pending,node_id(~Requirement,first)),first,ready_scan(~Requirement,rest,pending,edges))
146	
147	# Pending contains every not-yet-completed node, including disabled or refused
148	# work until its completion is recorded. Success is not a prerequisite here.
149	def ready(~Requirement:Data,+pending:List<&2,Node<Requirement>>,edges:List<&2,Edge>) -> List<&2,Node<Requirement>>:
150	  ready_scan(~Requirement,pending,pending,edges)