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