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