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 	pref "google.golang.org/protobuf/reflect/protoreflect"

    21 )

    22 

    23 type FileImports []pref.FileImport

    24 

    25 func (p *FileImports) Len() int                            { return len(*p) }

    26 func (p *FileImports) Get(i int) pref.FileImport           { return (*p)[i] }

    27 func (p *FileImports) Format(s fmt.State, r rune)          { descfmt.FormatList(s, r, p) }

    28 func (p *FileImports) ProtoInternal(pragma.DoNotImplement) {}

    29 

    30 type Names struct {

    31 	List []pref.Name

    32 	once sync.Once

    33 	has  map[pref.Name]int // protected by once

    34 }

    35 

    36 func (p *Names) Len() int                            { return len(p.List) }

    37 func (p *Names) Get(i int) pref.Name                 { return p.List[i] }

    38 func (p *Names) Has(s pref.Name) bool                { return p.lazyInit().has[s] > 0 }

    39 func (p *Names) Format(s fmt.State, r rune)          { descfmt.FormatList(s, r, p) }

    40 func (p *Names) ProtoInternal(pragma.DoNotImplement) {}

    41 func (p *Names) lazyInit() *Names {

    42 	p.once.Do(func() {

    43 		if len(p.List) > 0 {

    44 			p.has = make(map[pref.Name]int, len(p.List))

    45 			for _, s := range p.List {

    46 				p.has[s] = p.has[s] + 1

    47 			}

    48 		}

    49 	})

    50 	return p

    51 }

    52 

    53 // CheckValid reports any errors with the set of names with an error message

    54 // that completes the sentence: "ranges is invalid because it has ..."

    55 func (p *Names) CheckValid() error {

    56 	for s, n := range p.lazyInit().has {

    57 		switch {

    58 		case n > 1:

    59 			return errors.New("duplicate name: %q", s)

    60 		case false && !s.IsValid():

    61 			// NOTE: The C++ implementation does not validate the identifier.

    62 			// See https://github.com/protocolbuffers/protobuf/issues/6335.

    63 			return errors.New("invalid name: %q", s)

    64 		}

    65 	}

    66 	return nil

    67 }

    68 

    69 type EnumRanges struct {

    70 	List   [][2]pref.EnumNumber // start inclusive; end inclusive

    71 	once   sync.Once

    72 	sorted [][2]pref.EnumNumber // protected by once

    73 }

    74 

    75 func (p *EnumRanges) Len() int                     { return len(p.List) }

    76 func (p *EnumRanges) Get(i int) [2]pref.EnumNumber { return p.List[i] }

    77 func (p *EnumRanges) Has(n pref.EnumNumber) bool {

    78 	for ls := p.lazyInit().sorted; len(ls) > 0; {

    79 		i := len(ls) / 2

    80 		switch r := enumRange(ls[i]); {

    81 		case n < r.Start():

    82 			ls = ls[:i] // search lower

    83 		case n > r.End():

    84 			ls = ls[i+1:] // search upper

    85 		default:

    86 			return true

    87 		}

    88 	}

    89 	return false

    90 }

    91 func (p *EnumRanges) Format(s fmt.State, r rune)          { descfmt.FormatList(s, r, p) }

    92 func (p *EnumRanges) ProtoInternal(pragma.DoNotImplement) {}

    93 func (p *EnumRanges) lazyInit() *EnumRanges {

    94 	p.once.Do(func() {

    95 		p.sorted = append(p.sorted, p.List...)

    96 		sort.Slice(p.sorted, func(i, j int) bool {

    97 			return p.sorted[i][0] < p.sorted[j][0]

    98 		})

    99 	})

   100 	return p

   101 }

   102 

   103 // CheckValid reports any errors with the set of names with an error message

   104 // that completes the sentence: "ranges is invalid because it has ..."

   105 func (p *EnumRanges) CheckValid() error {

   106 	var rp enumRange

   107 	for i, r := range p.lazyInit().sorted {

   108 		r := enumRange(r)

   109 		switch {

   110 		case !(r.Start() <= r.End()):

   111 			return errors.New("invalid range: %v", r)

   112 		case !(rp.End() < r.Start()) && i > 0:

   113 			return errors.New("overlapping ranges: %v with %v", rp, r)

   114 		}

   115 		rp = r

   116 	}

   117 	return nil

   118 }

   119 

   120 type enumRange [2]protoreflect.EnumNumber

   121 

   122 func (r enumRange) Start() protoreflect.EnumNumber { return r[0] } // inclusive

   123 func (r enumRange) End() protoreflect.EnumNumber   { return r[1] } // inclusive

   124 func (r enumRange) String() string {

   125 	if r.Start() == r.End() {

   126 		return fmt.Sprintf("%d", r.Start())

   127 	}

   128 	return fmt.Sprintf("%d to %d", r.Start(), r.End())

   129 }

   130 

   131 type FieldRanges struct {

   132 	List   [][2]pref.FieldNumber // start inclusive; end exclusive

   133 	once   sync.Once

   134 	sorted [][2]pref.FieldNumber // protected by once

   135 }

   136 

   137 func (p *FieldRanges) Len() int                      { return len(p.List) }

   138 func (p *FieldRanges) Get(i int) [2]pref.FieldNumber { return p.List[i] }

   139 func (p *FieldRanges) Has(n pref.FieldNumber) bool {

   140 	for ls := p.lazyInit().sorted; len(ls) > 0; {

   141 		i := len(ls) / 2

   142 		switch r := fieldRange(ls[i]); {

   143 		case n < r.Start():

   144 			ls = ls[:i] // search lower

   145 		case n > r.End():

   146 			ls = ls[i+1:] // search upper

   147 		default:

   148 			return true

   149 		}

   150 	}

   151 	return false

   152 }

   153 func (p *FieldRanges) Format(s fmt.State, r rune)          { descfmt.FormatList(s, r, p) }

   154 func (p *FieldRanges) ProtoInternal(pragma.DoNotImplement) {}

   155 func (p *FieldRanges) lazyInit() *FieldRanges {

   156 	p.once.Do(func() {

   157 		p.sorted = append(p.sorted, p.List...)

   158 		sort.Slice(p.sorted, func(i, j int) bool {

   159 			return p.sorted[i][0] < p.sorted[j][0]

   160 		})

   161 	})

   162 	return p

   163 }

   164 

   165 // CheckValid reports any errors with the set of ranges with an error message

   166 // that completes the sentence: "ranges is invalid because it has ..."

   167 func (p *FieldRanges) CheckValid(isMessageSet bool) error {

   168 	var rp fieldRange

   169 	for i, r := range p.lazyInit().sorted {

   170 		r := fieldRange(r)

   171 		switch {

   172 		case !isValidFieldNumber(r.Start(), isMessageSet):

   173 			return errors.New("invalid field number: %d", r.Start())

   174 		case !isValidFieldNumber(r.End(), isMessageSet):

   175 			return errors.New("invalid field number: %d", r.End())

   176 		case !(r.Start() <= r.End()):

   177 			return errors.New("invalid range: %v", r)

   178 		case !(rp.End() < r.Start()) && i > 0:

   179 			return errors.New("overlapping ranges: %v with %v", rp, r)

   180 		}

   181 		rp = r

   182 	}

   183 	return nil

   184 }

   185 

   186 // isValidFieldNumber reports whether the field number is valid.

   187 // Unlike the FieldNumber.IsValid method, it allows ranges that cover the

   188 // reserved number range.

   189 func isValidFieldNumber(n protoreflect.FieldNumber, isMessageSet bool) bool {

   190 	return protowire.MinValidNumber <= n && (n <= protowire.MaxValidNumber || isMessageSet)

   191 }

   192 

   193 // CheckOverlap reports an error if p and q overlap.

   194 func (p *FieldRanges) CheckOverlap(q *FieldRanges) error {

   195 	rps := p.lazyInit().sorted

   196 	rqs := q.lazyInit().sorted

   197 	for pi, qi := 0, 0; pi < len(rps) && qi < len(rqs); {

   198 		rp := fieldRange(rps[pi])

   199 		rq := fieldRange(rqs[qi])

   200 		if !(rp.End() < rq.Start() || rq.End() < rp.Start()) {

   201 			return errors.New("overlapping ranges: %v with %v", rp, rq)

   202 		}

   203 		if rp.Start() < rq.Start() {

   204 			pi++

   205 		} else {

   206 			qi++

   207 		}

   208 	}

   209 	return nil

   210 }

   211 

   212 type fieldRange [2]protoreflect.FieldNumber

   213 

   214 func (r fieldRange) Start() protoreflect.FieldNumber { return r[0] }     // inclusive

   215 func (r fieldRange) End() protoreflect.FieldNumber   { return r[1] - 1 } // inclusive

   216 func (r fieldRange) String() string {

   217 	if r.Start() == r.End() {

   218 		return fmt.Sprintf("%d", r.Start())

   219 	}

   220 	return fmt.Sprintf("%d to %d", r.Start(), r.End())

   221 }

   222 

   223 type FieldNumbers struct {

   224 	List []pref.FieldNumber

   225 	once sync.Once

   226 	has  map[pref.FieldNumber]struct{} // protected by once

   227 }

   228 

   229 func (p *FieldNumbers) Len() int                   { return len(p.List) }

   230 func (p *FieldNumbers) Get(i int) pref.FieldNumber { return p.List[i] }

   231 func (p *FieldNumbers) Has(n pref.FieldNumber) bool {

   232 	p.once.Do(func() {

   233 		if len(p.List) > 0 {

   234 			p.has = make(map[pref.FieldNumber]struct{}, len(p.List))

   235 			for _, n := range p.List {

   236 				p.has[n] = struct{}{}

   237 			}

   238 		}

   239 	})

   240 	_, ok := p.has[n]

   241 	return ok

   242 }

   243 func (p *FieldNumbers) Format(s fmt.State, r rune)          { descfmt.FormatList(s, r, p) }

   244 func (p *FieldNumbers) ProtoInternal(pragma.DoNotImplement) {}

   245 

   246 type OneofFields struct {

   247 	List   []pref.FieldDescriptor

   248 	once   sync.Once

   249 	byName map[pref.Name]pref.FieldDescriptor        // protected by once

   250 	byJSON map[string]pref.FieldDescriptor           // protected by once

   251 	byText map[string]pref.FieldDescriptor           // protected by once

   252 	byNum  map[pref.FieldNumber]pref.FieldDescriptor // protected by once

   253 }

   254 

   255 func (p *OneofFields) Len() int                                         { return len(p.List) }

   256 func (p *OneofFields) Get(i int) pref.FieldDescriptor                   { return p.List[i] }

   257 func (p *OneofFields) ByName(s pref.Name) pref.FieldDescriptor          { return p.lazyInit().byName[s] }

   258 func (p *OneofFields) ByJSONName(s string) pref.FieldDescriptor         { return p.lazyInit().byJSON[s] }

   259 func (p *OneofFields) ByTextName(s string) pref.FieldDescriptor         { return p.lazyInit().byText[s] }

   260 func (p *OneofFields) ByNumber(n pref.FieldNumber) pref.FieldDescriptor { return p.lazyInit().byNum[n] }

   261 func (p *OneofFields) Format(s fmt.State, r rune)                       { descfmt.FormatList(s, r, p) }

   262 func (p *OneofFields) ProtoInternal(pragma.DoNotImplement)              {}

   263 

   264 func (p *OneofFields) lazyInit() *OneofFields {

   265 	p.once.Do(func() {

   266 		if len(p.List) > 0 {

   267 			p.byName = make(map[pref.Name]pref.FieldDescriptor, len(p.List))

   268 			p.byJSON = make(map[string]pref.FieldDescriptor, len(p.List))

   269 			p.byText = make(map[string]pref.FieldDescriptor, len(p.List))

   270 			p.byNum = make(map[pref.FieldNumber]pref.FieldDescriptor, len(p.List))

   271 			for _, f := range p.List {

   272 				// Field names and numbers are guaranteed to be unique.

   273 				p.byName[f.Name()] = f

   274 				p.byJSON[f.JSONName()] = f

   275 				p.byText[f.TextName()] = f

   276 				p.byNum[f.Number()] = f

   277 			}

   278 		}

   279 	})

   280 	return p

   281 }

   282 

   283 type SourceLocations struct {

   284 	// List is a list of SourceLocations.

   285 	// The SourceLocation.Next field does not need to be populated

   286 	// as it will be lazily populated upon first need.

   287 	List []pref.SourceLocation

   288 

   289 	// File is the parent file descriptor that these locations are relative to.

   290 	// If non-nil, ByDescriptor verifies that the provided descriptor

   291 	// is a child of this file descriptor.

   292 	File pref.FileDescriptor

   293 

   294 	once   sync.Once

   295 	byPath map[pathKey]int

   296 }

   297 

   298 func (p *SourceLocations) Len() int                      { return len(p.List) }

   299 func (p *SourceLocations) Get(i int) pref.SourceLocation { return p.lazyInit().List[i] }

   300 func (p *SourceLocations) byKey(k pathKey) pref.SourceLocation {

   301 	if i, ok := p.lazyInit().byPath[k]; ok {

   302 		return p.List[i]

   303 	}

   304 	return pref.SourceLocation{}

   305 }

   306 func (p *SourceLocations) ByPath(path pref.SourcePath) pref.SourceLocation {

   307 	return p.byKey(newPathKey(path))

   308 }

   309 func (p *SourceLocations) ByDescriptor(desc pref.Descriptor) pref.SourceLocation {

   310 	if p.File != nil && desc != nil && p.File != desc.ParentFile() {

   311 		return pref.SourceLocation{} // mismatching parent files

   312 	}

   313 	var pathArr [16]int32

   314 	path := pathArr[:0]

   315 	for {

   316 		switch desc.(type) {

   317 		case pref.FileDescriptor:

   318 			// Reverse the path since it was constructed in reverse.

   319 			for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {

   320 				path[i], path[j] = path[j], path[i]

   321 			}

   322 			return p.byKey(newPathKey(path))

   323 		case pref.MessageDescriptor:

   324 			path = append(path, int32(desc.Index()))

   325 			desc = desc.Parent()

   326 			switch desc.(type) {

   327 			case pref.FileDescriptor:

   328 				path = append(path, int32(genid.FileDescriptorProto_MessageType_field_number))

   329 			case pref.MessageDescriptor:

   330 				path = append(path, int32(genid.DescriptorProto_NestedType_field_number))

   331 			default:

   332 				return pref.SourceLocation{}

   333 			}

   334 		case pref.FieldDescriptor:

   335 			isExtension := desc.(pref.FieldDescriptor).IsExtension()

   336 			path = append(path, int32(desc.Index()))

   337 			desc = desc.Parent()

   338 			if isExtension {

   339 				switch desc.(type) {

   340 				case pref.FileDescriptor:

   341 					path = append(path, int32(genid.FileDescriptorProto_Extension_field_number))

   342 				case pref.MessageDescriptor:

   343 					path = append(path, int32(genid.DescriptorProto_Extension_field_number))

   344 				default:

   345 					return pref.SourceLocation{}

   346 				}

   347 			} else {

   348 				switch desc.(type) {

   349 				case pref.MessageDescriptor:

   350 					path = append(path, int32(genid.DescriptorProto_Field_field_number))

   351 				default:

   352 					return pref.SourceLocation{}

   353 				}

   354 			}

   355 		case pref.OneofDescriptor:

   356 			path = append(path, int32(desc.Index()))

   357 			desc = desc.Parent()

   358 			switch desc.(type) {

   359 			case pref.MessageDescriptor:

   360 				path = append(path, int32(genid.DescriptorProto_OneofDecl_field_number))

   361 			default:

   362 				return pref.SourceLocation{}

   363 			}

   364 		case pref.EnumDescriptor:

   365 			path = append(path, int32(desc.Index()))

   366 			desc = desc.Parent()

   367 			switch desc.(type) {

   368 			case pref.FileDescriptor:

   369 				path = append(path, int32(genid.FileDescriptorProto_EnumType_field_number))

   370 			case pref.MessageDescriptor:

   371 				path = append(path, int32(genid.DescriptorProto_EnumType_field_number))

   372 			default:

   373 				return pref.SourceLocation{}

   374 			}

   375 		case pref.EnumValueDescriptor:

   376 			path = append(path, int32(desc.Index()))

   377 			desc = desc.Parent()

   378 			switch desc.(type) {

   379 			case pref.EnumDescriptor:

   380 				path = append(path, int32(genid.EnumDescriptorProto_Value_field_number))

   381 			default:

   382 				return pref.SourceLocation{}

   383 			}

   384 		case pref.ServiceDescriptor:

   385 			path = append(path, int32(desc.Index()))

   386 			desc = desc.Parent()

   387 			switch desc.(type) {

   388 			case pref.FileDescriptor:

   389 				path = append(path, int32(genid.FileDescriptorProto_Service_field_number))

   390 			default:

   391 				return pref.SourceLocation{}

   392 			}

   393 		case pref.MethodDescriptor:

   394 			path = append(path, int32(desc.Index()))

   395 			desc = desc.Parent()

   396 			switch desc.(type) {

   397 			case pref.ServiceDescriptor:

   398 				path = append(path, int32(genid.ServiceDescriptorProto_Method_field_number))

   399 			default:

   400 				return pref.SourceLocation{}

   401 			}

   402 		default:

   403 			return pref.SourceLocation{}

   404 		}

   405 	}

   406 }

   407 func (p *SourceLocations) lazyInit() *SourceLocations {

   408 	p.once.Do(func() {

   409 		if len(p.List) > 0 {

   410 			// Collect all the indexes for a given path.

   411 			pathIdxs := make(map[pathKey][]int, len(p.List))

   412 			for i, l := range p.List {

   413 				k := newPathKey(l.Path)

   414 				pathIdxs[k] = append(pathIdxs[k], i)

   415 			}

   416 

   417 			// Update the next index for all locations.

   418 			p.byPath = make(map[pathKey]int, len(p.List))

   419 			for k, idxs := range pathIdxs {

   420 				for i := 0; i < len(idxs)-1; i++ {

   421 					p.List[idxs[i]].Next = idxs[i+1]

   422 				}

   423 				p.List[idxs[len(idxs)-1]].Next = 0

   424 				p.byPath[k] = idxs[0] // record the first location for this path

   425 			}

   426 		}

   427 	})

   428 	return p

   429 }

   430 func (p *SourceLocations) ProtoInternal(pragma.DoNotImplement) {}

   431 

   432 // pathKey is a comparable representation of protoreflect.SourcePath.

   433 type pathKey struct {

   434 	arr [16]uint8 // first n-1 path segments; last element is the length

   435 	str string    // used if the path does not fit in arr

   436 }

   437 

   438 func newPathKey(p pref.SourcePath) (k pathKey) {

   439 	if len(p) < len(k.arr) {

   440 		for i, ps := range p {

   441 			if ps < 0 || math.MaxUint8 <= ps {

   442 				return pathKey{str: p.String()}

   443 			}

   444 			k.arr[i] = uint8(ps)

   445 		}

   446 		k.arr[len(k.arr)-1] = uint8(len(p))

   447 		return k

   448 	}

   449 	return pathKey{str: p.String()}

   450 }