source: proto/charsetcompiler/bitwise_expr.py @ 3944

Last change on this file since 3944 was 3942, checked in by cameron, 5 years ago

Refactor pulling out bitwise_expr module; prepare toAst method

File size: 7.8 KB
Line 
1#
2#  Bitwise Boolean Expressions.
3#
4import ast
5
6class BitwiseExpr:
7   """The BitwiseExpr class and its subclasses provide a symbolic
8      representation of bitwise Boolean expressions.
9   """
10   pass
11
12class Var(BitwiseExpr):
13    def __init__(self, varname):
14        self.varname = varname
15    def __str__(self): return 'Var("' + self.varname + '")'
16    def toAST(self): return ast.Name(id=self.varname, ctx=ast.Load())
17
18class TrueLiteral(BitwiseExpr):
19    def __init__(self):
20        self.value = True
21    def __str__(self): return 'T'
22    def toAST(self): return ast.Name(id='True', ctx=ast.Load())
23
24class FalseLiteral(BitwiseExpr):
25    def __init__(self):
26        self.value = False
27    def __str__(self): return 'F'
28    def toAST(self): return ast.Name(id='False', ctx=ast.Load())
29
30class Not(BitwiseExpr):
31    def __init__(self, expr):
32        self.operand = expr
33    def __str__(self): return 'Not(%s)' % (self.operand.__str__())
34    def toAST(self): return ast.UnaryOp(ast.Not(), self.operand.toAST())
35
36class And(BitwiseExpr):
37    def __init__(self, expr1, expr2):
38        self.operand1 = expr1
39        self.operand2 = expr2
40    def __str__(self): return 'And(%s, %s)' % (self.operand1.__str__(), self.operand2.__str__())
41    def toAST(self): return ast.BinOp(self.operand1.toAST(), ast.BitAnd(), self.operand2.toAST())
42
43class Or(BitwiseExpr):
44    def __init__(self, expr1, expr2):
45        self.operand1 = expr1
46        self.operand2 = expr2
47    def __str__(self): return 'Or(%s, %s)' % (self.operand1.__str__(), self.operand2.__str__())
48    def toAST(self): return ast.BinOp(self.operand1.toAST(), ast.BitOr(), self.operand2.toAST())
49
50class Xor(BitwiseExpr):
51    def __init__(self, expr1, expr2):
52        self.operand1 = expr1
53        self.operand2 = expr2
54    def __str__(self): return 'Xor(%s, %s)' % (self.operand1.__str__(), self.operand2.__str__())
55    def toAST(self): return ast.BinOp(self.operand1.toAST(), ast.BitXor(), self.operand2.toAST())
56
57class Sel(BitwiseExpr):
58    def __init__(self, expr1, expr2, expr3):
59        self.sel = expr1
60        self.true_branch = expr2
61        self.false_branch = expr3
62    def __str__(self): return 'Sel(%s, %s, %s)' % (self.sel.__str__(), self.true_branch.__str__(), self.false_branch.__str__())
63    def toAST(self): return ast.IfExpr(self.sel.toAST(), self.true_branch.toAST(), self.false_branch.toAST())
64
65
66#
67# Optimizing Constructors for Boolean Expressions
68# - Maintaining Assembler Instruction Form:
69#   - All boolean algebraic rules involving true/false applied.
70#   - Negations restricted:
71#       - no negations within or (DeMorgan's to nand)
72#       - at most one negation within and
73#
74
75def make_not(expr):
76    if isinstance(expr, TrueLiteral):
77        return FalseLiteral()
78    elif isinstance(expr, FalseLiteral):
79        return TrueLiteral()
80    elif isinstance(expr, Not):
81        return expr.operand
82    else: return Not(expr)
83
84def make_and(expr1, expr2):
85    if isinstance(expr1, TrueLiteral):
86        return expr2
87    elif isinstance(expr2, TrueLiteral):
88        return expr1
89    elif isinstance(expr1, FalseLiteral):
90        return FalseLiteral()
91    elif isinstance(expr2, FalseLiteral):
92        return FalseLiteral()
93    elif equal_exprs(expr1, expr2): return expr1
94    elif isinstance(expr1, Not):
95        if isinstance(expr2, Not):
96            return make_not(make_or(expr1.operand, expr2.operand))
97        elif equal_exprs(expr1.operand, expr2): return FalseLiteral()
98        else: return And(expr1, expr2)
99    elif isinstance(expr2, Not):
100        if equal_exprs(expr1, expr2.operand): return FalseLiteral()
101        else: return And(expr1, expr2)
102    else: return And(expr1, expr2)
103
104def make_or(expr1, expr2):
105    if isinstance(expr1, FalseLiteral):
106        return expr2
107    elif isinstance(expr2, FalseLiteral):
108        return expr1
109    elif isinstance(expr1, TrueLiteral):
110        return TrueLiteral()
111    elif isinstance(expr2, TrueLiteral):
112        return TrueLiteral()
113    elif isinstance(expr1, Not):
114        return make_not(make_and(expr1.operand, make_not(expr2)))
115    elif isinstance(expr2, Not):
116        return make_not(make_and(make_not(expr1), expr2.operand))
117    elif equal_exprs(expr1, expr2): return expr1
118    elif isinstance(expr1, And) and isinstance(expr2, And):
119        # These optimizations factor out common components that
120        # can occur when sets are formed by union (e.g., union of
121        # [a-z] and [A-Z].
122        if equal_exprs(expr1.operand1, expr2.operand1):
123            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand2))
124        elif equal_exprs(expr1.operand2, expr2.operand2):
125            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand1))
126        elif equal_exprs(expr1.operand1, expr2.operand2):
127            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand1))
128        elif equal_exprs(expr1.operand2, expr2.operand1):
129            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand2))
130        else: return Or(expr1, expr2)
131    else: return Or(expr1, expr2)
132
133def make_sel(if_expr, T_expr, F_expr):
134    if isinstance(if_expr, TrueLiteral):
135        return T_expr
136    elif isinstance(if_expr, FalseLiteral):
137        return F_expr
138    elif isinstance(T_expr, TrueLiteral):
139        # if x then T else y = x or y
140        return make_or(if_expr, F_expr) 
141    elif isinstance(T_expr, FalseLiteral):
142        # if x then F else y = not(x) and y
143        return make_and(make_not(if_expr), F_expr) 
144    elif isinstance(F_expr, FalseLiteral):
145        # if x then y else F = x and y
146        return make_and(if_expr, T_expr) 
147    elif isinstance(F_expr, TrueLiteral):
148        # if x then y else T = not(x) or y
149        return make_or(make_not(if_expr), T_expr)
150    elif equal_exprs(T_expr, F_expr):
151        return T_expr
152    else: return Sel(if_expr, T_expr, F_expr)
153
154
155def make_xor(expr1, expr2):
156    if isinstance(expr1, FalseLiteral):
157        return expr2
158    elif isinstance(expr2, FalseLiteral):
159        return expr1
160    elif isinstance(expr1, TrueLiteral):
161        return make_not(expr2)
162    elif isinstance(expr2, TrueLiteral):
163        return make_not(expr1)
164    elif isinstance(expr1, Not) and isinstance(expr2, Not):
165        return make_xor(expr1.operand, expr2.operand)
166    else: return Xor(expr1, expr2)
167
168# Return True if e1 and e2 can be proven equivalent according
169# to some rules, False otherwise.   Note that False may
170# be returned in some cases when the exprs are equivalent.
171def equal_exprs(e1, e2):
172    if isinstance(e1, FalseLiteral): return isinstance(e2, FalseLiteral)
173    elif isinstance(e1, TrueLiteral): return isinstance(e2, TrueLiteral)
174    elif isinstance(e1, Var) and isinstance(e2, Var):
175        return e1.varname == e2.varname
176    elif isinstance(e1, Not) and isinstance(e2, Not):
177        return equal_exprs(e1.operand, e2.operand)
178    elif isinstance(e1, And) and isinstance(e2, And):
179        if equal_exprs(e1.operand1, e2.operand1):
180            return equal_exprs(e1.operand2, e2.operand2)
181        elif equal_exprs(e1.operand1, e2.operand2):
182            return equal_exprs(e1.operand2, e2.operand1)
183        else: return False
184    elif isinstance(e1, Or) and isinstance(e2, Or):
185        if equal_exprs(e1.operand1, e2.operand1):
186            return equal_exprs(e1.operand2, e2.operand2)
187        elif equal_exprs(e1.operand1, e2.operand2):
188            return equal_exprs(e1.operand2, e2.operand1)
189        else: return False
190    elif isinstance(e1, Xor) and isinstance(e2, Xor):
191        if equal_exprs(e1.operand1, e2.operand1):
192            return equal_exprs(e1.operand2, e2.operand2)
193        elif equal_exprs(e1.operand1, e2.operand2):
194            return equal_exprs(e1.operand2, e2.operand1)
195        else: return False
196    elif isinstance(e1, Sel) and isinstance(e2, Sel):
197        if equal_exprs(e1.sel, e2.sel):
198             if equal_exprs(e1.true_branch, e2.true_branch):
199                 return equal_exprs(e1.false_branch, e2.false_branch)
200             else: return False
201        else: return False
202
203
Note: See TracBrowser for help on using the repository browser.