government / eval / arith.go

@ 5c83a9c6b185121b6a79d1e44755763853b4b6d5 | history


package eval

import (
	"math"

	"government/sexpr"
)

// The numeric tower has two levels: Int below Float. An operation on two
// Ints gives an Int; if either operand is a Float, both are treated as
// Floats and so is the result. Each step of a fold is promoted separately,
// so (+ 1 2 3.0) adds 1 and 2 as Ints, then 3 and 3.0 as Floats.
//
// Results never wrap or go non-finite: integer overflow, division by zero
// and NaN or infinite floats are all errors.

type binaryOp struct {
	name   string
	ints   func(a, b int64) (int64, bool) // false on overflow
	floats func(a, b float64) float64
}

func add(args []sexpr.Value) (sexpr.Value, error) {
	return fold(opAdd, sexpr.Int(0), args)
}

func multiply(args []sexpr.Value) (sexpr.Value, error) {
	return fold(opMul, sexpr.Int(1), args)
}

// (- x) is 0 - x; with more arguments, - subtracts from the first.
func subtract(args []sexpr.Value) (sexpr.Value, error) {
	if len(args) == 1 {
		return foldFrom(opSub, sexpr.Int(0), args, 0)
	}
	return foldFrom(opSub, args[0], args[1:], 1)
}

// (/ x) is 1 / x; with more arguments, / divides the first by the rest.
func divide(args []sexpr.Value) (sexpr.Value, error) {
	if len(args) == 1 {
		return foldFrom(opDiv, sexpr.Int(1), args, 0)
	}
	return foldFrom(opDiv, args[0], args[1:], 1)
}

var (
	opAdd = binaryOp{"+", checkedAdd, func(a, b float64) float64 { return a + b }}
	opSub = binaryOp{"-", checkedSub, func(a, b float64) float64 { return a - b }}
	opMul = binaryOp{"*", checkedMul, func(a, b float64) float64 { return a * b }}
	opDiv = binaryOp{"/", checkedDiv, func(a, b float64) float64 { return a / b }}
)

func fold(op binaryOp, start sexpr.Value, args []sexpr.Value) (sexpr.Value, error) {
	return foldFrom(op, start, args, 0)
}

// foldFrom combines acc with each of args in turn. offset is the position
// of args[0] in the original call, so type errors name the right argument.
func foldFrom(op binaryOp, acc sexpr.Value, args []sexpr.Value, offset int) (sexpr.Value, error) {
	if offset == 1 {
		if err := checkNumber(op.name, 0, acc); err != nil {
			return nil, err
		}
	}
	for i, arg := range args {
		if err := checkNumber(op.name, offset+i, arg); err != nil {
			return nil, err
		}
		var err error
		if acc, err = applyBinary(op, acc, arg); err != nil {
			return nil, err
		}
	}
	return acc, nil
}

func applyBinary(op binaryOp, a, b sexpr.Value) (sexpr.Value, error) {
	ai, aIsInt := a.(sexpr.Int)
	bi, bIsInt := b.(sexpr.Int)
	if aIsInt && bIsInt {
		if op.name == "/" && bi == 0 {
			return nil, errorf(ErrArith, "division by zero")
		}
		r, ok := op.ints(int64(ai), int64(bi))
		if !ok {
			return nil, errorf(ErrArith, "integer overflow in %s", op.name)
		}
		return sexpr.Int(r), nil
	}

	af, bf := toFloat(a), toFloat(b)
	if op.name == "/" && bf == 0 {
		return nil, errorf(ErrArith, "division by zero")
	}
	r := op.floats(af, bf)
	if math.IsInf(r, 0) || math.IsNaN(r) {
		return nil, errorf(ErrArith, "float overflow in %s", op.name)
	}
	return sexpr.Float(r), nil
}

func checkNumber(fn string, position int, v sexpr.Value) error {
	switch v.(type) {
	case sexpr.Int, sexpr.Float:
		return nil
	}
	return errorf(ErrType, "argument %d of %s must be a number, got %s", position+1, fn, sexpr.Print(v))
}

func toFloat(v sexpr.Value) float64 {
	if i, ok := v.(sexpr.Int); ok {
		return float64(i)
	}
	return float64(v.(sexpr.Float))
}

// Overflow checks without a wider integer type. A signed sum overflows
// exactly when both operands have the same sign and the result's sign
// differs; the XOR expressions test that with the sign bit.

func checkedAdd(a, b int64) (int64, bool) {
	s := a + b
	return s, (a^s)&(b^s) >= 0
}

func checkedSub(a, b int64) (int64, bool) {
	d := a - b
	return d, (a^b)&(a^d) >= 0
}

func checkedMul(a, b int64) (int64, bool) {
	if a == 0 || b == 0 {
		return 0, true
	}
	if (a == -1 && b == math.MinInt64) || (b == -1 && a == math.MinInt64) {
		return 0, false
	}
	p := a * b
	return p, p/b == a
}

// Integer division truncates toward zero: (/ -7 2) is -3. The only
// overflowing case is MinInt64 / -1, whose true result is MaxInt64 + 1.
func checkedDiv(a, b int64) (int64, bool) {
	if a == math.MinInt64 && b == -1 {
		return 0, false
	}
	return a / b, true
}