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