Bijective Regex

[p-avital]

Introduction

We've been pining for more precise wilds than * for quite some time. With the new key expression language, we can now introduce DSLs to do just that.

[p-avital]

Idea 1: BIRDs

This proposal seeks to define the BIjective Regex DSL (BIRD): a regex-like language that is bijective, allowing us to keep the unicity property of the KE language.

Syntax

KE integration

BIRD may be integrated into KEs to match exactly one chunk by surrounding them with $[...]. It may not be integrated as a subchunk (i.e. it can only be surrounded by /s).

Why couldn't BIRD match multiple chunks?

In theory, it could, but I suspect the cost of being able to do so would be too great. We can expand its functionality later if we want to, but be prepared for heavy canonization interactions.

Why couldn't BIRD be a subchunk?

Mostly because this would impact canonization greatly, as $[hello-.*-there-\d*] would have to become hello-$*-there-$[\d*].
By making BIRD work as a single chunk, as long as we detect cases where it could've been written exclusively with the currently available syntax, we can guarantee unicity.

Special characters

/?# are forbidden within BIRDs.

(){}[]|\*. are the syntactic characters. Any other character is classified as "normal".

Normal characters

They are always matched literally. A syntactic character may be literally matched by prefixing it with \.

Ranges

Ranges are written as a sorted list of inclusive intervals between UTF codepoints. None of these intervals can intersect, nor be joined into a larger interval. Intervals matching a single character may exist, as long as other intervals are included in the range.

Character classes

The following character classes are defined:

• \d for decimal digits. [09] must be replaced by this.
• \h for hexadecimal digits (case-insensitive?). [09AFaf] must be replaced by this.
• No range is defined for base64, as standard base64 encoding uses /.
• . for any character (except /).

Quantifiers

Quantifiers allow repeating a quantifiable pattern µ:

• µ*: 0 or more.
• µ{n}: exactly n repetitions.
• µ{a,}: at least a repetitions, a=0 is forbidden.
• µ{a,b}: between a and b (inclusive) repetitions, a>=b is forbidden.
  µ can never follow µ, µ* or µ{...}: repetitions of quantifiables must always be expressed through quantifiers.

Only ranges are quantifiables. Literal matches are not quantifiable, letting words be matched literally without needing to convert repeating letters to quantifiers-syntax.

Comments

Why can't BIRD have capture groups?

Because capture groups would have to be expressed in the language, but wouldn't change the set of keys defined, breaking the bijectivity.

Why can't BIRD have alternatives?

Because they create many ways to break bijectivity, some of which are very tricky to detect.

On top of that, alternatives may be better as their own DSL, exposing easier semantics for infrastructures to optimise upon. This could be done as the ADSL: $(...|...) where each variant is a chunk.

[p-avital]

Idea 2: Alternatives DSL (ADSL) + Range DSL (RDSL)

This idea needs further study before being turned into a proposal for this discussion.