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