Self-adjusting computation is a language-based approach to writing incremental programs that respond dynamically to input changes by maintaining a trace of the computation consistent with the input, thus also updating the output. For monotonic programs, i.e., where localized input changes cause localized changes in the computation, the trace can be repaired efficiently by insertions and deletions. However, non-local input changes can cause major reordering of the trace; in such cases, updating the trace can be asymptotically equal to running from scratch. We show how to eliminate the monotonicity restriction by generalizing the update mechanism to use trace slices, which are partial fragments of the computation that can be reordered with some bookkeeping.