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 up to two LLVM values, called `llmatch` and
68 * `llbinding` respectively (the `llbinding`, as will be described shortly, is
69 * optional and only present for by-value bindings---therefore it is bundled
70 * up as part of the `TransBindingMode` type). Both point at allocas.
72 * The `llmatch` binding always stores a pointer into the value being matched
73 * which points at the data for the binding. If the value being matched has
74 * type `T`, then, `llmatch` will point at an alloca of type `T*` (and hence
75 * `llmatch` has type `T**`). So, if you have a pattern like:
79 * match (a, b) { (ref c, d) => { ... } }
81 * For `c` and `d`, we would generate allocas of type `C*` and `D*`
82 * respectively. These are called the `llmatch`. As we match, when we come
83 * up against an identifier, we store the current pointer into the
84 * corresponding alloca.
86 * In addition, for each by-value binding (copy or move), we will create a
87 * second alloca (`llbinding`) that will hold the final value. In this
88 * example, that means that `d` would have this second alloca of type `D` (and
89 * hence `llbinding` has type `D*`).
91 * Once a pattern is completely matched, and assuming that there is no guard
92 * pattern, we will branch to a block that leads to the body itself. For any
93 * by-value bindings, this block will first load the ptr from `llmatch` (the
94 * one of type `D*`) and copy/move the value into `llbinding` (the one of type
95 * `D`). The second alloca then becomes the value of the local variable. For
96 * by ref bindings, the value of the local variable is simply the first
99 * So, for the example above, we would generate a setup kind of like this:
105 * +-------------------------------------------+
106 * | llmatch_c = (addr of first half of tuple) |
107 * | llmatch_d = (addr of first half of tuple) |
108 * +-------------------------------------------+
110 * +--------------------------------------+
111 * | *llbinding_d = **llmatch_dlbinding_d |
112 * +--------------------------------------+
114 * If there is a guard, the situation is slightly different, because we must
115 * execute the guard code. Moreover, we need to do so once for each of the
116 * alternatives that lead to the arm, because if the guard fails, they may
117 * have different points from which to continue the search. Therefore, in that
118 * case, we generate code that looks more like:
124 * +-------------------------------------------+
125 * | llmatch_c = (addr of first half of tuple) |
126 * | llmatch_d = (addr of first half of tuple) |
127 * +-------------------------------------------+
129 * +-------------------------------------------------+
130 * | *llbinding_d = **llmatch_dlbinding_d |
131 * | check condition |
132 * | if false { free *llbinding_d, goto next case } |
133 * | if true { goto body } |
134 * +-------------------------------------------------+
136 * The handling for the cleanups is a bit... sensitive. Basically, the body
137 * is the one that invokes `add_clean()` for each binding. During the guard
138 * evaluation, we add temporary cleanups and revoke them after the guard is
139 * evaluated (it could fail, after all). Presuming the guard fails, we drop
140 * the various values we copied explicitly. Note that guards and moves are
141 * just plain incompatible.
143 * Some relevant helper functions that manage bindings:
144 * - `create_bindings_map()`
145 * - `store_non_ref_bindings()`
146 * - `insert_lllocals()`
149 * ## Notes on vector pattern matching.
151 * Vector pattern matching is surprisingly tricky. The problem is that
152 * the structure of the vector isn't fully known, and slice matches
153 * can be done on subparts of it.
155 * The way that vector pattern matches are dealt with, then, is as
156 * follows. First, we make the actual condition associated with a
157 * vector pattern simply a vector length comparison. So the pattern
158 * [1, .. x] gets the condition "vec len >= 1", and the pattern
159 * [.. x] gets the condition "vec len >= 0". The problem here is that
160 * having the condition "vec len >= 1" hold clearly does not mean that
161 * only a pattern that has exactly that condition will match. This
162 * means that it may well be the case that a condition holds, but none
163 * of the patterns matching that condition match; to deal with this,
164 * when doing vector length matches, we have match failures proceed to
165 * the next condition to check.
167 * There are a couple more subtleties to deal with. While the "actual"
168 * condition associated with vector length tests is simply a test on
169 * the vector length, the actual vec_len Opt entry contains more
170 * information used to restrict which matches are associated with it.
171 * So that all matches in a submatch are matching against the same
172 * values from inside the vector, they are split up by how many
173 * elements they match at the front and at the back of the vector. In
174 * order to make sure that arms are properly checked in order, even
175 * with the overmatching conditions, each vec_len Opt entry is
176 * associated with a range of matches.
177 * Consider the following:
181 * [1, 2, 2, .. _] => 1,
182 * [1, 2, 3, .. _] => 2,
186 * The proper arm to match is arm 2, but arms 0 and 3 both have the
187 * condition "len >= 2". If arm 3 was lumped in with arm 0, then the
188 * wrong branch would be taken. Instead, vec_len Opts are associated
189 * with a contiguous range of matches that have the same "shape".
190 * This is sort of ugly and requires a bunch of special handling of
195 #![allow(non_camel_case_types)]
198 use driver::session::FullDebugInfo;
199 use lib::llvm::{llvm, ValueRef, BasicBlockRef};
200 use middle::const_eval;
201 use middle::borrowck::root_map_key;
202 use middle::lang_items::{UniqStrEqFnLangItem, StrEqFnLangItem};
203 use middle::pat_util::*;
204 use middle::resolve::DefMap;
205 use middle::trans::adt;
206 use middle::trans::base::*;
207 use middle::trans::build::*;
208 use middle::trans::callee;
209 use middle::trans::cleanup;
210 use middle::trans::cleanup::CleanupMethods;
211 use middle::trans::common::*;
212 use middle::trans::consts;
213 use middle::trans::controlflow;
214 use middle::trans::datum;
215 use middle::trans::datum::*;
216 use middle::trans::expr::Dest;
217 use middle::trans::expr;
218 use middle::trans::glue;
219 use middle::trans::tvec;
220 use middle::trans::type_of;
221 use middle::trans::debuginfo;
223 use util::common::indenter;
224 use util::ppaux::{Repr, vec_map_to_str};
226 use collections::HashMap;
230 use syntax::ast::Ident;
231 use syntax::ast_util::path_to_ident;
232 use syntax::ast_util;
233 use syntax::codemap::{Span, DUMMY_SP};
234 use syntax::parse::token::InternedString;
236 // An option identifying a literal: either a unit-like struct or an
239 UnitLikeStructLit(ast::NodeId), // the node ID of the pattern
241 ConstLit(ast::DefId), // the def ID of the constant
247 vec_len_ge(/* length of prefix */uint)
250 // An option identifying a branch (either a literal, an enum variant or a
254 var(ty::Disr, Rc<adt::Repr>),
255 range(@ast::Expr, @ast::Expr),
256 vec_len(/* length */ uint, VecLenOpt, /*range of matches*/(uint, uint))
259 fn lit_to_expr(tcx: &ty::ctxt, a: &Lit) -> @ast::Expr {
261 ExprLit(existing_a_expr) => existing_a_expr,
262 ConstLit(a_const) => const_eval::lookup_const_by_id(tcx, a_const).unwrap(),
263 UnitLikeStructLit(_) => fail!("lit_to_expr: unexpected struct lit"),
267 fn opt_eq(tcx: &ty::ctxt, a: &Opt, b: &Opt) -> bool {
269 (&lit(UnitLikeStructLit(a)), &lit(UnitLikeStructLit(b))) => a == b,
270 (&lit(a), &lit(b)) => {
271 let a_expr = lit_to_expr(tcx, &a);
272 let b_expr = lit_to_expr(tcx, &b);
273 match const_eval::compare_lit_exprs(tcx, a_expr, b_expr) {
274 Some(val1) => val1 == 0,
275 None => fail!("compare_list_exprs: type mismatch"),
278 (&range(a1, a2), &range(b1, b2)) => {
279 let m1 = const_eval::compare_lit_exprs(tcx, a1, b1);
280 let m2 = const_eval::compare_lit_exprs(tcx, a2, b2);
282 (Some(val1), Some(val2)) => (val1 == 0 && val2 == 0),
283 _ => fail!("compare_list_exprs: type mismatch"),
286 (&var(a, _), &var(b, _)) => a == b,
287 (&vec_len(a1, a2, _), &vec_len(b1, b2, _)) =>
288 a1 == b1 && a2 == b2,
293 fn opt_overlap(tcx: &ty::ctxt, a: &Opt, b: &Opt) -> bool {
295 (&lit(a), &lit(b)) => {
296 let a_expr = lit_to_expr(tcx, &a);
297 let b_expr = lit_to_expr(tcx, &b);
298 match const_eval::compare_lit_exprs(tcx, a_expr, b_expr) {
299 Some(val1) => val1 == 0,
300 None => fail!("opt_overlap: type mismatch"),
304 (&range(a1, a2), &range(b1, b2)) => {
305 let m1 = const_eval::compare_lit_exprs(tcx, a1, b2);
306 let m2 = const_eval::compare_lit_exprs(tcx, b1, a2);
308 // two ranges [a1, a2] and [b1, b2] overlap iff:
309 // a1 <= b2 && b1 <= a2
310 (Some(val1), Some(val2)) => (val1 <= 0 && val2 <= 0),
311 _ => fail!("opt_overlap: type mismatch"),
315 (&range(a1, a2), &lit(b)) | (&lit(b), &range(a1, a2)) => {
316 let b_expr = lit_to_expr(tcx, &b);
317 let m1 = const_eval::compare_lit_exprs(tcx, a1, b_expr);
318 let m2 = const_eval::compare_lit_exprs(tcx, a2, b_expr);
320 // b is in range [a1, a2] iff a1 <= b and b <= a2
321 (Some(val1), Some(val2)) => (val1 <= 0 && 0 <= val2),
322 _ => fail!("opt_overlap: type mismatch"),
325 _ => fail!("opt_overlap: expect lit or range")
329 pub enum opt_result<'a> {
330 single_result(Result<'a>),
331 lower_bound(Result<'a>),
332 range_result(Result<'a>, Result<'a>),
335 fn trans_opt<'a>(bcx: &'a Block<'a>, o: &Opt) -> opt_result<'a> {
336 let _icx = push_ctxt("match::trans_opt");
340 lit(ExprLit(lit_expr)) => {
341 let lit_datum = unpack_datum!(bcx, expr::trans(bcx, lit_expr));
342 let lit_datum = lit_datum.assert_rvalue(bcx); // literals are rvalues
343 let lit_datum = unpack_datum!(bcx, lit_datum.to_appropriate_datum(bcx));
344 return single_result(rslt(bcx, lit_datum.val));
346 lit(UnitLikeStructLit(pat_id)) => {
347 let struct_ty = ty::node_id_to_type(bcx.tcx(), pat_id);
348 let datum = datum::rvalue_scratch_datum(bcx, struct_ty, "");
349 return single_result(rslt(bcx, datum.val));
351 lit(ConstLit(lit_id)) => {
352 let (llval, _) = consts::get_const_val(bcx.ccx(), lit_id);
353 return single_result(rslt(bcx, llval));
355 var(disr_val, ref repr) => {
356 return adt::trans_case(bcx, &**repr, disr_val);
359 let (l1, _) = consts::const_expr(ccx, l1, true);
360 let (l2, _) = consts::const_expr(ccx, l2, true);
361 return range_result(rslt(bcx, l1), rslt(bcx, l2));
363 vec_len(n, vec_len_eq, _) => {
364 return single_result(rslt(bcx, C_int(ccx, n as int)));
366 vec_len(n, vec_len_ge(_), _) => {
367 return lower_bound(rslt(bcx, C_int(ccx, n as int)));
372 fn variant_opt(bcx: &Block, pat_id: ast::NodeId) -> Opt {
374 let def = ccx.tcx.def_map.borrow().get_copy(&pat_id);
376 ast::DefVariant(enum_id, var_id, _) => {
377 let variants = ty::enum_variants(ccx.tcx(), enum_id);
378 for v in (*variants).iter() {
380 return var(v.disr_val,
381 adt::represent_node(bcx, pat_id))
387 ast::DefStruct(_) => {
388 return lit(UnitLikeStructLit(pat_id));
391 ccx.sess().bug("non-variant or struct in variant_opt()");
397 enum TransBindingMode {
398 TrByValue(/*llbinding:*/ ValueRef),
403 * Information about a pattern binding:
404 * - `llmatch` is a pointer to a stack slot. The stack slot contains a
405 * pointer into the value being matched. Hence, llmatch has type `T**`
406 * where `T` is the value being matched.
407 * - `trmode` is the trans binding mode
408 * - `id` is the node id of the binding
409 * - `ty` is the Rust type of the binding */
413 trmode: TransBindingMode,
419 type BindingsMap = HashMap<Ident, BindingInfo>;
421 struct ArmData<'a, 'b> {
422 bodycx: &'b Block<'b>,
424 bindings_map: BindingsMap
429 * If all `pats` are matched then arm `data` will be executed.
430 * As we proceed `bound_ptrs` are filled with pointers to values to be bound,
431 * these pointers are stored in llmatch variables just before executing `data` arm.
433 struct Match<'a, 'b> {
434 pats: Vec<@ast::Pat>,
435 data: &'a ArmData<'a, 'b>,
436 bound_ptrs: Vec<(Ident, ValueRef)>
439 impl<'a, 'b> Repr for Match<'a, 'b> {
440 fn repr(&self, tcx: &ty::ctxt) -> ~str {
441 if tcx.sess.verbose() {
442 // for many programs, this just take too long to serialize
445 format!("{} pats", self.pats.len())
450 fn has_nested_bindings(m: &[Match], col: uint) -> bool {
452 match br.pats.get(col).node {
453 ast::PatIdent(_, _, Some(_)) => return true,
460 fn expand_nested_bindings<'a, 'b>(
462 m: &'a [Match<'a, 'b>],
465 -> Vec<Match<'a, 'b>> {
466 debug!("expand_nested_bindings(bcx={}, m={}, col={}, val={})",
470 bcx.val_to_str(val));
471 let _indenter = indenter();
474 match br.pats.get(col).node {
475 ast::PatIdent(_, ref path, Some(inner)) => {
476 let pats = Vec::from_slice(br.pats.slice(0u, col))
477 .append((vec!(inner))
478 .append(br.pats.slice(col + 1u, br.pats.len())).as_slice());
480 let mut bound_ptrs = br.bound_ptrs.clone();
481 bound_ptrs.push((path_to_ident(path), val));
485 bound_ptrs: bound_ptrs
489 pats: br.pats.clone(),
491 bound_ptrs: br.bound_ptrs.clone()
497 fn assert_is_binding_or_wild(bcx: &Block, p: @ast::Pat) {
498 if !pat_is_binding_or_wild(&bcx.tcx().def_map, p) {
501 format!("expected an identifier pattern but found p: {}",
506 type enter_pat<'a> = |@ast::Pat|: 'a -> Option<Vec<@ast::Pat>>;
508 fn enter_match<'a, 'b>(
511 m: &'a [Match<'a, 'b>],
515 -> Vec<Match<'a, 'b>> {
516 debug!("enter_match(bcx={}, m={}, col={}, val={})",
520 bcx.val_to_str(val));
521 let _indenter = indenter();
523 m.iter().filter_map(|br| {
524 e(*br.pats.get(col)).map(|sub| {
525 let pats = sub.append(br.pats.slice(0u, col))
526 .append(br.pats.slice(col + 1u, br.pats.len()));
528 let this = *br.pats.get(col);
529 let mut bound_ptrs = br.bound_ptrs.clone();
531 ast::PatIdent(_, ref path, None) => {
532 if pat_is_binding(dm, this) {
533 bound_ptrs.push((path_to_ident(path), val));
542 bound_ptrs: bound_ptrs
548 fn enter_default<'a, 'b>(
551 m: &'a [Match<'a, 'b>],
554 chk: &FailureHandler)
555 -> Vec<Match<'a, 'b>> {
556 debug!("enter_default(bcx={}, m={}, col={}, val={})",
560 bcx.val_to_str(val));
561 let _indenter = indenter();
563 // Collect all of the matches that can match against anything.
564 let matches = enter_match(bcx, dm, m, col, val, |p| {
566 ast::PatWild | ast::PatWildMulti | ast::PatTup(_) => Some(Vec::new()),
567 ast::PatIdent(_, _, None) if pat_is_binding(dm, p) => Some(Vec::new()),
572 // Ok, now, this is pretty subtle. A "default" match is a match
573 // that needs to be considered if none of the actual checks on the
574 // value being considered succeed. The subtlety lies in that sometimes
575 // identifier/wildcard matches are *not* default matches. Consider:
576 // "match x { _ if something => foo, true => bar, false => baz }".
577 // There is a wildcard match, but it is *not* a default case. The boolean
578 // case on the value being considered is exhaustive. If the case is
579 // exhaustive, then there are no defaults.
581 // We detect whether the case is exhaustive in the following
582 // somewhat kludgy way: if the last wildcard/binding match has a
583 // guard, then by non-redundancy, we know that there aren't any
584 // non guarded matches, and thus by exhaustiveness, we know that
585 // we don't need any default cases. If the check *isn't* nonexhaustive
586 // (because chk is Some), then we need the defaults anyways.
587 let is_exhaustive = match matches.last() {
588 Some(m) if m.data.arm.guard.is_some() && chk.is_infallible() => true,
592 if is_exhaustive { Vec::new() } else { matches }
595 // <pcwalton> nmatsakis: what does enter_opt do?
596 // <pcwalton> in trans/match
597 // <pcwalton> trans/match.rs is like stumbling around in a dark cave
598 // <nmatsakis> pcwalton: the enter family of functions adjust the set of
599 // patterns as needed
600 // <nmatsakis> yeah, at some point I kind of achieved some level of
602 // <nmatsakis> anyhow, they adjust the patterns given that something of that
603 // kind has been found
604 // <nmatsakis> pcwalton: ok, right, so enter_XXX() adjusts the patterns, as I
606 // <nmatsakis> enter_match() kind of embodies the generic code
607 // <nmatsakis> it is provided with a function that tests each pattern to see
608 // if it might possibly apply and so forth
609 // <nmatsakis> so, if you have a pattern like {a: _, b: _, _} and one like _
610 // <nmatsakis> then _ would be expanded to (_, _)
611 // <nmatsakis> one spot for each of the sub-patterns
612 // <nmatsakis> enter_opt() is one of the more complex; it covers the fallible
614 // <nmatsakis> enter_rec_or_struct() or enter_tuple() are simpler, since they
615 // are infallible patterns
616 // <nmatsakis> so all patterns must either be records (resp. tuples) or
619 fn enter_opt<'a, 'b>(
621 m: &'a [Match<'a, 'b>],
626 -> Vec<Match<'a, 'b>> {
627 debug!("enter_opt(bcx={}, m={}, opt={:?}, col={}, val={})",
632 bcx.val_to_str(val));
633 let _indenter = indenter();
636 let dummy = @ast::Pat {id: 0, node: ast::PatWild, span: DUMMY_SP};
638 // By the virtue of fact that we are in `trans` already, `enter_opt` is able
639 // to prune sub-match tree aggressively based on exact equality. But when it
640 // comes to literal or range, that strategy may lead to wrong result if there
641 // are guard function or multiple patterns inside tuple; in that case, pruning
642 // based on the overlap of patterns is required.
644 // Ideally, when constructing the sub-match tree for certain arm, only those
645 // arms beneath it matter. But that isn't how algorithm works right now and
646 // all other arms are taken into consideration when computing `guarded` below.
647 // That is ok since each round of `compile_submatch` guarantees to trim one
648 // "column" of arm patterns and the algorithm will converge.
649 let guarded = m.iter().any(|x| x.data.arm.guard.is_some());
650 let multi_pats = m.len() > 0 && m[0].pats.len() > 1;
651 enter_match(bcx, &tcx.def_map, m, col, val, |p| {
652 let answer = match p.node {
654 ast::PatIdent(_, _, None) if pat_is_const(&tcx.def_map, p) => {
655 let const_def = tcx.def_map.borrow().get_copy(&p.id);
656 let const_def_id = ast_util::def_id_of_def(const_def);
657 let konst = lit(ConstLit(const_def_id));
658 match guarded || multi_pats {
659 false if opt_eq(tcx, &konst, opt) => Some(Vec::new()),
660 true if opt_overlap(tcx, &konst, opt) => Some(Vec::new()),
664 ast::PatEnum(_, ref subpats) => {
665 if opt_eq(tcx, &variant_opt(bcx, p.id), opt) {
666 // FIXME: Must we clone?
668 None => Some(Vec::from_elem(variant_size, dummy)),
669 Some(ref subpats) => {
670 Some((*subpats).iter().map(|x| *x).collect())
677 ast::PatIdent(_, _, None)
678 if pat_is_variant_or_struct(&tcx.def_map, p) => {
679 if opt_eq(tcx, &variant_opt(bcx, p.id), opt) {
686 let lit_expr = lit(ExprLit(l));
687 match guarded || multi_pats {
688 false if opt_eq(tcx, &lit_expr, opt) => Some(Vec::new()),
689 true if opt_overlap(tcx, &lit_expr, opt) => Some(Vec::new()),
693 ast::PatRange(l1, l2) => {
694 let rng = range(l1, l2);
695 match guarded || multi_pats {
696 false if opt_eq(tcx, &rng, opt) => Some(Vec::new()),
697 true if opt_overlap(tcx, &rng, opt) => Some(Vec::new()),
701 ast::PatStruct(_, ref field_pats, _) => {
702 if opt_eq(tcx, &variant_opt(bcx, p.id), opt) {
703 // Look up the struct variant ID.
705 match tcx.def_map.borrow().get_copy(&p.id) {
706 ast::DefVariant(_, found_struct_id, _) => {
707 struct_id = found_struct_id;
710 tcx.sess.span_bug(p.span, "expected enum variant def");
714 // Reorder the patterns into the same order they were
715 // specified in the struct definition. Also fill in
716 // unspecified fields with dummy.
717 let mut reordered_patterns = Vec::new();
718 let r = ty::lookup_struct_fields(tcx, struct_id);
719 for field in r.iter() {
720 match field_pats.iter().find(|p| p.ident.name
722 None => reordered_patterns.push(dummy),
723 Some(fp) => reordered_patterns.push(fp.pat)
726 Some(reordered_patterns)
731 ast::PatVec(ref before, slice, ref after) => {
732 let (lo, hi) = match *opt {
733 vec_len(_, _, (lo, hi)) => (lo, hi),
734 _ => tcx.sess.span_bug(p.span,
735 "vec pattern but not vec opt")
739 Some(slice) if i >= lo && i <= hi => {
740 let n = before.len() + after.len();
741 let this_opt = vec_len(n, vec_len_ge(before.len()),
743 if opt_eq(tcx, &this_opt, opt) {
744 let mut new_before = Vec::new();
745 for pat in before.iter() {
746 new_before.push(*pat);
748 new_before.push(slice);
749 for pat in after.iter() {
750 new_before.push(*pat);
757 None if i >= lo && i <= hi => {
758 let n = before.len();
759 if opt_eq(tcx, &vec_len(n, vec_len_eq, (lo,hi)), opt) {
760 let mut new_before = Vec::new();
761 for pat in before.iter() {
762 new_before.push(*pat);
773 assert_is_binding_or_wild(bcx, p);
774 // In most cases, a binding/wildcard match be
775 // considered to match against any Opt. However, when
776 // doing vector pattern matching, submatches are
777 // considered even if the eventual match might be from
778 // a different submatch. Thus, when a submatch fails
779 // when doing a vector match, we proceed to the next
780 // submatch. Thus, including a default match would
781 // cause the default match to fire spuriously.
784 _ => Some(Vec::from_elem(variant_size, dummy))
793 fn enter_rec_or_struct<'a, 'b>(
796 m: &'a [Match<'a, 'b>],
798 fields: &[ast::Ident],
800 -> Vec<Match<'a, 'b>> {
801 debug!("enter_rec_or_struct(bcx={}, m={}, col={}, val={})",
805 bcx.val_to_str(val));
806 let _indenter = indenter();
808 let dummy = @ast::Pat {id: 0, node: ast::PatWild, span: DUMMY_SP};
809 enter_match(bcx, dm, m, col, val, |p| {
811 ast::PatStruct(_, ref fpats, _) => {
812 let mut pats = Vec::new();
813 for fname in fields.iter() {
814 match fpats.iter().find(|p| p.ident.name == fname.name) {
815 None => pats.push(dummy),
816 Some(pat) => pats.push(pat.pat)
822 assert_is_binding_or_wild(bcx, p);
823 Some(Vec::from_elem(fields.len(), dummy))
829 fn enter_tup<'a, 'b>(
832 m: &'a [Match<'a, 'b>],
836 -> Vec<Match<'a, 'b>> {
837 debug!("enter_tup(bcx={}, m={}, col={}, val={})",
841 bcx.val_to_str(val));
842 let _indenter = indenter();
844 let dummy = @ast::Pat {id: 0, node: ast::PatWild, span: DUMMY_SP};
845 enter_match(bcx, dm, m, col, val, |p| {
847 ast::PatTup(ref elts) => {
848 let mut new_elts = Vec::new();
849 for elt in elts.iter() {
850 new_elts.push((*elt).clone())
855 assert_is_binding_or_wild(bcx, p);
856 Some(Vec::from_elem(n_elts, dummy))
862 fn enter_tuple_struct<'a, 'b>(
865 m: &'a [Match<'a, 'b>],
869 -> Vec<Match<'a, 'b>> {
870 debug!("enter_tuple_struct(bcx={}, m={}, col={}, val={})",
874 bcx.val_to_str(val));
875 let _indenter = indenter();
877 let dummy = @ast::Pat {id: 0, node: ast::PatWild, span: DUMMY_SP};
878 enter_match(bcx, dm, m, col, val, |p| {
880 ast::PatEnum(_, Some(ref elts)) => {
881 Some(elts.iter().map(|x| (*x)).collect())
884 assert_is_binding_or_wild(bcx, p);
885 Some(Vec::from_elem(n_elts, dummy))
891 fn enter_uniq<'a, 'b>(
894 m: &'a [Match<'a, 'b>],
897 -> Vec<Match<'a, 'b>> {
898 debug!("enter_uniq(bcx={}, m={}, col={}, val={})",
902 bcx.val_to_str(val));
903 let _indenter = indenter();
905 let dummy = @ast::Pat {id: 0, node: ast::PatWild, span: DUMMY_SP};
906 enter_match(bcx, dm, m, col, val, |p| {
908 ast::PatUniq(sub) => {
912 assert_is_binding_or_wild(bcx, p);
919 fn enter_region<'a, 'b>(
922 m: &'a [Match<'a, 'b>],
925 -> Vec<Match<'a, 'b>> {
926 debug!("enter_region(bcx={}, m={}, col={}, val={})",
930 bcx.val_to_str(val));
931 let _indenter = indenter();
933 let dummy = @ast::Pat { id: 0, node: ast::PatWild, span: DUMMY_SP };
934 enter_match(bcx, dm, m, col, val, |p| {
936 ast::PatRegion(sub) => {
940 assert_is_binding_or_wild(bcx, p);
947 // Returns the options in one column of matches. An option is something that
948 // needs to be conditionally matched at runtime; for example, the discriminant
949 // on a set of enum variants or a literal.
950 fn get_options(bcx: &Block, m: &[Match], col: uint) -> Vec<Opt> {
952 fn add_to_set(tcx: &ty::ctxt, set: &mut Vec<Opt>, val: Opt) {
953 if set.iter().any(|l| opt_eq(tcx, l, &val)) {return;}
956 // Vector comparisons are special in that since the actual
957 // conditions over-match, we need to be careful about them. This
958 // means that in order to properly handle things in order, we need
959 // to not always merge conditions.
960 fn add_veclen_to_set(set: &mut Vec<Opt> , i: uint,
961 len: uint, vlo: VecLenOpt) {
963 // If the last condition in the list matches the one we want
964 // to add, then extend its range. Otherwise, make a new
965 // vec_len with a range just covering the new entry.
966 Some(&vec_len(len2, vlo2, (start, end)))
967 if len == len2 && vlo == vlo2 => {
968 let length = set.len();
969 *set.get_mut(length - 1) =
970 vec_len(len, vlo, (start, end+1))
972 _ => set.push(vec_len(len, vlo, (i, i)))
976 let mut found = Vec::new();
977 for (i, br) in m.iter().enumerate() {
978 let cur = *br.pats.get(col);
981 add_to_set(ccx.tcx(), &mut found, lit(ExprLit(l)));
983 ast::PatIdent(..) => {
984 // This is one of: an enum variant, a unit-like struct, or a
986 let opt_def = ccx.tcx.def_map.borrow().find_copy(&cur.id);
988 Some(ast::DefVariant(..)) => {
989 add_to_set(ccx.tcx(), &mut found,
990 variant_opt(bcx, cur.id));
992 Some(ast::DefStruct(..)) => {
993 add_to_set(ccx.tcx(), &mut found,
994 lit(UnitLikeStructLit(cur.id)));
996 Some(ast::DefStatic(const_did, false)) => {
997 add_to_set(ccx.tcx(), &mut found,
998 lit(ConstLit(const_did)));
1003 ast::PatEnum(..) | ast::PatStruct(..) => {
1004 // This could be one of: a tuple-like enum variant, a
1005 // struct-like enum variant, or a struct.
1006 let opt_def = ccx.tcx.def_map.borrow().find_copy(&cur.id);
1008 Some(ast::DefFn(..)) |
1009 Some(ast::DefVariant(..)) => {
1010 add_to_set(ccx.tcx(), &mut found,
1011 variant_opt(bcx, cur.id));
1013 Some(ast::DefStatic(const_did, false)) => {
1014 add_to_set(ccx.tcx(), &mut found,
1015 lit(ConstLit(const_did)));
1020 ast::PatRange(l1, l2) => {
1021 add_to_set(ccx.tcx(), &mut found, range(l1, l2));
1023 ast::PatVec(ref before, slice, ref after) => {
1024 let (len, vec_opt) = match slice {
1025 None => (before.len(), vec_len_eq),
1026 Some(_) => (before.len() + after.len(),
1027 vec_len_ge(before.len()))
1029 add_veclen_to_set(&mut found, i, len, vec_opt);
1037 struct ExtractedBlock<'a> {
1038 vals: Vec<ValueRef> ,
1042 fn extract_variant_args<'a>(
1047 -> ExtractedBlock<'a> {
1048 let _icx = push_ctxt("match::extract_variant_args");
1049 let args = Vec::from_fn(adt::num_args(repr, disr_val), |i| {
1050 adt::trans_field_ptr(bcx, repr, val, disr_val, i)
1053 ExtractedBlock { vals: args, bcx: bcx }
1056 fn match_datum(bcx: &Block,
1058 pat_id: ast::NodeId)
1061 * Helper for converting from the ValueRef that we pass around in
1062 * the match code, which is always an lvalue, into a Datum. Eventually
1063 * we should just pass around a Datum and be done with it.
1066 let ty = node_id_type(bcx, pat_id);
1067 Datum(val, ty, Lvalue)
1071 fn extract_vec_elems<'a>(
1073 pat_id: ast::NodeId,
1075 slice: Option<uint>,
1078 -> ExtractedBlock<'a> {
1079 let _icx = push_ctxt("match::extract_vec_elems");
1080 let vec_datum = match_datum(bcx, val, pat_id);
1081 let (base, len) = vec_datum.get_vec_base_and_len(bcx);
1082 let vec_ty = node_id_type(bcx, pat_id);
1083 let vt = tvec::vec_types(bcx, ty::sequence_element_type(bcx.tcx(), vec_ty));
1085 let mut elems = Vec::from_fn(elem_count, |i| {
1087 None => GEPi(bcx, base, [i]),
1088 Some(n) if i < n => GEPi(bcx, base, [i]),
1089 Some(n) if i > n => {
1090 InBoundsGEP(bcx, base, [
1092 C_int(bcx.ccx(), (elem_count - i) as int))])
1094 _ => unsafe { llvm::LLVMGetUndef(vt.llunit_ty.to_ref()) }
1097 if slice.is_some() {
1098 let n = slice.unwrap();
1099 let slice_byte_offset = Mul(bcx, vt.llunit_size, C_uint(bcx.ccx(), n));
1100 let slice_begin = tvec::pointer_add_byte(bcx, base, slice_byte_offset);
1101 let slice_len_offset = C_uint(bcx.ccx(), elem_count - 1u);
1102 let slice_len = Sub(bcx, len, slice_len_offset);
1103 let slice_ty = ty::mk_slice(bcx.tcx(),
1105 ty::mt {ty: vt.unit_ty, mutbl: ast::MutImmutable});
1106 let scratch = rvalue_scratch_datum(bcx, slice_ty, "");
1107 Store(bcx, slice_begin,
1108 GEPi(bcx, scratch.val, [0u, abi::slice_elt_base]));
1109 Store(bcx, slice_len, GEPi(bcx, scratch.val, [0u, abi::slice_elt_len]));
1110 *elems.get_mut(n) = scratch.val;
1113 ExtractedBlock { vals: elems, bcx: bcx }
1116 /// Checks every pattern in `m` at `col` column.
1117 /// If there are a struct pattern among them function
1118 /// returns list of all fields that are matched in these patterns.
1119 /// Function returns None if there is no struct pattern.
1120 /// Function doesn't collect fields from struct-like enum variants.
1121 /// Function can return empty list if there is only wildcard struct pattern.
1122 fn collect_record_or_struct_fields<'a>(
1126 -> Option<Vec<ast::Ident> > {
1127 let mut fields: Vec<ast::Ident> = Vec::new();
1128 let mut found = false;
1129 for br in m.iter() {
1130 match br.pats.get(col).node {
1131 ast::PatStruct(_, ref fs, _) => {
1132 match ty::get(node_id_type(bcx, br.pats.get(col).id)).sty {
1133 ty::ty_struct(..) => {
1134 extend(&mut fields, fs.as_slice());
1144 return Some(fields);
1149 fn extend(idents: &mut Vec<ast::Ident> , field_pats: &[ast::FieldPat]) {
1150 for field_pat in field_pats.iter() {
1151 let field_ident = field_pat.ident;
1152 if !idents.iter().any(|x| x.name == field_ident.name) {
1153 idents.push(field_ident);
1159 fn pats_require_rooting(bcx: &Block, m: &[Match], col: uint) -> bool {
1161 let pat_id = br.pats.get(col).id;
1162 let key = root_map_key {id: pat_id, derefs: 0u };
1163 bcx.ccx().maps.root_map.contains_key(&key)
1167 // Macro for deciding whether any of the remaining matches fit a given kind of
1168 // pattern. Note that, because the macro is well-typed, either ALL of the
1169 // matches should fit that sort of pattern or NONE (however, some of the
1170 // matches may be wildcards like _ or identifiers).
1171 macro_rules! any_pat (
1172 ($m:expr, $pattern:pat) => (
1173 ($m).iter().any(|br| {
1174 match br.pats.get(col).node {
1182 fn any_uniq_pat(m: &[Match], col: uint) -> bool {
1183 any_pat!(m, ast::PatUniq(_))
1186 fn any_region_pat(m: &[Match], col: uint) -> bool {
1187 any_pat!(m, ast::PatRegion(_))
1190 fn any_tup_pat(m: &[Match], col: uint) -> bool {
1191 any_pat!(m, ast::PatTup(_))
1194 fn any_tuple_struct_pat(bcx: &Block, m: &[Match], col: uint) -> bool {
1196 let pat = *br.pats.get(col);
1198 ast::PatEnum(_, Some(_)) => {
1199 match bcx.tcx().def_map.borrow().find(&pat.id) {
1200 Some(&ast::DefFn(..)) |
1201 Some(&ast::DefStruct(..)) => true,
1210 struct DynamicFailureHandler<'a> {
1213 msg: InternedString,
1214 finished: Cell<Option<BasicBlockRef>>,
1217 impl<'a> DynamicFailureHandler<'a> {
1218 fn handle_fail(&self) -> BasicBlockRef {
1219 match self.finished.get() {
1220 Some(bb) => return bb,
1224 let fcx = self.bcx.fcx;
1225 let fail_cx = fcx.new_block(false, "case_fallthrough", None);
1226 controlflow::trans_fail(fail_cx, self.sp, self.msg.clone());
1227 self.finished.set(Some(fail_cx.llbb));
1232 /// What to do when the pattern match fails.
1233 enum FailureHandler<'a> {
1235 JumpToBasicBlock(BasicBlockRef),
1236 DynamicFailureHandlerClass(~DynamicFailureHandler<'a>),
1239 impl<'a> FailureHandler<'a> {
1240 fn is_infallible(&self) -> bool {
1247 fn is_fallible(&self) -> bool {
1248 !self.is_infallible()
1251 fn handle_fail(&self) -> BasicBlockRef {
1254 fail!("attempted to fail in infallible failure handler!")
1256 JumpToBasicBlock(basic_block) => basic_block,
1257 DynamicFailureHandlerClass(ref dynamic_failure_handler) => {
1258 dynamic_failure_handler.handle_fail()
1264 fn pick_col(m: &[Match]) -> uint {
1265 fn score(p: &ast::Pat) -> uint {
1267 ast::PatLit(_) | ast::PatEnum(_, _) | ast::PatRange(_, _) => 1u,
1268 ast::PatIdent(_, _, Some(p)) => score(p),
1272 let mut scores = Vec::from_elem(m[0].pats.len(), 0u);
1273 for br in m.iter() {
1274 for (i, p) in br.pats.iter().enumerate() {
1275 *scores.get_mut(i) += score(*p);
1278 let mut max_score = 0u;
1279 let mut best_col = 0u;
1280 for (i, score) in scores.iter().enumerate() {
1283 // Irrefutable columns always go first, they'd only be duplicated in
1285 if score == 0u { return i; }
1286 // If no irrefutable ones are found, we pick the one with the biggest
1287 // branching factor.
1288 if score > max_score { max_score = score; best_col = i; }
1294 pub enum branch_kind { no_branch, single, switch, compare, compare_vec_len, }
1296 // Compiles a comparison between two things.
1298 // NB: This must produce an i1, not a Rust bool (i8).
1299 fn compare_values<'a>(
1305 let _icx = push_ctxt("compare_values");
1306 if ty::type_is_scalar(rhs_t) {
1307 let rs = compare_scalar_types(cx, lhs, rhs, rhs_t, ast::BiEq);
1308 return rslt(rs.bcx, rs.val);
1311 match ty::get(rhs_t).sty {
1312 ty::ty_str(ty::VstoreUniq) => {
1313 let scratch_lhs = alloca(cx, val_ty(lhs), "__lhs");
1314 Store(cx, lhs, scratch_lhs);
1315 let scratch_rhs = alloca(cx, val_ty(rhs), "__rhs");
1316 Store(cx, rhs, scratch_rhs);
1317 let did = langcall(cx, None,
1318 format!("comparison of `{}`", cx.ty_to_str(rhs_t)),
1319 UniqStrEqFnLangItem);
1320 let result = callee::trans_lang_call(cx, did, [scratch_lhs, scratch_rhs], None);
1323 val: bool_to_i1(result.bcx, result.val)
1327 let did = langcall(cx, None,
1328 format!("comparison of `{}`", cx.ty_to_str(rhs_t)),
1330 let result = callee::trans_lang_call(cx, did, [lhs, rhs], None);
1333 val: bool_to_i1(result.bcx, result.val)
1337 cx.sess().bug("only scalars and strings supported in compare_values");
1342 fn store_non_ref_bindings<'a>(
1344 bindings_map: &BindingsMap,
1345 opt_cleanup_scope: Option<cleanup::ScopeId>)
1349 * For each copy/move binding, copy the value from the value being
1350 * matched into its final home. This code executes once one of
1351 * the patterns for a given arm has completely matched. It adds
1352 * cleanups to the `opt_cleanup_scope`, if one is provided.
1357 for (_, &binding_info) in bindings_map.iter() {
1358 match binding_info.trmode {
1359 TrByValue(lldest) => {
1360 let llval = Load(bcx, binding_info.llmatch); // get a T*
1361 let datum = Datum(llval, binding_info.ty, Lvalue);
1362 bcx = datum.store_to(bcx, lldest);
1364 match opt_cleanup_scope {
1367 fcx.schedule_drop_mem(s, lldest, binding_info.ty);
1377 fn insert_lllocals<'a>(bcx: &'a Block<'a>,
1378 bindings_map: &BindingsMap,
1379 cleanup_scope: cleanup::ScopeId)
1382 * For each binding in `data.bindings_map`, adds an appropriate entry into
1383 * the `fcx.lllocals` map, scheduling cleanup in `cleanup_scope`.
1388 for (&ident, &binding_info) in bindings_map.iter() {
1389 let llval = match binding_info.trmode {
1390 // By value bindings: use the stack slot that we
1391 // copied/moved the value into
1392 TrByValue(lldest) => lldest,
1394 // By ref binding: use the ptr into the matched value
1395 TrByRef => binding_info.llmatch
1398 let datum = Datum(llval, binding_info.ty, Lvalue);
1399 fcx.schedule_drop_mem(cleanup_scope, llval, binding_info.ty);
1401 debug!("binding {:?} to {}",
1403 bcx.val_to_str(llval));
1404 bcx.fcx.lllocals.borrow_mut().insert(binding_info.id, datum);
1406 if bcx.sess().opts.debuginfo == FullDebugInfo {
1407 debuginfo::create_match_binding_metadata(bcx,
1417 fn compile_guard<'a, 'b>(
1419 guard_expr: &ast::Expr,
1421 m: &'a [Match<'a, 'b>],
1423 chk: &FailureHandler)
1425 debug!("compile_guard(bcx={}, guard_expr={}, m={}, vals={})",
1427 bcx.expr_to_str(guard_expr),
1429 vec_map_to_str(vals, |v| bcx.val_to_str(*v)));
1430 let _indenter = indenter();
1432 // Lest the guard itself should fail, introduce a temporary cleanup
1433 // scope for any non-ref bindings we create.
1434 let temp_scope = bcx.fcx.push_custom_cleanup_scope();
1437 bcx = store_non_ref_bindings(bcx, &data.bindings_map,
1438 Some(cleanup::CustomScope(temp_scope)));
1439 bcx = insert_lllocals(bcx, &data.bindings_map,
1440 cleanup::CustomScope(temp_scope));
1442 let val = unpack_datum!(bcx, expr::trans(bcx, guard_expr));
1443 let val = val.to_llbool(bcx);
1445 // Cancel cleanups now that the guard successfully executed. If
1446 // the guard was false, we will drop the values explicitly
1447 // below. Otherwise, we'll add lvalue cleanups at the end.
1448 bcx.fcx.pop_custom_cleanup_scope(temp_scope);
1450 return with_cond(bcx, Not(bcx, val), |bcx| {
1451 // Guard does not match: free the values we copied,
1452 // and remove all bindings from the lllocals table
1453 let bcx = drop_bindings(bcx, data);
1454 compile_submatch(bcx, m, vals, chk);
1458 fn drop_bindings<'a>(bcx: &'a Block<'a>, data: &ArmData)
1461 for (_, &binding_info) in data.bindings_map.iter() {
1462 match binding_info.trmode {
1463 TrByValue(llval) => {
1464 bcx = glue::drop_ty(bcx, llval, binding_info.ty);
1468 bcx.fcx.lllocals.borrow_mut().remove(&binding_info.id);
1474 fn compile_submatch<'a, 'b>(
1476 m: &'a [Match<'a, 'b>],
1478 chk: &FailureHandler) {
1479 debug!("compile_submatch(bcx={}, m={}, vals={})",
1482 vec_map_to_str(vals, |v| bcx.val_to_str(*v)));
1483 let _indenter = indenter();
1486 For an empty match, a fall-through case must exist
1488 assert!((m.len() > 0u || chk.is_fallible()));
1489 let _icx = push_ctxt("match::compile_submatch");
1492 Br(bcx, chk.handle_fail());
1495 if m[0].pats.len() == 0u {
1496 let data = &m[0].data;
1497 for &(ref ident, ref value_ptr) in m[0].bound_ptrs.iter() {
1498 let llmatch = data.bindings_map.get(ident).llmatch;
1499 Store(bcx, *value_ptr, llmatch);
1501 match data.arm.guard {
1502 Some(guard_expr) => {
1503 bcx = compile_guard(bcx,
1506 m.slice(1, m.len()),
1512 Br(bcx, data.bodycx.llbb);
1516 let col = pick_col(m);
1517 let val = vals[col];
1519 if has_nested_bindings(m, col) {
1520 let expanded = expand_nested_bindings(bcx, m, col, val);
1521 compile_submatch_continue(bcx,
1522 expanded.as_slice(),
1528 compile_submatch_continue(bcx, m, vals, chk, col, val)
1532 fn compile_submatch_continue<'a, 'b>(
1533 mut bcx: &'b Block<'b>,
1534 m: &'a [Match<'a, 'b>],
1536 chk: &FailureHandler,
1540 let tcx = bcx.tcx();
1541 let dm = &tcx.def_map;
1543 let vals_left = Vec::from_slice(vals.slice(0u, col)).append(vals.slice(col + 1u, vals.len()));
1544 let ccx = bcx.fcx.ccx;
1546 for br in m.iter() {
1547 // Find a real id (we're adding placeholder wildcard patterns, but
1548 // each column is guaranteed to have at least one real pattern)
1550 pat_id = br.pats.get(col).id;
1554 // If we are not matching against an `@T`, we should not be
1555 // required to root any values.
1556 assert!(!pats_require_rooting(bcx, m, col));
1558 match collect_record_or_struct_fields(bcx, m, col) {
1559 Some(ref rec_fields) => {
1560 let pat_ty = node_id_type(bcx, pat_id);
1561 let pat_repr = adt::represent_type(bcx.ccx(), pat_ty);
1562 expr::with_field_tys(tcx, pat_ty, Some(pat_id), |discr, field_tys| {
1563 let rec_vals = rec_fields.iter().map(|field_name| {
1564 let ix = ty::field_idx_strict(tcx, field_name.name, field_tys);
1565 adt::trans_field_ptr(bcx, &*pat_repr, val, discr, ix)
1566 }).collect::<Vec<_>>();
1569 enter_rec_or_struct(bcx,
1573 rec_fields.as_slice(),
1575 rec_vals.append(vals_left.as_slice()).as_slice(),
1583 if any_tup_pat(m, col) {
1584 let tup_ty = node_id_type(bcx, pat_id);
1585 let tup_repr = adt::represent_type(bcx.ccx(), tup_ty);
1586 let n_tup_elts = match ty::get(tup_ty).sty {
1587 ty::ty_tup(ref elts) => elts.len(),
1588 _ => ccx.sess().bug("non-tuple type in tuple pattern")
1590 let tup_vals = Vec::from_fn(n_tup_elts, |i| {
1591 adt::trans_field_ptr(bcx, &*tup_repr, val, 0, i)
1593 compile_submatch(bcx,
1599 n_tup_elts).as_slice(),
1600 tup_vals.append(vals_left.as_slice()).as_slice(),
1605 if any_tuple_struct_pat(bcx, m, col) {
1606 let struct_ty = node_id_type(bcx, pat_id);
1607 let struct_element_count;
1608 match ty::get(struct_ty).sty {
1609 ty::ty_struct(struct_id, _) => {
1610 struct_element_count =
1611 ty::lookup_struct_fields(tcx, struct_id).len();
1614 ccx.sess().bug("non-struct type in tuple struct pattern");
1618 let struct_repr = adt::represent_type(bcx.ccx(), struct_ty);
1619 let llstructvals = Vec::from_fn(struct_element_count, |i| {
1620 adt::trans_field_ptr(bcx, &*struct_repr, val, 0, i)
1622 compile_submatch(bcx,
1623 enter_tuple_struct(bcx, dm, m, col, val,
1624 struct_element_count).as_slice(),
1625 llstructvals.append(vals_left.as_slice()).as_slice(),
1630 if any_uniq_pat(m, col) {
1631 let llbox = Load(bcx, val);
1632 compile_submatch(bcx,
1633 enter_uniq(bcx, dm, m, col, val).as_slice(),
1634 (vec!(llbox)).append(vals_left.as_slice()).as_slice(),
1639 if any_region_pat(m, col) {
1640 let loaded_val = Load(bcx, val);
1641 compile_submatch(bcx,
1642 enter_region(bcx, dm, m, col, val).as_slice(),
1643 (vec!(loaded_val)).append(vals_left.as_slice()).as_slice(),
1648 // Decide what kind of branch we need
1649 let opts = get_options(bcx, m, col);
1650 debug!("options={:?}", opts);
1651 let mut kind = no_branch;
1652 let mut test_val = val;
1653 debug!("test_val={}", bcx.val_to_str(test_val));
1654 if opts.len() > 0u {
1655 match *opts.get(0) {
1656 var(_, ref repr) => {
1657 let (the_kind, val_opt) = adt::trans_switch(bcx, &**repr, val);
1659 for &tval in val_opt.iter() { test_val = tval; }
1662 let pty = node_id_type(bcx, pat_id);
1663 test_val = load_if_immediate(bcx, val, pty);
1664 kind = if ty::type_is_integral(pty) { switch }
1668 test_val = Load(bcx, val);
1672 let vec_ty = node_id_type(bcx, pat_id);
1673 let (_, len) = tvec::get_base_and_len(bcx, val, vec_ty);
1675 kind = compare_vec_len;
1679 for o in opts.iter() {
1681 range(_, _) => { kind = compare; break }
1685 let else_cx = match kind {
1686 no_branch | single => bcx,
1687 _ => bcx.fcx.new_temp_block("match_else")
1689 let sw = if kind == switch {
1690 Switch(bcx, test_val, else_cx.llbb, opts.len())
1692 C_int(ccx, 0) // Placeholder for when not using a switch
1695 let defaults = enter_default(else_cx, dm, m, col, val, chk);
1696 let exhaustive = chk.is_infallible() && defaults.len() == 0u;
1697 let len = opts.len();
1699 // Compile subtrees for each option
1700 for (i, opt) in opts.iter().enumerate() {
1701 // In some cases in vector pattern matching, we need to override
1702 // the failure case so that instead of failing, it proceeds to
1703 // try more matching. branch_chk, then, is the proper failure case
1704 // for the current conditional branch.
1705 let mut branch_chk = None;
1706 let mut opt_cx = else_cx;
1707 if !exhaustive || i+1 < len {
1708 opt_cx = bcx.fcx.new_temp_block("match_case");
1710 single => Br(bcx, opt_cx.llbb),
1712 match trans_opt(bcx, opt) {
1713 single_result(r) => {
1715 llvm::LLVMAddCase(sw, r.val, opt_cx.llbb);
1721 "in compile_submatch, expected \
1722 trans_opt to return a single_result")
1727 let t = node_id_type(bcx, pat_id);
1728 let Result {bcx: after_cx, val: matches} = {
1729 match trans_opt(bcx, opt) {
1730 single_result(Result {bcx, val}) => {
1731 compare_values(bcx, test_val, val, t)
1733 lower_bound(Result {bcx, val}) => {
1734 compare_scalar_types(
1738 range_result(Result {val: vbegin, ..},
1739 Result {bcx, val: vend}) => {
1740 let Result {bcx, val: llge} =
1741 compare_scalar_types(
1743 vbegin, t, ast::BiGe);
1744 let Result {bcx, val: llle} =
1745 compare_scalar_types(
1746 bcx, test_val, vend,
1748 rslt(bcx, And(bcx, llge, llle))
1752 bcx = fcx.new_temp_block("compare_next");
1753 CondBr(after_cx, matches, opt_cx.llbb, bcx.llbb);
1755 compare_vec_len => {
1756 let Result {bcx: after_cx, val: matches} = {
1757 match trans_opt(bcx, opt) {
1759 Result {bcx, val}) => {
1760 let value = compare_scalar_values(
1762 signed_int, ast::BiEq);
1766 Result {bcx, val: val}) => {
1767 let value = compare_scalar_values(
1769 signed_int, ast::BiGe);
1773 Result {val: vbegin, ..},
1774 Result {bcx, val: vend}) => {
1776 compare_scalar_values(
1778 vbegin, signed_int, ast::BiGe);
1780 compare_scalar_values(
1781 bcx, test_val, vend,
1782 signed_int, ast::BiLe);
1783 rslt(bcx, And(bcx, llge, llle))
1787 bcx = fcx.new_temp_block("compare_vec_len_next");
1789 // If none of these subcases match, move on to the
1791 branch_chk = Some(JumpToBasicBlock(bcx.llbb));
1792 CondBr(after_cx, matches, opt_cx.llbb, bcx.llbb);
1796 } else if kind == compare || kind == compare_vec_len {
1797 Br(bcx, else_cx.llbb);
1801 let mut unpacked = Vec::new();
1803 var(disr_val, ref repr) => {
1804 let ExtractedBlock {vals: argvals, bcx: new_bcx} =
1805 extract_variant_args(opt_cx, &**repr, disr_val, val);
1806 size = argvals.len();
1810 vec_len(n, vt, _) => {
1811 let (n, slice) = match vt {
1812 vec_len_ge(i) => (n + 1u, Some(i)),
1813 vec_len_eq => (n, None)
1815 let args = extract_vec_elems(opt_cx, pat_id, n,
1816 slice, val, test_val);
1817 size = args.vals.len();
1818 unpacked = args.vals.clone();
1821 lit(_) | range(_, _) => ()
1823 let opt_ms = enter_opt(opt_cx, m, opt, col, size, val);
1824 let opt_vals = unpacked.append(vals_left.as_slice());
1828 compile_submatch(opt_cx,
1830 opt_vals.as_slice(),
1833 Some(branch_chk) => {
1834 compile_submatch(opt_cx,
1836 opt_vals.as_slice(),
1842 // Compile the fall-through case, if any
1844 if kind == compare || kind == compare_vec_len {
1845 Br(bcx, else_cx.llbb);
1848 compile_submatch(else_cx,
1849 defaults.as_slice(),
1850 vals_left.as_slice(),
1856 pub fn trans_match<'a>(
1858 match_expr: &ast::Expr,
1859 discr_expr: &ast::Expr,
1863 let _icx = push_ctxt("match::trans_match");
1864 trans_match_inner(bcx, match_expr.id, discr_expr, arms, dest)
1867 fn create_bindings_map(bcx: &Block, pat: @ast::Pat) -> BindingsMap {
1868 // Create the bindings map, which is a mapping from each binding name
1869 // to an alloca() that will be the value for that local variable.
1870 // Note that we use the names because each binding will have many ids
1871 // from the various alternatives.
1872 let ccx = bcx.ccx();
1873 let tcx = bcx.tcx();
1874 let mut bindings_map = HashMap::new();
1875 pat_bindings(&tcx.def_map, pat, |bm, p_id, span, path| {
1876 let ident = path_to_ident(path);
1877 let variable_ty = node_id_type(bcx, p_id);
1878 let llvariable_ty = type_of::type_of(ccx, variable_ty);
1883 ast::BindByValue(_) => {
1884 // in this case, the final type of the variable will be T,
1885 // but during matching we need to store a *T as explained
1887 llmatch = alloca(bcx, llvariable_ty.ptr_to(), "__llmatch");
1888 trmode = TrByValue(alloca(bcx, llvariable_ty,
1891 ast::BindByRef(_) => {
1892 llmatch = alloca(bcx, llvariable_ty, bcx.ident(ident));
1896 bindings_map.insert(ident, BindingInfo {
1904 return bindings_map;
1907 fn trans_match_inner<'a>(scope_cx: &'a Block<'a>,
1908 match_id: ast::NodeId,
1909 discr_expr: &ast::Expr,
1911 dest: Dest) -> &'a Block<'a> {
1912 let _icx = push_ctxt("match::trans_match_inner");
1913 let fcx = scope_cx.fcx;
1914 let mut bcx = scope_cx;
1915 let tcx = bcx.tcx();
1917 let discr_datum = unpack_datum!(bcx, expr::trans_to_lvalue(bcx, discr_expr,
1919 if bcx.unreachable.get() {
1923 let t = node_id_type(bcx, discr_expr.id);
1925 if ty::type_is_empty(tcx, t) {
1926 // Special case for empty types
1927 let fail_cx = Cell::new(None);
1928 let fail_handler = ~DynamicFailureHandler {
1930 sp: discr_expr.span,
1931 msg: InternedString::new("scrutinizing value that can't \
1935 DynamicFailureHandlerClass(fail_handler)
1941 let arm_datas: Vec<ArmData> = arms.iter().map(|arm| ArmData {
1942 bodycx: fcx.new_id_block("case_body", arm.body.id),
1944 bindings_map: create_bindings_map(bcx, *arm.pats.get(0))
1947 let mut matches = Vec::new();
1948 for arm_data in arm_datas.iter() {
1949 matches.extend(arm_data.arm.pats.iter().map(|p| Match {
1952 bound_ptrs: Vec::new(),
1956 compile_submatch(bcx, matches.as_slice(), [discr_datum.val], &chk);
1958 let mut arm_cxs = Vec::new();
1959 for arm_data in arm_datas.iter() {
1960 let mut bcx = arm_data.bodycx;
1962 // If this arm has a guard, then the various by-value bindings have
1963 // already been copied into their homes. If not, we do it here. This
1964 // is just to reduce code space. See extensive comment at the start
1965 // of the file for more details.
1966 if arm_data.arm.guard.is_none() {
1967 bcx = store_non_ref_bindings(bcx, &arm_data.bindings_map, None);
1970 // insert bindings into the lllocals map and add cleanups
1971 let cleanup_scope = fcx.push_custom_cleanup_scope();
1972 bcx = insert_lllocals(bcx, &arm_data.bindings_map,
1973 cleanup::CustomScope(cleanup_scope));
1974 bcx = expr::trans_into(bcx, arm_data.arm.body, dest);
1975 bcx = fcx.pop_and_trans_custom_cleanup_scope(bcx, cleanup_scope);
1979 bcx = scope_cx.fcx.join_blocks(match_id, arm_cxs.as_slice());
1983 enum IrrefutablePatternBindingMode {
1984 // Stores the association between node ID and LLVM value in `lllocals`.
1986 // Stores the association between node ID and LLVM value in `llargs`.
1990 pub fn store_local<'a>(bcx: &'a Block<'a>,
1994 * Generates code for a local variable declaration like
1995 * `let <pat>;` or `let <pat> = <opt_init_expr>`.
1997 let _icx = push_ctxt("match::store_local");
1999 let tcx = bcx.tcx();
2000 let pat = local.pat;
2001 let opt_init_expr = local.init;
2003 return match opt_init_expr {
2004 Some(init_expr) => {
2005 // Optimize the "let x = expr" case. This just writes
2006 // the result of evaluating `expr` directly into the alloca
2007 // for `x`. Often the general path results in similar or the
2008 // same code post-optimization, but not always. In particular,
2009 // in unsafe code, you can have expressions like
2011 // let x = intrinsics::uninit();
2013 // In such cases, the more general path is unsafe, because
2014 // it assumes it is matching against a valid value.
2015 match simple_identifier(pat) {
2017 let var_scope = cleanup::var_scope(tcx, local.id);
2018 return mk_binding_alloca(
2019 bcx, pat.id, path, BindLocal, var_scope, (),
2020 |(), bcx, v, _| expr::trans_into(bcx, init_expr,
2029 unpack_datum!(bcx, expr::trans_to_lvalue(bcx, init_expr, "let"));
2030 if ty::type_is_bot(expr_ty(bcx, init_expr)) {
2031 create_dummy_locals(bcx, pat)
2033 if bcx.sess().asm_comments() {
2034 add_comment(bcx, "creating zeroable ref llval");
2036 let var_scope = cleanup::var_scope(tcx, local.id);
2037 bind_irrefutable_pat(bcx, pat, init_datum.val, BindLocal, var_scope)
2041 create_dummy_locals(bcx, pat)
2045 fn create_dummy_locals<'a>(mut bcx: &'a Block<'a>,
2048 // create dummy memory for the variables if we have no
2049 // value to store into them immediately
2050 let tcx = bcx.tcx();
2051 pat_bindings(&tcx.def_map, pat, |_, p_id, _, path| {
2052 let scope = cleanup::var_scope(tcx, p_id);
2053 bcx = mk_binding_alloca(
2054 bcx, p_id, path, BindLocal, scope, (),
2055 |(), bcx, llval, ty| { zero_mem(bcx, llval, ty); bcx });
2061 pub fn store_arg<'a>(mut bcx: &'a Block<'a>,
2064 arg_scope: cleanup::ScopeId)
2067 * Generates code for argument patterns like `fn foo(<pat>: T)`.
2068 * Creates entries in the `llargs` map for each of the bindings
2073 * - `pat` is the argument pattern
2074 * - `llval` is a pointer to the argument value (in other words,
2075 * if the argument type is `T`, then `llval` is a `T*`). In some
2076 * cases, this code may zero out the memory `llval` points at.
2079 let _icx = push_ctxt("match::store_arg");
2081 match simple_identifier(pat) {
2083 // Generate nicer LLVM for the common case of fn a pattern
2085 let arg_ty = node_id_type(bcx, pat.id);
2086 if type_of::arg_is_indirect(bcx.ccx(), arg_ty)
2087 && bcx.sess().opts.debuginfo != FullDebugInfo {
2088 // Don't copy an indirect argument to an alloca, the caller
2089 // already put it in a temporary alloca and gave it up, unless
2090 // we emit extra-debug-info, which requires local allocas :(.
2091 let arg_val = arg.add_clean(bcx.fcx, arg_scope);
2092 bcx.fcx.llargs.borrow_mut()
2093 .insert(pat.id, Datum(arg_val, arg_ty, Lvalue));
2097 bcx, pat.id, path, BindArgument, arg_scope, arg,
2098 |arg, bcx, llval, _| arg.store_to(bcx, llval))
2103 // General path. Copy out the values that are used in the
2105 let arg = unpack_datum!(
2106 bcx, arg.to_lvalue_datum_in_scope(bcx, "__arg", arg_scope));
2107 bind_irrefutable_pat(bcx, pat, arg.val,
2108 BindArgument, arg_scope)
2113 fn mk_binding_alloca<'a,A>(bcx: &'a Block<'a>,
2116 binding_mode: IrrefutablePatternBindingMode,
2117 cleanup_scope: cleanup::ScopeId,
2119 populate: |A, &'a Block<'a>, ValueRef, ty::t| -> &'a Block<'a>)
2121 let var_ty = node_id_type(bcx, p_id);
2122 let ident = ast_util::path_to_ident(path);
2124 // Allocate memory on stack for the binding.
2125 let llval = alloc_ty(bcx, var_ty, bcx.ident(ident));
2127 // Subtle: be sure that we *populate* the memory *before*
2128 // we schedule the cleanup.
2129 let bcx = populate(arg, bcx, llval, var_ty);
2130 bcx.fcx.schedule_drop_mem(cleanup_scope, llval, var_ty);
2132 // Now that memory is initialized and has cleanup scheduled,
2133 // create the datum and insert into the local variable map.
2134 let datum = Datum(llval, var_ty, Lvalue);
2135 let mut llmap = match binding_mode {
2136 BindLocal => bcx.fcx.lllocals.borrow_mut(),
2137 BindArgument => bcx.fcx.llargs.borrow_mut()
2139 llmap.insert(p_id, datum);
2143 fn bind_irrefutable_pat<'a>(
2147 binding_mode: IrrefutablePatternBindingMode,
2148 cleanup_scope: cleanup::ScopeId)
2151 * A simple version of the pattern matching code that only handles
2152 * irrefutable patterns. This is used in let/argument patterns,
2153 * not in match statements. Unifying this code with the code above
2154 * sounds nice, but in practice it produces very inefficient code,
2155 * since the match code is so much more general. In most cases,
2156 * LLVM is able to optimize the code, but it causes longer compile
2157 * times and makes the generated code nigh impossible to read.
2160 * - bcx: starting basic block context
2161 * - pat: the irrefutable pattern being matched.
2162 * - val: the value being matched -- must be an lvalue (by ref, with cleanup)
2163 * - binding_mode: is this for an argument or a local variable?
2166 debug!("bind_irrefutable_pat(bcx={}, pat={}, binding_mode={:?})",
2168 pat.repr(bcx.tcx()),
2171 if bcx.sess().asm_comments() {
2172 add_comment(bcx, format!("bind_irrefutable_pat(pat={})",
2173 pat.repr(bcx.tcx())));
2176 let _indenter = indenter();
2178 let _icx = push_ctxt("match::bind_irrefutable_pat");
2180 let tcx = bcx.tcx();
2181 let ccx = bcx.ccx();
2183 ast::PatIdent(pat_binding_mode, ref path, inner) => {
2184 if pat_is_binding(&tcx.def_map, pat) {
2185 // Allocate the stack slot where the value of this
2186 // binding will live and place it into the appropriate
2188 bcx = mk_binding_alloca(
2189 bcx, pat.id, path, binding_mode, cleanup_scope, (),
2190 |(), bcx, llval, ty| {
2191 match pat_binding_mode {
2192 ast::BindByValue(_) => {
2193 // By value binding: move the value that `val`
2194 // points at into the binding's stack slot.
2195 let d = Datum(val, ty, Lvalue);
2196 d.store_to(bcx, llval)
2199 ast::BindByRef(_) => {
2200 // By ref binding: the value of the variable
2201 // is the pointer `val` itself.
2202 Store(bcx, val, llval);
2209 for &inner_pat in inner.iter() {
2210 bcx = bind_irrefutable_pat(bcx, inner_pat, val,
2211 binding_mode, cleanup_scope);
2214 ast::PatEnum(_, ref sub_pats) => {
2215 let opt_def = bcx.tcx().def_map.borrow().find_copy(&pat.id);
2217 Some(ast::DefVariant(enum_id, var_id, _)) => {
2218 let repr = adt::represent_node(bcx, pat.id);
2219 let vinfo = ty::enum_variant_with_id(ccx.tcx(),
2222 let args = extract_variant_args(bcx,
2226 for sub_pat in sub_pats.iter() {
2227 for (i, argval) in args.vals.iter().enumerate() {
2228 bcx = bind_irrefutable_pat(bcx, *sub_pat.get(i),
2229 *argval, binding_mode,
2234 Some(ast::DefFn(..)) |
2235 Some(ast::DefStruct(..)) => {
2238 // This is a unit-like struct. Nothing to do here.
2240 Some(ref elems) => {
2241 // This is the tuple struct case.
2242 let repr = adt::represent_node(bcx, pat.id);
2243 for (i, elem) in elems.iter().enumerate() {
2244 let fldptr = adt::trans_field_ptr(bcx, &*repr,
2246 bcx = bind_irrefutable_pat(bcx, *elem,
2247 fldptr, binding_mode,
2253 Some(ast::DefStatic(_, false)) => {
2256 // Nothing to do here.
2260 ast::PatStruct(_, ref fields, _) => {
2261 let tcx = bcx.tcx();
2262 let pat_ty = node_id_type(bcx, pat.id);
2263 let pat_repr = adt::represent_type(bcx.ccx(), pat_ty);
2264 expr::with_field_tys(tcx, pat_ty, Some(pat.id), |discr, field_tys| {
2265 for f in fields.iter() {
2266 let ix = ty::field_idx_strict(tcx, f.ident.name, field_tys);
2267 let fldptr = adt::trans_field_ptr(bcx, &*pat_repr, val,
2269 bcx = bind_irrefutable_pat(bcx, f.pat, fldptr,
2270 binding_mode, cleanup_scope);
2274 ast::PatTup(ref elems) => {
2275 let repr = adt::represent_node(bcx, pat.id);
2276 for (i, elem) in elems.iter().enumerate() {
2277 let fldptr = adt::trans_field_ptr(bcx, &*repr, val, 0, i);
2278 bcx = bind_irrefutable_pat(bcx, *elem, fldptr,
2279 binding_mode, cleanup_scope);
2282 ast::PatUniq(inner) => {
2283 let llbox = Load(bcx, val);
2284 bcx = bind_irrefutable_pat(bcx, inner, llbox, binding_mode, cleanup_scope);
2286 ast::PatRegion(inner) => {
2287 let loaded_val = Load(bcx, val);
2288 bcx = bind_irrefutable_pat(bcx, inner, loaded_val, binding_mode, cleanup_scope);
2290 ast::PatVec(..) => {
2291 bcx.sess().span_bug(pat.span,
2292 format!("vector patterns are never irrefutable!"));
2294 ast::PatWild | ast::PatWildMulti | ast::PatLit(_) | ast::PatRange(_, _) => ()