Proposal: Parse-time arbitrary value storage
I'm currently working on writing a parser for Microsoft's [NRBF](https://winprotocoldoc.blob.core.windows.net/productionwindowsarchives/MS-NRBF/%5bMS-NRBF%5d.pdf) serialization format, which is the format that the [`BinaryFormatter`](https://docs.microsoft.com/en-us/dotnet/api/system.runtime.serialization.formatters.binary.binaryformatter) class serializes into. It is ([ill-advisedly](https://docs.microsoft.com/en-us/dotnet/standard/serialization/binaryformatter-security-guide)) used as a form of data serialization for quite a few C# applications, including a whole bunch of Unity games. I'm working from the basis of https://github.com/hakanai/nrbf.ksy, which I imagine probably got abandoned when the author realized that Kaitai doesn't provide enough functionality to even do a basic parse of the format.

The problem is that NRBF aims to be an extremely compact binary format, like Protobuf, while still being self-describing. As such, there are several different ways to represent a given piece of data with more or less verbosity, depending on how much information the sender can assume the receiver has. At the high end of verbosity, an instance of a serializable class is represented by first describing the class schema, giving names and types for all arguments, and then following the schema with the serialized form of each of the instance's fields, in order.

Much like Protobuf or ASN.1/BER, NRBF has the concept of "tagged" or "explicit" values vs "untagged" or "implicit". In the serialization of a class instance's members, NRBF requires that primitive-typed fields be represented as implicitly-tagged values, without any identifying markers in the stream; in other words, a class with a 32-bit integer field, a boolean value field, and a 64-bit double-precision float would have its data encoded in the next 13 bytes after the class schema. On the other hand, if those values were non-primitive - say, perhaps, that they were boxed in an Optional<T> class - then they would be encoded as three explicitly-tagged MemberReference records following the class schema record. Or, worst (and most common) case, _some_ of the fields are primitive, in which case the untagged bytes in the stream are interleaved between the tagged records, in whatever order the class members were declared. In short, it's impossible to parse the bytes following a class record without referring to the class definition schema.

But NRBF wants to be compact. So, the second or any later time the encoder sees an instance of the same class in that stream, it doesn't reiterate the class definition. Instead, it references the first object in the stream with a record that simply means "this object is of the same class as object N". N, in this case, is the arbitrary 32-bit signed integer specified as the "object id" in that object's record. No, those IDs aren't consecutive or even monotonic. Yes, the encoder sometimes uses negative values for the ID.

So, it's impossible to parse an NRBF stream without the parser having some way to refer to a previous piece of information in the stream _by id_. (Also worth noting: the NRBF spec also allows for a well-known system class to be represented by class name alone. I haven't found any in the wild yet, but it's a very similar problem to this one, except strings are used instead of integer IDs, and Kaitai would need some way to instantiate the appropriate class definition structs at compilation time - some kind of struct-literal expression.) Right now, I'm working around this with a truly horrendous hack, forcing Kaitai to perform a recursive linear search over all the existing records whenever it encounters one of these:

```ksy
seq:
  - id: records
    type: record
    repeat: expr
    repeat-expr: 15

instances:
  record_list:
    pos: 0
    type: record_list(records)
  by_id:
    pos: 0
    repeat: expr
    repeat-expr: 'record_list.max_id > 0 ? record_list.max_id + 1 : 1'
    type: by_id_from(_index, 0, records)
  by_nid:
    pos: 0
    repeat: expr
    repeat-expr: 'record_list.min_id < 0 ? -record_list.min_id + 1 : 0'
    type: by_id_from(-_index, 0, records)

types:
  by_id_from:
    params:
      - id: object_id # the object being searched for
        type: s4
      - id: from_id # the current index being searched
        type: s4
      - id: records # the records to search
        type: record[]
    instances:
      class:
        value: |
          from_id >= records.size ? undef :
          ( this_record.is_class_def
            and this_record.object_id == object_id ) ? this_record :
          next.class.as<record>
      object:
        value: |
          from_id >= records.size ? undef :
          ( this_record.is_object
            and this_record.object_id == object_id ) ? this_record :
          next.object.as<record>
      this_record:
        value: records[from_id].as<record>
      next:
        pos: 0
        size: 0
        type: by_id_from(object_id, from_id + 1, records)
        if: from_id < records.size
      undef: # Kaitai doesn't seem to have a way to represent undef in expression language, so I have to force one to exist here
        value: 0.as<record>
        if: false

  # 2.3.2.5 ClassWithId
  class_with_id:
    seq:
      - id: object_id
        type: s4
      - id: metadata_id
        type: s4
      - id: member_values
        type: class_member_value(class_info.member_names[_index], member_type_info.additional_infos[_index])
        repeat: expr
        repeat-expr: class_info.member_count
    instances:
      metadata_class:
        value: metadata_id >= 0 ? _root.by_id[metadata_id].class.payload : _root.by_nid[-metadata_id].class.payload
      class_info:
        value: metadata_class.as<system_class_with_members_and_types>.class_info
      member_type_info:
        value: metadata_class.as<system_class_with_members_and_types>.member_type_info
```

Of course, in addition to being inefficient and memory-hungry, it's also quite fragile; Kaitai is not particularly fond of recursive definitions and tends to spit out difficult-to-trace errors consisting solely of the class name rather than anything useful.

So, how to fix this? Well, most if not all of Kaitai's target languages contain some kind of map or dictionary type, with (at the very least) the ability to map an integer or string value to an object instance; we just need a way to create, access, and add to one during parse time, and a way to represent it declaratively. I propose something along these lines:

```ksy
seq:
  - id: records
    type: record
    repeat: expr
    repeat-expr: 15
    add-to:
      - map: class_by_id
        key: _.object_id
        value: _.class_info
        if: _.is_class_def
      - map: object_by_id
        key: _.object_id
        # value: _ # this is the default
        if: _.is_object

instances:
  object_by_id:
    key-type: s4
    value-type: record
  class_by_id:
    key-type: s4
    value-type: class_info
  class_by_name:
    key-type: str
    value-type: class_info
    initial-values:
      - key: 'System.Drawing.Point'
        value: |
          # Since the value-type is class_info, we need some way to create a class_info instance. Perhaps something like:
          class_info{
            name: "System.Drawing.Point"
            member_count: 2
            member_names: ["X","Y"]
          }
      sealed: true # nothing will get added to this map at parse-time

types:
  record:
    seq:
      - id: record_type_enum
        type: u1
        enum: record_type_enumeration
      - id: payload
        type:
          switch-on: record_type_enum
          cases:
            'record_type_enumeration::serialized_stream_header': serialization_header_record
            'record_type_enumeration::binary_library': binary_library
            'record_type_enumeration::class_with_members_and_types': class_with_members_and_types
            'record_type_enumeration::system_class_with_members_and_types': system_class_with_members_and_types
            'record_type_enumeration::class_with_id': class_with_id
            'record_type_enumeration::member_primitive_typed': member_primitive_typed
            'record_type_enumeration::member_reference': member_reference
            'record_type_enumeration::binary_array': binary_array
    instances:
      is_class_def:
        value: |
          record_type_enum.to_i >= record_type_enumeration::system_class_with_members.to_i
            and record_type_enum.to_i <= record_type_enumeration::class_with_members_and_types.to_i
      is_object:
        value: |
          record_type_enum.to_i >= record_type_enumeration::class_with_id.to_i
            and record_type_enum.to_i <= record_type_enumeration::binary_array.to_i
          or
          record_type_enum.to_i >= record_type_enumeration::object_null_multiple256.to_i
            and record_type_enum.to_i <= record_type_enumeration::array_single_string.to_i
      object_id:
        type: s4
        pos: _pos + 1
        if: is_object
```

Here, the `key-type` and `value-type` keys in an instance (which must either both appear or neither) cause it to be a third type of instance; instead of a positional (with `pos` and `type`) or value (with `value`) instance, it's now a _map_ instance. Access is performed with square brackets, like an array; values are added to the map (with write-once and error-on-duplicate semantics, I'd imagine, to match the rest of the language) using the `add-to` property on any parsed element, after it parses successfully.