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 "Update 'new_dict' with the contents of the set dictionary 'dicts'." 159 160 for old_dict in dicts: 161 for key, value in old_dict.items(): 162 if not new_dict.has_key(key): 163 if value is not None: 164 new_dict[key] = ObjectSet(value) 165 else: 166 new_dict[key] = None 167 elif new_dict[key] is not None: 168 if value is not None: 169 new_dict[key].update(value) 170 else: 171 new_dict[key].add(value) 172 else: 173 if value is not None: 174 objset = new_dict[key] = ObjectSet(value) 175 objset.add(None) 176 177 def combine_mapping_dicts(d1, d2): 178 179 """ 180 Combine dictionaries 'd1' and 'd2' in a resulting dictionary, with the 181 values of the contributing dictionaries being themselves combined such that 182 a "product" of the values for a given key are stored in the combined 183 dictionary. 184 185 For example: 186 187 d1: {'a' : [{'f', 'g'}, {'f', 'h'}], ...} 188 d2: {'a' : [{'f'}, {'e', 'f', 'g'}], ...} 189 -> {'a' : [{'f', 'g'}, {'f', 'h'}, {'e', 'f', 'g'}, {'e', 'f', 'g', 'h'}], ...} 190 191 Note that items of 'd2' whose keys are not in 'd1' are not added to 'd1' 192 since this, in the context of propagating attribute usage observations, 193 would result in spurious usage details being made available in places where 194 the names may not have been defined. 195 """ 196 197 return combine(d1, d2, {}, combine_object_set_lists, True) 198 199 def combine(d1, d2, combined, combine_op, only_d1_keys=False): 200 201 """ 202 Combine dictionaries 'd1' and 'd2' in the 'combined' object provided, using 203 the 'combine_op' to merge values from the dictionaries. 204 205 If 'only_d1_keys' is set to a true value, items from 'd2' employing keys not 206 in 'd1' will not be added to 'd1'. 207 """ 208 209 if d2 is not None: 210 d2_keys = d2.keys() 211 212 for key in d2_keys: 213 if not d1.has_key(key): 214 if not only_d1_keys: 215 combined[key] = d2[key] 216 else: 217 combined[key] = combine_op(d1[key], d2[key]) 218 else: 219 d2_keys = () 220 221 for key in d1.keys(): 222 if key not in d2_keys: 223 combined[key] = d1[key] 224 225 return combined 226 227 def combine_object_set_lists(l1, l2): 228 229 """ 230 Combine lists of object sets 'l1' and 'l2' to make a product of their 231 members. 232 """ 233 234 # If either list is undefined (indicated by None), return the defined list, 235 # or return None if neither is defined. 236 237 if l1 is None: 238 if l2 is None: 239 return None 240 else: 241 return l2 + [] 242 elif l2 is None: 243 return l1 + [] 244 245 combined = ObjectSet() 246 for i1 in l1: 247 for i2 in l2: 248 combined.add(i1.merge(i2)) 249 return combined 250 251 # Visitors and activities related to node annotations. 252 253 class ASTVisitor(compiler.visitor.ASTVisitor): 254 255 "A base class for visitors." 256 257 def dispatch(self, node, *args): 258 259 "Dispatch using 'node', annotating any raised exceptions." 260 261 try: 262 return compiler.visitor.ASTVisitor.dispatch(self, node, *args) 263 except NodeProcessingError, exc: 264 if exc.astnode is None: 265 exc.astnode = node 266 267 # NOTE: Should perhaps specialise the subclasses appropriately. 268 269 if hasattr(self, "unit"): 270 exc.unit_name = self.unit.full_name() 271 else: 272 exc.unit_name = self.full_name() 273 raise 274 275 def possible_accessor_types(self, node): 276 277 """ 278 Given annotations made during the inspection process, return all possible 279 type names and indications of static usage for a 'node' involved in 280 attribute access. 281 """ 282 283 target_names = set() 284 285 if hasattr(node, "_attrusers"): 286 287 # Visit each attribute user. 288 289 for user in node._attrusers: 290 291 # Since users such as branches may not provide type information, 292 # attempt to find defining users. 293 294 for def_user in user._attrdefs or [user]: 295 for target_name, is_static in def_user._attrtypes.get(node._username, []): 296 target_names.add((target_name, is_static)) 297 298 return target_names 299 300 def used_by_unit(node): 301 302 """ 303 Return whether the definition made by a 'node' is actually employed by the 304 program unit within which it is found. 305 """ 306 307 return hasattr(node, "unit") and node.unit.parent.has_key(node.unit.name) 308 309 def get_object_types_for_usage(usage, objtable, name, unit_name): 310 311 """ 312 Return for the given attribute 'usage', using the 'objtable', the object 313 types which satisfy such usage, reporting any problems for the given 'name' 314 and 'unit_name'. Each object type is given as a tuple of the form (type, 315 is_static). 316 """ 317 318 all_objtypes = set() 319 320 for attrnames in usage: 321 attrnames = attrnames or () 322 objtypes = objtable.all_possible_objects_plus_status(attrnames) 323 if not objtypes: 324 print "Warning: usage in %r for %r finds no object supporting all attributes %r" % ( 325 unit_name, name, attrnames) 326 objtypes = objtable.any_possible_objects_plus_status(attrnames) 327 if not objtypes: 328 print "Warning: usage in %r for %r finds no object supporting any attributes %r" % ( 329 unit_name, name, attrnames) 330 331 all_objtypes.update(objtypes) 332 333 return all_objtypes 334 335 # Errors. 336 337 class ProcessingError(Exception): 338 339 "A processing error." 340 341 pass 342 343 class TableError(ProcessingError): 344 345 "An error occurring during access to a lookup table." 346 347 pass 348 349 class TableGenerationError(ProcessingError): 350 351 "An error occurring when generating a lookup table." 352 353 pass 354 355 class NodeProcessingError(ProcessingError): 356 357 "A processing error associated with a particular program node." 358 359 def __init__(self, message): 360 self.message = message 361 self.unit_name = None 362 self.astnode = None 363 364 def get_lineno(self, node): 365 if node is None: 366 return None 367 368 lineno = node.lineno 369 if lineno is not None: 370 return lineno 371 else: 372 for child in node.getChildNodes(): 373 lineno = self.get_lineno(child) 374 if lineno is not None: 375 return lineno 376 return None 377 378 def __repr__(self): 379 return "Error in %r at line %r: %s" % (self.unit_name, self.get_lineno(self.astnode), self.message) 380 381 def __str__(self): 382 return repr(self) 383 384 class InspectError(NodeProcessingError): 385 386 "An error during the module inspection process." 387 388 pass 389 390 class TranslateError(NodeProcessingError): 391 392 "An error during the module translation process." 393 394 pass 395 396 class TranslationNotImplementedError(TranslateError): 397 398 "An error caused by a node not being supported in translation." 399 400 pass 401 402 # Special representations. 403 404 class AtLeast: 405 406 "A special representation for numbers of a given value or greater." 407 408 def __init__(self, count): 409 self.count = count 410 411 def __eq__(self, other): 412 return 0 413 414 __lt__ = __le__ = __eq__ 415 416 def __ne__(self, other): 417 return 1 418 419 def __gt__(self, other): 420 if isinstance(other, AtLeast): 421 return 0 422 else: 423 return self.count > other 424 425 def __ge__(self, other): 426 if isinstance(other, AtLeast): 427 return 0 428 else: 429 return self.count >= other 430 431 def __iadd__(self, other): 432 if isinstance(other, AtLeast): 433 self.count += other.count 434 else: 435 self.count += other 436 return self 437 438 def __radd__(self, other): 439 if isinstance(other, AtLeast): 440 return AtLeast(self.count + other.count) 441 else: 442 return AtLeast(self.count + other) 443 444 def __repr__(self): 445 return "AtLeast(%r)" % self.count 446 447 # Useful data. 448 449 operator_functions = { 450 451 # Binary operations. 452 453 "Add" : "add", 454 "Bitand" : "and_", 455 "Bitor" : "or_", 456 "Bitxor" : "xor", 457 "Div" : "div", 458 "FloorDiv" : "floordiv", 459 "LeftShift" : "lshift", 460 "Mod" : "mod", 461 "Mul" : "mul", 462 "Power" : "pow", 463 "RightShift" : "rshift", 464 "Sub" : "sub", 465 466 # Unary operations. 467 468 "Invert" : "invert", 469 "UnaryAdd" : "pos", 470 "UnarySub" : "neg", 471 472 # Augmented assignment. 473 474 "+=" : "iadd", 475 "-=" : "isub", 476 "*=" : "imul", 477 "/=" : "idiv", 478 "//=" : "ifloordiv", 479 "%=" : "imod", 480 "**=" : "ipow", 481 "<<=" : "ilshift", 482 ">>=" : "irshift", 483 "&=" : "iand", 484 "^=" : "ixor", 485 "|=" : "ior", 486 487 # Comparisons. 488 489 "==" : "eq", 490 "!=" : "ne", 491 "<" : "lt", 492 "<=" : "le", 493 ">=" : "ge", 494 ">" : "gt", 495 496 # Access and slicing. 497 498 "AssSlice" : "setslice", 499 "Slice" : "getslice", 500 "AssSubscript" : "setitem", 501 "Subscript" : "getitem", 502 } 503 504 # vim: tabstop=4 expandtab shiftwidth=4