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 ast_map;
  16 use rustc::session::{CompileResult, Session};
  17 use rustc::hir::def::{Def, DefMap};
  18 use rustc::util::nodemap::NodeMap;
  19
  20 use syntax::ast;
  21 use syntax::feature_gate::{GateIssue, emit_feature_err};
  22 use syntax_pos::Span;
  23 use rustc::hir::intravisit::{self, Visitor};
  24 use rustc::hir;
  25
  26 use std::cell::RefCell;
  27
  28 struct CheckCrateVisitor<'a, 'ast: 'a> {
  29     sess: &'a Session,
  30     def_map: &'a DefMap,
  31     ast_map: &'a ast_map::Map<'ast>,
  32     // `discriminant_map` is a cache that associates the `NodeId`s of local
  33     // variant definitions with the discriminant expression that applies to
  34     // each one. If the variant uses the default values (starting from `0`),
  35     // then `None` is stored.
  36     discriminant_map: RefCell<NodeMap<Option<&'ast hir::Expr>>>,
  37 }
  38
  39 impl<'a, 'ast: 'a> Visitor<'ast> for CheckCrateVisitor<'a, 'ast> {
  40     fn visit_item(&mut self, it: &'ast hir::Item) {
  41         match it.node {
  42             hir::ItemStatic(..) |
  43             hir::ItemConst(..) => {
  44                 let mut recursion_visitor = CheckItemRecursionVisitor::new(self, &it.span);
  45                 recursion_visitor.visit_item(it);
  46             }
  47             hir::ItemEnum(ref enum_def, ref generics) => {
  48                 // We could process the whole enum, but handling the variants
  49                 // with discriminant expressions one by one gives more specific,
  50                 // less redundant output.
  51                 for variant in &enum_def.variants {
  52                     if let Some(_) = variant.node.disr_expr {
  53                         let mut recursion_visitor = CheckItemRecursionVisitor::new(self,
  54                                                                                    &variant.span);
  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: &'ast hir::TraitItem) {
  66         match ti.node {
  67             hir::ConstTraitItem(_, ref default) => {
  68                 if let Some(_) = *default {
  69                     let mut recursion_visitor = CheckItemRecursionVisitor::new(self, &ti.span);
  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: &'ast hir::ImplItem) {
  79         match ii.node {
  80             hir::ImplItemKind::Const(..) => {
  81                 let mut recursion_visitor = CheckItemRecursionVisitor::new(self, &ii.span);
  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<'ast>(sess: &Session,
  91                          def_map: &DefMap,
  92                          ast_map: &ast_map::Map<'ast>)
  93                          -> CompileResult {
  94     let _task = ast_map.dep_graph.in_task(DepNode::CheckStaticRecursion);
  95
  96     let mut visitor = CheckCrateVisitor {
  97         sess: sess,
  98         def_map: def_map,
  99         ast_map: ast_map,
 100         discriminant_map: RefCell::new(NodeMap()),
 101     };
 102     sess.track_errors(|| {
 103         ast_map.krate().visit_all_items(&mut visitor);
 104     })
 105 }
 106
 107 struct CheckItemRecursionVisitor<'a, 'ast: 'a> {
 108     root_span: &'a Span,
 109     sess: &'a Session,
 110     ast_map: &'a ast_map::Map<'ast>,
 111     def_map: &'a DefMap,
 112     discriminant_map: &'a RefCell<NodeMap<Option<&'ast hir::Expr>>>,
 113     idstack: Vec<ast::NodeId>,
 114 }
 115
 116 impl<'a, 'ast: 'a> CheckItemRecursionVisitor<'a, 'ast> {
 117     fn new(v: &'a CheckCrateVisitor<'a, 'ast>,
 118            span: &'a Span)
 119            -> CheckItemRecursionVisitor<'a, 'ast> {
 120         CheckItemRecursionVisitor {
 121             root_span: span,
 122             sess: v.sess,
 123             ast_map: v.ast_map,
 124             def_map: v.def_map,
 125             discriminant_map: &v.discriminant_map,
 126             idstack: Vec::new(),
 127         }
 128     }
 129     fn with_item_id_pushed<F>(&mut self, id: ast::NodeId, f: F, span: Span)
 130         where F: Fn(&mut Self)
 131     {
 132         if self.idstack.iter().any(|&x| x == id) {
 133             let any_static = self.idstack.iter().any(|&x| {
 134                 if let ast_map::NodeItem(item) = self.ast_map.get(x) {
 135                     if let hir::ItemStatic(..) = item.node {
 136                         true
 137                     } else {
 138                         false
 139                     }
 140                 } else {
 141                     false
 142                 }
 143             });
 144             if any_static {
 145                 if !self.sess.features.borrow().static_recursion {
 146                     emit_feature_err(&self.sess.parse_sess.span_diagnostic,
 147                                      "static_recursion",
 148                                      *self.root_span,
 149                                      GateIssue::Language,
 150                                      "recursive static");
 151                 }
 152             } else {
 153                 struct_span_err!(self.sess, span, E0265, "recursive constant")
 154                     .span_label(span, &format!("recursion not allowed in constant"))
 155                     .emit();
 156             }
 157             return;
 158         }
 159         self.idstack.push(id);
 160         f(self);
 161         self.idstack.pop();
 162     }
 163     // If a variant has an expression specifying its discriminant, then it needs
 164     // to be checked just like a static or constant. However, if there are more
 165     // variants with no explicitly specified discriminant, those variants will
 166     // increment the same expression to get their values.
 167     //
 168     // So for every variant, we need to track whether there is an expression
 169     // somewhere in the enum definition that controls its discriminant. We do
 170     // this by starting from the end and searching backward.
 171     fn populate_enum_discriminants(&self, enum_definition: &'ast hir::EnumDef) {
 172         // Get the map, and return if we already processed this enum or if it
 173         // has no variants.
 174         let mut discriminant_map = self.discriminant_map.borrow_mut();
 175         match enum_definition.variants.first() {
 176             None => {
 177                 return;
 178             }
 179             Some(variant) if discriminant_map.contains_key(&variant.node.data.id()) => {
 180                 return;
 181             }
 182             _ => {}
 183         }
 184
 185         // Go through all the variants.
 186         let mut variant_stack: Vec<ast::NodeId> = Vec::new();
 187         for variant in enum_definition.variants.iter().rev() {
 188             variant_stack.push(variant.node.data.id());
 189             // When we find an expression, every variant currently on the stack
 190             // is affected by that expression.
 191             if let Some(ref expr) = variant.node.disr_expr {
 192                 for id in &variant_stack {
 193                     discriminant_map.insert(*id, Some(expr));
 194                 }
 195                 variant_stack.clear()
 196             }
 197         }
 198         // If we are at the top, that always starts at 0, so any variant on the
 199         // stack has a default value and does not need to be checked.
 200         for id in &variant_stack {
 201             discriminant_map.insert(*id, None);
 202         }
 203     }
 204 }
 205
 206 impl<'a, 'ast: 'a> Visitor<'ast> for CheckItemRecursionVisitor<'a, 'ast> {
 207     fn visit_item(&mut self, it: &'ast hir::Item) {
 208         self.with_item_id_pushed(it.id, |v| intravisit::walk_item(v, it), it.span);
 209     }
 210
 211     fn visit_enum_def(&mut self,
 212                       enum_definition: &'ast hir::EnumDef,
 213                       generics: &'ast hir::Generics,
 214                       item_id: ast::NodeId,
 215                       _: Span) {
 216         self.populate_enum_discriminants(enum_definition);
 217         intravisit::walk_enum_def(self, enum_definition, generics, item_id);
 218     }
 219
 220     fn visit_variant(&mut self,
 221                      variant: &'ast hir::Variant,
 222                      _: &'ast hir::Generics,
 223                      _: ast::NodeId) {
 224         let variant_id = variant.node.data.id();
 225         let maybe_expr;
 226         if let Some(get_expr) = self.discriminant_map.borrow().get(&variant_id) {
 227             // This is necessary because we need to let the `discriminant_map`
 228             // borrow fall out of scope, so that we can reborrow farther down.
 229             maybe_expr = (*get_expr).clone();
 230         } else {
 231             span_bug!(variant.span,
 232                       "`check_static_recursion` attempted to visit \
 233                       variant with unknown discriminant")
 234         }
 235         // If `maybe_expr` is `None`, that's because no discriminant is
 236         // specified that affects this variant. Thus, no risk of recursion.
 237         if let Some(expr) = maybe_expr {
 238             self.with_item_id_pushed(expr.id, |v| intravisit::walk_expr(v, expr), expr.span);
 239         }
 240     }
 241
 242     fn visit_trait_item(&mut self, ti: &'ast hir::TraitItem) {
 243         self.with_item_id_pushed(ti.id, |v| intravisit::walk_trait_item(v, ti), ti.span);
 244     }
 245
 246     fn visit_impl_item(&mut self, ii: &'ast hir::ImplItem) {
 247         self.with_item_id_pushed(ii.id, |v| intravisit::walk_impl_item(v, ii), ii.span);
 248     }
 249
 250     fn visit_expr(&mut self, e: &'ast hir::Expr) {
 251         match e.node {
 252             hir::ExprPath(..) => {
 253                 match self.def_map.get(&e.id).map(|d| d.base_def) {
 254                     Some(Def::Static(def_id, _)) |
 255                     Some(Def::AssociatedConst(def_id)) |
 256                     Some(Def::Const(def_id)) => {
 257                         if let Some(node_id) = self.ast_map.as_local_node_id(def_id) {
 258                             match self.ast_map.get(node_id) {
 259                                 ast_map::NodeItem(item) => self.visit_item(item),
 260                                 ast_map::NodeTraitItem(item) => self.visit_trait_item(item),
 261                                 ast_map::NodeImplItem(item) => self.visit_impl_item(item),
 262                                 ast_map::NodeForeignItem(_) => {}
 263                                 _ => {
 264                                     span_bug!(e.span,
 265                                               "expected item, found {}",
 266                                               self.ast_map.node_to_string(node_id));
 267                                 }
 268                             }
 269                         }
 270                     }
 271                     // For variants, we only want to check expressions that
 272                     // affect the specific variant used, but we need to check
 273                     // the whole enum definition to see what expression that
 274                     // might be (if any).
 275                     Some(Def::Variant(enum_id, variant_id)) => {
 276                         if let Some(enum_node_id) = self.ast_map.as_local_node_id(enum_id) {
 277                             if let hir::ItemEnum(ref enum_def, ref generics) = self.ast_map
 278                                 .expect_item(enum_node_id)
 279                                 .node {
 280                                 self.populate_enum_discriminants(enum_def);
 281                                 let enum_id = self.ast_map.as_local_node_id(enum_id).unwrap();
 282                                 let variant_id = self.ast_map.as_local_node_id(variant_id).unwrap();
 283                                 let variant = self.ast_map.expect_variant(variant_id);
 284                                 self.visit_variant(variant, generics, enum_id);
 285                             } else {
 286                                 span_bug!(e.span,
 287                                           "`check_static_recursion` found \
 288                                            non-enum in Def::Variant");
 289                             }
 290                         }
 291                     }
 292                     _ => (),
 293                 }
 294             }
 295             _ => (),
 296         }
 297         intravisit::walk_expr(self, e);
 298     }
 299 }