math/big: accept non-decimal floats with Rat.SetString

This fixes an old oversight. Rat.SetString already permitted
fractions a/b where both a and b could independently specify
a base prefix. With this CL, it now also accepts non-decimal
floating-point numbers.

Fixes #29799.

Change-Id: I9cc65666a5cebb00f0202da2e4fc5654a02e3234
Reviewed-on: https://go-review.googlesource.com/c/go/+/168237
Reviewed-by: Emmanuel Odeke <emm.odeke@gmail.com>

4 files changed, 133 insertions, 38 deletions

diff --git a/src/math/big/floatconv.go b/src/math/big/floatconv.go
index 88216f5600..95e32d3319 100644
--- a/src/math/big/floatconv.go
+++ b/src/math/big/floatconv.go
@@ -70,8 +70,8 @@ func (z *Float) scan(r io.ByteScanner, base int) (f *Float, b int, err error) {
 	}
 	// len(z.mant) > 0
 
-	// The mantissa may have a decimal point (fcount <= 0) and there
-	// may be a nonzero exponent exp. The decimal point amounts to a
+	// The mantissa may have a radix point (fcount <= 0) and there
+	// may be a nonzero exponent exp. The radix point amounts to a
 	// division by b**(-fcount). An exponent means multiplication by
 	// ebase**exp. Finally, mantissa normalization (shift left) requires
 	// a correcting multiplication by 2**(-shiftcount). Multiplications
@@ -85,11 +85,11 @@ func (z *Float) scan(r io.ByteScanner, base int) (f *Float, b int, err error) {
 	exp2 := int64(len(z.mant))*_W - fnorm(z.mant)
 	exp5 := int64(0)
 
-	// determine binary or decimal exponent contribution of decimal point
+	// determine binary or decimal exponent contribution of radix point
 	if fcount < 0 {
-		// The mantissa has a "decimal" point ddd.dddd; and
-		// -fcount is the number of digits to the right of '.'.
-		// Adjust relevant exponent accordingly.
+		// The mantissa has a radix point ddd.dddd; and
+		// -fcount is the number of digits to the right
+		// of '.'. Adjust relevant exponent accordingly.
 		d := int64(fcount)
 		switch b {
 		case 10:
@@ -111,7 +111,7 @@ func (z *Float) scan(r io.ByteScanner, base int) (f *Float, b int, err error) {
 	switch ebase {
 	case 10:
 		exp5 += exp
-		fallthrough
+		fallthrough // see fallthrough above
 	case 2:
 		exp2 += exp
 	default:
diff --git a/src/math/big/nat.go b/src/math/big/nat.go
index 336633a2fa..22d7a6cac0 100644
--- a/src/math/big/nat.go
+++ b/src/math/big/nat.go
@@ -35,9 +35,10 @@ import (
 type nat []Word
 
 var (
-	natOne = nat{1}
-	natTwo = nat{2}
-	natTen = nat{10}
+	natOne  = nat{1}
+	natTwo  = nat{2}
+	natFive = nat{5}
+	natTen  = nat{10}
 )
 
 func (z nat) clear() {
diff --git a/src/math/big/ratconv.go b/src/math/big/ratconv.go
index 07288ca94f..3ea03d5c61 100644
--- a/src/math/big/ratconv.go
+++ b/src/math/big/ratconv.go
@@ -38,10 +38,22 @@ func (z *Rat) Scan(s fmt.ScanState, ch rune) error {
 }
 
 // SetString sets z to the value of s and returns z and a boolean indicating
-// success. s can be given as a fraction "a/b" or as a decimal floating-point
-// number optionally followed by an exponent. The entire string (not just a prefix)
-// must be valid for success. If the operation failed, the value of z is
-// undefined but the returned value is nil.
+// success. s can be given as a (possibly signed) fraction "a/b", or as a
+// floating-point number optionally followed by an exponent.
+// If a fraction is provided, both the dividend and the divisor may be a
+// decimal integer or independently use a prefix of ``0b'', ``0'' or ``0o'',
+// or ``0x'' (or their upper-case variants) to denote a binary, octal, or
+// hexadecimal integer, respectively. The divisor may not be signed.
+// If a floating-point number is provided, it may be in decimal form or
+// use any of the same prefixes as above but for ``0'' to denote a non-decimal
+// mantissa. A leading ``0'' is considered a decimal leading 0; it does not
+// indicate octal representation in this case.
+// An optional base-10 ``e'' or base-2 ``p'' (or their upper-case variants)
+// exponent may be provided as well, except for hexadecimal floats which
+// only accept an (optional) ``p'' exponent (because an ``e'' or ``E'' cannot
+// be distinguished from a mantissa digit).
+// The entire string, not just a prefix, must be valid for success. If the
+// operation failed, the value of z is undefined but the returned value is nil.
 func (z *Rat) SetString(s string) (*Rat, bool) {
 	if len(s) == 0 {
 		return nil, false
@@ -78,16 +90,17 @@ func (z *Rat) SetString(s string) (*Rat, bool) {
 	}
 
 	// mantissa
-	// TODO(gri) allow other bases besides 10 for mantissa and exponent? (issue #29799)
-	var ecorr int
-	z.a.abs, _, ecorr, err = z.a.abs.scan(r, 10, true)
+	var base int
+	var fcount int // fractional digit count; valid if <= 0
+	z.a.abs, base, fcount, err = z.a.abs.scan(r, 0, true)
 	if err != nil {
 		return nil, false
 	}
 
 	// exponent
 	var exp int64
-	exp, _, err = scanExponent(r, false, false)
+	var ebase int
+	exp, ebase, err = scanExponent(r, true, true)
 	if err != nil {
 		return nil, false
 	}
@@ -103,30 +116,91 @@ func (z *Rat) SetString(s string) (*Rat, bool) {
 	}
 	// len(z.a.abs) > 0
 
-	// correct exponent
-	if ecorr < 0 {
-		exp += int64(ecorr)
+	// The mantissa may have a radix point (fcount <= 0) and there
+	// may be a nonzero exponent exp. The radix point amounts to a
+	// division by base**(-fcount), which equals a multiplication by
+	// base**fcount. An exponent means multiplication by ebase**exp.
+	// Multiplications are commutative, so we can apply them in any
+	// order. We only have powers of 2 and 10, and we split powers
+	// of 10 into the product of the same powers of 2 and 5. This
+	// may reduce the the size of shift/multiplication factors or
+	// divisors required to create the final fraction, depending
+	// on the actual floating-point value.
+
+	// determine binary or decimal exponent contribution of radix point
+	var exp2, exp5 int64
+	if fcount < 0 {
+		// The mantissa has a radix point ddd.dddd; and
+		// -fcount is the number of digits to the right
+		// of '.'. Adjust relevant exponent accordingly.
+		d := int64(fcount)
+		switch base {
+		case 10:
+			exp5 = d
+			fallthrough // 10**e == 5**e * 2**e
+		case 2:
+			exp2 = d
+		case 8:
+			exp2 = d * 3 // octal digits are 3 bits each
+		case 16:
+			exp2 = d * 4 // hexadecimal digits are 4 bits each
+		default:
+			panic("unexpected mantissa base")
+		}
+		// fcount consumed - not needed anymore
 	}
 
-	// compute exponent power
-	expabs := exp
-	if expabs < 0 {
-		expabs = -expabs
+	// take actual exponent into account
+	switch ebase {
+	case 10:
+		exp5 += exp
+		fallthrough // see fallthrough above
+	case 2:
+		exp2 += exp
+	default:
+		panic("unexpected exponent base")
 	}
-	powTen := nat(nil).expNN(natTen, nat(nil).setWord(Word(expabs)), nil)
+	// exp consumed - not needed anymore
 
-	// complete fraction
-	if exp < 0 {
-		z.b.abs = powTen
-		z.norm()
-	} else {
-		z.a.abs = z.a.abs.mul(z.a.abs, powTen)
-		z.b.abs = z.b.abs[:0]
+	// compute pow5 if needed
+	pow5 := z.b.abs
+	if exp5 != 0 {
+		n := exp5
+		if n < 0 {
+			n = -n
+		}
+		pow5 = pow5.expNN(natFive, nat(nil).setWord(Word(n)), nil)
+	}
+
+	// apply dividend contributions of exponents
+	// (start with exp5 so the numbers to multiply are smaller)
+	if exp5 > 0 {
+		z.a.abs = z.a.abs.mul(z.a.abs, pow5)
+		exp5 = 0
+	}
+	if exp2 > 0 {
+		if int64(uint(exp2)) != exp2 {
+			panic("exponent too large")
+		}
+		z.a.abs = z.a.abs.shl(z.a.abs, uint(exp2))
+		exp2 = 0
+	}
+
+	// apply divisor contributions of exponents
+	z.b.abs = z.b.abs.setWord(1)
+	if exp5 < 0 {
+		z.b.abs = pow5
+	}
+	if exp2 < 0 {
+		if int64(uint(-exp2)) != -exp2 {
+			panic("exponent too large")
+		}
+		z.b.abs = z.b.abs.shl(z.b.abs, uint(-exp2))
 	}
 
 	z.a.neg = neg && len(z.a.abs) > 0 // 0 has no sign
 
-	return z, true
+	return z.norm(), true
 }
 
 // scanExponent scans the longest possible prefix of r representing a base 10
@@ -250,7 +324,7 @@ func (x *Rat) RatString() string {
 }
 
 // FloatString returns a string representation of x in decimal form with prec
-// digits of precision after the decimal point. The last digit is rounded to
+// digits of precision after the radix point. The last digit is rounded to
 // nearest, with halves rounded away from zero.
 func (x *Rat) FloatString(prec int) string {
 	var buf []byte
diff --git a/src/math/big/ratconv_test.go b/src/math/big/ratconv_test.go
index dea4d1933a..87ee9fa972 100644
--- a/src/math/big/ratconv_test.go
+++ b/src/math/big/ratconv_test.go
@@ -135,29 +135,49 @@ var setStringTests = []StringTest{
 var setStringTests2 = []StringTest{
 	// invalid
 	{in: "4/3x"},
+	{in: "0/-1"},
+	{in: "-1/-1"},
 
 	// invalid with separators
 	// (smoke tests only - a comprehensive set of tests is in natconv_test.go)
 	{in: "10_/1"},
 	{in: "_10/1"},
 	{in: "1/1__0"},
-	{in: "1_000.0"}, // floats are base 10 which doesn't permit separators; see also issue #29799
 
 	// valid
 	{"0b1000/3", "8/3", true},
 	{"0B1000/0x8", "1", true},
-	{"-010/1", "-8", true},
-	{"-010.", "-10", true},
+	{"-010/1", "-8", true}, // 0-prefix indicates octal in this case
+	{"-010.0", "-10", true},
 	{"-0o10/1", "-8", true},
 	{"0x10/1", "16", true},
 	{"0x10/0x20", "1/2", true},
 
+	{"0010", "10", true}, // 0-prefix is ignored in this case (not a fraction)
+	{"0x10.0", "16", true},
+	{"0x1.8", "3/2", true},
+	{"0X1.8p4", "24", true},
+	{"0x1.1E2", "2289/2048", true}, // E is part of hex mantissa, not exponent
+	{"0b1.1E2", "150", true},
+	{"0B1.1P3", "12", true},
+	{"0o10e-2", "2/25", true},
+	{"0O10p-3", "1", true},
+
 	// valid with separators
 	// (smoke tests only - a comprehensive set of tests is in natconv_test.go)
 	{"0b_1000/3", "8/3", true},
 	{"0B_10_00/0x8", "1", true},
 	{"0xdead/0B1101_1110_1010_1101", "1", true},
 	{"0B1101_1110_1010_1101/0XD_E_A_D", "1", true},
+	{"1_000.0", "1000", true},
+
+	{"0x_10.0", "16", true},
+	{"0x1_0.0", "16", true},
+	{"0x1.8_0", "3/2", true},
+	{"0X1.8p0_4", "24", true},
+	{"0b1.1_0E2", "150", true},
+	{"0o1_0e-2", "2/25", true},
+	{"0O_10p-3", "1", true},
 }
 
 func TestRatSetString(t *testing.T) {