source: proto/charsetcompiler/CC_compiler.py @ 4071

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

Restructuring; if-test simplification; odd/even ranges for Lu/Ll?

File size: 11.5 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 sym in enclosing_cgo.common_expression_map.keys():
26            self.common_expression_map[sym] = enclosing_cgo.common_expression_map[sym]
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 make_bit_test(self, pattern, bit_count):
74            if bit_count == 0: return TrueLiteral()
75            bit_terms = []
76            test_bit = 2**(bit_count - 1)
77            for i in range(0, bit_count):
78                if (pattern & test_bit) == 0:
79                    bit_terms.append(make_not(self.make_bitv((self.mEncoding.bits - 1)-i)))   
80                else: bit_terms.append(self.make_bitv((self.mEncoding.bits - 1)-i))           
81                test_bit >>= 1
82            while len(bit_terms) > 1:
83                new_terms = []
84                for i in range(0, len(bit_terms)/ 2):
85                    new_terms.append(make_and(bit_terms[2*i], bit_terms[2*i+1]))
86                if len(bit_terms) % 2 == 1:
87                    new_terms.append(bit_terms[-1])
88                bit_terms = new_terms
89            return bit_terms[0]
90
91    def bit_pattern_expr(self, pattern, selected_bits):
92            if selected_bits == 0: return TrueLiteral()
93            bit_terms = []
94            bit_no = 0
95            while selected_bits:
96              test_bit = 1 << bit_no
97              if selected_bits & test_bit:
98                if (pattern & test_bit) == 0:
99                    bit_terms = [make_not(self.make_bitv(bit_no))] + bit_terms
100                else: bit_terms = [self.make_bitv(bit_no)] + bit_terms
101              else: bit_terms = [TrueLiteral()] + bit_terms
102              # Appending TrueLiteral() for nonselected bits is intended
103              # to keep consistent grouping of variables in the next loop.
104              selected_bits &= ~test_bit
105              bit_no += 1
106            while len(bit_terms) > 1:
107                new_terms = []
108                for i in range(0, len(bit_terms)/ 2):
109                    new_terms.append(make_and(bit_terms[2*i], bit_terms[2*i+1]))
110                if len(bit_terms) % 2 == 1:
111                    new_terms.append(bit_terms[-1])
112                bit_terms = new_terms     
113            return bit_terms[0]
114   
115    def char_test_expr(self, chval):
116            return self.bit_pattern_expr(chval, self.mEncoding.mask) 
117
118    def GE_Range(self, N, n):
119            if N == 0: return TrueLiteral()
120            elif N % 2 == 0 and (n >> (N - 2)) == 0:
121                return make_or(make_or(self.make_bitv(N-1), self.make_bitv(N-2)),
122                                self.GE_Range(N - 2, n))
123            elif N % 2 == 0 and (n >> (N - 2)) == 3:   # >= 11xxxx
124                return make_and(make_and(self.make_bitv(N-1), self.make_bitv(N-2)),
125                                self.GE_Range(N - 2, n - (3 << (N-2))))
126            elif N >= 1:
127                hi_bit = n & (1 << (N-1))
128                lo_bits = n - hi_bit
129                lo_range = self.GE_Range(N-1, lo_bits)
130                if hi_bit == 0:
131                    # If the hi_bit of n is not set, then whenever the corresponding bit
132                    # is set in the target, the target will certainly be >=.  Otherwise,
133                    # the value of GE_range(N-1, lo_bits) is required.
134                    return make_or(self.make_bitv(N-1), lo_range)
135                else: 
136                    # If the hi_bit of n is set, then the corresponding bit must be set
137                    # in the target for >= and GE_range(N-1, lo_bits) must also be true.
138                    return make_and(self.make_bitv(N-1), lo_range)
139
140    def LE_Range(self, N, n):
141            # If an N-bit pattern is all ones, then it is always
142            # true that any n-bit value is LE this pattern.
143            # Handling this as a special case avoids an overflow
144            # issue with n+1 requiring more than N bits.
145            if n+1 == 2 ** N:
146                return TrueLiteral()
147            else:
148                return make_not(self.GE_Range(N, n+1))
149
150    def Make_Range(self, n1, n2):  # require n2 >= n1
151            diff_bits = n1 ^ n2
152            diff_count = 0
153            while diff_bits > 0:
154                diff_count += 1
155                diff_bits >>= 1
156            if n2 < n1 or diff_count > self.mEncoding.bits: raise Exception("Bad range: (%x, %x)." % (n1, n2))
157            mask = 2**(diff_count) - 1
158            #common = make_bit_test(n1 >> diff_count, 8 - diff_count)
159            common = self.bit_pattern_expr(n1 & ~mask, self.mEncoding.mask^mask)   
160            if diff_count == 0: return common
161            mask = 2**(diff_count-1) - 1
162            lo_test = self.GE_Range(diff_count-1, n1 & mask)
163            hi_test = self.LE_Range(diff_count-1, n2 & mask)
164            return make_and(common, make_sel(self.make_bitv(diff_count-1), hi_test, lo_test))
165
166
167    def char_or_range_expr(self, charset_item):
168            (lo, hi) = charset_item
169            if lo == hi:
170                return self.char_test_expr(lo)
171            else:
172                return self.Make_Range(lo, hi)
173
174    def charset_expr(self, chardef):
175            if chardef.items == []: return FalseLiteral()
176            if len(chardef.items) > 2:
177                combine = True
178                #If all of the charset items are single codepoints
179                #such that X0 == Y0, X1 == Y1 etc.
180                for item in chardef.items:
181                    if item[0] != item[1]:
182                        combine = False
183                        break
184                if combine == True:
185                    #If charset items are all of the form X1 = X0 + 2.
186                    for i in range(len(chardef.items) - 1):
187                        curr_item = chardef.items[i]
188                        next_item = chardef.items[i+1]
189                        if curr_item[0] != next_item[0] - 2:
190                            combine = False
191                            break
192                if combine == True:
193                    lo = chardef.items[0][0]
194                    hi = chardef.items[-1][0]
195                    print "Combined odd/even range %x-%x" % (lo, hi)
196                    utf_temp = self.mEncoding.mask - 1
197                    lo &= utf_temp
198                    hi |= (self.mEncoding.mask ^ utf_temp)
199                    if lo & 1 == 1: return make_and(self.char_or_range_expr((lo, hi)), self.make_bitv(0))
200                    else: return make_and(self.char_or_range_expr((lo, hi)), make_not(self.make_bitv(0)))
201            e1 = self.char_or_range_expr(chardef.items[0])
202            for i in range(1, len(chardef.items)):   
203                e1 = make_or(e1, self.char_or_range_expr(chardef.items[i]))
204            if chardef.complemented: return make_not(e1)
205            else: return e1
206
207    def add_assignment(self, varname, expr):
208        #if not self.sym_in_map(varname):
209            self.common_expression_map[expr] = varname       
210            self.generated_code.append('\t%s%s = %s\n' % (self.typedecl, varname, expr))
211
212    # An assignment to a variable name that uniquely specifies the expr
213    def add_canonical_assignment(self, canonical_var, expr):
214        if not canonical_var in self.canonical_sym_map.keys():
215            self.common_expression_map[expr] = canonical_var       
216            self.canonical_sym_map[canonical_var] = expr
217            self.generated_code.append('\t%s%s = %s\n' % (self.typedecl, canonical_var, expr))
218
219    def add_if_stmt(self, test_expr, generated_subcode):
220        test_line = 'if %s:\n' % (self.expr_string_to_variable(self.expr2py(test_expr)))
221        self.generated_code.append('\t' + test_line)
222        self.generated_code += ['\t' + line for line in generated_subcode]
223        self.generated_code.append('\t#end' + test_line)
224       
225
226    def expr_string_to_variable(self, expr_string):
227        if self.common_expression_map.has_key(expr_string):
228            return self.common_expression_map[expr_string]
229        else:
230            self.gensym_counter += 1                           
231            sym = self.gensym_template % self.gensym_counter 
232            self.add_assignment(sym, expr_string) 
233            return sym
234
235    def showcode(self):
236        s = ''
237        for stmt in self.generated_code: s += stmt
238        return s
239
240    def expr2py(self, expr):
241            """Translate a Boolean expression into three-address python code.
242            """
243            if isinstance(expr, TrueLiteral): return '-1'
244            elif isinstance(expr, FalseLiteral): return '0'
245            elif isinstance(expr, Var): 
246               # This is a hack.
247               self.common_expression_map[expr.varname] = expr.varname
248               return expr.varname
249            elif isinstance(expr, Not):
250               e = self.expr_string_to_variable(self.expr2py(expr.operand))
251               return '(~%s)' % (e)
252            elif isinstance(expr, Or):
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, Xor):
257               e1 = self.expr_string_to_variable(self.expr2py(expr.operand1))
258               e2 = self.expr_string_to_variable(self.expr2py(expr.operand2))
259               return '(%s ^ %s)' % (e1, e2)
260            elif isinstance(expr, And):
261               if isinstance(expr.operand1, Not):
262                   e1 = self.expr_string_to_variable(self.expr2py(expr.operand1.operand))
263                   e2 = self.expr_string_to_variable(self.expr2py(expr.operand2))
264                   return '(%s &~ %s)' % (e2, e1)
265               elif isinstance(expr.operand2, Not):
266                   e1 = self.expr_string_to_variable(self.expr2py(expr.operand1))
267                   e2 = self.expr_string_to_variable(self.expr2py(expr.operand2.operand))
268                   return '(%s &~ %s)' % (e1, e2)
269               else:
270                   e1 = self.expr_string_to_variable(self.expr2py(expr.operand1))
271                   e2 = self.expr_string_to_variable(self.expr2py(expr.operand2))
272                   return '(%s & %s)' % (e1, e2)
273            elif isinstance(expr, Sel):
274               sel = self.expr_string_to_variable(self.expr2py(expr.sel))
275               e1 = self.expr_string_to_variable(self.expr2py(expr.true_branch))
276               e2 = self.expr_string_to_variable(self.expr2py(expr.false_branch))
277               return '((%s & %s)|(~(%s) & %s))' %(sel, e1, sel, e2)
278            elif isinstance(expr, Adv):
279               e = self.expr_string_to_variable(self.expr2py(expr.operand))
280               if expr.offset == 1: return 'Advance(%s)' % (e)
281               else: return 'Advance(%s, %i)' % (e, expr.offset)
282            else: raise Exception("Bad expression: %s" % repr(expr))
283
284    def chardef2py(self, chardef):
285            self.add_assignment(chardef.name, self.expr2py(self.charset_expr(chardef)))
286
287    def chardef_canonical(self, chardef):
288            self.add_canonical_assignment(chardef.name, self.expr2py(self.charset_expr(chardef)))
289   
290    def chardeflist2py(self, chardeflist):
291            for d in chardeflist:
292                self.chardef2py(d) 
293            return self.showcode()
294
295
Note: See TracBrowser for help on using the repository browser.