src/librustc_trans/trans/tvec.rs

   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.
   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 #![allow(non_camel_case_types)]
  12
  13 use back::abi;
  14 use llvm;
  15 use llvm::ValueRef;
  16 use trans::base::*;
  17 use trans::base;
  18 use trans::build::*;
  19 use trans::cleanup;
  20 use trans::cleanup::CleanupMethods;
  21 use trans::common::*;
  22 use trans::consts;
  23 use trans::datum::*;
  24 use trans::debuginfo::DebugLoc;
  25 use trans::expr::{Dest, Ignore, SaveIn};
  26 use trans::expr;
  27 use trans::machine::llsize_of_alloc;
  28 use trans::type_::Type;
  29 use trans::type_of;
  30 use middle::ty::{self, Ty};
  31
  32 use syntax::ast;
  33 use syntax::parse::token::InternedString;
  34
  35 #[derive(Copy, Clone)]
  36 struct VecTypes<'tcx> {
  37     unit_ty: Ty<'tcx>,
  38     llunit_ty: Type
  39 }
  40
  41 impl<'tcx> VecTypes<'tcx> {
  42     pub fn to_string<'a>(&self, ccx: &CrateContext<'a, 'tcx>) -> String {
  43         format!("VecTypes {{unit_ty={}, llunit_ty={}}}",
  44                 self.unit_ty,
  45                 ccx.tn().type_to_string(self.llunit_ty))
  46     }
  47 }
  48
  49 pub fn trans_fixed_vstore<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
  50                                       expr: &ast::Expr,
  51                                       dest: expr::Dest)
  52                                       -> Block<'blk, 'tcx> {
  53     //!
  54     //
  55     // [...] allocates a fixed-size array and moves it around "by value".
  56     // In this case, it means that the caller has already given us a location
  57     // to store the array of the suitable size, so all we have to do is
  58     // generate the content.
  59
  60     debug!("trans_fixed_vstore(expr={:?}, dest={})",
  61            expr, dest.to_string(bcx.ccx()));
  62
  63     let vt = vec_types_from_expr(bcx, expr);
  64
  65     return match dest {
  66         Ignore => write_content(bcx, &vt, expr, expr, dest),
  67         SaveIn(lldest) => {
  68             // lldest will have type *[T x N], but we want the type *T,
  69             // so use GEP to convert:
  70             let lldest = GEPi(bcx, lldest, &[0, 0]);
  71             write_content(bcx, &vt, expr, expr, SaveIn(lldest))
  72         }
  73     };
  74 }
  75
  76 /// &[...] allocates memory on the stack and writes the values into it, returning the vector (the
  77 /// caller must make the reference).  "..." is similar except that the memory can be statically
  78 /// allocated and we return a reference (strings are always by-ref).
  79 pub fn trans_slice_vec<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
  80                                    slice_expr: &ast::Expr,
  81                                    content_expr: &ast::Expr)
  82                                    -> DatumBlock<'blk, 'tcx, Expr> {
  83     let fcx = bcx.fcx;
  84     let ccx = fcx.ccx;
  85     let mut bcx = bcx;
  86
  87     debug!("trans_slice_vec(slice_expr={:?})",
  88            slice_expr);
  89
  90     let vec_ty = node_id_type(bcx, slice_expr.id);
  91
  92     // Handle the "..." case (returns a slice since strings are always unsized):
  93     if let ast::ExprLit(ref lit) = content_expr.node {
  94         if let ast::LitStr(ref s, _) = lit.node {
  95             let scratch = rvalue_scratch_datum(bcx, vec_ty, "");
  96             bcx = trans_lit_str(bcx,
  97                                 content_expr,
  98                                 s.clone(),
  99                                 SaveIn(scratch.val));
 100             return DatumBlock::new(bcx, scratch.to_expr_datum());
 101         }
 102     }
 103
 104     // Handle the &[...] case:
 105     let vt = vec_types_from_expr(bcx, content_expr);
 106     let count = elements_required(bcx, content_expr);
 107     debug!("    vt={}, count={}", vt.to_string(ccx), count);
 108
 109     let fixed_ty = ty::mk_vec(bcx.tcx(),
 110                               vt.unit_ty,
 111                               Some(count));
 112     let llfixed_ty = type_of::type_of(bcx.ccx(), fixed_ty);
 113
 114     // Always create an alloca even if zero-sized, to preserve
 115     // the non-null invariant of the inner slice ptr
 116     let llfixed = base::alloca(bcx, llfixed_ty, "");
 117
 118     if count > 0 {
 119         // Arrange for the backing array to be cleaned up.
 120         let cleanup_scope = cleanup::temporary_scope(bcx.tcx(), content_expr.id);
 121         fcx.schedule_lifetime_end(cleanup_scope, llfixed);
 122         fcx.schedule_drop_mem(cleanup_scope, llfixed, fixed_ty);
 123
 124         // Generate the content into the backing array.
 125         // llfixed has type *[T x N], but we want the type *T,
 126         // so use GEP to convert
 127         bcx = write_content(bcx, &vt, slice_expr, content_expr,
 128                             SaveIn(GEPi(bcx, llfixed, &[0, 0])));
 129     };
 130
 131     immediate_rvalue_bcx(bcx, llfixed, vec_ty).to_expr_datumblock()
 132 }
 133
 134 /// Literal strings translate to slices into static memory.  This is different from
 135 /// trans_slice_vstore() above because it doesn't need to copy the content anywhere.
 136 pub fn trans_lit_str<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 137                                  lit_expr: &ast::Expr,
 138                                  str_lit: InternedString,
 139                                  dest: Dest)
 140                                  -> Block<'blk, 'tcx> {
 141     debug!("trans_lit_str(lit_expr={:?}, dest={})",
 142            lit_expr,
 143            dest.to_string(bcx.ccx()));
 144
 145     match dest {
 146         Ignore => bcx,
 147         SaveIn(lldest) => {
 148             let bytes = str_lit.len();
 149             let llbytes = C_uint(bcx.ccx(), bytes);
 150             let llcstr = C_cstr(bcx.ccx(), str_lit, false);
 151             let llcstr = consts::ptrcast(llcstr, Type::i8p(bcx.ccx()));
 152             Store(bcx, llcstr, GEPi(bcx, lldest, &[0, abi::FAT_PTR_ADDR]));
 153             Store(bcx, llbytes, GEPi(bcx, lldest, &[0, abi::FAT_PTR_EXTRA]));
 154             bcx
 155         }
 156     }
 157 }
 158
 159 fn write_content<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 160                              vt: &VecTypes<'tcx>,
 161                              vstore_expr: &ast::Expr,
 162                              content_expr: &ast::Expr,
 163                              dest: Dest)
 164                              -> Block<'blk, 'tcx> {
 165     let _icx = push_ctxt("tvec::write_content");
 166     let fcx = bcx.fcx;
 167     let mut bcx = bcx;
 168
 169     debug!("write_content(vt={}, dest={}, vstore_expr={:?})",
 170            vt.to_string(bcx.ccx()),
 171            dest.to_string(bcx.ccx()),
 172            vstore_expr);
 173
 174     match content_expr.node {
 175         ast::ExprLit(ref lit) => {
 176             match lit.node {
 177                 ast::LitStr(ref s, _) => {
 178                     match dest {
 179                         Ignore => return bcx,
 180                         SaveIn(lldest) => {
 181                             let bytes = s.len();
 182                             let llbytes = C_uint(bcx.ccx(), bytes);
 183                             let llcstr = C_cstr(bcx.ccx(), (*s).clone(), false);
 184                             base::call_memcpy(bcx,
 185                                               lldest,
 186                                               llcstr,
 187                                               llbytes,
 188                                               1);
 189                             return bcx;
 190                         }
 191                     }
 192                 }
 193                 _ => {
 194                     bcx.tcx().sess.span_bug(content_expr.span,
 195                                             "unexpected evec content");
 196                 }
 197             }
 198         }
 199         ast::ExprVec(ref elements) => {
 200             match dest {
 201                 Ignore => {
 202                     for element in elements {
 203                         bcx = expr::trans_into(bcx, &**element, Ignore);
 204                     }
 205                 }
 206
 207                 SaveIn(lldest) => {
 208                     let temp_scope = fcx.push_custom_cleanup_scope();
 209                     for (i, element) in elements.iter().enumerate() {
 210                         let lleltptr = GEPi(bcx, lldest, &[i]);
 211                         debug!("writing index {} with lleltptr={}",
 212                                i, bcx.val_to_string(lleltptr));
 213                         bcx = expr::trans_into(bcx, &**element,
 214                                                SaveIn(lleltptr));
 215                         let scope = cleanup::CustomScope(temp_scope);
 216                         fcx.schedule_lifetime_end(scope, lleltptr);
 217                         fcx.schedule_drop_mem(scope, lleltptr, vt.unit_ty);
 218                     }
 219                     fcx.pop_custom_cleanup_scope(temp_scope);
 220                 }
 221             }
 222             return bcx;
 223         }
 224         ast::ExprRepeat(ref element, ref count_expr) => {
 225             match dest {
 226                 Ignore => {
 227                     return expr::trans_into(bcx, &**element, Ignore);
 228                 }
 229                 SaveIn(lldest) => {
 230                     match ty::eval_repeat_count(bcx.tcx(), &**count_expr) {
 231                         0 => expr::trans_into(bcx, &**element, Ignore),
 232                         1 => expr::trans_into(bcx, &**element, SaveIn(lldest)),
 233                         count => {
 234                             let elem = unpack_datum!(bcx, expr::trans(bcx, &**element));
 235                             let bcx = iter_vec_loop(bcx, lldest, vt,
 236                                                     C_uint(bcx.ccx(), count),
 237                                                     |set_bcx, lleltptr, _| {
 238                                                         elem.shallow_copy(set_bcx, lleltptr)
 239                                                     });
 240                             bcx
 241                         }
 242                     }
 243                 }
 244             }
 245         }
 246         _ => {
 247             bcx.tcx().sess.span_bug(content_expr.span,
 248                                     "unexpected vec content");
 249         }
 250     }
 251 }
 252
 253 fn vec_types_from_expr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, vec_expr: &ast::Expr)
 254                                    -> VecTypes<'tcx> {
 255     let vec_ty = node_id_type(bcx, vec_expr.id);
 256     vec_types(bcx, ty::sequence_element_type(bcx.tcx(), vec_ty))
 257 }
 258
 259 fn vec_types<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, unit_ty: Ty<'tcx>)
 260                          -> VecTypes<'tcx> {
 261     VecTypes {
 262         unit_ty: unit_ty,
 263         llunit_ty: type_of::type_of(bcx.ccx(), unit_ty)
 264     }
 265 }
 266
 267 fn elements_required(bcx: Block, content_expr: &ast::Expr) -> usize {
 268     //! Figure out the number of elements we need to store this content
 269
 270     match content_expr.node {
 271         ast::ExprLit(ref lit) => {
 272             match lit.node {
 273                 ast::LitStr(ref s, _) => s.len(),
 274                 _ => {
 275                     bcx.tcx().sess.span_bug(content_expr.span,
 276                                             "unexpected evec content")
 277                 }
 278             }
 279         },
 280         ast::ExprVec(ref es) => es.len(),
 281         ast::ExprRepeat(_, ref count_expr) => {
 282             ty::eval_repeat_count(bcx.tcx(), &**count_expr)
 283         }
 284         _ => bcx.tcx().sess.span_bug(content_expr.span,
 285                                      "unexpected vec content")
 286     }
 287 }
 288
 289 /// Converts a fixed-length vector into the slice pair. The vector should be stored in `llval`
 290 /// which should be by ref.
 291 pub fn get_fixed_base_and_len(bcx: Block,
 292                               llval: ValueRef,
 293                               vec_length: usize)
 294                               -> (ValueRef, ValueRef) {
 295     let ccx = bcx.ccx();
 296
 297     let base = expr::get_dataptr(bcx, llval);
 298     let len = C_uint(ccx, vec_length);
 299     (base, len)
 300 }
 301
 302 /// Converts a vector into the slice pair.  The vector should be stored in `llval` which should be
 303 /// by-reference.  If you have a datum, you would probably prefer to call
 304 /// `Datum::get_base_and_len()` which will handle any conversions for you.
 305 pub fn get_base_and_len<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 306                                     llval: ValueRef,
 307                                     vec_ty: Ty<'tcx>)
 308                                     -> (ValueRef, ValueRef) {
 309     let ccx = bcx.ccx();
 310
 311     match vec_ty.sty {
 312         ty::TyArray(_, n) => get_fixed_base_and_len(bcx, llval, n),
 313         ty::TySlice(_) | ty::TyStr => {
 314             let base = Load(bcx, expr::get_dataptr(bcx, llval));
 315             let len = Load(bcx, expr::get_len(bcx, llval));
 316             (base, len)
 317         }
 318
 319         // Only used for pattern matching.
 320         ty::TyBox(ty) | ty::TyRef(_, ty::mt{ty, ..}) => {
 321             let inner = if type_is_sized(bcx.tcx(), ty) {
 322                 Load(bcx, llval)
 323             } else {
 324                 llval
 325             };
 326             get_base_and_len(bcx, inner, ty)
 327         },
 328         _ => ccx.sess().bug("unexpected type in get_base_and_len"),
 329     }
 330 }
 331
 332 fn iter_vec_loop<'blk, 'tcx, F>(bcx: Block<'blk, 'tcx>,
 333                                 data_ptr: ValueRef,
 334                                 vt: &VecTypes<'tcx>,
 335                                 count: ValueRef,
 336                                 f: F)
 337                                 -> Block<'blk, 'tcx> where
 338     F: FnOnce(Block<'blk, 'tcx>, ValueRef, Ty<'tcx>) -> Block<'blk, 'tcx>,
 339 {
 340     let _icx = push_ctxt("tvec::iter_vec_loop");
 341
 342     if bcx.unreachable.get() {
 343         return bcx;
 344     }
 345
 346     let fcx = bcx.fcx;
 347     let loop_bcx = fcx.new_temp_block("expr_repeat");
 348     let next_bcx = fcx.new_temp_block("expr_repeat: next");
 349
 350     Br(bcx, loop_bcx.llbb, DebugLoc::None);
 351
 352     let loop_counter = Phi(loop_bcx, bcx.ccx().int_type(),
 353                            &[C_uint(bcx.ccx(), 0 as usize)], &[bcx.llbb]);
 354
 355     let bcx = loop_bcx;
 356
 357     let lleltptr = if llsize_of_alloc(bcx.ccx(), vt.llunit_ty) == 0 {
 358         data_ptr
 359     } else {
 360         InBoundsGEP(bcx, data_ptr, &[loop_counter])
 361     };
 362     let bcx = f(bcx, lleltptr, vt.unit_ty);
 363     let plusone = Add(bcx, loop_counter, C_uint(bcx.ccx(), 1usize), DebugLoc::None);
 364     AddIncomingToPhi(loop_counter, plusone, bcx.llbb);
 365
 366     let cond_val = ICmp(bcx, llvm::IntULT, plusone, count, DebugLoc::None);
 367     CondBr(bcx, cond_val, loop_bcx.llbb, next_bcx.llbb, DebugLoc::None);
 368
 369     next_bcx
 370 }
 371
 372 pub fn iter_vec_raw<'blk, 'tcx, F>(bcx: Block<'blk, 'tcx>,
 373                                    data_ptr: ValueRef,
 374                                    unit_ty: Ty<'tcx>,
 375                                    len: ValueRef,
 376                                    f: F)
 377                                    -> Block<'blk, 'tcx> where
 378     F: FnOnce(Block<'blk, 'tcx>, ValueRef, Ty<'tcx>) -> Block<'blk, 'tcx>,
 379 {
 380     let _icx = push_ctxt("tvec::iter_vec_raw");
 381     let fcx = bcx.fcx;
 382
 383     let vt = vec_types(bcx, unit_ty);
 384
 385     if llsize_of_alloc(bcx.ccx(), vt.llunit_ty) == 0 {
 386         // Special-case vectors with elements of size 0  so they don't go out of bounds (#9890)
 387         iter_vec_loop(bcx, data_ptr, &vt, len, f)
 388     } else {
 389         // Calculate the last pointer address we want to handle.
 390         let data_end_ptr = InBoundsGEP(bcx, data_ptr, &[len]);
 391
 392         // Now perform the iteration.
 393         let header_bcx = fcx.new_temp_block("iter_vec_loop_header");
 394         Br(bcx, header_bcx.llbb, DebugLoc::None);
 395         let data_ptr =
 396             Phi(header_bcx, val_ty(data_ptr), &[data_ptr], &[bcx.llbb]);
 397         let not_yet_at_end =
 398             ICmp(header_bcx, llvm::IntULT, data_ptr, data_end_ptr, DebugLoc::None);
 399         let body_bcx = fcx.new_temp_block("iter_vec_loop_body");
 400         let next_bcx = fcx.new_temp_block("iter_vec_next");
 401         CondBr(header_bcx, not_yet_at_end, body_bcx.llbb, next_bcx.llbb, DebugLoc::None);
 402         let body_bcx = f(body_bcx, data_ptr, unit_ty);
 403         AddIncomingToPhi(data_ptr, InBoundsGEP(body_bcx, data_ptr,
 404                                                &[C_int(bcx.ccx(), 1)]),
 405                          body_bcx.llbb);
 406         Br(body_bcx, header_bcx.llbb, DebugLoc::None);
 407         next_bcx
 408     }
 409 }