Completely rework templates

* Find each item's used template parameters when we begin the codegen phase

* Add TemplateDeclaration::used_template_params()

  This method is available during the codegen phase, and uses the information
  gleaned by the `ir::named::UsedTemplateParameters` analysis.

* Remove Item::{applicable_template_args,signature_contains_named_type}

  They are replaced by the template parameter usage analysis and
  TemplateDeclaration::used_template_params.

* Parse and de-duplicate named template type parameters

* Do not attempt to determine template parameter usage when not recursively whitelisting

* Add a proper TemplateInstantiation type

  This makes it so that CompInfo is always either a compound type definition, or a
  template compound type definition, never an instantiation of a template. It also
  pulls out TypeKind::TemplateInstantiation(<inline stuff>) to a proper
  ir::TemplateInstantiation type, and TypeKind::TemplateInstantiation just wraps
  ir::TemplateInstantiation into TypeKind.

* Allow template definitions to lack template parameters because of opaque template definitions

* Detect and ignore cycles deriving Copy/Debug and whether a type has a vtable

* Bail out early in the face of partial template specialization

  We don't support it, and shouldn't continue trying to parse a type from this
  cursor.

* Do not consider inner type's parameter usage as our own parameter usage

* Do not require a parent_id for template instantiations

  It is not necessary, and in fact was preventing us from creating template
  instantiations in some places, resulting in such nonsense as a generic template
  definition as a base for another type.

* Only join if this is NOT a named template type or a template instantiation

  Otherwise, we'll always consider all of a template instantiation's arguments as
  used, when they should only be considered used if the template definition uses
  that template parameter.

* Consider function return and parameter types as used

  Although we should not follow class method edges because we cannot create new
  monomorphizations of methods, code can create aliases of function pointers whose
  return or parameter types are template parameters, and those template parameters
  should be considered used.

* Add the AsNamed trait for things which might be a named template type

  This sees through ResolvedTypeReferences to get at the final named type and its
  canonical item id. By using this in the named template parameter usage analysis,
  we ensure we don't have bugs where there are ResolvedTypeReferences in the usage
  sets rather than the canonical named item id, which could cause template
  parameters to be ignored accidentally.

* Do not consider an inner var's template parameter usage as our own

* Make the expectations' tests less noisy

* Use opaque blobs for unknown template definition types

  When we don't know how to generate a Rust type from a template definition (eg
  because it uses non-type template parameters), then we should fall back to using
  the instantiation's layout to generate the opaque blob.

* Implement CanDeriveDebug for TemplateInstantiation

  We need the template instantiation's layout to determine if we can derive debug
  for it when the instantiation's template definition has non-type parameters.

* Stop thrashing malloc when unioning ItemSets in UsedTemplateParameters

  Previously, we were cloning an ItemSet, which requires a malloc for non-empty
  sets, when taking its union with our current id's set. Now, instead of doing
  that, we wrap each ItemSet in an Option, and take the set out of the hash map
  when modifying it. This allows us to side-step the borrow checker and HashMap's
  lack of an analog to `slice::split_at_mut` and mutate what is logically a value
  in the hash map while also using immutable references of values that are
  physically in the hash map.

* Add some tests explicitly about template parameter usage

* Updated test expectations now that we are inferring template parameter usage

* Reinstate the layout tests for template instantiations

* Generate opaque blobs for uses of partially specialized templates

  This adds `TypeKind::Opaque` which signifies that we do not understand anything
  about the given type and that we should just generate an opaque blob based on
  the type's layout. It explicitly uses the opaque type kind for partially
  specialized templates.

* Add note about None vs Some([]) in TemplateDeclaration

* Do not rely on TypeKind implementing PartialEq

* Prefer assert_eq!(lhs, rhs) to assert!(lhs == rhs)

* Expand some comments for ir::named::UsedTemplateParameters

* Expand Item::is_opaque to consider TypeKind::Opaque

* Use opaque types instead of panicking

  Use opaque types as our last resort when resolving type references after we have
  collected unresolved type references instead of panicking.

* Find template definitions that don't want to be found

* Recognize associated template types and make them opaque

1 files changed, 153 insertions, 127 deletions

diff --git a/src/codegen/mod.rs b/src/codegen/mod.rs
index 77941fa3..7bc8985b 100644
--- a/src/codegen/mod.rs
+++ b/src/codegen/mod.rs
@@ -2,8 +2,8 @@ mod helpers;
 mod struct_layout;
 
 use self::helpers::{BlobTyBuilder, attributes};
+use self::struct_layout::{StructLayoutTracker, bytes_from_bits_pow2};
 use self::struct_layout::{align_to, bytes_from_bits};
-use self::struct_layout::{bytes_from_bits_pow2, StructLayoutTracker};
 use aster;
 
 use ir::annotations::FieldAccessorKind;
@@ -20,7 +20,8 @@ use ir::item_kind::ItemKind;
 use ir::layout::Layout;
 use ir::module::Module;
 use ir::objc::ObjCInterface;
-use ir::ty::{Type, TypeKind};
+use ir::template::{AsNamed, TemplateInstantiation};
+use ir::ty::{TemplateDeclaration, Type, TypeKind};
 use ir::var::Var;
 
 use std::borrow::Cow;
@@ -137,11 +138,6 @@ impl<'a> CodegenResult<'a> {
         }
     }
 
-    fn next_id(&mut self) -> usize {
-        self.codegen_id.set(self.codegen_id.get() + 1);
-        self.codegen_id.get()
-    }
-
     fn saw_union(&mut self) {
         self.saw_union = true;
     }
@@ -522,19 +518,20 @@ impl CodeGenerator for Type {
             TypeKind::Pointer(..) |
             TypeKind::BlockPointer |
             TypeKind::Reference(..) |
-            TypeKind::TemplateInstantiation(..) |
             TypeKind::Function(..) |
             TypeKind::ResolvedTypeRef(..) |
+            TypeKind::Opaque |
             TypeKind::Named => {
                 // These items don't need code generation, they only need to be
                 // converted to rust types in fields, arguments, and such.
                 return;
             }
+            TypeKind::TemplateInstantiation(ref inst) => {
+                inst.codegen(ctx, result, whitelisted_items, item)
+            }
             TypeKind::Comp(ref ci) => {
                 ci.codegen(ctx, result, whitelisted_items, item)
             }
-            // NB: The code below will pick the correct
-            // applicable_template_args.
             TypeKind::TemplateAlias(inner, _) |
             TypeKind::Alias(inner) => {
                 let inner_item = ctx.resolve_item(inner);
@@ -557,10 +554,9 @@ impl CodeGenerator for Type {
                     return;
                 }
 
-                let mut applicable_template_args =
-                    item.applicable_template_args(ctx);
+                let mut used_template_params = item.used_template_params(ctx);
                 let inner_rust_type = if item.is_opaque(ctx) {
-                    applicable_template_args.clear();
+                    used_template_params = None;
                     // Pray if there's no layout.
                     let layout = self.layout(ctx).unwrap_or_else(Layout::zero);
                     BlobTyBuilder::new(layout).build()
@@ -603,7 +599,7 @@ impl CodeGenerator for Type {
                 // https://github.com/rust-lang/rust/issues/26264
                 let simple_enum_path = match inner_rust_type.node {
                     ast::TyKind::Path(None, ref p) => {
-                        if applicable_template_args.is_empty() &&
+                        if used_template_params.is_none() &&
                            inner_item.expect_type()
                             .canonical_type(ctx)
                             .is_enum() &&
@@ -627,17 +623,21 @@ impl CodeGenerator for Type {
                     typedef.use_().build(p).as_(rust_name)
                 } else {
                     let mut generics = typedef.type_(rust_name).generics();
-                    for template_arg in applicable_template_args.iter() {
-                        let template_arg = ctx.resolve_type(*template_arg);
-                        if template_arg.is_named() {
-                            if template_arg.is_invalid_named_type() {
-                                warn!("Item contained invalid template \
-                                       parameter: {:?}",
-                                      item);
-                                return;
+                    if let Some(ref params) = used_template_params {
+                        for template_param in params {
+                            if let Some(id) =
+                                template_param.as_named(ctx, &()) {
+                                let template_param = ctx.resolve_type(id);
+                                if template_param.is_invalid_named_type() {
+                                    warn!("Item contained invalid template \
+                                           parameter: {:?}",
+                                          item);
+                                    return;
+                                }
+                                generics =
+                                    generics.ty_param_id(template_param.name()
+                                        .unwrap());
                             }
-                            generics =
-                                generics.ty_param_id(template_arg.name().unwrap());
                         }
                     }
                     generics.build().build_ty(inner_rust_type)
@@ -768,7 +768,7 @@ impl<'a> Bitfield<'a> {
             let field_align = field_ty_layout.align;
 
             if field_size_in_bits != 0 &&
-                (width == 0 || width as usize > unfilled_bits_in_last_unit) {
+               (width == 0 || width as usize > unfilled_bits_in_last_unit) {
                 field_size_in_bits = align_to(field_size_in_bits, field_align);
                 // Push the new field.
                 let ty =
@@ -829,6 +829,53 @@ impl<'a> Bitfield<'a> {
     }
 }
 
+impl CodeGenerator for TemplateInstantiation {
+    type Extra = Item;
+
+    fn codegen<'a>(&self,
+                   ctx: &BindgenContext,
+                   result: &mut CodegenResult<'a>,
+                   _whitelisted_items: &ItemSet,
+                   item: &Item) {
+        // Although uses of instantiations don't need code generation, and are
+        // just converted to rust types in fields, vars, etc, we take this
+        // opportunity to generate tests for their layout here.
+
+        let layout = item.kind().expect_type().layout(ctx);
+
+        if let Some(layout) = layout {
+            let size = layout.size;
+            let align = layout.align;
+
+            let name = item.canonical_name(ctx);
+            let fn_name = format!("__bindgen_test_layout_{}_instantiation_{}",
+                                  name,
+                                  item.id().as_usize());
+            let fn_name = ctx.rust_ident_raw(&fn_name);
+
+            let prefix = ctx.trait_prefix();
+            let ident = item.to_rust_ty(ctx);
+            let size_of_expr = quote_expr!(ctx.ext_cx(),
+                                           ::$prefix::mem::size_of::<$ident>());
+            let align_of_expr = quote_expr!(ctx.ext_cx(),
+                                            ::$prefix::mem::align_of::<$ident>());
+
+            let item = quote_item!(
+                ctx.ext_cx(),
+                #[test]
+                fn $fn_name() {
+                    assert_eq!($size_of_expr, $size,
+                               concat!("Size of template specialization: ", stringify!($ident)));
+                    assert_eq!($align_of_expr, $align,
+                               concat!("Alignment of template specialization: ", stringify!($ident)));
+                })
+                .unwrap();
+
+            result.push(item);
+        }
+    }
+}
+
 impl CodeGenerator for CompInfo {
     type Extra = Item;
 
@@ -847,12 +894,11 @@ impl CodeGenerator for CompInfo {
             return;
         }
 
-        let applicable_template_args = item.applicable_template_args(ctx);
+        let used_template_params = item.used_template_params(ctx);
 
         // generate tuple struct if struct or union is a forward declaration,
         // skip for now if template parameters are needed.
-        if self.is_forward_declaration() &&
-           applicable_template_args.is_empty() {
+        if self.is_forward_declaration() && used_template_params.is_none() {
             let struct_name = item.canonical_name(ctx);
             let struct_name = ctx.rust_ident_raw(&struct_name);
             let tuple_struct = quote_item!(ctx.ext_cx(),
@@ -865,35 +911,6 @@ impl CodeGenerator for CompInfo {
             return;
         }
 
-        if self.is_template_specialization() {
-            let layout = item.kind().expect_type().layout(ctx);
-
-            if let Some(layout) = layout {
-                let fn_name = format!("__bindgen_test_layout_template_{}",
-                                      result.next_id());
-                let fn_name = ctx.rust_ident_raw(&fn_name);
-                let ident = item.to_rust_ty(ctx);
-                let prefix = ctx.trait_prefix();
-                let size_of_expr = quote_expr!(ctx.ext_cx(),
-                                ::$prefix::mem::size_of::<$ident>());
-                let align_of_expr = quote_expr!(ctx.ext_cx(),
-                                ::$prefix::mem::align_of::<$ident>());
-                let size = layout.size;
-                let align = layout.align;
-                let item = quote_item!(ctx.ext_cx(),
-                                       #[test]
-                                       fn $fn_name() {
-                                           assert_eq!($size_of_expr, $size,
-                                                      concat!("Size of template specialization: ", stringify!($ident)));
-                                           assert_eq!($align_of_expr, $align,
-                                                      concat!("Alignment of template specialization: ", stringify!($ident)));
-                                       })
-                    .unwrap();
-                result.push(item);
-            }
-            return;
-        }
-
         let mut attributes = vec![];
         let mut needs_clone_impl = false;
         let mut needs_default_impl = false;
@@ -923,7 +940,7 @@ impl CodeGenerator for CompInfo {
         if item.can_derive_copy(ctx, ()) &&
            !item.annotations().disallow_copy() {
             derives.push("Copy");
-            if !applicable_template_args.is_empty() {
+            if used_template_params.is_some() {
                 // FIXME: This requires extra logic if you have a big array in a
                 // templated struct. The reason for this is that the magic:
                 //     fn clone(&self) -> Self { *self }
@@ -940,8 +957,6 @@ impl CodeGenerator for CompInfo {
             attributes.push(attributes::derives(&derives))
         }
 
-        let mut template_args_used =
-            vec![false; applicable_template_args.len()];
         let canonical_name = item.canonical_name(ctx);
         let builder = if is_union && ctx.options().unstable_rust {
             aster::AstBuilder::new()
@@ -1004,13 +1019,6 @@ impl CodeGenerator for CompInfo {
                 continue;
             }
 
-            for (i, ty_id) in applicable_template_args.iter().enumerate() {
-                let template_arg_ty = ctx.resolve_type(*ty_id);
-                if base_ty.signature_contains_named_type(ctx, template_arg_ty) {
-                    template_args_used[i] = true;
-                }
-            }
-
             let inner = base.ty.to_rust_ty(ctx);
             let field_name = if i == 0 {
                 "_base".into()
@@ -1092,13 +1100,6 @@ impl CodeGenerator for CompInfo {
                 continue;
             }
 
-            for (i, ty_id) in applicable_template_args.iter().enumerate() {
-                let template_arg = ctx.resolve_type(*ty_id);
-                if field_ty.signature_contains_named_type(ctx, template_arg) {
-                    template_args_used[i] = true;
-                }
-            }
-
             let ty = field.ty().to_rust_ty(ctx);
 
             // NB: In unstable rust we use proper `union` types.
@@ -1108,7 +1109,8 @@ impl CodeGenerator for CompInfo {
                 } else {
                     quote_ty!(ctx.ext_cx(), __BindgenUnionField<$ty>)
                 }
-            } else if let Some(item) = field_ty.is_incomplete_array(ctx) {
+            } else if let Some(item) =
+                field_ty.is_incomplete_array(ctx) {
                 result.saw_incomplete_array();
 
                 let inner = item.to_rust_ty(ctx);
@@ -1257,9 +1259,6 @@ impl CodeGenerator for CompInfo {
         if item.is_opaque(ctx) {
             fields.clear();
             methods.clear();
-            for i in 0..template_args_used.len() {
-                template_args_used[i] = false;
-            }
 
             match layout {
                 Some(l) => {
@@ -1276,7 +1275,9 @@ impl CodeGenerator for CompInfo {
             }
         } else if !is_union && !self.is_unsized(ctx) {
             if let Some(padding_field) =
-                layout.and_then(|layout| struct_layout.pad_struct(&canonical_name, layout)) {
+                layout.and_then(|layout| {
+                    struct_layout.pad_struct(&canonical_name, layout)
+                }) {
                 fields.push(padding_field);
             }
 
@@ -1299,35 +1300,17 @@ impl CodeGenerator for CompInfo {
             fields.push(field);
         }
 
-        // Append any extra template arguments that nobody has used so far.
-        for (i, ty) in applicable_template_args.iter().enumerate() {
-            if !template_args_used[i] {
-                let name = ctx.resolve_type(*ty).name().unwrap();
+        let mut generics = aster::AstBuilder::new().generics();
+
+        if let Some(ref params) = used_template_params {
+            for ty in params.iter() {
+                let param = ctx.resolve_type(*ty);
+                let name = param.name().unwrap();
                 let ident = ctx.rust_ident(name);
-                let prefix = ctx.trait_prefix();
-                let phantom = quote_ty!(ctx.ext_cx(),
-                                        ::$prefix::marker::PhantomData<$ident>);
-                let field = StructFieldBuilder::named(format!("_phantom_{}",
-                                                              i))
-                    .pub_()
-                    .build_ty(phantom);
-                fields.push(field)
+                generics = generics.ty_param_id(ident);
             }
         }
 
-
-        let mut generics = aster::AstBuilder::new().generics();
-        for template_arg in applicable_template_args.iter() {
-            // Take into account that here only arrive named types, not
-            // template specialisations that would need to be
-            // instantiated.
-            //
-            // TODO: Add template args from the parent, here and in
-            // `to_rust_ty`!!
-            let template_arg = ctx.resolve_type(*template_arg);
-            generics = generics.ty_param_id(template_arg.name().unwrap());
-        }
-
         let generics = generics.build();
 
         let rust_struct = builder.with_generics(generics.clone())
@@ -1353,7 +1336,7 @@ impl CodeGenerator for CompInfo {
                   canonical_name);
         }
 
-        if applicable_template_args.is_empty() {
+        if used_template_params.is_none() {
             for var in self.inner_vars() {
                 ctx.resolve_item(*var)
                     .codegen(ctx, result, whitelisted_items, &());
@@ -2193,16 +2176,54 @@ impl ToRustTy for Type {
                 let path = item.namespace_aware_canonical_path(ctx);
                 aster::AstBuilder::new().ty().path().ids(path).build()
             }
-            TypeKind::TemplateInstantiation(inner, ref template_args) => {
-                // PS: Sorry for the duplication here.
-                let mut inner_ty = inner.to_rust_ty(ctx).unwrap();
+            TypeKind::TemplateInstantiation(ref inst) => {
+                let decl = inst.template_definition();
+                let mut ty = decl.to_rust_ty(ctx).unwrap();
 
-                if let ast::TyKind::Path(_, ref mut path) = inner_ty.node {
-                    let template_args = template_args.iter()
-                        .map(|arg| arg.to_rust_ty(ctx))
+                // If we gave up when making a type for the template definition,
+                // check if maybe we can make a better opaque blob for the
+                // instantiation.
+                if ty == aster::AstBuilder::new().ty().unit().unwrap() {
+                    if let Some(layout) = self.layout(ctx) {
+                        ty = BlobTyBuilder::new(layout).build().unwrap()
+                    }
+                }
+
+                let decl_params = if let Some(params) =
+                    decl.self_template_params(ctx) {
+                    params
+                } else {
+                    // This can happen if we generated an opaque type for a
+                    // partial template specialization, in which case we just
+                    // use the opaque type's layout. If we don't have a layout,
+                    // we cross our fingers and hope for the best :-/
+                    debug_assert!(ctx.resolve_type_through_type_refs(decl)
+                        .is_opaque());
+                    let layout = self.layout(ctx).unwrap_or(Layout::zero());
+                    ty = BlobTyBuilder::new(layout).build().unwrap();
+
+                    vec![]
+                };
+
+                // TODO: If the decl type is a template class/struct
+                // declaration's member template declaration, it could rely on
+                // generic template parameters from its outer template
+                // class/struct. When we emit bindings for it, it could require
+                // *more* type arguments than we have here, and we will need to
+                // reconstruct them somehow. We don't have any means of doing
+                // that reconstruction at this time.
+
+                if let ast::TyKind::Path(_, ref mut path) = ty.node {
+                    let template_args = inst.template_arguments()
+                        .iter()
+                        .zip(decl_params.iter())
+                        // Only pass type arguments for the type parameters that
+                        // the decl uses.
+                        .filter(|&(_, param)| ctx.uses_template_parameter(decl, *param))
+                        .map(|(arg, _)| arg.to_rust_ty(ctx))
                         .collect::<Vec<_>>();
 
-                    path.segments.last_mut().unwrap().parameters = if
+                    path.segments.last_mut().unwrap().parameters = if 
                         template_args.is_empty() {
                         None
                     } else {
@@ -2216,18 +2237,19 @@ impl ToRustTy for Type {
                     }
                 }
 
-                P(inner_ty)
+                P(ty)
             }
             TypeKind::ResolvedTypeRef(inner) => inner.to_rust_ty(ctx),
             TypeKind::TemplateAlias(inner, _) |
             TypeKind::Alias(inner) => {
-                let applicable_named_args = item.applicable_template_args(ctx)
+                let template_params = item.used_template_params(ctx)
+                    .unwrap_or(vec![])
                     .into_iter()
-                    .filter(|arg| ctx.resolve_type(*arg).is_named())
+                    .filter(|param| param.is_named(ctx, &()))
                     .collect::<Vec<_>>();
 
                 let spelling = self.name().expect("Unnamed alias?");
-                if item.is_opaque(ctx) && !applicable_named_args.is_empty() {
+                if item.is_opaque(ctx) && !template_params.is_empty() {
                     // Pray if there's no available layout.
                     let layout = self.layout(ctx).unwrap_or_else(Layout::zero);
                     BlobTyBuilder::new(layout).build()
@@ -2236,15 +2258,13 @@ impl ToRustTy for Type {
                                                                 inner) {
                     ty
                 } else {
-                    utils::build_templated_path(item,
-                                                ctx,
-                                                applicable_named_args)
+                    utils::build_templated_path(item, ctx, template_params)
                 }
             }
             TypeKind::Comp(ref info) => {
-                let template_args = item.applicable_template_args(ctx);
+                let template_params = item.used_template_params(ctx);
                 if info.has_non_type_template_params() ||
-                   (item.is_opaque(ctx) && !template_args.is_empty()) {
+                   (item.is_opaque(ctx) && template_params.is_some()) {
                     return match self.layout(ctx) {
                         Some(layout) => BlobTyBuilder::new(layout).build(),
                         None => {
@@ -2256,7 +2276,13 @@ impl ToRustTy for Type {
                     };
                 }
 
-                utils::build_templated_path(item, ctx, template_args)
+                utils::build_templated_path(item,
+                                            ctx,
+                                            template_params.unwrap_or(vec![]))
+            }
+            TypeKind::Opaque => {
+                BlobTyBuilder::new(self.layout(ctx).unwrap_or(Layout::zero()))
+                    .build()
             }
             TypeKind::BlockPointer => {
                 let void = raw_type(ctx, "c_void");
@@ -2742,19 +2768,19 @@ mod utils {
 
     pub fn build_templated_path(item: &Item,
                                 ctx: &BindgenContext,
-                                template_args: Vec<ItemId>)
+                                template_params: Vec<ItemId>)
                                 -> P<ast::Ty> {
         let path = item.namespace_aware_canonical_path(ctx);
         let builder = aster::AstBuilder::new().ty().path();
 
-        let template_args = template_args.iter()
-            .map(|arg| arg.to_rust_ty(ctx))
+        let template_params = template_params.iter()
+            .map(|param| param.to_rust_ty(ctx))
             .collect::<Vec<_>>();
 
         // XXX: I suck at aster.
         if path.len() == 1 {
             return builder.segment(&path[0])
-                .with_tys(template_args)
+                .with_tys(template_params)
                 .build()
                 .build();
         }
@@ -2765,7 +2791,7 @@ mod utils {
             builder = if i == path.len() - 2 {
                 // XXX Extra clone courtesy of the borrow checker.
                 builder.segment(&segment)
-                    .with_tys(template_args.clone())
+                    .with_tys(template_params.clone())
                     .build()
             } else {
                 builder.segment(&segment).build()