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

View as plain text