consteval.d

// Written in the D programming language
// License: http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0
module ast.consteval;

import ast.lexer: Location, Tok, TokenType;
import ast.expression;
import ast.type;

import util;
import util.maybe;

private Expression make(ℤ v){
	return LiteralExp.makeInteger(v);
}

private Expression make(int v){
	return make(ℤ(v));
}

private Expression make(TokenType subop)(Location loc, Expression sub1) {
	import ast.semantic_: minusType;

	assert(isNumericTy(sub1.type));
	Expression subty;
	static if(subop == Tok!"-") {
		subty = minusType(sub1.type);
	} else {
		static assert(0);
	}
	assert(subty);
	assert(isNumericTy(subty));
	auto r = new UnaryExp!subop(sub1);
	r.loc = loc;
	r.type = subty;
	r.setSemCompleted();
	return r.eval();
}

private Expression make(TokenType subop)(Location loc, Expression sub1, Expression sub2) {
	import ast.semantic_: arithmeticType, subtractionType, nSubType, cmpType;

	assert(isNumericTy(sub1.type));
	assert(isNumericTy(sub2.type));
	Expression subty;
	static if(subop == Tok!"+") {
		subty = arithmeticType!false(sub1.type, sub2.type);
	} else static if(subop == Tok!"-") {
		subty = subtractionType(sub1.type, sub2.type);
	} else static if(subop == Tok!"sub") {
		subty = nSubType(sub1.type, sub2.type);
	} else static if(subop == Tok!"·") {
		subty = arithmeticType!true(sub1.type, sub2.type);
	} else static if(subop == Tok!"=" || subop == Tok!"≠") {
		subty = cmpType!true(sub1.type, sub2.type);
	} else {
		static assert(0);
	}
	assert(subty);
	assert(isNumericTy(subty));
	auto r = new BinaryExp!subop(sub1, sub2);
	r.loc = loc;
	r.type = subty;
	r.setSemCompleted();
	return r.eval();
}

private bool isNumericSum(Expression e){
	if(cast(BinaryExp!(Tok!"+"))e) return true;
	if(cast(BinaryExp!(Tok!"-"))e) return true;
	if(cast(BinaryExp!(Tok!"sub"))e) return true;
	return false;
}

private void collectSummands(Expression e, ref Expression[] summands){
	if(auto ae = cast(BinaryExp!(Tok!"+"))e){
		collectSummands(ae.e1, summands);
		collectSummands(ae.e2, summands);
	}else summands ~= e;
}

private Expression negatedSummand(Location loc, Expression s){
	if(auto u = cast(UnaryExp!(Tok!"-"))s) return u.e;
	if(auto v = s.asIntegerConstant()) if(v.get() < 0) return make(-v.get());
	return null;
}

private bool nonNeg(Expression e){ return isSubtype(e.type, ℕt(false)); }

private bool soundCommonFactor(TokenType op)(Expression factor){
	static if(op == Tok!"sub") return nonNeg(factor);
	else return true;
}

private bool factorInnerOK(TokenType op)(Expression inner){
	if(isNumericSum(inner)) return false;
	static if(op == Tok!"sub"){
		if(cast(UnaryExp!(Tok!"-"))inner) return false;
		if(auto v = inner.asIntegerConstant()) if(v.get() < 0) return false;
	}
	return true;
}

Expression evalNumericBinop(TokenType op: Tok!"+")(Location loc, Expression ne1, Maybe!ℤ v1, Expression ne2, Maybe!ℤ v2) {
	if(v1 && v2) return make(v1.get() + v2.get());
	if(v1 && v1.get() == 0) return ne2;
	if(v2 && v2.get() == 0) return ne1;
	if(v1 && !v2) return make!(Tok!"+")(loc, ne2, ne1);
	if(v2 && v2.get() < 0) {
		return make!(Tok!"-")(loc, ne1, make(-v2.get()));
	}
	static foreach(sub1;[Tok!"-",Tok!"sub"]){
		if(auto se1 = cast(BinaryExp!sub1)ne1){
			static foreach(sub2;[Tok!"-",Tok!"sub"]){
				if(auto se2 = cast(BinaryExp!sub2)ne2){
					auto nb0 = make!(Tok!"+")(loc, se1.e1, se2.e1);
					auto nb1 = make!sub1(loc, nb0, se1.e2);
					auto nb2 = make!sub2(loc, nb1, se2.e2);
					return nb2;
				}
			}
			auto v12 = se1.e2.asIntegerConstant();
			if(v12 && v2) {
				return make!sub1(loc, se1.e1, make(v12.get() - v2.get()));
			}
			if(ne2.isDeterministic() && se1.e2 == ne2) return se1.e1;
		}
	}
	if(v2) {
		if(auto ae1 = cast(BinaryExp!(Tok!"+"))ne1){
			auto v12 = ae1.e2.asIntegerConstant();
			if(v12) {
				return make!op(loc, ae1.e1, make(v12.get() + v2.get()));
			}
		}
	}
	if(auto ae2 = cast(BinaryExp!(Tok!"+"))ne2){
		return make!(Tok!"+")(loc, make!(Tok!"+")(loc, ne1, ae2.e1), ae2.e2);
	}
	if(ne1.isDeterministic()) {
		if(ne1 == ne2){
			return make!(Tok!"·")(loc, make(2), ne2);
		}
		static foreach(sub2;[Tok!"-",Tok!"sub"]){
			if(auto se2 = cast(BinaryExp!sub2)ne2){
				if(se2.e2 == ne1) return se2.e1;
			}
		}
	}
	return evalNumericSum!op(loc, ne1, ne2);
}

Expression evalNumericBinop(TokenType op)(Location loc, Expression ne1, Maybe!ℤ v1, Expression ne2, Maybe!ℤ v2) if(op == Tok!"-" || op == Tok!"sub") {
	if(v1 && v2){
		static if(op == Tok!"-") return make(v1.get() - v2.get());
		else if(v1.get() >= v2.get()) return make(v1.get() - v2.get());
	}
	if(ne1.isDeterministic() && ne1 == ne2) return make(0);
	if(v2){
		if(v2.get() == 0){
			static if(op == Tok!"-") return ne1;
			else if(nonNeg(ne1)) return ne1;
		}
		static if(op == Tok!"-")
		if(v2.get() < 0){
			return make!(Tok!"+")(loc, ne1, make(-v2.get()));
		}
	}
	static if(op == Tok!"-")
	if(v1 && v1.get() == 0) return make!(Tok!"-")(loc, ne2);
	static if(op == Tok!"-")
	if(auto se2 = cast(UnaryExp!(Tok!"-")) ne2) {
		return make!(Tok!"+")(loc, ne1, se2.e);
	}
	if(ne2.isDeterministic()) {
		if(auto ae1 = cast(BinaryExp!(Tok!"+"))ne1){
			if(ae1.e1 == ne2) return ae1.e2;
			if(ae1.e2 == ne2) return ae1.e1;
			auto v12 = ae1.e2.asIntegerConstant();
			if(v12 && v2){
				return make!op(loc, ae1.e1, make(v2.get() - v12.get()));
			}
			if(auto ae2 = cast(BinaryExp!(Tok!"+"))ne2){
				if(ae1.e1 == ae2.e1)
					return make!op(loc, ae1.e2, ae2.e2);
			}
		}
		static foreach(sub;[Tok!"-",Tok!"sub"]){
			if(auto se1 = cast(BinaryExp!sub)ne1){
				if(se1.e1 == ne2){
					auto mY = make!(Tok!"-")(loc, se1.e2);
					static if(op == Tok!"-" && sub == Tok!"-") return mY;
					else static if(op == Tok!"sub" && sub == Tok!"-"){ if(nonNeg(mY)) return mY; }
					else { if(nonNeg(ne2) && nonNeg(mY)) return mY; }
				}
			}
		}
	}
	if(ne1.isDeterministic()) {
		if(auto ae2 = cast(BinaryExp!(Tok!"+"))ne2){
			static if(op == Tok!"-"){
				if(ae2.e1 == ne1) return make!(Tok!"-")(loc, ae2.e2);
				if(ae2.e2 == ne1) return make!(Tok!"-")(loc, ae2.e1);
			}else{
				if(ae2.e1 == ne1) return make!(Tok!"sub")(loc, make(0), ae2.e2);
				if(ae2.e2 == ne1) return make!(Tok!"sub")(loc, make(0), ae2.e1);
			}
		}
		static foreach(sub;[Tok!"-",Tok!"sub"]){
			if(auto se2 = cast(BinaryExp!sub)ne2){
				if(se2.e1 == ne1){
					auto Y = se2.e2;
					auto mY = make!(Tok!"-")(loc, Y);
					static if(op == Tok!"-" && sub == Tok!"-") return Y.eval();
					else static if(op == Tok!"sub" && sub == Tok!"-"){ if(nonNeg(Y)) return Y.eval(); }
					else static if(op == Tok!"-" && sub == Tok!"sub"){ if(nonNeg(ne1) && nonNeg(mY)) return Y.eval(); }
					else { if(nonNeg(ne1) && nonNeg(mY) && nonNeg(Y)) return Y.eval(); }
				}
			}
		}
	}
	static foreach(sub1;[Tok!"-",Tok!"sub"]){
		if(auto se1 = cast(BinaryExp!sub1)ne1){
			if(auto ae = cast(BinaryExp!(Tok!"+"))se1.e1){
				if(ne2.isDeterministic()){
					bool ok = true; // TODO: assumes se1.e1 >= se1.e2 for sub1==Tok!"sub"
					// static if(sub1==Tok!"sub") ok = nonNeg(make!(Tok!"-")(loc, se1.e1, se1.e2));
					if(ok){
						if(ae.e1 == ne2) return make!op(loc, ae.e2, se1.e2);
						if(ae.e2 == ne2) return make!op(loc, ae.e1, se1.e2);
					}
				}
			}
		}
	}
	static foreach(sub2;[Tok!"-",Tok!"sub"]){
		if(auto se2 = cast(BinaryExp!sub2)ne2){
			bool ok = true; // TODO: assumes `se2.e1 >= se2.e2` for sub2==Tok!"sub"
			// static if(sub2==Tok!"sub") ok = nonNeg(make!(Tok!"-")(loc, se2.e1, se2.e2));
			if(ok) return make!op(loc, make!(Tok!"+")(loc, ne1, se2.e2), se2.e1);
		}
	}
	Expression[] ls, rs;
	collectSummands(ne1, ls);
	collectSummands(ne2, rs);
	bool moved = false;
	static if(op == Tok!"sub"){
		Expression[] L, R;
		foreach(s; ls){ if(auto neg = negatedSummand(loc, s)){ R ~= neg; moved = true; } else L ~= s; }
		foreach(s; rs){ if(auto neg = negatedSummand(loc, s)){ L ~= neg; moved = true; } else R ~= s; }
		ls = L; rs = R;
	}
	bool any = false;
	auto usedR = new bool[rs.length];
	auto keepL = new bool[ls.length];
	foreach(i, l; ls){
		keepL[i] = true;
		if(!l.isDeterministic()) continue;
		foreach(j, r; rs){
			if(!usedR[j] && l == r){
				usedR[j] = true; keepL[i] = false; any = true; break;
			}
		}
	}
	if(moved || any){
		Expression lhs = null, rhs = null;
		foreach(i, l; ls) if(keepL[i]) lhs = lhs ? make!(Tok!"+")(loc, lhs, l) : l;
		foreach(j, r; rs) if(!usedR[j]) rhs = rhs ? make!(Tok!"+")(loc, rhs, r) : r;
		return make!op(loc, lhs ? lhs : make(0), rhs ? rhs : make(0));
	}
	return evalNumericSum!op(loc, ne1, ne2);
}

Expression evalNumericBinop(TokenType op: Tok!"·")(Location loc, Expression ne1, Maybe!ℤ v1, Expression ne2, Maybe!ℤ v2) {
	if(v1 && v2) return make(v1.get() * v2.get());
	if(v1 && v1.get() == 0) return ne1;
	if(v2 && v2.get() == 0) return ne2;
	if(v1 && v1.get() == 1) return ne2;
	if(v2 && v2.get() == 1) return ne1;
	if(cast(LiteralExp)ne2 && !cast(LiteralExp)ne1) {
		return make!op(loc, ne2, ne1);
	}
	if(v1){
		static foreach(sop;[Tok!"+",Tok!"-",Tok!"sub"]){
			if(auto se2 = cast(BinaryExp!sop)ne2){
				if(auto v = se2.e2.asIntegerConstant()){
					return make!sop(loc,
					                make!(Tok!"·")(loc, ne1, se2.e1),
					                make(v1.get() * v.get()));
				}
			}
		}
	}
	return null;
}

Expression evalNumericBinop(TokenType op: Tok!"^")(Location loc, Expression ne1, Maybe!ℤ v1, Expression ne2, Maybe!ℤ v2) {
	if(v2 && v2.get() == 0) return make(1);
	if(v2 && v2.get() == 1) return ne1;
	if(v1 && v1.get() == 1) return make(1);
	if(v1 && v2 && v2.get() >= 0) {
		return make(pow(v1.get(), v2.get()));
	}
	return null;
}

Expression evalNumericSum(TokenType op)(Location loc, Expression ne1, Expression ne2) if(op == Tok!"+" || op == Tok!"-" || op == Tok!"sub") {
	if(auto me1=cast(BinaryExp!(Tok!"·"))ne1){
		if(auto le1=cast(LiteralExp)me1.e1){
			if(ne2.isDeterministic() && me1.e2==ne2){
				auto a = make!op(loc, le1, make(1));
				return make!(Tok!"·")(loc, a, me1.e2);
			}
			if(auto me2=cast(BinaryExp!(Tok!"·"))ne2){
				if(auto le2=cast(LiteralExp)me2.e1){
					if(me1.e2.isDeterministic() && me1.e2==me2.e2){
						auto a = make!op(loc, le1, le2);
						return make!(Tok!"·")(loc, a, me1.e2);
					}
				}
			}
		}
	}
	if(auto me2=cast(BinaryExp!(Tok!"·"))ne2){
		if(auto le2=cast(LiteralExp)me2.e1){
			if(ne1.isDeterministic() && me2.e2==ne1){
				auto a = make!op(loc, make(1), le2);
				return make!(Tok!"·")(loc, a, ne1);
			}
		}
	}
	if(auto me1=cast(BinaryExp!(Tok!"·"))ne1){
		if(auto me2=cast(BinaryExp!(Tok!"·"))ne2){
			static foreach(i;0..2){
				static foreach(j;0..2){{
					auto f1 = i ? me1.e1 : me1.e2;
					auto r1 = i ? me1.e2 : me1.e1;
					auto f2 = j ? me2.e1 : me2.e2;
					auto r2 = j ? me2.e2 : me2.e1;
					if(!cast(LiteralExp)f1 && f1.isDeterministic() && f1==f2 && soundCommonFactor!op(f1)){
						auto inner = make!op(loc, r1, r2);
						if(factorInnerOK!op(inner))
							return make!(Tok!"·")(loc, f1, inner);
					}
				}}
			}
		}
	}
	if(auto me1=cast(BinaryExp!(Tok!"·"))ne1){
		if(ne2.isDeterministic()){
			static foreach(i;0..2){{
				auto f1 = i ? me1.e1 : me1.e2;
				auto r1 = i ? me1.e2 : me1.e1;
				if(!cast(LiteralExp)f1 && f1==ne2 && soundCommonFactor!op(f1)){
					auto inner = make!op(loc, r1, make(1));
					if(factorInnerOK!op(inner))
						return make!(Tok!"·")(loc, inner, f1);
				}
			}}
		}
	}
	if(auto me2=cast(BinaryExp!(Tok!"·"))ne2){
		if(ne1.isDeterministic()){
			static foreach(j;0..2){{
				auto f2 = j ? me2.e1 : me2.e2;
				auto r2 = j ? me2.e2 : me2.e1;
				if(!cast(LiteralExp)f2 && f2==ne1 && soundCommonFactor!op(f2)){
					auto inner = make!op(loc, make(1), r2);
					if(factorInnerOK!op(inner))
						return make!(Tok!"·")(loc, inner, f2);
				}
			}}
		}
	}
	return null;
}

Expression evalNumericBinop(TokenType op)(Location loc, Expression ne1, Maybe!ℤ v1, Expression ne2, Maybe!ℤ v2) if(op == Tok!"=" || op == Tok!"≠") {
	if(v1 && v2) {
		return make((v1.get() == v2.get()) ^ (op != Tok!"="));
	}
	if(ne1.isDeterministic() && ne1 == ne2) {
		return make(op == Tok!"=");
	}
	if(cast(LiteralExp)ne1 && !cast(LiteralExp)ne2) {
		return make!op(loc, ne2, ne1);
	}
	if(!v2) {
		import ast.semantic_: subtractionType;
		if(subtractionType(ne1.type, ne2.type)) {
			return make!op(loc, make!(Tok!"-")(loc, ne1, ne2), make(0));
		}
	}
	return null;
}