Functional Weave
Code in Rust

text.pattern-match@1.0.0

README.md

4,337 bytes · view raw

# text.pattern-match

`matchesPattern(pattern, value)` answers what an input's `pattern` attribute
answers in the browser: does the **whole** value match? The browser compiles
`pattern` as `^(?:pattern)$` with the `v` flag; this does the same, in
TypeScript, Python and Rust, so a server checks a submitted form with exactly
the rule the browser showed. `form.validate-input` uses it for its `pattern`
rule.

```ts
matchesPattern("[0-9]{5}", "90210");      // true
matchesPattern("[0-9]{5}", "90210\n");    // false: no trailing-newline slack
matchesPattern("(?=.*\\d).{8,}", "x");    // throws "unsupported pattern: ..."
```

## Why not the language's own regex

The three engines disagree. Python's `$` matches before a trailing newline,
its `\d` and `\w` are Unicode (`"٣"` is a digit), and `re` has no `v` flag;
Rust's standard library has no regex at all (and a crate is not allowed);
JavaScript's `\s` takes Unicode spaces. A pattern checked by three engines is
three rules. This is one small engine written three times, pinned by the same
vectors, and checked against the browser's own `RegExp(…, "v")` by a
differential fuzz while it was written (no disagreement on any pattern both
accept).

## The supported subset

| Syntax | Meaning |
|--------|---------|
| `a`, `é`, `😀` | that code point |
| `.` | any code point but a line terminator (`\n`, `\r`, U+2028, U+2029) |
| `\d` `\D` | ASCII digit `[0-9]`, and not |
| `\w` `\W` | ASCII word character `[A-Za-z0-9_]`, and not |
| `\s` `\S` | ASCII whitespace (space, `\t`, `\n`, `\v`, `\f`, `\r`), and not |
| `\t` `\n` `\v` `\f` `\r` | those control characters |
| `\.` `\*` `\(` … | an escaped syntax character `^ $ \ . * + ? ( ) [ ] { } \| /` |
| `[abc]` `[a-z]` `[^0-9]` | a class, with ranges, negation and the escapes above; inside a class `\-` `\&` `\!` `\#` `\%` `\,` `\:` `\;` `\<` `\=` `\>` `\@` `` \` `` `\~` are literals too |
| `(…)` `(?:…)` | a group (nothing is captured: whole-string matching has no use for it) |
| `a\|b` | alternation |
| `*` `+` `?` `{n}` `{n,}` `{n,m}` | repeats, with a lazy `?` suffix accepted (it cannot change a whole-string answer) |
| `^` first, `$` last | allowed and ignored: the match is always of the whole value |

Everything is over Unicode code points, as the `v` flag is. There is no
ignore-case: list both cases (`[A-Za-z]`).

## What is refused, and why

`matchesPattern` throws `unsupported pattern: <what>` (the same phrase in
every language) for:

- lookahead and lookbehind (`(?=` `(?!` `(?<=` `(?<!`), named groups,
  inline flags: they cannot be run in linear time, or are rarely used in a
  pattern attribute;
- backreferences (`\1`, `\k<…>`), `\b` and `\B`, `\p{…}`, `\u…`, `\x…`,
  `\c…`, `\0`, and any other escaped letter or punctuation the `v` flag
  rejects;
- `^` or `$` anywhere but the very start and end of the pattern;
- an unbalanced `(`, `)`, `[`, a lone `]`, `{` or `}`;
- the `v` flag's own class rules: an unescaped `( ) [ ] { } / - \ |` inside
  `[…]` (so `[A-Za-z-]` must be written `[A-Za-z\-]`; the browser ignores the
  former pattern entirely), and doubled punctuators such as `&&`;
- a range written backwards (`[z-a]`) or with a class at either end (`[\d-z]`);
- a quantifier with nothing before it, or straight after another (`a**`);
- `{n,m}` with n above m, or a count above 1000;
- a pattern that would compile to more than 20,000 steps (nested counted
  repeats such as `(a{1000}){1000}`).

A pattern over 1000 code points throws `pattern is too long`.

A refused pattern is a programming error, not a user's typing error: it is
thrown whatever the value, so it fails the first test that uses it.

## Linear time

The pattern compiles to a program run as a Thompson NFA (a Pike VM without
captures): each character of the value is looked at once against each
program step, so `(a+)+b` against 10,000 `a`s answers at once. A backtracking
engine takes exponential time on it, which is how a pattern on a public form
becomes a denial of service on the server that re-checks it.

## Differences from the browser

Only where the browser's own rules are wider than the subset: `\s` here is
ASCII whitespace, where JavaScript's also takes no-break and other Unicode
spaces. Every pattern the subset accepts is one the browser accepts, and on
the values tested they agree.