# Swift Regex: lookbehind

**URL:** <https://forums.swift.org/t/swift-regex-lookbehind/58477>\
**Category:** Discussion\
**Tags:** string, swift, regex\
**Created:** [June 25, 2022, 9:41pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477 "2022-06-25T21:41:52Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![cherrycoke](https://avatars.discourse-cdn.com/v4/letter/c/0ea827/32.png) [@cherrycoke](https://forums.swift.org/u/cherrycoke)\
**Post date:** [June 25, 2022, 9:41pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/1 "2022-06-25T21:41:52Z")

</div>

Notably missing from Swift's new regex features is a way to perform a lookbehind. Is this an intentional omission or something that will eventually arrive?

---

<div class="post-metadata">

**Author:** ![Michael\_Ilseman](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/michael_ilseman/32/44640_2.png) [@Michael\_Ilseman](https://forums.swift.org/u/Michael_Ilseman)\
**Post date:** [June 28, 2022, 4:30pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/2 "2022-06-28T16:30:28Z")

</div>

It is intended to be eventually supported. Can you share your use case? There's a lot of different kinds of lookbehind, and many engines do not support the fully general case as it can add extra algorithmic factors that aren't present with lookahead.

For example, there's lookbehind of fixed-length verbatim content, look-behind of an alternation of fixed-length verbatim content, and lookbehind of simple and reversible regexes. These can be supported with different levels of efficiency without really changing the regex's algorithmic complexity.

But, in the most general form, a look-behind regex component would need to attempt the regex from every starting position in the input prior to the current position. This is very different than a lookahead regex which only tries from the current position.

---

<div class="post-metadata">

**Author:** ![bjhomer](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/bjhomer/32/313_2.png) [@bjhomer](https://forums.swift.org/u/bjhomer)\
**Post date:** [December 1, 2022, 1:58am UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/3 "2022-12-01T01:58:45Z")

</div>

A place where I just wanted to use a lookbehind was in implementing a hashtag detector that follows the [Unicode specification for Hashtag Identifiers](https://www.unicode.org/reports/tr31/#hashtag_identifiers). (Who knew such a thing existed?!)

The spec includes the following:

> `<Hashtag-Identifier> := <Start> <Continue>* (<Medial> <Continue>+)*`
> 
> When parsing hashtags in flowing text, it is recommended that an extended Hashtag only be recognized **when there is no Continue character before a Start character**. For example, in “abc#def” there would be no hashtag, while there would be in “abc #def” or “abc.#def”.

One natural way to implement this would be with a negative lookbehind, verifying that there is not a `<Continue>` character before the `<Start>` character (which is generally `'#'`).

So, this would be a single character lookbehind.

---

<div class="post-metadata">

**Author:** ![Simulacrotron](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/simulacrotron/32/8947_2.png) [@Simulacrotron](https://forums.swift.org/u/Simulacrotron)\
**Post date:** [March 1, 2023, 3:31pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/4 "2023-03-01T15:31:12Z")

</div>

I have regex using strings and `NSRegularExpression` that I'm looking to convert to Regex Builder that requires LookBehinds and NegativeLookBehinds. As a simple example I'm trying to extract valid comparison operators. Without NegativeLookBehinds I can't filter out repeating occurrences e.g. `===`, `<<` or `>>=` should not match, but `==`, `=`, `<=` etc should.

This is always evaluated on short strings, so for me the performance argument doesn't have much weight. For any api there is potential for bad performance to creep in if you use it incorrectly. `NSRegularExpression` supports this, so it seems a bit arbitrary to exclude it.

---

<div class="post-metadata">

**Author:** ![rnantes](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/rnantes/32/5653_2.png) [@rnantes](https://forums.swift.org/u/rnantes)\
**Post date:** [March 1, 2023, 5:02pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/5 "2023-03-01T17:02:29Z")

</div>

+1 for look-behind support

---

<div class="post-metadata">

**Author:** ![rnantes](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/rnantes/32/5653_2.png) [@rnantes](https://forums.swift.org/u/rnantes)\
**Post date:** [March 10, 2023, 4:53am UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/6 "2023-03-10T04:53:45Z")

</div>

RegExp lookbehind assertions would be useful to me. Especially with [Safari support in iOS 16.4](https://developer.apple.com/documentation/safari-release-notes/safari-16_4-release-notes).

My use case is wanting to match on a full word (not just part of a word), so the proceeding character must be the start of the string, a whitespace or newline, or a period or comma. However, preferably I would not capture what proceeds the first word as this is not important to me.

```swift
// EX 1: Colder with a low of 5.
// EX 2: a low of 5 below zero.
// EX 3: high of 5. low of 6.
let lowRegex = /(?<=^|\s|\.|\,)low of (\d+|zero)( below zero)?/

```

Without the lookbehind assertion I would capture `low zero` in `below zero` from example 2 which was not what I was intending. Alternatively if I just decide to capture the first character then my matches would often be prefixed by a whitespace/newline or period/comma which I'd rather ignore, especially if I intend on replacing the match in the original string.

---

<div class="post-metadata">

**Author:** ![bbrk24](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/bbrk24/32/27370_2.png) [@bbrk24](https://forums.swift.org/u/bbrk24)\
**Post date:** [March 10, 2023, 5:30am UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/7 "2023-03-10T05:30:49Z")

</div>

Perhaps a more general version of this would be something like PCRE's `\K`:

> The escape sequence \K causes any previously matched characters not to be included in the final matched sequence. For example, the pattern:
> 
> ```swift
> foo\Kbar
> 
> ```
> 
> matches "foobar", but reports that it has matched "bar".

The documentation says that `\K` can be used to work around the fact that lookbehinds must be fixed-length. I wonder if `\K` and variable-length lookbehinds have different performance implications.

---

<div class="post-metadata">

**Author:** ![JacobHearst](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jacobhearst/32/31923_2.png) [@JacobHearst](https://forums.swift.org/u/JacobHearst)\
**Post date:** [April 20, 2024, 1:52pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/8 "2024-04-20T13:52:43Z")

</div>

Any update on this? Would there need to be a pitch to get this added to the stdlib?

---

<div class="post-metadata">

**Author:** ![Michael\_Ilseman](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/michael_ilseman/32/44640_2.png) [@Michael\_Ilseman](https://forums.swift.org/u/Michael_Ilseman)\
**Post date:** [April 21, 2024, 5:58pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/9 "2024-04-21T17:58:46Z")

</div>

Yes, it would need a pitch and then formal proposal.

---

<div class="post-metadata">

**Author:** ![JacobHearst](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jacobhearst/32/31923_2.png) [@JacobHearst](https://forums.swift.org/u/JacobHearst)\
**Post date:** [April 22, 2024, 1:00am UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/10 "2024-04-22T01:00:25Z")

</div>

I'd be interested in taking a look at this although after reading through the `_StringProcessing` target of [swift-experimental-string-processing](https://github.com/apple/swift-experimental-string-processing/) I have some serious doubts as to my ability to actually write an implementation.

Before reading through that target, my understanding was that Swift was using ICU under the hood as a regex engine which led me to believe that the stdlib Regex object was simply a facade in front of that library. My interpretation of the contents of `_StringProcessing.Processor` though is that this is not the case for the more modern version of Regex that was introduced in Swift 5.7. Instead, it seems like an entirely new regex engine was created and so adding support for lookbehinds will require writing new algorithms as opposed to simply calling some functions from ICU. Is that accurate?

---

<div class="post-metadata">

**Author:** ![JacobHearst](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jacobhearst/32/31923_2.png) [@JacobHearst](https://forums.swift.org/u/JacobHearst)\
**Post date:** [April 24, 2024, 5:01pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/11 "2024-04-24T17:01:41Z")

</div>

Spent some more time reading through the `Processor` and trying to understand the pipeline from the Regex DSL -\> bytecode -\> execution and I think I actually have enough of an understanding that I could at least attempt an implementation. I think it would be better to have look-behinds be more flexible rather than less in the long term but maybe for an initial implementation, fixed-length expressions would suffice? I suppose this is all discussion that could/should happen in the pitch but for the sake of discussion in this thread I did a quick survey of what other popular implementations support and here's what I found:

Fixed-length (ex: `abc`, `a|b|c` is allowed but `a+` and `a{1,2}` are not)

- [PCRE](https://www.pcre.org/current/doc/html/pcre2pattern.html#SEC20)
  - Allows top-level alternatives to have different lengths but not branches. ex: `(?<=bullock|donkey)` is allowed but `(?<=a(c|de))` is not

- [Python](https://docs.python.org/3/library/re.html)
- Ruby
  - Couldn't find docs from ruby so my source here is [regular-expressions.info](https://www.regular-expressions.info/refadv.html)

- PHP
  - Couldn't find docs from PHP so my source here is [regular-expressions.info](https://www.regular-expressions.info/refadv.html)

Unbounded variable length (ex: `[abc]+` or `[abc]{1,}` is allowed)

- [Javascript](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Regular_expressions/Lookbehind_assertion)

Bounded variable length (ex: `[abc]{1,3}` is allowed but `[abc]+` or `[abc]{1,}` are not)

- Java
  - Couldn't find docs from Java so my source here is [regular-expressions.info](https://www.regular-expressions.info/refadv.html) and [regex101](https://regex101.com)

- [Perl](https://perldoc.perl.org/perlre#(*positive_lookbehind:pattern))
  - Perl allows bounded variable length expressions between 1 and 255 characters as an experimental feature as of Perl 5.30.
  - 

> In Perl 5.35.10 the scope of the experimental nature of this construct has been reduced, and experimental warnings will only be produced when the construct contains capturing parenthesis.

---

<div class="post-metadata">

**Author:** ![paiv](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/paiv/32/4041_2.png) [@paiv](https://forums.swift.org/u/paiv)\
**Post date:** [April 24, 2024, 8:46pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/12 "2024-04-24T20:46:14Z")

</div>

- [Java class Pattern](https://docs.oracle.com/javase/8/docs/api/java/util/regex/Pattern.html)
- PHP is [PCRE2](https://www.pcre.org/current/doc/html/pcre2pattern.html)
- Ruby is [Oniguruma](https://oniguruma.org/oniguruma.c/en/md_docs_2en_2regex-syntax.html)

---

<div class="post-metadata">

**Author:** ![JacobHearst](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jacobhearst/32/31923_2.png) [@JacobHearst](https://forums.swift.org/u/JacobHearst)\
**Post date:** [April 27, 2024, 3:33pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/13 "2024-04-27T15:33:51Z")

</div>

@Michael_Ilseman I was reading through the [Implementation Musings](https://github.com/apple/swift-experimental-string-processing/blob/main/Documentation/ImplementationMusings.md#frontends) document and found myself uncertain about the state of `swift-experimental-string-processing`. Based on the repo's README and the fact that it's checked out as a part of setup for development of the swift toolchain itself I felt fairly confident that this library was shipping as part of the stdlib. However, after reading this paragraph from "Frontends", wanted to double check that conclusion.

> For string processing, this repo contains an example regex parser, compiler, and a few execution strategies. The regex parser itself serves as an example of writing parsers in Swift for simple languages. It hasn't (yet) been ported to run on the MatchingEngine, and doing so requires picking an execution strategy or strategies. It's AST can serve as the start of a simple result-builder API (tbd).

The result-builder frontend shipped in Swift 5.7 so can I assume that this document was simply written before then?

As a sidenote, I'm sure it's a non-trivial amount of work to do this but would it make sense to change the repo's name to remove the word `experimental` if this is in fact shipping with Swift?

---

<div class="post-metadata">

**Author:** ![scanon](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/scanon/32/2445_2.png) [@scanon](https://forums.swift.org/u/scanon)\
**Post date:** [April 27, 2024, 8:31pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/14 "2024-04-27T20:31:16Z")

</div>

> [@JacobHearst](#):
>
> The result-builder frontend shipped in Swift 5.7 so can I assume that this document was simply written before then?

That's right; the `_StringProcessing` module that's built by that package is part of the standard library (up to handwaving about exactly what exactly "standard library" means), and contains the execution engine for Regex and other string processing operations.

---

<div class="post-metadata">

**Author:** ![JacobHearst](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jacobhearst/32/31923_2.png) [@JacobHearst](https://forums.swift.org/u/JacobHearst)\
**Post date:** [April 29, 2024, 7:32pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/15 "2024-04-29T19:32:19Z")

</div>

EDIT: This has turned more into a log of my thoughts and learning process as I answer the questions in "Unanswered Questions". I plan to continue updating this post with the hope that others who are interested in this topic will find my musings useful.

Bytecode is pretty foreign to me so I wanted to write up my initial thoughts/implementation plans with two goals:

- Force myself to think more thoroughly about my design before actually starting the implementation. I often find that the simple act of writing things out accomplishes this.
- Get feedback/guidance from some of the original authors (if they have time)

# Trying to understand `emitPositiveLookahead`

I think there are some core similarities in execution pattern between lookaheads and lookbehinds. At a high level, they both need to:

1. Make a save state for successful matches
2. Make a save state to intercept failed matches
3. Start at some position  
a. For lookahead, this is just the current position  
b. For lookbehind, this is the start position of the input
4. Perform a non-consuming match
5. Did the match succeed?  
Yes: Go back to the original position and continue execution  
No: Go back to the original position and fail (lookbehinds will actually just go to the position after the last one it checked and repeat the above process until it reaches the current position)

Due to these similarities I thought it would be a good idea to try and get a working knowledge of how the bytecode for positive lookaheads is generated. I've copied `emitPositiveLookahead` below and annotated each line with my interpretation of what it does. Lines with three slashes (`///`) are my comments, all others were left by the authors.

```swift
mutating func emitPositiveLookahead(_ child: DSLTree.Node) throws {
  /*
    save(restoringAt: success)
    save(restoringAt: intercept)
    <sub-pattern> // failure restores at intercept
    clearThrough(intercept) // remove intercept and any leftovers from <sub-pattern>
   fail(preservingCaptures: true) // ->success
  intercept:
    clearSavePoint // remove success
    fail // propagate failure
  success:
    ...
  */
  /// If the lookahead match fails, it'll restore cpu state to the save point created with this address.
  let intercept = builder.makeAddress() 
  /// If the lookahead match succeeds, this will cause the first `fail` instruction created below to restore to the save point created with this address.
  let success = builder.makeAddress()

   /// Build a save point with the success address. Do this first because save points are treated as a stack and we want the intercept to be popped first
  builder.buildSave(success)
  /// Build a save point with the intercept address
  builder.buildSave(intercept) 
  /// Build the instructions for the expression in the lookahead
  try emitNode(child)
  /// Get rid of the intercept save point. If the lookahead failed, the cpu was restored to the intercept save point but now that the pattern has been evaluated, we can get rid of this save point.
  builder.buildClearThrough(intercept)
  /// Restore to the `success` save point but don't throw away any captures that happened
  builder.buildFail(preservingCaptures: true) // Lookahead succeeds here

  /// Store this index (after the `fail` instruction that's built above) as the position the `intercept` save point should restore to
  builder.label(intercept)
  /// Clear the success save point
  builder.buildClear()
  /// Fail the match
  builder.buildFail()

  /// Store this index (after the `fail` instruction that's built above) as the position the `success` save point should restore to
  builder.label(success)
}

```

# A simple design

I decided it would be best to start with the simplest implementation I can think of so I can build my understanding of the bytecode generation process and then work from there. With that in mind, here's the test case I want to be able to execute with this implementation:

- Given:
  - Pattern: `(?<=abc)def`
  - Input: `abcdef`

- Expect that:
  - `abc` is not consumed
  - `def` is consumed

Notably, the lookbehind pattern matches exactly the characters between the start of the string and the pattern we're actually matching on (`def`). This means the lookbehind will succeed on the first step and looping through more indices is not necessary.

```swift
// This snippet is just pseudocode following the pattern from `emitPositiveLookahead`

save(restoringAt: success)
save(restoringAt: intercept)
goToStart // This won't work if the lookbehind pattern's length is less than the distance from the start index to the current position.
<sub-pattern> // failure restores at intercept
clearThrough(intercept) // remove intercept and any leftovers from <sub-pattern>
fail(preservingCaptures: true) // ->success
intercept:
clearSavePoint // remove success
fail // propagate failure
success:
...

```

# Unanswered questions

_ **Questions that are rolling around my head, potential rambling ahead.** _

**Q:** Why is this function called `label`? To me, labeling something means assigning an object some identifier for later use but here it seems like it just tells the processor to continue to the next instruction.

```swift
// Resolves the address token to the next instruction (one past the most
// recently added one), updating prior and future address references.
mutating func label(_ t: AddressToken) {
  addressTokens[t.rawValue] =
    InstructionAddress(instructions.count)
}

```

**A:**  
`label` isn't telling the processor to go to the _next_ instruction, it's a GOTO that tells the cpu to just go to the instruction at the address you pass to `label`. `builder.makeAddress` essentially reserves space in the `MEProgram.Builder.addressTokens` array by appending `nil` and then the `label` function replaces the `nil` value with the end index of the `MEProgram.Builder.instructions` array. Because the save instructions are emitted with an `addressToken`, when the cpu builds a save state, it's able to restore to the instruction index stored in the `addressTokens` array at the `addressToken` index. This is a bit complicated to explain as text so I also put together a diagram mapping out this process [here](https://viewer.diagrams.net/?tags=%7B%7D&highlight=0000ff&edit=_blank&layers=1&nav=1&title=emitPositiveLookahead%20(drive).drawio#R7Z1db9u4EoZ%2FTYDsRQNR1Odlk21395z2oDhdYPdcKrYSa6tYgSyn6f76Q9mi%2FDGMxCSSZ7QZoEAjRXZs6SGHnHlf8kxe3T3%2BUib3i8%2FFPM3PXGf%2BeCZ%2FPnNdL4pD9V995sf2jBt68fbMbZnNt%2Bec3Ymv2d%2Fp9qTQZ9fZPF0157anqqLIq%2Bz%2B8OSsWC7TWXVwLinL4vvhZTdFPj84cZ%2Fcpgcfoz7xdZbkKbjsj2xeLbZnI3%2Fv6l%2FT7Hah%2F7Jwmt%2FcJfri5sRqkcyL73un5IczeVUWRbX96e7xKs3ru3d4Xz4%2B8dv2g5XpsrJ5wc3N73%2Bvnfz2j39l8t%2Fr6OPnv7zwnWiexqr6ob9xOlc3oDksympR3BbLJP%2BwO3tZFuvlPK3f1lFHu2s%2BFcW9OinUyb%2FSqvrRPM1kXRXq1KK6y5vfpo9Z9efez%2F%2Br3%2BrCb45%2BfmzeeXPwQx8sq%2FLHn%2FsHe6%2BqD3cv2xzp18Hb1Ny5VbEuZ2nXvfEb3pLyNq26Lgy2F9Z3bu9PNI%2Fhl7S4S9UnUheUaZ5U2cMhWklD6G173e4hqh%2Ba5%2FicZ9p87ockXzd%2F6rdlVmVJvnnQSZWCZ776nt3lybJ%2BuN8XWZV%2BvU82t%2Ba7atWHj%2B7J2%2FmQllX62Pn1m9%2B%2Bc73mNU2n8C5qmsj3XQuTkdyeW%2By1rjCKR7pnHrhlnz98KYvbMrm7uFxn%2BTwtL5L5vExXq9%2BLb%2Bly1XULb4plpVtQjeBsod7gU%2FKjWNffQz2B2Td9dLkoyuxvdX2ib7D6dVk1LUc6B1d8rV%2FZvKf6JOqaL%2Fo5iKNTn5PHgws%2FJatKf5oiz5P7VXa9%2BXz1C%2B8U4Nnysqiq4q656NkUdJNozUYQX%2FgHbHgSoOF6HkQjcMYiA6JxVdzdZ7ki4vJHlV6pmPdLury4S76lX4pVVrdv1RF%2BSxZpMj9rO38GZVhQZHQEinR82Ik4wQlJEV5g0Ytky1VVrmdVVnAnMhIbvnvEhtDDnP1eJIwgG8IfD44QwHGdqjt2ldxX6xKGZPVdq82TLFW8uSryolTnl8WWjSzPj04leXa7VId5elO%2FrL5ZmRrFvm9O32Xz%2BWbstlKPI1veftpc9rO3O%2FPf5i7Upwr18pt8M1hdqBem6h0u74tsWW3uin%2Bp%2Fqn7dFUPvnz1Wa%2FUsdgdq3%2F15WV1VdSsJ9nm8aYKnu9pDZAaP6pBSHLdoj0QJ23z6wel7TPssJDjUREBKtTEYbaoZyBJyVAgQBHgQxEzFMSgiNGh0JGJoSADhXCxqZASQAFIOEE%2BB95i6xxLc9N7cyxu0ydSybHAof6ZG%2BQ1nvf1YC64rX%2FM1VdSb7SsUnUX7uufN5c6181coJ4zvt9mFc5%2F0q9Xn2fvLbqmCOOnalz9PelkajThnKoZtvuz7%2F2emmVJ%2F8KFc3BjhzjaHNyFHeIyyzk6vhaPttVNZ24lTVMrc47uZr2c1YDMivvO3Dj3FsP1Fm7k4XcXEs60dtFavle%2Feb8XSdr4DZO63KE8k6C2dU6nQxG%2BALRwfpdCXyKEZUcyYn7Xh%2BNSzu8OWwewn77Q6TLgeJSzNrhQ4Od3fVhSZihwoSCQ34WqHYYCFwr8%2FK6hpwAkkM7v6rRtb37Xo6Whc%2BHE8Mn87mo9m6kp4vSyu4FmmU52V8IqF2d3B0jfxc9lA2Z3Q7u%2BMB4tVwNn35zaHSIT41izQWVaJWFYZBRQUMCfTDkmsQyn%2BcmEDRFeCIOG%2B6ShQwg4rOA8%2F2mmXY49Q1TCixBwqKEH%2BU%2FDIhgWBFjwA5APhd1cFaIQeoTJO3TqqhAUIXBVaNi0XmgNCpn44ncKvM%2BTn5gLBC7wQ0kAh6n7XFwzFxhc4NeGAjge3edixlxgcIFfHgqmLv%2F3bOX%2FujpKpDxkcPoaykO6ELT5%2F2vykJ43s0iS1SA1%2BQoPxs8EykEG0yyXg17f2T3D6vTU5MqzVNyNltMzOGe5BjAEG9ObTxn8sowCCgr4UygHRmYuB9EJGzKQF9iRQzhwVMHVoBMl%2BCe4RocDRxpcDaIJC378CWxWkuNq0OkjTyuw7q0GRePBATXeXA0a1kvmWYNCJr4EpiErV4OQuSAQSuAwlatB6FwQqAZ1rhnH1SAcLvCrQSKAebBVXXUQTAQKET42ETIMwJPvrwfO1uXDphy4mQugrvUuzp611vshzvP0Jllvymwa31lap3m6AK5nXB%2BTuyyv3%2FLXNH9I6%2Bv0VGz7HYVojuEfypPrNL9Uk6vbzX2DF6TL%2Bft6V4L6w%2BTJapXNnj8JslhUzdp1R2tVtdAFHdgL%2BEWsZ%2Fu2Wwbo3oTIjTeYj63q2W3alGZF23fJGRx9mzXCuaL93PDsv36RcA%2Fb4GgQknMZcwg2pldzMMjGGQUUFPDTQI5pCSGuaJMJG3qMgVjPhjUnrmefqEQprQGiEluEAwf7XM%2BmCQt%2B9AltFmThevbp444ILevZ7VaaI8ABfSlczx60y2ib34TiiyGLx%2FVsdC4IhJLOtVC5no3DBX49O%2BxcDpXr2ThcEKhnh4aJCtez8YhAr2eLEFZPNkQ4TAQKEYZ62qkVDiF48qxw6AKYssJBT4v7FQ6hbaFdV1KIFNqlbh3M69vi1Xqhg3BoXjcvVV8x%2BbF3QRONdu%2F8pT6xSzdJvbREu%2Fqvs89%2B7%2FWxe9RUth9g13Dab%2FLythSbRCvPbluIaiEtAuqFIqKlFjJ4nLZ%2FPr3Lqv8U8%2FR8k9iFY7LTqn9izztgkoD6x2AAYvXP64euz9Dmkl3PwuACYsnHEGzYl1qoZNANxh9GAQUF%2FKS5Vmmw%2Bodk2PD1Up6I6h9YhGX1z4kEHROszjqwOsvqH5qw4EefkNc2pxl3RCxs2RgPDl7bfOyKzPTW4hMhr21OkAv8UBKZJjKs%2FkHmAl%2F9E%2FHa5gS5IKD%2BiQwTFVb%2F4BGBr%2F6JoICU1T%2BIRKCrf0TULR01lCAZjPHBaB0niGDAQus%2BGCmDgQKGhw9G92KLNwwGChghNhhS5y1YmPcPEObpDGu%2FME%2FPMvpXbBpcmPc6XvXgi3l9W7xKW16DoXl9oZD0aAOIJgA%2FLSQ9vD52jprKCEJSV5i283p240JUkka2SlIR09LDGyZwB6vMXeVpUv6%2BULf2dnGw2tzTZcbxlaUKUucAUgLKUsOEh5Wlrx%2FLRgMoSwO7oe1oCiHDlKdd3FEv1LjRF%2B5WcHxy%2FUaeDD0XoOnJTyMo%2BmBe6PKCXtqNTOvRs0SVSvwJBPbCpnrQwwrVk%2FcmkTU%2BVKKPppD1qdRRQQ88wjBSYXkqhZjjOpaTHjkiHCxPHbnOE01QnmoYi7A8FZ0L%2FFBiGHawPBWdC3x5qvZZsDyVEhcE5KnNCicsTyVCBL48NWZ5Kiki8OWpMctTCYJBQJ5qWLqK5an4YODLU2OWp1IEA12eKuKni7Lz7EHXX2f7chlnf1PGvYsYIZTMFzZCMoJVElaMdgFMWTEaWStG9US1f5VJagpnl3l9i7zaKpwjKgrnpt1ovV9TjX5a4Xx4fSyOmsoICmfhwWyVHhwshB4Y1Mu3GlU7igM3SO7qYLm8Xt1vnno7sti9Hr6j%2BnVyPTs%2Fkx%2B3IP1Uf0%2FzS81jkr22aN8OTEH%2BsCuA0D5bBPwuFOLgObp6f5t9EbD0YYTXwuDBe0zXsLn0C7pQRB17K0%2FvbfyupBWt2k%2F%2BlJL9Y5Ll5%2FdlukrLBzUGbqrQjailKteGOf9pRe1hdMgzAVG7iGG1llXtA8xfYnuxD9nt0l3D0qisUz7ZFLhtmtMRf7iGpVKZGMLEoMtCXMNqqaxtJxSFAoG9%2B7rrwLIvq9tP0qPsWueUYhCsCbO%2BnSYsBMKPjauXBe4Igcd1LOc%2FrVd8BDpguocV7sP2GdNz77ZgssKdEhcEYonJpssKd2Qu0BXurtPtiGGFOwoX%2BAr3VibJCncaRKAr3F0B86escEckAl3hrrqpzuDBCncUMPAV7q6AWVFWuOODga5wd0W3J4YV7jhgoCvc1fgGgMEK9wkhhK9wdwVMfd3UsiuzvIqhOAEU6PnQVrLGMvJ%2FgIy8Ld30SknbMXC%2FlFSXV4lISWWrlWdi3xaxwppYZ2hiX2h9aCqQrfXB3ae%2F9%2FrYPWosYyzubtjD%2BAXNC1EU30rd%2B7nwaa3u3n5ygyh%2B0%2BjILOkuW3kIHfW7%2Bnvg7rH6fYBhrLR379JVv0tYttPxg%2Bc4r4Fjekvmtlk91rVPgxh8MYhnWtaOde1k4gsBXbvBMsy69tP0KJ79%2BJVODDKsfse6dpKwEAg%2FsAjIunYSgaddaApR1%2B7BSiDr2oftM%2ByX%2BKcTYLqXxmNdOwoXBGJJt9%2BBde0oXODr2r1uvwPr2lG4IKBr92DmlHXtiETg69p9mD9lXTsiEfi6dr972w%2FWtaOAQUDX7sOsKOva8cHA17X73YYH1rXjgIGva%2FdhrpN17RNCiICu3YcJUda140KBng%2BVeqd4Vgn%2FA1TCbemmXw2q0xf9alA9KCKiBpV6wXYm9m0Rq9MrFot6x0MTO4iuXR4K1Uno2qVhf2v1PH9T7eORhwQUSum%2Bb1tKH2%2BMEAIUsHpc3a3a9LgT7TnbQNHGArtAMXyPK23HCG0vMnCPa%2BgiL2QQea5wfDeQIgiP2koYXjS%2F8sMo1rU7%2Ff7b79G85VGjGMIjZNhn4AUNB9MjpJ0%2F%2FTE2HDzGvnJy27NxxlWdGTnH9gcFrjwAloI%2FyOfdMUaR0fn2gn66%2FqAA1jTZHzQEHBPc9yLgfS8mRQy%2BqC4wlTnZH0QmvhDwBwW87wVWj9K2zinFIN73YiqwEAg%2FvO%2FFcwKP%2FrKfsmV6dOojbBMnDFP2bqIR4xTvkjF2DzPBXTIC3iWDIBcEIg%2FvkkGQC3w3UcC7ZBDkgoCbKIR5VnYTIRKB7yYKeZcMUkTgu4lCUzaV3UTIYBBwE4W8SwZFMPDdRCHvkkERDHw3Uci7ZEwaIQJuohAmRNlNhAsFfj40hHmvTSfCPGDwgJ4HlVq1SEA5zl6d6uyVXh1dyuvXEesRTr%2BOWIvKiOiI2woiE%2FvGiLXeNUX3qujussMieb%2B77PD6k7jLYii9mYJz6KUWHG5NR23EwkdCa68Z6cIk6wsQxvTwaGdOv2uL2I5l7Sd%2FysPzManV5UcP46QGHs%2FRizwQMvBEsHbIBp4BZlwtjlM28ESwjMgGngHgaBvdhNRqkSm2sYGHLDHo%2BRs3MlUW2cBDJr4QMPBEsMbIBp4T9SjSGiA6MQhWHtnAQxMWAuEH1hjZwEMi8AgtRuuDw3PHo8OwLTBbcgbtMwJrUOgEmG7rBVtyULggEEu6rRdsyUHhAt%2BSE8PsKVty0LkgYMmJYeaULTmIROBbcmKYP2VLDiIR%2BJacuNt5wZYcFDAIWHLibucFK6RxwMC35MQw%2F8mWHHww8C05Mcx1siVnQggRsOTEMCHKlhxcKPDzoTFbcgjxgJ4Hbbup407iJslX3EvgUIGeBdXmAQpCfba9VGevFOrrAm%2B%2FWFwnOfuF%2Blo8SEQsLnXqhYl9Y8S61sQObm94oVHraBuwZtFIUtuA6XwVgdbERq0TtqbIuv%2BPiRm1DIs7vwBhRKNWa7%2FqN2pp0xGVe%2B%2FA0qg2am3APm8kncjbLXnekeeVgFtLOrCIyG6t10%2B7dkxO2K0lHVhPZLfWEHC41nBQETJKB5YQBZzzMAvjs0AgaWeqGrIPCy1yHM7QAh%2FbhSUdWD1kF9aJ%2BpPp7VshHVgpZBcWTVgIBB9YQWQXFokJCwEXlnQMi7awC2tQUOx30CITYASsMrMLC50L%2FFgiYOaQXVjoXODrDwTMirILC50LfBeWFDAjyi4sRCLQXVhSGLYAZhcWHhHoLiwpuj0V7MJCAQPfhSUFzIqyCwsfDHQXlhTd%2B%2FayCwsHDHQXlhQw18kurAkhhO%2FCkgImRNmFhQsFfj7UhflQdmGh8YCfB3VhHpRdWMhU4GdB9eIABFT47Gmpzl6nwm8LvP1KcJ3ktNiyg5gSXK9awMS%2BMWI9a2Ll0MS%2B0IXVfA5rF9bh9adxYcG0hHqev6n28chDAgqCG1%2B7DxHHCBFAgZ16b6DHdax7XN2LkBkj0NkElok9JbHWo1qdHUEeI%2BjkrzHk913te%2BFRUxljhODB4veH5XzTuJIqVf%2BfZ8tZvp6rgK0Oivu0TBpJrpPc1Nipm3yXVcA4gu3UjKJDSwUFp6YHy8rs1BxgHNYy%2FAqnpm83DBvPcOPB0jI7NYeAY4JuGg9O29ipicICfmLfM20%2Fwk5NMpEjCCV66IAFYvZqnqhHmaCVxoelY%2FZq0oQFP%2Fz4sK7MXk0SgUfYitu8aDw6XEAHezUHBcW3T33QCTDdm5iwVxOFCwKxpHsPE%2FZqonCBr1Lyu%2B027NVE4YKAV9OHOVH2aiISge%2FV9A3rDLFXE48IfK%2Bmb8qPslcTGQwCXk2%2Fe39mFsXjgIHv1Qxg%2FpO9mvhg4Hs1A5jrZK%2FmhBAi4NUMYEKUvZq4UODnQwOYD2WvJhoP%2BHnQAOZB2auJTAV%2BFjSAya50OedKGh4UHn4GNID5rmS20fUwEAhAoCdAPYNqi%2F2xXQCT9r5oGUi%2F90WXQiz29qLl1vIM0jEm9i0QG1oTGwxN7Asd3YcCK338tKP78PpmCDmqX8vTmw0RaE3sfTxha%2FKsW1MweGt6Zf9PZ19lJvaUxFqPWAIaK3rodfaM3Xnf1b7nn72i91eHZVFU%2B5erec3iczFP6yv%2BDw%3D%3D).

**Q:** Why is a failure emitted after clearing the `success` save point? `signalFailure` sets the processor's state to `fail` if there aren't any other save points so wouldn't this fail the entire match? Even if it doesn't fail the entire match, the captures aren't being preserved so how does this not throw away all the captures that have happened up to this point?

```swift
mutating func signalFailure(preservingCaptures: Bool = false) {
  guard !savePoints.isEmpty else {
    state = .fail
    return
  }
  //...
  if !preservingCaptures {
    // Reset all capture information
    storedCaptures = capEnds
  }
}

```

**A:**

- The failure is emitted so that if the intercept save point is the one restored (caused by the lookahead match failing), it restores to that failure and ends the capture. When the `fail` that triggers the `success` save point to be restored is hit, it restores the instruction position to `endCapture`.
- `signalFailures` doesn't throw away the already stored captures, it sets `storedCaptures` to the stored captures contained in the save point that's being restored.

**Q:** How can I represent iterating through each index from the start to the current position in bytecode without a ton of duplicate instructions? At time of bytecode generation I don't know the length of the input string so I guess it has to be relative? Maybe something like this?

```swift
start = input.startIndex
goto start
<execute the match>
if success:
  exit
else:
  start += 1
  goto start

```

Not entirely sure how that translates into opcodes though.

**A:**  
_TODO_

---

<div class="post-metadata">

**Author:** ![JacobHearst](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jacobhearst/32/31923_2.png) [@JacobHearst](https://forums.swift.org/u/JacobHearst)\
**Post date:** [May 6, 2024, 3:40pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/16 "2024-05-06T15:40:14Z")

</div>

> [@JacobHearst](#):
>
> ```swift
> // This snippet is just pseudocode following the pattern from `emitPositiveLookahead`
> 
> save(restoringAt: success)
> save(restoringAt: intercept)
> goToStart // This won't work if the lookbehind pattern's length is less than the distance from the start index to the current position.
> <sub-pattern> // failure restores at intercept
> clearThrough(intercept) // remove intercept and any leftovers from <sub-pattern>
> fail(preservingCaptures: true) // ->success
> intercept:
> clearSavePoint // remove success
> fail // propagate failure
> success:
> ...
> 
> ```

I think this design actually doesn't make sense. Lookaheads want to continue execution at the current position because by the time a lookahead is being processed, we've already consumed the characters that are dependent on the lookahead matching.

Lookbehinds haven't consumed those characters though so creating a save point at the position of the lookbehind to restore to on success doesn't make sense. I think what actually needs to happen is that the lookbehind should restore at the end of the pattern that's immediately after it.

```swift
// Lookahead
abc(?=def)
   |-> create success save point here. If `def` are the next
   | characters, we want to continue matching the characters
   | that come after `abc`

// Lookbehind
(?<=abc)def
           |-> Create success save point here, if `abc` are the
           | preceding characters, we want to continue matching
           | the characters that come after `def`

```

Of course I'm not quite sure how to create a save point at a position that hasn't been reached yet...

---

<div class="post-metadata">

**Author:** ![Michael\_Ilseman](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/michael_ilseman/32/44640_2.png) [@Michael\_Ilseman](https://forums.swift.org/u/Michael_Ilseman)\
**Post date:** [May 6, 2024, 5:13pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/17 "2024-05-06T17:13:15Z")

</div>

Looking behind is fundamentally different than looking ahead, so you'll need to add new instructions to the engine.

For fixed-length lookbehinds, you'd want a move-back instruction to move the current position back. E.g. `(?<=abc)def` would move current position back 3 characters and then try matching. `(?<=abc|d|efghi)jkl` would emit an alternation, and in that alternation would be a move-back of 3, 1, and 5, respectively.

A straight-forward implementation of bounded variable length lookbehinds could be to go back the max amount, then subtract one and try again, etc. More efficient approaches are a little more involved, and might be better handled as compiler optimizations. E.g., `(?<=\d{1,3}-.{1,3}-\d{1,3})suffix` could split the lookbehind into different segments and match each one in reverse order. But, this can be nuanced when the bounded variable length segment's match can overlap with the segment before or after it (e.g. the `.{1,3}` in `-.{1,3}-` can also match `-`).

If all we are able design in a reasonable time frame is bounded variable length lookbehinds using this straight-forward implementation, that's still a massive improvement.

For fully variable length lookbehind, I'm not certain what a good implementation strategy would be. A naive approach could be to spin up a fully separate matching sub-process on the portion of the string already matched. That will require more additions to the engine. Those additions would be what would also support a `String.ends(with: RegexComponent)` API.

---

<div class="post-metadata">

**Author:** ![Michael\_Ilseman](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/michael_ilseman/32/44640_2.png) [@Michael\_Ilseman](https://forums.swift.org/u/Michael_Ilseman)\
**Post date:** [May 6, 2024, 5:31pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/18 "2024-05-06T17:31:41Z")

</div>

Reading up a little more on Javascript:

```javascript
/(?<=([ab]+)([bc]+))$/.exec("abc"); // ['', 'a', 'bc']
// Not ['', 'ab', 'c']

```

This means that they do a reverse match from the end of the prefix. This is far simpler semantically (and more efficient) than the alternative. We could probably support this by adding match-back, etc., variant instructions.

---

<div class="post-metadata">

**Author:** ![JacobHearst](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jacobhearst/32/31923_2.png) [@JacobHearst](https://forums.swift.org/u/JacobHearst)\
**Post date:** [June 10, 2024, 2:45pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/19 "2024-06-10T14:45:05Z")

</div>

As a quick update for anyone interested in this work, I was able to implement a flawed, but partially functioning solution for positive lookbehinds! You can check out all the changes at [this commit](https://github.com/apple/swift-experimental-string-processing/commit/1c59bbd94bdd0be83860e93ba07eae5d1b410879) but here's the core algorithm:

```swift
save(restoringAt: success)
save(restoringAt: intercept)
moveBack(<sub-pattern max length>
<sub-pattern> // failure restores at intercept
clearThrough(intercept) // remove intercept and any leftovers from <sub-pattern>
fail(preservingCaptures: true) // ->success
intercept:
clearSavePoint // remove success
fail // propagate failure
success:
...

```

As an example, this implementation is able to successfully find a match for `(?<=abc)def` in the string `zabcdefg`

Many thanks to @Michael_Ilseman for his guidance and help getting me to this point.

As I mentioned above however, this solution is quite flawed and has many cases that should work but don't. My next goal is to replace this solution with reverse matching which should enable unbounded variable-length assertions in lookbehinds as well as things like `String.ends(with: RegexComponent)`

---

<div class="post-metadata">

**Author:** ![JacobHearst](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jacobhearst/32/31923_2.png) [@JacobHearst](https://forums.swift.org/u/JacobHearst)\
**Post date:** [July 26, 2024, 1:42pm UTC](https://forums.swift.org/t/swift-regex-lookbehind/58477/20 "2024-07-26T13:42:41Z")

</div>

Pitch is now [up on the forums](https://forums.swift.org/t/pitch-regex-reverse-matching/73482)!

[Next page](https://forums.swift.org/t/swift-regex-lookbehind/58477.md?page=2)