# HG changeset patch
# User Rubidium <rubidium@openttd.org>
# Date 2021-04-15 17:44:43
# Node ID b31f7cc3774b088904d3fc83f19d3cccd179e66a
# Parent  205b0c2c0e50ad046d717a0215f1b36db2cf90b6

Fix #7513: recursive array/class/table release caused stack overflow

diff --git a/src/3rdparty/squirrel/squirrel/sqarray.h b/src/3rdparty/squirrel/squirrel/sqarray.h
--- a/src/3rdparty/squirrel/squirrel/sqarray.h
+++ b/src/3rdparty/squirrel/squirrel/sqarray.h
@@ -17,9 +17,9 @@ public:
 		return newarray;
 	}
 #ifndef NO_GARBAGE_COLLECTOR
-	void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue);
+	void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue) override;
 #endif
-	void Finalize(){
+	void Finalize() override {
 		_values.resize(0);
 	}
 	bool Get(const SQInteger nidx,SQObjectPtr &val)
@@ -78,9 +78,13 @@ public:
 		ShrinkIfNeeded();
 		return true;
 	}
-	void Release()
+	void Release() override
 	{
-		sq_delete(this,SQArray);
+		this->_sharedstate->DelayFinalFree(this);
+	}
+	void FinalFree() override
+	{
+		sq_delete(this, SQArray);
 	}
 	SQObjectPtrVec _values;
 };
diff --git a/src/3rdparty/squirrel/squirrel/sqclass.h b/src/3rdparty/squirrel/squirrel/sqclass.h
--- a/src/3rdparty/squirrel/squirrel/sqclass.h
+++ b/src/3rdparty/squirrel/squirrel/sqclass.h
@@ -126,31 +126,33 @@ public:
 		}
 		return false;
 	}
-	void Release() {
+	void Release() override {
 		_uiRef++;
 		try {
 			if (_hook) { _hook(_userpointer,0);}
 		} catch (...) {
 			_uiRef--;
 			if (_uiRef == 0) {
-				SQInteger size = _memsize;
-				this->~SQInstance();
-				SQ_FREE(this, size);
+				this->_sharedstate->DelayFinalFree(this);
 			}
 			throw;
 		}
 		_uiRef--;
 		if(_uiRef > 0) return;
+		this->_sharedstate->DelayFinalFree(this);
+	}
+	void FinalFree() override
+	{
 		SQInteger size = _memsize;
 		this->~SQInstance();
 		SQ_FREE(this, size);
 	}
-	void Finalize();
+	void Finalize() override;
 #ifndef NO_GARBAGE_COLLECTOR
-	void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue);
+	void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue) override;
 #endif
 	bool InstanceOf(SQClass *trg);
-	bool GetMetaMethod(SQVM *v,SQMetaMethod mm,SQObjectPtr &res);
+	bool GetMetaMethod(SQVM *v,SQMetaMethod mm,SQObjectPtr &res) override;
 
 	SQClass *_class;
 	SQUserPointer _userpointer;
diff --git a/src/3rdparty/squirrel/squirrel/sqobject.h b/src/3rdparty/squirrel/squirrel/sqobject.h
--- a/src/3rdparty/squirrel/squirrel/sqobject.h
+++ b/src/3rdparty/squirrel/squirrel/sqobject.h
@@ -2,7 +2,7 @@
 #ifndef _SQOBJECT_H_
 #define _SQOBJECT_H_
 
-#include <forward_list>
+#include <vector>
 #include "squtils.h"
 
 #define SQ_CLOSURESTREAM_HEAD (('S'<<24)|('Q'<<16)|('I'<<8)|('R'))
@@ -350,6 +350,14 @@ struct SQCollectable : public SQRefCount
 	virtual void Finalize()=0;
 	static void AddToChain(SQCollectable **chain,SQCollectable *c);
 	static void RemoveFromChain(SQCollectable **chain,SQCollectable *c);
+
+	/**
+	 * Helper to perform the final memory freeing of this instance. Since the destructor might
+	 * release more objects, this can cause a very deep recursion. As such, the calls to this
+	 * are to be done via _sharedstate->DelayFinalFree which ensures the calls to this method
+	 * are done in an iterative instead of recursive approach.
+	 */
+	virtual void FinalFree() {}
 };
 
 /**
@@ -357,19 +365,19 @@ struct SQCollectable : public SQRefCount
  * The iterative approach provides effectively a depth first search approach.
  */
 class SQGCMarkerQueue {
-	std::forward_list<SQCollectable*> queue; ///< The queue of elements to still process.
+	std::vector<SQCollectable*> stack; ///< The elements to still process, with the most recent elements at the back.
 public:
 	/** Whether there are any elements left to process. */
-	bool IsEmpty() { return this->queue.empty(); }
+	bool IsEmpty() { return this->stack.empty(); }
 
 	/**
-	 * Remove the first element from the queue.
+	 * Remove the most recently added element from the queue.
 	 * Removal when the queue is empty results in undefined behaviour.
 	 */
 	SQCollectable *Pop()
 	{
-		SQCollectable *collectable = this->queue.front();
-		this->queue.pop_front();
+		SQCollectable *collectable = this->stack.back();
+		this->stack.pop_back();
 		return collectable;
 	}
 
@@ -382,7 +390,7 @@ public:
 	{
 		if ((collectable->_uiRef & MARK_FLAG) == 0) {
 			collectable->_uiRef |= MARK_FLAG;
-			this->queue.push_front(collectable);
+			this->stack.push_back(collectable);
 		}
 	}
 };
diff --git a/src/3rdparty/squirrel/squirrel/sqstate.cpp b/src/3rdparty/squirrel/squirrel/sqstate.cpp
--- a/src/3rdparty/squirrel/squirrel/sqstate.cpp
+++ b/src/3rdparty/squirrel/squirrel/sqstate.cpp
@@ -99,6 +99,7 @@ SQSharedState::SQSharedState()
 	_notifyallexceptions = false;
 	_scratchpad=NULL;
 	_scratchpadsize=0;
+	_collectable_free_processing = false;
 #ifndef NO_GARBAGE_COLLECTOR
 	_gc_chain=NULL;
 #endif
@@ -226,6 +227,34 @@ SQInteger SQSharedState::GetMetaMethodId
 	return -1;
 }
 
+/**
+ * Helper function that is to be used instead of calling FinalFree directly on the instance,
+ * so the frees can happen iteratively. This as in the FinalFree the references to any other
+ * objects are released, which can cause those object to be freed yielding a potentially
+ * very deep stack in case of for example a link list.
+ *
+ * This is done internally by a vector onto which the to be freed instances are pushed. When
+ * this is called when not already processing, this method will actually call the FinalFree
+ * function which might cause more elements to end up in the queue which this method then
+ * picks up continueing until it has processed all instances in that queue.
+ * @param collectable The collectable to (eventually) free.
+ */
+void SQSharedState::DelayFinalFree(SQCollectable *collectable)
+{
+	this->_collectable_free_queue.push_back(collectable);
+
+	if (!this->_collectable_free_processing) {
+		this->_collectable_free_processing = true;
+		while (!this->_collectable_free_queue.empty()) {
+			SQCollectable *collectable = this->_collectable_free_queue.back();
+			this->_collectable_free_queue.pop_back();
+			collectable->FinalFree();
+		}
+		this->_collectable_free_processing = false;
+	}
+}
+
+
 #ifndef NO_GARBAGE_COLLECTOR
 
 void SQSharedState::EnqueueMarkObject(SQObjectPtr &o,SQGCMarkerQueue &queue)
diff --git a/src/3rdparty/squirrel/squirrel/sqstate.h b/src/3rdparty/squirrel/squirrel/sqstate.h
--- a/src/3rdparty/squirrel/squirrel/sqstate.h
+++ b/src/3rdparty/squirrel/squirrel/sqstate.h
@@ -61,6 +61,7 @@ struct SQSharedState
 public:
 	SQChar* GetScratchPad(SQInteger size);
 	SQInteger GetMetaMethodIdxByName(const SQObjectPtr &name);
+	void DelayFinalFree(SQCollectable *collectable);
 #ifndef NO_GARBAGE_COLLECTOR
 	SQInteger CollectGarbage(SQVM *vm);
 	static void EnqueueMarkObject(SQObjectPtr &o,SQGCMarkerQueue &queue);
@@ -74,6 +75,10 @@ public:
 	SQObjectPtr _registry;
 	SQObjectPtr _consts;
 	SQObjectPtr _constructoridx;
+	/** Queue to make freeing of collectables iterative. */
+	std::vector<SQCollectable *> _collectable_free_queue;
+	/** Whether someone is already processing the _collectable_free_queue. */
+	bool _collectable_free_processing;
 #ifndef NO_GARBAGE_COLLECTOR
 	SQCollectable *_gc_chain;
 #endif
diff --git a/src/3rdparty/squirrel/squirrel/sqtable.h b/src/3rdparty/squirrel/squirrel/sqtable.h
--- a/src/3rdparty/squirrel/squirrel/sqtable.h
+++ b/src/3rdparty/squirrel/squirrel/sqtable.h
@@ -50,7 +50,7 @@ public:
 		newtable->_delegate = NULL;
 		return newtable;
 	}
-	void Finalize();
+	void Finalize() override;
 	SQTable *Clone();
 	~SQTable()
 	{
@@ -60,7 +60,7 @@ public:
 		SQ_FREE(_nodes, _numofnodes * sizeof(_HashNode));
 	}
 #ifndef NO_GARBAGE_COLLECTOR
-	void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue);
+	void EnqueueMarkObjectForChildren(SQGCMarkerQueue &queue) override;
 #endif
 	inline _HashNode *_Get(const SQObjectPtr &key,SQHash hash)
 	{
@@ -81,7 +81,11 @@ public:
 
 	SQInteger CountUsed(){ return _usednodes;}
 	void Clear();
-	void Release()
+	void Release() override
+	{
+		this->_sharedstate->DelayFinalFree(this);
+	}
+	void FinalFree() override
 	{
 		sq_delete(this, SQTable);
 	}