Top-Down, Bottom-Up and Sandwich Integration

Top-down's strength is that the program's main control flow, and something a user can see, exist from the first day. Its weakness is that the modules that do the real computation, the fee calculator and the seat allocation, arrive last, so for most of the integration their results are faked by stubs, and a stub that returns a fixed fee proves nothing about fees.

Bottom-up integration

Bottom-up integration begins with the units at the bottom, which call nothing, and works upwards. A unit whose caller is not yet integrated is exercised by a driver, a "software module used to invoke a module under test and, often, provide test inputs, control and monitor execution, and report test results" (ISO/IEC/IEEE 24765). Units are usually combined in clusters, the units one caller needs, so one driver can stand in for their caller. When the real caller arrives it replaces the driver.

Bottom-up's strength is the mirror of top-down's weakness: the computational units, the fee calculator above all, are tested with real code and real inputs early. Its weakness is that there is no program a user could recognise until the last module, the top, is integrated, and defects in the overall control flow are found last.

Sandwich integration

The two directions can be combined. Top-down integration proceeds from the top, bottom-up integration from the units, and the two meet at a chosen middle layer, which is integrated last and replaces both the stubs above it and the drivers below it. This combination is called sandwich integration, because the middle layer is tested last, between the two.

It is the practical choice on many projects, for the reason Brian Randell gave at the 1968 NATO conference about the two approaches in design: "Clearly the blind application of just one of these approaches would be quite foolish." Teams can work at both ends at once, the user-facing control flow and the computational units are both tested early, and neither needs scaffolding for the whole tree.

Worked example: orders and scaffolding for ExamReg

The program walks ExamReg's tree in each order and counts the scaffolding each needs, using one rule: when a module is integrated, each module it calls that is not yet present needs a stub (one stub per called module); and if the module that calls it is not yet present, that caller needs a driver (one driver per caller, shared by all the units it calls).

TREE = {"ExamReg": ["Login", "Exam Form", "Fee Payment", "Hall Ticket"],
        "Login": ["Password check"],
        "Exam Form": ["Eligibility check", "Paper selection"],
        "Fee Payment": ["Fee calculator", "Gateway adapter"],
        "Hall Ticket": ["Seat allocation", "PDF generator"]}
ROOT = "ExamReg"
parent = {child: p for p, children in TREE.items() for child in children}

def depth_first(m):                      # a module, then each subtree in turn
    return [m] + [x for c in TREE.get(m, []) for x in depth_first(c)]

def breadth_first():                     # level by level
    order, level = [], [ROOT]
    while level:
        order += level
        level = [c for m in level for c in TREE.get(m, [])]
    return order

def bottom_up(m):                        # every subtree before the module that calls it
    return [x for c in TREE.get(m, []) for x in bottom_up(c)] + [m]

def scaffolding(order):
    """Integrate in this order. A called module not yet present needs a STUB (one per module);
    a calling module not yet present needs a DRIVER (one per caller, shared by its callees)."""
    done, stubs, drivers = set(), set(), set()
    for m in order:
        stubs.update(c for c in TREE.get(m, []) if c not in done)
        if m in parent and parent[m] not in done:
            drivers.add(parent[m])
        done.add(m)
    return len(stubs), len(drivers)

leaves = [m for m in depth_first(ROOT) if m not in TREE]
middle = TREE[ROOT]
strategies = {"top-down, depth first": depth_first(ROOT),
              "top-down, breadth first": breadth_first(),
              "bottom-up": bottom_up(ROOT),
              "sandwich (top down to, and bottom up to, the middle layer)": [ROOT] + leaves + middle}
for name, order in strategies.items():
    stubs, drivers = scaffolding(order)
    print(f"{name}: {stubs} stubs, {drivers} drivers")
    line = "  "
    for i, m in enumerate(order):
        piece = m if i == 0 else " > " + m
        if len(line) + len(piece) > 86:              # wrap between modules, never inside a name
            print(line)
            line, piece = "    ", "> " + m
        line += piece
    print(line)

top-down, depth first: 11 stubs, 0 drivers
  ExamReg > Login > Password check > Exam Form > Eligibility check > Paper selection
    > Fee Payment > Fee calculator > Gateway adapter > Hall Ticket > Seat allocation
    > PDF generator
top-down, breadth first: 11 stubs, 0 drivers
  ExamReg > Login > Exam Form > Fee Payment > Hall Ticket > Password check
    > Eligibility check > Paper selection > Fee calculator > Gateway adapter
    > Seat allocation > PDF generator
bottom-up: 0 stubs, 5 drivers
  Password check > Login > Eligibility check > Paper selection > Exam Form
    > Fee calculator > Gateway adapter > Fee Payment > Seat allocation > PDF generator
    > Hall Ticket > ExamReg
sandwich (top down to, and bottom up to, the middle layer): 4 stubs, 4 drivers
  ExamReg > Password check > Eligibility check > Paper selection > Fee calculator
    > Gateway adapter > Seat allocation > PDF generator > Login > Exam Form
    > Fee Payment > Hall Ticket

The counts say what each order costs.

• Top-down needs a stub for every module except the top: 11 of them, and no drivers, whichever way it goes down. Depth first has the login feature working after three steps; breadth first has all four subsystems wired together after five.
• Bottom-up needs no stubs, and only 5 drivers, one for each module that calls others, because one driver can call all the units in its cluster. The fee calculator, the unit that decides money, is tested with its real code at step 6, where top-down depth first reaches it only at step 8, and breadth first at step 9, with a stub standing in for it until then.
• Sandwich needs 4 stubs (for the four subsystems, beneath the real top module) and 4 drivers (standing in for the same four subsystems, above the real units), and the middle layer, integrated last, replaces all eight at once.

Stubs are usually the dearer kind. A driver only has to call a unit and check what comes back; a stub has to imitate what a missing module would have done, well enough for its caller's tests to mean something. A stub for the fee calculator that returns Rs 800 for every student lets the exam form's tests pass without saying anything about fees.

The approaches compared

Choosing an order

The order should follow the risk. If ExamReg's main risk is that students cannot find their way through the portal, top-down shows the flow early; if it is that fees are wrong, bottom-up tests the calculator first with real code. The 2018 ISTQB syllabus adds a practical point: "If integration tests and the integration strategy are planned before components or systems are built, those components or systems can be built in the order required for most efficient testing." And whatever the order, it keeps the rule from the last chapter: integrate a few modules at a time, and test after each.

What it does not mean

Top-down does not mean the top module is untested until the end. It is tested first, with stubs beneath it; what arrives last is the real computation beneath.

Bottom-up does not need a driver for every unit. One driver standing in for a caller can exercise all the units that caller uses.

The scaffolding is not free. Stubs and drivers are code that must be written, reviewed and maintained, and a poor stub can make a test meaningless.

These orders are not only for trees. Real calling structures share modules and have cycles; the same idea, integrating along the calls with stubs or drivers at the edge, still applies.

Quick revision

• Top-down: from the highest-level component downwards; stubs replace modules not yet integrated; depth first (one branch at a time) or breadth first (one level at a time).
• Bottom-up: from the lowest-level components upwards; drivers replace callers not yet integrated; units combined in clusters.
• Sandwich: top-down to a middle layer and bottom-up to it; the middle layer last.
• Big-bang testing: all elements combined at once; faults hard to locate.
• ExamReg: top-down 11 stubs, no drivers; bottom-up no stubs, 5 drivers; sandwich 4 stubs and 4 drivers.
• Top-down shows the control flow early; bottom-up tests real computation early; choose the order by risk.

Test yourself

1. Explain top-down integration, with its depth-first and breadth-first forms. Integration begins with the top module and moves down the calling hierarchy, with stubs standing in for the modules not yet integrated, each replaced by the real module in turn. Depth first completes one branch before the next, so a whole feature works early; breadth first completes one level before going deeper, so the whole control structure works early.

2. Explain bottom-up integration. What does it need instead of stubs? Integration begins with the lowest-level units, which call nothing, combined in clusters and moved up the hierarchy. It needs drivers, which stand in for the callers not yet integrated, calling the units and checking their results; each is replaced when the real caller arrives.

3. Compare top-down and bottom-up integration. Top-down tests the main control flow and gives a visible skeleton early but needs stubs and tests the real computation late. Bottom-up tests the computational units with real code early and needs only drivers, but gives no working program until the end and tests the control flow last.

4. What is sandwich integration and why is it used? A combination in which the upper layers are integrated top-down and the lower layers bottom-up, meeting at a middle layer that is integrated last. It lets teams work at both ends at once, tests both the control flow and the computational units early, and needs scaffolding only around the middle layer.

5. How many stubs does top-down integration of ExamReg need, and why? Eleven: one for every module except the top, because each module is called by a module already integrated before it arrives, so each must first be stood in for by a stub.