okami.mom/albedo

git clone https://git.nkp.pet/okami.mom/albedo

Aly Raffaufrefactor(gleam): clean up code and enforce focused lint checksb585313

main
branchesmainall refs →
2.0 KiB64 linesraw
1//// The wildcard retry algorithm must agree with exhaustive small-pattern
2//// matching, including overlapping wildcard retries. HTTP E2E cannot cover
3//// this combinatorial space or reliably catch exponential work regressions.
4
5import albedo/harness/cache_ttl
6import gleam/list
7import gleam/string
8import gleeunit/should
9
10fn words(alphabet: List(String), length: Int) -> List(String) {
11  case length {
12    0 -> [""]
13    _ -> {
14      let shorter = words(alphabet, length - 1)
15      list.append(
16        [""],
17        list.flat_map(alphabet, fn(head) {
18          list.map(shorter, fn(tail) { head <> tail })
19        }),
20      )
21    }
22  }
23}
24
25// An intentionally exhaustive oracle for bounded inputs; the production
26// matcher must not explore both branches recursively on long inputs.
27fn exhaustive(pattern: List(String), value: List(String)) -> Bool {
28  case pattern, value {
29    [], [] -> True
30    ["*", ..rest], _ ->
31      exhaustive(rest, value)
32      || case value {
33        [_, ..tail] -> exhaustive(pattern, tail)
34        [] -> False
35      }
36    [head, ..rest], [letter, ..tail] -> head == letter && exhaustive(rest, tail)
37    _, _ -> False
38  }
39}
40
41pub fn wildcard_retry_agrees_with_exhaustive_matching_test() -> Nil {
42  list.each(words(["a", "b", "*"], 5), fn(pattern) {
43    list.each(words(["a", "b"], 4), fn(value) {
44      cache_ttl.matches_glob(pattern, value)
45      |> should.equal(exhaustive(
46        string.to_graphemes(pattern),
47        string.to_graphemes(value),
48      ))
49    })
50  })
51}
52
53pub fn repeated_wildcards_fail_without_exponential_backtracking_test() -> Nil {
54  let pattern = string.repeat("*a", 24) <> "b"
55  cache_ttl.matches_glob(pattern, string.repeat("a", 48))
56  |> should.be_false
57}
58
59pub fn wildcard_matches_unicode_graphemes_and_only_star_is_special_test() -> Nil {
60  cache_ttl.matches_glob("É*👩‍💻?", "éclair👩‍💻?") |> should.be_true
61  cache_ttl.matches_glob("é*", "éclair") |> should.be_true
62  cache_ttl.matches_glob("a?", "ab") |> should.be_false
63  cache_ttl.matches_glob("[ab]", "a") |> should.be_false
64}