Source file src/google.golang.org/protobuf/internal/filedesc/desc_list.go

Documentation: google.golang.org/protobuf/internal/filedesc

     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  

View as plain text