# Unsized Types in MiniRust

## Types
### Size

To support unsized types, we make `Type`'s `.size()` to return an `Option<Size>`, and this can affect the value's encoding/decoding.

For most sized types or compound types where only sized types are allowed in their fields (such as unions, tuples, enums, etc.), it is trivial to replace `.size()` with `.size().unwrap()`.

### Layout
References and boxes (or even the raw pointers) should be carefully taken care of, because their pointee types may be unsized. We changed the `size` in `Layout` to be optional because the only difference between a sized type and an unsized type, is that the sized type has a known `size` but the unsized type doesn't. They both have an `align` and an `inhabited` property.

## Values
### Metadata
When encoding/decoding the unsized types, we need extra information to determine how many bytes should we decode or how many values should we encode. In the surficial Rust language, fat pointers carry metadata containing this information. But in MiniRust, there is no metadata involved yet in the `encode`/`decode` method, so here it might need further design,

For slice types, it is possible to calculate their lengths from the list of abstract bytes or the list of values, since the length of bytes must be a multiple of the element type's size, and the number of encoded values must equal the length of the slice. But for trait objects, it is not possible to do that.

### PointerRepr (The May-be-Fat Pointer)
Fortunately, because `encode` and `decode` are only used in the typed load or store, it is possible to pass in the metadata from the pointer to read or write. We simply add a `PointerRepr` type including a pointer address and the optional metadata, where the metadata needs further design if we would like to support more unsized types such as trait objects.

For pointer families, there is a minor change in `encode`/`decode`: we need to encode or decode the metadata if it is a fat pointer.

By the way, `PointerRepr` may not be a good name.

### The "More Defined" Partial Order
For thin pointers, it remains the same case as the previous `Pointer`.

For fat pointers, there is no partial order of the "more defined" relationship because there are no choices of changing the value of metadata when doing an encode and then decode. Thus, we define its partial order as, a may-be-fat pointer is more defined than another if and only if its address is more defined than the other, and they have the same metadata.

## Places
We simply change the type alias of `Place` from the thin `Pointer` to the may-be-fat `PointerRepr`, to enable places of unsized types.

## New Operators for Slice Types
Finally, we add two operators which are commonly used for the slice types.

### `Len`
Similar to MIRI, `len` supports both array types and slice types:
- for the array type, the length comes directly from its type's definition;
- for the slice type, the length comes from the metadata of the place value.

### `PtrUnsize`
This converts a sized pointer to an unsized pointer.

## Unresolved Questions

- [ ] Should we make the size in `Layout` an `Option<Size>` or use other ways to represent fat-pointer types?
- [ ] What type should the metadata in fat pointers be?
- [ ] How should we support other unsized types such as trait objects? (We may need to define function pointers though)
- [ ] What name should we pick up for the may-be-fat pointer? (Currently `PointerRepr`)
- [ ] What type should the `Place` be?
- [ ] Are we going to add more operators for unsized types?