src/libcore/cell.rs

   1 // Copyright 2012-2013 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 //! Shareable mutable containers.
  12 //!
  13 //! Values of the `Cell` and `RefCell` types may be mutated through
  14 //! shared references (i.e. the common `&T` type), whereas most Rust
  15 //! types can only be mutated through unique (`&mut T`) references. We
  16 //! say that `Cell` and `RefCell` provide *interior mutability*, in
  17 //! contrast with typical Rust types that exhibit *inherited
  18 //! mutability*.
  19 //!
  20 //! Cell types come in two flavors: `Cell` and `RefCell`. `Cell`
  21 //! provides `get` and `set` methods that change the
  22 //! interior value with a single method call. `Cell` though is only
  23 //! compatible with types that implement `Copy`. For other types,
  24 //! one must use the `RefCell` type, acquiring a write lock before
  25 //! mutating.
  26 //!
  27 //! `RefCell` uses Rust's lifetimes to implement *dynamic borrowing*,
  28 //! a process whereby one can claim temporary, exclusive, mutable
  29 //! access to the inner value. Borrows for `RefCell`s are tracked *at
  30 //! runtime*, unlike Rust's native reference types which are entirely
  31 //! tracked statically, at compile time. Because `RefCell` borrows are
  32 //! dynamic it is possible to attempt to borrow a value that is
  33 //! already mutably borrowed; when this happens it results in task
  34 //! panic.
  35 //!
  36 //! # When to choose interior mutability
  37 //!
  38 //! The more common inherited mutability, where one must have unique
  39 //! access to mutate a value, is one of the key language elements that
  40 //! enables Rust to reason strongly about pointer aliasing, statically
  41 //! preventing crash bugs. Because of that, inherited mutability is
  42 //! preferred, and interior mutability is something of a last
  43 //! resort. Since cell types enable mutation where it would otherwise
  44 //! be disallowed though, there are occasions when interior
  45 //! mutability might be appropriate, or even *must* be used, e.g.
  46 //!
  47 //! * Introducing inherited mutability roots to shared types.
  48 //! * Implementation details of logically-immutable methods.
  49 //! * Mutating implementations of `clone`.
  50 //!
  51 //! ## Introducing inherited mutability roots to shared types
  52 //!
  53 //! Shared smart pointer types, including `Rc` and `Arc`, provide
  54 //! containers that can be cloned and shared between multiple parties.
  55 //! Because the contained values may be multiply-aliased, they can
  56 //! only be borrowed as shared references, not mutable references.
  57 //! Without cells it would be impossible to mutate data inside of
  58 //! shared boxes at all!
  59 //!
  60 //! It's very common then to put a `RefCell` inside shared pointer
  61 //! types to reintroduce mutability:
  62 //!
  63 //! ```
  64 //! use std::collections::HashMap;
  65 //! use std::cell::RefCell;
  66 //! use std::rc::Rc;
  67 //!
  68 //! fn main() {
  69 //!     let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
  70 //!     shared_map.borrow_mut().insert("africa", 92388i);
  71 //!     shared_map.borrow_mut().insert("kyoto", 11837i);
  72 //!     shared_map.borrow_mut().insert("piccadilly", 11826i);
  73 //!     shared_map.borrow_mut().insert("marbles", 38i);
  74 //! }
  75 //! ```
  76 //!
  77 //! ## Implementation details of logically-immutable methods
  78 //!
  79 //! Occasionally it may be desirable not to expose in an API that
  80 //! there is mutation happening "under the hood". This may be because
  81 //! logically the operation is immutable, but e.g. caching forces the
  82 //! implementation to perform mutation; or because you must employ
  83 //! mutation to implement a trait method that was originally defined
  84 //! to take `&self`.
  85 //!
  86 //! ```
  87 //! use std::cell::RefCell;
  88 //!
  89 //! struct Graph {
  90 //!     edges: Vec<(uint, uint)>,
  91 //!     span_tree_cache: RefCell<Option<Vec<(uint, uint)>>>
  92 //! }
  93 //!
  94 //! impl Graph {
  95 //!     fn minimum_spanning_tree(&self) -> Vec<(uint, uint)> {
  96 //!         // Create a new scope to contain the lifetime of the
  97 //!         // dynamic borrow
  98 //!         {
  99 //!             // Take a reference to the inside of cache cell
 100 //!             let mut cache = self.span_tree_cache.borrow_mut();
 101 //!             if cache.is_some() {
 102 //!                 return cache.as_ref().unwrap().clone();
 103 //!             }
 104 //!
 105 //!             let span_tree = self.calc_span_tree();
 106 //!             *cache = Some(span_tree);
 107 //!         }
 108 //!
 109 //!         // Recursive call to return the just-cached value.
 110 //!         // Note that if we had not let the previous borrow
 111 //!         // of the cache fall out of scope then the subsequent
 112 //!         // recursive borrow would cause a dynamic task panic.
 113 //!         // This is the major hazard of using `RefCell`.
 114 //!         self.minimum_spanning_tree()
 115 //!     }
 116 //! #   fn calc_span_tree(&self) -> Vec<(uint, uint)> { vec![] }
 117 //! }
 118 //! # fn main() { }
 119 //! ```
 120 //!
 121 //! ## Mutating implementations of `clone`
 122 //!
 123 //! This is simply a special - but common - case of the previous:
 124 //! hiding mutability for operations that appear to be immutable.
 125 //! The `clone` method is expected to not change the source value, and
 126 //! is declared to take `&self`, not `&mut self`. Therefore any
 127 //! mutation that happens in the `clone` method must use cell
 128 //! types. For example, `Rc` maintains its reference counts within a
 129 //! `Cell`.
 130 //!
 131 //! ```
 132 //! use std::cell::Cell;
 133 //!
 134 //! struct Rc<T> {
 135 //!     ptr: *mut RcBox<T>
 136 //! }
 137 //!
 138 //! struct RcBox<T> {
 139 //!     value: T,
 140 //!     refcount: Cell<uint>
 141 //! }
 142 //!
 143 //! impl<T> Clone for Rc<T> {
 144 //!     fn clone(&self) -> Rc<T> {
 145 //!         unsafe {
 146 //!             (*self.ptr).refcount.set((*self.ptr).refcount.get() + 1);
 147 //!             Rc { ptr: self.ptr }
 148 //!         }
 149 //!     }
 150 //! }
 151 //! ```
 152 //!
 153 // FIXME: Explain difference between Cell and RefCell
 154 // FIXME: Downsides to interior mutability
 155 // FIXME: Can't be shared between threads. Dynamic borrows
 156 // FIXME: Relationship to Atomic types and RWLock
 157
 158 #![stable]
 159
 160 use clone::Clone;
 161 use cmp::PartialEq;
 162 use default::Default;
 163 use fmt;
 164 use kinds::{Copy, Send};
 165 use ops::{Deref, DerefMut, Drop};
 166 use option::Option;
 167 use option::Option::{None, Some};
 168
 169 /// A mutable memory location that admits only `Copy` data.
 170 #[stable]
 171 pub struct Cell<T> {
 172     value: UnsafeCell<T>,
 173 }
 174
 175 impl<T:Copy> Cell<T> {
 176     /// Creates a new `Cell` containing the given value.
 177     #[stable]
 178     pub fn new(value: T) -> Cell<T> {
 179         Cell {
 180             value: UnsafeCell::new(value),
 181         }
 182     }
 183
 184     /// Returns a copy of the contained value.
 185     #[inline]
 186     #[stable]
 187     pub fn get(&self) -> T {
 188         unsafe{ *self.value.get() }
 189     }
 190
 191     /// Sets the contained value.
 192     #[inline]
 193     #[stable]
 194     pub fn set(&self, value: T) {
 195         unsafe {
 196             *self.value.get() = value;
 197         }
 198     }
 199
 200     /// Get a reference to the underlying `UnsafeCell`.
 201     ///
 202     /// This can be used to circumvent `Cell`'s safety checks.
 203     ///
 204     /// This function is `unsafe` because `UnsafeCell`'s field is public.
 205     #[inline]
 206     #[experimental]
 207     pub unsafe fn as_unsafe_cell<'a>(&'a self) -> &'a UnsafeCell<T> {
 208         &self.value
 209     }
 210 }
 211
 212 #[stable]
 213 unsafe impl<T> Send for Cell<T> where T: Send {}
 214
 215 #[stable]
 216 impl<T:Copy> Clone for Cell<T> {
 217     fn clone(&self) -> Cell<T> {
 218         Cell::new(self.get())
 219     }
 220 }
 221
 222 #[stable]
 223 impl<T:Default + Copy> Default for Cell<T> {
 224     #[stable]
 225     fn default() -> Cell<T> {
 226         Cell::new(Default::default())
 227     }
 228 }
 229
 230 #[stable]
 231 impl<T:PartialEq + Copy> PartialEq for Cell<T> {
 232     fn eq(&self, other: &Cell<T>) -> bool {
 233         self.get() == other.get()
 234     }
 235 }
 236
 237 /// A mutable memory location with dynamically checked borrow rules
 238 #[stable]
 239 pub struct RefCell<T> {
 240     value: UnsafeCell<T>,
 241     borrow: Cell<BorrowFlag>,
 242 }
 243
 244 // Values [1, MAX-1] represent the number of `Ref` active
 245 // (will not outgrow its range since `uint` is the size of the address space)
 246 type BorrowFlag = uint;
 247 const UNUSED: BorrowFlag = 0;
 248 const WRITING: BorrowFlag = -1;
 249
 250 impl<T> RefCell<T> {
 251     /// Create a new `RefCell` containing `value`
 252     #[stable]
 253     pub fn new(value: T) -> RefCell<T> {
 254         RefCell {
 255             value: UnsafeCell::new(value),
 256             borrow: Cell::new(UNUSED),
 257         }
 258     }
 259
 260     /// Consumes the `RefCell`, returning the wrapped value.
 261     #[stable]
 262     pub fn into_inner(self) -> T {
 263         // Since this function takes `self` (the `RefCell`) by value, the
 264         // compiler statically verifies that it is not currently borrowed.
 265         // Therefore the following assertion is just a `debug_assert!`.
 266         debug_assert!(self.borrow.get() == UNUSED);
 267         unsafe { self.value.into_inner() }
 268     }
 269
 270     /// Deprecated, use into_inner() instead
 271     #[deprecated = "renamed to into_inner()"]
 272     pub fn unwrap(self) -> T { self.into_inner() }
 273
 274     /// Attempts to immutably borrow the wrapped value.
 275     ///
 276     /// The borrow lasts until the returned `Ref` exits scope. Multiple
 277     /// immutable borrows can be taken out at the same time.
 278     ///
 279     /// Returns `None` if the value is currently mutably borrowed.
 280     #[unstable = "may be renamed or removed"]
 281     pub fn try_borrow<'a>(&'a self) -> Option<Ref<'a, T>> {
 282         match BorrowRef::new(&self.borrow) {
 283             Some(b) => Some(Ref { _value: unsafe { &*self.value.get() }, _borrow: b }),
 284             None => None,
 285         }
 286     }
 287
 288     /// Immutably borrows the wrapped value.
 289     ///
 290     /// The borrow lasts until the returned `Ref` exits scope. Multiple
 291     /// immutable borrows can be taken out at the same time.
 292     ///
 293     /// # Panics
 294     ///
 295     /// Panics if the value is currently mutably borrowed.
 296     #[stable]
 297     pub fn borrow<'a>(&'a self) -> Ref<'a, T> {
 298         match self.try_borrow() {
 299             Some(ptr) => ptr,
 300             None => panic!("RefCell<T> already mutably borrowed")
 301         }
 302     }
 303
 304     /// Mutably borrows the wrapped value.
 305     ///
 306     /// The borrow lasts until the returned `RefMut` exits scope. The value
 307     /// cannot be borrowed while this borrow is active.
 308     ///
 309     /// Returns `None` if the value is currently borrowed.
 310     #[unstable = "may be renamed or removed"]
 311     pub fn try_borrow_mut<'a>(&'a self) -> Option<RefMut<'a, T>> {
 312         match BorrowRefMut::new(&self.borrow) {
 313             Some(b) => Some(RefMut { _value: unsafe { &mut *self.value.get() }, _borrow: b }),
 314             None => None,
 315         }
 316     }
 317
 318     /// Mutably borrows the wrapped value.
 319     ///
 320     /// The borrow lasts until the returned `RefMut` exits scope. The value
 321     /// cannot be borrowed while this borrow is active.
 322     ///
 323     /// # Panics
 324     ///
 325     /// Panics if the value is currently borrowed.
 326     #[stable]
 327     pub fn borrow_mut<'a>(&'a self) -> RefMut<'a, T> {
 328         match self.try_borrow_mut() {
 329             Some(ptr) => ptr,
 330             None => panic!("RefCell<T> already borrowed")
 331         }
 332     }
 333
 334     /// Get a reference to the underlying `UnsafeCell`.
 335     ///
 336     /// This can be used to circumvent `RefCell`'s safety checks.
 337     ///
 338     /// This function is `unsafe` because `UnsafeCell`'s field is public.
 339     #[inline]
 340     #[experimental]
 341     pub unsafe fn as_unsafe_cell<'a>(&'a self) -> &'a UnsafeCell<T> {
 342         &self.value
 343     }
 344 }
 345
 346 #[stable]
 347 unsafe impl<T> Send for RefCell<T> where T: Send {}
 348
 349 #[stable]
 350 impl<T: Clone> Clone for RefCell<T> {
 351     fn clone(&self) -> RefCell<T> {
 352         RefCell::new(self.borrow().clone())
 353     }
 354 }
 355
 356 #[stable]
 357 impl<T:Default> Default for RefCell<T> {
 358     #[stable]
 359     fn default() -> RefCell<T> {
 360         RefCell::new(Default::default())
 361     }
 362 }
 363
 364 #[stable]
 365 impl<T: PartialEq> PartialEq for RefCell<T> {
 366     fn eq(&self, other: &RefCell<T>) -> bool {
 367         *self.borrow() == *other.borrow()
 368     }
 369 }
 370
 371 #[unstable]
 372 impl<T:fmt::Show> fmt::Show for RefCell<T> {
 373     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 374         match self.try_borrow() {
 375             Some(val) => write!(f, "{}", val),
 376             None => write!(f, "<borrowed RefCell>")
 377         }
 378     }
 379 }
 380
 381 struct BorrowRef<'b> {
 382     _borrow: &'b Cell<BorrowFlag>,
 383 }
 384
 385 impl<'b> BorrowRef<'b> {
 386     fn new(borrow: &'b Cell<BorrowFlag>) -> Option<BorrowRef<'b>> {
 387         match borrow.get() {
 388             WRITING => None,
 389             b => {
 390                 borrow.set(b + 1);
 391                 Some(BorrowRef { _borrow: borrow })
 392             },
 393         }
 394     }
 395 }
 396
 397 #[unsafe_destructor]
 398 impl<'b> Drop for BorrowRef<'b> {
 399     fn drop(&mut self) {
 400         let borrow = self._borrow.get();
 401         debug_assert!(borrow != WRITING && borrow != UNUSED);
 402         self._borrow.set(borrow - 1);
 403     }
 404 }
 405
 406 impl<'b> Clone for BorrowRef<'b> {
 407     fn clone(&self) -> BorrowRef<'b> {
 408         // Since this Ref exists, we know the borrow flag
 409         // is not set to WRITING.
 410         let borrow = self._borrow.get();
 411         debug_assert!(borrow != WRITING && borrow != UNUSED);
 412         self._borrow.set(borrow + 1);
 413         BorrowRef { _borrow: self._borrow }
 414     }
 415 }
 416
 417 /// Wraps a borrowed reference to a value in a `RefCell` box.
 418 #[stable]
 419 pub struct Ref<'b, T:'b> {
 420     // FIXME #12808: strange name to try to avoid interfering with
 421     // field accesses of the contained type via Deref
 422     _value: &'b T,
 423     _borrow: BorrowRef<'b>,
 424 }
 425
 426 #[unstable = "waiting for `Deref` to become stable"]
 427 impl<'b, T> Deref for Ref<'b, T> {
 428     type Target = T;
 429
 430     #[inline]
 431     fn deref<'a>(&'a self) -> &'a T {
 432         self._value
 433     }
 434 }
 435
 436 /// Copy a `Ref`.
 437 ///
 438 /// The `RefCell` is already immutably borrowed, so this cannot fail.
 439 ///
 440 /// A `Clone` implementation would interfere with the widespread
 441 /// use of `r.borrow().clone()` to clone the contents of a `RefCell`.
 442 #[experimental = "likely to be moved to a method, pending language changes"]
 443 pub fn clone_ref<'b, T:Clone>(orig: &Ref<'b, T>) -> Ref<'b, T> {
 444     Ref {
 445         _value: orig._value,
 446         _borrow: orig._borrow.clone(),
 447     }
 448 }
 449
 450 struct BorrowRefMut<'b> {
 451     _borrow: &'b Cell<BorrowFlag>,
 452 }
 453
 454 #[unsafe_destructor]
 455 impl<'b> Drop for BorrowRefMut<'b> {
 456     fn drop(&mut self) {
 457         let borrow = self._borrow.get();
 458         debug_assert!(borrow == WRITING);
 459         self._borrow.set(UNUSED);
 460     }
 461 }
 462
 463 impl<'b> BorrowRefMut<'b> {
 464     fn new(borrow: &'b Cell<BorrowFlag>) -> Option<BorrowRefMut<'b>> {
 465         match borrow.get() {
 466             UNUSED => {
 467                 borrow.set(WRITING);
 468                 Some(BorrowRefMut { _borrow: borrow })
 469             },
 470             _ => None,
 471         }
 472     }
 473 }
 474
 475 /// Wraps a mutable borrowed reference to a value in a `RefCell` box.
 476 #[stable]
 477 pub struct RefMut<'b, T:'b> {
 478     // FIXME #12808: strange name to try to avoid interfering with
 479     // field accesses of the contained type via Deref
 480     _value: &'b mut T,
 481     _borrow: BorrowRefMut<'b>,
 482 }
 483
 484 #[unstable = "waiting for `Deref` to become stable"]
 485 impl<'b, T> Deref for RefMut<'b, T> {
 486     type Target = T;
 487
 488     #[inline]
 489     fn deref<'a>(&'a self) -> &'a T {
 490         self._value
 491     }
 492 }
 493
 494 #[unstable = "waiting for `DerefMut` to become stable"]
 495 impl<'b, T> DerefMut for RefMut<'b, T> {
 496     #[inline]
 497     fn deref_mut<'a>(&'a mut self) -> &'a mut T {
 498         self._value
 499     }
 500 }
 501
 502 /// The core primitive for interior mutability in Rust.
 503 ///
 504 /// `UnsafeCell` type that wraps a type T and indicates unsafe interior
 505 /// operations on the wrapped type. Types with an `UnsafeCell<T>` field are
 506 /// considered to have an *unsafe interior*. The `UnsafeCell` type is the only
 507 /// legal way to obtain aliasable data that is considered mutable. In general,
 508 /// transmuting an &T type into an &mut T is considered undefined behavior.
 509 ///
 510 /// Although it is possible to put an `UnsafeCell<T>` into static item, it is
 511 /// not permitted to take the address of the static item if the item is not
 512 /// declared as mutable. This rule exists because immutable static items are
 513 /// stored in read-only memory, and thus any attempt to mutate their interior
 514 /// can cause segfaults. Immutable static items containing `UnsafeCell<T>`
 515 /// instances are still useful as read-only initializers, however, so we do not
 516 /// forbid them altogether.
 517 ///
 518 /// Types like `Cell` and `RefCell` use this type to wrap their internal data.
 519 ///
 520 /// `UnsafeCell` doesn't opt-out from any kind, instead, types with an
 521 /// `UnsafeCell` interior are expected to opt-out from kinds themselves.
 522 ///
 523 /// # Example:
 524 ///
 525 /// ```rust
 526 /// use std::cell::UnsafeCell;
 527 /// use std::kinds::marker;
 528 ///
 529 /// struct NotThreadSafe<T> {
 530 ///     value: UnsafeCell<T>,
 531 ///     marker: marker::NoSync
 532 /// }
 533 /// ```
 534 ///
 535 /// **NOTE:** `UnsafeCell<T>` fields are public to allow static initializers. It
 536 /// is not recommended to access its fields directly, `get` should be used
 537 /// instead.
 538 #[lang="unsafe"]
 539 #[stable]
 540 pub struct UnsafeCell<T> {
 541     /// Wrapped value
 542     ///
 543     /// This field should not be accessed directly, it is made public for static
 544     /// initializers.
 545     #[unstable]
 546     pub value: T,
 547 }
 548
 549 impl<T> UnsafeCell<T> {
 550     /// Construct a new instance of `UnsafeCell` which will wrap the specified
 551     /// value.
 552     ///
 553     /// All access to the inner value through methods is `unsafe`, and it is
 554     /// highly discouraged to access the fields directly.
 555     #[stable]
 556     pub fn new(value: T) -> UnsafeCell<T> {
 557         UnsafeCell { value: value }
 558     }
 559
 560     /// Gets a mutable pointer to the wrapped value.
 561     #[inline]
 562     #[stable]
 563     pub fn get(&self) -> *mut T { &self.value as *const T as *mut T }
 564
 565     /// Unwraps the value
 566     ///
 567     /// This function is unsafe because there is no guarantee that this or other
 568     /// tasks are currently inspecting the inner value.
 569     #[inline]
 570     #[stable]
 571     pub unsafe fn into_inner(self) -> T { self.value }
 572
 573     /// Deprecated, use into_inner() instead
 574     #[deprecated = "renamed to into_inner()"]
 575     pub unsafe fn unwrap(self) -> T { self.into_inner() }
 576 }