Auto merge of #932 - bd339:has_destructor_fp, r=fitzgen

Rewrite `has destructor` analysis as a fixed-point analysis

Fixes #927 . Note that this creates a dependency between the "cannot derive copy" and "has destructor" analysis, i.e. the "has destructor" analysis must run before the "cannot derive copy" analysis, because "cannot derive copy" needs the results of "has destructor".

7 files changed, 213 insertions, 73 deletions

diff --git a/src/ir/analysis/derive_copy.rs b/src/ir/analysis/derive_copy.rs
index de06f81c..c108a961 100644
--- a/src/ir/analysis/derive_copy.rs
+++ b/src/ir/analysis/derive_copy.rs
@@ -208,7 +208,7 @@ impl<'ctx, 'gen> MonotoneFramework for CannotDeriveCopy<'ctx, 'gen> {
                 // NOTE: Take into account that while unions in C and C++ are copied by
                 // default, the may have an explicit destructor in C++, so we can't
                 // defer this check just for the union case.
-                if info.has_destructor(self.ctx) {
+                if self.ctx.lookup_item_id_has_destructor(&id) {
                     trace!("    comp has destructor which cannot derive copy");
                     return self.insert(id);
                 }
diff --git a/src/ir/analysis/has_destructor.rs b/src/ir/analysis/has_destructor.rs
new file mode 100644
index 00000000..b37dbaaa
--- /dev/null
+++ b/src/ir/analysis/has_destructor.rs
@@ -0,0 +1,179 @@
+//! Determining which types have destructors
+
+use super::{ConstrainResult, MonotoneFramework, generate_dependencies};
+use ir::context::{BindgenContext, ItemId};
+use ir::traversal::EdgeKind;
+use ir::comp::{CompKind, Field, FieldMethods};
+use ir::ty::TypeKind;
+use std::collections::HashMap;
+use std::collections::HashSet;
+
+/// An analysis that finds for each IR item whether it has a destructor or not
+///
+/// We use the monotone function `has destructor`, defined as follows:
+///
+/// * If T is a type alias, a templated alias, or an indirection to another type,
+///   T has a destructor if the type T refers to has a destructor.
+/// * If T is a compound type, T has a destructor if we saw a destructor when parsing it,
+///   or if it's a struct, T has a destructor if any of its base members has a destructor,
+///   or if any of its fields have a destructor.
+/// * If T is an instantiation of an abstract template definition, T has
+///   a destructor if its template definition has a destructor,
+///   or if any of the template arguments has a destructor.
+/// * If T is the type of a field, that field has a destructor if it's not a bitfield,
+///   and if T has a destructor.
+#[derive(Debug, Clone)]
+pub struct HasDestructorAnalysis<'ctx, 'gen>
+where
+    'gen: 'ctx,
+{
+    ctx: &'ctx BindgenContext<'gen>,
+
+    // The incremental result of this analysis's computation. Everything in this
+    // set definitely has a destructor.
+    have_destructor: HashSet<ItemId>,
+
+    // Dependencies saying that if a key ItemId has been inserted into the
+    // `have_destructor` set, then each of the ids in Vec<ItemId> need to be
+    // considered again.
+    //
+    // This is a subset of the natural IR graph with reversed edges, where we
+    // only include the edges from the IR graph that can affect whether a type
+    // has a destructor or not.
+    dependencies: HashMap<ItemId, Vec<ItemId>>,
+}
+
+impl<'ctx, 'gen> HasDestructorAnalysis<'ctx, 'gen> {
+    fn consider_edge(kind: EdgeKind) -> bool {
+        match kind {
+            // These are the only edges that can affect whether a type has a
+            // destructor or not.
+            EdgeKind::TypeReference |
+            EdgeKind::BaseMember |
+            EdgeKind::Field |
+            EdgeKind::TemplateArgument |
+            EdgeKind::TemplateDeclaration => true,
+            _ => false,
+        }
+    }
+
+    fn insert(&mut self, id: ItemId) -> ConstrainResult {
+        let was_not_already_in_set = self.have_destructor.insert(id);
+        assert!(
+            was_not_already_in_set,
+            "We shouldn't try and insert {:?} twice because if it was \
+             already in the set, `constrain` should have exited early.",
+            id
+        );
+        ConstrainResult::Changed
+    }
+}
+
+impl<'ctx, 'gen> MonotoneFramework for HasDestructorAnalysis<'ctx, 'gen> {
+    type Node = ItemId;
+    type Extra = &'ctx BindgenContext<'gen>;
+    type Output = HashSet<ItemId>;
+
+    fn new(ctx: &'ctx BindgenContext<'gen>) -> Self {
+        let have_destructor = HashSet::new();
+        let dependencies = generate_dependencies(ctx, Self::consider_edge);
+
+        HasDestructorAnalysis {
+            ctx,
+            have_destructor,
+            dependencies,
+        }
+    }
+
+    fn initial_worklist(&self) -> Vec<ItemId> {
+        self.ctx.whitelisted_items().iter().cloned().collect()
+    }
+
+    fn constrain(&mut self, id: ItemId) -> ConstrainResult {
+        if self.have_destructor.contains(&id) {
+            // We've already computed that this type has a destructor and that can't
+            // change.
+            return ConstrainResult::Same;
+        }
+
+        let item = self.ctx.resolve_item(id);
+        let ty = match item.as_type() {
+            None => return ConstrainResult::Same,
+            Some(ty) => ty,
+        };
+
+        match *ty.kind() {
+            TypeKind::TemplateAlias(t, _) |
+            TypeKind::Alias(t) |
+            TypeKind::ResolvedTypeRef(t) => {
+                if self.have_destructor.contains(&t) {
+                    self.insert(id)
+                } else {
+                    ConstrainResult::Same
+                }
+            }
+
+            TypeKind::Comp(ref info) => {
+                if info.has_own_destructor() {
+                    return self.insert(id);
+                }
+
+                match info.kind() {
+                    CompKind::Union => ConstrainResult::Same,
+                    CompKind::Struct => {
+                        let base_or_field_destructor =
+                            info.base_members().iter().any(|base| {
+                                self.have_destructor.contains(&base.ty)
+                            }) ||
+                            info.fields().iter().any(|field| {
+                                match *field {
+                                    Field::DataMember(ref data) =>
+                                        self.have_destructor.contains(&data.ty()),
+                                    Field::Bitfields(_) => false
+                                }
+                            });
+                        if base_or_field_destructor {
+                            self.insert(id)
+                        } else {
+                            ConstrainResult::Same
+                        }
+                    }
+                }
+            }
+
+            TypeKind::TemplateInstantiation(ref inst) => {
+                let definition_or_arg_destructor =
+                    self.have_destructor.contains(&inst.template_definition())
+                    ||
+                    inst.template_arguments().iter().any(|arg| {
+                        self.have_destructor.contains(arg)
+                    });
+                if definition_or_arg_destructor {
+                    self.insert(id)
+                } else {
+                    ConstrainResult::Same
+                }
+            }
+
+            _ => ConstrainResult::Same,
+        }
+    }
+
+    fn each_depending_on<F>(&self, id: ItemId, mut f: F)
+    where
+        F: FnMut(ItemId),
+    {
+        if let Some(edges) = self.dependencies.get(&id) {
+            for item in edges {
+                trace!("enqueue {:?} into worklist", item);
+                f(*item);
+            }
+        }
+    }
+}
+
+impl<'ctx, 'gen> From<HasDestructorAnalysis<'ctx, 'gen>> for HashSet<ItemId> {
+    fn from(analysis: HasDestructorAnalysis<'ctx, 'gen>) -> Self {
+        analysis.have_destructor
+    }
+}
diff --git a/src/ir/analysis/mod.rs b/src/ir/analysis/mod.rs
index 42aa4a8f..ab19cb4f 100644
--- a/src/ir/analysis/mod.rs
+++ b/src/ir/analysis/mod.rs
@@ -45,6 +45,8 @@ pub use self::derive_debug::CannotDeriveDebug;
 mod has_vtable;
 pub use self::has_vtable::HasVtable;
 pub use self::has_vtable::HasVtableAnalysis;
+mod has_destructor;
+pub use self::has_destructor::HasDestructorAnalysis;
 mod derive_default;
 pub use self::derive_default::CannotDeriveDefault;
 mod derive_copy;
diff --git a/src/ir/comp.rs b/src/ir/comp.rs
index 1a02feb5..bbccd06a 100644
--- a/src/ir/comp.rs
+++ b/src/ir/comp.rs
@@ -13,7 +13,6 @@ use codegen::struct_layout::{align_to, bytes_from_bits_pow2};
 use ir::derive::CanDeriveCopy;
 use parse::{ClangItemParser, ParseError};
 use peeking_take_while::PeekableExt;
-use std::cell::Cell;
 use std::cmp;
 use std::io;
 use std::mem;
@@ -170,18 +169,6 @@ pub enum Field {
 }
 
 impl Field {
-    fn has_destructor(&self, ctx: &BindgenContext) -> bool {
-        match *self {
-            Field::DataMember(ref data) => {
-                ctx.resolve_type(data.ty).has_destructor(ctx)
-            }
-            // Bitfields may not be of a type that has a destructor.
-            Field::Bitfields(BitfieldUnit {
-                                 ..
-                             }) => false,
-        }
-    }
-
     /// Get this field's layout.
     pub fn layout(&self, ctx: &BindgenContext) -> Option<Layout> {
         match *self {
@@ -865,10 +852,6 @@ pub struct CompInfo {
     /// and pray, or behave as an opaque type.
     found_unknown_attr: bool,
 
-    /// Used to detect if we've run in a has_destructor cycle while cycling
-    /// around the template arguments.
-    detect_has_destructor_cycle: Cell<bool>,
-
     /// Used to indicate when a struct has been forward declared. Usually used
     /// in headers so that APIs can't modify them directly.
     is_forward_declaration: bool,
@@ -893,7 +876,6 @@ impl CompInfo {
             has_non_type_template_params: false,
             packed: false,
             found_unknown_attr: false,
-            detect_has_destructor_cycle: Cell::new(false),
             is_forward_declaration: false,
         }
     }
@@ -909,34 +891,6 @@ impl CompInfo {
             })
     }
 
-    /// Does this compound type have a destructor?
-    pub fn has_destructor(&self, ctx: &BindgenContext) -> bool {
-        if self.detect_has_destructor_cycle.get() {
-            warn!("Cycle detected looking for destructors");
-            // Assume no destructor, since we don't have an explicit one.
-            return false;
-        }
-
-        self.detect_has_destructor_cycle.set(true);
-
-        let has_destructor = self.has_destructor ||
-            match self.kind {
-                CompKind::Union => false,
-                CompKind::Struct => {
-                    self.base_members.iter().any(|base| {
-                        ctx.resolve_type(base.ty).has_destructor(ctx)
-                    }) ||
-                        self.fields().iter().any(
-                            |field| field.has_destructor(ctx),
-                        )
-                }
-            };
-
-        self.detect_has_destructor_cycle.set(false);
-
-        has_destructor
-    }
-
     /// Compute the layout of this type.
     ///
     /// This is called as a fallback under some circumstances where LLVM doesn't
@@ -989,6 +943,11 @@ impl CompInfo {
         return self.has_own_virtual_method;
     }
 
+    /// Did we see a destructor when parsing this type?
+    pub fn has_own_destructor(&self) -> bool {
+        self.has_destructor
+    }
+
     /// Get this type's set of methods.
     pub fn methods(&self) -> &[Method] {
         &self.methods
diff --git a/src/ir/context.rs b/src/ir/context.rs
index 67245c29..3f503fdd 100644
--- a/src/ir/context.rs
+++ b/src/ir/context.rs
@@ -3,8 +3,8 @@
 use super::analysis::{CannotDeriveCopy, CannotDeriveDebug,
                       CannotDeriveDefault, CannotDeriveHash,
                       CannotDerivePartialEq, HasTypeParameterInArray,
-                      HasVtableAnalysis, UsedTemplateParameters, HasFloat,
-                      analyze};
+                      HasVtableAnalysis, HasDestructorAnalysis, UsedTemplateParameters,
+                      HasFloat, analyze};
 use super::derive::{CanDeriveCopy, CanDeriveDebug, CanDeriveDefault,
                     CanDeriveHash, CanDerivePartialEq, CanDeriveEq};
 use super::int::IntKind;
@@ -239,6 +239,12 @@ pub struct BindgenContext<'ctx> {
     /// before that and `Some` after.
     have_vtable: Option<HashSet<ItemId>>,
 
+    /// The set of (`ItemId's of`) types that has destructor.
+    ///
+    /// Populated when we enter codegen by `compute_has_destructor`; always `None`
+    /// before that and `Some` after.
+    have_destructor: Option<HashSet<ItemId>>,
+
     /// The set of (`ItemId's of`) types that has array.
     ///
     /// Populated when we enter codegen by `compute_has_type_param_in_array`; always `None`
@@ -390,6 +396,7 @@ impl<'ctx> BindgenContext<'ctx> {
             cannot_derive_hash: None,
             cannot_derive_partialeq: None,
             have_vtable: None,
+            have_destructor: None,
             has_type_param_in_array: None,
             has_float: None,
         };
@@ -901,6 +908,7 @@ impl<'ctx> BindgenContext<'ctx> {
         self.assert_every_item_in_a_module();
 
         self.compute_has_vtable();
+        self.compute_has_destructor();
         self.find_used_template_parameters();
         self.compute_cannot_derive_debug();
         self.compute_cannot_derive_default();
@@ -1001,6 +1009,22 @@ impl<'ctx> BindgenContext<'ctx> {
         self.have_vtable.as_ref().unwrap().contains(id)
     }
 
+    /// Compute whether the type has a destructor.
+    fn compute_has_destructor(&mut self) {
+        assert!(self.have_destructor.is_none());
+        self.have_destructor = Some(analyze::<HasDestructorAnalysis>(self));
+    }
+
+    /// Look up whether the item with `id` has a destructor.
+    pub fn lookup_item_id_has_destructor(&self, id: &ItemId) -> bool {
+        assert!(
+            self.in_codegen_phase(),
+            "We only compute destructors when we enter codegen"
+        );
+
+        self.have_destructor.as_ref().unwrap().contains(id)
+    }
+
     fn find_used_template_parameters(&mut self) {
         if self.options.whitelist_recursively {
             let used_params = analyze::<UsedTemplateParameters>(self);
diff --git a/src/ir/template.rs b/src/ir/template.rs
index 8fe4c704..c1650abc 100644
--- a/src/ir/template.rs
+++ b/src/ir/template.rs
@@ -309,14 +309,6 @@ impl TemplateInstantiation {
             template_args,
         ))
     }
-
-    /// Does this instantiation have a destructor?
-    pub fn has_destructor(&self, ctx: &BindgenContext) -> bool {
-        ctx.resolve_type(self.definition).has_destructor(ctx) ||
-            self.args.iter().any(|arg| {
-                ctx.resolve_type(*arg).has_destructor(ctx)
-            })
-    }
 }
 
 impl IsOpaque for TemplateInstantiation {
diff --git a/src/ir/ty.rs b/src/ir/ty.rs
index bd2a54ef..da1cc6d7 100644
--- a/src/ir/ty.rs
+++ b/src/ir/ty.rs
@@ -237,22 +237,6 @@ impl Type {
         })
     }
 
-    /// Returns whether this type has a destructor.
-    pub fn has_destructor(&self, ctx: &BindgenContext) -> bool {
-        match self.kind {
-            TypeKind::TemplateAlias(t, _) |
-            TypeKind::Alias(t) |
-            TypeKind::ResolvedTypeRef(t) => {
-                ctx.resolve_type(t).has_destructor(ctx)
-            }
-            TypeKind::TemplateInstantiation(ref inst) => {
-                inst.has_destructor(ctx)
-            }
-            TypeKind::Comp(ref info) => info.has_destructor(ctx),
-            _ => false,
-        }
-    }
-
     /// Whether this named type is an invalid C++ identifier. This is done to
     /// avoid generating invalid code with some cases we can't handle, see:
     ///