diff options
| author | Mathieu David <mathieudavid@mathieudavid.org> | 2015-07-27 20:46:01 +0200 |
|---|---|---|
| committer | Mathieu David <mathieudavid@mathieudavid.org> | 2015-07-27 20:46:01 +0200 |
| commit | f6e9240a99e86d2c799dc29f179dd2870e51f71d (patch) | |
| tree | a7e5ba20745b16949a45a4612b2708e262693a7b /src/libcore | |
| parent | 003c3eaa62981b791f9eb7bcad015baa1e00d98c (diff) | |
| parent | 3351afeecffcc9ebaeb1188a5cde976da8e4a5aa (diff) | |
| download | rust-f6e9240a99e86d2c799dc29f179dd2870e51f71d.tar.gz rust-f6e9240a99e86d2c799dc29f179dd2870e51f71d.zip | |
Fix the relative path issue by including the files using include_bytes!
Diffstat (limited to 'src/libcore')
37 files changed, 1648 insertions, 729 deletions
diff --git a/src/libcore/any.rs b/src/libcore/any.rs index f0c77ae866d..e7b39c11f4c 100644 --- a/src/libcore/any.rs +++ b/src/libcore/any.rs @@ -8,15 +8,13 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -//! Traits for dynamic typing of any `'static` type (through runtime reflection) -//! //! This module implements the `Any` trait, which enables dynamic typing //! of any `'static` type through runtime reflection. //! //! `Any` itself can be used to get a `TypeId`, and has more features when used //! as a trait object. As `&Any` (a borrowed trait object), it has the `is` and //! `as_ref` methods, to test if the contained value is of a given type, and to -//! get a reference to the inner value as a type. As`&mut Any`, there is also +//! get a reference to the inner value as a type. As `&mut Any`, there is also //! the `as_mut` method, for getting a mutable reference to the inner value. //! `Box<Any>` adds the `move` method, which will unwrap a `Box<T>` from the //! object. See the extension traits (`*Ext`) for the full details. diff --git a/src/libcore/array.rs b/src/libcore/array.rs index a9b240de30b..cfe22b89178 100644 --- a/src/libcore/array.rs +++ b/src/libcore/array.rs @@ -11,8 +11,9 @@ //! Implementations of things like `Eq` for fixed-length arrays //! up to a certain length. Eventually we should able to generalize //! to all lengths. +//! +//! *[See also the array primitive type](../primitive.array.html).* -#![doc(primitive = "array")] #![unstable(feature = "fixed_size_array", reason = "traits and impls are better expressed through generic \ integer constants")] diff --git a/src/libcore/atomic.rs b/src/libcore/atomic.rs index 1b8ee8db5f4..c6434e71957 100644 --- a/src/libcore/atomic.rs +++ b/src/libcore/atomic.rs @@ -78,6 +78,7 @@ use intrinsics; use cell::UnsafeCell; use default::Default; +use fmt; /// A boolean type which can be safely shared between threads. #[stable(feature = "rust1", since = "1.0.0")] @@ -272,13 +273,13 @@ impl AtomicBool { unsafe { atomic_swap(self.v.get(), val, order) > 0 } } - /// Stores a value into the bool if the current value is the same as the expected value. + /// Stores a value into the `bool` if the current value is the same as the `current` value. /// - /// The return value is always the previous value. If it is equal to `old`, then the value was - /// updated. + /// The return value is always the previous value. If it is equal to `current`, then the value + /// was updated. /// - /// `swap` also takes an `Ordering` argument which describes the memory ordering of this - /// operation. + /// `compare_and_swap` also takes an `Ordering` argument which describes the memory ordering of + /// this operation. /// /// # Examples /// @@ -295,11 +296,11 @@ impl AtomicBool { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn compare_and_swap(&self, old: bool, new: bool, order: Ordering) -> bool { - let old = if old { UINT_TRUE } else { 0 }; + pub fn compare_and_swap(&self, current: bool, new: bool, order: Ordering) -> bool { + let current = if current { UINT_TRUE } else { 0 }; let new = if new { UINT_TRUE } else { 0 }; - unsafe { atomic_compare_and_swap(self.v.get(), old, new, order) > 0 } + unsafe { atomic_compare_and_swap(self.v.get(), current, new, order) > 0 } } /// Logical "and" with a boolean value. @@ -515,10 +516,10 @@ impl AtomicIsize { unsafe { atomic_swap(self.v.get(), val, order) } } - /// Stores a value into the isize if the current value is the same as the expected value. + /// Stores a value into the `isize` if the current value is the same as the `current` value. /// - /// The return value is always the previous value. If it is equal to `old`, then the value was - /// updated. + /// The return value is always the previous value. If it is equal to `current`, then the value + /// was updated. /// /// `compare_and_swap` also takes an `Ordering` argument which describes the memory ordering of /// this operation. @@ -538,8 +539,8 @@ impl AtomicIsize { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn compare_and_swap(&self, old: isize, new: isize, order: Ordering) -> isize { - unsafe { atomic_compare_and_swap(self.v.get(), old, new, order) } + pub fn compare_and_swap(&self, current: isize, new: isize, order: Ordering) -> isize { + unsafe { atomic_compare_and_swap(self.v.get(), current, new, order) } } /// Add an isize to the current value, returning the previous value. @@ -709,10 +710,10 @@ impl AtomicUsize { unsafe { atomic_swap(self.v.get(), val, order) } } - /// Stores a value into the usize if the current value is the same as the expected value. + /// Stores a value into the `usize` if the current value is the same as the `current` value. /// - /// The return value is always the previous value. If it is equal to `old`, then the value was - /// updated. + /// The return value is always the previous value. If it is equal to `current`, then the value + /// was updated. /// /// `compare_and_swap` also takes an `Ordering` argument which describes the memory ordering of /// this operation. @@ -732,8 +733,8 @@ impl AtomicUsize { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn compare_and_swap(&self, old: usize, new: usize, order: Ordering) -> usize { - unsafe { atomic_compare_and_swap(self.v.get(), old, new, order) } + pub fn compare_and_swap(&self, current: usize, new: usize, order: Ordering) -> usize { + unsafe { atomic_compare_and_swap(self.v.get(), current, new, order) } } /// Add to the current usize, returning the previous value. @@ -910,10 +911,10 @@ impl<T> AtomicPtr<T> { unsafe { atomic_swap(self.p.get() as *mut usize, ptr as usize, order) as *mut T } } - /// Stores a value into the pointer if the current value is the same as the expected value. + /// Stores a value into the pointer if the current value is the same as the `current` value. /// - /// The return value is always the previous value. If it is equal to `old`, then the value was - /// updated. + /// The return value is always the previous value. If it is equal to `current`, then the value + /// was updated. /// /// `compare_and_swap` also takes an `Ordering` argument which describes the memory ordering of /// this operation. @@ -933,9 +934,9 @@ impl<T> AtomicPtr<T> { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] - pub fn compare_and_swap(&self, old: *mut T, new: *mut T, order: Ordering) -> *mut T { + pub fn compare_and_swap(&self, current: *mut T, new: *mut T, order: Ordering) -> *mut T { unsafe { - atomic_compare_and_swap(self.p.get() as *mut usize, old as usize, + atomic_compare_and_swap(self.p.get() as *mut usize, current as usize, new as usize, order) as *mut T } } @@ -953,7 +954,6 @@ unsafe fn atomic_store<T>(dst: *mut T, val: T, order:Ordering) { } #[inline] -#[stable(feature = "rust1", since = "1.0.0")] unsafe fn atomic_load<T>(dst: *const T, order:Ordering) -> T { match order { Acquire => intrinsics::atomic_load_acq(dst), @@ -965,7 +965,6 @@ unsafe fn atomic_load<T>(dst: *const T, order:Ordering) -> T { } #[inline] -#[stable(feature = "rust1", since = "1.0.0")] unsafe fn atomic_swap<T>(dst: *mut T, val: T, order: Ordering) -> T { match order { Acquire => intrinsics::atomic_xchg_acq(dst, val), @@ -978,7 +977,6 @@ unsafe fn atomic_swap<T>(dst: *mut T, val: T, order: Ordering) -> T { /// Returns the old value (like __sync_fetch_and_add). #[inline] -#[stable(feature = "rust1", since = "1.0.0")] unsafe fn atomic_add<T>(dst: *mut T, val: T, order: Ordering) -> T { match order { Acquire => intrinsics::atomic_xadd_acq(dst, val), @@ -991,7 +989,6 @@ unsafe fn atomic_add<T>(dst: *mut T, val: T, order: Ordering) -> T { /// Returns the old value (like __sync_fetch_and_sub). #[inline] -#[stable(feature = "rust1", since = "1.0.0")] unsafe fn atomic_sub<T>(dst: *mut T, val: T, order: Ordering) -> T { match order { Acquire => intrinsics::atomic_xsub_acq(dst, val), @@ -1003,7 +1000,6 @@ unsafe fn atomic_sub<T>(dst: *mut T, val: T, order: Ordering) -> T { } #[inline] -#[stable(feature = "rust1", since = "1.0.0")] unsafe fn atomic_compare_and_swap<T>(dst: *mut T, old:T, new:T, order: Ordering) -> T { match order { Acquire => intrinsics::atomic_cxchg_acq(dst, old, new), @@ -1015,7 +1011,6 @@ unsafe fn atomic_compare_and_swap<T>(dst: *mut T, old:T, new:T, order: Ordering) } #[inline] -#[stable(feature = "rust1", since = "1.0.0")] unsafe fn atomic_and<T>(dst: *mut T, val: T, order: Ordering) -> T { match order { Acquire => intrinsics::atomic_and_acq(dst, val), @@ -1027,7 +1022,6 @@ unsafe fn atomic_and<T>(dst: *mut T, val: T, order: Ordering) -> T { } #[inline] -#[stable(feature = "rust1", since = "1.0.0")] unsafe fn atomic_nand<T>(dst: *mut T, val: T, order: Ordering) -> T { match order { Acquire => intrinsics::atomic_nand_acq(dst, val), @@ -1040,7 +1034,6 @@ unsafe fn atomic_nand<T>(dst: *mut T, val: T, order: Ordering) -> T { #[inline] -#[stable(feature = "rust1", since = "1.0.0")] unsafe fn atomic_or<T>(dst: *mut T, val: T, order: Ordering) -> T { match order { Acquire => intrinsics::atomic_or_acq(dst, val), @@ -1053,7 +1046,6 @@ unsafe fn atomic_or<T>(dst: *mut T, val: T, order: Ordering) -> T { #[inline] -#[stable(feature = "rust1", since = "1.0.0")] unsafe fn atomic_xor<T>(dst: *mut T, val: T, order: Ordering) -> T { match order { Acquire => intrinsics::atomic_xor_acq(dst, val), @@ -1098,3 +1090,23 @@ pub fn fence(order: Ordering) { } } } + +macro_rules! impl_Debug { + ($($t:ident)*) => ($( + #[stable(feature = "atomic_debug", since = "1.3.0")] + impl fmt::Debug for $t { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_tuple(stringify!($t)).field(&self.load(Ordering::SeqCst)).finish() + } + } + )*); +} + +impl_Debug!{ AtomicUsize AtomicIsize AtomicBool } + +#[stable(feature = "atomic_debug", since = "1.3.0")] +impl<T> fmt::Debug for AtomicPtr<T> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_tuple("AtomicPtr").field(&self.load(Ordering::SeqCst)).finish() + } +} diff --git a/src/libcore/cell.rs b/src/libcore/cell.rs index 37f37654c1f..2c4ebeafc0b 100644 --- a/src/libcore/cell.rs +++ b/src/libcore/cell.rs @@ -36,16 +36,16 @@ //! would otherwise be disallowed though, there are occasions when interior mutability might be //! appropriate, or even *must* be used, e.g. //! -//! * Introducing inherited mutability roots to shared types. +//! * Introducing mutability 'inside' of something immutable //! * Implementation details of logically-immutable methods. //! * Mutating implementations of `Clone`. //! -//! ## Introducing inherited mutability roots to shared types +//! ## Introducing mutability 'inside' of something immutable //! -//! Shared smart pointer types, including `Rc<T>` and `Arc<T>`, provide containers that can be +//! Many shared smart pointer types, including `Rc<T>` and `Arc<T>`, provide containers that can be //! cloned and shared between multiple parties. Because the contained values may be -//! multiply-aliased, they can only be borrowed as shared references, not mutable references. -//! Without cells it would be impossible to mutate data inside of shared boxes at all! +//! multiply-aliased, they can only be borrowed with `&`, not `&mut`. Without cells it would be +//! impossible to mutate data inside of these smart pointers at all. //! //! It's very common then to put a `RefCell<T>` inside shared pointer types to reintroduce //! mutability: @@ -65,8 +65,8 @@ //! ``` //! //! Note that this example uses `Rc<T>` and not `Arc<T>`. `RefCell<T>`s are for single-threaded -//! scenarios. Consider using `Mutex<T>` if you need shared mutability in a multi-threaded -//! situation. +//! scenarios. Consider using `RwLock<T>` or `Mutex<T>` if you need shared mutability in a +//! multi-threaded situation. //! //! ## Implementation details of logically-immutable methods //! diff --git a/src/libcore/char.rs b/src/libcore/char.rs index 12aa06667a1..c6d0e97a0cd 100644 --- a/src/libcore/char.rs +++ b/src/libcore/char.rs @@ -13,7 +13,6 @@ //! For more details, see ::rustc_unicode::char (a.k.a. std::char) #![allow(non_snake_case)] -#![doc(primitive = "char")] #![stable(feature = "core_char", since = "1.2.0")] use iter::Iterator; @@ -85,10 +84,18 @@ pub fn from_u32(i: u32) -> Option<char> { if (i > MAX as u32) || (i >= 0xD800 && i <= 0xDFFF) { None } else { - Some(unsafe { transmute(i) }) + Some(unsafe { from_u32_unchecked(i) }) } } +/// Converts a `u32` to an `char`, not checking whether it is a valid unicode +/// codepoint. +#[inline] +#[unstable(feature = "char_from_unchecked", reason = "recently added API")] +pub unsafe fn from_u32_unchecked(i: u32) -> char { + transmute(i) +} + /// Converts a number to the character representing it. /// /// # Return value @@ -116,12 +123,11 @@ pub fn from_digit(num: u32, radix: u32) -> Option<char> { panic!("from_digit: radix is too high (maximum 36)"); } if num < radix { - unsafe { - if num < 10 { - Some(transmute('0' as u32 + num)) - } else { - Some(transmute('a' as u32 + num - 10)) - } + let num = num as u8; + if num < 10 { + Some((b'0' + num) as char) + } else { + Some((b'a' + num - 10) as char) } } else { None @@ -319,16 +325,13 @@ impl Iterator for EscapeUnicode { Some('{') } EscapeUnicodeState::Value(offset) => { - let v = match ((self.c as i32) >> (offset * 4)) & 0xf { - i @ 0 ... 9 => '0' as i32 + i, - i => 'a' as i32 + (i - 10) - }; + let c = from_digit(((self.c as u32) >> (offset * 4)) & 0xf, 16).unwrap(); if offset == 0 { self.state = EscapeUnicodeState::RightBrace; } else { self.state = EscapeUnicodeState::Value(offset - 1); } - Some(unsafe { transmute(v) }) + Some(c) } EscapeUnicodeState::RightBrace => { self.state = EscapeUnicodeState::Done; diff --git a/src/libcore/cmp.rs b/src/libcore/cmp.rs index 0269499ad54..52ed29c1b61 100644 --- a/src/libcore/cmp.rs +++ b/src/libcore/cmp.rs @@ -166,6 +166,8 @@ impl Ordering { /// /// - total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is true; and /// - transitive, `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`. +/// +/// When this trait is `derive`d, it produces a lexicographic ordering. #[stable(feature = "rust1", since = "1.0.0")] pub trait Ord: Eq + PartialOrd<Self> { /// This method returns an `Ordering` between `self` and `other`. diff --git a/src/libcore/fmt/builders.rs b/src/libcore/fmt/builders.rs index 32d6aa19c64..22f0215f0ad 100644 --- a/src/libcore/fmt/builders.rs +++ b/src/libcore/fmt/builders.rs @@ -175,6 +175,12 @@ impl<'a, 'b: 'a> DebugTuple<'a, 'b> { fn is_pretty(&self) -> bool { self.fmt.flags() & (1 << (FlagV1::Alternate as usize)) != 0 } + + /// Returns the wrapped `Formatter`. + #[unstable(feature = "debug_builder_formatter", reason = "recently added")] + pub fn formatter(&mut self) -> &mut fmt::Formatter<'b> { + &mut self.fmt + } } struct DebugInner<'a, 'b: 'a> { diff --git a/src/libcore/fmt/mod.rs b/src/libcore/fmt/mod.rs index cbbb186af76..29a2f76ef29 100644 --- a/src/libcore/fmt/mod.rs +++ b/src/libcore/fmt/mod.rs @@ -267,11 +267,18 @@ impl<'a> Display for Arguments<'a> { } } -/// Format trait for the `:?` format. Useful for debugging, all types -/// should implement this. +/// Format trait for the `?` character. +/// +/// `Debug` should format the output in a programmer-facing, debugging context. /// /// Generally speaking, you should just `derive` a `Debug` implementation. /// +/// When used with the alternate format specifier `#?`, the output is pretty-printed. +/// +/// For more information on formatters, see [the module-level documentation][module]. +/// +/// [module]: ../index.html +/// /// # Examples /// /// Deriving an implementation: @@ -309,10 +316,42 @@ impl<'a> Display for Arguments<'a> { /// println!("The origin is: {:?}", origin); /// ``` /// +/// This outputs: +/// +/// ```text +/// The origin is: Point { x: 0, y: 0 } +/// ``` +/// /// There are a number of `debug_*` methods on `Formatter` to help you with manual /// implementations, such as [`debug_struct`][debug_struct]. /// +/// `Debug` implementations using either `derive` or the debug builder API +/// on `Formatter` support pretty printing using the alternate flag: `{:#?}`. +/// /// [debug_struct]: ../std/fmt/struct.Formatter.html#method.debug_struct +/// +/// Pretty printing with `#?`: +/// +/// ``` +/// #[derive(Debug)] +/// struct Point { +/// x: i32, +/// y: i32, +/// } +/// +/// let origin = Point { x: 0, y: 0 }; +/// +/// println!("The origin is: {:#?}", origin); +/// ``` +/// +/// This outputs: +/// +/// ```text +/// The origin is: Point { +/// x: 0, +/// y: 0 +/// } +/// ``` #[stable(feature = "rust1", since = "1.0.0")] #[rustc_on_unimplemented = "`{Self}` cannot be formatted using `:?`; if it is \ defined in your crate, add `#[derive(Debug)]` or \ @@ -324,8 +363,39 @@ pub trait Debug { fn fmt(&self, &mut Formatter) -> Result; } -/// When a value can be semantically expressed as a String, this trait may be -/// used. It corresponds to the default format, `{}`. +/// Format trait for an empty format, `{}`. +/// +/// `Display` is similar to [`Debug`][debug], but `Display` is for user-facing +/// output, and so cannot be derived. +/// +/// [debug]: trait.Debug.html +/// +/// For more information on formatters, see [the module-level documentation][module]. +/// +/// [module]: ../index.html +/// +/// # Examples +/// +/// Implementing `Display` on a type: +/// +/// ``` +/// use std::fmt; +/// +/// struct Point { +/// x: i32, +/// y: i32, +/// } +/// +/// impl fmt::Display for Point { +/// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { +/// write!(f, "({}, {})", self.x, self.y) +/// } +/// } +/// +/// let origin = Point { x: 0, y: 0 }; +/// +/// println!("The origin is: {}", origin); +/// ``` #[rustc_on_unimplemented = "`{Self}` cannot be formatted with the default \ formatter; try using `:?` instead if you are using \ a format string"] @@ -336,7 +406,46 @@ pub trait Display { fn fmt(&self, &mut Formatter) -> Result; } -/// Format trait for the `o` character +/// Format trait for the `o` character. +/// +/// The `Octal` trait should format its output as a number in base-8. +/// +/// The alternate flag, `#`, adds a `0o` in front of the output. +/// +/// For more information on formatters, see [the module-level documentation][module]. +/// +/// [module]: ../index.html +/// +/// # Examples +/// +/// Basic usage with `i32`: +/// +/// ``` +/// let x = 42; // 42 is '52' in octal +/// +/// assert_eq!(format!("{:o}", x), "52"); +/// assert_eq!(format!("{:#o}", x), "0o52"); +/// ``` +/// +/// Implementing `Octal` on a type: +/// +/// ``` +/// use std::fmt; +/// +/// struct Length(i32); +/// +/// impl fmt::Octal for Length { +/// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { +/// let val = self.0; +/// +/// write!(f, "{:o}", val) // delegate to i32's implementation +/// } +/// } +/// +/// let l = Length(9); +/// +/// println!("l as octal is: {:o}", l); +/// ``` #[stable(feature = "rust1", since = "1.0.0")] pub trait Octal { /// Formats the value using the given formatter. @@ -344,7 +453,46 @@ pub trait Octal { fn fmt(&self, &mut Formatter) -> Result; } -/// Format trait for the `b` character +/// Format trait for the `b` character. +/// +/// The `Binary` trait should format its output as a number in binary. +/// +/// The alternate flag, `#`, adds a `0b` in front of the output. +/// +/// For more information on formatters, see [the module-level documentation][module]. +/// +/// [module]: ../index.html +/// +/// # Examples +/// +/// Basic usage with `i32`: +/// +/// ``` +/// let x = 42; // 42 is '101010' in binary +/// +/// assert_eq!(format!("{:b}", x), "101010"); +/// assert_eq!(format!("{:#b}", x), "0b101010"); +/// ``` +/// +/// Implementing `Binary` on a type: +/// +/// ``` +/// use std::fmt; +/// +/// struct Length(i32); +/// +/// impl fmt::Binary for Length { +/// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { +/// let val = self.0; +/// +/// write!(f, "{:b}", val) // delegate to i32's implementation +/// } +/// } +/// +/// let l = Length(107); +/// +/// println!("l as binary is: {:b}", l); +/// ``` #[stable(feature = "rust1", since = "1.0.0")] pub trait Binary { /// Formats the value using the given formatter. @@ -352,7 +500,47 @@ pub trait Binary { fn fmt(&self, &mut Formatter) -> Result; } -/// Format trait for the `x` character +/// Format trait for the `x` character. +/// +/// The `LowerHex` trait should format its output as a number in hexidecimal, with `a` through `f` +/// in lower case. +/// +/// The alternate flag, `#`, adds a `0x` in front of the output. +/// +/// For more information on formatters, see [the module-level documentation][module]. +/// +/// [module]: ../index.html +/// +/// # Examples +/// +/// Basic usage with `i32`: +/// +/// ``` +/// let x = 42; // 42 is '2a' in hex +/// +/// assert_eq!(format!("{:x}", x), "2a"); +/// assert_eq!(format!("{:#x}", x), "0x2a"); +/// ``` +/// +/// Implementing `LowerHex` on a type: +/// +/// ``` +/// use std::fmt; +/// +/// struct Length(i32); +/// +/// impl fmt::LowerHex for Length { +/// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { +/// let val = self.0; +/// +/// write!(f, "{:x}", val) // delegate to i32's implementation +/// } +/// } +/// +/// let l = Length(9); +/// +/// println!("l as hex is: {:x}", l); +/// ``` #[stable(feature = "rust1", since = "1.0.0")] pub trait LowerHex { /// Formats the value using the given formatter. @@ -360,7 +548,47 @@ pub trait LowerHex { fn fmt(&self, &mut Formatter) -> Result; } -/// Format trait for the `X` character +/// Format trait for the `X` character. +/// +/// The `UpperHex` trait should format its output as a number in hexidecimal, with `A` through `F` +/// in upper case. +/// +/// The alternate flag, `#`, adds a `0x` in front of the output. +/// +/// For more information on formatters, see [the module-level documentation][module]. +/// +/// [module]: ../index.html +/// +/// # Examples +/// +/// Basic usage with `i32`: +/// +/// ``` +/// let x = 42; // 42 is '2A' in hex +/// +/// assert_eq!(format!("{:X}", x), "2A"); +/// assert_eq!(format!("{:#X}", x), "0x2A"); +/// ``` +/// +/// Implementing `UpperHex` on a type: +/// +/// ``` +/// use std::fmt; +/// +/// struct Length(i32); +/// +/// impl fmt::UpperHex for Length { +/// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { +/// let val = self.0; +/// +/// write!(f, "{:X}", val) // delegate to i32's implementation +/// } +/// } +/// +/// let l = Length(9); +/// +/// println!("l as hex is: {:X}", l); +/// ``` #[stable(feature = "rust1", since = "1.0.0")] pub trait UpperHex { /// Formats the value using the given formatter. @@ -368,7 +596,44 @@ pub trait UpperHex { fn fmt(&self, &mut Formatter) -> Result; } -/// Format trait for the `p` character +/// Format trait for the `p` character. +/// +/// The `Pointer` trait should format its output as a memory location. This is commonly presented +/// as hexidecimal. +/// +/// For more information on formatters, see [the module-level documentation][module]. +/// +/// [module]: ../index.html +/// +/// # Examples +/// +/// Basic usage with `&i32`: +/// +/// ``` +/// let x = &42; +/// +/// let address = format!("{:p}", x); // this produces something like '0x7f06092ac6d0' +/// ``` +/// +/// Implementing `Pointer` on a type: +/// +/// ``` +/// use std::fmt; +/// +/// struct Length(i32); +/// +/// impl fmt::Pointer for Length { +/// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { +/// // use `as` to convert to a `*const T`, which implements Pointer, which we can use +/// +/// write!(f, "{:p}", self as *const Length) +/// } +/// } +/// +/// let l = Length(42); +/// +/// println!("l is in memory here: {:p}", l); +/// ``` #[stable(feature = "rust1", since = "1.0.0")] pub trait Pointer { /// Formats the value using the given formatter. @@ -376,7 +641,42 @@ pub trait Pointer { fn fmt(&self, &mut Formatter) -> Result; } -/// Format trait for the `e` character +/// Format trait for the `e` character. +/// +/// The `LowerExp` trait should format its output in scientific notation with a lower-case `e`. +/// +/// For more information on formatters, see [the module-level documentation][module]. +/// +/// [module]: ../index.html +/// +/// # Examples +/// +/// Basic usage with `i32`: +/// +/// ``` +/// let x = 42.0; // 42.0 is '4.2e1' in scientific notation +/// +/// assert_eq!(format!("{:e}", x), "4.2e1"); +/// ``` +/// +/// Implementing `LowerExp` on a type: +/// +/// ``` +/// use std::fmt; +/// +/// struct Length(i32); +/// +/// impl fmt::LowerExp for Length { +/// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { +/// let val = self.0; +/// write!(f, "{}e1", val / 10) +/// } +/// } +/// +/// let l = Length(100); +/// +/// println!("l in scientific notation is: {:e}", l); +/// ``` #[stable(feature = "rust1", since = "1.0.0")] pub trait LowerExp { /// Formats the value using the given formatter. @@ -384,7 +684,42 @@ pub trait LowerExp { fn fmt(&self, &mut Formatter) -> Result; } -/// Format trait for the `E` character +/// Format trait for the `E` character. +/// +/// The `UpperExp` trait should format its output in scientific notation with an upper-case `E`. +/// +/// For more information on formatters, see [the module-level documentation][module]. +/// +/// [module]: ../index.html +/// +/// # Examples +/// +/// Basic usage with `f32`: +/// +/// ``` +/// let x = 42.0; // 42.0 is '4.2E1' in scientific notation +/// +/// assert_eq!(format!("{:E}", x), "4.2E1"); +/// ``` +/// +/// Implementing `UpperExp` on a type: +/// +/// ``` +/// use std::fmt; +/// +/// struct Length(i32); +/// +/// impl fmt::UpperExp for Length { +/// fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { +/// let val = self.0; +/// write!(f, "{}E1", val / 10) +/// } +/// } +/// +/// let l = Length(100); +/// +/// println!("l in scientific notation is: {:E}", l); +/// ``` #[stable(feature = "rust1", since = "1.0.0")] pub trait UpperExp { /// Formats the value using the given formatter. @@ -980,7 +1315,14 @@ impl Debug for char { #[stable(feature = "rust1", since = "1.0.0")] impl Display for char { fn fmt(&self, f: &mut Formatter) -> Result { - f.write_char(*self) + if f.width.is_none() && f.precision.is_none() { + f.write_char(*self) + } else { + let mut utf8 = [0; 4]; + let amt = self.encode_utf8(&mut utf8).unwrap_or(0); + let s: &str = unsafe { mem::transmute(&utf8[..amt]) }; + f.pad(s) + } } } @@ -1146,20 +1488,19 @@ macro_rules! tuple { impl<$($name:Debug),*> Debug for ($($name,)*) { #[allow(non_snake_case, unused_assignments)] fn fmt(&self, f: &mut Formatter) -> Result { - try!(write!(f, "(")); + let mut builder = f.debug_tuple(""); let ($(ref $name,)*) = *self; let mut n = 0; $( - if n > 0 { - try!(write!(f, ", ")); - } - try!(write!(f, "{:?}", *$name)); + builder.field($name); n += 1; )* + if n == 1 { - try!(write!(f, ",")); + try!(write!(builder.formatter(), ",")); } - write!(f, ")") + + builder.finish() } } peel! { $($name,)* } diff --git a/src/libcore/fmt/num.rs b/src/libcore/fmt/num.rs index fc49f87d107..8141916dd60 100644 --- a/src/libcore/fmt/num.rs +++ b/src/libcore/fmt/num.rs @@ -12,26 +12,31 @@ // FIXME: #6220 Implement floating point formatting -#![allow(unsigned_negation)] - use prelude::*; use fmt; use num::Zero; use ops::{Div, Rem, Sub}; use str; +use slice; +use ptr; +use mem; #[doc(hidden)] trait Int: Zero + PartialEq + PartialOrd + Div<Output=Self> + Rem<Output=Self> + Sub<Output=Self> + Copy { fn from_u8(u: u8) -> Self; fn to_u8(&self) -> u8; + fn to_u32(&self) -> u32; + fn to_u64(&self) -> u64; } macro_rules! doit { ($($t:ident)*) => ($(impl Int for $t { fn from_u8(u: u8) -> $t { u as $t } fn to_u8(&self) -> u8 { *self as u8 } + fn to_u32(&self) -> u32 { *self as u32 } + fn to_u64(&self) -> u64 { *self as u64 } })*) } doit! { i8 i16 i32 i64 isize u8 u16 u32 u64 usize } @@ -188,6 +193,7 @@ macro_rules! radix_fmt { } } } + macro_rules! int_base { ($Trait:ident for $T:ident as $U:ident -> $Radix:ident) => { #[stable(feature = "rust1", since = "1.0.0")] @@ -209,9 +215,9 @@ macro_rules! debug { } } } + macro_rules! integer { ($Int:ident, $Uint:ident) => { - int_base! { Display for $Int as $Int -> Decimal } int_base! { Binary for $Int as $Uint -> Binary } int_base! { Octal for $Int as $Uint -> Octal } int_base! { LowerHex for $Int as $Uint -> LowerHex } @@ -219,7 +225,6 @@ macro_rules! integer { radix_fmt! { $Int as $Int, fmt_int } debug! { $Int } - int_base! { Display for $Uint as $Uint -> Decimal } int_base! { Binary for $Uint as $Uint -> Binary } int_base! { Octal for $Uint as $Uint -> Octal } int_base! { LowerHex for $Uint as $Uint -> LowerHex } @@ -233,3 +238,80 @@ integer! { i8, u8 } integer! { i16, u16 } integer! { i32, u32 } integer! { i64, u64 } + +const DEC_DIGITS_LUT: &'static[u8] = + b"0001020304050607080910111213141516171819\ + 2021222324252627282930313233343536373839\ + 4041424344454647484950515253545556575859\ + 6061626364656667686970717273747576777879\ + 8081828384858687888990919293949596979899"; + +macro_rules! impl_Display { + ($($t:ident),*: $conv_fn:ident) => ($( + impl fmt::Display for $t { + #[allow(unused_comparisons)] + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + let is_positive = *self >= 0; + let mut n = if is_positive { + self.$conv_fn() + } else { + // convert the negative num to positive by summing 1 to it's 2 complement + (!self.$conv_fn()).wrapping_add(1) + }; + let mut buf: [u8; 20] = unsafe { mem::uninitialized() }; + let mut curr = buf.len() as isize; + let buf_ptr = buf.as_mut_ptr(); + let lut_ptr = DEC_DIGITS_LUT.as_ptr(); + + unsafe { + // eagerly decode 4 characters at a time + if <$t>::max_value() as u64 >= 10000 { + while n >= 10000 { + let rem = (n % 10000) as isize; + n /= 10000; + + let d1 = (rem / 100) << 1; + let d2 = (rem % 100) << 1; + curr -= 4; + ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2); + ptr::copy_nonoverlapping(lut_ptr.offset(d2), buf_ptr.offset(curr + 2), 2); + } + } + + // if we reach here numbers are <= 9999, so at most 4 chars long + let mut n = n as isize; // possibly reduce 64bit math + + // decode 2 more chars, if > 2 chars + if n >= 100 { + let d1 = (n % 100) << 1; + n /= 100; + curr -= 2; + ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2); + } + + // decode last 1 or 2 chars + if n < 10 { + curr -= 1; + *buf_ptr.offset(curr) = (n as u8) + 48; + } else { + let d1 = n << 1; + curr -= 2; + ptr::copy_nonoverlapping(lut_ptr.offset(d1), buf_ptr.offset(curr), 2); + } + } + + let buf_slice = unsafe { + str::from_utf8_unchecked( + slice::from_raw_parts(buf_ptr.offset(curr), buf.len() - curr as usize)) + }; + f.pad_integral(is_positive, "", buf_slice) + } + })*); +} + +impl_Display!(i8, u8, i16, u16, i32, u32: to_u32); +impl_Display!(i64, u64: to_u64); +#[cfg(target_pointer_width = "32")] +impl_Display!(isize, usize: to_u32); +#[cfg(target_pointer_width = "64")] +impl_Display!(isize, usize: to_u64); diff --git a/src/libcore/hash/sip.rs b/src/libcore/hash/sip.rs index a92b72e0f00..d26e9ab7072 100644 --- a/src/libcore/hash/sip.rs +++ b/src/libcore/hash/sip.rs @@ -10,8 +10,6 @@ //! An implementation of SipHash 2-4. -#![allow(deprecated)] // until the next snapshot for inherent wrapping ops - use prelude::*; use super::Hasher; diff --git a/src/libcore/intrinsics.rs b/src/libcore/intrinsics.rs index 455928077da..1d466895f2c 100644 --- a/src/libcore/intrinsics.rs +++ b/src/libcore/intrinsics.rs @@ -184,6 +184,14 @@ extern "rust-intrinsic" { /// elements. pub fn size_of<T>() -> usize; + #[cfg(not(stage0))] + /// Moves a value to an uninitialized memory location. + /// + /// Drop glue is not run on the destination. + pub fn move_val_init<T>(dst: *mut T, src: T); + + // SNAP d4432b3 + #[cfg(stage0)] /// Moves a value to an uninitialized memory location. /// /// Drop glue is not run on the destination. @@ -586,20 +594,26 @@ extern "rust-intrinsic" { pub fn overflowing_mul<T>(a: T, b: T) -> T; /// Performs an unchecked signed division, which results in undefined behavior, - /// in cases where y == 0, or x == int::MIN and y == -1 + /// in cases where y == 0, or x == isize::MIN and y == -1 pub fn unchecked_sdiv<T>(x: T, y: T) -> T; /// Performs an unchecked unsigned division, which results in undefined behavior, /// in cases where y == 0 pub fn unchecked_udiv<T>(x: T, y: T) -> T; /// Returns the remainder of an unchecked signed division, which results in - /// undefined behavior, in cases where y == 0, or x == int::MIN and y == -1 - pub fn unchecked_urem<T>(x: T, y: T) -> T; - /// Returns the remainder of an unchecked signed division, which results in - /// undefined behavior, in cases where y == 0 + /// undefined behavior, in cases where y == 0, or x == isize::MIN and y == -1 pub fn unchecked_srem<T>(x: T, y: T) -> T; + /// Returns the remainder of an unchecked unsigned division, which results in + /// undefined behavior, in cases where y == 0 + pub fn unchecked_urem<T>(x: T, y: T) -> T; /// Returns the value of the discriminant for the variant in 'v', /// cast to a `u64`; if `T` has no discriminant, returns 0. pub fn discriminant_value<T>(v: &T) -> u64; + + /// Rust's "try catch" construct which invokes the function pointer `f` with + /// the data pointer `data`, returning the exception payload if an exception + /// is thrown (aka the thread panics). + #[cfg(not(stage0))] + pub fn try(f: fn(*mut u8), data: *mut u8) -> *mut u8; } diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs index 3026f91e853..415326a8a61 100644 --- a/src/libcore/iter.rs +++ b/src/libcore/iter.rs @@ -2555,7 +2555,7 @@ impl<I: RandomAccessIterator, F> RandomAccessIterator for Inspect<I, F> #[unstable(feature = "iter_unfold")] #[derive(Clone)] #[deprecated(since = "1.2.0", - reason = "has gained enough traction to retain its position \ + reason = "has not gained enough traction to retain its position \ in the standard library")] #[allow(deprecated)] pub struct Unfold<St, F> { @@ -2567,7 +2567,7 @@ pub struct Unfold<St, F> { #[unstable(feature = "iter_unfold")] #[deprecated(since = "1.2.0", - reason = "has gained enough traction to retain its position \ + reason = "has not gained enough traction to retain its position \ in the standard library")] #[allow(deprecated)] impl<A, St, F> Unfold<St, F> where F: FnMut(&mut St) -> Option<A> { @@ -2655,8 +2655,8 @@ macro_rules! step_impl_signed { #[allow(trivial_numeric_casts)] fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> { if *by == 0 { return None; } - let mut diff: usize; - let mut by_u: usize; + let diff: usize; + let by_u: usize; if *by > 0 { if *start >= *end { return Some(0); @@ -3018,7 +3018,7 @@ type IterateState<T, F> = (F, Option<T>, bool); /// from a given seed value. #[unstable(feature = "iter_iterate")] #[deprecated(since = "1.2.0", - reason = "has gained enough traction to retain its position \ + reason = "has not gained enough traction to retain its position \ in the standard library")] #[allow(deprecated)] pub type Iterate<T, F> = Unfold<IterateState<T, F>, fn(&mut IterateState<T, F>) -> Option<T>>; @@ -3027,7 +3027,7 @@ pub type Iterate<T, F> = Unfold<IterateState<T, F>, fn(&mut IterateState<T, F>) /// repeated applications of the given function `f`. #[unstable(feature = "iter_iterate")] #[deprecated(since = "1.2.0", - reason = "has gained enough traction to retain its position \ + reason = "has not gained enough traction to retain its position \ in the standard library")] #[allow(deprecated)] pub fn iterate<T, F>(seed: T, f: F) -> Iterate<T, F> where diff --git a/src/libcore/lib.rs b/src/libcore/lib.rs index 030d2a33f8f..ef2a33c37dd 100644 --- a/src/libcore/lib.rs +++ b/src/libcore/lib.rs @@ -154,10 +154,6 @@ pub mod str; pub mod hash; pub mod fmt; -#[doc(primitive = "bool")] -mod bool { -} - // note: does not need to be public mod tuple; diff --git a/src/libcore/mem.rs b/src/libcore/mem.rs index 15e7cdbde40..271d83201b1 100644 --- a/src/libcore/mem.rs +++ b/src/libcore/mem.rs @@ -155,6 +155,7 @@ pub fn size_of_val<T: ?Sized>(val: &T) -> usize { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] +#[deprecated(reason = "use `align_of` instead", since = "1.2.0")] pub fn min_align_of<T>() -> usize { unsafe { intrinsics::min_align_of::<T>() } } @@ -170,14 +171,14 @@ pub fn min_align_of<T>() -> usize { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] +#[deprecated(reason = "use `align_of_val` instead", since = "1.2.0")] pub fn min_align_of_val<T: ?Sized>(val: &T) -> usize { unsafe { intrinsics::min_align_of_val(val) } } /// Returns the alignment in memory for a type. /// -/// This function will return the alignment, in bytes, of a type in memory. If the alignment -/// returned is adhered to, then the type is guaranteed to function properly. +/// This is the alignment used for struct fields. It may be smaller than the preferred alignment. /// /// # Examples /// @@ -189,17 +190,10 @@ pub fn min_align_of_val<T: ?Sized>(val: &T) -> usize { #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn align_of<T>() -> usize { - // We use the preferred alignment as the default alignment for a type. This - // appears to be what clang migrated towards as well: - // - // http://lists.cs.uiuc.edu/pipermail/cfe-commits/Week-of-Mon-20110725/044411.html - unsafe { intrinsics::pref_align_of::<T>() } + unsafe { intrinsics::min_align_of::<T>() } } -/// Returns the alignment of the type of the value that `_val` points to. -/// -/// This is similar to `align_of`, but function will properly handle types such as trait objects -/// (in the future), returning the alignment for an arbitrary value at runtime. +/// Returns the ABI-required minimum alignment of the type of the value that `val` points to /// /// # Examples /// @@ -210,8 +204,8 @@ pub fn align_of<T>() -> usize { /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] -pub fn align_of_val<T>(_val: &T) -> usize { - align_of::<T>() +pub fn align_of_val<T: ?Sized>(val: &T) -> usize { + unsafe { intrinsics::min_align_of_val(val) } } /// Creates a value initialized to zero. @@ -371,11 +365,48 @@ pub fn replace<T>(dest: &mut T, mut src: T) -> T { /// Disposes of a value. /// -/// This function can be used to destroy any value by allowing `drop` to take ownership of its -/// argument. +/// While this does call the argument's implementation of `Drop`, it will not +/// release any borrows, as borrows are based on lexical scope. /// /// # Examples /// +/// Basic usage: +/// +/// ``` +/// let v = vec![1, 2, 3]; +/// +/// drop(v); // explicitly drop the vector +/// ``` +/// +/// Borrows are based on lexical scope, so this produces an error: +/// +/// ```ignore +/// let mut v = vec![1, 2, 3]; +/// let x = &v[0]; +/// +/// drop(x); // explicitly drop the reference, but the borrow still exists +/// +/// v.push(4); // error: cannot borrow `v` as mutable because it is also +/// // borrowed as immutable +/// ``` +/// +/// An inner scope is needed to fix this: +/// +/// ``` +/// let mut v = vec![1, 2, 3]; +/// +/// { +/// let x = &v[0]; +/// +/// drop(x); // this is now redundant, as `x` is going out of scope anyway +/// } +/// +/// v.push(4); // no problems +/// ``` +/// +/// Since `RefCell` enforces the borrow rules at runtime, `drop()` can +/// seemingly release a borrow of one: +/// /// ``` /// use std::cell::RefCell; /// @@ -414,17 +445,22 @@ macro_rules! repeat_u8_as_u64 { // // And of course, 0x00 brings back the old world of zero'ing on drop. #[unstable(feature = "filling_drop")] +#[allow(missing_docs)] pub const POST_DROP_U8: u8 = 0x1d; #[unstable(feature = "filling_drop")] +#[allow(missing_docs)] pub const POST_DROP_U32: u32 = repeat_u8_as_u32!(POST_DROP_U8); #[unstable(feature = "filling_drop")] +#[allow(missing_docs)] pub const POST_DROP_U64: u64 = repeat_u8_as_u64!(POST_DROP_U8); #[cfg(target_pointer_width = "32")] #[unstable(feature = "filling_drop")] +#[allow(missing_docs)] pub const POST_DROP_USIZE: usize = POST_DROP_U32 as usize; #[cfg(target_pointer_width = "64")] #[unstable(feature = "filling_drop")] +#[allow(missing_docs)] pub const POST_DROP_USIZE: usize = POST_DROP_U64 as usize; /// Interprets `src` as `&U`, and then reads `src` without moving the contained diff --git a/src/libcore/num/f32.rs b/src/libcore/num/f32.rs index aade9061657..6b4424093b4 100644 --- a/src/libcore/num/f32.rs +++ b/src/libcore/num/f32.rs @@ -10,7 +10,6 @@ //! Operations and constants for 32-bits floats (`f32` type) -#![doc(primitive = "f32")] // FIXME: MIN_VALUE and MAX_VALUE literals are parsed as -inf and inf #14353 #![allow(overflowing_literals)] @@ -24,14 +23,18 @@ use num::{Float, ParseFloatError}; use num::FpCategory as Fp; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const RADIX: u32 = 2; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MANTISSA_DIGITS: u32 = 24; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const DIGITS: u32 = 6; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const EPSILON: f32 = 1.19209290e-07_f32; /// Smallest finite f32 value @@ -45,20 +48,27 @@ pub const MIN_POSITIVE: f32 = 1.17549435e-38_f32; pub const MAX: f32 = 3.40282347e+38_f32; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MIN_EXP: i32 = -125; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MAX_EXP: i32 = 128; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MIN_10_EXP: i32 = -37; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MAX_10_EXP: i32 = 38; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const NAN: f32 = 0.0_f32/0.0_f32; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const INFINITY: f32 = 1.0_f32/0.0_f32; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const NEG_INFINITY: f32 = -1.0_f32/0.0_f32; /// Basic mathematial constants. @@ -215,13 +225,37 @@ impl Float for f32 { /// Rounds towards minus infinity. #[inline] fn floor(self) -> f32 { - unsafe { intrinsics::floorf32(self) } + return floorf(self); + + // On MSVC LLVM will lower many math intrinsics to a call to the + // corresponding function. On MSVC, however, many of these functions + // aren't actually available as symbols to call, but rather they are all + // `static inline` functions in header files. This means that from a C + // perspective it's "compatible", but not so much from an ABI + // perspective (which we're worried about). + // + // The inline header functions always just cast to a f64 and do their + // operation, so we do that here as well, but only for MSVC targets. + // + // Note that there are many MSVC-specific float operations which + // redirect to this comment, so `floorf` is just one case of a missing + // function on MSVC, but there are many others elsewhere. + #[cfg(target_env = "msvc")] + fn floorf(f: f32) -> f32 { (f as f64).floor() as f32 } + #[cfg(not(target_env = "msvc"))] + fn floorf(f: f32) -> f32 { unsafe { intrinsics::floorf32(f) } } } /// Rounds towards plus infinity. #[inline] fn ceil(self) -> f32 { - unsafe { intrinsics::ceilf32(self) } + return ceilf(self); + + // see notes above in `floor` + #[cfg(target_env = "msvc")] + fn ceilf(f: f32) -> f32 { (f as f64).ceil() as f32 } + #[cfg(not(target_env = "msvc"))] + fn ceilf(f: f32) -> f32 { unsafe { intrinsics::ceilf32(f) } } } /// Rounds to nearest integer. Rounds half-way cases away from zero. @@ -299,7 +333,13 @@ impl Float for f32 { #[inline] fn powf(self, n: f32) -> f32 { - unsafe { intrinsics::powf32(self, n) } + return powf(self, n); + + // see notes above in `floor` + #[cfg(target_env = "msvc")] + fn powf(f: f32, n: f32) -> f32 { (f as f64).powf(n as f64) as f32 } + #[cfg(not(target_env = "msvc"))] + fn powf(f: f32, n: f32) -> f32 { unsafe { intrinsics::powf32(f, n) } } } #[inline] @@ -317,7 +357,13 @@ impl Float for f32 { /// Returns the exponential of the number. #[inline] fn exp(self) -> f32 { - unsafe { intrinsics::expf32(self) } + return expf(self); + + // see notes above in `floor` + #[cfg(target_env = "msvc")] + fn expf(f: f32) -> f32 { (f as f64).exp() as f32 } + #[cfg(not(target_env = "msvc"))] + fn expf(f: f32) -> f32 { unsafe { intrinsics::expf32(f) } } } /// Returns 2 raised to the power of the number. @@ -329,7 +375,13 @@ impl Float for f32 { /// Returns the natural logarithm of the number. #[inline] fn ln(self) -> f32 { - unsafe { intrinsics::logf32(self) } + return logf(self); + + // see notes above in `floor` + #[cfg(target_env = "msvc")] + fn logf(f: f32) -> f32 { (f as f64).ln() as f32 } + #[cfg(not(target_env = "msvc"))] + fn logf(f: f32) -> f32 { unsafe { intrinsics::logf32(f) } } } /// Returns the logarithm of the number with respect to an arbitrary base. @@ -345,7 +397,13 @@ impl Float for f32 { /// Returns the base 10 logarithm of the number. #[inline] fn log10(self) -> f32 { - unsafe { intrinsics::log10f32(self) } + return log10f(self); + + // see notes above in `floor` + #[cfg(target_env = "msvc")] + fn log10f(f: f32) -> f32 { (f as f64).log10() as f32 } + #[cfg(not(target_env = "msvc"))] + fn log10f(f: f32) -> f32 { unsafe { intrinsics::log10f32(f) } } } /// Converts to degrees, assuming the number is in radians. diff --git a/src/libcore/num/f64.rs b/src/libcore/num/f64.rs index 7c9e846af9b..fa7aa2ab5ce 100644 --- a/src/libcore/num/f64.rs +++ b/src/libcore/num/f64.rs @@ -10,7 +10,6 @@ //! Operations and constants for 64-bits floats (`f64` type) -#![doc(primitive = "f64")] // FIXME: MIN_VALUE and MAX_VALUE literals are parsed as -inf and inf #14353 #![allow(overflowing_literals)] @@ -24,14 +23,18 @@ use num::FpCategory as Fp; use num::{Float, ParseFloatError}; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const RADIX: u32 = 2; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MANTISSA_DIGITS: u32 = 53; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const DIGITS: u32 = 15; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const EPSILON: f64 = 2.2204460492503131e-16_f64; /// Smallest finite f64 value @@ -45,20 +48,27 @@ pub const MIN_POSITIVE: f64 = 2.2250738585072014e-308_f64; pub const MAX: f64 = 1.7976931348623157e+308_f64; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MIN_EXP: i32 = -1021; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MAX_EXP: i32 = 1024; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MIN_10_EXP: i32 = -307; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MAX_10_EXP: i32 = 308; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const NAN: f64 = 0.0_f64/0.0_f64; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const INFINITY: f64 = 1.0_f64/0.0_f64; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const NEG_INFINITY: f64 = -1.0_f64/0.0_f64; /// Basic mathematial constants. diff --git a/src/libcore/num/i16.rs b/src/libcore/num/i16.rs index 5ea60d0d96d..dacb4ebcdfa 100644 --- a/src/libcore/num/i16.rs +++ b/src/libcore/num/i16.rs @@ -11,6 +11,5 @@ //! Operations and constants for signed 16-bits integers (`i16` type) #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "i16")] int_module! { i16, 16 } diff --git a/src/libcore/num/i32.rs b/src/libcore/num/i32.rs index 7d9faa998c1..250d66de70b 100644 --- a/src/libcore/num/i32.rs +++ b/src/libcore/num/i32.rs @@ -11,6 +11,5 @@ //! Operations and constants for signed 32-bits integers (`i32` type) #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "i32")] int_module! { i32, 32 } diff --git a/src/libcore/num/i64.rs b/src/libcore/num/i64.rs index 5a70911387b..5ed21d7246c 100644 --- a/src/libcore/num/i64.rs +++ b/src/libcore/num/i64.rs @@ -11,6 +11,5 @@ //! Operations and constants for signed 64-bits integers (`i64` type) #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "i64")] int_module! { i64, 64 } diff --git a/src/libcore/num/i8.rs b/src/libcore/num/i8.rs index 1d7d78ffa6c..0394c12d5c4 100644 --- a/src/libcore/num/i8.rs +++ b/src/libcore/num/i8.rs @@ -11,6 +11,5 @@ //! Operations and constants for signed 8-bits integers (`i8` type) #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "i8")] int_module! { i8, 8 } diff --git a/src/libcore/num/int_macros.rs b/src/libcore/num/int_macros.rs index efc91238809..cb9bffca842 100644 --- a/src/libcore/num/int_macros.rs +++ b/src/libcore/num/int_macros.rs @@ -16,21 +16,25 @@ macro_rules! int_module { ($T:ty, $bits:expr) => ( // calling the `mem::size_of` function. #[unstable(feature = "num_bits_bytes", reason = "may want to be an associated function")] +#[allow(missing_docs)] pub const BITS : usize = $bits; // FIXME(#11621): Should be deprecated once CTFE is implemented in favour of // calling the `mem::size_of` function. #[unstable(feature = "num_bits_bytes", reason = "may want to be an associated function")] +#[allow(missing_docs)] pub const BYTES : usize = ($bits / 8); // FIXME(#11621): Should be deprecated once CTFE is implemented in favour of // calling the `Bounded::min_value` function. #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MIN: $T = (-1 as $T) << (BITS - 1); // FIXME(#9837): Compute MIN like this so the high bits that shouldn't exist are 0. // FIXME(#11621): Should be deprecated once CTFE is implemented in favour of // calling the `Bounded::max_value` function. #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MAX: $T = !MIN; ) } diff --git a/src/libcore/num/isize.rs b/src/libcore/num/isize.rs index 2cdfe03eafe..066cb10cce2 100644 --- a/src/libcore/num/isize.rs +++ b/src/libcore/num/isize.rs @@ -11,7 +11,6 @@ //! Operations and constants for pointer-sized signed integers (`isize` type) #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "isize")] #[cfg(target_pointer_width = "32")] int_module! { isize, 32 } diff --git a/src/libcore/num/mod.rs b/src/libcore/num/mod.rs index 97b4f776755..bfbb2ded078 100644 --- a/src/libcore/num/mod.rs +++ b/src/libcore/num/mod.rs @@ -24,6 +24,7 @@ use mem::size_of; use option::Option::{self, Some, None}; use result::Result::{self, Ok, Err}; use str::{FromStr, StrExt}; +use slice::SliceExt; /// Provides intentionally-wrapped arithmetic on `T`. /// @@ -459,7 +460,7 @@ macro_rules! int_impl { } } - /// Wrapping (modular) division. Computes `floor(self / other)`, + /// Wrapping (modular) division. Computes `self / other`, /// wrapping around at the boundary of the type. /// /// The only case where such wrapping can occur is when one @@ -467,7 +468,7 @@ macro_rules! int_impl { /// negative minimal value for the type); this is equivalent /// to `-MIN`, a positive value that is too large to represent /// in the type. In such a case, this function returns `MIN` - /// itself.. + /// itself. #[stable(feature = "num_wrapping", since = "1.2.0")] #[inline(always)] pub fn wrapping_div(self, rhs: Self) -> Self { @@ -668,10 +669,12 @@ macro_rules! uint_impl { $mul_with_overflow:path) => { /// Returns the smallest value that can be represented by this integer type. #[stable(feature = "rust1", since = "1.0.0")] + #[inline] pub fn min_value() -> Self { 0 } /// Returns the largest value that can be represented by this integer type. #[stable(feature = "rust1", since = "1.0.0")] + #[inline] pub fn max_value() -> Self { !0 } /// Converts a string slice in a given base to an integer. @@ -1029,7 +1032,7 @@ macro_rules! uint_impl { } } - /// Wrapping (modular) division. Computes `floor(self / other)`, + /// Wrapping (modular) division. Computes `self / other`, /// wrapping around at the boundary of the type. /// /// The only case where such wrapping can occur is when one @@ -1037,7 +1040,7 @@ macro_rules! uint_impl { /// negative minimal value for the type); this is equivalent /// to `-MIN`, a positive value that is too large to represent /// in the type. In such a case, this function returns `MIN` - /// itself.. + /// itself. #[stable(feature = "num_wrapping", since = "1.2.0")] #[inline(always)] pub fn wrapping_div(self, rhs: Self) -> Self { @@ -1124,7 +1127,7 @@ macro_rules! uint_impl { acc } - /// Returns `true` iff `self == 2^k` for some `k`. + /// Returns `true` if and only if `self == 2^k` for some `k`. #[stable(feature = "rust1", since = "1.0.0")] #[inline] pub fn is_power_of_two(self) -> bool { @@ -1446,19 +1449,30 @@ fn from_str_radix<T: FromStrRadixHelper>(src: &str, radix: u32) -> Result<T, ParseIntError> { use self::IntErrorKind::*; use self::ParseIntError as PIE; + assert!(radix >= 2 && radix <= 36, "from_str_radix_int: must lie in the range `[2, 36]` - found {}", radix); + if src.is_empty() { + return Err(PIE { kind: Empty }); + } + let is_signed_ty = T::from_u32(0) > T::min_value(); - match src.slice_shift_char() { - Some(('-', "")) => Err(PIE { kind: Empty }), - Some(('-', src)) if is_signed_ty => { + // all valid digits are ascii, so we will just iterate over the utf8 bytes + // and cast them to chars. .to_digit() will safely return None for anything + // other than a valid ascii digit for a the given radix, including the first-byte + // of multi-byte sequences + let src = src.as_bytes(); + + match (src[0], &src[1..]) { + (b'-', digits) if digits.is_empty() => Err(PIE { kind: Empty }), + (b'-', digits) if is_signed_ty => { // The number is negative let mut result = T::from_u32(0); - for c in src.chars() { - let x = match c.to_digit(radix) { + for &c in digits { + let x = match (c as char).to_digit(radix) { Some(x) => x, None => return Err(PIE { kind: InvalidDigit }), }; @@ -1473,11 +1487,14 @@ fn from_str_radix<T: FromStrRadixHelper>(src: &str, radix: u32) } Ok(result) }, - Some((_, _)) => { + (c, digits) => { // The number is signed - let mut result = T::from_u32(0); - for c in src.chars() { - let x = match c.to_digit(radix) { + let mut result = match (c as char).to_digit(radix) { + Some(x) => T::from_u32(x), + None => return Err(PIE { kind: InvalidDigit }), + }; + for &c in digits { + let x = match (c as char).to_digit(radix) { Some(x) => x, None => return Err(PIE { kind: InvalidDigit }), }; @@ -1491,8 +1508,7 @@ fn from_str_radix<T: FromStrRadixHelper>(src: &str, radix: u32) }; } Ok(result) - }, - None => Err(ParseIntError { kind: Empty }), + } } } diff --git a/src/libcore/num/u16.rs b/src/libcore/num/u16.rs index 21635799a77..ecf79944848 100644 --- a/src/libcore/num/u16.rs +++ b/src/libcore/num/u16.rs @@ -11,6 +11,5 @@ //! Operations and constants for unsigned 16-bits integers (`u16` type) #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "u16")] uint_module! { u16, i16, 16 } diff --git a/src/libcore/num/u32.rs b/src/libcore/num/u32.rs index 7d520770503..b0682b55ac0 100644 --- a/src/libcore/num/u32.rs +++ b/src/libcore/num/u32.rs @@ -11,6 +11,5 @@ //! Operations and constants for unsigned 32-bits integers (`u32` type) #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "u32")] uint_module! { u32, i32, 32 } diff --git a/src/libcore/num/u64.rs b/src/libcore/num/u64.rs index f10822077dc..dbc6a64a905 100644 --- a/src/libcore/num/u64.rs +++ b/src/libcore/num/u64.rs @@ -11,6 +11,5 @@ //! Operations and constants for unsigned 64-bits integer (`u64` type) #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "u64")] uint_module! { u64, i64, 64 } diff --git a/src/libcore/num/u8.rs b/src/libcore/num/u8.rs index 3d6922b07b1..bf9347ca62c 100644 --- a/src/libcore/num/u8.rs +++ b/src/libcore/num/u8.rs @@ -11,6 +11,5 @@ //! Operations and constants for unsigned 8-bits integers (`u8` type) #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "u8")] uint_module! { u8, i8, 8 } diff --git a/src/libcore/num/uint_macros.rs b/src/libcore/num/uint_macros.rs index 0719d7c17cc..b31d6a73a7f 100644 --- a/src/libcore/num/uint_macros.rs +++ b/src/libcore/num/uint_macros.rs @@ -14,14 +14,18 @@ macro_rules! uint_module { ($T:ty, $T_SIGNED:ty, $bits:expr) => ( #[unstable(feature = "num_bits_bytes", reason = "may want to be an associated function")] +#[allow(missing_docs)] pub const BITS : usize = $bits; #[unstable(feature = "num_bits_bytes", reason = "may want to be an associated function")] +#[allow(missing_docs)] pub const BYTES : usize = ($bits / 8); #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MIN: $T = 0 as $T; #[stable(feature = "rust1", since = "1.0.0")] +#[allow(missing_docs)] pub const MAX: $T = !0 as $T; ) } diff --git a/src/libcore/num/usize.rs b/src/libcore/num/usize.rs index 6fd23425e4d..67e3c954ab6 100644 --- a/src/libcore/num/usize.rs +++ b/src/libcore/num/usize.rs @@ -11,6 +11,5 @@ //! Operations and constants for pointer-sized unsigned integers (`usize` type) #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "usize")] uint_module! { usize, isize, ::isize::BITS } diff --git a/src/libcore/num/wrapping.rs b/src/libcore/num/wrapping.rs index 748ed29e3a3..2e3b34af513 100644 --- a/src/libcore/num/wrapping.rs +++ b/src/libcore/num/wrapping.rs @@ -119,6 +119,16 @@ macro_rules! wrapping_impl { } } + #[stable(feature = "wrapping_div", since = "1.3.0")] + impl Div for Wrapping<$t> { + type Output = Wrapping<$t>; + + #[inline(always)] + fn div(self, other: Wrapping<$t>) -> Wrapping<$t> { + Wrapping(self.0.wrapping_div(other.0)) + } + } + #[stable(feature = "rust1", since = "1.0.0")] impl Not for Wrapping<$t> { type Output = Wrapping<$t>; diff --git a/src/libcore/ops.rs b/src/libcore/ops.rs index 48b1cbeef4f..c1cf2230ac4 100644 --- a/src/libcore/ops.rs +++ b/src/libcore/ops.rs @@ -351,8 +351,10 @@ pub trait Div<RHS=Self> { fn div(self, rhs: RHS) -> Self::Output; } -macro_rules! div_impl { +macro_rules! div_impl_integer { ($($t:ty)*) => ($( + /// This operation rounds towards zero, truncating any + /// fractional part of the exact result. #[stable(feature = "rust1", since = "1.0.0")] impl Div for $t { type Output = $t; @@ -365,7 +367,23 @@ macro_rules! div_impl { )*) } -div_impl! { usize u8 u16 u32 u64 isize i8 i16 i32 i64 f32 f64 } +div_impl_integer! { usize u8 u16 u32 u64 isize i8 i16 i32 i64 } + +macro_rules! div_impl_float { + ($($t:ty)*) => ($( + #[stable(feature = "rust1", since = "1.0.0")] + impl Div for $t { + type Output = $t; + + #[inline] + fn div(self, other: $t) -> $t { self / other } + } + + forward_ref_binop! { impl Div, div for $t, $t } + )*) +} + +div_impl_float! { f32 f64 } /// The `Rem` trait is used to specify the functionality of `%`. /// @@ -407,6 +425,8 @@ pub trait Rem<RHS=Self> { macro_rules! rem_impl { ($($t:ty)*) => ($( + /// This operation satisfies `n % d == n - (n / d) * d`. The + /// result has the same sign as the left operand. #[stable(feature = "rust1", since = "1.0.0")] impl Rem for $t { type Output = $t; @@ -419,26 +439,40 @@ macro_rules! rem_impl { )*) } -macro_rules! rem_float_impl { - ($t:ty, $fmod:ident) => { - #[stable(feature = "rust1", since = "1.0.0")] - impl Rem for $t { - type Output = $t; +rem_impl! { usize u8 u16 u32 u64 isize i8 i16 i32 i64 } - #[inline] - fn rem(self, other: $t) -> $t { - extern { fn $fmod(a: $t, b: $t) -> $t; } - unsafe { $fmod(self, other) } - } - } +#[stable(feature = "rust1", since = "1.0.0")] +impl Rem for f32 { + type Output = f32; + + // see notes in `core::f32::Float::floor` + #[inline] + #[cfg(target_env = "msvc")] + fn rem(self, other: f32) -> f32 { + (self as f64).rem(other as f64) as f32 + } - forward_ref_binop! { impl Rem, rem for $t, $t } + #[inline] + #[cfg(not(target_env = "msvc"))] + fn rem(self, other: f32) -> f32 { + extern { fn fmodf(a: f32, b: f32) -> f32; } + unsafe { fmodf(self, other) } } } -rem_impl! { usize u8 u16 u32 u64 isize i8 i16 i32 i64 } -rem_float_impl! { f32, fmodf } -rem_float_impl! { f64, fmod } +#[stable(feature = "rust1", since = "1.0.0")] +impl Rem for f64 { + type Output = f64; + + #[inline] + fn rem(self, other: f64) -> f64 { + extern { fn fmod(a: f64, b: f64) -> f64; } + unsafe { fmod(self, other) } + } +} + +forward_ref_binop! { impl Rem, rem for f64, f64 } +forward_ref_binop! { impl Rem, rem for f32, f32 } /// The `Neg` trait is used to specify the functionality of unary `-`. /// @@ -483,7 +517,6 @@ pub trait Neg { macro_rules! neg_impl_core { ($id:ident => $body:expr, $($t:ty)*) => ($( #[stable(feature = "rust1", since = "1.0.0")] - #[allow(unsigned_negation)] impl Neg for $t { #[stable(feature = "rust1", since = "1.0.0")] type Output = $t; @@ -1024,6 +1057,10 @@ impl<Idx: fmt::Debug> fmt::Debug for RangeTo<Idx> { /// The `Deref` trait is used to specify the functionality of dereferencing /// operations like `*v`. /// +/// `Deref` also enables ['`Deref` coercions'][coercions]. +/// +/// [coercions]: ../../book/deref-coercions.html +/// /// # Examples /// /// A struct with a single field which is accessible via dereferencing the @@ -1078,6 +1115,10 @@ impl<'a, T: ?Sized> Deref for &'a mut T { /// The `DerefMut` trait is used to specify the functionality of dereferencing /// mutably like `*v = 1;` /// +/// `DerefMut` also enables ['`Deref` coercions'][coercions]. +/// +/// [coercions]: ../../book/deref-coercions.html +/// /// # Examples /// /// A struct with a single field which is modifiable via dereferencing the @@ -1233,3 +1274,120 @@ impl<T: ?Sized+Unsize<U>, U: ?Sized> CoerceUnsized<*const U> for *mut T {} // *const T -> *const U impl<T: ?Sized+Unsize<U>, U: ?Sized> CoerceUnsized<*const U> for *const T {} + +/// Both `in (PLACE) EXPR` and `box EXPR` desugar into expressions +/// that allocate an intermediate "place" that holds uninitialized +/// state. The desugaring evaluates EXPR, and writes the result at +/// the address returned by the `pointer` method of this trait. +/// +/// A `Place` can be thought of as a special representation for a +/// hypothetical `&uninit` reference (which Rust cannot currently +/// express directly). That is, it represents a pointer to +/// uninitialized storage. +/// +/// The client is responsible for two steps: First, initializing the +/// payload (it can access its address via `pointer`). Second, +/// converting the agent to an instance of the owning pointer, via the +/// appropriate `finalize` method (see the `InPlace`. +/// +/// If evaluating EXPR fails, then the destructor for the +/// implementation of Place to clean up any intermediate state +/// (e.g. deallocate box storage, pop a stack, etc). +#[unstable(feature = "placement_new_protocol")] +pub trait Place<Data: ?Sized> { + /// Returns the address where the input value will be written. + /// Note that the data at this address is generally uninitialized, + /// and thus one should use `ptr::write` for initializing it. + fn pointer(&mut self) -> *mut Data; +} + +/// Interface to implementations of `in (PLACE) EXPR`. +/// +/// `in (PLACE) EXPR` effectively desugars into: +/// +/// ```rust,ignore +/// let p = PLACE; +/// let mut place = Placer::make_place(p); +/// let raw_place = Place::pointer(&mut place); +/// let value = EXPR; +/// unsafe { +/// std::ptr::write(raw_place, value); +/// InPlace::finalize(place) +/// } +/// ``` +/// +/// The type of `in (PLACE) EXPR` is derived from the type of `PLACE`; +/// if the type of `PLACE` is `P`, then the final type of the whole +/// expression is `P::Place::Owner` (see the `InPlace` and `Boxed` +/// traits). +/// +/// Values for types implementing this trait usually are transient +/// intermediate values (e.g. the return value of `Vec::emplace_back`) +/// or `Copy`, since the `make_place` method takes `self` by value. +#[unstable(feature = "placement_new_protocol")] +pub trait Placer<Data: ?Sized> { + /// `Place` is the intermedate agent guarding the + /// uninitialized state for `Data`. + type Place: InPlace<Data>; + + /// Creates a fresh place from `self`. + fn make_place(self) -> Self::Place; +} + +/// Specialization of `Place` trait supporting `in (PLACE) EXPR`. +#[unstable(feature = "placement_new_protocol")] +pub trait InPlace<Data: ?Sized>: Place<Data> { + /// `Owner` is the type of the end value of `in (PLACE) EXPR` + /// + /// Note that when `in (PLACE) EXPR` is solely used for + /// side-effecting an existing data-structure, + /// e.g. `Vec::emplace_back`, then `Owner` need not carry any + /// information at all (e.g. it can be the unit type `()` in that + /// case). + type Owner; + + /// Converts self into the final value, shifting + /// deallocation/cleanup responsibilities (if any remain), over to + /// the returned instance of `Owner` and forgetting self. + unsafe fn finalize(self) -> Self::Owner; +} + +/// Core trait for the `box EXPR` form. +/// +/// `box EXPR` effectively desugars into: +/// +/// ```rust,ignore +/// let mut place = BoxPlace::make_place(); +/// let raw_place = Place::pointer(&mut place); +/// let value = EXPR; +/// unsafe { +/// ::std::ptr::write(raw_place, value); +/// Boxed::finalize(place) +/// } +/// ``` +/// +/// The type of `box EXPR` is supplied from its surrounding +/// context; in the above expansion, the result type `T` is used +/// to determine which implementation of `Boxed` to use, and that +/// `<T as Boxed>` in turn dictates determines which +/// implementation of `BoxPlace` to use, namely: +/// `<<T as Boxed>::Place as BoxPlace>`. +#[unstable(feature = "placement_new_protocol")] +pub trait Boxed { + /// The kind of data that is stored in this kind of box. + type Data; /* (`Data` unused b/c cannot yet express below bound.) */ + /// The place that will negotiate the storage of the data. + type Place: BoxPlace<Self::Data>; + + /// Converts filled place into final owning value, shifting + /// deallocation/cleanup responsibilities (if any remain), over to + /// returned instance of `Self` and forgetting `filled`. + unsafe fn finalize(filled: Self::Place) -> Self; +} + +/// Specialization of `Place` trait supporting `box EXPR`. +#[unstable(feature = "placement_new_protocol")] +pub trait BoxPlace<Data: ?Sized> : Place<Data> { + /// Creates a globally fresh place. + fn make_place() -> Self; +} diff --git a/src/libcore/option.rs b/src/libcore/option.rs index c5203c5111b..9ccba7ad78d 100644 --- a/src/libcore/option.rs +++ b/src/libcore/option.rs @@ -46,7 +46,7 @@ //! // The division was valid //! Some(x) => println!("Result: {}", x), //! // The division was invalid -//! None => println!("Cannot divide by 0") +//! None => println!("Cannot divide by 0"), //! } //! ``` //! @@ -75,7 +75,7 @@ //! fn check_optional(optional: &Option<Box<i32>>) { //! match *optional { //! Some(ref p) => println!("have value {}", p), -//! None => println!("have no value") +//! None => println!("have no value"), //! } //! } //! ``` @@ -95,13 +95,13 @@ //! // Take a reference to the contained string //! match msg { //! Some(ref m) => println!("{}", *m), -//! None => () +//! None => (), //! } //! //! // Remove the contained string, destroying the Option //! let unwrapped_msg = match msg { //! Some(m) => m, -//! None => "default message" +//! None => "default message", //! }; //! ``` //! @@ -137,7 +137,7 @@ //! //! match name_of_biggest_animal { //! Some(name) => println!("the biggest animal is {}", name), -//! None => println!("there are no animals :(") +//! None => println!("there are no animals :("), //! } //! ``` @@ -198,7 +198,7 @@ impl<T> Option<T> { pub fn is_some(&self) -> bool { match *self { Some(_) => true, - None => false + None => false, } } @@ -244,7 +244,7 @@ impl<T> Option<T> { pub fn as_ref<'r>(&'r self) -> Option<&'r T> { match *self { Some(ref x) => Some(x), - None => None + None => None, } } @@ -265,7 +265,7 @@ impl<T> Option<T> { pub fn as_mut<'r>(&'r mut self) -> Option<&'r mut T> { match *self { Some(ref mut x) => Some(x), - None => None + None => None, } } @@ -376,7 +376,7 @@ impl<T> Option<T> { pub fn unwrap_or(self, def: T) -> T { match self { Some(x) => x, - None => def + None => def, } } @@ -394,7 +394,7 @@ impl<T> Option<T> { pub fn unwrap_or_else<F: FnOnce() -> T>(self, f: F) -> T { match self { Some(x) => x, - None => f() + None => f(), } } @@ -420,7 +420,7 @@ impl<T> Option<T> { pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> Option<U> { match self { Some(x) => Some(f(x)), - None => None + None => None, } } @@ -464,7 +464,7 @@ impl<T> Option<T> { pub fn map_or_else<U, D: FnOnce() -> U, F: FnOnce(T) -> U>(self, default: D, f: F) -> U { match self { Some(t) => f(t), - None => default() + None => default(), } } @@ -637,7 +637,7 @@ impl<T> Option<T> { pub fn or(self, optb: Option<T>) -> Option<T> { match self { Some(_) => self, - None => optb + None => optb, } } @@ -659,7 +659,7 @@ impl<T> Option<T> { pub fn or_else<F: FnOnce() -> Option<T>>(self, f: F) -> Option<T> { match self { Some(_) => self, - None => f() + None => f(), } } @@ -736,7 +736,7 @@ impl<T: Default> Option<T> { pub fn unwrap_or_default(self) -> T { match self { Some(x) => x, - None => Default::default() + None => Default::default(), } } } diff --git a/src/libcore/ptr.rs b/src/libcore/ptr.rs index f2792a525d6..13d95e9ab1a 100644 --- a/src/libcore/ptr.rs +++ b/src/libcore/ptr.rs @@ -10,86 +10,11 @@ // FIXME: talk about offset, copy_memory, copy_nonoverlapping_memory -//! Operations on raw pointers, `*const T`, and `*mut T`. +//! Raw, unsafe pointers, `*const T`, and `*mut T` //! -//! Working with raw pointers in Rust is uncommon, -//! typically limited to a few patterns. -//! -//! Use the `null` function to create null pointers, and the `is_null` method -//! of the `*const T` type to check for null. The `*const T` type also defines -//! the `offset` method, for pointer math. -//! -//! # Common ways to create raw pointers -//! -//! ## 1. Coerce a reference (`&T`) or mutable reference (`&mut T`). -//! -//! ``` -//! let my_num: i32 = 10; -//! let my_num_ptr: *const i32 = &my_num; -//! let mut my_speed: i32 = 88; -//! let my_speed_ptr: *mut i32 = &mut my_speed; -//! ``` -//! -//! To get a pointer to a boxed value, dereference the box: -//! -//! ``` -//! let my_num: Box<i32> = Box::new(10); -//! let my_num_ptr: *const i32 = &*my_num; -//! let mut my_speed: Box<i32> = Box::new(88); -//! let my_speed_ptr: *mut i32 = &mut *my_speed; -//! ``` -//! -//! This does not take ownership of the original allocation -//! and requires no resource management later, -//! but you must not use the pointer after its lifetime. -//! -//! ## 2. Consume a box (`Box<T>`). -//! -//! The `into_raw` function consumes a box and returns -//! the raw pointer. It doesn't destroy `T` or deallocate any memory. -//! -//! ``` -//! # #![feature(box_raw)] -//! use std::boxed; -//! -//! unsafe { -//! let my_speed: Box<i32> = Box::new(88); -//! let my_speed: *mut i32 = boxed::into_raw(my_speed); -//! -//! // By taking ownership of the original `Box<T>` though -//! // we are obligated to put it together later to be destroyed. -//! drop(Box::from_raw(my_speed)); -//! } -//! ``` -//! -//! Note that here the call to `drop` is for clarity - it indicates -//! that we are done with the given value and it should be destroyed. -//! -//! ## 3. Get it from C. -//! -//! ``` -//! # #![feature(libc)] -//! extern crate libc; -//! -//! use std::mem; -//! -//! fn main() { -//! unsafe { -//! let my_num: *mut i32 = libc::malloc(mem::size_of::<i32>() as libc::size_t) as *mut i32; -//! if my_num.is_null() { -//! panic!("failed to allocate memory"); -//! } -//! libc::free(my_num as *mut libc::c_void); -//! } -//! } -//! ``` -//! -//! Usually you wouldn't literally use `malloc` and `free` from Rust, -//! but C APIs hand out a lot of pointers generally, so are a common source -//! of raw pointers in Rust. +//! *[See also the pointer primitive types](../primitive.pointer.html).* #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "pointer")] use mem; use clone::Clone; diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs index a8c995f37cc..9339f232e91 100644 --- a/src/libcore/slice.rs +++ b/src/libcore/slice.rs @@ -13,7 +13,6 @@ //! For more details `std::slice`. #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "slice")] // How this module is organized. // @@ -83,6 +82,8 @@ pub trait SliceExt { fn first<'a>(&'a self) -> Option<&'a Self::Item>; fn tail<'a>(&'a self) -> &'a [Self::Item]; fn init<'a>(&'a self) -> &'a [Self::Item]; + fn split_first<'a>(&'a self) -> Option<(&'a Self::Item, &'a [Self::Item])>; + fn split_last<'a>(&'a self) -> Option<(&'a Self::Item, &'a [Self::Item])>; fn last<'a>(&'a self) -> Option<&'a Self::Item>; unsafe fn get_unchecked<'a>(&'a self, index: usize) -> &'a Self::Item; fn as_ptr(&self) -> *const Self::Item; @@ -95,6 +96,8 @@ pub trait SliceExt { fn first_mut<'a>(&'a mut self) -> Option<&'a mut Self::Item>; fn tail_mut<'a>(&'a mut self) -> &'a mut [Self::Item]; fn init_mut<'a>(&'a mut self) -> &'a mut [Self::Item]; + fn split_first_mut<'a>(&'a mut self) -> Option<(&'a mut Self::Item, &'a mut [Self::Item])>; + fn split_last_mut<'a>(&'a mut self) -> Option<(&'a mut Self::Item, &'a mut [Self::Item])>; fn last_mut<'a>(&'a mut self) -> Option<&'a mut Self::Item>; fn split_mut<'a, P>(&'a mut self, pred: P) -> SplitMut<'a, Self::Item, P> where P: FnMut(&Self::Item) -> bool; @@ -238,8 +241,17 @@ impl<T> SliceExt for [T] { fn tail(&self) -> &[T] { &self[1..] } #[inline] - fn init(&self) -> &[T] { - &self[..self.len() - 1] + fn split_first(&self) -> Option<(&T, &[T])> { + if self.is_empty() { None } else { Some((&self[0], &self[1..])) } + } + + #[inline] + fn init(&self) -> &[T] { &self[..self.len() - 1] } + + #[inline] + fn split_last(&self) -> Option<(&T, &[T])> { + let len = self.len(); + if len == 0 { None } else { Some((&self[len - 1], &self[..(len - 1)])) } } #[inline] @@ -328,8 +340,14 @@ impl<T> SliceExt for [T] { } #[inline] - fn tail_mut(&mut self) -> &mut [T] { - &mut self[1 ..] + fn tail_mut(&mut self) -> &mut [T] { &mut self[1 ..] } + + #[inline] + fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> { + if self.is_empty() { None } else { + let split = self.split_at_mut(1); + Some((&mut split.0[0], split.1)) + } } #[inline] @@ -339,6 +357,15 @@ impl<T> SliceExt for [T] { } #[inline] + fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> { + let len = self.len(); + if len == 0 { None } else { + let split = self.split_at_mut(len - 1); + Some((&mut split.1[0], split.0)) + } + } + + #[inline] fn split_mut<'a, P>(&'a mut self, pred: P) -> SplitMut<'a, T, P> where P: FnMut(&T) -> bool { SplitMut { v: self, pred: pred, finished: false } } @@ -1368,10 +1395,14 @@ pub fn mut_ref_slice<'a, A>(s: &'a mut A) -> &'a mut [A] { /// /// The `len` argument is the number of **elements**, not the number of bytes. /// +/// # Unsafety +/// /// This function is unsafe as there is no guarantee that the given pointer is /// valid for `len` elements, nor whether the lifetime inferred is a suitable /// lifetime for the returned slice. /// +/// `p` must be non-null, even for zero-length slices. +/// /// # Caveat /// /// The lifetime for the returned slice is inferred from its usage. To @@ -1459,12 +1490,30 @@ pub mod bytes { #[stable(feature = "rust1", since = "1.0.0")] impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> { fn eq(&self, other: &[B]) -> bool { - self.len() == other.len() && - order::eq(self.iter(), other.iter()) + if self.len() != other.len() { + return false; + } + + for i in 0..self.len() { + if !self[i].eq(&other[i]) { + return false; + } + } + + true } fn ne(&self, other: &[B]) -> bool { - self.len() != other.len() || - order::ne(self.iter(), other.iter()) + if self.len() != other.len() { + return true; + } + + for i in 0..self.len() { + if self[i].ne(&other[i]) { + return true; + } + } + + false } } diff --git a/src/libcore/str/mod.rs b/src/libcore/str/mod.rs index 5a621176c4a..4f0b881c5cd 100644 --- a/src/libcore/str/mod.rs +++ b/src/libcore/str/mod.rs @@ -12,16 +12,14 @@ //! //! For more details, see std::str -#![doc(primitive = "str")] #![stable(feature = "rust1", since = "1.0.0")] -use self::OldSearcher::{TwoWay, TwoWayLong}; use self::pattern::Pattern; use self::pattern::{Searcher, ReverseSearcher, DoubleEndedSearcher}; use char::CharExt; use clone::Clone; -use cmp::{self, Eq}; +use cmp::Eq; use convert::AsRef; use default::Default; use fmt; @@ -33,7 +31,6 @@ use option::Option::{self, None, Some}; use raw::{Repr, Slice}; use result::Result::{self, Ok, Err}; use slice::{self, SliceExt}; -use usize; pub mod pattern; @@ -638,10 +635,10 @@ impl<'a, P: Pattern<'a>> SplitInternal<'a, P> { generate_pattern_iterators! { forward: - #[doc="Created with the method `.split()`."] + /// Created with the method `.split()`. struct Split; reverse: - #[doc="Created with the method `.rsplit()`."] + /// Created with the method `.rsplit()`. struct RSplit; stability: #[stable(feature = "rust1", since = "1.0.0")] @@ -652,10 +649,10 @@ generate_pattern_iterators! { generate_pattern_iterators! { forward: - #[doc="Created with the method `.split_terminator()`."] + /// Created with the method `.split_terminator()`. struct SplitTerminator; reverse: - #[doc="Created with the method `.rsplit_terminator()`."] + /// Created with the method `.rsplit_terminator()`. struct RSplitTerminator; stability: #[stable(feature = "rust1", since = "1.0.0")] @@ -698,10 +695,10 @@ impl<'a, P: Pattern<'a>> SplitNInternal<'a, P> { generate_pattern_iterators! { forward: - #[doc="Created with the method `.splitn()`."] + /// Created with the method `.splitn()`. struct SplitN; reverse: - #[doc="Created with the method `.rsplitn()`."] + /// Created with the method `.rsplitn()`. struct RSplitN; stability: #[stable(feature = "rust1", since = "1.0.0")] @@ -732,10 +729,10 @@ impl<'a, P: Pattern<'a>> MatchIndicesInternal<'a, P> { generate_pattern_iterators! { forward: - #[doc="Created with the method `.match_indices()`."] + /// Created with the method `.match_indices()`. struct MatchIndices; reverse: - #[doc="Created with the method `.rmatch_indices()`."] + /// Created with the method `.rmatch_indices()`. struct RMatchIndices; stability: #[unstable(feature = "str_match_indices", @@ -773,10 +770,10 @@ impl<'a, P: Pattern<'a>> MatchesInternal<'a, P> { generate_pattern_iterators! { forward: - #[doc="Created with the method `.matches()`."] + /// Created with the method `.matches()`. struct Matches; reverse: - #[doc="Created with the method `.rmatches()`."] + /// Created with the method `.rmatches()`. struct RMatches; stability: #[stable(feature = "str_matches", since = "1.2.0")] @@ -870,311 +867,16 @@ impl<'a> DoubleEndedIterator for LinesAny<'a> { } } -/// The internal state of an iterator that searches for matches of a substring -/// within a larger string using two-way search -#[derive(Clone)] -struct TwoWaySearcher { - // constants - crit_pos: usize, - period: usize, - byteset: u64, - - // variables - position: usize, - memory: usize -} - -/* - This is the Two-Way search algorithm, which was introduced in the paper: - Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675. - - Here's some background information. - - A *word* is a string of symbols. The *length* of a word should be a familiar - notion, and here we denote it for any word x by |x|. - (We also allow for the possibility of the *empty word*, a word of length zero). - - If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a - *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p]. - For example, both 1 and 2 are periods for the string "aa". As another example, - the only period of the string "abcd" is 4. - - We denote by period(x) the *smallest* period of x (provided that x is non-empty). - This is always well-defined since every non-empty word x has at least one period, - |x|. We sometimes call this *the period* of x. - - If u, v and x are words such that x = uv, where uv is the concatenation of u and - v, then we say that (u, v) is a *factorization* of x. - - Let (u, v) be a factorization for a word x. Then if w is a non-empty word such - that both of the following hold - - - either w is a suffix of u or u is a suffix of w - - either w is a prefix of v or v is a prefix of w - - then w is said to be a *repetition* for the factorization (u, v). - - Just to unpack this, there are four possibilities here. Let w = "abc". Then we - might have: - - - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde") - - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab") - - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi") - - u is a suffix of w and v is a prefix of w. ex: ("bc", "a") - - Note that the word vu is a repetition for any factorization (u,v) of x = uv, - so every factorization has at least one repetition. - - If x is a string and (u, v) is a factorization for x, then a *local period* for - (u, v) is an integer r such that there is some word w such that |w| = r and w is - a repetition for (u, v). - - We denote by local_period(u, v) the smallest local period of (u, v). We sometimes - call this *the local period* of (u, v). Provided that x = uv is non-empty, this - is well-defined (because each non-empty word has at least one factorization, as - noted above). - - It can be proven that the following is an equivalent definition of a local period - for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for - all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are - defined. (i.e. i > 0 and i + r < |x|). - - Using the above reformulation, it is easy to prove that - - 1 <= local_period(u, v) <= period(uv) - - A factorization (u, v) of x such that local_period(u,v) = period(x) is called a - *critical factorization*. - - The algorithm hinges on the following theorem, which is stated without proof: - - **Critical Factorization Theorem** Any word x has at least one critical - factorization (u, v) such that |u| < period(x). - - The purpose of maximal_suffix is to find such a critical factorization. - -*/ -impl TwoWaySearcher { - #[allow(dead_code)] - fn new(needle: &[u8]) -> TwoWaySearcher { - let (crit_pos_false, period_false) = TwoWaySearcher::maximal_suffix(needle, false); - let (crit_pos_true, period_true) = TwoWaySearcher::maximal_suffix(needle, true); - - let (crit_pos, period) = - if crit_pos_false > crit_pos_true { - (crit_pos_false, period_false) - } else { - (crit_pos_true, period_true) - }; - - // This isn't in the original algorithm, as far as I'm aware. - let byteset = needle.iter() - .fold(0, |a, &b| (1 << ((b & 0x3f) as usize)) | a); - - // A particularly readable explanation of what's going on here can be found - // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically - // see the code for "Algorithm CP" on p. 323. - // - // What's going on is we have some critical factorization (u, v) of the - // needle, and we want to determine whether u is a suffix of - // &v[..period]. If it is, we use "Algorithm CP1". Otherwise we use - // "Algorithm CP2", which is optimized for when the period of the needle - // is large. - if &needle[..crit_pos] == &needle[period.. period + crit_pos] { - TwoWaySearcher { - crit_pos: crit_pos, - period: period, - byteset: byteset, - - position: 0, - memory: 0 - } - } else { - TwoWaySearcher { - crit_pos: crit_pos, - period: cmp::max(crit_pos, needle.len() - crit_pos) + 1, - byteset: byteset, - - position: 0, - memory: usize::MAX // Dummy value to signify that the period is long - } - } - } - - // One of the main ideas of Two-Way is that we factorize the needle into - // two halves, (u, v), and begin trying to find v in the haystack by scanning - // left to right. If v matches, we try to match u by scanning right to left. - // How far we can jump when we encounter a mismatch is all based on the fact - // that (u, v) is a critical factorization for the needle. - #[inline] - fn next(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) - -> Option<(usize, usize)> { - 'search: loop { - // Check that we have room to search in - if self.position + needle.len() > haystack.len() { - return None; - } - - // Quickly skip by large portions unrelated to our substring - if (self.byteset >> - ((haystack[self.position + needle.len() - 1] & 0x3f) - as usize)) & 1 == 0 { - self.position += needle.len(); - if !long_period { - self.memory = 0; - } - continue 'search; - } - - // See if the right part of the needle matches - let start = if long_period { self.crit_pos } - else { cmp::max(self.crit_pos, self.memory) }; - for i in start..needle.len() { - if needle[i] != haystack[self.position + i] { - self.position += i - self.crit_pos + 1; - if !long_period { - self.memory = 0; - } - continue 'search; - } - } - - // See if the left part of the needle matches - let start = if long_period { 0 } else { self.memory }; - for i in (start..self.crit_pos).rev() { - if needle[i] != haystack[self.position + i] { - self.position += self.period; - if !long_period { - self.memory = needle.len() - self.period; - } - continue 'search; - } - } - - // We have found a match! - let match_pos = self.position; - self.position += needle.len(); // add self.period for all matches - if !long_period { - self.memory = 0; // set to needle.len() - self.period for all matches - } - return Some((match_pos, match_pos + needle.len())); - } - } - - // Computes a critical factorization (u, v) of `arr`. - // Specifically, returns (i, p), where i is the starting index of v in some - // critical factorization (u, v) and p = period(v) - #[inline] - #[allow(dead_code)] - #[allow(deprecated)] - fn maximal_suffix(arr: &[u8], reversed: bool) -> (usize, usize) { - let mut left: usize = !0; // Corresponds to i in the paper - let mut right = 0; // Corresponds to j in the paper - let mut offset = 1; // Corresponds to k in the paper - let mut period = 1; // Corresponds to p in the paper - - while right + offset < arr.len() { - let a; - let b; - if reversed { - a = arr[left.wrapping_add(offset)]; - b = arr[right + offset]; - } else { - a = arr[right + offset]; - b = arr[left.wrapping_add(offset)]; - } - if a < b { - // Suffix is smaller, period is entire prefix so far. - right += offset; - offset = 1; - period = right.wrapping_sub(left); - } else if a == b { - // Advance through repetition of the current period. - if offset == period { - right += offset; - offset = 1; - } else { - offset += 1; - } - } else { - // Suffix is larger, start over from current location. - left = right; - right += 1; - offset = 1; - period = 1; - } - } - (left.wrapping_add(1), period) - } -} - -/// The internal state of an iterator that searches for matches of a substring -/// within a larger string using a dynamically chosen search algorithm -#[derive(Clone)] -// NB: This is kept around for convenience because -// it is planned to be used again in the future -enum OldSearcher { - TwoWay(TwoWaySearcher), - TwoWayLong(TwoWaySearcher), -} - -impl OldSearcher { - #[allow(dead_code)] - fn new(haystack: &[u8], needle: &[u8]) -> OldSearcher { - if needle.is_empty() { - // Handle specially - unimplemented!() - // FIXME: Tune this. - // FIXME(#16715): This unsigned integer addition will probably not - // overflow because that would mean that the memory almost solely - // consists of the needle. Needs #16715 to be formally fixed. - } else if needle.len() + 20 > haystack.len() { - // Use naive searcher - unimplemented!() - } else { - let searcher = TwoWaySearcher::new(needle); - if searcher.memory == usize::MAX { // If the period is long - TwoWayLong(searcher) - } else { - TwoWay(searcher) - } - } - } -} - -#[derive(Clone)] -// NB: This is kept around for convenience because -// it is planned to be used again in the future -struct OldMatchIndices<'a, 'b> { - // constants - haystack: &'a str, - needle: &'b str, - searcher: OldSearcher -} - -impl<'a, 'b> OldMatchIndices<'a, 'b> { - #[inline] - #[allow(dead_code)] - fn next(&mut self) -> Option<(usize, usize)> { - match self.searcher { - TwoWay(ref mut searcher) - => searcher.next(self.haystack.as_bytes(), self.needle.as_bytes(), false), - TwoWayLong(ref mut searcher) - => searcher.next(self.haystack.as_bytes(), self.needle.as_bytes(), true), - } - } -} - /* Section: Comparing strings */ -// share the implementation of the lang-item vs. non-lang-item -// eq_slice. +/// Bytewise slice equality /// NOTE: This function is (ab)used in rustc::middle::trans::_match /// to compare &[u8] byte slices that are not necessarily valid UTF-8. +#[lang = "str_eq"] #[inline] -fn eq_slice_(a: &str, b: &str) -> bool { +fn eq_slice(a: &str, b: &str) -> bool { // NOTE: In theory n should be libc::size_t and not usize, but libc is not available here #[allow(improper_ctypes)] extern { fn memcmp(s1: *const i8, s2: *const i8, n: usize) -> i32; } @@ -1185,15 +887,6 @@ fn eq_slice_(a: &str, b: &str) -> bool { } } -/// Bytewise slice equality -/// NOTE: This function is (ab)used in rustc::middle::trans::_match -/// to compare &[u8] byte slices that are not necessarily valid UTF-8. -#[lang = "str_eq"] -#[inline] -fn eq_slice(a: &str, b: &str) -> bool { - eq_slice_(a, b) -} - /* Section: Misc */ @@ -1413,6 +1106,23 @@ mod traits { } } + /// Returns a mutable slice of the given string from the byte range + /// [`begin`..`end`). + #[stable(feature = "derefmut_for_string", since = "1.2.0")] + impl ops::IndexMut<ops::Range<usize>> for str { + #[inline] + fn index_mut(&mut self, index: ops::Range<usize>) -> &mut str { + // is_char_boundary checks that the index is in [0, .len()] + if index.start <= index.end && + self.is_char_boundary(index.start) && + self.is_char_boundary(index.end) { + unsafe { self.slice_mut_unchecked(index.start, index.end) } + } else { + super::slice_error_fail(self, index.start, index.end) + } + } + } + /// Returns a slice of the string from the beginning to byte /// `end`. /// @@ -1435,6 +1145,21 @@ mod traits { } } + /// Returns a mutable slice of the string from the beginning to byte + /// `end`. + #[stable(feature = "derefmut_for_string", since = "1.2.0")] + impl ops::IndexMut<ops::RangeTo<usize>> for str { + #[inline] + fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut str { + // is_char_boundary checks that the index is in [0, .len()] + if self.is_char_boundary(index.end) { + unsafe { self.slice_mut_unchecked(0, index.end) } + } else { + super::slice_error_fail(self, 0, index.end) + } + } + } + /// Returns a slice of the string from `begin` to its end. /// /// Equivalent to `self[begin .. self.len()]`. @@ -1456,6 +1181,21 @@ mod traits { } } + /// Returns a slice of the string from `begin` to its end. + #[stable(feature = "derefmut_for_string", since = "1.2.0")] + impl ops::IndexMut<ops::RangeFrom<usize>> for str { + #[inline] + fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut str { + // is_char_boundary checks that the index is in [0, .len()] + if self.is_char_boundary(index.start) { + let len = self.len(); + unsafe { self.slice_mut_unchecked(index.start, len) } + } else { + super::slice_error_fail(self, index.start, self.len()) + } + } + } + #[stable(feature = "rust1", since = "1.0.0")] impl ops::Index<ops::RangeFull> for str { type Output = str; @@ -1465,6 +1205,14 @@ mod traits { self } } + + #[stable(feature = "derefmut_for_string", since = "1.2.0")] + impl ops::IndexMut<ops::RangeFull> for str { + #[inline] + fn index_mut(&mut self, _index: ops::RangeFull) -> &mut str { + self + } + } } /// Methods for string slices @@ -1501,6 +1249,7 @@ pub trait StrExt { fn char_len(&self) -> usize; fn slice_chars<'a>(&'a self, begin: usize, end: usize) -> &'a str; unsafe fn slice_unchecked<'a>(&'a self, begin: usize, end: usize) -> &'a str; + unsafe fn slice_mut_unchecked<'a>(&'a mut self, begin: usize, end: usize) -> &'a mut str; fn starts_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool; fn ends_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool where P::Searcher: ReverseSearcher<'a>; @@ -1520,6 +1269,7 @@ pub trait StrExt { where P::Searcher: ReverseSearcher<'a>; fn find_str<'a, P: Pattern<'a>>(&'a self, pat: P) -> Option<usize>; fn split_at(&self, mid: usize) -> (&str, &str); + fn split_at_mut(&mut self, mid: usize) -> (&mut str, &mut str); fn slice_shift_char<'a>(&'a self) -> Option<(char, &'a str)>; fn subslice_offset(&self, inner: &str) -> usize; fn as_ptr(&self) -> *const u8; @@ -1677,6 +1427,14 @@ impl StrExt for str { } #[inline] + unsafe fn slice_mut_unchecked(&mut self, begin: usize, end: usize) -> &mut str { + mem::transmute(Slice { + data: self.as_ptr().offset(begin as isize), + len: end - begin, + }) + } + + #[inline] fn starts_with<'a, P: Pattern<'a>>(&'a self, pat: P) -> bool { pat.is_prefix_of(self) } @@ -1824,6 +1582,20 @@ impl StrExt for str { } } + fn split_at_mut(&mut self, mid: usize) -> (&mut str, &mut str) { + // is_char_boundary checks that the index is in [0, .len()] + if self.is_char_boundary(mid) { + let len = self.len(); + unsafe { + let self2: &mut str = mem::transmute_copy(&self); + (self.slice_mut_unchecked(0, mid), + self2.slice_mut_unchecked(mid, len)) + } + } else { + slice_error_fail(self, 0, mid) + } + } + #[inline] fn slice_shift_char(&self) -> Option<(char, &str)> { if self.is_empty() { diff --git a/src/libcore/str/pattern.rs b/src/libcore/str/pattern.rs index 8bdbab55211..707f7fcf2ab 100644 --- a/src/libcore/str/pattern.rs +++ b/src/libcore/str/pattern.rs @@ -17,6 +17,8 @@ reason = "API not fully fleshed out and ready to be stabilized")] use prelude::*; +use core::cmp; +use usize; // Pattern @@ -342,148 +344,6 @@ unsafe impl<'a, C: CharEq> ReverseSearcher<'a> for CharEqSearcher<'a, C> { impl<'a, C: CharEq> DoubleEndedSearcher<'a> for CharEqSearcher<'a, C> {} ///////////////////////////////////////////////////////////////////////////// -// Impl for &str -///////////////////////////////////////////////////////////////////////////// - -// Todo: Optimize the naive implementation here - -/// Associated type for `<&str as Pattern<'a>>::Searcher`. -#[derive(Clone)] -pub struct StrSearcher<'a, 'b> { - haystack: &'a str, - needle: &'b str, - start: usize, - end: usize, - state: State, -} - -#[derive(Clone, PartialEq)] -enum State { Done, NotDone, Reject(usize, usize) } -impl State { - #[inline] fn done(&self) -> bool { *self == State::Done } - #[inline] fn take(&mut self) -> State { ::mem::replace(self, State::NotDone) } -} - -/// Non-allocating substring search. -/// -/// Will handle the pattern `""` as returning empty matches at each utf8 -/// boundary. -impl<'a, 'b> Pattern<'a> for &'b str { - type Searcher = StrSearcher<'a, 'b>; - - #[inline] - fn into_searcher(self, haystack: &'a str) -> StrSearcher<'a, 'b> { - StrSearcher { - haystack: haystack, - needle: self, - start: 0, - end: haystack.len(), - state: State::NotDone, - } - } -} - -unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b> { - #[inline] - fn haystack(&self) -> &'a str { - self.haystack - } - - #[inline] - fn next(&mut self) -> SearchStep { - str_search_step(self, - |m: &mut StrSearcher| { - // Forward step for empty needle - let current_start = m.start; - if !m.state.done() { - m.start = m.haystack.char_range_at(current_start).next; - m.state = State::Reject(current_start, m.start); - } - SearchStep::Match(current_start, current_start) - }, - |m: &mut StrSearcher| { - // Forward step for nonempty needle - let current_start = m.start; - // Compare byte window because this might break utf8 boundaries - let possible_match = &m.haystack.as_bytes()[m.start .. m.start + m.needle.len()]; - if possible_match == m.needle.as_bytes() { - m.start += m.needle.len(); - SearchStep::Match(current_start, m.start) - } else { - // Skip a char - let haystack_suffix = &m.haystack[m.start..]; - m.start += haystack_suffix.chars().next().unwrap().len_utf8(); - SearchStep::Reject(current_start, m.start) - } - }) - } -} - -unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b> { - #[inline] - fn next_back(&mut self) -> SearchStep { - str_search_step(self, - |m: &mut StrSearcher| { - // Backward step for empty needle - let current_end = m.end; - if !m.state.done() { - m.end = m.haystack.char_range_at_reverse(current_end).next; - m.state = State::Reject(m.end, current_end); - } - SearchStep::Match(current_end, current_end) - }, - |m: &mut StrSearcher| { - // Backward step for nonempty needle - let current_end = m.end; - // Compare byte window because this might break utf8 boundaries - let possible_match = &m.haystack.as_bytes()[m.end - m.needle.len() .. m.end]; - if possible_match == m.needle.as_bytes() { - m.end -= m.needle.len(); - SearchStep::Match(m.end, current_end) - } else { - // Skip a char - let haystack_prefix = &m.haystack[..m.end]; - m.end -= haystack_prefix.chars().rev().next().unwrap().len_utf8(); - SearchStep::Reject(m.end, current_end) - } - }) - } -} - -// Helper function for encapsulating the common control flow -// of doing a search step from the front or doing a search step from the back -fn str_search_step<F, G>(mut m: &mut StrSearcher, - empty_needle_step: F, - nonempty_needle_step: G) -> SearchStep - where F: FnOnce(&mut StrSearcher) -> SearchStep, - G: FnOnce(&mut StrSearcher) -> SearchStep -{ - if m.state.done() { - SearchStep::Done - } else if m.needle.is_empty() && m.start <= m.end { - // Case for needle == "" - if let State::Reject(a, b) = m.state.take() { - SearchStep::Reject(a, b) - } else { - if m.start == m.end { - m.state = State::Done; - } - empty_needle_step(&mut m) - } - } else if m.start + m.needle.len() <= m.end { - // Case for needle != "" - nonempty_needle_step(&mut m) - } else if m.start < m.end { - // Remaining slice shorter than needle, reject it - m.state = State::Done; - SearchStep::Reject(m.start, m.end) - } else { - m.state = State::Done; - SearchStep::Done - } -} - -///////////////////////////////////////////////////////////////////////////// macro_rules! pattern_methods { ($t:ty, $pmap:expr, $smap:expr) => { @@ -633,3 +493,578 @@ impl<'a, F> Pattern<'a> for F where F: FnMut(char) -> bool { impl<'a, 'b> Pattern<'a> for &'b &'b str { pattern_methods!(StrSearcher<'a, 'b>, |&s| s, |s| s); } + +///////////////////////////////////////////////////////////////////////////// +// Impl for &str +///////////////////////////////////////////////////////////////////////////// + +/// Non-allocating substring search. +/// +/// Will handle the pattern `""` as returning empty matches at each character +/// boundary. +impl<'a, 'b> Pattern<'a> for &'b str { + type Searcher = StrSearcher<'a, 'b>; + + #[inline] + fn into_searcher(self, haystack: &'a str) -> StrSearcher<'a, 'b> { + StrSearcher::new(haystack, self) + } + + /// Checks whether the pattern matches at the front of the haystack + #[inline] + fn is_prefix_of(self, haystack: &'a str) -> bool { + haystack.is_char_boundary(self.len()) && + self == &haystack[..self.len()] + } + + /// Checks whether the pattern matches at the back of the haystack + #[inline] + fn is_suffix_of(self, haystack: &'a str) -> bool { + self.len() <= haystack.len() && + haystack.is_char_boundary(haystack.len() - self.len()) && + self == &haystack[haystack.len() - self.len()..] + } +} + + +///////////////////////////////////////////////////////////////////////////// +// Two Way substring searcher +///////////////////////////////////////////////////////////////////////////// + +#[derive(Clone, Debug)] +/// Associated type for `<&str as Pattern<'a>>::Searcher`. +pub struct StrSearcher<'a, 'b> { + haystack: &'a str, + needle: &'b str, + + searcher: StrSearcherImpl, +} + +#[derive(Clone, Debug)] +enum StrSearcherImpl { + Empty(EmptyNeedle), + TwoWay(TwoWaySearcher), +} + +#[derive(Clone, Debug)] +struct EmptyNeedle { + position: usize, + end: usize, + is_match_fw: bool, + is_match_bw: bool, +} + +impl<'a, 'b> StrSearcher<'a, 'b> { + fn new(haystack: &'a str, needle: &'b str) -> StrSearcher<'a, 'b> { + if needle.is_empty() { + StrSearcher { + haystack: haystack, + needle: needle, + searcher: StrSearcherImpl::Empty(EmptyNeedle { + position: 0, + end: haystack.len(), + is_match_fw: true, + is_match_bw: true, + }), + } + } else { + StrSearcher { + haystack: haystack, + needle: needle, + searcher: StrSearcherImpl::TwoWay( + TwoWaySearcher::new(needle.as_bytes(), haystack.len()) + ), + } + } + } +} + +unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b> { + fn haystack(&self) -> &'a str { self.haystack } + + #[inline] + fn next(&mut self) -> SearchStep { + match self.searcher { + StrSearcherImpl::Empty(ref mut searcher) => { + // empty needle rejects every char and matches every empty string between them + let is_match = searcher.is_match_fw; + searcher.is_match_fw = !searcher.is_match_fw; + let pos = searcher.position; + match self.haystack[pos..].chars().next() { + _ if is_match => SearchStep::Match(pos, pos), + None => SearchStep::Done, + Some(ch) => { + searcher.position += ch.len_utf8(); + SearchStep::Reject(pos, searcher.position) + } + } + } + StrSearcherImpl::TwoWay(ref mut searcher) => { + // TwoWaySearcher produces valid *Match* indices that split at char boundaries + // as long as it does correct matching and that haystack and needle are + // valid UTF-8 + // *Rejects* from the algorithm can fall on any indices, but we will walk them + // manually to the next character boundary, so that they are utf-8 safe. + if searcher.position == self.haystack.len() { + return SearchStep::Done; + } + let is_long = searcher.memory == usize::MAX; + match searcher.next::<RejectAndMatch>(self.haystack.as_bytes(), + self.needle.as_bytes(), + is_long) + { + SearchStep::Reject(a, mut b) => { + // skip to next char boundary + while !self.haystack.is_char_boundary(b) { + b += 1; + } + searcher.position = cmp::max(b, searcher.position); + SearchStep::Reject(a, b) + } + otherwise => otherwise, + } + } + } + } + + #[inline(always)] + fn next_match(&mut self) -> Option<(usize, usize)> { + match self.searcher { + StrSearcherImpl::Empty(..) => { + loop { + match self.next() { + SearchStep::Match(a, b) => return Some((a, b)), + SearchStep::Done => return None, + SearchStep::Reject(..) => { } + } + } + } + StrSearcherImpl::TwoWay(ref mut searcher) => { + let is_long = searcher.memory == usize::MAX; + if is_long { + searcher.next::<MatchOnly>(self.haystack.as_bytes(), + self.needle.as_bytes(), + true) + } else { + searcher.next::<MatchOnly>(self.haystack.as_bytes(), + self.needle.as_bytes(), + false) + } + } + } + } + +} +unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b> { + #[inline] + fn next_back(&mut self) -> SearchStep { + match self.searcher { + StrSearcherImpl::Empty(ref mut searcher) => { + let is_match = searcher.is_match_bw; + searcher.is_match_bw = !searcher.is_match_bw; + let end = searcher.end; + match self.haystack[..end].chars().next_back() { + _ if is_match => SearchStep::Match(end, end), + None => SearchStep::Done, + Some(ch) => { + searcher.end -= ch.len_utf8(); + SearchStep::Reject(searcher.end, end) + } + } + } + StrSearcherImpl::TwoWay(ref mut searcher) => { + if searcher.end == 0 { + return SearchStep::Done; + } + match searcher.next_back::<RejectAndMatch>(self.haystack.as_bytes(), + self.needle.as_bytes()) + { + SearchStep::Reject(mut a, b) => { + // skip to next char boundary + while !self.haystack.is_char_boundary(a) { + a -= 1; + } + searcher.end = cmp::min(a, searcher.end); + SearchStep::Reject(a, b) + } + otherwise => otherwise, + } + } + } + } + + #[inline] + fn next_match_back(&mut self) -> Option<(usize, usize)> { + match self.searcher { + StrSearcherImpl::Empty(..) => { + loop { + match self.next_back() { + SearchStep::Match(a, b) => return Some((a, b)), + SearchStep::Done => return None, + SearchStep::Reject(..) => { } + } + } + } + StrSearcherImpl::TwoWay(ref mut searcher) => { + searcher.next_back::<MatchOnly>(self.haystack.as_bytes(), + self.needle.as_bytes()) + } + } + } +} + +/// The internal state of an iterator that searches for matches of a substring +/// within a larger string using two-way search +#[derive(Clone, Debug)] +struct TwoWaySearcher { + // constants + crit_pos: usize, + period: usize, + byteset: u64, + + // variables + position: usize, + end: usize, + memory: usize +} + +/* + This is the Two-Way search algorithm, which was introduced in the paper: + Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675. + + Here's some background information. + + A *word* is a string of symbols. The *length* of a word should be a familiar + notion, and here we denote it for any word x by |x|. + (We also allow for the possibility of the *empty word*, a word of length zero). + + If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a + *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p]. + For example, both 1 and 2 are periods for the string "aa". As another example, + the only period of the string "abcd" is 4. + + We denote by period(x) the *smallest* period of x (provided that x is non-empty). + This is always well-defined since every non-empty word x has at least one period, + |x|. We sometimes call this *the period* of x. + + If u, v and x are words such that x = uv, where uv is the concatenation of u and + v, then we say that (u, v) is a *factorization* of x. + + Let (u, v) be a factorization for a word x. Then if w is a non-empty word such + that both of the following hold + + - either w is a suffix of u or u is a suffix of w + - either w is a prefix of v or v is a prefix of w + + then w is said to be a *repetition* for the factorization (u, v). + + Just to unpack this, there are four possibilities here. Let w = "abc". Then we + might have: + + - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde") + - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab") + - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi") + - u is a suffix of w and v is a prefix of w. ex: ("bc", "a") + + Note that the word vu is a repetition for any factorization (u,v) of x = uv, + so every factorization has at least one repetition. + + If x is a string and (u, v) is a factorization for x, then a *local period* for + (u, v) is an integer r such that there is some word w such that |w| = r and w is + a repetition for (u, v). + + We denote by local_period(u, v) the smallest local period of (u, v). We sometimes + call this *the local period* of (u, v). Provided that x = uv is non-empty, this + is well-defined (because each non-empty word has at least one factorization, as + noted above). + + It can be proven that the following is an equivalent definition of a local period + for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for + all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are + defined. (i.e. i > 0 and i + r < |x|). + + Using the above reformulation, it is easy to prove that + + 1 <= local_period(u, v) <= period(uv) + + A factorization (u, v) of x such that local_period(u,v) = period(x) is called a + *critical factorization*. + + The algorithm hinges on the following theorem, which is stated without proof: + + **Critical Factorization Theorem** Any word x has at least one critical + factorization (u, v) such that |u| < period(x). + + The purpose of maximal_suffix is to find such a critical factorization. + +*/ +impl TwoWaySearcher { + fn new(needle: &[u8], end: usize) -> TwoWaySearcher { + let (crit_pos_false, period_false) = TwoWaySearcher::maximal_suffix(needle, false); + let (crit_pos_true, period_true) = TwoWaySearcher::maximal_suffix(needle, true); + + let (crit_pos, period) = + if crit_pos_false > crit_pos_true { + (crit_pos_false, period_false) + } else { + (crit_pos_true, period_true) + }; + + // This isn't in the original algorithm, as far as I'm aware. + let byteset = needle.iter() + .fold(0, |a, &b| (1 << ((b & 0x3f) as usize)) | a); + + // A particularly readable explanation of what's going on here can be found + // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically + // see the code for "Algorithm CP" on p. 323. + // + // What's going on is we have some critical factorization (u, v) of the + // needle, and we want to determine whether u is a suffix of + // &v[..period]. If it is, we use "Algorithm CP1". Otherwise we use + // "Algorithm CP2", which is optimized for when the period of the needle + // is large. + if &needle[..crit_pos] == &needle[period.. period + crit_pos] { + // short period case + TwoWaySearcher { + crit_pos: crit_pos, + period: period, + byteset: byteset, + + position: 0, + end: end, + memory: 0 + } + } else { + // long period case + // we have an approximation to the actual period, and don't use memory. + TwoWaySearcher { + crit_pos: crit_pos, + period: cmp::max(crit_pos, needle.len() - crit_pos) + 1, + byteset: byteset, + + position: 0, + end: end, + memory: usize::MAX // Dummy value to signify that the period is long + } + } + } + + #[inline(always)] + fn byteset_contains(&self, byte: u8) -> bool { + (self.byteset >> ((byte & 0x3f) as usize)) & 1 != 0 + } + + // One of the main ideas of Two-Way is that we factorize the needle into + // two halves, (u, v), and begin trying to find v in the haystack by scanning + // left to right. If v matches, we try to match u by scanning right to left. + // How far we can jump when we encounter a mismatch is all based on the fact + // that (u, v) is a critical factorization for the needle. + #[inline(always)] + fn next<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) + -> S::Output + where S: TwoWayStrategy + { + // `next()` uses `self.position` as its cursor + let old_pos = self.position; + 'search: loop { + // Check that we have room to search in + if needle.len() > haystack.len() - self.position { + self.position = haystack.len(); + return S::rejecting(old_pos, self.position); + } + + if S::use_early_reject() && old_pos != self.position { + return S::rejecting(old_pos, self.position); + } + + // Quickly skip by large portions unrelated to our substring + if !self.byteset_contains(haystack[self.position + needle.len() - 1]) { + self.position += needle.len(); + if !long_period { + self.memory = 0; + } + continue 'search; + } + + // See if the right part of the needle matches + let start = if long_period { self.crit_pos } + else { cmp::max(self.crit_pos, self.memory) }; + for i in start..needle.len() { + if needle[i] != haystack[self.position + i] { + self.position += i - self.crit_pos + 1; + if !long_period { + self.memory = 0; + } + continue 'search; + } + } + + // See if the left part of the needle matches + let start = if long_period { 0 } else { self.memory }; + for i in (start..self.crit_pos).rev() { + if needle[i] != haystack[self.position + i] { + self.position += self.period; + if !long_period { + self.memory = needle.len() - self.period; + } + continue 'search; + } + } + + // We have found a match! + let match_pos = self.position; + + // Note: add self.period instead of needle.len() to have overlapping matches + self.position += needle.len(); + if !long_period { + self.memory = 0; // set to needle.len() - self.period for overlapping matches + } + + return S::matching(match_pos, match_pos + needle.len()); + } + } + + // Follows the ideas in `next()`. + // + // All the definitions are completely symmetrical, with period(x) = period(reverse(x)) + // and local_period(u, v) = local_period(reverse(v), reverse(u)), so if (u, v) + // is a critical factorization, so is (reverse(v), reverse(u)). Similarly, + // the "period" stored in self.period is the real period if long_period is + // false, and so is still valid for a reversed needle, and if long_period is + // true, all the algorithm requires is that self.period is less than or + // equal to the real period, which must be true for the forward case anyway. + // + // To search in reverse through the haystack, we search forward through + // a reversed haystack with a reversed needle, and the above paragraph shows + // that the precomputed parameters can be left alone. + #[inline] + fn next_back<S>(&mut self, haystack: &[u8], needle: &[u8]) + -> S::Output + where S: TwoWayStrategy + { + // `next_back()` uses `self.end` as its cursor -- so that `next()` and `next_back()` + // are independent. + let old_end = self.end; + 'search: loop { + // Check that we have room to search in + if needle.len() > self.end { + self.end = 0; + return S::rejecting(0, old_end); + } + + if S::use_early_reject() && old_end != self.end { + return S::rejecting(self.end, old_end); + } + + // Quickly skip by large portions unrelated to our substring + if !self.byteset_contains(haystack[self.end - needle.len()]) { + self.end -= needle.len(); + continue 'search; + } + + // See if the left part of the needle matches + for i in (0..self.crit_pos).rev() { + if needle[i] != haystack[self.end - needle.len() + i] { + self.end -= self.crit_pos - i; + continue 'search; + } + } + + // See if the right part of the needle matches + for i in self.crit_pos..needle.len() { + if needle[i] != haystack[self.end - needle.len() + i] { + self.end -= self.period; + continue 'search; + } + } + + // We have found a match! + let match_pos = self.end - needle.len(); + // Note: sub self.period instead of needle.len() to have overlapping matches + self.end -= needle.len(); + + return S::matching(match_pos, match_pos + needle.len()); + } + } + + // Computes a critical factorization (u, v) of `arr`. + // Specifically, returns (i, p), where i is the starting index of v in some + // critical factorization (u, v) and p = period(v) + #[inline] + fn maximal_suffix(arr: &[u8], reversed: bool) -> (usize, usize) { + let mut left: usize = !0; // Corresponds to i in the paper + let mut right = 0; // Corresponds to j in the paper + let mut offset = 1; // Corresponds to k in the paper + let mut period = 1; // Corresponds to p in the paper + + while right + offset < arr.len() { + let a; + let b; + if reversed { + a = arr[left.wrapping_add(offset)]; + b = arr[right + offset]; + } else { + a = arr[right + offset]; + b = arr[left.wrapping_add(offset)]; + } + if a < b { + // Suffix is smaller, period is entire prefix so far. + right += offset; + offset = 1; + period = right.wrapping_sub(left); + } else if a == b { + // Advance through repetition of the current period. + if offset == period { + right += offset; + offset = 1; + } else { + offset += 1; + } + } else { + // Suffix is larger, start over from current location. + left = right; + right += 1; + offset = 1; + period = 1; + } + } + (left.wrapping_add(1), period) + } +} + +// TwoWayStrategy allows the algorithm to either skip non-matches as quickly +// as possible, or to work in a mode where it emits Rejects relatively quickly. +trait TwoWayStrategy { + type Output; + fn use_early_reject() -> bool; + fn rejecting(usize, usize) -> Self::Output; + fn matching(usize, usize) -> Self::Output; +} + +/// Skip to match intervals as quickly as possible +enum MatchOnly { } + +impl TwoWayStrategy for MatchOnly { + type Output = Option<(usize, usize)>; + + #[inline] + fn use_early_reject() -> bool { false } + #[inline] + fn rejecting(_a: usize, _b: usize) -> Self::Output { None } + #[inline] + fn matching(a: usize, b: usize) -> Self::Output { Some((a, b)) } +} + +/// Emit Rejects regularly +enum RejectAndMatch { } + +impl TwoWayStrategy for RejectAndMatch { + type Output = SearchStep; + + #[inline] + fn use_early_reject() -> bool { true } + #[inline] + fn rejecting(a: usize, b: usize) -> Self::Output { SearchStep::Reject(a, b) } + #[inline] + fn matching(a: usize, b: usize) -> Self::Output { SearchStep::Match(a, b) } +} diff --git a/src/libcore/tuple.rs b/src/libcore/tuple.rs index ba6a7c4a5fe..6c5ff222323 100644 --- a/src/libcore/tuple.rs +++ b/src/libcore/tuple.rs @@ -8,7 +8,7 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -//! Operations on tuples +//! A finite heterogeneous sequence, `(T, U, ..)` //! //! To access a single element of a tuple one can use the `.0` //! field access syntax. @@ -28,7 +28,6 @@ //! * `Default` #![stable(feature = "rust1", since = "1.0.0")] -#![doc(primitive = "tuple")] use clone::Clone; use cmp::*; |