mbeckerle commented on a change in pull request #17: Design notes on schema compiler space/speed issue URL: https://github.com/apache/incubator-daffodil-site/pull/17#discussion_r376111928
########## File path: site/dev/design-notes/term-sharing-in-schema-compiler.adoc ########## @@ -0,0 +1,562 @@ +:page-layout: page +:keywords: schema-compiler performance alignment optimization +// /////////////////////////////////////////////////////////////////////////// +// +// This file is written in AsciiDoc. +// +// If you can read this comment, your browser is not rendering asciidoc automatically. +// +// You need to install the asciidoc plugin to Chrome or Firefox +// so that this page will be properly rendered for your viewing pleasure. +// +// You can get the plugins by searching the web for 'asciidoc plugin' +// +// You will want to change plugin settings to enable diagrams (they're off by default.) +// +// You need to view this page with Chrome or Firefox. +// +// /////////////////////////////////////////////////////////////////////////// +// +// When editing, please start each sentence on a new line. +// See https://asciidoctor.org/docs/asciidoc-recommended-practices/#one-sentence-per-line[one sentence-per-line writing technique.] +// It is acceptable to start each sentence on a new line, but then wrap the lines to a reasonable length. +// It's the starting on a new line that matters. +// +// This makes textual diffs of this file useful in a similar way to the way they work for code. +// +// ////////////////////////////////////////////////////////////////////////// + +== Term Sharing in the Schema Compiler + +=== Introduction + +The DFDL language has a composition property known as _referential transparency_. +It is not supposed to matter whether you lift a part of the schema out +and create a reusable group, reusable type, or reusable element from +it. + +Because DFDL (version 1.0) does not allow recursive definitions of any +kind, it is theoretically possible to implement this by treating all +reusable definitions in the language like macros. +I.e., inline-expand all definitions at their point of use. +This will work for schemas up to some size. However, it leads to an +unacceptable expansion in schema compilation time and space, as the +size of the schema once all these inline substitutions have been +performed can be exponentially larger than the original +non-substituted schema. + +To avoid this undesirable combinatorial explosion, the Daffodil schema +compiler arranges to achieve the same macro-like semantics, while +still sharing the core parts of the reusable components so they need +only be compiled once for each unique way the component is used. + +This is also part of eventually enabling an extension of the DFDL +language to allow recursive definitions. + +The dfdl:alignment property is one of the largest contributors to +complexity in sharing objects by the schema compiler. + +Alignment will be used as the example in this design note to +illustrate the schema compiler behavior. + +=== DSOM Term Objects + +DSOM is the Daffodil Schema Object Model. +Within this model, the entities from a DFDL schema that actually have +representations in the data stream are called _terms_ and they are +represented by the subclasses of the class Term. +There are terms which have no representation at all such as computed elements. + +For this discussion we are concerned only with terms that have representation. + +The classes in Daffodil that are used for concrete terms are: + +* ElementRef +* Root (A degenerate element ref to the root element) +* LocalElementDecl +* the quasi-elements: + +** PrefixLengthQuasiElementDecl (Fake local element decl used for the + length fields of Prefixed-length types) + +** RepTypeQuasiElementDecl (Fake local element decl used as the + representation of elements that are computed via the dfdl:repType + mechanism.) + +* Sequence +* SequenceGroupRef + +* ChoiceBranchImpliedSequence (The sequence that is inserted when a + choice branch is a single element decl/ref) + +* Choice +* ChoiceGroupRef + +=== Term Representation Regions + +Consider the representation of a term, which we call the term's +_region_, as appearing between two other term regions in the data +stream as illustrated below: + +[ditaa] +.... +---+ +-----------------------------------------------+ +--- + | | term | | + | | | | + | | +---------------+ +--------+ +--------------+ | | +...| | | unique before | | shared | | shared after | | |... + | | +---------------+ +--------+ +--------------+ | | + --+ +-----------------------------------------------+ +-- +.... +In the above, lower position bits are to the left. +Higher position bits to the right. +In the diagram, we see that the term's region consists of 3 +sub-regions, named _unique before_, _shared_, and _shared after_. Each +term appears in a context of possible additional terms before it and +after it which are shown with ellipsis above. + +A term can be an element or a model-group (sequence or choice). +By far the most common situation is that a term appears inside a model group. +There are two exceptions. The _root_, and the model-group of a complex type. + +The core idea here is that we are separating the representation of a +term into unique and shared parts. +The unique region is affected by the surrounding model group context. +The shared regions are, in many cases, sharable across instances of +this term and is independent of the surrounding model-group context. +So if the term was defined by way of a reusable global definition, +then the goal is that there need be only one implementation of the +shared part(s). + +There are some limits to this sharing. +A single implementation is not always achievable, but generally one or +a small number of implementations are possible. + +=== Limits to Sharing + +Consider if this term above was defined by way of a XSD group +reference. +The DFDL properties expressed on the group reference must +be combined with those expressed on the group definition, to form the +complete set of properties associated with the term. +This combining creates situations where a given shared group definition can have +wildly different representations for different uses. +Consider this: + +```xml +<group name="g"> + <sequence> + <element name="a" type="xs:int"/> + <element name="b" type="xs:int"/> + <element name="c" type="xs:int"/> + </sequence> +</group> + +.... + +<element name="e"> + <complexType> + <sequence> + ... some stuff here ... + <group ref="tns:g" dfdl:separator="|"/> <!-- separated --> + ... more stuff here ... + <group ref="tns:g"/> <!-- not separated --> + ... yet more stuff here ... + </sequence> + </complexType> +</element> +``` + +The two uses of the group definition for 'g' are wildly different, in +that one has separators, the other does not. + +This is a rather extreme example, but DFDL implementations must allow +for this. + +Experience with DFDL schemas to-date (2020-01-21) is that this is very +rare and appears only in test cases designed to exercise it. +However, less extreme versions of this are possible, such as different +uses all being separated and delimited textual data, but where the +distinct uses do not all use the same separator characters, so the +separator to be used would be specified differently on each group +reference. Another expected variation could be separated sequence +groups where some uses are infix separator and others are prefix or +postfix separator. + +Anecdotally, the vast majority of schemas seen to-date reuse groups +entirely, that is specifying no properties at all on the group +reference. + +==== Property Environment or PropEnv + +We define the _property environment_ or _PropEnv_ of a term, as the +complete set of properties for that term, combining them from all the +schema components that define the term. This can include element +references, group references, local or global element declarations, +global group definitions, and local and global type definitions. + +A key observation is that the PropEnv of a term is entirely defined by: + +* local properties (including any dfdl:ref property) on the schema component for the term. +** E.g., for an element reference, the local properties expressed on the element reference itself. +* default format object at top level of the schema where the term lexically appears. +* definition object being referenced. +** E.g., for an element reference, the global element declaration being referenced. + +So if two terms, say group references, have the same PropEnv, then we +can share much about their definitions when implementing them. + +Hence, when constructing the Daffodil schema compiler's representation +for a term, we can maintain a cache for each global definition, with +the key of the cache being the PropEnv. +When a given term uses a global definition, if the point of use has +the same PropEnv as another, both can share the part of the term that +is context independent, that is, the shared region. + +The actual components of the PropEnv of a term are slighly more +complicated than described above. +The table below gives the components of the PropEnv for the various +kinds of terms. Note that the "local properties" below includes any +dfdl:ref property if it appears, but equality of any property which +has as its value a QName, like dfdl:ref, the property value is based +on a resolved QName, not the QName string. + +[cols="2,6a"] +.PropEnv Components +|=== +|Term Definition (one PropEnv subtype per) | PropEnv Components + +|Local Element Decl with type reference +| +* Local properties expressed on the Local Element Decl (Set of property name + value pairs) +* Lexically enclosing default format (object ref) +* Type definition (object ref) or primitive type (object ref) +| Local Element Decl with anonymous Simple Type Definition +| +* Combined set of local properties expressed on the Local Element Decl and the anoymous Simple Type definition. +* Lexically enclosing default format (object ref) +* Base simple type definition (object ref), or primitive type (object ref) +|Local Element Decl with anonymous complex type definition +| +* Local properties expressed on the local element decl +* Lexically enclosing default format (object ref) +* Anonymous complex type (object ref) +|Element Reference to Global Element Decl +| +* Local properties expressed on the element reference +* Lexically enclosing default format (object ref) +* Global Element Decl (object ref) +|=== + +Lookups by PropEnv compare sets by equality of members, and object +references by pointer equality i.e, eq comparison. + +This definition of PropEnv can be improved by memoizing the +construction of default format objects, so that equivalent default +formats from different schema documents are represented by the same +object. +That is, so that multiple schema documents each containing: +```xml + <dfdl:format ref="prefix:formatName"/> +``` +are instantiated as the same object when the QName resolves to the same format object. + +==== Details of Unique and Shared Regions + +The division of the reprsentation into the unique part which appears +before the shared parts indicates where we can share implementation, +and where we must have unique context-specific implementation for the +term. + +To understand this better, the below breaks down the sub-regions of a term further: + +[ditaa] +.... +----+ +------------------------------------------------------------------------------+ +------+ +---------------------------------------------------+ +---- + | | +-------------------+ unique before | |shared| | shared after +---------------------+ | | + | | | sequence before | | | | | | sequence after | | | + | | | +------+ +------+ | +-----+ +---------+ +------+ +------+ +------+ +-----+ | | | | +------+ +------+ +-----+ | +-------+ +-------+ | | | + | | | |prefix| |prefix| | |lSkip| |alignFill| |init'r| |init'r| |prefix| +value| | | | | |term'r| |term'r| |tSkip| | |postfix| |postfix| | | | + | | | |infix | |infix | | | | | | | MTA | | | |length| | MTA | | | | | | MTA | | | | | | | sep'r | | sep'r | | | | + | | | |sep'r | |sep'r | | | | | | | | | | | | | | | | | | | | | | | | | | MTA | | | | | | +... | | | | MTA | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |... + | | | +------+ +------+ | +-----+ +---------+ +------+ +------+ +------+ +-----+ | | | | +------+ +------+ +-----+ | +-------+ +-------+ | | | + | | +-------------------+ | | | | +---------------------+ | | +----+ +------------------------------------------------------------------------------+ +------+ +---------------------------------------------------+ +---- + + ^ + | + | + + + Known Alignment Point + +.... + +The central idea here is that all the regions to the left (before) the known alignment point are context dependent. +That is, whether these alignment fill and mandatory text alignment regions can be statically determined +in size is dependent on where the prior term ended. + +In contrast, the known alignment point is a fresh start for alignment. The alignment as required by the alignment properties Review comment: This doesn't have exactly macro semantics then. (Brandon's observation). The difference is super subtle and involves the interior-alignment problem and won't be detectable except when unparsing. Add description. ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected] With regards, Apache Git Services
