New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optional fields in structs #2327

Closed
aboodman opened this Issue Aug 10, 2016 · 12 comments

Comments

Projects
None yet
3 participants
@aboodman
Contributor

aboodman commented Aug 10, 2016

Our lack of optional fields quickly leads to combinatorial explosion of types. If we have data like:

List(
  Struct({a:int}),
  Struct({b:int}),
  Struct({a:int, b:int}),
)

... we infer the type as:

List<
  Struct{a:int} |
  Struct{b:int} |
  Struct{a:int, b:int}
>

I think we should instead infer (conceptually):

List<Struct{a:?int, b:?int}>

I'm still not sure exactly how optional should work in Noms though. It could be a special concept (optional), or there could be a new type Nil that just means no value is acceptable (so you'd actually see: List<Struct{a:int|nil, b:int|nil}>.

Not sure what the tradeoff is.

@aboodman

This comment has been minimized.

Show comment
Hide comment
@aboodman

aboodman Aug 10, 2016

Contributor

See also related #2326

Contributor

aboodman commented Aug 10, 2016

See also related #2326

@aboodman

This comment has been minimized.

Show comment
Hide comment
@aboodman

aboodman Aug 15, 2016

Contributor

I was wondering today again if there was a way to do this without being a serialization change.

I think conceptually, you could represent optional like this:

struct T {
  foo: int|struct Nil{}
}

The nil struct could just be a convention. But I'm not sure if in practice this idea is compatible with our actual current serialization. @arv, what do you think is this workable?

Contributor

aboodman commented Aug 15, 2016

I was wondering today again if there was a way to do this without being a serialization change.

I think conceptually, you could represent optional like this:

struct T {
  foo: int|struct Nil{}
}

The nil struct could just be a convention. But I'm not sure if in practice this idea is compatible with our actual current serialization. @arv, what do you think is this workable?

@arv

This comment has been minimized.

Show comment
Hide comment
@arv

arv Aug 15, 2016

Contributor

That would work.

But it would not lead to smaller types unless we change makeCommitType or makeUnionType.

Contributor

arv commented Aug 15, 2016

That would work.

But it would not lead to smaller types unless we change makeCommitType or makeUnionType.

@aboodman

This comment has been minimized.

Show comment
Hide comment
@aboodman

aboodman Sep 27, 2016

Contributor

@kalman and i were talking about this again today.

Strawman:

  1. Establish a convention in noms format 7 that T|struct Nil{} means "optional".
  2. Change type validation to know about this convention. E.g., given struct Foo{bar: Number|Nil} and f := types.NewStruct("Foo", {}}, f is special-cased to be valid instance of Foo.

Discuss... @arv , @kalman

Contributor

aboodman commented Sep 27, 2016

@kalman and i were talking about this again today.

Strawman:

  1. Establish a convention in noms format 7 that T|struct Nil{} means "optional".
  2. Change type validation to know about this convention. E.g., given struct Foo{bar: Number|Nil} and f := types.NewStruct("Foo", {}}, f is special-cased to be valid instance of Foo.

Discuss... @arv , @kalman

@arv

This comment has been minimized.

Show comment
Hide comment
@arv

arv Sep 27, 2016

Contributor

That would work.

Contributor

arv commented Sep 27, 2016

That would work.

@arv

This comment has been minimized.

Show comment
Hide comment
@arv

arv Mar 21, 2017

Contributor

Here are some implementation ideas.

Only struct types need an optional bit. A struct value does not have a notion of optional. At this point all values carry a type. We will assert that there are no optional bits sets for values.

Currently we have two slices, one with names and one with types. We will add another one for optionality bit. This can be implemented as a bit set (https://godoc.org/xojoc.pw/bitset) or a slice of bool.

Places we need to update:

  • encoding/decoding
  • Is subtype
  • Type simplification
  • ngql
  • marshal
  • nomdl parser
  • human encoded serialization (strawman use fieldName?: type)
  • OID (oid is going away so maybe we can ignore this?)
  • ContainCommonSuperType
  • WalkDifferentStructs (can now take type predicate and prune search)
Contributor

arv commented Mar 21, 2017

Here are some implementation ideas.

Only struct types need an optional bit. A struct value does not have a notion of optional. At this point all values carry a type. We will assert that there are no optional bits sets for values.

Currently we have two slices, one with names and one with types. We will add another one for optionality bit. This can be implemented as a bit set (https://godoc.org/xojoc.pw/bitset) or a slice of bool.

Places we need to update:

  • encoding/decoding
  • Is subtype
  • Type simplification
  • ngql
  • marshal
  • nomdl parser
  • human encoded serialization (strawman use fieldName?: type)
  • OID (oid is going away so maybe we can ignore this?)
  • ContainCommonSuperType
  • WalkDifferentStructs (can now take type predicate and prune search)
@rafael-atticlabs

This comment has been minimized.

Show comment
Hide comment
@rafael-atticlabs

rafael-atticlabs Mar 21, 2017

Contributor

The BR type functions ContainCommonSuperType (and one other, unless I miss-remember).

I think some of other changes coming will precipitate some bigger changes in the encoding (I've been thinking alot about it and plan to write a design doc), so I wouldn't spend alot of time on compactness (e.g. bitfield) with this right now. I'd humbly suggest alternating field name & optional flag (rather than two slices), but if you feel strongly, just go for it.

Contributor

rafael-atticlabs commented Mar 21, 2017

The BR type functions ContainCommonSuperType (and one other, unless I miss-remember).

I think some of other changes coming will precipitate some bigger changes in the encoding (I've been thinking alot about it and plan to write a design doc), so I wouldn't spend alot of time on compactness (e.g. bitfield) with this right now. I'd humbly suggest alternating field name & optional flag (rather than two slices), but if you feel strongly, just go for it.

@arv arv self-assigned this Mar 21, 2017

@arv

This comment has been minimized.

Show comment
Hide comment
@arv

arv Mar 21, 2017

Contributor

@rafael-atticlabs I've started working on this and the encoding we have now is string, type, string type, ... so it will be string, type, bool, string, type, bool, ... How we represent StructDesc is not really important (it is currently two slices and I might make it a single slice of structs)

Contributor

arv commented Mar 21, 2017

@rafael-atticlabs I've started working on this and the encoding we have now is string, type, string type, ... so it will be string, type, bool, string, type, bool, ... How we represent StructDesc is not really important (it is currently two slices and I might make it a single slice of structs)

@arv

This comment has been minimized.

Show comment
Hide comment
@arv

arv Mar 21, 2017

Contributor

I'm aware of some of the changes we have planned but I didn't want to hold off optional types at this point. The extra work is minimal at this point.

Contributor

arv commented Mar 21, 2017

I'm aware of some of the changes we have planned but I didn't want to hold off optional types at this point. The extra work is minimal at this point.

@rafael-atticlabs

This comment has been minimized.

Show comment
Hide comment
@rafael-atticlabs

rafael-atticlabs Mar 22, 2017

Contributor

SGTM. Totally agree. Getting this done is blocking BR working properly.

Contributor

rafael-atticlabs commented Mar 22, 2017

SGTM. Totally agree. Getting this done is blocking BR working properly.

@arv

This comment has been minimized.

Show comment
Hide comment
@arv

arv Mar 22, 2017

Contributor

The current API I'm using is

types.MakeStructType2("Name", 
  types.StructField{"x", BoolType, true},
  types.StructField{Name: "y", Type: StringType, Optional: false},
)

The old MakeStructType and MakeStructTypeFromFields creates only required fields. My approach is to land with a strange name, update all usages to use MakeStructType2 and then rename MakeStructType2 to MakeStructType and remove the other two.

  • The question is what API we want?
  • Can the slice and field type names be made clearer?
  • I was thinking we would do the sorting of the fields
Contributor

arv commented Mar 22, 2017

The current API I'm using is

types.MakeStructType2("Name", 
  types.StructField{"x", BoolType, true},
  types.StructField{Name: "y", Type: StringType, Optional: false},
)

The old MakeStructType and MakeStructTypeFromFields creates only required fields. My approach is to land with a strange name, update all usages to use MakeStructType2 and then rename MakeStructType2 to MakeStructType and remove the other two.

  • The question is what API we want?
  • Can the slice and field type names be made clearer?
  • I was thinking we would do the sorting of the fields

@arv arv changed the title from We need optional fields in types to Optional fields in structs Mar 22, 2017

@arv

This comment has been minimized.

Show comment
Hide comment
@arv

arv Mar 22, 2017

Contributor

I talked to @ehalpern about ContainCommonSuperType. To us it seems like the semantics will not change. I'll add a few more tests though.

Contributor

arv commented Mar 22, 2017

I talked to @ehalpern about ContainCommonSuperType. To us it seems like the semantics will not change. I'll add a few more tests though.

@arv arv closed this in #3287 Mar 27, 2017

arv added a commit that referenced this issue Mar 27, 2017

Optional fields (#3287)
This adds optional fields to structs.

New version: 7.4

To create a struct type with optional fields use types.MakeStructType2

There are some API changes in this commit and there will be some more in followup commits.

Fixes #2327
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment