platform/lang-api/src/com/intellij/psi/WalkingState.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;
  18
  19 import org.jetbrains.annotations.NotNull;
  20
  21 /**
  22  * @author cdr
  23  */
  24 public abstract class WalkingState<T> {
  25   public interface TreeGuide<T> {
  26     T getNextSibling(@NotNull T element);
  27     T getPrevSibling(@NotNull T element);
  28     T getFirstChild(@NotNull T element);
  29     T getParent(@NotNull T element);
  30   }
  31   private boolean isDown;
  32   protected boolean startedWalking;
  33   private final TreeGuide<T> myWalker;
  34   private boolean stopped;
  35
  36   public abstract void elementFinished(@NotNull T element);
  37
  38   protected WalkingState(@NotNull TreeGuide<T> delegate) {
  39     myWalker = delegate;
  40   }
  41
  42   public void visit(@NotNull T element) {
  43     elementStarted(element);
  44   }
  45
  46   public void elementStarted(@NotNull T element){
  47     isDown = true;
  48     if (!startedWalking) {
  49       stopped = false;
  50       startedWalking = true;
  51       walkChildren(element);
  52       startedWalking = false;
  53     }
  54   }
  55
  56   private void walkChildren(T root) {
  57     for (T element = next(root,root,isDown); element != null && !stopped; element = next(element, root, isDown)) {
  58       isDown = false; // if client visitor did not call default visitElement it means skip subtree
  59       T parent = myWalker.getParent(element);
  60       T next = myWalker.getNextSibling(element);
  61       visit(element);
  62       assert myWalker.getNextSibling(element) == next : "Next sibling of the element '"+element+"' changed. Was: "+next+"; Now:"+myWalker.getNextSibling(element)+"; Root:"+root;
  63       assert myWalker.getParent(element) == parent : "Parent of the element '"+element+"' changed. Was: "+parent+"; Now:"+myWalker.getParent(element)+"; Root:"+root;
  64     }
  65   }
  66
  67   private T next(T element, T root, boolean isDown) {
  68     if (isDown) {
  69       T child = myWalker.getFirstChild(element);
  70       if (child != null) return child;
  71     }
  72     // up
  73     while (element != root && element!=null) {
  74       T next = myWalker.getNextSibling(element);
  75
  76       elementFinished(element);
  77       if (next != null) {
  78         Object nextPrev = myWalker.getPrevSibling(next);
  79         if (nextPrev != element) {
  80           String msg = "Element: " + element + "; next: "+next+"; next.prev: " + nextPrev;
  81           while (true) {
  82             T top = myWalker.getParent(element);
  83             if (top == null) break;
  84             element = top;
  85           }
  86           assert false : msg+" Top:"+element;
  87         }
  88         return next;
  89       }
  90       element = myWalker.getParent(element);
  91     }
  92     elementFinished(element);
  93     return null;
  94   }
  95
  96   public void startedWalking() {
  97     startedWalking = true;
  98   }
  99
 100   public void stopWalking() {
 101     stopped = true;
 102   }
 103 }