[PythonCAD] more undo

[Art Haas]

On Sat, Sep 04, 2004 at 08:57:36AM -0500, Eric Wilhelm wrote:
> I'm poking at your undo system to see how it works.  If I draw a line, 
> change the color, and then try ctrl+Z, I get this:
> 
> <raw_junk>
> 
> saveUndoData: ('add', ('point', (4, 1), 159.0, 516.0))
> saveUndoData: ('add', ('point', (5, 1), 408.0, 326.0))
> saveUndoData: ('add', ('segment', (6, 1), (None, None, None, None), 4, 
> 5))
> saveUndoData: ('attr_changed', 'color', (255, 255, 255))
> saveUndoData: ('mod', 6)
> Traceback (most recent call last):
>   File "./trunk/Interface/Gtk/gtkmenus.py", line 313, in edit_undo_cb
>     gtkimage.undo()
>   File "./trunk/Generic/image.py", line 916, in undo
>     _layer.undo()
>   File "./trunk/Generic/entity.py", line 256, in undo
>     self.__log.undo()
>   File "./trunk/Generic/logger.py", line 67, in undo
>     self.execute(True, *_data)
>   File "./trunk/Generic/layer.py", line 2388, in execute
>     _obj.undo()
>   File "./trunk/Generic/entity.py", line 256, in undo
>     self.__log.undo()
>   File "./trunk/Generic/logger.py", line 67, in undo
>     self.execute(True, *_data)
>   File "./trunk/Generic/segment.py", line 991, in execute
>     raise ValueError, "Unexpected operation: %s" % _op
> ValueError: Unexpected operation: attr_changed
> 
> </raw_junk>

[ ... Goes and looks at code ... ]

A-ha. The SegmentLog doesn't know what to do, but instead of calling
its base GraphicObjectLog.execute() method, which deals with the
'attr_changed' operation, the SegmentLog raises an exception. This
bug will also be in Circles, Arcs, Leaders, and Polylines as well.

> I've turned on some of your debugging statements in Generic/logger.py.  
> Digging around a little further, it seems that each class has an 
> execute() function, but this is only involved in undo/redo (and then 
> only with attributes?)

The execute() method is the call that does the work of the particular
undo/redo operation. As for what operations the execute method performs,
that depends on what the particular Logger instance stores. If you look
at the PointLog in 'Generic/point.py', the PointLog will store the
coordinates it receives when the movePoint() method is called, and it
stores them in a tuple where the first entry is the key 'moved'. When
the PointLog execute() method is called, the tuple that contains the
arguments is split up and the first thing in the tuple is examined to
determine what to do. With the PointLog class, all it knows how to do is
handle 'moved' operations.

> I've looked back through the archives, but can't seem to find an 
> "executive summary" of how undo/redo works.  Is there some 
> documentation that I'm missing?

Unfortunately not. The only documentation is the code, and you have to
step through it. :-(

The lack of documentation for the undo/redo stuff is a problem, and I'll
try to add some to the website as soon as possible. 

> From my poking around, it looks like the undo/redo is managed on a 
> fairly low level (where each change is logged and there must be a 
> specific action defined for undo/redo of that kind of change.)  Is 
> this correct?

Yes.

> If so, how well does this scale as new types of 
> entities and actions are added?

The current setup works well enough for the initial undo/redo
implementation. As for new entities, as they get added a class
for logging the various values that may change in the new entity will
need to be written as well.

> Is there a more generic system that would work?

I can't answer "Yes", as I don't know of a more generic system that
would work, but I can't answer question "No" as my lack of knowledge
doesn't mean that a better undo/redo approach exists.

Prior to writing the undo/redo code, I went looking for examples of how
other programs handle this feature. Everyone seems to do it differently,
not surprisingly. Some programs built in environments like KDE can
utilize some lower-level libraries or functionality provided in KDE.
The GNOME programs I looked at didn't seem to have the ability to
utilize a common GNOME undo/redo mechanism, but such an infrastructure
may exist and I just missed it. I spent a good bit of time looking at
how Gnumeric (a wonderful spreadsheet) handles undo and redo, and from
that code came my use of execute() as the Gnumeric code had comments
suggesting a common undo/redo operation handler was better than what
they had at the time.

> Consider this.  What if you wanted to create an animation of a 
> session's editing changes?  What if you wanted to create it 
> backwards?  Ignoring the animation issues, how would the code be able 
> to create the data at each change point?  What if you want to undo 
> the last thing done before the file was last saved?
> 
> Global snapshots at each change would be the most generic way, but 
> also the most expensive.  Differences of these snapshots might be 
> less expensive, but that could be tricky to do efficiently (unless 
> you work with the persistent directory idea.)
> 
> With the logging system, you have to have a record of each change and 
> a function that is able to undo each particular change.  This gives a 
> foo() and unfoo() pair of functions for each particular action.  
> Efficient, but hard to code and maintain.
> 
> So, global the snapshot/rollback undo is really simple and hard to get 
> wrong.  The local change-specific undo is really CPU efficient and 
> hard to get right.
> 
> Assuming that you don't want to explore a global diff/patch undo 
> system, what would make the local scheme more robust?

I believe the global approach is becomes unworkable as the size of the
drawing - number of entities - increases. Each entity would have to have
its various values queried and then stored in some fashion. So for
drawings with hundreds or thousands of entities, each action in the
drawing would means retrieving lots of info that hasn't changed, and the
storage requirements for the drawing would explode. Yes, it is harder to
store only the bits that changed, but the memory requirements are
signifcantly smaller and the CPU usage is low. In a way, the undo/redo
stuff is storing just the difference between the drawing at one point in
time and another.

As for making the existing scheme more robust, I would suggest adding
unit test into the repository that would exercise the entity and its
logging abilities. When the project started I'd written some unit tests
for some of the basic entities, but there haven't been any additions is
a long while, and the advancements in the program haven't had unit tests
created for verifying the functionality works and that newer
functionality doesn't break existing code (without a good reason).

> Maybe a scripting/unscripting system?  This gives you the added 
> benefit of a scripting system while simultaneously abstracting the 
> undo mechanism into a more robust scheme and allowing the undo 
> history to be persistent across a reboot.

I don't see undo/redo stuff needing to store information after a file is
closed. Some programs may do this, allowing you to work on a drawing one
day, close it for a while, then open it up and undo the very last thing
done previously. That ability would require the storage of the undo/redo
information in the file, and that sounds like a recipe for the file size
to explode.

> If you build this into the existing logger, a syntax like the 
> following might work.
> 
>   entity CHANGE property TO value
> 
> And to make it easily unscriptable, you could pass something like this 
> to the logger.
> 
>   entity CHANGE property FROM value1 TO value2
> 
> So, undo becomes a matter of munging the TO and FROM around.
> 
> What about create/delete?
> 
>   entity ADD type WITH property=value AND property2=value2
>   entity REMOVE type LOG property=value AND property2=value2
> 
> Of course, I'm just messing around with this SQL-like syntax, but you 
> get the idea.  It's verbose and very structured.  Designed with 
> inversion in mind.  The point is, if every action is scriptable and 
> unscriptable, the undo/redo becomes a matter of parsing and running a 
> script.

The current undo/redo stuff is somewhat similar to this, except the
information is stored in a tuple instead of a script.

Here's a quick rundown of how undo/redo works. We'll pretend that there
is a drawing with a Point instance at (0,0), and you are going to move
it to (1,0). When the Point was added to the drawing, a PointLog was
created and connected to listen to any 'moved' messages the Point may
send. Also, the Layer containing the newly added Point tests if it has
a LayerLog instance, and if so connects the LayerLog to listen for any
'modified' message sent by the Point.

1) Point is moved by Point.setCoords() method. The move() or setX()
methods also could be used, but we'll use setCoords() for this
example.
2) The displacement is large enough that the point sends out the 'moved'
message, and the old coordinates are passed as arguments as part
of the sendMessage() call.
3) The PointLog receives the 'moved' message and invokes its
movePoint() method.
4) The PointLog stores the information as ('moved', x, y) where 'x'
and 'y' were the old coordinates. The info is stored as ('moved', 0, 0).
5) The Point issues a 'modified' message.
6) The LayerLog receives the 'modified' message and invokes its modObj()
method.
7) The modObj() method stores in the Layer log the information that
the Point has been modified. This info is stored as ('mod', id), where
'id' is the value returned by the entity.getID() method, not the python
builtin id(). We'll pretend that our Point has an id of 5, so the
LayerLog stores ('mod', 5).
8) The Layer sends a 'modified' message out.

The Image containing the Layer listens for 'modified' messages, and it
saves in a list the Layer that sent the signal.

Now, time to undo.

1) The image checks for the last item in the list it keeps of undoable
actions (see Generic/image.py::undo()).
2) The Layer sending the image is identified, and the Layer's undo()
method is called (see Generic/entity.py::undo())
3) If the layer has a LayerLog, the LayerLog undo() method is called
(see Generic/logger.py::undo())
4) The LayerLog takes the last item on its list - ('mod', 5) - and
invokes the execute() method with the tuple as arguments. 
5) The execute() method sees the first part of the tuple is 'mod', so
the object id is extracted from the tuple (5), and the object having
that id is found (our Point). (see Generic/layer.py::execute()).
6) The Point.undo() method is then invoked (see Generic/entity.py::execute()).
7) The Point checks to see if it has a PointLog, and as it does
executes the PointLog's undo() method (see Generic/logger.py::undo()).
7) The PointLog pops the last thing off its list - ('moved', 0, 0) - and
invokes the execute() method the the tuple as arguments.
8) The execuate method sees the first part of is 'moved', so the
PointLog ends up invoking Point.setCoords() with the old coordinates
as arguments.

If you step through the example and look at the code, you'll see how
the information for redo operations is stored when doing the undo.
You'll also see how places where various messages get ignored. When
executing an undo operation, the entity logs would become invalid if
they tried to store the effects of the operation as if it was a non-undo
type change. To accomplish this, startUndo()/endUndo() calls are placed
around the object method that will be invoked to actually do the undo
operation.

> Other than the undo system uses, I'm not sure that this sort of macro 
> scripting is a good idea.  After all, you could simply evaluate some 
> Python, or even have an embedded Perl interpreter.  The problem with 
> these languages is that parsing for the sake of inversion is HARD.

I'd say it is close to impossible.

While not perfect by any stretch, the undo/redo approach used in
PythonCAD is performing its job well. Yes, it can be improved, as
the bug you found points out. I hope the description of the undo
operation I gave above helps to explain how things currently work.

Art
-- 
Man once surrendering his reason, has no remaining guard against absurdities
the most monstrous, and like a ship without rudder, is the sport of every wind.

-Thomas Jefferson to James Smith, 1822