]> git.lizzy.rs Git - rust.git/blob - src/librustc_mir/transform/elaborate_drops.rs
rustdoc: pretty-print Unevaluated expressions in types.
[rust.git] / src / librustc_mir / transform / elaborate_drops.rs
1 // Copyright 2016 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.
4 //
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.
10
11 use dataflow::move_paths::{HasMoveData, MoveData, MovePathIndex, LookupResult};
12 use dataflow::{MaybeInitializedLvals, MaybeUninitializedLvals};
13 use dataflow::{DataflowResults};
14 use dataflow::{on_all_children_bits, on_all_drop_children_bits};
15 use dataflow::{drop_flag_effects_for_location, on_lookup_result_bits};
16 use dataflow::MoveDataParamEnv;
17 use dataflow;
18 use rustc::ty::{self, TyCtxt};
19 use rustc::mir::*;
20 use rustc::mir::transform::{MirPass, MirSource};
21 use rustc::middle::const_val::ConstVal;
22 use rustc::util::nodemap::FxHashMap;
23 use rustc_data_structures::indexed_set::IdxSetBuf;
24 use rustc_data_structures::indexed_vec::Idx;
25 use util::patch::MirPatch;
26 use util::elaborate_drops::{DropFlagState, Unwind, elaborate_drop};
27 use util::elaborate_drops::{DropElaborator, DropStyle, DropFlagMode};
28 use syntax::ast;
29 use syntax_pos::Span;
30
31 use std::fmt;
32
33 pub struct ElaborateDrops;
34
35 impl MirPass for ElaborateDrops {
36     fn run_pass<'a, 'tcx>(&self,
37                           tcx: TyCtxt<'a, 'tcx, 'tcx>,
38                           src: MirSource,
39                           mir: &mut Mir<'tcx>)
40     {
41         debug!("elaborate_drops({:?} @ {:?})", src, mir.span);
42         match src {
43             MirSource::Fn(..) => {},
44             _ => return
45         }
46         let id = src.item_id();
47         let param_env = tcx.param_env(tcx.hir.local_def_id(id));
48         let move_data = MoveData::gather_moves(mir, tcx, param_env);
49         let elaborate_patch = {
50             let mir = &*mir;
51             let env = MoveDataParamEnv {
52                 move_data,
53                 param_env,
54             };
55             let dead_unwinds = find_dead_unwinds(tcx, mir, id, &env);
56             let flow_inits =
57                 dataflow::do_dataflow(tcx, mir, id, &[], &dead_unwinds,
58                                       MaybeInitializedLvals::new(tcx, mir, &env),
59                                       |bd, p| &bd.move_data().move_paths[p]);
60             let flow_uninits =
61                 dataflow::do_dataflow(tcx, mir, id, &[], &dead_unwinds,
62                                       MaybeUninitializedLvals::new(tcx, mir, &env),
63                                       |bd, p| &bd.move_data().move_paths[p]);
64
65             ElaborateDropsCtxt {
66                 tcx,
67                 mir,
68                 env: &env,
69                 flow_inits,
70                 flow_uninits,
71                 drop_flags: FxHashMap(),
72                 patch: MirPatch::new(mir),
73             }.elaborate()
74         };
75         elaborate_patch.apply(mir);
76     }
77 }
78
79 /// Return the set of basic blocks whose unwind edges are known
80 /// to not be reachable, because they are `drop` terminators
81 /// that can't drop anything.
82 fn find_dead_unwinds<'a, 'tcx>(
83     tcx: TyCtxt<'a, 'tcx, 'tcx>,
84     mir: &Mir<'tcx>,
85     id: ast::NodeId,
86     env: &MoveDataParamEnv<'tcx>)
87     -> IdxSetBuf<BasicBlock>
88 {
89     debug!("find_dead_unwinds({:?})", mir.span);
90     // We only need to do this pass once, because unwind edges can only
91     // reach cleanup blocks, which can't have unwind edges themselves.
92     let mut dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len());
93     let flow_inits =
94         dataflow::do_dataflow(tcx, mir, id, &[], &dead_unwinds,
95                            MaybeInitializedLvals::new(tcx, mir, &env),
96                            |bd, p| &bd.move_data().move_paths[p]);
97     for (bb, bb_data) in mir.basic_blocks().iter_enumerated() {
98         let location = match bb_data.terminator().kind {
99             TerminatorKind::Drop { ref location, unwind: Some(_), .. } |
100             TerminatorKind::DropAndReplace { ref location, unwind: Some(_), .. } => location,
101             _ => continue,
102         };
103
104         let mut init_data = InitializationData {
105             live: flow_inits.sets().on_entry_set_for(bb.index()).to_owned(),
106             dead: IdxSetBuf::new_empty(env.move_data.move_paths.len()),
107         };
108         debug!("find_dead_unwinds @ {:?}: {:?}; init_data={:?}",
109                bb, bb_data, init_data.live);
110         for stmt in 0..bb_data.statements.len() {
111             let loc = Location { block: bb, statement_index: stmt };
112             init_data.apply_location(tcx, mir, env, loc);
113         }
114
115         let path = match env.move_data.rev_lookup.find(location) {
116             LookupResult::Exact(e) => e,
117             LookupResult::Parent(..) => {
118                 debug!("find_dead_unwinds: has parent; skipping");
119                 continue
120             }
121         };
122
123         debug!("find_dead_unwinds @ {:?}: path({:?})={:?}", bb, location, path);
124
125         let mut maybe_live = false;
126         on_all_drop_children_bits(tcx, mir, &env, path, |child| {
127             let (child_maybe_live, _) = init_data.state(child);
128             maybe_live |= child_maybe_live;
129         });
130
131         debug!("find_dead_unwinds @ {:?}: maybe_live={}", bb, maybe_live);
132         if !maybe_live {
133             dead_unwinds.add(&bb);
134         }
135     }
136
137     dead_unwinds
138 }
139
140 struct InitializationData {
141     live: IdxSetBuf<MovePathIndex>,
142     dead: IdxSetBuf<MovePathIndex>
143 }
144
145 impl InitializationData {
146     fn apply_location<'a,'tcx>(&mut self,
147                                tcx: TyCtxt<'a, 'tcx, 'tcx>,
148                                mir: &Mir<'tcx>,
149                                env: &MoveDataParamEnv<'tcx>,
150                                loc: Location)
151     {
152         drop_flag_effects_for_location(tcx, mir, env, loc, |path, df| {
153             debug!("at location {:?}: setting {:?} to {:?}",
154                    loc, path, df);
155             match df {
156                 DropFlagState::Present => {
157                     self.live.add(&path);
158                     self.dead.remove(&path);
159                 }
160                 DropFlagState::Absent => {
161                     self.dead.add(&path);
162                     self.live.remove(&path);
163                 }
164             }
165         });
166     }
167
168     fn state(&self, path: MovePathIndex) -> (bool, bool) {
169         (self.live.contains(&path), self.dead.contains(&path))
170     }
171 }
172
173 struct Elaborator<'a, 'b: 'a, 'tcx: 'b> {
174     init_data: &'a InitializationData,
175     ctxt: &'a mut ElaborateDropsCtxt<'b, 'tcx>,
176 }
177
178 impl<'a, 'b, 'tcx> fmt::Debug for Elaborator<'a, 'b, 'tcx> {
179     fn fmt(&self, _f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
180         Ok(())
181     }
182 }
183
184 impl<'a, 'b, 'tcx> DropElaborator<'a, 'tcx> for Elaborator<'a, 'b, 'tcx> {
185     type Path = MovePathIndex;
186
187     fn patch(&mut self) -> &mut MirPatch<'tcx> {
188         &mut self.ctxt.patch
189     }
190
191     fn mir(&self) -> &'a Mir<'tcx> {
192         self.ctxt.mir
193     }
194
195     fn tcx(&self) -> ty::TyCtxt<'a, 'tcx, 'tcx> {
196         self.ctxt.tcx
197     }
198
199     fn param_env(&self) -> ty::ParamEnv<'tcx> {
200         self.ctxt.param_env()
201     }
202
203     fn drop_style(&self, path: Self::Path, mode: DropFlagMode) -> DropStyle {
204         let ((maybe_live, maybe_dead), multipart) = match mode {
205             DropFlagMode::Shallow => (self.init_data.state(path), false),
206             DropFlagMode::Deep => {
207                 let mut some_live = false;
208                 let mut some_dead = false;
209                 let mut children_count = 0;
210                 on_all_drop_children_bits(
211                     self.tcx(), self.mir(), self.ctxt.env, path, |child| {
212                         let (live, dead) = self.init_data.state(child);
213                         debug!("elaborate_drop: state({:?}) = {:?}",
214                                child, (live, dead));
215                         some_live |= live;
216                         some_dead |= dead;
217                         children_count += 1;
218                     });
219                 ((some_live, some_dead), children_count != 1)
220             }
221         };
222         match (maybe_live, maybe_dead, multipart) {
223             (false, _, _) => DropStyle::Dead,
224             (true, false, _) => DropStyle::Static,
225             (true, true, false) => DropStyle::Conditional,
226             (true, true, true) => DropStyle::Open,
227         }
228     }
229
230     fn clear_drop_flag(&mut self, loc: Location, path: Self::Path, mode: DropFlagMode) {
231         match mode {
232             DropFlagMode::Shallow => {
233                 self.ctxt.set_drop_flag(loc, path, DropFlagState::Absent);
234             }
235             DropFlagMode::Deep => {
236                 on_all_children_bits(
237                     self.tcx(), self.mir(), self.ctxt.move_data(), path,
238                     |child| self.ctxt.set_drop_flag(loc, child, DropFlagState::Absent)
239                  );
240             }
241         }
242     }
243
244     fn field_subpath(&self, path: Self::Path, field: Field) -> Option<Self::Path> {
245         dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
246             match p {
247                 &Projection {
248                     elem: ProjectionElem::Field(idx, _), ..
249                 } => idx == field,
250                 _ => false
251             }
252         })
253     }
254
255     fn deref_subpath(&self, path: Self::Path) -> Option<Self::Path> {
256         dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
257             match p {
258                 &Projection { elem: ProjectionElem::Deref, .. } => true,
259                 _ => false
260             }
261         })
262     }
263
264     fn downcast_subpath(&self, path: Self::Path, variant: usize) -> Option<Self::Path> {
265         dataflow::move_path_children_matching(self.ctxt.move_data(), path, |p| {
266             match p {
267                 &Projection {
268                     elem: ProjectionElem::Downcast(_, idx), ..
269                 } => idx == variant,
270                 _ => false
271             }
272         })
273     }
274
275     fn get_drop_flag(&mut self, path: Self::Path) -> Option<Operand<'tcx>> {
276         self.ctxt.drop_flag(path).map(Operand::Consume)
277     }
278 }
279
280 struct ElaborateDropsCtxt<'a, 'tcx: 'a> {
281     tcx: TyCtxt<'a, 'tcx, 'tcx>,
282     mir: &'a Mir<'tcx>,
283     env: &'a MoveDataParamEnv<'tcx>,
284     flow_inits: DataflowResults<MaybeInitializedLvals<'a, 'tcx>>,
285     flow_uninits:  DataflowResults<MaybeUninitializedLvals<'a, 'tcx>>,
286     drop_flags: FxHashMap<MovePathIndex, Local>,
287     patch: MirPatch<'tcx>,
288 }
289
290 impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
291     fn move_data(&self) -> &'b MoveData<'tcx> { &self.env.move_data }
292
293     fn param_env(&self) -> ty::ParamEnv<'tcx> {
294         self.env.param_env
295     }
296
297     fn initialization_data_at(&self, loc: Location) -> InitializationData {
298         let mut data = InitializationData {
299             live: self.flow_inits.sets().on_entry_set_for(loc.block.index())
300                 .to_owned(),
301             dead: self.flow_uninits.sets().on_entry_set_for(loc.block.index())
302                 .to_owned(),
303         };
304         for stmt in 0..loc.statement_index {
305             data.apply_location(self.tcx, self.mir, self.env,
306                                 Location { block: loc.block, statement_index: stmt });
307         }
308         data
309     }
310
311     fn create_drop_flag(&mut self, index: MovePathIndex, span: Span) {
312         let tcx = self.tcx;
313         let patch = &mut self.patch;
314         debug!("create_drop_flag({:?})", self.mir.span);
315         self.drop_flags.entry(index).or_insert_with(|| {
316             patch.new_internal(tcx.types.bool, span)
317         });
318     }
319
320     fn drop_flag(&mut self, index: MovePathIndex) -> Option<Lvalue<'tcx>> {
321         self.drop_flags.get(&index).map(|t| Lvalue::Local(*t))
322     }
323
324     /// create a patch that elaborates all drops in the input
325     /// MIR.
326     fn elaborate(mut self) -> MirPatch<'tcx>
327     {
328         self.collect_drop_flags();
329
330         self.elaborate_drops();
331
332         self.drop_flags_on_init();
333         self.drop_flags_for_fn_rets();
334         self.drop_flags_for_args();
335         self.drop_flags_for_locs();
336
337         self.patch
338     }
339
340     fn collect_drop_flags(&mut self)
341     {
342         for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
343             let terminator = data.terminator();
344             let location = match terminator.kind {
345                 TerminatorKind::Drop { ref location, .. } |
346                 TerminatorKind::DropAndReplace { ref location, .. } => location,
347                 _ => continue
348             };
349
350             let init_data = self.initialization_data_at(Location {
351                 block: bb,
352                 statement_index: data.statements.len()
353             });
354
355             let path = self.move_data().rev_lookup.find(location);
356             debug!("collect_drop_flags: {:?}, lv {:?} ({:?})",
357                    bb, location, path);
358
359             let path = match path {
360                 LookupResult::Exact(e) => e,
361                 LookupResult::Parent(None) => continue,
362                 LookupResult::Parent(Some(parent)) => {
363                     let (_maybe_live, maybe_dead) = init_data.state(parent);
364                     if maybe_dead {
365                         span_bug!(terminator.source_info.span,
366                                   "drop of untracked, uninitialized value {:?}, lv {:?} ({:?})",
367                                   bb, location, path);
368                     }
369                     continue
370                 }
371             };
372
373             on_all_drop_children_bits(self.tcx, self.mir, self.env, path, |child| {
374                 let (maybe_live, maybe_dead) = init_data.state(child);
375                 debug!("collect_drop_flags: collecting {:?} from {:?}@{:?} - {:?}",
376                        child, location, path, (maybe_live, maybe_dead));
377                 if maybe_live && maybe_dead {
378                     self.create_drop_flag(child, terminator.source_info.span)
379                 }
380             });
381         }
382     }
383
384     fn elaborate_drops(&mut self)
385     {
386         for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
387             let loc = Location { block: bb, statement_index: data.statements.len() };
388             let terminator = data.terminator();
389
390             let resume_block = self.patch.resume_block();
391             match terminator.kind {
392                 TerminatorKind::Drop { ref location, target, unwind } => {
393                     let init_data = self.initialization_data_at(loc);
394                     match self.move_data().rev_lookup.find(location) {
395                         LookupResult::Exact(path) => {
396                             elaborate_drop(
397                                 &mut Elaborator {
398                                     init_data: &init_data,
399                                     ctxt: self
400                                 },
401                                 terminator.source_info,
402                                 location,
403                                 path,
404                                 target,
405                                 if data.is_cleanup {
406                                     Unwind::InCleanup
407                                 } else {
408                                     Unwind::To(Option::unwrap_or(unwind, resume_block))
409                                 },
410                                 bb)
411                         }
412                         LookupResult::Parent(..) => {
413                             span_bug!(terminator.source_info.span,
414                                       "drop of untracked value {:?}", bb);
415                         }
416                     }
417                 }
418                 TerminatorKind::DropAndReplace { ref location, ref value,
419                                                  target, unwind } =>
420                 {
421                     assert!(!data.is_cleanup);
422
423                     self.elaborate_replace(
424                         loc,
425                         location, value,
426                         target, unwind
427                     );
428                 }
429                 _ => continue
430             }
431         }
432     }
433
434     /// Elaborate a MIR `replace` terminator. This instruction
435     /// is not directly handled by translation, and therefore
436     /// must be desugared.
437     ///
438     /// The desugaring drops the location if needed, and then writes
439     /// the value (including setting the drop flag) over it in *both* arms.
440     ///
441     /// The `replace` terminator can also be called on lvalues that
442     /// are not tracked by elaboration (for example,
443     /// `replace x[i] <- tmp0`). The borrow checker requires that
444     /// these locations are initialized before the assignment,
445     /// so we just generate an unconditional drop.
446     fn elaborate_replace(
447         &mut self,
448         loc: Location,
449         location: &Lvalue<'tcx>,
450         value: &Operand<'tcx>,
451         target: BasicBlock,
452         unwind: Option<BasicBlock>)
453     {
454         let bb = loc.block;
455         let data = &self.mir[bb];
456         let terminator = data.terminator();
457         assert!(!data.is_cleanup, "DropAndReplace in unwind path not supported");
458
459         let assign = Statement {
460             kind: StatementKind::Assign(location.clone(), Rvalue::Use(value.clone())),
461             source_info: terminator.source_info
462         };
463
464         let unwind = unwind.unwrap_or(self.patch.resume_block());
465         let unwind = self.patch.new_block(BasicBlockData {
466             statements: vec![assign.clone()],
467             terminator: Some(Terminator {
468                 kind: TerminatorKind::Goto { target: unwind },
469                 ..*terminator
470             }),
471             is_cleanup: true
472         });
473
474         let target = self.patch.new_block(BasicBlockData {
475             statements: vec![assign],
476             terminator: Some(Terminator {
477                 kind: TerminatorKind::Goto { target: target },
478                 ..*terminator
479             }),
480             is_cleanup: false,
481         });
482
483         match self.move_data().rev_lookup.find(location) {
484             LookupResult::Exact(path) => {
485                 debug!("elaborate_drop_and_replace({:?}) - tracked {:?}", terminator, path);
486                 let init_data = self.initialization_data_at(loc);
487
488                 elaborate_drop(
489                     &mut Elaborator {
490                         init_data: &init_data,
491                         ctxt: self
492                     },
493                     terminator.source_info,
494                     location,
495                     path,
496                     target,
497                     Unwind::To(unwind),
498                     bb);
499                 on_all_children_bits(self.tcx, self.mir, self.move_data(), path, |child| {
500                     self.set_drop_flag(Location { block: target, statement_index: 0 },
501                                        child, DropFlagState::Present);
502                     self.set_drop_flag(Location { block: unwind, statement_index: 0 },
503                                        child, DropFlagState::Present);
504                 });
505             }
506             LookupResult::Parent(parent) => {
507                 // drop and replace behind a pointer/array/whatever. The location
508                 // must be initialized.
509                 debug!("elaborate_drop_and_replace({:?}) - untracked {:?}", terminator, parent);
510                 self.patch.patch_terminator(bb, TerminatorKind::Drop {
511                     location: location.clone(),
512                     target,
513                     unwind: Some(unwind)
514                 });
515             }
516         }
517     }
518
519     fn constant_bool(&self, span: Span, val: bool) -> Rvalue<'tcx> {
520         Rvalue::Use(Operand::Constant(Box::new(Constant {
521             span,
522             ty: self.tcx.types.bool,
523             literal: Literal::Value {
524                 value: self.tcx.mk_const(ty::Const {
525                     val: ConstVal::Bool(val),
526                     ty: self.tcx.types.bool
527                 })
528             }
529         })))
530     }
531
532     fn set_drop_flag(&mut self, loc: Location, path: MovePathIndex, val: DropFlagState) {
533         if let Some(&flag) = self.drop_flags.get(&path) {
534             let span = self.patch.source_info_for_location(self.mir, loc).span;
535             let val = self.constant_bool(span, val.value());
536             self.patch.add_assign(loc, Lvalue::Local(flag), val);
537         }
538     }
539
540     fn drop_flags_on_init(&mut self) {
541         let loc = Location { block: START_BLOCK, statement_index: 0 };
542         let span = self.patch.source_info_for_location(self.mir, loc).span;
543         let false_ = self.constant_bool(span, false);
544         for flag in self.drop_flags.values() {
545             self.patch.add_assign(loc, Lvalue::Local(*flag), false_.clone());
546         }
547     }
548
549     fn drop_flags_for_fn_rets(&mut self) {
550         for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
551             if let TerminatorKind::Call {
552                 destination: Some((ref lv, tgt)), cleanup: Some(_), ..
553             } = data.terminator().kind {
554                 assert!(!self.patch.is_patched(bb));
555
556                 let loc = Location { block: tgt, statement_index: 0 };
557                 let path = self.move_data().rev_lookup.find(lv);
558                 on_lookup_result_bits(
559                     self.tcx, self.mir, self.move_data(), path,
560                     |child| self.set_drop_flag(loc, child, DropFlagState::Present)
561                 );
562             }
563         }
564     }
565
566     fn drop_flags_for_args(&mut self) {
567         let loc = Location { block: START_BLOCK, statement_index: 0 };
568         dataflow::drop_flag_effects_for_function_entry(
569             self.tcx, self.mir, self.env, |path, ds| {
570                 self.set_drop_flag(loc, path, ds);
571             }
572         )
573     }
574
575     fn drop_flags_for_locs(&mut self) {
576         // We intentionally iterate only over the *old* basic blocks.
577         //
578         // Basic blocks created by drop elaboration update their
579         // drop flags by themselves, to avoid the drop flags being
580         // clobbered before they are read.
581
582         for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
583             debug!("drop_flags_for_locs({:?})", data);
584             for i in 0..(data.statements.len()+1) {
585                 debug!("drop_flag_for_locs: stmt {}", i);
586                 let mut allow_initializations = true;
587                 if i == data.statements.len() {
588                     match data.terminator().kind {
589                         TerminatorKind::Drop { .. } => {
590                             // drop elaboration should handle that by itself
591                             continue
592                         }
593                         TerminatorKind::DropAndReplace { .. } => {
594                             // this contains the move of the source and
595                             // the initialization of the destination. We
596                             // only want the former - the latter is handled
597                             // by the elaboration code and must be done
598                             // *after* the destination is dropped.
599                             assert!(self.patch.is_patched(bb));
600                             allow_initializations = false;
601                         }
602                         TerminatorKind::Resume => {
603                             // It is possible for `Resume` to be patched
604                             // (in particular it can be patched to be replaced with
605                             // a Goto; see `MirPatch::new`).
606                         }
607                         _ => {
608                             assert!(!self.patch.is_patched(bb));
609                         }
610                     }
611                 }
612                 let loc = Location { block: bb, statement_index: i };
613                 dataflow::drop_flag_effects_for_location(
614                     self.tcx, self.mir, self.env, loc, |path, ds| {
615                         if ds == DropFlagState::Absent || allow_initializations {
616                             self.set_drop_flag(loc, path, ds)
617                         }
618                     }
619                 )
620             }
621
622             // There may be a critical edge after this call,
623             // so mark the return as initialized *before* the
624             // call.
625             if let TerminatorKind::Call {
626                 destination: Some((ref lv, _)), cleanup: None, ..
627             } = data.terminator().kind {
628                 assert!(!self.patch.is_patched(bb));
629
630                 let loc = Location { block: bb, statement_index: data.statements.len() };
631                 let path = self.move_data().rev_lookup.find(lv);
632                 on_lookup_result_bits(
633                     self.tcx, self.mir, self.move_data(), path,
634                     |child| self.set_drop_flag(loc, child, DropFlagState::Present)
635                 );
636             }
637         }
638     }
639 }