Commit Graph
76 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
Jeremy Schonfeld 3e120b48bb [CMake] Reduce path lengths in single-module build (#392)
* Eliminate relative paths from the cmake single-module build

* Attempt to reduce length of paths in single module build
2024-06-26 08:39:11 -07:00
Jeremy Schonfeld ee97538f5b Add Single Module Build Mode to CMake for Foundation (#385)
* Add new single-module and foundation-toolchain-module modes to CMake build

* Fix allowable client flag syntax
2024-06-03 16:15:50 -07:00
Karoy Lorentey a0b839d7de [Rope] Fix copy-on-write violation in Rope.join
Rope.join has a logic error where it fails to properly ensure uniqueness of child node references before zipping the two b-trees together.

rdar://128450202
2024-05-31 17:12:07 -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
Charles Hu ba5154b934 Rename RopeModule to _RopeModule in CMakeLists.txt to match Package.swift 2024-04-30 11:23:27 -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 33f23b6a06 [RopeModule] Remove unnecessary typealiases
These render the emitted .swiftinterface unusable when the module is built with library evolution enabled.
2023-10-18 17:57:00 -07:00
Karoy Lorentey bd1a622735 [CMake, Xcode] Update buid configurations 2023-10-18 15:54:07 -07:00
Karoy Lorentey de2c8a9086 [RopeModule] Allow building with library evolution enabled
rdar://114659667
2023-10-18 14:22:12 -07:00
Karoy Lorentey 03e7f0c401 [Rope] Fix find to return a zero remainder for the end position 2023-06-02 17:37:30 -07:00
Karoy Lorentey 03c9ef743a [Rope] Fix crash when calling replaceSubrange/removeSubrange on an empty rope 2023-06-01 20:24:24 -07:00
Karoy Lorentey dce7b156e7 [Rope] remove(at:): Fix assertion when removing the last item creates a deficiency 2023-04-17 17:20:07 -07:00
Karoy Lorentey b0fe7ca8ba [Rope] replaceSubrange: take a sequence, not a collection 2023-04-14 14:38:30 -07:00
Karoy Lorentey 3fa52c48de [Rope] Add remove(at:), remove(at:in:) variants that preserve the position 2023-04-13 19:36:09 -07:00
Karoy Lorentey 1925ed3001 [Rope] update(at:by:): Invalidate indices
Calling this function is supposed to invalidate all indices other than
the input index — so let’s do that.
2023-04-12 17:55:19 -07:00
Karoy Lorentey cead2b3d64 [Rope] index(_:offsetBy:in:preferEnd:) fix result tuple labeling
This renames `remainder` to `remaining`, restoring API consistency.
2023-04-12 17:54:13 -07:00
Karoy Lorentey bc21b90ff1 [Rope] Minor usability fixes and API additions 2023-04-12 17:53:04 -07:00
Karoy Lorentey 4afdfe4da2 [Rope] Flesh out docs a little bit
Rope remains woefully undocumented, and I suspect its abstraction
level isn’t right for general use, but let’s see if writing up some
documentation for it will make it a bit more accessible.
2023-04-12 17:52:19 -07:00
Karoy Lorentey 900e7851ab Merge pull request #271 from lorentey/fix-rope-sendable
Rope: Fix `Sendable` conformance
2023-04-10 17:43:23 -07:00
Karoy Lorentey 7c17b02963 Merge pull request #272 from lorentey/fix-bigstring-utility
BigString: Fix String.Index._knownScalarAligned
2023-04-10 17:42:39 -07:00
Karoy Lorentey 454c84b5e4 Make most of Rope inlinable 2023-04-10 16:56:30 -07:00
Karoy Lorentey 96d7162888 BigString: Fix String.Index._knownScalarAligned
This member isn’t currently used, but unlike its counterpart in the stdlib, this one accidentally sets the character-alignment bit.
2023-04-10 16:50:37 -07:00
Karoy Lorentey 9c3328e235 Rope: Fix Sendable conformance
`Rope._Node` wasn’t declared `Sendable`, which triggered valid warnings.
2023-04-10 16:45:28 -07: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 cbab9e3737 Introduce COLLECTIONS_SINGLE_MODULE condition 2023-03-21 18:42:33 -07:00
Karoy Lorentey 8394ea7575 Clean up test definitions 2023-03-21 01:30:03 -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 dc23b4d621 Rope: Fix splitting logic after insertions
I changed the minNodeSize formula to match with the B-tree definition, but I failed to match the insertion logic, so it left trees with undersized nodes. D’oh!
2023-03-21 01:06:53 -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 535b8b8562 Fix compatbility with Swift toolchains below 5.8 2023-03-20 14:25:28 -07:00
Karoy Lorentey ddcd1788aa Unconditionally enable use of _CharacterRecognizer’s Equatable conformance if we aren’t building a package 2023-03-20 13:12:14 -07:00
Karoy Lorentey da78365bef _BString: Add isIdentical(to:) to all string views 2023-03-20 13:12:14 -07:00
Karoy Lorentey b50fb5aab5 _BString.resolve: Don’t crash when resolving indices in the empty string 2023-03-20 13:12:14 -07:00
Karoy Lorentey 64a8098bf9 _BSubstring.UnicodeScalarView: Fix range-replacing mutations that don’t take indices 2023-03-20 13:12:14 -07:00
Karoy Lorentey b355480eb7 _BString: Make unicodeScalars properties mutable 2023-03-20 13:12:13 -07:00
Karoy Lorentey b8927d819b BigString: Flesh out views, make them consistent with _BString 2023-03-20 13:12:13 -07:00
Karoy Lorentey d79a752fc8 _BString: Review views & add missing functionality/shortcuts 2023-03-20 13:12:13 -07:00
Karoy Lorentey cffcd517a2 BigString: Start modernizing 2023-03-20 13:12:13 -07:00
Karoy Lorentey 6a7f53c3da _BString: Add conversion initializers from all views 2023-03-20 13:12:12 -07:00
Karoy Lorentey 03d7c43c22 _BString: Add index rounding methods to all views 2023-03-20 13:12:12 -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