Physical Hierarchy

This chapter explains how physical dependencies among components form a hierarchy that affects testability, maintainability, reuse, and development cost.

4.1 A Metaphor for Software Testing

Complex software systems should be tested at multiple levels, like complex physical products.

A well-designed system is tested:

1. In isolation.
2. Through partially integrated subsystems.
3. As a fully integrated product.

Principle:
Low-level components should be tested directly rather than relying only on tests of the final system.

Component
    ↓
Subsystem
    ↓
Integrated System

Testing only at the highest-level interface makes it difficult to identify which lower-level component is responsible for a failure.

4.2 A Complex Subsystem

A subsystem can hide a large implementation behind a very small interface.

The chapter uses a point-to-point router as an example.

The router receives:

• An enclosing region.
• A set of obstructions.
• A start point.
• An end point.
• A path width.

It determines whether a rectilinear path exists and may return a shortest path.

The important design point is:

Large Internal Implementation
        ↓
Small Logical Interface

A component can therefore be easy to use while internally containing substantial complexity.

4.3 The Difficulty in Testing "Good" Interfaces

Good Interface:
A small, well-defined, easy-to-understand interface that hides implementation complexity.

Such interfaces are desirable for clients but can make high-level testing difficult.

Regression Testing

Regression Testing:
Comparing the output produced for a fixed input against previously established expected results to verify that behavior remains correct across versions.

Fixed Input
    ↓
Run Program
    ↓
Compare with Expected Result

Regression testing becomes difficult when:

• Multiple correct outputs are possible.
• Heuristic algorithms are used.
• Results are not deterministic.
• Asynchronous behavior produces different valid executions.

A high-level test can also miss defects in internal components when those defects merely degrade output quality rather than causing complete failure.

4.4 Design for Testability

Design for Testability (DFT):
Designing a system so that its internal functionality can be tested efficiently and directly.

The goal is to avoid relying exclusively on the top-level interface for testing.

Principle:
With respect to testing, a software class is analogous to a real-world instance.

If a class implementation is correct, all instances of that class share that implementation.

Principle:
Distributing testing throughout the design hierarchy can be more cost-effective than testing only from the highest-level interface.

System-Level Testing Only
        ↓
Hard to isolate internal behavior

Hierarchical Testing
        ↓
Directly test lower-level functionality

A good physical hierarchy allows internal components to be tested without adding test-only operations to the public interface of the final product.

4.5 Testing in Isolation

Isolation Testing:
Testing an individual component or subsystem independently of the rest of the system.

Principle:
Independent testing reduces part of the risk associated with software integration.

Principle:
Testing a component in isolation is an effective way to ensure reliability.

Isolation testing helps detect:

• Boundary-condition errors.
• Memory-management errors.
• Low-level implementation bugs.
• Portability problems.
• Functionality not exercised by a particular client.

A reusable component should not depend on one specific application to exercise all of its behavior.

Big Bang Integration

Big Bang Approach:
Waiting until most or all components are complete before integrating and testing the system.

This makes it harder to distinguish:

• Integration errors.
• Specification errors.
• Ordinary coding defects.

Testing components independently allows coding defects to be removed before integration.

Tests as Part of the Component

The testing effort can be grouped with the component itself.

Component
├── Source
├── Interface
├── Tests
└── Documentation

Well-written component tests also provide examples of correct usage.

Isolation testing should still be justified by cost and benefit.

Creating separate components solely for testing very small implementation details can increase physical complexity unnecessarily.

4.6 Acyclic Physical Dependencies

Directed Acyclic Graph (DAG):
A directed dependency graph containing no cycles.

An acyclic component dependency graph provides a natural testing order.

Example:

c3
↓
c2
↓
c1

Testing can proceed:

c1
↓
c2
↓
c3

Each component is tested after the components it depends on have already been verified.

Principle:
Acyclic physical dependencies make systems easier to test.

A cyclic dependency has the form:

c1 → c2
↑     ↓
└─────┘

In this case, neither component can be tested or reused independently of the other.

4.7 Level Numbers

Level Number:
A non-negative integer used to classify a component according to its physical dependencies.

Level numbers provide an objective testing order for acyclic dependency graphs.

4.7.1 The Origin of Level Numbers

The concept comes from levelized digital circuit simulation.

A node can be evaluated only after all nodes on which it depends have been evaluated.

Principle:
Every directed acyclic graph can be assigned unique level numbers; a graph containing cycles cannot.

Levelizable:
A physical dependency graph that can be assigned level numbers.

Acyclic Graph
    ↓
Levelizable

Cyclic Graph
    ↓
Not Levelizable

4.7.2 Using Level Numbers in Software

The book defines component levels as follows.

Level 0:
A component external to the current package.

Level 1:
A component with no local physical dependencies.

Level N:
A component that depends on a component at level N - 1, but on no component at a higher level.

Equivalent rule:

level(component)
=
1 + maximum level of local dependencies

External dependencies are treated as level 0.

Leaf Component:
A level-1 component that depends only on external or compiler-supplied components.

Leaf components are testable in isolation.

Level of a Component:
The length of the longest path from the component through the local dependency graph to external or compiler-supplied components.

Example:

Level 4: A
         ↓
Level 3: B
         ↓
Level 2: C
         ↓
Level 1: D
         ↓
Level 0: External Library

Principle:
In most real-world situations, large designs must be levelizable if they are to be tested effectively.

Level numbers help determine:

• Testing order.
• Reuse requirements.
• Dependency depth.
• Overall physical structure.

4.8 Hierarchical and Incremental Testing

Hierarchical Testing

Hierarchical Testing:
Testing individual components at each level of the physical hierarchy.

Principle:
Hierarchical testing requires a separate test driver for every component.

component_a
└── a.t.c

component_b
└── b.t.c

A separate test driver verifies that a component can operate using only the dependencies shown in its dependency graph.

This also helps detect:

• Missing definitions.
• Hidden dependencies.
• Violations of physical design rules.
• Non-levelizable structures.

Incremental Testing

Incremental Testing:
Testing only the functionality implemented directly within the component under test.

Lower-level components are presumed to have already been tested.

Lower-Level Component
    ↓ already verified

Current Component
    ↓
Test only added functionality

Principle:
Testing only the functionality directly implemented within a component keeps test complexity proportional to the complexity of that component.

This avoids repeatedly testing functionality already verified at lower levels.

White-Box Testing

White-Box Testing:
Testing a component using knowledge of its internal implementation.

White-box testing is useful for:

• Internal code coverage.
• Logic errors.
• Memory errors.
• Implementation-specific behavior.

It verifies that the implementation works as intended.

Black-Box Testing

Black-Box Testing:
Testing a component solely from its specification and public behavior, without relying on implementation details.

It verifies that the component satisfies its requirements.

White-Box Testing
└── Implementation

Black-Box Testing
└── Specification

Both techniques are complementary.

White-box testing asks:

Did we implement it correctly?

Black-box testing asks:

Did we implement the correct behavior?

4.9 Testing a Complex Subsystem

A complex subsystem should be factored into a levelizable hierarchy of independently testable components.

High-Level Component
        ↓
Intermediate Components
        ↓
Low-Level Components

Lower-level components should provide:

• Predictable behavior.
• Well-defined interfaces.
• Manageable functionality.
• Independent tests.

The highest-level component should primarily coordinate lower-level functionality rather than contain the entire implementation itself.

This reduces the testing burden at the top-level interface.

Principle:
Hierarchical physical implementations of complex subsystems can be more reliable and less expensive to test than monolithic alternatives.

4.10 Testability versus Testing

Testability:
The property of a design that allows its behavior to be verified effectively.

Tested:
The state in which a product has demonstrated conformance to its specification.

Testability
└── Design Property

Testing
└── Development Activity

Tested
└── Verified State

Testability must be designed into a system before systematic testing becomes necessary.

Principle:
Thorough regression testing is expensive but essential; the appropriate time to create thorough regression tests depends on the stability of the subsystem.

Early in development, interfaces may still change frequently.

As components mature and interfaces stabilize, more thorough regression suites become cost-effective.

4.11 Cyclic Physical Dependencies

Cyclic Physical Dependency:
A dependency relationship in which a path leads from a component back to itself.

Example:

A DependsOn B
B DependsOn A

Principle:
Cyclic physical dependencies inhibit understanding, testing, and reuse.

Guideline:
Avoid cyclic physical dependencies among components.

When two components are mutually dependent, possible responses include:

1. Repackage them to remove the cycle.
2. Merge them into one component.
3. Treat them as one physical unit.

The preferred solution is to eliminate the cycle when possible.

Closely related logical entities with intimate access needs may belong naturally in the same component.

Mutually Dependent Components
        ↓
Repackage / Merge / Restructure

4.12 Cumulative Component Dependency

Cumulative Component Dependency (CCD):
The sum, over all components in a subsystem, of the number of components required to test each component incrementally.

For each component:

Component Dependency Count
=
Component itself
+
All components it DependsOn

Then:

CCD
=
Sum of all component dependency counts

CCD approximates the cumulative cost of incremental linking and testing.

Cyclic System

For a fully interdependent system with N components:

CCD ≈ N²

Every component may require all N components to test.

Balanced Tree-Like System

For a balanced binary dependency tree:

CCD = O(N log N)

The book gives:

CCD_balanced(N)
=
(N + 1) log2(N + 1) - N

for the theoretical balanced binary-tree case.

Principle:
Acyclic physical dependencies can dramatically reduce link-time costs associated with developing, maintaining, and testing large systems.

CCD Meaning

Lower CCD generally means:

• Less physical coupling.
• Lower incremental link cost.
• Lower disk-space cost for test executables.
• Better opportunities for isolated testing and reuse.

CCD is primarily useful for comparing alternative physical organizations of the same or similar subsystem.

4.13 Physical Design Quality

Physical design quality is strongly related to the amount and shape of physical coupling.

The book describes a continuum:

Cyclic
  ↓
Vertical
  ↓
Tree-Like
  ↓
Horizontal

Cyclic Design

High coupling
Poor independent reuse
Poor testability
High CCD

Vertical Design

Vertical Design:
A levelizable hierarchy in which components form a long dependency chain.

A
↓
B
↓
C
↓
D

A vertical design is acyclic but highly coupled.

For N components, the maximum CCD for an acyclic vertical chain is:

CCD = N(N + 1) / 2

Tree-Like Design

A tree-like design distributes dependencies across branches.

       A
      / \
     B   C
    / \ / \
   D  E F  G

It usually provides better:

• Parallel development.
• Incremental testing.
• Reuse.
• Maintenance.

Horizontal Design

Horizontal Design:
A subsystem whose components are independent of one another.

A   B   C   D

A horizontal system has minimal coupling.

Each component can be:

• Tested independently.
• Reused independently.
• Modified with minimal propagation.

Average Component Dependency

Average Component Dependency (ACD):
The ratio of CCD to the number of components.

ACD = CCD / N

ACD represents the average number of components involved when incrementally testing a component.

Normalized Cumulative Component Dependency

Normalized Cumulative Component Dependency (NCCD):
The ratio of a subsystem's CCD to the CCD of a theoretical balanced tree of the same size.

NCCD
=
CCD(subsystem)
/
CCD_balanced(N)

Interpretation:

NCCD < 1
└── More horizontal / loosely coupled

NCCD ≈ 1
└── Tree-like coupling

NCCD > 1
└── More vertical / tightly coupled

NCCD >> 1
└── Possible significant cyclic coupling

NCCD characterizes coupling but is not by itself a measure of overall design quality.

A design can achieve a lower NCCD simply by introducing unnecessary components or removing valid reuse.

Principle:
The primary purpose of CCD is to quantify changes in overall coupling caused by changes to an architecture.

Principle:
Minimizing CCD for a given set of components is a design goal.

The important objective is not a specific numerical CCD value, but keeping physical dependency lower than necessary.

4.14 Key Concepts

Physical Hierarchy
        ↓
DependsOn Graph

Testing Strategy
├── Isolation Testing
├── Hierarchical Testing
├── Incremental Testing
├── White-Box Testing
└── Black-Box Testing

Acyclic Dependencies
        ↓
DAG
        ↓
Levelizable
        ↓
Level Numbers
        ↓
Ordered Testing

Levels
├── Level 0 = External Component
├── Level 1 = No Local Dependencies
└── Level N = 1 + Max Dependency Level

Cycles
        ↓
Poor Testing
Poor Understanding
Poor Reuse

Physical Coupling Metrics
├── CCD
├── ACD
└── NCCD

Dependency Shapes
├── Cyclic
├── Vertical
├── Tree-Like
└── Horizontal

Design Goal
        ↓
Acyclic
Levelizable
Low CCD
Independently Testable Components