Commit Graph
23 Commits
Author SHA1 Message Date
Karoy Lorentey 5e1fe6e8f0 [BigString] Fix accidentally quadratic BigString.init
When ingesting a `String` instance, `BigString` assumes that the input string has a reasonably efficient UTF-8 view.

Unfortunately, that is very much not the case when the input happens to be backed by a bridged NSString object — it appears that in this case, the ingester loop invokes some operation(s) with linear complexity in the size of the entire input, rendering the ingester’s overall complexity quadratic.

The BigString ingester is only expected to operate within a single chunk at the time. It’s unclear precisely which operation triggers the quadratic behavior; ideally we should figure it out and resolve it with a more targeted fix.

In the meantime, a blunt stopgap fix is to force-transcode the input string to UTF-8 at the time the ingester is initialized. This unnecessarily wastes some (temporary) memory on holding the transcoded string, but it avoids the quadratic cliff.
2024-07-15 13:13:44 -07:00
Karoy Lorentey 35d5746117 Rename _CollectionsUtilities to InternalCollectionsUtilities
We are forced to do this due to an Xcode issue (#364) with underscored module names.

This module remains unstable, despite the removal of the underscore. Directly importing it from outside the package remains unsupported. This module and/or its entire contents may go away or change in incompatible ways in any future swift-collections release.
2024-05-29 14:00:13 -07:00
Dimitris Apostolou 7539583245 Fix typos
# Conflicts:
#	Sources/SortedCollections/BTree/_BTree+BidirectionalCollection.swift
#	Sources/SortedCollections/BTree/_BTree+UnsafeCursor.swift
#	Sources/SortedCollections/BTree/_BTree.Builder.swift
#	Sources/SortedCollections/BTree/_BTree.swift
#	Sources/SortedCollections/BTree/_Node.Splinter.swift
#	Sources/SortedCollections/BTree/_Node.Storage.swift
#	Sources/SortedCollections/BTree/_Node.UnsafeHandle+Insertion.swift
#	Sources/SortedCollections/BTree/_Node.swift
#	Tests/SortedCollectionsTests/BTree/Node+Join Tests.swift
2024-02-06 15:52:26 -08:00
Karoy Lorentey ffa4a58bc1 Update remaining copyright notices 2024-02-02 16:20:22 -08:00
Karoy Lorentey 5bce3c9ceb [RopeModule] Adopt _specialize and extend adoption of modern generic decl syntax 2024-02-02 16:20:21 -08:00
Karoy Lorentey 73936bba69 Expose a handful of BigString.Index methods
These help implementing conversions between String.Index and BigString.Index.
2023-04-07 19:26:47 -07:00
Karoy Lorentey 28010b2f6c Use COLLECTIONS_INTERNAL_CHECKS 2023-03-21 01:28:13 -07:00
Karoy Lorentey ad82bc3f80 Naming review 2023-03-21 01:21:43 -07:00
Karoy Lorentey 88286b661d BigString: Fix Issue in utf16.distance when endpoint is on the trailing surrogate of the first scalar in a chunk 2023-03-21 01:04:12 -07:00
Karoy Lorentey 6f3f19d1c5 _Rope → Rope 2023-03-20 23:49:57 -07:00
Karoy Lorentey 51ef8613c2 Underscore more internals 2023-03-20 22:27:32 -07:00
Karoy Lorentey 0ad7f0ce38 _BString → BigString 2023-03-20 21:20:30 -07:00
Karoy Lorentey b022b7fee5 Make _BString and _Rope public 2023-03-20 18:36:37 -07:00
Karoy Lorentey b8927d819b BigString: Flesh out views, make them consistent with _BString 2023-03-20 13:12:13 -07:00
Karoy Lorentey cffcd517a2 BigString: Start modernizing 2023-03-20 13:12:13 -07:00
Karoy Lorentey 258d22947c _BString: Review Equatable implementations 2023-03-20 13:12:12 -07:00
Karoy Lorentey abf5dfd260 _BSubstring: Conform to Comparable 2023-03-20 13:12:12 -07:00
Karoy Lorentey a10439bc32 _BString, _BSubstring: Merge character views into top-level types. Add RangeReplaceableCollection conformances.
This emulates the standard String.
2023-03-20 13:12:12 -07:00
Karoy Lorentey 8c1740ad28 _Rope.Index: Merge height into UInt64 storage.
This leaves 56 bits for path data, which should still be plenty.
(We want to allow big strings to grow to 2^48 UTF-8 code units, to
match the standard String; however, there is no practical need to
support any more, and even that is a stretch.)

Add tests to verify that the tree capacity matches expectations
in Release builds. (In Debug builds, we limit the maximum node size,
which drastically reduces capacity. This is okay.)
2023-03-20 13:12:09 -07:00
Karoy Lorentey 8c8cb5622b Restrict BIgString and _BString to Swift 5.8 and macOS 13.3 /iOS 16.4/etc
These types heavily rely on stdlib functionality that ships in
Swift 5.8; they do not run correctly on earlier releases.
2023-03-20 13:12:09 -07:00
Karoy Lorentey 283d4071bc Assorted bug fixes and refinements 2023-03-20 13:12:08 -07:00
Karoy Lorentey eabd941799 Add some operations taking subsequences 2023-03-20 13:12:07 -07:00
Karoy Lorentey 150a165d73 Add experimental rope implementation 2023-03-20 13:11:21 -07:00