tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

nsScannerString.cpp (11370B)

      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 }