lib/text/main.bend
bend-lint-rules@0.2.1.0 · 398 lines · 0 definitions
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.
3import Base
4import bend-lint-api@0.2.1.0/shared/lists.bend as Lists
5import bend-lint-api@0.2.1.0/shared/names.bend as Names
6import bend-lint-api@0.2.1.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`.
12type Edit is Data:
13 Edit{path: String, beg: U32, end: U32, text: String}
14
15def Edit.path(edit: Edit) -> String:
16 match edit:
17 case Edit{path, beg, end, text}:
18 path
19
20def 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.
27def 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.
40def 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.
48type Spans is Data:
49 SLeaf{}
50 SNode{height: U32, left: Spans, beg: U32, end: U32, right: Spans}
51
52def 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.
60def 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
65def 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.
83def 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
90def 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`.
107def 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
114def 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.
124def 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
129def 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.
139def 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.
147def 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.
157def 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
168def 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.
177def 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
186def 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.
194def 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
201def 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
208def 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.
220type Position is Data:
221 Position{line: U32, column: U32}
222
223# An offset in the file at `path`.
224type 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.
228type Placed is Data:
229 Placed{index: U32, offset: U32}
230
231type 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.
235type Walk is Data:
236 Walk{pending: List<&2, Placed>, out: List<&2, Located>}
237
238def 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
243def 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
248def 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
255def 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`.
263def 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
284def 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.
290def 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
313def 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.
321def 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.
325def 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
335def 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.
339def 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`.
347def 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`.
358def 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.
370def 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.
396def 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))