lib/text/main.bend

bend-lint-rules@0.2.0.0 · 398 lines · 45 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.0.0/shared/lists.bend as Lists
5import bend-lint-api@0.2.0.0/shared/names.bend as Names
6import bend-lint-api@0.2.0.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))