The Tor Browser / file comparison

comparison: js/src/vm/String.h

js/src/vm/String.h

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:7f0501605a83
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 #ifndef vm_String_h
8 #define vm_String_h
9
10 #include "mozilla/MemoryReporting.h"
11 #include "mozilla/PodOperations.h"
12
13 #include "jsapi.h"
14 #include "jsfriendapi.h"
15 #include "jsstr.h"
16
17 #include "gc/Barrier.h"
18 #include "gc/Heap.h"
19 #include "gc/Marking.h"
20 #include "gc/Rooting.h"
21 #include "js/CharacterEncoding.h"
22 #include "js/RootingAPI.h"
23
24 class JSDependentString;
25 class JSExtensibleString;
26 class JSExternalString;
27 class JSInlineString;
28 class JSRope;
29
30 namespace js {
31
32 class StaticStrings;
33 class PropertyName;
34
35 /* The buffer length required to contain any unsigned 32-bit integer. */
36 static const size_t UINT32_CHAR_BUFFER_LENGTH = sizeof("4294967295") - 1;
37
38 } /* namespace js */
39
40 /*
41 * JavaScript strings
42 *
43 * Conceptually, a JS string is just an array of chars and a length. This array
44 * of chars may or may not be null-terminated and, if it is, the null character
45 * is not included in the length.
46 *
47 * To improve performance of common operations, the following optimizations are
48 * made which affect the engine's representation of strings:
49 *
50 * - The plain vanilla representation is a "flat" string which consists of a
51 * string header in the GC heap and a malloc'd null terminated char array.
52 *
53 * - To avoid copying a substring of an existing "base" string , a "dependent"
54 * string (JSDependentString) can be created which points into the base
55 * string's char array.
56 *
57 * - To avoid O(n^2) char buffer copying, a "rope" node (JSRope) can be created
58 * to represent a delayed string concatenation. Concatenation (called
59 * flattening) is performed if and when a linear char array is requested. In
60 * general, ropes form a binary dag whose internal nodes are JSRope string
61 * headers with no associated char array and whose leaf nodes are either flat
62 * or dependent strings.
63 *
64 * - To avoid copying the left-hand side when flattening, the left-hand side's
65 * buffer may be grown to make space for a copy of the right-hand side (see
66 * comment in JSString::flatten). This optimization requires that there are
67 * no external pointers into the char array. We conservatively maintain this
68 * property via a flat string's "extensible" property.
69 *
70 * - To avoid allocating small char arrays, short strings can be stored inline
71 * in the string header (JSInlineString). To increase the max size of such
72 * inline strings, larger string headers can be used (JSFatInlineString).
73 *
74 * - To avoid comparing O(n) string equality comparison, strings can be
75 * canonicalized to "atoms" (JSAtom) such that there is a single atom with a
76 * given (length,chars).
77 *
78 * - To avoid copying all strings created through the JSAPI, an "external"
79 * string (JSExternalString) can be created whose chars are managed by the
80 * JSAPI client.
81 *
82 * Although all strings share the same basic memory layout, we can conceptually
83 * arrange them into a hierarchy of operations/invariants and represent this
84 * hierarchy in C++ with classes:
85 *
86 * C++ type operations+fields / invariants+properties
87 * ========================== =========================================
88 * JSString (abstract) getCharsZ, getChars, length / -
89 * | \
90 * | JSRope leftChild, rightChild / -
91 * |
92 * JSLinearString (abstract) chars / might be null-terminated
93 * | \
94 * | JSDependentString base / -
95 * |
96 * JSFlatString - / null terminated
97 * | |
98 * | +-- JSExternalString - / char array memory managed by embedding
99 * | |
100 * | +-- JSExtensibleString capacity / no external pointers into char array
101 * | |
102 * | +-- JSUndependedString original dependent base / -
103 * | |
104 * | +-- JSInlineString - / chars stored in header
105 * | \
106 * | JSFatInlineString - / header is fat
107 * |
108 * JSAtom - / string equality === pointer equality
109 * |
110 * js::PropertyName - / chars don't contain an index (uint32_t)
111 *
112 * Classes marked with (abstract) above are not literally C++ Abstract Base
113 * Classes (since there are no virtual functions, pure or not, in this
114 * hierarchy), but have the same meaning: there are no strings with this type as
115 * its most-derived type.
116 *
117 * Atoms can additionally be permanent, i.e. unable to be collected, and can
118 * be combined with other string types to create additional most-derived types
119 * that satisfy the invariants of more than one of the abovementioned
120 * most-derived types:
121 * - InlineAtom = JSInlineString + JSAtom (atom with inline chars)
122 * - FatInlineAtom = JSFatInlineString + JSAtom (atom with (more) inline chars)
123 *
124 * Derived string types can be queried from ancestor types via isX() and
125 * retrieved with asX() debug-only-checked casts.
126 *
127 * The ensureX() operations mutate 'this' in place to effectively the type to be
128 * at least X (e.g., ensureLinear will change a JSRope to be a JSFlatString).
129 */
130
131 class JSString : public js::gc::BarrieredCell<JSString>
132 {
133 protected:
134 static const size_t NUM_INLINE_CHARS = 2 * sizeof(void *) / sizeof(jschar);
135
136 /* Fields only apply to string types commented on the right. */
137 struct Data
138 {
139 size_t lengthAndFlags; /* JSString */
140 union {
141 const jschar *chars; /* JSLinearString */
142 JSString *left; /* JSRope */
143 } u1;
144 union {
145 jschar inlineStorage[NUM_INLINE_CHARS]; /* JS(Inline|FatInline)String */
146 struct {
147 union {
148 JSLinearString *base; /* JS(Dependent|Undepended)String */
149 JSString *right; /* JSRope */
150 size_t capacity; /* JSFlatString (extensible) */
151 const JSStringFinalizer *externalFinalizer;/* JSExternalString */
152 } u2;
153 union {
154 JSString *parent; /* JSRope (temporary) */
155 size_t reserved; /* may use for bug 615290 */
156 } u3;
157 } s;
158 };
159 } d;
160
161 public:
162 /* Flags exposed only for jits */
163
164 /*
165 * The low LENGTH_SHIFT bits of lengthAndFlags are used to encode the type
166 * of the string. The remaining bits store the string length (which must be
167 * less or equal than MAX_LENGTH).
168 *
169 * Instead of using a dense index to represent the most-derived type, string
170 * types are encoded to allow single-op tests for hot queries (isRope,
171 * isDependent, isFlat, isAtom) which, in view of subtyping, would require
172 * slower (isX() || isY() || isZ()).
173 *
174 * The string type encoding can be summarized as follows. The "instance
175 * encoding" entry for a type specifies the flag bits used to create a
176 * string instance of that type. Abstract types have no instances and thus
177 * have no such entry. The "subtype predicate" entry for a type specifies
178 * the predicate used to query whether a JSString instance is subtype
179 * (reflexively) of that type.
180 *
181 * Rope 0000 0000
182 * Linear - !0000
183 * HasBase - xxx1
184 * Dependent 0001 0001
185 * Flat - isLinear && !isDependent
186 * Undepended 0011 0011
187 * Extensible 0010 0010
188 * Inline 0100 isFlat && !isExtensible && (u1.chars == inlineStorage)
189 * FatInline 0100 isInline && header in FINALIZE_FAT_INLINE_STRING arena
190 * External 0100 header in FINALIZE_EXTERNAL_STRING arena
191 * Atom - 1xxx
192 * PermanentAtom 1100 1100
193 * InlineAtom - isAtom && isInline
194 * FatInlineAtom - isAtom && isFatInline
195 *
196 * "HasBase" here refers to the two string types that have a 'base' field:
197 * JSDependentString and JSUndependedString.
198 * A JSUndependedString is a JSDependentString which has been 'fixed' (by ensureFixed)
199 * to be null-terminated. In such cases, the string must keep marking its base since
200 * there may be any number of *other* JSDependentStrings transitively depending on it.
201 *
202 */
203
204 static const size_t LENGTH_SHIFT = 4;
205 static const size_t FLAGS_MASK = JS_BITMASK(LENGTH_SHIFT);
206
207 static const size_t ROPE_FLAGS = 0;
208 static const size_t DEPENDENT_FLAGS = JS_BIT(0);
209 static const size_t UNDEPENDED_FLAGS = JS_BIT(0) | JS_BIT(1);
210 static const size_t EXTENSIBLE_FLAGS = JS_BIT(1);
211 static const size_t FIXED_FLAGS = JS_BIT(2);
212
213 static const size_t INT32_MASK = JS_BITMASK(3);
214 static const size_t INT32_FLAGS = JS_BIT(1) | JS_BIT(2);
215
216 static const size_t HAS_BASE_BIT = JS_BIT(0);
217 static const size_t PERMANENT_BIT = JS_BIT(2);
218 static const size_t ATOM_BIT = JS_BIT(3);
219
220 static const size_t PERMANENT_ATOM_FLAGS = JS_BIT(2) | JS_BIT(3);
221
222 static const size_t MAX_LENGTH = JS_BIT(32 - LENGTH_SHIFT) - 1;
223
224 size_t buildLengthAndFlags(size_t length, size_t flags) {
225 JS_ASSERT(length <= MAX_LENGTH);
226 JS_ASSERT(flags <= FLAGS_MASK);
227 return (length << LENGTH_SHIFT) | flags;
228 }
229
230 /*
231 * Helper function to validate that a string of a given length is
232 * representable by a JSString. An allocation overflow is reported if false
233 * is returned.
234 */
235 static inline bool validateLength(js::ThreadSafeContext *maybecx, size_t length);
236
237 static void staticAsserts() {
238 JS_STATIC_ASSERT(JS_BITS_PER_WORD >= 32);
239 JS_STATIC_ASSERT(((JSString::MAX_LENGTH << JSString::LENGTH_SHIFT) >>
240 JSString::LENGTH_SHIFT) == JSString::MAX_LENGTH);
241 JS_STATIC_ASSERT(sizeof(JSString) ==
242 offsetof(JSString, d.inlineStorage) + NUM_INLINE_CHARS * sizeof(jschar));
243 JS_STATIC_ASSERT(offsetof(JSString, d.u1.chars) ==
244 offsetof(js::shadow::Atom, chars));
245 }
246
247 /* Avoid lame compile errors in JSRope::flatten */
248 friend class JSRope;
249
250 public:
251 /* All strings have length. */
252
253 MOZ_ALWAYS_INLINE
254 size_t length() const {
255 return d.lengthAndFlags >> LENGTH_SHIFT;
256 }
257
258 MOZ_ALWAYS_INLINE
259 bool empty() const {
260 return d.lengthAndFlags <= FLAGS_MASK;
261 }
262
263 /*
264 * All strings have a fallible operation to get an array of chars.
265 * getCharsZ additionally ensures the array is null terminated.
266 */
267
268 inline const jschar *getChars(js::ExclusiveContext *cx);
269 inline const jschar *getCharsZ(js::ExclusiveContext *cx);
270 inline bool getChar(js::ExclusiveContext *cx, size_t index, jschar *code);
271
272 /*
273 * A string has "pure" chars if it can return a pointer to its chars
274 * infallibly without mutating anything so they are safe to be from off the
275 * main thread. If a string does not have pure chars, the caller can call
276 * copyNonPureChars to allocate a copy of the chars which is also a
277 * non-mutating threadsafe operation. Beware, this is an O(n) operation
278 * (involving a DAG traversal for ropes).
279 */
280 bool hasPureChars() const { return isLinear(); }
281 bool hasPureCharsZ() const { return isFlat(); }
282 inline const jschar *pureChars() const;
283 inline const jschar *pureCharsZ() const;
284 inline bool copyNonPureChars(js::ThreadSafeContext *cx,
285 js::ScopedJSFreePtr<jschar> &out) const;
286 inline bool copyNonPureCharsZ(js::ThreadSafeContext *cx,
287 js::ScopedJSFreePtr<jschar> &out) const;
288
289 /* Fallible conversions to more-derived string types. */
290
291 inline JSLinearString *ensureLinear(js::ExclusiveContext *cx);
292 inline JSFlatString *ensureFlat(js::ExclusiveContext *cx);
293
294 static bool ensureLinear(js::ExclusiveContext *cx, JSString *str) {
295 return str->ensureLinear(cx) != nullptr;
296 }
297
298 /* Type query and debug-checked casts */
299
300 MOZ_ALWAYS_INLINE
301 bool isRope() const {
302 return (d.lengthAndFlags & FLAGS_MASK) == ROPE_FLAGS;
303 }
304
305 MOZ_ALWAYS_INLINE
306 JSRope &asRope() const {
307 JS_ASSERT(isRope());
308 return *(JSRope *)this;
309 }
310
311 MOZ_ALWAYS_INLINE
312 bool isLinear() const {
313 return !isRope();
314 }
315
316 MOZ_ALWAYS_INLINE
317 JSLinearString &asLinear() const {
318 JS_ASSERT(JSString::isLinear());
319 return *(JSLinearString *)this;
320 }
321
322 MOZ_ALWAYS_INLINE
323 bool isDependent() const {
324 return (d.lengthAndFlags & FLAGS_MASK) == DEPENDENT_FLAGS;
325 }
326
327 MOZ_ALWAYS_INLINE
328 JSDependentString &asDependent() const {
329 JS_ASSERT(isDependent());
330 return *(JSDependentString *)this;
331 }
332
333 MOZ_ALWAYS_INLINE
334 bool isFlat() const {
335 return isLinear() && !isDependent();
336 }
337
338 MOZ_ALWAYS_INLINE
339 JSFlatString &asFlat() const {
340 JS_ASSERT(isFlat());
341 return *(JSFlatString *)this;
342 }
343
344 MOZ_ALWAYS_INLINE
345 bool isExtensible() const {
346 return (d.lengthAndFlags & FLAGS_MASK) == EXTENSIBLE_FLAGS;
347 }
348
349 MOZ_ALWAYS_INLINE
350 JSExtensibleString &asExtensible() const {
351 JS_ASSERT(isExtensible());
352 return *(JSExtensibleString *)this;
353 }
354
355 MOZ_ALWAYS_INLINE
356 bool isInline() const {
357 return isFlat() && !isExtensible() && (d.u1.chars == d.inlineStorage);
358 }
359
360 MOZ_ALWAYS_INLINE
361 JSInlineString &asInline() const {
362 JS_ASSERT(isInline());
363 return *(JSInlineString *)this;
364 }
365
366 bool isFatInline() const;
367
368 /* For hot code, prefer other type queries. */
369 bool isExternal() const;
370
371 MOZ_ALWAYS_INLINE
372 JSExternalString &asExternal() const {
373 JS_ASSERT(isExternal());
374 return *(JSExternalString *)this;
375 }
376
377 MOZ_ALWAYS_INLINE
378 bool isUndepended() const {
379 return (d.lengthAndFlags & FLAGS_MASK) == UNDEPENDED_FLAGS;
380 }
381
382 MOZ_ALWAYS_INLINE
383 bool isAtom() const {
384 return d.lengthAndFlags & ATOM_BIT;
385 }
386
387 MOZ_ALWAYS_INLINE
388 bool isPermanentAtom() const {
389 return (d.lengthAndFlags & FLAGS_MASK) == PERMANENT_ATOM_FLAGS;
390 }
391
392 MOZ_ALWAYS_INLINE
393 JSAtom &asAtom() const {
394 JS_ASSERT(isAtom());
395 return *(JSAtom *)this;
396 }
397
398 /* Only called by the GC for dependent or undepended strings. */
399
400 inline bool hasBase() const {
401 JS_STATIC_ASSERT((DEPENDENT_FLAGS | JS_BIT(1)) == UNDEPENDED_FLAGS);
402 return d.lengthAndFlags & HAS_BASE_BIT;
403 }
404
405 inline JSLinearString *base() const;
406
407 inline void markBase(JSTracer *trc);
408
409 /* Only called by the GC for strings with the FINALIZE_STRING kind. */
410
411 inline void finalize(js::FreeOp *fop);
412
413 /* Gets the number of bytes that the chars take on the heap. */
414
415 size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);
416
417 /* Offsets for direct field from jit code. */
418
419 static size_t offsetOfLengthAndFlags() {
420 return offsetof(JSString, d.lengthAndFlags);
421 }
422
423 static size_t offsetOfChars() {
424 return offsetof(JSString, d.u1.chars);
425 }
426
427 js::gc::AllocKind getAllocKind() const { return tenuredGetAllocKind(); }
428
429 static inline js::ThingRootKind rootKind() { return js::THING_ROOT_STRING; }
430
431 #ifdef DEBUG
432 void dump();
433 static void dumpChars(const jschar *s, size_t len);
434 bool equals(const char *s);
435 #endif
436
437 static MOZ_ALWAYS_INLINE void readBarrier(JSString *thing) {
438 #ifdef JSGC_INCREMENTAL
439 if (thing->isPermanentAtom())
440 return;
441
442 js::gc::BarrieredCell<JSString>::readBarrier(thing);
443 #endif
444 }
445
446 static MOZ_ALWAYS_INLINE void writeBarrierPre(JSString *thing) {
447 #ifdef JSGC_INCREMENTAL
448 if (isNullLike(thing) || thing->isPermanentAtom())
449 return;
450
451 js::gc::BarrieredCell<JSString>::writeBarrierPre(thing);
452 #endif
453 }
454
455 private:
456 JSString() MOZ_DELETE;
457 JSString(const JSString &other) MOZ_DELETE;
458 void operator=(const JSString &other) MOZ_DELETE;
459 };
460
461 class JSRope : public JSString
462 {
463 bool copyNonPureCharsInternal(js::ThreadSafeContext *cx,
464 js::ScopedJSFreePtr<jschar> &out,
465 bool nullTerminate) const;
466 bool copyNonPureChars(js::ThreadSafeContext *cx, js::ScopedJSFreePtr<jschar> &out) const;
467 bool copyNonPureCharsZ(js::ThreadSafeContext *cx, js::ScopedJSFreePtr<jschar> &out) const;
468
469 enum UsingBarrier { WithIncrementalBarrier, NoBarrier };
470 template<UsingBarrier b>
471 JSFlatString *flattenInternal(js::ExclusiveContext *cx);
472
473 friend class JSString;
474 JSFlatString *flatten(js::ExclusiveContext *cx);
475
476 void init(js::ThreadSafeContext *cx, JSString *left, JSString *right, size_t length);
477
478 public:
479 template <js::AllowGC allowGC>
480 static inline JSRope *new_(js::ThreadSafeContext *cx,
481 typename js::MaybeRooted<JSString*, allowGC>::HandleType left,
482 typename js::MaybeRooted<JSString*, allowGC>::HandleType right,
483 size_t length);
484
485 inline JSString *leftChild() const {
486 JS_ASSERT(isRope());
487 return d.u1.left;
488 }
489
490 inline JSString *rightChild() const {
491 JS_ASSERT(isRope());
492 return d.s.u2.right;
493 }
494
495 inline void markChildren(JSTracer *trc);
496
497 inline static size_t offsetOfLeft() {
498 return offsetof(JSRope, d.u1.left);
499 }
500 inline static size_t offsetOfRight() {
501 return offsetof(JSRope, d.s.u2.right);
502 }
503 };
504
505 JS_STATIC_ASSERT(sizeof(JSRope) == sizeof(JSString));
506
507 class JSLinearString : public JSString
508 {
509 friend class JSString;
510
511 /* Vacuous and therefore unimplemented. */
512 JSLinearString *ensureLinear(JSContext *cx) MOZ_DELETE;
513 bool isLinear() const MOZ_DELETE;
514 JSLinearString &asLinear() const MOZ_DELETE;
515
516 public:
517 MOZ_ALWAYS_INLINE
518 const jschar *chars() const {
519 JS_ASSERT(JSString::isLinear());
520 return d.u1.chars;
521 }
522
523 JS::TwoByteChars range() const {
524 JS_ASSERT(JSString::isLinear());
525 return JS::TwoByteChars(d.u1.chars, length());
526 }
527 };
528
529 JS_STATIC_ASSERT(sizeof(JSLinearString) == sizeof(JSString));
530
531 class JSDependentString : public JSLinearString
532 {
533 bool copyNonPureCharsZ(js::ThreadSafeContext *cx, js::ScopedJSFreePtr<jschar> &out) const;
534
535 friend class JSString;
536 JSFlatString *undepend(js::ExclusiveContext *cx);
537
538 void init(js::ThreadSafeContext *cx, JSLinearString *base, const jschar *chars,
539 size_t length);
540
541 /* Vacuous and therefore unimplemented. */
542 bool isDependent() const MOZ_DELETE;
543 JSDependentString &asDependent() const MOZ_DELETE;
544
545 public:
546 static inline JSLinearString *new_(js::ExclusiveContext *cx, JSLinearString *base,
547 const jschar *chars, size_t length);
548 };
549
550 JS_STATIC_ASSERT(sizeof(JSDependentString) == sizeof(JSString));
551
552 class JSFlatString : public JSLinearString
553 {
554 /* Vacuous and therefore unimplemented. */
555 JSFlatString *ensureFlat(JSContext *cx) MOZ_DELETE;
556 bool isFlat() const MOZ_DELETE;
557 JSFlatString &asFlat() const MOZ_DELETE;
558
559 bool isIndexSlow(uint32_t *indexp) const;
560
561 void init(const jschar *chars, size_t length);
562
563 public:
564 template <js::AllowGC allowGC>
565 static inline JSFlatString *new_(js::ThreadSafeContext *cx,
566 const jschar *chars, size_t length);
567
568 MOZ_ALWAYS_INLINE
569 const jschar *charsZ() const {
570 JS_ASSERT(JSString::isFlat());
571 return chars();
572 }
573
574 /*
575 * Returns true if this string's characters store an unsigned 32-bit
576 * integer value, initializing *indexp to that value if so. (Thus if
577 * calling isIndex returns true, js::IndexToString(cx, *indexp) will be a
578 * string equal to this string.)
579 */
580 inline bool isIndex(uint32_t *indexp) const {
581 const jschar *s = chars();
582 return JS7_ISDEC(*s) && isIndexSlow(indexp);
583 }
584
585 /*
586 * Returns a property name represented by this string, or null on failure.
587 * You must verify that this is not an index per isIndex before calling
588 * this method.
589 */
590 inline js::PropertyName *toPropertyName(JSContext *cx);
591
592 /*
593 * Once a JSFlatString sub-class has been added to the atom state, this
594 * operation changes the string to the JSAtom type, in place.
595 */
596 MOZ_ALWAYS_INLINE JSAtom *morphAtomizedStringIntoAtom() {
597 d.lengthAndFlags = buildLengthAndFlags(length(), ATOM_BIT);
598 return &asAtom();
599 }
600 MOZ_ALWAYS_INLINE JSAtom *morphAtomizedStringIntoPermanentAtom() {
601 d.lengthAndFlags = buildLengthAndFlags(length(), PERMANENT_ATOM_FLAGS);
602 return &asAtom();
603 }
604
605 inline void finalize(js::FreeOp *fop);
606 };
607
608 JS_STATIC_ASSERT(sizeof(JSFlatString) == sizeof(JSString));
609
610 class JSExtensibleString : public JSFlatString
611 {
612 /* Vacuous and therefore unimplemented. */
613 bool isExtensible() const MOZ_DELETE;
614 JSExtensibleString &asExtensible() const MOZ_DELETE;
615
616 public:
617 MOZ_ALWAYS_INLINE
618 size_t capacity() const {
619 JS_ASSERT(JSString::isExtensible());
620 return d.s.u2.capacity;
621 }
622 };
623
624 JS_STATIC_ASSERT(sizeof(JSExtensibleString) == sizeof(JSString));
625
626 /* On 32-bit platforms, MAX_INLINE_LENGTH is 4. On 64-bit platforms it is 8. */
627 class JSInlineString : public JSFlatString
628 {
629 static const size_t MAX_INLINE_LENGTH = NUM_INLINE_CHARS - 1;
630
631 public:
632 template <js::AllowGC allowGC>
633 static inline JSInlineString *new_(js::ThreadSafeContext *cx);
634
635 inline jschar *init(size_t length);
636
637 inline void resetLength(size_t length);
638
639 static bool lengthFits(size_t length) {
640 return length <= MAX_INLINE_LENGTH;
641 }
642
643 static size_t offsetOfInlineStorage() {
644 return offsetof(JSInlineString, d.inlineStorage);
645 }
646 };
647
648 JS_STATIC_ASSERT(sizeof(JSInlineString) == sizeof(JSString));
649
650 /*
651 * On both 32-bit and 64-bit platforms, INLINE_EXTENSION_CHARS is 12. This is
652 * deliberate, in order to minimize potential performance differences between
653 * 32-bit and 64-bit platforms.
654 *
655 * There are still some differences due to NUM_INLINE_CHARS being different.
656 * E.g. strings of length 4--7 will be JSFatInlineStrings on 32-bit platforms
657 * and JSInlineStrings on 64-bit platforms. But the more significant transition
658 * from inline strings to non-inline strings occurs at length 12 on both 32-bit
659 * and 64-bit platforms.
660 */
661 class JSFatInlineString : public JSInlineString
662 {
663 static const size_t INLINE_EXTENSION_CHARS = 12 - NUM_INLINE_CHARS;
664
665 static void staticAsserts() {
666 JS_STATIC_ASSERT((INLINE_EXTENSION_CHARS * sizeof(jschar)) % js::gc::CellSize == 0);
667 JS_STATIC_ASSERT(MAX_FAT_INLINE_LENGTH + 1 ==
668 (sizeof(JSFatInlineString) -
669 offsetof(JSFatInlineString, d.inlineStorage)) / sizeof(jschar));
670 }
671
672 protected: /* to fool clang into not warning this is unused */
673 jschar inlineStorageExtension[INLINE_EXTENSION_CHARS];
674
675 public:
676 template <js::AllowGC allowGC>
677 static inline JSFatInlineString *new_(js::ThreadSafeContext *cx);
678
679 static const size_t MAX_FAT_INLINE_LENGTH = JSString::NUM_INLINE_CHARS +
680 INLINE_EXTENSION_CHARS
681 -1 /* null terminator */;
682
683 static bool lengthFits(size_t length) {
684 return length <= MAX_FAT_INLINE_LENGTH;
685 }
686
687 /* Only called by the GC for strings with the FINALIZE_FAT_INLINE_STRING kind. */
688
689 MOZ_ALWAYS_INLINE void finalize(js::FreeOp *fop);
690 };
691
692 JS_STATIC_ASSERT(sizeof(JSFatInlineString) % js::gc::CellSize == 0);
693
694 class JSExternalString : public JSFlatString
695 {
696 void init(const jschar *chars, size_t length, const JSStringFinalizer *fin);
697
698 /* Vacuous and therefore unimplemented. */
699 bool isExternal() const MOZ_DELETE;
700 JSExternalString &asExternal() const MOZ_DELETE;
701
702 public:
703 static inline JSExternalString *new_(JSContext *cx, const jschar *chars, size_t length,
704 const JSStringFinalizer *fin);
705
706 const JSStringFinalizer *externalFinalizer() const {
707 JS_ASSERT(JSString::isExternal());
708 return d.s.u2.externalFinalizer;
709 }
710
711 /* Only called by the GC for strings with the FINALIZE_EXTERNAL_STRING kind. */
712
713 inline void finalize(js::FreeOp *fop);
714 };
715
716 JS_STATIC_ASSERT(sizeof(JSExternalString) == sizeof(JSString));
717
718 class JSUndependedString : public JSFlatString
719 {
720 /*
721 * JSUndependedString is not explicitly used and is only present for
722 * consistency. See JSDependentString::undepend for how a JSDependentString
723 * gets morphed into a JSUndependedString.
724 */
725 };
726
727 JS_STATIC_ASSERT(sizeof(JSUndependedString) == sizeof(JSString));
728
729 class JSAtom : public JSFlatString
730 {
731 /* Vacuous and therefore unimplemented. */
732 bool isAtom() const MOZ_DELETE;
733 JSAtom &asAtom() const MOZ_DELETE;
734
735 public:
736 /* Returns the PropertyName for this. isIndex() must be false. */
737 inline js::PropertyName *asPropertyName();
738
739 inline void finalize(js::FreeOp *fop);
740
741 MOZ_ALWAYS_INLINE
742 bool isPermanent() const {
743 return d.lengthAndFlags & PERMANENT_BIT;
744 }
745
746 // Transform this atom into a permanent atom. This is only done during
747 // initialization of the runtime.
748 MOZ_ALWAYS_INLINE void morphIntoPermanentAtom() {
749 d.lengthAndFlags = buildLengthAndFlags(length(), PERMANENT_ATOM_FLAGS);
750 }
751
752 #ifdef DEBUG
753 void dump();
754 #endif
755 };
756
757 JS_STATIC_ASSERT(sizeof(JSAtom) == sizeof(JSString));
758
759 namespace js {
760
761 /*
762 * Thread safe RAII wrapper for inspecting the contents of JSStrings. The
763 * thread safe operations such as |getCharsNonDestructive| require allocation
764 * of a char array. This allocation is not always required, such as when the
765 * string is already linear. This wrapper makes dealing with this detail more
766 * convenient by encapsulating the allocation logic.
767 *
768 * As the name suggests, this class is scoped. Return values from chars() and
769 * range() may not be valid after the inspector goes out of scope.
770 */
771
772 class ScopedThreadSafeStringInspector
773 {
774 private:
775 JSString *str_;
776 ScopedJSFreePtr<jschar> scopedChars_;
777 const jschar *chars_;
778
779 public:
780 ScopedThreadSafeStringInspector(JSString *str)
781 : str_(str),
782 chars_(nullptr)
783 { }
784
785 bool ensureChars(ThreadSafeContext *cx);
786
787 const jschar *chars() {
788 JS_ASSERT(chars_);
789 return chars_;
790 }
791
792 JS::TwoByteChars range() {
793 JS_ASSERT(chars_);
794 return JS::TwoByteChars(chars_, str_->length());
795 }
796 };
797
798 class StaticStrings
799 {
800 private:
801 /* Bigger chars cannot be in a length-2 string. */
802 static const size_t SMALL_CHAR_LIMIT = 128U;
803 static const size_t NUM_SMALL_CHARS = 64U;
804
805 JSAtom *length2StaticTable[NUM_SMALL_CHARS * NUM_SMALL_CHARS];
806
807 public:
808 /* We keep these public for the JITs. */
809 static const size_t UNIT_STATIC_LIMIT = 256U;
810 JSAtom *unitStaticTable[UNIT_STATIC_LIMIT];
811
812 static const size_t INT_STATIC_LIMIT = 256U;
813 JSAtom *intStaticTable[INT_STATIC_LIMIT];
814
815 StaticStrings() {
816 mozilla::PodZero(this);
817 }
818
819 bool init(JSContext *cx);
820 void trace(JSTracer *trc);
821
822 static bool hasUint(uint32_t u) { return u < INT_STATIC_LIMIT; }
823
824 JSAtom *getUint(uint32_t u) {
825 JS_ASSERT(hasUint(u));
826 return intStaticTable[u];
827 }
828
829 static bool hasInt(int32_t i) {
830 return uint32_t(i) < INT_STATIC_LIMIT;
831 }
832
833 JSAtom *getInt(int32_t i) {
834 JS_ASSERT(hasInt(i));
835 return getUint(uint32_t(i));
836 }
837
838 static bool hasUnit(jschar c) { return c < UNIT_STATIC_LIMIT; }
839
840 JSAtom *getUnit(jschar c) {
841 JS_ASSERT(hasUnit(c));
842 return unitStaticTable[c];
843 }
844
845 /* May not return atom, returns null on (reported) failure. */
846 inline JSLinearString *getUnitStringForElement(JSContext *cx, JSString *str, size_t index);
847
848 static bool isStatic(JSAtom *atom);
849
850 /* Return null if no static atom exists for the given (chars, length). */
851 JSAtom *lookup(const jschar *chars, size_t length) {
852 switch (length) {
853 case 1:
854 if (chars[0] < UNIT_STATIC_LIMIT)
855 return getUnit(chars[0]);
856 return nullptr;
857 case 2:
858 if (fitsInSmallChar(chars[0]) && fitsInSmallChar(chars[1]))
859 return getLength2(chars[0], chars[1]);
860 return nullptr;
861 case 3:
862 /*
863 * Here we know that JSString::intStringTable covers only 256 (or at least
864 * not 1000 or more) chars. We rely on order here to resolve the unit vs.
865 * int string/length-2 string atom identity issue by giving priority to unit
866 * strings for "0" through "9" and length-2 strings for "10" through "99".
867 */
868 JS_STATIC_ASSERT(INT_STATIC_LIMIT <= 999);
869 if ('1' <= chars[0] && chars[0] <= '9' &&
870 '0' <= chars[1] && chars[1] <= '9' &&
871 '0' <= chars[2] && chars[2] <= '9') {
872 int i = (chars[0] - '0') * 100 +
873 (chars[1] - '0') * 10 +
874 (chars[2] - '0');
875
876 if (unsigned(i) < INT_STATIC_LIMIT)
877 return getInt(i);
878 }
879 return nullptr;
880 }
881
882 return nullptr;
883 }
884
885 private:
886 typedef uint8_t SmallChar;
887 static const SmallChar INVALID_SMALL_CHAR = -1;
888
889 static bool fitsInSmallChar(jschar c) {
890 return c < SMALL_CHAR_LIMIT && toSmallChar[c] != INVALID_SMALL_CHAR;
891 }
892
893 static const SmallChar toSmallChar[];
894
895 JSAtom *getLength2(jschar c1, jschar c2);
896 JSAtom *getLength2(uint32_t u) {
897 JS_ASSERT(u < 100);
898 return getLength2('0' + u / 10, '0' + u % 10);
899 }
900 };
901
902 /*
903 * Represents an atomized string which does not contain an index (that is, an
904 * unsigned 32-bit value). Thus for any PropertyName propname,
905 * ToString(ToUint32(propname)) never equals propname.
906 *
907 * To more concretely illustrate the utility of PropertyName, consider that it
908 * is used to partition, in a type-safe manner, the ways to refer to a
909 * property, as follows:
910 *
911 * - uint32_t indexes,
912 * - PropertyName strings which don't encode uint32_t indexes, and
913 * - jsspecial special properties (non-ES5 properties like object-valued
914 * jsids, JSID_EMPTY, JSID_VOID, and maybe in the future Harmony-proposed
915 * private names).
916 */
917 class PropertyName : public JSAtom
918 {};
919
920 JS_STATIC_ASSERT(sizeof(PropertyName) == sizeof(JSString));
921
922 static MOZ_ALWAYS_INLINE jsid
923 NameToId(PropertyName *name)
924 {
925 return NON_INTEGER_ATOM_TO_JSID(name);
926 }
927
928 typedef HeapPtr<JSAtom> HeapPtrAtom;
929
930 class AutoNameVector : public AutoVectorRooter<PropertyName *>
931 {
932 typedef AutoVectorRooter<PropertyName *> BaseType;
933 public:
934 explicit AutoNameVector(JSContext *cx
935 MOZ_GUARD_OBJECT_NOTIFIER_PARAM)
936 : AutoVectorRooter<PropertyName *>(cx, NAMEVECTOR)
937 {
938 MOZ_GUARD_OBJECT_NOTIFIER_INIT;
939 }
940
941 HandlePropertyName operator[](size_t i) const {
942 return HandlePropertyName::fromMarkedLocation(&begin()[i]);
943 }
944
945 MOZ_DECL_USE_GUARD_OBJECT_NOTIFIER
946 };
947
948 } /* namespace js */
949
950 /* Avoid requiring vm/String-inl.h just to call getChars. */
951
952 MOZ_ALWAYS_INLINE const jschar *
953 JSString::getChars(js::ExclusiveContext *cx)
954 {
955 if (JSLinearString *str = ensureLinear(cx))
956 return str->chars();
957 return nullptr;
958 }
959
960 MOZ_ALWAYS_INLINE bool
961 JSString::getChar(js::ExclusiveContext *cx, size_t index, jschar *code)
962 {
963 JS_ASSERT(index < length());
964
965 /*
966 * Optimization for one level deep ropes.
967 * This is common for the following pattern:
968 *
969 * while() {
970 * text = text.substr(0, x) + "bla" + text.substr(x)
971 * test.charCodeAt(x + 1)
972 * }
973 */
974 const jschar *chars;
975 if (isRope()) {
976 JSRope *rope = &asRope();
977 if (uint32_t(index) < rope->leftChild()->length()) {
978 chars = rope->leftChild()->getChars(cx);
979 } else {
980 chars = rope->rightChild()->getChars(cx);
981 index -= rope->leftChild()->length();
982 }
983 } else {
984 chars = getChars(cx);
985 }
986
987 if (!chars)
988 return false;
989
990 *code = chars[index];
991 return true;
992 }
993
994 MOZ_ALWAYS_INLINE const jschar *
995 JSString::getCharsZ(js::ExclusiveContext *cx)
996 {
997 if (JSFlatString *str = ensureFlat(cx))
998 return str->chars();
999 return nullptr;
1000 }
1001
1002 MOZ_ALWAYS_INLINE const jschar *
1003 JSString::pureChars() const
1004 {
1005 JS_ASSERT(hasPureChars());
1006 return asLinear().chars();
1007 }
1008
1009 MOZ_ALWAYS_INLINE const jschar *
1010 JSString::pureCharsZ() const
1011 {
1012 JS_ASSERT(hasPureCharsZ());
1013 return asFlat().charsZ();
1014 }
1015
1016 MOZ_ALWAYS_INLINE bool
1017 JSString::copyNonPureChars(js::ThreadSafeContext *cx, js::ScopedJSFreePtr<jschar> &out) const
1018 {
1019 JS_ASSERT(!hasPureChars());
1020 return asRope().copyNonPureChars(cx, out);
1021 }
1022
1023 MOZ_ALWAYS_INLINE bool
1024 JSString::copyNonPureCharsZ(js::ThreadSafeContext *cx, js::ScopedJSFreePtr<jschar> &out) const
1025 {
1026 JS_ASSERT(!hasPureChars());
1027 if (isDependent())
1028 return asDependent().copyNonPureCharsZ(cx, out);
1029 return asRope().copyNonPureCharsZ(cx, out);
1030 }
1031
1032 MOZ_ALWAYS_INLINE JSLinearString *
1033 JSString::ensureLinear(js::ExclusiveContext *cx)
1034 {
1035 return isLinear()
1036 ? &asLinear()
1037 : asRope().flatten(cx);
1038 }
1039
1040 MOZ_ALWAYS_INLINE JSFlatString *
1041 JSString::ensureFlat(js::ExclusiveContext *cx)
1042 {
1043 return isFlat()
1044 ? &asFlat()
1045 : isDependent()
1046 ? asDependent().undepend(cx)
1047 : asRope().flatten(cx);
1048 }
1049
1050 inline JSLinearString *
1051 JSString::base() const
1052 {
1053 JS_ASSERT(hasBase());
1054 JS_ASSERT(!d.s.u2.base->isInline());
1055 return d.s.u2.base;
1056 }
1057
1058 inline js::PropertyName *
1059 JSAtom::asPropertyName()
1060 {
1061 #ifdef DEBUG
1062 uint32_t dummy;
1063 JS_ASSERT(!isIndex(&dummy));
1064 #endif
1065 return static_cast<js::PropertyName *>(this);
1066 }
1067
1068 #endif /* vm_String_h */

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial