RFC 4911
Encoding Instructions for the Robust XML Encoding Rules (RXER)
RFC 4911 ✨ Encoding Instructions for the Robust XML Encoding Rules (RXER)
okay bestie, RFC 4911 is here and it's giving experimental era 🧪. It's from the Network Working Group, and the document number is RFC 4911. S. Legg from eB2Bcom wrote it, it's in the Experimental category, and it's dated July 2007 📅. The title block has no "Obsoletes" or "Updates" line, so this one doesn't replace or change any other RFC 🦋.
Status of This Memo 🎀
This memo defines an Experimental Protocol for the Internet community. It is not an Internet standard of any kind. The authors want discussion and suggestions for improvement, and anyone can distribute the memo freely (unlimited distribution) 💌.
Copyright Notice 🌸
Copyright (C) The IETF Trust (2007).
Abstract 💜
okay so this doc defines encoding instructions you can drop into an ASN.1 spec 💅. They change how ASN.1 values get encoded by the Robust XML Encoding Rules (RXER) and the Canonical Robust XML Encoding Rules (CRXER). The big example is turning a component of an ASN.1 value into an XML attribute instead of a child element 🫶. Some of these instructions also change how an ASN.1 spec gets translated into an Abstract Syntax Notation X (ASN.X) spec. And on top of that, there are instructions that let your ASN.1 spec point at definitions written in other XML schema languages ✨.
Table of Contents 🧚
1. Introduction ....................................................3
2. Conventions .....................................................3
3. Definitions .....................................................4
4. Notation for RXER Encoding Instructions .........................4
5. Component Encoding Instructions .................................6
6. Reference Encoding Instructions .................................8
7. Expanded Names of Components ...................................10
8. The ATTRIBUTE Encoding Instruction .............................11
9. The ATTRIBUTE-REF Encoding Instruction .........................12
10. The COMPONENT-REF Encoding Instruction ........................13
11. The ELEMENT-REF Encoding Instruction ..........................16
12. The LIST Encoding Instruction .................................17
13. The NAME Encoding Instruction .................................19
14. The REF-AS-ELEMENT Encoding Instruction .......................19
15. The REF-AS-TYPE Encoding Instruction ..........................20
16. The SCHEMA-IDENTITY Encoding Instruction ......................22
17. The SIMPLE-CONTENT Encoding Instruction .......................22
18. The TARGET-NAMESPACE Encoding Instruction .....................23
19. The TYPE-AS-VERSION Encoding Instruction ......................24
20. The TYPE-REF Encoding Instruction .............................25
21. The UNION Encoding Instruction ................................26
22. The VALUES Encoding Instruction ...............................27
23. Insertion Encoding Instructions ...............................29
24. The VERSION-INDICATOR Encoding Instruction ....................32
25. The GROUP Encoding Instruction ................................34
25.1. Unambiguous Encodings ....................................36
25.1.1. Grammar Construction ..............................37
25.1.2. Unique Component Attribution ......................47
25.1.3. Deterministic Grammars ............................52
25.1.4. Attributes in Unknown Extensions ..................54
26. Security Considerations .......................................56
27. References ....................................................56
27.1. Normative References .....................................56
27.2. Informative References ...................................57
Appendix A. GROUP Encoding Instruction Examples ...................58
Appendix B. Insertion Encoding Instruction Examples ...............74
Appendix C. Extension and Versioning Examples .....................871. Introduction ✨
so this doc defines encoding instructions [X.680-1] that you can use in an Abstract Syntax Notation One (ASN.1) [X.680] spec to change how ASN.1 values get encoded by the Robust XML Encoding Rules (RXER) [RXER] and the Canonical Robust XML Encoding Rules (CRXER) [RXER] 💖. The classic example is encoding a component of an ASN.1 value as an Extensible Markup Language (XML) [XML10] attribute rather than a child element 🌈. Some of these instructions also affect how an ASN.1 spec gets translated into an Abstract Syntax Notation X (ASN.X) spec [ASN.X] 🎀.
It also defines encoding instructions that let an ASN.1 spec pull in the definitions of types, elements, and attributes from specs written in other XML schema languages 🦋. That covers XML Schema [XSD1] types, elements, and attributes, RELAX NG [RNG] named patterns and elements, and XML document type definition (DTD) [XML10] element types 💅.
Most of the time, this document only briefly mentions what an encoding instruction does 🧠. The full, precise details live in the RXER [RXER] and ASN.X [ASN.X] specs, at the spots where each instruction applies 🔥.
2. Conventions 💅
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED" and "MAY" in this document are to be interpreted as described in BCP 14, RFC 2119 [BCP14] 🫶. The key word "OPTIONAL" is used only with its ASN.1 meaning 🌸.
Throughout this document, "type" shall be taken to mean an ASN.1 type, and "value" shall be taken to mean an ASN.1 abstract value, unless it's qualified otherwise 💜.
A reference to an ASN.1 production [X.680] (for example, Type or NamedType) is a reference to the text in an ASN.1 spec that matches that production ✨. Across this document, "component" is just another name for NamedType 🧚.
This document uses the namespace prefix xsi: to stand for the namespace name [XMLNS10] http://www.w3.org/2001/XMLSchema-instance 🌷.
Example ASN.1 definitions in this document are assumed to live in an ASN.1 module with a TagDefault of AUTOMATIC TAGS and an EncodingReferenceDefault [X.680-1] of RXER INSTRUCTIONS 🍓.
3. Definitions 🌟
Here's the definition of base type. A bunch of encoding instructions rely on it 💖.
Definition (base type): If a type, T, is a constrained type, then the base type of T is the base type of the type that is constrained. Else, if T is a prefixed type, then the base type of T is the base type of the type that is prefixed. Else, if T is a type notation that references or denotes another type (that is, DefinedType, ObjectClassFieldType, SelectionType, TypeFromObject, or ValueSetFromObjects), then the base type of T is the base type of the type that is referenced or denoted. Otherwise, the base type of T is T itself 🫧.
Aside: A tagged type is a special case of a prefixed type 🏷️.
4. Notation for RXER Encoding Instructions 🦋
The ASN.1 grammar lets you apply encoding instructions [X.680-1] through type prefixes and encoding control sections. Those change how abstract values get encoded by whichever encoding rules you name 💌.
The generic notation for type prefixes and encoding control sections comes from the ASN.1 basic notation [X.680] [X.680-1]. It includes an encoding reference that says which encoding rules the instruction affects 🎀.
The encoding reference that identifies the Robust XML Encoding Rules is literally RXER. An RXER encoding instruction applies to both RXER and CRXER encodings, equally 👑.
The notation for an instruction under a particular set of encoding rules is left to the spec for those rules. So this companion document to the RXER spec [RXER] defines the notation for RXER encoding instructions. Specifically, it fleshes out the EncodingInstruction and EncodingInstructionAssignmentList placeholder productions from the ASN.1 basic notation 🧁.
In the RXER encoding reference context, the EncodingInstruction production is defined like this, using the ASN.1 basic notation conventions 🪄:
EncodingInstruction ::=
AttributeInstruction |
AttributeRefInstruction |
ComponentRefInstruction |
ElementRefInstruction |
GroupInstruction |
InsertionsInstruction |
ListInstruction |
NameInstruction |
RefAsElementInstruction |
RefAsTypeInstruction |
SimpleContentInstruction |
TypeAsVersionInstruction |
TypeRefInstruction |
UnionInstruction |
ValuesInstruction |
VersionIndicatorInstructionAlso in the RXER encoding reference context, the EncodingInstructionAssignmentList production (which only shows up in an encoding control section) is defined like this 🌈:
EncodingInstructionAssignmentList ::=
SchemaIdentityInstruction ?
TargetNamespaceInstruction ?
TopLevelComponents ?
TopLevelComponents ::= TopLevelComponent TopLevelComponents ?
TopLevelComponent ::= "COMPONENT" NamedTypeDefinition (top-level NamedType): A NamedType is a top-level NamedType (or, put another way, a top-level component) if and only if it's the NamedType inside a TopLevelComponent. A NamedType nested inside the Type of the NamedType of a TopLevelComponent is not itself a top-level NamedType 🧩.
Aside: Spec writers, take note: non-trivial types defined within a top-level NamedType won't be visible to ASN.1 tools that don't understand RXER 👀.
Even though a top-level NamedType only shows up in an RXER encoding control section, the module's default encoding reference [X.680-1] still applies when you parse a top-level NamedType 🫶.
Each top-level NamedType within a module SHALL have a distinct identifier 💖.
The NamedType production comes straight from the ASN.1 basic notation. The other productions get described in later sections and use these ones 🌸:
NCNameValue ::= Value
AnyURIValue ::= Value
QNameValue ::= Value
NameValue ::= ValueThe Value production comes from the ASN.1 basic notation too 🍓.
The governing type for the Value in an NCNameValue is the NCName type from the AdditionalBasicDefinitions module [RXER] ✨.
The governing type for the Value in an AnyURIValue is the AnyURI type from the AdditionalBasicDefinitions module 🌷.
The governing type for the Value in a QNameValue is the QName type from the AdditionalBasicDefinitions module 🧚.
The governing type for the Value in a NameValue is the Name type from the AdditionalBasicDefinitions module 🎀.
The Value in an NCNameValue, AnyURIValue, QNameValue, or NameValue SHALL NOT be a DummyReference [X.683], and it SHALL NOT textually contain a nested DummyReference 🚫.
Aside: So encoding instructions can't be parameterized in any way. This restriction is going to matter if a future ASN.X spec explicitly represents parameterized definitions and parameterized references, instead of expanding out parameterized references the way the current spec does. A parameterized definition couldn't be translated directly into ASN.X if it contained encoding instructions that weren't fully specified 😭.
Next up: Section 5, the Component Encoding Instructions 🦋💖
5. Component Encoding Instructions ✨
okay so some of the RXER encoding instructions are the component encoding instructions 💅 bestie, these are ATTRIBUTE, ATTRIBUTE-REF, COMPONENT-REF, GROUP, ELEMENT-REF, NAME, REF-AS-ELEMENT, SIMPLE-CONTENT, TYPE-AS-VERSION, and VERSION-INDICATOR. Their notations are AttributeInstruction, AttributeRefInstruction, ComponentRefInstruction, GroupInstruction, ElementRefInstruction, NameInstruction, RefAsElementInstruction, SimpleContentInstruction, TypeAsVersionInstruction, and VersionIndicatorInstruction 🦋
the Type inside the EncodingPrefixedType for a component encoding instruction SHALL be one of these:
- (1) the Type in a NamedType, or
- (2) the Type in an EncodingPrefixedType in a PrefixedType in a BuiltinType in a Type that is one of (1) to (4), or
- (3) the Type in a TaggedType in a PrefixedType in a BuiltinType in a Type that is one of (1) to (4), or
- (4) the Type in a ConstrainedType (excluding a TypeWithConstraint) in a Type that is one of (1) to (4).
Aside: this basically forces the component encoding instructions to sit textually inside the NamedType they apply to 🎀 Only case (2) can be true on the first pass, since the Type belongs to an EncodingPrefixedType. After that, any of (1) to (4) can be true on later passes 🌸
Case (4) is NOT permitted when the encoding instruction is ATTRIBUTE-REF, COMPONENT-REF, ELEMENT-REF, or REF-AS-ELEMENT 🙈
A NamedType in case (1) is called "subject to" the component encoding instruction 🧚
A top-level NamedType SHALL NOT be subject to an ATTRIBUTE-REF, COMPONENT-REF, GROUP, ELEMENT-REF, REF-AS-ELEMENT, or SIMPLE-CONTENT encoding instruction 💀
Aside: this doesn't stop these instructions from being used on a nested NamedType 💖
A NamedType SHALL NOT be subject to two or more component encoding instructions of the same kind. For example, a NamedType isn't allowed to be subject to two NAME encoding instructions 🙅♀️
The ATTRIBUTE, ATTRIBUTE-REF, COMPONENT-REF, GROUP, ELEMENT-REF, REF-AS-ELEMENT, SIMPLE-CONTENT, and TYPE-AS-VERSION encoding instructions are mutually exclusive 🔥 The NAME, ATTRIBUTE-REF, COMPONENT-REF, ELEMENT-REF, and REF-AS-ELEMENT encoding instructions are also mutually exclusive with each other 🦋 A NamedType SHALL NOT be subject to two or more encoding instructions that are mutually exclusive ✨
A SelectionType [X.680] SHALL NOT be used to select the Type from a NamedType that is subject to an ATTRIBUTE-REF, COMPONENT-REF, ELEMENT-REF, or REF-AS-ELEMENT encoding instruction 👑 The other component encoding instructions are not inherited by the type a SelectionType points to 💅
Definition (attribute component): an attribute component is a NamedType that is subject to an ATTRIBUTE or ATTRIBUTE-REF encoding instruction, or a NamedType subject to a COMPONENT-REF encoding instruction that references a top-level NamedType which is subject to an ATTRIBUTE encoding instruction 🌈
Definition (element component): an element component is a NamedType that is not subject to an ATTRIBUTE, ATTRIBUTE-REF, GROUP, or SIMPLE-CONTENT encoding instruction, and is also not subject to a COMPONENT-REF encoding instruction that references a top-level NamedType which is subject to an ATTRIBUTE encoding instruction 🍓
Aside: a NamedType subject to a GROUP or SIMPLE-CONTENT encoding instruction is neither an attribute component nor an element component 🫶
6. Reference Encoding Instructions 🦋
so some RXER encoding instructions are the reference encoding instructions 🌸 These are ATTRIBUTE-REF, COMPONENT-REF, ELEMENT-REF, REF-AS-ELEMENT, REF-AS-TYPE, and TYPE-REF. Their notations are AttributeRefInstruction, ComponentRefInstruction, ElementRefInstruction, RefAsElementInstruction, RefAsTypeInstruction, and TypeRefInstruction 🧚 Except for COMPONENT-REF, these let an ASN.1 spec pull in definitions of types, elements, and attributes from specs written in other XML schema languages. It works through implied constraints on the markup that can show up in values of the Markup ASN.1 type from the AdditionalBasicDefinitions module [RXER] (for ELEMENT-REF, REF-AS-ELEMENT, REF-AS-TYPE, and TYPE-REF), or the UTF8String type (for ATTRIBUTE-REF) ✨ References to XML Schema [XSD1] types, elements, and attributes are supported, and so are RELAX NG [RNG] named patterns and elements, plus XML document type definition (DTD) [XML10] element types 💖 References to ASN.1 types and top-level components are allowed too. COMPONENT-REF is the more direct way to reference a top-level component 🎀
The Type in the EncodingPrefixedType for an ELEMENT-REF, REF-AS-ELEMENT, REF-AS-TYPE, or TYPE-REF encoding instruction SHALL be one of these:
- (1) a ReferencedType that is a DefinedType that is a typereference (not a DummyReference) or an ExternalTypeReference that references the Markup ASN.1 type from the AdditionalBasicDefinitions module [RXER], or
- (2) a BuiltinType that is a PrefixedType that is a TaggedType where the Type in the TaggedType is one of (1) to (3), or
- (3) a BuiltinType that is a PrefixedType that is an EncodingPrefixedType where the Type in the EncodingPrefixedType is one of (1) to (3) and the EncodingPrefix in the EncodingPrefixedType does not contain a reference encoding instruction.
Aside: case (3), and similar cases for ATTRIBUTE-REF and COMPONENT-REF, have the effect of making the reference encoding instructions mutually exclusive AND singly occurring 🙈
For REF-AS-TYPE and TYPE-REF, the DefinedType in case (1) is called "subject to" the encoding instruction 🧚
The restrictions on the Type in the EncodingPrefixedType for an ATTRIBUTE-REF encoding instruction are in Section 9 💅 The restrictions for a COMPONENT-REF encoding instruction are in Section 10 🌈
The reference encoding instructions all use a shared production, defined like this:
RefParameters ::= ContextParameter ?
ContextParameter ::= "CONTEXT" AnyURIValueA RefParameters instance gives you extra info about a reference to a definition 🍓 A ContextParameter is used when a reference is ambiguous, meaning it points at definitions in more than one schema document or external DTD subset 🫶 This could happen, for example, when you import types with the same name from independently developed XML Schemas that don't have a target namespace [XSD1] 👑 When it's used with a reference to an element type in an external DTD subset, the AnyURIValue in the ContextParameter is the system identifier (a Uniform Resource Identifier or URI [URI]) of that external DTD subset 💖 Otherwise, the AnyURIValue is a URI that points to the intended schema document, which can be an XML Schema specification, a RELAX NG specification, or an ASN.1 or ASN.X specification 🦋
7. Expanded Names of Components ✨
every NamedType gets an expanded name [XMLNS10], and it's worked out like this 🧚
- (1) if the NamedType is subject to a NAME encoding instruction, the local name of the expanded name is the character string given by the NCNameValue of that NAME encoding instruction,
- (2) else if the NamedType is subject to a COMPONENT-REF encoding instruction, the expanded name is the same as the expanded name of the referenced top-level NamedType,
- (3) else if the NamedType is subject to an ATTRIBUTE-REF or ELEMENT-REF encoding instruction, the namespace name of the expanded name equals the namespace-name component of the QNameValue of the instruction, and the local name equals the local-name component of that QNameValue,
- (4) else if the NamedType is subject to a REF-AS-ELEMENT encoding instruction, the local name of the expanded name is the LocalPart [XMLNS10] of the qualified name given by the NameValue of the instruction,
- (5) otherwise, the local name of the expanded name is the identifier of the NamedType.
In cases (1) and (5), if the NamedType is a top-level NamedType and the module containing it has a TARGET-NAMESPACE encoding instruction, then the namespace name of the expanded name is the character string given by the AnyURIValue of that TARGET-NAMESPACE instruction. Otherwise the namespace name has no value 🌸
Aside: so TARGET-NAMESPACE only applies to a top-level NamedType, and never to any other NamedType 🙈
In case (4), if the encoding instruction contains a Namespace, the namespace name of the expanded name is the character string given by the AnyURIValue of that Namespace. Otherwise the namespace name has no value 🎀
The expanded names for the attribute components of a CHOICE, SEQUENCE, or SET type MUST be distinct 🔥 The expanded names for the components of a CHOICE, SEQUENCE, or SET type that are NOT attribute components MUST be distinct too 💅 These checks run after the COMPONENTS OF transformation from X.680, Clause 24.4 [X.680] 🌈
Aside: two components of the same CHOICE, SEQUENCE, or SET type can share an expanded name if one is an attribute component and the other isn't 👀 And that "isn't" case includes components subject to a GROUP or SIMPLE-CONTENT encoding instruction 💀
The expanded name of a top-level NamedType subject to an ATTRIBUTE encoding instruction MUST be distinct from the expanded name of every other top-level NamedType subject to an ATTRIBUTE encoding instruction in the same module 🍓
The expanded name of a top-level NamedType NOT subject to an ATTRIBUTE encoding instruction MUST be distinct from the expanded name of every other top-level NamedType NOT subject to an ATTRIBUTE encoding instruction in the same module 🫶
Aside: two top-level components can share an expanded name if one is an attribute component and the other isn't 🦋
8. The ATTRIBUTE Encoding Instruction 💖
the ATTRIBUTE encoding instruction tells an RXER encoder to write a component's value as an XML attribute instead of as a child element 🎀
Here's the notation for an ATTRIBUTE encoding instruction:
AttributeInstruction ::= "ATTRIBUTE"The base type of a NamedType's type, when that NamedType is subject to an ATTRIBUTE encoding instruction, SHALL NOT be:
- (1) a CHOICE, SET, or SET OF type, or
- (2) a SEQUENCE type other than the one defining the QName type from the AdditionalBasicDefinitions module [RXER] (so QName is allowed), or
- (3) a SEQUENCE OF type where the SequenceOfType is not subject to a LIST encoding instruction, or
- (4) an open type.
Example 🧁
PersonalDetails ::= SEQUENCE {
firstName [ATTRIBUTE] UTF8String,
middleName [ATTRIBUTE] UTF8String,
surname [ATTRIBUTE] UTF8String
}9. The ATTRIBUTE-REF Encoding Instruction ✨
okay so the ATTRIBUTE-REF encoding instruction is giving main character energy 💅. It tells an RXER encoder to write a component's value as an XML attribute instead of a child element 🎀. The attribute's name is the qualified name of the attribute declaration it points to. It also makes UTF8String values get restricted so they match the type of that attribute declaration 🦋
The notation is:
AttributeRefInstruction ::=
"ATTRIBUTE-REF" QNameValue RefParametersTaken together, the QNameValue and the ContextParameter in the RefParameters (if present) MUST reference an XML Schema attribute declaration or a top-level NamedType that is subject to an ATTRIBUTE encoding instruction. 💖
The type of a referenced XML Schema attribute declaration SHALL NOT be, either directly or by derivation, the XML Schema type QName, NOTATION, ENTITY, ENTITIES, or anySimpleType. 🙈
Aside: Values of these types need information from the context of the attribute to be interpreted 🧐. Since an ATTRIBUTE-REF encoding instruction can only prefix the ASN.1 UTF8String type, there's no way to capture that context, so these types are a no-go 💀
The type of a referenced top-level NamedType SHALL NOT be, either directly or by subtyping, the QName type from the AdditionalBasicDefinitions module [RXER]. 🚫
The Type in the EncodingPrefixedType for an ATTRIBUTE-REF encoding instruction SHALL be either:
- (1) the UTF8String type, or
- (2) a BuiltinType that is a PrefixedType that is a TaggedType where the Type in the TaggedType is one of (1) to (3), or
- (3) a BuiltinType that is a PrefixedType that is an EncodingPrefixedType where the Type in the EncodingPrefixedType is one of (1) to (3) and the EncodingPrefix in the EncodingPrefixedType does not contain a reference encoding instruction.
The identifier of a NamedType subject to an ATTRIBUTE-REF encoding instruction doesn't affect the name of attributes in an RXER encoding 🌸. For consistency, the identifier SHOULD, where possible, be the same as the local name of the referenced attribute declaration. ✨
10. The COMPONENT-REF Encoding Instruction 🧚
so ASN.1's basic notation has no concept of a top-level NamedType 😭. That means it has no way to reference one. Enter COMPONENT-REF 🦋, which lets you say that a NamedType inside a combining type definition is equivalent to a referenced top-level NamedType. Iconic 👑
The notation is:
ComponentRefInstruction ::= "COMPONENT-REF" ComponentReference
ComponentReference ::=
InternalComponentReference |
ExternalComponentReference
InternalComponentReference ::= identifier FromModule ?
FromModule ::= "FROM" GlobalModuleReference
ExternalComponentReference ::= modulereference "." identifierThe GlobalModuleReference production is defined by the ASN.1 basic notation [X.680]. If the GlobalModuleReference is absent from an InternalComponentReference, then the identifier MUST be the identifier of a top-level NamedType in the same module. If the GlobalModuleReference is present in an InternalComponentReference, then the identifier MUST be the identifier of a top-level NamedType in the referenced module. 💅
The modulereference in an ExternalComponentReference is used in the same way as a modulereference in an ExternalTypeReference. The identifier in an ExternalComponentReference MUST be the identifier of a top-level NamedType in the referenced module. 🎀
The Type in the EncodingPrefixedType for a COMPONENT-REF encoding instruction SHALL be either:
- (1) a ReferencedType that is a DefinedType that is a typereference (not a DummyReference) or an ExternalTypeReference, or
- (2) a BuiltinType or ReferencedType that is one of the productions in Table 1 in Section 5 of the specification for RXER [RXER], or
- (3) a BuiltinType that is a PrefixedType that is a TaggedType where the Type in the TaggedType is one of (1) to (4), or
- (4) a BuiltinType that is a PrefixedType that is an EncodingPrefixedType where the Type in the EncodingPrefixedType is one of (1) to (4) and the EncodingPrefix in the EncodingPrefixedType does not contain a reference encoding instruction.
The rules for RXER encoding instructions are strict here: no other RXER encoding instruction is allowed within a NamedType if that NamedType is subject to a COMPONENT-REF encoding instruction 🙅♀️
The Type in the top-level NamedType referenced by the COMPONENT-REF encoding instruction MUST be either:
- (a) if the preceding case (1) is used, a ReferencedType that is a DefinedType that is a typereference or ExternalTypeReference that references the same type as the DefinedType in case (1), or
- (b) if the preceding case (2) is used, a BuiltinType or ReferencedType that is the same as the BuiltinType or ReferencedType in case (2), or
- (c) a BuiltinType that is a PrefixedType that is an EncodingPrefixedType where the Type in the EncodingPrefixedType is one of (a) to (c), and the EncodingPrefix in the EncodingPrefixedType contains an RXER encoding instruction.
In principle, COMPONENT-REF creates a notional NamedType 🧠. Its expanded name is that of the referenced top-level NamedType, and the Type in case (1) or (2) gets swapped out for the Type of the referenced top-level NamedType.
In practice, non-RXER encoders and decoders can just use the original NamedType instead of the notional one 🌈. The Type in case (1) or (2) can only differ from the Type of the referenced top-level NamedType by having fewer RXER encoding instructions, and non-RXER encoders and decoders ignore RXER encoding instructions anyway.
Any prefixes on the Type in case (1) or (2) would get bypassed. RXER encoders and decoders can still use the referenced top-level NamedType instead of the notional one, because those prefixes can't be RXER encoding instructions (except for COMPONENT-REF itself) and can't affect an RXER encoding 💖
Example
Modules ::= SEQUENCE OF
module [COMPONENT-REF module
FROM AbstractSyntaxNotation-X
{ 1 3 6 1 4 1 21472 1 0 1 }]
ModuleDefinitionNote that the "module" top-level NamedType in the AbstractSyntaxNotation-X module is defined like so:
COMPONENT module ModuleDefinitionThe ASN.X translation of the SEQUENCE OF type definition gives a much more natural representation 🥰:
<namedType xmlns:asnx="urn:ietf:params:xml:ns:asnx"
name="Modules">
<sequenceOf>
<element ref="asnx:module"/>
</sequenceOf>
</namedType>Aside: The <namedType> element in ASN.X corresponds to a TypeAssignment, not a NamedType. 🤓
The identifier of a NamedType subject to a COMPONENT-REF encoding instruction doesn't contribute to an RXER encoding 🦋. For consistency with other encoding rules, the identifier SHOULD be the same as the identifier in the ComponentRefInstruction. ✨
11. The ELEMENT-REF Encoding Instruction 🌷
the ELEMENT-REF encoding instruction is the element version of ATTRIBUTE-REF 🫶. It makes an RXER encoder write a component's value as an element, and the element's name is the qualified name of the element declaration it references. It also makes values of the Markup ASN.1 type conform to the type of that element declaration 💜
The notation is:
ElementRefInstruction ::= "ELEMENT-REF" QNameValue RefParametersTaken together, the QNameValue and the ContextParameter in the RefParameters (if present) MUST reference an XML Schema element declaration, a RELAX NG element definition, or a top-level NamedType that is not subject to an ATTRIBUTE encoding instruction. 🍓
A referenced XML Schema element declaration MUST NOT have a type that requires the presence of values for the XML Schema ENTITY or ENTITIES types. 🚫
Aside: Entity declarations are not supported by CRXER. 💀
Example
AnySchema ::= CHOICE {
module [ELEMENT-REF {
namespace-name
"urn:ietf:params:xml:ns:asnx",
local-name "module" }]
Markup,
schema [ELEMENT-REF {
namespace-name
"http://www.w3.org/2001/XMLSchema",
local-name "schema" }]
Markup,
grammar [ELEMENT-REF {
namespace-name
"http://relaxng.org/ns/structure/1.0",
local-name "grammar" }]
Markup
}The ASN.X translation of the choice type definition gives a more natural representation 🌸:
<namedType xmlns:asnx="urn:ietf:params:xml:ns:asnx"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
xmlns:rng="http://relaxng.org/ns/structure/1.0"
name="AnySchema">
<choice>
<element ref="asnx:module" embedded="true"/>
<element ref="xs:schema" embedded="true"/>
<element ref="rng:grammar" embedded="true"/>
</choice>
</namedType>The identifier of a NamedType subject to an ELEMENT-REF encoding instruction doesn't affect the name of an element in an RXER encoding 🧚. For consistency, the identifier SHOULD, where possible, be the same as the local name of the referenced element declaration. 💅
12. The LIST Encoding Instruction 🎀
okay so the LIST encoding instruction tells an RXER encoder to take a value of a SEQUENCE OF type and write it out as one white-space-separated list of the component values 🧚
The notation is super simple:
ListInstruction ::= "LIST"The Type inside an EncodingPrefixedType for a LIST encoding instruction SHALL be one of these five cases 💅
(1) a BuiltinType that is a SequenceOfType of the "SEQUENCE OF NamedType" form, or
(2) a ConstrainedType that is a TypeWithConstraint of the "SEQUENCE Constraint OF NamedType" form or "SEQUENCE SizeConstraint OF NamedType" form, or
(3) a ConstrainedType that is not a TypeWithConstraint where the Type in the ConstrainedType is one of (1) to (5), or
(4) a BuiltinType that is a PrefixedType that is a TaggedType where the Type in the TaggedType is one of (1) to (5), or
(5) a BuiltinType that is a PrefixedType that is an EncodingPrefixedType where the Type in the EncodingPrefixedType is one of (1) to (5).
The whole point of this rule is to force the LIST encoding instruction to sit right next to the SequenceOfType or TypeWithConstraint it applies to 🫶
Aside: this makes it crystal clear to a reader that the encoding instruction applies to every use of the type, no matter how it gets referenced. no sneaky exceptions, periodt 💀
The SequenceOfType in case (1) and the TypeWithConstraint in case (2) are said to be "subject to" the LIST encoding instruction ✨
A SequenceOfType or TypeWithConstraint SHALL NOT be subject to more than one LIST encoding instruction. one LIST per type, no double dipping 🙅♀️
The base type of the component type of a SequenceOfType or TypeWithConstraint that is subject to a LIST encoding instruction MUST be one of the following:
(1) the BOOLEAN, INTEGER, ENUMERATED, REAL, OBJECT IDENTIFIER, RELATIVE-OID, GeneralizedTime, or UTCTime type, or
(2) the NCName, AnyURI, Name, or QName type from the AdditionalBasicDefinitions module [RXER].
Aside: yes, it would technically be possible to also allow any character string type that's constrained so that all its values have a length above zero and never contain white space. but checking that is a whole mess 😭 so to keep things simple, only the immediately useful constrained UTF8String types that are known to be suitable get in: NCName, AnyURI, and Name. bestie, keep it simple 🌸
The NamedType in a SequenceOfType or TypeWithConstraint that is subject to a LIST encoding instruction MUST NOT be subject to an ATTRIBUTE, ATTRIBUTE-REF, COMPONENT-REF, GROUP, ELEMENT-REF, REF-AS-ELEMENT, SIMPLE-CONTENT, or TYPE-AS-VERSION encoding instruction. no stacking these, it's giving chaos 🌪️
Example:
UpdateTimes ::= [LIST] SEQUENCE OF updateTime GeneralizedTime13. The NAME Encoding Instruction 🦋
The NAME encoding instruction lets an RXER encoder use a nominated character string instead of a component's identifier, wherever that identifier would otherwise show up in the encoding (like as an element or attribute name). rename-it-and-slay energy ✨
The notation:
NameInstruction ::= "NAME" "AS"? NCNameValueExample:
CHOICE {
foo-att [ATTRIBUTE] [NAME AS "Foo"] INTEGER,
foo-elem [NAME "Foo"] INTEGER
}14. The REF-AS-ELEMENT Encoding Instruction 🌈
The REF-AS-ELEMENT encoding instruction tells an RXER encoder to encode a component's value as an element, where the element's name is the name of the external DTD subset element type declaration that the instruction references. 👑 Extra bonus: it also restricts values of the Markup ASN.1 type so they stick to the content and attributes allowed by that element type declaration and its attribute-list declarations. so strict, so iconic 💅
The notation:
RefAsElementInstruction ::=
"REF-AS-ELEMENT" NameValue Namespace ? RefParameters
Namespace ::= "NAMESPACE" AnyURIValueTaken together, the NameValue and the ContextParameter in the RefParameters (if present) MUST reference an element type declaration in an external DTD subset that is conformant with Namespaces in XML 1.0 [XMLNS10]. this part is non-negotiable, bestie 🫶
The Namespace is present if and only if the Name of the referenced element type declaration conforms to a PrefixedName (a QName) [XMLNS10]. when it's there, the Namespace gives the namespace name that gets associated with the Prefix of that PrefixedName 🧁
The referenced element type declaration MUST NOT require the presence of attributes of type ENTITY or ENTITIES. 🙈
Aside: entity declarations aren't supported by CRXER. so no entities allowed, sorry not sorry 🫠
Example:
Suppose that the following external DTD subset has been defined with a system identifier of "http://www.example.com/inventory":
<?xml version='1.0'?>
<!ELEMENT product EMPTY>
<!ATTLIST product
name CDATA #IMPLIED
partNumber CDATA #REQUIRED
quantity CDATA #REQUIRED >The product element type declaration can be referenced as an element in an ASN.1 type definition:
CHOICE {
product [REF-AS-ELEMENT "product"
CONTEXT "http://www.example.com/inventory"]
Markup
}Here is the ASN.X translation of this ASN.1 type definition:
<type>
<choice>
<element elementType="product"
context="http://www.example.com/inventory"/>
</choice>
</type>The identifier of a NamedType subject to a REF-AS-ELEMENT encoding instruction does not contribute to the name of an element in an RXER encoding. for consistency's sake, the identifier SHOULD, where possible, be the same as the Name of the referenced element type declaration (or the LocalPart if the Name conforms to a PrefixedName). ✨
15. The REF-AS-TYPE Encoding Instruction 🍓
The REF-AS-TYPE encoding instruction restricts values of the Markup ASN.1 type so they conform to the content and attributes permitted by a nominated element type declaration and its attribute-list declarations in an external DTD subset. basically a dress code for your markup 👗
The notation:
RefAsTypeInstruction ::= "REF-AS-TYPE" NameValue RefParametersTaken together, the NameValue and the ContextParameter of the RefParameters (if present) MUST reference an element type declaration in an external DTD subset that is conformant with Namespaces in XML 1.0 [XMLNS10]. ✔️
The referenced element type declaration MUST NOT require the presence of attributes of type ENTITY or ENTITIES. 🙅♀️
Aside: entity declarations aren't supported by CRXER. same tea as before, babe 🍵
Example:
The product element type declaration can be referenced as a type in an ASN.1 definition:
SEQUENCE OF
inventoryItem
[REF-AS-TYPE "product"
CONTEXT "http://www.example.com/inventory"]
MarkupHere is the ASN.X translation of this definition:
<sequenceOf>
<element name="inventoryItem">
<type elementType="product"
context="http://www.example.com/inventory"/>
</element>
</sequenceOf>Note that when an element type declaration is referenced as a type, the Name of that element type declaration does not contribute to RXER encodings. for example, child elements in the RXER encoding of values of the above SEQUENCE OF type would look like this:
<inventoryItem name="hammer" partNumber="1543" quantity="29"/>16. The SCHEMA-IDENTITY Encoding Instruction 🧚
The SCHEMA-IDENTITY encoding instruction gives a unique identifier, a URI [URI], to the ASN.1 module that contains the encoding instruction. 🪪 It has no effect on an RXER encoder, but it does affect how an ASN.1 specification gets translated into an ASN.X representation.
The notation:
SchemaIdentityInstruction ::= "SCHEMA-IDENTITY" AnyURIValueThe character string given by the AnyURIValue of each SCHEMA-IDENTITY encoding instruction MUST be distinct. so, successive versions of an ASN.1 module must each have a different schema identity URI value. no copy-pasting the old URI and calling it a day 😭
17. The SIMPLE-CONTENT Encoding Instruction 💖
The SIMPLE-CONTENT encoding instruction tells an RXER encoder to encode a component's value (of a SEQUENCE or SET type) without wrapping it in a child element 🌸
The notation:
SimpleContentInstruction ::= "SIMPLE-CONTENT"A NamedType subject to a SIMPLE-CONTENT encoding instruction SHALL be in a ComponentType in a ComponentTypeList in a RootComponentTypeList. At most one such NamedType of a SEQUENCE or SET type is permitted to be subject to a SIMPLE-CONTENT encoding instruction. If any component is subject to a SIMPLE-CONTENT encoding instruction, then all other components in the same SEQUENCE or SET type definition MUST be attribute components. These tests are applied after the COMPONENTS OF transformation specified in X.680, Clause 24.4 [X.680]. ⭐
Aside: child elements and simple content are mutually exclusive, so pick a lane! specification writers should note: using SIMPLE-CONTENT on a component of an extensible SEQUENCE or SET type means every future extension has to be an attribute component, using only the limited set of types allowed for attribute components. ATTRIBUTE encoding instruction instead of SIMPLE-CONTENT dodges that limitation, so use it if you want freedom later 🦋
The base type of the type of a NamedType subject to a SIMPLE-CONTENT encoding instruction SHALL NOT be:
(1) a SET or SET OF type, or
(2) a CHOICE type where the ChoiceType is not subject to a UNION encoding instruction, or
(3) a SEQUENCE type other than the one defining the QName type from the AdditionalBasicDefinitions module [RXER] (i.e., QName is allowed), or
(4) a SEQUENCE OF type where the SequenceOfType is not subject to a LIST encoding instruction, or
(5) an open type.
If the type of a NamedType subject to a SIMPLE-CONTENT encoding instruction has abstract values with an empty character data translation [RXER] (i.e., an empty encoding), then the NamedType SHALL NOT be marked OPTIONAL or DEFAULT. no empty-but-optional situations, that's a no from me 🙅♀️
Example:
SEQUENCE {
units [ATTRIBUTE] UTF8String,
amount [SIMPLE-CONTENT] INTEGER
}18. The TARGET-NAMESPACE Encoding Instruction 🎀
okay so the TARGET-NAMESPACE encoding instruction is the one that attaches an XML namespace name 💖 [XMLNS10], which is a URI [URI], to all the type, object class, value, object, and object set references in the ASN.1 module it lives in. It also hooks that same namespace name onto every top-level NamedType in the RXER encoding control section. main character energy 👑
The notation looks like this:
TargetNamespaceInstruction ::=
"TARGET-NAMESPACE" AnyURIValue Prefix ?
Prefix ::= "PREFIX" NCNameValueThe AnyURIValue SHALL NOT specify an empty string. no empty strings allowed bestie 🙅♀️
Definition (target namespace): if an ASN.1 module has a TARGET-NAMESPACE encoding instruction, then the module's target namespace is the character string given by that instruction's AnyURIValue. If there's no such instruction, the target namespace is said to be absent. ✨
Two or more ASN.1 modules MAY share the same non-absent target namespace, but only if the expanded names of the top-level attribute components are distinct across all of those modules, the expanded names of the top-level element components are distinct across all of them, and the defined type, object class, value, object, and object set references are distinct within their category across all of them. it's giving careful naming 🧚
The Prefix, if it's there, just suggests an NCName to use as the namespace prefix in namespace declarations involving the target namespace. An RXER encoder is not obligated to use the nominated namespace prefix, so it's a suggestion, not a rule 🌸
If there are no top-level components, then RXER encodings produced using a module with a TARGET-NAMESPACE encoding instruction are backward compatible with the RXER encodings produced by that same module without the instruction. backwards compatible and iconic 🫶
19. The TYPE-AS-VERSION Encoding Instruction 🦋
The TYPE-AS-VERSION encoding instruction makes an RXER encoder include an xsi:type attribute in the encoding of a value of the component it's applied to. That attribute lets an XML Schema [XSD1] validator pick the right XML Schema translation for the version of the ASN.1 specification that was used to make the encoding, if one is available. ✨
Aside: Translations of an ASN.1 specification into a compatible XML Schema are expected to be slightly different across versions because of progressive extensions to the ASN.1 specification. Any incompatibilities between these translations can be accommodated if each version uses a different target namespace. The target namespace will be evident in the value of the xsi:type attribute and will cause an XML Schema validator to use the appropriate version. This mechanism also accommodates an ASN.1 type that is renamed in a later version of the ASN.1 specification. 💅
The notation for a TYPE-AS-VERSION encoding instruction is:
TypeAsVersionInstruction ::= "TYPE-AS-VERSION"The Type in a NamedType that is subject to a TYPE-AS-VERSION encoding instruction MUST be a namespace-qualified reference [RXER]. this one's a must, no cap 🔥
The addition of a TYPE-AS-VERSION encoding instruction does not affect the backward compatibility of RXER encodings. so adding it won't break anything old 🌈
Aside: In a translation of an ASN.1 specification into XML Schema, any Type in a NamedType that is subject to a TYPE-AS-VERSION encoding instruction is expected to be translated into the XML Schema anyType so that the xsi:type attribute acts as a switch to select the appropriate version. 🧚
20. The TYPE-REF Encoding Instruction 🌸
The TYPE-REF encoding instruction makes values of the Markup ASN.1 type get restricted so they conform to a specific XML Schema named type, a RELAX NG named pattern, or an ASN.1 defined type. ok so it's basically a pointer to a schema type 🍓
Aside: Referencing an ASN.1 type in a TYPE-REF encoding instruction does not have the effect of imposing a requirement to preserve the Infoset [INFOSET] representation of the RXER encoding of an abstract value of the type. It is still sufficient to preserve just the abstract value. 🦋
The notation for a TYPE-REF encoding instruction is:
TypeRefInstruction ::= "TYPE-REF" QNameValue RefParametersTaken together, the QNameValue and the ContextParameter of the RefParameters (if present) MUST reference an XML Schema named type, a RELAX NG named pattern, or an ASN.1 defined type. the combo has to actually point at something real 💖
A referenced XML Schema type MUST NOT require the presence of values for the XML Schema ENTITY or ENTITIES types. no ENTITY requirements allowed here 🙈
Aside: Entity declarations are not supported by CRXER. 💀
The QNameValue SHALL NOT be a direct reference to the XML Schema NOTATION type [XSD2] (that's the namespace name "http://www.w3.org/2001/XMLSchema" with local name "NOTATION"). however, a reference to an XML Schema type derived from the NOTATION type is permitted. so you can't point straight at NOTATION, but a derived type is fine 🫶
Aside: This restriction is to ensure that the lexical space [XSD2] of the referenced type is actually populated with the names of notations [XSD1]. 🌈
Example:
MyDecimal ::=
[TYPE-REF {
namespace-name "http://www.w3.org/2001/XMLSchema",
local-name "decimal" }]
MarkupNote that the ASN.X translation of this ASN.1 type definition provides a more natural way to reference the XML Schema decimal type:
<namedType xmlns:xs="http://www.w3.org/2001/XMLSchema"
name="MyDecimal">
<type ref="xs:decimal" embedded="true"/>
</namedType>21. The UNION Encoding Instruction 👑
The UNION encoding instruction makes an RXER encoder encode the value of an alternative of a CHOICE type without wrapping it in a child element. ✨ The chosen alternative can optionally be indicated with a member attribute. The optional PrecedenceList also lets a specification writer change the order in which an RXER decoder checks the alternatives of the CHOICE when it's figuring out which one was used (this only matters if the actual alternative wasn't given through the member attribute). the order is customisable, lowkey iconic 🧚
The notation for a UNION encoding instruction is:
UnionInstruction ::= "UNION" AlternativesPrecedence ?
AlternativesPrecedence ::= "PRECEDENCE" PrecedenceList
PrecedenceList ::= identifier PrecedenceList ?The Type in the EncodingPrefixedType for a UNION encoding instruction SHALL be one of the following:
- a BuiltinType that is a ChoiceType, or
- a ConstrainedType that is not a TypeWithConstraint where the Type in the ConstrainedType is one of (1) to (4), or
- a BuiltinType that is a PrefixedType that is a TaggedType where the Type in the TaggedType is one of (1) to (4), or
- a BuiltinType that is a PrefixedType that is an EncodingPrefixedType where the Type in the EncodingPrefixedType is one of (1) to (4).
The ChoiceType in case (1) is said to be "subject to" the UNION encoding instruction. 🦋
The base type of the type of each alternative of a ChoiceType that is subject to a UNION encoding instruction SHALL NOT be any of the following:
- a CHOICE, SET, or SET OF type, or
- a SEQUENCE type other than the one defining the QName type from the AdditionalBasicDefinitions module [RXER] (so QName is allowed), or
- a SEQUENCE OF type where the SequenceOfType is not subject to a LIST encoding instruction, or
- an open type.
these are the banned vibes 🙅♀️
Each identifier in the PrecedenceList MUST be the identifier of a NamedType in the ChoiceType. every identifier has to match a real NamedType 💅
A particular identifier SHALL NOT appear more than once in the same PrecedenceList. no repeats 💀
Every NamedType in a ChoiceType that is subject to a UNION encoding instruction MUST NOT be subject to an ATTRIBUTE, ATTRIBUTE-REF, COMPONENT-REF, GROUP, ELEMENT-REF, REF-AS-ELEMENT, SIMPLE-CONTENT, or TYPE-AS-VERSION encoding instruction. none of those instructions allowed on these NamedTypes 🙈
Example:
[UNION PRECEDENCE basicName] CHOICE {
extendedName UTF8String,
basicName PrintableString
}22. The VALUES Encoding Instruction 🌈
The VALUES encoding instruction makes an RXER encoder use nominated names instead of the identifiers that would otherwise show up in the encoding of a value of a BIT STRING, ENUMERATED, or INTEGER type. name swap, but make it cute 🎀
The notation for a VALUES encoding instruction is:
ValuesInstruction ::=
"VALUES" AllValuesMapped ? ValueMappingList ?
AllValuesMapped ::= AllCapitalized | AllUppercased
AllCapitalized ::= "ALL" "CAPITALIZED"
AllUppercased ::= "ALL" "UPPERCASED"
ValueMappingList ::= ValueMapping ValueMappingList ?
ValueMapping ::= "," identifier "AS" NCNameValueThe Type in the EncodingPrefixedType for a VALUES encoding instruction SHALL be one of the following:
- a BuiltinType that is a BitStringType with a NamedBitList, or
- a BuiltinType that is an EnumeratedType, or
- a BuiltinType that is an IntegerType with a NamedNumberList, or
- a ConstrainedType that is not a TypeWithConstraint where the Type in the ConstrainedType is one of (1) to (6), or
- a BuiltinType that is a PrefixedType that is a TaggedType where the Type in the TaggedType is one of (1) to (6), or
- a BuiltinType that is a PrefixedType that is an EncodingPrefixedType where the Type in the EncodingPrefixedType is one of (1) to (6).
The effect of this condition is to force the VALUES encoding instruction to sit textually next to the type definition it applies to. so it has to live right beside the type 🧚
The BitStringType, EnumeratedType, or IntegerType in case (1), (2), or (3), respectively, is said to be "subject to" the VALUES encoding instruction. 🦋
A BitStringType, EnumeratedType, or IntegerType SHALL NOT be subject to more than one VALUES encoding instruction. only one VALUES per type, periodt 💅
Each identifier in a ValueMapping MUST be an identifier appearing in the NamedBitList, Enumerations, or NamedNumberList, as the case may be. every mapped identifier has to actually exist in that list 🫶
The identifier in a ValueMapping SHALL NOT be the same as the identifier in any other ValueMapping for the same ValueMappingList. no identifier can be mapped twice in one list 🙅♀️
Definition (replacement name): each identifier in a BitStringType, EnumeratedType, or IntegerType subject to a VALUES encoding instruction has a replacement name. If there is a ValueMapping for the identifier, then the replacement name is the character string given by the NCNameValue in that ValueMapping. Otherwise, if AllCapitalized is used, the replacement name is the identifier with its first character uppercased. Otherwise, if AllUppercased is used, the replacement name is the identifier with all of its characters uppercased. In every other case, the replacement name is the identifier itself. ✨
The replacement names for the identifiers in a BitStringType subject to a VALUES encoding instruction MUST be distinct. 🌸
The replacement names for the identifiers in an EnumeratedType subject to a VALUES encoding instruction MUST be distinct. 🌸
The replacement names for the identifiers in an IntegerType subject to a VALUES encoding instruction MUST be distinct. 🌸
Example:
Traffic-Light ::= [VALUES ALL CAPITALIZED, red AS "RED"]
ENUMERATED {
red, -- Replacement name is RED.
amber, -- Replacement name is Amber.
green -- Replacement name is Green.
}23. Insertion Encoding Instructions ✨
okay so the insertion encoding instructions are the ones that handle extensions, and there are five of them 🎀 NO-INSERTIONS, HOLLOW-INSERTIONS, SINGULAR-INSERTIONS, UNIFORM-INSERTIONS, and MULTIFORM-INSERTIONS. their notations are NoInsertionsInstruction, HollowInsertionsInstruction, SingularInsertionsInstruction, UniformInsertionsInstruction, and MultiformInsertionsInstruction. 💅
here's the notation for the whole family:
InsertionsInstruction ::=
NoInsertionsInstruction |
HollowInsertionsInstruction |
SingularInsertionsInstruction |
UniformInsertionsInstruction |
MultiformInsertionsInstruction
NoInsertionsInstruction ::= "NO-INSERTIONS"
HollowInsertionsInstruction ::= "HOLLOW-INSERTIONS"
SingularInsertionsInstruction ::= "SINGULAR-INSERTIONS"
UniformInsertionsInstruction ::= "UNIFORM-INSERTIONS"
MultiformInsertionsInstruction ::= "MULTIFORM-INSERTIONS"so here's the tea ☕ using the GROUP encoding instruction on components with extensible types can get messy, because an unknown extension could end up tied to more than one extension insertion point. the insertion encoding instructions fix that by limiting what extensions are allowed to look like. basically they tell you which extensions can be added to an ASN.1 specification without breaking forward compatibility for RXER encodings. main character energy 🦋
Aside: Forward compatibility means the ability for a decoder to successfully decode an encoding containing extensions introduced into a version of the specification that is more recent than the one used by the decoder. 🧚
in the most general case, an extension to a CHOICE, SET, or SEQUENCE type can generate zero or more attributes and zero or more elements, because the extension might use GROUP and ATTRIBUTE encoding instructions. it's giving chaos 😭
now the individual vibes:
MULTIFORM-INSERTIONS means that RXER encodings made by forward-compatible extensions to a type will always have one or more elements and zero or more attributes. there's no rule on what the elements are called. 🌈
Aside: Of necessity, the names of the attributes will all be different in any given encoding.
UNIFORM-INSERTIONS means that those encodings will always have one or more elements that share the same expanded name, plus zero or more attributes. the shared expanded name doesn't have to match the one used in any other encoding of the extension. for example, in one encoding the elements might all be called "foo", while in another they might all be called "bar". iconic shapeshifting 🫶
SINGULAR-INSERTIONS means those encodings will always have exactly one element and zero or more attributes. the name of that single element doesn't have to be the same in every possible encoding of the extension. 🍓
HOLLOW-INSERTIONS means those encodings will always have zero elements and zero or more attributes. just attributes, no elements, very minimalist 🌸
NO-INSERTIONS means no forward-compatible extensions can be made to a type at all. closed doors, bestie 🚪
examples of forward-compatible extensions are in Appendix C, so go check those out ✨
the Type inside the EncodingPrefixedType for an insertion encoding instruction SHALL be one of the following:
- a BuiltinType that is a ChoiceType, where the ChoiceType is not subject to a UNION encoding instruction, or
- a BuiltinType that is a SequenceType or SetType, or
- a ConstrainedType that is not a TypeWithConstraint, where the Type in the ConstrainedType is one of (1) to (5), or
- a BuiltinType that is a PrefixedType that is a TaggedType, where the Type in the TaggedType is one of (1) to (5), or
- a BuiltinType that is a PrefixedType that is an EncodingPrefixedType, where the Type in the EncodingPrefixedType is one of (1) to (5).
case (2) is not allowed when the insertion encoding instruction is SINGULAR-INSERTIONS, UNIFORM-INSERTIONS, or MULTIFORM-INSERTIONS 🙅♀️
Aside: Because extensions to a SET or SEQUENCE type are serial and effectively optional, the SINGULAR-INSERTIONS, UNIFORM-INSERTIONS, and MULTIFORM-INSERTIONS encoding instructions offer no advantage over unrestricted extensions (for a SET or SEQUENCE). for example, an optional series of singular insertions generates zero or more elements and zero or more attributes, just like an unrestricted extension. 💀
the Type in case (1) or case (2) is said to be "subject to" the insertion encoding instruction. 🎀
the Type in case (1) or case (2) MUST be extensible, either explicitly or by default. no exceptions, babe 💖
a Type SHALL NOT be subject to more than one insertion encoding instruction. one lane only 🛣️
ok so the insertion encoding instructions tell you what kinds of extensions can be made to a type without breaking forward compatibility, but they don't stop you from making extensions that DO break it. it's not an error for a type's base type to contain extensions that don't follow an insertion encoding instruction affecting the type. BUT if any of those extensions get made, then a new value SHOULD be added to the extensible set of permitted values for a version indicator attribute (or attributes, see Section 24) whose scope covers those extensions. an example is in Appendix C. 🔥
24. The VERSION-INDICATOR Encoding Instruction ✨
the VERSION-INDICATOR encoding instruction is basically the alarm bell 🚨 it lets RXER decoders know that an encoding has extensions that break forward compatibility (see the section right before this one, obviously 🙈).
the notation is:
VersionIndicatorInstruction ::= "VERSION-INDICATOR"a NamedType subject to a VERSION-INDICATOR encoding instruction MUST also be subject to an ATTRIBUTE encoding instruction. no ATTRIBUTE, no party 🎉
the type of that NamedType MUST be directly or indirectly a constrained type where the set of permitted values is defined to be extensible. each value stands for a different version of the ASN.1 specification. usually, an application sets the version indicator attribute to the last of those permitted values. an application MAY set it to the value for an earlier version of the specification if it hasn't used any of the extensions added in a later version. flexible, honestly iconic 💅
here's the important bit 👀 if an RXER decoder runs into a value of the type that isn't one of the root values or extension additions (but is still allowed, since the set is extensible), that means the decoder is using a version of the ASN.1 specification that isn't compatible with the one that made the encoding. in that case, the decoder SHOULD treat the element containing the attribute as having an unknown ASN.1 type. 😭
Aside: A version indicator attribute only signals an incompatibility with respect to RXER encodings. Other encodings are not affected because the GROUP encoding instruction does not apply to them. 🧚
Examples
in this first example, the decoder is using an incompatible older version if the value of the version attribute in a received RXER encoding is not 1, 2, or 3.
SEQUENCE {
version [ATTRIBUTE] [VERSION-INDICATOR]
INTEGER (1, ..., 2..3),
message MessageType
}in this second example, the decoder is using an incompatible older version if the value of the format attribute in a received RXER encoding is not "1.0", "1.1", or "2.0".
SEQUENCE {
format [ATTRIBUTE] [VERSION-INDICATOR]
UTF8String ("1.0", ..., "1.1" | "2.0"),
message MessageType
}an extensive example is in Appendix C, so you know where to look 🌈
it isn't necessary for every extensible type to have its own version indicator attribute. it's pretty typical for only the types of top-level element components to have one, and that single attribute then serves as the version indicator for all the nested components. one attribute to rule them all 👑🦋
25. The GROUP Encoding Instruction ✨
okay bestie, the GROUP encoding instruction is lowkey the main character of this whole section 💅 It tells an RXER encoder to encode a component's value without wrapping it in its own element. The contents just show up as elements directly, which lets you build non-trivial content models for element content 🦋
The notation is super simple:
GroupInstruction ::= "GROUP"Now the rules. The base type of a NamedType that gets a GROUP encoding instruction SHALL be one of these:
- (1) a SEQUENCE, SET, or SET OF type, or
- (2) a CHOICE type where the ChoiceType is not subject to a UNION encoding instruction, or
- (3) a SEQUENCE OF type where the SequenceOfType is not subject to a LIST encoding instruction.
For case (1), the SEQUENCE type SHALL NOT be the associated type for a built-in type, SHALL NOT be a type from the AdditionalBasicDefinitions module [RXER], and SHALL NOT contain a component that is subject to a SIMPLE-CONTENT encoding instruction.
Aside: so the CHARACTER STRING, EMBEDDED PDV, EXTERNAL, REAL, and QName types are all excluded 🙈
For case (2), the CHOICE type SHALL NOT be a type from the AdditionalBasicDefinitions module.
Aside: which means the Markup type is excluded too 💀
Definition (visible component): ignoring all type constraints, the visible components for a type that is directly or indirectly a combining ASN.1 type (i.e., SEQUENCE, SET, CHOICE, SEQUENCE OF, or SET OF) are the components of the combining type definition, plus, for each NamedType (of the combining type definition) that is subject to a GROUP encoding instruction, the visible components for the type of that NamedType. The visible components are determined after the COMPONENTS OF transformation specified in X.680, Clause 24.4 [X.680].
Aside: the set of visible attribute and element components for a type is basically every component of the type, plus any nested types, that describe attributes and child elements showing up in the RXER encodings of values of the outer type 🎀
A GROUP encoding instruction MUST NOT be used where it would cause a NamedType to be a visible component of the type of that same NamedType. This can only happen if the type definition is recursive, so be careful 🚫
Aside: components subject to a GROUP encoding instruction might get translated into a compatible XML Schema [XSD1] as group definitions. A NamedType that is visible to its own type is kinda like a circular group, and XML Schema disallows those 🙈
Section 25.1 adds more conditions on using GROUP, so keep reading 📖
In any use of the GROUP encoding instruction, there's an including type (the type that contains the component subject to the GROUP encoding instruction) and an included type (the base type of that component). Either one can have an extensible content model, either by using ASN.1 extensibility directly or by including, through another GROUP encoding instruction, some other type that is extensible ✨
The including and included types can be defined in different ASN.1 modules. When that happens, the owner of the including type (the person or organization with the authority to add extensions to the including type's definition) might be a different person from the owner of the included type 👑
Here's where it gets messy. If the owner of the including type isn't using the most recent version of the included type's definition, they might add an extension that's valid for the older version but turns out to be invalid when the latest versions of both definitions get brought together, maybe by a third party 😭 The owner of the including type has to know the included type exists, but the reverse isn't necessarily true. The owner of the included type could add an extension without realizing it breaks somebody else's including type. Yikes 🙈
So to avoid all that drama, a GROUP encoding instruction MUST NOT be used if all three of these are true:
- (1) the included type is defined in a different module from the including type, and
- (2) the included type has an extensible content model, and
- (3) changes to the included type are not coordinated with the owner of the including type.
Changes in the included type are coordinated with the owner of the including type if any of these are true:
- (1) the owner of the included type is also the owner of the including type, or
- (2) the owner of the including type is collaborating with the owner of the included type, or
- (3) all changes will be vetted by a common third party before being approved and published.
25.1. Unambiguous Encodings 🌸
Okay so unregulated use of GROUP can easily lead to specs where totally different abstract values have RXER encodings that look exactly the same. That's called ambiguous encodings, and it's a mess 😵💫 This section puts restrictions on GROUP so that distinct abstract values always have distinct RXER encodings. These restrictions also make sure an abstract value can be decoded in a single pass, with no backtracking. Clean, efficient, iconic 💖
An RXER decoder for an ASN.1 type can be thought of as a recognizer for a notional language made of element and attribute expanded names. The type definition describes the grammar for that language (it's actually a context-free grammar). The rules for keeping decoding easy and unambiguous are way easier to state as conditions on this associated grammar, so that's what we do 🧚
Implementations aren't expected to check type definitions exactly the way this section describes. However, the procedure they use MUST produce the same result.
Section 25.1.1 explains how to recast, as a grammar, a type definition that has components subject to GROUP. Sections 25.1.2 and 25.1.3 list the conditions the grammar must satisfy for the type definition to be valid. Section 25.1.4 explains how unrecognized attributes get accepted by the grammar for an extensible type 💜
Appendices A and B have extensive examples, so go peek if you want to see it in action 🍓
25.1.1. Grammar Construction 🧩
A grammar is a collection of productions. Each production has a left-hand side and a right-hand side, separated in this document by the ::= symbol. In a context-free grammar, the left-hand side is a single non-terminal symbol. The right-hand side is a sequence of non-terminal and terminal symbols. The terminal symbols are the lexical items of the language the grammar describes. One non-terminal gets nominated as the start symbol. You generate a valid sequence of terminals by starting from the start symbol and repeatedly replacing any non-terminal with the right-hand side of one of the productions where that non-terminal is on the left-hand side. You're done once there are no non-terminals left to replace ✨
Aside: X.680 describes the ASN.1 basic notation using a context-free grammar 🎀
Each NamedType has an associated primary non-terminal and an associated secondary non-terminal.
Aside: the secondary non-terminal for a NamedType gets used when the base type of the type in the NamedType is a SEQUENCE OF type or SET OF type 💅
Each ExtensionAddition and ExtensionAdditionAlternative has an associated non-terminal. Every extensible type has a non-terminal for its extension insertion point. There's also a primary start non-terminal (the start symbol) and a secondary start non-terminal. The exact names of the non-terminals don't matter much, but all of them MUST be mutually distinct 🔥
For most of the examples in this document (though not in the most general case), the primary non-terminal for a NamedType is just the identifier of that NamedType. The primary start non-terminal is S. The non-terminals for the ExtensionAddition and ExtensionAdditionAlternative instances are E1, E2, E3, and so on. The non-terminals for the extension insertion points are I1, I2, I3, and so on. Secondary non-terminals get labelled by adding a ' character to the primary label, so the primary and secondary start non-terminals are S and S', respectively 🦋
Each NamedType and extension insertion point has an associated terminal. There's also a terminal called the general extension terminal, which isn't tied to any specific notation. The general extension terminal and the terminals for the extension insertion points are used to represent elements in unknown extensions. The exact nature of the terminals doesn't matter, but the aforementioned terminals MUST be mutually distinct 🙌 Terminals are further categorized as either element terminals or attribute terminals. A terminal for a NamedType is an attribute terminal if its associated NamedType is an attribute component, and it's an element terminal otherwise. The general extension terminal and the terminals for the extension insertion points are categorized as element terminals 🌈
Terminals for attributes in unknown extensions aren't explicitly provided in the grammar. Some productions in the grammar are categorized as insertion point productions, and Section 25.1.4 describes their role in accepting unknown attributes 🧚♀️
In the examples in this document, the terminal for a component other than an attribute component is written as the local name of the component's expanded name, in double quotes. The terminal for an attribute component is written as the local name of its expanded name, prefixed by the @ character and enclosed in double quotes. The general extension terminal is written as "*", and the terminals for the extension insertion points are written as "*1", "*2", "*3", and so on 💖
The productions generated from a NamedType depend on the base type of the type of the NamedType. The productions for the start non-terminals depend on the combining type definition being tested. In either case, the procedure for generating productions takes a primary non-terminal, a secondary non-terminal (sometimes), and a type definition 🎀
The grammar is constructed starting from the start non-terminals and the combining type definition being tested.
A grammar is constructed after the COMPONENTS OF transformation specified in X.680, Clause 24.4 [X.680].
Given a primary non-terminal, N, and a type whose base type is a SEQUENCE or SET type, a production is added to the grammar with N as the left-hand side. The right-hand side is built from an initial empty state, following these cases in order:
- (1) If an initial RootComponentTypeList is present in the base type, then the sequence of primary non-terminals for the components nested in that RootComponentTypeList gets appended to the right-hand side, in the order they're defined.
- (2) If an ExtensionAdditions instance is present in the base type and not empty, then the non-terminal for the first ExtensionAddition nested in that ExtensionAdditions instance gets appended to the right-hand side.
Okay bestie, this is where the grammar really starts coming together, and it's giving main character energy 💅✨
(3) If an ExtensionAdditions instance is empty or not there at all in the base type, the base type is extensible (explicitly or by default), and the base type is not subject to a NO-INSERTIONS or HOLLOW-INSERTIONS encoding instruction, then the non-terminal for the extension insertion point of the base type gets appended to the right-hand side. 🫶
(4) If there's a final RootComponentTypeList in the base type, then the primary non-terminals for the components nested in that RootComponentTypeList get appended to the right-hand side, in the order they were defined. 📝
The production is an insertion point production if an ExtensionAdditions instance is empty or not present in the base type, the base type is extensible (explicitly or by default), and the base type is not subject to a NO-INSERTIONS encoding instruction. 🌸
If a component in a ComponentTypeList (in either a RootComponentTypeList or an ExtensionAdditionGroup) is marked OPTIONAL or DEFAULT, then a production gets added to the grammar with the component's primary non-terminal as the left-hand side and an empty right-hand side. Bestie, the empty option is what makes it skippable 🦋
If a component is subject to a GROUP encoding instruction, the ASN.1 combining type containing it doesn't matter. One or more productions built according to the component's type get added to the grammar, and each one has the component's primary non-terminal as its left-hand side. 🧚
If a component is not subject to a GROUP encoding instruction, again regardless of the combining type, then a production gets added with the component's primary non-terminal as the left-hand side and the component's terminal as the right-hand side. Simple and iconic 💖
Example
Consider the following ASN.1 type definition:
SEQUENCE {
-- Start of initial RootComponentTypeList.
one [ATTRIBUTE] UTF8String,
two BOOLEAN OPTIONAL,
three INTEGER
-- End of initial RootComponentTypeList.
}Here is the grammar derived from this type:
S ::= one two three
one ::= "@one"
two ::= "two"
two ::=
three ::= "three"For each ExtensionAddition (of a SEQUENCE or SET base type), a production gets added where the left-hand side is that ExtensionAddition's non-terminal and the right-hand side starts out empty. If the ExtensionAddition is a ComponentType, the primary non-terminal for the NamedType in that ComponentType gets appended to the right-hand side. Otherwise (it's an ExtensionAdditionGroup), the primary non-terminals for the components nested in the ComponentTypeList of that group get appended, in the order they were defined. 🔥
If another ExtensionAddition follows, that next ExtensionAddition's non-terminal gets appended to the right-hand side. If it doesn't, and the base type isn't subject to a NO-INSERTIONS or HOLLOW-INSERTIONS encoding instruction, then the extension insertion point's non-terminal of the base type gets appended instead. And if the ExtensionAddition isn't followed by another one and the base type isn't subject to a NO-INSERTIONS encoding instruction, the production is an insertion point production. 🎀
If the empty sequence of terminals can't be generated from the production, then another production gets added where the left-hand side is that ExtensionAddition's non-terminal and the right-hand side is empty. Heads up though: you might have to wait until the whole grammar is done before you can tell whether that's needed 👀
Aside: An extension is always effectively optional since a sender may be using an earlier version of the ASN.1 specification where none, or only some, of the extensions have been defined.
Aside: The grammar generated for ExtensionAdditions is structured to take account of the condition that an extension can only be used if all the earlier extensions are also used [X.680].
If a SEQUENCE or SET base type is extensible (explicitly or by default) and isn't subject to a NO-INSERTIONS or HOLLOW-INSERTIONS encoding instruction, then two things happen:
- (1) A production gets added where the left-hand side is the extension insertion point's non-terminal of the base type, and the right-hand side is the general extension terminal followed by that same non-terminal, and
- (2) A production gets added where the left-hand side is the extension insertion point's non-terminal and the right-hand side is empty.
Example
Consider the following ASN.1 type definition:
SEQUENCE {
-- Start of initial RootComponentTypeList.
one BOOLEAN,
two INTEGER OPTIONAL,
-- End of initial RootComponentTypeList.
...,
-- Start of ExtensionAdditions.
four INTEGER, -- First ExtensionAddition (E1).
five BOOLEAN OPTIONAL, -- Second ExtensionAddition (E2).
[[ -- An ExtensionAdditionGroup.
six UTF8String,
seven INTEGER OPTIONAL
]], -- Third ExtensionAddition (E3).
-- End of ExtensionAdditions.
-- The extension insertion point is here (I1).
...,
-- Start of final RootComponentTypeList.
three INTEGER
}Here is the grammar derived from this type:
S ::= one two E1 three
E1 ::= four E2
E1 ::=
E2 ::= five E3
E3 ::= six seven I1
E3 ::=
I1 ::= "*" I1
I1 ::=
one ::= "one"
two ::= "two"
two ::=
three ::= "three"
four ::= "four"
five ::= "five"
five ::=
six ::= "six"
seven ::= "seven"
seven ::=If the SEQUENCE type were subject to a NO-INSERTIONS or HOLLOW-INSERTIONS encoding instruction, then the productions for I1 would not appear, and the first production for E3 would be:
E3 ::= six sevenNow for the CHOICE situation 🌈 Given a primary non-terminal, N, and a type where the base type is a CHOICE type:
- (1) A production gets added for each NamedType nested in the RootAlternativeTypeList of the base type, where the left-hand side is N and the right-hand side is that NamedType's primary non-terminal.
- (2) A production gets added for each ExtensionAdditionAlternative of the base type, where the left-hand side is N and the right-hand side is that ExtensionAdditionAlternative's non-terminal.
- (3) If the base type is extensible (explicitly or by default) and isn't subject to an insertion encoding instruction, then:
- (a) A production gets added where the left-hand side is N and the right-hand side is the extension insertion point's non-terminal of the base type. This production is an insertion point production.
- (b) A production gets added where the left-hand side is the extension insertion point's non-terminal of the base type and the right-hand side is the general extension terminal followed by that same non-terminal.
- (c) A production gets added where the left-hand side is the extension insertion point's non-terminal of the base type and the right-hand side is empty.
- (4) If the base type is subject to a
HOLLOW-INSERTIONSencoding instruction, then a production gets added where the left-hand side is N and the right-hand side is empty. This production is an insertion point production. - (5) If the base type is subject to a
SINGULAR-INSERTIONSencoding instruction, then a production gets added where the left-hand side is N and the right-hand side is the general extension terminal. This production is an insertion point production. - (6) If the base type is subject to a
UNIFORM-INSERTIONSencoding instruction, then:- (a) A production gets added where the left-hand side is N and the right-hand side is the general extension terminal.
Aside: This production is used to verify the correctness of an ASN.1 type definition, but would not be used in the implementation of an RXER decoder. The next production takes precedence over it for accepting an unknown element.
- (b) A production gets added where the left-hand side is N and the right-hand side is the terminal for the extension insertion point of the base type followed by the non-terminal for the extension insertion point. This production is an insertion point production.
- (c) A production gets added where the left-hand side is the extension insertion point's non-terminal of the base type and the right-hand side is the terminal for the extension insertion point followed by that same non-terminal.
- (d) A production gets added where the left-hand side is the extension insertion point's non-terminal of the base type and the right-hand side is empty.
- (7) If the base type is subject to a
MULTIFORM-INSERTIONSencoding instruction, then:- (a) A production gets added where the left-hand side is N and the right-hand side is the general extension terminal followed by the extension insertion point's non-terminal of the base type. This production is an insertion point production.
- (b) A production gets added where the left-hand side is the extension insertion point's non-terminal of the base type and the right-hand side is the general extension terminal followed by that same non-terminal.
- (c) A production gets added where the left-hand side is the extension insertion point's non-terminal of the base type and the right-hand side is empty.
If an ExtensionAdditionAlternative is a NamedType, a production gets added where the left-hand side is that ExtensionAdditionAlternative's non-terminal and the right-hand side is the NamedType's primary non-terminal. 💜
If an ExtensionAdditionAlternative is an ExtensionAdditionAlternativesGroup, then a production gets added for each NamedType nested in that group, where the left-hand side is the ExtensionAdditionAlternative's non-terminal and the right-hand side is that NamedType's primary non-terminal. Group chat, we're almost at the example! 🙈
Example
Consider the following ASN.1 type definition:
Okay so, bestie, this is where the CHOICE thing gets really fun 🎀 Check out this type:
CHOICE {
-- Start of RootAlternativeTypeList.
one BOOLEAN,
two INTEGER,
-- End of RootAlternativeTypeList.
...,
-- Start of ExtensionAdditionAlternatives.
three INTEGER, -- First ExtensionAdditionAlternative (E1).
[[ -- An ExtensionAdditionAlternativesGroup.
four UTF8String,
five INTEGER
]] -- Second ExtensionAdditionAlternative (E2).
-- The extension insertion point is here (I1).
}And here's the grammar that falls out of it 🧚
S ::= one
S ::= two
S ::= E1
S ::= E2
S ::= I1
I1 ::= "*" I1
I1 ::=
E1 ::= three
E2 ::= four
E2 ::= five
one ::= "one"
two ::= "two"
three ::= "three"
four ::= "four"
five ::= "five"If this CHOICE gets a NO-INSERTIONS encoding instruction, the fifth, sixth, and seventh productions get deleted 💀
(fifth, sixth, and seventh productions removed)If it gets a HOLLOW-INSERTIONS instruction instead, those same three productions get swapped out for this one 🫶
S ::=With SINGULAR-INSERTIONS, they become this 💅
S ::= "*"With UNIFORM-INSERTIONS, the fifth and sixth productions get replaced by these ✨
S ::= "*"
S ::= "*1" I1
I1 ::= "*1" I1And MULTIFORM-INSERTIONS only swaps out the fifth production 🌈
S ::= "*" I1Constraints on a SEQUENCE, SET, or CHOICE type get ignored. They do not affect the grammar being generated 🙈
Aside: This avoids an awkward situation where values of a subtype have to be decoded differently from values of the parent type. It also simplifies the verification procedure. Honestly the whole point is to keep things simple, iykyk 🦋
Now for SEQUENCE OF and SET OF. Say you've got a primary non-terminal, N, and a type with a SEQUENCE OF or SET OF base type that allows a size of zero (an empty sequence or set) 🍓 Then:
- A production gets added where the left-hand side is N and the right-hand side is the primary non-terminal for the NamedType of the component of the SEQUENCE OF or SET OF base type, followed by N.
- A production gets added where the left-hand side is N and the right-hand side is empty.
Now if you have a primary non-terminal, N, a secondary non-terminal, N', and a SEQUENCE OF or SET OF type that does not allow size zero, it's a little different 👑
- A production gets added where the left-hand side is N and the right-hand side is the primary non-terminal for the NamedType of the component, followed by N'.
- A production gets added where the left-hand side is N' and the right-hand side is the primary non-terminal for the NamedType of the component, followed by N'.
- A production gets added where the left-hand side is N' and the right-hand side is empty.
Example time! 🧁 Consider this ASN.1 type definition:
SEQUENCE SIZE(1..MAX) OF number INTEGERAnd the grammar derived from it:
S ::= number S'
S' ::= number S'
S' ::=
number ::= "number"Any inner subtyping (InnerTypeContraints) gets ignored when you're deciding whether a SEQUENCE OF or SET OF type permits a value of size zero. Totally irrelevant, no cap 🙅♀️
And that wraps up the transformation of ASN.1 combining type definitions into a grammar! 🎉
25.1.2. Unique Component Attribution ✨
This part is about the rules the grammar has to follow so that every element and attribute in a received RXER encoding can be pinned to exactly one ASN.1 component definition. Super important, periodt 💜
Definition (used by the grammar): a non-terminal, N, is used by the grammar if:
- N is the start symbol, or
- N appears on the right-hand side of a production where the non-terminal on the left-hand side is used by the grammar.
Definition (multiple derivation paths): a non-terminal, N, has multiple derivation paths if:
- N appears on the right-hand side of a production where the non-terminal on the left-hand side has multiple derivation paths, or
- N appears on the right-hand side of more than one production where the non-terminal on the left-hand side is used by the grammar, or
- N is the start symbol and it appears on the right-hand side of a production where the non-terminal on the left-hand side is used by the grammar.
Now the big rule 😭 For every ASN.1 type with a base type containing components that are subject to a GROUP encoding instruction, the grammar derived by the method in this document MUST NOT have:
- two or more primary non-terminals that are used by the grammar and are associated with element components having the same expanded name, or
- two or more primary non-terminals that are used by the grammar and are associated with attribute components having the same expanded name, or
- a primary non-terminal that has multiple derivation paths and is associated with an attribute component.
Aside: Case (1) is there because of component referencing notations that get evaluated against the XML encoding of an abstract value. Case (1) guarantees, without needing extensive testing (which would have to account for the encoding instructions of every other encoding rule), that all sibling elements with the same expanded name get associated with equivalent type definitions. That equivalence means a component referenced by element name can be re-encoded using a different set of ASN.1 encoding rules without any confusion about which type definition and encoding instructions apply. Cases (2) and (3) make sure an attribute name is always uniquely tied to one component that can occur at most once and always sits in the same part of an abstract value. Clean and predictable, I love that for us 🦋
Example time 🎀 The following example types show various uses and misuses of the GROUP encoding instruction with respect to unique component attribution:
TA ::= SEQUENCE {
a [GROUP] TB,
b [GROUP] CHOICE {
a [GROUP] TB,
b [NAME AS "c"] [ATTRIBUTE] INTEGER,
c INTEGER,
d TB,
e [GROUP] TD,
f [ATTRIBUTE] UTF8String
},
c [ATTRIBUTE] INTEGER,
d [GROUP] SEQUENCE OF
a [GROUP] SEQUENCE {
a [ATTRIBUTE] OBJECT IDENTIFIER,
b INTEGER
},
e [NAME AS "c"] INTEGER,
COMPONENTS OF TD
}
TB ::= SEQUENCE {
a INTEGER,
b [ATTRIBUTE] BOOLEAN,
COMPONENTS OF TC
}
TC ::= SEQUENCE {
f OBJECT IDENTIFIER
}
TD ::= SEQUENCE {
g OBJECT IDENTIFIER
}The grammar for TA gets built after the COMPONENTS OF transformation, so here's what that transformation produces. This example breaks from the usual habit of using just the identifier of a NamedType for its primary non-terminal. Instead, a label relative to the outermost type gets used, which makes unique component attribution easier to see 🔍 The labels are shown on the right-hand side:
TA ::= SEQUENCE {
a [GROUP] TB, -- TA.a
b [GROUP] CHOICE { -- TA.b
a [GROUP] TB, -- TA.b.a
b [NAME AS "c"] [ATTRIBUTE] INTEGER, -- TA.b.b
c INTEGER, -- TA.b.c
d TB, -- TA.b.d
e [GROUP] TD, -- TA.b.e
f [ATTRIBUTE] UTF8String -- TA.b.f
},
c [ATTRIBUTE] INTEGER, -- TA.c
d [GROUP] SEQUENCE OF -- TA.d
a [GROUP] SEQUENCE { -- TA.d.a
a [ATTRIBUTE] OBJECT IDENTIFIER, -- TA.d.a.a
b INTEGER -- TA.d.a.b
},
e [NAME AS "c"] INTEGER, -- TA.e
g OBJECT IDENTIFIER -- TA.g
}
TB ::= SEQUENCE {
a INTEGER, -- TB.a
b [ATTRIBUTE] BOOLEAN, -- TB.b
f OBJECT IDENTIFIER -- TB.f
}
-- Type TC is no longer of interest. --
TD ::= SEQUENCE {
g OBJECT IDENTIFIER -- TD.g
}The associated grammar is:
S ::= TA.a TA.b TA.c TA.d TA.e TA.g
TA.a ::= TB.a TB.b TB.f
TB.a ::= "a"
TB.b ::= "@b"
TB.f ::= "f"
TA.b ::= TA.b.a
TA.b ::= TA.b.b
TA.b ::= TA.b.c
TA.b ::= TA.b.d
TA.b ::= TA.b.e
TA.b ::= TA.b.f
TA.b.a ::= TB.a TB.b TB.f
TA.b.b ::= "@c"
TA.b.c ::= "c"
TA.b.d ::= "d"
TA.b.e ::= TD.g
TA.b.f ::= "@f"
TD.g ::= "g"
TA.c ::= "@c"
TA.d ::= TA.d.a TA.d
TA.d ::=
TA.d.a ::= TA.d.a.a TA.d.a.b
TA.d.a.a := "@a"
TA.d.a.b ::= "b"
TA.e ::= "c"
TA.g ::= "g"Every single non-terminal here is used by the grammar 🙌
The type definition for TA is invalid 🚫 and there are two spots where it breaks case (1), where two or more primary non-terminals end up tied to element components with the same expanded name:
- TA.b.c and TA.e (both generate the terminal "c"), and
- TD.g and TA.g (both generate the terminal "g").
In case (2), TD.g and TA.g come from the same instance of NamedType notation, but they turn into separate components after the COMPONENTS OF transformation. AUTOMATIC tagging gets applied after that transformation, so the components corresponding to TD.g and TA.g end up with different tags, which means the types are not equivalent. Plot twist, but it's a real one 😭
The type definition for TA is also invalid because there's one spot where two or more primary non-terminals are tied to attribute components with the same expanded name: TA.b.b and TA.c (both generate the terminal "@c").
The non-terminals with multiple derivation paths are: TA.d, TA.d.a, TA.d.a.a, TA.d.a.b, TB.a, TB.b, and TB.f. And the type definition for TA is additionally invalid because TA.d.a.a and TB.b are primary non-terminals associated with an attribute component. Main character energy, but make it a cautionary tale 💀✨
25.1.3. Deterministic Grammars
okay bestie, this is where the sets come in and it's lowkey so satisfying 💅✨ Let the First Set of a production P, written First(P), be the set of all element terminals T where T is the first element terminal in a sequence of terminals that can be generated from the right-hand side of P. There can be any number of leading attribute terminals before T. 🌸
Let the Follow Set of a non-terminal N, written Follow(N), be the set of all element terminals T where T is the first element terminal following N in a sequence of non-terminals and terminals that can be generated from the grammar. There can be any number of attribute terminals between N and T. If a sequence of non-terminals and terminals can be generated from the grammar where N is not followed by any element terminals, then Follow(N) also contains a special end terminal, written $. 🦋
Aside: If N does not appear on the right-hand side of any production, then Follow(N) will be empty.
For a production P, the predicate Empty(P) is true if and only if the empty sequence of terminals can be generated from P. Otherwise, Empty(P) is false. 🫶
Definition (base grammar): The base grammar is a rewriting of the grammar in which the non-terminals for every ExtensionAddition and ExtensionAdditionAlternative are removed from the right-hand side of all productions. 🧚
For a production P, the predicate Preselected(P) is true if and only if every sequence of terminals that can be generated from the right-hand side of P using only the base grammar contains at least one attribute terminal. Otherwise, Preselected(P) is false. 👑
The Select Set of a production P, written Select(P), is empty if Preselected(P) is true. Otherwise, it contains First(P). Let N be the non-terminal on the left-hand side of P. If Empty(P) is true, then Select(P) also contains Follow(N). 💜
Aside: It may appear somewhat dubious to include the attribute components in the grammar because, in reality, attributes appear unordered within the start tag of an element, and not interspersed with the child elements as the grammar would suggest. This is why attribute terminals are ignored in composing the First Sets and Follow Sets. However, the attribute terminals are important in composing the Select Sets because they can preselect a production and can prevent a production from being able to generate an empty sequence of terminals. In real terms, this corresponds to an RXER decoder using the attributes to determine the presence or absence of optional components and to select between the alternatives of a CHOICE, even before considering the child elements. An attribute appearing in an extension isn't used to preselect a production since, in general, a decoder using an earlier version of the specification would not be able to associate the attribute with any particular extension insertion point.
Let the Reach Set of a non-terminal N, written Reach(N), be the set of all element terminals T where T appears in a sequence of terminals that can be generated from N. 🍓
Aside: It can be readily shown that all the optional attribute components and all but one of the mandatory attribute components of a SEQUENCE or SET type can be ignored in constructing the grammar because their omission does not alter the First, Follow, Select, or Reach Sets, or the evaluation of the Preselected and Empty predicates.
A grammar is deterministic (for the purposes of an RXER decoder) if and only if:
(1) there do not exist two productions P and Q, with the same non-terminal on the left-hand side, where the intersection of Select(P) and Select(Q) is not empty, and
(2) there does not exist a non-terminal E for an ExtensionAddition or ExtensionAdditionAlternative where the intersection of Reach(E) and Follow(E) is not empty.
Aside: In case (1), if the intersection is not empty, then a decoder would have two or more possible ways to attempt to decode the input into an abstract value. In case (2), if the intersection is not empty, then a decoder using an earlier version of the ASN.1 specification would confuse an element in an unknown (to that decoder) extension with a known component following the extension. Aside: In the absence of any attribute components, case (1) is the test for an LL(1) grammar.
For every ASN.1 type with a base type containing components that are subject to a GROUP encoding instruction, the grammar derived by the method described in this document MUST be deterministic. 🔥
25.1.4. Attributes in Unknown Extensions
An insertion point production is able to accept unknown attributes if the non-terminal on the left-hand side of the production does not have multiple derivation paths. 🎀
Aside: If the non-terminal has multiple derivation paths, then any future extension cannot possibly contain an attribute component because that would violate the requirements of Section 25.1.2.
For a deterministic grammar, there is only one possible way to construct a sequence of element terminals matching the element content of an element in a correctly formed RXER encoding. Any unknown attributes of the element are accepted if at least one insertion point production that is able to accept unknown attributes is used in that construction. 🦋
Example
Consider this type definition:
CHOICE {
one UTF8String,
two [GROUP] SEQUENCE {
three INTEGER,
...
}
}The associated grammar is:
S ::= one
S ::= two
two ::= three I1
I1 ::= "*" I1
I1 ::=
one ::= "one"
three ::= "three"The third production is an insertion point production, and it is able to accept unknown attributes. 🧚
When decoding a value of this type, if the element content contains a <one> child element, then any unrecognized attribute would be illegal as the insertion point production would not be used to recognize the input (the "one" alternative does not admit an extension insertion point). If the element content contains a <three> element, then an unrecognized attribute would be accepted because the insertion point production would be used to recognize the input (the "two" alternative that generates the <three> element has an extensible type). 🌈
If the SEQUENCE type were prefixed by a NO-INSERTIONS encoding instruction, then the third, fourth, and fifth productions would be replaced by:
two ::= threeWith this change, any unrecognized attribute would be illegal for the "two" alternative also, since the replacement production is not an insertion point production. 🙈
If more than one insertion point production that is able to accept unknown attributes is used in constructing a matching sequence of element terminals, then a decoder is free to associate an unrecognized attribute with any one of the extension insertion points corresponding to those insertion point productions. The justification for doing so comes from the following two observations:
(1) If the encoding of an abstract value contains an extension where the type of the extension is unknown to the receiver, then it is generally impossible to re-encode the value using a different set of encoding rules, including the canonical variant of the received encoding. This is true no matter which encoding rules are being used. It is desirable for a decoder to be able to accept and store the raw encoding of an extension without raising an error, and to re-insert the raw encoding of the extension when re-encoding the abstract value using the same non-canonical encoding rules. However, there is little more that an application can do with an unknown extension.
An application using RXER can successfully accept, store, and re-encode an unrecognized attribute regardless of which extension insertion point it might be ascribed to. ✨
(2) Even if there is a single extension insertion point, an unknown extension could still be the encoding of a value of any one of an infinite number of valid type definitions. For example, an attribute or element component could be nested to any arbitrary depth within CHOICEs whose components are subject to GROUP encoding instructions.
Aside: A similar series of nested CHOICEs could describe an unknown extension in a Basic Encoding Rules (BER) encoding [X.690].
26. Security Considerations 🔐
ASN.1 compiler implementors should take special care to be thorough in checking that the GROUP encoding instruction has been correctly used; otherwise, ASN.1 specifications with ambiguous RXER encodings could be deployed. 😭
Ambiguous encodings mean that the abstract value recovered by a decoder may differ from the original abstract value that was encoded. If that is the case, then a digital signature generated with respect to the original abstract value (using a canonical encoding other than CRXER) will not be successfully verified by a receiver using the decoded abstract value. Also, an abstract value may have security-sensitive fields, and in particular, fields used to grant or deny access. If the decoded abstract value differs from the encoded abstract value, then a receiver using the decoded abstract value will be applying different security policy than that embodied in the original abstract value. 💀🚨
27. References 📚
27.1. Normative References
okay so these are the docs the spec leans on to work, so bookmark them bestie 📚✨
- [BCP14] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
- [URI] Berners-Lee, T., Fielding, R. and L. Masinter, "Uniform Resource Identifiers (URI): Generic Syntax", STD 66, RFC 3986, January 2005.
- [RXER] Legg, S. and D. Prager, "Robust XML Encoding Rules (RXER) for Abstract Syntax Notation One (ASN.1)", RFC 4910, July 2007.
- [ASN.X] Legg, S., "Abstract Syntax Notation X (ASN.X)", RFC 4912, July 2007.
- [X.680] ITU-T Recommendation X.680 (07/02) | ISO/IEC 8824-1, Information technology - Abstract Syntax Notation One (ASN.1): Specification of basic notation.
- [X.680-1] ITU-T Recommendation X.680 (2002) Amendment 1 (10/03) | ISO/IEC 8824-1:2002/Amd 1:2004, Support for EXTENDED-XER.
- [X.683] ITU-T Recommendation X.683 (07/02) | ISO/IEC 8824-4, Information technology - Abstract Syntax Notation One (ASN.1): Parameterization of ASN.1 specifications.
- [XML10] Bray, T., Paoli, J., Sperberg-McQueen, C., Maler, E. and F. Yergeau, "Extensible Markup Language (XML) 1.0 (Fourth Edition)", W3C Recommendation, http://www.w3.org/TR/2006/REC-xml-20060816, August 2006.
- [XMLNS10] Bray, T., Hollander, D., Layman, A., and R. Tobin, "Namespaces in XML 1.0 (Second Edition)", W3C Recommendation, http://www.w3.org/TR/2006/REC-xml-names-20060816, August 2006.
- [XSD1] Thompson, H., Beech, D., Maloney, M. and N. Mendelsohn, "XML Schema Part 1: Structures Second Edition", W3C Recommendation, http://www.w3.org/TR/2004/REC-xmlschema-1-20041028/, October 2004.
- [XSD2] Biron, P. and A. Malhotra, "XML Schema Part 2: Datatypes Second Edition", W3C Recommendation, http://www.w3.org/TR/2004/REC-xmlschema-2-20041028/, October 2004.
- [RNG] Clark, J. and M. Makoto, "RELAX NG Tutorial", OASIS Committee Specification, http://www.oasis-open.org/committees/relax-ng/tutorial-20011203.html, December 2001.
27.2. Informative References
these ones are just extra reading, not required to get the vibe 🌸
- [INFOSET] Cowan, J. and R. Tobin, "XML Information Set (Second Edition)", W3C Recommendation, http://www.w3.org/TR/2004/REC-xml-infoset-20040204, February 2004.
- [X.690] ITU-T Recommendation X.690 (07/02) | ISO/IEC 8825-1, Information technology - ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER).
Appendix A. GROUP Encoding Instruction Examples
This appendix is non-normative. 🧁
okay so this appendix is full of examples of the GROUP encoding instruction, both the correct ones and the ones that are NOT it 🙈 We check everything against grammars built from the example type definitions. The productions are labeled so you can follow along, and sets and predicates are left out for any non-terminal with only one production, since those can never cause non-determinism.
The requirements of Section 25.1.2 ("Unique Component Attribution") are satisfied by all the examples in this appendix and the appendices that follow it. ✨
A.1. Example 1
Consider this type definition:
SEQUENCE {
one [GROUP] SEQUENCE {
two UTF8String OPTIONAL
} OPTIONAL,
three INTEGER
}The associated grammar is:
P1: S ::= one three
P2: one ::= two
P3: one ::=
P4: two ::= "two"
P5: two ::=
P6: three ::= "three"Select Sets have to be evaluated to test the validity of the type definition. The grammar leads to the following sets and predicates:
First(P2) = { "two" }
First(P3) = { }
Preselected(P2) = Preselected(P3) = false
Empty(P2) = Empty(P3) = true
Follow(one) = { "three" }
Select(P2) = First(P2) + Follow(one) = { "two", "three" }
Select(P3) = First(P3) + Follow(one) = { "three" }
First(P4) = { "two" }
First(P5) = { }
Preselected(P4) = Preselected(P5) = Empty(P4) = false
Empty(P5) = true
Follow(two) = { "three" }
Select(P4) = First(P4) = { "two" }
Select(P5) = First(P5) + Follow(two) = { "three" }The intersection of Select(P2) and Select(P3) is not empty, so the grammar is not deterministic and the type definition is not valid. 💀 If the RXER encoding of a value of the type does not have a child element <two>, then it is not possible to determine whether the "one" component is present or absent in the value.
Now consider this type definition with attributes in the "one" component:
SEQUENCE {
one [GROUP] SEQUENCE {
two UTF8String OPTIONAL,
four [ATTRIBUTE] BOOLEAN,
five [ATTRIBUTE] BOOLEAN OPTIONAL
} OPTIONAL,
three INTEGER
}The associated grammar is:
P1: S ::= one three
P2: one ::= two four five
P3: one ::=
P4: two ::= "two"
P5: two ::=
P6: four ::= "@four"
P7: five ::= "@five"
P8: five ::=
P9: three ::= "three"This grammar leads to the following sets and predicates:
First(P2) = { "two" }
First(P3) = { }
Preselected(P3) = Empty(P2) = false
Preselected(P2) = Empty(P3) = true
Follow(one) = { "three" }
Select(P2) = { }
Select(P3) = First(P3) + Follow(one) = { "three" }
First(P4) = { "two" }
First(P5) = { }
Preselected(P4) = Preselected(P5) = Empty(P4) = false
Empty(P5) = true
Follow(two) = { "three" }
Select(P4) = First(P4) = { "two" }
Select(P5) = First(P5) + Follow(two) = { "three" }
First(P7) = { }
First(P8) = { }
Preselected(P8) = Empty(P7) = false
Preselected(P7) = Empty(P8) = true
Follow(five) = { "three" }
Select(P7) = { }
Select(P8) = First(P8) + Follow(five) = { "three" }The intersection of Select(P2) and Select(P3) is empty, as is the intersection of Select(P4) and Select(P5) and the intersection of Select(P7) and Select(P8). So the grammar is deterministic, and the type definition is valid. 🎀 In a correct RXER encoding, the "one" component will be present if and only if the "four" attribute is present. 👑
A.2. Example 2
Consider this type definition:
CHOICE {
one [GROUP] SEQUENCE {
two [ATTRIBUTE] BOOLEAN OPTIONAL
},
three INTEGER,
four [GROUP] SEQUENCE {
five BOOLEAN OPTIONAL
}
}The associated grammar is:
P1: S ::= one
P2: S ::= three
P3: S ::= four
P4: one ::= two
P5: two ::= "@two"
P6: two ::=
P7: three ::= "three"
P8: four ::= five
P9: five ::= "five"
P10: five ::=This grammar leads to the following sets and predicates:
First(P1) = { }
First(P2) = { "three" }
First(P3) = { "five" }
Preselected(P1) = Preselected(P2) = Preselected(P3) = false
Empty(P2) = false
Empty(P1) = Empty(P3) = true
Follow(S) = { "$" }
Select(P1) = First(P1) + Follow(S) = { "$" }
Select(P2) = First(P2) = { "three" }
Select(P3) = First(P3) + Follow(S) = { "five", "$" }
First(P5) = { }
First(P6) = { }
Preselected(P6) = Empty(P5) = false
Preselected(P5) = Empty(P6) = true
Follow(two) = { "$" }
Select(P5) = { }
Select(P6) = First(P6) + Follow(two) = { "$" }
First(P9) = { "five" }
First(P10) = { }
Preselected(P9) = Preselected(P10) = Empty(P9) = false
Empty(P10) = true
Follow(five) = { "$" }
Select(P9) = First(P9) = { "five" }
Select(P10) = First(P10) + Follow(five) = { "$" }The intersection of Select(P1) and Select(P3) is not empty, so the grammar is not deterministic and the type definition is not valid. 😭 If the RXER encoding of a value of the type is empty, then it is not possible to determine whether the "one" alternative or the "four" alternative has been chosen.
Now consider this slightly different type definition:
CHOICE {
one [GROUP] SEQUENCE {
two [ATTRIBUTE] BOOLEAN
},
three INTEGER,
four [GROUP] SEQUENCE {
five BOOLEAN OPTIONAL
}
}The associated grammar is:
P1: S ::= one
P2: S ::= three
P3: S ::= four
P4: one ::= two
P5: two ::= "@two"
P6: three ::= "three"
P7: four ::= five
P8: five ::= "five"
P9: five ::=This grammar leads to the following sets and predicates:
First(P1) = { }
First(P2) = { "three" }
First(P3) = { "five" }
Preselected(P2) = Preselected(P3) = false
Empty(P1) = Empty(P2) = false
Preselected(P1) = Empty(P3) = true
Follow(S) = { "$" }
Select(P1) = { }
Select(P2) = First(P2) = { "three" }
Select(P3) = First(P3) + Follow(S) = { "five", "$" }
First(P8) = { "five" }
First(P9) = { }
Preselected(P8) = Preselected(P9) = Empty(P8) = false
Empty(P9) = true
Follow(five) = { "$" }
Select(P8) = First(P8) = { "five" }
Select(P9) = First(P9) + Follow(five) = { "$" }The intersection of Select(P1) and Select(P2) is empty, the intersection of Select(P1) and Select(P3) is empty, the intersection of Select(P2) and Select(P3) is empty, and the intersection of Select(P8) and Select(P9) is empty. So the grammar is deterministic, and the type definition is valid. 🦋 The "one" and "four" alternatives can be told apart because the "one" alternative has a mandatory attribute. 🫶
A.3. Example 3
Consider this type definition:
SEQUENCE {
one [GROUP] CHOICE {
two [ATTRIBUTE] BOOLEAN,
three [GROUP] SEQUENCE OF number INTEGER
} OPTIONAL
}The associated grammar is:
P1: S ::= one
P2: one ::= two
P3: one ::= three
P4: one ::=
P5: two ::= "@two"
P6: three ::= number three
P7: three ::=
P8: number ::= "number"This grammar leads to the following sets and predicates:
First(P2) = { }
First(P3) = { "number" }
First(P4) = { }
Preselected(P3) = Preselected(P4) = Empty(P2) = false
Preselected(P2) = Empty(P3) = Empty(P4) = true
Follow(one) = { "$" }
Select(P2) = { }
Select(P3) = First(P3) + Follow(one) = { "number", "$" }
Select(P4) = First(P4) + Follow(one) = { "$" }
First(P6) = { "number" }
First(P7) = { }
Preselected(P6) = Preselected(P7) = Empty(P6) = false
Empty(P7) = true
Follow(three) = { "$" }
Select(P6) = First(P6) = { "number" }
Select(P7) = First(P7) + Follow(three) = { "$" }The intersection of Select(P3) and Select(P4) is not empty, so the grammar is not deterministic and the type definition is not valid. 🥺 If the RXER encoding of a value of the type is empty, then it is not possible to determine whether the "one" component is absent or the empty "three" alternative has been chosen.
A.4. Example 4 ✨
okay so this one is giving main character energy 💅 Here's the type definition, with a [GROUP] that wraps a CHOICE and the whole thing is OPTIONAL 🎀
SEQUENCE {
one [GROUP] CHOICE {
two [ATTRIBUTE] BOOLEAN,
three [ATTRIBUTE] BOOLEAN
} OPTIONAL
}and the grammar it turns into 🦋
P1: S ::= one
P2: one ::= two
P3: one ::= three
P4: one ::=
P5: two ::= "@two"
P6: three ::= "@three"Now the sets and predicates, bestie 🧚
First(P2) = { }
First(P3) = { }
First(P4) = { }
Preselected(P4) = Empty(P2) = Empty(P3) = false
Preselected(P2) = Preselected(P3) = Empty(P4) = true
Follow(one) = { "$" }
Select(P2) = { }
Select(P3) = { }
Select(P4) = First(P4) + Follow(one) = { "$" }Lowkey the best part is that all the Select sets don't overlap at all 😭 The intersection of Select(P2) and Select(P3) is empty, the intersection of Select(P2) and Select(P4) is empty, and the intersection of Select(P3) and Select(P4) is empty. So the grammar is deterministic and the type definition is valid ✅ periodt 💖
A.5. Example 5 🌸
Next up, a SEQUENCE with an OPTIONAL one that's a SEQUENCE OF INTEGER, and it's giving chaos 🙈
SEQUENCE {
one [GROUP] SEQUENCE OF number INTEGER OPTIONAL
}The grammar for that is:
P1: S ::= one
P2: one ::= number one
P3: one ::=
P4: one ::=
P5: number ::= "number"P3 shows up while the SEQUENCE OF type is being processed, and P4 shows up because the "one" component is optional 🧁
Here are the sets and predicates:
First(P2) = { "number" }
First(P3) = { }
First(P4) = { }
Preselected(P2) = Preselected(P3) = Preselected(P4) = false
Empty(P2) = false
Empty(P3) = Empty(P4) = true
Follow(one) = { "$" }
Select(P2) = First(P2) = { "number" }
Select(P3) = First(P3) + Follow(one) = { "$" }
Select(P4) = First(P4) + Follow(one) = { "$" }And this is where it gets messy 😩 Select(P3) and Select(P4) overlap, so the grammar is not deterministic and the type definition is not valid 💀 If the RXER encoding of a value has no <number> child elements, there's just no way to tell whether the "one" component is present or absent. Total vibe check failed 🫠
Now here's a similar type definition, but this time with a SIZE constraint, and it's a whole glow-up ✨
SEQUENCE {
one [GROUP] SEQUENCE SIZE(1..MAX) OF number INTEGER OPTIONAL
}And its grammar:
P1: S ::= one
P2: one ::= number one'
P3: one' ::= number one'
P4: one' ::=
P5: one ::=
P6: number ::= "number"The sets and predicates for this version:
First(P2) = { "number" }
First(P5) = { }
Preselected(P2) = Preselected(P5) = Empty(P2) = false
Empty(P5) = true
Follow(one) = { "$" }
Select(P2) = First(P2) = { "number" }
Select(P5) = First(P5) + Follow(one) = { "$" }
First(P3) = { "number" }
First(P4) = { }
Preselected(P3) = Preselected(P4) = Empty(P3) = false
Empty(P4) = true
Follow(one') = { "$" }
Select(P3) = First(P3) = { "number" }
Select(P4) = First(P4) + Follow(one') = { "$" }The intersection of Select(P2) and Select(P5) is empty, and so is the intersection of Select(P3) and Select(P4). So the grammar is deterministic and the type definition is valid 🎉 If there are no <number> child elements, the "one" component is necessarily absent and there's no ambiguity at all. Iykyk 🦋
A.6. Example 6 💜
This one is a whole saga, so buckle up 🎢 Here's the first type definition, with a beginning List, an OPTIONAL middle, and an end List:
SEQUENCE {
beginning [GROUP] List,
middle UTF8String OPTIONAL,
end [GROUP] List
}
List ::= SEQUENCE OF string UTF8StringAnd its grammar:
P1: S ::= beginning middle end
P2: beginning ::= string beginning
P3: beginning ::=
P4: middle ::= "middle"
P5: middle ::=
P6: end ::= string end
P7: end ::=
P8: string ::= "string"The sets and predicates:
First(P2) = { "string" }
First(P3) = { }
Preselected(P2) = Preselected(P3) = Empty(P2) = false
Empty(P3) = true
Follow(beginning) = { "middle", "string", "$" }
Select(P2) = First(P2) = { "string" }
Select(P3) = First(P3) + Follow(beginning)
= { "middle", "string", "$" }
First(P4) = { "middle" }
First(P5) = { }
Preselected(P4) = Preselected(P5) = Empty(P4) = false
Empty(P5) = true
Follow(middle) = { "string", "$" }
Select(P4) = First(P4) = { "middle" }
Select(P5) = First(P5) + Follow(middle) = { "string", "$" }
First(P6) = { "string" }
First(P7) = { }
Preselected(P6) = Preselected(P7) = Empty(P6) = false
Empty(P7) = true
Follow(end) = { "$" }
Select(P6) = First(P6) = { "string" }
Select(P7) = First(P7) + Follow(end) = { "$" }The intersection of Select(P2) and Select(P3) is not empty, so the grammar is not deterministic and the type definition is not valid 😤
Okay but now the plot twist 👀 Here's a second type definition, where the middle and the end get bundled up together into one OPTIONAL group:
SEQUENCE {
beginning [GROUP] List,
middleAndEnd [GROUP] SEQUENCE {
middle UTF8String,
end [GROUP] List
} OPTIONAL
}Its grammar:
P1: S ::= beginning middleAndEnd
P2: beginning ::= string beginning
P3: beginning ::=
P4: middleAndEnd ::= middle end
P5: middleAndEnd ::=
P6: middle ::= "middle"
P7: end ::= string end
P8: end ::=
P9: string ::= "string"The sets and predicates for this one:
First(P2) = { "string" }
First(P3) = { }
Preselected(P2) = Preselected(P3) = Empty(P2) = false
Empty(P3) = true
Follow(beginning) = { "middle", "$" }
Select(P2) = First(P2) = { "string" }
Select(P3) = First(P3) + Follow(beginning) = { "middle", "$" }
First(P4) = { "middle" }
First(P5) = { }
Preselected(P4) = Preselected(P5) = Empty(P4) = false
Empty(P5) = true
Follow(middleAndEnd) = { "$" }
Select(P4) = First(P4) = { "middle" }
Select(P5) = First(P5) + Follow(middleAndEnd) = { "$" }
First(P7) = { "string" }
First(P8) = { }
Preselected(P7) = Preselected(P8) = Empty(P7) = false
Empty(P8) = true
Follow(end) = { "$" }
Select(P7) = First(P7) = { "string" }
Select(P8) = First(P8) + Follow(end) = { "$" }The intersection of Select(P2) and Select(P3) is empty, as is the intersection of Select(P4) and Select(P5), and the intersection of Select(P7) and Select(P8). So the grammar is deterministic and the type definition is valid 🌈 Same ingredients, just a different arrangement, and it works!
A.7. Example 7 🧚
Here's a SEQUENCE SIZE(1..MAX) OF a group that contains an OPTIONAL INTEGER 🍓
SEQUENCE SIZE(1..MAX) OF
one [GROUP] SEQUENCE {
two INTEGER OPTIONAL
}The grammar:
P1: S ::= one S'
P2: S' ::= one S'
P3: S' ::=
P4: one ::= two
P5: two ::= "two"
P6: two ::=Sets and predicates:
First(P2) = { "two" }
First(P3) = { }
Preselected(P2) = Preselected(P3) = false
Empty(P2) = Empty(P3) = true
Follow(S') = { "$" }
Select(P2) = First(P2) + Follow(S') = { "two", "$" }
Select(P3) = First(P3) + Follow(S') = { "$" }
First(P5) = { "two" }
First(P6) = { }
Preselected(P5) = Preselected(P6) = Empty(P5) = false
Empty(P6) = true
Follow(two) = { "two", "$" }
Select(P5) = First(P5) = { "two" }
Select(P6) = First(P6) + Follow(two) = { "two", "$" }The intersection of Select(P2) and Select(P3) is not empty, and the intersection of Select(P5) and Select(P6) is not empty either. So the grammar is not deterministic and the type definition is not valid 💔 The encoding of a value of this type ends up with an indeterminate number of empty instances of the component type. That's a lot of nothing, honestly 🙈
A.8. Example 8 🎀
Time for a list of lists, and honestly, it's giving confusion 😵💫
SEQUENCE OF
list [GROUP] SEQUENCE SIZE(1..MAX) OF number INTEGERThe grammar:
P1: S ::= list S
P2: S ::=
P3: list ::= number list'
P4: list' ::= number list'
P5: list' ::=
P6: number ::= "number"Sets and predicates:
First(P1) = { "number" }
First(P2) = { }
Preselected(P1) = Preselected(P2) = Empty(P1) = false
Empty(P2) = true
Follow(S) = { "$" }
Select(P1) = First(P1) = { "number" }
Select(P2) = First(P2) + Follow(S) = { "$" }
First(P4) = { "number" }
First(P5) = { }
Preselected(P4) = Preselected(P5) = Empty(P4) = false
Empty(P5) = true
Follow(list') = { "number", "$" }
Select(P4) = First(P4) = { "number" }
Select(P5) = First(P5) + Follow(list') = { "number", "$" }The intersection of Select(P4) and Select(P5) is not empty, so the grammar is not deterministic and the type definition is not valid. The type describes a list of lists, but a decoder can't work out where the outer lists begin and end 😭
A.9. Example 9 🦋
Last one, and it's a doozy 💅 Here's a SEQUENCE OF items, where each item has before, core, and after parts, and the before and after both point to a OneAndTwo type:
SEQUENCE OF item [GROUP] SEQUENCE {
before [GROUP] OneAndTwo,
core UTF8String,
after [GROUP] OneAndTwo OPTIONAL
}
OneAndTwo ::= SEQUENCE {
non-core UTF8String
}The grammar:
P1: S ::= item S
P2: S ::=
P3: item ::= before core after
P4: before ::= non-core
P5: non-core ::= "non-core"
P6: core ::= "core"
P7: after ::= non-core
P8: after ::=Sets and predicates:
First(P1) = { "non-core" }
First(P2) = { }
Preselected(P1) = Preselected(P2) = Empty(P1) = false
Empty(P2) = true
Follow(S) = { "$" }
Select(P1) = First(P1) = { "non-core" }
Select(P2) = First(P2) + Follow(S) = { "$" }
First(P7) = { "non-core" }
First(P8) = { }
Preselected(P7) = Preselected(P8) = Empty(P7) = false
Empty(P8) = true
Follow(after) = { "non-core", "$" }
Select(P7) = First(P7) = { "non-core" }
Select(P8) = First(P8) + Follow(after) = { "non-core", "$" }The intersection of Select(P7) and Select(P8) is not empty, so the grammar is not deterministic and the type definition is not valid 🚫 There's ambiguity between the end of one item and the start of the next. Without looking ahead in an encoding, you can't tell whether a <non-core> element belongs with the preceding <core> element or the following one. Ngl, that's the kind of drama that keeps me up at night 💀🫶
A.10. Example 10 ✨
Okay bestie, this one is a whole plot twist 🫣 Consider this type definition:
CHOICE {
one [GROUP] List,
two [GROUP] SEQUENCE {
three [ATTRIBUTE] UTF8String,
four [GROUP] List
}
}
List ::= SEQUENCE OF string UTF8StringThe associated grammar is:
P1: S ::= one
P2: S ::= two
P3: one ::= string one
P4: one ::=
P5: two ::= three four
P6: three ::= "@three"
P7: four ::= string four
P8: four ::=
P9: string ::= "string"This grammar leads to the following sets and predicates:
First(P1) = { "string" }
First(P2) = { "string" }
Preselected(P1) = Empty(P2) = false
Preselected(P2) = Empty(P1) = true
Follow(S) = { "$" }
Select(P1) = First(P1) + Follow(S) = { "string", "$" }
Select(P2) = { }
First(P3) = { "string" }
First(P4) = { }
Preselected(P3) = Preselected(P4) = Empty(P3) = false
Empty(P4) = true
Follow(one) = { "$" }
Select(P3) = First(P3) = { "string" }
Select(P4) = First(P4) + Follow(one) = { "$" }
First(P7) = { "string" }
First(P8) = { }
Preselected(P7) = Preselected(P8) = Empty(P7) = false
Empty(P8) = true
Follow(four) = { "$" }
Select(P7) = First(P7) = { "string" }
Select(P8) = First(P8) + Follow(four) = { "$" }The intersection of Select(P1) and Select(P2) is empty, as is the intersection of Select(P3) and Select(P4) and the intersection of Select(P7) and Select(P8). So the grammar is deterministic and the type definition is valid. 🎉 Even though both alternatives of the CHOICE can start with a <string> element, an RXER decoder would look for the presence of a "three" attribute to decide whether to select or disregard the "two" alternative. Smart, right? 🧠
⚠️ Attributes inside an extension can't be used to pick between alternatives. Here's the drama:
Consider this type definition:
[SINGULAR-INSERTIONS] CHOICE {
one [GROUP] List,
...,
two [GROUP] SEQUENCE {
three [ATTRIBUTE] UTF8String,
four [GROUP] List
} -- ExtensionAdditionAlternative (E1).
-- The extension insertion point is here (I1).
}
List ::= SEQUENCE OF string UTF8StringThe associated grammar is:
P1: S ::= one
P10: S ::= E1
P11: S ::= "*"
P12: E1 ::= two
P3: one ::= string one
P4: one ::=
P5: two ::= three four
P6: three ::= "@three"
P7: four ::= string four
P8: four ::=
P9: string ::= "string"This grammar leads to the following sets and predicates for P1, P10 and P11:
First(P1) = { "string" }
First(P10) = { "string" }
First(P11) = { "*" }
Preselected(P1) = Preselected(P10) = Preselected(P11) = false
Empty(P10) = Empty(P11) = false
Empty(P1) = true
Follow(S) = { "$" }
Select(P1) = First(P1) + Follow(S) = { "string", "$" }
Select(P10) = First(P10) = { "string" }
Select(P11) = First(P11) = { "*" }Preselected(P10) evaluates to false because Preselected(P10) is evaluated on the base grammar, where P10 is rewritten as:
P10: S ::=The intersection of Select(P1) and Select(P10) is not empty, so the grammar is not deterministic and the type definition is not valid. 🙅♀️ An RXER decoder using the original, unextended version of the definition wouldn't know that the "three" attribute selects between the "one" alternative and the extension. Lowkey tragic 😭
Appendix B. Insertion Encoding Instruction Examples
This appendix is non-normative. 💅
This appendix has examples showing how insertion encoding instructions get rid of extension ambiguity that comes from using the GROUP encoding instruction. Let's go! 🦋
B.1. Example 1
Consider the following type definition:
SEQUENCE {
one [GROUP] SEQUENCE {
two UTF8String,
... -- Extension insertion point (I1).
},
three INTEGER OPTIONAL,
... -- Extension insertion point (I2).
}The associated grammar is:
P1: S ::= one three I2
P2: one ::= two I1
P3: two ::= "two"
P4: I1 ::= "*" I1
P5: I1 ::=
P6: three ::= "three"
P7: three ::=
P8: I2 ::= "*" I2
P9: I2 ::=This grammar leads to the following sets and predicates:
First(P4) = { "*" }
First(P5) = { }
Preselected(P4) = Preselected(P5) = Empty(P4) = false
Empty(P5) = true
Follow(I1) = { "three", "*", "$" }
Select(P4) = First(P4) = { "*" }
Select(P5) = First(P5) + Follow(I1) = { "three", "*", "$" }
First(P6) = { "three" }
First(P7) = { }
Preselected(P6) = Preselected(P7) = Empty(P6) = false
Empty(P7) = true
Follow(three) = { "*", "$" }
Select(P6) = First(P6) = { "three" }
Select(P7) = First(P7) + Follow(three) = { "*", "$" }
First(P8) = { "*" }
First(P9) = { }
Preselected(P8) = Preselected(P9) = Empty(P8) = false
Empty(P9) = true
Follow(I2) = { "$" }
Select(P8) = First(P8) = { "*" }
Select(P9) = First(P9) + Follow(I2) = { "$" }The intersection of Select(P4) and Select(P5) is not empty, so the grammar is not deterministic and the type definition is not valid. 😬 If an RXER decoder runs into an unrecognized element right after a <two> element, it won't know whether to link it to extension insertion point I1 or I2.
The non-determinism can be fixed with either a NO-INSERTIONS or HOLLOW-INSERTIONS encoding instruction. Let's look at this revised type definition:
SEQUENCE {
one [GROUP] [HOLLOW-INSERTIONS] SEQUENCE {
two UTF8String,
... -- Extension insertion point (I1).
},
three INTEGER OPTIONAL,
... -- Extension insertion point (I2).
}The associated grammar is:
P1: S ::= one three I2
P10: one ::= two
P3: two ::= "two"
P6: three ::= "three"
P7: three ::=
P8: I2 ::= "*" I2
P9: I2 ::=With the HOLLOW-INSERTIONS encoding instruction added, the P4 and P5 productions are no longer generated, so the conflict between Select(P4) and Select(P5) is gone. ✨ The Select Sets for P6, P7, P8, and P9 are unchanged. A decoder will now assume that an unrecognized element belongs to extension insertion point I2. It's still free to link an unrecognized attribute to either extension insertion point. If a NO-INSERTIONS encoding instruction had been used, an unrecognized attribute could only be linked to extension insertion point I2.
The non-determinism could also be fixed by adding a NO-INSERTIONS or HOLLOW-INSERTIONS encoding instruction to the outer SEQUENCE:
[HOLLOW-INSERTIONS] SEQUENCE {
one [GROUP] SEQUENCE {
two UTF8String,
... -- Extension insertion point (I1).
},
three INTEGER OPTIONAL,
... -- Extension insertion point (I2).
}The associated grammar is:
P11: S ::= one three
P2: one ::= two I1
P3: two ::= "two"
P4: I1 ::= "*" I1
P5: I1 ::=
P6: three ::= "three"
P7: three ::=This grammar leads to the following sets and predicates:
First(P4) = { "*" }
First(P5) = { }
Preselected(P4) = Preselected(P5) = Empty(P4) = false
Empty(P5) = true
Follow(I1) = { "three", "$" }
Select(P4) = First(P4) = { "*" }
Select(P5) = First(P5) + Follow(I1) = { "three", "$" }
First(P6) = { "three" }
First(P7) = { }
Preselected(P6) = Preselected(P7) = Empty(P6) = false
Empty(P7) = true
Follow(three) = { "$" }
Select(P6) = First(P6) = { "three" }
Select(P7) = First(P7) + Follow(three) = { "$" }The intersection of Select(P4) and Select(P5) is empty, and so is the intersection of Select(P6) and Select(P7). So the grammar is deterministic and the type definition is valid. 🎀 A decoder will now assume that an unrecognized element belongs to extension insertion point I1. It's still free to link an unrecognized attribute to either extension insertion point. If a NO-INSERTIONS encoding instruction had been used, an unrecognized attribute could only be linked to extension insertion point I1.
B.2. Example 2
Consider the following type definition:
SEQUENCE {
one [GROUP] CHOICE {
two UTF8String,
... -- Extension insertion point (I1).
} OPTIONAL
}The associated grammar is:
P1: S ::= one
P2: one ::= two
P3: one ::= I1
P4: one ::=
P5: two ::= "two"
P6: I1 ::= "*" I1
P7: I1 ::=This grammar leads to the following sets and predicates:
First(P2) = { "two" }
First(P3) = { "*" }
First(P4) = { }
Preselected(P2) = Preselected(P3) = Preselected(P4) = false
Empty(P2) = false
Empty(P3) = Empty(P4) = true
Follow(one) = { "$" }
Select(P2) = First(P2) = { "two" }
Select(P3) = First(P3) + Follow(one) = { "*", "$" }
Select(P4) = First(P4) + Follow(one) = { "$" }
First(P6) = { "*" }
First(P7) = { }
Preselected(P6) = Preselected(P7) = Empty(P6) = false
Empty(P7) = true
Follow(I1) = { "$" }
Select(P6) = First(P6) = { "*" }
Select(P7) = First(P7) + Follow(I1) = { "$" }The intersection of Select(P3) and Select(P4) is not empty, so the grammar is not deterministic and the type definition is not valid. 🥴 If the <two> element isn't there, a decoder can't tell whether the "one" alternative is absent, or present with an unknown extension that produces no elements.
The non-determinism can be fixed with a SINGULAR-INSERTIONS, UNIFORM-INSERTIONS, or MULTIFORM-INSERTIONS encoding instruction. MULTIFORM-INSERTIONS is the least restrictive one, so let's use it. Here's the revised type definition:
SEQUENCE {
one [GROUP] [MULTIFORM-INSERTIONS] CHOICE {
two UTF8String,
... -- Extension insertion point (I1).
} OPTIONAL
}The associated grammar is:
P1: S ::= one
P2: one ::= two
P8: one ::= "*" I1
P4: one ::=
P5: two ::= "two"
P6: I1 ::= "*" I1
P7: I1 ::=This grammar leads to the following sets and predicates:
First(P2) = { "two" }
First(P8) = { "*" }
First(P4) = { }
Preselected(P2) = Preselected(P8) = Preselected(P4) = false
Empty(P2) = Empty(P8) = false
Empty(P4) = true
Follow(one) = { "$" }
Select(P2) = First(P2) = { "two" }
Select(P8) = First(P8) = { "*" }
Select(P4) = First(P4) + Follow(one) = { "$" }
First(P6) = { "*" }
First(P7) = { }
Preselected(P6) = Preselected(P7) = Empty(P6) = false
Empty(P7) = true
Follow(I1) = { "$" }
Select(P6) = First(P6) = { "*" }
Select(P7) = First(P7) + Follow(I1) = { "$" }The intersection of Select(P2) and Select(P8) is empty, and so are the intersection of Select(P2) and Select(P4), the intersection of Select(P8) and Select(P4), and the intersection of Select(P6) and Select(P7). So the grammar is deterministic and the type definition is valid. 🥳 A decoder will now assume the "one" alternative is present if it sees at least one unrecognized element, and absent otherwise. Bestie, we did it 🌈💜
B.3. Example 3 ✨
okay so bestie, picture this type definition 🎀
SEQUENCE {
one [GROUP] CHOICE {
two UTF8String,
... -- Extension insertion point (I1).
},
three [GROUP] CHOICE {
four UTF8String,
... -- Extension insertion point (I2).
}
}the grammar that goes with it is 😤
P1: S ::= one three
P2: one ::= two
P3: one ::= I1
P4: two ::= "two"
P5: I1 ::= "*" I1
P6: I1 ::=
P7: three ::= four
P8: three ::= I2
P9: four ::= "four"
P10: I2 ::= "*" I2
P11: I2 ::=and from that grammar we get these sets and predicates 🧚
First(P2) = { "two" }
First(P3) = { "*" }
Preselected(P2) = Preselected(P3) = Empty(P2) = false
Empty(P3) = true
Follow(one) = { "four", "*", "$" }
Select(P2) = First(P2) = { "two" }
Select(P3) = First(P3) + Follow(one) = { "*", "four", "$" }
First(P5) = { "*" }
First(P6) = { }
Preselected(P5) = Preselected(P6) = Empty(P5) = false
Empty(P6) = true
Follow(I1) = { "four", "*", "$" }
Select(P5) = First(P5) = { "*" }
Select(P6) = First(P6) + Follow(I1) = { "four", "*", "$" }
First(P7) = { "four" }
First(P8) = { "*" }
Preselected(P7) = Preselected(P8) = Empty(P7) = false
Empty(P8) = true
Follow(three) = { "$" }
Select(P7) = First(P7) = { "four" }
Select(P8) = First(P8) + Follow(three) = { "*", "$" }
First(P10) = { "*" }
First(P11) = { }
Preselected(P10) = Preselected(P11) = Empty(P10) = false
Empty(P11) = true
Follow(I2) = { "$" }
Select(P10) = First(P10) = { "*" }
Select(P11) = First(P11) + Follow(I2) = { "$" }so Select(P5) and Select(P6) overlap, which means the grammar is not deterministic and the type definition is not valid 💀 like, if the first child element is an unrecognized element, a decoder literally can't tell whether it belongs to I1, or to I2 by pretending the "one" component has an unknown extension that generates no elements. not it 🙈
good news though! the non-determinism can be fixed with either a SINGULAR-INSERTIONS or a UNIFORM-INSERTIONS encoding instruction ✨ let's start with SINGULAR-INSERTIONS:
SEQUENCE {
one [GROUP] [SINGULAR-INSERTIONS] CHOICE {
two UTF8String,
... -- Extension insertion point (I1).
},
three [GROUP] CHOICE {
four UTF8String,
... -- Extension insertion point (I2).
}
}the grammar for this one is 💅
P1: S ::= one three
P2: one ::= two
P12: one ::= "*"
P4: two ::= "two"
P7: three ::= four
P8: three ::= I2
P9: four ::= "four"
P10: I2 ::= "*" I2
P11: I2 ::=with SINGULAR-INSERTIONS added, the P5 and P6 productions just don't get generated anymore 🫶 the grammar gives these sets and predicates for P2 and P12:
First(P2) = { "two" }
First(P12) = { "*" }
Preselected(P2) = Preselected(P12) = false
Empty(P2) = Empty(P12) = false
Follow(one) = { "four", "*", "$" }
Select(P2) = First(P2) = { "two" }
Select(P12) = First(P12) = { "*" }the P5 and P6 sets are gone, and everything else stays the same 🌸
now the Select(P2) and Select(P12) intersection is empty, same goes for Select(P7) and Select(P8) and for Select(P10) and Select(P11). so the grammar is deterministic and the type definition is valid 👑 the new vibe: if the first child element is an unrecognized element, a decoder will now assume it goes to extension insertion point I1. whatever comes after, even another unrecognized element, belongs to the "three" component 🦋
now let's look at the same type definition, but with UNIFORM-INSERTIONS instead 🍓
SEQUENCE {
one [GROUP] [UNIFORM-INSERTIONS] CHOICE {
two UTF8String,
... -- Extension insertion point (I1).
},
three [GROUP] CHOICE {
four UTF8String,
... -- Extension insertion point (I2).
}
}its grammar is 🌈
P1: S ::= one three
P2: one ::= two
P13: one ::= "*"
P14: one ::= "*1" I1
P4: two ::= "two"
P15: I1 ::= "*1" I1
P6: I1 ::=
P7: three ::= four
P8: three ::= I2
P9: four ::= "four"
P10: I2 ::= "*" I2
P11: I2 ::=and the sets and predicates for P2, P13, P14, P15, and P6 are:
First(P2) = { "two" }
First(P13) = { "*" }
First(P14) = { "*1" }
Preselected(P2) = Preselected(P13) = Preselected(P14) = false
Empty(P2) = Empty(P13) = Empty(P14) = false
Follow(one) = { "four", "*", "$" }
Select(P2) = First(P2) = { "two" }
Select(P13) = First(P13) = { "*" }
Select(P14) = First(P14) = { "*1" }
First(P15) = { "*1" }
First(P6) = { }
Preselected(P15) = Preselected(P6) = Empty(P15) = false
Empty(P6) = true
Follow(I1) = { "four", "*", "$" }
Select(P15) = First(P15) = { "*1" }
Select(P6) = First(P6) + Follow(I1) = { "four", "*", "$" }the remaining sets are unchanged 🫧
the Select(P2) and Select(P13) intersection is empty, same for Select(P2) and Select(P14), for Select(P13) and Select(P14), and for Select(P15) and Select(P6). so the grammar is deterministic and the type definition is valid 🎉 with UNIFORM-INSERTIONS, if the first child element is an unrecognized element, a decoder will now assume that it, and every later unrecognized element with the same name, goes to I1. whatever follows, even an unrecognized element with a different name, belongs to the "three" component ⭐
ngl this is the important bit: using UNIFORM-INSERTIONS means any future extension to the "three" component has to generate elements with names that are different from the ones the "one" component generates. with SINGULAR-INSERTIONS, extensions to "three" are allowed to use the same names as the elements from "one" 💜
B.4. Example 4 🧚
okay so this one is the bestie of the examples 🫶 we're looking at a type with a [GROUP] and a CHOICE that has an extension insertion point (I1) in it. The type definition is:
SEQUENCE OF one [GROUP] CHOICE {
two UTF8String,
... -- Extension insertion point (I1).
}The grammar that goes with it is:
P1: S ::= one S
P2: S ::=
P3: one ::= two
P4: one ::= I1
P5: two ::= "two"
P6: I1 ::= "*" I1
P7: I1 ::=Now the fun part, the sets and predicates 🤓
First(P1) = { "two", "*" }
First(P2) = { }
Preselected(P1) = Preselected(P2) = false
Empty(P1) = Empty(P2) = true
Follow(S) = { "$" }
Select(P1) = First(P1) + Follow(S) = { "two", "*", "$" }
Select(P2) = First(P2) + Follow(S) = { "$" }
First(P3) = { "two" }
First(P4) = { "*" }
Preselected(P3) = Preselected(P4) = Empty(P3) = false
Empty(P4) = true
Follow(one) = { "two", "*", "$" }
Select(P3) = First(P3) = { "two" }
Select(P4) = First(P4) + Follow(one) = { "*", "two", "$" }
First(P6) = { "*" }
First(P7) = { }
Preselected(P6) = Preselected(P7) = Empty(P6) = false
Empty(P7) = true
Follow(I1) = { "two", "*", "$" }
Select(P6) = First(P6) = { "*" }
Select(P7) = First(P7) + Follow(I1) = { "two", "*", "$" }and here's the tea ☕ the intersection of Select(P1) and Select(P2) is not empty. Same drama with Select(P3) and Select(P4), and with Select(P6) and Select(P7). So the grammar is not deterministic and the type definition is not valid 💀 If a decoder runs into two or more unrecognized elements in a row, it can't tell whether that's one instance of the "one" component or more than one. And even with zero unrecognized elements, there's still a problem: an encoding could hold an indeterminate number of "one" components through an extension that makes no elements at all 🙈
the non-determinism can't be fixed with a UNIFORM-INSERTIONS encoding instruction. so here's a revised type definition that uses it:
SEQUENCE OF one [GROUP] [UNIFORM-INSERTIONS] CHOICE {
two UTF8String,
... -- Extension insertion point (I1).
}with this grammar:
P1: S ::= one S
P2: S ::=
P3: one ::= two
P8: one ::= "*"
P9: one ::= "*1" I1
P5: two ::= "two"
P10: I1 ::= "*1" I1
P7: I1 ::=and the sets and predicates:
First(P1) = { "two", "*", "*1" }
First(P2) = { }
Preselected(P1) = Preselected(P2) = Empty(P1) = false
Empty(P2) = true
Follow(S) = { "$" }
Select(P1) = First(P1) = { "two", "*", "*1" }
Select(P2) = First(P2) + Follow(S) = { "$" }
First(P3) = { "two" }
First(P8) = { "*" }
First(P9) = { "*1" }
Preselected(P3) = Preselected(P8) = Preselected(P9) = false
Empty(P3) = Empty(P8) = Empty(P9) = false
Follow(one) = { "two", "*", "*1", "$" }
Select(P3) = First(P3) = { "two" }
Select(P8) = First(P8) = { "*" }
Select(P9) = First(P9) = { "*1" }
First(P10) = { "*1" }
First(P7) = { }
Preselected(P10) = Preselected(P7) = Empty(P10) = false
Empty(P7) = true
Follow(I1) = { "two", "*", "*1", "$" }
Select(P10) = First(P10) = { "*1" }
Select(P7) = First(P7) + Follow(I1) = { "two", "*", "*1", "$" }okay so the Select(P1) vs Select(P2) clash is gone ✨ but Select(P10) and Select(P7) still overlap, so the grammar is still not deterministic and the type definition is still not valid 😭 the "indeterminate number from an extension that makes no elements" problem is solved, BUT if a decoder sees a run of elements with the same name, it still can't tell whether that's one instance of "one" or several.
the non-determinism can be fully fixed with a SINGULAR-INSERTIONS encoding instruction 💖 here's the revised type definition:
SEQUENCE OF one [GROUP] [SINGULAR-INSERTIONS] CHOICE {
two UTF8String,
... -- Extension insertion point (I1).
}with this grammar:
P1: S ::= one S
P2: S ::=
P3: one ::= two
P8: one ::= "*"
P5: two ::= "two"and the sets and predicates:
First(P1) = { "two", "*" }
First(P2) = { }
Preselected(P1) = Preselected(P2) = Empty(P1) = false
Empty(P2) = true
Follow(S) = { "$" }
Select(P1) = First(P1) = { "two", "*" }
Select(P2) = First(P2) + Follow(S) = { "$" }
First(P3) = { "two" }
First(P8) = { "*" }
Preselected(P3) = Preselected(P8) = false
Empty(P3) = Empty(P8) = false
Follow(one) = { "two", "*", "$" }
Select(P3) = First(P3) = { "two" }
Select(P8) = First(P8) = { "*" }and this one is the main character 👑 the intersection of Select(P1) and Select(P2) is empty, and so is the intersection of Select(P3) and Select(P8). so the grammar is deterministic and the type definition is valid 🎀 a decoder now knows that every extension to the "one" component generates a single element, so it decodes the right number of "one" components every time. iconic, honestly 🦋
Appendix C. Extension and Versioning Examples ✨
This appendix is non-normative.
C.1. Valid Extensions for Insertion Encoding Instructions
the first example shows extensions that satisfy the HOLLOW-INSERTIONS encoding instruction 🌸
[HOLLOW-INSERTIONS] CHOICE {
one BOOLEAN,
...,
two [ATTRIBUTE] INTEGER,
three [GROUP] SEQUENCE {
four [ATTRIBUTE] UTF8String,
five [ATTRIBUTE] INTEGER OPTIONAL,
...
},
six [GROUP] CHOICE {
seven [ATTRIBUTE] BOOLEAN,
eight [ATTRIBUTE] INTEGER
}
}the "two" and "six" components only generate attributes 🍓
the "three" component, in its current form, doesn't generate any elements. so any extension to "three" needs to do the same thing or it'll break forward compatibility 💀
the second example shows extensions that satisfy the SINGULAR-INSERTIONS encoding instruction 🧚
[SINGULAR-INSERTIONS] CHOICE {
one BOOLEAN,
...,
two INTEGER,
three [GROUP] SEQUENCE {
four [ATTRIBUTE] UTF8String,
five INTEGER
},
six [GROUP] CHOICE {
seven BOOLEAN,
eight INTEGER
}
}the "two" component will always generate a single <two> element ✨
the "three" component will always generate a single <five> element. it'll also generate a "four" attribute, but SINGULAR-INSERTIONS allows any number of attributes, so we're good 💅
the "six" component will generate either a single <seven> element or a single <eight> element. either way, there's a single element in any given encoding of the extension, which is exactly what the requirement asks for 🫶
the third example shows extensions that satisfy the UNIFORM-INSERTIONS encoding instruction 💜
[UNIFORM-INSERTIONS] CHOICE {
one BOOLEAN,
...,
two INTEGER,
three [GROUP] SEQUENCE SIZE(1..MAX) OF four INTEGER,
five [GROUP] SEQUENCE {
six [ATTRIBUTE] UTF8String OPTIONAL,
seven INTEGER
},
eight [GROUP] CHOICE {
nine BOOLEAN,
ten [GROUP] SEQUENCE SIZE(1..MAX) OF eleven INTEGER
}
}the "two" component will always generate a single <two> element 🌈
the "three" component will always generate one or more <four> elements 🎀
the "five" component will always generate a single <seven> element. it may also generate a "six" attribute, and UNIFORM-INSERTIONS allows any number of attributes, so that's fine too 💖
the "eight" component will generate either a single <nine> element or one or more <eleven> elements. either case satisfies the requirement that there must be one or more elements with the same name in any given encoding of the extension ✨
C.2. Versioning Example
okay versioning time 🦋 making extensions that aren't forward compatible is permitted, as long as the incompatibility is signalled with a version indicator attribute 🚩
suppose version 1.0 of a specification has this type definition:
MyMessageType ::= SEQUENCE {
version [ATTRIBUTE] [VERSION-INDICATOR]
UTF8String ("1.0", ...) DEFAULT "1.0",
one [GROUP] [SINGULAR-INSERTIONS] CHOICE {
two BOOLEAN,
...
},
...
}now an attribute needs to be added to the CHOICE for version 1.1 🎀 this change is not forward compatible, since it doesn't satisfy the SINGULAR-INSERTIONS encoding instruction. so the version indicator attribute has to be updated at the same time (or added, if it wasn't already there) 🔥 the new type definition for version 1.1 is:
MyMessageType ::= SEQUENCE {
version [ATTRIBUTE] [VERSION-INDICATOR]
UTF8String ("1.0", ..., "1.1") DEFAULT "1.0",
one [GROUP] [SINGULAR-INSERTIONS] CHOICE {
two BOOLEAN,
...,
three [ATTRIBUTE] INTEGER -- Added in Version 1.1
},
...
}if a version 1.1 conformant application hasn't used the version 1.1 extension in a value of MyMessageType, then it's allowed to set the version attribute to "1.0" 🌸
next up, a pair of elements gets added to the CHOICE for version 1.2 🧁 again, the change doesn't satisfy SINGULAR-INSERTIONS. the type definition for version 1.2 is:
MyMessageType ::= SEQUENCE {
version [ATTRIBUTE] [VERSION-INDICATOR]
UTF8String ("1.0", ..., "1.1" | "1.2")
DEFAULT "1.0",
one [GROUP] [SINGULAR-INSERTIONS] CHOICE {
two BOOLEAN,
...,
three [ATTRIBUTE] INTEGER, -- Added in Version 1.1
four [GROUP] SEQUENCE {
five UTF8String,
six GeneralizedTime
} -- Added in version 1.2
},
...
}if a version 1.2 conformant application hasn't used the version 1.2 extension in a value of MyMessageType, it's allowed to set the version attribute to "1.1". and if it hasn't used either extension, it's allowed to set the version attribute to "1.0" 💜
Author's Address 📮
Dr. Steven Legg
eB2Bcom
Suite 3, Woodhouse Corporate Centre
935 Station Street
Box Hill North, Victoria 3129
AUSTRALIA
Phone: +61 3 9896 7830
Fax: +61 3 9896 7801
EMail: steven.legg@eb2bcom.comFull Copyright Statement ⚖️
Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights.
This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property ✨
okay so bestie, the IETF is basically saying "we're not picking a side on this one" 💅 🎀 They don't take a position on whether any Intellectual Property Rights (the legal stuff that might be claimed over a technology) are valid or how far they reach. They also don't promise that a license for those rights is available, or that it isn't. And they're not claiming they went out and checked for any such rights themselves 🙈
Info about how RFC documents deal with those rights lives in BCP 78 and BCP 79 📖 🦋
Want copies of IPR disclosures sent to the IETF Secretariat? Or assurances that licenses will be available? Or the results of someone trying to get a general license or permission for implementers or users of this spec to use those proprietary rights? You can find all of that in the IETF on-line IPR repository at http://www.ietf.org/ipr 🌸
And if you know about any copyrights, patents, patent applications, or other proprietary rights that might cover technology you'd need to implement this standard, the IETF totally wants to hear about it 💜 Send it to ietf-ipr@ietf.org and they'll take it from there ✨
Acknowledgement 🫶
Last but not least, the RFC Editor function is currently funded by the Internet Society 🌈 Thank you, Internet Society, you're iconic 👑
📦 where this page comes from
- ietf: rfc4911 2007-07
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms