From 816cb8c5350084e04770b9c3a133400923bd2e1b Mon Sep 17 00:00:00 2001 From: Lindsey Kuper Date: Fri, 4 Jan 2013 09:52:07 -0500 Subject: Rename identifiers that still use 'alt' to use 'match' This'll be less confusing for anyone who works on match in future. --- src/librustc/driver/driver.rs | 4 +- src/librustc/middle/borrowck/gather_loans.rs | 8 +- src/librustc/middle/borrowck/mod.rs | 4 +- src/librustc/middle/borrowck/preserve.rs | 18 +- src/librustc/middle/check_alt.rs | 848 ------------ src/librustc/middle/check_match.rs | 848 ++++++++++++ src/librustc/middle/const_eval.rs | 2 +- src/librustc/middle/mem_categorization.rs | 2 +- src/librustc/middle/region.rs | 2 +- src/librustc/middle/trans/_match.rs | 1802 ++++++++++++++++++++++++++ src/librustc/middle/trans/alt.rs | 1802 -------------------------- src/librustc/middle/trans/base.rs | 22 +- src/librustc/middle/trans/debuginfo.rs | 2 +- src/librustc/middle/trans/expr.rs | 3 +- src/librustc/middle/typeck/check/_match.rs | 582 +++++++++ src/librustc/middle/typeck/check/alt.rs | 582 --------- src/librustc/middle/typeck/check/mod.rs | 16 +- src/librustc/rustc.rc | 4 +- src/librustc/util/ppaux.rs | 2 +- src/libsyntax/ext/tt/macro_parser.rs | 2 +- src/libsyntax/parse/parser.rs | 4 +- src/libsyntax/print/pprust.rs | 12 +- 22 files changed, 3286 insertions(+), 3285 deletions(-) delete mode 100644 src/librustc/middle/check_alt.rs create mode 100644 src/librustc/middle/check_match.rs create mode 100644 src/librustc/middle/trans/_match.rs delete mode 100644 src/librustc/middle/trans/alt.rs create mode 100644 src/librustc/middle/typeck/check/_match.rs delete mode 100644 src/librustc/middle/typeck/check/alt.rs (limited to 'src') diff --git a/src/librustc/driver/driver.rs b/src/librustc/driver/driver.rs index 12573e0fc62..b5f57d904bc 100644 --- a/src/librustc/driver/driver.rs +++ b/src/librustc/driver/driver.rs @@ -275,8 +275,8 @@ fn compile_upto(sess: Session, cfg: ast::crate_cfg, time(time_passes, ~"mode computation", || middle::mode::compute_modes(ty_cx, method_map, crate)); - time(time_passes, ~"alt checking", || - middle::check_alt::check_crate(ty_cx, method_map, crate)); + time(time_passes, ~"match checking", || + middle::check_match::check_crate(ty_cx, method_map, crate)); let last_use_map = time(time_passes, ~"liveness checking", || diff --git a/src/librustc/middle/borrowck/gather_loans.rs b/src/librustc/middle/borrowck/gather_loans.rs index 9524980a1f9..d5652ae78d6 100644 --- a/src/librustc/middle/borrowck/gather_loans.rs +++ b/src/librustc/middle/borrowck/gather_loans.rs @@ -506,7 +506,7 @@ impl gather_loan_ctxt { discr_cmt: cmt, root_pat: @ast::pat, arm_id: ast::node_id, - alt_id: ast::node_id) { + match_id: ast::node_id) { do self.bccx.cat_pattern(discr_cmt, root_pat) |cmt, pat| { match pat.node { ast::pat_ident(bm, _, _) if self.pat_is_binding(pat) => { @@ -514,11 +514,11 @@ impl gather_loan_ctxt { ast::bind_by_value | ast::bind_by_move => { // copying does not borrow anything, so no check // is required - // as for move, check::alt ensures it's from an rvalue. + // as for move, check::_match ensures it's from an rvalue. } ast::bind_by_ref(mutbl) => { // ref x or ref x @ p --- creates a ptr which must - // remain valid for the scope of the alt + // remain valid for the scope of the match // find the region of the resulting pointer (note that // the type of such a pattern will *always* be a @@ -531,7 +531,7 @@ impl gather_loan_ctxt { // of the function of this node in method preserve(): let arm_scope = ty::re_scope(arm_id); if self.bccx.is_subregion_of(scope_r, arm_scope) { - let cmt_discr = self.bccx.cat_discr(cmt, alt_id); + let cmt_discr = self.bccx.cat_discr(cmt, match_id); self.guarantee_valid(cmt_discr, mutbl, scope_r); } else { self.guarantee_valid(cmt, mutbl, scope_r); diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs index 1cd88aa8197..fa7dfd1b77f 100644 --- a/src/librustc/middle/borrowck/mod.rs +++ b/src/librustc/middle/borrowck/mod.rs @@ -494,8 +494,8 @@ impl borrowck_ctxt { cat_variant(self.tcx, self.method_map, arg, enum_did, cmt) } - fn cat_discr(cmt: cmt, alt_id: ast::node_id) -> cmt { - return @{cat:cat_discr(cmt, alt_id),.. *cmt}; + fn cat_discr(cmt: cmt, match_id: ast::node_id) -> cmt { + return @{cat:cat_discr(cmt, match_id),.. *cmt}; } fn cat_pattern(cmt: cmt, pat: @ast::pat, op: fn(cmt, @ast::pat)) { diff --git a/src/librustc/middle/borrowck/preserve.rs b/src/librustc/middle/borrowck/preserve.rs index 220685e58ca..e6d311fd04f 100644 --- a/src/librustc/middle/borrowck/preserve.rs +++ b/src/librustc/middle/borrowck/preserve.rs @@ -195,15 +195,15 @@ priv impl &preserve_ctxt { self.attempt_root(cmt, base, derefs) } } - cat_discr(base, alt_id) => { - // Subtle: in an alt, we must ensure that each binding + cat_discr(base, match_id) => { + // Subtle: in a match, we must ensure that each binding // variable remains valid for the duration of the arm in // which it appears, presuming that this arm is taken. // But it is inconvenient in trans to root something just // for one arm. Therefore, we insert a cat_discr(), // basically a special kind of category that says "if this // value must be dynamically rooted, root it for the scope - // `alt_id`. + // `match_id`. // // As an example, consider this scenario: // @@ -213,7 +213,7 @@ priv impl &preserve_ctxt { // Technically, the value `x` need only be rooted // in the `some` arm. However, we evaluate `x` in trans // before we know what arm will be taken, so we just - // always root it for the duration of the alt. + // always root it for the duration of the match. // // As a second example, consider *this* scenario: // @@ -225,7 +225,7 @@ priv impl &preserve_ctxt { // found only when checking which pattern matches: but // this check is done before entering the arm. Therefore, // even in this case we just choose to keep the value - // rooted for the entire alt. This means the value will be + // rooted for the entire match. This means the value will be // rooted even if the none arm is taken. Oh well. // // At first, I tried to optimize the second case to only @@ -247,12 +247,12 @@ priv impl &preserve_ctxt { // Nonetheless, if you decide to optimize this case in the // future, you need only adjust where the cat_discr() // node appears to draw the line between what will be rooted - // in the *arm* vs the *alt*. + // in the *arm* vs the *match*. - let alt_rooting_ctxt = - preserve_ctxt({scope_region: ty::re_scope(alt_id), + let match_rooting_ctxt = + preserve_ctxt({scope_region: ty::re_scope(match_id), .. **self}); - (&alt_rooting_ctxt).preserve(base) + (&match_rooting_ctxt).preserve(base) } } } diff --git a/src/librustc/middle/check_alt.rs b/src/librustc/middle/check_alt.rs deleted file mode 100644 index bdd2b06e6ab..00000000000 --- a/src/librustc/middle/check_alt.rs +++ /dev/null @@ -1,848 +0,0 @@ -// Copyright 2012 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 middle::const_eval::{compare_const_vals, lookup_const_by_id}; -use middle::const_eval::{eval_const_expr, const_val, const_int, const_bool}; -use middle::pat_util::*; -use middle::ty::*; -use middle::ty; -use middle::typeck::method_map; -use util::ppaux::ty_to_str; - -use core::cmp; -use core::option; -use core::uint; -use core::vec; -use std::map::HashMap; -use std::sort; -use syntax::ast::*; -use syntax::ast_util::{variant_def_ids, dummy_sp, unguarded_pat, walk_pat}; -use syntax::ast_util; -use syntax::codemap::span; -use syntax::print::pprust::pat_to_str; -use syntax::visit; - -struct AltCheckCtxt { - tcx: ty::ctxt, - method_map: method_map, -} - -fn check_crate(tcx: ty::ctxt, method_map: method_map, crate: @crate) { - let cx = @AltCheckCtxt { tcx: tcx, method_map: method_map }; - visit::visit_crate(*crate, (), visit::mk_vt(@{ - visit_expr: |a,b,c| check_expr(cx, a, b, c), - visit_local: |a,b,c| check_local(cx, a, b, c), - visit_fn: |kind, decl, body, sp, id, e, v| - check_fn(cx, kind, decl, body, sp, id, e, v), - .. *visit::default_visitor::<()>() - })); - tcx.sess.abort_if_errors(); -} - -fn expr_is_non_moving_lvalue(cx: @AltCheckCtxt, expr: @expr) -> bool { - if !ty::expr_is_lval(cx.tcx, cx.method_map, expr) { - return false; - } - - match cx.tcx.value_modes.find(expr.id) { - Some(MoveValue) => return false, - Some(CopyValue) | Some(ReadValue) => return true, - None => { - cx.tcx.sess.span_bug(expr.span, ~"no entry in value mode map"); - } - } -} - -fn check_expr(cx: @AltCheckCtxt, ex: @expr, &&s: (), v: visit::vt<()>) { - visit::visit_expr(ex, s, v); - match ex.node { - expr_match(scrut, ref arms) => { - // First, check legality of move bindings. - let is_non_moving_lvalue = expr_is_non_moving_lvalue(cx, ex); - for arms.each |arm| { - check_legality_of_move_bindings(cx, - is_non_moving_lvalue, - arm.guard.is_some(), - arm.pats); - } - - check_arms(cx, (/*bad*/copy *arms)); - /* Check for exhaustiveness */ - // Check for empty enum, because is_useful only works on inhabited - // types. - let pat_ty = node_id_to_type(cx.tcx, scrut.id); - if (*arms).is_empty() { - if !type_is_empty(cx.tcx, pat_ty) { - // We know the type is inhabited, so this must be wrong - cx.tcx.sess.span_err(ex.span, fmt!("non-exhaustive patterns: \ - type %s is non-empty", - ty_to_str(cx.tcx, pat_ty))); - } - // If the type *is* empty, it's vacuously exhaustive - return; - } - match ty::get(pat_ty).sty { - ty_enum(did, _) => { - if (*enum_variants(cx.tcx, did)).is_empty() && - (*arms).is_empty() { - - return; - } - } - _ => { /* We assume only enum types can be uninhabited */ } - } - let arms = vec::concat(vec::filter_map((*arms), unguarded_pat)); - check_exhaustive(cx, ex.span, arms); - } - _ => () - } -} - -// Check for unreachable patterns -fn check_arms(cx: @AltCheckCtxt, arms: ~[arm]) { - let mut seen = ~[]; - for arms.each |arm| { - for arm.pats.each |pat| { - let v = ~[*pat]; - match is_useful(cx, seen, v) { - not_useful => { - cx.tcx.sess.span_err(pat.span, ~"unreachable pattern"); - } - _ => () - } - if arm.guard.is_none() { seen.push(v); } - } - } -} - -fn raw_pat(p: @pat) -> @pat { - match p.node { - pat_ident(_, _, Some(s)) => { raw_pat(s) } - _ => { p } - } -} - -fn check_exhaustive(cx: @AltCheckCtxt, sp: span, pats: ~[@pat]) { - assert(pats.is_not_empty()); - let ext = match is_useful(cx, vec::map(pats, |p| ~[*p]), ~[wild()]) { - not_useful => return, // This is good, wildcard pattern isn't reachable - useful_ => None, - useful(ty, ref ctor) => { - match ty::get(ty).sty { - ty::ty_bool => { - match (*ctor) { - val(const_bool(true)) => Some(~"true"), - val(const_bool(false)) => Some(~"false"), - _ => None - } - } - ty::ty_enum(id, _) => { - let vid = match (*ctor) { variant(id) => id, - _ => fail ~"check_exhaustive: non-variant ctor" }; - match vec::find(*ty::enum_variants(cx.tcx, id), - |v| v.id == vid) { - Some(v) => Some(cx.tcx.sess.str_of(v.name)), - None => fail ~"check_exhaustive: bad variant in ctor" - } - } - ty::ty_unboxed_vec(*) | ty::ty_evec(*) => { - match (*ctor) { - vec(n) => Some(fmt!("vectors of length %u", n)), - _ => None - } - } - _ => None - } - } - }; - let msg = ~"non-exhaustive patterns" + match ext { - Some(ref s) => ~": " + (*s) + ~" not covered", - None => ~"" - }; - cx.tcx.sess.span_err(sp, msg); -} - -type matrix = ~[~[@pat]]; - -enum useful { useful(ty::t, ctor), useful_, not_useful } - -enum ctor { - single, - variant(def_id), - val(const_val), - range(const_val, const_val), - vec(uint) -} - -impl ctor : cmp::Eq { - pure fn eq(&self, other: &ctor) -> bool { - match ((*self), (*other)) { - (single, single) => true, - (variant(did_self), variant(did_other)) => did_self == did_other, - (val(ref cv_self), val(ref cv_other)) => - (*cv_self) == (*cv_other), - (range(ref cv0_self, ref cv1_self), - range(ref cv0_other, ref cv1_other)) => { - (*cv0_self) == (*cv0_other) && (*cv1_self) == (*cv1_other) - } - (vec(n_self), vec(n_other)) => n_self == n_other, - (single, _) | (variant(_), _) | (val(_), _) | - (range(*), _) | (vec(*), _) => { - false - } - } - } - pure fn ne(&self, other: &ctor) -> bool { !(*self).eq(other) } -} - -// Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html -// -// Whether a vector `v` of patterns is 'useful' in relation to a set of such -// vectors `m` is defined as there being a set of inputs that will match `v` -// but not any of the sets in `m`. -// -// 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). - -// Note: is_useful doesn't work on empty types, as the paper notes. -// So it assumes that v is non-empty. -fn is_useful(cx: @AltCheckCtxt, +m: matrix, +v: ~[@pat]) -> useful { - if m.len() == 0u { return useful_; } - if m[0].len() == 0u { return not_useful; } - let real_pat = match vec::find(m, |r| r[0].id != 0) { - Some(r) => r[0], None => v[0] - }; - let left_ty = if real_pat.id == 0 { ty::mk_nil(cx.tcx) } - else { ty::node_id_to_type(cx.tcx, real_pat.id) }; - - match pat_ctor_id(cx, v[0]) { - None => { - match missing_ctor(cx, m, left_ty) { - None => { - match ty::get(left_ty).sty { - ty::ty_bool => { - match is_useful_specialized(cx, m, v, - val(const_bool(true)), - 0u, left_ty){ - not_useful => { - is_useful_specialized(cx, m, v, - val(const_bool(false)), - 0u, left_ty) - } - ref u => (/*bad*/copy *u) - } - } - ty::ty_enum(eid, _) => { - for (*ty::enum_variants(cx.tcx, eid)).each |va| { - match is_useful_specialized(cx, m, v, variant(va.id), - va.args.len(), left_ty) { - not_useful => (), - ref u => return (/*bad*/copy *u) - } - } - not_useful - } - ty::ty_unboxed_vec(*) | ty::ty_evec(*) => { - let max_len = do m.foldr(0) |r, max_len| { - match /*bad*/copy r[0].node { - pat_vec(elems, _) => uint::max(elems.len(), max_len), - _ => max_len - } - }; - for uint::range(0, max_len + 1) |n| { - match is_useful_specialized(cx, m, v, vec(n), n, left_ty) { - not_useful => (), - ref u => return (/*bad*/copy *u) - } - } - not_useful - } - _ => { - let arity = ctor_arity(cx, single, left_ty); - is_useful_specialized(cx, m, v, single, arity, left_ty) - } - } - } - Some(ref ctor) => { - match is_useful(cx, vec::filter_map(m, |r| default(cx, *r)), - vec::tail(v)) { - useful_ => useful(left_ty, (/*bad*/copy *ctor)), - ref u => (/*bad*/copy *u) - } - } - } - } - Some(ref v0_ctor) => { - let arity = ctor_arity(cx, (*v0_ctor), left_ty); - is_useful_specialized(cx, m, v, /*bad*/copy *v0_ctor, arity, left_ty) - } - } -} - -fn is_useful_specialized(cx: @AltCheckCtxt, m: matrix, +v: ~[@pat], - +ctor: ctor, arity: uint, lty: ty::t) -> useful { - let ms = vec::filter_map(m, |r| specialize(cx, *r, ctor, arity, lty)); - let could_be_useful = is_useful( - cx, ms, specialize(cx, v, ctor, arity, lty).get()); - match could_be_useful { - useful_ => useful(lty, ctor), - ref u => (/*bad*/copy *u) - } -} - -fn pat_ctor_id(cx: @AltCheckCtxt, p: @pat) -> Option { - let pat = raw_pat(p); - match /*bad*/copy pat.node { - pat_wild => { None } - pat_ident(_, _, _) | pat_enum(_, _) => { - match cx.tcx.def_map.find(pat.id) { - Some(def_variant(_, id)) => Some(variant(id)), - Some(def_const(did)) => { - let const_expr = lookup_const_by_id(cx.tcx, did).get(); - Some(val(eval_const_expr(cx.tcx, const_expr))) - } - _ => None - } - } - pat_lit(expr) => { Some(val(eval_const_expr(cx.tcx, expr))) } - pat_range(lo, hi) => { - Some(range(eval_const_expr(cx.tcx, lo), eval_const_expr(cx.tcx, hi))) - } - pat_struct(*) => { - match cx.tcx.def_map.find(pat.id) { - Some(def_variant(_, id)) => Some(variant(id)), - _ => Some(single) - } - } - pat_box(_) | pat_uniq(_) | pat_rec(_, _) | pat_tup(_) | - pat_region(*) => { - Some(single) - } - pat_vec(elems, tail) => { - match tail { - Some(_) => None, - None => Some(vec(elems.len())) - } - } - } -} - -fn is_wild(cx: @AltCheckCtxt, p: @pat) -> bool { - let pat = raw_pat(p); - match pat.node { - pat_wild => { true } - pat_ident(_, _, _) => { - match cx.tcx.def_map.find(pat.id) { - Some(def_variant(_, _)) | Some(def_const(*)) => { false } - _ => { true } - } - } - _ => { false } - } -} - -fn missing_ctor(cx: @AltCheckCtxt, - m: matrix, - left_ty: ty::t) - -> Option { - match ty::get(left_ty).sty { - ty::ty_box(_) | ty::ty_uniq(_) | ty::ty_rptr(*) | ty::ty_tup(_) | - ty::ty_rec(_) | ty::ty_struct(*) => { - for m.each |r| { - if !is_wild(cx, r[0]) { return None; } - } - return Some(single); - } - ty::ty_enum(eid, _) => { - let mut found = ~[]; - for m.each |r| { - do option::iter(&pat_ctor_id(cx, r[0])) |id| { - if !vec::contains(found, id) { - found.push(/*bad*/copy *id); - } - } - } - let variants = ty::enum_variants(cx.tcx, eid); - if found.len() != (*variants).len() { - for vec::each(*variants) |v| { - if !found.contains(&(variant(v.id))) { - return Some(variant(v.id)); - } - } - fail; - } else { None } - } - ty::ty_nil => None, - ty::ty_bool => { - let mut true_found = false, false_found = false; - for m.each |r| { - match pat_ctor_id(cx, r[0]) { - None => (), - Some(val(const_bool(true))) => true_found = true, - Some(val(const_bool(false))) => false_found = true, - _ => fail ~"impossible case" - } - } - if true_found && false_found { None } - else if true_found { Some(val(const_bool(false))) } - else { Some(val(const_bool(true))) } - } - ty::ty_unboxed_vec(*) | ty::ty_evec(*) => { - - // Find the lengths and tails of all vector patterns. - let vec_pat_lens = do m.filter_map |r| { - match /*bad*/copy r[0].node { - pat_vec(elems, tail) => { - Some((elems.len(), tail.is_some())) - } - _ => None - } - }; - - // Sort them by length such that for patterns of the same length, - // those with a destructured tail come first. - let mut sorted_vec_lens = sort::merge_sort(vec_pat_lens, - |&(len1, tail1), &(len2, tail2)| { - if len1 == len2 { - tail1 > tail2 - } else { - len1 <= len2 - } - } - ); - vec::dedup(&mut sorted_vec_lens); - - let mut found_tail = false; - let mut next = 0; - let mut missing = None; - for sorted_vec_lens.each |&(length, tail)| { - if length != next { - missing = Some(next); - break; - } - if tail { - found_tail = true; - break; - } - next += 1; - } - - // We found patterns of all lengths within <0, next), yet there was no - // pattern with a tail - therefore, we report vec(next) as missing. - if !found_tail { - missing = Some(next); - } - match missing { - Some(k) => Some(vec(k)), - None => None - } - } - _ => Some(single) - } -} - -fn ctor_arity(cx: @AltCheckCtxt, ctor: ctor, ty: ty::t) -> uint { - match /*bad*/copy ty::get(ty).sty { - ty::ty_tup(fs) => fs.len(), - ty::ty_rec(fs) => fs.len(), - ty::ty_box(_) | ty::ty_uniq(_) | ty::ty_rptr(*) => 1u, - ty::ty_enum(eid, _) => { - let id = match ctor { variant(id) => id, - _ => fail ~"impossible case" }; - match vec::find(*ty::enum_variants(cx.tcx, eid), |v| v.id == id ) { - Some(v) => v.args.len(), - None => fail ~"impossible case" - } - } - ty::ty_struct(cid, _) => ty::lookup_struct_fields(cx.tcx, cid).len(), - ty::ty_unboxed_vec(*) | ty::ty_evec(*) => { - match ctor { - vec(n) => n, - _ => 0u - } - } - _ => 0u - } -} - -fn wild() -> @pat { - @{id: 0, node: pat_wild, span: ast_util::dummy_sp()} -} - -fn specialize(cx: @AltCheckCtxt, r: ~[@pat], ctor_id: ctor, arity: uint, - left_ty: ty::t) -> Option<~[@pat]> { - let r0 = raw_pat(r[0]); - match /*bad*/copy r0.node { - pat_wild => Some(vec::append(vec::from_elem(arity, wild()), - vec::tail(r))), - pat_ident(_, _, _) => { - match cx.tcx.def_map.find(r0.id) { - Some(def_variant(_, id)) => { - if variant(id) == ctor_id { Some(vec::tail(r)) } - else { None } - } - Some(def_const(did)) => { - let const_expr = lookup_const_by_id(cx.tcx, did).get(); - let e_v = eval_const_expr(cx.tcx, const_expr); - let match_ = match ctor_id { - val(ref v) => compare_const_vals(e_v, (*v)) == 0, - range(ref c_lo, ref c_hi) => { - compare_const_vals((*c_lo), e_v) >= 0 && - compare_const_vals((*c_hi), e_v) <= 0 - } - single => true, - _ => fail ~"type error" - }; - if match_ { Some(vec::tail(r)) } else { None } - } - _ => Some(vec::append(vec::from_elem(arity, wild()), vec::tail(r))) - } - } - pat_enum(_, args) => { - match cx.tcx.def_map.get(r0.id) { - def_variant(_, id) if variant(id) == ctor_id => { - let args = match args { - Some(args) => args, - None => vec::from_elem(arity, wild()) - }; - Some(vec::append(args, vec::tail(r))) - } - def_variant(_, _) => None, - def_struct(*) => { - // XXX: Is this right? --pcw - let new_args; - match args { - Some(args) => new_args = args, - None => new_args = vec::from_elem(arity, wild()) - } - Some(vec::append(new_args, vec::tail(r))) - } - _ => None - } - } - pat_rec(flds, _) => { - let ty_flds = match /*bad*/copy ty::get(left_ty).sty { - ty::ty_rec(flds) => flds, - _ => fail ~"bad type for pat_rec" - }; - let args = vec::map(ty_flds, |ty_fld| { - match vec::find(flds, |f| f.ident == ty_fld.ident ) { - Some(f) => f.pat, - _ => wild() - } - }); - Some(vec::append(args, vec::tail(r))) - } - pat_struct(_, flds, _) => { - // Is this a struct or an enum variant? - match cx.tcx.def_map.get(r0.id) { - def_variant(_, variant_id) => { - if variant(variant_id) == ctor_id { - // XXX: Is this right? --pcw - let args = flds.map(|ty_field| { - match vec::find(flds, |f| f.ident == ty_field.ident) { - Some(f) => f.pat, - _ => wild() - } - }); - Some(vec::append(args, vec::tail(r))) - } else { - None - } - } - _ => { - // Grab the class data that we care about. - let class_fields, class_id; - match ty::get(left_ty).sty { - ty::ty_struct(cid, _) => { - class_id = cid; - class_fields = ty::lookup_struct_fields(cx.tcx, - class_id); - } - _ => { - cx.tcx.sess.span_bug(r0.span, ~"struct pattern \ - didn't resolve to a \ - struct"); - } - } - let args = vec::map(class_fields, |class_field| { - match vec::find(flds, |f| f.ident == class_field.ident ) { - Some(f) => f.pat, - _ => wild() - } - }); - Some(vec::append(args, vec::tail(r))) - } - } - } - pat_tup(args) => Some(vec::append(args, vec::tail(r))), - pat_box(a) | pat_uniq(a) | pat_region(a) => - Some(vec::append(~[a], vec::tail(r))), - pat_lit(expr) => { - let e_v = eval_const_expr(cx.tcx, expr); - let match_ = match ctor_id { - val(ref v) => compare_const_vals(e_v, (*v)) == 0, - range(ref c_lo, ref c_hi) => { - compare_const_vals((*c_lo), e_v) >= 0 && - compare_const_vals((*c_hi), e_v) <= 0 - } - single => true, - _ => fail ~"type error" - }; - if match_ { Some(vec::tail(r)) } else { None } - } - pat_range(lo, hi) => { - let (c_lo, c_hi) = match ctor_id { - val(ref v) => ((/*bad*/copy *v), (/*bad*/copy *v)), - range(ref lo, ref hi) => ((/*bad*/copy *lo), (/*bad*/copy *hi)), - single => return Some(vec::tail(r)), - _ => fail ~"type error" - }; - let v_lo = eval_const_expr(cx.tcx, lo), - v_hi = eval_const_expr(cx.tcx, hi); - let match_ = compare_const_vals(c_lo, v_lo) >= 0 && - compare_const_vals(c_hi, v_hi) <= 0; - if match_ { Some(vec::tail(r)) } else { None } - } - pat_vec(elems, tail) => { - match ctor_id { - vec(_) => { - if elems.len() < arity && tail.is_some() { - // XXX: Bad copy. - Some(vec::append( - vec::append(copy elems, vec::from_elem( - arity - elems.len(), wild() - )), - vec::tail(r) - )) - } else if elems.len() == arity { - Some(vec::append(elems, vec::tail(r))) - } else { - None - } - } - _ => None - } - } - } -} - -fn default(cx: @AltCheckCtxt, r: ~[@pat]) -> Option<~[@pat]> { - if is_wild(cx, r[0]) { Some(vec::tail(r)) } - else { None } -} - -fn check_local(cx: @AltCheckCtxt, loc: @local, &&s: (), v: visit::vt<()>) { - visit::visit_local(loc, s, v); - if is_refutable(cx, loc.node.pat) { - cx.tcx.sess.span_err(loc.node.pat.span, - ~"refutable pattern in local binding"); - } - - // Check legality of move bindings. - let is_lvalue = match loc.node.init { - Some(init) => expr_is_non_moving_lvalue(cx, init), - None => true - }; - check_legality_of_move_bindings(cx, is_lvalue, false, [ loc.node.pat ]); -} - -fn check_fn(cx: @AltCheckCtxt, - kind: visit::fn_kind, - decl: fn_decl, - body: blk, - sp: span, - id: node_id, - &&s: (), - v: visit::vt<()>) { - visit::visit_fn(kind, decl, body, sp, id, s, v); - for decl.inputs.each |input| { - if is_refutable(cx, input.pat) { - cx.tcx.sess.span_err(input.pat.span, - ~"refutable pattern in function argument"); - } - } -} - -fn is_refutable(cx: @AltCheckCtxt, pat: &pat) -> bool { - match cx.tcx.def_map.find(pat.id) { - Some(def_variant(enum_id, _)) => { - if vec::len(*ty::enum_variants(cx.tcx, enum_id)) != 1u { - return true; - } - } - Some(def_const(*)) => return true, - _ => () - } - - match /*bad*/copy pat.node { - pat_box(sub) | pat_uniq(sub) | pat_region(sub) | - pat_ident(_, _, Some(sub)) => { - is_refutable(cx, sub) - } - pat_wild | pat_ident(_, _, None) => { false } - pat_lit(@{node: expr_lit(@{node: lit_nil, _}), _}) => { false } // "()" - pat_lit(_) | pat_range(_, _) => { true } - pat_rec(fields, _) => { - fields.any(|f| is_refutable(cx, f.pat)) - } - pat_struct(_, fields, _) => { - fields.any(|f| is_refutable(cx, f.pat)) - } - pat_tup(elts) => { - elts.any(|elt| is_refutable(cx, *elt)) - } - pat_enum(_, Some(args)) => { - args.any(|a| is_refutable(cx, *a)) - } - pat_enum(_,_) => { false } - pat_vec(*) => { true } - } -} - -// Legality of move bindings checking - -fn check_legality_of_move_bindings(cx: @AltCheckCtxt, - is_lvalue: bool, - has_guard: bool, - pats: &[@pat]) { - let tcx = cx.tcx; - let def_map = tcx.def_map; - let mut by_ref_span = None; - let mut any_by_move = false; - for pats.each |pat| { - do pat_bindings(def_map, *pat) |bm, id, span, _path| { - match bm { - bind_by_ref(_) => { - by_ref_span = Some(span); - } - bind_by_move => { - any_by_move = true; - } - bind_by_value => {} - bind_infer => { - match cx.tcx.value_modes.find(id) { - Some(MoveValue) => any_by_move = true, - Some(CopyValue) | Some(ReadValue) => {} - None => { - cx.tcx.sess.span_bug(span, ~"no mode for pat \ - binding"); - } - } - } - } - } - } - - let check_move: &fn(@pat, Option<@pat>) = |p, sub| { - // check legality of moving out of the enum - if sub.is_some() { - tcx.sess.span_err( - p.span, - ~"cannot bind by-move with sub-bindings"); - } else if has_guard { - tcx.sess.span_err( - p.span, - ~"cannot bind by-move into a pattern guard"); - } else if by_ref_span.is_some() { - tcx.sess.span_err( - p.span, - ~"cannot bind by-move and by-ref \ - in the same pattern"); - tcx.sess.span_note( - by_ref_span.get(), - ~"by-ref binding occurs here"); - } else if is_lvalue { - tcx.sess.span_err( - p.span, - ~"cannot bind by-move when \ - matching an lvalue"); - } - }; - - if !any_by_move { return; } // pointless micro-optimization - for pats.each |pat| { - do walk_pat(*pat) |p| { - if pat_is_binding(def_map, p) { - match p.node { - pat_ident(bind_by_move, _, sub) => check_move(p, sub), - pat_ident(bind_infer, _, sub) => { - match tcx.value_modes.find(p.id) { - Some(MoveValue) => check_move(p, sub), - Some(CopyValue) | Some(ReadValue) => {} - None => { - cx.tcx.sess.span_bug( - pat.span, ~"no mode for pat binding"); - } - } - } - _ => {} - } - } - } - - // Now check to ensure that any move binding is not behind an @ or &. - // This is always illegal. - let vt = visit::mk_vt(@{ - visit_pat: |pat, behind_bad_pointer, v| { - let error_out = || { - cx.tcx.sess.span_err(pat.span, ~"by-move pattern \ - bindings may not occur \ - behind @ or & bindings"); - }; - match pat.node { - pat_ident(binding_mode, _, sub) => { - debug!("(check legality of move) checking pat \ - ident with behind_bad_pointer %?", - behind_bad_pointer); - match binding_mode { - bind_by_move if behind_bad_pointer => error_out(), - bind_infer if behind_bad_pointer => { - match cx.tcx.value_modes.find(pat.id) { - Some(MoveValue) => error_out(), - Some(CopyValue) | - Some(ReadValue) => {} - None => { - cx.tcx.sess.span_bug(pat.span, - ~"no mode for pat binding"); - } - } - } - _ => {} - } - match sub { - None => {} - Some(subpat) => { - (v.visit_pat)(subpat, behind_bad_pointer, v); - } - } - } - pat_box(subpat) | pat_region(subpat) => { - (v.visit_pat)(subpat, true, v); - } - _ => visit::visit_pat(pat, behind_bad_pointer, v) - } - }, - .. *visit::default_visitor::() - }); - (vt.visit_pat)(*pat, false, vt); - } -} - -// Local Variables: -// mode: rust -// fill-column: 78; -// indent-tabs-mode: nil -// c-basic-offset: 4 -// buffer-file-coding-system: utf-8-unix -// End: diff --git a/src/librustc/middle/check_match.rs b/src/librustc/middle/check_match.rs new file mode 100644 index 00000000000..dc66df93624 --- /dev/null +++ b/src/librustc/middle/check_match.rs @@ -0,0 +1,848 @@ +// Copyright 2012 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 middle::const_eval::{compare_const_vals, lookup_const_by_id}; +use middle::const_eval::{eval_const_expr, const_val, const_int, const_bool}; +use middle::pat_util::*; +use middle::ty::*; +use middle::ty; +use middle::typeck::method_map; +use util::ppaux::ty_to_str; + +use core::cmp; +use core::option; +use core::uint; +use core::vec; +use std::map::HashMap; +use std::sort; +use syntax::ast::*; +use syntax::ast_util::{variant_def_ids, dummy_sp, unguarded_pat, walk_pat}; +use syntax::ast_util; +use syntax::codemap::span; +use syntax::print::pprust::pat_to_str; +use syntax::visit; + +struct MatchCheckCtxt { + tcx: ty::ctxt, + method_map: method_map, +} + +fn check_crate(tcx: ty::ctxt, method_map: method_map, crate: @crate) { + let cx = @MatchCheckCtxt { tcx: tcx, method_map: method_map }; + visit::visit_crate(*crate, (), visit::mk_vt(@{ + visit_expr: |a,b,c| check_expr(cx, a, b, c), + visit_local: |a,b,c| check_local(cx, a, b, c), + visit_fn: |kind, decl, body, sp, id, e, v| + check_fn(cx, kind, decl, body, sp, id, e, v), + .. *visit::default_visitor::<()>() + })); + tcx.sess.abort_if_errors(); +} + +fn expr_is_non_moving_lvalue(cx: @MatchCheckCtxt, expr: @expr) -> bool { + if !ty::expr_is_lval(cx.tcx, cx.method_map, expr) { + return false; + } + + match cx.tcx.value_modes.find(expr.id) { + Some(MoveValue) => return false, + Some(CopyValue) | Some(ReadValue) => return true, + None => { + cx.tcx.sess.span_bug(expr.span, ~"no entry in value mode map"); + } + } +} + +fn check_expr(cx: @MatchCheckCtxt, ex: @expr, &&s: (), v: visit::vt<()>) { + visit::visit_expr(ex, s, v); + match ex.node { + expr_match(scrut, ref arms) => { + // First, check legality of move bindings. + let is_non_moving_lvalue = expr_is_non_moving_lvalue(cx, ex); + for arms.each |arm| { + check_legality_of_move_bindings(cx, + is_non_moving_lvalue, + arm.guard.is_some(), + arm.pats); + } + + check_arms(cx, (/*bad*/copy *arms)); + /* Check for exhaustiveness */ + // Check for empty enum, because is_useful only works on inhabited + // types. + let pat_ty = node_id_to_type(cx.tcx, scrut.id); + if (*arms).is_empty() { + if !type_is_empty(cx.tcx, pat_ty) { + // We know the type is inhabited, so this must be wrong + cx.tcx.sess.span_err(ex.span, fmt!("non-exhaustive patterns: \ + type %s is non-empty", + ty_to_str(cx.tcx, pat_ty))); + } + // If the type *is* empty, it's vacuously exhaustive + return; + } + match ty::get(pat_ty).sty { + ty_enum(did, _) => { + if (*enum_variants(cx.tcx, did)).is_empty() && + (*arms).is_empty() { + + return; + } + } + _ => { /* We assume only enum types can be uninhabited */ } + } + let arms = vec::concat(vec::filter_map((*arms), unguarded_pat)); + check_exhaustive(cx, ex.span, arms); + } + _ => () + } +} + +// Check for unreachable patterns +fn check_arms(cx: @MatchCheckCtxt, arms: ~[arm]) { + let mut seen = ~[]; + for arms.each |arm| { + for arm.pats.each |pat| { + let v = ~[*pat]; + match is_useful(cx, seen, v) { + not_useful => { + cx.tcx.sess.span_err(pat.span, ~"unreachable pattern"); + } + _ => () + } + if arm.guard.is_none() { seen.push(v); } + } + } +} + +fn raw_pat(p: @pat) -> @pat { + match p.node { + pat_ident(_, _, Some(s)) => { raw_pat(s) } + _ => { p } + } +} + +fn check_exhaustive(cx: @MatchCheckCtxt, sp: span, pats: ~[@pat]) { + assert(pats.is_not_empty()); + let ext = match is_useful(cx, vec::map(pats, |p| ~[*p]), ~[wild()]) { + not_useful => return, // This is good, wildcard pattern isn't reachable + useful_ => None, + useful(ty, ref ctor) => { + match ty::get(ty).sty { + ty::ty_bool => { + match (*ctor) { + val(const_bool(true)) => Some(~"true"), + val(const_bool(false)) => Some(~"false"), + _ => None + } + } + ty::ty_enum(id, _) => { + let vid = match (*ctor) { variant(id) => id, + _ => fail ~"check_exhaustive: non-variant ctor" }; + match vec::find(*ty::enum_variants(cx.tcx, id), + |v| v.id == vid) { + Some(v) => Some(cx.tcx.sess.str_of(v.name)), + None => fail ~"check_exhaustive: bad variant in ctor" + } + } + ty::ty_unboxed_vec(*) | ty::ty_evec(*) => { + match (*ctor) { + vec(n) => Some(fmt!("vectors of length %u", n)), + _ => None + } + } + _ => None + } + } + }; + let msg = ~"non-exhaustive patterns" + match ext { + Some(ref s) => ~": " + (*s) + ~" not covered", + None => ~"" + }; + cx.tcx.sess.span_err(sp, msg); +} + +type matrix = ~[~[@pat]]; + +enum useful { useful(ty::t, ctor), useful_, not_useful } + +enum ctor { + single, + variant(def_id), + val(const_val), + range(const_val, const_val), + vec(uint) +} + +impl ctor : cmp::Eq { + pure fn eq(&self, other: &ctor) -> bool { + match ((*self), (*other)) { + (single, single) => true, + (variant(did_self), variant(did_other)) => did_self == did_other, + (val(ref cv_self), val(ref cv_other)) => + (*cv_self) == (*cv_other), + (range(ref cv0_self, ref cv1_self), + range(ref cv0_other, ref cv1_other)) => { + (*cv0_self) == (*cv0_other) && (*cv1_self) == (*cv1_other) + } + (vec(n_self), vec(n_other)) => n_self == n_other, + (single, _) | (variant(_), _) | (val(_), _) | + (range(*), _) | (vec(*), _) => { + false + } + } + } + pure fn ne(&self, other: &ctor) -> bool { !(*self).eq(other) } +} + +// Algorithm from http://moscova.inria.fr/~maranget/papers/warn/index.html +// +// Whether a vector `v` of patterns is 'useful' in relation to a set of such +// vectors `m` is defined as there being a set of inputs that will match `v` +// but not any of the sets in `m`. +// +// 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). + +// Note: is_useful doesn't work on empty types, as the paper notes. +// So it assumes that v is non-empty. +fn is_useful(cx: @MatchCheckCtxt, +m: matrix, +v: ~[@pat]) -> useful { + if m.len() == 0u { return useful_; } + if m[0].len() == 0u { return not_useful; } + let real_pat = match vec::find(m, |r| r[0].id != 0) { + Some(r) => r[0], None => v[0] + }; + let left_ty = if real_pat.id == 0 { ty::mk_nil(cx.tcx) } + else { ty::node_id_to_type(cx.tcx, real_pat.id) }; + + match pat_ctor_id(cx, v[0]) { + None => { + match missing_ctor(cx, m, left_ty) { + None => { + match ty::get(left_ty).sty { + ty::ty_bool => { + match is_useful_specialized(cx, m, v, + val(const_bool(true)), + 0u, left_ty){ + not_useful => { + is_useful_specialized(cx, m, v, + val(const_bool(false)), + 0u, left_ty) + } + ref u => (/*bad*/copy *u) + } + } + ty::ty_enum(eid, _) => { + for (*ty::enum_variants(cx.tcx, eid)).each |va| { + match is_useful_specialized(cx, m, v, variant(va.id), + va.args.len(), left_ty) { + not_useful => (), + ref u => return (/*bad*/copy *u) + } + } + not_useful + } + ty::ty_unboxed_vec(*) | ty::ty_evec(*) => { + let max_len = do m.foldr(0) |r, max_len| { + match /*bad*/copy r[0].node { + pat_vec(elems, _) => uint::max(elems.len(), max_len), + _ => max_len + } + }; + for uint::range(0, max_len + 1) |n| { + match is_useful_specialized(cx, m, v, vec(n), n, left_ty) { + not_useful => (), + ref u => return (/*bad*/copy *u) + } + } + not_useful + } + _ => { + let arity = ctor_arity(cx, single, left_ty); + is_useful_specialized(cx, m, v, single, arity, left_ty) + } + } + } + Some(ref ctor) => { + match is_useful(cx, vec::filter_map(m, |r| default(cx, *r)), + vec::tail(v)) { + useful_ => useful(left_ty, (/*bad*/copy *ctor)), + ref u => (/*bad*/copy *u) + } + } + } + } + Some(ref v0_ctor) => { + let arity = ctor_arity(cx, (*v0_ctor), left_ty); + is_useful_specialized(cx, m, v, /*bad*/copy *v0_ctor, arity, left_ty) + } + } +} + +fn is_useful_specialized(cx: @MatchCheckCtxt, m: matrix, +v: ~[@pat], + +ctor: ctor, arity: uint, lty: ty::t) -> useful { + let ms = vec::filter_map(m, |r| specialize(cx, *r, ctor, arity, lty)); + let could_be_useful = is_useful( + cx, ms, specialize(cx, v, ctor, arity, lty).get()); + match could_be_useful { + useful_ => useful(lty, ctor), + ref u => (/*bad*/copy *u) + } +} + +fn pat_ctor_id(cx: @MatchCheckCtxt, p: @pat) -> Option { + let pat = raw_pat(p); + match /*bad*/copy pat.node { + pat_wild => { None } + pat_ident(_, _, _) | pat_enum(_, _) => { + match cx.tcx.def_map.find(pat.id) { + Some(def_variant(_, id)) => Some(variant(id)), + Some(def_const(did)) => { + let const_expr = lookup_const_by_id(cx.tcx, did).get(); + Some(val(eval_const_expr(cx.tcx, const_expr))) + } + _ => None + } + } + pat_lit(expr) => { Some(val(eval_const_expr(cx.tcx, expr))) } + pat_range(lo, hi) => { + Some(range(eval_const_expr(cx.tcx, lo), eval_const_expr(cx.tcx, hi))) + } + pat_struct(*) => { + match cx.tcx.def_map.find(pat.id) { + Some(def_variant(_, id)) => Some(variant(id)), + _ => Some(single) + } + } + pat_box(_) | pat_uniq(_) | pat_rec(_, _) | pat_tup(_) | + pat_region(*) => { + Some(single) + } + pat_vec(elems, tail) => { + match tail { + Some(_) => None, + None => Some(vec(elems.len())) + } + } + } +} + +fn is_wild(cx: @MatchCheckCtxt, p: @pat) -> bool { + let pat = raw_pat(p); + match pat.node { + pat_wild => { true } + pat_ident(_, _, _) => { + match cx.tcx.def_map.find(pat.id) { + Some(def_variant(_, _)) | Some(def_const(*)) => { false } + _ => { true } + } + } + _ => { false } + } +} + +fn missing_ctor(cx: @MatchCheckCtxt, + m: matrix, + left_ty: ty::t) + -> Option { + match ty::get(left_ty).sty { + ty::ty_box(_) | ty::ty_uniq(_) | ty::ty_rptr(*) | ty::ty_tup(_) | + ty::ty_rec(_) | ty::ty_struct(*) => { + for m.each |r| { + if !is_wild(cx, r[0]) { return None; } + } + return Some(single); + } + ty::ty_enum(eid, _) => { + let mut found = ~[]; + for m.each |r| { + do option::iter(&pat_ctor_id(cx, r[0])) |id| { + if !vec::contains(found, id) { + found.push(/*bad*/copy *id); + } + } + } + let variants = ty::enum_variants(cx.tcx, eid); + if found.len() != (*variants).len() { + for vec::each(*variants) |v| { + if !found.contains(&(variant(v.id))) { + return Some(variant(v.id)); + } + } + fail; + } else { None } + } + ty::ty_nil => None, + ty::ty_bool => { + let mut true_found = false, false_found = false; + for m.each |r| { + match pat_ctor_id(cx, r[0]) { + None => (), + Some(val(const_bool(true))) => true_found = true, + Some(val(const_bool(false))) => false_found = true, + _ => fail ~"impossible case" + } + } + if true_found && false_found { None } + else if true_found { Some(val(const_bool(false))) } + else { Some(val(const_bool(true))) } + } + ty::ty_unboxed_vec(*) | ty::ty_evec(*) => { + + // Find the lengths and tails of all vector patterns. + let vec_pat_lens = do m.filter_map |r| { + match /*bad*/copy r[0].node { + pat_vec(elems, tail) => { + Some((elems.len(), tail.is_some())) + } + _ => None + } + }; + + // Sort them by length such that for patterns of the same length, + // those with a destructured tail come first. + let mut sorted_vec_lens = sort::merge_sort(vec_pat_lens, + |&(len1, tail1), &(len2, tail2)| { + if len1 == len2 { + tail1 > tail2 + } else { + len1 <= len2 + } + } + ); + vec::dedup(&mut sorted_vec_lens); + + let mut found_tail = false; + let mut next = 0; + let mut missing = None; + for sorted_vec_lens.each |&(length, tail)| { + if length != next { + missing = Some(next); + break; + } + if tail { + found_tail = true; + break; + } + next += 1; + } + + // We found patterns of all lengths within <0, next), yet there was no + // pattern with a tail - therefore, we report vec(next) as missing. + if !found_tail { + missing = Some(next); + } + match missing { + Some(k) => Some(vec(k)), + None => None + } + } + _ => Some(single) + } +} + +fn ctor_arity(cx: @MatchCheckCtxt, ctor: ctor, ty: ty::t) -> uint { + match /*bad*/copy ty::get(ty).sty { + ty::ty_tup(fs) => fs.len(), + ty::ty_rec(fs) => fs.len(), + ty::ty_box(_) | ty::ty_uniq(_) | ty::ty_rptr(*) => 1u, + ty::ty_enum(eid, _) => { + let id = match ctor { variant(id) => id, + _ => fail ~"impossible case" }; + match vec::find(*ty::enum_variants(cx.tcx, eid), |v| v.id == id ) { + Some(v) => v.args.len(), + None => fail ~"impossible case" + } + } + ty::ty_struct(cid, _) => ty::lookup_struct_fields(cx.tcx, cid).len(), + ty::ty_unboxed_vec(*) | ty::ty_evec(*) => { + match ctor { + vec(n) => n, + _ => 0u + } + } + _ => 0u + } +} + +fn wild() -> @pat { + @{id: 0, node: pat_wild, span: ast_util::dummy_sp()} +} + +fn specialize(cx: @MatchCheckCtxt, r: ~[@pat], ctor_id: ctor, arity: uint, + left_ty: ty::t) -> Option<~[@pat]> { + let r0 = raw_pat(r[0]); + match /*bad*/copy r0.node { + pat_wild => Some(vec::append(vec::from_elem(arity, wild()), + vec::tail(r))), + pat_ident(_, _, _) => { + match cx.tcx.def_map.find(r0.id) { + Some(def_variant(_, id)) => { + if variant(id) == ctor_id { Some(vec::tail(r)) } + else { None } + } + Some(def_const(did)) => { + let const_expr = lookup_const_by_id(cx.tcx, did).get(); + let e_v = eval_const_expr(cx.tcx, const_expr); + let match_ = match ctor_id { + val(ref v) => compare_const_vals(e_v, (*v)) == 0, + range(ref c_lo, ref c_hi) => { + compare_const_vals((*c_lo), e_v) >= 0 && + compare_const_vals((*c_hi), e_v) <= 0 + } + single => true, + _ => fail ~"type error" + }; + if match_ { Some(vec::tail(r)) } else { None } + } + _ => Some(vec::append(vec::from_elem(arity, wild()), vec::tail(r))) + } + } + pat_enum(_, args) => { + match cx.tcx.def_map.get(r0.id) { + def_variant(_, id) if variant(id) == ctor_id => { + let args = match args { + Some(args) => args, + None => vec::from_elem(arity, wild()) + }; + Some(vec::append(args, vec::tail(r))) + } + def_variant(_, _) => None, + def_struct(*) => { + // XXX: Is this right? --pcw + let new_args; + match args { + Some(args) => new_args = args, + None => new_args = vec::from_elem(arity, wild()) + } + Some(vec::append(new_args, vec::tail(r))) + } + _ => None + } + } + pat_rec(flds, _) => { + let ty_flds = match /*bad*/copy ty::get(left_ty).sty { + ty::ty_rec(flds) => flds, + _ => fail ~"bad type for pat_rec" + }; + let args = vec::map(ty_flds, |ty_fld| { + match vec::find(flds, |f| f.ident == ty_fld.ident ) { + Some(f) => f.pat, + _ => wild() + } + }); + Some(vec::append(args, vec::tail(r))) + } + pat_struct(_, flds, _) => { + // Is this a struct or an enum variant? + match cx.tcx.def_map.get(r0.id) { + def_variant(_, variant_id) => { + if variant(variant_id) == ctor_id { + // XXX: Is this right? --pcw + let args = flds.map(|ty_field| { + match vec::find(flds, |f| f.ident == ty_field.ident) { + Some(f) => f.pat, + _ => wild() + } + }); + Some(vec::append(args, vec::tail(r))) + } else { + None + } + } + _ => { + // Grab the class data that we care about. + let class_fields, class_id; + match ty::get(left_ty).sty { + ty::ty_struct(cid, _) => { + class_id = cid; + class_fields = ty::lookup_struct_fields(cx.tcx, + class_id); + } + _ => { + cx.tcx.sess.span_bug(r0.span, ~"struct pattern \ + didn't resolve to a \ + struct"); + } + } + let args = vec::map(class_fields, |class_field| { + match vec::find(flds, |f| f.ident == class_field.ident ) { + Some(f) => f.pat, + _ => wild() + } + }); + Some(vec::append(args, vec::tail(r))) + } + } + } + pat_tup(args) => Some(vec::append(args, vec::tail(r))), + pat_box(a) | pat_uniq(a) | pat_region(a) => + Some(vec::append(~[a], vec::tail(r))), + pat_lit(expr) => { + let e_v = eval_const_expr(cx.tcx, expr); + let match_ = match ctor_id { + val(ref v) => compare_const_vals(e_v, (*v)) == 0, + range(ref c_lo, ref c_hi) => { + compare_const_vals((*c_lo), e_v) >= 0 && + compare_const_vals((*c_hi), e_v) <= 0 + } + single => true, + _ => fail ~"type error" + }; + if match_ { Some(vec::tail(r)) } else { None } + } + pat_range(lo, hi) => { + let (c_lo, c_hi) = match ctor_id { + val(ref v) => ((/*bad*/copy *v), (/*bad*/copy *v)), + range(ref lo, ref hi) => ((/*bad*/copy *lo), (/*bad*/copy *hi)), + single => return Some(vec::tail(r)), + _ => fail ~"type error" + }; + let v_lo = eval_const_expr(cx.tcx, lo), + v_hi = eval_const_expr(cx.tcx, hi); + let match_ = compare_const_vals(c_lo, v_lo) >= 0 && + compare_const_vals(c_hi, v_hi) <= 0; + if match_ { Some(vec::tail(r)) } else { None } + } + pat_vec(elems, tail) => { + match ctor_id { + vec(_) => { + if elems.len() < arity && tail.is_some() { + // XXX: Bad copy. + Some(vec::append( + vec::append(copy elems, vec::from_elem( + arity - elems.len(), wild() + )), + vec::tail(r) + )) + } else if elems.len() == arity { + Some(vec::append(elems, vec::tail(r))) + } else { + None + } + } + _ => None + } + } + } +} + +fn default(cx: @MatchCheckCtxt, r: ~[@pat]) -> Option<~[@pat]> { + if is_wild(cx, r[0]) { Some(vec::tail(r)) } + else { None } +} + +fn check_local(cx: @MatchCheckCtxt, loc: @local, &&s: (), v: visit::vt<()>) { + visit::visit_local(loc, s, v); + if is_refutable(cx, loc.node.pat) { + cx.tcx.sess.span_err(loc.node.pat.span, + ~"refutable pattern in local binding"); + } + + // Check legality of move bindings. + let is_lvalue = match loc.node.init { + Some(init) => expr_is_non_moving_lvalue(cx, init), + None => true + }; + check_legality_of_move_bindings(cx, is_lvalue, false, [ loc.node.pat ]); +} + +fn check_fn(cx: @MatchCheckCtxt, + kind: visit::fn_kind, + decl: fn_decl, + body: blk, + sp: span, + id: node_id, + &&s: (), + v: visit::vt<()>) { + visit::visit_fn(kind, decl, body, sp, id, s, v); + for decl.inputs.each |input| { + if is_refutable(cx, input.pat) { + cx.tcx.sess.span_err(input.pat.span, + ~"refutable pattern in function argument"); + } + } +} + +fn is_refutable(cx: @MatchCheckCtxt, pat: &pat) -> bool { + match cx.tcx.def_map.find(pat.id) { + Some(def_variant(enum_id, _)) => { + if vec::len(*ty::enum_variants(cx.tcx, enum_id)) != 1u { + return true; + } + } + Some(def_const(*)) => return true, + _ => () + } + + match /*bad*/copy pat.node { + pat_box(sub) | pat_uniq(sub) | pat_region(sub) | + pat_ident(_, _, Some(sub)) => { + is_refutable(cx, sub) + } + pat_wild | pat_ident(_, _, None) => { false } + pat_lit(@{node: expr_lit(@{node: lit_nil, _}), _}) => { false } // "()" + pat_lit(_) | pat_range(_, _) => { true } + pat_rec(fields, _) => { + fields.any(|f| is_refutable(cx, f.pat)) + } + pat_struct(_, fields, _) => { + fields.any(|f| is_refutable(cx, f.pat)) + } + pat_tup(elts) => { + elts.any(|elt| is_refutable(cx, *elt)) + } + pat_enum(_, Some(args)) => { + args.any(|a| is_refutable(cx, *a)) + } + pat_enum(_,_) => { false } + pat_vec(*) => { true } + } +} + +// Legality of move bindings checking + +fn check_legality_of_move_bindings(cx: @MatchCheckCtxt, + is_lvalue: bool, + has_guard: bool, + pats: &[@pat]) { + let tcx = cx.tcx; + let def_map = tcx.def_map; + let mut by_ref_span = None; + let mut any_by_move = false; + for pats.each |pat| { + do pat_bindings(def_map, *pat) |bm, id, span, _path| { + match bm { + bind_by_ref(_) => { + by_ref_span = Some(span); + } + bind_by_move => { + any_by_move = true; + } + bind_by_value => {} + bind_infer => { + match cx.tcx.value_modes.find(id) { + Some(MoveValue) => any_by_move = true, + Some(CopyValue) | Some(ReadValue) => {} + None => { + cx.tcx.sess.span_bug(span, ~"no mode for pat \ + binding"); + } + } + } + } + } + } + + let check_move: &fn(@pat, Option<@pat>) = |p, sub| { + // check legality of moving out of the enum + if sub.is_some() { + tcx.sess.span_err( + p.span, + ~"cannot bind by-move with sub-bindings"); + } else if has_guard { + tcx.sess.span_err( + p.span, + ~"cannot bind by-move into a pattern guard"); + } else if by_ref_span.is_some() { + tcx.sess.span_err( + p.span, + ~"cannot bind by-move and by-ref \ + in the same pattern"); + tcx.sess.span_note( + by_ref_span.get(), + ~"by-ref binding occurs here"); + } else if is_lvalue { + tcx.sess.span_err( + p.span, + ~"cannot bind by-move when \ + matching an lvalue"); + } + }; + + if !any_by_move { return; } // pointless micro-optimization + for pats.each |pat| { + do walk_pat(*pat) |p| { + if pat_is_binding(def_map, p) { + match p.node { + pat_ident(bind_by_move, _, sub) => check_move(p, sub), + pat_ident(bind_infer, _, sub) => { + match tcx.value_modes.find(p.id) { + Some(MoveValue) => check_move(p, sub), + Some(CopyValue) | Some(ReadValue) => {} + None => { + cx.tcx.sess.span_bug( + pat.span, ~"no mode for pat binding"); + } + } + } + _ => {} + } + } + } + + // Now check to ensure that any move binding is not behind an @ or &. + // This is always illegal. + let vt = visit::mk_vt(@{ + visit_pat: |pat, behind_bad_pointer, v| { + let error_out = || { + cx.tcx.sess.span_err(pat.span, ~"by-move pattern \ + bindings may not occur \ + behind @ or & bindings"); + }; + match pat.node { + pat_ident(binding_mode, _, sub) => { + debug!("(check legality of move) checking pat \ + ident with behind_bad_pointer %?", + behind_bad_pointer); + match binding_mode { + bind_by_move if behind_bad_pointer => error_out(), + bind_infer if behind_bad_pointer => { + match cx.tcx.value_modes.find(pat.id) { + Some(MoveValue) => error_out(), + Some(CopyValue) | + Some(ReadValue) => {} + None => { + cx.tcx.sess.span_bug(pat.span, + ~"no mode for pat binding"); + } + } + } + _ => {} + } + match sub { + None => {} + Some(subpat) => { + (v.visit_pat)(subpat, behind_bad_pointer, v); + } + } + } + pat_box(subpat) | pat_region(subpat) => { + (v.visit_pat)(subpat, true, v); + } + _ => visit::visit_pat(pat, behind_bad_pointer, v) + } + }, + .. *visit::default_visitor::() + }); + (vt.visit_pat)(*pat, false, vt); + } +} + +// Local Variables: +// mode: rust +// fill-column: 78; +// indent-tabs-mode: nil +// c-basic-offset: 4 +// buffer-file-coding-system: utf-8-unix +// End: diff --git a/src/librustc/middle/const_eval.rs b/src/librustc/middle/const_eval.rs index dbde060c6f5..e2de186ca2f 100644 --- a/src/librustc/middle/const_eval.rs +++ b/src/librustc/middle/const_eval.rs @@ -46,7 +46,7 @@ use syntax::ast::*; // & and * pointers // copies of general constants // -// (in theory, probably not at first: if/alt on integer-const +// (in theory, probably not at first: if/match on integer-const // conditions / descriminants) // // - Non-constants: everything else. diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs index 1bbdc699377..9b373ef0c16 100644 --- a/src/librustc/middle/mem_categorization.rs +++ b/src/librustc/middle/mem_categorization.rs @@ -904,7 +904,7 @@ impl &mem_categorization_ctxt { // local(x)->@->@ // // where the id of `local(x)` is the id of the `x` that appears - // in the alt, the id of `local(x)->@` is the `@y` pattern, + // in the match, the id of `local(x)->@` is the `@y` pattern, // and the id of `local(x)->@->@` is the id of the `y` pattern. diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs index 3a263347536..6f9c3070a0e 100644 --- a/src/librustc/middle/region.rs +++ b/src/librustc/middle/region.rs @@ -71,7 +71,7 @@ struct ctxt { // that when we visit it we can view it as a parent. root_exprs: HashMap, - // The parent scope is the innermost block, statement, call, or alt + // The parent scope is the innermost block, statement, call, or match // expression during the execution of which the current expression // will be evaluated. Generally speaking, the innermost parent // scope is also the closest suitable ancestor in the AST tree. diff --git a/src/librustc/middle/trans/_match.rs b/src/librustc/middle/trans/_match.rs new file mode 100644 index 00000000000..97331021560 --- /dev/null +++ b/src/librustc/middle/trans/_match.rs @@ -0,0 +1,1802 @@ +// Copyright 2012 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. + +/*! + * + * # Compilation of match statements + * + * I will endeavor to explain the code as best I can. I have only a loose + * understanding of some parts of it. + * + * ## Matching + * + * The basic state of the code is maintained in an array `m` of `@Match` + * objects. Each `@Match` describes some list of patterns, all of which must + * match against the current list of values. If those patterns match, then + * the arm listed in the match is the correct arm. A given arm may have + * multiple corresponding match entries, one for each alternative that + * remains. As we proceed these sets of matches are adjusted by the various + * `enter_XXX()` functions, each of which adjusts the set of options given + * some information about the value which has been matched. + * + * So, initially, there is one value and N matches, each of which have one + * constituent pattern. N here is usually the number of arms but may be + * greater, if some arms have multiple alternatives. For example, here: + * + * enum Foo { A, B(int), C(uint, uint) } + * match foo { + * A => ..., + * B(x) => ..., + * C(1u, 2) => ..., + * C(_) => ... + * } + * + * The value would be `foo`. There would be four matches, each of which + * contains one pattern (and, in one case, a guard). We could collect the + * various options and then compile the code for the case where `foo` is an + * `A`, a `B`, and a `C`. When we generate the code for `C`, we would (1) + * drop the two matches that do not match a `C` and (2) expand the other two + * into two patterns each. In the first case, the two patterns would be `1u` + * and `2`, and the in the second case the _ pattern would be expanded into + * `_` and `_`. The two values are of course the arguments to `C`. + * + * Here is a quick guide to the various functions: + * + * - `compile_submatch()`: The main workhouse. It takes a list of values and + * a list of matches and finds the various possibilities that could occur. + * + * - `enter_XXX()`: modifies the list of matches based on some information + * about the value that has been matched. For example, + * `enter_rec_or_struct()` adjusts the values given that a record or struct + * has been matched. This is an infallible pattern, so *all* of the matches + * must be either wildcards or record/struct patterns. `enter_opt()` + * handles the fallible cases, and it is correspondingly more complex. + * + * ## Bindings + * + * We store information about the bound variables for each arm as part of the + * per-arm `ArmData` struct. There is a mapping from identifiers to + * `BindingInfo` structs. These structs contain the mode/id/type of the + * binding, but they also contain up to two LLVM values, called `llmatch` and + * `llbinding` respectively (the `llbinding`, as will be described shortly, is + * optional and only present for by-value bindings---therefore it is bundled + * up as part of the `TransBindingMode` type). Both point at allocas. + * + * The `llmatch` binding always stores a pointer into the value being matched + * which points at the data for the binding. If the value being matched has + * type `T`, then, `llmatch` will point at an alloca of type `T*` (and hence + * `llmatch` has type `T**`). So, if you have a pattern like: + * + * let a: A = ...; + * let b: B = ...; + * match (a, b) { (ref c, copy d) => { ... } } + * + * For `c` and `d`, we would generate allocas of type `C*` and `D*` + * respectively. These are called the `llmatch`. As we match, when we come + * up against an identifier, we store the current pointer into the + * corresponding alloca. + * + * In addition, for each by-value binding (copy or move), we will create a + * second alloca (`llbinding`) that will hold the final value. In this + * example, that means that `d` would have this second alloca of type `D` (and + * hence `llbinding` has type `D*`). + * + * Once a pattern is completely matched, and assuming that there is no guard + * pattern, we will branch to a block that leads to the body itself. For any + * by-value bindings, this block will first load the ptr from `llmatch` (the + * one of type `D*`) and copy/move the value into `llbinding` (the one of type + * `D`). The second alloca then becomes the value of the local variable. For + * by ref bindings, the value of the local variable is simply the first + * alloca. + * + * So, for the example above, we would generate a setup kind of like this: + * + * +-------+ + * | Entry | + * +-------+ + * | + * +-------------------------------------------+ + * | llmatch_c = (addr of first half of tuple) | + * | llmatch_d = (addr of first half of tuple) | + * +-------------------------------------------+ + * | + * +--------------------------------------+ + * | *llbinding_d = **llmatch_dlbinding_d | + * +--------------------------------------+ + * + * If there is a guard, the situation is slightly different, because we must + * execute the guard code. Moreover, we need to do so once for each of the + * alternatives that lead to the arm, because if the guard fails, they may + * have different points from which to continue the search. Therefore, in that + * case, we generate code that looks more like: + * + * +-------+ + * | Entry | + * +-------+ + * | + * +-------------------------------------------+ + * | llmatch_c = (addr of first half of tuple) | + * | llmatch_d = (addr of first half of tuple) | + * +-------------------------------------------+ + * | + * +-------------------------------------------------+ + * | *llbinding_d = **llmatch_dlbinding_d | + * | check condition | + * | if false { free *llbinding_d, goto next case } | + * | if true { goto body } | + * +-------------------------------------------------+ + * + * The handling for the cleanups is a bit... sensitive. Basically, the body + * is the one that invokes `add_clean()` for each binding. During the guard + * evaluation, we add temporary cleanups and revoke them after the guard is + * evaluated (it could fail, after all). Presuming the guard fails, we drop + * the various values we copied explicitly. Note that guards and moves are + * just plain incompatible. + * + */ + + +use back::abi; +use lib::llvm::llvm; +use lib::llvm::{ValueRef, BasicBlockRef}; +use middle::const_eval; +use middle::pat_util::*; +use middle::resolve::DefMap; +use middle::trans::base::*; +use middle::trans::build::*; +use middle::trans::callee; +use middle::trans::common::*; +use middle::trans::consts; +use middle::trans::controlflow; +use middle::trans::datum::*; +use middle::trans::expr::Dest; +use middle::trans::expr; +use middle::trans::glue; +use middle::ty::{CopyValue, MoveValue, ReadValue}; +use util::common::indenter; + +use core::dvec::DVec; +use core::dvec; +use std::map::HashMap; +use syntax::ast::def_id; +use syntax::ast; +use syntax::ast_util::{dummy_sp, path_to_ident}; +use syntax::ast_util; +use syntax::codemap::span; +use syntax::print::pprust::pat_to_str; + +fn macros() { include!("macros.rs"); } // FIXME(#3114): Macro import/export. + +// An option identifying a literal: either a unit-like struct or an +// expression. +enum Lit { + UnitLikeStructLit(ast::node_id), // the node ID of the pattern + ExprLit(@ast::expr), + ConstLit(ast::def_id), // the def ID of the constant +} + +// An option identifying a branch (either a literal, a enum variant or a +// range) +enum Opt { + lit(Lit), + var(/* disr val */int, /* variant dids */{enm: def_id, var: def_id}), + range(@ast::expr, @ast::expr), + vec_len_eq(uint), + vec_len_ge(uint) +} + +fn opt_eq(tcx: ty::ctxt, a: &Opt, b: &Opt) -> bool { + match (*a, *b) { + (lit(a), lit(b)) => { + match (a, b) { + (UnitLikeStructLit(a), UnitLikeStructLit(b)) => a == b, + _ => { + let a_expr; + match a { + ExprLit(existing_a_expr) => a_expr = existing_a_expr, + ConstLit(a_const) => { + let e = const_eval::lookup_const_by_id(tcx, a_const); + a_expr = e.get(); + } + UnitLikeStructLit(_) => { + fail ~"UnitLikeStructLit should have been handled \ + above" + } + } + + let b_expr; + match b { + ExprLit(existing_b_expr) => b_expr = existing_b_expr, + ConstLit(b_const) => { + let e = const_eval::lookup_const_by_id(tcx, b_const); + b_expr = e.get(); + } + UnitLikeStructLit(_) => { + fail ~"UnitLikeStructLit should have been handled \ + above" + } + } + + const_eval::compare_lit_exprs(tcx, a_expr, b_expr) == 0 + } + } + } + (range(a1, a2), range(b1, b2)) => { + const_eval::compare_lit_exprs(tcx, a1, b1) == 0 && + const_eval::compare_lit_exprs(tcx, a2, b2) == 0 + } + (var(a, _), var(b, _)) => a == b, + (vec_len_eq(a), vec_len_eq(b)) => a == b, + (vec_len_ge(a), vec_len_ge(b)) => a == b, + _ => false + } +} + +enum opt_result { + single_result(Result), + lower_bound(Result), + range_result(Result, Result), +} +fn trans_opt(bcx: block, o: &Opt) -> opt_result { + let _icx = bcx.insn_ctxt("match::trans_opt"); + let ccx = bcx.ccx(); + let mut bcx = bcx; + match *o { + lit(ExprLit(lit_expr)) => { + let datumblock = expr::trans_to_datum(bcx, lit_expr); + return single_result(datumblock.to_result()); + } + lit(UnitLikeStructLit(pat_id)) => { + let struct_ty = ty::node_id_to_type(bcx.tcx(), pat_id); + let datumblock = datum::scratch_datum(bcx, struct_ty, true); + return single_result(datumblock.to_result(bcx)); + } + lit(ConstLit(lit_id)) => { + let llval = consts::get_const_val(bcx.ccx(), lit_id); + return single_result(rslt(bcx, llval)); + } + var(disr_val, _) => { + return single_result(rslt(bcx, C_int(ccx, disr_val))); + } + range(l1, l2) => { + return range_result(rslt(bcx, consts::const_expr(ccx, l1)), + rslt(bcx, consts::const_expr(ccx, l2))); + } + vec_len_eq(n) => { + return single_result(rslt(bcx, C_int(ccx, n as int))); + } + vec_len_ge(n) => { + return lower_bound(rslt(bcx, C_int(ccx, n as int))); + } + } +} + +fn variant_opt(tcx: ty::ctxt, pat_id: ast::node_id) -> Opt { + match tcx.def_map.get(pat_id) { + ast::def_variant(enum_id, var_id) => { + let variants = ty::enum_variants(tcx, enum_id); + for vec::each(*variants) |v| { + if var_id == v.id { + return var(v.disr_val, {enm: enum_id, var: var_id}); + } + } + ::core::util::unreachable(); + } + ast::def_struct(_) => { + return lit(UnitLikeStructLit(pat_id)); + } + _ => { + tcx.sess.bug(~"non-variant or struct in variant_opt()"); + } + } +} + +enum TransBindingMode { + TrByValue(/*ismove:*/ bool, /*llbinding:*/ ValueRef), + TrByRef, + TrByImplicitRef +} + +/** + * Information about a pattern binding: + * - `llmatch` is a pointer to a stack slot. The stack slot contains a + * pointer into the value being matched. Hence, llmatch has type `T**` + * where `T` is the value being matched. + * - `trmode` is the trans binding mode + * - `id` is the node id of the binding + * - `ty` is the Rust type of the binding */ +struct BindingInfo { + llmatch: ValueRef, + trmode: TransBindingMode, + id: ast::node_id, + ty: ty::t, +} + +type BindingsMap = HashMap; + +struct ArmData { + bodycx: block, + arm: &ast::arm, + bindings_map: BindingsMap +} + +struct Match { + pats: ~[@ast::pat], + data: @ArmData +} + +fn match_to_str(bcx: block, m: &Match) -> ~str { + if bcx.sess().verbose() { + // for many programs, this just take too long to serialize + fmt!("%?", m.pats.map(|p| pat_to_str(*p, bcx.sess().intr()))) + } else { + fmt!("%u pats", m.pats.len()) + } +} + +fn matches_to_str(bcx: block, m: &[@Match]) -> ~str { + fmt!("%?", m.map(|n| match_to_str(bcx, *n))) +} + +fn has_nested_bindings(m: &[@Match], col: uint) -> bool { + for vec::each(m) |br| { + match br.pats[col].node { + ast::pat_ident(_, _, Some(_)) => return true, + _ => () + } + } + return false; +} + +fn expand_nested_bindings(bcx: block, m: &[@Match/&r], + col: uint, val: ValueRef) + -> ~[@Match/&r] +{ + debug!("expand_nested_bindings(bcx=%s, m=%s, col=%u, val=%?)", + bcx.to_str(), + matches_to_str(bcx, m), + col, + bcx.val_str(val)); + let _indenter = indenter(); + + do m.map |br| { + match br.pats[col].node { + ast::pat_ident(_, path, Some(inner)) => { + let pats = vec::append( + vec::slice(br.pats, 0u, col), + vec::append(~[inner], + vec::view(br.pats, col + 1u, br.pats.len()))); + + let binding_info = + br.data.bindings_map.get(path_to_ident(path)); + + Store(bcx, val, binding_info.llmatch); + @Match {pats: pats, data: br.data} + } + _ => { + *br + } + } + } +} + +type enter_pat = fn(@ast::pat) -> Option<~[@ast::pat]>; + +fn assert_is_binding_or_wild(bcx: block, p: @ast::pat) { + if !pat_is_binding_or_wild(bcx.tcx().def_map, p) { + bcx.sess().span_bug( + p.span, + fmt!("Expected an identifier pattern but found p: %s", + pat_to_str(p, bcx.sess().intr()))); + } +} + +fn enter_match(bcx: block, dm: DefMap, m: &[@Match/&r], + col: uint, val: ValueRef, e: enter_pat) + -> ~[@Match/&r] +{ + debug!("enter_match(bcx=%s, m=%s, col=%u, val=%?)", + bcx.to_str(), + matches_to_str(bcx, m), + col, + bcx.val_str(val)); + let _indenter = indenter(); + + let mut result = ~[]; + for vec::each(m) |br| { + match e(br.pats[col]) { + Some(sub) => { + let pats = + vec::append( + vec::append(sub, vec::view(br.pats, 0u, col)), + vec::view(br.pats, col + 1u, br.pats.len())); + + let self = br.pats[col]; + match self.node { + ast::pat_ident(_, path, None) => { + if pat_is_binding(dm, self) { + let binding_info = + br.data.bindings_map.get(path_to_ident(path)); + Store(bcx, val, binding_info.llmatch); + } + } + _ => {} + } + + result.push(@Match {pats: pats, data: br.data}); + } + None => () + } + } + + debug!("result=%s", matches_to_str(bcx, result)); + + return result; +} + +fn enter_default(bcx: block, dm: DefMap, m: &[@Match/&r], + col: uint, val: ValueRef) + -> ~[@Match/&r] +{ + debug!("enter_default(bcx=%s, m=%s, col=%u, val=%?)", + bcx.to_str(), + matches_to_str(bcx, m), + col, + bcx.val_str(val)); + let _indenter = indenter(); + + do enter_match(bcx, dm, m, col, val) |p| { + match p.node { + ast::pat_wild | ast::pat_rec(_, _) | ast::pat_tup(_) | + ast::pat_struct(*) => Some(~[]), + ast::pat_ident(_, _, None) if pat_is_binding(dm, p) => Some(~[]), + _ => None + } + } +} + +// nmatsakis: what does enter_opt do? +// in trans/match +// trans/match.rs is like stumbling around in a dark cave +// pcwalton: the enter family of functions adjust the set of +// patterns as needed +// yeah, at some point I kind of achieved some level of +// understanding +// anyhow, they adjust the patterns given that something of that +// kind has been found +// pcwalton: ok, right, so enter_XXX() adjusts the patterns, as I +// said +// enter_match() kind of embodies the generic code +// it is provided with a function that tests each pattern to see +// if it might possibly apply and so forth +// so, if you have a pattern like {a: _, b: _, _} and one like _ +// then _ would be expanded to (_, _) +// one spot for each of the sub-patterns +// enter_opt() is one of the more complex; it covers the fallible +// cases +// enter_rec_or_struct() or enter_tuple() are simpler, since they +// are infallible patterns +// so all patterns must either be records (resp. tuples) or +// wildcards + +fn enter_opt(bcx: block, m: &[@Match/&r], opt: &Opt, col: uint, + variant_size: uint, val: ValueRef) + -> ~[@Match/&r] +{ + debug!("enter_opt(bcx=%s, m=%s, col=%u, val=%?)", + bcx.to_str(), + matches_to_str(bcx, m), + col, + bcx.val_str(val)); + let _indenter = indenter(); + + let tcx = bcx.tcx(); + let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; + do enter_match(bcx, tcx.def_map, m, col, val) |p| { + match /*bad*/copy p.node { + ast::pat_enum(_, subpats) => { + if opt_eq(tcx, &variant_opt(tcx, p.id), opt) { + Some(option::get_or_default(subpats, + vec::from_elem(variant_size, + dummy))) + } else { + None + } + } + ast::pat_ident(_, _, None) + if pat_is_variant_or_struct(tcx.def_map, p) => { + if opt_eq(tcx, &variant_opt(tcx, p.id), opt) { + Some(~[]) + } else { + None + } + } + ast::pat_ident(_, _, None) if pat_is_const(tcx.def_map, p) => { + let const_def = tcx.def_map.get(p.id); + let const_def_id = ast_util::def_id_of_def(const_def); + if opt_eq(tcx, &lit(ConstLit(const_def_id)), opt) { + Some(~[]) + } else { + None + } + } + ast::pat_lit(l) => { + if opt_eq(tcx, &lit(ExprLit(l)), opt) {Some(~[])} else {None} + } + ast::pat_range(l1, l2) => { + if opt_eq(tcx, &range(l1, l2), opt) {Some(~[])} else {None} + } + ast::pat_struct(_, field_pats, _) => { + if opt_eq(tcx, &variant_opt(tcx, p.id), opt) { + // Look up the struct variant ID. + let struct_id; + match tcx.def_map.get(p.id) { + ast::def_variant(_, found_struct_id) => { + struct_id = found_struct_id; + } + _ => { + tcx.sess.span_bug(p.span, ~"expected enum \ + variant def"); + } + } + + // Reorder the patterns into the same order they were + // specified in the struct definition. Also fill in + // unspecified fields with dummy. + let reordered_patterns = dvec::DVec(); + for ty::lookup_struct_fields(tcx, struct_id).each + |field| { + match field_pats.find(|p| + p.ident == field.ident) { + None => reordered_patterns.push(dummy), + Some(fp) => reordered_patterns.push(fp.pat) + } + } + Some(dvec::unwrap(move reordered_patterns)) + } else { + None + } + } + ast::pat_vec(elems, tail) => { + match tail { + Some(_) => { + if opt_eq(tcx, &vec_len_ge(elems.len()), opt) { + Some(vec::append_one(elems, tail.get())) + } else { + None + } + } + None => { + if opt_eq(tcx, &vec_len_eq(elems.len()), opt) { + Some(copy elems) + } else { + None + } + } + } + } + _ => { + assert_is_binding_or_wild(bcx, p); + Some(vec::from_elem(variant_size, dummy)) + } + } + } +} + +fn enter_rec_or_struct(bcx: block, dm: DefMap, m: &[@Match/&r], col: uint, + fields: ~[ast::ident], val: ValueRef) -> ~[@Match/&r] { + debug!("enter_rec_or_struct(bcx=%s, m=%s, col=%u, val=%?)", + bcx.to_str(), + matches_to_str(bcx, m), + col, + bcx.val_str(val)); + let _indenter = indenter(); + + let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; + do enter_match(bcx, dm, m, col, val) |p| { + match /*bad*/copy p.node { + ast::pat_rec(fpats, _) | ast::pat_struct(_, fpats, _) => { + let mut pats = ~[]; + for vec::each(fields) |fname| { + match fpats.find(|p| p.ident == *fname) { + None => pats.push(dummy), + Some(pat) => pats.push(pat.pat) + } + } + Some(pats) + } + _ => { + assert_is_binding_or_wild(bcx, p); + Some(vec::from_elem(fields.len(), dummy)) + } + } + } +} + +fn enter_tup(bcx: block, dm: DefMap, m: &[@Match/&r], + col: uint, val: ValueRef, n_elts: uint) + -> ~[@Match/&r] +{ + debug!("enter_tup(bcx=%s, m=%s, col=%u, val=%?)", + bcx.to_str(), + matches_to_str(bcx, m), + col, + bcx.val_str(val)); + let _indenter = indenter(); + + let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; + do enter_match(bcx, dm, m, col, val) |p| { + match /*bad*/copy p.node { + ast::pat_tup(elts) => { + Some(elts) + } + _ => { + assert_is_binding_or_wild(bcx, p); + Some(vec::from_elem(n_elts, dummy)) + } + } + } +} + +fn enter_tuple_struct(bcx: block, dm: DefMap, m: &[@Match/&r], col: uint, + val: ValueRef, n_elts: uint) + -> ~[@Match/&r] +{ + debug!("enter_tuple_struct(bcx=%s, m=%s, col=%u, val=%?)", + bcx.to_str(), + matches_to_str(bcx, m), + col, + bcx.val_str(val)); + let _indenter = indenter(); + + let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; + do enter_match(bcx, dm, m, col, val) |p| { + match /*bad*/copy p.node { + ast::pat_enum(_, Some(elts)) => Some(elts), + _ => { + assert_is_binding_or_wild(bcx, p); + Some(vec::from_elem(n_elts, dummy)) + } + } + } +} + +fn enter_box(bcx: block, dm: DefMap, m: &[@Match/&r], + col: uint, val: ValueRef) + -> ~[@Match/&r] +{ + debug!("enter_box(bcx=%s, m=%s, col=%u, val=%?)", + bcx.to_str(), + matches_to_str(bcx, m), + col, + bcx.val_str(val)); + let _indenter = indenter(); + + let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; + do enter_match(bcx, dm, m, col, val) |p| { + match p.node { + ast::pat_box(sub) => { + Some(~[sub]) + } + _ => { + assert_is_binding_or_wild(bcx, p); + Some(~[dummy]) + } + } + } +} + +fn enter_uniq(bcx: block, dm: DefMap, m: &[@Match/&r], + col: uint, val: ValueRef) + -> ~[@Match/&r] +{ + debug!("enter_uniq(bcx=%s, m=%s, col=%u, val=%?)", + bcx.to_str(), + matches_to_str(bcx, m), + col, + bcx.val_str(val)); + let _indenter = indenter(); + + let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; + do enter_match(bcx, dm, m, col, val) |p| { + match p.node { + ast::pat_uniq(sub) => { + Some(~[sub]) + } + _ => { + assert_is_binding_or_wild(bcx, p); + Some(~[dummy]) + } + } + } +} + +fn enter_region(bcx: block, dm: DefMap, m: &[@Match/&r], + col: uint, val: ValueRef) + -> ~[@Match/&r] +{ + debug!("enter_region(bcx=%s, m=%s, col=%u, val=%?)", + bcx.to_str(), + matches_to_str(bcx, m), + col, + bcx.val_str(val)); + let _indenter = indenter(); + + let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; + do enter_match(bcx, dm, m, col, val) |p| { + match p.node { + ast::pat_region(sub) => { + Some(~[sub]) + } + _ => { + assert_is_binding_or_wild(bcx, p); + Some(~[dummy]) + } + } + } +} + +// Returns the options in one column of matches. An option is something that +// needs to be conditionally matched at runtime; for example, the discriminant +// on a set of enum variants or a literal. +fn get_options(ccx: @crate_ctxt, m: &[@Match], col: uint) -> ~[Opt] { + fn add_to_set(tcx: ty::ctxt, set: &DVec, val: Opt) { + if set.any(|l| opt_eq(tcx, l, &val)) {return;} + set.push(val); + } + + let found = DVec(); + for vec::each(m) |br| { + let cur = br.pats[col]; + match /*bad*/copy cur.node { + ast::pat_lit(l) => { + add_to_set(ccx.tcx, &found, lit(ExprLit(l))); + } + ast::pat_ident(*) => { + // This is one of: an enum variant, a unit-like struct, or a + // variable binding. + match ccx.tcx.def_map.find(cur.id) { + Some(ast::def_variant(*)) => { + add_to_set(ccx.tcx, &found, + variant_opt(ccx.tcx, cur.id)); + } + Some(ast::def_struct(*)) => { + add_to_set(ccx.tcx, &found, + lit(UnitLikeStructLit(cur.id))); + } + Some(ast::def_const(const_did)) => { + add_to_set(ccx.tcx, &found, + lit(ConstLit(const_did))); + } + _ => {} + } + } + ast::pat_enum(*) | ast::pat_struct(*) => { + // This could be one of: a tuple-like enum variant, a + // struct-like enum variant, or a struct. + match ccx.tcx.def_map.find(cur.id) { + Some(ast::def_variant(*)) => { + add_to_set(ccx.tcx, &found, + variant_opt(ccx.tcx, cur.id)); + } + _ => {} + } + } + ast::pat_range(l1, l2) => { + add_to_set(ccx.tcx, &found, range(l1, l2)); + } + ast::pat_vec(elems, tail) => { + let opt = match tail { + None => vec_len_eq(elems.len()), + Some(_) => vec_len_ge(elems.len()) + }; + add_to_set(ccx.tcx, &found, opt); + } + _ => {} + } + } + return dvec::unwrap(move found); +} + +fn extract_variant_args(bcx: block, pat_id: ast::node_id, + vdefs: {enm: def_id, var: def_id}, + val: ValueRef) + -> {vals: ~[ValueRef], bcx: block} +{ + let _icx = bcx.insn_ctxt("match::extract_variant_args"); + let ccx = bcx.fcx.ccx; + let enum_ty_substs = match ty::get(node_id_type(bcx, pat_id)).sty { + ty::ty_enum(id, ref substs) => { + assert id == vdefs.enm; + /*bad*/copy (*substs).tps + } + _ => bcx.sess().bug(~"extract_variant_args: pattern has non-enum type") + }; + let mut blobptr = val; + let variants = ty::enum_variants(ccx.tcx, vdefs.enm); + let size = ty::enum_variant_with_id(ccx.tcx, vdefs.enm, + vdefs.var).args.len(); + if size > 0u && (*variants).len() != 1u { + let enumptr = + PointerCast(bcx, val, T_opaque_enum_ptr(ccx)); + blobptr = GEPi(bcx, enumptr, [0u, 1u]); + } + let vdefs_tg = vdefs.enm; + let vdefs_var = vdefs.var; + let args = do vec::from_fn(size) |i| { + GEP_enum(bcx, blobptr, vdefs_tg, vdefs_var, + /*bad*/copy enum_ty_substs, i) + }; + return {vals: args, bcx: bcx}; +} + +fn extract_vec_elems(bcx: block, pat_id: ast::node_id, + elem_count: uint, tail: bool, val: ValueRef) + -> {vals: ~[ValueRef], bcx: block} +{ + let _icx = bcx.insn_ctxt("match::extract_vec_elems"); + let vt = tvec::vec_types(bcx, node_id_type(bcx, pat_id)); + let unboxed = load_if_immediate(bcx, val, vt.vec_ty); + let (base, len) = tvec::get_base_and_len(bcx, unboxed, vt.vec_ty); + + let mut elems = do vec::from_fn(elem_count) |i| { + GEPi(bcx, base, ~[i]) + }; + if tail { + let tail_offset = Mul(bcx, vt.llunit_size, + C_int(bcx.ccx(), elem_count as int) + ); + let tail_begin = tvec::pointer_add(bcx, base, tail_offset); + let tail_len = Sub(bcx, len, tail_offset); + let tail_ty = ty::mk_evec(bcx.tcx(), + {ty: vt.unit_ty, mutbl: ast::m_imm}, + ty::vstore_slice(ty::re_static) + ); + let scratch = scratch_datum(bcx, tail_ty, false); + Store(bcx, tail_begin, + GEPi(bcx, scratch.val, [0u, abi::slice_elt_base]) + ); + Store(bcx, tail_len, + GEPi(bcx, scratch.val, [0u, abi::slice_elt_len]) + ); + elems.push(scratch.val); + scratch.add_clean(bcx); + } + return {vals: elems, bcx: bcx}; +} + +// NB: This function does not collect fields from struct-like enum variants. +fn collect_record_or_struct_fields(bcx: block, m: &[@Match], col: uint) -> + ~[ast::ident] { + let mut fields: ~[ast::ident] = ~[]; + for vec::each(m) |br| { + match /*bad*/copy br.pats[col].node { + ast::pat_rec(fs, _) => extend(&mut fields, fs), + ast::pat_struct(_, fs, _) => { + match ty::get(node_id_type(bcx, br.pats[col].id)).sty { + ty::ty_struct(*) => extend(&mut fields, fs), + _ => () + } + } + _ => () + } + } + return fields; + + fn extend(idents: &mut ~[ast::ident], field_pats: &[ast::field_pat]) { + for field_pats.each |field_pat| { + let field_ident = field_pat.ident; + if !vec::any(*idents, |x| *x == field_ident) { + idents.push(field_ident); + } + } + } +} + +fn root_pats_as_necessary(bcx: block, m: &[@Match], + col: uint, val: ValueRef) +{ + for vec::each(m) |br| { + let pat_id = br.pats[col].id; + + match bcx.ccx().maps.root_map.find({id:pat_id, derefs:0u}) { + None => (), + Some(scope_id) => { + // Note: the scope_id will always be the id of the match. See + // the extended comment in rustc::middle::borrowck::preserve() + // for details (look for the case covering cat_discr). + + let datum = Datum {val: val, ty: node_id_type(bcx, pat_id), + mode: ByRef, source: FromLvalue}; + datum.root(bcx, scope_id); + return; // if we kept going, we'd only re-root the same value + } + } + } +} + +// Macro for deciding whether any of the remaining matches fit a given kind of +// pattern. Note that, because the macro is well-typed, either ALL of the +// matches should fit that sort of pattern or NONE (however, some of the +// matches may be wildcards like _ or identifiers). +macro_rules! any_pat ( + ($m:expr, $pattern:pat) => ( + vec::any($m, |br| { + match br.pats[col].node { + $pattern => true, + _ => false + } + }) + ) +) + +fn any_box_pat(m: &[@Match], col: uint) -> bool { + any_pat!(m, ast::pat_box(_)) +} + +fn any_uniq_pat(m: &[@Match], col: uint) -> bool { + any_pat!(m, ast::pat_uniq(_)) +} + +fn any_region_pat(m: &[@Match], col: uint) -> bool { + any_pat!(m, ast::pat_region(_)) +} + +fn any_tup_pat(m: &[@Match], col: uint) -> bool { + any_pat!(m, ast::pat_tup(_)) +} + +fn any_tuple_struct_pat(bcx: block, m: &[@Match], col: uint) -> bool { + vec::any(m, |br| { + let pat = br.pats[col]; + match pat.node { + ast::pat_enum(_, Some(_)) => { + match bcx.tcx().def_map.find(pat.id) { + Some(ast::def_struct(*)) => true, + _ => false + } + } + _ => false + } + }) +} + +type mk_fail = fn@() -> BasicBlockRef; + +fn pick_col(m: &[@Match]) -> uint { + fn score(p: @ast::pat) -> uint { + match p.node { + ast::pat_lit(_) | ast::pat_enum(_, _) | ast::pat_range(_, _) => 1u, + ast::pat_ident(_, _, Some(p)) => score(p), + _ => 0u + } + } + let scores = vec::to_mut(vec::from_elem(m[0].pats.len(), 0u)); + for vec::each(m) |br| { + let mut i = 0u; + for vec::each(br.pats) |p| { scores[i] += score(*p); i += 1u; } + } + let mut max_score = 0u; + let mut best_col = 0u; + let mut i = 0u; + for vec::each(scores) |score| { + let score = *score; + + // Irrefutable columns always go first, they'd only be duplicated in + // the branches. + if score == 0u { return i; } + // If no irrefutable ones are found, we pick the one with the biggest + // branching factor. + if score > max_score { max_score = score; best_col = i; } + i += 1u; + } + return best_col; +} + +enum branch_kind { no_branch, single, switch, compare, compare_vec_len, } + +impl branch_kind : cmp::Eq { + pure fn eq(&self, other: &branch_kind) -> bool { + ((*self) as uint) == ((*other) as uint) + } + pure fn ne(&self, other: &branch_kind) -> bool { !(*self).eq(other) } +} + +// Compiles a comparison between two things. +fn compare_values(cx: block, lhs: ValueRef, rhs: ValueRef, rhs_t: ty::t) -> + Result { + let _icx = cx.insn_ctxt("compare_values"); + if ty::type_is_scalar(rhs_t) { + let rs = compare_scalar_types(cx, lhs, rhs, rhs_t, ast::eq); + return rslt(rs.bcx, rs.val); + } + + match ty::get(rhs_t).sty { + ty::ty_estr(ty::vstore_uniq) => { + let scratch_result = scratch_datum(cx, ty::mk_bool(cx.tcx()), + false); + let scratch_lhs = alloca(cx, val_ty(lhs)); + Store(cx, lhs, scratch_lhs); + let scratch_rhs = alloca(cx, val_ty(rhs)); + Store(cx, rhs, scratch_rhs); + let did = cx.tcx().lang_items.uniq_str_eq_fn(); + let bcx = callee::trans_rtcall_or_lang_call(cx, did, + ~[scratch_lhs, + scratch_rhs], + expr::SaveIn( + scratch_result.val)); + return scratch_result.to_result(bcx); + } + ty::ty_estr(_) => { + let scratch_result = scratch_datum(cx, ty::mk_bool(cx.tcx()), + false); + let did = cx.tcx().lang_items.str_eq_fn(); + let bcx = callee::trans_rtcall_or_lang_call(cx, did, + ~[lhs, rhs], + expr::SaveIn( + scratch_result.val)); + return scratch_result.to_result(bcx); + } + _ => { + cx.tcx().sess.bug(~"only scalars and strings supported in \ + compare_values"); + } + } +} + +fn store_non_ref_bindings(bcx: block, + data: &ArmData, + opt_temp_cleanups: Option<&DVec>) + -> block +{ + /*! + * + * For each copy/move binding, copy the value from the value + * being matched into its final home. This code executes once + * one of the patterns for a given arm has completely matched. + * It adds temporary cleanups to the `temp_cleanups` array, + * if one is provided. + */ + + let mut bcx = bcx; + for data.bindings_map.each_value |binding_info| { + match binding_info.trmode { + TrByValue(is_move, lldest) => { + let llval = Load(bcx, binding_info.llmatch); // get a T* + let datum = Datum {val: llval, ty: binding_info.ty, + mode: ByRef, source: FromLvalue}; + bcx = { + if is_move { + datum.move_to(bcx, INIT, lldest) + } else { + datum.copy_to(bcx, INIT, lldest) + } + }; + + for opt_temp_cleanups.each |temp_cleanups| { + add_clean_temp_mem(bcx, lldest, binding_info.ty); + temp_cleanups.push(lldest); + } + } + TrByRef | TrByImplicitRef => {} + } + } + return bcx; +} + +fn insert_lllocals(bcx: block, + data: &ArmData, + add_cleans: bool) -> block { + /*! + * + * For each binding in `data.bindings_map`, adds an appropriate entry into + * the `fcx.lllocals` map. If add_cleans is true, then adds cleanups for + * the bindings. */ + + for data.bindings_map.each_value |binding_info| { + let llval = match binding_info.trmode { + // By value bindings: use the stack slot that we + // copied/moved the value into + TrByValue(_, lldest) => { + if add_cleans { + add_clean(bcx, lldest, binding_info.ty); + } + + lldest + } + + // By ref binding: use the ptr into the matched value + TrByRef => { + binding_info.llmatch + } + + // Ugly: for implicit ref, we actually want a T*, but + // we have a T**, so we had to load. This will go away + // once implicit refs go away. + TrByImplicitRef => { + Load(bcx, binding_info.llmatch) + } + }; + + bcx.fcx.lllocals.insert(binding_info.id, + local_mem(llval)); + } + return bcx; +} + +fn compile_guard(bcx: block, + guard_expr: @ast::expr, + data: &ArmData, + m: &[@Match], + vals: &[ValueRef], + chk: Option) + -> block +{ + debug!("compile_guard(bcx=%s, guard_expr=%s, m=%s, vals=%?)", + bcx.to_str(), + bcx.expr_to_str(guard_expr), + matches_to_str(bcx, m), + vals.map(|v| bcx.val_str(*v))); + let _indenter = indenter(); + + let mut bcx = bcx; + let temp_cleanups = DVec(); + bcx = store_non_ref_bindings(bcx, data, Some(&temp_cleanups)); + bcx = insert_lllocals(bcx, data, false); + + let val = unpack_result!(bcx, { + do with_scope_result(bcx, guard_expr.info(), + ~"guard") |bcx| { + expr::trans_to_datum(bcx, guard_expr).to_result() + } + }); + + // Revoke the temp cleanups now that the guard successfully executed. + for temp_cleanups.each |llval| { + revoke_clean(bcx, *llval); + } + + return do with_cond(bcx, Not(bcx, val)) |bcx| { + // Guard does not match: free the values we copied, + // and remove all bindings from the lllocals table + let bcx = drop_bindings(bcx, data); + compile_submatch(bcx, m, vals, chk); + bcx + }; + + fn drop_bindings(bcx: block, data: &ArmData) -> block { + let mut bcx = bcx; + for data.bindings_map.each_value |binding_info| { + match binding_info.trmode { + TrByValue(_, llval) => { + bcx = glue::drop_ty(bcx, llval, binding_info.ty); + } + TrByRef | TrByImplicitRef => {} + } + bcx.fcx.lllocals.remove(binding_info.id); + } + return bcx; + } +} + +fn compile_submatch(bcx: block, + m: &[@Match], + vals: &[ValueRef], + chk: Option) +{ + debug!("compile_submatch(bcx=%s, m=%s, vals=%?)", + bcx.to_str(), + matches_to_str(bcx, m), + vals.map(|v| bcx.val_str(*v))); + let _indenter = indenter(); + + /* + For an empty match, a fall-through case must exist + */ + assert(m.len() > 0u || chk.is_some()); + let _icx = bcx.insn_ctxt("match::compile_submatch"); + let mut bcx = bcx; + let tcx = bcx.tcx(), dm = tcx.def_map; + if m.len() == 0u { + Br(bcx, chk.get()()); + return; + } + if m[0].pats.len() == 0u { + let data = m[0].data; + match data.arm.guard { + Some(guard_expr) => { + bcx = compile_guard(bcx, guard_expr, m[0].data, + vec::view(m, 1, m.len()), + vals, chk); + } + _ => () + } + Br(bcx, data.bodycx.llbb); + return; + } + + let col = pick_col(m); + let val = vals[col]; + let m = { + if has_nested_bindings(m, col) { + expand_nested_bindings(bcx, m, col, val) + } else { + m.to_vec() + } + }; + + let vals_left = vec::append(vec::slice(vals, 0u, col), + vec::view(vals, col + 1u, vals.len())); + let ccx = bcx.fcx.ccx; + let mut pat_id = 0; + for vec::each(m) |br| { + // Find a real id (we're adding placeholder wildcard patterns, but + // each column is guaranteed to have at least one real pattern) + if pat_id == 0 { pat_id = br.pats[col].id; } + } + + root_pats_as_necessary(bcx, m, col, val); + + let rec_fields = collect_record_or_struct_fields(bcx, m, col); + if rec_fields.len() > 0 { + let pat_ty = node_id_type(bcx, pat_id); + do expr::with_field_tys(tcx, pat_ty, None) |_has_dtor, field_tys| { + let rec_vals = rec_fields.map(|field_name| { + let ix = ty::field_idx_strict(tcx, *field_name, field_tys); + GEPi(bcx, val, struct_field(ix)) + }); + compile_submatch( + bcx, + enter_rec_or_struct(bcx, dm, m, col, rec_fields, val), + vec::append(rec_vals, vals_left), + chk); + } + return; + } + + if any_tup_pat(m, col) { + let tup_ty = node_id_type(bcx, pat_id); + let n_tup_elts = match /*bad*/copy ty::get(tup_ty).sty { + ty::ty_tup(elts) => elts.len(), + _ => ccx.sess.bug(~"non-tuple type in tuple pattern") + }; + let tup_vals = vec::from_fn(n_tup_elts, |i| GEPi(bcx, val, [0u, i])); + compile_submatch(bcx, enter_tup(bcx, dm, m, col, val, n_tup_elts), + vec::append(tup_vals, vals_left), chk); + return; + } + + if any_tuple_struct_pat(bcx, m, col) { + let struct_ty = node_id_type(bcx, pat_id); + let struct_element_count; + match ty::get(struct_ty).sty { + ty::ty_struct(struct_id, _) => { + struct_element_count = + ty::lookup_struct_fields(tcx, struct_id).len(); + } + _ => { + ccx.sess.bug(~"non-struct type in tuple struct pattern"); + } + } + + let llstructvals = vec::from_fn( + struct_element_count, |i| GEPi(bcx, val, struct_field(i))); + compile_submatch(bcx, + enter_tuple_struct(bcx, dm, m, col, val, + struct_element_count), + vec::append(llstructvals, vals_left), + chk); + return; + } + + // Unbox in case of a box field + if any_box_pat(m, col) { + let llbox = Load(bcx, val); + let box_no_addrspace = non_gc_box_cast(bcx, llbox); + let unboxed = + GEPi(bcx, box_no_addrspace, [0u, abi::box_field_body]); + compile_submatch(bcx, enter_box(bcx, dm, m, col, val), + vec::append(~[unboxed], vals_left), chk); + return; + } + + if any_uniq_pat(m, col) { + let llbox = Load(bcx, val); + let box_no_addrspace = non_gc_box_cast(bcx, llbox); + let unboxed = + GEPi(bcx, box_no_addrspace, [0u, abi::box_field_body]); + compile_submatch(bcx, enter_uniq(bcx, dm, m, col, val), + vec::append(~[unboxed], vals_left), chk); + return; + } + + if any_region_pat(m, col) { + let loaded_val = Load(bcx, val); + compile_submatch(bcx, enter_region(bcx, dm, m, col, val), + vec::append(~[loaded_val], vals_left), chk); + return; + } + + // Decide what kind of branch we need + let opts = get_options(ccx, m, col); + let mut kind = no_branch; + let mut test_val = val; + if opts.len() > 0u { + match opts[0] { + var(_, vdef) => { + if (*ty::enum_variants(tcx, vdef.enm)).len() == 1u { + kind = single; + } else { + let enumptr = + PointerCast(bcx, val, T_opaque_enum_ptr(ccx)); + let discrimptr = GEPi(bcx, enumptr, [0u, 0u]); + test_val = Load(bcx, discrimptr); + kind = switch; + } + } + lit(_) => { + let pty = node_id_type(bcx, pat_id); + test_val = load_if_immediate(bcx, val, pty); + kind = if ty::type_is_integral(pty) { switch } + else { compare }; + } + range(_, _) => { + test_val = Load(bcx, val); + kind = compare; + }, + vec_len_eq(_) | vec_len_ge(_) => { + let vt = tvec::vec_types(bcx, node_id_type(bcx, pat_id)); + let unboxed = load_if_immediate(bcx, val, vt.vec_ty); + let (_, len) = tvec::get_base_and_len( + bcx, unboxed, vt.vec_ty + ); + test_val = SDiv(bcx, len, vt.llunit_size); + kind = compare_vec_len; + } + } + } + for vec::each(opts) |o| { + match *o { + range(_, _) => { kind = compare; break } + _ => () + } + } + let else_cx = match kind { + no_branch | single => bcx, + _ => sub_block(bcx, ~"match_else") + }; + let sw = if kind == switch { + Switch(bcx, test_val, else_cx.llbb, opts.len()) + } else { + C_int(ccx, 0) // Placeholder for when not using a switch + }; + + let defaults = enter_default(else_cx, dm, m, col, val); + let exhaustive = chk.is_none() && defaults.len() == 0u; + let len = opts.len(); + let mut i = 0u; + + // Compile subtrees for each option + for vec::each(opts) |opt| { + i += 1u; + let mut opt_cx = else_cx; + if !exhaustive || i < len { + opt_cx = sub_block(bcx, ~"match_case"); + match kind { + single => Br(bcx, opt_cx.llbb), + switch => { + match trans_opt(bcx, opt) { + single_result(r) => { + llvm::LLVMAddCase(sw, r.val, opt_cx.llbb); + bcx = r.bcx; + } + _ => { + bcx.sess().bug( + ~"in compile_submatch, expected \ + trans_opt to return a single_result") + } + } + } + compare => { + let t = node_id_type(bcx, pat_id); + let Result {bcx: after_cx, val: matches} = { + do with_scope_result(bcx, None, + ~"compare_scope") |bcx| { + match trans_opt(bcx, opt) { + single_result( + Result {bcx, val}) => { + compare_values(bcx, test_val, val, t) + } + lower_bound( + Result {bcx, val}) => { + compare_scalar_types( + bcx, test_val, val, + t, ast::ge) + } + range_result( + Result {val: vbegin, _}, + Result {bcx, val: vend}) => { + let Result {bcx, val: llge} = + compare_scalar_types( + bcx, test_val, + vbegin, t, ast::ge); + let Result {bcx, val: llle} = + compare_scalar_types( + bcx, test_val, vend, + t, ast::le); + rslt(bcx, And(bcx, llge, llle)) + } + } + } + }; + bcx = sub_block(after_cx, ~"compare_next"); + CondBr(after_cx, matches, opt_cx.llbb, bcx.llbb); + } + compare_vec_len => { + let Result {bcx: after_cx, val: matches} = { + do with_scope_result(bcx, None, + ~"compare_vec_len_scope") |bcx| { + match trans_opt(bcx, opt) { + single_result( + Result {bcx, val}) => { + let value = compare_scalar_values( + bcx, test_val, val, + signed_int, ast::eq); + rslt(bcx, value) + } + lower_bound( + Result {bcx, val: val}) => { + let value = compare_scalar_values( + bcx, test_val, val, + signed_int, ast::ge); + rslt(bcx, value) + } + range_result( + Result {val: vbegin, _}, + Result {bcx, val: vend}) => { + let llge = + compare_scalar_values( + bcx, test_val, + vbegin, signed_int, ast::ge); + let llle = + compare_scalar_values( + bcx, test_val, vend, + signed_int, ast::le); + rslt(bcx, And(bcx, llge, llle)) + } + } + } + }; + bcx = sub_block(after_cx, ~"compare_vec_len_next"); + CondBr(after_cx, matches, opt_cx.llbb, bcx.llbb); + } + _ => () + } + } else if kind == compare || kind == compare_vec_len { + Br(bcx, else_cx.llbb); + } + + let mut size = 0u; + let mut unpacked = ~[]; + match *opt { + var(_, vdef) => { + let args = extract_variant_args(opt_cx, pat_id, vdef, val); + size = args.vals.len(); + unpacked = /*bad*/copy args.vals; + opt_cx = args.bcx; + } + vec_len_eq(n) | vec_len_ge(n) => { + let tail = match *opt { + vec_len_ge(_) => true, + _ => false + }; + let args = extract_vec_elems(opt_cx, pat_id, n, tail, val); + size = args.vals.len(); + unpacked = /*bad*/copy args.vals; + opt_cx = args.bcx; + } + lit(_) | range(_, _) => () + } + let opt_ms = enter_opt(opt_cx, m, opt, col, size, val); + let opt_vals = vec::append(unpacked, vals_left); + compile_submatch(opt_cx, opt_ms, opt_vals, chk); + } + + // Compile the fall-through case, if any + if !exhaustive { + if kind == compare || kind == compare_vec_len { + Br(bcx, else_cx.llbb); + } + if kind != single { + compile_submatch(else_cx, defaults, vals_left, chk); + } + } +} + +fn trans_match(bcx: block, + match_expr: @ast::expr, + discr_expr: @ast::expr, + arms: ~[ast::arm], + dest: Dest) -> block { + let _icx = bcx.insn_ctxt("match::trans_match"); + do with_scope(bcx, match_expr.info(), ~"match") |bcx| { + trans_match_inner(bcx, discr_expr, arms, dest) + } +} + +fn trans_match_inner(scope_cx: block, + discr_expr: @ast::expr, + arms: &[ast::arm], + dest: Dest) -> block { + let _icx = scope_cx.insn_ctxt("match::trans_match_inner"); + let mut bcx = scope_cx; + let tcx = bcx.tcx(); + + let discr_datum = unpack_datum!(bcx, { + expr::trans_to_datum(bcx, discr_expr) + }); + if bcx.unreachable { + return bcx; + } + + let mut arm_datas = ~[], matches = ~[]; + for vec::each(arms) |arm| { + let body = scope_block(bcx, arm.body.info(), ~"case_body"); + + // Create the bindings map, which is a mapping from each binding name + // to an alloca() that will be the value for that local variable. + // Note that we use the names because each binding will have many ids + // from the various alternatives. + let bindings_map = HashMap(); + do pat_bindings(tcx.def_map, arm.pats[0]) |bm, p_id, s, path| { + let ident = path_to_ident(path); + let variable_ty = node_id_type(bcx, p_id); + let llvariable_ty = type_of::type_of(bcx.ccx(), variable_ty); + + let llmatch, trmode; + match bm { + ast::bind_by_value | ast::bind_by_move => { + // in this case, the type of the variable will be T, + // but we need to store a *T + let is_move = (bm == ast::bind_by_move); + llmatch = alloca(bcx, T_ptr(llvariable_ty)); + trmode = TrByValue(is_move, alloca(bcx, llvariable_ty)); + } + ast::bind_infer => { + // in this case also, the type of the variable will be T, + // but we need to store a *T + let is_move = match tcx.value_modes.find(p_id) { + None => { + tcx.sess.span_bug(s, ~"no value mode"); + } + Some(MoveValue) => true, + Some(CopyValue) | Some(ReadValue) => false + }; + llmatch = alloca(bcx, T_ptr(llvariable_ty)); + trmode = TrByValue(is_move, alloca(bcx, llvariable_ty)); + } + ast::bind_by_ref(_) => { + llmatch = alloca(bcx, llvariable_ty); + trmode = TrByRef; + } + }; + bindings_map.insert(ident, BindingInfo { + llmatch: llmatch, trmode: trmode, + id: p_id, ty: variable_ty + }); + } + + let arm_data = @ArmData {bodycx: body, + arm: arm, + bindings_map: bindings_map}; + arm_datas.push(arm_data); + for vec::each(arm.pats) |p| { + matches.push(@Match {pats: ~[*p], data: arm_data}); + } + } + + let t = node_id_type(bcx, discr_expr.id); + let chk = { + if ty::type_is_empty(tcx, t) { + // Special case for empty types + let fail_cx = @mut None; + Some(|| mk_fail(scope_cx, discr_expr.span, + ~"scrutinizing value that can't exist", fail_cx)) + } else { + None + } + }; + let lldiscr = discr_datum.to_ref_llval(bcx); + compile_submatch(bcx, matches, ~[lldiscr], chk); + + let arm_cxs = DVec(); + for arm_datas.each |arm_data| { + let mut bcx = arm_data.bodycx; + + // If this arm has a guard, then the various by-value bindings have + // already been copied into their homes. If not, we do it here. This + // is just to reduce code space. See extensive comment at the start + // of the file for more details. + if arm_data.arm.guard.is_none() { + bcx = store_non_ref_bindings(bcx, *arm_data, None); + } + + // insert bindings into the lllocals map and add cleanups + bcx = insert_lllocals(bcx, *arm_data, true); + + bcx = controlflow::trans_block(bcx, arm_data.arm.body, dest); + bcx = trans_block_cleanups(bcx, block_cleanups(arm_data.bodycx)); + arm_cxs.push(bcx); + } + + return controlflow::join_blocks(scope_cx, dvec::unwrap(move arm_cxs)); + + fn mk_fail(bcx: block, sp: span, +msg: ~str, + finished: @mut Option) -> BasicBlockRef { + match *finished { Some(bb) => return bb, _ => () } + let fail_cx = sub_block(bcx, ~"case_fallthrough"); + controlflow::trans_fail(fail_cx, Some(sp), msg); + *finished = Some(fail_cx.llbb); + return fail_cx.llbb; + } +} + +enum IrrefutablePatternBindingMode { + // Stores the association between node ID and LLVM value in `lllocals`. + BindLocal, + // Stores the association between node ID and LLVM value in `llargs`. + BindArgument +} + +// Not match-related, but similar to the pattern-munging code above +fn bind_irrefutable_pat(bcx: block, + pat: @ast::pat, + val: ValueRef, + make_copy: bool, + binding_mode: IrrefutablePatternBindingMode) + -> block { + let _icx = bcx.insn_ctxt("match::bind_irrefutable_pat"); + let ccx = bcx.fcx.ccx; + let mut bcx = bcx; + + // Necessary since bind_irrefutable_pat is called outside trans_match + match /*bad*/copy pat.node { + ast::pat_ident(_, _,inner) => { + if pat_is_variant_or_struct(bcx.tcx().def_map, pat) { + return bcx; + } + + if make_copy { + let binding_ty = node_id_type(bcx, pat.id); + let datum = Datum {val: val, ty: binding_ty, + mode: ByRef, source: FromRvalue}; + let scratch = scratch_datum(bcx, binding_ty, false); + datum.copy_to_datum(bcx, INIT, scratch); + match binding_mode { + BindLocal => { + bcx.fcx.lllocals.insert(pat.id, + local_mem(scratch.val)); + } + BindArgument => { + bcx.fcx.llargs.insert(pat.id, + local_mem(scratch.val)); + } + } + add_clean(bcx, scratch.val, binding_ty); + } else { + match binding_mode { + BindLocal => { + bcx.fcx.lllocals.insert(pat.id, local_mem(val)); + } + BindArgument => { + bcx.fcx.llargs.insert(pat.id, local_mem(val)); + } + } + } + + for inner.each |inner_pat| { + bcx = bind_irrefutable_pat( + bcx, *inner_pat, val, true, binding_mode); + } + } + ast::pat_enum(_, sub_pats) => { + match bcx.tcx().def_map.find(pat.id) { + Some(ast::def_variant(*)) => { + let pat_def = ccx.tcx.def_map.get(pat.id); + let vdefs = ast_util::variant_def_ids(pat_def); + let args = extract_variant_args(bcx, pat.id, vdefs, val); + for sub_pats.each |sub_pat| { + for vec::eachi(args.vals) |i, argval| { + bcx = bind_irrefutable_pat(bcx, + sub_pat[i], + *argval, + make_copy, + binding_mode); + } + } + } + Some(ast::def_struct(*)) => { + match sub_pats { + None => { + // This is a unit-like struct. Nothing to do here. + } + Some(elems) => { + // This is the tuple variant case. + for vec::eachi(elems) |i, elem| { + let fldptr = GEPi(bcx, val, struct_field(i)); + bcx = bind_irrefutable_pat(bcx, + *elem, + fldptr, + make_copy, + binding_mode); + } + } + } + } + _ => { + // Nothing to do here. + } + } + } + ast::pat_rec(fields, _) | ast::pat_struct(_, fields, _) => { + let tcx = bcx.tcx(); + let pat_ty = node_id_type(bcx, pat.id); + do expr::with_field_tys(tcx, pat_ty, None) |_hd, field_tys| { + for vec::each(fields) |f| { + let ix = ty::field_idx_strict(tcx, f.ident, field_tys); + let fldptr = GEPi(bcx, val, struct_field(ix)); + bcx = bind_irrefutable_pat(bcx, + f.pat, + fldptr, + make_copy, + binding_mode); + } + } + } + ast::pat_tup(elems) => { + for vec::eachi(elems) |i, elem| { + let fldptr = GEPi(bcx, val, [0u, i]); + bcx = bind_irrefutable_pat(bcx, + *elem, + fldptr, + make_copy, + binding_mode); + } + } + ast::pat_box(inner) | ast::pat_uniq(inner) => { + let llbox = Load(bcx, val); + let unboxed = GEPi(bcx, llbox, [0u, abi::box_field_body]); + bcx = bind_irrefutable_pat(bcx, + inner, + unboxed, + true, + binding_mode); + } + ast::pat_region(inner) => { + let loaded_val = Load(bcx, val); + bcx = bind_irrefutable_pat(bcx, + inner, + loaded_val, + true, + binding_mode); + } + ast::pat_wild | ast::pat_lit(_) | ast::pat_range(_, _) | + ast::pat_vec(*) => () + } + return bcx; +} + +// Local Variables: +// mode: rust +// fill-column: 78; +// indent-tabs-mode: nil +// c-basic-offset: 4 +// buffer-file-coding-system: utf-8-unix +// End: diff --git a/src/librustc/middle/trans/alt.rs b/src/librustc/middle/trans/alt.rs deleted file mode 100644 index a183bd453d0..00000000000 --- a/src/librustc/middle/trans/alt.rs +++ /dev/null @@ -1,1802 +0,0 @@ -// Copyright 2012 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. - -/*! - * - * # Compilation of match statements - * - * I will endeavor to explain the code as best I can. I have only a loose - * understanding of some parts of it. - * - * ## Matching - * - * The basic state of the code is maintained in an array `m` of `@Match` - * objects. Each `@Match` describes some list of patterns, all of which must - * match against the current list of values. If those patterns match, then - * the arm listed in the match is the correct arm. A given arm may have - * multiple corresponding match entries, one for each alternative that - * remains. As we proceed these sets of matches are adjusted by the various - * `enter_XXX()` functions, each of which adjusts the set of options given - * some information about the value which has been matched. - * - * So, initially, there is one value and N matches, each of which have one - * constituent pattern. N here is usually the number of arms but may be - * greater, if some arms have multiple alternatives. For example, here: - * - * enum Foo { A, B(int), C(uint, uint) } - * match foo { - * A => ..., - * B(x) => ..., - * C(1u, 2) => ..., - * C(_) => ... - * } - * - * The value would be `foo`. There would be four matches, each of which - * contains one pattern (and, in one case, a guard). We could collect the - * various options and then compile the code for the case where `foo` is an - * `A`, a `B`, and a `C`. When we generate the code for `C`, we would (1) - * drop the two matches that do not match a `C` and (2) expand the other two - * into two patterns each. In the first case, the two patterns would be `1u` - * and `2`, and the in the second case the _ pattern would be expanded into - * `_` and `_`. The two values are of course the arguments to `C`. - * - * Here is a quick guide to the various functions: - * - * - `compile_submatch()`: The main workhouse. It takes a list of values and - * a list of matches and finds the various possibilities that could occur. - * - * - `enter_XXX()`: modifies the list of matches based on some information - * about the value that has been matched. For example, - * `enter_rec_or_struct()` adjusts the values given that a record or struct - * has been matched. This is an infallible pattern, so *all* of the matches - * must be either wildcards or record/struct patterns. `enter_opt()` - * handles the fallible cases, and it is correspondingly more complex. - * - * ## Bindings - * - * We store information about the bound variables for each arm as part of the - * per-arm `ArmData` struct. There is a mapping from identifiers to - * `BindingInfo` structs. These structs contain the mode/id/type of the - * binding, but they also contain up to two LLVM values, called `llmatch` and - * `llbinding` respectively (the `llbinding`, as will be described shortly, is - * optional and only present for by-value bindings---therefore it is bundled - * up as part of the `TransBindingMode` type). Both point at allocas. - * - * The `llmatch` binding always stores a pointer into the value being matched - * which points at the data for the binding. If the value being matched has - * type `T`, then, `llmatch` will point at an alloca of type `T*` (and hence - * `llmatch` has type `T**`). So, if you have a pattern like: - * - * let a: A = ...; - * let b: B = ...; - * match (a, b) { (ref c, copy d) => { ... } } - * - * For `c` and `d`, we would generate allocas of type `C*` and `D*` - * respectively. These are called the `llmatch`. As we match, when we come - * up against an identifier, we store the current pointer into the - * corresponding alloca. - * - * In addition, for each by-value binding (copy or move), we will create a - * second alloca (`llbinding`) that will hold the final value. In this - * example, that means that `d` would have this second alloca of type `D` (and - * hence `llbinding` has type `D*`). - * - * Once a pattern is completely matched, and assuming that there is no guard - * pattern, we will branch to a block that leads to the body itself. For any - * by-value bindings, this block will first load the ptr from `llmatch` (the - * one of type `D*`) and copy/move the value into `llbinding` (the one of type - * `D`). The second alloca then becomes the value of the local variable. For - * by ref bindings, the value of the local variable is simply the first - * alloca. - * - * So, for the example above, we would generate a setup kind of like this: - * - * +-------+ - * | Entry | - * +-------+ - * | - * +-------------------------------------------+ - * | llmatch_c = (addr of first half of tuple) | - * | llmatch_d = (addr of first half of tuple) | - * +-------------------------------------------+ - * | - * +--------------------------------------+ - * | *llbinding_d = **llmatch_dlbinding_d | - * +--------------------------------------+ - * - * If there is a guard, the situation is slightly different, because we must - * execute the guard code. Moreover, we need to do so once for each of the - * alternatives that lead to the arm, because if the guard fails, they may - * have different points from which to continue the search. Therefore, in that - * case, we generate code that looks more like: - * - * +-------+ - * | Entry | - * +-------+ - * | - * +-------------------------------------------+ - * | llmatch_c = (addr of first half of tuple) | - * | llmatch_d = (addr of first half of tuple) | - * +-------------------------------------------+ - * | - * +-------------------------------------------------+ - * | *llbinding_d = **llmatch_dlbinding_d | - * | check condition | - * | if false { free *llbinding_d, goto next case } | - * | if true { goto body } | - * +-------------------------------------------------+ - * - * The handling for the cleanups is a bit... sensitive. Basically, the body - * is the one that invokes `add_clean()` for each binding. During the guard - * evaluation, we add temporary cleanups and revoke them after the guard is - * evaluated (it could fail, after all). Presuming the guard fails, we drop - * the various values we copied explicitly. Note that guards and moves are - * just plain incompatible. - * - */ - - -use back::abi; -use lib::llvm::llvm; -use lib::llvm::{ValueRef, BasicBlockRef}; -use middle::const_eval; -use middle::pat_util::*; -use middle::resolve::DefMap; -use middle::trans::base::*; -use middle::trans::build::*; -use middle::trans::callee; -use middle::trans::common::*; -use middle::trans::consts; -use middle::trans::controlflow; -use middle::trans::datum::*; -use middle::trans::expr::Dest; -use middle::trans::expr; -use middle::trans::glue; -use middle::ty::{CopyValue, MoveValue, ReadValue}; -use util::common::indenter; - -use core::dvec::DVec; -use core::dvec; -use std::map::HashMap; -use syntax::ast::def_id; -use syntax::ast; -use syntax::ast_util::{dummy_sp, path_to_ident}; -use syntax::ast_util; -use syntax::codemap::span; -use syntax::print::pprust::pat_to_str; - -fn macros() { include!("macros.rs"); } // FIXME(#3114): Macro import/export. - -// An option identifying a literal: either a unit-like struct or an -// expression. -enum Lit { - UnitLikeStructLit(ast::node_id), // the node ID of the pattern - ExprLit(@ast::expr), - ConstLit(ast::def_id), // the def ID of the constant -} - -// An option identifying a branch (either a literal, a enum variant or a -// range) -enum Opt { - lit(Lit), - var(/* disr val */int, /* variant dids */{enm: def_id, var: def_id}), - range(@ast::expr, @ast::expr), - vec_len_eq(uint), - vec_len_ge(uint) -} - -fn opt_eq(tcx: ty::ctxt, a: &Opt, b: &Opt) -> bool { - match (*a, *b) { - (lit(a), lit(b)) => { - match (a, b) { - (UnitLikeStructLit(a), UnitLikeStructLit(b)) => a == b, - _ => { - let a_expr; - match a { - ExprLit(existing_a_expr) => a_expr = existing_a_expr, - ConstLit(a_const) => { - let e = const_eval::lookup_const_by_id(tcx, a_const); - a_expr = e.get(); - } - UnitLikeStructLit(_) => { - fail ~"UnitLikeStructLit should have been handled \ - above" - } - } - - let b_expr; - match b { - ExprLit(existing_b_expr) => b_expr = existing_b_expr, - ConstLit(b_const) => { - let e = const_eval::lookup_const_by_id(tcx, b_const); - b_expr = e.get(); - } - UnitLikeStructLit(_) => { - fail ~"UnitLikeStructLit should have been handled \ - above" - } - } - - const_eval::compare_lit_exprs(tcx, a_expr, b_expr) == 0 - } - } - } - (range(a1, a2), range(b1, b2)) => { - const_eval::compare_lit_exprs(tcx, a1, b1) == 0 && - const_eval::compare_lit_exprs(tcx, a2, b2) == 0 - } - (var(a, _), var(b, _)) => a == b, - (vec_len_eq(a), vec_len_eq(b)) => a == b, - (vec_len_ge(a), vec_len_ge(b)) => a == b, - _ => false - } -} - -enum opt_result { - single_result(Result), - lower_bound(Result), - range_result(Result, Result), -} -fn trans_opt(bcx: block, o: &Opt) -> opt_result { - let _icx = bcx.insn_ctxt("alt::trans_opt"); - let ccx = bcx.ccx(); - let mut bcx = bcx; - match *o { - lit(ExprLit(lit_expr)) => { - let datumblock = expr::trans_to_datum(bcx, lit_expr); - return single_result(datumblock.to_result()); - } - lit(UnitLikeStructLit(pat_id)) => { - let struct_ty = ty::node_id_to_type(bcx.tcx(), pat_id); - let datumblock = datum::scratch_datum(bcx, struct_ty, true); - return single_result(datumblock.to_result(bcx)); - } - lit(ConstLit(lit_id)) => { - let llval = consts::get_const_val(bcx.ccx(), lit_id); - return single_result(rslt(bcx, llval)); - } - var(disr_val, _) => { - return single_result(rslt(bcx, C_int(ccx, disr_val))); - } - range(l1, l2) => { - return range_result(rslt(bcx, consts::const_expr(ccx, l1)), - rslt(bcx, consts::const_expr(ccx, l2))); - } - vec_len_eq(n) => { - return single_result(rslt(bcx, C_int(ccx, n as int))); - } - vec_len_ge(n) => { - return lower_bound(rslt(bcx, C_int(ccx, n as int))); - } - } -} - -fn variant_opt(tcx: ty::ctxt, pat_id: ast::node_id) -> Opt { - match tcx.def_map.get(pat_id) { - ast::def_variant(enum_id, var_id) => { - let variants = ty::enum_variants(tcx, enum_id); - for vec::each(*variants) |v| { - if var_id == v.id { - return var(v.disr_val, {enm: enum_id, var: var_id}); - } - } - ::core::util::unreachable(); - } - ast::def_struct(_) => { - return lit(UnitLikeStructLit(pat_id)); - } - _ => { - tcx.sess.bug(~"non-variant or struct in variant_opt()"); - } - } -} - -enum TransBindingMode { - TrByValue(/*ismove:*/ bool, /*llbinding:*/ ValueRef), - TrByRef, - TrByImplicitRef -} - -/** - * Information about a pattern binding: - * - `llmatch` is a pointer to a stack slot. The stack slot contains a - * pointer into the value being matched. Hence, llmatch has type `T**` - * where `T` is the value being matched. - * - `trmode` is the trans binding mode - * - `id` is the node id of the binding - * - `ty` is the Rust type of the binding */ -struct BindingInfo { - llmatch: ValueRef, - trmode: TransBindingMode, - id: ast::node_id, - ty: ty::t, -} - -type BindingsMap = HashMap; - -struct ArmData { - bodycx: block, - arm: &ast::arm, - bindings_map: BindingsMap -} - -struct Match { - pats: ~[@ast::pat], - data: @ArmData -} - -fn match_to_str(bcx: block, m: &Match) -> ~str { - if bcx.sess().verbose() { - // for many programs, this just take too long to serialize - fmt!("%?", m.pats.map(|p| pat_to_str(*p, bcx.sess().intr()))) - } else { - fmt!("%u pats", m.pats.len()) - } -} - -fn matches_to_str(bcx: block, m: &[@Match]) -> ~str { - fmt!("%?", m.map(|n| match_to_str(bcx, *n))) -} - -fn has_nested_bindings(m: &[@Match], col: uint) -> bool { - for vec::each(m) |br| { - match br.pats[col].node { - ast::pat_ident(_, _, Some(_)) => return true, - _ => () - } - } - return false; -} - -fn expand_nested_bindings(bcx: block, m: &[@Match/&r], - col: uint, val: ValueRef) - -> ~[@Match/&r] -{ - debug!("expand_nested_bindings(bcx=%s, m=%s, col=%u, val=%?)", - bcx.to_str(), - matches_to_str(bcx, m), - col, - bcx.val_str(val)); - let _indenter = indenter(); - - do m.map |br| { - match br.pats[col].node { - ast::pat_ident(_, path, Some(inner)) => { - let pats = vec::append( - vec::slice(br.pats, 0u, col), - vec::append(~[inner], - vec::view(br.pats, col + 1u, br.pats.len()))); - - let binding_info = - br.data.bindings_map.get(path_to_ident(path)); - - Store(bcx, val, binding_info.llmatch); - @Match {pats: pats, data: br.data} - } - _ => { - *br - } - } - } -} - -type enter_pat = fn(@ast::pat) -> Option<~[@ast::pat]>; - -fn assert_is_binding_or_wild(bcx: block, p: @ast::pat) { - if !pat_is_binding_or_wild(bcx.tcx().def_map, p) { - bcx.sess().span_bug( - p.span, - fmt!("Expected an identifier pattern but found p: %s", - pat_to_str(p, bcx.sess().intr()))); - } -} - -fn enter_match(bcx: block, dm: DefMap, m: &[@Match/&r], - col: uint, val: ValueRef, e: enter_pat) - -> ~[@Match/&r] -{ - debug!("enter_match(bcx=%s, m=%s, col=%u, val=%?)", - bcx.to_str(), - matches_to_str(bcx, m), - col, - bcx.val_str(val)); - let _indenter = indenter(); - - let mut result = ~[]; - for vec::each(m) |br| { - match e(br.pats[col]) { - Some(sub) => { - let pats = - vec::append( - vec::append(sub, vec::view(br.pats, 0u, col)), - vec::view(br.pats, col + 1u, br.pats.len())); - - let self = br.pats[col]; - match self.node { - ast::pat_ident(_, path, None) => { - if pat_is_binding(dm, self) { - let binding_info = - br.data.bindings_map.get(path_to_ident(path)); - Store(bcx, val, binding_info.llmatch); - } - } - _ => {} - } - - result.push(@Match {pats: pats, data: br.data}); - } - None => () - } - } - - debug!("result=%s", matches_to_str(bcx, result)); - - return result; -} - -fn enter_default(bcx: block, dm: DefMap, m: &[@Match/&r], - col: uint, val: ValueRef) - -> ~[@Match/&r] -{ - debug!("enter_default(bcx=%s, m=%s, col=%u, val=%?)", - bcx.to_str(), - matches_to_str(bcx, m), - col, - bcx.val_str(val)); - let _indenter = indenter(); - - do enter_match(bcx, dm, m, col, val) |p| { - match p.node { - ast::pat_wild | ast::pat_rec(_, _) | ast::pat_tup(_) | - ast::pat_struct(*) => Some(~[]), - ast::pat_ident(_, _, None) if pat_is_binding(dm, p) => Some(~[]), - _ => None - } - } -} - -// nmatsakis: what does enter_opt do? -// in trans/alt -// trans/alt.rs is like stumbling around in a dark cave -// pcwalton: the enter family of functions adjust the set of -// patterns as needed -// yeah, at some point I kind of achieved some level of -// understanding -// anyhow, they adjust the patterns given that something of that -// kind has been found -// pcwalton: ok, right, so enter_XXX() adjusts the patterns, as I -// said -// enter_match() kind of embodies the generic code -// it is provided with a function that tests each pattern to see -// if it might possibly apply and so forth -// so, if you have a pattern like {a: _, b: _, _} and one like _ -// then _ would be expanded to (_, _) -// one spot for each of the sub-patterns -// enter_opt() is one of the more complex; it covers the fallible -// cases -// enter_rec_or_struct() or enter_tuple() are simpler, since they -// are infallible patterns -// so all patterns must either be records (resp. tuples) or -// wildcards - -fn enter_opt(bcx: block, m: &[@Match/&r], opt: &Opt, col: uint, - variant_size: uint, val: ValueRef) - -> ~[@Match/&r] -{ - debug!("enter_opt(bcx=%s, m=%s, col=%u, val=%?)", - bcx.to_str(), - matches_to_str(bcx, m), - col, - bcx.val_str(val)); - let _indenter = indenter(); - - let tcx = bcx.tcx(); - let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; - do enter_match(bcx, tcx.def_map, m, col, val) |p| { - match /*bad*/copy p.node { - ast::pat_enum(_, subpats) => { - if opt_eq(tcx, &variant_opt(tcx, p.id), opt) { - Some(option::get_or_default(subpats, - vec::from_elem(variant_size, - dummy))) - } else { - None - } - } - ast::pat_ident(_, _, None) - if pat_is_variant_or_struct(tcx.def_map, p) => { - if opt_eq(tcx, &variant_opt(tcx, p.id), opt) { - Some(~[]) - } else { - None - } - } - ast::pat_ident(_, _, None) if pat_is_const(tcx.def_map, p) => { - let const_def = tcx.def_map.get(p.id); - let const_def_id = ast_util::def_id_of_def(const_def); - if opt_eq(tcx, &lit(ConstLit(const_def_id)), opt) { - Some(~[]) - } else { - None - } - } - ast::pat_lit(l) => { - if opt_eq(tcx, &lit(ExprLit(l)), opt) {Some(~[])} else {None} - } - ast::pat_range(l1, l2) => { - if opt_eq(tcx, &range(l1, l2), opt) {Some(~[])} else {None} - } - ast::pat_struct(_, field_pats, _) => { - if opt_eq(tcx, &variant_opt(tcx, p.id), opt) { - // Look up the struct variant ID. - let struct_id; - match tcx.def_map.get(p.id) { - ast::def_variant(_, found_struct_id) => { - struct_id = found_struct_id; - } - _ => { - tcx.sess.span_bug(p.span, ~"expected enum \ - variant def"); - } - } - - // Reorder the patterns into the same order they were - // specified in the struct definition. Also fill in - // unspecified fields with dummy. - let reordered_patterns = dvec::DVec(); - for ty::lookup_struct_fields(tcx, struct_id).each - |field| { - match field_pats.find(|p| - p.ident == field.ident) { - None => reordered_patterns.push(dummy), - Some(fp) => reordered_patterns.push(fp.pat) - } - } - Some(dvec::unwrap(move reordered_patterns)) - } else { - None - } - } - ast::pat_vec(elems, tail) => { - match tail { - Some(_) => { - if opt_eq(tcx, &vec_len_ge(elems.len()), opt) { - Some(vec::append_one(elems, tail.get())) - } else { - None - } - } - None => { - if opt_eq(tcx, &vec_len_eq(elems.len()), opt) { - Some(copy elems) - } else { - None - } - } - } - } - _ => { - assert_is_binding_or_wild(bcx, p); - Some(vec::from_elem(variant_size, dummy)) - } - } - } -} - -fn enter_rec_or_struct(bcx: block, dm: DefMap, m: &[@Match/&r], col: uint, - fields: ~[ast::ident], val: ValueRef) -> ~[@Match/&r] { - debug!("enter_rec_or_struct(bcx=%s, m=%s, col=%u, val=%?)", - bcx.to_str(), - matches_to_str(bcx, m), - col, - bcx.val_str(val)); - let _indenter = indenter(); - - let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; - do enter_match(bcx, dm, m, col, val) |p| { - match /*bad*/copy p.node { - ast::pat_rec(fpats, _) | ast::pat_struct(_, fpats, _) => { - let mut pats = ~[]; - for vec::each(fields) |fname| { - match fpats.find(|p| p.ident == *fname) { - None => pats.push(dummy), - Some(pat) => pats.push(pat.pat) - } - } - Some(pats) - } - _ => { - assert_is_binding_or_wild(bcx, p); - Some(vec::from_elem(fields.len(), dummy)) - } - } - } -} - -fn enter_tup(bcx: block, dm: DefMap, m: &[@Match/&r], - col: uint, val: ValueRef, n_elts: uint) - -> ~[@Match/&r] -{ - debug!("enter_tup(bcx=%s, m=%s, col=%u, val=%?)", - bcx.to_str(), - matches_to_str(bcx, m), - col, - bcx.val_str(val)); - let _indenter = indenter(); - - let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; - do enter_match(bcx, dm, m, col, val) |p| { - match /*bad*/copy p.node { - ast::pat_tup(elts) => { - Some(elts) - } - _ => { - assert_is_binding_or_wild(bcx, p); - Some(vec::from_elem(n_elts, dummy)) - } - } - } -} - -fn enter_tuple_struct(bcx: block, dm: DefMap, m: &[@Match/&r], col: uint, - val: ValueRef, n_elts: uint) - -> ~[@Match/&r] -{ - debug!("enter_tuple_struct(bcx=%s, m=%s, col=%u, val=%?)", - bcx.to_str(), - matches_to_str(bcx, m), - col, - bcx.val_str(val)); - let _indenter = indenter(); - - let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; - do enter_match(bcx, dm, m, col, val) |p| { - match /*bad*/copy p.node { - ast::pat_enum(_, Some(elts)) => Some(elts), - _ => { - assert_is_binding_or_wild(bcx, p); - Some(vec::from_elem(n_elts, dummy)) - } - } - } -} - -fn enter_box(bcx: block, dm: DefMap, m: &[@Match/&r], - col: uint, val: ValueRef) - -> ~[@Match/&r] -{ - debug!("enter_box(bcx=%s, m=%s, col=%u, val=%?)", - bcx.to_str(), - matches_to_str(bcx, m), - col, - bcx.val_str(val)); - let _indenter = indenter(); - - let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; - do enter_match(bcx, dm, m, col, val) |p| { - match p.node { - ast::pat_box(sub) => { - Some(~[sub]) - } - _ => { - assert_is_binding_or_wild(bcx, p); - Some(~[dummy]) - } - } - } -} - -fn enter_uniq(bcx: block, dm: DefMap, m: &[@Match/&r], - col: uint, val: ValueRef) - -> ~[@Match/&r] -{ - debug!("enter_uniq(bcx=%s, m=%s, col=%u, val=%?)", - bcx.to_str(), - matches_to_str(bcx, m), - col, - bcx.val_str(val)); - let _indenter = indenter(); - - let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; - do enter_match(bcx, dm, m, col, val) |p| { - match p.node { - ast::pat_uniq(sub) => { - Some(~[sub]) - } - _ => { - assert_is_binding_or_wild(bcx, p); - Some(~[dummy]) - } - } - } -} - -fn enter_region(bcx: block, dm: DefMap, m: &[@Match/&r], - col: uint, val: ValueRef) - -> ~[@Match/&r] -{ - debug!("enter_region(bcx=%s, m=%s, col=%u, val=%?)", - bcx.to_str(), - matches_to_str(bcx, m), - col, - bcx.val_str(val)); - let _indenter = indenter(); - - let dummy = @{id: 0, node: ast::pat_wild, span: dummy_sp()}; - do enter_match(bcx, dm, m, col, val) |p| { - match p.node { - ast::pat_region(sub) => { - Some(~[sub]) - } - _ => { - assert_is_binding_or_wild(bcx, p); - Some(~[dummy]) - } - } - } -} - -// Returns the options in one column of matches. An option is something that -// needs to be conditionally matched at runtime; for example, the discriminant -// on a set of enum variants or a literal. -fn get_options(ccx: @crate_ctxt, m: &[@Match], col: uint) -> ~[Opt] { - fn add_to_set(tcx: ty::ctxt, set: &DVec, val: Opt) { - if set.any(|l| opt_eq(tcx, l, &val)) {return;} - set.push(val); - } - - let found = DVec(); - for vec::each(m) |br| { - let cur = br.pats[col]; - match /*bad*/copy cur.node { - ast::pat_lit(l) => { - add_to_set(ccx.tcx, &found, lit(ExprLit(l))); - } - ast::pat_ident(*) => { - // This is one of: an enum variant, a unit-like struct, or a - // variable binding. - match ccx.tcx.def_map.find(cur.id) { - Some(ast::def_variant(*)) => { - add_to_set(ccx.tcx, &found, - variant_opt(ccx.tcx, cur.id)); - } - Some(ast::def_struct(*)) => { - add_to_set(ccx.tcx, &found, - lit(UnitLikeStructLit(cur.id))); - } - Some(ast::def_const(const_did)) => { - add_to_set(ccx.tcx, &found, - lit(ConstLit(const_did))); - } - _ => {} - } - } - ast::pat_enum(*) | ast::pat_struct(*) => { - // This could be one of: a tuple-like enum variant, a - // struct-like enum variant, or a struct. - match ccx.tcx.def_map.find(cur.id) { - Some(ast::def_variant(*)) => { - add_to_set(ccx.tcx, &found, - variant_opt(ccx.tcx, cur.id)); - } - _ => {} - } - } - ast::pat_range(l1, l2) => { - add_to_set(ccx.tcx, &found, range(l1, l2)); - } - ast::pat_vec(elems, tail) => { - let opt = match tail { - None => vec_len_eq(elems.len()), - Some(_) => vec_len_ge(elems.len()) - }; - add_to_set(ccx.tcx, &found, opt); - } - _ => {} - } - } - return dvec::unwrap(move found); -} - -fn extract_variant_args(bcx: block, pat_id: ast::node_id, - vdefs: {enm: def_id, var: def_id}, - val: ValueRef) - -> {vals: ~[ValueRef], bcx: block} -{ - let _icx = bcx.insn_ctxt("alt::extract_variant_args"); - let ccx = bcx.fcx.ccx; - let enum_ty_substs = match ty::get(node_id_type(bcx, pat_id)).sty { - ty::ty_enum(id, ref substs) => { - assert id == vdefs.enm; - /*bad*/copy (*substs).tps - } - _ => bcx.sess().bug(~"extract_variant_args: pattern has non-enum type") - }; - let mut blobptr = val; - let variants = ty::enum_variants(ccx.tcx, vdefs.enm); - let size = ty::enum_variant_with_id(ccx.tcx, vdefs.enm, - vdefs.var).args.len(); - if size > 0u && (*variants).len() != 1u { - let enumptr = - PointerCast(bcx, val, T_opaque_enum_ptr(ccx)); - blobptr = GEPi(bcx, enumptr, [0u, 1u]); - } - let vdefs_tg = vdefs.enm; - let vdefs_var = vdefs.var; - let args = do vec::from_fn(size) |i| { - GEP_enum(bcx, blobptr, vdefs_tg, vdefs_var, - /*bad*/copy enum_ty_substs, i) - }; - return {vals: args, bcx: bcx}; -} - -fn extract_vec_elems(bcx: block, pat_id: ast::node_id, - elem_count: uint, tail: bool, val: ValueRef) - -> {vals: ~[ValueRef], bcx: block} -{ - let _icx = bcx.insn_ctxt("alt::extract_vec_elems"); - let vt = tvec::vec_types(bcx, node_id_type(bcx, pat_id)); - let unboxed = load_if_immediate(bcx, val, vt.vec_ty); - let (base, len) = tvec::get_base_and_len(bcx, unboxed, vt.vec_ty); - - let mut elems = do vec::from_fn(elem_count) |i| { - GEPi(bcx, base, ~[i]) - }; - if tail { - let tail_offset = Mul(bcx, vt.llunit_size, - C_int(bcx.ccx(), elem_count as int) - ); - let tail_begin = tvec::pointer_add(bcx, base, tail_offset); - let tail_len = Sub(bcx, len, tail_offset); - let tail_ty = ty::mk_evec(bcx.tcx(), - {ty: vt.unit_ty, mutbl: ast::m_imm}, - ty::vstore_slice(ty::re_static) - ); - let scratch = scratch_datum(bcx, tail_ty, false); - Store(bcx, tail_begin, - GEPi(bcx, scratch.val, [0u, abi::slice_elt_base]) - ); - Store(bcx, tail_len, - GEPi(bcx, scratch.val, [0u, abi::slice_elt_len]) - ); - elems.push(scratch.val); - scratch.add_clean(bcx); - } - return {vals: elems, bcx: bcx}; -} - -// NB: This function does not collect fields from struct-like enum variants. -fn collect_record_or_struct_fields(bcx: block, m: &[@Match], col: uint) -> - ~[ast::ident] { - let mut fields: ~[ast::ident] = ~[]; - for vec::each(m) |br| { - match /*bad*/copy br.pats[col].node { - ast::pat_rec(fs, _) => extend(&mut fields, fs), - ast::pat_struct(_, fs, _) => { - match ty::get(node_id_type(bcx, br.pats[col].id)).sty { - ty::ty_struct(*) => extend(&mut fields, fs), - _ => () - } - } - _ => () - } - } - return fields; - - fn extend(idents: &mut ~[ast::ident], field_pats: &[ast::field_pat]) { - for field_pats.each |field_pat| { - let field_ident = field_pat.ident; - if !vec::any(*idents, |x| *x == field_ident) { - idents.push(field_ident); - } - } - } -} - -fn root_pats_as_necessary(bcx: block, m: &[@Match], - col: uint, val: ValueRef) -{ - for vec::each(m) |br| { - let pat_id = br.pats[col].id; - - match bcx.ccx().maps.root_map.find({id:pat_id, derefs:0u}) { - None => (), - Some(scope_id) => { - // Note: the scope_id will always be the id of the alt. See - // the extended comment in rustc::middle::borrowck::preserve() - // for details (look for the case covering cat_discr). - - let datum = Datum {val: val, ty: node_id_type(bcx, pat_id), - mode: ByRef, source: FromLvalue}; - datum.root(bcx, scope_id); - return; // if we kept going, we'd only re-root the same value - } - } - } -} - -// Macro for deciding whether any of the remaining matches fit a given kind of -// pattern. Note that, because the macro is well-typed, either ALL of the -// matches should fit that sort of pattern or NONE (however, some of the -// matches may be wildcards like _ or identifiers). -macro_rules! any_pat ( - ($m:expr, $pattern:pat) => ( - vec::any($m, |br| { - match br.pats[col].node { - $pattern => true, - _ => false - } - }) - ) -) - -fn any_box_pat(m: &[@Match], col: uint) -> bool { - any_pat!(m, ast::pat_box(_)) -} - -fn any_uniq_pat(m: &[@Match], col: uint) -> bool { - any_pat!(m, ast::pat_uniq(_)) -} - -fn any_region_pat(m: &[@Match], col: uint) -> bool { - any_pat!(m, ast::pat_region(_)) -} - -fn any_tup_pat(m: &[@Match], col: uint) -> bool { - any_pat!(m, ast::pat_tup(_)) -} - -fn any_tuple_struct_pat(bcx: block, m: &[@Match], col: uint) -> bool { - vec::any(m, |br| { - let pat = br.pats[col]; - match pat.node { - ast::pat_enum(_, Some(_)) => { - match bcx.tcx().def_map.find(pat.id) { - Some(ast::def_struct(*)) => true, - _ => false - } - } - _ => false - } - }) -} - -type mk_fail = fn@() -> BasicBlockRef; - -fn pick_col(m: &[@Match]) -> uint { - fn score(p: @ast::pat) -> uint { - match p.node { - ast::pat_lit(_) | ast::pat_enum(_, _) | ast::pat_range(_, _) => 1u, - ast::pat_ident(_, _, Some(p)) => score(p), - _ => 0u - } - } - let scores = vec::to_mut(vec::from_elem(m[0].pats.len(), 0u)); - for vec::each(m) |br| { - let mut i = 0u; - for vec::each(br.pats) |p| { scores[i] += score(*p); i += 1u; } - } - let mut max_score = 0u; - let mut best_col = 0u; - let mut i = 0u; - for vec::each(scores) |score| { - let score = *score; - - // Irrefutable columns always go first, they'd only be duplicated in - // the branches. - if score == 0u { return i; } - // If no irrefutable ones are found, we pick the one with the biggest - // branching factor. - if score > max_score { max_score = score; best_col = i; } - i += 1u; - } - return best_col; -} - -enum branch_kind { no_branch, single, switch, compare, compare_vec_len, } - -impl branch_kind : cmp::Eq { - pure fn eq(&self, other: &branch_kind) -> bool { - ((*self) as uint) == ((*other) as uint) - } - pure fn ne(&self, other: &branch_kind) -> bool { !(*self).eq(other) } -} - -// Compiles a comparison between two things. -fn compare_values(cx: block, lhs: ValueRef, rhs: ValueRef, rhs_t: ty::t) -> - Result { - let _icx = cx.insn_ctxt("compare_values"); - if ty::type_is_scalar(rhs_t) { - let rs = compare_scalar_types(cx, lhs, rhs, rhs_t, ast::eq); - return rslt(rs.bcx, rs.val); - } - - match ty::get(rhs_t).sty { - ty::ty_estr(ty::vstore_uniq) => { - let scratch_result = scratch_datum(cx, ty::mk_bool(cx.tcx()), - false); - let scratch_lhs = alloca(cx, val_ty(lhs)); - Store(cx, lhs, scratch_lhs); - let scratch_rhs = alloca(cx, val_ty(rhs)); - Store(cx, rhs, scratch_rhs); - let did = cx.tcx().lang_items.uniq_str_eq_fn(); - let bcx = callee::trans_rtcall_or_lang_call(cx, did, - ~[scratch_lhs, - scratch_rhs], - expr::SaveIn( - scratch_result.val)); - return scratch_result.to_result(bcx); - } - ty::ty_estr(_) => { - let scratch_result = scratch_datum(cx, ty::mk_bool(cx.tcx()), - false); - let did = cx.tcx().lang_items.str_eq_fn(); - let bcx = callee::trans_rtcall_or_lang_call(cx, did, - ~[lhs, rhs], - expr::SaveIn( - scratch_result.val)); - return scratch_result.to_result(bcx); - } - _ => { - cx.tcx().sess.bug(~"only scalars and strings supported in \ - compare_values"); - } - } -} - -fn store_non_ref_bindings(bcx: block, - data: &ArmData, - opt_temp_cleanups: Option<&DVec>) - -> block -{ - /*! - * - * For each copy/move binding, copy the value from the value - * being matched into its final home. This code executes once - * one of the patterns for a given arm has completely matched. - * It adds temporary cleanups to the `temp_cleanups` array, - * if one is provided. - */ - - let mut bcx = bcx; - for data.bindings_map.each_value |binding_info| { - match binding_info.trmode { - TrByValue(is_move, lldest) => { - let llval = Load(bcx, binding_info.llmatch); // get a T* - let datum = Datum {val: llval, ty: binding_info.ty, - mode: ByRef, source: FromLvalue}; - bcx = { - if is_move { - datum.move_to(bcx, INIT, lldest) - } else { - datum.copy_to(bcx, INIT, lldest) - } - }; - - for opt_temp_cleanups.each |temp_cleanups| { - add_clean_temp_mem(bcx, lldest, binding_info.ty); - temp_cleanups.push(lldest); - } - } - TrByRef | TrByImplicitRef => {} - } - } - return bcx; -} - -fn insert_lllocals(bcx: block, - data: &ArmData, - add_cleans: bool) -> block { - /*! - * - * For each binding in `data.bindings_map`, adds an appropriate entry into - * the `fcx.lllocals` map. If add_cleans is true, then adds cleanups for - * the bindings. */ - - for data.bindings_map.each_value |binding_info| { - let llval = match binding_info.trmode { - // By value bindings: use the stack slot that we - // copied/moved the value into - TrByValue(_, lldest) => { - if add_cleans { - add_clean(bcx, lldest, binding_info.ty); - } - - lldest - } - - // By ref binding: use the ptr into the matched value - TrByRef => { - binding_info.llmatch - } - - // Ugly: for implicit ref, we actually want a T*, but - // we have a T**, so we had to load. This will go away - // once implicit refs go away. - TrByImplicitRef => { - Load(bcx, binding_info.llmatch) - } - }; - - bcx.fcx.lllocals.insert(binding_info.id, - local_mem(llval)); - } - return bcx; -} - -fn compile_guard(bcx: block, - guard_expr: @ast::expr, - data: &ArmData, - m: &[@Match], - vals: &[ValueRef], - chk: Option) - -> block -{ - debug!("compile_guard(bcx=%s, guard_expr=%s, m=%s, vals=%?)", - bcx.to_str(), - bcx.expr_to_str(guard_expr), - matches_to_str(bcx, m), - vals.map(|v| bcx.val_str(*v))); - let _indenter = indenter(); - - let mut bcx = bcx; - let temp_cleanups = DVec(); - bcx = store_non_ref_bindings(bcx, data, Some(&temp_cleanups)); - bcx = insert_lllocals(bcx, data, false); - - let val = unpack_result!(bcx, { - do with_scope_result(bcx, guard_expr.info(), - ~"guard") |bcx| { - expr::trans_to_datum(bcx, guard_expr).to_result() - } - }); - - // Revoke the temp cleanups now that the guard successfully executed. - for temp_cleanups.each |llval| { - revoke_clean(bcx, *llval); - } - - return do with_cond(bcx, Not(bcx, val)) |bcx| { - // Guard does not match: free the values we copied, - // and remove all bindings from the lllocals table - let bcx = drop_bindings(bcx, data); - compile_submatch(bcx, m, vals, chk); - bcx - }; - - fn drop_bindings(bcx: block, data: &ArmData) -> block { - let mut bcx = bcx; - for data.bindings_map.each_value |binding_info| { - match binding_info.trmode { - TrByValue(_, llval) => { - bcx = glue::drop_ty(bcx, llval, binding_info.ty); - } - TrByRef | TrByImplicitRef => {} - } - bcx.fcx.lllocals.remove(binding_info.id); - } - return bcx; - } -} - -fn compile_submatch(bcx: block, - m: &[@Match], - vals: &[ValueRef], - chk: Option) -{ - debug!("compile_submatch(bcx=%s, m=%s, vals=%?)", - bcx.to_str(), - matches_to_str(bcx, m), - vals.map(|v| bcx.val_str(*v))); - let _indenter = indenter(); - - /* - For an empty match, a fall-through case must exist - */ - assert(m.len() > 0u || chk.is_some()); - let _icx = bcx.insn_ctxt("alt::compile_submatch"); - let mut bcx = bcx; - let tcx = bcx.tcx(), dm = tcx.def_map; - if m.len() == 0u { - Br(bcx, chk.get()()); - return; - } - if m[0].pats.len() == 0u { - let data = m[0].data; - match data.arm.guard { - Some(guard_expr) => { - bcx = compile_guard(bcx, guard_expr, m[0].data, - vec::view(m, 1, m.len()), - vals, chk); - } - _ => () - } - Br(bcx, data.bodycx.llbb); - return; - } - - let col = pick_col(m); - let val = vals[col]; - let m = { - if has_nested_bindings(m, col) { - expand_nested_bindings(bcx, m, col, val) - } else { - m.to_vec() - } - }; - - let vals_left = vec::append(vec::slice(vals, 0u, col), - vec::view(vals, col + 1u, vals.len())); - let ccx = bcx.fcx.ccx; - let mut pat_id = 0; - for vec::each(m) |br| { - // Find a real id (we're adding placeholder wildcard patterns, but - // each column is guaranteed to have at least one real pattern) - if pat_id == 0 { pat_id = br.pats[col].id; } - } - - root_pats_as_necessary(bcx, m, col, val); - - let rec_fields = collect_record_or_struct_fields(bcx, m, col); - if rec_fields.len() > 0 { - let pat_ty = node_id_type(bcx, pat_id); - do expr::with_field_tys(tcx, pat_ty, None) |_has_dtor, field_tys| { - let rec_vals = rec_fields.map(|field_name| { - let ix = ty::field_idx_strict(tcx, *field_name, field_tys); - GEPi(bcx, val, struct_field(ix)) - }); - compile_submatch( - bcx, - enter_rec_or_struct(bcx, dm, m, col, rec_fields, val), - vec::append(rec_vals, vals_left), - chk); - } - return; - } - - if any_tup_pat(m, col) { - let tup_ty = node_id_type(bcx, pat_id); - let n_tup_elts = match /*bad*/copy ty::get(tup_ty).sty { - ty::ty_tup(elts) => elts.len(), - _ => ccx.sess.bug(~"non-tuple type in tuple pattern") - }; - let tup_vals = vec::from_fn(n_tup_elts, |i| GEPi(bcx, val, [0u, i])); - compile_submatch(bcx, enter_tup(bcx, dm, m, col, val, n_tup_elts), - vec::append(tup_vals, vals_left), chk); - return; - } - - if any_tuple_struct_pat(bcx, m, col) { - let struct_ty = node_id_type(bcx, pat_id); - let struct_element_count; - match ty::get(struct_ty).sty { - ty::ty_struct(struct_id, _) => { - struct_element_count = - ty::lookup_struct_fields(tcx, struct_id).len(); - } - _ => { - ccx.sess.bug(~"non-struct type in tuple struct pattern"); - } - } - - let llstructvals = vec::from_fn( - struct_element_count, |i| GEPi(bcx, val, struct_field(i))); - compile_submatch(bcx, - enter_tuple_struct(bcx, dm, m, col, val, - struct_element_count), - vec::append(llstructvals, vals_left), - chk); - return; - } - - // Unbox in case of a box field - if any_box_pat(m, col) { - let llbox = Load(bcx, val); - let box_no_addrspace = non_gc_box_cast(bcx, llbox); - let unboxed = - GEPi(bcx, box_no_addrspace, [0u, abi::box_field_body]); - compile_submatch(bcx, enter_box(bcx, dm, m, col, val), - vec::append(~[unboxed], vals_left), chk); - return; - } - - if any_uniq_pat(m, col) { - let llbox = Load(bcx, val); - let box_no_addrspace = non_gc_box_cast(bcx, llbox); - let unboxed = - GEPi(bcx, box_no_addrspace, [0u, abi::box_field_body]); - compile_submatch(bcx, enter_uniq(bcx, dm, m, col, val), - vec::append(~[unboxed], vals_left), chk); - return; - } - - if any_region_pat(m, col) { - let loaded_val = Load(bcx, val); - compile_submatch(bcx, enter_region(bcx, dm, m, col, val), - vec::append(~[loaded_val], vals_left), chk); - return; - } - - // Decide what kind of branch we need - let opts = get_options(ccx, m, col); - let mut kind = no_branch; - let mut test_val = val; - if opts.len() > 0u { - match opts[0] { - var(_, vdef) => { - if (*ty::enum_variants(tcx, vdef.enm)).len() == 1u { - kind = single; - } else { - let enumptr = - PointerCast(bcx, val, T_opaque_enum_ptr(ccx)); - let discrimptr = GEPi(bcx, enumptr, [0u, 0u]); - test_val = Load(bcx, discrimptr); - kind = switch; - } - } - lit(_) => { - let pty = node_id_type(bcx, pat_id); - test_val = load_if_immediate(bcx, val, pty); - kind = if ty::type_is_integral(pty) { switch } - else { compare }; - } - range(_, _) => { - test_val = Load(bcx, val); - kind = compare; - }, - vec_len_eq(_) | vec_len_ge(_) => { - let vt = tvec::vec_types(bcx, node_id_type(bcx, pat_id)); - let unboxed = load_if_immediate(bcx, val, vt.vec_ty); - let (_, len) = tvec::get_base_and_len( - bcx, unboxed, vt.vec_ty - ); - test_val = SDiv(bcx, len, vt.llunit_size); - kind = compare_vec_len; - } - } - } - for vec::each(opts) |o| { - match *o { - range(_, _) => { kind = compare; break } - _ => () - } - } - let else_cx = match kind { - no_branch | single => bcx, - _ => sub_block(bcx, ~"match_else") - }; - let sw = if kind == switch { - Switch(bcx, test_val, else_cx.llbb, opts.len()) - } else { - C_int(ccx, 0) // Placeholder for when not using a switch - }; - - let defaults = enter_default(else_cx, dm, m, col, val); - let exhaustive = chk.is_none() && defaults.len() == 0u; - let len = opts.len(); - let mut i = 0u; - - // Compile subtrees for each option - for vec::each(opts) |opt| { - i += 1u; - let mut opt_cx = else_cx; - if !exhaustive || i < len { - opt_cx = sub_block(bcx, ~"match_case"); - match kind { - single => Br(bcx, opt_cx.llbb), - switch => { - match trans_opt(bcx, opt) { - single_result(r) => { - llvm::LLVMAddCase(sw, r.val, opt_cx.llbb); - bcx = r.bcx; - } - _ => { - bcx.sess().bug( - ~"in compile_submatch, expected \ - trans_opt to return a single_result") - } - } - } - compare => { - let t = node_id_type(bcx, pat_id); - let Result {bcx: after_cx, val: matches} = { - do with_scope_result(bcx, None, - ~"compare_scope") |bcx| { - match trans_opt(bcx, opt) { - single_result( - Result {bcx, val}) => { - compare_values(bcx, test_val, val, t) - } - lower_bound( - Result {bcx, val}) => { - compare_scalar_types( - bcx, test_val, val, - t, ast::ge) - } - range_result( - Result {val: vbegin, _}, - Result {bcx, val: vend}) => { - let Result {bcx, val: llge} = - compare_scalar_types( - bcx, test_val, - vbegin, t, ast::ge); - let Result {bcx, val: llle} = - compare_scalar_types( - bcx, test_val, vend, - t, ast::le); - rslt(bcx, And(bcx, llge, llle)) - } - } - } - }; - bcx = sub_block(after_cx, ~"compare_next"); - CondBr(after_cx, matches, opt_cx.llbb, bcx.llbb); - } - compare_vec_len => { - let Result {bcx: after_cx, val: matches} = { - do with_scope_result(bcx, None, - ~"compare_vec_len_scope") |bcx| { - match trans_opt(bcx, opt) { - single_result( - Result {bcx, val}) => { - let value = compare_scalar_values( - bcx, test_val, val, - signed_int, ast::eq); - rslt(bcx, value) - } - lower_bound( - Result {bcx, val: val}) => { - let value = compare_scalar_values( - bcx, test_val, val, - signed_int, ast::ge); - rslt(bcx, value) - } - range_result( - Result {val: vbegin, _}, - Result {bcx, val: vend}) => { - let llge = - compare_scalar_values( - bcx, test_val, - vbegin, signed_int, ast::ge); - let llle = - compare_scalar_values( - bcx, test_val, vend, - signed_int, ast::le); - rslt(bcx, And(bcx, llge, llle)) - } - } - } - }; - bcx = sub_block(after_cx, ~"compare_vec_len_next"); - CondBr(after_cx, matches, opt_cx.llbb, bcx.llbb); - } - _ => () - } - } else if kind == compare || kind == compare_vec_len { - Br(bcx, else_cx.llbb); - } - - let mut size = 0u; - let mut unpacked = ~[]; - match *opt { - var(_, vdef) => { - let args = extract_variant_args(opt_cx, pat_id, vdef, val); - size = args.vals.len(); - unpacked = /*bad*/copy args.vals; - opt_cx = args.bcx; - } - vec_len_eq(n) | vec_len_ge(n) => { - let tail = match *opt { - vec_len_ge(_) => true, - _ => false - }; - let args = extract_vec_elems(opt_cx, pat_id, n, tail, val); - size = args.vals.len(); - unpacked = /*bad*/copy args.vals; - opt_cx = args.bcx; - } - lit(_) | range(_, _) => () - } - let opt_ms = enter_opt(opt_cx, m, opt, col, size, val); - let opt_vals = vec::append(unpacked, vals_left); - compile_submatch(opt_cx, opt_ms, opt_vals, chk); - } - - // Compile the fall-through case, if any - if !exhaustive { - if kind == compare || kind == compare_vec_len { - Br(bcx, else_cx.llbb); - } - if kind != single { - compile_submatch(else_cx, defaults, vals_left, chk); - } - } -} - -fn trans_alt(bcx: block, - alt_expr: @ast::expr, - discr_expr: @ast::expr, - arms: ~[ast::arm], - dest: Dest) -> block { - let _icx = bcx.insn_ctxt("alt::trans_alt"); - do with_scope(bcx, alt_expr.info(), ~"alt") |bcx| { - trans_alt_inner(bcx, discr_expr, arms, dest) - } -} - -fn trans_alt_inner(scope_cx: block, - discr_expr: @ast::expr, - arms: &[ast::arm], - dest: Dest) -> block { - let _icx = scope_cx.insn_ctxt("alt::trans_alt_inner"); - let mut bcx = scope_cx; - let tcx = bcx.tcx(); - - let discr_datum = unpack_datum!(bcx, { - expr::trans_to_datum(bcx, discr_expr) - }); - if bcx.unreachable { - return bcx; - } - - let mut arm_datas = ~[], matches = ~[]; - for vec::each(arms) |arm| { - let body = scope_block(bcx, arm.body.info(), ~"case_body"); - - // Create the bindings map, which is a mapping from each binding name - // to an alloca() that will be the value for that local variable. - // Note that we use the names because each binding will have many ids - // from the various alternatives. - let bindings_map = HashMap(); - do pat_bindings(tcx.def_map, arm.pats[0]) |bm, p_id, s, path| { - let ident = path_to_ident(path); - let variable_ty = node_id_type(bcx, p_id); - let llvariable_ty = type_of::type_of(bcx.ccx(), variable_ty); - - let llmatch, trmode; - match bm { - ast::bind_by_value | ast::bind_by_move => { - // in this case, the type of the variable will be T, - // but we need to store a *T - let is_move = (bm == ast::bind_by_move); - llmatch = alloca(bcx, T_ptr(llvariable_ty)); - trmode = TrByValue(is_move, alloca(bcx, llvariable_ty)); - } - ast::bind_infer => { - // in this case also, the type of the variable will be T, - // but we need to store a *T - let is_move = match tcx.value_modes.find(p_id) { - None => { - tcx.sess.span_bug(s, ~"no value mode"); - } - Some(MoveValue) => true, - Some(CopyValue) | Some(ReadValue) => false - }; - llmatch = alloca(bcx, T_ptr(llvariable_ty)); - trmode = TrByValue(is_move, alloca(bcx, llvariable_ty)); - } - ast::bind_by_ref(_) => { - llmatch = alloca(bcx, llvariable_ty); - trmode = TrByRef; - } - }; - bindings_map.insert(ident, BindingInfo { - llmatch: llmatch, trmode: trmode, - id: p_id, ty: variable_ty - }); - } - - let arm_data = @ArmData {bodycx: body, - arm: arm, - bindings_map: bindings_map}; - arm_datas.push(arm_data); - for vec::each(arm.pats) |p| { - matches.push(@Match {pats: ~[*p], data: arm_data}); - } - } - - let t = node_id_type(bcx, discr_expr.id); - let chk = { - if ty::type_is_empty(tcx, t) { - // Special case for empty types - let fail_cx = @mut None; - Some(|| mk_fail(scope_cx, discr_expr.span, - ~"scrutinizing value that can't exist", fail_cx)) - } else { - None - } - }; - let lldiscr = discr_datum.to_ref_llval(bcx); - compile_submatch(bcx, matches, ~[lldiscr], chk); - - let arm_cxs = DVec(); - for arm_datas.each |arm_data| { - let mut bcx = arm_data.bodycx; - - // If this arm has a guard, then the various by-value bindings have - // already been copied into their homes. If not, we do it here. This - // is just to reduce code space. See extensive comment at the start - // of the file for more details. - if arm_data.arm.guard.is_none() { - bcx = store_non_ref_bindings(bcx, *arm_data, None); - } - - // insert bindings into the lllocals map and add cleanups - bcx = insert_lllocals(bcx, *arm_data, true); - - bcx = controlflow::trans_block(bcx, arm_data.arm.body, dest); - bcx = trans_block_cleanups(bcx, block_cleanups(arm_data.bodycx)); - arm_cxs.push(bcx); - } - - return controlflow::join_blocks(scope_cx, dvec::unwrap(move arm_cxs)); - - fn mk_fail(bcx: block, sp: span, +msg: ~str, - finished: @mut Option) -> BasicBlockRef { - match *finished { Some(bb) => return bb, _ => () } - let fail_cx = sub_block(bcx, ~"case_fallthrough"); - controlflow::trans_fail(fail_cx, Some(sp), msg); - *finished = Some(fail_cx.llbb); - return fail_cx.llbb; - } -} - -enum IrrefutablePatternBindingMode { - // Stores the association between node ID and LLVM value in `lllocals`. - BindLocal, - // Stores the association between node ID and LLVM value in `llargs`. - BindArgument -} - -// Not alt-related, but similar to the pattern-munging code above -fn bind_irrefutable_pat(bcx: block, - pat: @ast::pat, - val: ValueRef, - make_copy: bool, - binding_mode: IrrefutablePatternBindingMode) - -> block { - let _icx = bcx.insn_ctxt("alt::bind_irrefutable_pat"); - let ccx = bcx.fcx.ccx; - let mut bcx = bcx; - - // Necessary since bind_irrefutable_pat is called outside trans_alt - match /*bad*/copy pat.node { - ast::pat_ident(_, _,inner) => { - if pat_is_variant_or_struct(bcx.tcx().def_map, pat) { - return bcx; - } - - if make_copy { - let binding_ty = node_id_type(bcx, pat.id); - let datum = Datum {val: val, ty: binding_ty, - mode: ByRef, source: FromRvalue}; - let scratch = scratch_datum(bcx, binding_ty, false); - datum.copy_to_datum(bcx, INIT, scratch); - match binding_mode { - BindLocal => { - bcx.fcx.lllocals.insert(pat.id, - local_mem(scratch.val)); - } - BindArgument => { - bcx.fcx.llargs.insert(pat.id, - local_mem(scratch.val)); - } - } - add_clean(bcx, scratch.val, binding_ty); - } else { - match binding_mode { - BindLocal => { - bcx.fcx.lllocals.insert(pat.id, local_mem(val)); - } - BindArgument => { - bcx.fcx.llargs.insert(pat.id, local_mem(val)); - } - } - } - - for inner.each |inner_pat| { - bcx = bind_irrefutable_pat( - bcx, *inner_pat, val, true, binding_mode); - } - } - ast::pat_enum(_, sub_pats) => { - match bcx.tcx().def_map.find(pat.id) { - Some(ast::def_variant(*)) => { - let pat_def = ccx.tcx.def_map.get(pat.id); - let vdefs = ast_util::variant_def_ids(pat_def); - let args = extract_variant_args(bcx, pat.id, vdefs, val); - for sub_pats.each |sub_pat| { - for vec::eachi(args.vals) |i, argval| { - bcx = bind_irrefutable_pat(bcx, - sub_pat[i], - *argval, - make_copy, - binding_mode); - } - } - } - Some(ast::def_struct(*)) => { - match sub_pats { - None => { - // This is a unit-like struct. Nothing to do here. - } - Some(elems) => { - // This is the tuple variant case. - for vec::eachi(elems) |i, elem| { - let fldptr = GEPi(bcx, val, struct_field(i)); - bcx = bind_irrefutable_pat(bcx, - *elem, - fldptr, - make_copy, - binding_mode); - } - } - } - } - _ => { - // Nothing to do here. - } - } - } - ast::pat_rec(fields, _) | ast::pat_struct(_, fields, _) => { - let tcx = bcx.tcx(); - let pat_ty = node_id_type(bcx, pat.id); - do expr::with_field_tys(tcx, pat_ty, None) |_hd, field_tys| { - for vec::each(fields) |f| { - let ix = ty::field_idx_strict(tcx, f.ident, field_tys); - let fldptr = GEPi(bcx, val, struct_field(ix)); - bcx = bind_irrefutable_pat(bcx, - f.pat, - fldptr, - make_copy, - binding_mode); - } - } - } - ast::pat_tup(elems) => { - for vec::eachi(elems) |i, elem| { - let fldptr = GEPi(bcx, val, [0u, i]); - bcx = bind_irrefutable_pat(bcx, - *elem, - fldptr, - make_copy, - binding_mode); - } - } - ast::pat_box(inner) | ast::pat_uniq(inner) => { - let llbox = Load(bcx, val); - let unboxed = GEPi(bcx, llbox, [0u, abi::box_field_body]); - bcx = bind_irrefutable_pat(bcx, - inner, - unboxed, - true, - binding_mode); - } - ast::pat_region(inner) => { - let loaded_val = Load(bcx, val); - bcx = bind_irrefutable_pat(bcx, - inner, - loaded_val, - true, - binding_mode); - } - ast::pat_wild | ast::pat_lit(_) | ast::pat_range(_, _) | - ast::pat_vec(*) => () - } - return bcx; -} - -// Local Variables: -// mode: rust -// fill-column: 78; -// indent-tabs-mode: nil -// c-basic-offset: 4 -// buffer-file-coding-system: utf-8-unix -// End: diff --git a/src/librustc/middle/trans/base.rs b/src/librustc/middle/trans/base.rs index c20747b54b5..c3b4adeaf8b 100644 --- a/src/librustc/middle/trans/base.rs +++ b/src/librustc/middle/trans/base.rs @@ -41,7 +41,7 @@ use metadata::{csearch, cstore, decoder, encoder}; use middle::astencode; use middle::pat_util::*; use middle::resolve; -use middle::trans::alt; +use middle::trans::_match; use middle::trans::build::*; use middle::trans::callee; use middle::trans::common::*; @@ -1045,11 +1045,11 @@ fn init_local(bcx: block, local: @ast::local) -> block { bcx.to_str()); add_clean(bcx, llptr, ty); - return alt::bind_irrefutable_pat(bcx, - local.node.pat, - llptr, - false, - alt::BindLocal); + return _match::bind_irrefutable_pat(bcx, + local.node.pat, + llptr, + false, + _match::BindLocal); } fn trans_stmt(cx: block, s: ast::stmt) -> block { @@ -1597,11 +1597,11 @@ fn copy_args_to_allocas(fcx: fn_ctxt, } } - bcx = alt::bind_irrefutable_pat(bcx, - args[arg_n].pat, - llarg, - false, - alt::BindArgument); + bcx = _match::bind_irrefutable_pat(bcx, + args[arg_n].pat, + llarg, + false, + _match::BindArgument); fcx.llargs.insert(arg_id, local_mem(llarg)); diff --git a/src/librustc/middle/trans/debuginfo.rs b/src/librustc/middle/trans/debuginfo.rs index 78d19e9e0cb..10edfb2f929 100644 --- a/src/librustc/middle/trans/debuginfo.rs +++ b/src/librustc/middle/trans/debuginfo.rs @@ -266,7 +266,7 @@ fn create_block(cx: block) -> @metadata { let fname = /*bad*/copy start.file.name; let end = cx.sess().codemap.lookup_char_pos(sp.hi); let tg = LexicalBlockTag; - /*alt cached_metadata::<@metadata>( + /*match cached_metadata::<@metadata>( cache, tg, {|md| start == md.data.start && end == md.data.end}) { option::Some(md) { return md; } diff --git a/src/librustc/middle/trans/expr.rs b/src/librustc/middle/trans/expr.rs index d2254097106..ed9abea465b 100644 --- a/src/librustc/middle/trans/expr.rs +++ b/src/librustc/middle/trans/expr.rs @@ -528,7 +528,8 @@ fn trans_rvalue_dps_unadjusted(bcx: block, expr: @ast::expr, return controlflow::trans_if(bcx, cond, (*thn), els, dest); } ast::expr_match(discr, ref arms) => { - return alt::trans_alt(bcx, expr, discr, /*bad*/copy *arms, dest); + return _match::trans_match(bcx, expr, discr, /*bad*/copy *arms, + dest); } ast::expr_block(ref blk) => { return do base::with_scope(bcx, (*blk).info(), diff --git a/src/librustc/middle/typeck/check/_match.rs b/src/librustc/middle/typeck/check/_match.rs new file mode 100644 index 00000000000..7ff3dfcb073 --- /dev/null +++ b/src/librustc/middle/typeck/check/_match.rs @@ -0,0 +1,582 @@ +// Copyright 2012 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 middle::pat_util::{pat_is_binding, pat_is_const}; +use middle::pat_util::{pat_is_variant_or_struct}; +use middle::ty; +use middle::typeck::check::demand; + +use core::vec; +use std::map::HashMap; +use syntax::ast; +use syntax::ast_util::walk_pat; +use syntax::ast_util; +use syntax::print::pprust; + +fn check_match(fcx: @fn_ctxt, + expr: @ast::expr, + discrim: @ast::expr, + arms: ~[ast::arm]) -> bool { + let tcx = fcx.ccx.tcx; + let mut bot; + + let pattern_ty = fcx.infcx().next_ty_var(); + bot = check_expr_with(fcx, discrim, pattern_ty); + + // Typecheck the patterns first, so that we get types for all the + // bindings. + for arms.each |arm| { + let pcx = pat_ctxt { + fcx: fcx, + map: pat_id_map(tcx.def_map, arm.pats[0]), + match_region: ty::re_scope(expr.id), + block_region: ty::re_scope(arm.body.node.id) + }; + + for arm.pats.each |p| { check_pat(pcx, *p, pattern_ty);} + } + + // Now typecheck the blocks. + let mut result_ty = fcx.infcx().next_ty_var(); + let mut arm_non_bot = false; + for arms.each |arm| { + match arm.guard { + Some(e) => { check_expr_with(fcx, e, ty::mk_bool(tcx)); }, + None => () + } + if !check_block(fcx, arm.body) { arm_non_bot = true; } + let bty = fcx.node_ty(arm.body.node.id); + demand::suptype(fcx, arm.body.span, result_ty, bty); + } + bot |= !arm_non_bot; + if !arm_non_bot { result_ty = ty::mk_bot(tcx); } + fcx.write_ty(expr.id, result_ty); + return bot; +} + +struct pat_ctxt { + fcx: @fn_ctxt, + map: PatIdMap, + match_region: ty::Region, // Region for the match as a whole + block_region: ty::Region, // Region for the block of the arm +} + +fn check_pat_variant(pcx: pat_ctxt, pat: @ast::pat, path: @ast::path, + +subpats: Option<~[@ast::pat]>, expected: ty::t) { + + // Typecheck the path. + let fcx = pcx.fcx; + let tcx = pcx.fcx.ccx.tcx; + + let arg_types, kind_name; + + // structure_of requires type variables to be resolved. + // So when we pass in , it's an error if it + // contains type variables. + + // Check to see whether this is an enum or a struct. + match structure_of(pcx.fcx, pat.span, expected) { + ty::ty_enum(_, ref expected_substs) => { + // Lookup the enum and variant def ids: + let v_def = lookup_def(pcx.fcx, path.span, pat.id); + let v_def_ids = ast_util::variant_def_ids(v_def); + + // Assign the pattern the type of the *enum*, not the variant. + let enum_tpt = ty::lookup_item_type(tcx, v_def_ids.enm); + instantiate_path(pcx.fcx, path, enum_tpt, pat.span, pat.id, + pcx.block_region); + + // check that the type of the value being matched is a subtype + // of the type of the pattern: + let pat_ty = fcx.node_ty(pat.id); + demand::suptype(fcx, pat.span, pat_ty, expected); + + // Get the expected types of the arguments. + arg_types = { + let vinfo = + ty::enum_variant_with_id( + tcx, v_def_ids.enm, v_def_ids.var); + let var_tpt = ty::lookup_item_type(tcx, v_def_ids.var); + vinfo.args.map(|t| { + if var_tpt.bounds.len() == expected_substs.tps.len() { + ty::subst(tcx, expected_substs, *t) + } + else { + *t // In this case, an error was already signaled + // anyway + } + }) + }; + + kind_name = "variant"; + } + ty::ty_struct(struct_def_id, ref expected_substs) => { + // Assign the pattern the type of the struct. + let struct_tpt = ty::lookup_item_type(tcx, struct_def_id); + instantiate_path(pcx.fcx, path, struct_tpt, pat.span, pat.id, + pcx.block_region); + + // Check that the type of the value being matched is a subtype of + // the type of the pattern. + let pat_ty = fcx.node_ty(pat.id); + demand::suptype(fcx, pat.span, pat_ty, expected); + + // Get the expected types of the arguments. + let class_fields = ty::struct_fields( + tcx, struct_def_id, expected_substs); + arg_types = class_fields.map(|field| field.mt.ty); + + kind_name = "structure"; + } + _ => { + tcx.sess.span_fatal( + pat.span, + fmt!("mismatched types: expected enum or structure but \ + found `%s`", + fcx.infcx().ty_to_str(expected))); + } + } + + let arg_len = arg_types.len(); + + // Count the number of subpatterns. + let subpats_len; + match subpats { + None => subpats_len = arg_len, + Some(ref subpats) => subpats_len = subpats.len() + } + + if arg_len > 0u { + // N-ary variant. + if arg_len != subpats_len { + let s = fmt!("this pattern has %u field%s, but the corresponding \ + %s has %u field%s", + subpats_len, + if subpats_len == 1u { ~"" } else { ~"s" }, + kind_name, + arg_len, + if arg_len == 1u { ~"" } else { ~"s" }); + // XXX: This should not be fatal. + tcx.sess.span_fatal(pat.span, s); + } + + do subpats.iter() |pats| { + for vec::each2(*pats, arg_types) |subpat, arg_ty| { + check_pat(pcx, *subpat, *arg_ty); + } + }; + } else if subpats_len > 0u { + tcx.sess.span_fatal + (pat.span, fmt!("this pattern has %u field%s, but the \ + corresponding %s has no fields", + subpats_len, + if subpats_len == 1u { ~"" } + else { ~"s" }, + kind_name)); + } +} + +/// `path` is the AST path item naming the type of this struct. +/// `fields` is the field patterns of the struct pattern. +/// `class_fields` describes the type of each field of the struct. +/// `class_id` is the ID of the struct. +/// `substitutions` are the type substitutions applied to this struct type +/// (e.g. K,V in HashMap). +/// `etc` is true if the pattern said '...' and false otherwise. +fn check_struct_pat_fields(pcx: pat_ctxt, + span: span, + path: @ast::path, + fields: ~[ast::field_pat], + class_fields: ~[ty::field_ty], + class_id: ast::def_id, + substitutions: &ty::substs, + etc: bool) { + let tcx = pcx.fcx.ccx.tcx; + + // Index the class fields. + let field_map = HashMap(); + for class_fields.eachi |i, class_field| { + field_map.insert(class_field.ident, i); + } + + // Typecheck each field. + let found_fields = HashMap(); + for fields.each |field| { + match field_map.find(field.ident) { + Some(index) => { + let class_field = class_fields[index]; + let field_type = ty::lookup_field_type(tcx, + class_id, + class_field.id, + substitutions); + check_pat(pcx, field.pat, field_type); + found_fields.insert(index, ()); + } + None => { + let name = pprust::path_to_str(path, tcx.sess.intr()); + tcx.sess.span_err(span, + fmt!("struct `%s` does not have a field + named `%s`", name, + tcx.sess.str_of(field.ident))); + } + } + } + + // Report an error if not all the fields were specified. + if !etc { + for class_fields.eachi |i, field| { + if found_fields.contains_key(i) { + loop; + } + tcx.sess.span_err(span, + fmt!("pattern does not mention field `%s`", + tcx.sess.str_of(field.ident))); + } + } +} + +fn check_struct_pat(pcx: pat_ctxt, pat_id: ast::node_id, span: span, + expected: ty::t, path: @ast::path, + +fields: ~[ast::field_pat], etc: bool, + class_id: ast::def_id, substitutions: &ty::substs) { + let fcx = pcx.fcx; + let tcx = pcx.fcx.ccx.tcx; + + let class_fields = ty::lookup_struct_fields(tcx, class_id); + + // Check to ensure that the struct is the one specified. + match tcx.def_map.find(pat_id) { + Some(ast::def_struct(supplied_def_id)) + if supplied_def_id == class_id => { + // OK. + } + Some(ast::def_struct(*)) | Some(ast::def_variant(*)) => { + let name = pprust::path_to_str(path, tcx.sess.intr()); + tcx.sess.span_err(span, + fmt!("mismatched types: expected `%s` but \ + found `%s`", + fcx.infcx().ty_to_str(expected), + name)); + } + _ => { + tcx.sess.span_bug(span, ~"resolve didn't write in class"); + } + } + + // Forbid pattern-matching structs with destructors. + if ty::has_dtor(tcx, class_id) { + tcx.sess.span_err(span, ~"deconstructing struct not allowed in \ + pattern (it has a destructor)"); + } + + check_struct_pat_fields(pcx, span, path, fields, class_fields, class_id, + substitutions, etc); +} + +fn check_struct_like_enum_variant_pat(pcx: pat_ctxt, + pat_id: ast::node_id, + span: span, + expected: ty::t, + path: @ast::path, + +fields: ~[ast::field_pat], + etc: bool, + enum_id: ast::def_id, + substitutions: &ty::substs) { + let fcx = pcx.fcx; + let tcx = pcx.fcx.ccx.tcx; + + // Find the variant that was specified. + match tcx.def_map.find(pat_id) { + Some(ast::def_variant(found_enum_id, variant_id)) + if found_enum_id == enum_id => { + // Get the struct fields from this struct-like enum variant. + let class_fields = ty::lookup_struct_fields(tcx, variant_id); + + check_struct_pat_fields(pcx, span, path, fields, class_fields, + variant_id, substitutions, etc); + } + Some(ast::def_struct(*)) | Some(ast::def_variant(*)) => { + let name = pprust::path_to_str(path, tcx.sess.intr()); + tcx.sess.span_err(span, + fmt!("mismatched types: expected `%s` but \ + found `%s`", + fcx.infcx().ty_to_str(expected), + name)); + } + _ => { + tcx.sess.span_bug(span, ~"resolve didn't write in variant"); + } + } +} + +// Pattern checking is top-down rather than bottom-up so that bindings get +// their types immediately. +fn check_pat(pcx: pat_ctxt, pat: @ast::pat, expected: ty::t) { + let fcx = pcx.fcx; + let tcx = pcx.fcx.ccx.tcx; + + match /*bad*/copy pat.node { + ast::pat_wild => { + fcx.write_ty(pat.id, expected); + } + ast::pat_lit(lt) => { + check_expr_with(fcx, lt, expected); + fcx.write_ty(pat.id, fcx.expr_ty(lt)); + } + ast::pat_range(begin, end) => { + check_expr_with(fcx, begin, expected); + check_expr_with(fcx, end, expected); + let b_ty = + fcx.infcx().resolve_type_vars_if_possible(fcx.expr_ty(begin)); + let e_ty = + fcx.infcx().resolve_type_vars_if_possible(fcx.expr_ty(end)); + debug!("pat_range beginning type: %?", b_ty); + debug!("pat_range ending type: %?", e_ty); + if !require_same_types( + tcx, Some(fcx.infcx()), false, pat.span, b_ty, e_ty, + || ~"mismatched types in range") + { + // no-op + } else if !ty::type_is_numeric(b_ty) { + tcx.sess.span_err(pat.span, ~"non-numeric type used in range"); + } else if !valid_range_bounds(fcx.ccx, begin, end) { + tcx.sess.span_err(begin.span, ~"lower range bound must be less \ + than upper"); + } + fcx.write_ty(pat.id, b_ty); + } + ast::pat_ident(*) if pat_is_const(tcx.def_map, pat) => { + let const_did = ast_util::def_id_of_def(tcx.def_map.get(pat.id)); + let const_tpt = ty::lookup_item_type(tcx, const_did); + fcx.write_ty(pat.id, const_tpt.ty); + } + ast::pat_ident(bm, name, sub) if pat_is_binding(tcx.def_map, pat) => { + let vid = lookup_local(fcx, pat.span, pat.id); + let mut typ = ty::mk_var(tcx, vid); + + match bm { + ast::bind_by_ref(mutbl) => { + // if the binding is like + // ref x | ref const x | ref mut x + // then the type of x is &M T where M is the mutability + // and T is the expected type + let region_var = + fcx.infcx().next_region_var_with_lb( + pat.span, pcx.block_region); + let mt = {ty: expected, mutbl: mutbl}; + let region_ty = ty::mk_rptr(tcx, region_var, mt); + demand::eqtype(fcx, pat.span, region_ty, typ); + } + // otherwise the type of x is the expected type T + ast::bind_by_value | ast::bind_by_move | ast::bind_infer => { + demand::eqtype(fcx, pat.span, expected, typ); + } + } + + let canon_id = pcx.map.get(ast_util::path_to_ident(name)); + if canon_id != pat.id { + let tv_id = lookup_local(fcx, pat.span, canon_id); + let ct = ty::mk_var(tcx, tv_id); + demand::eqtype(fcx, pat.span, ct, typ); + } + fcx.write_ty(pat.id, typ); + + debug!("(checking match) writing type for pat id %d", pat.id); + + match sub { + Some(p) => check_pat(pcx, p, expected), + _ => () + } + } + ast::pat_ident(_, path, _) => { + check_pat_variant(pcx, pat, path, Some(~[]), expected); + } + ast::pat_enum(path, subpats) => { + check_pat_variant(pcx, pat, path, subpats, expected); + } + ast::pat_rec(fields, etc) => { + let ex_fields = match structure_of(fcx, pat.span, expected) { + ty::ty_rec(fields) => fields, + _ => { + tcx.sess.span_fatal + (pat.span, + fmt!("mismatched types: expected `%s` but found record", + fcx.infcx().ty_to_str(expected))); + } + }; + let f_count = vec::len(fields); + let ex_f_count = vec::len(ex_fields); + if ex_f_count < f_count || !etc && ex_f_count > f_count { + tcx.sess.span_fatal + (pat.span, fmt!("mismatched types: expected a record \ + with %u fields, found one with %u \ + fields", + ex_f_count, f_count)); + } + + for fields.each |f| { + match vec::find(ex_fields, |a| f.ident == a.ident) { + Some(field) => { + check_pat(pcx, f.pat, field.mt.ty); + } + None => { + tcx.sess.span_fatal(pat.span, + fmt!("mismatched types: did not \ + expect a record with a field `%s`", + tcx.sess.str_of(f.ident))); + } + } + } + fcx.write_ty(pat.id, expected); + } + ast::pat_struct(path, fields, etc) => { + // Grab the class data that we care about. + let structure = structure_of(fcx, pat.span, expected); + match structure { + ty::ty_struct(cid, ref substs) => { + check_struct_pat(pcx, pat.id, pat.span, expected, path, + fields, etc, cid, substs); + } + ty::ty_enum(eid, ref substs) => { + check_struct_like_enum_variant_pat( + pcx, pat.id, pat.span, expected, path, fields, etc, eid, + substs); + } + _ => { + // XXX: This should not be fatal. + tcx.sess.span_fatal(pat.span, + fmt!("mismatched types: expected `%s` \ + but found struct", + fcx.infcx().ty_to_str(expected))); + } + } + + // Finally, write in the type. + fcx.write_ty(pat.id, expected); + } + ast::pat_tup(elts) => { + let ex_elts = match structure_of(fcx, pat.span, expected) { + ty::ty_tup(elts) => elts, + _ => { + tcx.sess.span_fatal + (pat.span, + fmt!("mismatched types: expected `%s`, found tuple", + fcx.infcx().ty_to_str(expected))); + } + }; + let e_count = vec::len(elts); + if e_count != vec::len(ex_elts) { + tcx.sess.span_fatal + (pat.span, fmt!("mismatched types: expected a tuple \ + with %u fields, found one with %u \ + fields", vec::len(ex_elts), e_count)); + } + let mut i = 0u; + for elts.each |elt| { + check_pat(pcx, *elt, ex_elts[i]); + i += 1u; + } + + fcx.write_ty(pat.id, expected); + } + ast::pat_box(inner) => { + match structure_of(fcx, pat.span, expected) { + ty::ty_box(e_inner) => { + check_pat(pcx, inner, e_inner.ty); + fcx.write_ty(pat.id, expected); + } + _ => { + tcx.sess.span_fatal( + pat.span, + ~"mismatched types: expected `" + + fcx.infcx().ty_to_str(expected) + + ~"` found box"); + } + } + } + ast::pat_uniq(inner) => { + match structure_of(fcx, pat.span, expected) { + ty::ty_uniq(e_inner) => { + check_pat(pcx, inner, e_inner.ty); + fcx.write_ty(pat.id, expected); + } + _ => { + tcx.sess.span_fatal( + pat.span, + ~"mismatched types: expected `" + + fcx.infcx().ty_to_str(expected) + + ~"` found uniq"); + } + } + } + ast::pat_region(inner) => { + match structure_of(fcx, pat.span, expected) { + ty::ty_rptr(_, e_inner) => { + check_pat(pcx, inner, e_inner.ty); + fcx.write_ty(pat.id, expected); + } + _ => { + tcx.sess.span_fatal( + pat.span, + ~"mismatched types: expected `" + + fcx.infcx().ty_to_str(expected) + + ~"` found borrowed pointer"); + } + } + } + ast::pat_vec(elts, tail) => { + let default_region_var = + fcx.infcx().next_region_var_with_lb( + pat.span, pcx.block_region + ); + + let (elt_type, region_var) = match structure_of( + fcx, pat.span, expected + ) { + ty::ty_evec(mt, vstore) => { + let region_var = match vstore { + ty::vstore_slice(r) => r, + ty::vstore_box | ty::vstore_uniq | ty::vstore_fixed(_) => { + default_region_var + } + }; + (mt, region_var) + } + ty::ty_unboxed_vec(mt) => { + (mt, default_region_var) + }, + _ => { + tcx.sess.span_fatal( + pat.span, + fmt!("mismatched type: expected `%s` but found vector", + fcx.infcx().ty_to_str(expected)) + ); + } + }; + for elts.each |elt| { + check_pat(pcx, *elt, elt_type.ty); + } + fcx.write_ty(pat.id, expected); + + match tail { + Some(tail_pat) => { + let slice_ty = ty::mk_evec(tcx, + {ty: elt_type.ty, mutbl: elt_type.mutbl}, + ty::vstore_slice(region_var) + ); + check_pat(pcx, tail_pat, slice_ty); + } + None => () + } + } + } +} + diff --git a/src/librustc/middle/typeck/check/alt.rs b/src/librustc/middle/typeck/check/alt.rs deleted file mode 100644 index 95bd9a39769..00000000000 --- a/src/librustc/middle/typeck/check/alt.rs +++ /dev/null @@ -1,582 +0,0 @@ -// Copyright 2012 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 middle::pat_util::{pat_is_binding, pat_is_const}; -use middle::pat_util::{pat_is_variant_or_struct}; -use middle::ty; -use middle::typeck::check::demand; - -use core::vec; -use std::map::HashMap; -use syntax::ast; -use syntax::ast_util::walk_pat; -use syntax::ast_util; -use syntax::print::pprust; - -fn check_alt(fcx: @fn_ctxt, - expr: @ast::expr, - discrim: @ast::expr, - arms: ~[ast::arm]) -> bool { - let tcx = fcx.ccx.tcx; - let mut bot; - - let pattern_ty = fcx.infcx().next_ty_var(); - bot = check_expr_with(fcx, discrim, pattern_ty); - - // Typecheck the patterns first, so that we get types for all the - // bindings. - for arms.each |arm| { - let pcx = pat_ctxt { - fcx: fcx, - map: pat_id_map(tcx.def_map, arm.pats[0]), - alt_region: ty::re_scope(expr.id), - block_region: ty::re_scope(arm.body.node.id) - }; - - for arm.pats.each |p| { check_pat(pcx, *p, pattern_ty);} - } - - // Now typecheck the blocks. - let mut result_ty = fcx.infcx().next_ty_var(); - let mut arm_non_bot = false; - for arms.each |arm| { - match arm.guard { - Some(e) => { check_expr_with(fcx, e, ty::mk_bool(tcx)); }, - None => () - } - if !check_block(fcx, arm.body) { arm_non_bot = true; } - let bty = fcx.node_ty(arm.body.node.id); - demand::suptype(fcx, arm.body.span, result_ty, bty); - } - bot |= !arm_non_bot; - if !arm_non_bot { result_ty = ty::mk_bot(tcx); } - fcx.write_ty(expr.id, result_ty); - return bot; -} - -struct pat_ctxt { - fcx: @fn_ctxt, - map: PatIdMap, - alt_region: ty::Region, // Region for the alt as a whole - block_region: ty::Region, // Region for the block of the arm -} - -fn check_pat_variant(pcx: pat_ctxt, pat: @ast::pat, path: @ast::path, - +subpats: Option<~[@ast::pat]>, expected: ty::t) { - - // Typecheck the path. - let fcx = pcx.fcx; - let tcx = pcx.fcx.ccx.tcx; - - let arg_types, kind_name; - - // structure_of requires type variables to be resolved. - // So when we pass in , it's an error if it - // contains type variables. - - // Check to see whether this is an enum or a struct. - match structure_of(pcx.fcx, pat.span, expected) { - ty::ty_enum(_, ref expected_substs) => { - // Lookup the enum and variant def ids: - let v_def = lookup_def(pcx.fcx, path.span, pat.id); - let v_def_ids = ast_util::variant_def_ids(v_def); - - // Assign the pattern the type of the *enum*, not the variant. - let enum_tpt = ty::lookup_item_type(tcx, v_def_ids.enm); - instantiate_path(pcx.fcx, path, enum_tpt, pat.span, pat.id, - pcx.block_region); - - // check that the type of the value being matched is a subtype - // of the type of the pattern: - let pat_ty = fcx.node_ty(pat.id); - demand::suptype(fcx, pat.span, pat_ty, expected); - - // Get the expected types of the arguments. - arg_types = { - let vinfo = - ty::enum_variant_with_id( - tcx, v_def_ids.enm, v_def_ids.var); - let var_tpt = ty::lookup_item_type(tcx, v_def_ids.var); - vinfo.args.map(|t| { - if var_tpt.bounds.len() == expected_substs.tps.len() { - ty::subst(tcx, expected_substs, *t) - } - else { - *t // In this case, an error was already signaled - // anyway - } - }) - }; - - kind_name = "variant"; - } - ty::ty_struct(struct_def_id, ref expected_substs) => { - // Assign the pattern the type of the struct. - let struct_tpt = ty::lookup_item_type(tcx, struct_def_id); - instantiate_path(pcx.fcx, path, struct_tpt, pat.span, pat.id, - pcx.block_region); - - // Check that the type of the value being matched is a subtype of - // the type of the pattern. - let pat_ty = fcx.node_ty(pat.id); - demand::suptype(fcx, pat.span, pat_ty, expected); - - // Get the expected types of the arguments. - let class_fields = ty::struct_fields( - tcx, struct_def_id, expected_substs); - arg_types = class_fields.map(|field| field.mt.ty); - - kind_name = "structure"; - } - _ => { - tcx.sess.span_fatal( - pat.span, - fmt!("mismatched types: expected enum or structure but \ - found `%s`", - fcx.infcx().ty_to_str(expected))); - } - } - - let arg_len = arg_types.len(); - - // Count the number of subpatterns. - let subpats_len; - match subpats { - None => subpats_len = arg_len, - Some(ref subpats) => subpats_len = subpats.len() - } - - if arg_len > 0u { - // N-ary variant. - if arg_len != subpats_len { - let s = fmt!("this pattern has %u field%s, but the corresponding \ - %s has %u field%s", - subpats_len, - if subpats_len == 1u { ~"" } else { ~"s" }, - kind_name, - arg_len, - if arg_len == 1u { ~"" } else { ~"s" }); - // XXX: This should not be fatal. - tcx.sess.span_fatal(pat.span, s); - } - - do subpats.iter() |pats| { - for vec::each2(*pats, arg_types) |subpat, arg_ty| { - check_pat(pcx, *subpat, *arg_ty); - } - }; - } else if subpats_len > 0u { - tcx.sess.span_fatal - (pat.span, fmt!("this pattern has %u field%s, but the \ - corresponding %s has no fields", - subpats_len, - if subpats_len == 1u { ~"" } - else { ~"s" }, - kind_name)); - } -} - -/// `path` is the AST path item naming the type of this struct. -/// `fields` is the field patterns of the struct pattern. -/// `class_fields` describes the type of each field of the struct. -/// `class_id` is the ID of the struct. -/// `substitutions` are the type substitutions applied to this struct type -/// (e.g. K,V in HashMap). -/// `etc` is true if the pattern said '...' and false otherwise. -fn check_struct_pat_fields(pcx: pat_ctxt, - span: span, - path: @ast::path, - fields: ~[ast::field_pat], - class_fields: ~[ty::field_ty], - class_id: ast::def_id, - substitutions: &ty::substs, - etc: bool) { - let tcx = pcx.fcx.ccx.tcx; - - // Index the class fields. - let field_map = HashMap(); - for class_fields.eachi |i, class_field| { - field_map.insert(class_field.ident, i); - } - - // Typecheck each field. - let found_fields = HashMap(); - for fields.each |field| { - match field_map.find(field.ident) { - Some(index) => { - let class_field = class_fields[index]; - let field_type = ty::lookup_field_type(tcx, - class_id, - class_field.id, - substitutions); - check_pat(pcx, field.pat, field_type); - found_fields.insert(index, ()); - } - None => { - let name = pprust::path_to_str(path, tcx.sess.intr()); - tcx.sess.span_err(span, - fmt!("struct `%s` does not have a field - named `%s`", name, - tcx.sess.str_of(field.ident))); - } - } - } - - // Report an error if not all the fields were specified. - if !etc { - for class_fields.eachi |i, field| { - if found_fields.contains_key(i) { - loop; - } - tcx.sess.span_err(span, - fmt!("pattern does not mention field `%s`", - tcx.sess.str_of(field.ident))); - } - } -} - -fn check_struct_pat(pcx: pat_ctxt, pat_id: ast::node_id, span: span, - expected: ty::t, path: @ast::path, - +fields: ~[ast::field_pat], etc: bool, - class_id: ast::def_id, substitutions: &ty::substs) { - let fcx = pcx.fcx; - let tcx = pcx.fcx.ccx.tcx; - - let class_fields = ty::lookup_struct_fields(tcx, class_id); - - // Check to ensure that the struct is the one specified. - match tcx.def_map.find(pat_id) { - Some(ast::def_struct(supplied_def_id)) - if supplied_def_id == class_id => { - // OK. - } - Some(ast::def_struct(*)) | Some(ast::def_variant(*)) => { - let name = pprust::path_to_str(path, tcx.sess.intr()); - tcx.sess.span_err(span, - fmt!("mismatched types: expected `%s` but \ - found `%s`", - fcx.infcx().ty_to_str(expected), - name)); - } - _ => { - tcx.sess.span_bug(span, ~"resolve didn't write in class"); - } - } - - // Forbid pattern-matching structs with destructors. - if ty::has_dtor(tcx, class_id) { - tcx.sess.span_err(span, ~"deconstructing struct not allowed in \ - pattern (it has a destructor)"); - } - - check_struct_pat_fields(pcx, span, path, fields, class_fields, class_id, - substitutions, etc); -} - -fn check_struct_like_enum_variant_pat(pcx: pat_ctxt, - pat_id: ast::node_id, - span: span, - expected: ty::t, - path: @ast::path, - +fields: ~[ast::field_pat], - etc: bool, - enum_id: ast::def_id, - substitutions: &ty::substs) { - let fcx = pcx.fcx; - let tcx = pcx.fcx.ccx.tcx; - - // Find the variant that was specified. - match tcx.def_map.find(pat_id) { - Some(ast::def_variant(found_enum_id, variant_id)) - if found_enum_id == enum_id => { - // Get the struct fields from this struct-like enum variant. - let class_fields = ty::lookup_struct_fields(tcx, variant_id); - - check_struct_pat_fields(pcx, span, path, fields, class_fields, - variant_id, substitutions, etc); - } - Some(ast::def_struct(*)) | Some(ast::def_variant(*)) => { - let name = pprust::path_to_str(path, tcx.sess.intr()); - tcx.sess.span_err(span, - fmt!("mismatched types: expected `%s` but \ - found `%s`", - fcx.infcx().ty_to_str(expected), - name)); - } - _ => { - tcx.sess.span_bug(span, ~"resolve didn't write in variant"); - } - } -} - -// Pattern checking is top-down rather than bottom-up so that bindings get -// their types immediately. -fn check_pat(pcx: pat_ctxt, pat: @ast::pat, expected: ty::t) { - let fcx = pcx.fcx; - let tcx = pcx.fcx.ccx.tcx; - - match /*bad*/copy pat.node { - ast::pat_wild => { - fcx.write_ty(pat.id, expected); - } - ast::pat_lit(lt) => { - check_expr_with(fcx, lt, expected); - fcx.write_ty(pat.id, fcx.expr_ty(lt)); - } - ast::pat_range(begin, end) => { - check_expr_with(fcx, begin, expected); - check_expr_with(fcx, end, expected); - let b_ty = - fcx.infcx().resolve_type_vars_if_possible(fcx.expr_ty(begin)); - let e_ty = - fcx.infcx().resolve_type_vars_if_possible(fcx.expr_ty(end)); - debug!("pat_range beginning type: %?", b_ty); - debug!("pat_range ending type: %?", e_ty); - if !require_same_types( - tcx, Some(fcx.infcx()), false, pat.span, b_ty, e_ty, - || ~"mismatched types in range") - { - // no-op - } else if !ty::type_is_numeric(b_ty) { - tcx.sess.span_err(pat.span, ~"non-numeric type used in range"); - } else if !valid_range_bounds(fcx.ccx, begin, end) { - tcx.sess.span_err(begin.span, ~"lower range bound must be less \ - than upper"); - } - fcx.write_ty(pat.id, b_ty); - } - ast::pat_ident(*) if pat_is_const(tcx.def_map, pat) => { - let const_did = ast_util::def_id_of_def(tcx.def_map.get(pat.id)); - let const_tpt = ty::lookup_item_type(tcx, const_did); - fcx.write_ty(pat.id, const_tpt.ty); - } - ast::pat_ident(bm, name, sub) if pat_is_binding(tcx.def_map, pat) => { - let vid = lookup_local(fcx, pat.span, pat.id); - let mut typ = ty::mk_var(tcx, vid); - - match bm { - ast::bind_by_ref(mutbl) => { - // if the binding is like - // ref x | ref const x | ref mut x - // then the type of x is &M T where M is the mutability - // and T is the expected type - let region_var = - fcx.infcx().next_region_var_with_lb( - pat.span, pcx.block_region); - let mt = {ty: expected, mutbl: mutbl}; - let region_ty = ty::mk_rptr(tcx, region_var, mt); - demand::eqtype(fcx, pat.span, region_ty, typ); - } - // otherwise the type of x is the expected type T - ast::bind_by_value | ast::bind_by_move | ast::bind_infer => { - demand::eqtype(fcx, pat.span, expected, typ); - } - } - - let canon_id = pcx.map.get(ast_util::path_to_ident(name)); - if canon_id != pat.id { - let tv_id = lookup_local(fcx, pat.span, canon_id); - let ct = ty::mk_var(tcx, tv_id); - demand::eqtype(fcx, pat.span, ct, typ); - } - fcx.write_ty(pat.id, typ); - - debug!("(checking alt) writing type for pat id %d", pat.id); - - match sub { - Some(p) => check_pat(pcx, p, expected), - _ => () - } - } - ast::pat_ident(_, path, _) => { - check_pat_variant(pcx, pat, path, Some(~[]), expected); - } - ast::pat_enum(path, subpats) => { - check_pat_variant(pcx, pat, path, subpats, expected); - } - ast::pat_rec(fields, etc) => { - let ex_fields = match structure_of(fcx, pat.span, expected) { - ty::ty_rec(fields) => fields, - _ => { - tcx.sess.span_fatal - (pat.span, - fmt!("mismatched types: expected `%s` but found record", - fcx.infcx().ty_to_str(expected))); - } - }; - let f_count = vec::len(fields); - let ex_f_count = vec::len(ex_fields); - if ex_f_count < f_count || !etc && ex_f_count > f_count { - tcx.sess.span_fatal - (pat.span, fmt!("mismatched types: expected a record \ - with %u fields, found one with %u \ - fields", - ex_f_count, f_count)); - } - - for fields.each |f| { - match vec::find(ex_fields, |a| f.ident == a.ident) { - Some(field) => { - check_pat(pcx, f.pat, field.mt.ty); - } - None => { - tcx.sess.span_fatal(pat.span, - fmt!("mismatched types: did not \ - expect a record with a field `%s`", - tcx.sess.str_of(f.ident))); - } - } - } - fcx.write_ty(pat.id, expected); - } - ast::pat_struct(path, fields, etc) => { - // Grab the class data that we care about. - let structure = structure_of(fcx, pat.span, expected); - match structure { - ty::ty_struct(cid, ref substs) => { - check_struct_pat(pcx, pat.id, pat.span, expected, path, - fields, etc, cid, substs); - } - ty::ty_enum(eid, ref substs) => { - check_struct_like_enum_variant_pat( - pcx, pat.id, pat.span, expected, path, fields, etc, eid, - substs); - } - _ => { - // XXX: This should not be fatal. - tcx.sess.span_fatal(pat.span, - fmt!("mismatched types: expected `%s` \ - but found struct", - fcx.infcx().ty_to_str(expected))); - } - } - - // Finally, write in the type. - fcx.write_ty(pat.id, expected); - } - ast::pat_tup(elts) => { - let ex_elts = match structure_of(fcx, pat.span, expected) { - ty::ty_tup(elts) => elts, - _ => { - tcx.sess.span_fatal - (pat.span, - fmt!("mismatched types: expected `%s`, found tuple", - fcx.infcx().ty_to_str(expected))); - } - }; - let e_count = vec::len(elts); - if e_count != vec::len(ex_elts) { - tcx.sess.span_fatal - (pat.span, fmt!("mismatched types: expected a tuple \ - with %u fields, found one with %u \ - fields", vec::len(ex_elts), e_count)); - } - let mut i = 0u; - for elts.each |elt| { - check_pat(pcx, *elt, ex_elts[i]); - i += 1u; - } - - fcx.write_ty(pat.id, expected); - } - ast::pat_box(inner) => { - match structure_of(fcx, pat.span, expected) { - ty::ty_box(e_inner) => { - check_pat(pcx, inner, e_inner.ty); - fcx.write_ty(pat.id, expected); - } - _ => { - tcx.sess.span_fatal( - pat.span, - ~"mismatched types: expected `" + - fcx.infcx().ty_to_str(expected) + - ~"` found box"); - } - } - } - ast::pat_uniq(inner) => { - match structure_of(fcx, pat.span, expected) { - ty::ty_uniq(e_inner) => { - check_pat(pcx, inner, e_inner.ty); - fcx.write_ty(pat.id, expected); - } - _ => { - tcx.sess.span_fatal( - pat.span, - ~"mismatched types: expected `" + - fcx.infcx().ty_to_str(expected) + - ~"` found uniq"); - } - } - } - ast::pat_region(inner) => { - match structure_of(fcx, pat.span, expected) { - ty::ty_rptr(_, e_inner) => { - check_pat(pcx, inner, e_inner.ty); - fcx.write_ty(pat.id, expected); - } - _ => { - tcx.sess.span_fatal( - pat.span, - ~"mismatched types: expected `" + - fcx.infcx().ty_to_str(expected) + - ~"` found borrowed pointer"); - } - } - } - ast::pat_vec(elts, tail) => { - let default_region_var = - fcx.infcx().next_region_var_with_lb( - pat.span, pcx.block_region - ); - - let (elt_type, region_var) = match structure_of( - fcx, pat.span, expected - ) { - ty::ty_evec(mt, vstore) => { - let region_var = match vstore { - ty::vstore_slice(r) => r, - ty::vstore_box | ty::vstore_uniq | ty::vstore_fixed(_) => { - default_region_var - } - }; - (mt, region_var) - } - ty::ty_unboxed_vec(mt) => { - (mt, default_region_var) - }, - _ => { - tcx.sess.span_fatal( - pat.span, - fmt!("mismatched type: expected `%s` but found vector", - fcx.infcx().ty_to_str(expected)) - ); - } - }; - for elts.each |elt| { - check_pat(pcx, *elt, elt_type.ty); - } - fcx.write_ty(pat.id, expected); - - match tail { - Some(tail_pat) => { - let slice_ty = ty::mk_evec(tcx, - {ty: elt_type.ty, mutbl: elt_type.mutbl}, - ty::vstore_slice(region_var) - ); - check_pat(pcx, tail_pat, slice_ty); - } - None => () - } - } - } -} - diff --git a/src/librustc/middle/typeck/check/mod.rs b/src/librustc/middle/typeck/check/mod.rs index f4bae52bd91..4eaf6311148 100644 --- a/src/librustc/middle/typeck/check/mod.rs +++ b/src/librustc/middle/typeck/check/mod.rs @@ -85,7 +85,7 @@ use middle::ty; use middle::typeck::astconv::{ast_conv, ast_path_to_ty}; use middle::typeck::astconv::{ast_region_to_region, ast_ty_to_ty}; use middle::typeck::astconv; -use middle::typeck::check::alt::pat_ctxt; +use middle::typeck::check::_match::pat_ctxt; use middle::typeck::check::method::TransformTypeNormally; use middle::typeck::check::regionmanip::replace_bound_regions_in_fn_ty; use middle::typeck::check::vtable::{LocationInfo, VtableContext}; @@ -117,7 +117,7 @@ use syntax::print::pprust; use syntax::visit; use syntax; -export alt; +export _match; export vtable; export writeback; export regionmanip; @@ -133,7 +133,7 @@ export DoDerefArgs; export check_item_types; #[legacy_exports] -pub mod alt; +pub mod _match; #[legacy_exports] pub mod vtable; #[legacy_exports] @@ -427,10 +427,10 @@ fn check_fn(ccx: @crate_ctxt, let pcx = pat_ctxt { fcx: fcx, map: pat_id_map(tcx.def_map, input.pat), - alt_region: region, + match_region: region, block_region: region, }; - alt::check_pat(pcx, input.pat, *arg_ty); + _match::check_pat(pcx, input.pat, *arg_ty); } // Add explicitly-declared locals. @@ -2124,7 +2124,7 @@ fn check_expr_with_unifier(fcx: @fn_ctxt, bot = !may_break(tcx, expr.id, (*body)); } ast::expr_match(discrim, ref arms) => { - bot = alt::check_alt(fcx, expr, discrim, (/*bad*/copy *arms)); + bot = _match::check_match(fcx, expr, discrim, (/*bad*/copy *arms)); } ast::expr_fn(proto, ref decl, ref body, cap_clause) => { check_expr_fn(fcx, expr, Some(proto), @@ -2517,10 +2517,10 @@ fn check_decl_local(fcx: @fn_ctxt, local: @ast::local) -> bool { let pcx = pat_ctxt { fcx: fcx, map: pat_id_map(tcx.def_map, local.node.pat), - alt_region: region, + match_region: region, block_region: region, }; - alt::check_pat(pcx, local.node.pat, t); + _match::check_pat(pcx, local.node.pat, t); return bot; } diff --git a/src/librustc/rustc.rc b/src/librustc/rustc.rc index 271d43087f3..60780df5287 100644 --- a/src/librustc/rustc.rc +++ b/src/librustc/rustc.rc @@ -77,7 +77,7 @@ mod middle { #[legacy_exports] mod base; #[legacy_exports] - mod alt; + mod _match; #[legacy_exports] mod uniq; #[legacy_exports] @@ -109,7 +109,7 @@ mod middle { #[legacy_exports] mod check_loop; #[legacy_exports] - mod check_alt; + mod check_match; #[legacy_exports] mod check_const; #[legacy_exports] diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs index b5609f72523..12dd40356eb 100644 --- a/src/librustc/util/ppaux.rs +++ b/src/librustc/util/ppaux.rs @@ -158,7 +158,7 @@ fn re_scope_id_to_str(cx: ctxt, node_id: ast::node_id) -> ~str { cx.sess.codemap.span_to_str(expr.span)) } ast::expr_match(*) => { - fmt!("", + fmt!("", cx.sess.codemap.span_to_str(expr.span)) } ast::expr_assign_op(*) | diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs index c7b4a2b239a..724e2fc9dba 100644 --- a/src/libsyntax/ext/tt/macro_parser.rs +++ b/src/libsyntax/ext/tt/macro_parser.rs @@ -245,7 +245,7 @@ fn parse(sess: parse_sess, cfg: ast::crate_cfg, rdr: reader, ms: ~[matcher]) /* at end of sequence */ if idx >= len { - // can't move out of `alt`s, so: + // can't move out of `match`es, so: if is_some(ei.up) { // hack: a matcher sequence is repeating iff it has a // parent (the top level is just a container) diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs index f85ca3fefef..f32a782622a 100644 --- a/src/libsyntax/parse/parser.rs +++ b/src/libsyntax/parse/parser.rs @@ -940,7 +940,7 @@ impl Parser { } else if self.eat_keyword(~"loop") { return self.parse_loop_expr(); } else if self.eat_keyword(~"match") { - return self.parse_alt_expr(); + return self.parse_match_expr(); } else if self.eat_keyword(~"fn") { let opt_proto = self.parse_fn_ty_proto(); let proto = match opt_proto { @@ -1722,7 +1722,7 @@ impl Parser { return expr_rec(fields, base); } - fn parse_alt_expr() -> @expr { + fn parse_match_expr() -> @expr { let lo = self.last_span.lo; let discriminant = self.parse_expr(); self.expect(token::LBRACE); diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs index ad4080c3094..239cff22cc0 100644 --- a/src/libsyntax/print/pprust.rs +++ b/src/libsyntax/print/pprust.rs @@ -83,7 +83,7 @@ fn rust_printer(writer: io::Writer, intr: @ident_interner) -> ps { } const indent_unit: uint = 4u; -const alt_indent_unit: uint = 2u; +const match_indent_unit: uint = 2u; const default_columns: uint = 78u; @@ -1251,7 +1251,7 @@ fn print_expr(s: ps, &&expr: @ast::expr) { print_block(s, (*blk)); } ast::expr_match(expr, ref arms) => { - cbox(s, alt_indent_unit); + cbox(s, match_indent_unit); ibox(s, 4); word_nbsp(s, ~"match"); print_expr(s, expr); @@ -1260,7 +1260,7 @@ fn print_expr(s: ps, &&expr: @ast::expr) { let len = (*arms).len(); for (*arms).eachi |i, arm| { space(s.s); - cbox(s, alt_indent_unit); + cbox(s, match_indent_unit); ibox(s, 0u); let mut first = true; for arm.pats.each |p| { @@ -1293,7 +1293,7 @@ fn print_expr(s: ps, &&expr: @ast::expr) { ast::expr_block(ref blk) => { // the block will close the pattern's ibox print_block_unclosed_indent( - s, (*blk), alt_indent_unit); + s, (*blk), match_indent_unit); } _ => { end(s); // close the ibox for the pattern @@ -1310,10 +1310,10 @@ fn print_expr(s: ps, &&expr: @ast::expr) { } } else { // the block will close the pattern's ibox - print_block_unclosed_indent(s, arm.body, alt_indent_unit); + print_block_unclosed_indent(s, arm.body, match_indent_unit); } } - bclose_(s, expr.span, alt_indent_unit); + bclose_(s, expr.span, match_indent_unit); } ast::expr_fn(proto, decl, ref body, cap_clause) => { // containing cbox, will be closed by print-block at } -- cgit 1.4.1-3-g733a5