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 }