jsarray.c

来自「java script test programing source code」· C语言 代码 · 共 1,865 行 · 第 1/4 页

    jsval       *localroot;     /* need one local root, for sort_compare */
} CompareArgs;

static JSBool
sort_compare(void *arg, const void *a, const void *b, int *result)
{
    jsval av = *(const jsval *)a, bv = *(const jsval *)b;
    CompareArgs *ca = (CompareArgs *) arg;
    JSContext *cx = ca->context;
    jsval fval;
    JSBool ok;

    /**
     * array_sort deals with holes and undefs on its own and they should not
     * come here.
     */
    JS_ASSERT(av != JSVAL_VOID);
    JS_ASSERT(bv != JSVAL_VOID);

    *result = 0;
    ok = JS_TRUE;
    fval = ca->fval;
    if (fval == JSVAL_NULL) {
        JSString *astr, *bstr;

        if (av != bv) {
            /*
             * Set our local root to astr in case the second js_ValueToString
             * displaces the newborn root in cx, and the GC nests under that
             * call.  Don't bother guarding the local root store with an astr
             * non-null test.  If we tag null as a string, the GC will untag,
             * null-test, and avoid dereferencing null.
             */
            astr = js_ValueToString(cx, av);
            *ca->localroot = STRING_TO_JSVAL(astr);
            if (astr && (bstr = js_ValueToString(cx, bv)))
                *result = js_CompareStrings(astr, bstr);
            else
                ok = JS_FALSE;
        }
    } else {
        jsdouble cmp;
        jsval argv[2];

        argv[0] = av;
        argv[1] = bv;
        ok = js_InternalCall(cx,
                             OBJ_GET_PARENT(cx, JSVAL_TO_OBJECT(fval)),
                             fval, 2, argv, ca->localroot);
        if (ok) {
            ok = js_ValueToNumber(cx, *ca->localroot, &cmp);

            /* Clamp cmp to -1, 0, 1. */
            if (ok) {
                if (JSDOUBLE_IS_NaN(cmp)) {
                    /*
                     * XXX report some kind of error here?  ECMA talks about
                     * 'consistent compare functions' that don't return NaN,
                     * but is silent about what the result should be.  So we
                     * currently ignore it.
                     */
                } else if (cmp != 0) {
                    *result = cmp > 0 ? 1 : -1;
                }
            }
        }
    }
    return ok;
}

static int
sort_compare_strings(void *arg, const void *a, const void *b, int *result)
{
    jsval av = *(const jsval *)a, bv = *(const jsval *)b;

    *result = (int) js_CompareStrings(JSVAL_TO_STRING(av), JSVAL_TO_STRING(bv));
    return JS_TRUE;
}

static JSBool
array_sort(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
{
    jsval fval, *vec, *pivotroot;
    CompareArgs ca;
    jsuint len, newlen, i, undefs;
    JSTempValueRooter tvr;
    JSBool hole, ok;

    /*
     * Optimize the default compare function case if all of obj's elements
     * have values of type string.
     */
    JSBool all_strings;

    if (argc > 0) {
        if (JSVAL_IS_PRIMITIVE(argv[0])) {
            JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
                                 JSMSG_BAD_SORT_ARG);
            return JS_FALSE;
        }
        fval = argv[0];
        all_strings = JS_FALSE; /* non-default compare function */
    } else {
        fval = JSVAL_NULL;
        all_strings = JS_TRUE;  /* check for all string values */
    }

    if (!js_GetLengthProperty(cx, obj, &len))
        return JS_FALSE;
    if (len == 0) {
        *rval = OBJECT_TO_JSVAL(obj);
        return JS_TRUE;
    }

    /*
     * We need a temporary array of len jsvals to hold elements of the array.
     * Check that its size does not overflow size_t, which would allow for
     * indexing beyond the end of the malloc'd vector.
     */
    if (len > ((size_t) -1) / sizeof(jsval)) {
        JS_ReportOutOfMemory(cx);
        return JS_FALSE;
    }

    vec = (jsval *) JS_malloc(cx, ((size_t) len) * sizeof(jsval));
    if (!vec)
        return JS_FALSE;

    /*
     * Initialize vec as a root. We will clear elements of vec one by
     * one while increasing tvr.count when we know that the property at
     * the corresponding index exists and its value must be rooted.
     *
     * In this way when sorting a huge mostly sparse array we will not
     * access the tail of vec corresponding to properties that do not
     * exist, allowing OS to avoiding committing RAM. See bug 330812.
     *
     * After this point control must flow through label out: to exit.
     */
    JS_PUSH_TEMP_ROOT(cx, 0, vec, &tvr);

    /*
     * By ECMA 262, 15.4.4.11, a property that does not exist (which we
     * call a "hole") is always greater than an existing property with
     * value undefined and that is always greater than any other property.
     * Thus to sort holes and undefs we simply count them, sort the rest
     * of elements, append undefs after them and then make holes after
     * undefs.
     */
    undefs = 0;
    newlen = 0;
    for (i = 0; i < len; i++) {
        /* Clear vec[newlen] before including it in the rooted set. */
        vec[newlen] = JSVAL_NULL;
        tvr.count = newlen + 1;
        ok = GetArrayElement(cx, obj, i, &hole, &vec[newlen]);
        if (!ok)
            goto out;

        if (hole)
            continue;

        if (vec[newlen] == JSVAL_VOID) {
            ++undefs;
            continue;
        }

        /* We know JSVAL_IS_STRING yields 0 or 1, so avoid a branch via &=. */
        all_strings &= JSVAL_IS_STRING(vec[newlen]);

        ++newlen;
    }

    /* Here len == newlen + undefs + number_of_holes. */
    ca.context = cx;
    ca.fval = fval;
    ca.localroot = argv + argc;       /* local GC root for temporary string */
    pivotroot    = argv + argc + 1;   /* local GC root for pivot val */
    ok = js_HeapSort(vec, (size_t) newlen, pivotroot, sizeof(jsval),
                     all_strings ? sort_compare_strings : sort_compare,
                     &ca);
    if (!ok)
        goto out;

    ok = InitArrayElements(cx, obj, 0, newlen, vec);
    if (!ok)
        goto out;

  out:
    JS_POP_TEMP_ROOT(cx, &tvr);
    JS_free(cx, vec);
    if (!ok)
        return JS_FALSE;

    /* Set undefs that sorted after the rest of elements. */
    while (undefs != 0) {
        --undefs;
        if (!SetArrayElement(cx, obj, newlen++, JSVAL_VOID))
            return JS_FALSE;
    }

    /* Re-create any holes that sorted to the end of the array. */
    while (len > newlen) {
        if (!DeleteArrayElement(cx, obj, --len))
            return JS_FALSE;
    }
    *rval = OBJECT_TO_JSVAL(obj);
    return JS_TRUE;
}

/*
 * Perl-inspired push, pop, shift, unshift, and splice methods.
 */
static JSBool
array_push(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
{
    jsuint length, newlength;

    if (!js_GetLengthProperty(cx, obj, &length))
        return JS_FALSE;
    newlength = length + argc;
    if (!InitArrayElements(cx, obj, length, newlength, argv))
        return JS_FALSE;

    /* Per ECMA-262, return the new array length. */
    if (!IndexToValue(cx, newlength, rval))
        return JS_FALSE;
    return js_SetLengthProperty(cx, obj, newlength);
}

static JSBool
array_pop(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
{
    jsuint index;
    JSBool hole;

    if (!js_GetLengthProperty(cx, obj, &index))
        return JS_FALSE;
    if (index > 0) {
        index--;

        /* Get the to-be-deleted property's value into rval. */
        if (!GetArrayElement(cx, obj, index, &hole, rval))
            return JS_FALSE;
        if (!hole && !DeleteArrayElement(cx, obj, index))
            return JS_FALSE;
    }
    return js_SetLengthProperty(cx, obj, index);
}

static JSBool
array_shift(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
{
    jsuint length, i;
    JSBool hole;

    if (!js_GetLengthProperty(cx, obj, &length))
        return JS_FALSE;
    if (length == 0) {
        *rval = JSVAL_VOID;
    } else {
        length--;

        /* Get the to-be-deleted property's value into rval ASAP. */
        if (!GetArrayElement(cx, obj, 0, &hole, rval))
            return JS_FALSE;

        /*
         * Slide down the array above the first element.
         */
        for (i = 0; i != length; i++) {
            if (!GetArrayElement(cx, obj, i + 1, &hole, &argv[0]))
                return JS_FALSE;
            if (!SetOrDeleteArrayElement(cx, obj, i, hole, argv[0]))
                return JS_FALSE;
        }

        /* Delete the only or last element when it exist. */
        if (!hole && !DeleteArrayElement(cx, obj, length))
            return JS_FALSE;
    }
    return js_SetLengthProperty(cx, obj, length);
}

static JSBool
array_unshift(JSContext *cx, JSObject *obj, uintN argc, jsval *argv,
              jsval *rval)
{
    jsuint length, last;
    jsval *vp;
    JSBool hole;

    if (!js_GetLengthProperty(cx, obj, &length))
        return JS_FALSE;
    if (argc > 0) {
        /* Slide up the array to make room for argc at the bottom. */
        if (length > 0) {
            last = length;
            vp = argv + argc;   /* local root */
            do {
                --last;
                if (!GetArrayElement(cx, obj, last, &hole, vp) ||
                    !SetOrDeleteArrayElement(cx, obj, last + argc, hole, *vp)) {
                    return JS_FALSE;
                }
            } while (last != 0);
        }

        /* Copy from argv to the bottom of the array. */
        if (!InitArrayElements(cx, obj, 0, argc, argv))
            return JS_FALSE;

        length += argc;
        if (!js_SetLengthProperty(cx, obj, length))
            return JS_FALSE;
    }

    /* Follow Perl by returning the new array length. */
    return IndexToValue(cx, length, rval);
}

static JSBool
array_splice(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
{
    jsval *vp;
    jsuint length, begin, end, count, delta, last;
    jsdouble d;
    JSBool hole;
    JSObject *obj2;

    /*
     * Nothing to do if no args.  Otherwise point vp at our one explicit local
     * root and get length.
     */
    if (argc == 0)
        return JS_TRUE;
    vp = argv + argc;
    if (!js_GetLengthProperty(cx, obj, &length))
        return JS_FALSE;

    /* Convert the first argument into a starting index. */
    if (!js_ValueToNumber(cx, *argv, &d))
        return JS_FALSE;
    d = js_DoubleToInteger(d);
    if (d < 0) {
        d += length;
        if (d < 0)
            d = 0;
    } else if (d > length) {
        d = length;
    }
    begin = (jsuint)d; /* d has been clamped to uint32 */
    argc--;
    argv++;

    /* Convert the second argument from a count into a fencepost index. */
    delta = length - begin;
    if (argc == 0) {
        count = delta;
        end = length;
    } else {
        if (!js_ValueToNumber(cx, *argv, &d))
            return JS_FALSE;
        d = js_DoubleToInteger(d);
        if (d < 0)
            d = 0;
        else if (d > delta)
            d = delta;
        count = (jsuint)d;
        end = begin + count;
        argc--;
        argv++;
    }


    /*
     * Create a new array value to return.  Our ECMA v2 proposal specs
     * that splice always returns an array value, even when given no
     * arguments.  We think this is best because it eliminates the need
     * for callers to do an extra test to handle the empty splice case.
     */
    obj2 = js_NewArrayObject(cx, 0, NULL);
    if (!obj2)
        return JS_FALSE;
    *rval = OBJECT_TO_JSVAL(obj2);

    /* If there are elements to remove, put them into the return value. */
    if (count > 0) {
        for (last = begin; last < end; last++) {
            if (!GetArrayElement(cx, obj, last, &hole, vp))
                return JS_FALSE;

            /* Copy *vp to new array unless it's a hole. */
            if (!hole && !SetArrayElement(cx, obj2, last - begin, *vp))
                return JS_FALSE;
        }

        if (!js_SetLengthProperty(cx, obj2, end - begin))
            return JS_FALSE;
    }

    /* Find the direction (up or down) to copy and make way for argv. */
    if (argc > count) {
        delta = (jsuint)argc - count;
        last = length;
        /* (uint) end could be 0, so can't use vanilla >= test */
        while (last-- > end) {
            if (!GetArrayElement(cx, obj, last, &hole, vp) ||
                !SetOrDeleteArrayElement(cx, obj, last + delta, hole, *vp)) {
                return JS_FALSE;
            }
        }
        length += delta;
    } else if (argc < count) {
        delta = count - (jsuint)argc;
        for (last = end; last < length; last++) {
            if (!GetArrayElement(cx, obj, last, &hole, vp) ||
                !SetOrDeleteArrayElement(cx, obj, last - delta, hole, *vp)) {
                return JS_FALSE;
            }
        }
        length -= delta;
    }

    /* Copy from argv into the hole to complete the splice. */
    if (!InitArrayElements(cx, obj, begin, begin + argc, argv))
        return JS_FALSE;

    /* Update length in case we deleted elements from the end. */
    return js_SetLengthProperty(cx, obj, length);
}

/*
 * Python-esque sequence operations.
 */
static JSBool
array_concat(JSContext *cx, JSObject *obj, uintN argc, jsval *argv, jsval *rval)
{
    jsval *vp, v;
    JSObject *nobj, *aobj;
    jsuint length, alength, slot;
    uintN i;
    JSBool hole;

    /* Hoist the explicit local root address computation. */
    vp = argv + argc;

    /* Treat obj as the first argument; see ECMA 15.4.4.4. */
    --argv;
    JS_ASSERT(obj == JSVAL_TO_OBJECT(argv[0]));

    /* Create a new Array object and store it in the rval local root. */
    nobj = js_NewArrayObject(cx, 0, NULL);
    if (!nobj)
        return JS_FALSE;
    *rval = OBJECT_TO_JSVAL(nobj);

    /* Loop over [0, argc] to concat args into nobj, expanding all Arrays. */
    length = 0;
    for (i = 0; i <= argc; i++) {
        v = argv[i];
        if (JSVAL_IS_OBJECT(v)) {
            aobj = JSVAL_TO_OBJECT(v);
            if (aobj && OBJ_GET_CLASS(cx, aobj) == &js_ArrayClass) {
                if (!OBJ_GET_PROPERTY(cx, aobj,
                                      ATOM_TO_JSID(cx->runtime->atomState
                                                   .lengthAtom),