[Design] Record data types

[ruvi-d]

Design proposal for Record data types

Overview

Similar to how we have modeled the Map data type, we can model the record type object in the Rust runtime and use an opaque pointer on the LLVM codegen side to hold it as its value. The implementation of runtime operations (like load and store) will pass the record object's opaque pointer back to the run time library to invoke the correct functionality.

Note:

• As with the map implementation, since we don't have a memory management implementation, currently the record object memory will leak memory.
• Support for Anonymous Records have not been considered

Data model - C++/BIR representation

Type class needs to hold or point to the record type information e.g. "record_fields" and the record init function. Instead of Extending the current Type class to support this, I propose to create a standalone class called TypeRecord. The Type class will have a new generic member called typeStructure of type std::variant. This will hold any type specific values. For Record types the typeStructure will be a reference to a TypeRecord object. The actual TypeRecord object ownership will be with a std::map container in the Package class, similar to how we currently store global variables. This design will allow us to easily extend Type class to support other complex types in the future without having to resort to extending the Type class and having to use pointers and static_cast in the Variable class to hold Type member information.

The TypeRecord class will include members to hold all the relevant parameters like name, rest_field, record_fields and init_function as well.

Codegen logic

Init logic

• A runtime lib API will be called to create a record type opaque pointer
  • This requires us to pass record type information as parameters (including a variable length list of record_field) to the Rust API
  • For this I propose we generate a C style POD struct with pointers and lengths to encapsulate this information
  • Similar to the c_str() method of std::string; TypeRecord will expose a c_struct() method to expose the C style structure required for the Rust API
  • The Rust API implementation will deference pointers in the structure to get the record_field and generate the Record type in the runtime
• After a record type opaque pointer is returned from the runtime, we will inject it's init function logic (LLVM IR codegen)

Runtime operations

• Similar to the map type implementations, we will call the appropriate runtime APIs with the Record object's runtime opaque pointer
• For load and store operations, we will have different APIs for each primitive type (pass by value types) and one common method for all types handled via opaque pointers.

Data model - Runtime (Rust)

• The Record type structure in the Rust implementation will be called BalRecord
• The members of BalRecord will contain the properties from the TypeRecord class, with additional information to map Ballerina types to Rust types
• To store the actual Record field values, I propose to use a HashMap with the field names as the map key and have the values stored using a type safe union mechanism like Rust's enumerations (viability to be verified)

BIR parser updates

• Need to add support for record_type and record_bodies
• Update ShapeCpInfo::read() to handle record types
• Update BIRReader::readFunction() to support the parsing of Record's init function

[jclark]

A value that is a record is a map and vice-versa. Record types and map types are two ways of describing sets of mapping values.

For closed records and a r.x expression, you shouldn't need to use hashing: you can compute at compile-time where in the record the field value is stored.

I would recommend using tagged pointers for unions: you can represent that by a Rust union.

[manuranga]

Levels of optimizations we could start with:

1. unoptimized - every record is a hashmap
2. storage optimized - records are struct+optional hashmap (for closed records it can be just a struct). record access happens though vtable-for-fields.
3. storage and access optimized - above memory structure, but direct access to struct whenever possible, only resolve via the vtable when needed (such as when casted to a map)

In previous BVM we had approach 1, current jBallerina backend uses approach 2.

[ruvi-d]

For nBallerina shall we start off with an "#1 : Unoptimized" implementation?

[ruvi-d]

Few updates to the aforementioned design proposal.

• Start implementation with "1. unoptimized - every record is a hashmap" design
• Use a Rust hashmap to store the fields
• The value can be modeled as a Rust enum that holds the value of primitives or a reference of objects
• This approach will allow us to easily convert between maps and records; as the underlying hashmap can be accessed via either the a map or record interface
• The potential Rust implementation for a "2 storage optimized" design is unclear. I am yet to figure out an efficient solution to model a r.x type member access in Rust.

[jclark]

We should be designing this in terms of the memory layout of the representation, not in terms of Rust. The problem is not "to figure out an efficient solution to model a r.x type member access in Rust". Rust has low-level support (e.g. raw pointers) to do whatever is needed. The goal is not (at this low level) to have a solution that is elegant or convenient in Rust: it only needs to be possible to build a convenient/elegant Rust interface on top of the low-level layer.

Before you get into designing specific basic types, there fundamental problem is how to represent values tagged with basic types. Here's an paper on that, which is old, but useful: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.4394&rep=rep1&type=pdf

We also need to have some idea of how we are going to approach GC.

[ruvi-d]

Noted! thanks for the reference.

[jclark]

You might find this interesting:

https://github.com/rust-lang/hashbrown/blob/master/src/raw/mod.rs

It's the low-level hash-table implementation that underlies (with several layers of abstraction) Rust's HashMap. It uses the algorithm described in this talk:

https://www.youtube.com/watch?v=ncHmEUmJZf4

It's interesting both because of the algorithm and because it illustrates how Rust can be used for really low-level manipulation of raw memory.