Declarative String Processing Overview

[Michael_Ilseman]

@ahti

Wrt the bigger picture, I think the idea of good support for multi-tiered processing is very appealing, even beyond strings in data: I've implemented a few binary parsers in recent years, and was always unsatisfied with how different parsing libraries handled extracting information from bit ranges that don't line up with byte boundaries (e.g. parsing 4 6-bit numbers from a 3 byte section of data).

What formats have you had to parse?

The pattern I would recommend for this kind of task is a strongly-typed wrapper around the raw bytes, with computed vars that will do the masking and shifting.

struct EncodedPixel: RawRepresentable {
  var rawValue: (UInt8, UInt8, UInt8)

  var red: UInt32 { ... unpack ... }
  var green: UInt32 { ... unpack ... }
  var blue: UInt32 { ... unpack ... }
  var alpha: UInt32 { ... unpack ... }
}

A failable init can do error checking, if necessary for your format. A encoded pixel parser's conformance to something like CollctionConsumer (as an example interface for composition) would just try to init and advance 3 bytes.

@Karl

That is rather unforunate. The standard library only has an eager split ; there is a lazy version in swift-algorithms , but that's a very big package and some projects may be reluctant to add such massive dependencies. We have a lazy filter , but it's a badly-behaved Collection which can lead to performance and code-size penalties. There is definitely room for improvement when it comes to the standard library's collection algorithms, even outside of this effort.

Definitely improvements to be made to the current laziness situation (CC @timv). Even with an ideal presentation of laziness, it's not quite a drop-in for the script as written (e.g. use of integer subscripting).

A potential issue with approaches which accumulate and transform closures is that they rely on Swift's general-purpose optimizer, whose inlining heuristics are not necessarily tuned for your exact use case :-). It can also be foiled by such pesky real-world concerns as separate compilation.

It's still early, but we're hoping to leverage static compilation and/or staged compilation techniques for the parser library, inspired somewhat by work done in Scala. @rxwei will be exploring this more deeply.

@Karl

This looks really great. The biggest issue I see is that result-builders don't allow you to control type resolution. Adding types like "Group", "Newline", or "Repeating" to the top-level standard library seems problematic. The topic has come up several times before, though, so there is certainly interest in the community.

@1-877-547-7272

Also, does this imply we’re taking Group out of SwiftUI and putting it into the standard library? I think it’s a good idea, but would the ABI support it?

I'm hoping we can extend result builders by allowing conformers to provide a type to serve as a namespaces for lookup, similar to custom string interpolation.

That would also open the door to defining and using custom operators (e.g. postfix +) inside of a result builder without bloating their global overload set.

@Karl

Is it possible for the compiler to disambiguate the result-builder from the regular contains(where:) function we have today?

We'll definitely have to figure out trailing closure ambiguity here. This seems like an issue that will keep coming up with broader application of result builders.

There's also more potential ambiguity with collection algorithms. For example, str.contains("A") will currently resolve "A" as a Character because there's only the Element-taking variant. But if there's an overload for a collection-with-the-same-element, it would prefer String for a literal. And, we're showing the use of literals inside a result builder to represent a literal subpattern. Semantically they would all be equivalent, but we like code to keep calling the functions they think they're calling :-).

We'll have to tackle these problems as we deploy the collection algorithms. For the consumers/searchers prototype way back when, I fell back to using argument labels to differentiate, but hopefully we can provide something cleaner here.

@timv is exploring these algorithms in more depth.

@Karl

Can we do this with RangeReplaceableCollection ? It has... certain quirks, you might say (little things, like invalidating all indices whenever you mutate the collection) that make this difficult to implement generically. I'd definitely be +1 to replacing RRC itself to remedy this.

If the matches are returned as slices and then processed in bulk, using them for replacement means quadratic performance due to excessive COWs. Replacing-as-you-go can be more efficient, but only if you can stop the collection removing excess capacity until all operations are finished. IMO, that would be a critical part of an RRC replacement.

I agree that RRC is basically broken for batch operations and wrote more about it here. A version of replaceSubrange that returns the newly created range can help in some cases, but would still be inefficient.

At the time I was hoping more work on ownership and generalized accessors would make the design pattern obvious. This is definitely a bridge that needs to be crossed.

@Jumhyn

We could always put these in some sort of Patterns module I suppose

@Lantua

Does this need to be in standard library? The result builder part feels like it could sit in a separate lib just fine.

We defintely want to ship runtime support as part of Swift. Whether you access API directly from the Swift default module or need an explicit import Pattern is still up for debate. I'm hoping that result builder namespaces makes this decision clearer.

@Patrick_Smith

... parser combinators ...

Yup, I'm a big fan of the programmer experience afforded by parser combinators and will defintely check out that work in Elm. As mentioned in the big picture, we also want to be able to leverage compiler technology to get around some of the performance issues with parser combinator libraries, especially since Swift supports separate compilation.