1231204 - Add JSAPI for accessing strings in a rope

Status: RESOLVED INVALID

(Core :: JavaScript Engine, defect)

Description

[Michael Wu [:mwu]]

Being able to access the branches in the rope lets us iterate over the contents of the string without making a copy to a linear string.

Comment 1

[Jeff Walden [:Waldo]]

A couple questions to resolve here.

Is it okay for the JSAPI access to be rooting-unsafe, or to require no heap accesses happen while the iteration is in progress?  That simplifies life somewhat, because it means the iteration doesn't have to take extra steps to ensure the string being iterated over (or its subcomponents) will disappear underneath iteration.

What's the strategy to track current iteration state?  Ropey stuff doesn't point to its parent (there might be multiple parents), so you can't just do it saving just the current node.  Gobbling up all the parts into a vector is easy but may involve allocation, which may well defeat the purpose of this JSAPI, depending.  If you can guarantee no heap accesses, you probably can mutate the pointer contents of the JSString structure in-place to track iteration state.  JSRope::flattenInternal does this right now.  But it's horrifically complicated and tricky (and much worse since moving GC/barriers came into play), and I wouldn't wish upon my worst enemies debugging mistakes made if someone did access the string in the heap.  :-)

Comment 2

[Jason Orendorff [:jorendorff]]

Suppose we do this:

    namespace JS {
    JSString* NewRope(JSContext* cx, StringHandle left, StringHandle right);
    bool StringIsRope(JSContext* cx, StringHandle str);
    void GetRopeHalves(JSContext* cx, MutableStringHandle left, MutableStringHandle right);
    }

mwu: Is that good enough? Every string is either a rope or a JSLinearString.

Comment 3

[Morgan Phillips [:mrrrgn]]

Attachment: ropeapi.diff

Still double checking my usage of jsapi here since I'm a newb. Hopefully this is close.

Comment 4

[Morgan Phillips [:mrrrgn]]

Attachment: ropeapi.diff

Comment 5

[Michael Wu [:mwu]]

Weird, I remember commenting here. Where did the comment go...

I like the API, though JS::NewRope seems to be redundant with JS_ConcatStrings. Maybe JS::NewRope gives you a better guarantee that you'll get a rope back? (In which case, DOM can abuse js ropes as a binary tree which could be pretty fun.)

Comment 6

[Jan de Mooij [:jandem]]

(In reply to Michael Wu [:mwu] from comment #5)
> I like the API, though JS::NewRope seems to be redundant with
> JS_ConcatStrings. Maybe JS::NewRope gives you a better guarantee that you'll
> get a rope back? (In which case, DOM can abuse js ropes as a binary tree
> which could be pretty fun.)

(ConcatStrings also ensures the length does not exceed JSString::MAX_LENGTH, and optimizes things like x + "" to just return x.)

Comment 7

[Jason Orendorff [:jorendorff]]

Comment on attachment 8697052 [details] [diff] [review]
ropeapi.diff

Review of attachment 8697052 [details] [diff] [review]:
-----------------------------------------------------------------

OK, r=me, but please don't land this yet! I want to hear from mwu first whether or not this is helpful.

::: js/src/jsapi.cpp
@@ +4772,5 @@
> +JS::GetRopeHalves(JSContext *cx, HandleString rope, MutableHandleString left, MutableHandleString right) {
> +    AssertHeapIsIdle(cx);
> +    CHECK_REQUEST(cx);
> +
> +    MOZ_ASSERT(rope->isRope());

Please delete this assertion. The house style is

*   don't assert things if they're about to be asserted anyway, and

*   all downcast-methods, like asRope(), do the assertion for you.

Comment 8

[Morgan Phillips [:mrrrgn]]

(In reply to Jan de Mooij [:jandem] from comment #6)
> (In reply to Michael Wu [:mwu] from comment #5)
> > I like the API, though JS::NewRope seems to be redundant with
> > JS_ConcatStrings. Maybe JS::NewRope gives you a better guarantee that you'll
> > get a rope back? (In which case, DOM can abuse js ropes as a binary tree
> > which could be pretty fun.)
> 
> (ConcatStrings also ensures the length does not exceed JSString::MAX_LENGTH,
> and optimizes things like x + "" to just return x.)

I'll add that check into JS::NewRope, I think it makes sense to have a function that _only_ returns ropes since concat can't guarantee that.

Comment 9

[Morgan Phillips [:mrrrgn]]

Attachment: ropeapi.diff

Sorry for the extra review, I went ahead and added zone and max string length checks to JS::NewRope.

Comment 10

[Jason Orendorff [:jorendorff]]

After talking with mwu about his use case, I think we probably shouldn't land this.


## Background

mwu's plan is for Servo to support:

1.  doing document.createTextNode(s) on the main thread, where s is a rope
2.  running layout on a background thread and laying out the text without copies

GC and JS would be disabled during (2). Ultimately, mwu wants to allow scripts to run on the main thread, racing freely with (2) as long as they don't touch the DOM or do GC; there would be some locking around the DOM to prevent bad races.


## Is this a good idea?

Runtimes are single-threaded. The JSAPI asserts like mad if you use it off-thread (mwu has disabled "one" assertion to get this to work, I don't know where).

It's generally not a super great idea to use a massive single-threaded C++ codebase in a multi-threaded way, reasoning that you understand well enough what the library does with memory[*] and layering your own locking on top. It's C++: there's mutation in unexpected places. We all agreed that accessing ropes while main-thread content can touch them is unsafe; there are less obvious uses of state in SM too.

And yet if we ever want to self-host the DOM in JS for real, we'll need to access data off-thread.


## Conclusion

For now, mwu can linearize the strings on the main thread.

If self-hosting the DOM wins out, we'll have to offer new API for off-thread access.



[*]: A locking scheme requires the cooperation of all code accessing the lock-protected memory. Making this explicit and enforcing it with the borrow checker is what makes Rust's Mutex safe.

Comment 11

[Morgan Phillips [:mrrrgn]]

Putting this one on the shelf. :)