304376 - String = Array changes strings to have Array's prototype

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Blake Kaplan (:mrbkap) (inactive)]

This actually causes a crash in one instance. I'll attach a wallpaper for the
crash in a second.

According to Ecma-262, 15.5.2.1, the string constructor creates a new object
with "original String prototype object, the one that is the initial value of
String.prototype (15.5.3.1)." When I set |String = Array|, subsequent string
objects have Array prototypes. Brendan interprets this to mean that we're not
compliant with the spec.

Comment 1

[Blake Kaplan (:mrbkap) (inactive)]

Attachment: wallpaper over the crash

Steps to reproduce the crash:
js> String = Array
function Array() {
    [native code]
}
js> "".join()
<crash>

This is caused by js_EnterSharpObject not incrementing map->depth when it
creates the hash table. The problem is that we end up re-entering it when
enumerating the properties while marking the incoming object as sharp. Its
subsequent attempts to used the destroyed (null'd out) hash table cause a
segfault.

Comment 2

[Blake Kaplan (:mrbkap) (inactive)]

(timeless gets credit for influencing the testcase that found this crash).

Comment 3

[Brendan Eich [:brendan]]

Comment on attachment 192446 [details] [diff] [review]
wallpaper over the crash

r=me, but I would not say this is a Hack unless you can show a cleaner patch
that forks the initial condition earlier, and sets map->depth to 1 right away. 
I bet that's not a cleaner patch.

If you agree, remove the "Hack: ".  Oh, and s/since/because/ (or s/since/as/),
usage nit of the day.

This particular fix is safe for 1.8b4.	Go fast!

/be

Comment 4

[Blake Kaplan (:mrbkap) (inactive)]

Attachment 192446 [details] [diff] is checked in. I'm leaving this bug open to solve the more
general issue of String's prototype getting replaced.

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #4)
> I'm leaving this bug open to solve the more
> general issue of String's prototype getting replaced.

String.prototype is readonly and permanent, so it's really String that is
getting replaced, along with all the other standard class constructors defined
in section 15 of ECMA-262 Edition 3.

The fix here will entail some kind of per-global-object peer data structure
containing the initial value of the standard class prototypes.  We could stick
'em in the cx used to init standard classes, but API compatibility for JS_Get-
and JS_SetGlobalObject/JS_InitStandardClasses says we have to be prepared to
swap out the prototype pointers, swapping in those associated with the new obj
being set.

What's more, it is possible to JS_SetGlobalObject with a non-null obj, then call
JS_InitStandardClasses with a different obj param (perhaps one related by proto
or parent linkage; perhaps not).  So we can't just store the root-by-definition
proto pointers in cx -- we need a runtime-wide mapping from "global" obj (scope
obj, really) to proto-roots.

/be

Comment 6

[Brendan Eich [:brendan]]

The reason JS_InitStandardClasses (actually, InitFunctionAndObjectClasses) calls
JS_SetGlobalObject if (!cx->globalObject) is so that js_FindConstructor can find
a class-named constructor or prototype without any frames active on cx.  This is
a concession to ancient code, but it could be fixed by making JS_Init*Class*
push a dummy frame with scopeChain == obj.

That might not cover other APIs that can run on a cx with no frames active and
want to resolve a standard class, though.  Pushing dummy frames for a bunch of
APIs is going to bloat code and runtime, so let's stick with the august and
venerable cx->globalObject hack, I say.

We could optimize to avoid creating a proto-root peer data structure for common
cases such as Mozilla's DOM, by inlining a proto-roots struct in JSContext and
using that if (obj == cx->globalObject || !cx->globalObject).  Comments?

/be

Comment 7

[Bob Clary [:bc] (inactive)]

Checking in regress-304376.js;
/cvsroot/mozilla/js/tests/ecma_3/String/regress-304376.js,v  <--  regress-304376.js
initial revision: 1.1
done

Comment 8

[Brendan Eich [:brendan]]

Patch coming in the big one for bug 326466.

/be

Comment 9

[Brendan Eich [:brendan]]

Attachment: proposed fix

- Conform to ECMA-262 verbiage about "the original value of Object.prototype"
  as the per-instance prototype for objects created during runtime, e.g. (same
  for Array, etc.).  This patch implements a cache per JSContext of prototypes
  indexed by a well-known int id (dense index).  Care required to avoid dynamic
  scope bugs.  Well-known native classes include JSCLASS_CACHED_PROTO_KEY(key)
  in their flags initializer to associate their int prototype cache id.  Using
  this flags field, js_NewObject can avoid a global object lookup.
- Fix JS_ValueToId to return object-tagged XML ids given QName, AttributeName,
  and AnyName object values.
- Add JSCLASS_IS_ANONYMOUS for initialized classes that should not bind their
  class name to a constructor or prototype.
- Split out JS_GetMethodById API from JS_GetMethod (former takes a jsid id,
  latter takes a const char *name).
- Factor js_MarkStackFrame from js_GC, for future use from generator_mark.

/be

Comment 10

[Brendan Eich [:brendan]]

Comment on attachment 218767 [details] [diff] [review]
proposed fix

Urgh, forgot to re-diff after my own review.

/be

Comment 11

[Brendan Eich [:brendan]]

Attachment: proposed fix

See next-to-last comment for proposed checkin message.

/be

Comment 12

[Brendan Eich [:brendan]]

Comment on attachment 218768 [details] [diff] [review]
proposed fix

Igor, feel free to review if you have time.  This follows up on some recently patched areas of common interest.

/be

Comment 13

[Brendan Eich [:brendan]]

Attachment: consarnit, left out two files

Comment 14

[Brendan Eich [:brendan]]

This is going in first, so reversing dependency.

/be

Comment 15

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 218777 [details] [diff] [review]
consarnit, left out two files

Nice! r=mrbkap

Comment 16

[Igor Bukanov]

I run the test from bug 325724 comment 1.  The patch for this bug slows down js shell by 2% while the patch from bug 325724 makes things faster by 10%. (Be aware  of the patch from bug 334261 that optimises aways object creation and makes test useless when applied!)

But this is strange as it seems the patch should make the same speedup as the idea behind bug 325724 even for the single threaded case. Any reason for this?

Comment 17

[Andreas]

String= Array, "".join()

still doesn't work as expected (should throw TypeError because the original
String prototype has no callable property named "join").

Another case:

js> String= Number, "".valueOf()
typein:1: strict warning: assignment to undeclared variable String
typein:1: TypeError: Number.prototype.valueOf called on incompatible String

Both with and without the patch for bug 334261. (Is the warning a bug?)

Comment 18

[Brendan Eich [:brendan]]

A bunch of JSCLASS_HAS_CACHED_PROTO(JSProto_...) flag setting is missing.  Plus, jsproto.tbl is bereft of init functions.  This explains the performance loss due to futile extra checking of js_GetCachedPrototype.  Fixing, should be much better soon.

/be

Comment 19

[Brendan Eich [:brendan]]

Attachment: the rest of the story...

This was work.

/be

Comment 20

[Brendan Eich [:brendan]]

Comment on attachment 218777 [details] [diff] [review]
consarnit, left out two files

Igor, please feel free to review the sum of the two latest patches -- sorry for the mess.

/be

Comment 21

[Brendan Eich [:brendan]]

(In reply to comment #17)
> String= Array, "".join()
> 
> still doesn't work as expected (should throw TypeError because the original
> String prototype has no callable property named "join").

Works now:

js> String = Array, "".join()
typein:1: TypeError: "".join is not a function

> Another case:
> 
> js> String= Number, "".valueOf()
> typein:1: strict warning: assignment to undeclared variable String
> typein:1: TypeError: Number.prototype.valueOf called on incompatible String

Works also:

js> String = Number, "".valueOf()

js>

> Both with and without the patch for bug 334261. (Is the warning a bug?)

The warning is an odd interaction between lazy standard class initialization via JS_ResolveStandardClass, done only if the name being resolved is not on the left side of assignment.  Perhaps (and this bug would have been helped by it) the global_resolve code, and similar code in the Gecko DOM, should resolve whether or not the name is on the left of assignment.

Igor, with your test from bug 325724 comment 1, with 1000*1000 passed instead of 100*1000, I see a best-of-three speedup from 942 to 871 with the patches for this bug applied.

/be

Comment 22

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 219076 [details] [diff] [review]
the rest of the story...

r=mrbkap

Comment 23

[Brendan Eich [:brendan]]

Final patch checked in.  Anything still not quite right should be reported in a followup bug.

/be

Comment 24

[Brendan Eich [:brendan]]

Attachment: brain-damage is contagious

Sloppy, late night hacking -- no excuse.  This fixes the orange tinderboxes.

/be

Comment 25

[Brendan Eich [:brendan]]

Attachment: XDR is bi-directional, data flow is hard

Comment 26

[Blake Kaplan (:mrbkap) (inactive)]

Comment on attachment 219090 [details] [diff] [review]
XDR is bi-directional, data flow is hard

But it's so symetric or something...

Comment 27

[Andreas]

I filed bug 334807 for the arguments object still being affected by
assignment to Object, but I do not know what should happen with object
and array literals. The spec says:

  Create a new object/array as if by the expression new Object()/Array().

It is unclear if this simply refers to section 15.2.2.1/15.4.2.1 or means
to use the value of Object resp. Array at the time of evaluation. Current
behaviour is the latter.

Furthermore, the description of the Object constructor doesn't refer to the
/original/ value of Object.prototype, unlike all the other constructors.

Comment 28

[Igor Bukanov]

> Igor, with your test from bug 325724 comment 1, with 1000*1000 passed instead
> of 100*1000, I see a best-of-three speedup from 942 to 871 with the patches for
> this bug applied.


In fact I run already the test with N set to 10**6. My numbers for the optimized build of js shell under 2.6 Ghz Pentium-4 box with Ubuntu 5.10/GCC 4.0:

Without the patch (CVS tree from 2006-04-17): 1185
With the patch (Current CVS HEAD): 1133
With the patch from bug 325724 apllied for CVS tree from 2006-04-17: 1059

That is, the speedup from the last patch is less then halve then the speedup from the patch in bug 325724. The question is why?

Comment 29

[Andreas]

Such a small testcase measures much random noise. My similar testcase from
bug 334261 has this results for str.length (without the patch for bug 334261):

                    before    now
compiled with -O1:   3791    4109
compiled with -O2:   3133    2885

(This is on an Athlon, where performance depends very much on how good jump
targets happen to be aligned, and compiled without -march set)

Comment 30

[Igor Bukanov]

(In reply to comment #29)
> Such a small testcase measures much random noise. My similar testcase from
> bug 334261 has this results for str.length (without the patch for bug 334261):
> 
>                     before    now
> compiled with -O1:   3791    4109
> compiled with -O2:   3133    2885
> 
> (This is on an Athlon, where performance depends very much on how good jump
> targets happen to be aligned, and compiled without -march set)

Could you also check the patch from the patch from bug 325724 apllied for CVS tree from 2006-04-17 ?

Comment 31

[Igor Bukanov]

Here is my data with -O2 (2.6 Ghz Pentium-4 box with Ubuntu 5.10/GCC
4.0):

                                before    now   bug 334261 
compiled with -O:     1185    1133   1059
compiled with -O2:   1111    1033   951

So the conclusion is the same: the speedup from bug 334261 is 2 times greater that this patch. 

It seems that for the single threaded case this patch brings too much code to look for cached classes compared to property lookup for known atoms.

Comment 32

[Igor Bukanov]

Here is stats for jsshell compiled with JS_THREADSAFE=1 (note that to compile against CVS 2006-04-17 config.mk and Makefile.ref should be kept from HEAD as fixes to allow such compilation was committed after the patch):

                                before    now   bug 334261 
With JS_THREADSAFE:
compiled with -O:     1761    1586   1505
compiled with -O2:   1670    1493   1491

Without JS_THREADSAFE:
compiled with -O:     1185    1133   1059
compiled with -O2:   1111    1033   951

I interpret this as the code in the patch is not optimized for the single threaded case while its more complex nature requires more efforts for the compiler to optimize with JS_THREADSAFE defined.

Comment 33

[Brendan Eich [:brendan]]

I'll try to get VS8 numbers, but anyone with similar hardware who can use MS's fine compilers, please report results.

/be

Comment 34

[Brendan Eich [:brendan]]

Just for the record, Blake and I at least are pretty put off by ECMA-262's weird "the original Foo prototype object" language.  Note how 15.11.7.2 does *not* say to use the original value of, e.g., SyntaxError.prototype.  Other lacunae noted by Andreas just beg the question: why?  If the goal is to support optimization by avoiding reflection at runtime on each construction, it would be better to try to make the global properties bound to standard constructors readonly and dontdelete.

If not for this ECMA-262 language, I would prefer Igor's patch to parameterize internal constructor calls with atoms, and not this bug's patches.  But the spec is the standard, and we probably should follow it, until we can fix it.  Anyway we should figure out how to have both patches and best performance.

I will take this up with ECMA TG1 today or tomorrow.

/be

Comment 35

[Igor Bukanov]

With the patch applied GCC complains:

jsobj.c:1810: warning: 'With' defined but not used

Before it was used in js_InitObjectClass via:

#if JS_HAS_OBJ_PROTO_PROP
    if (!JS_InitClass(cx, obj, NULL, &js_WithClass, With, 0,
                      NULL, NULL, NULL, NULL)) {
        return NULL;
    }
#endif

but now that code is gone.

Comment 36

[Robert Kaiser]

Comment on attachment 219076 [details] [diff] [review]
the rest of the story...

>         /* Bootstrap Function.prototype (see also JS_InitStandardClasses). */
>         if (OBJ_GET_CLASS(cx, ctor) == clasp) {
>-            /* XXXMLM - this fails in framesets that are writing over
>-             *           themselves!
>-             * JS_ASSERT(!OBJ_GET_PROTO(cx, ctor));
>-             */
>+            JS_ASSERT(!OBJ_GET_PROTO(cx, ctor));
>             OBJ_SET_PROTO(cx, ctor, proto);
>         }
>     }

This assertion, which was introduced as a comment in June 1998 and never was actually live until today, now fires and causes problems, see bug 334834

Comment 37

[Andreas]

(In reply to comment #30)
> Could you also check the patch from the patch from bug 325724 apllied for CVS
> tree from 2006-04-17 ?

Loop overhead and total time, minimum of 8:

       2006-04-18   2006-04-20   bug 325724   bug 334261

-O0     261  6394    266  4440    256  4454    260   567
-O1     183  3775    178  4150    188  3005    179   369
-O2     175  2951    175  2726    178  2611    173   337
-O2a    169  3171    169  2515    172  2474    172   343
-O3a    141  2759    143  2299    141  2315    139   288

2006-04-18 := CVS 2006-04-18 12:00 UTC
2006-04-20 := CVS synced early today
bug 325724 := 2006-04-18 + attachment 218944 [details] [diff] [review]
bug 334261 := 2006-04-20 + attachment 219038 [details] [diff] [review]

-O0  := -O0
-O1  := -O1
-O2  := -O2 -fomit-frame-pointer
-O2a := -O2 -fomit-frame-pointer -march=athlon
-O3a := -O3 -fomit-frame-pointer -march=athlon

Testcase used (to minimize loop overhead):

var n= 1e6, m= 8;

function test0() {
  var i= n, str= "str", now= Date.now, t= now();
  do str; while ( --i );
  return now() - t;
}

function test() {
  var i= n, str= "str", now= Date.now, t= now();
  do str.length; while ( --i );
  return now() - t;
}

for ( var a0= [], a= [], i= 0; i < m; ++i )
  a0.push( test0() ), a.push( test() );

print( Math.min.apply( null, a0 ), Math.min.apply( null, a ) );

Comment 38

[Andreas]

The times above were probably without any GC. Forcing GC to be included by
setting ulimit -v 4096, I get these results:

       2006-04-18   2006-04-20   bug 325724   bug 334261

-O0     258  7052    265  5169    254  5144    258   566
-O1     183  4217    176  4619    186  3441    178   365
-O2     174  3361    174  3183    177  3044    172   335
-O2a    168  3584    168  2974    171  2894    171   341
-O3a    140  3178    141  2785    140  2712    139   284

Comment 39

[Andreas]

This broke compiling with JS_VERSION < 160 because of missing
#if JS_HAS_XML_SUPPORT in jsproto.tbl.

Comment 40

[Andreas]

(In reply to comment #39)
> This broke compiling with JS_VERSION < 160 because of missing
> #if JS_HAS_XML_SUPPORT in jsproto.tbl.

Filed bug 335001.

Comment 41

[Bob Clary [:bc] (inactive)]

ecma_3/String/regress-304376.js fails in the browser with  
Expected value 'String', Actual value 'Array' FAILED!: 
and in the shell with TypeError: "".join is not a function 

The TypeError looks right. I'll modify the test to catch the exception. Not sure why the browser test fails.

Comment 42

[Bob Clary [:bc] (inactive)]

Attachment: ecma_3/String/regress-304376.js

browser:

BUGNUMBER: 304376
STATUS: String.prototype should be readonly and permanent
FAILED!: String.prototype should be readonly and permanent
FAILED!: Expected value 'String', Actual value 'Array'
FAILED!:
FAILED!: String.prototype should be readonly and permanent
FAILED!: Expected value 'TypeError', Actual value 'No Error'
FAILED!:

shell:
Testcase ecma_3/String/regress-304376.js failed Bug Number 304376
[ Top of Page ]
STATUS: String.prototype should be readonly and permanent
STATUS: TypeError: "".join is not a function
Failure messages were:
FAILED!: String.prototype should be readonly and permanent
FAILED!: Expected value 'String', Actual value 'Array'
FAILED!:

Comment 43

[Brendan Eich [:brendan]]

mrbkap is all over this.  The browser embedding has inner and outer globals, and the cached class object logic is blissfully ignorant of the rules for innerizing and outerizing.

/be

Comment 44

[Bob Clary [:bc] (inactive)]

remove bogus check for the prototype name
Checking in regress-304376.js;
/cvsroot/mozilla/js/tests/ecma_3/String/regress-304376.js,v  <--  regress-304376.js
new revision: 1.3; previous revision: 1.2

Comment 45

[Blake Kaplan (:mrbkap) (inactive)]

I think this is really fixed now.

Comment 46

[Bob Clary [:bc] (inactive)]

it looks ok. I'll verify when I run it again with the fixed test case.

Checking in regress-304376.js;
/cvsroot/mozilla/js/tests/ecma_3/String/regress-304376.js,v  <--  regress-304376.js
new revision: 1.4; previous revision: 1.3
done

Comment 47

[Bob Clary [:bc] (inactive)]

Note the test case fails in the browser on the trunk with  string.replace is not a function Page: http://test.mozilla.com/tests/mozilla.org/js/ecma_3/browser.js Line: 80 but it does pass in the shell. Note the test tries to reset the String constructor prior to any calls to a String method....


expect = 'TypeError';

var saveString = String;
  
String = Array;

try
{
  // see if we can crash...
  "".join();
  String = saveString;
  actual = 'No Error';
}
catch(ex)
{
  String = saveString;
  actual = ex.name;
  printStatus(ex + '');
}

reportCompare(expect, actual, summary);

Comment 48

[Bob Clary [:bc] (inactive)]

Brendan, Blake: any idea what is wrong with my test case or if the failure to reset the String constructor is this or a new bug?

Comment 49

[Bob Clary [:bc] (inactive)]

something changed. verified fixed win/macppc/linux 2006070603 1.9a1

Comment 50

[Bob Clary [:bc] (inactive)]

fixed by Bug 336373 on the 1.8.1 branch. 
verified fixed 1.8.1 with windows/macppc/linux 20060707