From e97089dae33d5b228bb1b50ae12e96b13ab499b3 Mon Sep 17 00:00:00 2001 From: Oliver Schneider Date: Wed, 27 Dec 2017 21:32:01 +0100 Subject: Move librustc_const_eval to librustc_mir --- src/doc/rustc-ux-guidelines.md | 1 - src/librustc/dep_graph/dep_node.rs | 1 - src/librustc/ty/maps/config.rs | 1 - src/librustc_const_eval/Cargo.toml | 19 - src/librustc_const_eval/_match.rs | 1217 ---------------------------- src/librustc_const_eval/check_match.rs | 636 --------------- src/librustc_const_eval/diagnostics.rs | 571 ------------- src/librustc_const_eval/eval.rs | 697 ---------------- src/librustc_const_eval/pattern.rs | 1069 ------------------------ src/librustc_driver/Cargo.toml | 1 - src/librustc_driver/driver.rs | 3 +- src/librustc_driver/lib.rs | 2 - src/librustc_lint/Cargo.toml | 2 +- src/librustc_lint/lib.rs | 2 +- src/librustc_lint/types.rs | 2 +- src/librustc_mir/Cargo.toml | 2 +- src/librustc_mir/build/mod.rs | 2 +- src/librustc_mir/const_eval/_match.rs | 1217 ++++++++++++++++++++++++++++ src/librustc_mir/const_eval/check_match.rs | 636 +++++++++++++++ src/librustc_mir/const_eval/eval.rs | 697 ++++++++++++++++ src/librustc_mir/const_eval/mod.rs | 18 + src/librustc_mir/const_eval/pattern.rs | 1070 ++++++++++++++++++++++++ src/librustc_mir/diagnostics.rs | 550 +++++++++++++ src/librustc_mir/hair/mod.rs | 2 +- src/librustc_mir/interpret/const_eval.rs | 34 +- src/librustc_mir/lib.rs | 6 +- src/librustc_passes/Cargo.toml | 2 +- src/librustc_passes/consts.rs | 2 +- src/librustc_passes/lib.rs | 2 +- 29 files changed, 4224 insertions(+), 4240 deletions(-) delete mode 100644 src/librustc_const_eval/Cargo.toml delete mode 100644 src/librustc_const_eval/_match.rs delete mode 100644 src/librustc_const_eval/check_match.rs delete mode 100644 src/librustc_const_eval/diagnostics.rs delete mode 100644 src/librustc_const_eval/eval.rs delete mode 100644 src/librustc_const_eval/pattern.rs create mode 100644 src/librustc_mir/const_eval/_match.rs create mode 100644 src/librustc_mir/const_eval/check_match.rs create mode 100644 src/librustc_mir/const_eval/eval.rs create mode 100644 src/librustc_mir/const_eval/mod.rs create mode 100644 src/librustc_mir/const_eval/pattern.rs diff --git a/src/doc/rustc-ux-guidelines.md b/src/doc/rustc-ux-guidelines.md index 323d49e4691..b62762ef69e 100644 --- a/src/doc/rustc-ux-guidelines.md +++ b/src/doc/rustc-ux-guidelines.md @@ -64,7 +64,6 @@ for details on how to format and write long error codes. [librustc](https://github.com/rust-lang/rust/blob/master/src/librustc/diagnostics.rs), [libsyntax](https://github.com/rust-lang/rust/blob/master/src/libsyntax/diagnostics.rs), [librustc_borrowck](https://github.com/rust-lang/rust/blob/master/src/librustc_borrowck/diagnostics.rs), - [librustc_const_eval](https://github.com/rust-lang/rust/blob/master/src/librustc_const_eval/diagnostics.rs), [librustc_metadata](https://github.com/rust-lang/rust/blob/master/src/librustc_metadata/diagnostics.rs), [librustc_mir](https://github.com/rust-lang/rust/blob/master/src/librustc_mir/diagnostics.rs), [librustc_passes](https://github.com/rust-lang/rust/blob/master/src/librustc_passes/diagnostics.rs), diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs index 15e1d38be69..ed46296389d 100644 --- a/src/librustc/dep_graph/dep_node.rs +++ b/src/librustc/dep_graph/dep_node.rs @@ -63,7 +63,6 @@ use hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX}; use hir::map::DefPathHash; use hir::{HirId, ItemLocalId}; -use mir; use ich::Fingerprint; use ty::{TyCtxt, Instance, InstanceDef, ParamEnv, ParamEnvAnd, PolyTraitRef, Ty}; diff --git a/src/librustc/ty/maps/config.rs b/src/librustc/ty/maps/config.rs index ef1c8a8d4fa..d880b022e2f 100644 --- a/src/librustc/ty/maps/config.rs +++ b/src/librustc/ty/maps/config.rs @@ -13,7 +13,6 @@ use hir::def_id::{CrateNum, DefId, DefIndex}; use ty::{self, Ty, TyCtxt}; use ty::maps::queries; use ty::subst::Substs; -use mir; use std::hash::Hash; use syntax_pos::symbol::InternedString; diff --git a/src/librustc_const_eval/Cargo.toml b/src/librustc_const_eval/Cargo.toml deleted file mode 100644 index 53b8402ab2a..00000000000 --- a/src/librustc_const_eval/Cargo.toml +++ /dev/null @@ -1,19 +0,0 @@ -[package] -authors = ["The Rust Project Developers"] -name = "rustc_const_eval" -version = "0.0.0" - -[lib] -name = "rustc_const_eval" -path = "lib.rs" -crate-type = ["dylib"] - -[dependencies] -arena = { path = "../libarena" } -log = "0.4" -rustc = { path = "../librustc" } -rustc_const_math = { path = "../librustc_const_math" } -rustc_data_structures = { path = "../librustc_data_structures" } -rustc_errors = { path = "../librustc_errors" } -syntax = { path = "../libsyntax" } -syntax_pos = { path = "../libsyntax_pos" } diff --git a/src/librustc_const_eval/_match.rs b/src/librustc_const_eval/_match.rs deleted file mode 100644 index 9e9eb4a81d0..00000000000 --- a/src/librustc_const_eval/_match.rs +++ /dev/null @@ -1,1217 +0,0 @@ -// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -use self::Constructor::*; -use self::Usefulness::*; -use self::WitnessPreference::*; - -use rustc::middle::const_val::ConstVal; -use eval::{compare_const_vals}; - -use rustc_const_math::ConstInt; - -use rustc_data_structures::fx::FxHashMap; -use rustc_data_structures::indexed_vec::Idx; - -use pattern::{FieldPattern, Pattern, PatternKind}; -use pattern::{PatternFoldable, PatternFolder}; - -use rustc::hir::def_id::DefId; -use rustc::hir::RangeEnd; -use rustc::ty::{self, Ty, TyCtxt, TypeFoldable}; - -use rustc::mir::Field; -use rustc::mir::interpret::{Value, PrimVal}; -use rustc::util::common::ErrorReported; - -use syntax_pos::{Span, DUMMY_SP}; - -use arena::TypedArena; - -use std::cmp::{self, Ordering}; -use std::fmt; -use std::iter::{FromIterator, IntoIterator, repeat}; - -pub fn expand_pattern<'a, 'tcx>(cx: &MatchCheckCtxt<'a, 'tcx>, pat: Pattern<'tcx>) - -> &'a Pattern<'tcx> -{ - cx.pattern_arena.alloc(LiteralExpander.fold_pattern(&pat)) -} - -struct LiteralExpander; -impl<'tcx> PatternFolder<'tcx> for LiteralExpander { - fn fold_pattern(&mut self, pat: &Pattern<'tcx>) -> Pattern<'tcx> { - match (&pat.ty.sty, &*pat.kind) { - (&ty::TyRef(_, mt), &PatternKind::Constant { ref value }) => { - Pattern { - ty: pat.ty, - span: pat.span, - kind: box PatternKind::Deref { - subpattern: Pattern { - ty: mt.ty, - span: pat.span, - kind: box PatternKind::Constant { value: value.clone() }, - } - } - } - } - (_, &PatternKind::Binding { subpattern: Some(ref s), .. }) => { - s.fold_with(self) - } - _ => pat.super_fold_with(self) - } - } -} - -impl<'tcx> Pattern<'tcx> { - fn is_wildcard(&self) -> bool { - match *self.kind { - PatternKind::Binding { subpattern: None, .. } | PatternKind::Wild => - true, - _ => false - } - } -} - -pub struct Matrix<'a, 'tcx: 'a>(Vec>>); - -impl<'a, 'tcx> Matrix<'a, 'tcx> { - pub fn empty() -> Self { - Matrix(vec![]) - } - - pub fn push(&mut self, row: Vec<&'a Pattern<'tcx>>) { - self.0.push(row) - } -} - -/// Pretty-printer for matrices of patterns, example: -/// ++++++++++++++++++++++++++ -/// + _ + [] + -/// ++++++++++++++++++++++++++ -/// + true + [First] + -/// ++++++++++++++++++++++++++ -/// + true + [Second(true)] + -/// ++++++++++++++++++++++++++ -/// + false + [_] + -/// ++++++++++++++++++++++++++ -/// + _ + [_, _, ..tail] + -/// ++++++++++++++++++++++++++ -impl<'a, 'tcx> fmt::Debug for Matrix<'a, 'tcx> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - write!(f, "\n")?; - - let &Matrix(ref m) = self; - let pretty_printed_matrix: Vec> = m.iter().map(|row| { - row.iter().map(|pat| format!("{:?}", pat)).collect() - }).collect(); - - let column_count = m.iter().map(|row| row.len()).max().unwrap_or(0); - assert!(m.iter().all(|row| row.len() == column_count)); - let column_widths: Vec = (0..column_count).map(|col| { - pretty_printed_matrix.iter().map(|row| row[col].len()).max().unwrap_or(0) - }).collect(); - - let total_width = column_widths.iter().cloned().sum::() + column_count * 3 + 1; - let br = repeat('+').take(total_width).collect::(); - write!(f, "{}\n", br)?; - for row in pretty_printed_matrix { - write!(f, "+")?; - for (column, pat_str) in row.into_iter().enumerate() { - write!(f, " ")?; - write!(f, "{:1$}", pat_str, column_widths[column])?; - write!(f, " +")?; - } - write!(f, "\n")?; - write!(f, "{}\n", br)?; - } - Ok(()) - } -} - -impl<'a, 'tcx> FromIterator>> for Matrix<'a, 'tcx> { - fn from_iter>>>(iter: T) -> Self - { - Matrix(iter.into_iter().collect()) - } -} - -//NOTE: appears to be the only place other then InferCtxt to contain a ParamEnv -pub struct MatchCheckCtxt<'a, 'tcx: 'a> { - pub tcx: TyCtxt<'a, 'tcx, 'tcx>, - /// The module in which the match occurs. This is necessary for - /// checking inhabited-ness of types because whether a type is (visibly) - /// inhabited can depend on whether it was defined in the current module or - /// not. eg. `struct Foo { _private: ! }` cannot be seen to be empty - /// outside it's module and should not be matchable with an empty match - /// statement. - pub module: DefId, - pub pattern_arena: &'a TypedArena>, - pub byte_array_map: FxHashMap<*const Pattern<'tcx>, Vec<&'a Pattern<'tcx>>>, -} - -impl<'a, 'tcx> MatchCheckCtxt<'a, 'tcx> { - pub fn create_and_enter( - tcx: TyCtxt<'a, 'tcx, 'tcx>, - module: DefId, - f: F) -> R - where F: for<'b> FnOnce(MatchCheckCtxt<'b, 'tcx>) -> R - { - let pattern_arena = TypedArena::new(); - - f(MatchCheckCtxt { - tcx, - module, - pattern_arena: &pattern_arena, - byte_array_map: FxHashMap(), - }) - } - - // convert a byte-string pattern to a list of u8 patterns. - fn lower_byte_str_pattern<'p>(&mut self, pat: &'p Pattern<'tcx>) -> Vec<&'p Pattern<'tcx>> - where 'a: 'p - { - let pattern_arena = &*self.pattern_arena; - let tcx = self.tcx; - self.byte_array_map.entry(pat).or_insert_with(|| { - match pat.kind { - box PatternKind::Constant { - value: &ty::Const { val: ConstVal::ByteStr(b), .. } - } => { - b.data.iter().map(|&b| &*pattern_arena.alloc(Pattern { - ty: tcx.types.u8, - span: pat.span, - kind: box PatternKind::Constant { - value: tcx.mk_const(ty::Const { - val: ConstVal::Integral(ConstInt::U8(b)), - ty: tcx.types.u8 - }) - } - })).collect() - } - box PatternKind::Constant { - value: &ty::Const { val: ConstVal::Value(b), ty } - } => { - match b { - Value::ByVal(PrimVal::Ptr(ptr)) => { - let is_array_ptr = ty - .builtin_deref(true, ty::NoPreference) - .and_then(|t| t.ty.builtin_index()) - .map_or(false, |t| t == tcx.types.u8); - assert!(is_array_ptr); - let alloc = tcx - .interpret_interner - .borrow() - .get_alloc(ptr.alloc_id.0) - .unwrap(); - assert_eq!(ptr.offset, 0); - // FIXME: check length - alloc.bytes.iter().map(|b| { - &*pattern_arena.alloc(Pattern { - ty: tcx.types.u8, - span: pat.span, - kind: box PatternKind::Constant { - value: tcx.mk_const(ty::Const { - val: ConstVal::Value(Value::ByVal( - PrimVal::Bytes(*b as u128), - )), - ty: tcx.types.u8 - }) - } - }) - }).collect() - }, - _ => bug!("not a byte str: {:?}", b), - } - } - _ => span_bug!(pat.span, "unexpected byte array pattern {:?}", pat) - } - }).clone() - } - - fn is_uninhabited(&self, ty: Ty<'tcx>) -> bool { - if self.tcx.features().never_type { - self.tcx.is_ty_uninhabited_from(self.module, ty) - } else { - false - } - } - - fn is_non_exhaustive_enum(&self, ty: Ty<'tcx>) -> bool { - match ty.sty { - ty::TyAdt(adt_def, ..) => adt_def.is_enum() && adt_def.is_non_exhaustive(), - _ => false, - } - } - - fn is_local(&self, ty: Ty<'tcx>) -> bool { - match ty.sty { - ty::TyAdt(adt_def, ..) => adt_def.did.is_local(), - _ => false, - } - } - - fn is_variant_uninhabited(&self, - variant: &'tcx ty::VariantDef, - substs: &'tcx ty::subst::Substs<'tcx>) - -> bool - { - if self.tcx.features().never_type { - self.tcx.is_enum_variant_uninhabited_from(self.module, variant, substs) - } else { - false - } - } -} - -#[derive(Clone, Debug, PartialEq)] -pub enum Constructor<'tcx> { - /// The constructor of all patterns that don't vary by constructor, - /// e.g. struct patterns and fixed-length arrays. - Single, - /// Enum variants. - Variant(DefId), - /// Literal values. - ConstantValue(&'tcx ty::Const<'tcx>), - /// Ranges of literal values (`2...5` and `2..5`). - ConstantRange(&'tcx ty::Const<'tcx>, &'tcx ty::Const<'tcx>, RangeEnd), - /// Array patterns of length n. - Slice(u64), -} - -impl<'tcx> Constructor<'tcx> { - fn variant_index_for_adt(&self, adt: &'tcx ty::AdtDef) -> usize { - match self { - &Variant(vid) => adt.variant_index_with_id(vid), - &Single => { - assert!(!adt.is_enum()); - 0 - } - _ => bug!("bad constructor {:?} for adt {:?}", self, adt) - } - } -} - -#[derive(Clone)] -pub enum Usefulness<'tcx> { - Useful, - UsefulWithWitness(Vec>), - NotUseful -} - -impl<'tcx> Usefulness<'tcx> { - fn is_useful(&self) -> bool { - match *self { - NotUseful => false, - _ => true - } - } -} - -#[derive(Copy, Clone)] -pub enum WitnessPreference { - ConstructWitness, - LeaveOutWitness -} - -#[derive(Copy, Clone, Debug)] -struct PatternContext<'tcx> { - ty: Ty<'tcx>, - max_slice_length: u64, -} - -/// A stack of patterns in reverse order of construction -#[derive(Clone)] -pub struct Witness<'tcx>(Vec>); - -impl<'tcx> Witness<'tcx> { - pub fn single_pattern(&self) -> &Pattern<'tcx> { - assert_eq!(self.0.len(), 1); - &self.0[0] - } - - fn push_wild_constructor<'a>( - mut self, - cx: &MatchCheckCtxt<'a, 'tcx>, - ctor: &Constructor<'tcx>, - ty: Ty<'tcx>) - -> Self - { - let sub_pattern_tys = constructor_sub_pattern_tys(cx, ctor, ty); - self.0.extend(sub_pattern_tys.into_iter().map(|ty| { - Pattern { - ty, - span: DUMMY_SP, - kind: box PatternKind::Wild, - } - })); - self.apply_constructor(cx, ctor, ty) - } - - - /// Constructs a partial witness for a pattern given a list of - /// patterns expanded by the specialization step. - /// - /// When a pattern P is discovered to be useful, this function is used bottom-up - /// to reconstruct a complete witness, e.g. a pattern P' that covers a subset - /// of values, V, where each value in that set is not covered by any previously - /// used patterns and is covered by the pattern P'. Examples: - /// - /// left_ty: tuple of 3 elements - /// pats: [10, 20, _] => (10, 20, _) - /// - /// left_ty: struct X { a: (bool, &'static str), b: usize} - /// pats: [(false, "foo"), 42] => X { a: (false, "foo"), b: 42 } - fn apply_constructor<'a>( - mut self, - cx: &MatchCheckCtxt<'a,'tcx>, - ctor: &Constructor<'tcx>, - ty: Ty<'tcx>) - -> Self - { - let arity = constructor_arity(cx, ctor, ty); - let pat = { - let len = self.0.len() as u64; - let mut pats = self.0.drain((len-arity) as usize..).rev(); - - match ty.sty { - ty::TyAdt(..) | - ty::TyTuple(..) => { - let pats = pats.enumerate().map(|(i, p)| { - FieldPattern { - field: Field::new(i), - pattern: p - } - }).collect(); - - if let ty::TyAdt(adt, substs) = ty.sty { - if adt.is_enum() { - PatternKind::Variant { - adt_def: adt, - substs, - variant_index: ctor.variant_index_for_adt(adt), - subpatterns: pats - } - } else { - PatternKind::Leaf { subpatterns: pats } - } - } else { - PatternKind::Leaf { subpatterns: pats } - } - } - - ty::TyRef(..) => { - PatternKind::Deref { subpattern: pats.nth(0).unwrap() } - } - - ty::TySlice(_) | ty::TyArray(..) => { - PatternKind::Slice { - prefix: pats.collect(), - slice: None, - suffix: vec![] - } - } - - _ => { - match *ctor { - ConstantValue(value) => PatternKind::Constant { value }, - _ => PatternKind::Wild, - } - } - } - }; - - self.0.push(Pattern { - ty, - span: DUMMY_SP, - kind: Box::new(pat), - }); - - self - } -} - -/// This determines the set of all possible constructors of a pattern matching -/// values of type `left_ty`. For vectors, this would normally be an infinite set -/// but is instead bounded by the maximum fixed length of slice patterns in -/// the column of patterns being analyzed. -/// -/// This intentionally does not list ConstantValue specializations for -/// non-booleans, because we currently assume that there is always a -/// "non-standard constant" that matches. See issue #12483. -/// -/// We make sure to omit constructors that are statically impossible. eg for -/// Option we do not include Some(_) in the returned list of constructors. -fn all_constructors<'a, 'tcx: 'a>(cx: &mut MatchCheckCtxt<'a, 'tcx>, - pcx: PatternContext<'tcx>) - -> Vec> -{ - debug!("all_constructors({:?})", pcx.ty); - match pcx.ty.sty { - ty::TyBool => { - [true, false].iter().map(|&b| { - ConstantValue(cx.tcx.mk_const(ty::Const { - val: if cx.tcx.sess.opts.debugging_opts.miri { - ConstVal::Value(Value::ByVal(PrimVal::Bytes(b as u128))) - } else { - ConstVal::Bool(b) - }, - ty: cx.tcx.types.bool - })) - }).collect() - } - ty::TyArray(ref sub_ty, len) if len.val.to_u128().is_some() => { - let len = len.val.unwrap_u64(); - if len != 0 && cx.is_uninhabited(sub_ty) { - vec![] - } else { - vec![Slice(len)] - } - } - // Treat arrays of a constant but unknown length like slices. - ty::TyArray(ref sub_ty, _) | - ty::TySlice(ref sub_ty) => { - if cx.is_uninhabited(sub_ty) { - vec![Slice(0)] - } else { - (0..pcx.max_slice_length+1).map(|length| Slice(length)).collect() - } - } - ty::TyAdt(def, substs) if def.is_enum() => { - def.variants.iter() - .filter(|v| !cx.is_variant_uninhabited(v, substs)) - .map(|v| Variant(v.did)) - .collect() - } - _ => { - if cx.is_uninhabited(pcx.ty) { - vec![] - } else { - vec![Single] - } - } - } -} - -fn max_slice_length<'p, 'a: 'p, 'tcx: 'a, I>( - cx: &mut MatchCheckCtxt<'a, 'tcx>, - patterns: I) -> u64 - where I: Iterator> -{ - // The exhaustiveness-checking paper does not include any details on - // checking variable-length slice patterns. However, they are matched - // by an infinite collection of fixed-length array patterns. - // - // Checking the infinite set directly would take an infinite amount - // of time. However, it turns out that for each finite set of - // patterns `P`, all sufficiently large array lengths are equivalent: - // - // Each slice `s` with a "sufficiently-large" length `l ≥ L` that applies - // to exactly the subset `Pₜ` of `P` can be transformed to a slice - // `sₘ` for each sufficiently-large length `m` that applies to exactly - // the same subset of `P`. - // - // Because of that, each witness for reachability-checking from one - // of the sufficiently-large lengths can be transformed to an - // equally-valid witness from any other length, so we only have - // to check slice lengths from the "minimal sufficiently-large length" - // and below. - // - // Note that the fact that there is a *single* `sₘ` for each `m` - // not depending on the specific pattern in `P` is important: if - // you look at the pair of patterns - // `[true, ..]` - // `[.., false]` - // Then any slice of length ≥1 that matches one of these two - // patterns can be be trivially turned to a slice of any - // other length ≥1 that matches them and vice-versa - for - // but the slice from length 2 `[false, true]` that matches neither - // of these patterns can't be turned to a slice from length 1 that - // matches neither of these patterns, so we have to consider - // slices from length 2 there. - // - // Now, to see that that length exists and find it, observe that slice - // patterns are either "fixed-length" patterns (`[_, _, _]`) or - // "variable-length" patterns (`[_, .., _]`). - // - // For fixed-length patterns, all slices with lengths *longer* than - // the pattern's length have the same outcome (of not matching), so - // as long as `L` is greater than the pattern's length we can pick - // any `sₘ` from that length and get the same result. - // - // For variable-length patterns, the situation is more complicated, - // because as seen above the precise value of `sₘ` matters. - // - // However, for each variable-length pattern `p` with a prefix of length - // `plₚ` and suffix of length `slₚ`, only the first `plₚ` and the last - // `slₚ` elements are examined. - // - // Therefore, as long as `L` is positive (to avoid concerns about empty - // types), all elements after the maximum prefix length and before - // the maximum suffix length are not examined by any variable-length - // pattern, and therefore can be added/removed without affecting - // them - creating equivalent patterns from any sufficiently-large - // length. - // - // Of course, if fixed-length patterns exist, we must be sure - // that our length is large enough to miss them all, so - // we can pick `L = max(FIXED_LEN+1 ∪ {max(PREFIX_LEN) + max(SUFFIX_LEN)})` - // - // for example, with the above pair of patterns, all elements - // but the first and last can be added/removed, so any - // witness of length ≥2 (say, `[false, false, true]`) can be - // turned to a witness from any other length ≥2. - - let mut max_prefix_len = 0; - let mut max_suffix_len = 0; - let mut max_fixed_len = 0; - - for row in patterns { - match *row.kind { - PatternKind::Constant { value: &ty::Const { val: ConstVal::ByteStr(b), .. } } => { - max_fixed_len = cmp::max(max_fixed_len, b.data.len() as u64); - } - PatternKind::Constant { - value: &ty::Const { - val: ConstVal::Value(Value::ByVal(PrimVal::Ptr(ptr))), - ty, - } - } => { - let is_array_ptr = ty - .builtin_deref(true, ty::NoPreference) - .and_then(|t| t.ty.builtin_index()) - .map_or(false, |t| t == cx.tcx.types.u8); - if is_array_ptr { - let alloc = cx.tcx - .interpret_interner - .borrow() - .get_alloc(ptr.alloc_id.0) - .unwrap(); - max_fixed_len = cmp::max(max_fixed_len, alloc.bytes.len() as u64); - } - } - PatternKind::Slice { ref prefix, slice: None, ref suffix } => { - let fixed_len = prefix.len() as u64 + suffix.len() as u64; - max_fixed_len = cmp::max(max_fixed_len, fixed_len); - } - PatternKind::Slice { ref prefix, slice: Some(_), ref suffix } => { - max_prefix_len = cmp::max(max_prefix_len, prefix.len() as u64); - max_suffix_len = cmp::max(max_suffix_len, suffix.len() as u64); - } - _ => {} - } - } - - cmp::max(max_fixed_len + 1, max_prefix_len + max_suffix_len) -} - -/// Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html -/// The algorithm from the paper has been modified to correctly handle empty -/// types. The changes are: -/// (0) We don't exit early if the pattern matrix has zero rows. We just -/// continue to recurse over columns. -/// (1) all_constructors will only return constructors that are statically -/// possible. eg. it will only return Ok for Result -/// -/// This finds whether a (row) vector `v` of patterns is 'useful' in relation -/// to a set of such vectors `m` - this is defined as there being a set of -/// inputs that will match `v` but not any of the sets in `m`. -/// -/// All the patterns at each column of the `matrix ++ v` matrix must -/// have the same type, except that wildcard (PatternKind::Wild) patterns -/// with type TyErr are also allowed, even if the "type of the column" -/// is not TyErr. That is used to represent private fields, as using their -/// real type would assert that they are inhabited. -/// -/// This is used both for reachability checking (if a pattern isn't useful in -/// relation to preceding patterns, it is not reachable) and exhaustiveness -/// checking (if a wildcard pattern is useful in relation to a matrix, the -/// matrix isn't exhaustive). -pub fn is_useful<'p, 'a: 'p, 'tcx: 'a>(cx: &mut MatchCheckCtxt<'a, 'tcx>, - matrix: &Matrix<'p, 'tcx>, - v: &[&'p Pattern<'tcx>], - witness: WitnessPreference) - -> Usefulness<'tcx> { - let &Matrix(ref rows) = matrix; - debug!("is_useful({:#?}, {:#?})", matrix, v); - - // The base case. We are pattern-matching on () and the return value is - // based on whether our matrix has a row or not. - // NOTE: This could potentially be optimized by checking rows.is_empty() - // first and then, if v is non-empty, the return value is based on whether - // the type of the tuple we're checking is inhabited or not. - if v.is_empty() { - return if rows.is_empty() { - match witness { - ConstructWitness => UsefulWithWitness(vec![Witness(vec![])]), - LeaveOutWitness => Useful, - } - } else { - NotUseful - } - }; - - assert!(rows.iter().all(|r| r.len() == v.len())); - - let pcx = PatternContext { - // TyErr is used to represent the type of wildcard patterns matching - // against inaccessible (private) fields of structs, so that we won't - // be able to observe whether the types of the struct's fields are - // inhabited. - // - // If the field is truly inaccessible, then all the patterns - // matching against it must be wildcard patterns, so its type - // does not matter. - // - // However, if we are matching against non-wildcard patterns, we - // need to know the real type of the field so we can specialize - // against it. This primarily occurs through constants - they - // can include contents for fields that are inaccessible at the - // location of the match. In that case, the field's type is - // inhabited - by the constant - so we can just use it. - // - // FIXME: this might lead to "unstable" behavior with macro hygiene - // introducing uninhabited patterns for inaccessible fields. We - // need to figure out how to model that. - ty: rows.iter().map(|r| r[0].ty).find(|ty| !ty.references_error()) - .unwrap_or(v[0].ty), - max_slice_length: max_slice_length(cx, rows.iter().map(|r| r[0]).chain(Some(v[0]))) - }; - - debug!("is_useful_expand_first_col: pcx={:#?}, expanding {:#?}", pcx, v[0]); - - if let Some(constructors) = pat_constructors(cx, v[0], pcx) { - debug!("is_useful - expanding constructors: {:#?}", constructors); - constructors.into_iter().map(|c| - is_useful_specialized(cx, matrix, v, c.clone(), pcx.ty, witness) - ).find(|result| result.is_useful()).unwrap_or(NotUseful) - } else { - debug!("is_useful - expanding wildcard"); - - let used_ctors: Vec = rows.iter().flat_map(|row| { - pat_constructors(cx, row[0], pcx).unwrap_or(vec![]) - }).collect(); - debug!("used_ctors = {:#?}", used_ctors); - let all_ctors = all_constructors(cx, pcx); - debug!("all_ctors = {:#?}", all_ctors); - let missing_ctors: Vec = all_ctors.iter().filter(|c| { - !used_ctors.contains(*c) - }).cloned().collect(); - - // `missing_ctors` is the set of constructors from the same type as the - // first column of `matrix` that are matched only by wildcard patterns - // from the first column. - // - // Therefore, if there is some pattern that is unmatched by `matrix`, - // it will still be unmatched if the first constructor is replaced by - // any of the constructors in `missing_ctors` - // - // However, if our scrutinee is *privately* an empty enum, we - // must treat it as though it had an "unknown" constructor (in - // that case, all other patterns obviously can't be variants) - // to avoid exposing its emptyness. See the `match_privately_empty` - // test for details. - // - // FIXME: currently the only way I know of something can - // be a privately-empty enum is when the never_type - // feature flag is not present, so this is only - // needed for that case. - - let is_privately_empty = - all_ctors.is_empty() && !cx.is_uninhabited(pcx.ty); - let is_declared_nonexhaustive = - cx.is_non_exhaustive_enum(pcx.ty) && !cx.is_local(pcx.ty); - debug!("missing_ctors={:#?} is_privately_empty={:#?} is_declared_nonexhaustive={:#?}", - missing_ctors, is_privately_empty, is_declared_nonexhaustive); - - // For privately empty and non-exhaustive enums, we work as if there were an "extra" - // `_` constructor for the type, so we can never match over all constructors. - let is_non_exhaustive = is_privately_empty || is_declared_nonexhaustive; - - if missing_ctors.is_empty() && !is_non_exhaustive { - all_ctors.into_iter().map(|c| { - is_useful_specialized(cx, matrix, v, c.clone(), pcx.ty, witness) - }).find(|result| result.is_useful()).unwrap_or(NotUseful) - } else { - let matrix = rows.iter().filter_map(|r| { - if r[0].is_wildcard() { - Some(r[1..].to_vec()) - } else { - None - } - }).collect(); - match is_useful(cx, &matrix, &v[1..], witness) { - UsefulWithWitness(pats) => { - let cx = &*cx; - // In this case, there's at least one "free" - // constructor that is only matched against by - // wildcard patterns. - // - // There are 2 ways we can report a witness here. - // Commonly, we can report all the "free" - // constructors as witnesses, e.g. if we have: - // - // ``` - // enum Direction { N, S, E, W } - // let Direction::N = ...; - // ``` - // - // we can report 3 witnesses: `S`, `E`, and `W`. - // - // However, there are 2 cases where we don't want - // to do this and instead report a single `_` witness: - // - // 1) If the user is matching against a non-exhaustive - // enum, there is no point in enumerating all possible - // variants, because the user can't actually match - // against them himself, e.g. in an example like: - // ``` - // let err: io::ErrorKind = ...; - // match err { - // io::ErrorKind::NotFound => {}, - // } - // ``` - // we don't want to show every possible IO error, - // but instead have `_` as the witness (this is - // actually *required* if the user specified *all* - // IO errors, but is probably what we want in every - // case). - // - // 2) If the user didn't actually specify a constructor - // in this arm, e.g. in - // ``` - // let x: (Direction, Direction, bool) = ...; - // let (_, _, false) = x; - // ``` - // we don't want to show all 16 possible witnesses - // `(, , true)` - we are - // satisfied with `(_, _, true)`. In this case, - // `used_ctors` is empty. - let new_witnesses = if is_non_exhaustive || used_ctors.is_empty() { - // All constructors are unused. Add wild patterns - // rather than each individual constructor - pats.into_iter().map(|mut witness| { - witness.0.push(Pattern { - ty: pcx.ty, - span: DUMMY_SP, - kind: box PatternKind::Wild, - }); - witness - }).collect() - } else { - pats.into_iter().flat_map(|witness| { - missing_ctors.iter().map(move |ctor| { - witness.clone().push_wild_constructor(cx, ctor, pcx.ty) - }) - }).collect() - }; - UsefulWithWitness(new_witnesses) - } - result => result - } - } - } -} - -fn is_useful_specialized<'p, 'a:'p, 'tcx: 'a>( - cx: &mut MatchCheckCtxt<'a, 'tcx>, - &Matrix(ref m): &Matrix<'p, 'tcx>, - v: &[&'p Pattern<'tcx>], - ctor: Constructor<'tcx>, - lty: Ty<'tcx>, - witness: WitnessPreference) -> Usefulness<'tcx> -{ - debug!("is_useful_specialized({:#?}, {:#?}, {:?})", v, ctor, lty); - let sub_pat_tys = constructor_sub_pattern_tys(cx, &ctor, lty); - let wild_patterns_owned: Vec<_> = sub_pat_tys.iter().map(|ty| { - Pattern { - ty, - span: DUMMY_SP, - kind: box PatternKind::Wild, - } - }).collect(); - let wild_patterns: Vec<_> = wild_patterns_owned.iter().collect(); - let matrix = Matrix(m.iter().flat_map(|r| { - specialize(cx, &r, &ctor, &wild_patterns) - }).collect()); - match specialize(cx, v, &ctor, &wild_patterns) { - Some(v) => match is_useful(cx, &matrix, &v, witness) { - UsefulWithWitness(witnesses) => UsefulWithWitness( - witnesses.into_iter() - .map(|witness| witness.apply_constructor(cx, &ctor, lty)) - .collect() - ), - result => result - }, - None => NotUseful - } -} - -/// Determines the constructors that the given pattern can be specialized to. -/// -/// In most cases, there's only one constructor that a specific pattern -/// represents, such as a specific enum variant or a specific literal value. -/// Slice patterns, however, can match slices of different lengths. For instance, -/// `[a, b, ..tail]` can match a slice of length 2, 3, 4 and so on. -/// -/// Returns None in case of a catch-all, which can't be specialized. -fn pat_constructors<'tcx>(_cx: &mut MatchCheckCtxt, - pat: &Pattern<'tcx>, - pcx: PatternContext) - -> Option>> -{ - match *pat.kind { - PatternKind::Binding { .. } | PatternKind::Wild => - None, - PatternKind::Leaf { .. } | PatternKind::Deref { .. } => - Some(vec![Single]), - PatternKind::Variant { adt_def, variant_index, .. } => - Some(vec![Variant(adt_def.variants[variant_index].did)]), - PatternKind::Constant { value } => - Some(vec![ConstantValue(value)]), - PatternKind::Range { lo, hi, end } => - Some(vec![ConstantRange(lo, hi, end)]), - PatternKind::Array { .. } => match pcx.ty.sty { - ty::TyArray(_, length) => Some(vec![ - Slice(length.val.unwrap_u64()) - ]), - _ => span_bug!(pat.span, "bad ty {:?} for array pattern", pcx.ty) - }, - PatternKind::Slice { ref prefix, ref slice, ref suffix } => { - let pat_len = prefix.len() as u64 + suffix.len() as u64; - if slice.is_some() { - Some((pat_len..pcx.max_slice_length+1).map(Slice).collect()) - } else { - Some(vec![Slice(pat_len)]) - } - } - } -} - -/// This computes the arity of a constructor. The arity of a constructor -/// is how many subpattern patterns of that constructor should be expanded to. -/// -/// For instance, a tuple pattern (_, 42, Some([])) has the arity of 3. -/// A struct pattern's arity is the number of fields it contains, etc. -fn constructor_arity(_cx: &MatchCheckCtxt, ctor: &Constructor, ty: Ty) -> u64 { - debug!("constructor_arity({:#?}, {:?})", ctor, ty); - match ty.sty { - ty::TyTuple(ref fs, _) => fs.len() as u64, - ty::TySlice(..) | ty::TyArray(..) => match *ctor { - Slice(length) => length, - ConstantValue(_) => 0, - _ => bug!("bad slice pattern {:?} {:?}", ctor, ty) - }, - ty::TyRef(..) => 1, - ty::TyAdt(adt, _) => { - adt.variants[ctor.variant_index_for_adt(adt)].fields.len() as u64 - } - _ => 0 - } -} - -/// This computes the types of the sub patterns that a constructor should be -/// expanded to. -/// -/// For instance, a tuple pattern (43u32, 'a') has sub pattern types [u32, char]. -fn constructor_sub_pattern_tys<'a, 'tcx: 'a>(cx: &MatchCheckCtxt<'a, 'tcx>, - ctor: &Constructor, - ty: Ty<'tcx>) -> Vec> -{ - debug!("constructor_sub_pattern_tys({:#?}, {:?})", ctor, ty); - match ty.sty { - ty::TyTuple(ref fs, _) => fs.into_iter().map(|t| *t).collect(), - ty::TySlice(ty) | ty::TyArray(ty, _) => match *ctor { - Slice(length) => (0..length).map(|_| ty).collect(), - ConstantValue(_) => vec![], - Single => vec![ty], - _ => bug!("bad slice pattern {:?} {:?}", ctor, ty) - }, - ty::TyRef(_, ref ty_and_mut) => vec![ty_and_mut.ty], - ty::TyAdt(adt, substs) => { - if adt.is_box() { - // Use T as the sub pattern type of Box. - vec![substs.type_at(0)] - } else { - if let ConstantValue(_) = *ctor { - return vec![]; - } - adt.variants[ctor.variant_index_for_adt(adt)].fields.iter().map(|field| { - let is_visible = adt.is_enum() - || field.vis.is_accessible_from(cx.module, cx.tcx); - if is_visible { - field.ty(cx.tcx, substs) - } else { - // Treat all non-visible fields as TyErr. They - // can't appear in any other pattern from - // this match (because they are private), - // so their type does not matter - but - // we don't want to know they are - // uninhabited. - cx.tcx.types.err - } - }).collect() - } - } - _ => vec![], - } -} - -fn slice_pat_covered_by_constructor(tcx: TyCtxt, _span: Span, - ctor: &Constructor, - prefix: &[Pattern], - slice: &Option, - suffix: &[Pattern]) - -> Result { - let data: &[u8] = match *ctor { - ConstantValue(&ty::Const { val: ConstVal::ByteStr(b), .. }) => b.data, - ConstantValue(&ty::Const { val: ConstVal::Value( - Value::ByVal(PrimVal::Ptr(ptr)) - ), ty }) => { - let is_array_ptr = ty - .builtin_deref(true, ty::NoPreference) - .and_then(|t| t.ty.builtin_index()) - .map_or(false, |t| t == tcx.types.u8); - assert!(is_array_ptr); - tcx - .interpret_interner - .borrow() - .get_alloc(ptr.alloc_id.0) - .unwrap() - .bytes - .as_ref() - } - _ => bug!() - }; - - let pat_len = prefix.len() + suffix.len(); - if data.len() < pat_len || (slice.is_none() && data.len() > pat_len) { - return Ok(false); - } - - for (ch, pat) in - data[..prefix.len()].iter().zip(prefix).chain( - data[data.len()-suffix.len()..].iter().zip(suffix)) - { - match pat.kind { - box PatternKind::Constant { value } => match value.val { - ConstVal::Integral(ConstInt::U8(u)) => { - if u != *ch { - return Ok(false); - } - }, - ConstVal::Value(Value::ByVal(PrimVal::Bytes(b))) => { - assert_eq!(b as u8 as u128, b); - if b as u8 != *ch { - return Ok(false); - } - } - _ => span_bug!(pat.span, "bad const u8 {:?}", value) - }, - _ => {} - } - } - - Ok(true) -} - -fn constructor_covered_by_range(ctor: &Constructor, - from: &ConstVal, to: &ConstVal, - end: RangeEnd, - ty: Ty) - -> Result { - trace!("constructor_covered_by_range {:#?}, {:#?}, {:#?}, {}", ctor, from, to, ty); - let cmp_from = |c_from| compare_const_vals(c_from, from, ty) - .map(|res| res != Ordering::Less); - let cmp_to = |c_to| compare_const_vals(c_to, to, ty); - macro_rules! some_or_ok { - ($e:expr) => { - match $e { - Some(to) => to, - None => return Ok(false), // not char or int - } - }; - } - match *ctor { - ConstantValue(value) => { - let to = some_or_ok!(cmp_to(&value.val)); - let end = (to == Ordering::Less) || - (end == RangeEnd::Included && to == Ordering::Equal); - Ok(some_or_ok!(cmp_from(&value.val)) && end) - }, - ConstantRange(from, to, RangeEnd::Included) => { - let to = some_or_ok!(cmp_to(&to.val)); - let end = (to == Ordering::Less) || - (end == RangeEnd::Included && to == Ordering::Equal); - Ok(some_or_ok!(cmp_from(&from.val)) && end) - }, - ConstantRange(from, to, RangeEnd::Excluded) => { - let to = some_or_ok!(cmp_to(&to.val)); - let end = (to == Ordering::Less) || - (end == RangeEnd::Excluded && to == Ordering::Equal); - Ok(some_or_ok!(cmp_from(&from.val)) && end) - } - Variant(_) | - Single => Ok(true), - _ => bug!(), - } -} - -fn patterns_for_variant<'p, 'a: 'p, 'tcx: 'a>( - subpatterns: &'p [FieldPattern<'tcx>], - wild_patterns: &[&'p Pattern<'tcx>]) - -> Vec<&'p Pattern<'tcx>> -{ - let mut result = wild_patterns.to_owned(); - - for subpat in subpatterns { - result[subpat.field.index()] = &subpat.pattern; - } - - debug!("patterns_for_variant({:#?}, {:#?}) = {:#?}", subpatterns, wild_patterns, result); - result -} - -/// This is the main specialization step. It expands the first pattern in the given row -/// into `arity` patterns based on the constructor. For most patterns, the step is trivial, -/// for instance tuple patterns are flattened and box patterns expand into their inner pattern. -/// -/// OTOH, slice patterns with a subslice pattern (..tail) can be expanded into multiple -/// different patterns. -/// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing -/// fields filled with wild patterns. -fn specialize<'p, 'a: 'p, 'tcx: 'a>( - cx: &mut MatchCheckCtxt<'a, 'tcx>, - r: &[&'p Pattern<'tcx>], - constructor: &Constructor<'tcx>, - wild_patterns: &[&'p Pattern<'tcx>]) - -> Option>> -{ - let pat = &r[0]; - - let head: Option> = match *pat.kind { - PatternKind::Binding { .. } | PatternKind::Wild => { - Some(wild_patterns.to_owned()) - }, - - PatternKind::Variant { adt_def, variant_index, ref subpatterns, .. } => { - let ref variant = adt_def.variants[variant_index]; - if *constructor == Variant(variant.did) { - Some(patterns_for_variant(subpatterns, wild_patterns)) - } else { - None - } - } - - PatternKind::Leaf { ref subpatterns } => { - Some(patterns_for_variant(subpatterns, wild_patterns)) - } - PatternKind::Deref { ref subpattern } => { - Some(vec![subpattern]) - } - - PatternKind::Constant { value } => { - match *constructor { - Slice(..) => match value.val { - ConstVal::ByteStr(b) => { - if wild_patterns.len() == b.data.len() { - Some(cx.lower_byte_str_pattern(pat)) - } else { - None - } - } - ConstVal::Value(Value::ByVal(PrimVal::Ptr(ptr))) => { - let is_array_ptr = value.ty - .builtin_deref(true, ty::NoPreference) - .and_then(|t| t.ty.builtin_index()) - .map_or(false, |t| t == cx.tcx.types.u8); - assert!(is_array_ptr); - let data_len = cx.tcx - .interpret_interner - .borrow() - .get_alloc(ptr.alloc_id.0) - .unwrap() - .bytes - .len(); - if wild_patterns.len() == data_len { - Some(cx.lower_byte_str_pattern(pat)) - } else { - None - } - } - _ => span_bug!(pat.span, - "unexpected const-val {:?} with ctor {:?}", value, constructor) - }, - _ => { - match constructor_covered_by_range( - constructor, &value.val, &value.val, RangeEnd::Included, - value.ty, - ) { - Ok(true) => Some(vec![]), - Ok(false) => None, - Err(ErrorReported) => None, - } - } - } - } - - PatternKind::Range { lo, hi, ref end } => { - match constructor_covered_by_range( - constructor, &lo.val, &hi.val, end.clone(), lo.ty, - ) { - Ok(true) => Some(vec![]), - Ok(false) => None, - Err(ErrorReported) => None, - } - } - - PatternKind::Array { ref prefix, ref slice, ref suffix } | - PatternKind::Slice { ref prefix, ref slice, ref suffix } => { - match *constructor { - Slice(..) => { - let pat_len = prefix.len() + suffix.len(); - if let Some(slice_count) = wild_patterns.len().checked_sub(pat_len) { - if slice_count == 0 || slice.is_some() { - Some( - prefix.iter().chain( - wild_patterns.iter().map(|p| *p) - .skip(prefix.len()) - .take(slice_count) - .chain( - suffix.iter() - )).collect()) - } else { - None - } - } else { - None - } - } - ConstantValue(..) => { - match slice_pat_covered_by_constructor( - cx.tcx, pat.span, constructor, prefix, slice, suffix - ) { - Ok(true) => Some(vec![]), - Ok(false) => None, - Err(ErrorReported) => None - } - } - _ => span_bug!(pat.span, - "unexpected ctor {:?} for slice pat", constructor) - } - } - }; - debug!("specialize({:#?}, {:#?}) = {:#?}", r[0], wild_patterns, head); - - head.map(|mut head| { - head.extend_from_slice(&r[1 ..]); - head - }) -} diff --git a/src/librustc_const_eval/check_match.rs b/src/librustc_const_eval/check_match.rs deleted file mode 100644 index 6f7143c185c..00000000000 --- a/src/librustc_const_eval/check_match.rs +++ /dev/null @@ -1,636 +0,0 @@ -// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -use _match::{MatchCheckCtxt, Matrix, expand_pattern, is_useful}; -use _match::Usefulness::*; -use _match::WitnessPreference::*; - -use pattern::{Pattern, PatternContext, PatternError, PatternKind}; - -use rustc::middle::expr_use_visitor::{ConsumeMode, Delegate, ExprUseVisitor}; -use rustc::middle::expr_use_visitor::{LoanCause, MutateMode}; -use rustc::middle::expr_use_visitor as euv; -use rustc::middle::mem_categorization::{cmt}; -use rustc::middle::region; -use rustc::session::Session; -use rustc::ty::{self, Ty, TyCtxt}; -use rustc::ty::subst::Substs; -use rustc::lint; -use rustc_errors::DiagnosticBuilder; -use rustc::util::common::ErrorReported; - -use rustc::hir::def::*; -use rustc::hir::def_id::DefId; -use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap}; -use rustc::hir::{self, Pat, PatKind}; - -use std::slice; - -use syntax::ast; -use syntax::ptr::P; -use syntax_pos::{Span, DUMMY_SP}; - -struct OuterVisitor<'a, 'tcx: 'a> { tcx: TyCtxt<'a, 'tcx, 'tcx> } - -impl<'a, 'tcx> Visitor<'tcx> for OuterVisitor<'a, 'tcx> { - fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { - NestedVisitorMap::OnlyBodies(&self.tcx.hir) - } - - fn visit_body(&mut self, body: &'tcx hir::Body) { - intravisit::walk_body(self, body); - let def_id = self.tcx.hir.body_owner_def_id(body.id()); - let _ = self.tcx.check_match(def_id); - } -} - -pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) { - tcx.hir.krate().visit_all_item_likes(&mut OuterVisitor { tcx: tcx }.as_deep_visitor()); - tcx.sess.abort_if_errors(); -} - -pub(crate) fn check_match<'a, 'tcx>( - tcx: TyCtxt<'a, 'tcx, 'tcx>, - def_id: DefId, -) -> Result<(), ErrorReported> { - let body_id = if let Some(id) = tcx.hir.as_local_node_id(def_id) { - tcx.hir.body_owned_by(id) - } else { - return Ok(()); - }; - - tcx.sess.track_errors(|| { - MatchVisitor { - tcx, - tables: tcx.body_tables(body_id), - region_scope_tree: &tcx.region_scope_tree(def_id), - param_env: tcx.param_env(def_id), - identity_substs: Substs::identity_for_item(tcx, def_id), - }.visit_body(tcx.hir.body(body_id)); - }) -} - -fn create_e0004<'a>(sess: &'a Session, sp: Span, error_message: String) -> DiagnosticBuilder<'a> { - struct_span_err!(sess, sp, E0004, "{}", &error_message) -} - -struct MatchVisitor<'a, 'tcx: 'a> { - tcx: TyCtxt<'a, 'tcx, 'tcx>, - tables: &'a ty::TypeckTables<'tcx>, - param_env: ty::ParamEnv<'tcx>, - identity_substs: &'tcx Substs<'tcx>, - region_scope_tree: &'a region::ScopeTree, -} - -impl<'a, 'tcx> Visitor<'tcx> for MatchVisitor<'a, 'tcx> { - fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { - NestedVisitorMap::None - } - - fn visit_expr(&mut self, ex: &'tcx hir::Expr) { - intravisit::walk_expr(self, ex); - - match ex.node { - hir::ExprMatch(ref scrut, ref arms, source) => { - self.check_match(scrut, arms, source); - } - _ => {} - } - } - - fn visit_local(&mut self, loc: &'tcx hir::Local) { - intravisit::walk_local(self, loc); - - self.check_irrefutable(&loc.pat, match loc.source { - hir::LocalSource::Normal => "local binding", - hir::LocalSource::ForLoopDesugar => "`for` loop binding", - }); - - // Check legality of move bindings and `@` patterns. - self.check_patterns(false, slice::from_ref(&loc.pat)); - } - - fn visit_body(&mut self, body: &'tcx hir::Body) { - intravisit::walk_body(self, body); - - for arg in &body.arguments { - self.check_irrefutable(&arg.pat, "function argument"); - self.check_patterns(false, slice::from_ref(&arg.pat)); - } - } -} - - -impl<'a, 'tcx> PatternContext<'a, 'tcx> { - fn report_inlining_errors(&self, pat_span: Span) { - for error in &self.errors { - match *error { - PatternError::StaticInPattern(span) => { - self.span_e0158(span, "statics cannot be referenced in patterns") - } - PatternError::AssociatedConstInPattern(span) => { - self.span_e0158(span, "associated consts cannot be referenced in patterns") - } - PatternError::ConstEval(ref err) => { - err.report(self.tcx, pat_span, "pattern"); - } - } - } - } - - fn span_e0158(&self, span: Span, text: &str) { - span_err!(self.tcx.sess, span, E0158, "{}", text) - } -} - -impl<'a, 'tcx> MatchVisitor<'a, 'tcx> { - fn check_patterns(&self, has_guard: bool, pats: &[P]) { - check_legality_of_move_bindings(self, has_guard, pats); - for pat in pats { - check_legality_of_bindings_in_at_patterns(self, pat); - } - } - - fn check_match( - &self, - scrut: &hir::Expr, - arms: &'tcx [hir::Arm], - source: hir::MatchSource) - { - for arm in arms { - // First, check legality of move bindings. - self.check_patterns(arm.guard.is_some(), &arm.pats); - - // Second, if there is a guard on each arm, make sure it isn't - // assigning or borrowing anything mutably. - if let Some(ref guard) = arm.guard { - check_for_mutation_in_guard(self, &guard); - } - - // Third, perform some lints. - for pat in &arm.pats { - check_for_bindings_named_the_same_as_variants(self, pat); - } - } - - let module = self.tcx.hir.get_module_parent(scrut.id); - MatchCheckCtxt::create_and_enter(self.tcx, module, |ref mut cx| { - let mut have_errors = false; - - let inlined_arms : Vec<(Vec<_>, _)> = arms.iter().map(|arm| ( - arm.pats.iter().map(|pat| { - let mut patcx = PatternContext::new(self.tcx, - self.param_env.and(self.identity_substs), - self.tables); - let pattern = expand_pattern(cx, patcx.lower_pattern(&pat)); - if !patcx.errors.is_empty() { - patcx.report_inlining_errors(pat.span); - have_errors = true; - } - (pattern, &**pat) - }).collect(), - arm.guard.as_ref().map(|e| &**e) - )).collect(); - - // Bail out early if inlining failed. - if have_errors { - return; - } - - // Fourth, check for unreachable arms. - check_arms(cx, &inlined_arms, source); - - // Then, if the match has no arms, check whether the scrutinee - // is uninhabited. - let pat_ty = self.tables.node_id_to_type(scrut.hir_id); - let module = self.tcx.hir.get_module_parent(scrut.id); - if inlined_arms.is_empty() { - let scrutinee_is_uninhabited = if self.tcx.features().never_type { - self.tcx.is_ty_uninhabited_from(module, pat_ty) - } else { - self.conservative_is_uninhabited(pat_ty) - }; - if !scrutinee_is_uninhabited { - // We know the type is inhabited, so this must be wrong - let mut err = create_e0004(self.tcx.sess, scrut.span, - format!("non-exhaustive patterns: type {} \ - is non-empty", - pat_ty)); - span_help!(&mut err, scrut.span, - "Please ensure that all possible cases are being handled; \ - possibly adding wildcards or more match arms."); - err.emit(); - } - // If the type *is* uninhabited, it's vacuously exhaustive - return; - } - - let matrix: Matrix = inlined_arms - .iter() - .filter(|&&(_, guard)| guard.is_none()) - .flat_map(|arm| &arm.0) - .map(|pat| vec![pat.0]) - .collect(); - let scrut_ty = self.tables.node_id_to_type(scrut.hir_id); - check_exhaustive(cx, scrut_ty, scrut.span, &matrix); - }) - } - - fn conservative_is_uninhabited(&self, scrutinee_ty: Ty<'tcx>) -> bool { - // "rustc-1.0-style" uncontentious uninhabitableness check - match scrutinee_ty.sty { - ty::TyNever => true, - ty::TyAdt(def, _) => def.variants.is_empty(), - _ => false - } - } - - fn check_irrefutable(&self, pat: &'tcx Pat, origin: &str) { - let module = self.tcx.hir.get_module_parent(pat.id); - MatchCheckCtxt::create_and_enter(self.tcx, module, |ref mut cx| { - let mut patcx = PatternContext::new(self.tcx, - self.param_env.and(self.identity_substs), - self.tables); - let pattern = patcx.lower_pattern(pat); - let pattern_ty = pattern.ty; - let pats : Matrix = vec![vec![ - expand_pattern(cx, pattern) - ]].into_iter().collect(); - - let wild_pattern = Pattern { - ty: pattern_ty, - span: DUMMY_SP, - kind: box PatternKind::Wild, - }; - let witness = match is_useful(cx, &pats, &[&wild_pattern], ConstructWitness) { - UsefulWithWitness(witness) => witness, - NotUseful => return, - Useful => bug!() - }; - - let pattern_string = witness[0].single_pattern().to_string(); - let mut diag = struct_span_err!( - self.tcx.sess, pat.span, E0005, - "refutable pattern in {}: `{}` not covered", - origin, pattern_string - ); - let label_msg = match pat.node { - PatKind::Path(hir::QPath::Resolved(None, ref path)) - if path.segments.len() == 1 && path.segments[0].parameters.is_none() => { - format!("interpreted as a {} pattern, not new variable", path.def.kind_name()) - } - _ => format!("pattern `{}` not covered", pattern_string), - }; - diag.span_label(pat.span, label_msg); - diag.emit(); - }); - } -} - -fn check_for_bindings_named_the_same_as_variants(cx: &MatchVisitor, pat: &Pat) { - pat.walk(|p| { - if let PatKind::Binding(_, _, name, None) = p.node { - let bm = *cx.tables - .pat_binding_modes() - .get(p.hir_id) - .expect("missing binding mode"); - - if bm != ty::BindByValue(hir::MutImmutable) { - // Nothing to check. - return true; - } - let pat_ty = cx.tables.pat_ty(p); - if let ty::TyAdt(edef, _) = pat_ty.sty { - if edef.is_enum() && edef.variants.iter().any(|variant| { - variant.name == name.node && variant.ctor_kind == CtorKind::Const - }) { - let ty_path = cx.tcx.item_path_str(edef.did); - let mut err = struct_span_warn!(cx.tcx.sess, p.span, E0170, - "pattern binding `{}` is named the same as one \ - of the variants of the type `{}`", - name.node, ty_path); - help!(err, - "if you meant to match on a variant, \ - consider making the path in the pattern qualified: `{}::{}`", - ty_path, name.node); - err.emit(); - } - } - } - true - }); -} - -/// Checks for common cases of "catchall" patterns that may not be intended as such. -fn pat_is_catchall(pat: &Pat) -> bool { - match pat.node { - PatKind::Binding(.., None) => true, - PatKind::Binding(.., Some(ref s)) => pat_is_catchall(s), - PatKind::Ref(ref s, _) => pat_is_catchall(s), - PatKind::Tuple(ref v, _) => v.iter().all(|p| { - pat_is_catchall(&p) - }), - _ => false - } -} - -// Check for unreachable patterns -fn check_arms<'a, 'tcx>(cx: &mut MatchCheckCtxt<'a, 'tcx>, - arms: &[(Vec<(&'a Pattern<'tcx>, &hir::Pat)>, Option<&hir::Expr>)], - source: hir::MatchSource) -{ - let mut seen = Matrix::empty(); - let mut catchall = None; - let mut printed_if_let_err = false; - for (arm_index, &(ref pats, guard)) in arms.iter().enumerate() { - for &(pat, hir_pat) in pats { - let v = vec![pat]; - - match is_useful(cx, &seen, &v, LeaveOutWitness) { - NotUseful => { - match source { - hir::MatchSource::IfLetDesugar { .. } => { - if printed_if_let_err { - // we already printed an irrefutable if-let pattern error. - // We don't want two, that's just confusing. - } else { - // find the first arm pattern so we can use its span - let &(ref first_arm_pats, _) = &arms[0]; - let first_pat = &first_arm_pats[0]; - let span = first_pat.0.span; - struct_span_err!(cx.tcx.sess, span, E0162, - "irrefutable if-let pattern") - .span_label(span, "irrefutable pattern") - .emit(); - printed_if_let_err = true; - } - }, - - hir::MatchSource::WhileLetDesugar => { - // find the first arm pattern so we can use its span - let &(ref first_arm_pats, _) = &arms[0]; - let first_pat = &first_arm_pats[0]; - let span = first_pat.0.span; - - // check which arm we're on. - match arm_index { - // The arm with the user-specified pattern. - 0 => { - cx.tcx.lint_node( - lint::builtin::UNREACHABLE_PATTERNS, - hir_pat.id, pat.span, - "unreachable pattern"); - }, - // The arm with the wildcard pattern. - 1 => { - struct_span_err!(cx.tcx.sess, span, E0165, - "irrefutable while-let pattern") - .span_label(span, "irrefutable pattern") - .emit(); - }, - _ => bug!(), - } - }, - - hir::MatchSource::ForLoopDesugar | - hir::MatchSource::Normal => { - let mut err = cx.tcx.struct_span_lint_node( - lint::builtin::UNREACHABLE_PATTERNS, - hir_pat.id, - pat.span, - "unreachable pattern", - ); - // if we had a catchall pattern, hint at that - if let Some(catchall) = catchall { - err.span_label(pat.span, "unreachable pattern"); - err.span_label(catchall, "matches any value"); - } - err.emit(); - }, - - // Unreachable patterns in try expressions occur when one of the arms - // are an uninhabited type. Which is OK. - hir::MatchSource::TryDesugar => {} - } - } - Useful => (), - UsefulWithWitness(_) => bug!() - } - if guard.is_none() { - seen.push(v); - if catchall.is_none() && pat_is_catchall(hir_pat) { - catchall = Some(pat.span); - } - } - } - } -} - -fn check_exhaustive<'a, 'tcx>(cx: &mut MatchCheckCtxt<'a, 'tcx>, - scrut_ty: Ty<'tcx>, - sp: Span, - matrix: &Matrix<'a, 'tcx>) { - let wild_pattern = Pattern { - ty: scrut_ty, - span: DUMMY_SP, - kind: box PatternKind::Wild, - }; - match is_useful(cx, matrix, &[&wild_pattern], ConstructWitness) { - UsefulWithWitness(pats) => { - let witnesses = if pats.is_empty() { - vec![&wild_pattern] - } else { - pats.iter().map(|w| w.single_pattern()).collect() - }; - - const LIMIT: usize = 3; - let joined_patterns = match witnesses.len() { - 0 => bug!(), - 1 => format!("`{}`", witnesses[0]), - 2...LIMIT => { - let (tail, head) = witnesses.split_last().unwrap(); - let head: Vec<_> = head.iter().map(|w| w.to_string()).collect(); - format!("`{}` and `{}`", head.join("`, `"), tail) - }, - _ => { - let (head, tail) = witnesses.split_at(LIMIT); - let head: Vec<_> = head.iter().map(|w| w.to_string()).collect(); - format!("`{}` and {} more", head.join("`, `"), tail.len()) - } - }; - - let label_text = match witnesses.len() { - 1 => format!("pattern {} not covered", joined_patterns), - _ => format!("patterns {} not covered", joined_patterns) - }; - create_e0004(cx.tcx.sess, sp, - format!("non-exhaustive patterns: {} not covered", - joined_patterns)) - .span_label(sp, label_text) - .emit(); - } - NotUseful => { - // This is good, wildcard pattern isn't reachable - }, - _ => bug!() - } -} - -// Legality of move bindings checking -fn check_legality_of_move_bindings(cx: &MatchVisitor, - has_guard: bool, - pats: &[P]) { - let mut by_ref_span = None; - for pat in pats { - pat.each_binding(|_, id, span, _path| { - let hir_id = cx.tcx.hir.node_to_hir_id(id); - let bm = *cx.tables - .pat_binding_modes() - .get(hir_id) - .expect("missing binding mode"); - if let ty::BindByReference(..) = bm { - by_ref_span = Some(span); - } - }) - } - - let check_move = |p: &Pat, sub: Option<&Pat>| { - // check legality of moving out of the enum - - // x @ Foo(..) is legal, but x @ Foo(y) isn't. - if sub.map_or(false, |p| p.contains_bindings()) { - struct_span_err!(cx.tcx.sess, p.span, E0007, - "cannot bind by-move with sub-bindings") - .span_label(p.span, "binds an already bound by-move value by moving it") - .emit(); - } else if has_guard { - struct_span_err!(cx.tcx.sess, p.span, E0008, - "cannot bind by-move into a pattern guard") - .span_label(p.span, "moves value into pattern guard") - .emit(); - } else if by_ref_span.is_some() { - struct_span_err!(cx.tcx.sess, p.span, E0009, - "cannot bind by-move and by-ref in the same pattern") - .span_label(p.span, "by-move pattern here") - .span_label(by_ref_span.unwrap(), "both by-ref and by-move used") - .emit(); - } - }; - - for pat in pats { - pat.walk(|p| { - if let PatKind::Binding(_, _, _, ref sub) = p.node { - let bm = *cx.tables - .pat_binding_modes() - .get(p.hir_id) - .expect("missing binding mode"); - match bm { - ty::BindByValue(..) => { - let pat_ty = cx.tables.node_id_to_type(p.hir_id); - if pat_ty.moves_by_default(cx.tcx, cx.param_env, pat.span) { - check_move(p, sub.as_ref().map(|p| &**p)); - } - } - _ => {} - } - } - true - }); - } -} - -/// Ensures that a pattern guard doesn't borrow by mutable reference or -/// assign. -/// -/// FIXME: this should be done by borrowck. -fn check_for_mutation_in_guard(cx: &MatchVisitor, guard: &hir::Expr) { - let mut checker = MutationChecker { - cx, - }; - ExprUseVisitor::new(&mut checker, cx.tcx, cx.param_env, cx.region_scope_tree, cx.tables, None) - .walk_expr(guard); -} - -struct MutationChecker<'a, 'tcx: 'a> { - cx: &'a MatchVisitor<'a, 'tcx>, -} - -impl<'a, 'tcx> Delegate<'tcx> for MutationChecker<'a, 'tcx> { - fn matched_pat(&mut self, _: &Pat, _: cmt, _: euv::MatchMode) {} - fn consume(&mut self, _: ast::NodeId, _: Span, _: cmt, _: ConsumeMode) {} - fn consume_pat(&mut self, _: &Pat, _: cmt, _: ConsumeMode) {} - fn borrow(&mut self, - _: ast::NodeId, - span: Span, - _: cmt, - _: ty::Region<'tcx>, - kind:ty:: BorrowKind, - _: LoanCause) { - match kind { - ty::MutBorrow => { - struct_span_err!(self.cx.tcx.sess, span, E0301, - "cannot mutably borrow in a pattern guard") - .span_label(span, "borrowed mutably in pattern guard") - .emit(); - } - ty::ImmBorrow | ty::UniqueImmBorrow => {} - } - } - fn decl_without_init(&mut self, _: ast::NodeId, _: Span) {} - fn mutate(&mut self, _: ast::NodeId, span: Span, _: cmt, mode: MutateMode) { - match mode { - MutateMode::JustWrite | MutateMode::WriteAndRead => { - struct_span_err!(self.cx.tcx.sess, span, E0302, "cannot assign in a pattern guard") - .span_label(span, "assignment in pattern guard") - .emit(); - } - MutateMode::Init => {} - } - } -} - -/// Forbids bindings in `@` patterns. This is necessary for memory safety, -/// because of the way rvalues are handled in the borrow check. (See issue -/// #14587.) -fn check_legality_of_bindings_in_at_patterns(cx: &MatchVisitor, pat: &Pat) { - AtBindingPatternVisitor { cx: cx, bindings_allowed: true }.visit_pat(pat); -} - -struct AtBindingPatternVisitor<'a, 'b:'a, 'tcx:'b> { - cx: &'a MatchVisitor<'b, 'tcx>, - bindings_allowed: bool -} - -impl<'a, 'b, 'tcx, 'v> Visitor<'v> for AtBindingPatternVisitor<'a, 'b, 'tcx> { - fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> { - NestedVisitorMap::None - } - - fn visit_pat(&mut self, pat: &Pat) { - match pat.node { - PatKind::Binding(.., ref subpat) => { - if !self.bindings_allowed { - struct_span_err!(self.cx.tcx.sess, pat.span, E0303, - "pattern bindings are not allowed after an `@`") - .span_label(pat.span, "not allowed after `@`") - .emit(); - } - - if subpat.is_some() { - let bindings_were_allowed = self.bindings_allowed; - self.bindings_allowed = false; - intravisit::walk_pat(self, pat); - self.bindings_allowed = bindings_were_allowed; - } - } - _ => intravisit::walk_pat(self, pat), - } - } -} diff --git a/src/librustc_const_eval/diagnostics.rs b/src/librustc_const_eval/diagnostics.rs deleted file mode 100644 index d01b3c45f7f..00000000000 --- a/src/librustc_const_eval/diagnostics.rs +++ /dev/null @@ -1,571 +0,0 @@ -// Copyright 2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -#![allow(non_snake_case)] - -// Error messages for EXXXX errors. -// Each message should start and end with a new line, and be wrapped to 80 characters. -// In vim you can `:set tw=80` and use `gq` to wrap paragraphs. Use `:set tw=0` to disable. -register_long_diagnostics! { - -E0001: r##" -#### Note: this error code is no longer emitted by the compiler. - -This error suggests that the expression arm corresponding to the noted pattern -will never be reached as for all possible values of the expression being -matched, one of the preceding patterns will match. - -This means that perhaps some of the preceding patterns are too general, this -one is too specific or the ordering is incorrect. - -For example, the following `match` block has too many arms: - -``` -match Some(0) { - Some(bar) => {/* ... */} - x => {/* ... */} // This handles the `None` case - _ => {/* ... */} // All possible cases have already been handled -} -``` - -`match` blocks have their patterns matched in order, so, for example, putting -a wildcard arm above a more specific arm will make the latter arm irrelevant. - -Ensure the ordering of the match arm is correct and remove any superfluous -arms. -"##, - -E0002: r##" -#### Note: this error code is no longer emitted by the compiler. - -This error indicates that an empty match expression is invalid because the type -it is matching on is non-empty (there exist values of this type). In safe code -it is impossible to create an instance of an empty type, so empty match -expressions are almost never desired. This error is typically fixed by adding -one or more cases to the match expression. - -An example of an empty type is `enum Empty { }`. So, the following will work: - -``` -enum Empty {} - -fn foo(x: Empty) { - match x { - // empty - } -} -``` - -However, this won't: - -```compile_fail -fn foo(x: Option) { - match x { - // empty - } -} -``` -"##, - -E0003: r##" -#### Note: this error code is no longer emitted by the compiler. - -Not-a-Number (NaN) values cannot be compared for equality and hence can never -match the input to a match expression. So, the following will not compile: - -```compile_fail -const NAN: f32 = 0.0 / 0.0; - -let number = 0.1f32; - -match number { - NAN => { /* ... */ }, - _ => {} -} -``` - -To match against NaN values, you should instead use the `is_nan()` method in a -guard, like so: - -``` -let number = 0.1f32; - -match number { - x if x.is_nan() => { /* ... */ } - _ => {} -} -``` -"##, - -E0004: r##" -This error indicates that the compiler cannot guarantee a matching pattern for -one or more possible inputs to a match expression. Guaranteed matches are -required in order to assign values to match expressions, or alternatively, -determine the flow of execution. Erroneous code example: - -```compile_fail,E0004 -enum Terminator { - HastaLaVistaBaby, - TalkToMyHand, -} - -let x = Terminator::HastaLaVistaBaby; - -match x { // error: non-exhaustive patterns: `HastaLaVistaBaby` not covered - Terminator::TalkToMyHand => {} -} -``` - -If you encounter this error you must alter your patterns so that every possible -value of the input type is matched. For types with a small number of variants -(like enums) you should probably cover all cases explicitly. Alternatively, the -underscore `_` wildcard pattern can be added after all other patterns to match -"anything else". Example: - -``` -enum Terminator { - HastaLaVistaBaby, - TalkToMyHand, -} - -let x = Terminator::HastaLaVistaBaby; - -match x { - Terminator::TalkToMyHand => {} - Terminator::HastaLaVistaBaby => {} -} - -// or: - -match x { - Terminator::TalkToMyHand => {} - _ => {} -} -``` -"##, - -E0005: r##" -Patterns used to bind names must be irrefutable, that is, they must guarantee -that a name will be extracted in all cases. Erroneous code example: - -```compile_fail,E0005 -let x = Some(1); -let Some(y) = x; -// error: refutable pattern in local binding: `None` not covered -``` - -If you encounter this error you probably need to use a `match` or `if let` to -deal with the possibility of failure. Example: - -``` -let x = Some(1); - -match x { - Some(y) => { - // do something - }, - None => {} -} - -// or: - -if let Some(y) = x { - // do something -} -``` -"##, - -E0007: r##" -This error indicates that the bindings in a match arm would require a value to -be moved into more than one location, thus violating unique ownership. Code -like the following is invalid as it requires the entire `Option` to be -moved into a variable called `op_string` while simultaneously requiring the -inner `String` to be moved into a variable called `s`. - -```compile_fail,E0007 -let x = Some("s".to_string()); - -match x { - op_string @ Some(s) => {}, // error: cannot bind by-move with sub-bindings - None => {}, -} -``` - -See also the error E0303. -"##, - -E0008: r##" -Names bound in match arms retain their type in pattern guards. As such, if a -name is bound by move in a pattern, it should also be moved to wherever it is -referenced in the pattern guard code. Doing so however would prevent the name -from being available in the body of the match arm. Consider the following: - -```compile_fail,E0008 -match Some("hi".to_string()) { - Some(s) if s.len() == 0 => {}, // use s. - _ => {}, -} -``` - -The variable `s` has type `String`, and its use in the guard is as a variable of -type `String`. The guard code effectively executes in a separate scope to the -body of the arm, so the value would be moved into this anonymous scope and -therefore becomes unavailable in the body of the arm. - -The problem above can be solved by using the `ref` keyword. - -``` -match Some("hi".to_string()) { - Some(ref s) if s.len() == 0 => {}, - _ => {}, -} -``` - -Though this example seems innocuous and easy to solve, the problem becomes clear -when it encounters functions which consume the value: - -```compile_fail,E0008 -struct A{} - -impl A { - fn consume(self) -> usize { - 0 - } -} - -fn main() { - let a = Some(A{}); - match a { - Some(y) if y.consume() > 0 => {} - _ => {} - } -} -``` - -In this situation, even the `ref` keyword cannot solve it, since borrowed -content cannot be moved. This problem cannot be solved generally. If the value -can be cloned, here is a not-so-specific solution: - -``` -#[derive(Clone)] -struct A{} - -impl A { - fn consume(self) -> usize { - 0 - } -} - -fn main() { - let a = Some(A{}); - match a{ - Some(ref y) if y.clone().consume() > 0 => {} - _ => {} - } -} -``` - -If the value will be consumed in the pattern guard, using its clone will not -move its ownership, so the code works. -"##, - -E0009: r##" -In a pattern, all values that don't implement the `Copy` trait have to be bound -the same way. The goal here is to avoid binding simultaneously by-move and -by-ref. - -This limitation may be removed in a future version of Rust. - -Erroneous code example: - -```compile_fail,E0009 -struct X { x: (), } - -let x = Some((X { x: () }, X { x: () })); -match x { - Some((y, ref z)) => {}, // error: cannot bind by-move and by-ref in the - // same pattern - None => panic!() -} -``` - -You have two solutions: - -Solution #1: Bind the pattern's values the same way. - -``` -struct X { x: (), } - -let x = Some((X { x: () }, X { x: () })); -match x { - Some((ref y, ref z)) => {}, - // or Some((y, z)) => {} - None => panic!() -} -``` - -Solution #2: Implement the `Copy` trait for the `X` structure. - -However, please keep in mind that the first solution should be preferred. - -``` -#[derive(Clone, Copy)] -struct X { x: (), } - -let x = Some((X { x: () }, X { x: () })); -match x { - Some((y, ref z)) => {}, - None => panic!() -} -``` -"##, - -E0158: r##" -`const` and `static` mean different things. A `const` is a compile-time -constant, an alias for a literal value. This property means you can match it -directly within a pattern. - -The `static` keyword, on the other hand, guarantees a fixed location in memory. -This does not always mean that the value is constant. For example, a global -mutex can be declared `static` as well. - -If you want to match against a `static`, consider using a guard instead: - -``` -static FORTY_TWO: i32 = 42; - -match Some(42) { - Some(x) if x == FORTY_TWO => {} - _ => {} -} -``` -"##, - -E0162: r##" -An if-let pattern attempts to match the pattern, and enters the body if the -match was successful. If the match is irrefutable (when it cannot fail to -match), use a regular `let`-binding instead. For instance: - -```compile_fail,E0162 -struct Irrefutable(i32); -let irr = Irrefutable(0); - -// This fails to compile because the match is irrefutable. -if let Irrefutable(x) = irr { - // This body will always be executed. - // ... -} -``` - -Try this instead: - -``` -struct Irrefutable(i32); -let irr = Irrefutable(0); - -let Irrefutable(x) = irr; -println!("{}", x); -``` -"##, - -E0165: r##" -A while-let pattern attempts to match the pattern, and enters the body if the -match was successful. If the match is irrefutable (when it cannot fail to -match), use a regular `let`-binding inside a `loop` instead. For instance: - -```compile_fail,E0165 -struct Irrefutable(i32); -let irr = Irrefutable(0); - -// This fails to compile because the match is irrefutable. -while let Irrefutable(x) = irr { - // ... -} -``` - -Try this instead: - -```no_run -struct Irrefutable(i32); -let irr = Irrefutable(0); - -loop { - let Irrefutable(x) = irr; - // ... -} -``` -"##, - -E0170: r##" -Enum variants are qualified by default. For example, given this type: - -``` -enum Method { - GET, - POST, -} -``` - -You would match it using: - -``` -enum Method { - GET, - POST, -} - -let m = Method::GET; - -match m { - Method::GET => {}, - Method::POST => {}, -} -``` - -If you don't qualify the names, the code will bind new variables named "GET" and -"POST" instead. This behavior is likely not what you want, so `rustc` warns when -that happens. - -Qualified names are good practice, and most code works well with them. But if -you prefer them unqualified, you can import the variants into scope: - -``` -use Method::*; -enum Method { GET, POST } -# fn main() {} -``` - -If you want others to be able to import variants from your module directly, use -`pub use`: - -``` -pub use Method::*; -pub enum Method { GET, POST } -# fn main() {} -``` -"##, - - -E0297: r##" -#### Note: this error code is no longer emitted by the compiler. - -Patterns used to bind names must be irrefutable. That is, they must guarantee -that a name will be extracted in all cases. Instead of pattern matching the -loop variable, consider using a `match` or `if let` inside the loop body. For -instance: - -```compile_fail,E0005 -let xs : Vec> = vec![Some(1), None]; - -// This fails because `None` is not covered. -for Some(x) in xs { - // ... -} -``` - -Match inside the loop instead: - -``` -let xs : Vec> = vec![Some(1), None]; - -for item in xs { - match item { - Some(x) => {}, - None => {}, - } -} -``` - -Or use `if let`: - -``` -let xs : Vec> = vec![Some(1), None]; - -for item in xs { - if let Some(x) = item { - // ... - } -} -``` -"##, - -E0301: r##" -Mutable borrows are not allowed in pattern guards, because matching cannot have -side effects. Side effects could alter the matched object or the environment -on which the match depends in such a way, that the match would not be -exhaustive. For instance, the following would not match any arm if mutable -borrows were allowed: - -```compile_fail,E0301 -match Some(()) { - None => { }, - option if option.take().is_none() => { - /* impossible, option is `Some` */ - }, - Some(_) => { } // When the previous match failed, the option became `None`. -} -``` -"##, - -E0302: r##" -Assignments are not allowed in pattern guards, because matching cannot have -side effects. Side effects could alter the matched object or the environment -on which the match depends in such a way, that the match would not be -exhaustive. For instance, the following would not match any arm if assignments -were allowed: - -```compile_fail,E0302 -match Some(()) { - None => { }, - option if { option = None; false } => { }, - Some(_) => { } // When the previous match failed, the option became `None`. -} -``` -"##, - -E0303: r##" -In certain cases it is possible for sub-bindings to violate memory safety. -Updates to the borrow checker in a future version of Rust may remove this -restriction, but for now patterns must be rewritten without sub-bindings. - -Before: - -```compile_fail,E0303 -match Some("hi".to_string()) { - ref op_string_ref @ Some(s) => {}, - None => {}, -} -``` - -After: - -``` -match Some("hi".to_string()) { - Some(ref s) => { - let op_string_ref = &Some(s); - // ... - }, - None => {}, -} -``` - -The `op_string_ref` binding has type `&Option<&String>` in both cases. - -See also https://github.com/rust-lang/rust/issues/14587 -"##, - -} - - -register_diagnostics! { -// E0298, // cannot compare constants -// E0299, // mismatched types between arms -// E0471, // constant evaluation error (in pattern) -} diff --git a/src/librustc_const_eval/eval.rs b/src/librustc_const_eval/eval.rs deleted file mode 100644 index 58fe40d12be..00000000000 --- a/src/librustc_const_eval/eval.rs +++ /dev/null @@ -1,697 +0,0 @@ -// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -use rustc::middle::const_val::ConstVal::*; -use rustc::middle::const_val::ConstAggregate::*; -use rustc::middle::const_val::ErrKind::*; -use rustc::middle::const_val::{ByteArray, ConstVal, ConstEvalErr, EvalResult, ErrKind}; - -use rustc::hir::map::blocks::FnLikeNode; -use rustc::hir::def::{Def, CtorKind}; -use rustc::hir::def_id::DefId; -use rustc::ty::{self, Ty, TyCtxt}; -use rustc::ty::util::IntTypeExt; -use rustc::ty::subst::{Substs, Subst}; -use rustc::util::common::ErrorReported; -use rustc::util::nodemap::NodeMap; - -use syntax::abi::Abi; -use syntax::ast; -use syntax::attr; -use rustc::hir::{self, Expr}; - -use std::cmp::Ordering; - -use rustc_const_math::*; -macro_rules! signal { - ($e:expr, $exn:expr) => { - return Err(ConstEvalErr { span: $e.span, kind: $exn }) - } -} - -macro_rules! math { - ($e:expr, $op:expr) => { - match $op { - Ok(val) => val, - Err(e) => signal!($e, ErrKind::from(e)), - } - } -} - -/// * `DefId` is the id of the constant. -/// * `Substs` is the monomorphized substitutions for the expression. -pub fn lookup_const_by_id<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - key: ty::ParamEnvAnd<'tcx, (DefId, &'tcx Substs<'tcx>)>) - -> Option<(DefId, &'tcx Substs<'tcx>)> { - ty::Instance::resolve( - tcx, - key.param_env, - key.value.0, - key.value.1, - ).map(|instance| (instance.def_id(), instance.substs)) -} - -pub struct ConstContext<'a, 'tcx: 'a> { - tcx: TyCtxt<'a, 'tcx, 'tcx>, - tables: &'a ty::TypeckTables<'tcx>, - param_env: ty::ParamEnv<'tcx>, - substs: &'tcx Substs<'tcx>, - fn_args: Option>> -} - -impl<'a, 'tcx> ConstContext<'a, 'tcx> { - pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, - param_env_and_substs: ty::ParamEnvAnd<'tcx, &'tcx Substs<'tcx>>, - tables: &'a ty::TypeckTables<'tcx>) - -> Self { - ConstContext { - tcx, - param_env: param_env_and_substs.param_env, - tables, - substs: param_env_and_substs.value, - fn_args: None - } - } - - /// Evaluate a constant expression in a context where the expression isn't - /// guaranteed to be evaluable. - pub fn eval(&self, e: &'tcx Expr) -> EvalResult<'tcx> { - if self.tables.tainted_by_errors { - signal!(e, TypeckError); - } - eval_const_expr_partial(self, e) - } -} - -type CastResult<'tcx> = Result, ErrKind<'tcx>>; - -fn eval_const_expr_partial<'a, 'tcx>(cx: &ConstContext<'a, 'tcx>, - e: &'tcx Expr) -> EvalResult<'tcx> { - trace!("eval_const_expr_partial: {:?}", e); - let tcx = cx.tcx; - let ty = cx.tables.expr_ty(e).subst(tcx, cx.substs); - let mk_const = |val| tcx.mk_const(ty::Const { val, ty }); - - let result = match e.node { - hir::ExprUnary(hir::UnNeg, ref inner) => { - // unary neg literals already got their sign during creation - if let hir::ExprLit(ref lit) = inner.node { - return match lit_to_const(&lit.node, tcx, ty, true) { - Ok(val) => Ok(mk_const(val)), - Err(err) => signal!(e, err), - }; - } - mk_const(match cx.eval(inner)?.val { - Float(f) => Float(-f), - Integral(i) => Integral(math!(e, -i)), - _ => signal!(e, TypeckError) - }) - } - hir::ExprUnary(hir::UnNot, ref inner) => { - mk_const(match cx.eval(inner)?.val { - Integral(i) => Integral(math!(e, !i)), - Bool(b) => Bool(!b), - _ => signal!(e, TypeckError) - }) - } - hir::ExprUnary(hir::UnDeref, _) => signal!(e, UnimplementedConstVal("deref operation")), - hir::ExprBinary(op, ref a, ref b) => { - // technically, if we don't have type hints, but integral eval - // gives us a type through a type-suffix, cast or const def type - // we need to re-eval the other value of the BinOp if it was - // not inferred - mk_const(match (cx.eval(a)?.val, cx.eval(b)?.val) { - (Float(a), Float(b)) => { - use std::cmp::Ordering::*; - match op.node { - hir::BiAdd => Float(math!(e, a + b)), - hir::BiSub => Float(math!(e, a - b)), - hir::BiMul => Float(math!(e, a * b)), - hir::BiDiv => Float(math!(e, a / b)), - hir::BiRem => Float(math!(e, a % b)), - hir::BiEq => Bool(math!(e, a.try_cmp(b)) == Equal), - hir::BiLt => Bool(math!(e, a.try_cmp(b)) == Less), - hir::BiLe => Bool(math!(e, a.try_cmp(b)) != Greater), - hir::BiNe => Bool(math!(e, a.try_cmp(b)) != Equal), - hir::BiGe => Bool(math!(e, a.try_cmp(b)) != Less), - hir::BiGt => Bool(math!(e, a.try_cmp(b)) == Greater), - _ => span_bug!(e.span, "typeck error"), - } - } - (Integral(a), Integral(b)) => { - use std::cmp::Ordering::*; - match op.node { - hir::BiAdd => Integral(math!(e, a + b)), - hir::BiSub => Integral(math!(e, a - b)), - hir::BiMul => Integral(math!(e, a * b)), - hir::BiDiv => Integral(math!(e, a / b)), - hir::BiRem => Integral(math!(e, a % b)), - hir::BiBitAnd => Integral(math!(e, a & b)), - hir::BiBitOr => Integral(math!(e, a | b)), - hir::BiBitXor => Integral(math!(e, a ^ b)), - hir::BiShl => Integral(math!(e, a << b)), - hir::BiShr => Integral(math!(e, a >> b)), - hir::BiEq => Bool(math!(e, a.try_cmp(b)) == Equal), - hir::BiLt => Bool(math!(e, a.try_cmp(b)) == Less), - hir::BiLe => Bool(math!(e, a.try_cmp(b)) != Greater), - hir::BiNe => Bool(math!(e, a.try_cmp(b)) != Equal), - hir::BiGe => Bool(math!(e, a.try_cmp(b)) != Less), - hir::BiGt => Bool(math!(e, a.try_cmp(b)) == Greater), - _ => span_bug!(e.span, "typeck error"), - } - } - (Bool(a), Bool(b)) => { - Bool(match op.node { - hir::BiAnd => a && b, - hir::BiOr => a || b, - hir::BiBitXor => a ^ b, - hir::BiBitAnd => a & b, - hir::BiBitOr => a | b, - hir::BiEq => a == b, - hir::BiNe => a != b, - hir::BiLt => a < b, - hir::BiLe => a <= b, - hir::BiGe => a >= b, - hir::BiGt => a > b, - _ => span_bug!(e.span, "typeck error"), - }) - } - (Char(a), Char(b)) => { - Bool(match op.node { - hir::BiEq => a == b, - hir::BiNe => a != b, - hir::BiLt => a < b, - hir::BiLe => a <= b, - hir::BiGe => a >= b, - hir::BiGt => a > b, - _ => span_bug!(e.span, "typeck error"), - }) - } - - _ => signal!(e, MiscBinaryOp), - }) - } - hir::ExprCast(ref base, _) => { - let base_val = cx.eval(base)?; - let base_ty = cx.tables.expr_ty(base).subst(tcx, cx.substs); - if ty == base_ty { - base_val - } else { - match cast_const(tcx, base_val.val, ty) { - Ok(val) => mk_const(val), - Err(kind) => signal!(e, kind), - } - } - } - hir::ExprPath(ref qpath) => { - let substs = cx.tables.node_substs(e.hir_id).subst(tcx, cx.substs); - match cx.tables.qpath_def(qpath, e.hir_id) { - Def::Const(def_id) | - Def::AssociatedConst(def_id) => { - let substs = tcx.normalize_associated_type_in_env(&substs, cx.param_env); - match tcx.at(e.span).const_eval(cx.param_env.and((def_id, substs))) { - Ok(val) => val, - Err(ConstEvalErr { kind: TypeckError, .. }) => { - signal!(e, TypeckError); - } - Err(err) => { - debug!("bad reference: {:?}, {:?}", err.description(), err.span); - signal!(e, ErroneousReferencedConstant(box err)) - }, - } - }, - Def::VariantCtor(variant_def, CtorKind::Const) => { - mk_const(Variant(variant_def)) - } - Def::VariantCtor(_, CtorKind::Fn) => { - signal!(e, UnimplementedConstVal("enum variants")); - } - Def::StructCtor(_, CtorKind::Const) => { - mk_const(Aggregate(Struct(&[]))) - } - Def::StructCtor(_, CtorKind::Fn) => { - signal!(e, UnimplementedConstVal("tuple struct constructors")) - } - Def::Local(id) => { - debug!("Def::Local({:?}): {:?}", id, cx.fn_args); - if let Some(&val) = cx.fn_args.as_ref().and_then(|args| args.get(&id)) { - val - } else { - signal!(e, NonConstPath); - } - }, - Def::Method(id) | Def::Fn(id) => mk_const(Function(id, substs)), - Def::Err => span_bug!(e.span, "typeck error"), - _ => signal!(e, NonConstPath), - } - } - hir::ExprCall(ref callee, ref args) => { - let (def_id, substs) = match cx.eval(callee)?.val { - Function(def_id, substs) => (def_id, substs), - _ => signal!(e, TypeckError), - }; - - if tcx.fn_sig(def_id).abi() == Abi::RustIntrinsic { - let layout_of = |ty: Ty<'tcx>| { - let ty = tcx.erase_regions(&ty); - tcx.at(e.span).layout_of(cx.param_env.and(ty)).map_err(|err| { - ConstEvalErr { span: e.span, kind: LayoutError(err) } - }) - }; - match &tcx.item_name(def_id)[..] { - "size_of" => { - let size = layout_of(substs.type_at(0))?.size.bytes(); - return Ok(mk_const(Integral(Usize(ConstUsize::new(size, - tcx.sess.target.usize_ty).unwrap())))); - } - "min_align_of" => { - let align = layout_of(substs.type_at(0))?.align.abi(); - return Ok(mk_const(Integral(Usize(ConstUsize::new(align, - tcx.sess.target.usize_ty).unwrap())))); - } - "type_id" => { - let type_id = tcx.type_id_hash(substs.type_at(0)); - return Ok(mk_const(Integral(U64(type_id)))); - } - _ => signal!(e, TypeckError) - } - } - - let body = if let Some(node_id) = tcx.hir.as_local_node_id(def_id) { - if let Some(fn_like) = FnLikeNode::from_node(tcx.hir.get(node_id)) { - if fn_like.constness() == hir::Constness::Const { - tcx.hir.body(fn_like.body()) - } else { - signal!(e, TypeckError) - } - } else { - signal!(e, TypeckError) - } - } else { - if tcx.is_const_fn(def_id) { - tcx.extern_const_body(def_id).body - } else { - signal!(e, TypeckError) - } - }; - - let arg_ids = body.arguments.iter().map(|arg| match arg.pat.node { - hir::PatKind::Binding(_, canonical_id, _, _) => Some(canonical_id), - _ => None - }).collect::>(); - assert_eq!(arg_ids.len(), args.len()); - - let mut call_args = NodeMap(); - for (arg, arg_expr) in arg_ids.into_iter().zip(args.iter()) { - let arg_val = cx.eval(arg_expr)?; - debug!("const call arg: {:?}", arg); - if let Some(id) = arg { - assert!(call_args.insert(id, arg_val).is_none()); - } - } - debug!("const call({:?})", call_args); - let callee_cx = ConstContext { - tcx, - param_env: cx.param_env, - tables: tcx.typeck_tables_of(def_id), - substs, - fn_args: Some(call_args) - }; - callee_cx.eval(&body.value)? - }, - hir::ExprLit(ref lit) => match lit_to_const(&lit.node, tcx, ty, false) { - Ok(val) => mk_const(val), - Err(err) => signal!(e, err), - }, - hir::ExprBlock(ref block) => { - match block.expr { - Some(ref expr) => cx.eval(expr)?, - None => mk_const(Aggregate(Tuple(&[]))), - } - } - hir::ExprType(ref e, _) => cx.eval(e)?, - hir::ExprTup(ref fields) => { - let values = fields.iter().map(|e| cx.eval(e)).collect::, _>>()?; - mk_const(Aggregate(Tuple(tcx.alloc_const_slice(&values)))) - } - hir::ExprStruct(_, ref fields, _) => { - mk_const(Aggregate(Struct(tcx.alloc_name_const_slice(&fields.iter().map(|f| { - cx.eval(&f.expr).map(|v| (f.name.node, v)) - }).collect::, _>>()?)))) - } - hir::ExprIndex(ref arr, ref idx) => { - if !tcx.features().const_indexing { - signal!(e, IndexOpFeatureGated); - } - let arr = cx.eval(arr)?; - let idx = match cx.eval(idx)?.val { - Integral(Usize(i)) => i.as_u64(), - _ => signal!(idx, IndexNotUsize), - }; - assert_eq!(idx as usize as u64, idx); - match arr.val { - Aggregate(Array(v)) => { - if let Some(&elem) = v.get(idx as usize) { - elem - } else { - let n = v.len() as u64; - signal!(e, IndexOutOfBounds { len: n, index: idx }) - } - } - - Aggregate(Repeat(.., n)) if idx >= n => { - signal!(e, IndexOutOfBounds { len: n, index: idx }) - } - Aggregate(Repeat(elem, _)) => elem, - - ByteStr(b) if idx >= b.data.len() as u64 => { - signal!(e, IndexOutOfBounds { len: b.data.len() as u64, index: idx }) - } - ByteStr(b) => { - mk_const(Integral(U8(b.data[idx as usize]))) - }, - - _ => signal!(e, IndexedNonVec), - } - } - hir::ExprArray(ref v) => { - let values = v.iter().map(|e| cx.eval(e)).collect::, _>>()?; - mk_const(Aggregate(Array(tcx.alloc_const_slice(&values)))) - } - hir::ExprRepeat(ref elem, _) => { - let n = match ty.sty { - ty::TyArray(_, n) => n.val.unwrap_u64(), - _ => span_bug!(e.span, "typeck error") - }; - mk_const(Aggregate(Repeat(cx.eval(elem)?, n))) - }, - hir::ExprTupField(ref base, index) => { - if let Aggregate(Tuple(fields)) = cx.eval(base)?.val { - fields[index.node] - } else { - span_bug!(base.span, "{:#?}", cx.eval(base)?.val); - //signal!(base, ExpectedConstTuple); - } - } - hir::ExprField(ref base, field_name) => { - if let Aggregate(Struct(fields)) = cx.eval(base)?.val { - if let Some(&(_, f)) = fields.iter().find(|&&(name, _)| name == field_name.node) { - f - } else { - signal!(e, MissingStructField); - } - } else { - signal!(base, ExpectedConstStruct); - } - } - hir::ExprAddrOf(..) => signal!(e, UnimplementedConstVal("address operator")), - _ => signal!(e, MiscCatchAll) - }; - - Ok(result) -} - -fn cast_const_int<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - val: ConstInt, - ty: Ty<'tcx>) - -> CastResult<'tcx> { - let v = val.to_u128_unchecked(); - match ty.sty { - ty::TyBool if v == 0 => Ok(Bool(false)), - ty::TyBool if v == 1 => Ok(Bool(true)), - ty::TyInt(ast::IntTy::I8) => Ok(Integral(I8(v as i128 as i8))), - ty::TyInt(ast::IntTy::I16) => Ok(Integral(I16(v as i128 as i16))), - ty::TyInt(ast::IntTy::I32) => Ok(Integral(I32(v as i128 as i32))), - ty::TyInt(ast::IntTy::I64) => Ok(Integral(I64(v as i128 as i64))), - ty::TyInt(ast::IntTy::I128) => Ok(Integral(I128(v as i128))), - ty::TyInt(ast::IntTy::Isize) => { - Ok(Integral(Isize(ConstIsize::new_truncating(v as i128, tcx.sess.target.isize_ty)))) - }, - ty::TyUint(ast::UintTy::U8) => Ok(Integral(U8(v as u8))), - ty::TyUint(ast::UintTy::U16) => Ok(Integral(U16(v as u16))), - ty::TyUint(ast::UintTy::U32) => Ok(Integral(U32(v as u32))), - ty::TyUint(ast::UintTy::U64) => Ok(Integral(U64(v as u64))), - ty::TyUint(ast::UintTy::U128) => Ok(Integral(U128(v as u128))), - ty::TyUint(ast::UintTy::Usize) => { - Ok(Integral(Usize(ConstUsize::new_truncating(v, tcx.sess.target.usize_ty)))) - }, - ty::TyFloat(fty) => { - if let Some(i) = val.to_u128() { - Ok(Float(ConstFloat::from_u128(i, fty))) - } else { - // The value must be negative, go through signed integers. - let i = val.to_u128_unchecked() as i128; - Ok(Float(ConstFloat::from_i128(i, fty))) - } - } - ty::TyRawPtr(_) => Err(ErrKind::UnimplementedConstVal("casting an address to a raw ptr")), - ty::TyChar => match val { - U8(u) => Ok(Char(u as char)), - _ => bug!(), - }, - _ => Err(CannotCast), - } -} - -fn cast_const_float<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - val: ConstFloat, - ty: Ty<'tcx>) -> CastResult<'tcx> { - let int_width = |ty| { - ty::layout::Integer::from_attr(tcx, ty).size().bits() as usize - }; - match ty.sty { - ty::TyInt(ity) => { - if let Some(i) = val.to_i128(int_width(attr::SignedInt(ity))) { - cast_const_int(tcx, I128(i), ty) - } else { - Err(CannotCast) - } - } - ty::TyUint(uty) => { - if let Some(i) = val.to_u128(int_width(attr::UnsignedInt(uty))) { - cast_const_int(tcx, U128(i), ty) - } else { - Err(CannotCast) - } - } - ty::TyFloat(fty) => Ok(Float(val.convert(fty))), - _ => Err(CannotCast), - } -} - -fn cast_const<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - val: ConstVal<'tcx>, - ty: Ty<'tcx>) - -> CastResult<'tcx> { - match val { - Integral(i) => cast_const_int(tcx, i, ty), - Bool(b) => cast_const_int(tcx, U8(b as u8), ty), - Float(f) => cast_const_float(tcx, f, ty), - Char(c) => cast_const_int(tcx, U32(c as u32), ty), - Variant(v) => { - let adt = tcx.adt_def(tcx.parent_def_id(v).unwrap()); - let idx = adt.variant_index_with_id(v); - cast_const_int(tcx, adt.discriminant_for_variant(tcx, idx), ty) - } - Function(..) => Err(UnimplementedConstVal("casting fn pointers")), - ByteStr(b) => match ty.sty { - ty::TyRawPtr(_) => { - Err(ErrKind::UnimplementedConstVal("casting a bytestr to a raw ptr")) - }, - ty::TyRef(_, ty::TypeAndMut { ref ty, mutbl: hir::MutImmutable }) => match ty.sty { - ty::TyArray(ty, n) => { - let n = n.val.unwrap_u64(); - if ty == tcx.types.u8 && n == b.data.len() as u64 { - Ok(val) - } else { - Err(CannotCast) - } - } - ty::TySlice(_) => { - Err(ErrKind::UnimplementedConstVal("casting a bytestr to slice")) - }, - _ => Err(CannotCast), - }, - _ => Err(CannotCast), - }, - Str(s) => match ty.sty { - ty::TyRawPtr(_) => Err(ErrKind::UnimplementedConstVal("casting a str to a raw ptr")), - ty::TyRef(_, ty::TypeAndMut { ref ty, mutbl: hir::MutImmutable }) => match ty.sty { - ty::TyStr => Ok(Str(s)), - _ => Err(CannotCast), - }, - _ => Err(CannotCast), - }, - _ => Err(CannotCast), - } -} - -pub fn lit_to_const<'a, 'tcx>(lit: &'tcx ast::LitKind, - tcx: TyCtxt<'a, 'tcx, 'tcx>, - mut ty: Ty<'tcx>, - neg: bool) - -> Result, ErrKind<'tcx>> { - use syntax::ast::*; - use syntax::ast::LitIntType::*; - - if tcx.sess.opts.debugging_opts.miri { - use rustc::mir::interpret::*; - let lit = match *lit { - LitKind::Str(ref s, _) => { - let s = s.as_str(); - let id = tcx.allocate_cached(s.as_bytes()); - let ptr = MemoryPointer::new(AllocId(id), 0); - Value::ByValPair( - PrimVal::Ptr(ptr), - PrimVal::from_u128(s.len() as u128), - ) - }, - LitKind::ByteStr(ref data) => { - let id = tcx.allocate_cached(data); - let ptr = MemoryPointer::new(AllocId(id), 0); - Value::ByVal(PrimVal::Ptr(ptr)) - }, - LitKind::Byte(n) => Value::ByVal(PrimVal::Bytes(n as u128)), - LitKind::Int(n, _) if neg => { - let n = n as i128; - let n = n.overflowing_neg().0; - Value::ByVal(PrimVal::Bytes(n as u128)) - }, - LitKind::Int(n, _) => Value::ByVal(PrimVal::Bytes(n as u128)), - LitKind::Float(n, fty) => { - let n = n.as_str(); - let mut f = parse_float(&n, fty)?; - if neg { - f = -f; - } - let bits = f.bits; - Value::ByVal(PrimVal::Bytes(bits)) - } - LitKind::FloatUnsuffixed(n) => { - let fty = match ty.sty { - ty::TyFloat(fty) => fty, - _ => bug!() - }; - let n = n.as_str(); - let mut f = parse_float(&n, fty)?; - if neg { - f = -f; - } - let bits = f.bits; - Value::ByVal(PrimVal::Bytes(bits)) - } - LitKind::Bool(b) => Value::ByVal(PrimVal::Bytes(b as u128)), - LitKind::Char(c) => Value::ByVal(PrimVal::Bytes(c as u128)), - }; - return Ok(ConstVal::Value(lit)); - } - - if let ty::TyAdt(adt, _) = ty.sty { - if adt.is_enum() { - ty = adt.repr.discr_type().to_ty(tcx) - } - } - - match *lit { - LitKind::Str(ref s, _) => Ok(Str(s.as_str())), - LitKind::ByteStr(ref data) => Ok(ByteStr(ByteArray { data })), - LitKind::Byte(n) => Ok(Integral(U8(n))), - LitKind::Int(n, hint) => { - match (&ty.sty, hint) { - (&ty::TyInt(ity), _) | - (_, Signed(ity)) => { - let mut n = n as i128; - if neg { - n = n.overflowing_neg().0; - } - Ok(Integral(ConstInt::new_signed_truncating(n, - ity, tcx.sess.target.isize_ty))) - } - (&ty::TyUint(uty), _) | - (_, Unsigned(uty)) => { - Ok(Integral(ConstInt::new_unsigned_truncating(n, - uty, tcx.sess.target.usize_ty))) - } - _ => bug!() - } - } - LitKind::Float(n, fty) => { - let mut f = parse_float(&n.as_str(), fty)?; - if neg { - f = -f; - } - Ok(Float(f)) - } - LitKind::FloatUnsuffixed(n) => { - let fty = match ty.sty { - ty::TyFloat(fty) => fty, - _ => bug!() - }; - let mut f = parse_float(&n.as_str(), fty)?; - if neg { - f = -f; - } - Ok(Float(f)) - } - LitKind::Bool(b) => Ok(Bool(b)), - LitKind::Char(c) => Ok(Char(c)), - } -} - -fn parse_float<'tcx>(num: &str, fty: ast::FloatTy) - -> Result> { - ConstFloat::from_str(num, fty).map_err(|_| { - // FIXME(#31407) this is only necessary because float parsing is buggy - UnimplementedConstVal("could not evaluate float literal (see issue #31407)") - }) -} - -pub fn compare_const_vals(a: &ConstVal, b: &ConstVal, ty: Ty) -> Option { - trace!("compare_const_vals: {:?}, {:?}", a, b); - use rustc::mir::interpret::{Value, PrimVal}; - match (a, b) { - (&Integral(a), &Integral(b)) => a.try_cmp(b).ok(), - (&Char(a), &Char(b)) => Some(a.cmp(&b)), - (&Value(Value::ByVal(PrimVal::Bytes(a))), - &Value(Value::ByVal(PrimVal::Bytes(b)))) => { - Some(if ty.is_signed() { - (a as i128).cmp(&(b as i128)) - } else { - a.cmp(&b) - }) - }, - _ if a == b => Some(Ordering::Equal), - _ => None, - } -} - -impl<'a, 'tcx> ConstContext<'a, 'tcx> { - pub fn compare_lit_exprs(&self, - a: &'tcx Expr, - b: &'tcx Expr) -> Result, ErrorReported> { - let tcx = self.tcx; - let ty = self.tables.expr_ty(a); - let a = match self.eval(a) { - Ok(a) => a, - Err(e) => { - e.report(tcx, a.span, "expression"); - return Err(ErrorReported); - } - }; - let b = match self.eval(b) { - Ok(b) => b, - Err(e) => { - e.report(tcx, b.span, "expression"); - return Err(ErrorReported); - } - }; - Ok(compare_const_vals(&a.val, &b.val, ty)) - } -} diff --git a/src/librustc_const_eval/pattern.rs b/src/librustc_const_eval/pattern.rs deleted file mode 100644 index a2daf22c3b4..00000000000 --- a/src/librustc_const_eval/pattern.rs +++ /dev/null @@ -1,1069 +0,0 @@ -// Copyright 2016 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -use eval; - -use rustc::middle::const_val::{ConstEvalErr, ConstVal, ConstAggregate}; -use rustc::mir::{Field, BorrowKind, Mutability}; -use rustc::mir::interpret::{Value, PrimVal}; -use rustc::ty::{self, TyCtxt, AdtDef, Ty, Region}; -use rustc::ty::subst::{Substs, Kind}; -use rustc::hir::{self, PatKind, RangeEnd}; -use rustc::hir::def::{Def, CtorKind}; -use rustc::hir::pat_util::EnumerateAndAdjustIterator; - -use rustc_data_structures::indexed_vec::Idx; - -use std::fmt; -use syntax::ast; -use syntax::ptr::P; -use syntax_pos::Span; - -#[derive(Clone, Debug)] -pub enum PatternError<'tcx> { - AssociatedConstInPattern(Span), - StaticInPattern(Span), - ConstEval(ConstEvalErr<'tcx>), -} - -#[derive(Copy, Clone, Debug)] -pub enum BindingMode<'tcx> { - ByValue, - ByRef(Region<'tcx>, BorrowKind), -} - -#[derive(Clone, Debug)] -pub struct FieldPattern<'tcx> { - pub field: Field, - pub pattern: Pattern<'tcx>, -} - -#[derive(Clone, Debug)] -pub struct Pattern<'tcx> { - pub ty: Ty<'tcx>, - pub span: Span, - pub kind: Box>, -} - -#[derive(Clone, Debug)] -pub enum PatternKind<'tcx> { - Wild, - - /// x, ref x, x @ P, etc - Binding { - mutability: Mutability, - name: ast::Name, - mode: BindingMode<'tcx>, - var: ast::NodeId, - ty: Ty<'tcx>, - subpattern: Option>, - }, - - /// Foo(...) or Foo{...} or Foo, where `Foo` is a variant name from an adt with >1 variants - Variant { - adt_def: &'tcx AdtDef, - substs: &'tcx Substs<'tcx>, - variant_index: usize, - subpatterns: Vec>, - }, - - /// (...), Foo(...), Foo{...}, or Foo, where `Foo` is a variant name from an adt with 1 variant - Leaf { - subpatterns: Vec>, - }, - - /// box P, &P, &mut P, etc - Deref { - subpattern: Pattern<'tcx>, - }, - - Constant { - value: &'tcx ty::Const<'tcx>, - }, - - Range { - lo: &'tcx ty::Const<'tcx>, - hi: &'tcx ty::Const<'tcx>, - end: RangeEnd, - }, - - /// matches against a slice, checking the length and extracting elements. - /// irrefutable when there is a slice pattern and both `prefix` and `suffix` are empty. - /// e.g. `&[ref xs..]`. - Slice { - prefix: Vec>, - slice: Option>, - suffix: Vec>, - }, - - /// fixed match against an array, irrefutable - Array { - prefix: Vec>, - slice: Option>, - suffix: Vec>, - }, -} - -fn print_const_val(value: &ty::Const, f: &mut fmt::Formatter) -> fmt::Result { - match value.val { - ConstVal::Float(ref x) => write!(f, "{}", x), - ConstVal::Integral(ref i) => write!(f, "{}", i), - ConstVal::Str(ref s) => write!(f, "{:?}", &s[..]), - ConstVal::ByteStr(b) => write!(f, "{:?}", b.data), - ConstVal::Bool(b) => write!(f, "{:?}", b), - ConstVal::Char(c) => write!(f, "{:?}", c), - ConstVal::Value(v) => print_miri_value(v, value.ty, f), - ConstVal::Variant(_) | - ConstVal::Function(..) | - ConstVal::Aggregate(_) | - ConstVal::Unevaluated(..) => bug!("{:?} not printable in a pattern", value) - } -} - -fn print_miri_value(value: Value, ty: Ty, f: &mut fmt::Formatter) -> fmt::Result { - use rustc::ty::TypeVariants::*; - match (value, &ty.sty) { - (Value::ByVal(PrimVal::Bytes(0)), &TyBool) => write!(f, "false"), - (Value::ByVal(PrimVal::Bytes(1)), &TyBool) => write!(f, "true"), - (Value::ByVal(PrimVal::Bytes(n)), &TyUint(..)) => write!(f, "{:?}", n), - (Value::ByVal(PrimVal::Bytes(n)), &TyInt(..)) => write!(f, "{:?}", n as i128), - (Value::ByVal(PrimVal::Bytes(n)), &TyChar) => - write!(f, "{:?}", ::std::char::from_u32(n as u32).unwrap()), - _ => bug!("{:?}: {} not printable in a pattern", value, ty), - } -} - -impl<'tcx> fmt::Display for Pattern<'tcx> { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - match *self.kind { - PatternKind::Wild => write!(f, "_"), - PatternKind::Binding { mutability, name, mode, ref subpattern, .. } => { - let is_mut = match mode { - BindingMode::ByValue => mutability == Mutability::Mut, - BindingMode::ByRef(_, bk) => { - write!(f, "ref ")?; - match bk { BorrowKind::Mut { .. } => true, _ => false } - } - }; - if is_mut { - write!(f, "mut ")?; - } - write!(f, "{}", name)?; - if let Some(ref subpattern) = *subpattern { - write!(f, " @ {}", subpattern)?; - } - Ok(()) - } - PatternKind::Variant { ref subpatterns, .. } | - PatternKind::Leaf { ref subpatterns } => { - let variant = match *self.kind { - PatternKind::Variant { adt_def, variant_index, .. } => { - Some(&adt_def.variants[variant_index]) - } - _ => if let ty::TyAdt(adt, _) = self.ty.sty { - if !adt.is_enum() { - Some(&adt.variants[0]) - } else { - None - } - } else { - None - } - }; - - let mut first = true; - let mut start_or_continue = || if first { first = false; "" } else { ", " }; - - if let Some(variant) = variant { - write!(f, "{}", variant.name)?; - - // Only for TyAdt we can have `S {...}`, - // which we handle separately here. - if variant.ctor_kind == CtorKind::Fictive { - write!(f, " {{ ")?; - - let mut printed = 0; - for p in subpatterns { - if let PatternKind::Wild = *p.pattern.kind { - continue; - } - let name = variant.fields[p.field.index()].name; - write!(f, "{}{}: {}", start_or_continue(), name, p.pattern)?; - printed += 1; - } - - if printed < variant.fields.len() { - write!(f, "{}..", start_or_continue())?; - } - - return write!(f, " }}"); - } - } - - let num_fields = variant.map_or(subpatterns.len(), |v| v.fields.len()); - if num_fields != 0 || variant.is_none() { - write!(f, "(")?; - for i in 0..num_fields { - write!(f, "{}", start_or_continue())?; - - // Common case: the field is where we expect it. - if let Some(p) = subpatterns.get(i) { - if p.field.index() == i { - write!(f, "{}", p.pattern)?; - continue; - } - } - - // Otherwise, we have to go looking for it. - if let Some(p) = subpatterns.iter().find(|p| p.field.index() == i) { - write!(f, "{}", p.pattern)?; - } else { - write!(f, "_")?; - } - } - write!(f, ")")?; - } - - Ok(()) - } - PatternKind::Deref { ref subpattern } => { - match self.ty.sty { - ty::TyAdt(def, _) if def.is_box() => write!(f, "box ")?, - ty::TyRef(_, mt) => { - write!(f, "&")?; - if mt.mutbl == hir::MutMutable { - write!(f, "mut ")?; - } - } - _ => bug!("{} is a bad Deref pattern type", self.ty) - } - write!(f, "{}", subpattern) - } - PatternKind::Constant { value } => { - print_const_val(value, f) - } - PatternKind::Range { lo, hi, end } => { - print_const_val(lo, f)?; - match end { - RangeEnd::Included => write!(f, "...")?, - RangeEnd::Excluded => write!(f, "..")?, - } - print_const_val(hi, f) - } - PatternKind::Slice { ref prefix, ref slice, ref suffix } | - PatternKind::Array { ref prefix, ref slice, ref suffix } => { - let mut first = true; - let mut start_or_continue = || if first { first = false; "" } else { ", " }; - write!(f, "[")?; - for p in prefix { - write!(f, "{}{}", start_or_continue(), p)?; - } - if let Some(ref slice) = *slice { - write!(f, "{}", start_or_continue())?; - match *slice.kind { - PatternKind::Wild => {} - _ => write!(f, "{}", slice)? - } - write!(f, "..")?; - } - for p in suffix { - write!(f, "{}{}", start_or_continue(), p)?; - } - write!(f, "]") - } - } - } -} - -pub struct PatternContext<'a, 'tcx: 'a> { - pub tcx: TyCtxt<'a, 'tcx, 'tcx>, - pub param_env: ty::ParamEnv<'tcx>, - pub tables: &'a ty::TypeckTables<'tcx>, - pub substs: &'tcx Substs<'tcx>, - pub errors: Vec>, -} - -impl<'a, 'tcx> Pattern<'tcx> { - pub fn from_hir(tcx: TyCtxt<'a, 'tcx, 'tcx>, - param_env_and_substs: ty::ParamEnvAnd<'tcx, &'tcx Substs<'tcx>>, - tables: &'a ty::TypeckTables<'tcx>, - pat: &'tcx hir::Pat) -> Self { - let mut pcx = PatternContext::new(tcx, param_env_and_substs, tables); - let result = pcx.lower_pattern(pat); - if !pcx.errors.is_empty() { - let msg = format!("encountered errors lowering pattern: {:?}", pcx.errors); - tcx.sess.delay_span_bug(pat.span, &msg); - } - debug!("Pattern::from_hir({:?}) = {:?}", pat, result); - result - } -} - -impl<'a, 'tcx> PatternContext<'a, 'tcx> { - pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, - param_env_and_substs: ty::ParamEnvAnd<'tcx, &'tcx Substs<'tcx>>, - tables: &'a ty::TypeckTables<'tcx>) -> Self { - PatternContext { - tcx, - param_env: param_env_and_substs.param_env, - tables, - substs: param_env_and_substs.value, - errors: vec![] - } - } - - pub fn lower_pattern(&mut self, pat: &'tcx hir::Pat) -> Pattern<'tcx> { - // When implicit dereferences have been inserted in this pattern, the unadjusted lowered - // pattern has the type that results *after* dereferencing. For example, in this code: - // - // ``` - // match &&Some(0i32) { - // Some(n) => { ... }, - // _ => { ... }, - // } - // ``` - // - // the type assigned to `Some(n)` in `unadjusted_pat` would be `Option` (this is - // determined in rustc_typeck::check::match). The adjustments would be - // - // `vec![&&Option, &Option]`. - // - // Applying the adjustments, we want to instead output `&&Some(n)` (as a HAIR pattern). So - // we wrap the unadjusted pattern in `PatternKind::Deref` repeatedly, consuming the - // adjustments in *reverse order* (last-in-first-out, so that the last `Deref` inserted - // gets the least-dereferenced type). - let unadjusted_pat = self.lower_pattern_unadjusted(pat); - self.tables - .pat_adjustments() - .get(pat.hir_id) - .unwrap_or(&vec![]) - .iter() - .rev() - .fold(unadjusted_pat, |pat, ref_ty| { - debug!("{:?}: wrapping pattern with type {:?}", pat, ref_ty); - Pattern { - span: pat.span, - ty: ref_ty, - kind: Box::new(PatternKind::Deref { subpattern: pat }), - } - }, - ) - } - - fn lower_pattern_unadjusted(&mut self, pat: &'tcx hir::Pat) -> Pattern<'tcx> { - let mut ty = self.tables.node_id_to_type(pat.hir_id); - - let kind = match pat.node { - PatKind::Wild => PatternKind::Wild, - - PatKind::Lit(ref value) => self.lower_lit(value), - - PatKind::Range(ref lo, ref hi, end) => { - match (self.lower_lit(lo), self.lower_lit(hi)) { - (PatternKind::Constant { value: lo }, - PatternKind::Constant { value: hi }) => { - PatternKind::Range { lo, hi, end } - } - _ => PatternKind::Wild - } - } - - PatKind::Path(ref qpath) => { - return self.lower_path(qpath, pat.hir_id, pat.span); - } - - PatKind::Ref(ref subpattern, _) | - PatKind::Box(ref subpattern) => { - PatternKind::Deref { subpattern: self.lower_pattern(subpattern) } - } - - PatKind::Slice(ref prefix, ref slice, ref suffix) => { - let ty = self.tables.node_id_to_type(pat.hir_id); - match ty.sty { - ty::TyRef(_, mt) => - PatternKind::Deref { - subpattern: Pattern { - ty: mt.ty, - span: pat.span, - kind: Box::new(self.slice_or_array_pattern( - pat.span, mt.ty, prefix, slice, suffix)) - }, - }, - - ty::TySlice(..) | - ty::TyArray(..) => - self.slice_or_array_pattern(pat.span, ty, prefix, slice, suffix), - - ref sty => - span_bug!( - pat.span, - "unexpanded type for vector pattern: {:?}", - sty), - } - } - - PatKind::Tuple(ref subpatterns, ddpos) => { - let ty = self.tables.node_id_to_type(pat.hir_id); - match ty.sty { - ty::TyTuple(ref tys, _) => { - let subpatterns = - subpatterns.iter() - .enumerate_and_adjust(tys.len(), ddpos) - .map(|(i, subpattern)| FieldPattern { - field: Field::new(i), - pattern: self.lower_pattern(subpattern) - }) - .collect(); - - PatternKind::Leaf { subpatterns: subpatterns } - } - - ref sty => span_bug!(pat.span, "unexpected type for tuple pattern: {:?}", sty), - } - } - - PatKind::Binding(_, id, ref ident, ref sub) => { - let var_ty = self.tables.node_id_to_type(pat.hir_id); - let region = match var_ty.sty { - ty::TyRef(r, _) => Some(r), - _ => None, - }; - let bm = *self.tables.pat_binding_modes().get(pat.hir_id) - .expect("missing binding mode"); - let (mutability, mode) = match bm { - ty::BindByValue(hir::MutMutable) => - (Mutability::Mut, BindingMode::ByValue), - ty::BindByValue(hir::MutImmutable) => - (Mutability::Not, BindingMode::ByValue), - ty::BindByReference(hir::MutMutable) => - (Mutability::Not, BindingMode::ByRef( - region.unwrap(), BorrowKind::Mut { allow_two_phase_borrow: false })), - ty::BindByReference(hir::MutImmutable) => - (Mutability::Not, BindingMode::ByRef( - region.unwrap(), BorrowKind::Shared)), - }; - - // A ref x pattern is the same node used for x, and as such it has - // x's type, which is &T, where we want T (the type being matched). - if let ty::BindByReference(_) = bm { - if let ty::TyRef(_, mt) = ty.sty { - ty = mt.ty; - } else { - bug!("`ref {}` has wrong type {}", ident.node, ty); - } - } - - PatternKind::Binding { - mutability, - mode, - name: ident.node, - var: id, - ty: var_ty, - subpattern: self.lower_opt_pattern(sub), - } - } - - PatKind::TupleStruct(ref qpath, ref subpatterns, ddpos) => { - let def = self.tables.qpath_def(qpath, pat.hir_id); - let adt_def = match ty.sty { - ty::TyAdt(adt_def, _) => adt_def, - _ => span_bug!(pat.span, "tuple struct pattern not applied to an ADT"), - }; - let variant_def = adt_def.variant_of_def(def); - - let subpatterns = - subpatterns.iter() - .enumerate_and_adjust(variant_def.fields.len(), ddpos) - .map(|(i, field)| FieldPattern { - field: Field::new(i), - pattern: self.lower_pattern(field), - }) - .collect(); - self.lower_variant_or_leaf(def, ty, subpatterns) - } - - PatKind::Struct(ref qpath, ref fields, _) => { - let def = self.tables.qpath_def(qpath, pat.hir_id); - let adt_def = match ty.sty { - ty::TyAdt(adt_def, _) => adt_def, - _ => { - span_bug!( - pat.span, - "struct pattern not applied to an ADT"); - } - }; - let variant_def = adt_def.variant_of_def(def); - - let subpatterns = - fields.iter() - .map(|field| { - let index = variant_def.index_of_field_named(field.node.name); - let index = index.unwrap_or_else(|| { - span_bug!( - pat.span, - "no field with name {:?}", - field.node.name); - }); - FieldPattern { - field: Field::new(index), - pattern: self.lower_pattern(&field.node.pat), - } - }) - .collect(); - - self.lower_variant_or_leaf(def, ty, subpatterns) - } - }; - - Pattern { - span: pat.span, - ty, - kind: Box::new(kind), - } - } - - fn lower_patterns(&mut self, pats: &'tcx [P]) -> Vec> { - pats.iter().map(|p| self.lower_pattern(p)).collect() - } - - fn lower_opt_pattern(&mut self, pat: &'tcx Option>) -> Option> - { - pat.as_ref().map(|p| self.lower_pattern(p)) - } - - fn flatten_nested_slice_patterns( - &mut self, - prefix: Vec>, - slice: Option>, - suffix: Vec>) - -> (Vec>, Option>, Vec>) - { - let orig_slice = match slice { - Some(orig_slice) => orig_slice, - None => return (prefix, slice, suffix) - }; - let orig_prefix = prefix; - let orig_suffix = suffix; - - // dance because of intentional borrow-checker stupidity. - let kind = *orig_slice.kind; - match kind { - PatternKind::Slice { prefix, slice, mut suffix } | - PatternKind::Array { prefix, slice, mut suffix } => { - let mut orig_prefix = orig_prefix; - - orig_prefix.extend(prefix); - suffix.extend(orig_suffix); - - (orig_prefix, slice, suffix) - } - _ => { - (orig_prefix, Some(Pattern { - kind: box kind, ..orig_slice - }), orig_suffix) - } - } - } - - fn slice_or_array_pattern( - &mut self, - span: Span, - ty: Ty<'tcx>, - prefix: &'tcx [P], - slice: &'tcx Option>, - suffix: &'tcx [P]) - -> PatternKind<'tcx> - { - let prefix = self.lower_patterns(prefix); - let slice = self.lower_opt_pattern(slice); - let suffix = self.lower_patterns(suffix); - let (prefix, slice, suffix) = - self.flatten_nested_slice_patterns(prefix, slice, suffix); - - match ty.sty { - ty::TySlice(..) => { - // matching a slice or fixed-length array - PatternKind::Slice { prefix: prefix, slice: slice, suffix: suffix } - } - - ty::TyArray(_, len) => { - // fixed-length array - let len = len.val.unwrap_u64(); - assert!(len >= prefix.len() as u64 + suffix.len() as u64); - PatternKind::Array { prefix: prefix, slice: slice, suffix: suffix } - } - - _ => { - span_bug!(span, "bad slice pattern type {:?}", ty); - } - } - } - - fn lower_variant_or_leaf( - &mut self, - def: Def, - ty: Ty<'tcx>, - subpatterns: Vec>) - -> PatternKind<'tcx> - { - match def { - Def::Variant(variant_id) | Def::VariantCtor(variant_id, ..) => { - let enum_id = self.tcx.parent_def_id(variant_id).unwrap(); - let adt_def = self.tcx.adt_def(enum_id); - if adt_def.is_enum() { - let substs = match ty.sty { - ty::TyAdt(_, substs) | - ty::TyFnDef(_, substs) => substs, - _ => bug!("inappropriate type for def: {:?}", ty.sty), - }; - PatternKind::Variant { - adt_def, - substs, - variant_index: adt_def.variant_index_with_id(variant_id), - subpatterns, - } - } else { - PatternKind::Leaf { subpatterns: subpatterns } - } - } - - Def::Struct(..) | Def::StructCtor(..) | Def::Union(..) | - Def::TyAlias(..) | Def::AssociatedTy(..) | Def::SelfTy(..) => { - PatternKind::Leaf { subpatterns: subpatterns } - } - - _ => bug!() - } - } - - fn lower_path(&mut self, - qpath: &hir::QPath, - id: hir::HirId, - span: Span) - -> Pattern<'tcx> { - let ty = self.tables.node_id_to_type(id); - let def = self.tables.qpath_def(qpath, id); - let is_associated_const = match def { - Def::AssociatedConst(_) => true, - _ => false, - }; - let kind = match def { - Def::Const(def_id) | Def::AssociatedConst(def_id) => { - let substs = self.tables.node_substs(id); - match self.tcx.at(span).const_eval(self.param_env.and((def_id, substs))) { - Ok(value) => { - if self.tcx.sess.opts.debugging_opts.miri { - if let ConstVal::Value(_) = value.val {} else { - panic!("const eval produced non-miri value: {:#?}", value); - } - } - let instance = ty::Instance::resolve( - self.tcx, - self.param_env, - def_id, - substs, - ).unwrap(); - return self.const_to_pat(instance, value, span) - }, - Err(e) => { - self.errors.push(PatternError::ConstEval(e)); - PatternKind::Wild - } - } - } - _ => self.lower_variant_or_leaf(def, ty, vec![]), - }; - - Pattern { - span, - ty, - kind: Box::new(kind), - } - } - - fn lower_lit(&mut self, expr: &'tcx hir::Expr) -> PatternKind<'tcx> { - if self.tcx.sess.opts.debugging_opts.miri { - return match expr.node { - hir::ExprLit(ref lit) => { - let ty = self.tables.expr_ty(expr); - match ::eval::lit_to_const(&lit.node, self.tcx, ty, false) { - Ok(value) => PatternKind::Constant { - value: self.tcx.mk_const(ty::Const { - ty, - val: value, - }), - }, - Err(e) => { - self.errors.push(PatternError::ConstEval(ConstEvalErr { - span: lit.span, - kind: e, - })); - PatternKind::Wild - }, - } - }, - hir::ExprPath(ref qpath) => *self.lower_path(qpath, expr.hir_id, expr.span).kind, - hir::ExprUnary(hir::UnNeg, ref expr) => { - let ty = self.tables.expr_ty(expr); - let lit = match expr.node { - hir::ExprLit(ref lit) => lit, - _ => span_bug!(expr.span, "not a literal: {:?}", expr), - }; - match ::eval::lit_to_const(&lit.node, self.tcx, ty, true) { - Ok(value) => PatternKind::Constant { - value: self.tcx.mk_const(ty::Const { - ty, - val: value, - }), - }, - Err(e) => { - self.errors.push(PatternError::ConstEval(ConstEvalErr { - span: lit.span, - kind: e, - })); - PatternKind::Wild - }, - } - } - _ => span_bug!(expr.span, "not a literal: {:?}", expr), - } - } - let const_cx = eval::ConstContext::new(self.tcx, - self.param_env.and(self.substs), - self.tables); - match const_cx.eval(expr) { - Ok(value) => { - if let ConstVal::Variant(def_id) = value.val { - let ty = self.tables.expr_ty(expr); - self.lower_variant_or_leaf(Def::Variant(def_id), ty, vec![]) - } else { - PatternKind::Constant { value } - } - } - Err(e) => { - self.errors.push(PatternError::ConstEval(e)); - PatternKind::Wild - } - } - } - - fn const_to_pat( - &self, - instance: ty::Instance<'tcx>, - cv: &'tcx ty::Const<'tcx>, - span: Span, - ) -> Pattern<'tcx> { - debug!("const_to_pat: cv={:#?}", cv); - let kind = match cv.ty.sty { - ty::TyFloat(_) => { - self.tcx.sess.span_err(span, "floating point constants cannot be used in patterns"); - PatternKind::Wild - } - ty::TyAdt(adt_def, _) if adt_def.is_union() => { - // Matching on union fields is unsafe, we can't hide it in constants - self.tcx.sess.span_err(span, "cannot use unions in constant patterns"); - PatternKind::Wild - } - ty::TyAdt(adt_def, _) if !self.tcx.has_attr(adt_def.did, "structural_match") => { - let msg = format!("to use a constant of type `{}` in a pattern, \ - `{}` must be annotated with `#[derive(PartialEq, Eq)]`", - self.tcx.item_path_str(adt_def.did), - self.tcx.item_path_str(adt_def.did)); - self.tcx.sess.span_err(span, &msg); - PatternKind::Wild - }, - ty::TyAdt(adt_def, substs) if adt_def.is_enum() => { - match cv.val { - ConstVal::Value(val) => { - let discr = self.tcx.const_discr(self.param_env.and(( - instance, val, cv.ty - ))).unwrap(); - let variant_index = adt_def - .discriminants(self.tcx) - .position(|var| var.to_u128_unchecked() == discr) - .unwrap(); - PatternKind::Variant { - adt_def, - substs, - variant_index, - subpatterns: adt_def - .variants[variant_index] - .fields - .iter() - .enumerate() - .map(|(i, _)| { - let field = Field::new(i); - let val = match cv.val { - ConstVal::Value(miri) => self.tcx.const_val_field( - self.param_env.and((instance, field, miri, cv.ty)), - ).unwrap(), - _ => bug!("{:#?} is not a valid tuple", cv), - }; - FieldPattern { - field, - pattern: self.const_to_pat(instance, val, span), - } - }).collect(), - } - }, - ConstVal::Variant(var_did) => { - let variant_index = adt_def - .variants - .iter() - .position(|var| var.did == var_did) - .unwrap(); - PatternKind::Variant { - adt_def, - substs, - variant_index, - subpatterns: Vec::new(), - } - } - _ => return Pattern { - span, - ty: cv.ty, - kind: Box::new(PatternKind::Constant { - value: cv, - }), - } - } - }, - ty::TyAdt(adt_def, _) => { - let struct_var = adt_def.struct_variant(); - PatternKind::Leaf { - subpatterns: struct_var.fields.iter().enumerate().map(|(i, f)| { - let field = Field::new(i); - let val = match cv.val { - ConstVal::Aggregate(ConstAggregate::Struct(consts)) => { - consts.iter().find(|&&(name, _)| name == f.name).unwrap().1 - }, - ConstVal::Value(miri) => self.tcx.const_val_field( - self.param_env.and((instance, field, miri, cv.ty)), - ).unwrap(), - _ => bug!("{:#?} is not a valid tuple", cv), - }; - FieldPattern { - field, - pattern: self.const_to_pat(instance, val, span), - } - }).collect() - } - } - ty::TyTuple(fields, _) => { - PatternKind::Leaf { - subpatterns: (0..fields.len()).map(|i| { - let field = Field::new(i); - let val = match cv.val { - ConstVal::Aggregate(ConstAggregate::Tuple(consts)) => consts[i], - ConstVal::Value(miri) => self.tcx.const_val_field( - self.param_env.and((instance, field, miri, cv.ty)), - ).unwrap(), - _ => bug!("{:#?} is not a valid tuple", cv), - }; - FieldPattern { - field, - pattern: self.const_to_pat(instance, val, span), - } - }).collect() - } - } - ty::TyArray(_, n) => { - PatternKind::Leaf { - subpatterns: (0..n.val.unwrap_u64()).map(|i| { - let i = i as usize; - let field = Field::new(i); - let val = match cv.val { - ConstVal::Aggregate(ConstAggregate::Array(consts)) => consts[i], - ConstVal::Aggregate(ConstAggregate::Repeat(cv, _)) => cv, - ConstVal::Value(miri) => self.tcx.const_val_field( - self.param_env.and((instance, field, miri, cv.ty)), - ).unwrap(), - _ => bug!("{:#?} is not a valid tuple", cv), - }; - FieldPattern { - field, - pattern: self.const_to_pat(instance, val, span), - } - }).collect() - } - } - _ => { - PatternKind::Constant { - value: cv, - } - }, - }; - - Pattern { - span, - ty: cv.ty, - kind: Box::new(kind), - } - } -} - -pub trait PatternFoldable<'tcx> : Sized { - fn fold_with>(&self, folder: &mut F) -> Self { - self.super_fold_with(folder) - } - - fn super_fold_with>(&self, folder: &mut F) -> Self; -} - -pub trait PatternFolder<'tcx> : Sized { - fn fold_pattern(&mut self, pattern: &Pattern<'tcx>) -> Pattern<'tcx> { - pattern.super_fold_with(self) - } - - fn fold_pattern_kind(&mut self, kind: &PatternKind<'tcx>) -> PatternKind<'tcx> { - kind.super_fold_with(self) - } -} - - -impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Box { - fn super_fold_with>(&self, folder: &mut F) -> Self { - let content: T = (**self).fold_with(folder); - box content - } -} - -impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Vec { - fn super_fold_with>(&self, folder: &mut F) -> Self { - self.iter().map(|t| t.fold_with(folder)).collect() - } -} - -impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Option { - fn super_fold_with>(&self, folder: &mut F) -> Self{ - self.as_ref().map(|t| t.fold_with(folder)) - } -} - -macro_rules! CloneImpls { - (<$lt_tcx:tt> $($ty:ty),+) => { - $( - impl<$lt_tcx> PatternFoldable<$lt_tcx> for $ty { - fn super_fold_with>(&self, _: &mut F) -> Self { - Clone::clone(self) - } - } - )+ - } -} - -CloneImpls!{ <'tcx> - Span, Field, Mutability, ast::Name, ast::NodeId, usize, &'tcx ty::Const<'tcx>, - Region<'tcx>, Ty<'tcx>, BindingMode<'tcx>, &'tcx AdtDef, - &'tcx Substs<'tcx>, &'tcx Kind<'tcx> -} - -impl<'tcx> PatternFoldable<'tcx> for FieldPattern<'tcx> { - fn super_fold_with>(&self, folder: &mut F) -> Self { - FieldPattern { - field: self.field.fold_with(folder), - pattern: self.pattern.fold_with(folder) - } - } -} - -impl<'tcx> PatternFoldable<'tcx> for Pattern<'tcx> { - fn fold_with>(&self, folder: &mut F) -> Self { - folder.fold_pattern(self) - } - - fn super_fold_with>(&self, folder: &mut F) -> Self { - Pattern { - ty: self.ty.fold_with(folder), - span: self.span.fold_with(folder), - kind: self.kind.fold_with(folder) - } - } -} - -impl<'tcx> PatternFoldable<'tcx> for PatternKind<'tcx> { - fn fold_with>(&self, folder: &mut F) -> Self { - folder.fold_pattern_kind(self) - } - - fn super_fold_with>(&self, folder: &mut F) -> Self { - match *self { - PatternKind::Wild => PatternKind::Wild, - PatternKind::Binding { - mutability, - name, - mode, - var, - ty, - ref subpattern, - } => PatternKind::Binding { - mutability: mutability.fold_with(folder), - name: name.fold_with(folder), - mode: mode.fold_with(folder), - var: var.fold_with(folder), - ty: ty.fold_with(folder), - subpattern: subpattern.fold_with(folder), - }, - PatternKind::Variant { - adt_def, - substs, - variant_index, - ref subpatterns, - } => PatternKind::Variant { - adt_def: adt_def.fold_with(folder), - substs: substs.fold_with(folder), - variant_index: variant_index.fold_with(folder), - subpatterns: subpatterns.fold_with(folder) - }, - PatternKind::Leaf { - ref subpatterns, - } => PatternKind::Leaf { - subpatterns: subpatterns.fold_with(folder), - }, - PatternKind::Deref { - ref subpattern, - } => PatternKind::Deref { - subpattern: subpattern.fold_with(folder), - }, - PatternKind::Constant { - value - } => PatternKind::Constant { - value: value.fold_with(folder) - }, - PatternKind::Range { - lo, - hi, - end, - } => PatternKind::Range { - lo: lo.fold_with(folder), - hi: hi.fold_with(folder), - end, - }, - PatternKind::Slice { - ref prefix, - ref slice, - ref suffix, - } => PatternKind::Slice { - prefix: prefix.fold_with(folder), - slice: slice.fold_with(folder), - suffix: suffix.fold_with(folder) - }, - PatternKind::Array { - ref prefix, - ref slice, - ref suffix - } => PatternKind::Array { - prefix: prefix.fold_with(folder), - slice: slice.fold_with(folder), - suffix: suffix.fold_with(folder) - }, - } - } -} diff --git a/src/librustc_driver/Cargo.toml b/src/librustc_driver/Cargo.toml index 802fe61d6f3..6a1d9e56534 100644 --- a/src/librustc_driver/Cargo.toml +++ b/src/librustc_driver/Cargo.toml @@ -17,7 +17,6 @@ rustc = { path = "../librustc" } rustc_allocator = { path = "../librustc_allocator" } rustc_back = { path = "../librustc_back" } rustc_borrowck = { path = "../librustc_borrowck" } -rustc_const_eval = { path = "../librustc_const_eval" } rustc_data_structures = { path = "../librustc_data_structures" } rustc_errors = { path = "../librustc_errors" } rustc_incremental = { path = "../librustc_incremental" } diff --git a/src/librustc_driver/driver.rs b/src/librustc_driver/driver.rs index 571cc46bc64..54457eacbf2 100644 --- a/src/librustc_driver/driver.rs +++ b/src/librustc_driver/driver.rs @@ -37,7 +37,7 @@ use rustc_privacy; use rustc_plugin::registry::Registry; use rustc_plugin as plugin; use rustc_passes::{self, ast_validation, loops, consts, hir_stats}; -use rustc_const_eval::{self, check_match}; +use rustc_mir::const_eval::check_match; use super::Compilation; use serialize::json; @@ -942,7 +942,6 @@ pub fn default_provide(providers: &mut ty::maps::Providers) { ty::provide(providers); traits::provide(providers); reachable::provide(providers); - rustc_const_eval::provide(providers); rustc_passes::provide(providers); middle::region::provide(providers); cstore::provide(providers); diff --git a/src/librustc_driver/lib.rs b/src/librustc_driver/lib.rs index 4b496fe3db6..4953b85f994 100644 --- a/src/librustc_driver/lib.rs +++ b/src/librustc_driver/lib.rs @@ -35,7 +35,6 @@ extern crate rustc; extern crate rustc_allocator; extern crate rustc_back; extern crate rustc_borrowck; -extern crate rustc_const_eval; extern crate rustc_data_structures; extern crate rustc_errors as errors; extern crate rustc_passes; @@ -1566,7 +1565,6 @@ pub fn diagnostics_registry() -> errors::registry::Registry { // FIXME: need to figure out a way to get these back in here // all_errors.extend_from_slice(get_trans(sess).diagnostics()); all_errors.extend_from_slice(&rustc_trans_utils::DIAGNOSTICS); - all_errors.extend_from_slice(&rustc_const_eval::DIAGNOSTICS); all_errors.extend_from_slice(&rustc_metadata::DIAGNOSTICS); all_errors.extend_from_slice(&rustc_passes::DIAGNOSTICS); all_errors.extend_from_slice(&rustc_plugin::DIAGNOSTICS); diff --git a/src/librustc_lint/Cargo.toml b/src/librustc_lint/Cargo.toml index 9fee2d54e47..5ff891202db 100644 --- a/src/librustc_lint/Cargo.toml +++ b/src/librustc_lint/Cargo.toml @@ -12,6 +12,6 @@ test = false [dependencies] log = "0.4" rustc = { path = "../librustc" } -rustc_const_eval = { path = "../librustc_const_eval" } +rustc_mir = { path = "../librustc_mir"} syntax = { path = "../libsyntax" } syntax_pos = { path = "../libsyntax_pos" } diff --git a/src/librustc_lint/lib.rs b/src/librustc_lint/lib.rs index 9dc6d977851..79f3ff9f19f 100644 --- a/src/librustc_lint/lib.rs +++ b/src/librustc_lint/lib.rs @@ -39,7 +39,7 @@ extern crate syntax; extern crate rustc; #[macro_use] extern crate log; -extern crate rustc_const_eval; +extern crate rustc_mir; extern crate syntax_pos; use rustc::lint; diff --git a/src/librustc_lint/types.rs b/src/librustc_lint/types.rs index f400ce42a90..926aa2a7241 100644 --- a/src/librustc_lint/types.rs +++ b/src/librustc_lint/types.rs @@ -15,7 +15,7 @@ use rustc::ty::subst::Substs; use rustc::ty::{self, AdtKind, Ty, TyCtxt}; use rustc::ty::layout::{self, LayoutOf}; use middle::const_val::ConstVal; -use rustc_const_eval::ConstContext; +use rustc_mir::const_eval::ConstContext; use rustc::mir::interpret::{Value, PrimVal}; use util::nodemap::FxHashSet; use lint::{LateContext, LintContext, LintArray}; diff --git a/src/librustc_mir/Cargo.toml b/src/librustc_mir/Cargo.toml index ea05a513f7e..90a0f18aba3 100644 --- a/src/librustc_mir/Cargo.toml +++ b/src/librustc_mir/Cargo.toml @@ -9,13 +9,13 @@ path = "lib.rs" crate-type = ["dylib"] [dependencies] +arena = { path = "../libarena" } bitflags = "1.0" graphviz = { path = "../libgraphviz" } log = "0.4" log_settings = "0.1.1" rustc = { path = "../librustc" } rustc_back = { path = "../librustc_back" } -rustc_const_eval = { path = "../librustc_const_eval" } rustc_const_math = { path = "../librustc_const_math" } rustc_data_structures = { path = "../librustc_data_structures" } rustc_errors = { path = "../librustc_errors" } diff --git a/src/librustc_mir/build/mod.rs b/src/librustc_mir/build/mod.rs index a325cfe3eaa..0f4d1e5bb0e 100644 --- a/src/librustc_mir/build/mod.rs +++ b/src/librustc_mir/build/mod.rs @@ -21,7 +21,7 @@ use rustc::ty::{self, Ty, TyCtxt}; use rustc::ty::subst::Substs; use rustc::util::nodemap::NodeMap; use rustc_back::PanicStrategy; -use rustc_const_eval::pattern::{BindingMode, PatternKind}; +use const_eval::pattern::{BindingMode, PatternKind}; use rustc_data_structures::indexed_vec::{IndexVec, Idx}; use shim; use std::mem; diff --git a/src/librustc_mir/const_eval/_match.rs b/src/librustc_mir/const_eval/_match.rs new file mode 100644 index 00000000000..9ebbc111628 --- /dev/null +++ b/src/librustc_mir/const_eval/_match.rs @@ -0,0 +1,1217 @@ +// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use self::Constructor::*; +use self::Usefulness::*; +use self::WitnessPreference::*; + +use rustc::middle::const_val::ConstVal; +use const_eval::eval::{compare_const_vals}; + +use rustc_const_math::ConstInt; + +use rustc_data_structures::fx::FxHashMap; +use rustc_data_structures::indexed_vec::Idx; + +use const_eval::pattern::{FieldPattern, Pattern, PatternKind}; +use const_eval::pattern::{PatternFoldable, PatternFolder}; + +use rustc::hir::def_id::DefId; +use rustc::hir::RangeEnd; +use rustc::ty::{self, Ty, TyCtxt, TypeFoldable}; + +use rustc::mir::Field; +use rustc::mir::interpret::{Value, PrimVal}; +use rustc::util::common::ErrorReported; + +use syntax_pos::{Span, DUMMY_SP}; + +use arena::TypedArena; + +use std::cmp::{self, Ordering}; +use std::fmt; +use std::iter::{FromIterator, IntoIterator, repeat}; + +pub fn expand_pattern<'a, 'tcx>(cx: &MatchCheckCtxt<'a, 'tcx>, pat: Pattern<'tcx>) + -> &'a Pattern<'tcx> +{ + cx.pattern_arena.alloc(LiteralExpander.fold_pattern(&pat)) +} + +struct LiteralExpander; +impl<'tcx> PatternFolder<'tcx> for LiteralExpander { + fn fold_pattern(&mut self, pat: &Pattern<'tcx>) -> Pattern<'tcx> { + match (&pat.ty.sty, &*pat.kind) { + (&ty::TyRef(_, mt), &PatternKind::Constant { ref value }) => { + Pattern { + ty: pat.ty, + span: pat.span, + kind: box PatternKind::Deref { + subpattern: Pattern { + ty: mt.ty, + span: pat.span, + kind: box PatternKind::Constant { value: value.clone() }, + } + } + } + } + (_, &PatternKind::Binding { subpattern: Some(ref s), .. }) => { + s.fold_with(self) + } + _ => pat.super_fold_with(self) + } + } +} + +impl<'tcx> Pattern<'tcx> { + fn is_wildcard(&self) -> bool { + match *self.kind { + PatternKind::Binding { subpattern: None, .. } | PatternKind::Wild => + true, + _ => false + } + } +} + +pub struct Matrix<'a, 'tcx: 'a>(Vec>>); + +impl<'a, 'tcx> Matrix<'a, 'tcx> { + pub fn empty() -> Self { + Matrix(vec![]) + } + + pub fn push(&mut self, row: Vec<&'a Pattern<'tcx>>) { + self.0.push(row) + } +} + +/// Pretty-printer for matrices of patterns, example: +/// ++++++++++++++++++++++++++ +/// + _ + [] + +/// ++++++++++++++++++++++++++ +/// + true + [First] + +/// ++++++++++++++++++++++++++ +/// + true + [Second(true)] + +/// ++++++++++++++++++++++++++ +/// + false + [_] + +/// ++++++++++++++++++++++++++ +/// + _ + [_, _, ..tail] + +/// ++++++++++++++++++++++++++ +impl<'a, 'tcx> fmt::Debug for Matrix<'a, 'tcx> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "\n")?; + + let &Matrix(ref m) = self; + let pretty_printed_matrix: Vec> = m.iter().map(|row| { + row.iter().map(|pat| format!("{:?}", pat)).collect() + }).collect(); + + let column_count = m.iter().map(|row| row.len()).max().unwrap_or(0); + assert!(m.iter().all(|row| row.len() == column_count)); + let column_widths: Vec = (0..column_count).map(|col| { + pretty_printed_matrix.iter().map(|row| row[col].len()).max().unwrap_or(0) + }).collect(); + + let total_width = column_widths.iter().cloned().sum::() + column_count * 3 + 1; + let br = repeat('+').take(total_width).collect::(); + write!(f, "{}\n", br)?; + for row in pretty_printed_matrix { + write!(f, "+")?; + for (column, pat_str) in row.into_iter().enumerate() { + write!(f, " ")?; + write!(f, "{:1$}", pat_str, column_widths[column])?; + write!(f, " +")?; + } + write!(f, "\n")?; + write!(f, "{}\n", br)?; + } + Ok(()) + } +} + +impl<'a, 'tcx> FromIterator>> for Matrix<'a, 'tcx> { + fn from_iter>>>(iter: T) -> Self + { + Matrix(iter.into_iter().collect()) + } +} + +//NOTE: appears to be the only place other then InferCtxt to contain a ParamEnv +pub struct MatchCheckCtxt<'a, 'tcx: 'a> { + pub tcx: TyCtxt<'a, 'tcx, 'tcx>, + /// The module in which the match occurs. This is necessary for + /// checking inhabited-ness of types because whether a type is (visibly) + /// inhabited can depend on whether it was defined in the current module or + /// not. eg. `struct Foo { _private: ! }` cannot be seen to be empty + /// outside it's module and should not be matchable with an empty match + /// statement. + pub module: DefId, + pub pattern_arena: &'a TypedArena>, + pub byte_array_map: FxHashMap<*const Pattern<'tcx>, Vec<&'a Pattern<'tcx>>>, +} + +impl<'a, 'tcx> MatchCheckCtxt<'a, 'tcx> { + pub fn create_and_enter( + tcx: TyCtxt<'a, 'tcx, 'tcx>, + module: DefId, + f: F) -> R + where F: for<'b> FnOnce(MatchCheckCtxt<'b, 'tcx>) -> R + { + let pattern_arena = TypedArena::new(); + + f(MatchCheckCtxt { + tcx, + module, + pattern_arena: &pattern_arena, + byte_array_map: FxHashMap(), + }) + } + + // convert a byte-string pattern to a list of u8 patterns. + fn lower_byte_str_pattern<'p>(&mut self, pat: &'p Pattern<'tcx>) -> Vec<&'p Pattern<'tcx>> + where 'a: 'p + { + let pattern_arena = &*self.pattern_arena; + let tcx = self.tcx; + self.byte_array_map.entry(pat).or_insert_with(|| { + match pat.kind { + box PatternKind::Constant { + value: &ty::Const { val: ConstVal::ByteStr(b), .. } + } => { + b.data.iter().map(|&b| &*pattern_arena.alloc(Pattern { + ty: tcx.types.u8, + span: pat.span, + kind: box PatternKind::Constant { + value: tcx.mk_const(ty::Const { + val: ConstVal::Integral(ConstInt::U8(b)), + ty: tcx.types.u8 + }) + } + })).collect() + } + box PatternKind::Constant { + value: &ty::Const { val: ConstVal::Value(b), ty } + } => { + match b { + Value::ByVal(PrimVal::Ptr(ptr)) => { + let is_array_ptr = ty + .builtin_deref(true, ty::NoPreference) + .and_then(|t| t.ty.builtin_index()) + .map_or(false, |t| t == tcx.types.u8); + assert!(is_array_ptr); + let alloc = tcx + .interpret_interner + .borrow() + .get_alloc(ptr.alloc_id.0) + .unwrap(); + assert_eq!(ptr.offset, 0); + // FIXME: check length + alloc.bytes.iter().map(|b| { + &*pattern_arena.alloc(Pattern { + ty: tcx.types.u8, + span: pat.span, + kind: box PatternKind::Constant { + value: tcx.mk_const(ty::Const { + val: ConstVal::Value(Value::ByVal( + PrimVal::Bytes(*b as u128), + )), + ty: tcx.types.u8 + }) + } + }) + }).collect() + }, + _ => bug!("not a byte str: {:?}", b), + } + } + _ => span_bug!(pat.span, "unexpected byte array pattern {:?}", pat) + } + }).clone() + } + + fn is_uninhabited(&self, ty: Ty<'tcx>) -> bool { + if self.tcx.features().never_type { + self.tcx.is_ty_uninhabited_from(self.module, ty) + } else { + false + } + } + + fn is_non_exhaustive_enum(&self, ty: Ty<'tcx>) -> bool { + match ty.sty { + ty::TyAdt(adt_def, ..) => adt_def.is_enum() && adt_def.is_non_exhaustive(), + _ => false, + } + } + + fn is_local(&self, ty: Ty<'tcx>) -> bool { + match ty.sty { + ty::TyAdt(adt_def, ..) => adt_def.did.is_local(), + _ => false, + } + } + + fn is_variant_uninhabited(&self, + variant: &'tcx ty::VariantDef, + substs: &'tcx ty::subst::Substs<'tcx>) + -> bool + { + if self.tcx.features().never_type { + self.tcx.is_enum_variant_uninhabited_from(self.module, variant, substs) + } else { + false + } + } +} + +#[derive(Clone, Debug, PartialEq)] +pub enum Constructor<'tcx> { + /// The constructor of all patterns that don't vary by constructor, + /// e.g. struct patterns and fixed-length arrays. + Single, + /// Enum variants. + Variant(DefId), + /// Literal values. + ConstantValue(&'tcx ty::Const<'tcx>), + /// Ranges of literal values (`2...5` and `2..5`). + ConstantRange(&'tcx ty::Const<'tcx>, &'tcx ty::Const<'tcx>, RangeEnd), + /// Array patterns of length n. + Slice(u64), +} + +impl<'tcx> Constructor<'tcx> { + fn variant_index_for_adt(&self, adt: &'tcx ty::AdtDef) -> usize { + match self { + &Variant(vid) => adt.variant_index_with_id(vid), + &Single => { + assert!(!adt.is_enum()); + 0 + } + _ => bug!("bad constructor {:?} for adt {:?}", self, adt) + } + } +} + +#[derive(Clone)] +pub enum Usefulness<'tcx> { + Useful, + UsefulWithWitness(Vec>), + NotUseful +} + +impl<'tcx> Usefulness<'tcx> { + fn is_useful(&self) -> bool { + match *self { + NotUseful => false, + _ => true + } + } +} + +#[derive(Copy, Clone)] +pub enum WitnessPreference { + ConstructWitness, + LeaveOutWitness +} + +#[derive(Copy, Clone, Debug)] +struct PatternContext<'tcx> { + ty: Ty<'tcx>, + max_slice_length: u64, +} + +/// A stack of patterns in reverse order of construction +#[derive(Clone)] +pub struct Witness<'tcx>(Vec>); + +impl<'tcx> Witness<'tcx> { + pub fn single_pattern(&self) -> &Pattern<'tcx> { + assert_eq!(self.0.len(), 1); + &self.0[0] + } + + fn push_wild_constructor<'a>( + mut self, + cx: &MatchCheckCtxt<'a, 'tcx>, + ctor: &Constructor<'tcx>, + ty: Ty<'tcx>) + -> Self + { + let sub_pattern_tys = constructor_sub_pattern_tys(cx, ctor, ty); + self.0.extend(sub_pattern_tys.into_iter().map(|ty| { + Pattern { + ty, + span: DUMMY_SP, + kind: box PatternKind::Wild, + } + })); + self.apply_constructor(cx, ctor, ty) + } + + + /// Constructs a partial witness for a pattern given a list of + /// patterns expanded by the specialization step. + /// + /// When a pattern P is discovered to be useful, this function is used bottom-up + /// to reconstruct a complete witness, e.g. a pattern P' that covers a subset + /// of values, V, where each value in that set is not covered by any previously + /// used patterns and is covered by the pattern P'. Examples: + /// + /// left_ty: tuple of 3 elements + /// pats: [10, 20, _] => (10, 20, _) + /// + /// left_ty: struct X { a: (bool, &'static str), b: usize} + /// pats: [(false, "foo"), 42] => X { a: (false, "foo"), b: 42 } + fn apply_constructor<'a>( + mut self, + cx: &MatchCheckCtxt<'a,'tcx>, + ctor: &Constructor<'tcx>, + ty: Ty<'tcx>) + -> Self + { + let arity = constructor_arity(cx, ctor, ty); + let pat = { + let len = self.0.len() as u64; + let mut pats = self.0.drain((len-arity) as usize..).rev(); + + match ty.sty { + ty::TyAdt(..) | + ty::TyTuple(..) => { + let pats = pats.enumerate().map(|(i, p)| { + FieldPattern { + field: Field::new(i), + pattern: p + } + }).collect(); + + if let ty::TyAdt(adt, substs) = ty.sty { + if adt.is_enum() { + PatternKind::Variant { + adt_def: adt, + substs, + variant_index: ctor.variant_index_for_adt(adt), + subpatterns: pats + } + } else { + PatternKind::Leaf { subpatterns: pats } + } + } else { + PatternKind::Leaf { subpatterns: pats } + } + } + + ty::TyRef(..) => { + PatternKind::Deref { subpattern: pats.nth(0).unwrap() } + } + + ty::TySlice(_) | ty::TyArray(..) => { + PatternKind::Slice { + prefix: pats.collect(), + slice: None, + suffix: vec![] + } + } + + _ => { + match *ctor { + ConstantValue(value) => PatternKind::Constant { value }, + _ => PatternKind::Wild, + } + } + } + }; + + self.0.push(Pattern { + ty, + span: DUMMY_SP, + kind: Box::new(pat), + }); + + self + } +} + +/// This determines the set of all possible constructors of a pattern matching +/// values of type `left_ty`. For vectors, this would normally be an infinite set +/// but is instead bounded by the maximum fixed length of slice patterns in +/// the column of patterns being analyzed. +/// +/// This intentionally does not list ConstantValue specializations for +/// non-booleans, because we currently assume that there is always a +/// "non-standard constant" that matches. See issue #12483. +/// +/// We make sure to omit constructors that are statically impossible. eg for +/// Option we do not include Some(_) in the returned list of constructors. +fn all_constructors<'a, 'tcx: 'a>(cx: &mut MatchCheckCtxt<'a, 'tcx>, + pcx: PatternContext<'tcx>) + -> Vec> +{ + debug!("all_constructors({:?})", pcx.ty); + match pcx.ty.sty { + ty::TyBool => { + [true, false].iter().map(|&b| { + ConstantValue(cx.tcx.mk_const(ty::Const { + val: if cx.tcx.sess.opts.debugging_opts.miri { + ConstVal::Value(Value::ByVal(PrimVal::Bytes(b as u128))) + } else { + ConstVal::Bool(b) + }, + ty: cx.tcx.types.bool + })) + }).collect() + } + ty::TyArray(ref sub_ty, len) if len.val.to_u128().is_some() => { + let len = len.val.unwrap_u64(); + if len != 0 && cx.is_uninhabited(sub_ty) { + vec![] + } else { + vec![Slice(len)] + } + } + // Treat arrays of a constant but unknown length like slices. + ty::TyArray(ref sub_ty, _) | + ty::TySlice(ref sub_ty) => { + if cx.is_uninhabited(sub_ty) { + vec![Slice(0)] + } else { + (0..pcx.max_slice_length+1).map(|length| Slice(length)).collect() + } + } + ty::TyAdt(def, substs) if def.is_enum() => { + def.variants.iter() + .filter(|v| !cx.is_variant_uninhabited(v, substs)) + .map(|v| Variant(v.did)) + .collect() + } + _ => { + if cx.is_uninhabited(pcx.ty) { + vec![] + } else { + vec![Single] + } + } + } +} + +fn max_slice_length<'p, 'a: 'p, 'tcx: 'a, I>( + cx: &mut MatchCheckCtxt<'a, 'tcx>, + patterns: I) -> u64 + where I: Iterator> +{ + // The exhaustiveness-checking paper does not include any details on + // checking variable-length slice patterns. However, they are matched + // by an infinite collection of fixed-length array patterns. + // + // Checking the infinite set directly would take an infinite amount + // of time. However, it turns out that for each finite set of + // patterns `P`, all sufficiently large array lengths are equivalent: + // + // Each slice `s` with a "sufficiently-large" length `l ≥ L` that applies + // to exactly the subset `Pₜ` of `P` can be transformed to a slice + // `sₘ` for each sufficiently-large length `m` that applies to exactly + // the same subset of `P`. + // + // Because of that, each witness for reachability-checking from one + // of the sufficiently-large lengths can be transformed to an + // equally-valid witness from any other length, so we only have + // to check slice lengths from the "minimal sufficiently-large length" + // and below. + // + // Note that the fact that there is a *single* `sₘ` for each `m` + // not depending on the specific pattern in `P` is important: if + // you look at the pair of patterns + // `[true, ..]` + // `[.., false]` + // Then any slice of length ≥1 that matches one of these two + // patterns can be be trivially turned to a slice of any + // other length ≥1 that matches them and vice-versa - for + // but the slice from length 2 `[false, true]` that matches neither + // of these patterns can't be turned to a slice from length 1 that + // matches neither of these patterns, so we have to consider + // slices from length 2 there. + // + // Now, to see that that length exists and find it, observe that slice + // patterns are either "fixed-length" patterns (`[_, _, _]`) or + // "variable-length" patterns (`[_, .., _]`). + // + // For fixed-length patterns, all slices with lengths *longer* than + // the pattern's length have the same outcome (of not matching), so + // as long as `L` is greater than the pattern's length we can pick + // any `sₘ` from that length and get the same result. + // + // For variable-length patterns, the situation is more complicated, + // because as seen above the precise value of `sₘ` matters. + // + // However, for each variable-length pattern `p` with a prefix of length + // `plₚ` and suffix of length `slₚ`, only the first `plₚ` and the last + // `slₚ` elements are examined. + // + // Therefore, as long as `L` is positive (to avoid concerns about empty + // types), all elements after the maximum prefix length and before + // the maximum suffix length are not examined by any variable-length + // pattern, and therefore can be added/removed without affecting + // them - creating equivalent patterns from any sufficiently-large + // length. + // + // Of course, if fixed-length patterns exist, we must be sure + // that our length is large enough to miss them all, so + // we can pick `L = max(FIXED_LEN+1 ∪ {max(PREFIX_LEN) + max(SUFFIX_LEN)})` + // + // for example, with the above pair of patterns, all elements + // but the first and last can be added/removed, so any + // witness of length ≥2 (say, `[false, false, true]`) can be + // turned to a witness from any other length ≥2. + + let mut max_prefix_len = 0; + let mut max_suffix_len = 0; + let mut max_fixed_len = 0; + + for row in patterns { + match *row.kind { + PatternKind::Constant { value: &ty::Const { val: ConstVal::ByteStr(b), .. } } => { + max_fixed_len = cmp::max(max_fixed_len, b.data.len() as u64); + } + PatternKind::Constant { + value: &ty::Const { + val: ConstVal::Value(Value::ByVal(PrimVal::Ptr(ptr))), + ty, + } + } => { + let is_array_ptr = ty + .builtin_deref(true, ty::NoPreference) + .and_then(|t| t.ty.builtin_index()) + .map_or(false, |t| t == cx.tcx.types.u8); + if is_array_ptr { + let alloc = cx.tcx + .interpret_interner + .borrow() + .get_alloc(ptr.alloc_id.0) + .unwrap(); + max_fixed_len = cmp::max(max_fixed_len, alloc.bytes.len() as u64); + } + } + PatternKind::Slice { ref prefix, slice: None, ref suffix } => { + let fixed_len = prefix.len() as u64 + suffix.len() as u64; + max_fixed_len = cmp::max(max_fixed_len, fixed_len); + } + PatternKind::Slice { ref prefix, slice: Some(_), ref suffix } => { + max_prefix_len = cmp::max(max_prefix_len, prefix.len() as u64); + max_suffix_len = cmp::max(max_suffix_len, suffix.len() as u64); + } + _ => {} + } + } + + cmp::max(max_fixed_len + 1, max_prefix_len + max_suffix_len) +} + +/// Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html +/// The algorithm from the paper has been modified to correctly handle empty +/// types. The changes are: +/// (0) We don't exit early if the pattern matrix has zero rows. We just +/// continue to recurse over columns. +/// (1) all_constructors will only return constructors that are statically +/// possible. eg. it will only return Ok for Result +/// +/// This finds whether a (row) vector `v` of patterns is 'useful' in relation +/// to a set of such vectors `m` - this is defined as there being a set of +/// inputs that will match `v` but not any of the sets in `m`. +/// +/// All the patterns at each column of the `matrix ++ v` matrix must +/// have the same type, except that wildcard (PatternKind::Wild) patterns +/// with type TyErr are also allowed, even if the "type of the column" +/// is not TyErr. That is used to represent private fields, as using their +/// real type would assert that they are inhabited. +/// +/// This is used both for reachability checking (if a pattern isn't useful in +/// relation to preceding patterns, it is not reachable) and exhaustiveness +/// checking (if a wildcard pattern is useful in relation to a matrix, the +/// matrix isn't exhaustive). +pub fn is_useful<'p, 'a: 'p, 'tcx: 'a>(cx: &mut MatchCheckCtxt<'a, 'tcx>, + matrix: &Matrix<'p, 'tcx>, + v: &[&'p Pattern<'tcx>], + witness: WitnessPreference) + -> Usefulness<'tcx> { + let &Matrix(ref rows) = matrix; + debug!("is_useful({:#?}, {:#?})", matrix, v); + + // The base case. We are pattern-matching on () and the return value is + // based on whether our matrix has a row or not. + // NOTE: This could potentially be optimized by checking rows.is_empty() + // first and then, if v is non-empty, the return value is based on whether + // the type of the tuple we're checking is inhabited or not. + if v.is_empty() { + return if rows.is_empty() { + match witness { + ConstructWitness => UsefulWithWitness(vec![Witness(vec![])]), + LeaveOutWitness => Useful, + } + } else { + NotUseful + } + }; + + assert!(rows.iter().all(|r| r.len() == v.len())); + + let pcx = PatternContext { + // TyErr is used to represent the type of wildcard patterns matching + // against inaccessible (private) fields of structs, so that we won't + // be able to observe whether the types of the struct's fields are + // inhabited. + // + // If the field is truly inaccessible, then all the patterns + // matching against it must be wildcard patterns, so its type + // does not matter. + // + // However, if we are matching against non-wildcard patterns, we + // need to know the real type of the field so we can specialize + // against it. This primarily occurs through constants - they + // can include contents for fields that are inaccessible at the + // location of the match. In that case, the field's type is + // inhabited - by the constant - so we can just use it. + // + // FIXME: this might lead to "unstable" behavior with macro hygiene + // introducing uninhabited patterns for inaccessible fields. We + // need to figure out how to model that. + ty: rows.iter().map(|r| r[0].ty).find(|ty| !ty.references_error()) + .unwrap_or(v[0].ty), + max_slice_length: max_slice_length(cx, rows.iter().map(|r| r[0]).chain(Some(v[0]))) + }; + + debug!("is_useful_expand_first_col: pcx={:#?}, expanding {:#?}", pcx, v[0]); + + if let Some(constructors) = pat_constructors(cx, v[0], pcx) { + debug!("is_useful - expanding constructors: {:#?}", constructors); + constructors.into_iter().map(|c| + is_useful_specialized(cx, matrix, v, c.clone(), pcx.ty, witness) + ).find(|result| result.is_useful()).unwrap_or(NotUseful) + } else { + debug!("is_useful - expanding wildcard"); + + let used_ctors: Vec = rows.iter().flat_map(|row| { + pat_constructors(cx, row[0], pcx).unwrap_or(vec![]) + }).collect(); + debug!("used_ctors = {:#?}", used_ctors); + let all_ctors = all_constructors(cx, pcx); + debug!("all_ctors = {:#?}", all_ctors); + let missing_ctors: Vec = all_ctors.iter().filter(|c| { + !used_ctors.contains(*c) + }).cloned().collect(); + + // `missing_ctors` is the set of constructors from the same type as the + // first column of `matrix` that are matched only by wildcard patterns + // from the first column. + // + // Therefore, if there is some pattern that is unmatched by `matrix`, + // it will still be unmatched if the first constructor is replaced by + // any of the constructors in `missing_ctors` + // + // However, if our scrutinee is *privately* an empty enum, we + // must treat it as though it had an "unknown" constructor (in + // that case, all other patterns obviously can't be variants) + // to avoid exposing its emptyness. See the `match_privately_empty` + // test for details. + // + // FIXME: currently the only way I know of something can + // be a privately-empty enum is when the never_type + // feature flag is not present, so this is only + // needed for that case. + + let is_privately_empty = + all_ctors.is_empty() && !cx.is_uninhabited(pcx.ty); + let is_declared_nonexhaustive = + cx.is_non_exhaustive_enum(pcx.ty) && !cx.is_local(pcx.ty); + debug!("missing_ctors={:#?} is_privately_empty={:#?} is_declared_nonexhaustive={:#?}", + missing_ctors, is_privately_empty, is_declared_nonexhaustive); + + // For privately empty and non-exhaustive enums, we work as if there were an "extra" + // `_` constructor for the type, so we can never match over all constructors. + let is_non_exhaustive = is_privately_empty || is_declared_nonexhaustive; + + if missing_ctors.is_empty() && !is_non_exhaustive { + all_ctors.into_iter().map(|c| { + is_useful_specialized(cx, matrix, v, c.clone(), pcx.ty, witness) + }).find(|result| result.is_useful()).unwrap_or(NotUseful) + } else { + let matrix = rows.iter().filter_map(|r| { + if r[0].is_wildcard() { + Some(r[1..].to_vec()) + } else { + None + } + }).collect(); + match is_useful(cx, &matrix, &v[1..], witness) { + UsefulWithWitness(pats) => { + let cx = &*cx; + // In this case, there's at least one "free" + // constructor that is only matched against by + // wildcard patterns. + // + // There are 2 ways we can report a witness here. + // Commonly, we can report all the "free" + // constructors as witnesses, e.g. if we have: + // + // ``` + // enum Direction { N, S, E, W } + // let Direction::N = ...; + // ``` + // + // we can report 3 witnesses: `S`, `E`, and `W`. + // + // However, there are 2 cases where we don't want + // to do this and instead report a single `_` witness: + // + // 1) If the user is matching against a non-exhaustive + // enum, there is no point in enumerating all possible + // variants, because the user can't actually match + // against them himself, e.g. in an example like: + // ``` + // let err: io::ErrorKind = ...; + // match err { + // io::ErrorKind::NotFound => {}, + // } + // ``` + // we don't want to show every possible IO error, + // but instead have `_` as the witness (this is + // actually *required* if the user specified *all* + // IO errors, but is probably what we want in every + // case). + // + // 2) If the user didn't actually specify a constructor + // in this arm, e.g. in + // ``` + // let x: (Direction, Direction, bool) = ...; + // let (_, _, false) = x; + // ``` + // we don't want to show all 16 possible witnesses + // `(, , true)` - we are + // satisfied with `(_, _, true)`. In this case, + // `used_ctors` is empty. + let new_witnesses = if is_non_exhaustive || used_ctors.is_empty() { + // All constructors are unused. Add wild patterns + // rather than each individual constructor + pats.into_iter().map(|mut witness| { + witness.0.push(Pattern { + ty: pcx.ty, + span: DUMMY_SP, + kind: box PatternKind::Wild, + }); + witness + }).collect() + } else { + pats.into_iter().flat_map(|witness| { + missing_ctors.iter().map(move |ctor| { + witness.clone().push_wild_constructor(cx, ctor, pcx.ty) + }) + }).collect() + }; + UsefulWithWitness(new_witnesses) + } + result => result + } + } + } +} + +fn is_useful_specialized<'p, 'a:'p, 'tcx: 'a>( + cx: &mut MatchCheckCtxt<'a, 'tcx>, + &Matrix(ref m): &Matrix<'p, 'tcx>, + v: &[&'p Pattern<'tcx>], + ctor: Constructor<'tcx>, + lty: Ty<'tcx>, + witness: WitnessPreference) -> Usefulness<'tcx> +{ + debug!("is_useful_specialized({:#?}, {:#?}, {:?})", v, ctor, lty); + let sub_pat_tys = constructor_sub_pattern_tys(cx, &ctor, lty); + let wild_patterns_owned: Vec<_> = sub_pat_tys.iter().map(|ty| { + Pattern { + ty, + span: DUMMY_SP, + kind: box PatternKind::Wild, + } + }).collect(); + let wild_patterns: Vec<_> = wild_patterns_owned.iter().collect(); + let matrix = Matrix(m.iter().flat_map(|r| { + specialize(cx, &r, &ctor, &wild_patterns) + }).collect()); + match specialize(cx, v, &ctor, &wild_patterns) { + Some(v) => match is_useful(cx, &matrix, &v, witness) { + UsefulWithWitness(witnesses) => UsefulWithWitness( + witnesses.into_iter() + .map(|witness| witness.apply_constructor(cx, &ctor, lty)) + .collect() + ), + result => result + }, + None => NotUseful + } +} + +/// Determines the constructors that the given pattern can be specialized to. +/// +/// In most cases, there's only one constructor that a specific pattern +/// represents, such as a specific enum variant or a specific literal value. +/// Slice patterns, however, can match slices of different lengths. For instance, +/// `[a, b, ..tail]` can match a slice of length 2, 3, 4 and so on. +/// +/// Returns None in case of a catch-all, which can't be specialized. +fn pat_constructors<'tcx>(_cx: &mut MatchCheckCtxt, + pat: &Pattern<'tcx>, + pcx: PatternContext) + -> Option>> +{ + match *pat.kind { + PatternKind::Binding { .. } | PatternKind::Wild => + None, + PatternKind::Leaf { .. } | PatternKind::Deref { .. } => + Some(vec![Single]), + PatternKind::Variant { adt_def, variant_index, .. } => + Some(vec![Variant(adt_def.variants[variant_index].did)]), + PatternKind::Constant { value } => + Some(vec![ConstantValue(value)]), + PatternKind::Range { lo, hi, end } => + Some(vec![ConstantRange(lo, hi, end)]), + PatternKind::Array { .. } => match pcx.ty.sty { + ty::TyArray(_, length) => Some(vec![ + Slice(length.val.unwrap_u64()) + ]), + _ => span_bug!(pat.span, "bad ty {:?} for array pattern", pcx.ty) + }, + PatternKind::Slice { ref prefix, ref slice, ref suffix } => { + let pat_len = prefix.len() as u64 + suffix.len() as u64; + if slice.is_some() { + Some((pat_len..pcx.max_slice_length+1).map(Slice).collect()) + } else { + Some(vec![Slice(pat_len)]) + } + } + } +} + +/// This computes the arity of a constructor. The arity of a constructor +/// is how many subpattern patterns of that constructor should be expanded to. +/// +/// For instance, a tuple pattern (_, 42, Some([])) has the arity of 3. +/// A struct pattern's arity is the number of fields it contains, etc. +fn constructor_arity(_cx: &MatchCheckCtxt, ctor: &Constructor, ty: Ty) -> u64 { + debug!("constructor_arity({:#?}, {:?})", ctor, ty); + match ty.sty { + ty::TyTuple(ref fs, _) => fs.len() as u64, + ty::TySlice(..) | ty::TyArray(..) => match *ctor { + Slice(length) => length, + ConstantValue(_) => 0, + _ => bug!("bad slice pattern {:?} {:?}", ctor, ty) + }, + ty::TyRef(..) => 1, + ty::TyAdt(adt, _) => { + adt.variants[ctor.variant_index_for_adt(adt)].fields.len() as u64 + } + _ => 0 + } +} + +/// This computes the types of the sub patterns that a constructor should be +/// expanded to. +/// +/// For instance, a tuple pattern (43u32, 'a') has sub pattern types [u32, char]. +fn constructor_sub_pattern_tys<'a, 'tcx: 'a>(cx: &MatchCheckCtxt<'a, 'tcx>, + ctor: &Constructor, + ty: Ty<'tcx>) -> Vec> +{ + debug!("constructor_sub_pattern_tys({:#?}, {:?})", ctor, ty); + match ty.sty { + ty::TyTuple(ref fs, _) => fs.into_iter().map(|t| *t).collect(), + ty::TySlice(ty) | ty::TyArray(ty, _) => match *ctor { + Slice(length) => (0..length).map(|_| ty).collect(), + ConstantValue(_) => vec![], + Single => vec![ty], + _ => bug!("bad slice pattern {:?} {:?}", ctor, ty) + }, + ty::TyRef(_, ref ty_and_mut) => vec![ty_and_mut.ty], + ty::TyAdt(adt, substs) => { + if adt.is_box() { + // Use T as the sub pattern type of Box. + vec![substs.type_at(0)] + } else { + if let ConstantValue(_) = *ctor { + return vec![]; + } + adt.variants[ctor.variant_index_for_adt(adt)].fields.iter().map(|field| { + let is_visible = adt.is_enum() + || field.vis.is_accessible_from(cx.module, cx.tcx); + if is_visible { + field.ty(cx.tcx, substs) + } else { + // Treat all non-visible fields as TyErr. They + // can't appear in any other pattern from + // this match (because they are private), + // so their type does not matter - but + // we don't want to know they are + // uninhabited. + cx.tcx.types.err + } + }).collect() + } + } + _ => vec![], + } +} + +fn slice_pat_covered_by_constructor(tcx: TyCtxt, _span: Span, + ctor: &Constructor, + prefix: &[Pattern], + slice: &Option, + suffix: &[Pattern]) + -> Result { + let data: &[u8] = match *ctor { + ConstantValue(&ty::Const { val: ConstVal::ByteStr(b), .. }) => b.data, + ConstantValue(&ty::Const { val: ConstVal::Value( + Value::ByVal(PrimVal::Ptr(ptr)) + ), ty }) => { + let is_array_ptr = ty + .builtin_deref(true, ty::NoPreference) + .and_then(|t| t.ty.builtin_index()) + .map_or(false, |t| t == tcx.types.u8); + assert!(is_array_ptr); + tcx + .interpret_interner + .borrow() + .get_alloc(ptr.alloc_id.0) + .unwrap() + .bytes + .as_ref() + } + _ => bug!() + }; + + let pat_len = prefix.len() + suffix.len(); + if data.len() < pat_len || (slice.is_none() && data.len() > pat_len) { + return Ok(false); + } + + for (ch, pat) in + data[..prefix.len()].iter().zip(prefix).chain( + data[data.len()-suffix.len()..].iter().zip(suffix)) + { + match pat.kind { + box PatternKind::Constant { value } => match value.val { + ConstVal::Integral(ConstInt::U8(u)) => { + if u != *ch { + return Ok(false); + } + }, + ConstVal::Value(Value::ByVal(PrimVal::Bytes(b))) => { + assert_eq!(b as u8 as u128, b); + if b as u8 != *ch { + return Ok(false); + } + } + _ => span_bug!(pat.span, "bad const u8 {:?}", value) + }, + _ => {} + } + } + + Ok(true) +} + +fn constructor_covered_by_range(ctor: &Constructor, + from: &ConstVal, to: &ConstVal, + end: RangeEnd, + ty: Ty) + -> Result { + trace!("constructor_covered_by_range {:#?}, {:#?}, {:#?}, {}", ctor, from, to, ty); + let cmp_from = |c_from| compare_const_vals(c_from, from, ty) + .map(|res| res != Ordering::Less); + let cmp_to = |c_to| compare_const_vals(c_to, to, ty); + macro_rules! some_or_ok { + ($e:expr) => { + match $e { + Some(to) => to, + None => return Ok(false), // not char or int + } + }; + } + match *ctor { + ConstantValue(value) => { + let to = some_or_ok!(cmp_to(&value.val)); + let end = (to == Ordering::Less) || + (end == RangeEnd::Included && to == Ordering::Equal); + Ok(some_or_ok!(cmp_from(&value.val)) && end) + }, + ConstantRange(from, to, RangeEnd::Included) => { + let to = some_or_ok!(cmp_to(&to.val)); + let end = (to == Ordering::Less) || + (end == RangeEnd::Included && to == Ordering::Equal); + Ok(some_or_ok!(cmp_from(&from.val)) && end) + }, + ConstantRange(from, to, RangeEnd::Excluded) => { + let to = some_or_ok!(cmp_to(&to.val)); + let end = (to == Ordering::Less) || + (end == RangeEnd::Excluded && to == Ordering::Equal); + Ok(some_or_ok!(cmp_from(&from.val)) && end) + } + Variant(_) | + Single => Ok(true), + _ => bug!(), + } +} + +fn patterns_for_variant<'p, 'a: 'p, 'tcx: 'a>( + subpatterns: &'p [FieldPattern<'tcx>], + wild_patterns: &[&'p Pattern<'tcx>]) + -> Vec<&'p Pattern<'tcx>> +{ + let mut result = wild_patterns.to_owned(); + + for subpat in subpatterns { + result[subpat.field.index()] = &subpat.pattern; + } + + debug!("patterns_for_variant({:#?}, {:#?}) = {:#?}", subpatterns, wild_patterns, result); + result +} + +/// This is the main specialization step. It expands the first pattern in the given row +/// into `arity` patterns based on the constructor. For most patterns, the step is trivial, +/// for instance tuple patterns are flattened and box patterns expand into their inner pattern. +/// +/// OTOH, slice patterns with a subslice pattern (..tail) can be expanded into multiple +/// different patterns. +/// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing +/// fields filled with wild patterns. +fn specialize<'p, 'a: 'p, 'tcx: 'a>( + cx: &mut MatchCheckCtxt<'a, 'tcx>, + r: &[&'p Pattern<'tcx>], + constructor: &Constructor<'tcx>, + wild_patterns: &[&'p Pattern<'tcx>]) + -> Option>> +{ + let pat = &r[0]; + + let head: Option> = match *pat.kind { + PatternKind::Binding { .. } | PatternKind::Wild => { + Some(wild_patterns.to_owned()) + }, + + PatternKind::Variant { adt_def, variant_index, ref subpatterns, .. } => { + let ref variant = adt_def.variants[variant_index]; + if *constructor == Variant(variant.did) { + Some(patterns_for_variant(subpatterns, wild_patterns)) + } else { + None + } + } + + PatternKind::Leaf { ref subpatterns } => { + Some(patterns_for_variant(subpatterns, wild_patterns)) + } + PatternKind::Deref { ref subpattern } => { + Some(vec![subpattern]) + } + + PatternKind::Constant { value } => { + match *constructor { + Slice(..) => match value.val { + ConstVal::ByteStr(b) => { + if wild_patterns.len() == b.data.len() { + Some(cx.lower_byte_str_pattern(pat)) + } else { + None + } + } + ConstVal::Value(Value::ByVal(PrimVal::Ptr(ptr))) => { + let is_array_ptr = value.ty + .builtin_deref(true, ty::NoPreference) + .and_then(|t| t.ty.builtin_index()) + .map_or(false, |t| t == cx.tcx.types.u8); + assert!(is_array_ptr); + let data_len = cx.tcx + .interpret_interner + .borrow() + .get_alloc(ptr.alloc_id.0) + .unwrap() + .bytes + .len(); + if wild_patterns.len() == data_len { + Some(cx.lower_byte_str_pattern(pat)) + } else { + None + } + } + _ => span_bug!(pat.span, + "unexpected const-val {:?} with ctor {:?}", value, constructor) + }, + _ => { + match constructor_covered_by_range( + constructor, &value.val, &value.val, RangeEnd::Included, + value.ty, + ) { + Ok(true) => Some(vec![]), + Ok(false) => None, + Err(ErrorReported) => None, + } + } + } + } + + PatternKind::Range { lo, hi, ref end } => { + match constructor_covered_by_range( + constructor, &lo.val, &hi.val, end.clone(), lo.ty, + ) { + Ok(true) => Some(vec![]), + Ok(false) => None, + Err(ErrorReported) => None, + } + } + + PatternKind::Array { ref prefix, ref slice, ref suffix } | + PatternKind::Slice { ref prefix, ref slice, ref suffix } => { + match *constructor { + Slice(..) => { + let pat_len = prefix.len() + suffix.len(); + if let Some(slice_count) = wild_patterns.len().checked_sub(pat_len) { + if slice_count == 0 || slice.is_some() { + Some( + prefix.iter().chain( + wild_patterns.iter().map(|p| *p) + .skip(prefix.len()) + .take(slice_count) + .chain( + suffix.iter() + )).collect()) + } else { + None + } + } else { + None + } + } + ConstantValue(..) => { + match slice_pat_covered_by_constructor( + cx.tcx, pat.span, constructor, prefix, slice, suffix + ) { + Ok(true) => Some(vec![]), + Ok(false) => None, + Err(ErrorReported) => None + } + } + _ => span_bug!(pat.span, + "unexpected ctor {:?} for slice pat", constructor) + } + } + }; + debug!("specialize({:#?}, {:#?}) = {:#?}", r[0], wild_patterns, head); + + head.map(|mut head| { + head.extend_from_slice(&r[1 ..]); + head + }) +} diff --git a/src/librustc_mir/const_eval/check_match.rs b/src/librustc_mir/const_eval/check_match.rs new file mode 100644 index 00000000000..3621d80df1d --- /dev/null +++ b/src/librustc_mir/const_eval/check_match.rs @@ -0,0 +1,636 @@ +// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use const_eval::_match::{MatchCheckCtxt, Matrix, expand_pattern, is_useful}; +use const_eval::_match::Usefulness::*; +use const_eval::_match::WitnessPreference::*; + +use const_eval::pattern::{Pattern, PatternContext, PatternError, PatternKind}; + +use rustc::middle::expr_use_visitor::{ConsumeMode, Delegate, ExprUseVisitor}; +use rustc::middle::expr_use_visitor::{LoanCause, MutateMode}; +use rustc::middle::expr_use_visitor as euv; +use rustc::middle::mem_categorization::{cmt}; +use rustc::middle::region; +use rustc::session::Session; +use rustc::ty::{self, Ty, TyCtxt}; +use rustc::ty::subst::Substs; +use rustc::lint; +use rustc_errors::DiagnosticBuilder; +use rustc::util::common::ErrorReported; + +use rustc::hir::def::*; +use rustc::hir::def_id::DefId; +use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap}; +use rustc::hir::{self, Pat, PatKind}; + +use std::slice; + +use syntax::ast; +use syntax::ptr::P; +use syntax_pos::{Span, DUMMY_SP}; + +struct OuterVisitor<'a, 'tcx: 'a> { tcx: TyCtxt<'a, 'tcx, 'tcx> } + +impl<'a, 'tcx> Visitor<'tcx> for OuterVisitor<'a, 'tcx> { + fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { + NestedVisitorMap::OnlyBodies(&self.tcx.hir) + } + + fn visit_body(&mut self, body: &'tcx hir::Body) { + intravisit::walk_body(self, body); + let def_id = self.tcx.hir.body_owner_def_id(body.id()); + let _ = self.tcx.check_match(def_id); + } +} + +pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) { + tcx.hir.krate().visit_all_item_likes(&mut OuterVisitor { tcx: tcx }.as_deep_visitor()); + tcx.sess.abort_if_errors(); +} + +pub(crate) fn check_match<'a, 'tcx>( + tcx: TyCtxt<'a, 'tcx, 'tcx>, + def_id: DefId, +) -> Result<(), ErrorReported> { + let body_id = if let Some(id) = tcx.hir.as_local_node_id(def_id) { + tcx.hir.body_owned_by(id) + } else { + return Ok(()); + }; + + tcx.sess.track_errors(|| { + MatchVisitor { + tcx, + tables: tcx.body_tables(body_id), + region_scope_tree: &tcx.region_scope_tree(def_id), + param_env: tcx.param_env(def_id), + identity_substs: Substs::identity_for_item(tcx, def_id), + }.visit_body(tcx.hir.body(body_id)); + }) +} + +fn create_e0004<'a>(sess: &'a Session, sp: Span, error_message: String) -> DiagnosticBuilder<'a> { + struct_span_err!(sess, sp, E0004, "{}", &error_message) +} + +struct MatchVisitor<'a, 'tcx: 'a> { + tcx: TyCtxt<'a, 'tcx, 'tcx>, + tables: &'a ty::TypeckTables<'tcx>, + param_env: ty::ParamEnv<'tcx>, + identity_substs: &'tcx Substs<'tcx>, + region_scope_tree: &'a region::ScopeTree, +} + +impl<'a, 'tcx> Visitor<'tcx> for MatchVisitor<'a, 'tcx> { + fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> { + NestedVisitorMap::None + } + + fn visit_expr(&mut self, ex: &'tcx hir::Expr) { + intravisit::walk_expr(self, ex); + + match ex.node { + hir::ExprMatch(ref scrut, ref arms, source) => { + self.check_match(scrut, arms, source); + } + _ => {} + } + } + + fn visit_local(&mut self, loc: &'tcx hir::Local) { + intravisit::walk_local(self, loc); + + self.check_irrefutable(&loc.pat, match loc.source { + hir::LocalSource::Normal => "local binding", + hir::LocalSource::ForLoopDesugar => "`for` loop binding", + }); + + // Check legality of move bindings and `@` patterns. + self.check_patterns(false, slice::from_ref(&loc.pat)); + } + + fn visit_body(&mut self, body: &'tcx hir::Body) { + intravisit::walk_body(self, body); + + for arg in &body.arguments { + self.check_irrefutable(&arg.pat, "function argument"); + self.check_patterns(false, slice::from_ref(&arg.pat)); + } + } +} + + +impl<'a, 'tcx> PatternContext<'a, 'tcx> { + fn report_inlining_errors(&self, pat_span: Span) { + for error in &self.errors { + match *error { + PatternError::StaticInPattern(span) => { + self.span_e0158(span, "statics cannot be referenced in patterns") + } + PatternError::AssociatedConstInPattern(span) => { + self.span_e0158(span, "associated consts cannot be referenced in patterns") + } + PatternError::ConstEval(ref err) => { + err.report(self.tcx, pat_span, "pattern"); + } + } + } + } + + fn span_e0158(&self, span: Span, text: &str) { + span_err!(self.tcx.sess, span, E0158, "{}", text) + } +} + +impl<'a, 'tcx> MatchVisitor<'a, 'tcx> { + fn check_patterns(&self, has_guard: bool, pats: &[P]) { + check_legality_of_move_bindings(self, has_guard, pats); + for pat in pats { + check_legality_of_bindings_in_at_patterns(self, pat); + } + } + + fn check_match( + &self, + scrut: &hir::Expr, + arms: &'tcx [hir::Arm], + source: hir::MatchSource) + { + for arm in arms { + // First, check legality of move bindings. + self.check_patterns(arm.guard.is_some(), &arm.pats); + + // Second, if there is a guard on each arm, make sure it isn't + // assigning or borrowing anything mutably. + if let Some(ref guard) = arm.guard { + check_for_mutation_in_guard(self, &guard); + } + + // Third, perform some lints. + for pat in &arm.pats { + check_for_bindings_named_the_same_as_variants(self, pat); + } + } + + let module = self.tcx.hir.get_module_parent(scrut.id); + MatchCheckCtxt::create_and_enter(self.tcx, module, |ref mut cx| { + let mut have_errors = false; + + let inlined_arms : Vec<(Vec<_>, _)> = arms.iter().map(|arm| ( + arm.pats.iter().map(|pat| { + let mut patcx = PatternContext::new(self.tcx, + self.param_env.and(self.identity_substs), + self.tables); + let pattern = expand_pattern(cx, patcx.lower_pattern(&pat)); + if !patcx.errors.is_empty() { + patcx.report_inlining_errors(pat.span); + have_errors = true; + } + (pattern, &**pat) + }).collect(), + arm.guard.as_ref().map(|e| &**e) + )).collect(); + + // Bail out early if inlining failed. + if have_errors { + return; + } + + // Fourth, check for unreachable arms. + check_arms(cx, &inlined_arms, source); + + // Then, if the match has no arms, check whether the scrutinee + // is uninhabited. + let pat_ty = self.tables.node_id_to_type(scrut.hir_id); + let module = self.tcx.hir.get_module_parent(scrut.id); + if inlined_arms.is_empty() { + let scrutinee_is_uninhabited = if self.tcx.features().never_type { + self.tcx.is_ty_uninhabited_from(module, pat_ty) + } else { + self.conservative_is_uninhabited(pat_ty) + }; + if !scrutinee_is_uninhabited { + // We know the type is inhabited, so this must be wrong + let mut err = create_e0004(self.tcx.sess, scrut.span, + format!("non-exhaustive patterns: type {} \ + is non-empty", + pat_ty)); + span_help!(&mut err, scrut.span, + "Please ensure that all possible cases are being handled; \ + possibly adding wildcards or more match arms."); + err.emit(); + } + // If the type *is* uninhabited, it's vacuously exhaustive + return; + } + + let matrix: Matrix = inlined_arms + .iter() + .filter(|&&(_, guard)| guard.is_none()) + .flat_map(|arm| &arm.0) + .map(|pat| vec![pat.0]) + .collect(); + let scrut_ty = self.tables.node_id_to_type(scrut.hir_id); + check_exhaustive(cx, scrut_ty, scrut.span, &matrix); + }) + } + + fn conservative_is_uninhabited(&self, scrutinee_ty: Ty<'tcx>) -> bool { + // "rustc-1.0-style" uncontentious uninhabitableness check + match scrutinee_ty.sty { + ty::TyNever => true, + ty::TyAdt(def, _) => def.variants.is_empty(), + _ => false + } + } + + fn check_irrefutable(&self, pat: &'tcx Pat, origin: &str) { + let module = self.tcx.hir.get_module_parent(pat.id); + MatchCheckCtxt::create_and_enter(self.tcx, module, |ref mut cx| { + let mut patcx = PatternContext::new(self.tcx, + self.param_env.and(self.identity_substs), + self.tables); + let pattern = patcx.lower_pattern(pat); + let pattern_ty = pattern.ty; + let pats : Matrix = vec![vec![ + expand_pattern(cx, pattern) + ]].into_iter().collect(); + + let wild_pattern = Pattern { + ty: pattern_ty, + span: DUMMY_SP, + kind: box PatternKind::Wild, + }; + let witness = match is_useful(cx, &pats, &[&wild_pattern], ConstructWitness) { + UsefulWithWitness(witness) => witness, + NotUseful => return, + Useful => bug!() + }; + + let pattern_string = witness[0].single_pattern().to_string(); + let mut diag = struct_span_err!( + self.tcx.sess, pat.span, E0005, + "refutable pattern in {}: `{}` not covered", + origin, pattern_string + ); + let label_msg = match pat.node { + PatKind::Path(hir::QPath::Resolved(None, ref path)) + if path.segments.len() == 1 && path.segments[0].parameters.is_none() => { + format!("interpreted as a {} pattern, not new variable", path.def.kind_name()) + } + _ => format!("pattern `{}` not covered", pattern_string), + }; + diag.span_label(pat.span, label_msg); + diag.emit(); + }); + } +} + +fn check_for_bindings_named_the_same_as_variants(cx: &MatchVisitor, pat: &Pat) { + pat.walk(|p| { + if let PatKind::Binding(_, _, name, None) = p.node { + let bm = *cx.tables + .pat_binding_modes() + .get(p.hir_id) + .expect("missing binding mode"); + + if bm != ty::BindByValue(hir::MutImmutable) { + // Nothing to check. + return true; + } + let pat_ty = cx.tables.pat_ty(p); + if let ty::TyAdt(edef, _) = pat_ty.sty { + if edef.is_enum() && edef.variants.iter().any(|variant| { + variant.name == name.node && variant.ctor_kind == CtorKind::Const + }) { + let ty_path = cx.tcx.item_path_str(edef.did); + let mut err = struct_span_warn!(cx.tcx.sess, p.span, E0170, + "pattern binding `{}` is named the same as one \ + of the variants of the type `{}`", + name.node, ty_path); + help!(err, + "if you meant to match on a variant, \ + consider making the path in the pattern qualified: `{}::{}`", + ty_path, name.node); + err.emit(); + } + } + } + true + }); +} + +/// Checks for common cases of "catchall" patterns that may not be intended as such. +fn pat_is_catchall(pat: &Pat) -> bool { + match pat.node { + PatKind::Binding(.., None) => true, + PatKind::Binding(.., Some(ref s)) => pat_is_catchall(s), + PatKind::Ref(ref s, _) => pat_is_catchall(s), + PatKind::Tuple(ref v, _) => v.iter().all(|p| { + pat_is_catchall(&p) + }), + _ => false + } +} + +// Check for unreachable patterns +fn check_arms<'a, 'tcx>(cx: &mut MatchCheckCtxt<'a, 'tcx>, + arms: &[(Vec<(&'a Pattern<'tcx>, &hir::Pat)>, Option<&hir::Expr>)], + source: hir::MatchSource) +{ + let mut seen = Matrix::empty(); + let mut catchall = None; + let mut printed_if_let_err = false; + for (arm_index, &(ref pats, guard)) in arms.iter().enumerate() { + for &(pat, hir_pat) in pats { + let v = vec![pat]; + + match is_useful(cx, &seen, &v, LeaveOutWitness) { + NotUseful => { + match source { + hir::MatchSource::IfLetDesugar { .. } => { + if printed_if_let_err { + // we already printed an irrefutable if-let pattern error. + // We don't want two, that's just confusing. + } else { + // find the first arm pattern so we can use its span + let &(ref first_arm_pats, _) = &arms[0]; + let first_pat = &first_arm_pats[0]; + let span = first_pat.0.span; + struct_span_err!(cx.tcx.sess, span, E0162, + "irrefutable if-let pattern") + .span_label(span, "irrefutable pattern") + .emit(); + printed_if_let_err = true; + } + }, + + hir::MatchSource::WhileLetDesugar => { + // find the first arm pattern so we can use its span + let &(ref first_arm_pats, _) = &arms[0]; + let first_pat = &first_arm_pats[0]; + let span = first_pat.0.span; + + // check which arm we're on. + match arm_index { + // The arm with the user-specified pattern. + 0 => { + cx.tcx.lint_node( + lint::builtin::UNREACHABLE_PATTERNS, + hir_pat.id, pat.span, + "unreachable pattern"); + }, + // The arm with the wildcard pattern. + 1 => { + struct_span_err!(cx.tcx.sess, span, E0165, + "irrefutable while-let pattern") + .span_label(span, "irrefutable pattern") + .emit(); + }, + _ => bug!(), + } + }, + + hir::MatchSource::ForLoopDesugar | + hir::MatchSource::Normal => { + let mut err = cx.tcx.struct_span_lint_node( + lint::builtin::UNREACHABLE_PATTERNS, + hir_pat.id, + pat.span, + "unreachable pattern", + ); + // if we had a catchall pattern, hint at that + if let Some(catchall) = catchall { + err.span_label(pat.span, "unreachable pattern"); + err.span_label(catchall, "matches any value"); + } + err.emit(); + }, + + // Unreachable patterns in try expressions occur when one of the arms + // are an uninhabited type. Which is OK. + hir::MatchSource::TryDesugar => {} + } + } + Useful => (), + UsefulWithWitness(_) => bug!() + } + if guard.is_none() { + seen.push(v); + if catchall.is_none() && pat_is_catchall(hir_pat) { + catchall = Some(pat.span); + } + } + } + } +} + +fn check_exhaustive<'a, 'tcx>(cx: &mut MatchCheckCtxt<'a, 'tcx>, + scrut_ty: Ty<'tcx>, + sp: Span, + matrix: &Matrix<'a, 'tcx>) { + let wild_pattern = Pattern { + ty: scrut_ty, + span: DUMMY_SP, + kind: box PatternKind::Wild, + }; + match is_useful(cx, matrix, &[&wild_pattern], ConstructWitness) { + UsefulWithWitness(pats) => { + let witnesses = if pats.is_empty() { + vec![&wild_pattern] + } else { + pats.iter().map(|w| w.single_pattern()).collect() + }; + + const LIMIT: usize = 3; + let joined_patterns = match witnesses.len() { + 0 => bug!(), + 1 => format!("`{}`", witnesses[0]), + 2...LIMIT => { + let (tail, head) = witnesses.split_last().unwrap(); + let head: Vec<_> = head.iter().map(|w| w.to_string()).collect(); + format!("`{}` and `{}`", head.join("`, `"), tail) + }, + _ => { + let (head, tail) = witnesses.split_at(LIMIT); + let head: Vec<_> = head.iter().map(|w| w.to_string()).collect(); + format!("`{}` and {} more", head.join("`, `"), tail.len()) + } + }; + + let label_text = match witnesses.len() { + 1 => format!("pattern {} not covered", joined_patterns), + _ => format!("patterns {} not covered", joined_patterns) + }; + create_e0004(cx.tcx.sess, sp, + format!("non-exhaustive patterns: {} not covered", + joined_patterns)) + .span_label(sp, label_text) + .emit(); + } + NotUseful => { + // This is good, wildcard pattern isn't reachable + }, + _ => bug!() + } +} + +// Legality of move bindings checking +fn check_legality_of_move_bindings(cx: &MatchVisitor, + has_guard: bool, + pats: &[P]) { + let mut by_ref_span = None; + for pat in pats { + pat.each_binding(|_, id, span, _path| { + let hir_id = cx.tcx.hir.node_to_hir_id(id); + let bm = *cx.tables + .pat_binding_modes() + .get(hir_id) + .expect("missing binding mode"); + if let ty::BindByReference(..) = bm { + by_ref_span = Some(span); + } + }) + } + + let check_move = |p: &Pat, sub: Option<&Pat>| { + // check legality of moving out of the enum + + // x @ Foo(..) is legal, but x @ Foo(y) isn't. + if sub.map_or(false, |p| p.contains_bindings()) { + struct_span_err!(cx.tcx.sess, p.span, E0007, + "cannot bind by-move with sub-bindings") + .span_label(p.span, "binds an already bound by-move value by moving it") + .emit(); + } else if has_guard { + struct_span_err!(cx.tcx.sess, p.span, E0008, + "cannot bind by-move into a pattern guard") + .span_label(p.span, "moves value into pattern guard") + .emit(); + } else if by_ref_span.is_some() { + struct_span_err!(cx.tcx.sess, p.span, E0009, + "cannot bind by-move and by-ref in the same pattern") + .span_label(p.span, "by-move pattern here") + .span_label(by_ref_span.unwrap(), "both by-ref and by-move used") + .emit(); + } + }; + + for pat in pats { + pat.walk(|p| { + if let PatKind::Binding(_, _, _, ref sub) = p.node { + let bm = *cx.tables + .pat_binding_modes() + .get(p.hir_id) + .expect("missing binding mode"); + match bm { + ty::BindByValue(..) => { + let pat_ty = cx.tables.node_id_to_type(p.hir_id); + if pat_ty.moves_by_default(cx.tcx, cx.param_env, pat.span) { + check_move(p, sub.as_ref().map(|p| &**p)); + } + } + _ => {} + } + } + true + }); + } +} + +/// Ensures that a pattern guard doesn't borrow by mutable reference or +/// assign. +/// +/// FIXME: this should be done by borrowck. +fn check_for_mutation_in_guard(cx: &MatchVisitor, guard: &hir::Expr) { + let mut checker = MutationChecker { + cx, + }; + ExprUseVisitor::new(&mut checker, cx.tcx, cx.param_env, cx.region_scope_tree, cx.tables, None) + .walk_expr(guard); +} + +struct MutationChecker<'a, 'tcx: 'a> { + cx: &'a MatchVisitor<'a, 'tcx>, +} + +impl<'a, 'tcx> Delegate<'tcx> for MutationChecker<'a, 'tcx> { + fn matched_pat(&mut self, _: &Pat, _: cmt, _: euv::MatchMode) {} + fn consume(&mut self, _: ast::NodeId, _: Span, _: cmt, _: ConsumeMode) {} + fn consume_pat(&mut self, _: &Pat, _: cmt, _: ConsumeMode) {} + fn borrow(&mut self, + _: ast::NodeId, + span: Span, + _: cmt, + _: ty::Region<'tcx>, + kind:ty:: BorrowKind, + _: LoanCause) { + match kind { + ty::MutBorrow => { + struct_span_err!(self.cx.tcx.sess, span, E0301, + "cannot mutably borrow in a pattern guard") + .span_label(span, "borrowed mutably in pattern guard") + .emit(); + } + ty::ImmBorrow | ty::UniqueImmBorrow => {} + } + } + fn decl_without_init(&mut self, _: ast::NodeId, _: Span) {} + fn mutate(&mut self, _: ast::NodeId, span: Span, _: cmt, mode: MutateMode) { + match mode { + MutateMode::JustWrite | MutateMode::WriteAndRead => { + struct_span_err!(self.cx.tcx.sess, span, E0302, "cannot assign in a pattern guard") + .span_label(span, "assignment in pattern guard") + .emit(); + } + MutateMode::Init => {} + } + } +} + +/// Forbids bindings in `@` patterns. This is necessary for memory safety, +/// because of the way rvalues are handled in the borrow check. (See issue +/// #14587.) +fn check_legality_of_bindings_in_at_patterns(cx: &MatchVisitor, pat: &Pat) { + AtBindingPatternVisitor { cx: cx, bindings_allowed: true }.visit_pat(pat); +} + +struct AtBindingPatternVisitor<'a, 'b:'a, 'tcx:'b> { + cx: &'a MatchVisitor<'b, 'tcx>, + bindings_allowed: bool +} + +impl<'a, 'b, 'tcx, 'v> Visitor<'v> for AtBindingPatternVisitor<'a, 'b, 'tcx> { + fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'v> { + NestedVisitorMap::None + } + + fn visit_pat(&mut self, pat: &Pat) { + match pat.node { + PatKind::Binding(.., ref subpat) => { + if !self.bindings_allowed { + struct_span_err!(self.cx.tcx.sess, pat.span, E0303, + "pattern bindings are not allowed after an `@`") + .span_label(pat.span, "not allowed after `@`") + .emit(); + } + + if subpat.is_some() { + let bindings_were_allowed = self.bindings_allowed; + self.bindings_allowed = false; + intravisit::walk_pat(self, pat); + self.bindings_allowed = bindings_were_allowed; + } + } + _ => intravisit::walk_pat(self, pat), + } + } +} diff --git a/src/librustc_mir/const_eval/eval.rs b/src/librustc_mir/const_eval/eval.rs new file mode 100644 index 00000000000..58fe40d12be --- /dev/null +++ b/src/librustc_mir/const_eval/eval.rs @@ -0,0 +1,697 @@ +// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use rustc::middle::const_val::ConstVal::*; +use rustc::middle::const_val::ConstAggregate::*; +use rustc::middle::const_val::ErrKind::*; +use rustc::middle::const_val::{ByteArray, ConstVal, ConstEvalErr, EvalResult, ErrKind}; + +use rustc::hir::map::blocks::FnLikeNode; +use rustc::hir::def::{Def, CtorKind}; +use rustc::hir::def_id::DefId; +use rustc::ty::{self, Ty, TyCtxt}; +use rustc::ty::util::IntTypeExt; +use rustc::ty::subst::{Substs, Subst}; +use rustc::util::common::ErrorReported; +use rustc::util::nodemap::NodeMap; + +use syntax::abi::Abi; +use syntax::ast; +use syntax::attr; +use rustc::hir::{self, Expr}; + +use std::cmp::Ordering; + +use rustc_const_math::*; +macro_rules! signal { + ($e:expr, $exn:expr) => { + return Err(ConstEvalErr { span: $e.span, kind: $exn }) + } +} + +macro_rules! math { + ($e:expr, $op:expr) => { + match $op { + Ok(val) => val, + Err(e) => signal!($e, ErrKind::from(e)), + } + } +} + +/// * `DefId` is the id of the constant. +/// * `Substs` is the monomorphized substitutions for the expression. +pub fn lookup_const_by_id<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + key: ty::ParamEnvAnd<'tcx, (DefId, &'tcx Substs<'tcx>)>) + -> Option<(DefId, &'tcx Substs<'tcx>)> { + ty::Instance::resolve( + tcx, + key.param_env, + key.value.0, + key.value.1, + ).map(|instance| (instance.def_id(), instance.substs)) +} + +pub struct ConstContext<'a, 'tcx: 'a> { + tcx: TyCtxt<'a, 'tcx, 'tcx>, + tables: &'a ty::TypeckTables<'tcx>, + param_env: ty::ParamEnv<'tcx>, + substs: &'tcx Substs<'tcx>, + fn_args: Option>> +} + +impl<'a, 'tcx> ConstContext<'a, 'tcx> { + pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, + param_env_and_substs: ty::ParamEnvAnd<'tcx, &'tcx Substs<'tcx>>, + tables: &'a ty::TypeckTables<'tcx>) + -> Self { + ConstContext { + tcx, + param_env: param_env_and_substs.param_env, + tables, + substs: param_env_and_substs.value, + fn_args: None + } + } + + /// Evaluate a constant expression in a context where the expression isn't + /// guaranteed to be evaluable. + pub fn eval(&self, e: &'tcx Expr) -> EvalResult<'tcx> { + if self.tables.tainted_by_errors { + signal!(e, TypeckError); + } + eval_const_expr_partial(self, e) + } +} + +type CastResult<'tcx> = Result, ErrKind<'tcx>>; + +fn eval_const_expr_partial<'a, 'tcx>(cx: &ConstContext<'a, 'tcx>, + e: &'tcx Expr) -> EvalResult<'tcx> { + trace!("eval_const_expr_partial: {:?}", e); + let tcx = cx.tcx; + let ty = cx.tables.expr_ty(e).subst(tcx, cx.substs); + let mk_const = |val| tcx.mk_const(ty::Const { val, ty }); + + let result = match e.node { + hir::ExprUnary(hir::UnNeg, ref inner) => { + // unary neg literals already got their sign during creation + if let hir::ExprLit(ref lit) = inner.node { + return match lit_to_const(&lit.node, tcx, ty, true) { + Ok(val) => Ok(mk_const(val)), + Err(err) => signal!(e, err), + }; + } + mk_const(match cx.eval(inner)?.val { + Float(f) => Float(-f), + Integral(i) => Integral(math!(e, -i)), + _ => signal!(e, TypeckError) + }) + } + hir::ExprUnary(hir::UnNot, ref inner) => { + mk_const(match cx.eval(inner)?.val { + Integral(i) => Integral(math!(e, !i)), + Bool(b) => Bool(!b), + _ => signal!(e, TypeckError) + }) + } + hir::ExprUnary(hir::UnDeref, _) => signal!(e, UnimplementedConstVal("deref operation")), + hir::ExprBinary(op, ref a, ref b) => { + // technically, if we don't have type hints, but integral eval + // gives us a type through a type-suffix, cast or const def type + // we need to re-eval the other value of the BinOp if it was + // not inferred + mk_const(match (cx.eval(a)?.val, cx.eval(b)?.val) { + (Float(a), Float(b)) => { + use std::cmp::Ordering::*; + match op.node { + hir::BiAdd => Float(math!(e, a + b)), + hir::BiSub => Float(math!(e, a - b)), + hir::BiMul => Float(math!(e, a * b)), + hir::BiDiv => Float(math!(e, a / b)), + hir::BiRem => Float(math!(e, a % b)), + hir::BiEq => Bool(math!(e, a.try_cmp(b)) == Equal), + hir::BiLt => Bool(math!(e, a.try_cmp(b)) == Less), + hir::BiLe => Bool(math!(e, a.try_cmp(b)) != Greater), + hir::BiNe => Bool(math!(e, a.try_cmp(b)) != Equal), + hir::BiGe => Bool(math!(e, a.try_cmp(b)) != Less), + hir::BiGt => Bool(math!(e, a.try_cmp(b)) == Greater), + _ => span_bug!(e.span, "typeck error"), + } + } + (Integral(a), Integral(b)) => { + use std::cmp::Ordering::*; + match op.node { + hir::BiAdd => Integral(math!(e, a + b)), + hir::BiSub => Integral(math!(e, a - b)), + hir::BiMul => Integral(math!(e, a * b)), + hir::BiDiv => Integral(math!(e, a / b)), + hir::BiRem => Integral(math!(e, a % b)), + hir::BiBitAnd => Integral(math!(e, a & b)), + hir::BiBitOr => Integral(math!(e, a | b)), + hir::BiBitXor => Integral(math!(e, a ^ b)), + hir::BiShl => Integral(math!(e, a << b)), + hir::BiShr => Integral(math!(e, a >> b)), + hir::BiEq => Bool(math!(e, a.try_cmp(b)) == Equal), + hir::BiLt => Bool(math!(e, a.try_cmp(b)) == Less), + hir::BiLe => Bool(math!(e, a.try_cmp(b)) != Greater), + hir::BiNe => Bool(math!(e, a.try_cmp(b)) != Equal), + hir::BiGe => Bool(math!(e, a.try_cmp(b)) != Less), + hir::BiGt => Bool(math!(e, a.try_cmp(b)) == Greater), + _ => span_bug!(e.span, "typeck error"), + } + } + (Bool(a), Bool(b)) => { + Bool(match op.node { + hir::BiAnd => a && b, + hir::BiOr => a || b, + hir::BiBitXor => a ^ b, + hir::BiBitAnd => a & b, + hir::BiBitOr => a | b, + hir::BiEq => a == b, + hir::BiNe => a != b, + hir::BiLt => a < b, + hir::BiLe => a <= b, + hir::BiGe => a >= b, + hir::BiGt => a > b, + _ => span_bug!(e.span, "typeck error"), + }) + } + (Char(a), Char(b)) => { + Bool(match op.node { + hir::BiEq => a == b, + hir::BiNe => a != b, + hir::BiLt => a < b, + hir::BiLe => a <= b, + hir::BiGe => a >= b, + hir::BiGt => a > b, + _ => span_bug!(e.span, "typeck error"), + }) + } + + _ => signal!(e, MiscBinaryOp), + }) + } + hir::ExprCast(ref base, _) => { + let base_val = cx.eval(base)?; + let base_ty = cx.tables.expr_ty(base).subst(tcx, cx.substs); + if ty == base_ty { + base_val + } else { + match cast_const(tcx, base_val.val, ty) { + Ok(val) => mk_const(val), + Err(kind) => signal!(e, kind), + } + } + } + hir::ExprPath(ref qpath) => { + let substs = cx.tables.node_substs(e.hir_id).subst(tcx, cx.substs); + match cx.tables.qpath_def(qpath, e.hir_id) { + Def::Const(def_id) | + Def::AssociatedConst(def_id) => { + let substs = tcx.normalize_associated_type_in_env(&substs, cx.param_env); + match tcx.at(e.span).const_eval(cx.param_env.and((def_id, substs))) { + Ok(val) => val, + Err(ConstEvalErr { kind: TypeckError, .. }) => { + signal!(e, TypeckError); + } + Err(err) => { + debug!("bad reference: {:?}, {:?}", err.description(), err.span); + signal!(e, ErroneousReferencedConstant(box err)) + }, + } + }, + Def::VariantCtor(variant_def, CtorKind::Const) => { + mk_const(Variant(variant_def)) + } + Def::VariantCtor(_, CtorKind::Fn) => { + signal!(e, UnimplementedConstVal("enum variants")); + } + Def::StructCtor(_, CtorKind::Const) => { + mk_const(Aggregate(Struct(&[]))) + } + Def::StructCtor(_, CtorKind::Fn) => { + signal!(e, UnimplementedConstVal("tuple struct constructors")) + } + Def::Local(id) => { + debug!("Def::Local({:?}): {:?}", id, cx.fn_args); + if let Some(&val) = cx.fn_args.as_ref().and_then(|args| args.get(&id)) { + val + } else { + signal!(e, NonConstPath); + } + }, + Def::Method(id) | Def::Fn(id) => mk_const(Function(id, substs)), + Def::Err => span_bug!(e.span, "typeck error"), + _ => signal!(e, NonConstPath), + } + } + hir::ExprCall(ref callee, ref args) => { + let (def_id, substs) = match cx.eval(callee)?.val { + Function(def_id, substs) => (def_id, substs), + _ => signal!(e, TypeckError), + }; + + if tcx.fn_sig(def_id).abi() == Abi::RustIntrinsic { + let layout_of = |ty: Ty<'tcx>| { + let ty = tcx.erase_regions(&ty); + tcx.at(e.span).layout_of(cx.param_env.and(ty)).map_err(|err| { + ConstEvalErr { span: e.span, kind: LayoutError(err) } + }) + }; + match &tcx.item_name(def_id)[..] { + "size_of" => { + let size = layout_of(substs.type_at(0))?.size.bytes(); + return Ok(mk_const(Integral(Usize(ConstUsize::new(size, + tcx.sess.target.usize_ty).unwrap())))); + } + "min_align_of" => { + let align = layout_of(substs.type_at(0))?.align.abi(); + return Ok(mk_const(Integral(Usize(ConstUsize::new(align, + tcx.sess.target.usize_ty).unwrap())))); + } + "type_id" => { + let type_id = tcx.type_id_hash(substs.type_at(0)); + return Ok(mk_const(Integral(U64(type_id)))); + } + _ => signal!(e, TypeckError) + } + } + + let body = if let Some(node_id) = tcx.hir.as_local_node_id(def_id) { + if let Some(fn_like) = FnLikeNode::from_node(tcx.hir.get(node_id)) { + if fn_like.constness() == hir::Constness::Const { + tcx.hir.body(fn_like.body()) + } else { + signal!(e, TypeckError) + } + } else { + signal!(e, TypeckError) + } + } else { + if tcx.is_const_fn(def_id) { + tcx.extern_const_body(def_id).body + } else { + signal!(e, TypeckError) + } + }; + + let arg_ids = body.arguments.iter().map(|arg| match arg.pat.node { + hir::PatKind::Binding(_, canonical_id, _, _) => Some(canonical_id), + _ => None + }).collect::>(); + assert_eq!(arg_ids.len(), args.len()); + + let mut call_args = NodeMap(); + for (arg, arg_expr) in arg_ids.into_iter().zip(args.iter()) { + let arg_val = cx.eval(arg_expr)?; + debug!("const call arg: {:?}", arg); + if let Some(id) = arg { + assert!(call_args.insert(id, arg_val).is_none()); + } + } + debug!("const call({:?})", call_args); + let callee_cx = ConstContext { + tcx, + param_env: cx.param_env, + tables: tcx.typeck_tables_of(def_id), + substs, + fn_args: Some(call_args) + }; + callee_cx.eval(&body.value)? + }, + hir::ExprLit(ref lit) => match lit_to_const(&lit.node, tcx, ty, false) { + Ok(val) => mk_const(val), + Err(err) => signal!(e, err), + }, + hir::ExprBlock(ref block) => { + match block.expr { + Some(ref expr) => cx.eval(expr)?, + None => mk_const(Aggregate(Tuple(&[]))), + } + } + hir::ExprType(ref e, _) => cx.eval(e)?, + hir::ExprTup(ref fields) => { + let values = fields.iter().map(|e| cx.eval(e)).collect::, _>>()?; + mk_const(Aggregate(Tuple(tcx.alloc_const_slice(&values)))) + } + hir::ExprStruct(_, ref fields, _) => { + mk_const(Aggregate(Struct(tcx.alloc_name_const_slice(&fields.iter().map(|f| { + cx.eval(&f.expr).map(|v| (f.name.node, v)) + }).collect::, _>>()?)))) + } + hir::ExprIndex(ref arr, ref idx) => { + if !tcx.features().const_indexing { + signal!(e, IndexOpFeatureGated); + } + let arr = cx.eval(arr)?; + let idx = match cx.eval(idx)?.val { + Integral(Usize(i)) => i.as_u64(), + _ => signal!(idx, IndexNotUsize), + }; + assert_eq!(idx as usize as u64, idx); + match arr.val { + Aggregate(Array(v)) => { + if let Some(&elem) = v.get(idx as usize) { + elem + } else { + let n = v.len() as u64; + signal!(e, IndexOutOfBounds { len: n, index: idx }) + } + } + + Aggregate(Repeat(.., n)) if idx >= n => { + signal!(e, IndexOutOfBounds { len: n, index: idx }) + } + Aggregate(Repeat(elem, _)) => elem, + + ByteStr(b) if idx >= b.data.len() as u64 => { + signal!(e, IndexOutOfBounds { len: b.data.len() as u64, index: idx }) + } + ByteStr(b) => { + mk_const(Integral(U8(b.data[idx as usize]))) + }, + + _ => signal!(e, IndexedNonVec), + } + } + hir::ExprArray(ref v) => { + let values = v.iter().map(|e| cx.eval(e)).collect::, _>>()?; + mk_const(Aggregate(Array(tcx.alloc_const_slice(&values)))) + } + hir::ExprRepeat(ref elem, _) => { + let n = match ty.sty { + ty::TyArray(_, n) => n.val.unwrap_u64(), + _ => span_bug!(e.span, "typeck error") + }; + mk_const(Aggregate(Repeat(cx.eval(elem)?, n))) + }, + hir::ExprTupField(ref base, index) => { + if let Aggregate(Tuple(fields)) = cx.eval(base)?.val { + fields[index.node] + } else { + span_bug!(base.span, "{:#?}", cx.eval(base)?.val); + //signal!(base, ExpectedConstTuple); + } + } + hir::ExprField(ref base, field_name) => { + if let Aggregate(Struct(fields)) = cx.eval(base)?.val { + if let Some(&(_, f)) = fields.iter().find(|&&(name, _)| name == field_name.node) { + f + } else { + signal!(e, MissingStructField); + } + } else { + signal!(base, ExpectedConstStruct); + } + } + hir::ExprAddrOf(..) => signal!(e, UnimplementedConstVal("address operator")), + _ => signal!(e, MiscCatchAll) + }; + + Ok(result) +} + +fn cast_const_int<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + val: ConstInt, + ty: Ty<'tcx>) + -> CastResult<'tcx> { + let v = val.to_u128_unchecked(); + match ty.sty { + ty::TyBool if v == 0 => Ok(Bool(false)), + ty::TyBool if v == 1 => Ok(Bool(true)), + ty::TyInt(ast::IntTy::I8) => Ok(Integral(I8(v as i128 as i8))), + ty::TyInt(ast::IntTy::I16) => Ok(Integral(I16(v as i128 as i16))), + ty::TyInt(ast::IntTy::I32) => Ok(Integral(I32(v as i128 as i32))), + ty::TyInt(ast::IntTy::I64) => Ok(Integral(I64(v as i128 as i64))), + ty::TyInt(ast::IntTy::I128) => Ok(Integral(I128(v as i128))), + ty::TyInt(ast::IntTy::Isize) => { + Ok(Integral(Isize(ConstIsize::new_truncating(v as i128, tcx.sess.target.isize_ty)))) + }, + ty::TyUint(ast::UintTy::U8) => Ok(Integral(U8(v as u8))), + ty::TyUint(ast::UintTy::U16) => Ok(Integral(U16(v as u16))), + ty::TyUint(ast::UintTy::U32) => Ok(Integral(U32(v as u32))), + ty::TyUint(ast::UintTy::U64) => Ok(Integral(U64(v as u64))), + ty::TyUint(ast::UintTy::U128) => Ok(Integral(U128(v as u128))), + ty::TyUint(ast::UintTy::Usize) => { + Ok(Integral(Usize(ConstUsize::new_truncating(v, tcx.sess.target.usize_ty)))) + }, + ty::TyFloat(fty) => { + if let Some(i) = val.to_u128() { + Ok(Float(ConstFloat::from_u128(i, fty))) + } else { + // The value must be negative, go through signed integers. + let i = val.to_u128_unchecked() as i128; + Ok(Float(ConstFloat::from_i128(i, fty))) + } + } + ty::TyRawPtr(_) => Err(ErrKind::UnimplementedConstVal("casting an address to a raw ptr")), + ty::TyChar => match val { + U8(u) => Ok(Char(u as char)), + _ => bug!(), + }, + _ => Err(CannotCast), + } +} + +fn cast_const_float<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + val: ConstFloat, + ty: Ty<'tcx>) -> CastResult<'tcx> { + let int_width = |ty| { + ty::layout::Integer::from_attr(tcx, ty).size().bits() as usize + }; + match ty.sty { + ty::TyInt(ity) => { + if let Some(i) = val.to_i128(int_width(attr::SignedInt(ity))) { + cast_const_int(tcx, I128(i), ty) + } else { + Err(CannotCast) + } + } + ty::TyUint(uty) => { + if let Some(i) = val.to_u128(int_width(attr::UnsignedInt(uty))) { + cast_const_int(tcx, U128(i), ty) + } else { + Err(CannotCast) + } + } + ty::TyFloat(fty) => Ok(Float(val.convert(fty))), + _ => Err(CannotCast), + } +} + +fn cast_const<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + val: ConstVal<'tcx>, + ty: Ty<'tcx>) + -> CastResult<'tcx> { + match val { + Integral(i) => cast_const_int(tcx, i, ty), + Bool(b) => cast_const_int(tcx, U8(b as u8), ty), + Float(f) => cast_const_float(tcx, f, ty), + Char(c) => cast_const_int(tcx, U32(c as u32), ty), + Variant(v) => { + let adt = tcx.adt_def(tcx.parent_def_id(v).unwrap()); + let idx = adt.variant_index_with_id(v); + cast_const_int(tcx, adt.discriminant_for_variant(tcx, idx), ty) + } + Function(..) => Err(UnimplementedConstVal("casting fn pointers")), + ByteStr(b) => match ty.sty { + ty::TyRawPtr(_) => { + Err(ErrKind::UnimplementedConstVal("casting a bytestr to a raw ptr")) + }, + ty::TyRef(_, ty::TypeAndMut { ref ty, mutbl: hir::MutImmutable }) => match ty.sty { + ty::TyArray(ty, n) => { + let n = n.val.unwrap_u64(); + if ty == tcx.types.u8 && n == b.data.len() as u64 { + Ok(val) + } else { + Err(CannotCast) + } + } + ty::TySlice(_) => { + Err(ErrKind::UnimplementedConstVal("casting a bytestr to slice")) + }, + _ => Err(CannotCast), + }, + _ => Err(CannotCast), + }, + Str(s) => match ty.sty { + ty::TyRawPtr(_) => Err(ErrKind::UnimplementedConstVal("casting a str to a raw ptr")), + ty::TyRef(_, ty::TypeAndMut { ref ty, mutbl: hir::MutImmutable }) => match ty.sty { + ty::TyStr => Ok(Str(s)), + _ => Err(CannotCast), + }, + _ => Err(CannotCast), + }, + _ => Err(CannotCast), + } +} + +pub fn lit_to_const<'a, 'tcx>(lit: &'tcx ast::LitKind, + tcx: TyCtxt<'a, 'tcx, 'tcx>, + mut ty: Ty<'tcx>, + neg: bool) + -> Result, ErrKind<'tcx>> { + use syntax::ast::*; + use syntax::ast::LitIntType::*; + + if tcx.sess.opts.debugging_opts.miri { + use rustc::mir::interpret::*; + let lit = match *lit { + LitKind::Str(ref s, _) => { + let s = s.as_str(); + let id = tcx.allocate_cached(s.as_bytes()); + let ptr = MemoryPointer::new(AllocId(id), 0); + Value::ByValPair( + PrimVal::Ptr(ptr), + PrimVal::from_u128(s.len() as u128), + ) + }, + LitKind::ByteStr(ref data) => { + let id = tcx.allocate_cached(data); + let ptr = MemoryPointer::new(AllocId(id), 0); + Value::ByVal(PrimVal::Ptr(ptr)) + }, + LitKind::Byte(n) => Value::ByVal(PrimVal::Bytes(n as u128)), + LitKind::Int(n, _) if neg => { + let n = n as i128; + let n = n.overflowing_neg().0; + Value::ByVal(PrimVal::Bytes(n as u128)) + }, + LitKind::Int(n, _) => Value::ByVal(PrimVal::Bytes(n as u128)), + LitKind::Float(n, fty) => { + let n = n.as_str(); + let mut f = parse_float(&n, fty)?; + if neg { + f = -f; + } + let bits = f.bits; + Value::ByVal(PrimVal::Bytes(bits)) + } + LitKind::FloatUnsuffixed(n) => { + let fty = match ty.sty { + ty::TyFloat(fty) => fty, + _ => bug!() + }; + let n = n.as_str(); + let mut f = parse_float(&n, fty)?; + if neg { + f = -f; + } + let bits = f.bits; + Value::ByVal(PrimVal::Bytes(bits)) + } + LitKind::Bool(b) => Value::ByVal(PrimVal::Bytes(b as u128)), + LitKind::Char(c) => Value::ByVal(PrimVal::Bytes(c as u128)), + }; + return Ok(ConstVal::Value(lit)); + } + + if let ty::TyAdt(adt, _) = ty.sty { + if adt.is_enum() { + ty = adt.repr.discr_type().to_ty(tcx) + } + } + + match *lit { + LitKind::Str(ref s, _) => Ok(Str(s.as_str())), + LitKind::ByteStr(ref data) => Ok(ByteStr(ByteArray { data })), + LitKind::Byte(n) => Ok(Integral(U8(n))), + LitKind::Int(n, hint) => { + match (&ty.sty, hint) { + (&ty::TyInt(ity), _) | + (_, Signed(ity)) => { + let mut n = n as i128; + if neg { + n = n.overflowing_neg().0; + } + Ok(Integral(ConstInt::new_signed_truncating(n, + ity, tcx.sess.target.isize_ty))) + } + (&ty::TyUint(uty), _) | + (_, Unsigned(uty)) => { + Ok(Integral(ConstInt::new_unsigned_truncating(n, + uty, tcx.sess.target.usize_ty))) + } + _ => bug!() + } + } + LitKind::Float(n, fty) => { + let mut f = parse_float(&n.as_str(), fty)?; + if neg { + f = -f; + } + Ok(Float(f)) + } + LitKind::FloatUnsuffixed(n) => { + let fty = match ty.sty { + ty::TyFloat(fty) => fty, + _ => bug!() + }; + let mut f = parse_float(&n.as_str(), fty)?; + if neg { + f = -f; + } + Ok(Float(f)) + } + LitKind::Bool(b) => Ok(Bool(b)), + LitKind::Char(c) => Ok(Char(c)), + } +} + +fn parse_float<'tcx>(num: &str, fty: ast::FloatTy) + -> Result> { + ConstFloat::from_str(num, fty).map_err(|_| { + // FIXME(#31407) this is only necessary because float parsing is buggy + UnimplementedConstVal("could not evaluate float literal (see issue #31407)") + }) +} + +pub fn compare_const_vals(a: &ConstVal, b: &ConstVal, ty: Ty) -> Option { + trace!("compare_const_vals: {:?}, {:?}", a, b); + use rustc::mir::interpret::{Value, PrimVal}; + match (a, b) { + (&Integral(a), &Integral(b)) => a.try_cmp(b).ok(), + (&Char(a), &Char(b)) => Some(a.cmp(&b)), + (&Value(Value::ByVal(PrimVal::Bytes(a))), + &Value(Value::ByVal(PrimVal::Bytes(b)))) => { + Some(if ty.is_signed() { + (a as i128).cmp(&(b as i128)) + } else { + a.cmp(&b) + }) + }, + _ if a == b => Some(Ordering::Equal), + _ => None, + } +} + +impl<'a, 'tcx> ConstContext<'a, 'tcx> { + pub fn compare_lit_exprs(&self, + a: &'tcx Expr, + b: &'tcx Expr) -> Result, ErrorReported> { + let tcx = self.tcx; + let ty = self.tables.expr_ty(a); + let a = match self.eval(a) { + Ok(a) => a, + Err(e) => { + e.report(tcx, a.span, "expression"); + return Err(ErrorReported); + } + }; + let b = match self.eval(b) { + Ok(b) => b, + Err(e) => { + e.report(tcx, b.span, "expression"); + return Err(ErrorReported); + } + }; + Ok(compare_const_vals(&a.val, &b.val, ty)) + } +} diff --git a/src/librustc_mir/const_eval/mod.rs b/src/librustc_mir/const_eval/mod.rs new file mode 100644 index 00000000000..27356c2b082 --- /dev/null +++ b/src/librustc_mir/const_eval/mod.rs @@ -0,0 +1,18 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! constant evaluation on the HIR and code to validate patterns/matches + +mod eval; +mod _match; +pub mod check_match; +pub mod pattern; + +pub use self::eval::*; diff --git a/src/librustc_mir/const_eval/pattern.rs b/src/librustc_mir/const_eval/pattern.rs new file mode 100644 index 00000000000..a1109dbfdd1 --- /dev/null +++ b/src/librustc_mir/const_eval/pattern.rs @@ -0,0 +1,1070 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use const_eval::eval; +use interpret::{const_val_field, const_discr}; + +use rustc::middle::const_val::{ConstEvalErr, ConstVal, ConstAggregate}; +use rustc::mir::{Field, BorrowKind, Mutability}; +use rustc::mir::interpret::{Value, PrimVal}; +use rustc::ty::{self, TyCtxt, AdtDef, Ty, Region}; +use rustc::ty::subst::{Substs, Kind}; +use rustc::hir::{self, PatKind, RangeEnd}; +use rustc::hir::def::{Def, CtorKind}; +use rustc::hir::pat_util::EnumerateAndAdjustIterator; + +use rustc_data_structures::indexed_vec::Idx; + +use std::fmt; +use syntax::ast; +use syntax::ptr::P; +use syntax_pos::Span; + +#[derive(Clone, Debug)] +pub enum PatternError<'tcx> { + AssociatedConstInPattern(Span), + StaticInPattern(Span), + ConstEval(ConstEvalErr<'tcx>), +} + +#[derive(Copy, Clone, Debug)] +pub enum BindingMode<'tcx> { + ByValue, + ByRef(Region<'tcx>, BorrowKind), +} + +#[derive(Clone, Debug)] +pub struct FieldPattern<'tcx> { + pub field: Field, + pub pattern: Pattern<'tcx>, +} + +#[derive(Clone, Debug)] +pub struct Pattern<'tcx> { + pub ty: Ty<'tcx>, + pub span: Span, + pub kind: Box>, +} + +#[derive(Clone, Debug)] +pub enum PatternKind<'tcx> { + Wild, + + /// x, ref x, x @ P, etc + Binding { + mutability: Mutability, + name: ast::Name, + mode: BindingMode<'tcx>, + var: ast::NodeId, + ty: Ty<'tcx>, + subpattern: Option>, + }, + + /// Foo(...) or Foo{...} or Foo, where `Foo` is a variant name from an adt with >1 variants + Variant { + adt_def: &'tcx AdtDef, + substs: &'tcx Substs<'tcx>, + variant_index: usize, + subpatterns: Vec>, + }, + + /// (...), Foo(...), Foo{...}, or Foo, where `Foo` is a variant name from an adt with 1 variant + Leaf { + subpatterns: Vec>, + }, + + /// box P, &P, &mut P, etc + Deref { + subpattern: Pattern<'tcx>, + }, + + Constant { + value: &'tcx ty::Const<'tcx>, + }, + + Range { + lo: &'tcx ty::Const<'tcx>, + hi: &'tcx ty::Const<'tcx>, + end: RangeEnd, + }, + + /// matches against a slice, checking the length and extracting elements. + /// irrefutable when there is a slice pattern and both `prefix` and `suffix` are empty. + /// e.g. `&[ref xs..]`. + Slice { + prefix: Vec>, + slice: Option>, + suffix: Vec>, + }, + + /// fixed match against an array, irrefutable + Array { + prefix: Vec>, + slice: Option>, + suffix: Vec>, + }, +} + +fn print_const_val(value: &ty::Const, f: &mut fmt::Formatter) -> fmt::Result { + match value.val { + ConstVal::Float(ref x) => write!(f, "{}", x), + ConstVal::Integral(ref i) => write!(f, "{}", i), + ConstVal::Str(ref s) => write!(f, "{:?}", &s[..]), + ConstVal::ByteStr(b) => write!(f, "{:?}", b.data), + ConstVal::Bool(b) => write!(f, "{:?}", b), + ConstVal::Char(c) => write!(f, "{:?}", c), + ConstVal::Value(v) => print_miri_value(v, value.ty, f), + ConstVal::Variant(_) | + ConstVal::Function(..) | + ConstVal::Aggregate(_) | + ConstVal::Unevaluated(..) => bug!("{:?} not printable in a pattern", value) + } +} + +fn print_miri_value(value: Value, ty: Ty, f: &mut fmt::Formatter) -> fmt::Result { + use rustc::ty::TypeVariants::*; + match (value, &ty.sty) { + (Value::ByVal(PrimVal::Bytes(0)), &TyBool) => write!(f, "false"), + (Value::ByVal(PrimVal::Bytes(1)), &TyBool) => write!(f, "true"), + (Value::ByVal(PrimVal::Bytes(n)), &TyUint(..)) => write!(f, "{:?}", n), + (Value::ByVal(PrimVal::Bytes(n)), &TyInt(..)) => write!(f, "{:?}", n as i128), + (Value::ByVal(PrimVal::Bytes(n)), &TyChar) => + write!(f, "{:?}", ::std::char::from_u32(n as u32).unwrap()), + _ => bug!("{:?}: {} not printable in a pattern", value, ty), + } +} + +impl<'tcx> fmt::Display for Pattern<'tcx> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match *self.kind { + PatternKind::Wild => write!(f, "_"), + PatternKind::Binding { mutability, name, mode, ref subpattern, .. } => { + let is_mut = match mode { + BindingMode::ByValue => mutability == Mutability::Mut, + BindingMode::ByRef(_, bk) => { + write!(f, "ref ")?; + match bk { BorrowKind::Mut { .. } => true, _ => false } + } + }; + if is_mut { + write!(f, "mut ")?; + } + write!(f, "{}", name)?; + if let Some(ref subpattern) = *subpattern { + write!(f, " @ {}", subpattern)?; + } + Ok(()) + } + PatternKind::Variant { ref subpatterns, .. } | + PatternKind::Leaf { ref subpatterns } => { + let variant = match *self.kind { + PatternKind::Variant { adt_def, variant_index, .. } => { + Some(&adt_def.variants[variant_index]) + } + _ => if let ty::TyAdt(adt, _) = self.ty.sty { + if !adt.is_enum() { + Some(&adt.variants[0]) + } else { + None + } + } else { + None + } + }; + + let mut first = true; + let mut start_or_continue = || if first { first = false; "" } else { ", " }; + + if let Some(variant) = variant { + write!(f, "{}", variant.name)?; + + // Only for TyAdt we can have `S {...}`, + // which we handle separately here. + if variant.ctor_kind == CtorKind::Fictive { + write!(f, " {{ ")?; + + let mut printed = 0; + for p in subpatterns { + if let PatternKind::Wild = *p.pattern.kind { + continue; + } + let name = variant.fields[p.field.index()].name; + write!(f, "{}{}: {}", start_or_continue(), name, p.pattern)?; + printed += 1; + } + + if printed < variant.fields.len() { + write!(f, "{}..", start_or_continue())?; + } + + return write!(f, " }}"); + } + } + + let num_fields = variant.map_or(subpatterns.len(), |v| v.fields.len()); + if num_fields != 0 || variant.is_none() { + write!(f, "(")?; + for i in 0..num_fields { + write!(f, "{}", start_or_continue())?; + + // Common case: the field is where we expect it. + if let Some(p) = subpatterns.get(i) { + if p.field.index() == i { + write!(f, "{}", p.pattern)?; + continue; + } + } + + // Otherwise, we have to go looking for it. + if let Some(p) = subpatterns.iter().find(|p| p.field.index() == i) { + write!(f, "{}", p.pattern)?; + } else { + write!(f, "_")?; + } + } + write!(f, ")")?; + } + + Ok(()) + } + PatternKind::Deref { ref subpattern } => { + match self.ty.sty { + ty::TyAdt(def, _) if def.is_box() => write!(f, "box ")?, + ty::TyRef(_, mt) => { + write!(f, "&")?; + if mt.mutbl == hir::MutMutable { + write!(f, "mut ")?; + } + } + _ => bug!("{} is a bad Deref pattern type", self.ty) + } + write!(f, "{}", subpattern) + } + PatternKind::Constant { value } => { + print_const_val(value, f) + } + PatternKind::Range { lo, hi, end } => { + print_const_val(lo, f)?; + match end { + RangeEnd::Included => write!(f, "...")?, + RangeEnd::Excluded => write!(f, "..")?, + } + print_const_val(hi, f) + } + PatternKind::Slice { ref prefix, ref slice, ref suffix } | + PatternKind::Array { ref prefix, ref slice, ref suffix } => { + let mut first = true; + let mut start_or_continue = || if first { first = false; "" } else { ", " }; + write!(f, "[")?; + for p in prefix { + write!(f, "{}{}", start_or_continue(), p)?; + } + if let Some(ref slice) = *slice { + write!(f, "{}", start_or_continue())?; + match *slice.kind { + PatternKind::Wild => {} + _ => write!(f, "{}", slice)? + } + write!(f, "..")?; + } + for p in suffix { + write!(f, "{}{}", start_or_continue(), p)?; + } + write!(f, "]") + } + } + } +} + +pub struct PatternContext<'a, 'tcx: 'a> { + pub tcx: TyCtxt<'a, 'tcx, 'tcx>, + pub param_env: ty::ParamEnv<'tcx>, + pub tables: &'a ty::TypeckTables<'tcx>, + pub substs: &'tcx Substs<'tcx>, + pub errors: Vec>, +} + +impl<'a, 'tcx> Pattern<'tcx> { + pub fn from_hir(tcx: TyCtxt<'a, 'tcx, 'tcx>, + param_env_and_substs: ty::ParamEnvAnd<'tcx, &'tcx Substs<'tcx>>, + tables: &'a ty::TypeckTables<'tcx>, + pat: &'tcx hir::Pat) -> Self { + let mut pcx = PatternContext::new(tcx, param_env_and_substs, tables); + let result = pcx.lower_pattern(pat); + if !pcx.errors.is_empty() { + let msg = format!("encountered errors lowering pattern: {:?}", pcx.errors); + tcx.sess.delay_span_bug(pat.span, &msg); + } + debug!("Pattern::from_hir({:?}) = {:?}", pat, result); + result + } +} + +impl<'a, 'tcx> PatternContext<'a, 'tcx> { + pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, + param_env_and_substs: ty::ParamEnvAnd<'tcx, &'tcx Substs<'tcx>>, + tables: &'a ty::TypeckTables<'tcx>) -> Self { + PatternContext { + tcx, + param_env: param_env_and_substs.param_env, + tables, + substs: param_env_and_substs.value, + errors: vec![] + } + } + + pub fn lower_pattern(&mut self, pat: &'tcx hir::Pat) -> Pattern<'tcx> { + // When implicit dereferences have been inserted in this pattern, the unadjusted lowered + // pattern has the type that results *after* dereferencing. For example, in this code: + // + // ``` + // match &&Some(0i32) { + // Some(n) => { ... }, + // _ => { ... }, + // } + // ``` + // + // the type assigned to `Some(n)` in `unadjusted_pat` would be `Option` (this is + // determined in rustc_typeck::check::match). The adjustments would be + // + // `vec![&&Option, &Option]`. + // + // Applying the adjustments, we want to instead output `&&Some(n)` (as a HAIR pattern). So + // we wrap the unadjusted pattern in `PatternKind::Deref` repeatedly, consuming the + // adjustments in *reverse order* (last-in-first-out, so that the last `Deref` inserted + // gets the least-dereferenced type). + let unadjusted_pat = self.lower_pattern_unadjusted(pat); + self.tables + .pat_adjustments() + .get(pat.hir_id) + .unwrap_or(&vec![]) + .iter() + .rev() + .fold(unadjusted_pat, |pat, ref_ty| { + debug!("{:?}: wrapping pattern with type {:?}", pat, ref_ty); + Pattern { + span: pat.span, + ty: ref_ty, + kind: Box::new(PatternKind::Deref { subpattern: pat }), + } + }, + ) + } + + fn lower_pattern_unadjusted(&mut self, pat: &'tcx hir::Pat) -> Pattern<'tcx> { + let mut ty = self.tables.node_id_to_type(pat.hir_id); + + let kind = match pat.node { + PatKind::Wild => PatternKind::Wild, + + PatKind::Lit(ref value) => self.lower_lit(value), + + PatKind::Range(ref lo, ref hi, end) => { + match (self.lower_lit(lo), self.lower_lit(hi)) { + (PatternKind::Constant { value: lo }, + PatternKind::Constant { value: hi }) => { + PatternKind::Range { lo, hi, end } + } + _ => PatternKind::Wild + } + } + + PatKind::Path(ref qpath) => { + return self.lower_path(qpath, pat.hir_id, pat.span); + } + + PatKind::Ref(ref subpattern, _) | + PatKind::Box(ref subpattern) => { + PatternKind::Deref { subpattern: self.lower_pattern(subpattern) } + } + + PatKind::Slice(ref prefix, ref slice, ref suffix) => { + let ty = self.tables.node_id_to_type(pat.hir_id); + match ty.sty { + ty::TyRef(_, mt) => + PatternKind::Deref { + subpattern: Pattern { + ty: mt.ty, + span: pat.span, + kind: Box::new(self.slice_or_array_pattern( + pat.span, mt.ty, prefix, slice, suffix)) + }, + }, + + ty::TySlice(..) | + ty::TyArray(..) => + self.slice_or_array_pattern(pat.span, ty, prefix, slice, suffix), + + ref sty => + span_bug!( + pat.span, + "unexpanded type for vector pattern: {:?}", + sty), + } + } + + PatKind::Tuple(ref subpatterns, ddpos) => { + let ty = self.tables.node_id_to_type(pat.hir_id); + match ty.sty { + ty::TyTuple(ref tys, _) => { + let subpatterns = + subpatterns.iter() + .enumerate_and_adjust(tys.len(), ddpos) + .map(|(i, subpattern)| FieldPattern { + field: Field::new(i), + pattern: self.lower_pattern(subpattern) + }) + .collect(); + + PatternKind::Leaf { subpatterns: subpatterns } + } + + ref sty => span_bug!(pat.span, "unexpected type for tuple pattern: {:?}", sty), + } + } + + PatKind::Binding(_, id, ref ident, ref sub) => { + let var_ty = self.tables.node_id_to_type(pat.hir_id); + let region = match var_ty.sty { + ty::TyRef(r, _) => Some(r), + _ => None, + }; + let bm = *self.tables.pat_binding_modes().get(pat.hir_id) + .expect("missing binding mode"); + let (mutability, mode) = match bm { + ty::BindByValue(hir::MutMutable) => + (Mutability::Mut, BindingMode::ByValue), + ty::BindByValue(hir::MutImmutable) => + (Mutability::Not, BindingMode::ByValue), + ty::BindByReference(hir::MutMutable) => + (Mutability::Not, BindingMode::ByRef( + region.unwrap(), BorrowKind::Mut { allow_two_phase_borrow: false })), + ty::BindByReference(hir::MutImmutable) => + (Mutability::Not, BindingMode::ByRef( + region.unwrap(), BorrowKind::Shared)), + }; + + // A ref x pattern is the same node used for x, and as such it has + // x's type, which is &T, where we want T (the type being matched). + if let ty::BindByReference(_) = bm { + if let ty::TyRef(_, mt) = ty.sty { + ty = mt.ty; + } else { + bug!("`ref {}` has wrong type {}", ident.node, ty); + } + } + + PatternKind::Binding { + mutability, + mode, + name: ident.node, + var: id, + ty: var_ty, + subpattern: self.lower_opt_pattern(sub), + } + } + + PatKind::TupleStruct(ref qpath, ref subpatterns, ddpos) => { + let def = self.tables.qpath_def(qpath, pat.hir_id); + let adt_def = match ty.sty { + ty::TyAdt(adt_def, _) => adt_def, + _ => span_bug!(pat.span, "tuple struct pattern not applied to an ADT"), + }; + let variant_def = adt_def.variant_of_def(def); + + let subpatterns = + subpatterns.iter() + .enumerate_and_adjust(variant_def.fields.len(), ddpos) + .map(|(i, field)| FieldPattern { + field: Field::new(i), + pattern: self.lower_pattern(field), + }) + .collect(); + self.lower_variant_or_leaf(def, ty, subpatterns) + } + + PatKind::Struct(ref qpath, ref fields, _) => { + let def = self.tables.qpath_def(qpath, pat.hir_id); + let adt_def = match ty.sty { + ty::TyAdt(adt_def, _) => adt_def, + _ => { + span_bug!( + pat.span, + "struct pattern not applied to an ADT"); + } + }; + let variant_def = adt_def.variant_of_def(def); + + let subpatterns = + fields.iter() + .map(|field| { + let index = variant_def.index_of_field_named(field.node.name); + let index = index.unwrap_or_else(|| { + span_bug!( + pat.span, + "no field with name {:?}", + field.node.name); + }); + FieldPattern { + field: Field::new(index), + pattern: self.lower_pattern(&field.node.pat), + } + }) + .collect(); + + self.lower_variant_or_leaf(def, ty, subpatterns) + } + }; + + Pattern { + span: pat.span, + ty, + kind: Box::new(kind), + } + } + + fn lower_patterns(&mut self, pats: &'tcx [P]) -> Vec> { + pats.iter().map(|p| self.lower_pattern(p)).collect() + } + + fn lower_opt_pattern(&mut self, pat: &'tcx Option>) -> Option> + { + pat.as_ref().map(|p| self.lower_pattern(p)) + } + + fn flatten_nested_slice_patterns( + &mut self, + prefix: Vec>, + slice: Option>, + suffix: Vec>) + -> (Vec>, Option>, Vec>) + { + let orig_slice = match slice { + Some(orig_slice) => orig_slice, + None => return (prefix, slice, suffix) + }; + let orig_prefix = prefix; + let orig_suffix = suffix; + + // dance because of intentional borrow-checker stupidity. + let kind = *orig_slice.kind; + match kind { + PatternKind::Slice { prefix, slice, mut suffix } | + PatternKind::Array { prefix, slice, mut suffix } => { + let mut orig_prefix = orig_prefix; + + orig_prefix.extend(prefix); + suffix.extend(orig_suffix); + + (orig_prefix, slice, suffix) + } + _ => { + (orig_prefix, Some(Pattern { + kind: box kind, ..orig_slice + }), orig_suffix) + } + } + } + + fn slice_or_array_pattern( + &mut self, + span: Span, + ty: Ty<'tcx>, + prefix: &'tcx [P], + slice: &'tcx Option>, + suffix: &'tcx [P]) + -> PatternKind<'tcx> + { + let prefix = self.lower_patterns(prefix); + let slice = self.lower_opt_pattern(slice); + let suffix = self.lower_patterns(suffix); + let (prefix, slice, suffix) = + self.flatten_nested_slice_patterns(prefix, slice, suffix); + + match ty.sty { + ty::TySlice(..) => { + // matching a slice or fixed-length array + PatternKind::Slice { prefix: prefix, slice: slice, suffix: suffix } + } + + ty::TyArray(_, len) => { + // fixed-length array + let len = len.val.unwrap_u64(); + assert!(len >= prefix.len() as u64 + suffix.len() as u64); + PatternKind::Array { prefix: prefix, slice: slice, suffix: suffix } + } + + _ => { + span_bug!(span, "bad slice pattern type {:?}", ty); + } + } + } + + fn lower_variant_or_leaf( + &mut self, + def: Def, + ty: Ty<'tcx>, + subpatterns: Vec>) + -> PatternKind<'tcx> + { + match def { + Def::Variant(variant_id) | Def::VariantCtor(variant_id, ..) => { + let enum_id = self.tcx.parent_def_id(variant_id).unwrap(); + let adt_def = self.tcx.adt_def(enum_id); + if adt_def.is_enum() { + let substs = match ty.sty { + ty::TyAdt(_, substs) | + ty::TyFnDef(_, substs) => substs, + _ => bug!("inappropriate type for def: {:?}", ty.sty), + }; + PatternKind::Variant { + adt_def, + substs, + variant_index: adt_def.variant_index_with_id(variant_id), + subpatterns, + } + } else { + PatternKind::Leaf { subpatterns: subpatterns } + } + } + + Def::Struct(..) | Def::StructCtor(..) | Def::Union(..) | + Def::TyAlias(..) | Def::AssociatedTy(..) | Def::SelfTy(..) => { + PatternKind::Leaf { subpatterns: subpatterns } + } + + _ => bug!() + } + } + + fn lower_path(&mut self, + qpath: &hir::QPath, + id: hir::HirId, + span: Span) + -> Pattern<'tcx> { + let ty = self.tables.node_id_to_type(id); + let def = self.tables.qpath_def(qpath, id); + let is_associated_const = match def { + Def::AssociatedConst(_) => true, + _ => false, + }; + let kind = match def { + Def::Const(def_id) | Def::AssociatedConst(def_id) => { + let substs = self.tables.node_substs(id); + match self.tcx.at(span).const_eval(self.param_env.and((def_id, substs))) { + Ok(value) => { + if self.tcx.sess.opts.debugging_opts.miri { + if let ConstVal::Value(_) = value.val {} else { + panic!("const eval produced non-miri value: {:#?}", value); + } + } + let instance = ty::Instance::resolve( + self.tcx, + self.param_env, + def_id, + substs, + ).unwrap(); + return self.const_to_pat(instance, value, span) + }, + Err(e) => { + self.errors.push(PatternError::ConstEval(e)); + PatternKind::Wild + } + } + } + _ => self.lower_variant_or_leaf(def, ty, vec![]), + }; + + Pattern { + span, + ty, + kind: Box::new(kind), + } + } + + fn lower_lit(&mut self, expr: &'tcx hir::Expr) -> PatternKind<'tcx> { + if self.tcx.sess.opts.debugging_opts.miri { + return match expr.node { + hir::ExprLit(ref lit) => { + let ty = self.tables.expr_ty(expr); + match super::eval::lit_to_const(&lit.node, self.tcx, ty, false) { + Ok(value) => PatternKind::Constant { + value: self.tcx.mk_const(ty::Const { + ty, + val: value, + }), + }, + Err(e) => { + self.errors.push(PatternError::ConstEval(ConstEvalErr { + span: lit.span, + kind: e, + })); + PatternKind::Wild + }, + } + }, + hir::ExprPath(ref qpath) => *self.lower_path(qpath, expr.hir_id, expr.span).kind, + hir::ExprUnary(hir::UnNeg, ref expr) => { + let ty = self.tables.expr_ty(expr); + let lit = match expr.node { + hir::ExprLit(ref lit) => lit, + _ => span_bug!(expr.span, "not a literal: {:?}", expr), + }; + match super::eval::lit_to_const(&lit.node, self.tcx, ty, true) { + Ok(value) => PatternKind::Constant { + value: self.tcx.mk_const(ty::Const { + ty, + val: value, + }), + }, + Err(e) => { + self.errors.push(PatternError::ConstEval(ConstEvalErr { + span: lit.span, + kind: e, + })); + PatternKind::Wild + }, + } + } + _ => span_bug!(expr.span, "not a literal: {:?}", expr), + } + } + let const_cx = eval::ConstContext::new(self.tcx, + self.param_env.and(self.substs), + self.tables); + match const_cx.eval(expr) { + Ok(value) => { + if let ConstVal::Variant(def_id) = value.val { + let ty = self.tables.expr_ty(expr); + self.lower_variant_or_leaf(Def::Variant(def_id), ty, vec![]) + } else { + PatternKind::Constant { value } + } + } + Err(e) => { + self.errors.push(PatternError::ConstEval(e)); + PatternKind::Wild + } + } + } + + fn const_to_pat( + &self, + instance: ty::Instance<'tcx>, + cv: &'tcx ty::Const<'tcx>, + span: Span, + ) -> Pattern<'tcx> { + debug!("const_to_pat: cv={:#?}", cv); + let kind = match cv.ty.sty { + ty::TyFloat(_) => { + self.tcx.sess.span_err(span, "floating point constants cannot be used in patterns"); + PatternKind::Wild + } + ty::TyAdt(adt_def, _) if adt_def.is_union() => { + // Matching on union fields is unsafe, we can't hide it in constants + self.tcx.sess.span_err(span, "cannot use unions in constant patterns"); + PatternKind::Wild + } + ty::TyAdt(adt_def, _) if !self.tcx.has_attr(adt_def.did, "structural_match") => { + let msg = format!("to use a constant of type `{}` in a pattern, \ + `{}` must be annotated with `#[derive(PartialEq, Eq)]`", + self.tcx.item_path_str(adt_def.did), + self.tcx.item_path_str(adt_def.did)); + self.tcx.sess.span_err(span, &msg); + PatternKind::Wild + }, + ty::TyAdt(adt_def, substs) if adt_def.is_enum() => { + match cv.val { + ConstVal::Value(val) => { + let discr = const_discr( + self.tcx, self.param_env, instance, val, cv.ty + ).unwrap(); + let variant_index = adt_def + .discriminants(self.tcx) + .position(|var| var.to_u128_unchecked() == discr) + .unwrap(); + PatternKind::Variant { + adt_def, + substs, + variant_index, + subpatterns: adt_def + .variants[variant_index] + .fields + .iter() + .enumerate() + .map(|(i, _)| { + let field = Field::new(i); + let val = match cv.val { + ConstVal::Value(miri) => const_val_field( + self.tcx, self.param_env, instance, field, miri, cv.ty, + ).unwrap(), + _ => bug!("{:#?} is not a valid tuple", cv), + }; + FieldPattern { + field, + pattern: self.const_to_pat(instance, val, span), + } + }).collect(), + } + }, + ConstVal::Variant(var_did) => { + let variant_index = adt_def + .variants + .iter() + .position(|var| var.did == var_did) + .unwrap(); + PatternKind::Variant { + adt_def, + substs, + variant_index, + subpatterns: Vec::new(), + } + } + _ => return Pattern { + span, + ty: cv.ty, + kind: Box::new(PatternKind::Constant { + value: cv, + }), + } + } + }, + ty::TyAdt(adt_def, _) => { + let struct_var = adt_def.struct_variant(); + PatternKind::Leaf { + subpatterns: struct_var.fields.iter().enumerate().map(|(i, f)| { + let field = Field::new(i); + let val = match cv.val { + ConstVal::Aggregate(ConstAggregate::Struct(consts)) => { + consts.iter().find(|&&(name, _)| name == f.name).unwrap().1 + }, + ConstVal::Value(miri) => const_val_field( + self.tcx, self.param_env, instance, field, miri, cv.ty, + ).unwrap(), + _ => bug!("{:#?} is not a valid tuple", cv), + }; + FieldPattern { + field, + pattern: self.const_to_pat(instance, val, span), + } + }).collect() + } + } + ty::TyTuple(fields, _) => { + PatternKind::Leaf { + subpatterns: (0..fields.len()).map(|i| { + let field = Field::new(i); + let val = match cv.val { + ConstVal::Aggregate(ConstAggregate::Tuple(consts)) => consts[i], + ConstVal::Value(miri) => const_val_field( + self.tcx, self.param_env, instance, field, miri, cv.ty, + ).unwrap(), + _ => bug!("{:#?} is not a valid tuple", cv), + }; + FieldPattern { + field, + pattern: self.const_to_pat(instance, val, span), + } + }).collect() + } + } + ty::TyArray(_, n) => { + PatternKind::Leaf { + subpatterns: (0..n.val.unwrap_u64()).map(|i| { + let i = i as usize; + let field = Field::new(i); + let val = match cv.val { + ConstVal::Aggregate(ConstAggregate::Array(consts)) => consts[i], + ConstVal::Aggregate(ConstAggregate::Repeat(cv, _)) => cv, + ConstVal::Value(miri) => const_val_field( + self.tcx, self.param_env, instance, field, miri, cv.ty, + ).unwrap(), + _ => bug!("{:#?} is not a valid tuple", cv), + }; + FieldPattern { + field, + pattern: self.const_to_pat(instance, val, span), + } + }).collect() + } + } + _ => { + PatternKind::Constant { + value: cv, + } + }, + }; + + Pattern { + span, + ty: cv.ty, + kind: Box::new(kind), + } + } +} + +pub trait PatternFoldable<'tcx> : Sized { + fn fold_with>(&self, folder: &mut F) -> Self { + self.super_fold_with(folder) + } + + fn super_fold_with>(&self, folder: &mut F) -> Self; +} + +pub trait PatternFolder<'tcx> : Sized { + fn fold_pattern(&mut self, pattern: &Pattern<'tcx>) -> Pattern<'tcx> { + pattern.super_fold_with(self) + } + + fn fold_pattern_kind(&mut self, kind: &PatternKind<'tcx>) -> PatternKind<'tcx> { + kind.super_fold_with(self) + } +} + + +impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Box { + fn super_fold_with>(&self, folder: &mut F) -> Self { + let content: T = (**self).fold_with(folder); + box content + } +} + +impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Vec { + fn super_fold_with>(&self, folder: &mut F) -> Self { + self.iter().map(|t| t.fold_with(folder)).collect() + } +} + +impl<'tcx, T: PatternFoldable<'tcx>> PatternFoldable<'tcx> for Option { + fn super_fold_with>(&self, folder: &mut F) -> Self{ + self.as_ref().map(|t| t.fold_with(folder)) + } +} + +macro_rules! CloneImpls { + (<$lt_tcx:tt> $($ty:ty),+) => { + $( + impl<$lt_tcx> PatternFoldable<$lt_tcx> for $ty { + fn super_fold_with>(&self, _: &mut F) -> Self { + Clone::clone(self) + } + } + )+ + } +} + +CloneImpls!{ <'tcx> + Span, Field, Mutability, ast::Name, ast::NodeId, usize, &'tcx ty::Const<'tcx>, + Region<'tcx>, Ty<'tcx>, BindingMode<'tcx>, &'tcx AdtDef, + &'tcx Substs<'tcx>, &'tcx Kind<'tcx> +} + +impl<'tcx> PatternFoldable<'tcx> for FieldPattern<'tcx> { + fn super_fold_with>(&self, folder: &mut F) -> Self { + FieldPattern { + field: self.field.fold_with(folder), + pattern: self.pattern.fold_with(folder) + } + } +} + +impl<'tcx> PatternFoldable<'tcx> for Pattern<'tcx> { + fn fold_with>(&self, folder: &mut F) -> Self { + folder.fold_pattern(self) + } + + fn super_fold_with>(&self, folder: &mut F) -> Self { + Pattern { + ty: self.ty.fold_with(folder), + span: self.span.fold_with(folder), + kind: self.kind.fold_with(folder) + } + } +} + +impl<'tcx> PatternFoldable<'tcx> for PatternKind<'tcx> { + fn fold_with>(&self, folder: &mut F) -> Self { + folder.fold_pattern_kind(self) + } + + fn super_fold_with>(&self, folder: &mut F) -> Self { + match *self { + PatternKind::Wild => PatternKind::Wild, + PatternKind::Binding { + mutability, + name, + mode, + var, + ty, + ref subpattern, + } => PatternKind::Binding { + mutability: mutability.fold_with(folder), + name: name.fold_with(folder), + mode: mode.fold_with(folder), + var: var.fold_with(folder), + ty: ty.fold_with(folder), + subpattern: subpattern.fold_with(folder), + }, + PatternKind::Variant { + adt_def, + substs, + variant_index, + ref subpatterns, + } => PatternKind::Variant { + adt_def: adt_def.fold_with(folder), + substs: substs.fold_with(folder), + variant_index: variant_index.fold_with(folder), + subpatterns: subpatterns.fold_with(folder) + }, + PatternKind::Leaf { + ref subpatterns, + } => PatternKind::Leaf { + subpatterns: subpatterns.fold_with(folder), + }, + PatternKind::Deref { + ref subpattern, + } => PatternKind::Deref { + subpattern: subpattern.fold_with(folder), + }, + PatternKind::Constant { + value + } => PatternKind::Constant { + value: value.fold_with(folder) + }, + PatternKind::Range { + lo, + hi, + end, + } => PatternKind::Range { + lo: lo.fold_with(folder), + hi: hi.fold_with(folder), + end, + }, + PatternKind::Slice { + ref prefix, + ref slice, + ref suffix, + } => PatternKind::Slice { + prefix: prefix.fold_with(folder), + slice: slice.fold_with(folder), + suffix: suffix.fold_with(folder) + }, + PatternKind::Array { + ref prefix, + ref slice, + ref suffix + } => PatternKind::Array { + prefix: prefix.fold_with(folder), + slice: slice.fold_with(folder), + suffix: suffix.fold_with(folder) + }, + } + } +} diff --git a/src/librustc_mir/diagnostics.rs b/src/librustc_mir/diagnostics.rs index 3491faf9cda..d71298fb1a6 100644 --- a/src/librustc_mir/diagnostics.rs +++ b/src/librustc_mir/diagnostics.rs @@ -12,6 +12,553 @@ register_long_diagnostics! { + +E0001: r##" +#### Note: this error code is no longer emitted by the compiler. + +This error suggests that the expression arm corresponding to the noted pattern +will never be reached as for all possible values of the expression being +matched, one of the preceding patterns will match. + +This means that perhaps some of the preceding patterns are too general, this +one is too specific or the ordering is incorrect. + +For example, the following `match` block has too many arms: + +``` +match Some(0) { + Some(bar) => {/* ... */} + x => {/* ... */} // This handles the `None` case + _ => {/* ... */} // All possible cases have already been handled +} +``` + +`match` blocks have their patterns matched in order, so, for example, putting +a wildcard arm above a more specific arm will make the latter arm irrelevant. + +Ensure the ordering of the match arm is correct and remove any superfluous +arms. +"##, + +E0002: r##" +#### Note: this error code is no longer emitted by the compiler. + +This error indicates that an empty match expression is invalid because the type +it is matching on is non-empty (there exist values of this type). In safe code +it is impossible to create an instance of an empty type, so empty match +expressions are almost never desired. This error is typically fixed by adding +one or more cases to the match expression. + +An example of an empty type is `enum Empty { }`. So, the following will work: + +``` +enum Empty {} + +fn foo(x: Empty) { + match x { + // empty + } +} +``` + +However, this won't: + +```compile_fail +fn foo(x: Option) { + match x { + // empty + } +} +``` +"##, + +E0003: r##" +#### Note: this error code is no longer emitted by the compiler. + +Not-a-Number (NaN) values cannot be compared for equality and hence can never +match the input to a match expression. So, the following will not compile: + +```compile_fail +const NAN: f32 = 0.0 / 0.0; + +let number = 0.1f32; + +match number { + NAN => { /* ... */ }, + _ => {} +} +``` + +To match against NaN values, you should instead use the `is_nan()` method in a +guard, like so: + +``` +let number = 0.1f32; + +match number { + x if x.is_nan() => { /* ... */ } + _ => {} +} +``` +"##, + +E0004: r##" +This error indicates that the compiler cannot guarantee a matching pattern for +one or more possible inputs to a match expression. Guaranteed matches are +required in order to assign values to match expressions, or alternatively, +determine the flow of execution. Erroneous code example: + +```compile_fail,E0004 +enum Terminator { + HastaLaVistaBaby, + TalkToMyHand, +} + +let x = Terminator::HastaLaVistaBaby; + +match x { // error: non-exhaustive patterns: `HastaLaVistaBaby` not covered + Terminator::TalkToMyHand => {} +} +``` + +If you encounter this error you must alter your patterns so that every possible +value of the input type is matched. For types with a small number of variants +(like enums) you should probably cover all cases explicitly. Alternatively, the +underscore `_` wildcard pattern can be added after all other patterns to match +"anything else". Example: + +``` +enum Terminator { + HastaLaVistaBaby, + TalkToMyHand, +} + +let x = Terminator::HastaLaVistaBaby; + +match x { + Terminator::TalkToMyHand => {} + Terminator::HastaLaVistaBaby => {} +} + +// or: + +match x { + Terminator::TalkToMyHand => {} + _ => {} +} +``` +"##, + +E0005: r##" +Patterns used to bind names must be irrefutable, that is, they must guarantee +that a name will be extracted in all cases. Erroneous code example: + +```compile_fail,E0005 +let x = Some(1); +let Some(y) = x; +// error: refutable pattern in local binding: `None` not covered +``` + +If you encounter this error you probably need to use a `match` or `if let` to +deal with the possibility of failure. Example: + +``` +let x = Some(1); + +match x { + Some(y) => { + // do something + }, + None => {} +} + +// or: + +if let Some(y) = x { + // do something +} +``` +"##, + +E0007: r##" +This error indicates that the bindings in a match arm would require a value to +be moved into more than one location, thus violating unique ownership. Code +like the following is invalid as it requires the entire `Option` to be +moved into a variable called `op_string` while simultaneously requiring the +inner `String` to be moved into a variable called `s`. + +```compile_fail,E0007 +let x = Some("s".to_string()); + +match x { + op_string @ Some(s) => {}, // error: cannot bind by-move with sub-bindings + None => {}, +} +``` + +See also the error E0303. +"##, + +E0008: r##" +Names bound in match arms retain their type in pattern guards. As such, if a +name is bound by move in a pattern, it should also be moved to wherever it is +referenced in the pattern guard code. Doing so however would prevent the name +from being available in the body of the match arm. Consider the following: + +```compile_fail,E0008 +match Some("hi".to_string()) { + Some(s) if s.len() == 0 => {}, // use s. + _ => {}, +} +``` + +The variable `s` has type `String`, and its use in the guard is as a variable of +type `String`. The guard code effectively executes in a separate scope to the +body of the arm, so the value would be moved into this anonymous scope and +therefore becomes unavailable in the body of the arm. + +The problem above can be solved by using the `ref` keyword. + +``` +match Some("hi".to_string()) { + Some(ref s) if s.len() == 0 => {}, + _ => {}, +} +``` + +Though this example seems innocuous and easy to solve, the problem becomes clear +when it encounters functions which consume the value: + +```compile_fail,E0008 +struct A{} + +impl A { + fn consume(self) -> usize { + 0 + } +} + +fn main() { + let a = Some(A{}); + match a { + Some(y) if y.consume() > 0 => {} + _ => {} + } +} +``` + +In this situation, even the `ref` keyword cannot solve it, since borrowed +content cannot be moved. This problem cannot be solved generally. If the value +can be cloned, here is a not-so-specific solution: + +``` +#[derive(Clone)] +struct A{} + +impl A { + fn consume(self) -> usize { + 0 + } +} + +fn main() { + let a = Some(A{}); + match a{ + Some(ref y) if y.clone().consume() > 0 => {} + _ => {} + } +} +``` + +If the value will be consumed in the pattern guard, using its clone will not +move its ownership, so the code works. +"##, + +E0009: r##" +In a pattern, all values that don't implement the `Copy` trait have to be bound +the same way. The goal here is to avoid binding simultaneously by-move and +by-ref. + +This limitation may be removed in a future version of Rust. + +Erroneous code example: + +```compile_fail,E0009 +struct X { x: (), } + +let x = Some((X { x: () }, X { x: () })); +match x { + Some((y, ref z)) => {}, // error: cannot bind by-move and by-ref in the + // same pattern + None => panic!() +} +``` + +You have two solutions: + +Solution #1: Bind the pattern's values the same way. + +``` +struct X { x: (), } + +let x = Some((X { x: () }, X { x: () })); +match x { + Some((ref y, ref z)) => {}, + // or Some((y, z)) => {} + None => panic!() +} +``` + +Solution #2: Implement the `Copy` trait for the `X` structure. + +However, please keep in mind that the first solution should be preferred. + +``` +#[derive(Clone, Copy)] +struct X { x: (), } + +let x = Some((X { x: () }, X { x: () })); +match x { + Some((y, ref z)) => {}, + None => panic!() +} +``` +"##, + +E0158: r##" +`const` and `static` mean different things. A `const` is a compile-time +constant, an alias for a literal value. This property means you can match it +directly within a pattern. + +The `static` keyword, on the other hand, guarantees a fixed location in memory. +This does not always mean that the value is constant. For example, a global +mutex can be declared `static` as well. + +If you want to match against a `static`, consider using a guard instead: + +``` +static FORTY_TWO: i32 = 42; + +match Some(42) { + Some(x) if x == FORTY_TWO => {} + _ => {} +} +``` +"##, + +E0162: r##" +An if-let pattern attempts to match the pattern, and enters the body if the +match was successful. If the match is irrefutable (when it cannot fail to +match), use a regular `let`-binding instead. For instance: + +```compile_fail,E0162 +struct Irrefutable(i32); +let irr = Irrefutable(0); + +// This fails to compile because the match is irrefutable. +if let Irrefutable(x) = irr { + // This body will always be executed. + // ... +} +``` + +Try this instead: + +``` +struct Irrefutable(i32); +let irr = Irrefutable(0); + +let Irrefutable(x) = irr; +println!("{}", x); +``` +"##, + +E0165: r##" +A while-let pattern attempts to match the pattern, and enters the body if the +match was successful. If the match is irrefutable (when it cannot fail to +match), use a regular `let`-binding inside a `loop` instead. For instance: + +```compile_fail,E0165 +struct Irrefutable(i32); +let irr = Irrefutable(0); + +// This fails to compile because the match is irrefutable. +while let Irrefutable(x) = irr { + // ... +} +``` + +Try this instead: + +```no_run +struct Irrefutable(i32); +let irr = Irrefutable(0); + +loop { + let Irrefutable(x) = irr; + // ... +} +``` +"##, + +E0170: r##" +Enum variants are qualified by default. For example, given this type: + +``` +enum Method { + GET, + POST, +} +``` + +You would match it using: + +``` +enum Method { + GET, + POST, +} + +let m = Method::GET; + +match m { + Method::GET => {}, + Method::POST => {}, +} +``` + +If you don't qualify the names, the code will bind new variables named "GET" and +"POST" instead. This behavior is likely not what you want, so `rustc` warns when +that happens. + +Qualified names are good practice, and most code works well with them. But if +you prefer them unqualified, you can import the variants into scope: + +``` +use Method::*; +enum Method { GET, POST } +# fn main() {} +``` + +If you want others to be able to import variants from your module directly, use +`pub use`: + +``` +pub use Method::*; +pub enum Method { GET, POST } +# fn main() {} +``` +"##, + + +E0297: r##" +#### Note: this error code is no longer emitted by the compiler. + +Patterns used to bind names must be irrefutable. That is, they must guarantee +that a name will be extracted in all cases. Instead of pattern matching the +loop variable, consider using a `match` or `if let` inside the loop body. For +instance: + +```compile_fail,E0005 +let xs : Vec> = vec![Some(1), None]; + +// This fails because `None` is not covered. +for Some(x) in xs { + // ... +} +``` + +Match inside the loop instead: + +``` +let xs : Vec> = vec![Some(1), None]; + +for item in xs { + match item { + Some(x) => {}, + None => {}, + } +} +``` + +Or use `if let`: + +``` +let xs : Vec> = vec![Some(1), None]; + +for item in xs { + if let Some(x) = item { + // ... + } +} +``` +"##, + +E0301: r##" +Mutable borrows are not allowed in pattern guards, because matching cannot have +side effects. Side effects could alter the matched object or the environment +on which the match depends in such a way, that the match would not be +exhaustive. For instance, the following would not match any arm if mutable +borrows were allowed: + +```compile_fail,E0301 +match Some(()) { + None => { }, + option if option.take().is_none() => { + /* impossible, option is `Some` */ + }, + Some(_) => { } // When the previous match failed, the option became `None`. +} +``` +"##, + +E0302: r##" +Assignments are not allowed in pattern guards, because matching cannot have +side effects. Side effects could alter the matched object or the environment +on which the match depends in such a way, that the match would not be +exhaustive. For instance, the following would not match any arm if assignments +were allowed: + +```compile_fail,E0302 +match Some(()) { + None => { }, + option if { option = None; false } => { }, + Some(_) => { } // When the previous match failed, the option became `None`. +} +``` +"##, + +E0303: r##" +In certain cases it is possible for sub-bindings to violate memory safety. +Updates to the borrow checker in a future version of Rust may remove this +restriction, but for now patterns must be rewritten without sub-bindings. + +Before: + +```compile_fail,E0303 +match Some("hi".to_string()) { + ref op_string_ref @ Some(s) => {}, + None => {}, +} +``` + +After: + +``` +match Some("hi".to_string()) { + Some(ref s) => { + let op_string_ref = &Some(s); + // ... + }, + None => {}, +} +``` + +The `op_string_ref` binding has type `&Option<&String>` in both cases. + +See also https://github.com/rust-lang/rust/issues/14587 +"##, + E0010: r##" The value of statics and constants must be known at compile time, and they live for the entire lifetime of a program. Creating a boxed value allocates memory on @@ -1771,6 +2318,9 @@ b.resume(); } register_diagnostics! { +// E0298, // cannot compare constants +// E0299, // mismatched types between arms +// E0471, // constant evaluation error (in pattern) // E0385, // {} in an aliasable location E0493, // destructors cannot be evaluated at compile-time E0524, // two closures require unique access to `..` at the same time diff --git a/src/librustc_mir/hair/mod.rs b/src/librustc_mir/hair/mod.rs index 09a31f9ab8f..329365c4415 100644 --- a/src/librustc_mir/hair/mod.rs +++ b/src/librustc_mir/hair/mod.rs @@ -27,7 +27,7 @@ use self::cx::Cx; pub mod cx; -pub use rustc_const_eval::pattern::{BindingMode, Pattern, PatternKind, FieldPattern}; +pub use const_eval::pattern::{BindingMode, Pattern, PatternKind, FieldPattern}; #[derive(Copy, Clone, Debug)] pub enum LintLevel { diff --git a/src/librustc_mir/interpret/const_eval.rs b/src/librustc_mir/interpret/const_eval.rs index ec8215fb64c..f5408c73818 100644 --- a/src/librustc_mir/interpret/const_eval.rs +++ b/src/librustc_mir/interpret/const_eval.rs @@ -5,7 +5,7 @@ use rustc::hir::def_id::DefId; use rustc::mir; use rustc::middle::const_val::ErrKind::{CheckMatchError, TypeckError}; use rustc::middle::const_val::{ConstEvalErr, ConstVal}; -use rustc_const_eval::{lookup_const_by_id, ConstContext}; +use const_eval::{lookup_const_by_id, ConstContext}; use rustc::mir::Field; use rustc_data_structures::indexed_vec::Idx; @@ -306,16 +306,19 @@ impl<'tcx> super::Machine<'tcx> for CompileTimeEvaluator { pub fn const_val_field<'a, 'tcx>( tcx: TyCtxt<'a, 'tcx, 'tcx>, - key: ty::ParamEnvAnd<'tcx, (ty::Instance<'tcx>, mir::Field, Value, Ty<'tcx>)>, + param_env: ty::ParamEnv<'tcx>, + instance: ty::Instance<'tcx>, + field: mir::Field, + val: Value, + ty: Ty<'tcx>, ) -> ::rustc::middle::const_val::EvalResult<'tcx> { - trace!("const_val_field: {:#?}", key); - match const_val_field_inner(tcx, key) { + match const_val_field_inner(tcx, param_env, instance, field, val, ty) { Ok((field, ty)) => Ok(tcx.mk_const(ty::Const { val: ConstVal::Value(field), ty, })), Err(err) => Err(ConstEvalErr { - span: tcx.def_span(key.value.0.def_id()), + span: tcx.def_span(instance.def_id()), kind: err.into(), }), } @@ -323,11 +326,14 @@ pub fn const_val_field<'a, 'tcx>( fn const_val_field_inner<'a, 'tcx>( tcx: TyCtxt<'a, 'tcx, 'tcx>, - key: ty::ParamEnvAnd<'tcx, (ty::Instance<'tcx>, mir::Field, Value, Ty<'tcx>)>, + param_env: ty::ParamEnv<'tcx>, + instance: ty::Instance<'tcx>, + field: mir::Field, + value: Value, + ty: Ty<'tcx>, ) -> ::rustc::mir::interpret::EvalResult<'tcx, (Value, Ty<'tcx>)> { - trace!("const_val_field: {:#?}", key); - let (instance, field, value, ty) = key.value; - let mut ecx = mk_eval_cx(tcx, instance, key.param_env).unwrap(); + trace!("const_val_field: {:?}, {:?}, {:?}, {:?}", instance, field, value, ty); + let mut ecx = mk_eval_cx(tcx, instance, param_env).unwrap(); let (mut field, ty) = match value { Value::ByValPair(..) | Value::ByVal(_) => ecx.read_field(value, field, ty)?.expect("const_val_field on non-field"), Value::ByRef(ptr, align) => { @@ -348,11 +354,13 @@ fn const_val_field_inner<'a, 'tcx>( pub fn const_discr<'a, 'tcx>( tcx: TyCtxt<'a, 'tcx, 'tcx>, - key: ty::ParamEnvAnd<'tcx, (ty::Instance<'tcx>, Value, Ty<'tcx>)>, + param_env: ty::ParamEnv<'tcx>, + instance: ty::Instance<'tcx>, + value: Value, + ty: Ty<'tcx>, ) -> EvalResult<'tcx, u128> { - trace!("const_discr: {:#?}", key); - let (instance, value, ty) = key.value; - let mut ecx = mk_eval_cx(tcx, instance, key.param_env).unwrap(); + trace!("const_discr: {:?}, {:?}, {:?}", instance, value, ty); + let mut ecx = mk_eval_cx(tcx, instance, param_env).unwrap(); let (ptr, align) = match value { Value::ByValPair(..) | Value::ByVal(_) => { let layout = ecx.layout_of(ty)?; diff --git a/src/librustc_mir/lib.rs b/src/librustc_mir/lib.rs index 8c15d1cf8b0..d25caa588fa 100644 --- a/src/librustc_mir/lib.rs +++ b/src/librustc_mir/lib.rs @@ -16,6 +16,8 @@ Rust MIR: a lowered representation of Rust. Also: an experiment! #![deny(warnings)] +#![feature(slice_patterns)] +#![feature(from_ref)] #![feature(box_patterns)] #![feature(box_syntax)] #![feature(catch_expr)] @@ -38,6 +40,7 @@ Rust MIR: a lowered representation of Rust. Also: an experiment! #![feature(nonzero)] #![feature(underscore_lifetimes)] +extern crate arena; #[macro_use] extern crate bitflags; #[macro_use] extern crate log; @@ -52,7 +55,6 @@ extern crate syntax; extern crate syntax_pos; extern crate rustc_back; extern crate rustc_const_math; -extern crate rustc_const_eval; extern crate core; // for NonZero extern crate log_settings; extern crate rustc_apfloat; @@ -69,6 +71,7 @@ pub mod transform; pub mod util; pub mod interpret; pub mod monomorphize; +pub mod const_eval; use rustc::ty::maps::Providers; @@ -77,6 +80,7 @@ pub fn provide(providers: &mut Providers) { shim::provide(providers); transform::provide(providers); providers.const_eval = interpret::const_eval_provider; + providers.check_match = const_eval::check_match::check_match; } __build_diagnostic_array! { librustc_mir, DIAGNOSTICS } diff --git a/src/librustc_passes/Cargo.toml b/src/librustc_passes/Cargo.toml index e87e976eac3..4bab24ae139 100644 --- a/src/librustc_passes/Cargo.toml +++ b/src/librustc_passes/Cargo.toml @@ -11,7 +11,7 @@ crate-type = ["dylib"] [dependencies] log = "0.4" rustc = { path = "../librustc" } -rustc_const_eval = { path = "../librustc_const_eval" } +rustc_mir = { path = "../librustc_mir"} rustc_const_math = { path = "../librustc_const_math" } rustc_data_structures = { path = "../librustc_data_structures" } syntax = { path = "../libsyntax" } diff --git a/src/librustc_passes/consts.rs b/src/librustc_passes/consts.rs index 8153c3c8493..420e8c4aad2 100644 --- a/src/librustc_passes/consts.rs +++ b/src/librustc_passes/consts.rs @@ -25,7 +25,7 @@ // by borrowck::gather_loans use rustc::ty::cast::CastKind; -use rustc_const_eval::ConstContext; +use rustc_mir::const_eval::ConstContext; use rustc::middle::const_val::ConstEvalErr; use rustc::middle::const_val::ErrKind::{IndexOpFeatureGated, UnimplementedConstVal, MiscCatchAll}; use rustc::middle::const_val::ErrKind::{ErroneousReferencedConstant, MiscBinaryOp, NonConstPath}; diff --git a/src/librustc_passes/lib.rs b/src/librustc_passes/lib.rs index 8bd95982887..a51bee91499 100644 --- a/src/librustc_passes/lib.rs +++ b/src/librustc_passes/lib.rs @@ -23,7 +23,7 @@ #[macro_use] extern crate rustc; -extern crate rustc_const_eval; +extern crate rustc_mir; extern crate rustc_const_math; extern crate rustc_data_structures; -- cgit 1.4.1-3-g733a5