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
::hir
::map
as ast_map
;
16 use rustc
::session
::{Session, CompileResult}
;
17 use rustc
::hir
::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
::hir
::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 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 "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
);
281 "`check_static_recursion` found \
282 non-enum in Def::Variant");
291 intravisit
::walk_expr(self, e
);