1	import Base
2	
3	# Edlib sentinels are distinct constructors, never wrapped U32 values.
4	type Mode is Data:
5	  NW{}
6	  SHW{}
7	  HW{}
8	
9	type Task is Data:
10	  Distance{}
11	  Locations{}
12	  Path{}
13	
14	type Threshold is Data:
15	  Unlimited{}
16	  MaxDistance{value: Nat}
17	
18	type EqualityPair is Data:
19	  EqualityPair{first: Char, second: Char}
20	
21	type CigarFormat is Data:
22	  Standard{}
23	  Extended{}
24	
25	type AlignConfig is Data:
26	  AlignConfig{mode: Mode, task: Task, threshold: Threshold,
27	    equalities: List<&2, EqualityPair>, cigar_format: CigarFormat}
28	
29	# Each independent batch job keeps its own configuration and orientation.
30	type AlignJob is Data:
31	  AlignJob{query: String, target: String, config: AlignConfig}
32	
33	type Status is Data:
34	  Ok{}
35	  Error{}
36	
37	type EditDistance is Data:
38	  Found{value: Nat}
39	  NotFound{}
40	
41	type Coordinate is Data:
42	  BeforeStart{}
43	  Position{index: Nat}
44	
45	type Operation is Data:
46	  Match{}
47	  Insert{}
48	  Delete{}
49	  Mismatch{}
50	
51	# Encoded runs have positive counts and are merged after mapping to the selected
52	# alphabet: adjacent Match/Mismatch operations form one Standard M run.
53	type CigarRun is Data:
54	  CigarRun{count: Nat, symbol: Char}
55	
56	type AlignResult is Data:
57	  AlignResult{status: Status, distance: EditDistance,
58	    end_locations: List<&2, Coordinate>,
59	    start_locations: Maybe<&2, List<&2, Coordinate>>,
60	    alignment: Maybe<&2, List<&2, Operation>>, cigar: Maybe<&2, String>}
61	
62	def default_config() -> AlignConfig:
63	  AlignConfig{NW{}, Distance{}, Unlimited{}, Nil{}, Extended{}}
64	
65	# Literal equality plus explicitly configured symmetric pairs. Scanning the
66	# pairs never follows a chain, so shared endpoints do not imply transitivity.
67	def pair_matches(pair: EqualityPair, +a: Char, +b: Char) -> Bool:
68	  match pair:
69	    case EqualityPair{+first, +second}:
70	      Bool.or(Bool.and(Char.is_eq(a, first), Char.is_eq(b, second)),
71	        Bool.and(Char.is_eq(a, second), Char.is_eq(b, first)))
72	
73	def equal(pairs: List<&2, EqualityPair>, +a: Char, +b: Char) -> Bool:
74	  match pairs:
75	    case Nil{}:
76	      Char.is_eq(a, b)
77	    case pair <> tail:
78	      Bool.or(pair_matches(pair, a, b), equal(tail, a, b))
79	
80	def end_coordinate(length: Nat) -> Coordinate:
81	  match length:
82	    case 0n:
83	      BeforeStart{}
84	    case 1n+p:
85	      Position{p}
86	
87	def distance_show(distance: EditDistance) -> String:
88	  match distance:
89	    case Found{value}:
90	      Nat.show(value)
91	    case NotFound{}:
92	      "-1"
93	
94	def coordinate_show(position: Coordinate) -> String:
95	  match position:
96	    case BeforeStart{}:
97	      "-1"
98	    case Position{index}:
99	      Nat.show(index)
100	
101	def status_show(status: Status) -> String:
102	  match status:
103	    case Ok{}:
104	      "0"
105	    case Error{}:
106	      "1"
107	
108	def operation_show(operation: Operation) -> String:
109	  match operation:
110	    case Match{}:
111	      "0"
112	    case Insert{}:
113	      "1"
114	    case Delete{}:
115	      "2"
116	    case Mismatch{}:
117	      "3"
118	
119	def operation_char(format: CigarFormat, operation: Operation) -> Char:
120	  match format operation:
121	    case _ Insert{}:
122	      'I'
123	    case _ Delete{}:
124	      'D'
125	    case Standard{} _:
126	      'M'
127	    case Extended{} Match{}:
128	      '='
129	    case Extended{} Mismatch{}:
130	      'X'
131	
132	def cigar_run_step(runs: List<&2, CigarRun>, count: Nat, symbol: Char,
133	                   next: Char, same: Bool) -> List<&2, CigarRun>:
134	  match same:
135	    case True{}:
136	      CigarRun{1n+count, symbol} <> runs
137	    case False{}:
138	      CigarRun{1n, next} <> CigarRun{count, symbol} <> runs
139	
140	# The current run depends on the preceding symbol, so this scan is sequential.
141	# Tail recursion keeps long homogeneous and alternating paths bounded in stack.
142	def alignment_runs_reversed(operations: List<&2, Operation>, +format: CigarFormat,
143	                             runs: List<&2, CigarRun>) -> List<&2, CigarRun>:
144	  match operations runs:
145	    case Nil{} _:
146	      runs
147	    case h <> t Nil{}:
148	      alignment_runs_reversed(t, format, [CigarRun{1n, operation_char(format, h)}])
149	    case h <> t CigarRun{count, +symbol} <> tail:
150	      +next = operation_char(format, h)
151	      alignment_runs_reversed(t, format,
152	        cigar_run_step(tail, count, symbol, next, Char.is_eq(symbol, next)))
153	
154	def alignment_runs(operations: List<&2, Operation>, format: CigarFormat) -> List<&2, CigarRun>:
155	  List.reverse(&2, CigarRun, alignment_runs_reversed(operations, format, Nil{}))
156	
157	def cigar_runs_show(runs: List<&2, CigarRun>) -> String:
158	  match runs:
159	    case Nil{}:
160	      ""
161	    case CigarRun{count, symbol} <> tail:
162	      Nat.show(count) ++ SCon{symbol, cigar_runs_show(tail)}
163	
164	def alignment_to_cigar(operations: List<&2, Operation>, format: CigarFormat) -> String:
165	  cigar_runs_show(alignment_runs(operations, format))
166	
167	def coordinates_show(locations: List<&2, Coordinate>) -> String:
168	  List.show(~&2, ~Coordinate, ~coordinate_show, locations)
169	
170	def starts_show(locations: Maybe<&2, List<&2, Coordinate>>) -> String:
171	  match locations:
172	    case None{}:
173	      "null"
174	    case Some{values}:
175	      coordinates_show(values)
176	
177	def alignment_show(alignment: Maybe<&2, List<&2, Operation>>) -> String:
178	  match alignment:
179	    case None{}:
180	      "null"
181	    case Some{operations}:
182	      List.show(~&2, ~Operation, ~operation_show, operations)
183	
184	# CIGAR contains only decimal counts and MID=X, so needs no JSON escaping.
185	def cigar_show(cigar: Maybe<&2, String>) -> String:
186	  match cigar:
187	    case None{}:
188	      "null"
189	    case Some{value}:
190	      "\"" ++ value ++ "\""
191	
192	def result_show(result: AlignResult) -> String:
193	  match result:
194	    case AlignResult{status, distance, ends, starts, alignment, cigar}:
195	      "{\"status\":" ++ status_show(status) ++
196	      ",\"edit_distance\":" ++ distance_show(distance) ++
197	      ",\"end_locations\":" ++ coordinates_show(ends) ++
198	      ",\"start_locations\":" ++ starts_show(starts) ++
199	      ",\"alignment\":" ++ alignment_show(alignment) ++
200	      ",\"cigar\":" ++ cigar_show(cigar) ++ "}"
201	
202	def not_found() -> AlignResult:
203	  AlignResult{Ok{}, NotFound{}, Nil{}, None{}, None{}, None{}}
204	
205	def within_threshold(threshold: Threshold, distance: Nat) -> Bool:
206	  match threshold:
207	    case Unlimited{}:
208	      True{}
209	    case MaxDistance{maximum}:
210	      Nat.is_le(distance, maximum)
211	
212	def distance_result(distance: Nat, end: Coordinate, accepted: Bool) -> AlignResult:
213	  match accepted:
214	    case True{}:
215	      AlignResult{Ok{}, Found{distance}, [end], None{}, None{}, None{}}
216	    case False{}:
217	      not_found()