michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "vm/String-inl.h"
michael@0: 
michael@0: #include "mozilla/MathAlgorithms.h"
michael@0: #include "mozilla/MemoryReporting.h"
michael@0: #include "mozilla/PodOperations.h"
michael@0: #include "mozilla/RangedPtr.h"
michael@0: 
michael@0: #include "gc/Marking.h"
michael@0: 
michael@0: #include "jscntxtinlines.h"
michael@0: #include "jscompartmentinlines.h"
michael@0: 
michael@0: using namespace js;
michael@0: 
michael@0: using mozilla::PodCopy;
michael@0: using mozilla::RangedPtr;
michael@0: using mozilla::RoundUpPow2;
michael@0: 
michael@0: bool
michael@0: JSString::isFatInline() const
michael@0: {
michael@0:     // It's possible for fat-inline strings to be converted to flat strings;
michael@0:     // as a result, checking just for the arena isn't enough to determine if a
michael@0:     // string is fat-inline.  Hence the isInline() check.
michael@0:     bool is_FatInline = (getAllocKind() == gc::FINALIZE_FAT_INLINE_STRING) && isInline();
michael@0:     JS_ASSERT_IF(is_FatInline, isFlat());
michael@0:     return is_FatInline;
michael@0: }
michael@0: 
michael@0: bool
michael@0: JSString::isExternal() const
michael@0: {
michael@0:     bool is_external = (getAllocKind() == gc::FINALIZE_EXTERNAL_STRING);
michael@0:     JS_ASSERT_IF(is_external, isFlat());
michael@0:     return is_external;
michael@0: }
michael@0: 
michael@0: size_t
michael@0: JSString::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf)
michael@0: {
michael@0:     // JSRope: do nothing, we'll count all children chars when we hit the leaf strings.
michael@0:     if (isRope())
michael@0:         return 0;
michael@0: 
michael@0:     JS_ASSERT(isLinear());
michael@0: 
michael@0:     // JSDependentString: do nothing, we'll count the chars when we hit the base string.
michael@0:     if (isDependent())
michael@0:         return 0;
michael@0: 
michael@0:     JS_ASSERT(isFlat());
michael@0: 
michael@0:     // JSExtensibleString: count the full capacity, not just the used space.
michael@0:     if (isExtensible()) {
michael@0:         JSExtensibleString &extensible = asExtensible();
michael@0:         return mallocSizeOf(extensible.chars());
michael@0:     }
michael@0: 
michael@0:     // JSExternalString: don't count, the chars could be stored anywhere.
michael@0:     if (isExternal())
michael@0:         return 0;
michael@0: 
michael@0:     // JSInlineString, JSFatInlineString [JSInlineAtom, JSFatInlineAtom]: the chars are inline.
michael@0:     if (isInline())
michael@0:         return 0;
michael@0: 
michael@0:     // JSAtom, JSUndependedString: measure the space for the chars.  For
michael@0:     // JSUndependedString, there is no need to count the base string, for the
michael@0:     // same reason as JSDependentString above.
michael@0:     JSFlatString &flat = asFlat();
michael@0:     return mallocSizeOf(flat.chars());
michael@0: }
michael@0: 
michael@0: #ifdef DEBUG
michael@0: 
michael@0: void
michael@0: JSString::dumpChars(const jschar *s, size_t n)
michael@0: {
michael@0:     if (n == SIZE_MAX) {
michael@0:         n = 0;
michael@0:         while (s[n])
michael@0:             n++;
michael@0:     }
michael@0: 
michael@0:     fputc('"', stderr);
michael@0:     for (size_t i = 0; i < n; i++) {
michael@0:         if (s[i] == '\n')
michael@0:             fprintf(stderr, "\\n");
michael@0:         else if (s[i] == '\t')
michael@0:             fprintf(stderr, "\\t");
michael@0:         else if (s[i] >= 32 && s[i] < 127)
michael@0:             fputc(s[i], stderr);
michael@0:         else if (s[i] <= 255)
michael@0:             fprintf(stderr, "\\x%02x", (unsigned int) s[i]);
michael@0:         else
michael@0:             fprintf(stderr, "\\u%04x", (unsigned int) s[i]);
michael@0:     }
michael@0:     fputc('"', stderr);
michael@0: }
michael@0: 
michael@0: void
michael@0: JSString::dump()
michael@0: {
michael@0:     if (const jschar *chars = getChars(nullptr)) {
michael@0:         fprintf(stderr, "JSString* (%p) = jschar * (%p) = ",
michael@0:                 (void *) this, (void *) chars);
michael@0:         dumpChars(chars, length());
michael@0:     } else {
michael@0:         fprintf(stderr, "(oom in JSString::dump)");
michael@0:     }
michael@0:     fputc('\n', stderr);
michael@0: }
michael@0: 
michael@0: bool
michael@0: JSString::equals(const char *s)
michael@0: {
michael@0:     const jschar *c = getChars(nullptr);
michael@0:     if (!c) {
michael@0:         fprintf(stderr, "OOM in JSString::equals!\n");
michael@0:         return false;
michael@0:     }
michael@0:     while (*c && *s) {
michael@0:         if (*c != *s)
michael@0:             return false;
michael@0:         c++;
michael@0:         s++;
michael@0:     }
michael@0:     return *c == *s;
michael@0: }
michael@0: #endif /* DEBUG */
michael@0: 
michael@0: static MOZ_ALWAYS_INLINE bool
michael@0: AllocChars(ThreadSafeContext *maybecx, size_t length, jschar **chars, size_t *capacity)
michael@0: {
michael@0:     /*
michael@0:      * String length doesn't include the null char, so include it here before
michael@0:      * doubling. Adding the null char after doubling would interact poorly with
michael@0:      * round-up malloc schemes.
michael@0:      */
michael@0:     size_t numChars = length + 1;
michael@0: 
michael@0:     /*
michael@0:      * Grow by 12.5% if the buffer is very large. Otherwise, round up to the
michael@0:      * next power of 2. This is similar to what we do with arrays; see
michael@0:      * JSObject::ensureDenseArrayElements.
michael@0:      */
michael@0:     static const size_t DOUBLING_MAX = 1024 * 1024;
michael@0:     numChars = numChars > DOUBLING_MAX ? numChars + (numChars / 8) : RoundUpPow2(numChars);
michael@0: 
michael@0:     /* Like length, capacity does not include the null char, so take it out. */
michael@0:     *capacity = numChars - 1;
michael@0: 
michael@0:     JS_STATIC_ASSERT(JSString::MAX_LENGTH * sizeof(jschar) < UINT32_MAX);
michael@0:     size_t bytes = numChars * sizeof(jschar);
michael@0:     *chars = (jschar *)(maybecx ? maybecx->malloc_(bytes) : js_malloc(bytes));
michael@0:     return *chars != nullptr;
michael@0: }
michael@0: 
michael@0: bool
michael@0: JSRope::copyNonPureChars(ThreadSafeContext *cx, ScopedJSFreePtr<jschar> &out) const
michael@0: {
michael@0:     return copyNonPureCharsInternal(cx, out, false);
michael@0: }
michael@0: 
michael@0: bool
michael@0: JSRope::copyNonPureCharsZ(ThreadSafeContext *cx, ScopedJSFreePtr<jschar> &out) const
michael@0: {
michael@0:     return copyNonPureCharsInternal(cx, out, true);
michael@0: }
michael@0: 
michael@0: bool
michael@0: JSRope::copyNonPureCharsInternal(ThreadSafeContext *cx, ScopedJSFreePtr<jschar> &out,
michael@0:                                  bool nullTerminate) const
michael@0: {
michael@0:     /*
michael@0:      * Perform non-destructive post-order traversal of the rope, splatting
michael@0:      * each node's characters into a contiguous buffer.
michael@0:      */
michael@0: 
michael@0:     size_t n = length();
michael@0:     if (cx)
michael@0:         out.reset(cx->pod_malloc<jschar>(n + 1));
michael@0:     else
michael@0:         out.reset(js_pod_malloc<jschar>(n + 1));
michael@0: 
michael@0:     if (!out)
michael@0:         return false;
michael@0: 
michael@0:     Vector<const JSString *, 8, SystemAllocPolicy> nodeStack;
michael@0:     const JSString *str = this;
michael@0:     jschar *pos = out;
michael@0:     while (true) {
michael@0:         if (str->isRope()) {
michael@0:             if (!nodeStack.append(str->asRope().rightChild()))
michael@0:                 return false;
michael@0:             str = str->asRope().leftChild();
michael@0:         } else {
michael@0:             size_t len = str->length();
michael@0:             PodCopy(pos, str->asLinear().chars(), len);
michael@0:             pos += len;
michael@0:             if (nodeStack.empty())
michael@0:                 break;
michael@0:             str = nodeStack.popCopy();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     JS_ASSERT(pos == out + n);
michael@0: 
michael@0:     if (nullTerminate)
michael@0:         out[n] = 0;
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: template<JSRope::UsingBarrier b>
michael@0: JSFlatString *
michael@0: JSRope::flattenInternal(ExclusiveContext *maybecx)
michael@0: {
michael@0:     /*
michael@0:      * Perform a depth-first dag traversal, splatting each node's characters
michael@0:      * into a contiguous buffer. Visit each rope node three times:
michael@0:      *   1. record position in the buffer and recurse into left child;
michael@0:      *   2. recurse into the right child;
michael@0:      *   3. transform the node into a dependent string.
michael@0:      * To avoid maintaining a stack, tree nodes are mutated to indicate how many
michael@0:      * times they have been visited. Since ropes can be dags, a node may be
michael@0:      * encountered multiple times during traversal. However, step 3 above leaves
michael@0:      * a valid dependent string, so everything works out. This algorithm is
michael@0:      * homomorphic to marking code.
michael@0:      *
michael@0:      * While ropes avoid all sorts of quadratic cases with string
michael@0:      * concatenation, they can't help when ropes are immediately flattened.
michael@0:      * One idiomatic case that we'd like to keep linear (and has traditionally
michael@0:      * been linear in SM and other JS engines) is:
michael@0:      *
michael@0:      *   while (...) {
michael@0:      *     s += ...
michael@0:      *     s.flatten
michael@0:      *   }
michael@0:      *
michael@0:      * To do this, when the buffer for a to-be-flattened rope is allocated, the
michael@0:      * allocation size is rounded up. Then, if the resulting flat string is the
michael@0:      * left-hand side of a new rope that gets flattened and there is enough
michael@0:      * capacity, the rope is flattened into the same buffer, thereby avoiding
michael@0:      * copying the left-hand side. Clearing the 'extensible' bit turns off this
michael@0:      * optimization. This is necessary, e.g., when the JSAPI hands out the raw
michael@0:      * null-terminated char array of a flat string.
michael@0:      *
michael@0:      * N.B. This optimization can create chains of dependent strings.
michael@0:      */
michael@0:     const size_t wholeLength = length();
michael@0:     size_t wholeCapacity;
michael@0:     jschar *wholeChars;
michael@0:     JSString *str = this;
michael@0:     jschar *pos;
michael@0: 
michael@0:     /* Find the left most string, containing the first string. */
michael@0:     JSRope *leftMostRope = this;
michael@0:     while (leftMostRope->leftChild()->isRope())
michael@0:         leftMostRope = &leftMostRope->leftChild()->asRope();
michael@0: 
michael@0:     if (leftMostRope->leftChild()->isExtensible()) {
michael@0:         JSExtensibleString &left = leftMostRope->leftChild()->asExtensible();
michael@0:         size_t capacity = left.capacity();
michael@0:         if (capacity >= wholeLength) {
michael@0:             /*
michael@0:              * Simulate a left-most traversal from the root to leftMost->leftChild()
michael@0:              * via first_visit_node
michael@0:              */
michael@0:             while (str != leftMostRope) {
michael@0:                 JS_ASSERT(str->isRope());
michael@0:                 if (b == WithIncrementalBarrier) {
michael@0:                     JSString::writeBarrierPre(str->d.u1.left);
michael@0:                     JSString::writeBarrierPre(str->d.s.u2.right);
michael@0:                 }
michael@0:                 JSString *child = str->d.u1.left;
michael@0:                 str->d.u1.chars = left.chars();
michael@0:                 child->d.s.u3.parent = str;
michael@0:                 child->d.lengthAndFlags = 0x200;
michael@0:                 str = child;
michael@0:             }
michael@0:             if (b == WithIncrementalBarrier) {
michael@0:                 JSString::writeBarrierPre(str->d.u1.left);
michael@0:                 JSString::writeBarrierPre(str->d.s.u2.right);
michael@0:             }
michael@0:             str->d.u1.chars = left.chars();
michael@0:             wholeCapacity = capacity;
michael@0:             wholeChars = const_cast<jschar *>(left.chars());
michael@0:             size_t bits = left.d.lengthAndFlags;
michael@0:             pos = wholeChars + (bits >> LENGTH_SHIFT);
michael@0:             JS_STATIC_ASSERT(!(EXTENSIBLE_FLAGS & DEPENDENT_FLAGS));
michael@0:             left.d.lengthAndFlags = bits ^ (EXTENSIBLE_FLAGS | DEPENDENT_FLAGS);
michael@0:             left.d.s.u2.base = (JSLinearString *)this;  /* will be true on exit */
michael@0:             StringWriteBarrierPostRemove(maybecx, &left.d.u1.left);
michael@0:             StringWriteBarrierPost(maybecx, (JSString **)&left.d.s.u2.base);
michael@0:             goto visit_right_child;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (!AllocChars(maybecx, wholeLength, &wholeChars, &wholeCapacity))
michael@0:         return nullptr;
michael@0: 
michael@0:     pos = wholeChars;
michael@0:     first_visit_node: {
michael@0:         if (b == WithIncrementalBarrier) {
michael@0:             JSString::writeBarrierPre(str->d.u1.left);
michael@0:             JSString::writeBarrierPre(str->d.s.u2.right);
michael@0:         }
michael@0: 
michael@0:         JSString &left = *str->d.u1.left;
michael@0:         str->d.u1.chars = pos;
michael@0:         StringWriteBarrierPostRemove(maybecx, &str->d.u1.left);
michael@0:         if (left.isRope()) {
michael@0:             left.d.s.u3.parent = str;          /* Return to this when 'left' done, */
michael@0:             left.d.lengthAndFlags = 0x200;     /* but goto visit_right_child. */
michael@0:             str = &left;
michael@0:             goto first_visit_node;
michael@0:         }
michael@0:         size_t len = left.length();
michael@0:         PodCopy(pos, left.d.u1.chars, len);
michael@0:         pos += len;
michael@0:     }
michael@0:     visit_right_child: {
michael@0:         JSString &right = *str->d.s.u2.right;
michael@0:         if (right.isRope()) {
michael@0:             right.d.s.u3.parent = str;         /* Return to this node when 'right' done, */
michael@0:             right.d.lengthAndFlags = 0x300;    /* but goto finish_node. */
michael@0:             str = &right;
michael@0:             goto first_visit_node;
michael@0:         }
michael@0:         size_t len = right.length();
michael@0:         PodCopy(pos, right.d.u1.chars, len);
michael@0:         pos += len;
michael@0:     }
michael@0:     finish_node: {
michael@0:         if (str == this) {
michael@0:             JS_ASSERT(pos == wholeChars + wholeLength);
michael@0:             *pos = '\0';
michael@0:             str->d.lengthAndFlags = buildLengthAndFlags(wholeLength, EXTENSIBLE_FLAGS);
michael@0:             str->d.u1.chars = wholeChars;
michael@0:             str->d.s.u2.capacity = wholeCapacity;
michael@0:             StringWriteBarrierPostRemove(maybecx, &str->d.u1.left);
michael@0:             StringWriteBarrierPostRemove(maybecx, &str->d.s.u2.right);
michael@0:             return &this->asFlat();
michael@0:         }
michael@0:         size_t progress = str->d.lengthAndFlags;
michael@0:         str->d.lengthAndFlags = buildLengthAndFlags(pos - str->d.u1.chars, DEPENDENT_FLAGS);
michael@0:         str->d.s.u2.base = (JSLinearString *)this;       /* will be true on exit */
michael@0:         StringWriteBarrierPost(maybecx, (JSString **)&str->d.s.u2.base);
michael@0:         str = str->d.s.u3.parent;
michael@0:         if (progress == 0x200)
michael@0:             goto visit_right_child;
michael@0:         JS_ASSERT(progress == 0x300);
michael@0:         goto finish_node;
michael@0:     }
michael@0: }
michael@0: 
michael@0: JSFlatString *
michael@0: JSRope::flatten(ExclusiveContext *maybecx)
michael@0: {
michael@0: #if JSGC_INCREMENTAL
michael@0:     if (zone()->needsBarrier())
michael@0:         return flattenInternal<WithIncrementalBarrier>(maybecx);
michael@0:     else
michael@0:         return flattenInternal<NoBarrier>(maybecx);
michael@0: #else
michael@0:     return flattenInternal<NoBarrier>(maybecx);
michael@0: #endif
michael@0: }
michael@0: 
michael@0: template <AllowGC allowGC>
michael@0: JSString *
michael@0: js::ConcatStrings(ThreadSafeContext *cx,
michael@0:                   typename MaybeRooted<JSString*, allowGC>::HandleType left,
michael@0:                   typename MaybeRooted<JSString*, allowGC>::HandleType right)
michael@0: {
michael@0:     JS_ASSERT_IF(!left->isAtom(), cx->isInsideCurrentZone(left));
michael@0:     JS_ASSERT_IF(!right->isAtom(), cx->isInsideCurrentZone(right));
michael@0: 
michael@0:     size_t leftLen = left->length();
michael@0:     if (leftLen == 0)
michael@0:         return right;
michael@0: 
michael@0:     size_t rightLen = right->length();
michael@0:     if (rightLen == 0)
michael@0:         return left;
michael@0: 
michael@0:     size_t wholeLength = leftLen + rightLen;
michael@0:     if (!JSString::validateLength(cx, wholeLength))
michael@0:         return nullptr;
michael@0: 
michael@0:     if (JSFatInlineString::lengthFits(wholeLength) && cx->isJSContext()) {
michael@0:         JSFatInlineString *str = js_NewGCFatInlineString<allowGC>(cx);
michael@0:         if (!str)
michael@0:             return nullptr;
michael@0: 
michael@0:         ScopedThreadSafeStringInspector leftInspector(left);
michael@0:         ScopedThreadSafeStringInspector rightInspector(right);
michael@0:         if (!leftInspector.ensureChars(cx) || !rightInspector.ensureChars(cx))
michael@0:             return nullptr;
michael@0: 
michael@0:         jschar *buf = str->init(wholeLength);
michael@0:         PodCopy(buf, leftInspector.chars(), leftLen);
michael@0:         PodCopy(buf + leftLen, rightInspector.chars(), rightLen);
michael@0: 
michael@0:         buf[wholeLength] = 0;
michael@0:         return str;
michael@0:     }
michael@0: 
michael@0:     return JSRope::new_<allowGC>(cx, left, right, wholeLength);
michael@0: }
michael@0: 
michael@0: template JSString *
michael@0: js::ConcatStrings<CanGC>(ThreadSafeContext *cx, HandleString left, HandleString right);
michael@0: 
michael@0: template JSString *
michael@0: js::ConcatStrings<NoGC>(ThreadSafeContext *cx, JSString *left, JSString *right);
michael@0: 
michael@0: bool
michael@0: JSDependentString::copyNonPureCharsZ(ThreadSafeContext *cx, ScopedJSFreePtr<jschar> &out) const
michael@0: {
michael@0:     JS_ASSERT(JSString::isDependent());
michael@0: 
michael@0:     size_t n = length();
michael@0:     jschar *s = cx->pod_malloc<jschar>(n + 1);
michael@0:     if (!s)
michael@0:         return false;
michael@0: 
michael@0:     PodCopy(s, chars(), n);
michael@0:     s[n] = 0;
michael@0: 
michael@0:     out.reset(s);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: JSFlatString *
michael@0: JSDependentString::undepend(ExclusiveContext *cx)
michael@0: {
michael@0:     JS_ASSERT(JSString::isDependent());
michael@0: 
michael@0:     /*
michael@0:      * We destroy the base() pointer in undepend, so we need a pre-barrier. We
michael@0:      * don't need a post-barrier because there aren't any outgoing pointers
michael@0:      * afterwards.
michael@0:      */
michael@0:     JSString::writeBarrierPre(base());
michael@0: 
michael@0:     size_t n = length();
michael@0:     size_t size = (n + 1) * sizeof(jschar);
michael@0:     jschar *s = (jschar *) cx->malloc_(size);
michael@0:     if (!s)
michael@0:         return nullptr;
michael@0: 
michael@0:     PodCopy(s, chars(), n);
michael@0:     s[n] = 0;
michael@0:     d.u1.chars = s;
michael@0: 
michael@0:     /*
michael@0:      * Transform *this into an undepended string so 'base' will remain rooted
michael@0:      * for the benefit of any other dependent string that depends on *this.
michael@0:      */
michael@0:     d.lengthAndFlags = buildLengthAndFlags(n, UNDEPENDED_FLAGS);
michael@0: 
michael@0:     return &this->asFlat();
michael@0: }
michael@0: 
michael@0: bool
michael@0: JSFlatString::isIndexSlow(uint32_t *indexp) const
michael@0: {
michael@0:     const jschar *s = charsZ();
michael@0:     jschar ch = *s;
michael@0: 
michael@0:     if (!JS7_ISDEC(ch))
michael@0:         return false;
michael@0: 
michael@0:     size_t n = length();
michael@0:     if (n > UINT32_CHAR_BUFFER_LENGTH)
michael@0:         return false;
michael@0: 
michael@0:     /*
michael@0:      * Make sure to account for the '\0' at the end of characters, dereferenced
michael@0:      * in the loop below.
michael@0:      */
michael@0:     RangedPtr<const jschar> cp(s, n + 1);
michael@0:     const RangedPtr<const jschar> end(s + n, s, n + 1);
michael@0: 
michael@0:     uint32_t index = JS7_UNDEC(*cp++);
michael@0:     uint32_t oldIndex = 0;
michael@0:     uint32_t c = 0;
michael@0: 
michael@0:     if (index != 0) {
michael@0:         while (JS7_ISDEC(*cp)) {
michael@0:             oldIndex = index;
michael@0:             c = JS7_UNDEC(*cp);
michael@0:             index = 10 * index + c;
michael@0:             cp++;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* It's not an element if there are characters after the number. */
michael@0:     if (cp != end)
michael@0:         return false;
michael@0: 
michael@0:     /*
michael@0:      * Look out for "4294967296" and larger-number strings that fit in
michael@0:      * UINT32_CHAR_BUFFER_LENGTH: only unsigned 32-bit integers shall pass.
michael@0:      */
michael@0:     if (oldIndex < UINT32_MAX / 10 || (oldIndex == UINT32_MAX / 10 && c <= (UINT32_MAX % 10))) {
michael@0:         *indexp = index;
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: bool
michael@0: ScopedThreadSafeStringInspector::ensureChars(ThreadSafeContext *cx)
michael@0: {
michael@0:     if (chars_)
michael@0:         return true;
michael@0: 
michael@0:     if (cx->isExclusiveContext()) {
michael@0:         JSLinearString *linear = str_->ensureLinear(cx->asExclusiveContext());
michael@0:         if (!linear)
michael@0:             return false;
michael@0:         chars_ = linear->chars();
michael@0:     } else {
michael@0:         if (str_->hasPureChars()) {
michael@0:             chars_ = str_->pureChars();
michael@0:         } else {
michael@0:             if (!str_->copyNonPureChars(cx, scopedChars_))
michael@0:                 return false;
michael@0:             chars_ = scopedChars_;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     JS_ASSERT(chars_);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Set up some tools to make it easier to generate large tables. After constant
michael@0:  * folding, for each n, Rn(0) is the comma-separated list R(0), R(1), ..., R(2^n-1).
michael@0:  * Similary, Rn(k) (for any k and n) generates the list R(k), R(k+1), ..., R(k+2^n-1).
michael@0:  * To use this, define R appropriately, then use Rn(0) (for some value of n), then
michael@0:  * undefine R.
michael@0:  */
michael@0: #define R2(n) R(n),  R((n) + (1 << 0)),  R((n) + (2 << 0)),  R((n) + (3 << 0))
michael@0: #define R4(n) R2(n), R2((n) + (1 << 2)), R2((n) + (2 << 2)), R2((n) + (3 << 2))
michael@0: #define R6(n) R4(n), R4((n) + (1 << 4)), R4((n) + (2 << 4)), R4((n) + (3 << 4))
michael@0: #define R7(n) R6(n), R6((n) + (1 << 6))
michael@0: 
michael@0: /*
michael@0:  * This is used when we generate our table of short strings, so the compiler is
michael@0:  * happier if we use |c| as few times as possible.
michael@0:  */
michael@0: #define FROM_SMALL_CHAR(c) jschar((c) + ((c) < 10 ? '0' :      \
michael@0:                                          (c) < 36 ? 'a' - 10 : \
michael@0:                                          'A' - 36))
michael@0: 
michael@0: /*
michael@0:  * Declare length-2 strings. We only store strings where both characters are
michael@0:  * alphanumeric. The lower 10 short chars are the numerals, the next 26 are
michael@0:  * the lowercase letters, and the next 26 are the uppercase letters.
michael@0:  */
michael@0: #define TO_SMALL_CHAR(c) ((c) >= '0' && (c) <= '9' ? (c) - '0' :              \
michael@0:                           (c) >= 'a' && (c) <= 'z' ? (c) - 'a' + 10 :         \
michael@0:                           (c) >= 'A' && (c) <= 'Z' ? (c) - 'A' + 36 :         \
michael@0:                           StaticStrings::INVALID_SMALL_CHAR)
michael@0: 
michael@0: #define R TO_SMALL_CHAR
michael@0: const StaticStrings::SmallChar StaticStrings::toSmallChar[] = { R7(0) };
michael@0: #undef R
michael@0: 
michael@0: bool
michael@0: StaticStrings::init(JSContext *cx)
michael@0: {
michael@0:     AutoLockForExclusiveAccess lock(cx);
michael@0:     AutoCompartment ac(cx, cx->runtime()->atomsCompartment());
michael@0: 
michael@0:     for (uint32_t i = 0; i < UNIT_STATIC_LIMIT; i++) {
michael@0:         jschar buffer[] = { jschar(i), '\0' };
michael@0:         JSFlatString *s = js_NewStringCopyN<NoGC>(cx, buffer, 1);
michael@0:         if (!s)
michael@0:             return false;
michael@0:         unitStaticTable[i] = s->morphAtomizedStringIntoPermanentAtom();
michael@0:     }
michael@0: 
michael@0:     for (uint32_t i = 0; i < NUM_SMALL_CHARS * NUM_SMALL_CHARS; i++) {
michael@0:         jschar buffer[] = { FROM_SMALL_CHAR(i >> 6), FROM_SMALL_CHAR(i & 0x3F), '\0' };
michael@0:         JSFlatString *s = js_NewStringCopyN<NoGC>(cx, buffer, 2);
michael@0:         if (!s)
michael@0:             return false;
michael@0:         length2StaticTable[i] = s->morphAtomizedStringIntoPermanentAtom();
michael@0:     }
michael@0: 
michael@0:     for (uint32_t i = 0; i < INT_STATIC_LIMIT; i++) {
michael@0:         if (i < 10) {
michael@0:             intStaticTable[i] = unitStaticTable[i + '0'];
michael@0:         } else if (i < 100) {
michael@0:             size_t index = ((size_t)TO_SMALL_CHAR((i / 10) + '0') << 6) +
michael@0:                 TO_SMALL_CHAR((i % 10) + '0');
michael@0:             intStaticTable[i] = length2StaticTable[index];
michael@0:         } else {
michael@0:             jschar buffer[] = { jschar('0' + (i / 100)),
michael@0:                                 jschar('0' + ((i / 10) % 10)),
michael@0:                                 jschar('0' + (i % 10)),
michael@0:                                 '\0' };
michael@0:             JSFlatString *s = js_NewStringCopyN<NoGC>(cx, buffer, 3);
michael@0:             if (!s)
michael@0:                 return false;
michael@0:             intStaticTable[i] = s->morphAtomizedStringIntoPermanentAtom();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: void
michael@0: StaticStrings::trace(JSTracer *trc)
michael@0: {
michael@0:     /* These strings never change, so barriers are not needed. */
michael@0: 
michael@0:     for (uint32_t i = 0; i < UNIT_STATIC_LIMIT; i++)
michael@0:         MarkPermanentAtom(trc, unitStaticTable[i], "unit-static-string");
michael@0: 
michael@0:     for (uint32_t i = 0; i < NUM_SMALL_CHARS * NUM_SMALL_CHARS; i++)
michael@0:         MarkPermanentAtom(trc, length2StaticTable[i], "length2-static-string");
michael@0: 
michael@0:     /* This may mark some strings more than once, but so be it. */
michael@0:     for (uint32_t i = 0; i < INT_STATIC_LIMIT; i++)
michael@0:         MarkPermanentAtom(trc, intStaticTable[i], "int-static-string");
michael@0: }
michael@0: 
michael@0: bool
michael@0: StaticStrings::isStatic(JSAtom *atom)
michael@0: {
michael@0:     const jschar *chars = atom->chars();
michael@0:     switch (atom->length()) {
michael@0:       case 1:
michael@0:         return chars[0] < UNIT_STATIC_LIMIT;
michael@0:       case 2:
michael@0:         return fitsInSmallChar(chars[0]) && fitsInSmallChar(chars[1]);
michael@0:       case 3:
michael@0:         if ('1' <= chars[0] && chars[0] <= '9' &&
michael@0:             '0' <= chars[1] && chars[1] <= '9' &&
michael@0:             '0' <= chars[2] && chars[2] <= '9') {
michael@0:             int i = (chars[0] - '0') * 100 +
michael@0:                       (chars[1] - '0') * 10 +
michael@0:                       (chars[2] - '0');
michael@0: 
michael@0:             return unsigned(i) < INT_STATIC_LIMIT;
michael@0:         }
michael@0:         return false;
michael@0:       default:
michael@0:         return false;
michael@0:     }
michael@0: }
michael@0: 
michael@0: #ifdef DEBUG
michael@0: void
michael@0: JSAtom::dump()
michael@0: {
michael@0:     fprintf(stderr, "JSAtom* (%p) = ", (void *) this);
michael@0:     this->JSString::dump();
michael@0: }
michael@0: #endif /* DEBUG */