dependency_plan.bend

bendvy-ecs-core@0.1.0.3 · 150 lines · 33 definitions

1import Base
2
3type Node<Requirement:Data> is Data:
4  Node{id:U32,requirements:List<&2,Requirement>}
5type Edge is Data:
6  Edge{before:U32,after:U32}
7type 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}
13type Build<Requirement:Data> is Data:
14  Planned{order:List<&2,Node<Requirement>>,edges:List<&2,Edge>}
15  Rejected{reason:Invalid<Requirement>}
16
17def node_id(~Requirement:Data,node:Node<Requirement>) -> U32:
18  match node:
19    case Node{id,_}:id
20
21def 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
26def 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
31def 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
36def 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
41def 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
46def 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
51def 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
56def 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
61def 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
66def 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
71def 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
76def 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
81def 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
86def 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
91def 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
96def 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
101def 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
106def 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
111def 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
116def 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.
123def 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
126def before(first:U32,second:U32) -> Edge:Edge{first,second}
127def after(second:U32,first:U32) -> Edge:Edge{first,second}
128def 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)
132def chain(ids:List<&2,U32>) -> List<&2,Edge>:
133  match ids:
134    case []:[]
135    case first <> rest:chain_from(rest,first)
136
137def 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
142def 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.
149def ready(~Requirement:Data,+pending:List<&2,Node<Requirement>>,edges:List<&2,Edge>) -> List<&2,Node<Requirement>>:
150  ready_scan(~Requirement,pending,pending,edges)