platform/lang-impl/src/com/intellij/psi/impl/source/tree/CompositeElement.java

   1 /*
   2  * Copyright 2000-2009 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.psi.impl.source.tree;
  18
  19 import com.intellij.extapi.psi.ASTDelegatePsiElement;
  20 import com.intellij.lang.*;
  21 import com.intellij.openapi.application.ApplicationManager;
  22 import com.intellij.openapi.diagnostic.Logger;
  23 import com.intellij.pom.tree.events.ChangeInfo;
  24 import com.intellij.pom.tree.events.TreeChangeEvent;
  25 import com.intellij.pom.tree.events.impl.ChangeInfoImpl;
  26 import com.intellij.pom.tree.events.impl.ReplaceChangeInfoImpl;
  27 import com.intellij.psi.PsiElement;
  28 import com.intellij.psi.PsiFile;
  29 import com.intellij.psi.PsiLock;
  30 import com.intellij.psi.impl.DebugUtil;
  31 import com.intellij.psi.impl.source.DummyHolder;
  32 import com.intellij.psi.impl.source.DummyHolderFactory;
  33 import com.intellij.psi.impl.source.PsiElementArrayConstructor;
  34 import com.intellij.psi.impl.source.SourceTreeToPsiMap;
  35 import com.intellij.psi.impl.source.codeStyle.CodeEditUtil;
  36 import com.intellij.psi.tree.IElementType;
  37 import com.intellij.psi.tree.TokenSet;
  38 import com.intellij.util.text.CharArrayCharSequence;
  39 import org.jetbrains.annotations.NotNull;
  40 import org.jetbrains.annotations.Nullable;
  41
  42 public class CompositeElement extends TreeElement {
  43   private static final Logger LOG = Logger.getInstance("#com.intellij.psi.impl.source.tree.CompositeElement");
  44
  45   private TreeElement firstChild = null;
  46   private TreeElement lastChild = null;
  47
  48   private volatile int myModificationsCount = 0;
  49   private static final int NOT_CACHED = -239;
  50   private volatile int myCachedLength = NOT_CACHED;
  51   private volatile int myHC = -1;
  52   private volatile PsiElement myWrapper = null;
  53
  54   public CompositeElement(@NotNull IElementType type) {
  55     super(type);
  56   }
  57
  58   public int getModificationCount() {
  59     return myModificationsCount;
  60   }
  61
  62   public Object clone() {
  63     CompositeElement clone = (CompositeElement)super.clone();
  64
  65     clone.clearCaches();
  66     clone.firstChild = null;
  67     clone.lastChild = null;
  68     clone.myModificationsCount = 0;
  69     clone.myWrapper = null;
  70     for (ASTNode child = rawFirstChild(); child != null; child = child.getTreeNext()) {
  71       clone.rawAddChildren((TreeElement)child.clone());
  72     }
  73     return clone;
  74   }
  75
  76   public void subtreeChanged() {
  77     clearCaches();
  78     if (!(this instanceof PsiElement)) {
  79       final PsiElement psi = getPsi();
  80       if (psi instanceof ASTDelegatePsiElement) {
  81         ((ASTDelegatePsiElement)psi).subtreeChanged();
  82       }
  83       else if (psi instanceof PsiFile) {
  84         ((PsiFile)psi).subtreeChanged();
  85       }
  86     }
  87
  88     CompositeElement treeParent = getTreeParent();
  89     if (treeParent != null) treeParent.subtreeChanged();
  90   }
  91
  92   public void clearCaches() {
  93     super.clearCaches();
  94     myCachedLength = NOT_CACHED;
  95
  96     myModificationsCount++;
  97     myHC = -1;
  98
  99     clearRelativeOffsets(rawFirstChild());
 100   }
 101
 102   public void acceptTree(TreeElementVisitor visitor) {
 103     visitor.visitComposite(this);
 104   }
 105
 106   public LeafElement findLeafElementAt(int offset) {
 107     TreeElement child = getFirstChildNode();
 108     while (child != null) {
 109       final int textLength = child.getTextLength();
 110       if (textLength > offset) {
 111         if (child instanceof ForeignLeafPsiElement) {
 112           continue;
 113         }
 114         return child.findLeafElementAt(offset);
 115       }
 116       offset -= textLength;
 117       child = child.getTreeNext();
 118     }
 119     return null;
 120   }
 121
 122   public ASTNode findChildByType(IElementType type) {
 123     if (DebugUtil.CHECK_INSIDE_ATOMIC_ACTION_ENABLED){
 124       ApplicationManager.getApplication().assertReadAccessAllowed();
 125     }
 126
 127     for(ASTNode element = getFirstChildNode(); element != null; element = element.getTreeNext()){
 128       if (element.getElementType() == type) return element;
 129     }
 130     return null;
 131   }
 132
 133   @Nullable
 134   public ASTNode findChildByType(@NotNull TokenSet types) {
 135     if (DebugUtil.CHECK_INSIDE_ATOMIC_ACTION_ENABLED){
 136       ApplicationManager.getApplication().assertReadAccessAllowed();
 137     }
 138     for(ASTNode element = getFirstChildNode(); element != null; element = element.getTreeNext()){
 139       if (types.contains(element.getElementType())) return element;
 140     }
 141     return null;
 142   }
 143
 144   @Nullable
 145   public ASTNode findChildByType(@NotNull TokenSet typesSet, ASTNode anchor) {
 146     ASTNode child = anchor;
 147     while (true) {
 148       if (child == null) return null;
 149       if (typesSet.contains(child.getElementType())) return child;
 150       child = child.getTreeNext();
 151     }
 152   }
 153
 154   @NotNull
 155   public String getText() {
 156     char[] buffer = new char[getTextLength()];
 157     AstBufferUtil.toBuffer(this, buffer, 0);
 158     return new String(buffer);
 159   }
 160
 161   public CharSequence getChars() {
 162     char[] buffer = new char[getTextLength()];
 163     AstBufferUtil.toBuffer(this, buffer, 0);
 164     return new CharArrayCharSequence(buffer);
 165   }
 166
 167   public int getNotCachedLength() {
 168     int length = 0;
 169     TreeElement child = getFirstChildNode();
 170     while(child != null){
 171       length += child.getNotCachedLength();
 172       child = child.getTreeNext();
 173     }
 174     return length;
 175   }
 176
 177   @NotNull
 178   public char[] textToCharArray() {
 179     char[] buffer = new char[getTextLength()];
 180     AstBufferUtil.toBuffer(this, buffer, 0);
 181     return buffer;
 182   }
 183
 184   public boolean textContains(char c) {
 185     for (ASTNode child = getFirstChildNode(); child != null; child = child.getTreeNext()) {
 186       if (child.textContains(c)) return true;
 187     }
 188     return false;
 189   }
 190
 191   protected int textMatches(CharSequence buffer, int start) {
 192     int curOffset = start;
 193     for (TreeElement child = getFirstChildNode(); child != null; child = child.getTreeNext()) {
 194       curOffset = child.textMatches(buffer, curOffset);
 195       if (curOffset == -1) return -1;
 196     }
 197     return curOffset;
 198   }
 199
 200
 201   public final PsiElement findChildByRoleAsPsiElement(int role) {
 202     ASTNode element = findChildByRole(role);
 203     if (element == null) return null;
 204     return SourceTreeToPsiMap.treeElementToPsi(element);
 205   }
 206
 207   @Nullable
 208   public ASTNode findChildByRole(int role) {
 209     // assert ChildRole.isUnique(role);
 210     for (ASTNode child = getFirstChildNode(); child != null; child = child.getTreeNext()) {
 211       if (getChildRole(child) == role) return child;
 212     }
 213     return null;
 214   }
 215
 216   public int getChildRole(ASTNode child) {
 217     assert child.getTreeParent() == this;
 218     return 0; //ChildRole.NONE;
 219   }
 220
 221   protected final int getChildRole(ASTNode child, int roleCandidate) {
 222     if (findChildByRole(roleCandidate) == child) {
 223       return roleCandidate;
 224     }
 225     else {
 226       return 0; //ChildRole.NONE;
 227     }
 228   }
 229
 230   public ASTNode[] getChildren(TokenSet filter) {
 231     int count = countChildren(filter);
 232     if (count == 0) {
 233       return EMPTY_ARRAY;
 234     }
 235     final ASTNode[] result = new ASTNode[count];
 236     count = 0;
 237     for (ASTNode child = getFirstChildNode(); child != null; child = child.getTreeNext()) {
 238       if (filter == null || filter.contains(child.getElementType())) {
 239         result[count++] = child;
 240       }
 241     }
 242     return result;
 243   }
 244
 245
 246   @NotNull
 247   public <T extends PsiElement> T[] getChildrenAsPsiElements(TokenSet filter, PsiElementArrayConstructor<T> constructor) {
 248     ApplicationManager.getApplication().assertReadAccessAllowed();
 249     int count = countChildren(filter);
 250     T[] result = constructor.newPsiElementArray(count);
 251     if (count == 0) {
 252       return result;
 253     }
 254     int idx = 0;
 255     for (ASTNode child = getFirstChildNode(); child != null && idx < count; child = child.getTreeNext()) {
 256       if (filter == null || filter.contains(child.getElementType())) {
 257         T element = (T)child.getPsi();
 258         assert element != null;
 259         result[idx++] = element;
 260       }
 261     }
 262     return result;
 263   }
 264
 265   public int countChildren(TokenSet filter) {
 266     // no lock is needed because all chameleons are expanded already
 267     int count = 0;
 268     for (ASTNode child = getFirstChildNode(); child != null; child = child.getTreeNext()) {
 269       if (filter == null || filter.contains(child.getElementType())) {
 270         count++;
 271       }
 272     }
 273
 274     return count;
 275   }
 276
 277   /**
 278    * @return First element that was appended (for example whitespaces could be skipped)
 279    */
 280   public TreeElement addInternal(TreeElement first, ASTNode last, ASTNode anchor, Boolean before) {
 281     ASTNode anchorBefore;
 282     if (anchor != null) {
 283       anchorBefore = before.booleanValue() ? anchor : anchor.getTreeNext();
 284     }
 285     else {
 286       anchorBefore = before == null || before.booleanValue() ? null : getFirstChildNode();
 287     }
 288     return (TreeElement)CodeEditUtil.addChildren(this, first, last, anchorBefore);
 289   }
 290
 291   public void deleteChildInternal(@NotNull ASTNode child) {
 292     CodeEditUtil.removeChild(this, child);
 293   }
 294
 295   public void replaceChildInternal(@NotNull ASTNode child, @NotNull TreeElement newElement) {
 296     CodeEditUtil.replaceChild(this, child, newElement);
 297   }
 298
 299   public int getTextLength() {
 300     int cachedLength = myCachedLength;
 301     if (cachedLength >= 0) return cachedLength;
 302
 303     synchronized (START_OFFSET_LOCK) {
 304       walkCachingLength();
 305       return myCachedLength;
 306     }
 307   }
 308
 309   public int hc() {
 310     int hc = myHC;
 311     if (hc == -1) {
 312       hc = 0;
 313       TreeElement child = firstChild;
 314       while (child != null) {
 315         hc += child.hc();
 316         child = child.getTreeNext();
 317       }
 318       myHC = hc;
 319     }
 320     return hc;
 321   }
 322
 323   public int getCachedLength() {
 324     return myCachedLength;
 325   }
 326
 327   private void walkCachingLength() {
 328     TreeElement cur = this;
 329
 330     while (cur != null) {
 331       cur = next(cur, cur.getCachedLength() == NOT_CACHED);
 332     }
 333
 334     assert myCachedLength >= 0;
 335   }
 336
 337   @Nullable
 338   private TreeElement next(TreeElement cur, boolean down) {
 339     if (down) {
 340       CompositeElement composite = (CompositeElement)cur; // It's a composite or we won't be going down
 341       TreeElement child = composite.firstChild;
 342       if (child != null) {
 343         LOG.assertTrue(child.getTreeParent() == composite, cur);
 344         return child;
 345       }
 346
 347       composite.myCachedLength = 0;
 348     }
 349
 350     // up
 351     while (cur != this) {
 352       CompositeElement parent = cur.getTreeParent();
 353       parent.myCachedLength -= cur.getCachedLength();
 354
 355       TreeElement next = cur.getTreeNext();
 356       if (next != null) {
 357         LOG.assertTrue(next.getTreePrev() == cur, cur);
 358         return next;
 359       }
 360
 361       parent.myCachedLength = -parent.myCachedLength + NOT_CACHED;
 362
 363       cur = parent;
 364     }
 365
 366     return null;
 367   }
 368
 369
 370   public TreeElement getFirstChildNode() {
 371     return firstChild;
 372   }
 373
 374   public TreeElement getLastChildNode() {
 375     return lastChild;
 376   }
 377
 378   public void setFirstChildNode(TreeElement firstChild) {
 379     this.firstChild = firstChild;
 380   }
 381
 382   public void setLastChildNode(TreeElement lastChild) {
 383     this.lastChild = lastChild;
 384   }
 385
 386   public void addChild(@NotNull ASTNode child, final ASTNode anchorBefore) {
 387     LOG.assertTrue(anchorBefore == null || ((TreeElement)anchorBefore).getTreeParent() == this, "anchorBefore == null || anchorBefore.getTreeParent() == parent");
 388     TreeUtil.ensureParsed(getFirstChildNode());
 389     TreeUtil.ensureParsed(child);
 390     final TreeElement last = ((TreeElement)child).getTreeNext();
 391     final TreeElement first = (TreeElement)child;
 392
 393     removeChildrenInner(first, last);
 394
 395     ChangeUtil.prepareAndRunChangeAction(new ChangeUtil.ChangeAction(){
 396       public void makeChange(TreeChangeEvent destinationTreeChange) {
 397         if (anchorBefore != null) {
 398           insertBefore(destinationTreeChange, (TreeElement)anchorBefore, first);
 399         }
 400         else {
 401           add(destinationTreeChange, CompositeElement.this, first);
 402         }
 403       }
 404     }, this);
 405   }
 406
 407   public void addLeaf(@NotNull final IElementType leafType, final CharSequence leafText, final ASTNode anchorBefore) {
 408     FileElement holder = new DummyHolder(getManager(), null).getTreeElement();
 409     final LeafElement leaf = ASTFactory.leaf(leafType, holder.getCharTable().intern(leafText));
 410     CodeEditUtil.setNodeGenerated(leaf, true);
 411     holder.rawAddChildren(leaf);
 412
 413     addChild(leaf, anchorBefore);
 414   }
 415
 416   public void addChild(@NotNull ASTNode child) {
 417     addChild(child, null);
 418   }
 419
 420   public void removeChild(@NotNull ASTNode child) {
 421     removeChildInner((TreeElement)child);
 422   }
 423
 424   public void removeRange(@NotNull ASTNode first, ASTNode firstWhichStayInTree) {
 425     removeChildrenInner((TreeElement)first, (TreeElement)firstWhichStayInTree);
 426   }
 427
 428   public void replaceChild(@NotNull ASTNode oldChild, @NotNull ASTNode newChild) {
 429     LOG.assertTrue(((TreeElement)oldChild).getTreeParent() == this);
 430     final TreeElement oldChild1 = (TreeElement)oldChild;
 431     final TreeElement newChildNext = ((TreeElement)newChild).getTreeNext();
 432     final TreeElement newChild1 = (TreeElement)newChild;
 433
 434     if(oldChild1 == newChild1) return;
 435
 436     removeChildrenInner(newChild1, newChildNext);
 437
 438     ChangeUtil.prepareAndRunChangeAction(new ChangeUtil.ChangeAction(){
 439       public void makeChange(TreeChangeEvent destinationTreeChange) {
 440         replace(destinationTreeChange, oldChild1, newChild1);
 441         repairRemovedElement(CompositeElement.this, oldChild1);
 442       }
 443     }, this);
 444   }
 445
 446   public void replaceAllChildrenToChildrenOf(final ASTNode anotherParent) {
 447     TreeUtil.ensureParsed(getFirstChildNode());
 448     TreeUtil.ensureParsed(anotherParent.getFirstChildNode());
 449     final ASTNode firstChild1 = anotherParent.getFirstChildNode();
 450     ChangeUtil.prepareAndRunChangeAction(new ChangeUtil.ChangeAction(){
 451       public void makeChange(TreeChangeEvent destinationTreeChange) {
 452         destinationTreeChange.addElementaryChange(anotherParent, ChangeInfoImpl.create(ChangeInfo.CONTENTS_CHANGED, anotherParent));
 453         ((CompositeElement)anotherParent).rawRemoveAllChildren();
 454       }
 455     }, (TreeElement)anotherParent);
 456
 457     if (firstChild1 != null) {
 458       ChangeUtil.prepareAndRunChangeAction(new ChangeUtil.ChangeAction(){
 459         public void makeChange(TreeChangeEvent destinationTreeChange) {
 460           if(getTreeParent() != null){
 461             final ChangeInfoImpl changeInfo = ChangeInfoImpl.create(ChangeInfo.CONTENTS_CHANGED, CompositeElement.this);
 462             changeInfo.setOldLength(getTextLength());
 463             destinationTreeChange.addElementaryChange(CompositeElement.this, changeInfo);
 464             rawRemoveAllChildren();
 465             rawAddChildren((TreeElement)firstChild1);
 466           }
 467           else{
 468             final TreeElement first = getFirstChildNode();
 469             remove(destinationTreeChange, first, null);
 470             add(destinationTreeChange, CompositeElement.this, (TreeElement)firstChild1);
 471             repairRemovedElement(CompositeElement.this, first);
 472           }
 473         }
 474       }, this);
 475     }
 476     else {
 477       removeAllChildren();
 478     }
 479   }
 480
 481   public void removeAllChildren() {
 482     final TreeElement child = getFirstChildNode();
 483     if (child != null) {
 484       removeRange(child, null);
 485     }
 486   }
 487
 488   public void addChildren(ASTNode firstChild, ASTNode lastChild, ASTNode anchorBefore) {
 489     while (firstChild != lastChild) {
 490       final ASTNode next1 = firstChild.getTreeNext();
 491       addChild(firstChild, anchorBefore);
 492       firstChild = next1;
 493     }
 494   }
 495
 496   public PsiElement getPsi() {
 497     PsiElement wrapper = myWrapper;
 498     if (wrapper != null) return wrapper;
 499
 500     synchronized (PsiLock.LOCK) {
 501       wrapper = myWrapper;
 502       if (wrapper != null) return wrapper;
 503
 504       final Language lang = getElementType().getLanguage();
 505       final ParserDefinition parserDefinition = LanguageParserDefinitions.INSTANCE.forLanguage(lang);
 506       if (parserDefinition != null) {
 507         myWrapper = wrapper = parserDefinition.createElement(this);
 508         //noinspection ConstantConditions
 509         LOG.assertTrue(wrapper != null, "ParserDefinition.createElement() may not return null");
 510       }
 511
 512       return wrapper;
 513     }
 514   }
 515
 516   public void setPsi(@NotNull PsiElement psi) {
 517     myWrapper = psi;
 518   }
 519
 520   public void rawAddChildren(@NotNull TreeElement first) {
 521     final TreeElement last = getLastChildNode();
 522     if (last == null){
 523       setFirstChildNode(first);
 524       first.setTreePrev(null);
 525       while(true){
 526         final TreeElement treeNext = first.getTreeNext();
 527         first.setTreeParent(this);
 528         if(treeNext == null) break;
 529         first = treeNext;
 530       }
 531       setLastChildNode(first);
 532       first.setTreeParent(this);
 533     }
 534     else {
 535       last.rawInsertAfterMe(first);
 536     }
 537
 538     if (DebugUtil.CHECK) DebugUtil.checkTreeStructure(this);
 539   }
 540
 541   public void rawRemoveAllChildren() {
 542     TreeElement first = getFirstChildNode();
 543     if (first != null) {
 544       first.rawRemoveUpToLast();
 545     }
 546   }
 547
 548   private static void repairRemovedElement(final CompositeElement oldParent, final TreeElement oldChild) {
 549     if(oldChild == null) return;
 550     final FileElement treeElement = DummyHolderFactory.createHolder(oldParent.getManager(), null, false).getTreeElement();
 551     treeElement.rawAddChildren(oldChild);
 552   }
 553
 554   private static void add(final TreeChangeEvent destinationTreeChange,
 555                           final CompositeElement parent,
 556                           final TreeElement first) {
 557     parent.rawAddChildren(first);
 558     TreeElement child = first;
 559     while(child != null){
 560       destinationTreeChange.addElementaryChange(child, ChangeInfoImpl.create(ChangeInfo.ADD, child));
 561       child = child.getTreeNext();
 562     }
 563   }
 564
 565   private static void remove(final TreeChangeEvent destinationTreeChange,
 566                              final TreeElement first,
 567                              final TreeElement last) {
 568     if (first != null) {
 569       TreeElement child = first;
 570       while(child != last && child != null){
 571         destinationTreeChange.addElementaryChange(child, ChangeInfoImpl.create(ChangeInfo.REMOVED, child));
 572         child = child.getTreeNext();
 573       }
 574
 575       first.rawRemoveUpTo(last);
 576     }
 577   }
 578
 579   private static void insertBefore(final TreeChangeEvent destinationTreeChange,
 580                                    final TreeElement anchorBefore,
 581                                    final TreeElement first) {
 582     anchorBefore.rawInsertBeforeMe(first);
 583     TreeElement child = first;
 584     while(child != anchorBefore){
 585       destinationTreeChange.addElementaryChange(child, ChangeInfoImpl.create(ChangeInfo.ADD, child));
 586       child = child.getTreeNext();
 587     }
 588   }
 589
 590   private static void replace(final TreeChangeEvent sourceTreeChange,
 591                               final TreeElement oldChild,
 592                               final TreeElement newChild) {
 593     oldChild.rawReplaceWithList(newChild);
 594     final ReplaceChangeInfoImpl change = (ReplaceChangeInfoImpl)ChangeInfoImpl.create(ChangeInfo.REPLACE, newChild);
 595     sourceTreeChange.addElementaryChange(newChild, change);
 596     change.setReplaced(oldChild);
 597   }
 598
 599   private static void removeChildInner(final TreeElement child) {
 600     removeChildrenInner(child, child.getTreeNext());
 601   }
 602
 603   private static void removeChildrenInner(final TreeElement first, final TreeElement last) {
 604     final FileElement fileElement = TreeUtil.getFileElement(first);
 605     if (fileElement != null) {
 606       ChangeUtil.prepareAndRunChangeAction(new ChangeUtil.ChangeAction() {
 607         public void makeChange(TreeChangeEvent destinationTreeChange) {
 608           remove(destinationTreeChange, first, last);
 609           repairRemovedElement(fileElement, first);
 610         }
 611       }, first.getTreeParent());
 612     }
 613     else {
 614       first.rawRemoveUpTo(last);
 615     }
 616   }
 617
 618
 619   public TreeElement rawFirstChild() {
 620     return firstChild;
 621   }
 622
 623   public TreeElement rawLastChild() {
 624     return lastChild;
 625   }
 626 }