Blog

The problem with automatic fixes

Applying a fix is harder than finding the bug. Four questions explain safety, collisions, convergence, and trust in an automatic fixer.

On this page
  1. Safe, unsafe, and the large grey middle
  2. Where to cut, and what happens when edits collide
  3. Making it stop
  4. Trusting the fix, and where it came from
  5. One file is not a transaction
  6. What alint can promise
  7. References

"Just fix it" is the feature everyone wants from a linter, and the one most likely to go wrong.

Finding a problem is read-only. Applying the fix writes to your files, and a careless write can delete the wrong thing, change what the code does without saying so, or fight another fix and rewrite the same line over and over until a built-in limit cuts it off. Mature fixers carry the scars: ESLint documents circular fixes that undo one another, Prettier treats non-idempotence as a bug, and rustfmt has fixed the same class of failure.

None of those failures is new. Compiler and refactoring research tell us why meaning is hard to preserve. Text editors teach us what happens when ranges move or collide. Rewrite theory explains loops. Security engineering asks who gets to act with your authority. A modern fixer turns those ideas into rules it can test and explain.

Four questions separate a found problem from a fix safe enough to apply on its own:

  • Does it change meaning?
  • Where exactly does it cut?
  • Will it ever stop?
  • Who gave it permission to run?

Each question has a long history. We will take them in order, using alint, a general linter, as the running example. The alint details below are based on v0.17.0.

Safe, unsafe, and the large grey middle

Some fixes are low-risk when their scope is clear. Adding a final newline to ordinary source text is a good example. The same byte change can matter in a signed artifact, a byte-exact fixture, or an enclosing format. Trimming trailing whitespace looks cosmetic until the file is Markdown, where two trailing spaces can request a hard line break. Deleting a file or rewriting source by regex raises the cost of a targeting mistake further. A useful safety label depends on the target and on what it would cost to be wrong.

For a language-aware rewrite, observational equivalence is still the ideal. Two fragments of code are observationally equivalent when no surrounding context can tell them apart: substitute one for the other anywhere, and the program's observable behavior is unchanged. James Morris gave the idea its formal shape in 1968[1], and it is the bar two older disciplines work under. A refactoring is behavior-preserving when its preconditions hold (Opdyke, 1992)[2]. An optimizing compiler may rewrite code under the as-if rule: observable behavior must stay the same. Repository fixes are broader: they also create files, change data and permissions, and mutate Git state. The equivalence lens is useful whenever a fixer claims a source rewrite preserves behavior.

Equivalence cannot be decided in general. Rice's theorem (1953)[3] rules out a general decider for non-trivial semantic properties of programs. A real fixer has to work with narrower preconditions and a hand-picked classification. That classification can still be wrong. Ruff says Safe fixes are intended to preserve runtime behavior and asks users to report a Safe fix that breaks code. The label is a promise from the tool, not a proof.

The grey middle is where a rewrite is right about the value and still not equivalent. Ruff's safe-versus-unsafe split is this idea in a shipping tool, and its stock example lives in that gap: rewriting list(x)[0] to next(iter(x)) returns the same first element and runs faster, but on an empty input the first raises IndexError and the second raises StopIteration. The raised exception is observable, so a caller that writes except IndexError is a distinguishing context: it separates the two fragments, which means they are not equivalent, which means the rewrite is unsafe.

One distinguishing context makes a rewrite unsafe Does the rewrite change meaning? THE REWRITE list(x)[0] fix next(iter(x)) Equivalent = no context C[ ] can tell them apart. Any ordinary context x = [10, 20] same result list(x)[0] -> 10 next(iter(x)) -> 10 A distinguishing context empty input, and the caller writes except IndexError list(x)[0] IndexError caught next(iter(x)) StopIteration escapes One distinguishing context is enough: the rewrite is Unsafe. General equivalence is undecidable (Rice, 1953). A fixer uses narrow preconditions and a curated Safe set. Safe is an engineering commitment, not a proof.
list(x)[0] and next(iter(x)) return the same value for a non-empty input, but a caller that catches IndexError distinguishes them when the input is empty. One counterexample makes this particular rewrite Unsafe. More generally, a Safe classification is a scoped engineering promise, not a proof of arbitrary program equivalence.

alint puts fixes into four tiers. Safe is eligible for a bare alint fix. Unsafe waits for --unsafe-fixes. A Suggestion carries a proposed change, but alint will not write it automatically. ESLint makes a similar distinction between fixes and suggestions. Never is an internal state used for provenance. It is neither applied nor offered. These tiers govern what the engine may do under the configured policy. They do not certify meaning preservation for every possible file.

alint's four fix-applicability states Safe, unsafe, and what a bare fix writes Safe config.py - timeout = 30 ·· + timeout = 30 Scoped to ordinary Python source. A bare alint fix may apply it. alint fix writes to here Unsafe first.py - return list(xs)[0] + return next(iter(xs)) Same value, until the list is empty: IndexError becomes StopIteration, so except IndexError stops catching. alint fix --unsafe-fixes reaches here Suggestion Proposed, never auto-applied two rewrites Never Internal state, not offered provenance
Applicability is a policy about what may happen automatically. A narrowly scoped whitespace fix can be Safe while a rewrite that changes an exception remains Unsafe. Suggestion and Never are both non-applying states, but only Suggestion is offered to the user.

The same reasoning sorts the harder cases. Reindenting a file from tabs to spaces preserves behavior in many formats, until the many bites: a bare fix aimed at a Makefile recipe would turn its leading tab into spaces, and make rejects the file with a missing separator error. alint therefore defaults reindentation, deletion, and regex replacement to Unsafe. A user can override a tier for a narrowly scoped rule. The tier is a policy about target, intent, reversibility, and the cost of a mistake, not a timeless fact about an edit in isolation.

Where to cut, and what happens when edits collide

A located fix is an edit: replace the bytes from offset m to n with this text. Recovering a small sequence of edits between two strings is the classical edit-script and diff problem, developed through edit distance (Levenshtein, 1965)[4], the string-to-string correction algorithm (Wagner and Fischer, 1974)[5], and Myers's diff algorithm (1986)[6]. alint does not infer a shortest script from two files, though. A rule proposes an operation, and the engine decides whether and how that operation may run.

alint fixes more than byte ranges. Some fixes transform a whole file, with several transforms composed in memory. Others create, remove, or rename paths, change permissions, touch Git, or run a command. Those operations need different safeguards. For now, consider the range case, where one stale coordinate is enough to corrupt a file.

One range is easy. The trouble starts with more than one, because a byte offset is not a stable address: apply one edit and every offset after it shifts, so the next edit, computed against the old text, now points at the wrong place. Collaborative editors face a richer version of this hazard. Operational transformation (Ellis and Gibbs, 1989)[7] transforms positions against concurrent edits. Conflict-free replicated data types (Shapiro and colleagues, 2011)[8] can use stable identities plus deterministic conflict rules. alint uses neither system, but their central lesson applies: coordinates only make sense relative to the state that produced them.

A byte offset belongs to the snapshot that produced it A byte offset is not a stable address ADDRESSING BY POSITION (OFFSET) A stored edit says: change the character at offset 4. h e l l o 0 1 2 3 4 offset 4 is o, the char you meant insert X at the front, every later offset shifts +1 X h e l l o 0 1 2 3 4 5 offset 4 now lands on l, the wrong character (o moved to offset 5) ADDRESSING BY STABLE IDENTITY A stored edit says: change the character with id 5. h e l l o 1 2 3 4 5 id 5 is o, the char you meant insert X with a fresh id 9, every existing id is unchanged X h e l l o 9 1 2 3 4 5 id 5 is still o, the edit still lands the target survives this insert Positions require a shared snapshot or transformation against intervening edits (OT, 1989). Stable identities plus conflict rules underpin CRDT designs (Shapiro et al., 2011).
A byte offset is valid only for the snapshot that produced it. Insert one character and an old offset can land on the wrong byte. Collaborative systems solve a broader problem with transformed positions or stable identities. alint uses neither OT nor a CRDT. It captures the bytes behind each range, selects compatible ranges against that snapshot, and splices them back-to-front.

alint takes the simpler route a one-shot fixer can afford: every located range addresses captured file bytes. It sorts proposals by (start, end, rule index, violation index), then accepts the first eligible, in-bounds edit for each compatible span. A later overlapping edit, or one in an already-used isolation group, is skipped. A tier-gated suggestion reserves no range. This produces a deterministic compatible subset, not necessarily the largest or globally best set.

The accepted ranges are then spliced from the highest offset down, so a later edit cannot move the bytes addressed by an earlier one. Verification is deliberately narrower than "prove the fix correct." Structured set_value, remove_value, and matching replacements can carry a parse-and-query postcondition. If that check fails against the composed bytes, the edit becomes a suggestion and the survivors are recomposed. Other operations carry no semantic verifier. A normalizer's transform is its specification, while paths, metadata, Git, and commands have their own checks.

Reverse splicing preserves captured offsets Splicing located edits: order changes everything TWO EDITS FOR ONE LINE a rule gives each length a px unit w = 1 , h = 2 P byte 2 1 -> 1px Q byte 7 2 -> 2px Each edit is a byte-range replacement. The order the fixer applies them in matters. naive low offset first w = 1 p x ,h=2 P ok Q: byte 7 wrong byte P added 2 bytes, so Q's offset 7 now lands on h, not on 2. alint high offset first w = 1 p x ,h=2px Q is last, so nothing shifts before P runs. Both land correctly. Overlap: deterministic first eligible edit wins A, kept B overlaps A, skip Structured edits can carry a verifier Re-parse and re-run the declared query. Postcondition fails: demote, then recompose. Every range addresses captured bytes. Other operation classes use different checks.
Both ranges address the same captured bytes. Applying the higher offset first keeps the lower offset valid. alint selects a deterministic compatible subset rather than claiming a maximum set. It splices that subset from the back. Structured edits can carry a parse-and-query verifier. Other edits have narrower, operation-specific guarantees.

Making it stop

The simplest way a fixer never stops is a fix whose own output still matches the rule that triggered it. Say a rule flags the token foo and its fix rewrites each match, but the replacement still contains foo. The first pass produces foofoo. The next produces foofoofoo. The file gains another foo on every pass and never settles. Nobody writes that fix on purpose, but it is easy to hit by accident. A rename from foo to foo_bar with a plain substring replacement loops for the same reason. That is the termination question, and a fixer cannot avoid it.

A fixer can be viewed as a rewrite system: rules replace matches with something new, possibly over several passes. Two classical properties sharpen the risks. A system terminates if no rewrite sequence runs forever. It is confluent, the Church-Rosser property (1936)[9], if diverging rewrites can always rejoin, so order does not change the final result. A terminating, confluent system has a unique normal form where no rewrite applies. A formatter often wants an even more practical property, idempotence: one pass already reaches a stable result, so a second pass does nothing.

That looping fix has no fixed point. There is nothing to converge to. Termination of an arbitrary rewrite system is undecidable, by reduction to the halting problem (Turing, 1936)[10], so a general fixer cannot promise it in advance. A restricted system can sometimes prove termination with a measure that falls on every step. Without such a proof, the engine needs a pass limit. Ruff sets MAX_ITERATIONS = 100, while ESLint sets MAX_AUTOFIX_PASSES to 10. The exact number matters less than refusing to call an unbounded loop success.

Termination and confluence answer different questions Rewriting: does it stop, and is the answer unique? DOES IT STOP? (TERMINATION) terminates m = 3 m = 2 m = 1 m = 0 normal form diverges foo foofoo foofoofoo ... A falling measure forces a stop. A growing one never reaches a fixed point. IS THE ANSWER UNIQUE? (CONFLUENCE) 1 + 2 + 3 left first right first 3 + 3 1 + 5 6 Confluence makes this normal form unique (Church-Rosser, 1936). alint does not promise confluence or a unique normal form. It promises deterministic order and a bounded pass budget.
Termination and confluence answer different questions. One asks whether rewriting stops. The other asks whether order changes the answer. alint claims neither property for arbitrary configs. It fixes the order, repeats while work applies, and enforces a pass limit.

alint attacks the loop from both sides. First it catches the most obvious self-loop: the regex replace fixer drops a proposed replacement if those replacement bytes still match the rule's source pattern. That blocks foo to foo_bar, but it cannot prove that adjacent splices will not form a new match or that two different rules will not undo each other.

The backstop is bounded iteration. A real fix evaluates the current tree, applies one deterministic pass, then re-walks after any progress. If a pass applies nothing, the engine has settled under the active tier and scope and reports whatever remains. The tree may still contain Unsafe fixes, Suggestions, unfixable findings, skipped writes, or errors. In that case the command can exit 1. After ten applying passes, alint makes one non-mutating confirmation pass. If work is still available, it reports the applying rules, marks the run non-convergent, and exits 2. An idempotent fixer helps, but several fixers can still interact or undo one another.

alint bounds its fix loop and reports residual work Fixes run in passes, until a pass changes nothing A FIX THAT RE-CREATES ITS OWN TARGET naive foo 1 foofoo 2 foofoofoo 3 ... exit 2 never settles alint foo re-match? replacement still matches /foo/ so the edit is dropped foo settled, residual remains WHAT THE ENGINE OBSERVES Pass 1 3 applied Pass 2 1 applied Pass 3 0 applied, settled The finding count may rise or fall. Applied operations control the loop. THE LOOP re-walk the tree run one deterministic fix pass did this pass change anything? yes: next pass no report residuals after pass 10 confirm, maybe exit 2
The self-match guard blocks one obvious regex loop but can leave the original finding unresolved. A real run re-walks after progress and stops when a pass applies nothing, preserving any residual findings. If ten passes all apply work, a final no-write pass checks whether the last pass happened to settle. Work still available means non-convergence and exit 2.

With the same inputs, alint resolves proposals in the same order. That still does not produce one canonical answer. The result may contain findings, and a command invoked by a rule may bring its own sources of variation.

Trusting the fix, and where it came from

The first three questions show up in every auto-fixer. The fourth is sharper in alint because its configs compose. A root file can extend a bundled ruleset, a local file, or a SHA-256-pinned URL. A monorepo can also opt into nested configs. The rule editing your files may have been written somewhere else and fetched a moment ago. Even checking is not always passive. A trusted root kind: command rule may run a diagnostic process, so process authority matters before the fix command enters the picture.

Security engineering has names for this problem. Saltzer and Schroeder's principles of least privilege and fail-safe defaults say to grant the minimum authority and deny by default[11]. Capability systems tie authority to what a component holds (Dennis and Van Horn, 1966)[12]. Hardy's confused deputy is a privileged program tricked into using its authority for someone else[13]. A linter applying a downloaded fix with your filesystem and shell faces the same risk. alint is not a formal object-capability system, but it borrows these ideas.

Two things decide how much authority a fix receives: what it can do and where it came from. Root .alint.yml and .alint.d/ drop-ins have the broadest authority. Bundled rulesets, local-path extensions, and allowlisted remote URLs may retain their content-editing tiers, but they still cannot introduce process-spawning behavior. Content-changing fixes from untrusted remote or nested sources are capped at Suggestion. Any spawning behavior from those sources is rejected while the config loads. Fixed protective operations, such as stripping an invisible Trojan-Source control character, keep their declared tier.

That provenance has to survive composition. Otherwise an untrusted rule could borrow a trusted template, or a later trusted field could complete an untrusted template. alint carries a private untrusted-source bit through rule merges and template expansion, then caps the finished fixer. A later field cannot erase the history of an earlier source. Listing a URL under trusted_extends: restores content authority. It never grants process authority.

Fix authority depends on operation and provenance A fix can arrive from a ruleset you did not write Rules compose from root, local, bundled, remote, and nested sources. What an effective fixer may do depends on all of its provenance. Root config trusted Untrusted / nested untrusted Spawns a process run a command, git untrack Runs Refused curl x.sh | sh Injects chosen content replace, file_create, sort Applied Suggestion unless trusted_extends Purely protective strip a Trojan-Source char Honored Honored Provenance survives merges and templates. Content trust never grants spawn.
Root configuration holds the broadest authority. Untrusted remote and nested sources cannot spawn and can only suggest aimed content changes. Fixed protective operations keep their tier. Bundled, local, or allowlisted sources may regain content authority, but never process authority. A monotonic provenance bit keeps those limits intact through merges and templates.

One file is not a transaction

One boundary remains: what happens after the engine decides to write. For a content rewrite, alint creates a uniquely named temporary file beside the target. It writes the new bytes, copies the original permissions, calls fsync, and renames the temporary file over the target. If that sequence fails, the original is not left half-written. When the target is a symlink, alint updates the file it points to without replacing the link itself.

That guarantee stops at one file. There is no repository-wide transaction covering content writes, renames, permission changes, Git operations, and commands. If file A and file B succeed before file C fails, A and B remain changed. alint records the failure and returns a nonzero status when appropriate. It does not roll the earlier work back. Version control is the recovery mechanism, which is why it still matters to know your starting state and inspect the final diff.

Per-file atomic writes protect individual files but do not roll back a partially changed repository The commit boundary is one file Each content write avoids torn output. The repository is not one transaction. FILE A a.ymloriginal .a.yml.alint-fix.*write · permissions · fsync rename committedA changed atomically FILE B b.tomloriginal rename committedB changed atomically FILE C c.jsonoriginal write failedC original remains reported partial successA = new · B = new · C = originalno repository rollback, so inspect the report and Git diff Atomic file replacement prevents truncation. It does not create a multi-file transaction.
A failed content write leaves that file's original intact, but earlier successful files stay changed. This is the difference between atomic persistence for one file and transactional all-or-nothing behavior for a repository.

What alint can promise

None of these safeguards proves that a repository is correct. They keep smaller failures under control. Safety tiers decide which changes need consent. Snapshot ranges keep accepted edits aimed at the bytes that produced them. A verifier can reject a bad structured edit, and the pass limit catches a configuration that keeps rewriting. Provenance keeps inherited rules within their authority.

So what does a bare alint fix promise? Every operation must clear the active safety tier, source policy, path scope, and conflict rules. A structured edit that carries a verifier has to pass it. Content transforms for one file are composed before that file is replaced. Anything unresolved, skipped, or failed stays in the report. The pass loop is bounded, and inherited config cannot smuggle in process authority.

The promise stops well short of "the repository is now correct." A successful edit can leave other findings behind, and the command can still exit 1. A later file can fail after earlier files have changed. alint fix --dry-run and alint fix --diff touch nothing, but they show only the first composed pass. They cannot predict later cascades, an I/O failure, a loop that reaches the pass limit, or the side effects of a command. A general linter also cannot know whether the result compiles or passes the repository's tests.

In practice, the workflow is ordinary:

Terminal window
git status --short       # know the starting state
alint fix --diff .       # inspect the first composed pass
alint fix .              # apply eligible fixes to a bounded fixpoint
alint check .            # inspect what remains
git diff --check         # inspect what actually changed
# run the repository's formatter, tests, and build

Git gives you a way back. Tests cover behavior a general linter cannot infer. alint's report tells you what changed and what did not. That is the practical version of "just fix it": keep the automatic part bounded, visible, and easy to review.

The fixing guide covers the tiers and per-rule overrides. For implementation details, see the alint-core engine and located-edit pipeline, including the located-edit tests and bounded overlap proof.

References

  1. J. H. Morris Jr. (1968). Lambda-Calculus Models of Programming Languages. PhD thesis, MIT. dspace.mit.edu
  2. W. F. Opdyke (1992). Refactoring Object-Oriented Frameworks. PhD thesis, University of Illinois at Urbana-Champaign. PDF
  3. H. G. Rice (1953). Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society 74(2), 358-366. doi:10.1090/S0002-9947-1953-0053041-6
  4. V. I. Levenshtein (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady 10(8), 707-710 (English translation of the 1965 Russian original). mathnet.ru
  5. R. A. Wagner, M. J. Fischer (1974). The string-to-string correction problem. Journal of the ACM 21(1), 168-173. doi:10.1145/321796.321811
  6. E. W. Myers (1986). An O(ND) difference algorithm and its variations. Algorithmica 1(2), 251-266. doi:10.1007/BF01840446
  7. C. A. Ellis, S. J. Gibbs (1989). Concurrency control in groupware systems. Proceedings of ACM SIGMOD 1989, 399-407. doi:10.1145/67544.66963
  8. M. Shapiro, N. Preguica, C. Baquero, M. Zawirski (2011). Conflict-free replicated data types. Proceedings of SSS 2011, 386-400. doi:10.1007/978-3-642-24550-3_29
  9. A. Church, J. B. Rosser (1936). Some properties of conversion. Transactions of the American Mathematical Society 39(3), 472-482. doi:10.1090/S0002-9947-1936-1501858-0
  10. A. M. Turing (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society s2-42(1), 230-265. doi:10.1112/plms/s2-42.1.230
  11. J. H. Saltzer, M. D. Schroeder (1975). The protection of information in computer systems. Proceedings of the IEEE 63(9), 1278-1308. doi:10.1109/PROC.1975.9939
  12. J. B. Dennis, E. C. Van Horn (1966). Programming semantics for multiprogrammed computations. Communications of the ACM 9(3), 143-155. doi:10.1145/365230.365252
  13. N. Hardy (1988). The confused deputy. ACM SIGOPS Operating Systems Review 22(4), 36-38. doi:10.1145/54289.871709

Comments