blob: aed1423ce39d1c429d3b7c30972878cc578f704c [file] [log] [blame]
// Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
#ifndef VM_REGEXP_PARSER_H_
#define VM_REGEXP_PARSER_H_
#include "vm/allocation.h"
#include "vm/growable_array.h"
#include "vm/regexp_ast.h"
namespace dart {
// Accumulates RegExp atoms and assertions into lists of terms and alternatives.
class RegExpBuilder: public ZoneAllocated {
public:
RegExpBuilder();
void AddCharacter(uint16_t character);
// "Adds" an empty expression. Does nothing except consume a
// following quantifier
void AddEmpty();
void AddAtom(RegExpTree* tree);
void AddAssertion(RegExpTree* tree);
void NewAlternative(); // '|'
void AddQuantifierToAtom(
intptr_t min, intptr_t max, RegExpQuantifier::QuantifierType type);
RegExpTree* ToRegExp();
private:
void FlushCharacters();
void FlushText();
void FlushTerms();
Zone* zone() const { return zone_; }
Zone* zone_;
bool pending_empty_;
ZoneGrowableArray<uint16_t>* characters_;
GrowableArray<RegExpTree*> terms_;
GrowableArray<RegExpTree*> text_;
GrowableArray<RegExpTree*> alternatives_;
#ifdef DEBUG
enum {ADD_NONE, ADD_CHAR, ADD_TERM, ADD_ASSERT, ADD_ATOM} last_added_;
#define LAST(x) last_added_ = x;
#else
#define LAST(x)
#endif
};
class RegExpParser : public ValueObject {
public:
RegExpParser(const String& in,
String* error,
bool multiline_mode);
static bool ParseFunction(ParsedFunction* parsed_function);
static bool ParseRegExp(const String& input,
bool multiline,
RegExpCompileData* result);
RegExpTree* ParsePattern();
RegExpTree* ParseDisjunction();
RegExpTree* ParseGroup();
RegExpTree* ParseCharacterClass();
// Parses a {...,...} quantifier and stores the range in the given
// out parameters.
bool ParseIntervalQuantifier(intptr_t* min_out, intptr_t* max_out);
// Parses and returns a single escaped character. The character
// must not be 'b' or 'B' since they are usually handle specially.
uint32_t ParseClassCharacterEscape();
// Checks whether the following is a length-digit hexadecimal number,
// and sets the value if it is.
bool ParseHexEscape(intptr_t length, uint32_t* value);
uint32_t ParseOctalLiteral();
// Tries to parse the input as a back reference. If successful it
// stores the result in the output parameter and returns true. If
// it fails it will push back the characters read so the same characters
// can be reparsed.
bool ParseBackReferenceIndex(intptr_t* index_out);
CharacterRange ParseClassAtom(uint16_t* char_class);
void ReportError(const char* message);
void Advance();
void Advance(intptr_t dist);
void Reset(intptr_t pos);
// Reports whether the pattern might be used as a literal search string.
// Only use if the result of the parse is a single atom node.
bool simple();
bool contains_anchor() { return contains_anchor_; }
void set_contains_anchor() { contains_anchor_ = true; }
intptr_t captures_started() { return captures_ == NULL ?
0 : captures_->length(); }
intptr_t position() { return next_pos_ - 1; }
bool failed() { return failed_; }
static const intptr_t kMaxCaptures = 1 << 16;
static const uint32_t kEndMarker = (1 << 21);
private:
enum SubexpressionType {
INITIAL,
CAPTURE, // All positive values represent captures.
POSITIVE_LOOKAHEAD,
NEGATIVE_LOOKAHEAD,
GROUPING
};
class RegExpParserState : public ZoneAllocated {
public:
RegExpParserState(RegExpParserState* previous_state,
SubexpressionType group_type,
intptr_t disjunction_capture_index,
Zone *zone)
: previous_state_(previous_state),
builder_(new(zone) RegExpBuilder()),
group_type_(group_type),
disjunction_capture_index_(disjunction_capture_index) {}
// Parser state of containing expression, if any.
RegExpParserState* previous_state() { return previous_state_; }
bool IsSubexpression() { return previous_state_ != NULL; }
// RegExpBuilder building this regexp's AST.
RegExpBuilder* builder() { return builder_; }
// Type of regexp being parsed (parenthesized group or entire regexp).
SubexpressionType group_type() { return group_type_; }
// Index in captures array of first capture in this sub-expression, if any.
// Also the capture index of this sub-expression itself, if group_type
// is CAPTURE.
intptr_t capture_index() { return disjunction_capture_index_; }
private:
// Linked list implementation of stack of states.
RegExpParserState* previous_state_;
// Builder for the stored disjunction.
RegExpBuilder* builder_;
// Stored disjunction type (capture, look-ahead or grouping), if any.
SubexpressionType group_type_;
// Stored disjunction's capture index (if any).
intptr_t disjunction_capture_index_;
};
Zone* zone() { return zone_; }
uint32_t current() { return current_; }
bool has_more() { return has_more_; }
bool has_next() { return next_pos_ < in().Length(); }
uint32_t Next();
const String& in() { return in_; }
void ScanForCaptures();
Zone* zone_;
String* error_;
ZoneGrowableArray<RegExpCapture*>* captures_;
const String& in_;
uint32_t current_;
intptr_t next_pos_;
// The capture count is only valid after we have scanned for captures.
intptr_t capture_count_;
bool has_more_;
bool multiline_;
bool simple_;
bool contains_anchor_;
bool is_scanned_for_captures_;
bool failed_;
};
} // namespace dart
#endif // VM_REGEXP_PARSER_H_