Introduction

Daffodil has a module called daffodil-runtime1. The suffix "1" was intentional to suggest that there would be other kinds of Daffodil backends in the future.

The goals of Runtime 1 were to get a correct, complete implementation of DFDL as quickly as possible. Making it as efficient as possible was important, but secondary to completeness and correctness. Other goals including streaming behavior (when the DFDL schema allows it), so that data larger than memory can be parsed/unparsed.

Today there are many parties interested in Daffodil but who have different requirements:

• selective linking or other technique to keep memory footprint small

• C/C++ code generation for non-JVM environments

• native object population - ex: for Java, directly populating POJO objects corresponding to the logical DFDL schema objects. (Akin to how JAXB fills in objects from XML data.)

In many cases these requirements are more important than numerous DFDL language features which are not used by the data formats of interest to these users.

The module daffodil-codegen-c is an additional backend for Daffodil intended to be a first attempt to accommodate some of these needs, and to illustrate how alternative Daffodil backends can be created.

daffodil-codegen-c is a very minimalist system which handles only a tiny subset of DFDL from which it generates C source code for separate compilation and use. The subset of DFDL can increase in size over time, but initially it is intended to be the smallest possible subset that will illustrate how an alternative backend can be constructed.

Daffodil Primary Data Structures

Daffodil is a compiler and runtime. The primary data structures are:

• DSOM - Daffodil Schema Object Model - the Abstract Syntax Tree (AST) of the DFDL schema.
• Gram - The data "Grammar" objects - an intermediate compiler structure to support rule-based, backend-independent optimizations
• Parser/Unparser objects - these are the runtime-specific objects that actually carry out parsing/unparsing.

The current Parser/Unparser objects are specific to daffodil-runtime1.  Introduction of daffodil-codegen-c requires replacing Parser/Unparser above with CodeGenerator. This is an object which is the output of the Daffodil schema compiler and which encapsulates generator-specific optimizations and behavior.  The above list becomes:

• DSOM
• Gram
• Runtime
  • For daffodil-runtime1 - Parser/Unparser objects created by parser() and unparser() methods - these are the runtime-specific objects that actually carry out parsing/unparsing. There are also RuntimeData classes which store information used by parsers/unparsers, and Evaluatable objects which encapsulate compiled expressions for evaluation at runtime.
  • For daffodil-codegen-c - Generator objects generated by the Compiler.forLanguage() method.  Calling their generateCode() method returns a newly created code directory containing C source code for parsing/unparsing a given schema.

The DSOM and Gram layers of the Daffodil schema compiler should be runtime independent.

DSOM - Daffodil Schema Object Model

Daffodil contains a DFDL schema compiler, primarily implemented in the daffodil-core module, and a runtime (currently as of 2019-09-25, daffodil-runtime1).

The schema compiler parses a DFDL schema into a DSOM tree. DSOM is DFDL Schema Object Model. It is a set of classes that directly represent the DFDL schema. It is the abstract syntax tree (AST) of the DFDL schema.

The DSOM tree has numerous members on it which are computed by reference to other parts of the DSOM model. Lazy evaluation is used to avoid the need to compose these into passes.

Nothing computed on the DSOM tree should be in any way specific to any runtime system.

The runtimeData methods (runtimeData, termRuntimeData, modelGroupRuntimeData, ElementRuntimeData, etc.). These methods return RuntimeData objects, which are defined in daffodil-runtime1.

Gram or Grammar Objects

The DFDL specification contains something called the "Data Syntax Grammar". The notion is that data describable by DFDL must be something the data syntax grammar can describe.

Internally to Daffodil there is an object taxonomy rooted at the Gram trait (a Scala trait is much like a Java Interface). The Gram objects implement something that was intended to be a realistic implementation of the data syntax grammar found in the specification, but it has drifted substantially from anything closely related to what is in the DFDL spec. The grammar in the DFDL specification is not suited to actual implementation. As a result, the Gram structures in Daffodil in many places are not structured very much like grammar rules at all.

The Gram objects use techniques similar to Scala’s Parser Combinators and something like guarded-clause logic to implement simple rule-based optimizers.

An important goal for the Gram objects is that the rules and the optimizations they perform are independent of any backend/runtime strategy. That is, they are universal. For example, a data format that does not use any sort of delimiters does not need any Gram objects corresponding to initiators, separators, nor terminators. Hence, all grammar rules associated with those regions of the grammar are folded away and disappear from the effective grammar describing the data format.

As with DSOM, the Gram objects use lazy evaluation to avoid the need to organize the compilation process into passes.

The leaves or terminals of the grammar are implementations of the Terminal class. These are generally called the grammar primitives, and those are where the back-end independent code meets the back-end specific code.

Runtime Objects

The primitives of the grammar are where the schema compiler actually constructs the runtime artifacts.

For daffodil-runtime1, this is done with the parser() and unparser() methods of the grammar primitives. These return runtime1's Parser and Unparser class instances.

For daffodil-codegen-c, the generateCode() method invokes the codegen-c backend to generate the implementation.

To avoid exposing much about the code generator to the schema compiler, the signature of its forLanguage() method returns a CodeGenerator object instantiated via reflection API. The notion is that the CodeGenerator object starts with some initial internal state and builds up declarations and code within it when you call its generateCode() method. Ultimately, the CodeGenerator object ends up with a complete copy of the generated code, writes it out to source files, and returns the directory containing the source files.

DPath - Expressions in the DFDL Path Language

Expression - the DPath Abstract Syntax Tree

Daffodil’s schema compiler (in daffodil-core) also compiles DFDL’s expression language, which we call DPath (for DFDL Path), which is closely related to the standard XPath 2.0 language. We refer to the part of Daffodil’s schema compiler that compiles DPath expressions as the DPath compiler.

The DFDLExpressionParser class is a parser for DPath which parses DPath expressions into an AST of Expression class/trait objects. The AST Expression instances have a compiledDPath member which evaluates into a CompiledDPath object (defined in daffodil-runtime1) containing a sequence of RecipeOp operations (also defined in daffodil-runtime1) which are runtime operations that actually carry out expression evaluation. During this DPath compilation static type analysis is performed.

The DPath compiler attempts to fold constants in expressions by attempting to evaluate expressions at compile time. Expressions that produce values without attempting to parse data are replaced by those constant values. This uses daffodil-runtime1's implementation of DPath in a mode where attempting to access data or attempting to access the runtime infoset tree results in failure and the expression being deemed "not constant".

Even when compiling expressions for different backend runtime implementations of DPath, the constant folding by way of daffodil-runtime1’s implementation of DPath can still be used.

Ultimately, the DPath compiler produces a CompiledExpression object which is implemented either as a ConstantExpression (when constant folding worked), or a RuntimeExpressionDPath object which contains the CompiledDPath.

Code Generator Design

Simplifying Assumptions

DFDL allows conforming subsets of features. The Code Generator subset will be, roughly, the smallest possible conforming subset of DFDL.

The table below is derived from Section 21 of the DFDL specification 1.0, with a third column added specifying the implementation goal for code generation.

Daffodil extensions to DFDL - layering, blob objects, the dfdlx:emptyElementParsePolicy property, additional character sets (hex, octal, bits, and specialty sets), etc. all will not be supported.

Additional characteristics we expect Code Generators to have, which simplify the implementation:

• each parse operation consumes data from an input stream and produces a data structure. This data structure is not produced incrementally, but all at once.

  • Rationale: This eliminates the technological hurdles of streaming-parsing which really are only needed for massively large data objects - large enough that bringing them into memory as an infoset object is problematic.

• each unparse operation consumes one entire fully populated data structure and produces data to an output stream.

  • Rationale: This massively simplifies unparsing by allowing expression evaluation to always assume the entire "infoset" object is already constructed. Expression evaluation never needs to support streaming, that is, be suspended waiting for additional infoset events to arrive.

• I/O is byte-centric

  • data is byte-centric. That is no element can be of size that is not a multiple of bytes long. Alignment is always 1 byte.

  • data can be big or little endian.

  • character sets are all byte-oriented. Their code units are 8 bit bytes minimum.

  • Rationale: This set of constraints insures ordinary C I/O supplies most of the I/O layer natively.

In general, use of unsupported features will cause a compile time SDE.

• Only lengthKind 'explicit' or 'implicit' for simple types, and only lengthKind 'implicit' for complex types.

• Only types boolean, long, int, short, byte, unsignedLong, unsignedInt, unsignedShort, unsignedByte, float, double, hexBinary, and string are supported.

  • Leaves out the decimal, integers greater than 64 bits long, and date/time related types

• The dfdl:representation is always 'binary'. No text numbers are supported.

• As the dfdl:binaryNumberRep is always 'binary', integers are fixed-length 2’s complement.

• When added, note that occursCountKind="expression", and choices with only dfdl:choiceDispatchKey and dfdl:choiceBranchKey implies no backtracking/discrimination is required.

  • Rationale: This and requiring only dfdl:occursCountKind='expression' means there are no points of uncertainty, so there is no backtracking.

A large number of DFDL properties are going to be required to be defined, but if they do not have the correct value that is supported by the implementation it will be an SDE.

Properties that end up needed but shouldn't be - ex: anything about text numbers, anything about date/time - are bugs in Daffodil that should be reported. An include-file DFDL format definition should hide these from users, so they are not distracting.

Phases

The above restrictions on the features suggest dividing up the implementation of Code Generators into 2 distinct phases:

• Phase 1: No expressions. All lengths are fixed. All arrays have fixed length.
• Phase 2: Adding the DFDL expression language, lengthKind 'explicit', occursCountKind 'expression'.

Goals

• Initial focus is a backend where the Infoset is composed from C struct definitions. The C struct definitions are part of the generated code, which is output as one or multiple text files.

• DPath expressions (when implemented) compile into C language expressions that navigate Infoset structs the way handwritten code would.

• The amount of runtime-library code should produce a minimum footprint.

Random Implementation Notes

• ParseError and UnparseError must be supported. Both are always fatal as there are no points-of-uncertainty/backtracking.

• RuntimeSDE ??

  • TBD: Can runtime SDEs occur? We may have eliminated all possibilities for them.

• PState and UState (state of parser/unparser) and mutable data structures reachable from them are thread specific. All other data structures are shared across threads and immutable or thread-safe.

• TDML-style tests should be easily created.