1 // Copyright 2012 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()`
152 use lib::llvm::{llvm, ValueRef, BasicBlockRef};
153 use middle::const_eval;
154 use middle::borrowck::root_map_key;
155 use middle::lang_items::{UniqStrEqFnLangItem, StrEqFnLangItem};
156 use middle::pat_util::*;
157 use middle::resolve::DefMap;
158 use middle::trans::adt;
159 use middle::trans::base::*;
160 use middle::trans::build::*;
161 use middle::trans::callee;
162 use middle::trans::common::*;
163 use middle::trans::consts;
164 use middle::trans::controlflow;
165 use middle::trans::datum;
166 use middle::trans::datum::*;
167 use middle::trans::expr::Dest;
168 use middle::trans::expr;
169 use middle::trans::glue;
170 use middle::trans::tvec;
171 use middle::trans::type_of;
173 use util::common::indenter;
175 use std::hashmap::HashMap;
178 use syntax::ast::ident;
179 use syntax::ast_util::path_to_ident;
180 use syntax::ast_util;
181 use syntax::codemap::{span, dummy_sp};
182 use syntax::print::pprust::pat_to_str;
184 // An option identifying a literal: either a unit-like struct or an
187 UnitLikeStructLit(ast::node_id), // the node ID of the pattern
189 ConstLit(ast::def_id), // the def ID of the constant
192 // An option identifying a branch (either a literal, a enum variant or a
196 var(/* disr val */int, @adt::Repr),
197 range(@ast::expr, @ast::expr),
199 vec_len_ge(uint, /* slice */uint)
202 pub fn opt_eq(tcx: ty::ctxt, a: &Opt, b: &Opt) -> bool {
204 (&lit(a), &lit(b)) => {
206 (UnitLikeStructLit(a), UnitLikeStructLit(b)) => a == b,
210 ExprLit(existing_a_expr) => a_expr = existing_a_expr,
211 ConstLit(a_const) => {
212 let e = const_eval::lookup_const_by_id(tcx, a_const);
215 UnitLikeStructLit(_) => {
216 fail!("UnitLikeStructLit should have been handled \
223 ExprLit(existing_b_expr) => b_expr = existing_b_expr,
224 ConstLit(b_const) => {
225 let e = const_eval::lookup_const_by_id(tcx, b_const);
228 UnitLikeStructLit(_) => {
229 fail!("UnitLikeStructLit should have been handled \
234 match const_eval::compare_lit_exprs(tcx, a_expr, b_expr) {
235 Some(val1) => val1 == 0,
236 None => fail!("compare_list_exprs: type mismatch"),
241 (&range(a1, a2), &range(b1, b2)) => {
242 let m1 = const_eval::compare_lit_exprs(tcx, a1, b1);
243 let m2 = const_eval::compare_lit_exprs(tcx, a2, b2);
245 (Some(val1), Some(val2)) => (val1 == 0 && val2 == 0),
246 _ => fail!("compare_list_exprs: type mismatch"),
249 (&var(a, _), &var(b, _)) => a == b,
250 (&vec_len_eq(a), &vec_len_eq(b)) => a == b,
251 (&vec_len_ge(a, _), &vec_len_ge(b, _)) => a == b,
256 pub enum opt_result {
257 single_result(Result),
259 range_result(Result, Result),
261 pub fn trans_opt(bcx: block, o: &Opt) -> opt_result {
262 let _icx = push_ctxt("match::trans_opt");
266 lit(ExprLit(lit_expr)) => {
267 let datumblock = expr::trans_to_datum(bcx, lit_expr);
268 return single_result(datumblock.to_result());
270 lit(UnitLikeStructLit(pat_id)) => {
271 let struct_ty = ty::node_id_to_type(bcx.tcx(), pat_id);
272 let datumblock = datum::scratch_datum(bcx, struct_ty, "", true);
273 return single_result(datumblock.to_result(bcx));
275 lit(ConstLit(lit_id)) => {
276 let llval = consts::get_const_val(bcx.ccx(), lit_id);
277 return single_result(rslt(bcx, llval));
279 var(disr_val, repr) => {
280 return adt::trans_case(bcx, repr, disr_val);
283 return range_result(rslt(bcx, consts::const_expr(ccx, l1)),
284 rslt(bcx, consts::const_expr(ccx, l2)));
287 return single_result(rslt(bcx, C_int(ccx, n as int)));
289 vec_len_ge(n, _) => {
290 return lower_bound(rslt(bcx, C_int(ccx, n as int)));
295 pub fn variant_opt(bcx: block, pat_id: ast::node_id)
298 match ccx.tcx.def_map.get_copy(&pat_id) {
299 ast::def_variant(enum_id, var_id) => {
300 let variants = ty::enum_variants(ccx.tcx, enum_id);
301 for (*variants).iter().advance |v| {
303 return var(v.disr_val,
304 adt::represent_node(bcx, pat_id))
307 ::std::util::unreachable();
310 ast::def_struct(_) => {
311 return lit(UnitLikeStructLit(pat_id));
314 ccx.sess.bug("non-variant or struct in variant_opt()");
320 pub enum TransBindingMode {
321 TrByValue(/*llbinding:*/ ValueRef),
326 * Information about a pattern binding:
327 * - `llmatch` is a pointer to a stack slot. The stack slot contains a
328 * pointer into the value being matched. Hence, llmatch has type `T**`
329 * where `T` is the value being matched.
330 * - `trmode` is the trans binding mode
331 * - `id` is the node id of the binding
332 * - `ty` is the Rust type of the binding */
334 pub struct BindingInfo {
336 trmode: TransBindingMode,
341 pub type BindingsMap = HashMap<ident, BindingInfo>;
344 pub struct ArmData<'self> {
346 arm: &'self ast::arm,
347 bindings_map: @BindingsMap
351 pub struct Match<'self> {
356 pub fn match_to_str(bcx: block, m: &Match) -> ~str {
357 if bcx.sess().verbose() {
358 // for many programs, this just take too long to serialize
359 fmt!("%?", m.pats.map(|p| pat_to_str(*p, bcx.sess().intr())))
361 fmt!("%u pats", m.pats.len())
365 pub fn matches_to_str(bcx: block, m: &[Match]) -> ~str {
366 fmt!("%?", m.map(|n| match_to_str(bcx, n)))
369 pub fn has_nested_bindings(m: &[Match], col: uint) -> bool {
370 for m.iter().advance |br| {
371 match br.pats[col].node {
372 ast::pat_ident(_, _, Some(_)) => return true,
379 pub fn expand_nested_bindings<'r>(bcx: block,
384 debug!("expand_nested_bindings(bcx=%s, m=%s, col=%u, val=%?)",
386 matches_to_str(bcx, m),
388 bcx.val_to_str(val));
389 let _indenter = indenter();
392 match br.pats[col].node {
393 ast::pat_ident(_, ref path, Some(inner)) => {
394 let pats = vec::append(
395 br.pats.slice(0u, col).to_owned(),
396 vec::append(~[inner],
397 br.pats.slice(col + 1u,
401 br.data.bindings_map.get(&path_to_ident(path));
403 Store(bcx, val, binding_info.llmatch);
406 data: br.data.clone()
414 pub fn assert_is_binding_or_wild(bcx: block, p: @ast::pat) {
415 if !pat_is_binding_or_wild(bcx.tcx().def_map, p) {
418 fmt!("Expected an identifier pattern but found p: %s",
419 pat_to_str(p, bcx.sess().intr())));
423 pub type enter_pat<'self> = &'self fn(@ast::pat) -> Option<~[@ast::pat]>;
425 pub fn enter_match<'r>(bcx: block,
432 debug!("enter_match(bcx=%s, m=%s, col=%u, val=%?)",
434 matches_to_str(bcx, m),
436 bcx.val_to_str(val));
437 let _indenter = indenter();
439 let mut result = ~[];
440 for m.iter().advance |br| {
441 match e(br.pats[col]) {
445 vec::append(sub, br.pats.slice(0u, col)),
446 br.pats.slice(col + 1u, br.pats.len()));
448 let this = br.pats[col];
450 ast::pat_ident(_, ref path, None) => {
451 if pat_is_binding(dm, this) {
453 br.data.bindings_map.get(
454 &path_to_ident(path));
455 Store(bcx, val, binding_info.llmatch);
463 data: br.data.clone()
470 debug!("result=%s", matches_to_str(bcx, result));
475 pub fn enter_default<'r>(bcx: block,
481 debug!("enter_default(bcx=%s, m=%s, col=%u, val=%?)",
483 matches_to_str(bcx, m),
485 bcx.val_to_str(val));
486 let _indenter = indenter();
488 do enter_match(bcx, dm, m, col, val) |p| {
490 ast::pat_wild | ast::pat_tup(_) | ast::pat_struct(*) => Some(~[]),
491 ast::pat_ident(_, _, None) if pat_is_binding(dm, p) => Some(~[]),
497 // <pcwalton> nmatsakis: what does enter_opt do?
498 // <pcwalton> in trans/match
499 // <pcwalton> trans/match.rs is like stumbling around in a dark cave
500 // <nmatsakis> pcwalton: the enter family of functions adjust the set of
501 // patterns as needed
502 // <nmatsakis> yeah, at some point I kind of achieved some level of
504 // <nmatsakis> anyhow, they adjust the patterns given that something of that
505 // kind has been found
506 // <nmatsakis> pcwalton: ok, right, so enter_XXX() adjusts the patterns, as I
508 // <nmatsakis> enter_match() kind of embodies the generic code
509 // <nmatsakis> it is provided with a function that tests each pattern to see
510 // if it might possibly apply and so forth
511 // <nmatsakis> so, if you have a pattern like {a: _, b: _, _} and one like _
512 // <nmatsakis> then _ would be expanded to (_, _)
513 // <nmatsakis> one spot for each of the sub-patterns
514 // <nmatsakis> enter_opt() is one of the more complex; it covers the fallible
516 // <nmatsakis> enter_rec_or_struct() or enter_tuple() are simpler, since they
517 // are infallible patterns
518 // <nmatsakis> so all patterns must either be records (resp. tuples) or
521 pub fn enter_opt<'r>(bcx: block,
528 debug!("enter_opt(bcx=%s, m=%s, col=%u, val=%?)",
530 matches_to_str(bcx, m),
532 bcx.val_to_str(val));
533 let _indenter = indenter();
536 let dummy = @ast::pat {id: 0, node: ast::pat_wild, span: dummy_sp()};
537 do enter_match(bcx, tcx.def_map, m, col, val) |p| {
540 ast::pat_ident(_, _, None) if pat_is_const(tcx.def_map, p) => {
541 let const_def = tcx.def_map.get_copy(&p.id);
542 let const_def_id = ast_util::def_id_of_def(const_def);
543 if opt_eq(tcx, &lit(ConstLit(const_def_id)), opt) {
549 ast::pat_enum(_, ref subpats) => {
550 if opt_eq(tcx, &variant_opt(bcx, p.id), opt) {
551 // XXX: Must we clone?
553 None => Some(vec::from_elem(variant_size, dummy)),
554 _ => (*subpats).clone(),
560 ast::pat_ident(_, _, None)
561 if pat_is_variant_or_struct(tcx.def_map, p) => {
562 if opt_eq(tcx, &variant_opt(bcx, p.id), opt) {
569 if opt_eq(tcx, &lit(ExprLit(l)), opt) {Some(~[])} else {None}
571 ast::pat_range(l1, l2) => {
572 if opt_eq(tcx, &range(l1, l2), opt) {Some(~[])} else {None}
574 ast::pat_struct(_, ref field_pats, _) => {
575 if opt_eq(tcx, &variant_opt(bcx, p.id), opt) {
576 // Look up the struct variant ID.
578 match tcx.def_map.get_copy(&p.id) {
579 ast::def_variant(_, found_struct_id) => {
580 struct_id = found_struct_id;
583 tcx.sess.span_bug(p.span, "expected enum variant def");
587 // Reorder the patterns into the same order they were
588 // specified in the struct definition. Also fill in
589 // unspecified fields with dummy.
590 let mut reordered_patterns = ~[];
591 let r = ty::lookup_struct_fields(tcx, struct_id);
592 for r.iter().advance |field| {
593 match field_pats.iter().find_(|p| p.ident == field.ident) {
594 None => reordered_patterns.push(dummy),
595 Some(fp) => reordered_patterns.push(fp.pat)
598 Some(reordered_patterns)
603 ast::pat_vec(ref before, slice, ref after) => {
606 let n = before.len() + after.len();
607 let i = before.len();
608 if opt_eq(tcx, &vec_len_ge(n, i), opt) {
609 Some(vec::append_one((*before).clone(), slice) +
616 let n = before.len();
617 if opt_eq(tcx, &vec_len_eq(n), opt) {
618 Some((*before).clone())
626 assert_is_binding_or_wild(bcx, p);
627 Some(vec::from_elem(variant_size, dummy))
633 pub fn enter_rec_or_struct<'r>(bcx: block,
637 fields: &[ast::ident],
640 debug!("enter_rec_or_struct(bcx=%s, m=%s, col=%u, val=%?)",
642 matches_to_str(bcx, m),
644 bcx.val_to_str(val));
645 let _indenter = indenter();
647 let dummy = @ast::pat {id: 0, node: ast::pat_wild, span: dummy_sp()};
648 do enter_match(bcx, dm, m, col, val) |p| {
650 ast::pat_struct(_, ref fpats, _) => {
652 for fields.iter().advance |fname| {
653 match fpats.iter().find_(|p| p.ident == *fname) {
654 None => pats.push(dummy),
655 Some(pat) => pats.push(pat.pat)
661 assert_is_binding_or_wild(bcx, p);
662 Some(vec::from_elem(fields.len(), dummy))
668 pub fn enter_tup<'r>(bcx: block,
675 debug!("enter_tup(bcx=%s, m=%s, col=%u, val=%?)",
677 matches_to_str(bcx, m),
679 bcx.val_to_str(val));
680 let _indenter = indenter();
682 let dummy = @ast::pat {id: 0, node: ast::pat_wild, span: dummy_sp()};
683 do enter_match(bcx, dm, m, col, val) |p| {
685 ast::pat_tup(ref elts) => Some((*elts).clone()),
687 assert_is_binding_or_wild(bcx, p);
688 Some(vec::from_elem(n_elts, dummy))
694 pub fn enter_tuple_struct<'r>(bcx: block,
701 debug!("enter_tuple_struct(bcx=%s, m=%s, col=%u, val=%?)",
703 matches_to_str(bcx, m),
705 bcx.val_to_str(val));
706 let _indenter = indenter();
708 let dummy = @ast::pat {id: 0, node: ast::pat_wild, span: dummy_sp()};
709 do enter_match(bcx, dm, m, col, val) |p| {
711 ast::pat_enum(_, Some(ref elts)) => Some((*elts).clone()),
713 assert_is_binding_or_wild(bcx, p);
714 Some(vec::from_elem(n_elts, dummy))
720 pub fn enter_box<'r>(bcx: block,
726 debug!("enter_box(bcx=%s, m=%s, col=%u, val=%?)",
728 matches_to_str(bcx, m),
730 bcx.val_to_str(val));
731 let _indenter = indenter();
733 let dummy = @ast::pat {id: 0, node: ast::pat_wild, span: dummy_sp()};
734 do enter_match(bcx, dm, m, col, val) |p| {
736 ast::pat_box(sub) => {
740 assert_is_binding_or_wild(bcx, p);
747 pub fn enter_uniq<'r>(bcx: block,
753 debug!("enter_uniq(bcx=%s, m=%s, col=%u, val=%?)",
755 matches_to_str(bcx, m),
757 bcx.val_to_str(val));
758 let _indenter = indenter();
760 let dummy = @ast::pat {id: 0, node: ast::pat_wild, span: dummy_sp()};
761 do enter_match(bcx, dm, m, col, val) |p| {
763 ast::pat_uniq(sub) => {
767 assert_is_binding_or_wild(bcx, p);
774 pub fn enter_region<'r>(bcx: block,
780 debug!("enter_region(bcx=%s, m=%s, col=%u, val=%?)",
782 matches_to_str(bcx, m),
784 bcx.val_to_str(val));
785 let _indenter = indenter();
787 let dummy = @ast::pat { id: 0, node: ast::pat_wild, span: dummy_sp() };
788 do enter_match(bcx, dm, m, col, val) |p| {
790 ast::pat_region(sub) => {
794 assert_is_binding_or_wild(bcx, p);
801 // Returns the options in one column of matches. An option is something that
802 // needs to be conditionally matched at runtime; for example, the discriminant
803 // on a set of enum variants or a literal.
804 pub fn get_options(bcx: block, m: &[Match], col: uint) -> ~[Opt] {
806 fn add_to_set(tcx: ty::ctxt, set: &mut ~[Opt], val: Opt) {
807 if set.iter().any(|l| opt_eq(tcx, l, &val)) {return;}
812 for m.iter().advance |br| {
813 let cur = br.pats[col];
816 add_to_set(ccx.tcx, &mut found, lit(ExprLit(l)));
818 ast::pat_ident(*) => {
819 // This is one of: an enum variant, a unit-like struct, or a
821 match ccx.tcx.def_map.find(&cur.id) {
822 Some(&ast::def_variant(*)) => {
823 add_to_set(ccx.tcx, &mut found,
824 variant_opt(bcx, cur.id));
826 Some(&ast::def_struct(*)) => {
827 add_to_set(ccx.tcx, &mut found,
828 lit(UnitLikeStructLit(cur.id)));
830 Some(&ast::def_static(const_did, false)) => {
831 add_to_set(ccx.tcx, &mut found,
832 lit(ConstLit(const_did)));
837 ast::pat_enum(*) | ast::pat_struct(*) => {
838 // This could be one of: a tuple-like enum variant, a
839 // struct-like enum variant, or a struct.
840 match ccx.tcx.def_map.find(&cur.id) {
841 Some(&ast::def_fn(*)) |
842 Some(&ast::def_variant(*)) => {
843 add_to_set(ccx.tcx, &mut found,
844 variant_opt(bcx, cur.id));
846 Some(&ast::def_static(const_did, false)) => {
847 add_to_set(ccx.tcx, &mut found,
848 lit(ConstLit(const_did)));
853 ast::pat_range(l1, l2) => {
854 add_to_set(ccx.tcx, &mut found, range(l1, l2));
856 ast::pat_vec(ref before, slice, ref after) => {
857 let opt = match slice {
858 None => vec_len_eq(before.len()),
859 Some(_) => vec_len_ge(before.len() + after.len(),
862 add_to_set(ccx.tcx, &mut found, opt);
870 pub struct ExtractedBlock {
875 pub fn extract_variant_args(bcx: block,
880 let _icx = push_ctxt("match::extract_variant_args");
881 let args = do vec::from_fn(adt::num_args(repr, disr_val)) |i| {
882 adt::trans_field_ptr(bcx, repr, val, disr_val, i)
885 ExtractedBlock { vals: args, bcx: bcx }
888 fn match_datum(bcx: block, val: ValueRef, pat_id: ast::node_id) -> Datum {
889 //! Helper for converting from the ValueRef that we pass around in
890 //! the match code, which is always by ref, into a Datum. Eventually
891 //! we should just pass around a Datum and be done with it.
893 let ty = node_id_type(bcx, pat_id);
894 Datum {val: val, ty: ty, mode: datum::ByRef(RevokeClean)}
898 pub fn extract_vec_elems(bcx: block,
900 pat_id: ast::node_id,
906 let _icx = push_ctxt("match::extract_vec_elems");
907 let vec_datum = match_datum(bcx, val, pat_id);
908 let (bcx, base, len) = vec_datum.get_vec_base_and_len(bcx, pat_span,
910 let vt = tvec::vec_types(bcx, node_id_type(bcx, pat_id));
912 let mut elems = do vec::from_fn(elem_count) |i| {
914 None => GEPi(bcx, base, [i]),
915 Some(n) if i < n => GEPi(bcx, base, [i]),
916 Some(n) if i > n => {
917 InBoundsGEP(bcx, base, [
919 C_int(bcx.ccx(), (elem_count - i) as int))])
921 _ => unsafe { llvm::LLVMGetUndef(vt.llunit_ty.to_ref()) }
926 let slice_offset = Mul(bcx, vt.llunit_size,
927 C_int(bcx.ccx(), n as int)
929 let slice_begin = tvec::pointer_add(bcx, base, slice_offset);
930 let slice_len_offset = Mul(bcx, vt.llunit_size,
931 C_int(bcx.ccx(), (elem_count - 1u) as int)
933 let slice_len = Sub(bcx, len, slice_len_offset);
934 let slice_ty = ty::mk_evec(bcx.tcx(),
935 ty::mt {ty: vt.unit_ty, mutbl: ast::m_imm},
936 ty::vstore_slice(ty::re_static)
938 let scratch = scratch_datum(bcx, slice_ty, "", false);
939 Store(bcx, slice_begin,
940 GEPi(bcx, scratch.val, [0u, abi::slice_elt_base])
942 Store(bcx, slice_len,
943 GEPi(bcx, scratch.val, [0u, abi::slice_elt_len])
945 elems[n] = scratch.val;
946 scratch.add_clean(bcx);
949 ExtractedBlock { vals: elems, bcx: bcx }
952 // NB: This function does not collect fields from struct-like enum variants.
953 pub fn collect_record_or_struct_fields(bcx: block,
957 let mut fields: ~[ast::ident] = ~[];
958 for m.iter().advance |br| {
959 match br.pats[col].node {
960 ast::pat_struct(_, ref fs, _) => {
961 match ty::get(node_id_type(bcx, br.pats[col].id)).sty {
962 ty::ty_struct(*) => extend(&mut fields, *fs),
971 fn extend(idents: &mut ~[ast::ident], field_pats: &[ast::field_pat]) {
972 for field_pats.iter().advance |field_pat| {
973 let field_ident = field_pat.ident;
974 if !idents.iter().any(|x| *x == field_ident) {
975 idents.push(field_ident);
981 pub fn pats_require_rooting(bcx: block,
985 do m.iter().any |br| {
986 let pat_id = br.pats[col].id;
987 let key = root_map_key {id: pat_id, derefs: 0u };
988 bcx.ccx().maps.root_map.contains_key(&key)
992 pub fn root_pats_as_necessary(mut bcx: block,
997 for m.iter().advance |br| {
998 let pat_id = br.pats[col].id;
1000 let datum = Datum {val: val, ty: node_id_type(bcx, pat_id),
1001 mode: ByRef(ZeroMem)};
1002 bcx = datum.root_and_write_guard(bcx, br.pats[col].span, pat_id, 0);
1008 // Macro for deciding whether any of the remaining matches fit a given kind of
1009 // pattern. Note that, because the macro is well-typed, either ALL of the
1010 // matches should fit that sort of pattern or NONE (however, some of the
1011 // matches may be wildcards like _ or identifiers).
1012 macro_rules! any_pat (
1013 ($m:expr, $pattern:pat) => (
1014 do ($m).iter().any |br| {
1015 match br.pats[col].node {
1023 pub fn any_box_pat(m: &[Match], col: uint) -> bool {
1024 any_pat!(m, ast::pat_box(_))
1027 pub fn any_uniq_pat(m: &[Match], col: uint) -> bool {
1028 any_pat!(m, ast::pat_uniq(_))
1031 pub fn any_region_pat(m: &[Match], col: uint) -> bool {
1032 any_pat!(m, ast::pat_region(_))
1035 pub fn any_tup_pat(m: &[Match], col: uint) -> bool {
1036 any_pat!(m, ast::pat_tup(_))
1039 pub fn any_tuple_struct_pat(bcx: block, m: &[Match], col: uint) -> bool {
1040 do m.iter().any |br| {
1041 let pat = br.pats[col];
1043 ast::pat_enum(_, Some(_)) => {
1044 match bcx.tcx().def_map.find(&pat.id) {
1045 Some(&ast::def_fn(*)) |
1046 Some(&ast::def_struct(*)) => true,
1055 pub type mk_fail = @fn() -> BasicBlockRef;
1057 pub fn pick_col(m: &[Match]) -> uint {
1058 fn score(p: &ast::pat) -> uint {
1060 ast::pat_lit(_) | ast::pat_enum(_, _) | ast::pat_range(_, _) => 1u,
1061 ast::pat_ident(_, _, Some(p)) => score(p),
1065 let mut scores = vec::from_elem(m[0].pats.len(), 0u);
1066 for m.iter().advance |br| {
1068 for br.pats.iter().advance |p| { scores[i] += score(*p); i += 1u; }
1070 let mut max_score = 0u;
1071 let mut best_col = 0u;
1073 for scores.iter().advance |score| {
1076 // Irrefutable columns always go first, they'd only be duplicated in
1078 if score == 0u { return i; }
1079 // If no irrefutable ones are found, we pick the one with the biggest
1080 // branching factor.
1081 if score > max_score { max_score = score; best_col = i; }
1088 pub enum branch_kind { no_branch, single, switch, compare, compare_vec_len, }
1090 // Compiles a comparison between two things.
1092 // NB: This must produce an i1, not a Rust bool (i8).
1093 pub fn compare_values(cx: block,
1098 let _icx = push_ctxt("compare_values");
1099 if ty::type_is_scalar(rhs_t) {
1100 let rs = compare_scalar_types(cx, lhs, rhs, rhs_t, ast::eq);
1101 return rslt(rs.bcx, rs.val);
1104 match ty::get(rhs_t).sty {
1105 ty::ty_estr(ty::vstore_uniq) => {
1106 let scratch_lhs = alloca(cx, val_ty(lhs), "__lhs");
1107 Store(cx, lhs, scratch_lhs);
1108 let scratch_rhs = alloca(cx, val_ty(rhs), "__rhs");
1109 Store(cx, rhs, scratch_rhs);
1110 let did = langcall(cx, None,
1111 fmt!("comparison of `%s`", cx.ty_to_str(rhs_t)),
1112 UniqStrEqFnLangItem);
1113 let result = callee::trans_lang_call(cx, did, [scratch_lhs, scratch_rhs], None);
1116 val: bool_to_i1(result.bcx, result.val)
1120 let did = langcall(cx, None,
1121 fmt!("comparison of `%s`", cx.ty_to_str(rhs_t)),
1123 let result = callee::trans_lang_call(cx, did, [lhs, rhs], None);
1126 val: bool_to_i1(result.bcx, result.val)
1130 cx.tcx().sess.bug("only scalars and strings supported in \
1136 fn store_non_ref_bindings(bcx: block,
1137 bindings_map: &BindingsMap,
1138 mut opt_temp_cleanups: Option<&mut ~[ValueRef]>)
1143 * For each copy/move binding, copy the value from the value
1144 * being matched into its final home. This code executes once
1145 * one of the patterns for a given arm has completely matched.
1146 * It adds temporary cleanups to the `temp_cleanups` array,
1147 * if one is provided.
1151 for bindings_map.each_value |&binding_info| {
1152 match binding_info.trmode {
1153 TrByValue(lldest) => {
1154 let llval = Load(bcx, binding_info.llmatch); // get a T*
1155 let datum = Datum {val: llval, ty: binding_info.ty,
1156 mode: ByRef(ZeroMem)};
1157 bcx = datum.store_to(bcx, INIT, lldest);
1158 do opt_temp_cleanups.mutate |temp_cleanups| {
1159 add_clean_temp_mem(bcx, lldest, binding_info.ty);
1160 temp_cleanups.push(lldest);
1170 fn insert_lllocals(bcx: block,
1171 bindings_map: &BindingsMap,
1172 binding_mode: IrrefutablePatternBindingMode,
1173 add_cleans: bool) -> block {
1175 * For each binding in `data.bindings_map`, adds an appropriate entry into
1176 * the `fcx.lllocals` map. If add_cleans is true, then adds cleanups for
1180 let llmap = match binding_mode {
1181 BindLocal => bcx.fcx.lllocals,
1182 BindArgument => bcx.fcx.llargs
1185 for bindings_map.each_value |&binding_info| {
1186 let llval = match binding_info.trmode {
1187 // By value bindings: use the stack slot that we
1188 // copied/moved the value into
1189 TrByValue(lldest) => {
1191 add_clean(bcx, lldest, binding_info.ty);
1197 // By ref binding: use the ptr into the matched value
1199 binding_info.llmatch
1203 debug!("binding %? to %s", binding_info.id, bcx.val_to_str(llval));
1204 llmap.insert(binding_info.id, llval);
1209 pub fn compile_guard(bcx: block,
1210 guard_expr: @ast::expr,
1214 chk: Option<mk_fail>)
1216 debug!("compile_guard(bcx=%s, guard_expr=%s, m=%s, vals=%?)",
1218 bcx.expr_to_str(guard_expr),
1219 matches_to_str(bcx, m),
1220 vals.map(|v| bcx.val_to_str(*v)));
1221 let _indenter = indenter();
1224 let mut temp_cleanups = ~[];
1225 bcx = store_non_ref_bindings(bcx,
1227 Some(&mut temp_cleanups));
1228 bcx = insert_lllocals(bcx, data.bindings_map, BindLocal, false);
1230 let val = unpack_result!(bcx, {
1231 do with_scope_result(bcx, guard_expr.info(),
1233 expr::trans_to_datum(bcx, guard_expr).to_result()
1236 let val = bool_to_i1(bcx, val);
1238 // Revoke the temp cleanups now that the guard successfully executed.
1239 for temp_cleanups.iter().advance |llval| {
1240 revoke_clean(bcx, *llval);
1243 return do with_cond(bcx, Not(bcx, val)) |bcx| {
1244 // Guard does not match: free the values we copied,
1245 // and remove all bindings from the lllocals table
1246 let bcx = drop_bindings(bcx, data);
1247 compile_submatch(bcx, m, vals, chk);
1251 fn drop_bindings(bcx: block, data: &ArmData) -> block {
1253 for data.bindings_map.each_value |&binding_info| {
1254 match binding_info.trmode {
1255 TrByValue(llval) => {
1256 bcx = glue::drop_ty(bcx, llval, binding_info.ty);
1260 bcx.fcx.lllocals.remove(&binding_info.id);
1266 pub fn compile_submatch(bcx: block,
1269 chk: Option<mk_fail>) {
1270 debug!("compile_submatch(bcx=%s, m=%s, vals=%?)",
1272 matches_to_str(bcx, m),
1273 vals.map(|v| bcx.val_to_str(*v)));
1274 let _indenter = indenter();
1277 For an empty match, a fall-through case must exist
1279 assert!((m.len() > 0u || chk.is_some()));
1280 let _icx = push_ctxt("match::compile_submatch");
1282 let tcx = bcx.tcx();
1283 let dm = tcx.def_map;
1285 Br(bcx, chk.get()());
1288 if m[0].pats.len() == 0u {
1289 let data = &m[0].data;
1290 match data.arm.guard {
1291 Some(guard_expr) => {
1292 bcx = compile_guard(bcx,
1295 m.slice(1, m.len()),
1301 Br(bcx, data.bodycx.llbb);
1305 let col = pick_col(m);
1306 let val = vals[col];
1308 if has_nested_bindings(m, col) {
1309 let expanded = expand_nested_bindings(bcx, m, col, val);
1310 compile_submatch_continue(bcx, expanded, vals, chk, col, val)
1312 compile_submatch_continue(bcx, m, vals, chk, col, val)
1316 fn compile_submatch_continue(mut bcx: block,
1319 chk: Option<mk_fail>,
1322 let tcx = bcx.tcx();
1323 let dm = tcx.def_map;
1325 let vals_left = vec::append(vals.slice(0u, col).to_owned(),
1326 vals.slice(col + 1u, vals.len()));
1327 let ccx = bcx.fcx.ccx;
1329 let mut pat_span = dummy_sp();
1330 for m.iter().advance |br| {
1331 // Find a real id (we're adding placeholder wildcard patterns, but
1332 // each column is guaranteed to have at least one real pattern)
1334 pat_id = br.pats[col].id;
1335 pat_span = br.pats[col].span;
1339 // If we are not matching against an `@T`, we should not be
1340 // required to root any values.
1341 assert!(any_box_pat(m, col) || !pats_require_rooting(bcx, m, col));
1343 let rec_fields = collect_record_or_struct_fields(bcx, m, col);
1344 if rec_fields.len() > 0 {
1345 let pat_ty = node_id_type(bcx, pat_id);
1346 let pat_repr = adt::represent_type(bcx.ccx(), pat_ty);
1347 do expr::with_field_tys(tcx, pat_ty, None) |discr, field_tys| {
1348 let rec_vals = rec_fields.map(|field_name| {
1349 let ix = ty::field_idx_strict(tcx, *field_name, field_tys);
1350 adt::trans_field_ptr(bcx, pat_repr, val, discr, ix)
1354 enter_rec_or_struct(bcx, dm, m, col, rec_fields, val),
1355 vec::append(rec_vals, vals_left),
1361 if any_tup_pat(m, col) {
1362 let tup_ty = node_id_type(bcx, pat_id);
1363 let tup_repr = adt::represent_type(bcx.ccx(), tup_ty);
1364 let n_tup_elts = match ty::get(tup_ty).sty {
1365 ty::ty_tup(ref elts) => elts.len(),
1366 _ => ccx.sess.bug("non-tuple type in tuple pattern")
1368 let tup_vals = do vec::from_fn(n_tup_elts) |i| {
1369 adt::trans_field_ptr(bcx, tup_repr, val, 0, i)
1371 compile_submatch(bcx, enter_tup(bcx, dm, m, col, val, n_tup_elts),
1372 vec::append(tup_vals, vals_left), chk);
1376 if any_tuple_struct_pat(bcx, m, col) {
1377 let struct_ty = node_id_type(bcx, pat_id);
1378 let struct_element_count;
1379 match ty::get(struct_ty).sty {
1380 ty::ty_struct(struct_id, _) => {
1381 struct_element_count =
1382 ty::lookup_struct_fields(tcx, struct_id).len();
1385 ccx.sess.bug("non-struct type in tuple struct pattern");
1389 let struct_repr = adt::represent_type(bcx.ccx(), struct_ty);
1390 let llstructvals = do vec::from_fn(struct_element_count) |i| {
1391 adt::trans_field_ptr(bcx, struct_repr, val, 0, i)
1393 compile_submatch(bcx,
1394 enter_tuple_struct(bcx, dm, m, col, val,
1395 struct_element_count),
1396 vec::append(llstructvals, vals_left),
1401 // Unbox in case of a box field
1402 if any_box_pat(m, col) {
1403 bcx = root_pats_as_necessary(bcx, m, col, val);
1404 let llbox = Load(bcx, val);
1405 let unboxed = GEPi(bcx, llbox, [0u, abi::box_field_body]);
1406 compile_submatch(bcx, enter_box(bcx, dm, m, col, val),
1407 vec::append(~[unboxed], vals_left), chk);
1411 if any_uniq_pat(m, col) {
1412 let pat_ty = node_id_type(bcx, pat_id);
1413 let llbox = Load(bcx, val);
1414 let unboxed = match ty::get(pat_ty).sty {
1415 ty::ty_uniq(*) if !ty::type_contents(bcx.tcx(), pat_ty).contains_managed() => llbox,
1416 _ => GEPi(bcx, llbox, [0u, abi::box_field_body])
1418 compile_submatch(bcx, enter_uniq(bcx, dm, m, col, val),
1419 vec::append(~[unboxed], vals_left), chk);
1423 if any_region_pat(m, col) {
1424 let loaded_val = Load(bcx, val);
1425 compile_submatch(bcx, enter_region(bcx, dm, m, col, val),
1426 vec::append(~[loaded_val], vals_left), chk);
1430 // Decide what kind of branch we need
1431 let opts = get_options(bcx, m, col);
1432 let mut kind = no_branch;
1433 let mut test_val = val;
1434 if opts.len() > 0u {
1437 let (the_kind, val_opt) = adt::trans_switch(bcx, repr, val);
1439 for val_opt.iter().advance |&tval| { test_val = tval; }
1442 let pty = node_id_type(bcx, pat_id);
1443 test_val = load_if_immediate(bcx, val, pty);
1444 kind = if ty::type_is_integral(pty) { switch }
1448 test_val = Load(bcx, val);
1451 vec_len_eq(*) | vec_len_ge(*) => {
1452 let vt = tvec::vec_types(bcx, node_id_type(bcx, pat_id));
1453 let unboxed = load_if_immediate(bcx, val, vt.vec_ty);
1454 let (_, len) = tvec::get_base_and_len(
1455 bcx, unboxed, vt.vec_ty
1457 test_val = SDiv(bcx, len, vt.llunit_size);
1458 kind = compare_vec_len;
1462 for opts.iter().advance |o| {
1464 range(_, _) => { kind = compare; break }
1468 let else_cx = match kind {
1469 no_branch | single => bcx,
1470 _ => sub_block(bcx, "match_else")
1472 let sw = if kind == switch {
1473 Switch(bcx, test_val, else_cx.llbb, opts.len())
1475 C_int(ccx, 0) // Placeholder for when not using a switch
1478 let defaults = enter_default(else_cx, dm, m, col, val);
1479 let exhaustive = chk.is_none() && defaults.len() == 0u;
1480 let len = opts.len();
1483 // Compile subtrees for each option
1484 for opts.iter().advance |opt| {
1486 let mut opt_cx = else_cx;
1487 if !exhaustive || i < len {
1488 opt_cx = sub_block(bcx, "match_case");
1490 single => Br(bcx, opt_cx.llbb),
1492 match trans_opt(bcx, opt) {
1493 single_result(r) => {
1495 llvm::LLVMAddCase(sw, r.val, opt_cx.llbb);
1501 "in compile_submatch, expected \
1502 trans_opt to return a single_result")
1507 let t = node_id_type(bcx, pat_id);
1508 let Result {bcx: after_cx, val: matches} = {
1509 do with_scope_result(bcx, None,
1510 "compare_scope") |bcx| {
1511 match trans_opt(bcx, opt) {
1513 Result {bcx, val}) => {
1514 compare_values(bcx, test_val, val, t)
1517 Result {bcx, val}) => {
1518 compare_scalar_types(
1523 Result {val: vbegin, _},
1524 Result {bcx, val: vend}) => {
1525 let Result {bcx, val: llge} =
1526 compare_scalar_types(
1528 vbegin, t, ast::ge);
1529 let Result {bcx, val: llle} =
1530 compare_scalar_types(
1531 bcx, test_val, vend,
1533 rslt(bcx, And(bcx, llge, llle))
1538 bcx = sub_block(after_cx, "compare_next");
1539 CondBr(after_cx, matches, opt_cx.llbb, bcx.llbb);
1541 compare_vec_len => {
1542 let Result {bcx: after_cx, val: matches} = {
1543 do with_scope_result(bcx, None,
1544 "compare_vec_len_scope") |bcx| {
1545 match trans_opt(bcx, opt) {
1547 Result {bcx, val}) => {
1548 let value = compare_scalar_values(
1550 signed_int, ast::eq);
1554 Result {bcx, val: val}) => {
1555 let value = compare_scalar_values(
1557 signed_int, ast::ge);
1561 Result {val: vbegin, _},
1562 Result {bcx, val: vend}) => {
1564 compare_scalar_values(
1566 vbegin, signed_int, ast::ge);
1568 compare_scalar_values(
1569 bcx, test_val, vend,
1570 signed_int, ast::le);
1571 rslt(bcx, And(bcx, llge, llle))
1576 bcx = sub_block(after_cx, "compare_vec_len_next");
1577 CondBr(after_cx, matches, opt_cx.llbb, bcx.llbb);
1581 } else if kind == compare || kind == compare_vec_len {
1582 Br(bcx, else_cx.llbb);
1586 let mut unpacked = ~[];
1588 var(disr_val, repr) => {
1589 let ExtractedBlock {vals: argvals, bcx: new_bcx} =
1590 extract_variant_args(opt_cx, repr, disr_val, val);
1591 size = argvals.len();
1595 vec_len_eq(n) | vec_len_ge(n, _) => {
1596 let n = match *opt {
1597 vec_len_ge(*) => n + 1u,
1600 let slice = match *opt {
1601 vec_len_ge(_, i) => Some(i),
1604 let args = extract_vec_elems(opt_cx, pat_span, pat_id, n, slice,
1606 size = args.vals.len();
1607 unpacked = args.vals.clone();
1610 lit(_) | range(_, _) => ()
1612 let opt_ms = enter_opt(opt_cx, m, opt, col, size, val);
1613 let opt_vals = vec::append(unpacked, vals_left);
1614 compile_submatch(opt_cx, opt_ms, opt_vals, chk);
1617 // Compile the fall-through case, if any
1619 if kind == compare || kind == compare_vec_len {
1620 Br(bcx, else_cx.llbb);
1623 compile_submatch(else_cx, defaults, vals_left, chk);
1628 pub fn trans_match(bcx: block,
1629 match_expr: &ast::expr,
1630 discr_expr: @ast::expr,
1632 dest: Dest) -> block {
1633 let _icx = push_ctxt("match::trans_match");
1634 do with_scope(bcx, match_expr.info(), "match") |bcx| {
1635 trans_match_inner(bcx, discr_expr, arms, dest)
1639 fn create_bindings_map(bcx: block, pat: @ast::pat) -> BindingsMap {
1640 // Create the bindings map, which is a mapping from each binding name
1641 // to an alloca() that will be the value for that local variable.
1642 // Note that we use the names because each binding will have many ids
1643 // from the various alternatives.
1644 let ccx = bcx.ccx();
1645 let tcx = bcx.tcx();
1646 let mut bindings_map = HashMap::new();
1647 do pat_bindings(tcx.def_map, pat) |bm, p_id, _s, path| {
1648 let ident = path_to_ident(path);
1649 let variable_ty = node_id_type(bcx, p_id);
1650 let llvariable_ty = type_of::type_of(ccx, variable_ty);
1655 ast::bind_infer => {
1656 // in this case, the final type of the variable will be T,
1657 // but during matching we need to store a *T as explained
1659 llmatch = alloca(bcx, llvariable_ty.ptr_to(), "__llmatch");
1660 trmode = TrByValue(alloca(bcx, llvariable_ty,
1663 ast::bind_by_ref(_) => {
1664 llmatch = alloca(bcx, llvariable_ty, bcx.ident(ident));
1668 bindings_map.insert(ident, BindingInfo {
1669 llmatch: llmatch, trmode: trmode,
1670 id: p_id, ty: variable_ty
1673 return bindings_map;
1676 pub fn trans_match_inner(scope_cx: block,
1677 discr_expr: @ast::expr,
1679 dest: Dest) -> block {
1680 let _icx = push_ctxt("match::trans_match_inner");
1681 let mut bcx = scope_cx;
1682 let tcx = bcx.tcx();
1684 let discr_datum = unpack_datum!(bcx, {
1685 expr::trans_to_datum(bcx, discr_expr)
1687 if bcx.unreachable {
1691 let mut arm_datas = ~[];
1692 let mut matches = ~[];
1693 for arms.iter().advance |arm| {
1694 let body = scope_block(bcx, arm.body.info(), "case_body");
1695 let bindings_map = create_bindings_map(bcx, arm.pats[0]);
1696 let arm_data = ArmData {
1699 bindings_map: @bindings_map
1701 arm_datas.push(arm_data.clone());
1702 for arm.pats.iter().advance |p| {
1703 matches.push(Match {
1705 data: arm_data.clone(),
1710 let t = node_id_type(bcx, discr_expr.id);
1712 if ty::type_is_empty(tcx, t) {
1713 // Special case for empty types
1714 let fail_cx = @mut None;
1715 let f: mk_fail = || mk_fail(scope_cx, discr_expr.span,
1716 @"scrutinizing value that can't exist", fail_cx);
1722 let lldiscr = discr_datum.to_zeroable_ref_llval(bcx);
1723 compile_submatch(bcx, matches, [lldiscr], chk);
1725 let mut arm_cxs = ~[];
1726 for arm_datas.iter().advance |arm_data| {
1727 let mut bcx = arm_data.bodycx;
1729 // If this arm has a guard, then the various by-value bindings have
1730 // already been copied into their homes. If not, we do it here. This
1731 // is just to reduce code space. See extensive comment at the start
1732 // of the file for more details.
1733 if arm_data.arm.guard.is_none() {
1734 bcx = store_non_ref_bindings(bcx, arm_data.bindings_map, None);
1737 // insert bindings into the lllocals map and add cleanups
1738 bcx = insert_lllocals(bcx, arm_data.bindings_map, BindLocal, true);
1740 bcx = controlflow::trans_block(bcx, &arm_data.arm.body, dest);
1741 bcx = trans_block_cleanups(bcx, block_cleanups(arm_data.bodycx));
1745 bcx = controlflow::join_blocks(scope_cx, arm_cxs);
1748 fn mk_fail(bcx: block, sp: span, msg: @str,
1749 finished: @mut Option<BasicBlockRef>) -> BasicBlockRef {
1750 match *finished { Some(bb) => return bb, _ => () }
1751 let fail_cx = sub_block(bcx, "case_fallthrough");
1752 controlflow::trans_fail(fail_cx, Some(sp), msg);
1753 *finished = Some(fail_cx.llbb);
1754 return fail_cx.llbb;
1758 pub enum IrrefutablePatternBindingMode {
1759 // Stores the association between node ID and LLVM value in `lllocals`.
1761 // Stores the association between node ID and LLVM value in `llargs`.
1765 pub fn store_local(bcx: block,
1767 opt_init_expr: Option<@ast::expr>)
1770 * Generates code for a local variable declaration like
1771 * `let <pat>;` or `let <pat> = <opt_init_expr>`.
1773 let _icx = push_ctxt("match::store_local");
1776 return match opt_init_expr {
1777 Some(init_expr) => {
1778 // Optimize the "let x = expr" case. This just writes
1779 // the result of evaluating `expr` directly into the alloca
1780 // for `x`. Often the general path results in similar or the
1781 // same code post-optimization, but not always. In particular,
1782 // in unsafe code, you can have expressions like
1784 // let x = intrinsics::uninit();
1786 // In such cases, the more general path is unsafe, because
1787 // it assumes it is matching against a valid value.
1788 match simple_identifier(pat) {
1790 return mk_binding_alloca(
1791 bcx, pat.id, path, BindLocal,
1792 |bcx, _, llval| expr::trans_into(bcx, init_expr,
1793 expr::SaveIn(llval)));
1803 expr::trans_to_datum(bcx, init_expr));
1804 if ty::type_is_bot(expr_ty(bcx, init_expr)) {
1805 create_dummy_locals(bcx, pat)
1807 if bcx.sess().asm_comments() {
1808 add_comment(bcx, "creating zeroable ref llval");
1810 let llptr = init_datum.to_zeroable_ref_llval(bcx);
1811 return bind_irrefutable_pat(bcx, pat, llptr, BindLocal);
1815 create_dummy_locals(bcx, pat)
1819 fn create_dummy_locals(mut bcx: block, pat: @ast::pat) -> block {
1820 // create dummy memory for the variables if we have no
1821 // value to store into them immediately
1822 let tcx = bcx.tcx();
1823 do pat_bindings(tcx.def_map, pat) |_, p_id, _, path| {
1824 bcx = mk_binding_alloca(
1825 bcx, p_id, path, BindLocal,
1826 |bcx, var_ty, llval| { zero_mem(bcx, llval, var_ty); bcx });
1832 pub fn store_arg(mut bcx: block,
1837 * Generates code for argument patterns like `fn foo(<pat>: T)`.
1838 * Creates entries in the `llargs` map for each of the bindings
1843 * - `pat` is the argument pattern
1844 * - `llval` is a pointer to the argument value (in other words,
1845 * if the argument type is `T`, then `llval` is a `T*`). In some
1846 * cases, this code may zero out the memory `llval` points at.
1848 let _icx = push_ctxt("match::store_arg");
1850 // We always need to cleanup the argument as we exit the fn scope.
1851 // Note that we cannot do it before for fear of a fn like
1852 // fn getaddr(~ref x: ~uint) -> *uint {....}
1853 // (From test `run-pass/func-arg-ref-pattern.rs`)
1854 let arg_ty = node_id_type(bcx, pat.id);
1855 add_clean(bcx, llval, arg_ty);
1857 match simple_identifier(pat) {
1859 // Optimized path for `x: T` case. This just adopts
1860 // `llval` wholesale as the pointer for `x`, avoiding the
1861 // general logic which may copy out of `llval`.
1862 bcx.fcx.llargs.insert(pat.id, llval);
1866 // General path. Copy out the values that are used in the
1868 bcx = bind_irrefutable_pat(bcx, pat, llval, BindArgument);
1875 fn mk_binding_alloca(mut bcx: block,
1878 binding_mode: IrrefutablePatternBindingMode,
1879 populate: &fn(block, ty::t, ValueRef) -> block) -> block {
1880 let var_ty = node_id_type(bcx, p_id);
1881 let ident = ast_util::path_to_ident(path);
1882 let llval = alloc_ty(bcx, var_ty, bcx.ident(ident));
1883 bcx = populate(bcx, var_ty, llval);
1884 let llmap = match binding_mode {
1885 BindLocal => bcx.fcx.lllocals,
1886 BindArgument => bcx.fcx.llargs
1888 llmap.insert(p_id, llval);
1889 add_clean(bcx, llval, var_ty);
1893 fn bind_irrefutable_pat(bcx: block,
1896 binding_mode: IrrefutablePatternBindingMode)
1899 * A simple version of the pattern matching code that only handles
1900 * irrefutable patterns. This is used in let/argument patterns,
1901 * not in match statements. Unifying this code with the code above
1902 * sounds nice, but in practice it produces very inefficient code,
1903 * since the match code is so much more general. In most cases,
1904 * LLVM is able to optimize the code, but it causes longer compile
1905 * times and makes the generated code nigh impossible to read.
1908 * - bcx: starting basic block context
1909 * - pat: the irrefutable pattern being matched.
1910 * - val: a pointer to the value being matched. If pat matches a value
1911 * of type T, then this is a T*. If the value is moved from `pat`,
1912 * then `*pat` will be zeroed; otherwise, it's existing cleanup
1914 * - binding_mode: is this for an argument or a local variable?
1917 debug!("bind_irrefutable_pat(bcx=%s, pat=%s, binding_mode=%?)",
1919 pat_to_str(pat, bcx.sess().intr()),
1922 if bcx.sess().asm_comments() {
1923 add_comment(bcx, fmt!("bind_irrefutable_pat(pat=%s)",
1924 pat_to_str(pat, bcx.sess().intr())));
1927 let _indenter = indenter();
1929 let _icx = push_ctxt("alt::bind_irrefutable_pat");
1931 let tcx = bcx.tcx();
1932 let ccx = bcx.ccx();
1934 ast::pat_ident(pat_binding_mode, ref path, inner) => {
1935 if pat_is_binding(tcx.def_map, pat) {
1936 // Allocate the stack slot where the value of this
1937 // binding will live and place it into the appropriate
1939 bcx = mk_binding_alloca(
1940 bcx, pat.id, path, binding_mode,
1941 |bcx, variable_ty, llvariable_val| {
1942 match pat_binding_mode {
1943 ast::bind_infer => {
1944 // By value binding: move the value that `val`
1945 // points at into the binding's stack slot.
1946 let datum = Datum {val: val,
1948 mode: ByRef(ZeroMem)};
1949 datum.store_to(bcx, INIT, llvariable_val)
1952 ast::bind_by_ref(_) => {
1953 // By ref binding: the value of the variable
1954 // is the pointer `val` itself.
1955 Store(bcx, val, llvariable_val);
1962 for inner.iter().advance |&inner_pat| {
1963 bcx = bind_irrefutable_pat(bcx, inner_pat, val, binding_mode);
1966 ast::pat_enum(_, ref sub_pats) => {
1967 match bcx.tcx().def_map.find(&pat.id) {
1968 Some(&ast::def_variant(enum_id, var_id)) => {
1969 let repr = adt::represent_node(bcx, pat.id);
1970 let vinfo = ty::enum_variant_with_id(ccx.tcx,
1973 let args = extract_variant_args(bcx,
1977 for sub_pats.iter().advance |sub_pat| {
1978 for args.vals.iter().enumerate().advance |(i, argval)| {
1979 bcx = bind_irrefutable_pat(bcx, sub_pat[i],
1980 *argval, binding_mode);
1984 Some(&ast::def_fn(*)) |
1985 Some(&ast::def_struct(*)) => {
1988 // This is a unit-like struct. Nothing to do here.
1990 Some(ref elems) => {
1991 // This is the tuple struct case.
1992 let repr = adt::represent_node(bcx, pat.id);
1993 for elems.iter().enumerate().advance |(i, elem)| {
1994 let fldptr = adt::trans_field_ptr(bcx, repr,
1996 bcx = bind_irrefutable_pat(bcx, *elem,
1997 fldptr, binding_mode);
2002 Some(&ast::def_static(_, false)) => {
2005 // Nothing to do here.
2009 ast::pat_struct(_, ref fields, _) => {
2010 let tcx = bcx.tcx();
2011 let pat_ty = node_id_type(bcx, pat.id);
2012 let pat_repr = adt::represent_type(bcx.ccx(), pat_ty);
2013 do expr::with_field_tys(tcx, pat_ty, None) |discr, field_tys| {
2014 for fields.iter().advance |f| {
2015 let ix = ty::field_idx_strict(tcx, f.ident, field_tys);
2016 let fldptr = adt::trans_field_ptr(bcx, pat_repr, val,
2018 bcx = bind_irrefutable_pat(bcx, f.pat, fldptr, binding_mode);
2022 ast::pat_tup(ref elems) => {
2023 let repr = adt::represent_node(bcx, pat.id);
2024 for elems.iter().enumerate().advance |(i, elem)| {
2025 let fldptr = adt::trans_field_ptr(bcx, repr, val, 0, i);
2026 bcx = bind_irrefutable_pat(bcx, *elem, fldptr, binding_mode);
2029 ast::pat_box(inner) | ast::pat_uniq(inner) => {
2030 let pat_ty = node_id_type(bcx, pat.id);
2031 let llbox = Load(bcx, val);
2032 let unboxed = match ty::get(pat_ty).sty {
2033 ty::ty_uniq(*) if !ty::type_contents(bcx.tcx(), pat_ty).contains_managed() => llbox,
2034 _ => GEPi(bcx, llbox, [0u, abi::box_field_body])
2036 bcx = bind_irrefutable_pat(bcx, inner, unboxed, binding_mode);
2038 ast::pat_region(inner) => {
2039 let loaded_val = Load(bcx, val);
2040 bcx = bind_irrefutable_pat(bcx, inner, loaded_val, binding_mode);
2042 ast::pat_vec(*) => {
2043 bcx.tcx().sess.span_bug(
2045 fmt!("vector patterns are never irrefutable!"));
2047 ast::pat_wild | ast::pat_lit(_) | ast::pat_range(_, _) => ()
2052 fn simple_identifier<'a>(pat: &'a ast::pat) -> Option<&'a ast::Path> {
2054 ast::pat_ident(ast::bind_infer, ref path, None) => {