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 if node is None: 360 return None 361 362 lineno = node.lineno 363 if lineno is not None: 364 return lineno 365 else: 366 for child in node.getChildNodes(): 367 lineno = self.get_lineno(child) 368 if lineno is not None: 369 return lineno 370 return None 371 372 def __repr__(self): 373 return "Error in %r at line %r: %s" % (self.unit_name, self.get_lineno(self.astnode), self.message) 374 375 def __str__(self): 376 return repr(self) 377 378 class InspectError(NodeProcessingError): 379 380 "An error during the module inspection process." 381 382 pass 383 384 class TranslateError(NodeProcessingError): 385 386 "An error during the module translation process." 387 388 pass 389 390 class TranslationNotImplementedError(TranslateError): 391 392 "An error caused by a node not being supported in translation." 393 394 pass 395 396 # Special representations. 397 398 class AtLeast: 399 400 "A special representation for numbers of a given value or greater." 401 402 def __init__(self, count): 403 self.count = count 404 405 def __eq__(self, other): 406 return 0 407 408 __lt__ = __le__ = __eq__ 409 410 def __ne__(self, other): 411 return 1 412 413 def __gt__(self, other): 414 if isinstance(other, AtLeast): 415 return 0 416 else: 417 return self.count > other 418 419 def __ge__(self, other): 420 if isinstance(other, AtLeast): 421 return 0 422 else: 423 return self.count >= other 424 425 def __iadd__(self, other): 426 if isinstance(other, AtLeast): 427 self.count += other.count 428 else: 429 self.count += other 430 return self 431 432 def __radd__(self, other): 433 if isinstance(other, AtLeast): 434 return AtLeast(self.count + other.count) 435 else: 436 return AtLeast(self.count + other) 437 438 def __repr__(self): 439 return "AtLeast(%r)" % self.count 440 441 # Useful data. 442 443 operator_functions = { 444 445 # Binary operations. 446 447 "Add" : "add", 448 "Bitand" : "and_", 449 "Bitor" : "or_", 450 "Bitxor" : "xor", 451 "Div" : "div", 452 "FloorDiv" : "floordiv", 453 "LeftShift" : "lshift", 454 "Mod" : "mod", 455 "Mul" : "mul", 456 "Power" : "pow", 457 "RightShift" : "rshift", 458 "Sub" : "sub", 459 460 # Unary operations. 461 462 "Invert" : "invert", 463 "UnaryAdd" : "pos", 464 "UnarySub" : "neg", 465 466 # Augmented assignment. 467 468 "+=" : "iadd", 469 "-=" : "isub", 470 "*=" : "imul", 471 "/=" : "idiv", 472 "//=" : "ifloordiv", 473 "%=" : "imod", 474 "**=" : "ipow", 475 "<<=" : "ilshift", 476 ">>=" : "irshift", 477 "&=" : "iand", 478 "^=" : "ixor", 479 "|=" : "ior", 480 481 # Comparisons. 482 483 "==" : "eq", 484 "!=" : "ne", 485 "<" : "lt", 486 "<=" : "le", 487 ">=" : "ge", 488 ">" : "gt", 489 490 # Access and slicing. 491 492 "AssSlice" : "setslice", 493 "Slice" : "getslice", 494 "AssSubscript" : "setitem", 495 "Subscript" : "getitem", 496 } 497 498 # vim: tabstop=4 expandtab shiftwidth=4