2-스택 역연산 Undo/Redo

정의

에디터에서 Ctrl+Z(실행 취소)와 Ctrl+Shift+Z(다시 실행)를 만들고 싶을 때 쓰는 히스토리(편집 기록) 모델이다. 편집 하나하나를 통째로 저장하지 않고, "앞으로 가는 연산"과 "그걸 되돌리는 반대 연산" 한 쌍만 기록해 두면 스택 두 개(취소용·재실행용)를 오가며 상태를 왕복할 수 있다.

정확히 말하면, 2-스택 역연산 undo/redo는 편집을 앞으로 가는 연산(do) 과 뒤로 가는 연산(undo/inverse) 쌍으로 기록하고, undo 스택과 redo 스택 두 개에 그 쌍을 옮겨 담는 히스토리 모델이다. inverse(역연산)는 어떤 편집을 정확히 되돌리는 반대 편집을 뜻한다 — 예: "3번 위치에 'a' 삽입"의 inverse는 "3번 위치의 'a' 삭제". 전체 상태 스냅샷(그 순간 문서 전체를 통째로 복사한 것)을 쌓지 않고 명령(이벤트)의 역으로 상태를 왕복한다. GoF Command 패턴(편집을 실행/취소가 가능한 하나의 "명령 객체"로 다루는 고전 설계 패턴)의 execute / unexecute와 같은 계열이다.

왜 필요한가

문서·캔버스·폼처럼 상태가 크면 편집마다 문서 전체를 복사해 스택에 쌓는 비용이 크고, 구조 공유·메모이제이션(값을 캐싱해 재계산을 피하는 최적화) 계약을 깨뜨리기 쉽다. 모든 편집이 이미 "패치(patch, 상태를 부분적으로 바꾸는 변경 조각)/커맨드"로 표현된다면, 그 단일 apply 관문(모든 편집이 반드시 거쳐 가는 하나의 적용 함수)에서 inverse만 같이 계산하면 undo는 거의 공짜다. 관문이 없으면 undo UI보다 기록 관문을 먼저 만들어야 한다.

동작 원리

1. 사용자 편집이 apply 관문을 지나면 do와 inverse를 동시에 계산한다.
2. 엔트리 { undo: inverse, redo: do }를 undo 스택에 push하고, redo 스택은 비운다(새 분기가 미래를 무효화).
3. Undo: undo 스택에서 pop → undo 적용 → 같은 엔트리를 redo 스택에 push.
4. Redo: redo 스택에서 pop → redo 적용 → 다시 undo 스택에 push.
5. 히스토리 재생 중에는 다시 record하지 않고, trailing node(문서 끝을 항상 빈 문단으로 유지하는 등의 규칙) 같은 자동 normalizer(편집 후 문서를 규칙에 맞게 자동 보정하는 로직)도 끈다. 안 지키면 스택이 자기 자신을 오염하거나, undo 후 정규화가 상태를 바꿔 redo가 어긋난다.

실무 적용

인라인 에디터(세션 히스토리)와 문서 트리 히스토리가 공존할 때는, 하위 keymap(키 입력을 특정 동작에 연결한 매핑)이 처리할 게 없으면 false를 반환해 상위 핸들러로 이벤트를 버블(이벤트가 하위에서 상위로 전파되는 것)시킨다.

트레이드오프

• 스냅샷 스택보다 메모리가 작고 빠르지만, 모든 연산에 올바른 inverse가 필요하다. inverse가 틀리면 조용히 상태가 깨진다.
• 불변식(항상 빈 문단으로 끝남 등)과 히스토리는 상호 배제해야 한다. 불변식을 히스토리 경로에서도 돌리면 redo가 계산된 상태와 어긋난다.

사용하면 안 되는 경우

• 편집이 관문 없이 상태를 직접 돌연변이할 때 — inverse를 신뢰할 수 없다.
• OT/CRDT(여러 사용자의 동시 편집을 충돌 없이 합치는 협업 알고리즘) 등 다중 사용자 동시 편집이 본체인 경우 — 로컬 2-스택만으로는 원격 연산과 합성 규칙이 다르다.
• 상태가 작고 스냅샷이 더 단순한 경우(설정 토글 몇 개) — 스냅샷 스택이 충분하다.

흔한 실수

• undo 경로에서도 record가 켜져 스택이 자기 자신을 다시 쌓는다.
• undo 후 trailing-block 같은 normalizer가 상태를 바꿔 redo가 붕괴한다.
• 새 편집 후에도 redo 스택을 비우지 않아 “미래”가 남는다.
• 인라인 에디터와 문서 히스토리가 같은 키(예: Mod-z)를 두고 서로 덮어쓴다.

관련 개념

• focused-guest-editor — 인라인 guest 세션 히스토리와 문서 host 히스토리를 층으로 나누는 전형적 배경.