Re: [9] Review Request for 8030702: Deadlock between subclass of AbstractDocument and UndoManager

[Alexander Scherbatiy]

  The fix looks good to me.

  Thanks,
  Alexandr.

On 9/24/2015 8:27 PM, Semyon Sadetsky wrote:

On 9/22/2015 5:04 PM, Semyon Sadetsky wrote:

On 9/22/2015 4:18 PM, Alexander Scherbatiy wrote:

On 9/21/2015 12:19 PM, Semyon Sadetsky wrote:

On 9/21/2015 11:27 AM, Alexandr Scherbatiy wrote:

18.09.2015 19:22, Semyon Sadetsky пишет:

On 9/18/2015 6:51 PM, Alexander Scherbatiy wrote:

On 9/16/2015 5:14 PM, Semyon Sadetsky wrote:

On 9/16/2015 1:38 PM, Alexander Scherbatiy wrote:

On 9/15/2015 10:37 PM, Semyon Sadetsky wrote:

On 9/15/2015 6:16 PM, Alexander Scherbatiy wrote:

On 9/11/2015 7:24 PM, Semyon Sadetsky wrote:

The deadlock that you described exists only because AbstractDocument uses locks in the UndoableEdit.undo()/redo() methods. Applications that use UndoManager and do not use lock in the UndoableEdit.undo()/redo() methods do not have deadlock. They worked fine before the fix and can lost data consistency after the fix. This is definitely the regression.

You mean scenario when a document that does not support synchronization but anyway is modified from several threads. You can expect that such scenario is functional only if such document is a single atomic field. I updated the fix http://cr.openjdk.java.net/~ssadetsky/8030702/webrev.04/ take it into account.

    This looks better. There are just some comments:

- The 'inProgress' variable in UndoManager.undo()/redo()/undoOrRedo() methods should have synchronization. Is it possible to move 'if (inProgress)' check into tryUndoOrRedo() method similarly to as it was used in the version 2 of the fix? - UndoManager line 489: why not to use the original check from the undoOrRedo() method "if (indexOfNextAdd == edits.size())" to pick up undo or redo action? - UndoManager line 516: An undoable edit can be requested two times for the ANY action because the 'undo' variable can have old value in the second synchronized block. Even the logic is right it is better to take an edit based on the 'action' variable. - UndoManager.undoOrRedo() throws CannotUndoException now instead of CannotRedoException if the redo action is not possible. - It is possible to get rid of the 'done ' variable in UndoManager.tryUndoOrRedo() just simply have an infinity loop. - It is possible to use Boolean values TRUE, FALSE or null for three-state logic. But it is up to you to choose enums or Boolean in the fix.

I made the changes: http://cr.openjdk.java.net/~ssadetsky/8030702/webrev.05/ except for the last one. Actually triple Boolean logic is a bad style.

There are two main synchronized block in the tryUndoOrRedo() method: one to look up an undoable edit lock and the second which use the undoable edit lock. In the version 02 of the fix the original code from undo() and redo() methods were moved to these two blocks. It is not clear why don't you want to do the same (just call tryUndoOrRedo() with necessary argument for all UndoManager.undo()/redo()/undoOrRedo() methods) in the latest fix?

    Splitting logic like:
 -------------------
 420     public void undo() throws CannotUndoException {
 421         if (!tryUndoOrRedo(Action.UNDO)) {
 422             synchronized (this) {
 423                 super.undo();
 424             }
 425         }
 426     }
 -------------------

always have a question that before the fix the super.undo() was called only for '!inProgress' condition but now the 'inProgress' can be changed when super.undo() is called.

inProgress can be changed when super.undo() is called because it is protected by synchronized block. Imagine that undo() is called with inProgress = true, then it is blocked by the concurrent document change, and after the retry it finds inProgress= false, so it cannot undo by usual way anymore, because the UndoManager is converted into a single edit and it should undo using super.undo().

   I am talking about slightly different thing.
   This is the code for the undo() method before the fix.
 -------------------
 410     public synchronized void undo() throws CannotUndoException {
 411         if (inProgress) {
 412             UndoableEdit edit = editToBeUndone();
                      ...
 416             undoTo(edit);
 417         } else {
 418             super.undo();
 419         }
 420     }
-------------------

Checking the 'inProgress' variable and calling undoTo(edit) and super.undo() is done under the same synchronized block.

  Let's slightly modify the code:
-------------------
      public void undo() throws CannotUndoException {

          boolean res = true;

          synchronized (this) {
              if (inProgress) {
                  UndoableEdit edit = editToBeUndone();
                  ...
                  undoTo(edit);

It is not possible to execute undoTo() here because it will cause the deadlock we are trying to fix.

  May be with the updated sample it would be cleaner.
  This is just a some method which uses a synchronization:
----------------------
    public synchronized void someMethod() {
        if (inProgress) {
            // do something
        } else {
            // do something else
        }
    }
----------------------

 This is an updated method:
-------------------
      public void someMethod() {

          boolean res = true;

          [some synchronization]
              if (inProgress) {
                  // do something
              } else {
                 res = false;
              }
          [end of some synchronization]


          [some synchronization]
              if (!res) {
                  do something else
              }
          [end of some synchronization]
      }
-------------------

The problem with the updated method is that inProgress variable can have a value different from 'res' and the 'do something else' action can be executed even inProgress is true.

InProgress goes only one direction true->false. Once it detected as false the super method should be called always.

Alexander, the version as per our off-line discussion: http://cr.openjdk.java.net/~ssadetsky/8030702/webrev.06/

} else {
                 res = false;
              }
          }

          synchronized (this) {
              if (!res) {
                  super.undo();
              }
          }
      }
-------------------

Now the 'inProgress' variable checking and undoTo() is done on the first synchronized block. The result of the inProgress is used in the second synchronized block. But the 'inProgress' variable can be changed between these two blocks and we can't relay on the 'res' value. Instead of 'res' the original 'inProgress' value should be checked in the second synchronized block and if it is true the undoTo(edit) should be called again instead of super.undo().

Above you provided the code logic bore the fix which is reworked because it does not work. Why do we need to discuss it?

We need to discuss this because the inProgress variable in your latest fix is used exactly as in the provided sample. UndoManager line: 473 tryUndoOrRedo(action) returns false if inProgress is false. UndoManager line: 422 super.undo() is called if tryUndoOrRedo(action) returns false despite the real 'inProgress' variable value.

   Thanks,
   Alexandr.

  Thanks,
  Alexandr.

Thanks,
  Alexandr.

Thanks,
   Alexandr.

   Thanks,
   Alexandr.

  Thanks,
  Alexandr.

   Thanks,
   Alexandr.

Also synchronization is needed to provide coherency with the state of the document. If those two are not provided the document can be corrupted. This is enough most usages.

  Thanks,
  Alexandr.

  Thanks,
  Alexandr.

  Thanks,
  Alexandr.

Thanks,
   Alexandr.

It is

I still think that updating the UndoableManager for one particular AbstarctManager class can be made only after investigation of other possibilities.

You could start with choosing behavior which you want to achieve or to keep, like:

   - fix the deadlock
   - atomic undo() method
   - serialization
   - immediate roll back action

- abstract document consistency after undo() action

  - ...

We need to pay attention to the deadlock at first of cause. Serialization and consistency are achieved. Any concrete doubts? immediate roll back action -- ?what is that?

"if user starts a long edit operation and press undo after that he expects when the long edit is finished it will be rolled back immediately." - what ever does it mean.

Got it. It will work within the fairness. We have discussed this allready.

I sacrificed undo/redo call atomicity because you did not like doc references in undo manager. I think it is not important for the most multithreaded undo/redo scenarios.

Could you give more details about it. Which doc references do you mean?

Your statement a dozen iterations ago was: "There should be a way to solve these problems without storing links of external classes inside the UndoManager." I guess you used "link" term for references. I would recommend to use standard terminology: reference to the object, dependency on the class, etc... to avoid misunderstanding. Usually "link" is in a browser document or a tool that produces executables after compilation.

and look which of the following approaches can better solve them (where the fist is more preferred and the last is less preferred case): - using UndoManager as is without adding links from some specific classes to it - provide an API for UndoManager to work with UndoableEdit-s which have synchronization for undo/redo methods - adding links of external classes directly to UndoManager

What do you mean under link term? A reference or dependency?

There are two options. If UndoManager is a class designed to be only used with the AbstractDocument and placed in the javax.swing.text package it definitly can have special code to handle an abstract document instance in a special way. If UndoManager is a general purpose class, it looks strange that it handles some special classes in different way as all others. It usually mean that there are some design problems in this class. That is why I just asked to look at other ways at first. Only if other solutions are not suitable it has sense to look at the way that you are provided.

Correct. I introduced extra dependency. It is optional, but anyway. Of cause there is a design problem in undo javax.swing.undo package. But I cannot rewrite the API because we will get a compatibility problem then. I mentioned this several times in this thread.

We are constrained by compatibility requirements. UndoManager is a broadly used class we cannot change the API so drastically.

I think that you can generalize your solution just adding an internal interface like sun.swing.UndoableEditLock. Every UndoableEdit which implements this interface can provide a lock for its synchronization.

If this will work it can be made public in some days so other application can also have proper synchronization for their undo/redo actions.

OK. I added it.

http://cr.openjdk.java.net/~ssadetsky/8030702/webrev.02/

- We can return a public class that implements an internal interface, but we can't expose an internal API in the public class definition. May be it is possible to wrap an UndoableEdit to the UndoableEditLockSupport in the UndoableEditEvent or in some other place.

- The similar code is used both in the UndoManager.undo() and redo() methods. Is it possible to move this code to one method that does undo or redo depending on the given argument?

OK. accepted.

http://cr.openjdk.java.net/~ssadetsky/8030702/webrev.03/

   - UndoManager.undo/redo methods

In your previous fix inProgress variable and the super call were used under the lock. It may leads to some synchronization issues if you decide to omit it.

  - UndoManager.tryUndoOrRedo()

It is possible to get rid of 'done' variable just using an infinity loop and return the exact result where the loop is terminated. - AbstractDocument.DefaultDocumentEventUndoableWrapper implements both UndoableEdit and UndoableEditLockSupport interfaces but UndoableEditLockSupport already extends UndoableEdit. - "@since 1.9" javadoc for DefaultDocumentEventUndoableWrapper.lockEdit()/unlockEdit() methods really belongs to the UndoableEditLockSupport methods. In this case there is no need for {@inheritDoc} tag.

  Thanks,
  Alexandr.

Thanks,
  Alexandr.

  Thanks,
  Alexandr.

"adding links of external classes directly to UndoManager" - Sorry, did not catch what are you about? Could you clarify?

--Semyon

Thanks,
  Alexandr.

--Semyon

There is a mistake in your scenario steps: fireUndoableEditUpdate() is called before the freeing the lock (see AbstractDocument.handleInsertString() method).

Yet another argument do not do this from the user experience: if user starts a long edit operation and press undo after that he expects when the long edit is finished it will be rolled back immediately.

It is not true. The first process adds his undo edit to the UndoManager. While a user trying to press undo the second long process can be started.

That is what led to this issue because when undo is in progress document writing should be allowed. Sorry but I didn't see why is "It not true"? Then what is your expectation when you press undo button while edit is not finished yet and there is no way to abort it?

It would be good if it works as you described. But it does not work in this way with or without your fix. undo() action has writeLock in AbstractDocument and because of it is always executed after insert string action. If a user sees that undo is available, he can call it but the second long insertString process can start earlier and acquire the writeLock.

That is what we are going to fix. And this does work after this fix. Undo call will be blocked by the long edit until the last is done without any deadlocks. And when edit is done undo() will acquire the lock and prevent any new edits until undo() is done. Please provide a scenario when in your opinion it does not wok.

The first process starts for 5 minutes. When it is finished a user sees that he can press undo. While he is pressing undo button, the second long process starts for 10 minutes and acquire the write lock. The user presses undo but he needs to wait 10 more minutes until the second process is finished.

Actually, if two or more threads are waiting for a monitor it is not determined which one will get the control after the signal. To order that the ReentrantLock API could be used but AbstractDocument uses wait/notify for locking. I think it is not worth to dig so deep. It does not cause any issues

The issue that is considered is "if user starts a long edit operation and press undo after that he expects when the long edit is finished it will be rolled back immediately." If you are agree that it is not always possible to do the roll back "immediately" there is no point to discussion.

I agree. On that level it is not possible to predict the order exactly in such scenario. But the state of the document will be consistent. And it is possible to have it predictable using lock fairness.

because undo() always get the last edit anyway. If it will be important for somebody to preserve the execution order on that level of details we will fix it.

So undo should be executed after the edit is fully performed because the corresponding UndoableEdit which undos this edit can be produced only after the edit is done. I think at first we need to look on the situation externally rather than concentrate on implementation questions like in which class do references go.

Yes, please look on this situation from a user point of view which wants to implement simple Java Painter.

But could you describe this scenario? Just steps when this simple Painter fails under the proposed fix?I Note, if this Painter's content is not an AbstarctDocument it will work as before the fix.

Any application that uses UndoManager and wants to have the same synchronization (have the same lock both for UndoableEdit adding and undo() method execution) will have the same deadlock problems.

   As I have already written:
---------------

Consider someone writes Java Painter application where it is possible to draw lines and images and uses UndoManager for undo/redo actions. He might want that it was possible to work with copied images. He can get lock on ctrl+v action, process an image, prepare UndoableEdit and notify the UndoManager. He also can use lock/unlock in the undo action to have a consistent state with the processed image. If someone calls undo action during the image processing and gets a deadlock does it mean that link from Java Painter need to be added to the UndoManager?

---------------

Still do not understand the steps for your Painter scenario. A link (reference?) can be added if it is required to implement functionality. If the content is not an AbstarctDocument it may be required to implement custom UndoManager to support the same behavior.

What is the difference between the AbstractDocument and other classes (in Swing or user defined)? Do you mean that the UndoManager is intended only to be used with AbstractDocument and it shouldn't be used in other cases where undo/redo actions are required for non text data?

No, undo manager can be used with any classes. But since we have it assigned to AbstarctDocument so often we need to do our best to make undo manager working with it correctly because users do not like deadlocks usualy. For other classes we cannot provide synchronization by default because there is no API to get the lock. So it remains up to user how to provide the undo manager synchronization with the object it controls for other classes

What we should do just to understand that the same deadlock can happen in an user applications because he wants to use the same synchronization both for the data processing and for the undo action. If so, there should be two investigations: 1. Is it possible to achieve the requested goals without changing UndoManager? In other words The UndoManager should be used in proper way as it is required by its design. 2. Is it possible to update the UndoManager API to provide functionality that meets new requests?

With API change it is reachable. But I would preserve the current API as less constrained. If we add some methods for locking we will determine the way how a user should synchronize his undoable content. And user may not need any synchronization at all. We should keep in mind this opportunity as well.

Only after this discussion there can be a reason to look to other ways.

  Thanks,
  Alexandr.

I think our undo manager implementation do not pretend to be used as the global undo manager for big complex applications and it cannot cover all possible undo approaches. But some basic functionality can be provided and it should be usable. Without edits serialization approach it is not usable for multithreaded use. So either we do not pretend to provide a multithreaded undo manager and remove all synchronize keywords from UndoManager class, either we need to support serialization approach which does not cause deadlocks.

 Thanks,
 Alexandr.

I don't see a contradiction here, could you point on it more precisely?

 Thanks,
 Alexandr.

Thanks,
   Alexandr.

Thanks,
  Alexandr.

--Semyon

Thanks,
  Alexandr.

--Semyon

On 7/30/2015 5:27 PM, Alexander Scherbatiy wrote:

Consider someone writes Java Painter application where it is possible to draw lines and images and uses UndoManager for undo/redo actions. He might want that it was possible to work with copied images. He can get lock on ctrl+v action, process an image, prepare UndoableEdit and notify the UndoManager. He also can use lock/unlock in the undo action to have a consistent state with the processed image. If someone calls undo action during the image processing and gets a deadlock does it mean that link from Java Painter need to be added to the UndoManager?

  Thanks,
  Alexandr.

It looks like AbstractDocument violates UndoManager synchronization contract when it both use lock to work with UndoManager and in the implemented undo() method.

  Thanks,
  Alexandr.

--Semyon