Why "Sorry, only pointer types can be used as generic parameters."?

[Samuel Ainsworth]

Following the schema introduction (https://capnproto.org/language.html), I have something like the following:

struct Map(Key, Value) {
  entries @0 :List(Entry);
  struct Entry {
    key @0 :Key;
    value @1 :Value;
  }
}


struct Directory {
 contents @0 :Map(UInt64, UInt64);
}

But capnproto isn't too happy about this:

src/newworld/filetree.capnp:51:23-29: error: Sorry, only pointer types can be used as generic parameters.

I understand what this is saying, but I'm a bit puzzled as to why this constraint exists... Why are only pointer types allowed as the instantiations of generic parameters?

Thanks,

Samuel

[Samuel Ainsworth]

I guess I'm especially puzzled since

struct File {
 test @0 :List(UInt64);
}

isn't a problem.

[Kenton Varda]

Hi Samuel,

Basically, because all pointers are the same size regardless of their type, so varying the type of a pointer does not change the overall layout of the containing struct.

If the field can actually change sizes for different generic types, then it could affect the size and position of other fields around it. For example, imagine this:

    struct Foo(T) {

      a @0 :Int16;

      b @1 :Int32;

      c @2 :T;

      d @3 :Int64;

    }

If we replace `T` with the type `Int16`, then the struct will be laid out like this:

    0...16 a

    16...32 c

    32...64 b

    64...128 d

But if we replace `T` with type `Int32`, then the struct looks like this:

    0...16 a

    16...32 (empty padding)

    32...64 b

    64...96 c

    96...128 (empty padding)

    128...192 d

Notice that the offset to field `d` differs between these. Also notice that deciding the offset of d depends on the specific details of all the fields that come before it.

Because of this complexity, if we wanted Cap'n Proto generics to support varying primitive types, we'd essentially be forced to output a whole copy of the class for each combination of type parameters, because potentially all the offsets could differ for each permutation.

*Or* we would need to say that generic types are laid out differently from the equivalent substituted type.

Either of these options seemed unreasonably bad in practice. So the only other option was to support varying pointer types only.

Note that this rule doesn't apply to List(T) because List(T) is a built-in type, not a generic.

-Kenton

--
You received this message because you are subscribed to the Google Groups "Cap'n Proto" group.
To unsubscribe from this group and stop receiving emails from it, send an email to capnproto+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/capnproto/9668d18e-63d3-4643-ac24-a32f11fc8bde%40googlegroups.com.

[Kenton Varda]

Note that this is roughly the same reason that Java has a similar restriction imposed on its generics.

-Kenton

[Samuel Ainsworth]

Thanks for the quick response! I see... I guess I was thinking that types would not have defined sizes until they became fully specialized to their arguments. This would make code generation less straightforward, but it's not unlike what goes on in many modern compilers these days. Easier said than done though.

Best,

Samuel

To unsubscribe from this group and stop receiving emails from it, send an email to capn...@googlegroups.com.

[Kenton Varda]

Yeah, I think if we really really wanted to do this, the approach I'd take is to have the capnp code generator output full specializations for each permutation of primitive type arguments. The really hard part is deciding which permutations to generate. You don't really know which specializations are needed until they are used, but if you generate them at the usage site, then you potentially end up with duplicates -- these are all the same problems that C++ templates have. I suppose we could do what C++ compilers do and, like, output weak symbols, but even if that works in C++, I suspect it won't work in many other languages.

And we'd have to come up with some other hack to support dynamically loading schemas from schema.capnp format -- that format has offsets precomputed, which again implies that specializations involving primitive types actually have to have their own separate compiled schema representations... ugh.

-Kenton

To unsubscribe from this group and stop receiving emails from it, send an email to capnproto+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/capnproto/d33a330b-0aac-48d9-8f41-82d25fe1c7ba%40googlegroups.com.

[Ian Denhardt]

Quoting 'Kenton Varda' via Cap'n Proto (2020-04-30 18:51:40)

> Yeah, I think if we really really wanted to do this, the approach I'd
> take is to have the capnp code generator output full specializations
> for each permutation of primitive type arguments. The really hard part
> is deciding which permutations to generate. You don't really know which
> specializations are needed until they are used, but if you generate
> them at the usage site, then you potentially end up with duplicates --
> these are all the same problems that C++ templates have. I suppose we
> could do what C++ compilers do and, like, output weak symbols, but even

> if that works in C++, I suspect it won't work in many other languages.

Yeah, this sounds like it would be incredibly difficult to implement in
almost anything else.

Even in languages like Rust which use the same underlying execution
model for generics, you can't do template specialization, and type
parameters still have to be treated uniformly at the source level. And
capnproto is complex enough for implementers to begin with.

-Ian