source: proto/charsetcompiler/CC_compiler.py @ 3944

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

Convert character set definitions to use canonical list of range data structure.

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