encoding/openapi: convert CUE to openapi schemas

Change-Id: Iea3369d702f7cb91e49e61153518c04d6845f03c
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/2120
Reviewed-by: Marcel van Lohuizen <mpvl@google.com>
diff --git a/encoding/openapi/build.go b/encoding/openapi/build.go
new file mode 100644
index 0000000..0cef528
--- /dev/null
+++ b/encoding/openapi/build.go
@@ -0,0 +1,696 @@
+// Copyright 2019 CUE Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package openapi
+
+import (
+	"fmt"
+	"math"
+	"path"
+	"strings"
+
+	"cuelang.org/go/cue"
+)
+
+type buildContext struct {
+	refPrefix string
+	path      []string
+
+	expandRefs bool
+
+	schemas *orderedMap
+}
+
+type oaSchema = orderedMap
+
+type typeFunc func(b *builder, a cue.Value)
+
+func components(inst *cue.Instance, cfg *Config) (comps *orderedMap, err error) {
+	c := buildContext{
+		refPrefix:  "components/schema",
+		expandRefs: cfg.ExpandReferences,
+		schemas:    &orderedMap{},
+	}
+
+	defer func() {
+		if x := recover(); x != nil {
+			// TODO: check if it's one of our own.
+			path := strings.Join(c.path, ".")
+			err = fmt.Errorf("error: %s: %v", path, x)
+		}
+	}()
+
+	schemas := &orderedMap{}
+	schemas.Set("schema", c.schemas)
+	comps = &orderedMap{}
+	comps.Set("openapi", "3.0.0")
+	comps.Set("components", schemas)
+
+	i, err := inst.Value().Fields()
+	if err != nil {
+		return nil, err
+	}
+	for i.Next() {
+		// message, enum, or constant.
+		c.schemas.Set(i.Label(), c.build(i.Value()))
+	}
+	return comps, nil
+}
+
+func (c *buildContext) build(v cue.Value) *oaSchema {
+	return newRootBuilder(c).schema(v)
+}
+
+func (b *builder) schema(v cue.Value) *oaSchema {
+	c := newRootBuilder(b.ctx)
+	c.value(v, nil)
+	schema := c.finish()
+	doc := []string{}
+	for _, d := range v.Doc() {
+		doc = append(doc, d.Text())
+	}
+	if len(doc) > 0 {
+		str := strings.TrimSpace(strings.Join(doc, "\n"))
+		schema.Prepend("description", str)
+	}
+	return schema
+}
+
+func (b *builder) value(v cue.Value, f typeFunc) {
+	count := 0
+	var values cue.Value
+	if b.ctx.expandRefs {
+		values = v
+		count = 1
+	} else {
+		for _, v := range appendSplit(nil, cue.AndOp, v) {
+			// This may be a reference to an enum. So we need to check references before
+			// dissecting them.
+			switch r := v.Reference(); {
+			case r != nil:
+				b.addRef(r)
+			default:
+				count++
+				values = values.Unify(v)
+			}
+		}
+	}
+
+	if count > 0 { // TODO: implement IsAny.
+		// NOTE: Eval is not necessary here. Removing it will yield
+		// different results that also are correct. The difference is that
+		// Eval detects and eliminates impossible combinations at the
+		// expense of having potentially much larger configurations due to
+		// a combinatorial explosion. This rudimentary check picks the least
+		// fo the two extreme forms.
+		if eval := values.Eval(); countNodes(eval) < countNodes(values) {
+			values = eval
+		}
+
+		for _, v := range appendSplit(nil, cue.AndOp, values) {
+			switch {
+			case isConcrete(v):
+				b.dispatch(f, v)
+				b.set("enum", []interface{}{decode(v)})
+
+			default:
+				if a := appendSplit(nil, cue.OrOp, v); len(a) > 1 {
+					b.disjunction(a, f)
+				} else {
+					v = a[0]
+					if err := v.Err(); err != nil {
+						panic(err)
+					}
+					b.dispatch(f, v)
+				}
+			}
+		}
+	}
+
+	if v, ok := v.Default(); ok && v.IsConcrete() {
+		v.Default()
+		b.set("default", v)
+	}
+}
+
+func appendSplit(a []cue.Value, splitBy cue.Op, v cue.Value) []cue.Value {
+	op, args := v.Expr()
+	if op == cue.NoOp && len(args) > 0 {
+		// TODO: this is to deal with default value removal. This may change
+		// whe we completely separate default values from values.
+		a = append(a, args...)
+	} else if op != splitBy {
+		a = append(a, v)
+	} else {
+		for _, v := range args {
+			a = appendSplit(a, splitBy, v)
+		}
+	}
+	return a
+}
+
+func countNodes(v cue.Value) (n int) {
+	switch op, a := v.Expr(); op {
+	case cue.OrOp, cue.AndOp:
+		for _, v := range a {
+			n += countNodes(v)
+		}
+		n += len(a) - 1
+	default:
+		switch v.Kind() {
+		case cue.ListKind:
+			for i, _ := v.List(); i.Next(); {
+				n += countNodes(i.Value())
+			}
+		case cue.StructKind:
+			for i, _ := v.Fields(); i.Next(); {
+				n += countNodes(i.Value()) + 1
+			}
+		}
+	}
+	return n + 1
+}
+
+// isConcrete reports whether v is concrete and not a struct (recursively).
+// structs are not supported as the result of a struct enum depends on how
+// conjunctions and disjunctions are distributed. We could consider still doing
+// this if we define a normal form.
+func isConcrete(v cue.Value) bool {
+	if !v.IsConcrete() {
+		return false
+	}
+	if v.Kind() == cue.StructKind {
+		return false // TODO: handle struct kinds
+	}
+	for list, _ := v.List(); list.Next(); {
+		if !isConcrete(list.Value()) {
+			return false
+		}
+	}
+	return true
+}
+
+func (b *builder) disjunction(a []cue.Value, f typeFunc) {
+	disjuncts := []cue.Value{}
+	enums := []interface{}{} // TODO: unique the enums
+	nullable := false        // Only supported in OpenAPI, not JSON schema
+
+	for _, v := range a {
+		switch {
+		case v.Null() == nil:
+			// TODO: for JSON schema, we need to fall through.
+			nullable = true
+
+		case isConcrete(v):
+			enums = append(enums, decode(v))
+
+		default:
+			disjuncts = append(disjuncts, v)
+		}
+	}
+
+	// Only one conjunct?
+	if len(disjuncts) == 0 || (len(disjuncts) == 1 && len(enums) == 0) {
+		if len(disjuncts) == 1 {
+			b.value(disjuncts[0], f)
+		}
+		if len(enums) > 0 {
+			b.set("enum", enums)
+		}
+		if nullable {
+			b.set("nullable", true)
+		}
+		return
+	}
+
+	b.addConjunct(func(b *builder) {
+		anyOf := []*oaSchema{}
+		if len(enums) > 0 {
+			anyOf = append(anyOf, b.kv("enum", enums))
+		}
+
+		for _, v := range disjuncts {
+			c := newOASBuilder(b)
+			c.value(v, f)
+			anyOf = append(anyOf, c.finish())
+		}
+
+		b.set("anyOf", anyOf)
+		if nullable {
+			b.set("nullable", true)
+		}
+	})
+}
+
+func (b *builder) dispatch(f typeFunc, v cue.Value) {
+	if f != nil {
+		f(b, v)
+		return
+	}
+
+	switch v.IncompleteKind() &^ cue.BottomKind {
+	case cue.NullKind:
+		// TODO: for JSON schema we would set the type here. For OpenAPI,
+		// it must be nullable.
+		b.set("nullable", true)
+
+	case cue.BoolKind:
+		b.setType("boolean", "")
+		// No need to call.
+
+	case cue.FloatKind, cue.NumberKind:
+		// TODO:
+		// Common   Name	type	format	Comments
+		// float	number	float
+		// double	number	double
+		b.setType("number", "") // may be overridden to integer
+		b.number(v)
+
+	case cue.IntKind:
+		// integer	integer	int32	signed 	32 bits
+		// long		integer	int64	signed 	64 bits
+		b.setType("integer", "") // may be overridden to integer
+		b.number(v)
+
+	case cue.BytesKind:
+		// byte		string	byte	base64 	encoded characters
+		// binary	string	binary	any 	sequence of octets
+		b.setType("string", "byte")
+		b.bytes(v)
+	case cue.StringKind:
+		// date		string			date	   As defined by full-date - RFC3339
+		// dateTime	string			date-time  As defined by date-time - RFC3339
+		// password	string			password   A hint to UIs to obscure input
+		b.setType("string", "")
+		b.string(v)
+	case cue.StructKind:
+		b.setType("object", "")
+		b.object(v)
+	case cue.ListKind:
+		b.setType("array", "")
+		b.array(v)
+	}
+}
+
+// object supports the following
+// - maxProperties: maximum allowed fields in this struct.
+// - minProperties: minimum required fields in this struct.a
+// - patternProperties: [regexp]: schema
+//   TODO: we can support this once .kv(key, value) allow
+//      foo [=~"pattern"]: type
+//      An instance field must match all schemas for which a regexp matches.
+//   Even though it is not supported in OpenAPI, we should still accept it
+//   when receiving from OpenAPI. We could possibly use disjunctions to encode
+//   this.
+// - dependencies: what?
+// - propertyNames: schema
+//   every property name in the enclosed schema matches that of
+func (b *builder) object(v cue.Value) {
+	// TODO: discriminator objects: we could theoretically derive discriminator
+	// objects automatically: for every object in a oneOf/allOf/anyOf, or any
+	// object composed of the same type, if a property is required and set to a
+	// constant value for each type, it is a discriminator.
+
+	required := []string{}
+	for i, _ := v.Fields(cue.Optional(false), cue.Hidden(false)); i.Next(); {
+		required = append(required, i.Label())
+	}
+	if len(required) > 0 {
+		b.set("required", required)
+	}
+
+	properties := map[string]*oaSchema{}
+	for i, _ := v.Fields(cue.Optional(true), cue.Hidden(false)); i.Next(); {
+		properties[i.Label()] = b.schema(i.Value())
+	}
+	if len(properties) > 0 {
+		b.set("properties", properties)
+	}
+
+	if t, ok := v.Elem(); ok {
+		b.set("additionalProperties", b.schema(t))
+	}
+
+	// TODO: maxProperties, minProperties: can be done once we allow cap to
+	// unify with structs.
+}
+
+// List constraints:
+//
+// Max and min items.
+// - maxItems: int (inclusive)
+// - minItems: int (inclusive)
+// - items (item type)
+//   schema: applies to all items
+//   array of schemas:
+//       schema at pos must match if both value and items are defined.
+// - additional items:
+//   schema: where items must be an array of schemas, intstance elements
+//   succeed for if they match this value for any value at a position
+//   greater than that covered by items.
+// - uniqueItems: bool
+//   TODO: support with list.Unique() unique() or comprehensions.
+//   For the latter, we need equality for all values, which is doable,
+//   but not done yet.
+//
+// NOT SUPPORTED IN OpenAPI:
+// - contains:
+//   schema: an array instance is valid if at least one element matches
+//   this schema.
+func (b *builder) array(v cue.Value) {
+	// Possible conjuncts:
+	//   - one list (CUE guarantees merging all conjuncts)
+	//   - no cap: is unified with list
+	//   - unique items: at most one, but idempotent if multiple.
+	// There is never a need for allOf or anyOf. Note that a CUE list
+	// corresponds almost one-to-one to OpenAPI lists.
+	items := []*oaSchema{}
+	for i, _ := v.List(); i.Next(); {
+		items = append(items, b.schema(i.Value()))
+	}
+	if len(items) > 0 {
+		// TODO: per-item schema are not allowed in OpenAPI, only in JSON Schema.
+		// Perhaps we should turn this into an OR after first normalizing
+		// the entries.
+		b.set("items", items)
+		// panic("per-item types not supported in OpenAPI")
+	}
+
+	// TODO:
+	// A CUE cap can be a set of discontinuous ranges. If we encounter this,
+	// we can create an allOf(list type, anyOf(ranges)).
+	cap := v.Len()
+	hasMax := false
+	maxLength := int64(math.MaxInt64)
+
+	if n, capErr := cap.Int64(); capErr == nil {
+		maxLength = n
+		hasMax = true
+	} else {
+		b.value(cap, (*builder).listCap)
+	}
+
+	if !hasMax || int64(len(items)) < maxLength {
+		if typ, ok := v.Elem(); ok {
+			t := b.schema(typ)
+			if len(items) > 0 {
+				b.set("additionalItems", t)
+			} else {
+				b.set("items", t)
+			}
+		}
+	}
+}
+
+func (b *builder) listCap(v cue.Value) {
+	switch op, a := v.Expr(); op {
+	case cue.LessThanOp:
+		b.set("maxItems", b.int(a[0])-1)
+	case cue.LessThanEqualOp:
+		b.set("maxItems", b.int(a[0]))
+	case cue.GreaterThanOp:
+		b.set("minItems", b.int(a[0])+1)
+	case cue.GreaterThanEqualOp:
+		if b.int(a[0]) > 0 {
+			b.set("minItems", b.int(a[0]))
+		}
+	case cue.NoOp:
+		// must be type, so okay.
+	case cue.NotEqualOp:
+		i := b.int(a[0])
+		b.setNot("allOff", []*oaSchema{
+			b.kv("minItems", i),
+			b.kv("maxItems", i),
+		})
+
+	default:
+		panic(fmt.Sprintf("unsupported op for list capacity %v", op))
+	}
+}
+
+func (b *builder) number(v cue.Value) {
+	// Multiple conjuncts mostly means just additive constraints.
+	// Type may be number of float.
+	// TODO: deterimine integer kind.
+	// if v.IsInt() {
+	// 	b.typ = "integer"
+	// }
+
+	switch op, a := v.Expr(); op {
+	// TODO: support the following JSON schema constraints
+	// - multipleOf
+	// setIntConstraint(t, "multipleOf", a)
+
+	case cue.LessThanOp:
+		b.set("exclusiveMaximum", b.int(a[0]))
+
+	case cue.LessThanEqualOp:
+		b.set("maximum", b.int(a[0]))
+
+	case cue.GreaterThanOp:
+		b.set("exclusiveMinimum", b.int(a[0]))
+
+	case cue.GreaterThanEqualOp:
+		b.set("minimum", b.int(a[0]))
+
+	case cue.NotEqualOp:
+		i := b.int(a[0])
+		b.setNot("allOff", []*oaSchema{
+			b.kv("minItems", i),
+			b.kv("maxItems", i),
+		})
+
+	case cue.NoOp:
+		// TODO: extract format from specific type.
+
+	default:
+		// panic(fmt.Sprintf("unsupported of %v for number type", op))
+	}
+}
+
+// Multiple Regexp conjuncts are represented as allOf all other
+// constraints can be combined unless in the even of discontinuous
+// lengths.
+
+// string supports the following options:
+//
+// - maxLenght (Unicode codepoints)
+// - minLenght (Unicode codepoints)
+// - pattern (a regexp)
+//
+// The regexp pattern is as follows, and is limited to be a  strict subset of RE2:
+// Ref: https://tools.ietf.org/html/draft-wright-json-schema-validation-01#section-3.3
+//
+// JSON schema requires ECMA 262 regular expressions, but
+// limited to the following constructs:
+//   - simple character classes: [abc]
+//   - range character classes: [a-z]
+//   - complement character classes: [^abc], [^a-z]
+//   - simple quantifiers: +, *, ?, and lazy versions +? *? ??
+//   - range quantifiers: {x}, {x,y}, {x,}, {x}?, {x,y}?, {x,}?
+//   - begin and end anchors: ^ and $
+//   - simple grouping: (...)
+//   - alteration: |
+// This is a subset of RE2 used by CUE.
+//
+// Most notably absent:
+//   - the '.' for any character (not sure if that is a doc bug)
+//   - character classes \d \D [[::]] \pN \p{Name} \PN \P{Name}
+//   - word boundaries
+//   - capturing directives.
+//   - flag setting
+//   - comments
+//
+// The capturing directives and comments can be removed without
+// compromising the meaning of the regexp (TODO). Removing
+// flag setting will be tricky. Unicode character classes,
+// boundaries, etc can be compiled into simple character classes,
+// although the resulting regexp will look cumbersome.
+//
+func (b *builder) string(v cue.Value) {
+	switch op, a := v.Expr(); op {
+
+	case cue.RegexMatchOp, cue.NotRegexMatchOp:
+		s, err := a[0].String()
+		if err != nil {
+			// TODO: this may be an unresolved interpolation or expression. Consider
+			// whether it is reasonable to treat unevaluated operands as wholes and
+			// generate a compound regular expression.
+			panic(err)
+		}
+		if op == cue.RegexMatchOp {
+			b.set("pattern", s)
+		} else {
+			b.setNot("pattern", s)
+		}
+
+		// TODO: support the following JSON schema constraints
+		// - maxLength
+		// - minLength
+
+	case cue.NoOp:
+		// TODO: determine formats from specific types.
+
+	default:
+		panic(fmt.Sprintf("unsupported of %v for bytes type", op))
+	}
+}
+
+func (b *builder) bytes(v cue.Value) {
+	switch op, a := v.Expr(); op {
+
+	case cue.RegexMatchOp, cue.NotRegexMatchOp:
+		s, err := a[0].Bytes()
+		if err != nil {
+			// TODO: this may be an unresolved interpolation or expression. Consider
+			// whether it is reasonable to treat unevaluated operands as wholes and
+			// generate a compound regular expression.
+			panic(err)
+		}
+
+		if op == cue.RegexMatchOp {
+			b.set("pattern", s)
+		} else {
+			b.setNot("pattern", s)
+		}
+
+		// TODO: support the following JSON schema constraints
+		// - maxLength
+		// - minLength
+
+	case cue.NoOp:
+
+	default:
+		panic(fmt.Sprintf("unsupported of %v for bytes type", op))
+	}
+}
+
+type builder struct {
+	ctx     *buildContext
+	typ     string
+	format  string
+	current *oaSchema
+	allOf   []*oaSchema
+	enums   []interface{}
+}
+
+func newRootBuilder(c *buildContext) *builder {
+	return &builder{ctx: c}
+}
+
+func newOASBuilder(parent *builder) *builder {
+	b := &builder{
+		ctx:    parent.ctx,
+		typ:    parent.typ,
+		format: parent.format,
+	}
+	return b
+}
+
+func (b *builder) setType(t, format string) {
+	if b.typ == "" {
+		b.typ = t
+		b.format = format
+	}
+}
+
+func setType(t *oaSchema, b *builder) {
+	if b.typ != "" {
+		t.Set("type", b.typ)
+		if b.format != "" {
+			t.Set("format", b.format)
+		}
+	}
+}
+
+func (b *builder) set(key string, v interface{}) {
+	if b.current == nil {
+		b.current = &orderedMap{}
+		b.allOf = append(b.allOf, b.current)
+		setType(b.current, b)
+	} else if b.current.Exists(key) {
+		b.current = &orderedMap{}
+		b.allOf = append(b.allOf, b.current)
+	}
+	b.current.Set(key, v)
+}
+
+func (b *builder) kv(key string, value interface{}) *oaSchema {
+	constraint := &orderedMap{}
+	setType(constraint, b)
+	constraint.Set(key, value)
+	return constraint
+}
+
+func (b *builder) setNot(key string, value interface{}) {
+	not := &orderedMap{}
+	not.Set("not", b.kv(key, value))
+	b.add(not)
+}
+
+func (b *builder) finish() *oaSchema {
+	switch len(b.allOf) {
+	case 0:
+		if b.typ == "" {
+			panic("no type specified at finish")
+		}
+		t := &orderedMap{}
+		setType(t, b)
+		return t
+
+	case 1:
+		setType(b.allOf[0], b)
+		return b.allOf[0]
+
+	default:
+		t := &orderedMap{}
+		t.Set("allOf", b.allOf)
+		return t
+	}
+}
+
+func (b *builder) add(t *oaSchema) {
+	b.allOf = append(b.allOf, t)
+}
+
+func (b *builder) addConjunct(f func(*builder)) {
+	c := newOASBuilder(b)
+	f(c)
+	b.add(c.finish())
+}
+
+func (b *builder) addRef(ref []string) {
+	// TODO: validate path.
+	// TODO: map CUE types to OAPI types.
+	b.addConjunct(func(b *builder) {
+		a := append([]string{"#", b.ctx.refPrefix}, ref...)
+		b.set("$ref", path.Join(a...))
+	})
+}
+
+func (b *builder) int(v cue.Value) int64 {
+	i, err := v.Int64()
+	if err != nil {
+		panic("could not retrieve int")
+	}
+	return i
+}
+
+func decode(v cue.Value) interface{} {
+	var d interface{}
+	if err := v.Decode(&d); err != nil {
+		panic(err)
+	}
+	return d
+}
diff --git a/encoding/openapi/doc.go b/encoding/openapi/doc.go
new file mode 100644
index 0000000..42bf934
--- /dev/null
+++ b/encoding/openapi/doc.go
@@ -0,0 +1,34 @@
+// Copyright 2019 CUE Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Package openapi provides functionality for mapping CUE to and from
+// OpenAPI v3.0.0.
+//
+// It currently handles OpenAPI Schema components only.
+//
+// See https://github.com/OAI/OpenAPI-Specification/blob/master/versions/3.0.0.md#schemaObject.
+package openapi
+
+// TODO:
+// * map range boundaries to format For instance,
+// 		{
+//			"type": "integer",
+//			"minimum": -2147483648,
+//			"maximum": 2147483647
+//		}
+//     should map to
+// 		{
+//			"type": "integer",
+//			"format": "int32"
+//		}
diff --git a/encoding/openapi/openapi.go b/encoding/openapi/openapi.go
new file mode 100644
index 0000000..9e3acd2
--- /dev/null
+++ b/encoding/openapi/openapi.go
@@ -0,0 +1,56 @@
+// Copyright 2019 CUE Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package openapi
+
+import (
+	"encoding/json"
+
+	"cuelang.org/go/cue"
+)
+
+// A Config defines options for mapping CUE to and from OpenAPI.
+type Config struct {
+	// ExpandReferences replaces references with actual objects when generating
+	// OpenAPI Schema. It is an error for an CUE value to refer to itself
+	// when this object is used.
+	ExpandReferences bool
+}
+
+// Gen generates the set OpenAPI schema for all top-level types of the given
+// instance.
+//
+func Gen(inst *cue.Instance, c *Config) ([]byte, error) {
+	if c == nil {
+		c = defaultConfig
+	}
+	comps, err := components(inst, c)
+	if err != nil {
+		return nil, err
+	}
+	return json.Marshal(comps)
+}
+
+var defaultConfig = &Config{}
+
+// TODO
+// The conversion interprets @openapi(<entry> {, <entry>}) attributes as follows:
+//
+//      readOnly        sets the readOnly flag for a property in the schema
+//                      only one of readOnly and writeOnly may be set.
+//      writeOnly       sets the writeOnly flag for a property in the schema
+//                      only one of readOnly and writeOnly may be set.
+//      discriminator   explicitly sets a field as the discriminator field
+//      deprecated      sets a field as deprecated
+//
diff --git a/encoding/openapi/openapi_test.go b/encoding/openapi/openapi_test.go
new file mode 100644
index 0000000..504b75a
--- /dev/null
+++ b/encoding/openapi/openapi_test.go
@@ -0,0 +1,80 @@
+// Copyright 2019 CUE Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package openapi
+
+import (
+	"bytes"
+	"encoding/json"
+	"flag"
+	"io/ioutil"
+	"path/filepath"
+	"testing"
+
+	"cuelang.org/go/cue"
+	"cuelang.org/go/cue/build"
+	"cuelang.org/go/cue/load"
+	"cuelang.org/go/cue/parser"
+	"github.com/kylelemons/godebug/diff"
+)
+
+var update *bool = flag.Bool("update", false, "update the test output")
+
+var config = &load.Config{
+	Context: build.NewContext(build.ParseOptions(parser.ParseComments)),
+}
+
+func TestParseDefinitions(t *testing.T) {
+	defaultConfig := &Config{}
+	resolveRefs := &Config{ExpandReferences: true}
+
+	testCases := []struct {
+		in, out string
+		config  *Config
+	}{{
+		"openapi.cue",
+		"openapi.json",
+		defaultConfig,
+	}, {
+		"openapi.cue",
+		"openapi-norefs.json",
+		resolveRefs,
+	}}
+	for _, tc := range testCases {
+		t.Run(tc.out, func(t *testing.T) {
+			filename := filepath.Join("testdata", filepath.FromSlash(tc.in))
+
+			inst := cue.Build(load.Instances([]string{filename}, config))[0]
+
+			b, err := Gen(inst, tc.config)
+			var out = &bytes.Buffer{}
+			json.Indent(out, b, "", "   ")
+
+			wantFile := filepath.Join("testdata", tc.out)
+			if *update {
+				ioutil.WriteFile(wantFile, out.Bytes(), 0644)
+				return
+			}
+
+			b, err = ioutil.ReadFile(wantFile)
+			if err != nil {
+				t.Fatal(err)
+			}
+
+			if d := diff.Diff(string(b), out.String()); d != "" {
+				t.Errorf("files differ:\n%v", d)
+			}
+		})
+	}
+}
diff --git a/encoding/openapi/orderedmap.go b/encoding/openapi/orderedmap.go
new file mode 100644
index 0000000..74e789f
--- /dev/null
+++ b/encoding/openapi/orderedmap.go
@@ -0,0 +1,71 @@
+// Copyright 2019 CUE Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package openapi
+
+import "encoding/json"
+
+type orderedMap []kvPair
+
+type kvPair struct {
+	key   string
+	value interface{}
+}
+
+func (m *orderedMap) Prepend(key string, value interface{}) {
+	*m = append([]kvPair{{key, value}}, (*m)...)
+}
+
+func (m *orderedMap) Set(key string, value interface{}) {
+	for i, v := range *m {
+		if v.key == key {
+			(*m)[i].value = value
+			return
+		}
+	}
+	*m = append(*m, kvPair{key, value})
+}
+
+func (m *orderedMap) Exists(key string) bool {
+	for _, v := range *m {
+		if v.key == key {
+			return true
+		}
+	}
+	return false
+}
+
+func (m *orderedMap) MarshalJSON() (b []byte, err error) {
+	b = append(b, '{')
+	for i, v := range *m {
+		if i > 0 {
+			b = append(b, ",\n"...)
+		}
+		key, err := json.Marshal(v.key)
+		if je, ok := err.(*json.MarshalerError); ok {
+			return nil, je.Err
+		}
+		b = append(b, key...)
+		b = append(b, ": "...)
+
+		value, err := json.Marshal(v.value)
+		if je, ok := err.(*json.MarshalerError); ok {
+			// return nil, je.Err
+			value, _ = json.Marshal(je.Err.Error())
+		}
+		b = append(b, value...)
+	}
+	b = append(b, '}')
+	return b, nil
+}
diff --git a/encoding/openapi/testdata/openapi-norefs.json b/encoding/openapi/testdata/openapi-norefs.json
new file mode 100644
index 0000000..075be6b
--- /dev/null
+++ b/encoding/openapi/testdata/openapi-norefs.json
@@ -0,0 +1,311 @@
+{
+   "openapi": "3.0.0",
+   "components": {
+      "schema": {
+         "MyMessage": {
+            "description": "MyMessage is my message.",
+            "allOf": [
+               {
+                  "type": "object",
+                  "required": [
+                     "foo",
+                     "bar"
+                  ],
+                  "properties": {
+                     "bar": {
+                        "type": "array",
+                        "items": {
+                           "type": "string"
+                        },
+                        "default": []
+                     },
+                     "foo": {
+                        "type": "number",
+                        "exclusiveMinimum": 10,
+                        "exclusiveMaximum": 1000
+                     },
+                     "port": {
+                        "type": "object",
+                        "required": [
+                           "port",
+                           "obj"
+                        ],
+                        "properties": {
+                           "obj": {
+                              "type": "array",
+                              "items": {
+                                 "type": "integer"
+                              },
+                              "default": []
+                           },
+                           "port": {
+                              "type": "integer"
+                           }
+                        }
+                     }
+                  }
+               },
+               {
+                  "type": "object",
+                  "anyOf": [
+                     {
+                        "type": "object",
+                        "required": [
+                           "a"
+                        ],
+                        "properties": {
+                           "a": {
+                              "description": "Field a.",
+                              "type": "integer",
+                              "enum": [
+                                 1
+                              ]
+                           }
+                        }
+                     },
+                     {
+                        "type": "object",
+                        "required": [
+                           "b"
+                        ],
+                        "properties": {
+                           "b": {
+                              "type": "string"
+                           }
+                        }
+                     }
+                  ]
+               }
+            ]
+         },
+         "Port": {
+            "type": "object",
+            "required": [
+               "port",
+               "obj"
+            ],
+            "properties": {
+               "obj": {
+                  "type": "array",
+                  "items": {
+                     "type": "integer"
+                  },
+                  "default": []
+               },
+               "port": {
+                  "type": "integer"
+               }
+            }
+         },
+         "Int32": {
+            "type": "integer",
+            "minimum": -2147483648,
+            "maximum": 2147483647
+         },
+         "YourMessage": {
+            "anyOf": [
+               {
+                  "type": "object",
+                  "required": [
+                     "b"
+                  ],
+                  "properties": {
+                     "a": {
+                        "type": "string"
+                     },
+                     "b": {
+                        "type": "string"
+                     }
+                  }
+               },
+               {
+                  "type": "object",
+                  "required": [
+                     "b"
+                  ],
+                  "properties": {
+                     "a": {
+                        "type": "string"
+                     },
+                     "b": {
+                        "type": "number"
+                     }
+                  }
+               }
+            ]
+         },
+         "YourMessage2": {
+            "allOf": [
+               {
+                  "anyOf": [
+                     {
+                        "type": "object",
+                        "required": [
+                           "a"
+                        ],
+                        "properties": {
+                           "a": {
+                              "type": "number"
+                           }
+                        }
+                     },
+                     {
+                        "type": "object",
+                        "required": [
+                           "b"
+                        ],
+                        "properties": {
+                           "b": {
+                              "type": "number"
+                           }
+                        }
+                     }
+                  ]
+               },
+               {
+                  "anyOf": [
+                     {
+                        "type": "object",
+                        "required": [
+                           "c"
+                        ],
+                        "properties": {
+                           "c": {
+                              "type": "number"
+                           }
+                        }
+                     },
+                     {
+                        "type": "object",
+                        "required": [
+                           "d"
+                        ],
+                        "properties": {
+                           "d": {
+                              "type": "number"
+                           }
+                        }
+                     }
+                  ]
+               },
+               {
+                  "anyOf": [
+                     {
+                        "type": "object",
+                        "required": [
+                           "e"
+                        ],
+                        "properties": {
+                           "e": {
+                              "type": "number"
+                           }
+                        }
+                     },
+                     {
+                        "type": "object",
+                        "required": [
+                           "f"
+                        ],
+                        "properties": {
+                           "f": {
+                              "type": "number"
+                           }
+                        }
+                     }
+                  ]
+               }
+            ]
+         },
+         "Msg2": {
+            "anyOf": [
+               {
+                  "type": "object",
+                  "required": [
+                     "b"
+                  ],
+                  "properties": {
+                     "b": {
+                        "type": "number"
+                     }
+                  }
+               },
+               {
+                  "type": "object",
+                  "required": [
+                     "a"
+                  ],
+                  "properties": {
+                     "a": {
+                        "type": "string"
+                     }
+                  }
+               }
+            ]
+         },
+         "Enum": {
+            "enum": [
+               "foo",
+               "bar",
+               "baz"
+            ]
+         },
+         "List": {
+            "type": "array",
+            "items": {
+               "type": "number"
+            },
+            "default": [
+               1,
+               2,
+               3
+            ]
+         },
+         "DefaultStruct": {
+            "allOf": [
+               {
+                  "anyOf": [
+                     {
+                        "type": "object",
+                        "required": [
+                           "port",
+                           "obj"
+                        ],
+                        "properties": {
+                           "obj": {
+                              "type": "array",
+                              "items": {
+                                 "type": "integer"
+                              },
+                              "default": []
+                           },
+                           "port": {
+                              "type": "integer"
+                           }
+                        }
+                     },
+                     {
+                        "type": "object",
+                        "required": [
+                           "port"
+                        ],
+                        "properties": {
+                           "port": {
+                              "type": "integer",
+                              "enum": [
+                                 1
+                              ]
+                           }
+                        }
+                     }
+                  ]
+               },
+               {
+                  "default": {
+                     "port": 1
+                  }
+               }
+            ]
+         }
+      }
+   }
+}
\ No newline at end of file
diff --git a/encoding/openapi/testdata/openapi.cue b/encoding/openapi/testdata/openapi.cue
new file mode 100644
index 0000000..c4308e8
--- /dev/null
+++ b/encoding/openapi/testdata/openapi.cue
@@ -0,0 +1,39 @@
+package openapi
+
+// MyMessage is my message.
+MyMessage: {
+	port?: Port & {} @protobuf(1)
+
+	foo: Int32 & >10 & <1000 & int32 @protobuf(2)
+
+	bar: [...string] @protobuf(3)
+}
+
+MyMessage: {
+	// Field a.
+	a: 1
+} | {
+	b: string //2: crash
+}
+
+YourMessage: ({a: number} | {b: string} | {b: number}) & {a?: string}
+
+YourMessage2: ({a: number} | {b: number}) &
+	({c: number} | {d: number}) &
+	({e: number} | {f: number})
+
+Msg2: {b: number} | {a: string}
+
+Int32: int32
+
+Enum: "foo" | "bar" | "baz"
+
+List: [...number] | *[1, 2, 3]
+
+DefaultStruct: Port | *{port: 1}
+
+Port: {
+	port: int
+
+	obj: [...int]
+}
diff --git a/encoding/openapi/testdata/openapi.json b/encoding/openapi/testdata/openapi.json
new file mode 100644
index 0000000..c6cc8cb
--- /dev/null
+++ b/encoding/openapi/testdata/openapi.json
@@ -0,0 +1,287 @@
+{
+   "openapi": "3.0.0",
+   "components": {
+      "schema": {
+         "MyMessage": {
+            "description": "MyMessage is my message.",
+            "allOf": [
+               {
+                  "type": "object",
+                  "required": [
+                     "foo",
+                     "bar"
+                  ],
+                  "properties": {
+                     "bar": {
+                        "type": "array",
+                        "items": {
+                           "type": "string"
+                        },
+                        "default": []
+                     },
+                     "foo": {
+                        "allOf": [
+                           {
+                              "$ref": "#/components/schema/Int32"
+                           },
+                           {
+                              "type": "number",
+                              "exclusiveMinimum": 10,
+                              "exclusiveMaximum": 1000
+                           }
+                        ]
+                     },
+                     "port": {
+                        "$ref": "#/components/schema/Port",
+                        "type": "object"
+                     }
+                  }
+               },
+               {
+                  "type": "object",
+                  "anyOf": [
+                     {
+                        "type": "object",
+                        "required": [
+                           "a"
+                        ],
+                        "properties": {
+                           "a": {
+                              "description": "Field a.",
+                              "type": "integer",
+                              "enum": [
+                                 1
+                              ]
+                           }
+                        }
+                     },
+                     {
+                        "type": "object",
+                        "required": [
+                           "b"
+                        ],
+                        "properties": {
+                           "b": {
+                              "type": "string"
+                           }
+                        }
+                     }
+                  ]
+               }
+            ]
+         },
+         "Port": {
+            "type": "object",
+            "required": [
+               "port",
+               "obj"
+            ],
+            "properties": {
+               "obj": {
+                  "type": "array",
+                  "items": {
+                     "type": "integer"
+                  },
+                  "default": []
+               },
+               "port": {
+                  "type": "integer"
+               }
+            }
+         },
+         "Int32": {
+            "type": "integer",
+            "minimum": -2147483648,
+            "maximum": 2147483647
+         },
+         "YourMessage": {
+            "anyOf": [
+               {
+                  "type": "object",
+                  "required": [
+                     "b"
+                  ],
+                  "properties": {
+                     "a": {
+                        "type": "string"
+                     },
+                     "b": {
+                        "type": "string"
+                     }
+                  }
+               },
+               {
+                  "type": "object",
+                  "required": [
+                     "b"
+                  ],
+                  "properties": {
+                     "a": {
+                        "type": "string"
+                     },
+                     "b": {
+                        "type": "number"
+                     }
+                  }
+               }
+            ]
+         },
+         "YourMessage2": {
+            "allOf": [
+               {
+                  "anyOf": [
+                     {
+                        "type": "object",
+                        "required": [
+                           "a"
+                        ],
+                        "properties": {
+                           "a": {
+                              "type": "number"
+                           }
+                        }
+                     },
+                     {
+                        "type": "object",
+                        "required": [
+                           "b"
+                        ],
+                        "properties": {
+                           "b": {
+                              "type": "number"
+                           }
+                        }
+                     }
+                  ]
+               },
+               {
+                  "anyOf": [
+                     {
+                        "type": "object",
+                        "required": [
+                           "c"
+                        ],
+                        "properties": {
+                           "c": {
+                              "type": "number"
+                           }
+                        }
+                     },
+                     {
+                        "type": "object",
+                        "required": [
+                           "d"
+                        ],
+                        "properties": {
+                           "d": {
+                              "type": "number"
+                           }
+                        }
+                     }
+                  ]
+               },
+               {
+                  "anyOf": [
+                     {
+                        "type": "object",
+                        "required": [
+                           "e"
+                        ],
+                        "properties": {
+                           "e": {
+                              "type": "number"
+                           }
+                        }
+                     },
+                     {
+                        "type": "object",
+                        "required": [
+                           "f"
+                        ],
+                        "properties": {
+                           "f": {
+                              "type": "number"
+                           }
+                        }
+                     }
+                  ]
+               }
+            ]
+         },
+         "Msg2": {
+            "anyOf": [
+               {
+                  "type": "object",
+                  "required": [
+                     "b"
+                  ],
+                  "properties": {
+                     "b": {
+                        "type": "number"
+                     }
+                  }
+               },
+               {
+                  "type": "object",
+                  "required": [
+                     "a"
+                  ],
+                  "properties": {
+                     "a": {
+                        "type": "string"
+                     }
+                  }
+               }
+            ]
+         },
+         "Enum": {
+            "enum": [
+               "foo",
+               "bar",
+               "baz"
+            ]
+         },
+         "List": {
+            "type": "array",
+            "items": {
+               "type": "number"
+            },
+            "default": [
+               1,
+               2,
+               3
+            ]
+         },
+         "DefaultStruct": {
+            "allOf": [
+               {
+                  "anyOf": [
+                     {
+                        "$ref": "#/components/schema/Port"
+                     },
+                     {
+                        "type": "object",
+                        "required": [
+                           "port"
+                        ],
+                        "properties": {
+                           "port": {
+                              "type": "integer",
+                              "enum": [
+                                 1
+                              ]
+                           }
+                        }
+                     }
+                  ]
+               },
+               {
+                  "default": {
+                     "port": 1
+                  }
+               }
+            ]
+         }
+      }
+   }
+}
\ No newline at end of file
diff --git a/go.mod b/go.mod
index 9e941a7..8f75590 100644
--- a/go.mod
+++ b/go.mod
@@ -7,6 +7,7 @@
 	github.com/ghodss/yaml v1.0.0
 	github.com/google/go-cmp v0.2.0
 	github.com/kr/pretty v0.1.0
+	github.com/kylelemons/godebug v1.1.0
 	github.com/lib/pq v1.0.0 // indirect
 	github.com/mitchellh/go-homedir v1.0.0
 	github.com/pkg/errors v0.8.0 // indirect
diff --git a/go.sum b/go.sum
index 20e8381..4b480ba 100644
--- a/go.sum
+++ b/go.sum
@@ -27,6 +27,8 @@
 github.com/kr/pty v1.1.1/go.mod h1:pFQYn66WHrOpPYNljwOMqo10TkYh1fy3cYio2l3bCsQ=
 github.com/kr/text v0.1.0 h1:45sCR5RtlFHMR4UwH9sdQ5TC8v0qDQCHnXt+kaKSTVE=
 github.com/kr/text v0.1.0/go.mod h1:4Jbv+DJW3UT/LiOwJeYQe1efqtUx/iVham/4vfdArNI=
+github.com/kylelemons/godebug v1.1.0 h1:RPNrshWIDI6G2gRW9EHilWtl7Z6Sb1BR0xunSBf0SNc=
+github.com/kylelemons/godebug v1.1.0/go.mod h1:9/0rRGxNHcop5bhtWyNeEfOS8JIWk580+fNqagV/RAw=
 github.com/lib/pq v1.0.0 h1:X5PMW56eZitiTeO7tKzZxFCSpbFZJtkMMooicw2us9A=
 github.com/lib/pq v1.0.0/go.mod h1:5WUZQaWbwv1U+lTReE5YruASi9Al49XbQIvNi/34Woo=
 github.com/logrusorgru/aurora v0.0.0-20180419164547-d694e6f975a9/go.mod h1:7rIyQOR62GCctdiQpZ/zOJlFyk6y+94wXzv6RNZgaR4=