path: root/libbindgen/src/ir/context.rs

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

use BindgenOptions;
use cexpr;
use chooser::TypeChooser;
use clang::{self, Cursor};
use parse::ClangItemParser;
use std::borrow::Cow;
use std::cell::Cell;
use std::collections::{HashMap, VecDeque, hash_map};
use std::collections::btree_map::{self, BTreeMap};
use std::fmt;
use super::derive::{CanDeriveCopy, CanDeriveDebug};
use super::int::IntKind;
use super::item::{Item, ItemCanonicalPath};
use super::item_kind::ItemKind;
use super::module::{Module, ModuleKind};
use super::ty::{FloatKind, Type, TypeKind};
use super::type_collector::{ItemSet, TypeCollector};
use syntax::ast::Ident;
use syntax::codemap::{DUMMY_SP, Span};
use syntax::ext::base::ExtCtxt;

/// A single identifier for an item.
///
/// TODO: Build stronger abstractions on top of this, like TypeId(ItemId)?
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ItemId(usize);

impl ItemId {
    /// Get a numeric representation of this id.
    pub fn as_usize(&self) -> usize {
        self.0
    }
}

impl CanDeriveDebug for ItemId {
    type Extra = ();

    fn can_derive_debug(&self, ctx: &BindgenContext, _: ()) -> bool {
        ctx.resolve_item(*self).can_derive_debug(ctx, ())
    }
}

impl<'a> CanDeriveCopy<'a> for ItemId {
    type Extra = ();

    fn can_derive_copy(&self, ctx: &BindgenContext, _: ()) -> bool {
        ctx.resolve_item(*self).can_derive_copy(ctx, ())
    }

    fn can_derive_copy_in_array(&self, ctx: &BindgenContext, _: ()) -> bool {
        ctx.resolve_item(*self).can_derive_copy_in_array(ctx, ())
    }
}

/// 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),
}

// This is just convenience to avoid creating a manual debug impl for the
// context.
struct GenContext<'ctx>(ExtCtxt<'ctx>);

impl<'ctx> fmt::Debug for GenContext<'ctx> {
    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
        write!(fmt, "GenContext {{ ... }}")
    }
}

/// A context used during parsing and generation of structs.
#[derive(Debug)]
pub struct BindgenContext<'ctx> {
    /// The map of all the items parsed so far.
    ///
    /// It's a BTreeMap because we want the keys to be sorted to have consistent
    /// output.
    items: BTreeMap<ItemId, Item>,

    /// The next item id to use during this bindings regeneration.
    next_item_id: ItemId,

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

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

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

    /// Current module being traversed.
    current_module: 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.
    ///
    /// FIXME: Should not be public, though... meh.
    pub currently_parsed_types: Vec<(Cursor, ItemId)>,

    /// A HashSet 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.
    parsed_macros: HashMap<Vec<u8>, cexpr::expr::EvalResult>,

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

    collected_typerefs: bool,

    /// Dummy structures for code generation.
    gen_ctx: Option<&'ctx GenContext<'ctx>>,
    span: Span,

    /// The clang index for parsing.
    index: clang::Index,

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

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

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

impl<'ctx> BindgenContext<'ctx> {
    /// Construct the context for the given `options`.
    pub fn new(options: BindgenOptions) -> Self {
        use clang_sys;

        let index = clang::Index::new(false, true);

        let parse_options =
            clang_sys::CXTranslationUnit_DetailedPreprocessingRecord;
        let translation_unit =
            clang::TranslationUnit::parse(&index,
                                          "",
                                          &options.clang_args,
                                          &[],
                                          parse_options)
                .expect("TranslationUnit::parse");

        let root_module = Self::build_root_module(ItemId(0));
        let mut me = BindgenContext {
            items: Default::default(),
            types: Default::default(),
            modules: Default::default(),
            next_item_id: ItemId(1),
            root_module: root_module.id(),
            current_module: root_module.id(),
            currently_parsed_types: vec![],
            parsed_macros: Default::default(),
            replacements: Default::default(),
            collected_typerefs: false,
            gen_ctx: None,
            span: DUMMY_SP,
            index: index,
            translation_unit: translation_unit,
            options: options,
            generated_bindegen_complex: Cell::new(false),
        };

        me.add_item(root_module, None, None);

        me
    }

    /// Get the user-provided type chooser by reference, if any.
    pub fn type_chooser(&self) -> Option<&TypeChooser> {
        self.options().type_chooser.as_ref().map(|t| &**t)
    }

    /// Define a new item.
    ///
    /// This inserts it into the internal items set, and its type into the
    /// internal types set.
    pub 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_named(),
                      "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();

        // Be sure to track all the generated children under namespace, even
        // those generated after resolving typerefs, etc.
        if item.id() != item.parent_id() {
            if let Some(mut parent) = self.items.get_mut(&item.parent_id()) {
                if let Some(mut module) = parent.as_module_mut() {
                    module.children_mut().push(item.id());
                }
            }
        }

        let old_item = self.items.insert(id, item);
        assert!(old_item.is_none(), "Inserted type twice?");

        // 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 && declaration.is_some() {
            let mut declaration = declaration.unwrap();
            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.items.get(&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);
            debug_assert_eq!(old, None);
        }
    }

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

    /// Given that we are in the codegen phase, get the syntex context.
    pub fn ext_cx(&self) -> &ExtCtxt<'ctx> {
        &self.gen_ctx.expect("Not in gen phase").0
    }

    /// Given that we are in the codegen phase, get the current syntex span.
    pub fn span(&self) -> Span {
        self.span
    }

    /// Mangles a name so it doesn't conflict with any keyword.
    pub fn rust_mangle<'a>(&self, name: &'a str) -> Cow<'a, str> {
        use syntax::parse::token;
        let ident = self.rust_ident_raw(name);
        let token = token::Ident(ident);
        if token.is_any_keyword() || name.contains("@") ||
           name.contains("?") || name.contains("$") ||
           "bool" == name {
            let mut s = name.to_owned();
            s = s.replace("@", "_");
            s = s.replace("?", "_");
            s = s.replace("$", "_");
            s.push_str("_");
            return Cow::Owned(s);
        }
        Cow::Borrowed(name)
    }

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

    /// Returns a mangled name as a rust identifier.
    pub fn rust_ident_raw(&self, name: &str) -> Ident {
        self.ext_cx().ident_of(name)
    }

    /// Iterate over all items that have been defined.
    pub fn items<'a>(&'a self) -> btree_map::Iter<'a, ItemId, Item> {
        self.items.iter()
    }

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

    /// Gather all the unresolved type references.
    fn collect_typerefs
        (&mut self)
         -> Vec<(ItemId, clang::Type, Option<clang::Cursor>, Option<ItemId>)> {
        debug_assert!(!self.collected_typerefs);
        self.collected_typerefs = true;
        let mut typerefs = vec![];
        for (id, ref mut item) in &mut self.items {
            let kind = item.kind();
            let ty = match kind.as_type() {
                Some(ty) => ty,
                None => continue,
            };

            match *ty.kind() {
                TypeKind::UnresolvedTypeRef(ref ty, loc, parent_id) => {
                    typerefs.push((*id, ty.clone(), loc, parent_id));
                }
                _ => {}
            };
        }
        typerefs
    }

    /// Collect all of our unresolved type references and resolve them.
    fn resolve_typerefs(&mut self) {
        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)
                    .expect("What happened?");
                let mut item = self.items.get_mut(&id).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?");
        }
    }

    /// 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) {
        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.iter() {
            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(ref ci) if !ci.is_template_specialization() => {}
                TypeKind::TemplateAlias(..) |
                TypeKind::Alias(..) => {}
                _ => continue,
            }

            let path = item.canonical_path(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.items.get(replacement).is_some() {
                        replacements.push((*id, *replacement));
                    }
                }
            }
        }

        for (id, replacement) in replacements {
            debug!("Replacing {:?} with {:?}", id, replacement);

            let new_parent = {
                let mut item = self.items.get_mut(&id).unwrap();
                *item.kind_mut().as_type_mut().unwrap().kind_mut() =
                    TypeKind::ResolvedTypeRef(replacement);
                item.parent_id()
            };


            // Reparent the item.
            let old_parent = self.resolve_item(replacement).parent_id();

            if new_parent == old_parent {
                continue;
            }

            if let Some(mut module) = self.items
                .get_mut(&old_parent)
                .unwrap()
                .as_module_mut() {
                // Deparent the replacement.
                let position = module.children()
                    .iter()
                    .position(|id| *id == replacement)
                    .unwrap();
                module.children_mut().remove(position);
            }

            if let Some(mut module) = self.items
                .get_mut(&new_parent)
                .unwrap()
                .as_module_mut() {
                module.children_mut().push(replacement);
            }

            self.items
                .get_mut(&replacement)
                .unwrap()
                .set_parent_for_replacement(new_parent);
            self.items
                .get_mut(&id)
                .unwrap()
                .set_parent_for_replacement(old_parent);
        }
    }

    /// Enter the code generation phase, invoke the given callback `cb`, and
    /// leave the code generation phase.
    pub fn gen<F, Out>(&mut self, cb: F) -> Out
        where F: FnOnce(&Self) -> Out,
    {
        use syntax::ext::expand::ExpansionConfig;
        use syntax::codemap::{ExpnInfo, MacroBang, NameAndSpan};
        use syntax::ext::base;
        use syntax::parse;
        use std::mem;

        let cfg = ExpansionConfig::default("xxx".to_owned());
        let sess = parse::ParseSess::new();
        let mut loader = base::DummyResolver;
        let mut ctx = GenContext(base::ExtCtxt::new(&sess, cfg, &mut loader));

        ctx.0.bt_push(ExpnInfo {
            call_site: self.span,
            callee: NameAndSpan {
                format: MacroBang(parse::token::intern("")),
                allow_internal_unstable: false,
                span: None,
            },
        });

        // FIXME: This is evil, we should move code generation to use a wrapper
        // of BindgenContext instead, I guess. Even though we know it's fine
        // because we remove it before the end of this function.
        self.gen_ctx = Some(unsafe { mem::transmute(&ctx) });

        self.assert_no_dangling_references();

        if !self.collected_typerefs() {
            self.resolve_typerefs();
            self.process_replacements();
        }

        let ret = cb(self);
        self.gen_ctx = None;
        ret
    }

    /// This function trying to find any dangling references inside of `items`
    fn assert_no_dangling_references(&self) {
        if cfg!(feature = "assert_no_dangling_items") {
            for _ in self.assert_no_dangling_item_traversal() {
                // The iterator's next method does the asserting for us.
            }
        }
    }

    fn assert_no_dangling_item_traversal<'me>
        (&'me self)
         -> AssertNoDanglingItemIter<'me, 'ctx> {
        assert!(self.in_codegen_phase());
        assert!(self.current_module == self.root_module);

        let mut roots = self.items().map(|(&id, _)| id);

        let mut seen = BTreeMap::<ItemId, ItemId>::new();
        let next_child = roots.next().map(|id| id).unwrap();
        seen.insert(next_child, next_child);

        let to_iterate = seen.iter().map(|(&id, _)| id).rev().collect();

        AssertNoDanglingItemIter {
            ctx: self,
            seen: seen,
            to_iterate: to_iterate,
        }
    }

    // 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());
        let id = item.id();
        let old_item = self.items.insert(id, 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))
    }

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

    /// Resolve the given `ItemId` as a type.
    ///
    /// Panics if there is no item for the given `ItemId` or if the resolved
    /// item is not a `Type`.
    pub fn resolve_type(&self, type_id: ItemId) -> &Type {
        self.items.get(&type_id).unwrap().kind().expect_type()
    }

    /// 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 fn safe_resolve_type(&self, type_id: ItemId) -> Option<&Type> {
        self.items.get(&type_id).map(|t| t.kind().expect_type())
    }

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

    /// Resolve the given `ItemId` into an `Item`.
    ///
    /// Panics if the given id does not resolve to any item.
    pub fn resolve_item(&self, item_id: ItemId) -> &Item {
        match self.items.get(&item_id) {
            Some(item) => item,
            None => panic!("Not an item: {:?}", item_id),
        }
    }

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

    /// This is one of the hackiest methods in all the parsing code. This method
    /// is used to allow having templates with another argument names instead of
    /// the canonical ones.
    ///
    /// This is surprisingly difficult to do with libclang, due to the fact that
    /// partial template specializations don't provide explicit template
    /// argument information.
    ///
    /// The only way to do this as far as I know, is inspecting manually the
    /// AST, looking for TypeRefs inside. This, unfortunately, doesn't work for
    /// more complex cases, see the comment on the assertion below.
    ///
    /// To see an example of what this handles:
    ///
    /// ```c++
    ///     template<typename T>
    ///     class Incomplete {
    ///       T p;
    ///     };
    ///
    ///     template<typename U>
    ///     class Foo {
    ///       Incomplete<U> bar;
    ///     };
    /// ```
    fn build_template_wrapper(&mut self,
                              with_id: ItemId,
                              wrapping: ItemId,
                              parent_id: ItemId,
                              ty: &clang::Type,
                              location: clang::Cursor,
                              declaration: clang::Cursor)
                              -> ItemId {
        use clang_sys::*;
        let mut args = vec![];
        location.visit(|c| {
            if c.kind() == CXCursor_TypeRef {
                // The `with_id` id will potentially end up unused if we give up
                // on this type (for example, its a tricky partial template
                // specialization), 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 new_ty = Item::from_ty_or_ref(c.cur_type(),
                                                  Some(c),
                                                  Some(wrapping),
                                                  self);
                args.push(new_ty);
            }
            CXChildVisit_Continue
        });

        let item = {
            let wrapping_type = self.resolve_type(wrapping);
            if let TypeKind::Comp(ref ci) = *wrapping_type.kind() {
                let old_args = ci.template_args();

                // The following assertion actually fails with partial template
                // specialization. But as far as I know there's no way at all to
                // grab the specialized types from neither the AST or libclang,
                // which sucks. The same happens for specialized type alias
                // template declarations, where we have that ugly hack up there.
                //
                // This flaw was already on the old parser, but I now think it
                // has no clear solution (apart from patching libclang to
                // somehow expose them, of course).
                //
                // For an easy example in which there's no way at all of getting
                // the `int` type, except manually parsing the spelling:
                //
                //     template<typename T, typename U>
                //     class Incomplete {
                //       T d;
                //       U p;
                //     };
                //
                //     template<typename U>
                //     class Foo {
                //       Incomplete<U, int> bar;
                //     };
                //
                // debug_assert_eq!(old_args.len(), args.len());
                //
                // That being said, this is not so common, so just error! and
                // hope for the best, returning the previous type, who knows.
                if old_args.len() != args.len() {
                    error!("Found partial template specialization, \
                            expect dragons!");
                    return wrapping;
                }
            } else {
                assert_eq!(declaration.kind(),
                           ::clang_sys::CXCursor_TypeAliasTemplateDecl,
                           "Expected wrappable type");
            }

            let type_kind = TypeKind::TemplateRef(wrapping, args);
            let name = ty.spelling();
            let name = if name.is_empty() { None } else { Some(name) };
            let ty = Type::new(name,
                               ty.fallible_layout().ok(),
                               type_kind,
                               ty.is_const());
            Item::new(with_id, None, None, parent_id, ItemKind::Type(ty))
        };

        // Bypass all the validations in add_item explicitly.
        debug!("build_template_wrapper: inserting item: {:?}", item);
        debug_assert!(with_id == item.id());
        self.items.insert(with_id, item);
        with_id
    }

    /// Looks up for an already resolved type, either because it's builtin, or
    /// because we already have it in the map.
    pub fn builtin_or_resolved_ty(&mut self,
                                  with_id: ItemId,
                                  parent_id: Option<ItemId>,
                                  ty: &clang::Type,
                                  location: Option<clang::Cursor>)
                                  -> Option<ItemId> {
        use clang_sys::{CXCursor_TypeAliasTemplateDecl, CXCursor_TypeRef};
        debug!("builtin_or_resolved_ty: {:?}, {:?}, {:?}",
               ty,
               location,
               parent_id);
        let mut declaration = ty.declaration();
        if !declaration.is_valid() {
            if let Some(location) = location {
                if location.is_template_like() {
                    declaration = location;
                }
            }
        }
        let canonical_declaration = declaration.canonical();
        if canonical_declaration.is_valid() {
            let id = self.types
                .get(&TypeKey::Declaration(canonical_declaration))
                .map(|id| *id)
                .or_else(|| {
                    canonical_declaration.usr()
                        .and_then(|usr| self.types.get(&TypeKey::USR(usr)))
                        .map(|id| *id)
                });
            if let Some(id) = id {
                debug!("Already resolved ty {:?}, {:?}, {:?} {:?}",
                       id,
                       declaration,
                       ty,
                       location);

                // If the declaration existed, we *might* be done, but it's not
                // the case for class templates, where the template arguments
                // may vary.
                //
                // In this case, we create a TemplateRef with the new template
                // arguments, pointing to the canonical template.
                //
                // Note that we only do it if parent_id is some, and we have a
                // location for building the new arguments, the template
                // argument names don't matter in the global context.
                if declaration.is_template_like() &&
                   *ty != canonical_declaration.cur_type() &&
                   location.is_some() &&
                   parent_id.is_some() {
                    // For specialized type aliases, there's no way to get the
                    // template parameters as of this writing (for a struct
                    // specialization we wouldn't be in this branch anyway).
                    //
                    // Explicitly return `None` if there aren't any
                    // unspecialized parameters (contains any `TypeRef`) so we
                    // resolve the canonical type if there is one and it's
                    // exposed.
                    //
                    // This is _tricky_, I know :(
                    if declaration.kind() == CXCursor_TypeAliasTemplateDecl &&
                       !location.unwrap().contains_cursor(CXCursor_TypeRef) &&
                       ty.canonical_type().is_valid_and_exposed() {
                        return None;
                    }

                    return Some(self.build_template_wrapper(with_id,
                                                id,
                                                parent_id.unwrap(),
                                                ty,
                                                location.unwrap(),
                                                declaration));
                }

                return Some(self.build_ty_wrapper(with_id, id, parent_id, ty));
            }
        }

        debug!("Not resolved, maybe builtin?");

        // Else, build it.
        self.build_builtin_ty(ty, declaration)
    }

    // This is unfortunately a lot of bloat, but is needed to properly track
    // constness et. al.
    //
    // We should probably make the constness tracking separate, so it doesn't
    // bloat that much, but hey, we already bloat the heck out of builtin types.
    fn build_ty_wrapper(&mut self,
                        with_id: ItemId,
                        wrapped_id: ItemId,
                        parent_id: Option<ItemId>,
                        ty: &clang::Type)
                        -> ItemId {
        let spelling = ty.spelling();
        let is_const = ty.is_const();
        let layout = ty.fallible_layout().ok();
        let type_kind = TypeKind::ResolvedTypeRef(wrapped_id);
        let ty = Type::new(Some(spelling), layout, type_kind, is_const);
        let item = Item::new(with_id,
                             None,
                             None,
                             parent_id.unwrap_or(self.current_module),
                             ItemKind::Type(ty));
        self.add_builtin_item(item);
        with_id
    }

    /// Returns the next item id to be used for an item.
    pub fn next_item_id(&mut self) -> ItemId {
        let ret = self.next_item_id;
        self.next_item_id = ItemId(self.next_item_id.0 + 1);
        ret
    }

    fn build_builtin_ty(&mut self,
                        ty: &clang::Type,
                        _declaration: Cursor)
                        -> Option<ItemId> {
        use clang_sys::*;
        let type_kind = match ty.kind() {
            CXType_NullPtr => TypeKind::NullPtr,
            CXType_Void => TypeKind::Void,
            CXType_Bool => TypeKind::Int(IntKind::Bool),
            CXType_Int => TypeKind::Int(IntKind::Int),
            CXType_UInt => TypeKind::Int(IntKind::UInt),
            CXType_SChar | CXType_Char_S => TypeKind::Int(IntKind::Char),
            CXType_UChar | CXType_Char_U => TypeKind::Int(IntKind::UChar),
            CXType_Short => TypeKind::Int(IntKind::Short),
            CXType_UShort => TypeKind::Int(IntKind::UShort),
            CXType_WChar | CXType_Char16 => TypeKind::Int(IntKind::U16),
            CXType_Char32 => TypeKind::Int(IntKind::U32),
            CXType_Long => TypeKind::Int(IntKind::Long),
            CXType_ULong => TypeKind::Int(IntKind::ULong),
            CXType_LongLong => TypeKind::Int(IntKind::LongLong),
            CXType_ULongLong => TypeKind::Int(IntKind::ULongLong),
            CXType_Int128 => TypeKind::Int(IntKind::I128),
            CXType_UInt128 => TypeKind::Int(IntKind::U128),
            CXType_Float => TypeKind::Float(FloatKind::Float),
            CXType_Double => TypeKind::Float(FloatKind::Double),
            CXType_LongDouble => TypeKind::Float(FloatKind::LongDouble),
            CXType_Float128 => TypeKind::Float(FloatKind::Float128),
            CXType_Complex => {
                let float_type = ty.elem_type()
                    .expect("Not able to resolve complex type?");
                let float_kind = match float_type.kind() {
                    CXType_Float => FloatKind::Float,
                    CXType_Double => FloatKind::Double,
                    CXType_LongDouble => FloatKind::LongDouble,
                    _ => panic!("Non floating-type complex?"),
                };
                TypeKind::Complex(float_kind)
            }
            _ => return None,
        };

        let spelling = ty.spelling();
        let is_const = ty.is_const();
        let layout = ty.fallible_layout().ok();
        let ty = Type::new(Some(spelling), layout, type_kind, is_const);
        let id = self.next_item_id();
        let item =
            Item::new(id, None, None, self.root_module, ItemKind::Type(ty));
        self.add_builtin_item(item);
        Some(id)
    }

    /// Get the current Clang translation unit that is being processed.
    pub fn translation_unit(&self) -> &clang::TranslationUnit {
        &self.translation_unit
    }

    /// Have we parsed the macro named `macro_name` already?
    pub fn parsed_macro(&self, macro_name: &[u8]) -> bool {
        self.parsed_macros.contains_key(macro_name)
    }

    /// Get the currently parsed macros.
    pub fn parsed_macros(&self) -> &HashMap<Vec<u8>, cexpr::expr::EvalResult> {
        debug_assert!(!self.in_codegen_phase());
        &self.parsed_macros
    }

    /// Mark the macro named `macro_name` as parsed.
    pub fn note_parsed_macro(&mut self,
                             id: Vec<u8>,
                             value: cexpr::expr::EvalResult) {
        self.parsed_macros.insert(id, value);
    }

    /// Are we in the codegen phase?
    pub fn in_codegen_phase(&self) -> bool {
        self.gen_ctx.is_some()
    }

    /// Mark the type with the given `name` as replaced by the type with id
    /// `potential_ty`.
    ///
    /// Replacement types are declared using the `replaces="xxx"` annotation,
    /// and implies that the original type is hidden.
    pub fn replace(&mut self, name: &[String], potential_ty: ItemId) {
        match self.replacements.entry(name.into()) {
            hash_map::Entry::Vacant(entry) => {
                debug!("Defining replacement for {:?} as {:?}",
                       name,
                       potential_ty);
                entry.insert(potential_ty);
            }
            hash_map::Entry::Occupied(occupied) => {
                warn!("Replacement for {:?} already defined as {:?}; \
                       ignoring duplicate replacement definition as {:?}",
                      name,
                      occupied.get(),
                      potential_ty);
            }
        }
    }

    /// Is the item with the given `name` hidden? Or is the item with the given
    /// `name` and `id` replaced by another type, and effectively hidden?
    pub fn hidden_by_name(&self, path: &[String], id: ItemId) -> bool {
        debug_assert!(self.in_codegen_phase(),
                      "You're not supposed to call this yet");
        self.options.hidden_types.matches(&path[1..].join("::")) ||
        self.is_replaced_type(path, id)
    }

    /// Has the item with the given `name` and `id` been replaced by another
    /// type?
    pub fn is_replaced_type(&self, path: &[String], id: ItemId) -> bool {
        match self.replacements.get(path) {
            Some(replaced_by) if *replaced_by != id => true,
            _ => false,
        }
    }

    /// Is the type with the given `name` marked as opaque?
    pub fn opaque_by_name(&self, path: &[String]) -> bool {
        debug_assert!(self.in_codegen_phase(),
                      "You're not supposed to call this yet");
        self.options.opaque_types.matches(&path[1..].join("::"))
    }

    /// Get the options used to configure this bindgen context.
    pub fn options(&self) -> &BindgenOptions {
        &self.options
    }

    /// Tokenizes a namespace cursor in order to get the name and kind of the
    /// namespace,
    fn tokenize_namespace(&self,
                          cursor: &clang::Cursor)
                          -> (Option<String>, ModuleKind) {
        assert_eq!(cursor.kind(), ::clang_sys::CXCursor_Namespace,
                   "Be a nice person");
        let tokens = match self.translation_unit.tokens(&cursor) {
            Some(tokens) => tokens,
            None => return (None, ModuleKind::Normal),
        };

        let mut iter = tokens.iter();
        let mut kind = ModuleKind::Normal;
        let mut found_namespace_keyword = false;
        let mut module_name = None;
        while let Some(token) = iter.next() {
            match &*token.spelling {
                "inline" => {
                    assert!(!found_namespace_keyword);
                    assert!(kind != ModuleKind::Inline);
                    kind = ModuleKind::Inline;
                }
                "namespace" => {
                    found_namespace_keyword = true;
                }
                "{" => {
                    assert!(found_namespace_keyword);
                    break;
                }
                name if found_namespace_keyword => {
                    module_name = Some(name.to_owned());
                    break;
                }
                _ => {
                    panic!("Unknown token while processing namespace: {:?}",
                           token);
                }
            }
        };

        (module_name, kind)
    }

    /// Given a CXCursor_Namespace cursor, return the item id of the
    /// corresponding module, or create one on the fly.
    pub fn module(&mut self, cursor: clang::Cursor) -> ItemId {
        use clang_sys::*;
        assert_eq!(cursor.kind(), CXCursor_Namespace, "Be a nice person");
        let cursor = cursor.canonical();
        if let Some(id) = self.modules.get(&cursor) {
            return *id;
        }

        let (module_name, kind) = self.tokenize_namespace(&cursor);

        let module_id = self.next_item_id();
        let module = Module::new(module_name, kind);
        let module = Item::new(module_id,
                               None,
                               None,
                               self.current_module,
                               ItemKind::Module(module));

        self.modules.insert(cursor, module.id());

        self.add_item(module, None, None);

        module_id
    }

    /// Start traversing the module with the given `module_id`, invoke the
    /// callback `cb`, and then return to traversing the original module.
    pub fn with_module<F>(&mut self, module_id: ItemId, cb: F)
        where F: FnOnce(&mut Self),
    {
        debug_assert!(self.resolve_item(module_id).kind().is_module(), "Wat");

        let previous_id = self.current_module;
        self.current_module = module_id;

        cb(self);

        self.current_module = previous_id;
    }

    /// Iterate over all (explicitly or transitively) whitelisted items.
    ///
    /// If no items are explicitly whitelisted, then all items are considered
    /// whitelisted.
    pub fn whitelisted_items<'me>(&'me self)
                                  -> WhitelistedItemsIter<'me, 'ctx> {
        assert!(self.in_codegen_phase());
        assert!(self.current_module == self.root_module);

        let roots = self.items()
            .filter(|&(_, item)| {
                // If nothing is explicitly whitelisted, then everything is fair
                // game.
                if self.options().whitelisted_types.is_empty() &&
                   self.options().whitelisted_functions.is_empty() &&
                   self.options().whitelisted_vars.is_empty() {
                    return true;
                }

                // If this is a type that explicitly replaces another, we assume
                // you know what you're doing.
                if item.annotations().use_instead_of().is_some() {
                    return true;
                }

                let name = item.canonical_path(self)[1..].join("::");
                debug!("whitelisted_items: testing {:?}", name);
                match *item.kind() {
                    ItemKind::Module(..) => true,
                    ItemKind::Function(_) => {
                        self.options().whitelisted_functions.matches(&name)
                    }
                    ItemKind::Var(_) => {
                        self.options().whitelisted_vars.matches(&name)
                    }
                    ItemKind::Type(ref ty) => {
                        if self.options().whitelisted_types.matches(&name) {
                            return true;
                        }

                        let parent = self.resolve_item(item.parent_id());
                        if parent.is_module() {
                            let mut prefix_path = parent.canonical_path(self);

                            // Unnamed top-level enums are special and we
                            // whitelist them via the `whitelisted_vars` filter,
                            // since they're effectively top-level constants,
                            // and there's no way for them to be referenced
                            // consistently.
                            if let TypeKind::Enum(ref enum_) = *ty.kind() {
                                if ty.name().is_none() &&
                                   enum_.variants().iter().any(|variant| {
                                    prefix_path.push(variant.name().into());
                                    let name = prefix_path[1..].join("::");
                                    prefix_path.pop().unwrap();
                                    self.options()
                                        .whitelisted_vars
                                        .matches(&name)
                                }) {
                                    return true;
                                }
                            }
                        }

                        false
                    }
                }
            })
            .map(|(&id, _)| id);

        let seen: ItemSet = roots.collect();

        // The .rev() preserves the expected ordering traversal, resulting in
        // more stable-ish bindgen-generated names for anonymous types (like
        // unions).
        let to_iterate = seen.iter().cloned().rev().collect();

        WhitelistedItemsIter {
            ctx: self,
            seen: seen,
            to_iterate: to_iterate,
        }
    }

    /// Convenient method for getting the prefix to use for most traits in
    /// codegen depending on the `use_core` option.
    pub fn trait_prefix(&self) -> Ident {
        if self.options().use_core {
            self.rust_ident_raw("core")
        } else {
            self.rust_ident_raw("std")
        }
    }

    /// Call if a binden complex is generated
    pub fn generated_bindegen_complex(&self) {
        self.generated_bindegen_complex.set(true)
    }

    /// Whether we need to generate the binden complex type
    pub fn need_bindegen_complex_type(&self) -> bool {
        self.generated_bindegen_complex.get()
    }
}

/// An iterator over whitelisted items.
///
/// See `BindgenContext::whitelisted_items` for more information.
pub struct WhitelistedItemsIter<'ctx, 'gen>
    where 'gen: 'ctx,
{
    ctx: &'ctx BindgenContext<'gen>,

    // The set of whitelisted items we have seen. If you think of traversing
    // whitelisted items like GC tracing, this is the mark bits, and contains
    // both black and gray items.
    seen: ItemSet,

    // The set of whitelisted items that we have seen but have yet to iterate
    // over and collect transitive references from. To return to the GC analogy,
    // this is the mark stack, containing the set of gray items which we have
    // not finished tracing yet.
    to_iterate: Vec<ItemId>,
}

impl<'ctx, 'gen> Iterator for WhitelistedItemsIter<'ctx, 'gen>
    where 'gen: 'ctx,
{
    type Item = ItemId;

    fn next(&mut self) -> Option<Self::Item> {
        let id = match self.to_iterate.pop() {
            None => return None,
            Some(id) => id,
        };

        debug_assert!(self.seen.contains(&id));
        debug_assert!(self.ctx.items.contains_key(&id));

        let mut sub_types = ItemSet::new();
        id.collect_types(self.ctx, &mut sub_types, &());

        for id in sub_types {
            if self.seen.insert(id) {
                self.to_iterate.push(id);
            }
        }

        Some(id)
    }
}

/// An iterator to find any dangling items.
///
/// See `BindgenContext::assert_no_dangling_item_traversal` for more
/// information.
pub struct AssertNoDanglingItemIter<'ctx, 'gen>
    where 'gen: 'ctx,
{
    ctx: &'ctx BindgenContext<'gen>,
    seen: BTreeMap<ItemId, ItemId>,
    to_iterate: VecDeque<ItemId>,
}

impl<'ctx, 'gen> Iterator for AssertNoDanglingItemIter<'ctx, 'gen>
    where 'gen: 'ctx,
{
    type Item = ItemId;

    fn next(&mut self) -> Option<Self::Item> {
        let id = match self.to_iterate.pop_front() {
            None => {
                // We've traversed everything reachable from the previous
                // root(s), see if we have any more roots.
                match self.ctx
                    .items()
                    .filter(|&(id, _)| !self.seen.contains_key(id))
                    .next()
                    .map(|(id, _)| *id) {
                    None => return None,
                    Some(id) => {
                        // This is a new root.
                        self.seen.insert(id, id);
                        id
                    }
                }
            }
            Some(id) => id,
        };

        let mut sub_types = ItemSet::new();
        id.collect_types(self.ctx, &mut sub_types, &());

        if self.ctx.resolve_item_fallible(id).is_none() {
            let mut path = vec![];
            let mut current = id;
            loop {
                let predecessor = *self.seen
                    .get(&current)
                    .expect("We know we found this item id, so it must have a \
                            predecessor");
                if predecessor == current {
                    break;
                }
                path.push(predecessor);
                current = predecessor;
            }
            path.reverse();
            panic!("Found reference to dangling id = {:?}\nvia path = {:?}",
                   id,
                   path);
        }

        for sub_id in sub_types {
            if self.seen.insert(sub_id, id).is_none() {
                // We've never visited this sub item before.
                self.to_iterate.push_back(sub_id);
            }
        }

        Some(id)
    }
}