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.
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.
11 // This compiler pass detects constants that refer to themselves
14 use rustc::dep_graph::DepNode;
15 use rustc::front::map as ast_map;
16 use rustc::session::{Session, CompileResult};
17 use rustc::middle::def::{Def, DefMap};
18 use rustc::util::nodemap::NodeMap;
21 use syntax::codemap::Span;
22 use syntax::feature_gate::{GateIssue, emit_feature_err};
23 use rustc_front::intravisit::{self, Visitor};
26 use std::cell::RefCell;
28 struct CheckCrateVisitor<'a, 'ast: 'a> {
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>>>,
39 impl<'a, 'ast: 'a> Visitor<'ast> for CheckCrateVisitor<'a, 'ast> {
40 fn visit_item(&mut self, it: &'ast hir::Item) {
43 hir::ItemConst(..) => {
44 let mut recursion_visitor =
45 CheckItemRecursionVisitor::new(self, &it.span);
46 recursion_visitor.visit_item(it);
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 =
55 CheckItemRecursionVisitor::new(self, &variant.span);
56 recursion_visitor.populate_enum_discriminants(enum_def);
57 recursion_visitor.visit_variant(variant, generics, it.id);
63 intravisit::walk_item(self, it)
66 fn visit_trait_item(&mut self, ti: &'ast hir::TraitItem) {
68 hir::ConstTraitItem(_, ref default) => {
69 if let Some(_) = *default {
70 let mut recursion_visitor =
71 CheckItemRecursionVisitor::new(self, &ti.span);
72 recursion_visitor.visit_trait_item(ti);
77 intravisit::walk_trait_item(self, ti)
80 fn visit_impl_item(&mut self, ii: &'ast hir::ImplItem) {
82 hir::ImplItemKind::Const(..) => {
83 let mut recursion_visitor =
84 CheckItemRecursionVisitor::new(self, &ii.span);
85 recursion_visitor.visit_impl_item(ii);
89 intravisit::walk_impl_item(self, ii)
93 pub fn check_crate<'ast>(sess: &Session,
95 ast_map: &ast_map::Map<'ast>)
97 let _task = ast_map.dep_graph.in_task(DepNode::CheckStaticRecursion);
99 let mut visitor = CheckCrateVisitor {
103 discriminant_map: RefCell::new(NodeMap()),
105 sess.track_errors(|| {
106 ast_map.krate().visit_all_items(&mut visitor);
110 struct CheckItemRecursionVisitor<'a, 'ast: 'a> {
113 ast_map: &'a ast_map::Map<'ast>,
115 discriminant_map: &'a RefCell<NodeMap<Option<&'ast hir::Expr>>>,
116 idstack: Vec<ast::NodeId>,
119 impl<'a, 'ast: 'a> CheckItemRecursionVisitor<'a, 'ast> {
120 fn new(v: &'a CheckCrateVisitor<'a, 'ast>, span: &'a Span)
121 -> CheckItemRecursionVisitor<'a, 'ast> {
122 CheckItemRecursionVisitor {
127 discriminant_map: &v.discriminant_map,
131 fn with_item_id_pushed<F>(&mut self, id: ast::NodeId, f: F)
132 where F: Fn(&mut Self) {
133 if self.idstack.iter().any(|&x| x == id) {
134 let any_static = self.idstack.iter().any(|&x| {
135 if let ast_map::NodeItem(item) = self.ast_map.get(x) {
136 if let hir::ItemStatic(..) = item.node {
146 if !self.sess.features.borrow().static_recursion {
147 emit_feature_err(&self.sess.parse_sess.span_diagnostic,
149 *self.root_span, GateIssue::Language, "recursive static");
152 span_err!(self.sess, *self.root_span, E0265, "recursive constant");
156 self.idstack.push(id);
160 // If a variant has an expression specifying its discriminant, then it needs
161 // to be checked just like a static or constant. However, if there are more
162 // variants with no explicitly specified discriminant, those variants will
163 // increment the same expression to get their values.
165 // So for every variant, we need to track whether there is an expression
166 // somewhere in the enum definition that controls its discriminant. We do
167 // this by starting from the end and searching backward.
168 fn populate_enum_discriminants(&self, enum_definition: &'ast hir::EnumDef) {
169 // Get the map, and return if we already processed this enum or if it
171 let mut discriminant_map = self.discriminant_map.borrow_mut();
172 match enum_definition.variants.first() {
174 Some(variant) if discriminant_map.contains_key(&variant.node.data.id()) => {
180 // Go through all the variants.
181 let mut variant_stack: Vec<ast::NodeId> = Vec::new();
182 for variant in enum_definition.variants.iter().rev() {
183 variant_stack.push(variant.node.data.id());
184 // When we find an expression, every variant currently on the stack
185 // is affected by that expression.
186 if let Some(ref expr) = variant.node.disr_expr {
187 for id in &variant_stack {
188 discriminant_map.insert(*id, Some(expr));
190 variant_stack.clear()
193 // If we are at the top, that always starts at 0, so any variant on the
194 // stack has a default value and does not need to be checked.
195 for id in &variant_stack {
196 discriminant_map.insert(*id, None);
201 impl<'a, 'ast: 'a> Visitor<'ast> for CheckItemRecursionVisitor<'a, 'ast> {
202 fn visit_item(&mut self, it: &'ast hir::Item) {
203 self.with_item_id_pushed(it.id, |v| intravisit::walk_item(v, it));
206 fn visit_enum_def(&mut self, enum_definition: &'ast hir::EnumDef,
207 generics: &'ast hir::Generics, item_id: ast::NodeId, _: Span) {
208 self.populate_enum_discriminants(enum_definition);
209 intravisit::walk_enum_def(self, enum_definition, generics, item_id);
212 fn visit_variant(&mut self, variant: &'ast hir::Variant,
213 _: &'ast hir::Generics, _: ast::NodeId) {
214 let variant_id = variant.node.data.id();
216 if let Some(get_expr) = self.discriminant_map.borrow().get(&variant_id) {
217 // This is necessary because we need to let the `discriminant_map`
218 // borrow fall out of scope, so that we can reborrow farther down.
219 maybe_expr = (*get_expr).clone();
221 self.sess.span_bug(variant.span,
222 "`check_static_recursion` attempted to visit \
223 variant with unknown discriminant")
225 // If `maybe_expr` is `None`, that's because no discriminant is
226 // specified that affects this variant. Thus, no risk of recursion.
227 if let Some(expr) = maybe_expr {
228 self.with_item_id_pushed(expr.id, |v| intravisit::walk_expr(v, expr));
232 fn visit_trait_item(&mut self, ti: &'ast hir::TraitItem) {
233 self.with_item_id_pushed(ti.id, |v| intravisit::walk_trait_item(v, ti));
236 fn visit_impl_item(&mut self, ii: &'ast hir::ImplItem) {
237 self.with_item_id_pushed(ii.id, |v| intravisit::walk_impl_item(v, ii));
240 fn visit_expr(&mut self, e: &'ast hir::Expr) {
242 hir::ExprPath(..) => {
243 match self.def_map.get(&e.id).map(|d| d.base_def) {
244 Some(Def::Static(def_id, _)) |
245 Some(Def::AssociatedConst(def_id)) |
246 Some(Def::Const(def_id)) => {
247 if let Some(node_id) = self.ast_map.as_local_node_id(def_id) {
248 match self.ast_map.get(node_id) {
249 ast_map::NodeItem(item) =>
250 self.visit_item(item),
251 ast_map::NodeTraitItem(item) =>
252 self.visit_trait_item(item),
253 ast_map::NodeImplItem(item) =>
254 self.visit_impl_item(item),
255 ast_map::NodeForeignItem(_) => {},
259 &format!("expected item, found {}",
260 self.ast_map.node_to_string(node_id)));
265 // For variants, we only want to check expressions that
266 // affect the specific variant used, but we need to check
267 // the whole enum definition to see what expression that
268 // might be (if any).
269 Some(Def::Variant(enum_id, variant_id)) => {
270 if let Some(enum_node_id) = self.ast_map.as_local_node_id(enum_id) {
271 if let hir::ItemEnum(ref enum_def, ref generics) =
272 self.ast_map.expect_item(enum_node_id).node
274 self.populate_enum_discriminants(enum_def);
275 let enum_id = self.ast_map.as_local_node_id(enum_id).unwrap();
276 let variant_id = self.ast_map.as_local_node_id(variant_id).unwrap();
277 let variant = self.ast_map.expect_variant(variant_id);
278 self.visit_variant(variant, generics, enum_id);
280 self.sess.span_bug(e.span,
281 "`check_static_recursion` found \
282 non-enum in Def::Variant");
291 intravisit::walk_expr(self, e);