platform/lang-impl/src/com/intellij/psi/impl/search/LowLevelSearchUtil.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.search;
  18
  19 import com.intellij.lang.ASTNode;
  20 import com.intellij.openapi.diagnostic.Logger;
  21 import com.intellij.openapi.progress.ProgressManager;
  22 import com.intellij.openapi.util.Pair;
  23 import com.intellij.openapi.util.TextRange;
  24 import com.intellij.psi.PsiElement;
  25 import com.intellij.psi.PsiFile;
  26 import com.intellij.psi.PsiLanguageInjectionHost;
  27 import com.intellij.psi.impl.source.tree.LeafElement;
  28 import com.intellij.psi.impl.source.tree.TreeElement;
  29 import com.intellij.psi.search.TextOccurenceProcessor;
  30 import com.intellij.psi.util.PsiTreeUtil;
  31 import com.intellij.util.text.StringSearcher;
  32
  33 import java.util.List;
  34
  35 public class LowLevelSearchUtil {
  36   private static final Logger LOG = Logger.getInstance("#com.intellij.psi.impl.search.LowLevelSearchUtil");
  37
  38   private LowLevelSearchUtil() {
  39   }
  40
  41   // TRUE/FALSE -> injected psi has been discovered and processor returned true/false;
  42   // null -> there were nothing injected found
  43   private static Boolean processInjectedFile(PsiElement element, final TextOccurenceProcessor processor, final StringSearcher searcher) {
  44     if (!(element instanceof PsiLanguageInjectionHost)) return null;
  45     List<Pair<PsiElement,TextRange>> list = ((PsiLanguageInjectionHost)element).getInjectedPsi();
  46     if (list == null) return null;
  47     for (Pair<PsiElement, TextRange> pair : list) {
  48       final PsiElement injected = pair.getFirst();
  49       if (!processElementsContainingWordInElement(processor, injected, searcher, false)) return Boolean.FALSE;
  50     }
  51     return Boolean.TRUE;
  52   }
  53
  54   private static boolean processTreeUp(final TextOccurenceProcessor processor,
  55                                        final PsiElement scope,
  56                                        final StringSearcher searcher,
  57                                        final int offset,
  58                                        final boolean ignoreInjectedPsi) {
  59     final int scopeStartOffset = scope.getTextRange().getStartOffset();
  60     final int patternLength = searcher.getPatternLength();
  61     PsiElement leafElement = null;
  62     TreeElement leafNode = null;
  63     ASTNode scopeNode = scope.getNode();
  64     boolean useTree = scopeNode != null;
  65
  66     int start;
  67     if (useTree) {
  68       leafNode = (LeafElement)scopeNode.findLeafElementAt(offset);
  69       if (leafNode == null) return true;
  70       start = offset - leafNode.getStartOffset() + scopeStartOffset;
  71     }
  72     else {
  73       if (scope instanceof PsiFile) {
  74         leafElement = ((PsiFile)scope).getViewProvider().findElementAt(offset, scope.getLanguage());
  75       }
  76       else {
  77         leafElement = scope.findElementAt(offset);
  78       }
  79       if (leafElement == null) return true;
  80       start = offset - leafElement.getTextRange().getStartOffset() + scopeStartOffset;
  81     }
  82     if (start < 0) {
  83       LOG.error("offset=" + offset + " scopeStartOffset=" + scopeStartOffset + " leafElement=" + leafElement + " " +
  84                                   " scope=" + scope.toString());
  85     }
  86     boolean contains = false;
  87     PsiElement prev = null;
  88     TreeElement prevNode = null;
  89     PsiElement run = null;
  90     while (run != scope) {
  91       if (useTree) {
  92         start += prevNode == null ? 0 : prevNode.getStartOffsetInParent();
  93         prevNode = leafNode;
  94         run = leafNode.getPsi();
  95       }
  96       else {
  97         start += prev == null ? 0 : prev.getStartOffsetInParent();
  98         prev = run;
  99         run = leafElement;
 100       }
 101       contains |= run.getTextLength() - start >= patternLength;  //do not compute if already contains
 102       if (contains) {
 103         if (!ignoreInjectedPsi) {
 104           Boolean result = processInjectedFile(run, processor, searcher);
 105           if (result != null) return result.booleanValue();
 106         }
 107         if (!processor.execute(run, start)) return false;
 108       }
 109       if (useTree) {
 110         leafNode = leafNode.getTreeParent();
 111         if (leafNode == null) break;
 112       }
 113       else {
 114         leafElement = leafElement.getParent();
 115         if (leafElement == null) break;
 116       }
 117     }
 118     assert run == scope: "Malbuilt PSI: scopeNode="+scope+"; leafNode="+run+"; isAncestor="+ PsiTreeUtil.isAncestor(scope, run, false);
 119
 120     return true;
 121   }
 122   //@RequiresReadAction
 123   public static boolean processElementsContainingWordInElement(final TextOccurenceProcessor processor,
 124                                                                final PsiElement scope,
 125                                                                final StringSearcher searcher,
 126                                                                final boolean ignoreInjectedPsi) {
 127     ProgressManager.checkCanceled();
 128
 129     PsiFile file = scope.getContainingFile();
 130     final CharSequence buffer = file.getViewProvider().getContents();
 131
 132     TextRange range = scope.getTextRange();
 133     int scopeStart = range.getStartOffset();
 134     int startOffset = scopeStart;
 135     int endOffset = range.getEndOffset();
 136
 137     do {
 138       startOffset  = searchWord(buffer, startOffset, endOffset, searcher);
 139       if (startOffset < 0) {
 140         return true;
 141       }
 142       if (!processTreeUp(processor, scope, searcher, startOffset - scopeStart, ignoreInjectedPsi)) return false;
 143
 144       startOffset++;
 145     }
 146     while (startOffset < endOffset);
 147
 148     return true;
 149   }
 150
 151   public static int searchWord(CharSequence text, int startOffset, int endOffset, StringSearcher searcher) {
 152     for (int index = startOffset; index < endOffset; index++) {
 153       //noinspection AssignmentToForLoopParameter
 154       index = searcher.scan(text, index, endOffset);
 155       if (index < 0) return -1;
 156       if (!searcher.isJavaIdentifier()) {
 157         return index;
 158       }
 159
 160       if (index > startOffset) {
 161         char c = text.charAt(index - 1);
 162         if (Character.isJavaIdentifierPart(c) && c != '$') {
 163           if (index < 2 || text.charAt(index - 2) != '\\') { //escape sequence
 164             continue;
 165           }
 166         }
 167       }
 168
 169       String pattern = searcher.getPattern();
 170       if (index + pattern.length() < endOffset) {
 171         char c = text.charAt(index + pattern.length());
 172         if (Character.isJavaIdentifierPart(c) && c != '$') {
 173           continue;
 174         }
 175       }
 176       return index;
 177     }
 178     return -1;
 179   }
 180 }