src/librustc/front/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 middle::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 pub type DefPath = Vec<DisambiguatedDefPathData>;
  63 /// Root of an inlined item. We track the `DefPath` of the item within
  64 /// the original crate but also its def-id. This is kind of an
  65 /// augmented version of a `DefPath` that includes a `DefId`. This is
  66 /// all sort of ugly but the hope is that inlined items will be going
  67 /// away soon anyway.
  68 ///
  69 /// Some of the constraints that led to the current approach:
  70 ///
  71 /// - I don't want to have a `DefId` in the main `DefPath` because
  72 ///   that gets serialized for incr. comp., and when reloaded the
  73 ///   `DefId` is no longer valid. I'd rather maintain the invariant
  74 ///   that every `DefId` is valid, and a potentially outdated `DefId` is
  75 ///   represented as a `DefPath`.
  76 ///   - (We don't serialize def-paths from inlined items, so it's ok to have one here.)
  77 /// - We need to be able to extract the def-id from inline items to
  78 ///   make the symbol name. In theory we could retrace it from the
  79 ///   data, but the metadata doesn't have the required indices, and I
  80 ///   don't want to write the code to create one just for this.
  81 /// - It may be that we don't actually need `data` at all. We'll have
  82 ///   to see about that.
  83 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
  84 pub struct InlinedRootPath {
  85     pub data: Vec<DisambiguatedDefPathData>,
  86     pub def_id: DefId,
  87 }
  88
  89 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
  90 pub enum DefPathData {
  91     // Root: these should only be used for the root nodes, because
  92     // they are treated specially by the `def_path` function.
  93     CrateRoot,
  94     InlinedRoot(Box<InlinedRootPath>),
  95
  96     // Catch-all for random DefId things like DUMMY_NODE_ID
  97     Misc,
  98
  99     // Different kinds of items and item-like things:
 100     Impl(ast::Name),
 101     Type(ast::Name),
 102     Mod(ast::Name),
 103     Value(ast::Name),
 104     MacroDef(ast::Name),
 105     ClosureExpr,
 106
 107     // Subportions of items
 108     TypeParam(ast::Name),
 109     LifetimeDef(ast::Name),
 110     EnumVariant(ast::Name),
 111     Field(ast::Name),
 112     StructCtor, // implicit ctor for a tuple-like struct
 113     Initializer, // initializer for a const
 114     Binding(ast::Name), // pattern binding
 115
 116     // An external crate that does not have an `extern crate` in this
 117     // crate.
 118     DetachedCrate(ast::Name),
 119 }
 120
 121 impl Definitions {
 122     pub fn new() -> Definitions {
 123         Definitions {
 124             data: vec![],
 125             key_map: FnvHashMap(),
 126             node_map: NodeMap(),
 127         }
 128     }
 129
 130     pub fn len(&self) -> usize {
 131         self.data.len()
 132     }
 133
 134     pub fn def_key(&self, index: DefIndex) -> DefKey {
 135         self.data[index.as_usize()].key.clone()
 136     }
 137
 138     /// Returns the path from the crate root to `index`. The root
 139     /// nodes are not included in the path (i.e., this will be an
 140     /// empty vector for the crate root). For an inlined item, this
 141     /// will be the path of the item in the external crate (but the
 142     /// path will begin with the path to the external crate).
 143     pub fn def_path(&self, index: DefIndex) -> DefPath {
 144         make_def_path(index, |p| self.def_key(p))
 145     }
 146
 147     pub fn opt_def_index(&self, node: ast::NodeId) -> Option<DefIndex> {
 148         self.node_map.get(&node).cloned()
 149     }
 150
 151     pub fn opt_local_def_id(&self, node: ast::NodeId) -> Option<DefId> {
 152         self.opt_def_index(node).map(DefId::local)
 153     }
 154
 155     pub fn as_local_node_id(&self, def_id: DefId) -> Option<ast::NodeId> {
 156         if def_id.krate == LOCAL_CRATE {
 157             assert!(def_id.index.as_usize() < self.data.len());
 158             Some(self.data[def_id.index.as_usize()].node_id)
 159         } else {
 160             None
 161         }
 162     }
 163
 164     pub fn create_def_with_parent(&mut self,
 165                                   parent: Option<DefIndex>,
 166                                   node_id: ast::NodeId,
 167                                   data: DefPathData)
 168                                   -> DefIndex {
 169         assert!(!self.node_map.contains_key(&node_id),
 170                 "adding a def'n for node-id {:?} and data {:?} but a previous def'n exists: {:?}",
 171                 node_id,
 172                 data,
 173                 self.data[self.node_map[&node_id].as_usize()]);
 174
 175         // Find a unique DefKey. This basically means incrementing the disambiguator
 176         // until we get no match.
 177         let mut key = DefKey {
 178             parent: parent,
 179             disambiguated_data: DisambiguatedDefPathData {
 180                 data: data,
 181                 disambiguator: 0
 182             }
 183         };
 184
 185         while self.key_map.contains_key(&key) {
 186             key.disambiguated_data.disambiguator += 1;
 187         }
 188
 189         // Create the definition.
 190         let index = DefIndex::new(self.data.len());
 191         self.data.push(DefData { key: key.clone(), node_id: node_id });
 192         self.node_map.insert(node_id, index);
 193         self.key_map.insert(key, index);
 194
 195         index
 196     }
 197 }
 198
 199 impl DefPathData {
 200     pub fn as_interned_str(&self) -> InternedString {
 201         use self::DefPathData::*;
 202         match *self {
 203             Impl(name) |
 204             Type(name) |
 205             Mod(name) |
 206             Value(name) |
 207             MacroDef(name) |
 208             TypeParam(name) |
 209             LifetimeDef(name) |
 210             EnumVariant(name) |
 211             DetachedCrate(name) |
 212             Binding(name) |
 213             Field(name) => {
 214                 name.as_str()
 215             }
 216
 217             // note that this does not show up in user printouts
 218             CrateRoot => {
 219                 InternedString::new("{{root}}")
 220             }
 221
 222             // note that this does not show up in user printouts
 223             InlinedRoot(_) => {
 224                 InternedString::new("{{inlined-root}}")
 225             }
 226
 227             Misc => {
 228                 InternedString::new("{{?}}")
 229             }
 230
 231             ClosureExpr => {
 232                 InternedString::new("{{closure}}")
 233             }
 234
 235             StructCtor => {
 236                 InternedString::new("{{constructor}}")
 237             }
 238
 239             Initializer => {
 240                 InternedString::new("{{initializer}}")
 241             }
 242         }
 243     }
 244
 245     pub fn to_string(&self) -> String {
 246         self.as_interned_str().to_string()
 247     }
 248 }
 249
 250 pub fn make_def_path<FN>(start_index: DefIndex, mut get_key: FN) -> DefPath
 251     where FN: FnMut(DefIndex) -> DefKey
 252 {
 253     let mut result = vec![];
 254     let mut index = Some(start_index);
 255     while let Some(p) = index {
 256         let key = get_key(p);
 257         match key.disambiguated_data.data {
 258             DefPathData::CrateRoot => {
 259                 assert!(key.parent.is_none());
 260                 break;
 261             }
 262             DefPathData::InlinedRoot(ref p) => {
 263                 assert!(key.parent.is_none());
 264                 result.extend(p.iter().cloned().rev());
 265                 break;
 266             }
 267             _ => {
 268                 result.push(key.disambiguated_data);
 269                 index = key.parent;
 270             }
 271         }
 272     }
 273     result.reverse();
 274     result
 275 }