restored/math.cpp
← All source files · Download this file
9,336 bytes · SHA256 3094e3423ffb74b7fbd300468e50f5039564c735295e0a7ca6a22d09986d6606
// New bounded expression parser replacing historical mathemu; see docs/LINEAGE.md.
#include "script.h"
#include <algorithm>
#include <cerrno>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <sstream>
#include <cctype>
namespace vanilla {
[[noreturn]] void fail(const Source& s, const std::string& message) { throw Error(s, message); }
[[noreturn]] void failLimit(const Source& s, const std::string& message) { throw Error(s, message, true); }
static bool digit(char c) { return c >= '0' && c <= '9'; }
bool numeric(const std::string& s, double& result) {
std::size_t p = 0;
if (p < s.size() && (s[p] == '+' || s[p] == '-')) ++p;
bool digits = false;
while (p < s.size() && digit(s[p])) { ++p; digits = true; }
if (p < s.size() && s[p] == '.') {
++p;
while (p < s.size() && digit(s[p])) { ++p; digits = true; }
}
if (!digits) return false;
if (p < s.size() && (s[p] == 'e' || s[p] == 'E')) {
++p;
if (p < s.size() && (s[p] == '+' || s[p] == '-')) ++p;
auto begin = p;
while (p < s.size() && digit(s[p])) ++p;
if (p == begin) return false;
}
if (p != s.size()) return false;
errno = 0;
char* end = nullptr;
result = std::strtod(s.c_str(), &end);
return end == s.c_str()+s.size() && errno != ERANGE && std::isfinite(result);
}
double number(const std::string& s, const Source& source) {
double n;
if (!numeric(s, n)) fail(source, "expected finite decimal number: " + s.substr(0,80));
return n;
}
std::string format(double n, const Source& s) {
if (!std::isfinite(n)) fail(s, "numeric result must be finite");
if (n == 0) return "0";
std::ostringstream out;
out << std::setprecision(17) << n;
return out.str();
}
long long integer(const std::string& s, long long low, long long high, const Source& source) {
// All callers use bounds inside the exactly representable double integer range.
double n;
if (!numeric(s,n) || std::trunc(n) != n || n < static_cast<double>(low) || n > static_cast<double>(high))
fail(source,"expected integer in bounds");
return static_cast<long long>(n);
}
class Expression {
const std::string& text;
const Source& source;
const std::function<double(const std::string&)>& resolve;
MathCache& cache;
void emit(MathOp op, double n = 0, std::string ref = {}) { cache.code.push_back({op,n,std::move(ref)}); }
std::size_t pos = 0;
void space() { while(pos < text.size() && std::isspace(static_cast<unsigned char>(text[pos]))) ++pos; }
char peek() { space(); return pos < text.size() ? text[pos] : '\0'; }
bool take(char c) { if(peek() == c) { ++pos; return true; } return false; }
[[noreturn]] void bad() { fail(source,"invalid expression near column " + std::to_string(pos+1)); }
double checked(double n) { if(!std::isfinite(n)) fail(source,"numeric result must be finite"); return n; }
double parse(int minimum, unsigned depth) {
if (depth > 128) failLimit(source,"expression nesting limit (128)");
char c = peek();
double left = 0;
if (c == '+' || c == '-') {
++pos;
left = parse(30,depth+1);
if(c == '-') { left = -left; emit(MathOp::neg); }
} else if(take('(')) {
left = parse(0,depth+1);
if(!take(')')) bad();
} else if(c == '$' || c == '%') {
auto begin = pos++;
while(pos < text.size() && (std::isalnum(static_cast<unsigned char>(text[pos])) || text[pos] == '_')) ++pos;
if(pos == begin+1) bad();
auto ref = text.substr(begin,pos-begin);
left = resolve(ref);
emit(MathOp::reference,0,std::move(ref));
} else if(std::isalpha(static_cast<unsigned char>(c))) {
auto begin = pos++;
while(pos < text.size() && std::isalpha(static_cast<unsigned char>(text[pos]))) ++pos;
auto name = text.substr(begin,pos-begin);
if(!take('(')) bad();
double a = parse(0,depth+1), b = 0;
bool binary = take(',');
if(binary) b = parse(0,depth+1);
if(!take(')')) bad();
if(binary && name == "min") left = std::min(a,b);
else if(binary && name == "max") left = std::max(a,b);
else if(binary && name == "pow") left = std::pow(a,b);
else if(!binary && name == "abs") left = std::abs(a);
else if(!binary && name == "sqrt") left = std::sqrt(a);
else if(!binary && name == "floor") left = std::floor(a);
else if(!binary && name == "ceil") left = std::ceil(a);
else if(!binary && name == "round") left = std::round(a);
else fail(source,"unknown math function or argument count: " + name);
checked(left);
emit(binary ? (name == "min" ? MathOp::minimum : name == "max" ? MathOp::maximum : MathOp::power)
: name == "abs" ? MathOp::absolute : name == "sqrt" ? MathOp::root
: name == "floor" ? MathOp::floor : name == "ceil" ? MathOp::ceil : MathOp::round);
} else if(digit(c) || c == '.') {
auto begin = pos;
while(pos < text.size() && digit(text[pos])) ++pos;
if(pos < text.size() && text[pos] == '.') {
++pos; while(pos < text.size() && digit(text[pos])) ++pos;
}
if(pos < text.size() && (text[pos] == 'e' || text[pos] == 'E')) {
++pos;
if(pos < text.size() && (text[pos] == '+' || text[pos] == '-')) ++pos;
while(pos < text.size() && digit(text[pos])) ++pos;
}
left = number(text.substr(begin,pos-begin),source);
emit(MathOp::constant,left);
} else bad();
while(true) {
c = peek();
int precedence = c == '+' || c == '-' ? 10 : c == '*' || c == '/' || c == '%' ? 20 : c == '^' ? 40 : -1;
if(precedence < minimum) break;
++pos;
double right = parse(precedence + (c == '^' ? 0 : 1),depth+1);
if(c == '+') left += right;
else if(c == '-') left -= right;
else if(c == '*') left *= right;
else if(c == '^') left = std::pow(left,right);
else {
if(right == 0) fail(source,"division or modulo by zero");
if(c == '/') left /= right;
else left = std::fmod(left,right);
}
checked(left);
emit(c == '+' ? MathOp::add : c == '-' ? MathOp::sub : c == '*' ? MathOp::mul
: c == '^' ? MathOp::power : c == '/' ? MathOp::div : MathOp::mod);
}
return left;
}
public:
Expression(const std::string& t, const Source& s, const std::function<double(const std::string&)>& r, MathCache& m): text(t),source(s),resolve(r),cache(m) {}
double run() { auto n = parse(0,0); if(peek() != '\0') bad(); return n; }
};
double expression(const std::string& text, const Source& s, const std::function<double(const std::string&)>& resolve, MathCache& cache) {
if(!cache.ready) {
if(text.size() > 16384) failLimit(s,"expression size limit (16384)");
// Record while evaluating, rather than parsing ahead of runtime failures.
// This preserves the original first error (e.g. 1/0 followed by bad syntax).
cache.code.clear();
auto result = Expression(text,s,resolve,cache).run();
// Each emitted instruction consumes source characters. Size is bounded
// by the 16384-byte expression limit; allocate once, never per iteration.
cache.stack.resize(cache.code.size());
cache.ready = true;
return result;
}
std::size_t top = 0;
for(const auto& instruction:cache.code) {
auto op = instruction.op;
if(op == MathOp::constant || op == MathOp::reference) {
cache.stack[top++] = op == MathOp::constant ? instruction.constant : resolve(instruction.reference);
continue;
}
double right = 0;
if(op >= MathOp::add && op <= MathOp::maximum) right = cache.stack[--top];
double& left = cache.stack[top-1];
switch(op) {
case MathOp::neg: left = -left; break;
case MathOp::add: left += right; break;
case MathOp::sub: left -= right; break;
case MathOp::mul: left *= right; break;
case MathOp::div: case MathOp::mod:
if(right == 0) fail(s,"division or modulo by zero");
left = op == MathOp::div ? left/right : std::fmod(left,right); break;
case MathOp::power: left = std::pow(left,right); break;
case MathOp::minimum: left = std::min(left,right); break;
case MathOp::maximum: left = std::max(left,right); break;
case MathOp::absolute: left = std::abs(left); break;
case MathOp::root: left = std::sqrt(left); break;
case MathOp::floor: left = std::floor(left); break;
case MathOp::ceil: left = std::ceil(left); break;
case MathOp::round: left = std::round(left); break;
default: break; // constants/references handled above
}
if(!std::isfinite(left)) fail(s,"numeric result must be finite");
}
return cache.stack[0];
}
} // namespace vanilla