summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBasVanDijk <>2018-05-06 23:51:00 (GMT)
committerhdiff <hdiff@hdiff.luite.com>2018-05-06 23:51:00 (GMT)
commitf6a0322dd85c259c8546f29356071ee0b1068661 (patch)
tree4f75bc06ee82fe79024d86ba23ed7e4ace89d64c
parent32e2f7cf0c2bdaffb6d11fd69e5b7eaf92b76504 (diff)
version 0.3.6.00.3.6.0
-rw-r--r--changelog38
-rw-r--r--scientific.cabal2
-rw-r--r--src/Data/Scientific.hs223
-rw-r--r--test/test.hs11
4 files changed, 198 insertions, 76 deletions
diff --git a/changelog b/changelog
index 2455076..df8564b 100644
--- a/changelog
+++ b/changelog
@@ -1,3 +1,41 @@
+0.3.6.0
+ * Make the methods of the Hashable, Eq and Ord instances safe to
+ use when applied to scientific numbers coming from untrusted
+ sources. Previously these methods first converted their arguments
+ to Rational before applying the operation. This is unsafe because
+ converting a Scientific to a Rational could fill up all space and
+ crash your program when the Scientific has a huge base10Exponent.
+
+ Do note that the hash computation of the Hashable Scientific
+ instance has been changed because of this improvement!
+
+ Thanks to Tom Sydney Kerckhove (@NorfairKing) for pushing me to
+ fix this.
+
+ * fromRational :: Rational -> Scientific now throws an error
+ instead of diverging when applied to a repeating decimal. This
+ does mean it will consume space linear in the number of digits of
+ the resulting scientific. This makes "fromRational" and the other
+ Fractional methods "recip" and "/" a bit safer to use.
+
+ * To get the old unsafe but more efficient behaviour the following
+ function was added: unsafeFromRational :: Rational -> Scientific.
+
+ * Add alternatives for fromRationalRepetend:
+
+ fromRationalRepetendLimited
+ :: Int -- ^ limit
+ -> Rational
+ -> Either (Scientific, Rational)
+ (Scientific, Maybe Int)
+
+ and:
+
+ fromRationalRepetendUnlimited
+ :: Rational -> (Scientific, Maybe Int)
+
+ Thanks to Ian Jeffries (@seagreen) for the idea.
+
0.3.5.3
* Dropped upper version bounds of dependencies
because it's to much work to maintain.
diff --git a/scientific.cabal b/scientific.cabal
index a82d1b6..35ee6e9 100644
--- a/scientific.cabal
+++ b/scientific.cabal
@@ -1,5 +1,5 @@
name: scientific
-version: 0.3.5.3
+version: 0.3.6.0
synopsis: Numbers represented using scientific notation
description:
"Data.Scientific" provides the number type 'Scientific'. Scientific numbers are
diff --git a/src/Data/Scientific.hs b/src/Data/Scientific.hs
index ff59971..6e6fb8f 100644
--- a/src/Data/Scientific.hs
+++ b/src/Data/Scientific.hs
@@ -22,6 +22,11 @@
-- aren't truly arbitrary precision. I intend to change the type of the exponent
-- to 'Integer' in a future release.
--
+-- /WARNING:/ Although @Scientific@ has instances for all numeric classes the
+-- methods should be used with caution when applied to scientific numbers coming
+-- from untrusted sources. See the warnings of the instances belonging to
+-- 'Scientific'.
+--
-- The main application of 'Scientific' is to be used as the target of parsing
-- arbitrary precision numbers coming from an untrusted source. The advantages
-- over using 'Rational' for this are that:
@@ -41,13 +46,6 @@
-- to @'Integral's@ (like: 'Int') or @'RealFloat's@ (like: 'Double' or 'Float')
-- will always be bounded by the target type.
--
--- /WARNING:/ Although @Scientific@ is an instance of 'Fractional', the methods
--- are only partially defined! Specifically 'recip' and '/' will diverge
--- (i.e. loop and consume all space) when their outputs have an infinite decimal
--- expansion. 'fromRational' will diverge when the input 'Rational' has an
--- infinite decimal expansion. Consider using 'fromRationalRepetend' for these
--- rationals which will detect the repetition and indicate where it starts.
---
-- This module is designed to be imported qualified:
--
-- @import Data.Scientific as Scientific@
@@ -66,8 +64,14 @@ module Data.Scientific
, isInteger
-- * Conversions
+ -- ** Rational
+ , unsafeFromRational
, fromRationalRepetend
+ , fromRationalRepetendLimited
+ , fromRationalRepetendUnlimited
, toRationalRepetend
+
+ -- ** Floating & integer
, floatingOrInteger
, toRealFloat
, toBoundedRealFloat
@@ -99,7 +103,6 @@ import Control.DeepSeq (NFData, rnf)
import Data.Binary (Binary, get, put)
import Data.Char (intToDigit, ord)
import Data.Data (Data)
-import Data.Function (on)
import Data.Hashable (Hashable(..))
import Data.Int (Int8, Int16, Int32, Int64)
import qualified Data.Map as M (Map, empty, insert, lookup)
@@ -174,42 +177,63 @@ scientific = Scientific
instance NFData Scientific where
rnf (Scientific _ _) = ()
+-- | A hash can be safely calculated from a @Scientific@. No magnitude @10^e@ is
+-- calculated so there's no risk of a blowup in space or time when hashing
+-- scientific numbers coming from untrusted sources.
instance Hashable Scientific where
- hashWithSalt salt = hashWithSalt salt . toRational
+ hashWithSalt salt s = salt `hashWithSalt` c `hashWithSalt` e
+ where
+ Scientific c e = normalize s
+-- | Note that in the future I intend to change the type of the 'base10Exponent'
+-- from @Int@ to @Integer@. To be forward compatible the @Binary@ instance
+-- already encodes the exponent as 'Integer'.
instance Binary Scientific where
- put (Scientific c e) = do
- put c
- -- In the future I intend to change the type of the base10Exponent e from
- -- Int to Integer. To support backward compatibility I already convert e
- -- to Integer here:
- put $ toInteger e
-
+ put (Scientific c e) = put c *> put (toInteger e)
get = Scientific <$> get <*> (fromInteger <$> get)
+-- | Scientific numbers can be safely compared for equality. No magnitude @10^e@
+-- is calculated so there's no risk of a blowup in space or time when comparing
+-- scientific numbers coming from untrusted sources.
instance Eq Scientific where
- (==) = (==) `on` toRational
- {-# INLINABLE (==) #-}
-
- (/=) = (/=) `on` toRational
- {-# INLINABLE (/=) #-}
+ s1 == s2 = c1 == c2 && e1 == e2
+ where
+ Scientific c1 e1 = normalize s1
+ Scientific c2 e2 = normalize s2
+-- | Scientific numbers can be safely compared for ordering. No magnitude @10^e@
+-- is calculated so there's no risk of a blowup in space or time when comparing
+-- scientific numbers coming from untrusted sources.
instance Ord Scientific where
- (<) = (<) `on` toRational
- {-# INLINABLE (<) #-}
-
- (<=) = (<=) `on` toRational
- {-# INLINABLE (<=) #-}
-
- (>) = (>) `on` toRational
- {-# INLINABLE (>) #-}
+ compare s1 s2
+ | c1 == c2 && e1 == e2 = EQ
+ | c1 < 0 = if c2 < 0 then cmp (-c2) e2 (-c1) e1 else LT
+ | c1 > 0 = if c2 > 0 then cmp c1 e1 c2 e2 else GT
+ | otherwise = if c2 > 0 then LT else GT
+ where
+ Scientific c1 e1 = normalize s1
+ Scientific c2 e2 = normalize s2
+
+ cmp cx ex cy ey
+ | log10sx < log10sy = LT
+ | log10sx > log10sy = GT
+ | d < 0 = if cx <= (cy `quotInteger` magnitude (-d)) then LT else GT
+ | d > 0 = if cy > (cx `quotInteger` magnitude d) then LT else GT
+ | otherwise = if cx < cy then LT else GT
+ where
+ log10sx = log10cx + ex
+ log10sy = log10cy + ey
- (>=) = (>=) `on` toRational
- {-# INLINABLE (>=) #-}
+ log10cx = integerLog10' cx
+ log10cy = integerLog10' cy
- compare = compare `on` toRational
- {-# INLINABLE compare #-}
+ d = log10cx - log10cy
+-- | /WARNING:/ '+' and '-' compute the 'Integer' magnitude: @10^e@ where @e@ is
+-- the difference between the @'base10Exponent's@ of the arguments. If these
+-- methods are applied to arguments which have huge exponents this could fill up
+-- all space and crash your program! So don't apply these methods to scientific
+-- numbers coming from untrusted sources. The other methods can be used safely.
instance Num Scientific where
Scientific c1 e1 + Scientific c2 e2
| e1 < e2 = Scientific (c1 + c2*l) e1
@@ -264,12 +288,12 @@ instance Real Scientific where
"realToFrac_toRealFloat_Float"
realToFrac = toRealFloat :: Scientific -> Float #-}
--- | /WARNING:/ 'recip' and '/' will diverge (i.e. loop and consume all space)
--- when their outputs are <https://en.wikipedia.org/wiki/Repeating_decimal repeating decimals>.
+-- | /WARNING:/ 'recip' and '/' will throw an error when their outputs are
+-- <https://en.wikipedia.org/wiki/Repeating_decimal repeating decimals>.
--
--- 'fromRational' will diverge when the input 'Rational' is a repeating decimal.
--- Consider using 'fromRationalRepetend' for these rationals which will detect
--- the repetition and indicate where it starts.
+-- 'fromRational' will throw an error when the input 'Rational' is a repeating
+-- decimal. Consider using 'fromRationalRepetend' for these rationals which
+-- will detect the repetition and indicate where it starts.
instance Fractional Scientific where
recip = fromRational . recip . toRational
{-# INLINABLE recip #-}
@@ -277,23 +301,45 @@ instance Fractional Scientific where
x / y = fromRational $ toRational x / toRational y
{-# INLINABLE (/) #-}
- fromRational rational
- | d == 0 = throw DivideByZero
- | otherwise = positivize (longDiv 0 0) (numerator rational)
+ fromRational rational =
+ case mbRepetendIx of
+ Nothing -> s
+ Just _ix -> error $
+ "fromRational has been applied to a repeating decimal " ++
+ "which can't be represented as a Scientific! " ++
+ "It's better to avoid performing fractional operations on Scientifics " ++
+ "and convert them to other fractional types like Double as early as possible."
where
- -- Divide the numerator by the denominator using long division.
- longDiv :: Integer -> Int -> (Integer -> Scientific)
- longDiv !c !e 0 = Scientific c e
- longDiv !c !e !n
- -- TODO: Use a logarithm here!
- | n < d = longDiv (c * 10) (e - 1) (n * 10)
- | otherwise = case n `quotRemInteger` d of
- (#q, r#) -> longDiv (c + q) e r
-
- d = denominator rational
-
--- | Like 'fromRational', this function converts a `Rational` to a `Scientific`
--- but instead of diverging (i.e loop and consume all space) on
+ (s, mbRepetendIx) = fromRationalRepetendUnlimited rational
+
+-- | Although 'fromRational' is unsafe because it will throw errors on
+-- <https://en.wikipedia.org/wiki/Repeating_decimal repeating decimals>,
+-- @unsafeFromRational@ is even more unsafe because it will diverge instead (i.e
+-- loop and consume all space). Though it will be more efficient because it
+-- doesn't need to consume space linear in the number of digits in the resulting
+-- scientific to detect the repetition.
+--
+-- Consider using 'fromRationalRepetend' for these rationals which will detect
+-- the repetition and indicate where it starts.
+unsafeFromRational :: Rational -> Scientific
+unsafeFromRational rational
+ | d == 0 = throw DivideByZero
+ | otherwise = positivize (longDiv 0 0) (numerator rational)
+ where
+ -- Divide the numerator by the denominator using long division.
+ longDiv :: Integer -> Int -> (Integer -> Scientific)
+ longDiv !c !e 0 = Scientific c e
+ longDiv !c !e !n
+ -- TODO: Use a logarithm here!
+ | n < d = longDiv (c * 10) (e - 1) (n * 10)
+ | otherwise = case n `quotRemInteger` d of
+ (#q, r#) -> longDiv (c + q) e r
+
+ d = denominator rational
+
+-- | Like 'fromRational' and 'unsafeFromRational', this function converts a
+-- `Rational` to a `Scientific` but instead of failing or diverging (i.e loop
+-- and consume all space) on
-- <https://en.wikipedia.org/wiki/Repeating_decimal repeating decimals>
-- it detects the repeating part, the /repetend/, and returns where it starts.
--
@@ -335,7 +381,18 @@ fromRationalRepetend
-> Rational
-> Either (Scientific, Rational)
(Scientific, Maybe Int)
-fromRationalRepetend mbLimit rational
+fromRationalRepetend mbLimit rational =
+ case mbLimit of
+ Nothing -> Right $ fromRationalRepetendUnlimited rational
+ Just l -> fromRationalRepetendLimited l rational
+
+-- | Like 'fromRationalRepetend' but always accepts a limit.
+fromRationalRepetendLimited
+ :: Int -- ^ limit
+ -> Rational
+ -> Either (Scientific, Rational)
+ (Scientific, Maybe Int)
+fromRationalRepetendLimited l rational
| d == 0 = throw DivideByZero
| num < 0 = case longDiv (-num) of
Left (s, r) -> Left (-s, -r)
@@ -345,11 +402,38 @@ fromRationalRepetend mbLimit rational
num = numerator rational
longDiv :: Integer -> Either (Scientific, Rational) (Scientific, Maybe Int)
- longDiv n = case mbLimit of
- Nothing -> Right $ longDivNoLimit 0 0 M.empty n
- Just l -> longDivWithLimit (-l) n
+ longDiv = longDivWithLimit 0 0 M.empty
+
+ longDivWithLimit
+ :: Integer
+ -> Int
+ -> M.Map Integer Int
+ -> (Integer -> Either (Scientific, Rational)
+ (Scientific, Maybe Int))
+ longDivWithLimit !c !e _ns 0 = Right (Scientific c e, Nothing)
+ longDivWithLimit !c !e ns !n
+ | Just e' <- M.lookup n ns = Right (Scientific c e, Just (-e'))
+ | e <= (-l) = Left (Scientific c e, n % (d * magnitude (-e)))
+ | n < d = let !ns' = M.insert n e ns
+ in longDivWithLimit (c * 10) (e - 1) ns' (n * 10)
+ | otherwise = case n `quotRemInteger` d of
+ (#q, r#) -> longDivWithLimit (c + q) e ns r
+
+ d = denominator rational
+
+-- | Like 'fromRationalRepetend' but doesn't accept a limit.
+fromRationalRepetendUnlimited :: Rational -> (Scientific, Maybe Int)
+fromRationalRepetendUnlimited rational
+ | d == 0 = throw DivideByZero
+ | num < 0 = case longDiv (-num) of
+ (s, mb) -> (-s, mb)
+ | otherwise = longDiv num
+ where
+ num = numerator rational
+
+ longDiv :: Integer -> (Scientific, Maybe Int)
+ longDiv = longDivNoLimit 0 0 M.empty
- -- Divide the numerator by the denominator using long division.
longDivNoLimit :: Integer
-> Int
-> M.Map Integer Int
@@ -362,22 +446,6 @@ fromRationalRepetend mbLimit rational
| otherwise = case n `quotRemInteger` d of
(#q, r#) -> longDivNoLimit (c + q) e ns r
- longDivWithLimit :: Int -> Integer -> Either (Scientific, Rational) (Scientific, Maybe Int)
- longDivWithLimit l = go 0 0 M.empty
- where
- go :: Integer
- -> Int
- -> M.Map Integer Int
- -> (Integer -> Either (Scientific, Rational) (Scientific, Maybe Int))
- go !c !e _ns 0 = Right (Scientific c e, Nothing)
- go !c !e ns !n
- | Just e' <- M.lookup n ns = Right (Scientific c e, Just (-e'))
- | e <= l = Left (Scientific c e, n % (d * magnitude (-e)))
- | n < d = let !ns' = M.insert n e ns
- in go (c * 10) (e - 1) ns' (n * 10)
- | otherwise = case n `quotRemInteger` d of
- (#q, r#) -> go (c + q) e ns r
-
d = denominator rational
-- |
@@ -443,6 +511,10 @@ toRationalRepetend s r
nines = m - 1
+-- | /WARNING:/ the methods of the @RealFrac@ instance need to compute the
+-- magnitude @10^e@. If applied to a huge exponent this could take a long
+-- time. Even worse, when the destination type is unbounded (i.e. 'Integer') it
+-- could fill up all space and crash your program!
instance RealFrac Scientific where
-- | The function 'properFraction' takes a Scientific number @s@
-- and returns a pair @(n,f)@ such that @s = n+f@, and:
@@ -885,6 +957,7 @@ isE c = c == 'e' || c == 'E'
-- Pretty Printing
----------------------------------------------------------------------
+-- | See 'formatScientific' if you need more control over the rendering.
instance Show Scientific where
show s | coefficient s < 0 = '-':showPositive (-s)
| otherwise = showPositive s
diff --git a/test/test.hs b/test/test.hs
index 990fa34..72eff5d 100644
--- a/test/test.hs
+++ b/test/test.hs
@@ -97,6 +97,17 @@ main = testMain $ testGroup "scientific"
-- show d
]
+ , testGroup "Eq"
+ [ testProperty "==" $ \(s1 :: Scientific) (s2 :: Scientific) ->
+ (s1 == s2) == (toRational s1 == toRational s2)
+ , testProperty "s == s" $ \(s :: Scientific) -> s == s
+ ]
+
+ , testGroup "Ord"
+ [ testProperty "compare" $ \(s1 :: Scientific) (s2 :: Scientific) ->
+ compare s1 s2 == compare (toRational s1) (toRational s2)
+ ]
+
, testGroup "Num"
[ testGroup "Equal to Rational"
[ testProperty "fromInteger" $ \i -> fromInteger i === fromRational (fromInteger i)