Source file src/cmd/vendor/github.com/ianlancetaylor/demangle/demangle.go

     1  // Copyright 2015 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 demangle defines functions that demangle GCC/LLVM
     6  // C++ and Rust symbol names.
     7  // This package recognizes names that were mangled according to the C++ ABI
     8  // defined at http://codesourcery.com/cxx-abi/ and the Rust ABI
     9  // defined at
    10  // https://rust-lang.github.io/rfcs/2603-rust-symbol-name-mangling-v0.html
    11  //
    12  // Most programs will want to call Filter or ToString.
    13  package demangle
    14  
    15  import (
    16  	"errors"
    17  	"fmt"
    18  	"strings"
    19  )
    20  
    21  // ErrNotMangledName is returned by CheckedDemangle if the string does
    22  // not appear to be a C++ symbol name.
    23  var ErrNotMangledName = errors.New("not a C++ or Rust mangled name")
    24  
    25  // Option is the type of demangler options.
    26  type Option int
    27  
    28  const (
    29  	// The NoParams option disables demangling of function parameters.
    30  	// It only omits the parameters of the function name being demangled,
    31  	// not the parameter types of other functions that may be mentioned.
    32  	// Using the option will speed up the demangler and cause it to
    33  	// use less memory.
    34  	NoParams Option = iota
    35  
    36  	// The NoTemplateParams option disables demangling of template parameters.
    37  	// This applies to both C++ and Rust.
    38  	NoTemplateParams
    39  
    40  	// The NoEnclosingParams option disables demangling of the function
    41  	// parameter types of the enclosing function when demangling a
    42  	// local name defined within a function.
    43  	NoEnclosingParams
    44  
    45  	// The NoClones option disables inclusion of clone suffixes.
    46  	// NoParams implies NoClones.
    47  	NoClones
    48  
    49  	// The NoRust option disables demangling of old-style Rust
    50  	// mangled names, which can be confused with C++ style mangled
    51  	// names. New style Rust mangled names are still recognized.
    52  	NoRust
    53  
    54  	// The Verbose option turns on more verbose demangling.
    55  	Verbose
    56  
    57  	// LLVMStyle tries to translate an AST to a string in the
    58  	// style of the LLVM demangler. This does not affect
    59  	// the parsing of the AST, only the conversion of the AST
    60  	// to a string.
    61  	LLVMStyle
    62  )
    63  
    64  // maxLengthShift is how we shift the MaxLength value.
    65  const maxLengthShift = 16
    66  
    67  // maxLengthMask is a mask for the maxLength value.
    68  const maxLengthMask = 0x1f << maxLengthShift
    69  
    70  // MaxLength returns an Option that limits the maximum length of a
    71  // demangled string. The maximum length is expressed as a power of 2,
    72  // so a value of 1 limits the returned string to 2 characters, and
    73  // a value of 16 limits the returned string to 65,536 characters.
    74  // The value must be between 1 and 30.
    75  func MaxLength(pow int) Option {
    76  	if pow <= 0 || pow > 30 {
    77  		panic("demangle: invalid MaxLength value")
    78  	}
    79  	return Option(pow << maxLengthShift)
    80  }
    81  
    82  // isMaxLength reports whether an Option holds a maximum length.
    83  func isMaxLength(opt Option) bool {
    84  	return opt&maxLengthMask != 0
    85  }
    86  
    87  // maxLength returns the maximum length stored in an Option.
    88  func maxLength(opt Option) int {
    89  	return 1 << ((opt & maxLengthMask) >> maxLengthShift)
    90  }
    91  
    92  // Filter demangles a C++ or Rust symbol name,
    93  // returning the human-readable C++ or Rust name.
    94  // If any error occurs during demangling, the input string is returned.
    95  func Filter(name string, options ...Option) string {
    96  	ret, err := ToString(name, options...)
    97  	if err != nil {
    98  		return name
    99  	}
   100  	return ret
   101  }
   102  
   103  // ToString demangles a C++ or Rust symbol name,
   104  // returning a human-readable C++ or Rust name or an error.
   105  // If the name does not appear to be a C++ or Rust symbol name at all,
   106  // the error will be ErrNotMangledName.
   107  func ToString(name string, options ...Option) (string, error) {
   108  	if strings.HasPrefix(name, "_R") {
   109  		return rustToString(name, options)
   110  	}
   111  
   112  	// Check for an old-style Rust mangled name.
   113  	// It starts with _ZN and ends with "17h" followed by 16 hex digits
   114  	// followed by "E" followed by an optional suffix starting with "."
   115  	// (which we ignore).
   116  	if strings.HasPrefix(name, "_ZN") {
   117  		rname := name
   118  		if pos := strings.LastIndex(rname, "E."); pos > 0 {
   119  			rname = rname[:pos+1]
   120  		}
   121  		if strings.HasSuffix(rname, "E") && len(rname) > 23 && rname[len(rname)-20:len(rname)-17] == "17h" {
   122  			noRust := false
   123  			for _, o := range options {
   124  				if o == NoRust {
   125  					noRust = true
   126  					break
   127  				}
   128  			}
   129  			if !noRust {
   130  				s, ok := oldRustToString(rname, options)
   131  				if ok {
   132  					return s, nil
   133  				}
   134  			}
   135  		}
   136  	}
   137  
   138  	a, err := ToAST(name, options...)
   139  	if err != nil {
   140  		return "", err
   141  	}
   142  	return ASTToString(a, options...), nil
   143  }
   144  
   145  // ToAST demangles a C++ symbol name into an abstract syntax tree
   146  // representing the symbol.
   147  // If the NoParams option is passed, and the name has a function type,
   148  // the parameter types are not demangled.
   149  // If the name does not appear to be a C++ symbol name at all, the
   150  // error will be ErrNotMangledName.
   151  // This function does not currently support Rust symbol names.
   152  func ToAST(name string, options ...Option) (AST, error) {
   153  	if strings.HasPrefix(name, "_Z") {
   154  		a, err := doDemangle(name[2:], options...)
   155  		return a, adjustErr(err, 2)
   156  	}
   157  
   158  	if strings.HasPrefix(name, "___Z") {
   159  		// clang extensions
   160  		block := strings.LastIndex(name, "_block_invoke")
   161  		if block == -1 {
   162  			return nil, ErrNotMangledName
   163  		}
   164  		a, err := doDemangle(name[4:block], options...)
   165  		if err != nil {
   166  			return a, adjustErr(err, 4)
   167  		}
   168  		name = strings.TrimPrefix(name[block:], "_block_invoke")
   169  		if len(name) > 0 && name[0] == '_' {
   170  			name = name[1:]
   171  		}
   172  		for len(name) > 0 && isDigit(name[0]) {
   173  			name = name[1:]
   174  		}
   175  		if len(name) > 0 && name[0] != '.' {
   176  			return nil, errors.New("unparsed characters at end of mangled name")
   177  		}
   178  		a = &Special{Prefix: "invocation function for block in ", Val: a}
   179  		return a, nil
   180  	}
   181  
   182  	const prefix = "_GLOBAL_"
   183  	if strings.HasPrefix(name, prefix) {
   184  		// The standard demangler ignores NoParams for global
   185  		// constructors.  We are compatible.
   186  		i := 0
   187  		for i < len(options) {
   188  			if options[i] == NoParams {
   189  				options = append(options[:i], options[i+1:]...)
   190  			} else {
   191  				i++
   192  			}
   193  		}
   194  		a, err := globalCDtorName(name[len(prefix):], options...)
   195  		return a, adjustErr(err, len(prefix))
   196  	}
   197  
   198  	return nil, ErrNotMangledName
   199  }
   200  
   201  // globalCDtorName demangles a global constructor/destructor symbol name.
   202  // The parameter is the string following the "_GLOBAL_" prefix.
   203  func globalCDtorName(name string, options ...Option) (AST, error) {
   204  	if len(name) < 4 {
   205  		return nil, ErrNotMangledName
   206  	}
   207  	switch name[0] {
   208  	case '.', '_', '$':
   209  	default:
   210  		return nil, ErrNotMangledName
   211  	}
   212  
   213  	var ctor bool
   214  	switch name[1] {
   215  	case 'I':
   216  		ctor = true
   217  	case 'D':
   218  		ctor = false
   219  	default:
   220  		return nil, ErrNotMangledName
   221  	}
   222  
   223  	if name[2] != '_' {
   224  		return nil, ErrNotMangledName
   225  	}
   226  
   227  	if !strings.HasPrefix(name[3:], "_Z") {
   228  		return &GlobalCDtor{Ctor: ctor, Key: &Name{Name: name}}, nil
   229  	} else {
   230  		a, err := doDemangle(name[5:], options...)
   231  		if err != nil {
   232  			return nil, adjustErr(err, 5)
   233  		}
   234  		return &GlobalCDtor{Ctor: ctor, Key: a}, nil
   235  	}
   236  }
   237  
   238  // The doDemangle function is the entry point into the demangler proper.
   239  func doDemangle(name string, options ...Option) (ret AST, err error) {
   240  	// When the demangling routines encounter an error, they panic
   241  	// with a value of type demangleErr.
   242  	defer func() {
   243  		if r := recover(); r != nil {
   244  			if de, ok := r.(demangleErr); ok {
   245  				ret = nil
   246  				err = de
   247  				return
   248  			}
   249  			panic(r)
   250  		}
   251  	}()
   252  
   253  	params := true
   254  	clones := true
   255  	verbose := false
   256  	for _, o := range options {
   257  		switch {
   258  		case o == NoParams:
   259  			params = false
   260  			clones = false
   261  		case o == NoClones:
   262  			clones = false
   263  		case o == Verbose:
   264  			verbose = true
   265  		case o == NoTemplateParams || o == NoEnclosingParams || o == LLVMStyle || isMaxLength(o):
   266  			// These are valid options but only affect
   267  			// printing of the AST.
   268  		case o == NoRust:
   269  			// Unimportant here.
   270  		default:
   271  			return nil, fmt.Errorf("unrecognized demangler option %v", o)
   272  		}
   273  	}
   274  
   275  	st := &state{str: name, verbose: verbose}
   276  	a := st.encoding(params, notForLocalName)
   277  
   278  	// Accept a clone suffix.
   279  	if clones {
   280  		for len(st.str) > 1 && st.str[0] == '.' && (isLower(st.str[1]) || st.str[1] == '_' || isDigit(st.str[1])) {
   281  			a = st.cloneSuffix(a)
   282  		}
   283  	}
   284  
   285  	if clones && len(st.str) > 0 {
   286  		st.fail("unparsed characters at end of mangled name")
   287  	}
   288  
   289  	return a, nil
   290  }
   291  
   292  // A state holds the current state of demangling a string.
   293  type state struct {
   294  	str       string        // remainder of string to demangle
   295  	verbose   bool          // whether to use verbose demangling
   296  	off       int           // offset of str within original string
   297  	subs      substitutions // substitutions
   298  	templates []*Template   // templates being processed
   299  
   300  	// The number of entries in templates when we started parsing
   301  	// a lambda, plus 1 so that 0 means not parsing a lambda.
   302  	lambdaTemplateLevel int
   303  
   304  	// Counts of template parameters without template arguments,
   305  	// for lambdas.
   306  	typeTemplateParamCount     int
   307  	nonTypeTemplateParamCount  int
   308  	templateTemplateParamCount int
   309  }
   310  
   311  // copy returns a copy of the current state.
   312  func (st *state) copy() *state {
   313  	n := new(state)
   314  	*n = *st
   315  	return n
   316  }
   317  
   318  // fail panics with demangleErr, to be caught in doDemangle.
   319  func (st *state) fail(err string) {
   320  	panic(demangleErr{err: err, off: st.off})
   321  }
   322  
   323  // failEarlier is like fail, but decrements the offset to indicate
   324  // that the point of failure occurred earlier in the string.
   325  func (st *state) failEarlier(err string, dec int) {
   326  	if st.off < dec {
   327  		panic("internal error")
   328  	}
   329  	panic(demangleErr{err: err, off: st.off - dec})
   330  }
   331  
   332  // advance advances the current string offset.
   333  func (st *state) advance(add int) {
   334  	if len(st.str) < add {
   335  		panic("internal error")
   336  	}
   337  	st.str = st.str[add:]
   338  	st.off += add
   339  }
   340  
   341  // checkChar requires that the next character in the string be c, and
   342  // advances past it.
   343  func (st *state) checkChar(c byte) {
   344  	if len(st.str) == 0 || st.str[0] != c {
   345  		panic("internal error")
   346  	}
   347  	st.advance(1)
   348  }
   349  
   350  // A demangleErr is an error at a specific offset in the mangled
   351  // string.
   352  type demangleErr struct {
   353  	err string
   354  	off int
   355  }
   356  
   357  // Error implements the builtin error interface for demangleErr.
   358  func (de demangleErr) Error() string {
   359  	return fmt.Sprintf("%s at %d", de.err, de.off)
   360  }
   361  
   362  // adjustErr adjusts the position of err, if it is a demangleErr,
   363  // and returns err.
   364  func adjustErr(err error, adj int) error {
   365  	if err == nil {
   366  		return nil
   367  	}
   368  	if de, ok := err.(demangleErr); ok {
   369  		de.off += adj
   370  		return de
   371  	}
   372  	return err
   373  }
   374  
   375  type forLocalNameType int
   376  
   377  const (
   378  	forLocalName forLocalNameType = iota
   379  	notForLocalName
   380  )
   381  
   382  // encoding parses:
   383  //
   384  //	encoding ::= <(function) name> <bare-function-type>
   385  //	             <(data) name>
   386  //	             <special-name>
   387  func (st *state) encoding(params bool, local forLocalNameType) AST {
   388  	if len(st.str) < 1 {
   389  		st.fail("expected encoding")
   390  	}
   391  
   392  	if st.str[0] == 'G' || st.str[0] == 'T' {
   393  		return st.specialName()
   394  	}
   395  
   396  	a := st.name()
   397  	a = simplify(a)
   398  
   399  	if !params {
   400  		// Don't demangle the parameters.
   401  
   402  		// Strip CV-qualifiers, as they apply to the 'this'
   403  		// parameter, and are not output by the standard
   404  		// demangler without parameters.
   405  		if mwq, ok := a.(*MethodWithQualifiers); ok {
   406  			a = mwq.Method
   407  		}
   408  
   409  		// If this is a local name, there may be CV-qualifiers
   410  		// on the name that really apply to the top level, and
   411  		// therefore must be discarded when discarding
   412  		// parameters.  This can happen when parsing a class
   413  		// that is local to a function.
   414  		if q, ok := a.(*Qualified); ok && q.LocalName {
   415  			p := &q.Name
   416  			if da, ok := (*p).(*DefaultArg); ok {
   417  				p = &da.Arg
   418  			}
   419  			if mwq, ok := (*p).(*MethodWithQualifiers); ok {
   420  				*p = mwq.Method
   421  			}
   422  		}
   423  
   424  		return a
   425  	}
   426  
   427  	if len(st.str) == 0 || st.str[0] == 'E' {
   428  		// There are no parameters--this is a data symbol, not
   429  		// a function symbol.
   430  		return a
   431  	}
   432  
   433  	mwq, _ := a.(*MethodWithQualifiers)
   434  
   435  	var findTemplate func(AST) *Template
   436  	findTemplate = func(check AST) *Template {
   437  		switch check := check.(type) {
   438  		case *Template:
   439  			return check
   440  		case *Qualified:
   441  			if check.LocalName {
   442  				return findTemplate(check.Name)
   443  			} else if _, ok := check.Name.(*Constructor); ok {
   444  				return findTemplate(check.Name)
   445  			}
   446  		case *MethodWithQualifiers:
   447  			return findTemplate(check.Method)
   448  		case *Constructor:
   449  			if check.Base != nil {
   450  				return findTemplate(check.Base)
   451  			}
   452  		}
   453  		return nil
   454  	}
   455  
   456  	template := findTemplate(a)
   457  	var oldLambdaTemplateLevel int
   458  	if template != nil {
   459  		st.templates = append(st.templates, template)
   460  		oldLambdaTemplateLevel = st.lambdaTemplateLevel
   461  		st.lambdaTemplateLevel = 0
   462  	}
   463  
   464  	// Checking for the enable_if attribute here is what the LLVM
   465  	// demangler does.  This is not very general but perhaps it is
   466  	// sufficient.
   467  	const enableIfPrefix = "Ua9enable_ifI"
   468  	var enableIfArgs []AST
   469  	if strings.HasPrefix(st.str, enableIfPrefix) {
   470  		st.advance(len(enableIfPrefix) - 1)
   471  		enableIfArgs = st.templateArgs()
   472  	}
   473  
   474  	ft := st.bareFunctionType(hasReturnType(a))
   475  
   476  	if template != nil {
   477  		st.templates = st.templates[:len(st.templates)-1]
   478  		st.lambdaTemplateLevel = oldLambdaTemplateLevel
   479  	}
   480  
   481  	ft = simplify(ft)
   482  
   483  	// For a local name, discard the return type, so that it
   484  	// doesn't get confused with the top level return type.
   485  	if local == forLocalName {
   486  		if functype, ok := ft.(*FunctionType); ok {
   487  			functype.ForLocalName = true
   488  		}
   489  	}
   490  
   491  	// Any top-level qualifiers belong to the function type.
   492  	if mwq != nil {
   493  		a = mwq.Method
   494  		mwq.Method = ft
   495  		ft = mwq
   496  	}
   497  	if q, ok := a.(*Qualified); ok && q.LocalName {
   498  		p := &q.Name
   499  		if da, ok := (*p).(*DefaultArg); ok {
   500  			p = &da.Arg
   501  		}
   502  		if mwq, ok := (*p).(*MethodWithQualifiers); ok {
   503  			*p = mwq.Method
   504  			mwq.Method = ft
   505  			ft = mwq
   506  		}
   507  	}
   508  
   509  	r := AST(&Typed{Name: a, Type: ft})
   510  
   511  	if len(enableIfArgs) > 0 {
   512  		r = &EnableIf{Type: r, Args: enableIfArgs}
   513  	}
   514  
   515  	return r
   516  }
   517  
   518  // hasReturnType returns whether the mangled form of a will have a
   519  // return type.
   520  func hasReturnType(a AST) bool {
   521  	switch a := a.(type) {
   522  	case *Qualified:
   523  		if a.LocalName {
   524  			return hasReturnType(a.Name)
   525  		}
   526  		return false
   527  	case *Template:
   528  		return !isCDtorConversion(a.Name)
   529  	case *TypeWithQualifiers:
   530  		return hasReturnType(a.Base)
   531  	case *MethodWithQualifiers:
   532  		return hasReturnType(a.Method)
   533  	default:
   534  		return false
   535  	}
   536  }
   537  
   538  // isCDtorConversion returns when an AST is a constructor, a
   539  // destructor, or a conversion operator.
   540  func isCDtorConversion(a AST) bool {
   541  	switch a := a.(type) {
   542  	case *Qualified:
   543  		return isCDtorConversion(a.Name)
   544  	case *Constructor, *Destructor, *Cast:
   545  		return true
   546  	default:
   547  		return false
   548  	}
   549  }
   550  
   551  // taggedName parses:
   552  //
   553  //	<tagged-name> ::= <name> B <source-name>
   554  func (st *state) taggedName(a AST) AST {
   555  	for len(st.str) > 0 && st.str[0] == 'B' {
   556  		st.advance(1)
   557  		tag := st.sourceName()
   558  		a = &TaggedName{Name: a, Tag: tag}
   559  	}
   560  	return a
   561  }
   562  
   563  // name parses:
   564  //
   565  //	<name> ::= <nested-name>
   566  //	       ::= <unscoped-name>
   567  //	       ::= <unscoped-template-name> <template-args>
   568  //	       ::= <local-name>
   569  //
   570  //	<unscoped-name> ::= <unqualified-name>
   571  //	                ::= St <unqualified-name>
   572  //
   573  //	<unscoped-template-name> ::= <unscoped-name>
   574  //	                         ::= <substitution>
   575  func (st *state) name() AST {
   576  	if len(st.str) < 1 {
   577  		st.fail("expected name")
   578  	}
   579  	switch st.str[0] {
   580  	case 'N':
   581  		return st.nestedName()
   582  	case 'Z':
   583  		return st.localName()
   584  	case 'U':
   585  		a, isCast := st.unqualifiedName()
   586  		if isCast {
   587  			st.setTemplate(a, nil)
   588  		}
   589  		return a
   590  	case 'S':
   591  		if len(st.str) < 2 {
   592  			st.advance(1)
   593  			st.fail("expected substitution index")
   594  		}
   595  		var a AST
   596  		isCast := false
   597  		subst := false
   598  		if st.str[1] == 't' {
   599  			st.advance(2)
   600  			a, isCast = st.unqualifiedName()
   601  			a = &Qualified{Scope: &Name{Name: "std"}, Name: a, LocalName: false}
   602  		} else {
   603  			a = st.substitution(false)
   604  			subst = true
   605  		}
   606  		if len(st.str) > 0 && st.str[0] == 'I' {
   607  			// This can only happen if we saw
   608  			// <unscoped-template-name> and are about to see
   609  			// <template-args>.  <unscoped-template-name> is a
   610  			// substitution candidate if it did not come from a
   611  			// substitution.
   612  			if !subst {
   613  				st.subs.add(a)
   614  			}
   615  			args := st.templateArgs()
   616  			tmpl := &Template{Name: a, Args: args}
   617  			if isCast {
   618  				st.setTemplate(a, tmpl)
   619  				st.clearTemplateArgs(args)
   620  				isCast = false
   621  			}
   622  			a = tmpl
   623  		}
   624  		if isCast {
   625  			st.setTemplate(a, nil)
   626  		}
   627  		return a
   628  
   629  	default:
   630  		a, isCast := st.unqualifiedName()
   631  		if len(st.str) > 0 && st.str[0] == 'I' {
   632  			st.subs.add(a)
   633  			args := st.templateArgs()
   634  			tmpl := &Template{Name: a, Args: args}
   635  			if isCast {
   636  				st.setTemplate(a, tmpl)
   637  				st.clearTemplateArgs(args)
   638  				isCast = false
   639  			}
   640  			a = tmpl
   641  		}
   642  		if isCast {
   643  			st.setTemplate(a, nil)
   644  		}
   645  		return a
   646  	}
   647  }
   648  
   649  // nestedName parses:
   650  //
   651  //	<nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
   652  //	              ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
   653  func (st *state) nestedName() AST {
   654  	st.checkChar('N')
   655  	q := st.cvQualifiers()
   656  	r := st.refQualifier()
   657  	a := st.prefix()
   658  	if q != nil || r != "" {
   659  		a = &MethodWithQualifiers{Method: a, Qualifiers: q, RefQualifier: r}
   660  	}
   661  	if len(st.str) == 0 || st.str[0] != 'E' {
   662  		st.fail("expected E after nested name")
   663  	}
   664  	st.advance(1)
   665  	return a
   666  }
   667  
   668  // prefix parses:
   669  //
   670  //	<prefix> ::= <prefix> <unqualified-name>
   671  //	         ::= <template-prefix> <template-args>
   672  //	         ::= <template-param>
   673  //	         ::= <decltype>
   674  //	         ::=
   675  //	         ::= <substitution>
   676  //
   677  //	<template-prefix> ::= <prefix> <(template) unqualified-name>
   678  //	                  ::= <template-param>
   679  //	                  ::= <substitution>
   680  //
   681  //	<decltype> ::= Dt <expression> E
   682  //	           ::= DT <expression> E
   683  func (st *state) prefix() AST {
   684  	var a AST
   685  
   686  	// The last name seen, for a constructor/destructor.
   687  	var last AST
   688  
   689  	getLast := func(a AST) AST {
   690  		for {
   691  			if t, ok := a.(*Template); ok {
   692  				a = t.Name
   693  			} else if q, ok := a.(*Qualified); ok {
   694  				a = q.Name
   695  			} else if t, ok := a.(*TaggedName); ok {
   696  				a = t.Name
   697  			} else {
   698  				return a
   699  			}
   700  		}
   701  	}
   702  
   703  	var cast *Cast
   704  	for {
   705  		if len(st.str) == 0 {
   706  			st.fail("expected prefix")
   707  		}
   708  		var next AST
   709  
   710  		c := st.str[0]
   711  		if isDigit(c) || isLower(c) || c == 'U' || c == 'L' || (c == 'D' && len(st.str) > 1 && st.str[1] == 'C') {
   712  			un, isUnCast := st.unqualifiedName()
   713  			next = un
   714  			if isUnCast {
   715  				if tn, ok := un.(*TaggedName); ok {
   716  					un = tn.Name
   717  				}
   718  				cast = un.(*Cast)
   719  			}
   720  		} else {
   721  			switch st.str[0] {
   722  			case 'C':
   723  				inheriting := false
   724  				st.advance(1)
   725  				if len(st.str) > 0 && st.str[0] == 'I' {
   726  					inheriting = true
   727  					st.advance(1)
   728  				}
   729  				if len(st.str) < 1 {
   730  					st.fail("expected constructor type")
   731  				}
   732  				if last == nil {
   733  					st.fail("constructor before name is seen")
   734  				}
   735  				st.advance(1)
   736  				var base AST
   737  				if inheriting {
   738  					base = st.demangleType(false)
   739  				}
   740  				next = &Constructor{
   741  					Name: getLast(last),
   742  					Base: base,
   743  				}
   744  				if len(st.str) > 0 && st.str[0] == 'B' {
   745  					next = st.taggedName(next)
   746  				}
   747  			case 'D':
   748  				if len(st.str) > 1 && (st.str[1] == 'T' || st.str[1] == 't') {
   749  					next = st.demangleType(false)
   750  				} else {
   751  					if len(st.str) < 2 {
   752  						st.fail("expected destructor type")
   753  					}
   754  					if last == nil {
   755  						st.fail("destructor before name is seen")
   756  					}
   757  					st.advance(2)
   758  					next = &Destructor{Name: getLast(last)}
   759  					if len(st.str) > 0 && st.str[0] == 'B' {
   760  						next = st.taggedName(next)
   761  					}
   762  				}
   763  			case 'S':
   764  				next = st.substitution(true)
   765  			case 'I':
   766  				if a == nil {
   767  					st.fail("unexpected template arguments")
   768  				}
   769  				var args []AST
   770  				args = st.templateArgs()
   771  				tmpl := &Template{Name: a, Args: args}
   772  				if cast != nil {
   773  					st.setTemplate(cast, tmpl)
   774  					st.clearTemplateArgs(args)
   775  					cast = nil
   776  				}
   777  				a = nil
   778  				next = tmpl
   779  			case 'T':
   780  				next = st.templateParam()
   781  			case 'E':
   782  				if a == nil {
   783  					st.fail("expected prefix")
   784  				}
   785  				if cast != nil {
   786  					var toTmpl *Template
   787  					if castTempl, ok := cast.To.(*Template); ok {
   788  						toTmpl = castTempl
   789  					}
   790  					st.setTemplate(cast, toTmpl)
   791  				}
   792  				return a
   793  			case 'M':
   794  				if a == nil {
   795  					st.fail("unexpected lambda initializer")
   796  				}
   797  				// This is the initializer scope for a
   798  				// lambda.  We don't need to record
   799  				// it.  The normal code will treat the
   800  				// variable has a type scope, which
   801  				// gives appropriate output.
   802  				st.advance(1)
   803  				continue
   804  			case 'J':
   805  				// It appears that in some cases clang
   806  				// can emit a J for a template arg
   807  				// without the expected I.  I don't
   808  				// know when this happens, but I've
   809  				// seen it in some large C++ programs.
   810  				if a == nil {
   811  					st.fail("unexpected template arguments")
   812  				}
   813  				var args []AST
   814  				for len(st.str) == 0 || st.str[0] != 'E' {
   815  					arg := st.templateArg()
   816  					args = append(args, arg)
   817  				}
   818  				st.advance(1)
   819  				tmpl := &Template{Name: a, Args: args}
   820  				if cast != nil {
   821  					st.setTemplate(cast, tmpl)
   822  					st.clearTemplateArgs(args)
   823  					cast = nil
   824  				}
   825  				a = nil
   826  				next = tmpl
   827  			default:
   828  				st.fail("unrecognized letter in prefix")
   829  			}
   830  		}
   831  		last = next
   832  		if a == nil {
   833  			a = next
   834  		} else {
   835  			a = &Qualified{Scope: a, Name: next, LocalName: false}
   836  		}
   837  
   838  		if c != 'S' && (len(st.str) == 0 || st.str[0] != 'E') {
   839  			st.subs.add(a)
   840  		}
   841  	}
   842  }
   843  
   844  // unqualifiedName parses:
   845  //
   846  //	<unqualified-name> ::= <operator-name>
   847  //	                   ::= <ctor-dtor-name>
   848  //	                   ::= <source-name>
   849  //	                   ::= <local-source-name>
   850  //
   851  //	 <local-source-name>	::= L <source-name> <discriminator>
   852  func (st *state) unqualifiedName() (r AST, isCast bool) {
   853  	if len(st.str) < 1 {
   854  		st.fail("expected unqualified name")
   855  	}
   856  	var a AST
   857  	isCast = false
   858  	c := st.str[0]
   859  	if isDigit(c) {
   860  		a = st.sourceName()
   861  	} else if isLower(c) {
   862  		a, _ = st.operatorName(false)
   863  		if _, ok := a.(*Cast); ok {
   864  			isCast = true
   865  		}
   866  		if op, ok := a.(*Operator); ok && op.Name == `operator"" ` {
   867  			n := st.sourceName()
   868  			a = &Unary{Op: op, Expr: n, Suffix: false, SizeofType: false}
   869  		}
   870  	} else if c == 'D' && len(st.str) > 1 && st.str[1] == 'C' {
   871  		var bindings []AST
   872  		st.advance(2)
   873  		for {
   874  			binding := st.sourceName()
   875  			bindings = append(bindings, binding)
   876  			if len(st.str) > 0 && st.str[0] == 'E' {
   877  				st.advance(1)
   878  				break
   879  			}
   880  		}
   881  		a = &StructuredBindings{Bindings: bindings}
   882  	} else {
   883  		switch c {
   884  		case 'C', 'D':
   885  			st.fail("constructor/destructor not in nested name")
   886  		case 'L':
   887  			st.advance(1)
   888  			a = st.sourceName()
   889  			a = st.discriminator(a)
   890  		case 'U':
   891  			if len(st.str) < 2 {
   892  				st.advance(1)
   893  				st.fail("expected closure or unnamed type")
   894  			}
   895  			c := st.str[1]
   896  			switch c {
   897  			case 'b':
   898  				st.advance(2)
   899  				st.compactNumber()
   900  				a = &Name{Name: "'block-literal'"}
   901  			case 'l':
   902  				a = st.closureTypeName()
   903  			case 't':
   904  				a = st.unnamedTypeName()
   905  			default:
   906  				st.advance(1)
   907  				st.fail("expected closure or unnamed type")
   908  			}
   909  		default:
   910  			st.fail("expected unqualified name")
   911  		}
   912  	}
   913  
   914  	if len(st.str) > 0 && st.str[0] == 'B' {
   915  		a = st.taggedName(a)
   916  	}
   917  
   918  	return a, isCast
   919  }
   920  
   921  // sourceName parses:
   922  //
   923  //	<source-name> ::= <(positive length) number> <identifier>
   924  //	identifier ::= <(unqualified source code identifier)>
   925  func (st *state) sourceName() AST {
   926  	val := st.number()
   927  	if val <= 0 {
   928  		st.fail("expected positive number")
   929  	}
   930  	if len(st.str) < val {
   931  		st.fail("not enough characters for identifier")
   932  	}
   933  	id := st.str[:val]
   934  	st.advance(val)
   935  
   936  	// Look for GCC encoding of anonymous namespace, and make it
   937  	// more friendly.
   938  	const anonPrefix = "_GLOBAL_"
   939  	if strings.HasPrefix(id, anonPrefix) && len(id) > len(anonPrefix)+2 {
   940  		c1 := id[len(anonPrefix)]
   941  		c2 := id[len(anonPrefix)+1]
   942  		if (c1 == '.' || c1 == '_' || c1 == '$') && c2 == 'N' {
   943  			id = "(anonymous namespace)"
   944  		}
   945  	}
   946  
   947  	n := &Name{Name: id}
   948  	return n
   949  }
   950  
   951  // number parses:
   952  //
   953  //	number ::= [n] <(non-negative decimal integer)>
   954  func (st *state) number() int {
   955  	neg := false
   956  	if len(st.str) > 0 && st.str[0] == 'n' {
   957  		neg = true
   958  		st.advance(1)
   959  	}
   960  	if len(st.str) == 0 || !isDigit(st.str[0]) {
   961  		st.fail("missing number")
   962  	}
   963  	val := 0
   964  	for len(st.str) > 0 && isDigit(st.str[0]) {
   965  		// Number picked to ensure we can't overflow with 32-bit int.
   966  		// Any very large number here is bogus.
   967  		if val >= 0x80000000/10-10 {
   968  			st.fail("numeric overflow")
   969  		}
   970  		val = val*10 + int(st.str[0]-'0')
   971  		st.advance(1)
   972  	}
   973  	if neg {
   974  		val = -val
   975  	}
   976  	return val
   977  }
   978  
   979  // seqID parses:
   980  //
   981  //	<seq-id> ::= <0-9A-Z>+
   982  //
   983  // We expect this to be followed by an underscore.
   984  func (st *state) seqID(eofOK bool) int {
   985  	if len(st.str) > 0 && st.str[0] == '_' {
   986  		st.advance(1)
   987  		return 0
   988  	}
   989  	id := 0
   990  	for {
   991  		if len(st.str) == 0 {
   992  			if eofOK {
   993  				return id + 1
   994  			}
   995  			st.fail("missing end to sequence ID")
   996  		}
   997  		// Don't overflow a 32-bit int.
   998  		if id >= 0x80000000/36-36 {
   999  			st.fail("sequence ID overflow")
  1000  		}
  1001  		c := st.str[0]
  1002  		if c == '_' {
  1003  			st.advance(1)
  1004  			return id + 1
  1005  		}
  1006  		if isDigit(c) {
  1007  			id = id*36 + int(c-'0')
  1008  		} else if isUpper(c) {
  1009  			id = id*36 + int(c-'A') + 10
  1010  		} else {
  1011  			st.fail("invalid character in sequence ID")
  1012  		}
  1013  		st.advance(1)
  1014  	}
  1015  }
  1016  
  1017  // An operator is the demangled name, and the number of arguments it
  1018  // takes in an expression.
  1019  type operator struct {
  1020  	name string
  1021  	args int
  1022  }
  1023  
  1024  // The operators map maps the mangled operator names to information
  1025  // about them.
  1026  var operators = map[string]operator{
  1027  	"aN": {"&=", 2},
  1028  	"aS": {"=", 2},
  1029  	"aa": {"&&", 2},
  1030  	"ad": {"&", 1},
  1031  	"an": {"&", 2},
  1032  	"at": {"alignof ", 1},
  1033  	"aw": {"co_await ", 1},
  1034  	"az": {"alignof ", 1},
  1035  	"cc": {"const_cast", 2},
  1036  	"cl": {"()", 2},
  1037  	// cp is not in the ABI but is used by clang "when the call
  1038  	// would use ADL except for being parenthesized."
  1039  	"cp": {"()", 2},
  1040  	"cm": {",", 2},
  1041  	"co": {"~", 1},
  1042  	"dV": {"/=", 2},
  1043  	"dX": {"[...]=", 3},
  1044  	"da": {"delete[] ", 1},
  1045  	"dc": {"dynamic_cast", 2},
  1046  	"de": {"*", 1},
  1047  	"di": {"=", 2},
  1048  	"dl": {"delete ", 1},
  1049  	"ds": {".*", 2},
  1050  	"dt": {".", 2},
  1051  	"dv": {"/", 2},
  1052  	"dx": {"]=", 2},
  1053  	"eO": {"^=", 2},
  1054  	"eo": {"^", 2},
  1055  	"eq": {"==", 2},
  1056  	"fl": {"...", 2},
  1057  	"fr": {"...", 2},
  1058  	"fL": {"...", 3},
  1059  	"fR": {"...", 3},
  1060  	"ge": {">=", 2},
  1061  	"gs": {"::", 1},
  1062  	"gt": {">", 2},
  1063  	"ix": {"[]", 2},
  1064  	"lS": {"<<=", 2},
  1065  	"le": {"<=", 2},
  1066  	"li": {`operator"" `, 1},
  1067  	"ls": {"<<", 2},
  1068  	"lt": {"<", 2},
  1069  	"mI": {"-=", 2},
  1070  	"mL": {"*=", 2},
  1071  	"mi": {"-", 2},
  1072  	"ml": {"*", 2},
  1073  	"mm": {"--", 1},
  1074  	"na": {"new[]", 3},
  1075  	"ne": {"!=", 2},
  1076  	"ng": {"-", 1},
  1077  	"nt": {"!", 1},
  1078  	"nw": {"new", 3},
  1079  	"nx": {"noexcept", 1},
  1080  	"oR": {"|=", 2},
  1081  	"oo": {"||", 2},
  1082  	"or": {"|", 2},
  1083  	"pL": {"+=", 2},
  1084  	"pl": {"+", 2},
  1085  	"pm": {"->*", 2},
  1086  	"pp": {"++", 1},
  1087  	"ps": {"+", 1},
  1088  	"pt": {"->", 2},
  1089  	"qu": {"?", 3},
  1090  	"rM": {"%=", 2},
  1091  	"rS": {">>=", 2},
  1092  	"rc": {"reinterpret_cast", 2},
  1093  	"rm": {"%", 2},
  1094  	"rs": {">>", 2},
  1095  	"sP": {"sizeof...", 1},
  1096  	"sZ": {"sizeof...", 1},
  1097  	"sc": {"static_cast", 2},
  1098  	"ss": {"<=>", 2},
  1099  	"st": {"sizeof ", 1},
  1100  	"sz": {"sizeof ", 1},
  1101  	"tr": {"throw", 0},
  1102  	"tw": {"throw ", 1},
  1103  }
  1104  
  1105  // operatorName parses:
  1106  //
  1107  //	operator_name ::= many different two character encodings.
  1108  //	              ::= cv <type>
  1109  //	              ::= v <digit> <source-name>
  1110  //
  1111  // We need to know whether we are in an expression because it affects
  1112  // how we handle template parameters in the type of a cast operator.
  1113  func (st *state) operatorName(inExpression bool) (AST, int) {
  1114  	if len(st.str) < 2 {
  1115  		st.fail("missing operator code")
  1116  	}
  1117  	code := st.str[:2]
  1118  	st.advance(2)
  1119  	if code[0] == 'v' && isDigit(code[1]) {
  1120  		name := st.sourceName()
  1121  		return &Operator{Name: name.(*Name).Name}, int(code[1] - '0')
  1122  	} else if code == "cv" {
  1123  		// Push a nil on templates to indicate that template
  1124  		// parameters will have their template filled in
  1125  		// later.
  1126  		if !inExpression {
  1127  			st.templates = append(st.templates, nil)
  1128  		}
  1129  
  1130  		t := st.demangleType(!inExpression)
  1131  
  1132  		if !inExpression {
  1133  			st.templates = st.templates[:len(st.templates)-1]
  1134  		}
  1135  
  1136  		return &Cast{To: t}, 1
  1137  	} else if op, ok := operators[code]; ok {
  1138  		return &Operator{Name: op.name}, op.args
  1139  	} else {
  1140  		st.failEarlier("unrecognized operator code", 2)
  1141  		panic("not reached")
  1142  	}
  1143  }
  1144  
  1145  // localName parses:
  1146  //
  1147  //	<local-name> ::= Z <(function) encoding> E <(entity) name> [<discriminator>]
  1148  //	             ::= Z <(function) encoding> E s [<discriminator>]
  1149  //	             ::= Z <(function) encoding> E d [<parameter> number>] _ <entity name>
  1150  func (st *state) localName() AST {
  1151  	st.checkChar('Z')
  1152  	fn := st.encoding(true, forLocalName)
  1153  	if len(st.str) == 0 || st.str[0] != 'E' {
  1154  		st.fail("expected E after local name")
  1155  	}
  1156  	st.advance(1)
  1157  	if len(st.str) > 0 && st.str[0] == 's' {
  1158  		st.advance(1)
  1159  		var n AST = &Name{Name: "string literal"}
  1160  		n = st.discriminator(n)
  1161  		return &Qualified{Scope: fn, Name: n, LocalName: true}
  1162  	} else {
  1163  		num := -1
  1164  		if len(st.str) > 0 && st.str[0] == 'd' {
  1165  			// Default argument scope.
  1166  			st.advance(1)
  1167  			num = st.compactNumber()
  1168  		}
  1169  		n := st.name()
  1170  		n = st.discriminator(n)
  1171  		if num >= 0 {
  1172  			n = &DefaultArg{Num: num, Arg: n}
  1173  		}
  1174  		return &Qualified{Scope: fn, Name: n, LocalName: true}
  1175  	}
  1176  }
  1177  
  1178  // Parse a Java resource special-name.
  1179  func (st *state) javaResource() AST {
  1180  	off := st.off
  1181  	ln := st.number()
  1182  	if ln <= 1 {
  1183  		st.failEarlier("java resource length less than 1", st.off-off)
  1184  	}
  1185  	if len(st.str) == 0 || st.str[0] != '_' {
  1186  		st.fail("expected _ after number")
  1187  	}
  1188  	st.advance(1)
  1189  	ln--
  1190  	if len(st.str) < ln {
  1191  		st.fail("not enough characters for java resource length")
  1192  	}
  1193  	str := st.str[:ln]
  1194  	final := ""
  1195  	st.advance(ln)
  1196  	for i := 0; i < len(str); i++ {
  1197  		if str[i] != '$' {
  1198  			final += string(str[i])
  1199  		} else {
  1200  			if len(str) <= i+1 {
  1201  				st.failEarlier("java resource escape at end of string", 1)
  1202  			}
  1203  			i++
  1204  			r, ok := map[byte]string{
  1205  				'S': "/",
  1206  				'_': ".",
  1207  				'$': "$",
  1208  			}[str[i]]
  1209  			if !ok {
  1210  				st.failEarlier("unrecognized java resource escape", ln-i-1)
  1211  			}
  1212  			final += r
  1213  		}
  1214  	}
  1215  	return &Special{Prefix: "java resource ", Val: &Name{Name: final}}
  1216  }
  1217  
  1218  // specialName parses:
  1219  //
  1220  //	<special-name> ::= TV <type>
  1221  //	               ::= TT <type>
  1222  //	               ::= TI <type>
  1223  //	               ::= TS <type>
  1224  //	               ::= TA <template-arg>
  1225  //	               ::= GV <(object) name>
  1226  //	               ::= T <call-offset> <(base) encoding>
  1227  //	               ::= Tc <call-offset> <call-offset> <(base) encoding>
  1228  //	g++ extensions:
  1229  //	               ::= TC <type> <(offset) number> _ <(base) type>
  1230  //	               ::= TF <type>
  1231  //	               ::= TJ <type>
  1232  //	               ::= GR <name>
  1233  //	               ::= GA <encoding>
  1234  //	               ::= Gr <resource name>
  1235  //	               ::= GTt <encoding>
  1236  //	               ::= GTn <encoding>
  1237  func (st *state) specialName() AST {
  1238  	if st.str[0] == 'T' {
  1239  		st.advance(1)
  1240  		if len(st.str) == 0 {
  1241  			st.fail("expected special name code")
  1242  		}
  1243  		c := st.str[0]
  1244  		st.advance(1)
  1245  		switch c {
  1246  		case 'V':
  1247  			t := st.demangleType(false)
  1248  			return &Special{Prefix: "vtable for ", Val: t}
  1249  		case 'T':
  1250  			t := st.demangleType(false)
  1251  			return &Special{Prefix: "VTT for ", Val: t}
  1252  		case 'I':
  1253  			t := st.demangleType(false)
  1254  			return &Special{Prefix: "typeinfo for ", Val: t}
  1255  		case 'S':
  1256  			t := st.demangleType(false)
  1257  			return &Special{Prefix: "typeinfo name for ", Val: t}
  1258  		case 'A':
  1259  			t := st.templateArg()
  1260  			return &Special{Prefix: "template parameter object for ", Val: t}
  1261  		case 'h':
  1262  			st.callOffset('h')
  1263  			v := st.encoding(true, notForLocalName)
  1264  			return &Special{Prefix: "non-virtual thunk to ", Val: v}
  1265  		case 'v':
  1266  			st.callOffset('v')
  1267  			v := st.encoding(true, notForLocalName)
  1268  			return &Special{Prefix: "virtual thunk to ", Val: v}
  1269  		case 'c':
  1270  			st.callOffset(0)
  1271  			st.callOffset(0)
  1272  			v := st.encoding(true, notForLocalName)
  1273  			return &Special{Prefix: "covariant return thunk to ", Val: v}
  1274  		case 'C':
  1275  			derived := st.demangleType(false)
  1276  			off := st.off
  1277  			offset := st.number()
  1278  			if offset < 0 {
  1279  				st.failEarlier("expected positive offset", st.off-off)
  1280  			}
  1281  			if len(st.str) == 0 || st.str[0] != '_' {
  1282  				st.fail("expected _ after number")
  1283  			}
  1284  			st.advance(1)
  1285  			base := st.demangleType(false)
  1286  			return &Special2{Prefix: "construction vtable for ", Val1: base, Middle: "-in-", Val2: derived}
  1287  		case 'F':
  1288  			t := st.demangleType(false)
  1289  			return &Special{Prefix: "typeinfo fn for ", Val: t}
  1290  		case 'J':
  1291  			t := st.demangleType(false)
  1292  			return &Special{Prefix: "java Class for ", Val: t}
  1293  		case 'H':
  1294  			n := st.name()
  1295  			return &Special{Prefix: "TLS init function for ", Val: n}
  1296  		case 'W':
  1297  			n := st.name()
  1298  			return &Special{Prefix: "TLS wrapper function for ", Val: n}
  1299  		default:
  1300  			st.fail("unrecognized special T name code")
  1301  			panic("not reached")
  1302  		}
  1303  	} else {
  1304  		st.checkChar('G')
  1305  		if len(st.str) == 0 {
  1306  			st.fail("expected special name code")
  1307  		}
  1308  		c := st.str[0]
  1309  		st.advance(1)
  1310  		switch c {
  1311  		case 'V':
  1312  			n := st.name()
  1313  			return &Special{Prefix: "guard variable for ", Val: n}
  1314  		case 'R':
  1315  			n := st.name()
  1316  			st.seqID(true)
  1317  			return &Special{Prefix: "reference temporary for ", Val: n}
  1318  		case 'A':
  1319  			v := st.encoding(true, notForLocalName)
  1320  			return &Special{Prefix: "hidden alias for ", Val: v}
  1321  		case 'T':
  1322  			if len(st.str) == 0 {
  1323  				st.fail("expected special GT name code")
  1324  			}
  1325  			c := st.str[0]
  1326  			st.advance(1)
  1327  			v := st.encoding(true, notForLocalName)
  1328  			switch c {
  1329  			case 'n':
  1330  				return &Special{Prefix: "non-transaction clone for ", Val: v}
  1331  			default:
  1332  				// The proposal is that different
  1333  				// letters stand for different types
  1334  				// of transactional cloning.  Treat
  1335  				// them all the same for now.
  1336  				fallthrough
  1337  			case 't':
  1338  				return &Special{Prefix: "transaction clone for ", Val: v}
  1339  			}
  1340  		case 'r':
  1341  			return st.javaResource()
  1342  		default:
  1343  			st.fail("unrecognized special G name code")
  1344  			panic("not reached")
  1345  		}
  1346  	}
  1347  }
  1348  
  1349  // callOffset parses:
  1350  //
  1351  //	<call-offset> ::= h <nv-offset> _
  1352  //	              ::= v <v-offset> _
  1353  //
  1354  //	<nv-offset> ::= <(offset) number>
  1355  //
  1356  //	<v-offset> ::= <(offset) number> _ <(virtual offset) number>
  1357  //
  1358  // The c parameter, if not 0, is a character we just read which is the
  1359  // start of the <call-offset>.
  1360  //
  1361  // We don't display the offset information anywhere.
  1362  func (st *state) callOffset(c byte) {
  1363  	if c == 0 {
  1364  		if len(st.str) == 0 {
  1365  			st.fail("missing call offset")
  1366  		}
  1367  		c = st.str[0]
  1368  		st.advance(1)
  1369  	}
  1370  	switch c {
  1371  	case 'h':
  1372  		st.number()
  1373  	case 'v':
  1374  		st.number()
  1375  		if len(st.str) == 0 || st.str[0] != '_' {
  1376  			st.fail("expected _ after number")
  1377  		}
  1378  		st.advance(1)
  1379  		st.number()
  1380  	default:
  1381  		st.failEarlier("unrecognized call offset code", 1)
  1382  	}
  1383  	if len(st.str) == 0 || st.str[0] != '_' {
  1384  		st.fail("expected _ after call offset")
  1385  	}
  1386  	st.advance(1)
  1387  }
  1388  
  1389  // builtinTypes maps the type letter to the type name.
  1390  var builtinTypes = map[byte]string{
  1391  	'a': "signed char",
  1392  	'b': "bool",
  1393  	'c': "char",
  1394  	'd': "double",
  1395  	'e': "long double",
  1396  	'f': "float",
  1397  	'g': "__float128",
  1398  	'h': "unsigned char",
  1399  	'i': "int",
  1400  	'j': "unsigned int",
  1401  	'l': "long",
  1402  	'm': "unsigned long",
  1403  	'n': "__int128",
  1404  	'o': "unsigned __int128",
  1405  	's': "short",
  1406  	't': "unsigned short",
  1407  	'v': "void",
  1408  	'w': "wchar_t",
  1409  	'x': "long long",
  1410  	'y': "unsigned long long",
  1411  	'z': "...",
  1412  }
  1413  
  1414  // demangleType parses:
  1415  //
  1416  //	<type> ::= <builtin-type>
  1417  //	       ::= <function-type>
  1418  //	       ::= <class-enum-type>
  1419  //	       ::= <array-type>
  1420  //	       ::= <pointer-to-member-type>
  1421  //	       ::= <template-param>
  1422  //	       ::= <template-template-param> <template-args>
  1423  //	       ::= <substitution>
  1424  //	       ::= <CV-qualifiers> <type>
  1425  //	       ::= P <type>
  1426  //	       ::= R <type>
  1427  //	       ::= O <type> (C++0x)
  1428  //	       ::= C <type>
  1429  //	       ::= G <type>
  1430  //	       ::= U <source-name> <type>
  1431  //
  1432  //	<builtin-type> ::= various one letter codes
  1433  //	               ::= u <source-name>
  1434  func (st *state) demangleType(isCast bool) AST {
  1435  	if len(st.str) == 0 {
  1436  		st.fail("expected type")
  1437  	}
  1438  
  1439  	addSubst := true
  1440  
  1441  	q := st.cvQualifiers()
  1442  	if q != nil {
  1443  		if len(st.str) == 0 {
  1444  			st.fail("expected type")
  1445  		}
  1446  
  1447  		// CV-qualifiers before a function type apply to
  1448  		// 'this', so avoid adding the unqualified function
  1449  		// type to the substitution list.
  1450  		if st.str[0] == 'F' {
  1451  			addSubst = false
  1452  		}
  1453  	}
  1454  
  1455  	var ret AST
  1456  
  1457  	// Use correct substitution for a template parameter.
  1458  	var sub AST
  1459  
  1460  	if btype, ok := builtinTypes[st.str[0]]; ok {
  1461  		ret = &BuiltinType{Name: btype}
  1462  		st.advance(1)
  1463  		if q != nil {
  1464  			ret = &TypeWithQualifiers{Base: ret, Qualifiers: q}
  1465  			st.subs.add(ret)
  1466  		}
  1467  		return ret
  1468  	}
  1469  	c := st.str[0]
  1470  	switch c {
  1471  	case 'u':
  1472  		st.advance(1)
  1473  		ret = st.sourceName()
  1474  	case 'F':
  1475  		ret = st.functionType()
  1476  	case 'N', 'Z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
  1477  		ret = st.name()
  1478  	case 'A':
  1479  		ret = st.arrayType(isCast)
  1480  	case 'M':
  1481  		ret = st.pointerToMemberType(isCast)
  1482  	case 'T':
  1483  		if len(st.str) > 1 && (st.str[1] == 's' || st.str[1] == 'u' || st.str[1] == 'e') {
  1484  			c = st.str[1]
  1485  			st.advance(2)
  1486  			ret = st.name()
  1487  			var kind string
  1488  			switch c {
  1489  			case 's':
  1490  				kind = "struct"
  1491  			case 'u':
  1492  				kind = "union"
  1493  			case 'e':
  1494  				kind = "enum"
  1495  			}
  1496  			ret = &ElaboratedType{Kind: kind, Type: ret}
  1497  			break
  1498  		}
  1499  
  1500  		ret = st.templateParam()
  1501  		if len(st.str) > 0 && st.str[0] == 'I' {
  1502  			// See the function comment to explain this.
  1503  			if !isCast {
  1504  				st.subs.add(ret)
  1505  				args := st.templateArgs()
  1506  				ret = &Template{Name: ret, Args: args}
  1507  			} else {
  1508  				ret = st.demangleCastTemplateArgs(ret, true)
  1509  			}
  1510  		}
  1511  	case 'S':
  1512  		// If this is a special substitution, then it
  1513  		// is the start of <class-enum-type>.
  1514  		var c2 byte
  1515  		if len(st.str) > 1 {
  1516  			c2 = st.str[1]
  1517  		}
  1518  		if isDigit(c2) || c2 == '_' || isUpper(c2) {
  1519  			ret = st.substitution(false)
  1520  			if len(st.str) == 0 || st.str[0] != 'I' {
  1521  				addSubst = false
  1522  			} else {
  1523  				// See the function comment to explain this.
  1524  				if _, ok := ret.(*TemplateParam); !ok || !isCast {
  1525  					args := st.templateArgs()
  1526  					ret = &Template{Name: ret, Args: args}
  1527  				} else {
  1528  					next := st.demangleCastTemplateArgs(ret, false)
  1529  					if next == ret {
  1530  						addSubst = false
  1531  					}
  1532  					ret = next
  1533  				}
  1534  			}
  1535  		} else {
  1536  			ret = st.name()
  1537  			// This substitution is not itself a
  1538  			// substitution candidate, unless template
  1539  			// arguments were added.
  1540  			if ret == subAST[c2] || ret == verboseAST[c2] {
  1541  				addSubst = false
  1542  			}
  1543  		}
  1544  	case 'O', 'P', 'R', 'C', 'G':
  1545  		st.advance(1)
  1546  		t := st.demangleType(isCast)
  1547  		switch c {
  1548  		case 'O':
  1549  			ret = &RvalueReferenceType{Base: t}
  1550  		case 'P':
  1551  			ret = &PointerType{Base: t}
  1552  		case 'R':
  1553  			ret = &ReferenceType{Base: t}
  1554  		case 'C':
  1555  			ret = &ComplexType{Base: t}
  1556  		case 'G':
  1557  			ret = &ImaginaryType{Base: t}
  1558  		}
  1559  	case 'U':
  1560  		if len(st.str) < 2 {
  1561  			st.fail("expected source name or unnamed type")
  1562  		}
  1563  		switch st.str[1] {
  1564  		case 'l':
  1565  			ret = st.closureTypeName()
  1566  			addSubst = false
  1567  		case 't':
  1568  			ret = st.unnamedTypeName()
  1569  			addSubst = false
  1570  		default:
  1571  			st.advance(1)
  1572  			n := st.sourceName()
  1573  			if len(st.str) > 0 && st.str[0] == 'I' {
  1574  				args := st.templateArgs()
  1575  				n = &Template{Name: n, Args: args}
  1576  			}
  1577  			t := st.demangleType(isCast)
  1578  			ret = &VendorQualifier{Qualifier: n, Type: t}
  1579  		}
  1580  	case 'D':
  1581  		st.advance(1)
  1582  		if len(st.str) == 0 {
  1583  			st.fail("expected D code for type")
  1584  		}
  1585  		addSubst = false
  1586  		c2 := st.str[0]
  1587  		st.advance(1)
  1588  		switch c2 {
  1589  		case 'T', 't':
  1590  			// decltype(expression)
  1591  			ret = st.expression()
  1592  			if len(st.str) == 0 || st.str[0] != 'E' {
  1593  				st.fail("expected E after expression in type")
  1594  			}
  1595  			st.advance(1)
  1596  			ret = &Decltype{Expr: ret}
  1597  			addSubst = true
  1598  
  1599  		case 'p':
  1600  			t := st.demangleType(isCast)
  1601  			pack := st.findArgumentPack(t)
  1602  			ret = &PackExpansion{Base: t, Pack: pack}
  1603  			addSubst = true
  1604  
  1605  		case 'a':
  1606  			ret = &Name{Name: "auto"}
  1607  		case 'c':
  1608  			ret = &Name{Name: "decltype(auto)"}
  1609  
  1610  		case 'f':
  1611  			ret = &BuiltinType{Name: "decimal32"}
  1612  		case 'd':
  1613  			ret = &BuiltinType{Name: "decimal64"}
  1614  		case 'e':
  1615  			ret = &BuiltinType{Name: "decimal128"}
  1616  		case 'h':
  1617  			ret = &BuiltinType{Name: "half"}
  1618  		case 'u':
  1619  			ret = &BuiltinType{Name: "char8_t"}
  1620  		case 's':
  1621  			ret = &BuiltinType{Name: "char16_t"}
  1622  		case 'i':
  1623  			ret = &BuiltinType{Name: "char32_t"}
  1624  		case 'n':
  1625  			ret = &BuiltinType{Name: "decltype(nullptr)"}
  1626  
  1627  		case 'F':
  1628  			accum := false
  1629  			bits := 0
  1630  			if len(st.str) > 0 && isDigit(st.str[0]) {
  1631  				accum = true
  1632  				bits = st.number()
  1633  			}
  1634  			if len(st.str) > 0 && st.str[0] == '_' {
  1635  				if bits == 0 {
  1636  					st.fail("expected non-zero number of bits")
  1637  				}
  1638  				st.advance(1)
  1639  				ret = &BinaryFP{Bits: bits}
  1640  			} else {
  1641  				base := st.demangleType(isCast)
  1642  				if len(st.str) > 0 && isDigit(st.str[0]) {
  1643  					// We don't care about the bits.
  1644  					st.number()
  1645  				}
  1646  				sat := false
  1647  				if len(st.str) > 0 {
  1648  					if st.str[0] == 's' {
  1649  						sat = true
  1650  					}
  1651  					st.advance(1)
  1652  				}
  1653  				ret = &FixedType{Base: base, Accum: accum, Sat: sat}
  1654  			}
  1655  
  1656  		case 'v':
  1657  			ret = st.vectorType(isCast)
  1658  			addSubst = true
  1659  
  1660  		default:
  1661  			st.fail("unrecognized D code in type")
  1662  		}
  1663  
  1664  	default:
  1665  		st.fail("unrecognized type code")
  1666  	}
  1667  
  1668  	if addSubst {
  1669  		if sub != nil {
  1670  			st.subs.add(sub)
  1671  		} else {
  1672  			st.subs.add(ret)
  1673  		}
  1674  	}
  1675  
  1676  	if q != nil {
  1677  		if _, ok := ret.(*FunctionType); ok {
  1678  			ret = &MethodWithQualifiers{Method: ret, Qualifiers: q, RefQualifier: ""}
  1679  		} else if mwq, ok := ret.(*MethodWithQualifiers); ok {
  1680  			// Merge adjacent qualifiers.  This case
  1681  			// happens with a function with a trailing
  1682  			// ref-qualifier.
  1683  			mwq.Qualifiers = mergeQualifiers(q, mwq.Qualifiers)
  1684  		} else {
  1685  			// Merge adjacent qualifiers.  This case
  1686  			// happens with multi-dimensional array types.
  1687  			if qsub, ok := ret.(*TypeWithQualifiers); ok {
  1688  				q = mergeQualifiers(q, qsub.Qualifiers)
  1689  				ret = qsub.Base
  1690  			}
  1691  			ret = &TypeWithQualifiers{Base: ret, Qualifiers: q}
  1692  		}
  1693  		st.subs.add(ret)
  1694  	}
  1695  
  1696  	return ret
  1697  }
  1698  
  1699  // demangleCastTemplateArgs is for a rather hideous parse.  When we
  1700  // see a template-param followed by a template-args, we need to decide
  1701  // whether we have a template-param or a template-template-param.
  1702  // Normally it is template-template-param, meaning that we pick up the
  1703  // template arguments here.  But, if we are parsing the type for a
  1704  // cast operator, then the only way this can be template-template-param
  1705  // is if there is another set of template-args immediately after this
  1706  // set.  That would look like this:
  1707  //
  1708  //	<nested-name>
  1709  //	-> <template-prefix> <template-args>
  1710  //	-> <prefix> <template-unqualified-name> <template-args>
  1711  //	-> <unqualified-name> <template-unqualified-name> <template-args>
  1712  //	-> <source-name> <template-unqualified-name> <template-args>
  1713  //	-> <source-name> <operator-name> <template-args>
  1714  //	-> <source-name> cv <type> <template-args>
  1715  //	-> <source-name> cv <template-template-param> <template-args> <template-args>
  1716  //
  1717  // Otherwise, we have this derivation:
  1718  //
  1719  //	<nested-name>
  1720  //	-> <template-prefix> <template-args>
  1721  //	-> <prefix> <template-unqualified-name> <template-args>
  1722  //	-> <unqualified-name> <template-unqualified-name> <template-args>
  1723  //	-> <source-name> <template-unqualified-name> <template-args>
  1724  //	-> <source-name> <operator-name> <template-args>
  1725  //	-> <source-name> cv <type> <template-args>
  1726  //	-> <source-name> cv <template-param> <template-args>
  1727  //
  1728  // in which the template-args are actually part of the prefix.  For
  1729  // the special case where this arises, demangleType is called with
  1730  // isCast as true.  This function is then responsible for checking
  1731  // whether we see <template-param> <template-args> but there is not
  1732  // another following <template-args>.  In that case, we reset the
  1733  // parse and just return the <template-param>.
  1734  func (st *state) demangleCastTemplateArgs(tp AST, addSubst bool) AST {
  1735  	save := st.copy()
  1736  
  1737  	var args []AST
  1738  	failed := false
  1739  	func() {
  1740  		defer func() {
  1741  			if r := recover(); r != nil {
  1742  				if _, ok := r.(demangleErr); ok {
  1743  					failed = true
  1744  				} else {
  1745  					panic(r)
  1746  				}
  1747  			}
  1748  		}()
  1749  
  1750  		args = st.templateArgs()
  1751  	}()
  1752  
  1753  	if !failed && len(st.str) > 0 && st.str[0] == 'I' {
  1754  		if addSubst {
  1755  			st.subs.add(tp)
  1756  		}
  1757  		return &Template{Name: tp, Args: args}
  1758  	}
  1759  	// Reset back to before we started reading the template arguments.
  1760  	// They will be read again by st.prefix.
  1761  	*st = *save
  1762  	return tp
  1763  }
  1764  
  1765  // mergeQualifiers merges two qualifier lists into one.
  1766  func mergeQualifiers(q1AST, q2AST AST) AST {
  1767  	if q1AST == nil {
  1768  		return q2AST
  1769  	}
  1770  	if q2AST == nil {
  1771  		return q1AST
  1772  	}
  1773  	q1 := q1AST.(*Qualifiers)
  1774  	m := make(map[string]bool)
  1775  	for _, qualAST := range q1.Qualifiers {
  1776  		qual := qualAST.(*Qualifier)
  1777  		if len(qual.Exprs) == 0 {
  1778  			m[qual.Name] = true
  1779  		}
  1780  	}
  1781  	rq := q1.Qualifiers
  1782  	for _, qualAST := range q2AST.(*Qualifiers).Qualifiers {
  1783  		qual := qualAST.(*Qualifier)
  1784  		if len(qual.Exprs) > 0 {
  1785  			rq = append(rq, qualAST)
  1786  		} else if !m[qual.Name] {
  1787  			rq = append(rq, qualAST)
  1788  			m[qual.Name] = true
  1789  		}
  1790  	}
  1791  	q1.Qualifiers = rq
  1792  	return q1
  1793  }
  1794  
  1795  // qualifiers maps from the character used in the mangled name to the
  1796  // string to print.
  1797  var qualifiers = map[byte]string{
  1798  	'r': "restrict",
  1799  	'V': "volatile",
  1800  	'K': "const",
  1801  }
  1802  
  1803  // cvQualifiers parses:
  1804  //
  1805  //	<CV-qualifiers> ::= [r] [V] [K]
  1806  func (st *state) cvQualifiers() AST {
  1807  	var q []AST
  1808  qualLoop:
  1809  	for len(st.str) > 0 {
  1810  		if qv, ok := qualifiers[st.str[0]]; ok {
  1811  			qual := &Qualifier{Name: qv}
  1812  			q = append([]AST{qual}, q...)
  1813  			st.advance(1)
  1814  		} else if len(st.str) > 1 && st.str[0] == 'D' {
  1815  			var qual AST
  1816  			switch st.str[1] {
  1817  			case 'x':
  1818  				qual = &Qualifier{Name: "transaction_safe"}
  1819  				st.advance(2)
  1820  			case 'o':
  1821  				qual = &Qualifier{Name: "noexcept"}
  1822  				st.advance(2)
  1823  			case 'O':
  1824  				st.advance(2)
  1825  				expr := st.expression()
  1826  				if len(st.str) == 0 || st.str[0] != 'E' {
  1827  					st.fail("expected E after computed noexcept expression")
  1828  				}
  1829  				st.advance(1)
  1830  				qual = &Qualifier{Name: "noexcept", Exprs: []AST{expr}}
  1831  			case 'w':
  1832  				st.advance(2)
  1833  				parmlist := st.parmlist()
  1834  				if len(st.str) == 0 || st.str[0] != 'E' {
  1835  					st.fail("expected E after throw parameter list")
  1836  				}
  1837  				st.advance(1)
  1838  				qual = &Qualifier{Name: "throw", Exprs: parmlist}
  1839  			default:
  1840  				break qualLoop
  1841  			}
  1842  			q = append([]AST{qual}, q...)
  1843  		} else {
  1844  			break
  1845  		}
  1846  	}
  1847  	if len(q) == 0 {
  1848  		return nil
  1849  	}
  1850  	return &Qualifiers{Qualifiers: q}
  1851  }
  1852  
  1853  // refQualifier parses:
  1854  //
  1855  //	<ref-qualifier> ::= R
  1856  //	                ::= O
  1857  func (st *state) refQualifier() string {
  1858  	if len(st.str) > 0 {
  1859  		switch st.str[0] {
  1860  		case 'R':
  1861  			st.advance(1)
  1862  			return "&"
  1863  		case 'O':
  1864  			st.advance(1)
  1865  			return "&&"
  1866  		}
  1867  	}
  1868  	return ""
  1869  }
  1870  
  1871  // parmlist parses:
  1872  //
  1873  //	<type>+
  1874  func (st *state) parmlist() []AST {
  1875  	var ret []AST
  1876  	for {
  1877  		if len(st.str) < 1 {
  1878  			break
  1879  		}
  1880  		if st.str[0] == 'E' || st.str[0] == '.' {
  1881  			break
  1882  		}
  1883  		if (st.str[0] == 'R' || st.str[0] == 'O') && len(st.str) > 1 && st.str[1] == 'E' {
  1884  			// This is a function ref-qualifier.
  1885  			break
  1886  		}
  1887  		ptype := st.demangleType(false)
  1888  		ret = append(ret, ptype)
  1889  	}
  1890  
  1891  	// There should always be at least one type.  A function that
  1892  	// takes no arguments will have a single parameter type
  1893  	// "void".
  1894  	if len(ret) == 0 {
  1895  		st.fail("expected at least one type in type list")
  1896  	}
  1897  
  1898  	// Omit a single parameter type void.
  1899  	if len(ret) == 1 {
  1900  		if bt, ok := ret[0].(*BuiltinType); ok && bt.Name == "void" {
  1901  			ret = nil
  1902  		}
  1903  	}
  1904  
  1905  	return ret
  1906  }
  1907  
  1908  // functionType parses:
  1909  //
  1910  //	<function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E
  1911  func (st *state) functionType() AST {
  1912  	st.checkChar('F')
  1913  	if len(st.str) > 0 && st.str[0] == 'Y' {
  1914  		// Function has C linkage.  We don't print this.
  1915  		st.advance(1)
  1916  	}
  1917  	ret := st.bareFunctionType(true)
  1918  	r := st.refQualifier()
  1919  	if r != "" {
  1920  		ret = &MethodWithQualifiers{Method: ret, Qualifiers: nil, RefQualifier: r}
  1921  	}
  1922  	if len(st.str) == 0 || st.str[0] != 'E' {
  1923  		st.fail("expected E after function type")
  1924  	}
  1925  	st.advance(1)
  1926  	return ret
  1927  }
  1928  
  1929  // bareFunctionType parses:
  1930  //
  1931  //	<bare-function-type> ::= [J]<type>+
  1932  func (st *state) bareFunctionType(hasReturnType bool) AST {
  1933  	if len(st.str) > 0 && st.str[0] == 'J' {
  1934  		hasReturnType = true
  1935  		st.advance(1)
  1936  	}
  1937  	var returnType AST
  1938  	if hasReturnType {
  1939  		returnType = st.demangleType(false)
  1940  	}
  1941  	types := st.parmlist()
  1942  	return &FunctionType{
  1943  		Return:       returnType,
  1944  		Args:         types,
  1945  		ForLocalName: false, // may be set later in encoding
  1946  	}
  1947  }
  1948  
  1949  // arrayType parses:
  1950  //
  1951  //	<array-type> ::= A <(positive dimension) number> _ <(element) type>
  1952  //	             ::= A [<(dimension) expression>] _ <(element) type>
  1953  func (st *state) arrayType(isCast bool) AST {
  1954  	st.checkChar('A')
  1955  
  1956  	if len(st.str) == 0 {
  1957  		st.fail("missing array dimension")
  1958  	}
  1959  
  1960  	var dim AST
  1961  	if st.str[0] == '_' {
  1962  		dim = &Name{Name: ""}
  1963  	} else if isDigit(st.str[0]) {
  1964  		i := 1
  1965  		for len(st.str) > i && isDigit(st.str[i]) {
  1966  			i++
  1967  		}
  1968  		dim = &Name{Name: st.str[:i]}
  1969  		st.advance(i)
  1970  	} else {
  1971  		dim = st.expression()
  1972  	}
  1973  
  1974  	if len(st.str) == 0 || st.str[0] != '_' {
  1975  		st.fail("expected _ after dimension")
  1976  	}
  1977  	st.advance(1)
  1978  
  1979  	t := st.demangleType(isCast)
  1980  
  1981  	arr := &ArrayType{Dimension: dim, Element: t}
  1982  
  1983  	// Qualifiers on the element of an array type go on the whole
  1984  	// array type.
  1985  	if q, ok := arr.Element.(*TypeWithQualifiers); ok {
  1986  		return &TypeWithQualifiers{Base: &ArrayType{Dimension: dim, Element: q.Base}, Qualifiers: q.Qualifiers}
  1987  	}
  1988  
  1989  	return arr
  1990  }
  1991  
  1992  // vectorType parses:
  1993  //
  1994  //	<vector-type> ::= Dv <number> _ <type>
  1995  //	              ::= Dv _ <expression> _ <type>
  1996  func (st *state) vectorType(isCast bool) AST {
  1997  	if len(st.str) == 0 {
  1998  		st.fail("expected vector dimension")
  1999  	}
  2000  
  2001  	var dim AST
  2002  	if st.str[0] == '_' {
  2003  		st.advance(1)
  2004  		dim = st.expression()
  2005  	} else {
  2006  		num := st.number()
  2007  		dim = &Name{Name: fmt.Sprintf("%d", num)}
  2008  	}
  2009  
  2010  	if len(st.str) == 0 || st.str[0] != '_' {
  2011  		st.fail("expected _ after vector dimension")
  2012  	}
  2013  	st.advance(1)
  2014  
  2015  	t := st.demangleType(isCast)
  2016  
  2017  	return &VectorType{Dimension: dim, Base: t}
  2018  }
  2019  
  2020  // pointerToMemberType parses:
  2021  //
  2022  //	<pointer-to-member-type> ::= M <(class) type> <(member) type>
  2023  func (st *state) pointerToMemberType(isCast bool) AST {
  2024  	st.checkChar('M')
  2025  	cl := st.demangleType(false)
  2026  
  2027  	// The ABI says, "The type of a non-static member function is
  2028  	// considered to be different, for the purposes of
  2029  	// substitution, from the type of a namespace-scope or static
  2030  	// member function whose type appears similar. The types of
  2031  	// two non-static member functions are considered to be
  2032  	// different, for the purposes of substitution, if the
  2033  	// functions are members of different classes. In other words,
  2034  	// for the purposes of substitution, the class of which the
  2035  	// function is a member is considered part of the type of
  2036  	// function."
  2037  	//
  2038  	// For a pointer to member function, this call to demangleType
  2039  	// will end up adding a (possibly qualified) non-member
  2040  	// function type to the substitution table, which is not
  2041  	// correct; however, the member function type will never be
  2042  	// used in a substitution, so putting the wrong type in the
  2043  	// substitution table is harmless.
  2044  	mem := st.demangleType(isCast)
  2045  	return &PtrMem{Class: cl, Member: mem}
  2046  }
  2047  
  2048  // compactNumber parses:
  2049  //
  2050  //	<non-negative number> _
  2051  func (st *state) compactNumber() int {
  2052  	if len(st.str) == 0 {
  2053  		st.fail("missing index")
  2054  	}
  2055  	if st.str[0] == '_' {
  2056  		st.advance(1)
  2057  		return 0
  2058  	} else if st.str[0] == 'n' {
  2059  		st.fail("unexpected negative number")
  2060  	}
  2061  	n := st.number()
  2062  	if len(st.str) == 0 || st.str[0] != '_' {
  2063  		st.fail("missing underscore after number")
  2064  	}
  2065  	st.advance(1)
  2066  	return n + 1
  2067  }
  2068  
  2069  // templateParam parses:
  2070  //
  2071  //	<template-param> ::= T_
  2072  //	                 ::= T <(parameter-2 non-negative) number> _
  2073  //	                 ::= TL <level-1> __
  2074  //	                 ::= TL <level-1> _ <parameter-2 non-negative number> _
  2075  //
  2076  // When a template parameter is a substitution candidate, any
  2077  // reference to that substitution refers to the template parameter
  2078  // with the same index in the currently active template, not to
  2079  // whatever the template parameter would be expanded to here.  We sort
  2080  // this out in substitution and simplify.
  2081  func (st *state) templateParam() AST {
  2082  	off := st.off
  2083  	st.checkChar('T')
  2084  
  2085  	level := 0
  2086  	if len(st.str) > 0 && st.str[0] == 'L' {
  2087  		st.advance(1)
  2088  		level = st.compactNumber()
  2089  	}
  2090  
  2091  	n := st.compactNumber()
  2092  
  2093  	if level >= len(st.templates) {
  2094  		if st.lambdaTemplateLevel > 0 && level == st.lambdaTemplateLevel-1 {
  2095  			// Lambda auto params are mangled as template params.
  2096  			// See https://gcc.gnu.org/PR78252.
  2097  			return &LambdaAuto{Index: n}
  2098  		}
  2099  		st.failEarlier(fmt.Sprintf("template parameter is not in scope of template (level %d >= %d)", level, len(st.templates)), st.off-off)
  2100  	}
  2101  
  2102  	template := st.templates[level]
  2103  
  2104  	if template == nil {
  2105  		// We are parsing a cast operator.  If the cast is
  2106  		// itself a template, then this is a forward
  2107  		// reference.  Fill it in later.
  2108  		return &TemplateParam{Index: n, Template: nil}
  2109  	}
  2110  
  2111  	if n >= len(template.Args) {
  2112  		if st.lambdaTemplateLevel > 0 && level == st.lambdaTemplateLevel-1 {
  2113  			// Lambda auto params are mangled as template params.
  2114  			// See https://gcc.gnu.org/PR78252.
  2115  			return &LambdaAuto{Index: n}
  2116  		}
  2117  		st.failEarlier(fmt.Sprintf("template index out of range (%d >= %d)", n, len(template.Args)), st.off-off)
  2118  	}
  2119  
  2120  	return &TemplateParam{Index: n, Template: template}
  2121  }
  2122  
  2123  // setTemplate sets the Template field of any TemplateParam's in a.
  2124  // This handles the forward referencing template parameters found in
  2125  // cast operators.
  2126  func (st *state) setTemplate(a AST, tmpl *Template) {
  2127  	var seen []AST
  2128  	a.Traverse(func(a AST) bool {
  2129  		switch a := a.(type) {
  2130  		case *TemplateParam:
  2131  			if a.Template != nil {
  2132  				if tmpl != nil {
  2133  					st.fail("duplicate template parameters")
  2134  				}
  2135  				return false
  2136  			}
  2137  			if tmpl == nil {
  2138  				st.fail("cast template parameter not in scope of template")
  2139  			}
  2140  			if a.Index >= len(tmpl.Args) {
  2141  				st.fail(fmt.Sprintf("cast template index out of range (%d >= %d)", a.Index, len(tmpl.Args)))
  2142  			}
  2143  			a.Template = tmpl
  2144  			return false
  2145  		case *Closure:
  2146  			// There are no template params in closure types.
  2147  			// https://gcc.gnu.org/PR78252.
  2148  			return false
  2149  		default:
  2150  			for _, v := range seen {
  2151  				if v == a {
  2152  					return false
  2153  				}
  2154  			}
  2155  			seen = append(seen, a)
  2156  			return true
  2157  		}
  2158  	})
  2159  }
  2160  
  2161  // clearTemplateArgs gives an error for any unset Template field in
  2162  // args.  This handles erroneous cases where a cast operator with a
  2163  // forward referenced template is in the scope of another cast
  2164  // operator.
  2165  func (st *state) clearTemplateArgs(args []AST) {
  2166  	for _, a := range args {
  2167  		st.setTemplate(a, nil)
  2168  	}
  2169  }
  2170  
  2171  // templateArgs parses:
  2172  //
  2173  //	<template-args> ::= I <template-arg>+ E
  2174  func (st *state) templateArgs() []AST {
  2175  	if len(st.str) == 0 || (st.str[0] != 'I' && st.str[0] != 'J') {
  2176  		panic("internal error")
  2177  	}
  2178  	st.advance(1)
  2179  
  2180  	var ret []AST
  2181  	for len(st.str) == 0 || st.str[0] != 'E' {
  2182  		arg := st.templateArg()
  2183  		ret = append(ret, arg)
  2184  	}
  2185  	st.advance(1)
  2186  	return ret
  2187  }
  2188  
  2189  // templateArg parses:
  2190  //
  2191  //	<template-arg> ::= <type>
  2192  //	               ::= X <expression> E
  2193  //	               ::= <expr-primary>
  2194  func (st *state) templateArg() AST {
  2195  	if len(st.str) == 0 {
  2196  		st.fail("missing template argument")
  2197  	}
  2198  	switch st.str[0] {
  2199  	case 'X':
  2200  		st.advance(1)
  2201  		expr := st.expression()
  2202  		if len(st.str) == 0 || st.str[0] != 'E' {
  2203  			st.fail("missing end of expression")
  2204  		}
  2205  		st.advance(1)
  2206  		return expr
  2207  
  2208  	case 'L':
  2209  		return st.exprPrimary()
  2210  
  2211  	case 'I', 'J':
  2212  		args := st.templateArgs()
  2213  		return &ArgumentPack{Args: args}
  2214  
  2215  	default:
  2216  		return st.demangleType(false)
  2217  	}
  2218  }
  2219  
  2220  // exprList parses a sequence of expressions up to a terminating character.
  2221  func (st *state) exprList(stop byte) AST {
  2222  	if len(st.str) > 0 && st.str[0] == stop {
  2223  		st.advance(1)
  2224  		return &ExprList{Exprs: nil}
  2225  	}
  2226  
  2227  	var exprs []AST
  2228  	for {
  2229  		e := st.expression()
  2230  		exprs = append(exprs, e)
  2231  		if len(st.str) > 0 && st.str[0] == stop {
  2232  			st.advance(1)
  2233  			break
  2234  		}
  2235  	}
  2236  	return &ExprList{Exprs: exprs}
  2237  }
  2238  
  2239  // expression parses:
  2240  //
  2241  //	<expression> ::= <(unary) operator-name> <expression>
  2242  //	             ::= <(binary) operator-name> <expression> <expression>
  2243  //	             ::= <(trinary) operator-name> <expression> <expression> <expression>
  2244  //	             ::= pp_ <expression>
  2245  //	             ::= mm_ <expression>
  2246  //	             ::= cl <expression>+ E
  2247  //	             ::= cl <expression>+ E
  2248  //	             ::= cv <type> <expression>
  2249  //	             ::= cv <type> _ <expression>* E
  2250  //	             ::= tl <type> <braced-expression>* E
  2251  //	             ::= il <braced-expression>* E
  2252  //	             ::= [gs] nw <expression>* _ <type> E
  2253  //	             ::= [gs] nw <expression>* _ <type> <initializer>
  2254  //	             ::= [gs] na <expression>* _ <type> E
  2255  //	             ::= [gs] na <expression>* _ <type> <initializer>
  2256  //	             ::= [gs] dl <expression>
  2257  //	             ::= [gs] da <expression>
  2258  //	             ::= dc <type> <expression>
  2259  //	             ::= sc <type> <expression>
  2260  //	             ::= cc <type> <expression>
  2261  //	             ::= mc <parameter type> <expr> [<offset number>] E
  2262  //	             ::= rc <type> <expression>
  2263  //	             ::= ti <type>
  2264  //	             ::= te <expression>
  2265  //	             ::= so <referent type> <expr> [<offset number>] <union-selector>* [p] E
  2266  //	             ::= st <type>
  2267  //	             ::= sz <expression>
  2268  //	             ::= at <type>
  2269  //	             ::= az <expression>
  2270  //	             ::= nx <expression>
  2271  //	             ::= <template-param>
  2272  //	             ::= <function-param>
  2273  //	             ::= dt <expression> <unresolved-name>
  2274  //	             ::= pt <expression> <unresolved-name>
  2275  //	             ::= ds <expression> <expression>
  2276  //	             ::= sZ <template-param>
  2277  //	             ::= sZ <function-param>
  2278  //	             ::= sP <template-arg>* E
  2279  //	             ::= sp <expression>
  2280  //	             ::= fl <binary operator-name> <expression>
  2281  //	             ::= fr <binary operator-name> <expression>
  2282  //	             ::= fL <binary operator-name> <expression> <expression>
  2283  //	             ::= fR <binary operator-name> <expression> <expression>
  2284  //	             ::= tw <expression>
  2285  //	             ::= tr
  2286  //	             ::= u <source-name> <template-arg>* E
  2287  //	             ::= <unresolved-name>
  2288  //	             ::= <expr-primary>
  2289  //
  2290  //	<function-param> ::= fp <CV-qualifiers> _
  2291  //	                 ::= fp <CV-qualifiers> <number>
  2292  //	                 ::= fL <number> p <CV-qualifiers> _
  2293  //	                 ::= fL <number> p <CV-qualifiers> <number>
  2294  //	                 ::= fpT
  2295  //
  2296  //	<braced-expression> ::= <expression>
  2297  //	                    ::= di <field source-name> <braced-expression>
  2298  //	                    ::= dx <index expression> <braced-expression>
  2299  //	                    ::= dX <range begin expression> <range end expression> <braced-expression>
  2300  func (st *state) expression() AST {
  2301  	if len(st.str) == 0 {
  2302  		st.fail("expected expression")
  2303  	}
  2304  	if st.str[0] == 'L' {
  2305  		return st.exprPrimary()
  2306  	} else if st.str[0] == 'T' {
  2307  		return st.templateParam()
  2308  	} else if st.str[0] == 's' && len(st.str) > 1 && st.str[1] == 'o' {
  2309  		st.advance(2)
  2310  		return st.subobject()
  2311  	} else if st.str[0] == 's' && len(st.str) > 1 && st.str[1] == 'r' {
  2312  		return st.unresolvedName()
  2313  	} else if st.str[0] == 's' && len(st.str) > 1 && st.str[1] == 'p' {
  2314  		st.advance(2)
  2315  		e := st.expression()
  2316  		pack := st.findArgumentPack(e)
  2317  		return &PackExpansion{Base: e, Pack: pack}
  2318  	} else if st.str[0] == 's' && len(st.str) > 1 && st.str[1] == 'Z' {
  2319  		st.advance(2)
  2320  		off := st.off
  2321  		e := st.expression()
  2322  		ap := st.findArgumentPack(e)
  2323  		if ap == nil {
  2324  			st.failEarlier("missing argument pack", st.off-off)
  2325  		}
  2326  		return &SizeofPack{Pack: ap}
  2327  	} else if st.str[0] == 's' && len(st.str) > 1 && st.str[1] == 'P' {
  2328  		st.advance(2)
  2329  		var args []AST
  2330  		for len(st.str) == 0 || st.str[0] != 'E' {
  2331  			arg := st.templateArg()
  2332  			args = append(args, arg)
  2333  		}
  2334  		st.advance(1)
  2335  		return &SizeofArgs{Args: args}
  2336  	} else if st.str[0] == 'f' && len(st.str) > 1 && st.str[1] == 'p' {
  2337  		st.advance(2)
  2338  		if len(st.str) > 0 && st.str[0] == 'T' {
  2339  			st.advance(1)
  2340  			return &FunctionParam{Index: 0}
  2341  		} else {
  2342  			// We can see qualifiers here, but we don't
  2343  			// include them in the demangled string.
  2344  			st.cvQualifiers()
  2345  			index := st.compactNumber()
  2346  			return &FunctionParam{Index: index + 1}
  2347  		}
  2348  	} else if st.str[0] == 'f' && len(st.str) > 2 && st.str[1] == 'L' && isDigit(st.str[2]) {
  2349  		st.advance(2)
  2350  		// We don't include the scope count in the demangled string.
  2351  		st.number()
  2352  		if len(st.str) == 0 || st.str[0] != 'p' {
  2353  			st.fail("expected p after function parameter scope count")
  2354  		}
  2355  		st.advance(1)
  2356  		// We can see qualifiers here, but we don't include them
  2357  		// in the demangled string.
  2358  		st.cvQualifiers()
  2359  		index := st.compactNumber()
  2360  		return &FunctionParam{Index: index + 1}
  2361  	} else if st.str[0] == 'm' && len(st.str) > 1 && st.str[1] == 'c' {
  2362  		st.advance(2)
  2363  		typ := st.demangleType(false)
  2364  		expr := st.expression()
  2365  		offset := 0
  2366  		if len(st.str) > 0 && (st.str[0] == 'n' || isDigit(st.str[0])) {
  2367  			offset = st.number()
  2368  		}
  2369  		if len(st.str) == 0 || st.str[0] != 'E' {
  2370  			st.fail("expected E after pointer-to-member conversion")
  2371  		}
  2372  		st.advance(1)
  2373  		return &PtrMemCast{
  2374  			Type:   typ,
  2375  			Expr:   expr,
  2376  			Offset: offset,
  2377  		}
  2378  	} else if isDigit(st.str[0]) || (st.str[0] == 'o' && len(st.str) > 1 && st.str[1] == 'n') {
  2379  		if st.str[0] == 'o' {
  2380  			// Skip operator function ID.
  2381  			st.advance(2)
  2382  		}
  2383  		n, _ := st.unqualifiedName()
  2384  		if len(st.str) > 0 && st.str[0] == 'I' {
  2385  			args := st.templateArgs()
  2386  			n = &Template{Name: n, Args: args}
  2387  		}
  2388  		return n
  2389  	} else if (st.str[0] == 'i' || st.str[0] == 't') && len(st.str) > 1 && st.str[1] == 'l' {
  2390  		// Brace-enclosed initializer list.
  2391  		c := st.str[0]
  2392  		st.advance(2)
  2393  		var t AST
  2394  		if c == 't' {
  2395  			t = st.demangleType(false)
  2396  		}
  2397  		exprs := st.exprList('E')
  2398  		return &InitializerList{Type: t, Exprs: exprs}
  2399  	} else if st.str[0] == 's' && len(st.str) > 1 && st.str[1] == 't' {
  2400  		o, _ := st.operatorName(true)
  2401  		t := st.demangleType(false)
  2402  		return &Unary{Op: o, Expr: t, Suffix: false, SizeofType: true}
  2403  	} else if st.str[0] == 'u' {
  2404  		st.advance(1)
  2405  		name := st.sourceName()
  2406  		// Special case __uuidof followed by type or
  2407  		// expression, as used by LLVM.
  2408  		if n, ok := name.(*Name); ok && n.Name == "__uuidof" {
  2409  			if len(st.str) < 2 {
  2410  				st.fail("missing uuidof argument")
  2411  			}
  2412  			var operand AST
  2413  			if st.str[0] == 't' {
  2414  				st.advance(1)
  2415  				operand = st.demangleType(false)
  2416  			} else if st.str[0] == 'z' {
  2417  				st.advance(1)
  2418  				operand = st.expression()
  2419  			}
  2420  			if operand != nil {
  2421  				return &Binary{
  2422  					Op:   &Operator{Name: "()"},
  2423  					Left: name,
  2424  					Right: &ExprList{
  2425  						Exprs: []AST{operand},
  2426  					},
  2427  				}
  2428  			}
  2429  		}
  2430  		var args []AST
  2431  		for {
  2432  			if len(st.str) == 0 {
  2433  				st.fail("missing argument in vendor extended expressoin")
  2434  			}
  2435  			if st.str[0] == 'E' {
  2436  				st.advance(1)
  2437  				break
  2438  			}
  2439  			arg := st.templateArg()
  2440  			args = append(args, arg)
  2441  		}
  2442  		return &Binary{
  2443  			Op:    &Operator{Name: "()"},
  2444  			Left:  name,
  2445  			Right: &ExprList{Exprs: args},
  2446  		}
  2447  	} else {
  2448  		if len(st.str) < 2 {
  2449  			st.fail("missing operator code")
  2450  		}
  2451  		code := st.str[:2]
  2452  		o, args := st.operatorName(true)
  2453  		switch args {
  2454  		case 0:
  2455  			return &Nullary{Op: o}
  2456  
  2457  		case 1:
  2458  			suffix := false
  2459  			if code == "pp" || code == "mm" {
  2460  				if len(st.str) > 0 && st.str[0] == '_' {
  2461  					st.advance(1)
  2462  				} else {
  2463  					suffix = true
  2464  				}
  2465  			}
  2466  			var operand AST
  2467  			if _, ok := o.(*Cast); ok && len(st.str) > 0 && st.str[0] == '_' {
  2468  				st.advance(1)
  2469  				operand = st.exprList('E')
  2470  			} else {
  2471  				operand = st.expression()
  2472  			}
  2473  			return &Unary{Op: o, Expr: operand, Suffix: suffix, SizeofType: false}
  2474  
  2475  		case 2:
  2476  			var left, right AST
  2477  			if code == "sc" || code == "dc" || code == "cc" || code == "rc" {
  2478  				left = st.demangleType(false)
  2479  			} else if code[0] == 'f' {
  2480  				left, _ = st.operatorName(true)
  2481  				right = st.expression()
  2482  				return &Fold{Left: code[1] == 'l', Op: left, Arg1: right, Arg2: nil}
  2483  			} else if code == "di" {
  2484  				left, _ = st.unqualifiedName()
  2485  			} else {
  2486  				left = st.expression()
  2487  			}
  2488  			if code == "cl" || code == "cp" {
  2489  				right = st.exprList('E')
  2490  			} else if code == "dt" || code == "pt" {
  2491  				right = st.unresolvedName()
  2492  				if len(st.str) > 0 && st.str[0] == 'I' {
  2493  					args := st.templateArgs()
  2494  					right = &Template{Name: right, Args: args}
  2495  				}
  2496  			} else {
  2497  				right = st.expression()
  2498  			}
  2499  			return &Binary{Op: o, Left: left, Right: right}
  2500  
  2501  		case 3:
  2502  			if code[0] == 'n' {
  2503  				if code[1] != 'w' && code[1] != 'a' {
  2504  					panic("internal error")
  2505  				}
  2506  				place := st.exprList('_')
  2507  				if place.(*ExprList).Exprs == nil {
  2508  					place = nil
  2509  				}
  2510  				t := st.demangleType(false)
  2511  				var ini AST
  2512  				if len(st.str) > 0 && st.str[0] == 'E' {
  2513  					st.advance(1)
  2514  				} else if len(st.str) > 1 && st.str[0] == 'p' && st.str[1] == 'i' {
  2515  					// Parenthesized initializer.
  2516  					st.advance(2)
  2517  					ini = st.exprList('E')
  2518  				} else if len(st.str) > 1 && st.str[0] == 'i' && st.str[1] == 'l' {
  2519  					// Initializer list.
  2520  					ini = st.expression()
  2521  				} else {
  2522  					st.fail("unrecognized new initializer")
  2523  				}
  2524  				return &New{Op: o, Place: place, Type: t, Init: ini}
  2525  			} else if code[0] == 'f' {
  2526  				first, _ := st.operatorName(true)
  2527  				second := st.expression()
  2528  				third := st.expression()
  2529  				return &Fold{Left: code[1] == 'L', Op: first, Arg1: second, Arg2: third}
  2530  			} else {
  2531  				first := st.expression()
  2532  				second := st.expression()
  2533  				third := st.expression()
  2534  				return &Trinary{Op: o, First: first, Second: second, Third: third}
  2535  			}
  2536  
  2537  		default:
  2538  			st.fail(fmt.Sprintf("unsupported number of operator arguments: %d", args))
  2539  			panic("not reached")
  2540  		}
  2541  	}
  2542  }
  2543  
  2544  // subobject parses:
  2545  //
  2546  //	<expression> ::= so <referent type> <expr> [<offset number>] <union-selector>* [p] E
  2547  //	<union-selector> ::= _ [<number>]
  2548  func (st *state) subobject() AST {
  2549  	typ := st.demangleType(false)
  2550  	expr := st.expression()
  2551  	offset := 0
  2552  	if len(st.str) > 0 && (st.str[0] == 'n' || isDigit(st.str[0])) {
  2553  		offset = st.number()
  2554  	}
  2555  	var selectors []int
  2556  	for len(st.str) > 0 && st.str[0] == '_' {
  2557  		st.advance(1)
  2558  		selector := 0
  2559  		if len(st.str) > 0 && (st.str[0] == 'n' || isDigit(st.str[0])) {
  2560  			selector = st.number()
  2561  		}
  2562  		selectors = append(selectors, selector)
  2563  	}
  2564  	pastEnd := false
  2565  	if len(st.str) > 0 && st.str[0] == 'p' {
  2566  		st.advance(1)
  2567  		pastEnd = true
  2568  	}
  2569  	if len(st.str) == 0 || st.str[0] != 'E' {
  2570  		st.fail("expected E after subobject")
  2571  	}
  2572  	st.advance(1)
  2573  	return &Subobject{
  2574  		Type:      typ,
  2575  		SubExpr:   expr,
  2576  		Offset:    offset,
  2577  		Selectors: selectors,
  2578  		PastEnd:   pastEnd,
  2579  	}
  2580  }
  2581  
  2582  // unresolvedName parses:
  2583  //
  2584  //	<unresolved-name> ::= [gs] <base-unresolved-name>
  2585  //	                  ::= sr <unresolved-type> <base-unresolved-name>
  2586  //	                  ::= srN <unresolved-type> <unresolved-qualifier-level>+ E <base-unresolved-name>
  2587  //	                  ::= [gs] sr <unresolved-qualifier-level>+ E <base-unresolved-name>
  2588  func (st *state) unresolvedName() AST {
  2589  	if len(st.str) >= 2 && st.str[:2] == "gs" {
  2590  		st.advance(2)
  2591  		n := st.unresolvedName()
  2592  		return &Unary{
  2593  			Op:         &Operator{Name: "::"},
  2594  			Expr:       n,
  2595  			Suffix:     false,
  2596  			SizeofType: false,
  2597  		}
  2598  	} else if len(st.str) >= 2 && st.str[:2] == "sr" {
  2599  		st.advance(2)
  2600  		if len(st.str) == 0 {
  2601  			st.fail("expected unresolved type")
  2602  		}
  2603  		switch st.str[0] {
  2604  		case 'T', 'D', 'S':
  2605  			t := st.demangleType(false)
  2606  			n := st.baseUnresolvedName()
  2607  			n = &Qualified{Scope: t, Name: n, LocalName: false}
  2608  			if len(st.str) > 0 && st.str[0] == 'I' {
  2609  				args := st.templateArgs()
  2610  				n = &Template{Name: n, Args: args}
  2611  				st.subs.add(n)
  2612  			}
  2613  			return n
  2614  		default:
  2615  			var s AST
  2616  			if st.str[0] == 'N' {
  2617  				st.advance(1)
  2618  				s = st.demangleType(false)
  2619  			}
  2620  			for len(st.str) == 0 || st.str[0] != 'E' {
  2621  				// GCC does not seem to follow the ABI here.
  2622  				// It can emit type/name without an 'E'.
  2623  				if s != nil && len(st.str) > 0 && !isDigit(st.str[0]) {
  2624  					if q, ok := s.(*Qualified); ok {
  2625  						a := q.Scope
  2626  						if t, ok := a.(*Template); ok {
  2627  							st.subs.add(t.Name)
  2628  							st.subs.add(t)
  2629  						} else {
  2630  							st.subs.add(a)
  2631  						}
  2632  						return s
  2633  					}
  2634  				}
  2635  				n := st.sourceName()
  2636  				if len(st.str) > 0 && st.str[0] == 'I' {
  2637  					st.subs.add(n)
  2638  					args := st.templateArgs()
  2639  					n = &Template{Name: n, Args: args}
  2640  				}
  2641  				if s == nil {
  2642  					s = n
  2643  				} else {
  2644  					s = &Qualified{Scope: s, Name: n, LocalName: false}
  2645  				}
  2646  				st.subs.add(s)
  2647  			}
  2648  			if s == nil {
  2649  				st.fail("missing scope in unresolved name")
  2650  			}
  2651  			st.advance(1)
  2652  			n := st.baseUnresolvedName()
  2653  			return &Qualified{Scope: s, Name: n, LocalName: false}
  2654  		}
  2655  	} else {
  2656  		return st.baseUnresolvedName()
  2657  	}
  2658  }
  2659  
  2660  // baseUnresolvedName parses:
  2661  //
  2662  //	<base-unresolved-name> ::= <simple-id>
  2663  //	                       ::= on <operator-name>
  2664  //	                       ::= on <operator-name> <template-args>
  2665  //	                       ::= dn <destructor-name>
  2666  //
  2667  //	<simple-id> ::= <source-name> [ <template-args> ]
  2668  func (st *state) baseUnresolvedName() AST {
  2669  	var n AST
  2670  	if len(st.str) >= 2 && st.str[:2] == "on" {
  2671  		st.advance(2)
  2672  		n, _ = st.operatorName(true)
  2673  	} else if len(st.str) >= 2 && st.str[:2] == "dn" {
  2674  		st.advance(2)
  2675  		if len(st.str) > 0 && isDigit(st.str[0]) {
  2676  			n = st.sourceName()
  2677  		} else {
  2678  			n = st.demangleType(false)
  2679  		}
  2680  		n = &Destructor{Name: n}
  2681  	} else if len(st.str) > 0 && isDigit(st.str[0]) {
  2682  		n = st.sourceName()
  2683  	} else {
  2684  		// GCC seems to not follow the ABI here: it can have
  2685  		// an operator name without on.
  2686  		// See https://gcc.gnu.org/PR70182.
  2687  		n, _ = st.operatorName(true)
  2688  	}
  2689  	if len(st.str) > 0 && st.str[0] == 'I' {
  2690  		args := st.templateArgs()
  2691  		n = &Template{Name: n, Args: args}
  2692  	}
  2693  	return n
  2694  }
  2695  
  2696  // exprPrimary parses:
  2697  //
  2698  //	<expr-primary> ::= L <type> <(value) number> E
  2699  //	               ::= L <type> <(value) float> E
  2700  //	               ::= L <mangled-name> E
  2701  func (st *state) exprPrimary() AST {
  2702  	st.checkChar('L')
  2703  	if len(st.str) == 0 {
  2704  		st.fail("expected primary expression")
  2705  
  2706  	}
  2707  
  2708  	// Check for 'Z' here because g++ incorrectly omitted the
  2709  	// underscore until -fabi-version=3.
  2710  	var ret AST
  2711  	if st.str[0] == '_' || st.str[0] == 'Z' {
  2712  		if st.str[0] == '_' {
  2713  			st.advance(1)
  2714  		}
  2715  		if len(st.str) == 0 || st.str[0] != 'Z' {
  2716  			st.fail("expected mangled name")
  2717  		}
  2718  		st.advance(1)
  2719  		ret = st.encoding(true, notForLocalName)
  2720  	} else {
  2721  		t := st.demangleType(false)
  2722  
  2723  		isArrayType := func(typ AST) bool {
  2724  			if twq, ok := typ.(*TypeWithQualifiers); ok {
  2725  				typ = twq.Base
  2726  			}
  2727  			_, ok := typ.(*ArrayType)
  2728  			return ok
  2729  		}
  2730  
  2731  		neg := false
  2732  		if len(st.str) > 0 && st.str[0] == 'n' {
  2733  			neg = true
  2734  			st.advance(1)
  2735  		}
  2736  		if len(st.str) > 0 && st.str[0] == 'E' {
  2737  			if bt, ok := t.(*BuiltinType); ok && bt.Name == "decltype(nullptr)" {
  2738  				// A nullptr should not have a value.
  2739  				// We accept one if present because GCC
  2740  				// used to generate one.
  2741  				// https://gcc.gnu.org/PR91979.
  2742  			} else if cl, ok := t.(*Closure); ok {
  2743  				// A closure doesn't have a value.
  2744  				st.advance(1)
  2745  				return &LambdaExpr{Type: cl}
  2746  			} else if isArrayType(t) {
  2747  				st.advance(1)
  2748  				return &StringLiteral{Type: t}
  2749  			} else {
  2750  				st.fail("missing literal value")
  2751  			}
  2752  		}
  2753  		i := 0
  2754  		for len(st.str) > i && st.str[i] != 'E' {
  2755  			i++
  2756  		}
  2757  		val := st.str[:i]
  2758  		st.advance(i)
  2759  		ret = &Literal{Type: t, Val: val, Neg: neg}
  2760  	}
  2761  	if len(st.str) == 0 || st.str[0] != 'E' {
  2762  		st.fail("expected E after literal")
  2763  	}
  2764  	st.advance(1)
  2765  	return ret
  2766  }
  2767  
  2768  // discriminator parses:
  2769  //
  2770  //	<discriminator> ::= _ <(non-negative) number> (when number < 10)
  2771  //	                    __ <(non-negative) number> _ (when number >= 10)
  2772  func (st *state) discriminator(a AST) AST {
  2773  	if len(st.str) == 0 || st.str[0] != '_' {
  2774  		// clang can generate a discriminator at the end of
  2775  		// the string with no underscore.
  2776  		for i := 0; i < len(st.str); i++ {
  2777  			if !isDigit(st.str[i]) {
  2778  				return a
  2779  			}
  2780  		}
  2781  		// Skip the trailing digits.
  2782  		st.advance(len(st.str))
  2783  		return a
  2784  	}
  2785  	off := st.off
  2786  	st.advance(1)
  2787  	trailingUnderscore := false
  2788  	if len(st.str) > 0 && st.str[0] == '_' {
  2789  		st.advance(1)
  2790  		trailingUnderscore = true
  2791  	}
  2792  	d := st.number()
  2793  	if d < 0 {
  2794  		st.failEarlier("invalid negative discriminator", st.off-off)
  2795  	}
  2796  	if trailingUnderscore && d >= 10 {
  2797  		if len(st.str) == 0 || st.str[0] != '_' {
  2798  			st.fail("expected _ after discriminator >= 10")
  2799  		}
  2800  		st.advance(1)
  2801  	}
  2802  	// We don't currently print out the discriminator, so we don't
  2803  	// save it.
  2804  	return a
  2805  }
  2806  
  2807  // closureTypeName parses:
  2808  //
  2809  //	<closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
  2810  //	<lambda-sig> ::= <parameter type>+
  2811  func (st *state) closureTypeName() AST {
  2812  	st.checkChar('U')
  2813  	st.checkChar('l')
  2814  
  2815  	oldLambdaTemplateLevel := st.lambdaTemplateLevel
  2816  	st.lambdaTemplateLevel = len(st.templates) + 1
  2817  
  2818  	var templateArgs []AST
  2819  	var template *Template
  2820  	for len(st.str) > 1 && st.str[0] == 'T' {
  2821  		arg, templateVal := st.templateParamDecl()
  2822  		if arg == nil {
  2823  			break
  2824  		}
  2825  		templateArgs = append(templateArgs, arg)
  2826  		if template == nil {
  2827  			template = &Template{
  2828  				Name: &Name{Name: "lambda"},
  2829  			}
  2830  			st.templates = append(st.templates, template)
  2831  		}
  2832  		template.Args = append(template.Args, templateVal)
  2833  	}
  2834  
  2835  	types := st.parmlist()
  2836  
  2837  	st.lambdaTemplateLevel = oldLambdaTemplateLevel
  2838  
  2839  	if template != nil {
  2840  		st.templates = st.templates[:len(st.templates)-1]
  2841  	}
  2842  
  2843  	if len(st.str) == 0 || st.str[0] != 'E' {
  2844  		st.fail("expected E after closure type name")
  2845  	}
  2846  	st.advance(1)
  2847  	num := st.compactNumber()
  2848  	return &Closure{TemplateArgs: templateArgs, Types: types, Num: num}
  2849  }
  2850  
  2851  // templateParamDecl parses:
  2852  //
  2853  //	<template-param-decl> ::= Ty                          # type parameter
  2854  //	                      ::= Tn <type>                   # non-type parameter
  2855  //	                      ::= Tt <template-param-decl>* E # template parameter
  2856  //	                      ::= Tp <template-param-decl>    # parameter pack
  2857  //
  2858  // Returns the new AST to include in the AST we are building and the
  2859  // new AST to add to the list of template parameters.
  2860  //
  2861  // Returns nil, nil if not looking at a template-param-decl.
  2862  func (st *state) templateParamDecl() (AST, AST) {
  2863  	if len(st.str) < 2 || st.str[0] != 'T' {
  2864  		return nil, nil
  2865  	}
  2866  	mk := func(prefix string, p *int) AST {
  2867  		idx := *p
  2868  		(*p)++
  2869  		return &TemplateParamName{
  2870  			Prefix: prefix,
  2871  			Index:  idx,
  2872  		}
  2873  	}
  2874  	switch st.str[1] {
  2875  	case 'y':
  2876  		st.advance(2)
  2877  		name := mk("$T", &st.typeTemplateParamCount)
  2878  		tp := &TypeTemplateParam{
  2879  			Name: name,
  2880  		}
  2881  		return tp, name
  2882  	case 'n':
  2883  		st.advance(2)
  2884  		name := mk("$N", &st.nonTypeTemplateParamCount)
  2885  		typ := st.demangleType(false)
  2886  		tp := &NonTypeTemplateParam{
  2887  			Name: name,
  2888  			Type: typ,
  2889  		}
  2890  		return tp, name
  2891  	case 't':
  2892  		st.advance(2)
  2893  		name := mk("$TT", &st.templateTemplateParamCount)
  2894  		var params []AST
  2895  		var template *Template
  2896  		for {
  2897  			if len(st.str) == 0 {
  2898  				st.fail("expected closure template parameter")
  2899  			}
  2900  			if st.str[0] == 'E' {
  2901  				st.advance(1)
  2902  				break
  2903  			}
  2904  			off := st.off
  2905  			param, templateVal := st.templateParamDecl()
  2906  			if param == nil {
  2907  				st.failEarlier("expected closure template parameter", st.off-off)
  2908  			}
  2909  			params = append(params, param)
  2910  			if template == nil {
  2911  				template = &Template{
  2912  					Name: &Name{Name: "template_template"},
  2913  				}
  2914  				st.templates = append(st.templates, template)
  2915  			}
  2916  			template.Args = append(template.Args, templateVal)
  2917  		}
  2918  		if template != nil {
  2919  			st.templates = st.templates[:len(st.templates)-1]
  2920  		}
  2921  		tp := &TemplateTemplateParam{
  2922  			Name:   name,
  2923  			Params: params,
  2924  		}
  2925  		return tp, name
  2926  	case 'p':
  2927  		st.advance(2)
  2928  		off := st.off
  2929  		param, templateVal := st.templateParamDecl()
  2930  		if param == nil {
  2931  			st.failEarlier("expected lambda template parameter", st.off-off)
  2932  		}
  2933  		return &TemplateParamPack{Param: param}, templateVal
  2934  	default:
  2935  		return nil, nil
  2936  	}
  2937  }
  2938  
  2939  // unnamedTypeName parses:
  2940  //
  2941  //	<unnamed-type-name> ::= Ut [ <nonnegative number> ] _
  2942  func (st *state) unnamedTypeName() AST {
  2943  	st.checkChar('U')
  2944  	st.checkChar('t')
  2945  	num := st.compactNumber()
  2946  	ret := &UnnamedType{Num: num}
  2947  	st.subs.add(ret)
  2948  	return ret
  2949  }
  2950  
  2951  // Recognize a clone suffix.  These are not part of the mangling API,
  2952  // but are added by GCC when cloning functions.
  2953  func (st *state) cloneSuffix(a AST) AST {
  2954  	i := 0
  2955  	if len(st.str) > 1 && st.str[0] == '.' && (isLower(st.str[1]) || isDigit(st.str[1]) || st.str[1] == '_') {
  2956  		i += 2
  2957  		for len(st.str) > i && (isLower(st.str[i]) || isDigit(st.str[i]) || st.str[i] == '_') {
  2958  			i++
  2959  		}
  2960  	}
  2961  	for len(st.str) > i+1 && st.str[i] == '.' && isDigit(st.str[i+1]) {
  2962  		i += 2
  2963  		for len(st.str) > i && isDigit(st.str[i]) {
  2964  			i++
  2965  		}
  2966  	}
  2967  	suffix := st.str[:i]
  2968  	st.advance(i)
  2969  	return &Clone{Base: a, Suffix: suffix}
  2970  }
  2971  
  2972  // substitutions is the list of substitution candidates that may
  2973  // appear later in the string.
  2974  type substitutions []AST
  2975  
  2976  // add adds a new substitution candidate.
  2977  func (subs *substitutions) add(a AST) {
  2978  	*subs = append(*subs, a)
  2979  }
  2980  
  2981  // subAST maps standard substitution codes to the corresponding AST.
  2982  var subAST = map[byte]AST{
  2983  	't': &Name{Name: "std"},
  2984  	'a': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "allocator"}},
  2985  	'b': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "basic_string"}},
  2986  	's': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "string"}},
  2987  	'i': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "istream"}},
  2988  	'o': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "ostream"}},
  2989  	'd': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "iostream"}},
  2990  }
  2991  
  2992  // verboseAST maps standard substitution codes to the long form of the
  2993  // corresponding AST.  We use this when the Verbose option is used, to
  2994  // match the standard demangler.
  2995  var verboseAST = map[byte]AST{
  2996  	't': &Name{Name: "std"},
  2997  	'a': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "allocator"}},
  2998  	'b': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "basic_string"}},
  2999  
  3000  	// std::basic_string<char, std::char_traits<char>, std::allocator<char> >
  3001  	's': &Template{
  3002  		Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "basic_string"}},
  3003  		Args: []AST{
  3004  			&BuiltinType{Name: "char"},
  3005  			&Template{
  3006  				Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "char_traits"}},
  3007  				Args: []AST{&BuiltinType{Name: "char"}}},
  3008  			&Template{
  3009  				Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "allocator"}},
  3010  				Args: []AST{&BuiltinType{Name: "char"}}}}},
  3011  	// std::basic_istream<char, std::char_traits<char> >
  3012  	'i': &Template{
  3013  		Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "basic_istream"}},
  3014  		Args: []AST{
  3015  			&BuiltinType{Name: "char"},
  3016  			&Template{
  3017  				Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "char_traits"}},
  3018  				Args: []AST{&BuiltinType{Name: "char"}}}}},
  3019  	// std::basic_ostream<char, std::char_traits<char> >
  3020  	'o': &Template{
  3021  		Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "basic_ostream"}},
  3022  		Args: []AST{
  3023  			&BuiltinType{Name: "char"},
  3024  			&Template{
  3025  				Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "char_traits"}},
  3026  				Args: []AST{&BuiltinType{Name: "char"}}}}},
  3027  	// std::basic_iostream<char, std::char_traits<char> >
  3028  	'd': &Template{
  3029  		Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "basic_iostream"}},
  3030  		Args: []AST{
  3031  			&BuiltinType{Name: "char"},
  3032  			&Template{
  3033  				Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "char_traits"}},
  3034  				Args: []AST{&BuiltinType{Name: "char"}}}}},
  3035  }
  3036  
  3037  // substitution parses:
  3038  //
  3039  //	<substitution> ::= S <seq-id> _
  3040  //	               ::= S_
  3041  //	               ::= St
  3042  //	               ::= Sa
  3043  //	               ::= Sb
  3044  //	               ::= Ss
  3045  //	               ::= Si
  3046  //	               ::= So
  3047  //	               ::= Sd
  3048  func (st *state) substitution(forPrefix bool) AST {
  3049  	st.checkChar('S')
  3050  	if len(st.str) == 0 {
  3051  		st.fail("missing substitution index")
  3052  	}
  3053  	c := st.str[0]
  3054  	off := st.off
  3055  	if c == '_' || isDigit(c) || isUpper(c) {
  3056  		id := st.seqID(false)
  3057  		if id >= len(st.subs) {
  3058  			st.failEarlier(fmt.Sprintf("substitution index out of range (%d >= %d)", id, len(st.subs)), st.off-off)
  3059  		}
  3060  
  3061  		ret := st.subs[id]
  3062  
  3063  		// We need to update any references to template
  3064  		// parameters to refer to the currently active
  3065  		// template.
  3066  
  3067  		// When copying a Typed we may need to adjust
  3068  		// the templates.
  3069  		copyTemplates := st.templates
  3070  		var oldLambdaTemplateLevel []int
  3071  
  3072  		// pushTemplate is called from skip, popTemplate from copy.
  3073  		pushTemplate := func(template *Template) {
  3074  			copyTemplates = append(copyTemplates, template)
  3075  			oldLambdaTemplateLevel = append(oldLambdaTemplateLevel, st.lambdaTemplateLevel)
  3076  			st.lambdaTemplateLevel = 0
  3077  		}
  3078  		popTemplate := func() {
  3079  			copyTemplates = copyTemplates[:len(copyTemplates)-1]
  3080  			st.lambdaTemplateLevel = oldLambdaTemplateLevel[len(oldLambdaTemplateLevel)-1]
  3081  			oldLambdaTemplateLevel = oldLambdaTemplateLevel[:len(oldLambdaTemplateLevel)-1]
  3082  		}
  3083  
  3084  		copy := func(a AST) AST {
  3085  			var index int
  3086  			switch a := a.(type) {
  3087  			case *Typed:
  3088  				// Remove the template added in skip.
  3089  				if _, ok := a.Name.(*Template); ok {
  3090  					popTemplate()
  3091  				}
  3092  				return nil
  3093  			case *Closure:
  3094  				// Undo the save in skip.
  3095  				st.lambdaTemplateLevel = oldLambdaTemplateLevel[len(oldLambdaTemplateLevel)-1]
  3096  				oldLambdaTemplateLevel = oldLambdaTemplateLevel[:len(oldLambdaTemplateLevel)-1]
  3097  				return nil
  3098  			case *TemplateParam:
  3099  				index = a.Index
  3100  			case *LambdaAuto:
  3101  				// A lambda auto parameter is represented
  3102  				// as a template parameter, so we may have
  3103  				// to change back when substituting.
  3104  				index = a.Index
  3105  			default:
  3106  				return nil
  3107  			}
  3108  			if st.lambdaTemplateLevel > 0 {
  3109  				if _, ok := a.(*LambdaAuto); ok {
  3110  					return nil
  3111  				}
  3112  				return &LambdaAuto{Index: index}
  3113  			}
  3114  			var template *Template
  3115  			if len(copyTemplates) > 0 {
  3116  				template = copyTemplates[len(copyTemplates)-1]
  3117  			} else if rt, ok := ret.(*Template); ok {
  3118  				// At least with clang we can see a template
  3119  				// to start, and sometimes we need to refer
  3120  				// to it. There is probably something wrong
  3121  				// here.
  3122  				template = rt
  3123  			} else {
  3124  				st.failEarlier("substituted template parameter not in scope of template", st.off-off)
  3125  			}
  3126  			if template == nil {
  3127  				// This template parameter is within
  3128  				// the scope of a cast operator.
  3129  				return &TemplateParam{Index: index, Template: nil}
  3130  			}
  3131  
  3132  			if index >= len(template.Args) {
  3133  				st.failEarlier(fmt.Sprintf("substituted template index out of range (%d >= %d)", index, len(template.Args)), st.off-off)
  3134  			}
  3135  
  3136  			return &TemplateParam{Index: index, Template: template}
  3137  		}
  3138  		var seen []AST
  3139  		skip := func(a AST) bool {
  3140  			switch a := a.(type) {
  3141  			case *Typed:
  3142  				if template, ok := a.Name.(*Template); ok {
  3143  					// This template is removed in copy.
  3144  					pushTemplate(template)
  3145  				}
  3146  				return false
  3147  			case *Closure:
  3148  				// This is undone in copy.
  3149  				oldLambdaTemplateLevel = append(oldLambdaTemplateLevel, st.lambdaTemplateLevel)
  3150  				st.lambdaTemplateLevel = len(copyTemplates) + 1
  3151  				return false
  3152  			case *TemplateParam, *LambdaAuto:
  3153  				return false
  3154  			}
  3155  			for _, v := range seen {
  3156  				if v == a {
  3157  					return true
  3158  				}
  3159  			}
  3160  			seen = append(seen, a)
  3161  			return false
  3162  		}
  3163  
  3164  		if c := ret.Copy(copy, skip); c != nil {
  3165  			return c
  3166  		}
  3167  
  3168  		return ret
  3169  	} else {
  3170  		st.advance(1)
  3171  		m := subAST
  3172  		if st.verbose {
  3173  			m = verboseAST
  3174  		}
  3175  		// For compatibility with the standard demangler, use
  3176  		// a longer name for a constructor or destructor.
  3177  		if forPrefix && len(st.str) > 0 && (st.str[0] == 'C' || st.str[0] == 'D') {
  3178  			m = verboseAST
  3179  		}
  3180  		a, ok := m[c]
  3181  		if !ok {
  3182  			st.failEarlier("unrecognized substitution code", 1)
  3183  		}
  3184  
  3185  		if len(st.str) > 0 && st.str[0] == 'B' {
  3186  			a = st.taggedName(a)
  3187  			st.subs.add(a)
  3188  		}
  3189  
  3190  		return a
  3191  	}
  3192  }
  3193  
  3194  // isDigit returns whetner c is a digit for demangling purposes.
  3195  func isDigit(c byte) bool {
  3196  	return c >= '0' && c <= '9'
  3197  }
  3198  
  3199  // isUpper returns whether c is an upper case letter for demangling purposes.
  3200  func isUpper(c byte) bool {
  3201  	return c >= 'A' && c <= 'Z'
  3202  }
  3203  
  3204  // isLower returns whether c is a lower case letter for demangling purposes.
  3205  func isLower(c byte) bool {
  3206  	return c >= 'a' && c <= 'z'
  3207  }
  3208  
  3209  // simplify replaces template parameters with their expansions, and
  3210  // merges qualifiers.
  3211  func simplify(a AST) AST {
  3212  	var seen []AST
  3213  	skip := func(a AST) bool {
  3214  		for _, v := range seen {
  3215  			if v == a {
  3216  				return true
  3217  			}
  3218  		}
  3219  		seen = append(seen, a)
  3220  		return false
  3221  	}
  3222  	if r := a.Copy(simplifyOne, skip); r != nil {
  3223  		return r
  3224  	}
  3225  	return a
  3226  }
  3227  
  3228  // simplifyOne simplifies a single AST.  It returns nil if there is
  3229  // nothing to do.
  3230  func simplifyOne(a AST) AST {
  3231  	switch a := a.(type) {
  3232  	case *TemplateParam:
  3233  		if a.Template != nil && a.Index < len(a.Template.Args) {
  3234  			return a.Template.Args[a.Index]
  3235  		}
  3236  	case *MethodWithQualifiers:
  3237  		if m, ok := a.Method.(*MethodWithQualifiers); ok {
  3238  			ref := a.RefQualifier
  3239  			if ref == "" {
  3240  				ref = m.RefQualifier
  3241  			} else if m.RefQualifier != "" {
  3242  				if ref == "&" || m.RefQualifier == "&" {
  3243  					ref = "&"
  3244  				}
  3245  			}
  3246  			return &MethodWithQualifiers{Method: m.Method, Qualifiers: mergeQualifiers(a.Qualifiers, m.Qualifiers), RefQualifier: ref}
  3247  		}
  3248  		if t, ok := a.Method.(*TypeWithQualifiers); ok {
  3249  			return &MethodWithQualifiers{Method: t.Base, Qualifiers: mergeQualifiers(a.Qualifiers, t.Qualifiers), RefQualifier: a.RefQualifier}
  3250  		}
  3251  	case *TypeWithQualifiers:
  3252  		if ft, ok := a.Base.(*FunctionType); ok {
  3253  			return &MethodWithQualifiers{Method: ft, Qualifiers: a.Qualifiers, RefQualifier: ""}
  3254  		}
  3255  		if t, ok := a.Base.(*TypeWithQualifiers); ok {
  3256  			return &TypeWithQualifiers{Base: t.Base, Qualifiers: mergeQualifiers(a.Qualifiers, t.Qualifiers)}
  3257  		}
  3258  		if m, ok := a.Base.(*MethodWithQualifiers); ok {
  3259  			return &MethodWithQualifiers{Method: m.Method, Qualifiers: mergeQualifiers(a.Qualifiers, m.Qualifiers), RefQualifier: m.RefQualifier}
  3260  		}
  3261  	case *ReferenceType:
  3262  		if rt, ok := a.Base.(*ReferenceType); ok {
  3263  			return rt
  3264  		}
  3265  		if rrt, ok := a.Base.(*RvalueReferenceType); ok {
  3266  			return &ReferenceType{Base: rrt.Base}
  3267  		}
  3268  	case *RvalueReferenceType:
  3269  		if rrt, ok := a.Base.(*RvalueReferenceType); ok {
  3270  			return rrt
  3271  		}
  3272  		if rt, ok := a.Base.(*ReferenceType); ok {
  3273  			return rt
  3274  		}
  3275  	case *ArrayType:
  3276  		// Qualifiers on the element of an array type
  3277  		// go on the whole array type.
  3278  		if q, ok := a.Element.(*TypeWithQualifiers); ok {
  3279  			return &TypeWithQualifiers{
  3280  				Base:       &ArrayType{Dimension: a.Dimension, Element: q.Base},
  3281  				Qualifiers: q.Qualifiers,
  3282  			}
  3283  		}
  3284  	case *PackExpansion:
  3285  		// Expand the pack and replace it with a list of
  3286  		// expressions.
  3287  		if a.Pack != nil {
  3288  			exprs := make([]AST, len(a.Pack.Args))
  3289  			for i, arg := range a.Pack.Args {
  3290  				copy := func(sub AST) AST {
  3291  					// Replace the ArgumentPack
  3292  					// with a specific argument.
  3293  					if sub == a.Pack {
  3294  						return arg
  3295  					}
  3296  					// Copy everything else.
  3297  					return nil
  3298  				}
  3299  
  3300  				var seen []AST
  3301  				skip := func(sub AST) bool {
  3302  					// Don't traverse into another
  3303  					// pack expansion.
  3304  					if _, ok := sub.(*PackExpansion); ok {
  3305  						return true
  3306  					}
  3307  					for _, v := range seen {
  3308  						if v == sub {
  3309  							return true
  3310  						}
  3311  					}
  3312  					seen = append(seen, sub)
  3313  					return false
  3314  				}
  3315  
  3316  				b := a.Base.Copy(copy, skip)
  3317  				if b == nil {
  3318  					b = a.Base
  3319  				}
  3320  				exprs[i] = simplify(b)
  3321  			}
  3322  			return &ExprList{Exprs: exprs}
  3323  		}
  3324  	}
  3325  	return nil
  3326  }
  3327  
  3328  // findArgumentPack walks the AST looking for the argument pack for a
  3329  // pack expansion.  We find it via a template parameter.
  3330  func (st *state) findArgumentPack(a AST) *ArgumentPack {
  3331  	var seen []AST
  3332  	var ret *ArgumentPack
  3333  	a.Traverse(func(a AST) bool {
  3334  		if ret != nil {
  3335  			return false
  3336  		}
  3337  		switch a := a.(type) {
  3338  		case *TemplateParam:
  3339  			if a.Template == nil || a.Index >= len(a.Template.Args) {
  3340  				return true
  3341  			}
  3342  			if pack, ok := a.Template.Args[a.Index].(*ArgumentPack); ok {
  3343  				ret = pack
  3344  				return false
  3345  			}
  3346  		case *PackExpansion, *Closure, *Name:
  3347  			return false
  3348  		case *TaggedName, *Operator, *BuiltinType, *FunctionParam:
  3349  			return false
  3350  		case *UnnamedType, *FixedType, *DefaultArg:
  3351  			return false
  3352  		}
  3353  		for _, v := range seen {
  3354  			if v == a {
  3355  				return false
  3356  			}
  3357  		}
  3358  		seen = append(seen, a)
  3359  		return true
  3360  	})
  3361  	return ret
  3362  }
  3363  

View as plain text