Using parametrized generic const for a value of a non-parametrized generic field of same type fails.

[ku...@bertec.com]

Is this a feature or a bug?

struct Outer {

    inner @0 :Inner;

}

struct Inner(T) {

    value @0 :T;

}

struct ValueA { a @0 :Int32; }

struct ValueB { b @0 :Int32; }

const outerWorks :Outer = (inner = .innerWorks);

const innerWorks :Inner = ();

const outer :Outer = (inner = .inner); # fails here

const inner :Inner(Value) = (value = ());

Fails with error: Type mismatch; expected Inner.

I'd like at minimum the above to work, but ideally I would really like is something like:

struct OuterList {

  inners @0 :List(Inner);

}

const outer :OuterList = [

  (inner = :Inner(ValueA) (a = 0)),

  (inner = :Inner(ValueB) (b = 42)),

];

Any thoughts? I could take a stab at implementing whatever you suggest. - Kuba

[Kenton Varda]

This is called "generics covariance".

It does seem like covariance could be supported here, however this can be trickier than it looks. It's OK here specifically because constants are transitively immutable, and can't possibly contain capabilities.

Covariance would be technically incorrect in the presence of capabilities, if the type parameter is used as the input type to a method. For example:

    interface Queue(T) {

      add @0 (value :T);

    }

    const textQueue :Queue(Text) = ...;

    const genericQueue :Queue = .textQueue;

    // ERROR: genericQueue could be used to send non-text values to textQueue,

    //   violating its type contract!

In fact, in this case, contravariance could be allowed:

    const genericQueue :Queue = ...;

    const textQueue :Queue(Text) = genericQueue;

    // OK: genericQueue accepts any input, including Text.

Anyway, I guess given that there's no such thing as a constant capability currently, we don't need to worry about that? And covariance is correct for all other types? So we could support it?

-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/ab0c1e68-f52e-46aa-b4e5-c51a113358c1%40googlegroups.com.

[Ian Denhardt]

Quoting 'Kenton Varda' via Cap'n Proto (2019-09-16 16:14:59)

> Anyway, I guess given that there's no such thing as a constant
> capability currently, we don't need to worry about that? And covariance
> is correct for all other types? So we could support it?

It's sound for constants, but given that it's not for mutable values
(even without caps), my gut is that adding this is probably not a good
cost:benefit ratio. It would only enable creating constants that would
be impossible to construct dynamically anyway, and it's not clear to me
what sort of programming this enables that justifies that.

-Ian

[Kenton Varda]

Hmm, I think it might be sound for mutable values as long as you don't have aliasing.

Practically speaking, you can actually construct such values at runtime, at least in the C++ implementation.

-Kenton

[Ian Denhardt]

Quoting Kenton Varda (2019-09-16 18:42:36)

> Hmm, I think it might be sound for mutable values as long as you
> don't have aliasing.

I think you might be right, but importantly the lack of aliasing has to
hold all the way up the pointer chain, to your program's "root set" to
use GC terminology; it's not sufficient for the message itself not to
have aliasing, since otherwise you might have the usual problem with two
pointers to the message's root struct.

Rust will enforce that, and from what I've seen the style encouraged by
most of your own work follows this by convention (C++ isn't memory safe,
so obviously there's a certain amount of discipline that has to be
assumed for conversations about soundness to even be coherent). But it
doesn't seem like a safe assumption for languages that use a GC, rather
than relying on RAII and the like.

-Ian

[Ian Denhardt]

(Adding the list back to CC; I assume you didn't mean to just send this
to me).

> When passing GenericType to something that expects GenericType(Text),
> it’s up to the user not to mess it up

Catching this kind of mistake is the whole point of a type system. If
you're going to make the argument that the type system shouldn't worry
too much about edge cases and just act as a linter, then maybe you can
claim that this isn't a big deal, but I think the premise that Kenton
and I have been assuming is that type soundness (the property that
well-typed programs do not have run-time type errors) is desirable here.
Obviously this isn't really achievable for the C++ implementation
overall since C++ itself fails this property, but it's probably worth
hanging on to both for other languages and because getting closer to the
goal in C++ is probably still a useful thing.

---

To get into the details of what the problem is: perhaps this is review
for everyone, but: the classic example of the problem with covariant
generics and mutability is demonstrated by this java program:

public class Main {
public static void main(String[] args) {
Integer[] ints = new Integer[4];

// assign by reference, so `objs` points to the same array
// as `ints`. Covariance (the notion that if A is a subtype
// of B, then A[] is a subtype of B[]) is rule by which java
// admits this statement:
Object[] objs = ints;

// And then because String is a subtype of Object, we can
// put a string in our list of integers through `objs`:
objs[0] = "OOPS";
}
}

As Kenton suggests, the example critically depends on pointer aliasing
for its unsoundness, so given that such aliasing is banned by the spec,
it may not be possible to construct such an example in a given message.
However, per my prior email it's not clear that you can't still run into
trouble by aliased references to the root struct of a message from the
rest of the program.

-Ian

Quoting Kuba Ober (2019-09-17 17:44:37)
> Either I’m not getting something or this is certainly meant to work with mutable types?
>
> Any field accepting a GenericType should accept an arbitrary specialization, at least in the implementations I know of. Of course the application itself may further constrain what types are allowed, but we’re talking about static type checking within CapnProto runtime implementation(s).
>
> I consider implementations that would not allow it to be buggy – otherwise the entire premise of generic types in CapnProto is IMHO broken. As far as I can divine intent from CapnProto documentation, the generics were designed so that an unparametrized type is a stand-in for all of its specializations, both in co- and contravariant directions. When passing GenericType to something that expects GenericType(Text), it’s up to the user not to mess it up – there are several such areas in CapnProto where the sender of a message and the receiver must agree on what type is actually sent.
>
> It’s up to the implementer to make it possibly type-safe, e.g. an implementation could store the parameter type id and do a single check when GenericType.Reader is coerced to GenericType<Text>.Reader, and so on.
>
> Slightly confused, Kuba
>
> > 16 sep. 2019 kl. 6:31 em skrev Ian Denhardt <i...@zenhack.net>:
> >
> > Quoting 'Kenton Varda' via Cap'n Proto (2019-09-16 16:14:59)

[ku...@bertec.com]

But I'm talking about Capnproto schema language, not any particular implementation. If catching mistakes were a viable goal, then there would be no `AnyPointer`, since that is (and I quote documentation) "void* like in C". Can't get any more explicit than that: `void*` catches no mistakes, it's the idiom for type erasure, it lets you write type-unsound programs. Same goes for generic interfaces and generic methods - no typechecking there in the sense that either end of the RPC connection can use wrong types and everything can then blow up, with no runtime diagnostics other than when the pointer kinds mismatch.

As things are, it's impossible to divine when `AnyPointer` is usable and when it isn't. The usual way the implementations deal with going from `AnyPointer` to some specific type is by doing an explicit cast, just as you would in C, letting the user assert that they know what they are doing. I really fail to see what the Java snippet provided below has to do with this Capnproto issue. In Java, `Object` is like `void*`, it's a type-erasure type, and so are `object` and `dynamic` in C#. If you want to do silly things, the runtime will stop you, and that's that, no problem - you chose to use type erasure, you reap what you sow. In C, C++ and Capnproto, the runtime won't generally stop you, and that's fine with me, too. You can initialize whatever pointer type you want in an `AnyPointer` field, and the user of the structure must somehow divine what really went there.

So for there to be some coherency, either `AnyPointer` has to be removed, or it has to be embraced to mean what it means in C/C++: type erasure and delegation of type checking to the user, not the compiler. It's a broken typecheck escape as it stands right now. If typechecks were not to be bypassed, then not only would `AnyPointer` have to go, but interface specializations would need to do typechecking on the wire, so that at least at runtime the mistakes would be caught.

If `AnyPointer` is not a stand-in for `void*`, then a) this mention has to go from the documentation, since neither design intent nor reference implementation behavior are really like `void*`, and b) some guidance has to be provided as to what purpose does `AnyPointer` serve, since clearly generally taken type erasure isn't its goal. Except the few times it is, of course. Sigh.

Looking past AnyPointer: You can specialize Capnproto generic interfaces to any pointer type you want on either side of the wire, and so you can specialize generic methods too, and it's entirely to the user and the interface implementor to somehow agree on what types are really passed around. There are no typesystem checks for this, and the parameter and result wire formats can differ, etc. RPC typechecking is quite arbitrary in general: the unspecialized interface type is typechecked on every method call, as a consequence of an implementation detail (a sensible implementation detail, I should add), yet the lower hanging fruit of typechecking a generic interface's type parameters at capability acquisition time is not done, even though its wire overhead would be dwarfed by the cost of method invocations (including their inherent typechecking).

Looking even further, this arbitrariness carries to constants, where you can't do what is perfectly fine at runtime - and if one wasn't confused already, this is a real stunner. At runtime you can e.g. initialize an `AnyPointer` field as `Text`, but constants don't let you do that. I have no idea in fact what was the intended behavior of an `AnyPointer` field in a constant. This puzzles me to no end given that type soundness checking lends itself well to compile-time typechecking of constants. If `AnyPointer` is verboten where typechecking would be impossible, then surely it should be allowed in constant context where typechecking can be done. Imagine that in const context you replace every `AnyPointer` field with a generic type parameter, and then substitute the actual types used, and present the constant of such a type to the user: it's wire-compatible with `AnyPointer`, and it's a minor matter to allow conversion from such a specialized generic type to a non-generic type with `AnyPointer` substituted for each generic parameter. Hey, the generic unspecialized type already acts as if it had `AnyPointer` type parameters, so this is like 99% done, the only missing step is conversion between `struct Generic(T) { field @0 :T; }` and `struct NonGeneric { field @0 :AnyPointer; }` Maybe `AnyPointer` should not be available, and instead one should be forced to use type parameters wherever one would use `AnyPointer`? Would that be more kosher? Or perhaps structs with `AnyPointer` fields should be transcribed to generic types (effectively being some weird syntactic sugar), with `AnyPointer` really meaning "an unnamed generic type parameter"?

The more I look into this, the more arbitrary it all seems to be, and I can't visualize overarching design goals that might have driven this. Now I do appreciate that implementation realities often curtail fully developed designs, so I'm not trying to imply that the present way Capnproto works is somehow inherently "bad" - it is what it is, and the only way to look is forward, AFAICT.

Cheers, Kuba

[Ian Denhardt]

A thing I'd missed before, since we're just talking about constants, my
concern about multiple pointers (of different types) in the program
can't actually happen as long as we don't alias within the message --
since these aren't messages being constructed at runtime. So I think
Kenton is actually right that allowing covariant generics for constants
in the schema file is fine as long as we don't alias within a message.

Regarding what the rules should be around `AnyPointer`: I think it's
reasonable to allow otherwise-possibly-unsound assignments of
`AnyPointer`s with explicit casts, but I don't think such things
should just silently succeed.

In principle, this would be fine:

```
const foo: AnyPointer = "hello";
```

Since `Text` is always valid to use as a misc. pointer.

But this should fail:

```
const bar: AnyPointer = ...;
const baz: Text = bar; # Failure should happen here.
```

Because the inverse isn't true -- we don't know statically that `bar` is
actually usable as a `Text`.

Right now the first case is actually rejected -- maybe it shouldn't be.

The Java example is only relevant to mutable cases, but the point is it
demonstrates how allowing covariant subtyping on mutable generic types
leads to the same problem. It's not about how stuff that doesn't get
caught statically is handled at runtime, it's about what gets caught
statically. This was flatly just a mistake in the type system, and
the generics added to Java later do not work the same way in this regard
as arrays, since they'd discovered the mistake by the time they added
them.

Quoting ku...@bertec.com (2019-09-19 16:29:47)

> <[1]i...@zenhack.net>:

> > >
> > > Quoting 'Kenton Varda' via Cap'n Proto (2019-09-16 16:14:59)
> > >
> > >> � Anyway, I guess given that there's no such thing as a
> constant
> > >> � capability currently, we don't need to worry about that? And
> covariance
> > >> � is correct for all other types? So we could support it?
> > >
> > > It's sound for constants, but given that it's not for mutable
> values
> > > (even without caps), my gut is that adding this is probably not
> a good
> > > cost:benefit ratio. It would only enable creating constants that
> would
> > > be impossible to construct dynamically anyway, and it's not
> clear to me
> > > what sort of programming this enables that justifies that.
> > >
> > > -Ian
>

> --
> 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 [2]capnproto+...@googlegroups.com.

> To view this discussion on the web visit

> [3]https://groups.google.com/d/msgid/capnproto/29333b57-9383-4535-9949-
> e0ca0bff5c96%40googlegroups.com.
>
> Verweise
>
> 1. javascript:/
> 2. mailto:capnproto+...@googlegroups.com
> 3. https://groups.google.com/d/msgid/capnproto/29333b57-9383-4535-9949-e0ca0bff5c96%40googlegroups.com?utm_medium=email&utm_source=footer

[Kenton Varda]

FWIW

> const foo: AnyPointer = "hello";

Parsing this could be tricky because the literal "hello" isn't necessarily a Text; it could be a Data. This is why, in general, you can only assign an AnyPointer value to a named constant, because that named constant has an explicit type. That is:

> const fooText :Text = "foo";

> const foo :AnyPointer = .fooText;

However, it appears that this doesn't work either, currently. That seems like a bug. This does work:

> struct Foo {}
> const fooTyped :Foo = ();
> const foo :AnyPointer = .fooTyped;

As to the original question, again, I think what Kuba is trying to do ought to work.

And as to what's allowed at runtime, it seems reasonable that we could support covariance on struct-typed setters. Since setters make a copy, there is no soundness concern.

I am also not religious about soundness. I prioritize practicality.

-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/156892956443.821.23146561515920431%40localhost.localdomain.

[Ian Denhardt]

Quoting Kenton Varda (2019-09-20 15:01:44)

> As to the original question, again, I think what Kuba is trying to do
> ought to work.

I think I've come around to agreeing here.

> And as to what's allowed at runtime, it seems reasonable that we could
> support covariance on struct-typed setters. Since setters make a copy,
> there is no soundness concern.

I believe this may be correct, after having thought through the details.

> I am also not religious about soundness. I prioritize practicality.

I wasn't really arguing from a religious standpoint, but I think
requiring an explicit cast for possibly-unsound operations is not much
of a burden, and has clear benefits from a safety perspective, which are
well worth it. It seems like the point is moot in this case though.

-Ian