dart::CharacterRange Class Reference

#include <regexp.h>

Public Member Functions
	CharacterRange ()
	CharacterRange (int32_t from, int32_t to)
bool	Contains (int32_t i) const
int32_t	from () const
void	set_from (int32_t value)
int32_t	to () const
void	set_to (int32_t value)
bool	is_valid () const
bool	IsEverything (int32_t max) const
bool	IsSingleton () const

Static Public Member Functions
static void	AddClassEscape (uint16_t type, ZoneGrowableArray< CharacterRange > *ranges)
static void	AddClassEscape (uint16_t type, ZoneGrowableArray< CharacterRange > *ranges, bool add_unicode_case_equivalents)
static GrowableArray< const intptr_t >	GetWordBounds ()
static CharacterRange	Singleton (int32_t value)
static CharacterRange	Range (int32_t from, int32_t to)
static CharacterRange	Everything ()
static ZoneGrowableArray< CharacterRange > *	List (Zone *zone, CharacterRange range)
static void	AddCaseEquivalents (ZoneGrowableArray< CharacterRange > *ranges, bool is_one_byte, Zone *zone)
static void	Split (ZoneGrowableArray< CharacterRange > *base, GrowableArray< const intptr_t > overlay, ZoneGrowableArray< CharacterRange > **included, ZoneGrowableArray< CharacterRange > **excluded, Zone *zone)
static bool	IsCanonical (ZoneGrowableArray< CharacterRange > *ranges)
static void	Canonicalize (ZoneGrowableArray< CharacterRange > *ranges)
static void	Negate (ZoneGrowableArray< CharacterRange > *src, ZoneGrowableArray< CharacterRange > *dst)

Static Public Attributes
static constexpr intptr_t	kStartMarker = (1 << 24)
static constexpr intptr_t	kPayloadMask = (1 << 24) - 1

Detailed Description

Definition at line 25 of file regexp.h.

Constructor & Destructor Documentation

CharacterRange() [1/2]

dart::CharacterRange::CharacterRange ( )

inline

Definition at line 27 of file regexp.h.

: from_(0), to_(0) {}

CharacterRange() [2/2]

dart::CharacterRange::CharacterRange ( int32_t  from, int32_t  to  )

inline

Definition at line 28 of file regexp.h.

: from_(from), to_(to) {}

Member Function Documentation

AddCaseEquivalents()

void dart::CharacterRange::AddCaseEquivalents ( ZoneGrowableArray< CharacterRange > *  ranges, bool  is_one_byte, Zone *  zone  )

static

Definition at line 4691 of file regexp.cc.

                {
  CharacterRange::Canonicalize(ranges);
  int range_count = ranges->length();
  for (intptr_t i = 0; i < range_count; i++) {
    CharacterRange range = ranges->At(i);
    int32_t bottom = range.from();
    if (bottom > Utf16::kMaxCodeUnit) continue;
    int32_t top = Utils::Minimum(range.to(), Utf16::kMaxCodeUnit);
    // Nothing to be done for surrogates
    if (bottom >= Utf16::kLeadSurrogateStart &&
        top <= Utf16::kTrailSurrogateEnd) {
      continue;
    }
    if (is_one_byte && !RangeContainsLatin1Equivalents(range)) {
      if (bottom > Symbols::kMaxOneCharCodeSymbol) continue;
      if (top > Symbols::kMaxOneCharCodeSymbol) {
        top = Symbols::kMaxOneCharCodeSymbol;
      }
    }
 
    unibrow::Mapping<unibrow::Ecma262UnCanonicalize> jsregexp_uncanonicalize;
    unibrow::Mapping<unibrow::CanonicalizationRange> jsregexp_canonrange;
    int32_t chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
    if (top == bottom) {
      // If this is a singleton we just expand the one character.
      intptr_t length = jsregexp_uncanonicalize.get(bottom, '\0', chars);
      for (intptr_t i = 0; i < length; i++) {
        int32_t chr = chars[i];
        if (chr != bottom) {
          ranges->Add(CharacterRange::Singleton(chars[i]));
        }
      }
    } else {
      // If this is a range we expand the characters block by block,
      // expanding contiguous subranges (blocks) one at a time.
      // The approach is as follows.  For a given start character we
      // look up the remainder of the block that contains it (represented
      // by the end point), for instance we find 'z' if the character
      // is 'c'.  A block is characterized by the property
      // that all characters uncanonicalize in the same way, except that
      // each entry in the result is incremented by the distance from the first
      // element.  So a-z is a block because 'a' uncanonicalizes to ['a', 'A']
      // and the k'th letter uncanonicalizes to ['a' + k, 'A' + k].
      // Once we've found the end point we look up its uncanonicalization
      // and produce a range for each element.  For instance for [c-f]
      // we look up ['z', 'Z'] and produce [c-f] and [C-F].  We then only
      // add a range if it is not already contained in the input, so [c-f]
      // will be skipped but [C-F] will be added.  If this range is not
      // completely contained in a block we do this for all the blocks
      // covered by the range (handling characters that is not in a block
      // as a "singleton block").
      int32_t range[unibrow::Ecma262UnCanonicalize::kMaxWidth];
      intptr_t pos = bottom;
      while (pos <= top) {
        intptr_t length = jsregexp_canonrange.get(pos, '\0', range);
        int32_t block_end;
        if (length == 0) {
          block_end = pos;
        } else {
          ASSERT(length == 1);
          block_end = range[0];
        }
        intptr_t end = (block_end > top) ? top : block_end;
        length = jsregexp_uncanonicalize.get(block_end, '\0', range);
        for (intptr_t i = 0; i < length; i++) {
          int32_t c = range[i];
          int32_t range_from = c - (block_end - pos);
          int32_t range_to = c - (block_end - end);
          if (!(bottom <= range_from && range_to <= top)) {
            ranges->Add(CharacterRange(range_from, range_to));
          }
        }
        pos = end + 1;
      }
    }
  }
}

AddClassEscape() [1/2]

void dart::CharacterRange::AddClassEscape ( uint16_t  type, ZoneGrowableArray< CharacterRange > *  ranges  )

static

Definition at line 4651 of file regexp.cc.

                                                                               {
  switch (type) {
    case 's':
      AddClass(kSpaceRanges, kSpaceRangeCount, ranges);
      break;
    case 'S':
      AddClassNegated(kSpaceRanges, kSpaceRangeCount, ranges);
      break;
    case 'w':
      AddClass(kWordRanges, kWordRangeCount, ranges);
      break;
    case 'W':
      AddClassNegated(kWordRanges, kWordRangeCount, ranges);
      break;
    case 'd':
      AddClass(kDigitRanges, kDigitRangeCount, ranges);
      break;
    case 'D':
      AddClassNegated(kDigitRanges, kDigitRangeCount, ranges);
      break;
    case '.':
      AddClassNegated(kLineTerminatorRanges, kLineTerminatorRangeCount, ranges);
      break;
    // This is not a character range as defined by the spec but a
    // convenient shorthand for a character class that matches any
    // character.
    case '*':
      ranges->Add(CharacterRange::Everything());
      break;
    // This is the set of characters matched by the $ and ^ symbols
    // in multiline mode.
    case 'n':
      AddClass(kLineTerminatorRanges, kLineTerminatorRangeCount, ranges);
      break;
    default:
      UNREACHABLE();
  }
}

AddClassEscape() [2/2]

void dart::CharacterRange::AddClassEscape ( uint16_t  type, ZoneGrowableArray< CharacterRange > *  ranges, bool  add_unicode_case_equivalents  )

static

Definition at line 4628 of file regexp.cc.

                                                                       {
  if (add_unicode_case_equivalents && (type == 'w' || type == 'W')) {
    // See #sec-runtime-semantics-wordcharacters-abstract-operation
    // In case of unicode and ignore_case, we need to create the closure over
    // case equivalent characters before negating.
    ZoneGrowableArray<CharacterRange>* new_ranges =
        new ZoneGrowableArray<CharacterRange>(2);
    AddClass(kWordRanges, kWordRangeCount, new_ranges);
    AddUnicodeCaseEquivalents(new_ranges);
    if (type == 'W') {
      ZoneGrowableArray<CharacterRange>* negated =
          new ZoneGrowableArray<CharacterRange>(2);
      CharacterRange::Negate(new_ranges, negated);
      new_ranges = negated;
    }
    ranges->AddArray(*new_ranges);
    return;
  }
  AddClassEscape(type, ranges);
}

Canonicalize()

void dart::CharacterRange::Canonicalize ( ZoneGrowableArray< CharacterRange > *  ranges )

static

Definition at line 4876 of file regexp.cc.

                                                         {
  if (character_ranges->length() <= 1) return;
  // Check whether ranges are already canonical (increasing, non-overlapping,
  // non-adjacent).
  intptr_t n = character_ranges->length();
  intptr_t max = character_ranges->At(0).to();
  intptr_t i = 1;
  while (i < n) {
    CharacterRange current = character_ranges->At(i);
    if (current.from() <= max + 1) {
      break;
    }
    max = current.to();
    i++;
  }
  // Canonical until the i'th range. If that's all of them, we are done.
  if (i == n) return;
 
  // The ranges at index i and forward are not canonicalized. Make them so by
  // doing the equivalent of insertion sort (inserting each into the previous
  // list, in order).
  // Notice that inserting a range can reduce the number of ranges in the
  // result due to combining of adjacent and overlapping ranges.
  intptr_t read = i;           // Range to insert.
  intptr_t num_canonical = i;  // Length of canonicalized part of list.
  do {
    num_canonical = InsertRangeInCanonicalList(character_ranges, num_canonical,
                                               character_ranges->At(read));
    read++;
  } while (read < n);
  character_ranges->TruncateTo(num_canonical);
 
  ASSERT(CharacterRange::IsCanonical(character_ranges));
}

Contains()

bool dart::CharacterRange::Contains ( int32_t  i ) const

inline

Definition at line 53 of file regexp.h.

{ return from_ <= i && i <= to_; }

Everything()

static CharacterRange dart::CharacterRange::Everything ( )

inlinestatic

Definition at line 44 of file regexp.h.

                                            {
    return CharacterRange(0, Utf::kMaxCodePoint);
  }

from()

int32_t dart::CharacterRange::from ( ) const

inline

Definition at line 54 of file regexp.h.

{ return from_; }

GetWordBounds()

static GrowableArray< const intptr_t > dart::CharacterRange::GetWordBounds ( )

static

is_valid()

bool dart::CharacterRange::is_valid ( ) const

inline

Definition at line 58 of file regexp.h.

{ return from_ <= to_; }

IsCanonical()

bool dart::CharacterRange::IsCanonical ( ZoneGrowableArray< CharacterRange > *  ranges )

static

Definition at line 4772 of file regexp.cc.

                                                                          {
  ASSERT(ranges != nullptr);
  intptr_t n = ranges->length();
  if (n <= 1) return true;
  intptr_t max = ranges->At(0).to();
  for (intptr_t i = 1; i < n; i++) {
    CharacterRange next_range = ranges->At(i);
    if (next_range.from() <= max + 1) return false;
    max = next_range.to();
  }
  return true;
}

IsEverything()

bool dart::CharacterRange::IsEverything ( int32_t  max ) const

inline

Definition at line 59 of file regexp.h.

{ return from_ == 0 && to_ >= max; }

IsSingleton()

bool dart::CharacterRange::IsSingleton ( ) const

inline

Definition at line 60 of file regexp.h.

{ return (from_ == to_); }

List()

static ZoneGrowableArray< CharacterRange > * dart::CharacterRange::List ( Zone *  zone, CharacterRange  range  )

inlinestatic

Definition at line 47 of file regexp.h.

                                                                              {
    auto list = new (zone) ZoneGrowableArray<CharacterRange>(1);
    list->Add(range);
    return list;
  }

Negate()

void dart::CharacterRange::Negate ( ZoneGrowableArray< CharacterRange > *  src, ZoneGrowableArray< CharacterRange > *  dst  )

static

Definition at line 4912 of file regexp.cc.

                                                                               {
  ASSERT(CharacterRange::IsCanonical(ranges));
  ASSERT(negated_ranges->length() == 0);
  intptr_t range_count = ranges->length();
  uint32_t from = 0;
  intptr_t i = 0;
  if (range_count > 0 && ranges->At(0).from() == 0) {
    from = ranges->At(0).to();
    i = 1;
  }
  while (i < range_count) {
    CharacterRange range = ranges->At(i);
    negated_ranges->Add(CharacterRange(from + 1, range.from() - 1));
    from = range.to();
    i++;
  }
  if (from < Utf::kMaxCodePoint) {
    negated_ranges->Add(CharacterRange(from + 1, Utf::kMaxCodePoint));
  }
}

Range()

static CharacterRange dart::CharacterRange::Range ( int32_t  from, int32_t  to  )

inlinestatic

Definition at line 40 of file regexp.h.

                                                               {
    ASSERT(from <= to);
    return CharacterRange(from, to);
  }

set_from()

void dart::CharacterRange::set_from ( int32_t  value )

inline

Definition at line 55 of file regexp.h.

{ from_ = value; }

set_to()

void dart::CharacterRange::set_to ( int32_t  value )

inline

Definition at line 57 of file regexp.h.

{ to_ = value; }

Singleton()

static CharacterRange dart::CharacterRange::Singleton ( int32_t  value )

inlinestatic

Definition at line 37 of file regexp.h.

                                                        {
    return CharacterRange(value, value);
  }

Split()

static void dart::CharacterRange::Split ( ZoneGrowableArray< CharacterRange > *  base, GrowableArray< const intptr_t >  overlay, ZoneGrowableArray< CharacterRange > **  included, ZoneGrowableArray< CharacterRange > **  excluded, Zone *  zone  )

static

to()

int32_t dart::CharacterRange::to ( ) const

inline

Definition at line 56 of file regexp.h.

{ return to_; }

Member Data Documentation

kPayloadMask

constexpr intptr_t dart::CharacterRange::kPayloadMask = (1 << 24) - 1

staticconstexpr

Definition at line 81 of file regexp.h.

kStartMarker

constexpr intptr_t dart::CharacterRange::kStartMarker = (1 << 24)

staticconstexpr

Definition at line 80 of file regexp.h.

---

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