v8::internal::BoyerMooreLookahead Class Reference

#include <jsregexp.h>

Inheritance diagram for v8::internal::BoyerMooreLookahead:

Collaboration diagram for v8::internal::BoyerMooreLookahead:

Public Member Functions
	BoyerMooreLookahead (int length, RegExpCompiler *compiler, Zone *zone)
int	length ()
int	max_char ()
RegExpCompiler *	compiler ()
int	Count (int map_number)
BoyerMoorePositionInfo *	at (int i)
void	Set (int map_number, int character)
void	SetInterval (int map_number, const Interval &interval)
void	SetAll (int map_number)
void	SetRest (int from_map)
void	EmitSkipInstructions (RegExpMacroAssembler *masm)
Public Member Functions inherited from v8::internal::ZoneObject
	INLINE (void *operator new(size_t size, Zone *zone))
void	operator delete (void *, size_t)
void	operator delete (void *pointer, Zone *zone)

Private Member Functions
int	GetSkipTable (int min_lookahead, int max_lookahead, Handle< ByteArray > boolean_skip_table)
bool	FindWorthwhileInterval (int *from, int *to)
int	FindBestInterval (int max_number_of_chars, int old_biggest_points, int *from, int *to)

Private Attributes
int	length_
RegExpCompiler *	compiler_
int	max_char_
ZoneList< BoyerMoorePositionInfo * > *	bitmaps_

Detailed Description

Definition at line 1286 of file jsregexp.h.

Constructor & Destructor Documentation

BoyerMooreLookahead()

v8::internal::BoyerMooreLookahead::BoyerMooreLookahead	(	int	length,
		RegExpCompiler *	compiler,
		Zone *	zone
	)

Definition at line 3633 of file jsregexp.cc.

    : length_(length),
      compiler_(compiler) {
  if (compiler->one_byte()) {
    max_char_ = String::kMaxOneByteCharCode;
  } else {
    max_char_ = String::kMaxUtf16CodeUnit;
  }
  bitmaps_ = new(zone) ZoneList<BoyerMoorePositionInfo*>(length, zone);
  for (int i = 0; i < length; i++) {
    bitmaps_->Add(new(zone) BoyerMoorePositionInfo(zone), zone);
  }
}

References bitmaps_, compiler(), v8::internal::String::kMaxOneByteCharCode, v8::internal::String::kMaxUtf16CodeUnit, length(), max_char_, and v8::internal::RegExpCompiler::one_byte().

Here is the call graph for this function:

Member Function Documentation

at()

BoyerMoorePositionInfo* v8::internal::BoyerMooreLookahead::at ( int  i )

inline

Definition at line 1298 of file jsregexp.h.

{ return bitmaps_->at(i); }

References bitmaps_.

Referenced by v8::internal::AssertionNode::EmitBoundaryCheck().

Here is the caller graph for this function:

compiler()

RegExpCompiler* v8::internal::BoyerMooreLookahead::compiler ( )

inline

Definition at line 1292 of file jsregexp.h.

{ return compiler_; }

References compiler_.

Referenced by BoyerMooreLookahead(), and v8::internal::TextNode::FillInBMInfo().

Here is the caller graph for this function:

Count()

int v8::internal::BoyerMooreLookahead::Count ( int  map_number )

inline

Definition at line 1294 of file jsregexp.h.

                            {
    return bitmaps_->at(map_number)->map_count();
  }

References bitmaps_.

Referenced by FindBestInterval().

Here is the caller graph for this function:

EmitSkipInstructions()

void v8::internal::BoyerMooreLookahead::EmitSkipInstructions

(

RegExpMacroAssembler *

masm

)

Definition at line 3754 of file jsregexp.cc.

                                                                         {
  const int kSize = RegExpMacroAssembler::kTableSize;
 
  int min_lookahead = 0;
  int max_lookahead = 0;
 
  if (!FindWorthwhileInterval(&min_lookahead, &max_lookahead)) return;
 
  bool found_single_character = false;
  int single_character = 0;
  for (int i = max_lookahead; i >= min_lookahead; i--) {
    BoyerMoorePositionInfo* map = bitmaps_->at(i);
    if (map->map_count() > 1 ||
        (found_single_character && map->map_count() != 0)) {
      found_single_character = false;
      break;
    }
    for (int j = 0; j < kSize; j++) {
      if (map->at(j)) {
        found_single_character = true;
        single_character = j;
        break;
      }
    }
  }
 
  int lookahead_width = max_lookahead + 1 - min_lookahead;
 
  if (found_single_character && lookahead_width == 1 && max_lookahead < 3) {
    // The mask-compare can probably handle this better.
    return;
  }
 
  if (found_single_character) {
    Label cont, again;
    masm->Bind(&again);
    masm->LoadCurrentCharacter(max_lookahead, &cont, true);
    if (max_char_ > kSize) {
      masm->CheckCharacterAfterAnd(single_character,
                                   RegExpMacroAssembler::kTableMask,
                                   &cont);
    } else {
      masm->CheckCharacter(single_character, &cont);
    }
    masm->AdvanceCurrentPosition(lookahead_width);
    masm->GoTo(&again);
    masm->Bind(&cont);
    return;
  }
 
  Factory* factory = masm->zone()->isolate()->factory();
  Handle<ByteArray> boolean_skip_table = factory->NewByteArray(kSize, TENURED);
  int skip_distance = GetSkipTable(
      min_lookahead, max_lookahead, boolean_skip_table);
  DCHECK(skip_distance != 0);
 
  Label cont, again;
  masm->Bind(&again);
  masm->LoadCurrentCharacter(max_lookahead, &cont, true);
  masm->CheckBitInTable(boolean_skip_table, &cont);
  masm->AdvanceCurrentPosition(skip_distance);
  masm->GoTo(&again);
  masm->Bind(&cont);
}

References v8::internal::RegExpMacroAssembler::AdvanceCurrentPosition(), v8::internal::RegExpMacroAssembler::Bind(), bitmaps_, v8::internal::RegExpMacroAssembler::CheckBitInTable(), v8::internal::RegExpMacroAssembler::CheckCharacter(), v8::internal::RegExpMacroAssembler::CheckCharacterAfterAnd(), DCHECK, v8::internal::Isolate::factory(), FindWorthwhileInterval(), GetSkipTable(), v8::internal::RegExpMacroAssembler::GoTo(), v8::internal::Zone::isolate(), v8::internal::RegExpMacroAssembler::kTableMask, v8::internal::RegExpMacroAssembler::kTableSize, v8::internal::RegExpMacroAssembler::LoadCurrentCharacter(), map, max_char_, v8::internal::TENURED, and v8::internal::RegExpMacroAssembler::zone().

Referenced by v8::internal::ChoiceNode::EmitOptimizedUnanchoredSearch().

Here is the call graph for this function:

Here is the caller graph for this function:

FindBestInterval()

int v8::internal::BoyerMooreLookahead::FindBestInterval ( int  max_number_of_chars, int  old_biggest_points, int *  from, int *  to  )

private

Definition at line 3674 of file jsregexp.cc.

                                                                         {
  int biggest_points = old_biggest_points;
  static const int kSize = RegExpMacroAssembler::kTableSize;
  for (int i = 0; i < length_; ) {
    while (i < length_ && Count(i) > max_number_of_chars) i++;
    if (i == length_) break;
    int remembered_from = i;
    bool union_map[kSize];
    for (int j = 0; j < kSize; j++) union_map[j] = false;
    while (i < length_ && Count(i) <= max_number_of_chars) {
      BoyerMoorePositionInfo* map = bitmaps_->at(i);
      for (int j = 0; j < kSize; j++) union_map[j] |= map->at(j);
      i++;
    }
    int frequency = 0;
    for (int j = 0; j < kSize; j++) {
      if (union_map[j]) {
        // Add 1 to the frequency to give a small per-character boost for
        // the cases where our sampling is not good enough and many
        // characters have a frequency of zero.  This means the frequency
        // can theoretically be up to 2*kSize though we treat it mostly as
        // a fraction of kSize.
        frequency += compiler_->frequency_collator()->Frequency(j) + 1;
      }
    }
    // We use the probability of skipping times the distance we are skipping to
    // judge the effectiveness of this.  Actually we have a cut-off:  By
    // dividing by 2 we switch off the skipping if the probability of skipping
    // is less than 50%.  This is because the multibyte mask-and-compare
    // skipping in quickcheck is more likely to do well on this case.
    bool in_quickcheck_range =
        ((i - remembered_from < 4) ||
         (compiler_->one_byte() ? remembered_from <= 4 : remembered_from <= 2));
    // Called 'probability' but it is only a rough estimate and can actually
    // be outside the 0-kSize range.
    int probability = (in_quickcheck_range ? kSize / 2 : kSize) - frequency;
    int points = (i - remembered_from) * probability;
    if (points > biggest_points) {
      *from = remembered_from;
      *to = i - 1;
      biggest_points = points;
    }
  }
  return biggest_points;
}

References bitmaps_, compiler_, Count(), v8::internal::FrequencyCollator::Frequency(), v8::internal::RegExpCompiler::frequency_collator(), v8::internal::RegExpMacroAssembler::kTableSize, length_, map, v8::internal::RegExpCompiler::one_byte(), and to().

Referenced by FindWorthwhileInterval().

Here is the call graph for this function:

Here is the caller graph for this function:

FindWorthwhileInterval()

bool v8::internal::BoyerMooreLookahead::FindWorthwhileInterval ( int *  from, int *  to  )

private

Definition at line 3652 of file jsregexp.cc.

                                                                   {
  int biggest_points = 0;
  // If more than 32 characters out of 128 can occur it is unlikely that we can
  // be lucky enough to step forwards much of the time.
  const int kMaxMax = 32;
  for (int max_number_of_chars = 4;
       max_number_of_chars < kMaxMax;
       max_number_of_chars *= 2) {
    biggest_points =
        FindBestInterval(max_number_of_chars, biggest_points, from, to);
  }
  if (biggest_points == 0) return false;
  return true;
}

References FindBestInterval(), and to().

Referenced by EmitSkipInstructions().

Here is the call graph for this function:

Here is the caller graph for this function:

GetSkipTable()

int v8::internal::BoyerMooreLookahead::GetSkipTable ( int  min_lookahead, int  max_lookahead, Handle< ByteArray >  boolean_skip_table  )

private

Definition at line 3727 of file jsregexp.cc.

                                                                            {
  const int kSize = RegExpMacroAssembler::kTableSize;
 
  const int kSkipArrayEntry = 0;
  const int kDontSkipArrayEntry = 1;
 
  for (int i = 0; i < kSize; i++) {
    boolean_skip_table->set(i, kSkipArrayEntry);
  }
  int skip = max_lookahead + 1 - min_lookahead;
 
  for (int i = max_lookahead; i >= min_lookahead; i--) {
    BoyerMoorePositionInfo* map = bitmaps_->at(i);
    for (int j = 0; j < kSize; j++) {
      if (map->at(j)) {
        boolean_skip_table->set(j, kDontSkipArrayEntry);
      }
    }
  }
 
  return skip;
}

References bitmaps_, v8::internal::RegExpMacroAssembler::kTableSize, and map.

Referenced by EmitSkipInstructions().

Here is the caller graph for this function:

length()

int v8::internal::BoyerMooreLookahead::length ( )

inline

Definition at line 1290 of file jsregexp.h.

{ return length_; }

References length_.

Referenced by BoyerMooreLookahead(), and v8::internal::TextNode::FillInBMInfo().

Here is the caller graph for this function:

max_char()

int v8::internal::BoyerMooreLookahead::max_char ( )

inline

Definition at line 1291 of file jsregexp.h.

{ return max_char_; }

References max_char_.

Referenced by v8::internal::TextNode::FillInBMInfo().

Here is the caller graph for this function:

Set()

void v8::internal::BoyerMooreLookahead::Set ( int  map_number, int  character  )

inline

Definition at line 1300 of file jsregexp.h.

                                          {
    if (character > max_char_) return;
    BoyerMoorePositionInfo* info = bitmaps_->at(map_number);
    info->Set(character);
  }

References bitmaps_, max_char_, and v8::internal::BoyerMoorePositionInfo::Set().

Referenced by v8::internal::TextNode::FillInBMInfo().

Here is the call graph for this function:

Here is the caller graph for this function:

SetAll()

void v8::internal::BoyerMooreLookahead::SetAll ( int  map_number )

inline

Definition at line 1316 of file jsregexp.h.

                              {
    bitmaps_->at(map_number)->SetAll();
  }

References bitmaps_.

Referenced by v8::internal::TextNode::FillInBMInfo(), and SetRest().

Here is the caller graph for this function:

SetInterval()

void v8::internal::BoyerMooreLookahead::SetInterval ( int  map_number, const Interval &  interval  )

inline

Definition at line 1306 of file jsregexp.h.

                                                             {
    if (interval.from() > max_char_) return;
    BoyerMoorePositionInfo* info = bitmaps_->at(map_number);
    if (interval.to() > max_char_) {
      info->SetInterval(Interval(interval.from(), max_char_));
    } else {
      info->SetInterval(interval);
    }
  }

References bitmaps_, v8::internal::Interval::from(), max_char_, v8::internal::BoyerMoorePositionInfo::SetInterval(), and v8::internal::Interval::to().

Referenced by v8::internal::TextNode::FillInBMInfo().

Here is the call graph for this function:

Here is the caller graph for this function:

SetRest()

void v8::internal::BoyerMooreLookahead::SetRest ( int  from_map )

inline

Definition at line 1320 of file jsregexp.h.

                             {
    for (int i = from_map; i < length_; i++) SetAll(i);
  }

References length_, and SetAll().

Referenced by v8::internal::ActionNode::FillInBMInfo(), v8::internal::BackReferenceNode::FillInBMInfo(), v8::internal::ChoiceNode::FillInBMInfo(), and v8::internal::LoopChoiceNode::FillInBMInfo().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

bitmaps_

ZoneList<BoyerMoorePositionInfo*>* v8::internal::BoyerMooreLookahead::bitmaps_

private

Definition at line 1334 of file jsregexp.h.

Referenced by at(), BoyerMooreLookahead(), Count(), EmitSkipInstructions(), FindBestInterval(), GetSkipTable(), Set(), SetAll(), and SetInterval().

compiler_

RegExpCompiler* v8::internal::BoyerMooreLookahead::compiler_

private

Definition at line 1331 of file jsregexp.h.

Referenced by compiler(), and FindBestInterval().

length_

int v8::internal::BoyerMooreLookahead::length_

private

Definition at line 1330 of file jsregexp.h.

Referenced by FindBestInterval(), length(), and SetRest().

max_char_

int v8::internal::BoyerMooreLookahead::max_char_

private

Definition at line 1333 of file jsregexp.h.

Referenced by BoyerMooreLookahead(), EmitSkipInstructions(), max_char(), Set(), and SetInterval().

---

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

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