Fix OC-8127: Appcode hangs on reformatting (endless right shift) +review CR-OC @Anton...
[idea/community.git] / platform / lang-impl / src / com / intellij / formatting / AlignmentImpl.java
1 /*
2  * Copyright 2000-2012 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
17 package com.intellij.formatting;
18
19 import org.jetbrains.annotations.NotNull;
20 import org.jetbrains.annotations.Nullable;
21
22 import java.util.*;
23
24 class AlignmentImpl extends Alignment {
25   private static final List<LeafBlockWrapper> EMPTY = Collections.unmodifiableList(new ArrayList<LeafBlockWrapper>(0));
26   private final boolean myAllowBackwardShift;
27   private final Anchor myAnchor;
28   private Collection<LeafBlockWrapper> myOffsetRespBlocks = EMPTY;
29   private AlignmentImpl myParentAlignment;
30
31   /**
32    * Creates new <code>AlignmentImpl</code> object with <code>'false'</code> as <code>'allows backward shift'</code> argument flag.
33    */
34   AlignmentImpl() {
35     this(false, Anchor.LEFT);
36   }
37
38   /**
39    * Creates new <code>AlignmentImpl</code> object with the given <code>'allows backward shift'</code> argument flag.
40    *
41    * @param allowBackwardShift    flag that indicates if it should be possible to shift former aligned block to right
42    *                              in order to align to subsequent aligned block (see {@link Alignment#createAlignment(boolean, Anchor)})
43    * @param anchor                alignment anchor (see {@link Alignment#createAlignment(boolean, Anchor)})
44    */
45   AlignmentImpl(boolean allowBackwardShift, @NotNull Anchor anchor) {
46     myAllowBackwardShift = allowBackwardShift;
47     myAnchor = anchor;
48   }
49
50   public boolean isAllowBackwardShift() {
51     return myAllowBackwardShift;
52   }
53
54   @NotNull
55   public Anchor getAnchor() {
56     return myAnchor;
57   }
58
59   public String getId() {
60     return String.valueOf(System.identityHashCode(this));
61   }
62
63   public void reset() {
64     if (myOffsetRespBlocks != EMPTY) myOffsetRespBlocks.clear();
65   }
66
67   public void setParent(final Alignment base) {
68     myParentAlignment = (AlignmentImpl)base;
69   }
70
71   /**
72    * Selects target wrapped block by the following algorithm:
73    * <ol>
74    *   <li>
75    *      Filter blocks registered via {@link #setOffsetRespBlock(LeafBlockWrapper)} in order to process only those that start
76    *      before the given block (blocks which start offset is lower than start offset of the given block).
77    *   </li>
78    *   <li>
79    *      Try to find out result from those filtered blocks using the following algorithm:
80    *      <ol>
81    *        <li>
82    *            Use the last block (block which has the greatest start offset) after the block which
83    *            {@link AbstractBlockWrapper#getWhiteSpace() white space} contains line feeds;
84    *        </li>
85    *        <li>
86    *            Use the first block (block with the smallest start offset) if no block can be selected using the rule above;
87    *        </li>
88    *        <li>
89    *            Use the last block (block with the greatest start offset) if no block can be selected using the rules above;
90    *        </li>
91    *      </ol>
92    *   </li>
93    *   <li>
94    *      Delegate the task to the {@link #setParent(Alignment) parent alignment} (if it's registered) if no blocks
95    *      are configured for the current one;
96    *   </li>
97    * </ol>
98    *
99    * @param block     target block to use during blocks filtering
100    * @return          block {@link #setOffsetRespBlock(LeafBlockWrapper) registered} for the current alignment object or
101    *                  {@link #setParent(Alignment) its parent} using the algorithm above if any; <code>null</code> otherwise
102    */
103   @Nullable
104   LeafBlockWrapper getOffsetRespBlockBefore(@Nullable final AbstractBlockWrapper block) {
105     if (!continueOffsetResponsibleBlockRetrieval(block)) {
106       return null;
107     }
108     LeafBlockWrapper result = null;
109     if (myOffsetRespBlocks != EMPTY) {
110       LeafBlockWrapper lastBlockAfterLineFeed = null;
111       LeafBlockWrapper firstAlignedBlock = null;
112       LeafBlockWrapper lastAlignedBlock = null;
113       for (final LeafBlockWrapper current : myOffsetRespBlocks) {
114         if (block == null || current.getStartOffset() < block.getStartOffset()) {
115           if (!onDifferentLines(current, block)) {
116             continue;
117           }
118           if (firstAlignedBlock == null || firstAlignedBlock.getStartOffset() > current.getStartOffset()) {
119             firstAlignedBlock = current;
120           }
121
122           if (lastAlignedBlock == null || lastAlignedBlock.getStartOffset() < current.getStartOffset()) {
123             lastAlignedBlock = current;
124           }
125
126           if (current.getWhiteSpace().containsLineFeeds() &&
127               (lastBlockAfterLineFeed == null || lastBlockAfterLineFeed.getStartOffset() < current.getStartOffset())) {
128             lastBlockAfterLineFeed = current;
129           }
130
131         }
132         //each.remove();
133       }
134       if (lastBlockAfterLineFeed != null) {
135         result = lastBlockAfterLineFeed;
136       }
137       else if (firstAlignedBlock != null) {
138         result = firstAlignedBlock;
139       }
140       else {
141         result = lastAlignedBlock;
142       }
143     }
144     
145     if (result == null && myParentAlignment != null) {
146       return myParentAlignment.getOffsetRespBlockBefore(block);
147     }
148     else {
149       return result;
150     }
151   }
152
153   /**
154    * Registers wrapped block within the current alignment in order to use it for further
155    * {@link #getOffsetRespBlockBefore(AbstractBlockWrapper)} calls processing.
156    *
157    * @param block   wrapped block to register within the current alignment object
158    */
159   void setOffsetRespBlock(final LeafBlockWrapper block) {
160     if (myOffsetRespBlocks == EMPTY) myOffsetRespBlocks = new LinkedHashSet<LeafBlockWrapper>(1);
161     myOffsetRespBlocks.add(block);
162   }
163
164   @Nullable
165   private AbstractBlockWrapper getLeftRespNeighbor(@NotNull AbstractBlockWrapper block) {
166     AbstractBlockWrapper nearLeft = null;
167     int distance = Integer.MAX_VALUE;
168     for (AbstractBlockWrapper offsetBlock : myOffsetRespBlocks) if (offsetBlock != null) {
169       int curDistance = block.getStartOffset() - offsetBlock.getStartOffset();
170       if (curDistance < distance && curDistance > 0) {
171         nearLeft = offsetBlock;
172         distance = curDistance;
173       }
174     }
175     return nearLeft;
176   }
177
178   @NotNull
179   private static AbstractBlockWrapper extendBlockFromStart(@NotNull AbstractBlockWrapper block) {
180     while (true) {
181       AbstractBlockWrapper parent = block.getParent();
182       if (parent != null && parent.getStartOffset() == block.getStartOffset()) {
183         block = parent;
184       }
185       else {
186         return block;
187       }
188     }
189   }
190
191   @NotNull
192   private static AbstractBlockWrapper extendBlockFromEnd(@NotNull AbstractBlockWrapper block) {
193     while (true) {
194       AbstractBlockWrapper parent = block.getParent();
195       if (parent != null && parent.getEndOffset() == block.getEndOffset()) {
196         block = parent;
197       }
198       else {
199         return block;
200       }
201     }
202   }
203
204   private boolean continueOffsetResponsibleBlockRetrieval(@Nullable AbstractBlockWrapper block) {
205     // We don't want to align block that doesn't start new line if it's not configured for 'by columns' alignment.
206     if (!myAllowBackwardShift && block != null && !block.getWhiteSpace().containsLineFeeds()) {
207       return false;
208     }
209
210     if (block != null) {
211       AbstractBlockWrapper prevAlignBlock = getLeftRespNeighbor(block);
212       if (!onDifferentLines(prevAlignBlock, block)) {
213         return false;
214       }
215
216       //blocks are on different lines
217       if (myAllowBackwardShift
218           && myAnchor == Anchor.RIGHT
219           && prevAlignBlock != null
220           && prevAlignBlock.getWhiteSpace().containsLineFeeds() // {prevAlignBlock} starts new indent => can be moved
221       ) {
222         // extend block on position for right align
223         prevAlignBlock = extendBlockFromStart(prevAlignBlock);
224
225         AbstractBlockWrapper current = block;
226         do {
227           if (current.getStartOffset() < prevAlignBlock.getEndOffset()) {
228             return false; //{prevAlignBlock{current}} | {current}{prevAlignBlock}, no new lines
229           }
230           if (current.getWhiteSpace().containsLineFeeds()) {
231             break; // correct new line was found
232           }
233           else {
234             AbstractBlockWrapper prev = current.getPreviousBlock();
235             if (prev != null) {
236                 prev = extendBlockFromEnd(prev);
237             }
238             current = prev;
239           }
240         } while (current != null);
241         if (current == null) {
242           return false; //root block is the top
243         }
244       }
245     }
246     return myParentAlignment == null || myParentAlignment.continueOffsetResponsibleBlockRetrieval(block);
247   }
248
249   private static boolean onDifferentLines(AbstractBlockWrapper block1, AbstractBlockWrapper block2) {
250     if (block1 == null || block2 == null) {
251       return true;
252     }
253
254     AbstractBlockWrapper leftBlock = block1.getStartOffset() <= block2.getStartOffset() ? block1 : block2;
255     AbstractBlockWrapper rightBlock = block1.getStartOffset() > block2.getStartOffset() ? block1 : block2;
256     for (; rightBlock != null && rightBlock.getStartOffset() > leftBlock.getStartOffset(); rightBlock = rightBlock.getPreviousBlock()) {
257       if (rightBlock.getWhiteSpace().containsLineFeeds()) {
258         return true;
259       }
260     }
261     return false;
262   }
263
264   @Override
265   public String toString() {
266     return "Align: " + System.identityHashCode(this);
267   }
268 }