Struct upper bound

[cueckoo]

Originally opened by @pblkt in cuelang/cue#40

The behavior of struct unification specified as

The successful unification of structs a and b is a new struct c which has all fields of both a and b

Cannot define an upper bound for structs. Specifically, CUE cannot help us verify that the resulting expression is limited to allowed fields.

For example, the unification

base: {
  onlyViableField: string | *"myDefault"
}

{
  base & {onlyViableFeild: "nonDefaultValue"}
}

yields

{
  onlyViableField: "myDefault"
  onlyViableFeild: "nonDefaultValue"
}

In kubernetes, the existence of extraneous fields causes failure when kubectl applys the resulting YAML, whereas in other systems the expression above could use silently use the default value erroneously.

When comparing CUE to a typed configuration language (like dhall), this is a qualitative difference in capabilities, since the extraneous field would be found by explicitly typing the result.

Extraneous fields can be hard to find - especially in large, opaque, auto-generated config schemes.

[cueckoo]

Original reply by @pblkt in cuelang/cue#40 (comment)

A possibility to mitigate this is the addition of strict structs - witch have the same unification rules as ordinary structs, but without the rule that merges keys - so only concretization unification is allowed.

a: !{ // '!' is the suggested strict syntax
  a1: string
}

b: {
  a1: "thing"
}

c: {
  a1: "other"
  a2: 2
}

a & b             // result: !{ a1 : "thing" }
a & c             // result: _|_
a & b & c         // result: _|_

Note that unification transitivity (a & b) & c = a & ( b & c ) requires the unification of a strict struct and a non-strict one to result in a strict version.

[cueckoo]

Original reply by @mpvl in cuelang/cue#40 (comment)

@pebbleKite
Yes, I'm aware of this limitation and have been looking into solutions. There are broadly three different approaches:

1. a Typescript approach where the maximum is inferred. For instance, the element type of a map or list would limit the allowed elements unless it explicitly allows it.
2. An explicit limit. This could, in turn, be limited per value, as you suggest, or per field, for instance the Haskell style:

a :: {
   // fully defined struct, anything that unifies with this has cannot add fields.
}

3. a full-blown usage analysis to see where values end up and flagging any values that will not eventually be used. This solution would come with a "type casting" operation to eliminate fields. For instance, to send something to K8s, one would do something like v1.Service(myService) to cast your type and remove unnecessary fields. Any unused field is flagged.

In my opinion, the first approach is preferred, but it is not entirely clear if it a) is sufficient, and b) won't be too limiting. This won't solve your particular example, for instance. Using Typescript semantics, this would be an error indeed, but there are many cases where one would want to be able to extend a struct. In fact, for the same struct one would sometimes want to add it and sometimes not. In Typescript, the workaround is that unifying two references does not trigger the check, so adding an indirection solves it. But it this would be both unclear and awkward in CUE.

But adding the check for struct and list element types would be reasonable and probably cover a lot of ground. For instance for Kubernetes, something like this:

import "k8s.io/api/core/v1" // generated with cue get go k8s.io/api/core/v1

service <name>: v1.Service

or

services: [...v1.Service]

would only allow known fields for services in that case.

Are there practical cases you can think of where this would not be sufficient?

CUE is strongly typed, btw, this part is just not (yet) covered by the type system. :)

[cueckoo]

Original reply by @mpvl in cuelang/cue#40 (comment)

@pebbleKite: thanks for your response.

Since doing ([myVal] & [...myType])[0] as a "conversion" is functionally equivalent to option 2(explicit type annotations), I would only comment that it might be surprising that [...x] behaves in a special way rather than the ubiquitous unification. It's a non-default behavior in a nested syntax.

I think I understand you point. I'm not following the non-default part, but IIUC you are basically saying that !{} would be analogous in behavior to []. That is a fair point.

Related to this: as a last syntax change before guaranteeing backwards compatibility, I'm considering unifying the syntax for map and list:

• myMap <_>: string would become myMap [string]: string
• server <Name>: { name: Name, ... } -> server [Name=string]: string
• myList: [...string] -> myList [int]: string

This allows:

• maps of integer to values (useful for supporting TypeScript, Protobuf, etc.)
• unified selector notation: myMap.foo and myMay[key], but also myList.0 and myList[num]
• this in turn makes selection of the nodes on the LHS more uniform, but also allows for a more natural query notation.
• allows for specifying constraints on subsets: myList [>20&<30]: otherType
• the name binding is used much less than I expected so this deemphasizes this and gives a better alternative for <_>.
• bunch of other benefits.
• I could mostly make this a backwards compatible change (with automated rewrite on format)

Anyway, this may open up some other possibilities. For instance, it would allow ditching the ... token in favor of using the same operator to close/open lists and maps. Another possibility would be an operator to explicitly allow new fields elements where they otherwise were not allowed.

Either way, I'm writing an OpenAPI 3 <-> CUE converter now (which is quite eliminating by itself) and will look in to this soon thereafter. These kind of changes are tricky, as one needs to consider carefully that commutativity, associativity and idempotence are preserved, which is not always trivial. A lot of the power of the language is derived from these properties.

[cueckoo]

Original reply by @pblkt in cuelang/cue#40 (comment)

CUE is strongly typed, btw

Agree. A better phrasing would refer to the separation of types and values rather than typing strength.

would only allow known fields for services in that case.

So

myField: myValPrev
myField: myVal

would mean

myField :: myValPrev // ...and also...
myField :: myVal

rather than

myField : myValPrev & myVal

?

[cueckoo]

Original reply by @mpvl in cuelang/cue#40 (comment)

The meaning of :: would be along the following lines:

For a given field name, unify all its field declarations marked ::, then unify all fields marked : where the latter are not allowed to introduce new fields. “Template/Type” values from map and list specs mix in as ::.

In other words, :: usually means “is a”, so in this case it means the rest of this field must conform strictly to this “type”.

Note that this is not very well thought out. More a sketch based on a parallel drawn to Haskell. Not saying that this is my preferred option either, just a possibility.

[cueckoo]

Original reply by @mpvl in cuelang/cue#40 (comment)

See https://cue-review.googlesource.com/c/cue/+/2280 for a proposed change to the spec to support this.

[cueckoo]

Original reply by @jlongtine in cuelang/cue#40 (comment)

@mpvl I have been reading through your comments on closed structs in that proposal for a spec change, and I'm curious about how we might implement something like the CloudFormation AWS::S3::Bucket type.

{
  "Type" : "AWS::S3::Bucket",
  "Properties" : {
      "AccelerateConfiguration" : AccelerateConfiguration,
      "AccessControl" : String,
      "AnalyticsConfigurations" : [ AnalyticsConfiguration, ... ],
      "BucketEncryption" : BucketEncryption,
      "BucketName" : String,
      "CorsConfiguration" : CorsConfiguration,
      "InventoryConfigurations" : [ InventoryConfiguration, ... ],
      "LifecycleConfiguration" : LifecycleConfiguration,
      "LoggingConfiguration" : LoggingConfiguration,
      "MetricsConfigurations" : [ MetricsConfiguration, ... ],
      "NotificationConfiguration" : NotificationConfiguration,
      "ObjectLockConfiguration" : ObjectLockConfiguration,
      "ObjectLockEnabled" : Boolean,
      "PublicAccessBlockConfiguration" : PublicAccessBlockConfiguration,
      "ReplicationConfiguration" : ReplicationConfiguration,
      "Tags" : [ Tag, ... ],
      "VersioningConfiguration" : VersioningConfiguration,
      "WebsiteConfiguration" : WebsiteConfiguration
    }
}

Every one of those fields is optional, but I'd like to enforce that the user not add fields beyond these fields (because it would fail when submitted to CloudFormation). How would closed/open structs interact with this?

[cueckoo]

Original reply by @mpvl in cuelang/cue#40 (comment)

@jlongtine the spec was just updated to explain the mechanism. Closing a struct can be done with the close builtin. In practice, however, one would use a new construct called definitions. In your case, you would write:

Bucket :: {
  "Type" : "AWS::S3::Bucket",
  "Properties" : {
      "AccelerateConfiguration" : AccelerateConfiguration,
      "AccessControl" : String,
      "AnalyticsConfigurations" : [ ....AnalyticsConfiguration ],
      // ...
  }
}

AccelerateConfigurtion :: {
    // ...

Definitions differ from regular fields in two ways; 1) they are not part of the data model, 2) any literal struct defined within the scope of a definition is closed by default. To keep a struct open use a template or ....

The spec provides embedding (similar to Go and other languages) for extending definitions.

[cueckoo]

Original reply by @jlongtine in cuelang/cue#40 (comment)

@mpvl Sweet! I'm excited. We'll start playing with this soon!

[cueckoo]

Original reply by @mpvl in cuelang/cue#40 (comment)

This has been implemented.