1	# Edits to texts, and places in them: the edits to make, spans that must not touch, and the lines and columns of
2	# offsets.
3	import Base
4	import bend-lint-api@0.2.2.0/shared/lists.bend as Lists
5	import bend-lint-api@0.2.2.0/shared/names.bend as Names
6	import bend-lint-api@0.2.2.0/shared/strings.bend as Strings
7	
8	# Edits
9	# =====
10	
11	# The text from `beg` to `end` in the file at `path`, replaced by `text`.
12	type Edit is Data:
13	  Edit{path: String, beg: U32, end: U32, text: String}
14	
15	def Edit.path(edit: Edit) -> String:
16	  match edit:
17	    case Edit{path, beg, end, text}:
18	      path
19	
20	def Edit.is_le(a: Edit, b: Edit) -> Bool:
21	  match a b:
22	    case Edit{p, x, e, t} Edit{q, y, f, u}:
23	      U32.is_le(x, y)
24	
25	# `rest`, the text from `at` on, with `edits` (in order) made, after the pieces of `out` (last first). The pieces join
26	# once, at the end, so the text is copied once, whatever the number of edits.
27	def apply.go(edits: List<&2, Edit>, +rest: String, +at: U32, out: List<&2, String>) -> String:
28	  match edits:
29	    case Nil{}:
30	      Strings.onto(rest <> out, "")
31	    case Con{Edit{p, beg, +end, text}, more}:
32	      apply.go(
33	        more,
34	        String.drop(rest, U32.to_nat((end - at: U32))),
35	        end,
36	        text <> Strings.take(rest, U32.to_nat((beg - at: U32))) <> out
37	      )
38	
39	# `text` with `edits` made. Edits must not overlap.
40	def apply(edits: List<&2, Edit>, text: String) -> String:
41	  apply.go(Lists.sort(~Edit, ~Edit.is_le, edits), text, 0, [])
42	
43	# Spans
44	# =====
45	
46	# Spans that never touch (`Spans.touches`), by place: a balanced (AVL) tree, by start, then end; `height` counts its
47	# levels. As spans never touch, their ends rise with their starts.
48	type Spans is Data:
49	  SLeaf{}
50	  SNode{height: U32, left: Spans, beg: U32, end: U32, right: Spans}
51	
52	def Spans.height(t: Spans) -> U32:
53	  match t:
54	    case SLeaf{}:
55	      0
56	    case SNode{h, l, b, e, r}:
57	      h
58	
59	# The node over `l` and `r`, whose heights differ by one at most.
60	def Spans.node(+l: Spans, b: U32, e: U32, +r: Spans) -> Spans:
61	  +hl = Spans.height(l)
62	  +hr = Spans.height(r)
63	  SNode{(Bool.pick(U32, U32.is_ge(hl, hr), hl, hr) + 1: U32), l, b, e, r}
64	
65	def Spans.lean_left.if(
66	  outer: Bool,
67	  ll: Spans,
68	  lb: U32,
69	  le: U32,
70	  lr: Spans,
71	  b: U32,
72	  e: U32,
73	  r: Spans
74	) -> Spans:
75	  match outer lr:
76	    case False{} SNode{h, lrl, lrb, lre, lrr}:
77	      Spans.node(Spans.node(ll, lb, le, lrl), lrb, lre, Spans.node(lrr, b, e, r))
78	    case _ _:
79	      Spans.node(ll, lb, le, Spans.node(lr, b, e, r))
80	
81	# The node over `l` and `r`, where `l` is two levels higher: turned right, after its left turns left if its inner side
82	# is the higher.
83	def Spans.lean_left(l: Spans, b: U32, e: U32, r: Spans) -> Spans:
84	  match l:
85	    case SNode{h, +ll, lb, le, +lr}:
86	      Spans.lean_left.if(U32.is_ge(Spans.height(ll), Spans.height(lr)), ll, lb, le, lr, b, e, r)
87	    case SLeaf{}:
88	      Spans.node(SLeaf{}, b, e, r)
89	
90	def Spans.lean_right.if(
91	  outer: Bool,
92	  l: Spans,
93	  b: U32,
94	  e: U32,
95	  rl: Spans,
96	  rb: U32,
97	  re: U32,
98	  rr: Spans
99	) -> Spans:
100	  match outer rl:
101	    case False{} SNode{h, rll, rlb, rle, rlr}:
102	      Spans.node(Spans.node(l, b, e, rll), rlb, rle, Spans.node(rlr, rb, re, rr))
103	    case _ _:
104	      Spans.node(Spans.node(l, b, e, rl), rb, re, rr)
105	
106	# The node over `l` and `r`, where `r` is two levels higher: the mirror of `lean_left`.
107	def Spans.lean_right(l: Spans, b: U32, e: U32, r: Spans) -> Spans:
108	  match r:
109	    case SNode{h, +rl, rb, re, +rr}:
110	      Spans.lean_right.if(U32.is_ge(Spans.height(rr), Spans.height(rl)), l, b, e, rl, rb, re, rr)
111	    case SLeaf{}:
112	      Spans.node(l, b, e, SLeaf{})
113	
114	def Spans.balance.if(left: Bool, right: Bool, l: Spans, b: U32, e: U32, r: Spans) -> Spans:
115	  match left right:
116	    case True{} _:
117	      Spans.lean_left(l, b, e, r)
118	    case _ True{}:
119	      Spans.lean_right(l, b, e, r)
120	    case _ _:
121	      Spans.node(l, b, e, r)
122	
123	# The node over `l` and `r`, balanced: their heights may differ by two.
124	def Spans.balance(+l: Spans, b: U32, e: U32, +r: Spans) -> Spans:
125	  +hl = Spans.height(l)
126	  +hr = Spans.height(r)
127	  Spans.balance.if(U32.is_gt(hl, (hr + 1: U32)), U32.is_gt(hr, (hl + 1: U32)), l, b, e, r)
128	
129	def Spans.cmp.of(starts: Cmp, e: U32, y: U32) -> Cmp:
130	  match starts:
131	    case EQ{}:
132	      U32.cmp(e, y)
133	    case LT{}:
134	      LT{}
135	    case GT{}:
136	      GT{}
137	
138	# How the span from `b` to `e` compares with the root's of `t`, by start, then end; GT past a leaf.
139	def Spans.cmp(t: Spans, b: U32, e: U32) -> Cmp:
140	  match t:
141	    case SNode{h, l, x, y, r}:
142	      Spans.cmp.of(U32.cmp(b, x), e, y)
143	    case SLeaf{}:
144	      GT{}
145	
146	# `t` with the span from `b` to `e`; `side` is how it compares with the root's.
147	def Spans.add(t: Spans, +b: U32, +e: U32, side: Cmp) -> Spans:
148	  match t side:
149	    case SLeaf{} _:
150	      SNode{1, SLeaf{}, b, e, SLeaf{}}
151	    case SNode{h, +l, x, y, r} LT{}:
152	      Spans.balance(Spans.add(l, b, e, Spans.cmp(l, b, e)), x, y, r)
153	    case SNode{h, l, x, y, +r} _:
154	      Spans.balance(l, x, y, Spans.add(r, b, e, Spans.cmp(r, b, e)))
155	
156	# Whether `t` holds the span from `b` to `e`; `side` is how it compares with the root's.
157	def Spans.has(t: Spans, +b: U32, +e: U32, side: Cmp) -> Bool:
158	  match t side:
159	    case SLeaf{} _:
160	      False{}
161	    case SNode{h, l, x, y, r} EQ{}:
162	      True{}
163	    case SNode{h, +l, x, y, r} LT{}:
164	      Spans.has(l, b, e, Spans.cmp(l, b, e))
165	    case SNode{h, l, x, y, +r} GT{}:
166	      Spans.has(r, b, e, Spans.cmp(r, b, e))
167	
168	def Spans.starts_before(t: Spans, e: U32) -> Bool:
169	  match t:
170	    case SNode{h, l, x, y, r}:
171	      U32.is_lt(x, e)
172	    case SLeaf{}:
173	      False{}
174	
175	# The end of the last span of `t` (by start, then end) that starts before `e`, or `found`. `before` says whether the
176	# root's does. Its end is the furthest of theirs, as ends rise with starts.
177	def Spans.last(t: Spans, +e: U32, found: Maybe<&2, U32>, before: Bool) -> Maybe<&2, U32>:
178	  match t before:
179	    case SLeaf{} _:
180	      found
181	    case SNode{h, l, x, y, +r} True{}:
182	      Spans.last(r, e, Some{y}, Spans.starts_before(r, e))
183	    case SNode{h, +l, x, y, r} False{}:
184	      Spans.last(l, e, found, Spans.starts_before(l, e))
185	
186	def Spans.ends_after(last: Maybe<&2, U32>, b: U32) -> Bool:
187	  match last:
188	    case Some{y}:
189	      U32.is_lt(b, y)
190	    case None{}:
191	      False{}
192	
193	# Whether the span from `b` to `e` touches one of `t`: they share a character, or two insertions are at one place.
194	def Spans.touches.insertion(insertion: Bool, +t: Spans, +b: U32, +e: U32) -> Bool:
195	  match insertion:
196	    case True{}:
197	      Spans.has(t, b, e, Spans.cmp(t, b, e))
198	    case False{}:
199	      False{}
200	
201	def Spans.touches.of(shares: Bool, t: Spans, +b: U32, +e: U32) -> Bool:
202	  match shares:
203	    case True{}:
204	      True{}
205	    case False{}:
206	      Spans.touches.insertion(U32.is_eq(b, e), t, b, e)
207	
208	def Spans.touches(+t: Spans, +b: U32, +e: U32) -> Bool:
209	  Spans.touches.of(
210	    Spans.ends_after(Spans.last(t, e, None{}, Spans.starts_before(t, e)), b),
211	    t,
212	    b,
213	    e
214	  )
215	
216	# Places
217	# ======
218	
219	# A place in a text: its line and its column, from 1. A column counts UTF-16 units, as editors do.
220	type Position is Data:
221	  Position{line: U32, column: U32}
222	
223	# An offset in the file at `path`.
224	type Place is Data:
225	  Place{path: String, offset: U32}
226	
227	# An offset to place, by its place among the offsets asked; and a place found, by the same.
228	type Placed is Data:
229	  Placed{index: U32, offset: U32}
230	
231	type Located is Data:
232	  Located{index: U32, at: Position}
233	
234	# The offsets left to place, in offset order, and the places found, last first.
235	type Walk is Data:
236	  Walk{pending: List<&2, Placed>, out: List<&2, Located>}
237	
238	def Placed.is_le(a: Placed, b: Placed) -> Bool:
239	  match a b:
240	    case Placed{i, x} Placed{j, y}:
241	      U32.is_le(x, y)
242	
243	def Located.is_le(a: Located, b: Located) -> Bool:
244	  match a b:
245	    case Located{i, x} Located{j, y}:
246	      U32.is_le(i, j)
247	
248	def Placed.of(offsets: List<&2, U32>, +index: U32, out: List<&2, Placed>) -> List<&2, Placed>:
249	  match offsets:
250	    case Nil{}:
251	      out
252	    case Con{o, rest}:
253	      Placed.of(rest, (index + 1: U32), Placed{index, o} <> out)
254	
255	def Walk.is_due(pending: List<&2, Placed>, at: U32) -> Bool:
256	  match pending:
257	    case Con{Placed{i, offset}, rest}:
258	      U32.is_le(offset, at)
259	    case Nil{}:
260	      False{}
261	
262	# The offsets due at `at`, placed at `line` and `column`.
263	def Walk.emit(
264	  pending: List<&2, Placed>,
265	  due: Bool,
266	  +at: U32,
267	  +line: U32,
268	  +column: U32,
269	  out: List<&2, Located>
270	) -> Walk:
271	  match pending due:
272	    case Con{Placed{i, offset}, +rest} True{}:
273	      Walk.emit(
274	        rest,
275	        Walk.is_due(rest, at),
276	        at,
277	        line,
278	        column,
279	        Located{i, Position{line, column}} <> out
280	      )
281	    case _ _:
282	      Walk{pending, out}
283	
284	def Walk.done(w: Walk) -> List<&2, Located>:
285	  match w:
286	    case Walk{pending, out}:
287	      out
288	
289	# The offsets placed, one character of `text` at a time; offsets past its end are placed at its end.
290	def Walk.go(text: String, +at: U32, +line: U32, column: U32, w: Walk) -> List<&2, Located>:
291	  match text w:
292	    case _ Walk{Nil{}, out}:
293	      out
294	    case SNil{} Walk{pending, out}:
295	      Walk.done(Walk.emit(pending, True{}, 4294967295, line, column, out))
296	    case SCon{+c, t} Walk{+pending, out}:
297	      +ends = Char.is_eq(c, '\n')
298	      +l = Bool.pick(U32, ends, (line + 1: U32), line)
299	      +col = Bool.pick(
300	        U32,
301	        ends,
302	        1,
303	        (column + Bool.pick(U32, U32.is_ge(Char.to_u32(c), 65536), 2, 1): U32)
304	      )
305	      Walk.go(
306	        t,
307	        (at + 1: U32),
308	        l,
309	        col,
310	        Walk.emit(pending, Walk.is_due(pending, (at + 1: U32)), (at + 1: U32), l, col, out)
311	      )
312	
313	def Walk.positions(located: List<&2, Located>, out: List<&2, Position>) -> List<&2, Position>:
314	  match located:
315	    case Nil{}:
316	      List.reverse(&2, Position, out)
317	    case Con{Located{i, at}, rest}:
318	      Walk.positions(rest, at <> out)
319	
320	# The offsets of `sorted` (in offset order) placed in `text`, in no order.
321	def Walk.locate(+sorted: List<&2, Placed>, text: String) -> List<&2, Located>:
322	  Walk.go(text, 0, 1, 1, Walk.emit(sorted, Walk.is_due(sorted, 0), 0, 1, 1, []))
323	
324	# Where each offset of `offsets` is in `text`, in order: one pass over the text, whatever the number of offsets.
325	def positions(text: String, offsets: List<&2, U32>) -> List<&2, Position>:
326	  Walk.positions(
327	    Lists.sort(
328	      ~Located,
329	      ~Located.is_le,
330	      Walk.locate(Lists.sort(~Placed, ~Placed.is_le, Placed.of(offsets, 0, [])), text)
331	    ),
332	    []
333	  )
334	
335	def Place.key(path: String, offset: U32) -> String:
336	  path ++ "\t" ++ U32.show(offset)
337	
338	# Where the offset `offset` of the file at `path` is, among `places` (what `places` gives); 1:1 if it is not there.
339	def Place.at(places: Map<&2, Position>, path: String, offset: U32) -> Position:
340	  Pair.snd(
341	    Map<&2, Position>,
342	    Position,
343	    Map.get(Position, Position{1, 1}, places, Place.key(path, offset))
344	  )
345	
346	# The requests by file, each offset numbered by itself, onto `groups`.
347	def places.group(
348	  requests: List<&2, Place>,
349	  groups: Map<&2, List<&2, Placed>>
350	) -> Map<&2, List<&2, Placed>>:
351	  match requests:
352	    case Nil{}:
353	      groups
354	    case Con{Place{path, +offset}, rest}:
355	      places.group(rest, Names.Group.add(Placed, groups, path, Placed{offset, offset}))
356	
357	# The places found in the file at `path`, by key, onto `out`.
358	def places.keep(
359	  located: List<&2, Located>,
360	  +path: String,
361	  out: Map<&2, Position>
362	) -> Map<&2, Position>:
363	  match located:
364	    case Nil{}:
365	      out
366	    case Con{Located{offset, at}, rest}:
367	      places.keep(rest, path, Map.set(&2, Position, out, Place.key(path, offset), at))
368	
369	# The requests of each file of `paths` placed in its text, onto `out`; a file `texts` lacks places them at its start.
370	def places.walk(
371	  paths: List<&2, String>,
372	  +groups: Map<&2, List<&2, Placed>>,
373	  +texts: Map<&2, String>,
374	  out: Map<&2, Position>
375	) -> Map<&2, Position>:
376	  match paths:
377	    case Nil{}:
378	      out
379	    case Con{+path, rest}:
380	      places.walk(
381	        rest,
382	        groups,
383	        texts,
384	        places.keep(
385	          Walk.locate(
386	            Lists.sort(~Placed, ~Placed.is_le, Names.Group.get(Placed, groups, path)),
387	            Pair.snd(Map<&2, String>, String, Map.get(String, "", texts, path))
388	          ),
389	          path,
390	          out
391	        )
392	      )
393	
394	# Where each requested offset is, by key (read with `Place.at`): one pass over each file asked about, whatever the
395	# number of requests. `texts` holds the files' texts, by path.
396	def places(texts: Map<&2, String>, requests: List<&2, Place>) -> Map<&2, Position>:
397	  +groups = places.group(requests, Map.new(&2, List<&2, Placed>))
398	  places.walk(Map.keys(&2, List<&2, Placed>, groups), groups, texts, Map.new(&2, Position))