Implementing Undo: Trial and Error

I'm working eagerly on undo, and have a few thoughts to share on it. first, let me say that it's really not easy. so many thing can go wrong, since undo should mean "create a state as if the last action had never occured". it's easy to forget one of the implicit things that happen when you change something. if it's an event listener, or updating some kind of cache, there are so many possibilities.

the first thing to do when you start a programming task is deciding your goals. for undo, I had two goals of great importance

• it must be possible to divide big actions into several small ones. ideally, every action is so small that it only changes one value. in other words, an action should be simple enough that you can find almost all bugs
• it should be easy to use the system. magic has many cards, and if the majority of card code is related to the undo system, that can't be good. coding cards should be easy, ideally fun, so that many of them get implemented.

these don't really sound very compatible. be very precise and document every action, but don't bother me with it...

the second should be looking for help and reference material, but I just skipped over to the third one: error ;)

my first thought was a tree of actions with a controller actually executing of them. the controller checks that actions are executed in proper sequence. the work would be to create and append the action, and then let the controller execute it. the parent action is passed as a parameter to the modifying method so it knows where to plug the action into the tree:
//from laterna.magica.timestamp.Timestamp

private TimestampFactory f;

private int              timestamp;


...



public void updateTimestamp(Move m) {

    //the constructor plugs the move into the tree

    //with m as its parent

    Move parent = new CompoundMove(m, true);

    //plugs in the move which creates the next timestamp

    //for the factory 
    f.nextTimestamp(parent);

    //plugs in the move which updates this Timestamp's value

    new UpdateTimestampMove(parent);

}



...



private class UpdateTimestampMove extends Move {

    private int               before;  

    public UpdateTimestampMove(Move parent) {

        //Move does the tree stuff

        super(parent);

        before = timestamp;

    }

  

    @Override

    public void make() {

        timestamp = f.getCurrentTimestamp();

    }

  

    @Override

    public void undo() {

        timestamp = before;

    }

}



//from laterna.magica.timestamp.TimestampFactory

private int currentTimestamp;



...



public int getCurrentTimestamp() {

    return currentTimestamp;

}



public void nextTimestamp(Move m) {

    new NextTimestampMove(m);

}



...



private class NextTimestampMove extends Move {

    private int               currentTimestamp;  

    public NextTimestampMove(Move parent) {

        super(parent);      

        currentTimestamp = TimestampFactory.this.currentTimestamp;

    }  

    @Override

    public void make() {

        //Set the timestamp after that of this move as current

        TimestampFactory.this.currentTimestamp = currentTimestamp + 1;

    }

  

    @Override

    public void undo() {

        //Resets to the current timestamp of this move

        TimestampFactory.this.currentTimestamp = currentTimestamp;

    }

}
You know what? a call to updateTimestamp() doesn't even really update the timestamp! and even better, it isn't correct just because of that. the line
currentTimestamp = TimestampFactory.this.currentTimestamp;
is executed when the move is constructed. so, if two such moves are constructed before any of them was executed, they bear the same value.

this is known as "lost update": you expect something to be executed in the order read-compute-write-read-compute-write, but really it's read-read-compute-compute-write-write, or something similar. both compute steps can't take into account the other computation, respectively, and the first write step is plainly overwritten.

this is exactly the problem with the code: what you expect (having the new timestamp stored after the call) ist not what the code does, and such misunderstandings are a major source of bugs. additionally, the second point is almost ignored. this layout requires an additional parameter in every method that does the slightest modification, and a manual "execute" in the controller to do the actual work.

impressing how lines fly if you really have something to talk about! i will continue with this story very soon, until then here's a quick lines-of-code count with cloc.pl:

http://cloc.sourceforge.net v 1.08  T=1.0 s (138.0 files/s, 8966.0 lines/s)
-------------------------------------------------------------------------------
Language          files     blank   comment      code    scale   3rd gen. equiv
-------------------------------------------------------------------------------
Java                138      1497      3126      4343 x   1.36 =        5906.48


Impressing, there are alone 1.5k EMPTY lines in my program ;)