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

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

View as plain text