diff options
Diffstat (limited to 'platform/structuralsearch/source/com/intellij/structuralsearch/impl/matcher/MatcherImpl.java')
-rw-r--r-- | platform/structuralsearch/source/com/intellij/structuralsearch/impl/matcher/MatcherImpl.java | 737 |
1 files changed, 737 insertions, 0 deletions
diff --git a/platform/structuralsearch/source/com/intellij/structuralsearch/impl/matcher/MatcherImpl.java b/platform/structuralsearch/source/com/intellij/structuralsearch/impl/matcher/MatcherImpl.java new file mode 100644 index 000000000000..d667b068ee48 --- /dev/null +++ b/platform/structuralsearch/source/com/intellij/structuralsearch/impl/matcher/MatcherImpl.java @@ -0,0 +1,737 @@ +package com.intellij.structuralsearch.impl.matcher; + +import com.intellij.dupLocator.iterators.ArrayBackedNodeIterator; +import com.intellij.dupLocator.iterators.NodeIterator; +import com.intellij.lang.Language; +import com.intellij.lang.StdLanguages; +import com.intellij.openapi.application.ApplicationManager; +import com.intellij.openapi.application.ModalityState; +import com.intellij.openapi.diagnostic.Logger; +import com.intellij.openapi.editor.Document; +import com.intellij.openapi.fileTypes.FileType; +import com.intellij.openapi.fileTypes.FileTypes; +import com.intellij.openapi.fileTypes.LanguageFileType; +import com.intellij.openapi.progress.ProcessCanceledException; +import com.intellij.openapi.progress.ProgressIndicator; +import com.intellij.openapi.project.Project; +import com.intellij.openapi.roots.ContentIterator; +import com.intellij.openapi.roots.ProjectFileIndex; +import com.intellij.openapi.util.Computable; +import com.intellij.openapi.util.Pair; +import com.intellij.openapi.vfs.VirtualFile; +import com.intellij.psi.*; +import com.intellij.psi.impl.source.tree.injected.InjectedLanguageUtil; +import com.intellij.psi.search.DelegatingGlobalSearchScope; +import com.intellij.psi.search.GlobalSearchScope; +import com.intellij.psi.search.LocalSearchScope; +import com.intellij.psi.search.SearchScope; +import com.intellij.structuralsearch.*; +import com.intellij.structuralsearch.impl.matcher.compiler.PatternCompiler; +import com.intellij.structuralsearch.impl.matcher.handlers.MatchingHandler; +import com.intellij.structuralsearch.impl.matcher.handlers.TopLevelMatchingHandler; +import com.intellij.structuralsearch.impl.matcher.iterators.SsrFilteringNodeIterator; +import com.intellij.structuralsearch.impl.matcher.strategies.MatchingStrategy; +import com.intellij.structuralsearch.plugin.ui.Configuration; +import com.intellij.structuralsearch.plugin.util.CollectingMatchResultSink; +import com.intellij.util.IncorrectOperationException; +import com.intellij.util.PairProcessor; +import com.intellij.util.SmartList; +import com.intellij.util.indexing.FileBasedIndex; +import org.jetbrains.annotations.NotNull; +import org.jetbrains.annotations.Nullable; + +import java.lang.ref.SoftReference; +import java.util.ArrayList; +import java.util.LinkedList; +import java.util.List; + +/** + * This class makes program structure tree matching: + */ +public class MatcherImpl { + private static final Logger LOG = Logger.getInstance("#com.intellij.structuralsearch.impl.matcher.MatcherImpl"); + // project being worked on + private final Project project; + + // context of matching + private final MatchContext matchContext; + private boolean isTesting; + + // visitor to delegate the real work + private final GlobalMatchingVisitor visitor = new GlobalMatchingVisitor(); + private ProgressIndicator progress; + private final TaskScheduler scheduler = new TaskScheduler(); + + private int totalFilesToScan; + private int scannedFilesCount; + + public MatcherImpl(final Project project, final MatchOptions matchOptions) { + this.project = project; + matchContext = new MatchContext(); + matchContext.setMatcher(visitor); + + if (matchOptions != null) { + matchContext.setOptions(matchOptions); + cacheCompiledPattern(matchOptions, PatternCompiler.compilePattern(project,matchOptions)); + } + } + + static class LastMatchData { + CompiledPattern lastPattern; + MatchOptions lastOptions; + } + + private static SoftReference<LastMatchData> lastMatchData; + + protected MatcherImpl(Project project) { + this(project, null); + } + + public static void validate(Project project, MatchOptions options) { + PsiDocumentManager.getInstance(project).commitAllDocuments(); + + synchronized(MatcherImpl.class) { + final LastMatchData data = new LastMatchData(); + data.lastPattern = PatternCompiler.compilePattern(project, options); + data.lastOptions = options; + lastMatchData = new SoftReference<LastMatchData>(data); + } + + final StructuralSearchProfile profile = StructuralSearchUtil.getProfileByFileType(options.getFileType()); + profile.checkSearchPattern(project, options); + } + + public static class CompiledOptions { + public final List<Pair<MatchContext, Configuration>> matchContexts; + + public CompiledOptions(final List<Pair<MatchContext, Configuration>> matchContexts) { + this.matchContexts = matchContexts; + } + + public List<Pair<MatchContext, Configuration>> getMatchContexts() { + return matchContexts; + } + } + + public static boolean checkIfShouldAttemptToMatch(MatchContext context, NodeIterator matchedNodes) { + final CompiledPattern pattern = context.getPattern(); + final NodeIterator patternNodes = pattern.getNodes(); + try { + while (true) { + final PsiElement patternNode = patternNodes.current(); + if (patternNode == null) { + return true; + } + final PsiElement matchedNode = matchedNodes.current(); + if (matchedNode == null) { + return false; + } + final MatchingHandler matchingHandler = pattern.getHandler(patternNode); + if (matchingHandler == null || !matchingHandler.canMatch(patternNode, matchedNode)) { + return false; + } + matchedNodes.advance(); + patternNodes.advance(); + } + } finally { + patternNodes.reset(); + matchedNodes.reset(); + } + } + + public void processMatchesInElement(MatchContext context, Configuration configuration, + NodeIterator matchedNodes, + PairProcessor<MatchResult, Configuration> processor) { + try { + configureOptions(context, configuration, matchedNodes.current(), processor); + context.setShouldRecursivelyMatch(false); + visitor.matchContext(matchedNodes); + } finally { + matchedNodes.reset(); + } + } + + public void clearContext() { + matchContext.clear(); + } + + private void configureOptions(MatchContext context, + final Configuration configuration, + PsiElement psiFile, + final PairProcessor<MatchResult, Configuration> processor) { + if (psiFile == null) return; + LocalSearchScope scope = new LocalSearchScope(psiFile); + + matchContext.clear(); + matchContext.setMatcher(visitor); + + MatchOptions options = context.getOptions(); + matchContext.setOptions(options); + matchContext.setPattern(context.getPattern()); + matchContext.setShouldRecursivelyMatch(context.shouldRecursivelyMatch()); + visitor.setMatchContext(matchContext); + + matchContext.setSink( + new MatchConstraintsSink( + new MatchResultSink() { + public void newMatch(MatchResult result) { + processor.process(result, configuration); + } + + public void processFile(PsiFile element) { + } + + public void setMatchingProcess(MatchingProcess matchingProcess) { + } + + public void matchingFinished() { + } + + public ProgressIndicator getProgressIndicator() { + return null; + } + }, + options.getMaxMatchesCount(), + options.isDistinct(), + options.isCaseSensitiveMatch() + ) + ); + options.setScope(scope); + } + + public CompiledOptions precompileOptions(List<Configuration> configurations) { + List<Pair<MatchContext, Configuration>> contexts = new ArrayList<Pair<MatchContext, Configuration>>(); + + for (Configuration configuration : configurations) { + MatchContext matchContext = new MatchContext(); + matchContext.setMatcher(visitor); + MatchOptions matchOptions = configuration.getMatchOptions(); + matchContext.setOptions(matchOptions); + + try { + CompiledPattern compiledPattern = PatternCompiler.compilePattern(project, matchOptions); + matchContext.setPattern(compiledPattern); + contexts.add(Pair.create(matchContext, configuration)); + } + catch (UnsupportedPatternException ignored) {} + catch (MalformedPatternException ignored) {} + } + return new CompiledOptions(contexts); + } + + Project getProject() { + return project; + } + + /** + * Finds the matches of given pattern starting from given tree element. + * @throws MalformedPatternException + * @throws UnsupportedPatternException + */ + protected void findMatches(MatchResultSink sink, final MatchOptions options) throws MalformedPatternException, UnsupportedPatternException + { + CompiledPattern compiledPattern = prepareMatching(sink, options); + if (compiledPattern== null) { + return; + } + + matchContext.getSink().setMatchingProcess( scheduler ); + scheduler.init(); + progress = matchContext.getSink().getProgressIndicator(); + + if (/*TokenBasedSearcher.canProcess(compiledPattern)*/ false) { + //TokenBasedSearcher searcher = new TokenBasedSearcher(this); + //searcher.search(compiledPattern); + if (isTesting) { + matchContext.getSink().matchingFinished(); + return; + } + } + else { + if (isTesting) { + // testing mode; + final PsiElement[] elements = ((LocalSearchScope)options.getScope()).getScope(); + + PsiElement parent = elements[0].getParent(); + if (elements.length > 0 && matchContext.getPattern().getStrategy().continueMatching(parent != null ? parent : elements[0])) { + visitor.matchContext(new SsrFilteringNodeIterator(new ArrayBackedNodeIterator(elements))); + } + else { + for (PsiElement element : elements) { + match(element); + } + } + + matchContext.getSink().matchingFinished(); + return; + } + if (!findMatches(options, compiledPattern)) { + return; + } + } + + if (scheduler.getTaskQueueEndAction()==null) { + scheduler.setTaskQueueEndAction( + new Runnable() { + public void run() { + matchContext.getSink().matchingFinished(); + } + } + ); + } + + scheduler.executeNext(); + } + + private boolean findMatches(MatchOptions options, CompiledPattern compiledPattern) { + LanguageFileType languageFileType = (LanguageFileType)options.getFileType(); + final StructuralSearchProfile profile = StructuralSearchUtil.getProfileByLanguage(languageFileType.getLanguage()); + assert profile != null; + PsiElement node = compiledPattern.getNodes().current(); + final Language ourPatternLanguage = node != null ? profile.getLanguage(node) : ((LanguageFileType)options.getFileType()).getLanguage(); + final Language ourPatternLanguage2 = ourPatternLanguage == StdLanguages.XML ? StdLanguages.XHTML:null; + SearchScope searchScope = compiledPattern.getScope(); + boolean ourOptimizedScope = searchScope != null; + if (!ourOptimizedScope) searchScope = options.getScope(); + + if (searchScope instanceof GlobalSearchScope) { + final GlobalSearchScope scope = (GlobalSearchScope)searchScope; + + final ContentIterator ci = new ContentIterator() { + public boolean processFile(final VirtualFile fileOrDir) { + if (!fileOrDir.isDirectory() && scope.contains(fileOrDir) && fileOrDir.getFileType() != FileTypes.UNKNOWN) { + ++totalFilesToScan; + scheduler.addOneTask(new MatchOneVirtualFile(fileOrDir, profile, ourPatternLanguage, ourPatternLanguage2)); + } + return true; + } + }; + + ApplicationManager.getApplication().runReadAction(new Runnable() { + @Override + public void run() { + FileBasedIndex.getInstance().iterateIndexableFiles(ci, project, progress); + } + }); + progress.setText2(""); + } + else { + final PsiElement[] elementsToScan = ((LocalSearchScope)searchScope).getScope(); + totalFilesToScan = elementsToScan.length; + + for (int i = 0; i < elementsToScan.length; ++i) { + final PsiElement psiElement = elementsToScan[i]; + + if (psiElement == null) continue; + final Language language = psiElement.getLanguage(); + + PsiFile file = psiElement instanceof PsiFile ? (PsiFile)psiElement : psiElement.getContainingFile(); + + if (profile.isMyFile(file, language, ourPatternLanguage, ourPatternLanguage2)) { + scheduler.addOneTask(new MatchOnePsiFile(psiElement)); + } + if (ourOptimizedScope) elementsToScan[i] = null; // to prevent long PsiElement reference + } + } + return true; + } + + private CompiledPattern prepareMatching(final MatchResultSink sink, final MatchOptions options) { + CompiledPattern savedPattern = null; + + if (matchContext.getOptions() == options && matchContext.getPattern() != null && + matchContext.getOptions().hashCode() == matchContext.getPattern().getOptionsHashStamp()) { + savedPattern = matchContext.getPattern(); + } + + matchContext.clear(); + matchContext.setSink( + new MatchConstraintsSink( + sink, + options.getMaxMatchesCount(), + options.isDistinct(), + options.isCaseSensitiveMatch() + ) + ); + matchContext.setOptions(options); + matchContext.setMatcher(visitor); + visitor.setMatchContext(matchContext); + + CompiledPattern compiledPattern = savedPattern; + + if (compiledPattern == null) { + + synchronized(getClass()) { + final LastMatchData data = com.intellij.reference.SoftReference.dereference(lastMatchData); + if (data != null && options == data.lastOptions) { + compiledPattern = data.lastPattern; + } + lastMatchData = null; + } + + if (compiledPattern==null) { + compiledPattern = ApplicationManager.getApplication().runReadAction(new Computable<CompiledPattern>() { + @Override + public CompiledPattern compute() { + return PatternCompiler.compilePattern(project,options); + } + }); + } + } + + cacheCompiledPattern(options, compiledPattern); + return compiledPattern; + } + + private void cacheCompiledPattern(final MatchOptions options, final CompiledPattern compiledPattern) { + matchContext.setPattern(compiledPattern); + compiledPattern.setOptionsHashStamp(options.hashCode()); + } + + /** + * Finds the matches of given pattern starting from given tree element. + * @param sink match result destination + * @throws MalformedPatternException + * @throws UnsupportedPatternException + */ + protected void testFindMatches(MatchResultSink sink, MatchOptions options) + throws MalformedPatternException, UnsupportedPatternException { + isTesting = true; + try { + findMatches(sink,options); + } finally { + isTesting = false; + } + } + + /** + * Finds the matches of given pattern starting from given tree element. + * @param source string for search + * @param pattern to be searched + * @return list of matches found + * @throws MalformedPatternException + * @throws UnsupportedPatternException + */ + protected List<MatchResult> testFindMatches(String source, + String pattern, + MatchOptions options, + boolean filePattern, + FileType sourceFileType, + String sourceExtension, + boolean physicalSourceFile) + throws MalformedPatternException, UnsupportedPatternException { + + CollectingMatchResultSink sink = new CollectingMatchResultSink(); + + try { + PsiElement[] elements = MatcherImplUtil.createSourceTreeFromText(source, + filePattern ? PatternTreeContext.File : PatternTreeContext.Block, + sourceFileType, + sourceExtension, + project, physicalSourceFile); + + options.setSearchPattern(pattern); + options.setScope(new LocalSearchScope(elements)); + testFindMatches(sink, options); + } + catch (IncorrectOperationException e) { + MalformedPatternException exception = new MalformedPatternException(); + exception.initCause(e); + throw exception; + } + + return sink.getMatches(); + } + + protected List<MatchResult> testFindMatches(String source, String pattern, MatchOptions options, boolean filePattern) { + return testFindMatches(source, pattern, options, filePattern, options.getFileType(), null, false); + } + + class TaskScheduler implements MatchingProcess { + private LinkedList<Runnable> tasks = new LinkedList<Runnable>(); + private boolean ended; + private Runnable taskQueueEndAction; + + private boolean suspended; + + public void stop() { + ended = true; + } + + public void pause() { + suspended = true; + } + + public void resume() { + if (!suspended) return; + suspended = false; + executeNext(); + } + + public boolean isSuspended() { + return suspended; + } + + public boolean isEnded() { + return ended; + } + + void setTaskQueueEndAction(Runnable taskQueueEndAction) { + this.taskQueueEndAction = taskQueueEndAction; + } + Runnable getTaskQueueEndAction () { + return taskQueueEndAction; + } + + void addOneTask(Runnable runnable) { + tasks.add(runnable); + } + + private void executeNext() { + while(!suspended && !ended) { + if (tasks.isEmpty()) { + ended = true; + break; + } + + final Runnable task = tasks.removeFirst(); + try { + task.run(); + } + catch (ProcessCanceledException e) { + ended = true; + clearSchedule(); + throw e; + } + catch (StructuralSearchException e) { + ended = true; + clearSchedule(); + throw e; + } + catch (Throwable th) { + LOG.error(th); + } + } + + if (ended) clearSchedule(); + } + + private void init() { + ended = false; + suspended = false; + PsiManager.getInstance(project).startBatchFilesProcessingMode(); + } + + private void clearSchedule() { + if (tasks != null) { + taskQueueEndAction.run(); + if (!project.isDisposed()) { + PsiManager.getInstance(project).finishBatchFilesProcessingMode(); + } + tasks = null; + } + } + + } + + private class MatchOnePsiFile extends MatchOneFile { + private PsiElement file; + + MatchOnePsiFile(PsiElement file) { + this.file = file; + } + + @Nullable + @Override + protected List<PsiElement> getPsiElementsToProcess() { + PsiElement file = this.file; + this.file = null; + return new SmartList<PsiElement>(file); + } + } + + private abstract class MatchOneFile implements Runnable { + public void run() { + List<PsiElement> files = getPsiElementsToProcess(); + + if (progress!=null) { + progress.setFraction((double)scannedFilesCount/totalFilesToScan); + } + + ++scannedFilesCount; + + if (files == null || files.size() == 0) return; + final PsiFile psiFile = files.get(0).getContainingFile(); + + if (psiFile!=null) { + final Runnable action = new Runnable() { + public void run() { + ApplicationManager.getApplication().runWriteAction(new Runnable() { + public void run() { + if (project.isDisposed()) return; + final PsiDocumentManager manager = PsiDocumentManager.getInstance(project); + Document document = manager.getDocument(psiFile); + if (document != null) manager.commitDocument(document); + } + }); + } + }; + + if (ApplicationManager.getApplication().isDispatchThread()) { + action.run(); + } else { + ApplicationManager.getApplication().invokeAndWait( + action, + ModalityState.defaultModalityState() + ); + } + } + + if (project.isDisposed()) return; + + for(PsiElement file:files) { + if (file instanceof PsiFile) { + matchContext.getSink().processFile((PsiFile)file); + } + + final PsiElement finalFile = file; + ApplicationManager.getApplication().runReadAction( + new Runnable() { + public void run() { + PsiElement file = finalFile; + if (!file.isValid()) return; + file = StructuralSearchUtil.getProfileByLanguage(file.getLanguage()).extendMatchOnePsiFile(file); + match(file); + } + } + ); + } + } + + protected abstract @Nullable List<PsiElement> getPsiElementsToProcess(); + } + + // Initiates the matching process for given element + // @param element the current search tree element + public void match(PsiElement element) { + MatchingStrategy strategy = matchContext.getPattern().getStrategy(); + + if (strategy.continueMatching(element)) { + visitor.matchContext(new ArrayBackedNodeIterator(new PsiElement[] {element})); + return; + } + for(PsiElement el=element.getFirstChild();el!=null;el=el.getNextSibling()) { + match(el); + } + if (element instanceof PsiLanguageInjectionHost) { + InjectedLanguageUtil.enumerate(element, new PsiLanguageInjectionHost.InjectedPsiVisitor() { + @Override + public void visit(@NotNull PsiFile injectedPsi, @NotNull List<PsiLanguageInjectionHost.Shred> places) { + match(injectedPsi); + } + }); + } + } + + @Nullable + protected MatchResult isMatchedByDownUp(PsiElement element, final MatchOptions options) { + final CollectingMatchResultSink sink = new CollectingMatchResultSink(); + CompiledPattern compiledPattern = prepareMatching(sink, options); + + if (compiledPattern== null) { + assert false; + return null; + } + + PsiElement targetNode = compiledPattern.getTargetNode(); + PsiElement elementToStartMatching = null; + + if (targetNode == null) { + targetNode = compiledPattern.getNodes().current(); + if (targetNode != null) { + compiledPattern.getNodes().advance(); + assert !compiledPattern.getNodes().hasNext(); + compiledPattern.getNodes().rewind(); + + while (element.getClass() != targetNode.getClass()) { + element = element.getParent(); + if (element == null) return null; + } + + elementToStartMatching = element; + } + } else { + targetNode = StructuralSearchUtil.getProfileByPsiElement(element).extendMatchedByDownUp(targetNode); + + MatchingHandler handler = null; + + while (element.getClass() == targetNode.getClass() || + compiledPattern.isTypedVar(targetNode) && compiledPattern.getHandler(targetNode).canMatch(targetNode, element) + ) { + handler = compiledPattern.getHandler(targetNode); + handler.setPinnedElement(element); + elementToStartMatching = element; + if (handler instanceof TopLevelMatchingHandler) break; + element = element.getParent(); + targetNode = targetNode.getParent(); + + if (options.isLooseMatching()) { + element = StructuralSearchUtil.getProfileByPsiElement(element).updateCurrentNode(element); + targetNode = StructuralSearchUtil.getProfileByPsiElement(element).updateCurrentNode(targetNode); + } + } + + if (!(handler instanceof TopLevelMatchingHandler)) return null; + } + + assert targetNode != null : "Could not match down up when no target node"; + + match(elementToStartMatching); + matchContext.getSink().matchingFinished(); + final int matchCount = sink.getMatches().size(); + assert matchCount <= 1; + return matchCount > 0 ? sink.getMatches().get(0) : null; + } + + private class MatchOneVirtualFile extends MatchOneFile { + private final VirtualFile myFileOrDir; + private final StructuralSearchProfile myProfile; + private final Language myOurPatternLanguage; + private final Language myOurPatternLanguage2; + + public MatchOneVirtualFile(VirtualFile fileOrDir, + StructuralSearchProfile profile, + Language ourPatternLanguage, + Language ourPatternLanguage2) { + myFileOrDir = fileOrDir; + myProfile = profile; + myOurPatternLanguage = ourPatternLanguage; + myOurPatternLanguage2 = ourPatternLanguage2; + } + + @Nullable + @Override + protected List<PsiElement> getPsiElementsToProcess() { + return ApplicationManager.getApplication().runReadAction(new Computable<List<PsiElement>>() { + @Override + public List<PsiElement> compute() { + PsiFile file = PsiManager.getInstance(project).findFile(myFileOrDir); + if (file == null) { + return null; + } + + final FileViewProvider viewProvider = file.getViewProvider(); + List<PsiElement> elementsToProcess = new SmartList<PsiElement>(); + + for(Language lang: viewProvider.getLanguages()) { + if (myProfile.isMyFile(file, lang, myOurPatternLanguage, myOurPatternLanguage2)) { + elementsToProcess.add(viewProvider.getPsi(lang)); + } + } + + return elementsToProcess; + } + }); + } + } +} |