View Issue Details

IDCategoryLast Update
0001136features2006-02-04 00:33
ReportertimbyrAssigned Totimbyr 
Status assignedResolutionopen 
Product Version 
Fixed in Version 
Summary0001136: Design of new undo/redo system.
DescriptionAttached is an irc log of a discussion about using a new model for interacting with state history or to put it another way a new undo system. The purpose of which would be to increase the functionality of ardour and simplify some aspects of development.

The new system discussed would have the following benefits over the existing system.

Changes to objects are implicitly monitored by the undo system rather that having to explicitly add the changes. for example

Editor::clear_markers ()
    if (session) {
        session->begin_reversible_command (_("clear markers"));
        session->add_undo (session->locations()->get_memento());
        session->locations()->clear_markers ();
        session->add_redo_no_execute (session->locations()->get_memento());
        session->commit_reversible_command ();


Editor::clear_markers ()
    if (session) {
        session->begin_reversible_command (_("clear markers"));
        session->locations()->clear_markers ();
        session->commit_reversible_command ();

It works on the assumption that if you change an object, then that object knows that it has changed and can monitor its own state or preferably just signal another state manager class that its state has changed, rather than having to explicitly tell a session/gui that you are changing its state. It might seem trivial, if we just look at LOC saved grep -R -P "add_undo|add_redo" * | wc -l currently displays 211 lines which isn't that significant but it reduces the complexity of writing new object manipulation routines and would stop some of the types of bugs that are currently in ardour where some of the modifications to objects are part of the undo/redo system and others aren't.

Another major benefit is that the state history can be serialized which enables the undo system to be restored each time a session is loaded. It also means that the state of individual objects can be restored from a previous state without effecting other objects in the state history. For example a user may want to restore the entire state of a track to an old state but still keep all the changes that have been made to other tracks. Or to put it another way "I want to see what that track sounded like yesterday before I made a whole bunch of silly changes but keep everything else the same" etc.
TagsNo tags attached.


2005-10-27 03:43


statehistory.log.txt (18,624 bytes)
timbyr las: I don't think there will be a problem with rcu and undo. It actually makes it easier because then the undo system has a reference to all the old state data and it can't be deleted via unref being called from a RT RT thread a
timbyr oops.
las timbyr: its never deleted.
las timbyr: but the undo state refers to objects that no longer exist
timbyr las: redhat is having c++ ABI issues with the I18N input modules, as static linking isn't an option I've been asked to look into possible solutions/guides. fun fun fun.
las timbyr: and if RCU keeps on being used, that means we can't delete the copies it generates at any time either. which gets to be a bit insane.
timbyr las: why don't they exist, the undo system has a reference to them so they must exist.
las timbyr: tell them to go shoot the g++ crew
las timbyr: we can't keep all these object copies around ...
timbyr las: the old copies are deleted via unref.
las timbyr: but they will never unref'ed to the point of deletion until the undo state is deleted
las timbyr: and even then, it won't work correctly
las timbyr: the undo state is re-created by executing a void sigc::slot<void>
las timbyr: which will modify the object from which the undo memento was created
las timbyr: but thats not going to be the object "in use" anymore if RCU is used
nick_m|afk las, are you doing the region list?
* nick_m|afk is now known as nick_m
timbyr las: processing.
las nick_m: already done
las nick_m: or rather, first pass is already done
las nick_m: i want to go back and handle DnD again now that i understand it
timbyr las: oh ok, I get ya. rcu could work using object states. I know this isn't entirely how the current system works but bare with me. take for example a region, the region has a class member called RegionState(or whatever) that is wrapped in an RCU class. when the region is modified the region class gets a new region state(copy of existing) from the RCU class by calling the writer method. After the RegionState has been modified the Region 
timbyr class then emits a signal something like sigc::signal<void, Glib::RefPtr<RegionState> > that a global state management class is connected to. There is then another class that converts a RegionState into an XML node and the state management class updates the XML document. Whether or not it does it in the same writer thread is another thing. How the state management class stores region states and how undo works I won't go into but as you c
timbyr an see it has a reference to all the states of a region it can use a set_state method or preferably an operator= to restore state.
las timbyr: lets see ....
las timbyr: first of all, there is a general weakness in libardour that when we started adding XML serialization, it was never done properly
las timbyr: consequently, there is no Session::operator= (const XMLNode&) method
las timbyr: and that is partly because for many objects, there is no Session::operator= (const XMLNode*) either
las timbyr: the existing set_state (const XMLNode&) methods were envisaged (stupidly, incorrectly) as serving a more limited role
las timbyr: that said, the undo/redo system is largely immune from this particular isue
las timbyr: it is immune because it doesn't use XML at all
las timbyr: let me explain briefly how it works
timbyr las: I know how it works.
las timbyr: ok :)
las timbyr: what you are proposing would imply an undo/redo system that was completely redundant
timbyr las: sorry, I thought I'd save you the time.
las timbyr: because all the objects that are referred to by undo state continue to exist, and continue to exist in their pre-modification state
las timbyr: so undo would simply involve switching back to use that object, rather than another one
las timbyr: this is problematic, for several reasons
timbyr las: not a different object, a different object state.
las timbyr: well, this gets back to my first point :)
las timbyr: if you assume you can always write a perfect operator= (someState&) then ok
timbyr las: what point is that? that heaps of data is stored?
las timbyr: but (a) we don't have such methods (b) i think they are hard to write 
timbyr las: I can't think of a class in ardour that you couldn't, but you are obviously more familiar with it.
las timbyr: what does operator= do for a playlist?
timbyr las: you already have such stuff in some places.
las timbyr: almost none of it is a real assignment op, its almost always partial
timbyr las: ok, for playlist....
las timbyr: right now, playlist mods are horribly inefficient, and its for the reasons that make it hard to write operator=, i think.
las timbyr: take the case of moving a region in the playlist
las timbyr: and explain to me how it should work (i know how its borked already ;)
timbyr las: ok, just a sec.
timbyr las: It would work exactly as it does currently, but I'll describe it in terms of RCU if you like.
las timbyr: what it does currently is a bit insane
las timbyr: it gets an undo memento from every region in the playlist, not just the one that was moved
timbyr las: region modified, playlist notified, playlist creates a copy of playlist(even though it doesn't really have to in this case)
las timbyr: the efficient way to handle a move is to store an undo op that just moves the region back to where it came from
timbyr las: yes, but that only allows for sequential undo/redo operations. you can't say for instance, I want that track that to be in the state it was yesterday without undoing all the operations, or I guess you could store an undo/redo stack for each object, but then you can't serialize it easily which is trivial using object states.
las timbyr: correct.
las timbyr: but we don't have object states
las :(((
las timbyr: so yes, this needs to be corrected.
timbyr las: yes, not for all objects. but no reason why you can't.
las timbyr: so you would store the "copy of the playlist" not as a set of regions, but as a set of region states
timbyr las: yes, A playlist would have to have an operator=(const Glib::RefPtr< Playlist >&) method that gets a new state(RCU) modifes it to reflect the old state, then for each Region in the list call a similar method. So it means that operator=(const Glib::RefPtr< StateClass >) wouldn't emit a state changed signal.
las timbyr: that strikes me as a little odd.
las timbyr: the original object has operator=() called on it, but its state doesn't change?
timbyr las: it may be, let me see if I got it right.
las timbyr: presumably, the idea is that the GUI has "undo" requested
timbyr las: yes sorry its state does change, so a state_changed signal would be emitted. I thought there might be an issue with changing the state from an old state but maybe not.
las timbyr: so *it* does RC on the object(s) in question, calls operator=() on them, and then does the U
las timbyr: at which time there must be some way to emit "state changed"
las timbyr: although presumably, it would always be called, since there was some reason to do a U
timbyr las: sorry what stage of the undo process are you describing?
las timbyr: i'm thinking of it all the way through. the GUI gets told to do an undo (say, ctrl-z)
las timbyr: it looks in the history stack, and executes an undo memento 
las timbyr: the memento has a reference to the ... hmm ...
las timbyr: lets skip that part for now
timbyr las: sorry yes, even though the state being restored will be the same as the new state a copy still has to be made so there will be two state classes with the same data inside, but it has to be done I think.
las timbyr: somehow, it finds an object of the correct type, and does RC, then operator=, then U
las timbyr: but ... this implies that we have two operator= methods, one for operator= (someState&), and one for operator= (theCopy&)
las timbyr: presumably unified into operator= (theCopy& copy) {return operator= (copy.state()); }
las timbyr: tis second method is called at U time, right?
timbyr las: I'm getting a little confused :) an objects state is access via the RCU's reader method. so the current state of an object is always stored inside it.
las timbyr: but undo is supposed to change the state of the current "in use" object
las timbyr: so at some point along the way, an undo operation has to carry out an update step
las timbyr: i forgot, update is a ptr swap. sorry.
timbyr las: to restore an old state we have to call RCU->writer() to get a new copy of the data and modify it. the reason that the change state signal won't be called after a state has been restored is becuase the state manager class is restoring a state, so a separate signal would be emitted no signify that the state has changed, but not the same signal that the state manager class is connected to to be notified of a user driven state change.
las timbyr: ok, so undo has to locate the object in question, then change its state via operator=(someState&), then do the update to swap ptrs
las timbyr: i still got that wrong, it has to find the object, then do RC, then state mode, then update, right?
timbyr las: yes, so it has a map of some kind. that contain a pointer to the object, and a list of states/or a list with that contains a wrapper class that contains other data like modification time etc.
las timbyr: i understand your point about the signals too
las timbyr: well, finding the object is the hard part here :)
timbyr las: the RCU is automatic, it is all done by the smart pointer classes.
las timbyr: but these changes have all been envisioned before
las timbyr: it requires several fundamental engineering changes, which is a bit scary
las timbyr: but worthwhile, i think. 
timbyr las: yes I think at least I have brought them up before, using rcu doesn't change the design at all, it could be done without it. it just means that readers of the data don't need to take locks.
las timbyr: one question is: how many classes are there where sizeof(objectState) << sizeof (object) ?
timbyr las: hah not many.
las timbyr: because if that's true, then the worthiness of having a separate object state becomes questionable, eh?
las timbyr: however, Region is an interesting example of an approach to this. Region IS-A RegionState
las timbyr: i.e. define the core attributes of the object type, then extend to provide methods and non-state member variables (if such a thing can be said to exist)
timbyr las: you need a separate state object so that you can wrap it in an RCU class so that pointers/refs to say a region don't change.
timbyr las: yes can't do IS-A
las timbyr: why not?
las timbyr: Region::operator= (const RegionState&)
las timbyr: (RegionState *) ptrToRegion;
las timbyr: etc.
timbyr las: well if you don't use RCU then that is what you would use.
las timbyr: what do you need with RCU?
las timbyr: my impression was that RCU::writer() would copy the object, then we call operator=(const RegionState&), then we unref the copy (or something) and that does the update
timbyr las: well with the way I've implemented it you need some sort of smart pointer class that track how many global references there are to an object. Glib::RefPtr leaves this up to the class and calls a classes reference/unreference methods. If you just pass around bare references it is harder to track etc.
las timbyr: no, thats fine, but you're still doing fundamentally the same operations, no?
timbyr las: are no, that is the beauty of it, the data is updated automatically when the Glib::RefPtr that was recieved by calling writer goes out of scope.
las timbyr: same difference from this perspective, i think.
timbyr las: yes same same.
las timbyr: the point is you use operator= (someState&) to do the undo/redo
las timbyr: the hard part is (a) defining object states (b) finding objects
las timbyr: but this was part of my original plan for revamping undo/redo
las timbyr: all objects have to inherit from a class that has a name or id that is global
las timbyr: and there is a global map of all such objects
timbyr las: huh? please explain
las timbyr: bear with me a sec
timbyr ok, I need to do something for a bit anyway.
las timbyr: all undo/redo ops consist of the id of the object to manipulated
las timbyr: combined with either a state or (and now, given RCU, probably not) some named method+args
las timbyr: to carry out the op, you first find the object by looking it up by id in the global map
las timbyr: this lets you serialize undo history to disk
las timbyr: and then once you have the object you either (A: PRE-RCU) modify the object directly (B: PRE-RCU) do an RCU on it
las timbyr: if all undo switches to using object state, its a bit inefficient, but it is a uniform model that can easily (!) be serialized
las timbyr: so in shorthand, all undo/redo becomes
las object_map[undo_record.objectID]->writer() = undo_record.objectState();
las timbyr: roughly correct?
las timbyr: and serialization of the undo/redo history becomes just a matter of writing pairs of object:state to a disk file
las timbyr: where the state is itself serialized
timbyr las: yes, but you have to work out which state you are going to restore first I guess.
las timbyr: thats in the undo record
timbyr las: oh, I see so an undo record is used for each object that changes in a "change set", that sounds similar to the model I once envisiged.
las timbyr: yes
las timbyr: technically, a full undo record is a list of object:state pairs
las timbyr: which are serially ordered 
las timbyr: so you can actually undo something "atomically" that involved changing several objects at once
timbyr las: yep, sounds good to me.
las timbyr: "atomic" here just means from a UI perspective, nothing to with true atomicity of course
las timbyr: this is probably about as much work as the GTK2 port :)
timbyr las: So just let me go through what a single undo/redo process would involve and see if you agree ok?
las timbyr: ok
timbyr las: yes, that is why you should decide whether it is worth the effort. I don't mind helping out on this, much preferred to GUI stuff at the moment.
las timbyr: it can't happen at this point in time. way too disruptive. but it should start after about 2.1
las timbyr: my biggest problem right now is that work itself is very mentally consuming (and not in a good way). i plan to do ardour work at night, but i just don't have it in me.
timbyr las: So lets say the a user does something that modifes session data. begin_reversible_command()/state_change is called and a new change set is made. modifications are then made to the various objects and for each object that is modifed a new state will be created and state manager class will then add a new undo_record/change to the change set for each object. When the modifications are complete the commit_reversible_command/commit_chang
timbyr e method is called and the change set is added to the undo/redo stack etc. To undo a change we grab the old change set and apply it, which restores the states of objects etc.
las timbyr: more or less. we have to grab 2 states per object, 1 to undo, 1 to redo
timbyr las: yes, very big change. Oh just for kicks I started modifying midi++ and libardour to depend on glibmm rather than pbd, I finished midi++ which was easy, but libardour will take alot of work. It was more just out of interest to see how much dependence there was on pbd as there is a fair bit of stuff in it that isn't used etc.
timbyr las: oh yes, I forgot about that one.
las timbyr: the thing that bothers me a little is this apparent dichotomy between an undo/redo system based on storing actions and one based on states
las timbyr: the action based one seems *massively* more efficient
las timbyr: but is tricky to serialize
timbyr las: yes and serializing an action based undo system would be pretty hard.
las timbyr: with an action based one, the outline above is changed so that rather than storing states, we store operations (by name) and arguments (using templates)
las timbyr: then we serialize as object_id:operation:argument_list
timbyr las: you have outlined it before and I cringed then and I'm cringing now.
las timbyr: doesn't change the way it interacts with RCU, but its way more efficient: no more states floating around. however, you cannot, as you pointed out, jump straight into a given "state"
timbyr las: well perhaps cringed is too strong. I just prefer complete state storage.
las timbyr: the memory costs can be substantial
las timbyr: imagine an experimental piece with 5K regions per track
timbyr las: I like the idea of being able to restore a particular state for a single object. It also opens up all sorts of session merging possibilites.
las timbyr: every modification to a region, even just position, requires 10K regions states to be saved
timbyr las: yes we should definately do some rough calculations before any significant work is done.
las timbyr: still, i just described what we have now ;)
timbyr las: but as the states are in a format that can be easily converted into XML etc. it is just a matter of only storing x changesets in the undo/redo system and writting the rest to disk.
las timbyr: so true
timbyr las: not trivial, but not too hard.
las timbyr: man, this would all be so much interesting than the RPC crapola i have to deal with at work
las timbyr: wah! i want to get paid for this! :))
timbyr las: meh, This week I've written an smtp proxy, http proxy authentification client and server in perl and an open gl scene renderer etc. it all sucks :)
las timbyr: try hacking a 20 year old RPC system to handle a more modern design, except that the hack is really to a code generator
las timbyr: i can so live without having to do this.
timbyr las: I might grab this log, so that when we come back to this there is a good starting point. I forget small details given a few months.
las timbyr: great idea. maybe even file it in mantis?
timbyr las: good idea.
las timbyr: so the one remaining question about RCU: are there any objects for which the copy step is too costly ... diskstreams seem to be the only candidate
las timbyr: other than Session, of course :)
las timbyr: although seriously, Session is a bit of a problem.
timbyr las: that would have to be worked out. the buffers etc dont' need to be of course so it is just POD stuff I think.
las timbyr: possible refactoring: RealTimeSession, NonRealTimeSession; RCU used only on RTSession
las timbyr: you might want to imagine how one would do a seek/locate with RCU
timbyr las: Session class is way way way to big anyway. It needs to be refactored IMO.
las timbyr: true. another long put off task
timbyr las: I'll continue to think on it but I have to get back to work. thanks for the interesting discussion.
las timbyr: thank you!
statehistory.log.txt (18,624 bytes)


2006-02-01 00:54

developer   ~0002446

There is also the possibility of instead of using a begin/end pair, you just use a marker, like mark_undo_point() that will finalize the current undo action and create a new undo action.

Issue History

Date Modified Username Field Change
2005-10-27 03:43 timbyr New Issue
2005-10-27 03:43 timbyr File Added: statehistory.log.txt
2005-10-27 03:43 timbyr E-mail =>
2005-10-27 03:43 timbyr Name => Tim Mayberry
2006-02-01 00:54 timbyr Note Added: 0002446
2006-02-04 00:33 timbyr Status new => assigned
2006-02-04 00:33 timbyr Assigned To => timbyr