Experimental-ish rollback functionality

20 files changed, 1316 insertions, 27 deletions

diff --git a/builtin/chatcommands.lua b/builtin/chatcommands.lua
index da9e6c78c..49ae8c633 100644
--- a/builtin/chatcommands.lua
+++ b/builtin/chatcommands.lua
@@ -496,3 +496,75 @@ minetest.register_chatcommand("pulverize", {
 	end,
 })
 
+-- Key = player name
+minetest.rollback_punch_callbacks = {}
+
+minetest.register_on_punchnode(function(pos, node, puncher)
+	local name = puncher:get_player_name()
+	if minetest.rollback_punch_callbacks[name] then
+		minetest.rollback_punch_callbacks[name](pos, node, puncher)
+		minetest.rollback_punch_callbacks[name] = nil
+	end
+end)
+
+minetest.register_chatcommand("rollback_check", {
+	params = "[<range>] [<seconds>]",
+	description = "check who has last touched a node or near it, "..
+			"max. <seconds> ago (default range=0, seconds=86400=24h)",
+	privs = {rollback=true},
+	func = function(name, param)
+		local range, seconds = string.match(param, "(%d+) *(%d*)")
+		range = tonumber(range) or 0
+		seconds = tonumber(seconds) or 86400
+		minetest.chat_send_player(name, "Punch a node (limits set: range="..
+				dump(range).." seconds="..dump(seconds).."s)")
+		minetest.rollback_punch_callbacks[name] = function(pos, node, puncher)
+			local name = puncher:get_player_name()
+			local actor, act_p, act_seconds =
+					minetest.rollback_get_last_node_actor(pos, range, seconds)
+			if actor == "" then
+				minetest.chat_send_player(name, "Nobody has touched the "..
+						"specified location in "..dump(seconds).." seconds")
+				return
+			end
+			local nodedesc = "this node"
+			if act_p.x ~= pos.x or act_p.y ~= pos.y or act_p.z ~= pos.z then
+				nodedesc = minetest.pos_to_string(act_p)
+			end
+			minetest.chat_send_player(name, "Last actor on "..nodedesc.." was "..
+					actor..", "..dump(act_seconds).."s ago")
+		end
+	end,
+})
+
+minetest.register_chatcommand("rollback", {
+	params = "<player name> [<seconds>] | :liquid [<seconds>]",
+	description = "revert actions of a player; default for <seconds> is 60",
+	privs = {rollback=true},
+	func = function(name, param)
+		local target_name, seconds = string.match(param, ":([^ ]+) *(%d*)")
+		if not target_name then
+			local player_name = nil;
+			player_name, seconds = string.match(param, "([^ ]+) *(%d*)")
+			if not player_name then
+				minetest.chat_send_player(name, "Invalid parameters. See /help rollback and /help rollback_check")
+				return
+			end
+			target_name = "player:"..player_name
+		end
+		seconds = tonumber(seconds) or 60
+		minetest.chat_send_player(name, "Reverting actions of "..
+				dump(target_name).." since "..dump(seconds).." seconds.")
+		local success, log = minetest.rollback_revert_actions_by(
+				target_name, seconds)
+		for _,line in ipairs(log) do
+			minetest.chat_send_player(name, line)
+		end
+		if success then
+			minetest.chat_send_player(name, "Reverting actions succeeded.")
+		else
+			minetest.chat_send_player(name, "Reverting actions FAILED.")
+		end
+	end,
+})
+
diff --git a/builtin/privileges.lua b/builtin/privileges.lua
index 6cb42c103..9ec09d7f6 100644
--- a/builtin/privileges.lua
+++ b/builtin/privileges.lua
@@ -44,5 +44,5 @@ minetest.register_privilege("fast", {
 	description = "Can walk fast using the fast_move mode",
 	give_to_singleplayer = false,
 })
-
+minetest.register_privilege("rollback", "Can use the rollback functionality")
 
diff --git a/doc/lua_api.txt b/doc/lua_api.txt
index d47281b2d..46ea3a86e 100644
--- a/doc/lua_api.txt
+++ b/doc/lua_api.txt
@@ -889,6 +889,14 @@ minetest.get_craft_recipe(output) -> input
                               stack 5, stack 6, stack 7, stack 8, stack 9 }
 ^ input.items = nil if no recipe found
 
+Rollbacks:
+minetest.rollback_get_last_node_actor(p, range, seconds) -> actor, p, seconds
+^ Find who has done something to a node, or near a node
+^ actor: "player:<name>", also "liquid".
+minetest.rollback_revert_actions_by(actor, seconds) -> bool, log messages
+^ Revert latest actions of someone
+^ actor: "player:<name>", also "liquid".
+
 Defaults for the on_* item definition functions:
 (These return the leftover itemstack)
 minetest.item_place_node(itemstack, placer, pointed_thing)
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index e369b9623..43d7f241a 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -153,6 +153,8 @@ configure_file(
 )
 
 set(common_SRCS
+	rollback_interface.cpp
+	rollback.cpp
 	genericobject.cpp
 	voxelalgorithms.cpp
 	sound.cpp
diff --git a/src/content_abm.cpp b/src/content_abm.cpp
index edadfe99e..12dbeea8e 100644
--- a/src/content_abm.cpp
+++ b/src/content_abm.cpp
@@ -26,6 +26,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "settings.h"
 #include "mapblock.h" // For getNodeBlockPos
 #include "mapgen.h" // For mapgen::make_tree
+#include "map.h"
 
 #define PP(x) "("<<(x).X<<","<<(x).Y<<","<<(x).Z<<")"
 
diff --git a/src/content_cao.cpp b/src/content_cao.cpp
index 58ff130f2..aa5c2d674 100644
--- a/src/content_cao.cpp
+++ b/src/content_cao.cpp
@@ -39,6 +39,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "util/numeric.h" // For IntervalLimiter
 #include "util/serialize.h"
 #include "util/mathconstants.h"
+#include "map.h"
 
 class Settings;
 struct ToolCapabilities;
diff --git a/src/content_cso.cpp b/src/content_cso.cpp
index 6f7ecbe50..666f17734 100644
--- a/src/content_cso.cpp
+++ b/src/content_cso.cpp
@@ -23,6 +23,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "environment.h"
 #include "gamedef.h"
 #include "log.h"
+#include "map.h"
 
 static void setBillboardTextureMatrix(scene::IBillboardSceneNode *bill,
 		float txs, float tys, int col, int row)
diff --git a/src/environment.cpp b/src/environment.cpp
index 02ca1f71b..9390101e7 100644
--- a/src/environment.cpp
+++ b/src/environment.cpp
@@ -349,6 +349,17 @@ ServerEnvironment::~ServerEnvironment()
 	}
 }
 
+Map & ServerEnvironment::getMap()
+{
+	return *m_map;
+}
+
+ServerMap & ServerEnvironment::getServerMap()
+{
+	return *m_map;
+}
+
+
 void ServerEnvironment::serializePlayers(const std::string &savedir)
 {
 	std::string players_path = savedir + "/players";
diff --git a/src/environment.h b/src/environment.h
index 0e4b85e06..6c52b003d 100644
--- a/src/environment.h
+++ b/src/environment.h
@@ -33,11 +33,12 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include <set>
 #include "irrlichttypes_extrabloated.h"
 #include "player.h"
-#include "map.h"
 #include <ostream>
 #include "activeobject.h"
 #include "util/container.h"
 #include "util/numeric.h"
+#include "mapnode.h"
+#include "mapblock.h"
 
 class Server;
 class ServerEnvironment;
@@ -46,6 +47,8 @@ class ServerActiveObject;
 typedef struct lua_State lua_State;
 class ITextureSource;
 class IGameDef;
+class Map;
+class ServerMap;
 class ClientMap;
 
 class Environment
@@ -191,11 +194,9 @@ public:
 			IBackgroundBlockEmerger *emerger);
 	~ServerEnvironment();
 
-	Map & getMap()
-		{ return *m_map; }
+	Map & getMap();
 
-	ServerMap & getServerMap()
-		{ return *m_map; }
+	ServerMap & getServerMap();
 
 	lua_State* getLua()
 		{ return m_lua; }
diff --git a/src/gamedef.h b/src/gamedef.h
index 88c15be78..87918d726 100644
--- a/src/gamedef.h
+++ b/src/gamedef.h
@@ -29,6 +29,7 @@ class ICraftDefManager;
 class ITextureSource;
 class ISoundManager;
 class MtEventManager;
+class IRollbackReportSink;
 
 /*
 	An interface for fetching game-global definitions like tool and
@@ -54,6 +55,10 @@ public:
 	// Only usable on the client
 	virtual ISoundManager* getSoundManager()=0;
 	virtual MtEventManager* getEventManager()=0;
+
+	// Only usable on the server, and NOT thread-safe. It is usable from the
+	// environment thread.
+	virtual IRollbackReportSink* getRollbackReportSink(){return NULL;}
 	
 	// Used on the client
 	virtual bool checkLocalPrivilege(const std::string &priv)
@@ -66,6 +71,7 @@ public:
 	ITextureSource* tsrc(){return getTextureSource();}
 	ISoundManager* sound(){return getSoundManager();}
 	MtEventManager* event(){return getEventManager();}
+	IRollbackReportSink* rollback(){return getRollbackReportSink();}
 };
 
 #endif
diff --git a/src/inventorymanager.cpp b/src/inventorymanager.cpp
index 06978fbb9..85668d645 100644
--- a/src/inventorymanager.cpp
+++ b/src/inventorymanager.cpp
@@ -25,6 +25,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "main.h"  // for g_settings
 #include "settings.h"
 #include "craftdef.h"
+#include "rollback_interface.h"
 
 #define PP(x) "("<<(x).X<<","<<(x).Y<<","<<(x).Z<<")"
 
@@ -200,6 +201,14 @@ void IMoveAction::apply(InventoryManager *mgr, ServerActiveObject *player, IGame
 	}
 
 	/*
+		Do not handle rollback if both inventories are that of the same player
+	*/
+	bool ignore_rollback = (
+		from_inv.type == InventoryLocation::PLAYER &&
+		to_inv.type == InventoryLocation::PLAYER &&
+		from_inv.name == to_inv.name);
+
+	/*
 		Collect information of endpoints
 	*/
 
@@ -344,6 +353,41 @@ void IMoveAction::apply(InventoryManager *mgr, ServerActiveObject *player, IGame
 			<<std::endl;
 
 	/*
+		Record rollback information
+	*/
+	if(!ignore_rollback)
+	{
+		IRollbackReportSink *rollback = gamedef->rollback();
+
+		// If source is not infinite, record item take
+		if(!src_can_take_count != -1){
+			RollbackAction action;
+			std::string loc;
+			{
+				std::ostringstream os(std::ios::binary);
+				from_inv.serialize(os);
+				loc = os.str();
+			}
+			action.setModifyInventoryStack(loc, from_list, from_i, false,
+					src_item.getItemString());
+			rollback->reportAction(action);
+		}
+		// If destination is not infinite, record item put
+		if(!dst_can_put_count != -1){
+			RollbackAction action;
+			std::string loc;
+			{
+				std::ostringstream os(std::ios::binary);
+				to_inv.serialize(os);
+				loc = os.str();
+			}
+			action.setModifyInventoryStack(loc, to_list, to_i, true,
+					src_item.getItemString());
+			rollback->reportAction(action);
+		}
+	}
+
+	/*
 		Report move to endpoints
 	*/
 	
@@ -405,7 +449,7 @@ void IMoveAction::apply(InventoryManager *mgr, ServerActiveObject *player, IGame
 					L, from_inv.p, from_list, from_i, src_item, player);
 		}
 	}
-
+	
 	mgr->setInventoryModified(from_inv);
 	if(inv_from != inv_to)
 		mgr->setInventoryModified(to_inv);
@@ -489,6 +533,11 @@ void IDropAction::apply(InventoryManager *mgr, ServerActiveObject *player, IGame
 	}
 
 	/*
+		Do not handle rollback if inventory is player's
+	*/
+	bool ignore_src_rollback = (from_inv.type == InventoryLocation::PLAYER);
+
+	/*
 		Collect information of endpoints
 	*/
 
@@ -575,6 +624,28 @@ void IDropAction::apply(InventoryManager *mgr, ServerActiveObject *player, IGame
 		scriptapi_nodemeta_inventory_on_take(
 				L, from_inv.p, from_list, from_i, src_item, player);
 	}
+
+	/*
+		Record rollback information
+	*/
+	if(!ignore_src_rollback)
+	{
+		IRollbackReportSink *rollback = gamedef->rollback();
+
+		// If source is not infinite, record item take
+		if(!src_can_take_count != -1){
+			RollbackAction action;
+			std::string loc;
+			{
+				std::ostringstream os(std::ios::binary);
+				from_inv.serialize(os);
+				loc = os.str();
+			}
+			action.setModifyInventoryStack(loc, from_list, from_i,
+					false, src_item.getItemString());
+			rollback->reportAction(action);
+		}
+	}
 }
 
 void IDropAction::clientApply(InventoryManager *mgr, IGameDef *gamedef)
diff --git a/src/map.cpp b/src/map.cpp
index dc1f45068..734122105 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -32,6 +32,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "nodedef.h"
 #include "gamedef.h"
 #include "util/directiontables.h"
+#include "rollback_interface.h"
 
 #define PP(x) "("<<(x).X<<","<<(x).Y<<","<<(x).Z<<")"
 
@@ -932,12 +933,12 @@ void Map::updateLighting(core::map<v3s16, MapBlock*> & a_blocks,
 void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 		core::map<v3s16, MapBlock*> &modified_blocks)
 {
-	INodeDefManager *nodemgr = m_gamedef->ndef();
+	INodeDefManager *ndef = m_gamedef->ndef();
 
 	/*PrintInfo(m_dout);
 	m_dout<<DTIME<<"Map::addNodeAndUpdate(): p=("
 			<<p.X<<","<<p.Y<<","<<p.Z<<")"<<std::endl;*/
-
+	
 	/*
 		From this node to nodes underneath:
 		If lighting is sunlight (1.0), unlight neighbours and
@@ -950,6 +951,11 @@ void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 
 	bool node_under_sunlight = true;
 	core::map<v3s16, bool> light_sources;
+	
+	/*
+		Collect old node for rollback
+	*/
+	RollbackNode rollback_oldnode(this, p, m_gamedef);
 
 	/*
 		If there is a node at top and it doesn't have sunlight,
@@ -960,7 +966,7 @@ void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 	try{
 		MapNode topnode = getNode(toppos);
 
-		if(topnode.getLight(LIGHTBANK_DAY, nodemgr) != LIGHT_SUN)
+		if(topnode.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN)
 			node_under_sunlight = false;
 	}
 	catch(InvalidPositionException &e)
@@ -980,7 +986,7 @@ void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 	{
 		enum LightBank bank = banks[i];
 
-		u8 lightwas = getNode(p).getLight(bank, nodemgr);
+		u8 lightwas = getNode(p).getLight(bank, ndef);
 
 		// Add the block of the added node to modified_blocks
 		v3s16 blockpos = getNodeBlockPos(p);
@@ -997,16 +1003,16 @@ void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 		// light again into this.
 		unLightNeighbors(bank, p, lightwas, light_sources, modified_blocks);
 
-		n.setLight(bank, 0, nodemgr);
+		n.setLight(bank, 0, ndef);
 	}
 
 	/*
 		If node lets sunlight through and is under sunlight, it has
 		sunlight too.
 	*/
-	if(node_under_sunlight && nodemgr->get(n).sunlight_propagates)
+	if(node_under_sunlight && ndef->get(n).sunlight_propagates)
 	{
-		n.setLight(LIGHTBANK_DAY, LIGHT_SUN, nodemgr);
+		n.setLight(LIGHTBANK_DAY, LIGHT_SUN, ndef);
 	}
 
 	/*
@@ -1028,7 +1034,7 @@ void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 		TODO: This could be optimized by mass-unlighting instead
 			  of looping
 	*/
-	if(node_under_sunlight && !nodemgr->get(n).sunlight_propagates)
+	if(node_under_sunlight && !ndef->get(n).sunlight_propagates)
 	{
 		s16 y = p.Y - 1;
 		for(;; y--){
@@ -1044,12 +1050,12 @@ void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 				break;
 			}
 
-			if(n2.getLight(LIGHTBANK_DAY, nodemgr) == LIGHT_SUN)
+			if(n2.getLight(LIGHTBANK_DAY, ndef) == LIGHT_SUN)
 			{
 				unLightNeighbors(LIGHTBANK_DAY,
-						n2pos, n2.getLight(LIGHTBANK_DAY, nodemgr),
+						n2pos, n2.getLight(LIGHTBANK_DAY, ndef),
 						light_sources, modified_blocks);
-				n2.setLight(LIGHTBANK_DAY, 0, nodemgr);
+				n2.setLight(LIGHTBANK_DAY, 0, ndef);
 				setNode(n2pos, n2);
 			}
 			else
@@ -1079,6 +1085,17 @@ void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 	}
 
 	/*
+		Report for rollback
+	*/
+	if(m_gamedef->rollback())
+	{
+		RollbackNode rollback_newnode(this, p, m_gamedef);
+		RollbackAction action;
+		action.setSetNode(p, rollback_oldnode, rollback_newnode);
+		m_gamedef->rollback()->reportAction(action);
+	}
+
+	/*
 		Add neighboring liquid nodes and the node itself if it is
 		liquid (=water node was added) to transform queue.
 	*/
@@ -1099,7 +1116,7 @@ void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 		v3s16 p2 = p + dirs[i];
 
 		MapNode n2 = getNode(p2);
-		if(nodemgr->get(n2).isLiquid() || n2.getContent() == CONTENT_AIR)
+		if(ndef->get(n2).isLiquid() || n2.getContent() == CONTENT_AIR)
 		{
 			m_transforming_liquid.push_back(p2);
 		}
@@ -1115,7 +1132,7 @@ void Map::addNodeAndUpdate(v3s16 p, MapNode n,
 void Map::removeNodeAndUpdate(v3s16 p,
 		core::map<v3s16, MapBlock*> &modified_blocks)
 {
-	INodeDefManager *nodemgr = m_gamedef->ndef();
+	INodeDefManager *ndef = m_gamedef->ndef();
 
 	/*PrintInfo(m_dout);
 	m_dout<<DTIME<<"Map::removeNodeAndUpdate(): p=("
@@ -1129,13 +1146,18 @@ void Map::removeNodeAndUpdate(v3s16 p,
 	content_t replace_material = CONTENT_AIR;
 
 	/*
+		Collect old node for rollback
+	*/
+	RollbackNode rollback_oldnode(this, p, m_gamedef);
+
+	/*
 		If there is a node at top and it doesn't have sunlight,
 		there will be no sunlight going down.
 	*/
 	try{
 		MapNode topnode = getNode(toppos);
 
-		if(topnode.getLight(LIGHTBANK_DAY, nodemgr) != LIGHT_SUN)
+		if(topnode.getLight(LIGHTBANK_DAY, ndef) != LIGHT_SUN)
 			node_under_sunlight = false;
 	}
 	catch(InvalidPositionException &e)
@@ -1157,7 +1179,7 @@ void Map::removeNodeAndUpdate(v3s16 p,
 			Unlight neighbors (in case the node is a light source)
 		*/
 		unLightNeighbors(bank, p,
-				getNode(p).getLight(bank, nodemgr),
+				getNode(p).getLight(bank, ndef),
 				light_sources, modified_blocks);
 	}
 
@@ -1219,7 +1241,7 @@ void Map::removeNodeAndUpdate(v3s16 p,
 		// TODO: Is this needed? Lighting is cleared up there already.
 		try{
 			MapNode n = getNode(p);
-			n.setLight(LIGHTBANK_DAY, 0, nodemgr);
+			n.setLight(LIGHTBANK_DAY, 0, ndef);
 			setNode(p, n);
 		}
 		catch(InvalidPositionException &e)
@@ -1255,6 +1277,17 @@ void Map::removeNodeAndUpdate(v3s16 p,
 	}
 
 	/*
+		Report for rollback
+	*/
+	if(m_gamedef->rollback())
+	{
+		RollbackNode rollback_newnode(this, p, m_gamedef);
+		RollbackAction action;
+		action.setSetNode(p, rollback_oldnode, rollback_newnode);
+		m_gamedef->rollback()->reportAction(action);
+	}
+
+	/*
 		Add neighboring liquid nodes and this node to transform queue.
 		(it's vital for the node itself to get updated last.)
 	*/
@@ -1275,7 +1308,7 @@ void Map::removeNodeAndUpdate(v3s16 p,
 		v3s16 p2 = p + dirs[i];
 
 		MapNode n2 = getNode(p2);
-		if(nodemgr->get(n2).isLiquid() || n2.getContent() == CONTENT_AIR)
+		if(ndef->get(n2).isLiquid() || n2.getContent() == CONTENT_AIR)
 		{
 			m_transforming_liquid.push_back(p2);
 		}
@@ -1588,6 +1621,11 @@ void Map::transformLiquids(core::map<v3s16, MapBlock*> & modified_blocks)
 	DSTACK(__FUNCTION_NAME);
 	//TimeTaker timer("transformLiquids()");
 
+	/*
+		If something goes wrong, liquids are to blame
+	*/
+	RollbackScopeActor rollback_scope(m_gamedef->rollback(), "liquid");
+
 	u32 loopcount = 0;
 	u32 initial_size = m_transforming_liquid.size();
 
@@ -1791,7 +1829,22 @@ void Map::transformLiquids(core::map<v3s16, MapBlock*> & modified_blocks)
 			n0.param2 = ~(LIQUID_LEVEL_MASK | LIQUID_FLOW_DOWN_MASK);
 		}
 		n0.setContent(new_node_content);
+
+		// Get old node for rollback
+		RollbackNode rollback_oldnode(this, p0, m_gamedef);
+
+		// Set node
 		setNode(p0, n0);
+		
+		// Report for rollback
+		if(m_gamedef->rollback())
+		{
+			RollbackNode rollback_newnode(this, p0, m_gamedef);
+			RollbackAction action;
+			action.setSetNode(p0, rollback_oldnode, rollback_newnode);
+			m_gamedef->rollback()->reportAction(action);
+		}
+
 		v3s16 blockpos = getNodeBlockPos(p0);
 		MapBlock *block = getBlockNoCreateNoEx(blockpos);
 		if(block != NULL) {
diff --git a/src/map.h b/src/map.h
index b561e5e72..30cf626bb 100644
--- a/src/map.h
+++ b/src/map.h
@@ -44,6 +44,7 @@ class ServerMapSector;
 class MapBlock;
 class NodeMetadata;
 class IGameDef;
+class IRollbackReportSink;
 
 namespace mapgen{
 	struct BlockMakeData;
@@ -169,7 +170,7 @@ public:
 	void removeEventReceiver(MapEventReceiver *event_receiver);
 	// event shall be deleted by caller after the call.
 	void dispatchEvent(MapEditEvent *event);
-
+	
 	// On failure returns NULL
 	MapSector * getSectorNoGenerateNoExNoLock(v2s16 p2d);
 	// Same as the above (there exists no lock anymore)
@@ -336,7 +337,7 @@ protected:
 	IGameDef *m_gamedef;
 
 	core::map<MapEventReceiver*, bool> m_event_receivers;
-	
+
 	core::map<v2s16, MapSector*> m_sectors;
 
 	// Be sure to set this to NULL when the cached sector is deleted 
diff --git a/src/rollback.cpp b/src/rollback.cpp
new file mode 100644
index 000000000..3fe791050
--- /dev/null
+++ b/src/rollback.cpp
@@ -0,0 +1,293 @@
+/*
+Minetest-c55
+Copyright (C) 2012 celeron55, Perttu Ahola <celeron55@gmail.com>
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 2.1 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public License along
+with this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+
+#include "rollback.h"
+#include <fstream>
+#include <list>
+#include <sstream>
+#include "log.h"
+#include "mapnode.h"
+#include "gamedef.h"
+#include "nodedef.h"
+#include "util/serialize.h"
+#include "util/string.h"
+#include "strfnd.h"
+#include "inventorymanager.h" // deserializing InventoryLocations
+
+#define PP(x) "("<<(x).X<<","<<(x).Y<<","<<(x).Z<<")"
+
+class RollbackManager: public IRollbackManager
+{
+public:
+	// IRollbackManager interface
+
+	void reportAction(const RollbackAction &action_)
+	{
+		// Ignore if not important
+		if(!action_.isImportant(m_gamedef))
+			return;
+		RollbackAction action = action_;
+		action.unix_time = time(0);
+		action.actor = m_current_actor;
+		infostream<<"RollbackManager::reportAction():"
+				<<" time="<<action.unix_time
+				<<" actor=\""<<action.actor<<"\""
+				<<" action="<<action.toString()
+				<<std::endl;
+		addAction(action);
+	}
+	std::string getActor()
+	{
+		return m_current_actor;
+	}
+	void setActor(const std::string &actor)
+	{
+		m_current_actor = actor;
+	}
+	void flush()
+	{
+		infostream<<"RollbackManager::flush()"<<std::endl;
+		std::ofstream of(m_filepath.c_str(), std::ios::app);
+		if(!of.good()){
+			errorstream<<"RollbackManager::flush(): Could not open file "
+					<<"for appending: \""<<m_filepath<<"\""<<std::endl;
+			return;
+		}
+		for(std::list<RollbackAction>::const_iterator
+				i = m_action_todisk_buffer.begin();
+				i != m_action_todisk_buffer.end(); i++)
+		{
+			// Do not save stuff that does not have an actor
+			if(i->actor == "")
+				continue;
+			of<<i->unix_time;
+			of<<" ";
+			of<<serializeJsonString(i->actor);
+			of<<" ";
+			std::string action_s = i->toString();
+			of<<action_s<<std::endl;
+		}
+		m_action_todisk_buffer.clear();
+	}
+	
+	// Other
+
+	RollbackManager(const std::string &filepath, IGameDef *gamedef):
+		m_filepath(filepath),
+		m_gamedef(gamedef)
+	{
+		infostream<<"RollbackManager::RollbackManager("<<filepath<<")"
+				<<std::endl;
+	}
+	~RollbackManager()
+	{
+		infostream<<"RollbackManager::~RollbackManager()"<<std::endl;
+		flush();
+	}
+
+	void addAction(const RollbackAction &action)
+	{
+		m_action_todisk_buffer.push_back(action);
+		m_action_latest_buffer.push_back(action);
+
+		// Flush to disk sometimes
+		if(m_action_todisk_buffer.size() >= 100)
+			flush();
+	}
+	
+	bool readFile(std::list<RollbackAction> &dst)
+	{
+		// Load whole file to memory
+		std::ifstream f(m_filepath.c_str(), std::ios::in);
+		if(!f.good()){
+			errorstream<<"RollbackManager::readFile(): Could not open "
+					<<"file for reading: \""<<m_filepath<<"\""<<std::endl;
+			return false;
+		}
+		for(;;){
+			if(f.eof() || !f.good())
+				break;
+			std::string line;
+			std::getline(f, line);
+			line = trim(line);
+			if(line == "")
+				continue;
+			std::istringstream is(line);
+			
+			try{
+				std::string action_time_raw;
+				std::getline(is, action_time_raw, ' ');
+				std::string action_actor;
+				try{
+					action_actor = deSerializeJsonString(is);
+				}catch(SerializationError &e){
+					errorstream<<"RollbackManager: Error deserializing actor: "
+							<<e.what()<<std::endl;
+					throw e;
+				}
+				RollbackAction action;
+				action.unix_time = stoi(action_time_raw);
+				action.actor = action_actor;
+				int c = is.get();
+				if(c != ' '){
+					is.putback(c);
+					throw SerializationError("readFile(): second ' ' not found");
+				}
+				action.fromStream(is);
+				/*infostream<<"RollbackManager::readFile(): Action from disk: "
+						<<action.toString()<<std::endl;*/
+				dst.push_back(action);
+			}
+			catch(SerializationError &e){
+				errorstream<<"RollbackManager: Error on line: "<<line<<std::endl;
+				errorstream<<"RollbackManager: ^ error: "<<e.what()<<std::endl;
+			}
+		}
+		return true;
+	}
+
+	std::list<RollbackAction> getEntriesSince(int first_time)
+	{
+		infostream<<"RollbackManager::getEntriesSince("<<first_time<<")"<<std::endl;
+		// Collect enough data to this buffer
+		std::list<RollbackAction> action_buffer;
+		// Use the latest buffer if it is long enough
+		if(!m_action_latest_buffer.empty() &&
+				m_action_latest_buffer.begin()->unix_time <= first_time){
+			action_buffer = m_action_latest_buffer;
+		}
+		else
+		{
+			// Save all remaining stuff
+			flush();
+			// Load whole file to memory
+			bool good = readFile(action_buffer);
+			if(!good){
+				errorstream<<"RollbackManager::getEntriesSince(): Failed to"
+						<<" open file; using data in memory."<<std::endl;
+				action_buffer = m_action_latest_buffer;
+			}
+		}
+		return action_buffer;
+	}
+	
+	std::string getLastNodeActor(v3s16 p, int range, int seconds,
+			v3s16 *act_p, int *act_seconds)
+	{
+		infostream<<"RollbackManager::getLastNodeActor("<<PP(p)
+				<<", "<<seconds<<")"<<std::endl;
+		// Figure out time
+		int cur_time = time(0);
+		int first_time = cur_time - seconds;
+
+		std::list<RollbackAction> action_buffer = getEntriesSince(first_time);
+		
+		std::list<RollbackAction> result;
+
+		for(std::list<RollbackAction>::const_reverse_iterator
+				i = action_buffer.rbegin();
+				i != action_buffer.rend(); i++)
+		{
+			if(i->unix_time < first_time)
+				break;
+
+			// Find position of action or continue
+			v3s16 action_p;
+
+			if(i->type == RollbackAction::TYPE_SET_NODE)
+			{
+				action_p = i->p;
+			}
+			else if(i->type == RollbackAction::TYPE_MODIFY_INVENTORY_STACK)
+			{
+				InventoryLocation loc;
+				loc.deSerialize(i->inventory_location);
+				if(loc.type != InventoryLocation::NODEMETA)
+					continue;
+				action_p = loc.p;
+			}
+			else
+				continue;
+
+			if(range == 0){
+				if(action_p != p)
+					continue;
+			} else {
+				if(abs(action_p.X - p.X) > range ||
+						abs(action_p.Y - p.Y) > range ||
+						abs(action_p.Z - p.Z) > range)
+					continue;
+			}
+			
+			if(act_p)
+				*act_p = action_p;
+			if(act_seconds)
+				*act_seconds = cur_time - i->unix_time;
+			return i->actor;
+		}
+		return "";
+	}
+
+	std::list<RollbackAction> getRevertActions(const std::string &actor_filter,
+			int seconds)
+	{
+		infostream<<"RollbackManager::getRevertActions("<<actor_filter
+				<<", "<<seconds<<")"<<std::endl;
+		// Figure out time
+		int cur_time = time(0);
+		int first_time = cur_time - seconds;
+		
+		std::list<RollbackAction> action_buffer = getEntriesSince(first_time);
+		
+		std::list<RollbackAction> result;
+
+		for(std::list<RollbackAction>::const_reverse_iterator
+				i = action_buffer.rbegin();
+				i != action_buffer.rend(); i++)
+		{
+			if(i->unix_time < first_time)
+				break;
+			if(i->actor != actor_filter)
+				continue;
+			const RollbackAction &action = *i;
+			/*infostream<<"RollbackManager::revertAction(): Should revert"
+					<<" time="<<action.unix_time
+					<<" actor=\""<<action.actor<<"\""
+					<<" action="<<action.toString()
+					<<std::endl;*/
+			result.push_back(action);
+		}
+
+		return result;
+	}
+
+private:
+	std::string m_filepath;
+	IGameDef *m_gamedef;
+	std::string m_current_actor;
+	std::list<RollbackAction> m_action_todisk_buffer;
+	std::list<RollbackAction> m_action_latest_buffer;
+};
+
+IRollbackManager *createRollbackManager(const std::string &filepath, IGameDef *gamedef)
+{
+	return new RollbackManager(filepath, gamedef);
+}
+
+
diff --git a/src/rollback.h b/src/rollback.h
new file mode 100644
index 000000000..b5428c451
--- /dev/null
+++ b/src/rollback.h
@@ -0,0 +1,51 @@
+/*
+Minetest-c55
+Copyright (C) 2012 celeron55, Perttu Ahola <celeron55@gmail.com>
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 2.1 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public License along
+with this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+
+#ifndef ROLLBACK_HEADER
+#define ROLLBACK_HEADER
+
+#include <string>
+#include "irr_v3d.h"
+#include "rollback_interface.h"
+#include <list>
+
+class IGameDef;
+
+class IRollbackManager: public IRollbackReportSink
+{
+public:
+	// IRollbackReportManager
+	virtual void reportAction(const RollbackAction &action) = 0;
+	virtual std::string getActor() = 0;
+	virtual void setActor(const std::string &actor) = 0;
+
+	virtual ~IRollbackManager(){}
+	virtual void flush() = 0;
+	// Get last actor that did something to position p, but not further than
+	// <seconds> in history
+	virtual std::string getLastNodeActor(v3s16 p, int range, int seconds,
+			v3s16 *act_p, int *act_seconds) = 0;
+	// Get actions to revert <seconds> of history made by <actor>
+	virtual std::list<RollbackAction> getRevertActions(const std::string &actor,
+			int seconds) = 0;
+};
+
+IRollbackManager *createRollbackManager(const std::string &filepath, IGameDef *gamedef);
+
+#endif
diff --git a/src/rollback_interface.cpp b/src/rollback_interface.cpp
new file mode 100644
index 000000000..e15fe3da3
--- /dev/null
+++ b/src/rollback_interface.cpp
@@ -0,0 +1,398 @@
+/*
+Minetest-c55
+Copyright (C) 2012 celeron55, Perttu Ahola <celeron55@gmail.com>
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 2.1 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public License along
+with this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+
+#include "rollback_interface.h"
+#include <sstream>
+#include "util/serialize.h"
+#include "util/string.h"
+#include "util/numeric.h"
+#include "map.h"
+#include "gamedef.h"
+#include "nodedef.h"
+#include "nodemetadata.h"
+#include "exceptions.h"
+#include "log.h"
+#include "inventorymanager.h"
+#include "inventory.h"
+#include "mapblock.h"
+
+#define PP(x) "("<<(x).X<<","<<(x).Y<<","<<(x).Z<<")"
+
+RollbackNode::RollbackNode(Map *map, v3s16 p, IGameDef *gamedef)
+{
+	INodeDefManager *ndef = gamedef->ndef();
+	MapNode n = map->getNodeNoEx(p);
+	name = ndef->get(n).name;
+	param1 = n.param1;
+	param2 = n.param2;
+	NodeMetadata *metap = map->getNodeMetadata(p);
+	if(metap){
+		std::ostringstream os(std::ios::binary);
+		metap->serialize(os);
+		meta = os.str();
+	}
+}
+
+std::string RollbackAction::toString() const
+{
+	switch(type){
+	case TYPE_SET_NODE: {
+		std::ostringstream os(std::ios::binary);
+		os<<"[set_node";
+		os<<" ";
+		os<<"("<<itos(p.X)<<","<<itos(p.Y)<<","<<itos(p.Z)<<")";
+		os<<" ";
+		os<<serializeJsonString(n_old.name);
+		os<<" ";
+		os<<itos(n_old.param1);
+		os<<" ";
+		os<<itos(n_old.param2);
+		os<<" ";
+		os<<serializeJsonString(n_old.meta);
+		os<<" ";
+		os<<serializeJsonString(n_new.name);
+		os<<" ";
+		os<<itos(n_new.param1);
+		os<<" ";
+		os<<itos(n_new.param2);
+		os<<" ";
+		os<<serializeJsonString(n_new.meta);
+		os<<"]";
+		return os.str(); }
+	case TYPE_MODIFY_INVENTORY_STACK: {
+		std::ostringstream os(std::ios::binary);
+		os<<"[modify_inventory_stack";
+		os<<" ";
+		os<<serializeJsonString(inventory_location);
+		os<<" ";
+		os<<serializeJsonString(inventory_list);
+		os<<" ";
+		os<<inventory_index;
+		os<<" ";
+		os<<(inventory_add?"add":"remove");
+		os<<" ";
+		os<<serializeJsonString(inventory_stack);
+		os<<"]";
+		return os.str(); }
+	default:
+		return "none";
+	}
+}
+
+void RollbackAction::fromStream(std::istream &is) throw(SerializationError)
+{
+	int c = is.get();
+	if(c != '['){
+		is.putback(c);
+		throw SerializationError("RollbackAction: starting [ not found");
+	}
+	
+	std::string id;
+	std::getline(is, id, ' ');
+	
+	if(id == "set_node")
+	{
+		c = is.get();
+		if(c != '('){
+			is.putback(c);
+			throw SerializationError("RollbackAction: starting ( not found");
+		}
+		// Position
+		std::string px_raw;
+		std::string py_raw;
+		std::string pz_raw;
+		std::getline(is, px_raw, ',');
+		std::getline(is, py_raw, ',');
+		std::getline(is, pz_raw, ')');
+		c = is.get();
+		if(c != ' '){
+			is.putback(c);
+			throw SerializationError("RollbackAction: after-p ' ' not found");
+		}
+		v3s16 loaded_p(stoi(px_raw), stoi(py_raw), stoi(pz_raw));
+		// Old node
+		std::string old_name;
+		try{
+			old_name = deSerializeJsonString(is);
+		}catch(SerializationError &e){
+			errorstream<<"Serialization error in RollbackAction::fromStream(): "
+					<<"old_name: "<<e.what()<<std::endl;
+			throw e;
+		}
+		c = is.get();
+		if(c != ' '){
+			is.putback(c);
+			throw SerializationError("RollbackAction: after-old_name ' ' not found");
+		}
+		std::string old_p1_raw;
+		std::string old_p2_raw;
+		std::getline(is, old_p1_raw, ' ');
+		std::getline(is, old_p2_raw, ' ');
+		int old_p1 = stoi(old_p1_raw);
+		int old_p2 = stoi(old_p2_raw);
+		std::string old_meta;
+		try{
+			old_meta = deSerializeJsonString(is);
+		}catch(SerializationError &e){
+			errorstream<<"Serialization error in RollbackAction::fromStream(): "
+					<<"old_meta: "<<e.what()<<std::endl;
+			throw e;
+		}
+		c = is.get();
+		if(c != ' '){
+			is.putback(c);
+			throw SerializationError("RollbackAction: after-old_meta ' ' not found");
+		}
+		// New node
+		std::string new_name;
+		try{
+			new_name = deSerializeJsonString(is);
+		}catch(SerializationError &e){
+			errorstream<<"Serialization error in RollbackAction::fromStream(): "
+					<<"new_name: "<<e.what()<<std::endl;
+			throw e;
+		}
+		c = is.get();
+		if(c != ' '){
+			is.putback(c);
+			throw SerializationError("RollbackAction: after-new_name ' ' not found");
+		}
+		std::string new_p1_raw;
+		std::string new_p2_raw;
+		std::getline(is, new_p1_raw, ' ');
+		std::getline(is, new_p2_raw, ' ');
+		int new_p1 = stoi(new_p1_raw);
+		int new_p2 = stoi(new_p2_raw);
+		std::string new_meta;
+		try{
+			new_meta = deSerializeJsonString(is);
+		}catch(SerializationError &e){
+			errorstream<<"Serialization error in RollbackAction::fromStream(): "
+					<<"new_meta: "<<e.what()<<std::endl;
+			throw e;
+		}
+		c = is.get();
+		if(c != ']'){
+			is.putback(c);
+			throw SerializationError("RollbackAction: after-new_meta ] not found");
+		}
+		// Set values
+		type = TYPE_SET_NODE;
+		p = loaded_p;
+		n_old.name = old_name;
+		n_old.param1 = old_p1;
+		n_old.param2 = old_p2;
+		n_old.meta = old_meta;
+		n_new.name = new_name;
+		n_new.param1 = new_p1;
+		n_new.param2 = new_p2;
+		n_new.meta = new_meta;
+	}
+	else if(id == "modify_inventory_stack")
+	{
+		// Location
+		std::string location;
+		try{
+			location = deSerializeJsonString(is);
+		}catch(SerializationError &e){
+			errorstream<<"Serialization error in RollbackAction::fromStream(): "
+					<<"location: "<<e.what()<<std::endl;
+			throw e;
+		}
+		c = is.get();
+		if(c != ' '){
+			is.putback(c);
+			throw SerializationError("RollbackAction: after-loc ' ' not found");
+		}
+		// List
+		std::string listname;
+		try{
+			listname = deSerializeJsonString(is);
+		}catch(SerializationError &e){
+			errorstream<<"Serialization error in RollbackAction::fromStream(): "
+					<<"listname: "<<e.what()<<std::endl;
+			throw e;
+		}
+		c = is.get();
+		if(c != ' '){
+			is.putback(c);
+			throw SerializationError("RollbackAction: after-list ' ' not found");
+		}
+		// Index
+		std::string index_raw;
+		std::getline(is, index_raw, ' ');
+		// add/remove
+		std::string addremove;
+		std::getline(is, addremove, ' ');
+		if(addremove != "add" && addremove != "remove"){
+			throw SerializationError("RollbackAction: addremove is not add or remove");
+		}
+		// Itemstring
+		std::string stack;
+		try{
+			stack = deSerializeJsonString(is);
+		}catch(SerializationError &e){
+			errorstream<<"Serialization error in RollbackAction::fromStream(): "
+					<<"stack: "<<e.what()<<std::endl;
+			throw e;
+		}
+		// Set values
+		type = TYPE_MODIFY_INVENTORY_STACK;
+		inventory_location = location;
+		inventory_list = listname;
+		inventory_index = stoi(index_raw);
+		inventory_add = (addremove == "add");
+		inventory_stack = stack;
+	}
+	else
+	{
+		throw SerializationError("RollbackAction: Unknown id");
+	}
+}
+
+bool RollbackAction::isImportant(IGameDef *gamedef) const
+{
+	switch(type){
+	case TYPE_SET_NODE: {
+		// If names differ, action is always important
+		if(n_old.name != n_new.name)
+			return true;
+		// If metadata differs, action is always important
+		if(n_old.meta != n_new.meta)
+			return true;
+		INodeDefManager *ndef = gamedef->ndef();
+		// Both are of the same name, so a single definition is needed
+		const ContentFeatures &def = ndef->get(n_old.name);
+		// If the type is flowing liquid, action is not important
+		if(def.liquid_type == LIQUID_FLOWING)
+			return false;
+		// Otherwise action is important
+		return true; }
+	default:
+		return true;
+	}
+}
+
+bool RollbackAction::applyRevert(Map *map, InventoryManager *imgr, IGameDef *gamedef) const
+{
+	try{
+		switch(type){
+		case TYPE_NOTHING:
+			return true;
+		case TYPE_SET_NODE: {
+			INodeDefManager *ndef = gamedef->ndef();
+			// Make sure position is loaded from disk
+			map->emergeBlock(getContainerPos(p, MAP_BLOCKSIZE), false);
+			// Check current node
+			MapNode current_node = map->getNodeNoEx(p);
+			std::string current_name = ndef->get(current_node).name;
+			// If current node not the new node, it's bad
+			if(current_name != n_new.name)
+				return false;
+			/*// If current node not the new node and not ignore, it's bad
+			if(current_name != n_new.name && current_name != "ignore")
+				return false;*/
+			// Create rollback node
+			MapNode n(ndef, n_old.name, n_old.param1, n_old.param2);
+			// Set rollback node
+			try{
+				if(!map->addNodeWithEvent(p, n)){
+					infostream<<"RollbackAction::applyRevert(): "
+							<<"AddNodeWithEvent failed at "
+							<<PP(p)<<" for "<<n_old.name<<std::endl;
+					return false;
+				}
+				NodeMetadata *meta = map->getNodeMetadata(p);
+				if(n_old.meta != ""){
+					if(!meta){
+						meta = new NodeMetadata(gamedef);
+						map->setNodeMetadata(p, meta);
+					}
+					std::istringstream is(n_old.meta, std::ios::binary);
+					meta->deSerialize(is);
+				} else {
+					map->removeNodeMetadata(p);
+				}
+				// NOTE: This same code is in scriptapi.cpp
+				// Inform other things that the metadata has changed
+				v3s16 blockpos = getContainerPos(p, MAP_BLOCKSIZE);
+				MapEditEvent event;
+				event.type = MEET_BLOCK_NODE_METADATA_CHANGED;
+				event.p = blockpos;
+				map->dispatchEvent(&event);
+				// Set the block to be saved
+				MapBlock *block = map->getBlockNoCreateNoEx(blockpos);
+				if(block)
+					block->raiseModified(MOD_STATE_WRITE_NEEDED,
+							"NodeMetaRef::reportMetadataChange");
+			}catch(InvalidPositionException &e){
+				infostream<<"RollbackAction::applyRevert(): "
+						<<"InvalidPositionException: "<<e.what()<<std::endl;
+				return false;
+			}
+			// Success
+			return true; }
+		case TYPE_MODIFY_INVENTORY_STACK: {
+			InventoryLocation loc;
+			loc.deSerialize(inventory_location);
+			ItemStack stack;
+			stack.deSerialize(inventory_stack, gamedef->idef());
+			Inventory *inv = imgr->getInventory(loc);
+			if(!inv){
+				infostream<<"RollbackAction::applyRevert(): Could not get "
+						"inventory at "<<inventory_location<<std::endl;
+				return false;
+			}
+			InventoryList *list = inv->getList(inventory_list);
+			if(!list){
+				infostream<<"RollbackAction::applyRevert(): Could not get "
+						"inventory list \""<<inventory_list<<"\" in "
+						<<inventory_location<<std::endl;
+				return false;
+			}
+			if(list->getSize() <= inventory_index){
+				infostream<<"RollbackAction::applyRevert(): List index "
+						<<inventory_index<<" too large in "
+						<<"inventory list \""<<inventory_list<<"\" in "
+						<<inventory_location<<std::endl;
+			}
+			// If item was added, take away item, otherwise add removed item
+			if(inventory_add){
+				// Silently ignore different current item
+				if(list->getItem(inventory_index).name != stack.name)
+					return false;
+				list->takeItem(inventory_index, stack.count);
+			} else {
+				list->addItem(inventory_index, stack);
+			}
+			// Inventory was modified; send to clients
+			imgr->setInventoryModified(loc);
+			return true; }
+		default:
+			errorstream<<"RollbackAction::applyRevert(): type not handled"
+					<<std::endl;
+			return false;
+		}
+	}catch(SerializationError &e){
+		errorstream<<"RollbackAction::applyRevert(): n_old.name="<<n_old.name
+				<<", SerializationError: "<<e.what()<<std::endl;
+	}
+	return false;
+}
+
diff --git a/src/rollback_interface.h b/src/rollback_interface.h
new file mode 100644
index 000000000..0f0a11885
--- /dev/null
+++ b/src/rollback_interface.h
@@ -0,0 +1,145 @@
+/*
+Minetest-c55
+Copyright (C) 2012 celeron55, Perttu Ahola <celeron55@gmail.com>
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU Lesser General Public License as published by
+the Free Software Foundation; either version 2.1 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public License along
+with this program; if not, write to the Free Software Foundation, Inc.,
+51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+*/
+
+#ifndef ROLLBACK_INTERFACE_HEADER
+#define ROLLBACK_INTERFACE_HEADER
+
+#include "irr_v3d.h"
+#include <string>
+#include <iostream>
+#include "exceptions.h"
+
+class Map;
+class IGameDef;
+struct MapNode;
+class InventoryManager;
+
+struct RollbackNode
+{
+	std::string name;
+	int param1;
+	int param2;
+	std::string meta;
+
+	bool operator==(const RollbackNode &other)
+	{
+		return (name == other.name && param1 == other.param1 &&
+				param2 == other.param2 && meta == other.meta);
+	}
+	bool operator!=(const RollbackNode &other)
+	{
+		return !(*this == other);
+	}
+
+	RollbackNode():
+		param1(0),
+		param2(0)
+	{}
+
+	RollbackNode(Map *map, v3s16 p, IGameDef *gamedef);
+};
+
+struct RollbackAction
+{
+	enum Type{
+		TYPE_NOTHING,
+		TYPE_SET_NODE,
+		TYPE_MODIFY_INVENTORY_STACK,
+	} type;
+
+	int unix_time;
+	std::string actor;
+
+	v3s16 p;
+	RollbackNode n_old;
+	RollbackNode n_new;
+	
+	std::string inventory_location;
+	std::string inventory_list;
+	u32 inventory_index;
+	bool inventory_add;
+	std::string inventory_stack;
+
+	RollbackAction():
+		type(TYPE_NOTHING)
+	{}
+
+	void setSetNode(v3s16 p_, const RollbackNode &n_old_,
+			const RollbackNode &n_new_)
+	{
+		type = TYPE_SET_NODE;
+		p = p_;
+		n_old = n_old_;
+		n_new = n_new_;
+	}
+
+	void setModifyInventoryStack(const std::string &inventory_location_,
+			const std::string &inventory_list_, int index_,
+			bool add_, const std::string &inventory_stack_)
+	{
+		type = TYPE_MODIFY_INVENTORY_STACK;
+		inventory_location = inventory_location_;
+		inventory_list = inventory_list_;
+		inventory_index = index_;
+		inventory_add = add_;
+		inventory_stack = inventory_stack_;
+	}
+	
+	// String should not contain newlines or nulls
+	std::string toString() const;
+	void fromStream(std::istream &is) throw(SerializationError);
+	
+	// Eg. flowing water level changes are not important
+	bool isImportant(IGameDef *gamedef) const;
+
+	bool applyRevert(Map *map, InventoryManager *imgr, IGameDef *gamedef) const;
+};
+
+class IRollbackReportSink
+{
+public:
+	virtual ~IRollbackReportSink(){}
+	virtual void reportAction(const RollbackAction &action) = 0;
+	virtual std::string getActor() = 0;
+	virtual void setActor(const std::string &actor) = 0;
+};
+
+class RollbackScopeActor
+{
+public:
+	RollbackScopeActor(IRollbackReportSink *sink, const std::string &actor):
+		m_sink(sink)
+	{
+		if(m_sink){
+			m_actor_was = m_sink->getActor();
+			m_sink->setActor(actor);
+		}
+	}
+	~RollbackScopeActor()
+	{
+		if(m_sink){
+			m_sink->setActor(m_actor_was);
+		}
+	}
+private:
+	IRollbackReportSink *m_sink;
+	std::string m_actor_was;
+};
+
+#endif
diff --git a/src/scriptapi.cpp b/src/scriptapi.cpp
index e1d918542..61488abb4 100644
--- a/src/scriptapi.cpp
+++ b/src/scriptapi.cpp
@@ -47,6 +47,7 @@ extern "C" {
 #include "daynightratio.h"
 #include "noise.h" // PseudoRandom for LuaPseudoRandom
 #include "util/pointedthing.h"
+#include "rollback.h"
 
 static void stackDump(lua_State *L, std::ostream &o)
 {
@@ -2106,6 +2107,7 @@ private:
 
 	static void reportMetadataChange(NodeMetaRef *ref)
 	{
+		// NOTE: This same code is in rollback_interface.cpp
 		// Inform other things that the metadata has changed
 		v3s16 blockpos = getNodeBlockPos(ref->m_p);
 		MapEditEvent event;
@@ -4853,6 +4855,55 @@ static int l_get_craft_recipe(lua_State *L)
 	return 1;
 }
 
+// rollback_get_last_node_actor(p, range, seconds) -> actor, p, seconds
+static int l_rollback_get_last_node_actor(lua_State *L)
+{
+	v3s16 p = read_v3s16(L, 1);
+	int range = luaL_checknumber(L, 2);
+	int seconds = luaL_checknumber(L, 3);
+	Server *server = get_server(L);
+	IRollbackManager *rollback = server->getRollbackManager();
+	v3s16 act_p;
+	int act_seconds = 0;
+	std::string actor = rollback->getLastNodeActor(p, range, seconds, &act_p, &act_seconds);
+	lua_pushstring(L, actor.c_str());
+	push_v3s16(L, act_p);
+	lua_pushnumber(L, act_seconds);
+	return 3;
+}
+
+// rollback_revert_actions_by(actor, seconds) -> bool, log messages
+static int l_rollback_revert_actions_by(lua_State *L)
+{
+	std::string actor = luaL_checkstring(L, 1);
+	int seconds = luaL_checknumber(L, 2);
+	Server *server = get_server(L);
+	IRollbackManager *rollback = server->getRollbackManager();
+	std::list<RollbackAction> actions = rollback->getRevertActions(actor, seconds);
+	std::list<std::string> log;
+	bool success = server->rollbackRevertActions(actions, &log);
+	// Push boolean result
+	lua_pushboolean(L, success);
+	// Get the table insert function and push the log table
+	lua_getglobal(L, "table");
+	lua_getfield(L, -1, "insert");
+	int table_insert = lua_gettop(L);
+	lua_newtable(L);
+	int table = lua_gettop(L);
+	for(std::list<std::string>::const_iterator i = log.begin();
+			i != log.end(); i++)
+	{
+		lua_pushvalue(L, table_insert);
+		lua_pushvalue(L, table);
+		lua_pushstring(L, i->c_str());
+		if(lua_pcall(L, 2, 0, 0))
+			script_error(L, "error: %s", lua_tostring(L, -1));
+	}
+	lua_remove(L, -2); // Remove table
+	lua_remove(L, -2); // Remove insert
+	return 2;
+}
+
 static const struct luaL_Reg minetest_f [] = {
 	{"debug", l_debug},
 	{"log", l_log},
@@ -4880,6 +4931,8 @@ static const struct luaL_Reg minetest_f [] = {
 	{"notify_authentication_modified", l_notify_authentication_modified},
 	{"get_craft_result", l_get_craft_result},
 	{"get_craft_recipe", l_get_craft_recipe},
+	{"rollback_get_last_node_actor", l_rollback_get_last_node_actor},
+	{"rollback_revert_actions_by", l_rollback_revert_actions_by},
 	{NULL, NULL}
 };
 
diff --git a/src/server.cpp b/src/server.cpp
index 21c936e69..a868a0425 100644
--- a/src/server.cpp
+++ b/src/server.cpp
@@ -54,6 +54,7 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "util/string.h"
 #include "util/pointedthing.h"
 #include "util/mathconstants.h"
+#include "rollback.h"
 
 #define PP(x) "("<<(x).X<<","<<(x).Y<<","<<(x).Z<<")"
 
@@ -934,6 +935,8 @@ Server::Server(
 	m_env(NULL),
 	m_con(PROTOCOL_ID, 512, CONNECTION_TIMEOUT, this),
 	m_banmanager(path_world+DIR_DELIM+"ipban.txt"),
+	m_rollback(NULL),
+	m_rollback_sink_enabled(true),
 	m_lua(NULL),
 	m_itemdef(createItemDefManager()),
 	m_nodedef(createNodeDefManager()),
@@ -973,6 +976,10 @@ Server::Server(
 	infostream<<"- config: "<<m_path_config<<std::endl;
 	infostream<<"- game:   "<<m_gamespec.path<<std::endl;
 
+	// Create rollback manager
+	std::string rollback_path = m_path_world+DIR_DELIM+"rollback.txt";
+	m_rollback = createRollbackManager(rollback_path, this);
+
 	// Add world mod search path
 	m_modspaths.push_front(m_path_world + DIR_DELIM + "worldmods");
 	// Add addon mod search path
@@ -1049,7 +1056,7 @@ Server::Server(
 	
 	m_env = new ServerEnvironment(new ServerMap(path_world, this), m_lua,
 			this, this);
-
+	
 	// Give environment reference to scripting api
 	scriptapi_add_environment(m_lua, m_env);
 	
@@ -1152,6 +1159,7 @@ Server::~Server()
 	
 	// Delete things in the reverse order of creation
 	delete m_env;
+	delete m_rollback;
 	delete m_event;
 	delete m_itemdef;
 	delete m_nodedef;
@@ -2481,6 +2489,10 @@ void Server::ProcessData(u8 *data, u32 datasize, u16 peer_id)
 			return;
 		}
 
+		// If something goes wrong, this player is to blame
+		RollbackScopeActor rollback_scope(m_rollback,
+				std::string("player:")+player->getName());
+
 		/*
 			Note: Always set inventory not sent, to repair cases
 			where the client made a bad prediction.
@@ -2950,6 +2962,12 @@ void Server::ProcessData(u8 *data, u32 datasize, u16 peer_id)
 		}
 
 		/*
+			If something goes wrong, this player is to blame
+		*/
+		RollbackScopeActor rollback_scope(m_rollback,
+				std::string("player:")+player->getName());
+
+		/*
 			0: start digging or punch object
 		*/
 		if(action == 0)
@@ -3204,8 +3222,23 @@ void Server::ProcessData(u8 *data, u32 datasize, u16 peer_id)
 			fields[fieldname] = fieldvalue;
 		}
 
+		// If something goes wrong, this player is to blame
+		RollbackScopeActor rollback_scope(m_rollback,
+				std::string("player:")+player->getName());
+
+		// Check the target node for rollback data; leave others unnoticed
+		RollbackNode rn_old(&m_env->getMap(), p, this);
+
 		scriptapi_node_on_receive_fields(m_lua, p, formname, fields,
 				playersao);
+
+		// Report rollback data
+		RollbackNode rn_new(&m_env->getMap(), p, this);
+		if(rollback() && rn_new != rn_old){
+			RollbackAction action;
+			action.setSetNode(p, rn_old, rn_new);
+			rollback()->reportAction(action);
+		}
 	}
 	else if(command == TOSERVER_INVENTORY_FIELDS)
 	{
@@ -4522,6 +4555,73 @@ Inventory* Server::createDetachedInventory(const std::string &name)
 	return inv;
 }
 
+class BoolScopeSet
+{
+public:
+	BoolScopeSet(bool *dst, bool val):
+		m_dst(dst)
+	{
+		m_orig_state = *m_dst;
+		*m_dst = val;
+	}
+	~BoolScopeSet()
+	{
+		*m_dst = m_orig_state;
+	}
+private:
+	bool *m_dst;
+	bool m_orig_state;
+};
+
+// actions: time-reversed list
+// Return value: success/failure
+bool Server::rollbackRevertActions(const std::list<RollbackAction> &actions,
+		std::list<std::string> *log)
+{
+	infostream<<"Server::rollbackRevertActions(len="<<actions.size()<<")"<<std::endl;
+	ServerMap *map = (ServerMap*)(&m_env->getMap());
+	// Disable rollback report sink while reverting
+	BoolScopeSet rollback_scope_disable(&m_rollback_sink_enabled, false);
+	
+	// Fail if no actions to handle
+	if(actions.empty()){
+		log->push_back("Nothing to do.");
+		return false;
+	}
+
+	int num_tried = 0;
+	int num_failed = 0;
+	
+	for(std::list<RollbackAction>::const_iterator
+			i = actions.begin();
+			i != actions.end(); i++)
+	{
+		const RollbackAction &action = *i;
+		num_tried++;
+		bool success = action.applyRevert(map, this, this);
+		if(!success){
+			num_failed++;
+			std::ostringstream os;
+			os<<"Revert of step ("<<num_tried<<") "<<action.toString()<<" failed";
+			infostream<<"Map::rollbackRevertActions(): "<<os.str()<<std::endl;
+			if(log)
+				log->push_back(os.str());
+		}else{
+			std::ostringstream os;
+			os<<"Succesfully reverted step ("<<num_tried<<") "<<action.toString();
+			infostream<<"Map::rollbackRevertActions(): "<<os.str()<<std::endl;
+			if(log)
+				log->push_back(os.str());
+		}
+	}
+	
+	infostream<<"Map::rollbackRevertActions(): "<<num_failed<<"/"<<num_tried
+			<<" failed"<<std::endl;
+
+	// Call it done if less than half failed
+	return num_failed <= num_tried/2;
+}
+
 // IGameDef interface
 // Under envlock
 IItemDefManager* Server::getItemDefManager()
@@ -4552,6 +4652,12 @@ MtEventManager* Server::getEventManager()
 {
 	return m_event;
 }
+IRollbackReportSink* Server::getRollbackReportSink()
+{
+	if(!m_rollback_sink_enabled)
+		return NULL;
+	return m_rollback;
+}
 
 IWritableItemDefManager* Server::getWritableItemDefManager()
 {
diff --git a/src/server.h b/src/server.h
index 4316bc21f..668d42416 100644
--- a/src/server.h
+++ b/src/server.h
@@ -36,6 +36,8 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "sound.h"
 #include "util/thread.h"
 #include "util/string.h"
+#include "rollback_interface.h" // Needed for rollbackRevertActions()
+#include <list> // Needed for rollbackRevertActions()
 
 struct LuaState;
 typedef struct lua_State lua_State;
@@ -44,6 +46,7 @@ class IWritableNodeDefManager;
 class IWritableCraftDefManager;
 class EventManager;
 class PlayerSAO;
+class IRollbackManager;
 
 class ServerError : public std::exception
 {
@@ -543,6 +546,13 @@ public:
 	
 	// Envlock and conlock should be locked when using Lua
 	lua_State *getLua(){ return m_lua; }
+
+	// Envlock should be locked when using the rollback manager
+	IRollbackManager *getRollbackManager(){ return m_rollback; }
+	// actions: time-reversed list
+	// Return value: success/failure
+	bool rollbackRevertActions(const std::list<RollbackAction> &actions,
+			std::list<std::string> *log);
 	
 	// IGameDef interface
 	// Under envlock
@@ -553,6 +563,7 @@ public:
 	virtual u16 allocateUnknownNodeId(const std::string &name);
 	virtual ISoundManager* getSoundManager();
 	virtual MtEventManager* getEventManager();
+	virtual IRollbackReportSink* getRollbackReportSink();
 	
 	IWritableItemDefManager* getWritableItemDefManager();
 	IWritableNodeDefManager* getWritableNodeDefManager();
@@ -720,6 +731,10 @@ private:
 	// Bann checking
 	BanManager m_banmanager;
 
+	// Rollback manager (behind m_env_mutex)
+	IRollbackManager *m_rollback;
+	bool m_rollback_sink_enabled;
+
 	// Scripting
 	// Envlock and conlock should be locked when using Lua
 	lua_State *m_lua;