src/librustc/hir/map/definitions.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use middle::cstore::LOCAL_CRATE;
  12 use hir::def_id::{DefId, DefIndex};
  13 use hir::map::def_collector::DefCollector;
  14 use rustc_data_structures::fnv::FnvHashMap;
  15 use std::fmt::Write;
  16 use std::hash::{Hash, Hasher, SipHasher};
  17 use syntax::{ast, visit};
  18 use syntax::parse::token::InternedString;
  19 use ty::TyCtxt;
  20 use util::nodemap::NodeMap;
  21
  22 /// The definition table containing node definitions
  23 #[derive(Clone)]
  24 pub struct Definitions {
  25     data: Vec<DefData>,
  26     key_map: FnvHashMap<DefKey, DefIndex>,
  27     node_map: NodeMap<DefIndex>,
  28 }
  29
  30 /// A unique identifier that we can use to lookup a definition
  31 /// precisely. It combines the index of the definition's parent (if
  32 /// any) with a `DisambiguatedDefPathData`.
  33 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
  34 pub struct DefKey {
  35     /// Parent path.
  36     pub parent: Option<DefIndex>,
  37
  38     /// Identifier of this node.
  39     pub disambiguated_data: DisambiguatedDefPathData,
  40 }
  41
  42 /// Pair of `DefPathData` and an integer disambiguator. The integer is
  43 /// normally 0, but in the event that there are multiple defs with the
  44 /// same `parent` and `data`, we use this field to disambiguate
  45 /// between them. This introduces some artificial ordering dependency
  46 /// but means that if you have (e.g.) two impls for the same type in
  47 /// the same module, they do get distinct def-ids.
  48 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
  49 pub struct DisambiguatedDefPathData {
  50     pub data: DefPathData,
  51     pub disambiguator: u32
  52 }
  53
  54 /// For each definition, we track the following data.  A definition
  55 /// here is defined somewhat circularly as "something with a def-id",
  56 /// but it generally corresponds to things like structs, enums, etc.
  57 /// There are also some rather random cases (like const initializer
  58 /// expressions) that are mostly just leftovers.
  59 #[derive(Clone, Debug)]
  60 pub struct DefData {
  61     pub key: DefKey,
  62
  63     /// Local ID within the HIR.
  64     pub node_id: ast::NodeId,
  65 }
  66
  67 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
  68 pub struct DefPath {
  69     /// the path leading from the crate root to the item
  70     pub data: Vec<DisambiguatedDefPathData>,
  71
  72     /// what krate root is this path relative to?
  73     pub krate: ast::CrateNum,
  74 }
  75
  76 impl DefPath {
  77     pub fn is_local(&self) -> bool {
  78         self.krate == LOCAL_CRATE
  79     }
  80
  81     pub fn make<FN>(start_krate: ast::CrateNum,
  82                     start_index: DefIndex,
  83                     mut get_key: FN) -> DefPath
  84         where FN: FnMut(DefIndex) -> DefKey
  85     {
  86         let mut krate = start_krate;
  87         let mut data = vec![];
  88         let mut index = Some(start_index);
  89         loop {
  90             debug!("DefPath::make: krate={:?} index={:?}", krate, index);
  91             let p = index.unwrap();
  92             let key = get_key(p);
  93             debug!("DefPath::make: key={:?}", key);
  94             match key.disambiguated_data.data {
  95                 DefPathData::CrateRoot => {
  96                     assert!(key.parent.is_none());
  97                     break;
  98                 }
  99                 DefPathData::InlinedRoot(ref p) => {
 100                     assert!(key.parent.is_none());
 101                     assert!(!p.def_id.is_local());
 102                     data.extend(p.data.iter().cloned().rev());
 103                     krate = p.def_id.krate;
 104                     break;
 105                 }
 106                 _ => {
 107                     data.push(key.disambiguated_data);
 108                     index = key.parent;
 109                 }
 110             }
 111         }
 112         data.reverse();
 113         DefPath { data: data, krate: krate }
 114     }
 115
 116     pub fn to_string(&self, tcx: TyCtxt) -> String {
 117         let mut s = String::with_capacity(self.data.len() * 16);
 118
 119         if self.krate == LOCAL_CRATE {
 120             s.push_str(&tcx.crate_name(self.krate));
 121         } else {
 122             s.push_str(&tcx.sess.cstore.original_crate_name(self.krate));
 123         }
 124         s.push_str("/");
 125         s.push_str(&tcx.crate_disambiguator(self.krate));
 126
 127         for component in &self.data {
 128             write!(s,
 129                    "::{}[{}]",
 130                    component.data.as_interned_str(),
 131                    component.disambiguator)
 132                 .unwrap();
 133         }
 134
 135         s
 136     }
 137
 138     pub fn deterministic_hash(&self, tcx: TyCtxt) -> u64 {
 139         let mut state = SipHasher::new();
 140         self.deterministic_hash_to(tcx, &mut state);
 141         state.finish()
 142     }
 143
 144     pub fn deterministic_hash_to<H: Hasher>(&self, tcx: TyCtxt, state: &mut H) {
 145         tcx.crate_name(self.krate).hash(state);
 146         tcx.crate_disambiguator(self.krate).hash(state);
 147         self.data.hash(state);
 148     }
 149 }
 150
 151 /// Root of an inlined item. We track the `DefPath` of the item within
 152 /// the original crate but also its def-id. This is kind of an
 153 /// augmented version of a `DefPath` that includes a `DefId`. This is
 154 /// all sort of ugly but the hope is that inlined items will be going
 155 /// away soon anyway.
 156 ///
 157 /// Some of the constraints that led to the current approach:
 158 ///
 159 /// - I don't want to have a `DefId` in the main `DefPath` because
 160 ///   that gets serialized for incr. comp., and when reloaded the
 161 ///   `DefId` is no longer valid. I'd rather maintain the invariant
 162 ///   that every `DefId` is valid, and a potentially outdated `DefId` is
 163 ///   represented as a `DefPath`.
 164 ///   - (We don't serialize def-paths from inlined items, so it's ok to have one here.)
 165 /// - We need to be able to extract the def-id from inline items to
 166 ///   make the symbol name. In theory we could retrace it from the
 167 ///   data, but the metadata doesn't have the required indices, and I
 168 ///   don't want to write the code to create one just for this.
 169 /// - It may be that we don't actually need `data` at all. We'll have
 170 ///   to see about that.
 171 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 172 pub struct InlinedRootPath {
 173     pub data: Vec<DisambiguatedDefPathData>,
 174     pub def_id: DefId,
 175 }
 176
 177 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 178 pub enum DefPathData {
 179     // Root: these should only be used for the root nodes, because
 180     // they are treated specially by the `def_path` function.
 181     /// The crate root (marker)
 182     CrateRoot,
 183     /// An inlined root
 184     InlinedRoot(Box<InlinedRootPath>),
 185
 186     // Catch-all for random DefId things like DUMMY_NODE_ID
 187     Misc,
 188
 189     // Different kinds of items and item-like things:
 190     /// An impl
 191     Impl,
 192     /// Something in the type NS
 193     TypeNs(InternedString),
 194     /// Something in the value NS
 195     ValueNs(InternedString),
 196     /// A module declaration
 197     Module(InternedString),
 198     /// A macro rule
 199     MacroDef(InternedString),
 200     /// A closure expression
 201     ClosureExpr,
 202
 203     // Subportions of items
 204     /// A type parameter (generic parameter)
 205     TypeParam(InternedString),
 206     /// A lifetime definition
 207     LifetimeDef(InternedString),
 208     /// A variant of a enum
 209     EnumVariant(InternedString),
 210     /// A struct field
 211     Field(InternedString),
 212     /// Implicit ctor for a tuple-like struct
 213     StructCtor,
 214     /// Initializer for a const
 215     Initializer,
 216     /// Pattern binding
 217     Binding(InternedString),
 218     /// An `impl Trait` type node.
 219     ImplTrait
 220 }
 221
 222 impl Definitions {
 223     /// Create new empty definition map.
 224     pub fn new() -> Definitions {
 225         Definitions {
 226             data: vec![],
 227             key_map: FnvHashMap(),
 228             node_map: NodeMap(),
 229         }
 230     }
 231
 232     pub fn collect(&mut self, krate: &ast::Crate) {
 233         let mut def_collector = DefCollector::root(self);
 234         visit::walk_crate(&mut def_collector, krate);
 235     }
 236
 237     /// Get the number of definitions.
 238     pub fn len(&self) -> usize {
 239         self.data.len()
 240     }
 241
 242     pub fn def_key(&self, index: DefIndex) -> DefKey {
 243         self.data[index.as_usize()].key.clone()
 244     }
 245
 246     pub fn def_index_for_def_key(&self, key: DefKey) -> Option<DefIndex> {
 247         self.key_map.get(&key).cloned()
 248     }
 249
 250     /// Returns the path from the crate root to `index`. The root
 251     /// nodes are not included in the path (i.e., this will be an
 252     /// empty vector for the crate root). For an inlined item, this
 253     /// will be the path of the item in the external crate (but the
 254     /// path will begin with the path to the external crate).
 255     pub fn def_path(&self, index: DefIndex) -> DefPath {
 256         DefPath::make(LOCAL_CRATE, index, |p| self.def_key(p))
 257     }
 258
 259     pub fn opt_def_index(&self, node: ast::NodeId) -> Option<DefIndex> {
 260         self.node_map.get(&node).cloned()
 261     }
 262
 263     pub fn opt_local_def_id(&self, node: ast::NodeId) -> Option<DefId> {
 264         self.opt_def_index(node).map(DefId::local)
 265     }
 266
 267     pub fn local_def_id(&self, node: ast::NodeId) -> DefId {
 268         self.opt_local_def_id(node).unwrap()
 269     }
 270
 271     pub fn as_local_node_id(&self, def_id: DefId) -> Option<ast::NodeId> {
 272         if def_id.krate == LOCAL_CRATE {
 273             assert!(def_id.index.as_usize() < self.data.len());
 274             Some(self.data[def_id.index.as_usize()].node_id)
 275         } else {
 276             None
 277         }
 278     }
 279
 280     /// Add a definition with a parent definition.
 281     pub fn create_def_with_parent(&mut self,
 282                                   parent: Option<DefIndex>,
 283                                   node_id: ast::NodeId,
 284                                   data: DefPathData)
 285                                   -> DefIndex {
 286         debug!("create_def_with_parent(parent={:?}, node_id={:?}, data={:?})",
 287                parent, node_id, data);
 288
 289         assert!(!self.node_map.contains_key(&node_id),
 290                 "adding a def'n for node-id {:?} and data {:?} but a previous def'n exists: {:?}",
 291                 node_id,
 292                 data,
 293                 self.data[self.node_map[&node_id].as_usize()]);
 294
 295         assert!(parent.is_some() ^ match data {
 296             DefPathData::CrateRoot | DefPathData::InlinedRoot(_) => true,
 297             _ => false,
 298         });
 299
 300         // Find a unique DefKey. This basically means incrementing the disambiguator
 301         // until we get no match.
 302         let mut key = DefKey {
 303             parent: parent,
 304             disambiguated_data: DisambiguatedDefPathData {
 305                 data: data,
 306                 disambiguator: 0
 307             }
 308         };
 309
 310         while self.key_map.contains_key(&key) {
 311             key.disambiguated_data.disambiguator += 1;
 312         }
 313
 314         debug!("create_def_with_parent: after disambiguation, key = {:?}", key);
 315
 316         // Create the definition.
 317         let index = DefIndex::new(self.data.len());
 318         self.data.push(DefData { key: key.clone(), node_id: node_id });
 319         debug!("create_def_with_parent: node_map[{:?}] = {:?}", node_id, index);
 320         self.node_map.insert(node_id, index);
 321         debug!("create_def_with_parent: key_map[{:?}] = {:?}", key, index);
 322         self.key_map.insert(key, index);
 323
 324
 325         index
 326     }
 327 }
 328
 329 impl DefPathData {
 330     pub fn as_interned_str(&self) -> InternedString {
 331         use self::DefPathData::*;
 332         match *self {
 333             TypeNs(ref name) |
 334             ValueNs(ref name) |
 335             Module(ref name) |
 336             MacroDef(ref name) |
 337             TypeParam(ref name) |
 338             LifetimeDef(ref name) |
 339             EnumVariant(ref name) |
 340             Binding(ref name) |
 341             Field(ref name) => {
 342                 name.clone()
 343             }
 344
 345             Impl => {
 346                 InternedString::new("{{impl}}")
 347             }
 348
 349             // note that this does not show up in user printouts
 350             CrateRoot => {
 351                 InternedString::new("{{root}}")
 352             }
 353
 354             // note that this does not show up in user printouts
 355             InlinedRoot(_) => {
 356                 InternedString::new("{{inlined-root}}")
 357             }
 358
 359             Misc => {
 360                 InternedString::new("{{?}}")
 361             }
 362
 363             ClosureExpr => {
 364                 InternedString::new("{{closure}}")
 365             }
 366
 367             StructCtor => {
 368                 InternedString::new("{{constructor}}")
 369             }
 370
 371             Initializer => {
 372                 InternedString::new("{{initializer}}")
 373             }
 374
 375             ImplTrait => {
 376                 InternedString::new("{{impl-Trait}}")
 377             }
 378         }
 379     }
 380
 381     pub fn to_string(&self) -> String {
 382         self.as_interned_str().to_string()
 383     }
 384 }
 385