The Equivalence Relation That Refactoring Depends On

A refactoring is a change to code that preserves observable behavior. The definition is repeated so often that the operative clause stops being read. Behavior is not a property a program has on its own; it is a relation between a program and a set of observations that someone has decided to make. Widen or narrow that set and the same edit becomes either a refactoring or a change in function. Nearly every disagreement about whether a change “counts” is a disagreement about the observation set, conducted without either side naming it.

Behavior is a projection, not a whole

Consider everything a running program does: every memory write, every branch taken, every system call, every intermediate value in a register. That is the full trace, and essentially none of it is visible to anything outside the process. What is visible is a much smaller projection: return values, thrown exceptions, writes to files and sockets, the order of those writes, and whether the process terminates.

Fix a set of observation functions $O$. Two implementations $P$ and $Q$ are equivalent under $O$ when, for every input $i$, $O(P, i) = O(Q, i)$. The definition is deliberately relative. There is no absolute answer to “does this change behavior,” only an answer conditioned on the $O$ that was chosen.

That relativity produces the first useful consequence: refactorings are not equally strong. Each one preserves some observations and quietly alters others.

Transformation	Preserved	Altered observably
Rename a local variable	Return values, effects, order, exceptions	Debug symbol names; stack traces under some debuggers
Extract a function	Return values, effects, order, exceptions	Stack depth, stack traces, profiler attribution
Inline a function	Return values, effects, order, exceptions	Same set, in the opposite direction
Replace conditional with dispatch	Results for all inputs	Instruction count, allocation pattern, inlining decisions
Introduce a parameter object	Results for all inputs	Number of allocations, object identity

Renaming a local is the weakest interesting case: it preserves every observation except one that reads names, and name-reading is rare enough that people treat the rename as free. Extract function preserves the externally visible contract but inserts a frame, so anything that inspects the call stack, including a crash reporter, observes a difference. The table is not a list of caveats. It is the actual content of the claim “behavior is preserved.”

Undecidability forces the relation into a sample

Rice’s theorem states that for any non-trivial semantic property of programs, no algorithm decides whether an arbitrary program has that property. Program equivalence is such a property: pick a program $Q$, and “behaves like $Q$” is non-trivial and semantic. Therefore no tool can decide, in general, whether a diff preserves behavior. Any tool that appears to do so is operating on a restricted language, a restricted observation set, or both.

Since the full relation cannot be decided, it is replaced by a finite sample. A test suite enumerates a set of inputs and compares observed outputs. That substitution is what makes refactoring tractable at all, and it is also the entire source of risk: the suite is a sample of $O$ drawn from inputs somebody thought of, and it says nothing about inputs nobody thought of.

Three mechanisms substitute for the missing proof, and they cover different regions.

A test suite samples observations over chosen inputs. It catches concrete disagreements on inputs it contains and is silent everywhere else. Its coverage is a property of the input distribution, not of the code.

Static analysis and type checking reason about all executions, but only about coarse properties. A type checker can establish that no call has the wrong arity and that a null cannot reach a dereference. It cannot establish that a function still returns the same number, because that is a value-level property and undecidable in the same way.

Human review of the diff reasons about the cases nobody enumerated. It is the only mechanism that can notice “the new path skips the retry when the response is a 429,” because that case is absent from both the suite and the type system. Review capacity scales inversely with diff size, which is the real argument for small changes, independent of any tooling preference.

The observations the standard definition excludes

Four categories sit outside the usual observation set, and each exclusion is a decision with consequences.

Cost. A program that returns identical answers in ten times the elapsed time is equivalent under the definition. This is not an oversight. If cost were part of behavior, almost no structural change would qualify, because every added indirection costs something: an extra frame, an extra load, an extra branch. Excluding cost keeps refactoring possible, and it means performance work is a different activity with a different verification method. Combining the two in one commit destroys the property that made the commit reviewable, since a reviewer can no longer tell which part was supposed to be inert.

Interleaving. For concurrent code, the set of possible interleavings is part of behavior and no sequential observation captures it. Two implementations can agree on every test and differ under a schedule that no test produces. Refactoring a lock into a lock-free structure is therefore never behavior-preserving in the strict sense, whatever the tests say.

Resource lifetime. A change that closes a descriptor one statement later preserves return values and changes the peak descriptor count. Under a low limit, that is a visible difference.

Ordering that leaks. Field order in a serialized struct, key order in JSON, iteration order of a hash table. Changing a hash function reorders iteration; if anything downstream depends on that order, the reordering is a behavior change that the type system will not flag and a test may not cover.

def observations(fn, inputs):
    """Project a callable onto the observations a test can actually compare."""
    out = []
    for args in inputs:
        try:
            out.append(("return", fn(*args)))
        except Exception as exc:                  # exceptions are observations too
            out.append(("raise", type(exc).__name__, str(exc)))
    return out

def total_loop(xs):
    t = 0
    for x in xs:
        t += x
    return t

def total_builtin(xs):
    return sum(xs)

cases = [((),), ((1,),), ((1, 2, 3),), ((-5, 5),)]   # each entry is an arg tuple
assert observations(total_loop, cases) == observations(total_builtin, cases)

The projection above records return values and exception identity. It does not record elapsed time, allocation count, or stack depth, so two functions can pass it while differing in all three. That is the definition working as specified, not a flaw in the comparison.

Fixing the observation set before the edit

The operational rule that follows is short. State the observation set in the same place the change is described, before the change is made, and state it as a claim that can be checked. “Same return values and same sequence of writes for all inputs currently covered by the suite” is a claim. “No behavior change” is not, because it names no set.

The label then does real work during review. A reviewer told that behavior is preserved reads the diff for structure and for accidental effects. A reviewer told that behavior changed reads it for correctness against an intended new contract. Mixing the two labels in one change forces the reviewer to do both jobs on the same diff and usually results in neither being done.

Two failure modes are worth naming. The first is overstating the set: claiming equivalence over observations the change actually alters, which is how a refactoring commit acquires a latent bug that surfaces later as a mystery. The second is understating it, which is safer but wasteful, because it turns every mechanical edit into a negotiation about whether the edit was allowed.

The same reasoning scales up. A characterization suite is a deliberate widening of the observation set for code that has none, as described in Characterization Tests as a Refactoring Safety Net. A repository-wide rewrite is the same relation applied to thousands of call sites at once, which is where the sampling problem becomes severe. And the boundary cases above are the subject of What Behavior-Preserving Change Cannot Preserve, where the excluded observations turn out to be the ones that matter most once the code is carrying real traffic.