Support slice type and pointer-unsize cast

[frank-king]

This PR implements part of #1.

It adds optional metadata in the pointer value and the place representation.

Slices' subslice is not supported yet. In MIRI, it seems to be a function call of Index::<impl RangeBounds<usize>>::index. I'm not sure how should mini-rust deal with it.

TODO: need to check the files manually one by one.

• [ ] prelude.md
• [ ] types.md
• [ ] values.md
• [ ] well-formed.md
• [ ] syntax.md
• [ ] machine.md
• [ ] step.md
• [ ] operator.md

[RalfJung]

Thanks for the PR! Unsized types will need some careful design I think, so it probably makes sense to discuss this a bit before committing to and implementing one design.

[frank-king]

Yes, Indeed. I can write down my idea here later and discuss it with you in the next week. Have fun on your vacation! :smile:

[frank-king]

Types

Size

To support unsized types, I 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. I changed the size in Layout to be optional because the only difference between a sized type and an unsized type I think, is that the sized type has a known size but the unsized type doesn't. They both have an align and an inhabited property (I'm not sure of it).

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 I think 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. I simply added 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.

BTW, 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, I don't think there is a 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, I defined 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

I cannot tell the subtle differences between Place and Pointer (I just think Place of a semantical correspondence of Pointer), so I simply changed 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, I added 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. I put it in the UnaryOp but I'm not sure if it is the right place.

---

Questions that I'm not sure about:

• [ ] 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?

[RalfJung]

@frank-king are you on Zulip? For design decisions I think a good strategy is to have a design document on https://hackmd.io/ and then discuss on Zulip.

[frank-king]

Yes, my ID on Zulip is "Frank King".

[RalfJung]

Great, I created a topic :)

[RalfJung]

Thanks for the proposal! However, I don't think a MiniRust PR (with concrete code suggestions) is a good place for such a design discussion, so I am going to close it. Please either open a new issue with the design draft, or put it into a hackmd so that we can discuss it on Zulip.