Expandable indent storing additional block, which indent is used as min indent marker...
[idea/community.git] / platform / lang-impl / src / com / intellij / formatting / FormatProcessor.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
17 package com.intellij.formatting;
18
19 import com.intellij.lang.ASTNode;
20 import com.intellij.lang.Language;
21 import com.intellij.openapi.diagnostic.Logger;
22 import com.intellij.openapi.editor.Document;
23 import com.intellij.openapi.editor.Editor;
24 import com.intellij.openapi.editor.EditorFactory;
25 import com.intellij.openapi.editor.TextChange;
26 import com.intellij.openapi.editor.ex.DocumentEx;
27 import com.intellij.openapi.editor.impl.BulkChangesMerger;
28 import com.intellij.openapi.editor.impl.TextChangeImpl;
29 import com.intellij.openapi.fileTypes.StdFileTypes;
30 import com.intellij.openapi.util.Condition;
31 import com.intellij.openapi.util.TextRange;
32 import com.intellij.psi.PsiElement;
33 import com.intellij.psi.PsiFile;
34 import com.intellij.psi.codeStyle.CodeStyleSettings;
35 import com.intellij.psi.codeStyle.CommonCodeStyleSettings;
36 import com.intellij.util.containers.ContainerUtil;
37 import com.intellij.util.containers.MultiMap;
38 import com.intellij.util.ui.UIUtil;
39 import gnu.trove.TIntObjectHashMap;
40 import org.jetbrains.annotations.NotNull;
41 import org.jetbrains.annotations.Nullable;
42
43 import java.util.*;
44
45 public class FormatProcessor {
46
47   private static final Map<Alignment.Anchor, BlockAlignmentProcessor> ALIGNMENT_PROCESSORS =
48     new EnumMap<Alignment.Anchor, BlockAlignmentProcessor>(Alignment.Anchor.class);
49   static {
50     ALIGNMENT_PROCESSORS.put(Alignment.Anchor.LEFT, new LeftEdgeAlignmentProcessor());
51     ALIGNMENT_PROCESSORS.put(Alignment.Anchor.RIGHT, new RightEdgeAlignmentProcessor());
52   }
53
54   /**
55    * There is a possible case that formatting introduced big number of changes to the underlying document. That number may be
56    * big enough for that their subsequent appliance is much slower than direct replacing of the whole document text.
57    * <p/>
58    * Current constant holds minimum number of changes that should trigger such <code>'replace whole text'</code> optimization.
59    */
60   private static final int BULK_REPLACE_OPTIMIZATION_CRITERIA = 3000;
61
62   private static final Logger LOG = Logger.getInstance("#com.intellij.formatting.FormatProcessor");
63   private Set<Alignment> myAlignmentsInsideRangesToModify = null;
64   private boolean myReformatContext;
65
66   private LeafBlockWrapper myCurrentBlock;
67
68   private Map<AbstractBlockWrapper, Block>    myInfos;
69   private CompositeBlockWrapper               myRootBlockWrapper;
70   private TIntObjectHashMap<LeafBlockWrapper> myTextRangeToWrapper;
71
72   private final CommonCodeStyleSettings.IndentOptions myDefaultIndentOption;
73   private final CodeStyleSettings                     mySettings;
74   private final Document                              myDocument;
75
76   /**
77    * Remembers mappings between backward-shifted aligned block and blocks that cause that shift in order to detect
78    * infinite cycles that may occur when, for example following alignment is specified:
79    * <p/>
80    * <pre>
81    *     int i1     = 1;
82    *     int i2, i3 = 2;
83    * </pre>
84    * <p/>
85    * There is a possible case that <code>'i1'</code>, <code>'i2'</code> and <code>'i3'</code> blocks re-use
86    * the same alignment, hence, <code>'i1'</code> is shifted to right during <code>'i3'</code> processing but
87    * that causes <code>'i2'</code> to be shifted right as wll because it's aligned to <code>'i1'</code> that
88    * increases offset of <code>'i3'</code> that, in turn, causes backward shift of <code>'i1'</code> etc.
89    * <p/>
90    * This map remembers such backward shifts in order to be able to break such infinite cycles.
91    */
92   private final Map<LeafBlockWrapper, Set<LeafBlockWrapper>> myBackwardShiftedAlignedBlocks
93     = new HashMap<LeafBlockWrapper, Set<LeafBlockWrapper>>();
94
95   private final Map<AbstractBlockWrapper, Set<AbstractBlockWrapper>> myAlignmentMappings
96     = new HashMap<AbstractBlockWrapper, Set<AbstractBlockWrapper>>();
97
98   /**
99    * There is a possible case that we detect a 'cycled alignment' rules (see {@link #myBackwardShiftedAlignedBlocks}). We want
100    * just to skip processing for such alignments then.
101    * <p/>
102    * This container holds 'bad alignment' objects that should not be processed.
103    */
104   private final Set<Alignment> myAlignmentsToSkip = new HashSet<Alignment>();
105
106   private LeafBlockWrapper myWrapCandidate           = null;
107   private LeafBlockWrapper myFirstWrappedBlockOnLine = null;
108
109   private LeafBlockWrapper myFirstTokenBlock;
110   private LeafBlockWrapper myLastTokenBlock;
111
112   /**
113    * Formatter provides a notion of {@link DependantSpacingImpl dependent spacing}, i.e. spacing that insist on line feed if target
114    * dependent region contains line feed.
115    * <p/>
116    * Example:
117    * <pre>
118    *       int[] data = {1, 2, 3};
119    * </pre>
120    * We want to keep that in one line if possible but place curly braces on separate lines if the width is not enough:
121    * <pre>
122    *      int[] data = {    | &lt; right margin
123    *          1, 2, 3       |
124    *      }                 |
125    * </pre>
126    * There is a possible case that particular block has dependent spacing property that targets region that lays beyond the
127    * current block. E.g. consider example above - <code>'1'</code> block has dependent spacing that targets the whole
128    * <code>'{1, 2, 3}'</code> block. So, it's not possible to answer whether line feed should be used during processing block
129    * <code>'1'</code>.
130    * <p/>
131    * We store such 'forward dependencies' at the current collection where the key is the range of the target 'dependent forward
132    * region' and value is dependent spacing object.
133    * <p/>
134    * Every time we detect that formatter changes 'has line feeds' status of such dependent region, we
135    * {@link DependantSpacingImpl#setDependentRegionLinefeedStatusChanged() mark} the dependent spacing as changed and schedule one more
136    * formatting iteration.
137    */
138   private SortedMap<TextRange, DependantSpacingImpl> myPreviousDependencies =
139     new TreeMap<TextRange, DependantSpacingImpl>(new Comparator<TextRange>() {
140       @Override
141       public int compare(final TextRange o1, final TextRange o2) {
142         int offsetsDelta = o1.getEndOffset() - o2.getEndOffset();
143
144         if (offsetsDelta == 0) {
145           offsetsDelta = o2.getStartOffset() - o1.getStartOffset();     // starting earlier is greater
146         }
147         return offsetsDelta;
148       }
149     });
150
151   private final HashSet<WhiteSpace> myAlignAgain = new HashSet<WhiteSpace>();
152   @NotNull
153   private final FormattingProgressCallback myProgressCallback;
154
155   private WhiteSpace                      myLastWhiteSpace;
156   private boolean                         myDisposed;
157   private CommonCodeStyleSettings.IndentOptions myJavaIndentOptions;
158   private final int myRightMargin;
159
160   @NotNull
161   private State myCurrentState;
162   private MultiMap<ExpandableIndent, AbstractBlockWrapper> myExpandableIndents;
163   private Map<Block, AbstractBlockWrapper> myExpandableIndentsMinOffsetBlocksToWrappers;
164
165   public FormatProcessor(final FormattingDocumentModel docModel,
166                          Block rootBlock,
167                          CodeStyleSettings settings,
168                          CommonCodeStyleSettings.IndentOptions indentOptions,
169                          @Nullable FormatTextRanges affectedRanges,
170                          @NotNull FormattingProgressCallback progressCallback)
171   {
172     this(docModel, rootBlock, new FormatOptions(settings, indentOptions, affectedRanges, false), progressCallback);
173   }
174
175   public FormatProcessor(FormattingDocumentModel model,
176                          Block block,
177                          FormatOptions options,
178                          @NotNull FormattingProgressCallback callback)
179   {
180     myProgressCallback = callback;
181     myDefaultIndentOption = options.myIndentOptions;
182     mySettings = options.mySettings;
183     myDocument = model.getDocument();
184     myReformatContext = options.myReformatContext;
185     myCurrentState = new WrapBlocksState(block, model, options.myAffectedRanges, options.myInterestingOffset);
186     myRightMargin = getRightMargin(block);
187   }
188
189   private int getRightMargin(Block rootBlock) {
190     Language language = null;
191     if (rootBlock instanceof ASTBlock) {
192       ASTNode node = ((ASTBlock)rootBlock).getNode();
193       if (node != null) {
194         PsiElement psiElement = node.getPsi();
195         if (psiElement.isValid()) {
196           PsiFile psiFile = psiElement.getContainingFile();
197           if (psiFile != null) {
198             language = psiFile.getViewProvider().getBaseLanguage();
199           }
200         }
201       }
202     }
203     return mySettings.getRightMargin(language);
204   }
205
206   private LeafBlockWrapper getLastBlock() {
207     LeafBlockWrapper result = myFirstTokenBlock;
208     while (result.getNextBlock() != null) {
209       result = result.getNextBlock();
210     }
211     return result;
212   }
213
214   private static TIntObjectHashMap<LeafBlockWrapper> buildTextRangeToInfoMap(final LeafBlockWrapper first) {
215     final TIntObjectHashMap<LeafBlockWrapper> result = new TIntObjectHashMap<LeafBlockWrapper>();
216     LeafBlockWrapper current = first;
217     while (current != null) {
218       result.put(current.getStartOffset(), current);
219       current = current.getNextBlock();
220     }
221     return result;
222   }
223
224   public void format(FormattingModel model) {
225     format(model, false);
226   }
227
228   /**
229    * Asks current processor to perform formatting.
230    * <p/>
231    * There are two processing approaches at the moment:
232    * <pre>
233    * <ul>
234    *   <li>perform formatting during the current method call;</li>
235    *   <li>
236    *     split the whole formatting process to the set of fine-grained tasks and execute them sequentially during
237    *     subsequent {@link #iteration()} calls;
238    *   </li>
239    * </ul>
240    * </pre>
241    * <p/>
242    * Here is rationale for the second approach - formatting may introduce changes to the underlying document and IntelliJ IDEA
243    * is designed in a way that write access is allowed from EDT only. That means that every time we execute particular action
244    * from EDT we have no chance of performing any other actions from EDT simultaneously (e.g. we may want to show progress bar
245    * that reflects current formatting state but the progress bar can' bet updated if formatting is performed during a single long
246    * method call). So, we can interleave formatting iterations with GUI state updates.
247    *
248    * @param model         target formatting model
249    * @param sequentially  flag that indicates what kind of processing should be used
250    */
251   public void format(FormattingModel model, boolean sequentially) {
252     if (sequentially) {
253       AdjustWhiteSpacesState adjustState = new AdjustWhiteSpacesState();
254       ExpandChildrenIndent expandChildrenIndent = new ExpandChildrenIndent();
255       ApplyChangesState applyChangesState = new ApplyChangesState(model);
256
257       expandChildrenIndent.setNext(applyChangesState);
258       adjustState.setNext(expandChildrenIndent);
259       myCurrentState.setNext(adjustState);
260     }
261     else {
262       formatWithoutRealModifications(false);
263       performModifications(model, false);
264     }
265   }
266
267   /**
268    * Asks current processor to perform processing iteration
269    *
270    * @return    <code>true</code> if the processing is finished; <code>false</code> otherwise
271    * @see #format(FormattingModel, boolean)
272    */
273   public boolean iteration() {
274     if (myCurrentState.isDone()) {
275       return true;
276     }
277     myCurrentState.iteration();
278     return myCurrentState.isDone();
279   }
280
281   /**
282    * Asks current processor to stop any active sequential processing if any.
283    */
284   public void stopSequentialProcessing() {
285     myCurrentState.stop();
286   }
287
288   public void formatWithoutRealModifications() {
289     formatWithoutRealModifications(false);
290   }
291
292   @SuppressWarnings({"WhileLoopSpinsOnField"})
293   public void formatWithoutRealModifications(boolean sequentially) {
294     AdjustWhiteSpacesState adjustSpace = new AdjustWhiteSpacesState();
295     adjustSpace.setNext(new ExpandChildrenIndent());
296     myCurrentState.setNext(adjustSpace);
297
298     if (sequentially) {
299       return;
300     }
301
302     doIterationsSynchronously(FormattingStateId.PROCESSING_BLOCKS);
303   }
304
305   private void reset() {
306     myBackwardShiftedAlignedBlocks.clear();
307     myAlignmentMappings.clear();
308     myPreviousDependencies.clear();
309     myWrapCandidate = null;
310     if (myRootBlockWrapper != null) {
311       myRootBlockWrapper.reset();
312     }
313   }
314
315   public void performModifications(FormattingModel model) {
316     performModifications(model, false);
317   }
318
319   public void performModifications(FormattingModel model, boolean sequentially) {
320     assert !myDisposed;
321     myCurrentState.setNext(new ApplyChangesState(model));
322
323     if (sequentially) {
324       return;
325     }
326
327     doIterationsSynchronously(FormattingStateId.APPLYING_CHANGES);
328   }
329
330   /**
331    * Perform iterations against the {@link #myCurrentState current state} until it's {@link FormattingStateId type}
332    * is {@link FormattingStateId#getPreviousStates() less} or equal to the given state.
333    *
334    * @param state   target state to process
335    */
336   private void doIterationsSynchronously(@NotNull FormattingStateId state) {
337     while ((myCurrentState.getStateId() == state || state.getPreviousStates().contains(myCurrentState.getStateId()))
338            && !myCurrentState.isDone())
339     {
340       myCurrentState.iteration();
341     }
342   }
343
344   public void setJavaIndentOptions(final CommonCodeStyleSettings.IndentOptions javaIndentOptions) {
345     myJavaIndentOptions = javaIndentOptions;
346   }
347
348   /**
349    * Decides whether applying formatter changes should be applied incrementally one-by-one or merge result should be
350    * constructed locally and the whole document text should be replaced. Performs such single bulk change if necessary.
351    *
352    * @param blocksToModify        changes introduced by formatter
353    * @param model                 current formatting model
354    * @param indentOption          indent options to use
355    * @return                      <code>true</code> if given changes are applied to the document (i.e. no further processing is required);
356    *                              <code>false</code> otherwise
357    */
358   @SuppressWarnings({"deprecation"})
359   private boolean applyChangesAtRewriteMode(@NotNull final List<LeafBlockWrapper> blocksToModify,
360                                             @NotNull final FormattingModel model,
361                                             @NotNull CommonCodeStyleSettings.IndentOptions indentOption)
362   {
363     FormattingDocumentModel documentModel = model.getDocumentModel();
364     Document document = documentModel.getDocument();
365     CaretOffsetUpdater caretOffsetUpdater = new CaretOffsetUpdater(document);
366
367     List<TextChange> changes = new ArrayList<TextChange>();
368     int shift = 0;
369     int currentIterationShift = 0;
370     for (LeafBlockWrapper block : blocksToModify) {
371       WhiteSpace whiteSpace = block.getWhiteSpace();
372       CharSequence newWs = documentModel.adjustWhiteSpaceIfNecessary(
373         whiteSpace.generateWhiteSpace(getIndentOptionsToUse(block, indentOption)), whiteSpace.getStartOffset(),
374         whiteSpace.getEndOffset(), block.getNode(), false
375       );
376       if (changes.size() > 10000) {
377         caretOffsetUpdater.update(changes);
378         CharSequence mergeResult = BulkChangesMerger.INSTANCE.mergeToCharSequence(document.getChars(), document.getTextLength(), changes);
379         document.replaceString(0, document.getTextLength(), mergeResult);
380         shift += currentIterationShift;
381         currentIterationShift = 0;
382         changes.clear();
383       }
384       TextChangeImpl change = new TextChangeImpl(newWs, whiteSpace.getStartOffset() + shift, whiteSpace.getEndOffset() + shift);
385       currentIterationShift += change.getDiff();
386       changes.add(change);
387     }
388     caretOffsetUpdater.update(changes);
389     CharSequence mergeResult = BulkChangesMerger.INSTANCE.mergeToCharSequence(document.getChars(), document.getTextLength(), changes);
390     document.replaceString(0, document.getTextLength(), mergeResult);
391     caretOffsetUpdater.restoreCaretLocations();
392     cleanupBlocks(blocksToModify);
393     return true;
394   }
395
396   private static void cleanupBlocks(List<LeafBlockWrapper> blocks) {
397     for (LeafBlockWrapper block : blocks) {
398       block.getParent().dispose();
399       block.dispose();
400     }
401     blocks.clear();
402   }
403
404   @Nullable
405   private static DocumentEx getAffectedDocument(final FormattingModel model) {
406     final Document document = model.getDocumentModel().getDocument();
407     if (document instanceof DocumentEx) {
408       return (DocumentEx)document;
409     }
410     else {
411       return null;
412     }
413   }
414
415   private static int replaceWhiteSpace(final FormattingModel model,
416                                        @NotNull final LeafBlockWrapper block,
417                                        int shift,
418                                        final CharSequence _newWhiteSpace,
419                                        final CommonCodeStyleSettings.IndentOptions options
420   ) {
421     final WhiteSpace whiteSpace = block.getWhiteSpace();
422     final TextRange textRange = whiteSpace.getTextRange();
423     final TextRange wsRange = textRange.shiftRight(shift);
424     final String newWhiteSpace = _newWhiteSpace.toString();
425     TextRange newWhiteSpaceRange = model instanceof FormattingModelEx
426                                    ? ((FormattingModelEx) model).replaceWhiteSpace(wsRange, block.getNode(), newWhiteSpace)
427                                    : model.replaceWhiteSpace(wsRange, newWhiteSpace);
428
429     shift += newWhiteSpaceRange.getLength() - textRange.getLength();
430
431     if (block.isLeaf() && whiteSpace.containsLineFeeds() && block.containsLineFeeds()) {
432       final TextRange currentBlockRange = block.getTextRange().shiftRight(shift);
433
434       IndentInside oldBlockIndent = whiteSpace.getInitialLastLineIndent();
435       IndentInside whiteSpaceIndent = IndentInside.createIndentOn(IndentInside.getLastLine(newWhiteSpace));
436       final int shiftInside = calcShift(oldBlockIndent, whiteSpaceIndent, options);
437
438       if (shiftInside != 0 || !oldBlockIndent.equals(whiteSpaceIndent)) {
439         final TextRange newBlockRange = model.shiftIndentInsideRange(block.getNode(), currentBlockRange, shiftInside);
440         shift += newBlockRange.getLength() - block.getLength();
441       }
442     }
443     return shift;
444   }
445
446   @NotNull
447   private List<LeafBlockWrapper> collectBlocksToModify() {
448     List<LeafBlockWrapper> blocksToModify = new ArrayList<LeafBlockWrapper>();
449
450     for (LeafBlockWrapper block = myFirstTokenBlock; block != null; block = block.getNextBlock()) {
451       final WhiteSpace whiteSpace = block.getWhiteSpace();
452       if (!whiteSpace.isReadOnly()) {
453         final String newWhiteSpace = whiteSpace.generateWhiteSpace(getIndentOptionsToUse(block, myDefaultIndentOption));
454         if (!whiteSpace.equalsToString(newWhiteSpace)) {
455           blocksToModify.add(block);
456         }
457       }
458     }
459     return blocksToModify;
460   }
461
462   @NotNull
463   private CommonCodeStyleSettings.IndentOptions getIndentOptionsToUse(@NotNull AbstractBlockWrapper block,
464                                                                       @NotNull CommonCodeStyleSettings.IndentOptions fallbackIndentOptions)
465   {
466     final Language language = block.getLanguage();
467     if (language == null) {
468       return fallbackIndentOptions;
469     }
470     final CommonCodeStyleSettings commonSettings = mySettings.getCommonSettings(language);
471     if (commonSettings == null) {
472       return fallbackIndentOptions;
473     }
474     final CommonCodeStyleSettings.IndentOptions result = commonSettings.getIndentOptions();
475     return result == null ? fallbackIndentOptions : result;
476   }
477
478   private void processToken() {
479     final SpacingImpl spaceProperty = myCurrentBlock.getSpaceProperty();
480     final WhiteSpace whiteSpace = myCurrentBlock.getWhiteSpace();
481
482     if (isReformatSelectedRangesContext()) {
483       if (isCurrentBlockAlignmentUsedInRangesToModify() && whiteSpace.isReadOnly() && spaceProperty != null && !spaceProperty.isReadOnly()) {
484         whiteSpace.setReadOnly(false);
485         whiteSpace.setLineFeedsAreReadOnly(true);
486       }
487     }
488
489     whiteSpace.arrangeLineFeeds(spaceProperty, this);
490
491     if (!whiteSpace.containsLineFeeds()) {
492       whiteSpace.arrangeSpaces(spaceProperty);
493     }
494
495     try {
496       if (processWrap()) {
497         return;
498       }
499     }
500     finally {
501       if (whiteSpace.containsLineFeeds()) {
502         onCurrentLineChanged();
503       }
504     }
505
506     if (!adjustIndent()) {
507       return;
508     }
509
510     defineAlignOffset(myCurrentBlock);
511
512     if (myCurrentBlock.containsLineFeeds()) {
513       onCurrentLineChanged();
514     }
515
516
517     final List<TextRange> ranges = getDependentRegionRangesAfterCurrentWhiteSpace(spaceProperty, whiteSpace);
518     if (!ranges.isEmpty()) {
519       registerUnresolvedDependentSpacingRanges(spaceProperty, ranges);
520     }
521
522     if (!whiteSpace.isIsReadOnly() && shouldReformatPreviouslyLocatedDependentSpacing(whiteSpace)) {
523       myAlignAgain.add(whiteSpace);
524     }
525     else if (!myAlignAgain.isEmpty()) {
526       myAlignAgain.remove(whiteSpace);
527     }
528
529     myCurrentBlock = myCurrentBlock.getNextBlock();
530   }
531
532   private boolean isReformatSelectedRangesContext() {
533     return myReformatContext && !ContainerUtil.isEmpty(myAlignmentsInsideRangesToModify);
534   }
535
536   private boolean isCurrentBlockAlignmentUsedInRangesToModify() {
537     AbstractBlockWrapper block = myCurrentBlock;
538     AlignmentImpl alignment = myCurrentBlock.getAlignment();
539
540     while (alignment == null) {
541       block = block.getParent();
542       if (block == null || block.getStartOffset() != myCurrentBlock.getStartOffset()) {
543         return false;
544       }
545       alignment = block.getAlignment();
546     }
547
548     return myAlignmentsInsideRangesToModify.contains(alignment);
549   }
550
551   private boolean shouldReformatPreviouslyLocatedDependentSpacing(WhiteSpace space) {
552     final TextRange changed = space.getTextRange();
553     final SortedMap<TextRange, DependantSpacingImpl> sortedHeadMap = myPreviousDependencies.tailMap(changed);
554
555     for (final Map.Entry<TextRange, DependantSpacingImpl> entry : sortedHeadMap.entrySet()) {
556       final TextRange textRange = entry.getKey();
557
558       if (textRange.contains(changed)) {
559         final DependantSpacingImpl spacing = entry.getValue();
560         if (spacing.isDependentRegionLinefeedStatusChanged()) {
561           continue;
562         }
563
564         final boolean containedLineFeeds = spacing.getMinLineFeeds() > 0;
565         final boolean containsLineFeeds = containsLineFeeds(textRange);
566
567         if (containedLineFeeds != containsLineFeeds) {
568           spacing.setDependentRegionLinefeedStatusChanged();
569           return true;
570         }
571       }
572     }
573
574     return false;
575   }
576
577   private void registerUnresolvedDependentSpacingRanges(final SpacingImpl spaceProperty, List<TextRange> unprocessedRanges) {
578     final DependantSpacingImpl dependantSpaceProperty = (DependantSpacingImpl)spaceProperty;
579     if (dependantSpaceProperty.isDependentRegionLinefeedStatusChanged()) return;
580
581     for (TextRange range: unprocessedRanges) {
582       myPreviousDependencies.put(range, dependantSpaceProperty);
583     }
584   }
585
586   private static List<TextRange> getDependentRegionRangesAfterCurrentWhiteSpace(final SpacingImpl spaceProperty,
587                                                                                 final WhiteSpace whiteSpace)
588   {
589     if (!(spaceProperty instanceof DependantSpacingImpl)) return ContainerUtil.emptyList();
590
591     if (whiteSpace.isReadOnly() || whiteSpace.isLineFeedsAreReadOnly()) return ContainerUtil.emptyList();
592
593     DependantSpacingImpl spacing = (DependantSpacingImpl)spaceProperty;
594     return ContainerUtil.filter(spacing.getDependentRegionRanges(), new Condition<TextRange>() {
595       @Override
596       public boolean value(TextRange dependencyRange) {
597         return whiteSpace.getStartOffset() < dependencyRange.getEndOffset();
598       }
599     });
600   }
601
602   /**
603    * Processes the wrap of the current block.
604    *
605    * @return true if we have changed myCurrentBlock and need to restart its processing; false if myCurrentBlock is unchanged and we can
606    * continue processing
607    */
608   private boolean processWrap() {
609     final SpacingImpl spacing = myCurrentBlock.getSpaceProperty();
610     final WhiteSpace whiteSpace = myCurrentBlock.getWhiteSpace();
611
612     final boolean wrapWasPresent = whiteSpace.containsLineFeeds();
613
614     if (wrapWasPresent) {
615       myFirstWrappedBlockOnLine = null;
616
617       if (!whiteSpace.containsLineFeedsInitially()) {
618         whiteSpace.removeLineFeeds(spacing, this);
619       }
620     }
621
622     final boolean wrapIsPresent = whiteSpace.containsLineFeeds();
623
624     final ArrayList<WrapImpl> wraps = myCurrentBlock.getWraps();
625     for (WrapImpl wrap : wraps) {
626       wrap.setWrapOffset(myCurrentBlock.getStartOffset());
627     }
628
629     final WrapImpl wrap = getWrapToBeUsed(wraps);
630
631     if (wrap != null || wrapIsPresent) {
632       if (!wrapIsPresent && !canReplaceWrapCandidate(wrap)) {
633         myCurrentBlock = myWrapCandidate;
634         return true;
635       }
636       if (wrap != null && wrap.getChopStartBlock() != null) {
637         // getWrapToBeUsed() returns the block only if it actually exceeds the right margin. In this case, we need to go back to the
638         // first block that has the CHOP_IF_NEEDED wrap type and start wrapping from there.
639         myCurrentBlock = wrap.getChopStartBlock();
640         wrap.setActive();
641         return true;
642       }
643       if (wrap != null && isChopNeeded(wrap)) {
644         wrap.setActive();
645       }
646
647       if (!wrapIsPresent) {
648         whiteSpace.ensureLineFeed();
649         if (!wrapWasPresent) {
650           if (myFirstWrappedBlockOnLine != null && wrap.isChildOf(myFirstWrappedBlockOnLine.getWrap(), myCurrentBlock)) {
651             wrap.ignoreParentWrap(myFirstWrappedBlockOnLine.getWrap(), myCurrentBlock);
652             myCurrentBlock = myFirstWrappedBlockOnLine;
653             return true;
654           }
655           else {
656             myFirstWrappedBlockOnLine = myCurrentBlock;
657           }
658         }
659       }
660
661       myWrapCandidate = null;
662     }
663     else {
664       for (final WrapImpl wrap1 : wraps) {
665         if (isCandidateToBeWrapped(wrap1) && canReplaceWrapCandidate(wrap1)) {
666           myWrapCandidate = myCurrentBlock;
667         }
668         if (isChopNeeded(wrap1)) {
669           wrap1.saveChopBlock(myCurrentBlock);
670         }
671       }
672     }
673
674     if (!whiteSpace.containsLineFeeds() && myWrapCandidate != null && !whiteSpace.isReadOnly() && lineOver()) {
675       myCurrentBlock = myWrapCandidate;
676       return true;
677     }
678
679     return false;
680   }
681
682   /**
683    * Allows to answer if wrap of the {@link #myWrapCandidate} object (if any) may be replaced by the given wrap.
684    *
685    * @param wrap wrap candidate to check
686    * @return <code>true</code> if wrap of the {@link #myWrapCandidate} object (if any) may be replaced by the given wrap;
687    *         <code>false</code> otherwise
688    */
689   private boolean canReplaceWrapCandidate(WrapImpl wrap) {
690     if (myWrapCandidate == null) return true;
691     WrapImpl.Type type = wrap.getType();
692     if (wrap.isActive() && (type == WrapImpl.Type.CHOP_IF_NEEDED || type == WrapImpl.Type.WRAP_ALWAYS)) return true;
693     final WrapImpl currentWrap = myWrapCandidate.getWrap();
694     return wrap == currentWrap || !wrap.isChildOf(currentWrap, myCurrentBlock);
695   }
696
697   private boolean isCandidateToBeWrapped(final WrapImpl wrap) {
698     return isSuitableInTheCurrentPosition(wrap) &&
699            (wrap.getType() == WrapImpl.Type.WRAP_AS_NEEDED || wrap.getType() == WrapImpl.Type.CHOP_IF_NEEDED) &&
700            !myCurrentBlock.getWhiteSpace().isReadOnly();
701   }
702
703   private void onCurrentLineChanged() {
704     myWrapCandidate = null;
705   }
706
707   /**
708    * Adjusts indent of the current block.
709    *
710    * @return <code>true</code> if current formatting iteration should be continued;
711    *         <code>false</code> otherwise (e.g. if previously processed block is shifted inside this method for example
712    *         because of specified alignment options)
713    */
714   private boolean adjustIndent() {
715     AlignmentImpl alignment = CoreFormatterUtil.getAlignment(myCurrentBlock);
716     WhiteSpace whiteSpace = myCurrentBlock.getWhiteSpace();
717
718     if (alignment == null || myAlignmentsToSkip.contains(alignment)) {
719       if (whiteSpace.containsLineFeeds()) {
720         adjustSpacingByIndentOffset();
721       }
722       else {
723         whiteSpace.arrangeSpaces(myCurrentBlock.getSpaceProperty());
724       }
725       return true;
726     }
727
728     BlockAlignmentProcessor alignmentProcessor = ALIGNMENT_PROCESSORS.get(alignment.getAnchor());
729     if (alignmentProcessor == null) {
730       LOG.error(String.format("Can't find alignment processor for alignment anchor %s", alignment.getAnchor()));
731       return true;
732     }
733
734     BlockAlignmentProcessor.Context context = new BlockAlignmentProcessor.Context(
735       myDocument, alignment, myCurrentBlock, myAlignmentMappings, myBackwardShiftedAlignedBlocks,
736       getIndentOptionsToUse(myCurrentBlock, myDefaultIndentOption), myRightMargin
737     );
738     BlockAlignmentProcessor.Result result = alignmentProcessor.applyAlignment(context);
739     final LeafBlockWrapper offsetResponsibleBlock = alignment.getOffsetRespBlockBefore(myCurrentBlock);
740     switch (result) {
741       case TARGET_BLOCK_PROCESSED_NOT_ALIGNED: return true;
742       case TARGET_BLOCK_ALIGNED: storeAlignmentMapping(); return true;
743       case BACKWARD_BLOCK_ALIGNED:
744         if (offsetResponsibleBlock == null) {
745           return true;
746         }
747         Set<LeafBlockWrapper> blocksCausedRealignment = new HashSet<LeafBlockWrapper>();
748         myBackwardShiftedAlignedBlocks.clear();
749         myBackwardShiftedAlignedBlocks.put(offsetResponsibleBlock, blocksCausedRealignment);
750         blocksCausedRealignment.add(myCurrentBlock);
751         storeAlignmentMapping(myCurrentBlock, offsetResponsibleBlock);
752         myCurrentBlock = offsetResponsibleBlock.getNextBlock();
753         onCurrentLineChanged();
754         return false;
755       case RECURSION_DETECTED:
756         myCurrentBlock = offsetResponsibleBlock; // Fall through to the 'register alignment to skip'.
757       case UNABLE_TO_ALIGN_BACKWARD_BLOCK:
758         myAlignmentsToSkip.add(alignment);
759         return false;
760       default: return true;
761     }
762   }
763
764   /**
765    * We need to track blocks which white spaces are modified because of alignment rules.
766    * <p/>
767    * This method encapsulates the logic of storing such information.
768    */
769   private void storeAlignmentMapping() {
770     AlignmentImpl alignment = null;
771     AbstractBlockWrapper block = myCurrentBlock;
772     while (alignment == null && block != null) {
773       alignment = block.getAlignment();
774       block = block.getParent();
775     }
776     if (alignment != null) {
777       block = alignment.getOffsetRespBlockBefore(myCurrentBlock);
778       if (block != null) {
779         storeAlignmentMapping(myCurrentBlock, block);
780       }
781     }
782   }
783
784   private void storeAlignmentMapping(AbstractBlockWrapper block1, AbstractBlockWrapper block2) {
785     doStoreAlignmentMapping(block1, block2);
786     doStoreAlignmentMapping(block2, block1);
787   }
788
789   private void doStoreAlignmentMapping(AbstractBlockWrapper key, AbstractBlockWrapper value) {
790     Set<AbstractBlockWrapper> wrappers = myAlignmentMappings.get(key);
791     if (wrappers == null) {
792       myAlignmentMappings.put(key, wrappers = new HashSet<AbstractBlockWrapper>());
793     }
794     wrappers.add(value);
795   }
796
797   /**
798    * Applies indent to the white space of {@link #myCurrentBlock currently processed wrapped block}. Both indentation
799    * and alignment options are took into consideration here.
800    */
801   private void adjustLineIndent() {
802     IndentData alignOffset = getAlignOffset();
803
804     if (alignOffset == null) {
805       adjustSpacingByIndentOffset();
806     }
807     else {
808       myCurrentBlock.getWhiteSpace().setSpaces(alignOffset.getSpaces(), alignOffset.getIndentSpaces());
809     }
810   }
811
812   private void adjustSpacingByIndentOffset() {
813     IndentData offset = myCurrentBlock.calculateOffset(getIndentOptionsToUse(myCurrentBlock, myDefaultIndentOption));
814     myCurrentBlock.getWhiteSpace().setSpaces(offset.getSpaces(), offset.getIndentSpaces());
815   }
816
817   private boolean isChopNeeded(final WrapImpl wrap) {
818     return wrap != null && wrap.getType() == WrapImpl.Type.CHOP_IF_NEEDED && isSuitableInTheCurrentPosition(wrap);
819   }
820
821   private boolean isSuitableInTheCurrentPosition(final WrapImpl wrap) {
822     if (wrap.getWrapOffset() < myCurrentBlock.getStartOffset()) {
823       return true;
824     }
825
826     if (wrap.isWrapFirstElement()) {
827       return true;
828     }
829
830     if (wrap.getType() == WrapImpl.Type.WRAP_AS_NEEDED) {
831       return positionAfterWrappingIsSuitable();
832     }
833
834     return wrap.getType() == WrapImpl.Type.CHOP_IF_NEEDED && lineOver() && positionAfterWrappingIsSuitable();
835   }
836
837   /**
838    * Ensures that offset of the {@link #myCurrentBlock currently processed block} is not increased if we make a wrap on it.
839    *
840    * @return <code>true</code> if it's ok to wrap at the currently processed block; <code>false</code> otherwise
841    */
842   private boolean positionAfterWrappingIsSuitable() {
843     final WhiteSpace whiteSpace = myCurrentBlock.getWhiteSpace();
844     if (whiteSpace.containsLineFeeds()) return true;
845     final int spaces = whiteSpace.getSpaces();
846     int indentSpaces = whiteSpace.getIndentSpaces();
847     try {
848       final int startColumnNow = CoreFormatterUtil.getStartColumn(myCurrentBlock);
849       whiteSpace.ensureLineFeed();
850       adjustLineIndent();
851       final int startColumnAfterWrap = CoreFormatterUtil.getStartColumn(myCurrentBlock);
852       return startColumnNow > startColumnAfterWrap;
853     }
854     finally {
855       whiteSpace.removeLineFeeds(myCurrentBlock.getSpaceProperty(), this);
856       whiteSpace.setSpaces(spaces, indentSpaces);
857     }
858   }
859
860   @Nullable
861   private WrapImpl getWrapToBeUsed(final ArrayList<WrapImpl> wraps) {
862     if (wraps.isEmpty()) {
863       return null;
864     }
865     if (myWrapCandidate == myCurrentBlock) return wraps.get(0);
866
867     for (final WrapImpl wrap : wraps) {
868       if (!isSuitableInTheCurrentPosition(wrap)) continue;
869       if (wrap.isActive()) return wrap;
870
871       final WrapImpl.Type type = wrap.getType();
872       if (type == WrapImpl.Type.WRAP_ALWAYS) return wrap;
873       if (type == WrapImpl.Type.WRAP_AS_NEEDED || type == WrapImpl.Type.CHOP_IF_NEEDED) {
874         if (lineOver()) {
875           return wrap;
876         }
877       }
878     }
879     return null;
880   }
881
882   /**
883    * @return <code>true</code> if {@link #myCurrentBlock currently processed wrapped block} doesn't contain line feeds and
884    *         exceeds right margin; <code>false</code> otherwise
885    */
886   private boolean lineOver() {
887     return !myCurrentBlock.containsLineFeeds() &&
888            CoreFormatterUtil.getStartColumn(myCurrentBlock) + myCurrentBlock.getLength() > myRightMargin;
889   }
890
891   private void defineAlignOffset(final LeafBlockWrapper block) {
892     AbstractBlockWrapper current = myCurrentBlock;
893     while (true) {
894       final AlignmentImpl alignment = current.getAlignment();
895       if (alignment != null) {
896         alignment.setOffsetRespBlock(block);
897       }
898       current = current.getParent();
899       if (current == null) return;
900       if (current.getStartOffset() != myCurrentBlock.getStartOffset()) return;
901
902     }
903   }
904
905   /**
906    * Tries to get align-implied indent of the current block.
907    *
908    * @return indent of the current block if any; <code>null</code> otherwise
909    */
910   @Nullable
911   private IndentData getAlignOffset() {
912     AbstractBlockWrapper current = myCurrentBlock;
913     while (true) {
914       final AlignmentImpl alignment = current.getAlignment();
915       LeafBlockWrapper offsetResponsibleBlock;
916       if (alignment != null && (offsetResponsibleBlock = alignment.getOffsetRespBlockBefore(myCurrentBlock)) != null) {
917         final WhiteSpace whiteSpace = offsetResponsibleBlock.getWhiteSpace();
918         if (whiteSpace.containsLineFeeds()) {
919           return new IndentData(whiteSpace.getIndentSpaces(), whiteSpace.getSpaces());
920         }
921         else {
922           final int offsetBeforeBlock = CoreFormatterUtil.getStartColumn(offsetResponsibleBlock);
923           final AbstractBlockWrapper indentedParentBlock = CoreFormatterUtil.getIndentedParentBlock(myCurrentBlock);
924           if (indentedParentBlock == null) {
925             return new IndentData(0, offsetBeforeBlock);
926           }
927           else {
928             final int parentIndent = indentedParentBlock.getWhiteSpace().getIndentOffset();
929             if (parentIndent > offsetBeforeBlock) {
930               return new IndentData(0, offsetBeforeBlock);
931             }
932             else {
933               return new IndentData(parentIndent, offsetBeforeBlock - parentIndent);
934             }
935           }
936         }
937       }
938       else {
939         current = current.getParent();
940         if (current == null || current.getStartOffset() != myCurrentBlock.getStartOffset()) return null;
941       }
942     }
943   }
944
945   public boolean containsLineFeeds(final TextRange dependency) {
946     LeafBlockWrapper child = myTextRangeToWrapper.get(dependency.getStartOffset());
947     if (child == null) return false;
948     if (child.containsLineFeeds()) return true;
949     final int endOffset = dependency.getEndOffset();
950     while (child.getEndOffset() < endOffset) {
951       child = child.getNextBlock();
952       if (child == null) return false;
953       if (child.getWhiteSpace().containsLineFeeds()) return true;
954       if (child.containsLineFeeds()) return true;
955     }
956     return false;
957   }
958
959   @Nullable
960   public LeafBlockWrapper getBlockAtOrAfter(final int startOffset) {
961     int current = startOffset;
962     LeafBlockWrapper result = null;
963     while (current < myLastWhiteSpace.getStartOffset()) {
964       final LeafBlockWrapper currentValue = myTextRangeToWrapper.get(current);
965       if (currentValue != null) {
966         result = currentValue;
967         break;
968       }
969       current++;
970     }
971
972     LeafBlockWrapper prevBlock = getPrevBlock(result);
973
974     if (prevBlock != null && prevBlock.contains(startOffset)) {
975       return prevBlock;
976     }
977     else {
978       return result;
979     }
980   }
981
982   @Nullable
983   private LeafBlockWrapper getPrevBlock(@Nullable final LeafBlockWrapper result) {
984     if (result != null) {
985       return result.getPreviousBlock();
986     }
987     else {
988       return myLastTokenBlock;
989     }
990   }
991
992   public void setAllWhiteSpacesAreReadOnly() {
993     LeafBlockWrapper current = myFirstTokenBlock;
994     while (current != null) {
995       current.getWhiteSpace().setReadOnly(true);
996       current = current.getNextBlock();
997     }
998   }
999
1000   static class ChildAttributesInfo {
1001     public final AbstractBlockWrapper parent;
1002     final        ChildAttributes      attributes;
1003     final        int                  index;
1004
1005     public ChildAttributesInfo(final AbstractBlockWrapper parent, final ChildAttributes attributes, final int index) {
1006       this.parent = parent;
1007       this.attributes = attributes;
1008       this.index = index;
1009     }
1010   }
1011
1012   public IndentInfo getIndentAt(final int offset) {
1013     processBlocksBefore(offset);
1014     AbstractBlockWrapper parent = getParentFor(offset, myCurrentBlock);
1015     if (parent == null) {
1016       final LeafBlockWrapper previousBlock = myCurrentBlock.getPreviousBlock();
1017       if (previousBlock != null) parent = getParentFor(offset, previousBlock);
1018       if (parent == null) return new IndentInfo(0, 0, 0);
1019     }
1020     int index = getNewChildPosition(parent, offset);
1021     final Block block = myInfos.get(parent);
1022
1023     if (block == null) {
1024       return new IndentInfo(0, 0, 0);
1025     }
1026
1027     ChildAttributesInfo info = getChildAttributesInfo(block, index, parent);
1028     if (info == null) {
1029       return new IndentInfo(0, 0, 0);
1030     }
1031
1032     return adjustLineIndent(info.parent, info.attributes, info.index);
1033   }
1034
1035   @Nullable
1036   private static ChildAttributesInfo getChildAttributesInfo(@NotNull final Block block,
1037                                                             final int index,
1038                                                             @Nullable AbstractBlockWrapper parent) {
1039     if (parent == null) {
1040       return null;
1041     }
1042     ChildAttributes childAttributes = block.getChildAttributes(index);
1043
1044     if (childAttributes == ChildAttributes.DELEGATE_TO_PREV_CHILD) {
1045       final Block newBlock = block.getSubBlocks().get(index - 1);
1046       AbstractBlockWrapper prevWrappedBlock;
1047       if (parent instanceof CompositeBlockWrapper) {
1048         prevWrappedBlock = ((CompositeBlockWrapper)parent).getChildren().get(index - 1);
1049       }
1050       else {
1051         prevWrappedBlock = parent.getPreviousBlock();
1052       }
1053       return getChildAttributesInfo(newBlock, newBlock.getSubBlocks().size(), prevWrappedBlock);
1054     }
1055
1056     else if (childAttributes == ChildAttributes.DELEGATE_TO_NEXT_CHILD) {
1057       AbstractBlockWrapper nextWrappedBlock;
1058       if (parent instanceof CompositeBlockWrapper) {
1059         List<AbstractBlockWrapper> children = ((CompositeBlockWrapper)parent).getChildren();
1060         if (children != null && index < children.size()) {
1061           nextWrappedBlock = children.get(index);
1062         }
1063         else {
1064           return null;
1065         }
1066       }
1067       else {
1068         nextWrappedBlock = ((LeafBlockWrapper)parent).getNextBlock();
1069       }
1070       return getChildAttributesInfo(block.getSubBlocks().get(index), 0, nextWrappedBlock);
1071     }
1072
1073     else {
1074       return new ChildAttributesInfo(parent, childAttributes, index);
1075     }
1076   }
1077
1078   private IndentInfo adjustLineIndent(final AbstractBlockWrapper parent, final ChildAttributes childAttributes, final int index) {
1079     int alignOffset = getAlignOffsetBefore(childAttributes.getAlignment(), null);
1080     if (alignOffset == -1) {
1081       return parent.calculateChildOffset(getIndentOptionsToUse(parent, myDefaultIndentOption), childAttributes, index).createIndentInfo();
1082     }
1083     else {
1084       AbstractBlockWrapper indentedParentBlock = CoreFormatterUtil.getIndentedParentBlock(myCurrentBlock);
1085       if (indentedParentBlock == null) {
1086         return new IndentInfo(0, 0, alignOffset);
1087       }
1088       else {
1089         int indentOffset = indentedParentBlock.getWhiteSpace().getIndentOffset();
1090         if (indentOffset > alignOffset) {
1091           return new IndentInfo(0, 0, alignOffset);
1092         }
1093         else {
1094           return new IndentInfo(0, indentOffset, alignOffset - indentOffset);
1095         }
1096       }
1097     }
1098   }
1099
1100   private static int getAlignOffsetBefore(@Nullable final Alignment alignment, @Nullable final LeafBlockWrapper blockAfter) {
1101     if (alignment == null) return -1;
1102     final LeafBlockWrapper alignRespBlock = ((AlignmentImpl)alignment).getOffsetRespBlockBefore(blockAfter);
1103     if (alignRespBlock != null) {
1104       return CoreFormatterUtil.getStartColumn(alignRespBlock);
1105     }
1106     else {
1107       return -1;
1108     }
1109   }
1110
1111   private static int getNewChildPosition(final AbstractBlockWrapper parent, final int offset) {
1112     AbstractBlockWrapper parentBlockToUse = getLastNestedCompositeBlockForSameRange(parent);
1113     if (!(parentBlockToUse instanceof CompositeBlockWrapper)) return 0;
1114     final List<AbstractBlockWrapper> subBlocks = ((CompositeBlockWrapper)parentBlockToUse).getChildren();
1115     //noinspection ConstantConditions
1116     if (subBlocks != null) {
1117       for (int i = 0; i < subBlocks.size(); i++) {
1118         AbstractBlockWrapper block = subBlocks.get(i);
1119         if (block.getStartOffset() >= offset) return i;
1120       }
1121       return subBlocks.size();
1122     }
1123     else {
1124       return 0;
1125     }
1126   }
1127
1128   @Nullable
1129   private static AbstractBlockWrapper getParentFor(final int offset, AbstractBlockWrapper block) {
1130     AbstractBlockWrapper current = block;
1131     while (current != null) {
1132       if (current.getStartOffset() < offset && current.getEndOffset() >= offset) {
1133         return current;
1134       }
1135       current = current.getParent();
1136     }
1137     return null;
1138   }
1139
1140   @Nullable
1141   private AbstractBlockWrapper getParentFor(final int offset, LeafBlockWrapper block) {
1142     AbstractBlockWrapper previous = getPreviousIncompleteBlock(block, offset);
1143     if (previous != null) {
1144       return getLastNestedCompositeBlockForSameRange(previous);
1145     }
1146     else {
1147       return getParentFor(offset, (AbstractBlockWrapper)block);
1148     }
1149   }
1150
1151   @Nullable
1152   private AbstractBlockWrapper getPreviousIncompleteBlock(final LeafBlockWrapper block, final int offset) {
1153     if (block == null) {
1154       if (myLastTokenBlock.isIncomplete()) {
1155         return myLastTokenBlock;
1156       }
1157       else {
1158         return null;
1159       }
1160     }
1161
1162     AbstractBlockWrapper current = block;
1163     while (current.getParent() != null && current.getParent().getStartOffset() > offset) {
1164       current = current.getParent();
1165     }
1166
1167     if (current.getParent() == null) return null;
1168
1169     if (current.getEndOffset() <= offset) {
1170       while (!current.isIncomplete() &&
1171              current.getParent() != null &&
1172              current.getParent().getEndOffset() <= offset) {
1173         current = current.getParent();
1174       }
1175       if (current.isIncomplete()) return current;
1176     }
1177
1178     if (current.getParent() == null) return null;
1179
1180     final List<AbstractBlockWrapper> subBlocks = current.getParent().getChildren();
1181     final int index = subBlocks.indexOf(current);
1182     if (index < 0) {
1183       LOG.assertTrue(false);
1184     }
1185     if (index == 0) return null;
1186
1187     AbstractBlockWrapper currentResult = subBlocks.get(index - 1);
1188     if (!currentResult.isIncomplete()) return null;
1189
1190     AbstractBlockWrapper lastChild = getLastChildOf(currentResult);
1191     while (lastChild != null && lastChild.isIncomplete()) {
1192       currentResult = lastChild;
1193       lastChild = getLastChildOf(currentResult);
1194     }
1195     return currentResult;
1196   }
1197
1198   @Nullable
1199   private static AbstractBlockWrapper getLastChildOf(final AbstractBlockWrapper currentResult) {
1200     AbstractBlockWrapper parentBlockToUse = getLastNestedCompositeBlockForSameRange(currentResult);
1201     if (!(parentBlockToUse instanceof CompositeBlockWrapper)) return null;
1202     final List<AbstractBlockWrapper> subBlocks = ((CompositeBlockWrapper)parentBlockToUse).getChildren();
1203     if (subBlocks.isEmpty()) return null;
1204     return subBlocks.get(subBlocks.size() - 1);
1205   }
1206
1207   /**
1208    * There is a possible case that particular block is a composite block that contains number of nested composite blocks
1209    * that all target the same text range. This method allows to derive the most nested block that shares the same range (if any).
1210    *
1211    * @param block   block to check
1212    * @return        the most nested block of the given one that shares the same text range if any; given block otherwise
1213    */
1214   @NotNull
1215   private static AbstractBlockWrapper getLastNestedCompositeBlockForSameRange(@NotNull final AbstractBlockWrapper block) {
1216     if (!(block instanceof CompositeBlockWrapper)) {
1217       return block;
1218     }
1219
1220     AbstractBlockWrapper result = block;
1221     AbstractBlockWrapper candidate = block;
1222     while (true) {
1223       List<AbstractBlockWrapper> subBlocks = ((CompositeBlockWrapper)candidate).getChildren();
1224       if (subBlocks == null || subBlocks.size() != 1) {
1225         break;
1226       }
1227
1228       candidate = subBlocks.get(0);
1229       if (candidate.getStartOffset() == block.getStartOffset() && candidate.getEndOffset() == block.getEndOffset()
1230           && candidate instanceof CompositeBlockWrapper)
1231       {
1232         result = candidate;
1233       }
1234       else {
1235         break;
1236       }
1237     }
1238     return result;
1239   }
1240
1241   private void processBlocksBefore(final int offset) {
1242     while (true) {
1243       myAlignAgain.clear();
1244       myCurrentBlock = myFirstTokenBlock;
1245       while (myCurrentBlock != null && myCurrentBlock.getStartOffset() < offset) {
1246         processToken();
1247         if (myCurrentBlock == null) {
1248           myCurrentBlock = myLastTokenBlock;
1249           if (myCurrentBlock != null) {
1250             myProgressCallback.afterProcessingBlock(myCurrentBlock);
1251           }
1252           break;
1253         }
1254       }
1255       if (myAlignAgain.isEmpty()) return;
1256       reset();
1257     }
1258   }
1259
1260   public LeafBlockWrapper getFirstTokenBlock() {
1261     return myFirstTokenBlock;
1262   }
1263
1264   public WhiteSpace getLastWhiteSpace() {
1265     return myLastWhiteSpace;
1266   }
1267
1268   /**
1269    * Calculates difference in visual columns between the given indents.
1270    *
1271    * @param oldIndent  old indent
1272    * @param newIndent  new indent
1273    * @param options    indent options to use
1274    * @return           difference in visual columns between the given indents
1275    */
1276   private static int calcShift(@NotNull final IndentInside oldIndent,
1277                                @NotNull final IndentInside newIndent,
1278                                @NotNull final CommonCodeStyleSettings.IndentOptions options)
1279   {
1280     if (oldIndent.equals(newIndent)) return 0;
1281     return newIndent.getSpacesCount(options) - oldIndent.getSpacesCount(options);
1282   }
1283
1284   /**
1285    * Utility method to use during debugging formatter processing.
1286    *
1287    * @return    text that contains intermediate formatter-introduced changes (even not committed yet)
1288    */
1289   @SuppressWarnings("UnusedDeclaration")
1290   @NotNull
1291   private String getCurrentText() {
1292     StringBuilder result = new StringBuilder();
1293     for (LeafBlockWrapper block = myFirstTokenBlock; block != null; block = block.getNextBlock()) {
1294       result.append(block.getWhiteSpace().generateWhiteSpace(getIndentOptionsToUse(block, myDefaultIndentOption)));
1295       result.append(myDocument.getCharsSequence().subSequence(block.getStartOffset(), block.getEndOffset()));
1296     }
1297     return result.toString();
1298   }
1299
1300   private abstract class State {
1301
1302     private final FormattingStateId myStateId;
1303
1304     private State   myNextState;
1305     private boolean myDone;
1306
1307     protected State(FormattingStateId stateId) {
1308       myStateId = stateId;
1309     }
1310
1311     public void iteration() {
1312       if (!isDone()) {
1313         doIteration();
1314       }
1315       shiftStateIfNecessary();
1316     }
1317
1318     public boolean isDone() {
1319       return myDone;
1320     }
1321
1322     protected void setDone(boolean done) {
1323       myDone = done;
1324     }
1325
1326     public void setNext(@NotNull State state) {
1327       if (getStateId() == state.getStateId() || (myNextState != null && myNextState.getStateId() == state.getStateId())) {
1328         return;
1329       }
1330       myNextState = state;
1331       shiftStateIfNecessary();
1332     }
1333
1334     public FormattingStateId getStateId() {
1335       return myStateId;
1336     }
1337
1338     public void stop() {
1339     }
1340
1341     protected abstract void doIteration();
1342     protected abstract void prepare();
1343
1344     private void shiftStateIfNecessary() {
1345       if (isDone() && myNextState != null) {
1346         myCurrentState = myNextState;
1347         myNextState = null;
1348         myCurrentState.prepare();
1349       }
1350     }
1351   }
1352
1353   private class WrapBlocksState extends State {
1354
1355     private final InitialInfoBuilder      myWrapper;
1356     private final FormattingDocumentModel myModel;
1357
1358     WrapBlocksState(@NotNull Block root,
1359                     @NotNull FormattingDocumentModel model,
1360                     @Nullable final FormatTextRanges affectedRanges,
1361                     int interestingOffset)
1362     {
1363       super(FormattingStateId.WRAPPING_BLOCKS);
1364       myModel = model;
1365       myWrapper = InitialInfoBuilder.prepareToBuildBlocksSequentially(
1366         root, model, affectedRanges, mySettings, myDefaultIndentOption, interestingOffset, myProgressCallback
1367       );
1368       myWrapper.setCollectAlignmentsInsideFormattingRange(myReformatContext);
1369
1370       myExpandableIndents = myWrapper.getExpandableIndentsBlocks();
1371       myExpandableIndentsMinOffsetBlocksToWrappers = myWrapper.getMarkerBlocks();
1372     }
1373
1374     @Override
1375     protected void prepare() {
1376     }
1377
1378     @Override
1379     public void doIteration() {
1380       if (isDone()) {
1381         return;
1382       }
1383
1384       setDone(myWrapper.iteration());
1385       if (!isDone()) {
1386         return;
1387       }
1388
1389       myInfos = myWrapper.getBlockToInfoMap();
1390       myRootBlockWrapper = myWrapper.getRootBlockWrapper();
1391       myFirstTokenBlock = myWrapper.getFirstTokenBlock();
1392       myLastTokenBlock = myWrapper.getLastTokenBlock();
1393       myCurrentBlock = myFirstTokenBlock;
1394       myTextRangeToWrapper = buildTextRangeToInfoMap(myFirstTokenBlock);
1395       int lastBlockOffset = getLastBlock().getEndOffset();
1396       myLastWhiteSpace = new WhiteSpace(lastBlockOffset, false);
1397       myLastWhiteSpace.append(Math.max(lastBlockOffset, myWrapper.getEndOffset()), myModel, myDefaultIndentOption);
1398       myAlignmentsInsideRangesToModify = myWrapper.getAlignmentsInsideRangeToModify();
1399     }
1400   }
1401
1402   private class AdjustWhiteSpacesState extends State {
1403
1404     AdjustWhiteSpacesState() {
1405       super(FormattingStateId.PROCESSING_BLOCKS);
1406     }
1407
1408     @Override
1409     protected void prepare() {
1410     }
1411
1412     @Override
1413     protected void doIteration() {
1414       LeafBlockWrapper blockToProcess = myCurrentBlock;
1415       processToken();
1416       if (blockToProcess != null) {
1417         myProgressCallback.afterProcessingBlock(blockToProcess);
1418       }
1419
1420       if (myCurrentBlock != null) {
1421         return;
1422       }
1423
1424       if (myAlignAgain.isEmpty()) {
1425         setDone(true);
1426       }
1427       else {
1428         myAlignAgain.clear();
1429         myPreviousDependencies.clear();
1430         myCurrentBlock = myFirstTokenBlock;
1431       }
1432     }
1433   }
1434
1435   private class ApplyChangesState extends State {
1436
1437     private final FormattingModel        myModel;
1438     private       List<LeafBlockWrapper> myBlocksToModify;
1439     private       int                    myShift;
1440     private       int                    myIndex;
1441     private       boolean                myResetBulkUpdateState;
1442
1443     private ApplyChangesState(FormattingModel model) {
1444       super(FormattingStateId.APPLYING_CHANGES);
1445       myModel = model;
1446     }
1447
1448     @Override
1449     protected void prepare() {
1450       myBlocksToModify = collectBlocksToModify();
1451       // call doModifications static method to ensure no access to state
1452       // thus we may clear formatting state
1453       reset();
1454
1455       myInfos = null;
1456       myRootBlockWrapper = null;
1457       myTextRangeToWrapper = null;
1458       myPreviousDependencies = null;
1459       myLastWhiteSpace = null;
1460       myFirstTokenBlock = null;
1461       myLastTokenBlock = null;
1462       myDisposed = true;
1463
1464       if (myBlocksToModify.isEmpty()) {
1465         setDone(true);
1466         return;
1467       }
1468
1469       //for GeneralCodeFormatterTest
1470       if (myJavaIndentOptions == null) {
1471         myJavaIndentOptions = mySettings.getIndentOptions(StdFileTypes.JAVA);
1472       }
1473
1474       myProgressCallback.beforeApplyingFormatChanges(myBlocksToModify);
1475
1476       final int blocksToModifyCount = myBlocksToModify.size();
1477       final boolean bulkReformat = blocksToModifyCount > 50;
1478       DocumentEx updatedDocument = bulkReformat ? getAffectedDocument(myModel) : null;
1479       if (updatedDocument != null) {
1480         updatedDocument.setInBulkUpdate(true);
1481         myResetBulkUpdateState = true;
1482       }
1483       if (blocksToModifyCount > BULK_REPLACE_OPTIMIZATION_CRITERIA
1484           && applyChangesAtRewriteMode(myBlocksToModify, myModel, myDefaultIndentOption))
1485       {
1486         setDone(true);
1487       }
1488     }
1489
1490     @Override
1491     protected void doIteration() {
1492       LeafBlockWrapper blockWrapper = myBlocksToModify.get(myIndex);
1493       myShift = replaceWhiteSpace(
1494         myModel,
1495         blockWrapper,
1496         myShift,
1497         blockWrapper.getWhiteSpace().generateWhiteSpace(getIndentOptionsToUse(blockWrapper, myDefaultIndentOption)),
1498         myDefaultIndentOption
1499       );
1500       myProgressCallback.afterApplyingChange(blockWrapper);
1501       // block could be gc'd
1502       blockWrapper.getParent().dispose();
1503       blockWrapper.dispose();
1504       myBlocksToModify.set(myIndex, null);
1505       myIndex++;
1506
1507       if (myIndex >= myBlocksToModify.size()) {
1508         setDone(true);
1509       }
1510     }
1511
1512     @Override
1513     protected void setDone(boolean done) {
1514       super.setDone(done);
1515
1516       if (myResetBulkUpdateState) {
1517         DocumentEx document = getAffectedDocument(myModel);
1518         if (document != null) {
1519           document.setInBulkUpdate(false);
1520           myResetBulkUpdateState = false;
1521         }
1522       }
1523
1524       if (done) {
1525         myModel.commitChanges();
1526       }
1527     }
1528
1529     @Override
1530     public void stop() {
1531       if (myIndex > 0) {
1532         UIUtil.invokeAndWaitIfNeeded(new Runnable() {
1533           @Override
1534           public void run() {
1535             myModel.commitChanges();
1536           }
1537         });
1538       }
1539     }
1540   }
1541
1542   private static class CaretOffsetUpdater {
1543     private final Map<Editor, Integer> myCaretOffsets = new HashMap<Editor, Integer>();
1544
1545     private CaretOffsetUpdater(@NotNull Document document) {
1546       Editor[] editors = EditorFactory.getInstance().getEditors(document);
1547       for (Editor editor : editors) {
1548         myCaretOffsets.put(editor, editor.getCaretModel().getOffset());
1549       }
1550     }
1551
1552     private void update(@NotNull List<? extends TextChange> changes) {
1553       BulkChangesMerger merger = BulkChangesMerger.INSTANCE;
1554       for (Map.Entry<Editor, Integer> entry : myCaretOffsets.entrySet()) {
1555         entry.setValue(merger.updateOffset(entry.getValue(), changes));
1556       }
1557     }
1558
1559     private void restoreCaretLocations() {
1560       for (Map.Entry<Editor, Integer> entry : myCaretOffsets.entrySet()) {
1561         entry.getKey().getCaretModel().moveToOffset(entry.getValue());
1562       }
1563     }
1564   }
1565
1566
1567   public static class FormatOptions {
1568     private CodeStyleSettings mySettings;
1569     private CommonCodeStyleSettings.IndentOptions myIndentOptions;
1570
1571     private FormatTextRanges myAffectedRanges;
1572     private boolean myReformatContext;
1573
1574     private int myInterestingOffset;
1575
1576     public FormatOptions(CodeStyleSettings settings,
1577                          CommonCodeStyleSettings.IndentOptions options,
1578                          FormatTextRanges ranges,
1579                          boolean reformatContext) {
1580       this(settings, options, ranges, reformatContext, -1);
1581     }
1582
1583     public FormatOptions(CodeStyleSettings settings,
1584                          CommonCodeStyleSettings.IndentOptions options,
1585                          FormatTextRanges ranges,
1586                          boolean reformatContext,
1587                          int interestingOffset) {
1588       mySettings = settings;
1589       myIndentOptions = options;
1590       myAffectedRanges = ranges;
1591       myReformatContext = reformatContext;
1592       myInterestingOffset = interestingOffset;
1593     }
1594   }
1595
1596   private class ExpandChildrenIndent extends State {
1597     private Iterator<ExpandableIndent> myIterator;
1598
1599     public ExpandChildrenIndent() {
1600       super(FormattingStateId.EXPANDING_CHILDREN_INDENTS);
1601     }
1602
1603     @Override
1604     protected void doIteration() {
1605       if (myIterator == null) {
1606         myIterator = myExpandableIndents.keySet().iterator();
1607       }
1608       if (!myIterator.hasNext()) {
1609         setDone(true);
1610         return;
1611       }
1612
1613       final ExpandableIndent indent = myIterator.next();
1614       Collection<AbstractBlockWrapper> blocksToExpandIndent = myExpandableIndents.get(indent);
1615       if (shouldExpand(indent, blocksToExpandIndent)) {
1616         for (AbstractBlockWrapper block : blocksToExpandIndent) {
1617           indent.setEnforceIndent(true);
1618           reindentNewLineChildren(block);
1619           indent.setEnforceIndent(false);
1620         }
1621       }
1622     }
1623
1624     private boolean shouldExpand(ExpandableIndent indent, Collection<AbstractBlockWrapper> blocksToExpandIndent) {
1625       for (AbstractBlockWrapper block : blocksToExpandIndent) {
1626         if (!block.getWhiteSpace().containsLineFeeds()) continue;
1627         return true;
1628       }
1629
1630       int strictMinOffset = getStrictMinOffset(indent);
1631       if (strictMinOffset == Integer.MAX_VALUE) {
1632         return false;
1633       }
1634
1635       for (AbstractBlockWrapper block : blocksToExpandIndent) {
1636         int minNewLineChildrenOffset = findMinNewLineIndent(block);
1637         if (minNewLineChildrenOffset <= strictMinOffset) {
1638           return true;
1639         }
1640       }
1641
1642       return false;
1643     }
1644
1645     private int getStrictMinOffset(ExpandableIndent indent) {
1646       final Block minOffsetBlock = indent.getStrictMinOffsetBlock();
1647       if (minOffsetBlock == null) return Integer.MAX_VALUE;
1648
1649       AbstractBlockWrapper wrapper = myExpandableIndentsMinOffsetBlocksToWrappers.get(minOffsetBlock);
1650       if (wrapper.getWhiteSpace().containsLineFeeds()) {
1651         return wrapper.getNumberOfSymbolsBeforeBlock().getTotalSpaces();
1652       }
1653
1654       return Integer.MAX_VALUE;
1655     }
1656
1657     private int findMinNewLineIndent(@NotNull AbstractBlockWrapper block) {
1658       if (block instanceof LeafBlockWrapper && block.getWhiteSpace().containsLineFeeds()) {
1659         return block.getNumberOfSymbolsBeforeBlock().getTotalSpaces();
1660       }
1661       else if (block instanceof CompositeBlockWrapper) {
1662         List<AbstractBlockWrapper> children = ((CompositeBlockWrapper)block).getChildren();
1663         int currentMin = Integer.MAX_VALUE;
1664         for (AbstractBlockWrapper child : children) {
1665           int childIndent = findMinNewLineIndent(child);
1666           if (childIndent < currentMin) {
1667             currentMin = childIndent;
1668           }
1669         }
1670         return currentMin;
1671       }
1672       return Integer.MAX_VALUE;
1673     }
1674
1675     private void reindentNewLineChildren(final @NotNull AbstractBlockWrapper block) {
1676       if (block instanceof LeafBlockWrapper) {
1677         WhiteSpace space = block.getWhiteSpace();
1678
1679         if (space.containsLineFeeds()) {
1680           myCurrentBlock = (LeafBlockWrapper)block;
1681           adjustIndent();
1682         }
1683       }
1684       else if (block instanceof CompositeBlockWrapper) {
1685         List<AbstractBlockWrapper> children = ((CompositeBlockWrapper)block).getChildren();
1686         for (AbstractBlockWrapper childBlock : children) {
1687           reindentNewLineChildren(childBlock);
1688         }
1689       }
1690     }
1691
1692     @Override
1693     protected void prepare() {
1694     }
1695   }
1696 }