Speed up conversion between UTF-16 offset ranges
and string index ranges, by carefully switching
between absolute and relative index calculations,
depending on the distance we need to go.
It is a surprisingly tricky puzzle to do this
correctly while avoiding redundant calculations.
Offset ranges within substrings add the additional
complication of having to bias offset values with
the absolute offset of the substring’s start index.
We commonly start from the `startIndex`, in which case
`_nativeGetOffset` is essentially free. Consider this
case when calculating the threshold for using breadcrumbs.
Previously we insisted on using breadcrumbs even if we only needed to
travel a very short way. This could be as much as ten times slower
than the naive algorithm of simply visiting all the Unicode scalars
in between the start and the end.
(Using breadcrumbs generally means that we need to walk to both
endpoints from their nearest breadcrumb, which on average requires
walking half the distance between breadcrumbs — and this can mean
visiting vastly more Unicode scalars than the ones that are simply
lying in between the endpoints themselves.)
This patch goes through and adds zippering and the swift module
dependencies to a bunch of pieces of the swift runtimes. Here's to
hoping I hit everything that needed to be hit. :D
With this patch, I'm seeing the appropriate modules under
lib/swift/maccatalyst, so things seem to be working right.
AnyKeyPath's debugDescription assumes there's always at least one component, but `\Type.self` produces an empty keypath. Special-case the empty case to display a `.self` component.
rdar://103237845
This discussion borrows wording from the docs for the default
implementation of Collection.count[1], which are inherited by many other
symbols, but with a rewrite here because String doesn't guarantee
random-access performance (doesn't conform to RandomAccessCollection),
so accessing the count is never an O(1) operation.
1: https://developer.apple.com/documentation/swift/collection/count-4l4qk
This fixes a failure compiling the stdlib where the importer cannot find (i.e.,
refuses to import) functions _stdlib_remainderl and _stdlib_squareRootl.
While we’re vacillating on how best to add CustomStringConvertible
and CustomDebugStringConvertible conformances to String.Index, add
the prospective implementations as underscored-but-public members,
to make life a little more bearable for people who need to debug
string index operations.
- originally had avoided `_copyContents` because all the standard library fast paths were already covered.
- however Swift Collections piecewise-contiguous collections still rely on `_copyContents` to accelerate copies.
