desc_list.go raw
1 // Copyright 2019 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
5 package filedesc
6
7 import (
8 "fmt"
9 "math"
10 "sort"
11 "sync"
12
13 "google.golang.org/protobuf/internal/genid"
14
15 "google.golang.org/protobuf/encoding/protowire"
16 "google.golang.org/protobuf/internal/descfmt"
17 "google.golang.org/protobuf/internal/errors"
18 "google.golang.org/protobuf/internal/pragma"
19 "google.golang.org/protobuf/reflect/protoreflect"
20 )
21
22 type FileImports []protoreflect.FileImport
23
24 func (p *FileImports) Len() int { return len(*p) }
25 func (p *FileImports) Get(i int) protoreflect.FileImport { return (*p)[i] }
26 func (p *FileImports) Format(s fmt.State, r rune) { descfmt.FormatList(s, r, p) }
27 func (p *FileImports) ProtoInternal(pragma.DoNotImplement) {}
28
29 type Names struct {
30 List []protoreflect.Name
31 once sync.Once
32 has map[protoreflect.Name]int // protected by once
33 }
34
35 func (p *Names) Len() int { return len(p.List) }
36 func (p *Names) Get(i int) protoreflect.Name { return p.List[i] }
37 func (p *Names) Has(s protoreflect.Name) bool { return p.lazyInit().has[s] > 0 }
38 func (p *Names) Format(s fmt.State, r rune) { descfmt.FormatList(s, r, p) }
39 func (p *Names) ProtoInternal(pragma.DoNotImplement) {}
40 func (p *Names) lazyInit() *Names {
41 p.once.Do(func() {
42 if len(p.List) > 0 {
43 p.has = make(map[protoreflect.Name]int, len(p.List))
44 for _, s := range p.List {
45 p.has[s] = p.has[s] + 1
46 }
47 }
48 })
49 return p
50 }
51
52 // CheckValid reports any errors with the set of names with an error message
53 // that completes the sentence: "ranges is invalid because it has ..."
54 func (p *Names) CheckValid() error {
55 for s, n := range p.lazyInit().has {
56 switch {
57 case n > 1:
58 return errors.New("duplicate name: %q", s)
59 case false && !s.IsValid():
60 // NOTE: The C++ implementation does not validate the identifier.
61 // See https://github.com/protocolbuffers/protobuf/issues/6335.
62 return errors.New("invalid name: %q", s)
63 }
64 }
65 return nil
66 }
67
68 type EnumRanges struct {
69 List [][2]protoreflect.EnumNumber // start inclusive; end inclusive
70 once sync.Once
71 sorted [][2]protoreflect.EnumNumber // protected by once
72 }
73
74 func (p *EnumRanges) Len() int { return len(p.List) }
75 func (p *EnumRanges) Get(i int) [2]protoreflect.EnumNumber { return p.List[i] }
76 func (p *EnumRanges) Has(n protoreflect.EnumNumber) bool {
77 for ls := p.lazyInit().sorted; len(ls) > 0; {
78 i := len(ls) / 2
79 switch r := enumRange(ls[i]); {
80 case n < r.Start():
81 ls = ls[:i] // search lower
82 case n > r.End():
83 ls = ls[i+1:] // search upper
84 default:
85 return true
86 }
87 }
88 return false
89 }
90 func (p *EnumRanges) Format(s fmt.State, r rune) { descfmt.FormatList(s, r, p) }
91 func (p *EnumRanges) ProtoInternal(pragma.DoNotImplement) {}
92 func (p *EnumRanges) lazyInit() *EnumRanges {
93 p.once.Do(func() {
94 p.sorted = append(p.sorted, p.List...)
95 sort.Slice(p.sorted, func(i, j int) bool {
96 return p.sorted[i][0] < p.sorted[j][0]
97 })
98 })
99 return p
100 }
101
102 // CheckValid reports any errors with the set of names with an error message
103 // that completes the sentence: "ranges is invalid because it has ..."
104 func (p *EnumRanges) CheckValid() error {
105 var rp enumRange
106 for i, r := range p.lazyInit().sorted {
107 r := enumRange(r)
108 switch {
109 case !(r.Start() <= r.End()):
110 return errors.New("invalid range: %v", r)
111 case !(rp.End() < r.Start()) && i > 0:
112 return errors.New("overlapping ranges: %v with %v", rp, r)
113 }
114 rp = r
115 }
116 return nil
117 }
118
119 type enumRange [2]protoreflect.EnumNumber
120
121 func (r enumRange) Start() protoreflect.EnumNumber { return r[0] } // inclusive
122 func (r enumRange) End() protoreflect.EnumNumber { return r[1] } // inclusive
123 func (r enumRange) String() string {
124 if r.Start() == r.End() {
125 return fmt.Sprintf("%d", r.Start())
126 }
127 return fmt.Sprintf("%d to %d", r.Start(), r.End())
128 }
129
130 type FieldRanges struct {
131 List [][2]protoreflect.FieldNumber // start inclusive; end exclusive
132 once sync.Once
133 sorted [][2]protoreflect.FieldNumber // protected by once
134 }
135
136 func (p *FieldRanges) Len() int { return len(p.List) }
137 func (p *FieldRanges) Get(i int) [2]protoreflect.FieldNumber { return p.List[i] }
138 func (p *FieldRanges) Has(n protoreflect.FieldNumber) bool {
139 for ls := p.lazyInit().sorted; len(ls) > 0; {
140 i := len(ls) / 2
141 switch r := fieldRange(ls[i]); {
142 case n < r.Start():
143 ls = ls[:i] // search lower
144 case n > r.End():
145 ls = ls[i+1:] // search upper
146 default:
147 return true
148 }
149 }
150 return false
151 }
152 func (p *FieldRanges) Format(s fmt.State, r rune) { descfmt.FormatList(s, r, p) }
153 func (p *FieldRanges) ProtoInternal(pragma.DoNotImplement) {}
154 func (p *FieldRanges) lazyInit() *FieldRanges {
155 p.once.Do(func() {
156 p.sorted = append(p.sorted, p.List...)
157 sort.Slice(p.sorted, func(i, j int) bool {
158 return p.sorted[i][0] < p.sorted[j][0]
159 })
160 })
161 return p
162 }
163
164 // CheckValid reports any errors with the set of ranges with an error message
165 // that completes the sentence: "ranges is invalid because it has ..."
166 func (p *FieldRanges) CheckValid(isMessageSet bool) error {
167 var rp fieldRange
168 for i, r := range p.lazyInit().sorted {
169 r := fieldRange(r)
170 switch {
171 case !isValidFieldNumber(r.Start(), isMessageSet):
172 return errors.New("invalid field number: %d", r.Start())
173 case !isValidFieldNumber(r.End(), isMessageSet):
174 return errors.New("invalid field number: %d", r.End())
175 case !(r.Start() <= r.End()):
176 return errors.New("invalid range: %v", r)
177 case !(rp.End() < r.Start()) && i > 0:
178 return errors.New("overlapping ranges: %v with %v", rp, r)
179 }
180 rp = r
181 }
182 return nil
183 }
184
185 // isValidFieldNumber reports whether the field number is valid.
186 // Unlike the FieldNumber.IsValid method, it allows ranges that cover the
187 // reserved number range.
188 func isValidFieldNumber(n protoreflect.FieldNumber, isMessageSet bool) bool {
189 return protowire.MinValidNumber <= n && (n <= protowire.MaxValidNumber || isMessageSet)
190 }
191
192 // CheckOverlap reports an error if p and q overlap.
193 func (p *FieldRanges) CheckOverlap(q *FieldRanges) error {
194 rps := p.lazyInit().sorted
195 rqs := q.lazyInit().sorted
196 for pi, qi := 0, 0; pi < len(rps) && qi < len(rqs); {
197 rp := fieldRange(rps[pi])
198 rq := fieldRange(rqs[qi])
199 if !(rp.End() < rq.Start() || rq.End() < rp.Start()) {
200 return errors.New("overlapping ranges: %v with %v", rp, rq)
201 }
202 if rp.Start() < rq.Start() {
203 pi++
204 } else {
205 qi++
206 }
207 }
208 return nil
209 }
210
211 type fieldRange [2]protoreflect.FieldNumber
212
213 func (r fieldRange) Start() protoreflect.FieldNumber { return r[0] } // inclusive
214 func (r fieldRange) End() protoreflect.FieldNumber { return r[1] - 1 } // inclusive
215 func (r fieldRange) String() string {
216 if r.Start() == r.End() {
217 return fmt.Sprintf("%d", r.Start())
218 }
219 return fmt.Sprintf("%d to %d", r.Start(), r.End())
220 }
221
222 type FieldNumbers struct {
223 List []protoreflect.FieldNumber
224 once sync.Once
225 has map[protoreflect.FieldNumber]struct{} // protected by once
226 }
227
228 func (p *FieldNumbers) Len() int { return len(p.List) }
229 func (p *FieldNumbers) Get(i int) protoreflect.FieldNumber { return p.List[i] }
230 func (p *FieldNumbers) Has(n protoreflect.FieldNumber) bool {
231 p.once.Do(func() {
232 if len(p.List) > 0 {
233 p.has = make(map[protoreflect.FieldNumber]struct{}, len(p.List))
234 for _, n := range p.List {
235 p.has[n] = struct{}{}
236 }
237 }
238 })
239 _, ok := p.has[n]
240 return ok
241 }
242 func (p *FieldNumbers) Format(s fmt.State, r rune) { descfmt.FormatList(s, r, p) }
243 func (p *FieldNumbers) ProtoInternal(pragma.DoNotImplement) {}
244
245 type OneofFields struct {
246 List []protoreflect.FieldDescriptor
247 once sync.Once
248 byName map[protoreflect.Name]protoreflect.FieldDescriptor // protected by once
249 byJSON map[string]protoreflect.FieldDescriptor // protected by once
250 byText map[string]protoreflect.FieldDescriptor // protected by once
251 byNum map[protoreflect.FieldNumber]protoreflect.FieldDescriptor // protected by once
252 }
253
254 func (p *OneofFields) Len() int { return len(p.List) }
255 func (p *OneofFields) Get(i int) protoreflect.FieldDescriptor { return p.List[i] }
256 func (p *OneofFields) ByName(s protoreflect.Name) protoreflect.FieldDescriptor {
257 return p.lazyInit().byName[s]
258 }
259 func (p *OneofFields) ByJSONName(s string) protoreflect.FieldDescriptor {
260 return p.lazyInit().byJSON[s]
261 }
262 func (p *OneofFields) ByTextName(s string) protoreflect.FieldDescriptor {
263 return p.lazyInit().byText[s]
264 }
265 func (p *OneofFields) ByNumber(n protoreflect.FieldNumber) protoreflect.FieldDescriptor {
266 return p.lazyInit().byNum[n]
267 }
268 func (p *OneofFields) Format(s fmt.State, r rune) { descfmt.FormatList(s, r, p) }
269 func (p *OneofFields) ProtoInternal(pragma.DoNotImplement) {}
270
271 func (p *OneofFields) lazyInit() *OneofFields {
272 p.once.Do(func() {
273 if len(p.List) > 0 {
274 p.byName = make(map[protoreflect.Name]protoreflect.FieldDescriptor, len(p.List))
275 p.byJSON = make(map[string]protoreflect.FieldDescriptor, len(p.List))
276 p.byText = make(map[string]protoreflect.FieldDescriptor, len(p.List))
277 p.byNum = make(map[protoreflect.FieldNumber]protoreflect.FieldDescriptor, len(p.List))
278 for _, f := range p.List {
279 // Field names and numbers are guaranteed to be unique.
280 p.byName[f.Name()] = f
281 p.byJSON[f.JSONName()] = f
282 p.byText[f.TextName()] = f
283 p.byNum[f.Number()] = f
284 }
285 }
286 })
287 return p
288 }
289
290 type SourceLocations struct {
291 // List is a list of SourceLocations.
292 // The SourceLocation.Next field does not need to be populated
293 // as it will be lazily populated upon first need.
294 List []protoreflect.SourceLocation
295
296 // File is the parent file descriptor that these locations are relative to.
297 // If non-nil, ByDescriptor verifies that the provided descriptor
298 // is a child of this file descriptor.
299 File protoreflect.FileDescriptor
300
301 once sync.Once
302 byPath map[pathKey]int
303 }
304
305 func (p *SourceLocations) Len() int { return len(p.List) }
306 func (p *SourceLocations) Get(i int) protoreflect.SourceLocation { return p.lazyInit().List[i] }
307 func (p *SourceLocations) byKey(k pathKey) protoreflect.SourceLocation {
308 if i, ok := p.lazyInit().byPath[k]; ok {
309 return p.List[i]
310 }
311 return protoreflect.SourceLocation{}
312 }
313 func (p *SourceLocations) ByPath(path protoreflect.SourcePath) protoreflect.SourceLocation {
314 return p.byKey(newPathKey(path))
315 }
316 func (p *SourceLocations) ByDescriptor(desc protoreflect.Descriptor) protoreflect.SourceLocation {
317 if p.File != nil && desc != nil && p.File != desc.ParentFile() {
318 return protoreflect.SourceLocation{} // mismatching parent files
319 }
320 var pathArr [16]int32
321 path := pathArr[:0]
322 for {
323 switch desc.(type) {
324 case protoreflect.FileDescriptor:
325 // Reverse the path since it was constructed in reverse.
326 for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
327 path[i], path[j] = path[j], path[i]
328 }
329 return p.byKey(newPathKey(path))
330 case protoreflect.MessageDescriptor:
331 path = append(path, int32(desc.Index()))
332 desc = desc.Parent()
333 switch desc.(type) {
334 case protoreflect.FileDescriptor:
335 path = append(path, int32(genid.FileDescriptorProto_MessageType_field_number))
336 case protoreflect.MessageDescriptor:
337 path = append(path, int32(genid.DescriptorProto_NestedType_field_number))
338 default:
339 return protoreflect.SourceLocation{}
340 }
341 case protoreflect.FieldDescriptor:
342 isExtension := desc.(protoreflect.FieldDescriptor).IsExtension()
343 path = append(path, int32(desc.Index()))
344 desc = desc.Parent()
345 if isExtension {
346 switch desc.(type) {
347 case protoreflect.FileDescriptor:
348 path = append(path, int32(genid.FileDescriptorProto_Extension_field_number))
349 case protoreflect.MessageDescriptor:
350 path = append(path, int32(genid.DescriptorProto_Extension_field_number))
351 default:
352 return protoreflect.SourceLocation{}
353 }
354 } else {
355 switch desc.(type) {
356 case protoreflect.MessageDescriptor:
357 path = append(path, int32(genid.DescriptorProto_Field_field_number))
358 default:
359 return protoreflect.SourceLocation{}
360 }
361 }
362 case protoreflect.OneofDescriptor:
363 path = append(path, int32(desc.Index()))
364 desc = desc.Parent()
365 switch desc.(type) {
366 case protoreflect.MessageDescriptor:
367 path = append(path, int32(genid.DescriptorProto_OneofDecl_field_number))
368 default:
369 return protoreflect.SourceLocation{}
370 }
371 case protoreflect.EnumDescriptor:
372 path = append(path, int32(desc.Index()))
373 desc = desc.Parent()
374 switch desc.(type) {
375 case protoreflect.FileDescriptor:
376 path = append(path, int32(genid.FileDescriptorProto_EnumType_field_number))
377 case protoreflect.MessageDescriptor:
378 path = append(path, int32(genid.DescriptorProto_EnumType_field_number))
379 default:
380 return protoreflect.SourceLocation{}
381 }
382 case protoreflect.EnumValueDescriptor:
383 path = append(path, int32(desc.Index()))
384 desc = desc.Parent()
385 switch desc.(type) {
386 case protoreflect.EnumDescriptor:
387 path = append(path, int32(genid.EnumDescriptorProto_Value_field_number))
388 default:
389 return protoreflect.SourceLocation{}
390 }
391 case protoreflect.ServiceDescriptor:
392 path = append(path, int32(desc.Index()))
393 desc = desc.Parent()
394 switch desc.(type) {
395 case protoreflect.FileDescriptor:
396 path = append(path, int32(genid.FileDescriptorProto_Service_field_number))
397 default:
398 return protoreflect.SourceLocation{}
399 }
400 case protoreflect.MethodDescriptor:
401 path = append(path, int32(desc.Index()))
402 desc = desc.Parent()
403 switch desc.(type) {
404 case protoreflect.ServiceDescriptor:
405 path = append(path, int32(genid.ServiceDescriptorProto_Method_field_number))
406 default:
407 return protoreflect.SourceLocation{}
408 }
409 default:
410 return protoreflect.SourceLocation{}
411 }
412 }
413 }
414 func (p *SourceLocations) lazyInit() *SourceLocations {
415 p.once.Do(func() {
416 if len(p.List) > 0 {
417 // Collect all the indexes for a given path.
418 pathIdxs := make(map[pathKey][]int, len(p.List))
419 for i, l := range p.List {
420 k := newPathKey(l.Path)
421 pathIdxs[k] = append(pathIdxs[k], i)
422 }
423
424 // Update the next index for all locations.
425 p.byPath = make(map[pathKey]int, len(p.List))
426 for k, idxs := range pathIdxs {
427 for i := 0; i < len(idxs)-1; i++ {
428 p.List[idxs[i]].Next = idxs[i+1]
429 }
430 p.List[idxs[len(idxs)-1]].Next = 0
431 p.byPath[k] = idxs[0] // record the first location for this path
432 }
433 }
434 })
435 return p
436 }
437 func (p *SourceLocations) ProtoInternal(pragma.DoNotImplement) {}
438
439 // pathKey is a comparable representation of protoreflect.SourcePath.
440 type pathKey struct {
441 arr [16]uint8 // first n-1 path segments; last element is the length
442 str string // used if the path does not fit in arr
443 }
444
445 func newPathKey(p protoreflect.SourcePath) (k pathKey) {
446 if len(p) < len(k.arr) {
447 for i, ps := range p {
448 if ps < 0 || math.MaxUint8 <= ps {
449 return pathKey{str: p.String()}
450 }
451 k.arr[i] = uint8(ps)
452 }
453 k.arr[len(k.arr)-1] = uint8(len(p))
454 return k
455 }
456 return pathKey{str: p.String()}
457 }
458