dart::TextNode Class Reference

#include <regexp.h>

Inheritance diagram for dart::TextNode:

Public Member Functions
	TextNode (ZoneGrowableArray< TextElement > *elms, bool read_backward, RegExpNode *on_success)
	TextNode (RegExpCharacterClass *that, bool read_backward, RegExpNode *on_success)
virtual void	Accept (NodeVisitor *visitor)
virtual void	Emit (RegExpCompiler *compiler, Trace *trace)
virtual intptr_t	EatsAtLeast (intptr_t still_to_find, intptr_t budget, bool not_at_start)
virtual void	GetQuickCheckDetails (QuickCheckDetails *details, RegExpCompiler *compiler, intptr_t characters_filled_in, bool not_at_start)
ZoneGrowableArray< TextElement > *	elements ()
bool	read_backward ()
void	MakeCaseIndependent (bool is_one_byte)
virtual intptr_t	GreedyLoopTextLength ()
virtual RegExpNode *	GetSuccessorOfOmnivorousTextNode (RegExpCompiler *compiler)
virtual void	FillInBMInfo (intptr_t offset, intptr_t budget, BoyerMooreLookahead *bm, bool not_at_start)
void	CalculateOffsets ()
virtual RegExpNode *	FilterOneByte (intptr_t depth)
Public Member Functions inherited from dart::SeqRegExpNode
	SeqRegExpNode (RegExpNode *on_success)
RegExpNode *	on_success ()
void	set_on_success (RegExpNode *node)
Public Member Functions inherited from dart::RegExpNode
	RegExpNode (Zone *zone)
virtual	~RegExpNode ()
bool	EmitQuickCheck (RegExpCompiler *compiler, Trace *bounds_check_trace, Trace *trace, bool preload_has_checked_bounds, BlockLabel *on_possible_success, QuickCheckDetails *details_return, bool fall_through_on_failure)
RegExpNode *	replacement ()
RegExpNode *	set_replacement (RegExpNode *replacement)
void	SaveBMInfo (BoyerMooreLookahead *bm, bool not_at_start, intptr_t offset)
BlockLabel *	label ()
NodeInfo *	info ()
BoyerMooreLookahead *	bm_info (bool not_at_start)
Zone *	zone () const
Public Member Functions inherited from dart::ZoneAllocated
	ZoneAllocated ()
void *	operator new (size_t size)
void *	operator new (size_t size, Zone *zone)
void	operator delete (void *pointer)

Static Public Member Functions
static TextNode *	CreateForCharacterRanges (ZoneGrowableArray< CharacterRange > *ranges, bool read_backward, RegExpNode *on_success, RegExpFlags flags)
static TextNode *	CreateForSurrogatePair (CharacterRange lead, CharacterRange trail, bool read_backward, RegExpNode *on_success, RegExpFlags flags)

Additional Inherited Members
Static Public Attributes inherited from dart::RegExpNode
static constexpr intptr_t	kNodeIsTooComplexForGreedyLoops = -1
static constexpr intptr_t	kRecursionBudget = 200
static constexpr intptr_t	kMaxCopiesCodeGenerated = 10
Protected Types inherited from dart::RegExpNode
enum	LimitResult { DONE , CONTINUE }
Protected Member Functions inherited from dart::SeqRegExpNode
RegExpNode *	FilterSuccessor (intptr_t depth)
Protected Member Functions inherited from dart::RegExpNode
LimitResult	LimitVersions (RegExpCompiler *compiler, Trace *trace)
void	set_bm_info (bool not_at_start, BoyerMooreLookahead *bm)
Protected Attributes inherited from dart::RegExpNode
RegExpNode *	replacement_

Detailed Description

Definition at line 650 of file regexp.h.

Constructor & Destructor Documentation

TextNode() [1/2]

dart::TextNode::TextNode ( ZoneGrowableArray< TextElement > *  elms, bool  read_backward, RegExpNode *  on_success  )

inline

Definition at line 652 of file regexp.h.

      : SeqRegExpNode(on_success), elms_(elms), read_backward_(read_backward) {}

TextNode() [2/2]

dart::TextNode::TextNode ( RegExpCharacterClass *  that, bool  read_backward, RegExpNode *  on_success  )

inline

Definition at line 656 of file regexp.h.

      : SeqRegExpNode(on_success),
        elms_(new(zone()) ZoneGrowableArray<TextElement>(1)),
        read_backward_(read_backward) {
    elms_->Add(TextElement::CharClass(that));
  }

Member Function Documentation

Accept()

virtual void dart::TextNode::Accept ( NodeVisitor *  visitor )

virtual

Implements dart::RegExpNode.

CalculateOffsets()

void dart::TextNode::CalculateOffsets

(

)

Definition at line 5104 of file regexp.cc.

                                {
  intptr_t element_count = elements()->length();
  // Set up the offsets of the elements relative to the start.  This is a fixed
  // quantity since a TextNode can only contain fixed-width things.
  intptr_t cp_offset = 0;
  for (intptr_t i = 0; i < element_count; i++) {
    TextElement& elm = (*elements())[i];
    elm.set_cp_offset(cp_offset);
    cp_offset += elm.length();
  }
}

CreateForCharacterRanges()

TextNode * dart::TextNode::CreateForCharacterRanges ( ZoneGrowableArray< CharacterRange > *  ranges, bool  read_backward, RegExpNode *  on_success, RegExpFlags  flags  )

static

Definition at line 2480 of file regexp.cc.

                       {
  ASSERT(ranges != nullptr);
  ZoneGrowableArray<TextElement>* elms = new ZoneGrowableArray<TextElement>(1);
  elms->Add(TextElement::CharClass(new RegExpCharacterClass(ranges, flags)));
  return new TextNode(elms, read_backward, on_success);
}

CreateForSurrogatePair()

TextNode * dart::TextNode::CreateForSurrogatePair ( CharacterRange  lead, CharacterRange  trail, bool  read_backward, RegExpNode *  on_success, RegExpFlags  flags  )

static

Definition at line 2491 of file regexp.cc.

                                                              {
  auto lead_ranges = CharacterRange::List(on_success->zone(), lead);
  auto trail_ranges = CharacterRange::List(on_success->zone(), trail);
  auto elms = new ZoneGrowableArray<TextElement>(2);
 
  elms->Add(
      TextElement::CharClass(new RegExpCharacterClass(lead_ranges, flags)));
  elms->Add(
      TextElement::CharClass(new RegExpCharacterClass(trail_ranges, flags)));
 
  return new TextNode(elms, read_backward, on_success);
}

EatsAtLeast()

intptr_t dart::TextNode::EatsAtLeast ( intptr_t  still_to_find, intptr_t  budget, bool  not_at_start  )

virtual

Implements dart::RegExpNode.

Definition at line 1524 of file regexp.cc.

                                                  {
  if (read_backward()) return 0;
  intptr_t answer = Length();
  if (answer >= still_to_find) return answer;
  if (budget <= 0) return answer;
  // We are not at start after this node so we set the last argument to 'true'.
  return answer +
         on_success()->EatsAtLeast(still_to_find - answer, budget - 1, true);
}

elements()

ZoneGrowableArray< TextElement > * dart::TextNode::elements ( )

inline

Definition at line 686 of file regexp.h.

{ return elms_; }

Emit()

void dart::TextNode::Emit ( RegExpCompiler *  compiler, Trace *  trace  )

virtual

Implements dart::RegExpNode.

Definition at line 2514 of file regexp.cc.

                                                          {
  LimitResult limit_result = LimitVersions(compiler, trace);
  if (limit_result == DONE) return;
  ASSERT(limit_result == CONTINUE);
 
  if (trace->cp_offset() + Length() > RegExpMacroAssembler::kMaxCPOffset) {
    compiler->SetRegExpTooBig();
    return;
  }
 
  if (compiler->one_byte()) {
    intptr_t dummy = 0;
    TextEmitPass(compiler, NON_LATIN1_MATCH, false, trace, false, &dummy);
  }
 
  bool first_elt_done = false;
  intptr_t bound_checked_to = trace->cp_offset() - 1;
  bound_checked_to += trace->bound_checked_up_to();
 
  // If a character is preloaded into the current character register then
  // check that now.
  if (trace->characters_preloaded() == 1) {
    for (intptr_t pass = kFirstRealPass; pass <= kLastPass; pass++) {
      TextEmitPass(compiler, static_cast<TextEmitPassType>(pass), true, trace,
                   false, &bound_checked_to);
    }
    first_elt_done = true;
  }
 
  for (intptr_t pass = kFirstRealPass; pass <= kLastPass; pass++) {
    TextEmitPass(compiler, static_cast<TextEmitPassType>(pass), false, trace,
                 first_elt_done, &bound_checked_to);
  }
 
  Trace successor_trace(*trace);
  // If we advance backward, we may end up at the start.
  successor_trace.AdvanceCurrentPositionInTrace(
      read_backward() ? -Length() : Length(), compiler);
  successor_trace.set_at_start(read_backward() ? Trace::UNKNOWN
                                               : Trace::FALSE_VALUE);
  RecursionCheck rc(compiler);
  on_success()->Emit(compiler, &successor_trace);
}

FillInBMInfo()

void dart::TextNode::FillInBMInfo ( intptr_t  offset, intptr_t  budget, BoyerMooreLookahead *  bm, bool  not_at_start  )

virtual

Reimplemented from dart::SeqRegExpNode.

Definition at line 5203 of file regexp.cc.

                                               {
  if (initial_offset >= bm->length()) return;
  intptr_t offset = initial_offset;
  intptr_t max_char = bm->max_char();
  for (intptr_t i = 0; i < elements()->length(); i++) {
    if (offset >= bm->length()) {
      if (initial_offset == 0) set_bm_info(not_at_start, bm);
      return;
    }
    TextElement text = elements()->At(i);
    if (text.text_type() == TextElement::ATOM) {
      RegExpAtom* atom = text.atom();
      for (intptr_t j = 0; j < atom->length(); j++, offset++) {
        if (offset >= bm->length()) {
          if (initial_offset == 0) set_bm_info(not_at_start, bm);
          return;
        }
        uint16_t character = atom->data()->At(j);
        if (atom->flags().IgnoreCase()) {
          int32_t chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
          intptr_t length = GetCaseIndependentLetters(
              character, bm->max_char() == Symbols::kMaxOneCharCodeSymbol,
              chars);
          for (intptr_t j = 0; j < length; j++) {
            bm->Set(offset, chars[j]);
          }
        } else {
          if (character <= max_char) bm->Set(offset, character);
        }
      }
    } else {
      ASSERT(text.text_type() == TextElement::CHAR_CLASS);
      RegExpCharacterClass* char_class = text.char_class();
      ZoneGrowableArray<CharacterRange>* ranges = char_class->ranges();
      if (char_class->is_negated()) {
        bm->SetAll(offset);
      } else {
        for (intptr_t k = 0; k < ranges->length(); k++) {
          const CharacterRange& range = ranges->At(k);
          if (range.from() > max_char) continue;
          intptr_t to =
              Utils::Minimum(max_char, static_cast<intptr_t>(range.to()));
          bm->SetInterval(offset, Interval(range.from(), to));
        }
      }
      offset++;
    }
  }
  if (offset >= bm->length()) {
    if (initial_offset == 0) set_bm_info(not_at_start, bm);
    return;
  }
  on_success()->FillInBMInfo(offset, budget - 1, bm,
                             true);  // Not at start after a text node.
  if (initial_offset == 0) set_bm_info(not_at_start, bm);
}

FilterOneByte()

RegExpNode * dart::TextNode::FilterOneByte ( intptr_t  depth )

virtual

Reimplemented from dart::SeqRegExpNode.

Definition at line 1977 of file regexp.cc.

                                                  {
  if (info()->replacement_calculated) return replacement();
  if (depth < 0) return this;
  ASSERT(!info()->visited);
  VisitMarker marker(info());
  intptr_t element_count = elms_->length();
  for (intptr_t i = 0; i < element_count; i++) {
    TextElement elm = elms_->At(i);
    if (elm.text_type() == TextElement::ATOM) {
      ZoneGrowableArray<uint16_t>* quarks = elm.atom()->data();
      for (intptr_t j = 0; j < quarks->length(); j++) {
        uint16_t c = quarks->At(j);
        if (c <= Symbols::kMaxOneCharCodeSymbol) continue;
        if (!elm.atom()->ignore_case()) return set_replacement(nullptr);
        // Here, we need to check for characters whose upper and lower cases
        // are outside the Latin-1 range.
        uint16_t converted = ConvertNonLatin1ToLatin1(c);
        // Character is outside Latin-1 completely
        if (converted == 0) return set_replacement(nullptr);
        // Convert quark to Latin-1 in place.
        (*quarks)[0] = converted;
      }
    } else {
      ASSERT(elm.text_type() == TextElement::CHAR_CLASS);
      RegExpCharacterClass* cc = elm.char_class();
      ZoneGrowableArray<CharacterRange>* ranges = cc->ranges();
      if (!CharacterRange::IsCanonical(ranges)) {
        CharacterRange::Canonicalize(ranges);
      }
      // Now they are in order so we only need to look at the first.
      intptr_t range_count = ranges->length();
      if (cc->is_negated()) {
        if (range_count != 0 && ranges->At(0).from() == 0 &&
            ranges->At(0).to() >= Symbols::kMaxOneCharCodeSymbol) {
          // This will be handled in a later filter.
          if (cc->flags().IgnoreCase() &&
              RangesContainLatin1Equivalents(ranges)) {
            continue;
          }
          return set_replacement(nullptr);
        }
      } else {
        if (range_count == 0 ||
            ranges->At(0).from() > Symbols::kMaxOneCharCodeSymbol) {
          // This will be handled in a later filter.
          if (cc->flags().IgnoreCase() &&
              RangesContainLatin1Equivalents(ranges))
            continue;
          return set_replacement(nullptr);
        }
      }
    }
  }
  return FilterSuccessor(depth - 1);
}

GetQuickCheckDetails()

void dart::TextNode::GetQuickCheckDetails ( QuickCheckDetails *  details, RegExpCompiler *  compiler, intptr_t  characters_filled_in, bool  not_at_start  )

virtual

Implements dart::RegExpNode.

Definition at line 1700 of file regexp.cc.

                                                       {
#if defined(__GNUC__) && defined(__BYTE_ORDER__)
  // TODO(zerny): Make the combination code byte-order independent.
  ASSERT(details->characters() == 1 ||
         (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__));
#endif
  // Do not collect any quick check details if the text node reads backward,
  // since it reads in the opposite direction than we use for quick checks.
  if (read_backward()) return;
  ASSERT(characters_filled_in < details->characters());
  intptr_t characters = details->characters();
  int32_t char_mask;
  if (compiler->one_byte()) {
    char_mask = Symbols::kMaxOneCharCodeSymbol;
  } else {
    char_mask = Utf16::kMaxCodeUnit;
  }
  for (intptr_t k = 0; k < elms_->length(); k++) {
    TextElement elm = elms_->At(k);
    if (elm.text_type() == TextElement::ATOM) {
      ZoneGrowableArray<uint16_t>* quarks = elm.atom()->data();
      for (intptr_t i = 0; i < characters && i < quarks->length(); i++) {
        QuickCheckDetails::Position* pos =
            details->positions(characters_filled_in);
        uint16_t c = quarks->At(i);
        if (c > char_mask) {
          // If we expect a non-Latin1 character from an one-byte string,
          // there is no way we can match. Not even case independent
          // matching can turn an Latin1 character into non-Latin1 or
          // vice versa.
          // TODO(dcarney): issue 3550.  Verify that this works as expected.
          // For example, \u0178 is uppercase of \u00ff (y-umlaut).
          details->set_cannot_match();
          pos->determines_perfectly = false;
          return;
        }
        if (elm.atom()->ignore_case()) {
          int32_t chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
          intptr_t length =
              GetCaseIndependentLetters(c, compiler->one_byte(), chars);
          ASSERT(length != 0);  // Can only happen if c > char_mask (see above).
          if (length == 1) {
            // This letter has no case equivalents, so it's nice and simple
            // and the mask-compare will determine definitely whether we have
            // a match at this character position.
            pos->mask = char_mask;
            pos->value = c;
            pos->determines_perfectly = true;
          } else {
            uint32_t common_bits = char_mask;
            uint32_t bits = chars[0];
            for (intptr_t j = 1; j < length; j++) {
              uint32_t differing_bits = ((chars[j] & common_bits) ^ bits);
              common_bits ^= differing_bits;
              bits &= common_bits;
            }
            // If length is 2 and common bits has only one zero in it then
            // our mask and compare instruction will determine definitely
            // whether we have a match at this character position.  Otherwise
            // it can only be an approximate check.
            uint32_t one_zero = (common_bits | ~char_mask);
            if (length == 2 && ((~one_zero) & ((~one_zero) - 1)) == 0) {
              pos->determines_perfectly = true;
            }
            pos->mask = common_bits;
            pos->value = bits;
          }
        } else {
          // Don't ignore case.  Nice simple case where the mask-compare will
          // determine definitely whether we have a match at this character
          // position.
          pos->mask = char_mask;
          pos->value = c;
          pos->determines_perfectly = true;
        }
        characters_filled_in++;
        ASSERT(characters_filled_in <= details->characters());
        if (characters_filled_in == details->characters()) {
          return;
        }
      }
    } else {
      QuickCheckDetails::Position* pos =
          details->positions(characters_filled_in);
      RegExpCharacterClass* tree = elm.char_class();
      ZoneGrowableArray<CharacterRange>* ranges = tree->ranges();
      ASSERT(!ranges->is_empty());
      if (!CharacterRange::IsCanonical(ranges)) {
        CharacterRange::Canonicalize(ranges);
      }
      if (tree->is_negated()) {
        // A quick check uses multi-character mask and compare.  There is no
        // useful way to incorporate a negative char class into this scheme
        // so we just conservatively create a mask and value that will always
        // succeed.
        pos->mask = 0;
        pos->value = 0;
      } else {
        intptr_t first_range = 0;
        while (ranges->At(first_range).from() > char_mask) {
          first_range++;
          if (first_range == ranges->length()) {
            details->set_cannot_match();
            pos->determines_perfectly = false;
            return;
          }
        }
        CharacterRange range = ranges->At(first_range);
        uint16_t from = range.from();
        uint16_t to = range.to();
        if (to > char_mask) {
          to = char_mask;
        }
        uint32_t differing_bits = (from ^ to);
        // A mask and compare is only perfect if the differing bits form a
        // number like 00011111 with one single block of trailing 1s.
        if ((differing_bits & (differing_bits + 1)) == 0 &&
            from + differing_bits == to) {
          pos->determines_perfectly = true;
        }
        uint32_t common_bits = ~SmearBitsRight(differing_bits);
        uint32_t bits = (from & common_bits);
        for (intptr_t i = first_range + 1; i < ranges->length(); i++) {
          CharacterRange range = ranges->At(i);
          uint16_t from = range.from();
          uint16_t to = range.to();
          if (from > char_mask) continue;
          if (to > char_mask) to = char_mask;
          // Here we are combining more ranges into the mask and compare
          // value.  With each new range the mask becomes more sparse and
          // so the chances of a false positive rise.  A character class
          // with multiple ranges is assumed never to be equivalent to a
          // mask and compare operation.
          pos->determines_perfectly = false;
          uint32_t new_common_bits = (from ^ to);
          new_common_bits = ~SmearBitsRight(new_common_bits);
          common_bits &= new_common_bits;
          bits &= new_common_bits;
          uint32_t differing_bits = (from & common_bits) ^ bits;
          common_bits ^= differing_bits;
          bits &= common_bits;
        }
        pos->mask = common_bits;
        pos->value = bits;
      }
      characters_filled_in++;
      ASSERT(characters_filled_in <= details->characters());
      if (characters_filled_in == details->characters()) {
        return;
      }
    }
  }
  ASSERT(characters_filled_in != details->characters());
  if (!details->cannot_match()) {
    on_success()->GetQuickCheckDetails(details, compiler, characters_filled_in,
                                       true);
  }
}

GetSuccessorOfOmnivorousTextNode()

RegExpNode * dart::TextNode::GetSuccessorOfOmnivorousTextNode ( RegExpCompiler *  compiler )

virtual

Reimplemented from dart::RegExpNode.

Definition at line 2604 of file regexp.cc.

                              {
  if (read_backward()) return nullptr;
  if (elms_->length() != 1) return nullptr;
  TextElement elm = elms_->At(0);
  if (elm.text_type() != TextElement::CHAR_CLASS) return nullptr;
  RegExpCharacterClass* node = elm.char_class();
  ZoneGrowableArray<CharacterRange>* ranges = node->ranges();
  if (!CharacterRange::IsCanonical(ranges)) {
    CharacterRange::Canonicalize(ranges);
  }
  if (node->is_negated()) {
    return ranges->length() == 0 ? on_success() : nullptr;
  }
  if (ranges->length() != 1) return nullptr;
  uint32_t max_char;
  if (compiler->one_byte()) {
    max_char = Symbols::kMaxOneCharCodeSymbol;
  } else {
    max_char = Utf16::kMaxCodeUnit;
  }
  return ranges->At(0).IsEverything(max_char) ? on_success() : nullptr;
}

GreedyLoopTextLength()

intptr_t dart::TextNode::GreedyLoopTextLength ( )

virtual

Reimplemented from dart::RegExpNode.

Definition at line 2599 of file regexp.cc.

                                        {
  TextElement elm = elms_->At(elms_->length() - 1);
  return elm.cp_offset() + elm.length();
}

MakeCaseIndependent()

void dart::TextNode::MakeCaseIndependent

(

bool

is_one_byte

)

Definition at line 2581 of file regexp.cc.

                                                   {
  intptr_t element_count = elms_->length();
  for (intptr_t i = 0; i < element_count; i++) {
    TextElement elm = elms_->At(i);
    if (elm.text_type() == TextElement::CHAR_CLASS) {
      RegExpCharacterClass* cc = elm.char_class();
      bool case_equivalents_already_added =
          cc->flags().NeedsUnicodeCaseEquivalents();
      if (cc->flags().IgnoreCase() && !case_equivalents_already_added) {
        // None of the standard character classes is different in the case
        // independent case and it slows us down if we don't know that.
        if (cc->is_standard()) continue;
        CharacterRange::AddCaseEquivalents(cc->ranges(), is_one_byte, Z);
      }
    }
  }
}

read_backward()

bool dart::TextNode::read_backward ( )

inline

Definition at line 687 of file regexp.h.

{ return read_backward_; }

---

The documentation for this class was generated from the following files:

• third_party/dart-lang/sdk/runtime/vm/regexp.h
• third_party/dart-lang/sdk/runtime/vm/regexp.cc