1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
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 "vm/String-inl.h"
8
9 #include "mozilla/MathAlgorithms.h"
10 #include "mozilla/MemoryReporting.h"
11 #include "mozilla/PodOperations.h"
12 #include "mozilla/RangedPtr.h"
13 #include "mozilla/SizePrintfMacros.h"
14 #include "mozilla/TypeTraits.h"
15 #include "mozilla/Unused.h"
16
17 #include "gc/Marking.h"
18 #include "js/UbiNode.h"
19 #include "vm/SPSProfiler.h"
20
21 #include "jscntxtinlines.h"
22 #include "jscompartmentinlines.h"
23
24 using namespace js;
25
26 using mozilla::IsSame;
27 using mozilla::PodCopy;
28 using mozilla::RangedPtr;
29 using mozilla::RoundUpPow2;
30
31 using JS::AutoCheckCannotGC;
32
33 size_t
sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf)34 JSString::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf)
35 {
36 // JSRope: do nothing, we'll count all children chars when we hit the leaf strings.
37 if (isRope())
38 return 0;
39
40 MOZ_ASSERT(isLinear());
41
42 // JSDependentString: do nothing, we'll count the chars when we hit the base string.
43 if (isDependent())
44 return 0;
45
46 // JSExternalString: don't count, the chars could be stored anywhere.
47 if (isExternal())
48 return 0;
49
50 MOZ_ASSERT(isFlat());
51
52 // JSExtensibleString: count the full capacity, not just the used space.
53 if (isExtensible()) {
54 JSExtensibleString& extensible = asExtensible();
55 return extensible.hasLatin1Chars()
56 ? mallocSizeOf(extensible.rawLatin1Chars())
57 : mallocSizeOf(extensible.rawTwoByteChars());
58 }
59
60 // JSInlineString, JSFatInlineString [JSInlineAtom, JSFatInlineAtom]: the chars are inline.
61 if (isInline())
62 return 0;
63
64 // JSAtom, JSUndependedString: measure the space for the chars. For
65 // JSUndependedString, there is no need to count the base string, for the
66 // same reason as JSDependentString above.
67 JSFlatString& flat = asFlat();
68 return flat.hasLatin1Chars()
69 ? mallocSizeOf(flat.rawLatin1Chars())
70 : mallocSizeOf(flat.rawTwoByteChars());
71 }
72
73 JS::ubi::Node::Size
size(mozilla::MallocSizeOf mallocSizeOf) const74 JS::ubi::Concrete<JSString>::size(mozilla::MallocSizeOf mallocSizeOf) const
75 {
76 JSString& str = get();
77 size_t size;
78 if (str.isAtom())
79 size = str.isFatInline() ? sizeof(js::FatInlineAtom) : sizeof(js::NormalAtom);
80 else
81 size = str.isFatInline() ? sizeof(JSFatInlineString) : sizeof(JSString);
82
83 // We can't use mallocSizeof on things in the nursery. At the moment,
84 // strings are never in the nursery, but that may change.
85 MOZ_ASSERT(!IsInsideNursery(&str));
86 size += str.sizeOfExcludingThis(mallocSizeOf);
87
88 return size;
89 }
90
91 const char16_t JS::ubi::Concrete<JSString>::concreteTypeName[] = u"JSString";
92
93 #ifdef DEBUG
94
95 template <typename CharT>
96 /*static */ void
dumpChars(const CharT * s,size_t n,FILE * fp)97 JSString::dumpChars(const CharT* s, size_t n, FILE* fp)
98 {
99 if (n == SIZE_MAX) {
100 n = 0;
101 while (s[n])
102 n++;
103 }
104
105 fputc('"', fp);
106 for (size_t i = 0; i < n; i++) {
107 char16_t c = s[i];
108 if (c == '\n')
109 fprintf(fp, "\\n");
110 else if (c == '\t')
111 fprintf(fp, "\\t");
112 else if (c >= 32 && c < 127)
113 fputc(s[i], fp);
114 else if (c <= 255)
115 fprintf(fp, "\\x%02x", unsigned(c));
116 else
117 fprintf(fp, "\\u%04x", unsigned(c));
118 }
119 fputc('"', fp);
120 }
121
122 template void
123 JSString::dumpChars(const Latin1Char* s, size_t n, FILE* fp);
124
125 template void
126 JSString::dumpChars(const char16_t* s, size_t n, FILE* fp);
127
128 void
dumpCharsNoNewline(FILE * fp)129 JSString::dumpCharsNoNewline(FILE* fp)
130 {
131 if (JSLinearString* linear = ensureLinear(nullptr)) {
132 AutoCheckCannotGC nogc;
133 if (hasLatin1Chars())
134 dumpChars(linear->latin1Chars(nogc), length(), fp);
135 else
136 dumpChars(linear->twoByteChars(nogc), length(), fp);
137 } else {
138 fprintf(fp, "(oom in JSString::dumpCharsNoNewline)");
139 }
140 }
141
142 void
dump(FILE * fp)143 JSString::dump(FILE* fp)
144 {
145 if (JSLinearString* linear = ensureLinear(nullptr)) {
146 AutoCheckCannotGC nogc;
147 if (hasLatin1Chars()) {
148 const Latin1Char* chars = linear->latin1Chars(nogc);
149 fprintf(fp, "JSString* (%p) = Latin1Char * (%p) = ", (void*) this,
150 (void*) chars);
151 dumpChars(chars, length(), fp);
152 } else {
153 const char16_t* chars = linear->twoByteChars(nogc);
154 fprintf(fp, "JSString* (%p) = char16_t * (%p) = ", (void*) this,
155 (void*) chars);
156 dumpChars(chars, length(), fp);
157 }
158 } else {
159 fprintf(fp, "(oom in JSString::dump)");
160 }
161 fputc('\n', fp);
162 }
163
164 void
dumpCharsNoNewline()165 JSString::dumpCharsNoNewline()
166 {
167 dumpCharsNoNewline(stderr);
168 }
169
170 void
dump()171 JSString::dump()
172 {
173 dump(stderr);
174 }
175
176 void
dumpRepresentation(FILE * fp,int indent) const177 JSString::dumpRepresentation(FILE* fp, int indent) const
178 {
179 if (isRope()) asRope() .dumpRepresentation(fp, indent);
180 else if (isDependent()) asDependent() .dumpRepresentation(fp, indent);
181 else if (isExternal()) asExternal() .dumpRepresentation(fp, indent);
182 else if (isExtensible()) asExtensible() .dumpRepresentation(fp, indent);
183 else if (isInline()) asInline() .dumpRepresentation(fp, indent);
184 else if (isFlat()) asFlat() .dumpRepresentation(fp, indent);
185 else
186 MOZ_CRASH("Unexpected JSString representation");
187 }
188
189 void
dumpRepresentationHeader(FILE * fp,int indent,const char * subclass) const190 JSString::dumpRepresentationHeader(FILE* fp, int indent, const char* subclass) const
191 {
192 uint32_t flags = d.u1.flags;
193 // Print the string's address as an actual C++ expression, to facilitate
194 // copy-and-paste into a debugger.
195 fprintf(fp, "((%s*) %p) length: %" PRIuSIZE " flags: 0x%x", subclass, this, length(), flags);
196 if (flags & FLAT_BIT) fputs(" FLAT", fp);
197 if (flags & HAS_BASE_BIT) fputs(" HAS_BASE", fp);
198 if (flags & INLINE_CHARS_BIT) fputs(" INLINE_CHARS", fp);
199 if (flags & ATOM_BIT) fputs(" ATOM", fp);
200 if (isPermanentAtom()) fputs(" PERMANENT", fp);
201 if (flags & LATIN1_CHARS_BIT) fputs(" LATIN1", fp);
202 fputc('\n', fp);
203 }
204
205 void
dumpRepresentationChars(FILE * fp,int indent) const206 JSLinearString::dumpRepresentationChars(FILE* fp, int indent) const
207 {
208 if (hasLatin1Chars()) {
209 fprintf(fp, "%*schars: ((Latin1Char*) %p) ", indent, "", rawLatin1Chars());
210 dumpChars(rawLatin1Chars(), length());
211 } else {
212 fprintf(fp, "%*schars: ((char16_t*) %p) ", indent, "", rawTwoByteChars());
213 dumpChars(rawTwoByteChars(), length());
214 }
215 fputc('\n', fp);
216 }
217
218 bool
equals(const char * s)219 JSString::equals(const char* s)
220 {
221 JSLinearString* linear = ensureLinear(nullptr);
222 if (!linear) {
223 fprintf(stderr, "OOM in JSString::equals!\n");
224 return false;
225 }
226
227 return StringEqualsAscii(linear, s);
228 }
229 #endif /* DEBUG */
230
231 template <typename CharT>
232 static MOZ_ALWAYS_INLINE bool
AllocChars(JSString * str,size_t length,CharT ** chars,size_t * capacity)233 AllocChars(JSString* str, size_t length, CharT** chars, size_t* capacity)
234 {
235 /*
236 * String length doesn't include the null char, so include it here before
237 * doubling. Adding the null char after doubling would interact poorly with
238 * round-up malloc schemes.
239 */
240 size_t numChars = length + 1;
241
242 /*
243 * Grow by 12.5% if the buffer is very large. Otherwise, round up to the
244 * next power of 2. This is similar to what we do with arrays; see
245 * JSObject::ensureDenseArrayElements.
246 */
247 static const size_t DOUBLING_MAX = 1024 * 1024;
248 numChars = numChars > DOUBLING_MAX ? numChars + (numChars / 8) : RoundUpPow2(numChars);
249
250 /* Like length, capacity does not include the null char, so take it out. */
251 *capacity = numChars - 1;
252
253 JS_STATIC_ASSERT(JSString::MAX_LENGTH * sizeof(CharT) < UINT32_MAX);
254 *chars = str->zone()->pod_malloc<CharT>(numChars);
255 return *chars != nullptr;
256 }
257
258 bool
copyLatin1CharsZ(ExclusiveContext * cx,ScopedJSFreePtr<Latin1Char> & out) const259 JSRope::copyLatin1CharsZ(ExclusiveContext* cx, ScopedJSFreePtr<Latin1Char>& out) const
260 {
261 return copyCharsInternal<Latin1Char>(cx, out, true);
262 }
263
264 bool
copyTwoByteCharsZ(ExclusiveContext * cx,ScopedJSFreePtr<char16_t> & out) const265 JSRope::copyTwoByteCharsZ(ExclusiveContext* cx, ScopedJSFreePtr<char16_t>& out) const
266 {
267 return copyCharsInternal<char16_t>(cx, out, true);
268 }
269
270 bool
copyLatin1Chars(ExclusiveContext * cx,ScopedJSFreePtr<Latin1Char> & out) const271 JSRope::copyLatin1Chars(ExclusiveContext* cx, ScopedJSFreePtr<Latin1Char>& out) const
272 {
273 return copyCharsInternal<Latin1Char>(cx, out, false);
274 }
275
276 bool
copyTwoByteChars(ExclusiveContext * cx,ScopedJSFreePtr<char16_t> & out) const277 JSRope::copyTwoByteChars(ExclusiveContext* cx, ScopedJSFreePtr<char16_t>& out) const
278 {
279 return copyCharsInternal<char16_t>(cx, out, false);
280 }
281
282 template <typename CharT>
283 bool
copyCharsInternal(ExclusiveContext * cx,ScopedJSFreePtr<CharT> & out,bool nullTerminate) const284 JSRope::copyCharsInternal(ExclusiveContext* cx, ScopedJSFreePtr<CharT>& out,
285 bool nullTerminate) const
286 {
287 /*
288 * Perform non-destructive post-order traversal of the rope, splatting
289 * each node's characters into a contiguous buffer.
290 */
291
292 size_t n = length();
293 if (cx)
294 out.reset(cx->pod_malloc<CharT>(n + 1));
295 else
296 out.reset(js_pod_malloc<CharT>(n + 1));
297
298 if (!out)
299 return false;
300
301 Vector<const JSString*, 8, SystemAllocPolicy> nodeStack;
302 const JSString* str = this;
303 CharT* pos = out;
304 while (true) {
305 if (str->isRope()) {
306 if (!nodeStack.append(str->asRope().rightChild()))
307 return false;
308 str = str->asRope().leftChild();
309 } else {
310 CopyChars(pos, str->asLinear());
311 pos += str->length();
312 if (nodeStack.empty())
313 break;
314 str = nodeStack.popCopy();
315 }
316 }
317
318 MOZ_ASSERT(pos == out + n);
319
320 if (nullTerminate)
321 out[n] = 0;
322
323 return true;
324 }
325
326 #ifdef DEBUG
327 void
dumpRepresentation(FILE * fp,int indent) const328 JSRope::dumpRepresentation(FILE* fp, int indent) const
329 {
330 dumpRepresentationHeader(fp, indent, "JSRope");
331 indent += 2;
332
333 fprintf(fp, "%*sleft: ", indent, "");
334 leftChild()->dumpRepresentation(fp, indent);
335
336 fprintf(fp, "%*sright: ", indent, "");
337 rightChild()->dumpRepresentation(fp, indent);
338 }
339 #endif
340
341 namespace js {
342
343 template <>
344 void
CopyChars(char16_t * dest,const JSLinearString & str)345 CopyChars(char16_t* dest, const JSLinearString& str)
346 {
347 AutoCheckCannotGC nogc;
348 if (str.hasTwoByteChars())
349 PodCopy(dest, str.twoByteChars(nogc), str.length());
350 else
351 CopyAndInflateChars(dest, str.latin1Chars(nogc), str.length());
352 }
353
354 template <>
355 void
CopyChars(Latin1Char * dest,const JSLinearString & str)356 CopyChars(Latin1Char* dest, const JSLinearString& str)
357 {
358 AutoCheckCannotGC nogc;
359 if (str.hasLatin1Chars()) {
360 PodCopy(dest, str.latin1Chars(nogc), str.length());
361 } else {
362 /*
363 * When we flatten a TwoByte rope, we turn child ropes (including Latin1
364 * ropes) into TwoByte dependent strings. If one of these strings is
365 * also part of another Latin1 rope tree, we can have a Latin1 rope with
366 * a TwoByte descendent and we end up here when we flatten it. Although
367 * the chars are stored as TwoByte, we know they must be in the Latin1
368 * range, so we can safely deflate here.
369 */
370 size_t len = str.length();
371 const char16_t* chars = str.twoByteChars(nogc);
372 for (size_t i = 0; i < len; i++) {
373 MOZ_ASSERT(chars[i] <= JSString::MAX_LATIN1_CHAR);
374 dest[i] = chars[i];
375 }
376 }
377 }
378
379 } /* namespace js */
380
381 template<JSRope::UsingBarrier b, typename CharT>
382 JSFlatString*
flattenInternal(ExclusiveContext * maybecx)383 JSRope::flattenInternal(ExclusiveContext* maybecx)
384 {
385 /*
386 * Consider the DAG of JSRopes rooted at this JSRope, with non-JSRopes as
387 * its leaves. Mutate the root JSRope into a JSExtensibleString containing
388 * the full flattened text that the root represents, and mutate all other
389 * JSRopes in the interior of the DAG into JSDependentStrings that refer to
390 * this new JSExtensibleString.
391 *
392 * If the leftmost leaf of our DAG is a JSExtensibleString, consider
393 * stealing its buffer for use in our new root, and transforming it into a
394 * JSDependentString too. Do not mutate any of the other leaves.
395 *
396 * Perform a depth-first dag traversal, splatting each node's characters
397 * into a contiguous buffer. Visit each rope node three times:
398 * 1. record position in the buffer and recurse into left child;
399 * 2. recurse into the right child;
400 * 3. transform the node into a dependent string.
401 * To avoid maintaining a stack, tree nodes are mutated to indicate how many
402 * times they have been visited. Since ropes can be dags, a node may be
403 * encountered multiple times during traversal. However, step 3 above leaves
404 * a valid dependent string, so everything works out.
405 *
406 * While ropes avoid all sorts of quadratic cases with string concatenation,
407 * they can't help when ropes are immediately flattened. One idiomatic case
408 * that we'd like to keep linear (and has traditionally been linear in SM
409 * and other JS engines) is:
410 *
411 * while (...) {
412 * s += ...
413 * s.flatten
414 * }
415 *
416 * Two behaviors accomplish this:
417 *
418 * - When the leftmost non-rope in the DAG we're flattening is a
419 * JSExtensibleString with sufficient capacity to hold the entire
420 * flattened string, we just flatten the DAG into its buffer. Then, when
421 * we transform the root of the DAG from a JSRope into a
422 * JSExtensibleString, we steal that buffer, and change the victim from a
423 * JSExtensibleString to a JSDependentString. In this case, the left-hand
424 * side of the string never needs to be copied.
425 *
426 * - Otherwise, we round up the total flattened size and create a fresh
427 * JSExtensibleString with that much capacity. If this in turn becomes the
428 * leftmost leaf of a subsequent flatten, we will hopefully be able to
429 * fill it, as in the case above.
430 *
431 * Note that, even though the code for creating JSDependentStrings avoids
432 * creating dependents of dependents, we can create that situation here: the
433 * JSExtensibleStrings we transform into JSDependentStrings might have
434 * JSDependentStrings pointing to them already. Stealing the buffer doesn't
435 * change its address, only its owning JSExtensibleString, so all chars()
436 * pointers in the JSDependentStrings are still valid.
437 */
438 const size_t wholeLength = length();
439 size_t wholeCapacity;
440 CharT* wholeChars;
441 JSString* str = this;
442 CharT* pos;
443
444 /*
445 * JSString::flattenData is a tagged pointer to the parent node.
446 * The tag indicates what to do when we return to the parent.
447 */
448 static const uintptr_t Tag_Mask = 0x3;
449 static const uintptr_t Tag_FinishNode = 0x0;
450 static const uintptr_t Tag_VisitRightChild = 0x1;
451
452 AutoCheckCannotGC nogc;
453
454 /* Find the left most string, containing the first string. */
455 JSRope* leftMostRope = this;
456 while (leftMostRope->leftChild()->isRope())
457 leftMostRope = &leftMostRope->leftChild()->asRope();
458
459 if (leftMostRope->leftChild()->isExtensible()) {
460 JSExtensibleString& left = leftMostRope->leftChild()->asExtensible();
461 size_t capacity = left.capacity();
462 if (capacity >= wholeLength && left.hasTwoByteChars() == IsSame<CharT, char16_t>::value) {
463 /*
464 * Simulate a left-most traversal from the root to leftMost->leftChild()
465 * via first_visit_node
466 */
467 MOZ_ASSERT(str->isRope());
468 while (str != leftMostRope) {
469 if (b == WithIncrementalBarrier) {
470 JSString::writeBarrierPre(str->d.s.u2.left);
471 JSString::writeBarrierPre(str->d.s.u3.right);
472 }
473 JSString* child = str->d.s.u2.left;
474 MOZ_ASSERT(child->isRope());
475 str->setNonInlineChars(left.nonInlineChars<CharT>(nogc));
476 child->d.u1.flattenData = uintptr_t(str) | Tag_VisitRightChild;
477 str = child;
478 }
479 if (b == WithIncrementalBarrier) {
480 JSString::writeBarrierPre(str->d.s.u2.left);
481 JSString::writeBarrierPre(str->d.s.u3.right);
482 }
483 str->setNonInlineChars(left.nonInlineChars<CharT>(nogc));
484 wholeCapacity = capacity;
485 wholeChars = const_cast<CharT*>(left.nonInlineChars<CharT>(nogc));
486 pos = wholeChars + left.d.u1.length;
487 JS_STATIC_ASSERT(!(EXTENSIBLE_FLAGS & DEPENDENT_FLAGS));
488 left.d.u1.flags ^= (EXTENSIBLE_FLAGS | DEPENDENT_FLAGS);
489 left.d.s.u3.base = (JSLinearString*)this; /* will be true on exit */
490 StringWriteBarrierPostRemove(maybecx, &left.d.s.u2.left);
491 StringWriteBarrierPost(maybecx, (JSString**)&left.d.s.u3.base);
492 goto visit_right_child;
493 }
494 }
495
496 if (!AllocChars(this, wholeLength, &wholeChars, &wholeCapacity)) {
497 if (maybecx)
498 ReportOutOfMemory(maybecx);
499 return nullptr;
500 }
501
502 pos = wholeChars;
503 first_visit_node: {
504 if (b == WithIncrementalBarrier) {
505 JSString::writeBarrierPre(str->d.s.u2.left);
506 JSString::writeBarrierPre(str->d.s.u3.right);
507 }
508
509 JSString& left = *str->d.s.u2.left;
510 str->setNonInlineChars(pos);
511 StringWriteBarrierPostRemove(maybecx, &str->d.s.u2.left);
512 if (left.isRope()) {
513 /* Return to this node when 'left' done, then goto visit_right_child. */
514 left.d.u1.flattenData = uintptr_t(str) | Tag_VisitRightChild;
515 str = &left;
516 goto first_visit_node;
517 }
518 CopyChars(pos, left.asLinear());
519 pos += left.length();
520 }
521 visit_right_child: {
522 JSString& right = *str->d.s.u3.right;
523 if (right.isRope()) {
524 /* Return to this node when 'right' done, then goto finish_node. */
525 right.d.u1.flattenData = uintptr_t(str) | Tag_FinishNode;
526 str = &right;
527 goto first_visit_node;
528 }
529 CopyChars(pos, right.asLinear());
530 pos += right.length();
531 }
532 finish_node: {
533 if (str == this) {
534 MOZ_ASSERT(pos == wholeChars + wholeLength);
535 *pos = '\0';
536 str->d.u1.length = wholeLength;
537 if (IsSame<CharT, char16_t>::value)
538 str->d.u1.flags = EXTENSIBLE_FLAGS;
539 else
540 str->d.u1.flags = EXTENSIBLE_FLAGS | LATIN1_CHARS_BIT;
541 str->setNonInlineChars(wholeChars);
542 str->d.s.u3.capacity = wholeCapacity;
543 StringWriteBarrierPostRemove(maybecx, &str->d.s.u2.left);
544 StringWriteBarrierPostRemove(maybecx, &str->d.s.u3.right);
545 return &this->asFlat();
546 }
547 uintptr_t flattenData = str->d.u1.flattenData;
548 if (IsSame<CharT, char16_t>::value)
549 str->d.u1.flags = DEPENDENT_FLAGS;
550 else
551 str->d.u1.flags = DEPENDENT_FLAGS | LATIN1_CHARS_BIT;
552 str->d.u1.length = pos - str->asLinear().nonInlineChars<CharT>(nogc);
553 str->d.s.u3.base = (JSLinearString*)this; /* will be true on exit */
554 StringWriteBarrierPost(maybecx, (JSString**)&str->d.s.u3.base);
555 str = (JSString*)(flattenData & ~Tag_Mask);
556 if ((flattenData & Tag_Mask) == Tag_VisitRightChild)
557 goto visit_right_child;
558 MOZ_ASSERT((flattenData & Tag_Mask) == Tag_FinishNode);
559 goto finish_node;
560 }
561 }
562
563 template<JSRope::UsingBarrier b>
564 JSFlatString*
flattenInternal(ExclusiveContext * maybecx)565 JSRope::flattenInternal(ExclusiveContext* maybecx)
566 {
567 if (hasTwoByteChars())
568 return flattenInternal<b, char16_t>(maybecx);
569 return flattenInternal<b, Latin1Char>(maybecx);
570 }
571
572 JSFlatString*
flatten(ExclusiveContext * maybecx)573 JSRope::flatten(ExclusiveContext* maybecx)
574 {
575 mozilla::Maybe<AutoSPSEntry> sps;
576 if (maybecx && maybecx->isJSContext())
577 sps.emplace(maybecx->asJSContext()->runtime(), "JSRope::flatten");
578
579 if (zone()->needsIncrementalBarrier())
580 return flattenInternal<WithIncrementalBarrier>(maybecx);
581 return flattenInternal<NoBarrier>(maybecx);
582 }
583
584 template <AllowGC allowGC>
585 static JSLinearString*
EnsureLinear(ExclusiveContext * cx,typename MaybeRooted<JSString *,allowGC>::HandleType string)586 EnsureLinear(ExclusiveContext* cx, typename MaybeRooted<JSString*, allowGC>::HandleType string)
587 {
588 JSLinearString* linear = string->ensureLinear(cx);
589 // Don't report an exception if GC is not allowed, just return nullptr.
590 if (!linear && !allowGC)
591 cx->recoverFromOutOfMemory();
592 return linear;
593 }
594
595 template <AllowGC allowGC>
596 JSString*
ConcatStrings(ExclusiveContext * cx,typename MaybeRooted<JSString *,allowGC>::HandleType left,typename MaybeRooted<JSString *,allowGC>::HandleType right)597 js::ConcatStrings(ExclusiveContext* cx,
598 typename MaybeRooted<JSString*, allowGC>::HandleType left,
599 typename MaybeRooted<JSString*, allowGC>::HandleType right)
600 {
601 MOZ_ASSERT_IF(!left->isAtom(), cx->isInsideCurrentZone(left));
602 MOZ_ASSERT_IF(!right->isAtom(), cx->isInsideCurrentZone(right));
603
604 size_t leftLen = left->length();
605 if (leftLen == 0)
606 return right;
607
608 size_t rightLen = right->length();
609 if (rightLen == 0)
610 return left;
611
612 size_t wholeLength = leftLen + rightLen;
613 if (MOZ_UNLIKELY(wholeLength > JSString::MAX_LENGTH)) {
614 // Don't report an exception if GC is not allowed, just return nullptr.
615 if (allowGC)
616 js::ReportAllocationOverflow(cx);
617 return nullptr;
618 }
619
620 bool isLatin1 = left->hasLatin1Chars() && right->hasLatin1Chars();
621 bool canUseInline = isLatin1
622 ? JSInlineString::lengthFits<Latin1Char>(wholeLength)
623 : JSInlineString::lengthFits<char16_t>(wholeLength);
624 if (canUseInline && cx->isJSContext()) {
625 Latin1Char* latin1Buf = nullptr; // initialize to silence GCC warning
626 char16_t* twoByteBuf = nullptr; // initialize to silence GCC warning
627 JSInlineString* str = isLatin1
628 ? AllocateInlineString<allowGC>(cx, wholeLength, &latin1Buf)
629 : AllocateInlineString<allowGC>(cx, wholeLength, &twoByteBuf);
630 if (!str)
631 return nullptr;
632
633 AutoCheckCannotGC nogc;
634 JSLinearString* leftLinear = EnsureLinear<allowGC>(cx, left);
635 if (!leftLinear)
636 return nullptr;
637 JSLinearString* rightLinear = EnsureLinear<allowGC>(cx, right);
638 if (!rightLinear)
639 return nullptr;
640
641 if (isLatin1) {
642 PodCopy(latin1Buf, leftLinear->latin1Chars(nogc), leftLen);
643 PodCopy(latin1Buf + leftLen, rightLinear->latin1Chars(nogc), rightLen);
644 latin1Buf[wholeLength] = 0;
645 } else {
646 if (leftLinear->hasTwoByteChars())
647 PodCopy(twoByteBuf, leftLinear->twoByteChars(nogc), leftLen);
648 else
649 CopyAndInflateChars(twoByteBuf, leftLinear->latin1Chars(nogc), leftLen);
650 if (rightLinear->hasTwoByteChars())
651 PodCopy(twoByteBuf + leftLen, rightLinear->twoByteChars(nogc), rightLen);
652 else
653 CopyAndInflateChars(twoByteBuf + leftLen, rightLinear->latin1Chars(nogc), rightLen);
654 twoByteBuf[wholeLength] = 0;
655 }
656
657 return str;
658 }
659
660 return JSRope::new_<allowGC>(cx, left, right, wholeLength);
661 }
662
663 template JSString*
664 js::ConcatStrings<CanGC>(ExclusiveContext* cx, HandleString left, HandleString right);
665
666 template JSString*
667 js::ConcatStrings<NoGC>(ExclusiveContext* cx, JSString* const& left, JSString* const& right);
668
669 template <typename CharT>
670 JSFlatString*
undependInternal(JSContext * cx)671 JSDependentString::undependInternal(JSContext* cx)
672 {
673 size_t n = length();
674 CharT* s = cx->pod_malloc<CharT>(n + 1);
675 if (!s)
676 return nullptr;
677
678 AutoCheckCannotGC nogc;
679 PodCopy(s, nonInlineChars<CharT>(nogc), n);
680 s[n] = '\0';
681 setNonInlineChars<CharT>(s);
682
683 /*
684 * Transform *this into an undepended string so 'base' will remain rooted
685 * for the benefit of any other dependent string that depends on *this.
686 */
687 if (IsSame<CharT, Latin1Char>::value)
688 d.u1.flags = UNDEPENDED_FLAGS | LATIN1_CHARS_BIT;
689 else
690 d.u1.flags = UNDEPENDED_FLAGS;
691
692 return &this->asFlat();
693 }
694
695 JSFlatString*
undepend(JSContext * cx)696 JSDependentString::undepend(JSContext* cx)
697 {
698 MOZ_ASSERT(JSString::isDependent());
699 return hasLatin1Chars()
700 ? undependInternal<Latin1Char>(cx)
701 : undependInternal<char16_t>(cx);
702 }
703
704 #ifdef DEBUG
705 void
dumpRepresentation(FILE * fp,int indent) const706 JSDependentString::dumpRepresentation(FILE* fp, int indent) const
707 {
708 dumpRepresentationHeader(fp, indent, "JSDependentString");
709 indent += 2;
710
711 if (mozilla::Maybe<size_t> offset = baseOffset())
712 fprintf(fp, "%*soffset: %" PRIuSIZE "\n", indent, "", *offset);
713
714 fprintf(fp, "%*sbase: ", indent, "");
715 base()->dumpRepresentation(fp, indent);
716 }
717 #endif
718
719 template <typename CharT>
720 /* static */ bool
isIndexSlow(const CharT * s,size_t length,uint32_t * indexp)721 JSFlatString::isIndexSlow(const CharT* s, size_t length, uint32_t* indexp)
722 {
723 CharT ch = *s;
724
725 if (!JS7_ISDEC(ch))
726 return false;
727
728 if (length > UINT32_CHAR_BUFFER_LENGTH)
729 return false;
730
731 /*
732 * Make sure to account for the '\0' at the end of characters, dereferenced
733 * in the loop below.
734 */
735 RangedPtr<const CharT> cp(s, length + 1);
736 const RangedPtr<const CharT> end(s + length, s, length + 1);
737
738 uint32_t index = JS7_UNDEC(*cp++);
739 uint32_t oldIndex = 0;
740 uint32_t c = 0;
741
742 if (index != 0) {
743 while (JS7_ISDEC(*cp)) {
744 oldIndex = index;
745 c = JS7_UNDEC(*cp);
746 index = 10 * index + c;
747 cp++;
748 }
749 }
750
751 /* It's not an element if there are characters after the number. */
752 if (cp != end)
753 return false;
754
755 /*
756 * Look out for "4294967296" and larger-number strings that fit in
757 * UINT32_CHAR_BUFFER_LENGTH: only unsigned 32-bit integers shall pass.
758 */
759 if (oldIndex < UINT32_MAX / 10 || (oldIndex == UINT32_MAX / 10 && c <= (UINT32_MAX % 10))) {
760 *indexp = index;
761 return true;
762 }
763
764 return false;
765 }
766
767 template bool
768 JSFlatString::isIndexSlow(const Latin1Char* s, size_t length, uint32_t* indexp);
769
770 template bool
771 JSFlatString::isIndexSlow(const char16_t* s, size_t length, uint32_t* indexp);
772
773 /*
774 * Set up some tools to make it easier to generate large tables. After constant
775 * folding, for each n, Rn(0) is the comma-separated list R(0), R(1), ..., R(2^n-1).
776 * Similary, Rn(k) (for any k and n) generates the list R(k), R(k+1), ..., R(k+2^n-1).
777 * To use this, define R appropriately, then use Rn(0) (for some value of n), then
778 * undefine R.
779 */
780 #define R2(n) R(n), R((n) + (1 << 0)), R((n) + (2 << 0)), R((n) + (3 << 0))
781 #define R4(n) R2(n), R2((n) + (1 << 2)), R2((n) + (2 << 2)), R2((n) + (3 << 2))
782 #define R6(n) R4(n), R4((n) + (1 << 4)), R4((n) + (2 << 4)), R4((n) + (3 << 4))
783 #define R7(n) R6(n), R6((n) + (1 << 6))
784
785 /*
786 * This is used when we generate our table of short strings, so the compiler is
787 * happier if we use |c| as few times as possible.
788 */
789 #define FROM_SMALL_CHAR(c) Latin1Char((c) + ((c) < 10 ? '0' : \
790 (c) < 36 ? 'a' - 10 : \
791 'A' - 36))
792
793 /*
794 * Declare length-2 strings. We only store strings where both characters are
795 * alphanumeric. The lower 10 short chars are the numerals, the next 26 are
796 * the lowercase letters, and the next 26 are the uppercase letters.
797 */
798 #define TO_SMALL_CHAR(c) ((c) >= '0' && (c) <= '9' ? (c) - '0' : \
799 (c) >= 'a' && (c) <= 'z' ? (c) - 'a' + 10 : \
800 (c) >= 'A' && (c) <= 'Z' ? (c) - 'A' + 36 : \
801 StaticStrings::INVALID_SMALL_CHAR)
802
803 #define R TO_SMALL_CHAR
804 const StaticStrings::SmallChar StaticStrings::toSmallChar[] = { R7(0) };
805 #undef R
806
807 #undef R2
808 #undef R4
809 #undef R6
810 #undef R7
811
812 bool
init(JSContext * cx)813 StaticStrings::init(JSContext* cx)
814 {
815 AutoLockForExclusiveAccess lock(cx);
816 AutoCompartment ac(cx, cx->runtime()->atomsCompartment(lock), &lock);
817
818 static_assert(UNIT_STATIC_LIMIT - 1 <= JSString::MAX_LATIN1_CHAR,
819 "Unit strings must fit in Latin1Char.");
820
821 using Latin1Range = mozilla::Range<const Latin1Char>;
822
823 for (uint32_t i = 0; i < UNIT_STATIC_LIMIT; i++) {
824 Latin1Char buffer[] = { Latin1Char(i), '\0' };
825 JSFlatString* s = NewInlineString<NoGC>(cx, Latin1Range(buffer, 1));
826 if (!s)
827 return false;
828 HashNumber hash = mozilla::HashString(buffer, 1);
829 unitStaticTable[i] = s->morphAtomizedStringIntoPermanentAtom(hash);
830 }
831
832 for (uint32_t i = 0; i < NUM_SMALL_CHARS * NUM_SMALL_CHARS; i++) {
833 Latin1Char buffer[] = { FROM_SMALL_CHAR(i >> 6), FROM_SMALL_CHAR(i & 0x3F), '\0' };
834 JSFlatString* s = NewInlineString<NoGC>(cx, Latin1Range(buffer, 2));
835 if (!s)
836 return false;
837 HashNumber hash = mozilla::HashString(buffer, 2);
838 length2StaticTable[i] = s->morphAtomizedStringIntoPermanentAtom(hash);
839 }
840
841 for (uint32_t i = 0; i < INT_STATIC_LIMIT; i++) {
842 if (i < 10) {
843 intStaticTable[i] = unitStaticTable[i + '0'];
844 } else if (i < 100) {
845 size_t index = ((size_t)TO_SMALL_CHAR((i / 10) + '0') << 6) +
846 TO_SMALL_CHAR((i % 10) + '0');
847 intStaticTable[i] = length2StaticTable[index];
848 } else {
849 Latin1Char buffer[] = { Latin1Char('0' + (i / 100)),
850 Latin1Char('0' + ((i / 10) % 10)),
851 Latin1Char('0' + (i % 10)),
852 '\0' };
853 JSFlatString* s = NewInlineString<NoGC>(cx, Latin1Range(buffer, 3));
854 if (!s)
855 return false;
856 HashNumber hash = mozilla::HashString(buffer, 3);
857 intStaticTable[i] = s->morphAtomizedStringIntoPermanentAtom(hash);
858 }
859 }
860
861 return true;
862 }
863
864 void
trace(JSTracer * trc)865 StaticStrings::trace(JSTracer* trc)
866 {
867 /* These strings never change, so barriers are not needed. */
868
869 for (uint32_t i = 0; i < UNIT_STATIC_LIMIT; i++)
870 TraceProcessGlobalRoot(trc, unitStaticTable[i], "unit-static-string");
871
872 for (uint32_t i = 0; i < NUM_SMALL_CHARS * NUM_SMALL_CHARS; i++)
873 TraceProcessGlobalRoot(trc, length2StaticTable[i], "length2-static-string");
874
875 /* This may mark some strings more than once, but so be it. */
876 for (uint32_t i = 0; i < INT_STATIC_LIMIT; i++)
877 TraceProcessGlobalRoot(trc, intStaticTable[i], "int-static-string");
878 }
879
880 template <typename CharT>
881 /* static */ bool
isStatic(const CharT * chars,size_t length)882 StaticStrings::isStatic(const CharT* chars, size_t length)
883 {
884 switch (length) {
885 case 1: {
886 char16_t c = chars[0];
887 return c < UNIT_STATIC_LIMIT;
888 }
889 case 2:
890 return fitsInSmallChar(chars[0]) && fitsInSmallChar(chars[1]);
891 case 3:
892 if ('1' <= chars[0] && chars[0] <= '9' &&
893 '0' <= chars[1] && chars[1] <= '9' &&
894 '0' <= chars[2] && chars[2] <= '9') {
895 int i = (chars[0] - '0') * 100 +
896 (chars[1] - '0') * 10 +
897 (chars[2] - '0');
898
899 return unsigned(i) < INT_STATIC_LIMIT;
900 }
901 return false;
902 default:
903 return false;
904 }
905 }
906
907 /* static */ bool
isStatic(JSAtom * atom)908 StaticStrings::isStatic(JSAtom* atom)
909 {
910 AutoCheckCannotGC nogc;
911 return atom->hasLatin1Chars()
912 ? isStatic(atom->latin1Chars(nogc), atom->length())
913 : isStatic(atom->twoByteChars(nogc), atom->length());
914 }
915
916 bool
init(JSContext * cx,JSString * s)917 AutoStableStringChars::init(JSContext* cx, JSString* s)
918 {
919 RootedLinearString linearString(cx, s->ensureLinear(cx));
920 if (!linearString)
921 return false;
922
923 MOZ_ASSERT(state_ == Uninitialized);
924
925 if (linearString->isExternal() && !linearString->ensureFlat(cx))
926 return false;
927
928 // If the chars are inline then we need to copy them since they may be moved
929 // by a compacting GC.
930 if (baseIsInline(linearString)) {
931 return linearString->hasTwoByteChars() ? copyTwoByteChars(cx, linearString)
932 : copyLatin1Chars(cx, linearString);
933 }
934
935 if (linearString->hasLatin1Chars()) {
936 state_ = Latin1;
937 latin1Chars_ = linearString->rawLatin1Chars();
938 } else {
939 state_ = TwoByte;
940 twoByteChars_ = linearString->rawTwoByteChars();
941 }
942
943 s_ = linearString;
944 return true;
945 }
946
947 bool
initTwoByte(JSContext * cx,JSString * s)948 AutoStableStringChars::initTwoByte(JSContext* cx, JSString* s)
949 {
950 RootedLinearString linearString(cx, s->ensureLinear(cx));
951 if (!linearString)
952 return false;
953
954 MOZ_ASSERT(state_ == Uninitialized);
955
956 if (linearString->hasLatin1Chars())
957 return copyAndInflateLatin1Chars(cx, linearString);
958
959 if (linearString->isExternal() && !linearString->ensureFlat(cx))
960 return false;
961
962 // If the chars are inline then we need to copy them since they may be moved
963 // by a compacting GC.
964 if (baseIsInline(linearString))
965 return copyTwoByteChars(cx, linearString);
966
967 state_ = TwoByte;
968 twoByteChars_ = linearString->rawTwoByteChars();
969 s_ = linearString;
970 return true;
971 }
972
baseIsInline(HandleLinearString linearString)973 bool AutoStableStringChars::baseIsInline(HandleLinearString linearString)
974 {
975 JSString* base = linearString;
976 while (base->isDependent())
977 base = base->asDependent().base();
978 return base->isInline();
979 }
980
981 template <typename T>
982 T*
allocOwnChars(JSContext * cx,size_t count)983 AutoStableStringChars::allocOwnChars(JSContext* cx, size_t count)
984 {
985 static_assert(
986 InlineCapacity >= sizeof(JS::Latin1Char) * (JSFatInlineString::MAX_LENGTH_LATIN1 + 1) &&
987 InlineCapacity >= sizeof(char16_t) * (JSFatInlineString::MAX_LENGTH_TWO_BYTE + 1),
988 "InlineCapacity too small to hold fat inline strings");
989
990 static_assert((JSString::MAX_LENGTH & mozilla::tl::MulOverflowMask<sizeof(T)>::value) == 0,
991 "Size calculation can overflow");
992 MOZ_ASSERT(count <= (JSString::MAX_LENGTH + 1));
993 size_t size = sizeof(T) * count;
994
995 ownChars_.emplace(cx);
996 if (!ownChars_->resize(size)) {
997 ownChars_.reset();
998 return nullptr;
999 }
1000
1001 return reinterpret_cast<T*>(ownChars_->begin());
1002 }
1003
1004 bool
copyAndInflateLatin1Chars(JSContext * cx,HandleLinearString linearString)1005 AutoStableStringChars::copyAndInflateLatin1Chars(JSContext* cx, HandleLinearString linearString)
1006 {
1007 char16_t* chars = allocOwnChars<char16_t>(cx, linearString->length() + 1);
1008 if (!chars)
1009 return false;
1010
1011 CopyAndInflateChars(chars, linearString->rawLatin1Chars(),
1012 linearString->length());
1013 chars[linearString->length()] = 0;
1014
1015 state_ = TwoByte;
1016 twoByteChars_ = chars;
1017 s_ = linearString;
1018 return true;
1019 }
1020
1021 bool
copyLatin1Chars(JSContext * cx,HandleLinearString linearString)1022 AutoStableStringChars::copyLatin1Chars(JSContext* cx, HandleLinearString linearString)
1023 {
1024 size_t length = linearString->length();
1025 JS::Latin1Char* chars = allocOwnChars<JS::Latin1Char>(cx, length + 1);
1026 if (!chars)
1027 return false;
1028
1029 PodCopy(chars, linearString->rawLatin1Chars(), length);
1030 chars[length] = 0;
1031
1032 state_ = Latin1;
1033 latin1Chars_ = chars;
1034 s_ = linearString;
1035 return true;
1036 }
1037
1038 bool
copyTwoByteChars(JSContext * cx,HandleLinearString linearString)1039 AutoStableStringChars::copyTwoByteChars(JSContext* cx, HandleLinearString linearString)
1040 {
1041 size_t length = linearString->length();
1042 char16_t* chars = allocOwnChars<char16_t>(cx, length + 1);
1043 if (!chars)
1044 return false;
1045
1046 PodCopy(chars, linearString->rawTwoByteChars(), length);
1047 chars[length] = 0;
1048
1049 state_ = TwoByte;
1050 twoByteChars_ = chars;
1051 s_ = linearString;
1052 return true;
1053 }
1054
1055 JSFlatString*
ensureFlat(JSContext * cx)1056 JSString::ensureFlat(JSContext* cx)
1057 {
1058 if (isFlat())
1059 return &asFlat();
1060 if (isDependent())
1061 return asDependent().undepend(cx);
1062 if (isRope())
1063 return asRope().flatten(cx);
1064 return asExternal().ensureFlat(cx);
1065 }
1066
1067 JSFlatString*
ensureFlat(JSContext * cx)1068 JSExternalString::ensureFlat(JSContext* cx)
1069 {
1070 MOZ_ASSERT(hasTwoByteChars());
1071
1072 size_t n = length();
1073 char16_t* s = cx->pod_malloc<char16_t>(n + 1);
1074 if (!s)
1075 return nullptr;
1076
1077 // Copy the chars before finalizing the string.
1078 {
1079 AutoCheckCannotGC nogc;
1080 PodCopy(s, nonInlineChars<char16_t>(nogc), n);
1081 s[n] = '\0';
1082 }
1083
1084 // Release the external chars.
1085 finalize(cx->runtime()->defaultFreeOp());
1086
1087 // Transform the string into a non-external, flat string.
1088 setNonInlineChars<char16_t>(s);
1089 d.u1.flags = FLAT_BIT;
1090
1091 return &this->asFlat();
1092 }
1093
1094 #ifdef DEBUG
1095 void
dump(FILE * fp)1096 JSAtom::dump(FILE* fp)
1097 {
1098 fprintf(fp, "JSAtom* (%p) = ", (void*) this);
1099 this->JSString::dump(fp);
1100 }
1101
1102 void
dump()1103 JSAtom::dump()
1104 {
1105 dump(stderr);
1106 }
1107
1108 void
dumpRepresentation(FILE * fp,int indent) const1109 JSExternalString::dumpRepresentation(FILE* fp, int indent) const
1110 {
1111 dumpRepresentationHeader(fp, indent, "JSExternalString");
1112 indent += 2;
1113
1114 fprintf(fp, "%*sfinalizer: ((JSStringFinalizer*) %p)\n", indent, "", externalFinalizer());
1115 fprintf(fp, "%*sbase: ", indent, "");
1116 base()->dumpRepresentation(fp, indent);
1117 }
1118 #endif /* DEBUG */
1119
1120 JSLinearString*
NewDependentString(JSContext * cx,JSString * baseArg,size_t start,size_t length)1121 js::NewDependentString(JSContext* cx, JSString* baseArg, size_t start, size_t length)
1122 {
1123 if (length == 0)
1124 return cx->emptyString();
1125
1126 JSLinearString* base = baseArg->ensureLinear(cx);
1127 if (!base)
1128 return nullptr;
1129
1130 if (start == 0 && length == base->length())
1131 return base;
1132
1133 if (base->hasTwoByteChars()) {
1134 AutoCheckCannotGC nogc;
1135 const char16_t* chars = base->twoByteChars(nogc) + start;
1136 if (JSLinearString* staticStr = cx->staticStrings().lookup(chars, length))
1137 return staticStr;
1138 } else {
1139 AutoCheckCannotGC nogc;
1140 const Latin1Char* chars = base->latin1Chars(nogc) + start;
1141 if (JSLinearString* staticStr = cx->staticStrings().lookup(chars, length))
1142 return staticStr;
1143 }
1144
1145 return JSDependentString::new_(cx, base, start, length);
1146 }
1147
1148 static bool
CanStoreCharsAsLatin1(const char16_t * s,size_t length)1149 CanStoreCharsAsLatin1(const char16_t* s, size_t length)
1150 {
1151 for (const char16_t* end = s + length; s < end; ++s) {
1152 if (*s > JSString::MAX_LATIN1_CHAR)
1153 return false;
1154 }
1155
1156 return true;
1157 }
1158
1159 static bool
CanStoreCharsAsLatin1(const Latin1Char * s,size_t length)1160 CanStoreCharsAsLatin1(const Latin1Char* s, size_t length)
1161 {
1162 MOZ_CRASH("Shouldn't be called for Latin1 chars");
1163 }
1164
1165 template <AllowGC allowGC>
1166 static MOZ_ALWAYS_INLINE JSInlineString*
NewInlineStringDeflated(ExclusiveContext * cx,mozilla::Range<const char16_t> chars)1167 NewInlineStringDeflated(ExclusiveContext* cx, mozilla::Range<const char16_t> chars)
1168 {
1169 size_t len = chars.length();
1170 Latin1Char* storage;
1171 JSInlineString* str = AllocateInlineString<allowGC>(cx, len, &storage);
1172 if (!str)
1173 return nullptr;
1174
1175 for (size_t i = 0; i < len; i++) {
1176 MOZ_ASSERT(chars[i] <= JSString::MAX_LATIN1_CHAR);
1177 storage[i] = Latin1Char(chars[i]);
1178 }
1179 storage[len] = '\0';
1180 return str;
1181 }
1182
1183 template <typename CharT>
1184 static MOZ_ALWAYS_INLINE JSFlatString*
TryEmptyOrStaticString(ExclusiveContext * cx,const CharT * chars,size_t n)1185 TryEmptyOrStaticString(ExclusiveContext* cx, const CharT* chars, size_t n)
1186 {
1187 // Measurements on popular websites indicate empty strings are pretty common
1188 // and most strings with length 1 or 2 are in the StaticStrings table. For
1189 // length 3 strings that's only about 1%, so we check n <= 2.
1190 if (n <= 2) {
1191 if (n == 0)
1192 return cx->emptyString();
1193
1194 if (JSFlatString* str = cx->staticStrings().lookup(chars, n))
1195 return str;
1196 }
1197
1198 return nullptr;
1199 }
1200
1201 template <AllowGC allowGC>
1202 static JSFlatString*
NewStringDeflated(ExclusiveContext * cx,const char16_t * s,size_t n)1203 NewStringDeflated(ExclusiveContext* cx, const char16_t* s, size_t n)
1204 {
1205 if (JSFlatString* str = TryEmptyOrStaticString(cx, s, n))
1206 return str;
1207
1208 if (JSInlineString::lengthFits<Latin1Char>(n))
1209 return NewInlineStringDeflated<allowGC>(cx, mozilla::Range<const char16_t>(s, n));
1210
1211 ScopedJSFreePtr<Latin1Char> news(cx->pod_malloc<Latin1Char>(n + 1));
1212 if (!news)
1213 return nullptr;
1214
1215 for (size_t i = 0; i < n; i++) {
1216 MOZ_ASSERT(s[i] <= JSString::MAX_LATIN1_CHAR);
1217 news.get()[i] = Latin1Char(s[i]);
1218 }
1219 news[n] = '\0';
1220
1221 JSFlatString* str = JSFlatString::new_<allowGC>(cx, news.get(), n);
1222 if (!str)
1223 return nullptr;
1224
1225 news.forget();
1226 return str;
1227 }
1228
1229 template <AllowGC allowGC>
1230 static JSFlatString*
NewStringDeflated(ExclusiveContext * cx,const Latin1Char * s,size_t n)1231 NewStringDeflated(ExclusiveContext* cx, const Latin1Char* s, size_t n)
1232 {
1233 MOZ_CRASH("Shouldn't be called for Latin1 chars");
1234 }
1235
1236 template <AllowGC allowGC, typename CharT>
1237 JSFlatString*
NewStringDontDeflate(ExclusiveContext * cx,CharT * chars,size_t length)1238 js::NewStringDontDeflate(ExclusiveContext* cx, CharT* chars, size_t length)
1239 {
1240 if (JSFlatString* str = TryEmptyOrStaticString(cx, chars, length)) {
1241 // Free |chars| because we're taking possession of it, but it's no
1242 // longer needed because we use the static string instead.
1243 js_free(chars);
1244 return str;
1245 }
1246
1247 if (JSInlineString::lengthFits<CharT>(length)) {
1248 JSInlineString* str =
1249 NewInlineString<allowGC>(cx, mozilla::Range<const CharT>(chars, length));
1250 if (!str)
1251 return nullptr;
1252
1253 js_free(chars);
1254 return str;
1255 }
1256
1257 return JSFlatString::new_<allowGC>(cx, chars, length);
1258 }
1259
1260 template JSFlatString*
1261 js::NewStringDontDeflate<CanGC>(ExclusiveContext* cx, char16_t* chars, size_t length);
1262
1263 template JSFlatString*
1264 js::NewStringDontDeflate<NoGC>(ExclusiveContext* cx, char16_t* chars, size_t length);
1265
1266 template JSFlatString*
1267 js::NewStringDontDeflate<CanGC>(ExclusiveContext* cx, Latin1Char* chars, size_t length);
1268
1269 template JSFlatString*
1270 js::NewStringDontDeflate<NoGC>(ExclusiveContext* cx, Latin1Char* chars, size_t length);
1271
1272 template <AllowGC allowGC, typename CharT>
1273 JSFlatString*
NewString(ExclusiveContext * cx,CharT * chars,size_t length)1274 js::NewString(ExclusiveContext* cx, CharT* chars, size_t length)
1275 {
1276 if (IsSame<CharT, char16_t>::value && CanStoreCharsAsLatin1(chars, length)) {
1277 JSFlatString* s = NewStringDeflated<allowGC>(cx, chars, length);
1278 if (!s)
1279 return nullptr;
1280
1281 // Free |chars| because we're taking possession of it but not using it.
1282 js_free(chars);
1283 return s;
1284 }
1285
1286 return NewStringDontDeflate<allowGC>(cx, chars, length);
1287 }
1288
1289 template JSFlatString*
1290 js::NewString<CanGC>(ExclusiveContext* cx, char16_t* chars, size_t length);
1291
1292 template JSFlatString*
1293 js::NewString<NoGC>(ExclusiveContext* cx, char16_t* chars, size_t length);
1294
1295 template JSFlatString*
1296 js::NewString<CanGC>(ExclusiveContext* cx, Latin1Char* chars, size_t length);
1297
1298 template JSFlatString*
1299 js::NewString<NoGC>(ExclusiveContext* cx, Latin1Char* chars, size_t length);
1300
1301 namespace js {
1302
1303 template <AllowGC allowGC, typename CharT>
1304 JSFlatString*
NewStringCopyNDontDeflate(ExclusiveContext * cx,const CharT * s,size_t n)1305 NewStringCopyNDontDeflate(ExclusiveContext* cx, const CharT* s, size_t n)
1306 {
1307 if (JSFlatString* str = TryEmptyOrStaticString(cx, s, n))
1308 return str;
1309
1310 if (JSInlineString::lengthFits<CharT>(n))
1311 return NewInlineString<allowGC>(cx, mozilla::Range<const CharT>(s, n));
1312
1313 ScopedJSFreePtr<CharT> news(cx->pod_malloc<CharT>(n + 1));
1314 if (!news) {
1315 if (!allowGC)
1316 cx->recoverFromOutOfMemory();
1317 return nullptr;
1318 }
1319
1320 PodCopy(news.get(), s, n);
1321 news[n] = 0;
1322
1323 JSFlatString* str = JSFlatString::new_<allowGC>(cx, news.get(), n);
1324 if (!str)
1325 return nullptr;
1326
1327 news.forget();
1328 return str;
1329 }
1330
1331 template JSFlatString*
1332 NewStringCopyNDontDeflate<CanGC>(ExclusiveContext* cx, const char16_t* s, size_t n);
1333
1334 template JSFlatString*
1335 NewStringCopyNDontDeflate<NoGC>(ExclusiveContext* cx, const char16_t* s, size_t n);
1336
1337 template JSFlatString*
1338 NewStringCopyNDontDeflate<CanGC>(ExclusiveContext* cx, const Latin1Char* s, size_t n);
1339
1340 template JSFlatString*
1341 NewStringCopyNDontDeflate<NoGC>(ExclusiveContext* cx, const Latin1Char* s, size_t n);
1342
1343 JSFlatString*
NewLatin1StringZ(ExclusiveContext * cx,UniqueChars chars)1344 NewLatin1StringZ(ExclusiveContext* cx, UniqueChars chars)
1345 {
1346 JSFlatString* str = NewString<CanGC>(cx, (Latin1Char*)chars.get(), strlen(chars.get()));
1347 if (!str)
1348 return nullptr;
1349
1350 mozilla::Unused << chars.release();
1351 return str;
1352 }
1353
1354 template <AllowGC allowGC, typename CharT>
1355 JSFlatString*
NewStringCopyN(ExclusiveContext * cx,const CharT * s,size_t n)1356 NewStringCopyN(ExclusiveContext* cx, const CharT* s, size_t n)
1357 {
1358 if (IsSame<CharT, char16_t>::value && CanStoreCharsAsLatin1(s, n))
1359 return NewStringDeflated<allowGC>(cx, s, n);
1360
1361 return NewStringCopyNDontDeflate<allowGC>(cx, s, n);
1362 }
1363
1364 template JSFlatString*
1365 NewStringCopyN<CanGC>(ExclusiveContext* cx, const char16_t* s, size_t n);
1366
1367 template JSFlatString*
1368 NewStringCopyN<NoGC>(ExclusiveContext* cx, const char16_t* s, size_t n);
1369
1370 template JSFlatString*
1371 NewStringCopyN<CanGC>(ExclusiveContext* cx, const Latin1Char* s, size_t n);
1372
1373 template JSFlatString*
1374 NewStringCopyN<NoGC>(ExclusiveContext* cx, const Latin1Char* s, size_t n);
1375
1376 template <js::AllowGC allowGC>
1377 JSFlatString*
NewStringCopyUTF8N(JSContext * cx,const JS::UTF8Chars utf8)1378 NewStringCopyUTF8N(JSContext* cx, const JS::UTF8Chars utf8)
1379 {
1380 JS::SmallestEncoding encoding = JS::FindSmallestEncoding(utf8);
1381 if (encoding == JS::SmallestEncoding::ASCII)
1382 return NewStringCopyN<allowGC>(cx, utf8.begin().get(), utf8.length());
1383
1384 size_t length;
1385 if (encoding == JS::SmallestEncoding::Latin1) {
1386 Latin1Char* latin1 = UTF8CharsToNewLatin1CharsZ(cx, utf8, &length).get();
1387 if (!latin1)
1388 return nullptr;
1389
1390 JSFlatString* result = NewString<allowGC>(cx, latin1, length);
1391 if (!result)
1392 js_free((void*)latin1);
1393 return result;
1394 }
1395
1396 MOZ_ASSERT(encoding == JS::SmallestEncoding::UTF16);
1397
1398 char16_t* utf16 = UTF8CharsToNewTwoByteCharsZ(cx, utf8, &length).get();
1399 if (!utf16)
1400 return nullptr;
1401
1402 JSFlatString* result = NewString<allowGC>(cx, utf16, length);
1403 if (!result)
1404 js_free((void*)utf16);
1405 return result;
1406 }
1407
1408 template JSFlatString*
1409 NewStringCopyUTF8N<CanGC>(JSContext* cx, const JS::UTF8Chars utf8);
1410
1411 } /* namespace js */
1412
1413 #ifdef DEBUG
1414 void
dumpRepresentation(FILE * fp,int indent) const1415 JSExtensibleString::dumpRepresentation(FILE* fp, int indent) const
1416 {
1417 dumpRepresentationHeader(fp, indent, "JSExtensibleString");
1418 indent += 2;
1419
1420 fprintf(fp, "%*scapacity: %" PRIuSIZE "\n", indent, "", capacity());
1421 dumpRepresentationChars(fp, indent);
1422 }
1423
1424 void
dumpRepresentation(FILE * fp,int indent) const1425 JSInlineString::dumpRepresentation(FILE* fp, int indent) const
1426 {
1427 dumpRepresentationHeader(fp, indent,
1428 isFatInline() ? "JSFatInlineString" : "JSThinInlineString");
1429 indent += 2;
1430
1431 dumpRepresentationChars(fp, indent);
1432 }
1433
1434 void
dumpRepresentation(FILE * fp,int indent) const1435 JSFlatString::dumpRepresentation(FILE* fp, int indent) const
1436 {
1437 dumpRepresentationHeader(fp, indent, "JSFlatString");
1438 indent += 2;
1439
1440 dumpRepresentationChars(fp, indent);
1441 }
1442 #endif
1443