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