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