Code Path Analysis

Black-box testing asks whether the code meets its specification; code path analysis is the white-box counterpart — it reads the code's structure and asks: which routes through this logic have my tests actually walked? It is how you find the branch nobody has ever executed, and how you decide, defensibly, how many tests a piece of logic deserves. (For where this sits among the other techniques, see Types of Testing.)

Control Flow Graphs

Every function can be drawn as a control flow graph (CFG): nodes are straight-line chunks of code, edges are the possible jumps between them. Here is a cinema pricing function and its CFG:

Cyclomatic Complexity

McCabe's cyclomatic complexity counts the independent paths through a CFG [1]:

\( M = E - N + 2P \)   (edges − nodes + 2 × connected components), or more practically: number of decisions + 1.

Our function has four decisions (D1–D4), so \( M = 5 \). That number is useful twice over:

• As a test budget: M is the size of a basis path set — a set of paths from which every possible route can be composed. Five decisions ⇒ you need at least five tests for branch-level confidence.
• As a design smell: M grows with nesting and branching. A common rule of thumb treats M > 10 as a refactoring prompt [1] — not because 11 is dangerous, but because the test budget (and human working memory) scales with it.

The Coverage Criteria Ladder

Basis path testing is the practical compromise: cover the M independent paths and you have branch coverage plus the confidence that every decision has been exercised in context.

From Paths to Tests

Choose a baseline path (all decisions false), then flip one decision at a time — each flip is one basis path and one test:

def ticket_price(age, is_member, day):
    price = 10.0
    if age < 16:                 # D1
        price *= 0.5
    elif age >= 65:              # D2
        price *= 0.7
    if is_member:                # D3
        price -= 1.0
    if day == "tuesday":         # D4
        price *= 0.9
    return round(price, 2)

# One test per basis path (M = 5)
def test_adult_baseline():                    # all decisions false
    assert ticket_price(30, False, "monday") == 10.00

def test_child_rate():                        # D1 true
    assert ticket_price(10, False, "monday") == 5.00

def test_senior_rate():                       # D2 true
    assert ticket_price(70, False, "monday") == 7.00

def test_member_discount():                   # D3 true
    assert ticket_price(30, True, "monday") == 9.00

def test_tuesday_offer():                     # D4 true
    assert ticket_price(30, False, "tuesday") == 9.00

double ticket_price(int age, bool is_member, const std::string& day) {
    double price = 10.0;
    if (age < 16) {              // D1
        price *= 0.5;
    } else if (age >= 65) {      // D2
        price *= 0.7;
    }
    if (is_member) {             // D3
        price -= 1.0;
    }
    if (day == "tuesday") {      // D4
        price *= 0.9;
    }
    return std::round(price * 100) / 100.0;
}

// One test per basis path (M = 5)
TEST_CASE("adult baseline")   { CHECK(ticket_price(30, false, "monday") == 10.00); }
TEST_CASE("child rate")       { CHECK(ticket_price(10, false, "monday") == 5.00); }
TEST_CASE("senior rate")      { CHECK(ticket_price(70, false, "monday") == 7.00); }
TEST_CASE("member discount")  { CHECK(ticket_price(30, true,  "monday") == 9.00); }
TEST_CASE("tuesday offer")    { CHECK(ticket_price(30, false, "tuesday") == 9.00); }

double ticketPrice(int age, boolean isMember, String day) {
    double price = 10.0;
    if (age < 16) {              // D1
        price *= 0.5;
    } else if (age >= 65) {      // D2
        price *= 0.7;
    }
    if (isMember) {              // D3
        price -= 1.0;
    }
    if (day.equals("tuesday")) { // D4
        price *= 0.9;
    }
    return Math.round(price * 100) / 100.0;
}

// One test per basis path (M = 5)
@Test void adultBaseline()   { assertEquals(10.00, ticketPrice(30, false, "monday")); }
@Test void childRate()       { assertEquals(5.00,  ticketPrice(10, false, "monday")); }
@Test void seniorRate()      { assertEquals(7.00,  ticketPrice(70, false, "monday")); }
@Test void memberDiscount()  { assertEquals(9.00,  ticketPrice(30, true,  "monday")); }
@Test void tuesdayOffer()    { assertEquals(9.00,  ticketPrice(30, false, "tuesday")); }

double TicketPrice(int age, bool isMember, string day)
{
    var price = 10.0;
    if (age < 16)                // D1
        price *= 0.5;
    else if (age >= 65)          // D2
        price *= 0.7;
    if (isMember)                // D3
        price -= 1.0;
    if (day == "tuesday")        // D4
        price *= 0.9;
    return Math.Round(price, 2);
}

// One test per basis path (M = 5)
[Fact] public void AdultBaseline()  => Assert.Equal(10.00, TicketPrice(30, false, "monday"));
[Fact] public void ChildRate()      => Assert.Equal(5.00,  TicketPrice(10, false, "monday"));
[Fact] public void SeniorRate()     => Assert.Equal(7.00,  TicketPrice(70, false, "monday"));
[Fact] public void MemberDiscount() => Assert.Equal(9.00,  TicketPrice(30, true,  "monday"));
[Fact] public void TuesdayOffer()   => Assert.Equal(9.00,  TicketPrice(30, false, "tuesday"));

def ticket_price(age, member, day)
  price = 10.0
  if age < 16                  # D1
    price *= 0.5
  elsif age >= 65              # D2
    price *= 0.7
  end
  price -= 1.0 if member       # D3
  price *= 0.9 if day == "tuesday" # D4
  price.round(2)
end

# One test per basis path (M = 5)
RSpec.describe "ticket_price" do
  it("charges adults full price")   { expect(ticket_price(30, false, "monday")).to eq(10.00) }
  it("halves the price for children") { expect(ticket_price(10, false, "monday")).to eq(5.00) }
  it("discounts seniors to 70%")    { expect(ticket_price(70, false, "monday")).to eq(7.00) }
  it("takes £1 off for members")    { expect(ticket_price(30, true, "monday")).to eq(9.00) }
  it("applies the Tuesday offer")   { expect(ticket_price(30, false, "tuesday")).to eq(9.00) }
end

Notice what the analysis bought: the test list was derived, not brainstormed, and anyone reviewing it can check completeness against the CFG rather than against your imagination.

Building a Coverage Tool When Your Language Has No Execution Hook

Try it yourself: the live branch coverage tool runs entirely in your browser, or run pat --ir-run self_hosting/tools/coverage_main.patlang <test_file.patlang> for the CLI form that can report on a whole real test suite.

Every tool in the table below assumes something: the language runtime it instruments already has SOME way to observe "this line/branch just executed" — a trace hook (Python's sys.settrace), a JVM instrumentation agent, a debugger API. PatLang, a small language whose interpreter and compiler were both built from scratch this project, has none of that — confirmed by reading the actual interpreter source directly rather than assuming, and finding genuinely nothing to hook into. That absence forced a real decision with a real, generalizable answer: when there's no execution hook, instrument the source itself, not the runtime. This is the same technique Python's coverage.py falls back to in AST mode and what Istanbul/nyc do for JavaScript by default — rewrite the program with small tracking calls inserted, then run the rewritten copy instead of the original.

Wrapping the condition, not the branch body

The first design considered was inserting a tracking statement as the first line of each branch's body, located by source line number. That turned out to need more than the CFG-level design assumes: not just the if keyword's line, but the else keyword's line specifically (not tracked by the original parser), and it breaks on an empty branch body. The design that actually shipped wraps the CONDITION EXPRESSION instead:

# before
if balance > threshold then
  flag_account()
end

# after instrumentation -- semantics identical, cov_check returns its
# argument unchanged
if cov_check(17, balance > threshold) then
  flag_account()
end

cov_check(id, value) records that branch 17 evaluated to value and returns value unchanged, so the program's actual behaviour is completely unaffected — the wrapper is only ever a side effect riding along on a value that was being computed anyway. This needs only the condition (already a single, self-contained expression) and captures both outcomes in one place, regardless of what either branch's body contains, empty or not.

The one real trade-off worth naming

Source instrumentation means regenerating the ENTIRE program from its parsed structure — not a line-preserving patch, a full rebuild using the language's own canonical formatting. The instrumented copy is semantically identical to the original but not byte-identical to it, and it exists only to be run once to collect coverage, never as a program's real, ongoing source. That's a real cost (a language needs an actual unparser — reconstructing valid syntax from the parsed tree, not just a debug pretty-printer for humans to read) but it's a bounded, one-time cost, considerably smaller than building an entire new interpreter execution mode.

What this actually caught, on a real test suite

Run against a real hex-grid simulation's own 23-check test suite, the resulting tool reported 71 of 150 tracked branches covered (47%) — not a toy number, a genuine SimpleCov-style table, one row per function:

Function                                  Branches    Coverage
--------                                  --------    --------
rts_apply_order                           7/7         100%
rts_step                                  0/1         0%
rts_advance_unit                          9/12        75%
...
--------                                  --------    --------
TOTAL                                     71/150      47%

rts_step at 0% is the interesting row, not a bug in the tool: the test suite's own helper always called it with an empty list of pending orders, so the one branch inside rts_step that processes a NEW order was never exercised by that suite at all — even though the function it would have called, rts_apply_order, was itself tested thoroughly, just never through rts_step. That's exactly the kind of gap a branch coverage report is supposed to surface: not "is this logic ever tested," but "is this specific PATH into that logic ever tested."

Two real, small bugs came out of actually running the finished tool against real data, worth noting because neither was a coverage-specific mistake — both are general lessons that showed up here: a percentage that printed as 142/3% instead of 47%, because integer division that doesn't divide evenly returned an exact fraction rather than a truncated number in PatLang's numeric model (fixed by explicitly flooring the result — the exact "check your language's actual division semantics, don't assume" lesson from the testing/risk companion page); and a process-spawning call that silently received zero real arguments because a list was passed where the underlying function expected individual arguments — caught only by writing a minimal, isolated reproduction of that one call and inspecting what it actually returned, not by reasoning about the API from its own doc comment.

Tooling — and the Limit of Coverage

One warning belongs in bold: coverage measures execution, not verification. A test that calls ticket_price and asserts nothing scores 100% while checking nothing. The tool that closes that gap is mutation testing.

References

1. McCabe, T.J. (1976). "A Complexity Measure." IEEE Transactions on Software Engineering, SE-2(4), 308–320. https://doi.org/10.1109/TSE.1976.233837
2. Watson, A.H. & McCabe, T.J. (1996). Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric. NIST Special Publication 500-235. https://www.mccabe.com/pdf/mccabe-nist235r.pdf
3. Ammann, P. & Offutt, J. (2016). Introduction to Software Testing (2nd ed.). Cambridge University Press. https://cs.gmu.edu/~offutt/softwaretest/