Subject: Re: [abnf-discuss] Mail regarding draft-seantek-constrained-abnf

From: Sean Leonard <[email-masked]>
Date: Fri, 8 Jul 2016 09:23:02 -0700

+abnf-discuss@

On 7/8/2016 8:06 AM, Paul Kyzivat wrote:
> On 7/8/16 8:11 AM, Jonathan Hansford wrote:
>> Hi,
>>
>>
>>
>> I’ve just discovered draft-seantek-constrained-abnf-00 and have a couple
>> of questions:
>
> Note that while Sean and I have been bouncing ideas around about this 
> for some time, the draft is a trial balloon and the specific text is 
> all Sean's. I'm not yet wild about some of the syntax, but it is good 
> to have something tangible written down to talk about.
>
> So far it seems that only Sean and I are interested. If you are, then 
> that would make three.

Yay for three!

>
>> 1)      Does Constrained ABNF work with RFC 7405 “Case-Sensitive String
>> Support in ABNF”? Either way, it might be worth mentioning that RFC in
>> your I-D.
>
> Certainly it does. The functionality is entirely orthogonal.

Yes, what Paul said.

>
>> 2)      Has there been any call to further constrain ABNF such that
>> rules can have length constraints applied to them? I’m not sure how much
>> benefit there would be for RFCs (though I can think of examples where
>> identifying such a constraint within the ABNF rather than just within
>> the accompanying text would be beneficial), but a Constrained ABNF
>> compliant parser that included length constraints would be good.
>
> I'm not aware of any such thing. Of course it already has repetition 
> constraints, but I guess that is not what you are looking for.
>
> I have difficulty imagining how you would fit such constraints into 
> the syntax. The syntax of ABNF is pretty nice for what it does, but it 
> doesn't leave much room for extension because we are running out of 
> special characters. (Perhaps the possibilities could be expanded by 
> using unicode characters. Imagine what could be done with emojis as 
> operator characters.)

Length constraints are expressible with current ABNF. Generically, 
suppose you have an identifier comprised of ALPHAs and DIGITs:

identifier = 1*(ALPHA / DIGIT)

Well, if you want to limit identifier to 20 chars, then you can say max 
twenty:

identifier = 1*20(ALPHA / DIGIT)

As Paul says, this is a repetition constraints, and is easy to analyze 
with the repeated symbols are fixed-width. But what about variable width?

Well, suppose you have Domain from RFC 5321:

    Domain         = sub-domain *("." sub-domain)

    sub-domain     = Let-dig [Ldh-str]
    Let-dig        = ALPHA / DIGIT
    Ldh-str        = *( ALPHA / DIGIT / "-" ) Let-dig

Now suppose you want to constrain Domain to be 255 chars. Such a 
constrained domain might be called DNSDomain. Then you can say:

    DNSDomain ^ Domain = 1*255ASCII

...and that's it! Basically you have to compose a production that 
evaluates to a single symbol (character/integer), where the domain of 
the symbol is any possible character that can appear in the production. 
The minimum conforming production would be:

    DNSDomain ^ Domain = 1*255(ALPHA / DIGIT / "-" / ".")

The maximum conforming production would be:

    DNSDomain ^ Domain = 1*255(%x00-FFFFFFFFFFFFFFFFFFFFFFFFF...(infinity))

Reducing the production from a non-maximum to the minimum form, can be 
evaluated programmatically. A parser would need to evaluate the 
constrained production for all "reachable" single terminal symbols 
(characters/integers that may appear at least once), which can be done 
more-or-less in O(n) time. It adds all such integers to a set, and then 
expresses the set.

It can also be shown that you can also integrate the constraint into the 
base production, at least for all non-recursive productions. In this 
case, you would have to break down Domain into a very, very long string 
of terminal symbol possibilities (essentially, expressing it as a huge 
finite state machine). Once you get all the possible states, you can 
limit each symbol combination so that the total combinations do not 
exceed 255. This can probably be done computationally, but the proof 
would require a lot of math that I do not care to figure out right now. 
:) And it's unclear how computationally difficult it would be to do it 
in the general case.

Actually now that I think about it, if your constraint is to limit the 
total number of symbols, you can probably prove that any recursive 
expression can be expressed as a finite state machine. Therefore, 
integrating length constraints would actually be computable. It would 
also be super-ugly, but you get the point.

***

Regarding Paul's Unicode point: it would be nice for ABNF to have an 
extension that defines the domain of the input symbols, with specific 
options for: ASCII-only, octets, fixed-bit-width units, UTF-8, 
UTF-16LE/BE, and Unicode scalar values (0-0xD7FF, 0xE000-0x10FFFF), and 
Unicode characters (non-characters such as 0xFFFF are excluded). The 
most important of these are ASCII-only, octets, and Unicode scalar values.

I thought about writing such an I-D, but, it would take more work than I 
have time for right now, and one would have to address a few of issues.

Currently the domain of ABNF is any unsigned integer, which is an 
infinite set. This is good in that you can express anything positive, 
and bad in that you can't express negative symbol productions (e.g., all 
symbols EXCEPT "Q"). Once you constrain the set to finite, you can 
express things like the regex [^Q]. This makes ABNF compilers more 
complex. If you really want to express exclusionary productions, maybe 
BNF languages aren't the right tool for the job?

A compatibility problem arises when you want to reference productions 
from other specs, that have different domains. Suppose that one spec is 
authored in the UTF-8 domain (see LDAP specs e.g., RFC 4512), and other 
spec is authored in the Unicode scalar value domain. This is a real 
issue that I am encountering in draft-seantek-certspec, which I 
encourage you to read...I wanted to import (reference) distinguishedName 
from LDAP / RFC 4514, but distinguishedName includes UTF-8 multibyte 
productions, and draft-seantek-certspec is authored to be at least 
potentially character set neutral. It would be okay (in 
draft-seantek-certspec) to write the string in ISO-2022-JP and then 
convert it to something else.

Converting between domains is computable (e.g., the Unicode scalar value 
expressed as %x1F60A 😊 can be broken down into %xD83D.DE0A or 
%xF0.9F.98.8A), but symbology for doing it would be arcane. We want to 
keep ABNF as simple as possible, and that stuff strikes me as calling 
for a complex syntax.

Any proposal that involves Unicode is going to have to at least think 
about character properties and classes. See UTS #18.

Both the Unicode Consortium and W3C use BNF flavors to describe Unicode 
things. As ABNF uses the same mathematical theories and their BNF 
flavors, it would be good to replicate syntax where possible.

Regards,

Sean

>     Thanks,
>     Paul

---

From: Paul Kyzivat <[email-masked]>
Date: Fri, 8 Jul 2016 12:49:04 -0400

>    DNSDomain ^ Domain = 1*255ASCII

Ah. Interesting!

> most important of these are ASCII-only, octets, and Unicode scalar values.

Note that if you are using quoted strings in ABNF then you are 
restricted to their mapping to ASCII, which then extends obviously to 
Unicode.

I am not well informed about Unicode, but ISTM that if you are using 
ABNF with it then it makes sense to only do it over Unicode scalar 
values, while leaving the conversion of those to/from a particular 
encoding like UTF-8 can be via a pre/post-processor. You need to be a 
glutton for punishment to define your Unicode-based grammar over octets. 
And is there any operational difference between defining ABNF over 
unsigned integers and defining it over Unicode scalar values?

	Thanks,
	Paul

---

From: Sean Leonard <[email-masked]>
Date: Fri, 8 Jul 2016 12:22:13 -0700

> On Jul 8, 2016, at 9:49 AM, Paul Kyzivat <[email-masked]> wrote:
> 
> Note that if you are using quoted strings in ABNF then you are restricted to their mapping to ASCII, which then extends obviously to Unicode.
> 
> I am not well informed about Unicode, but ISTM that if you are using ABNF with it then it makes sense to only do it over Unicode scalar values, while leaving the conversion of those to/from a particular encoding like UTF-8 can be via a pre/post-processor. You need to be a glutton for punishment to define your Unicode-based grammar over octets.

Perhaps. But, that is exactly what RFC 451x (LDAP series) and RFC 3629 (UTF-8 specification) do. The problem is that when you refer to RFC 3629’s ABNF literally, you are operating over octets.

But it is useful to define ABNF over octets when you are dealing with octets, e.g., when you’re defining Unicode encodings themselves!

> And is there any operational difference between defining ABNF over unsigned integers and defining it over Unicode scalar values?

Best to look up the definitions:
http://unicode.org/glossary/

“Technically” if you are in ISO 10646-land, the applicable integers are 0 - (2^32-1). At some point it got limited to 0x10FFFF for various practical reasons, resulting in 1114112 possible code points. Like Bill Gates said, “640K ought to be enough for anybody.”

A Unicode code point is any integer from 0 to 0x10FFFF. But because of the Unicode surrogate technique in the 0xD800-0xDFFF range for UTF-16, the code points 0xD800-0xDFFF can never be assigned to so-called “actual characters”. The “Unicode scalar value” definition carves out a donut hole for these values.

Unfortunately, Unicode scalar value != Unicode characters. That is because some code points are specifically called “noncharacters”, which is to say, they have semantics in the Unicode character set to mean they are not in the character set. There are 66 of them and they are interspersed (although I suppose they can be screened out with bit patterns rather than requiring a big table).

Hence, making ABNF for all of this, is nontrivial. Depending on the use cases, you might want to include them, or you might not want to include them. You could, for example, use them to delimit “strings of Unicode characters” safely, assuming that you really are talking about strings of Unicode characters and not strings of arbitrary integer values that may or may not conform to some version of Unicode.

In my mind, it kind of comes down to, “do you really want to modify a pretty stable standard, ABNF, to incorporate an ever-shifting standard that keeps on giving you more and more 😫?” ABNF is based on ASCII which really hasn’t changed since ’68. ASCII is not without its drawbacks (BEL, anyone?), but it has given us half a century of peace. I’m not against incorporating Unicode, but those are all of the issues.

Sean

---

From: "Jonathan Hansford" <[email-masked]>
Date: Fri, 8 Jul 2016 22:08:48 +0100

Paul and Sean,

Thanks for the replies. Life is too hectic at the moment, but I’m hoping I will find some time to properly read the I-D and your replies and see how it would all work for me. Is there a parser for constrained ABNF at the moment?

Jonathan

=O)

From: Sean Leonard [mailto:[email-masked]] 
Sent: 08 July 2016 17:23
To: Paul Kyzivat <[email-masked]>; Jonathan Hansford <[email-masked]>; [email-masked]
Cc: [email-masked]
Subject: Re: Mail regarding draft-seantek-constrained-abnf

+abnf-discuss@

Hi, 

Note that while Sean and I have been bouncing ideas around about this for some time, the draft is a trial balloon and the specific text is all Sean's. I'm not yet wild about some of the syntax, but it is good to have something tangible written down to talk about. 

So far it seems that only Sean and I are interested. If you are, then that would make three. 

Yay for three!

Yes, what Paul said.

I'm not aware of any such thing. Of course it already has repetition constraints, but I guess that is not what you are looking for. 

I have difficulty imagining how you would fit such constraints into the syntax. The syntax of ABNF is pretty nice for what it does, but it doesn't leave much room for extension because we are running out of special characters. (Perhaps the possibilities could be expanded by using unicode characters. Imagine what could be done with emojis as operator characters.) 

Length constraints are expressible with current ABNF. Generically, suppose you have an identifier comprised of ALPHAs and DIGITs:

Well, if you want to limit identifier to 20 chars, then you can say max twenty:

As Paul says, this is a repetition constraints, and is easy to analyze with the repeated symbols are fixed-width. But what about variable width?

 

Now suppose you want to constrain Domain to be 255 chars. Such a constrained domain might be called DNSDomain. Then you can say:

...and that's it! Basically you have to compose a production that evaluates to a single symbol (character/integer), where the domain of the symbol is any possible character that can appear in the production. The minimum conforming production would be:

Reducing the production from a non-maximum to the minimum form, can be evaluated programmatically. A parser would need to evaluate the constrained production for all "reachable" single terminal symbols (characters/integers that may appear at least once), which can be done more-or-less in O(n) time. It adds all such integers to a set, and then expresses the set.

It can also be shown that you can also integrate the constraint into the base production, at least for all non-recursive productions. In this case, you would have to break down Domain into a very, very long string of terminal symbol possibilities (essentially, expressing it as a huge finite state machine). Once you get all the possible states, you can limit each symbol combination so that the total combinations do not exceed 255. This can probably be done computationally, but the proof would require a lot of math that I do not care to figure out right now. :) And it's unclear how computationally difficult it would be to do it in the general case.

Actually now that I think about it, if your constraint is to limit the total number of symbols, you can probably prove that any recursive expression can be expressed as a finite state machine. Therefore, integrating length constraints would actually be computable. It would also be super-ugly, but you get the point.

***

Regarding Paul's Unicode point: it would be nice for ABNF to have an extension that defines the domain of the input symbols, with specific options for: ASCII-only, octets, fixed-bit-width units, UTF-8, UTF-16LE/BE, and Unicode scalar values (0-0xD7FF, 0xE000-0x10FFFF), and Unicode characters (non-characters such as 0xFFFF are excluded). The most important of these are ASCII-only, octets, and Unicode scalar values.

I thought about writing such an I-D, but, it would take more work than I have time for right now, and one would have to address a few of issues.

Currently the domain of ABNF is any unsigned integer, which is an infinite set. This is good in that you can express anything positive, and bad in that you can't express negative symbol productions (e.g., all symbols EXCEPT "Q"). Once you constrain the set to finite, you can express things like the regex [^Q]. This makes ABNF compilers more complex. If you really want to express exclusionary productions, maybe BNF languages aren't the right tool for the job?

A compatibility problem arises when you want to reference productions from other specs, that have different domains. Suppose that one spec is authored in the UTF-8 domain (see LDAP specs e.g., RFC 4512), and other spec is authored in the Unicode scalar value domain. This is a real issue that I am encountering in draft-seantek-certspec, which I encourage you to read...I wanted to import (reference) distinguishedName from LDAP / RFC 4514, but distinguishedName includes UTF-8 multibyte productions, and draft-seantek-certspec is authored to be at least potentially character set neutral. It would be okay (in draft-seantek-certspec) to write the string in ISO-2022-JP and then convert it to something else.

Converting between domains is computable (e.g., the Unicode scalar value expressed as %x1F60A 😊 can be broken down into %xD83D.DE0A or %xF0.9F.98.8A), but symbology for doing it would be arcane. We want to keep ABNF as simple as possible, and that stuff strikes me as calling for a complex syntax.

Any proposal that involves Unicode is going to have to at least think about character properties and classes. See UTS #18.

Both the Unicode Consortium and W3C use BNF flavors to describe Unicode things. As ABNF uses the same mathematical theories and their BNF flavors, it would be good to replicate syntax where possible.

Regards,

Sean

    Thanks, 
    Paul

---

From: Paul Kyzivat <[email-masked]>
Date: Fri, 8 Jul 2016 18:11:09 -0400

On 7/8/16 5:08 PM, Jonathan Hansford wrote:
> Paul and Sean,
>
>
>
> Thanks for the replies. Life is too hectic at the moment, but I’m hoping
> I will find some time to properly read the I-D and your replies and see
> how it would all work for me. Is there a parser for constrained ABNF at
> the moment?

AFAIK there is not. As I said, the draft is a trial balloon. I think it 
still needs a lot of work, not on the general concept, but on how you 
link grammars together. (The use case that drives my interest is 
defining extensibility hooks in a grammar when defining a standard, and 
then writing another draft that adds syntactical extensions from such a 
hook.)

I'm not aware of a generally available parser for case-sensitive ABNF 
either. I developed extensions to Bap to do it, and made them available 
to the author on github, but he never took them. I saw somebody else 
with another (worse) implementation, but AFAIK it also at least hasn't 
made it into the web-based Bap linked to the ietf tools page.

	Thanks,
	Paul

> Jonathan
>
>
>
> =O)
>
>
>
> *From:*Sean Leonard [mailto:[email-masked]]
> *Sent:* 08 July 2016 17:23
> *To:* Paul Kyzivat <[email-masked]>; Jonathan Hansford
> <[email-masked]>; [email-masked]
> *Cc:* [email-masked]
> *Subject:* Re: Mail regarding draft-seantek-constrained-abnf
>
>
>
> +abnf-discuss@
>
>     Note that while Sean and I have been bouncing ideas around about
>     this for some time, the draft is a trial balloon and the specific
>     text is all Sean's. I'm not yet wild about some of the syntax, but
>     it is good to have something tangible written down to talk about.
>
>     the syntax. The syntax of ABNF is pretty nice for what it does, but
>     it doesn't leave much room for extension because we are running out
>     of special characters. (Perhaps the possibilities could be expanded
>     by using unicode characters. Imagine what could be done with emojis
>     as operator characters.)
>
>
> _______________________________________________
> abnf-discuss mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/abnf-discuss
>

---

From: Paul Kyzivat <[email-masked]>
Date: Fri, 8 Jul 2016 18:39:40 -0400

> A Unicode code point is any integer from 0 to 0x10FFFF. But because of the Unicode surrogate technique in the 0xD800-0xDFFF range for UTF-16, the code points 0xD800-0xDFFF can never be assigned to…

Interesting. As I said, I don't know all that much about Unicode.

> Unfortunately, Unicode scalar value != Unicode characters. That is because some code points are specifically called “noncharacters”, which is to say, they have semantics in the Unicode character se…

IIUC, all Unicode characters have a unique Unicode scalar value, but not 
all Unicode scalar values correspond to Unicode code points.

> In my mind, it kind of comes down to, “do you really want to modify a pretty stable standard, ABNF, to incorporate an ever-shifting standard that keeps on giving you more and more 😫?” ABNF is based…

ISTM that you are making this harder than it needs to be.

It would be difficult (and IMO undesirable) to define ABNF over Unicode 
characters or over ASCII characters. You would have to restrict the 
numeric byte values that you could use. And so ranges might also need to 
be declared invalid in some cases.

"Defined over X" could be a predicate that a verifier could decide for a 
given ABNF grammar. For instance you could verify that 3261 is defined 
over octets. (It never references values greater than 255.) That means 
it is also defined over ranges that a supersets of octets, like 16 and 
32 bit ints.

OTOH, if you analyze an ABNF grammar and find it uses character values 
greater than 255 then you know you must not use it with an input/output 
stream that works in octets.

"Defined over ASCII" and "Defined over Unicode" could also be determined 
by analysis of the grammar.

If the grammar is "defined over Unicode" then you can use I/O that 
converts to UTF-8, UTF-16, etc.

But if it is is not defined that way, then you can't safely use that 
kind of I/O. For instance SIP formally defined over UTF-8. It is 
"mostly" ASCII, but in some places allows UTF-8 by defining the 
allowable sequences of bytes. (But the syntax is *old*. I have no idea 
whether changes in Unicode have invalidated it.)

	Thanks,
	Paul

---

From: Sean Leonard <[email-masked]>
Date: Sat, 9 Jul 2016 00:04:40 -0700

> On Jul 8, 2016, at 2:08 PM, Jonathan Hansford <[email-masked]> wrote:
> 
> Paul and Sean,
>  

Not yet, but you are welcome to write one. :)

Sean

---

From: Sean Leonard <[email-masked]>
Date: Sat, 9 Jul 2016 00:22:53 -0700

> On Jul 8, 2016, at 3:39 PM, Paul Kyzivat <[email-masked]> wrote:
> 
> IIUC, all Unicode characters have a unique Unicode scalar value, but not all Unicode scalar values correspond to Unicode code points.

Not quite; I think you may have it slightly out-of-order:

Unicode code points (0 - 10FFFF) >
 Unicode scalar values (0-D7FF, E000-10FFFF) >
  “Unicode characters” (excluding the noncharacters/noncharacter code points) (0-D7FF, E000-FDCF, FDF0-FFEF, 10000-1FFFD, 20000-2FFFD .. 100000-10FFFD) >
   assigned characters (expands as the Standard advances)

In Unicode, the terms “code point” and “characters” are sometimes interchangeable, and sometimes not. Code points are definitely 0 - 10FFFF. A code point is not a “character” in certain circumstances, for example, if the code point is a “noncharacter” (literally, it’s a code point that is assigned to be NOT a character), or if the code point is an “unassigned/reserved code point” (literally, it is a code point that is NOT assigned, but is reserved for future assignment; once assigned it presumably fits the definition of a character).

-Sean

---

From: Sean Leonard <[email-masked]>
Date: Sat, 9 Jul 2016 00:51:16 -0700

> [...]
> "Defined over X" could be a predicate that a verifier could decide for a given ABNF grammar. [...]
> 
> "Defined over ASCII" and "Defined over Unicode" could also be determined by analysis of the grammar.

Up to this point, that is determined by (human) analysis of the specification text. It’s worked out overall.

As much as I would like to see some more Unicode action, we already have two proposals on the table that I would like to focus on and get adopted & passed, before working on new stuff. The proposals are abnf-more-core-rules and constrained-abnf.

In abnf-more-core-rules, there already are mechanisms for incorporating Unicode, in the productions:
 UNICODE
 BEYONDASCII
 C1
 BEYONDC1 (to be included in next draft)

I suppose the following could be added:
 LATIN1
 BEYONDLATIN1

I submit that these mechanisms are probably “quite enough” for IETF usage. There is a strong bias in ABNF for ASCII, which basically reflects the institutional bias in the IETF for US-English and the history of the Internet’s development. I have yet to see an IETF standard that calls out a specific character beyond the ASCII range and gives it special semantics (other than NEL, and even then, NEL is not really used).

Sean

---

From: Paul Kyzivat <[email-masked]>
Date: Sat, 9 Jul 2016 13:56:03 -0400

> Up to this point, that is determined by (human) analysis of the specification text. It’s worked out overall.

IIUC this can be determined mechanically. First it is necessary to 
decide whether we mean "defined over Unicode codepoints" or "defined 
over Unicode characters". I guess defining over characters is a moving 
target, while code points are (relatively) stable.

And I think for ABNF, defining over codepoints is good enough. If you 
know that, then I/O processes that convert to/from UTF-8, etc. are valid 
to use.

> I submit that these mechanisms are probably “quite enough” for IETF usage. There is a strong bias in ABNF for ASCII, which basically reflects the institutional bias in the IETF for US-English and t…

I'm not convinced. You can *already* do Unicode. All the above do is 
give you some standard symbols to use for ranges of values that are 
interesting in the context of Unicode. They don't standardize any way of 
introducing Unicode characters that don't fall into the ASCII subset. 
People will still need to enter those numerically, or define symbols for 
ones they care about.

Your draft for more core rules hasn't received a lot of support - 
perhaps because it isn't perceived to add sufficient value to be worth 
the trouble.

ISTM that an important part of "supporting" Unicode in ABNF would be 
allowing use of Unicode characters in some form of quoted string. 
(Perhaps yet another new form.) That might add perceived value to those 
who really want to define grammars that actually *use* non-ascii 
characters.

I think in turn that defining that only makes sense if the grammars 
using those work over Uncode scalar values. (The alternative to that 
seems to be to define those literals to expand into UTF-8, so each 
character in the string might represent multiple bytes. And then you 
need to know what encoding the parser is running over.)

That in turn presumes some way to get unicode scalar values into the 
parser. I think maybe that requires some sort of "framework" that 
discusses input/output to the parser.

OTOH, I don't see a groundswell of users clamoring for this sort of 
thing. So for now I think this is ought to just be a background discussion.

	Thanks,
	Paul

	Thanks,
	Paul