# `Feel.Runtime.Regex`
[🔗](https://github.com/FeeJai/BDM/blob/feel-v0.1.0/apps/feel/lib/feel/runtime/regex.ex#L1)

The regular expressions of `matches`, `replace` and `split` (DMN 1.6, section 10.3.4.3, footnote 2 of
Table 75; D-80, was D-80).

The specification says that `pattern`, `replacement` and `flags` conform to clause 7.6 of XQuery 1.0 and
XPath 2.0 Functions and Operators, and that where XPath gives an error FEEL gives `null`. That dialect is
the regular expressions of XML Schema (appendix F of XSD part 2) with a few additions, and it is not the
one of Erlang (PCRE): `\s` is four characters and not the Unicode spaces, `.` leaves out the carriage
return, `$` is only the end of the string, there are character classes with a subtraction
(`[A-Z-[OI]]`) and blocks (`\p{IsBasicLatin}`), and there is no look-around, no `\b`, no inline flags and
no possessive quantifier. So a pattern is **read here**, strictly, in the dialect of XPath, and written
as a PCRE pattern that means the same; a pattern that is not in the dialect is `:error`, and the function
is `null`. Nothing of the pattern reaches the engine as it was written.

## The dialect

  * **Atoms.** A character (not one of `. \ ? * + { } ( ) | [ ] ^ $`), `.` (any character but a line feed
    or a carriage return, or any with the flag `s`), an escape, a class, or a group. The escapes are
    `\n \r \t`, a character that is special (`\\ \| \. \- \^ \? \* \+ \{ \} \( \) \[ \]`), `\s \S \d \D \w \W`
    (as XML Schema has them: `\s` is a space, a tab, a line feed or a carriage return), `\i \I \c \C` (the
    characters of XML names), `\p{..}` and `\P{..}` (a category such as `L` or `Nd`, or a block such as
    `IsBasicLatin`), and `\1` to `\9`, which is the text of a group that has been closed.
  * **Classes.** `[a-z0-9_]`, `[^...]`, and `[base-[subtracted]]`, the characters of the first that are not
    in the second. A `-` that is not the dash of a range or of a subtraction is a character only first in
    the class or last; anywhere else it has to be escaped (`[a-c-e]` is an error, as XML Schema has it).
  * **Groups.** `( )` captures and `(?: )` does not. Any other `(?` is an error.
  * **Quantifiers.** `? * + {n} {n,} {n,m}`, each with an optional `?` after it for the shortest match.
  * **Anchors.** `^` and `$` are the start and the end of the string; with the flag `m`, the start and the
    end of a line (a line ends at a line feed).
  * **Flags.** `s` (a dot is any character), `m`, `i` (a letter is its other case too, for the whole of
    Unicode: the Kelvin sign is a `k`) and `x` (the white space of the pattern is taken out first, but for
    what is in a class). Another character is an error.

A range whose end is before its start, a quantifier that has nothing to repeat, a back-reference to a
group that is not closed, an unbalanced bracket or parenthesis, an escape that is none of the above, and a
block that is not listed (the names of `blocks/0`, which are most of the scripts) are errors.

## What is done with a pattern

`compile/2` reads it. `matches?/3` is true if some part of the input matches (the pattern is not anchored).
`replace/4` replaces every match, left to right, the replacement having `$0`, `$1`, ... for the text of a
group (empty if the group did not take part or does not exist; the number takes as many digits as there are
groups to hold it), `\$` for a dollar and `\\` for a backslash, and any other `$` or `\` an error. `split/3` cuts
the input at every match, and keeps the empty parts, those at the end included. `replace` and `split` need a
pattern that does not match the empty string (`a*` does), which is an error as in XPath. The input is data and
not a pattern.

The engine is told how long it may look (`regex_match_limit` of `Feel.Limits`); a match that takes more is
`{:error, :limit}`. It has to be asked to say so (`:report_errors`): otherwise the engine answers that
there is no match, which is a wrong answer and not an end of the run.

## The size of the result

`replace/5`, `split/4` and `scan/4` take the most that their result may have (bytes for `replace/5`, items for the
others) and answer `{:error, {:over, size}}` where it would be more, with the count at which it passed. The walk over the
matches adds up what the result is as it goes and ends at the first match that makes it too long, and nothing is built
that is not within the cap: a replacement of 100 KB for each of a million matches is 100 GB, and the limit of a finished
string would look at it after it was made.

**A pattern that is only text** (`,`, `ab`, `é`: no character of the syntax, and no flag `i` or `x`) is searched for one
match at a time with `:binary.match/3`, so the walk costs what it walks: a megabyte of `a` split by `a` ends at the
100,001st part, in 26 ms and a few megabytes, where the engine took 600 ms and 380 MB for the million.

**Any other pattern** is run by the engine one match at a time too, so the walk costs what it walks (D-215): the
engine is asked for the first match from a byte offset of the whole text (the text is not cut, so `^`, `$` and the
characters before the offset mean what they mean in the whole), and for the next from where that one ended, with an
empty match stepped over as the engine's own `:global` run steps over it. The public `:re.run/3` cannot do this
cheaply: a run for each match checks the whole text for UTF-8 again every time (80 KB took 3.5 s, and 1 MB does not
end). The function `internal_run` of `:re` (four arguments) is what the engine's own loop calls for each match after
the first, and its last argument says that the text has been checked; the first call checks it, as a `:global` run
does, and a text that is not UTF-8 raises as before. That function is not documented, and the loop that steps over an
empty match is that of OTP 28 and later, so where a version of OTP does not have the function, or is before 28, the
matches are listed whole as before (about 360 bytes of heap for a match, 360 MB for a megabyte of `a` and the pattern
`[a]`), and the cap and the engine's limit are crossed in the list, not on the walk.

# `t`

```elixir
@type t() :: %Feel.Runtime.Regex{
  groups: non_neg_integer(),
  literal: String.t() | nil,
  program: :re.mp()
}
```

A pattern that is read: the program of the engine, the number of groups, and the text it is when it is only that text
(`nil` if it is more).

# `blocks`

```elixir
@spec blocks() :: [String.t()]
```

The names of the blocks that a pattern may use after `Is`, sorted.

# `compile`

```elixir
@spec compile(String.t(), String.t() | nil) :: {:ok, t()} | :error
```

Reads a pattern and its flags (`nil` for none), or says that they are not in the dialect.

    iex> {:ok, regex} = Feel.Runtime.Regex.compile("a(b)c", nil)
    iex> regex.groups
    1
    iex> Feel.Runtime.Regex.compile("a(", nil)
    :error
    iex> Feel.Runtime.Regex.compile("a", "q")
    :error

# `matches?`

```elixir
@spec matches?(t(), String.t(), non_neg_integer() | :infinity) ::
  {:ok, boolean()} | {:error, :limit}
```

Whether some part of the input matches. `{:error, :limit}` if the engine gave up (`limit` is the
`regex_match_limit` of the run).

    iex> {:ok, regex} = Feel.Runtime.Regex.compile("^fo*b", nil)
    iex> Feel.Runtime.Regex.matches?(regex, "foobar", :infinity)
    {:ok, true}
    iex> Feel.Runtime.Regex.matches?(regex, "a foobar", :infinity)
    {:ok, false}

# `matches_empty?`

```elixir
@spec matches_empty?(t()) :: boolean()
```

Whether the pattern matches the empty string, which `replace` and `split` do not allow.

    iex> {:ok, regex} = Feel.Runtime.Regex.compile("a*", nil)
    iex> Feel.Runtime.Regex.matches_empty?(regex)
    true

# `replace`

```elixir
@spec replace(
  t(),
  String.t(),
  String.t(),
  non_neg_integer() | :infinity,
  non_neg_integer() | :infinity
) ::
  {:ok, String.t()}
  | :error
  | {:error, :limit}
  | {:error, {:over, pos_integer()}}
```

Replaces every match with the replacement, or `:error` if the replacement is not in the dialect (a `$`
not followed by a digit, a `\\` not followed by a `$` or a `\\`) or the pattern matches the empty string.

`max` is the most bytes the text may have (`:infinity` for no cap): a result that would be longer is
`{:error, {:over, size}}`, where `size` is the count of bytes when it passed `max`, and is not made.

    iex> {:ok, regex} = Feel.Runtime.Regex.compile("(ab)|(a)", nil)
    iex> Feel.Runtime.Regex.replace(regex, "abcd", "[1=$1][2=$2]", :infinity)
    {:ok, "[1=ab][2=]cd"}
    iex> Feel.Runtime.Regex.replace(regex, "abcd", "$", :infinity)
    :error
    iex> Feel.Runtime.Regex.replace(regex, "abcd", "xyz", :infinity, 4)
    {:error, {:over, 5}}

# `scan`

```elixir
@spec scan(
  t(),
  String.t(),
  non_neg_integer() | :infinity,
  non_neg_integer() | :infinity
) ::
  {:ok, [String.t()]}
  | :error
  | {:error, :limit}
  | {:error, {:over, pos_integer()}}
```

The text of every match, left to right: none is `{:ok, []}`. A pattern that matches the empty string is `:error`, as
for `replace/5` and `split/4`: it would match everywhere.

`max` is the most matches there may be (`:infinity` for no cap): more are `{:error, {:over, count}}`, and are not made.

    iex> {:ok, regex} = Feel.Runtime.Regex.compile("12[0-9]*", nil)
    iex> Feel.Runtime.Regex.scan(regex, "references are 1234, 1256, 1378", :infinity)
    {:ok, ["1234", "1256"]}
    iex> Feel.Runtime.Regex.scan(regex, "nothing", :infinity)
    {:ok, []}
    iex> Feel.Runtime.Regex.scan(regex, "references are 1234, 1256, 1378", :infinity, 1)
    {:error, {:over, 2}}
    iex> {:ok, empty} = Feel.Runtime.Regex.compile("a*", nil)
    iex> Feel.Runtime.Regex.scan(empty, "baaa", :infinity)
    :error

# `split`

```elixir
@spec split(
  t(),
  String.t(),
  non_neg_integer() | :infinity,
  non_neg_integer() | :infinity
) ::
  {:ok, [String.t()]}
  | :error
  | {:error, :limit}
  | {:error, {:over, pos_integer()}}
```

Cuts the input at every match, keeping the empty parts. The empty string is no parts.

`max` is the most parts there may be (`:infinity` for no cap): more are `{:error, {:over, count}}`, and are not made.

    iex> {:ok, regex} = Feel.Runtime.Regex.compile(";", nil)
    iex> Feel.Runtime.Regex.split(regex, "a;b;c;;", :infinity)
    {:ok, ["a", "b", "c", "", ""]}
    iex> Feel.Runtime.Regex.split(regex, "", :infinity)
    {:ok, []}
    iex> Feel.Runtime.Regex.split(regex, "a;b;c;;", :infinity, 4)
    {:error, {:over, 5}}

---

*Consult [api-reference.md](api-reference.md) for complete listing*