src/memory.rs

   1 use byteorder::{NativeEndian, ReadBytesExt, WriteBytesExt};
   2 use std::collections::Bound::{Included, Excluded};
   3 use std::collections::{btree_map, BTreeMap, HashMap, HashSet, VecDeque};
   4 use std::{fmt, iter, mem, ptr};
   5
   6 use rustc::hir::def_id::DefId;
   7 use rustc::ty::BareFnTy;
   8 use rustc::ty::subst::Substs;
   9
  10 use error::{EvalError, EvalResult};
  11 use primval::PrimVal;
  12
  13 ////////////////////////////////////////////////////////////////////////////////
  14 // Allocations and pointers
  15 ////////////////////////////////////////////////////////////////////////////////
  16
  17 #[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
  18 pub struct AllocId(u64);
  19
  20 impl fmt::Display for AllocId {
  21     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  22         write!(f, "{}", self.0)
  23     }
  24 }
  25
  26 #[derive(Debug)]
  27 pub struct Allocation {
  28     pub bytes: Vec<u8>,
  29     pub relocations: BTreeMap<usize, AllocId>,
  30     pub undef_mask: UndefMask,
  31 }
  32
  33 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
  34 pub struct Pointer {
  35     pub alloc_id: AllocId,
  36     pub offset: usize,
  37 }
  38
  39 impl Pointer {
  40     pub fn offset(self, i: isize) -> Self {
  41         Pointer { offset: (self.offset as isize + i) as usize, ..self }
  42     }
  43 }
  44
  45 #[derive(Debug, Copy, Clone)]
  46 pub struct FunctionDefinition<'tcx> {
  47     pub def_id: DefId,
  48     pub substs: &'tcx Substs<'tcx>,
  49     pub fn_ty: &'tcx BareFnTy<'tcx>,
  50 }
  51
  52 ////////////////////////////////////////////////////////////////////////////////
  53 // Top-level interpreter memory
  54 ////////////////////////////////////////////////////////////////////////////////
  55
  56 pub struct Memory<'tcx> {
  57     /// Actual memory allocations (arbitrary bytes, may contain pointers into other allocations)
  58     alloc_map: HashMap<AllocId, Allocation>,
  59     /// Function "allocations". They exist solely so pointers have something to point to, and
  60     /// we can figure out what they point to.
  61     functions: HashMap<AllocId, FunctionDefinition<'tcx>>,
  62     next_id: AllocId,
  63     pub pointer_size: usize,
  64 }
  65
  66 impl<'tcx> Memory<'tcx> {
  67     // FIXME: pass tcx.data_layout (This would also allow it to use primitive type alignments to diagnose unaligned memory accesses.)
  68     pub fn new(pointer_size: usize) -> Self {
  69         Memory {
  70             alloc_map: HashMap::new(),
  71             functions: HashMap::new(),
  72             next_id: AllocId(0),
  73             pointer_size: pointer_size,
  74         }
  75     }
  76
  77     // FIXME: never create two pointers to the same def_id + substs combination
  78     // maybe re-use the statics cache of the EvalContext?
  79     pub fn create_fn_ptr(&mut self, def_id: DefId, substs: &'tcx Substs<'tcx>, fn_ty: &'tcx BareFnTy<'tcx>) -> Pointer {
  80         let id = self.next_id;
  81         debug!("creating fn ptr: {}", id);
  82         self.next_id.0 += 1;
  83         self.functions.insert(id, FunctionDefinition {
  84             def_id: def_id,
  85             substs: substs,
  86             fn_ty: fn_ty,
  87         });
  88         Pointer {
  89             alloc_id: id,
  90             offset: 0,
  91         }
  92     }
  93
  94     pub fn allocate(&mut self, size: usize) -> Pointer {
  95         let alloc = Allocation {
  96             bytes: vec![0; size],
  97             relocations: BTreeMap::new(),
  98             undef_mask: UndefMask::new(size),
  99         };
 100         let id = self.next_id;
 101         self.next_id.0 += 1;
 102         self.alloc_map.insert(id, alloc);
 103         Pointer {
 104             alloc_id: id,
 105             offset: 0,
 106         }
 107     }
 108
 109     // TODO(solson): Track which allocations were returned from __rust_allocate and report an error
 110     // when reallocating/deallocating any others.
 111     pub fn reallocate(&mut self, ptr: Pointer, new_size: usize) -> EvalResult<'tcx, ()> {
 112         if ptr.offset != 0 {
 113             // TODO(solson): Report error about non-__rust_allocate'd pointer.
 114             return Err(EvalError::Unimplemented(format!("bad pointer offset: {}", ptr.offset)));
 115         }
 116
 117         let size = self.get_mut(ptr.alloc_id)?.bytes.len();
 118
 119         if new_size > size {
 120             let amount = new_size - size;
 121             let alloc = self.get_mut(ptr.alloc_id)?;
 122             alloc.bytes.extend(iter::repeat(0).take(amount));
 123             alloc.undef_mask.grow(amount, false);
 124         } else if size > new_size {
 125             self.clear_relocations(ptr.offset(new_size as isize), size - new_size)?;
 126             let alloc = self.get_mut(ptr.alloc_id)?;
 127             alloc.bytes.truncate(new_size);
 128             alloc.undef_mask.truncate(new_size);
 129         }
 130
 131         Ok(())
 132     }
 133
 134     // TODO(solson): See comment on `reallocate`.
 135     pub fn deallocate(&mut self, ptr: Pointer) -> EvalResult<'tcx, ()> {
 136         if ptr.offset != 0 {
 137             // TODO(solson): Report error about non-__rust_allocate'd pointer.
 138             return Err(EvalError::Unimplemented(format!("bad pointer offset: {}", ptr.offset)));
 139         }
 140
 141         if self.alloc_map.remove(&ptr.alloc_id).is_none() {
 142             // TODO(solson): Report error about erroneous free. This is blocked on properly tracking
 143             // already-dropped state since this if-statement is entered even in safe code without
 144             // it.
 145         }
 146
 147         Ok(())
 148     }
 149
 150     ////////////////////////////////////////////////////////////////////////////////
 151     // Allocation accessors
 152     ////////////////////////////////////////////////////////////////////////////////
 153
 154     pub fn get(&self, id: AllocId) -> EvalResult<'tcx, &Allocation> {
 155         match self.alloc_map.get(&id) {
 156             Some(alloc) => Ok(alloc),
 157             None => match self.functions.get(&id) {
 158                 Some(_) => Err(EvalError::DerefFunctionPointer),
 159                 None => Err(EvalError::DanglingPointerDeref),
 160             }
 161         }
 162     }
 163
 164     pub fn get_mut(&mut self, id: AllocId) -> EvalResult<'tcx, &mut Allocation> {
 165         match self.alloc_map.get_mut(&id) {
 166             Some(alloc) => Ok(alloc),
 167             None => match self.functions.get(&id) {
 168                 Some(_) => Err(EvalError::DerefFunctionPointer),
 169                 None => Err(EvalError::DanglingPointerDeref),
 170             }
 171         }
 172     }
 173
 174     pub fn get_fn(&self, id: AllocId) -> EvalResult<'tcx, FunctionDefinition<'tcx>> {
 175         debug!("reading fn ptr: {}", id);
 176         match self.functions.get(&id) {
 177             Some(&fn_id) => Ok(fn_id),
 178             None => match self.alloc_map.get(&id) {
 179                 Some(_) => Err(EvalError::ExecuteMemory),
 180                 None => Err(EvalError::InvalidFunctionPointer),
 181             }
 182         }
 183     }
 184
 185     /// Print an allocation and all allocations it points to, recursively.
 186     pub fn dump(&self, id: AllocId) {
 187         let mut allocs_seen = HashSet::new();
 188         let mut allocs_to_print = VecDeque::new();
 189         allocs_to_print.push_back(id);
 190
 191         while let Some(id) = allocs_to_print.pop_front() {
 192             allocs_seen.insert(id);
 193             let prefix = format!("Alloc {:<5} ", format!("{}:", id));
 194             print!("{}", prefix);
 195             let mut relocations = vec![];
 196
 197             let alloc = match (self.alloc_map.get(&id), self.functions.get(&id)) {
 198                 (Some(a), None) => a,
 199                 (None, Some(_)) => {
 200                     // FIXME: print function name
 201                     println!("function pointer");
 202                     continue;
 203                 },
 204                 (None, None) => {
 205                     println!("(deallocated)");
 206                     continue;
 207                 },
 208                 (Some(_), Some(_)) => unreachable!(),
 209             };
 210
 211             for i in 0..alloc.bytes.len() {
 212                 if let Some(&target_id) = alloc.relocations.get(&i) {
 213                     if !allocs_seen.contains(&target_id) {
 214                         allocs_to_print.push_back(target_id);
 215                     }
 216                     relocations.push((i, target_id));
 217                 }
 218                 if alloc.undef_mask.is_range_defined(i, i + 1) {
 219                     print!("{:02x} ", alloc.bytes[i]);
 220                 } else {
 221                     print!("__ ");
 222                 }
 223             }
 224             println!("({} bytes)", alloc.bytes.len());
 225
 226             if !relocations.is_empty() {
 227                 print!("{:1$}", "", prefix.len()); // Print spaces.
 228                 let mut pos = 0;
 229                 let relocation_width = (self.pointer_size - 1) * 3;
 230                 for (i, target_id) in relocations {
 231                     print!("{:1$}", "", (i - pos) * 3);
 232                     print!("└{0:─^1$}┘ ", format!("({})", target_id), relocation_width);
 233                     pos = i + self.pointer_size;
 234                 }
 235                 println!("");
 236             }
 237         }
 238     }
 239
 240     ////////////////////////////////////////////////////////////////////////////////
 241     // Byte accessors
 242     ////////////////////////////////////////////////////////////////////////////////
 243
 244     fn get_bytes_unchecked(&self, ptr: Pointer, size: usize) -> EvalResult<'tcx, &[u8]> {
 245         let alloc = self.get(ptr.alloc_id)?;
 246         if ptr.offset + size > alloc.bytes.len() {
 247             return Err(EvalError::PointerOutOfBounds {
 248                 ptr: ptr,
 249                 size: size,
 250                 allocation_size: alloc.bytes.len(),
 251             });
 252         }
 253         Ok(&alloc.bytes[ptr.offset..ptr.offset + size])
 254     }
 255
 256     fn get_bytes_unchecked_mut(&mut self, ptr: Pointer, size: usize) -> EvalResult<'tcx, &mut [u8]> {
 257         let alloc = self.get_mut(ptr.alloc_id)?;
 258         if ptr.offset + size > alloc.bytes.len() {
 259             return Err(EvalError::PointerOutOfBounds {
 260                 ptr: ptr,
 261                 size: size,
 262                 allocation_size: alloc.bytes.len(),
 263             });
 264         }
 265         Ok(&mut alloc.bytes[ptr.offset..ptr.offset + size])
 266     }
 267
 268     fn get_bytes(&self, ptr: Pointer, size: usize) -> EvalResult<'tcx, &[u8]> {
 269         if self.relocations(ptr, size)?.count() != 0 {
 270             return Err(EvalError::ReadPointerAsBytes);
 271         }
 272         self.check_defined(ptr, size)?;
 273         self.get_bytes_unchecked(ptr, size)
 274     }
 275
 276     fn get_bytes_mut(&mut self, ptr: Pointer, size: usize) -> EvalResult<'tcx, &mut [u8]> {
 277         self.clear_relocations(ptr, size)?;
 278         self.mark_definedness(ptr, size, true)?;
 279         self.get_bytes_unchecked_mut(ptr, size)
 280     }
 281
 282     ////////////////////////////////////////////////////////////////////////////////
 283     // Reading and writing
 284     ////////////////////////////////////////////////////////////////////////////////
 285
 286     pub fn copy(&mut self, src: Pointer, dest: Pointer, size: usize) -> EvalResult<'tcx, ()> {
 287         self.check_relocation_edges(src, size)?;
 288
 289         let src_bytes = self.get_bytes_unchecked_mut(src, size)?.as_mut_ptr();
 290         let dest_bytes = self.get_bytes_mut(dest, size)?.as_mut_ptr();
 291
 292         // SAFE: The above indexing would have panicked if there weren't at least `size` bytes
 293         // behind `src` and `dest`. Also, we use the overlapping-safe `ptr::copy` if `src` and
 294         // `dest` could possibly overlap.
 295         unsafe {
 296             if src.alloc_id == dest.alloc_id {
 297                 ptr::copy(src_bytes, dest_bytes, size);
 298             } else {
 299                 ptr::copy_nonoverlapping(src_bytes, dest_bytes, size);
 300             }
 301         }
 302
 303         self.copy_undef_mask(src, dest, size)?;
 304         self.copy_relocations(src, dest, size)?;
 305
 306         Ok(())
 307     }
 308
 309     pub fn read_bytes(&self, ptr: Pointer, size: usize) -> EvalResult<'tcx, &[u8]> {
 310         self.get_bytes(ptr, size)
 311     }
 312
 313     pub fn write_bytes(&mut self, ptr: Pointer, src: &[u8]) -> EvalResult<'tcx, ()> {
 314         let bytes = self.get_bytes_mut(ptr, src.len())?;
 315         bytes.clone_from_slice(src);
 316         Ok(())
 317     }
 318
 319     pub fn write_repeat(&mut self, ptr: Pointer, val: u8, count: usize) -> EvalResult<'tcx, ()> {
 320         let bytes = self.get_bytes_mut(ptr, count)?;
 321         for b in bytes { *b = val; }
 322         Ok(())
 323     }
 324
 325     pub fn drop_fill(&mut self, ptr: Pointer, size: usize) -> EvalResult<'tcx, ()> {
 326         self.write_repeat(ptr, mem::POST_DROP_U8, size)
 327     }
 328
 329     pub fn read_ptr(&self, ptr: Pointer) -> EvalResult<'tcx, Pointer> {
 330         let size = self.pointer_size;
 331         self.check_defined(ptr, size)?;
 332         let offset = self.get_bytes_unchecked(ptr, size)?
 333             .read_uint::<NativeEndian>(size).unwrap() as usize;
 334         let alloc = self.get(ptr.alloc_id)?;
 335         match alloc.relocations.get(&ptr.offset) {
 336             Some(&alloc_id) => Ok(Pointer { alloc_id: alloc_id, offset: offset }),
 337             None => Err(EvalError::ReadBytesAsPointer),
 338         }
 339     }
 340
 341     pub fn write_ptr(&mut self, dest: Pointer, ptr: Pointer) -> EvalResult<'tcx, ()> {
 342         {
 343             let size = self.pointer_size;
 344             let mut bytes = self.get_bytes_mut(dest, size)?;
 345             bytes.write_uint::<NativeEndian>(ptr.offset as u64, size).unwrap();
 346         }
 347         self.get_mut(dest.alloc_id)?.relocations.insert(dest.offset, ptr.alloc_id);
 348         Ok(())
 349     }
 350
 351     pub fn write_primval(&mut self, ptr: Pointer, val: PrimVal) -> EvalResult<'tcx, ()> {
 352         let pointer_size = self.pointer_size;
 353         match val {
 354             PrimVal::Bool(b) => self.write_bool(ptr, b),
 355             PrimVal::I8(n)   => self.write_int(ptr, n as i64, 1),
 356             PrimVal::I16(n)  => self.write_int(ptr, n as i64, 2),
 357             PrimVal::I32(n)  => self.write_int(ptr, n as i64, 4),
 358             PrimVal::I64(n)  => self.write_int(ptr, n as i64, 8),
 359             PrimVal::U8(n)   => self.write_uint(ptr, n as u64, 1),
 360             PrimVal::U16(n)  => self.write_uint(ptr, n as u64, 2),
 361             PrimVal::U32(n)  => self.write_uint(ptr, n as u64, 4),
 362             PrimVal::U64(n)  => self.write_uint(ptr, n as u64, 8),
 363             PrimVal::IntegerPtr(n) => self.write_uint(ptr, n as u64, pointer_size),
 364             PrimVal::AbstractPtr(_p) => unimplemented!(),
 365         }
 366     }
 367
 368     pub fn read_bool(&self, ptr: Pointer) -> EvalResult<'tcx, bool> {
 369         let bytes = self.get_bytes(ptr, 1)?;
 370         match bytes[0] {
 371             0 => Ok(false),
 372             1 => Ok(true),
 373             _ => Err(EvalError::InvalidBool),
 374         }
 375     }
 376
 377     pub fn write_bool(&mut self, ptr: Pointer, b: bool) -> EvalResult<'tcx, ()> {
 378         self.get_bytes_mut(ptr, 1).map(|bytes| bytes[0] = b as u8)
 379     }
 380
 381     pub fn read_int(&self, ptr: Pointer, size: usize) -> EvalResult<'tcx, i64> {
 382         self.get_bytes(ptr, size).map(|mut b| b.read_int::<NativeEndian>(size).unwrap())
 383     }
 384
 385     pub fn write_int(&mut self, ptr: Pointer, n: i64, size: usize) -> EvalResult<'tcx, ()> {
 386         self.get_bytes_mut(ptr, size).map(|mut b| b.write_int::<NativeEndian>(n, size).unwrap())
 387     }
 388
 389     pub fn read_uint(&self, ptr: Pointer, size: usize) -> EvalResult<'tcx, u64> {
 390         self.get_bytes(ptr, size).map(|mut b| b.read_uint::<NativeEndian>(size).unwrap())
 391     }
 392
 393     pub fn write_uint(&mut self, ptr: Pointer, n: u64, size: usize) -> EvalResult<'tcx, ()> {
 394         self.get_bytes_mut(ptr, size).map(|mut b| b.write_uint::<NativeEndian>(n, size).unwrap())
 395     }
 396
 397     pub fn read_isize(&self, ptr: Pointer) -> EvalResult<'tcx, i64> {
 398         self.read_int(ptr, self.pointer_size)
 399     }
 400
 401     pub fn write_isize(&mut self, ptr: Pointer, n: i64) -> EvalResult<'tcx, ()> {
 402         let size = self.pointer_size;
 403         self.write_int(ptr, n, size)
 404     }
 405
 406     pub fn read_usize(&self, ptr: Pointer) -> EvalResult<'tcx, u64> {
 407         self.read_uint(ptr, self.pointer_size)
 408     }
 409
 410     pub fn write_usize(&mut self, ptr: Pointer, n: u64) -> EvalResult<'tcx, ()> {
 411         let size = self.pointer_size;
 412         self.write_uint(ptr, n, size)
 413     }
 414
 415     ////////////////////////////////////////////////////////////////////////////////
 416     // Relocations
 417     ////////////////////////////////////////////////////////////////////////////////
 418
 419     fn relocations(&self, ptr: Pointer, size: usize)
 420         -> EvalResult<'tcx, btree_map::Range<usize, AllocId>>
 421     {
 422         let start = ptr.offset.saturating_sub(self.pointer_size - 1);
 423         let end = ptr.offset + size;
 424         Ok(self.get(ptr.alloc_id)?.relocations.range(Included(&start), Excluded(&end)))
 425     }
 426
 427     fn clear_relocations(&mut self, ptr: Pointer, size: usize) -> EvalResult<'tcx, ()> {
 428         // Find all relocations overlapping the given range.
 429         let keys: Vec<_> = self.relocations(ptr, size)?.map(|(&k, _)| k).collect();
 430         if keys.is_empty() { return Ok(()); }
 431
 432         // Find the start and end of the given range and its outermost relocations.
 433         let start = ptr.offset;
 434         let end = start + size;
 435         let first = *keys.first().unwrap();
 436         let last = *keys.last().unwrap() + self.pointer_size;
 437
 438         let alloc = self.get_mut(ptr.alloc_id)?;
 439
 440         // Mark parts of the outermost relocations as undefined if they partially fall outside the
 441         // given range.
 442         if first < start { alloc.undef_mask.set_range(first, start, false); }
 443         if last > end { alloc.undef_mask.set_range(end, last, false); }
 444
 445         // Forget all the relocations.
 446         for k in keys { alloc.relocations.remove(&k); }
 447
 448         Ok(())
 449     }
 450
 451     fn check_relocation_edges(&self, ptr: Pointer, size: usize) -> EvalResult<'tcx, ()> {
 452         let overlapping_start = self.relocations(ptr, 0)?.count();
 453         let overlapping_end = self.relocations(ptr.offset(size as isize), 0)?.count();
 454         if overlapping_start + overlapping_end != 0 {
 455             return Err(EvalError::ReadPointerAsBytes);
 456         }
 457         Ok(())
 458     }
 459
 460     fn copy_relocations(&mut self, src: Pointer, dest: Pointer, size: usize) -> EvalResult<'tcx, ()> {
 461         let relocations: Vec<_> = self.relocations(src, size)?
 462             .map(|(&offset, &alloc_id)| {
 463                 // Update relocation offsets for the new positions in the destination allocation.
 464                 (offset + dest.offset - src.offset, alloc_id)
 465             })
 466             .collect();
 467         self.get_mut(dest.alloc_id)?.relocations.extend(relocations);
 468         Ok(())
 469     }
 470
 471     ////////////////////////////////////////////////////////////////////////////////
 472     // Undefined bytes
 473     ////////////////////////////////////////////////////////////////////////////////
 474
 475     // FIXME(solson): This is a very naive, slow version.
 476     fn copy_undef_mask(&mut self, src: Pointer, dest: Pointer, size: usize) -> EvalResult<'tcx, ()> {
 477         // The bits have to be saved locally before writing to dest in case src and dest overlap.
 478         let mut v = Vec::with_capacity(size);
 479         for i in 0..size {
 480             let defined = self.get(src.alloc_id)?.undef_mask.get(src.offset + i);
 481             v.push(defined);
 482         }
 483         for (i, defined) in v.into_iter().enumerate() {
 484             self.get_mut(dest.alloc_id)?.undef_mask.set(dest.offset + i, defined);
 485         }
 486         Ok(())
 487     }
 488
 489     fn check_defined(&self, ptr: Pointer, size: usize) -> EvalResult<'tcx, ()> {
 490         let alloc = self.get(ptr.alloc_id)?;
 491         if !alloc.undef_mask.is_range_defined(ptr.offset, ptr.offset + size) {
 492             return Err(EvalError::ReadUndefBytes);
 493         }
 494         Ok(())
 495     }
 496
 497     pub fn mark_definedness(&mut self, ptr: Pointer, size: usize, new_state: bool)
 498         -> EvalResult<'tcx, ()>
 499     {
 500         let mut alloc = self.get_mut(ptr.alloc_id)?;
 501         alloc.undef_mask.set_range(ptr.offset, ptr.offset + size, new_state);
 502         Ok(())
 503     }
 504 }
 505
 506 ////////////////////////////////////////////////////////////////////////////////
 507 // Undefined byte tracking
 508 ////////////////////////////////////////////////////////////////////////////////
 509
 510 type Block = u64;
 511 const BLOCK_SIZE: usize = 64;
 512
 513 #[derive(Clone, Debug)]
 514 pub struct UndefMask {
 515     blocks: Vec<Block>,
 516     len: usize,
 517 }
 518
 519 impl UndefMask {
 520     fn new(size: usize) -> Self {
 521         let mut m = UndefMask {
 522             blocks: vec![],
 523             len: 0,
 524         };
 525         m.grow(size, false);
 526         m
 527     }
 528
 529     /// Check whether the range `start..end` (end-exclusive) is entirely defined.
 530     fn is_range_defined(&self, start: usize, end: usize) -> bool {
 531         if end > self.len { return false; }
 532         for i in start..end {
 533             if !self.get(i) { return false; }
 534         }
 535         true
 536     }
 537
 538     fn set_range(&mut self, start: usize, end: usize, new_state: bool) {
 539         let len = self.len;
 540         if end > len { self.grow(end - len, new_state); }
 541         self.set_range_inbounds(start, end, new_state);
 542     }
 543
 544     fn set_range_inbounds(&mut self, start: usize, end: usize, new_state: bool) {
 545         for i in start..end { self.set(i, new_state); }
 546     }
 547
 548     fn get(&self, i: usize) -> bool {
 549         let (block, bit) = bit_index(i);
 550         (self.blocks[block] & 1 << bit) != 0
 551     }
 552
 553     fn set(&mut self, i: usize, new_state: bool) {
 554         let (block, bit) = bit_index(i);
 555         if new_state {
 556             self.blocks[block] |= 1 << bit;
 557         } else {
 558             self.blocks[block] &= !(1 << bit);
 559         }
 560     }
 561
 562     fn grow(&mut self, amount: usize, new_state: bool) {
 563         let unused_trailing_bits = self.blocks.len() * BLOCK_SIZE - self.len;
 564         if amount > unused_trailing_bits {
 565             let additional_blocks = amount / BLOCK_SIZE + 1;
 566             self.blocks.extend(iter::repeat(0).take(additional_blocks));
 567         }
 568         let start = self.len;
 569         self.len += amount;
 570         self.set_range_inbounds(start, start + amount, new_state);
 571     }
 572
 573     fn truncate(&mut self, length: usize) {
 574         self.len = length;
 575         self.blocks.truncate(self.len / BLOCK_SIZE + 1);
 576     }
 577 }
 578
 579 fn bit_index(bits: usize) -> (usize, usize) {
 580     (bits / BLOCK_SIZE, bits % BLOCK_SIZE)
 581 }