moonbitlang / core / 6093
91%

DEFAULT BRANCH: main
Ran
Jobs 1
Files 437
Run time 1min
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
coverage: 90.72%. Remained the same
6093

push

github

bobzhang 
test(internal/edit_distance): specify Levenshtein against the textbook DP

The package had no test file at all -- only the doc examples.

The definition of Levenshtein distance is a three-line dynamic program,
and the oracle here is exactly that: the full (m+1) x (n+1) table, no
trimming, no banding, no saturation. The implementation is none of
those things. It trims the common prefix and suffix, rolls two rows
instead of the table, swaps its arguments so the longer side comes
first, and for the `*_within` entry points restricts the search to a
diagonal band with Ukkonen bail-out and saturating arithmetic. Each of
those is a chance to be wrong on a particular shape of input, so the
suite checks the optimized code against the definition rather than
against itself.

Two things drive that comparison. Exhaustive sweeps settle whole input
spaces outright -- every ordered pair of binary words up to length 6
(16129 pairs) and of ternary words up to length 4, each checked at
*every* distance bound from -1 to one past the maximum, from both
argument orders. That is the only way to be confident no band-edge case
was missed, since the `lo`/`hi` clamping and the row sealing are where
an off-by-one would hide. Property tests then carry the same checks to
longer inputs.

Alongside those sit the axioms that hold independently of the
algorithm: Levenshtein is a metric, so it is zero exactly on equal
inputs, symmetric, and obeys the triangle inequality; it is bounded
below by the length difference and above by the longer length; a single
insertion, deletion or substitution costs exactly one; and it is
invariant under a shared prefix and suffix, which is precisely the
assumption the trimming step rests on. Finally, `edit_distance_str` is
pinned as the array API over `code_units()`, with the documented
astral-character behaviour as explicit cases.

Generators project onto a small alphabet on purpose: over unrestricted
Ints two random sequences almost never share an elem... (continued)

16012 of 17650 relevant lines covered (90.72%)

164436.02 hits per line

Jobs
ID Job ID Ran Files Coverage
1 6093.1 438
90.73
 GitHub Action Run
Source Files on build 6093