1// Copyright 2020 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package order
6
7import (
8	"math/rand"
9	"sort"
10	"testing"
11
12	"github.com/google/go-cmp/cmp"
13	"google.golang.org/protobuf/reflect/protoreflect"
14	pref "google.golang.org/protobuf/reflect/protoreflect"
15)
16
17type fieldDesc struct {
18	index      int
19	name       protoreflect.FullName
20	number     protoreflect.FieldNumber
21	extension  bool
22	oneofIndex int // non-zero means within oneof; negative means synthetic
23	pref.FieldDescriptor
24}
25
26func (d fieldDesc) Index() int               { return d.index }
27func (d fieldDesc) Name() pref.Name          { return d.name.Name() }
28func (d fieldDesc) FullName() pref.FullName  { return d.name }
29func (d fieldDesc) Number() pref.FieldNumber { return d.number }
30func (d fieldDesc) IsExtension() bool        { return d.extension }
31func (d fieldDesc) ContainingOneof() pref.OneofDescriptor {
32	switch {
33	case d.oneofIndex < 0:
34		return oneofDesc{index: -d.oneofIndex, synthetic: true}
35	case d.oneofIndex > 0:
36		return oneofDesc{index: +d.oneofIndex, synthetic: false}
37	default:
38		return nil
39	}
40}
41
42type oneofDesc struct {
43	index     int
44	synthetic bool
45	pref.OneofDescriptor
46}
47
48func (d oneofDesc) Index() int        { return d.index }
49func (d oneofDesc) IsSynthetic() bool { return d.synthetic }
50
51func TestFieldOrder(t *testing.T) {
52	tests := []struct {
53		label  string
54		order  FieldOrder
55		fields []fieldDesc
56	}{{
57		label: "LegacyFieldOrder",
58		order: LegacyFieldOrder,
59		fields: []fieldDesc{
60			// Extension fields sorted first by field number.
61			{number: 2, extension: true},
62			{number: 4, extension: true},
63			{number: 100, extension: true},
64			{number: 120, extension: true},
65
66			// Non-extension fields that are not within a oneof
67			// sorted next by field number.
68			{number: 1},
69			{number: 5, oneofIndex: -9}, // synthetic oneof
70			{number: 10},
71			{number: 11, oneofIndex: -10}, // synthetic oneof
72			{number: 12},
73
74			// Non-synthetic oneofs sorted last by index.
75			{number: 13, oneofIndex: 4},
76			{number: 3, oneofIndex: 5},
77			{number: 9, oneofIndex: 5},
78			{number: 7, oneofIndex: 8},
79		},
80	}, {
81		label: "NumberFieldOrder",
82		order: NumberFieldOrder,
83		fields: []fieldDesc{
84			{number: 1, index: 5, name: "c"},
85			{number: 2, index: 2, name: "b"},
86			{number: 3, index: 3, name: "d"},
87			{number: 5, index: 1, name: "a"},
88			{number: 7, index: 7, name: "e"},
89		},
90	}, {
91		label: "IndexNameFieldOrder",
92		order: IndexNameFieldOrder,
93		fields: []fieldDesc{
94			// Non-extension fields sorted first by index.
95			{index: 0, number: 5, name: "c"},
96			{index: 2, number: 2, name: "a"},
97			{index: 4, number: 4, name: "b"},
98			{index: 7, number: 6, name: "d"},
99
100			// Extension fields sorted last by full name.
101			{index: 3, number: 1, name: "d.a", extension: true},
102			{index: 5, number: 3, name: "e", extension: true},
103			{index: 1, number: 7, name: "g", extension: true},
104		},
105	}}
106
107	for _, tt := range tests {
108		t.Run(tt.label, func(t *testing.T) {
109			want := tt.fields
110			got := append([]fieldDesc(nil), want...)
111			for i, j := range rand.Perm(len(got)) {
112				got[i], got[j] = got[j], got[i]
113			}
114			sort.Slice(got, func(i, j int) bool {
115				return tt.order(got[i], got[j])
116			})
117			if diff := cmp.Diff(want, got,
118				cmp.Comparer(func(x, y fieldDesc) bool { return x == y }),
119			); diff != "" {
120				t.Errorf("order mismatch (-want +got):\n%s", diff)
121			}
122		})
123	}
124}
125
126func TestKeyOrder(t *testing.T) {
127	tests := []struct {
128		label string
129		order KeyOrder
130		keys  []interface{}
131	}{{
132		label: "GenericKeyOrder",
133		order: GenericKeyOrder,
134		keys:  []interface{}{false, true},
135	}, {
136		label: "GenericKeyOrder",
137		order: GenericKeyOrder,
138		keys:  []interface{}{int32(-100), int32(-99), int32(-10), int32(-9), int32(-1), int32(0), int32(+1), int32(+9), int32(+10), int32(+99), int32(+100)},
139	}, {
140		label: "GenericKeyOrder",
141		order: GenericKeyOrder,
142		keys:  []interface{}{int64(-100), int64(-99), int64(-10), int64(-9), int64(-1), int64(0), int64(+1), int64(+9), int64(+10), int64(+99), int64(+100)},
143	}, {
144		label: "GenericKeyOrder",
145		order: GenericKeyOrder,
146		keys:  []interface{}{uint32(0), uint32(1), uint32(9), uint32(10), uint32(99), uint32(100)},
147	}, {
148		label: "GenericKeyOrder",
149		order: GenericKeyOrder,
150		keys:  []interface{}{uint64(0), uint64(1), uint64(9), uint64(10), uint64(99), uint64(100)},
151	}, {
152		label: "GenericKeyOrder",
153		order: GenericKeyOrder,
154		keys:  []interface{}{"", "a", "aa", "ab", "ba", "bb", "\u0080", "\u0080\u0081", "\u0082\u0080"},
155	}}
156
157	for _, tt := range tests {
158		t.Run(tt.label, func(t *testing.T) {
159			var got, want []protoreflect.MapKey
160			for _, v := range tt.keys {
161				want = append(want, pref.ValueOf(v).MapKey())
162			}
163			got = append(got, want...)
164			for i, j := range rand.Perm(len(got)) {
165				got[i], got[j] = got[j], got[i]
166			}
167			sort.Slice(got, func(i, j int) bool {
168				return tt.order(got[i], got[j])
169			})
170			if diff := cmp.Diff(want, got, cmp.Transformer("", protoreflect.MapKey.Interface)); diff != "" {
171				t.Errorf("order mismatch (-want +got):\n%s", diff)
172			}
173		})
174	}
175}
176