Bug 89722 – Implement UndoManager's JSC bindings

• Component: HTML Editing
• Status: RESOLVED LATER

[Sukolsak Sakshuwong]

Implement undoManager's undo, redo, length, position, clearUndo,, and clearRedo

[Sukolsak Sakshuwong]

Created attachment 148926 [details]
Patch

[Sukolsak Sakshuwong]

Created attachment 148928 [details]
Patch

[Caio Marcelo de Oliveira Filho]

Comment on attachment 148928 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=148928&action=review

Nice :)  I have a couple of comments. What about the changes related to WK2 that you were asking about in IRC? Aren't they needed?

> Source/WebCore/editing/UndoManager.cpp:58
> +    if (m_undoStack.size() > 0) {

Check m_undoStack.isEmpty() and return early.

> Source/WebCore/editing/UndoManager.cpp:67
> +    if (m_redoStack.size() > 0) {

Check m_redoStack.isEmpty() and return early.

> Source/WebCore/editing/UndoManager.h:71
> +    Vector<RefPtr<UndoStep> > m_undoStack;
> +    Vector<RefPtr<UndoStep> > m_redoStack;

An ideia: I think this could be improved so it uses only one Vector and one extra index, that would be to mark the position that separate entries that can be redone and undone.

[Ryosuke Niwa]

Comment on attachment 148928 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=148928&action=review

>> Source/WebCore/editing/UndoManager.h:71
>> +    Vector<RefPtr<UndoStep> > m_redoStack;
> 
> An ideia: I think this could be improved so it uses only one Vector and one extra index, that would be to mark the position that separate entries that can be redone and undone.

If we do that, then undo or redo need to be O(n) instead of O(1).

[Caio Marcelo de Oliveira Filho]

(In reply to comment #4)
> (From update of attachment 148928 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=148928&action=review
> 
> >> Source/WebCore/editing/UndoManager.h:71
> >> +    Vector<RefPtr<UndoStep> > m_redoStack;
> > 
> > An ideia: I think this could be improved so it uses only one Vector and one extra index, that would be to mark the position that separate entries that can be redone and undone.
> 
> If we do that, then undo or redo need to be O(n) instead of O(1).

I was thinking something along these lines:

// in this case, I've applied 5 operations, last one was e.
//
// vector = [a, b, c, d, e]
// index = 4

apply():
    increment index
    set vector[index] to new entry
    apply the new entry
    resize the vector to index + 1

undo():
    if (index < 0)
        return
    unapply the entry at vector[index]
    decrement index

redo():
    if (index + 1 >= vector.size)
        return
    increment index
    reapply the entry at vector[index]

[Ryosuke Niwa]

Oops, I meant to say clearRedo and clearUndo. Making clearRedo fast is pretty important because we do that all the time.

[Caio Marcelo de Oliveira Filho]

Another question: how the WebKit layer will get informed about the undo/redo steps?

[Caio Marcelo de Oliveira Filho]

(In reply to comment #6)
> Oops, I meant to say clearRedo and clearUndo. Making clearRedo fast is pretty important because we do that all the time.

Well, clearRedo() could use Vector::shrinkCapacity(index + 1) like I sketched in the pseudo code for apply(). In this patch is implemented as m_redoStack.clear() which in practice is shrinkCapacity(0). So I don't see the difference.

But yes, for clearUndo(), when there are entries for redo, we have some memory move. How common is this case (clearUndo without clearRedo)?

[Sukolsak Sakshuwong]

Created attachment 149124 [details]
Patch

[Caio Marcelo de Oliveira Filho]

Comment on attachment 149124 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=149124&action=review

> Source/WebKit/qt/WebCoreSupport/EditorClientQt.cpp:338
>  void EditorClientQt::undo()
>  {
> +#if !ENABLE(UNDO_MANAGER)
>  #ifndef QT_NO_UNDOSTACK
>      m_inUndoRedo = true;
>      m_page->undoStack()->undo();
>      m_inUndoRedo = false;
>  #endif
> +#else
> +    Frame* frame = m_page->d->page->focusController()->focusedOrMainFrame();
> +    if (!frame)
> +        return;
> +    Document* document = frame->document();
> +    if (!document)
> +        return;
> +    document->undoManager()->undo();
> +#endif
>  }

I think there's something wrong with these changes to EditorClients. If we have UNDO_MANAGER enabled, these client functions will not be called.

[Sukolsak Sakshuwong]

Created attachment 149157 [details]
Patch

[Sukolsak Sakshuwong]

Created attachment 149160 [details]
Patch

[Sukolsak Sakshuwong]

(In reply to comment #7)
> Another question: how the WebKit layer will get informed about the undo/redo steps?

The WebKit layer will call WebCore::Editor for information, which will in turn call WebCore::UndoManager.

For example, in WebKit/gtk/webkit/webkitwebview.cpp, we have "webkit_web_view_real_redo" calling "frame->editor()->command("Redo").execute()" and "webkit_web_view_can_redo" calling "frame->editor()->canRedo()".

(In reply to comment #3)
> (From update of attachment 148928 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=148928&action=review
> 
> Nice :)  I have a couple of comments. What about the changes related to WK2 that you were asking about in IRC? Aren't they needed?

There are some issues with the Mac port that I found while implementing it. On GTK, EFL, Chromium, and BlackBerry, WebKit maintains its own undo stack. On Mac, however, we need to use the system's NSUndoManager to make GUI work. So, basically we need to "sync" our undo manager with NSUndoManager all the time. This requires us to be able to inspect/manipulate contents of NSUndoManager. But there is no public API for doing that. So, I think we may not be able to support Mac for now. And Mac seems to be the only platform that supports undo/redo in WK2 at this point.


(In reply to comment #10)
> (From update of attachment 149124 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=149124&action=review
> 
> > Source/WebKit/qt/WebCoreSupport/EditorClientQt.cpp:338
> >  void EditorClientQt::undo()
> >  {
> > +#if !ENABLE(UNDO_MANAGER)
> >  #ifndef QT_NO_UNDOSTACK
> >      m_inUndoRedo = true;
> >      m_page->undoStack()->undo();
> >      m_inUndoRedo = false;
> >  #endif
> > +#else
> > +    Frame* frame = m_page->d->page->focusController()->focusedOrMainFrame();
> > +    if (!frame)
> > +        return;
> > +    Document* document = frame->document();
> > +    if (!document)
> > +        return;
> > +    document->undoManager()->undo();
> > +#endif
> >  }
> 
> I think there's something wrong with these changes to EditorClients. If we have UNDO_MANAGER enabled, these client functions will not be called.

You're right. I have made them empty functions for the time being. Removing them will probably involve a lot of changes.

On GTK, EFL, Chromium, and BlackBerry, when the user undoes something via GUI, the call goes through WebCore::Editor::undo() first and then UndoManager. In Qt, I'm not sure how it works. Could you please take a look at it?

[Caio Marcelo de Oliveira Filho]

(In reply to comment #13)
> (In reply to comment #7)
> > Another question: how the WebKit layer will get informed about the undo/redo steps?
> 
> The WebKit layer will call WebCore::Editor for information, which will in turn call WebCore::UndoManager.

Yes, but the question is how WebKit layer get informed about undo/redo steps that page will generate. I think maybe we are missing something here. Let's take a step back and see how things work today.

For example, when an editing command is applied (Editor::appliedEditing), the Editor make a call to the WebKit layer (EditorClient::registerUndoStep) passing and UndoStep object, that has the information to undo/redo the command. If there's no client, nothing is registered.

The other situation is when we undo (Editor::undo), and it simply delegates again to WebKit layer (EditorClient::undo). It is the client responsibility to handle the stack changes and call the corresponding UndoStep object. In short, currently WebCore doesn't implement any stack at all.

This design allows ports to expose full control of the undo/redo stack to the applications if needed. At least Qt/WK1 and Mac do that, via QUndoStack and NSUndoManager respectively.


> There are some issues with the Mac port that I found while implementing it. On GTK, EFL, Chromium, and BlackBerry, WebKit maintains its own undo stack.

These ports don't expose full control. In practice, for them, would be fine if the code they implement for undo stack was provided by WebCore. As you are implementing here with the UndoManager, but...


> On Mac, however, we need to use the system's NSUndoManager to make GUI work. So, basically we need to "sync" our undo manager with NSUndoManager all the time. This requires us to be able to inspect/manipulate contents of NSUndoManager.

...maybe that's not best design when the ports actually want control. And it isn't clear to me whether they want this level of control (like Qt/WK1 and Mac) for all the UndoManagers we could have in a page.

[Sukolsak Sakshuwong]

Created attachment 150531 [details]
Work in progress

[Ryosuke Niwa]

Comment on attachment 150531 [details]
Work in progress

View in context: https://bugs.webkit.org/attachment.cgi?id=150531&action=review

> Source/WebCore/bindings/js/JSUndoManagerCustom.cpp:77
> +    JSValue thisValue = exec->hostThisValue();
> +    if (!thisValue.inherits(&JSUndoManager::s_info))
> +        return throwTypeError(exec);
> +    JSUndoManager* castedThis = jsCast<JSUndoManager*>(asObject(thisValue));
> +    ASSERT_GC_OBJECT_INHERITS(castedThis, &JSUndoManager::s_info);
> +    UndoManager* impl = static_cast<UndoManager*>(castedThis->impl());
> +    if (exec->argumentCount() < 2)
> +        return throwError(exec, createNotEnoughArgumentsError(exec));
> +    JSValue dictionary = MAYBE_MISSING_PARAMETER(exec, 0, DefaultIsUndefined);
> +    if (exec->hadException())
> +        return jsUndefined();
> +    if (!dictionary.isObject())
> +        return throwTypeError(exec);
> +    bool merge(MAYBE_MISSING_PARAMETER(exec, 1, DefaultIsUndefined).toBoolean());
> +    if (exec->hadException())
> +        return jsUndefined();
> +    ScriptExecutionContext* scriptContext = jsCast<JSDOMGlobalObject*>(exec->lexicalGlobalObject())->scriptExecutionContext();
> +    if (!scriptContext)
> +        return jsUndefined();
> +    RefPtr<DOMTransaction> transaction = DOMTransaction::create(dictionary.getObject(), thisValue.getObject(), currentWorld(exec), scriptContext);
> +    impl->transact(transaction, merge);
> +    return jsUndefined();

You can make some use of blank lines.

> Source/WebCore/editing/DOMTransaction.cpp:43
> +using namespace JSC;

We need to support both V8 and JSC so we shouldn't be doing this here. Maybe this code belongs in Source/WebCore/binding?

> Source/WebCore/editing/DOMTransaction.cpp:97
> +        scriptExecutionContext->isDocument()
> +            ? JSMainThreadExecState::call(exec, function, callType, callData, thisValue, args)
> +            : JSC::call(exec, function, callType, callData, thisValue, args);

This is not an appropriate use of the ternary operator. Just use the regular if.

> Source/WebCore/editing/DOMTransaction.h:48
> +class DOMTransaction : public UndoStep {

I would have made two classes V8DOMTransaction and JSDOMTransaction that inherited from DOMTransaction and kept this class agnostic of JS engine we use.

> Source/WebCore/editing/UndoManager.cpp:61
> +    if (m_isApplying || m_isUnapplying || m_isReapplying)

It seems excessive to have a flag for each of applying, unapplying, and reapplying a transaction.
I would have added a single flag like m_isOperationInProgress (we need a better name).

> Source/WebCore/editing/UndoManager.cpp:90
> +        UndoStep* step = entry[i-1].get();

What's the point of this local variable? You also need a space before/after -.

> Source/WebCore/editing/UndoManager.cpp:91
> +        step->unapply();

You can just do entry[i-1]->unapply().

> Source/WebCore/editing/UndoManager.cpp:109
> +        UndoStep* step = entry[i-1].get();
> +        step->reapply();

Ditto.

> Source/WebCore/editing/UndoManager.cpp:119
> +unsigned long UndoManager::length() const
> +{
> +    return m_undoStack.size() + m_redoStack.size();
> +}

I would have made this inline.

> Source/WebCore/editing/UndoManager.cpp:124
> +unsigned long UndoManager::position() const
> +{
> +    return m_redoStack.size();
>  }

Ditto.

> Source/WebCore/editing/UndoManager.cpp:144
> +bool UndoManager::canUndo() const
> +{
> +    return !m_undoStack.isEmpty();
> +}
> +
> +bool UndoManager::canRedo() const
> +{
> +    return !m_redoStack.isEmpty();
> +}

Ditto.

> Source/WebCore/editing/UndoManager.cpp:173
> +            if (step->isDOMTransaction()) {

Since we won't be fixing DOMTransaction & EditCommandComposition (we should add some assertions to ensure this invariant), I would have continue'd as soon as find that the first entry wasn't DOM transaction.

> Source/WebCore/editing/UndoManager.cpp:175
> +                DOMTransaction* transaction = static_cast<DOMTransaction*>(step);
> +                transaction->visitDictionary(visitor);

This would be done in one line.

[Adam Barth]

Comment on attachment 150531 [details]
Work in progress

View in context: https://bugs.webkit.org/attachment.cgi?id=150531&action=review

> Source/WebCore/bindings/js/JSUndoManagerCustom.cpp:54
> +JSValue JSUndoManager::transact(ExecState* exec)

Wow, this function is really complicated.  We can't auto-generate it?  It sounds like you just need CallWith=ScriptExecutoinContext,DOMWrapperWorld or something like that.

> Source/WebCore/editing/DOMTransaction.cpp:47
> +DOMTransaction::DOMTransaction(JSObject* function, JSObject* wrapper, DOMWrapperWorld* isolatedWorld, ScriptExecutionContext* context)

It's not correct to have JavaScriptCore-specific code in WebCore.  This is an illustration of the layering violation / reference cycle issue we discussed earlier.  The proper way to implement this is with a bunch of custom code in the bindings layer.  You probably don't want a C++ class for DOMTransaction at all.  You just want to use a native JavaScript object and hold it in WebCore proper using ScriptValue.

> Source/WebCore/editing/DOMTransaction.cpp:65
> +void DOMTransaction::callProperty(ScriptExecutionContext* scriptExecutionContext, const char* propertyName)

This function should all be in the bindings layer.

[Ryosuke Niwa]

(In reply to comment #17)
> (From update of attachment 150531 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=150531&action=review
> 
> > Source/WebCore/bindings/js/JSUndoManagerCustom.cpp:54
> > +JSValue JSUndoManager::transact(ExecState* exec)
> 
> Wow, this function is really complicated.  We can't auto-generate it?  It sounds like you just need CallWith=ScriptExecutoinContext,DOMWrapperWorld or something like that.
> 
> > Source/WebCore/editing/DOMTransaction.cpp:47
> > +DOMTransaction::DOMTransaction(JSObject* function, JSObject* wrapper, DOMWrapperWorld* isolatedWorld, ScriptExecutionContext* context)
> 
> It's not correct to have JavaScriptCore-specific code in WebCore.  This is an illustration of the layering violation / reference cycle issue we discussed earlier.  The proper way to implement this is with a bunch of custom code in the bindings layer.  You probably don't want a C++ class for DOMTransaction at all.  You just want to use a native JavaScript object and hold it in WebCore proper using ScriptValue.

We do need some subclass of UndoStep that wraps/holds the DOMTransaction object.

[Adam Barth]

> We do need some subclass of UndoStep that wraps/holds the DOMTransaction object.

Why not just hold a ScriptValue and let the bindings worry about the detailed JS structure of the object.

[Ryosuke Niwa]

(In reply to comment #19)
> > We do need some subclass of UndoStep that wraps/holds the DOMTransaction object.
> 
> Why not just hold a ScriptValue and let the bindings worry about the detailed JS structure of the object.

Yes, we should do that.

[Adam Barth]

We also need to do a bunch of the fancy stuff we do for event listeners.  This stuff is really subtle.  Please make sure you have a bindings expert review your patch before landing it.

[Sukolsak Sakshuwong]

Created attachment 151328 [details]
Work in progress

[Ryosuke Niwa]

Comment on attachment 151328 [details]
Work in progress

View in context: https://bugs.webkit.org/attachment.cgi?id=151328&action=review

> Source/WebCore/editing/DOMTransaction.h:53
> +#if USE(JSC)
> +    virtual void visitDictionary(JSC::SlotVisitor&) { };
> +#endif

This should be in JSDOMTransactionCustom instead.

> Source/WebCore/editing/UndoManager.cpp:83
> +    m_redoStack.append(emptyEntry);

This needs to happen after unapplying entries. Otherwise UndoManager::length() will return a wrong value inside undo functions implemented by scripts.

> Source/WebCore/editing/UndoManager.cpp:99
> +    m_undoStack.append(emptyEntry);

Ditto.

> Source/WebCore/editing/UndoManager.cpp:110
> +void UndoManager::registerUndoStep(PassRefPtr<UndoStep> cmd)

Please don't use abbreviations like cmd. Spell out command. Also, it isn't a command. It should probably be called step.

> Source/WebCore/editing/UndoManager.cpp:142
> +                static_cast<DOMTransaction*>(step)->visitDictionary(visitor);

You should just cast it to JSDOMTransaction here.

> Source/WebCore/editing/UndoManager.h:75
> +#if USE(JSC)
> +    void visitTransactions(JSC::SlotVisitor&);
> +#endif

This should be in JSUndoManagerCustom instead. We should just expose undoStack & redoStack since we'll need a V8 equivalent anyway.

> LayoutTests/editing/undomanager/undomanager-undo-redo-expected.txt:3
> +test
> +
> +PASS Untitled 

We need some test descriptions. Please add title element for the description.

> LayoutTests/editing/undomanager/undomanager-undo-redo.html:12
> +test(function() {

We should be calling test for each test case with some descriptive labels.

> LayoutTests/editing/undomanager/undomanager-undo-redo.html:19
> +    // start

These comments are not useful. Please get rid of them.

[Sukolsak Sakshuwong]

Created attachment 151376 [details]
Work in progress

[Ryosuke Niwa]

Comment on attachment 151376 [details]
Work in progress

View in context: https://bugs.webkit.org/attachment.cgi?id=151376&action=review

This looks like a very reasonable initial patch. We should wait for someone familiar with JSC binding to give us a feedback but you can probably submit a patch for a formal review now.

There's a pending discussion about whether we want to use the pure JS object & callbacks but a review from binding expert will also help us answering that question.

> Source/WebCore/WebCore.xcodeproj/project.pbxproj:28368
> +				OTHER_CFLAGS = "-DENABLE_UNDO_MANAGER";
>  				STRIP_INSTALLED_PRODUCT = NO;
> +				SYMROOT = /Volumes/project/webkit/WebKitBuild;

As you might be well aware, this shouldn't be in the final patch.

> Source/WebCore/editing/UndoManager.cpp:83
> +    Vector<RefPtr<UndoStep> > entry = m_undoStack.last();

This should be a const reference.

> Source/WebCore/editing/UndoManager.h:77
> +    Vector<Vector<RefPtr<UndoStep> > > m_undoStack;
> +    Vector<Vector<RefPtr<UndoStep> > > m_redoStack;

We might want to consider using OwnPtr<Vector<RefPtr<UndoStep> > > > instead so that we don't have to copy everything when we're resizing the vector.
(Please typedef it).

> Source/WebCore/editing/UndoManager.h:79
> +    bool m_isInProgress;
> +    Vector<RefPtr<UndoStep> > m_inProgressEntry;

You can combine these two member variables if we had used OwnPtr because then m_inProgressEntry being null would imply that we're not in the progress.

> Source/WebCore/editing/UndoManager.h:85
> +inline unsigned long UndoManager::length() const
> +{
> +    return m_undoStack.size() + m_redoStack.size();
>  }

We typically define these one line functions within the class declaration.

> LayoutTests/editing/undomanager/undomanager-undo-redo-expected.txt:1
> +test

Please add some test description in the body.

> LayoutTests/editing/undomanager/undomanager-undo-redo-expected.txt:11
> +PASS document has property undoManager. 
> +PASS undoManager has properties undo, redo, length, and position. 
> +PASS undoManager has correct initial values for length (0) and position (0). 
> +PASS After inserting text 'test' in a DIV, undoManager's length is 1 and position is 0. 
> +PASS After bolding the text, undoManager's length is 2 and position is 0, and the result is a bold 'test'. 
> +PASS After undoing, undoManager's length is 2 and position is 1, and the result is a plain 'test'. 
> +PASS After undoing, undoManager's length is 2 and position is 2, and the result is empty. 
> +PASS After redoing, undoManager's length is 2 and position is 1, and the result is a plain 'test'. 
> +PASS After redoing, undoManager's length is 2 and position is 0, and the result is a bold 'test'. 

Thanks! These outputs look much better.

[Sukolsak Sakshuwong]

Created attachment 151551 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 151551 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=151551&action=review

> Source/WebCore/ChangeLog:15
> +        * WebCore.xcodeproj/project.pbxproj:

You also need to add your files to WebCore.vcproj.

> Source/WebCore/WebCore.xcodeproj/project.pbxproj:8998
> +		76808B4D159DADFA002B5233 /* JSHTMLDialogElement.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSHTMLDialogElement.cpp; sourceTree = "<group>"; };
> +		76808B4E159DADFA002B5233 /* JSHTMLDialogElement.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = JSHTMLDialogElement.h; sourceTree = "<group>"; };

It seems like this is an unrelated change?

> Source/WebCore/WebCore.xcodeproj/project.pbxproj:25218
> +				7B517E8515ACF1F500F16B7A /* JSDOMTransaction.h in Headers */,
> +				7B517E8715ACF21100F16B7A /* DOMTransaction.h in Headers */,

Please sort these entries lexicologically.

> Source/WebCore/WebCore.xcodeproj/project.pbxproj:28278
> +				7B0992F515ACF1AD00ED6D20 /* JSUndoManagerCustom.cpp in Sources */,
> +				7B517E8415ACF1F500F16B7A /* JSDOMTransaction.cpp in Sources */,

Ditto.

> Source/WebCore/WebCore.xcodeproj/project.pbxproj:28393
> +				SYMROOT = /Volumes/project/webkit/WebKitBuild;

You need to revert this change.

> Source/WebCore/editing/UndoManager.cpp:107
> +    for (size_t i = entry.size(); i > 0; --i)
> +        entry[i - 1]->reapply();

This is wrong. You need to call reapply in the order they appear (e.g. if you had t1 and t2 in entry and called
t2.unapply() and t1.unapply() in the respective order, then we should be calling t1.reapply() and t2.reapply() in the respective order).
r- because of this bug. And please add a test case for this.

> Source/WebCore/editing/UndoManager.cpp:129
> +        UndoManagerEntry* entry = new UndoManagerEntry;

You should declare OwnPtr here instead and adoptPtr immediately.

> Source/WebCore/editing/UndoManager.cpp:131
> +        m_undoStack.append(adoptPtr(entry));

And call release() on that OwnPtr here.

> Source/WebCore/editing/UndoManager.cpp:144
> +        UndoManagerEntry* entry = new UndoManagerEntry;
> +        entry->append(step);
> +        m_redoStack.append(adoptPtr(entry));

Ditto.

> Source/WebCore/editing/UndoManager.idl:42
> +        void undo()
> +            raises(DOMException);
> +        void redo()
> +            raises(DOMException);

You can put the raises on the same line.

> Source/WebCore/editing/UndoManager.idl:50
> +        void clearUndo()
> +            raises(DOMException);
> +        void clearRedo()
> +            raises(DOMException);

Ditto.

[Sukolsak Sakshuwong]

(In reply to comment #27)
> > Source/WebCore/editing/UndoManager.cpp:107
> > +    for (size_t i = entry.size(); i > 0; --i)
> > +        entry[i - 1]->reapply();
> 
> This is wrong. You need to call reapply in the order they appear (e.g. if you had t1 and t2 in entry and called
> t2.unapply() and t1.unapply() in the respective order, then we should be calling t1.reapply() and t2.reapply() in the respective order).
> r- because of this bug. And please add a test case for this.
> 

This is actually correct. Let's say we transact(t1, false); transact(t2, true);. The undo stack will be <[t1, t2]>. When we undo, we unapply t2 first and then t1. Therefore, t2 is pushed to m_inProgressEntry first and then t1. Hence, the redo stack will be <[t2, t1]>. Therefore, we need to reapply in reverse order. If you want to apply in order they appear, I can change it so that undo steps are always inserted at the front when pushed to m_inProgressEntry. Or I can change it so that undo steps in m_inProgressEntry are reversed after we are done undoing. But either way will incur some performance penalty.

Because entries are exposed to the web only through the item() method, we can do reversion there. And since we create a new array in that method anyway, I think it's better to do it there.

> > Source/WebCore/editing/UndoManager.idl:42
> > +        void undo()
> > +            raises(DOMException);
> > +        void redo()
> > +            raises(DOMException);
> 
> You can put the raises on the same line.
> 
> > Source/WebCore/editing/UndoManager.idl:50
> > +        void clearUndo()
> > +            raises(DOMException);
> > +        void clearRedo()
> > +            raises(DOMException);
> 
> Ditto.

Every IDL file that I have seen so far seems to put it in another line.

[Sukolsak Sakshuwong]

Created attachment 151580 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 151580 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=151580&action=review

The patch looks good in general. We need someone familiar with JSC binding code to review the JS* code.

> Source/WebCore/editing/UndoManager.cpp:130
> +        OwnPtr<UndoManagerEntry> entry = adoptPtr(new UndoManagerEntry);
> +        entry->append(step);

It might make sense to put add some helper function for these two lines since they appear quite often.

> Source/WebCore/editing/UndoManager.cpp:134
> +        ExceptionCode ec;
> +        clearRedo(ec);

We should probably use ASSERT_NO_EXCEPTION as the default value in clearUndo & clearRedo.

> LayoutTests/editing/undomanager/undomanager-transact.html:30
> +    		edit.innerHTML += "1e ";

Nit: There's a tab character. There are multiple tab characters in this file. Please replace them all by 4 spaces.

[Build Bot]

Comment on attachment 151580 [details]
Patch

Attachment 151580 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/13201173

[Early Warning System Bot]

Comment on attachment 151580 [details]
Patch

Attachment 151580 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/13202152

[Early Warning System Bot]

Comment on attachment 151580 [details]
Patch

Attachment 151580 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/13205184

[Build Bot]

Comment on attachment 151580 [details]
Patch

Attachment 151580 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/13202165

[Build Bot]

Comment on attachment 151580 [details]
Patch

Attachment 151580 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/13205194

[Early Warning System Bot]

Comment on attachment 151580 [details]
Patch

Attachment 151580 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/13201190

[Sukolsak Sakshuwong]

Created attachment 151759 [details]
Patch

[Sukolsak Sakshuwong]

Created attachment 151763 [details]
Patch

[Ryosuke Niwa]

Sam, could you take a look at Sukolsak's patch for JSC binding?

[Sukolsak Sakshuwong]

Created attachment 152682 [details]
Work in progress

[Sukolsak Sakshuwong]

Created attachment 152880 [details]
Patch

[Sukolsak Sakshuwong]

Created attachment 153172 [details]
Work in progress

[Ryosuke Niwa]

Comment on attachment 153172 [details]
Work in progress

View in context: https://bugs.webkit.org/attachment.cgi?id=153172&action=review

> Source/WebCore/dom/ContainerNode.cpp:208
> +    if (DOMTransaction::isCapturingDOMChanges(this))

isRecordingAutomaticTransaction might be better.

> Source/WebCore/editing/DOMChange.cpp:63
> +    m_parent->removeChild(m_child.get(), ASSERT_NO_EXCEPTION);

I don't think we should assert exception here. It's totally possible for mutation events to mess things up.

> Source/WebCore/editing/DOMChange.cpp:73
> +    m_parent->insertBefore(m_child, m_refChild.get(), ASSERT_NO_EXCEPTION);

Ditto.

> Source/WebCore/editing/DOMChange.cpp:92
> +    m_parent->insertBefore(m_child, m_refChild.get(), ASSERT_NO_EXCEPTION);

Ditto.

> Source/WebCore/editing/DOMChange.cpp:99
> +    m_parent->removeChild(m_child.get(), ASSERT_NO_EXCEPTION);

Ditto.

> Source/WebCore/editing/DOMChange.h:44
> +class DOMChange : public RefCounted<DOMChange> {

I'm not sure if DOMChange is such a good name since DOM mutation/change is such an overloaded name.
How about DOMTransactionStep?

> Source/WebCore/editing/DOMChange.h:79
> +

It seems like you're missing the class for attribute changes.

[Kentaro Hara]

Comment on attachment 152880 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=152880&action=review

> Source/WebCore/ChangeLog:9
> +        Tests: editing/undomanager/undomanager-undo-redo.html
> +               editing/undomanager/undomanager-transact.html

Would you add test cases where gc() happens while undomanager is working?

> Source/WebCore/bindings/js/JSUndoManagerCustom.cpp:100
> +    RefPtr<JSDOMTransaction> transaction = JSDOMTransaction::create(dictionary.getObject(), thisValue.getObject(), currentWorld(exec), scriptContext);

Per the bindings convention (https://trac.webkit.org/wiki/WebKitIDL#CallWith), let's put ScriptExecutionContext on the first argument of the method.

> Source/WebCore/bindings/v8/V8DOMTransaction.cpp:48
> +    V8DOMTransaction* dictionary = static_cast<V8DOMTransaction*>(parameter);

Nit: Shall we rename 'dictionary' to 'transaction'?

> Source/WebCore/bindings/v8/V8DOMTransaction.cpp:96
> +    if (context->isJSExecutionForbidden())

Don't we need to check if 'context' is 0?

> Source/WebCore/bindings/v8/V8DOMTransaction.cpp:123
> +            proxy->callFunction(handlerFunction, receiver, 1, parameters);

1 => 0

> Source/WebCore/bindings/v8/V8DOMTransaction.h:57
> +    v8::Persistent<v8::Object> existingDictionaryObjectPersistentHandle() { return m_dictionary; }

Nit: Rename to dictionaryJSObject()?

> Source/WebCore/bindings/v8/V8DOMTransaction.h:58
> +    bool hasExistingDictionaryObject() { return !m_dictionary.IsEmpty(); }

Let's remove this method, and check IsEmpty() in the caller side.

> Source/WebCore/bindings/v8/custom/V8UndoManagerCustom.cpp:41
> +#include "V8IsolatedContext.h"

Is this needed?

> Source/WebCore/bindings/v8/custom/V8UndoManagerCustom.cpp:43
> +#include <wtf/UnusedParam.h>

Is this needed?

> Source/WebCore/bindings/v8/custom/V8UndoManagerCustom.cpp:60
> +                if (!transaction->hasExistingDictionaryObject())
> +                    continue;
> +                dictionaries.append(transaction->existingDictionaryObjectPersistentHandle());

This could be:

  Persistent<Value> dictionary = transaction->dictionaryJSObject();
  if (!dictionry.IsEmtpy())
    dictionaries.append(dictionary);

> Source/WebCore/bindings/v8/custom/V8UndoManagerCustom.cpp:85
> +        if (!dictionary.IsEmpty() && !dictionary->IsObject())

This check should be 'if (dictionary.IsEmpty() || !dictionary->IsObject())'.

> Source/WebCore/bindings/v8/custom/V8UndoManagerCustom.cpp:92
> +            return v8::Undefined();

Nit: Given that you are returning v8::Handle<v8::Value>() at the end of this method, let's return v8::Handle<v8::Value>() here too for consistency. (v8::Handle<v8::Value>() is equivalent to v8::Undefined().)

> Source/WebCore/bindings/v8/custom/V8UndoManagerCustom.cpp:94
> +        RefPtr<V8DOMTransaction> transaction = V8DOMTransaction::create(v8::Local<v8::Object>::Cast(dictionary), WorldContextHandle(UseCurrentWorld), context);

Per the bindings convention, 'context' should come first.

> Source/WebCore/bindings/v8/custom/V8UndoManagerCustom.cpp:97
> +        if (UNLIKELY(ec))

Nit: UNLIKELY is not needed. LIKELY/UNLIKELY would have no performance impact in such a complicated not-inlined method.

> Source/WebCore/bindings/v8/custom/V8UndoManagerCustom.cpp:98
> +            goto fail;

You can just return V8Proxy::setDOMException(ec, args.GetIsolate()) here.

> Source/WebCore/bindings/v8/custom/V8UndoManagerCustom.cpp:102
> +fail:
> +    return V8Proxy::setDOMException(ec, args.GetIsolate());

Remove this.

> Source/WebCore/editing/DOMTransaction.h:37
> +#include <wtf/RefCounted.h>

Is this needed?

[Adam Barth]

Comment on attachment 153172 [details]
Work in progress

View in context: https://bugs.webkit.org/attachment.cgi?id=153172&action=review

> Source/WebCore/bindings/v8/V8DOMTransaction.h:74
> +    RefPtr<ScriptExecutionContext> m_context;

This RefPtr is very worrisome.  If V8DOMTransaction is kept alive by the garbage collector, then it will keep the ScriptExecutionContext alive, which will keep a ton of JS objects alive.

[Sukolsak Sakshuwong]

Created attachment 155025 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 155025 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=155025&action=review

> Source/WebCore/bindings/js/JSDOMTransaction.h:66
> +    RefPtr<DOMWrapperWorld> m_isolatedWorld;

We shouldn't have a strong ref to the isolated world. Instead, retrieve this information from the document as needed.

> Source/WebCore/bindings/v8/V8DOMTransaction.h:62
> +    WorldContextHandle m_worldContext;

We shouldn't be storing the world context. Instead, retrieve it from the document.

> Source/WebCore/editing/UndoManager.h:53
>  class UndoManager : public RefCounted<UndoManager> {

Per discussion with abarth, this needs to be an active DOM object.

[Sukolsak Sakshuwong]

Created attachment 156514 [details]
Patch

[Adam Barth]

Comment on attachment 156514 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=156514&action=review

> Source/WebCore/bindings/js/DOMTransaction.cpp:43
> +DOMTransaction::DOMTransaction(DOMWrapperWorld* isolatedWorld)

Sooooooo much custom code!!!

> Source/WebCore/bindings/js/DOMTransaction.cpp:72
> +static bool getProperty(JSC::JSObject* object, const char* propertyName, JSC::JSValue &value, JSC::ExecState* exec)
> +{
> +    JSC::Identifier identifier(exec, propertyName);
> +    JSC::PropertySlot slot(object);
> +    if (!object->getPropertySlot(exec, identifier, slot))
> +        return false;
> +    if (exec->hadException())
> +        return false;
> +    value = slot.getValue(exec, identifier);
> +    return !exec->hadException();
> +}

This code doesn't seem to have anything to do with DOMTransaction.  Should this be in a more general location?

> Source/WebCore/editing/UndoManager.cpp:89
> +        entry[i - 1]->unapply();

As far as I can tell, unapply can run script, which means it can mutate m_undoStack, which means this line of code is almost certainly a use-after-free vulnerability.

[Adam Barth]

I'm not sure how to help you succeed with this patch.  This stuff is just very complicated and subtle.  :(

[Adam Barth]

I think the API is just poorly designed.  It's too hard to implement correctly.

I'm not really being helpful.  I need to walk away from the patient.  I'm sorry that I won't be able to review further patches on this feature.

[Kentaro Hara]

(In reply to comment #51)
> I think the API is just poorly designed.  It's too hard to implement correctly.

I think if APIs were designed based on event listeners (i.e. onundo, onredo, etc), the implementation would become much clearer.

[Sukolsak Sakshuwong]

Created attachment 156794 [details]
Patch

[Adam Barth]

Comment on attachment 156794 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=156794&action=review

> Source/WebCore/bindings/js/DOMTransaction.cpp:99
> +    JSDOMGlobalObject* globalObject = jsCast<JSDOMGlobalObject*>(exec->lexicalGlobalObject());
> +    JSObject* wrapper = asObject(toJS(exec, globalObject, this));
> +
> +    JSValue data = wrapper->get(exec, Identifier(exec, "data"));

Why are we grabbing "data" out of the global scope?  That's strange.

> Source/WebCore/editing/UndoManager.cpp:77
> +    m_isInProgress = true;
> +    transaction->apply();
> +    m_isInProgress = false;

Can we be re-entered here?  If so, we might need to use a counter.  I guess we test for m_isInProgress at the top of the function, so maybe that solves this problem.

[Adam Barth]

> > Source/WebCore/editing/UndoManager.cpp:89
> > +        entry[i - 1]->unapply();
> 
> As far as I can tell, unapply can run script, which means it can mutate m_undoStack, which means this line of code is almost certainly a use-after-free vulnerability.

This still seems to be an issue.  It looks like you've tried to mitigate this using the m_isInProgress flag, but it seems like the whole UndoManager can be destroyed synchronously at this program point.

[Sukolsak Sakshuwong]

(In reply to comment #55)
> > > Source/WebCore/editing/UndoManager.cpp:89
> > > +        entry[i - 1]->unapply();
> > 
> > As far as I can tell, unapply can run script, which means it can mutate m_undoStack, which means this line of code is almost certainly a use-after-free vulnerability.
> 
> This still seems to be an issue.  It looks like you've tried to mitigate this using the m_isInProgress flag, but it seems like the whole UndoManager can be destroyed synchronously at this program point.

I make a local copy of the last entry of m_undoStack before the loop. So, it shouldn't matter if m_undoStack gets mutated during unapplying/reapplying.

[Adam Barth]

Comment on attachment 156794 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=156794&action=review

> Source/WebCore/editing/UndoManager.cpp:121
> +    m_isInProgress = false;
> +
> +    m_undoStack.append(m_inProgressEntry.release());
> +    m_redoStack.removeLast();

Right, but nothing is keeping the whole UndoManager alive.  All these writes are to potentially unallocated memory.

[Sukolsak Sakshuwong]

(In reply to comment #57)
> (From update of attachment 156794 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=156794&action=review
> 
> > Source/WebCore/editing/UndoManager.cpp:121
> > +    m_isInProgress = false;
> > +
> > +    m_undoStack.append(m_inProgressEntry.release());
> > +    m_redoStack.removeLast();
> 
> Right, but nothing is keeping the whole UndoManager alive.  All these writes are to potentially unallocated memory.

I see. I'll fix it with "RefPtr<UndoManager> protect(this)" in the new patch.

[Adam Barth]

Comment on attachment 156794 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=156794&action=review

>> Source/WebCore/bindings/js/DOMTransaction.cpp:99
>> +    JSValue data = wrapper->get(exec, Identifier(exec, "data"));
> 
> Why are we grabbing "data" out of the global scope?  That's strange.

I misunderstood.  You're getting the data property out of the DOMTransaction wrapper.

> Source/WebCore/bindings/js/JSUndoManagerCustom.cpp:69
> +    Identifier dataName(exec, "data");

Should we make "data" a named constance so that we can share it here and in JSDOMTransaction?

Also, what happens if there's a setter for "data" defined on Object.prototype?  Will we trigger that here?  Should we test that case?  In the V8 bindings, we can use a hidden property, which solves these problems.

[Sukolsak Sakshuwong]

Created attachment 157100 [details]
Patch

[Sukolsak Sakshuwong]

Created attachment 157175 [details]
Patch

[Sukolsak Sakshuwong]

(In reply to comment #59)
Thanks for the comment

> > Source/WebCore/bindings/js/JSUndoManagerCustom.cpp:69
> > +    Identifier dataName(exec, "data");
> 
> Should we make "data" a named constance so that we can share it here and in JSDOMTransaction?

Done.

> Also, what happens if there's a setter for "data" defined on Object.prototype?  Will we trigger that here?  Should we test that case?  In the V8 bindings, we can use a hidden property, which solves these problems.

We will not trigger it because we use JSObject::putDirect. I've added a test in the latest patch to test that case.

[Kentaro Hara]

Comment on attachment 157175 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=157175&action=review

I looked at bindings/js/* and the IDL file. I added some minor comments. As the patch is doing something beyond my JSC knowledge, I'd be happy if JSC folks could take a look.

> Source/WebCore/bindings/js/DOMTransaction.h:45
> +class Node;
> +class ScriptExecutionContext;

Is this needed?

> Source/WebCore/bindings/js/DOMTransaction.h:50
> +    static PassRefPtr<DOMTransaction> create(DOMWrapperWorld* isolatedWorld);

Nit: "isolatedWorld" is not needed.

> Source/WebCore/bindings/js/DOMTransaction.h:63
> +    DOMTransaction(DOMWrapperWorld* isolatedWorld);

Ditto.

> Source/WebCore/bindings/js/JSDOMTransactionCustom.cpp:50
> +    if (!undoManager)
> +        return false;
> +    if (!undoManager->undoScopeHost())

!undoManager || !undoManager->undoScopeHost()

[Sukolsak Sakshuwong]

Created attachment 159157 [details]
work in progress

[Adam Barth]

UndoManager has been removed from trunk in bug 100711.