cpp_demangle 0.2.16

//! Abstract syntax tree types for mangled symbols.

use super::{DemangleWrite, DemangleNodeType, DemangleOptions};
use error::{self, Result};
use index_str::IndexStr;
use std::cell::Cell;
#[cfg(feature = "logging")]
use std::cell::RefCell;
use std::fmt::{self, Write};
use std::hash::{Hash, Hasher};
use std::mem;
use std::ops;
use std::ptr;
use subs::{Substitutable, SubstitutionTable};
use string::String;
use vec::Vec;
use boxed::Box;

struct AutoLogParse;

#[cfg(feature = "logging")]
thread_local! {
    static LOG_DEPTH: RefCell<usize> = RefCell::new(0);
}

impl AutoLogParse {
    #[cfg(feature = "logging")]
    fn new(production: &'static str, input: IndexStr<'_>) -> AutoLogParse {
        LOG_DEPTH.with(|depth| {
            if *depth.borrow() == 0 {
                println!();
            }

            let indent: String = (0..*depth.borrow() * 4).map(|_| ' ').collect();
            log!(
                "{}({} \"{}\"",
                indent,
                production,
                String::from_utf8_lossy(input.as_ref())
            );
            *depth.borrow_mut() += 1;
        });
        AutoLogParse
    }

    #[cfg(not(feature = "logging"))]
    #[inline(always)]
    fn new(_: &'static str, _: IndexStr) -> AutoLogParse {
        AutoLogParse
    }
}

#[cfg(feature = "logging")]
impl Drop for AutoLogParse {
    fn drop(&mut self) {
        LOG_DEPTH.with(|depth| {
            *depth.borrow_mut() -= 1;
            let indent: String = (0..*depth.borrow() * 4).map(|_| ' ').collect();
            log!("{})", indent);
        });
    }
}

/// Performs the two operations that begin every parse:
///
/// 1. Keeps track of recursion levels and early returns with an error if there
///    is too much recursion.
///
/// 2. Automatically log start and end parsing in an s-expression format, when the
///    `logging` feature is enabled.
macro_rules! try_begin_parse {
    ( $production:expr , $ctx:expr , $input:expr ) => {
        let _log = AutoLogParse::new($production, $input);
        let _auto_check_recursion = AutoParseRecursion::new($ctx)?;
    }
}

struct AutoLogDemangle;

impl AutoLogDemangle {
    #[cfg(feature = "logging")]
    fn new<P, W>(
        production: &P,
        ctx: &DemangleContext<W>,
        scope: Option<ArgScopeStack>,
        is_inner: bool,
    ) -> AutoLogDemangle
    where
        P: ?Sized + fmt::Debug,
        W: DemangleWrite,
    {
        LOG_DEPTH.with(|depth| {
            if *depth.borrow() == 0 {
                println!();
            }

            let indent: String = (0..*depth.borrow() * 4).map(|_| ' ').collect();
            log!("{}(", indent);
            log!(
                "{}  {}{:?}",
                indent,
                if is_inner { "as_inner: " } else { "" },
                production
            );
            log!("{}  inner = {:?}", indent, ctx.inner);
            log!("{}  scope = {:?}", indent, scope);

            *depth.borrow_mut() += 1;
        });
        AutoLogDemangle
    }

    #[cfg(not(feature = "logging"))]
    #[inline(always)]
    fn new<P, W>(
        _: &P,
        _: &DemangleContext<W>,
        _: Option<ArgScopeStack>,
        _: bool,
    ) -> AutoLogDemangle
    where
        P: ?Sized + fmt::Debug,
        W: DemangleWrite,
    {
        AutoLogDemangle
    }
}

#[cfg(feature = "logging")]
impl Drop for AutoLogDemangle {
    fn drop(&mut self) {
        LOG_DEPTH.with(|depth| {
            *depth.borrow_mut() -= 1;
            let indent: String = (0..*depth.borrow() * 4).map(|_| ' ').collect();
            log!("{})", indent);
        });
    }
}

/// Automatically log start and end demangling in an s-expression format, when
/// the `logging` feature is enabled.
macro_rules! try_begin_demangle {
    ( $production:expr, $ctx:expr, $scope:expr ) => {{
        let _log = AutoLogDemangle::new($production, $ctx, $scope, false);
        &mut AutoParseDemangle::new($ctx)?
    }}
}

/// Automatically log start and end demangling in an s-expression format, when
/// the `logging` feature is enabled.
macro_rules! try_begin_demangle_as_inner {
    ( $production:expr, $ctx:expr, $scope:expr ) => {{
        let _log = AutoLogDemangle::new($production, $ctx, $scope, true);
        &mut AutoParseDemangle::new($ctx)?
    }}
}

#[derive(Debug, Default, Clone, Copy)]
struct ParseContextState {
    // The current recursion level. Should always be less than or equal to the
    // maximum.
    recursion_level: u32,
    // Whether or not we are currently parsing a conversion operator.
    in_conversion: bool,
}

/// Common context needed when parsing.
#[derive(Debug, Clone)]
pub struct ParseContext {
    // Maximum amount of recursive parsing calls we will allow. If this is too
    // large, we can blow the stack.
    max_recursion: u32,
    // Mutable state within the `ParseContext`.
    state: Cell<ParseContextState>,
}

impl Default for ParseContext {
    fn default() -> ParseContext {
        ParseContext {
            max_recursion: 64,
            state: Cell::new(ParseContextState::default()),
        }
    }
}

impl ParseContext {
    /// Get the current recursion level for this context.
    pub fn recursion_level(&self) -> u32 {
        self.state.get().recursion_level
    }

    #[inline]
    fn enter_recursion(&self) -> error::Result<()> {
        let mut state = self.state.get();
        let new_recursion_level = state.recursion_level + 1;

        if new_recursion_level >= self.max_recursion {
            log!("Hit too much recursion at level {}", self.max_recursion);
            Err(error::Error::TooMuchRecursion)
        } else {
            state.recursion_level = new_recursion_level;
            self.state.set(state);
            Ok(())
        }
    }

    #[inline]
    fn exit_recursion(&self) {
        let mut state = self.state.get();
        debug_assert!(state.recursion_level >= 1);
        state.recursion_level -= 1;
        self.state.set(state);
    }

    #[inline]
    fn in_conversion(&self) -> bool {
        self.state.get().in_conversion
    }

    fn set_in_conversion(&self, in_conversion: bool) -> bool {
        let mut state = self.state.get();
        let previously_in_conversion = state.in_conversion;
        state.in_conversion = in_conversion;
        self.state.set(state);
        previously_in_conversion
    }
}

/// An RAII type to automatically check the recursion level against the
/// maximum. If the maximum has been crossed, return an error. Otherwise,
/// increment the level upon construction, and decrement it upon destruction.
struct AutoParseRecursion<'a>(&'a ParseContext);

impl<'a> AutoParseRecursion<'a> {
    #[inline]
    fn new(ctx: &'a ParseContext) -> error::Result<AutoParseRecursion<'a>> {
        ctx.enter_recursion()?;
        Ok(AutoParseRecursion(ctx))
    }
}

impl<'a> Drop for AutoParseRecursion<'a> {
    #[inline]
    fn drop(&mut self) {
        self.0.exit_recursion();
    }
}

/// A trait for anything that can be parsed from an `IndexStr` and return a
/// `Result` of the parsed `Self` value and the rest of the `IndexStr` input
/// that has not been consumed in parsing the `Self` value.
///
/// For AST types representing productions which have `<substitution>` as a
/// possible right hand side, do not implement this trait directly. Instead,
/// make a newtype over `usize`, parse either the `<substitution>` back
/// reference or "real" value, insert the "real" value into the substitution
/// table if needed, and *always* return the newtype index into the substitution
/// table.
#[doc(hidden)]
pub trait Parse: Sized {
    /// Parse the `Self` value from `input` and return it, updating the
    /// substitution table as needed.
    fn parse<'a, 'b>(
        ctx: &'a ParseContext,
        subs: &'a mut SubstitutionTable,
        input: IndexStr<'b>,
    ) -> Result<(Self, IndexStr<'b>)>;
}

/// Determine whether this AST node is an instantiated[*] template function, and
/// get its concrete template arguments.
///
/// [*] Note that we will never see an abstract, un-instantiated template
/// function, since they don't end up in object files and don't get mangled
/// names.
trait GetTemplateArgs {
    /// Returns `Some` if this is a template function, `None` otherwise.
    fn get_template_args<'a>(&'a self, subs: &'a SubstitutionTable) -> Option<&'a TemplateArgs>;
}

/// A leaf name is the part the name that describes some type or class without
/// any leading namespace qualifiers.
///
/// This is used when figuring out how to format constructors and destructors,
/// which are formatted as `gooble::dodo::Thing::~Thing()` but we don't have
/// direct access to `Thing` in the `CtorDtorName` AST.
#[derive(Debug)]
pub(crate) enum LeafName<'a> {
    SourceName(&'a SourceName),
    WellKnownComponent(&'a WellKnownComponent),
    Closure(&'a ClosureTypeName),
    UnnamedType(&'a UnnamedTypeName),
}

impl<'subs, W> DemangleAsLeaf<'subs, W> for LeafName<'subs>
where
    W: 'subs + DemangleWrite,
{
    fn demangle_as_leaf<'me, 'ctx>(
        &'me self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
    ) -> fmt::Result {
        match *self {
            LeafName::SourceName(sn) => sn.demangle(ctx, None),
            LeafName::Closure(c) => c.demangle(ctx, None),
            LeafName::WellKnownComponent(wkc) => wkc.demangle_as_leaf(ctx),
            LeafName::UnnamedType(utn) => utn.demangle_as_leaf(ctx),
        }
    }
}

/// Determine whether this AST node is some kind (potentially namespaced) name
/// and if so get its leaf name.
pub(crate) trait GetLeafName<'a> {
    fn get_leaf_name(&'a self, subs: &'a SubstitutionTable) -> Option<LeafName<'a>>;
}

/// Determine whether this AST node is a constructor, destructor, or conversion
/// function.
pub(crate) trait IsCtorDtorConversion {
    fn is_ctor_dtor_conversion(&self, subs: &SubstitutionTable) -> bool;
}

/// When formatting a mangled symbol's parsed AST as a demangled symbol, we need
/// to resolve indirect references to template and function arguments with
/// direct `TemplateArg` and `Type` references respectively.
///
/// Note that which set of arguments are implicitly referenced change as we
/// enter and leave different functions' scope. One might usually use de Brujin
/// indices to keep arguments within scopes separated from each other, but the
/// Itanium C++ ABI does not allow us the luxury. AFAIK, when the ABI was first
/// drafted, C++ did not have lambdas, and the issue did not come up at all
/// since a function simply couldn't refer to the types of closed over
/// variables.
///
/// This trait is implemented by anything that can potentially resolve arguments
/// for us.
trait ArgScope<'me, 'ctx>: fmt::Debug {
    /// Get the current scope's leaf name.
    fn leaf_name(&'me self) -> Result<LeafName<'ctx>>;

    /// Get the current scope's `index`th template argument.
    fn get_template_arg(&'me self, index: usize) -> Result<(&'ctx TemplateArg, &'ctx TemplateArgs)>;

    /// Get the current scope's `index`th function argument's type.
    fn get_function_arg(&'me self, index: usize) -> Result<&'ctx Type>;
}

/// An `ArgScopeStack` represents the current function and template demangling
/// scope we are within. As we enter new demangling scopes, we construct new
/// `ArgScopeStack`s whose `prev` references point back to the old ones. These
/// `ArgScopeStack`s are kept on the native stack, and as functions return, they
/// go out of scope and we use the previous `ArgScopeStack`s again.
#[derive(Copy, Clone, Debug)]
pub struct ArgScopeStack<'prev, 'subs>
where
    'subs: 'prev,
{
    item: &'subs dyn ArgScope<'subs, 'subs>,
    in_arg: Option<(usize, &'subs TemplateArgs)>,
    prev: Option<&'prev ArgScopeStack<'prev, 'subs>>,
}

/// When we first begin demangling, we haven't entered any function or template
/// demangling scope and we don't have any useful `ArgScopeStack`. Therefore, we
/// are never actually dealing with `ArgScopeStack` directly in practice, but
/// always an `Option<ArgScopeStack>` instead. Nevertheless, we want to define
/// useful methods on `Option<ArgScopeStack>`.
///
/// A custom "extension" trait with exactly one implementor: Rust's principled
/// monkey patching!
trait ArgScopeStackExt<'prev, 'subs>: Copy {
    /// Push a new `ArgScope` onto this `ArgScopeStack` and return the new
    /// `ArgScopeStack` with the pushed resolver on top.
    fn push(
        &'prev self,
        item: &'subs dyn ArgScope<'subs, 'subs>,
    ) -> Option<ArgScopeStack<'prev, 'subs>>;
}

impl<'prev, 'subs> ArgScopeStackExt<'prev, 'subs> for Option<ArgScopeStack<'prev, 'subs>> {
    fn push(
        &'prev self,
        item: &'subs dyn ArgScope<'subs, 'subs>,
    ) -> Option<ArgScopeStack<'prev, 'subs>> {
        log!("ArgScopeStack::push: {:?}", item);
        Some(ArgScopeStack {
            prev: self.as_ref(),
            in_arg: None,
            item: item,
        })
    }
}

/// A stack of `ArgScope`s is itself an `ArgScope`!
impl<'prev, 'subs> ArgScope<'prev, 'subs> for Option<ArgScopeStack<'prev, 'subs>> {
    fn leaf_name(&'prev self) -> Result<LeafName<'subs>> {
        let mut scope = self.as_ref();
        while let Some(s) = scope {
            if let Ok(c) = s.item.leaf_name() {
                return Ok(c);
            }
            scope = s.prev;
        }
        Err(error::Error::BadLeafNameReference)
    }

    fn get_template_arg(&'prev self, idx: usize) -> Result<(&'subs TemplateArg, &'subs TemplateArgs)> {
        let mut scope = self.as_ref();
        while let Some(s) = scope {
            if let Ok((arg, args)) = s.item.get_template_arg(idx) {
                if let Some((in_idx, in_args)) = s.in_arg {
                    if args as *const TemplateArgs == in_args as *const TemplateArgs &&
                        in_idx <= idx {
                        return Err(error::Error::ForwardTemplateArgReference);
                    }
                }
                return Ok((arg, args));
            }
            scope = s.prev;
        }

        Err(error::Error::BadTemplateArgReference)
    }

    fn get_function_arg(&'prev self, idx: usize) -> Result<&'subs Type> {
        let mut scope = self.as_ref();
        while let Some(s) = scope {
            if let Ok(arg) = s.item.get_function_arg(idx) {
                return Ok(arg);
            }
            scope = s.prev;
        }

        Err(error::Error::BadFunctionArgReference)
    }
}

#[derive(Debug, Copy, Clone)]
struct DemangleState {
    /// How deep in the demangling are we?
    pub recursion_level: u32,
}

/// An RAII type to automatically check the recursion level against the
/// maximum. If the maximum has been crossed, return an error. Otherwise,
/// increment the level upon construction, and decrement it upon destruction.
struct AutoParseDemangle<'a, 'b, W: 'a + DemangleWrite>(&'b mut DemangleContext<'a, W>);

impl<'a, 'b, W: 'a + DemangleWrite> AutoParseDemangle<'a, 'b, W> {
    #[inline]
    fn new(ctx: &'b mut DemangleContext<'a, W>) -> std::result::Result<Self, fmt::Error> {
        ctx.enter_recursion()?;
        Ok(AutoParseDemangle(ctx))
    }
}

impl<'a, 'b, W: 'a + DemangleWrite> std::ops::Deref for AutoParseDemangle<'a, 'b, W> {
    type Target = DemangleContext<'a, W>;

    fn deref(&self) -> &Self::Target {
        self.0
    }
}

impl<'a, 'b, W: 'a + DemangleWrite> std::ops::DerefMut for AutoParseDemangle<'a, 'b, W> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.0
    }
}

impl<'a, 'b, W: 'a + DemangleWrite> Drop for AutoParseDemangle<'a, 'b, W> {
    #[inline]
    fn drop(&mut self) {
        self.0.exit_recursion();
    }
}

/// Common state that is required when demangling a mangled symbol's parsed AST.
#[doc(hidden)]
#[derive(Debug)]
pub struct DemangleContext<'a, W>
where
    W: 'a + DemangleWrite,
{
    // The substitution table built up when parsing the mangled symbol into an
    // AST.
    subs: &'a SubstitutionTable,

    // The maximum recursion
    max_recursion: u32,

    // Sometimes an AST node needs to insert itself as an inner item within one
    // of its children when demangling that child. For example, the AST
    //
    //     (array 10 int)
    //
    // is demangled as `int[10]`, but if we were to demangle the AST
    //
    //     (lvalue-ref (array 10 int))
    //
    // then we would want this demangled form: `int (&) [10]`, which requires
    // the parent lvalue-ref to be passed into the child array's demangling
    // method. This kind of thing also pops up with function pointers.
    //
    // The `inner` stack enables such behavior by allowing us to pass AST
    // parents down to their children as inner items.
    inner: Vec<&'a dyn DemangleAsInner<'a, W>>,

    // The original input string.
    input: &'a [u8],

    // `Identifier`s will be placed here, so `UnnamedTypeName` can utilize and print
    // out the Constructor/Destructor used.
    source_name: Option<&'a str>,

    // What the demangled name is being written to.
    out: &'a mut W,

    // The total number of bytes written to `out`. This is maintained by the
    // `Write` implementation for `DemangleContext`.
    bytes_written: usize,

    // The last char written to `out`, if any.
    last_char_written: Option<char>,

    // We are currently demangling a lambda argument, so template substitution
    // should be suppressed to match libiberty.
    is_lambda_arg: bool,

    // We are currently demangling a template-prefix.
    is_template_prefix: bool,

    // We are currently demangling a template-prefix in a nested-name.
    is_template_prefix_in_nested_name: bool,

    //  `PackExpansion`'s should only print '...', only when there is no template
    //  argument pack.
    is_template_argument_pack: bool,

    // Whether to show function parameters and (if applicable) return types.
    // This must be set to true before calling `demangle` on `Encoding`
    // unless that call is via the toplevel call to `MangledName::demangle`.
    show_params: bool,

    // recursion protection.
    state: Cell<DemangleState>,
}

impl<'a, W> fmt::Write for DemangleContext<'a, W>
where
    W: 'a + DemangleWrite,
{
    fn write_str(&mut self, s: &str) -> fmt::Result {
        if s.is_empty() {
            return Ok(());
        }

        log!("DemangleContext::write: '{}'", s);

        self.out.write_string(s).map(|_| {
            self.last_char_written = s.chars().last();
            self.bytes_written += s.len();
        })
    }
}

impl<'a, W> DemangleContext<'a, W>
where
    W: 'a + DemangleWrite,
{
    /// Construct a new `DemangleContext`.
    pub fn new(
        subs: &'a SubstitutionTable,
        input: &'a [u8],
        options: DemangleOptions,
        out: &'a mut W,
    ) -> DemangleContext<'a, W> {
        DemangleContext {
            subs: subs,
            max_recursion: 128,
            inner: vec![],
            input: input,
            source_name: None,
            out: out,
            bytes_written: 0,
            last_char_written: None,
            is_lambda_arg: false,
            is_template_prefix: false,
            is_template_prefix_in_nested_name: false,
            is_template_argument_pack: false,
            show_params: !options.no_params,
            state: Cell::new(DemangleState {
                recursion_level: 0,
            }),
        }
    }

    /// Get the current recursion level for this context.
    pub fn recursion_level(&self) -> u32 {
        self.state.get().recursion_level
    }

    #[inline]
    fn enter_recursion(&self) -> fmt::Result {
        let mut state = self.state.get();
        let new_recursion_level = state.recursion_level + 1;

        if new_recursion_level >= self.max_recursion {
            log!("Hit too much recursion at level {}", self.max_recursion);
            Err(Default::default())
        } else {
            state.recursion_level = new_recursion_level;
            self.state.set(state);
            Ok(())
        }
    }

    #[inline]
    fn exit_recursion(&self) {
        let mut state = self.state.get();
        debug_assert!(state.recursion_level >= 1);
        state.recursion_level -= 1;
        self.state.set(state);
    }

    #[inline]
    fn ensure(&mut self, ch: char) -> fmt::Result {
        if self.last_char_written == Some(ch) {
            Ok(())
        } else {
            write!(self, "{}", ch)?;
            Ok(())
        }
    }

    #[inline]
    fn ensure_space(&mut self) -> fmt::Result {
        self.ensure(' ')
    }

    #[inline]
    fn push_inner(&mut self, item: &'a dyn DemangleAsInner<'a, W>) {
        log!("DemangleContext::push_inner: {:?}", item);
        self.inner.push(item);
    }

    #[inline]
    fn pop_inner(&mut self) -> Option<&'a dyn DemangleAsInner<'a, W>> {
        let popped = self.inner.pop();
        log!("DemangleContext::pop_inner: {:?}", popped);
        popped
    }

    #[inline]
    fn pop_inner_if(&mut self, inner: &'a dyn DemangleAsInner<'a, W>) -> bool {
        let last = match self.inner.last() {
            None => return false,
            Some(last) => *last,
        };

        if ptr::eq(last, inner) {
            self.inner.pop();
            true
        } else {
            false
        }
    }

    fn demangle_inner_prefixes<'prev>(
        &mut self,
        scope: Option<ArgScopeStack<'prev, 'a>>,
    ) -> fmt::Result {
        log!("DemangleContext::demangle_inner_prefixes");
        let mut new_inner = vec![];
        while let Some(inner) = self.pop_inner() {
            if inner
                .downcast_to_function_type()
                .map_or(false, |f| !f.cv_qualifiers.is_empty())
            {
                log!(
                    "DemangleContext::demangle_inner_prefixes: not a prefix, saving: {:?}",
                    inner
                );
                new_inner.push(inner);
            } else {
                log!(
                    "DemangleContext::demangle_inner_prefixes: demangling prefix: {:?}",
                    inner
                );
                inner.demangle_as_inner(self, scope)?;
            }
        }
        new_inner.reverse();
        self.inner = new_inner;
        Ok(())
    }

    fn demangle_inners<'prev>(
        &mut self,
        scope: Option<ArgScopeStack<'prev, 'a>>,
    ) -> fmt::Result {
        while let Some(inner) = self.pop_inner() {
            inner.demangle_as_inner(self, scope)?;
        }
        Ok(())
    }

    fn set_source_name(&mut self, start: usize, end: usize) {
        let ident = &self.input[start..end];
        self.source_name = std::str::from_utf8(ident).ok();
    }

    fn push_demangle_node(&mut self, t: DemangleNodeType) {
        self.out.push_demangle_node(t);
    }

    /// This should not be called on error paths.
    /// pop_inner_if already doesn't balance if there are errors.
    fn pop_demangle_node(&mut self) {
        self.out.pop_demangle_node();
    }
}

#[doc(hidden)]
#[derive(Debug)]
pub struct AutoDemangleContextInnerBarrier<'ctx, 'a, W>
where
    W: 'a + DemangleWrite,
    'a: 'ctx,
{
    ctx: &'ctx mut DemangleContext<'a, W>,
    saved_inner: Vec<&'a dyn DemangleAsInner<'a, W>>,
}

impl<'ctx, 'a, W> AutoDemangleContextInnerBarrier<'ctx, 'a, W>
where
    W: 'a + DemangleWrite,
    'a: 'ctx,
{
    /// Set aside the current inner stack on the demangle context.
    pub fn new(ctx: &'ctx mut DemangleContext<'a, W>) -> Self {
        let mut saved_inner = vec![];
        mem::swap(&mut saved_inner, &mut ctx.inner);
        AutoDemangleContextInnerBarrier {
            ctx: ctx,
            saved_inner: saved_inner,
        }
    }
}

impl<'ctx, 'a, W> ops::Deref for AutoDemangleContextInnerBarrier<'ctx, 'a, W>
where
    W: 'a + DemangleWrite,
    'a: 'ctx,
{
    type Target = DemangleContext<'a, W>;

    fn deref(&self) -> &Self::Target {
        self.ctx
    }
}

impl<'ctx, 'a, W> ops::DerefMut for AutoDemangleContextInnerBarrier<'ctx, 'a, W>
where
    W: 'a + DemangleWrite,
    'a: 'ctx,
{
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.ctx
    }
}

impl<'ctx, 'a, W> Drop for AutoDemangleContextInnerBarrier<'ctx, 'a, W>
where
    W: 'a + DemangleWrite,
    'a: 'ctx,
{
    fn drop(&mut self) {
        // NB: We cannot assert that the context's inner is empty here,
        // because if demangling failed we'll unwind the stack without
        // using everything that put on the inner.
        if !self.ctx.inner.is_empty() {
            log!("Context inner was not emptied, did demangling fail?");
        }
        mem::swap(&mut self.saved_inner, &mut self.ctx.inner);
    }
}

/// The inner stack allows passing AST nodes down deeper into the tree so that
/// nodes that logically precede something (e.g. PointerRef) can show up after
/// that thing in the demangled output. What's on the stack may not always be
/// intended for the first node that looks at the stack to grab, though.
///
/// Consider a function with template arguments and parameters, f<T>(a).
/// The function parameters logically precede the template arguments in the AST,
/// but they must be reversed in the output. The parameters end up on the inner
/// stack before processing the template argument nodes. If we're not careful,
/// a node inside the template arguments might pick the function parameters
/// off of the inner stack!
///
/// To solve this, certain nodes act as "inner barriers". By using this macro,
/// they set the existing inner stack aside and replace it with an empty stack
/// while visiting their children. This allows these barrier nodes to have
/// completely self-contained children.
macro_rules! inner_barrier {
    ( $ctx:ident ) => {
        let mut _ctx = AutoDemangleContextInnerBarrier::new($ctx);
        let $ctx = &mut _ctx;
    }
}

/// Any AST node that can be printed in a demangled form.
#[doc(hidden)]
pub trait Demangle<'subs, W>: fmt::Debug
where
    W: 'subs + DemangleWrite,
{
    /// Write the demangled form of this AST node to the given context.
    fn demangle<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result;
}

/// Any AST node that can be printed as an inner type.
///
/// See the comments surrounding `DemangleContext::inner` for details.
#[doc(hidden)]
pub trait DemangleAsInner<'subs, W>: Demangle<'subs, W>
where
    W: 'subs + DemangleWrite,
{
    /// Write the inner demangling form of this AST node to the given context.
    fn demangle_as_inner<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        self.demangle(ctx, scope)
    }

    /// Cast this `DemangleAsInner` to a `Type`.
    fn downcast_to_type(&self) -> Option<&Type> {
        None
    }

    /// Cast this `DemangleAsInner` to a `FunctionType`.
    fn downcast_to_function_type(&self) -> Option<&FunctionType> {
        None
    }

    /// Cast this `DemangleAsInner` to an `ArrayType`.
    fn downcast_to_array_type(&self) -> Option<&ArrayType> {
        None
    }

    /// Cast this `DemangleAsInner` to a `PointerToMember`.
    fn downcast_to_pointer_to_member(&self) -> Option<&PointerToMemberType> {
        None
    }

    fn is_qualified(&self) -> bool {
        false
    }
}

/// Demangle this thing in the leaf name position.
///
/// For most things this should be the same as its `Demangle`
/// implementation. For `WellKnownComponent`s we need to strip the embedded
/// `std::` namespace prefix.
pub(crate) trait DemangleAsLeaf<'subs, W>
where
    W: 'subs + DemangleWrite,
{
    fn demangle_as_leaf<'me, 'ctx>(
        &'me self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
    ) -> fmt::Result;
}

macro_rules! reference_newtype {
    ( $newtype_name:ident , $oldtype:ty ) => {
        #[derive(Debug)]
        struct $newtype_name($oldtype);

        impl $newtype_name {
            #[allow(clippy::ptr_arg)]
            #[allow(unsafe_code)]
            fn new(types: &$oldtype) -> &$newtype_name {
                unsafe {
                    // This is safe because we only create an immutable
                    // reference. We are not breaking unique mutable aliasing
                    // requirements. An immutable reference does not allow
                    // dropping the referent, so no worries about double-free
                    // (additionally, see the assertion inside `Drop` below).
                    &*(types as *const $oldtype as *const $newtype_name)
                }
            }
        }

        impl Drop for $newtype_name {
            fn drop(&mut self) {
                unreachable!("Dropping implies we dereferenced and took ownership, which \
                              is not safe for this newtype");
            }
        }

        impl ops::Deref for $newtype_name {
            type Target = $oldtype;

            fn deref(&self) -> &Self::Target {
                &self.0
            }
        }
    }
}

// We can't implement `DemangleAsInner` for newtypes of `[TypeHandle]` like we
// want to because it is unsized and we need to make trait objects out of
// `DemangleAsInner` for pushing onto the context's inner stack. Therefore, we
// have this inelegant newtyping of `Vec<TypeHandle>`.

// A set of function arguments.
reference_newtype!(FunctionArgList, Vec<TypeHandle>);

// A set of function arguments prefixed by a return type (which we want to
// ignore).
reference_newtype!(FunctionArgListAndReturnType, Vec<TypeHandle>);

// A newtype around a slice of type handles that we format as function
// arguments.
reference_newtype!(FunctionArgSlice, [TypeHandle]);

// Demangle a slice of TypeHandle as a function argument list.
impl<'subs, W> Demangle<'subs, W> for FunctionArgSlice
where
    W: 'subs + DemangleWrite,
{
    fn demangle<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        let ctx = try_begin_demangle!(self, ctx, scope);

        let mut saw_needs_paren = false;
        let (needs_space, needs_paren) = ctx.inner
            .iter()
            .rev()
            .map(|inner| {
                if inner.downcast_to_pointer_to_member().is_some() {
                    (true, true)
                } else {
                    match inner.downcast_to_type() {
                        Some(&Type::Qualified(..))
                        | Some(&Type::Complex(_))
                        | Some(&Type::Imaginary(_))
                        | Some(&Type::PointerToMember(_)) => (true, true),
                        Some(&Type::PointerTo(_))
                        | Some(&Type::LvalueRef(_))
                        | Some(&Type::RvalueRef(_)) => (false, true),
                        _ => (false, false),
                    }
                }
            })
            .take_while(|&(_, needs_paren)| {
                if saw_needs_paren {
                    false
                } else {
                    saw_needs_paren |= needs_paren;
                    true
                }
            })
            .fold((false, false), |(space, paren), (next_space, next_paren)| {
                (space || next_space, paren || next_paren)
            });

        if needs_paren {
            let needs_space = needs_space || match ctx.last_char_written {
                Some('(') | Some('*') => false,
                _ => true,
            };

            if needs_space {
                ctx.ensure_space()?;
            }

            write!(ctx, "(")?;
        }

        ctx.demangle_inner_prefixes(scope)?;

        if needs_paren {
            write!(ctx, ")")?;
        }

        write!(ctx, "(")?;

        // To maintain compatibility with libiberty, print `()` instead of
        // `(void)` for functions that take no arguments.
        if self.len() == 1 && self[0].is_void() {
            write!(ctx, ")")?;
            return Ok(());
        }

        let mut need_comma = false;
        for arg in self.iter() {
            if need_comma {
                write!(ctx, ", ")?;
            }
            arg.demangle(ctx, scope)?;
            need_comma = true;
        }

        write!(ctx, ")")?;

        ctx.demangle_inners(scope)
    }
}

impl<'subs, W> Demangle<'subs, W> for FunctionArgList
where
    W: 'subs + DemangleWrite,
{
    fn demangle<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        FunctionArgSlice::new(&self.0[..]).demangle(ctx, scope)
    }
}

impl<'subs, W> DemangleAsInner<'subs, W> for FunctionArgList
where
    W: 'subs + DemangleWrite,
{
}

impl<'subs, W> Demangle<'subs, W> for FunctionArgListAndReturnType
where
    W: 'subs + DemangleWrite,
{
    fn demangle<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        FunctionArgSlice::new(&self.0[1..]).demangle(ctx, scope)
    }
}

impl<'subs, W> DemangleAsInner<'subs, W> for FunctionArgListAndReturnType
where
    W: 'subs + DemangleWrite,
{
}

/// Define a handle to a AST type that lives inside the substitution table. A
/// handle is always either an index into the substitution table, or it is a
/// reference to a "well-known" component.
///
/// This declares:
///
/// - The enum of either a back reference into the substitution table or a
///   reference to a "well-known" component
/// - a `Demangle` impl that proxies to the appropriate `Substitutable` in the
///   `SubstitutionTable`
macro_rules! define_handle {
    (
        $(#[$attr:meta])*
        pub enum $typename:ident
    ) => {
        define_handle! {
            $(#[$attr])*
            pub enum $typename {}
        }
    };

    (
        $(#[$attr:meta])*
        pub enum $typename:ident {
            $(
                $( #[$extra_attr:meta] )*
                extra $extra_variant:ident ( $extra_variant_ty:ty ),
            )*
        }
    ) => {
        $(#[$attr])*
        #[derive(Clone, Debug, PartialEq, Eq)]
        pub enum $typename {
            /// A reference to a "well-known" component.
            WellKnown(WellKnownComponent),

            /// A back-reference into the substitution table to a component we
            /// have already parsed.
            BackReference(usize),

            $(
                $( #[$extra_attr] )*
                $extra_variant( $extra_variant_ty ),
            )*
        }

        impl $typename {
            /// If this is a `BackReference`, get its index.
            pub fn back_reference(&self) -> Option<usize> {
                match *self {
                    $typename::BackReference(n) => Some(n),
                    _ => None,
                }
            }
        }

        impl<'subs, W> Demangle<'subs, W> for $typename
        where
            W: 'subs + DemangleWrite
        {
            #[inline]
            fn demangle<'prev, 'ctx>(&'subs self,
                                     ctx: &'ctx mut DemangleContext<'subs, W>,
                                     scope: Option<ArgScopeStack<'prev, 'subs>>)
                                     -> fmt::Result {
                match *self {
                    $typename::WellKnown(ref comp) => comp.demangle(ctx, scope),
                    $typename::BackReference(idx) => ctx.subs[idx].demangle(ctx, scope),
                    $(
                        $typename::$extra_variant(ref extra) => extra.demangle(ctx, scope),
                    )*
                }
            }
        }

        impl<'a> GetLeafName<'a> for $typename {
            fn get_leaf_name(&'a self, subs: &'a SubstitutionTable) -> Option<LeafName<'a>> {
                match *self {
                    $typename::WellKnown(ref wk) => wk.get_leaf_name(subs),
                    $typename::BackReference(idx) => {
                        subs.get(idx).and_then(|s| s.get_leaf_name(subs))
                    }
                    $(
                        $typename::$extra_variant(ref e) => e.get_leaf_name(subs),
                    )*
                }
            }
        }
    };
}

/// A handle to a component that is usually substitutable, and lives in the
/// substitutions table, but in this particular case does not qualify for
/// substitutions.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct NonSubstitution(usize);

impl<'subs, W> Demangle<'subs, W> for NonSubstitution
where
    W: 'subs + DemangleWrite,
{
    fn demangle<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        ctx.subs.non_substitution(self.0).demangle(ctx, scope)
    }
}

impl<'a> GetLeafName<'a> for NonSubstitution {
    fn get_leaf_name(&'a self, subs: &'a SubstitutionTable) -> Option<LeafName<'a>> {
        subs.get_non_substitution(self.0)
            .and_then(|ns| ns.get_leaf_name(subs))
    }
}

/// Define a "vocabulary" nonterminal, something like `OperatorName` or
/// `CtorDtorName` that's basically a big list of constant strings.
///
/// This declares:
///
/// - the enum itself
/// - a `Parse` impl
/// - a `Demangle` impl
///
/// See the definition of `CTorDtorName` for an example of its use.
///
/// Optionally, a piece of user data can be attached to the definitions
/// and be returned by a generated accessor. See `SimpleOperatorName` for
/// an example.
macro_rules! define_vocabulary {
    ( $(#[$attr:meta])* pub enum $typename:ident {
        $($variant:ident ( $mangled:expr, $printable:expr )),*
    } ) => {

        $(#[$attr])*
        pub enum $typename {
            $(
                #[doc=$printable]
                $variant
            ),*
        }

        impl Parse for $typename {
            fn parse<'a, 'b>(ctx: &'a ParseContext,
                             _subs: &'a mut SubstitutionTable,
                             input: IndexStr<'b>)
                             -> Result<($typename, IndexStr<'b>)> {
                try_begin_parse!(stringify!($typename), ctx, input);

                let mut found_prefix = false;
                $(
                    if let Some((head, tail)) = input.try_split_at($mangled.len()) {
                        if head.as_ref() == $mangled {
                            return Ok(($typename::$variant, tail));
                        }
                    } else {
                        found_prefix |= 0 < input.len() &&
                            input.len() < $mangled.len() &&
                            input.as_ref() == &$mangled[..input.len()];
                    }
                )*

                if input.is_empty() || found_prefix {
                    Err(error::Error::UnexpectedEnd)
                } else {
                    Err(error::Error::UnexpectedText)
                }
            }
        }

        impl<'subs, W> Demangle<'subs, W> for $typename
        where
            W: 'subs + DemangleWrite,
        {
            fn demangle<'prev, 'ctx>(
                &'subs self,
                ctx: &'ctx mut DemangleContext<'subs, W>,
                scope: Option<ArgScopeStack<'prev, 'subs>>
            ) -> fmt::Result {
                let ctx = try_begin_demangle!(self, ctx, scope);

                write!(ctx, "{}", match *self {
                    $(
                        $typename::$variant => $printable
                    ),*
                })
            }
        }

        impl $typename {
            #[allow(dead_code)]
            #[inline]
            fn starts_with(byte: u8) -> bool {
                $(
                    if $mangled[0] == byte {
                        return true;
                    }
                )*

                false
            }
        }
    };
    ( $(#[$attr:meta])* pub enum $typename:ident {
        $($variant:ident ( $mangled:expr, $printable:expr, $userdata:expr)),*
    }

      impl $typename2:ident {
          fn $fn_name:ident(&self) -> $userdata_ty:ty;
    } ) => {
        define_vocabulary! {
            $(#[$attr])*
            pub enum $typename {
                $(
                    $variant ( $mangled, $printable )
                ),*
            }
        }

        impl $typename2 {
            fn $fn_name(&self) -> $userdata_ty {
                match *self {
                    $(
                        $typename2::$variant => $userdata,
                    )*
                }
            }
        }
    };
}

/// The root AST node, and starting production.
///
/// ```text
/// <mangled-name> ::= _Z <encoding> [<clone-suffix>]*
///                ::= ___Z <encoding> <block_invoke>
///                ::= <type>
///
/// <block_invoke> ::= _block_invoke
///                ::= _block_invoke<decimal-digit>+
///                ::= _block_invoke_<decimal-digit>+
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum MangledName {
    /// The encoding of the mangled symbol name.
    Encoding(Encoding, Vec<CloneSuffix>),

    /// The encoding of the mangled symbol name.
    BlockInvoke(Encoding, Option<isize>),

    /// A top-level type. Technically not allowed by the standard, however in
    /// practice this can happen, and is tested for by libiberty.
    Type(TypeHandle),

    /// A global constructor or destructor. This is another de facto standard
    /// extension (I think originally from `g++`?) that is not actually part of
    /// the standard proper.
    GlobalCtorDtor(GlobalCtorDtor),
}

impl Parse for MangledName {
    fn parse<'a, 'b>(
        ctx: &'a ParseContext,
        subs: &'a mut SubstitutionTable,
        input: IndexStr<'b>,
    ) -> Result<(MangledName, IndexStr<'b>)> {
        try_begin_parse!("MangledName", ctx, input);

        if let Ok(tail) = consume(b"_Z", input).or_else(|_| consume(b"__Z", input)) {
            let (encoding, tail) = Encoding::parse(ctx, subs, tail)?;
            let (clone_suffixes, tail) = zero_or_more(ctx, subs, tail)?;
            return Ok((MangledName::Encoding(encoding, clone_suffixes), tail));
        }

        if let Ok(tail) = consume(b"___Z", input).or_else(|_| consume(b"____Z", input)) {
            let (encoding, tail) = Encoding::parse(ctx, subs, tail)?;
            let tail = consume(b"_block_invoke", tail)?;

            let tail_opt = match consume(b"_", tail) {
                Ok(tail) => Some(parse_number(10, false, tail)?),
                Err(_) => parse_number(10, false, tail).ok(),
            };

            let (digits, tail) = match tail_opt {
                Some((digits, tail)) => (Some(digits), tail),
                None => (None, tail),
            };

            return Ok((MangledName::BlockInvoke(encoding, digits), tail));
        }

        if let Ok(tail) = consume(b"_GLOBAL_", input) {
            let (global_ctor_dtor, tail) = GlobalCtorDtor::parse(ctx, subs, tail)?;
            return Ok((MangledName::GlobalCtorDtor(global_ctor_dtor), tail));
        }

        // The libiberty tests also specify that a type can be top level,
        // and they are not prefixed with "_Z".
        let (ty, tail) = TypeHandle::parse(ctx, subs, input)?;
        Ok((MangledName::Type(ty), tail))
    }
}

impl<'subs, W> Demangle<'subs, W> for MangledName
where
    W: 'subs + DemangleWrite,
{
    fn demangle<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        let ctx = try_begin_demangle!(self, ctx, scope);

        match *self {
            MangledName::Encoding(ref enc, ref cs) => {
                enc.demangle(ctx, scope)?;
                if !cs.is_empty() && ctx.show_params {
                    for clone_suffix in cs {
                        clone_suffix.demangle(ctx, scope)?;
                    }
                }
                Ok(())
            },
            MangledName::BlockInvoke(ref enc, _) => {
                write!(ctx, "invocation function for block in ")?;
                enc.demangle(ctx, scope)?;
                Ok(())
            }
            MangledName::Type(ref ty) => ty.demangle(ctx, scope),
            MangledName::GlobalCtorDtor(ref gcd) => gcd.demangle(ctx, scope),
        }
    }
}

/// The `<encoding>` production.
///
/// ```text
/// <encoding> ::= <function name> <bare-function-type>
///            ::= <data name>
///            ::= <special-name>
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Encoding {
    /// An encoded function.
    Function(Name, BareFunctionType),

    /// An encoded static variable.
    Data(Name),

    /// A special encoding.
    Special(SpecialName),
}

impl Parse for Encoding {
    fn parse<'a, 'b>(
        ctx: &'a ParseContext,
        subs: &'a mut SubstitutionTable,
        input: IndexStr<'b>,
    ) -> Result<(Encoding, IndexStr<'b>)> {
        try_begin_parse!("Encoding", ctx, input);

        if let Ok((name, tail)) = Name::parse(ctx, subs, input) {
            if let Ok((ty, tail)) = BareFunctionType::parse(ctx, subs, tail) {
                return Ok((Encoding::Function(name, ty), tail));
            } else {
                return Ok((Encoding::Data(name), tail));
            }
        }

        let (name, tail) = SpecialName::parse(ctx, subs, input)?;
        Ok((Encoding::Special(name), tail))
    }
}

impl<'subs, W> Demangle<'subs, W> for Encoding
where
    W: 'subs + DemangleWrite,
{
    fn demangle<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        let ctx = try_begin_demangle!(self, ctx, scope);
        inner_barrier!(ctx);

        match *self {
            Encoding::Function(ref name, ref fun_ty) => {
                // Even if this function takes no args and doesn't have a return
                // value (see below), it will have the void parameter.
                debug_assert!(!fun_ty.0.is_empty());

                let scope = if let Some(leaf) = name.get_leaf_name(ctx.subs) {
                    match leaf {
                        LeafName::SourceName(leaf) => scope.push(leaf),
                        LeafName::WellKnownComponent(leaf) => scope.push(leaf),
                        LeafName::Closure(leaf) => scope.push(leaf),
                        LeafName::UnnamedType(leaf) => scope.push(leaf),
                    }
                } else {
                    scope
                };

                // Whether the first type in the BareFunctionType is a return
                // type or parameter depends on the context in which it
                // appears.
                //
                // * Templates and functions in a type or parameter position
                // have return types, unless they are constructors, destructors,
                // or conversion operator functions.
                //
                // * Non-template functions that are not in a type or parameter
                // position do not have a return type.
                //
                // We know we are not printing a type, so we only need to check
                // whether this is a template.
                //
                // For the details, see
                // http://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangle.function-type
                let scope = if let Some(template_args) = name.get_template_args(ctx.subs) {
                    let scope = scope.push(template_args);
                    if ctx.show_params && !name.is_ctor_dtor_conversion(ctx.subs) {
                        fun_ty.0[0].demangle(ctx, scope)?;
                        write!(ctx, " ")?;
                    }

                    scope
                } else {
                    scope
                };

                if ctx.show_params {
                    ctx.push_inner(self);
                    name.demangle(ctx, scope)?;
                    if ctx.pop_inner_if(self) {
                        self.demangle_as_inner(ctx, scope)?;
                    }
                } else {
                    name.demangle(ctx, scope)?;
                }

                Ok(())
            }
            Encoding::Data(ref name) => name.demangle(ctx, scope),
            Encoding::Special(ref name) => name.demangle(ctx, scope),
        }
    }
}

impl<'subs, W> DemangleAsInner<'subs, W> for Encoding
where
    W: 'subs + DemangleWrite,
{
    fn demangle_as_inner<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        if let Encoding::Function(ref name, ref fun_ty) = *self {
            let (scope, function_args) =
                if let Some(template_args) = name.get_template_args(ctx.subs) {
                    let scope = scope.push(template_args);
                    let function_args = FunctionArgListAndReturnType::new(&fun_ty.0);
                    (scope, function_args as &dyn DemangleAsInner<W>)
                } else {
                    let function_args = FunctionArgList::new(&fun_ty.0);
                    (scope, function_args as &dyn DemangleAsInner<W>)
                };
            function_args.demangle_as_inner(ctx, scope)
        } else {
            unreachable!("we only push Encoding::Function onto the inner stack");
        }
    }
}

/// <clone-suffix> ::= [ . <clone-type-identifier> ] [ . <nonnegative number> ]*

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct CloneSuffix(CloneTypeIdentifier, Vec<isize>);

impl Parse for CloneSuffix {
    fn parse<'a, 'b>(
        ctx: &'a ParseContext,
        subs: &'a mut SubstitutionTable,
        input: IndexStr<'b>,
    ) -> Result<(CloneSuffix, IndexStr<'b>)> {
        try_begin_parse!("CloneSuffix", ctx, input);

        let tail = consume(b".", input)?;
        let (identifier, mut tail) = CloneTypeIdentifier::parse(ctx, subs, tail)?;

        let mut numbers = Vec::with_capacity(1);
        while let Ok((n, t)) = consume(b".", tail).and_then(|t| parse_number(10, false, t)) {
            numbers.push(n);
            tail = t;
        }

        let clone_suffix = CloneSuffix(identifier, numbers);
        Ok((clone_suffix, tail))
    }
}

impl<'subs, W> Demangle<'subs, W> for CloneSuffix
where
    W: 'subs + DemangleWrite,
{
    fn demangle<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        let ctx = try_begin_demangle!(self, ctx, scope);
        write!(ctx, " [clone")?;
        self.0.demangle(ctx, scope)?;
        for nonnegative in &self.1 {
            write!(ctx, ".{}", nonnegative)?;
        }
        write!(ctx, "]")?;
        Ok(())
    }
}

/// A global constructor or destructor.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum GlobalCtorDtor {
    /// A global constructor.
    Ctor(Box<MangledName>),
    /// A global destructor.
    Dtor(Box<MangledName>),
}

impl Parse for GlobalCtorDtor {
    fn parse<'a, 'b>(
        ctx: &'a ParseContext,
        subs: &'a mut SubstitutionTable,
        input: IndexStr<'b>,
    ) -> Result<(GlobalCtorDtor, IndexStr<'b>)> {
        try_begin_parse!("GlobalCtorDtor", ctx, input);

        let tail = match input.next_or(error::Error::UnexpectedEnd)? {
            (b'_', t) | (b'.', t) | (b'$', t) => t,
            _ => return Err(error::Error::UnexpectedText),
        };

        match tail.next_or(error::Error::UnexpectedEnd)? {
            (b'I', tail) => {
                let tail = consume(b"_", tail)?;
                let (name, tail) = MangledName::parse(ctx, subs, tail)?;
                Ok((GlobalCtorDtor::Ctor(Box::new(name)), tail))
            }
            (b'D', tail) => {
                let tail = consume(b"_", tail)?;
                let (name, tail) = MangledName::parse(ctx, subs, tail)?;
                Ok((GlobalCtorDtor::Dtor(Box::new(name)), tail))
            }
            _ => Err(error::Error::UnexpectedText),
        }
    }
}

impl<'subs, W> Demangle<'subs, W> for GlobalCtorDtor
where
    W: 'subs + DemangleWrite,
{
    fn demangle<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        let ctx = try_begin_demangle!(self, ctx, scope);
        inner_barrier!(ctx);

        let saved_show_params = ctx.show_params;
        ctx.show_params = true;
        let ret = match *self {
            GlobalCtorDtor::Ctor(ref name) => {
                write!(ctx, "global constructors keyed to ")?;
                name.demangle(ctx, scope)
            }
            GlobalCtorDtor::Dtor(ref name) => {
                write!(ctx, "global destructors keyed to ")?;
                name.demangle(ctx, scope)
            }
        };
        ctx.show_params = saved_show_params;
        ret
    }
}

/// The `<name>` production.
///
/// ```text
/// <name> ::= <nested-name>
///        ::= <unscoped-name>
///        ::= <unscoped-template-name> <template-args>
///        ::= <local-name>
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Name {
    /// A nested name
    Nested(NestedName),

    /// An unscoped name.
    Unscoped(UnscopedName),

    /// An unscoped template.
    UnscopedTemplate(UnscopedTemplateNameHandle, TemplateArgs),

    /// A local name.
    Local(LocalName),
}

impl Parse for Name {
    fn parse<'a, 'b>(
        ctx: &'a ParseContext,
        subs: &'a mut SubstitutionTable,
        input: IndexStr<'b>,
    ) -> Result<(Name, IndexStr<'b>)> {
        try_begin_parse!("Name", ctx, input);

        if let Ok((name, tail)) = NestedName::parse(ctx, subs, input) {
            return Ok((Name::Nested(name), tail));
        }

        if let Ok((name, tail)) = UnscopedName::parse(ctx, subs, input) {
            if tail.peek() == Some(b'I') {
                let name = UnscopedTemplateName(name);
                let idx = subs.insert(Substitutable::UnscopedTemplateName(name));
                let handle = UnscopedTemplateNameHandle::BackReference(idx);

                let (args, tail) = TemplateArgs::parse(ctx, subs, tail)?;
                return Ok((Name::UnscopedTemplate(handle, args), tail));
            } else {
                return Ok((Name::Unscoped(name), tail));
            }
        }

        if let Ok((name, tail)) = UnscopedTemplateNameHandle::parse(ctx, subs, input) {
            let (args, tail) = TemplateArgs::parse(ctx, subs, tail)?;
            return Ok((Name::UnscopedTemplate(name, args), tail));
        }

        let (name, tail) = LocalName::parse(ctx, subs, input)?;
        Ok((Name::Local(name), tail))
    }
}

impl<'subs, W> Demangle<'subs, W> for Name
where
    W: 'subs + DemangleWrite,
{
    fn demangle<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        let ctx = try_begin_demangle!(self, ctx, scope);

        match *self {
            Name::Nested(ref nested) => nested.demangle(ctx, scope),
            Name::Unscoped(ref unscoped) => unscoped.demangle(ctx, scope),
            Name::UnscopedTemplate(ref template, ref args) => {
                template.demangle(ctx, scope.push(args))?;
                args.demangle(ctx, scope)
            }
            Name::Local(ref local) => local.demangle(ctx, scope),
        }
    }
}

impl GetTemplateArgs for Name {
    fn get_template_args<'a>(&'a self, subs: &'a SubstitutionTable) -> Option<&'a TemplateArgs> {
        match *self {
            Name::UnscopedTemplate(_, ref args) => Some(args),
            Name::Nested(ref nested) => nested.get_template_args(subs),
            Name::Local(ref local) => local.get_template_args(subs),
            Name::Unscoped(_) => None,
        }
    }
}

impl<'a> GetLeafName<'a> for Name {
    fn get_leaf_name(&'a self, subs: &'a SubstitutionTable) -> Option<LeafName<'a>> {
        match *self {
            Name::UnscopedTemplate(ref templ, _) => templ.get_leaf_name(subs),
            Name::Nested(ref nested) => nested.get_leaf_name(subs),
            Name::Unscoped(ref unscoped) => unscoped.get_leaf_name(subs),
            Name::Local(ref local) => local.get_leaf_name(subs),
        }
    }
}

impl IsCtorDtorConversion for Name {
    fn is_ctor_dtor_conversion(&self, subs: &SubstitutionTable) -> bool {
        match *self {
            Name::Unscoped(ref unscoped) => unscoped.is_ctor_dtor_conversion(subs),
            Name::Nested(ref nested) => nested.is_ctor_dtor_conversion(subs),
            Name::Local(_) |
            Name::UnscopedTemplate(..) => false,
        }
    }
}

/// The `<unscoped-name>` production.
///
/// ```text
/// <unscoped-name> ::= <unqualified-name>
///                 ::= St <unqualified-name>   # ::std::
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum UnscopedName {
    /// An unqualified name.
    Unqualified(UnqualifiedName),

    /// A name within the `std::` namespace.
    Std(UnqualifiedName),
}

impl Parse for UnscopedName {
    fn parse<'a, 'b>(
        ctx: &'a ParseContext,
        subs: &'a mut SubstitutionTable,
        input: IndexStr<'b>,
    ) -> Result<(UnscopedName, IndexStr<'b>)> {
        try_begin_parse!("UnscopedName", ctx, input);

        if let Ok(tail) = consume(b"St", input) {
            let (name, tail) = UnqualifiedName::parse(ctx, subs, tail)?;
            return Ok((UnscopedName::Std(name), tail));
        }

        let (name, tail) = UnqualifiedName::parse(ctx, subs, input)?;
        Ok((UnscopedName::Unqualified(name), tail))
    }
}

impl<'subs, W> Demangle<'subs, W> for UnscopedName
where
    W: 'subs + DemangleWrite,
{
    fn demangle<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        let ctx = try_begin_demangle!(self, ctx, scope);

        match *self {
            UnscopedName::Unqualified(ref unqualified) => unqualified.demangle(ctx, scope),
            UnscopedName::Std(ref std) => {
                write!(ctx, "std::")?;
                std.demangle(ctx, scope)
            }
        }
    }
}

impl<'a> GetLeafName<'a> for UnscopedName {
    fn get_leaf_name(&'a self, subs: &'a SubstitutionTable) -> Option<LeafName<'a>> {
        match *self {
            UnscopedName::Unqualified(ref name) | UnscopedName::Std(ref name) => {
                name.get_leaf_name(subs)
            }
        }
    }
}

impl IsCtorDtorConversion for UnscopedName {
    fn is_ctor_dtor_conversion(&self, subs: &SubstitutionTable) -> bool {
        match *self {
            UnscopedName::Unqualified(ref name) | UnscopedName::Std(ref name) => name.is_ctor_dtor_conversion(subs),
        }
    }
}

/// The `<unscoped-template-name>` production.
///
/// ```text
/// <unscoped-template-name> ::= <unscoped-name>
///                          ::= <substitution>
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct UnscopedTemplateName(UnscopedName);

define_handle! {
    /// A handle to an `UnscopedTemplateName`.
    pub enum UnscopedTemplateNameHandle {
        /// A handle to some `<unscoped-name>` component that isn't by itself
        /// substitutable.
        extra NonSubstitution(NonSubstitution),
    }
}

impl Parse for UnscopedTemplateNameHandle {
    fn parse<'a, 'b>(
        ctx: &'a ParseContext,
        subs: &'a mut SubstitutionTable,
        input: IndexStr<'b>,
    ) -> Result<(UnscopedTemplateNameHandle, IndexStr<'b>)> {
        try_begin_parse!("UnscopedTemplateNameHandle", ctx, input);

        if let Ok((name, tail)) = UnscopedName::parse(ctx, subs, input) {
            let name = UnscopedTemplateName(name);
            let idx = subs.insert(Substitutable::UnscopedTemplateName(name));
            let handle = UnscopedTemplateNameHandle::BackReference(idx);
            return Ok((handle, tail));
        }

        let (sub, tail) = Substitution::parse(ctx, subs, input)?;

        match sub {
            Substitution::WellKnown(component) => {
                Ok((UnscopedTemplateNameHandle::WellKnown(component), tail))
            }
            Substitution::BackReference(idx) => {
                // TODO: should this check/assert that subs[idx] is an
                // UnscopedTemplateName?
                Ok((UnscopedTemplateNameHandle::BackReference(idx), tail))
            }
        }
    }
}

impl<'subs, W> Demangle<'subs, W> for UnscopedTemplateName
where
    W: 'subs + DemangleWrite,
{
    fn demangle<'prev, 'ctx>(
        &'subs self,
        ctx: &'ctx mut DemangleContext<'subs, W>,
        scope: Option<ArgScopeStack<'prev, 'subs>>,
    ) -> fmt::Result {
        let ctx = try_begin_demangle!(self, ctx, scope);

        self.0.demangle(ctx, scope)
    }
}

impl<'a> GetLeafName<'a> for UnscopedTemplateName {
    fn get_leaf_name(&'a self, subs: &'a SubstitutionTable) -> Option<LeafName<'a>> {
        self.0.get_leaf_name(subs)
    }
}

/// The `<nested-name>` production.
///
/// ```text
/// <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
///               ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
/// ```
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum NestedName {
    /// A nested name.
    Unqualified(
        CvQualifiers,
        Option<RefQualifier>,
        PrefixHandle,
        UnqualifiedName,
    ),

    /// A nested template name. The `<template-args>` are part of the `PrefixHandle`.
    Template(CvQualifiers, Option<RefQualifier>, PrefixHandle),
}

impl Parse for NestedName {
    fn parse<'a, 'b>(
        ctx: &'a ParseContext,
        subs: &'a mut SubstitutionTable,
        input: IndexStr<'b>,
    ) -> Result<(NestedName, IndexStr<'b>)> {
        try_begin_parse!("NestedName", ctx, input);

        let tail = consume(b"N", input)?;

        let (cv_qualifiers, tail) = if let Ok((q, tail)) = CvQualifiers::parse(ctx, subs, tail) {
            (q, tail)
        } else {
            (Default::default(), tail)
        };

        let (ref_qualifier, tail) = if let Ok((r, tail)) = RefQualifier::parse(ctx, subs, tail) {
            (Some(r), tail)
        } else {
            (None, tail)
        };

        let (prefix, tail) = PrefixHandle::parse(ctx, subs, tail)?;
        let tail = consume(b"E", tail)?;

        let substitutable = match prefix {
            PrefixHandle::BackReference(idx) => subs.get(idx),
            PrefixHandle::NonSubstitution(NonSubstitution(idx)) => subs.get_non_substitution(idx),
            PrefixHandle::WellKnown(_) => None,
        };

        match substitutable {
            Some(&Substitutable::Prefix(Prefix::Nested(ref prefix, ref name))) => Ok((
                NestedName::Unqualified(cv_qualifiers, ref_qualifier, prefix.clone(), name.clone()),
                tail,
            )),
            Some(&Substitutable::Prefix(Prefix::Template(..))) => Ok((
                NestedName::Template(cv_qualifiers, ref_qualifier, prefix),
                tail,
            )),
            _ => Err(error::Error::UnexpectedText),
        }
    }
}

impl NestedName {