Commit Graph
95 Commits
Author SHA1 Message Date
Karoy Lorentey f9a6df8a55 [_RopeModule] Fix infinite loop while hashing the UTF-8 view of a multi-chunk big substring 2026-04-30 15:29:22 -07:00
Karoy Lorentey 1c69635852 Add SPDX-License-Identifier tags 2026-03-05 19:39:24 -08:00
Karoy Lorentey d9b09ecde8 Update copyright dates 2026-03-05 19:39:20 -08:00
Karoy Lorentey 3941dab5b0 [BasicContainers] Implement removals on RigidSet and UniqueSet
Dictionaries are still to be done.
2026-02-20 18:19:51 -08:00
Karoy Lorentey 9503f8fe57 Improve consistency of precondition failure messages
More uniform message strings should feel better, and they should ever so slightly reduce code size.
2026-02-04 10:27:17 -08:00
Alejandro Alonso 691855a60f Bring back _isUTF16TrailingSurrogate 2025-10-14 09:50:14 -07:00
Karoy Lorentey 6b8aa0202c [RopeModule] Update CMakeLists.txt 2025-10-10 16:01:03 -07:00
Karoy Lorentey 006ab60c42 Xcode/Collections.xcodeproj: Fix ability to build & test BigString 2025-10-10 15:53:16 -07:00
Karoy Lorentey a7e40d2055 Fix warnings 2025-10-02 18:29:35 -07:00
Alejandro Alonso a1f8f33a5b Make BigString unavailable in embedded 2025-09-30 12:40:09 -07:00
Alejandro Alonso 729869eb6d Use the underscored lifetime attribute 2025-09-30 09:11:47 -07:00
Alejandro Alonso a9bfbeac39 Conditionalize big string sources on 6.2 compiler
add some more
2025-09-30 09:04:52 -07:00
Alejandro Alonso 235030c10b Refactor BigString._Chunk to be its own managed buffer of UTF8 2025-09-30 09:04:19 -07:00
Karoy Lorentey bc9c63ae41 [Rope] Highlight CoW issue in Swift 6 mode 2025-08-17 13:33:40 -07:00
Karoy Lorentey 5f03d1bc24 Adopt availability macros 2025-08-17 13:23:01 -07:00
Karoy Lorentey fc411858ee [BigString] Speed up index distance calculations
This implements a roughly 40-45% improvement for distance measurements over `BigString`’s character and Unicode Scalar views.

Interestingly, we don’t see an improvement for UTF-16 views — I’m guessing this is due to String’s breadcrumbing. (And it will go away with the upcoming UTF8Span-ification of this type.)

The benchmarks I added only show an improvement for multi-chunk big string instances, but this is merely an artifact of the specific algorithm that is being measured — for single-chunk strings, the existing measurement method is already optimal, so the new heuristic never triggers for this particular payload.
2025-06-23 15:21:40 -07:00
Karoy Lorentey 65f99e3eff [BigString] Fix character indexing operations
BigString sometimes miscounted distances in its character view due to alignment issues. Resolve this by overhauling distance calculations in the character metric:

- Introduce a `prefixSize` function in `_StringMetric`, distinct from `distance`.
- In the metric-agnostic index distance algorithm, use `prefixCount` to avoid double-counting characters that cross (or end on) chunk boundaries.
- Simplify `_StringMetric.distance` by requiring that `start <= end`.
- Crucially, change character-index operations to start by rounding each input index down to the nearest character break.
2025-06-17 17:28:02 -07:00
Karoy Lorentey 755c06dd88 Adopt _pointerBitWidth 2024-09-25 14:17:32 -07:00
Karoy Lorentey e4cd17cc53 Remove support code for outdated toolchains 2024-09-25 14:14:48 -07:00
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