v8::internal::CharacterRange Class Reference

#include <jsregexp.h>

Collaboration diagram for v8::internal::CharacterRange:

Public Member Functions
	CharacterRange ()
	CharacterRange (void *null)
	CharacterRange (uc16 from, uc16 to)
bool	Contains (uc16 i)
uc16	from () const
void	set_from (uc16 value)
uc16	to () const
void	set_to (uc16 value)
bool	is_valid ()
bool	IsEverything (uc16 max)
bool	IsSingleton ()
void	AddCaseEquivalents (ZoneList< CharacterRange > *ranges, bool is_one_byte, Zone *zone)

Static Public Member Functions
static void	AddClassEscape (uc16 type, ZoneList< CharacterRange > *ranges, Zone *zone)
static Vector< const int >	GetWordBounds ()
static CharacterRange	Singleton (uc16 value)
static CharacterRange	Range (uc16 from, uc16 to)
static CharacterRange	Everything ()
static void	Split (ZoneList< CharacterRange > *base, Vector< const int > overlay, ZoneList< CharacterRange > **included, ZoneList< CharacterRange > **excluded, Zone *zone)
static bool	IsCanonical (ZoneList< CharacterRange > *ranges)
static void	Canonicalize (ZoneList< CharacterRange > *ranges)
static void	Negate (ZoneList< CharacterRange > *src, ZoneList< CharacterRange > *dst, Zone *zone)

Static Public Attributes
static const int	kStartMarker = (1 << 24)
static const int	kPayloadMask = (1 << 24) - 1

Private Attributes
uc16	from_
uc16	to_

Detailed Description

Definition at line 239 of file jsregexp.h.

Constructor & Destructor Documentation

CharacterRange() [1/3]

v8::internal::CharacterRange::CharacterRange ( )

inline

Definition at line 241 of file jsregexp.h.

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

Referenced by AddCaseEquivalents(), Everything(), Negate(), Range(), Singleton(), and Split().

Here is the caller graph for this function:

CharacterRange() [2/3]

v8::internal::CharacterRange::CharacterRange ( void *  null )

inline

Definition at line 243 of file jsregexp.h.

{ DCHECK_EQ(NULL, null); }  //NOLINT

References DCHECK_EQ, and NULL.

CharacterRange() [3/3]

v8::internal::CharacterRange::CharacterRange ( uc16  from, uc16  to  )

inline

Definition at line 244 of file jsregexp.h.

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

Member Function Documentation

AddCaseEquivalents()

void v8::internal::CharacterRange::AddCaseEquivalents	(	ZoneList< CharacterRange > *	ranges,
		bool	is_one_byte,
		Zone *	zone
	)

Definition at line 5335 of file jsregexp.cc.

                                                                      {
  Isolate* isolate = zone->isolate();
  uc16 bottom = from();
  uc16 top = to();
  if (is_one_byte && !RangeContainsLatin1Equivalents(*this)) {
    if (bottom > String::kMaxOneByteCharCode) return;
    if (top > String::kMaxOneByteCharCode) top = String::kMaxOneByteCharCode;
  }
  unibrow::uchar chars[unibrow::Ecma262UnCanonicalize::kMaxWidth];
  if (top == bottom) {
    // If this is a singleton we just expand the one character.
    int length = isolate->jsregexp_uncanonicalize()->get(bottom, '\0', chars);
    for (int i = 0; i < length; i++) {
      uc32 chr = chars[i];
      if (chr != bottom) {
        ranges->Add(CharacterRange::Singleton(chars[i]), zone);
      }
    }
  } 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").
    unibrow::uchar range[unibrow::Ecma262UnCanonicalize::kMaxWidth];
    int pos = bottom;
    while (pos <= top) {
      int length = isolate->jsregexp_canonrange()->get(pos, '\0', range);
      uc16 block_end;
      if (length == 0) {
        block_end = pos;
      } else {
        DCHECK_EQ(1, length);
        block_end = range[0];
      }
      int end = (block_end > top) ? top : block_end;
      length = isolate->jsregexp_uncanonicalize()->get(block_end, '\0', range);
      for (int i = 0; i < length; i++) {
        uc32 c = range[i];
        uc16 range_from = c - (block_end - pos);
        uc16 range_to = c - (block_end - end);
        if (!(bottom <= range_from && range_to <= top)) {
          ranges->Add(CharacterRange(range_from, range_to), zone);
        }
      }
      pos = end + 1;
    }
  }
}

References v8::internal::List< T, AllocationPolicy >::Add(), CharacterRange(), DCHECK_EQ, from(), unibrow::Mapping< T, size >::get(), v8::internal::Zone::isolate(), v8::internal::Isolate::jsregexp_canonrange(), v8::internal::Isolate::jsregexp_uncanonicalize(), v8::internal::String::kMaxOneByteCharCode, unibrow::Ecma262UnCanonicalize::kMaxWidth, v8::internal::RangeContainsLatin1Equivalents(), Singleton(), and to().

Here is the call graph for this function:

AddClassEscape()

void v8::internal::CharacterRange::AddClassEscape ( uc16  type, ZoneList< CharacterRange > *  ranges, Zone *  zone  )

static

Definition at line 5233 of file jsregexp.cc.

                                                {
  switch (type) {
    case 's':
      AddClass(kSpaceRanges, kSpaceRangeCount, ranges, zone);
      break;
    case 'S':
      AddClassNegated(kSpaceRanges, kSpaceRangeCount, ranges, zone);
      break;
    case 'w':
      AddClass(kWordRanges, kWordRangeCount, ranges, zone);
      break;
    case 'W':
      AddClassNegated(kWordRanges, kWordRangeCount, ranges, zone);
      break;
    case 'd':
      AddClass(kDigitRanges, kDigitRangeCount, ranges, zone);
      break;
    case 'D':
      AddClassNegated(kDigitRanges, kDigitRangeCount, ranges, zone);
      break;
    case '.':
      AddClassNegated(kLineTerminatorRanges,
                      kLineTerminatorRangeCount,
                      ranges,
                      zone);
      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(), zone);
      break;
    // This is the set of characters matched by the $ and ^ symbols
    // in multiline mode.
    case 'n':
      AddClass(kLineTerminatorRanges,
               kLineTerminatorRangeCount,
               ranges,
               zone);
      break;
    default:
      UNREACHABLE();
  }
}

References v8::internal::List< T, AllocationPolicy >::Add(), v8::internal::AddClass(), v8::internal::AddClassNegated(), Everything(), v8::internal::kDigitRangeCount, v8::internal::kDigitRanges, v8::internal::kLineTerminatorRangeCount, v8::internal::kLineTerminatorRanges, v8::internal::kSpaceRangeCount, v8::internal::kSpaceRanges, v8::internal::kWordRangeCount, v8::internal::kWordRanges, and UNREACHABLE.

Referenced by v8::internal::AddRangeOrEscape().

Here is the call graph for this function:

Here is the caller graph for this function:

Canonicalize()

void v8::internal::CharacterRange::Canonicalize ( ZoneList< CharacterRange > *  ranges )

static

Definition at line 5508 of file jsregexp.cc.

                                                                            {
  if (character_ranges->length() <= 1) return;
  // Check whether ranges are already canonical (increasing, non-overlapping,
  // non-adjacent).
  int n = character_ranges->length();
  int max = character_ranges->at(0).to();
  int 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.
  int read = i;  // Range to insert.
  int 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->Rewind(num_canonical);
 
  DCHECK(CharacterRange::IsCanonical(character_ranges));
}

References v8::internal::List< T, AllocationPolicy >::at(), DCHECK, from(), v8::internal::InsertRangeInCanonicalList(), IsCanonical(), and to().

Referenced by v8::internal::EmitCharClass(), v8::internal::TextNode::FilterOneByte(), and v8::internal::TextNode::GetSuccessorOfOmnivorousTextNode().

Here is the call graph for this function:

Here is the caller graph for this function:

Contains()

bool v8::internal::CharacterRange::Contains ( uc16  i )

inline

Definition at line 258 of file jsregexp.h.

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

References from_, and to_.

Referenced by v8::internal::RangeContainsLatin1Equivalents().

Here is the caller graph for this function:

Everything()

static CharacterRange v8::internal::CharacterRange::Everything ( )

inlinestatic

Definition at line 255 of file jsregexp.h.

                                            {
    return CharacterRange(0, 0xFFFF);
  }

References CharacterRange().

Referenced by AddClassEscape().

Here is the call graph for this function:

Here is the caller graph for this function:

from()

uc16 v8::internal::CharacterRange::from ( ) const

inline

Definition at line 259 of file jsregexp.h.

{ return from_; }

References from_.

Referenced by AddCaseEquivalents(), v8::internal::DispatchTableConstructor::AddInverse(), v8::internal::DispatchTable::AddRange(), Canonicalize(), v8::internal::CompareInverseRanges(), v8::internal::CompareRangeByFrom(), v8::internal::CompareRanges(), v8::internal::EmitCharClass(), v8::internal::TextNode::FillInBMInfo(), v8::internal::TextNode::GetQuickCheckDetails(), v8::internal::InsertRangeInCanonicalList(), IsCanonical(), Negate(), and Range().

Here is the caller graph for this function:

GetWordBounds()

Vector< const int > v8::internal::CharacterRange::GetWordBounds ( )

static

Definition at line 5281 of file jsregexp.cc.

                                                {
  return Vector<const int>(kWordRanges, kWordRangeCount - 1);
}

References v8::internal::kWordRangeCount, and v8::internal::kWordRanges.

is_valid()

bool v8::internal::CharacterRange::is_valid ( )

inline

Definition at line 263 of file jsregexp.h.

{ return from_ <= to_; }

References from_, and to_.

Referenced by v8::internal::DispatchTable::AddRange().

Here is the caller graph for this function:

IsCanonical()

bool v8::internal::CharacterRange::IsCanonical ( ZoneList< CharacterRange > *  ranges )

static

Definition at line 5400 of file jsregexp.cc.

                                                                 {
  DCHECK_NOT_NULL(ranges);
  int n = ranges->length();
  if (n <= 1) return true;
  int max = ranges->at(0).to();
  for (int 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;
}

References v8::internal::List< T, AllocationPolicy >::at(), DCHECK_NOT_NULL, from(), and to().

Referenced by Canonicalize(), v8::internal::EmitCharClass(), v8::internal::TextNode::FilterOneByte(), v8::internal::TextNode::GetSuccessorOfOmnivorousTextNode(), and Negate().

Here is the call graph for this function:

Here is the caller graph for this function:

IsEverything()

bool v8::internal::CharacterRange::IsEverything ( uc16  max )

inline

Definition at line 264 of file jsregexp.h.

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

References from_, and to_.

IsSingleton()

bool v8::internal::CharacterRange::IsSingleton ( )

inline

Definition at line 265 of file jsregexp.h.

{ return (from_ == to_); }

References from_, and to_.

Negate()

void v8::internal::CharacterRange::Negate ( ZoneList< CharacterRange > *  src, ZoneList< CharacterRange > *  dst, Zone *  zone  )

static

Definition at line 5545 of file jsregexp.cc.

                                        {
  DCHECK(CharacterRange::IsCanonical(ranges));
  DCHECK_EQ(0, negated_ranges->length());
  int range_count = ranges->length();
  uc16 from = 0;
  int 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), zone);
    from = range.to();
    i++;
  }
  if (from < String::kMaxUtf16CodeUnit) {
    negated_ranges->Add(CharacterRange(from + 1, String::kMaxUtf16CodeUnit),
                        zone);
  }
}

References v8::internal::List< T, AllocationPolicy >::Add(), v8::internal::List< T, AllocationPolicy >::at(), CharacterRange(), DCHECK, DCHECK_EQ, from(), IsCanonical(), v8::internal::String::kMaxUtf16CodeUnit, and to().

Here is the call graph for this function:

Range()

static CharacterRange v8::internal::CharacterRange::Range ( uc16  from, uc16  to  )

inlinestatic

Definition at line 251 of file jsregexp.h.

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

References CharacterRange(), DCHECK, from(), and to().

Here is the call graph for this function:

set_from()

void v8::internal::CharacterRange::set_from ( uc16  value )

inline

Definition at line 260 of file jsregexp.h.

{ from_ = value; }

References from_.

Referenced by v8::internal::DispatchTable::AddRange().

Here is the caller graph for this function:

set_to()

void v8::internal::CharacterRange::set_to ( uc16  value )

inline

Definition at line 262 of file jsregexp.h.

{ to_ = value; }

References to_.

Singleton()

static CharacterRange v8::internal::CharacterRange::Singleton ( uc16  value )

inlinestatic

Definition at line 248 of file jsregexp.h.

                                                     {
    return CharacterRange(value, value);
  }

References CharacterRange().

Referenced by AddCaseEquivalents().

Here is the call graph for this function:

Here is the caller graph for this function:

Split()

void v8::internal::CharacterRange::Split ( ZoneList< CharacterRange > *  base, Vector< const int >  overlay, ZoneList< CharacterRange > **  included, ZoneList< CharacterRange > **  excluded, Zone *  zone  )

static

Definition at line 5316 of file jsregexp.cc.

                                       {
  DCHECK_EQ(NULL, *included);
  DCHECK_EQ(NULL, *excluded);
  DispatchTable table(zone);
  for (int i = 0; i < base->length(); i++)
    table.AddRange(base->at(i), CharacterRangeSplitter::kInBase, zone);
  for (int i = 0; i < overlay.length(); i += 2) {
    table.AddRange(CharacterRange(overlay[i], overlay[i + 1] - 1),
                   CharacterRangeSplitter::kInOverlay, zone);
  }
  CharacterRangeSplitter callback(included, excluded, zone);
  table.ForEach(&callback);
}

References v8::internal::DispatchTable::AddRange(), v8::internal::List< T, AllocationPolicy >::at(), CharacterRange(), DCHECK_EQ, v8::internal::DispatchTable::ForEach(), v8::internal::CharacterRangeSplitter::kInBase, v8::internal::CharacterRangeSplitter::kInOverlay, v8::internal::Vector< T >::length(), and NULL.

Here is the call graph for this function:

to()

uc16 v8::internal::CharacterRange::to ( ) const

inline

Definition at line 261 of file jsregexp.h.

{ return to_; }

References to_.

Referenced by AddCaseEquivalents(), v8::internal::DispatchTableConstructor::AddInverse(), v8::internal::DispatchTable::AddRange(), Canonicalize(), v8::internal::CompareInverseRanges(), v8::internal::CompareRanges(), v8::internal::EmitCharClass(), v8::internal::TextNode::FillInBMInfo(), v8::internal::TextNode::GetQuickCheckDetails(), v8::internal::InsertRangeInCanonicalList(), IsCanonical(), Negate(), and Range().

Here is the caller graph for this function:

Member Data Documentation

from_

uc16 v8::internal::CharacterRange::from_

private

Definition at line 289 of file jsregexp.h.

Referenced by Contains(), from(), is_valid(), IsEverything(), IsSingleton(), and set_from().

kPayloadMask

const int v8::internal::CharacterRange::kPayloadMask = (1 << 24) - 1

static

Definition at line 286 of file jsregexp.h.

kStartMarker

const int v8::internal::CharacterRange::kStartMarker = (1 << 24)

static

Definition at line 285 of file jsregexp.h.

to_

uc16 v8::internal::CharacterRange::to_

private

Definition at line 290 of file jsregexp.h.

Referenced by Contains(), is_valid(), IsEverything(), IsSingleton(), set_to(), and to().

---

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

• /mnt/V8SourceCode/src/jsregexp.h
• /mnt/V8SourceCode/src/jsregexp.cc