1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
13 * # Compilation of match statements
15 * I will endeavor to explain the code as best I can. I have only a loose
16 * understanding of some parts of it.
20 * The basic state of the code is maintained in an array `m` of `Match`
21 * objects. Each `Match` describes some list of patterns, all of which must
22 * match against the current list of values. If those patterns match, then
23 * the arm listed in the match is the correct arm. A given arm may have
24 * multiple corresponding match entries, one for each alternative that
25 * remains. As we proceed these sets of matches are adjusted by the various
26 * `enter_XXX()` functions, each of which adjusts the set of options given
27 * some information about the value which has been matched.
29 * So, initially, there is one value and N matches, each of which have one
30 * constituent pattern. N here is usually the number of arms but may be
31 * greater, if some arms have multiple alternatives. For example, here:
33 * enum Foo { A, B(int), C(uint, uint) }
41 * The value would be `foo`. There would be four matches, each of which
42 * contains one pattern (and, in one case, a guard). We could collect the
43 * various options and then compile the code for the case where `foo` is an
44 * `A`, a `B`, and a `C`. When we generate the code for `C`, we would (1)
45 * drop the two matches that do not match a `C` and (2) expand the other two
46 * into two patterns each. In the first case, the two patterns would be `1u`
47 * and `2`, and the in the second case the _ pattern would be expanded into
48 * `_` and `_`. The two values are of course the arguments to `C`.
50 * Here is a quick guide to the various functions:
52 * - `compile_submatch()`: The main workhouse. It takes a list of values and
53 * a list of matches and finds the various possibilities that could occur.
55 * - `enter_XXX()`: modifies the list of matches based on some information
56 * about the value that has been matched. For example,
57 * `enter_rec_or_struct()` adjusts the values given that a record or struct
58 * has been matched. This is an infallible pattern, so *all* of the matches
59 * must be either wildcards or record/struct patterns. `enter_opt()`
60 * handles the fallible cases, and it is correspondingly more complex.
64 * We store information about the bound variables for each arm as part of the
65 * per-arm `ArmData` struct. There is a mapping from identifiers to
66 * `BindingInfo` structs. These structs contain the mode/id/type of the
67 * binding, but they also contain an LLVM value which points at an alloca
68 * called `llmatch`. For by value bindings that are Copy, we also create
69 * an extra alloca that we copy the matched value to so that any changes
70 * we do to our copy is not reflected in the original and vice-versa.
71 * We don't do this if it's a move since the original value can't be used
72 * and thus allowing us to cheat in not creating an extra alloca.
74 * The `llmatch` binding always stores a pointer into the value being matched
75 * which points at the data for the binding. If the value being matched has
76 * type `T`, then, `llmatch` will point at an alloca of type `T*` (and hence
77 * `llmatch` has type `T**`). So, if you have a pattern like:
81 * match (a, b) { (ref c, d) => { ... } }
83 * For `c` and `d`, we would generate allocas of type `C*` and `D*`
84 * respectively. These are called the `llmatch`. As we match, when we come
85 * up against an identifier, we store the current pointer into the
86 * corresponding alloca.
88 * Once a pattern is completely matched, and assuming that there is no guard
89 * pattern, we will branch to a block that leads to the body itself. For any
90 * by-value bindings, this block will first load the ptr from `llmatch` (the
91 * one of type `D*`) and then load a second time to get the actual value (the
92 * one of type `D`). For by ref bindings, the value of the local variable is
93 * simply the first alloca.
95 * So, for the example above, we would generate a setup kind of like this:
101 * +--------------------------------------------+
102 * | llmatch_c = (addr of first half of tuple) |
103 * | llmatch_d = (addr of second half of tuple) |
104 * +--------------------------------------------+
106 * +--------------------------------------+
107 * | *llbinding_d = **llmatch_d |
108 * +--------------------------------------+
110 * If there is a guard, the situation is slightly different, because we must
111 * execute the guard code. Moreover, we need to do so once for each of the
112 * alternatives that lead to the arm, because if the guard fails, they may
113 * have different points from which to continue the search. Therefore, in that
114 * case, we generate code that looks more like:
120 * +-------------------------------------------+
121 * | llmatch_c = (addr of first half of tuple) |
122 * | llmatch_d = (addr of first half of tuple) |
123 * +-------------------------------------------+
125 * +-------------------------------------------------+
126 * | *llbinding_d = **llmatch_d |
127 * | check condition |
128 * | if false { goto next case } |
129 * | if true { goto body } |
130 * +-------------------------------------------------+
132 * The handling for the cleanups is a bit... sensitive. Basically, the body
133 * is the one that invokes `add_clean()` for each binding. During the guard
134 * evaluation, we add temporary cleanups and revoke them after the guard is
135 * evaluated (it could fail, after all). Note that guards and moves are
136 * just plain incompatible.
138 * Some relevant helper functions that manage bindings:
139 * - `create_bindings_map()`
140 * - `insert_lllocals()`
143 * ## Notes on vector pattern matching.
145 * Vector pattern matching is surprisingly tricky. The problem is that
146 * the structure of the vector isn't fully known, and slice matches
147 * can be done on subparts of it.
149 * The way that vector pattern matches are dealt with, then, is as
150 * follows. First, we make the actual condition associated with a
151 * vector pattern simply a vector length comparison. So the pattern
152 * [1, .. x] gets the condition "vec len >= 1", and the pattern
153 * [.. x] gets the condition "vec len >= 0". The problem here is that
154 * having the condition "vec len >= 1" hold clearly does not mean that
155 * only a pattern that has exactly that condition will match. This
156 * means that it may well be the case that a condition holds, but none
157 * of the patterns matching that condition match; to deal with this,
158 * when doing vector length matches, we have match failures proceed to
159 * the next condition to check.
161 * There are a couple more subtleties to deal with. While the "actual"
162 * condition associated with vector length tests is simply a test on
163 * the vector length, the actual vec_len Opt entry contains more
164 * information used to restrict which matches are associated with it.
165 * So that all matches in a submatch are matching against the same
166 * values from inside the vector, they are split up by how many
167 * elements they match at the front and at the back of the vector. In
168 * order to make sure that arms are properly checked in order, even
169 * with the overmatching conditions, each vec_len Opt entry is
170 * associated with a range of matches.
171 * Consider the following:
175 * [1, 2, 2, .. _] => 1,
176 * [1, 2, 3, .. _] => 2,
180 * The proper arm to match is arm 2, but arms 0 and 3 both have the
181 * condition "len >= 2". If arm 3 was lumped in with arm 0, then the
182 * wrong branch would be taken. Instead, vec_len Opts are associated
183 * with a contiguous range of matches that have the same "shape".
184 * This is sort of ugly and requires a bunch of special handling of
189 #![allow(non_camel_case_types)]
192 use driver::config::FullDebugInfo;
193 use lib::llvm::{llvm, ValueRef, BasicBlockRef};
194 use middle::const_eval;
196 use middle::lang_items::{UniqStrEqFnLangItem, StrEqFnLangItem};
197 use middle::pat_util::*;
198 use middle::resolve::DefMap;
199 use middle::trans::adt;
200 use middle::trans::base::*;
201 use middle::trans::build::*;
202 use middle::trans::callee;
203 use middle::trans::cleanup;
204 use middle::trans::cleanup::CleanupMethods;
205 use middle::trans::common::*;
206 use middle::trans::consts;
207 use middle::trans::controlflow;
208 use middle::trans::datum;
209 use middle::trans::datum::*;
210 use middle::trans::expr::Dest;
211 use middle::trans::expr;
212 use middle::trans::tvec;
213 use middle::trans::type_of;
214 use middle::trans::debuginfo;
216 use util::common::indenter;
217 use util::ppaux::{Repr, vec_map_to_str};
219 use std::collections::HashMap;
222 use std::gc::{Gc, GC};
224 use syntax::ast::Ident;
225 use syntax::ast_util::path_to_ident;
226 use syntax::ast_util;
227 use syntax::codemap::{Span, DUMMY_SP};
228 use syntax::parse::token::InternedString;
230 // An option identifying a literal: either a unit-like struct or an
233 UnitLikeStructLit(ast::NodeId), // the node ID of the pattern
234 ExprLit(Gc<ast::Expr>),
235 ConstLit(ast::DefId), // the def ID of the constant
238 #[deriving(PartialEq)]
241 vec_len_ge(/* length of prefix */uint)
244 // An option identifying a branch (either a literal, an enum variant or a
248 var(ty::Disr, Rc<adt::Repr>),
249 range(Gc<ast::Expr>, Gc<ast::Expr>),
250 vec_len(/* length */ uint, VecLenOpt, /*range of matches*/(uint, uint))
253 fn lit_to_expr(tcx: &ty::ctxt, a: &Lit) -> Gc<ast::Expr> {
255 ExprLit(existing_a_expr) => existing_a_expr,
256 ConstLit(a_const) => const_eval::lookup_const_by_id(tcx, a_const).unwrap(),
257 UnitLikeStructLit(_) => fail!("lit_to_expr: unexpected struct lit"),
261 fn opt_eq(tcx: &ty::ctxt, a: &Opt, b: &Opt) -> bool {
263 (&lit(UnitLikeStructLit(a)), &lit(UnitLikeStructLit(b))) => a == b,
264 (&lit(a), &lit(b)) => {
265 let a_expr = lit_to_expr(tcx, &a);
266 let b_expr = lit_to_expr(tcx, &b);
267 match const_eval::compare_lit_exprs(tcx, &*a_expr, &*b_expr) {
268 Some(val1) => val1 == 0,
269 None => fail!("compare_list_exprs: type mismatch"),
272 (&range(ref a1, ref a2), &range(ref b1, ref b2)) => {
273 let m1 = const_eval::compare_lit_exprs(tcx, &**a1, &**b1);
274 let m2 = const_eval::compare_lit_exprs(tcx, &**a2, &**b2);
276 (Some(val1), Some(val2)) => (val1 == 0 && val2 == 0),
277 _ => fail!("compare_list_exprs: type mismatch"),
280 (&var(a, _), &var(b, _)) => a == b,
281 (&vec_len(a1, a2, _), &vec_len(b1, b2, _)) =>
282 a1 == b1 && a2 == b2,
287 pub enum opt_result<'a> {
288 single_result(Result<'a>),
289 lower_bound(Result<'a>),
290 range_result(Result<'a>, Result<'a>),
293 fn trans_opt<'a>(bcx: &'a Block<'a>, o: &Opt) -> opt_result<'a> {
294 let _icx = push_ctxt("match::trans_opt");
298 lit(ExprLit(ref lit_expr)) => {
299 let lit_datum = unpack_datum!(bcx, expr::trans(bcx, &**lit_expr));
300 let lit_datum = lit_datum.assert_rvalue(bcx); // literals are rvalues
301 let lit_datum = unpack_datum!(bcx, lit_datum.to_appropriate_datum(bcx));
302 return single_result(Result::new(bcx, lit_datum.val));
304 lit(UnitLikeStructLit(pat_id)) => {
305 let struct_ty = ty::node_id_to_type(bcx.tcx(), pat_id);
306 let datum = datum::rvalue_scratch_datum(bcx, struct_ty, "");
307 return single_result(Result::new(bcx, datum.val));
309 lit(l @ ConstLit(ref def_id)) => {
310 let lit_ty = ty::node_id_to_type(bcx.tcx(), lit_to_expr(bcx.tcx(), &l).id);
311 let (llval, _) = consts::get_const_val(bcx.ccx(), *def_id);
312 let lit_datum = immediate_rvalue(llval, lit_ty);
313 let lit_datum = unpack_datum!(bcx, lit_datum.to_appropriate_datum(bcx));
314 return single_result(Result::new(bcx, lit_datum.val));
316 var(disr_val, ref repr) => {
317 return adt::trans_case(bcx, &**repr, disr_val);
319 range(ref l1, ref l2) => {
320 let (l1, _) = consts::const_expr(ccx, &**l1, true);
321 let (l2, _) = consts::const_expr(ccx, &**l2, true);
322 return range_result(Result::new(bcx, l1), Result::new(bcx, l2));
324 vec_len(n, vec_len_eq, _) => {
325 return single_result(Result::new(bcx, C_int(ccx, n as int)));
327 vec_len(n, vec_len_ge(_), _) => {
328 return lower_bound(Result::new(bcx, C_int(ccx, n as int)));
333 fn variant_opt(bcx: &Block, pat_id: ast::NodeId) -> Opt {
335 let def = ccx.tcx.def_map.borrow().get_copy(&pat_id);
337 def::DefVariant(enum_id, var_id, _) => {
338 let variants = ty::enum_variants(ccx.tcx(), enum_id);
339 for v in (*variants).iter() {
341 return var(v.disr_val,
342 adt::represent_node(bcx, pat_id))
348 def::DefStruct(_) => {
349 return lit(UnitLikeStructLit(pat_id));
352 ccx.sess().bug("non-variant or struct in variant_opt()");
358 pub enum TransBindingMode {
359 TrByCopy(/* llbinding */ ValueRef),
365 * Information about a pattern binding:
366 * - `llmatch` is a pointer to a stack slot. The stack slot contains a
367 * pointer into the value being matched. Hence, llmatch has type `T**`
368 * where `T` is the value being matched.
369 * - `trmode` is the trans binding mode
370 * - `id` is the node id of the binding
371 * - `ty` is the Rust type of the binding */
373 pub struct BindingInfo {
374 pub llmatch: ValueRef,
375 pub trmode: TransBindingMode,
381 type BindingsMap = HashMap<Ident, BindingInfo>;
383 struct ArmData<'a, 'b> {
384 bodycx: &'b Block<'b>,
386 bindings_map: BindingsMap
391 * If all `pats` are matched then arm `data` will be executed.
392 * As we proceed `bound_ptrs` are filled with pointers to values to be bound,
393 * these pointers are stored in llmatch variables just before executing `data` arm.
395 struct Match<'a, 'b> {
396 pats: Vec<Gc<ast::Pat>>,
397 data: &'a ArmData<'a, 'b>,
398 bound_ptrs: Vec<(Ident, ValueRef)>
401 impl<'a, 'b> Repr for Match<'a, 'b> {
402 fn repr(&self, tcx: &ty::ctxt) -> String {
403 if tcx.sess.verbose() {
404 // for many programs, this just take too long to serialize
407 format!("{} pats", self.pats.len())
412 fn has_nested_bindings(m: &[Match], col: uint) -> bool {
414 match br.pats.get(col).node {
415 ast::PatIdent(_, _, Some(_)) => return true,
422 fn expand_nested_bindings<'a, 'b>(
424 m: &'a [Match<'a, 'b>],
427 -> Vec<Match<'a, 'b>> {
428 debug!("expand_nested_bindings(bcx={}, m={}, col={}, val={})",
432 bcx.val_to_str(val));
433 let _indenter = indenter();
436 match br.pats.get(col).node {
437 ast::PatIdent(_, ref path, Some(inner)) => {
438 let pats = Vec::from_slice(br.pats.slice(0u, col))
439 .append((vec!(inner))
440 .append(br.pats.slice(col + 1u, br.pats.len())).as_slice());
442 let mut bound_ptrs = br.bound_ptrs.clone();
443 bound_ptrs.push((path_to_ident(path), val));
447 bound_ptrs: bound_ptrs
451 pats: br.pats.clone(),
453 bound_ptrs: br.bound_ptrs.clone()
459 fn assert_is_binding_or_wild(bcx: &Block, p: Gc<ast::Pat>) {
460 if !pat_is_binding_or_wild(&bcx.tcx().def_map, &*p) {
463 format!("expected an identifier pattern but found p: {}",
464 p.repr(bcx.tcx())).as_slice());
468 type enter_pat<'a> = |Gc<ast::Pat>|: 'a -> Option<Vec<Gc<ast::Pat>>>;
470 fn enter_match<'a, 'b>(
473 m: &'a [Match<'a, 'b>],
477 -> Vec<Match<'a, 'b>> {
478 debug!("enter_match(bcx={}, m={}, col={}, val={})",
482 bcx.val_to_str(val));
483 let _indenter = indenter();
485 m.iter().filter_map(|br| {
486 e(*br.pats.get(col)).map(|sub| {
487 let pats = sub.append(br.pats.slice(0u, col))
488 .append(br.pats.slice(col + 1u, br.pats.len()));
490 let this = *br.pats.get(col);
491 let mut bound_ptrs = br.bound_ptrs.clone();
493 ast::PatIdent(_, ref path, None) => {
494 if pat_is_binding(dm, &*this) {
495 bound_ptrs.push((path_to_ident(path), val));
504 bound_ptrs: bound_ptrs
510 fn enter_default<'a, 'b>(
513 m: &'a [Match<'a, 'b>],
516 -> Vec<Match<'a, 'b>> {
517 debug!("enter_default(bcx={}, m={}, col={}, val={})",
521 bcx.val_to_str(val));
522 let _indenter = indenter();
524 // Collect all of the matches that can match against anything.
525 enter_match(bcx, dm, m, col, val, |p| {
527 ast::PatWild | ast::PatWildMulti => Some(Vec::new()),
528 ast::PatIdent(_, _, None) if pat_is_binding(dm, &*p) => Some(Vec::new()),
534 // <pcwalton> nmatsakis: what does enter_opt do?
535 // <pcwalton> in trans/match
536 // <pcwalton> trans/match.rs is like stumbling around in a dark cave
537 // <nmatsakis> pcwalton: the enter family of functions adjust the set of
538 // patterns as needed
539 // <nmatsakis> yeah, at some point I kind of achieved some level of
541 // <nmatsakis> anyhow, they adjust the patterns given that something of that
542 // kind has been found
543 // <nmatsakis> pcwalton: ok, right, so enter_XXX() adjusts the patterns, as I
545 // <nmatsakis> enter_match() kind of embodies the generic code
546 // <nmatsakis> it is provided with a function that tests each pattern to see
547 // if it might possibly apply and so forth
548 // <nmatsakis> so, if you have a pattern like {a: _, b: _, _} and one like _
549 // <nmatsakis> then _ would be expanded to (_, _)
550 // <nmatsakis> one spot for each of the sub-patterns
551 // <nmatsakis> enter_opt() is one of the more complex; it covers the fallible
553 // <nmatsakis> enter_rec_or_struct() or enter_tuple() are simpler, since they
554 // are infallible patterns
555 // <nmatsakis> so all patterns must either be records (resp. tuples) or
558 fn enter_opt<'a, 'b>(
560 m: &'a [Match<'a, 'b>],
565 -> Vec<Match<'a, 'b>> {
566 debug!("enter_opt(bcx={}, m={}, opt={:?}, col={}, val={})",
571 bcx.val_to_str(val));
572 let _indenter = indenter();
575 let dummy = box(GC) ast::Pat {id: 0, node: ast::PatWild, span: DUMMY_SP};
577 enter_match(bcx, &tcx.def_map, m, col, val, |p| {
578 let answer = match p.node {
580 ast::PatIdent(_, _, None) if pat_is_const(&tcx.def_map, &*p) => {
581 let const_def = tcx.def_map.borrow().get_copy(&p.id);
582 let const_def_id = const_def.def_id();
583 if opt_eq(tcx, &lit(ConstLit(const_def_id)), opt) {
589 ast::PatEnum(_, ref subpats) => {
590 if opt_eq(tcx, &variant_opt(bcx, p.id), opt) {
591 // FIXME: Must we clone?
593 None => Some(Vec::from_elem(variant_size, dummy)),
594 Some(ref subpats) => {
595 Some((*subpats).iter().map(|x| *x).collect())
602 ast::PatIdent(_, _, None)
603 if pat_is_variant_or_struct(&tcx.def_map, &*p) => {
604 if opt_eq(tcx, &variant_opt(bcx, p.id), opt) {
611 if opt_eq(tcx, &lit(ExprLit(l)), opt) { Some(Vec::new()) }
614 ast::PatRange(l1, l2) => {
615 if opt_eq(tcx, &range(l1, l2), opt) { Some(Vec::new()) }
618 ast::PatStruct(_, ref field_pats, _) => {
619 if opt_eq(tcx, &variant_opt(bcx, p.id), opt) {
620 // Look up the struct variant ID.
622 match tcx.def_map.borrow().get_copy(&p.id) {
623 def::DefVariant(_, found_struct_id, _) => {
624 struct_id = found_struct_id;
627 tcx.sess.span_bug(p.span, "expected enum variant def");
631 // Reorder the patterns into the same order they were
632 // specified in the struct definition. Also fill in
633 // unspecified fields with dummy.
634 let mut reordered_patterns = Vec::new();
635 let r = ty::lookup_struct_fields(tcx, struct_id);
636 for field in r.iter() {
637 match field_pats.iter().find(|p| p.ident.name
639 None => reordered_patterns.push(dummy),
640 Some(fp) => reordered_patterns.push(fp.pat)
643 Some(reordered_patterns)
648 ast::PatVec(ref before, slice, ref after) => {
649 let (lo, hi) = match *opt {
650 vec_len(_, _, (lo, hi)) => (lo, hi),
651 _ => tcx.sess.span_bug(p.span,
652 "vec pattern but not vec opt")
656 Some(slice) if i >= lo && i <= hi => {
657 let n = before.len() + after.len();
658 let this_opt = vec_len(n, vec_len_ge(before.len()),
660 if opt_eq(tcx, &this_opt, opt) {
661 let mut new_before = Vec::new();
662 for pat in before.iter() {
663 new_before.push(*pat);
665 new_before.push(slice);
666 for pat in after.iter() {
667 new_before.push(*pat);
674 None if i >= lo && i <= hi => {
675 let n = before.len();
676 if opt_eq(tcx, &vec_len(n, vec_len_eq, (lo,hi)), opt) {
677 let mut new_before = Vec::new();
678 for pat in before.iter() {
679 new_before.push(*pat);
690 assert_is_binding_or_wild(bcx, p);
691 Some(Vec::from_elem(variant_size, dummy))
699 fn enter_rec_or_struct<'a, 'b>(
702 m: &'a [Match<'a, 'b>],
704 fields: &[ast::Ident],
706 -> Vec<Match<'a, 'b>> {
707 debug!("enter_rec_or_struct(bcx={}, m={}, col={}, val={})",
711 bcx.val_to_str(val));
712 let _indenter = indenter();
714 let dummy = box(GC) ast::Pat {id: 0, node: ast::PatWild, span: DUMMY_SP};
715 enter_match(bcx, dm, m, col, val, |p| {
717 ast::PatStruct(_, ref fpats, _) => {
718 let mut pats = Vec::new();
719 for fname in fields.iter() {
720 match fpats.iter().find(|p| p.ident.name == fname.name) {
721 None => pats.push(dummy),
722 Some(pat) => pats.push(pat.pat)
728 assert_is_binding_or_wild(bcx, p);
729 Some(Vec::from_elem(fields.len(), dummy))
735 fn enter_tup<'a, 'b>(
738 m: &'a [Match<'a, 'b>],
742 -> Vec<Match<'a, 'b>> {
743 debug!("enter_tup(bcx={}, m={}, col={}, val={})",
747 bcx.val_to_str(val));
748 let _indenter = indenter();
750 let dummy = box(GC) ast::Pat {id: 0, node: ast::PatWild, span: DUMMY_SP};
751 enter_match(bcx, dm, m, col, val, |p| {
753 ast::PatTup(ref elts) => {
754 let mut new_elts = Vec::new();
755 for elt in elts.iter() {
756 new_elts.push((*elt).clone())
761 assert_is_binding_or_wild(bcx, p);
762 Some(Vec::from_elem(n_elts, dummy))
768 fn enter_tuple_struct<'a, 'b>(
771 m: &'a [Match<'a, 'b>],
775 -> Vec<Match<'a, 'b>> {
776 debug!("enter_tuple_struct(bcx={}, m={}, col={}, val={})",
780 bcx.val_to_str(val));
781 let _indenter = indenter();
783 let dummy = box(GC) ast::Pat {id: 0, node: ast::PatWild, span: DUMMY_SP};
784 enter_match(bcx, dm, m, col, val, |p| {
786 ast::PatEnum(_, Some(ref elts)) => {
787 Some(elts.iter().map(|x| (*x)).collect())
789 ast::PatEnum(_, None) => {
790 Some(Vec::from_elem(n_elts, dummy))
793 assert_is_binding_or_wild(bcx, p);
794 Some(Vec::from_elem(n_elts, dummy))
800 fn enter_uniq<'a, 'b>(
803 m: &'a [Match<'a, 'b>],
806 -> Vec<Match<'a, 'b>> {
807 debug!("enter_uniq(bcx={}, m={}, col={}, val={})",
811 bcx.val_to_str(val));
812 let _indenter = indenter();
814 let dummy = box(GC) ast::Pat {id: 0, node: ast::PatWild, span: DUMMY_SP};
815 enter_match(bcx, dm, m, col, val, |p| {
817 ast::PatBox(sub) => {
821 assert_is_binding_or_wild(bcx, p);
828 fn enter_region<'a, 'b>(
831 m: &'a [Match<'a, 'b>],
834 -> Vec<Match<'a, 'b>> {
835 debug!("enter_region(bcx={}, m={}, col={}, val={})",
839 bcx.val_to_str(val));
840 let _indenter = indenter();
842 let dummy = box(GC) ast::Pat { id: 0, node: ast::PatWild, span: DUMMY_SP };
843 enter_match(bcx, dm, m, col, val, |p| {
845 ast::PatRegion(sub) => {
849 assert_is_binding_or_wild(bcx, p);
856 // Returns the options in one column of matches. An option is something that
857 // needs to be conditionally matched at runtime; for example, the discriminant
858 // on a set of enum variants or a literal.
859 fn get_options(bcx: &Block, m: &[Match], col: uint) -> Vec<Opt> {
861 fn add_to_set(tcx: &ty::ctxt, set: &mut Vec<Opt>, val: Opt) {
862 if set.iter().any(|l| opt_eq(tcx, l, &val)) {return;}
865 // Vector comparisons are special in that since the actual
866 // conditions over-match, we need to be careful about them. This
867 // means that in order to properly handle things in order, we need
868 // to not always merge conditions.
869 fn add_veclen_to_set(set: &mut Vec<Opt> , i: uint,
870 len: uint, vlo: VecLenOpt) {
872 // If the last condition in the list matches the one we want
873 // to add, then extend its range. Otherwise, make a new
874 // vec_len with a range just covering the new entry.
875 Some(&vec_len(len2, vlo2, (start, end)))
876 if len == len2 && vlo == vlo2 => {
877 let length = set.len();
878 *set.get_mut(length - 1) =
879 vec_len(len, vlo, (start, end+1))
881 _ => set.push(vec_len(len, vlo, (i, i)))
885 let mut found = Vec::new();
886 for (i, br) in m.iter().enumerate() {
887 let cur = *br.pats.get(col);
890 add_to_set(ccx.tcx(), &mut found, lit(ExprLit(l)));
892 ast::PatIdent(..) => {
893 // This is one of: an enum variant, a unit-like struct, or a
895 let opt_def = ccx.tcx.def_map.borrow().find_copy(&cur.id);
897 Some(def::DefVariant(..)) => {
898 add_to_set(ccx.tcx(), &mut found,
899 variant_opt(bcx, cur.id));
901 Some(def::DefStruct(..)) => {
902 add_to_set(ccx.tcx(), &mut found,
903 lit(UnitLikeStructLit(cur.id)));
905 Some(def::DefStatic(const_did, false)) => {
906 add_to_set(ccx.tcx(), &mut found,
907 lit(ConstLit(const_did)));
912 ast::PatEnum(..) | ast::PatStruct(..) => {
913 // This could be one of: a tuple-like enum variant, a
914 // struct-like enum variant, or a struct.
915 let opt_def = ccx.tcx.def_map.borrow().find_copy(&cur.id);
917 Some(def::DefFn(..)) |
918 Some(def::DefVariant(..)) => {
919 add_to_set(ccx.tcx(), &mut found,
920 variant_opt(bcx, cur.id));
922 Some(def::DefStatic(const_did, false)) => {
923 add_to_set(ccx.tcx(), &mut found,
924 lit(ConstLit(const_did)));
929 ast::PatRange(l1, l2) => {
930 add_to_set(ccx.tcx(), &mut found, range(l1, l2));
932 ast::PatVec(ref before, slice, ref after) => {
933 let (len, vec_opt) = match slice {
934 None => (before.len(), vec_len_eq),
935 Some(_) => (before.len() + after.len(),
936 vec_len_ge(before.len()))
938 add_veclen_to_set(&mut found, i, len, vec_opt);
946 struct ExtractedBlock<'a> {
947 vals: Vec<ValueRef> ,
951 fn extract_variant_args<'a>(
956 -> ExtractedBlock<'a> {
957 let _icx = push_ctxt("match::extract_variant_args");
958 let args = Vec::from_fn(adt::num_args(repr, disr_val), |i| {
959 adt::trans_field_ptr(bcx, repr, val, disr_val, i)
962 ExtractedBlock { vals: args, bcx: bcx }
965 fn match_datum(bcx: &Block,
970 * Helper for converting from the ValueRef that we pass around in
971 * the match code, which is always an lvalue, into a Datum. Eventually
972 * we should just pass around a Datum and be done with it.
975 let ty = node_id_type(bcx, pat_id);
976 Datum::new(val, ty, Lvalue)
980 fn extract_vec_elems<'a>(
986 -> ExtractedBlock<'a> {
987 let _icx = push_ctxt("match::extract_vec_elems");
988 let vec_datum = match_datum(bcx, val, pat_id);
989 let (base, len) = vec_datum.get_vec_base_and_len(bcx);
990 let vec_ty = node_id_type(bcx, pat_id);
991 let vt = tvec::vec_types(bcx, ty::sequence_element_type(bcx.tcx(), vec_ty));
993 let mut elems = Vec::from_fn(elem_count, |i| {
995 None => GEPi(bcx, base, [i]),
996 Some(n) if i < n => GEPi(bcx, base, [i]),
997 Some(n) if i > n => {
998 InBoundsGEP(bcx, base, [
1000 C_int(bcx.ccx(), (elem_count - i) as int))])
1002 _ => unsafe { llvm::LLVMGetUndef(vt.llunit_ty.to_ref()) }
1005 if slice.is_some() {
1006 let n = slice.unwrap();
1007 let slice_byte_offset = Mul(bcx, vt.llunit_size, C_uint(bcx.ccx(), n));
1008 let slice_begin = tvec::pointer_add_byte(bcx, base, slice_byte_offset);
1009 let slice_len_offset = C_uint(bcx.ccx(), elem_count - 1u);
1010 let slice_len = Sub(bcx, len, slice_len_offset);
1011 let slice_ty = ty::mk_slice(bcx.tcx(),
1013 ty::mt {ty: vt.unit_ty, mutbl: ast::MutImmutable});
1014 let scratch = rvalue_scratch_datum(bcx, slice_ty, "");
1015 Store(bcx, slice_begin,
1016 GEPi(bcx, scratch.val, [0u, abi::slice_elt_base]));
1017 Store(bcx, slice_len, GEPi(bcx, scratch.val, [0u, abi::slice_elt_len]));
1018 *elems.get_mut(n) = scratch.val;
1021 ExtractedBlock { vals: elems, bcx: bcx }
1024 /// Checks every pattern in `m` at `col` column.
1025 /// If there are a struct pattern among them function
1026 /// returns list of all fields that are matched in these patterns.
1027 /// Function returns None if there is no struct pattern.
1028 /// Function doesn't collect fields from struct-like enum variants.
1029 /// Function can return empty list if there is only wildcard struct pattern.
1030 fn collect_record_or_struct_fields<'a>(
1034 -> Option<Vec<ast::Ident> > {
1035 let mut fields: Vec<ast::Ident> = Vec::new();
1036 let mut found = false;
1037 for br in m.iter() {
1038 match br.pats.get(col).node {
1039 ast::PatStruct(_, ref fs, _) => {
1040 match ty::get(node_id_type(bcx, br.pats.get(col).id)).sty {
1041 ty::ty_struct(..) => {
1042 extend(&mut fields, fs.as_slice());
1052 return Some(fields);
1057 fn extend(idents: &mut Vec<ast::Ident> , field_pats: &[ast::FieldPat]) {
1058 for field_pat in field_pats.iter() {
1059 let field_ident = field_pat.ident;
1060 if !idents.iter().any(|x| x.name == field_ident.name) {
1061 idents.push(field_ident);
1067 // Macro for deciding whether any of the remaining matches fit a given kind of
1068 // pattern. Note that, because the macro is well-typed, either ALL of the
1069 // matches should fit that sort of pattern or NONE (however, some of the
1070 // matches may be wildcards like _ or identifiers).
1071 macro_rules! any_pat (
1072 ($m:expr, $pattern:pat) => (
1073 ($m).iter().any(|br| {
1074 match br.pats.get(col).node {
1082 fn any_uniq_pat(m: &[Match], col: uint) -> bool {
1083 any_pat!(m, ast::PatBox(_))
1086 fn any_region_pat(m: &[Match], col: uint) -> bool {
1087 any_pat!(m, ast::PatRegion(_))
1090 fn any_tup_pat(m: &[Match], col: uint) -> bool {
1091 any_pat!(m, ast::PatTup(_))
1094 fn any_tuple_struct_pat(bcx: &Block, m: &[Match], col: uint) -> bool {
1096 let pat = *br.pats.get(col);
1098 ast::PatEnum(_, _) => {
1099 match bcx.tcx().def_map.borrow().find(&pat.id) {
1100 Some(&def::DefFn(..)) |
1101 Some(&def::DefStruct(..)) => true,
1110 struct DynamicFailureHandler<'a> {
1113 msg: InternedString,
1114 finished: Cell<Option<BasicBlockRef>>,
1117 impl<'a> DynamicFailureHandler<'a> {
1118 fn handle_fail(&self) -> BasicBlockRef {
1119 match self.finished.get() {
1120 Some(bb) => return bb,
1124 let fcx = self.bcx.fcx;
1125 let fail_cx = fcx.new_block(false, "case_fallthrough", None);
1126 controlflow::trans_fail(fail_cx, self.sp, self.msg.clone());
1127 self.finished.set(Some(fail_cx.llbb));
1132 /// What to do when the pattern match fails.
1133 enum FailureHandler<'a> {
1135 JumpToBasicBlock(BasicBlockRef),
1136 DynamicFailureHandlerClass(Box<DynamicFailureHandler<'a>>),
1139 impl<'a> FailureHandler<'a> {
1140 fn is_infallible(&self) -> bool {
1147 fn is_fallible(&self) -> bool {
1148 !self.is_infallible()
1151 fn handle_fail(&self) -> BasicBlockRef {
1154 fail!("attempted to fail in infallible failure handler!")
1156 JumpToBasicBlock(basic_block) => basic_block,
1157 DynamicFailureHandlerClass(ref dynamic_failure_handler) => {
1158 dynamic_failure_handler.handle_fail()
1164 fn pick_col(m: &[Match]) -> uint {
1165 fn score(p: &ast::Pat) -> uint {
1167 ast::PatLit(_) | ast::PatEnum(_, _) | ast::PatRange(_, _) => 1u,
1168 ast::PatIdent(_, _, Some(ref p)) => score(&**p),
1172 let mut scores = Vec::from_elem(m[0].pats.len(), 0u);
1173 for br in m.iter() {
1174 for (i, ref p) in br.pats.iter().enumerate() {
1175 *scores.get_mut(i) += score(&***p);
1178 let mut max_score = 0u;
1179 let mut best_col = 0u;
1180 for (i, score) in scores.iter().enumerate() {
1183 // Irrefutable columns always go first, they'd only be duplicated in
1185 if score == 0u { return i; }
1186 // If no irrefutable ones are found, we pick the one with the biggest
1187 // branching factor.
1188 if score > max_score { max_score = score; best_col = i; }
1193 #[deriving(PartialEq)]
1194 pub enum branch_kind { no_branch, single, switch, compare, compare_vec_len, }
1196 // Compiles a comparison between two things.
1197 fn compare_values<'a>(
1203 fn compare_str<'a>(cx: &'a Block<'a>,
1208 let did = langcall(cx,
1210 format!("comparison of `{}`",
1211 cx.ty_to_str(rhs_t)).as_slice(),
1213 callee::trans_lang_call(cx, did, [lhs, rhs], None)
1216 let _icx = push_ctxt("compare_values");
1217 if ty::type_is_scalar(rhs_t) {
1218 let rs = compare_scalar_types(cx, lhs, rhs, rhs_t, ast::BiEq);
1219 return Result::new(rs.bcx, rs.val);
1222 match ty::get(rhs_t).sty {
1223 ty::ty_uniq(t) => match ty::get(t).sty {
1225 let scratch_lhs = alloca(cx, val_ty(lhs), "__lhs");
1226 Store(cx, lhs, scratch_lhs);
1227 let scratch_rhs = alloca(cx, val_ty(rhs), "__rhs");
1228 Store(cx, rhs, scratch_rhs);
1229 let did = langcall(cx,
1231 format!("comparison of `{}`",
1232 cx.ty_to_str(rhs_t)).as_slice(),
1233 UniqStrEqFnLangItem);
1234 callee::trans_lang_call(cx, did, [scratch_lhs, scratch_rhs], None)
1236 _ => cx.sess().bug("only strings supported in compare_values"),
1238 ty::ty_rptr(_, mt) => match ty::get(mt.ty).sty {
1239 ty::ty_str => compare_str(cx, lhs, rhs, rhs_t),
1240 ty::ty_vec(mt, _) => match ty::get(mt.ty).sty {
1241 ty::ty_uint(ast::TyU8) => {
1242 // NOTE: cast &[u8] to &str and abuse the str_eq lang item,
1243 // which calls memcmp().
1244 let t = ty::mk_str_slice(cx.tcx(), ty::ReStatic, ast::MutImmutable);
1245 let lhs = BitCast(cx, lhs, type_of::type_of(cx.ccx(), t).ptr_to());
1246 let rhs = BitCast(cx, rhs, type_of::type_of(cx.ccx(), t).ptr_to());
1247 compare_str(cx, lhs, rhs, rhs_t)
1249 _ => cx.sess().bug("only byte strings supported in compare_values"),
1251 _ => cx.sess().bug("on string and byte strings supported in compare_values"),
1253 _ => cx.sess().bug("only scalars, byte strings, and strings supported in compare_values"),
1257 fn insert_lllocals<'a>(mut bcx: &'a Block<'a>,
1258 bindings_map: &BindingsMap,
1259 cleanup_scope: cleanup::ScopeId)
1262 * For each binding in `data.bindings_map`, adds an appropriate entry into
1263 * the `fcx.lllocals` map, scheduling cleanup in `cleanup_scope`.
1268 for (&ident, &binding_info) in bindings_map.iter() {
1269 let llval = match binding_info.trmode {
1270 // By value mut binding for a copy type: load from the ptr
1271 // into the matched value and copy to our alloca
1272 TrByCopy(llbinding) => {
1273 let llval = Load(bcx, binding_info.llmatch);
1274 let datum = Datum::new(llval, binding_info.ty, Lvalue);
1275 bcx = datum.store_to(bcx, llbinding);
1280 // By value move bindings: load from the ptr into the matched value
1281 TrByMove => Load(bcx, binding_info.llmatch),
1283 // By ref binding: use the ptr into the matched value
1284 TrByRef => binding_info.llmatch
1287 let datum = Datum::new(llval, binding_info.ty, Lvalue);
1288 fcx.schedule_drop_mem(cleanup_scope, llval, binding_info.ty);
1290 debug!("binding {:?} to {}",
1292 bcx.val_to_str(llval));
1293 bcx.fcx.lllocals.borrow_mut().insert(binding_info.id, datum);
1295 if bcx.sess().opts.debuginfo == FullDebugInfo {
1296 debuginfo::create_match_binding_metadata(bcx,
1304 fn compile_guard<'a, 'b>(
1306 guard_expr: &ast::Expr,
1308 m: &'a [Match<'a, 'b>],
1310 chk: &FailureHandler,
1311 has_genuine_default: bool)
1313 debug!("compile_guard(bcx={}, guard_expr={}, m={}, vals={})",
1315 bcx.expr_to_str(guard_expr),
1317 vec_map_to_str(vals, |v| bcx.val_to_str(*v)));
1318 let _indenter = indenter();
1320 // Lest the guard itself should fail, introduce a temporary cleanup
1321 // scope for any non-ref bindings we create.
1322 let temp_scope = bcx.fcx.push_custom_cleanup_scope();
1324 let mut bcx = insert_lllocals(bcx, &data.bindings_map,
1325 cleanup::CustomScope(temp_scope));
1327 let val = unpack_datum!(bcx, expr::trans(bcx, guard_expr));
1328 let val = val.to_llbool(bcx);
1330 // Cancel cleanups now that the guard successfully executed. If
1331 // the guard was false, we will drop the values explicitly
1332 // below. Otherwise, we'll add lvalue cleanups at the end.
1333 bcx.fcx.pop_custom_cleanup_scope(temp_scope);
1335 return with_cond(bcx, Not(bcx, val), |bcx| {
1336 // Guard does not match: remove all bindings from the lllocals table
1337 for (_, &binding_info) in data.bindings_map.iter() {
1338 bcx.fcx.lllocals.borrow_mut().remove(&binding_info.id);
1341 // If the default arm is the only one left, move on to the next
1342 // condition explicitly rather than (possibly) falling back to
1344 &JumpToBasicBlock(_) if m.len() == 1 && has_genuine_default => {
1345 Br(bcx, chk.handle_fail());
1348 compile_submatch(bcx, m, vals, chk, has_genuine_default);
1355 fn compile_submatch<'a, 'b>(
1357 m: &'a [Match<'a, 'b>],
1359 chk: &FailureHandler,
1360 has_genuine_default: bool) {
1361 debug!("compile_submatch(bcx={}, m={}, vals={})",
1364 vec_map_to_str(vals, |v| bcx.val_to_str(*v)));
1365 let _indenter = indenter();
1366 let _icx = push_ctxt("match::compile_submatch");
1369 if chk.is_fallible() {
1370 Br(bcx, chk.handle_fail());
1374 if m[0].pats.len() == 0u {
1375 let data = &m[0].data;
1376 for &(ref ident, ref value_ptr) in m[0].bound_ptrs.iter() {
1377 let llmatch = data.bindings_map.get(ident).llmatch;
1378 Store(bcx, *value_ptr, llmatch);
1380 match data.arm.guard {
1381 Some(ref guard_expr) => {
1382 bcx = compile_guard(bcx,
1385 m.slice(1, m.len()),
1388 has_genuine_default);
1392 Br(bcx, data.bodycx.llbb);
1396 let col = pick_col(m);
1397 let val = vals[col];
1399 if has_nested_bindings(m, col) {
1400 let expanded = expand_nested_bindings(bcx, m, col, val);
1401 compile_submatch_continue(bcx,
1402 expanded.as_slice(),
1407 has_genuine_default)
1409 compile_submatch_continue(bcx, m, vals, chk, col, val, has_genuine_default)
1413 fn compile_submatch_continue<'a, 'b>(
1414 mut bcx: &'b Block<'b>,
1415 m: &'a [Match<'a, 'b>],
1417 chk: &FailureHandler,
1420 has_genuine_default: bool) {
1422 let tcx = bcx.tcx();
1423 let dm = &tcx.def_map;
1425 let vals_left = Vec::from_slice(vals.slice(0u, col)).append(vals.slice(col + 1u, vals.len()));
1426 let ccx = bcx.fcx.ccx;
1428 for br in m.iter() {
1429 // Find a real id (we're adding placeholder wildcard patterns, but
1430 // each column is guaranteed to have at least one real pattern)
1432 pat_id = br.pats.get(col).id;
1436 match collect_record_or_struct_fields(bcx, m, col) {
1437 Some(ref rec_fields) => {
1438 let pat_ty = node_id_type(bcx, pat_id);
1439 let pat_repr = adt::represent_type(bcx.ccx(), pat_ty);
1440 expr::with_field_tys(tcx, pat_ty, Some(pat_id), |discr, field_tys| {
1441 let rec_vals = rec_fields.iter().map(|field_name| {
1442 let ix = ty::field_idx_strict(tcx, field_name.name, field_tys);
1443 adt::trans_field_ptr(bcx, &*pat_repr, val, discr, ix)
1444 }).collect::<Vec<_>>();
1447 enter_rec_or_struct(bcx,
1451 rec_fields.as_slice(),
1453 rec_vals.append(vals_left.as_slice()).as_slice(),
1454 chk, has_genuine_default);
1461 if any_tup_pat(m, col) {
1462 let tup_ty = node_id_type(bcx, pat_id);
1463 let tup_repr = adt::represent_type(bcx.ccx(), tup_ty);
1464 let n_tup_elts = match ty::get(tup_ty).sty {
1465 ty::ty_tup(ref elts) => elts.len(),
1466 _ => ccx.sess().bug("non-tuple type in tuple pattern")
1468 let tup_vals = Vec::from_fn(n_tup_elts, |i| {
1469 adt::trans_field_ptr(bcx, &*tup_repr, val, 0, i)
1471 compile_submatch(bcx,
1477 n_tup_elts).as_slice(),
1478 tup_vals.append(vals_left.as_slice()).as_slice(),
1479 chk, has_genuine_default);
1483 if any_tuple_struct_pat(bcx, m, col) {
1484 let struct_ty = node_id_type(bcx, pat_id);
1485 let struct_element_count;
1486 match ty::get(struct_ty).sty {
1487 ty::ty_struct(struct_id, _) => {
1488 struct_element_count =
1489 ty::lookup_struct_fields(tcx, struct_id).len();
1492 ccx.sess().bug("non-struct type in tuple struct pattern");
1496 let struct_repr = adt::represent_type(bcx.ccx(), struct_ty);
1497 let llstructvals = Vec::from_fn(struct_element_count, |i| {
1498 adt::trans_field_ptr(bcx, &*struct_repr, val, 0, i)
1500 compile_submatch(bcx,
1501 enter_tuple_struct(bcx, dm, m, col, val,
1502 struct_element_count).as_slice(),
1503 llstructvals.append(vals_left.as_slice()).as_slice(),
1504 chk, has_genuine_default);
1508 if any_uniq_pat(m, col) {
1509 let llbox = Load(bcx, val);
1510 compile_submatch(bcx,
1511 enter_uniq(bcx, dm, m, col, val).as_slice(),
1512 (vec!(llbox)).append(vals_left.as_slice()).as_slice(),
1513 chk, has_genuine_default);
1517 if any_region_pat(m, col) {
1518 let loaded_val = Load(bcx, val);
1519 compile_submatch(bcx,
1520 enter_region(bcx, dm, m, col, val).as_slice(),
1521 (vec!(loaded_val)).append(vals_left.as_slice()).as_slice(),
1522 chk, has_genuine_default);
1526 // Decide what kind of branch we need
1527 let opts = get_options(bcx, m, col);
1528 debug!("options={:?}", opts);
1529 let mut kind = no_branch;
1530 let mut test_val = val;
1531 debug!("test_val={}", bcx.val_to_str(test_val));
1532 if opts.len() > 0u {
1533 match *opts.get(0) {
1534 var(_, ref repr) => {
1535 let (the_kind, val_opt) = adt::trans_switch(bcx, &**repr, val);
1537 for &tval in val_opt.iter() { test_val = tval; }
1540 let pty = node_id_type(bcx, pat_id);
1541 test_val = load_if_immediate(bcx, val, pty);
1542 kind = if ty::type_is_integral(pty) { switch }
1546 test_val = Load(bcx, val);
1550 let vec_ty = node_id_type(bcx, pat_id);
1551 let (_, len) = tvec::get_base_and_len(bcx, val, vec_ty);
1553 kind = compare_vec_len;
1557 for o in opts.iter() {
1559 range(_, _) => { kind = compare; break }
1563 let else_cx = match kind {
1564 no_branch | single => bcx,
1565 _ => bcx.fcx.new_temp_block("match_else")
1567 let sw = if kind == switch {
1568 Switch(bcx, test_val, else_cx.llbb, opts.len())
1570 C_int(ccx, 0) // Placeholder for when not using a switch
1573 let defaults = enter_default(else_cx, dm, m, col, val);
1574 let exhaustive = chk.is_infallible() && defaults.len() == 0u;
1575 let len = opts.len();
1577 // Compile subtrees for each option
1578 for (i, opt) in opts.iter().enumerate() {
1579 // In some cases of range and vector pattern matching, we need to
1580 // override the failure case so that instead of failing, it proceeds
1581 // to try more matching. branch_chk, then, is the proper failure case
1582 // for the current conditional branch.
1583 let mut branch_chk = None;
1584 let mut opt_cx = else_cx;
1585 if !exhaustive || i+1 < len {
1586 opt_cx = bcx.fcx.new_temp_block("match_case");
1588 single => Br(bcx, opt_cx.llbb),
1590 match trans_opt(bcx, opt) {
1591 single_result(r) => {
1593 llvm::LLVMAddCase(sw, r.val, opt_cx.llbb);
1599 "in compile_submatch, expected \
1600 trans_opt to return a single_result")
1605 let t = node_id_type(bcx, pat_id);
1606 let Result {bcx: after_cx, val: matches} = {
1607 match trans_opt(bcx, opt) {
1608 single_result(Result {bcx, val}) => {
1609 compare_values(bcx, test_val, val, t)
1611 lower_bound(Result {bcx, val}) => {
1612 compare_scalar_types(
1616 range_result(Result {val: vbegin, ..},
1617 Result {bcx, val: vend}) => {
1618 let Result {bcx, val: llge} =
1619 compare_scalar_types(
1621 vbegin, t, ast::BiGe);
1622 let Result {bcx, val: llle} =
1623 compare_scalar_types(
1624 bcx, test_val, vend,
1626 Result::new(bcx, And(bcx, llge, llle))
1630 bcx = fcx.new_temp_block("compare_next");
1632 // If none of the sub-cases match, and the current condition
1633 // is guarded or has multiple patterns, move on to the next
1634 // condition, if there is any, rather than falling back to
1636 let guarded = m[i].data.arm.guard.is_some();
1637 let multi_pats = m[i].pats.len() > 1;
1638 if i+1 < len && (guarded || multi_pats) {
1639 branch_chk = Some(JumpToBasicBlock(bcx.llbb));
1641 CondBr(after_cx, matches, opt_cx.llbb, bcx.llbb);
1643 compare_vec_len => {
1644 let Result {bcx: after_cx, val: matches} = {
1645 match trans_opt(bcx, opt) {
1647 Result {bcx, val}) => {
1648 let value = compare_scalar_values(
1650 signed_int, ast::BiEq);
1651 Result::new(bcx, value)
1654 Result {bcx, val: val}) => {
1655 let value = compare_scalar_values(
1657 signed_int, ast::BiGe);
1658 Result::new(bcx, value)
1661 Result {val: vbegin, ..},
1662 Result {bcx, val: vend}) => {
1664 compare_scalar_values(
1666 vbegin, signed_int, ast::BiGe);
1668 compare_scalar_values(
1669 bcx, test_val, vend,
1670 signed_int, ast::BiLe);
1671 Result::new(bcx, And(bcx, llge, llle))
1675 bcx = fcx.new_temp_block("compare_vec_len_next");
1677 // If none of these subcases match, move on to the
1678 // next condition if there is any.
1680 branch_chk = Some(JumpToBasicBlock(bcx.llbb));
1682 CondBr(after_cx, matches, opt_cx.llbb, bcx.llbb);
1686 } else if kind == compare || kind == compare_vec_len {
1687 Br(bcx, else_cx.llbb);
1691 let mut unpacked = Vec::new();
1693 var(disr_val, ref repr) => {
1694 let ExtractedBlock {vals: argvals, bcx: new_bcx} =
1695 extract_variant_args(opt_cx, &**repr, disr_val, val);
1696 size = argvals.len();
1700 vec_len(n, vt, _) => {
1701 let (n, slice) = match vt {
1702 vec_len_ge(i) => (n + 1u, Some(i)),
1703 vec_len_eq => (n, None)
1705 let args = extract_vec_elems(opt_cx, pat_id, n,
1707 size = args.vals.len();
1708 unpacked = args.vals.clone();
1711 lit(_) | range(_, _) => ()
1713 let opt_ms = enter_opt(opt_cx, m, opt, col, size, val);
1714 let opt_vals = unpacked.append(vals_left.as_slice());
1718 compile_submatch(opt_cx,
1720 opt_vals.as_slice(),
1722 has_genuine_default)
1724 Some(branch_chk) => {
1725 compile_submatch(opt_cx,
1727 opt_vals.as_slice(),
1729 has_genuine_default)
1734 // Compile the fall-through case, if any
1735 if !exhaustive && kind != single {
1736 if kind == compare || kind == compare_vec_len {
1737 Br(bcx, else_cx.llbb);
1740 // If there is only one default arm left, move on to the next
1741 // condition explicitly rather than (eventually) falling back to
1742 // the last default arm.
1743 &JumpToBasicBlock(_) if defaults.len() == 1 && has_genuine_default => {
1744 Br(else_cx, chk.handle_fail());
1747 compile_submatch(else_cx,
1748 defaults.as_slice(),
1749 vals_left.as_slice(),
1751 has_genuine_default);
1757 pub fn trans_match<'a>(
1759 match_expr: &ast::Expr,
1760 discr_expr: &ast::Expr,
1764 let _icx = push_ctxt("match::trans_match");
1765 trans_match_inner(bcx, match_expr.id, discr_expr, arms, dest)
1768 fn create_bindings_map(bcx: &Block, pat: Gc<ast::Pat>) -> BindingsMap {
1769 // Create the bindings map, which is a mapping from each binding name
1770 // to an alloca() that will be the value for that local variable.
1771 // Note that we use the names because each binding will have many ids
1772 // from the various alternatives.
1773 let ccx = bcx.ccx();
1774 let tcx = bcx.tcx();
1775 let mut bindings_map = HashMap::new();
1776 pat_bindings(&tcx.def_map, &*pat, |bm, p_id, span, path| {
1777 let ident = path_to_ident(path);
1778 let variable_ty = node_id_type(bcx, p_id);
1779 let llvariable_ty = type_of::type_of(ccx, variable_ty);
1780 let tcx = bcx.tcx();
1786 if !ty::type_moves_by_default(tcx, variable_ty) => {
1787 llmatch = alloca(bcx,
1788 llvariable_ty.ptr_to(),
1790 trmode = TrByCopy(alloca(bcx,
1792 bcx.ident(ident).as_slice()));
1794 ast::BindByValue(_) => {
1795 // in this case, the final type of the variable will be T,
1796 // but during matching we need to store a *T as explained
1798 llmatch = alloca(bcx,
1799 llvariable_ty.ptr_to(),
1800 bcx.ident(ident).as_slice());
1803 ast::BindByRef(_) => {
1804 llmatch = alloca(bcx,
1806 bcx.ident(ident).as_slice());
1810 bindings_map.insert(ident, BindingInfo {
1818 return bindings_map;
1821 fn trans_match_inner<'a>(scope_cx: &'a Block<'a>,
1822 match_id: ast::NodeId,
1823 discr_expr: &ast::Expr,
1825 dest: Dest) -> &'a Block<'a> {
1826 let _icx = push_ctxt("match::trans_match_inner");
1827 let fcx = scope_cx.fcx;
1828 let mut bcx = scope_cx;
1829 let tcx = bcx.tcx();
1831 let discr_datum = unpack_datum!(bcx, expr::trans_to_lvalue(bcx, discr_expr,
1833 if bcx.unreachable.get() {
1837 let t = node_id_type(bcx, discr_expr.id);
1839 if ty::type_is_empty(tcx, t) {
1840 // Special case for empty types
1841 let fail_cx = Cell::new(None);
1842 let fail_handler = box DynamicFailureHandler {
1844 sp: discr_expr.span,
1845 msg: InternedString::new("scrutinizing value that can't \
1849 DynamicFailureHandlerClass(fail_handler)
1855 let arm_datas: Vec<ArmData> = arms.iter().map(|arm| ArmData {
1856 bodycx: fcx.new_id_block("case_body", arm.body.id),
1858 bindings_map: create_bindings_map(bcx, *arm.pats.get(0))
1861 let mut matches = Vec::new();
1862 for arm_data in arm_datas.iter() {
1863 matches.extend(arm_data.arm.pats.iter().map(|p| Match {
1866 bound_ptrs: Vec::new(),
1870 // `compile_submatch` works one column of arm patterns a time and
1871 // then peels that column off. So as we progress, it may become
1872 // impossible to tell whether we have a genuine default arm, i.e.
1873 // `_ => foo` or not. Sometimes it is important to know that in order
1874 // to decide whether moving on to the next condition or falling back
1875 // to the default arm.
1876 let has_default = arms.last().map_or(false, |arm| {
1878 && arm.pats.last().unwrap().node == ast::PatWild
1881 compile_submatch(bcx, matches.as_slice(), [discr_datum.val], &chk, has_default);
1883 let mut arm_cxs = Vec::new();
1884 for arm_data in arm_datas.iter() {
1885 let mut bcx = arm_data.bodycx;
1887 // insert bindings into the lllocals map and add cleanups
1888 let cleanup_scope = fcx.push_custom_cleanup_scope();
1889 bcx = insert_lllocals(bcx, &arm_data.bindings_map,
1890 cleanup::CustomScope(cleanup_scope));
1891 bcx = expr::trans_into(bcx, &*arm_data.arm.body, dest);
1892 bcx = fcx.pop_and_trans_custom_cleanup_scope(bcx, cleanup_scope);
1896 bcx = scope_cx.fcx.join_blocks(match_id, arm_cxs.as_slice());
1900 enum IrrefutablePatternBindingMode {
1901 // Stores the association between node ID and LLVM value in `lllocals`.
1903 // Stores the association between node ID and LLVM value in `llargs`.
1907 pub fn store_local<'a>(bcx: &'a Block<'a>,
1911 * Generates code for a local variable declaration like
1912 * `let <pat>;` or `let <pat> = <opt_init_expr>`.
1914 let _icx = push_ctxt("match::store_local");
1916 let tcx = bcx.tcx();
1917 let pat = local.pat;
1918 let opt_init_expr = local.init;
1920 return match opt_init_expr {
1921 Some(init_expr) => {
1922 // Optimize the "let x = expr" case. This just writes
1923 // the result of evaluating `expr` directly into the alloca
1924 // for `x`. Often the general path results in similar or the
1925 // same code post-optimization, but not always. In particular,
1926 // in unsafe code, you can have expressions like
1928 // let x = intrinsics::uninit();
1930 // In such cases, the more general path is unsafe, because
1931 // it assumes it is matching against a valid value.
1932 match simple_identifier(&*pat) {
1934 let var_scope = cleanup::var_scope(tcx, local.id);
1935 return mk_binding_alloca(
1936 bcx, pat.id, path, BindLocal, var_scope, (),
1937 |(), bcx, v, _| expr::trans_into(bcx, &*init_expr,
1946 unpack_datum!(bcx, expr::trans_to_lvalue(bcx, &*init_expr, "let"));
1947 if ty::type_is_bot(expr_ty(bcx, &*init_expr)) {
1948 create_dummy_locals(bcx, pat)
1950 if bcx.sess().asm_comments() {
1951 add_comment(bcx, "creating zeroable ref llval");
1953 let var_scope = cleanup::var_scope(tcx, local.id);
1954 bind_irrefutable_pat(bcx, pat, init_datum.val, BindLocal, var_scope)
1958 create_dummy_locals(bcx, pat)
1962 fn create_dummy_locals<'a>(mut bcx: &'a Block<'a>,
1965 // create dummy memory for the variables if we have no
1966 // value to store into them immediately
1967 let tcx = bcx.tcx();
1968 pat_bindings(&tcx.def_map, &*pat, |_, p_id, _, path| {
1969 let scope = cleanup::var_scope(tcx, p_id);
1970 bcx = mk_binding_alloca(
1971 bcx, p_id, path, BindLocal, scope, (),
1972 |(), bcx, llval, ty| { zero_mem(bcx, llval, ty); bcx });
1978 pub fn store_arg<'a>(mut bcx: &'a Block<'a>,
1981 arg_scope: cleanup::ScopeId)
1984 * Generates code for argument patterns like `fn foo(<pat>: T)`.
1985 * Creates entries in the `llargs` map for each of the bindings
1990 * - `pat` is the argument pattern
1991 * - `llval` is a pointer to the argument value (in other words,
1992 * if the argument type is `T`, then `llval` is a `T*`). In some
1993 * cases, this code may zero out the memory `llval` points at.
1996 let _icx = push_ctxt("match::store_arg");
1998 match simple_identifier(&*pat) {
2000 // Generate nicer LLVM for the common case of fn a pattern
2002 let arg_ty = node_id_type(bcx, pat.id);
2003 if type_of::arg_is_indirect(bcx.ccx(), arg_ty)
2004 && bcx.sess().opts.debuginfo != FullDebugInfo {
2005 // Don't copy an indirect argument to an alloca, the caller
2006 // already put it in a temporary alloca and gave it up, unless
2007 // we emit extra-debug-info, which requires local allocas :(.
2008 let arg_val = arg.add_clean(bcx.fcx, arg_scope);
2009 bcx.fcx.llargs.borrow_mut()
2010 .insert(pat.id, Datum::new(arg_val, arg_ty, Lvalue));
2014 bcx, pat.id, path, BindArgument, arg_scope, arg,
2015 |arg, bcx, llval, _| arg.store_to(bcx, llval))
2020 // General path. Copy out the values that are used in the
2022 let arg = unpack_datum!(
2023 bcx, arg.to_lvalue_datum_in_scope(bcx, "__arg", arg_scope));
2024 bind_irrefutable_pat(bcx, pat, arg.val,
2025 BindArgument, arg_scope)
2030 fn mk_binding_alloca<'a,A>(bcx: &'a Block<'a>,
2033 binding_mode: IrrefutablePatternBindingMode,
2034 cleanup_scope: cleanup::ScopeId,
2036 populate: |A, &'a Block<'a>, ValueRef, ty::t| -> &'a Block<'a>)
2038 let var_ty = node_id_type(bcx, p_id);
2039 let ident = ast_util::path_to_ident(path);
2041 // Allocate memory on stack for the binding.
2042 let llval = alloc_ty(bcx, var_ty, bcx.ident(ident).as_slice());
2044 // Subtle: be sure that we *populate* the memory *before*
2045 // we schedule the cleanup.
2046 let bcx = populate(arg, bcx, llval, var_ty);
2047 bcx.fcx.schedule_drop_mem(cleanup_scope, llval, var_ty);
2049 // Now that memory is initialized and has cleanup scheduled,
2050 // create the datum and insert into the local variable map.
2051 let datum = Datum::new(llval, var_ty, Lvalue);
2052 let mut llmap = match binding_mode {
2053 BindLocal => bcx.fcx.lllocals.borrow_mut(),
2054 BindArgument => bcx.fcx.llargs.borrow_mut()
2056 llmap.insert(p_id, datum);
2060 fn bind_irrefutable_pat<'a>(
2064 binding_mode: IrrefutablePatternBindingMode,
2065 cleanup_scope: cleanup::ScopeId)
2068 * A simple version of the pattern matching code that only handles
2069 * irrefutable patterns. This is used in let/argument patterns,
2070 * not in match statements. Unifying this code with the code above
2071 * sounds nice, but in practice it produces very inefficient code,
2072 * since the match code is so much more general. In most cases,
2073 * LLVM is able to optimize the code, but it causes longer compile
2074 * times and makes the generated code nigh impossible to read.
2077 * - bcx: starting basic block context
2078 * - pat: the irrefutable pattern being matched.
2079 * - val: the value being matched -- must be an lvalue (by ref, with cleanup)
2080 * - binding_mode: is this for an argument or a local variable?
2083 debug!("bind_irrefutable_pat(bcx={}, pat={}, binding_mode={:?})",
2085 pat.repr(bcx.tcx()),
2088 if bcx.sess().asm_comments() {
2089 add_comment(bcx, format!("bind_irrefutable_pat(pat={})",
2090 pat.repr(bcx.tcx())).as_slice());
2093 let _indenter = indenter();
2095 let _icx = push_ctxt("match::bind_irrefutable_pat");
2097 let tcx = bcx.tcx();
2098 let ccx = bcx.ccx();
2100 ast::PatIdent(pat_binding_mode, ref path, inner) => {
2101 if pat_is_binding(&tcx.def_map, &*pat) {
2102 // Allocate the stack slot where the value of this
2103 // binding will live and place it into the appropriate
2105 bcx = mk_binding_alloca(
2106 bcx, pat.id, path, binding_mode, cleanup_scope, (),
2107 |(), bcx, llval, ty| {
2108 match pat_binding_mode {
2109 ast::BindByValue(_) => {
2110 // By value binding: move the value that `val`
2111 // points at into the binding's stack slot.
2112 let d = Datum::new(val, ty, Lvalue);
2113 d.store_to(bcx, llval)
2116 ast::BindByRef(_) => {
2117 // By ref binding: the value of the variable
2118 // is the pointer `val` itself.
2119 Store(bcx, val, llval);
2126 for &inner_pat in inner.iter() {
2127 bcx = bind_irrefutable_pat(bcx, inner_pat, val,
2128 binding_mode, cleanup_scope);
2131 ast::PatEnum(_, ref sub_pats) => {
2132 let opt_def = bcx.tcx().def_map.borrow().find_copy(&pat.id);
2134 Some(def::DefVariant(enum_id, var_id, _)) => {
2135 let repr = adt::represent_node(bcx, pat.id);
2136 let vinfo = ty::enum_variant_with_id(ccx.tcx(),
2139 let args = extract_variant_args(bcx,
2143 for sub_pat in sub_pats.iter() {
2144 for (i, argval) in args.vals.iter().enumerate() {
2145 bcx = bind_irrefutable_pat(bcx, *sub_pat.get(i),
2146 *argval, binding_mode,
2151 Some(def::DefFn(..)) |
2152 Some(def::DefStruct(..)) => {
2155 // This is a unit-like struct. Nothing to do here.
2157 Some(ref elems) => {
2158 // This is the tuple struct case.
2159 let repr = adt::represent_node(bcx, pat.id);
2160 for (i, elem) in elems.iter().enumerate() {
2161 let fldptr = adt::trans_field_ptr(bcx, &*repr,
2163 bcx = bind_irrefutable_pat(bcx, *elem,
2164 fldptr, binding_mode,
2170 Some(def::DefStatic(_, false)) => {
2173 // Nothing to do here.
2177 ast::PatStruct(_, ref fields, _) => {
2178 let tcx = bcx.tcx();
2179 let pat_ty = node_id_type(bcx, pat.id);
2180 let pat_repr = adt::represent_type(bcx.ccx(), pat_ty);
2181 expr::with_field_tys(tcx, pat_ty, Some(pat.id), |discr, field_tys| {
2182 for f in fields.iter() {
2183 let ix = ty::field_idx_strict(tcx, f.ident.name, field_tys);
2184 let fldptr = adt::trans_field_ptr(bcx, &*pat_repr, val,
2186 bcx = bind_irrefutable_pat(bcx, f.pat, fldptr,
2187 binding_mode, cleanup_scope);
2191 ast::PatTup(ref elems) => {
2192 let repr = adt::represent_node(bcx, pat.id);
2193 for (i, elem) in elems.iter().enumerate() {
2194 let fldptr = adt::trans_field_ptr(bcx, &*repr, val, 0, i);
2195 bcx = bind_irrefutable_pat(bcx, *elem, fldptr,
2196 binding_mode, cleanup_scope);
2199 ast::PatBox(inner) => {
2200 let llbox = Load(bcx, val);
2201 bcx = bind_irrefutable_pat(bcx, inner, llbox, binding_mode, cleanup_scope);
2203 ast::PatRegion(inner) => {
2204 let loaded_val = Load(bcx, val);
2205 bcx = bind_irrefutable_pat(bcx, inner, loaded_val, binding_mode, cleanup_scope);
2207 ast::PatVec(ref before, ref slice, ref after) => {
2208 let extracted = extract_vec_elems(
2209 bcx, pat.id, before.len() + 1u + after.len(),
2210 slice.map(|_| before.len()), val
2213 .iter().map(|v| Some(*v))
2214 .chain(Some(*slice).move_iter())
2215 .chain(after.iter().map(|v| Some(*v)))
2216 .zip(extracted.vals.iter())
2217 .fold(bcx, |bcx, (inner, elem)| {
2218 inner.map_or(bcx, |inner| {
2219 bind_irrefutable_pat(bcx, inner, *elem, binding_mode, cleanup_scope)
2223 ast::PatMac(..) => {
2224 bcx.sess().span_bug(pat.span, "unexpanded macro");
2226 ast::PatWild | ast::PatWildMulti | ast::PatLit(_) | ast::PatRange(_, _) => ()