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 C++ symbol names.
     6	// This package recognizes names that were mangled according to the C++ ABI
     7	// defined at http://codesourcery.com/cxx-abi/.
     8	package demangle
     9	
    10	import (
    11		"errors"
    12		"fmt"
    13		"strings"
    14	)
    15	
    16	// ErrNotMangledName is returned by CheckedDemangle if the string does
    17	// not appear to be a C++ symbol name.
    18	var ErrNotMangledName = errors.New("not a C++ mangled name")
    19	
    20	// Option is the type of demangler options.
    21	type Option int
    22	
    23	const (
    24		// The NoParams option disables demangling of function parameters.
    25		NoParams Option = iota
    26	
    27		// The NoTemplateParams option disables demangling of template parameters.
    28		NoTemplateParams
    29	
    30		// The NoClones option disables inclusion of clone suffixes.
    31		// NoParams implies NoClones.
    32		NoClones
    33	
    34		// The Verbose option turns on more verbose demangling.
    35		Verbose
    36	)
    37	
    38	// Filter demangles a C++ symbol name, returning the human-readable C++ name.
    39	// If any error occurs during demangling, the input string is returned.
    40	func Filter(name string, options ...Option) string {
    41		ret, err := ToString(name, options...)
    42		if err != nil {
    43			return name
    44		}
    45		return ret
    46	}
    47	
    48	// ToString demangles a C++ symbol name, returning human-readable C++
    49	// name or an error.
    50	// If the name does not appear to be a C++ symbol name at all, the
    51	// error will be ErrNotMangledName.
    52	func ToString(name string, options ...Option) (string, error) {
    53		a, err := ToAST(name, options...)
    54		if err != nil {
    55			return "", err
    56		}
    57		return ASTToString(a, options...), nil
    58	}
    59	
    60	// ToAST demangles a C++ symbol name into an abstract syntax tree
    61	// representing the symbol.
    62	// If the NoParams option is passed, and the name has a function type,
    63	// the parameter types are not demangled.
    64	// If the name does not appear to be a C++ symbol name at all, the
    65	// error will be ErrNotMangledName.
    66	func ToAST(name string, options ...Option) (AST, error) {
    67		if strings.HasPrefix(name, "_Z") {
    68			a, err := doDemangle(name[2:], options...)
    69			return a, adjustErr(err, 2)
    70		}
    71	
    72		const prefix = "_GLOBAL_"
    73		if strings.HasPrefix(name, prefix) {
    74			// The standard demangler ignores NoParams for global
    75			// constructors.  We are compatible.
    76			i := 0
    77			for i < len(options) {
    78				if options[i] == NoParams {
    79					options = append(options[:i], options[i+1:]...)
    80				} else {
    81					i++
    82				}
    83			}
    84			a, err := globalCDtorName(name[len(prefix):], options...)
    85			return a, adjustErr(err, len(prefix))
    86		}
    87	
    88		return nil, ErrNotMangledName
    89	}
    90	
    91	// globalCDtorName demangles a global constructor/destructor symbol name.
    92	// The parameter is the string following the "_GLOBAL_" prefix.
    93	func globalCDtorName(name string, options ...Option) (AST, error) {
    94		if len(name) < 4 {
    95			return nil, ErrNotMangledName
    96		}
    97		switch name[0] {
    98		case '.', '_', '$':
    99		default:
   100			return nil, ErrNotMangledName
   101		}
   102	
   103		var ctor bool
   104		switch name[1] {
   105		case 'I':
   106			ctor = true
   107		case 'D':
   108			ctor = false
   109		default:
   110			return nil, ErrNotMangledName
   111		}
   112	
   113		if name[2] != '_' {
   114			return nil, ErrNotMangledName
   115		}
   116	
   117		if !strings.HasPrefix(name[3:], "_Z") {
   118			return &GlobalCDtor{Ctor: ctor, Key: &Name{Name: name}}, nil
   119		} else {
   120			a, err := doDemangle(name[5:], options...)
   121			if err != nil {
   122				return nil, adjustErr(err, 5)
   123			}
   124			return &GlobalCDtor{Ctor: ctor, Key: a}, nil
   125		}
   126	}
   127	
   128	// The doDemangle function is the entry point into the demangler proper.
   129	func doDemangle(name string, options ...Option) (ret AST, err error) {
   130		// When the demangling routines encounter an error, they panic
   131		// with a value of type demangleErr.
   132		defer func() {
   133			if r := recover(); r != nil {
   134				if de, ok := r.(demangleErr); ok {
   135					ret = nil
   136					err = de
   137					return
   138				}
   139				panic(r)
   140			}
   141		}()
   142	
   143		params := true
   144		clones := true
   145		verbose := false
   146		for _, o := range options {
   147			switch o {
   148			case NoParams:
   149				params = false
   150				clones = false
   151			case NoTemplateParams:
   152			// This is a valid option but only affect printing of the AST.
   153			case NoClones:
   154				clones = false
   155			case Verbose:
   156				verbose = true
   157			default:
   158				return nil, fmt.Errorf("unrecognized demangler option %v", o)
   159			}
   160		}
   161	
   162		st := &state{str: name, verbose: verbose}
   163		a := st.encoding(params)
   164	
   165		// Accept a clone suffix.
   166		if clones {
   167			for len(st.str) > 1 && st.str[0] == '.' && (isLower(st.str[1]) || st.str[1] == '_' || isDigit(st.str[1])) {
   168				a = st.cloneSuffix(a)
   169			}
   170		}
   171	
   172		if clones && len(st.str) > 0 {
   173			st.fail("unparsed characters at end of mangled name")
   174		}
   175	
   176		return a, nil
   177	}
   178	
   179	// A state holds the current state of demangling a string.
   180	type state struct {
   181		str       string        // remainder of string to demangle
   182		verbose   bool          // whether to use verbose demangling
   183		off       int           // offset of str within original string
   184		subs      substitutions // substitutions
   185		templates []*Template   // templates being processed
   186	}
   187	
   188	// copy returns a copy of the current state.
   189	func (st *state) copy() *state {
   190		n := new(state)
   191		*n = *st
   192		return n
   193	}
   194	
   195	// fail panics with demangleErr, to be caught in doDemangle.
   196	func (st *state) fail(err string) {
   197		panic(demangleErr{err: err, off: st.off})
   198	}
   199	
   200	// failEarlier is like fail, but decrements the offset to indicate
   201	// that the point of failure occurred earlier in the string.
   202	func (st *state) failEarlier(err string, dec int) {
   203		if st.off < dec {
   204			panic("internal error")
   205		}
   206		panic(demangleErr{err: err, off: st.off - dec})
   207	}
   208	
   209	// advance advances the current string offset.
   210	func (st *state) advance(add int) {
   211		if len(st.str) < add {
   212			panic("internal error")
   213		}
   214		st.str = st.str[add:]
   215		st.off += add
   216	}
   217	
   218	// checkChar requires that the next character in the string be c, and
   219	// advances past it.
   220	func (st *state) checkChar(c byte) {
   221		if len(st.str) == 0 || st.str[0] != c {
   222			panic("internal error")
   223		}
   224		st.advance(1)
   225	}
   226	
   227	// A demangleErr is an error at a specific offset in the mangled
   228	// string.
   229	type demangleErr struct {
   230		err string
   231		off int
   232	}
   233	
   234	// Error implements the builtin error interface for demangleErr.
   235	func (de demangleErr) Error() string {
   236		return fmt.Sprintf("%s at %d", de.err, de.off)
   237	}
   238	
   239	// adjustErr adjusts the position of err, if it is a demangleErr,
   240	// and returns err.
   241	func adjustErr(err error, adj int) error {
   242		if err == nil {
   243			return nil
   244		}
   245		if de, ok := err.(demangleErr); ok {
   246			de.off += adj
   247			return de
   248		}
   249		return err
   250	}
   251	
   252	// encoding ::= <(function) name> <bare-function-type>
   253	//              <(data) name>
   254	//              <special-name>
   255	func (st *state) encoding(params bool) AST {
   256		if len(st.str) < 1 {
   257			st.fail("expected encoding")
   258		}
   259	
   260		if st.str[0] == 'G' || st.str[0] == 'T' {
   261			return st.specialName()
   262		}
   263	
   264		a := st.name()
   265		a = simplify(a)
   266	
   267		if !params {
   268			// Don't demangle the parameters.
   269	
   270			// Strip CV-qualifiers, as they apply to the 'this'
   271			// parameter, and are not output by the standard
   272			// demangler without parameters.
   273			if mwq, ok := a.(*MethodWithQualifiers); ok {
   274				a = mwq.Method
   275			}
   276	
   277			// If this is a local name, there may be CV-qualifiers
   278			// on the name that really apply to the top level, and
   279			// therefore must be discarded when discarding
   280			// parameters.  This can happen when parsing a class
   281			// that is local to a function.
   282			if q, ok := a.(*Qualified); ok && q.LocalName {
   283				p := &q.Name
   284				if da, ok := (*p).(*DefaultArg); ok {
   285					p = &da.Arg
   286				}
   287				if mwq, ok := (*p).(*MethodWithQualifiers); ok {
   288					*p = mwq.Method
   289				}
   290			}
   291	
   292			return a
   293		}
   294	
   295		if len(st.str) == 0 || st.str[0] == 'E' {
   296			// There are no parameters--this is a data symbol, not
   297			// a function symbol.
   298			return a
   299		}
   300	
   301		check := a
   302		mwq, _ := check.(*MethodWithQualifiers)
   303		if mwq != nil {
   304			check = mwq.Method
   305		}
   306		template, _ := check.(*Template)
   307		if template != nil {
   308			st.templates = append(st.templates, template)
   309		}
   310	
   311		ft := st.bareFunctionType(hasReturnType(a))
   312	
   313		if template != nil {
   314			st.templates = st.templates[:len(st.templates)-1]
   315		}
   316	
   317		ft = simplify(ft)
   318	
   319		// Any top-level qualifiers belong to the function type.
   320		if mwq != nil {
   321			a = mwq.Method
   322			mwq.Method = ft
   323			ft = mwq
   324		}
   325		if q, ok := a.(*Qualified); ok && q.LocalName {
   326			p := &q.Name
   327			if da, ok := (*p).(*DefaultArg); ok {
   328				p = &da.Arg
   329			}
   330			if mwq, ok := (*p).(*MethodWithQualifiers); ok {
   331				*p = mwq.Method
   332				mwq.Method = ft
   333				ft = mwq
   334			}
   335		}
   336	
   337		return &Typed{Name: a, Type: ft}
   338	}
   339	
   340	// hasReturnType returns whether the mangled form of a will have a
   341	// return type.
   342	func hasReturnType(a AST) bool {
   343		switch a := a.(type) {
   344		case *Template:
   345			return !isCDtorConversion(a.Name)
   346		case *TypeWithQualifiers:
   347			return hasReturnType(a.Base)
   348		case *MethodWithQualifiers:
   349			return hasReturnType(a.Method)
   350		default:
   351			return false
   352		}
   353	}
   354	
   355	// isCDtorConversion returns when an AST is a constructor, a
   356	// destructor, or a conversion operator.
   357	func isCDtorConversion(a AST) bool {
   358		switch a := a.(type) {
   359		case *Qualified:
   360			return isCDtorConversion(a.Name)
   361		case *Constructor, *Destructor, *Cast:
   362			return true
   363		default:
   364			return false
   365		}
   366	}
   367	
   368	// <tagged-name> ::= <name> B <source-name>
   369	func (st *state) taggedName(a AST) AST {
   370		for len(st.str) > 0 && st.str[0] == 'B' {
   371			st.advance(1)
   372			tag := st.sourceName()
   373			a = &TaggedName{Name: a, Tag: tag}
   374		}
   375		return a
   376	}
   377	
   378	// <name> ::= <nested-name>
   379	//        ::= <unscoped-name>
   380	//        ::= <unscoped-template-name> <template-args>
   381	//        ::= <local-name>
   382	//
   383	// <unscoped-name> ::= <unqualified-name>
   384	//                 ::= St <unqualified-name>
   385	//
   386	// <unscoped-template-name> ::= <unscoped-name>
   387	//                          ::= <substitution>
   388	func (st *state) name() AST {
   389		if len(st.str) < 1 {
   390			st.fail("expected name")
   391		}
   392		switch st.str[0] {
   393		case 'N':
   394			return st.nestedName()
   395		case 'Z':
   396			return st.localName()
   397		case 'U':
   398			a, isCast := st.unqualifiedName()
   399			if isCast {
   400				st.setTemplate(a, nil)
   401			}
   402			return a
   403		case 'S':
   404			if len(st.str) < 2 {
   405				st.advance(1)
   406				st.fail("expected substitution index")
   407			}
   408			var a AST
   409			isCast := false
   410			subst := false
   411			if st.str[1] == 't' {
   412				st.advance(2)
   413				a, isCast = st.unqualifiedName()
   414				a = &Qualified{Scope: &Name{Name: "std"}, Name: a, LocalName: false}
   415			} else {
   416				a = st.substitution(false)
   417				subst = true
   418			}
   419			if len(st.str) > 0 && st.str[0] == 'I' {
   420				// This can only happen if we saw
   421				// <unscoped-template-name> and are about to see
   422				// <template-args>.  <unscoped-template-name> is a
   423				// substitution candidate if it did not come from a
   424				// substitution.
   425				if !subst {
   426					st.subs.add(a)
   427				}
   428				args := st.templateArgs()
   429				tmpl := &Template{Name: a, Args: args}
   430				if isCast {
   431					st.setTemplate(a, tmpl)
   432					st.clearTemplateArgs(args)
   433					isCast = false
   434				}
   435				a = tmpl
   436			}
   437			if isCast {
   438				st.setTemplate(a, nil)
   439			}
   440			return a
   441	
   442		default:
   443			a, isCast := st.unqualifiedName()
   444			if len(st.str) > 0 && st.str[0] == 'I' {
   445				st.subs.add(a)
   446				args := st.templateArgs()
   447				tmpl := &Template{Name: a, Args: args}
   448				if isCast {
   449					st.setTemplate(a, tmpl)
   450					st.clearTemplateArgs(args)
   451					isCast = false
   452				}
   453				a = tmpl
   454			}
   455			if isCast {
   456				st.setTemplate(a, nil)
   457			}
   458			return a
   459		}
   460	}
   461	
   462	// <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
   463	//               ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
   464	func (st *state) nestedName() AST {
   465		st.checkChar('N')
   466		q := st.cvQualifiers()
   467		r := st.refQualifier()
   468		a := st.prefix()
   469		if len(q) > 0 || r != "" {
   470			a = &MethodWithQualifiers{Method: a, Qualifiers: q, RefQualifier: r}
   471		}
   472		if len(st.str) == 0 || st.str[0] != 'E' {
   473			st.fail("expected E after nested name")
   474		}
   475		st.advance(1)
   476		return a
   477	}
   478	
   479	// <prefix> ::= <prefix> <unqualified-name>
   480	//          ::= <template-prefix> <template-args>
   481	//          ::= <template-param>
   482	//          ::= <decltype>
   483	//          ::=
   484	//          ::= <substitution>
   485	//
   486	// <template-prefix> ::= <prefix> <(template) unqualified-name>
   487	//                   ::= <template-param>
   488	//                   ::= <substitution>
   489	//
   490	// <decltype> ::= Dt <expression> E
   491	//            ::= DT <expression> E
   492	func (st *state) prefix() AST {
   493		var a AST
   494	
   495		// The last name seen, for a constructor/destructor.
   496		var last AST
   497	
   498		getLast := func(a AST) AST {
   499			for {
   500				if t, ok := a.(*Template); ok {
   501					a = t.Name
   502				} else if q, ok := a.(*Qualified); ok {
   503					a = q.Name
   504				} else if t, ok := a.(*TaggedName); ok {
   505					a = t.Name
   506				} else {
   507					return a
   508				}
   509			}
   510		}
   511	
   512		isCast := false
   513		for {
   514			if len(st.str) == 0 {
   515				st.fail("expected prefix")
   516			}
   517			var next AST
   518	
   519			c := st.str[0]
   520			if isDigit(c) || isLower(c) || c == 'U' || c == 'L' {
   521				un, isUnCast := st.unqualifiedName()
   522				next = un
   523				if isUnCast {
   524					isCast = true
   525				}
   526			} else {
   527				switch st.str[0] {
   528				case 'C':
   529					if len(st.str) < 2 {
   530						st.fail("expected constructor type")
   531					}
   532					if last == nil {
   533						st.fail("constructor before name is seen")
   534					}
   535					st.advance(2)
   536					next = &Constructor{Name: getLast(last)}
   537				case 'D':
   538					if len(st.str) > 1 && (st.str[1] == 'T' || st.str[1] == 't') {
   539						next = st.demangleType(false)
   540					} else {
   541						if len(st.str) < 2 {
   542							st.fail("expected destructor type")
   543						}
   544						if last == nil {
   545							st.fail("destructor before name is seen")
   546						}
   547						st.advance(2)
   548						next = &Destructor{Name: getLast(last)}
   549					}
   550				case 'S':
   551					next = st.substitution(true)
   552				case 'I':
   553					if a == nil {
   554						st.fail("unexpected template arguments")
   555					}
   556					var args []AST
   557					args = st.templateArgs()
   558					tmpl := &Template{Name: a, Args: args}
   559					if isCast {
   560						st.setTemplate(a, tmpl)
   561						st.clearTemplateArgs(args)
   562						isCast = false
   563					}
   564					a = nil
   565					next = tmpl
   566				case 'T':
   567					next = st.templateParam()
   568				case 'E':
   569					if a == nil {
   570						st.fail("expected prefix")
   571					}
   572					if isCast {
   573						st.setTemplate(a, nil)
   574					}
   575					return a
   576				case 'M':
   577					if a == nil {
   578						st.fail("unexpected lambda initializer")
   579					}
   580					// This is the initializer scope for a
   581					// lambda.  We don't need to record
   582					// it.  The normal code will treat the
   583					// variable has a type scope, which
   584					// gives appropriate output.
   585					st.advance(1)
   586					continue
   587				default:
   588					st.fail("unrecognized letter in prefix")
   589				}
   590			}
   591			last = next
   592			if a == nil {
   593				a = next
   594			} else {
   595				a = &Qualified{Scope: a, Name: next, LocalName: false}
   596			}
   597	
   598			if c != 'S' && (len(st.str) == 0 || st.str[0] != 'E') {
   599				st.subs.add(a)
   600			}
   601		}
   602	}
   603	
   604	// <unqualified-name> ::= <operator-name>
   605	//                    ::= <ctor-dtor-name>
   606	//                    ::= <source-name>
   607	//                    ::= <local-source-name>
   608	//
   609	//  <local-source-name>	::= L <source-name> <discriminator>
   610	func (st *state) unqualifiedName() (r AST, isCast bool) {
   611		if len(st.str) < 1 {
   612			st.fail("expected unqualified name")
   613		}
   614		var a AST
   615		isCast = false
   616		c := st.str[0]
   617		if isDigit(c) {
   618			a = st.sourceName()
   619		} else if isLower(c) {
   620			a, _ = st.operatorName(false)
   621			if _, ok := a.(*Cast); ok {
   622				isCast = true
   623			}
   624			if op, ok := a.(*Operator); ok && op.Name == `operator"" ` {
   625				n := st.sourceName()
   626				a = &Unary{Op: op, Expr: n, Suffix: false, SizeofType: false}
   627			}
   628		} else {
   629			switch c {
   630			case 'C', 'D':
   631				st.fail("constructor/destructor not in nested name")
   632			case 'L':
   633				st.advance(1)
   634				a = st.sourceName()
   635				a = st.discriminator(a)
   636			case 'U':
   637				if len(st.str) < 2 {
   638					st.advance(1)
   639					st.fail("expected closure or unnamed type")
   640				}
   641				c := st.str[1]
   642				switch c {
   643				case 'l':
   644					a = st.closureTypeName()
   645				case 't':
   646					a = st.unnamedTypeName()
   647				default:
   648					st.advance(1)
   649					st.fail("expected closure or unnamed type")
   650				}
   651			default:
   652				st.fail("expected unqualified name")
   653			}
   654		}
   655	
   656		if len(st.str) > 0 && st.str[0] == 'B' {
   657			a = st.taggedName(a)
   658		}
   659	
   660		return a, isCast
   661	}
   662	
   663	// <source-name> ::= <(positive length) number> <identifier>
   664	// identifier ::= <(unqualified source code identifier)>
   665	func (st *state) sourceName() AST {
   666		val := st.number()
   667		if val <= 0 {
   668			st.fail("expected positive number")
   669		}
   670		if len(st.str) < val {
   671			st.fail("not enough characters for identifier")
   672		}
   673		id := st.str[:val]
   674		st.advance(val)
   675	
   676		// Look for GCC encoding of anonymous namespace, and make it
   677		// more friendly.
   678		const anonPrefix = "_GLOBAL_"
   679		if strings.HasPrefix(id, anonPrefix) && len(id) > len(anonPrefix)+2 {
   680			c1 := id[len(anonPrefix)]
   681			c2 := id[len(anonPrefix)+1]
   682			if (c1 == '.' || c1 == '_' || c1 == '$') && c2 == 'N' {
   683				id = "(anonymous namespace)"
   684			}
   685		}
   686	
   687		n := &Name{Name: id}
   688		return n
   689	}
   690	
   691	// number ::= [n] <(non-negative decimal integer)>
   692	func (st *state) number() int {
   693		neg := false
   694		if len(st.str) > 0 && st.str[0] == 'n' {
   695			neg = true
   696			st.advance(1)
   697		}
   698		if len(st.str) == 0 || !isDigit(st.str[0]) {
   699			st.fail("missing number")
   700		}
   701		val := 0
   702		for len(st.str) > 0 && isDigit(st.str[0]) {
   703			// Number picked to ensure we can't overflow with 32-bit int.
   704			// Any very large number here is bogus.
   705			if val >= 0x80000000/10-10 {
   706				st.fail("numeric overflow")
   707			}
   708			val = val*10 + int(st.str[0]-'0')
   709			st.advance(1)
   710		}
   711		if neg {
   712			val = -val
   713		}
   714		return val
   715	}
   716	
   717	// An operator is the demangled name, and the number of arguments it
   718	// takes in an expression.
   719	type operator struct {
   720		name string
   721		args int
   722	}
   723	
   724	// The operators map maps the mangled operator names to information
   725	// about them.
   726	var operators = map[string]operator{
   727		"aN": {"&=", 2},
   728		"aS": {"=", 2},
   729		"aa": {"&&", 2},
   730		"ad": {"&", 1},
   731		"an": {"&", 2},
   732		"at": {"alignof ", 1},
   733		"az": {"alignof ", 1},
   734		"cc": {"const_cast", 2},
   735		"cl": {"()", 2},
   736		"cm": {",", 2},
   737		"co": {"~", 1},
   738		"dV": {"/=", 2},
   739		"da": {"delete[] ", 1},
   740		"dc": {"dynamic_cast", 2},
   741		"de": {"*", 1},
   742		"dl": {"delete ", 1},
   743		"ds": {".*", 2},
   744		"dt": {".", 2},
   745		"dv": {"/", 2},
   746		"eO": {"^=", 2},
   747		"eo": {"^", 2},
   748		"eq": {"==", 2},
   749		"fl": {"...", 2},
   750		"fr": {"...", 2},
   751		"fL": {"...", 3},
   752		"fR": {"...", 3},
   753		"ge": {">=", 2},
   754		"gs": {"::", 1},
   755		"gt": {">", 2},
   756		"ix": {"[]", 2},
   757		"lS": {"<<=", 2},
   758		"le": {"<=", 2},
   759		"li": {`operator"" `, 1},
   760		"ls": {"<<", 2},
   761		"lt": {"<", 2},
   762		"mI": {"-=", 2},
   763		"mL": {"*=", 2},
   764		"mi": {"-", 2},
   765		"ml": {"*", 2},
   766		"mm": {"--", 1},
   767		"na": {"new[]", 3},
   768		"ne": {"!=", 2},
   769		"ng": {"-", 1},
   770		"nt": {"!", 1},
   771		"nw": {"new", 3},
   772		"oR": {"|=", 2},
   773		"oo": {"||", 2},
   774		"or": {"|", 2},
   775		"pL": {"+=", 2},
   776		"pl": {"+", 2},
   777		"pm": {"->*", 2},
   778		"pp": {"++", 1},
   779		"ps": {"+", 1},
   780		"pt": {"->", 2},
   781		"qu": {"?", 3},
   782		"rM": {"%=", 2},
   783		"rS": {">>=", 2},
   784		"rc": {"reinterpret_cast", 2},
   785		"rm": {"%", 2},
   786		"rs": {">>", 2},
   787		"sc": {"static_cast", 2},
   788		"st": {"sizeof ", 1},
   789		"sz": {"sizeof ", 1},
   790		"tr": {"throw", 0},
   791		"tw": {"throw ", 1},
   792	}
   793	
   794	// operator_name ::= many different two character encodings.
   795	//               ::= cv <type>
   796	//               ::= v <digit> <source-name>
   797	//
   798	// We need to know whether we are in an expression because it affects
   799	// how we handle template parameters in the type of a cast operator.
   800	func (st *state) operatorName(inExpression bool) (AST, int) {
   801		if len(st.str) < 2 {
   802			st.fail("missing operator code")
   803		}
   804		code := st.str[:2]
   805		st.advance(2)
   806		if code[0] == 'v' && isDigit(code[1]) {
   807			name := st.sourceName()
   808			return &Operator{Name: name.(*Name).Name}, int(code[1] - '0')
   809		} else if code == "cv" {
   810			// Push a nil on templates to indicate that template
   811			// parameters will have their template filled in
   812			// later.
   813			if !inExpression {
   814				st.templates = append(st.templates, nil)
   815			}
   816	
   817			t := st.demangleType(!inExpression)
   818	
   819			if !inExpression {
   820				st.templates = st.templates[:len(st.templates)-1]
   821			}
   822	
   823			return &Cast{To: t}, 1
   824		} else if op, ok := operators[code]; ok {
   825			return &Operator{Name: op.name}, op.args
   826		} else {
   827			st.failEarlier("unrecognized operator code", 2)
   828			panic("not reached")
   829		}
   830	}
   831	
   832	// <local-name> ::= Z <(function) encoding> E <(entity) name> [<discriminator>]
   833	//              ::= Z <(function) encoding> E s [<discriminator>]
   834	//              ::= Z <(function) encoding> E d [<parameter> number>] _ <entity name>
   835	func (st *state) localName() AST {
   836		st.checkChar('Z')
   837		fn := st.encoding(true)
   838		if len(st.str) == 0 || st.str[0] != 'E' {
   839			st.fail("expected E after local name")
   840		}
   841		st.advance(1)
   842		if len(st.str) > 0 && st.str[0] == 's' {
   843			st.advance(1)
   844			var n AST = &Name{Name: "string literal"}
   845			n = st.discriminator(n)
   846			return &Qualified{Scope: fn, Name: n, LocalName: true}
   847		} else {
   848			num := -1
   849			if len(st.str) > 0 && st.str[0] == 'd' {
   850				// Default argument scope.
   851				st.advance(1)
   852				num = st.compactNumber()
   853			}
   854			var n AST = st.name()
   855			n = st.discriminator(n)
   856			if num >= 0 {
   857				n = &DefaultArg{Num: num, Arg: n}
   858			}
   859			return &Qualified{Scope: fn, Name: n, LocalName: true}
   860		}
   861	}
   862	
   863	// Parse a Java resource special-name.
   864	func (st *state) javaResource() AST {
   865		off := st.off
   866		ln := st.number()
   867		if ln <= 1 {
   868			st.failEarlier("java resource length less than 1", st.off-off)
   869		}
   870		if len(st.str) == 0 || st.str[0] != '_' {
   871			st.fail("expected _ after number")
   872		}
   873		st.advance(1)
   874		ln--
   875		if len(st.str) < ln {
   876			st.fail("not enough characters for java resource length")
   877		}
   878		str := st.str[:ln]
   879		final := ""
   880		st.advance(ln)
   881		for i := 0; i < len(str); i++ {
   882			if str[i] != '$' {
   883				final += string(str[i])
   884			} else {
   885				if len(str) <= i+1 {
   886					st.failEarlier("java resource escape at end of string", 1)
   887				}
   888				i++
   889				r, ok := map[byte]string{
   890					'S': "/",
   891					'_': ".",
   892					'$': "$",
   893				}[str[i]]
   894				if !ok {
   895					st.failEarlier("unrecognized java resource escape", ln-i-1)
   896				}
   897				final += r
   898			}
   899		}
   900		return &Special{Prefix: "java resource ", Val: &Name{Name: final}}
   901	}
   902	
   903	// <special-name> ::= TV <type>
   904	//                ::= TT <type>
   905	//                ::= TI <type>
   906	//                ::= TS <type>
   907	//                ::= GV <(object) name>
   908	//                ::= T <call-offset> <(base) encoding>
   909	//                ::= Tc <call-offset> <call-offset> <(base) encoding>
   910	// Also g++ extensions:
   911	//                ::= TC <type> <(offset) number> _ <(base) type>
   912	//                ::= TF <type>
   913	//                ::= TJ <type>
   914	//                ::= GR <name>
   915	//                ::= GA <encoding>
   916	//                ::= Gr <resource name>
   917	//                ::= GTt <encoding>
   918	//                ::= GTn <encoding>
   919	func (st *state) specialName() AST {
   920		if st.str[0] == 'T' {
   921			st.advance(1)
   922			if len(st.str) == 0 {
   923				st.fail("expected special name code")
   924			}
   925			c := st.str[0]
   926			st.advance(1)
   927			switch c {
   928			case 'V':
   929				t := st.demangleType(false)
   930				return &Special{Prefix: "vtable for ", Val: t}
   931			case 'T':
   932				t := st.demangleType(false)
   933				return &Special{Prefix: "VTT for ", Val: t}
   934			case 'I':
   935				t := st.demangleType(false)
   936				return &Special{Prefix: "typeinfo for ", Val: t}
   937			case 'S':
   938				t := st.demangleType(false)
   939				return &Special{Prefix: "typeinfo name for ", Val: t}
   940			case 'h':
   941				st.callOffset('h')
   942				v := st.encoding(true)
   943				return &Special{Prefix: "non-virtual thunk to ", Val: v}
   944			case 'v':
   945				st.callOffset('v')
   946				v := st.encoding(true)
   947				return &Special{Prefix: "virtual thunk to ", Val: v}
   948			case 'c':
   949				st.callOffset(0)
   950				st.callOffset(0)
   951				v := st.encoding(true)
   952				return &Special{Prefix: "covariant return thunk to ", Val: v}
   953			case 'C':
   954				derived := st.demangleType(false)
   955				off := st.off
   956				offset := st.number()
   957				if offset < 0 {
   958					st.failEarlier("expected positive offset", st.off-off)
   959				}
   960				if len(st.str) == 0 || st.str[0] != '_' {
   961					st.fail("expected _ after number")
   962				}
   963				st.advance(1)
   964				base := st.demangleType(false)
   965				return &Special2{Prefix: "construction vtable for ", Val1: base, Middle: "-in-", Val2: derived}
   966			case 'F':
   967				t := st.demangleType(false)
   968				return &Special{Prefix: "typeinfo fn for ", Val: t}
   969			case 'J':
   970				t := st.demangleType(false)
   971				return &Special{Prefix: "java Class for ", Val: t}
   972			case 'H':
   973				n := st.name()
   974				return &Special{Prefix: "TLS init function for ", Val: n}
   975			case 'W':
   976				n := st.name()
   977				return &Special{Prefix: "TLS wrapper function for ", Val: n}
   978			default:
   979				st.fail("unrecognized special T name code")
   980				panic("not reached")
   981			}
   982		} else {
   983			st.checkChar('G')
   984			if len(st.str) == 0 {
   985				st.fail("expected special name code")
   986			}
   987			c := st.str[0]
   988			st.advance(1)
   989			switch c {
   990			case 'V':
   991				n := st.name()
   992				return &Special{Prefix: "guard variable for ", Val: n}
   993			case 'R':
   994				n := st.name()
   995				i := st.number()
   996				return &Special{Prefix: fmt.Sprintf("reference temporary #%d for ", i), Val: n}
   997			case 'A':
   998				v := st.encoding(true)
   999				return &Special{Prefix: "hidden alias for ", Val: v}
  1000			case 'T':
  1001				if len(st.str) == 0 {
  1002					st.fail("expected special GT name code")
  1003				}
  1004				c := st.str[0]
  1005				st.advance(1)
  1006				v := st.encoding(true)
  1007				switch c {
  1008				case 'n':
  1009					return &Special{Prefix: "non-transaction clone for ", Val: v}
  1010				default:
  1011					// The proposal is that different
  1012					// letters stand for different types
  1013					// of transactional cloning.  Treat
  1014					// them all the same for now.
  1015					fallthrough
  1016				case 't':
  1017					return &Special{Prefix: "transaction clone for ", Val: v}
  1018				}
  1019			case 'r':
  1020				return st.javaResource()
  1021			default:
  1022				st.fail("unrecognized special G name code")
  1023				panic("not reached")
  1024			}
  1025		}
  1026	}
  1027	
  1028	// <call-offset> ::= h <nv-offset> _
  1029	//               ::= v <v-offset> _
  1030	//
  1031	// <nv-offset> ::= <(offset) number>
  1032	//
  1033	// <v-offset> ::= <(offset) number> _ <(virtual offset) number>
  1034	//
  1035	// The c parameter, if not 0, is a character we just read which is the
  1036	// start of the <call-offset>.
  1037	//
  1038	// We don't display the offset information anywhere.
  1039	func (st *state) callOffset(c byte) {
  1040		if c == 0 {
  1041			if len(st.str) == 0 {
  1042				st.fail("missing call offset")
  1043			}
  1044			c = st.str[0]
  1045			st.advance(1)
  1046		}
  1047		switch c {
  1048		case 'h':
  1049			st.number()
  1050		case 'v':
  1051			st.number()
  1052			if len(st.str) == 0 || st.str[0] != '_' {
  1053				st.fail("expected _ after number")
  1054			}
  1055			st.advance(1)
  1056			st.number()
  1057		default:
  1058			st.failEarlier("unrecognized call offset code", 1)
  1059		}
  1060		if len(st.str) == 0 || st.str[0] != '_' {
  1061			st.fail("expected _ after call offset")
  1062		}
  1063		st.advance(1)
  1064	}
  1065	
  1066	// builtinTypes maps the type letter to the type name.
  1067	var builtinTypes = map[byte]string{
  1068		'a': "signed char",
  1069		'b': "bool",
  1070		'c': "char",
  1071		'd': "double",
  1072		'e': "long double",
  1073		'f': "float",
  1074		'g': "__float128",
  1075		'h': "unsigned char",
  1076		'i': "int",
  1077		'j': "unsigned int",
  1078		'l': "long",
  1079		'm': "unsigned long",
  1080		'n': "__int128",
  1081		'o': "unsigned __int128",
  1082		's': "short",
  1083		't': "unsigned short",
  1084		'v': "void",
  1085		'w': "wchar_t",
  1086		'x': "long long",
  1087		'y': "unsigned long long",
  1088		'z': "...",
  1089	}
  1090	
  1091	// <type> ::= <builtin-type>
  1092	//        ::= <function-type>
  1093	//        ::= <class-enum-type>
  1094	//        ::= <array-type>
  1095	//        ::= <pointer-to-member-type>
  1096	//        ::= <template-param>
  1097	//        ::= <template-template-param> <template-args>
  1098	//        ::= <substitution>
  1099	//        ::= <CV-qualifiers> <type>
  1100	//        ::= P <type>
  1101	//        ::= R <type>
  1102	//        ::= O <type> (C++0x)
  1103	//        ::= C <type>
  1104	//        ::= G <type>
  1105	//        ::= U <source-name> <type>
  1106	//
  1107	// <builtin-type> ::= various one letter codes
  1108	//                ::= u <source-name>
  1109	func (st *state) demangleType(isCast bool) AST {
  1110		if len(st.str) == 0 {
  1111			st.fail("expected type")
  1112		}
  1113	
  1114		addSubst := true
  1115	
  1116		q := st.cvQualifiers()
  1117		if len(q) > 0 {
  1118			if len(st.str) == 0 {
  1119				st.fail("expected type")
  1120			}
  1121	
  1122			// CV-qualifiers before a function type apply to
  1123			// 'this', so avoid adding the unqualified function
  1124			// type to the substitution list.
  1125			if st.str[0] == 'F' {
  1126				addSubst = false
  1127			}
  1128		}
  1129	
  1130		var ret AST
  1131	
  1132		// Use correct substitution for a template parameter.
  1133		var sub AST
  1134	
  1135		if btype, ok := builtinTypes[st.str[0]]; ok {
  1136			ret = &BuiltinType{Name: btype}
  1137			st.advance(1)
  1138			if len(q) > 0 {
  1139				ret = &TypeWithQualifiers{Base: ret, Qualifiers: q}
  1140				st.subs.add(ret)
  1141			}
  1142			return ret
  1143		}
  1144		c := st.str[0]
  1145		switch c {
  1146		case 'u':
  1147			st.advance(1)
  1148			ret = st.sourceName()
  1149		case 'F':
  1150			ret = st.functionType()
  1151		case 'N', 'Z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
  1152			ret = st.name()
  1153		case 'A':
  1154			ret = st.arrayType(isCast)
  1155		case 'M':
  1156			ret = st.pointerToMemberType(isCast)
  1157		case 'T':
  1158			ret = st.templateParam()
  1159			if len(st.str) > 0 && st.str[0] == 'I' {
  1160				// See the function comment to explain this.
  1161				if !isCast {
  1162					st.subs.add(ret)
  1163					args := st.templateArgs()
  1164					ret = &Template{Name: ret, Args: args}
  1165				} else {
  1166					ret = st.demangleCastTemplateArgs(ret, true)
  1167				}
  1168			}
  1169		case 'S':
  1170			// If this is a special substitution, then it
  1171			// is the start of <class-enum-type>.
  1172			var c2 byte
  1173			if len(st.str) > 1 {
  1174				c2 = st.str[1]
  1175			}
  1176			if isDigit(c2) || c2 == '_' || isUpper(c2) {
  1177				ret = st.substitution(false)
  1178				if len(st.str) == 0 || st.str[0] != 'I' {
  1179					addSubst = false
  1180				} else {
  1181					// See the function comment to explain this.
  1182					if _, ok := ret.(*TemplateParam); !ok || !isCast {
  1183						args := st.templateArgs()
  1184						ret = &Template{Name: ret, Args: args}
  1185					} else {
  1186						next := st.demangleCastTemplateArgs(ret, false)
  1187						if next == ret {
  1188							addSubst = false
  1189						}
  1190						ret = next
  1191					}
  1192				}
  1193			} else {
  1194				ret = st.name()
  1195				// This substitution is not itself a
  1196				// substitution candidate, unless template
  1197				// arguments were added.
  1198				if ret == subAST[c2] || ret == verboseAST[c2] {
  1199					addSubst = false
  1200				}
  1201			}
  1202		case 'O', 'P', 'R', 'C', 'G':
  1203			st.advance(1)
  1204			t := st.demangleType(isCast)
  1205			switch c {
  1206			case 'O':
  1207				ret = &RvalueReferenceType{Base: t}
  1208			case 'P':
  1209				ret = &PointerType{Base: t}
  1210			case 'R':
  1211				ret = &ReferenceType{Base: t}
  1212			case 'C':
  1213				ret = &ComplexType{Base: t}
  1214			case 'G':
  1215				ret = &ImaginaryType{Base: t}
  1216			}
  1217		case 'U':
  1218			if len(st.str) < 2 {
  1219				st.fail("expected source name or unnamed type")
  1220			}
  1221			switch st.str[1] {
  1222			case 'l':
  1223				ret = st.closureTypeName()
  1224				addSubst = false
  1225			case 't':
  1226				ret = st.unnamedTypeName()
  1227				addSubst = false
  1228			default:
  1229				st.advance(1)
  1230				n := st.sourceName()
  1231				if len(st.str) > 0 && st.str[0] == 'I' {
  1232					args := st.templateArgs()
  1233					n = &Template{Name: n, Args: args}
  1234				}
  1235				t := st.demangleType(isCast)
  1236				ret = &VendorQualifier{Qualifier: n, Type: t}
  1237			}
  1238		case 'D':
  1239			st.advance(1)
  1240			if len(st.str) == 0 {
  1241				st.fail("expected D code for type")
  1242			}
  1243			addSubst = false
  1244			c2 := st.str[0]
  1245			st.advance(1)
  1246			switch c2 {
  1247			case 'T', 't':
  1248				// decltype(expression)
  1249				ret = st.expression()
  1250				if len(st.str) == 0 || st.str[0] != 'E' {
  1251					st.fail("expected E after expression in type")
  1252				}
  1253				st.advance(1)
  1254				ret = &Decltype{Expr: ret}
  1255				addSubst = true
  1256	
  1257			case 'p':
  1258				t := st.demangleType(isCast)
  1259				pack := st.findArgumentPack(t)
  1260				ret = &PackExpansion{Base: t, Pack: pack}
  1261				addSubst = true
  1262	
  1263			case 'a':
  1264				ret = &Name{Name: "auto"}
  1265	
  1266			case 'f':
  1267				ret = &BuiltinType{Name: "decimal32"}
  1268			case 'd':
  1269				ret = &BuiltinType{Name: "decimal64"}
  1270			case 'e':
  1271				ret = &BuiltinType{Name: "decimal128"}
  1272			case 'h':
  1273				ret = &BuiltinType{Name: "half"}
  1274			case 's':
  1275				ret = &BuiltinType{Name: "char16_t"}
  1276			case 'i':
  1277				ret = &BuiltinType{Name: "char32_t"}
  1278			case 'n':
  1279				ret = &BuiltinType{Name: "decltype(nullptr)"}
  1280	
  1281			case 'F':
  1282				accum := false
  1283				if len(st.str) > 0 && isDigit(st.str[0]) {
  1284					accum = true
  1285					// We don't care about the bits.
  1286					_ = st.number()
  1287				}
  1288				base := st.demangleType(isCast)
  1289				if len(st.str) > 0 && isDigit(st.str[0]) {
  1290					// We don't care about the bits.
  1291					st.number()
  1292				}
  1293				sat := false
  1294				if len(st.str) > 0 {
  1295					if st.str[0] == 's' {
  1296						sat = true
  1297					}
  1298					st.advance(1)
  1299				}
  1300				ret = &FixedType{Base: base, Accum: accum, Sat: sat}
  1301	
  1302			case 'v':
  1303				ret = st.vectorType(isCast)
  1304				addSubst = true
  1305	
  1306			default:
  1307				st.fail("unrecognized D code in type")
  1308			}
  1309	
  1310		default:
  1311			st.fail("unrecognized type code")
  1312		}
  1313	
  1314		if addSubst {
  1315			if sub != nil {
  1316				st.subs.add(sub)
  1317			} else {
  1318				st.subs.add(ret)
  1319			}
  1320		}
  1321	
  1322		if len(q) > 0 {
  1323			if _, ok := ret.(*FunctionType); ok {
  1324				ret = &MethodWithQualifiers{Method: ret, Qualifiers: q, RefQualifier: ""}
  1325			} else if mwq, ok := ret.(*MethodWithQualifiers); ok {
  1326				// Merge adjacent qualifiers.  This case
  1327				// happens with a function with a trailing
  1328				// ref-qualifier.
  1329				mwq.Qualifiers = mergeQualifiers(q, mwq.Qualifiers)
  1330			} else {
  1331				// Merge adjacent qualifiers.  This case
  1332				// happens with multi-dimensional array types.
  1333				if qsub, ok := ret.(*TypeWithQualifiers); ok {
  1334					q = mergeQualifiers(q, qsub.Qualifiers)
  1335					ret = qsub.Base
  1336				}
  1337				ret = &TypeWithQualifiers{Base: ret, Qualifiers: q}
  1338			}
  1339			st.subs.add(ret)
  1340		}
  1341	
  1342		return ret
  1343	}
  1344	
  1345	// demangleCastTemplateArgs is for a rather hideous parse.  When we
  1346	// see a template-param followed by a template-args, we need to decide
  1347	// whether we have a template-param or a template-template-param.
  1348	// Normally it is template-template-param, meaning that we pick up the
  1349	// template arguments here.  But, if we are parsing the type for a
  1350	// cast operator, then the only way this can be template-template-param
  1351	// is if there is another set of template-args immediately after this
  1352	// set.  That would look like this:
  1353	//
  1354	// <nested-name>
  1355	// -> <template-prefix> <template-args>
  1356	// -> <prefix> <template-unqualified-name> <template-args>
  1357	// -> <unqualified-name> <template-unqualified-name> <template-args>
  1358	// -> <source-name> <template-unqualified-name> <template-args>
  1359	// -> <source-name> <operator-name> <template-args>
  1360	// -> <source-name> cv <type> <template-args>
  1361	// -> <source-name> cv <template-template-param> <template-args> <template-args>
  1362	//
  1363	// Otherwise, we have this derivation:
  1364	//
  1365	// <nested-name>
  1366	// -> <template-prefix> <template-args>
  1367	// -> <prefix> <template-unqualified-name> <template-args>
  1368	// -> <unqualified-name> <template-unqualified-name> <template-args>
  1369	// -> <source-name> <template-unqualified-name> <template-args>
  1370	// -> <source-name> <operator-name> <template-args>
  1371	// -> <source-name> cv <type> <template-args>
  1372	// -> <source-name> cv <template-param> <template-args>
  1373	//
  1374	// in which the template-args are actually part of the prefix.  For
  1375	// the special case where this arises, demangleType is called with
  1376	// isCast as true.  This function is then responsible for checking
  1377	// whether we see <template-param> <template-args> but there is not
  1378	// another following <template-args>.  In that case, we reset the
  1379	// parse and just return the <template-param>.
  1380	func (st *state) demangleCastTemplateArgs(tp AST, addSubst bool) AST {
  1381		save := st.copy()
  1382	
  1383		var args []AST
  1384		failed := false
  1385		func() {
  1386			defer func() {
  1387				if r := recover(); r != nil {
  1388					if _, ok := r.(demangleErr); ok {
  1389						failed = true
  1390					} else {
  1391						panic(r)
  1392					}
  1393				}
  1394			}()
  1395	
  1396			args = st.templateArgs()
  1397		}()
  1398	
  1399		if !failed && len(st.str) > 0 && st.str[0] == 'I' {
  1400			if addSubst {
  1401				st.subs.add(tp)
  1402			}
  1403			return &Template{Name: tp, Args: args}
  1404		}
  1405		// Reset back to before we started reading the template arguments.
  1406		// They will be read again by st.prefix.
  1407		*st = *save
  1408		return tp
  1409	}
  1410	
  1411	// mergeQualifiers merges two qualifer lists into one.
  1412	func mergeQualifiers(q1, q2 Qualifiers) Qualifiers {
  1413		m := make(map[string]bool)
  1414		for _, qual := range q1 {
  1415			m[qual] = true
  1416		}
  1417		for _, qual := range q2 {
  1418			if !m[qual] {
  1419				q1 = append(q1, qual)
  1420				m[qual] = true
  1421			}
  1422		}
  1423		return q1
  1424	}
  1425	
  1426	// qualifiers maps from the character used in the mangled name to the
  1427	// string to print.
  1428	var qualifiers = map[byte]string{
  1429		'r': "restrict",
  1430		'V': "volatile",
  1431		'K': "const",
  1432	}
  1433	
  1434	// <CV-qualifiers> ::= [r] [V] [K]
  1435	func (st *state) cvQualifiers() Qualifiers {
  1436		var q Qualifiers
  1437		for len(st.str) > 0 {
  1438			if qv, ok := qualifiers[st.str[0]]; ok {
  1439				q = append([]string{qv}, q...)
  1440				st.advance(1)
  1441			} else if len(st.str) > 1 && st.str[:2] == "Dx" {
  1442				q = append([]string{"transaction_safe"}, q...)
  1443				st.advance(2)
  1444			} else {
  1445				break
  1446			}
  1447		}
  1448		return q
  1449	}
  1450	
  1451	// <ref-qualifier> ::= R
  1452	//                 ::= O
  1453	func (st *state) refQualifier() string {
  1454		if len(st.str) > 0 {
  1455			switch st.str[0] {
  1456			case 'R':
  1457				st.advance(1)
  1458				return "&"
  1459			case 'O':
  1460				st.advance(1)
  1461				return "&&"
  1462			}
  1463		}
  1464		return ""
  1465	}
  1466	
  1467	// <type>+
  1468	func (st *state) parmlist() []AST {
  1469		var ret []AST
  1470		for {
  1471			if len(st.str) < 1 {
  1472				break
  1473			}
  1474			if st.str[0] == 'E' || st.str[0] == '.' {
  1475				break
  1476			}
  1477			if (st.str[0] == 'R' || st.str[0] == 'O') && len(st.str) > 1 && st.str[1] == 'E' {
  1478				// This is a function ref-qualifier.
  1479				break
  1480			}
  1481			ptype := st.demangleType(false)
  1482			ret = append(ret, ptype)
  1483		}
  1484	
  1485		// There should always be at least one type.  A function that
  1486		// takes no arguments will have a single parameter type
  1487		// "void".
  1488		if len(ret) == 0 {
  1489			st.fail("expected at least one type in type list")
  1490		}
  1491	
  1492		// Omit a single parameter type void.
  1493		if len(ret) == 1 {
  1494			if bt, ok := ret[0].(*BuiltinType); ok && bt.Name == "void" {
  1495				ret = nil
  1496			}
  1497		}
  1498	
  1499		return ret
  1500	}
  1501	
  1502	// <function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E
  1503	func (st *state) functionType() AST {
  1504		st.checkChar('F')
  1505		if len(st.str) > 0 && st.str[0] == 'Y' {
  1506			// Function has C linkage.  We don't print this.
  1507			st.advance(1)
  1508		}
  1509		ret := st.bareFunctionType(true)
  1510		r := st.refQualifier()
  1511		if r != "" {
  1512			ret = &MethodWithQualifiers{Method: ret, Qualifiers: nil, RefQualifier: r}
  1513		}
  1514		if len(st.str) == 0 || st.str[0] != 'E' {
  1515			st.fail("expected E after function type")
  1516		}
  1517		st.advance(1)
  1518		return ret
  1519	}
  1520	
  1521	// <bare-function-type> ::= [J]<type>+
  1522	func (st *state) bareFunctionType(hasReturnType bool) AST {
  1523		if len(st.str) > 0 && st.str[0] == 'J' {
  1524			hasReturnType = true
  1525			st.advance(1)
  1526		}
  1527		var returnType AST
  1528		if hasReturnType {
  1529			returnType = st.demangleType(false)
  1530		}
  1531		types := st.parmlist()
  1532		return &FunctionType{Return: returnType, Args: types}
  1533	}
  1534	
  1535	// <array-type> ::= A <(positive dimension) number> _ <(element) type>
  1536	//              ::= A [<(dimension) expression>] _ <(element) type>
  1537	func (st *state) arrayType(isCast bool) AST {
  1538		st.checkChar('A')
  1539	
  1540		if len(st.str) == 0 {
  1541			st.fail("missing array dimension")
  1542		}
  1543	
  1544		var dim AST
  1545		if st.str[0] == '_' {
  1546			dim = &Name{Name: ""}
  1547		} else if isDigit(st.str[0]) {
  1548			i := 1
  1549			for len(st.str) > i && isDigit(st.str[i]) {
  1550				i++
  1551			}
  1552			dim = &Name{Name: st.str[:i]}
  1553			st.advance(i)
  1554		} else {
  1555			dim = st.expression()
  1556		}
  1557	
  1558		if len(st.str) == 0 || st.str[0] != '_' {
  1559			st.fail("expected _ after dimension")
  1560		}
  1561		st.advance(1)
  1562	
  1563		t := st.demangleType(isCast)
  1564	
  1565		arr := &ArrayType{Dimension: dim, Element: t}
  1566	
  1567		// Qualifiers on the element of an array type go on the whole
  1568		// array type.
  1569		if q, ok := arr.Element.(*TypeWithQualifiers); ok {
  1570			return &TypeWithQualifiers{Base: &ArrayType{Dimension: dim, Element: q.Base}, Qualifiers: q.Qualifiers}
  1571		}
  1572	
  1573		return arr
  1574	}
  1575	
  1576	// <vector-type> ::= Dv <number> _ <type>
  1577	//               ::= Dv _ <expression> _ <type>
  1578	func (st *state) vectorType(isCast bool) AST {
  1579		if len(st.str) == 0 {
  1580			st.fail("expected vector dimension")
  1581		}
  1582	
  1583		var dim AST
  1584		if st.str[0] == '_' {
  1585			st.advance(1)
  1586			dim = st.expression()
  1587		} else {
  1588			num := st.number()
  1589			dim = &Name{Name: fmt.Sprintf("%d", num)}
  1590		}
  1591	
  1592		if len(st.str) == 0 || st.str[0] != '_' {
  1593			st.fail("expected _ after vector dimension")
  1594		}
  1595		st.advance(1)
  1596	
  1597		t := st.demangleType(isCast)
  1598	
  1599		return &VectorType{Dimension: dim, Base: t}
  1600	}
  1601	
  1602	// <pointer-to-member-type> ::= M <(class) type> <(member) type>
  1603	func (st *state) pointerToMemberType(isCast bool) AST {
  1604		st.checkChar('M')
  1605		cl := st.demangleType(false)
  1606	
  1607		// The ABI says, "The type of a non-static member function is
  1608		// considered to be different, for the purposes of
  1609		// substitution, from the type of a namespace-scope or static
  1610		// member function whose type appears similar. The types of
  1611		// two non-static member functions are considered to be
  1612		// different, for the purposes of substitution, if the
  1613		// functions are members of different classes. In other words,
  1614		// for the purposes of substitution, the class of which the
  1615		// function is a member is considered part of the type of
  1616		// function."
  1617		//
  1618		// For a pointer to member function, this call to demangleType
  1619		// will end up adding a (possibly qualified) non-member
  1620		// function type to the substitution table, which is not
  1621		// correct; however, the member function type will never be
  1622		// used in a substitution, so putting the wrong type in the
  1623		// substitution table is harmless.
  1624		mem := st.demangleType(isCast)
  1625		return &PtrMem{Class: cl, Member: mem}
  1626	}
  1627	
  1628	// <non-negative number> _ */
  1629	func (st *state) compactNumber() int {
  1630		if len(st.str) == 0 {
  1631			st.fail("missing index")
  1632		}
  1633		if st.str[0] == '_' {
  1634			st.advance(1)
  1635			return 0
  1636		} else if st.str[0] == 'n' {
  1637			st.fail("unexpected negative number")
  1638		}
  1639		n := st.number()
  1640		if len(st.str) == 0 || st.str[0] != '_' {
  1641			st.fail("missing underscore after number")
  1642		}
  1643		st.advance(1)
  1644		return n + 1
  1645	}
  1646	
  1647	// <template-param> ::= T_
  1648	//                  ::= T <(parameter-2 non-negative) number> _
  1649	//
  1650	// When a template parameter is a substitution candidate, any
  1651	// reference to that substitution refers to the template parameter
  1652	// with the same index in the currently active template, not to
  1653	// whatever the template parameter would be expanded to here.  We sort
  1654	// this out in substitution and simplify.
  1655	func (st *state) templateParam() AST {
  1656		if len(st.templates) == 0 {
  1657			st.fail("template parameter not in scope of template")
  1658		}
  1659		off := st.off
  1660	
  1661		st.checkChar('T')
  1662		n := st.compactNumber()
  1663	
  1664		template := st.templates[len(st.templates)-1]
  1665	
  1666		if template == nil {
  1667			// We are parsing a cast operator.  If the cast is
  1668			// itself a template, then this is a forward
  1669			// reference.  Fill it in later.
  1670			return &TemplateParam{Index: n, Template: nil}
  1671		}
  1672	
  1673		if n >= len(template.Args) {
  1674			st.failEarlier(fmt.Sprintf("template index out of range (%d >= %d)", n, len(template.Args)), st.off-off)
  1675		}
  1676	
  1677		return &TemplateParam{Index: n, Template: template}
  1678	}
  1679	
  1680	// setTemplate sets the Template field of any TemplateParam's in a.
  1681	// This handles the forward referencing template parameters found in
  1682	// cast operators.
  1683	func (st *state) setTemplate(a AST, tmpl *Template) {
  1684		var seen []AST
  1685		a.Traverse(func(a AST) bool {
  1686			switch a := a.(type) {
  1687			case *TemplateParam:
  1688				if a.Template != nil {
  1689					if tmpl != nil {
  1690						st.fail("duplicate template parameters")
  1691					}
  1692					return false
  1693				}
  1694				if tmpl == nil {
  1695					st.fail("cast template parameter not in scope of template")
  1696				}
  1697				if a.Index >= len(tmpl.Args) {
  1698					st.fail(fmt.Sprintf("cast template index out of range (%d >= %d)", a.Index, len(tmpl.Args)))
  1699				}
  1700				a.Template = tmpl
  1701				return false
  1702			default:
  1703				for _, v := range seen {
  1704					if v == a {
  1705						return false
  1706					}
  1707				}
  1708				seen = append(seen, a)
  1709				return true
  1710			}
  1711		})
  1712	}
  1713	
  1714	// clearTemplateArgs gives an error for any unset Template field in
  1715	// args.  This handles erroneous cases where a cast operator with a
  1716	// forward referenced template is in the scope of another cast
  1717	// operator.
  1718	func (st *state) clearTemplateArgs(args []AST) {
  1719		for _, a := range args {
  1720			st.setTemplate(a, nil)
  1721		}
  1722	}
  1723	
  1724	// <template-args> ::= I <template-arg>+ E
  1725	func (st *state) templateArgs() []AST {
  1726		if len(st.str) == 0 || (st.str[0] != 'I' && st.str[0] != 'J') {
  1727			panic("internal error")
  1728		}
  1729		st.advance(1)
  1730	
  1731		var ret []AST
  1732		for len(st.str) == 0 || st.str[0] != 'E' {
  1733			arg := st.templateArg()
  1734			ret = append(ret, arg)
  1735		}
  1736		st.advance(1)
  1737		return ret
  1738	}
  1739	
  1740	// <template-arg> ::= <type>
  1741	//                ::= X <expression> E
  1742	//                ::= <expr-primary>
  1743	func (st *state) templateArg() AST {
  1744		if len(st.str) == 0 {
  1745			st.fail("missing template argument")
  1746		}
  1747		switch st.str[0] {
  1748		case 'X':
  1749			st.advance(1)
  1750			expr := st.expression()
  1751			if len(st.str) == 0 || st.str[0] != 'E' {
  1752				st.fail("missing end of expression")
  1753			}
  1754			st.advance(1)
  1755			return expr
  1756	
  1757		case 'L':
  1758			return st.exprPrimary()
  1759	
  1760		case 'I', 'J':
  1761			args := st.templateArgs()
  1762			return &ArgumentPack{Args: args}
  1763	
  1764		default:
  1765			return st.demangleType(false)
  1766		}
  1767	}
  1768	
  1769	// exprList parses a sequence of expressions up to a terminating character.
  1770	func (st *state) exprList(stop byte) AST {
  1771		if len(st.str) > 0 && st.str[0] == stop {
  1772			st.advance(1)
  1773			return &ExprList{Exprs: nil}
  1774		}
  1775	
  1776		var exprs []AST
  1777		for {
  1778			e := st.expression()
  1779			exprs = append(exprs, e)
  1780			if len(st.str) > 0 && st.str[0] == stop {
  1781				st.advance(1)
  1782				break
  1783			}
  1784		}
  1785		return &ExprList{Exprs: exprs}
  1786	}
  1787	
  1788	// <expression> ::= <(unary) operator-name> <expression>
  1789	//              ::= <(binary) operator-name> <expression> <expression>
  1790	//              ::= <(trinary) operator-name> <expression> <expression> <expression>
  1791	//              ::= cl <expression>+ E
  1792	//              ::= st <type>
  1793	//              ::= <template-param>
  1794	//              ::= sr <type> <unqualified-name>
  1795	//              ::= sr <type> <unqualified-name> <template-args>
  1796	//              ::= <expr-primary>
  1797	func (st *state) expression() AST {
  1798		if len(st.str) == 0 {
  1799			st.fail("expected expression")
  1800		}
  1801		if st.str[0] == 'L' {
  1802			return st.exprPrimary()
  1803		} else if st.str[0] == 'T' {
  1804			return st.templateParam()
  1805		} else if st.str[0] == 's' && len(st.str) > 1 && st.str[1] == 'r' {
  1806			st.advance(2)
  1807			if len(st.str) == 0 {
  1808				st.fail("expected unresolved type")
  1809			}
  1810			switch st.str[0] {
  1811			case 'T', 'D', 'S':
  1812				t := st.demangleType(false)
  1813				n := st.baseUnresolvedName()
  1814				n = &Qualified{Scope: t, Name: n, LocalName: false}
  1815				if len(st.str) > 0 && st.str[0] == 'I' {
  1816					args := st.templateArgs()
  1817					n = &Template{Name: n, Args: args}
  1818				}
  1819				return n
  1820			default:
  1821				var s AST
  1822				if st.str[0] == 'N' {
  1823					st.advance(1)
  1824					s = st.demangleType(false)
  1825				}
  1826				for len(st.str) == 0 || st.str[0] != 'E' {
  1827					// GCC does not seem to follow the ABI here.
  1828					// It can emit type/name without an 'E'.
  1829					if s != nil && len(st.str) > 0 && !isDigit(st.str[0]) {
  1830						if q, ok := s.(*Qualified); ok {
  1831							a := q.Scope
  1832							if t, ok := a.(*Template); ok {
  1833								st.subs.add(t.Name)
  1834								st.subs.add(t)
  1835							} else {
  1836								st.subs.add(a)
  1837							}
  1838							return s
  1839						}
  1840					}
  1841					n := st.sourceName()
  1842					if len(st.str) > 0 && st.str[0] == 'I' {
  1843						st.subs.add(n)
  1844						args := st.templateArgs()
  1845						n = &Template{Name: n, Args: args}
  1846					}
  1847					if s == nil {
  1848						s = n
  1849					} else {
  1850						s = &Qualified{Scope: s, Name: n, LocalName: false}
  1851					}
  1852					st.subs.add(s)
  1853				}
  1854				if s == nil {
  1855					st.fail("missing scope in unresolved name")
  1856				}
  1857				st.advance(1)
  1858				n := st.baseUnresolvedName()
  1859				return &Qualified{Scope: s, Name: n, LocalName: false}
  1860			}
  1861		} else if st.str[0] == 's' && len(st.str) > 1 && st.str[1] == 'p' {
  1862			st.advance(2)
  1863			e := st.expression()
  1864			pack := st.findArgumentPack(e)
  1865			return &PackExpansion{Base: e, Pack: pack}
  1866		} else if st.str[0] == 's' && len(st.str) > 1 && st.str[1] == 'Z' {
  1867			st.advance(2)
  1868			off := st.off
  1869			e := st.expression()
  1870			ap := st.findArgumentPack(e)
  1871			if ap == nil {
  1872				st.failEarlier("missing argument pack", st.off-off)
  1873			}
  1874			return &SizeofPack{Pack: ap}
  1875		} else if st.str[0] == 's' && len(st.str) > 1 && st.str[1] == 'P' {
  1876			st.advance(2)
  1877			var args []AST
  1878			for len(st.str) == 0 || st.str[0] != 'E' {
  1879				arg := st.templateArg()
  1880				args = append(args, arg)
  1881			}
  1882			st.advance(1)
  1883			return &SizeofArgs{Args: args}
  1884		} else if st.str[0] == 'f' && len(st.str) > 1 && st.str[1] == 'p' {
  1885			st.advance(2)
  1886			if len(st.str) > 0 && st.str[0] == 'T' {
  1887				st.advance(1)
  1888				return &FunctionParam{Index: 0}
  1889			} else {
  1890				index := st.compactNumber()
  1891				return &FunctionParam{Index: index + 1}
  1892			}
  1893		} else if isDigit(st.str[0]) || (st.str[0] == 'o' && len(st.str) > 1 && st.str[1] == 'n') {
  1894			if st.str[0] == 'o' {
  1895				// Skip operator function ID.
  1896				st.advance(2)
  1897			}
  1898			n, _ := st.unqualifiedName()
  1899			if len(st.str) > 0 && st.str[0] == 'I' {
  1900				args := st.templateArgs()
  1901				n = &Template{Name: n, Args: args}
  1902			}
  1903			return n
  1904		} else if (st.str[0] == 'i' || st.str[0] == 't') && len(st.str) > 1 && st.str[1] == 'l' {
  1905			// Brace-enclosed initializer list.
  1906			c := st.str[0]
  1907			st.advance(2)
  1908			var t AST
  1909			if c == 't' {
  1910				t = st.demangleType(false)
  1911			}
  1912			exprs := st.exprList('E')
  1913			return &InitializerList{Type: t, Exprs: exprs}
  1914		} else if st.str[0] == 's' && len(st.str) > 1 && st.str[1] == 't' {
  1915			o, _ := st.operatorName(true)
  1916			t := st.demangleType(false)
  1917			return &Unary{Op: o, Expr: t, Suffix: false, SizeofType: true}
  1918		} else {
  1919			if len(st.str) < 2 {
  1920				st.fail("missing operator code")
  1921			}
  1922			code := st.str[:2]
  1923			o, args := st.operatorName(true)
  1924			switch args {
  1925			case 0:
  1926				return &Nullary{Op: o}
  1927	
  1928			case 1:
  1929				suffix := false
  1930				if code == "pp" || code == "mm" {
  1931					if len(st.str) > 0 && st.str[0] == '_' {
  1932						st.advance(1)
  1933					} else {
  1934						suffix = true
  1935					}
  1936				}
  1937				var operand AST
  1938				if _, ok := o.(*Cast); ok && len(st.str) > 0 && st.str[0] == '_' {
  1939					st.advance(1)
  1940					operand = st.exprList('E')
  1941				} else {
  1942					operand = st.expression()
  1943				}
  1944				return &Unary{Op: o, Expr: operand, Suffix: suffix, SizeofType: false}
  1945	
  1946			case 2:
  1947				var left, right AST
  1948				if code == "sc" || code == "dc" || code == "cc" || code == "rc" {
  1949					left = st.demangleType(false)
  1950				} else if code[0] == 'f' {
  1951					left, _ = st.operatorName(true)
  1952					right = st.expression()
  1953					return &Fold{Left: code[1] == 'l', Op: left, Arg1: right, Arg2: nil}
  1954				} else {
  1955					left = st.expression()
  1956				}
  1957				if code == "cl" {
  1958					right = st.exprList('E')
  1959				} else if code == "dt" || code == "pt" {
  1960					right, _ = st.unqualifiedName()
  1961					if len(st.str) > 0 && st.str[0] == 'I' {
  1962						args := st.templateArgs()
  1963						right = &Template{Name: right, Args: args}
  1964					}
  1965				} else {
  1966					right = st.expression()
  1967				}
  1968				return &Binary{Op: o, Left: left, Right: right}
  1969	
  1970			case 3:
  1971				if code[0] == 'n' {
  1972					if code[1] != 'w' && code[1] != 'a' {
  1973						panic("internal error")
  1974					}
  1975					place := st.exprList('_')
  1976					if place.(*ExprList).Exprs == nil {
  1977						place = nil
  1978					}
  1979					t := st.demangleType(false)
  1980					var ini AST
  1981					if len(st.str) > 0 && st.str[0] == 'E' {
  1982						st.advance(1)
  1983					} else if len(st.str) > 1 && st.str[0] == 'p' && st.str[1] == 'i' {
  1984						// Parenthesized initializer.
  1985						st.advance(2)
  1986						ini = st.exprList('E')
  1987					} else if len(st.str) > 1 && st.str[0] == 'i' && st.str[1] == 'l' {
  1988						// Initializer list.
  1989						ini = st.expression()
  1990					} else {
  1991						st.fail("unrecognized new initializer")
  1992					}
  1993					return &New{Op: o, Place: place, Type: t, Init: ini}
  1994				} else if code[0] == 'f' {
  1995					first, _ := st.operatorName(true)
  1996					second := st.expression()
  1997					third := st.expression()
  1998					return &Fold{Left: code[1] == 'L', Op: first, Arg1: second, Arg2: third}
  1999				} else {
  2000					first := st.expression()
  2001					second := st.expression()
  2002					third := st.expression()
  2003					return &Trinary{Op: o, First: first, Second: second, Third: third}
  2004				}
  2005	
  2006			default:
  2007				st.fail(fmt.Sprintf("unsupported number of operator arguments: %d", args))
  2008				panic("not reached")
  2009			}
  2010		}
  2011	}
  2012	
  2013	// <base-unresolved-name> ::= <simple-id>
  2014	//                        ::= on <operator-name>
  2015	//                        ::= on <operator-name> <template-args>
  2016	//                        ::= dn <destructor-name>
  2017	//
  2018	//<simple-id> ::= <source-name> [ <template-args> ]
  2019	func (st *state) baseUnresolvedName() AST {
  2020		var n AST
  2021		if len(st.str) >= 2 && st.str[:2] == "on" {
  2022			st.advance(2)
  2023			n, _ = st.operatorName(true)
  2024		} else if len(st.str) >= 2 && st.str[:2] == "dn" {
  2025			st.advance(2)
  2026			if len(st.str) > 0 && isDigit(st.str[0]) {
  2027				n = st.sourceName()
  2028			} else {
  2029				n = st.demangleType(false)
  2030			}
  2031			n = &Destructor{Name: n}
  2032		} else if len(st.str) > 0 && isDigit(st.str[0]) {
  2033			n = st.sourceName()
  2034		} else {
  2035			// GCC seems to not follow the ABI here: it can have
  2036			// an operator name without on.
  2037			// See https://gcc.gnu.org/PR70182.
  2038			n, _ = st.operatorName(true)
  2039		}
  2040		if len(st.str) > 0 && st.str[0] == 'I' {
  2041			args := st.templateArgs()
  2042			n = &Template{Name: n, Args: args}
  2043		}
  2044		return n
  2045	}
  2046	
  2047	// <expr-primary> ::= L <type> <(value) number> E
  2048	//                ::= L <type> <(value) float> E
  2049	//                ::= L <mangled-name> E
  2050	func (st *state) exprPrimary() AST {
  2051		st.checkChar('L')
  2052		if len(st.str) == 0 {
  2053			st.fail("expected primary expression")
  2054	
  2055		}
  2056	
  2057		// Check for 'Z' here because g++ incorrectly omitted the
  2058		// underscore until -fabi-version=3.
  2059		var ret AST
  2060		if st.str[0] == '_' || st.str[0] == 'Z' {
  2061			if st.str[0] == '_' {
  2062				st.advance(1)
  2063			}
  2064			if len(st.str) == 0 || st.str[0] != 'Z' {
  2065				st.fail("expected mangled name")
  2066			}
  2067			st.advance(1)
  2068			ret = st.encoding(true)
  2069		} else {
  2070			t := st.demangleType(false)
  2071	
  2072			neg := false
  2073			if len(st.str) > 0 && st.str[0] == 'n' {
  2074				neg = true
  2075				st.advance(1)
  2076			}
  2077			i := 0
  2078			for len(st.str) > i && st.str[i] != 'E' {
  2079				i++
  2080			}
  2081			val := st.str[:i]
  2082			st.advance(i)
  2083			ret = &Literal{Type: t, Val: val, Neg: neg}
  2084		}
  2085		if len(st.str) == 0 || st.str[0] != 'E' {
  2086			st.fail("expected E after literal")
  2087		}
  2088		st.advance(1)
  2089		return ret
  2090	}
  2091	
  2092	// <discriminator> ::= _ <(non-negative) number>
  2093	func (st *state) discriminator(a AST) AST {
  2094		if len(st.str) == 0 || st.str[0] != '_' {
  2095			return a
  2096		}
  2097		off := st.off
  2098		st.advance(1)
  2099		d := st.number()
  2100		if d < 0 {
  2101			st.failEarlier("invalid negative discriminator", st.off-off)
  2102		}
  2103		// We don't currently print out the discriminator, so we don't
  2104		// save it.
  2105		return a
  2106	}
  2107	
  2108	// <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
  2109	func (st *state) closureTypeName() AST {
  2110		st.checkChar('U')
  2111		st.checkChar('l')
  2112		types := st.parmlist()
  2113		if len(st.str) == 0 || st.str[0] != 'E' {
  2114			st.fail("expected E after closure type name")
  2115		}
  2116		st.advance(1)
  2117		num := st.compactNumber()
  2118		ret := &Closure{Types: types, Num: num}
  2119		st.subs.add(ret)
  2120		return ret
  2121	}
  2122	
  2123	// <unnamed-type-name> ::= Ut [ <nonnegative number> ] _
  2124	func (st *state) unnamedTypeName() AST {
  2125		st.checkChar('U')
  2126		st.checkChar('t')
  2127		num := st.compactNumber()
  2128		ret := &UnnamedType{Num: num}
  2129		st.subs.add(ret)
  2130		return ret
  2131	}
  2132	
  2133	// Recognize a clone suffix.  These are not part of the mangling API,
  2134	// but are added by GCC when cloning functions.
  2135	func (st *state) cloneSuffix(a AST) AST {
  2136		i := 0
  2137		if len(st.str) > 1 && st.str[0] == '.' && (isLower(st.str[1]) || st.str[1] == '_') {
  2138			i += 2
  2139			for len(st.str) > i && (isLower(st.str[i]) || st.str[i] == '_') {
  2140				i++
  2141			}
  2142		}
  2143		for len(st.str) > i+1 && st.str[i] == '.' && isDigit(st.str[i+1]) {
  2144			i += 2
  2145			for len(st.str) > i && isDigit(st.str[i]) {
  2146				i++
  2147			}
  2148		}
  2149		suffix := st.str[:i]
  2150		st.advance(i)
  2151		return &Clone{Base: a, Suffix: suffix}
  2152	}
  2153	
  2154	// substitutions is the list of substitution candidates that may
  2155	// appear later in the string.
  2156	type substitutions []AST
  2157	
  2158	// add adds a new substitution candidate.
  2159	func (subs *substitutions) add(a AST) {
  2160		*subs = append(*subs, a)
  2161	}
  2162	
  2163	// subAST maps standard substitution codes to the corresponding AST.
  2164	var subAST = map[byte]AST{
  2165		't': &Name{Name: "std"},
  2166		'a': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "allocator"}},
  2167		'b': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "basic_string"}},
  2168		's': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "string"}},
  2169		'i': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "istream"}},
  2170		'o': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "ostream"}},
  2171		'd': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "iostream"}},
  2172	}
  2173	
  2174	// verboseAST maps standard substitution codes to the long form of the
  2175	// corresponding AST.  We use this when the Verbose option is used, to
  2176	// match the standard demangler.
  2177	var verboseAST = map[byte]AST{
  2178		't': &Name{Name: "std"},
  2179		'a': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "allocator"}},
  2180		'b': &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "basic_string"}},
  2181	
  2182		// std::basic_string<char, std::char_traits<char>, std::allocator<char> >
  2183		's': &Template{
  2184			Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "basic_string"}},
  2185			Args: []AST{
  2186				&BuiltinType{Name: "char"},
  2187				&Template{
  2188					Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "char_traits"}},
  2189					Args: []AST{&BuiltinType{Name: "char"}}},
  2190				&Template{
  2191					Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "allocator"}},
  2192					Args: []AST{&BuiltinType{Name: "char"}}}}},
  2193		// std::basic_istream<char, std::char_traits<char> >
  2194		'i': &Template{
  2195			Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "basic_istream"}},
  2196			Args: []AST{
  2197				&BuiltinType{Name: "char"},
  2198				&Template{
  2199					Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "char_traits"}},
  2200					Args: []AST{&BuiltinType{Name: "char"}}}}},
  2201		// std::basic_ostream<char, std::char_traits<char> >
  2202		'o': &Template{
  2203			Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "basic_ostream"}},
  2204			Args: []AST{
  2205				&BuiltinType{Name: "char"},
  2206				&Template{
  2207					Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "char_traits"}},
  2208					Args: []AST{&BuiltinType{Name: "char"}}}}},
  2209		// std::basic_iostream<char, std::char_traits<char> >
  2210		'd': &Template{
  2211			Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "basic_iostream"}},
  2212			Args: []AST{
  2213				&BuiltinType{Name: "char"},
  2214				&Template{
  2215					Name: &Qualified{Scope: &Name{Name: "std"}, Name: &Name{Name: "char_traits"}},
  2216					Args: []AST{&BuiltinType{Name: "char"}}}}},
  2217	}
  2218	
  2219	// <substitution> ::= S <seq-id> _
  2220	//                ::= S_
  2221	//                ::= St
  2222	//                ::= Sa
  2223	//                ::= Sb
  2224	//                ::= Ss
  2225	//                ::= Si
  2226	//                ::= So
  2227	//                ::= Sd
  2228	func (st *state) substitution(forPrefix bool) AST {
  2229		st.checkChar('S')
  2230		if len(st.str) == 0 {
  2231			st.fail("missing substitution index")
  2232		}
  2233		c := st.str[0]
  2234		st.advance(1)
  2235		dec := 1
  2236		if c == '_' || isDigit(c) || isUpper(c) {
  2237			id := 0
  2238			if c != '_' {
  2239				for c != '_' {
  2240					// Don't overflow a 32-bit int.
  2241					if id >= 0x80000000/36-36 {
  2242						st.fail("substitution index overflow")
  2243					}
  2244					if isDigit(c) {
  2245						id = id*36 + int(c-'0')
  2246					} else if isUpper(c) {
  2247						id = id*36 + int(c-'A') + 10
  2248					} else {
  2249						st.fail("invalid character in substitution index")
  2250					}
  2251	
  2252					if len(st.str) == 0 {
  2253						st.fail("missing end to substitution index")
  2254					}
  2255					c = st.str[0]
  2256					st.advance(1)
  2257					dec++
  2258				}
  2259				id++
  2260			}
  2261	
  2262			if id >= len(st.subs) {
  2263				st.failEarlier(fmt.Sprintf("substitution index out of range (%d >= %d)", id, len(st.subs)), dec)
  2264			}
  2265	
  2266			ret := st.subs[id]
  2267	
  2268			// We need to update any references to template
  2269			// parameters to refer to the currently active
  2270			// template.
  2271			copy := func(a AST) AST {
  2272				tp, ok := a.(*TemplateParam)
  2273				if !ok {
  2274					return nil
  2275				}
  2276				if len(st.templates) == 0 {
  2277					st.failEarlier("substituted template parameter not in scope of template", dec)
  2278				}
  2279				template := st.templates[len(st.templates)-1]
  2280				if template == nil {
  2281					// This template parameter is within
  2282					// the scope of a cast operator.
  2283					return &TemplateParam{Index: tp.Index, Template: nil}
  2284				}
  2285	
  2286				if tp.Index >= len(template.Args) {
  2287					st.failEarlier(fmt.Sprintf("substituted template index out of range (%d >= %d)", tp.Index, len(template.Args)), dec)
  2288				}
  2289	
  2290				return &TemplateParam{Index: tp.Index, Template: template}
  2291			}
  2292			var seen []AST
  2293			skip := func(a AST) bool {
  2294				if _, ok := a.(*Typed); ok {
  2295					return true
  2296				}
  2297				for _, v := range seen {
  2298					if v == a {
  2299						return true
  2300					}
  2301				}
  2302				seen = append(seen, a)
  2303				return false
  2304			}
  2305			if c := ret.Copy(copy, skip); c != nil {
  2306				return c
  2307			}
  2308	
  2309			return ret
  2310		} else {
  2311			m := subAST
  2312			if st.verbose {
  2313				m = verboseAST
  2314			}
  2315			// For compatibility with the standard demangler, use
  2316			// a longer name for a constructor or destructor.
  2317			if forPrefix && len(st.str) > 0 && (st.str[0] == 'C' || st.str[0] == 'D') {
  2318				m = verboseAST
  2319			}
  2320			a, ok := m[c]
  2321			if !ok {
  2322				st.failEarlier("unrecognized substitution code", 1)
  2323			}
  2324	
  2325			if len(st.str) > 0 && st.str[0] == 'B' {
  2326				a = st.taggedName(a)
  2327			}
  2328	
  2329			return a
  2330		}
  2331	}
  2332	
  2333	// isDigit returns whetner c is a digit for demangling purposes.
  2334	func isDigit(c byte) bool {
  2335		return c >= '0' && c <= '9'
  2336	}
  2337	
  2338	// isUpper returns whether c is an upper case letter for demangling purposes.
  2339	func isUpper(c byte) bool {
  2340		return c >= 'A' && c <= 'Z'
  2341	}
  2342	
  2343	// isLower returns whether c is a lower case letter for demangling purposes.
  2344	func isLower(c byte) bool {
  2345		return c >= 'a' && c <= 'z'
  2346	}
  2347	
  2348	// simplify replaces template parameters with their expansions, and
  2349	// merges qualifiers.
  2350	func simplify(a AST) AST {
  2351		var seen []AST
  2352		skip := func(a AST) bool {
  2353			for _, v := range seen {
  2354				if v == a {
  2355					return true
  2356				}
  2357			}
  2358			seen = append(seen, a)
  2359			return false
  2360		}
  2361		if r := a.Copy(simplifyOne, skip); r != nil {
  2362			return r
  2363		}
  2364		return a
  2365	}
  2366	
  2367	// simplifyOne simplifies a single AST.  It returns nil if there is
  2368	// nothing to do.
  2369	func simplifyOne(a AST) AST {
  2370		switch a := a.(type) {
  2371		case *TemplateParam:
  2372			if a.Template != nil && a.Index < len(a.Template.Args) {
  2373				return a.Template.Args[a.Index]
  2374			}
  2375		case *MethodWithQualifiers:
  2376			if m, ok := a.Method.(*MethodWithQualifiers); ok {
  2377				ref := a.RefQualifier
  2378				if ref == "" {
  2379					ref = m.RefQualifier
  2380				} else if m.RefQualifier != "" {
  2381					if ref == "&" || m.RefQualifier == "&" {
  2382						ref = "&"
  2383					}
  2384				}
  2385				return &MethodWithQualifiers{Method: m.Method, Qualifiers: mergeQualifiers(a.Qualifiers, m.Qualifiers), RefQualifier: ref}
  2386			}
  2387			if t, ok := a.Method.(*TypeWithQualifiers); ok {
  2388				return &MethodWithQualifiers{Method: t.Base, Qualifiers: mergeQualifiers(a.Qualifiers, t.Qualifiers), RefQualifier: a.RefQualifier}
  2389			}
  2390		case *TypeWithQualifiers:
  2391			if ft, ok := a.Base.(*FunctionType); ok {
  2392				return &MethodWithQualifiers{Method: ft, Qualifiers: a.Qualifiers, RefQualifier: ""}
  2393			}
  2394			if t, ok := a.Base.(*TypeWithQualifiers); ok {
  2395				return &TypeWithQualifiers{Base: t.Base, Qualifiers: mergeQualifiers(a.Qualifiers, t.Qualifiers)}
  2396			}
  2397			if m, ok := a.Base.(*MethodWithQualifiers); ok {
  2398				return &MethodWithQualifiers{Method: m.Method, Qualifiers: mergeQualifiers(a.Qualifiers, m.Qualifiers), RefQualifier: m.RefQualifier}
  2399			}
  2400		case *ReferenceType:
  2401			if rt, ok := a.Base.(*ReferenceType); ok {
  2402				return rt
  2403			}
  2404			if rrt, ok := a.Base.(*RvalueReferenceType); ok {
  2405				return &ReferenceType{Base: rrt.Base}
  2406			}
  2407		case *RvalueReferenceType:
  2408			if rrt, ok := a.Base.(*RvalueReferenceType); ok {
  2409				return rrt
  2410			}
  2411			if rt, ok := a.Base.(*ReferenceType); ok {
  2412				return rt
  2413			}
  2414		case *ArrayType:
  2415			// Qualifiers on the element of an array type
  2416			// go on the whole array type.
  2417			if q, ok := a.Element.(*TypeWithQualifiers); ok {
  2418				return &TypeWithQualifiers{
  2419					Base:       &ArrayType{Dimension: a.Dimension, Element: q.Base},
  2420					Qualifiers: q.Qualifiers,
  2421				}
  2422			}
  2423		case *PackExpansion:
  2424			// Expand the pack and replace it with a list of
  2425			// expressions.
  2426			if a.Pack != nil {
  2427				exprs := make([]AST, len(a.Pack.Args))
  2428				for i, arg := range a.Pack.Args {
  2429					copy := func(sub AST) AST {
  2430						// Replace the ArgumentPack
  2431						// with a specific argument.
  2432						if sub == a.Pack {
  2433							return arg
  2434						}
  2435						// Copy everything else.
  2436						return nil
  2437					}
  2438	
  2439					var seen []AST
  2440					skip := func(sub AST) bool {
  2441						// Don't traverse into another
  2442						// pack expansion.
  2443						if _, ok := sub.(*PackExpansion); ok {
  2444							return true
  2445						}
  2446						for _, v := range seen {
  2447							if v == sub {
  2448								return true
  2449							}
  2450						}
  2451						seen = append(seen, sub)
  2452						return false
  2453					}
  2454	
  2455					b := a.Base.Copy(copy, skip)
  2456					if b == nil {
  2457						b = a.Base
  2458					}
  2459					exprs[i] = simplify(b)
  2460				}
  2461				return &ExprList{Exprs: exprs}
  2462			}
  2463		}
  2464		return nil
  2465	}
  2466	
  2467	// findArgumentPack walks the AST looking for the argument pack for a
  2468	// pack expansion.  We find it via a template parameter.
  2469	func (st *state) findArgumentPack(a AST) *ArgumentPack {
  2470		var seen []AST
  2471		var ret *ArgumentPack
  2472		a.Traverse(func(a AST) bool {
  2473			if ret != nil {
  2474				return false
  2475			}
  2476			switch a := a.(type) {
  2477			case *TemplateParam:
  2478				if a.Template == nil || a.Index >= len(a.Template.Args) {
  2479					return true
  2480				}
  2481				if pack, ok := a.Template.Args[a.Index].(*ArgumentPack); ok {
  2482					ret = pack
  2483					return false
  2484				}
  2485			case *PackExpansion, *Closure, *Name:
  2486				return false
  2487			case *TaggedName, *Operator, *BuiltinType, *FunctionParam:
  2488				return false
  2489			case *UnnamedType, *FixedType, *DefaultArg:
  2490				return false
  2491			}
  2492			for _, v := range seen {
  2493				if v == a {
  2494					return false
  2495				}
  2496			}
  2497			seen = append(seen, a)
  2498			return true
  2499		})
  2500		return ret
  2501	}
  2502	

View as plain text