Edit comment LC-2187 for Efficient Extensible Interchange Working Group

Quick access to LC-2103 LC-2104 LC-2105 LC-2106 LC-2107 LC-2108 LC-2109 LC-2110 LC-2130 LC-2132 LC-2133 LC-2164 LC-2165 LC-2166 LC-2167 LC-2168 LC-2169 LC-2170 LC-2171 LC-2172 LC-2173 LC-2174 LC-2175 LC-2176 LC-2177 LC-2178 LC-2179 LC-2180 LC-2181 LC-2182 LC-2183 LC-2184 LC-2185 LC-2186 LC-2187 LC-2188 LC-2189 LC-2190 LC-2191 LC-2192 LC-2193 LC-2194 LC-2196 LC-2197 LC-2198 LC-2227 LC-2248

Comment LC-2187

Comment Shortname:

Commenter: TAMIYA Keisuke <tamiya.keisuke@canon.co.jp>

Message-id:

Section of the document concerned:

[Free text description]Document as a wholeEfficient XML Interchange (EXI) Format 1.0 /**/ code... Efficient XML Interchange (EXI) Format 1.0 W3C Working Draft 28 July 2008 Abstract Status of this Document Table of Contents Appendices 1. Introduction [Definition:]   [Definition:]   [Definition:]   1.1 History and Design 1.2 Notational Conventions and Terminology [Definition:]   2. Design Principles 3. Basic Concepts 4. EXI Streams [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   4. EXI Streams [Definition:]  An EXI stream is an EXI heade... 4. EXI Streams [Definition:]  An EXI stream is an EXI heade... name prefix local-element-ns public qname system text uri value 5. EXI Header [Definition:]   5.1 EXI Cookie [Definition:]   5.2 Distinguishing Bits [Definition:]   5.3 EXI Format Version [Definition:]   Example 5-1. EXI Format Version Examples 5.4 EXI Options [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   [Definition:]   6. Encoding EXI Streams [Definition:]   6.1 Determining Event Codes Example 6-1. Example productions with event codes 6.2 Representing Event Codes Example 6-2. Example event code encoding 6.3 Fidelity Options Preserve.prefixes Preserve.lexicalValues 7. Representing Event Content [Definition:]   7. Representing Event Content The content of each event in... 7. Representing Event Content The content of each event in... 7.1 Built-in EXI Datatype Representations 7.1.1 Binary 7.1.2 Boolean 7.1.3 Decimal 7.1.4 Float 7.1.5 Integer 7.1.6 Unsigned Integer Example 7-1. Example algorithm for decoding an Unsigned Inte... 7.1.7 QName 7.1.8 Date-Time 7.1.9 n-bit Unsigned Integer 7.1.10 String 7.1.10.1 Restricted Character Sets 7.1.11 List 7.2 Enumerations 7.3 String Table 7.3.1 String Table Partitions [Definition:]   7.3.2 Partitions Optimized for Frequent use of Compact Identifiers 7.3.3 Partitions Optimized for Frequent use of String Literals 7.4 Datatype Representation Map [Definition:]   Example 7-2. datatypeRepresentationMap indicating all Decima... Example 7-3. datatypeRepresentationMap illustrating a user-d... 8. EXI Grammars 8.1 Grammar Notation 8.1.1 Fixed Event Codes Example 8-1. Example productions with fixed event codes 8.1.2 Variable Event Codes Example 8-2. Example productions that use macro non-terminal... Example 8-3. Example non-terminal macros and its productions... Example 8-4. Expanded productions equivalent to the producti... 8.2 Grammar Event Codes Example 8-5. Example productions with event codes 8.3 Pruning Unneeded Productions Example 8-6. Example productions with full fidelity Example 8-7. Example productions after pruning 8.4 Built-in XML Grammars 8.4.1 Built-in Document Grammar 8.4.2 Built-in Fragment Grammar 8.4.3 Built-in Element Grammar [Definition:]   8.5 Schema-informed Grammars 8.5.1 Schema-informed Document Grammar 8.5.2 Schema-informed Fragment Grammar 8.5.3 Schema-informed Element Fragment Grammar 8.5.4 Schema-informed Element and Type Grammars [Definition:]   [Definition:]   8.5.4.1 EXI Proto-Grammars 8.5.4.1.1 Grammar Concatenation Operator 8.5.4.1.2 Element Grammars 8.5.4.1.3 Type Grammars 8.5.4.1.3.1 SimpleType Grammars 8.5.4.1.3.2 Complex Type Grammars 8.5.4.1.3.3 Complex Ur-Type Grammar 8.5.4.1.4 Attribute Uses 8.5.4.1.5 Particles 8.5.4.1.6 Element Terms 8.5.4.1.7 Wildcard Terms 8.5.4.1.8 Model Group Terms 8.5.4.1.8.1 Sequence Model Groups 8.5.4.1.8.2 Choice Model Groups 8.5.4.1.8.3 All Model Groups 8.5.4.2 EXI Normalized Grammars 8.5.4.2.1 Eliminating Productions with no Terminal Symbol 8.5.4.2.2 Eliminating Duplicate Terminal Symbols 8.5.4.3 Event Code Assignment 8.5.4.4 Undeclared Productions 8.5.4.4.1 Adding Productions when Strict is False Like an element, an attribute may occur in a schema-invalid... 8.5.4.4.2 Adding Productions when Strict is True 9. EXI Compression 9.1 Blocks 9.2 Channels 9.2.1 Structure Channel 9.2.2 Value Channels 9.3 Compressed Streams 10. Conformance 10.1 EXI Stream Conformance [Definition:]   [Definition:]   [Definition:]   10.2 EXI Processor Conformance A References A.1 Normative References IETF RFC 1951 IETF RFC 2119 ISO/IEC 10646 Unicode Database XML 1.0 XML Information Set XML Schema Structures XML Schema Datatypes A.2 Other References Efficient XML EXI Measurements Note EXI Primer EXI Evaluation Greibach Normal Form Huffman Coding ISO/IEC 19757-2:2003 SOAP 1.2 XBC Measurement Methodologies XBC Use Cases XBC Properties B Infoset Mapping B.1 Document Information Item B.2 Element Information Items B.3 Attribute Information Item B.4 Processing Instruction Information Item B.5 Unexpanded Entity Reference Information item B.6 Character Information item B.7 Comment Information item B.8 Document Type Declaration Information item B.9 Unparsed Entity Information Item B.10 Notation Information Item B.11 Namespace Information Item C XML Schema for EXI Options Header D Initial Entries in String Table Partitions D.1 Initial Entries in Uri Partition D.2 Initial Entries in Prefix Partitions D.3 Initial Entries in Local-Name Partitions E Deriving Character Sets from XML Schema Regular Expressions E Deriving Character Sets from XML Schema Regular Expressio... F Example Encoding (Non-Normative) G Schema-informed Grammar Examples (Non-Normative) Example G-1. Example XML Schema fragment G.1 Proto-Grammar Examples   Term_description   Term_description 0 :...   Term_description   Term_description 0 :...   Term_description   Term_description 0 :...   Particle_description   Term_description ...   Particle_quantity   Term_quantity 0 :...   Particle_quantity   Term_quantity 0 :...   Term_sequence   Term_description0 :...   Particle_sequence   Term_description0,0...   Use_sku   Use_sku 0 : AT("sku") Use_...   Use_sku   Use_sku 0 : AT("sku") Use_...   ProtoG_ProductElement   Use_color 0 :...   ProtoG_OrderElement   Term_prod... G.2 Normalized Grammar Examples   NormG_ProductElement Event Code Use_col...   NormG_ProductElement Event Code Use_col... G.3 Complete Grammar Examples   CompleteG_ProductElement Event Code Use...   CompleteG_ProductElement Event Code Use... H Recent Specification Changes (Non-Normative) H.1 Changes from Third Public Working Draft H.2 Changes from Second Public Working Draft H.3 Changes from First Public Working Draft I Acknowledgements (Non-Normative)
or

Refinement of the section concerned:

Status:

open proposal pending resolved_yes resolved_no resolved_partial other assigned to Nobody Bournez, Carine Brutzman, Don Cokus, Michael Fernández, Javier D. Heuer, Joerg Käbisch, Sebastian Kamiya, Takuki Kuntschke, Richard Matsukura, Ryuichi McGregor, Don Peintner, Daniel Quin, Liam Shah, Grishma ZERGAOUI, Mohamed

Type: substantive editorial typo question general comment undefined

Resolution status:

Response drafted Resolution implemented Reply sent to commenter

Response status:

No response from Commenter yet Commenter approved disposition Commenter objected to disposition
Commenter's response (URI):

Comment:

EXI has a mechanism of the grammer leaning (ref. Section 8).
So, an EXI parser use large memory to keep grammar data, if the XML data
has many kinds of node (ex. element).
For small devices, this is a serious problem.
I think the limitation mechanism of the grammar learning is needed in
the specification (ex. MAX number of the kind of event code).

Related issues: (space separated ids)

WG Notes:

Resolution: We understand the concern you have raised over the issue grammar learning behaviour may pose on the size of memory EXI processor consumes and requires. While acknowledging it is a potential issue, we had stopped short of adding a mechanism to restrain grammar learning at the time we dicussed the feature a while back, based on implementation report of the feature shared by the WG memebers, which suggested otherwise that the issue did not surface in real deployments. One of the traits that documents for use in exchange in general is that grammars are learned a lot up front at a pace close to linear rate, and the learning becomes less and less frequent, eventually saturating to a convergence. This observation helps explain why the issue is not very likely to emerge in practice. Based on these observation and analysis, as well as the consideration of the cost that would otherwise be incurred if a restraining mechanism was introduced both in terms of compactness and runtime efficiency, we stay cautious and may require further arguments involving specific use cases before we consider a way to alleviate the potential issue.

(Please make sure the resolution is adapted for public consumption)