Greedy and lazy quantifiers

Ask for the quoted fields of the row "Asha","Pune",411001 with ".*" and you get one match of 13 characters, "Asha","Pune", where you wanted two. The star in that pattern is greedy: it takes every character it can, so the match runs on to the last quote of the row. Add one question mark, ".*?", and the same row gives "Asha" and "Pune": lazy quantifiers take as little as they can.

Both searches are walked through below, one character at a time, followed by the case where lazy is still not shortest. Then .*? meets a negated class such as [^"]*, which says outright where a field ends and stays right on rows where the lazy pattern goes wrong. Last comes the ungreedy mode, (?U), which swaps the two forms in Go, PCRE2 and PHP and which JavaScript and Python refuse.

A greedy quantifier takes everything, then gives back

Every quantifier of the previous lesson, repetition with star, plus, question mark and braces, is greedy unless it says otherwise. A greedy quantifiergreedy quantifier: A quantifier in its usual form, such as * or {2,5}, which repeats its atom as many times as it can and gives repetitions back one at a time only when the rest of the pattern cannot match otherwise. repeats its atomatom: The single item a quantifier repeats, written right before it: one character, the dot, an escape, a character class or a group. In ab+ the atom is b; in (?:ab)+ it is the group ab. More in “Repetition with *, +, ? and {m,n}” as many times as it can, and only then lets the rest of the pattern try. When the rest fails, the engine does not leave that start position yet: it takes back one repetition and tries the rest again, and it goes on giving back until the rest matches or nothing is left to give. Going back to an earlier choice like this is backtrackingbacktracking: How a backtracking engine reacts to a failure: it returns to its most recent choice point, restores the text position it had there, and tries the next alternative. More in “How an engine finds a match, step by step”, the move that how an engine finds a match follows step by step. The ECMAScript specification fixes the order: a greedy repetition tries one more round of its atom first, and the rest of the pattern only when that round fails (ECMA-262, RepeatMatcher).

Here is what that means for ".*" on the row. Step through the search and watch the sub-label of .*, which says how many characters it holds:

The dot can match every character of the row, so .* first takes all 19 characters after the opening quote, and the closing quote finds nothing left. .* gives back the six digits and the comma one at a time, and the closing quote fails on each of them; the eighth character it gives back is the quote after Pune, and the closing quote matches it. The program below plays the engine’s part in the same order and then asks the real regex. Press Run, then Edit: add a third field such as ,"Goa" to the end of the row and run it again, and the match grows to the new last quote.

// How the greedy .* of ".*" finds where a quoted field ends. After the opening quote at position 0, .* takes the
// whole rest of the line, then gives back one character at a time until the closing quote can follow it. The loop
// plays the engine's part for this one pattern, in the order the ECMAScript specification gives; the last line asks
// the real regex.
const line = '"Asha","Pune",411001';

const rest = line.slice(1); // the characters .* may take after the opening quote
for (let take = rest.length; take >= 0; take--) {
  const next = rest[take];
  if (next === '"') {
    console.log(`.* holds ${take}, next is '"': the closing quote matches`);
    console.log(`gave back ${rest.length - take} characters; the match is ${line.slice(0, take + 2)}`);
    break;
  }
  console.log(`.* holds ${take}, next is ${next === undefined ? 'the end of the line' : `'${next}'`}: no quote`);
}

console.log('');
for (const match of line.matchAll(/".*"/g)) {
  console.log(`/".*"/g finds ${match[0]} at position ${match.index}`);
}

.* holds 19, next is the end of the line: no quote
.* holds 18, next is '1': no quote
.* holds 17, next is '0': no quote
.* holds 16, next is '0': no quote
.* holds 15, next is '1': no quote
.* holds 14, next is '1': no quote
.* holds 13, next is '4': no quote
.* holds 12, next is ',': no quote
.* holds 11, next is '"': the closing quote matches
gave back 8 characters; the match is "Asha","Pune"

/".*"/g finds "Asha","Pune" at position 0

Greedy does not mean careless: .* gave back exactly as much as the closing quote needed, not one character more. But it worked from the far end of the row, so it stopped at the last quote it could reach, and the comma between the two fields ended up inside the match.

A lazy quantifier takes as little as it can, then extends

Put a question mark after the quantifier and its preference turns round. A lazy quantifierlazy quantifier: A quantifier followed by a question mark, such as *? or {2,5}?, which repeats its atom as few times as it can and adds one repetition at a time only when the rest of the pattern cannot match otherwise. Also called non-greedy or reluctant. repeats its atom as few times as it can, lets the rest of the pattern try at once, and takes one more repetition only when the rest fails. The counts stay the same: *? still allows zero or more, +? one or more. Only the order of the tries changes: once its minimum is met, a non-greedy repetition tries the rest of the pattern before each further round of its atom (ECMA-262, RepeatMatcher, step 9). Python’s documentation calls the same thing non-greedy or minimal matching, and Java’s calls it reluctant.

Every quantifier has a lazy form, and with nothing after it in the pattern each one stops at its minimum. The table lists what each form took from aaaa in the program further down:

Now the same row with ".*?". Step through it and compare the sub-label of .*? with the greedy run:

.*? held 0, 1, 2, 3 and then 4 characters, and the closing quote matched on the fifth try, so the first match is "Asha". The search then started again after it and found "Pune" the same way. The program prints those tries, every match of the row, and every form of the table. Press Edit and try /".+?"/g: it still finds both fields, since each holds at least one character.

// How the lazy .*? of ".*?" finds where a quoted field ends. After the opening quote, .*? takes nothing at first and
// lets the closing quote try at once; each time the quote fails, it takes one more character. The loop plays the
// engine's part for the first field; then the real regex finds every field, and every lazy form shows its minimum.
const line = '"Asha","Pune",411001';

const rest = line.slice(1);
for (let take = 0; take <= rest.length; take++) {
  const next = rest[take];
  if (next === '"') {
    console.log(`.*? holds ${take}, next is '"': the closing quote matches`);
    console.log(`took ${take} characters; the match is ${line.slice(0, take + 2)}`);
    break;
  }
  console.log(`.*? holds ${take}, next is ${next === undefined ? 'the end of the line' : `'${next}'`}: take one more`);
}

console.log('');
for (const match of line.matchAll(/".*?"/g)) {
  console.log(`/".*?"/g finds ${match[0]} at position ${match.index}`);
}
const alone = line.match(/".*?/g);
console.log(`/".*?/g, with nothing after the lazy part: ${alone.length} matches, each ${alone[0]}`);

console.log('');
for (const re of [/a*/, /a*?/, /a+/, /a+?/, /a?/, /a??/, /a{2,3}/, /a{2,3}?/]) {
  console.log(`${String(re).padEnd(10)} on aaaa takes ${JSON.stringify('aaaa'.match(re)[0])}`);
}

.*? holds 0, next is 'A': take one more
.*? holds 1, next is 's': take one more
.*? holds 2, next is 'h': take one more
.*? holds 3, next is 'a': take one more
.*? holds 4, next is '"': the closing quote matches
took 4 characters; the match is "Asha"

/".*?"/g finds "Asha" at position 0
/".*?"/g finds "Pune" at position 7
/".*?/g, with nothing after the lazy part: 4 matches, each "

/a*/       on aaaa takes "aaaa"
/a*?/      on aaaa takes ""
/a+/       on aaaa takes "aaaa"
/a+?/      on aaaa takes "a"
/a?/       on aaaa takes "a"
/a??/      on aaaa takes ""
/a{2,3}/   on aaaa takes "aaa"
/a{2,3}?/  on aaaa takes "aa"

The two runs differ in one thing only, the end they approach the closing quote from: the greedy star from the end of the row, the lazy one from the opening quote.

Lazy is not shortest: the leftmost start wins first

Lazy quantifiers are easy to read as “find the shortest match”. They are not. Search xxy with x.*?y and the answer is xxy, all three characters, although xy, which starts one position later, is shorter. The engine tries start positions from left to right and keeps the first one at which the whole pattern matches; that rule comes before any preference of a quantifier. At position 0 the x matches, .*? takes nothing and y fails against the second x; .*? takes that x, y matches, and the search is over. It never looks at position 1. MDN states the same rule: once a match succeeds at some index, later indices are not tried.

Laziness only decides how much a match takes from the start the engine has already chosen. Run the six searches; the last three are the familiar case of tags:

// A lazy quantifier does not look for the shortest match in the whole text. The engine tries start positions from the
// left and keeps the first one where the pattern matches; laziness only decides how much that match takes.
const tries = [
  [/x.*?y/g, 'xxy'],
  [/x.*y/g, 'xxy'],
  [/x[^x]*y/g, 'xxy'],
  [/<.+?>/g, '<a><b>'],
  [/<.+>/g, '<a><b>'],
  [/<[^>]+>/g, '<a><b>'],
];
for (const [re, text] of tries) {
  const found = [...text.matchAll(re)].map((m) => `${m[0]} at ${m.index}`);
  console.log(`${String(re).padEnd(11)} on ${text.padEnd(7)} finds ${found.join(', ')}`);
}

/x.*?y/g    on xxy     finds xxy at 0
/x.*y/g     on xxy     finds xxy at 0
/x[^x]*y/g  on xxy     finds xy at 1
/<.+?>/g    on <a><b>  finds <a> at 0, <b> at 3
/<.+>/g     on <a><b>  finds <a><b> at 0
/<[^>]+>/g  on <a><b>  finds <a> at 0, <b> at 3

Read the rows in pairs. On xxy the lazy and the greedy pattern find the same match, and only x[^x]*y finds xy: its class refuses a second x, so no match can start at position 0. On <a><b> the lazy <.+?> finds the two tags, the greedy <.+> one match that spans both, and <[^>]+> the two tags without any giving back. JavaScript, Python and Go’s default are all leftmost-firstleftmost-first: A rule for choosing among matches: take the earliest start, then the match a backtracking search finds first, which follows the order of the alternatives. JavaScript, Python and PCRE2 use it. More in “How an engine finds a match, step by step” engines, and the Python and Go tabs find the same matches. Go also has Longest(), which switches a compiled pattern to the leftmost-longestleftmost-longest: A rule for choosing among matches: take the earliest start, then the longest match from it, whatever the order of the alternatives. POSIX specifies it. More in “How an engine finds a match, step by step” rule; the last two lines of the Go tab show what it does to a lazy quantifier:

"""The leftmost searches in Python's re: a lazy quantifier still returns the match that starts furthest left."""

import re

for pattern, text in [
    (r"x.*?y", "xxy"),
    (r"x.*y", "xxy"),
    (r"x[^x]*y", "xxy"),
    (r"<.+?>", "<a><b>"),
    (r"<.+>", "<a><b>"),
    (r"<[^>]+>", "<a><b>"),
]:
    found = [f"{m.group()} at {m.start()}" for m in re.finditer(pattern, text)]
    print(f"{pattern:9} on {text:7} finds {', '.join(found)}")

x.*?y     on xxy     finds xxy at 0
x.*y      on xxy     finds xxy at 0
x[^x]*y   on xxy     finds xy at 1
<.+?>     on <a><b>  finds <a> at 0, <b> at 3
<.+>      on <a><b>  finds <a><b> at 0
<[^>]+>   on <a><b>  finds <a> at 0, <b> at 3

// The leftmost searches in Go's regexp package (leftmost-first, like JavaScript and Python), then two lazy patterns
// after Longest(), which switches the Regexp to leftmost-longest: among the matches that start furthest left it takes
// the longest, so the lazy quantifier no longer makes a difference.
package main

import (
	"fmt"
	"regexp"
	"strings"
)

func show(note string, re *regexp.Regexp, text string) {
	var found []string
	for _, loc := range re.FindAllStringIndex(text, -1) {
		found = append(found, fmt.Sprintf("%s at %d", text[loc[0]:loc[1]], loc[0]))
	}
	fmt.Printf("%s%-9s on %-7s finds %s\n", note, re, text, strings.Join(found, ", "))
}

func main() {
	for _, t := range [][2]string{
		{`x.*?y`, "xxy"},
		{`x.*y`, "xxy"},
		{`x[^x]*y`, "xxy"},
		{`<.+?>`, "<a><b>"},
		{`<.+>`, "<a><b>"},
		{`<[^>]+>`, "<a><b>"},
	} {
		show("", regexp.MustCompile(t[0]), t[1])
	}
	fmt.Println()
	for _, t := range [][2]string{{`x.*?y`, "xxy"}, {`<.+?>`, "<a><b>"}} {
		re := regexp.MustCompile(t[0])
		re.Longest()
		show("Longest(): ", re, t[1])
	}
}

x.*?y     on xxy     finds xxy at 0
x.*y      on xxy     finds xxy at 0
x[^x]*y   on xxy     finds xy at 1
<.+?>     on <a><b>  finds <a> at 0, <b> at 3
<.+>      on <a><b>  finds <a><b> at 0
<[^>]+>   on <a><b>  finds <a> at 0, <b> at 3

Longest(): x.*?y     on xxy     finds xxy at 0
Longest(): <.+?>     on <a><b>  finds <a><b> at 0

After Longest(), <.+?> finds <a><b> again: among the matches that start furthest left, Go now takes the longest one (its documentation of Longest), so a lazy quantifier makes no difference there. Lazy and greedy are preferences that only a leftmost-first search follows.

A negated class says where a field ends

On the clean row, ".*?" and "[^"]*" find the same two fields. The second is a negated classnegated class: A character class that starts with a caret right after the opening bracket, such as [^0-9]. It matches exactly one character that is not in the set, line breaks included. More in “Character classes, ranges and negation” repeated by a greedy star: any run of characters that are not a quote. It cannot run past the closing quote, because a quote is the one character it refuses, while a lazy dot has no such limit: it extends past a closing quote whenever the rest of the pattern needs it to. Two rows show the difference. The first is a record whose keys are quoted fields followed by a colon; the second is a CSV row whose address field holds a line break, which CSV allows inside quotes (RFC 4180, section 2, rule 6):

// Three ways to write the middle of a quoted field, on three lines: a clean row, the keys of a JSON-like record (a key
// is a quoted field followed by a colon) and a CSV row whose second field holds a line break. Each match is printed in
// [brackets], with a line break shown as \n.
const show = (re, text) => {
  const found = text.match(re) ?? [];
  const list = found.map((m) => `[${m.replace(/\n/g, '\\n')}]`).join(' ');
  console.log(`  ${String(re).padEnd(11)} ${list || 'no match'}`);
};

const row = '"Asha","Pune",411001';
console.log('clean row:');
for (const re of [/".*"/g, /".*?"/g, /"[^"]*"/g]) show(re, row);

const record = '{"name": "Asha Rao", "city": "Pune"}';
console.log('keys of a record:');
for (const re of [/".*?":/g, /"[^"]*":/g]) show(re, record);

const csv = '"Asha Rao","12 MG Road\nPune","411001"';
console.log('a line break inside a field:');
for (const re of [/".*?"/g, /".*?"/gs, /"[^"]*"/g]) show(re, csv);

clean row:
  /".*"/g     ["Asha","Pune"]
  /".*?"/g    ["Asha"] ["Pune"]
  /"[^"]*"/g  ["Asha"] ["Pune"]
keys of a record:
  /".*?":/g   ["name":] ["Asha Rao", "city":]
  /"[^"]*":/g ["name":] ["city":]
a line break inside a field:
  /".*?"/g    ["Asha Rao"] [","]
  /".*?"/gs   ["Asha Rao"] ["12 MG Road\nPune"] ["411001"]
  /"[^"]*"/g  ["Asha Rao"] ["12 MG Road\nPune"] ["411001"]

On the record, ".*?": finds "name": and then "Asha Rao", "city":. After "Asha Rao" the colon failed against a comma, so .*? took one more character, and another, past the closing quote of Asha Rao and the opening quote of city, until a quote and a colon followed. The negated class cannot do that: its run stops at the next quote, so from the quote before Asha Rao the colon fails and the engine moves on to a later start. The second key comes out right, "city":.

On the CSV row the dot fails the other way: it does not match a line break, so ".*?" cannot finish the address field and ends up pairing the two quotes around a comma, ",". The s flag lets the dot cross the line break and mends this row, but it does nothing for the record; the class mends both. Python, Go and PHP print the same matches:

"""The three ways to write the middle of a quoted field, in Python's re, on the same three lines. Each match is
printed in [brackets], with a line break shown as \\n; re.S is Python's flag for a dot that also matches it."""

import re


def show(pattern, text, flags=0, note=""):
    found = re.findall(pattern, text, flags)
    shown = " ".join(f"[{m}]".replace("\n", "\\n") for m in found)
    print(f"  {pattern + note:11} {shown or 'no match'}")


row = '"Asha","Pune",411001'
print("clean row:")
for pattern in [r'".*"', r'".*?"', r'"[^"]*"']:
    show(pattern, row)

record = '{"name": "Asha Rao", "city": "Pune"}'
print("keys of a record:")
for pattern in [r'".*?":', r'"[^"]*":']:
    show(pattern, record)

csv = '"Asha Rao","12 MG Road\nPune","411001"'
print("a line break inside a field:")
show(r'".*?"', csv)
show(r'".*?"', csv, re.S, " re.S")
show(r'"[^"]*"', csv)

clean row:
  ".*"        ["Asha","Pune"]
  ".*?"       ["Asha"] ["Pune"]
  "[^"]*"     ["Asha"] ["Pune"]
keys of a record:
  ".*?":      ["name":] ["Asha Rao", "city":]
  "[^"]*":    ["name":] ["city":]
a line break inside a field:
  ".*?"       ["Asha Rao"] [","]
  ".*?" re.S  ["Asha Rao"] ["12 MG Road\nPune"] ["411001"]
  "[^"]*"     ["Asha Rao"] ["12 MG Road\nPune"] ["411001"]

// The three ways to write the middle of a quoted field, in Go's regexp package (RE2 syntax), on the same three lines.
// Each match is printed in [brackets], with a line break shown as \n; (?s) lets the dot match a line break too.
package main

import (
	"fmt"
	"regexp"
	"strings"
)

func show(pattern, text string) {
	var shown []string
	for _, m := range regexp.MustCompile(pattern).FindAllString(text, -1) {
		shown = append(shown, "["+strings.ReplaceAll(m, "\n", `\n`)+"]")
	}
	if len(shown) == 0 {
		shown = []string{"no match"}
	}
	fmt.Printf("  %-11s %s\n", pattern, strings.Join(shown, " "))
}

func main() {
	row := `"Asha","Pune",411001`
	fmt.Println("clean row:")
	for _, p := range []string{`".*"`, `".*?"`, `"[^"]*"`} {
		show(p, row)
	}

	record := `{"name": "Asha Rao", "city": "Pune"}`
	fmt.Println("keys of a record:")
	for _, p := range []string{`".*?":`, `"[^"]*":`} {
		show(p, record)
	}

	csv := "\"Asha Rao\",\"12 MG Road\nPune\",\"411001\""
	fmt.Println("a line break inside a field:")
	for _, p := range []string{`".*?"`, `(?s)".*?"`, `"[^"]*"`} {
		show(p, csv)
	}
}

clean row:
  ".*"        ["Asha","Pune"]
  ".*?"       ["Asha"] ["Pune"]
  "[^"]*"     ["Asha"] ["Pune"]
keys of a record:
  ".*?":      ["name":] ["Asha Rao", "city":]
  "[^"]*":    ["name":] ["city":]
a line break inside a field:
  ".*?"       ["Asha Rao"] [","]
  (?s)".*?"   ["Asha Rao"] ["12 MG Road\nPune"] ["411001"]
  "[^"]*"     ["Asha Rao"] ["12 MG Road\nPune"] ["411001"]

<?php
// The three ways to write the middle of a quoted field, in PHP's preg functions (PCRE2), on the same three lines.
// Each match is printed in [brackets], with a line break shown as \n; the s modifier lets the dot match it too.
function show(string $pattern, string $text): void
{
    preg_match_all($pattern, $text, $found);
    $shown = array_map(fn ($m) => '[' . str_replace("\n", '\n', $m) . ']', $found[0]);
    printf("  %-11s %s\n", $pattern, $shown ? implode(' ', $shown) : 'no match');
}

$row = '"Asha","Pune",411001';
echo "clean row:\n";
foreach (['/".*"/', '/".*?"/', '/"[^"]*"/'] as $p) {
    show($p, $row);
}

$record = '{"name": "Asha Rao", "city": "Pune"}';
echo "keys of a record:\n";
foreach (['/".*?":/', '/"[^"]*":/'] as $p) {
    show($p, $record);
}

$csv = "\"Asha Rao\",\"12 MG Road\nPune\",\"411001\"";
echo "a line break inside a field:\n";
foreach (['/".*?"/', '/".*?"/s', '/"[^"]*"/'] as $p) {
    show($p, $csv);
}

clean row:
  /".*"/      ["Asha","Pune"]
  /".*?"/     ["Asha"] ["Pune"]
  /"[^"]*"/   ["Asha"] ["Pune"]
keys of a record:
  /".*?":/    ["name":] ["Asha Rao", "city":]
  /"[^"]*":/  ["name":] ["city":]
a line break inside a field:
  /".*?"/     ["Asha Rao"] [","]
  /".*?"/s    ["Asha Rao"] ["12 MG Road\nPune"] ["411001"]
  /"[^"]*"/   ["Asha Rao"] ["12 MG Road\nPune"] ["411001"]

The class saves work as well. A lazy .*? tries the closing quote after every character of the field, and a greedy .* first runs to the end of the line and then gives back. PCRE2 can count this: its test program finds the smallest match limit each match needs, the number of rounds of its matching loop, which, unlike a time, does not depend on how fast the computer is (pcre2api, pcre2test). Each subject below holds a field of 1,000 characters:

"""How much work PCRE2 10.49 does to match one quoted field of 1,000 characters with ".*", ".*?" and "[^"]*".

pcre2test's find_limits_noheap modifier runs the match again and again to find the smallest match limit that lets it
finish: the number of rounds of PCRE2's matching loop the match needs (pcre2api), a count that comes out the same on
every computer, unlike a time. In a subject line, \\[a]{1000} is pcre2test's way to write 1,000 copies of a; this
program prints such a run in the same short form, a{1000}, where pcre2test printed the whole match."""

import contextlib
import io
import re

from pcre2_session import run


def show(script: str) -> None:
    """Runs the script and prints the transcript with every run of ten or more equal letters written as a{1000}."""
    out = io.StringIO()
    with contextlib.redirect_stdout(out):
        run(script)
    text = re.sub(r"([a-z])\1{9,}", lambda m: f"{m.group(1)}{{{len(m.group(0))}}}", out.getvalue())
    print(text, end="")


show(r'''
# A quoted field of 1,000 characters at the end of the line
/".*"/
    "\[a]{1000}"\=find_limits_noheap

/".*?"/
    "\[a]{1000}"\=find_limits_noheap

/"[^"]*"/
    "\[a]{1000}"\=find_limits_noheap

# The same field with 1,000 more characters after it
/".*"/
    "\[a]{1000}"\[b]{1000}\=find_limits_noheap

/".*?"/
    "\[a]{1000}"\[b]{1000}\=find_limits_noheap

/"[^"]*"/
    "\[a]{1000}"\[b]{1000}\=find_limits_noheap
''')

$ pcre2test -q patterns.txt   (PCRE2 10.49)
# A quoted field of 1,000 characters at the end of the line
/".*"/
    "\[a]{1000}"\=find_limits_noheap
Minimum match limit = 4
Minimum depth limit = 3
 0: "a{1000}"

/".*?"/
    "\[a]{1000}"\=find_limits_noheap
Minimum match limit = 1003
Minimum depth limit = 3
 0: "a{1000}"

/"[^"]*"/
    "\[a]{1000}"\=find_limits_noheap
Minimum match limit = 2
Minimum depth limit = 2
 0: "a{1000}"

# The same field with 1,000 more characters after it
/".*"/
    "\[a]{1000}"\[b]{1000}\=find_limits_noheap
Minimum match limit = 1004
Minimum depth limit = 3
 0: "a{1000}"

/".*?"/
    "\[a]{1000}"\[b]{1000}\=find_limits_noheap
Minimum match limit = 1003
Minimum depth limit = 3
 0: "a{1000}"

/"[^"]*"/
    "\[a]{1000}"\[b]{1000}\=find_limits_noheap
Minimum match limit = 2
Minimum depth limit = 2
 0: "a{1000}"

"""Runs a script of patterns and subjects through pcre2test, the test program of the PCRE2 10.49 library, and prints
what it printed.

pcre2test reads a pattern line such as /a.b/ (with modifiers after the closing slash, for example /a.b/dotall,utf),
then one subject per indented line, and prints each subject with " 0:" and the matched text (" 1:" and on for groups)
or "No match". A line starting with # is a comment and is printed as it is. Escapes in a subject such as \\r, \\n or
\\x{2028} stand for those characters (pcre2test's own subject escapes), so invisible characters can be tested.

The script is given in the example file itself, so the example's run record changes whenever the script does:

    from pcre2_session import run
    run(r'''
    /a.b/
        a\\rb
    ''')

The version banner and its release date are not printed (pcre2test -q); the session checks the version itself and
stops if this computer's pcre2test is not PCRE2 10.49, so a record never shows another version's behaviour.
"""

import re
import subprocess
import sys
import tempfile
from pathlib import Path

VERSION = "10.49"
_CANDIDATES = ("/opt/homebrew/bin/pcre2test", "/usr/local/bin/pcre2test")
_ENV = {"PATH": "/usr/bin:/bin", "LC_ALL": "C.UTF-8", "LANG": "C.UTF-8", "TZ": "UTC"}


def _tool() -> str:
    for candidate in _CANDIDATES:
        if Path(candidate).is_file():
            return candidate
    sys.exit("pcre2test (PCRE2 10.49) was not found")


def _check_version(tool: str) -> None:
    first = subprocess.run([tool, "-C"], capture_output=True, text=True, env=_ENV).stdout.splitlines()[:1]
    found = re.match(r"PCRE2 version (\S+)", first[0]) if first else None
    if not found or found.group(1) != VERSION:
        sys.exit(f"this session needs PCRE2 {VERSION}, found: {first[0] if first else 'nothing'}")


def run(script: str) -> None:
    """Prints the pcre2test transcript of the script (patterns, subjects and results)."""
    tool = _tool()
    _check_version(tool)
    lines = script.strip("\n").splitlines()
    text = "\n".join(_dedent(lines)) + "\n"
    with tempfile.TemporaryDirectory() as folder:
        source = Path(folder) / "patterns.txt"
        source.write_text(text, encoding="utf-8")
        done = subprocess.run([tool, "-q", str(source)], capture_output=True, text=True, encoding="utf-8", env=_ENV)
    print(f"$ pcre2test -q patterns.txt   (PCRE2 {VERSION})")
    sys.stdout.write(done.stdout)
    if done.stderr:
        sys.stdout.write(done.stderr)
    if done.returncode != 0:
        print(f"[exit status {done.returncode}]")
    sys.stdout.flush()


def _dedent(lines: list[str]) -> list[str]:
    """Removes the indentation the whole script shares, so it can sit indented inside a Python call."""
    widths = [len(line) - len(line.lstrip(" ")) for line in lines if line.strip()]
    cut = min(widths) if widths else 0
    return [line[cut:] for line in lines]

The minimum match limits from the run, side by side:

The lazy pattern pays for the length of the field and the greedy one for the text after it; the class pays for neither. PCRE2 even compiles [^"]* as a run that never gives characters back, since the quote after it can never be one of them (pcre2api calls this auto-possessification); the next lesson explains such runs. On a long line with many fields the difference adds up, and some patterns make a backtracking engine try far more combinations than these; a later module, on performance and ReDoS, deals with them.

Ungreedy mode swaps the two forms, where it exists

Some engines let a pattern flip its default. In Go, PCRE2 and PHP, (?U) at the start of a pattern turns on ungreedy modeungreedy mode: An option of PCRE2, PHP (the U modifier) and Go, also set with (?U) in a pattern, that swaps the two forms: a quantifier without a question mark is lazy and one with it is greedy. JavaScript and Python have no such mode.: every quantifier without a question mark becomes lazy, and every quantifier with one becomes greedy. Go’s syntax table describes the flag as a swap of x* and x*?, x+ and x+?, and so on; PCRE2 names it PCRE2_UNGREEDY and says it is not compatible with Perl; PHP also sets it with the U modifier after the closing delimiter. Each tab runs the row through both forms, with and without the mode:

// (?U) in Go's regexp package (RE2 syntax) is the ungreedy flag: it swaps the meaning of x* and x*?, x+ and x+?, and
// of the other quantifiers.
package main

import (
	"fmt"
	"regexp"
	"strings"
)

func main() {
	line := `"Asha","Pune",411001`
	for _, p := range []string{`".*"`, `(?U)".*"`, `".*?"`, `(?U)".*?"`, `(?U)\d+`, `(?U)\d+?`} {
		found := regexp.MustCompile(p).FindAllString(line, -1)
		fmt.Printf("%-10s %s\n", p, strings.Join(found, " "))
	}
}

".*"       "Asha","Pune"
(?U)".*"   "Asha" "Pune"
".*?"      "Asha" "Pune"
(?U)".*?"  "Asha","Pune"
(?U)\d+    4 1 1 0 0 1
(?U)\d+?   411001

<?php
// The U modifier of PHP's preg functions, and (?U) inside a pattern, set PCRE2's ungreedy mode: a quantifier without
// a question mark is lazy, and one with a question mark is greedy.
$line = '"Asha","Pune",411001';
foreach (['/".*"/', '/".*"/U', '/(?U)".*"/', '/".*?"/U', '/\d+/U', '/\d+?/U'] as $pattern) {
    preg_match_all($pattern, $line, $found);
    printf("%-11s %s\n", $pattern, implode(' ', $found[0]));
}

/".*"/      "Asha","Pune"
/".*"/U     "Asha" "Pune"
/(?U)".*"/  "Asha" "Pune"
/".*?"/U    "Asha","Pune"
/\d+/U      4 1 1 0 0 1
/\d+?/U     411001

"""Ungreedy mode in PCRE2 10.49 through pcre2test: (?U) at the start of the pattern, or the ungreedy modifier, which
sets the PCRE2_UNGREEDY compile option. Either way ".*" becomes lazy and ".*?" greedy."""

from pcre2_session import run

run(r'''
/".*"/g
    "Asha","Pune",411001

/(?U)".*"/g
    "Asha","Pune",411001

/".*"/g,ungreedy
    "Asha","Pune",411001

/".*?"/g,ungreedy
    "Asha","Pune",411001
''')

$ pcre2test -q patterns.txt   (PCRE2 10.49)
/".*"/g
    "Asha","Pune",411001
 0: "Asha","Pune"

/(?U)".*"/g
    "Asha","Pune",411001
 0: "Asha"
 0: "Pune"

/".*"/g,ungreedy
    "Asha","Pune",411001
 0: "Asha"
 0: "Pune"

/".*?"/g,ungreedy
    "Asha","Pune",411001
 0: "Asha","Pune"

"""Python's re has no ungreedy mode: (?U) is refused, and none of its flags swaps greedy and lazy."""

import re

for source in ['(?U)".*"', '(?U:".*")']:
    try:
        re.compile(source)
        print(f"{source:10} compiles")
    except re.PatternError as e:
        print(f"{source:10} {type(e).__name__}: {e}")

print("flags:", ", ".join(sorted(flag.name for flag in re.RegexFlag)))

(?U)".*"   PatternError: unknown extension ?U at position 1
(?U:".*")  PatternError: unknown extension ?U at position 1
flags: ASCII, DEBUG, DOTALL, IGNORECASE, LOCALE, MULTILINE, UNICODE, VERBOSE

"""Runs a script of patterns and subjects through pcre2test, the test program of the PCRE2 10.49 library, and prints
what it printed.

pcre2test reads a pattern line such as /a.b/ (with modifiers after the closing slash, for example /a.b/dotall,utf),
then one subject per indented line, and prints each subject with " 0:" and the matched text (" 1:" and on for groups)
or "No match". A line starting with # is a comment and is printed as it is. Escapes in a subject such as \\r, \\n or
\\x{2028} stand for those characters (pcre2test's own subject escapes), so invisible characters can be tested.

The script is given in the example file itself, so the example's run record changes whenever the script does:

    from pcre2_session import run
    run(r'''
    /a.b/
        a\\rb
    ''')

The version banner and its release date are not printed (pcre2test -q); the session checks the version itself and
stops if this computer's pcre2test is not PCRE2 10.49, so a record never shows another version's behaviour.
"""

import re
import subprocess
import sys
import tempfile
from pathlib import Path

VERSION = "10.49"
_CANDIDATES = ("/opt/homebrew/bin/pcre2test", "/usr/local/bin/pcre2test")
_ENV = {"PATH": "/usr/bin:/bin", "LC_ALL": "C.UTF-8", "LANG": "C.UTF-8", "TZ": "UTC"}


def _tool() -> str:
    for candidate in _CANDIDATES:
        if Path(candidate).is_file():
            return candidate
    sys.exit("pcre2test (PCRE2 10.49) was not found")


def _check_version(tool: str) -> None:
    first = subprocess.run([tool, "-C"], capture_output=True, text=True, env=_ENV).stdout.splitlines()[:1]
    found = re.match(r"PCRE2 version (\S+)", first[0]) if first else None
    if not found or found.group(1) != VERSION:
        sys.exit(f"this session needs PCRE2 {VERSION}, found: {first[0] if first else 'nothing'}")


def run(script: str) -> None:
    """Prints the pcre2test transcript of the script (patterns, subjects and results)."""
    tool = _tool()
    _check_version(tool)
    lines = script.strip("\n").splitlines()
    text = "\n".join(_dedent(lines)) + "\n"
    with tempfile.TemporaryDirectory() as folder:
        source = Path(folder) / "patterns.txt"
        source.write_text(text, encoding="utf-8")
        done = subprocess.run([tool, "-q", str(source)], capture_output=True, text=True, encoding="utf-8", env=_ENV)
    print(f"$ pcre2test -q patterns.txt   (PCRE2 {VERSION})")
    sys.stdout.write(done.stdout)
    if done.stderr:
        sys.stdout.write(done.stderr)
    if done.returncode != 0:
        print(f"[exit status {done.returncode}]")
    sys.stdout.flush()


def _dedent(lines: list[str]) -> list[str]:
    """Removes the indentation the whole script shares, so it can sit indented inside a Python call."""
    widths = [len(line) - len(line.lstrip(" ")) for line in lines if line.strip()]
    cut = min(widths) if widths else 0
    return [line[cut:] for line in lines]

In Go, (?U)".*" finds the two fields and (?U)".*?" finds one match across both, the reverse of the same patterns without the flag, and (?U)\d+ takes one digit at a time: six matches in 411001. PHP’s /".*"/U and PCRE2’s ungreedy modifier print the same lines. Python’s re stops with a PatternError, unknown extension ?U, and none of its flags swaps the two forms. JavaScript refuses the mode too:

// (?U), the ungreedy mode of Go, PCRE2 and PHP, is not part of JavaScript: a pattern that uses it does not compile.
// A pattern written for that mode is ported by swapping each quantifier by hand: in ungreedy mode .* is lazy and .*?
// is greedy, so the JavaScript versions are the other way round.
for (const source of ['(?U)".*"', '(?U:".*")']) {
  try {
    new RegExp(source);
    console.log(`${source.padEnd(10)} compiles`);
  } catch (e) {
    console.log(`${source.padEnd(10)} ${e.name}`);
  }
}

const line = '"Asha","Pune",411001';
const ports = [
  ['(?U)".*"', /".*?"/g],
  ['(?U)".*?"', /".*"/g],
  ['(?U)\\d+', /\d+?/g],
  ['(?U)\\d+?', /\d+/g],
];
console.log('');
for (const [ungreedy, port] of ports) {
  console.log(`${ungreedy.padEnd(10)} becomes ${String(port).padEnd(8)} ${line.match(port).join(' ')}`);
}

(?U)".*"   SyntaxError
(?U:".*")  SyntaxError

(?U)".*"   becomes /".*?"/g "Asha" "Pune"
(?U)".*?"  becomes /".*"/g  "Asha","Pune"
(?U)\d+    becomes /\d+?/g  4 1 1 0 0 1
(?U)\d+?   becomes /\d+/g   411001

Both spellings, (?U) and the group form (?U:...), are a SyntaxError in JavaScript. So a pattern written for ungreedy mode is ported by hand: put a question mark after every quantifier that has none, and take it away from every quantifier that has one. The four ported patterns print what the Go tab printed for the originals.

The mode costs readers something too: in a long pattern .* means one thing after the flag and the opposite before it. Use it knowingly, in code that only one engine runs, with a comment beside it; anywhere else, write the lazy quantifiers out.

Practise: pull the links out of a wiki page

The exercise asks for one pattern that uses the whole lesson. A wiki page writes its links as [[Pune]] or [[Pune|the city]], and real pages hold two links on one line, a link that was never closed and empty brackets. The starter’s greedy pattern swallows several links at once; a lazy one does better but still runs over a broken link. The sample tests run in your browser, in JavaScript and in Python:

// wikiLinks(text): every [[target]] and [[target|label]] link of a wiki page, in order, as [target, label] pairs.
// A target and a label are one or more characters other than [, ], | and a line break; anything else is not a link.

// Starter: a greedy .* between the brackets (the tests show where it goes wrong).
const LINK = /\[\[.*\]\]/g;

/** The links of text, in order: [target, label], the label equal to the target when the link has none. */
export function wikiLinks(text) {
  return (text.match(LINK) || []).map((link) => {
    const inner = link.slice(2, -2);
    const bar = inner.indexOf('|');
    return bar === -1 ? [inner, inner] : [inner.slice(0, bar), inner.slice(bar + 1)];
  });
}

import { test, assert } from 'mysmartcopilot:test';
import { wikiLinks } from './wikilinks.mjs';

function check(text, expected) {
  const got = wikiLinks(text);
  assert.ok(Array.isArray(got), `wikiLinks(${JSON.stringify(text)}) should return an array`);
  assert.deepEqual(got, expected, `wikiLinks(${JSON.stringify(text)})`);
}

test('one link without a label: the label is the target', () => {
  check('See [[Pune]] for the timings.', [['Pune', 'Pune']]);
});

test('one link with a label', () => {
  check('Trains to [[Pune|the city]] leave at six.', [['Pune', 'the city']]);
});

test('two links on one line stay two links', () => {
  check('See [[Pune]] and [[Mumbai|Bombay]].', [['Pune', 'Pune'], ['Mumbai', 'Bombay']]);
});

test('links side by side, and targets with spaces and other scripts', () => {
  check('[[New Delhi]][[पुणे|Pune]]', [['New Delhi', 'New Delhi'], ['पुणे', 'Pune']]);
});

test('links on several lines', () => {
  check('[[Pune]] is in the west.\nRead about [[Chennai|the south]] next.\n', [['Pune', 'Pune'], ['Chennai', 'the south']]);
});

test('a link that is never closed is skipped, and the next link still counts', () => {
  check('[[Pune] has a typo, but [[Delhi]] is fine.', [['Delhi', 'Delhi']]);
  check('The list ends with [[Kochi', []);
});

test('single brackets and empty parts are not links', () => {
  check('[Pune] [[]] [[|Pune]] [[Pune|]]', []);
});

test('a second bar is not a link', () => {
  check('[[Pune|the|city]] and [[Goa]]', [['Goa', 'Goa']]);
});

test('a link does not run over a line break', () => {
  check('[[New\nDelhi]] and [[Agra]]', [['Agra', 'Agra']]);
});

test('a page without links gives an empty list', () => {
  check('', []);
  check('No links on this page.', []);
});

"""wiki_links(text): every [[target]] and [[target|label]] link of a wiki page, in order, as (target, label) pairs.
A target and a label are one or more characters other than [, ], | and a line break; anything else is not a link."""

import re

# Starter: a greedy .* between the brackets (the tests show where it goes wrong).
LINK = re.compile(r"\[\[.*\]\]")


def wiki_links(text):
    """The links of text, in order: (target, label), the label equal to the target when the link has none."""
    links = []
    for link in LINK.findall(text):
        inner = link[2:-2]
        target, _, label = inner.partition("|")
        links.append((target, label) if "|" in inner else (inner, inner))
    return links

from wikilinks import wiki_links


def test_one_link():
    """one link without a label: the label is the target"""
    assert wiki_links("See [[Pune]] for the timings.") == [("Pune", "Pune")]


def test_label():
    """one link with a label"""
    assert wiki_links("Trains to [[Pune|the city]] leave at six.") == [("Pune", "the city")]


def test_two_links_on_one_line():
    """two links on one line stay two links"""
    assert wiki_links("See [[Pune]] and [[Mumbai|Bombay]].") == [("Pune", "Pune"), ("Mumbai", "Bombay")]


def test_side_by_side():
    """links side by side, and targets with spaces and other scripts"""
    assert wiki_links("[[New Delhi]][[पुणे|Pune]]") == [("New Delhi", "New Delhi"), ("पुणे", "Pune")]


def test_several_lines():
    """links on several lines"""
    text = "[[Pune]] is in the west.\nRead about [[Chennai|the south]] next.\n"
    assert wiki_links(text) == [("Pune", "Pune"), ("Chennai", "the south")]


def test_never_closed():
    """a link that is never closed is skipped, and the next link still counts"""
    assert wiki_links("[[Pune] has a typo, but [[Delhi]] is fine.") == [("Delhi", "Delhi")]
    assert wiki_links("The list ends with [[Kochi") == []


def test_empty_parts():
    """single brackets and empty parts are not links"""
    assert wiki_links("[Pune] [[]] [[|Pune]] [[Pune|]]") == []


def test_second_bar():
    """a second bar is not a link"""
    assert wiki_links("[[Pune|the|city]] and [[Goa]]") == [("Goa", "Goa")]


def test_line_break():
    """a link does not run over a line break"""
    assert wiki_links("[[New\nDelhi]] and [[Agra]]") == [("Agra", "Agra")]


def test_no_links():
    """a page without links gives an empty list"""
    assert wiki_links("") == []
    assert wiki_links("No links on this page.") == []

Last, the self-check: five ideas, the weakest one first, with the reason behind every choice shown the moment you answer.

Interview questions

Warm-up: what changes when a quantifier is made lazy, and does a lazy pattern return the shortest match?

A lazy quantifier keeps the same repetition counts and changes only the order of the tries. A greedy * takes as many repetitions as it can and gives them back one at a time when the rest of the pattern fails; *? takes as few as it can and adds one at a time. So ".*" on "Asha","Pune",411001 returns one match that runs to the last quote, while ".*?" returns "Asha" and "Pune". Lazy does not mean shortest, though: the engine still keeps the first start position where the pattern matches, so x.*?y on xxy returns all three characters, not xy. A lazy quantifier can also run past the delimiter you meant when the rest of the pattern fails there, so when a field ends at one character, a negated class such as [^"]* states that limit directly.

Two harder questions follow: config blocks that run into each other, and a parser that leaves PHP’s ungreedy mode behind. Jot down the first thing you would check in each, and only then open it:

Key takeaways

• A greedy quantifier takes every repetition it can and gives them back one at a time, so ".*" on a row of quoted fields gives back eight characters and still runs to the last quote: one match for two fields.
• A lazy quantifier, a quantifier with a question mark after it, tries the rest of the pattern before each extra repetition, so ".*?" stops at the first closing quote that lets the pattern match.
• Laziness never moves the start of a match: the leftmost start wins first, so x.*?y on xxy returns xxy, and under Go’s leftmost-longest Longest() a lazy quantifier makes no difference.
• A negated class such as "[^"]*" cannot run past the closing quote or stop at a line break, so it finds the right fields where .*? does not, and PCRE2 needs a match limit of 2 for it against 1,003 for the lazy dot on a field of 1,000 characters.
• (?U) swaps greedy and lazy in Go, PCRE2 and PHP, does not compile in JavaScript or Python and means Unicode classes in Java, so a pattern written for it is ported by swapping each quantifier by hand.