Tom Thuneby of UH Communications suggests the use of ANYs to add support for recursive ASN1 types in the cases not currently covered by the standard.

Here is his proposal:

Mutually recursive ASN.1 types could be modelled by replacing the occurrence(s) of the second type in the first with any, which would in practice always contain a value of the second type. The programmer needs to be aware of this, and use the appropriate operations on the any.

When a type refers to itself (inside e.g. CHIOCE), the rules for inline expansion are not applicable. The solution for mutually recursive types above may also be applied here.

Voting: 5 votes for, none against

• (Page 40, section 2.8, remove completely, to be added after section 2.9)
• (Pages 41-52, section 2.9, renumber all section to 2.8)
• (Page 42, section 2.9.1, change first bullet within numbered list item 4)

- If recursion is found, apply rules decribed in Section 2.9 on page ??.

• (Page 42, section 2.9.1, replace last paragraph)

Note that if recursion is detected, the rules described in section 2.9 Mapping of Recursive Types apply.

• (Page 46, section 2.9.3.1, remove all references to "recursion", move second example (Filter) to section on recursive types)
• (Page 53, section 2.10, insert this whole section before 2.10)

2.9 Mapping of Recursive Types

We call recursive types those constructed types that contain an element/item of its own type. Direct recursion is when the element/item is explicitly of the container type or the element/item is a SET OF/SEQUENCE OF the container type, while indirect recursion is when the element/item is of another type, which contains a direct or indirect reference to the initial type. We call nested recusive types those types where indirect recursion happens within an element/item of a composite type (see section 2.8.1 for further definitions).

Unlike ASN.1, IDL does not support recursive type definitions, except direct recursions when they are used in sequences. Indirect mutual recursion is explicitly prohibited in IDL. The only solution to indirect mutual recursion, then, is to loose type safety by introducing an IDL any, and semantically restricting its contents to those of the recursive type (applications are responsible to enforce the semantics).

2.9.1 Resolution of direct recursion

ASN.1 direct recursive type definitions are mapped by converting the recursive type reference to an IDL sequence. If such reference occurs directly in a SET OF or SEQUENCE OF, then the sequence is unbounded (or bounded according to size constraints), otherwise, it is bounded to size 1. ASN.1 direct recursive type definitions are expanded in place. Note that if the element has the OPTIONAL or DEFAULT property, then the mapping is also done in place, as specified in the following clauses.

For the ASN.1 clause:

<type> ::= SEQUENCE { <identifier> <type> OPTIONAL }

the resultant IDL would be:

struct <mapped type name> {

    union <mapped identifier name>Opt switch (boolean) {

        case TRUE: sequence<<mapped type name>, 1> value;

    } <mapped identifier name>;

};

And for the ASN.1 clause:

<type> ::= SEQUENCE { <identifier> [SET|SEQUENCE] OF <type> OPTIONAL }

the resultant IDL would be:

struct <mapped type name> {

    union <mapped identifier name>Opt switch (boolean) {

        case TRUE: sequence<<mapped type name>> value;

    } <mapped identifier name>;

};

Note: if in this case, the SET/SEQUENCE OF has a size contraint, this constraint should be applied inside the generated IDL sequence, making it bounded, as described in the section on Constrained Types.

These same rules apply when a named type has the DEFAULT property, changing the "Opt" suffix of the IDL union to "Def".

2.9.1.1 Examples:

Filter ::= CHOICE {

    item [8] FilterItem,

    and [9] IMPLICIT SET OF Filter,

    or [10] IMPLICIT SET OF Filter,

    not [11] Filter

}

enum FilterTypeChoice {

    itemChoice, andChoice, orChoice, notChoice

};

union FilterType switch (FilterTypeChoice) {

    case itemChoice: FilterItemType item;

    case andChoice: sequence<FilterType> and;

    case orChoice: sequence<FilterType> or;

    case notChoice: sequence<FilterType, 1> not;

}

NameTree ::= SEQUENCE {

    generation INTEGER,

    parents SET SIZE(0..2) OF NameTree,

    children SET OF NameTree

} 

struct NameTreeType {

    ASN1_Integer generation;

    sequence <NameTreeType, 2> parents;

    // SIZE constraint: [0..2]

    sequence <NameTreeType> children;

}

NumberTree ::= SEQUENCE {

    level INTEGER,

    root NumberTree OPTIONAL,

    children SET OF NumberTree OPTIONAL

}

struct NumberTreeType {

    ASN1_Integer level;

    union rootDef switch (boolean) {

        case TRUE: sequence <NumberTreeType, 1> value;

    } root;

    union childrenOpt switch (boolean) {

        case TRUE: sequence <NumberTreeType> value;

    } children;

} 

2.9.2 Resolution of indirect recursion

When mapping the ASN.1 type assignment corresponding to an indirectly recursive type, all ASN.1 recursive references to this type should be considereded from this moment as references to the ASN.1 ANY type. Because of this substitution, recursion is broken, and therefore the general mapping rules are applied.

Note that types must be considered in their ASN.1 input order, and that only recursive references to the type being considered are substituted by this rule.

The references substituted by this rule should be mapped to the IDL type named "ASN1_Recursive", defined in the ASN1Types.idl file as:

typedef any ASN1_Recursive;

A comment is added to identify the IDL type corresponding to the substituted reference. Only values of this IDL type are allowed in the ASN1_Recursive. If a value of a different type is inserted, unexpected results can happen (behaviour is undefined).

2.9.2.1 Examples:

NameTree ::= SEQUENCE {

    rdnInfo RDNInfo,

    family SET OF SEQUENCE {

        coparent NameTree, 

        children SET OF NameTree 

    } 

}

typedef sequence<ASN1_Recursive> NameTreeFamilyItemChildrenType; 

        // must be NameTreeType 

struct NameTreeFamilyItemType {

    ASN1_Recursive coparent; // must be NameTreeType 

    NameTreeFamilyItemChildrenType children; 

};

typedef sequence<NameTreeFamilyItemType> NameTreeFamilyType;

struct NameTreeType { 

    RDNInfoType rdnInfo; 

    NameTreeFamilyType family; 

};

A ::= SET OF B 

B ::= SEQUENCE { a INTEGER, b A } 

struct BType {

    ASN1_Integer a; 

    ASN1_Recursive b; // must be AType 

};

typedef sequence<BType> AType;

B ::= SEQUENCE { a INTEGER, b A }

A ::= SET OF B

typedef sequence<ASN1_Recursive> AType; 

        // must be BType

struct BType { ASN1_Integer a; AType b; };

A ::= SEQUENCE { a INTEGER, b B }

B ::= SEQUENCE { x INTEGER, y C }

C ::= SET OF A

typedef sequence<ASN1_Recursive> CType; 

        // must be AType

struct BType { ASN1_Integer x; CType y; };

struct AType { ASN1_Integer a; BType b; };

-- NOTE: Unusable ASN.1 types

--       due to circular references.

A ::= SEQUENCE { b B, c C } 

B ::= SEQUENCE { a A, c C } 

C ::= SEQUENCE { a A, b B }

struct CType {

    ASN1_Recursive a; // must be AType

    ASN1_Recursive b; // must be BType

};

struct BType {

    ASN1_Recursive a; // must be AType

    CType c;

};

struct AType {

    CType c;

    BType b;

}