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