potential undo freezes: compact map to avoid iteration over empty buckets
[idea/community.git] / platform / platform-impl / src / com / intellij / openapi / command / impl / UndoRedoStacksHolder.java
1 /*
2  * Copyright 2000-2017 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.WeakList;
25 import gnu.trove.THashMap;
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 THashMap<DocumentReference, LinkedList<UndoableGroup>> myDocumentStacks = new THashMap<>();
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     myDocumentStacks.entrySet().removeIf(each -> each.getValue().isEmpty());
174     myDocumentStacks.compact(); // make sure the following entrySet iteration will not go over empty buckets.
175
176     cleanWeaklyTrackedEmptyStacks(myDocumentsWithStacks);
177     cleanWeaklyTrackedEmptyStacks(myNonlocalVirtualFilesWithStacks);
178   }
179
180   private <T extends UserDataHolder> void cleanWeaklyTrackedEmptyStacks(@NotNull List<T> stackHolders) {
181     Set<T> holdersToDrop = new THashSet<>();
182     for (T holder : stackHolders) {
183       List<UndoableGroup> stack = holder.getUserData(STACK_IN_DOCUMENT_KEY);
184       if (stack != null && stack.isEmpty()) {
185         holder.putUserData(STACK_IN_DOCUMENT_KEY, null);
186         holdersToDrop.add(holder);
187       }
188     }
189     stackHolders.removeAll(holdersToDrop);
190   }
191
192   private void clearStacksFrom(@NotNull UndoableGroup from) {
193     for (LinkedList<UndoableGroup> each : getAffectedStacks(from)) {
194       int pos = each.indexOf(from);
195       if (pos == -1) continue;
196
197       if (pos > 0) {
198         int top = each.size() - pos;
199         clearStacksFrom(each.get(pos - 1));
200         assert each.size() == top && each.indexOf(from) == 0;
201       }
202       each.removeFirst();
203     }
204   }
205
206   @NotNull
207   private List<LinkedList<UndoableGroup>> getAffectedStacks(@NotNull UndoableGroup group) {
208     return getAffectedStacks(group.isGlobal(), group.getAffectedDocuments());
209   }
210
211   @NotNull
212   private List<LinkedList<UndoableGroup>> getAffectedStacks(boolean global, @NotNull Collection<DocumentReference> refs) {
213     List<LinkedList<UndoableGroup>> result = new ArrayList<>(refs.size() + 1);
214     if (global) result.add(myGlobalStack);
215     for (DocumentReference each : refs) {
216       result.add(getStack(each));
217     }
218     return result;
219   }
220
221   @TestOnly
222   void clearAllStacksInTests() {
223     clearStacks(true, getAffectedDocuments());
224     myGlobalStack.clear();
225     myDocumentStacks.clear();
226     myDocumentsWithStacks.clear();
227     myNonlocalVirtualFilesWithStacks.clear();
228   }
229
230   void collectAllAffectedDocuments(@NotNull Collection<DocumentReference> result) {
231     for (UndoableGroup each : myGlobalStack) {
232       result.addAll(each.getAffectedDocuments());
233     }
234     collectLocalAffectedDocuments(result);
235   }
236
237   private void collectLocalAffectedDocuments(@NotNull Collection<DocumentReference> result) {
238     result.addAll(myDocumentStacks.keySet());
239     DocumentReferenceManager documentReferenceManager = DocumentReferenceManager.getInstance();
240
241     for (Document each : myDocumentsWithStacks) {
242       result.add(documentReferenceManager.create(each));
243     }
244     for (VirtualFile each : myNonlocalVirtualFilesWithStacks) {
245       result.add(documentReferenceManager.create(each));
246     }
247   }
248
249   @NotNull
250   private Set<DocumentReference> getAffectedDocuments() {
251     Set<DocumentReference> result = new THashSet<>();
252     collectAllAffectedDocuments(result);
253     return result;
254   }
255
256   int getLastCommandTimestamp(@NotNull DocumentReference r) {
257     LinkedList<UndoableGroup> stack = getStack(r);
258     if (stack.isEmpty()) return 0;
259     return Math.max(stack.getFirst().getCommandTimestamp(), stack.getLast().getCommandTimestamp());
260   }
261
262   void invalidateActionsFor(@NotNull DocumentReference ref) {
263     for (List<UndoableGroup> eachStack : getAffectedStacks(true, Collections.singleton(ref))) {
264       for (UndoableGroup eachGroup : eachStack) {
265         eachGroup.invalidateActionsFor(ref);
266       }
267     }
268   }
269 }