func (t *typeTrie) rewriteDescriptor(name string) (proto.Message, error) {
	if len(t.children) == 0 && t.typ != nil {
		if mdp, ok := t.typ.(*descriptor.DescriptorProto); ok {
			if len(mdp.NestedType) == 0 && len(mdp.EnumType) == 0 {
				return mdp, nil
			}
			mdp = proto.Clone(mdp).(*descriptor.DescriptorProto)
			mdp.NestedType = nil
			mdp.EnumType = nil
			return mdp, nil
		}
		return t.typ, nil
	}
	var mdp *descriptor.DescriptorProto
	if t.typ == nil {
		mdp = createIntermediateMessageDescriptor(name)
	} else {
		mdp = t.typ.(*descriptor.DescriptorProto)
		mdp = proto.Clone(mdp).(*descriptor.DescriptorProto)
		mdp.NestedType = nil
		mdp.EnumType = nil
	}
	var keys []string
	for k := range t.children {
		keys = append(keys, k)
	}
	for _, n := range keys {
		ch := t.children[n]
		typ, err := ch.rewriteDescriptor(n)
		if err != nil {
			return nil, err
		}
		switch typ := typ.(type) {
		case (*descriptor.DescriptorProto):
			mdp.NestedType = append(mdp.NestedType, typ)
		case (*descriptor.EnumDescriptorProto):
			mdp.EnumType = append(mdp.EnumType, typ)
		default:
			return nil, fmt.Errorf("invalid descriptor trie: message cannot have child of type %v", reflect.TypeOf(typ))
		}
	}
	return mdp, nil
}
rewriteDescriptor converts this level of the trie into a new descriptor
proto, requiring that the element stored in t.type is already a service,
message, or enum descriptor proto. If this trie has children then t.typ must
be a message descriptor proto. The returned descriptor proto is the same as
.type but with possibly new nested elements to represent this trie node's
children.
package msgregistry
import (
	"bytes"
	"fmt"
	"reflect"
	"sort"
	"strings"
	"sync"
	"sync/atomic"
	"github.com/golang/protobuf/proto"
	"github.com/golang/protobuf/protoc-gen-go/descriptor"
	"github.com/golang/protobuf/ptypes/wrappers"
	"golang.org/x/net/context"
	"google.golang.org/genproto/protobuf/api"
	"google.golang.org/genproto/protobuf/ptype"
	"github.com/jhump/protoreflect/desc"
	"github.com/jhump/protoreflect/dynamic"
)
var (
	enumOptionsDesc, enumValueOptionsDesc *desc.MessageDescriptor
	msgOptionsDesc, fieldOptionsDesc      *desc.MessageDescriptor
	svcOptionsDesc, methodOptionsDesc     *desc.MessageDescriptor
)
func init() {
	var err error
	enumOptionsDesc, err = desc.LoadMessageDescriptorForMessage((*descriptor.EnumOptions)(nil))
	if err != nil {
		panic("Failed to load descriptor for EnumOptions")
	}
	enumValueOptionsDesc, err = desc.LoadMessageDescriptorForMessage((*descriptor.EnumValueOptions)(nil))
	if err != nil {
		panic("Failed to load descriptor for EnumValueOptions")
	}
	msgOptionsDesc, err = desc.LoadMessageDescriptorForMessage((*descriptor.MessageOptions)(nil))
	if err != nil {
		panic("Failed to load descriptor for MessageOptions")
	}
	fieldOptionsDesc, err = desc.LoadMessageDescriptorForMessage((*descriptor.FieldOptions)(nil))
	if err != nil {
		panic("Failed to load descriptor for FieldOptions")
	}
	svcOptionsDesc, err = desc.LoadMessageDescriptorForMessage((*descriptor.ServiceOptions)(nil))
	if err != nil {
		panic("Failed to load descriptor for ServiceOptions")
	}
	methodOptionsDesc, err = desc.LoadMessageDescriptorForMessage((*descriptor.MethodOptions)(nil))
	if err != nil {
		panic("Failed to load descriptor for MethodOptions")
	}
}
func ensureScheme(url string) string {
	pos := strings.Index(url, "://")
	if pos < 0 {
		return "https://" + url
	}
	return url
}
type typeResolver struct {
	fetcher TypeFetcher
	mr      *MessageRegistry
	mu      sync.RWMutex
	cache   map[string]desc.Descriptor
}
func (r *typeResolver) resolveUrlToMessageDescriptor(url string) (*desc.MessageDescriptor, error) {
	url = ensureScheme(url)
	r.mu.RLock()
	cached := r.cache[url]
	r.mu.RUnlock()
	if cached != nil {
		if md, ok := cached.(*desc.MessageDescriptor); ok {
			return md, nil
		} else {
			return nil, fmt.Errorf("type for URL %v is the wrong type: wanted message, got enum", url)
		}
	}
	rc := newResolutionContext(r)
	if err := rc.addType(url, false); err != nil {
		return nil, err
	}
	var files map[string]*desc.FileDescriptor
	files, err := rc.toFileDescriptors(r.mr)
	if err != nil {
		return nil, err
	}
	r.mu.Lock()
	defer r.mu.Unlock()
	var md *desc.MessageDescriptor
	if len(rc.typeLocations) > 0 {
		if r.cache == nil {
			r.cache = map[string]desc.Descriptor{}
		}
	}
	for typeUrl, fileName := range rc.typeLocations {
		fd := files[fileName]
		sym := fd.FindSymbol(typeName(typeUrl))
		r.cache[typeUrl] = sym
		if url == typeUrl {
			md = sym.(*desc.MessageDescriptor)
		}
	}
	return md, nil
}
func (r *typeResolver) resolveUrlsToMessageDescriptors(urls ...string) (map[string]*desc.MessageDescriptor, error) {
	ret := map[string]*desc.MessageDescriptor{}
	var unresolved []string
	r.mu.RLock()
	for _, u := range urls {
		u = ensureScheme(u)
		cached := r.cache[u]
		if cached != nil {
			if md, ok := cached.(*desc.MessageDescriptor); ok {
				ret[u] = md
			} else {
				r.mu.RUnlock()
				return nil, fmt.Errorf("type for URL %v is the wrong type: wanted message, got enum", u)
			}
		} else {
			ret[u] = nil
			unresolved = append(unresolved, u)
		}
	}
	r.mu.RUnlock()
	if len(unresolved) == 0 {
		return ret, nil
	}
	rc := newResolutionContext(r)
	for _, u := range unresolved {
		if err := rc.addType(u, false); err != nil {
			return nil, err
		}
	}
	var files map[string]*desc.FileDescriptor
	files, err := rc.toFileDescriptors(r.mr)
	if err != nil {
		return nil, err
	}
	r.mu.Lock()
	defer r.mu.Unlock()
	if len(rc.typeLocations) > 0 {
		if r.cache == nil {
			r.cache = map[string]desc.Descriptor{}
		}
	}
	for typeUrl, fileName := range rc.typeLocations {
		fd := files[fileName]
		sym := fd.FindSymbol(typeName(typeUrl))
		r.cache[typeUrl] = sym
		if _, ok := ret[typeUrl]; ok {
			ret[typeUrl] = sym.(*desc.MessageDescriptor)
		}
	}
	return ret, nil
}
func (r *typeResolver) resolveUrlToEnumDescriptor(url string) (*desc.EnumDescriptor, error) {
	url = ensureScheme(url)
	r.mu.RLock()
	cached := r.cache[url]
	r.mu.RUnlock()
	if cached != nil {
		if ed, ok := cached.(*desc.EnumDescriptor); ok {
			return ed, nil
		} else {
			return nil, fmt.Errorf("type for URL %v is the wrong type: wanted enum, got message", url)
		}
	}
	rc := newResolutionContext(r)
	if err := rc.addType(url, true); err != nil {
		return nil, err
	}
	var files map[string]*desc.FileDescriptor
	files, err := rc.toFileDescriptors(r.mr)
	if err != nil {
		return nil, err
	}
	r.mu.Lock()
	defer r.mu.Unlock()
	var ed *desc.EnumDescriptor
	if len(rc.typeLocations) > 0 {
		if r.cache == nil {
			r.cache = map[string]desc.Descriptor{}
		}
	}
	for typeUrl, fileName := range rc.typeLocations {
		fd := files[fileName]
		sym := fd.FindSymbol(typeName(typeUrl))
		r.cache[typeUrl] = sym
		if url == typeUrl {
			ed = sym.(*desc.EnumDescriptor)
		}
	}
	return ed, nil
}
type tracker func(d desc.Descriptor) bool
func newNameTracker() tracker {
	names := map[string]struct{}{}
	return func(d desc.Descriptor) bool {
		name := d.GetFullyQualifiedName()
		if _, ok := names[name]; ok {
			return false
		}
		names[name] = struct{}{}
		return true
	}
}
func addDescriptors(ref string, files map[string]*fileEntry, d desc.Descriptor, msgs map[string]*desc.MessageDescriptor, onAdd tracker) {
	name := d.GetFullyQualifiedName()
	fileName := d.GetFile().GetName()
	if fileName != ref {
		dependee := files[ref]
		if dependee.deps == nil {
			dependee.deps = map[string]struct{}{}
		}
		dependee.deps[fileName] = struct{}{}
	}
	if !onAdd(d) {
		return
	}
	fe := files[fileName]
	if fe == nil {
		fe = &fileEntry{}
		fe.proto3 = d.GetFile().IsProto3()
		files[fileName] = fe
	}
	fe.types.addType(name, d.AsProto())
	if md, ok := d.(*desc.MessageDescriptor); ok {
		for _, fld := range md.GetFields() {
			if fld.GetType() == descriptor.FieldDescriptorProto_TYPE_MESSAGE || fld.GetType() == descriptor.FieldDescriptorProto_TYPE_GROUP {
				md := msgs[fld.GetMessageType().GetFullyQualifiedName()]
				if md == nil {
					md = fld.GetMessageType()
				}
				addDescriptors(fileName, files, md, msgs, onAdd)
			} else if fld.GetType() == descriptor.FieldDescriptorProto_TYPE_ENUM {
				addDescriptors(fileName, files, fld.GetEnumType(), msgs, onAdd)
			}
		}
	}
}
type resolutionContext struct {
	ctx    context.Context
	cancel func()
	res    *typeResolver
	mu sync.Mutex
	files map[string]*fileEntry
	typeLocations map[string]string
	unknownCount int
}
func newResolutionContext(res *typeResolver) *resolutionContext {
	ctx, cancel := context.WithCancel(context.Background())
	return &resolutionContext{
		ctx:           ctx,
		cancel:        cancel,
		res:           res,
		typeLocations: map[string]string{},
		files:         map[string]*fileEntry{},
	}
}
func (rc *resolutionContext) addType(url string, enum bool) error {
	if err := rc.ctx.Err(); err != nil {
		return err
	}
	m, err := rc.res.fetcher(url, enum)
	if err != nil {
		return err
	} else if m == nil {
		return fmt.Errorf("failed to locate type for %s", url)
	}
	if enum {
		rc.recordEnum(url, m.(*ptype.Enum))
		return nil
	}
	t := m.(*ptype.Type)
	fe, fileName := rc.recordType(url, t)
	if fe == nil {
		return nil
	}
	var wg sync.WaitGroup
	var failed int32
	for _, f := range t.Fields {
		if f.Kind == ptype.Field_TYPE_GROUP || f.Kind == ptype.Field_TYPE_MESSAGE || f.Kind == ptype.Field_TYPE_ENUM {
			typeUrl := ensureScheme(f.TypeUrl)
			kind := f.Kind
			wg.Add(1)
			go func() {
				defer wg.Done()
				var d desc.Descriptor
				var innerErr error
				if kind == ptype.Field_TYPE_ENUM {
					var ed *desc.EnumDescriptor
					ed, innerErr = rc.res.mr.getRegisteredEnumTypeByUrl(typeUrl)
					if ed != nil {
						d = ed
					}
				} else {
					var md *desc.MessageDescriptor
					md, innerErr = rc.res.mr.getRegisteredMessageTypeByUrl(typeUrl)
					if md != nil {
						d = md
					}
				}
				if innerErr == nil {
					if d != nil {
						rc.recordDescriptor(typeUrl, fileName, d)
					} else {
						innerErr = rc.addType(typeUrl, kind == ptype.Field_TYPE_ENUM)
					}
				}
				if innerErr != nil && (rc.ctx.Err() == nil || innerErr != context.Canceled) {
					if atomic.CompareAndSwapInt32(&failed, 0, 1) {
						err = innerErr
					}
					rc.cancel()
				}
			}()
		}
	}
	wg.Wait()
	if err != nil {
		return err
	}
	if err = rc.ctx.Err(); err != nil {
		return err
	}
	rc.mu.Lock()
	defer rc.mu.Unlock()
	for _, f := range t.Fields {
		if f.Kind == ptype.Field_TYPE_GROUP || f.Kind == ptype.Field_TYPE_MESSAGE || f.Kind == ptype.Field_TYPE_ENUM {
			typeUrl := ensureScheme(f.TypeUrl)
			if fe.deps == nil {
				fe.deps = map[string]struct{}{}
			}
			dep := rc.typeLocations[typeUrl]
			if dep != fileName {
				fe.deps[dep] = struct{}{}
			}
		}
	}
	return nil
}
func (rc *resolutionContext) recordEnum(url string, e *ptype.Enum) {
	rc.mu.Lock()
	defer rc.mu.Unlock()
	var fileName string
	if e.SourceContext != nil && e.SourceContext.FileName != "" {
		fileName = e.SourceContext.FileName
	} else {
		fileName = fmt.Sprintf("--unknown--%d.proto", rc.unknownCount)
		rc.unknownCount++
	}
	rc.typeLocations[url] = fileName
	fe := rc.files[fileName]
	if fe == nil {
		fe = &fileEntry{}
		rc.files[fileName] = fe
	}
	fe.types.addType(e.Name, e)
	if e.Syntax == ptype.Syntax_SYNTAX_PROTO3 {
		fe.proto3 = true
	}
}
func (rc *resolutionContext) recordType(url string, t *ptype.Type) (*fileEntry, string) {
	rc.mu.Lock()
	defer rc.mu.Unlock()
	if _, ok := rc.typeLocations[url]; ok {
		return nil, ""
	}
	var fileName string
	if t.SourceContext != nil && t.SourceContext.FileName != "" {
		fileName = t.SourceContext.FileName
	} else {
		fileName = fmt.Sprintf("--unknown--%d.proto", rc.unknownCount)
		rc.unknownCount++
	}
	rc.typeLocations[url] = fileName
	fe := rc.files[fileName]
	if fe == nil {
		fe = &fileEntry{}
		rc.files[fileName] = fe
	}
	fe.types.addType(t.Name, t)
	if t.Syntax == ptype.Syntax_SYNTAX_PROTO3 {
		fe.proto3 = true
	}
	return fe, fileName
}
func (rc *resolutionContext) recordDescriptor(url, ref string, d desc.Descriptor) {
	rc.mu.Lock()
	defer rc.mu.Unlock()
	addDescriptors(ref, rc.files, d, nil, func(dsc desc.Descriptor) bool {
		u := ensureScheme(rc.res.mr.ComputeUrl(dsc))
		if _, ok := rc.typeLocations[u]; ok {
			return false
		}
		fileName := dsc.GetFile().GetName()
		rc.typeLocations[u] = fileName
		if dsc == d {
			rc.typeLocations[url] = fileName
		}
		return true
	})
}
func (rc *resolutionContext) toFileDescriptors(mr *MessageRegistry) (map[string]*desc.FileDescriptor, error) {
	return toFileDescriptors(rc.files, func(tt *typeTrie, name string) (proto.Message, error) {
		mdp, edp := tt.ptypeToDescriptor(name, mr)
		if mdp != nil {
			return mdp, nil
		} else {
			return edp, nil
		}
	})
}
func toFileDescriptors(files map[string]*fileEntry, trieFn func(*typeTrie, string) (proto.Message, error)) (map[string]*desc.FileDescriptor, error) {
	fdps := map[string]*descriptor.FileDescriptorProto{}
	for name, file := range files {
		fdp, err := file.toFileDescriptor(name, trieFn)
		if err != nil {
			return nil, err
		}
		fdps[name] = fdp
	}
	fds := map[string]*desc.FileDescriptor{}
	for name, fdp := range fdps {
		if _, ok := fds[name]; ok {
			continue
		}
		var err error
		if fds[name], err = makeFileDesc(fdp, fds, fdps); err != nil {
			return nil, err
		}
	}
	return fds, nil
}
func makeFileDesc(fdp *descriptor.FileDescriptorProto, fds map[string]*desc.FileDescriptor, fdps map[string]*descriptor.FileDescriptorProto) (*desc.FileDescriptor, error) {
	deps := make([]*desc.FileDescriptor, len(fdp.Dependency))
	for i, dep := range fdp.Dependency {
		d := fds[dep]
		if d == nil {
			var err error
			depFd := fdps[dep]
			if depFd == nil {
				return nil, fmt.Errorf("missing dependency: %s", dep)
			}
			d, err = makeFileDesc(depFd, fds, fdps)
			if err != nil {
				return nil, err
			}
		}
		deps[i] = d
	}
	if fd, err := desc.CreateFileDescriptor(fdp, deps...); err != nil {
		return nil, err
	} else {
		fds[fdp.GetName()] = fd
		return fd, nil
	}
}
type fileEntry struct {
	types  typeTrie
	deps   map[string]struct{}
	proto3 bool
}
func (fe *fileEntry) toFileDescriptor(name string, trieFn func(*typeTrie, string) (proto.Message, error)) (*descriptor.FileDescriptorProto, error) {
	var pkg bytes.Buffer
	tt := &fe.types
	first := true
	last := ""
	for tt.typ == nil {
		if last != "" {
			if first {
				first = false
			} else {
				pkg.WriteByte('.')
			}
			pkg.WriteString(last)
		}
		if len(tt.children) != 1 {
			break
		}
		for last, tt = range tt.children {
		}
	}
	fd := createFileDescriptor(name, pkg.String(), fe.proto3, fe.deps)
	if tt.typ != nil {
		pm, err := trieFn(tt, last)
		if err != nil {
			return nil, err
		}
		if mdp, ok := pm.(*descriptor.DescriptorProto); ok {
			fd.MessageType = append(fd.MessageType, mdp)
		} else if edp, ok := pm.(*descriptor.EnumDescriptorProto); ok {
			fd.EnumType = append(fd.EnumType, edp)
		} else {
			sdp := pm.(*descriptor.ServiceDescriptorProto)
			fd.Service = append(fd.Service, sdp)
		}
	} else {
		for name, nested := range tt.children {
			pm, err := trieFn(nested, name)
			if err != nil {
				return nil, err
			}
			if mdp, ok := pm.(*descriptor.DescriptorProto); ok {
				fd.MessageType = append(fd.MessageType, mdp)
			} else if edp, ok := pm.(*descriptor.EnumDescriptorProto); ok {
				fd.EnumType = append(fd.EnumType, edp)
			} else {
				sdp := pm.(*descriptor.ServiceDescriptorProto)
				fd.Service = append(fd.Service, sdp)
			}
		}
	}
	return fd, nil
}
type typeTrie struct {
	children map[string]*typeTrie
	typ proto.Message
}
func (t *typeTrie) addType(key string, typ proto.Message) {
	if key == "" {
		t.typ = typ
		return
	}
	if t.children == nil {
		t.children = map[string]*typeTrie{}
	}
	curr, rest := split(key)
	child := t.children[curr]
	if child == nil {
		child = &typeTrie{}
		t.children[curr] = child
	}
	child.addType(rest, typ)
}
func (t *typeTrie) ptypeToDescriptor(name string, mr *MessageRegistry) (*descriptor.DescriptorProto, *descriptor.EnumDescriptorProto) {
	switch typ := t.typ.(type) {
	case *descriptor.EnumDescriptorProto:
		return nil, typ
	case *ptype.Enum:
		return nil, createEnumDescriptor(typ, mr)
	case *descriptor.DescriptorProto:
		return typ, nil
	default:
		var msg *descriptor.DescriptorProto
		if t.typ == nil {
			msg = createIntermediateMessageDescriptor(name)
		} else {
			msg = createMessageDescriptor(t.typ.(*ptype.Type), mr)
		}
		var keys []string
		for k := range t.children {
			keys = append(keys, k)
		}
		for _, name := range keys {
			nested := t.children[name]
			chMsg, chEnum := nested.ptypeToDescriptor(name, mr)
			if chMsg != nil {
				msg.NestedType = append(msg.NestedType, chMsg)
			}
			if chEnum != nil {
				msg.EnumType = append(msg.EnumType, chEnum)
			}
		}
		return msg, nil
	}
}