Quelle  context.rs   Sprache: unbekannt

//! Common context that is passed around during parsing and codegen.

use super::super::time::Timer;
use super::analysis::{
    analyze, as_cannot_derive_set, CannotDerive, DeriveTrait,
    HasDestructorAnalysis, HasFloat, HasTypeParameterInArray,
    HasVtableAnalysis, HasVtableResult, SizednessAnalysis, SizednessResult,
    UsedTemplateParameters,
};
use super::derive::{
    CanDerive, CanDeriveCopy, CanDeriveDebug, CanDeriveDefault, CanDeriveEq,
    CanDeriveHash, CanDeriveOrd, CanDerivePartialEq, CanDerivePartialOrd,
};
use super::function::Function;
use super::int::IntKind;
use super::item::{IsOpaque, Item, ItemAncestors, ItemSet};
use super::item_kind::ItemKind;
use super::module::{Module, ModuleKind};
use super::template::{TemplateInstantiation, TemplateParameters};
use super::traversal::{self, Edge, ItemTraversal};
use super::ty::{FloatKind, Type, TypeKind};
use crate::clang::{self, ABIKind, Cursor};
use crate::codegen::CodegenError;
use crate::BindgenOptions;
use crate::{Entry, HashMap, HashSet};

use proc_macro2::{Ident, Span, TokenStream};
use quote::ToTokens;
use std::borrow::Cow;
use std::cell::{Cell, RefCell};
use std::collections::{BTreeSet, HashMap as StdHashMap};
use std::iter::IntoIterator;
use std::mem;

/// An identifier for some kind of IR item.
#[derive(Debug, Copy, Clone, Eq, PartialOrd, Ord, Hash)]
pub(crate) struct ItemId(usize);

/// Declare a newtype around `ItemId` with convesion methods.
macro_rules! item_id_newtype {
    (
        $( #[$attr:meta] )*
        pub(crate) struct $name:ident(ItemId)
        where
            $( #[$checked_attr:meta] )*
            checked = $checked:ident with $check_method:ident,
            $( #[$expected_attr:meta] )*
            expected = $expected:ident,
            $( #[$unchecked_attr:meta] )*
            unchecked = $unchecked:ident;
    ) => {
        $( #[$attr] )*
        #[derive(Debug, Copy, Clone, Eq, PartialOrd, Ord, Hash)]
        pub(crate) struct $name(ItemId);

        impl $name {
            /// Create an `ItemResolver` from this ID.
            #[allow(dead_code)]
            pub(crate) fn into_resolver(self) -> ItemResolver {
                let id: ItemId = self.into();
                id.into()
            }
        }

        impl<T> ::std::cmp::PartialEq<T> for $name
        where
            T: Copy + Into<ItemId>
        {
            fn eq(&self, rhs: &T) -> bool {
                let rhs: ItemId = (*rhs).into();
                self.0 == rhs
            }
        }

        impl From<$name> for ItemId {
            fn from(id: $name) -> ItemId {
                id.0
            }
        }

        impl<'a> From<&'a $name> for ItemId {
            fn from(id: &'a $name) -> ItemId {
                id.0
            }
        }

        #[allow(dead_code)]
        impl ItemId {
            $( #[$checked_attr] )*
            pub(crate) fn $checked(&self, ctx: &BindgenContext) -> Option<$name> {
                if ctx.resolve_item(*self).kind().$check_method() {
                    Some($name(*self))
                } else {
                    None
                }
            }

            $( #[$expected_attr] )*
            pub(crate) fn $expected(&self, ctx: &BindgenContext) -> $name {
                self.$checked(ctx)
                    .expect(concat!(
                        stringify!($expected),
                        " called with ItemId that points to the wrong ItemKind"
                    ))
            }

            $( #[$unchecked_attr] )*
            pub(crate) fn $unchecked(&self) -> $name {
                $name(*self)
            }
        }
    }
}

item_id_newtype! {
    /// An identifier for an `Item` whose `ItemKind` is known to be
    /// `ItemKind::Type`.
    pub(crate) struct TypeId(ItemId)
    where
        /// Convert this `ItemId` into a `TypeId` if its associated item is a type,
        /// otherwise return `None`.
        checked = as_type_id with is_type,

        /// Convert this `ItemId` into a `TypeId`.
        ///
        /// If this `ItemId` does not point to a type, then panic.
        expected = expect_type_id,

        /// Convert this `ItemId` into a `TypeId` without actually checking whether
        /// this ID actually points to a `Type`.
        unchecked = as_type_id_unchecked;
}

item_id_newtype! {
    /// An identifier for an `Item` whose `ItemKind` is known to be
    /// `ItemKind::Module`.
    pub(crate) struct ModuleId(ItemId)
    where
        /// Convert this `ItemId` into a `ModuleId` if its associated item is a
        /// module, otherwise return `None`.
        checked = as_module_id with is_module,

        /// Convert this `ItemId` into a `ModuleId`.
        ///
        /// If this `ItemId` does not point to a module, then panic.
        expected = expect_module_id,

        /// Convert this `ItemId` into a `ModuleId` without actually checking
        /// whether this ID actually points to a `Module`.
        unchecked = as_module_id_unchecked;
}

item_id_newtype! {
    /// An identifier for an `Item` whose `ItemKind` is known to be
    /// `ItemKind::Var`.
    pub(crate) struct VarId(ItemId)
    where
        /// Convert this `ItemId` into a `VarId` if its associated item is a var,
        /// otherwise return `None`.
        checked = as_var_id with is_var,

        /// Convert this `ItemId` into a `VarId`.
        ///
        /// If this `ItemId` does not point to a var, then panic.
        expected = expect_var_id,

        /// Convert this `ItemId` into a `VarId` without actually checking whether
        /// this ID actually points to a `Var`.
        unchecked = as_var_id_unchecked;
}

item_id_newtype! {
    /// An identifier for an `Item` whose `ItemKind` is known to be
    /// `ItemKind::Function`.
    pub(crate) struct FunctionId(ItemId)
    where
        /// Convert this `ItemId` into a `FunctionId` if its associated item is a function,
        /// otherwise return `None`.
        checked = as_function_id with is_function,

        /// Convert this `ItemId` into a `FunctionId`.
        ///
        /// If this `ItemId` does not point to a function, then panic.
        expected = expect_function_id,

        /// Convert this `ItemId` into a `FunctionId` without actually checking whether
        /// this ID actually points to a `Function`.
        unchecked = as_function_id_unchecked;
}

impl From<ItemId> for usize {
    fn from(id: ItemId) -> usize {
        id.0
    }
}

impl ItemId {
    /// Get a numeric representation of this ID.
    pub(crate) fn as_usize(&self) -> usize {
        (*self).into()
    }
}

impl<T> ::std::cmp::PartialEq<T> for ItemId
where
    T: Copy + Into<ItemId>,
{
    fn eq(&self, rhs: &T) -> bool {
        let rhs: ItemId = (*rhs).into();
        self.0 == rhs.0
    }
}

impl<T> CanDeriveDebug for T
where
    T: Copy + Into<ItemId>,
{
    fn can_derive_debug(&self, ctx: &BindgenContext) -> bool {
        ctx.options().derive_debug && ctx.lookup_can_derive_debug(*self)
    }
}

impl<T> CanDeriveDefault for T
where
    T: Copy + Into<ItemId>,
{
    fn can_derive_default(&self, ctx: &BindgenContext) -> bool {
        ctx.options().derive_default && ctx.lookup_can_derive_default(*self)
    }
}

impl<T> CanDeriveCopy for T
where
    T: Copy + Into<ItemId>,
{
    fn can_derive_copy(&self, ctx: &BindgenContext) -> bool {
        ctx.options().derive_copy && ctx.lookup_can_derive_copy(*self)
    }
}

impl<T> CanDeriveHash for T
where
    T: Copy + Into<ItemId>,
{
    fn can_derive_hash(&self, ctx: &BindgenContext) -> bool {
        ctx.options().derive_hash && ctx.lookup_can_derive_hash(*self)
    }
}

impl<T> CanDerivePartialOrd for T
where
    T: Copy + Into<ItemId>,
{
    fn can_derive_partialord(&self, ctx: &BindgenContext) -> bool {
        ctx.options().derive_partialord &&
            ctx.lookup_can_derive_partialeq_or_partialord(*self) ==
                CanDerive::Yes
    }
}

impl<T> CanDerivePartialEq for T
where
    T: Copy + Into<ItemId>,
{
    fn can_derive_partialeq(&self, ctx: &BindgenContext) -> bool {
        ctx.options().derive_partialeq &&
            ctx.lookup_can_derive_partialeq_or_partialord(*self) ==
                CanDerive::Yes
    }
}

impl<T> CanDeriveEq for T
where
    T: Copy + Into<ItemId>,
{
    fn can_derive_eq(&self, ctx: &BindgenContext) -> bool {
        ctx.options().derive_eq &&
            ctx.lookup_can_derive_partialeq_or_partialord(*self) ==
                CanDerive::Yes &&
            !ctx.lookup_has_float(*self)
    }
}

impl<T> CanDeriveOrd for T
where
    T: Copy + Into<ItemId>,
{
    fn can_derive_ord(&self, ctx: &BindgenContext) -> bool {
        ctx.options().derive_ord &&
            ctx.lookup_can_derive_partialeq_or_partialord(*self) ==
                CanDerive::Yes &&
            !ctx.lookup_has_float(*self)
    }
}

/// A key used to index a resolved type, so we only process it once.
///
/// This is almost always a USR string (an unique identifier generated by
/// clang), but it can also be the canonical declaration if the type is unnamed,
/// in which case clang may generate the same USR for multiple nested unnamed
/// types.
#[derive(Eq, PartialEq, Hash, Debug)]
enum TypeKey {
    Usr(String),
    Declaration(Cursor),
}

/// A context used during parsing and generation of structs.
#[derive(Debug)]
pub(crate) struct BindgenContext {
    /// The map of all the items parsed so far, keyed off ItemId.
    items: Vec<Option<Item>>,

    /// Clang USR to type map. This is needed to be able to associate types with
    /// item ids during parsing.
    types: HashMap<TypeKey, TypeId>,

    /// Maps from a cursor to the item ID of the named template type parameter
    /// for that cursor.
    type_params: HashMap<clang::Cursor, TypeId>,

    /// A cursor to module map. Similar reason than above.
    modules: HashMap<Cursor, ModuleId>,

    /// The root module, this is guaranteed to be an item of kind Module.
    root_module: ModuleId,

    /// Current module being traversed.
    current_module: ModuleId,

    /// A HashMap keyed on a type definition, and whose value is the parent ID
    /// of the declaration.
    ///
    /// This is used to handle the cases where the semantic and the lexical
    /// parents of the cursor differ, like when a nested class is defined
    /// outside of the parent class.
    semantic_parents: HashMap<clang::Cursor, ItemId>,

    /// A stack with the current type declarations and types we're parsing. This
    /// is needed to avoid infinite recursion when parsing a type like:
    ///
    /// struct c { struct c* next; };
    ///
    /// This means effectively, that a type has a potential ID before knowing if
    /// it's a correct type. But that's not important in practice.
    ///
    /// We could also use the `types` HashMap, but my intention with it is that
    /// only valid types and declarations end up there, and this could
    /// potentially break that assumption.
    currently_parsed_types: Vec<PartialType>,

    /// A map with all the already parsed macro names. This is done to avoid
    /// hard errors while parsing duplicated macros, as well to allow macro
    /// expression parsing.
    ///
    /// This needs to be an std::HashMap because the cexpr API requires it.
    parsed_macros: StdHashMap<Vec<u8>, cexpr::expr::EvalResult>,

    /// A map with all include locations.
    ///
    /// This is needed so that items are created in the order they are defined in.
    ///
    /// The key is the included file, the value is a pair of the source file and
    /// the position of the `#include` directive in the source file.
    includes: StdHashMap<String, (String, usize)>,

    /// A set of all the included filenames.
    deps: BTreeSet<Box<str>>,

    /// The active replacements collected from replaces="xxx" annotations.
    replacements: HashMap<Vec<String>, ItemId>,

    collected_typerefs: bool,

    in_codegen: bool,

    /// The translation unit for parsing.
    translation_unit: clang::TranslationUnit,

    /// Target information that can be useful for some stuff.
    target_info: clang::TargetInfo,

    /// The options given by the user via cli or other medium.
    options: BindgenOptions,

    /// Whether a bindgen complex was generated
    generated_bindgen_complex: Cell<bool>,

    /// Whether a bindgen float16 was generated
    generated_bindgen_float16: Cell<bool>,

    /// The set of `ItemId`s that are allowlisted. This the very first thing
    /// computed after parsing our IR, and before running any of our analyses.
    allowlisted: Option<ItemSet>,

    /// Cache for calls to `ParseCallbacks::blocklisted_type_implements_trait`
    blocklisted_types_implement_traits:
        RefCell<HashMap<DeriveTrait, HashMap<ItemId, CanDerive>>>,

    /// The set of `ItemId`s that are allowlisted for code generation _and_ that
    /// we should generate accounting for the codegen options.
    ///
    /// It's computed right after computing the allowlisted items.
    codegen_items: Option<ItemSet>,

    /// Map from an item's ID to the set of template parameter items that it
    /// uses. See `ir::named` for more details. Always `Some` during the codegen
    /// phase.
    used_template_parameters: Option<HashMap<ItemId, ItemSet>>,

    /// The set of `TypeKind::Comp` items found during parsing that need their
    /// bitfield allocation units computed. Drained in `compute_bitfield_units`.
    need_bitfield_allocation: Vec<ItemId>,

    /// The set of enums that are defined by a pair of `enum` and `typedef`,
    /// which is legal in C (but not C++).
    ///
    /// ```c++
    /// // in either order
    /// enum Enum { Variants... };
    /// typedef int16_t Enum;
    /// ```
    ///
    /// The stored `ItemId` is that of the `TypeKind::Enum`, not of the
    /// `TypeKind::Alias`.
    ///
    /// This is populated when we enter codegen by `compute_enum_typedef_combos`
    /// and is always `None` before that and `Some` after.
    enum_typedef_combos: Option<HashSet<ItemId>>,

    /// The set of (`ItemId`s of) types that can't derive debug.
    ///
    /// This is populated when we enter codegen by `compute_cannot_derive_debug`
    /// and is always `None` before that and `Some` after.
    cannot_derive_debug: Option<HashSet<ItemId>>,

    /// The set of (`ItemId`s of) types that can't derive default.
    ///
    /// This is populated when we enter codegen by `compute_cannot_derive_default`
    /// and is always `None` before that and `Some` after.
    cannot_derive_default: Option<HashSet<ItemId>>,

    /// The set of (`ItemId`s of) types that can't derive copy.
    ///
    /// This is populated when we enter codegen by `compute_cannot_derive_copy`
    /// and is always `None` before that and `Some` after.
    cannot_derive_copy: Option<HashSet<ItemId>>,

    /// The set of (`ItemId`s of) types that can't derive hash.
    ///
    /// This is populated when we enter codegen by `compute_can_derive_hash`
    /// and is always `None` before that and `Some` after.
    cannot_derive_hash: Option<HashSet<ItemId>>,

    /// The map why specified `ItemId`s of) types that can't derive hash.
    ///
    /// This is populated when we enter codegen by
    /// `compute_cannot_derive_partialord_partialeq_or_eq` and is always `None`
    /// before that and `Some` after.
    cannot_derive_partialeq_or_partialord: Option<HashMap<ItemId, CanDerive>>,

    /// The sizedness of types.
    ///
    /// This is populated by `compute_sizedness` and is always `None` before
    /// that function is invoked and `Some` afterwards.
    sizedness: Option<HashMap<TypeId, SizednessResult>>,

    /// The set of (`ItemId's of`) types that has vtable.
    ///
    /// Populated when we enter codegen by `compute_has_vtable`; always `None`
    /// before that and `Some` after.
    have_vtable: Option<HashMap<ItemId, HasVtableResult>>,

    /// The set of (`ItemId's of`) types that has destructor.
    ///
    /// Populated when we enter codegen by `compute_has_destructor`; always `None`
    /// before that and `Some` after.
    have_destructor: Option<HashSet<ItemId>>,

    /// The set of (`ItemId's of`) types that has array.
    ///
    /// Populated when we enter codegen by `compute_has_type_param_in_array`; always `None`
    /// before that and `Some` after.
    has_type_param_in_array: Option<HashSet<ItemId>>,

    /// The set of (`ItemId's of`) types that has float.
    ///
    /// Populated when we enter codegen by `compute_has_float`; always `None`
    /// before that and `Some` after.
    has_float: Option<HashSet<ItemId>>,
}

/// A traversal of allowlisted items.
struct AllowlistedItemsTraversal<'ctx> {
    ctx: &'ctx BindgenContext,
    traversal: ItemTraversal<'ctx, ItemSet, Vec<ItemId>>,
}

impl<'ctx> Iterator for AllowlistedItemsTraversal<'ctx> {
    type Item = ItemId;

    fn next(&mut self) -> Option<ItemId> {
        loop {
            let id = self.traversal.next()?;

            if self.ctx.resolve_item(id).is_blocklisted(self.ctx) {
                continue;
            }

            return Some(id);
        }
    }
}

impl<'ctx> AllowlistedItemsTraversal<'ctx> {
    /// Construct a new allowlisted items traversal.
    pub(crate) fn new<R>(
        ctx: &'ctx BindgenContext,
        roots: R,
        predicate: for<'a> fn(&'a BindgenContext, Edge) -> bool,
    ) -> Self
    where
        R: IntoIterator<Item = ItemId>,
    {
        AllowlistedItemsTraversal {
            ctx,
            traversal: ItemTraversal::new(ctx, roots, predicate),
        }
    }
}

impl BindgenContext {
    /// Construct the context for the given `options`.
    pub(crate) fn new(
        options: BindgenOptions,
        input_unsaved_files: &[clang::UnsavedFile],
    ) -> Self {
        // TODO(emilio): Use the CXTargetInfo here when available.
        //
        // see: https://reviews.llvm.org/D32389
        let index = clang::Index::new(false, true);

        let parse_options =
            clang_sys::CXTranslationUnit_DetailedPreprocessingRecord;

        let translation_unit = {
            let _t =
                Timer::new("translation_unit").with_output(options.time_phases);

            clang::TranslationUnit::parse(
                &index,
                "",
                &options.clang_args,
                input_unsaved_files,
                parse_options,
            ).expect("libclang error; possible causes include:
- Invalid flag syntax
- Unrecognized flags
- Invalid flag arguments
- File I/O errors
- Host vs. target architecture mismatch
If you encounter an error missing from this list, please file an issue or a PR!")
        };

        let target_info = clang::TargetInfo::new(&translation_unit);
        let root_module = Self::build_root_module(ItemId(0));
        let root_module_id = root_module.id().as_module_id_unchecked();

        // depfiles need to include the explicitly listed headers too
        let deps = options.input_headers.iter().cloned().collect();

        BindgenContext {
            items: vec![Some(root_module)],
            includes: Default::default(),
            deps,
            types: Default::default(),
            type_params: Default::default(),
            modules: Default::default(),
            root_module: root_module_id,
            current_module: root_module_id,
            semantic_parents: Default::default(),
            currently_parsed_types: vec![],
            parsed_macros: Default::default(),
            replacements: Default::default(),
            collected_typerefs: false,
            in_codegen: false,
            translation_unit,
            target_info,
            options,
            generated_bindgen_complex: Cell::new(false),
            generated_bindgen_float16: Cell::new(false),
            allowlisted: None,
            blocklisted_types_implement_traits: Default::default(),
            codegen_items: None,
            used_template_parameters: None,
            need_bitfield_allocation: Default::default(),
            enum_typedef_combos: None,
            cannot_derive_debug: None,
            cannot_derive_default: None,
            cannot_derive_copy: None,
            cannot_derive_hash: None,
            cannot_derive_partialeq_or_partialord: None,
            sizedness: None,
            have_vtable: None,
            have_destructor: None,
            has_type_param_in_array: None,
            has_float: None,
        }
    }

    /// Returns `true` if the target architecture is wasm32
    pub(crate) fn is_target_wasm32(&self) -> bool {
        self.target_info.triple.starts_with("wasm32-")
    }

    /// Creates a timer for the current bindgen phase. If time_phases is `true`,
    /// the timer will print to stderr when it is dropped, otherwise it will do
    /// nothing.
    pub(crate) fn timer<'a>(&self, name: &'a str) -> Timer<'a> {
        Timer::new(name).with_output(self.options.time_phases)
    }

    /// Returns the pointer width to use for the target for the current
    /// translation.
    pub(crate) fn target_pointer_size(&self) -> usize {
        self.target_info.pointer_width / 8
    }

    /// Returns the ABI, which is mostly useful for determining the mangling kind.
    pub(crate) fn abi_kind(&self) -> ABIKind {
        self.target_info.abi
    }

    /// Get the stack of partially parsed types that we are in the middle of
    /// parsing.
    pub(crate) fn currently_parsed_types(&self) -> &[PartialType] {
        &self.currently_parsed_types[..]
    }

    /// Begin parsing the given partial type, and push it onto the
    /// `currently_parsed_types` stack so that we won't infinite recurse if we
    /// run into a reference to it while parsing it.
    pub(crate) fn begin_parsing(&mut self, partial_ty: PartialType) {
        self.currently_parsed_types.push(partial_ty);
    }

    /// Finish parsing the current partial type, pop it off the
    /// `currently_parsed_types` stack, and return it.
    pub(crate) fn finish_parsing(&mut self) -> PartialType {
        self.currently_parsed_types.pop().expect(
            "should have been parsing a type, if we finished parsing a type",
        )
    }

    /// Add the location of the `#include` directive for the `included_file`.
    pub(crate) fn add_include(
        &mut self,
        source_file: String,
        included_file: String,
        offset: usize,
    ) {
        self.includes
            .entry(included_file)
            .or_insert((source_file, offset));
    }

    /// Get the location of the first `#include` directive for the `included_file`.
    pub(crate) fn included_file_location(
        &self,
        included_file: &str,
    ) -> Option<(String, usize)> {
        self.includes.get(included_file).cloned()
    }

    /// Add an included file.
    pub(crate) fn add_dep(&mut self, dep: Box<str>) {
        self.deps.insert(dep);
    }

    /// Get any included files.
    pub(crate) fn deps(&self) -> &BTreeSet<Box<str>> {
        &self.deps
    }

    /// Define a new item.
    ///
    /// This inserts it into the internal items set, and its type into the
    /// internal types set.
    pub(crate) fn add_item(
        &mut self,
        item: Item,
        declaration: Option<Cursor>,
        location: Option<Cursor>,
    ) {
        debug!(
            "BindgenContext::add_item({:?}, declaration: {:?}, loc: {:?}",
            item, declaration, location
        );
        debug_assert!(
            declaration.is_some() ||
                !item.kind().is_type() ||
                item.kind().expect_type().is_builtin_or_type_param() ||
                item.kind().expect_type().is_opaque(self, &item) ||
                item.kind().expect_type().is_unresolved_ref(),
            "Adding a type without declaration?"
        );

        let id = item.id();
        let is_type = item.kind().is_type();
        let is_unnamed = is_type && item.expect_type().name().is_none();
        let is_template_instantiation =
            is_type && item.expect_type().is_template_instantiation();

        if item.id() != self.root_module {
            self.add_item_to_module(&item);
        }

        if is_type && item.expect_type().is_comp() {
            self.need_bitfield_allocation.push(id);
        }

        let old_item = mem::replace(&mut self.items[id.0], Some(item));
        assert!(
            old_item.is_none(),
            "should not have already associated an item with the given id"
        );

        // Unnamed items can have an USR, but they can't be referenced from
        // other sites explicitly and the USR can match if the unnamed items are
        // nested, so don't bother tracking them.
        if !is_type || is_template_instantiation {
            return;
        }
        if let Some(mut declaration) = declaration {
            if !declaration.is_valid() {
                if let Some(location) = location {
                    if location.is_template_like() {
                        declaration = location;
                    }
                }
            }
            declaration = declaration.canonical();
            if !declaration.is_valid() {
                // This could happen, for example, with types like `int*` or
                // similar.
                //
                // Fortunately, we don't care about those types being
                // duplicated, so we can just ignore them.
                debug!(
                    "Invalid declaration {:?} found for type {:?}",
                    declaration,
                    self.resolve_item_fallible(id)
                        .unwrap()
                        .kind()
                        .expect_type()
                );
                return;
            }

            let key = if is_unnamed {
                TypeKey::Declaration(declaration)
            } else if let Some(usr) = declaration.usr() {
                TypeKey::Usr(usr)
            } else {
                warn!(
                    "Valid declaration with no USR: {:?}, {:?}",
                    declaration, location
                );
                TypeKey::Declaration(declaration)
            };

            let old = self.types.insert(key, id.as_type_id_unchecked());
            debug_assert_eq!(old, None);
        }
    }

    /// Ensure that every item (other than the root module) is in a module's
    /// children list. This is to make sure that every allowlisted item get's
    /// codegen'd, even if its parent is not allowlisted. See issue #769 for
    /// details.
    fn add_item_to_module(&mut self, item: &Item) {
        assert!(item.id() != self.root_module);
        assert!(self.resolve_item_fallible(item.id()).is_none());

        if let Some(ref mut parent) = self.items[item.parent_id().0] {
            if let Some(module) = parent.as_module_mut() {
                debug!(
                    "add_item_to_module: adding {:?} as child of parent module {:?}",
                    item.id(),
                    item.parent_id()
                );

                module.children_mut().insert(item.id());
                return;
            }
        }

        debug!(
            "add_item_to_module: adding {:?} as child of current module {:?}",
            item.id(),
            self.current_module
        );

        self.items[(self.current_module.0).0]
            .as_mut()
            .expect("Should always have an item for self.current_module")
            .as_module_mut()
            .expect("self.current_module should always be a module")
            .children_mut()
            .insert(item.id());
    }

    /// Add a new named template type parameter to this context's item set.
    pub(crate) fn add_type_param(
        &mut self,
        item: Item,
        definition: clang::Cursor,
    ) {
        debug!(
            "BindgenContext::add_type_param: item = {:?}; definition = {:?}",
            item, definition
        );

        assert!(
            item.expect_type().is_type_param(),
            "Should directly be a named type, not a resolved reference or anything"
        );
        assert_eq!(
            definition.kind(),
            clang_sys::CXCursor_TemplateTypeParameter
        );

        self.add_item_to_module(&item);

        let id = item.id();
        let old_item = mem::replace(&mut self.items[id.0], Some(item));
        assert!(
            old_item.is_none(),
            "should not have already associated an item with the given id"
        );

        let old_named_ty = self
            .type_params
            .insert(definition, id.as_type_id_unchecked());
        assert!(
            old_named_ty.is_none(),
            "should not have already associated a named type with this id"
        );
    }

    /// Get the named type defined at the given cursor location, if we've
    /// already added one.
    pub(crate) fn get_type_param(
        &self,
        definition: &clang::Cursor,
    ) -> Option<TypeId> {
        assert_eq!(
            definition.kind(),
            clang_sys::CXCursor_TemplateTypeParameter
        );
        self.type_params.get(definition).cloned()
    }

    // TODO: Move all this syntax crap to other part of the code.

    /// Mangles a name so it doesn't conflict with any keyword.
    #[rustfmt::skip]
    pub(crate) fn rust_mangle<'a>(&self, name: &'a str) -> Cow<'a, str> {
        if name.contains('@') ||
            name.contains('?') ||
            name.contains('$') ||
            matches!(
                name,
                "abstract" | "alignof" | "as" | "async" | "await" | "become" |
                    "box" | "break" | "const" | "continue" | "crate" | "do" |
                    "dyn" | "else" | "enum" | "extern" | "false" | "final" |
                    "fn" | "for" | "if" | "impl" | "in" | "let" | "loop" |
                    "macro" | "match" | "mod" | "move" | "mut" | "offsetof" |
                    "override" | "priv" | "proc" | "pub" | "pure" | "ref" |
                    "return" | "Self" | "self" | "sizeof" | "static" |
                    "struct" | "super" | "trait" | "true" | "try" | "type" | "typeof" |
                    "unsafe" | "unsized" | "use" | "virtual" | "where" |
                    "while" | "yield" | "str" | "bool" | "f32" | "f64" |
                    "usize" | "isize" | "u128" | "i128" | "u64" | "i64" |
                    "u32" | "i32" | "u16" | "i16" | "u8" | "i8" | "_"
            )
        {
            let mut s = name.to_owned();
            s = s.replace('@', "_");
            s = s.replace('?', "_");
            s = s.replace('$', "_");
            s.push('_');
            return Cow::Owned(s);
        }
        Cow::Borrowed(name)
    }

    /// Returns a mangled name as a rust identifier.
    pub(crate) fn rust_ident<S>(&self, name: S) -> Ident
    where
        S: AsRef<str>,
    {
        self.rust_ident_raw(self.rust_mangle(name.as_ref()))
    }

    /// Returns a mangled name as a rust identifier.
    pub(crate) fn rust_ident_raw<T>(&self, name: T) -> Ident
    where
        T: AsRef<str>,
    {
        Ident::new(name.as_ref(), Span::call_site())
    }

    /// Iterate over all items that have been defined.
    pub(crate) fn items(&self) -> impl Iterator<Item = (ItemId, &Item)> {
        self.items.iter().enumerate().filter_map(|(index, item)| {
            let item = item.as_ref()?;
            Some((ItemId(index), item))
        })
    }

    /// Have we collected all unresolved type references yet?
    pub(crate) fn collected_typerefs(&self) -> bool {
        self.collected_typerefs
    }

    /// Gather all the unresolved type references.
    fn collect_typerefs(
        &mut self,
    ) -> Vec<(ItemId, clang::Type, clang::Cursor, Option<ItemId>)> {
        debug_assert!(!self.collected_typerefs);
        self.collected_typerefs = true;
        let mut typerefs = vec![];

        for (id, item) in self.items() {
            let kind = item.kind();
            let ty = match kind.as_type() {
                Some(ty) => ty,
                None => continue,
            };

            if let TypeKind::UnresolvedTypeRef(ref ty, loc, parent_id) =
                *ty.kind()
            {
                typerefs.push((id, *ty, loc, parent_id));
            };
        }
        typerefs
    }

    /// Collect all of our unresolved type references and resolve them.
    fn resolve_typerefs(&mut self) {
        let _t = self.timer("resolve_typerefs");

        let typerefs = self.collect_typerefs();

        for (id, ty, loc, parent_id) in typerefs {
            let _resolved =
                {
                    let resolved = Item::from_ty(&ty, loc, parent_id, self)
                    .unwrap_or_else(|_| {
                        warn!("Could not resolve type reference, falling back \
                               to opaque blob");
                        Item::new_opaque_type(self.next_item_id(), &ty, self)
                    });

                    let item = self.items[id.0].as_mut().unwrap();
                    *item.kind_mut().as_type_mut().unwrap().kind_mut() =
                        TypeKind::ResolvedTypeRef(resolved);
                    resolved
                };

            // Something in the STL is trolling me. I don't need this assertion
            // right now, but worth investigating properly once this lands.
            //
            // debug_assert!(self.items.get(&resolved).is_some(), "How?");
            //
            // if let Some(parent_id) = parent_id {
            //     assert_eq!(self.items[&resolved].parent_id(), parent_id);
            // }
        }
    }

    /// Temporarily loan `Item` with the given `ItemId`. This provides means to
    /// mutably borrow `Item` while having a reference to `BindgenContext`.
    ///
    /// `Item` with the given `ItemId` is removed from the context, given
    /// closure is executed and then `Item` is placed back.
    ///
    /// # Panics
    ///
    /// Panics if attempt to resolve given `ItemId` inside the given
    /// closure is made.
    fn with_loaned_item<F, T>(&mut self, id: ItemId, f: F) -> T
    where
        F: (FnOnce(&BindgenContext, &mut Item) -> T),
    {
        let mut item = self.items[id.0].take().unwrap();

        let result = f(self, &mut item);

        let existing = mem::replace(&mut self.items[id.0], Some(item));
        assert!(existing.is_none());

        result
    }

    /// Compute the bitfield allocation units for all `TypeKind::Comp` items we
    /// parsed.
    fn compute_bitfield_units(&mut self) {
        let _t = self.timer("compute_bitfield_units");

        assert!(self.collected_typerefs());

        let need_bitfield_allocation =
            mem::take(&mut self.need_bitfield_allocation);
        for id in need_bitfield_allocation {
            self.with_loaned_item(id, |ctx, item| {
                let ty = item.kind_mut().as_type_mut().unwrap();
                let layout = ty.layout(ctx);
                ty.as_comp_mut()
                    .unwrap()
                    .compute_bitfield_units(ctx, layout.as_ref());
            });
        }
    }

    /// Assign a new generated name for each anonymous field.
    fn deanonymize_fields(&mut self) {
        let _t = self.timer("deanonymize_fields");

        let comp_item_ids: Vec<ItemId> = self
            .items()
            .filter_map(|(id, item)| {
                if item.kind().as_type()?.is_comp() {
                    return Some(id);
                }
                None
            })
            .collect();

        for id in comp_item_ids {
            self.with_loaned_item(id, |ctx, item| {
                item.kind_mut()
                    .as_type_mut()
                    .unwrap()
                    .as_comp_mut()
                    .unwrap()
                    .deanonymize_fields(ctx);
            });
        }
    }

    /// Iterate over all items and replace any item that has been named in a
    /// `replaces="SomeType"` annotation with the replacement type.
    fn process_replacements(&mut self) {
        let _t = self.timer("process_replacements");
        if self.replacements.is_empty() {
            debug!("No replacements to process");
            return;
        }

        // FIXME: This is linear, but the replaces="xxx" annotation was already
        // there, and for better or worse it's useful, sigh...
        //
        // We leverage the ResolvedTypeRef thing, though, which is cool :P.

        let mut replacements = vec![];

        for (id, item) in self.items() {
            if item.annotations().use_instead_of().is_some() {
                continue;
            }

            // Calls to `canonical_name` are expensive, so eagerly filter out
            // items that cannot be replaced.
            let ty = match item.kind().as_type() {
                Some(ty) => ty,
                None => continue,
            };

            match *ty.kind() {
                TypeKind::Comp(..) |
                TypeKind::TemplateAlias(..) |
                TypeKind::Enum(..) |
                TypeKind::Alias(..) => {}
                _ => continue,
            }

            let path = item.path_for_allowlisting(self);
            let replacement = self.replacements.get(&path[1..]);

            if let Some(replacement) = replacement {
                if *replacement != id {
                    // We set this just after parsing the annotation. It's
                    // very unlikely, but this can happen.
                    if self.resolve_item_fallible(*replacement).is_some() {
                        replacements.push((
                            id.expect_type_id(self),
                            replacement.expect_type_id(self),
                        ));
                    }
                }
            }
        }

        for (id, replacement_id) in replacements {
            debug!("Replacing {:?} with {:?}", id, replacement_id);
            let new_parent = {
                let item_id: ItemId = id.into();
                let item = self.items[item_id.0].as_mut().unwrap();
                *item.kind_mut().as_type_mut().unwrap().kind_mut() =
                    TypeKind::ResolvedTypeRef(replacement_id);
                item.parent_id()
            };

            // Relocate the replacement item from where it was declared, to
            // where the thing it is replacing was declared.
            //
            // First, we'll make sure that its parent ID is correct.

            let old_parent = self.resolve_item(replacement_id).parent_id();
            if new_parent == old_parent {
                // Same parent and therefore also same containing
                // module. Nothing to do here.
                continue;
            }

            let replacement_item_id: ItemId = replacement_id.into();
            self.items[replacement_item_id.0]
                .as_mut()
                .unwrap()
                .set_parent_for_replacement(new_parent);

            // Second, make sure that it is in the correct module's children
            // set.

            let old_module = {
                let immut_self = &*self;
                old_parent
                    .ancestors(immut_self)
                    .chain(Some(immut_self.root_module.into()))
                    .find(|id| {
                        let item = immut_self.resolve_item(*id);
                        item.as_module().map_or(false, |m| {
                            m.children().contains(&replacement_id.into())
                        })
                    })
            };
            let old_module = old_module
                .expect("Every replacement item should be in a module");

            let new_module = {
                let immut_self = &*self;
                new_parent
                    .ancestors(immut_self)
                    .find(|id| immut_self.resolve_item(*id).is_module())
            };
            let new_module =
                new_module.unwrap_or_else(|| self.root_module.into());

            if new_module == old_module {
                // Already in the correct module.
                continue;
            }

            self.items[old_module.0]
                .as_mut()
                .unwrap()
                .as_module_mut()
                .unwrap()
                .children_mut()
                .remove(&replacement_id.into());

            self.items[new_module.0]
                .as_mut()
                .unwrap()
                .as_module_mut()
                .unwrap()
                .children_mut()
                .insert(replacement_id.into());
        }
    }

    /// Enter the code generation phase, invoke the given callback `cb`, and
    /// leave the code generation phase.
    pub(crate) fn gen<F, Out>(
        mut self,
        cb: F,
    ) -> Result<(Out, BindgenOptions), CodegenError>
    where
        F: FnOnce(&Self) -> Result<Out, CodegenError>,
    {
        self.in_codegen = true;

        self.resolve_typerefs();
        self.compute_bitfield_units();
        self.process_replacements();

        self.deanonymize_fields();

        self.assert_no_dangling_references();

        // Compute the allowlisted set after processing replacements and
        // resolving type refs, as those are the final mutations of the IR
        // graph, and their completion means that the IR graph is now frozen.
        self.compute_allowlisted_and_codegen_items();

        // Make sure to do this after processing replacements, since that messes
        // with the parentage and module children, and we want to assert that it
        // messes with them correctly.
        self.assert_every_item_in_a_module();

        self.compute_has_vtable();
        self.compute_sizedness();
        self.compute_has_destructor();
        self.find_used_template_parameters();
        self.compute_enum_typedef_combos();
        self.compute_cannot_derive_debug();
        self.compute_cannot_derive_default();
        self.compute_cannot_derive_copy();
        self.compute_has_type_param_in_array();
        self.compute_has_float();
        self.compute_cannot_derive_hash();
        self.compute_cannot_derive_partialord_partialeq_or_eq();

        let ret = cb(&self)?;
        Ok((ret, self.options))
    }

    /// When the `__testing_only_extra_assertions` feature is enabled, this
    /// function walks the IR graph and asserts that we do not have any edges
    /// referencing an ItemId for which we do not have an associated IR item.
    fn assert_no_dangling_references(&self) {
        if cfg!(feature = "__testing_only_extra_assertions") {
            for _ in self.assert_no_dangling_item_traversal() {
                // The iterator's next method does the asserting for us.
            }
        }
    }

    fn assert_no_dangling_item_traversal(
        &self,
    ) -> traversal::AssertNoDanglingItemsTraversal {
        assert!(self.in_codegen_phase());
        assert!(self.current_module == self.root_module);

        let roots = self.items().map(|(id, _)| id);
        traversal::AssertNoDanglingItemsTraversal::new(
            self,
            roots,
            traversal::all_edges,
        )
    }

    /// When the `__testing_only_extra_assertions` feature is enabled, walk over
    /// every item and ensure that it is in the children set of one of its
    /// module ancestors.
    fn assert_every_item_in_a_module(&self) {
        if cfg!(feature = "__testing_only_extra_assertions") {
            assert!(self.in_codegen_phase());
            assert!(self.current_module == self.root_module);

            for (id, _item) in self.items() {
                if id == self.root_module {
                    continue;
                }

                assert!(
                    {
                        let id = id
                            .into_resolver()
                            .through_type_refs()
                            .through_type_aliases()
                            .resolve(self)
                            .id();
                        id.ancestors(self)
                            .chain(Some(self.root_module.into()))
                            .any(|ancestor| {
                                debug!(
                                    "Checking if {:?} is a child of {:?}",
                                    id, ancestor
                                );
                                self.resolve_item(ancestor)
                                    .as_module()
                                    .map_or(false, |m| {
                                        m.children().contains(&id)
                                    })
                            })
                    },
                    "{:?} should be in some ancestor module's children set",
                    id
                );
            }
        }
    }

    /// Compute for every type whether it is sized or not, and whether it is
    /// sized or not as a base class.
    fn compute_sizedness(&mut self) {
        let _t = self.timer("compute_sizedness");
        assert!(self.sizedness.is_none());
        self.sizedness = Some(analyze::<SizednessAnalysis>(self));
    }

    /// Look up whether the type with the given ID is sized or not.
    pub(crate) fn lookup_sizedness(&self, id: TypeId) -> SizednessResult {
        assert!(
            self.in_codegen_phase(),
            "We only compute sizedness after we've entered codegen"
        );

        self.sizedness
            .as_ref()
            .unwrap()
            .get(&id)
            .cloned()
            .unwrap_or(SizednessResult::ZeroSized)
    }

    /// Compute whether the type has vtable.
    fn compute_has_vtable(&mut self) {
        let _t = self.timer("compute_has_vtable");
        assert!(self.have_vtable.is_none());
        self.have_vtable = Some(analyze::<HasVtableAnalysis>(self));
    }

    /// Look up whether the item with `id` has vtable or not.
    pub(crate) fn lookup_has_vtable(&self, id: TypeId) -> HasVtableResult {
        assert!(
            self.in_codegen_phase(),
            "We only compute vtables when we enter codegen"
        );

        // Look up the computed value for whether the item with `id` has a
        // vtable or not.
        self.have_vtable
            .as_ref()
            .unwrap()
            .get(&id.into())
            .cloned()
            .unwrap_or(HasVtableResult::No)
    }

    /// Compute whether the type has a destructor.
    fn compute_has_destructor(&mut self) {
        let _t = self.timer("compute_has_destructor");
        assert!(self.have_destructor.is_none());
        self.have_destructor = Some(analyze::<HasDestructorAnalysis>(self));
    }

    /// Look up whether the item with `id` has a destructor.
    pub(crate) fn lookup_has_destructor(&self, id: TypeId) -> bool {
        assert!(
            self.in_codegen_phase(),
            "We only compute destructors when we enter codegen"
        );

        self.have_destructor.as_ref().unwrap().contains(&id.into())
    }

    fn find_used_template_parameters(&mut self) {
        let _t = self.timer("find_used_template_parameters");
        if self.options.allowlist_recursively {
            let used_params = analyze::<UsedTemplateParameters>(self);
            self.used_template_parameters = Some(used_params);
        } else {
            // If you aren't recursively allowlisting, then we can't really make
            // any sense of template parameter usage, and you're on your own.
            let mut used_params = HashMap::default();
            for &id in self.allowlisted_items() {
                used_params.entry(id).or_insert_with(|| {
                    id.self_template_params(self)
                        .into_iter()
                        .map(|p| p.into())
                        .collect()
                });
            }
            self.used_template_parameters = Some(used_params);
        }
    }

    /// Return `true` if `item` uses the given `template_param`, `false`
    /// otherwise.
    ///
    /// This method may only be called during the codegen phase, because the
    /// template usage information is only computed as we enter the codegen
    /// phase.
    ///
    /// If the item is blocklisted, then we say that it always uses the template
    /// parameter. This is a little subtle. The template parameter usage
    /// analysis only considers allowlisted items, and if any blocklisted item
    /// shows up in the generated bindings, it is the user's responsibility to
    /// manually provide a definition for them. To give them the most
    /// flexibility when doing that, we assume that they use every template
    /// parameter and always pass template arguments through in instantiations.
    pub(crate) fn uses_template_parameter(
        &self,
        item: ItemId,
        template_param: TypeId,
    ) -> bool {
        assert!(
            self.in_codegen_phase(),
            "We only compute template parameter usage as we enter codegen"
        );

        if self.resolve_item(item).is_blocklisted(self) {
            return true;
        }

        let template_param = template_param
            .into_resolver()
            .through_type_refs()
            .through_type_aliases()
            .resolve(self)
            .id();

        self.used_template_parameters
            .as_ref()
            .expect("should have found template parameter usage if we're in codegen")
            .get(&item)
            .map_or(false, |items_used_params| items_used_params.contains(&template_param))
    }

    /// Return `true` if `item` uses any unbound, generic template parameters,
    /// `false` otherwise.
    ///
    /// Has the same restrictions that `uses_template_parameter` has.
    pub(crate) fn uses_any_template_parameters(&self, item: ItemId) -> bool {
        assert!(
            self.in_codegen_phase(),
            "We only compute template parameter usage as we enter codegen"
        );

        self.used_template_parameters
            .as_ref()
            .expect(
                "should have template parameter usage info in codegen phase",
            )
            .get(&item)
            .map_or(false, |used| !used.is_empty())
    }

    // This deserves a comment. Builtin types don't get a valid declaration, so
    // we can't add it to the cursor->type map.
    //
    // That being said, they're not generated anyway, and are few, so the
    // duplication and special-casing is fine.
    //
    // If at some point we care about the memory here, probably a map TypeKind
    // -> builtin type ItemId would be the best to improve that.
    fn add_builtin_item(&mut self, item: Item) {
        debug!("add_builtin_item: item = {:?}", item);
        debug_assert!(item.kind().is_type());
        self.add_item_to_module(&item);
        let id = item.id();
        let old_item = mem::replace(&mut self.items[id.0], Some(item));
        assert!(old_item.is_none(), "Inserted type twice?");
    }

    fn build_root_module(id: ItemId) -> Item {
        let module = Module::new(Some("root".into()), ModuleKind::Normal);
        Item::new(id, None, None, id, ItemKind::Module(module), None)
    }

    /// Get the root module.
    pub(crate) fn root_module(&self) -> ModuleId {
        self.root_module
    }

    /// Resolve a type with the given ID.
    ///
    /// Panics if there is no item for the given `TypeId` or if the resolved
    /// item is not a `Type`.
    pub(crate) fn resolve_type(&self, type_id: TypeId) -> &Type {
        self.resolve_item(type_id).kind().expect_type()
    }

    /// Resolve a function with the given ID.
    ///
    /// Panics if there is no item for the given `FunctionId` or if the resolved
    /// item is not a `Function`.
    pub(crate) fn resolve_func(&self, func_id: FunctionId) -> &Function {
        self.resolve_item(func_id).kind().expect_function()
    }

    /// Resolve the given `ItemId` as a type, or `None` if there is no item with
    /// the given ID.
    ///
    /// Panics if the ID resolves to an item that is not a type.
    pub(crate) fn safe_resolve_type(&self, type_id: TypeId) -> Option<&Type> {
        self.resolve_item_fallible(type_id)
            .map(|t| t.kind().expect_type())
    }

    /// Resolve the given `ItemId` into an `Item`, or `None` if no such item
    /// exists.
    pub(crate) fn resolve_item_fallible<Id: Into<ItemId>>(
        &self,
        id: Id,
    ) -> Option<&Item> {
        self.items.get(id.into().0)?.as_ref()
    }

    /// Resolve the given `ItemId` into an `Item`.
    ///
    /// Panics if the given ID does not resolve to any item.
    pub(crate) fn resolve_item<Id: Into<ItemId>>(&self, item_id: Id) -> &Item {
        let item_id = item_id.into();
        match self.resolve_item_fallible(item_id) {
            Some(item) => item,
            None => panic!("Not an item: {:?}", item_id),
        }
    }

    /// Get the current module.
    pub(crate) fn current_module(&self) -> ModuleId {
        self.current_module
    }

    /// Add a semantic parent for a given type definition.
    ///
    /// We do this from the type declaration, in order to be able to find the
    /// correct type definition afterwards.
    ///
    /// TODO(emilio): We could consider doing this only when
    /// declaration.lexical_parent() != definition.lexical_parent(), but it's
    /// not sure it's worth it.
    pub(crate) fn add_semantic_parent(
        &mut self,
        definition: clang::Cursor,
        parent_id: ItemId,
    ) {
        self.semantic_parents.insert(definition, parent_id);
    }

    /// Returns a known semantic parent for a given definition.
    pub(crate) fn known_semantic_parent(
        &self,
        definition: clang::Cursor,
    ) -> Option<ItemId> {
        self.semantic_parents.get(&definition).cloned()
    }

    /// Given a cursor pointing to the location of a template instantiation,
    /// return a tuple of the form `(declaration_cursor, declaration_id,
    /// num_expected_template_args)`.
    ///
    /// Note that `declaration_id` is not guaranteed to be in the context's item
    /// set! It is possible that it is a partial type that we are still in the
    /// middle of parsing.
    fn get_declaration_info_for_template_instantiation(
        &self,
        instantiation: &Cursor,
    ) -> Option<(Cursor, ItemId, usize)> {
        instantiation
            .cur_type()
            .canonical_declaration(Some(instantiation))
            .and_then(|canon_decl| {
                self.get_resolved_type(&canon_decl).and_then(
                    |template_decl_id| {
                        let num_params =
                            template_decl_id.num_self_template_params(self);
                        if num_params == 0 {
                            None
                        } else {
                            Some((
                                *canon_decl.cursor(),
                                template_decl_id.into(),
                                num_params,
                            ))
                        }
                    },
                )
            })
            .or_else(|| {
                // If we haven't already parsed the declaration of
                // the template being instantiated, then it *must*
                // be on the stack of types we are currently
                // parsing. If it wasn't then clang would have
                // already errored out before we started
                // constructing our IR because you can't instantiate
                // a template until it is fully defined.
                instantiation
                    .referenced()
                    .and_then(|referenced| {
                        self.currently_parsed_types()
                            .iter()
                            .find(|partial_ty| *partial_ty.decl() == referenced)
                            .cloned()
                    })
                    .and_then(|template_decl| {
                        let num_template_params =
                            template_decl.num_self_template_params(self);
                        if num_template_params == 0 {
                            None
                        } else {
                            Some((
                                *template_decl.decl(),
                                template_decl.id(),
                                num_template_params,
                            ))
                        }
                    })
            })
    }

    /// Parse a template instantiation, eg `Foo<int>`.
    ///
    /// This is surprisingly difficult to do with libclang, due to the fact that
    /// it doesn't provide explicit template argument information, except for
    /// function template declarations(!?!??!).
    ///
    /// The only way to do this is manually inspecting the AST and looking for
    /// TypeRefs and TemplateRefs inside. This, unfortunately, doesn't work for
    /// more complex cases, see the comment on the assertion below.
    ///
    /// To add insult to injury, the AST itself has structure that doesn't make
    /// sense. Sometimes `Foo<Bar<int>>` has an AST with nesting like you might
    /// expect: `(Foo (Bar (int)))`. Other times, the AST we get is completely
    /// flat: `(Foo Bar int)`.
    ///
    /// To see an example of what this method handles:
    ///
    /// ```c++
    /// template<typename T>
    /// class Incomplete {
    ///   T p;
    /// };
    ///
    /// template<typename U>
    /// class Foo {
    ///   Incomplete<U> bar;
    /// };
    /// ```
    ///
    /// Finally, template instantiations are always children of the current
    /// module. They use their template's definition for their name, so the
    /// parent is only useful for ensuring that their layout tests get
    /// codegen'd.
    fn instantiate_template(
        &mut self,
        with_id: ItemId,
        template: TypeId,
        ty: &clang::Type,
        location: clang::Cursor,
    ) -> Option<TypeId> {
        let num_expected_args =
            self.resolve_type(template).num_self_template_params(self);
        if num_expected_args == 0 {
            warn!(
                "Tried to instantiate a template for which we could not \
                 determine any template parameters"
            );
            return None;
        }

        let mut args = vec![];
        let mut found_const_arg = false;
        let mut children = location.collect_children();

        if children.iter().all(|c| !c.has_children()) {
            // This is insanity... If clang isn't giving us a properly nested
            // AST for which template arguments belong to which template we are
            // instantiating, we'll need to construct it ourselves. However,
            // there is an extra `NamespaceRef, NamespaceRef, ..., TemplateRef`
            // representing a reference to the outermost template declaration
            // that we need to filter out of the children. We need to do this
            // filtering because we already know which template declaration is
            // being specialized via the `location`'s type, and if we do not
            // filter it out, we'll add an extra layer of template instantiation
            // on accident.
            let idx = children
                .iter()
                .position(|c| c.kind() == clang_sys::CXCursor_TemplateRef);
            if let Some(idx) = idx {
                if children
                    .iter()
                    .take(idx)
                    .all(|c| c.kind() == clang_sys::CXCursor_NamespaceRef)
                {
                    children = children.into_iter().skip(idx + 1).collect();
                }
            }
        }

        for child in children.iter().rev() {
            match child.kind() {
                clang_sys::CXCursor_TypeRef |
                clang_sys::CXCursor_TypedefDecl |
                clang_sys::CXCursor_TypeAliasDecl => {
                    // The `with_id` ID will potentially end up unused if we give up
                    // on this type (for example, because it has const value
                    // template args), so if we pass `with_id` as the parent, it is
                    // potentially a dangling reference. Instead, use the canonical
                    // template declaration as the parent. It is already parsed and
                    // has a known-resolvable `ItemId`.
                    let ty = Item::from_ty_or_ref(
                        child.cur_type(),
                        *child,
                        Some(template.into()),
                        self,
                    );
                    args.push(ty);
                }
                clang_sys::CXCursor_TemplateRef => {
                    let (
                        template_decl_cursor,
                        template_decl_id,
                        num_expected_template_args,
                    ) = self.get_declaration_info_for_template_instantiation(
                        child,
                    )?;

                    if num_expected_template_args == 0 ||
                        child.has_at_least_num_children(
                            num_expected_template_args,
                        )
                    {
                        // Do a happy little parse. See comment in the TypeRef
                        // match arm about parent IDs.
                        let ty = Item::from_ty_or_ref(
                            child.cur_type(),
                            *child,
                            Some(template.into()),
                            self,
                        );
                        args.push(ty);
                    } else {
                        // This is the case mentioned in the doc comment where
                        // clang gives us a flattened AST and we have to
                        // reconstruct which template arguments go to which
                        // instantiation :(
                        let args_len = args.len();
                        if args_len < num_expected_template_args {
                            warn!(
                                "Found a template instantiation without \
                                 enough template arguments"
                            );
                            return None;
                        }

                        let mut sub_args: Vec<_> = args
                            .drain(args_len - num_expected_template_args..)
                            .collect();
                        sub_args.reverse();

                        let sub_name = Some(template_decl_cursor.spelling());
                        let sub_inst = TemplateInstantiation::new(
                            // This isn't guaranteed to be a type that we've
                            // already finished parsing yet.
                            template_decl_id.as_type_id_unchecked(),
                            sub_args,
                        );
                        let sub_kind =
                            TypeKind::TemplateInstantiation(sub_inst);
                        let sub_ty = Type::new(
                            sub_name,
                            template_decl_cursor
                                .cur_type()
                                .fallible_layout(self)
                                .ok(),
                            sub_kind,
                            false,
                        );
                        let sub_id = self.next_item_id();
                        let sub_item = Item::new(
                            sub_id,
                            None,
                            None,
                            self.current_module.into(),
                            ItemKind::Type(sub_ty),
                            Some(child.location()),
                        );

                        // Bypass all the validations in add_item explicitly.
                        debug!(
                            "instantiate_template: inserting nested \
                             instantiation item: {:?}",
                            sub_item
                        );
                        self.add_item_to_module(&sub_item);
                        debug_assert_eq!(sub_id, sub_item.id());
                        self.items[sub_id.0] = Some(sub_item);
                        args.push(sub_id.as_type_id_unchecked());
                    }
                }
                _ => {
                    warn!(
                        "Found template arg cursor we can't handle: {:?}",
                        child
                    );
                    found_const_arg = true;
                }
            }
        }

        if found_const_arg {
            // This is a dependently typed template instantiation. That is, an
            // instantiation of a template with one or more const values as
            // template arguments, rather than only types as template
            // arguments. For example, `Foo<true, 5>` versus `Bar<bool, int>`.
            // We can't handle these instantiations, so just punt in this
            // situation...
            warn!(
                "Found template instantiated with a const value; \
                 bindgen can't handle this kind of template instantiation!"
            );
            return None;
        }

        if args.len() != num_expected_args {
            warn!(
--> --------------------

--> maximum size reached

--> --------------------