Subject: Re: [Cellar] EBML Element Parenting

From: Steve Lhomme <[email-masked]>
Date: Sun, 25 Sep 2016 09:53:01 +0200

We keep on updating the draft for this (big) change on Github.

To defined CRC-32 and Void that can have all kinds of parents we need
some kind of regular expression. For now I think `/+` and `/*`
respectively are good candidates to describe them.

For the parent description we need to make these expressions
unambiguously interpreted so it should be based on some regular
expression format. We don't want to reinvent the wheel here so
something already standardized would be better.

We need a format that allows:
- basic paths (`/xx/yy/c`)
- any path possible (`/*`)
- any path possible except the root (`/+`)

optional but welcome:
- repeatable path that would describe programmatically how the
recursion works (`/Tags/Tag[/SimpleTag]+`)
- a combination of pathes (`/xx/yy/[a|b|c]`)

While thinking about this it becomes clearer that what we need for
each element is not to define the parent (or the level) but actually
its valid path(es).

even more optional
- a way to make pathes mutually exclusive
- a way to make pathes relate to each other (all timestamps that
depend on the timestampscale)
- a way to mark elements that must both be present
(TimestampScaleNumerator & TimestampScaleDenominator)

By adopting a regular expression format we may impose some
restrictions on what is possible too. A very complex regular
expression handling would mean valid parsers would be required to
handle complex files for no good reasons.

2016-08-23 21:00 GMT+02:00 Dave Rice <[email-masked]>:
>
>> On Aug 23, 2016, at 2:41 PM, Steve Lhomme <[email-masked]> wrote:
>>
>> 2016-08-23 20:39 GMT+02:00 Dave Rice <[email-masked]>:
>>>
>>>> On Aug 23, 2016, at 2:35 PM, Steve Lhomme <[email-masked]> wrote:
>>>>
>>>> I updated the pull request with something that merges with the current master.
>>>>
>>>> Anyone disagree with the move before I merge it ?
>>>
>>> I've been thinking about it and have slowly starting thinking that this is a better approach than I first thought. It does deviate from the XML Schema analogy but maybe the complexity of XML Schemas aren't for the best here. You're right that it would be easier to add extensions (divx) with this approach. It also resolves the issue with xml being normative, since the text and xml versions would be more semantically identical without depending on xml nesting.
>>>
>>>> The next steps after that:
>>>> - unflatten the XML definition
>>>
>>> What do you mean?
>>
>> <EBMLSchema docType="files-in-ebml-demo" version="1">
>> <!-- Root Element-->
>> <element name="Files" parent="/" id="0x1946696C" type="master">
>>  <documentation lang="en" type="definition">Container of data and
>>  attributes representing one or many files.</documentation>
>> </element>
>> <element name="File" parent="/Files" id="0x6146" type="master" minOccurs="1"
>>  maxOccurs="unbounded">
>>   <documentation lang="en" type="definition">An attached file.</documentation>
>> </element>
>> <element name="FileName" parent="/Files/File" id="0x614E" type="utf-8"
>>   minOccurs="1">
>>  <documentation lang="en" type="definition">Filename of the attached
>>  file.</documentation>
>> </element>
>> <element name="MimeType" parent="/Files/File" id="0x464D" type="string"
>>   minOccurs="1">
>>  <documentation lang="en" type="definition">MIME type of the
>>  file.</documentation>
>> </element>
>> <element name="ModificationTimestamp" parent="/Files/File" id="0x4654"
>>   type="date" minOccurs="1">
>>  <documentation lang="en" type="definition">Modification timestamp of
>>  the file.</documentation>
>> </element>
>> <element name="Data" parent="/Files/File" id="0x4664" type="binary"
>>   minOccurs="1">
>>  <documentation lang="en" type="definition">The data of the
>>  file.</documentation>
>> </element>
>> </EBMLSchema>
>
> Ah, I would have considered that action as 'flattening', but I support the example that we'll use parent rather than nested elements.
>
>> No more hierarchy that could potentially interfere with the one
>> defined in "parent". Also as discussed before elements like Void have
>> no real hierarchy.
>
> +1
> Dave
>
>>>> - remove the level altogether, including all text references and in
>>>> the Matroska specs.
>>>
>>> Yes.
>>> Dave
>>>
>>>> 2016-08-05 17:34 GMT+02:00 Steve Lhomme <[email-masked]>:
>>>>> 2016-08-05 17:26 GMT+02:00 Dave Rice <[email-masked]>:
>>>>>>
>>>>>>> On Aug 5, 2016, at 11:13 AM, Steve Lhomme <[email-masked]> wrote:
>>>>>>>
>>>>>>> 2016-08-05 17:09 GMT+02:00 Steve Lhomme <[email-masked]>:
>>>>>>>> 2016-08-02 2:50 GMT+02:00 Dave Rice <[email-masked]>:
>>>>>>>>>
>>>>>>>>> On Jul 31, 2016, at 11:41 AM, Steve Lhomme <[email-masked]> wrote:
>>>>>>>>>
>>>>>>>>> As we're moving towards splitting the Matroska specs in many smaller
>>>>>>>>> documents, putting not essential things in a document it becomes more
>>>>>>>>> important to define things differently than the "level" element we
>>>>>>>>> currently rely on. It makes it very difficult to define a single
>>>>>>>>> element without having to copy all its parents to explain where it
>>>>>>>>> should go in the EBML format.
>>>>>>>>>
>>>>>>>>> I think we should set the name of the parent(s) explicitely to avoid
>>>>>>>>> that confusion. We will also not rely anymore on the order in which
>>>>>>>>> elements are defined in the specs.
>>>>>>>>>
>>>>>>>>> I did a pull request with this addition:
>>>>>>>>> https://github.com/Matroska-Org/ebml-specification/pull/83
>>>>>>>>>
>>>>>>>>> This change will probably mean many paragraphs need to be rewritten to
>>>>>>>>> rely less on the level system.
>>>>>>>>>
>>>>>>>>> I will do the pull request for Matroska as well once it's settled.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Sorry to join this conversation late. I think the current state of the EBML
>>>>>>>>> implies two different ways of documenting nesting. The EBML Schema example
>>>>>>>>> simply nests the <elements> within one another. For example:
>>>>>>>>>
>>>>>>>>> <element name="Files" level="0" id="0x1946696C" type="master">
>>>>>>>>>  <element name="File" level="1" id="0x6146" type="master" minOccurs=“1"
>>>>>>>>> maxOccurs=“unbounded">
>>>>>>>>>      <element name="FileName" level="2" id="0x614E" type="utf-8”
>>>>>>>>> minOccurs=“1”/>
>>>>>>>>> </element>
>>>>>>>>> </element>
>>>>>>>>>
>>>>>>>>> The nesting of the EBML Schema implies that FileName occurs within File and
>>>>>>>>> File occurs within Files. The use of the ‘level’ attribute is redundant to
>>>>>>>>> the structure.
>>>>>>>>
>>>>>>>> Yes it's redundant and should probably be removed. It only creates
>>>>>>>> possible issues and gives no extra information. Except when it's 1+
>>>>>>>> which doesn't have any equivalent in XML and is currently not defined.
>>>>>>>>
>>>>>>>>> However, later we list out the elements of the EBML Header in a series of
>>>>>>>>> tables. The tables don’t imply the nested structure as the xml does, so the
>>>>>>>>> level attribute here is needed, though it is certainly a bit unclear since
>>>>>>>>> determining the parent requiring reading backwards to the last master
>>>>>>>>> element of a higher value.
>>>>>>>>>
>>>>>>>>> I prefer to keep the XML analogy where elements are defined in an XML schema
>>>>>>>>> where the arrangement of the elements within one another defines the nesting
>>>>>>>>> structure. Then since we can compile our documentation the “Parent” values
>>>>>>>>> can be decipher from the XML-based EBML Schema. However this gets to a
>>>>>>>>> conversation at the CELLAR working group meeting on whether XML should be
>>>>>>>>> considered normative or not.
>>>>>>>>
>>>>>>>> While I support having an up to date machine readable version of the
>>>>>>>> specs. I don't think it should/will be the actual reference for the
>>>>>>>> specifications.
>>>>>>>>
>>>>>>>> Also the XML parent analogy only works if there's a fixed parent and
>>>>>>>> the element can only be found at that level. How do you define an
>>>>>>>> element that can be found anywhere under /File/Attribute/* (to use the
>>>>>>>> path system) (or elements similar to Void and CRC32 which can be
>>>>>>>> defined for a certain DocType) ? Either we add an attibute in the XML
>>>>>>>> element or we define how level with a + should be interpreted. Since
>>>>>>>> it's extra information it's probably better to put it out of the level
>>>>>>>> (which should go from the XML anyway). How would you define an element
>>>>>>>> that be put anywhere within a DocType in the XML format ? I agree that
>>>>>>>> it would be odd to have a "parent" attribute in a non flat XML file.
>>>>>>>> It's also odd to have a "parent" on a flat XML file.
>>>>>>>
>>>>>>> Also there's still the problem how to define a (set of) element(s)
>>>>>>> outside of the core Matroska speficications.
>>>>>>
>>>>>> You mean to define a custom extra section to Matroska?
>>>>>
>>>>> Yes, outside of the original spec. For example if a company does like
>>>>> DivX and creates a set of new elements. We don't want to update the
>>>>> original Matroska specs for that.
>>>>>
>>>>>>> I can't be the core
>>>>>>> specifications including an external file. It should be that external
>>>>>>> (XML) that tells where it should be inserted. Is there a common XML
>>>>>>> mechanism to inject one file into another ?
>>>>>>
>>>>>> Yes, in XML Schema there is a way to define an element to contain xsd:any meaning that any elements may occur within it. Within that section the sub-element should ideally have a namespace that points to another XML Schema that defines that particular section.
>>>>>>
>>>>>>> Does it involve defining
>>>>>>> all the elements in the original file to define where we want the
>>>>>>> insertion ? With possible mismatch or missing updates.
>>>>>>
>>>>>> It involves the parent format defining where the flexibility can occur so that any valid XML is allowed in a defined area and then the contents of that optionally being defined by another schema.
>>>>>
>>>>> That does not sound very practical/flexible in our case. Or we'd have
>>>>> to define all Master elements with such a system. And that would have
>>>>> to be done for all EBML-based formats.
>>>>>
>>>>>> dave
>>>>>>
>>>>>>>>> So I think I would prefer not to have a ‘parent’ attribute but to allow that
>>>>>>>>> to be implied by the nesting of elements within an EBML Schema. Then the
>>>>>>>>> parent data could be presented for users when we compile documentation from
>>>>>>>>> the EBML Schema. For instance this markdown is build from the EBML Schema
>>>>>>>>> and lists parent values derived from the structure of the EBML Schema.
>>>>>>>>> https://gist.github.com/dericed/dd1710e47dd3b6779463a85e4fc0f788
>>>>>>>>>
>>>>>>>>> Dave Rice
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> --
>>>>>>>> Steve Lhomme
>>>>>>>> Matroska association Chairman
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> Steve Lhomme
>>>>>>> Matroska association Chairman
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> Cellar mailing list
>>>>>>> [email-masked]
>>>>>>> https://www.ietf.org/mailman/listinfo/cellar
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> Steve Lhomme
>>>>> Matroska association Chairman
>>>>
>>>>
>>>>
>>>> --
>>>> Steve Lhomme
>>>> Matroska association Chairman
>>>>
>>>> _______________________________________________
>>>> Cellar mailing list
>>>> [email-masked]
>>>> https://www.ietf.org/mailman/listinfo/cellar
>>>
>>
>>
>>
>> --
>> Steve Lhomme
>> Matroska association Chairman
>>
>> _______________________________________________
>> Cellar mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/cellar
>

-- 
Steve Lhomme
Matroska association Chairman

---

From: Steve Lhomme <[email-masked]>
Date: Sun, 25 Sep 2016 10:11:46 +0200

I found the POSIX regex
https://en.wikipedia.org/wiki/Regular_expression#Standards

The ABNF and EBNF
https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form
https://en.wikipedia.org/wiki/Augmented_Backus%E2%80%93Naur_Form

The W3C derivative of the ABNF
https://www.w3.org/TR/REC-xml/#sec-notation

The problem with all these is that they define "character" or "binary"
regular expressions. What we want is something of higher level so we
can use the human friendly names rather than the binary representation
for each element. Maybe we need to define our own ABNF derivative. But
it's harder to parse than an POSIX-like regex. When looking at the
mess it is to do a regex for a URL or email address I don't the ABNF
is doing a great job.

---

From: Reto Kromer <[email-masked]>
Date: Sun, 25 Sep 2016 10:58:40 +0200

>https://en.wikipedia.org/wiki/Regular_expression#Standards

The formal standard is:

  ISO/IEC/IEEE 9945:2009
  Information technology -- Portable Operating System
  Interface (POSIX) Base Specifications, Issue 7

which contains much more than "just" the regex.

Best regards, Reto

AV Preservation by reto.ch
chemin du Suchet 5 | 1024 Ecublens | Switzerland
Web: https://reto.ch | Twitter: @retoch

---

From: Steve Lhomme <[email-masked]>
Date: Sun, 25 Sep 2016 17:51:37 +0200

I went ahead and did a new Pull Request with an EBNF based notation to
define the path. I merged the minOccurs/maxOccurs as well as it's
simple enough to add it to the "regular expression" in a way anyone
can understand. Just reading that path line of an element gives you a
quick view of where it is found and how often (including recursively).

https://github.com/Matroska-Org/ebml-specification/pull/106

Now after doing that I realized the XML schema wasn't as easy to parse
as before. Let me know what you think. We may have the EBNF notation
for each element definition in the RFC and the XML definition used
different parts of the EBNF definition in various attributes (likely
the ones we have before).

I struggled a bit to find a way to define the Void properly without
making the EBNF syntax too complex.

I left out more complex recursive possibilities like /a/b(/c/d)+ for
recursion jumping a level. It is not supported by current EBML parsers
and was never considered anyway.

I used the classic EBNF base with concatenation using the "," character.

---

From: Dave Rice <[email-masked]>
Date: Sun, 25 Sep 2016 12:34:33 -0400

Hi,

> On Sep 25, 2016, at 11:51, Steve Lhomme <[email-masked]> wrote:
> 

This looks good though I suggest that we have a mechanism to express a parent without the full path. In xpath '//' is used in this way.

For instance "//Info/MuxingApp" could mean that MuxingApp could be a Child Element of any Info Element. Subsequently Info could be defined only at "/Segment/Info". Through extrapolating one could see that MuxingApp can only be at "/Segment/Info/MuxingApp" without needed the full path.

> I used the classic EBNF base with concatenation using the "," character.

Such as "//Tags/SimpleTag,//SimpleTag/SimpleTag"?

Dave

---

From: Steve Lhomme <[email-masked]>
Date: Sun, 25 Sep 2016 20:22:31 +0200

Le 25 sept. 2016 18:38, "Dave Rice" <[email-masked]> a écrit :
> This looks good though I suggest that we have a mechanism to express a
parent without the full path. In xpath '//' is used in this way.
>
> For instance "//Info/MuxingApp" could mean that MuxingApp could be a
Child Element of any Info Element. Subsequently Info could be defined only
at "/Segment/Info". Through extrapolating one could see that MuxingApp can
only be at "/Segment/Info/MuxingApp" without needed the full path.

We could have something like that but the idea is that part of Matroska or
different EBML formats could be defined elsewhere. It's a lot easier to
understand unambiguously if you have the full path. Also if two formats use
the same name for different things that becomes a problem. You may also
have math formats using X, Y, Z all over the place.

But that should be easy to add an EBMLElementParent in there.

> Such as "//Tags/SimpleTag,//SimpleTag/SimpleTag"?

No. "a", "b" equals "ab".

---

From: Dave Rice <[email-masked]>
Date: Sun, 25 Sep 2016 17:31:37 -0400

Hi,

I finished a review of  https://github.com/Matroska-Org/ebml-specification/pull/106 <https://github.com/Matroska-Org/ebml-specification/pull/106> with many comments there. Overall I like the new version of EBML Path expression based on an EBNF-defined convention.

> On Sep 25, 2016, at 2:22 PM, Steve Lhomme <[email-masked]> wrote:
> Le 25 sept. 2016 18:38, "Dave Rice" <[email-masked] <mailto:[email-masked]>> a écrit :
> >
> > Hi,
> >
> > > On Sep 25, 2016, at 11:51, Steve Lhomme <[email-masked] <mailto:[email-masked]>> wrote:
> > >
> > > https://github.com/Matroska-Org/ebml-specification/pull/106 <https://github.com/Matroska-Org/ebml-specification/pull/106>
> >
> We could have something like that but the idea is that part of Matroska or different EBML formats could be defined elsewhere. It's a lot easier to understand unambiguously if you have the full path. Also if two formats use the same name for different things that becomes a problem. You may also have math formats using X, Y, Z all over the place.
> 
Yes but it could cut some of the semantic redundancy. For instance `Language`, `ChapLanguage`, and `TagLanguage` could be all defined as documenting the language of their Parent Element’s context.

name=“Language”
path="//TrackEntry/Language|//ChapterDisplay/Language|//SimpleTag/Language”

Also in the PR the concepts of minOccur and maxOccur are moved from <element> attributes into the path expression such as “/EBML/EBMLVersion(1,1)”. This makes it a bit more difficult as one would now have to parse the XML and then parse the path. Not a blocking issue, but for tools that will depend on the EBML Schema, parsing out queries such as ‘find all mandatory elements’ or ‘all non-repeating element’ may be more difficult.
> > > 2016-09-25 10:58 GMT+02:00 Reto Kromer <[email-masked] <mailto:[email-masked]>>:
> > >> Steve Lhomme wrote:
> > >>
> > >>> I found the POSIX regex
> > >>> https://en.wikipedia.org/wiki/Regular_expression#Standards <https://en.wikipedia.org/wiki/Regular_expression#Standards>
> > >>
> > >> The formal standard is:
> > >>
> > >>  ISO/IEC/IEEE 9945:2009
> > >> AV Preservation by reto.ch <http://reto.ch/>
> > >> Web: https://reto.ch <https://reto.ch/> | Twitter: @retoch
> > >>
> > >> [email-masked] <mailto:[email-masked]>
> > >> https://www.ietf.org/mailman/listinfo/cellar <https://www.ietf.org/mailman/listinfo/cellar>
> > >
> > >
> > >
> > > --
> > > Steve Lhomme
> > > [email-masked] <mailto:[email-masked]>
> > > https://www.ietf.org/mailman/listinfo/cellar <https://www.ietf.org/mailman/listinfo/cellar>
> >
> 
Dave Rice