Dynamically sized types

[nikomatsakis]

As described here:

http://smallcultfollowing.com/babysteps/blog/2013/04/30/dynamically-sized-types/

Rough notes on the plan:

• Thinking about dynamically sized types. What needs to change:

  • trans code:
    • need to ensure that all dynamically sized types have a consistent
      layout (e.g., (ptr, meta))
      • change repr of ~[T], ~str, `~Trait', etc
      • change repr of ~Trait to be a pair, moving type descriptor into vtable
      • change repr of @fn, ~fn, &fn to skip header for &fn pointer
    • make the various Datum routines for deref'ing and so forth do
      the right thing based on the ty::t
      • not sure what other places in the code think they know about
        the structure of a pointer, probably a few
      • we could keep the types as they are now and get this part right,
        by essentially translating in trans from something like
        AutoBorrowVec into the combination of datum.deref() and then
        datum.take_ref()
    • at type system level, 9then, we'll want to:
      • implement kind bounds on fns (I can do that relatively easily)
      • any other changes that would stand in the way of types being
        separated from & etc
      • do the change

• Semantic questions:

  • [a, b, c] has type [T, ..3]
  • ~[a, b, c] has type ~[T]
  • [a, b, c] --> [T]
  • Relevant to custom smart pointer types:
  • If we for a DWIM solution:
    • ~([a, b, c]) <-- what should this do?
    • basically we'll propagate information from ~ operator, @ operator, etc

• Modify kindck (probably?) to enforce Sized requirement

  • good idea to do this early, gives us an idea of the burden aspect
  • maybe move existing code to kindck as a first step?

• We may want to allow kind bounds of type definitions:

  struct Foo {
  vec: ~[T] <--- we would want to know here that T:Sized
  }

  or maybe just enforce this bound at use points instead

To be implemented by @pcwalton and @nikomatsakis.

[graydon]

accepted for well-defined milestone

[nikomatsakis]

Here is a rough plan I worked out:

First snapshot will contain:

• Implement the Sized bound and require its use:
  • initially all types will be considered Sized except for type parameters w/o a Sized bound
  • type of all local variables must be sized
  • whenever you index into a vector, type of elements must be sized
  • whenever you dereference a pointer in a non-lvalue context, type of the pointee must be sized
    • moves is already computing a lot of this information, if we generalize it a bit it can tell us whether a given context is lvalue vs rvalue, which would be useful for other things as well
• Add proc type, proc literals
• Enforce fn:K bounds on the upvars
  • check that upvars have the proper bounds
  • consider bounds when computing TypeContents of a closure type
• Add Trait:K bounds on object types (I think they are not parsed today)

Second snapshot will contain

• Port uses of @fn and ~fn to use proc
• Remove @fn, ~fn
• Add new fn type (just closures) and interpret &fn as fn
• Enforce Trait:K bounds on trait types
  • as with the "closure" case above

Third sdnapshot

• Remove &fn as a special case
• Modify ty.rs to remove evec, estr, sigils from objects. Deal with fallout.

Obviously the last step is a little vague.

[graydon]

Sounds good. Exciting!

There was some talk at the end of last discussion on this about alternatives to adding a full proc type-family, either forcing use of traits for the use cases, or moving it into another possibly disjoint fn-qualifier-name (like extern, unsafe and once), just to avoid the superficial charge of "having multiple types of function". Did you have feelings about that?

[nikomatsakis]

@graydon it seems I never responded to you. I had a long response prepared but I guess I closed (or lost?) the tab. Short version: I am open to discussion, but I think that as far as my personal preference goes, I'd prefer to change extern fn to a different noun rather than an adjective+noun. Even I find the current fn types kind of confusing, and I think they will only be more confusing if we add in env fn or something like that. I would sort of prefer that you select the noun based on the memory ownership rules then you can use the "adjectives" to designate restrictions that the caller must observe (caller must be unsafe, caller can only call once) and the bounds (fn:K, proc:K) to restrict the values that can be closed over. At least that was the logic. But my main goal is to make the types comprehensible, so if others feel that it's more comprehensible and/or feels less complicated to always include fn, I'm persuadable.

[bblum]

We probably don't want to allow unsizedness ever to "infect" containing types the same way the rest of the builtin bounds can, do we? The hardest case is with type parameters. For example:

struct Foo<T> {
    data: T,
}
struct Bar<T> {
    data: ~T,
}

and in another file:

x: Foo<[int]>, // must be either illegal or dynamically-sized
y: Bar<[int]>, // ok, but should we support it?

edit: In fact, the first case should almost certainly be illegal, due to struct Baz { x: Foo<[Int]>, y: Bar<[Int]>, } -- if allowed, the offset of y would have to be computed at runtime.

edit 2: This hints at other places where you'd need to use the Sized bound even when Copy is not in play -- container data structures. Examples: moving something into an ARC, mapping an option to an option, inserting into a hashtable.

[glaebhoerl]

I think there's three options WRT the first case:

1. Don't allow it at all.
2. Allow it if the unsized type is the only member (newtype-like), resulting type is unsized. This might allow str as a library?
3. Allow it if the unsized type is the last member (superset of 2.), resulting type is unsized. This would be a safe encoding of C's flexible array member idiom.

[nikomatsakis]

I had not expected to allow either Foo<[int]> or Bar<[int]> right now, though I would eventually love it if we allowed unsized members as the final member of a struct. And yes I expect to use the sized bound on container data structures and higher-order functions that operate on them.

[bblum]

We'll also need Sized bounds on all functions that use polymorphic vectors.

Um... should construction of dynamically-sized vector element types be forbidden, or only construction of values inhabiting such type? What I mean is:

fn bar<T: Sized>() { }
fn foo<T>() {
     bar::<~[T]>()
}

(Likewise for enums, structs, tuples, etc.)