1 #!/usr/bin/env python 2 3 """ 4 Common classes. 5 6 Copyright (C) 2007, 2008, 2009, 2010, 2011 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 16 details. 17 18 You should have received a copy of the GNU General Public License along with 19 this program. If not, see <http://www.gnu.org/licenses/>. 20 """ 21 22 import compiler.visitor 23 import operator 24 25 try: 26 set 27 except NameError: 28 from sets import Set as set 29 30 class ObjectSet: 31 32 "A set of objects with optional associated data." 33 34 def __init__(self, d=None): 35 if d is None: 36 self.objects = {} 37 elif hasattr(d, "items"): 38 self.objects = dict(d) 39 else: 40 self.objects = {} 41 for key in d: 42 self.add(key) 43 44 def __repr__(self): 45 out = ["{"] 46 first = 1 47 for key, value in self.items(): 48 if not first: 49 out.append(", ") 50 else: 51 first = 0 52 out.append(repr(key)) 53 if value: 54 out.append(" : ") 55 out.append(repr(value)) 56 out.append("}") 57 return "".join(out) 58 59 def __iter__(self): 60 return iter(self.keys()) 61 62 def __nonzero__(self): 63 return self.objects != {} 64 65 # Set membership and comparisons. 66 67 def __hash__(self): 68 return hash(tuple(self.keys())) 69 70 def __eq__(self, other): 71 return self.objects == other.objects 72 73 # Set methods. 74 75 def add(self, obj): 76 if not self.has_key(obj): 77 self[obj] = [] 78 79 # Dictionary and related methods. 80 81 def __getitem__(self, key): 82 return self.objects[key] 83 84 def get(self, key, default=None): 85 return self.objects.get(key, default) 86 87 def __setitem__(self, key, value): 88 self.objects[key] = value 89 90 def has_key(self, key): 91 return self.objects.has_key(key) 92 93 def keys(self): 94 return self.objects.keys() 95 96 def values(self): 97 return self.objects.values() 98 99 def items(self): 100 return self.objects.items() 101 102 def update(self, other): 103 104 # Combining dictionary-like objects involves combining values. 105 106 if hasattr(other, "items"): 107 for key, value in other.items(): 108 self[key] = value + self.get(key, []) 109 110 # Combining sequence-like objects involves just adding members. 111 112 else: 113 for key in other: 114 self.add(key) 115 116 def merge(self, other): 117 118 """ 119 Merge this object set with an 'other' set, combining the values where 120 possible, and incorporating values present in only one of the sets. 121 """ 122 123 return combine(self, other, ObjectSet(), operator.add) 124 125 def deepen_mapping_dict(d): 126 127 "Convert the values of 'd' to be elements of a potentially larger set." 128 129 new_dict = {} 130 for key, value in d.items(): 131 new_dict[key] = set([value]) 132 return new_dict 133 134 def merge_mapping_dicts(dicts): 135 136 "Merge the given 'dicts' mapping keys to sets of objects." 137 138 new_dict = {} 139 update_mapping_dict(new_dict, dicts) 140 return new_dict 141 142 def update_mapping_dict(new_dict, dicts): 143 144 "Update 'new_dict' with the contents of the set dictionary 'dicts'." 145 146 for old_dict in dicts: 147 for key, value in old_dict.items(): 148 if not new_dict.has_key(key): 149 new_dict[key] = ObjectSet(value) 150 else: 151 new_dict[key].update(value) 152 153 def combine_mapping_dicts(d1, d2): 154 155 """ 156 Combine dictionaries 'd1' and 'd2' in a resulting dictionary, with the 157 values of the contributing dictionaries being themselves combined such that 158 a "product" of the values for a given key are stored in the combined 159 dictionary. 160 161 For example: 162 163 d1: {'a' : [{'f', 'g'}, {'f', 'h'}], ...} 164 d2: {'a' : [{'f'}, {'e', 'f', 'g'}], ...} 165 -> {'a' : [{'f', 'g'}, {'f', 'h'}, {'e', 'f', 'g'}, {'e', 'f', 'g', 'h'}], ...} 166 """ 167 168 return combine(d1, d2, {}, combine_object_set_lists) 169 170 def combine(d1, d2, combined, combine_op): 171 172 """ 173 Combine dictionaries 'd1' and 'd2' in the 'combined' object provided, using 174 the 'combine_op' to merge values from the dictionaries. 175 """ 176 177 d2_keys = d2.keys() 178 179 for key in d2_keys: 180 if not d1.has_key(key): 181 combined[key] = d2[key] 182 else: 183 combined[key] = combine_op(d1[key], d2[key]) 184 185 for key in d1.keys(): 186 if key not in d2_keys: 187 combined[key] = d1[key] 188 189 return combined 190 191 def combine_object_set_lists(l1, l2): 192 193 """ 194 Combine lists of object sets 'l1' and 'l2' to make a product of their 195 members. 196 """ 197 198 combined = set([]) 199 for i1 in l1: 200 for i2 in l2: 201 combined.add(i1.merge(i2)) 202 return combined 203 204 # Visitors and activities related to node annotations. 205 206 class ASTVisitor(compiler.visitor.ASTVisitor): 207 208 "A base class for visitors." 209 210 def dispatch(self, node, *args): 211 212 "Dispatch using 'node', annotating any raised exceptions." 213 214 try: 215 return compiler.visitor.ASTVisitor.dispatch(self, node, *args) 216 except NodeProcessingError, exc: 217 if exc.astnode is None: 218 exc.astnode = node 219 220 # NOTE: Should perhaps specialise the subclasses appropriately. 221 222 if hasattr(self, "unit"): 223 exc.unit_name = self.unit.full_name() 224 else: 225 exc.unit_name = self.full_name() 226 raise 227 228 def possible_accessor_types(self, node): 229 230 """ 231 Given annotations made during the inspection process, return all possible 232 type names and indications of static usage for a 'node' involved in 233 attribute access. 234 """ 235 236 target_names = set() 237 238 if hasattr(node, "_attrusers"): 239 240 # Visit each attribute user. 241 242 for user in node._attrusers: 243 244 # Since users such as branches may not provide type information, 245 # attempt to find defining users. 246 247 for def_user in user._attrdefs or [user]: 248 for target_name, is_static in def_user._attrtypes.get(node._username, []): 249 target_names.add((target_name, is_static)) 250 251 return target_names 252 253 def used_by_unit(node): 254 255 """ 256 Return whether the definition made by a 'node' is actually employed by the 257 program unit within which it is found. 258 """ 259 260 return hasattr(node, "unit") and node.unit.parent.has_key(node.unit.name) 261 262 def get_object_types_for_usage(usage, objtable, name, unit_name): 263 264 """ 265 Return for the given attribute 'usage', using the 'objtable', the object 266 types which satisfy such usage, reporting any problems for the given 'name' 267 and 'unit_name'. Each object type is given as a tuple of the form (type, 268 is_static). 269 """ 270 271 all_objtypes = set() 272 273 for attrnames in usage: 274 objtypes = objtable.all_possible_objects_plus_status(attrnames) 275 if not objtypes: 276 print "Warning: usage in %r for %r finds no object supporting all attributes %r" % ( 277 unit_name, name, attrnames) 278 objtypes = objtable.any_possible_objects_plus_status(attrnames) 279 if not objtypes: 280 print "Warning: usage in %r for %r finds no object supporting any attributes %r" % ( 281 unit_name, name, attrnames) 282 283 all_objtypes.update(objtypes) 284 285 return all_objtypes 286 287 # Errors. 288 289 class ProcessingError(Exception): 290 291 "A processing error." 292 293 pass 294 295 class TableError(ProcessingError): 296 297 "An error occurring during access to a lookup table." 298 299 pass 300 301 class TableGenerationError(ProcessingError): 302 303 "An error occurring when generating a lookup table." 304 305 pass 306 307 class NodeProcessingError(ProcessingError): 308 309 "A processing error associated with a particular program node." 310 311 def __init__(self, message): 312 self.message = message 313 self.unit_name = None 314 self.astnode = None 315 316 def get_lineno(self, node): 317 lineno = node.lineno 318 if lineno is not None: 319 return lineno 320 else: 321 for child in node.getChildNodes(): 322 lineno = self.get_lineno(child) 323 if lineno is not None: 324 return lineno 325 return None 326 327 def __repr__(self): 328 return "Error in %r at line %r: %s" % (self.unit_name, self.get_lineno(self.astnode), self.message) 329 330 def __str__(self): 331 return repr(self) 332 333 class InspectError(NodeProcessingError): 334 335 "An error during the module inspection process." 336 337 pass 338 339 class TranslateError(NodeProcessingError): 340 341 "An error during the module translation process." 342 343 pass 344 345 class TranslationNotImplementedError(TranslateError): 346 347 "An error caused by a node not being supported in translation." 348 349 pass 350 351 # Special representations. 352 353 class AtLeast: 354 355 "A special representation for numbers of a given value or greater." 356 357 def __init__(self, count): 358 self.count = count 359 360 def __eq__(self, other): 361 return 0 362 363 __lt__ = __le__ = __eq__ 364 365 def __ne__(self, other): 366 return 1 367 368 def __gt__(self, other): 369 if isinstance(other, AtLeast): 370 return 0 371 else: 372 return self.count > other 373 374 def __ge__(self, other): 375 if isinstance(other, AtLeast): 376 return 0 377 else: 378 return self.count >= other 379 380 def __iadd__(self, other): 381 if isinstance(other, AtLeast): 382 self.count += other.count 383 else: 384 self.count += other 385 return self 386 387 def __radd__(self, other): 388 if isinstance(other, AtLeast): 389 return AtLeast(self.count + other.count) 390 else: 391 return AtLeast(self.count + other) 392 393 def __repr__(self): 394 return "AtLeast(%r)" % self.count 395 396 # Useful data. 397 398 operator_functions = { 399 400 # Binary operations. 401 402 "Add" : "add", 403 "Bitand" : "and_", 404 "Bitor" : "or_", 405 "Bitxor" : "xor", 406 "Div" : "div", 407 "FloorDiv" : "floordiv", 408 "LeftShift" : "lshift", 409 "Mod" : "mod", 410 "Mul" : "mul", 411 "Power" : "pow", 412 "RightShift" : "rshift", 413 "Sub" : "sub", 414 415 # Unary operations. 416 417 "Invert" : "invert", 418 "UnaryAdd" : "pos", 419 "UnarySub" : "neg", 420 421 # Augmented assignment. 422 423 "+=" : "iadd", 424 "-=" : "isub", 425 "*=" : "imul", 426 "/=" : "idiv", 427 "//=" : "ifloordiv", 428 "%=" : "imod", 429 "**=" : "ipow", 430 "<<=" : "ilshift", 431 ">>=" : "irshift", 432 "&=" : "iand", 433 "^=" : "ixor", 434 "|=" : "ior", 435 436 # Comparisons. 437 438 "==" : "eq", 439 "!=" : "ne", 440 "<" : "lt", 441 "<=" : "le", 442 ">=" : "ge", 443 ">" : "gt", 444 445 # Access and slicing. 446 447 "AssSlice" : "setslice", 448 "Slice" : "getslice", 449 "AssSubscript" : "setitem", 450 "Subscript" : "getitem", 451 } 452 453 # vim: tabstop=4 expandtab shiftwidth=4