michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* vim:set ts=2 sw=2 sts=2 et cindent: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include <stdlib.h>
michael@0: #include "nsScannerString.h"
michael@0: 
michael@0: 
michael@0:   /**
michael@0:    * nsScannerBufferList
michael@0:    */
michael@0: 
michael@0: #define MAX_CAPACITY ((UINT32_MAX / sizeof(char16_t)) - \
michael@0:                       (sizeof(Buffer) + sizeof(char16_t)))
michael@0: 
michael@0: nsScannerBufferList::Buffer*
michael@0: nsScannerBufferList::AllocBufferFromString( const nsAString& aString )
michael@0:   {
michael@0:     uint32_t len = aString.Length();
michael@0:     Buffer* buf = AllocBuffer(len);
michael@0: 
michael@0:     if (buf)
michael@0:       {
michael@0:         nsAString::const_iterator source;
michael@0:         aString.BeginReading(source);
michael@0:         nsCharTraits<char16_t>::copy(buf->DataStart(), source.get(), len);
michael@0:       }
michael@0:     return buf;
michael@0:   }
michael@0: 
michael@0: nsScannerBufferList::Buffer*
michael@0: nsScannerBufferList::AllocBuffer( uint32_t capacity )
michael@0:   {
michael@0:     if (capacity > MAX_CAPACITY)
michael@0:       return nullptr;
michael@0: 
michael@0:     void* ptr = malloc(sizeof(Buffer) + (capacity + 1) * sizeof(char16_t));
michael@0:     if (!ptr)
michael@0:       return nullptr;
michael@0: 
michael@0:     Buffer* buf = new (ptr) Buffer();
michael@0: 
michael@0:     buf->mUsageCount = 0;
michael@0:     buf->mDataEnd = buf->DataStart() + capacity;
michael@0: 
michael@0:     // XXX null terminate.  this shouldn't be required, but we do it because
michael@0:     // nsScanner erroneously thinks it can dereference DataEnd :-(
michael@0:     *buf->mDataEnd = char16_t(0);
michael@0:     return buf;
michael@0:   }
michael@0: 
michael@0: void
michael@0: nsScannerBufferList::ReleaseAll()
michael@0:   {
michael@0:     while (!mBuffers.isEmpty())
michael@0:       {
michael@0:         Buffer* node = mBuffers.popFirst();
michael@0:         //printf(">>> freeing buffer @%p\n", node);
michael@0:         free(node);
michael@0:       }
michael@0:   }
michael@0: 
michael@0: void
michael@0: nsScannerBufferList::SplitBuffer( const Position& pos )
michael@0:   {
michael@0:     // splitting to the right keeps the work string and any extant token
michael@0:     // pointing to and holding a reference count on the same buffer.
michael@0: 
michael@0:     Buffer* bufferToSplit = pos.mBuffer;
michael@0:     NS_ASSERTION(bufferToSplit, "null pointer");
michael@0: 
michael@0:     uint32_t splitOffset = pos.mPosition - bufferToSplit->DataStart();
michael@0:     NS_ASSERTION(pos.mPosition >= bufferToSplit->DataStart() &&
michael@0:                  splitOffset <= bufferToSplit->DataLength(),
michael@0:                  "split offset is outside buffer");
michael@0:     
michael@0:     uint32_t len = bufferToSplit->DataLength() - splitOffset;
michael@0:     Buffer* new_buffer = AllocBuffer(len);
michael@0:     if (new_buffer)
michael@0:       {
michael@0:         nsCharTraits<char16_t>::copy(new_buffer->DataStart(),
michael@0:                                       bufferToSplit->DataStart() + splitOffset,
michael@0:                                       len);
michael@0:         InsertAfter(new_buffer, bufferToSplit);
michael@0:         bufferToSplit->SetDataLength(splitOffset);
michael@0:       }
michael@0:   }
michael@0: 
michael@0: void
michael@0: nsScannerBufferList::DiscardUnreferencedPrefix( Buffer* aBuf )
michael@0:   {
michael@0:     if (aBuf == Head())
michael@0:       {
michael@0:         while (!mBuffers.isEmpty() && !Head()->IsInUse())
michael@0:           {
michael@0:             Buffer* buffer = Head();
michael@0:             buffer->remove();
michael@0:             free(buffer);
michael@0:           }
michael@0:       }
michael@0:   }
michael@0: 
michael@0: size_t
michael@0: nsScannerBufferList::Position::Distance( const Position& aStart, const Position& aEnd )
michael@0:   {
michael@0:     size_t result = 0;
michael@0:     if (aStart.mBuffer == aEnd.mBuffer)
michael@0:       {
michael@0:         result = aEnd.mPosition - aStart.mPosition;
michael@0:       }
michael@0:     else
michael@0:       {
michael@0:         result = aStart.mBuffer->DataEnd() - aStart.mPosition;
michael@0:         for (Buffer* b = aStart.mBuffer->Next(); b != aEnd.mBuffer; b = b->Next())
michael@0:           result += b->DataLength();
michael@0:         result += aEnd.mPosition - aEnd.mBuffer->DataStart();
michael@0:       }
michael@0:     return result;
michael@0:   }
michael@0: 
michael@0: 
michael@0: /**
michael@0:  * nsScannerSubstring
michael@0:  */
michael@0: 
michael@0: nsScannerSubstring::nsScannerSubstring()
michael@0:   : mStart(nullptr, nullptr)
michael@0:   , mEnd(nullptr, nullptr)
michael@0:   , mBufferList(nullptr)
michael@0:   , mLength(0)
michael@0:   , mIsDirty(true)
michael@0:   {
michael@0:   }
michael@0: 
michael@0: nsScannerSubstring::nsScannerSubstring( const nsAString& s )
michael@0:   : mBufferList(nullptr)
michael@0:   , mIsDirty(true)
michael@0:   {
michael@0:     Rebind(s);
michael@0:   }
michael@0: 
michael@0: nsScannerSubstring::~nsScannerSubstring()
michael@0:   {
michael@0:     release_ownership_of_buffer_list();
michael@0:   }
michael@0: 
michael@0: int32_t
michael@0: nsScannerSubstring::CountChar( char16_t c ) const
michael@0:   {
michael@0:       /*
michael@0:         re-write this to use a counting sink
michael@0:        */
michael@0: 
michael@0:     size_type result = 0;
michael@0:     size_type lengthToExamine = Length();
michael@0: 
michael@0:     nsScannerIterator iter;
michael@0:     for ( BeginReading(iter); ; )
michael@0:       {
michael@0:         int32_t lengthToExamineInThisFragment = iter.size_forward();
michael@0:         const char16_t* fromBegin = iter.get();
michael@0:         result += size_type(NS_COUNT(fromBegin, fromBegin+lengthToExamineInThisFragment, c));
michael@0:         if ( !(lengthToExamine -= lengthToExamineInThisFragment) )
michael@0:           return result;
michael@0:         iter.advance(lengthToExamineInThisFragment);
michael@0:       }
michael@0:       // never reached; quiets warnings
michael@0:     return 0;
michael@0:   }
michael@0: 
michael@0: void
michael@0: nsScannerSubstring::Rebind( const nsScannerSubstring& aString,
michael@0:                             const nsScannerIterator& aStart, 
michael@0:                             const nsScannerIterator& aEnd )
michael@0:   {
michael@0:     // allow for the case where &aString == this
michael@0: 
michael@0:     aString.acquire_ownership_of_buffer_list();
michael@0:     release_ownership_of_buffer_list();
michael@0: 
michael@0:     mStart      = aStart;
michael@0:     mEnd        = aEnd;
michael@0:     mBufferList = aString.mBufferList;
michael@0:     mLength     = Distance(aStart, aEnd);
michael@0:     mIsDirty    = true;
michael@0:   }
michael@0: 
michael@0: void
michael@0: nsScannerSubstring::Rebind( const nsAString& aString )
michael@0:   {
michael@0:     release_ownership_of_buffer_list();
michael@0: 
michael@0:     mBufferList = new nsScannerBufferList(AllocBufferFromString(aString));
michael@0:     mIsDirty    = true;
michael@0: 
michael@0:     init_range_from_buffer_list();
michael@0:     acquire_ownership_of_buffer_list();
michael@0:   }
michael@0: 
michael@0: const nsSubstring&
michael@0: nsScannerSubstring::AsString() const
michael@0:   {
michael@0:     if (mIsDirty)
michael@0:       {
michael@0:         nsScannerSubstring* mutable_this = const_cast<nsScannerSubstring*>(this);
michael@0: 
michael@0:         if (mStart.mBuffer == mEnd.mBuffer) {
michael@0:           // We only have a single fragment to deal with, so just return it
michael@0:           // as a substring.
michael@0:           mutable_this->mFlattenedRep.Rebind(mStart.mPosition, mEnd.mPosition);
michael@0:         } else {
michael@0:           // Otherwise, we need to copy the data into a flattened buffer.
michael@0:           nsScannerIterator start, end;
michael@0:           CopyUnicodeTo(BeginReading(start), EndReading(end), mutable_this->mFlattenedRep);
michael@0:         }
michael@0: 
michael@0:         mutable_this->mIsDirty = false;
michael@0:       }
michael@0: 
michael@0:     return mFlattenedRep;
michael@0:   }
michael@0: 
michael@0: nsScannerIterator&
michael@0: nsScannerSubstring::BeginReading( nsScannerIterator& iter ) const
michael@0:   {
michael@0:     iter.mOwner = this;
michael@0: 
michael@0:     iter.mFragment.mBuffer = mStart.mBuffer;
michael@0:     iter.mFragment.mFragmentStart = mStart.mPosition;
michael@0:     if (mStart.mBuffer == mEnd.mBuffer)
michael@0:       iter.mFragment.mFragmentEnd = mEnd.mPosition;
michael@0:     else
michael@0:       iter.mFragment.mFragmentEnd = mStart.mBuffer->DataEnd();
michael@0: 
michael@0:     iter.mPosition = mStart.mPosition;
michael@0:     iter.normalize_forward();
michael@0:     return iter;
michael@0:   }
michael@0: 
michael@0: nsScannerIterator&
michael@0: nsScannerSubstring::EndReading( nsScannerIterator& iter ) const
michael@0:   {
michael@0:     iter.mOwner = this;
michael@0: 
michael@0:     iter.mFragment.mBuffer = mEnd.mBuffer;
michael@0:     iter.mFragment.mFragmentEnd = mEnd.mPosition;
michael@0:     if (mStart.mBuffer == mEnd.mBuffer)
michael@0:       iter.mFragment.mFragmentStart = mStart.mPosition;
michael@0:     else
michael@0:       iter.mFragment.mFragmentStart = mEnd.mBuffer->DataStart();
michael@0: 
michael@0:     iter.mPosition = mEnd.mPosition;
michael@0:     // must not |normalize_backward| as that would likely invalidate tests like |while ( first != last )|
michael@0:     return iter;
michael@0:   }
michael@0: 
michael@0: bool
michael@0: nsScannerSubstring::GetNextFragment( nsScannerFragment& frag ) const
michael@0:   {
michael@0:     // check to see if we are at the end of the buffer list
michael@0:     if (frag.mBuffer == mEnd.mBuffer)
michael@0:       return false;
michael@0: 
michael@0:     frag.mBuffer = frag.mBuffer->getNext();
michael@0: 
michael@0:     if (frag.mBuffer == mStart.mBuffer)
michael@0:       frag.mFragmentStart = mStart.mPosition;
michael@0:     else
michael@0:       frag.mFragmentStart = frag.mBuffer->DataStart();
michael@0: 
michael@0:     if (frag.mBuffer == mEnd.mBuffer)
michael@0:       frag.mFragmentEnd = mEnd.mPosition;
michael@0:     else
michael@0:       frag.mFragmentEnd = frag.mBuffer->DataEnd();
michael@0: 
michael@0:     return true;
michael@0:   }
michael@0: 
michael@0: bool
michael@0: nsScannerSubstring::GetPrevFragment( nsScannerFragment& frag ) const
michael@0:   {
michael@0:     // check to see if we are at the beginning of the buffer list
michael@0:     if (frag.mBuffer == mStart.mBuffer)
michael@0:       return false;
michael@0: 
michael@0:     frag.mBuffer = frag.mBuffer->getPrevious();
michael@0: 
michael@0:     if (frag.mBuffer == mStart.mBuffer)
michael@0:       frag.mFragmentStart = mStart.mPosition;
michael@0:     else
michael@0:       frag.mFragmentStart = frag.mBuffer->DataStart();
michael@0: 
michael@0:     if (frag.mBuffer == mEnd.mBuffer)
michael@0:       frag.mFragmentEnd = mEnd.mPosition;
michael@0:     else
michael@0:       frag.mFragmentEnd = frag.mBuffer->DataEnd();
michael@0: 
michael@0:     return true;
michael@0:   }
michael@0: 
michael@0: 
michael@0:   /**
michael@0:    * nsScannerString
michael@0:    */
michael@0: 
michael@0: nsScannerString::nsScannerString( Buffer* aBuf )
michael@0:   {
michael@0:     mBufferList = new nsScannerBufferList(aBuf);
michael@0: 
michael@0:     init_range_from_buffer_list();
michael@0:     acquire_ownership_of_buffer_list();
michael@0:   }
michael@0: 
michael@0: void
michael@0: nsScannerString::AppendBuffer( Buffer* aBuf )
michael@0:   {
michael@0:     mBufferList->Append(aBuf);
michael@0:     mLength += aBuf->DataLength();
michael@0: 
michael@0:     mEnd.mBuffer = aBuf;
michael@0:     mEnd.mPosition = aBuf->DataEnd();
michael@0: 
michael@0:     mIsDirty = true;
michael@0:   }
michael@0: 
michael@0: void
michael@0: nsScannerString::DiscardPrefix( const nsScannerIterator& aIter )
michael@0:   {
michael@0:     Position old_start(mStart);
michael@0:     mStart = aIter;
michael@0:     mLength -= Position::Distance(old_start, mStart);
michael@0:     
michael@0:     mStart.mBuffer->IncrementUsageCount();
michael@0:     old_start.mBuffer->DecrementUsageCount();
michael@0: 
michael@0:     mBufferList->DiscardUnreferencedPrefix(old_start.mBuffer);
michael@0: 
michael@0:     mIsDirty = true;
michael@0:   }
michael@0: 
michael@0: void
michael@0: nsScannerString::UngetReadable( const nsAString& aReadable, const nsScannerIterator& aInsertPoint )
michael@0:     /*
michael@0:      * Warning: this routine manipulates the shared buffer list in an unexpected way.
michael@0:      *  The original design did not really allow for insertions, but this call promises
michael@0:      *  that if called for a point after the end of all extant token strings, that no token string
michael@0:      *  or the work string will be invalidated.
michael@0:      *
michael@0:      *  This routine is protected because it is the responsibility of the derived class to keep those promises.
michael@0:      */
michael@0:   {
michael@0:     Position insertPos(aInsertPoint);
michael@0: 
michael@0:     mBufferList->SplitBuffer(insertPos);
michael@0:       // splitting to the right keeps the work string and any extant token pointing to and
michael@0:       //  holding a reference count on the same buffer
michael@0: 
michael@0:     Buffer* new_buffer = AllocBufferFromString(aReadable);
michael@0:       // make a new buffer with all the data to insert...
michael@0:       //  BULLSHIT ALERT: we may have empty space to re-use in the split buffer, measure the cost
michael@0:       //  of this and decide if we should do the work to fill it
michael@0: 
michael@0:     Buffer* buffer_to_split = insertPos.mBuffer;
michael@0:     mBufferList->InsertAfter(new_buffer, buffer_to_split);
michael@0:     mLength += aReadable.Length();
michael@0: 
michael@0:     mEnd.mBuffer = mBufferList->Tail();
michael@0:     mEnd.mPosition = mEnd.mBuffer->DataEnd();
michael@0: 
michael@0:     mIsDirty = true;
michael@0:   }
michael@0: 
michael@0: void
michael@0: nsScannerString::ReplaceCharacter(nsScannerIterator& aPosition, char16_t aChar)
michael@0:   {
michael@0:     // XXX Casting a const to non-const. Unless the base class
michael@0:     // provides support for writing iterators, this is the best
michael@0:     // that can be done.
michael@0:     char16_t* pos = const_cast<char16_t*>(aPosition.get());
michael@0:     *pos = aChar;
michael@0: 
michael@0:     mIsDirty = true;
michael@0:   }
michael@0: 
michael@0: 
michael@0:   /**
michael@0:    * nsScannerSharedSubstring
michael@0:    */
michael@0: 
michael@0: void
michael@0: nsScannerSharedSubstring::Rebind(const nsScannerIterator &aStart,
michael@0:                               const nsScannerIterator &aEnd)
michael@0: {
michael@0:   // If the start and end positions are inside the same buffer, we must
michael@0:   // acquire ownership of the buffer.  If not, we can optimize by not holding
michael@0:   // onto it.
michael@0: 
michael@0:   Buffer *buffer = const_cast<Buffer*>(aStart.buffer());
michael@0:   bool sameBuffer = buffer == aEnd.buffer();
michael@0: 
michael@0:   nsScannerBufferList *bufferList;
michael@0: 
michael@0:   if (sameBuffer) {
michael@0:     bufferList = aStart.mOwner->mBufferList;
michael@0:     bufferList->AddRef();
michael@0:     buffer->IncrementUsageCount();
michael@0:   }
michael@0: 
michael@0:   if (mBufferList)
michael@0:     ReleaseBuffer();
michael@0: 
michael@0:   if (sameBuffer) {
michael@0:     mBuffer = buffer;
michael@0:     mBufferList = bufferList;
michael@0:     mString.Rebind(aStart.mPosition, aEnd.mPosition);
michael@0:   } else {
michael@0:     mBuffer = nullptr;
michael@0:     mBufferList = nullptr;
michael@0:     CopyUnicodeTo(aStart, aEnd, mString);
michael@0:   }
michael@0: }
michael@0: 
michael@0: void
michael@0: nsScannerSharedSubstring::ReleaseBuffer()
michael@0: {
michael@0:   NS_ASSERTION(mBufferList, "Should only be called with non-null mBufferList");
michael@0:   mBuffer->DecrementUsageCount();
michael@0:   mBufferList->DiscardUnreferencedPrefix(mBuffer);
michael@0:   mBufferList->Release();
michael@0: }
michael@0: 
michael@0: void
michael@0: nsScannerSharedSubstring::MakeMutable()
michael@0: {
michael@0:   nsString temp(mString); // this will force a copy of the data
michael@0:   mString.Assign(temp);   // mString will now share the just-allocated buffer
michael@0: 
michael@0:   ReleaseBuffer();
michael@0: 
michael@0:   mBuffer = nullptr;
michael@0:   mBufferList = nullptr;
michael@0: }
michael@0: 
michael@0:   /**
michael@0:    * utils -- based on code from nsReadableUtils.cpp
michael@0:    */
michael@0: 
michael@0: // private helper function
michael@0: static inline
michael@0: nsAString::iterator&
michael@0: copy_multifragment_string( nsScannerIterator& first, const nsScannerIterator& last, nsAString::iterator& result )
michael@0:   {
michael@0:     typedef nsCharSourceTraits<nsScannerIterator> source_traits;
michael@0:     typedef nsCharSinkTraits<nsAString::iterator> sink_traits;
michael@0: 
michael@0:     while ( first != last )
michael@0:       {
michael@0:         uint32_t distance = source_traits::readable_distance(first, last);
michael@0:         sink_traits::write(result, source_traits::read(first), distance);
michael@0:         NS_ASSERTION(distance > 0, "|copy_multifragment_string| will never terminate");
michael@0:         source_traits::advance(first, distance);
michael@0:       }
michael@0: 
michael@0:     return result;
michael@0:   }
michael@0: 
michael@0: void
michael@0: CopyUnicodeTo( const nsScannerIterator& aSrcStart,
michael@0:                const nsScannerIterator& aSrcEnd,
michael@0:                nsAString& aDest )
michael@0:   {
michael@0:     nsAString::iterator writer;
michael@0:     if (!aDest.SetLength(Distance(aSrcStart, aSrcEnd), mozilla::fallible_t())) {
michael@0:       aDest.Truncate();
michael@0:       return; // out of memory
michael@0:     }
michael@0:     aDest.BeginWriting(writer);
michael@0:     nsScannerIterator fromBegin(aSrcStart);
michael@0:     
michael@0:     copy_multifragment_string(fromBegin, aSrcEnd, writer);
michael@0:   }
michael@0: 
michael@0: void
michael@0: AppendUnicodeTo( const nsScannerIterator& aSrcStart,
michael@0:                  const nsScannerIterator& aSrcEnd,
michael@0:                  nsScannerSharedSubstring& aDest )
michael@0:   {
michael@0:     // Check whether we can just create a dependent string.
michael@0:     if (aDest.str().IsEmpty()) {
michael@0:       // We can just make |aDest| point to the buffer.
michael@0:       // This will take care of copying if the buffer spans fragments.
michael@0:       aDest.Rebind(aSrcStart, aSrcEnd);
michael@0:     } else {
michael@0:       // The dest string is not empty, so it can't be a dependent substring.
michael@0:       AppendUnicodeTo(aSrcStart, aSrcEnd, aDest.writable());
michael@0:     }
michael@0:   }
michael@0: 
michael@0: void
michael@0: AppendUnicodeTo( const nsScannerIterator& aSrcStart,
michael@0:                  const nsScannerIterator& aSrcEnd,
michael@0:                  nsAString& aDest )
michael@0:   {
michael@0:     nsAString::iterator writer;
michael@0:     uint32_t oldLength = aDest.Length();
michael@0:     if (!aDest.SetLength(oldLength + Distance(aSrcStart, aSrcEnd), mozilla::fallible_t()))
michael@0:       return; // out of memory
michael@0:     aDest.BeginWriting(writer).advance(oldLength);
michael@0:     nsScannerIterator fromBegin(aSrcStart);
michael@0:     
michael@0:     copy_multifragment_string(fromBegin, aSrcEnd, writer);
michael@0:   }
michael@0: 
michael@0: bool
michael@0: FindCharInReadable( char16_t aChar,
michael@0:                     nsScannerIterator& aSearchStart,
michael@0:                     const nsScannerIterator& aSearchEnd )
michael@0:   {
michael@0:     while ( aSearchStart != aSearchEnd )
michael@0:       {
michael@0:         int32_t fragmentLength;
michael@0:         if ( SameFragment(aSearchStart, aSearchEnd) ) 
michael@0:           fragmentLength = aSearchEnd.get() - aSearchStart.get();
michael@0:         else
michael@0:           fragmentLength = aSearchStart.size_forward();
michael@0: 
michael@0:         const char16_t* charFoundAt = nsCharTraits<char16_t>::find(aSearchStart.get(), fragmentLength, aChar);
michael@0:         if ( charFoundAt ) {
michael@0:           aSearchStart.advance( charFoundAt - aSearchStart.get() );
michael@0:           return true;
michael@0:         }
michael@0: 
michael@0:         aSearchStart.advance(fragmentLength);
michael@0:       }
michael@0: 
michael@0:     return false;
michael@0:   }
michael@0: 
michael@0: bool
michael@0: FindInReadable( const nsAString& aPattern,
michael@0:                 nsScannerIterator& aSearchStart,
michael@0:                 nsScannerIterator& aSearchEnd,
michael@0:                 const nsStringComparator& compare )
michael@0:   {
michael@0:     bool found_it = false;
michael@0: 
michael@0:       // only bother searching at all if we're given a non-empty range to search
michael@0:     if ( aSearchStart != aSearchEnd )
michael@0:       {
michael@0:         nsAString::const_iterator aPatternStart, aPatternEnd;
michael@0:         aPattern.BeginReading(aPatternStart);
michael@0:         aPattern.EndReading(aPatternEnd);
michael@0: 
michael@0:           // outer loop keeps searching till we find it or run out of string to search
michael@0:         while ( !found_it )
michael@0:           {
michael@0:               // fast inner loop (that's what it's called, not what it is) looks for a potential match
michael@0:             while ( aSearchStart != aSearchEnd &&
michael@0:                     compare(aPatternStart.get(), aSearchStart.get(), 1, 1) )
michael@0:               ++aSearchStart;
michael@0: 
michael@0:               // if we broke out of the `fast' loop because we're out of string ... we're done: no match
michael@0:             if ( aSearchStart == aSearchEnd )
michael@0:               break;
michael@0: 
michael@0:               // otherwise, we're at a potential match, let's see if we really hit one
michael@0:             nsAString::const_iterator testPattern(aPatternStart);
michael@0:             nsScannerIterator testSearch(aSearchStart);
michael@0: 
michael@0:               // slow inner loop verifies the potential match (found by the `fast' loop) at the current position
michael@0:             for(;;)
michael@0:               {
michael@0:                   // we already compared the first character in the outer loop,
michael@0:                   //  so we'll advance before the next comparison
michael@0:                 ++testPattern;
michael@0:                 ++testSearch;
michael@0: 
michael@0:                   // if we verified all the way to the end of the pattern, then we found it!
michael@0:                 if ( testPattern == aPatternEnd )
michael@0:                   {
michael@0:                     found_it = true;
michael@0:                     aSearchEnd = testSearch; // return the exact found range through the parameters
michael@0:                     break;
michael@0:                   }
michael@0: 
michael@0:                   // if we got to end of the string we're searching before we hit the end of the
michael@0:                   //  pattern, we'll never find what we're looking for
michael@0:                 if ( testSearch == aSearchEnd )
michael@0:                   {
michael@0:                     aSearchStart = aSearchEnd;
michael@0:                     break;
michael@0:                   }
michael@0: 
michael@0:                   // else if we mismatched ... it's time to advance to the next search position
michael@0:                   //  and get back into the `fast' loop
michael@0:                 if ( compare(testPattern.get(), testSearch.get(), 1, 1) )
michael@0:                   {
michael@0:                     ++aSearchStart;
michael@0:                     break;
michael@0:                   }
michael@0:               }
michael@0:           }
michael@0:       }
michael@0: 
michael@0:     return found_it;
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * This implementation is simple, but does too much work.
michael@0:    * It searches the entire string from left to right, and returns the last match found, if any.
michael@0:    * This implementation will be replaced when I get |reverse_iterator|s working.
michael@0:    */
michael@0: bool
michael@0: RFindInReadable( const nsAString& aPattern,
michael@0:                  nsScannerIterator& aSearchStart,
michael@0:                  nsScannerIterator& aSearchEnd,
michael@0:                  const nsStringComparator& aComparator )
michael@0:   {
michael@0:     bool found_it = false;
michael@0: 
michael@0:     nsScannerIterator savedSearchEnd(aSearchEnd);
michael@0:     nsScannerIterator searchStart(aSearchStart), searchEnd(aSearchEnd);
michael@0: 
michael@0:     while ( searchStart != searchEnd )
michael@0:       {
michael@0:         if ( FindInReadable(aPattern, searchStart, searchEnd, aComparator) )
michael@0:           {
michael@0:             found_it = true;
michael@0: 
michael@0:               // this is the best match so far, so remember it
michael@0:             aSearchStart = searchStart;
michael@0:             aSearchEnd = searchEnd;
michael@0: 
michael@0:               // ...and get ready to search some more
michael@0:               //  (it's tempting to set |searchStart=searchEnd| ... but that misses overlapping patterns)
michael@0:             ++searchStart;
michael@0:             searchEnd = savedSearchEnd;
michael@0:           }
michael@0:       }
michael@0: 
michael@0:       // if we never found it, return an empty range
michael@0:     if ( !found_it )
michael@0:       aSearchStart = aSearchEnd;
michael@0: 
michael@0:     return found_it;
michael@0:   }