1	import Base
2	import entity_key.bend as K
3	import relation_types.bend as T
4	
5	# Experimental maintained inverse implementation. Does not call graph-spec.
6	def key_erased(-S: Data,descriptor: T.Descriptor<S>) -> U32:
7	  match descriptor:
8	    case T.Descriptor{key,_,_,_}: key
9	def name_erased(-S: Data,descriptor: T.Descriptor<S>) -> String:
10	  match descriptor:
11	    case T.Descriptor{_,name,_,_}: name
12	def contains(xs: List<&2,K.Key>,+id: K.Key) -> Bool:
13	  match xs:
14	    case []: False{}
15	    case x <> rest: Bool.or(K.equal(x,id),contains(rest,id))
16	def removed_id(remove: Bool,id: K.Key,rest: List<&2,K.Key>) -> List<&2,K.Key>:
17	  match remove:
18	    case True{}: rest
19	    case False{}: id <> rest
20	def remove_id(xs: List<&2,K.Key>,+id: K.Key) -> List<&2,K.Key>:
21	  match xs:
22	    case []: []
23	    case +x <> rest: removed_id(K.equal(x,id),x,remove_id(rest,id))
24	def chosen_target(found: Bool,target: K.Key,next: Unit -> Maybe<&2,K.Key>) -> Maybe<&2,K.Key>:
25	  match found:
26	    case True{}: Some{target}
27	    case False{}: next(Unit{})
28	def target_edges_erased(-S: Data,edges: List<&2,T.Edge<S>>,+descriptor: T.Descriptor<S>,+source: K.Key) -> Maybe<&2,K.Key>:
29	  match edges:
30	    case []: None{}
31	    case T.Edge{other,id,target} <> rest: chosen_target(Bool.and(U32.is_eq(key_erased(S,other),key_erased(S,descriptor)),K.equal(id,source)),target,_ => target_edges_erased(S,rest,descriptor,source))
32	def target_erased(-S: Data,graph: T.Graph<S>,descriptor: T.Descriptor<S>,source: K.Key) -> Maybe<&2,K.Key>:
33	  match graph:
34	    case T.Graph{edges,_}: target_edges_erased(S,edges,descriptor,source)
35	def chosen_inverse(found: Bool,sources: List<&2,K.Key>,next: Unit -> List<&2,K.Key>) -> List<&2,K.Key>:
36	  match found:
37	    case True{}: sources
38	    case False{}: next(Unit{})
39	def inverse_entries_erased(-S: Data,entries: List<&2,T.Inverse<S>>,+descriptor: T.Descriptor<S>,+target: K.Key) -> List<&2,K.Key>:
40	  match entries:
41	    case []: []
42	    case T.Inverse{other,id,sources} <> rest: chosen_inverse(Bool.and(U32.is_eq(key_erased(S,other),key_erased(S,descriptor)),K.equal(id,target)),sources,_ => inverse_entries_erased(S,rest,descriptor,target))
43	def inverse_erased(-S: Data,graph: T.Graph<S>,descriptor: T.Descriptor<S>,target: K.Key) -> List<&2,K.Key>:
44	  match graph:
45	    case T.Graph{_,entries}: inverse_entries_erased(S,entries,descriptor,target)
46	def edge_removed_erased(-S: Data,remove: Bool,edge: T.Edge<S>,rest: List<&2,T.Edge<S>>) -> List<&2,T.Edge<S>>:
47	  match remove:
48	    case True{}: rest
49	    case False{}: edge <> rest
50	def remove_edge_fields_erased(-S: Data,edge: T.Edge<S>,+descriptor: T.Descriptor<S>,source: K.Key,next: Unit -> List<&2,T.Edge<S>>) -> List<&2,T.Edge<S>>:
51	  match edge:
52	    case T.Edge{+other,+id,+target}: edge_removed_erased(S,Bool.and(U32.is_eq(key_erased(S,other),key_erased(S,descriptor)),K.equal(id,source)),T.Edge{other,id,target},next(Unit{}))
53	def remove_edge_keep_erased(-S:Data,edge:T.Edge<S>,+descriptor:T.Descriptor<S>,source:K.Key,acc:List<&2,T.Edge<S>>) -> List<&2,T.Edge<S>>:
54	  match edge:
55	    case T.Edge{+other,+id,+target}: edge_removed_erased(S,Bool.and(U32.is_eq(key_erased(S,other),key_erased(S,descriptor)),K.equal(id,source)),T.Edge{other,id,target},acc)
56	def remove_edge_acc_erased(-S:Data,edges:List<&2,T.Edge<S>>,+descriptor:T.Descriptor<S>,+source:K.Key,acc:List<&2,T.Edge<S>>) -> List<&2,T.Edge<S>>:
57	  match edges:
58	    case []: List.reverse(&2,T.Edge<S>,acc)
59	    case +edge <> rest: remove_edge_acc_erased(S,rest,descriptor,source,remove_edge_keep_erased(S,edge,descriptor,source,acc))
60	def remove_edge_erased(-S: Data,edges: List<&2,T.Edge<S>>,descriptor: T.Descriptor<S>,source: K.Key) -> List<&2,T.Edge<S>>:
61	  remove_edge_acc_erased(S,edges,descriptor,source,[])
62	def nonempty_inverse_erased(-S: Data,descriptor: T.Descriptor<S>,target: K.Key,sources: List<&2,K.Key>,rest: List<&2,T.Inverse<S>>) -> List<&2,T.Inverse<S>>:
63	  match sources:
64	    case []: rest
65	    case head <> tail: T.Inverse{descriptor,target,head <> tail} <> rest
66	def inverse_remove_one_erased(-S: Data,matched: Bool,descriptor: T.Descriptor<S>,target: K.Key,sources: List<&2,K.Key>,source: K.Key,rest: List<&2,T.Inverse<S>>) -> List<&2,T.Inverse<S>>:
67	  match matched:
68	    case True{}: nonempty_inverse_erased(S,descriptor,target,remove_id(sources,source),rest)
69	    case False{}: T.Inverse{descriptor,target,sources} <> rest
70	def inverse_remove_acc_erased(-S:Data,entries:List<&2,T.Inverse<S>>,+descriptor:T.Descriptor<S>,+target:K.Key,+source:K.Key,acc:List<&2,T.Inverse<S>>) -> List<&2,T.Inverse<S>>:
71	  match entries:
72	    case []: List.reverse(&2,T.Inverse<S>,acc)
73	    case T.Inverse{+other,+id,sources} <> rest: inverse_remove_acc_erased(S,rest,descriptor,target,source,inverse_remove_one_erased(S,Bool.and(U32.is_eq(key_erased(S,other),key_erased(S,descriptor)),K.equal(id,target)),other,id,sources,source,acc))
74	def inverse_remove_erased(-S: Data,entries: List<&2,T.Inverse<S>>,descriptor: T.Descriptor<S>,target: K.Key,source: K.Key) -> List<&2,T.Inverse<S>>:
75	  inverse_remove_acc_erased(S,entries,descriptor,target,source,[])
76	def remove_previous_erased(-S: Data,previous: Maybe<&2,K.Key>,entries: List<&2,T.Inverse<S>>,descriptor: T.Descriptor<S>,source: K.Key) -> List<&2,T.Inverse<S>>:
77	  match previous:
78	    case None{}: entries
79	    case Some{target}: inverse_remove_erased(S,entries,descriptor,target,source)
80	def appended_source(present: Bool,sources: List<&2,K.Key>,source: K.Key) -> List<&2,K.Key>:
81	  match present:
82	    case True{}: sources
83	    case False{}: List.append(&2,K.Key,sources,[source])
84	def inverse_add_found_erased(-S: Data,found: Bool,other: T.Descriptor<S>,id: K.Key,+sources: List<&2,K.Key>,+descriptor: T.Descriptor<S>,target: K.Key,+source: K.Key,rest: List<&2,T.Inverse<S>>,next: Unit -> List<&2,T.Inverse<S>>) -> List<&2,T.Inverse<S>>:
85	  match found:
86	    case True{}: T.Inverse{other,id,appended_source(contains(sources,source),sources,source)} <> rest
87	    case False{}: T.Inverse{other,id,sources} <> next(Unit{})
88	def inverse_add_erased(-S: Data,entries: List<&2,T.Inverse<S>>,+descriptor: T.Descriptor<S>,+target: K.Key,+source: K.Key) -> List<&2,T.Inverse<S>>:
89	  match entries:
90	    case []: [T.Inverse{descriptor,target,[source]}]
91	    case T.Inverse{+other,+id,+sources} <> +rest: inverse_add_found_erased(S,Bool.and(U32.is_eq(key_erased(S,other),key_erased(S,descriptor)),K.equal(id,target)),other,id,sources,descriptor,target,source,rest,_ => inverse_add_erased(S,rest,descriptor,target,source))
92	def unrelate_erased(-S: Data,graph: T.Graph<S>,+descriptor: T.Descriptor<S>,+source: K.Key) -> T.Graph<S>:
93	  match graph:
94	    case T.Graph{+edges,inverses}: T.Graph{remove_edge_erased(S,edges,descriptor,source),remove_previous_erased(S,target_edges_erased(S,edges,descriptor,source),inverses,descriptor,source)}
95	def next_cycle_erased(-S: Data,current: Maybe<&2,K.Key>,next: K.Key -> Bool) -> Bool:
96	  match current:
97	    case None{}: False{}
98	    case Some{id}: next(id)
99	def cycle_loop_erased(-S: Data,fuel: Nat,+graph: T.Graph<S>,+descriptor: T.Descriptor<S>,+source: K.Key,+current: K.Key) -> Bool:
100	  match fuel:
101	    case 0n: K.equal(source,current)
102	    case 1n+rest: Bool.or(K.equal(source,current),next_cycle_erased(S,target_erased(S,graph,descriptor,current),id => cycle_loop_erased(S,rest,graph,descriptor,source,id)))
103	def cycle_erased(-S: Data,+graph: T.Graph<S>,descriptor: T.Descriptor<S>,source: K.Key,target: K.Key) -> Bool:
104	  match graph descriptor:
105	    case T.Graph{edges,inverses} T.Descriptor{k,n,inv,T.Ordinary{}}: False{}
106	    case T.Graph{+edges,+inverses} T.Descriptor{+k,+n,+inv,T.Hierarchy{}}: cycle_loop_erased(S,List.length(&2,T.Edge<S>,edges),T.Graph{edges,inverses},T.Descriptor{k,n,inv,T.Hierarchy{}},source,target)
107	def validation(sourceLive: Bool,targetLive: Bool,self: Bool,cyclic: Bool,source: K.Key,target: K.Key,name: String) -> Maybe<&2,T.Error>:
108	  match sourceLive targetLive self cyclic:
109	    case False{} _ _ _: Some{T.MissingEntity{source}}
110	    case True{} False{} _ _: Some{T.MissingTargetEntity{source,target,name}}
111	    case True{} True{} True{} _: Some{T.SelfRelationNotAllowed{source,name}}
112	    case True{} True{} False{} True{}: Some{T.HierarchyCycle{source,target,name}}
113	    case True{} True{} False{} False{}: None{}
114	def already(previous: Maybe<&2,K.Key>,target: K.Key) -> Bool:
115	  match previous:
116	    case None{}: False{}
117	    case Some{id}: K.equal(id,target)
118	def updated_erased(-S: Data,same: Bool,+edges: List<&2,T.Edge<S>>,inverses: List<&2,T.Inverse<S>>,+descriptor: T.Descriptor<S>,+source: K.Key,+target: K.Key) -> T.Graph<S>:
119	  match same:
120	    case True{}: T.Graph{edges,inverses}
121	    case False{}: T.Graph{List.append(&2,T.Edge<S>,remove_edge_erased(S,edges,descriptor,source),[T.Edge{descriptor,source,target}]),inverse_add_erased(S,remove_previous_erased(S,target_edges_erased(S,edges,descriptor,source),inverses,descriptor,source),descriptor,target,source)}
122	def checked_erased(-S: Data,error: Maybe<&2,T.Error>,graph: T.Graph<S>,+descriptor: T.Descriptor<S>,+source: K.Key,+target: K.Key) -> T.CoreResult<S>:
123	  match error graph:
124	    case Some{error} graph: T.CoreResult{graph,Some{error}}
125	    case None{} T.Graph{+edges,inverses}: T.CoreResult{updated_erased(S,already(target_edges_erased(S,edges,descriptor,source),target),edges,inverses,descriptor,source,target),None{}}
126	def relate_erased(-S: Data,+graph: T.Graph<S>,+descriptor: T.Descriptor<S>,+source: K.Key,+target: K.Key,sourceLive: Bool,targetLive: Bool) -> T.CoreResult<S>:
127	  checked_erased(S,validation(sourceLive,targetLive,K.equal(source,target),cycle_erased(S,graph,descriptor,source,target),source,target,name_erased(S,descriptor)),graph,descriptor,source,target)
128	def project_erased(-S: Data,graph: T.Graph<S>) -> T.SpecGraph<S>:
129	  match graph:
130	    case T.Graph{edges,_}: T.SpecGraph{edges}
131	# Public schema-specialized entry points delegate to the same erased algorithms.
132	def key(~S: Data,descriptor: T.Descriptor<S>) -> U32:
133	  key_erased(S,descriptor)
134	def name(~S: Data,descriptor: T.Descriptor<S>) -> String:
135	  name_erased(S,descriptor)
136	def target_edges(~S: Data,edges: List<&2,T.Edge<S>>,+descriptor: T.Descriptor<S>,+source: K.Key) -> Maybe<&2,K.Key>:
137	  target_edges_erased(S,edges,descriptor,source)
138	def target(~S: Data,graph: T.Graph<S>,descriptor: T.Descriptor<S>,source: K.Key) -> Maybe<&2,K.Key>:
139	  target_erased(S,graph,descriptor,source)
140	def inverse_entries(~S: Data,entries: List<&2,T.Inverse<S>>,+descriptor: T.Descriptor<S>,+target: K.Key) -> List<&2,K.Key>:
141	  inverse_entries_erased(S,entries,descriptor,target)
142	def inverse(~S: Data,graph: T.Graph<S>,descriptor: T.Descriptor<S>,target: K.Key) -> List<&2,K.Key>:
143	  inverse_erased(S,graph,descriptor,target)
144	def edge_removed(~S: Data,remove: Bool,edge: T.Edge<S>,rest: List<&2,T.Edge<S>>) -> List<&2,T.Edge<S>>:
145	  edge_removed_erased(S,remove,edge,rest)
146	def remove_edge_fields(~S: Data,edge: T.Edge<S>,+descriptor: T.Descriptor<S>,source: K.Key,next: Unit -> List<&2,T.Edge<S>>) -> List<&2,T.Edge<S>>:
147	  remove_edge_fields_erased(S,edge,descriptor,source,next)
148	def remove_edge_keep(~S:Data,edge:T.Edge<S>,+descriptor:T.Descriptor<S>,source:K.Key,acc:List<&2,T.Edge<S>>) -> List<&2,T.Edge<S>>:
149	  remove_edge_keep_erased(S,edge,descriptor,source,acc)
150	def remove_edge_acc(~S:Data,edges:List<&2,T.Edge<S>>,+descriptor:T.Descriptor<S>,+source:K.Key,acc:List<&2,T.Edge<S>>) -> List<&2,T.Edge<S>>:
151	  remove_edge_acc_erased(S,edges,descriptor,source,acc)
152	def remove_edge(~S: Data,edges: List<&2,T.Edge<S>>,descriptor: T.Descriptor<S>,source: K.Key) -> List<&2,T.Edge<S>>:
153	  remove_edge_erased(S,edges,descriptor,source)
154	def nonempty_inverse(~S: Data,descriptor: T.Descriptor<S>,target: K.Key,sources: List<&2,K.Key>,rest: List<&2,T.Inverse<S>>) -> List<&2,T.Inverse<S>>:
155	  nonempty_inverse_erased(S,descriptor,target,sources,rest)
156	def inverse_remove_one(~S: Data,matched: Bool,descriptor: T.Descriptor<S>,target: K.Key,sources: List<&2,K.Key>,source: K.Key,rest: List<&2,T.Inverse<S>>) -> List<&2,T.Inverse<S>>:
157	  inverse_remove_one_erased(S,matched,descriptor,target,sources,source,rest)
158	def inverse_remove_acc(~S:Data,entries:List<&2,T.Inverse<S>>,+descriptor:T.Descriptor<S>,+target:K.Key,+source:K.Key,acc:List<&2,T.Inverse<S>>) -> List<&2,T.Inverse<S>>:
159	  inverse_remove_acc_erased(S,entries,descriptor,target,source,acc)
160	def inverse_remove(~S: Data,entries: List<&2,T.Inverse<S>>,descriptor: T.Descriptor<S>,target: K.Key,source: K.Key) -> List<&2,T.Inverse<S>>:
161	  inverse_remove_erased(S,entries,descriptor,target,source)
162	def remove_previous(~S: Data,previous: Maybe<&2,K.Key>,entries: List<&2,T.Inverse<S>>,descriptor: T.Descriptor<S>,source: K.Key) -> List<&2,T.Inverse<S>>:
163	  remove_previous_erased(S,previous,entries,descriptor,source)
164	def inverse_add_found(~S: Data,found: Bool,other: T.Descriptor<S>,id: K.Key,+sources: List<&2,K.Key>,+descriptor: T.Descriptor<S>,target: K.Key,+source: K.Key,rest: List<&2,T.Inverse<S>>,next: Unit -> List<&2,T.Inverse<S>>) -> List<&2,T.Inverse<S>>:
165	  inverse_add_found_erased(S,found,other,id,sources,descriptor,target,source,rest,next)
166	def inverse_add(~S: Data,entries: List<&2,T.Inverse<S>>,+descriptor: T.Descriptor<S>,+target: K.Key,+source: K.Key) -> List<&2,T.Inverse<S>>:
167	  inverse_add_erased(S,entries,descriptor,target,source)
168	def unrelate(~S: Data,graph: T.Graph<S>,+descriptor: T.Descriptor<S>,+source: K.Key) -> T.Graph<S>:
169	  unrelate_erased(S,graph,descriptor,source)
170	def next_cycle(~S: Data,current: Maybe<&2,K.Key>,next: K.Key -> Bool) -> Bool:
171	  next_cycle_erased(S,current,next)
172	def cycle_loop(~S: Data,fuel: Nat,+graph: T.Graph<S>,+descriptor: T.Descriptor<S>,+source: K.Key,+current: K.Key) -> Bool:
173	  cycle_loop_erased(S,fuel,graph,descriptor,source,current)
174	def cycle(~S: Data,+graph: T.Graph<S>,descriptor: T.Descriptor<S>,source: K.Key,target: K.Key) -> Bool:
175	  cycle_erased(S,graph,descriptor,source,target)
176	def updated(~S: Data,same: Bool,+edges: List<&2,T.Edge<S>>,inverses: List<&2,T.Inverse<S>>,+descriptor: T.Descriptor<S>,+source: K.Key,+target: K.Key) -> T.Graph<S>:
177	  updated_erased(S,same,edges,inverses,descriptor,source,target)
178	def checked(~S: Data,error: Maybe<&2,T.Error>,graph: T.Graph<S>,+descriptor: T.Descriptor<S>,+source: K.Key,+target: K.Key) -> T.CoreResult<S>:
179	  checked_erased(S,error,graph,descriptor,source,target)
180	def relate(~S: Data,+graph: T.Graph<S>,+descriptor: T.Descriptor<S>,+source: K.Key,+target: K.Key,sourceLive: Bool,targetLive: Bool) -> T.CoreResult<S>:
181	  relate_erased(S,graph,descriptor,source,target,sourceLive,targetLive)
182	def project(~S: Data,graph: T.Graph<S>) -> T.SpecGraph<S>:
183	  project_erased(S,graph)