SSR: script log first pass
[idea/community.git] / platform / structuralsearch / source / com / intellij / structuralsearch / impl / matcher / compiler / PatternCompiler.java
1 package com.intellij.structuralsearch.impl.matcher.compiler;
2
3 import com.intellij.codeInsight.template.Template;
4 import com.intellij.codeInsight.template.TemplateManager;
5 import com.intellij.dupLocator.util.NodeFilter;
6 import com.intellij.lang.Language;
7 import com.intellij.openapi.application.ApplicationManager;
8 import com.intellij.openapi.extensions.Extensions;
9 import com.intellij.openapi.fileTypes.FileType;
10 import com.intellij.openapi.fileTypes.LanguageFileType;
11 import com.intellij.openapi.project.Project;
12 import com.intellij.openapi.util.text.StringUtil;
13 import com.intellij.psi.*;
14 import com.intellij.psi.impl.source.PsiFileImpl;
15 import com.intellij.psi.impl.source.tree.LeafElement;
16 import com.intellij.psi.search.GlobalSearchScope;
17 import com.intellij.psi.search.LocalSearchScope;
18 import com.intellij.psi.util.PsiUtilCore;
19 import com.intellij.structuralsearch.*;
20 import com.intellij.structuralsearch.impl.matcher.CompiledPattern;
21 import com.intellij.structuralsearch.impl.matcher.MatchPredicateProvider;
22 import com.intellij.structuralsearch.impl.matcher.MatcherImplUtil;
23 import com.intellij.structuralsearch.impl.matcher.PatternTreeContext;
24 import com.intellij.structuralsearch.impl.matcher.filters.LexicalNodesFilter;
25 import com.intellij.structuralsearch.impl.matcher.handlers.MatchPredicate;
26 import com.intellij.structuralsearch.impl.matcher.handlers.MatchingHandler;
27 import com.intellij.structuralsearch.impl.matcher.handlers.SubstitutionHandler;
28 import com.intellij.structuralsearch.impl.matcher.predicates.*;
29 import com.intellij.structuralsearch.plugin.ui.Configuration;
30 import com.intellij.util.IncorrectOperationException;
31 import gnu.trove.TIntArrayList;
32 import gnu.trove.TIntHashSet;
33 import org.jetbrains.annotations.NotNull;
34 import org.jetbrains.annotations.Nullable;
35
36 import java.util.*;
37 import java.util.regex.Matcher;
38 import java.util.regex.Pattern;
39
40 /**
41  * Compiles the handlers for usability
42  */
43 public class PatternCompiler {
44   private static CompileContext lastTestingContext;
45
46   public static void transformOldPattern(MatchOptions options) {
47     StringToConstraintsTransformer.transformOldPattern(options);
48   }
49
50   public static CompiledPattern compilePattern(final Project project, final MatchOptions options) throws MalformedPatternException,
51                                                                                                          UnsupportedOperationException {
52     FileType fileType = options.getFileType();
53     assert fileType instanceof LanguageFileType;
54     Language language = ((LanguageFileType)fileType).getLanguage();
55     StructuralSearchProfile profile = StructuralSearchUtil.getProfileByLanguage(language);
56     assert profile != null;
57     CompiledPattern result = profile.createCompiledPattern();
58
59     final String[] prefixes = result.getTypedVarPrefixes();
60     assert prefixes.length > 0;
61
62     final CompileContext context = new CompileContext();
63     if (ApplicationManager.getApplication().isUnitTestMode()) lastTestingContext = context;
64
65     /*CompiledPattern result = options.getFileType() == StdFileTypes.JAVA ?
66                              new JavaCompiledPattern() :
67                              new XmlCompiledPattern();*/
68
69     try {
70       context.init(result, options, project, options.getScope() instanceof GlobalSearchScope);
71
72       List<PsiElement> elements = compileByAllPrefixes(project, options, result, context, prefixes);
73
74       final CompiledPattern pattern = context.getPattern();
75       checkForUnknownVariables(pattern, elements);
76       pattern.setNodes(elements);
77
78       if (context.getSearchHelper().doOptimizing() && context.getSearchHelper().isScannedSomething()) {
79         final Set<PsiFile> set = context.getSearchHelper().getFilesSetToScan();
80         final List<PsiFile> filesToScan = new ArrayList<PsiFile>(set.size());
81         final GlobalSearchScope scope = (GlobalSearchScope)options.getScope();
82
83         for (final PsiFile file : set) {
84           if (!scope.contains(file.getVirtualFile())) {
85             continue;
86           }
87
88           if (file instanceof PsiFileImpl) {
89             ((PsiFileImpl)file).clearCaches();
90           }
91           filesToScan.add(file);
92         }
93
94         if (filesToScan.size() == 0) {
95           throw new MalformedPatternException(SSRBundle.message("ssr.will.not.find.anything"));
96         }
97         result.setScope(
98           new LocalSearchScope(PsiUtilCore.toPsiElementArray(filesToScan))
99         );
100       }
101     } finally {
102       context.clear();
103     }
104
105     return result;
106   }
107
108   private static void checkForUnknownVariables(final CompiledPattern pattern, List<PsiElement> elements) {
109     for (PsiElement element : elements) {
110       element.accept(new PsiRecursiveElementWalkingVisitor() {
111         @Override
112         public void visitElement(PsiElement element) {
113           if (element.getUserData(CompiledPattern.HANDLER_KEY) != null) {
114             return;
115           }
116           super.visitElement(element);
117
118           if (!(element instanceof LeafElement) || !pattern.isTypedVar(element)) {
119             return;
120           }
121           final MatchingHandler handler = pattern.getHandler(pattern.getTypedVarString(element));
122           if (handler == null) {
123             throw new MalformedPatternException();
124           }
125         }
126       });
127     }
128   }
129
130   public static String getLastFindPlan() {
131     return ((TestModeOptimizingSearchHelper)lastTestingContext.getSearchHelper()).getSearchPlan();
132   }
133
134   @NotNull
135   private static List<PsiElement> compileByAllPrefixes(Project project,
136                                                        MatchOptions options,
137                                                        CompiledPattern pattern,
138                                                        CompileContext context,
139                                                        String[] applicablePrefixes) {
140     if (applicablePrefixes.length == 0) {
141       return Collections.emptyList();
142     }
143
144     List<PsiElement> elements = doCompile(project, options, pattern, new ConstantPrefixProvider(applicablePrefixes[0]), context);
145     if (elements.isEmpty()) {
146       return elements;
147     }
148
149     final PsiFile file = elements.get(0).getContainingFile();
150     if (file == null) {
151       return elements;
152     }
153
154     final PsiElement last = elements.get(elements.size() - 1);
155     final Pattern[] patterns = new Pattern[applicablePrefixes.length];
156
157     for (int i = 0; i < applicablePrefixes.length; i++) {
158       String s = StructuralSearchUtil.shieldSpecialChars(applicablePrefixes[i]);
159       patterns[i] = Pattern.compile(s + "\\w+\\b");
160     }
161
162     final int[] varEndOffsets = findAllTypedVarOffsets(file, patterns);
163
164     final int patternEndOffset = last.getTextRange().getEndOffset();
165     if (elements.size() == 0 ||
166         checkErrorElements(file, patternEndOffset, patternEndOffset, varEndOffsets, true) != Boolean.TRUE) {
167       return elements;
168     }
169
170     final int varCount = varEndOffsets.length;
171     final String[] prefixSequence = new String[varCount];
172
173     for (int i = 0; i < varCount; i++) {
174       prefixSequence[i] = applicablePrefixes[0];
175     }
176
177     final List<PsiElement> finalElements =
178       compileByPrefixes(project, options, pattern, context, applicablePrefixes, patterns, prefixSequence, 0);
179     return finalElements != null
180            ? finalElements
181            : doCompile(project, options, pattern, new ConstantPrefixProvider(applicablePrefixes[0]), context);
182   }
183
184   @Nullable
185   private static List<PsiElement> compileByPrefixes(Project project,
186                                                     MatchOptions options,
187                                                     CompiledPattern pattern,
188                                                     CompileContext context,
189                                                     String[] applicablePrefixes,
190                                                     Pattern[] substitutionPatterns,
191                                                     String[] prefixSequence,
192                                                     int index) {
193     if (index >= prefixSequence.length) {
194       final List<PsiElement> elements = doCompile(project, options, pattern, new ArrayPrefixProvider(prefixSequence), context);
195       if (elements.isEmpty()) {
196         return elements;
197       }
198
199       final PsiElement parent = elements.get(0).getParent();
200       final PsiElement last = elements.get(elements.size() - 1);
201       final int[] varEndOffsets = findAllTypedVarOffsets(parent.getContainingFile(), substitutionPatterns);
202       final int patternEndOffset = last.getTextRange().getEndOffset();
203       return checkErrorElements(parent, patternEndOffset, patternEndOffset, varEndOffsets, false) != Boolean.TRUE
204              ? elements
205              : null;
206     }
207
208     String[] alternativeVariant = null;
209
210     for (String applicablePrefix : applicablePrefixes) {
211       prefixSequence[index] = applicablePrefix;
212
213       List<PsiElement> elements = doCompile(project, options, pattern, new ArrayPrefixProvider(prefixSequence), context);
214       if (elements.isEmpty()) {
215         return elements;
216       }
217
218       final PsiFile file = elements.get(0).getContainingFile();
219       if (file == null) {
220         return elements;
221       }
222
223       final int[] varEndOffsets = findAllTypedVarOffsets(file, substitutionPatterns);
224       final int offset = varEndOffsets[index];
225
226       final int patternEndOffset = elements.get(elements.size() - 1).getTextRange().getEndOffset();
227       final Boolean result = checkErrorElements(file, offset, patternEndOffset, varEndOffsets, false);
228
229       if (result == Boolean.TRUE) {
230         continue;
231       }
232
233       if (result == Boolean.FALSE || (result == null && alternativeVariant == null)) {
234         final List<PsiElement> finalElements =
235           compileByPrefixes(project, options, pattern, context, applicablePrefixes, substitutionPatterns, prefixSequence, index + 1);
236         if (finalElements != null) {
237           if (result == Boolean.FALSE) {
238             return finalElements;
239           }
240           alternativeVariant = new String[prefixSequence.length];
241           System.arraycopy(prefixSequence, 0, alternativeVariant, 0, prefixSequence.length);
242         }
243       }
244     }
245
246     return alternativeVariant != null ?
247            compileByPrefixes(project, options, pattern, context, applicablePrefixes, substitutionPatterns, alternativeVariant, index + 1) :
248            null;
249   }
250
251   @NotNull
252   private static int[] findAllTypedVarOffsets(final PsiFile file, final Pattern[] substitutionPatterns) {
253     final TIntHashSet result = new TIntHashSet();
254
255     file.accept(new PsiRecursiveElementWalkingVisitor() {
256       @Override
257       public void visitElement(PsiElement element) {
258         super.visitElement(element);
259
260         if (element instanceof LeafElement) {
261           final String text = element.getText();
262
263           for (Pattern pattern : substitutionPatterns) {
264             final Matcher matcher = pattern.matcher(text);
265
266             while (matcher.find()) {
267               result.add(element.getTextRange().getStartOffset() + matcher.end());
268             }
269           }
270         }
271       }
272     });
273
274     final int[] resultArray = result.toArray();
275     Arrays.sort(resultArray);
276     return resultArray;
277   }
278
279
280   /**
281    * False: there are no error elements before offset, except patternEndOffset
282    * Null: there are only error elements located exactly after template variables or at the end of the pattern
283    * True: otherwise
284    */
285   @Nullable
286   private static Boolean checkErrorElements(PsiElement element,
287                                             final int offset,
288                                             final int patternEndOffset,
289                                             final int[] varEndOffsets,
290                                             final boolean strict) {
291     final TIntArrayList errorOffsets = new TIntArrayList();
292     final boolean[] containsErrorTail = {false};
293     final TIntHashSet varEndOffsetsSet = new TIntHashSet(varEndOffsets);
294
295     element.accept(new PsiRecursiveElementWalkingVisitor() {
296       @Override
297       public void visitErrorElement(PsiErrorElement element) {
298         super.visitErrorElement(element);
299
300         final int startOffset = element.getTextRange().getStartOffset();
301
302         if ((strict || !varEndOffsetsSet.contains(startOffset)) && startOffset != patternEndOffset) {
303           errorOffsets.add(startOffset);
304         }
305
306         if (startOffset == offset) {
307           containsErrorTail[0] = true;
308         }
309       }
310     });
311
312     for (int i = 0; i < errorOffsets.size(); i++) {
313       final int errorOffset = errorOffsets.get(i);
314       if (errorOffset <= offset) {
315         return true;
316       }
317     }
318     return containsErrorTail[0] ? null : false;
319   }
320
321   private interface PrefixProvider {
322     String getPrefix(int varIndex);
323   }
324
325   private static class ConstantPrefixProvider implements PrefixProvider {
326     private final String myPrefix;
327
328     private ConstantPrefixProvider(String prefix) {
329       myPrefix = prefix;
330     }
331
332     @Override
333     public String getPrefix(int varIndex) {
334       return myPrefix;
335     }
336   }
337
338   private static class ArrayPrefixProvider implements PrefixProvider {
339     private final String[] myPrefixes;
340
341     private ArrayPrefixProvider(String[] prefixes) {
342       myPrefixes = prefixes;
343     }
344
345     @Override
346     public String getPrefix(int varIndex) {
347       if (varIndex >= myPrefixes.length) return null;
348       return myPrefixes[varIndex];
349     }
350   }
351
352   private static List<PsiElement> doCompile(Project project,
353                                             MatchOptions options,
354                                             CompiledPattern result,
355                                             PrefixProvider prefixProvider,
356                                             CompileContext context) {
357     result.clearHandlers();
358     context.init(result, options, project, options.getScope() instanceof GlobalSearchScope);
359
360     final StringBuilder buf = new StringBuilder();
361
362     Template template = TemplateManager.getInstance(project).createTemplate("","",options.getSearchPattern());
363
364     int segmentsCount = template.getSegmentsCount();
365     String text = template.getTemplateText();
366     buf.setLength(0);
367     int prevOffset = 0;
368
369     for(int i=0;i<segmentsCount;++i) {
370       final int offset = template.getSegmentOffset(i);
371       final String name = template.getSegmentName(i);
372
373       final String prefix = prefixProvider.getPrefix(i);
374       if (prefix == null) {
375         throw new MalformedPatternException();
376       }
377
378       buf.append(text.substring(prevOffset,offset));
379       buf.append(prefix);
380       buf.append(name);
381
382       MatchVariableConstraint constraint = options.getVariableConstraint(name);
383       if (constraint==null) {
384         // we do not edited the constraints
385         constraint = new MatchVariableConstraint();
386         constraint.setName( name );
387         options.addVariableConstraint(constraint);
388       }
389
390       SubstitutionHandler handler = result.createSubstitutionHandler(
391         name,
392         prefix + name,
393         constraint.isPartOfSearchResults(),
394         constraint.getMinCount(),
395         constraint.getMaxCount(),
396         constraint.isGreedy()
397       );
398
399       if(constraint.isWithinHierarchy()) {
400         handler.setSubtype(true);
401       }
402
403       if(constraint.isStrictlyWithinHierarchy()) {
404         handler.setStrictSubtype(true);
405       }
406
407       MatchPredicate predicate;
408
409       if (!StringUtil.isEmptyOrSpaces(constraint.getRegExp())) {
410         predicate = new RegExpPredicate(
411           constraint.getRegExp(),
412           options.isCaseSensitiveMatch(),
413           name,
414           constraint.isWholeWordsOnly(),
415           constraint.isPartOfSearchResults()
416         );
417         if (constraint.isInvertRegExp()) {
418           predicate = new NotPredicate(predicate);
419         }
420         addPredicate(handler,predicate);
421       }
422
423       if (constraint.isReference()) {
424         predicate = new ReferencePredicate( constraint.getNameOfReferenceVar() );
425
426         if (constraint.isInvertReference()) {
427           predicate = new NotPredicate(predicate);
428         }
429         addPredicate(handler,predicate);
430       }
431
432       Set<MatchPredicate> predicates = new LinkedHashSet<MatchPredicate>();
433       for (MatchPredicateProvider matchPredicateProvider : Extensions.getExtensions(MatchPredicateProvider.EP_NAME)) {
434         matchPredicateProvider.collectPredicates(constraint, name, options, predicates);
435       }
436       for (MatchPredicate matchPredicate : predicates) {
437         addPredicate(handler, matchPredicate);
438       }
439
440       addScriptConstraint(project, name, constraint, handler);
441
442       if (!StringUtil.isEmptyOrSpaces(constraint.getContainsConstraint())) {
443         predicate = new ContainsPredicate(name, constraint.getContainsConstraint());
444         if (constraint.isInvertContainsConstraint()) {
445           predicate = new NotPredicate(predicate);
446         }
447         addPredicate(handler,predicate);
448       }
449
450       if (!StringUtil.isEmptyOrSpaces(constraint.getWithinConstraint())) {
451         assert false;
452       }
453
454       prevOffset = offset;
455     }
456
457     MatchVariableConstraint constraint = options.getVariableConstraint(Configuration.CONTEXT_VAR_NAME);
458     if (constraint != null) {
459       SubstitutionHandler handler = result.createSubstitutionHandler(
460         Configuration.CONTEXT_VAR_NAME,
461         Configuration.CONTEXT_VAR_NAME,
462         constraint.isPartOfSearchResults(),
463         constraint.getMinCount(),
464         constraint.getMaxCount(),
465         constraint.isGreedy()
466       );
467
468       if (!StringUtil.isEmptyOrSpaces(constraint.getWithinConstraint())) {
469         MatchPredicate predicate =
470           new WithinPredicate(Configuration.CONTEXT_VAR_NAME, constraint.getWithinConstraint(), options.getFileType(), project);
471         if (constraint.isInvertWithinConstraint()) {
472           predicate = new NotPredicate(predicate);
473         }
474         addPredicate(handler,predicate);
475       }
476
477       addScriptConstraint(project, Configuration.CONTEXT_VAR_NAME, constraint, handler);
478     }
479
480     buf.append(text.substring(prevOffset,text.length()));
481
482     PsiElement[] matchStatements;
483
484     try {
485       matchStatements = MatcherImplUtil.createTreeFromText(buf.toString(), PatternTreeContext.Block, options.getFileType(),
486                                                            options.getDialect(), options.getPatternContext(), project, false);
487       if (matchStatements.length==0) throw new MalformedPatternException();
488     } catch (IncorrectOperationException e) {
489       throw new MalformedPatternException(e.getMessage());
490     }
491
492     NodeFilter filter = LexicalNodesFilter.getInstance();
493
494     GlobalCompilingVisitor compilingVisitor = new GlobalCompilingVisitor();
495     compilingVisitor.compile(matchStatements,context);
496     ArrayList<PsiElement> elements = new ArrayList<PsiElement>();
497
498     for (PsiElement matchStatement : matchStatements) {
499       if (!filter.accepts(matchStatement)) {
500         elements.add(matchStatement);
501       }
502     }
503
504     new DeleteNodesAction(compilingVisitor.getLexicalNodes()).run();
505     return elements;
506   }
507
508   private static void addScriptConstraint(Project project, String name, MatchVariableConstraint constraint, SubstitutionHandler handler) {
509     if (constraint.getScriptCodeConstraint()!= null && constraint.getScriptCodeConstraint().length() > 2) {
510       final String script = StringUtil.stripQuotesAroundValue(constraint.getScriptCodeConstraint());
511       final String s = ScriptSupport.checkValidScript(script);
512       if (s != null) throw new MalformedPatternException("Script constraint for " + constraint.getName() + " has problem "+s);
513       MatchPredicate predicate = new ScriptPredicate(project, name, script);
514       addPredicate(handler,predicate);
515     }
516   }
517
518   static void addPredicate(SubstitutionHandler handler, MatchPredicate predicate) {
519     if (handler.getPredicate()==null) {
520       handler.setPredicate(predicate);
521     } else {
522       handler.setPredicate(new BinaryPredicate(handler.getPredicate(), predicate, false));
523     }
524   }
525
526 }