Attachment #15013 for bug #14132

View Details Raw Unified Return to Bug 14132



2007-06-13  Darin Adler  <darin@apple.com>

        Reviewed by NOBODY (OOPS!).

        - fix http://bugs.webkit.org/show_bug.cgi?id=14132
          array sort with > 10000 elements sets elements > 10000 undefined

        Test: fast/js/sort-large-array.html

        * kjs/array_instance.h: Replaced pushUndefinedObjectsToEnd with
        compactForSorting, and removed ExecState parameters.

        * kjs/array_object.cpp:
        (ArrayInstance::sort): Changed to call compactForSorting.
        (ArrayInstance::compactForSorting): Do the get and delete of the
        properties directly on the property map instead of using public
        calls from JSObject. The public calls would just read the undefined
        values from the compacted sort results array!

2007-06-13  Simon Hausmann  <hausmann@kde.org>

        Reviewed by Lars.



/*
 *  This file is part of the KDE libraries
 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
 *  Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public


    void setLength(unsigned newLength, ExecState *exec);
    
    unsigned compactForSorting();
    
    void resizeStorage(unsigned);




/*
 *  This file is part of the KDE libraries
 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
 *  Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
 *  Copyright (C) 2003 Peter Kelly (pmk@post.com)
 *  Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
 *


void ArrayInstance::sort(ExecState* exec)
{
    size_t lengthNotIncludingUndefined = compactForSorting();
      
    ExecState* oldExec = execForCompareByStringForQSort;
    execForCompareByStringForQSort = exec;


void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)
{
    size_t lengthNotIncludingUndefined = compactForSorting();

    CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments;
    CompareWithCompareFunctionArguments args(exec, compareFunction);

    compareWithCompareFunctionArguments = oldArgs;
}

unsigned ArrayInstance::compactForSorting()
{
    JSValue *undefined = jsUndefined();


    PropertyNameArrayIterator end = sparseProperties.end();
    for (PropertyNameArrayIterator it = sparseProperties.begin(); it != end; ++it) {
        Identifier name = *it;
        storage[o] = getDirect(name);
        _prop.remove(name);
        o++;
    }
    



2007-06-13  Darin Adler  <darin@apple.com>

        Reviewed by NOBODY (OOPS!).

        - test for http://bugs.webkit.org/show_bug.cgi?id=14132
          array sort with > 10000 elements sets elements > 10000 undefined

        * fast/js/resources/sort-large-array.js: Added.
        * fast/js/sort-large-array-expected.txt: Added.
        * fast/js/sort-large-array.html: Added.

2007-06-10  Geoffrey Garen  <ggaren@apple.com>

        Reviewed by Beth Dakin.

Line 0 LayoutTests/fast/js/sort-large-array-expected.txt_sec1
- LayoutTests/fast/js/sort-large-array-expected.txt +14 lines
	1	This tests sorting an array with more than 10,000 values.
	2
	3	On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
	4
	5
	6	PASS test.length is 10010
	7	PASS test[9999] is 9999
	8	PASS test[10000] is 10000
	9	PASS test.slice(0, 20).join(', ') is '0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19'
	10	PASS test.slice(9990, 10010).join(', ') is '9990, 9991, 9992, 9993, 9994, 9995, 9996, 9997, 9998, 9999, 10000, 10001, 10002, 10003, 10004, 10005, 10006, 10007, 10008, 10009'
	11	PASS successfullyParsed is true
	12
	13	TEST COMPLETE
	14



<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
<head>
<link rel="stylesheet" href="resources/js-test-style.css">
<script src="resources/js-test-pre.js"></script>
</head>
<body>
<p id="description"></p>
<div id="console"></div>
<script src="resources/sort-large-array.js"></script>
<script src="resources/js-test-post.js"></script>
</body>
</html>

Line 0 LayoutTests/fast/js/resources/sort-large-array.js_sec1
- LayoutTests/fast/js/resources/sort-large-array.js +14 lines
	1	description("This tests sorting an array with more than 10,000 values.");
	2
	3	var test = [];
	4	for (var i = 0; i < 10010; i++)
	5	test.push(10009 - i);
	6	test.sort(function(a,b) {return a - b;});
	7
	8	shouldBe("test.length", "10010");
	9	shouldBe("test[9999]", "9999");
	10	shouldBe("test[10000]", "10000");
	11	shouldBe("test.slice(0, 20).join(', ')", "'0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19'");
	12	shouldBe("test.slice(9990, 10010).join(', ')", "'9990, 9991, 9992, 9993, 9994, 9995, 9996, 9997, 9998, 9999, 10000, 10001, 10002, 10003, 10004, 10005, 10006, 10007, 10008, 10009'");
	13
	14	var successfullyParsed = true;

Return to Bug 14132

Lines 2-8 JavaScriptCore/kjs/array_instance.h_sec1
- JavaScriptCore/kjs/array_instance.h -2 / +2 lines
2	/*	2	/*
3	* This file is part of the KDE libraries	3	* This file is part of the KDE libraries
4	* Copyright (C) 1999-2000 Harri Porten (porten@kde.org)	4	* Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
5	* Copyright (C) 2003 Apple Computer, Inc.	5	* Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
6	*	6	*
7	* This library is free software; you can redistribute it and/or	7	* This library is free software; you can redistribute it and/or
8	* modify it under the terms of the GNU Lesser General Public	8	* modify it under the terms of the GNU Lesser General Public
Lines 57-63 namespace KJS { JavaScriptCore/kjs/array_instance.h_sec2
57		57
58	void setLength(unsigned newLength, ExecState *exec);	58	void setLength(unsigned newLength, ExecState *exec);
59		59
60	unsigned pushUndefinedObjectsToEnd(ExecState *exec);	60	unsigned compactForSorting();
61		61
62	void resizeStorage(unsigned);	62	void resizeStorage(unsigned);
63		63

Lines 2-8 JavaScriptCore/kjs/array_object.cpp_sec1
- JavaScriptCore/kjs/array_object.cpp -6 / +6 lines
2	/*	2	/*
3	* This file is part of the KDE libraries	3	* This file is part of the KDE libraries
4	* Copyright (C) 1999-2000 Harri Porten (porten@kde.org)	4	* Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
5	* Copyright (C) 2003 Apple Computer, Inc.	5	* Copyright (C) 2003, 2007 Apple Inc. All rights reserved.
6	* Copyright (C) 2003 Peter Kelly (pmk@post.com)	6	* Copyright (C) 2003 Peter Kelly (pmk@post.com)
7	* Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)	7	* Copyright (C) 2006 Alexey Proskuryakov (ap@nypop.com)
8	*	8	*
Lines 330-336 static int compareByStringForQSort(const JavaScriptCore/kjs/array_object.cpp_sec2
330		330
331	void ArrayInstance::sort(ExecState* exec)	331	void ArrayInstance::sort(ExecState* exec)
332	{	332	{
333	size_t lengthNotIncludingUndefined = pushUndefinedObjectsToEnd(exec);	333	size_t lengthNotIncludingUndefined = compactForSorting();
334		334
335	ExecState* oldExec = execForCompareByStringForQSort;	335	ExecState* oldExec = execForCompareByStringForQSort;
336	execForCompareByStringForQSort = exec;	336	execForCompareByStringForQSort = exec;
Lines 397-403 static int compareWithCompareFunctionFor JavaScriptCore/kjs/array_object.cpp_sec3
397		397
398	void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)	398	void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)
399	{	399	{
400	size_t lengthNotIncludingUndefined = pushUndefinedObjectsToEnd(exec);	400	size_t lengthNotIncludingUndefined = compactForSorting();
401		401
402	CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments;	402	CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments;
403	CompareWithCompareFunctionArguments args(exec, compareFunction);	403	CompareWithCompareFunctionArguments args(exec, compareFunction);
Lines 422-428 void ArrayInstance::sort(ExecState* exec JavaScriptCore/kjs/array_object.cpp_sec4
422	compareWithCompareFunctionArguments = oldArgs;	422	compareWithCompareFunctionArguments = oldArgs;
423	}	423	}
424		424
425	unsigned ArrayInstance::pushUndefinedObjectsToEnd(ExecState *exec)	425	unsigned ArrayInstance::compactForSorting()
426	{	426	{
427	JSValue *undefined = jsUndefined();	427	JSValue *undefined = jsUndefined();
428		428
Lines 447-454 unsigned ArrayInstance::pushUndefinedObj JavaScriptCore/kjs/array_object.cpp_sec5
447	PropertyNameArrayIterator end = sparseProperties.end();	447	PropertyNameArrayIterator end = sparseProperties.end();
448	for (PropertyNameArrayIterator it = sparseProperties.begin(); it != end; ++it) {	448	for (PropertyNameArrayIterator it = sparseProperties.begin(); it != end; ++it) {
449	Identifier name = *it;	449	Identifier name = *it;
450	storage[o] = get(exec, name);	450	storage[o] = getDirect(name);
451	JSObject::deleteProperty(exec, name);	451	_prop.remove(name);
452	o++;	452	o++;
453	}	453	}
454		454

Lines 1-3 JavaScriptCore/ChangeLog_sec1
- JavaScriptCore/ChangeLog +19 lines
		1	2007-06-13 Darin Adler <darin@apple.com>
		2
		3	Reviewed by NOBODY (OOPS!).
		4
		5	- fix http://bugs.webkit.org/show_bug.cgi?id=14132
		6	array sort with > 10000 elements sets elements > 10000 undefined
		7
		8	Test: fast/js/sort-large-array.html
		9
		10	* kjs/array_instance.h: Replaced pushUndefinedObjectsToEnd with
		11	compactForSorting, and removed ExecState parameters.
		12
		13	* kjs/array_object.cpp:
		14	(ArrayInstance::sort): Changed to call compactForSorting.
		15	(ArrayInstance::compactForSorting): Do the get and delete of the
		16	properties directly on the property map instead of using public
		17	calls from JSObject. The public calls would just read the undefined
		18	values from the compacted sort results array!
		19
1	2007-06-13 Simon Hausmann <hausmann@kde.org>	20	2007-06-13 Simon Hausmann <hausmann@kde.org>
2		21
3	Reviewed by Lars.	22	Reviewed by Lars.

Lines 1-3 LayoutTests/ChangeLog_sec1
- LayoutTests/ChangeLog +11 lines
		1	2007-06-13 Darin Adler <darin@apple.com>
		2
		3	Reviewed by NOBODY (OOPS!).
		4
		5	- test for http://bugs.webkit.org/show_bug.cgi?id=14132
		6	array sort with > 10000 elements sets elements > 10000 undefined
		7
		8	* fast/js/resources/sort-large-array.js: Added.
		9	* fast/js/sort-large-array-expected.txt: Added.
		10	* fast/js/sort-large-array.html: Added.
		11
1	2007-06-10 Geoffrey Garen <ggaren@apple.com>	12	2007-06-10 Geoffrey Garen <ggaren@apple.com>
2		13
3	Reviewed by Beth Dakin.	14	Reviewed by Beth Dakin.

Line 0 LayoutTests/fast/js/sort-large-array.html_sec1
- LayoutTests/fast/js/sort-large-array.html +13 lines
	1	<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
	2	<html>
	3	<head>
	4	<link rel="stylesheet" href="resources/js-test-style.css">
	5	<script src="resources/js-test-pre.js"></script>
	6	</head>
	7	<body>
	8	<p id="description"></p>
	9	<div id="console"></div>
	10	<script src="resources/sort-large-array.js"></script>
	11	<script src="resources/js-test-post.js"></script>
	12	</body>
	13	</html>