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.
11 //! # Compilation of match statements
13 //! I will endeavor to explain the code as best I can. I have only a loose
14 //! understanding of some parts of it.
18 //! The basic state of the code is maintained in an array `m` of `Match`
19 //! objects. Each `Match` describes some list of patterns, all of which must
20 //! match against the current list of values. If those patterns match, then
21 //! the arm listed in the match is the correct arm. A given arm may have
22 //! multiple corresponding match entries, one for each alternative that
23 //! remains. As we proceed these sets of matches are adjusted by the various
24 //! `enter_XXX()` functions, each of which adjusts the set of options given
25 //! some information about the value which has been matched.
27 //! So, initially, there is one value and N matches, each of which have one
28 //! constituent pattern. N here is usually the number of arms but may be
29 //! greater, if some arms have multiple alternatives. For example, here:
31 //! enum Foo { A, B(int), C(usize, usize) }
39 //! The value would be `foo`. There would be four matches, each of which
40 //! contains one pattern (and, in one case, a guard). We could collect the
41 //! various options and then compile the code for the case where `foo` is an
42 //! `A`, a `B`, and a `C`. When we generate the code for `C`, we would (1)
43 //! drop the two matches that do not match a `C` and (2) expand the other two
44 //! into two patterns each. In the first case, the two patterns would be `1`
45 //! and `2`, and the in the second case the _ pattern would be expanded into
46 //! `_` and `_`. The two values are of course the arguments to `C`.
48 //! Here is a quick guide to the various functions:
50 //! - `compile_submatch()`: The main workhouse. It takes a list of values and
51 //! a list of matches and finds the various possibilities that could occur.
53 //! - `enter_XXX()`: modifies the list of matches based on some information
54 //! about the value that has been matched. For example,
55 //! `enter_rec_or_struct()` adjusts the values given that a record or struct
56 //! has been matched. This is an infallible pattern, so *all* of the matches
57 //! must be either wildcards or record/struct patterns. `enter_opt()`
58 //! handles the fallible cases, and it is correspondingly more complex.
62 //! We store information about the bound variables for each arm as part of the
63 //! per-arm `ArmData` struct. There is a mapping from identifiers to
64 //! `BindingInfo` structs. These structs contain the mode/id/type of the
65 //! binding, but they also contain an LLVM value which points at an alloca
66 //! called `llmatch`. For by value bindings that are Copy, we also create
67 //! an extra alloca that we copy the matched value to so that any changes
68 //! we do to our copy is not reflected in the original and vice-versa.
69 //! We don't do this if it's a move since the original value can't be used
70 //! and thus allowing us to cheat in not creating an extra alloca.
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 //! Once a pattern is completely matched, and assuming that there is no guard
87 //! pattern, we will branch to a block that leads to the body itself. For any
88 //! by-value bindings, this block will first load the ptr from `llmatch` (the
89 //! one of type `D*`) and then load a second time to get the actual value (the
90 //! one of type `D`). For by ref bindings, the value of the local variable is
91 //! simply the first alloca.
93 //! So, for the example above, we would generate a setup kind of like this:
99 //! +--------------------------------------------+
100 //! | llmatch_c = (addr of first half of tuple) |
101 //! | llmatch_d = (addr of second half of tuple) |
102 //! +--------------------------------------------+
104 //! +--------------------------------------+
105 //! | *llbinding_d = **llmatch_d |
106 //! +--------------------------------------+
108 //! If there is a guard, the situation is slightly different, because we must
109 //! execute the guard code. Moreover, we need to do so once for each of the
110 //! alternatives that lead to the arm, because if the guard fails, they may
111 //! have different points from which to continue the search. Therefore, in that
112 //! case, we generate code that looks more like:
118 //! +-------------------------------------------+
119 //! | llmatch_c = (addr of first half of tuple) |
120 //! | llmatch_d = (addr of first half of tuple) |
121 //! +-------------------------------------------+
123 //! +-------------------------------------------------+
124 //! | *llbinding_d = **llmatch_d |
125 //! | check condition |
126 //! | if false { goto next case } |
127 //! | if true { goto body } |
128 //! +-------------------------------------------------+
130 //! The handling for the cleanups is a bit... sensitive. Basically, the body
131 //! is the one that invokes `add_clean()` for each binding. During the guard
132 //! evaluation, we add temporary cleanups and revoke them after the guard is
133 //! evaluated (it could fail, after all). Note that guards and moves are
134 //! just plain incompatible.
136 //! Some relevant helper functions that manage bindings:
137 //! - `create_bindings_map()`
138 //! - `insert_lllocals()`
141 //! ## Notes on vector pattern matching.
143 //! Vector pattern matching is surprisingly tricky. The problem is that
144 //! the structure of the vector isn't fully known, and slice matches
145 //! can be done on subparts of it.
147 //! The way that vector pattern matches are dealt with, then, is as
148 //! follows. First, we make the actual condition associated with a
149 //! vector pattern simply a vector length comparison. So the pattern
150 //! [1, .. x] gets the condition "vec len >= 1", and the pattern
151 //! [.. x] gets the condition "vec len >= 0". The problem here is that
152 //! having the condition "vec len >= 1" hold clearly does not mean that
153 //! only a pattern that has exactly that condition will match. This
154 //! means that it may well be the case that a condition holds, but none
155 //! of the patterns matching that condition match; to deal with this,
156 //! when doing vector length matches, we have match failures proceed to
157 //! the next condition to check.
159 //! There are a couple more subtleties to deal with. While the "actual"
160 //! condition associated with vector length tests is simply a test on
161 //! the vector length, the actual vec_len Opt entry contains more
162 //! information used to restrict which matches are associated with it.
163 //! So that all matches in a submatch are matching against the same
164 //! values from inside the vector, they are split up by how many
165 //! elements they match at the front and at the back of the vector. In
166 //! order to make sure that arms are properly checked in order, even
167 //! with the overmatching conditions, each vec_len Opt entry is
168 //! associated with a range of matches.
169 //! Consider the following:
171 //! match &[1, 2, 3] {
172 //! [1, 1, .. _] => 0,
173 //! [1, 2, 2, .. _] => 1,
174 //! [1, 2, 3, .. _] => 2,
175 //! [1, 2, .. _] => 3,
178 //! The proper arm to match is arm 2, but arms 0 and 3 both have the
179 //! condition "len >= 2". If arm 3 was lumped in with arm 0, then the
180 //! wrong branch would be taken. Instead, vec_len Opts are associated
181 //! with a contiguous range of matches that have the same "shape".
182 //! This is sort of ugly and requires a bunch of special handling of
185 pub use self::BranchKind
::*;
186 pub use self::OptResult
::*;
187 pub use self::TransBindingMode
::*;
189 use self::FailureHandler
::*;
192 use llvm
::{ValueRef, BasicBlockRef}
;
193 use middle
::check_match
::StaticInliner
;
194 use middle
::check_match
;
195 use middle
::const_eval
;
196 use middle
::def
::{self, DefMap}
;
197 use middle
::expr_use_visitor
as euv
;
198 use middle
::lang_items
::StrEqFnLangItem
;
199 use middle
::mem_categorization
as mc
;
200 use middle
::pat_util
::*;
203 use trans
::build
::{AddCase, And, Br, CondBr, GEPi, InBoundsGEP, Load, PointerCast}
;
204 use trans
::build
::{Not, Store, Sub, add_comment}
;
207 use trans
::cleanup
::{self, CleanupMethods}
;
208 use trans
::common
::*;
211 use trans
::debuginfo
::{self, DebugLoc, ToDebugLoc}
;
212 use trans
::expr
::{self, Dest}
;
213 use trans
::monomorphize
;
216 use middle
::ty
::{self, Ty}
;
217 use session
::config
::{NoDebugInfo, FullDebugInfo}
;
218 use util
::common
::indenter
;
219 use util
::nodemap
::FnvHashMap
;
223 use std
::cmp
::Ordering
;
227 use syntax
::ast
::{DUMMY_NODE_ID, NodeId}
;
228 use syntax
::codemap
::Span
;
229 use syntax
::fold
::Folder
;
232 #[derive(Copy, Clone, Debug)]
233 struct ConstantExpr
<'a
>(&'a ast
::Expr
);
235 impl<'a
> ConstantExpr
<'a
> {
236 fn eq(self, other
: ConstantExpr
<'a
>, tcx
: &ty
::ctxt
) -> bool
{
237 match const_eval
::compare_lit_exprs(tcx
, self.0, other
.0, None
,
238 |id
| {ty::node_id_item_substs(tcx, id).substs}
) {
239 Some(result
) => result
== Ordering
::Equal
,
240 None
=> panic
!("compare_list_exprs: type mismatch"),
245 // An option identifying a branch (either a literal, an enum variant or a range)
248 ConstantValue(ConstantExpr
<'a
>, DebugLoc
),
249 ConstantRange(ConstantExpr
<'a
>, ConstantExpr
<'a
>, DebugLoc
),
250 Variant(ty
::Disr
, Rc
<adt
::Repr
<'tcx
>>, ast
::DefId
, DebugLoc
),
251 SliceLengthEqual(usize, DebugLoc
),
252 SliceLengthGreaterOrEqual(/* prefix length */ usize,
253 /* suffix length */ usize,
257 impl<'a
, 'tcx
> Opt
<'a
, 'tcx
> {
258 fn eq(&self, other
: &Opt
<'a
, 'tcx
>, tcx
: &ty
::ctxt
<'tcx
>) -> bool
{
259 match (self, other
) {
260 (&ConstantValue(a
, _
), &ConstantValue(b
, _
)) => a
.eq(b
, tcx
),
261 (&ConstantRange(a1
, a2
, _
), &ConstantRange(b1
, b2
, _
)) => {
262 a1
.eq(b1
, tcx
) && a2
.eq(b2
, tcx
)
264 (&Variant(a_disr
, ref a_repr
, a_def
, _
),
265 &Variant(b_disr
, ref b_repr
, b_def
, _
)) => {
266 a_disr
== b_disr
&& *a_repr
== *b_repr
&& a_def
== b_def
268 (&SliceLengthEqual(a
, _
), &SliceLengthEqual(b
, _
)) => a
== b
,
269 (&SliceLengthGreaterOrEqual(a1
, a2
, _
),
270 &SliceLengthGreaterOrEqual(b1
, b2
, _
)) => {
277 fn trans
<'blk
>(&self, mut bcx
: Block
<'blk
, 'tcx
>) -> OptResult
<'blk
, 'tcx
> {
278 let _icx
= push_ctxt("match::trans_opt");
281 ConstantValue(ConstantExpr(lit_expr
), _
) => {
282 let lit_ty
= ty
::node_id_to_type(bcx
.tcx(), lit_expr
.id
);
283 let (llval
, _
) = consts
::const_expr(ccx
, &*lit_expr
, bcx
.fcx
.param_substs
, None
);
284 let lit_datum
= immediate_rvalue(llval
, lit_ty
);
285 let lit_datum
= unpack_datum
!(bcx
, lit_datum
.to_appropriate_datum(bcx
));
286 SingleResult(Result
::new(bcx
, lit_datum
.val
))
288 ConstantRange(ConstantExpr(ref l1
), ConstantExpr(ref l2
), _
) => {
289 let (l1
, _
) = consts
::const_expr(ccx
, &**l1
, bcx
.fcx
.param_substs
, None
);
290 let (l2
, _
) = consts
::const_expr(ccx
, &**l2
, bcx
.fcx
.param_substs
, None
);
291 RangeResult(Result
::new(bcx
, l1
), Result
::new(bcx
, l2
))
293 Variant(disr_val
, ref repr
, _
, _
) => {
294 adt
::trans_case(bcx
, &**repr
, disr_val
)
296 SliceLengthEqual(length
, _
) => {
297 SingleResult(Result
::new(bcx
, C_uint(ccx
, length
)))
299 SliceLengthGreaterOrEqual(prefix
, suffix
, _
) => {
300 LowerBound(Result
::new(bcx
, C_uint(ccx
, prefix
+ suffix
)))
305 fn debug_loc(&self) -> DebugLoc
{
307 ConstantValue(_
,debug_loc
) |
308 ConstantRange(_
, _
, debug_loc
) |
309 Variant(_
, _
, _
, debug_loc
) |
310 SliceLengthEqual(_
, debug_loc
) |
311 SliceLengthGreaterOrEqual(_
, _
, debug_loc
) => debug_loc
316 #[derive(Copy, Clone, PartialEq)]
317 pub enum BranchKind
{
325 pub enum OptResult
<'blk
, 'tcx
: 'blk
> {
326 SingleResult(Result
<'blk
, 'tcx
>),
327 RangeResult(Result
<'blk
, 'tcx
>, Result
<'blk
, 'tcx
>),
328 LowerBound(Result
<'blk
, 'tcx
>)
331 #[derive(Clone, Copy, PartialEq)]
332 pub enum TransBindingMode
{
333 TrByCopy(/* llbinding */ ValueRef
),
338 /// Information about a pattern binding:
339 /// - `llmatch` is a pointer to a stack slot. The stack slot contains a
340 /// pointer into the value being matched. Hence, llmatch has type `T**`
341 /// where `T` is the value being matched.
342 /// - `trmode` is the trans binding mode
343 /// - `id` is the node id of the binding
344 /// - `ty` is the Rust type of the binding
345 #[derive(Clone, Copy)]
346 pub struct BindingInfo
<'tcx
> {
347 pub llmatch
: ValueRef
,
348 pub trmode
: TransBindingMode
,
354 type BindingsMap
<'tcx
> = FnvHashMap
<ast
::Ident
, BindingInfo
<'tcx
>>;
356 struct ArmData
<'p
, 'blk
, 'tcx
: 'blk
> {
357 bodycx
: Block
<'blk
, 'tcx
>,
359 bindings_map
: BindingsMap
<'tcx
>
362 /// Info about Match.
363 /// If all `pats` are matched then arm `data` will be executed.
364 /// As we proceed `bound_ptrs` are filled with pointers to values to be bound,
365 /// these pointers are stored in llmatch variables just before executing `data` arm.
366 struct Match
<'a
, 'p
: 'a
, 'blk
: 'a
, 'tcx
: 'blk
> {
367 pats
: Vec
<&'p ast
::Pat
>,
368 data
: &'a ArmData
<'p
, 'blk
, 'tcx
>,
369 bound_ptrs
: Vec
<(ast
::Ident
, ValueRef
)>,
370 // Thread along renamings done by the check_match::StaticInliner, so we can
371 // map back to original NodeIds
372 pat_renaming_map
: Option
<&'a FnvHashMap
<(NodeId
, Span
), NodeId
>>
375 impl<'a
, 'p
, 'blk
, 'tcx
> fmt
::Debug
for Match
<'a
, 'p
, 'blk
, 'tcx
> {
376 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
377 if ppaux
::verbose() {
378 // for many programs, this just take too long to serialize
379 write
!(f
, "{:?}", self.pats
)
381 write
!(f
, "{} pats", self.pats
.len())
386 fn has_nested_bindings(m
: &[Match
], col
: usize) -> bool
{
388 match br
.pats
[col
].node
{
389 ast
::PatIdent(_
, _
, Some(_
)) => return true,
396 fn expand_nested_bindings
<'a
, 'p
, 'blk
, 'tcx
>(bcx
: Block
<'blk
, 'tcx
>,
397 m
: &[Match
<'a
, 'p
, 'blk
, 'tcx
>],
400 -> Vec
<Match
<'a
, 'p
, 'blk
, 'tcx
>> {
401 debug
!("expand_nested_bindings(bcx={}, m={:?}, col={}, val={})",
405 bcx
.val_to_string(val
));
406 let _indenter
= indenter();
409 let mut bound_ptrs
= br
.bound_ptrs
.clone();
410 let mut pat
= br
.pats
[col
];
412 pat
= match pat
.node
{
413 ast
::PatIdent(_
, ref path
, Some(ref inner
)) => {
414 bound_ptrs
.push((path
.node
, val
));
421 let mut pats
= br
.pats
.clone();
426 bound_ptrs
: bound_ptrs
,
427 pat_renaming_map
: br
.pat_renaming_map
,
432 fn enter_match
<'a
, 'b
, 'p
, 'blk
, 'tcx
, F
>(bcx
: Block
<'blk
, 'tcx
>,
434 m
: &[Match
<'a
, 'p
, 'blk
, 'tcx
>],
438 -> Vec
<Match
<'a
, 'p
, 'blk
, 'tcx
>> where
439 F
: FnMut(&[&'p ast
::Pat
]) -> Option
<Vec
<&'p ast
::Pat
>>,
441 debug
!("enter_match(bcx={}, m={:?}, col={}, val={})",
445 bcx
.val_to_string(val
));
446 let _indenter
= indenter();
448 m
.iter().filter_map(|br
| {
449 e(&br
.pats
).map(|pats
| {
450 let this
= br
.pats
[col
];
451 let mut bound_ptrs
= br
.bound_ptrs
.clone();
453 ast
::PatIdent(_
, ref path
, None
) => {
454 if pat_is_binding(dm
, &*this
) {
455 bound_ptrs
.push((path
.node
, val
));
458 ast
::PatVec(ref before
, Some(ref slice
), ref after
) => {
459 if let ast
::PatIdent(_
, ref path
, None
) = slice
.node
{
460 let subslice_val
= bind_subslice_pat(
462 before
.len(), after
.len());
463 bound_ptrs
.push((path
.node
, subslice_val
));
471 bound_ptrs
: bound_ptrs
,
472 pat_renaming_map
: br
.pat_renaming_map
,
478 fn enter_default
<'a
, 'p
, 'blk
, 'tcx
>(bcx
: Block
<'blk
, 'tcx
>,
480 m
: &[Match
<'a
, 'p
, 'blk
, 'tcx
>],
483 -> Vec
<Match
<'a
, 'p
, 'blk
, 'tcx
>> {
484 debug
!("enter_default(bcx={}, m={:?}, col={}, val={})",
488 bcx
.val_to_string(val
));
489 let _indenter
= indenter();
491 // Collect all of the matches that can match against anything.
492 enter_match(bcx
, dm
, m
, col
, val
, |pats
| {
493 if pat_is_binding_or_wild(dm
, &*pats
[col
]) {
494 let mut r
= pats
[..col
].to_vec();
495 r
.push_all(&pats
[col
+ 1..]);
503 // <pcwalton> nmatsakis: what does enter_opt do?
504 // <pcwalton> in trans/match
505 // <pcwalton> trans/match.rs is like stumbling around in a dark cave
506 // <nmatsakis> pcwalton: the enter family of functions adjust the set of
507 // patterns as needed
508 // <nmatsakis> yeah, at some point I kind of achieved some level of
510 // <nmatsakis> anyhow, they adjust the patterns given that something of that
511 // kind has been found
512 // <nmatsakis> pcwalton: ok, right, so enter_XXX() adjusts the patterns, as I
514 // <nmatsakis> enter_match() kind of embodies the generic code
515 // <nmatsakis> it is provided with a function that tests each pattern to see
516 // if it might possibly apply and so forth
517 // <nmatsakis> so, if you have a pattern like {a: _, b: _, _} and one like _
518 // <nmatsakis> then _ would be expanded to (_, _)
519 // <nmatsakis> one spot for each of the sub-patterns
520 // <nmatsakis> enter_opt() is one of the more complex; it covers the fallible
522 // <nmatsakis> enter_rec_or_struct() or enter_tuple() are simpler, since they
523 // are infallible patterns
524 // <nmatsakis> so all patterns must either be records (resp. tuples) or
527 /// The above is now outdated in that enter_match() now takes a function that
528 /// takes the complete row of patterns rather than just the first one.
529 /// Also, most of the enter_() family functions have been unified with
530 /// the check_match specialization step.
531 fn enter_opt
<'a
, 'p
, 'blk
, 'tcx
>(
532 bcx
: Block
<'blk
, 'tcx
>,
535 m
: &[Match
<'a
, 'p
, 'blk
, 'tcx
>],
540 -> Vec
<Match
<'a
, 'p
, 'blk
, 'tcx
>> {
541 debug
!("enter_opt(bcx={}, m={:?}, opt={:?}, col={}, val={})",
546 bcx
.val_to_string(val
));
547 let _indenter
= indenter();
549 let ctor
= match opt
{
550 &ConstantValue(ConstantExpr(expr
), _
) => check_match
::ConstantValue(
551 const_eval
::eval_const_expr(bcx
.tcx(), &*expr
)
553 &ConstantRange(ConstantExpr(lo
), ConstantExpr(hi
), _
) => check_match
::ConstantRange(
554 const_eval
::eval_const_expr(bcx
.tcx(), &*lo
),
555 const_eval
::eval_const_expr(bcx
.tcx(), &*hi
)
557 &SliceLengthEqual(n
, _
) =>
558 check_match
::Slice(n
),
559 &SliceLengthGreaterOrEqual(before
, after
, _
) =>
560 check_match
::SliceWithSubslice(before
, after
),
561 &Variant(_
, _
, def_id
, _
) =>
562 check_match
::Constructor
::Variant(def_id
)
565 let param_env
= ty
::empty_parameter_environment(bcx
.tcx());
566 let mcx
= check_match
::MatchCheckCtxt
{
568 param_env
: param_env
,
570 enter_match(bcx
, dm
, m
, col
, val
, |pats
|
571 check_match
::specialize(&mcx
, &pats
[..], &ctor
, col
, variant_size
)
575 // Returns the options in one column of matches. An option is something that
576 // needs to be conditionally matched at runtime; for example, the discriminant
577 // on a set of enum variants or a literal.
578 fn get_branches
<'a
, 'p
, 'blk
, 'tcx
>(bcx
: Block
<'blk
, 'tcx
>,
579 m
: &[Match
<'a
, 'p
, 'blk
, 'tcx
>],
581 -> Vec
<Opt
<'p
, 'tcx
>> {
584 let mut found
: Vec
<Opt
> = vec
![];
586 let cur
= br
.pats
[col
];
587 let debug_loc
= match br
.pat_renaming_map
{
588 Some(pat_renaming_map
) => {
589 match pat_renaming_map
.get(&(cur
.id
, cur
.span
)) {
590 Some(&id
) => DebugLoc
::At(id
, cur
.span
),
591 None
=> DebugLoc
::At(cur
.id
, cur
.span
),
594 None
=> DebugLoc
::None
597 let opt
= match cur
.node
{
598 ast
::PatLit(ref l
) => {
599 ConstantValue(ConstantExpr(&**l
), debug_loc
)
601 ast
::PatIdent(..) | ast
::PatEnum(..) | ast
::PatStruct(..) => {
602 // This is either an enum variant or a variable binding.
603 let opt_def
= tcx
.def_map
.borrow().get(&cur
.id
).map(|d
| d
.full_def());
605 Some(def
::DefVariant(enum_id
, var_id
, _
)) => {
606 let variant
= ty
::enum_variant_with_id(tcx
, enum_id
, var_id
);
607 Variant(variant
.disr_val
,
608 adt
::represent_node(bcx
, cur
.id
),
615 ast
::PatRange(ref l1
, ref l2
) => {
616 ConstantRange(ConstantExpr(&**l1
), ConstantExpr(&**l2
), debug_loc
)
618 ast
::PatVec(ref before
, None
, ref after
) => {
619 SliceLengthEqual(before
.len() + after
.len(), debug_loc
)
621 ast
::PatVec(ref before
, Some(_
), ref after
) => {
622 SliceLengthGreaterOrEqual(before
.len(), after
.len(), debug_loc
)
627 if !found
.iter().any(|x
| x
.eq(&opt
, tcx
)) {
634 struct ExtractedBlock
<'blk
, 'tcx
: 'blk
> {
636 bcx
: Block
<'blk
, 'tcx
>,
639 fn extract_variant_args
<'blk
, 'tcx
>(bcx
: Block
<'blk
, 'tcx
>,
640 repr
: &adt
::Repr
<'tcx
>,
643 -> ExtractedBlock
<'blk
, 'tcx
> {
644 let _icx
= push_ctxt("match::extract_variant_args");
645 let args
= (0..adt
::num_args(repr
, disr_val
)).map(|i
| {
646 adt
::trans_field_ptr(bcx
, repr
, val
, disr_val
, i
)
649 ExtractedBlock { vals: args, bcx: bcx }
652 /// Helper for converting from the ValueRef that we pass around in the match code, which is always
653 /// an lvalue, into a Datum. Eventually we should just pass around a Datum and be done with it.
654 fn match_datum
<'tcx
>(val
: ValueRef
, left_ty
: Ty
<'tcx
>) -> Datum
<'tcx
, Lvalue
> {
655 Datum
::new(val
, left_ty
, Lvalue
)
658 fn bind_subslice_pat(bcx
: Block
,
662 offset_right
: usize) -> ValueRef
{
663 let _icx
= push_ctxt("match::bind_subslice_pat");
664 let vec_ty
= node_id_type(bcx
, pat_id
);
665 let unit_ty
= ty
::sequence_element_type(bcx
.tcx(), ty
::type_content(vec_ty
));
666 let vec_datum
= match_datum(val
, vec_ty
);
667 let (base
, len
) = vec_datum
.get_vec_base_and_len(bcx
);
669 let slice_begin
= InBoundsGEP(bcx
, base
, &[C_uint(bcx
.ccx(), offset_left
)]);
670 let slice_len_offset
= C_uint(bcx
.ccx(), offset_left
+ offset_right
);
671 let slice_len
= Sub(bcx
, len
, slice_len_offset
, DebugLoc
::None
);
672 let slice_ty
= ty
::mk_slice(bcx
.tcx(),
673 bcx
.tcx().mk_region(ty
::ReStatic
),
674 ty
::mt {ty: unit_ty, mutbl: ast::MutImmutable}
);
675 let scratch
= rvalue_scratch_datum(bcx
, slice_ty
, "");
676 Store(bcx
, slice_begin
,
677 GEPi(bcx
, scratch
.val
, &[0, abi
::FAT_PTR_ADDR
]));
678 Store(bcx
, slice_len
, GEPi(bcx
, scratch
.val
, &[0, abi
::FAT_PTR_EXTRA
]));
682 fn extract_vec_elems
<'blk
, 'tcx
>(bcx
: Block
<'blk
, 'tcx
>,
687 -> ExtractedBlock
<'blk
, 'tcx
> {
688 let _icx
= push_ctxt("match::extract_vec_elems");
689 let vec_datum
= match_datum(val
, left_ty
);
690 let (base
, len
) = vec_datum
.get_vec_base_and_len(bcx
);
691 let mut elems
= vec
![];
692 elems
.extend((0..before
).map(|i
| GEPi(bcx
, base
, &[i
])));
693 elems
.extend((0..after
).rev().map(|i
| {
694 InBoundsGEP(bcx
, base
, &[
695 Sub(bcx
, len
, C_uint(bcx
.ccx(), i
+ 1), DebugLoc
::None
)
698 ExtractedBlock { vals: elems, bcx: bcx }
701 // Macro for deciding whether any of the remaining matches fit a given kind of
702 // pattern. Note that, because the macro is well-typed, either ALL of the
703 // matches should fit that sort of pattern or NONE (however, some of the
704 // matches may be wildcards like _ or identifiers).
705 macro_rules
! any_pat
{
706 ($m
:expr
, $col
:expr
, $pattern
:pat
) => (
707 ($m
).iter().any(|br
| {
708 match br
.pats
[$col
].node
{
716 fn any_uniq_pat(m
: &[Match
], col
: usize) -> bool
{
717 any_pat
!(m
, col
, ast
::PatBox(_
))
720 fn any_region_pat(m
: &[Match
], col
: usize) -> bool
{
721 any_pat
!(m
, col
, ast
::PatRegion(..))
724 fn any_irrefutable_adt_pat(tcx
: &ty
::ctxt
, m
: &[Match
], col
: usize) -> bool
{
726 let pat
= br
.pats
[col
];
728 ast
::PatTup(_
) => true,
729 ast
::PatStruct(..) => {
730 match tcx
.def_map
.borrow().get(&pat
.id
).map(|d
| d
.full_def()) {
731 Some(def
::DefVariant(..)) => false,
735 ast
::PatEnum(..) | ast
::PatIdent(_
, _
, None
) => {
736 match tcx
.def_map
.borrow().get(&pat
.id
).map(|d
| d
.full_def()) {
737 Some(def
::DefStruct(..)) => true,
746 /// What to do when the pattern match fails.
747 enum FailureHandler
{
749 JumpToBasicBlock(BasicBlockRef
),
753 impl FailureHandler
{
754 fn is_fallible(&self) -> bool
{
761 fn is_infallible(&self) -> bool
{
765 fn handle_fail(&self, bcx
: Block
) {
768 panic
!("attempted to panic in a non-panicking panic handler!"),
769 JumpToBasicBlock(basic_block
) =>
770 Br(bcx
, basic_block
, DebugLoc
::None
),
772 build
::Unreachable(bcx
)
777 fn pick_column_to_specialize(def_map
: &DefMap
, m
: &[Match
]) -> Option
<usize> {
778 fn pat_score(def_map
: &DefMap
, pat
: &ast
::Pat
) -> usize {
780 ast
::PatIdent(_
, _
, Some(ref inner
)) => pat_score(def_map
, &**inner
),
781 _
if pat_is_refutable(def_map
, pat
) => 1,
786 let column_score
= |m
: &[Match
], col
: usize| -> usize {
787 let total_score
= m
.iter()
788 .map(|row
| row
.pats
[col
])
789 .map(|pat
| pat_score(def_map
, pat
))
792 // Irrefutable columns always go first, they'd only be duplicated in the branches.
793 if total_score
== 0 {
800 let column_contains_any_nonwild_patterns
= |&col
: &usize| -> bool
{
801 m
.iter().any(|row
| match row
.pats
[col
].node
{
802 ast
::PatWild(_
) => false,
808 .filter(column_contains_any_nonwild_patterns
)
809 .map(|col
| (col
, column_score(m
, col
)))
810 .max_by(|&(_
, score
)| score
)
814 // Compiles a comparison between two things.
815 fn compare_values
<'blk
, 'tcx
>(cx
: Block
<'blk
, 'tcx
>,
820 -> Result
<'blk
, 'tcx
> {
821 fn compare_str
<'blk
, 'tcx
>(cx
: Block
<'blk
, 'tcx
>,
826 -> Result
<'blk
, 'tcx
> {
827 let did
= langcall(cx
,
829 &format
!("comparison of `{}`", rhs_t
),
831 let lhs_data
= Load(cx
, expr
::get_dataptr(cx
, lhs
));
832 let lhs_len
= Load(cx
, expr
::get_len(cx
, lhs
));
833 let rhs_data
= Load(cx
, expr
::get_dataptr(cx
, rhs
));
834 let rhs_len
= Load(cx
, expr
::get_len(cx
, rhs
));
835 callee
::trans_lang_call(cx
, did
, &[lhs_data
, lhs_len
, rhs_data
, rhs_len
], None
, debug_loc
)
838 let _icx
= push_ctxt("compare_values");
839 if ty
::type_is_scalar(rhs_t
) {
840 let cmp
= compare_scalar_types(cx
, lhs
, rhs
, rhs_t
, ast
::BiEq
, debug_loc
);
841 return Result
::new(cx
, cmp
);
845 ty
::TyRef(_
, mt
) => match mt
.ty
.sty
{
846 ty
::TyStr
=> compare_str(cx
, lhs
, rhs
, rhs_t
, debug_loc
),
847 ty
::TyArray(ty
, _
) | ty
::TySlice(ty
) => match ty
.sty
{
848 ty
::TyUint(ast
::TyU8
) => {
849 // NOTE: cast &[u8] and &[u8; N] to &str and abuse the str_eq lang item,
850 // which calls memcmp().
851 let pat_len
= val_ty(rhs
).element_type().array_length();
852 let ty_str_slice
= ty
::mk_str_slice(cx
.tcx(),
853 cx
.tcx().mk_region(ty
::ReStatic
),
856 let rhs_str
= alloc_ty(cx
, ty_str_slice
, "rhs_str");
857 Store(cx
, GEPi(cx
, rhs
, &[0, 0]), expr
::get_dataptr(cx
, rhs_str
));
858 Store(cx
, C_uint(cx
.ccx(), pat_len
), expr
::get_len(cx
, rhs_str
));
861 if val_ty(lhs
) == val_ty(rhs
) {
862 // Both the discriminant and the pattern are thin pointers
863 lhs_str
= alloc_ty(cx
, ty_str_slice
, "lhs_str");
864 Store(cx
, GEPi(cx
, lhs
, &[0, 0]), expr
::get_dataptr(cx
, lhs_str
));
865 Store(cx
, C_uint(cx
.ccx(), pat_len
), expr
::get_len(cx
, lhs_str
));
868 // The discriminant is a fat pointer
869 let llty_str_slice
= type_of
::type_of(cx
.ccx(), ty_str_slice
).ptr_to();
870 lhs_str
= PointerCast(cx
, lhs
, llty_str_slice
);
873 compare_str(cx
, lhs_str
, rhs_str
, rhs_t
, debug_loc
)
875 _
=> cx
.sess().bug("only byte strings supported in compare_values"),
877 _
=> cx
.sess().bug("only string and byte strings supported in compare_values"),
879 _
=> cx
.sess().bug("only scalars, byte strings, and strings supported in compare_values"),
883 /// For each binding in `data.bindings_map`, adds an appropriate entry into the `fcx.lllocals` map
884 fn insert_lllocals
<'blk
, 'tcx
>(mut bcx
: Block
<'blk
, 'tcx
>,
885 bindings_map
: &BindingsMap
<'tcx
>,
886 cs
: Option
<cleanup
::ScopeId
>)
887 -> Block
<'blk
, 'tcx
> {
888 for (&ident
, &binding_info
) in bindings_map
{
889 let llval
= match binding_info
.trmode
{
890 // By value mut binding for a copy type: load from the ptr
891 // into the matched value and copy to our alloca
892 TrByCopy(llbinding
) => {
893 let llval
= Load(bcx
, binding_info
.llmatch
);
894 let datum
= Datum
::new(llval
, binding_info
.ty
, Lvalue
);
895 call_lifetime_start(bcx
, llbinding
);
896 bcx
= datum
.store_to(bcx
, llbinding
);
897 if let Some(cs
) = cs
{
898 bcx
.fcx
.schedule_lifetime_end(cs
, llbinding
);
904 // By value move bindings: load from the ptr into the matched value
905 TrByMove
=> Load(bcx
, binding_info
.llmatch
),
907 // By ref binding: use the ptr into the matched value
908 TrByRef
=> binding_info
.llmatch
911 let datum
= Datum
::new(llval
, binding_info
.ty
, Lvalue
);
912 if let Some(cs
) = cs
{
913 bcx
.fcx
.schedule_lifetime_end(cs
, binding_info
.llmatch
);
914 bcx
.fcx
.schedule_drop_and_fill_mem(cs
, llval
, binding_info
.ty
);
917 debug
!("binding {} to {}", binding_info
.id
, bcx
.val_to_string(llval
));
918 bcx
.fcx
.lllocals
.borrow_mut().insert(binding_info
.id
, datum
);
919 debuginfo
::create_match_binding_metadata(bcx
, ident
.name
, binding_info
);
924 fn compile_guard
<'a
, 'p
, 'blk
, 'tcx
>(bcx
: Block
<'blk
, 'tcx
>,
925 guard_expr
: &ast
::Expr
,
926 data
: &ArmData
<'p
, 'blk
, 'tcx
>,
927 m
: &[Match
<'a
, 'p
, 'blk
, 'tcx
>],
929 chk
: &FailureHandler
,
930 has_genuine_default
: bool
)
931 -> Block
<'blk
, 'tcx
> {
932 debug
!("compile_guard(bcx={}, guard_expr={:?}, m={:?}, vals=[{}])",
936 vals
.iter().map(|v
| bcx
.val_to_string(*v
)).collect
::<Vec
<_
>>().connect(", "));
937 let _indenter
= indenter();
939 let mut bcx
= insert_lllocals(bcx
, &data
.bindings_map
, None
);
941 let val
= unpack_datum
!(bcx
, expr
::trans(bcx
, guard_expr
));
942 let val
= val
.to_llbool(bcx
);
944 for (_
, &binding_info
) in &data
.bindings_map
{
945 if let TrByCopy(llbinding
) = binding_info
.trmode
{
946 call_lifetime_end(bcx
, llbinding
);
950 for (_
, &binding_info
) in &data
.bindings_map
{
951 bcx
.fcx
.lllocals
.borrow_mut().remove(&binding_info
.id
);
954 with_cond(bcx
, Not(bcx
, val
, guard_expr
.debug_loc()), |bcx
| {
955 for (_
, &binding_info
) in &data
.bindings_map
{
956 call_lifetime_end(bcx
, binding_info
.llmatch
);
959 // If the default arm is the only one left, move on to the next
960 // condition explicitly rather than (possibly) falling back to
962 &JumpToBasicBlock(_
) if m
.len() == 1 && has_genuine_default
=> {
963 chk
.handle_fail(bcx
);
966 compile_submatch(bcx
, m
, vals
, chk
, has_genuine_default
);
973 fn compile_submatch
<'a
, 'p
, 'blk
, 'tcx
>(bcx
: Block
<'blk
, 'tcx
>,
974 m
: &[Match
<'a
, 'p
, 'blk
, 'tcx
>],
976 chk
: &FailureHandler
,
977 has_genuine_default
: bool
) {
978 debug
!("compile_submatch(bcx={}, m={:?}, vals=[{}])",
981 vals
.iter().map(|v
| bcx
.val_to_string(*v
)).collect
::<Vec
<_
>>().connect(", "));
982 let _indenter
= indenter();
983 let _icx
= push_ctxt("match::compile_submatch");
986 if chk
.is_fallible() {
987 chk
.handle_fail(bcx
);
993 let def_map
= &tcx
.def_map
;
994 match pick_column_to_specialize(def_map
, m
) {
997 if has_nested_bindings(m
, col
) {
998 let expanded
= expand_nested_bindings(bcx
, m
, col
, val
);
999 compile_submatch_continue(bcx
,
1005 has_genuine_default
)
1007 compile_submatch_continue(bcx
, m
, vals
, chk
, col
, val
, has_genuine_default
)
1011 let data
= &m
[0].data
;
1012 for &(ref ident
, ref value_ptr
) in &m
[0].bound_ptrs
{
1013 let binfo
= *data
.bindings_map
.get(ident
).unwrap();
1014 call_lifetime_start(bcx
, binfo
.llmatch
);
1015 if binfo
.trmode
== TrByRef
&& type_is_fat_ptr(bcx
.tcx(), binfo
.ty
) {
1016 expr
::copy_fat_ptr(bcx
, *value_ptr
, binfo
.llmatch
);
1019 Store(bcx
, *value_ptr
, binfo
.llmatch
);
1022 match data
.arm
.guard
{
1023 Some(ref guard_expr
) => {
1024 bcx
= compile_guard(bcx
,
1030 has_genuine_default
);
1034 Br(bcx
, data
.bodycx
.llbb
, DebugLoc
::None
);
1039 fn compile_submatch_continue
<'a
, 'p
, 'blk
, 'tcx
>(mut bcx
: Block
<'blk
, 'tcx
>,
1040 m
: &[Match
<'a
, 'p
, 'blk
, 'tcx
>],
1042 chk
: &FailureHandler
,
1045 has_genuine_default
: bool
) {
1047 let tcx
= bcx
.tcx();
1048 let dm
= &tcx
.def_map
;
1050 let mut vals_left
= vals
[0..col
].to_vec();
1051 vals_left
.push_all(&vals
[col
+ 1..]);
1052 let ccx
= bcx
.fcx
.ccx
;
1054 // Find a real id (we're adding placeholder wildcard patterns, but
1055 // each column is guaranteed to have at least one real pattern)
1056 let pat_id
= m
.iter().map(|br
| br
.pats
[col
].id
)
1057 .find(|&id
| id
!= DUMMY_NODE_ID
)
1058 .unwrap_or(DUMMY_NODE_ID
);
1060 let left_ty
= if pat_id
== DUMMY_NODE_ID
{
1063 node_id_type(bcx
, pat_id
)
1066 let mcx
= check_match
::MatchCheckCtxt
{
1068 param_env
: ty
::empty_parameter_environment(bcx
.tcx()),
1070 let adt_vals
= if any_irrefutable_adt_pat(bcx
.tcx(), m
, col
) {
1071 let repr
= adt
::represent_type(bcx
.ccx(), left_ty
);
1072 let arg_count
= adt
::num_args(&*repr
, 0);
1073 let (arg_count
, struct_val
) = if type_is_sized(bcx
.tcx(), left_ty
) {
1076 // For an unsized ADT (i.e. DST struct), we need to treat
1077 // the last field specially: instead of simply passing a
1078 // ValueRef pointing to that field, as with all the others,
1079 // we skip it and instead construct a 'fat ptr' below.
1080 (arg_count
- 1, Load(bcx
, expr
::get_dataptr(bcx
, val
)))
1082 let mut field_vals
: Vec
<ValueRef
> = (0..arg_count
).map(|ix
|
1083 adt
::trans_field_ptr(bcx
, &*repr
, struct_val
, 0, ix
)
1087 ty
::TyStruct(def_id
, substs
) if !type_is_sized(bcx
.tcx(), left_ty
) => {
1088 // The last field is technically unsized but
1089 // since we can only ever match that field behind
1090 // a reference we construct a fat ptr here.
1091 let fields
= ty
::lookup_struct_fields(bcx
.tcx(), def_id
);
1092 let unsized_ty
= fields
.iter().last().map(|field
| {
1093 let fty
= ty
::lookup_field_type(bcx
.tcx(), def_id
, field
.id
, substs
);
1094 monomorphize
::normalize_associated_type(bcx
.tcx(), &fty
)
1096 let llty
= type_of
::type_of(bcx
.ccx(), unsized_ty
);
1097 let scratch
= alloca_no_lifetime(bcx
, llty
, "__struct_field_fat_ptr");
1098 let data
= adt
::trans_field_ptr(bcx
, &*repr
, struct_val
, 0, arg_count
);
1099 let len
= Load(bcx
, expr
::get_len(bcx
, val
));
1100 Store(bcx
, data
, expr
::get_dataptr(bcx
, scratch
));
1101 Store(bcx
, len
, expr
::get_len(bcx
, scratch
));
1102 field_vals
.push(scratch
);
1107 } else if any_uniq_pat(m
, col
) || any_region_pat(m
, col
) {
1108 Some(vec
!(Load(bcx
, val
)))
1111 ty
::TyArray(_
, n
) => {
1112 let args
= extract_vec_elems(bcx
, left_ty
, n
, 0, val
);
1119 Some(field_vals
) => {
1120 let pats
= enter_match(bcx
, dm
, m
, col
, val
, |pats
|
1121 check_match
::specialize(&mcx
, pats
,
1122 &check_match
::Single
, col
,
1125 let mut vals
= field_vals
;
1126 vals
.push_all(&vals_left
);
1127 compile_submatch(bcx
, &pats
, &vals
, chk
, has_genuine_default
);
1133 // Decide what kind of branch we need
1134 let opts
= get_branches(bcx
, m
, col
);
1135 debug
!("options={:?}", opts
);
1136 let mut kind
= NoBranch
;
1137 let mut test_val
= val
;
1138 debug
!("test_val={}", bcx
.val_to_string(test_val
));
1139 if !opts
.is_empty() {
1141 ConstantValue(..) | ConstantRange(..) => {
1142 test_val
= load_if_immediate(bcx
, val
, left_ty
);
1143 kind
= if ty
::type_is_integral(left_ty
) {
1149 Variant(_
, ref repr
, _
, _
) => {
1150 let (the_kind
, val_opt
) = adt
::trans_switch(bcx
, &**repr
, val
);
1152 if let Some(tval
) = val_opt { test_val = tval; }
1154 SliceLengthEqual(..) | SliceLengthGreaterOrEqual(..) => {
1155 let (_
, len
) = tvec
::get_base_and_len(bcx
, val
, left_ty
);
1163 ConstantRange(..) => { kind = Compare; break }
,
1164 SliceLengthGreaterOrEqual(..) => { kind = CompareSliceLength; break }
,
1168 let else_cx
= match kind
{
1169 NoBranch
| Single
=> bcx
,
1170 _
=> bcx
.fcx
.new_temp_block("match_else")
1172 let sw
= if kind
== Switch
{
1173 build
::Switch(bcx
, test_val
, else_cx
.llbb
, opts
.len())
1175 C_int(ccx
, 0) // Placeholder for when not using a switch
1178 let defaults
= enter_default(else_cx
, dm
, m
, col
, val
);
1179 let exhaustive
= chk
.is_infallible() && defaults
.is_empty();
1180 let len
= opts
.len();
1182 // Compile subtrees for each option
1183 for (i
, opt
) in opts
.iter().enumerate() {
1184 // In some cases of range and vector pattern matching, we need to
1185 // override the failure case so that instead of failing, it proceeds
1186 // to try more matching. branch_chk, then, is the proper failure case
1187 // for the current conditional branch.
1188 let mut branch_chk
= None
;
1189 let mut opt_cx
= else_cx
;
1190 let debug_loc
= opt
.debug_loc();
1192 if !exhaustive
|| i
+ 1 < len
{
1193 opt_cx
= bcx
.fcx
.new_temp_block("match_case");
1195 Single
=> Br(bcx
, opt_cx
.llbb
, debug_loc
),
1197 match opt
.trans(bcx
) {
1198 SingleResult(r
) => {
1199 AddCase(sw
, r
.val
, opt_cx
.llbb
);
1204 "in compile_submatch, expected \
1205 opt.trans() to return a SingleResult")
1209 Compare
| CompareSliceLength
=> {
1210 let t
= if kind
== Compare
{
1213 tcx
.types
.usize // vector length
1215 let Result { bcx: after_cx, val: matches }
= {
1216 match opt
.trans(bcx
) {
1217 SingleResult(Result { bcx, val }
) => {
1218 compare_values(bcx
, test_val
, val
, t
, debug_loc
)
1220 RangeResult(Result { val: vbegin, .. }
,
1221 Result { bcx, val: vend }
) => {
1222 let llge
= compare_scalar_types(bcx
, test_val
, vbegin
,
1223 t
, ast
::BiGe
, debug_loc
);
1224 let llle
= compare_scalar_types(bcx
, test_val
, vend
,
1225 t
, ast
::BiLe
, debug_loc
);
1226 Result
::new(bcx
, And(bcx
, llge
, llle
, DebugLoc
::None
))
1228 LowerBound(Result { bcx, val }
) => {
1229 Result
::new(bcx
, compare_scalar_types(bcx
, test_val
,
1235 bcx
= fcx
.new_temp_block("compare_next");
1237 // If none of the sub-cases match, and the current condition
1238 // is guarded or has multiple patterns, move on to the next
1239 // condition, if there is any, rather than falling back to
1241 let guarded
= m
[i
].data
.arm
.guard
.is_some();
1242 let multi_pats
= m
[i
].pats
.len() > 1;
1243 if i
+ 1 < len
&& (guarded
|| multi_pats
|| kind
== CompareSliceLength
) {
1244 branch_chk
= Some(JumpToBasicBlock(bcx
.llbb
));
1246 CondBr(after_cx
, matches
, opt_cx
.llbb
, bcx
.llbb
, debug_loc
);
1250 } else if kind
== Compare
|| kind
== CompareSliceLength
{
1251 Br(bcx
, else_cx
.llbb
, debug_loc
);
1255 let mut unpacked
= Vec
::new();
1257 Variant(disr_val
, ref repr
, _
, _
) => {
1258 let ExtractedBlock {vals: argvals, bcx: new_bcx}
=
1259 extract_variant_args(opt_cx
, &**repr
, disr_val
, val
);
1260 size
= argvals
.len();
1264 SliceLengthEqual(len
, _
) => {
1265 let args
= extract_vec_elems(opt_cx
, left_ty
, len
, 0, val
);
1266 size
= args
.vals
.len();
1267 unpacked
= args
.vals
.clone();
1270 SliceLengthGreaterOrEqual(before
, after
, _
) => {
1271 let args
= extract_vec_elems(opt_cx
, left_ty
, before
, after
, val
);
1272 size
= args
.vals
.len();
1273 unpacked
= args
.vals
.clone();
1276 ConstantValue(..) | ConstantRange(..) => ()
1278 let opt_ms
= enter_opt(opt_cx
, pat_id
, dm
, m
, opt
, col
, size
, val
);
1279 let mut opt_vals
= unpacked
;
1280 opt_vals
.push_all(&vals_left
[..]);
1281 compile_submatch(opt_cx
,
1284 branch_chk
.as_ref().unwrap_or(chk
),
1285 has_genuine_default
);
1288 // Compile the fall-through case, if any
1289 if !exhaustive
&& kind
!= Single
{
1290 if kind
== Compare
|| kind
== CompareSliceLength
{
1291 Br(bcx
, else_cx
.llbb
, DebugLoc
::None
);
1294 // If there is only one default arm left, move on to the next
1295 // condition explicitly rather than (eventually) falling back to
1296 // the last default arm.
1297 &JumpToBasicBlock(_
) if defaults
.len() == 1 && has_genuine_default
=> {
1298 chk
.handle_fail(else_cx
);
1301 compile_submatch(else_cx
,
1305 has_genuine_default
);
1311 pub fn trans_match
<'blk
, 'tcx
>(bcx
: Block
<'blk
, 'tcx
>,
1312 match_expr
: &ast
::Expr
,
1313 discr_expr
: &ast
::Expr
,
1316 -> Block
<'blk
, 'tcx
> {
1317 let _icx
= push_ctxt("match::trans_match");
1318 trans_match_inner(bcx
, match_expr
.id
, discr_expr
, arms
, dest
)
1321 /// Checks whether the binding in `discr` is assigned to anywhere in the expression `body`
1322 fn is_discr_reassigned(bcx
: Block
, discr
: &ast
::Expr
, body
: &ast
::Expr
) -> bool
{
1323 let (vid
, field
) = match discr
.node
{
1324 ast
::ExprPath(..) => match bcx
.def(discr
.id
) {
1325 def
::DefLocal(vid
) | def
::DefUpvar(vid
, _
) => (vid
, None
),
1328 ast
::ExprField(ref base
, field
) => {
1329 let vid
= match bcx
.tcx().def_map
.borrow().get(&base
.id
).map(|d
| d
.full_def()) {
1330 Some(def
::DefLocal(vid
)) | Some(def
::DefUpvar(vid
, _
)) => vid
,
1333 (vid
, Some(mc
::NamedField(field
.node
.name
)))
1335 ast
::ExprTupField(ref base
, field
) => {
1336 let vid
= match bcx
.tcx().def_map
.borrow().get(&base
.id
).map(|d
| d
.full_def()) {
1337 Some(def
::DefLocal(vid
)) | Some(def
::DefUpvar(vid
, _
)) => vid
,
1340 (vid
, Some(mc
::PositionalField(field
.node
)))
1345 let mut rc
= ReassignmentChecker
{
1351 let mut visitor
= euv
::ExprUseVisitor
::new(&mut rc
, bcx
);
1352 visitor
.walk_expr(body
);
1357 struct ReassignmentChecker
{
1359 field
: Option
<mc
::FieldName
>,
1363 // Determine if the expression we're matching on is reassigned to within
1364 // the body of the match's arm.
1365 // We only care for the `mutate` callback since this check only matters
1366 // for cases where the matched value is moved.
1367 impl<'tcx
> euv
::Delegate
<'tcx
> for ReassignmentChecker
{
1368 fn consume(&mut self, _
: ast
::NodeId
, _
: Span
, _
: mc
::cmt
, _
: euv
::ConsumeMode
) {}
1369 fn matched_pat(&mut self, _
: &ast
::Pat
, _
: mc
::cmt
, _
: euv
::MatchMode
) {}
1370 fn consume_pat(&mut self, _
: &ast
::Pat
, _
: mc
::cmt
, _
: euv
::ConsumeMode
) {}
1371 fn borrow(&mut self, _
: ast
::NodeId
, _
: Span
, _
: mc
::cmt
, _
: ty
::Region
,
1372 _
: ty
::BorrowKind
, _
: euv
::LoanCause
) {}
1373 fn decl_without_init(&mut self, _
: ast
::NodeId
, _
: Span
) {}
1375 fn mutate(&mut self, _
: ast
::NodeId
, _
: Span
, cmt
: mc
::cmt
, _
: euv
::MutateMode
) {
1377 mc
::cat_upvar(mc
::Upvar { id: ty::UpvarId { var_id: vid, .. }
, .. }) |
1378 mc
::cat_local(vid
) => self.reassigned
|= self.node
== vid
,
1379 mc
::cat_interior(ref base_cmt
, mc
::InteriorField(field
)) => {
1380 match base_cmt
.cat
{
1381 mc
::cat_upvar(mc
::Upvar { id: ty::UpvarId { var_id: vid, .. }
, .. }) |
1382 mc
::cat_local(vid
) => {
1383 self.reassigned
|= self.node
== vid
&& Some(field
) == self.field
1393 fn create_bindings_map
<'blk
, 'tcx
>(bcx
: Block
<'blk
, 'tcx
>, pat
: &ast
::Pat
,
1394 discr
: &ast
::Expr
, body
: &ast
::Expr
)
1395 -> BindingsMap
<'tcx
> {
1396 // Create the bindings map, which is a mapping from each binding name
1397 // to an alloca() that will be the value for that local variable.
1398 // Note that we use the names because each binding will have many ids
1399 // from the various alternatives.
1400 let ccx
= bcx
.ccx();
1401 let tcx
= bcx
.tcx();
1402 let reassigned
= is_discr_reassigned(bcx
, discr
, body
);
1403 let mut bindings_map
= FnvHashMap();
1404 pat_bindings(&tcx
.def_map
, &*pat
, |bm
, p_id
, span
, path1
| {
1405 let ident
= path1
.node
;
1406 let name
= ident
.name
;
1407 let variable_ty
= node_id_type(bcx
, p_id
);
1408 let llvariable_ty
= type_of
::type_of(ccx
, variable_ty
);
1409 let tcx
= bcx
.tcx();
1410 let param_env
= ty
::empty_parameter_environment(tcx
);
1416 if !ty
::type_moves_by_default(¶m_env
, span
, variable_ty
) || reassigned
=>
1418 llmatch
= alloca_no_lifetime(bcx
,
1419 llvariable_ty
.ptr_to(),
1421 trmode
= TrByCopy(alloca_no_lifetime(bcx
,
1425 ast
::BindByValue(_
) => {
1426 // in this case, the final type of the variable will be T,
1427 // but during matching we need to store a *T as explained
1429 llmatch
= alloca_no_lifetime(bcx
,
1430 llvariable_ty
.ptr_to(),
1434 ast
::BindByRef(_
) => {
1435 llmatch
= alloca_no_lifetime(bcx
,
1441 bindings_map
.insert(ident
, BindingInfo
{
1449 return bindings_map
;
1452 fn trans_match_inner
<'blk
, 'tcx
>(scope_cx
: Block
<'blk
, 'tcx
>,
1453 match_id
: ast
::NodeId
,
1454 discr_expr
: &ast
::Expr
,
1456 dest
: Dest
) -> Block
<'blk
, 'tcx
> {
1457 let _icx
= push_ctxt("match::trans_match_inner");
1458 let fcx
= scope_cx
.fcx
;
1459 let mut bcx
= scope_cx
;
1460 let tcx
= bcx
.tcx();
1462 let discr_datum
= unpack_datum
!(bcx
, expr
::trans_to_lvalue(bcx
, discr_expr
,
1464 if bcx
.unreachable
.get() {
1468 let t
= node_id_type(bcx
, discr_expr
.id
);
1469 let chk
= if ty
::type_is_empty(tcx
, t
) {
1475 let arm_datas
: Vec
<ArmData
> = arms
.iter().map(|arm
| ArmData
{
1476 bodycx
: fcx
.new_id_block("case_body", arm
.body
.id
),
1478 bindings_map
: create_bindings_map(bcx
, &*arm
.pats
[0], discr_expr
, &*arm
.body
)
1481 let mut pat_renaming_map
= if scope_cx
.sess().opts
.debuginfo
!= NoDebugInfo
{
1487 let arm_pats
: Vec
<Vec
<P
<ast
::Pat
>>> = {
1488 let mut static_inliner
= StaticInliner
::new(scope_cx
.tcx(),
1489 pat_renaming_map
.as_mut());
1490 arm_datas
.iter().map(|arm_data
| {
1491 arm_data
.arm
.pats
.iter().map(|p
| static_inliner
.fold_pat((*p
).clone())).collect()
1495 let mut matches
= Vec
::new();
1496 for (arm_data
, pats
) in arm_datas
.iter().zip(&arm_pats
) {
1497 matches
.extend(pats
.iter().map(|p
| Match
{
1500 bound_ptrs
: Vec
::new(),
1501 pat_renaming_map
: pat_renaming_map
.as_ref()
1505 // `compile_submatch` works one column of arm patterns a time and
1506 // then peels that column off. So as we progress, it may become
1507 // impossible to tell whether we have a genuine default arm, i.e.
1508 // `_ => foo` or not. Sometimes it is important to know that in order
1509 // to decide whether moving on to the next condition or falling back
1510 // to the default arm.
1511 let has_default
= arms
.last().map_or(false, |arm
| {
1513 && arm
.pats
.last().unwrap().node
== ast
::PatWild(ast
::PatWildSingle
)
1516 compile_submatch(bcx
, &matches
[..], &[discr_datum
.val
], &chk
, has_default
);
1518 let mut arm_cxs
= Vec
::new();
1519 for arm_data
in &arm_datas
{
1520 let mut bcx
= arm_data
.bodycx
;
1522 // insert bindings into the lllocals map and add cleanups
1523 let cs
= fcx
.push_custom_cleanup_scope();
1524 bcx
= insert_lllocals(bcx
, &arm_data
.bindings_map
, Some(cleanup
::CustomScope(cs
)));
1525 bcx
= expr
::trans_into(bcx
, &*arm_data
.arm
.body
, dest
);
1526 bcx
= fcx
.pop_and_trans_custom_cleanup_scope(bcx
, cs
);
1530 bcx
= scope_cx
.fcx
.join_blocks(match_id
, &arm_cxs
[..]);
1534 /// Generates code for a local variable declaration like `let <pat>;` or `let <pat> =
1535 /// <opt_init_expr>`.
1536 pub fn store_local
<'blk
, 'tcx
>(bcx
: Block
<'blk
, 'tcx
>,
1538 -> Block
<'blk
, 'tcx
> {
1539 let _icx
= push_ctxt("match::store_local");
1541 let tcx
= bcx
.tcx();
1542 let pat
= &*local
.pat
;
1544 fn create_dummy_locals
<'blk
, 'tcx
>(mut bcx
: Block
<'blk
, 'tcx
>,
1546 -> Block
<'blk
, 'tcx
> {
1547 let _icx
= push_ctxt("create_dummy_locals");
1548 // create dummy memory for the variables if we have no
1549 // value to store into them immediately
1550 let tcx
= bcx
.tcx();
1551 pat_bindings(&tcx
.def_map
, pat
, |_
, p_id
, _
, path1
| {
1552 let scope
= cleanup
::var_scope(tcx
, p_id
);
1553 bcx
= mk_binding_alloca(
1554 bcx
, p_id
, path1
.node
.name
, scope
, (),
1555 |(), bcx
, llval
, ty
| { drop_done_fill_mem(bcx, llval, ty); bcx }
);
1561 Some(ref init_expr
) => {
1562 // Optimize the "let x = expr" case. This just writes
1563 // the result of evaluating `expr` directly into the alloca
1564 // for `x`. Often the general path results in similar or the
1565 // same code post-optimization, but not always. In particular,
1566 // in unsafe code, you can have expressions like
1568 // let x = intrinsics::uninit();
1570 // In such cases, the more general path is unsafe, because
1571 // it assumes it is matching against a valid value.
1572 match simple_identifier(&*pat
) {
1574 let var_scope
= cleanup
::var_scope(tcx
, local
.id
);
1575 return mk_binding_alloca(
1576 bcx
, pat
.id
, ident
.name
, var_scope
, (),
1577 |(), bcx
, v
, _
| expr
::trans_into(bcx
, &**init_expr
,
1586 unpack_datum
!(bcx
, expr
::trans_to_lvalue(bcx
, &**init_expr
, "let"));
1587 if bcx
.sess().asm_comments() {
1588 add_comment(bcx
, "creating zeroable ref llval");
1590 let var_scope
= cleanup
::var_scope(tcx
, local
.id
);
1591 bind_irrefutable_pat(bcx
, pat
, init_datum
.val
, var_scope
)
1594 create_dummy_locals(bcx
, pat
)
1599 /// Generates code for argument patterns like `fn foo(<pat>: T)`.
1600 /// Creates entries in the `lllocals` map for each of the bindings
1605 /// - `pat` is the argument pattern
1606 /// - `llval` is a pointer to the argument value (in other words,
1607 /// if the argument type is `T`, then `llval` is a `T*`). In some
1608 /// cases, this code may zero out the memory `llval` points at.
1609 pub fn store_arg
<'blk
, 'tcx
>(mut bcx
: Block
<'blk
, 'tcx
>,
1611 arg
: Datum
<'tcx
, Rvalue
>,
1612 arg_scope
: cleanup
::ScopeId
)
1613 -> Block
<'blk
, 'tcx
> {
1614 let _icx
= push_ctxt("match::store_arg");
1616 match simple_identifier(&*pat
) {
1618 // Generate nicer LLVM for the common case of fn a pattern
1620 let arg_ty
= node_id_type(bcx
, pat
.id
);
1621 if type_of
::arg_is_indirect(bcx
.ccx(), arg_ty
)
1622 && bcx
.sess().opts
.debuginfo
!= FullDebugInfo
{
1623 // Don't copy an indirect argument to an alloca, the caller
1624 // already put it in a temporary alloca and gave it up, unless
1625 // we emit extra-debug-info, which requires local allocas :(.
1626 let arg_val
= arg
.add_clean(bcx
.fcx
, arg_scope
);
1627 bcx
.fcx
.lllocals
.borrow_mut()
1628 .insert(pat
.id
, Datum
::new(arg_val
, arg_ty
, Lvalue
));
1632 bcx
, pat
.id
, ident
.name
, arg_scope
, arg
,
1633 |arg
, bcx
, llval
, _
| arg
.store_to(bcx
, llval
))
1638 // General path. Copy out the values that are used in the
1640 let arg
= unpack_datum
!(
1641 bcx
, arg
.to_lvalue_datum_in_scope(bcx
, "__arg", arg_scope
));
1642 bind_irrefutable_pat(bcx
, pat
, arg
.val
, arg_scope
)
1647 fn mk_binding_alloca
<'blk
, 'tcx
, A
, F
>(bcx
: Block
<'blk
, 'tcx
>,
1650 cleanup_scope
: cleanup
::ScopeId
,
1653 -> Block
<'blk
, 'tcx
> where
1654 F
: FnOnce(A
, Block
<'blk
, 'tcx
>, ValueRef
, Ty
<'tcx
>) -> Block
<'blk
, 'tcx
>,
1656 let var_ty
= node_id_type(bcx
, p_id
);
1658 // Allocate memory on stack for the binding.
1659 let llval
= alloc_ty(bcx
, var_ty
, &bcx
.name(name
));
1661 // Subtle: be sure that we *populate* the memory *before*
1662 // we schedule the cleanup.
1663 let bcx
= populate(arg
, bcx
, llval
, var_ty
);
1664 bcx
.fcx
.schedule_lifetime_end(cleanup_scope
, llval
);
1665 bcx
.fcx
.schedule_drop_mem(cleanup_scope
, llval
, var_ty
);
1667 // Now that memory is initialized and has cleanup scheduled,
1668 // create the datum and insert into the local variable map.
1669 let datum
= Datum
::new(llval
, var_ty
, Lvalue
);
1670 bcx
.fcx
.lllocals
.borrow_mut().insert(p_id
, datum
);
1674 /// A simple version of the pattern matching code that only handles
1675 /// irrefutable patterns. This is used in let/argument patterns,
1676 /// not in match statements. Unifying this code with the code above
1677 /// sounds nice, but in practice it produces very inefficient code,
1678 /// since the match code is so much more general. In most cases,
1679 /// LLVM is able to optimize the code, but it causes longer compile
1680 /// times and makes the generated code nigh impossible to read.
1683 /// - bcx: starting basic block context
1684 /// - pat: the irrefutable pattern being matched.
1685 /// - val: the value being matched -- must be an lvalue (by ref, with cleanup)
1686 fn bind_irrefutable_pat
<'blk
, 'tcx
>(bcx
: Block
<'blk
, 'tcx
>,
1689 cleanup_scope
: cleanup
::ScopeId
)
1690 -> Block
<'blk
, 'tcx
> {
1691 debug
!("bind_irrefutable_pat(bcx={}, pat={:?})",
1695 if bcx
.sess().asm_comments() {
1696 add_comment(bcx
, &format
!("bind_irrefutable_pat(pat={:?})",
1700 let _indenter
= indenter();
1702 let _icx
= push_ctxt("match::bind_irrefutable_pat");
1704 let tcx
= bcx
.tcx();
1705 let ccx
= bcx
.ccx();
1707 ast
::PatIdent(pat_binding_mode
, ref path1
, ref inner
) => {
1708 if pat_is_binding(&tcx
.def_map
, &*pat
) {
1709 // Allocate the stack slot where the value of this
1710 // binding will live and place it into the appropriate
1712 bcx
= mk_binding_alloca(
1713 bcx
, pat
.id
, path1
.node
.name
, cleanup_scope
, (),
1714 |(), bcx
, llval
, ty
| {
1715 match pat_binding_mode
{
1716 ast
::BindByValue(_
) => {
1717 // By value binding: move the value that `val`
1718 // points at into the binding's stack slot.
1719 let d
= Datum
::new(val
, ty
, Lvalue
);
1720 d
.store_to(bcx
, llval
)
1723 ast
::BindByRef(_
) => {
1724 // By ref binding: the value of the variable
1725 // is the pointer `val` itself or fat pointer referenced by `val`
1726 if type_is_fat_ptr(bcx
.tcx(), ty
) {
1727 expr
::copy_fat_ptr(bcx
, val
, llval
);
1730 Store(bcx
, val
, llval
);
1739 if let Some(ref inner_pat
) = *inner
{
1740 bcx
= bind_irrefutable_pat(bcx
, &**inner_pat
, val
, cleanup_scope
);
1743 ast
::PatEnum(_
, ref sub_pats
) => {
1744 let opt_def
= bcx
.tcx().def_map
.borrow().get(&pat
.id
).map(|d
| d
.full_def());
1746 Some(def
::DefVariant(enum_id
, var_id
, _
)) => {
1747 let repr
= adt
::represent_node(bcx
, pat
.id
);
1748 let vinfo
= ty
::enum_variant_with_id(ccx
.tcx(),
1751 let args
= extract_variant_args(bcx
,
1755 if let Some(ref sub_pat
) = *sub_pats
{
1756 for (i
, &argval
) in args
.vals
.iter().enumerate() {
1757 bcx
= bind_irrefutable_pat(bcx
, &*sub_pat
[i
],
1758 argval
, cleanup_scope
);
1762 Some(def
::DefStruct(..)) => {
1765 // This is a unit-like struct. Nothing to do here.
1767 Some(ref elems
) => {
1768 // This is the tuple struct case.
1769 let repr
= adt
::represent_node(bcx
, pat
.id
);
1770 for (i
, elem
) in elems
.iter().enumerate() {
1771 let fldptr
= adt
::trans_field_ptr(bcx
, &*repr
,
1773 bcx
= bind_irrefutable_pat(bcx
, &**elem
,
1774 fldptr
, cleanup_scope
);
1780 // Nothing to do here.
1784 ast
::PatStruct(_
, ref fields
, _
) => {
1785 let tcx
= bcx
.tcx();
1786 let pat_ty
= node_id_type(bcx
, pat
.id
);
1787 let pat_repr
= adt
::represent_type(bcx
.ccx(), pat_ty
);
1788 expr
::with_field_tys(tcx
, pat_ty
, Some(pat
.id
), |discr
, field_tys
| {
1790 let ix
= ty
::field_idx_strict(tcx
, f
.node
.ident
.name
, field_tys
);
1791 let fldptr
= adt
::trans_field_ptr(bcx
, &*pat_repr
, val
,
1793 bcx
= bind_irrefutable_pat(bcx
, &*f
.node
.pat
, fldptr
, cleanup_scope
);
1797 ast
::PatTup(ref elems
) => {
1798 let repr
= adt
::represent_node(bcx
, pat
.id
);
1799 for (i
, elem
) in elems
.iter().enumerate() {
1800 let fldptr
= adt
::trans_field_ptr(bcx
, &*repr
, val
, 0, i
);
1801 bcx
= bind_irrefutable_pat(bcx
, &**elem
, fldptr
, cleanup_scope
);
1804 ast
::PatBox(ref inner
) => {
1805 let llbox
= Load(bcx
, val
);
1806 bcx
= bind_irrefutable_pat(bcx
, &**inner
, llbox
, cleanup_scope
);
1808 ast
::PatRegion(ref inner
, _
) => {
1809 let loaded_val
= Load(bcx
, val
);
1810 bcx
= bind_irrefutable_pat(bcx
, &**inner
, loaded_val
, cleanup_scope
);
1812 ast
::PatVec(ref before
, ref slice
, ref after
) => {
1813 let pat_ty
= node_id_type(bcx
, pat
.id
);
1814 let mut extracted
= extract_vec_elems(bcx
, pat_ty
, before
.len(), after
.len(), val
);
1817 extracted
.vals
.insert(
1819 bind_subslice_pat(bcx
, pat
.id
, val
, before
.len(), after
.len())
1826 .chain(slice
.iter())
1827 .chain(after
.iter())
1828 .zip(extracted
.vals
)
1829 .fold(bcx
, |bcx
, (inner
, elem
)|
1830 bind_irrefutable_pat(bcx
, &**inner
, elem
, cleanup_scope
)
1833 ast
::PatMac(..) => {
1834 bcx
.sess().span_bug(pat
.span
, "unexpanded macro");
1836 ast
::PatQPath(..) | ast
::PatWild(_
) | ast
::PatLit(_
) |
1837 ast
::PatRange(_
, _
) => ()