Auto merge of #539 - fitzgen:gotta-land-some-of-this-stuff, r=emilio

Gotta land some of this stuff...

My patch queue is getting quite large, as I refactor templates in bindgen, so I figure I should land the stuff that is in good shape sooner rather than later :-P

This stuff tweaks the named template parameter analysis, adds some edge kinds, stuff like that. This is still not used by codegen, yet. I have another branch where I de-dupe named types and all of that, and there is only two tests failing now, but still some clean up needed.

This also contains the expanded documentation for te named template parameter analysis that I promised.

See each commit message for details.

r? @emilio

7 files changed, 414 insertions, 102 deletions

diff --git a/src/ir/comp.rs b/src/ir/comp.rs
index ce6ec25d..492c1a98 100644
--- a/src/ir/comp.rs
+++ b/src/ir/comp.rs
@@ -871,7 +871,7 @@ impl CompInfo {
 }
 
 impl TemplateDeclaration for CompInfo {
-    fn template_params(&self, _ctx: &BindgenContext) -> Option<Vec<ItemId>> {
+    fn self_template_params(&self, _ctx: &BindgenContext) -> Option<Vec<ItemId>> {
         if self.template_args.is_empty() {
             None
         } else {
@@ -1040,10 +1040,10 @@ impl Trace for CompInfo {
         if let Some(template) = self.specialized_template() {
             // This is an instantiation of a template declaration with concrete
             // template type arguments.
-            tracer.visit(template);
+            tracer.visit_kind(template, EdgeKind::TemplateDeclaration);
             let args = item.applicable_template_args(context);
             for a in args {
-                tracer.visit(a);
+                tracer.visit_kind(a, EdgeKind::TemplateArgument);
             }
         } else {
             let params = item.applicable_template_args(context);
@@ -1055,27 +1055,27 @@ impl Trace for CompInfo {
         }
 
         for base in self.base_members() {
-            tracer.visit(base.ty);
+            tracer.visit_kind(base.ty, EdgeKind::BaseMember);
         }
 
         for field in self.fields() {
-            tracer.visit(field.ty());
+            tracer.visit_kind(field.ty(), EdgeKind::Field);
         }
 
         for &ty in self.inner_types() {
-            tracer.visit(ty);
+            tracer.visit_kind(ty, EdgeKind::InnerType);
         }
 
         for &var in self.inner_vars() {
-            tracer.visit(var);
+            tracer.visit_kind(var, EdgeKind::InnerVar);
         }
 
         for method in self.methods() {
-            tracer.visit(method.signature);
+            tracer.visit_kind(method.signature, EdgeKind::Method);
         }
 
         for &ctor in self.constructors() {
-            tracer.visit(ctor);
+            tracer.visit_kind(ctor, EdgeKind::Constructor);
         }
     }
 }
diff --git a/src/ir/context.rs b/src/ir/context.rs
index d2fb2bef..27a43f20 100644
--- a/src/ir/context.rs
+++ b/src/ir/context.rs
@@ -634,7 +634,7 @@ impl<'ctx> BindgenContext<'ctx> {
             .and_then(|canon_decl| {
                 self.get_resolved_type(&canon_decl)
                     .and_then(|template_decl_id| {
-                        template_decl_id.num_template_params(self)
+                        template_decl_id.num_self_template_params(self)
                             .map(|num_params| {
                                 (*canon_decl.cursor(),
                                  template_decl_id,
@@ -658,7 +658,7 @@ impl<'ctx> BindgenContext<'ctx> {
                             .cloned()
                     })
                     .and_then(|template_decl| {
-                        template_decl.num_template_params(self)
+                        template_decl.num_self_template_params(self)
                             .map(|num_template_params| {
                                 (*template_decl.decl(),
                                  template_decl.id(),
@@ -706,7 +706,7 @@ impl<'ctx> BindgenContext<'ctx> {
         use clang_sys;
 
         let num_expected_args = match self.resolve_type(template)
-            .num_template_params(self) {
+            .num_self_template_params(self) {
             Some(n) => n,
             None => {
                 warn!("Tried to instantiate a template for which we could not \
@@ -1331,13 +1331,13 @@ impl PartialType {
 }
 
 impl TemplateDeclaration for PartialType {
-    fn template_params(&self, _ctx: &BindgenContext) -> Option<Vec<ItemId>> {
+    fn self_template_params(&self, _ctx: &BindgenContext) -> Option<Vec<ItemId>> {
         // Maybe at some point we will eagerly parse named types, but for now we
         // don't and this information is unavailable.
         None
     }
 
-    fn num_template_params(&self, _ctx: &BindgenContext) -> Option<usize> {
+    fn num_self_template_params(&self, _ctx: &BindgenContext) -> Option<usize> {
         // Wouldn't it be nice if libclang would reliably give us this
         // information‽
         match self.decl().kind() {
diff --git a/src/ir/function.rs b/src/ir/function.rs
index daa30b89..2a13b9f0 100644
--- a/src/ir/function.rs
+++ b/src/ir/function.rs
@@ -3,7 +3,7 @@
 use super::context::{BindgenContext, ItemId};
 use super::dot::DotAttributes;
 use super::item::Item;
-use super::traversal::{Trace, Tracer};
+use super::traversal::{EdgeKind, Trace, Tracer};
 use super::ty::TypeKind;
 use clang;
 use clang_sys::CXCallingConv;
@@ -336,10 +336,10 @@ impl Trace for FunctionSig {
     fn trace<T>(&self, _: &BindgenContext, tracer: &mut T, _: &())
         where T: Tracer,
     {
-        tracer.visit(self.return_type());
+        tracer.visit_kind(self.return_type(), EdgeKind::FunctionReturn);
 
         for &(_, ty) in self.argument_types() {
-            tracer.visit(ty);
+            tracer.visit_kind(ty, EdgeKind::FunctionParameter);
         }
     }
 }
diff --git a/src/ir/item.rs b/src/ir/item.rs
index bd401aba..21b27f07 100644
--- a/src/ir/item.rs
+++ b/src/ir/item.rs
@@ -7,7 +7,7 @@ use super::dot::{DotAttributes};
 use super::function::Function;
 use super::item_kind::ItemKind;
 use super::module::Module;
-use super::traversal::{Trace, Tracer};
+use super::traversal::{EdgeKind, Trace, Tracer};
 use super::ty::{TemplateDeclaration, Type, TypeKind};
 use clang;
 use clang_sys;
@@ -205,7 +205,7 @@ impl Trace for Item {
                 tracer.visit(fun.signature());
             }
             ItemKind::Var(ref var) => {
-                tracer.visit(var.ty());
+                tracer.visit_kind(var.ty(), EdgeKind::VarType);
             }
             ItemKind::Module(_) => {
                 // Module -> children edges are "weak", and we do not want to
@@ -930,22 +930,22 @@ impl DotAttributes for Item {
 }
 
 impl TemplateDeclaration for ItemId {
-    fn template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>> {
+    fn self_template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>> {
         ctx.resolve_item_fallible(*self)
-            .and_then(|item| item.template_params(ctx))
+            .and_then(|item| item.self_template_params(ctx))
     }
 }
 
 impl TemplateDeclaration for Item {
-    fn template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>> {
-        self.kind.template_params(ctx)
+    fn self_template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>> {
+        self.kind.self_template_params(ctx)
     }
 }
 
 impl TemplateDeclaration for ItemKind {
-    fn template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>> {
+    fn self_template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>> {
         match *self {
-            ItemKind::Type(ref ty) => ty.template_params(ctx),
+            ItemKind::Type(ref ty) => ty.self_template_params(ctx),
             // If we start emitting bindings to explicitly instantiated
             // functions, then we'll need to check ItemKind::Function for
             // template params.
diff --git a/src/ir/named.rs b/src/ir/named.rs
index 7a6c597c..3c676662 100644
--- a/src/ir/named.rs
+++ b/src/ir/named.rs
@@ -76,11 +76,50 @@
 //! fixed-point.
 //!
 //! We use the "monotone framework" for this fix-point analysis where our
-//! lattice is the powerset of the template parameters that appear in the input
-//! C++ header, our join function is set union, and we use the
-//! `ir::traversal::Trace` trait to implement the work-list optimization so we
-//! don't have to revisit every node in the graph when for every iteration
-//! towards the fix-point.
+//! lattice is the mapping from each IR item to the powerset of the template
+//! parameters that appear in the input C++ header, our join function is set
+//! union, and we use the `ir::traversal::Trace` trait to implement the
+//! work-list optimization so we don't have to revisit every node in the graph
+//! when for every iteration towards the fix-point.
+//!
+//! A lattice is a set with a partial ordering between elements, where there is
+//! a single least upper bound and a single greatest least bound for every
+//! subset. We are dealing with finite lattices, which means that it has a
+//! finite number of elements, and it follows that there exists a single top and
+//! a single bottom member of the lattice. For example, the power set of a
+//! finite set forms a finite lattice where partial ordering is defined by set
+//! inclusion, that is `a <= b` if `a` is a subset of `b`. Here is the finite
+//! lattice constructed from the set {0,1,2}:
+//!
+//! ```text
+//!                    .----- Top = {0,1,2} -----.
+//!                   /            |              \
+//!                  /             |               \
+//!                 /              |                \
+//!              {0,1} -------.  {0,2}  .--------- {1,2}
+//!                |           \ /   \ /             |
+//!                |            /     \              |
+//!                |           / \   / \             |
+//!               {0} --------'   {1}   `---------- {2}
+//!                 \              |                /
+//!                  \             |               /
+//!                   \            |              /
+//!                    `------ Bottom = {} ------'
+//! ```
+//!
+//! A monotone function `f` is a function where if `x <= y`, then it holds that
+//! `f(x) <= f(y)`. It should be clear that running a monotone function to a
+//! fix-point on a finite lattice will always terminate: `f` can only "move"
+//! along the lattice in a single direction, and therefore can only either find
+//! a fix-point in the middle of the lattice or continue to the top or bottom
+//! depending if it is ascending or descending the lattice respectively.
+//!
+//! For our analysis, we are collecting the set of template parameters used by
+//! any given IR node. The set of template parameters appearing in the program
+//! is finite. Our lattice is their powerset. We start at the bottom element,
+//! the empty set. Our analysis only adds members to the set of used template
+//! parameters, never removes them, so it is monotone, and therefore iteration
+//! to a fix-point will terminate.
 //!
 //! For a deeper introduction to the general form of this kind of analysis, see
 //! [Static Program Analysis by Anders Møller and Michael I. Schwartzbach][spa].
@@ -173,42 +212,123 @@ pub fn analyze<Analysis>(extra: Analysis::Extra) -> Analysis::Output
     analysis.into()
 }
 
-/// An analysis that finds the set of template parameters that actually end up
-/// used in our generated bindings.
+/// An analysis that finds for each IR item its set of template parameters that
+/// it uses.
+///
+/// We use the following monotone constraint function:
+///
+/// ```ignore
+/// template_param_usage(v) =
+///     self_template_param_usage(v) union
+///     template_param_usage(w_0) union
+///     template_param_usage(w_1) union
+///     ...
+///     template_param_usage(w_n)
+/// ```
+///
+/// Where `v` has direct edges in the IR graph to each of `w_0`, `w_1`,
+/// ..., `w_n` (for example, if `v` were a struct type and `x` and `y`
+/// were the types of two of `v`'s fields). We ignore certain edges, such
+/// as edges from a template declaration to its template parameters'
+/// definitions for this analysis. If we didn't, then we would mistakenly
+/// determine that ever template parameter is always used.
+///
+/// Finally, `self_template_param_usage` is defined with the following cases:
+///
+/// * If `T` is a template parameter:
+///
+/// ```ignore
+/// self_template_param_usage(T) = { T }
+/// ```
+///
+/// * If `inst` is a template instantiation, `inst.args` are the template
+///   instantiation's template arguments, and `inst.decl` is the template
+///   declaration being instantiated:
+///
+/// ```ignore
+/// self_template_param_usage(inst) =
+///     { T: for T in inst.args, if T in template_param_usage(inst.decl) }
+/// ```
+///
+/// * And for all other IR items, the result is the empty set:
+///
+/// ```ignore
+/// self_template_param_usage(_) = { }
+/// ```
 #[derive(Debug, Clone)]
 pub struct UsedTemplateParameters<'a> {
     ctx: &'a BindgenContext<'a>,
-    used: ItemSet,
+    used: HashMap<ItemId, ItemSet>,
     dependencies: HashMap<ItemId, Vec<ItemId>>,
 }
 
+impl<'a> UsedTemplateParameters<'a> {
+    fn consider_edge(kind: EdgeKind) -> bool {
+        match kind {
+            // For each of these kinds of edges, if the referent uses a template
+            // parameter, then it should be considered that the origin of the
+            // edge also uses the template parameter.
+            EdgeKind::TemplateArgument |
+            EdgeKind::BaseMember |
+            EdgeKind::Field |
+            EdgeKind::InnerType |
+            EdgeKind::InnerVar |
+            EdgeKind::Constructor |
+            EdgeKind::VarType |
+            EdgeKind::TypeReference => true,
+
+            // We can't emit machine code for new instantiations of function
+            // templates and class templates' methods (and don't detect explicit
+            // instantiations) so we must ignore template parameters that are
+            // only used by functions.
+            EdgeKind::Method |
+            EdgeKind::FunctionReturn |
+            EdgeKind::FunctionParameter => false,
+
+            // If we considered these edges, we would end up mistakenly claiming
+            // that every template parameter always used.
+            EdgeKind::TemplateDeclaration |
+            EdgeKind::TemplateParameterDefinition => false,
+
+            // Since we have to be careful about which edges we consider for
+            // this analysis to be correct, we ignore generic edges. We also
+            // avoid a `_` wild card to force authors of new edge kinds to
+            // determine whether they need to be considered by this analysis.
+            EdgeKind::Generic => false,
+        }
+    }
+}
+
 impl<'a> MonotoneFramework for UsedTemplateParameters<'a> {
     type Node = ItemId;
     type Extra = &'a BindgenContext<'a>;
-    type Output = ItemSet;
+    type Output = HashMap<ItemId, ItemSet>;
 
     fn new(ctx: &'a BindgenContext<'a>) -> UsedTemplateParameters<'a> {
+        let mut used = HashMap::new();
         let mut dependencies = HashMap::new();
 
         for item in ctx.whitelisted_items() {
+            dependencies.entry(item).or_insert(vec![]);
+            used.insert(item, ItemSet::new());
+
             {
                 // We reverse our natural IR graph edges to find dependencies
                 // between nodes.
-                let mut add_reverse_edge = |sub_item, _| {
+                item.trace(ctx, &mut |sub_item, _| {
                     dependencies.entry(sub_item).or_insert(vec![]).push(item);
-                };
-                item.trace(ctx, &mut add_reverse_edge, &());
+                }, &());
             }
 
             // Additionally, whether a template instantiation's template
             // arguments are used depends on whether the template declaration's
             // generic template parameters are used.
-            ctx.resolve_item_fallible(item)
-                .and_then(|item| item.as_type())
+            ctx.resolve_item(item)
+                .as_type()
                 .map(|ty| match ty.kind() {
                     &TypeKind::TemplateInstantiation(decl, ref args) => {
                         let decl = ctx.resolve_type(decl);
-                        let params = decl.template_params(ctx)
+                        let params = decl.self_template_params(ctx)
                             .expect("a template instantiation's referenced \
                                      template declaration should have template \
                                      parameters");
@@ -222,57 +342,65 @@ impl<'a> MonotoneFramework for UsedTemplateParameters<'a> {
 
         UsedTemplateParameters {
             ctx: ctx,
-            used: ItemSet::new(),
+            used: used,
             dependencies: dependencies,
         }
     }
 
-    fn initial_worklist(&self) -> Vec<Self::Node> {
+    fn initial_worklist(&self) -> Vec<ItemId> {
         self.ctx.whitelisted_items().collect()
     }
 
-    fn constrain(&mut self, item: ItemId) -> bool {
-        let original_size = self.used.len();
+    fn constrain(&mut self, id: ItemId) -> bool {
+        let original_len = self.used[&id].len();
 
-        item.trace(self.ctx, &mut |item, edge_kind| {
-            if edge_kind == EdgeKind::TemplateParameterDefinition {
-                // The definition of a template parameter is not considered a
-                // use of said template parameter. Ignore this edge.
-                return;
+        // First, add this item's self template parameter usage.
+        let item = self.ctx.resolve_item(id);
+        let ty_kind = item.as_type().map(|ty| ty.kind());
+        match ty_kind {
+            Some(&TypeKind::Named) => {
+                // This is a trivial use of the template type parameter.
+                self.used.get_mut(&id).unwrap().insert(id);
             }
-
-            let ty_kind = self.ctx.resolve_item(item)
-                .as_type()
-                .map(|ty| ty.kind());
-
-            match ty_kind {
-                Some(&TypeKind::Named) => {
-                    // This is a "trivial" use of the template type parameter.
-                    self.used.insert(item);
-                },
-                Some(&TypeKind::TemplateInstantiation(decl, ref args)) => {
-                    // A template instantiation's concrete template argument is
-                    // only used if the template declaration uses the
-                    // corresponding template parameter.
-                    let decl = self.ctx.resolve_type(decl);
-                    let params = decl.template_params(self.ctx)
-                        .expect("a template instantiation's referenced \
-                                 template declaration should have template \
-                                 parameters");
-                    for (arg, param) in args.iter().zip(params.iter()) {
-                        if self.used.contains(param) {
-                            if self.ctx.resolve_item(*arg).is_named() {
-                                self.used.insert(*arg);
-                            }
+            Some(&TypeKind::TemplateInstantiation(decl, ref args)) => {
+                // A template instantiation's concrete template argument is
+                // only used if the template declaration uses the
+                // corresponding template parameter.
+                let params = decl.self_template_params(self.ctx)
+                    .expect("a template instantiation's referenced \
+                             template declaration should have template \
+                             parameters");
+                for (arg, param) in args.iter().zip(params.iter()) {
+                    if self.used[&decl].contains(param) {
+                        if self.ctx.resolve_item(*arg).is_named() {
+                            self.used.get_mut(&id).unwrap().insert(*arg);
                         }
                     }
-                },
-                _ => return,
+                }
             }
+            _ => {}
+        }
+
+        // Second, add the union of each of its referent item's template
+        // parameter usage.
+        item.trace(self.ctx, &mut |sub_id, edge_kind| {
+            if sub_id == id || !Self::consider_edge(edge_kind) {
+                return;
+            }
+
+            // This clone is unfortunate because we are potentially thrashing
+            // malloc. We could investigate replacing the ItemSet values with
+            // Rc<RefCell<ItemSet>> to make the borrow checker happy, but it
+            // isn't clear that the added indirection wouldn't outweigh the cost
+            // of malloc'ing a new ItemSet here. Ideally, `HashMap` would have a
+            // `split_entries` method analogous to `slice::split_at_mut`...
+            let to_add = self.used[&sub_id].clone();
+            self.used.get_mut(&id).unwrap().extend(to_add);
         }, &());
 
-        let new_size = self.used.len();
-        new_size != original_size
+        let new_len = self.used[&id].len();
+        assert!(new_len >= original_len);
+        new_len != original_len
     }
 
     fn each_depending_on<F>(&self, item: ItemId, mut f: F)
@@ -286,8 +414,8 @@ impl<'a> MonotoneFramework for UsedTemplateParameters<'a> {
     }
 }
 
-impl<'a> From<UsedTemplateParameters<'a>> for ItemSet {
-    fn from(used_templ_params: UsedTemplateParameters) -> ItemSet {
+impl<'a> From<UsedTemplateParameters<'a>> for HashMap<ItemId, ItemSet> {
+    fn from(used_templ_params: UsedTemplateParameters) -> Self {
         used_templ_params.used
     }
 }
diff --git a/src/ir/traversal.rs b/src/ir/traversal.rs
index 8c5e32cf..30772aad 100644
--- a/src/ir/traversal.rs
+++ b/src/ir/traversal.rs
@@ -44,22 +44,137 @@ impl Into<ItemId> for Edge {
 }
 
 /// The kind of edge reference. This is useful when we wish to only consider
-/// certain kinds of edges for a particular traversal.
+/// certain kinds of edges for a particular traversal or analysis.
 #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub enum EdgeKind {
     /// A generic, catch-all edge.
     Generic,
 
     /// An edge from a template declaration, to the definition of a named type
-    /// parameter. For example, the edge Foo -> T in the following snippet:
+    /// parameter. For example, the edge from `Foo<T>` to `T` in the following
+    /// snippet:
     ///
     /// ```C++
     /// template<typename T>
+    /// class Foo { };
+    /// ```
+    TemplateParameterDefinition,
+
+    /// An edge from a template instantiation to the template declaration that
+    /// is being instantiated. For example, the edge from `Foo<int>` to
+    /// to `Foo<T>`:
+    ///
+    /// ```C++
+    /// template<typename T>
+    /// class Foo { };
+    ///
+    /// using Bar = Foo<int>;
+    /// ```
+    TemplateDeclaration,
+
+    /// An edge from a template instantiation to its template argument. For
+    /// example, `Foo<Bar>` to `Bar`:
+    ///
+    /// ```C++
+    /// template<typename T>
+    /// class Foo { };
+    ///
+    /// class Bar { };
+    ///
+    /// using FooBar = Foo<Bar>;
+    /// ```
+    TemplateArgument,
+
+    /// An edge from a compound type to one of its base member types. For
+    /// example, the edge from `Bar` to `Foo`:
+    ///
+    /// ```C++
+    /// class Foo { };
+    ///
+    /// class Bar : public Foo { };
+    /// ```
+    BaseMember,
+
+    /// An edge from a compound type to the types of one of its fields. For
+    /// example, the edge from `Foo` to `int`:
+    ///
+    /// ```C++
     /// class Foo {
     ///     int x;
     /// };
     /// ```
-    TemplateParameterDefinition,
+    Field,
+
+    /// An edge from an class or struct type to an inner type member. For
+    /// example, the edge from `Foo` to `Foo::Bar` here:
+    ///
+    /// ```C++
+    /// class Foo {
+    ///     struct Bar { };
+    /// };
+    /// ```
+    InnerType,
+
+    /// An edge from an class or struct type to an inner static variable. For
+    /// example, the edge from `Foo` to `Foo::BAR` here:
+    ///
+    /// ```C++
+    /// class Foo {
+    ///     static const char* BAR;
+    /// };
+    /// ```
+    InnerVar,
+
+    /// An edge from a class or struct type to one of its method functions. For
+    /// example, the edge from `Foo` to `Foo::bar`:
+    ///
+    /// ```C++
+    /// class Foo {
+    ///     bool bar(int x, int y);
+    /// };
+    /// ```
+    Method,
+
+    /// An edge from a class or struct type to one of its constructor
+    /// functions. For example, the edge from `Foo` to `Foo::Foo(int x, int y)`:
+    ///
+    /// ```C++
+    /// class Foo {
+    ///     int my_x;
+    ///     int my_y;
+    ///
+    ///   public:
+    ///     Foo(int x, int y);
+    /// };
+    /// ```
+    Constructor,
+
+    /// An edge from a function declaration to its return type. For example, the
+    /// edge from `foo` to `int`:
+    ///
+    /// ```C++
+    /// int foo(char* string);
+    /// ```
+    FunctionReturn,
+
+    /// An edge from a function declaration to one of its parameter types. For
+    /// example, the edge from `foo` to `char*`:
+    ///
+    /// ```C++
+    /// int foo(char* string);
+    /// ```
+    FunctionParameter,
+
+    /// An edge from a static variable to its type. For example, the edge from
+    /// `FOO` to `const char*`:
+    ///
+    /// ```C++
+    /// static const char* FOO;
+    /// ```
+    VarType,
+
+    /// An edge from a non-templated alias or typedef to the referenced type.
+    TypeReference,
 }
 
 /// A predicate to allow visiting only sub-sets of the whole IR graph by
@@ -211,7 +326,8 @@ impl<F> Tracer for F
 }
 
 /// Trace all of the outgoing edges to other items. Implementations should call
-/// `tracer.visit(edge)` for each of their outgoing edges.
+/// one of `tracer.visit(edge)` or `tracer.visit_kind(edge, EdgeKind::Whatever)`
+/// for each of their outgoing edges.
 pub trait Trace {
     /// If a particular type needs extra information beyond what it has in
     /// `self` and `context` to find its referenced items, its implementation
diff --git a/src/ir/ty.rs b/src/ir/ty.rs
index 5491ceaf..ce42a171 100644
--- a/src/ir/ty.rs
+++ b/src/ir/ty.rs
@@ -7,25 +7,59 @@ use super::dot::DotAttributes;
 use super::enum_ty::Enum;
 use super::function::FunctionSig;
 use super::int::IntKind;
-use super::item::Item;
+use super::item::{Item, ItemAncestors};
 use super::layout::Layout;
 use super::objc::ObjCInterface;
-use super::traversal::{Trace, Tracer};
+use super::traversal::{EdgeKind, Trace, Tracer};
 use clang::{self, Cursor};
 use parse::{ClangItemParser, ParseError, ParseResult};
 use std::io;
 use std::mem;
 
-/// Template declaration related methods.
+/// Template declaration (and such declaration's template parameters) related
+/// methods.
+///
+/// Consider this example:
+///
+/// ```c++
+/// template <typename T, typename U>
+/// class Foo {
+///     template <typename V>
+///     using Bar = V*;
+///
+///     class Inner {
+///         T        x;
+///         U        y;
+///         Bar<int> z;
+///     };
+/// };
+///
+/// class Qux {
+///     int y;
+/// };
+/// ```
+///
+/// The following table depicts the results of each trait method when invoked on
+/// `Foo`, `Bar`, and `Qux`.
+///
+/// +------+----------------------+--------------------------+------------------------+
+/// |Decl. | self_template_params | num_self_template_params | all_template_parameters|
+/// +------+----------------------+--------------------------+------------------------+
+/// |Foo   | Some([T, U])         | Some(2)                  | Some([T, U])           |
+/// |Bar   | Some([V])            | Some(1)                  | Some([T, U, V])        |
+/// |Inner | None                 | None                     | Some([T, U])           |
+/// |Qux   | None                 | None                     | None                   |
+/// +------+----------------------+--------------------------+------------------------+
 pub trait TemplateDeclaration {
     /// Get the set of `ItemId`s that make up this template declaration's free
     /// template parameters.
     ///
     /// Note that these might *not* all be named types: C++ allows
-    /// constant-value template parameters. Of course, Rust does not allow
-    /// generic parameters to be anything but types, so we must treat them as
-    /// opaque, and avoid instantiating them.
-    fn template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>>;
+    /// constant-value template parameters as well as template-template
+    /// parameters. Of course, Rust does not allow generic parameters to be
+    /// anything but types, so we must treat them as opaque, and avoid
+    /// instantiating them.
+    fn self_template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>>;
 
     /// Get the number of free template parameters this template declaration
     /// has.
@@ -34,8 +68,38 @@ pub trait TemplateDeclaration {
     /// `template_params` returns `None`. This is useful when we only have
     /// partial information about the template declaration, such as when we are
     /// in the middle of parsing it.
-    fn num_template_params(&self, ctx: &BindgenContext) -> Option<usize> {
-        self.template_params(ctx).map(|params| params.len())
+    fn num_self_template_params(&self, ctx: &BindgenContext) -> Option<usize> {
+        self.self_template_params(ctx).map(|params| params.len())
+    }
+
+    /// Get the complete set of template parameters that can affect this
+    /// declaration.
+    ///
+    /// Note that this item doesn't need to be a template declaration itself for
+    /// `Some` to be returned here (in contrast to `self_template_params`). If
+    /// this item is a member of a template declaration, then the parent's
+    /// template parameters are included here.
+    ///
+    /// In the example above, `Inner` depends on both of the `T` and `U` type
+    /// parameters, even though it is not itself a template declaration and
+    /// therefore has no type parameters itself. Perhaps it helps to think about
+    /// how we would fully reference such a member type in C++:
+    /// `Foo<int,char>::Inner`. `Foo` *must* be instantiated with template
+    /// arguments before we can gain access to the `Inner` member type.
+    fn all_template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>>
+        where Self: ItemAncestors
+    {
+        let each_self_params: Vec<Vec<_>> = self.ancestors(ctx)
+            .filter_map(|id| id.self_template_params(ctx))
+            .collect();
+        if each_self_params.is_empty() {
+            None
+        } else {
+            Some(each_self_params.into_iter()
+                 .rev()
+                 .flat_map(|params| params)
+                 .collect())
+        }
     }
 }
 
@@ -491,18 +555,18 @@ fn is_invalid_named_type_empty_name() {
 
 
 impl TemplateDeclaration for Type {
-    fn template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>> {
-        self.kind.template_params(ctx)
+    fn self_template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>> {
+        self.kind.self_template_params(ctx)
     }
 }
 
 impl TemplateDeclaration for TypeKind {
-    fn template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>> {
+    fn self_template_params(&self, ctx: &BindgenContext) -> Option<Vec<ItemId>> {
         match *self {
             TypeKind::ResolvedTypeRef(id) => {
-                ctx.resolve_type(id).template_params(ctx)
+                ctx.resolve_type(id).self_template_params(ctx)
             }
-            TypeKind::Comp(ref comp) => comp.template_params(ctx),
+            TypeKind::Comp(ref comp) => comp.self_template_params(ctx),
             TypeKind::TemplateAlias(_, ref args) => Some(args.clone()),
 
             TypeKind::TemplateInstantiation(..) |
@@ -1202,14 +1266,18 @@ impl Trace for Type {
             TypeKind::Array(inner, _) |
             TypeKind::Alias(inner) |
             TypeKind::ResolvedTypeRef(inner) => {
-                tracer.visit(inner);
+                tracer.visit_kind(inner, EdgeKind::TypeReference);
+            }
+            TypeKind::TemplateAlias(inner, ref template_params) => {
+                tracer.visit_kind(inner, EdgeKind::TypeReference);
+                for &item in template_params {
+                    tracer.visit_kind(item, EdgeKind::TemplateParameterDefinition);
+                }
             }
-
-            TypeKind::TemplateAlias(inner, ref template_args) |
             TypeKind::TemplateInstantiation(inner, ref template_args) => {
-                tracer.visit(inner);
+                tracer.visit_kind(inner, EdgeKind::TemplateDeclaration);
                 for &item in template_args {
-                    tracer.visit(item);
+                    tracer.visit_kind(item, EdgeKind::TemplateArgument);
                 }
             }
             TypeKind::Comp(ref ci) => ci.trace(context, tracer, item),