Subject: [openpgp] Possible ambiguity in description of regular expressions: [^][]

From: "Neal H. Walfield" <[email-masked]>
Date: Wed, 23 Dec 2020 22:58:37 +0100

The description of regular expressions in Section 8 of 4880
(https://tools.ietf.org/html/rfc4880#section-8) says:

  A range is a sequence of characters enclosed in '[]'.  It normally
  matches any single character from the sequence.

Is an empty sequence allowed?  If so,

  []                  (1)

is a valid regular expression meaning *no match*.

  If the sequence begins with '^', it matches any single character not
  from the rest of the sequence.

Even if we assume that a sequence is non-empty, the rest of a one
character sequence after removing the first character is empty.  So,
it sounds like:

  [^]                 (2)

is definitely a valid regular expression meaning *match anything*.

  To include a literal ']' in the sequence, make it the first
  character (following a possible '^').

So, to match anything but a literal ']' we have to use:

  [^]]                (3)

And to match anything but '[' or ']' we have to use:

  [^][]               (4)

Wait... that can also be parsed as match anything (2) followed by
match nothing (1)!

Perhaps I'm misreading the standard.  I'd appreciate confirmation or
any help clarifying my mistake.

Thanks,

:) Neal

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 24 Dec 2020 08:58:18 -0500

Hi Neal--

nice find!  it's rather ugly, though.

the most straightforward way to resolve it seems to be to say that
sequences in a [] must be non-empty.

This means we don't get to say "[]", but that's ok because we already
have ".", which will handily replace it with the same semantics.  We
also don't get to say "[^]".  While i don't know how to replicate the
"no match" semantics, i'm also unclear where it could possibly be
useful.

Seems like a sufficient clarification would be:

-A range is a sequence of characters enclosed in '[]'.
+A range is a non-empty sequence of characters enclosed in '[]'.

Are there any implementers or users of the regex spec who see this as a
problem?

Neal, perhaps you want to formally file this as an erratum on rfc4880?

    --dkg

---

From: "Neal H. Walfield" <[email-masked]>
Date: Sun, 27 Dec 2020 11:57:32 +0100

Hi Daniel,

Thanks for following up.

On Thu, 24 Dec 2020 14:58:18 +0100,
> nice find!  it's rather ugly, though.

Thanks for confirming my suspicions.

> sequences in a [] must be non-empty.

Indeed.

> "no match" semantics, i'm also unclear where it could possibly be

For a non-empty regex, you can use an anchor where it doesn't belong.
So, 'a^' won't match anything.  Likewise, '$a' won't match anything.
This is obviously context sensitive, so it is not a perfect
replacement, but I don't think "no match" is that useful in practice.

> +A range is a non-empty sequence of characters enclosed in '[]'.

We need to exclude [^] as well.  Perhaps:

+A range is a non-empty sequence of characters excluding the optional
leading ^ enclosed in '[]'.

> Neal, perhaps you want to formally file this as an erratum on rfc4880?

I'll do that.

Thanks,

Neal