Skip to content

Commit 6f1ae66

Browse files
borsbors
committed
Auto merge of #38069 - canndrew:empty-sub-patterns-again, r=nikomatsakis
Fix handling of empty types in patterns. Fix for #12609.
2 parents 42bed72 + 275c19d commit 6f1ae66

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

43 files changed

+1172
-300
lines changed

‎src/librustc/lint/builtin.rs

+7
Original file line numberDiff line numberDiff line change
@@ -70,6 +70,12 @@ declare_lint! {
7070
"detects unreachable code paths"
7171
}
7272

73+
declare_lint! {
74+
pub UNREACHABLE_PATTERNS,
75+
Warn,
76+
"detects unreachable patterns"
77+
}
78+
7379
declare_lint! {
7480
pub WARNINGS,
7581
Warn,
@@ -239,6 +245,7 @@ impl LintPass for HardwiredLints {
239245
UNUSED_ASSIGNMENTS,
240246
DEAD_CODE,
241247
UNREACHABLE_CODE,
248+
UNREACHABLE_PATTERNS,
242249
WARNINGS,
243250
UNUSED_FEATURES,
244251
STABLE_FEATURES,

‎src/librustc/mir/mod.rs

+4
Original file line numberDiff line numberDiff line change
@@ -888,6 +888,10 @@ impl<'tcx> Lvalue<'tcx> {
888888
self.elem(ProjectionElem::Deref)
889889
}
890890

891+
pub fn downcast(self, adt_def: &'tcx AdtDef, variant_index: usize) -> Lvalue<'tcx> {
892+
self.elem(ProjectionElem::Downcast(adt_def, variant_index))
893+
}
894+
891895
pub fn index(self, index: Operand<'tcx>) -> Lvalue<'tcx> {
892896
self.elem(ProjectionElem::Index(index))
893897
}

‎src/librustc/ty/context.rs

+4
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,7 @@ use ty::{BareFnTy, InferTy, ParamTy, ProjectionTy, ExistentialPredicate};
3333
use ty::{TyVar, TyVid, IntVar, IntVid, FloatVar, FloatVid};
3434
use ty::TypeVariants::*;
3535
use ty::layout::{Layout, TargetDataLayout};
36+
use ty::inhabitedness::DefIdForest;
3637
use ty::maps;
3738
use util::common::MemoizationMap;
3839
use util::nodemap::{NodeMap, NodeSet, DefIdMap, DefIdSet};
@@ -459,6 +460,8 @@ pub struct GlobalCtxt<'tcx> {
459460
// FIXME dep tracking -- should be harmless enough
460461
pub normalized_cache: RefCell<FxHashMap<Ty<'tcx>, Ty<'tcx>>>,
461462

463+
pub inhabitedness_cache: RefCell<FxHashMap<Ty<'tcx>, DefIdForest>>,
464+
462465
pub lang_items: middle::lang_items::LanguageItems,
463466

464467
/// Maps from def-id of a type or region parameter to its
@@ -760,6 +763,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
760763
associated_item_def_ids: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
761764
ty_param_defs: RefCell::new(NodeMap()),
762765
normalized_cache: RefCell::new(FxHashMap()),
766+
inhabitedness_cache: RefCell::new(FxHashMap()),
763767
lang_items: lang_items,
764768
inherent_impls: RefCell::new(DepTrackingMap::new(dep_graph.clone())),
765769
used_unsafe: RefCell::new(NodeSet()),

‎src/librustc/ty/inhabitedness/def_id_forest.rs

+133
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,133 @@
1+
// Copyright 2012-2015 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+
use std::mem;
12+
use rustc_data_structures::small_vec::SmallVec;
13+
use syntax::ast::CRATE_NODE_ID;
14+
use ty::context::TyCtxt;
15+
use ty::{DefId, DefIdTree};
16+
17+
/// Represents a forest of DefIds closed under the ancestor relation. That is,
18+
/// if a DefId representing a module is contained in the forest then all
19+
/// DefIds defined in that module or submodules are also implicitly contained
20+
/// in the forest.
21+
///
22+
/// This is used to represent a set of modules in which a type is visibly
23+
/// uninhabited.
24+
#[derive(Clone)]
25+
pub struct DefIdForest {
26+
/// The minimal set of DefIds required to represent the whole set.
27+
/// If A and B are DefIds in the DefIdForest, and A is a desecendant
28+
/// of B, then only B will be in root_ids.
29+
/// We use a SmallVec here because (for its use for cacheing inhabitedness)
30+
/// its rare that this will contain even two ids.
31+
root_ids: SmallVec<[DefId; 1]>,
32+
}
33+
34+
impl<'a, 'gcx, 'tcx> DefIdForest {
35+
/// Create an empty forest.
36+
pub fn empty() -> DefIdForest {
37+
DefIdForest {
38+
root_ids: SmallVec::new(),
39+
}
40+
}
41+
42+
/// Create a forest consisting of a single tree representing the entire
43+
/// crate.
44+
#[inline]
45+
pub fn full(tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest {
46+
let crate_id = tcx.map.local_def_id(CRATE_NODE_ID);
47+
DefIdForest::from_id(crate_id)
48+
}
49+
50+
/// Create a forest containing a DefId and all its descendants.
51+
pub fn from_id(id: DefId) -> DefIdForest {
52+
let mut root_ids = SmallVec::new();
53+
root_ids.push(id);
54+
DefIdForest {
55+
root_ids: root_ids,
56+
}
57+
}
58+
59+
/// Test whether the forest is empty.
60+
pub fn is_empty(&self) -> bool {
61+
self.root_ids.is_empty()
62+
}
63+
64+
/// Test whether the forest conains a given DefId.
65+
pub fn contains(&self,
66+
tcx: TyCtxt<'a, 'gcx, 'tcx>,
67+
id: DefId) -> bool
68+
{
69+
for root_id in self.root_ids.iter() {
70+
if tcx.is_descendant_of(id, *root_id) {
71+
return true;
72+
}
73+
}
74+
false
75+
}
76+
77+
/// Calculate the intersection of a collection of forests.
78+
pub fn intersection<I>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
79+
iter: I) -> DefIdForest
80+
where I: IntoIterator<Item=DefIdForest>
81+
{
82+
let mut ret = DefIdForest::full(tcx);
83+
let mut next_ret = SmallVec::new();
84+
let mut old_ret: SmallVec<[DefId; 1]> = SmallVec::new();
85+
for next_forest in iter {
86+
for id in ret.root_ids.drain(..) {
87+
if next_forest.contains(tcx, id) {
88+
next_ret.push(id);
89+
} else {
90+
old_ret.push(id);
91+
}
92+
}
93+
ret.root_ids.extend(old_ret.drain(..));
94+
95+
for id in next_forest.root_ids {
96+
if ret.contains(tcx, id) {
97+
next_ret.push(id);
98+
}
99+
}
100+
101+
mem::swap(&mut next_ret, &mut ret.root_ids);
102+
next_ret.drain(..);
103+
}
104+
ret
105+
}
106+
107+
/// Calculate the union of a collection of forests.
108+
pub fn union<I>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
109+
iter: I) -> DefIdForest
110+
where I: IntoIterator<Item=DefIdForest>
111+
{
112+
let mut ret = DefIdForest::empty();
113+
let mut next_ret = SmallVec::new();
114+
for next_forest in iter {
115+
for id in ret.root_ids.drain(..) {
116+
if !next_forest.contains(tcx, id) {
117+
next_ret.push(id);
118+
}
119+
}
120+
121+
for id in next_forest.root_ids {
122+
if !next_ret.contains(&id) {
123+
next_ret.push(id);
124+
}
125+
}
126+
127+
mem::swap(&mut next_ret, &mut ret.root_ids);
128+
next_ret.drain(..);
129+
}
130+
ret
131+
}
132+
}
133+

‎src/librustc/ty/inhabitedness/mod.rs

+199
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,199 @@
1+
// Copyright 2012-2015 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+
use util::nodemap::FxHashSet;
12+
use ty::context::TyCtxt;
13+
use ty::{AdtDef, VariantDef, FieldDef, TyS};
14+
use ty::{DefId, Substs};
15+
use ty::{AdtKind, Visibility};
16+
use ty::TypeVariants::*;
17+
18+
pub use self::def_id_forest::DefIdForest;
19+
20+
mod def_id_forest;
21+
22+
// The methods in this module calculate DefIdForests of modules in which a
23+
// AdtDef/VariantDef/FieldDef is visibly uninhabited.
24+
//
25+
// # Example
26+
// ```rust
27+
// enum Void {}
28+
// mod a {
29+
// pub mod b {
30+
// pub struct SecretlyUninhabited {
31+
// _priv: !,
32+
// }
33+
// }
34+
// }
35+
//
36+
// mod c {
37+
// pub struct AlsoSecretlyUninhabited {
38+
// _priv: Void,
39+
// }
40+
// mod d {
41+
// }
42+
// }
43+
//
44+
// struct Foo {
45+
// x: a::b::SecretlyUninhabited,
46+
// y: c::AlsoSecretlyUninhabited,
47+
// }
48+
// ```
49+
// In this code, the type Foo will only be visibly uninhabited inside the
50+
// modules b, c and d. Calling uninhabited_from on Foo or its AdtDef will
51+
// return the forest of modules {b, c->d} (represented in a DefIdForest by the
52+
// set {b, c})
53+
//
54+
// We need this information for pattern-matching on Foo or types that contain
55+
// Foo.
56+
//
57+
// # Example
58+
// ```rust
59+
// let foo_result: Result<T, Foo> = ... ;
60+
// let Ok(t) = foo_result;
61+
// ```
62+
// This code should only compile in modules where the uninhabitedness of Foo is
63+
// visible.
64+
65+
impl<'a, 'gcx, 'tcx> AdtDef {
66+
/// Calculate the forest of DefIds from which this adt is visibly uninhabited.
67+
pub fn uninhabited_from(
68+
&self,
69+
visited: &mut FxHashSet<(DefId, &'tcx Substs<'tcx>)>,
70+
tcx: TyCtxt<'a, 'gcx, 'tcx>,
71+
substs: &'tcx Substs<'tcx>) -> DefIdForest
72+
{
73+
if !visited.insert((self.did, substs)) {
74+
return DefIdForest::empty();
75+
}
76+
77+
let ret = DefIdForest::intersection(tcx, self.variants.iter().map(|v| {
78+
v.uninhabited_from(visited, tcx, substs, self.adt_kind())
79+
}));
80+
visited.remove(&(self.did, substs));
81+
ret
82+
}
83+
}
84+
85+
impl<'a, 'gcx, 'tcx> VariantDef {
86+
/// Calculate the forest of DefIds from which this variant is visibly uninhabited.
87+
pub fn uninhabited_from(
88+
&self,
89+
visited: &mut FxHashSet<(DefId, &'tcx Substs<'tcx>)>,
90+
tcx: TyCtxt<'a, 'gcx, 'tcx>,
91+
substs: &'tcx Substs<'tcx>,
92+
adt_kind: AdtKind) -> DefIdForest
93+
{
94+
match adt_kind {
95+
AdtKind::Union => {
96+
DefIdForest::intersection(tcx, self.fields.iter().map(|f| {
97+
f.uninhabited_from(visited, tcx, substs, false)
98+
}))
99+
},
100+
AdtKind::Struct => {
101+
DefIdForest::union(tcx, self.fields.iter().map(|f| {
102+
f.uninhabited_from(visited, tcx, substs, false)
103+
}))
104+
},
105+
AdtKind::Enum => {
106+
DefIdForest::union(tcx, self.fields.iter().map(|f| {
107+
f.uninhabited_from(visited, tcx, substs, true)
108+
}))
109+
},
110+
}
111+
}
112+
}
113+
114+
impl<'a, 'gcx, 'tcx> FieldDef {
115+
/// Calculate the forest of DefIds from which this field is visibly uninhabited.
116+
pub fn uninhabited_from(
117+
&self,
118+
visited: &mut FxHashSet<(DefId, &'tcx Substs<'tcx>)>,
119+
tcx: TyCtxt<'a, 'gcx, 'tcx>,
120+
substs: &'tcx Substs<'tcx>,
121+
is_enum: bool) -> DefIdForest
122+
{
123+
let mut data_uninhabitedness = move || self.ty(tcx, substs).uninhabited_from(visited, tcx);
124+
// FIXME(canndrew): Currently enum fields are (incorrectly) stored with
125+
// Visibility::Invisible so we need to override self.vis if we're
126+
// dealing with an enum.
127+
if is_enum {
128+
data_uninhabitedness()
129+
} else {
130+
match self.vis {
131+
Visibility::Invisible => DefIdForest::empty(),
132+
Visibility::Restricted(from) => {
133+
let forest = DefIdForest::from_id(from);
134+
let iter = Some(forest).into_iter().chain(Some(data_uninhabitedness()));
135+
DefIdForest::intersection(tcx, iter)
136+
},
137+
Visibility::Public => data_uninhabitedness(),
138+
}
139+
}
140+
}
141+
}
142+
143+
impl<'a, 'gcx, 'tcx> TyS<'tcx> {
144+
/// Calculate the forest of DefIds from which this type is visibly uninhabited.
145+
pub fn uninhabited_from(
146+
&self,
147+
visited: &mut FxHashSet<(DefId, &'tcx Substs<'tcx>)>,
148+
tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest
149+
{
150+
match tcx.lift_to_global(&self) {
151+
Some(global_ty) => {
152+
{
153+
let cache = tcx.inhabitedness_cache.borrow();
154+
if let Some(forest) = cache.get(&global_ty) {
155+
return forest.clone();
156+
}
157+
}
158+
let forest = global_ty.uninhabited_from_inner(visited, tcx);
159+
let mut cache = tcx.inhabitedness_cache.borrow_mut();
160+
cache.insert(global_ty, forest.clone());
161+
forest
162+
},
163+
None => {
164+
let forest = self.uninhabited_from_inner(visited, tcx);
165+
forest
166+
},
167+
}
168+
}
169+
170+
fn uninhabited_from_inner(
171+
&self,
172+
visited: &mut FxHashSet<(DefId, &'tcx Substs<'tcx>)>,
173+
tcx: TyCtxt<'a, 'gcx, 'tcx>) -> DefIdForest
174+
{
175+
match self.sty {
176+
TyAdt(def, substs) => {
177+
def.uninhabited_from(visited, tcx, substs)
178+
},
179+
180+
TyNever => DefIdForest::full(tcx),
181+
TyTuple(ref tys) => {
182+
DefIdForest::union(tcx, tys.iter().map(|ty| {
183+
ty.uninhabited_from(visited, tcx)
184+
}))
185+
},
186+
TyArray(ty, len) => {
187+
if len == 0 {
188+
DefIdForest::empty()
189+
} else {
190+
ty.uninhabited_from(visited, tcx)
191+
}
192+
}
193+
TyRef(_, ref tm) => tm.ty.uninhabited_from(visited, tcx),
194+
195+
_ => DefIdForest::empty(),
196+
}
197+
}
198+
}
199+

0 commit comments

Comments
 (0)