46106ad4b5afb102699ee9158be0838fe94b1154
[idea/community.git] / platform / platform-impl / src / com / intellij / openapi / command / impl / UndoRedoStacksHolder.java
1 /*
2  * Copyright 2000-2015 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.openapi.command.impl;
17
18 import com.intellij.openapi.command.undo.DocumentReference;
19 import com.intellij.openapi.command.undo.DocumentReferenceManager;
20 import com.intellij.openapi.editor.Document;
21 import com.intellij.openapi.util.Key;
22 import com.intellij.openapi.util.UserDataHolder;
23 import com.intellij.openapi.vfs.VirtualFile;
24 import com.intellij.util.containers.HashMap;
25 import com.intellij.util.containers.WeakList;
26 import gnu.trove.THashSet;
27 import org.jetbrains.annotations.NotNull;
28 import org.jetbrains.annotations.TestOnly;
29
30 import java.util.*;
31
32 class UndoRedoStacksHolder {
33   private final Key<LinkedList<UndoableGroup>> STACK_IN_DOCUMENT_KEY = Key.create("STACK_IN_DOCUMENT_KEY");
34
35   private final boolean myUndo;
36
37   private final LinkedList<UndoableGroup> myGlobalStack = new LinkedList<>();
38   // strongly reference local files for which we can undo file removal
39   // document without files and nonlocal files are stored without strong reference
40   private final Map<DocumentReference, LinkedList<UndoableGroup>> myDocumentStacks = new HashMap<>();
41   private final List<Document> myDocumentsWithStacks = new WeakList<>();
42   private final List<VirtualFile> myNonlocalVirtualFilesWithStacks = new WeakList<>();
43
44   public UndoRedoStacksHolder(boolean isUndo) {
45     myUndo = isUndo;
46   }
47
48   @NotNull
49   LinkedList<UndoableGroup> getStack(@NotNull DocumentReference r) {
50     return r.getFile() != null ? doGetStackForFile(r) : doGetStackForDocument(r);
51   }
52
53   @NotNull
54   private LinkedList<UndoableGroup> doGetStackForFile(@NotNull DocumentReference r) {
55     LinkedList<UndoableGroup> result;
56     VirtualFile file = r.getFile();
57
58     if (!file.isInLocalFileSystem()) {
59       result = addWeaklyTrackedEmptyStack(file, myNonlocalVirtualFilesWithStacks);
60     }
61     else {
62       result = myDocumentStacks.get(r);
63       if (result == null) {
64         result = new LinkedList<>();
65         myDocumentStacks.put(r, result);
66       }
67     }
68
69     return result;
70   }
71
72   @NotNull
73   private LinkedList<UndoableGroup> doGetStackForDocument(@NotNull DocumentReference r) {
74     // If document is not associated with file, we have to store its stack in document
75     // itself to avoid memory leaks caused by holding stacks of all documents, ever created, here.
76     // And to know, what documents do exist now, we have to maintain weak reference list of them.
77
78     return addWeaklyTrackedEmptyStack(r.getDocument(), myDocumentsWithStacks);
79   }
80
81   @NotNull
82   private <T extends UserDataHolder> LinkedList<UndoableGroup> addWeaklyTrackedEmptyStack(@NotNull T holder, @NotNull List<T> allHolders) {
83     LinkedList<UndoableGroup> result = holder.getUserData(STACK_IN_DOCUMENT_KEY);
84     if (result == null) {
85       holder.putUserData(STACK_IN_DOCUMENT_KEY, result = new LinkedList<>());
86       allHolders.add(holder);
87     }
88     return result;
89   }
90
91   boolean canBeUndoneOrRedone(@NotNull Collection<DocumentReference> refs) {
92     if (refs.isEmpty()) return !myGlobalStack.isEmpty() && myGlobalStack.getLast().isValid();
93     for (DocumentReference each : refs) {
94       if (!getStack(each).isEmpty() && getStack(each).getLast().isValid()) return true;
95     }
96     return false;
97   }
98
99   @NotNull
100   UndoableGroup getLastAction(@NotNull Collection<DocumentReference> refs) {
101     if (refs.isEmpty()) return myGlobalStack.getLast();
102
103     UndoableGroup mostRecentAction = null;
104     int mostRecentDocTimestamp = myUndo ? -1 : Integer.MAX_VALUE;
105
106     for (DocumentReference each : refs) {
107       LinkedList<UndoableGroup> stack = getStack(each);
108       // the stack for a document can be empty in case of compound editors with several documents
109       if (stack.isEmpty()) continue;
110       UndoableGroup lastAction = stack.getLast();
111
112       int timestamp = lastAction.getCommandTimestamp();
113       if (myUndo ? timestamp > mostRecentDocTimestamp : timestamp < mostRecentDocTimestamp) {
114         mostRecentAction = lastAction;
115         mostRecentDocTimestamp = timestamp;
116       }
117     }
118
119     // result must not be null
120     return mostRecentAction;
121   }
122
123   @NotNull
124   Set<DocumentReference> collectClashingActions(@NotNull UndoableGroup group) {
125     Set<DocumentReference> result = new THashSet<>();
126
127     for (DocumentReference each : group.getAffectedDocuments()) {
128       UndoableGroup last = getStack(each).getLast();
129       if (last != group) {
130         result.addAll(last.getAffectedDocuments());
131       }
132     }
133
134     if (group.isGlobal()) {
135       UndoableGroup last = myGlobalStack.getLast();
136       if (last != group) {
137         result.addAll(last.getAffectedDocuments());
138       }
139     }
140
141     return result;
142   }
143
144   void addToStacks(@NotNull UndoableGroup group) {
145     for (LinkedList<UndoableGroup> each : getAffectedStacks(group)) {
146       doAddToStack(each, group, each == myGlobalStack ? UndoManagerImpl.getGlobalUndoLimit() : UndoManagerImpl.getDocumentUndoLimit());
147     }
148   }
149
150   private void doAddToStack(@NotNull LinkedList<UndoableGroup> stack, @NotNull UndoableGroup group, int limit) {
151     if (!group.isUndoable() && stack.isEmpty()) return;
152
153     stack.add(group);
154     while (stack.size() > limit) {
155       clearStacksFrom(stack.getFirst());
156     }
157   }
158
159   void removeFromStacks(@NotNull UndoableGroup group) {
160     for (LinkedList<UndoableGroup> each : getAffectedStacks(group)) {
161       assert each.getLast() == group;
162       each.removeLast();
163     }
164   }
165
166   void clearStacks(boolean clearGlobal, @NotNull Set<DocumentReference> refs) {
167     for (LinkedList<UndoableGroup> each : getAffectedStacks(clearGlobal, refs)) {
168       while(!each.isEmpty()) {
169         clearStacksFrom(each.getLast());
170       }
171     }
172
173     Set<DocumentReference> stacksToDrop = new THashSet<>();
174     for (Map.Entry<DocumentReference, LinkedList<UndoableGroup>> each : myDocumentStacks.entrySet()) {
175       if (each.getValue().isEmpty()) stacksToDrop.add(each.getKey());
176     }
177     for (DocumentReference each : stacksToDrop) {
178       myDocumentStacks.remove(each);
179     }
180
181
182     cleanWeaklyTrackedEmptyStacks(myDocumentsWithStacks);
183     cleanWeaklyTrackedEmptyStacks(myNonlocalVirtualFilesWithStacks);
184   }
185
186   private <T extends UserDataHolder> void cleanWeaklyTrackedEmptyStacks(@NotNull List<T> stackHolders) {
187     Set<T> holdersToDrop = new THashSet<>();
188     for (T holder : stackHolders) {
189       List<UndoableGroup> stack = holder.getUserData(STACK_IN_DOCUMENT_KEY);
190       if (stack != null && stack.isEmpty()) {
191         holder.putUserData(STACK_IN_DOCUMENT_KEY, null);
192         holdersToDrop.add(holder);
193       }
194     }
195     stackHolders.removeAll(holdersToDrop);
196   }
197
198   private void clearStacksFrom(@NotNull UndoableGroup from) {
199     for (LinkedList<UndoableGroup> each : getAffectedStacks(from)) {
200       int pos = each.indexOf(from);
201       if (pos == -1) continue;
202
203       if (pos > 0) {
204         int top = each.size() - pos;
205         clearStacksFrom(each.get(pos - 1));
206         assert each.size() == top && each.indexOf(from) == 0;
207       }
208       each.removeFirst();
209     }
210   }
211
212   @NotNull
213   private List<LinkedList<UndoableGroup>> getAffectedStacks(@NotNull UndoableGroup group) {
214     return getAffectedStacks(group.isGlobal(), group.getAffectedDocuments());
215   }
216
217   @NotNull
218   private List<LinkedList<UndoableGroup>> getAffectedStacks(boolean global, @NotNull Collection<DocumentReference> refs) {
219     List<LinkedList<UndoableGroup>> result = new ArrayList<>(refs.size() + 1);
220     if (global) result.add(myGlobalStack);
221     for (DocumentReference each : refs) {
222       result.add(getStack(each));
223     }
224     return result;
225   }
226
227   @TestOnly
228   void clearAllStacksInTests() {
229     clearStacks(true, getAffectedDocuments());
230     myGlobalStack.clear();
231     myDocumentStacks.clear();
232     myDocumentsWithStacks.clear();
233     myNonlocalVirtualFilesWithStacks.clear();
234   }
235
236   void collectAllAffectedDocuments(@NotNull Collection<DocumentReference> result) {
237     for (UndoableGroup each : myGlobalStack) {
238       result.addAll(each.getAffectedDocuments());
239     }
240     collectLocalAffectedDocuments(result);
241   }
242
243   private void collectLocalAffectedDocuments(@NotNull Collection<DocumentReference> result) {
244     result.addAll(myDocumentStacks.keySet());
245     DocumentReferenceManager documentReferenceManager = DocumentReferenceManager.getInstance();
246
247     for (Document each : myDocumentsWithStacks) {
248       result.add(documentReferenceManager.create(each));
249     }
250     for (VirtualFile each : myNonlocalVirtualFilesWithStacks) {
251       result.add(documentReferenceManager.create(each));
252     }
253   }
254
255   @NotNull
256   private Set<DocumentReference> getAffectedDocuments() {
257     Set<DocumentReference> result = new THashSet<>();
258     collectAllAffectedDocuments(result);
259     return result;
260   }
261
262   int getLastCommandTimestamp(@NotNull DocumentReference r) {
263     LinkedList<UndoableGroup> stack = getStack(r);
264     if (stack.isEmpty()) return 0;
265     return Math.max(stack.getFirst().getCommandTimestamp(), stack.getLast().getCommandTimestamp());
266   }
267
268   void invalidateActionsFor(@NotNull DocumentReference ref) {
269     for (List<UndoableGroup> eachStack : getAffectedStacks(true, Collections.singleton(ref))) {
270       for (UndoableGroup eachGroup : eachStack) {
271         eachGroup.invalidateActionsFor(ref);
272       }
273     }
274   }
275 }