government / src / eval / compare.go

@ 72c20a953a72bec361bd6d0c25c9d0133e8bf1bd | history


package eval

import (
	"math"

	"government/sexpr"
)

func less(args []sexpr.Value) (sexpr.Value, error) {
	return order("<", args, func(c int) bool { return c < 0 })
}
func greater(args []sexpr.Value) (sexpr.Value, error) {
	return order(">", args, func(c int) bool { return c > 0 })
}
func lessEq(args []sexpr.Value) (sexpr.Value, error) {
	return order("<=", args, func(c int) bool { return c <= 0 })
}
func greaterEq(args []sexpr.Value) (sexpr.Value, error) {
	return order(">=", args, func(c int) bool { return c >= 0 })
}

func order(name string, args []sexpr.Value, holds func(cmp int) bool) (sexpr.Value, error) {
	for i, a := range args {
		if err := checkNumber(name, i, a); err != nil {
			return nil, err
		}
	}
	return sexpr.Bool(holds(compareNumbers(args[0], args[1]))), nil
}

func equal(args []sexpr.Value) (sexpr.Value, error) {
	eq, err := valuesEqual(args[0], args[1])
	return sexpr.Bool(eq), err
}

func notEqual(args []sexpr.Value) (sexpr.Value, error) {
	eq, err := valuesEqual(args[0], args[1])
	return sexpr.Bool(!eq), err
}

func not(args []sexpr.Value) (sexpr.Value, error) {
	return sexpr.Bool(!isTrue(args[0])), nil
}

// valuesEqual is structural equality. Numbers compare by numeric value
// across Int and Float, other atoms by value, pairs element by element.
// Values of different kinds are unequal, so (== 1 "1") is F.
//
// Functions cannot be compared: closure equality would need either identity
// (two identical lambdas unequal) or deciding whether two programs compute
// the same thing (impossible), and neither is worth exposing.
func valuesEqual(a, b sexpr.Value) (bool, error) {
	for {
		if _, ok := a.(sexpr.Function); ok {
			return false, errorf(ErrType, "cannot compare functions")
		}
		if _, ok := b.(sexpr.Function); ok {
			return false, errorf(ErrType, "cannot compare functions")
		}
		pa, aIsPair := a.(*sexpr.Pair)
		pb, bIsPair := b.(*sexpr.Pair)
		if !aIsPair || !bIsPair {
			return atomsEqual(a, b), nil
		}
		// Recurse into the cars, loop along the cdrs, so long lists use
		// constant stack.
		eq, err := valuesEqual(pa.Car, pb.Car)
		if err != nil || !eq {
			return false, err
		}
		a, b = pa.Cdr, pb.Cdr
	}
}

func atomsEqual(a, b sexpr.Value) bool {
	if isNumber(a) && isNumber(b) {
		return compareNumbers(a, b) == 0
	}
	return a == b
}

func isNumber(v sexpr.Value) bool {
	switch v.(type) {
	case sexpr.Int, sexpr.Float:
		return true
	}
	return false
}

// compareNumbers returns -1, 0 or 1. It is exact across Int and Float:
// converting a large Int to float64 can round it (2^53 + 1 becomes 2^53),
// so mixed comparisons go through compareIntFloat instead.
func compareNumbers(a, b sexpr.Value) int {
	switch a := a.(type) {
	case sexpr.Int:
		switch b := b.(type) {
		case sexpr.Int:
			return cmp(a, b)
		case sexpr.Float:
			return compareIntFloat(int64(a), float64(b))
		}
	case sexpr.Float:
		switch b := b.(type) {
		case sexpr.Int:
			return -compareIntFloat(int64(b), float64(a))
		case sexpr.Float:
			return cmp(a, b)
		}
	}
	panic("eval: compareNumbers on non-numbers")
}

// compareIntFloat compares exactly by splitting f into its integer part,
// which is compared as an int64, and its fraction, which breaks ties.
func compareIntFloat(i int64, f float64) int {
	const two63 = 9223372036854775808.0 // 2^63, exactly representable
	switch {
	case f >= two63:
		return -1
	case f < -two63:
		return 1
	}
	whole := math.Trunc(f)
	if c := cmp(i, int64(whole)); c != 0 {
		return c
	}
	return cmp(0, f-whole)
}

func cmp[T int64 | sexpr.Int | sexpr.Float | float64](a, b T) int {
	switch {
	case a < b:
		return -1
	case a > b:
		return 1
	}
	return 0
}