| Age | Commit message (Collapse) | Author | Lines |
|---|
|
It was pointing at the issue for `placement_new_protocol`.
|
|
|
|
|
|
Fixes #27958
|
|
The iterator protocol specifies that the iteration ends with the return
value `None` from `.next()` (or `.next_back()`) and it is unspecified
what further calls return. The chain adaptor must account for this in
its DoubleEndedIterator implementation.
It uses three states:
- Both `a` and `b` are valid
- Only the Front iterator (`a`) is valid
- Only the Back iterator (`b`) is valid
The fourth state (neither iterator is valid) only occurs after Chain has
returned None once, so we don't need to store this state.
Fixes #26316
|
|
The implementation of the remainder operation belongs to
librustc_trans, but it is also stubbed out in libcore in order to
expose it as a trait on primitive types. Instead of exposing some
implementation details (like the upcast to `f64` in MSVC), use a
minimal implementation just like that of the `Div` trait.
|
|
|
|
|
|
|
|
These commits move libcore into a state so that it's ready for stabilization, performing some minor cleanup:
* The primitive modules for integers in the standard library were all removed from the source tree as they were just straight reexports of the libcore variants.
* The `core::atomic` module now lives in `core::sync::atomic`. The `core::sync` module is otherwise empty, but ripe for expansion!
* The `core::prelude::v1` module was stabilized after auditing that it is a subset of the standard library's prelude plus some primitive extension traits (char, str, and slice)
* Some unstable-hacks for float parsing errors were shifted around to not use the same unstable hacks (e.g. the `flt2dec` module is now used for "privacy").
After this commit, the remaining large unstable functionality specific to libcore is:
* `raw`, `intrinsics`, `nonzero`, `array`, `panicking`, `simd` -- these modules are all unstable or not reexported in the standard library, so they're just remaining in the same status quo as before
* `num::Float` - this extension trait for floats needs to be audited for functionality (much of that is happening in #27823) and may also want to be renamed to `FloatExt` or `F32Ext`/`F64Ext`.
* Should the extension traits for primitives be stabilized in libcore?
I believe other unstable pieces are not isolated to just libcore but also affect the standard library.
cc #27701
|
|
Implemented #27759
Example:
|
|
|
|
|
|
I just took out the sentences that were lies. I'm not sure if they need to be replaced.
r? steveklabnik
|
|
There wasn't any particular reason the functions needed to be there
anyway, so just get rid of them, and adjust libstd to compensate.
With this change, libcore depends on exactly two floating-point functions:
fmod and fmodf. They are implicitly referenced because they are used to
implement "%".
Dependencies of libcore on Linux x86-x64 with this patch:
```
0000000000000000 *UND* 0000000000000000 __powidf2
0000000000000000 *UND* 0000000000000000 __powisf2
0000000000000000 *UND* 0000000000000000 fmod
0000000000000000 *UND* 0000000000000000 fmodf
0000000000000000 *UND* 0000000000000000 memcmp
0000000000000000 *UND* 0000000000000000 memcpy
0000000000000000 *UND* 0000000000000000 memset
0000000000000000 *UND* 0000000000000000 rust_begin_unwind
0000000000000000 *UND* 0000000000000000 rust_eh_personality
```
|
|
Stop using stability to hide the implementation details of ParseFloatError and
instead move the error type into the `dec2flt` module. Also move the
implementation blocks of `FromStr for f{32,64}` into `dec2flt` directly.
|
|
This commit stabilizes the prelude::v1 module of libcore after verifying that
it's a subset of the prelude of the standard library with the addition of a few
extension traits.
|
|
StrSearcher: Implement the complete reverse case for the two way algorithm
Fix quadratic behavior in StrSearcher in reverse search with periodic
needles.
This commit adds the missing pieces for the "short period" case in
reverse search. The short case will show up when the needle is literally
periodic, for example "abababab".
Two way uses a "critical factorization" of the needle: x = u v.
Searching matches v first, if mismatch at character k, skip k forward.
Matching u, if mismatch, skip period(x) forward.
To avoid O(mn) behavior after mismatch in u, memorize the already
matched prefix.
The short period case requires that |u| < period(x).
For the reverse search we need to compute a different critical
factorization x = u' v' where |v'| < period(x), because we are searching
for the reversed needle. A short v' also benefits the algorithm in
general.
The reverse critical factorization is computed quickly by using the same
maximal suffix algorithm, but terminating as soon as we have a location
with local period equal to period(x).
This adds extra fields crit_pos_back and memory_back for the reverse
case. The new overhead for TwoWaySearcher::new is low, and additionally
I think the "short period" case is uncommon in many applications of
string search.
The maximal_suffix methods were updated in documentation and the
algorithms updated to not use !0 and wrapping add, variable left is now
1 larger, offset 1 smaller.
Use periodicity when computing byteset: in the periodic case, just
iterate over one period instead of the whole needle.
Example before (rfind) after (twoway_rfind) benchmark shows the removal
of quadratic behavior.
needle: "ab" * 100, haystack: ("bb" + "ab" * 100) * 100
```
test periodic::rfind ... bench: 1,926,595 ns/iter (+/- 11,390) = 10 MB/s
test periodic::twoway_rfind ... bench: 51,740 ns/iter (+/- 66) = 386 MB/s
```
|
|
Overload the operators using the traits so that things mostly keep
working during the deprecation period.
|
|
|
|
This functionality will be available out of tree in the `simd` crate on
crates.io.
[breaking-change]
|
|
This mirrors the same hierarchy in the standard library.
|
|
All of the modules in the standard library were just straight reexports of those
in libcore, so remove all the "macro modules" from the standard library and just
reexport what's in core directly.
|
|
I just took out the sentences that were lies. I'm not sure if they need to be replaced.
|
|
There wasn't any particular reason the functions needed to be there
anyway, so just get rid of them, and adjust libstd to compensate.
With this change, libcore depends on exactly two floating-point functions:
fmod and fmodf. They are implicitly referenced because they are
used to implement "%".
|
|
Break out a separate static method to create the "byteset".
|
|
|
|
|
|
|
|
This patch rewrites code in several places which assume that the current target has either 32-bit or 64-bit pointers so that it can support arbitrary-width pointers.
It does not completely remove all assumptions of pointer width, but it does reduce them significantly. There is a discussion [here](https://internals.rust-lang.org/t/adding-16-bit-pointer-support/2484/10) about the change.
|
|
|
|
|
|
|
|
This PR implements the majority of RFC 1214. In particular, it implements:
- the new outlives relation
- comprehensive WF checking
For the most part, new code receives warnings, not errors, though 3 regressions were found via a crater run.
There are some deviations from RFC 1214. Most notably:
- we still consider implied bounds from fn ret; this intersects other soundness issues that I intend to address in detail in a follow-up RFC. Fixing this without breaking a lot of code probably requires rewriting compare-method somewhat (which is probably a good thing).
- object types do not check trait bounds for fear of encountering `Self`; this was left as an unresolved question in RFC 1214, but ultimately feels inconsistent.
Both of those two issues are highlighted in the tracking issue, https://github.com/rust-lang/rust/issues/27579. #27579 also includes a testing matrix with new tests that I wrote -- these probably duplicate some existing tests, I tried to check but wasn't quite sure what to look for. I tried to be thorough in testing the WF relation, at least, but would welcome suggestions for missing tests.
r? @nrc (or perhaps someone else?)
|
|
This commit removes all unstable and deprecated functions in the standard
library. A release was recently cut (1.3) which makes this a good time for some
spring cleaning of the deprecated functions.
|
|
Completely rewrite the conversion of decimal strings to `f64` and `f32`. The code is intended to be absolutely positively completely 100% accurate (when it doesn't give up). To the best of my knowledge, it achieves that goal. Any input that is not rejected is converted to the floating point number that is closest to the true value of the input. This includes overflow, subnormal numbers, and underflow to zero. In other words, the rounding error is less than or equal to 0.5 units in the last place. Half-way cases (exactly 0.5 ULP error) are handled with half-to-even rounding, also known as banker's rounding.
This code implements the algorithms from the paper [How to Read Floating Point Numbers Accurately][paper] by William D. Clinger, with extensions to handle underflow, overflow and subnormals, as well as some algorithmic optimizations.
# Correctness
With such a large amount of tricky code, many bugs are to be expected. Indeed tracking down the obscure causes of various rounding errors accounts for the bulk of the development time. Extensive tests (taking in the order of hours to run through to completion) are included in `src/etc/test-float-parse`: Though exhaustively testing all possible inputs is impossible, I've had good success with generating millions of instances from various "classes" of inputs. These tests take far too long to be run by @bors so contributors who touch this code need the discipline to run them. There are `#[test]`s, but they don't even cover every stupid mistake I made in course of writing this.
Another aspect is *integer* overflow. Extreme (or malicious) inputs could cause overflow both in the machine-sized integers used for bookkeeping throughout the algorithms (e.g., the decimal exponent) as well as the arbitrary-precision arithmetic. There is input validation to reject all such cases I know of, and I am quite sure nobody will *accidentally* cause this code to go out of range. Still, no guarantees.
# Limitations
Noticed the weasel words "(when it doesn't give up)" at the beginning? Some otherwise well-formed decimal strings are rejected because spelling out the value of the input requires too many digits, i.e., `digits * 10^abs(exp)` can't be stored in a bignum. This only applies if the value is not "obviously" zero or infinite, i.e., if you take a near-infinity or near-zero value and add many pointless fractional digits. At least with the algorithm used here, computing the precise value would require computing the full value as a fraction, which would overflow. The precise limit is `number_of_digits + abs(exp) > 375` but could be raised almost arbitrarily. In the future, another algorithm might lift this restriction entirely.
This should not be an issue for any realistic inputs. Still, the code does reject inputs that would result in a finite float when evaluated with unlimited precision. Some of these inputs are even regressions that the old code (mostly) handled, such as `0.333...333` with 400+ `3`s. Thus this might qualify as [breaking-change].
# Performance
Benchmarks results are... tolerable. Short numbers that hit the fast paths (`f64` multiplication or shortcuts to zero/inf) have performance in the same order of magnitude as the old code tens of nanoseconds. Numbers that are delegated to Algorithm Bellerophon (using floats with 64 bit significand, implemented in software) are slower, but not drastically so (couple hundred nanoseconds).
Numbers that need the AlgorithmM fallback (for `f64`, roughly everything below 1e-305 and above 1e305) take far, far longer, hundreds of microseconds. Note that my implementation is not quite as naive as the expository version in the paper (it needs one to four division instead of ~1000), but division is fundamentally pretty expensive and my implementation of it is extremely simple and slow.
All benchmarks run on a mediocre laptop with a i5-4200U CPU under light load.
# Binary size
Unfortunately the implementation needs to duplicate almost all code: Once for `f32` and once for `f64`. Before you ask, no, this cannot be avoided, at least not completely (but see the Future Work section). There's also a precomputed table of powers of ten, weighing in at about six kilobytes.
Running a stage1 `rustc` over a stand-alone program that simply parses pi to `f32` and `f64` and outputs both results reveals that the overhead vs. the old parsing code is about 44 KiB normally and about 28 KiB with LTO. It's presumably half of that + 3 KiB when only one of the two code paths is exercised.
| rustc options | old | new | delta |
|--------------------------- |--------- |--------- |----------- |
| [nothing] | 2588375 | 2633828 | 44.39 KiB |
| -O | 2585211 | 2630688 | 44.41 KiB |
| -O -C lto | 1026353 | 1054981 | 27.96 KiB |
| -O -C lto -C link-args=-s | 414208 | 442368 | 27.5 KiB |
# Future Work
## Directory layout
The `dec2flt` code uses some types embedded deeply in the `flt2dec` module hierarchy, even though nothing about them it formatting-specific. They should be moved to a more conversion-direction-agnostic location at some point.
## Performance
It could be much better, especially for large inputs. Some low-hanging fruit has been picked but much more work could be done. Some specific ideas are jotted down in `FIXME`s all over the code.
## Binary size
One could try to compress the table further, though I am skeptical. Another avenue would be reducing the code duplication from basically everything being generic over `T: RawFloat`. Perhaps one can reduce the magnitude of the duplication by pushing the parts that don't need to know the target type into separate functions, but this is finicky and probably makes some code read less naturally.
## Other bases
This PR leaves `f{32,64}::from_str_radix` alone. It only replaces `FromStr` (and thus `.parse()`). I am convinced that `from_str_radix` should not exist, and have proposed its [deprecation and speedy removal][deprecate-radix]. Whatever the outcome of that discussion, it is independent from, and out of scope for, this PR.
Fixes #24557
Fixes #14353
r? @pnkfelix
cc @lifthrasiir @huonw
[paper]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.4152
[deprecate-radix]: https://internals.rust-lang.org/t/deprecate-f-32-64-from-str-radix/2405
|
|
Provides a custom implementation of Iterator methods `count`, `nth`, and `last` for the structures `slice::{Windows,Chunks,ChunksMut}` in the core module.
These implementations run in constant time as opposed to the default implementations which run in linear time.
Addresses Issue #24214
r? @aturon
|
|
|
|
This commit removes all unstable and deprecated functions in the standard
library. A release was recently cut (1.3) which makes this a good time for some
spring cleaning of the deprecated functions.
|
|
Implemented count, nth, and last in constant time for Windows, Chunks,
and ChunksMut created from a slice.
Included checks for overflow in the implementation of nth().
Also added a test for each implemented method to libcoretest.
Addresses #24214
|
|
|
|
* Lots of core prelude imports removed
* Makefile support for MSVC env vars and Rust crates removed
* Makefile support for morestack removed
|
|
Also fixes a few outdated links.
|
|
* Lots of core prelude imports removed
* Makefile support for MSVC env vars and Rust crates removed
* Makefile support for morestack removed
|
|
The "nth" element can be confusing. In an array context, we know indexes
start from 0 but one may believe this is not the case with "nth". For
example, would `.nth(1)` return the first (1th/1st) or the second
element? Rephrase a bit to be less confusing.
r? @steveklabnik
|
|
Also fixes a few outdated links.
|
|
|
|
|
|
The replacements are functions that usually use a single `mem::transmute` in
their body and restrict input and output via more concrete types than `T` and
`U`. Worth noting are the `transmute` functions for slices and the `from_utf8*`
family for mutable slices. Additionally, `mem::transmute` was often used for
casting raw pointers, when you can already cast raw pointers just fine with
`as`.
|
|
The "nth" element can be confusing. In an array context, we know indexes
start from 0 but one may believe this is not the case with "nth". For
example, would `.nth(1)` return the first (1th/1st) or the second
element? Rephrase a bit to be less confusing.
|
