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