gitweb.ps.run Git - toc/blob - antlr4-cpp-runtime-4.9.2-source/runtime/src/tree/pattern/ParseTreePatternMatcher.h

   1 /* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
   2  * Use of this file is governed by the BSD 3-clause license that
   3  * can be found in the LICENSE.txt file in the project root.
   4  */
   5
   6 #pragma once
   7
   8 #include "Exceptions.h"
   9
  10 namespace antlr4 {
  11 namespace tree {
  12 namespace pattern {
  13
  14   /// <summary>
  15   /// A tree pattern matching mechanism for ANTLR <seealso cref="ParseTree"/>s.
  16   /// <p/>
  17   /// Patterns are strings of source input text with special tags representing
  18   /// token or rule references such as:
  19   /// <p/>
  20   /// {@code <ID> = <expr>;}
  21   /// <p/>
  22   /// Given a pattern start rule such as {@code statement}, this object constructs
  23   /// a <seealso cref="ParseTree"/> with placeholders for the {@code ID} and {@code expr}
  24   /// subtree. Then the <seealso cref="#match"/> routines can compare an actual
  25   /// <seealso cref="ParseTree"/> from a parse with this pattern. Tag {@code <ID>} matches
  26   /// any {@code ID} token and tag {@code <expr>} references the result of the
  27   /// {@code expr} rule (generally an instance of {@code ExprContext}.
  28   /// <p/>
  29   /// Pattern {@code x = 0;} is a similar pattern that matches the same pattern
  30   /// except that it requires the identifier to be {@code x} and the expression to
  31   /// be {@code 0}.
  32   /// <p/>
  33   /// The <seealso cref="#matches"/> routines return {@code true} or {@code false} based
  34   /// upon a match for the tree rooted at the parameter sent in. The
  35   /// <seealso cref="#match"/> routines return a <seealso cref="ParseTreeMatch"/> object that
  36   /// contains the parse tree, the parse tree pattern, and a map from tag name to
  37   /// matched nodes (more below). A subtree that fails to match, returns with
  38   /// <seealso cref="ParseTreeMatch#mismatchedNode"/> set to the first tree node that did not
  39   /// match.
  40   /// <p/>
  41   /// For efficiency, you can compile a tree pattern in string form to a
  42   /// <seealso cref="ParseTreePattern"/> object.
  43   /// <p/>
  44   /// See {@code TestParseTreeMatcher} for lots of examples.
  45   /// <seealso cref="ParseTreePattern"/> has two static helper methods:
  46   /// <seealso cref="ParseTreePattern#findAll"/> and <seealso cref="ParseTreePattern#match"/> that
  47   /// are easy to use but not super efficient because they create new
  48   /// <seealso cref="ParseTreePatternMatcher"/> objects each time and have to compile the
  49   /// pattern in string form before using it.
  50   /// <p/>
  51   /// The lexer and parser that you pass into the <seealso cref="ParseTreePatternMatcher"/>
  52   /// constructor are used to parse the pattern in string form. The lexer converts
  53   /// the {@code <ID> = <expr>;} into a sequence of four tokens (assuming lexer
  54   /// throws out whitespace or puts it on a hidden channel). Be aware that the
  55   /// input stream is reset for the lexer (but not the parser; a
  56   /// <seealso cref="ParserInterpreter"/> is created to parse the input.). Any user-defined
  57   /// fields you have put into the lexer might get changed when this mechanism asks
  58   /// it to scan the pattern string.
  59   /// <p/>
  60   /// Normally a parser does not accept token {@code <expr>} as a valid
  61   /// {@code expr} but, from the parser passed in, we create a special version of
  62   /// the underlying grammar representation (an <seealso cref="ATN"/>) that allows imaginary
  63   /// tokens representing rules ({@code <expr>}) to match entire rules. We call
  64   /// these <em>bypass alternatives</em>.
  65   /// <p/>
  66   /// Delimiters are {@code <} and {@code >}, with {@code \} as the escape string
  67   /// by default, but you can set them to whatever you want using
  68   /// <seealso cref="#setDelimiters"/>. You must escape both start and stop strings
  69   /// {@code \<} and {@code \>}.
  70   /// </summary>
  71   class ANTLR4CPP_PUBLIC ParseTreePatternMatcher {
  72   public:
  73     class CannotInvokeStartRule : public RuntimeException {
  74     public:
  75       CannotInvokeStartRule(const RuntimeException &e);
  76       ~CannotInvokeStartRule();
  77     };
  78
  79     // Fixes https://github.com/antlr/antlr4/issues/413
  80     // "Tree pattern compilation doesn't check for a complete parse"
  81     class StartRuleDoesNotConsumeFullPattern : public RuntimeException {
  82     public:
  83       StartRuleDoesNotConsumeFullPattern() = default;
  84       StartRuleDoesNotConsumeFullPattern(StartRuleDoesNotConsumeFullPattern const&) = default;
  85       ~StartRuleDoesNotConsumeFullPattern();
  86
  87       StartRuleDoesNotConsumeFullPattern& operator=(StartRuleDoesNotConsumeFullPattern const&) = default;
  88     };
  89
  90     /// Constructs a <seealso cref="ParseTreePatternMatcher"/> or from a <seealso cref="Lexer"/> and
  91     /// <seealso cref="Parser"/> object. The lexer input stream is altered for tokenizing
  92     /// the tree patterns. The parser is used as a convenient mechanism to get
  93     /// the grammar name, plus token, rule names.
  94     ParseTreePatternMatcher(Lexer *lexer, Parser *parser);
  95     virtual ~ParseTreePatternMatcher();
  96
  97     /// <summary>
  98     /// Set the delimiters used for marking rule and token tags within concrete
  99     /// syntax used by the tree pattern parser.
 100     /// </summary>
 101     /// <param name="start"> The start delimiter. </param>
 102     /// <param name="stop"> The stop delimiter. </param>
 103     /// <param name="escapeLeft"> The escape sequence to use for escaping a start or stop delimiter.
 104     /// </param>
 105     /// <exception cref="IllegalArgumentException"> if {@code start} is {@code null} or empty. </exception>
 106     /// <exception cref="IllegalArgumentException"> if {@code stop} is {@code null} or empty. </exception>
 107     virtual void setDelimiters(const std::string &start, const std::string &stop, const std::string &escapeLeft);
 108
 109     /// <summary>
 110     /// Does {@code pattern} matched as rule {@code patternRuleIndex} match {@code tree}? </summary>
 111     virtual bool matches(ParseTree *tree, const std::string &pattern, int patternRuleIndex);
 112
 113     /// <summary>
 114     /// Does {@code pattern} matched as rule patternRuleIndex match tree? Pass in a
 115     ///  compiled pattern instead of a string representation of a tree pattern.
 116     /// </summary>
 117     virtual bool matches(ParseTree *tree, const ParseTreePattern &pattern);
 118
 119     /// <summary>
 120     /// Compare {@code pattern} matched as rule {@code patternRuleIndex} against
 121     /// {@code tree} and return a <seealso cref="ParseTreeMatch"/> object that contains the
 122     /// matched elements, or the node at which the match failed.
 123     /// </summary>
 124     virtual ParseTreeMatch match(ParseTree *tree, const std::string &pattern, int patternRuleIndex);
 125
 126     /// <summary>
 127     /// Compare {@code pattern} matched against {@code tree} and return a
 128     /// <seealso cref="ParseTreeMatch"/> object that contains the matched elements, or the
 129     /// node at which the match failed. Pass in a compiled pattern instead of a
 130     /// string representation of a tree pattern.
 131     /// </summary>
 132     virtual ParseTreeMatch match(ParseTree *tree, const ParseTreePattern &pattern);
 133
 134     /// <summary>
 135     /// For repeated use of a tree pattern, compile it to a
 136     /// <seealso cref="ParseTreePattern"/> using this method.
 137     /// </summary>
 138     virtual ParseTreePattern compile(const std::string &pattern, int patternRuleIndex);
 139
 140     /// <summary>
 141     /// Used to convert the tree pattern string into a series of tokens. The
 142     /// input stream is reset.
 143     /// </summary>
 144     virtual Lexer* getLexer();
 145
 146     /// <summary>
 147     /// Used to collect to the grammar file name, token names, rule names for
 148     /// used to parse the pattern into a parse tree.
 149     /// </summary>
 150     virtual Parser* getParser();
 151
 152     // ---- SUPPORT CODE ----
 153
 154     virtual std::vector<std::unique_ptr<Token>> tokenize(const std::string &pattern);
 155
 156     /// Split "<ID> = <e:expr>;" into 4 chunks for tokenizing by tokenize().
 157     virtual std::vector<Chunk> split(const std::string &pattern);
 158
 159   protected:
 160     std::string _start;
 161     std::string _stop;
 162     std::string _escape; // e.g., \< and \> must escape BOTH!
 163
 164     /// Recursively walk {@code tree} against {@code patternTree}, filling
 165     /// {@code match.}<seealso cref="ParseTreeMatch#labels labels"/>.
 166     ///
 167     /// <returns> the first node encountered in {@code tree} which does not match
 168     /// a corresponding node in {@code patternTree}, or {@code null} if the match
 169     /// was successful. The specific node returned depends on the matching
 170     /// algorithm used by the implementation, and may be overridden. </returns>
 171     virtual ParseTree* matchImpl(ParseTree *tree, ParseTree *patternTree, std::map<std::string, std::vector<ParseTree *>> &labels);
 172
 173     /// Is t <expr> subtree?
 174     virtual RuleTagToken* getRuleTagToken(ParseTree *t);
 175
 176   private:
 177     Lexer *_lexer;
 178     Parser *_parser;
 179
 180     void InitializeInstanceFields();
 181   };
 182
 183 } // namespace pattern
 184 } // namespace tree
 185 } // namespace antlr4