Regular Expressions

The previous lesson measured which information each of the three time types carries and which it does not. This lesson asks the same question on text: whether a string matches a given pattern. Java’s regular expression API has two parts — Pattern, the pattern itself; Matcher, the party that applies a pattern to a specific input — and this split already hints at the answer: a pattern is a value built once and used again and again, not a one-time call.

Four sections proceed in order: the pattern as a value and the two matching methods’ separate contract, the separate result two quantifier forms produce on the same input, the course’s single ineffective rule break (broken rule, unchanged result, changed cost), and the final limiting measurement — backtracking’s step count does not grow linearly with the input.

Regular-expression syntax was already built up in the Shell Programming course and in Python Fundamentals, and is not retaught here. This lesson’s contribution is Java’s own mechanism: the pattern as a compiled object, matching called through separate methods on it, and the decisions those methods force onto the caller.

A Pattern Is a Compiled Value

• IO25 — A single Pattern object is tested against four separate inputs with both matches (exact match) and find (search). Same pattern, same input, two separate methods.

// ExactMatchAndSearch.java — the pattern is a compiled value, matches and find carry separate contracts
import java.util.regex.*;

public class ExactMatchAndSearch {
    public static void main(String[] args) {
        Pattern pattern = Pattern.compile("[0-9]+");
        String[] inputs = { "12345", "code-12345", "12345-end", "abc" };

        System.out.printf("%-16s%-10s%s%n", "input", "matches", "find");
        for (String input : inputs) {
            Matcher m1 = pattern.matcher(input);
            boolean exactMatch = m1.matches();
            Matcher m2 = pattern.matcher(input);
            boolean search = m2.find();
            System.out.printf("%-16s%-10s%s%n", input, exactMatch, search);
        }
    }
}

input           matches   find
12345           true      true
code-12345      false     true
12345-end       false     true
abc             false     false

The Pattern.compile call is made once, and the returned pattern becomes the basis for four separate Matcher instances — the pattern itself is not a call, it is a value. The two methods called on it ask different questions. matches asks whether the entire input fits the pattern; code-12345 has digits, but the extra code- prefix means the whole input does not fit, so matches returns false. find, on the other hand, looks for a substring somewhere in the input that fits the pattern; since 12345 is found inside the same input, find returns true. Only on the last line do the two agree, because abc has no digits at all — neither method can find anything. What changes the contract while Pattern stays the same is the method called, not the pattern itself.

A Greedy and a Reluctant Quantifier Produce Different Captures

• IO26 — The same capturing group is written in two quantifier forms: (.*) greedy, (.*?) reluctant. Both are applied to the same input, the same pair of square brackets.

// GreedyAndReluctant.java — a greedy and a reluctant quantifier produce different captures on the same input
import java.util.regex.*;

public class GreedyAndReluctant {
    public static void main(String[] args) {
        String input = "[record-1][record-2]";

        Pattern greedy = Pattern.compile("\\[(.*)\\]");
        Pattern reluctant = Pattern.compile("\\[(.*?)\\]");

        Matcher m1 = greedy.matcher(input);
        m1.find();
        Matcher m2 = reluctant.matcher(input);
        m2.find();

        System.out.println("input: " + input);
        System.out.println("greedy    [(.*)]   captured: " + m1.group(1));
        System.out.println("reluctant [(.*?)]  captured: " + m2.group(1));

        int greedyCount = 0;
        Matcher m3 = greedy.matcher(input);
        while (m3.find()) greedyCount++;
        int reluctantCount = 0;
        Matcher m4 = reluctant.matcher(input);
        while (m4.find()) reluctantCount++;
        System.out.println("greedy total match count: " + greedyCount);
        System.out.println("reluctant total match count: " + reluctantCount);
    }
}

input: [record-1][record-2]
greedy    [(.*)]   captured: record-1][record-2
reluctant [(.*?)]  captured: record-1
greedy total match count: 1
reluctant total match count: 2

Both quantifiers mean “zero or more characters” and accept exactly the same set. What differs is not the set but the order they try it in. Greedy tries the longest run first and backs off only when the match fails; it starts with a .* reaching the end of the input, then gives ground backward until a closing bracket appears. Since the input has two closing brackets, the last one wins — the captured string spans everything between the two records, record-1][record-2. Reluctant does the opposite: it tries the shortest run, the empty string, first, and extends only when it must, stopping at the first closing bracket. The concrete result shows up in the match count: greedy consumes the whole input in one match, reluctant finds two separate matches in the same input.

The Caller’s Rule: Recompiling Is Ineffective

• IO27 — Five inputs are processed two ways: with a pattern recompiled every time, and with a pattern compiled once and used five times. The number of compile calls is also counted.

// Recompiling.java — recompiling the pattern on every call is ineffective: result stays the same, cost does not
import java.util.List;
import java.util.regex.*;

public class Recompiling {
    static int compileCounter = 0;

    static Pattern compile(String regex) {
        compileCounter++;
        return Pattern.compile(regex);
    }

    static boolean compilingEveryCall(String regex, String input) {
        return compile(regex).matcher(input).find();
    }

    public static void main(String[] args) {
        List<String> inputs = List.of("alpha-01", "beta-02", "gamma-03", "delta-04", "epsilon-05");
        String regex = "^[a-z]+-[0-9]{2}$";

        compileCounter = 0;
        boolean[] results1 = new boolean[inputs.size()];
        for (int i = 0; i < inputs.size(); i++)
            results1[i] = compilingEveryCall(regex, inputs.get(i));
        int compileCountEveryCall = compileCounter;

        compileCounter = 0;
        Pattern singlePattern = compile(regex);
        boolean[] results2 = new boolean[inputs.size()];
        for (int i = 0; i < inputs.size(); i++)
            results2[i] = singlePattern.matcher(inputs.get(i)).find();
        int compileCountOnce = compileCounter;

        System.out.println("are the results the same: " + java.util.Arrays.equals(results1, results2));
        System.out.println("compiling every call - compile count: " + compileCountEveryCall);
        System.out.println("compiling once       - compile count: " + compileCountOnce);
    }
}

are the results the same: true
compiling every call - compile count: 5
compiling once       - compile count: 1

This measurement is an example of the course’s third class: an ineffective rule break. Both paths reach exactly the same result across all five inputs — which fits and which does not is identical either way. Recompiling breaks the caller’s rule (“a reused pattern should be compiled once”), but the break neither throws an exception nor silently produces a wrong result; correctness is never disturbed. Only the cost is: over five inputs, the compile calls go from one to five. Pattern.compile may look cheap for a small pattern, but compiling is real work turning pattern text into a state machine, redone on every call. The break stays invisible here, since no output line is wrong — only the work spent is excessive.

The course’s shared definitions named three classes: exception (falls immediately, by name), silent (wrong result, no complaint), ineffective (the rule concerns cost, not correctness). Fourteen of fifteen observations fell into the first two; this is the fifteenth, and the course’s only ineffective line — the easiest to miss break of all, since it leaves no visible trace, only a difference in work between two pieces of code that do the same thing.

The Limiting Measurement: Backtracking Step Count Does Not Grow Linearly

• IO28 — The input is wrapped in a sequence that counts its own charAt calls. The same pattern is applied to an input that keeps growing but never matches; the total read count is recorded on each trial. The measure is the step count, not the duration.

// CountingSequence.java — a CharSequence that wraps an input and counts its own charAt calls (helper class, no main)
class CountingSequence implements CharSequence {
    private final String base;
    long readCount = 0;

    CountingSequence(String base) { this.base = base; }

    @Override public int length() { return base.length(); }

    @Override public char charAt(int i) {
        readCount++;
        return base.charAt(i);
    }

    @Override public CharSequence subSequence(int b, int e) { return base.subSequence(b, e); }

    @Override public String toString() { return base; }
}

// BacktrackingSteps.java — in backtracking matching, step count does not grow linearly with input
import java.util.Locale;
import java.util.regex.Pattern;

public class BacktrackingSteps {
    static long countSteps(Pattern p, String input) {
        CountingSequence seq = new CountingSequence(input);
        p.matcher(seq).matches();
        return seq.readCount;
    }

    public static void main(String[] args) {
        Pattern pattern = Pattern.compile("(a+)+b");

        System.out.printf(Locale.ROOT, "%-10s%s%n", "length", "charAt call count");
        long previous = 0;
        for (int length = 10; length <= 25; length += 5) {
            String input = "a".repeat(length);
            long steps = countSteps(pattern, input);
            System.out.printf(Locale.ROOT, "%-10d%d%n", length, steps);
            if (previous > 0) {
                double ratio = (double) steps / previous;
                System.out.printf(Locale.ROOT, "  (growth ratio over previous length: %.1f)%n", ratio);
            }
            previous = steps;
        }
    }
}

length    charAt call count
10        100
15        225
  (growth ratio over previous length: 2.3)
20        400
  (growth ratio over previous length: 1.8)
25        625
  (growth ratio over previous length: 1.6)

The input is made up of the letter a and contains no b; the pattern (a+)+b requires a b at the end no matter what. The match is doomed from the start, but until the engine works this out, the inner group (a+) explores how many ways it can split the input into runs — one letter, two, three — and every time a split fails to find a b, it backs off and tries another split. As input length grows from 10 to 25, two and a half times over, the read count grows from 100 to 625, six and a half times over: 100 at length 10, 225 at 15, 400 at 20, 625 at 25 — each line grows proportionally to the square of the previous one. While input grows linearly (constant step, constant increase), the step count grows quadratically; this is the measured shape of “does not grow linearly with the input.” The measure is not a real stopwatch but a wrapper counting charAt calls — which is why the result comes out exactly the same no matter who runs this document or on which machine.

The (a+)+b pattern itself is a valid, ordinary regular expression; what makes it dangerous is not an escape sequence or some special trick but that a nested quantifier can group the same characters in more than one way — this lesson does not build that geometry, it only counts it.

Summary

• Pattern is a compiled value; matches (exact match) and find (search) carry separate contracts on the same pattern and can give separate results on the same input.
• The greedy quantifier (.*) tries the longest run first and narrows backward; the reluctant quantifier (.*?) tries the shortest run first and extends as needed; they produce separate captures and separate match counts on the same input.
• Recompiling the pattern on every call is the course’s only ineffective rule break: the match result does not change, only the compile call count grows.
• In backtracking matching, the step count may not grow linearly with the input; in the measured example, as the input length grew two and a half times, the step count grew six and a half times, quadratically.
• The step count was measured not with a real stopwatch but with a CharSequence that wraps the input and counts its read calls; the result is therefore machine-independent and reproducible.

Course Wrap-Up

The course opened with one question: the moment you call a library someone else wrote, the decision moves outside your own language — so who gives the promise it makes you? Fifteen lessons put this question to fifteen behaviors, each time getting the answer by running at least two implementations, or two calling forms, side by side. The main claim was confirmed: of fifteen observations, seven were interface guarantees, eight were behavior of only the chosen implementation — most of a behavior list drawn from a single class was not the interface’s promise. The second claim was confirmed too: when the caller’s rule was broken, what fell most often was not an exception but a silently wrong result. The third claim was confirmed along with its limit: the compiler’s protection does not end entirely, but what it protects changes. The single-abstract-method restriction and the effectively final rule still fall at compile time; both are promises about a type’s shape. But none of the caller obligations the course measured showed up at compile time — all of it compiled, and the distinction was left to runtime. The compiler verifies a type’s shape, not that the promise was kept.

Lesson	Behavior measured	Who gives the guarantee	Limiting measurement
Collections Framework	7 of 15 observations are interface guarantees, 8 implementation behavior	interface (7) + implementation (8)	With a 4-element source, PriorityQueue’s traversal order coincidentally matches output order; the 5th element opens the gap
List, Set, and Queue	From a 6-element input, list drops no information, set drops 3, queue drops only positional access	interface (dropped information is the promise’s cost) + caller (remove(1))	LinkedList speaks two interfaces at once; the same remove(1) carries two meanings, and the break is silent
Maps	Three promises (key uniqueness, live view, absent key gives null) hold across three implementations; order and null keys diverge	interface (3 promises) + implementation (order) + caller (equals/hashCode)	The same flawed key is found in a sorted map; the promise used there is compareTo
Iterators and Concurrent Modification	NoSuchElementException on exhaustion is the same across three implementations; response to a change during traversal differs across three	interface (exhaustion) + implementation (response to change)	Iterator.remove does not break the rule; the rule is “no modification from outside the iterator”
Comparison and Sorting	Natural order is the type’s own promise, a comparator a separate object the caller supplies; stability holds across two implementations	interface (stability) + caller (comparator consistency)	An inconsistent comparator never drops an element from the list; the flaw comes from the container using it as a uniqueness decision
Functional Interfaces	The single abstract method is a compile-time promise; the behavioral promise is never checked anywhere	interface (the type’s shape); the behavioral promise belongs to no one	The annotation adds no guarantee, it only catches a violation earlier; an unannotated interface can be functional too
Lambda Expressions	Captured by the local variable’s value, effectively final enforced at compile time; a field carries no such restriction	caller (which form is chosen)	The restriction freezes the variable, not the object it points to; if a captured list changes, the lambda sees the new content
Stream API	3 of ten measurements are guarantees independent of the source, 5 depend on source ordering, 2 are the caller’s rule	interface (3) + source (5) + caller (2)	The sentence “the stream preserves order” is the source’s promise, not the stream’s
Collectors	Four parts (supplier, accumulator, combiner, finisher); the result container’s type is not the interface’s promise	implementation (container type) + caller (duplicate key)	When the caller supplies the container factory, the ambiguity closes; a dropped promise can be taken back
Optional	Unchecked-call count is equal across both signatures (4/4); the gain is visibility in the signature	caller (the check stays at runtime)	The gain disappears in a field and a parameter; of(null) fails immediately, ofNullable(null) does not
Stream-Based Input/Output	write(int)’s low-eight-bits promise and read()’s 0-255-plus--1 promise hold across two implementations; buffering only changes call count	interface (the byte promise) + caller (flushing)	An unflushed buffer leaves data incomplete; the decision to flush belongs to the caller
File System API	Path algebra is the same across two providers; exists and size query the provider’s own storage	interface (path algebra) + implementation (storage) + caller (two steps)	An existence check and an open are separate operations; if the file is deleted in between, the check passes and the open fails
Serialization	The constructor never runs; zero of the two invariants it set up hold automatically on readback	caller (no check without a written readObject)	With the version ID kept fixed and a field renamed, the old record silently passes with a default value
Date and Time API	Instant.equals and ZonedDateTime.isEqual answer “is it the same instant”; LocalDateTime.equals cannot answer it	type (information carried) + caller (comparing without a time zone)	At a daylight saving transition, an overlapping local time maps to two separate instants; the API picks the earlier offset
Regular Expressions	Pattern is a compiled value; matches and find carry separate contracts, greedy and reluctant produce separate captures	interface (Pattern’s contract) + caller (recompiling: the only ineffective line)	In backtracking, step count does not grow linearly with input; the measure is step count, not duration

The Standard Library and Streams closes here. The next course, JVM, Concurrency, and Performance, turns the same questions on a third layer: behind a guarantee there is no longer a single thread but a runtime in which multiple threads reach the same object at the same time — and at that point the answer to “who gives the guarantee” can start to depend on timing.