Subject: ABNF switch: list rules

From: Julian Reschke <[email-masked]>
Date: Thu, 22 May 2008 14:46:45 +0200

Hi.

We (well, I) haven't made big progress with respect to switching the BNF 
syntax to standard ABNF format, as defined by RFC 5234.

Reminder: after having cleaned up the existing BNF productions, the 
remaining issues are:

1) "/" instead of "|"
2) implicit LWS
3) the list rule ("#")

As far as I recall, we discussed 3) in Vancouver, and consensus was not 
to keep the list rule 
(<http://tools.ietf.org/wg/httpbis/minutes?item=minutes70.html>).

Let's take an example, such as Accept-Charset:

   Accept-Charset = "Accept-Charset" ":"
           1#( ( charset | "*" ) [ ";" "q" "=" qvalue ] )

(<http://greenbytes.de/tech/webdav/draft-ietf-httpbis-p3-payload-02.html#rfc.section.6.2>)

A mechanical translation would yield:

   Accept-Charset = "Accept-Charset" ":"
                  ( *LWS ( charset / "*" ) [ ";q=" qvalue ]
                 *( *LWS "," *LWS ( charset / "*" ) [ ";q=" qvalue ] ) )

(hopefully).

This is not very readable.

What we could do is introduce additional productions to enhance 
readability, such as in:

   AC-f = ( ( charset | "*" )[ ";" "q" "=" qvalue ] )
   AC-e = *LWS AC-f

   Accept-Charset = "Accept-Charset" ":" AC-e *( *LWS "," AC-e )

Feedback appreciated...

Julian

---

From: Alexey Melnikov <[email-masked]>
Date: Thu, 22 May 2008 16:59:16 +0400

> Hi.
Hi Julian,
> We (well, I) haven't made big progress with respect to switching the 
> BNF syntax to standard ABNF format, as defined by RFC 5234.
>
> As far as I recall, we discussed 3) in Vancouver, and consensus was 
> not to keep the list rule 
I vaguely remember there was a proposal to define something like
 COLONLWS = ":" *LWS

which might make this slightly more readable.
But otherwise this looks reasonable to me.

---

From: Bjoern Hoehrmann <[email-masked]>
Date: Thu, 22 May 2008 15:23:48 +0200

>                 *( *LWS "," *LWS ( charset / "*" ) [ ";q=" qvalue ] ) )

There are several differences here in what values the two allow; you did
not call them out so I am not sure whether they are intentional. In par-
ticular these are valid under the old production but not under yours:

  Accept-Charset: utf-8,,*
  Accept-Charset: utf-8 ; q = ...

I'm not sure whether your new production should be read assuming implied
linear white space, if not there are a number of additional differences,
and if so, then the production is more complex than would be necessary.

It would certainly be wise to factor repeated productions out into sepa-
rate productions, yes.
-- 
Björn Höhrmann · mailto:[email-masked] · http://bjoern.hoehrmann.de
Weinh. Str. 22 · Telefon: +49(0)621/4309674 · http://www.bjoernsworld.de
68309 Mannheim · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/

---

From: Jamie Lokier <[email-masked]>
Date: Thu, 22 May 2008 14:31:05 +0100

>   Accept-Charset = "Accept-Charset" ":" AC-e *( *LWS "," AC-e )

What Bjoern said:

    Accept-Charset: utf-8 ; q = 1

Although that was allowed, I wouldn't be surprised if it trips up some
implementations.

And also, *LWS at the end after the last non-LWS character.

-- Jamie

---

From: Julian Reschke <[email-masked]>
Date: Fri, 23 May 2008 15:19:09 +0200

> ticular these are valid under the old production but not under yours:

Good catch.

It seems to me that

"Wherever this construct is used, null elements are allowed, but do not 
contribute to the count of elements present. That is, "(element), , 
(element) " is permitted, but counts as only two elements. Therefore, 
where at least one element is required, at least one non-null element 
MUST be present. Default values are 0 and infinity so that "#element" 
allows any number, including zero; "1#element" requires at least one; 
and "1#2element" allows one or two."

doesn't translate well into ABNF syntax. So even if we said:

    Accept-Charset = "Accept-Charset" ":"
              ( *LWS ( charset / "*" ) [ ";q=" qvalue ]
             *( *LWS "," *LWS [ ( charset / "*" ) [ ";q=" qvalue ] ] ) )

that would allow

   Accept-Charset: utf-8,,*

but not

   Accept-Charset: ,,utf-8

which is valid in RFC2616. So we need to handle leading ("," *LWS) 
separately...

>   Accept-Charset: utf-8 ; q = ...

That's mistake I made when pasting bap's output back into the mail (bap 
doesn't know about implied LWS). So it should have read:

Accept-Charset = "Accept-Charset" ":"
             ( *LWS ( charset / "*" ) [ ";" "q" "=" qvalue ]
            *( *LWS "," *LWS ( charset / "*" ) [ ";" "q" "=" qvalue ] ) )

> and if so, then the production is more complex than would be necessary.

I was trying to get the list rule issue resolved first; of course the 
implied LWS needs to be resolved as well.

> It would certainly be wise to factor repeated productions out into sepa-

So, combining this, but still ignoring implied LWS, we'd get:

   Accept-Charset = "Accept-Charset" ":" *( *LWS "," ) AC-e *( *LWS "," 
[ AC-e ])

Or...

   COMMA = *LWS ","

   Accept-Charset = "Accept-Charset" ":" *COMMA AC-e *( COMMA [ AC-e ])

The more I look into this, the better the original syntax looks :-)

BR, Julian

---

From: Henrik Nordstrom <[email-masked]>
Date: Sat, 24 May 2008 01:25:43 +0200

> The more I look into this, the better the original syntax looks :-)

Yes, there is reasons why HTTP has the list syntax.. and I think that
one does a great job in keeping the BNF readable.

The reasons for the implied LWS is the same, to make the grammar more
readable, but unfortunately that one hasn't worked out very well..

If we can get the BNF syntax to a level of

  ABNF + list syntax, without implied LWS

then a lot is gained.

Eleminating the list syntax is mainly a goal to line up the HTTP BNF
syntax completely with other specifications, but I have a feeling that
it may be better to extend ABNF with a usable list construct.

While we are at that topic. The specification probably should make sure
to recommend producers to not produce lists with empty elements (a
SHOULD NOT). Not sure we have that in the specs today. Parsers MUST
accept them however and is what the BNF description describes but there
quite likely is many broken implementations out there not expecting
empty elements..

Regards
Henrik

---

From: "Zed A. Shaw" <[email-masked]>
Date: Sat, 24 May 2008 03:33:47 -0400

On Fri, 23 May 2008 15:19:09 +0200

>    Accept-Charset = "Accept-Charset" ":" *COMMA AC-e *( COMMA [ AC-e ])

That's actually a common production in programming languages that have
a ; to separate expressions.  They would always have a production that
says something like "a program is a list of expressions separated by ;
and a ; on its own is an empty expression".

The only thing is most parsers and lexers have a way to ignore
whitespace during operation, so they wouldn't need to include the LWS.

Based on that, you could rewrite it like this to be a bit clearer and
potentially reusable for other similar lists:

AC-QValue = ";" "q" "=" qvalue
AC-Type = (charset | "*")
AC-Expression = AC-Type AC-QValue?
AC-Element = *LWS [AC-Expression] [","]
Accept-Charset = "Accept-Charset" ":" *(AC-Element)

Assuming I got the syntax right (didn't refresh my memory about ABNF),
it's effectively saying:

"AC is 'Accept-Charset:' followed by any number of elements.  Elements
have any amount of leading white-space, an optional expression, and an
optional comma.  Expressions have a type and optional q-value."

You should then be able to sprinkle LWS production where they belong.

-- 
Zed A. Shaw
- Hate: http://savingtheinternetwithhate.com/
- Good: http://www.zedshaw.com/
- Evil: http://yearofevil.com/

---

From: Julian Reschke <[email-masked]>
Date: Sat, 24 May 2008 10:13:45 +0200

>   ABNF + list syntax, without implied LWS

Right.

In particular it seems it would be wise to solve the "implied LWS" issue 
*first*, and only then start looking at the list production.

> it may be better to extend ABNF with a usable list construct.

I'd prefer that.

If we can't keep it, I'd probably recommend to leave the # notation at 
least in ABNF comments.

> quite likely is many broken implementations out there not expecting

What do others think? Is there consensus for this? In which case we 
should raise a separate issue.

BR, Julian

---

From: Julian Reschke <[email-masked]>
Date: Sat, 24 May 2008 10:10:12 +0200

> AC-Expression = AC-Type AC-QValue?

AC-Expression = AC-Type [AC-QValue]

> optional comma.  Expressions have a type and optional q-value."

Right, but RFC2616 requires that the list includes at least one 
none-empty element :-)

BR, Julian

---

From: "Zed A. Shaw" <[email-masked]>
Date: Sat, 24 May 2008 05:05:19 -0400

On Sat, 24 May 2008 10:10:12 +0200

> Right, but RFC2616 requires that the list includes at least one 

Well, if it were a programming language I would say that's for
semantic analysis, rather than trying to cram that into the parser.
But yes, my version doesn't do that.

And looking at your's that's the way you have to do it to
enforce at least one element in the list.  Interesting.

On another note, is there a reason why it's specified this way with
the allowed empty elements at random locations? 

It makes more sense to just not send anything that'd be empty, rather
than using empty elements.  In theory someone could just stream a ton of
',' to make the server do useless work, which could thwart some poorly
implemented parsers.

I'm curious about the history if anyone knows it.

---

From: Julian Reschke <[email-masked]>
Date: Sat, 24 May 2008 11:59:02 +0200

Zed A. Shaw wrote:
> ...

I have no idea what it's good for and why it was specified this way in 
the first place.

> ',' to make the server do useless work, which could thwart some poorly

As far as I recall, it's a known attack vector (don't forget there can 
be CRs in between the list as well...).

BR, Julian

---

From: "Frank Ellermann" <[email-masked]>
Date: Sat, 24 May 2008 17:31:52 +0200

> it may be better to extend ABNF with a usable list construct.

Only if you consider empty 1F "appeal threatened" sections as boring.

The #-LWS horror permits ASCII art by commas, and that cruft has to 
be very explicit.  Recently 2822upd managed to split this into a no
nonsense ABNF, plus an *obsolete* ABNF covering ASCII art with commas.

ASCII art with commas is ugly like hell.  But if you try to keep any
"apparently empty lines" containing only significant white space for
LWS it is broken.  Kill it, or if you keep it make sure that it is
mentioned in the security considerations, and covered by a detailed
implementation and interoperability report.  

RFC 2822 + 2822upd have those "apparently empty lines" in <obs-FWS>,
nowhere else.  STD 68 mentions the issue in an <LWSP> ABNF comment.

You have already seen the 2831bis "translation" of the #-LWS horrors,
was anything wrong with that, or why are you looking for other ideas ?

 Frank

---

From: "Frank Ellermann" <[email-masked]>
Date: Sat, 24 May 2008 18:02:46 +0200

Julian Reschke wrote:

> Is there consensus for this?

No.  #-LWS has to be killed or obsoleted.  ASCII art by commas
is only ridiculous, but "apparently empty lines" are dangerous.
Example, #x permits...

 ,,,   ,   ,   ,,,  <CRLF>
 ,  ,  ,   ,  ,     <CRLF>
 ,,,   ,   ,  , ,,, <CRLF>
 ,  ,  ,   ,  ,   , <CRLF>
 ,,,    ,,,    ,,,  <CRLF>

...and that's IMNSHO ugly.  But it also permits...

 ,,,,,,,,,<CRLF>
<SP>      <CRLF>
<HTAB>    <CRLF>
 ,,,,,,,,,<CRLF>
 
...and that is dangerous when applications don't get the subtle
difference between "really empty" <CRLF> and "apparently empty"
<SP><CRLF> or even <HTAB><CRLF> lines.

The ABNF has to be very obvious what is permitted, and what is
obsoleted, without misguided attempts to hide these horrors in
any #-constructs.  

The one and only point of the "ABNF-ication" is precisely this
#-LWS issue, otherwise nothing was wrong with the old 2068-BNF.

 Frank

---

From: Mark Nottingham <[email-masked]>
Date: Sun, 25 May 2008 09:45:14 +1000

On 24/05/2008, at 6:13 PM, Julian Reschke wrote:

> In particular it seems it would be wise to solve the "implied LWS"  
> issue *first*, and only then start looking at the list production.

+1

> If we can't keep it, I'd probably recommend to leave the # notation  
> at least in ABNF comments.

+1

--
Mark Nottingham     http://www.mnot.net/

---

From: Mark Nottingham <[email-masked]>
Date: Sun, 25 May 2008 09:44:47 +1000

I disagree; I've seen implementations produce empty elements, and  
"it's ugly" isn't a good enough reason to break them.

That's not to say that we shouldn't discourage it. Also, we have an  
open issue about whether line folding should be disallowed;
   http://tools.ietf.org/wg/httpbis/trac/ticket/77

> obsoleted, without misguided attempts to hide these horrors in

Yes, which is why we should address the LWS issue first.

---

From: "Frank Ellermann" <[email-masked]>
Date: Tue, 27 May 2008 12:05:42 +0200

Julian Reschke wrote:

> I have no idea what it's good for and why it was specified
> this way in the first place.

"Copied from RFC 822" is likely a part of the answer, you can
find some fresh #-magic in 2822upd chapter 4 (obsolete syntax)
for some RFC 822 list constructs not yet covered by RFC 2822.

>> I'm curious about the history if anyone knows it.

RFC 2068 is older than RFC 2234/4234/5234, the #-construct is
an attractive shorthand when you are not aware of the details.
Of course I'm only guessing.

 Frank

---

From: "Frank Ellermann" <[email-masked]>
Date: Tue, 27 May 2008 15:43:08 +0200

Mark Nottingham wrote:
 
> I disagree; I've seen implementations produce empty elements,  
> and "it's ugly" isn't a good enough reason to break them.
 
> That's not to say that we shouldn't discourage it.

Julian just wrote that he will do "ABNF-ication" as first step.

After that it should be clearer that those ugly empty elements
are only ugly, the combination with more than one CRLF in LWSP
is the point where it can get out of hand wrt interoperability.

> we have an open issue about whether line folding should be
> disallowed;

Without any folding there can't be an <obs-FWS> multi-folding,
that would simplify the #-LWS issue.  Based on proper ABNF it
should be simple to get this right, either replace each LWSP
by [FWS] and say "MUST NOT generate <obs-FWS>", or replace it
by *WSP without folding.

If folding is still allowed (for the FWS approach) we have to
check that there are no cases where adjacent FWS is implicitly
possible (resulting in 2*FWS).

 Frank