Drop append-related @inlinable annotations for String, StringGuts,
StringStorage, and the Views. Drop several for larger operations, such
as case conversion. Drop as many as we can from StringGuts for now.
With the number of tests Swift does, this had a relatively high chance to fail
regularly somewhere.
Also, rejecting the lower tail means rejecting things that are perfectly
uniform, which I don't think should be the purpose of this test.
I noticed this during testing, but it has nothing to do with the other changes
in this PR. This static violation has always been present as a warning and would
continue to be a warning after my changes.
When Set/Dictionary is nested in another Set, the boundaries of the nested collections weren’t correctly delineated in commutative hashing.
For example, these Sets all hashed the same:
[[1, 2], [3, 4]]
[[1, 3], [2, 4]]
[[1, 4], [2, 3]]
Hash collisions could thus be systematically generated.
To fix this, remove collection-level support for one-shot hashing and revert to the previous method of generating hash values. (Set is still able to support one-shot hashing for its members, though.)
The new _rawHashValue(seed:) requirement allows stdlib types to specialize their hashing when they’re hashed on their own (i.e., not as a component of some composite type).
This makes it possible to get rid of discriminator/terminator values and to eliminate most of Hasher’s resiliency overhead, leading to a measurable speedup, especially for tiny keys.
Newly internal declarations include Hasher._seed and the integer overloads of Hasher._combine(_:), as well as _SipHash13 and _SipHash24.
Unify the interfaces of these SipHash testing structs with Hasher. Update SipHash test to cover Hasher, too.
Add @usableFromInline to all newly internal stuff. In addition to its normal use, it also enables white box testing; compile tests that need to use these declarations with -disable-access-control.
This prototype is not fully implemented, and it relies on specific hash values to not trigger unhandled cases.
To keep its test working, define and use a custom hashing interface that emulates hashValue behavior prior to SE-0206.
This is safe to do with hash(into:), because random hash collisions can be eliminated with awesome certainty by trying a number of different hash seeds. (Unless there is a weakness in SipHash.)
In some cases, we intentionally want hashing to produce looser equivalency classes than equality — to let those cases keep working, add an optional hashEqualityOracle parameter.
Review usages of checkHashable and add hash oracles as needed.
StdlibUnittest uses gyb to avoid duplicating many source-context
arguments. However, this means that any test that wishes to add new
expect helpers has to also be gybbed. Given that this structure hasn't
changed in years, and we should have a real language support
eventually, de-gyb it.
Since this code was first written, we've added more language features that introduce the opportunity for a materializeForSet protocol witness to have an incompatible polymorphic convention with its concrete implementation:
- In a conditional conformance, if a witness comes from a constrained extension with additional protocol requirements, then the witness will require those conformances as additional polymorphic arguments, making its materializeForSet uncallable from code using the protocol witness.
- Given a subscript requirement, the witness may be a generic subscript with a more general signature than the witness, making the generic arguments to the concrete materializeForSet callback incompatible with those expected for the witness.
Longer term, representing materializeForSet patterns using accessor coroutines should obviate the need for this hack. For now, it's necessary for correctness, addressing rdar://problem/35760754.
Switch StringObject and StringGuts from opaquely storing tagged cocoa
strings into storing small strings. Plumb small string support
throughout the standard library's routines.
Streamline internal String creation. Previously, everything funneled
into a single generic function, however, every single call of the
generic funnel had relevant specific information that could be used
for a more efficient algorithm.
In preparation for efficiently forming small strings, refactor this
logic into a handful of more specialized subroutines to preserve more
specific information from the callers.
This assumes these will land in Swift 4.1; the attributes need to be adjusted if that turns out not to be the case.
It seems @available for protocol conformances is not yet functional. I added attributes for those anyway, marked with FIXME(conformance-availability).
# Conflicts:
# stdlib/public/core/ExistentialCollection.swift.gyb
# stdlib/public/core/Mirror.swift
Now that Array and Dictionary conform to Hashable, we need to make sure that their bridged counterparts provide the same hash values when converted to AnyHashable.
* Add conditional Hashable conformance to Optional, Dictionary, Array, ArraySlice and ContiguousArray
* Modified hashValue implementations
The hashValues are now calculated similar to the automatically synthesized values when conforming to Hashable.
This entails using _combineHashValues as values of the collections are iterated - as well as calling _mixInt before returning the hash.
* Added FIXMEs as suggested by Max Moiseev
* Use checkHashable to check Hashable conformance
* Use 2 space indentation
* Hashing of Dictionary is now independent of traversal order
* Added a test to proof failure of (previous) wrong implementation of Dictionary hashValue. Unfortunately it does not work.
* Removed '_mixInt' from 'hashValue' implementation of Optional and Array types based on recommendations from lorentey
* Another attempt at detecting bad hashing due to traversal order
* Dictionary Hashable validation tests now detect bad hashing due to dependence on traversal order
* Removed superfluous initial _mixInt call for Dictionary hashValue implementation.
* Add more elements to dictionary in test to increase the number of possible permutations - making it more likely to detect order-dependent hashes
* Added Hashable conformance to CollectionOfOne, EmptyCollection and Range types
* Fix indirect referral to the only member of CollectionOfOne
* Re-added Hashable conformance to Range after merge from master
* Change hashValue based on comment from @lorentey
* Remove tests for conditional Hashable conformance for Range types. This is left for a followup PR
* Added tests for CollectionOfOne and EmptyCollection
* Added conditional conformance fo Equatable and Hashable for DictionaryLiteral. Added tests too.
* Added conditional Equatable and Hashable conformance to Slice
* Use 'elementsEqual' for Slice equality operator
* Fixed documentation comment and indentation
* Fix DictionaryLiteral equality implementation
* Revert "Fix DictionaryLiteral equality implementation"
This reverts commit 7fc1510bc3.
* Fix DictionaryLiteral equality implementation
* Use equalElements(:by:) to compare DictionaryLiteral elements
* Added conditional conformance for Equatable and Hashable to AnyCollection
* Revert "Use 'elementsEqual' for Slice equality operator"
This reverts commit 0ba2278b96.
* Revert "Added conditional Equatable and Hashable conformance to Slice"
This reverts commit 84f9934bb4.
* Added conditional conformance for Equatable and Hashable for ClosedRange
Stress tests are, by definition, stressful. They intentionally burn a
lot of resources by using randomness to hopefully surface state machine
bugs. Additionally, many stress tests are multi-threaded these days and
they may attempt to use all of the available CPUs to better uncover
bugs. In isolation, this is not a problem, but the test suite as a whole
assumes that individual tests are single threaded and therefore running
multiple stress tests at once can quickly spiral out of control.
This change formalizes stress tests and then treats them like long
tests, i.e. tested via 'check-swift-all' and otherwise opt-in.
Finally, with this change, the CI build bots might need to change if
they are still only testing 'validation' instead of all of the tests.
I see three options:
1) Run all of the tests. -- There are very few long tests left these
days, and the additional costs seems small relative to the cost of
the whole validation test suite before this change.
2) Continue checking 'validation', now sans stress tests.
3) Check 'validation', *then* the stress tests. If the former doesn't
pass, then there is no point in the latter, and by running the stress
tests separately, they stand a better chance of uncovering bugs and
not overwhelming build bot resources.
