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