www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Undo?

reply Mr. Jonse <Jonse Theory.uni> writes:
I requiring an undo feature in my code. Rather than go the 
regular route of using commands, I'm wondering if D can 
facilitate an undo system quite easily?

We can think of an undo system in an app as a sort of recorder. 
The traditional method is to use commands and inverse-commands. 
By recording the commands one can "unwind" the program by 
applying the inverse commands. The down side is that the app must 
be written with this approach in mind.

Storing the complete state of the app is another way which some 
apps use but usually it is too much data to store.

Since the only thing that one has to store from state of the app 
to the next is the change in data long with creation and deletion 
of the data, I think one could simplify the task?

Is it possible to write a generic system that records the the 
entire state changes without much boilerplate?

I'm thinking that two types of attributes would work, one for 
aggregates for creation and deletion of objects and one for 
properties to handle the data changes. If D can be used to 
automatically hook properties to have them report the changes to 
the undo system and one can properly deal with object creation 
and assignment, it might be a pretty sleek way to support undo.


Help appreciated!
Oct 09 2017
next sibling parent reply Mr. Jonse <Jonse Theory.uni> writes:
A simple(incomplete) undo system.

I'm curious about the overhead. The idea is to wrap any system 
changes using the Add function. This function stores both the 
forward and backward state changes using delegates.

By using forward, we call the action passed to set the data and 
backward will call the action to set the original data.

Delegates are used to avoid having to save the actual data 
manually, but I'm wondering if there is a lot of overhead and how 
the GC will be trashed by this, is there a better way or a better 
mechanism to use?



module undo;
import std.variant;


auto apply(T)(T t, Variant[] values) {
     import std.traits : ParameterTypeTuple;
     import std.conv : emplace;
     alias Types = ParameterTypeTuple!T;
     assert(values.length == Types.length);
     Types args = void;
     foreach(i, ref arg; args) { emplace!(typeof(arg))(&arg, 
values[i].get!typeof(arg))); }

	return { t(args); };
}

class Undo
{
	UndoNode Root;
	UndoNode CurrentNode;


	void Add(T, S, A...)(T t, S s, A a)
	{
		pragma(msg, T, " ------ ", S);
		pragma(msg, A);


	        UndoNode n = new UndoNode();
		n.Parent = CurrentNode;
		if (CurrentNode !is null)
			n.ParentBranch = CurrentNode.ParentBranch;
		foreach(_; a)
			n.Action.Data ~= Variant(_);
		if (CurrentNode !is null)
			CurrentNode.Children ~= n;
		CurrentNode = n;

		//t();		
		n.Action.cmd = { t(); };
		n.Action.inv = apply!S(s, n.Action.Data);

	}

	void Forward()
	{	
		CurrentNode.Action.cmd();
	}

	void Backward()
	{		
		CurrentNode.Action.inv();
	}	

	this()
	{
		CurrentNode = Root;
	}
}

struct UndoAction
{
	Variant[] Data;
	void delegate() cmd;
	void delegate() inv;
}


class UndoNode
{
	UndoNode Parent;
	UndoNode ParentBranch;
	UndoNode[] Children;
	UndoAction Action;
}




test code


import std.stdio;
import mUndo;


class Data
{
	int x = 0;
}






__gshared Undo GlobalUndo = new Undo();

int main(string[] argv)
{

	__gshared Data data = new Data();
	data.x = -1;
	auto globalUndo = GlobalUndo;


	globalUndo.Add(
				   {
					auto oldx = data.x;
					data.x = 4;
					return oldx;
				   },
				   (int d){
					auto oldx = data.x;
					data.x = d;
					return oldx;
				   }, data.x);

	writeln(data.x);
	globalUndo.Forward();
	writeln(data.x);
	globalUndo.Backward();
	writeln(data.x);

     writeln("------");
	getchar();
     return 0;
}
Oct 11 2017
parent Jesse Phillips <Jesse.K.Phillips+D gmail.com> writes:
On Thursday, 12 October 2017 at 02:18:49 UTC, Mr. Jonse wrote:

 A simple(incomplete) undo system.


I'd think that for D you'd want to do type wrapping where a new 
type is created which saves changes and can manage an Undo tree.

     __gshared Data data = new Data();
     auto undoable = Undo!data

     undoable.x = 5;
     assert(data.x == 5);

     undoable.undo();
     assert(data.x == 0);
     undoable.redo();
     assert(data.x == 5);

This would be done by monitoring the members which contain 
storage, available with:
https://dlang.org/phobos/std_traits.html#Fields

This is of course specific to a single object and plan for 
handling order across multiple objects along with creating an 
"Edit" where many data points could change and be undone with a 
single undo.
Oct 12 2017
prev sibling parent bitwise <bitwise.pvt gmail.com> writes:
On Tuesday, 10 October 2017 at 02:36:56 UTC, Mr. Jonse wrote:

 I requiring an undo feature in my code. Rather than go the 
 regular route of using commands, I'm wondering if D can 
 facilitate an undo system quite easily?

 We can think of an undo system in an app as a sort of recorder. 
 The traditional method is to use commands and inverse-commands. 
 By recording the commands one can "unwind" the program by 
 applying the inverse commands. The down side is that the app 
 must be written with this approach in mind.

 Storing the complete state of the app is another way which some 
 apps use but usually it is too much data to store.

 Since the only thing that one has to store from state of the 
 app to the next is the change in data long with creation and 
 deletion of the data, I think one could simplify the task?

 Is it possible to write a generic system that records the the 
 entire state changes without much boilerplate?

 I'm thinking that two types of attributes would work, one for 
 aggregates for creation and deletion of objects and one for 
 properties to handle the data changes. If D can be used to 
 automatically hook properties to have them report the changes 
 to the undo system and one can properly deal with object 
 creation and assignment, it might be a pretty sleek way to 
 support undo.


 Help appreciated!


I wrote an undo system for a level editor once:
https://github.com/nicolasjinchereau/pizza-quest/blob/90d1a2ae75c1f80ee13cedcfb634c6de0f9528db/source/editor/History.h

That class made it trivial to implement unlimited undo/redo.

Each object that's passed to History::AddObjectState() has to 
have `Undoable` implemented so that its state can be copied and 
replaced later if the object needs to be restored. In D though, 
you don't even really have to implement `Undoable`. You can make 
something like AddObjectState() into a template that uses D's 
`__traits`, or `tupleof` to record all of an object's fields into 
some generic undo state. I wrote that code so long ago that I 
don't really remember how I dealt with pointer ownership, but if 
you use GC allocation, or POD types, it should be easy.

With an approach like this, you don't need a discrete set of 
commands, but only objects that can be serialized before an 
operation, and restored afterward if you don't like the result.
Oct 12 2017