Make the rollback system VERY FUCKING GOD DAMN POWERFUL

5 files changed, 139 insertions, 40 deletions

diff --git a/src/map.cpp b/src/map.cpp
index 853693049..8aa73efbe 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -1621,12 +1621,6 @@ void Map::transformLiquids(core::map<v3s16, MapBlock*> & modified_blocks)
 	DSTACK(__FUNCTION_NAME);
 	//TimeTaker timer("transformLiquids()");
 
-	/*
-		If something goes wrong, liquids are to blame
-		NOTE: Do not track liquids; it causes huge amounts of rollback log
-	*/
-	//RollbackScopeActor rollback_scope(m_gamedef->rollback(), "liquid");
-
 	u32 loopcount = 0;
 	u32 initial_size = m_transforming_liquid.size();
 
@@ -1830,21 +1824,30 @@ 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())
-		{
+		// Find out whether there is a suspect for this action
+		std::string suspect;
+		if(m_gamedef->rollback()){
+			// Max. 5 seconds ago
+			suspect = m_gamedef->rollback()->getSuspect(p0, 5);
+		}
+
+		if(!suspect.empty()){
+			// Blame suspect
+			RollbackScopeActor rollback_scope(m_gamedef->rollback(), suspect, true);
+			// Get old node for rollback
+			RollbackNode rollback_oldnode(this, p0, m_gamedef);
+			// Set node
+			setNode(p0, n0);
+			// Report
 			RollbackNode rollback_newnode(this, p0, m_gamedef);
 			RollbackAction action;
 			action.setSetNode(p0, rollback_oldnode, rollback_newnode);
 			m_gamedef->rollback()->reportAction(action);
-		}*/
+		} else {
+			// Set node
+			setNode(p0, n0);
+		}
 
 		v3s16 blockpos = getNodeBlockPos(p0);
 		MapBlock *block = getBlockNoCreateNoEx(blockpos);
diff --git a/src/rollback.cpp b/src/rollback.cpp
index 3fe791050..db3f01702 100644
--- a/src/rollback.cpp
+++ b/src/rollback.cpp
@@ -28,10 +28,34 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "util/serialize.h"
 #include "util/string.h"
 #include "strfnd.h"
+#include "util/numeric.h"
 #include "inventorymanager.h" // deserializing InventoryLocations
 
 #define PP(x) "("<<(x).X<<","<<(x).Y<<","<<(x).Z<<")"
 
+// Get nearness factor for subject's action for this action
+// Return value: 0 = impossible, >0 = factor
+static float getSuspectNearness(bool is_guess, v3s16 suspect_p, int suspect_t,
+		v3s16 action_p, int action_t)
+{
+	// Suspect cannot cause things in the past
+	if(action_t < suspect_t)
+		return 0; // 0 = cannot be
+	// Start from 100
+	int f = 100;
+	// Distance (1 node = +1 point)
+	f += 1.0 * intToFloat(suspect_p, 1).getDistanceFrom(intToFloat(action_p, 1));
+	// Time (1 second = -1 point)
+	f -= 1.0 * (action_t - suspect_t);
+	// If is a guess, halve the points
+	if(is_guess)
+		f *= 0.5;
+	// Limit to 0
+	if(f < 0)
+		f = 0;
+	return f;
+}
+
 class RollbackManager: public IRollbackManager
 {
 public:
@@ -44,10 +68,23 @@ public:
 			return;
 		RollbackAction action = action_;
 		action.unix_time = time(0);
+		// Figure out actor
 		action.actor = m_current_actor;
+		action.actor_is_guess = m_current_actor_is_guess;
+		// If actor is not known, find out suspect or cancel
+		if(action.actor.empty()){
+			v3s16 p;
+			if(!action.getPosition(&p))
+				return;
+			action.actor = getSuspect(p, 5); // 5s timeframe
+			if(action.actor.empty())
+				return;
+			action.actor_is_guess = true;
+		}
 		infostream<<"RollbackManager::reportAction():"
 				<<" time="<<action.unix_time
 				<<" actor=\""<<action.actor<<"\""
+				<<(action.actor_is_guess?" (guess)":"")
 				<<" action="<<action.toString()
 				<<std::endl;
 		addAction(action);
@@ -56,9 +93,45 @@ public:
 	{
 		return m_current_actor;
 	}
-	void setActor(const std::string &actor)
+	bool isActorGuess()
+	{
+		return m_current_actor_is_guess;
+	}
+	void setActor(const std::string &actor, bool is_guess)
 	{
 		m_current_actor = actor;
+		m_current_actor_is_guess = is_guess;
+	}
+	std::string getSuspect(v3s16 p, int max_time)
+	{
+		if(m_current_actor != "")
+			return m_current_actor;
+		int cur_time = time(0);
+		int first_time = cur_time - max_time;
+		RollbackAction likely_suspect;
+		float likely_suspect_nearness = 0;
+		for(std::list<RollbackAction>::const_reverse_iterator
+				i = m_action_latest_buffer.rbegin();
+				i != m_action_latest_buffer.rend(); i++)
+		{
+			if(i->unix_time < first_time)
+				break;
+			// Find position of suspect or continue
+			v3s16 suspect_p;
+			if(!i->getPosition(&suspect_p))
+				continue;
+			float f = getSuspectNearness(i->actor_is_guess, suspect_p,
+					i->unix_time, p, cur_time);
+			if(f > likely_suspect_nearness){
+				likely_suspect_nearness = f;
+				likely_suspect = *i;
+			}
+		}
+		// No likely suspect was found
+		if(likely_suspect_nearness == 0)
+			return "";
+		// Likely suspect was found
+		return likely_suspect.actor;
 	}
 	void flush()
 	{
@@ -80,8 +153,12 @@ public:
 			of<<" ";
 			of<<serializeJsonString(i->actor);
 			of<<" ";
-			std::string action_s = i->toString();
-			of<<action_s<<std::endl;
+			of<<i->toString();
+			if(i->actor_is_guess){
+				of<<" ";
+				of<<"actor_is_guess";
+			}
+			of<<std::endl;
 		}
 		m_action_todisk_buffer.clear();
 	}
@@ -90,7 +167,8 @@ public:
 
 	RollbackManager(const std::string &filepath, IGameDef *gamedef):
 		m_filepath(filepath),
-		m_gamedef(gamedef)
+		m_gamedef(gamedef),
+		m_current_actor_is_guess(false)
 	{
 		infostream<<"RollbackManager::RollbackManager("<<filepath<<")"
 				<<std::endl;
@@ -209,20 +287,7 @@ public:
 
 			// 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
+			if(!i->getPosition(&action_p))
 				continue;
 
 			if(range == 0){
@@ -281,6 +346,7 @@ private:
 	std::string m_filepath;
 	IGameDef *m_gamedef;
 	std::string m_current_actor;
+	bool m_current_actor_is_guess;
 	std::list<RollbackAction> m_action_todisk_buffer;
 	std::list<RollbackAction> m_action_latest_buffer;
 };
diff --git a/src/rollback.h b/src/rollback.h
index b5428c451..59db122e3 100644
--- a/src/rollback.h
+++ b/src/rollback.h
@@ -33,7 +33,9 @@ public:
 	// IRollbackReportManager
 	virtual void reportAction(const RollbackAction &action) = 0;
 	virtual std::string getActor() = 0;
-	virtual void setActor(const std::string &actor) = 0;
+	virtual bool isActorGuess() = 0;
+	virtual void setActor(const std::string &actor, bool is_guess) = 0;
+	virtual std::string getSuspect(v3s16 p, int max_time) = 0;
 
 	virtual ~IRollbackManager(){}
 	virtual void flush() = 0;
diff --git a/src/rollback_interface.cpp b/src/rollback_interface.cpp
index e15fe3da3..b2eb2093c 100644
--- a/src/rollback_interface.cpp
+++ b/src/rollback_interface.cpp
@@ -289,6 +289,24 @@ bool RollbackAction::isImportant(IGameDef *gamedef) const
 	}
 }
 
+bool RollbackAction::getPosition(v3s16 *dst) const
+{
+	switch(type){
+	case RollbackAction::TYPE_SET_NODE:
+		if(dst) *dst = p;
+		return true;
+	case RollbackAction::TYPE_MODIFY_INVENTORY_STACK: {
+		InventoryLocation loc;
+		loc.deSerialize(inventory_location);
+		if(loc.type != InventoryLocation::NODEMETA)
+			return false;
+		if(dst) *dst = loc.p;
+		return true; }
+	default:
+		return false;
+	}
+}
+
 bool RollbackAction::applyRevert(Map *map, InventoryManager *imgr, IGameDef *gamedef) const
 {
 	try{
diff --git a/src/rollback_interface.h b/src/rollback_interface.h
index 0f0a11885..ac8368f4e 100644
--- a/src/rollback_interface.h
+++ b/src/rollback_interface.h
@@ -65,6 +65,7 @@ struct RollbackAction
 
 	int unix_time;
 	std::string actor;
+	bool actor_is_guess;
 
 	v3s16 p;
 	RollbackNode n_old;
@@ -77,7 +78,9 @@ struct RollbackAction
 	std::string inventory_stack;
 
 	RollbackAction():
-		type(TYPE_NOTHING)
+		type(TYPE_NOTHING),
+		unix_time(0),
+		actor_is_guess(false)
 	{}
 
 	void setSetNode(v3s16 p_, const RollbackNode &n_old_,
@@ -107,6 +110,8 @@ struct RollbackAction
 	
 	// Eg. flowing water level changes are not important
 	bool isImportant(IGameDef *gamedef) const;
+	
+	bool getPosition(v3s16 *dst) const;
 
 	bool applyRevert(Map *map, InventoryManager *imgr, IGameDef *gamedef) const;
 };
@@ -117,29 +122,34 @@ public:
 	virtual ~IRollbackReportSink(){}
 	virtual void reportAction(const RollbackAction &action) = 0;
 	virtual std::string getActor() = 0;
-	virtual void setActor(const std::string &actor) = 0;
+	virtual bool isActorGuess() = 0;
+	virtual void setActor(const std::string &actor, bool is_guess) = 0;
+	virtual std::string getSuspect(v3s16 p, int max_time) = 0;
 };
 
 class RollbackScopeActor
 {
 public:
-	RollbackScopeActor(IRollbackReportSink *sink, const std::string &actor):
+	RollbackScopeActor(IRollbackReportSink *sink, const std::string &actor,
+			bool is_guess=false):
 		m_sink(sink)
 	{
 		if(m_sink){
 			m_actor_was = m_sink->getActor();
-			m_sink->setActor(actor);
+			m_actor_was_guess = m_sink->isActorGuess();
+			m_sink->setActor(actor, is_guess);
 		}
 	}
 	~RollbackScopeActor()
 	{
 		if(m_sink){
-			m_sink->setActor(m_actor_was);
+			m_sink->setActor(m_actor_was, m_actor_was_guess);
 		}
 	}
 private:
 	IRollbackReportSink *m_sink;
 	std::string m_actor_was;
+	bool m_actor_was_guess;
 };
 
 #endif