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