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