Re: [xdi] Second draft of simplified top-level ABNF

["=Drummond Reed" <drummond.reed@xdi.org>]

William, good question, I know that when it gets to ABNF issues, it gets really esoteric really fast.

In layman's terms, I'd put it this way: XDI parsing could be much more expensive if we allow recursive nesting of XDI addresses inside parentheses (what we have been calling "cross-reference" syntax). Back in the early days of XDI we had use cases for doing that, but that was before we developed our modern syntax.

With the modern syntax I believe we no longer have the use cases requiring recursive addresses. If other TC members agree, then we can drop recursive nesting, simplify the ABNF, and make XDI parsing faster and lighter-weight.

=Drummond 

On Tue, Oct 28, 2014 at 11:30 AM, William Dyson <william@darmik.com> wrote:

Is there anyway to explain in laymen terms ?

Thanks

William 

On October 28, 2014 at 10:03:07 AM, Joseph Boyle (planetwork@josephboyle.net) wrote:

Here’s the recursion issue I brought up. For the most part, the XDI ABNF grammar proceeds top-down from high-level productions like xdi-statement and xdi-address, to individual address path components like roots, entities and attributes, and finally the basic syntax of XDI identifiers as well as embedded identifiers and values from other standards like JSON values and IRIs (URIs). 

The exception is the cross-reference (xref) construct which can jump back up and include higher-level productions. I think these recursive cases may correspond to theoretical constructs we don’t use and probably don’t need. Eliminating them would further simplify parsing and processing XDI, which could be significant as we progress to higher-volume software where performance becomes more of a consideration.

The XDI ABNF currently defines these singletons and collection member indexes:  

(keep in mind for Display Format, the C-I delimiter evaluates to empty string)

person-singleton     = "=" C-I ( xdi-name / xref / xdi-scheme )
legal-singleton      = "+" C-I ( xdi-name / xref / xdi-scheme )
general-singleton    = "*" C-I ( xdi-name / xref / xdi-scheme )
unreserved-class     = "#" C-I ( xdi-name / xref / xdi-scheme )

unordered-member     = "!" C-I ( xdi-name / xref / xdi-scheme )

An example with xdi-name is =markus and an example with xdi-scheme is !:uuid:dddd2222-…. 

These two cases are not recursive; only the xref case is. xref is defined as:

xref        = "(" ( common-address / xdi-iri / xdi-name ) ")"

An example with xdi-name is =(markus) (the “relative name” construct) and an example with xdi-iri is (http://example.com/user/markus). 

These two cases are not recursive either; only the common-address case is.

common-address is an XDI address which has no peer roots or inner roots, i.e. it is made up only of entities, attributes, and variables. 

An example singleton with common-address might be like +(=another-person*level1!index2)

Since each singleton within the common-address can in turn contain an xref with a enclosed common-address, we potentially have another level of recursion:

+(=(+another-company*employee.name!their-data)*(=this.person*category!index)!(=some_other_person*selector))

and so on, ad infinitum. Unless we really need this, I’d like to remove the possibility and confine xrefs to finite cases with a rule:

xref        = "(" ( xdi-iri / xdi-name ) ")"

I don’t think we are actually using this kind of recursion, but please consider whether we need it, and we can discuss it at a TC meeting and see if there is consensus.

A similar recursion issue we did dispose of is whether roots can contain more roots. Drummond concluded this does not correspond to anything we do or will use. Therefore, I’ve changed the ABNF so that a peer-root contains a common-address instead of an xdi-address, and an inner-root contains two common-addresses. (Note common-address does not include a final & for right-side literal addresses in relational statements either.)  We should also understand, discuss, and confirm this one.

On Oct 26, 2014, at 9:35 PM, =Drummond Reed <drummond.reed@xdi.org> wrote:

Joseph and I took advantage of another Sunday in Berkeley to get a working session in on the ABNF for XDI Core. See the newest entry (labelled Drummond Reed and Joseph Boyle 2014-10-26) on the XdiAbnf/Discussion page.

The basic action item was very simple: revise the previous simplified ABNF that we developed in August to reflect the decision about the removal of value nodes.

That didn't take very long. The rest of the work was on refactoring the ABNF to use rule names that are much more semantically precise, which is good not just for the ABNF but for the XDI Core spec and any other XDI spec that will need to reference these rule names. Specific examples:

• Supergraph and subgraph were replaced by rooted-address and common-address.
• We added a new rule for arc-address that includes all the atomic XDI arc types.

Joseph also continued work on the ABNF for the next layers down, i.e., the rules that will define the valid character sequences for the different arc-address types.

We also had a long discussion about cross-references, e.g., =(mailto:john@example.com). Joseph and I agreed they were still needed for URIs and for relative XDI names, but we were not sure we still needed them to encapsulate other XDI addresses. That's important because if we DON'T need to do that, we can avoid recursion in cross-references, which would be a big win.

Joseph is going to send a message exploring that question in more detail.

=Drummond