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