source: proto/charsetcompiler/CC_compiler.py

Last change on this file was 4514, checked in by cameron, 4 years ago

Avoid generating some unused variables

File size: 12.8 KB
Line 
1#
2#  Character Class Compiler - callable CharClassCompiler object.
3#
4import charset_input_parser
5
6import UTF_encoding
7Encoding_Type = UTF_encoding.UTF_Encoding_Type
8
9from pablo_expr import *
10
11class CC_compiler():
12    def __init__(self, encoding, gensym_pattern, little_endian_bit_numbering = True, typedecl = 'BitBlock '):
13        self.mEncoding = encoding
14        self.little_endian = little_endian_bit_numbering
15        self.gensym_template = gensym_pattern
16        self.gensym_counter = 0
17        self.generated_code = []
18        self.common_expression_map = {}
19        self.typedecl = typedecl
20        predeclared = [self.bit_var(i) for i in range(0, self.mEncoding.bits)]
21        for sym in predeclared: self.common_expression_map[sym] = sym
22        self.canonical_sym_map = {}
23
24    def add_common_expressions(self, enclosing_cgo):
25        for expr in enclosing_cgo.common_expression_map.keys():
26            self.common_expression_map[expr] = enclosing_cgo.common_expression_map[expr]
27        for sym in enclosing_cgo.canonical_sym_map.keys():
28            self.canonical_sym_map[sym] = enclosing_cgo.canonical_sym_map[sym]
29
30    def bit_var(self, n):
31
32            if len(self.mEncoding.basis_pattern) == 1:
33                return self.mEncoding.basis_pattern[0] % n
34           
35            if self.mEncoding.name == UTF_encoding.UTF16.name:
36                if options.little_endian == True:
37                    if n >= 8:
38                        return self.mEncoding.basis_pattern[0] % (n - 8)
39                    else:
40                        return self.mEncoding.basis_pattern[1] % n
41                else:
42                    if n <= 7:
43                        return self.mEncoding.basis_pattern[0] % n
44                    else:
45                        return self.mEncoding.basis_pattern[1] % (n - 8)
46
47            if self.mEncoding.name == UTF_encoding.UTF32.name:
48                if options.little_endian == True:
49                    if n >= 21:
50                        return "unused_bit%i" % (n - 21)
51                    elif n < 21 and n >= 16:
52                        return self.mEncoding.basis_pattern[0] % (n - 16)
53                    elif n < 16 and n >= 8:
54                        return self.mEncoding.basis_pattern[1] % (n - 8)
55                    elif n < 8:
56                        return self.mEncoding.basis_pattern[2] % n
57                else:
58                    if n <= 10:
59                        return "unused_bit%i" % n
60                    elif n > 10 and n <= 15:
61                        return self.mEncoding.basis_pattern[0] % (n - 8)
62                    elif n > 15 and n <= 23:
63                        return self.mEncoding.basis_pattern[1] % (n - 16)
64                    elif n > 23:
65                        return self.mEncoding.basis_pattern[2] % (n - 24)
66
67    def make_bitv(self, n):                 
68            if self.little_endian == True:
69                return Var(self.bit_var(n))
70            else:
71                return Var(self.bit_var((self.mEncoding.bits - 1) -n)) 
72               
73    def bit_pattern_expr(self, pattern, selected_bits):
74            if selected_bits == 0: return TrueLiteral()
75            bit_terms = []
76            bit_no = 0
77            while selected_bits:
78              test_bit = 1 << bit_no
79              if selected_bits & test_bit:
80                if (pattern & test_bit) == 0:
81                    bit_terms = [make_not(self.make_bitv(bit_no))] + bit_terms
82                else: bit_terms = [self.make_bitv(bit_no)] + bit_terms
83              else: bit_terms = [TrueLiteral()] + bit_terms
84              # Appending TrueLiteral() for nonselected bits is intended
85              # to keep consistent grouping of variables in the next loop.
86              selected_bits &= ~test_bit
87              bit_no += 1
88            while len(bit_terms) > 1:
89                new_terms = []
90                for i in range(0, len(bit_terms)/ 2):
91                    new_terms.append(make_and(bit_terms[2*i], bit_terms[2*i+1]))
92                if len(bit_terms) % 2 == 1:
93                    new_terms.append(bit_terms[-1])
94                bit_terms = new_terms           
95            return bit_terms[0]
96   
97    def char_test_expr(self, chval):
98            return self.bit_pattern_expr(chval, self.mEncoding.mask) 
99
100    def GE_Range(self, N, n):
101            if N == 0: return TrueLiteral()
102            elif N % 2 == 0 and (n >> (N - 2)) == 0:
103                return make_or(make_or(self.make_bitv(N-1), self.make_bitv(N-2)),
104                                self.GE_Range(N - 2, n))
105            elif N % 2 == 0 and (n >> (N - 2)) == 3:   # >= 11xxxx
106                return make_and(make_and(self.make_bitv(N-1), self.make_bitv(N-2)),
107                                self.GE_Range(N - 2, n - (3 << (N-2))))
108            elif N >= 1:
109                hi_bit = n & (1 << (N-1))
110                lo_bits = n - hi_bit
111                lo_range = self.GE_Range(N-1, lo_bits)
112                if hi_bit == 0:
113                    # If the hi_bit of n is not set, then whenever the corresponding bit
114                    # is set in the target, the target will certainly be >=.  Otherwise,
115                    # the value of GE_range(N-1, lo_bits) is required.
116                    return make_or(self.make_bitv(N-1), lo_range)
117                else: 
118                    # If the hi_bit of n is set, then the corresponding bit must be set
119                    # in the target for >= and GE_range(N-1, lo_bits) must also be true.
120                    return make_and(self.make_bitv(N-1), lo_range)
121
122    def LE_Range(self, N, n):
123            # If an N-bit pattern is all ones, then it is always
124            # true that any n-bit value is LE this pattern.
125            # Handling this as a special case avoids an overflow
126            # issue with n+1 requiring more than N bits.
127            if n+1 == 2 ** N:
128                return TrueLiteral()
129            else:
130                return make_not(self.GE_Range(N, n+1))
131
132    def Make_Range(self, n1, n2):  # require n2 >= n1
133            diff_bits = n1 ^ n2
134            diff_count = 0
135            while diff_bits > 0:
136                diff_count += 1
137                diff_bits >>= 1
138            if n2 < n1 or diff_count > self.mEncoding.bits: raise Exception("Bad range: (%x, %x)." % (n1, n2))
139            mask = 2**(diff_count) - 1
140            common = self.bit_pattern_expr(n1 & ~mask, self.mEncoding.mask^mask)   
141            if diff_count == 0: return common
142            mask = 2**(diff_count-1) - 1
143            lo_test = self.GE_Range(diff_count-1, n1 & mask)
144            hi_test = self.LE_Range(diff_count-1, n2 & mask)
145            return make_and(common, make_sel(self.make_bitv(diff_count-1), hi_test, lo_test))
146
147
148    def char_or_range_expr(self, charset_item):
149            (lo, hi) = charset_item
150            if lo == hi:
151                return self.char_test_expr(lo)
152            else:
153                return self.Make_Range(lo, hi)
154
155    def charset_expr(self, chardef):
156            if chardef.items == []: return FalseLiteral()
157            if len(chardef.items) > 2:
158                combine = True
159                #If all of the charset items are single codepoints
160                #such that X0 == Y0, X1 == Y1 etc.
161                for item in chardef.items:
162                    if item[0] != item[1]:
163                        combine = False
164                        break
165                if combine == True:
166                    #If charset items are all of the form X1 = X0 + 2.
167                    for i in range(len(chardef.items) - 1):
168                        curr_item = chardef.items[i]
169                        next_item = chardef.items[i+1]
170                        if curr_item[0] != next_item[0] - 2:
171                            combine = False
172                            break
173                if combine == True:
174                    lo = chardef.items[0][0]
175                    hi = chardef.items[-1][0]
176                    print "Combined odd/even range %x-%x" % (lo, hi)
177                    #
178                    if lo & 1 == 1: return make_and(self.char_or_range_expr((lo&~1, hi)), self.make_bitv(0))
179                    else: return make_and(self.char_or_range_expr((lo, hi|1)), make_not(self.make_bitv(0)))
180            e1 = self.char_or_range_expr(chardef.items[0])
181            for i in range(1, len(chardef.items)):   
182                e1 = make_or(e1, self.char_or_range_expr(chardef.items[i]))
183            if chardef.complemented: return make_not(e1)
184            else: return e1
185
186    def add_assignment(self, varname, expr_string):
187        if self.common_expression_map.has_key(expr_string):
188            assigned = self.common_expression_map[expr_string]
189            if assigned == varname: return
190        else:
191            self.common_expression_map[expr_string] = varname
192            assigned = expr_string   
193        self.generated_code.append('\t%s%s = %s\n' % (self.typedecl, varname, assigned))
194
195    # An assignment to a variable name that uniquely specifies the expr
196    def add_canonical_assignment(self, canonical_var, expr):
197        if not canonical_var in self.canonical_sym_map.keys():
198            self.add_assignment(canonical_var, expr)
199            self.common_expression_map[expr] = canonical_var       
200            self.canonical_sym_map[canonical_var] = expr       
201
202    def add_if_stmt(self, test_expr, generated_subcode):
203        test_line = 'if %s:\n' % (self.expr_string_to_variable(self.expr2py(test_expr)))
204        self.generated_code.append('\t' + test_line)
205        self.generated_code += ['\t' + line for line in generated_subcode]
206        self.generated_code.append('\t#end' + test_line)
207       
208
209    def expr_string_to_variable(self, expr_string):
210        if self.common_expression_map.has_key(expr_string):
211            return self.common_expression_map[expr_string]
212        else:
213            self.gensym_counter += 1                           
214            sym = self.gensym_template % self.gensym_counter 
215            self.add_assignment(sym, expr_string) 
216            return sym
217
218    def showcode(self):
219        s = ''
220        for stmt in self.generated_code: s += stmt
221        return s
222
223    def expr2py(self, expr):
224            """Translate a Boolean expression into three-address python code.
225            """
226            if isinstance(expr, TrueLiteral): return '-1'
227            elif isinstance(expr, FalseLiteral): return '0'
228            elif isinstance(expr, Var): 
229               # This is a hack.
230               self.common_expression_map[expr.varname] = expr.varname
231               return expr.varname
232            elif isinstance(expr, Not):
233               e = self.expr_string_to_variable(self.expr2py(expr.operand))
234               return '(~%s)' % (e)
235            elif isinstance(expr, Or):
236               e1 = self.expr_string_to_variable(self.expr2py(expr.operand1))
237               e2 = self.expr_string_to_variable(self.expr2py(expr.operand2))
238               return '(%s | %s)' % (e1, e2)
239            elif isinstance(expr, Xor):
240               e1 = self.expr_string_to_variable(self.expr2py(expr.operand1))
241               e2 = self.expr_string_to_variable(self.expr2py(expr.operand2))
242               return '(%s ^ %s)' % (e1, e2)
243            elif isinstance(expr, And):
244               if isinstance(expr.operand1, Not):
245                   e1 = self.expr_string_to_variable(self.expr2py(expr.operand1.operand))
246                   e2 = self.expr_string_to_variable(self.expr2py(expr.operand2))
247                   return '(%s &~ %s)' % (e2, e1)
248               elif isinstance(expr.operand2, Not):
249                   e1 = self.expr_string_to_variable(self.expr2py(expr.operand1))
250                   e2 = self.expr_string_to_variable(self.expr2py(expr.operand2.operand))
251                   return '(%s &~ %s)' % (e1, e2)
252               else:
253                   e1 = self.expr_string_to_variable(self.expr2py(expr.operand1))
254                   e2 = self.expr_string_to_variable(self.expr2py(expr.operand2))
255                   return '(%s & %s)' % (e1, e2)
256            elif isinstance(expr, Sel):
257               sel = self.expr_string_to_variable(self.expr2py(expr.sel))
258               e1 = self.expr_string_to_variable(self.expr2py(expr.true_branch))
259               e2 = self.expr_string_to_variable(self.expr2py(expr.false_branch))
260               return '((%s & %s)|(~(%s) & %s))' %(sel, e1, sel, e2)
261            elif isinstance(expr, Adv):
262               e = self.expr_string_to_variable(self.expr2py(expr.operand))
263               if expr.offset == 1: return 'Advance(%s)' % (e)
264               else: return 'Advance(%s, %i)' % (e, expr.offset)
265            else: raise Exception("Bad expression: %s" % repr(expr))
266
267    def chardef2py(self, chardef):
268            self.add_assignment(chardef.name, self.expr2py(self.charset_expr(chardef)))
269
270    def chardef_canonical(self, chardef):
271            self.add_canonical_assignment(chardef.name, self.expr2py(self.charset_expr(chardef)))
272   
273    def chardeflist2py(self, chardeflist):
274            for d in chardeflist:
275                self.chardef2py(d) 
276            return self.showcode()
277
278
Note: See TracBrowser for help on using the repository browser.