1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

use dep_graph::DepNode;
use hir::def_id::{DefId, LOCAL_CRATE};
use traits::{self, specialization_graph};
use ty;
use ty::fast_reject;
use ty::{Ty, TyCtxt, TraitRef};
use std::cell::{Cell, RefCell};
use hir;
use util::nodemap::FxHashMap;

use syntax::ast;
use syntax_pos::DUMMY_SP;

/// A trait's definition with type information.
pub struct TraitDef {
    pub def_id: DefId,

    pub unsafety: hir::Unsafety,

    /// If `true`, then this trait had the `#[rustc_paren_sugar]`
    /// attribute, indicating that it should be used with `Foo()`
    /// sugar. This is a temporary thing -- eventually any trait will
    /// be usable with the sugar (or without it).
    pub paren_sugar: bool,

    // Impls of a trait. To allow for quicker lookup, the impls are indexed by a
    // simplified version of their `Self` type: impls with a simplifiable `Self`
    // are stored in `nonblanket_impls` keyed by it, while all other impls are
    // stored in `blanket_impls`.
    //
    // A similar division is used within `specialization_graph`, but the ones
    // here are (1) stored as a flat list for the trait and (2) populated prior
    // to -- and used while -- determining specialization order.
    //
    // FIXME: solve the reentrancy issues and remove these lists in favor of the
    // ones in `specialization_graph`.
    //
    // These lists are tracked by `DepNode::TraitImpls`; we don't use
    // a DepTrackingMap but instead have the `TraitDef` insert the
    // required reads/writes.

    /// Impls of the trait.
    nonblanket_impls: RefCell<
        FxHashMap<fast_reject::SimplifiedType, Vec<DefId>>
    >,

    /// Blanket impls associated with the trait.
    blanket_impls: RefCell<Vec<DefId>>,

    /// The specialization order for impls of this trait.
    pub specialization_graph: RefCell<traits::specialization_graph::Graph>,

    /// Various flags
    pub flags: Cell<TraitFlags>,

    /// The number of impls we've added from the local crate.
    /// When this number matches up the list in the HIR map,
    /// we're done, and the specialization graph is correct.
    local_impl_count: Cell<usize>,

    /// The ICH of this trait's DefPath, cached here so it doesn't have to be
    /// recomputed all the time.
    pub def_path_hash: u64,
}

impl<'a, 'gcx, 'tcx> TraitDef {
    pub fn new(def_id: DefId,
               unsafety: hir::Unsafety,
               paren_sugar: bool,
               def_path_hash: u64)
               -> TraitDef {
        TraitDef {
            def_id: def_id,
            paren_sugar: paren_sugar,
            unsafety: unsafety,
            nonblanket_impls: RefCell::new(FxHashMap()),
            blanket_impls: RefCell::new(vec![]),
            flags: Cell::new(ty::TraitFlags::NO_TRAIT_FLAGS),
            local_impl_count: Cell::new(0),
            specialization_graph: RefCell::new(traits::specialization_graph::Graph::new()),
            def_path_hash: def_path_hash,
        }
    }

    // returns None if not yet calculated
    pub fn object_safety(&self) -> Option<bool> {
        if self.flags.get().intersects(TraitFlags::OBJECT_SAFETY_VALID) {
            Some(self.flags.get().intersects(TraitFlags::IS_OBJECT_SAFE))
        } else {
            None
        }
    }

    pub fn set_object_safety(&self, is_safe: bool) {
        assert!(self.object_safety().map(|cs| cs == is_safe).unwrap_or(true));
        self.flags.set(
            self.flags.get() | if is_safe {
                TraitFlags::OBJECT_SAFETY_VALID | TraitFlags::IS_OBJECT_SAFE
            } else {
                TraitFlags::OBJECT_SAFETY_VALID
            }
        );
    }

    fn write_trait_impls(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) {
        tcx.dep_graph.write(DepNode::TraitImpls(self.def_id));
    }

    fn read_trait_impls(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) {
        tcx.dep_graph.read(DepNode::TraitImpls(self.def_id));
    }

    /// Records a basic trait-to-implementation mapping.
    ///
    /// Returns `true` iff the impl has not previously been recorded.
    fn record_impl(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
                   impl_def_id: DefId,
                   impl_trait_ref: TraitRef<'tcx>)
                   -> bool {
        debug!("TraitDef::record_impl for {:?}, from {:?}",
               self, impl_trait_ref);

        // Record the write into the impl set, but only for local
        // impls: external impls are handled differently.
        if impl_def_id.is_local() {
            self.write_trait_impls(tcx);
        }

        // We don't want to borrow_mut after we already populated all impls,
        // so check if an impl is present with an immutable borrow first.
        if let Some(sty) = fast_reject::simplify_type(tcx,
                                                      impl_trait_ref.self_ty(), false) {
            if let Some(is) = self.nonblanket_impls.borrow().get(&sty) {
                if is.contains(&impl_def_id) {
                    return false; // duplicate - skip
                }
            }

            self.nonblanket_impls.borrow_mut().entry(sty).or_insert(vec![]).push(impl_def_id)
        } else {
            if self.blanket_impls.borrow().contains(&impl_def_id) {
                return false; // duplicate - skip
            }
            self.blanket_impls.borrow_mut().push(impl_def_id)
        }

        true
    }

    /// Records a trait-to-implementation mapping for a crate-local impl.
    pub fn record_local_impl(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
                             impl_def_id: DefId,
                             impl_trait_ref: TraitRef<'tcx>) {
        assert!(impl_def_id.is_local());
        let was_new = self.record_impl(tcx, impl_def_id, impl_trait_ref);
        assert!(was_new);

        self.local_impl_count.set(self.local_impl_count.get() + 1);
    }

    /// Records a trait-to-implementation mapping.
    pub fn record_has_default_impl(&self) {
        self.flags.set(self.flags.get() | TraitFlags::HAS_DEFAULT_IMPL);
    }

    /// Records a trait-to-implementation mapping for a non-local impl.
    ///
    /// The `parent_impl` is the immediately-less-specialized impl, or the
    /// trait's def ID if the impl is not a specialization -- information that
    /// should be pulled from the metadata.
    pub fn record_remote_impl(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>,
                              impl_def_id: DefId,
                              impl_trait_ref: TraitRef<'tcx>,
                              parent_impl: DefId) {
        assert!(!impl_def_id.is_local());

        // if the impl has not previously been recorded
        if self.record_impl(tcx, impl_def_id, impl_trait_ref) {
            // if the impl is non-local, it's placed directly into the
            // specialization graph using parent information drawn from metadata.
            self.specialization_graph.borrow_mut()
                .record_impl_from_cstore(tcx, parent_impl, impl_def_id)
        }
    }

    /// Adds a local impl into the specialization graph, returning an error with
    /// overlap information if the impl overlaps but does not specialize an
    /// existing impl.
    pub fn add_impl_for_specialization(&self,
                                       tcx: TyCtxt<'a, 'gcx, 'tcx>,
                                       impl_def_id: DefId)
                                       -> Result<(), traits::OverlapError> {
        assert!(impl_def_id.is_local());

        self.specialization_graph.borrow_mut()
            .insert(tcx, impl_def_id)
    }

    pub fn ancestors(&'a self, of_impl: DefId) -> specialization_graph::Ancestors<'a> {
        specialization_graph::ancestors(self, of_impl)
    }

    /// Whether the impl set and specialization graphs are complete.
    pub fn is_complete(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> bool {
        tcx.populate_implementations_for_trait_if_necessary(self.def_id);
        ty::queries::coherent_trait::try_get(tcx, DUMMY_SP, (LOCAL_CRATE, self.def_id)).is_ok()
    }

    /// If any local impls haven't been added yet, returns
    /// Some(list of local impls for this trait).
    fn missing_local_impls(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>)
                           -> Option<&'gcx [ast::NodeId]> {
        if self.flags.get().intersects(TraitFlags::HAS_LOCAL_IMPLS) {
            return None;
        }

        if self.is_complete(tcx) {
            self.flags.set(self.flags.get() | TraitFlags::HAS_LOCAL_IMPLS);
            return None;
        }

        let impls = tcx.hir.trait_impls(self.def_id);
        assert!(self.local_impl_count.get() <= impls.len());
        if self.local_impl_count.get() == impls.len() {
            self.flags.set(self.flags.get() | TraitFlags::HAS_LOCAL_IMPLS);
            return None;
        }

        Some(impls)
    }

    pub fn for_each_impl<F: FnMut(DefId)>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>, mut f: F) {
        self.read_trait_impls(tcx);
        tcx.populate_implementations_for_trait_if_necessary(self.def_id);

        let local_impls = self.missing_local_impls(tcx);
        if let Some(impls) = local_impls {
            for &id in impls {
                f(tcx.hir.local_def_id(id));
            }
        }
        let mut f = |def_id: DefId| {
            if !(local_impls.is_some() && def_id.is_local()) {
                f(def_id);
            }
        };

        for &impl_def_id in self.blanket_impls.borrow().iter() {
            f(impl_def_id);
        }

        for v in self.nonblanket_impls.borrow().values() {
            for &impl_def_id in v {
                f(impl_def_id);
            }
        }
    }

    /// Iterate over every impl that could possibly match the
    /// self-type `self_ty`.
    pub fn for_each_relevant_impl<F: FnMut(DefId)>(&self,
                                                   tcx: TyCtxt<'a, 'gcx, 'tcx>,
                                                   self_ty: Ty<'tcx>,
                                                   mut f: F)
    {
        self.read_trait_impls(tcx);
        tcx.populate_implementations_for_trait_if_necessary(self.def_id);

        let local_impls = self.missing_local_impls(tcx);
        if let Some(impls) = local_impls {
            for &id in impls {
                f(tcx.hir.local_def_id(id));
            }
        }
        let mut f = |def_id: DefId| {
            if !(local_impls.is_some() && def_id.is_local()) {
                f(def_id);
            }
        };

        for &impl_def_id in self.blanket_impls.borrow().iter() {
            f(impl_def_id);
        }

        // simplify_type(.., false) basically replaces type parameters and
        // projections with infer-variables. This is, of course, done on
        // the impl trait-ref when it is instantiated, but not on the
        // predicate trait-ref which is passed here.
        //
        // for example, if we match `S: Copy` against an impl like
        // `impl<T:Copy> Copy for Option<T>`, we replace the type variable
        // in `Option<T>` with an infer variable, to `Option<_>` (this
        // doesn't actually change fast_reject output), but we don't
        // replace `S` with anything - this impl of course can't be
        // selected, and as there are hundreds of similar impls,
        // considering them would significantly harm performance.
        if let Some(simp) = fast_reject::simplify_type(tcx, self_ty, true) {
            if let Some(impls) = self.nonblanket_impls.borrow().get(&simp) {
                for &impl_def_id in impls {
                    f(impl_def_id);
                }
            }
        } else {
            for v in self.nonblanket_impls.borrow().values() {
                for &impl_def_id in v {
                    f(impl_def_id);
                }
            }
        }
    }
}

bitflags! {
    flags TraitFlags: u32 {
        const NO_TRAIT_FLAGS        = 0,
        const HAS_DEFAULT_IMPL      = 1 << 0,
        const IS_OBJECT_SAFE        = 1 << 1,
        const OBJECT_SAFETY_VALID   = 1 << 2,
        const HAS_REMOTE_IMPLS      = 1 << 3,
        const HAS_LOCAL_IMPLS       = 1 << 4,
    }
}