platform/lang-impl/src/com/intellij/psi/impl/search/IndexPatternSearcher.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.Language;
  20 import com.intellij.lang.LanguageParserDefinitions;
  21 import com.intellij.lang.ParserDefinition;
  22 import com.intellij.lexer.Lexer;
  23 import com.intellij.openapi.extensions.Extensions;
  24 import com.intellij.openapi.fileTypes.FileType;
  25 import com.intellij.openapi.fileTypes.SyntaxHighlighter;
  26 import com.intellij.openapi.fileTypes.SyntaxHighlighterFactory;
  27 import com.intellij.openapi.fileTypes.impl.AbstractFileType;
  28 import com.intellij.openapi.progress.ProgressManager;
  29 import com.intellij.openapi.util.TextRange;
  30 import com.intellij.openapi.vfs.VirtualFile;
  31 import com.intellij.psi.*;
  32 import com.intellij.psi.impl.PsiManagerEx;
  33 import com.intellij.psi.impl.cache.CacheManager;
  34 import com.intellij.psi.search.IndexPattern;
  35 import com.intellij.psi.search.IndexPatternOccurrence;
  36 import com.intellij.psi.search.IndexPatternProvider;
  37 import com.intellij.psi.search.searches.IndexPatternSearch;
  38 import com.intellij.psi.tree.IElementType;
  39 import com.intellij.psi.tree.TokenSet;
  40 import com.intellij.util.Processor;
  41 import com.intellij.util.QueryExecutor;
  42 import com.intellij.util.text.CharSequenceSubSequence;
  43 import gnu.trove.TIntArrayList;
  44 import org.jetbrains.annotations.NotNull;
  45
  46 import java.util.Set;
  47 import java.util.regex.Matcher;
  48 import java.util.regex.Pattern;
  49
  50 /**
  51  * @author yole
  52  */
  53 public class IndexPatternSearcher implements QueryExecutor<IndexPatternOccurrence, IndexPatternSearch.SearchParameters> {
  54   public boolean execute(@NotNull final IndexPatternSearch.SearchParameters queryParameters, @NotNull final Processor<IndexPatternOccurrence> consumer) {
  55     final PsiFile file = queryParameters.getFile();
  56     VirtualFile virtualFile = file.getVirtualFile();
  57     if (file instanceof PsiBinaryFile || file instanceof PsiCompiledElement || virtualFile == null) {
  58       return true;
  59     }
  60
  61     final CacheManager cacheManager = ((PsiManagerEx)file.getManager()).getCacheManager();
  62     final IndexPatternProvider patternProvider = queryParameters.getPatternProvider();
  63     int count = patternProvider != null
  64                 ? cacheManager.getTodoCount(virtualFile, patternProvider)
  65                 : cacheManager.getTodoCount(virtualFile, queryParameters.getPattern());
  66     if (count == 0) return true;
  67
  68     return executeImpl(queryParameters, consumer);
  69   }
  70
  71   protected boolean executeImpl(IndexPatternSearch.SearchParameters queryParameters,
  72                               Processor<IndexPatternOccurrence> consumer) {
  73     final IndexPatternProvider patternProvider = queryParameters.getPatternProvider();
  74     final PsiFile file = queryParameters.getFile();
  75     TIntArrayList commentStarts = new TIntArrayList();
  76     TIntArrayList commentEnds = new TIntArrayList();
  77
  78     final CharSequence chars = file.getViewProvider().getContents();
  79     findCommentTokenRanges(file, chars, queryParameters.getRange(), commentStarts, commentEnds);
  80
  81     for (int i = 0; i < commentStarts.size(); i++) {
  82       int commentStart = commentStarts.get(i);
  83       int commentEnd = commentEnds.get(i);
  84
  85       if (patternProvider != null) {
  86         for (final IndexPattern pattern : patternProvider.getIndexPatterns()) {
  87           if (!collectPatternMatches(pattern, chars, commentStart, commentEnd, file, queryParameters.getRange(), consumer)) {
  88             return false;
  89           }
  90         }
  91       }
  92       else {
  93         if (!collectPatternMatches(queryParameters.getPattern(), chars, commentStart, commentEnd, file, queryParameters.getRange(),
  94                                    consumer)) {
  95           return false;
  96         }
  97       }
  98     }
  99
 100     return true;
 101   }
 102
 103
 104   private static final TokenSet COMMENT_TOKENS =
 105     TokenSet.create(CustomHighlighterTokenType.LINE_COMMENT, CustomHighlighterTokenType.MULTI_LINE_COMMENT);
 106
 107   private static void findCommentTokenRanges(final PsiFile file,
 108                                              final CharSequence chars,
 109                                              final TextRange range,
 110                                              final TIntArrayList commentStarts,
 111                                              final TIntArrayList commentEnds) {
 112     if (file instanceof PsiPlainTextFile) {
 113       FileType fType = file.getFileType();
 114       synchronized (PsiLock.LOCK) {
 115         if (fType instanceof AbstractFileType) {
 116           Lexer lexer = SyntaxHighlighter.PROVIDER.create(fType, file.getProject(), file.getVirtualFile()).getHighlightingLexer();
 117           findComments(lexer, chars, range, COMMENT_TOKENS, commentStarts, commentEnds, null);
 118         }
 119         else {
 120           commentStarts.add(0);
 121           commentEnds.add(file.getTextLength());
 122         }
 123       }
 124     }
 125     else {
 126       // collect comment offsets to prevent long locks by PsiManagerImpl.LOCK
 127       synchronized (PsiLock.LOCK) {
 128         final FileViewProvider viewProvider = file.getViewProvider();
 129         final Set<Language> relevantLanguages = viewProvider.getLanguages();
 130         for (Language lang : relevantLanguages) {
 131           final TIntArrayList commentStartsList = new TIntArrayList();
 132           final TIntArrayList commentEndsList = new TIntArrayList();
 133
 134           final SyntaxHighlighter syntaxHighlighter =
 135             SyntaxHighlighterFactory.getSyntaxHighlighter(lang, file.getProject(), file.getVirtualFile());
 136           Lexer lexer = syntaxHighlighter.getHighlightingLexer();
 137           TokenSet commentTokens = null;
 138           IndexPatternBuilder builderForFile = null;
 139           for (IndexPatternBuilder builder : Extensions.getExtensions(IndexPatternBuilder.EP_NAME)) {
 140             Lexer lexerFromBuilder = builder.getIndexingLexer(file);
 141             if (lexerFromBuilder != null) {
 142               lexer = lexerFromBuilder;
 143               commentTokens = builder.getCommentTokenSet(file);
 144               builderForFile = builder;
 145             }
 146           }
 147           if (builderForFile == null) {
 148             final ParserDefinition parserDefinition = LanguageParserDefinitions.INSTANCE.forLanguage(lang);
 149             if (parserDefinition != null) {
 150               commentTokens = parserDefinition.getCommentTokens();
 151             }
 152           }
 153
 154           if (commentTokens != null) {
 155             findComments(lexer, chars, range, commentTokens, commentStartsList, commentEndsList, builderForFile);
 156             mergeCommentLists(commentStarts, commentEnds, commentStartsList, commentEndsList);
 157           }
 158         }
 159       }
 160     }
 161   }
 162
 163   private static void mergeCommentLists(TIntArrayList commentStarts,
 164                                        TIntArrayList commentEnds,
 165                                        TIntArrayList commentStartsList,
 166                                        TIntArrayList commentEndsList) {
 167     if (commentStarts.size() == 0 && commentEnds.size() == 0) {
 168       commentStarts.add(commentStartsList.toNativeArray());
 169       commentEnds.add(commentEndsList.toNativeArray());
 170       return;
 171     }
 172
 173     // TODO: this is costly for large N !
 174     for (int i = 0; i < commentStartsList.size(); i++) {
 175       boolean found = false;
 176       for (int j = 0; j < commentStarts.size(); j++) {
 177         if (commentStarts.get(j) == commentStartsList.get(i) && commentEnds.get(j) == commentEndsList.get(i)) {
 178           found = true;
 179           break;
 180         }
 181       }
 182       if (!found) {
 183         commentStarts.add(commentStartsList.get(i));
 184         commentEnds.add(commentEndsList.get(i));
 185       }
 186     }
 187   }
 188
 189   private static void findComments(final Lexer lexer,
 190                                    final CharSequence chars,
 191                                    final TextRange range,
 192                                    final TokenSet commentTokens,
 193                                    final TIntArrayList commentStarts,
 194                                    final TIntArrayList commentEnds,
 195                                    final IndexPatternBuilder builderForFile) {
 196     for (lexer.start(chars); ; lexer.advance()) {
 197       IElementType tokenType = lexer.getTokenType();
 198       if (tokenType == null) break;
 199
 200       if (range != null) {
 201         if (lexer.getTokenEnd() <= range.getStartOffset()) continue;
 202         if (lexer.getTokenStart() >= range.getEndOffset()) break;
 203       }
 204
 205       boolean isComment = commentTokens.contains(tokenType);
 206       if (!isComment) {
 207         final Language commentLang = tokenType.getLanguage();
 208         final ParserDefinition parserDefinition = LanguageParserDefinitions.INSTANCE.forLanguage(commentLang);
 209         if (parserDefinition != null) {
 210           final TokenSet langCommentTokens = parserDefinition.getCommentTokens();
 211           isComment = langCommentTokens.contains(tokenType);
 212         }
 213       }
 214
 215       if (isComment) {
 216         final int startDelta = builderForFile != null ? builderForFile.getCommentStartDelta(lexer.getTokenType()) : 0;
 217         final int endDelta = builderForFile != null ? builderForFile.getCommentEndDelta(lexer.getTokenType()) : 0;
 218
 219         int start = lexer.getTokenStart() + startDelta;
 220         int end = lexer.getTokenEnd() - endDelta;
 221         assert start <= end : "Invalid comment range: " +
 222                               new TextRange(start, end) +
 223                               "; lexer token range=" +
 224                               new TextRange(lexer.getTokenStart(), lexer.getTokenEnd()) +
 225                               "; delta=" +
 226                               new TextRange(startDelta, endDelta) +
 227                               "; lexer=" +
 228                               lexer +
 229                               "; builder=" +
 230                               builderForFile +
 231                               "; chars length:" +
 232                               chars.length();
 233         assert end <= chars.length() : "Invalid comment end: " +
 234                                        new TextRange(start, end) +
 235                                        "; lexer token range=" +
 236                                        new TextRange(lexer.getTokenStart(), lexer.getTokenEnd()) +
 237                                        "; delta=" +
 238                                        new TextRange(startDelta, endDelta) +
 239                                        "; lexer=" +
 240                                        lexer +
 241                                        "; builder=" +
 242                                        builderForFile +
 243                                        "; chars length:" +
 244                                        chars.length();
 245         commentStarts.add(start);
 246         commentEnds.add(end);
 247       }
 248     }
 249   }
 250
 251   private static boolean collectPatternMatches(IndexPattern indexPattern,
 252                                                CharSequence chars,
 253                                                int commentStart,
 254                                                int commentEnd,
 255                                                PsiFile file,
 256                                                TextRange range,
 257                                                Processor<IndexPatternOccurrence> consumer) {
 258     Pattern pattern = indexPattern.getPattern();
 259     if (pattern != null) {
 260       ProgressManager.checkCanceled();
 261
 262       CharSequence input = new CharSequenceSubSequence(chars, commentStart, commentEnd);
 263       Matcher matcher = pattern.matcher(input);
 264       while (true) {
 265         //long time1 = System.currentTimeMillis();
 266         boolean found = matcher.find();
 267         //long time2 = System.currentTimeMillis();
 268         //System.out.println("scanned text of length " + (lexer.getTokenEnd() - lexer.getTokenStart() + " in " + (time2 - time1) + " ms"));
 269
 270         if (!found) break;
 271         int start = matcher.start() + commentStart;
 272         int end = matcher.end() + commentStart;
 273         if (start != end) {
 274           if (range == null || range.getStartOffset() <= start && end <= range.getEndOffset()) {
 275             if (!consumer.process(new IndexPatternOccurrenceImpl(file, start, end, indexPattern))) {
 276               return false;
 277             }
 278           }
 279         }
 280
 281         ProgressManager.checkCanceled();
 282       }
 283     }
 284     return true;
 285   }
 286 }