Allow capture and tryCapture to assign the captured value to a Reference, which can be used as a regex later in the scope.

Reference initialization creates a unique identifier. The compiler converts the identifier to an absolute backreference offset.

Example:

let regex = Regex {
  let a = Reference()
  let b = Reference()
  capture("abc", as: a)
  capture("def", as: b)
  a
  capture(b)
}

This is a first approximation of a CMake based build for this repository. The intent here is to localize the build rules for the repository to allow it to be consumed during the build of the toolchain. This allows the source list to be maintained in the repository as the source of truth rather than be explicitly listed in the swift repository.

For general purpose development, the SPM based build is recommended. Unless there is a specific need for the tests to be included, testing should be done via the SPM build.

This change is sufficient to build the content though does not perform the install or export steps which will be required to consume the results in the Swift build.

Example invocation:

cmake -B S:\b\16 ^
      -D CMAKE_BUILD_TYPE=Release ^
      -D ArgumentParser_DIR=S:\b\10\cmake\modules ^
      -G Ninja ^
      -S S:\SourceCache\swift-experimental-string-processing
cmake --build S:\b\16

• Track the whole match as an element of the "capture list" in the matching engine. Do so by emitting code as an implicit capture around the root node.
• No longer handle matcher as a special case within capture lowering, because the matcher can be arbitrarily nested within "output-forwarding" nodes, such as a changeMatchingOptions non-capturing group. Instead, make the bytecode emitter carry a result value so that a custom output can be propagated through any forwarding nodes.

  Regex {
    Capture(
      SemanticVersionParser()
        .ignoringCase()
        .matchingSemantics(.unicodeScalar)
    ) // This would not work previously.
  }
  

• Collapse DSLTree node transform into capture, because a transform can never be standalone (without a capture parent). This greatly simplifies capture lowering.
• Make the bytecode's capture transform use type (Input, _StoredCapture) -> Any so that it can transform any whole match, not just Substring. This means you can now transform any captured value, including a custom-consuming regex component's result!

  Regex {
    "version:"
    OneOrMore(.whitespace)
    Capture {
      SemanticVersionParser() // Regex<SemanticVersion>
    } transform: {
      // (SemanticVersion) -> SomethingElse
    }
  }
  

  The transforms of Capture and TryCapture are now generalized from taking Substring to taking generic parameter W (the whole match).

• Fix an issue where initial options were applied based solely on whether the bytecode had any instructions, failing examples such as ((?i:.)). It now checks whether the first matchable atom has been emitted.

For the regex literal syntax, we're looking at supporting a syntactic superset of:

• PCRE2, an "industry standard" of sorts, and a rough superset of Perl, Python, etc.

• Oniguruma, an internationalization-oriented engine with some modern features

• ICU, used by NSRegularExpression, a Unicode-focused engine

• Our interpretation of UTS#18's guidance, which is about semantics, but we can infer syntactic feature sets.

• TODO: .NET, which has delimiter-balancing and some interesting minor details on conditional patterns

These aren't all strictly compatible (e.g. a set operator in PCRE2 would just be a redundant statement of a set member). We can explore adding strict compatibility modes, but in general the syntactic superset is fairly straight-forward.

Status

The below are (roughly) implemented. There may be bugs, but we have some support and some testing coverage:

• Alternations a|b
• Capture groups e.g (x), (?:x), (?<name>x)
• Escaped character sequences e.g \n, \a
• Unicode scalars e.g \u{...}, \x{...}, \uHHHH
• Builtin character classes e.g ., \d, \w, \s
• Custom character classes [...], including binary operators &&, ~~, --
• Quantifiers x?, x+, x*, x{n,m}
• Anchors e.g \b, ^, $
• Quoted sequences \Q ... \E
• Comments (?#comment)
• Character properties \p{...}, [:...:]
• Named characters \N{...}, \N{U+hh}
• Lookahead and lookbehind e.g (?=), (?!), (*pla:), (?*...), (?<*...), (napla:...)
• Script runs e.g (*script_run:...), (*sr:...), (*atomic_script_run:...), (*asr:...)
• Octal sequences \ddd, \o{...}
• Backreferences e.g \1, \g2, \g{2}, \k<name>, \k'name', \g{name}, \k{name}, (?P=name)
• Matching options e.g (?m), (?-i), (?:si), (?^m)
• Sub-patterns e.g \g<n>, \g'n', (?R), (?1), (?&name), (?P>name)
• Conditional patterns e.g (?(R)...), (?(n)...), (?(<n>)...), (?('n')...), (?(condition)then|else)
• PCRE callouts e.g (?C2), (?C"text")
• PCRE backtracking directives e.g (*ACCEPT), (*SKIP:NAME)
• [.NET] Balancing group definitions (?<name1-name2>...)
• [Oniguruma] Recursion level for backreferences e.g \k<n+level>, (?(n+level))
• [Oniguruma] Extended callout syntax e.g (?{...}), (*name)
  • NOTE: In Perl, (?{...}) has in-line code in it, we could consider the same (for now, we just parse an arbitrary string)
• [Oniguruma] Absent functions e.g (?~absent)
• PCRE global matching options e.g (*LIMIT_MATCH=d), (*LF)
• Extended-mode (?x)/(?xx) syntax allowing for non-semantic whitespace and end-of-line comments abc # comment

Experimental syntax

Additionally, we have (even more experimental) support for some syntactic conveniences, if specified. Note that each of these (except perhaps ranges) may introduce a syntactic incompatibility with existing traditional-syntax regexes. Thus, they are mostly illustrative, showing what happens and where we go as we slide down this "slippery slope".

• Non-semantic whitespace: /a b c/ === /abc/
• Modern quotes: /"a.b"/ === /\Qa.b\E/
• Swift style ranges: /a{2..<10} b{...3}/ === /a{2,9}b{0,3}/
• Non-captures: /a (_: b) c/ === /a(?:b)c/

TBD:

• Modern named captures: /a (name: b) c/ === /a(?<name>b)c/
• Modern comments using /* comment */ or // commentinstead of(?#. comment)`
• Multi-line expressions
  • Line-terminating comments as // comment
• Full Swift-lexed comments, string literals as quotes (includes raw and interpolation), etc.
  • Makes sense to add as we suck actual literal lexing through our wormhole in the compiler

Swift's syntactic additions

• Options for selecting a semantic level
  • X: grapheme cluster semantics
  • O: Unicode scalar semantics
  • b: byte semantics

Source location tracking

Implemented:

• Location of | in alternation
• Location of - in [a-f]

TBD:

• TODO: @hamishknight, can you start tracking some of this here?

Integration with the Swift compiler

Initial parser support landed in https://github.com/apple/swift/pull/40595, using the delimiters '/.../', which are lexed in-package.

Adds

• Loading results from a file
• Measuring compile times (via a spi function in Regex)
• Comparing compile times and against NSRegularExpression
• Saving comparison results as csv
• Charts (based on #585)

Previously we would allow consuming a single scalar of a grapheme in grapheme semantic mode when matching a DSL .scalar. Change this behavior such that it is treated the same as a character with a single scalar. That is:

• In grapheme mode it must match an entire grapheme.
• In scalar semantic mode, it may match a single scalar.

Additionally, start converting AST .scalar atoms into .scalar DSL atoms. This is both for consistency with the DSL, and allows us to preserve the \u{...} syntax in more cases when a DSL conversion is performed.

Resolves #563 Resolves #564 rdar://96662651

This patch replaces O(2^arity) overloads of buildBlock with O(arity^2) overloads of buildBlock(combining:into:) with the language feature implemented in apple/swift#40799. This improves library compilation time, and fixes an issue where nested captures did not have a flattened type. Before this patch, fixing this would need O(arity!) overloads. This also allows us to switch back to native tuples for Match.

Also, rename renderAsPattern to renderAsBuilderDSL to work around a CI stale file issue.

This depends on swift-DEVELOPMENT-SNAPSHOT-2022-02-03 or later.

• Emit matchScalar instructions when emitting ascii quoted literals, ascii characters, and any scalar, as well as when in unicode scalars mode. matchScalar stores the scalar value inline instead of in a register like the character for match, making it faster and less susceptible to ARC
• Add matchScalarBitset to use the optimization from https://github.com/apple/swift-experimental-string-processing/pull/511 when in unicode scalars mode

Future work: We currently on match on ASCII because we may be given non normalized strings. Two options to deal with this are to A. normalize inputs B. compile two different programs, one optimized for if the input string is normalized and the other not making any assumptions

Large wins in the DNA benchmarks from https://github.com/apple/swift-experimental-string-processing/pull/515 since they have long quoted literal sequences in their patterns

=== Improvements =====================================================================
- DnaEndsMatchAll                         200ms	288ms	-88.8ms		-30.8%
- DnaMatchAll                             112ms	158ms	-45.9ms		-29.0%
- DnaEndsMatchFirst                       38.2ms	55.3ms	-17.1ms		-30.9%
- LiteralSearchAll                        70.6ms	85.4ms	-14.8ms		-17.3%
- EmailRFCNoMatchesAll                    98.3ms	108ms	-9.45ms		-8.8%
- EmailRFCAll                             42.2ms	51.2ms	-8.98ms		-17.5%
- DnaMatchFirst                           19.5ms	27.9ms	-8.38ms		-30.0%
- EmailLookaheadAll                       74.9ms	82.5ms	-7.63ms		-9.2%
- EmailLookaheadNoMatchesAll              53.8ms	60.5ms	-6.74ms		-11.1%
- ReluctantQuantWithTerminalWhole         8.6ms	10.5ms	-1.87ms		-17.9%
- HtmlAll                                 11.5ms	13.4ms	-1.85ms		-13.8%
- HangulSyllableAll                       6.69ms	8.25ms	-1.56ms		-18.9%
- TaggedEmojisAll                         16.6ms	18.1ms	-1.5ms		-8.3%
- InvertedCCC                             27.8ms	29.1ms	-1.35ms		-4.6%
- CaseInsensitiveCCC                      11.1ms	12ms	-933µs		-7.8%
- HangulSyllableFirst                     3.1ms	3.99ms	-891µs		-22.3%
- CssAll                                  4.05ms	4.85ms	-794µs		-16.4%
- BasicRangeCCC                           10.4ms	11.2ms	-785µs		-7.0%
- BasicCCC                                9.68ms	10.4ms	-742µs		-7.1%
- NotFoundAll                             6.41ms	7.06ms	-654µs		-9.3%

This implements these meta characters as per the Unicode proposal. We still need to expand how we treat \n. It should have mostly the same behavior as \v, but I also want to make sure that /\r\n/ will match an "\r\n" character.

• Adds matchBuiltin to match builtins instead of a consumeFn calling _CharacterClassModel.matches in most cases
• Removes AssertionFunction and changes assertBy to match in Processor instead

There are some gains (10% in microbenchmarks on builtin character classes) but the main purpose is to set up for future work

Future work:

• The layout of the payloads for matchBuiltin and assertBy will be optimized (hopefully soon) along with the rest of the instruction layout. Changes made in this branch and the scalar optimization branch showed that this is a strong next step
• I wasn't able to fully nuke _CharacterClassModel.matches but I think we're getting very close to being able to rip out most of it and the consumer interface for CustomCharacterClass

This prepares for adopting an opaque result type for matches(of:). The old, CollectionConsumer-based model moves index-by-index, and isn't aware of the regex's semantic level, which results in inaccurate results for regexes that match at a mid-character index.

The lazy range collection had the same issue, so this includes a wrapper for the new RegexMatchesCollection that just returns ranges, and modifies the replace/replacing methods to operate over a collection of ranges instead of a collection searcher.

macOS X 13.1 (22C65) Xcode Version 14.1 (14B47b)

The following code that uses a Regex Builder will crash at runtime when the user tries to get the result of an optional capture group via the regex match subscript. The same regex using a regex literal successfully returns an optional (but nil) value. You can generate the result builder from the literal if needed.

import Foundation
import RegexBuilder

// Case 1 - using regex literals. Works

let regex1 = #/\s*(?<label>\w+:)?/#

guard let match1 = "NOP".firstMatch(of: regex1) else {
    fatalError()
}
print(match1.output.label) // Should be nil. Is nil!

// #######################

// Case 2 - using regex builder. Crashes.

let label = Reference(Substring.self)
let regex2 = Regex {
    ZeroOrMore(.whitespace)
    Optionally {
        Capture(as: label) {
            Regex {
                OneOrMore(.word)
                ":"
            }
        }
    }
}

guard let match2 = "NOP".firstMatch(of: regex2) else {
    fatalError()
}
print(match2[label])  // Should be nil. Crashes with "Could not cast value of type 'Swift.Optional<Swift.Substring>' (0x....) to 'Swift.Substring' (0x....)."

I know that the optimization work is yet to come, but I'm wondering if this could be caused by something else. I have two versions of RegexRedux and, on my M1, processing the full 50 MB text file takes roughly 9 seconds with NSRegularExpression and over 3 minutes with StringProcessing:

import Foundation

extension String {
  func countMatches(of pattern: String) -> Int {
    let regex = try! NSRegularExpression(pattern: pattern)
    let range = NSRange(location: 0, length: self.count)
    return regex.numberOfMatches(in: self, range: range)
  }
}

let input = String(data: FileHandle.standardInput.readDataToEndOfFile(), encoding: .utf8)!

let sequence = input.replacingOccurrences(of: #">[^\n]*\n|\n"#, with: "", options: .regularExpression)

let resultLength = Task.detached { 
    [
      (regex: "tHa[Nt]",            replacement: "<4>"),
      (regex: "aND|caN|Ha[DS]|WaS", replacement: "<3>"),
      (regex: "a[NSt]|BY",          replacement: "<2>"),
      (regex: "<[^>]*>",            replacement: "|"),
      (regex: "\\|[^|][^|]*\\|",    replacement: "-")
    ].reduce(sequence) { buffer, iub in
      return buffer.replacingOccurrences(of: iub.regex, with: iub.replacement, options: .regularExpression)
    }.count
}

let variants = [
  "agggtaaa|tttaccct",
  "[cgt]gggtaaa|tttaccc[acg]",
  "a[act]ggtaaa|tttacc[agt]t",
  "ag[act]gtaaa|tttac[agt]ct",
  "agg[act]taaa|ttta[agt]cct",
  "aggg[acg]aaa|ttt[cgt]ccct",
  "agggt[cgt]aa|tt[acg]accct",
  "agggta[cgt]a|t[acg]taccct",
  "agggtaa[cgt]|[acg]ttaccct"
]

await withTaskGroup(of: (variant: String, count: Int).self) { group in
  for variant in variants {
    group.addTask { (variant, sequence.countMatches(of: variant)) }
  }

  let counts = await group.reduce(into: [:]) { $0[$1.variant] = $1.count }

  for variant in variants  {
    print(variant, counts[variant] ?? 0)
  }    
}

print("", input.count, sequence.count, await resultLength.value, separator: "\n")

Except for the countMatches extension on String, I've tried to keep both programs roughly the same.

import Foundation

let input = String(data: FileHandle.standardInput.readDataToEndOfFile(), encoding: .utf8)!

let sequence = input.replacing(try! Regex(">[^\n]*\n|\n"), with: "")

let resultLength = Task.detached { 
    [
      (regex: "tHa[Nt]",            replacement: "<4>"),
      (regex: "aND|caN|Ha[DS]|WaS", replacement: "<3>"),
      (regex: "a[NSt]|BY",          replacement: "<2>"),
      (regex: "<[^>]*>",            replacement: "|"),
      (regex: "\\|[^|][^|]*\\|",    replacement: "-")
    ].reduce(sequence) { buffer, iub in
      return buffer.replacing(try! Regex(iub.regex), with: iub.replacement) 
    }.count
}

let variants = [
  "agggtaaa|tttaccct",
  "[cgt]gggtaaa|tttaccc[acg]",
  "a[act]ggtaaa|tttacc[agt]t",
  "ag[act]gtaaa|tttac[agt]ct",
  "agg[act]taaa|ttta[agt]cct",
  "aggg[acg]aaa|ttt[cgt]ccct",
  "agggt[cgt]aa|tt[acg]accct",
  "agggta[cgt]a|t[acg]taccct",
  "agggtaa[cgt]|[acg]ttaccct"
]

await withTaskGroup(of: (variant: String, count: Int).self) { group in
  for variant in variants {
    group.addTask { (variant, sequence.matches(of: try! Regex(variant)).count) }
  }

  let counts = await group.reduce(into: [:]) { $0[$1.variant] = $1.count }

  for variant in variants  {
    print(variant, counts[variant] ?? 0)
  }  
}

print("", input.count, sequence.count, await resultLength.value, separator: "\n")

Hopefully I'm using the right compiler flags:

swiftc RegexRedux.swift -Ounchecked -o RegexRedux
./RegexRedux 0 < input.txt

Thanks for all your hard work on this project.

In Xcode 14.1 beta 3, this regex

#/(.*?)/#

Expands to this regex builder

Regex {
  Capture {
    ZeroOrMore(.reluctant, .any)
  }
}

Which fails to type check because ZeroOrMore takes the component first and the behavior second when not passed a trailing closure that produces a component.

Let capture information escape atomic groups and lookarounds: rdar://98738984 Correctly clear the dummy save point in possessive quantification: rdar://98852151

I thought this would be relatively easy to implement and I was curious what the performance benefits were so I implemented it quickly

A number of regressions in benchmarks without any code that hits any of the changes (most of these don't even have a custom character class). Most likely due to the instruction I added?

As expected EmailRFCNoMatches is much faster now that it's non-ascii CCC has it's ascii members collected into a bitset

The big benefit is being able to remove all the code in ConsumerInterface that did matching on things we already have instructions for (characters, scalars, case insensitive, etc)

Based on https://github.com/apple/swift-experimental-string-processing/pull/547

Comparing against benchmark result file before.json
=== Regressions ======================================================================
- EmailLookaheadAll                       88.6ms	85.8ms	2.84ms		3.3%
- DiceRollsInTextAll                      68.7ms	66ms	2.66ms		4.0%
- EmailLookaheadNoMatchesAll              63.2ms	61.1ms	2.09ms		3.4%
- BasicBuiltinCharacterClassAll           16.2ms	14.9ms	1.32ms		8.9%
- EmailLookaheadList                      24.5ms	23.4ms	1.04ms		4.4%
- EmailBuiltinCharacterClassAll           26.2ms	25.1ms	1.02ms		4.1%
- NumbersAll                              11.3ms	10.3ms	986µs		9.6%
- InvertedCCC                             29.6ms	28.9ms	668µs		2.3%
- WordsAll                                26.3ms	25.9ms	411µs		1.6%
- AnchoredNotFoundWhole                   9.73ms	9.41ms	328µs		3.5%
=== Improvements =====================================================================
- EmailRFCNoMatchesAll                    62.8ms	106ms	-43.1ms		-40.7%
- symDiffCCC                              19.4ms	40.7ms	-21.4ms		-52.5%
- IntersectionCCC                         12ms	16.2ms	-4.2ms		-26.0%
- SubtractionCCC                          11.7ms	15.7ms	-3.92ms		-25.0%
- EmailRFCAll                             48.5ms	50.6ms	-2.14ms		-4.2%
- EagarQuantWithTerminalWhole             7.75ms	8.41ms	-663µs		-7.9%