Added stack check to some recursive functions

2 files changed, 56 insertions, 4 deletions

diff --git a/src/GCodes/GCodeBuffer/ExpressionParser.cpp b/src/GCodes/GCodeBuffer/ExpressionParser.cpp
index 2279ca2e..6b9101ea 100644
--- a/src/GCodes/GCodeBuffer/ExpressionParser.cpp
+++ b/src/GCodes/GCodeBuffer/ExpressionParser.cpp
@@ -12,6 +12,7 @@
 #include <Platform/Platform.h>
 #include <General/NamedEnum.h>
 #include <General/NumericConverter.h>
+#include <Hardware/ExceptionHandlers.h>
 
 #include <limits>
 
@@ -21,6 +22,14 @@
 
 constexpr size_t MaxStringExpressionLength = StringLength100;
 
+namespace StackUsage
+{
+	// The following values are obtained from file ExpressionParser.su generated by the compiler
+	constexpr uint32_t ParseInternal = 72;
+	constexpr uint32_t ParseIdentifierExpression = 256;
+	constexpr uint32_t GetObjectValue_withTable = 48;
+}
+
 // These can't be declared locally inside ParseIdentifierExpression because NamedEnum includes static data
 NamedEnum(NamedConstant, unsigned int, _false, iterations, line, _null, pi, _result, _true);
 NamedEnum(Function, unsigned int, abs, acos, asin, atan, atan2, cos, degrees, exists, floor, isnan, max, min, mod, radians, random, sin, sqrt, tan);
@@ -35,6 +44,7 @@ ExpressionParser::ExpressionParser(const GCodeBuffer& p_gb, const char *text, co
 // Evaluate a bracketed expression
 void ExpressionParser::ParseExpectKet(ExpressionValue& rslt, bool evaluate, char closingBracket) THROWS(GCodeException)
 {
+	CheckStack(StackUsage::ParseInternal);
 	ParseInternal(rslt, evaluate, 0);
 	if (CurrentCharacter() != closingBracket)
 	{
@@ -43,7 +53,7 @@ void ExpressionParser::ParseExpectKet(ExpressionValue& rslt, bool evaluate, char
 	AdvancePointer();
 }
 
-// Evaluate an expression
+// Evaluate an expression. Do not call this one recursively!
 ExpressionValue ExpressionParser::Parse(bool evaluate) THROWS(GCodeException)
 {
 	obsoleteField.Clear();
@@ -77,6 +87,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_
 
 	case '-':
 		AdvancePointer();
+		CheckStack(StackUsage::ParseInternal);
 		ParseInternal(val, evaluate, UnaryPriority);
 		switch (val.GetType())
 		{
@@ -95,6 +106,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_
 
 	case '+':
 		AdvancePointer();
+		CheckStack(StackUsage::ParseInternal);
 		ParseInternal(val, evaluate, UnaryPriority);
 		switch (val.GetType())
 		{
@@ -119,10 +131,12 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_
 		if (isalpha(CurrentCharacter()))
 		{
 			// Probably applying # to an object model array, so optimise by asking the OM for just the length
+			CheckStack(StackUsage::ParseIdentifierExpression);
 			ParseIdentifierExpression(val, evaluate, true, false);
 		}
 		else
 		{
+			CheckStack(StackUsage::ParseInternal);
 			ParseInternal(val, evaluate, UnaryPriority);
 			if (val.GetType() == TypeCode::CString)
 			{
@@ -151,6 +165,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_
 
 	case '!':
 		AdvancePointer();
+		CheckStack(StackUsage::ParseInternal);
 		ParseInternal(val, evaluate, UnaryPriority);
 		ConvertToBool(val, evaluate);
 		val.bVal = !val.bVal;
@@ -163,6 +178,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_
 		}
 		else if (isalpha(c))				// looks like a variable name
 		{
+			CheckStack(StackUsage::ParseIdentifierExpression);
 			ParseIdentifierExpression(val, evaluate, false, false);
 		}
 		else
@@ -228,6 +244,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_
 			ConvertToBool(val, evaluate);
 			{
 				ExpressionValue val2;
+				CheckStack(StackUsage::ParseInternal);
 				ParseInternal(val2, evaluate && val.bVal, opPrio);		// get the next operand
 				if (val.bVal)
 				{
@@ -241,6 +258,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_
 			ConvertToBool(val, evaluate);
 			{
 				ExpressionValue val2;
+				CheckStack(StackUsage::ParseInternal);
 				ParseInternal(val2, evaluate && !val.bVal, opPrio);		// get the next operand
 				if (!val.bVal)
 				{
@@ -255,12 +273,14 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_
 			{
 				const bool b = val.bVal;
 				ExpressionValue val2;
+				CheckStack(StackUsage::ParseInternal);
 				ParseInternal(((b) ? val : val2), evaluate && b, opPrio);		// get the second operand
 				if (CurrentCharacter() != ':')
 				{
 					ThrowParseException("expected ':'");
 				}
 				AdvancePointer();
+				// We recently checked the stack for a call to ParseInternal, no need to do it again
 				ParseInternal(((b) ? val2 : val), evaluate && !b, opPrio - 1);	// get the third operand, which may be a further conditional expression
 				return;
 			}
@@ -269,6 +289,7 @@ void ExpressionParser::ParseInternal(ExpressionValue& val, bool evaluate, uint8_
 			// Handle binary operators that always evaluate both operands
 			{
 				ExpressionValue val2;
+				CheckStack(StackUsage::ParseInternal);
 				ParseInternal(val2, evaluate, opPrio);	// get the next operand
 				switch(opChar)
 				{
@@ -655,7 +676,7 @@ void ExpressionParser::ConvertToBool(ExpressionValue& val, bool evaluate) const
 	}
 }
 
-void ExpressionParser::ConvertToString(ExpressionValue& val, bool evaluate) THROWS(GCodeException)
+void ExpressionParser::ConvertToString(ExpressionValue& val, bool evaluate) noexcept
 {
 	if (!val.IsStringType())
 	{
@@ -729,6 +750,7 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva
 		if (c == '[')
 		{
 			ExpressionValue index;
+			CheckStack(StackUsage::ParseInternal);
 			ParseInternal(index, evaluate, 0);
 			if (CurrentCharacter() != ']')
 			{
@@ -836,10 +858,12 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva
 		AdvancePointer();
 		if (func == Function::exists)
 		{
+			CheckStack(StackUsage::ParseIdentifierExpression);
 			ParseIdentifierExpression(rslt, evaluate, false, true);
 		}
 		else
 		{
+			CheckStack(StackUsage::ParseInternal);
 			ParseInternal(rslt, evaluate, 0);					// evaluate the first operand
 
 			switch (func.RawValue())
@@ -911,6 +935,7 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva
 					AdvancePointer();
 					SkipWhiteSpace();
 					ExpressionValue nextOperand;
+					// We recently checked the stack for a call to ParseInternal, no need to do it again
 					ParseInternal(nextOperand, evaluate, 0);
 					ConvertToFloat(nextOperand, evaluate);
 					rslt.fVal = atan2f(rslt.fVal, nextOperand.fVal);
@@ -968,6 +993,7 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva
 					AdvancePointer();
 					SkipWhiteSpace();
 					ExpressionValue nextOperand;
+					// We recently checked the stack for a call to ParseInternal, no need to do it again
 					ParseInternal(nextOperand, evaluate, 0);
 					BalanceNumericTypes(rslt, nextOperand, evaluate);
 					if (rslt.GetType() == TypeCode::Float)
@@ -996,6 +1022,7 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva
 					AdvancePointer();
 					SkipWhiteSpace();
 					ExpressionValue nextOperand;
+					// We recently checked the stack for a call to ParseInternal, no need to do it again
 					ParseInternal(nextOperand, evaluate, 0);
 					BalanceNumericTypes(rslt, nextOperand, evaluate);
 					if (rslt.GetType() == TypeCode::Float)
@@ -1021,6 +1048,7 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva
 					AdvancePointer();
 					SkipWhiteSpace();
 					ExpressionValue nextOperand;
+					// We recently checked the stack for a call to ParseInternal, no need to do it again
 					ParseInternal(nextOperand, evaluate, 0);
 					BalanceNumericTypes(rslt, nextOperand, evaluate);
 					if (rslt.GetType() == TypeCode::Float)
@@ -1100,7 +1128,8 @@ void ExpressionParser::ParseIdentifierExpression(ExpressionValue& rslt, bool eva
 		}
 
 		// Else assume an object model value
-		rslt = reprap.GetObjectValue(context, nullptr, id.c_str());
+		CheckStack(StackUsage::GetObjectValue_withTable);
+		rslt = reprap.GetObjectValue(context, nullptr, id.c_str(), 0);
 		if (context.ObsoleteFieldQueried() && obsoleteField.IsEmpty())
 		{
 			obsoleteField.copy(id.c_str());
@@ -1200,4 +1229,25 @@ void ExpressionParser::ThrowParseException(const char *str, uint32_t param) cons
 	throw GCodeException(gb.GetLineNumber(), GetColumn(), str, param);
 }
 
+// Call this before making a recursive call, or before calling a function that needs a lot of stack from a recursive function
+void ExpressionParser::CheckStack(uint32_t calledFunctionStackUsage) const THROWS(GCodeException)
+{
+	register const char * stackPtr asm ("sp");
+	const char *stackLimit = (const char*)TaskBase::GetCallerTaskHandle() + sizeof(TaskBase);
+	debugPrintf("Margin: %u\n", stackPtr - stackLimit);
+	if (stackLimit + calledFunctionStackUsage + (StackUsage::Throw + StackUsage::Margin) <= stackPtr)
+	{
+		return;
+	}
+
+	// The stack is in danger of overflowing. Throw an exception if we have enough stack to do so (ideally, this should always be the case)
+	if (stackLimit + StackUsage::Throw <= stackPtr)
+	{
+		throw GCodeException(gb.GetLineNumber(), GetColumn(), "Expression nesting too deep");
+	}
+
+	// Not enough stack left to throw an exception
+	SoftwareReset(SoftwareResetReason::stackOverflow, (const uint32_t *)stackPtr);
+}
+
 // End
diff --git a/src/GCodes/GCodeBuffer/ExpressionParser.h b/src/GCodes/GCodeBuffer/ExpressionParser.h
index e504bed7..778a5b22 100644
--- a/src/GCodes/GCodeBuffer/ExpressionParser.h
+++ b/src/GCodes/GCodeBuffer/ExpressionParser.h
@@ -45,7 +45,9 @@ private:
 
 	void ConvertToFloat(ExpressionValue& val, bool evaluate) const THROWS(GCodeException);
 	void ConvertToBool(ExpressionValue& val, bool evaluate) const THROWS(GCodeException);
-	void ConvertToString(ExpressionValue& val, bool evaluate) THROWS(GCodeException);
+	void ConvertToString(ExpressionValue& val, bool evaluate) noexcept;
+
+	void CheckStack(uint32_t calledFunctionStackUsage) const THROWS(GCodeException);
 
 	// The following must be declared 'noinline' because it allocates a large buffer on the stack and its caller is recursive
 	static void __attribute__((noinline)) StringConcat(ExpressionValue &val, ExpressionValue &val2) noexcept;