cpp/third_party/antlr4-cpp-runtime-4/runtime/src/tree/pattern/ParseTreePatternMatcher.cpp - tsfile - Git at Google

 /* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
  * Use of this file is governed by the BSD 3-clause license that
  * can be found in the LICENSE.txt file in the project root.
  */

 #include "tree/pattern/ParseTreePattern.h"
 #include "tree/pattern/ParseTreeMatch.h"
 #include "tree/TerminalNode.h"
 #include "CommonTokenStream.h"
 #include "ParserInterpreter.h"
 #include "tree/pattern/TokenTagToken.h"
 #include "ParserRuleContext.h"
 #include "tree/pattern/RuleTagToken.h"
 #include "tree/pattern/TagChunk.h"
 #include "atn/ATN.h"
 #include "Lexer.h"
 #include "BailErrorStrategy.h"

 #include "ListTokenSource.h"
 #include "tree/pattern/TextChunk.h"
 #include "ANTLRInputStream.h"
 #include "support/Arrays.h"
 #include "Exceptions.h"
 #include "support/StringUtils.h"
 #include "support/CPPUtils.h"

 #include "tree/pattern/ParseTreePatternMatcher.h"

 using namespace antlr4;
 using namespace antlr4::tree;
 using namespace antlr4::tree::pattern;
 using namespace antlrcpp;

 ParseTreePatternMatcher::CannotInvokeStartRule::CannotInvokeStartRule(const RuntimeException &e) : RuntimeException(e.what()) {
 }

 ParseTreePatternMatcher::CannotInvokeStartRule::~CannotInvokeStartRule() {
 }

 ParseTreePatternMatcher::StartRuleDoesNotConsumeFullPattern::~StartRuleDoesNotConsumeFullPattern() {
 }

 ParseTreePatternMatcher::ParseTreePatternMatcher(Lexer *lexer, Parser *parser) : _lexer(lexer), _parser(parser) {
   InitializeInstanceFields();
 }

 ParseTreePatternMatcher::~ParseTreePatternMatcher() {
 }

 void ParseTreePatternMatcher::setDelimiters(const std::string &start, const std::string &stop, const std::string &escapeLeft) {
   if (start.empty()) {
     throw IllegalArgumentException("start cannot be null or empty");
   }

   if (stop.empty()) {
     throw IllegalArgumentException("stop cannot be null or empty");
   }

  _start = start;
   _stop = stop;
   _escape = escapeLeft;
 }

 bool ParseTreePatternMatcher::matches(ParseTree *tree, const std::string &pattern, int patternRuleIndex) {
   ParseTreePattern p = compile(pattern, patternRuleIndex);
   return matches(tree, p);
 }

 bool ParseTreePatternMatcher::matches(ParseTree *tree, const ParseTreePattern &pattern) {
   std::map<std::string, std::vector<ParseTree *>> labels;
   ParseTree *mismatchedNode = matchImpl(tree, pattern.getPatternTree(), labels);
   return mismatchedNode == nullptr;
 }

 ParseTreeMatch ParseTreePatternMatcher::match(ParseTree *tree, const std::string &pattern, int patternRuleIndex) {
   ParseTreePattern p = compile(pattern, patternRuleIndex);
   return match(tree, p);
 }

 ParseTreeMatch ParseTreePatternMatcher::match(ParseTree *tree, const ParseTreePattern &pattern) {
   std::map<std::string, std::vector<ParseTree *>> labels;
   tree::ParseTree *mismatchedNode = matchImpl(tree, pattern.getPatternTree(), labels);
   return ParseTreeMatch(tree, pattern, labels, mismatchedNode);
 }

 ParseTreePattern ParseTreePatternMatcher::compile(const std::string &pattern, int patternRuleIndex) {
   ListTokenSource tokenSrc(tokenize(pattern));
   CommonTokenStream tokens(&tokenSrc);

   ParserInterpreter parserInterp(_parser->getGrammarFileName(), _parser->getVocabulary(),
                                  _parser->getRuleNames(), _parser->getATNWithBypassAlts(), &tokens);

   ParserRuleContext *tree = nullptr;
   try {
     parserInterp.setErrorHandler(std::make_shared<BailErrorStrategy>());
     tree = parserInterp.parse(patternRuleIndex);
   } catch (ParseCancellationException &e) {
 #if defined(_MSC_FULL_VER) && _MSC_FULL_VER < 190023026
     // rethrow_if_nested is not available before VS 2015.
     throw e;
 #else
     std::rethrow_if_nested(e); // Unwrap the nested exception.
 #endif
   } catch (RecognitionException &re) {
     throw re;
 #if defined(_MSC_FULL_VER) && _MSC_FULL_VER < 190023026
   } catch (std::exception &e) {
     // throw_with_nested is not available before VS 2015.
     throw e;
 #else
   } catch (std::exception & /*e*/) {
     std::throw_with_nested((const char*)"Cannot invoke start rule"); // Wrap any other exception. We should however probably use one of the ANTLR exceptions here.
 #endif
   }

   // Make sure tree pattern compilation checks for a complete parse
   if (tokens.LA(1) != Token::EOF) {
     throw StartRuleDoesNotConsumeFullPattern();
   }

   return ParseTreePattern(this, pattern, patternRuleIndex, tree);
 }

 Lexer* ParseTreePatternMatcher::getLexer() {
   return _lexer;
 }

 Parser* ParseTreePatternMatcher::getParser() {
   return _parser;
 }

 ParseTree* ParseTreePatternMatcher::matchImpl(ParseTree *tree, ParseTree *patternTree,
                                               std::map<std::string, std::vector<ParseTree *>> &labels) {
   if (tree == nullptr) {
     throw IllegalArgumentException("tree cannot be nul");
   }

   if (patternTree == nullptr) {
     throw IllegalArgumentException("patternTree cannot be nul");
   }

   // x and <ID>, x and y, or x and x; or could be mismatched types
   if (is<TerminalNode *>(tree) && is<TerminalNode *>(patternTree)) {
     TerminalNode *t1 = dynamic_cast<TerminalNode *>(tree);
     TerminalNode *t2 = dynamic_cast<TerminalNode *>(patternTree);

     ParseTree *mismatchedNode = nullptr;
     // both are tokens and they have same type
     if (t1->getSymbol()->getType() == t2->getSymbol()->getType()) {
       if (is<TokenTagToken *>(t2->getSymbol())) { // x and <ID>
         TokenTagToken *tokenTagToken = dynamic_cast<TokenTagToken *>(t2->getSymbol());

         // track label->list-of-nodes for both token name and label (if any)
         labels[tokenTagToken->getTokenName()].push_back(tree);
         if (tokenTagToken->getLabel() != "") {
           labels[tokenTagToken->getLabel()].push_back(tree);
         }
       } else if (t1->getText() == t2->getText()) {
         // x and x
       } else {
         // x and y
         if (mismatchedNode == nullptr) {
           mismatchedNode = t1;
         }
       }
     } else {
       if (mismatchedNode == nullptr) {
         mismatchedNode = t1;
       }
     }

     return mismatchedNode;
   }

   if (is<ParserRuleContext *>(tree) && is<ParserRuleContext *>(patternTree)) {
     ParserRuleContext *r1 = dynamic_cast<ParserRuleContext *>(tree);
     ParserRuleContext *r2 = dynamic_cast<ParserRuleContext *>(patternTree);
     ParseTree *mismatchedNode = nullptr;

     // (expr ...) and <expr>
     RuleTagToken *ruleTagToken = getRuleTagToken(r2);
     if (ruleTagToken != nullptr) {
       //ParseTreeMatch *m = nullptr; // unused?
       if (r1->getRuleIndex() == r2->getRuleIndex()) {
         // track label->list-of-nodes for both rule name and label (if any)
         labels[ruleTagToken->getRuleName()].push_back(tree);
         if (ruleTagToken->getLabel() != "") {
           labels[ruleTagToken->getLabel()].push_back(tree);
         }
       } else {
         if (!mismatchedNode) {
           mismatchedNode = r1;
         }
       }

       return mismatchedNode;
     }

     // (expr ...) and (expr ...)
     if (r1->children.size() != r2->children.size()) {
       if (mismatchedNode == nullptr) {
         mismatchedNode = r1;
       }

       return mismatchedNode;
     }

     std::size_t n = r1->children.size();
     for (size_t i = 0; i < n; i++) {
       ParseTree *childMatch = matchImpl(r1->children[i], patternTree->children[i], labels);
       if (childMatch) {
         return childMatch;
       }
     }

     return mismatchedNode;
   }

   // if nodes aren't both tokens or both rule nodes, can't match
   return tree;
 }

 RuleTagToken* ParseTreePatternMatcher::getRuleTagToken(ParseTree *t) {
   if (t->children.size() == 1 && is<TerminalNode *>(t->children[0])) {
     TerminalNode *c = dynamic_cast<TerminalNode *>(t->children[0]);
     if (is<RuleTagToken *>(c->getSymbol())) {
       return dynamic_cast<RuleTagToken *>(c->getSymbol());
     }
   }
   return nullptr;
 }

 std::vector<std::unique_ptr<Token>> ParseTreePatternMatcher::tokenize(const std::string &pattern) {
   // split pattern into chunks: sea (raw input) and islands (<ID>, <expr>)
   std::vector<Chunk> chunks = split(pattern);

   // create token stream from text and tags
   std::vector<std::unique_ptr<Token>> tokens;
   for (auto chunk : chunks) {
     if (is<TagChunk *>(&chunk)) {
       TagChunk &tagChunk = (TagChunk&)chunk;
       // add special rule token or conjure up new token from name
       if (isupper(tagChunk.getTag()[0])) {
         size_t ttype = _parser->getTokenType(tagChunk.getTag());
         if (ttype == Token::INVALID_TYPE) {
           throw IllegalArgumentException("Unknown token " + tagChunk.getTag() + " in pattern: " + pattern);
         }
         tokens.emplace_back(new TokenTagToken(tagChunk.getTag(), (int)ttype, tagChunk.getLabel()));
       } else if (islower(tagChunk.getTag()[0])) {
         size_t ruleIndex = _parser->getRuleIndex(tagChunk.getTag());
         if (ruleIndex == INVALID_INDEX) {
           throw IllegalArgumentException("Unknown rule " + tagChunk.getTag() + " in pattern: " + pattern);
         }
         size_t ruleImaginaryTokenType = _parser->getATNWithBypassAlts().ruleToTokenType[ruleIndex];
         tokens.emplace_back(new RuleTagToken(tagChunk.getTag(), ruleImaginaryTokenType, tagChunk.getLabel()));
       } else {
         throw IllegalArgumentException("invalid tag: " + tagChunk.getTag() + " in pattern: " + pattern);
       }
     } else {
       TextChunk &textChunk = (TextChunk&)chunk;
       ANTLRInputStream input(textChunk.getText());
       _lexer->setInputStream(&input);
       std::unique_ptr<Token> t(_lexer->nextToken());
       while (t->getType() != Token::EOF) {
         tokens.push_back(std::move(t));
         t = _lexer->nextToken();
       }
       _lexer->setInputStream(nullptr);
     }
   }

   return tokens;
 }

 std::vector<Chunk> ParseTreePatternMatcher::split(const std::string &pattern) {
   size_t p = 0;
   size_t n = pattern.length();
   std::vector<Chunk> chunks;

   // find all start and stop indexes first, then collect
   std::vector<size_t> starts;
   std::vector<size_t> stops;
   while (p < n) {
     if (p == pattern.find(_escape + _start,p)) {
       p += _escape.length() + _start.length();
     } else if (p == pattern.find(_escape + _stop,p)) {
       p += _escape.length() + _stop.length();
     } else if (p == pattern.find(_start,p)) {
       starts.push_back(p);
       p += _start.length();
     } else if (p == pattern.find(_stop,p)) {
       stops.push_back(p);
       p += _stop.length();
     } else {
       p++;
     }
   }

   if (starts.size() > stops.size()) {
     throw IllegalArgumentException("unterminated tag in pattern: " + pattern);
   }

   if (starts.size() < stops.size()) {
     throw IllegalArgumentException("missing start tag in pattern: " + pattern);
   }

   size_t ntags = starts.size();
   for (size_t i = 0; i < ntags; i++) {
     if (starts[i] >= stops[i]) {
       throw IllegalArgumentException("tag delimiters out of order in pattern: " + pattern);
     }
   }

   // collect into chunks now
   if (ntags == 0) {
     std::string text = pattern.substr(0, n);
     chunks.push_back(TextChunk(text));
   }

   if (ntags > 0 && starts[0] > 0) { // copy text up to first tag into chunks
     std::string text = pattern.substr(0, starts[0]);
     chunks.push_back(TextChunk(text));
   }

   for (size_t i = 0; i < ntags; i++) {
     // copy inside of <tag>
     std::string tag = pattern.substr(starts[i] + _start.length(), stops[i] - (starts[i] + _start.length()));
     std::string ruleOrToken = tag;
     std::string label = "";
     size_t colon = tag.find(':');
     if (colon != std::string::npos) {
       label = tag.substr(0,colon);
       ruleOrToken = tag.substr(colon + 1, tag.length() - (colon + 1));
     }
     chunks.push_back(TagChunk(label, ruleOrToken));
     if (i + 1 < ntags) {
       // copy from end of <tag> to start of next
       std::string text = pattern.substr(stops[i] + _stop.length(), starts[i + 1] - (stops[i] + _stop.length()));
       chunks.push_back(TextChunk(text));
     }
   }

   if (ntags > 0) {
     size_t afterLastTag = stops[ntags - 1] + _stop.length();
     if (afterLastTag < n) { // copy text from end of last tag to end
       std::string text = pattern.substr(afterLastTag, n - afterLastTag);
       chunks.push_back(TextChunk(text));
     }
   }

   // strip out all backslashes from text chunks but not tags
   for (size_t i = 0; i < chunks.size(); i++) {
     Chunk &c = chunks[i];
     if (is<TextChunk *>(&c)) {
       TextChunk &tc = (TextChunk&)c;
       std::string unescaped = tc.getText();
       unescaped.erase(std::remove(unescaped.begin(), unescaped.end(), '\\'), unescaped.end());
       if (unescaped.length() < tc.getText().length()) {
         chunks[i] = TextChunk(unescaped);
       }
     }
   }

   return chunks;
 }

 void ParseTreePatternMatcher::InitializeInstanceFields() {
   _start = "<";
   _stop = ">";
   _escape = "\\";
 }
	/* Copyright (c) 2012-2017 The ANTLR Project. All rights reserved.
	* Use of this file is governed by the BSD 3-clause license that
	* can be found in the LICENSE.txt file in the project root.
	*/

	#include "tree/pattern/ParseTreePattern.h"
	#include "tree/pattern/ParseTreeMatch.h"
	#include "tree/TerminalNode.h"
	#include "CommonTokenStream.h"
	#include "ParserInterpreter.h"
	#include "tree/pattern/TokenTagToken.h"
	#include "ParserRuleContext.h"
	#include "tree/pattern/RuleTagToken.h"
	#include "tree/pattern/TagChunk.h"
	#include "atn/ATN.h"
	#include "Lexer.h"
	#include "BailErrorStrategy.h"

	#include "ListTokenSource.h"
	#include "tree/pattern/TextChunk.h"
	#include "ANTLRInputStream.h"
	#include "support/Arrays.h"
	#include "Exceptions.h"
	#include "support/StringUtils.h"
	#include "support/CPPUtils.h"

	#include "tree/pattern/ParseTreePatternMatcher.h"

	using namespace antlr4;
	using namespace antlr4::tree;
	using namespace antlr4::tree::pattern;
	using namespace antlrcpp;

	ParseTreePatternMatcher::CannotInvokeStartRule::CannotInvokeStartRule(const RuntimeException &e) : RuntimeException(e.what()) {
	}

	ParseTreePatternMatcher::CannotInvokeStartRule::~CannotInvokeStartRule() {
	}

	ParseTreePatternMatcher::StartRuleDoesNotConsumeFullPattern::~StartRuleDoesNotConsumeFullPattern() {
	}

	ParseTreePatternMatcher::ParseTreePatternMatcher(Lexer lexer, Parser parser) : _lexer(lexer), _parser(parser) {
	InitializeInstanceFields();
	}

	ParseTreePatternMatcher::~ParseTreePatternMatcher() {
	}

	void ParseTreePatternMatcher::setDelimiters(const std::string &start, const std::string &stop, const std::string &escapeLeft) {
	if (start.empty()) {
	throw IllegalArgumentException("start cannot be null or empty");
	}

	if (stop.empty()) {
	throw IllegalArgumentException("stop cannot be null or empty");
	}

	_start = start;
	_stop = stop;
	_escape = escapeLeft;
	}

	bool ParseTreePatternMatcher::matches(ParseTree *tree, const std::string &pattern, int patternRuleIndex) {
	ParseTreePattern p = compile(pattern, patternRuleIndex);
	return matches(tree, p);
	}

	bool ParseTreePatternMatcher::matches(ParseTree *tree, const ParseTreePattern &pattern) {
	std::map<std::string, std::vector<ParseTree *>> labels;
	ParseTree *mismatchedNode = matchImpl(tree, pattern.getPatternTree(), labels);
	return mismatchedNode == nullptr;
	}

	ParseTreeMatch ParseTreePatternMatcher::match(ParseTree *tree, const std::string &pattern, int patternRuleIndex) {
	ParseTreePattern p = compile(pattern, patternRuleIndex);
	return match(tree, p);
	}

	ParseTreeMatch ParseTreePatternMatcher::match(ParseTree *tree, const ParseTreePattern &pattern) {
	std::map<std::string, std::vector<ParseTree *>> labels;
	tree::ParseTree *mismatchedNode = matchImpl(tree, pattern.getPatternTree(), labels);
	return ParseTreeMatch(tree, pattern, labels, mismatchedNode);
	}

	ParseTreePattern ParseTreePatternMatcher::compile(const std::string &pattern, int patternRuleIndex) {
	ListTokenSource tokenSrc(tokenize(pattern));
	CommonTokenStream tokens(&tokenSrc);

	ParserInterpreter parserInterp(_parser->getGrammarFileName(), _parser->getVocabulary(),
	_parser->getRuleNames(), _parser->getATNWithBypassAlts(), &tokens);

	ParserRuleContext *tree = nullptr;
	try {
	parserInterp.setErrorHandler(std::make_shared<BailErrorStrategy>());
	tree = parserInterp.parse(patternRuleIndex);
	} catch (ParseCancellationException &e) {
	#if defined(_MSC_FULL_VER) && _MSC_FULL_VER < 190023026
	// rethrow_if_nested is not available before VS 2015.
	throw e;
	#else
	std::rethrow_if_nested(e); // Unwrap the nested exception.
	#endif
	} catch (RecognitionException &re) {
	throw re;
	#if defined(_MSC_FULL_VER) && _MSC_FULL_VER < 190023026
	} catch (std::exception &e) {
	// throw_with_nested is not available before VS 2015.
	throw e;
	#else
	} catch (std::exception & /e/) {
	std::throw_with_nested((const char*)"Cannot invoke start rule"); // Wrap any other exception. We should however probably use one of the ANTLR exceptions here.
	#endif
	}

	// Make sure tree pattern compilation checks for a complete parse
	if (tokens.LA(1) != Token::EOF) {
	throw StartRuleDoesNotConsumeFullPattern();
	}

	return ParseTreePattern(this, pattern, patternRuleIndex, tree);
	}

	Lexer* ParseTreePatternMatcher::getLexer() {
	return _lexer;
	}

	Parser* ParseTreePatternMatcher::getParser() {
	return _parser;
	}

	ParseTree* ParseTreePatternMatcher::matchImpl(ParseTree tree, ParseTree patternTree,
	std::map<std::string, std::vector<ParseTree *>> &labels) {
	if (tree == nullptr) {
	throw IllegalArgumentException("tree cannot be nul");
	}

	if (patternTree == nullptr) {
	throw IllegalArgumentException("patternTree cannot be nul");
	}

	// x and <ID>, x and y, or x and x; or could be mismatched types
	if (is<TerminalNode >(tree) && is<TerminalNode >(patternTree)) {
	TerminalNode t1 = dynamic_cast<TerminalNode >(tree);
	TerminalNode t2 = dynamic_cast<TerminalNode >(patternTree);

	ParseTree *mismatchedNode = nullptr;
	// both are tokens and they have same type
	if (t1->getSymbol()->getType() == t2->getSymbol()->getType()) {
	if (is<TokenTagToken *>(t2->getSymbol())) { // x and <ID>
	TokenTagToken tokenTagToken = dynamic_cast<TokenTagToken >(t2->getSymbol());

	// track label->list-of-nodes for both token name and label (if any)
	labels[tokenTagToken->getTokenName()].push_back(tree);
	if (tokenTagToken->getLabel() != "") {
	labels[tokenTagToken->getLabel()].push_back(tree);
	}
	} else if (t1->getText() == t2->getText()) {
	// x and x
	} else {
	// x and y
	if (mismatchedNode == nullptr) {
	mismatchedNode = t1;
	}
	}
	} else {
	if (mismatchedNode == nullptr) {
	mismatchedNode = t1;
	}
	}

	return mismatchedNode;
	}

	if (is<ParserRuleContext >(tree) && is<ParserRuleContext >(patternTree)) {
	ParserRuleContext r1 = dynamic_cast<ParserRuleContext >(tree);
	ParserRuleContext r2 = dynamic_cast<ParserRuleContext >(patternTree);
	ParseTree *mismatchedNode = nullptr;

	// (expr ...) and <expr>
	RuleTagToken *ruleTagToken = getRuleTagToken(r2);
	if (ruleTagToken != nullptr) {
	//ParseTreeMatch *m = nullptr; // unused?
	if (r1->getRuleIndex() == r2->getRuleIndex()) {
	// track label->list-of-nodes for both rule name and label (if any)
	labels[ruleTagToken->getRuleName()].push_back(tree);
	if (ruleTagToken->getLabel() != "") {
	labels[ruleTagToken->getLabel()].push_back(tree);
	}
	} else {
	if (!mismatchedNode) {
	mismatchedNode = r1;
	}
	}

	return mismatchedNode;
	}

	// (expr ...) and (expr ...)
	if (r1->children.size() != r2->children.size()) {
	if (mismatchedNode == nullptr) {
	mismatchedNode = r1;
	}

	return mismatchedNode;
	}

	std::size_t n = r1->children.size();
	for (size_t i = 0; i < n; i++) {
	ParseTree *childMatch = matchImpl(r1->children[i], patternTree->children[i], labels);
	if (childMatch) {
	return childMatch;
	}
	}

	return mismatchedNode;
	}

	// if nodes aren't both tokens or both rule nodes, can't match
	return tree;
	}

	RuleTagToken* ParseTreePatternMatcher::getRuleTagToken(ParseTree *t) {
	if (t->children.size() == 1 && is<TerminalNode *>(t->children[0])) {
	TerminalNode c = dynamic_cast<TerminalNode >(t->children[0]);
	if (is<RuleTagToken *>(c->getSymbol())) {
	return dynamic_cast<RuleTagToken *>(c->getSymbol());
	}
	}
	return nullptr;
	}

	std::vector<std::unique_ptr<Token>> ParseTreePatternMatcher::tokenize(const std::string &pattern) {
	// split pattern into chunks: sea (raw input) and islands (<ID>, <expr>)
	std::vector<Chunk> chunks = split(pattern);

	// create token stream from text and tags
	std::vector<std::unique_ptr<Token>> tokens;
	for (auto chunk : chunks) {
	if (is<TagChunk *>(&chunk)) {
	TagChunk &tagChunk = (TagChunk&)chunk;
	// add special rule token or conjure up new token from name
	if (isupper(tagChunk.getTag()[0])) {
	size_t ttype = _parser->getTokenType(tagChunk.getTag());
	if (ttype == Token::INVALID_TYPE) {
	throw IllegalArgumentException("Unknown token " + tagChunk.getTag() + " in pattern: " + pattern);
	}
	tokens.emplace_back(new TokenTagToken(tagChunk.getTag(), (int)ttype, tagChunk.getLabel()));
	} else if (islower(tagChunk.getTag()[0])) {
	size_t ruleIndex = _parser->getRuleIndex(tagChunk.getTag());
	if (ruleIndex == INVALID_INDEX) {
	throw IllegalArgumentException("Unknown rule " + tagChunk.getTag() + " in pattern: " + pattern);
	}
	size_t ruleImaginaryTokenType = _parser->getATNWithBypassAlts().ruleToTokenType[ruleIndex];
	tokens.emplace_back(new RuleTagToken(tagChunk.getTag(), ruleImaginaryTokenType, tagChunk.getLabel()));
	} else {
	throw IllegalArgumentException("invalid tag: " + tagChunk.getTag() + " in pattern: " + pattern);
	}
	} else {
	TextChunk &textChunk = (TextChunk&)chunk;
	ANTLRInputStream input(textChunk.getText());
	_lexer->setInputStream(&input);
	std::unique_ptr<Token> t(_lexer->nextToken());
	while (t->getType() != Token::EOF) {
	tokens.push_back(std::move(t));
	t = _lexer->nextToken();
	}
	_lexer->setInputStream(nullptr);
	}
	}

	return tokens;
	}

	std::vector<Chunk> ParseTreePatternMatcher::split(const std::string &pattern) {
	size_t p = 0;
	size_t n = pattern.length();
	std::vector<Chunk> chunks;

	// find all start and stop indexes first, then collect
	std::vector<size_t> starts;
	std::vector<size_t> stops;
	while (p < n) {
	if (p == pattern.find(_escape + _start,p)) {
	p += _escape.length() + _start.length();
	} else if (p == pattern.find(_escape + _stop,p)) {
	p += _escape.length() + _stop.length();
	} else if (p == pattern.find(_start,p)) {
	starts.push_back(p);
	p += _start.length();
	} else if (p == pattern.find(_stop,p)) {
	stops.push_back(p);
	p += _stop.length();
	} else {
	p++;
	}
	}

	if (starts.size() > stops.size()) {
	throw IllegalArgumentException("unterminated tag in pattern: " + pattern);
	}

	if (starts.size() < stops.size()) {
	throw IllegalArgumentException("missing start tag in pattern: " + pattern);
	}

	size_t ntags = starts.size();
	for (size_t i = 0; i < ntags; i++) {
	if (starts[i] >= stops[i]) {
	throw IllegalArgumentException("tag delimiters out of order in pattern: " + pattern);
	}
	}

	// collect into chunks now
	if (ntags == 0) {
	std::string text = pattern.substr(0, n);
	chunks.push_back(TextChunk(text));
	}

	if (ntags > 0 && starts[0] > 0) { // copy text up to first tag into chunks
	std::string text = pattern.substr(0, starts[0]);
	chunks.push_back(TextChunk(text));
	}

	for (size_t i = 0; i < ntags; i++) {
	// copy inside of <tag>
	std::string tag = pattern.substr(starts[i] + _start.length(), stops[i] - (starts[i] + _start.length()));
	std::string ruleOrToken = tag;
	std::string label = "";
	size_t colon = tag.find(':');
	if (colon != std::string::npos) {
	label = tag.substr(0,colon);
	ruleOrToken = tag.substr(colon + 1, tag.length() - (colon + 1));
	}
	chunks.push_back(TagChunk(label, ruleOrToken));
	if (i + 1 < ntags) {
	// copy from end of <tag> to start of next
	std::string text = pattern.substr(stops[i] + _stop.length(), starts[i + 1] - (stops[i] + _stop.length()));
	chunks.push_back(TextChunk(text));
	}
	}

	if (ntags > 0) {
	size_t afterLastTag = stops[ntags - 1] + _stop.length();
	if (afterLastTag < n) { // copy text from end of last tag to end
	std::string text = pattern.substr(afterLastTag, n - afterLastTag);
	chunks.push_back(TextChunk(text));
	}
	}

	// strip out all backslashes from text chunks but not tags
	for (size_t i = 0; i < chunks.size(); i++) {
	Chunk &c = chunks[i];
	if (is<TextChunk *>(&c)) {
	TextChunk &tc = (TextChunk&)c;
	std::string unescaped = tc.getText();
	unescaped.erase(std::remove(unescaped.begin(), unescaped.end(), '\\'), unescaped.end());
	if (unescaped.length() < tc.getText().length()) {
	chunks[i] = TextChunk(unescaped);
	}
	}
	}

	return chunks;
	}

	void ParseTreePatternMatcher::InitializeInstanceFields() {
	_start = "<";
	_stop = ">";
	_escape = "\\";
	}