1 files changed, 379 insertions, 0 deletions
diff --git a/parser/htmlparser/nsScannerString.cpp b/parser/htmlparser/nsScannerString.cpp
new file mode 100644
index 0000000000..2c7f09cfdd
--- /dev/null
+++ b/parser/htmlparser/nsScannerString.cpp
@@ -0,0 +1,379 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et cindent: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include <stdlib.h>
+#include "nsScannerString.h"
+#include "mozilla/CheckedInt.h"
+
+/**
+ * nsScannerBufferList
+ */
+
+#define MAX_CAPACITY \
+  ((UINT32_MAX / sizeof(char16_t)) - (sizeof(Buffer) + sizeof(char16_t)))
+
+nsScannerBufferList::Buffer* nsScannerBufferList::AllocBufferFromString(
+    const nsAString& aString) {
+  uint32_t len = aString.Length();
+  Buffer* buf = AllocBuffer(len);
+
+  if (buf) {
+    nsAString::const_iterator source;
+    aString.BeginReading(source);
+    nsCharTraits<char16_t>::copy(buf->DataStart(), source.get(), len);
+  }
+  return buf;
+}
+
+nsScannerBufferList::Buffer* nsScannerBufferList::AllocBuffer(
+    uint32_t capacity) {
+  if (capacity > MAX_CAPACITY) return nullptr;
+
+  void* ptr = malloc(sizeof(Buffer) + (capacity + 1) * sizeof(char16_t));
+  if (!ptr) return nullptr;
+
+  Buffer* buf = new (ptr) Buffer();
+
+  buf->mUsageCount = 0;
+  buf->mDataEnd = buf->DataStart() + capacity;
+
+  // XXX null terminate.  this shouldn't be required, but we do it because
+  // nsScanner erroneously thinks it can dereference DataEnd :-(
+  *buf->mDataEnd = char16_t(0);
+  return buf;
+}
+
+void nsScannerBufferList::ReleaseAll() {
+  while (!mBuffers.isEmpty()) {
+    Buffer* node = mBuffers.popFirst();
+    // printf(">>> freeing buffer @%p\n", node);
+    free(node);
+  }
+}
+
+void nsScannerBufferList::SplitBuffer(const Position& pos) {
+  // splitting to the right keeps the work string and any extant token
+  // pointing to and holding a reference count on the same buffer.
+
+  Buffer* bufferToSplit = pos.mBuffer;
+  NS_ASSERTION(bufferToSplit, "null pointer");
+
+  uint32_t splitOffset = pos.mPosition - bufferToSplit->DataStart();
+  NS_ASSERTION(pos.mPosition >= bufferToSplit->DataStart() &&
+                   splitOffset <= bufferToSplit->DataLength(),
+               "split offset is outside buffer");
+
+  uint32_t len = bufferToSplit->DataLength() - splitOffset;
+  Buffer* new_buffer = AllocBuffer(len);
+  if (new_buffer) {
+    nsCharTraits<char16_t>::copy(new_buffer->DataStart(),
+                                 bufferToSplit->DataStart() + splitOffset, len);
+    InsertAfter(new_buffer, bufferToSplit);
+    bufferToSplit->SetDataLength(splitOffset);
+  }
+}
+
+void nsScannerBufferList::DiscardUnreferencedPrefix(Buffer* aBuf) {
+  if (aBuf == Head()) {
+    while (!mBuffers.isEmpty() && !Head()->IsInUse()) {
+      Buffer* buffer = Head();
+      buffer->remove();
+      free(buffer);
+    }
+  }
+}
+
+size_t nsScannerBufferList::Position::Distance(const Position& aStart,
+                                               const Position& aEnd) {
+  size_t result = 0;
+  if (aStart.mBuffer == aEnd.mBuffer) {
+    result = aEnd.mPosition - aStart.mPosition;
+  } else {
+    result = aStart.mBuffer->DataEnd() - aStart.mPosition;
+    for (Buffer* b = aStart.mBuffer->Next(); b != aEnd.mBuffer; b = b->Next())
+      result += b->DataLength();
+    result += aEnd.mPosition - aEnd.mBuffer->DataStart();
+  }
+  return result;
+}
+
+/**
+ * nsScannerSubstring
+ */
+
+nsScannerSubstring::nsScannerSubstring()
+    : mStart(nullptr, nullptr),
+      mEnd(nullptr, nullptr),
+      mBufferList(nullptr),
+      mLength(0) {}
+
+nsScannerSubstring::nsScannerSubstring(const nsAString& s)
+    : mBufferList(nullptr) {
+  Rebind(s);
+}
+
+nsScannerSubstring::~nsScannerSubstring() {
+  release_ownership_of_buffer_list();
+}
+
+void nsScannerSubstring::Rebind(const nsScannerSubstring& aString,
+                                const nsScannerIterator& aStart,
+                                const nsScannerIterator& aEnd) {
+  // allow for the case where &aString == this
+
+  aString.acquire_ownership_of_buffer_list();
+  release_ownership_of_buffer_list();
+
+  mStart = aStart;
+  mEnd = aEnd;
+  mBufferList = aString.mBufferList;
+  mLength = Distance(aStart, aEnd);
+}
+
+void nsScannerSubstring::Rebind(const nsAString& aString) {
+  release_ownership_of_buffer_list();
+
+  mBufferList = new nsScannerBufferList(AllocBufferFromString(aString));
+
+  init_range_from_buffer_list();
+  acquire_ownership_of_buffer_list();
+}
+
+nsScannerIterator& nsScannerSubstring::BeginReading(
+    nsScannerIterator& iter) const {
+  iter.mOwner = this;
+
+  iter.mFragment.mBuffer = mStart.mBuffer;
+  iter.mFragment.mFragmentStart = mStart.mPosition;
+  if (mStart.mBuffer == mEnd.mBuffer)
+    iter.mFragment.mFragmentEnd = mEnd.mPosition;
+  else
+    iter.mFragment.mFragmentEnd = mStart.mBuffer->DataEnd();
+
+  iter.mPosition = mStart.mPosition;
+  iter.normalize_forward();
+  return iter;
+}
+
+nsScannerIterator& nsScannerSubstring::EndReading(
+    nsScannerIterator& iter) const {
+  iter.mOwner = this;
+
+  iter.mFragment.mBuffer = mEnd.mBuffer;
+  iter.mFragment.mFragmentEnd = mEnd.mPosition;
+  if (mStart.mBuffer == mEnd.mBuffer)
+    iter.mFragment.mFragmentStart = mStart.mPosition;
+  else
+    iter.mFragment.mFragmentStart = mEnd.mBuffer->DataStart();
+
+  iter.mPosition = mEnd.mPosition;
+  // must not |normalize_backward| as that would likely invalidate tests like
+  // |while ( first != last )|
+  return iter;
+}
+
+bool nsScannerSubstring::GetNextFragment(nsScannerFragment& frag) const {
+  // check to see if we are at the end of the buffer list
+  if (frag.mBuffer == mEnd.mBuffer) return false;
+
+  frag.mBuffer = frag.mBuffer->getNext();
+
+  if (frag.mBuffer == mStart.mBuffer)
+    frag.mFragmentStart = mStart.mPosition;
+  else
+    frag.mFragmentStart = frag.mBuffer->DataStart();
+
+  if (frag.mBuffer == mEnd.mBuffer)
+    frag.mFragmentEnd = mEnd.mPosition;
+  else
+    frag.mFragmentEnd = frag.mBuffer->DataEnd();
+
+  return true;
+}
+
+bool nsScannerSubstring::GetPrevFragment(nsScannerFragment& frag) const {
+  // check to see if we are at the beginning of the buffer list
+  if (frag.mBuffer == mStart.mBuffer) return false;
+
+  frag.mBuffer = frag.mBuffer->getPrevious();
+
+  if (frag.mBuffer == mStart.mBuffer)
+    frag.mFragmentStart = mStart.mPosition;
+  else
+    frag.mFragmentStart = frag.mBuffer->DataStart();
+
+  if (frag.mBuffer == mEnd.mBuffer)
+    frag.mFragmentEnd = mEnd.mPosition;
+  else
+    frag.mFragmentEnd = frag.mBuffer->DataEnd();
+
+  return true;
+}
+
+/**
+ * nsScannerString
+ */
+
+nsScannerString::nsScannerString(Buffer* aBuf) {
+  mBufferList = new nsScannerBufferList(aBuf);
+
+  init_range_from_buffer_list();
+  acquire_ownership_of_buffer_list();
+}
+
+void nsScannerString::AppendBuffer(Buffer* aBuf) {
+  mBufferList->Append(aBuf);
+  mLength += aBuf->DataLength();
+
+  mEnd.mBuffer = aBuf;
+  mEnd.mPosition = aBuf->DataEnd();
+}
+
+void nsScannerString::DiscardPrefix(const nsScannerIterator& aIter) {
+  Position old_start(mStart);
+  mStart = aIter;
+  mLength -= Position::Distance(old_start, mStart);
+
+  mStart.mBuffer->IncrementUsageCount();
+  old_start.mBuffer->DecrementUsageCount();
+
+  mBufferList->DiscardUnreferencedPrefix(old_start.mBuffer);
+}
+
+void nsScannerString::UngetReadable(const nsAString& aReadable,
+                                    const nsScannerIterator& aInsertPoint)
+/*
+ * Warning: this routine manipulates the shared buffer list in an
+ * unexpected way.  The original design did not really allow for
+ * insertions, but this call promises that if called for a point after the
+ * end of all extant token strings, that no token string or the work string
+ * will be invalidated.
+ *
+ * This routine is protected because it is the responsibility of the
+ * derived class to keep those promises.
+ */
+{
+  Position insertPos(aInsertPoint);
+
+  mBufferList->SplitBuffer(insertPos);
+  // splitting to the right keeps the work string and any extant token
+  // pointing to and holding a reference count on the same buffer
+
+  Buffer* new_buffer = AllocBufferFromString(aReadable);
+  // make a new buffer with all the data to insert...
+  // ALERT: we may have empty space to re-use in the split buffer,
+  // measure the cost of this and decide if we should do the work to fill
+  // it
+
+  Buffer* buffer_to_split = insertPos.mBuffer;
+  mBufferList->InsertAfter(new_buffer, buffer_to_split);
+  mLength += aReadable.Length();
+
+  mEnd.mBuffer = mBufferList->Tail();
+  mEnd.mPosition = mEnd.mBuffer->DataEnd();
+}
+
+/**
+ * nsScannerSharedSubstring
+ */
+
+void nsScannerSharedSubstring::Rebind(const nsScannerIterator& aStart,
+                                      const nsScannerIterator& aEnd) {
+  // If the start and end positions are inside the same buffer, we must
+  // acquire ownership of the buffer.  If not, we can optimize by not holding
+  // onto it.
+
+  Buffer* buffer = const_cast<Buffer*>(aStart.buffer());
+  bool sameBuffer = buffer == aEnd.buffer();
+
+  nsScannerBufferList* bufferList;
+
+  if (sameBuffer) {
+    bufferList = aStart.mOwner->mBufferList;
+    bufferList->AddRef();
+    buffer->IncrementUsageCount();
+  }
+
+  if (mBufferList) ReleaseBuffer();
+
+  if (sameBuffer) {
+    mBuffer = buffer;
+    mBufferList = bufferList;
+    mString.Rebind(aStart.mPosition, aEnd.mPosition);
+  } else {
+    mBuffer = nullptr;
+    mBufferList = nullptr;
+    CopyUnicodeTo(aStart, aEnd, mString);
+  }
+}
+
+void nsScannerSharedSubstring::ReleaseBuffer() {
+  NS_ASSERTION(mBufferList, "Should only be called with non-null mBufferList");
+  mBuffer->DecrementUsageCount();
+  mBufferList->DiscardUnreferencedPrefix(mBuffer);
+  mBufferList->Release();
+}
+
+/**
+ * utils -- based on code from nsReadableUtils.cpp
+ */
+
+// private helper function
+static inline nsAString::iterator& copy_multifragment_string(
+    nsScannerIterator& first, const nsScannerIterator& last,
+    nsAString::iterator& result) {
+  typedef nsCharSourceTraits<nsScannerIterator> source_traits;
+  typedef nsCharSinkTraits<nsAString::iterator> sink_traits;
+
+  while (first != last) {
+    uint32_t distance = source_traits::readable_distance(first, last);
+    sink_traits::write(result, source_traits::read(first), distance);
+    NS_ASSERTION(distance > 0,
+                 "|copy_multifragment_string| will never terminate");
+    source_traits::advance(first, distance);
+  }
+
+  return result;
+}
+
+bool CopyUnicodeTo(const nsScannerIterator& aSrcStart,
+                   const nsScannerIterator& aSrcEnd, nsAString& aDest) {
+  mozilla::CheckedInt<nsAString::size_type> distance(
+      Distance(aSrcStart, aSrcEnd));
+  if (!distance.isValid()) {
+    return false;  // overflow detected
+  }
+
+  if (!aDest.SetLength(distance.value(), mozilla::fallible)) {
+    aDest.Truncate();
+    return false;  // out of memory
+  }
+  auto writer = aDest.BeginWriting();
+  nsScannerIterator fromBegin(aSrcStart);
+
+  copy_multifragment_string(fromBegin, aSrcEnd, writer);
+  return true;
+}
+
+bool AppendUnicodeTo(const nsScannerIterator& aSrcStart,
+                     const nsScannerIterator& aSrcEnd, nsAString& aDest) {
+  const nsAString::size_type oldLength = aDest.Length();
+  mozilla::CheckedInt<nsAString::size_type> newLen(
+      Distance(aSrcStart, aSrcEnd));
+  newLen += oldLength;
+  if (!newLen.isValid()) {
+    return false;  // overflow detected
+  }
+
+  if (!aDest.SetLength(newLen.value(), mozilla::fallible))
+    return false;  // out of memory
+  auto writer = aDest.BeginWriting();
+  std::advance(writer, oldLength);
+  nsScannerIterator fromBegin(aSrcStart);
+
+  copy_multifragment_string(fromBegin, aSrcEnd, writer);
+  return true;
+}