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/. */
8 #include "nsScannerString.h"
9 #include "mozilla/CheckedInt.h"
15 #define MAX_CAPACITY \
16 ((UINT32_MAX / sizeof(char16_t)) - (sizeof(Buffer) + sizeof(char16_t)))
18 nsScannerBufferList::Buffer
* nsScannerBufferList::AllocBufferFromString(
19 const nsAString
& aString
) {
20 uint32_t len
= aString
.Length();
21 Buffer
* buf
= AllocBuffer(len
);
24 nsAString::const_iterator source
;
25 aString
.BeginReading(source
);
26 nsCharTraits
<char16_t
>::copy(buf
->DataStart(), source
.get(), len
);
31 nsScannerBufferList::Buffer
* nsScannerBufferList::AllocBuffer(
33 if (capacity
> MAX_CAPACITY
) return nullptr;
35 void* ptr
= malloc(sizeof(Buffer
) + (capacity
+ 1) * sizeof(char16_t
));
36 if (!ptr
) return nullptr;
38 Buffer
* buf
= new (ptr
) Buffer();
41 buf
->mDataEnd
= buf
->DataStart() + capacity
;
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);
49 void nsScannerBufferList::ReleaseAll() {
50 while (!mBuffers
.isEmpty()) {
51 Buffer
* node
= mBuffers
.popFirst();
52 // printf(">>> freeing buffer @%p\n", node);
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.
61 Buffer
* bufferToSplit
= pos
.mBuffer
;
62 NS_ASSERTION(bufferToSplit
, "null pointer");
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");
69 uint32_t len
= bufferToSplit
->DataLength() - splitOffset
;
70 Buffer
* new_buffer
= AllocBuffer(len
);
72 nsCharTraits
<char16_t
>::copy(new_buffer
->DataStart(),
73 bufferToSplit
->DataStart() + splitOffset
, len
);
74 InsertAfter(new_buffer
, bufferToSplit
);
75 bufferToSplit
->SetDataLength(splitOffset
);
79 void nsScannerBufferList::DiscardUnreferencedPrefix(Buffer
* aBuf
) {
81 while (!mBuffers
.isEmpty() && !Head()->IsInUse()) {
82 Buffer
* buffer
= Head();
89 size_t nsScannerBufferList::Position::Distance(const Position
& aStart
,
90 const Position
& aEnd
) {
92 if (aStart
.mBuffer
== aEnd
.mBuffer
) {
93 result
= aEnd
.mPosition
- aStart
.mPosition
;
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();
107 nsScannerSubstring::nsScannerSubstring()
108 : mStart(nullptr, nullptr),
109 mEnd(nullptr, nullptr),
110 mBufferList(nullptr),
113 nsScannerSubstring::nsScannerSubstring(const nsAString
& s
)
114 : mBufferList(nullptr) {
118 nsScannerSubstring::~nsScannerSubstring() {
119 release_ownership_of_buffer_list();
122 void nsScannerSubstring::Rebind(const nsScannerSubstring
& aString
,
123 const nsScannerIterator
& aStart
,
124 const nsScannerIterator
& aEnd
) {
125 // allow for the case where &aString == this
127 aString
.acquire_ownership_of_buffer_list();
128 release_ownership_of_buffer_list();
132 mBufferList
= aString
.mBufferList
;
133 mLength
= Distance(aStart
, aEnd
);
136 void nsScannerSubstring::Rebind(const nsAString
& aString
) {
137 release_ownership_of_buffer_list();
139 mBufferList
= new nsScannerBufferList(AllocBufferFromString(aString
));
141 init_range_from_buffer_list();
142 acquire_ownership_of_buffer_list();
145 nsScannerIterator
& nsScannerSubstring::BeginReading(
146 nsScannerIterator
& iter
) const {
149 iter
.mFragment
.mBuffer
= mStart
.mBuffer
;
150 iter
.mFragment
.mFragmentStart
= mStart
.mPosition
;
151 if (mStart
.mBuffer
== mEnd
.mBuffer
)
152 iter
.mFragment
.mFragmentEnd
= mEnd
.mPosition
;
154 iter
.mFragment
.mFragmentEnd
= mStart
.mBuffer
->DataEnd();
156 iter
.mPosition
= mStart
.mPosition
;
157 iter
.normalize_forward();
161 nsScannerIterator
& nsScannerSubstring::EndReading(
162 nsScannerIterator
& iter
) const {
165 iter
.mFragment
.mBuffer
= mEnd
.mBuffer
;
166 iter
.mFragment
.mFragmentEnd
= mEnd
.mPosition
;
167 if (mStart
.mBuffer
== mEnd
.mBuffer
)
168 iter
.mFragment
.mFragmentStart
= mStart
.mPosition
;
170 iter
.mFragment
.mFragmentStart
= mEnd
.mBuffer
->DataStart();
172 iter
.mPosition
= mEnd
.mPosition
;
173 // must not |normalize_backward| as that would likely invalidate tests like
174 // |while ( first != last )|
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;
182 frag
.mBuffer
= frag
.mBuffer
->getNext();
184 if (frag
.mBuffer
== mStart
.mBuffer
)
185 frag
.mFragmentStart
= mStart
.mPosition
;
187 frag
.mFragmentStart
= frag
.mBuffer
->DataStart();
189 if (frag
.mBuffer
== mEnd
.mBuffer
)
190 frag
.mFragmentEnd
= mEnd
.mPosition
;
192 frag
.mFragmentEnd
= frag
.mBuffer
->DataEnd();
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;
201 frag
.mBuffer
= frag
.mBuffer
->getPrevious();
203 if (frag
.mBuffer
== mStart
.mBuffer
)
204 frag
.mFragmentStart
= mStart
.mPosition
;
206 frag
.mFragmentStart
= frag
.mBuffer
->DataStart();
208 if (frag
.mBuffer
== mEnd
.mBuffer
)
209 frag
.mFragmentEnd
= mEnd
.mPosition
;
211 frag
.mFragmentEnd
= frag
.mBuffer
->DataEnd();
220 nsScannerString::nsScannerString(Buffer
* aBuf
) {
221 mBufferList
= new nsScannerBufferList(aBuf
);
223 init_range_from_buffer_list();
224 acquire_ownership_of_buffer_list();
227 void nsScannerString::AppendBuffer(Buffer
* aBuf
) {
228 mBufferList
->Append(aBuf
);
229 mLength
+= aBuf
->DataLength();
232 mEnd
.mPosition
= aBuf
->DataEnd();
235 void nsScannerString::DiscardPrefix(const nsScannerIterator
& aIter
) {
236 Position
old_start(mStart
);
238 mLength
-= Position::Distance(old_start
, mStart
);
240 mStart
.mBuffer
->IncrementUsageCount();
241 old_start
.mBuffer
->DecrementUsageCount();
243 mBufferList
->DiscardUnreferencedPrefix(old_start
.mBuffer
);
246 void nsScannerString::UngetReadable(const nsAString
& aReadable
,
247 const nsScannerIterator
& aInsertPoint
)
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.
255 * This routine is protected because it is the responsibility of the
256 * derived class to keep those promises.
259 Position
insertPos(aInsertPoint
);
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
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
271 Buffer
* buffer_to_split
= insertPos
.mBuffer
;
272 mBufferList
->InsertAfter(new_buffer
, buffer_to_split
);
273 mLength
+= aReadable
.Length();
275 mEnd
.mBuffer
= mBufferList
->Tail();
276 mEnd
.mPosition
= mEnd
.mBuffer
->DataEnd();
280 * nsScannerSharedSubstring
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
289 Buffer
* buffer
= const_cast<Buffer
*>(aStart
.buffer());
290 bool sameBuffer
= buffer
== aEnd
.buffer();
292 nsScannerBufferList
* bufferList
;
295 bufferList
= aStart
.mOwner
->mBufferList
;
296 bufferList
->AddRef();
297 buffer
->IncrementUsageCount();
300 if (mBufferList
) ReleaseBuffer();
304 mBufferList
= bufferList
;
305 mString
.Rebind(aStart
.mPosition
, aEnd
.mPosition
);
308 mBufferList
= nullptr;
309 CopyUnicodeTo(aStart
, aEnd
, mString
);
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();
321 * utils -- based on code from nsReadableUtils.cpp
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
;
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
);
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
350 if (!aDest
.SetLength(distance
.value(), mozilla::fallible
)) {
352 return false; // out of memory
354 auto writer
= aDest
.BeginWriting();
355 nsScannerIterator
fromBegin(aSrcStart
);
357 copy_multifragment_string(fromBegin
, aSrcEnd
, writer
);
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
));
367 if (!newLen
.isValid()) {
368 return false; // overflow detected
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
);
377 copy_multifragment_string(fromBegin
, aSrcEnd
, writer
);