Seems to pass the test now
author Sigurd Meldgaard Tue, 26 May 2009 18:14:12 +0200 b8b250033b5e 06088bcf6ab3 f5f904ab0f46 pysmcl/range_analysis.py 1 files changed, 22 insertions(+), 16 deletions(-) [+]
line wrap: on
line diff
```--- a/pysmcl/range_analysis.py	Tue May 26 17:35:27 2009 +0200
+++ b/pysmcl/range_analysis.py	Tue May 26 18:14:12 2009 +0200
@@ -3,10 +3,10 @@
#
#

-""" This module implements a range analysis of expressions in the
+""" This module implements a range analysis of expressions in the
core PySMCL language.

-The lattice is the power set lattice over all variables and their range in a given
+The lattice is the power set lattice over all variables and their range in a given
function. A range is represented as a tuple of two numbers or the bottom element.
"""

@@ -21,7 +21,7 @@

class Bottom(object):
"""The element used to represent intervals that are not between 0 and p.
-
+
e.g. for the expression x = 2-5 yields the range for x (Bottom(), Bottom())
"""
def __eq__(self, other):
@@ -51,7 +51,7 @@

def join(self, in_nodes):
"""The join function in the monotome framework.
-
+
in_nodes (Set) a set of predecessor nodes.
"""
if debug:
@@ -112,7 +112,7 @@
return rangeVisitor.visit(node)

class RangeVisitor(ast.NodeVisitor):
-    """RangeVisitor is the visitor which actually implements the
+    """RangeVisitor is the visitor which actually implements the
range computation."""

def __init__(self, prime, env):
@@ -132,6 +132,15 @@
return (0, self.prime)

def visit_BinOp(self, node):
+        def liftMinus(a,b):
+            if(isinstance(a, Bottom) or
+               isinstance(b, Bottom)):
+                return Bottom()
+            c = a-b
+            if(c < 0):
+                return Bottom()
+            return c
+
# operator = Add | Sub | Mult | Div | Mod | Pow | LShift
#          | RShift | BitOr | BitXor | BitAnd | FloorDiv
left = self.visit(node.left)
@@ -147,12 +156,8 @@
return (r0, r1)

if isinstance(node.op, ast.Sub):
-            r0 = left[0] - right[1]
-            r1 = left[1] - right[0]
-            if r0 < 0:
-                r0 = Bottom()
-            if r1 < 0:
-                r1 = Bottom()
+            r0 = liftMinus(left[0], right[1])
+            r1 = liftMinus(left[1], right[0])
return (r0, r1)

if isinstance(node.op, ast.Mult):
@@ -222,14 +227,15 @@

def combine_range((l1, h1), (l2, h2)):
"""Combine the two ranges."""
-    r = (Buttom(),Buttom())
+    (r0, r1) = (Bottom(),Bottom())
if l1 < l2:
r[0] = l1
+        r0 = l1
else:
-        r[0] = l2
+        r0 = l2

if h1 > h2:
-        r[1] = h1
+        r1 = h1
else:
-        r[1] = h2
-    return r
+        r1 = h2
+    return (r0,r1)```