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 hir_map
;
16 use rustc
::session
::{CompileResult, Session}
;
17 use rustc
::hir
::def
::{Def, CtorKind}
;
18 use rustc
::util
::nodemap
::{NodeMap, NodeSet}
;
21 use syntax
::feature_gate
::{GateIssue, emit_feature_err}
;
23 use rustc
::hir
::intravisit
::{self, Visitor, NestedVisitorMap}
;
26 struct CheckCrateVisitor
<'a
, 'hir
: 'a
> {
28 hir_map
: &'a hir_map
::Map
<'hir
>,
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
<hir
::BodyId
>>,
34 detected_recursive_ids
: NodeSet
,
37 impl<'a
, 'hir
: 'a
> Visitor
<'hir
> for CheckCrateVisitor
<'a
, 'hir
> {
38 fn nested_visit_map
<'this
>(&'this
mut self) -> NestedVisitorMap
<'this
, 'hir
> {
39 NestedVisitorMap
::None
42 fn visit_item(&mut self, it
: &'hir hir
::Item
) {
45 hir
::ItemConst(..) => {
46 let mut recursion_visitor
= CheckItemRecursionVisitor
::new(self, &it
.span
);
47 recursion_visitor
.visit_item(it
);
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,
57 recursion_visitor
.populate_enum_discriminants(enum_def
);
58 recursion_visitor
.visit_variant(variant
, generics
, it
.id
);
64 intravisit
::walk_item(self, it
)
67 fn visit_trait_item(&mut self, ti
: &'hir hir
::TraitItem
) {
69 hir
::TraitItemKind
::Const(_
, ref default) => {
70 if let Some(_
) = *default {
71 let mut recursion_visitor
= 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
: &'hir hir
::ImplItem
) {
82 hir
::ImplItemKind
::Const(..) => {
83 let mut recursion_visitor
= CheckItemRecursionVisitor
::new(self, &ii
.span
);
84 recursion_visitor
.visit_impl_item(ii
);
88 intravisit
::walk_impl_item(self, ii
)
92 pub fn check_crate
<'hir
>(sess
: &Session
, hir_map
: &hir_map
::Map
<'hir
>) -> CompileResult
{
93 let _task
= hir_map
.dep_graph
.in_task(DepNode
::CheckStaticRecursion
);
95 let mut visitor
= CheckCrateVisitor
{
98 discriminant_map
: NodeMap(),
99 detected_recursive_ids
: NodeSet(),
101 sess
.track_errors(|| {
102 // FIXME(#37712) could use ItemLikeVisitor if trait items were item-like
103 hir_map
.krate().visit_all_item_likes(&mut visitor
.as_deep_visitor());
107 struct CheckItemRecursionVisitor
<'a
, 'b
: 'a
, 'hir
: 'b
> {
110 hir_map
: &'b hir_map
::Map
<'hir
>,
111 discriminant_map
: &'a
mut NodeMap
<Option
<hir
::BodyId
>>,
112 idstack
: Vec
<ast
::NodeId
>,
113 detected_recursive_ids
: &'a
mut NodeSet
,
116 impl<'a
, 'b
: 'a
, 'hir
: 'b
> CheckItemRecursionVisitor
<'a
, 'b
, 'hir
> {
117 fn new(v
: &'a
mut CheckCrateVisitor
<'b
, 'hir
>, span
: &'b Span
) -> Self {
118 CheckItemRecursionVisitor
{
122 discriminant_map
: &mut v
.discriminant_map
,
124 detected_recursive_ids
: &mut v
.detected_recursive_ids
,
127 fn with_item_id_pushed
<F
>(&mut self, id
: ast
::NodeId
, f
: F
, span
: Span
)
128 where F
: Fn(&mut Self)
130 if self.idstack
.iter().any(|&x
| x
== id
) {
131 if self.detected_recursive_ids
.contains(&id
) {
134 self.detected_recursive_ids
.insert(id
);
135 let any_static
= self.idstack
.iter().any(|&x
| {
136 if let hir_map
::NodeItem(item
) = self.hir_map
.get(x
) {
137 if let hir
::ItemStatic(..) = item
.node
{
147 if !self.sess
.features
.borrow().static_recursion
{
148 emit_feature_err(&self.sess
.parse_sess
,
155 struct_span_err
!(self.sess
, span
, E0265
, "recursive constant")
156 .span_label(span
, &format
!("recursion not allowed in constant"))
161 self.idstack
.push(id
);
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.
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
: &'hir hir
::EnumDef
) {
174 // Get the map, and return if we already processed this enum or if it
176 match enum_definition
.variants
.first() {
180 Some(variant
) if self.discriminant_map
.contains_key(&variant
.node
.data
.id()) => {
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(expr
) = variant
.node
.disr_expr
{
193 for id
in &variant_stack
{
194 self.discriminant_map
.insert(*id
, Some(expr
));
196 variant_stack
.clear()
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
);
207 impl<'a
, 'b
: 'a
, 'hir
: 'b
> Visitor
<'hir
> for CheckItemRecursionVisitor
<'a
, 'b
, 'hir
> {
208 fn nested_visit_map
<'this
>(&'this
mut self) -> NestedVisitorMap
<'this
, 'hir
> {
209 NestedVisitorMap
::OnlyBodies(&self.hir_map
)
211 fn visit_item(&mut self, it
: &'hir hir
::Item
) {
212 self.with_item_id_pushed(it
.id
, |v
| intravisit
::walk_item(v
, it
), it
.span
);
215 fn visit_enum_def(&mut self,
216 enum_definition
: &'hir hir
::EnumDef
,
217 generics
: &'hir hir
::Generics
,
218 item_id
: ast
::NodeId
,
220 self.populate_enum_discriminants(enum_definition
);
221 intravisit
::walk_enum_def(self, enum_definition
, generics
, item_id
);
224 fn visit_variant(&mut self,
225 variant
: &'hir hir
::Variant
,
226 _
: &'hir hir
::Generics
,
228 let variant_id
= variant
.node
.data
.id();
229 let maybe_expr
= *self.discriminant_map
.get(&variant_id
).unwrap_or_else(|| {
230 span_bug
!(variant
.span
,
231 "`check_static_recursion` attempted to visit \
232 variant with unknown discriminant")
234 // If `maybe_expr` is `None`, that's because no discriminant is
235 // specified that affects this variant. Thus, no risk of recursion.
236 if let Some(expr
) = maybe_expr
{
237 let expr
= &self.hir_map
.body(expr
).value
;
238 self.with_item_id_pushed(expr
.id
, |v
| intravisit
::walk_expr(v
, expr
), expr
.span
);
242 fn visit_trait_item(&mut self, ti
: &'hir hir
::TraitItem
) {
243 self.with_item_id_pushed(ti
.id
, |v
| intravisit
::walk_trait_item(v
, ti
), ti
.span
);
246 fn visit_impl_item(&mut self, ii
: &'hir hir
::ImplItem
) {
247 self.with_item_id_pushed(ii
.id
, |v
| intravisit
::walk_impl_item(v
, ii
), ii
.span
);
250 fn visit_path(&mut self, path
: &'hir hir
::Path
, _
: ast
::NodeId
) {
252 Def
::Static(def_id
, _
) |
253 Def
::AssociatedConst(def_id
) |
254 Def
::Const(def_id
) => {
255 if let Some(node_id
) = self.hir_map
.as_local_node_id(def_id
) {
256 match self.hir_map
.get(node_id
) {
257 hir_map
::NodeItem(item
) => self.visit_item(item
),
258 hir_map
::NodeTraitItem(item
) => self.visit_trait_item(item
),
259 hir_map
::NodeImplItem(item
) => self.visit_impl_item(item
),
260 hir_map
::NodeForeignItem(_
) => {}
263 "expected item, found {}",
264 self.hir_map
.node_to_string(node_id
));
269 // For variants, we only want to check expressions that
270 // affect the specific variant used, but we need to check
271 // the whole enum definition to see what expression that
272 // might be (if any).
273 Def
::VariantCtor(variant_id
, CtorKind
::Const
) => {
274 if let Some(variant_id
) = self.hir_map
.as_local_node_id(variant_id
) {
275 let variant
= self.hir_map
.expect_variant(variant_id
);
276 let enum_id
= self.hir_map
.get_parent(variant_id
);
277 let enum_item
= self.hir_map
.expect_item(enum_id
);
278 if let hir
::ItemEnum(ref enum_def
, ref generics
) = enum_item
.node
{
279 self.populate_enum_discriminants(enum_def
);
280 self.visit_variant(variant
, generics
, enum_id
);
283 "`check_static_recursion` found \
284 non-enum in Def::VariantCtor");
290 intravisit
::walk_path(self, path
);