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