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 def get_object_types_for_usage(usage, objtable, name, unit_name): 264 265 """ 266 Return for the given attribute 'usage', using the 'objtable', the object 267 types which satisfy such usage, reporting any problems for the given 'name' 268 and 'unit_name'. 269 """ 270 271 all_objtypes = set() 272 273 for attrnames in usage: 274 objtypes = objtable.all_possible_objects_plus_status(attrnames) 275 if not objtypes: 276 print "Warning: usage in %r for %r finds no object supporting all attributes %r" % ( 277 unit_name, name, attrnames) 278 objtypes = objtable.any_possible_objects_plus_status(attrnames) 279 if not objtypes: 280 print "Warning: usage in %r for %r finds no object supporting any attributes %r" % ( 281 unit_name, name, attrnames) 282 283 all_objtypes.update(objtypes) 284 285 return all_objtypes 286 287 # Errors. 288 289 class ProcessingError(Exception): 290 291 "A processing error." 292 293 pass 294 295 class TableError(ProcessingError): 296 297 "An error occurring during access to a lookup table." 298 299 pass 300 301 class TableGenerationError(ProcessingError): 302 303 "An error occurring when generating a lookup table." 304 305 pass 306 307 class NodeProcessingError(ProcessingError): 308 309 "A processing error associated with a particular program node." 310 311 def __init__(self, message): 312 self.message = message 313 self.unit_name = None 314 self.astnode = None 315 316 def get_lineno(self, node): 317 lineno = node.lineno 318 if lineno is not None: 319 return lineno 320 else: 321 for child in node.getChildNodes(): 322 lineno = self.get_lineno(child) 323 if lineno is not None: 324 return lineno 325 return None 326 327 def __repr__(self): 328 return "Error in %r at line %r: %s" % (self.unit_name, self.get_lineno(self.astnode), self.message) 329 330 def __str__(self): 331 return repr(self) 332 333 class InspectError(NodeProcessingError): 334 335 "An error during the module inspection process." 336 337 pass 338 339 class TranslateError(NodeProcessingError): 340 341 "An error during the module translation process." 342 343 pass 344 345 class TranslationNotImplementedError(TranslateError): 346 347 "An error caused by a node not being supported in translation." 348 349 pass 350 351 # Special representations. 352 353 class AtLeast: 354 355 "A special representation for numbers of a given value or greater." 356 357 def __init__(self, count): 358 self.count = count 359 360 def __eq__(self, other): 361 return 0 362 363 __lt__ = __le__ = __eq__ 364 365 def __ne__(self, other): 366 return 1 367 368 def __gt__(self, other): 369 if isinstance(other, AtLeast): 370 return 0 371 else: 372 return self.count > other 373 374 def __ge__(self, other): 375 if isinstance(other, AtLeast): 376 return 0 377 else: 378 return self.count >= other 379 380 def __iadd__(self, other): 381 if isinstance(other, AtLeast): 382 self.count += other.count 383 else: 384 self.count += other 385 return self 386 387 def __radd__(self, other): 388 if isinstance(other, AtLeast): 389 return AtLeast(self.count + other.count) 390 else: 391 return AtLeast(self.count + other) 392 393 def __repr__(self): 394 return "AtLeast(%r)" % self.count 395 396 # Useful data. 397 398 operator_functions = { 399 400 # Binary operations. 401 402 "Add" : "add", 403 "Bitand" : "and_", 404 "Bitor" : "or_", 405 "Bitxor" : "xor", 406 "Div" : "div", 407 "FloorDiv" : "floordiv", 408 "LeftShift" : "lshift", 409 "Mod" : "mod", 410 "Mul" : "mul", 411 "Power" : "pow", 412 "RightShift" : "rshift", 413 "Sub" : "sub", 414 415 # Unary operations. 416 417 "Invert" : "invert", 418 "UnaryAdd" : "pos", 419 "UnarySub" : "neg", 420 421 # Augmented assignment. 422 423 "+=" : "iadd", 424 "-=" : "isub", 425 "*=" : "imul", 426 "/=" : "idiv", 427 "//=" : "ifloordiv", 428 "%=" : "imod", 429 "**=" : "ipow", 430 "<<=" : "ilshift", 431 ">>=" : "irshift", 432 "&=" : "iand", 433 "^=" : "ixor", 434 "|=" : "ior", 435 436 # Comparisons. 437 438 "==" : "eq", 439 "!=" : "ne", 440 "<" : "lt", 441 "<=" : "le", 442 ">=" : "ge", 443 ">" : "gt", 444 445 # Access and slicing. 446 447 "AssSlice" : "setslice", 448 "Slice" : "getslice", 449 "AssSubscript" : "setitem", 450 "Subscript" : "getitem", 451 } 452 453 # vim: tabstop=4 expandtab shiftwidth=4