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.
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.
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.)