changeset 93:c85711f38392

Updated testcases * Support for negatives A full range now goes from -(p//2) to p//2. * (Bottom(), Bottom()) => Bottom() (a, Bottom()) makes no sense, when we have lost control of one bound we can no more depend on the other one (because of wrapping) Maybe we should represent Bottom() with full_range, as that too indicates complete lack of knowledge
author Sigurd Meldgaard <stm@daimi.au.dk>
date Mon, 08 Jun 2009 12:29:02 +0200
parents fa10cecde7a7
children 28adf540a9ba
files pysmcl/test/unit/test_rangeanalysis.py
diffstat 1 files changed, 95 insertions(+), 86 deletions(-) [+]
line wrap: on
line diff
--- a/pysmcl/test/unit/test_rangeanalysis.py	Mon Jun 08 12:22:20 2009 +0200
+++ b/pysmcl/test/unit/test_rangeanalysis.py	Mon Jun 08 12:29:02 2009 +0200
@@ -1,43 +1,40 @@
-
-import sys
 import unittest
 
 from ast import *
-from pysmcl.range_analysis import RangeAnalysis, Bottom
+from pysmcl.range_analysis import RangeAnalysis, Bottom, full_range
 
-from pysmcl.flow import Flow
-from pysmcl.graph import Graph
 
 class RangeAnalysisTest(unittest.TestCase):
 
-
     def test_range_one_range(self):
-        p = 7
+        p = 13
         prog = parse("def f():\n\ty=0\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
 #         for node in prog.body[0].body:
 #             print "Result...:", node.out_values["range"]
 
-        self.assertEquals(prog.body[0].body[0].out_values["range"], {'y': (0, 0)})
+        self.assertEquals(prog.body[0].body[0].out_values["range"],
+                          {'y': (0, 0)})
 
     def test_range_too_large_constant(self):
-        p = 7
+        p = 13
         prog = parse("def f():\n\ty=8\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
-        self.assertEquals(prog.body[0].body[0].out_values["range"], {'y': (Bottom(), Bottom())})
+        self.assertEquals(prog.body[0].body[0].out_values["range"],
+                          {'y': Bottom()})
 
     def test_range_unknown_range(self):
-        p = 7
-        prog = parse("def f(x):\n\tx\n")
+        p = 13
+        prog = parse("def f(x):\n\ty=x\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[0].out_values["range"]
-        self.assertEquals(r, {'x': (0, p), '_': (0, p)})
+        self.assertEquals(r, {'x': full_range(p), 'y': full_range(p)})
 
     def test_range_add(self):
-        p = 7
+        p = 13
         prog = parse("def f(x):\n\tx=3\n\ty=2\n\tz=x+y\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
@@ -45,41 +42,57 @@
         self.assertEquals(r, {'y': (2, 2), 'x': (3, 3), 'z': (5, 5)})
 
     def test_range_add_wrap(self):
-        p = 7
+        p = 13
         prog = parse("def f(x):\n\tx=6\n\ty=2\n\tz=x+y\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[2].out_values["range"]
-        self.assertEquals(r, {'y': (2, 2), 'x': (6, 6), 'z': (Bottom(), Bottom())})
+        self.assertEquals(r, {'y': (2, 2), 'x': (6, 6), 'z': Bottom()})
 
     def test_range_add_bottom(self):
-        p = 7
+        p = 13
         prog = parse("def f(x):\n\tx=6\n\ty=8\n\tz=x+y\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[2].out_values["range"]
-        self.assertEquals(r, {'y': (Bottom(), Bottom()), 'x': (6, 6), 'z': (Bottom(), Bottom())})
+        self.assertEquals(r, {'y': Bottom(), 'x': (6, 6), 'z': Bottom()})
 
     def test_range_add_top_bottom(self):
-        p = 7
+        p = 13
+        prog = parse(
+"""
+def f(x):
+    x=1
+    y=4
+    if y:
+         y=y+2
+    else: y=y+0
+    y=y+1
+""")
+        range_analysis = RangeAnalysis(p)
+        range_analysis.apply(prog.body[0])
+        r = prog.body[0].body[-1].out_values["range"]
+        self.assertEquals(r, {'x': (1, 1), 'y': Bottom()})
+
+    def test_range_add_top_bottom2(self):
+        p = 13
         prog = parse(
 """
 def f(x):
     x=1
     y=4
     if x:
-         y=y+3
+         y=y+2
     y=y+1
-    z=x+y
 """)
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[-1].out_values["range"]
-        self.assertEquals(r, {'x': (1, 1), 'y': (5, Bottom()), 'z': (6, Bottom())})
-
+        print prog.body[0].body[-1]
+        self.assertEquals(r, {'x': (1, 1), 'y': Bottom()})
 
     def test_range_mul(self):
-        p = 7
+        p = 13
         prog = parse("def f(x):\n\tx=3\n\ty=2\n\tz=x*y\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
@@ -87,15 +100,15 @@
         self.assertEquals(r, {'y': (2, 2), 'x': (3, 3), 'z': (6, 6)})
 
     def test_range_mul_wrap(self):
-        p = 7
+        p = 13
         prog = parse("def f(x):\n\tx=3\n\ty=3\n\tz=x*y\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[2].out_values["range"]
-        self.assertEquals(r, {'y': (3, 3), 'x': (3, 3), 'z': (Bottom(), Bottom())})
+        self.assertEquals(r, {'y': (3, 3), 'x': (3, 3), 'z': Bottom()})
 
     def test_range_mult_bottom(self):
-        p = 7
+        p = 13
         prog = parse(
 """
 def f(x):
@@ -108,10 +121,10 @@
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[-1].out_values["range"]
-        self.assertEquals(r, {'x': (2, 2), 'y': (2, 5), 'z': (4, Bottom())})
+        self.assertEquals(r, {'x': (2, 2), 'y': (2, 5), 'z': Bottom()})
 
     def test_range_mult_top_bottom(self):
-        p = 7
+        p = 13
         prog = parse(
 """
 def f(x):
@@ -119,17 +132,15 @@
     y=1
     if x:
          y=y+6
-    y=y+1
     z=x*y
 """)
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[-1].out_values["range"]
-        self.assertEquals(r, {'x': (2, 2), 'y': (2, Bottom()), 'z': (4, Bottom())})
-
+        self.assertEquals(r, {'x': (2, 2), 'y': Bottom(), 'z': Bottom()})
 
     def test_range_minus(self):
-        p = 7
+        p = 13
         prog = parse(
 """
 def f(x):
@@ -141,43 +152,51 @@
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[-1].out_values["range"]
-        self.assertEquals(r, {'a': (3, 4), 'x': (0, p), 'z': (1, 3)})
+        self.assertEquals(r, {'a': (3, 4), 'x': full_range(p), 'z': (1, 3)})
 
-    def test_range_minus_wrap(self):
-        p = 7
+    def test_range_minus_negative(self):
+        p = 13
         prog = parse("def f(x):\n\tx=3\n\ty=4\n\tz=x-y\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[2].out_values["range"]
-        self.assertEquals(r, {'y': (4, 4), 'x': (3, 3), 'z': (Bottom(), Bottom())})
+        self.assertEquals(r, {'y': (4, 4), 'x': (3, 3), 'z': (-1, -1)})
+
+    def test_range_minus_wrap(self):
+        p = 13
+        prog = parse("def f(x):\n\tx=-2\n\ty=-5\n\tz=x+y\n")
+        range_analysis = RangeAnalysis(p)
+        range_analysis.apply(prog.body[0])
+        r = prog.body[0].body[2].out_values["range"]
+        self.assertEquals(r, {'x': (-2, -2), 'y': (-5, -5), 'z': Bottom()})
 
     def test_range_minus_bottom(self):
-        p = 7
+        p = 13
         prog = parse("def f(x):\n\tx=6\n\ty=8\n\tz=x-y\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[2].out_values["range"]
-        self.assertEquals(r, {'y': (Bottom(), Bottom()), 'x': (6, 6), 'z': (Bottom(), Bottom())})
+        self.assertEquals(r, {'y': Bottom(), 'x': (6, 6), 'z': Bottom()})
 
     def test_range_minus_bottom_bottom(self):
-        p = 7
+        p = 13
         prog = parse(
 """
 def f(x):
     x=1
-    y=3
+    y=0
     if x:
          y=y-3
-    y=y-2
+    y=y-4
     z=y-x
 """)
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[-1].out_values["range"]
-        self.assertEquals(r, {'x': (1, 1), 'y': (Bottom(), 1), 'z': (Bottom(), 0)})
+        self.assertEquals(r, {'x': (1, 1), 'y': Bottom(), 'z': Bottom()})
 
     def test_range_equals(self):
-        p = 7
+        p = 13
         prog = parse("def f(x):\n\tx=3\n\ty=2\n\tz=x==y\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
@@ -185,7 +204,7 @@
         self.assertEquals(r, {'y': (2, 2), 'x': (3, 3), 'z': (0, 1)})
 
     def test_range_leg(self):
-        p = 7
+        p = 13
         prog = parse("def f(x):\n\tx=3\n\ty=2\n\tz=x<=y\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
@@ -193,7 +212,7 @@
         self.assertEquals(r, {'y': (2, 2), 'x': (3, 3), 'z': (0, 1)})
 
     def test_range_geg(self):
-        p = 7
+        p = 13
         prog = parse("def f(x):\n\tx=3\n\ty=2\n\tz=x>=y\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
@@ -201,7 +220,7 @@
         self.assertEquals(r, {'y': (2, 2), 'x': (3, 3), 'z': (0, 1)})
 
     def test_range_multiple_compare(self):
-        p = 7
+        p = 13
         prog = parse("def f(x):\n\tx=3\n\ty=2\n\tz=x>y<=42\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
@@ -209,15 +228,15 @@
         self.assertEquals(r, {'y': (2, 2), 'x': (3, 3), 'z': (0, 1)})
 
     def test_range_random(self):
-        p = 7
+        p = 13
         prog = parse("def f():\n\tx=random()\n")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[0].out_values["range"]
-        self.assertEquals(r, {'x': (0, p - 1)})
+        self.assertEquals(r, {'x': full_range(p)})
 
     def test_range_random_bit(self):
-        p = 7
+        p = 13
         prog = parse("def f(x):\n\tx=random_bit()")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
@@ -225,15 +244,15 @@
         self.assertEquals(r, {'x': (0, 1)})
 
     def test_range_global_variable(self):
-        p = 7
-        prog = parse("def f():\n\tx")
+        p = 13
+        prog = parse("def f():\n\ty = x")
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[0].out_values["range"]
-        self.assertEquals(r, {'_': (0, p)})
+        self.assertEquals(r, {'y': full_range(p)})
 
     def test_range_if(self):
-        p = 7
+        p = 13
         prog = parse(
 """
 def f(x):
@@ -242,32 +261,33 @@
         y=2
     else:
         y=3
-    y
+    return y
 """)
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[-1].out_values["range"]
-        self.assertEquals(r, {'x': (0,7), 'y': (2, 3), '_': (2, 3)})
+        self.assertEquals(r, {'x': full_range(p), 'y': (2, 3)})
 
-    def test_range_while(self):
-        p = 7
-        prog = parse(
-"""
-def f(x):
-    x=3
-    y=1
-    while(x>0):
-        y=y+1
-        x=x-1
-    y
-""")
-        range_analysis = RangeAnalysis(p)
-        range_analysis.apply(prog.body[0])
-        r = prog.body[0].body[-1].out_values["range"]
-        self.assertEquals(r, {'y': (1, Bottom()), 'x': (Bottom(), 3), '_': (1, Bottom())})
-
+#    def test_range_while(self):
+#        p = 13
+#        prog = parse(
+#"""
+#def f(x):
+#    x=3
+#    y=1
+#    while(x>0):
+#        y=y+1
+#        x=x-1
+#    y
+#""")
+#        range_analysis = RangeAnalysis(p)
+#        range_analysis.apply(prog.body[0])
+#        r = prog.body[0].body[-1].out_values["range"]
+#        self.assertEquals(r, {'y': (1, Bottom()), 'x': (Bottom(), 3), '_':
+#           (1, Bottom())})
+#
     def test_range_return(self):
-        p = 7
+        p = 13
         prog = parse(
 """
 def f(x):
@@ -276,19 +296,8 @@
         range_analysis = RangeAnalysis(p)
         range_analysis.apply(prog.body[0])
         r = prog.body[0].body[-1].out_values["range"]
-        self.assertEquals(r, {'x': (0, p)})
+        self.assertEquals(r, {'x': full_range(p)})
 
-    def test_range_result(self):
-        p = 7
-        prog = parse(
-"""
-def f(x):
-    return x
-""")
-        range_analysis = RangeAnalysis(p)
-        range_analysis.apply(prog.body[0])
-        r = prog.body[0].body[-1].out_values["range"]
-        self.assertEquals(r, {'x': (0, 7)})
 
 #     def test_range_multiple_assign_and_tuples(self):
 #         p = 7