Auto merge of #663 - fitzgen:how-many-stylo-bugs-to-screw-in-a-lightbulb, r=emilio

Fix blacklisting and fix instantiations in the template analysis

For correctness, I now realize that we need to consider the full transitive closure of whitelisted items, including blacklisted items that we would otherwise not consider as whitelisted. We need this so that the data flow propagates properly through dependencies that may or may not be blacklisted.

This means that tracing infrastructure needs to trace items regardless if they are hidden or blacklisted. It is now the responsibility of consumers of a traversal to filter out such items if they are unwanted. I did this by turning the `ir::context::WhitelistedItems` type alias into a proper struct that performs the filtering. This approach avoids changing the many callers of whitelisted items traversal iteration.

Additionally, and equally importantly, I realized that the case of template instantiations' template usages were subtly wrong. Before this commit, we only considered a template argument used if it itself was a template parameter. This breaks down in the face of template instantiations used as arguments to another template instantiation. If the inner instantiation used a template parameter, we would accidentally lose that usage. For example:

```c++
template <class T>
struct Foo {
    // Direct usage of a template parameter T in an instantiation always worked.
    Bar<T> member;

    // While indirect usage of a template parameter nested within another
    // instantiation did NOT previously work.
    Bar< Qux<T> > another_member;
};
```

The solution is to take the union of each template arguments' template usages, not the template arguments themselves but only if they were themselves a template parameter. Obvious in retrospect!

Fixes #662.

r? @emilio

9 files changed, 258 insertions, 79 deletions

diff --git a/src/ir/context.rs b/src/ir/context.rs
index 60ea90c6..4d4a78d2 100644
--- a/src/ir/context.rs
+++ b/src/ir/context.rs
@@ -163,12 +163,53 @@ pub struct BindgenContext<'ctx> {
 }
 
 /// A traversal of whitelisted items.
-pub type WhitelistedItems<'ctx, 'gen> = ItemTraversal<'ctx,
-                                                      'gen,
-                                                      ItemSet,
-                                                      Vec<ItemId>,
-                                                      fn(Edge) -> bool>;
+pub struct WhitelistedItems<'ctx, 'gen>
+    where 'gen: 'ctx
+{
+    ctx: &'ctx BindgenContext<'gen>,
+    traversal: ItemTraversal<'ctx,
+                             'gen,
+                             ItemSet,
+                             Vec<ItemId>,
+                             fn(Edge) -> bool>,
+}
+
+impl<'ctx, 'gen> Iterator for WhitelistedItems<'ctx, 'gen>
+    where 'gen: 'ctx
+{
+    type Item = ItemId;
 
+    fn next(&mut self) -> Option<ItemId> {
+        loop {
+            match self.traversal.next() {
+                None => return None,
+                Some(id) if self.ctx.resolve_item(id).is_hidden(self.ctx) => continue,
+                Some(id) => return Some(id),
+            }
+        }
+    }
+}
+
+impl<'ctx, 'gen> WhitelistedItems<'ctx, 'gen>
+    where 'gen: 'ctx
+{
+    /// Construct a new whitelisted items traversal.
+    pub fn new<R>(ctx: &'ctx BindgenContext<'gen>,
+                  roots: R)
+                  -> WhitelistedItems<'ctx, 'gen>
+        where R: IntoIterator<Item = ItemId>,
+    {
+        let predicate = if ctx.options().whitelist_recursively {
+            traversal::all_edges
+        } else {
+            traversal::no_edges
+        };
+        WhitelistedItems {
+            ctx: ctx,
+            traversal: ItemTraversal::new(ctx, roots, predicate)
+        }
+    }
+}
 impl<'ctx> BindgenContext<'ctx> {
     /// Construct the context for the given `options`.
     pub fn new(options: BindgenOptions) -> Self {
@@ -646,12 +687,21 @@ impl<'ctx> BindgenContext<'ctx> {
         assert!(self.in_codegen_phase(),
                 "We only compute template parameter usage as we enter codegen");
 
+        if self.resolve_item(item).is_hidden(self) {
+            return true;
+        }
+
+        let template_param = template_param.into_resolver()
+            .through_type_refs()
+            .through_type_aliases()
+            .resolve(self)
+            .id();
+
         self.used_template_parameters
             .as_ref()
             .expect("should have found template parameter usage if we're in codegen")
             .get(&item)
-            .map(|items_used_params| items_used_params.contains(&template_param))
-            .unwrap_or_else(|| self.resolve_item(item).is_hidden(self))
+            .map_or(false, |items_used_params| items_used_params.contains(&template_param))
     }
 
     // This deserves a comment. Builtin types don't get a valid declaration, so
@@ -1374,14 +1424,7 @@ impl<'ctx> BindgenContext<'ctx> {
         // unions).
         let mut roots: Vec<_> = roots.collect();
         roots.reverse();
-
-        let predicate = if self.options().whitelist_recursively {
-            traversal::all_edges
-        } else {
-            traversal::no_edges
-        };
-
-        WhitelistedItems::new(self, roots, predicate)
+        WhitelistedItems::new(self, roots)
     }
 
     /// Convenient method for getting the prefix to use for most traits in
diff --git a/src/ir/item.rs b/src/ir/item.rs
index 20451bbc..a60697b8 100644
--- a/src/ir/item.rs
+++ b/src/ir/item.rs
@@ -217,9 +217,12 @@ impl Trace for Item {
     fn trace<T>(&self, ctx: &BindgenContext, tracer: &mut T, _extra: &())
         where T: Tracer,
     {
-        if self.is_hidden(ctx) {
-            return;
-        }
+        // Even if this item is blacklisted/hidden, we want to trace it. It is
+        // traversal iterators' consumers' responsibility to filter items as
+        // needed. Generally, this filtering happens in the implementation of
+        // `Iterator` for `WhitelistedItems`. Fully tracing blacklisted items is
+        // necessary for things like the template parameter usage analysis to
+        // function correctly.
 
         match *self.kind() {
             ItemKind::Type(ref ty) => {
diff --git a/src/ir/named.rs b/src/ir/named.rs
index 55f804ec..943d3a57 100644
--- a/src/ir/named.rs
+++ b/src/ir/named.rs
@@ -128,7 +128,7 @@
 
 use super::context::{BindgenContext, ItemId};
 use super::item::{Item, ItemSet};
-use super::template::{AsNamed, TemplateInstantiation, TemplateParameters};
+use super::template::{TemplateInstantiation, TemplateParameters};
 use super::traversal::{EdgeKind, Trace};
 use super::ty::TypeKind;
 use std::collections::{HashMap, HashSet};
@@ -222,12 +222,18 @@ pub fn analyze<Analysis>(extra: Analysis::Extra) -> Analysis::Output
 /// ```
 ///
 /// * If `inst` is a template instantiation, `inst.args` are the template
-///   instantiation's template arguments, and `inst.def` is the template
-///   definition being instantiated:
+///   instantiation's template arguments, `inst.def` is the template definition
+///   being instantiated, and `inst.def.params` is the template definition's
+///   template parameters, then the instantiation's usage is the union of each
+///   of its arguments' usages *if* the corresponding template parameter is in
+///   turn used by the template definition:
 ///
 /// ```ignore
-/// template_param_usage(inst) =
-///     { T: for T in inst.args, if T in template_param_usage(inst.def) }
+/// template_param_usage(inst) = union(
+///     template_param_usage(inst.args[i])
+///         for i in 0..length(inst.args.length)
+///             if inst.def.params[i] in template_param_usage(inst.def)
+/// )
 /// ```
 ///
 /// * Finally, for all other IR item kinds, we use our lattice's `join`
@@ -243,6 +249,15 @@ pub fn analyze<Analysis>(extra: Analysis::Extra) -> Analysis::Output
 /// 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.
+///
+/// The final wrinkle is handling of blacklisted types. Normally, we say that
+/// the set of whitelisted items is the transitive closure of items explicitly
+/// called out for whitelisting, *without* any items explicitly called out as
+/// blacklisted. However, for the purposes of this analysis's correctness, we
+/// simplify and consider run the analysis on the full transitive closure of
+/// whitelisted items. We do, however, treat instantiations of blacklisted items
+/// specially; see `constrain_instantiation_of_blacklisted_template` and its
+/// documentation for details.
 #[derive(Debug, Clone)]
 pub struct UsedTemplateParameters<'ctx, 'gen>
     where 'gen: 'ctx,
@@ -255,6 +270,9 @@ pub struct UsedTemplateParameters<'ctx, 'gen>
 
     dependencies: HashMap<ItemId, Vec<ItemId>>,
 
+    // The set of whitelisted items, without any blacklisted items reachable
+    // from the whitelisted items which would otherwise be considered
+    // whitelisted as well.
     whitelisted_items: HashSet<ItemId>,
 }
 
@@ -315,19 +333,31 @@ impl<'ctx, 'gen> UsedTemplateParameters<'ctx, 'gen> {
     /// what they'll to with template parameters, but we can push the issue down
     /// the line to them.
     fn constrain_instantiation_of_blacklisted_template(&self,
+                                                       this_id: ItemId,
                                                        used_by_this_id: &mut ItemSet,
                                                        instantiation: &TemplateInstantiation) {
         trace!("    instantiation of blacklisted template, uses all template \
                 arguments");
 
         let args = instantiation.template_arguments()
-            .iter()
-            .filter_map(|a| {
+            .into_iter()
+            .map(|a| {
                 a.into_resolver()
                     .through_type_refs()
                     .through_type_aliases()
                     .resolve(self.ctx)
-                    .as_named(self.ctx, &())
+                    .id()
+            })
+            .filter(|a| *a != this_id)
+            .flat_map(|a| {
+                self.used.get(&a)
+                    .expect("Should have a used entry for the template arg")
+                    .as_ref()
+                    .expect("Because a != this_id, and all used template \
+                             param sets other than this_id's are `Some`, \
+                             a's used template param set should be `Some`")
+                    .iter()
+                    .cloned()
             });
 
         used_by_this_id.extend(args);
@@ -336,6 +366,7 @@ impl<'ctx, 'gen> UsedTemplateParameters<'ctx, 'gen> {
     /// A template instantiation's concrete template argument is only used if
     /// the template definition uses the corresponding template parameter.
     fn constrain_instantiation(&self,
+                               this_id: ItemId,
                                used_by_this_id: &mut ItemSet,
                                instantiation: &TemplateInstantiation) {
         trace!("    template instantiation");
@@ -346,9 +377,14 @@ impl<'ctx, 'gen> UsedTemplateParameters<'ctx, 'gen> {
         let params = decl.self_template_params(self.ctx)
             .unwrap_or(vec![]);
 
-        let used_by_def = self.used[&instantiation.template_definition()]
+        debug_assert!(this_id != instantiation.template_definition());
+        let used_by_def = self.used
+            .get(&instantiation.template_definition())
+            .expect("Should have a used entry for instantiation's template definition")
             .as_ref()
-            .unwrap();
+            .expect("And it should be Some because only this_id's set is None, and an \
+                     instantiation's template definition should never be the \
+                     instantiation itself");
 
         for (arg, param) in args.iter().zip(params.iter()) {
             trace!("      instantiation's argument {:?} is used if definition's \
@@ -362,11 +398,24 @@ impl<'ctx, 'gen> UsedTemplateParameters<'ctx, 'gen> {
                 let arg = arg.into_resolver()
                     .through_type_refs()
                     .through_type_aliases()
-                    .resolve(self.ctx);
-                if let Some(named) = arg.as_named(self.ctx, &()) {
-                    trace!("        arg is a type parameter, marking used");
-                    used_by_this_id.insert(named);
+                    .resolve(self.ctx)
+                    .id();
+
+                if arg == this_id {
+                    continue;
                 }
+
+                let used_by_arg = self.used
+                    .get(&arg)
+                    .expect("Should have a used entry for the template arg")
+                    .as_ref()
+                    .expect("Because arg != this_id, and all used template \
+                             param sets other than this_id's are `Some`, \
+                             arg's used template param set should be \
+                             `Some`")
+                    .iter()
+                    .cloned();
+                used_by_this_id.extend(used_by_arg);
             }
         }
     }
@@ -379,14 +428,14 @@ impl<'ctx, 'gen> UsedTemplateParameters<'ctx, 'gen> {
         item.trace(self.ctx, &mut |sub_id, edge_kind| {
             // Ignore ourselves, since union with ourself is a
             // no-op. Ignore edges that aren't relevant to the
-            // analysis. Ignore edges to blacklisted items.
-            if sub_id == item.id() ||
-                !Self::consider_edge(edge_kind) ||
-                !self.whitelisted_items.contains(&sub_id) {
-                    return;
-                }
+            // analysis.
+            if sub_id == item.id() || !Self::consider_edge(edge_kind) {
+                return;
+            }
 
-            let used_by_sub_id = self.used[&sub_id]
+            let used_by_sub_id = self.used
+                .get(&sub_id)
+                .expect("Should have a used set for the sub_id successor")
                 .as_ref()
                 .expect("Because sub_id != id, and all used template \
                          param sets other than id's are `Some`, \
@@ -415,26 +464,26 @@ impl<'ctx, 'gen> MonotoneFramework for UsedTemplateParameters<'ctx, 'gen> {
         let mut dependencies = HashMap::new();
         let whitelisted_items: HashSet<_> = ctx.whitelisted_items().collect();
 
-        for item in whitelisted_items.iter().cloned() {
+        let whitelisted_and_blacklisted_items: ItemSet = whitelisted_items.iter()
+            .cloned()
+            .flat_map(|i| {
+                let mut reachable = vec![i];
+                i.trace(ctx, &mut |s, _| {
+                    reachable.push(s);
+                }, &());
+                reachable
+            })
+            .collect();
+
+        for item in whitelisted_and_blacklisted_items {
             dependencies.entry(item).or_insert(vec![]);
             used.entry(item).or_insert(Some(ItemSet::new()));
 
             {
                 // We reverse our natural IR graph edges to find dependencies
                 // between nodes.
-                item.trace(ctx, &mut |sub_item, _| {
+                item.trace(ctx, &mut |sub_item: ItemId, _| {
                     used.entry(sub_item).or_insert(Some(ItemSet::new()));
-
-                    // We won't be generating code for items that aren't
-                    // whitelisted, so don't bother keeping track of their
-                    // template parameters. But isn't whitelisting the
-                    // transitive closure of reachable items from the explicitly
-                    // whitelisted items? Usually! The exception is explicitly
-                    // blacklisted items.
-                    if !whitelisted_items.contains(&sub_item) {
-                        return;
-                    }
-
                     dependencies.entry(sub_item)
                         .or_insert(vec![])
                         .push(item);
@@ -458,12 +507,24 @@ impl<'ctx, 'gen> MonotoneFramework for UsedTemplateParameters<'ctx, 'gen> {
                             .unwrap_or(vec![]);
 
                         for (arg, param) in args.iter().zip(params.iter()) {
-                            used.entry(*arg).or_insert(Some(ItemSet::new()));
-                            used.entry(*param).or_insert(Some(ItemSet::new()));
-
-                            dependencies.entry(*arg)
+                            let arg = arg.into_resolver()
+                                .through_type_aliases()
+                                .through_type_refs()
+                                .resolve(ctx)
+                                .id();
+
+                            let param = param.into_resolver()
+                                .through_type_aliases()
+                                .through_type_refs()
+                                .resolve(ctx)
+                                .id();
+
+                            used.entry(arg).or_insert(Some(ItemSet::new()));
+                            used.entry(param).or_insert(Some(ItemSet::new()));
+
+                            dependencies.entry(arg)
                                 .or_insert(vec![])
-                                .push(*param);
+                                .push(param);
                         }
                     }
                     _ => {}
@@ -475,21 +536,20 @@ impl<'ctx, 'gen> MonotoneFramework for UsedTemplateParameters<'ctx, 'gen> {
             // item, as well as all explicitly blacklisted items that are
             // reachable from whitelisted items.
             //
+            // Invariant: the `dependencies` map has an entry for every
+            // whitelisted item.
+            //
             // (This is so that every item we call `constrain` on is guaranteed
             // to have a set of template parameters, and we can allow
             // blacklisted templates to use all of their parameters).
             for item in whitelisted_items.iter() {
                 extra_assert!(used.contains_key(item));
+                extra_assert!(dependencies.contains_key(item));
                 item.trace(ctx, &mut |sub_item, _| {
                     extra_assert!(used.contains_key(&sub_item));
+                    extra_assert!(dependencies.contains_key(&sub_item));
                 }, &())
             }
-
-            // Invariant: the `dependencies` map has an entry for every
-            // whitelisted item.
-            for item in whitelisted_items.iter() {
-                extra_assert!(dependencies.contains_key(item));
-            }
         }
 
         UsedTemplateParameters {
@@ -501,7 +561,18 @@ impl<'ctx, 'gen> MonotoneFramework for UsedTemplateParameters<'ctx, 'gen> {
     }
 
     fn initial_worklist(&self) -> Vec<ItemId> {
-        self.ctx.whitelisted_items().collect()
+        // The transitive closure of all whitelisted items, including explicitly
+        // blacklisted items.
+        self.ctx
+            .whitelisted_items()
+            .flat_map(|i| {
+                let mut reachable = vec![i];
+                i.trace(self.ctx, &mut |s, _| {
+                    reachable.push(s);
+                }, &());
+                reachable
+            })
+            .collect()
     }
 
     fn constrain(&mut self, id: ItemId) -> bool {
@@ -532,9 +603,10 @@ impl<'ctx, 'gen> MonotoneFramework for UsedTemplateParameters<'ctx, 'gen> {
             // template definition uses the corresponding template parameter.
             Some(&TypeKind::TemplateInstantiation(ref inst)) => {
                 if self.whitelisted_items.contains(&inst.template_definition()) {
-                    self.constrain_instantiation(&mut used_by_this_id, inst);
+                    self.constrain_instantiation(id, &mut used_by_this_id, inst);
                 } else {
-                    self.constrain_instantiation_of_blacklisted_template(&mut used_by_this_id,
+                    self.constrain_instantiation_of_blacklisted_template(id,
+                                                                         &mut used_by_this_id,
                                                                          inst);
                 }
             }
diff --git a/src/ir/traversal.rs b/src/ir/traversal.rs
index 95d2a456..0072e6b2 100644
--- a/src/ir/traversal.rs
+++ b/src/ir/traversal.rs
@@ -25,16 +25,6 @@ impl Edge {
             kind: kind,
         }
     }
-
-    /// Get the item that this edge is pointing to.
-    pub fn to(&self) -> ItemId {
-        self.to
-    }
-
-    /// Get the kind of edge that this is.
-    pub fn kind(&self) -> EdgeKind {
-        self.kind
-    }
 }
 
 impl Into<ItemId> for Edge {
diff --git a/tests/expectations/tests/issue-662-cannot-find-T-in-this-scope.rs b/tests/expectations/tests/issue-662-cannot-find-T-in-this-scope.rs
new file mode 100644
index 00000000..0c16b235
--- /dev/null
+++ b/tests/expectations/tests/issue-662-cannot-find-T-in-this-scope.rs
@@ -0,0 +1,30 @@
+/* automatically generated by rust-bindgen */
+
+
+#![allow(non_snake_case)]
+
+
+#[repr(C)]
+#[derive(Debug, Copy, Clone)]
+pub struct RefPtr<T> {
+    pub a: T,
+}
+impl <T> Default for RefPtr<T> {
+    fn default() -> Self { unsafe { ::std::mem::zeroed() } }
+}
+#[repr(C)]
+#[derive(Debug, Copy, Clone)]
+pub struct nsMainThreadPtrHolder<T> {
+    pub a: T,
+}
+impl <T> Default for nsMainThreadPtrHolder<T> {
+    fn default() -> Self { unsafe { ::std::mem::zeroed() } }
+}
+#[repr(C)]
+#[derive(Debug, Copy, Clone)]
+pub struct nsMainThreadPtrHandle<T> {
+    pub mPtr: RefPtr<nsMainThreadPtrHolder<T>>,
+}
+impl <T> Default for nsMainThreadPtrHandle<T> {
+    fn default() -> Self { unsafe { ::std::mem::zeroed() } }
+}
diff --git a/tests/expectations/tests/issue-662-part-2.rs b/tests/expectations/tests/issue-662-part-2.rs
new file mode 100644
index 00000000..fa80c5fe
--- /dev/null
+++ b/tests/expectations/tests/issue-662-part-2.rs
@@ -0,0 +1,23 @@
+/* automatically generated by rust-bindgen */
+
+
+#![allow(non_snake_case)]
+
+#[derive(Clone, Copy, Debug)] pub struct RefPtr<T>(T);
+
+#[repr(C)]
+#[derive(Debug, Copy, Clone)]
+pub struct nsMainThreadPtrHolder<T> {
+    pub a: T,
+}
+impl <T> Default for nsMainThreadPtrHolder<T> {
+    fn default() -> Self { unsafe { ::std::mem::zeroed() } }
+}
+#[repr(C)]
+#[derive(Debug, Copy, Clone)]
+pub struct nsMainThreadPtrHandle<U> {
+    pub mPtr: RefPtr<nsMainThreadPtrHolder<U>>,
+}
+impl <U> Default for nsMainThreadPtrHandle<U> {
+    fn default() -> Self { unsafe { ::std::mem::zeroed() } }
+}
diff --git a/tests/headers/issue-662-cannot-find-T-in-this-scope.hpp b/tests/headers/issue-662-cannot-find-T-in-this-scope.hpp
new file mode 100644
index 00000000..6b3f928b
--- /dev/null
+++ b/tests/headers/issue-662-cannot-find-T-in-this-scope.hpp
@@ -0,0 +1,7 @@
+// bindgen-flags: -- --std=c++14
+
+template <class T> class RefPtr { T a; };
+template <class T> class nsMainThreadPtrHolder { T a; };
+template <class T> class nsMainThreadPtrHandle {
+    RefPtr<nsMainThreadPtrHolder<T>> mPtr;
+};
diff --git a/tests/headers/issue-662-part-2.hpp b/tests/headers/issue-662-part-2.hpp
new file mode 100644
index 00000000..84edb397
--- /dev/null
+++ b/tests/headers/issue-662-part-2.hpp
@@ -0,0 +1,11 @@
+// bindgen-flags: --blacklist-type RefPtr --raw-line '#[derive(Clone, Copy, Debug)] pub struct RefPtr<T>(T);' -- --std=c++14
+
+// This is pretty much the same as the other issue 662 test case, but this time
+// we blacklist RefPtr to exercise the instantiation-of-a-blacklisted-template
+// path in the template analysis.
+
+template <class> class RefPtr {};
+template <class T> class nsMainThreadPtrHolder { T a; };
+template <class U> class nsMainThreadPtrHandle {
+    RefPtr<nsMainThreadPtrHolder<U>> mPtr;
+};
diff --git a/tests/test-one.sh b/tests/test-one.sh
index c7f9b2ae..cbb89eaf 100755
--- a/tests/test-one.sh
+++ b/tests/test-one.sh
@@ -18,8 +18,8 @@ export RUST_BACKTRACE=1
 # Grab the first match
 TEST=$(find ./tests/headers -type f -iname "*$1*" | head -n 1)
 
-BINDINGS=$(mktemp -t bindings_XXXXXX.rs)
-TEST_BINDINGS_BINARY=$(mktemp -t bindings.XXXXX)
+BINDINGS=$(mktemp -t bindings.rs.XXXXXX)
+TEST_BINDINGS_BINARY=$(mktemp -t bindings.XXXXXX)
 
 FLAGS="$(grep "// bindgen-flags: " "$TEST")"
 FLAGS="${FLAGS/\/\/ bindgen\-flags:/}"
@@ -41,7 +41,7 @@ echo "=== Generated bindings =================================================="
 cat "$BINDINGS"
 
 echo "=== Building bindings ==================================================="
-rustc --test -o "$TEST_BINDINGS_BINARY" "$BINDINGS"
+rustc --test -o "$TEST_BINDINGS_BINARY" "$BINDINGS" --crate-name bindgen_test_one
 
 echo "=== Testing bindings ===================================================="
 "$TEST_BINDINGS_BINARY"