parser/htmlparser/nsScannerString.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim:set ts=2 sw=2 sts=2 et cindent: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include <stdlib.h>
   8 #include "nsScannerString.h"
   9 #include "mozilla/CheckedInt.h"
  10
  11 /**
  12  * nsScannerBufferList
  13  */
  14
  15 #define MAX_CAPACITY \
  16   ((UINT32_MAX / sizeof(char16_t)) - (sizeof(Buffer) + sizeof(char16_t)))
  17
  18 nsScannerBufferList::Buffer* nsScannerBufferList::AllocBufferFromString(
  19     const nsAString& aString) {
  20   uint32_t len = aString.Length();
  21   Buffer* buf = AllocBuffer(len);
  22
  23   if (buf) {
  24     nsAString::const_iterator source;
  25     aString.BeginReading(source);
  26     nsCharTraits<char16_t>::copy(buf->DataStart(), source.get(), len);
  27   }
  28   return buf;
  29 }
  30
  31 nsScannerBufferList::Buffer* nsScannerBufferList::AllocBuffer(
  32     uint32_t capacity) {
  33   if (capacity > MAX_CAPACITY) return nullptr;
  34
  35   void* ptr = malloc(sizeof(Buffer) + (capacity + 1) * sizeof(char16_t));
  36   if (!ptr) return nullptr;
  37
  38   Buffer* buf = new (ptr) Buffer();
  39
  40   buf->mUsageCount = 0;
  41   buf->mDataEnd = buf->DataStart() + capacity;
  42
  43   // XXX null terminate.  this shouldn't be required, but we do it because
  44   // nsScanner erroneously thinks it can dereference DataEnd :-(
  45   *buf->mDataEnd = char16_t(0);
  46   return buf;
  47 }
  48
  49 void nsScannerBufferList::ReleaseAll() {
  50   while (!mBuffers.isEmpty()) {
  51     Buffer* node = mBuffers.popFirst();
  52     // printf(">>> freeing buffer @%p\n", node);
  53     free(node);
  54   }
  55 }
  56
  57 void nsScannerBufferList::SplitBuffer(const Position& pos) {
  58   // splitting to the right keeps the work string and any extant token
  59   // pointing to and holding a reference count on the same buffer.
  60
  61   Buffer* bufferToSplit = pos.mBuffer;
  62   NS_ASSERTION(bufferToSplit, "null pointer");
  63
  64   uint32_t splitOffset = pos.mPosition - bufferToSplit->DataStart();
  65   NS_ASSERTION(pos.mPosition >= bufferToSplit->DataStart() &&
  66                    splitOffset <= bufferToSplit->DataLength(),
  67                "split offset is outside buffer");
  68
  69   uint32_t len = bufferToSplit->DataLength() - splitOffset;
  70   Buffer* new_buffer = AllocBuffer(len);
  71   if (new_buffer) {
  72     nsCharTraits<char16_t>::copy(new_buffer->DataStart(),
  73                                  bufferToSplit->DataStart() + splitOffset, len);
  74     InsertAfter(new_buffer, bufferToSplit);
  75     bufferToSplit->SetDataLength(splitOffset);
  76   }
  77 }
  78
  79 void nsScannerBufferList::DiscardUnreferencedPrefix(Buffer* aBuf) {
  80   if (aBuf == Head()) {
  81     while (!mBuffers.isEmpty() && !Head()->IsInUse()) {
  82       Buffer* buffer = Head();
  83       buffer->remove();
  84       free(buffer);
  85     }
  86   }
  87 }
  88
  89 size_t nsScannerBufferList::Position::Distance(const Position& aStart,
  90                                                const Position& aEnd) {
  91   size_t result = 0;
  92   if (aStart.mBuffer == aEnd.mBuffer) {
  93     result = aEnd.mPosition - aStart.mPosition;
  94   } else {
  95     result = aStart.mBuffer->DataEnd() - aStart.mPosition;
  96     for (Buffer* b = aStart.mBuffer->Next(); b != aEnd.mBuffer; b = b->Next())
  97       result += b->DataLength();
  98     result += aEnd.mPosition - aEnd.mBuffer->DataStart();
  99   }
 100   return result;
 101 }
 102
 103 /**
 104  * nsScannerSubstring
 105  */
 106
 107 nsScannerSubstring::nsScannerSubstring()
 108     : mStart(nullptr, nullptr),
 109       mEnd(nullptr, nullptr),
 110       mBufferList(nullptr),
 111       mLength(0) {}
 112
 113 nsScannerSubstring::nsScannerSubstring(const nsAString& s)
 114     : mBufferList(nullptr) {
 115   Rebind(s);
 116 }
 117
 118 nsScannerSubstring::~nsScannerSubstring() {
 119   release_ownership_of_buffer_list();
 120 }
 121
 122 void nsScannerSubstring::Rebind(const nsScannerSubstring& aString,
 123                                 const nsScannerIterator& aStart,
 124                                 const nsScannerIterator& aEnd) {
 125   // allow for the case where &aString == this
 126
 127   aString.acquire_ownership_of_buffer_list();
 128   release_ownership_of_buffer_list();
 129
 130   mStart = aStart;
 131   mEnd = aEnd;
 132   mBufferList = aString.mBufferList;
 133   mLength = Distance(aStart, aEnd);
 134 }
 135
 136 void nsScannerSubstring::Rebind(const nsAString& aString) {
 137   release_ownership_of_buffer_list();
 138
 139   mBufferList = new nsScannerBufferList(AllocBufferFromString(aString));
 140
 141   init_range_from_buffer_list();
 142   acquire_ownership_of_buffer_list();
 143 }
 144
 145 nsScannerIterator& nsScannerSubstring::BeginReading(
 146     nsScannerIterator& iter) const {
 147   iter.mOwner = this;
 148
 149   iter.mFragment.mBuffer = mStart.mBuffer;
 150   iter.mFragment.mFragmentStart = mStart.mPosition;
 151   if (mStart.mBuffer == mEnd.mBuffer)
 152     iter.mFragment.mFragmentEnd = mEnd.mPosition;
 153   else
 154     iter.mFragment.mFragmentEnd = mStart.mBuffer->DataEnd();
 155
 156   iter.mPosition = mStart.mPosition;
 157   iter.normalize_forward();
 158   return iter;
 159 }
 160
 161 nsScannerIterator& nsScannerSubstring::EndReading(
 162     nsScannerIterator& iter) const {
 163   iter.mOwner = this;
 164
 165   iter.mFragment.mBuffer = mEnd.mBuffer;
 166   iter.mFragment.mFragmentEnd = mEnd.mPosition;
 167   if (mStart.mBuffer == mEnd.mBuffer)
 168     iter.mFragment.mFragmentStart = mStart.mPosition;
 169   else
 170     iter.mFragment.mFragmentStart = mEnd.mBuffer->DataStart();
 171
 172   iter.mPosition = mEnd.mPosition;
 173   // must not |normalize_backward| as that would likely invalidate tests like
 174   // |while ( first != last )|
 175   return iter;
 176 }
 177
 178 bool nsScannerSubstring::GetNextFragment(nsScannerFragment& frag) const {
 179   // check to see if we are at the end of the buffer list
 180   if (frag.mBuffer == mEnd.mBuffer) return false;
 181
 182   frag.mBuffer = frag.mBuffer->getNext();
 183
 184   if (frag.mBuffer == mStart.mBuffer)
 185     frag.mFragmentStart = mStart.mPosition;
 186   else
 187     frag.mFragmentStart = frag.mBuffer->DataStart();
 188
 189   if (frag.mBuffer == mEnd.mBuffer)
 190     frag.mFragmentEnd = mEnd.mPosition;
 191   else
 192     frag.mFragmentEnd = frag.mBuffer->DataEnd();
 193
 194   return true;
 195 }
 196
 197 bool nsScannerSubstring::GetPrevFragment(nsScannerFragment& frag) const {
 198   // check to see if we are at the beginning of the buffer list
 199   if (frag.mBuffer == mStart.mBuffer) return false;
 200
 201   frag.mBuffer = frag.mBuffer->getPrevious();
 202
 203   if (frag.mBuffer == mStart.mBuffer)
 204     frag.mFragmentStart = mStart.mPosition;
 205   else
 206     frag.mFragmentStart = frag.mBuffer->DataStart();
 207
 208   if (frag.mBuffer == mEnd.mBuffer)
 209     frag.mFragmentEnd = mEnd.mPosition;
 210   else
 211     frag.mFragmentEnd = frag.mBuffer->DataEnd();
 212
 213   return true;
 214 }
 215
 216 /**
 217  * nsScannerString
 218  */
 219
 220 nsScannerString::nsScannerString(Buffer* aBuf) {
 221   mBufferList = new nsScannerBufferList(aBuf);
 222
 223   init_range_from_buffer_list();
 224   acquire_ownership_of_buffer_list();
 225 }
 226
 227 void nsScannerString::AppendBuffer(Buffer* aBuf) {
 228   mBufferList->Append(aBuf);
 229   mLength += aBuf->DataLength();
 230
 231   mEnd.mBuffer = aBuf;
 232   mEnd.mPosition = aBuf->DataEnd();
 233 }
 234
 235 void nsScannerString::DiscardPrefix(const nsScannerIterator& aIter) {
 236   Position old_start(mStart);
 237   mStart = aIter;
 238   mLength -= Position::Distance(old_start, mStart);
 239
 240   mStart.mBuffer->IncrementUsageCount();
 241   old_start.mBuffer->DecrementUsageCount();
 242
 243   mBufferList->DiscardUnreferencedPrefix(old_start.mBuffer);
 244 }
 245
 246 void nsScannerString::UngetReadable(const nsAString& aReadable,
 247                                     const nsScannerIterator& aInsertPoint)
 248 /*
 249  * Warning: this routine manipulates the shared buffer list in an
 250  * unexpected way.  The original design did not really allow for
 251  * insertions, but this call promises that if called for a point after the
 252  * end of all extant token strings, that no token string or the work string
 253  * will be invalidated.
 254  *
 255  * This routine is protected because it is the responsibility of the
 256  * derived class to keep those promises.
 257  */
 258 {
 259   Position insertPos(aInsertPoint);
 260
 261   mBufferList->SplitBuffer(insertPos);
 262   // splitting to the right keeps the work string and any extant token
 263   // pointing to and holding a reference count on the same buffer
 264
 265   Buffer* new_buffer = AllocBufferFromString(aReadable);
 266   // make a new buffer with all the data to insert...
 267   // ALERT: we may have empty space to re-use in the split buffer,
 268   // measure the cost of this and decide if we should do the work to fill
 269   // it
 270
 271   Buffer* buffer_to_split = insertPos.mBuffer;
 272   mBufferList->InsertAfter(new_buffer, buffer_to_split);
 273   mLength += aReadable.Length();
 274
 275   mEnd.mBuffer = mBufferList->Tail();
 276   mEnd.mPosition = mEnd.mBuffer->DataEnd();
 277 }
 278
 279 /**
 280  * nsScannerSharedSubstring
 281  */
 282
 283 void nsScannerSharedSubstring::Rebind(const nsScannerIterator& aStart,
 284                                       const nsScannerIterator& aEnd) {
 285   // If the start and end positions are inside the same buffer, we must
 286   // acquire ownership of the buffer.  If not, we can optimize by not holding
 287   // onto it.
 288
 289   Buffer* buffer = const_cast<Buffer*>(aStart.buffer());
 290   bool sameBuffer = buffer == aEnd.buffer();
 291
 292   nsScannerBufferList* bufferList;
 293
 294   if (sameBuffer) {
 295     bufferList = aStart.mOwner->mBufferList;
 296     bufferList->AddRef();
 297     buffer->IncrementUsageCount();
 298   }
 299
 300   if (mBufferList) ReleaseBuffer();
 301
 302   if (sameBuffer) {
 303     mBuffer = buffer;
 304     mBufferList = bufferList;
 305     mString.Rebind(aStart.mPosition, aEnd.mPosition);
 306   } else {
 307     mBuffer = nullptr;
 308     mBufferList = nullptr;
 309     CopyUnicodeTo(aStart, aEnd, mString);
 310   }
 311 }
 312
 313 void nsScannerSharedSubstring::ReleaseBuffer() {
 314   NS_ASSERTION(mBufferList, "Should only be called with non-null mBufferList");
 315   mBuffer->DecrementUsageCount();
 316   mBufferList->DiscardUnreferencedPrefix(mBuffer);
 317   mBufferList->Release();
 318 }
 319
 320 /**
 321  * utils -- based on code from nsReadableUtils.cpp
 322  */
 323
 324 // private helper function
 325 static inline nsAString::iterator& copy_multifragment_string(
 326     nsScannerIterator& first, const nsScannerIterator& last,
 327     nsAString::iterator& result) {
 328   typedef nsCharSourceTraits<nsScannerIterator> source_traits;
 329   typedef nsCharSinkTraits<nsAString::iterator> sink_traits;
 330
 331   while (first != last) {
 332     uint32_t distance = source_traits::readable_distance(first, last);
 333     sink_traits::write(result, source_traits::read(first), distance);
 334     NS_ASSERTION(distance > 0,
 335                  "|copy_multifragment_string| will never terminate");
 336     source_traits::advance(first, distance);
 337   }
 338
 339   return result;
 340 }
 341
 342 bool CopyUnicodeTo(const nsScannerIterator& aSrcStart,
 343                    const nsScannerIterator& aSrcEnd, nsAString& aDest) {
 344   mozilla::CheckedInt<nsAString::size_type> distance(
 345       Distance(aSrcStart, aSrcEnd));
 346   if (!distance.isValid()) {
 347     return false;  // overflow detected
 348   }
 349
 350   if (!aDest.SetLength(distance.value(), mozilla::fallible)) {
 351     aDest.Truncate();
 352     return false;  // out of memory
 353   }
 354   auto writer = aDest.BeginWriting();
 355   nsScannerIterator fromBegin(aSrcStart);
 356
 357   copy_multifragment_string(fromBegin, aSrcEnd, writer);
 358   return true;
 359 }
 360
 361 bool AppendUnicodeTo(const nsScannerIterator& aSrcStart,
 362                      const nsScannerIterator& aSrcEnd, nsAString& aDest) {
 363   const nsAString::size_type oldLength = aDest.Length();
 364   mozilla::CheckedInt<nsAString::size_type> newLen(
 365       Distance(aSrcStart, aSrcEnd));
 366   newLen += oldLength;
 367   if (!newLen.isValid()) {
 368     return false;  // overflow detected
 369   }
 370
 371   if (!aDest.SetLength(newLen.value(), mozilla::fallible))
 372     return false;  // out of memory
 373   auto writer = aDest.BeginWriting();
 374   std::advance(writer, oldLength);
 375   nsScannerIterator fromBegin(aSrcStart);
 376
 377   copy_multifragment_string(fromBegin, aSrcEnd, writer);
 378   return true;
 379 }