src/librustc_passes/static_recursion.rs

   1 // Copyright 2014 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 // This compiler pass detects constants that refer to themselves
  12 // recursively.
  13
  14 use rustc::dep_graph::DepNode;
  15 use rustc::hir::map as hir_map;
  16 use rustc::session::{CompileResult, Session};
  17 use rustc::hir::def::{Def, CtorKind};
  18 use rustc::util::nodemap::{NodeMap, NodeSet};
  19
  20 use syntax::ast;
  21 use syntax_pos::Span;
  22 use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
  23 use rustc::hir;
  24
  25 struct CheckCrateVisitor<'a, 'hir: 'a> {
  26     sess: &'a Session,
  27     hir_map: &'a hir_map::Map<'hir>,
  28     // `discriminant_map` is a cache that associates the `NodeId`s of local
  29     // variant definitions with the discriminant expression that applies to
  30     // each one. If the variant uses the default values (starting from `0`),
  31     // then `None` is stored.
  32     discriminant_map: NodeMap<Option<hir::BodyId>>,
  33     detected_recursive_ids: NodeSet,
  34 }
  35
  36 impl<'a, 'hir: 'a> Visitor<'hir> for CheckCrateVisitor<'a, 'hir> {
  37     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'hir> {
  38         NestedVisitorMap::None
  39     }
  40
  41     fn visit_item(&mut self, it: &'hir hir::Item) {
  42         match it.node {
  43             hir::ItemStatic(..) |
  44             hir::ItemConst(..) => {
  45                 let mut recursion_visitor = CheckItemRecursionVisitor::new(self);
  46                 recursion_visitor.visit_item(it);
  47             }
  48             hir::ItemEnum(ref enum_def, ref generics) => {
  49                 // We could process the whole enum, but handling the variants
  50                 // with discriminant expressions one by one gives more specific,
  51                 // less redundant output.
  52                 for variant in &enum_def.variants {
  53                     if let Some(_) = variant.node.disr_expr {
  54                         let mut recursion_visitor = CheckItemRecursionVisitor::new(self);
  55                         recursion_visitor.populate_enum_discriminants(enum_def);
  56                         recursion_visitor.visit_variant(variant, generics, it.id);
  57                     }
  58                 }
  59             }
  60             _ => {}
  61         }
  62         intravisit::walk_item(self, it)
  63     }
  64
  65     fn visit_trait_item(&mut self, ti: &'hir hir::TraitItem) {
  66         match ti.node {
  67             hir::TraitItemKind::Const(_, ref default) => {
  68                 if let Some(_) = *default {
  69                     let mut recursion_visitor = CheckItemRecursionVisitor::new(self);
  70                     recursion_visitor.visit_trait_item(ti);
  71                 }
  72             }
  73             _ => {}
  74         }
  75         intravisit::walk_trait_item(self, ti)
  76     }
  77
  78     fn visit_impl_item(&mut self, ii: &'hir hir::ImplItem) {
  79         match ii.node {
  80             hir::ImplItemKind::Const(..) => {
  81                 let mut recursion_visitor = CheckItemRecursionVisitor::new(self);
  82                 recursion_visitor.visit_impl_item(ii);
  83             }
  84             _ => {}
  85         }
  86         intravisit::walk_impl_item(self, ii)
  87     }
  88 }
  89
  90 pub fn check_crate<'hir>(sess: &Session, hir_map: &hir_map::Map<'hir>) -> CompileResult {
  91     let _task = hir_map.dep_graph.in_task(DepNode::CheckStaticRecursion);
  92
  93     let mut visitor = CheckCrateVisitor {
  94         sess: sess,
  95         hir_map: hir_map,
  96         discriminant_map: NodeMap(),
  97         detected_recursive_ids: NodeSet(),
  98     };
  99     sess.track_errors(|| {
 100         // FIXME(#37712) could use ItemLikeVisitor if trait items were item-like
 101         hir_map.krate().visit_all_item_likes(&mut visitor.as_deep_visitor());
 102     })
 103 }
 104
 105 struct CheckItemRecursionVisitor<'a, 'b: 'a, 'hir: 'b> {
 106     sess: &'b Session,
 107     hir_map: &'b hir_map::Map<'hir>,
 108     discriminant_map: &'a mut NodeMap<Option<hir::BodyId>>,
 109     idstack: Vec<ast::NodeId>,
 110     detected_recursive_ids: &'a mut NodeSet,
 111 }
 112
 113 impl<'a, 'b: 'a, 'hir: 'b> CheckItemRecursionVisitor<'a, 'b, 'hir> {
 114     fn new(v: &'a mut CheckCrateVisitor<'b, 'hir>) -> Self {
 115         CheckItemRecursionVisitor {
 116             sess: v.sess,
 117             hir_map: v.hir_map,
 118             discriminant_map: &mut v.discriminant_map,
 119             idstack: Vec::new(),
 120             detected_recursive_ids: &mut v.detected_recursive_ids,
 121         }
 122     }
 123     fn with_item_id_pushed<F>(&mut self, id: ast::NodeId, f: F, span: Span)
 124         where F: Fn(&mut Self)
 125     {
 126         if self.idstack.iter().any(|&x| x == id) {
 127             if self.detected_recursive_ids.contains(&id) {
 128                 return;
 129             }
 130             self.detected_recursive_ids.insert(id);
 131             let any_static = self.idstack.iter().any(|&x| {
 132                 if let hir_map::NodeItem(item) = self.hir_map.get(x) {
 133                     if let hir::ItemStatic(..) = item.node {
 134                         true
 135                     } else {
 136                         false
 137                     }
 138                 } else {
 139                     false
 140                 }
 141             });
 142             if !any_static {
 143                 struct_span_err!(self.sess, span, E0265, "recursive constant")
 144                     .span_label(span, &format!("recursion not allowed in constant"))
 145                     .emit();
 146             }
 147             return;
 148         }
 149         self.idstack.push(id);
 150         f(self);
 151         self.idstack.pop();
 152     }
 153     // If a variant has an expression specifying its discriminant, then it needs
 154     // to be checked just like a static or constant. However, if there are more
 155     // variants with no explicitly specified discriminant, those variants will
 156     // increment the same expression to get their values.
 157     //
 158     // So for every variant, we need to track whether there is an expression
 159     // somewhere in the enum definition that controls its discriminant. We do
 160     // this by starting from the end and searching backward.
 161     fn populate_enum_discriminants(&mut self, enum_definition: &'hir hir::EnumDef) {
 162         // Get the map, and return if we already processed this enum or if it
 163         // has no variants.
 164         match enum_definition.variants.first() {
 165             None => {
 166                 return;
 167             }
 168             Some(variant) if self.discriminant_map.contains_key(&variant.node.data.id()) => {
 169                 return;
 170             }
 171             _ => {}
 172         }
 173
 174         // Go through all the variants.
 175         let mut variant_stack: Vec<ast::NodeId> = Vec::new();
 176         for variant in enum_definition.variants.iter().rev() {
 177             variant_stack.push(variant.node.data.id());
 178             // When we find an expression, every variant currently on the stack
 179             // is affected by that expression.
 180             if let Some(expr) = variant.node.disr_expr {
 181                 for id in &variant_stack {
 182                     self.discriminant_map.insert(*id, Some(expr));
 183                 }
 184                 variant_stack.clear()
 185             }
 186         }
 187         // If we are at the top, that always starts at 0, so any variant on the
 188         // stack has a default value and does not need to be checked.
 189         for id in &variant_stack {
 190             self.discriminant_map.insert(*id, None);
 191         }
 192     }
 193 }
 194
 195 impl<'a, 'b: 'a, 'hir: 'b> Visitor<'hir> for CheckItemRecursionVisitor<'a, 'b, 'hir> {
 196     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'hir> {
 197         NestedVisitorMap::OnlyBodies(&self.hir_map)
 198     }
 199     fn visit_item(&mut self, it: &'hir hir::Item) {
 200         self.with_item_id_pushed(it.id, |v| intravisit::walk_item(v, it), it.span);
 201     }
 202
 203     fn visit_enum_def(&mut self,
 204                       enum_definition: &'hir hir::EnumDef,
 205                       generics: &'hir hir::Generics,
 206                       item_id: ast::NodeId,
 207                       _: Span) {
 208         self.populate_enum_discriminants(enum_definition);
 209         intravisit::walk_enum_def(self, enum_definition, generics, item_id);
 210     }
 211
 212     fn visit_variant(&mut self,
 213                      variant: &'hir hir::Variant,
 214                      _: &'hir hir::Generics,
 215                      _: ast::NodeId) {
 216         let variant_id = variant.node.data.id();
 217         let maybe_expr = *self.discriminant_map.get(&variant_id).unwrap_or_else(|| {
 218             span_bug!(variant.span,
 219                       "`check_static_recursion` attempted to visit \
 220                       variant with unknown discriminant")
 221         });
 222         // If `maybe_expr` is `None`, that's because no discriminant is
 223         // specified that affects this variant. Thus, no risk of recursion.
 224         if let Some(expr) = maybe_expr {
 225             let expr = &self.hir_map.body(expr).value;
 226             self.with_item_id_pushed(expr.id, |v| intravisit::walk_expr(v, expr), expr.span);
 227         }
 228     }
 229
 230     fn visit_trait_item(&mut self, ti: &'hir hir::TraitItem) {
 231         self.with_item_id_pushed(ti.id, |v| intravisit::walk_trait_item(v, ti), ti.span);
 232     }
 233
 234     fn visit_impl_item(&mut self, ii: &'hir hir::ImplItem) {
 235         self.with_item_id_pushed(ii.id, |v| intravisit::walk_impl_item(v, ii), ii.span);
 236     }
 237
 238     fn visit_path(&mut self, path: &'hir hir::Path, _: ast::NodeId) {
 239         match path.def {
 240             Def::Static(def_id, _) |
 241             Def::AssociatedConst(def_id) |
 242             Def::Const(def_id) => {
 243                 if let Some(node_id) = self.hir_map.as_local_node_id(def_id) {
 244                     match self.hir_map.get(node_id) {
 245                         hir_map::NodeItem(item) => self.visit_item(item),
 246                         hir_map::NodeTraitItem(item) => self.visit_trait_item(item),
 247                         hir_map::NodeImplItem(item) => self.visit_impl_item(item),
 248                         hir_map::NodeForeignItem(_) => {}
 249                         _ => {
 250                             span_bug!(path.span,
 251                                       "expected item, found {}",
 252                                       self.hir_map.node_to_string(node_id));
 253                         }
 254                     }
 255                 }
 256             }
 257             // For variants, we only want to check expressions that
 258             // affect the specific variant used, but we need to check
 259             // the whole enum definition to see what expression that
 260             // might be (if any).
 261             Def::VariantCtor(variant_id, CtorKind::Const) => {
 262                 if let Some(variant_id) = self.hir_map.as_local_node_id(variant_id) {
 263                     let variant = self.hir_map.expect_variant(variant_id);
 264                     let enum_id = self.hir_map.get_parent(variant_id);
 265                     let enum_item = self.hir_map.expect_item(enum_id);
 266                     if let hir::ItemEnum(ref enum_def, ref generics) = enum_item.node {
 267                         self.populate_enum_discriminants(enum_def);
 268                         self.visit_variant(variant, generics, enum_id);
 269                     } else {
 270                         span_bug!(path.span,
 271                                   "`check_static_recursion` found \
 272                                     non-enum in Def::VariantCtor");
 273                     }
 274                 }
 275             }
 276             _ => (),
 277         }
 278         intravisit::walk_path(self, path);
 279     }
 280 }