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