pkg/list: add sort functionality
Unfortunately, quite a few reordering in tests.
Change-Id: I205adc611051e042be98b8d96d3322aee1f064a9
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/4481
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cue/builtin_test.go b/cue/builtin_test.go
index f68db8b..0ec2863 100644
--- a/cue/builtin_test.go
+++ b/cue/builtin_test.go
@@ -240,6 +240,28 @@
test("list", `list.Slice([1, 2, 3, 4], 1, 5)`),
`_|_(error in call to list.Slice: slice bounds out of range)`,
}, {
+ test("list", `list.Sort([], list.Ascending)`),
+ `[]`,
+ }, {
+ test("list", `list.Sort([2, 3, 1, 4], {x:_, y:_, less: (x<y)})`),
+ `[1,2,3,4]`,
+ }, {
+ test("list", `list.SortStable([{a:2,v:1}, {a:1,v:2}, {a:1,v:3}], {
+ x:_,
+ y:_,
+ less: (x.a < y.a)
+ })`),
+ `[{a: 1, v: 2},{a: 1, v: 3},{a: 2, v: 1}]`,
+ }, {
+ test("list", `list.Sort([{a:1}, {b:2}], list.Ascending)`),
+ `_|_(error in call to list.Sort: conflicting values close(T, close(T)) and {b: 2} (mismatched types number|string and struct))`,
+ }, {
+ test("list", `list.SortStrings(["b", "a"])`),
+ `["a","b"]`,
+ }, {
+ test("list", `list.SortStrings([1, 2])`),
+ `_|_(invalid list element 0 in argument 0 to list.SortStrings: cannot use value 1 (type int) as string)`,
+ }, {
test("list", `list.Sum([1, 2, 3, 4])`),
`10`,
}, {
diff --git a/cue/builtins.go b/cue/builtins.go
index 9668515..5635d40 100644
--- a/cue/builtins.go
+++ b/cue/builtins.go
@@ -1080,7 +1080,96 @@
}()
}
},
+ }, {
+ Name: "Sort",
+ Params: []kind{listKind, topKind},
+ Result: listKind,
+ Func: func(c *callCtxt) {
+ list, cmp := c.list(0), c.value(1)
+ if c.do() {
+ c.ret, c.err = func() (interface{}, error) {
+ s := valueSorter{list, cmp, nil}
+
+ sort.Sort(&s)
+ return s.ret()
+ }()
+ }
+ },
+ }, {
+ Name: "SortStable",
+ Params: []kind{listKind, topKind},
+ Result: listKind,
+ Func: func(c *callCtxt) {
+ list, cmp := c.list(0), c.value(1)
+ if c.do() {
+ c.ret, c.err = func() (interface{}, error) {
+ s := valueSorter{list, cmp, nil}
+ sort.Stable(&s)
+ return s.ret()
+ }()
+ }
+ },
+ }, {
+ Name: "SortStrings",
+ Params: []kind{listKind},
+ Result: listKind,
+ Func: func(c *callCtxt) {
+ a := c.strList(0)
+ if c.do() {
+ c.ret = func() interface{} {
+ sort.Strings(a)
+ return a
+ }()
+ }
+ },
+ }, {
+ Name: "IsSorted",
+ Params: []kind{listKind, topKind},
+ Result: boolKind,
+ Func: func(c *callCtxt) {
+ list, cmp := c.list(0), c.value(1)
+ if c.do() {
+ c.ret = func() interface{} {
+ s := valueSorter{list, cmp, nil}
+ return sort.IsSorted(&s)
+ }()
+ }
+ },
+ }, {
+ Name: "IsSortedStrings",
+ Params: []kind{listKind},
+ Result: boolKind,
+ Func: func(c *callCtxt) {
+ a := c.strList(0)
+ if c.do() {
+ c.ret = func() interface{} {
+ return sort.StringsAreSorted(a)
+ }()
+ }
+ },
}},
+ cue: `{
+ Comparer :: {
+ T :: _
+ less: bool
+ x: T
+ y: T
+ }
+ Ascending :: {
+ T :: number | string
+ less: true && x < y
+ x: T
+ y: T
+ Comparer
+ }
+ Descending :: {
+ T :: number | string
+ less: x > y
+ x: T
+ y: T
+ Comparer
+ }
+}`,
},
"math": &builtinPkg{
native: []*builtin{{
diff --git a/cue/builtinutil.go b/cue/builtinutil.go
new file mode 100644
index 0000000..d3c471e
--- /dev/null
+++ b/cue/builtinutil.go
@@ -0,0 +1,57 @@
+// 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 cue
+
+// TODO: this code could be generated, but currently isn't.
+
+type valueSorter struct {
+ a []Value
+ cmp Value
+ err error
+}
+
+func (s *valueSorter) ret() ([]Value, error) {
+ if s.err != nil {
+ return nil, s.err
+ }
+ // The input slice is already a copy and that we can modify it safely.
+ return s.a, nil
+}
+
+func (s *valueSorter) Len() int { return len(s.a) }
+func (s *valueSorter) Swap(i, j int) { s.a[i], s.a[j] = s.a[j], s.a[i] }
+func (s *valueSorter) Less(i, j int) bool {
+ x := fill(s.cmp, s.a[i], "x")
+ x = fill(x, s.a[j], "y")
+ isLess, err := x.Lookup("less").Bool()
+ if err != nil && s.err == nil {
+ s.err = err
+ return true
+ }
+ return isLess
+}
+
+// fill creates a new value with the old value unified with the given value.
+// TODO: consider making this a method on Value.
+func fill(v Value, x interface{}, path ...string) Value {
+ ctx := v.ctx()
+ root := v.path.val()
+ for i := len(path) - 1; i >= 0; i-- {
+ x = map[string]interface{}{path[i]: x}
+ }
+ value := convert(ctx, root, true, x)
+ eval := binOp(ctx, baseValue{}, opUnify, root, value)
+ return newValueRoot(ctx, eval)
+}
diff --git a/cue/export_test.go b/cue/export_test.go
index 5dcf8d6..4771064 100644
--- a/cue/export_test.go
+++ b/cue/export_test.go
@@ -784,11 +784,11 @@
T :: {
[string]: int64
}
- X :: {
+ x: {
[string]: int64
x: int64
}
- x: {
+ X :: {
[string]: int64
x: int64
}
@@ -809,10 +809,10 @@
{
T :: {
}
+ x: x: int64
X :: {
x: int64
}
- x: x: int64
}`),
}, {
eval: true,
diff --git a/cue/go_test.go b/cue/go_test.go
index b311a97..621dfa8 100644
--- a/cue/go_test.go
+++ b/cue/go_test.go
@@ -170,13 +170,13 @@
T time.Time
G func()
}{},
- `(*null | <0>{A: ((int & >=-32768 & int & <=32767) & (>=0 & <100)), ` +
+ `(*null | <0>{T: _, ` +
+ `A: ((int & >=-32768 & int & <=32767) & (>=0 & <100)), ` +
`C: string, ` +
`D: bool, ` +
`F: float, ` +
`b: null, ` +
- `L?: (*null | bytes), ` +
- `T: _})`,
+ `L?: (*null | bytes)})`,
}, {
struct {
A int `cue:"<"` // invalid
@@ -191,7 +191,7 @@
T string `cue:""` // allowed
h int
}{},
- "<0>{D?: number, T: string, P?: (*null | number), I?: _}",
+ "<0>{T: string, D?: number, P?: (*null | number), I?: _}",
}, {
struct {
A int8 `cue:"C-B"`
diff --git a/cue/resolve_test.go b/cue/resolve_test.go
index 6637245..c4871fc 100644
--- a/cue/resolve_test.go
+++ b/cue/resolve_test.go
@@ -518,9 +518,9 @@
x: x + 1
`,
out: `<0>{` +
+ `x: _|_((100 & 101):conflicting values 100 and 101), ` +
`a: _|_((210 & 200):conflicting values 210 and 200), ` +
- `b: _|_((210 & 200):conflicting values 210 and 200), ` +
- `x: _|_((100 & 101):conflicting values 100 and 101)}`,
+ `b: _|_((210 & 200):conflicting values 210 and 200)}`,
// TODO: find a way to mark error in data.
}}
rewriteHelper(t, testCases, evalPartial)
@@ -557,7 +557,7 @@
x: a & b
y: b & c
`,
- out: `<0>{a: "a", b: "a", c: (*"a" | *"b"), x: "a", y: (*"a" | *"b")}`,
+ out: `<0>{x: "a", y: (*"a" | *"b"), a: "a", b: "a", c: (*"a" | *"b")}`,
}}
rewriteHelper(t, testCases, evalFull)
}
@@ -577,7 +577,7 @@
out: "<0>{a: 3, b: <1>{c: <2>{d: 3}}, c: <3>{c: 2}, d: <4>{d: 2}}",
}, {
in: "`foo-bar`: 3\n x: `foo-bar`,",
- out: `<0>{foo-bar: 3, x: 3}`,
+ out: `<0>{x: 3, foo-bar: 3}`,
}, {
desc: "resolution of quoted identifiers",
in: `
@@ -1541,7 +1541,7 @@
w: v & { b: 100 }
wp: v & { b: 100 }
`,
- out: `<0>{a: <1>{b: int}, c: <2>{b: 100, d: (<3>.a.b + 3)}, x: <4>{b: int, c: (<5>.b + 5)}, y: <6>{b: 100, c: 105}, v: <7>{b: int, c: (<3>.v.b + 5)}, w: <8>{b: 100, c: (<3>.v.b + 5)}, wp: <9>{b: 100, c: (<3>.v.b + 5)}}`,
+ out: `<0>{x: <1>{b: int, c: (<2>.b + 5)}, y: <3>{b: 100, c: 105}, a: <4>{b: int}, c: <5>{b: 100, d: (<6>.a.b + 3)}, v: <7>{b: int, c: (<6>.v.b + 5)}, w: <8>{b: 100, c: (<6>.v.b + 5)}, wp: <9>{b: 100, c: (<6>.v.b + 5)}}`,
// TODO(#152): should be
// out: `<0>{a: <1>{b: int}, c: <2>{b: 100, d: (<3>.a.b + 3)}, x: <4>{b: int, c: (<5>.b + 5)}, y: <6>{b: 100, c: 105}, v: <7>{b: int, c: (<8>.b + 5)}, w: <9>{b: 100, c: 105}, wp: <10>{b: 100, c: 105}}`,
}, {
@@ -1639,7 +1639,7 @@
d: 4, // Combines constraints S.A, S.B, T.A, and T.B
}
}`,
- out: "<0>{S: <1>{A: <2>{a: 1}, B: <3>{a: 1, b: 2}}, T: <4>{A: <5>{a: 1, c: 3}, B: <6>{a: 1, b: 2, c: 3, d: 4}}}",
+ out: "<0>{T: <1>{A: <2>{a: 1, c: 3}, B: <3>{a: 1, b: 2, c: 3, d: 4}}, S: <4>{A: <5>{a: 1}, B: <6>{a: 1, b: 2}}}",
}, {
desc: "field templates",
in: `
@@ -1659,7 +1659,7 @@
bar: _
}
`,
- out: `<0>{a: <1>{[]: <2>(name: string)->int, k: 1}, b: <3>{[]: <4>(X: string)->(<5>{x: 0, y: (*1 | int)} & <6>{}), v: <7>{x: 0, y: (*1 | int)}, w: <8>{x: 0, y: (*1 | int)}}, c: <9>{[]: <10>(Name: string)-><11>{name: <10>.Name, y: 1}, foo: <12>{name: "foo", y: 1}, bar: <13>{name: "bar", y: 1}}}`,
+ out: `<0>{a: <1>{[]: <2>(name: string)->int, k: 1}, b: <3>{[]: <4>(X: string)->(<5>{x: 0, y: (*1 | int)} & <6>{}), v: <7>{x: 0, y: (*1 | int)}, w: <8>{x: 0, y: (*1 | int)}}, c: <9>{[]: <10>(Name: string)-><11>{y: 1, name: <10>.Name}, foo: <12>{y: 1, name: "foo"}, bar: <13>{y: 1, name: "bar"}}}`,
}, {
desc: "range unification",
in: `
@@ -2060,7 +2060,7 @@
bar: _
}
`,
- out: `<0>{a: <1>{[]: <2>(name: string)->int, k: 1}, b: <3>{[]: <4>(X: string)->(<5>{x: 0, y: (*1 | int)} & <6>{}), v: <7>{x: 0, y: 1}, w: <8>{x: 0, y: 0}}, c: <9>{[]: <10>(Name: string)-><11>{name: <10>.Name, y: 1}, foo: <12>{name: "foo", y: 1}, bar: <13>{name: "bar", y: 1}}}`,
+ out: `<0>{a: <1>{[]: <2>(name: string)->int, k: 1}, b: <3>{[]: <4>(X: string)->(<5>{x: 0, y: (*1 | int)} & <6>{}), v: <7>{x: 0, y: 1}, w: <8>{x: 0, y: 0}}, c: <9>{[]: <10>(Name: string)-><11>{y: 1, name: <10>.Name}, foo: <12>{y: 1, name: "foo"}, bar: <13>{y: 1, name: "bar"}}}`,
}, {
desc: "field comprehension",
in: `
@@ -2773,7 +2773,7 @@
s: t & {
ok :: false
}`,
- out: `<0>{t: <1>{ok :: true, x: int}, s: <2>{ok :: false}}`,
+ out: `<0>{t: <1>{x: int, ok :: true}, s: <2>{ok :: false}}`,
}, {
desc: "cross-dependent comprehension",
// TODO(eval): fix: c should ultimately be allowed the struct. Current
@@ -2793,7 +2793,7 @@
`,
// c should not be allowed, as it would break commutativiy.
// See comments above.
- out: `<0>{a :: <1>C{b: bool if <2>.b yield <3>C{c: 4}}, x: _|_(4:field "c" not allowed in closed struct), y: _|_(4:field "c" not allowed in closed struct)}`,
+ out: `<0>{x: _|_(4:field "c" not allowed in closed struct), y: _|_(4:field "c" not allowed in closed struct), a :: <1>C{b: bool if <2>.b yield <3>C{c: 4}}}`,
}, {
desc: "optional expanded before lookup",
in: `
diff --git a/pkg/list/sort.cue b/pkg/list/sort.cue
new file mode 100644
index 0000000..4ea3e78
--- /dev/null
+++ b/pkg/list/sort.cue
@@ -0,0 +1,48 @@
+// 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 list
+
+// A Comparer specifies whether one value is strictly less than another value.
+Comparer :: {
+ T :: _
+ x: T
+ y: T
+ less: bool // true if x < y
+}
+
+// Ascending defines a Comparer to sort comparable values in increasing order.
+//
+// Example:
+// list.Sort(a, list.Ascending)
+Ascending :: {
+ Comparer
+ T :: number | string
+ x: T
+ y: T
+ // TODO: the following will be fixed when removing old-school templating.
+ less: true && (x < y)
+}
+
+// Descending defines a Comparer to sort comparable values in decreasing order.
+//
+// Example:
+// list.Sort(a, list.Descending)
+Descending :: {
+ Comparer
+ T :: number | string
+ x: T
+ y: T
+ less: (x > y)
+}
diff --git a/pkg/list/sort.go b/pkg/list/sort.go
new file mode 100644
index 0000000..991bbc4
--- /dev/null
+++ b/pkg/list/sort.go
@@ -0,0 +1,96 @@
+// Copyright 2018 The 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.
+
+// Copyright 2018 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package list
+
+import (
+ "sort"
+
+ "cuelang.org/go/cue"
+)
+
+// valueSorter defines a sort.Interface; implemented in cue/builtinutil.go.
+type valueSorter struct {
+ a []cue.Value
+ cmp cue.Value
+ err error
+}
+
+func (s *valueSorter) ret() ([]cue.Value, error) {
+ panic("implemented in cue/builtinutil.go")
+}
+
+func (s *valueSorter) Len() int { panic("implemented in cue/builtinutil.go") }
+func (s *valueSorter) Swap(i, j int) { panic("implemented in cue/builtinutil.go") }
+func (s *valueSorter) Less(i, j int) bool { panic("implemented in cue/builtinutil.go") }
+
+// Sort sorts data. It does O(n*log(n)) comparisons.
+// The sort is not guaranteed to be stable.
+//
+// cmp is a struct of the form {T :: _, x: T, y: T, less: bool}, where
+// less should reflect x < y.
+//
+// Example:
+//
+// Sort([2, 3, 1], list.Ascending)
+//
+// Sort{{a: 2}, {a: 3}, {a: 1}, {a: {}, b: {}, less: x.a < y.a}}
+//
+func Sort(list []cue.Value, cmp cue.Value) (sorted []cue.Value, err error) {
+ s := valueSorter{list, cmp, nil}
+ // The input slice is already a copy and that we can modify it safely.
+ sort.Sort(&s)
+ return s.ret()
+}
+
+// SortStable sorts data while keeping the original order of equal elements.
+// It does O(n*log(n)) comparisons.
+//
+// cmp is a struct of the form {T :: _, a: T, b: T, less: bool}, where
+// less should reflect a < b.
+//
+// Example:
+//
+// Sort([2, 3, 1], list.Ascending)
+//
+// Sort{{a: 2}, {a: 3}, {a: 1}, {a: {}, b: {}, less: x.a < y.a}}
+//
+func SortStable(list []cue.Value, cmp cue.Value) (sorted []cue.Value, err error) {
+ s := valueSorter{list, cmp, nil}
+ sort.Stable(&s)
+ return s.ret()
+}
+
+// Strings sorts a list of strings in increasing order.
+func SortStrings(a []string) []string {
+ sort.Strings(a)
+ return a
+}
+
+// IsSorted tests whether a list is sorted.
+//
+// See Sort for an example comparator.
+func IsSorted(list []cue.Value, cmp cue.Value) bool {
+ s := valueSorter{list, cmp, nil}
+ return sort.IsSorted(&s)
+}
+
+// IsSortedStrings tests whether a list is a sorted lists of strings.
+func IsSortedStrings(a []string) bool {
+ return sort.StringsAreSorted(a)
+}
