// 「公式映射」表达式的编译 / 求值实现（详见 `FormulaEval.hpp`）。

#include "FormulaEval.hpp"

#include <cmath>
#include <cstddef>
#include <cstdlib>
#include <cwctype>
#include <limits>
#include <vector>

namespace jdi
{
	namespace
	{
		/** 公式允许的最大长度（防止恶意/误粘贴的超长文本导致解析耗时）。 */
		constexpr std::size_t kMaxFormulaLength = 512;
		/** 允许的最大记号数（与长度一起兜底）。 */
		constexpr std::size_t kMaxFormulaTokens = 512;

		/**
		 * @brief 逆波兰式里的一个运算单元。
		 *
		 * 类型定义在头文件里（`FormulaInstruction`），这样 `FormulaProgram` 可以在
		 * 头内联求值、而解析器与 `EvaluateFormula` 共用同一份指令表示。
		 */
		using FormulaOp = FormulaInstruction;

		/** 单个自变量占用的栈槽（求值时用）。 */
		constexpr std::size_t kMaxStack = kFormulaMaxStack;

		/** 记号类型。 */
		enum class TokenKind : int
		{
			NUMBER = 0,
			VARIABLE,
			PLUS,
			MINUS,
			STAR,
			SLASH,
			CARET,
			LEFT_PAREN,
			RIGHT_PAREN,
			END
		};

		struct Token
		{
			TokenKind kind = TokenKind::END;
			double value = 0.0;
		};

		/** 把一个公式文本切成记号序列（失败返回 false 并写 error）。 */
		bool Tokenize(const std::wstring& text, std::vector<Token>& tokens, std::wstring* error)
		{
			tokens.clear();
			std::size_t index = 0;
			const std::size_t length = text.size();
			if (length > kMaxFormulaLength)
			{
				if (error != nullptr)
				{
					*error = L"公式过长（最多 512 个字符）。";
				}
				return false;
			}
			while (index < length)
			{
				const wchar_t ch = text[index];
				if (std::iswspace(static_cast<wint_t>(ch)) != 0)
				{
					++index;
					continue;
				}
				if (ch == L'+')
				{
					tokens.push_back(Token{TokenKind::PLUS, 0.0});
					++index;
				}
				else if (ch == L'-')
				{
					tokens.push_back(Token{TokenKind::MINUS, 0.0});
					++index;
				}
				else if (ch == L'*')
				{
					tokens.push_back(Token{TokenKind::STAR, 0.0});
					++index;
				}
				else if (ch == L'/')
				{
					tokens.push_back(Token{TokenKind::SLASH, 0.0});
					++index;
				}
				else if (ch == L'^')
				{
					tokens.push_back(Token{TokenKind::CARET, 0.0});
					++index;
				}
				else if (ch == L'(')
				{
					tokens.push_back(Token{TokenKind::LEFT_PAREN, 0.0});
					++index;
				}
				else if (ch == L')')
				{
					tokens.push_back(Token{TokenKind::RIGHT_PAREN, 0.0});
					++index;
				}
				else if ((ch >= L'0' && ch <= L'9') || ch == L'.')
				{
					// 数字：手工扫描，交给 `wcstod` 转换（保证与内联编辑的数值语义一致）。
					const std::size_t start = index;
					while (index < length &&
					       ((text[index] >= L'0' && text[index] <= L'9') || text[index] == L'.'))
					{
						++index;
					}
					// 指数部分必须**真的带数字**才算数字的一部分：
					// `2e` 里的 `e` 是自然常数（不能把 `e` 吞进食指后当成数字 2 再用掉它）。
					if (index < length && (text[index] == L'e' || text[index] == L'E'))
					{
						std::size_t probe = index + 1;
						if (probe < length && (text[probe] == L'+' || text[probe] == L'-'))
						{
							++probe;
						}
						if (probe < length && text[probe] >= L'0' && text[probe] <= L'9')
						{
							index = probe;
							while (index < length && text[index] >= L'0' && text[index] <= L'9')
							{
								++index;
							}
						}
					}
					const std::wstring literal = text.substr(start, index - start);
					wchar_t* stop = nullptr;
					const double value = std::wcstod(literal.c_str(), &stop);
					if (stop == literal.c_str() || !std::isfinite(value))
					{
						if (error != nullptr)
						{
							*error = L"数字格式不正确。";
						}
						return false;
					}
					tokens.push_back(Token{TokenKind::NUMBER, value});
				}
				else if (std::iswalpha(static_cast<wint_t>(ch)) != 0)
				{
					// 标识符：只允许 X / x / f(t) 作为数据点，以及常量 e / pi。
					const std::size_t start = index;
					while (index < length && std::iswalpha(static_cast<wint_t>(text[index])) != 0)
					{
						++index;
					}
					std::wstring name = text.substr(start, index - start);
					// 跳过空格后可能是 `(t)`（`f(t)` 的写法）。
					std::size_t look = index;
					while (look < length && std::iswspace(static_cast<wint_t>(text[look])) != 0)
					{
						++look;
					}
					bool hasArgument = false;
					if (look < length && text[look] == L'(')
					{
						std::size_t inner = look + 1;
						while (inner < length && std::iswspace(static_cast<wint_t>(text[inner])) != 0)
						{
							++inner;
						}
						if (inner < length && (text[inner] == L't' || text[inner] == L'T'))
						{
							++inner;
							while (inner < length && std::iswspace(static_cast<wint_t>(text[inner])) != 0)
							{
								++inner;
							}
							if (inner < length && text[inner] == L')')
							{
								hasArgument = true;
								index = inner + 1;
							}
						}
					}
					for (wchar_t& letter : name)
					{
						letter = static_cast<wchar_t>(std::towlower(static_cast<wint_t>(letter)));
					}
					if (name == L"x" || (name == L"f" && hasArgument))
					{
						tokens.push_back(Token{TokenKind::VARIABLE, 0.0});
					}
					else if (name == L"pi")
					{
						tokens.push_back(Token{TokenKind::NUMBER, 3.14159265358979323846});
					}
					else if (name == L"e")
					{
						tokens.push_back(Token{TokenKind::NUMBER, 2.71828182845904523536});
					}
					else
					{
						if (error != nullptr)
						{
							*error = L"无法识别的标识符（数据点请写 f(t) 或 X；常量只支持 e / pi）。";
						}
						return false;
					}
				}
				else
				{
					if (error != nullptr)
					{
						*error = L"公式含有无法识别的字符。";
					}
					return false;
				}
			}
			tokens.push_back(Token{TokenKind::END, 0.0});
			if (tokens.size() > kMaxFormulaTokens)
			{
				if (error != nullptr)
				{
					*error = L"公式过于复杂。";
				}
				return false;
			}
			return true;
		}

		/** 递归下降解析器（直接产出逆波兰式）。 */
		class Parser
		{
		public:
			Parser(const std::vector<Token>& tokens, std::vector<FormulaOp>& output, std::wstring* error)
			    : m_tokens(tokens), m_output(output), m_error(error)
			{
			}

			bool Parse()
			{
				if (!ParseExpression())
				{
					return false;
				}
				if (Current().kind != TokenKind::END)
				{
					return SetError(L"公式存在多余的内容（请检查括号是否配对）。");
				}
				return true;
			}

		private:
			const Token& Current() const { return m_tokens[m_position]; }
			void Advance()
			{
				if (m_position + 1 < m_tokens.size())
				{
					++m_position;
				}
			}
			bool SetError(const wchar_t* message)
			{
				if (m_error != nullptr)
				{
					*m_error = message;
				}
				return false;
			}

			bool ParseExpression()
			{
				if (!ParseTerm())
				{
					return false;
				}
				while (Current().kind == TokenKind::PLUS || Current().kind == TokenKind::MINUS)
				{
					const bool add = (Current().kind == TokenKind::PLUS);
					Advance();
					if (!ParseTerm())
					{
						return false;
					}
					m_output.push_back(FormulaOp{add ? FormulaOp::Kind::ADD
					                                 : FormulaOp::Kind::SUBTRACT,
					                             0.0});
				}
				return true;
			}

			bool ParseTerm()
			{
				if (!ParseUnary())
				{
					return false;
				}
				while (Current().kind == TokenKind::STAR || Current().kind == TokenKind::SLASH)
				{
					const bool multiply = (Current().kind == TokenKind::STAR);
					Advance();
					if (!ParseUnary())
					{
						return false;
					}
					m_output.push_back(FormulaOp{multiply ? FormulaOp::Kind::MULTIPLY
					                                      : FormulaOp::Kind::DIVIDE,
					                             0.0});
				}
				return true;
			}

			bool ParseUnary()
			{
				if (Current().kind == TokenKind::PLUS)
				{
					Advance();
					return ParseUnary();
				}
				if (Current().kind == TokenKind::MINUS)
				{
					Advance();
					if (!ParseUnary())
					{
						return false;
					}
					m_output.push_back(FormulaOp{FormulaOp::Kind::NEGATE, 0.0});
					return true;
				}
				return ParsePower();
			}

			/**
			 * @brief 幂运算（优先级高于乘除、低于一元正负号；**右结合**）。
			 *
			 * `power := primary ('^' unary)?`
			 *  * `2^3^2` = 2^(3^2)（右结合）；
			 *  * `2^-1` 允许（指数的符号）；
			 *  * `-2^2` = -(2^2)（一元负号作用于整个幂）。
			 */
			bool ParsePower()
			{
				if (!ParsePrimary())
				{
					return false;
				}
				if (Current().kind != TokenKind::CARET)
				{
					return true;
				}
				Advance();
				if (!ParseUnary())
				{
					return false;
				}
				m_output.push_back(FormulaOp{FormulaOp::Kind::POWER, 0.0});
				return true;
			}

			bool ParsePrimary()
			{
				const Token& token = Current();
				if (token.kind == TokenKind::NUMBER)
				{
					m_output.push_back(FormulaOp{FormulaOp::Kind::NUMBER, token.value});
					Advance();
					return true;
				}
				if (token.kind == TokenKind::VARIABLE)
				{
					m_output.push_back(FormulaOp{FormulaOp::Kind::VARIABLE, 0.0});
					Advance();
					return true;
				}
				if (token.kind == TokenKind::LEFT_PAREN)
				{
					Advance();
					if (!ParseExpression())
					{
						return false;
					}
					if (Current().kind != TokenKind::RIGHT_PAREN)
					{
						return SetError(L"缺少右括号。");
					}
					Advance();
					return true;
				}
				return SetError(L"公式不完整或存在多余的运算符。");
			}

			const std::vector<Token>& m_tokens;
			std::vector<FormulaOp>& m_output;
			std::wstring* m_error;
			std::size_t m_position = 0;
		};

		/**
		 * @brief 编译期优化：常量折叠 + 幂次改写（减小逐点求值的指令数与 `pow` 调用）。
		 *
		 * 两件事：
		 *  1. `NUMBER a, NUMBER b, <二元运算>` ⇒ `NUMBER (a OP b)`。例如
		 *     `f(t)*2/1.25+14.2` 的 `2/1.25` 会折叠成 `1.6`，指令数 7 ⇒ 5。
		 *  2. `NUMBER 2, POWER` ⇒ `SQUARE`；`NUMBER 3, POWER` ⇒ `CUBE`；
		 *     `NUMBER 0.5, POWER` ⇒ `SQRT`。`std::pow` 每点一次在 2580 万采样上约 500ms，
		 *     而 `x*x` 只是一条乘法（实测 `f(t)^2` 从 0.9s 降到与线性公式同级）。
		 *
		 * 两者都**不改变语义**（浮点运算顺序原样保留），因此不需要"是否精确"的特判。
		 *
		 * @param [IN,OUT] program 解析器输出的逆波兰式（原地改写）。
		 */
		void OptimizeProgram(std::vector<FormulaInstruction>& program)
		{
			using Kind = FormulaInstruction::Kind;
			std::vector<FormulaInstruction> output;
			output.reserve(program.size());
			// ⚠️ `constant` 与**求值栈槽**一一对应（不是与 `output` 元素对应）：一元运算
			//    不改变栈深，因此它不会往 `constant` 里加元素。只有"栈顶是常量"时
			//    `output.back()` 才必然是一条 `NUMBER`，折叠才安全。
			std::vector<bool> constant;
			constant.reserve(program.size());

			const auto isBinary = [](Kind kind)
			{
				return kind == Kind::ADD || kind == Kind::SUBTRACT || kind == Kind::MULTIPLY ||
				       kind == Kind::DIVIDE || kind == Kind::POWER;
			};
			const auto pushNumber = [&output, &constant](double value)
			{
				FormulaInstruction instruction;
				instruction.kind = Kind::NUMBER;
				instruction.value = value;
				output.push_back(instruction);
				constant.push_back(true);
			};

			for (const FormulaInstruction& instruction : program)
			{
				if (instruction.kind == Kind::NUMBER || instruction.kind == Kind::VARIABLE)
				{
					output.push_back(instruction);
					constant.push_back(instruction.kind == Kind::NUMBER);
					continue;
				}
				if (isBinary(instruction.kind))
				{
					if (constant.size() >= 2 && constant[constant.size() - 1] &&
					    constant[constant.size() - 2])
					{
						// 两个操作数都是常量 ⇒ 折叠（`output` 末尾两条必是它们的 NUMBER 指令）。
						const double right = output.back().value;
						output.pop_back();
						constant.pop_back();
						const double left = output.back().value;
						output.pop_back();
						constant.pop_back();
						double folded = 0.0;
						switch (instruction.kind)
						{
						case Kind::ADD:
							folded = left + right;
							break;
						case Kind::SUBTRACT:
							folded = left - right;
							break;
						case Kind::MULTIPLY:
							folded = left * right;
							break;
						case Kind::DIVIDE:
							folded = left / right;
							break;
						default:
							folded = std::pow(left, right);
							break;
						}
						pushNumber(folded);
						continue;
					}
					// 幂次改写：`x ^ 2 / 3 / 0.5`（右操作数是常量）。
					if (instruction.kind == Kind::POWER && !constant.empty() && constant.back())
					{
						const double exponent = output.back().value;
						if (exponent == 2.0 || exponent == 3.0 || exponent == 0.5)
						{
							output.pop_back();
							constant.pop_back();
							FormulaInstruction rewritten;
							rewritten.kind = (exponent == 2.0)   ? Kind::SQUARE
							                 : (exponent == 3.0) ? Kind::CUBE
							                                     : Kind::SQRT;
							output.push_back(rewritten);
							constant.push_back(false);
							continue;
						}
					}
					output.push_back(instruction);
					constant.pop_back();
					constant.pop_back();
					constant.push_back(false);
					continue;
				}
				// 一元运算（NEGATE / SQUARE / CUBE / SQRT）：栈深不变。
				if (!constant.empty() && constant.back())
				{
					// 栈顶是常量 ⇒ 直接折叠成一条 `NUMBER`（`output.back()` 必为 NUMBER）。
					const double value = output.back().value;
					output.pop_back();
					double folded = value;
					switch (instruction.kind)
					{
					case Kind::NEGATE:
						folded = -value;
						break;
					case Kind::SQUARE:
						folded = value * value;
						break;
					case Kind::CUBE:
						folded = value * value * value;
						break;
					default:
						folded = std::sqrt(value);
						break;
					}
					pushNumber(folded);
					continue;
				}
				// 非常量：保留指令，栈顶保持"非常量"（本来就如此）。
				output.push_back(instruction);
			}
			program.swap(output);
		}


		} // namespace

	FormulaProgram::FormulaProgram(const std::wstring& text)
	{
		if (text.empty())
		{
			return;
		}
		std::vector<Token> tokens;
		std::wstring error;
		if (!Tokenize(text, tokens, &error))
		{
			return;
		}
		Parser parser(tokens, m_instructions, &error);
		if (!parser.Parse())
		{
			m_instructions.clear();
			return;
		}
		// 常量折叠 + 幂次改写（`x^2` ⇒ `x*x`）：逐点求值的指令数与 `pow` 调用都随之减少。
		OptimizeProgram(m_instructions);
		// ⚠️ 编译期栈深校验：`Evaluate()` 不做运行期边界检查（性能），因此这里必须拒绝
		//    深层嵌套的表达式（它们会回退到带检查的 `EvaluateFormula()`，结果一致）。
		std::size_t depth = 0;
		std::size_t maximumDepth = 0;
		for (const FormulaInstruction& instruction : m_instructions)
		{
			switch (instruction.kind)
			{
			case FormulaInstruction::Kind::NUMBER:
			case FormulaInstruction::Kind::VARIABLE:
				++depth;
				if (depth > maximumDepth)
				{
					maximumDepth = depth;
				}
				break;
			case FormulaInstruction::Kind::NEGATE:
				break;
			default:
				if (depth >= 2)
				{
					--depth;
				}
				break;
			}
		}
		if (maximumDepth > kFormulaMaxStack)
		{
			m_instructions.clear();
			return;
		}
		m_valid = true;
	}

	bool ValidateFormula(const std::wstring& text, std::wstring* error)
	{
		if (error != nullptr)
		{
			error->clear();
		}
		if (text.empty())
		{
			return true;
		}
		std::vector<Token> tokens;
		if (!Tokenize(text, tokens, error))
		{
			return false;
		}
		std::vector<FormulaOp> program;
		Parser parser(tokens, program, error);
		if (!parser.Parse())
		{
			return false;
		}
		return true;
	}

	double EvaluateFormula(const std::wstring& text, double x)
	{
		// 逐点路径（绘制 / 统计 / 派生烘焙）与批量路径共用**同一份**编译结果：
		// 线程内按**内容**缓存一条 `FormulaProgram`（含同一套编译期优化）。
		// ⚠️ 不能只比指针（SSO 下等长改公式会复用旧程序，见历史记录）。
		static thread_local FormulaProgram cachedProgram;
		static thread_local std::wstring cachedText;
		static thread_local bool cached = false;
		if (!cached || cachedText != text)
		{
			cachedProgram = FormulaProgram(text);
			cachedText = text;
			cached = true;
		}
		if (!cachedProgram.Valid())
		{
			return x;	// 空 / 非法：不做映射（保证波形照常显示）
		}
		return cachedProgram.Evaluate(x);
	}

	std::wstring NormalizeFormulaText(const std::wstring& text)
	{
		std::wstring output;
		output.reserve(text.size() + 8);
		const std::size_t length = text.size();
		std::size_t index = 0;
		while (index < length)
		{
			const wchar_t ch = text[index];
			if (std::iswalpha(static_cast<wint_t>(ch)) == 0)
			{
				output.push_back(ch);
				++index;
				continue;
			}
			const std::size_t start = index;
			while (index < length && std::iswalpha(static_cast<wint_t>(text[index])) != 0)
			{
				++index;
			}
			std::wstring name = text.substr(start, index - start);
			// 已经是 `f(t)`：跳过随后的 `(t)`，整体原样输出（统一写成小写形式）。
			std::size_t look = index;
			while (look < length && std::iswspace(static_cast<wint_t>(text[look])) != 0)
			{
				++look;
			}
			bool hasArgument = false;
			if (look < length && text[look] == L'(')
			{
				std::size_t inner = look + 1;
				while (inner < length && std::iswspace(static_cast<wint_t>(text[inner])) != 0)
				{
					++inner;
				}
				if (inner < length && (text[inner] == L't' || text[inner] == L'T'))
				{
					++inner;
					while (inner < length && std::iswspace(static_cast<wint_t>(text[inner])) != 0)
					{
						++inner;
					}
					if (inner < length && text[inner] == L')')
					{
						hasArgument = true;
						index = inner + 1;
					}
				}
			}
			std::wstring lowered = name;
			for (wchar_t& letter : lowered)
			{
				letter = static_cast<wchar_t>(std::towlower(static_cast<wint_t>(letter)));
			}
			// 数据点：`X` / `x` / `f(t)`（含 `F(T)`）一律写成规范形式 `f(t)`。
			// ⚠️ **单独的 `f` 不归一化**：它不是合法写法（用户 2026-11-03 明确要求），
			//    原样输出交给 `ValidateFormula` 报错，而不是悄悄当成 `f(t)` 接受。
			if (lowered == L"x" || (lowered == L"f" && hasArgument))
			{
				output += L"f(t)";
			}
			// 常量统一为小写（`E` / `Pi` / `PI` → `e` / `pi`）。
			else if (lowered == L"e")
			{
				output += L"e";
			}
			else if (lowered == L"pi")
			{
				output += L"pi";
			}
			else
			{
				output += name;
			}
		}
		return output;
	}
} // namespace jdi