1 #!/usr/bin/env python 2 3 """ 4 Common classes. 5 6 Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012 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 # List methods. 66 67 def __add__(self, other): 68 obj = ObjectSet(self) 69 for key in other: 70 obj.add(key) 71 return obj 72 73 # Set membership and comparisons. 74 75 def __hash__(self): 76 return hash(tuple(self.keys())) 77 78 def __eq__(self, other): 79 if hasattr(other, "objects"): 80 return self.objects == other.objects 81 else: 82 return set(self.objects.keys()) == set(other) 83 84 # Set methods. 85 86 def add(self, obj): 87 if not self.has_key(obj): 88 self[obj] = [] 89 90 # Dictionary and related methods. 91 92 def __getitem__(self, key): 93 return self.objects[key] 94 95 def get(self, key, default=None): 96 return self.objects.get(key, default) 97 98 def __setitem__(self, key, value): 99 self.objects[key] = value 100 101 def has_key(self, key): 102 return self.objects.has_key(key) 103 104 def keys(self): 105 return self.objects.keys() 106 107 def values(self): 108 return self.objects.values() 109 110 def items(self): 111 return self.objects.items() 112 113 def update(self, other): 114 115 # Combining dictionary-like objects involves combining values. 116 117 if hasattr(other, "items"): 118 for key, value in other.items(): 119 self[key] = value + self.get(key, []) 120 121 # Combining sequence-like objects involves just adding members. 122 123 else: 124 for key in other: 125 self.add(key) 126 127 def merge(self, other): 128 129 """ 130 Merge this object set with an 'other' set, combining the values where 131 possible, and incorporating values present in only one of the sets. 132 """ 133 134 return combine(self, other, ObjectSet(), operator.add) 135 136 def deepen_mapping_dict(d): 137 138 "Convert the values of 'd' to be elements of a potentially larger set." 139 140 new_dict = {} 141 for key, value in d.items(): 142 if value is None: 143 new_dict[key] = None 144 else: 145 new_dict[key] = ObjectSet([value]) 146 return new_dict 147 148 def merge_mapping_dicts(dicts): 149 150 "Merge the given 'dicts' mapping keys to sets of objects." 151 152 new_dict = {} 153 update_mapping_dict(new_dict, dicts) 154 return new_dict 155 156 def update_mapping_dict(new_dict, dicts): 157 158 """ 159 Update 'new_dict' with the contents of the set dictionary 'dicts'. 160 None entries may be incorporated into object sets. For example: 161 162 d1: {'a' : None} 163 d2: {'a' : x} 164 -> {'a' : {None, x}} 165 166 Here, None might be used to represent an empty set and x may be an existing 167 set. 168 """ 169 170 for old_dict in dicts: 171 for key, value in old_dict.items(): 172 if not new_dict.has_key(key): 173 if value is not None: 174 new_dict[key] = ObjectSet(value) 175 else: 176 new_dict[key] = None 177 elif new_dict[key] is not None: 178 if value is not None: 179 new_dict[key].update(value) 180 else: 181 new_dict[key].add(value) 182 else: 183 if value is not None: 184 objset = new_dict[key] = ObjectSet(value) 185 objset.add(None) 186 187 def combine_mapping_dicts(d1, d2): 188 189 """ 190 Combine dictionaries 'd1' and 'd2' in a resulting dictionary, with the 191 values of the contributing dictionaries being themselves combined such that 192 a "product" of the values for a given key are stored in the combined 193 dictionary. 194 195 For example: 196 197 d1: {'a' : [{'f', 'g'}, {'f', 'h'}], ...} 198 d2: {'a' : [{'f'}, {'e', 'f', 'g'}], ...} 199 -> {'a' : [{'f', 'g'}, {'f', 'h'}, {'e', 'f', 'g'}, {'e', 'f', 'g', 'h'}], ...} 200 201 Note that items of 'd2' whose keys are not in 'd1' are not added to 'd1' 202 since this, in the context of propagating attribute usage observations, 203 would result in spurious usage details being made available in places where 204 the names may not have been defined. 205 """ 206 207 return combine(d1, d2, {}, combine_object_set_lists, True) 208 209 def combine(d1, d2, combined, combine_op, only_d1_keys=False): 210 211 """ 212 Combine dictionaries 'd1' and 'd2' in the 'combined' object provided, using 213 the 'combine_op' to merge values from the dictionaries. 214 215 If 'only_d1_keys' is set to a true value, items from 'd2' employing keys not 216 in 'd1' will not be added to 'd1'. 217 """ 218 219 if d2 is not None: 220 d2_keys = d2.keys() 221 222 for key in d2_keys: 223 if not d1.has_key(key): 224 if not only_d1_keys: 225 combined[key] = d2[key] 226 else: 227 combined[key] = combine_op(d1[key], d2[key]) 228 else: 229 d2_keys = () 230 231 for key in d1.keys(): 232 if key not in d2_keys: 233 combined[key] = d1[key] 234 235 return combined 236 237 def combine_object_set_lists(l1, l2): 238 239 """ 240 Combine lists of object sets 'l1' and 'l2' to make a product of their 241 members. 242 """ 243 244 # If either list is undefined (indicated by None), return the defined list, 245 # or return None if neither is defined. 246 247 if l1 is None: 248 if l2 is None: 249 return None 250 else: 251 return l2 + [] 252 elif l2 is None: 253 return l1 + [] 254 255 combined = ObjectSet() 256 for i1 in l1: 257 for i2 in l2: 258 combined.add(i1.merge(i2)) 259 return combined 260 261 # Visitors and activities related to node annotations. 262 263 class ASTVisitor(compiler.visitor.ASTVisitor): 264 265 "A base class for visitors." 266 267 def dispatch(self, node, *args): 268 269 "Dispatch using 'node', annotating any raised exceptions." 270 271 try: 272 return compiler.visitor.ASTVisitor.dispatch(self, node, *args) 273 except NodeProcessingError, exc: 274 if exc.astnode is None: 275 exc.astnode = node 276 277 # NOTE: Should perhaps specialise the subclasses appropriately. 278 279 if hasattr(self, "unit"): 280 exc.unit_name = self.unit.full_name() 281 else: 282 exc.unit_name = self.full_name() 283 raise 284 285 def possible_accessor_types(self, node, defining_users=1): 286 287 """ 288 Given annotations made during the inspection process, return all possible 289 type names and indications of static usage for a 'node' involved in 290 attribute access. 291 292 If 'defining_users' is set to a false value, attempt to get the type 293 names specifically applicable to the node, rather than retrieving more 294 general definition-based type observations. 295 """ 296 297 target_names = set() 298 299 if hasattr(node, "_attrusers"): 300 301 # Visit each attribute user. 302 303 for user in node._attrusers: 304 305 # Since users such as branches may not provide type information, 306 # attempt to find defining users. 307 308 if defining_users: 309 for def_user in user._attrdefs or [user]: 310 for target_name, is_static in def_user._attrtypes.get(node._username, []): 311 target_names.add((target_name, is_static)) 312 else: 313 for target_name, is_static in user._attrspecifictypes.get(node._username, []): 314 target_names.add((target_name, is_static)) 315 316 return target_names 317 318 def used_by_unit(node): 319 320 """ 321 Return whether the definition made by a 'node' is actually employed by the 322 program unit within which it is found. 323 """ 324 325 return hasattr(node, "unit") and node.unit.parent.has_key(node.unit.name) 326 327 def get_object_types_for_usage(usage, objtable, name, unit_name): 328 329 """ 330 Return for the given attribute 'usage', using the 'objtable', the object 331 types which satisfy such usage, reporting any problems for the given 'name' 332 and 'unit_name'. Each object type is given as a tuple of the form (type, 333 is_static). 334 """ 335 336 all_objtypes = set() 337 338 for attrnames in usage: 339 attrnames = attrnames or () 340 objtypes = objtable.all_possible_objects_plus_status(attrnames) 341 if not objtypes: 342 print "Warning: usage in %r for %r finds no object supporting all attributes %r" % ( 343 unit_name, name, attrnames) 344 objtypes = objtable.any_possible_objects_plus_status(attrnames) 345 if not objtypes: 346 print "Warning: usage in %r for %r finds no object supporting any attributes %r" % ( 347 unit_name, name, attrnames) 348 349 all_objtypes.update(objtypes) 350 351 return all_objtypes 352 353 # Errors. 354 355 class ProcessingError(Exception): 356 357 "A processing error." 358 359 pass 360 361 class TableError(ProcessingError): 362 363 "An error occurring during access to a lookup table." 364 365 pass 366 367 class TableGenerationError(ProcessingError): 368 369 "An error occurring when generating a lookup table." 370 371 pass 372 373 class NodeProcessingError(ProcessingError): 374 375 "A processing error associated with a particular program node." 376 377 def __init__(self, message): 378 self.message = message 379 self.unit_name = None 380 self.astnode = None 381 382 def get_lineno(self, node): 383 if node is None: 384 return None 385 386 lineno = node.lineno 387 if lineno is not None: 388 return lineno 389 else: 390 for child in node.getChildNodes(): 391 lineno = self.get_lineno(child) 392 if lineno is not None: 393 return lineno 394 return None 395 396 def __repr__(self): 397 return "Error in %r at line %r: %s" % (self.unit_name, self.get_lineno(self.astnode), self.message) 398 399 def __str__(self): 400 return repr(self) 401 402 class InspectError(NodeProcessingError): 403 404 "An error during the module inspection process." 405 406 pass 407 408 class TranslateError(NodeProcessingError): 409 410 "An error during the module translation process." 411 412 pass 413 414 class TranslationNotImplementedError(TranslateError): 415 416 "An error caused by a node not being supported in translation." 417 418 pass 419 420 # Special representations. 421 422 class AtLeast: 423 424 "A special representation for numbers of a given value or greater." 425 426 def __init__(self, count): 427 self.count = count 428 429 def __eq__(self, other): 430 return 0 431 432 __lt__ = __le__ = __eq__ 433 434 def __ne__(self, other): 435 return 1 436 437 def __gt__(self, other): 438 if isinstance(other, AtLeast): 439 return 0 440 else: 441 return self.count > other 442 443 def __ge__(self, other): 444 if isinstance(other, AtLeast): 445 return 0 446 else: 447 return self.count >= other 448 449 def __iadd__(self, other): 450 if isinstance(other, AtLeast): 451 self.count += other.count 452 else: 453 self.count += other 454 return self 455 456 def __radd__(self, other): 457 if isinstance(other, AtLeast): 458 return AtLeast(self.count + other.count) 459 else: 460 return AtLeast(self.count + other) 461 462 def __repr__(self): 463 return "AtLeast(%r)" % self.count 464 465 # Useful data. 466 467 operator_functions = { 468 469 # Binary operations. 470 471 "Add" : "add", 472 "Bitand" : "and_", 473 "Bitor" : "or_", 474 "Bitxor" : "xor", 475 "Div" : "div", 476 "FloorDiv" : "floordiv", 477 "LeftShift" : "lshift", 478 "Mod" : "mod", 479 "Mul" : "mul", 480 "Power" : "pow", 481 "RightShift" : "rshift", 482 "Sub" : "sub", 483 484 # Unary operations. 485 486 "Invert" : "invert", 487 "UnaryAdd" : "pos", 488 "UnarySub" : "neg", 489 490 # Augmented assignment. 491 492 "+=" : "iadd", 493 "-=" : "isub", 494 "*=" : "imul", 495 "/=" : "idiv", 496 "//=" : "ifloordiv", 497 "%=" : "imod", 498 "**=" : "ipow", 499 "<<=" : "ilshift", 500 ">>=" : "irshift", 501 "&=" : "iand", 502 "^=" : "ixor", 503 "|=" : "ior", 504 505 # Comparisons. 506 507 "==" : "eq", 508 "!=" : "ne", 509 "<" : "lt", 510 "<=" : "le", 511 ">=" : "ge", 512 ">" : "gt", 513 514 # Access and slicing. 515 516 "AssSlice" : "setslice", 517 "Slice" : "getslice", 518 "AssSubscript" : "setitem", 519 "Subscript" : "getitem", 520 } 521 522 # vim: tabstop=4 expandtab shiftwidth=4