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 }