this repo has no description
handle.invalid
1// Copyright 2018 The CUE Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15// Copyright 2018 The Go Authors. All rights reserved.
16// Use of this source code is governed by a BSD-style
17// license that can be found in the LICENSE file.
18
19package list
20
21import (
22 "slices"
23 "sort"
24
25 "cuelang.org/go/cue"
26 "cuelang.org/go/internal/core/adt"
27 "cuelang.org/go/internal/core/eval"
28)
29
30// valueSorter defines a sort.Interface; implemented in cue/builtinutil.go.
31type valueSorter struct {
32 ctx *adt.OpContext
33 a []cue.Value
34 err error
35
36 cmp *adt.Vertex
37 less *adt.Vertex
38 x *adt.Vertex
39 y *adt.Vertex
40}
41
42func (s *valueSorter) ret() ([]cue.Value, error) {
43 if s.err != nil {
44 return nil, s.err
45 }
46 // The input slice is already a copy and that we can modify it safely.
47 return s.a, nil
48}
49
50func (s *valueSorter) Len() int { return len(s.a) }
51func (s *valueSorter) Swap(i, j int) { s.a[i], s.a[j] = s.a[j], s.a[i] }
52func (s *valueSorter) Less(i, j int) bool {
53 if s.err != nil {
54 return false
55 }
56
57 return s.lessNew(i, j)
58}
59
60func (s *valueSorter) lessNew(i, j int) bool {
61 ctx := s.ctx
62
63 n := &adt.Vertex{
64 Label: s.cmp.Label,
65 Parent: s.cmp.Parent,
66 Conjuncts: s.cmp.Conjuncts,
67 }
68
69 n.Init(ctx)
70
71 less := getArc(ctx, n, "less")
72 xa := getArc(ctx, n, "x")
73 ya := getArc(ctx, n, "y")
74
75 x := s.a[i].Core()
76 y := s.a[j].Core()
77
78 xa.InsertConjunctsFrom(x.V)
79 ya.InsertConjunctsFrom(y.V)
80
81 // TODO(perf): if we can determine that the comparator values for
82 // x and y are idempotent (no arcs and a basevalue being top or
83 // a struct or list marker), then we do not need to reevaluate the input.
84 // In that case, we can use the below code instead of the above two loops
85 // setting the conjuncts. This may improve performance significantly.
86 //
87 // s.x.BaseValue = x.V.BaseValue
88 // s.x.Arcs = x.V.Arcs
89 // s.y.BaseValue = y.V.BaseValue
90 // s.y.Arcs = y.V.Arcs
91
92 less.Finalize(s.ctx)
93
94 isLess := s.ctx.BoolValue(less)
95 if b := less.Err(s.ctx); b != nil && s.err == nil {
96 s.err = b.Err
97 return true
98 }
99
100 return isLess
101}
102
103var less = cue.ParsePath("less")
104
105func makeValueSorter(list []cue.Value, cmp cue.Value) (s valueSorter) {
106 if v := cmp.LookupPath(less); !v.Exists() {
107 return valueSorter{err: v.Err()}
108 }
109
110 v := cmp.Core()
111 ctx := eval.NewContext(v.R, v.V)
112
113 n := &adt.Vertex{
114 Label: v.V.Label,
115 Parent: v.V.Parent,
116 Conjuncts: v.V.Conjuncts,
117 }
118 n.CompleteArcs(ctx)
119
120 s = valueSorter{
121 a: list,
122 ctx: ctx,
123 cmp: n,
124 less: getArc(ctx, n, "less"),
125 x: getArc(ctx, n, "x"),
126 y: getArc(ctx, n, "y"),
127 }
128
129 // TODO(perf): see comment in the Less method. If we can determine
130 // the conjuncts for x and y are idempotent, we can pre finalize here and
131 // ignore the values in the Less method.
132 // s.x.UpdateStatus(adt.Finalized)
133 // s.y.UpdateStatus(adt.Finalized)
134
135 return s
136}
137
138// Sort sorts data while keeping the original order of equal elements.
139// It does O(n*log(n)) comparisons.
140//
141// cmp is a struct of the form {T: _, x: T, y: T, less: bool}, where
142// less should reflect x < y.
143//
144// Example:
145//
146// Sort([2, 3, 1], list.Ascending)
147//
148// Sort([{a: 2}, {a: 3}, {a: 1}], {x: {}, y: {}, less: x.a < y.a})
149func Sort(list []cue.Value, cmp cue.Value) (sorted []cue.Value, err error) {
150 s := makeValueSorter(list, cmp)
151
152 // The input slice is already a copy and that we can modify it safely.
153 sort.Stable(&s)
154 return s.ret()
155}
156
157func getArc(ctx *adt.OpContext, v *adt.Vertex, s string) *adt.Vertex {
158 f := ctx.StringLabel(s)
159 arc, _ := v.GetArc(ctx, f, 0)
160 return arc
161}
162
163// Deprecated: use [Sort], which is always stable
164func SortStable(list []cue.Value, cmp cue.Value) (sorted []cue.Value, err error) {
165 s := makeValueSorter(list, cmp)
166 sort.Stable(&s)
167 return s.ret()
168}
169
170// SortStrings sorts a list of strings in increasing order.
171func SortStrings(a []string) []string {
172 slices.Sort(a)
173 return a
174}
175
176// IsSorted tests whether a list is sorted.
177//
178// See Sort for an example comparator.
179func IsSorted(list []cue.Value, cmp cue.Value) bool {
180 s := makeValueSorter(list, cmp)
181 return sort.IsSorted(&s)
182}
183
184// IsSortedStrings tests whether a list is a sorted lists of strings.
185func IsSortedStrings(a []string) bool {
186 return slices.IsSorted(a)
187}