1 #!/usr/bin/env python 2 3 """ 4 Preparation of run-time attribute lookup tables. 5 6 Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013 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 from micropython.data import * 23 from micropython.errors import * 24 25 class List: 26 27 """ 28 A displaced list containing attribute details and an index mapping names to 29 offsets in the list. This is the optimised form of the table initially 30 constructed to record object attributes. 31 """ 32 33 def __init__(self, names): 34 self.names = names 35 self.displaced = [] 36 self.offsets = {} 37 self.offsets_used = {} 38 39 self.names_index = {} 40 for i, name in enumerate(self.names): 41 self.names_index[name] = i 42 43 def __len__(self): 44 return len(self.displaced) 45 46 def __getitem__(self, i): 47 return self.displaced[i] 48 49 def get_code(self, name): 50 51 "Return the code/offset of the given 'name'." 52 53 return self.offsets.get(name) 54 55 def get_name(self, code): 56 57 "Return the name for the given 'code' or offset." 58 59 return self.offsets_used[code] 60 61 # Simulation methods. 62 63 def access(self, objname, attrname): 64 obj_offset = self.offsets.get(objname) 65 attr_index = self.names_index.get(attrname) 66 if obj_offset is None or attr_index is None: 67 return None 68 69 element = self.displaced[obj_offset + attr_index] 70 if element is not None: 71 index, details = element 72 if index == attr_index: 73 return details 74 75 return None 76 77 def dir(self, objname): 78 attributes = {} 79 for name in self.names: 80 attr = self.access(objname, name) 81 if attr is not None: 82 attributes[name] = attr 83 return attributes 84 85 # Update methods. 86 87 def add(self, objname, attributes): 88 89 "Add an entry for 'objname' with the given 'attributes'." 90 91 len_displaced = len(self.displaced) 92 len_attributes = len(attributes) 93 94 # Try to fit the row into the list, starting from the beginning and 95 # skipping places where an existing row has been fitted. 96 97 for offset in xrange(0, len_displaced): 98 if self.offsets_used.has_key(offset): 99 continue 100 if self._fit_row(offset, attributes, len_displaced): 101 self.offsets_used[offset] = objname 102 self.offsets[objname] = offset 103 self._add_row(offset, attributes, len_displaced) 104 break 105 106 # Where a row could not be fitted within the list, add it to the 107 # end. 108 109 else: 110 self.offsets_used[len_displaced] = objname 111 self.offsets[objname] = len_displaced 112 self._add_row(len_displaced, attributes, len_displaced) 113 114 def _fit_row(self, offset, attributes, len_displaced): 115 116 """ 117 Fit, at the given 'offset', the row of 'attributes' in the displaced 118 list having length 'len_displaced'. 119 Return a true value if this succeeded. 120 """ 121 122 for i, attr in enumerate(attributes): 123 if i + offset >= len_displaced: 124 break 125 element = self.displaced[i + offset] 126 if attr is not None and element is not None: 127 return False 128 return True 129 130 def _add_row(self, offset, attributes, len_displaced): 131 132 """ 133 Add, at the given 'offset', the row of 'attributes' in the displaced 134 list having length 'len_displaced'. 135 """ 136 137 # Extend the list if necessary. 138 139 for i in xrange(0, offset + len(attributes) - len_displaced): 140 self.displaced.append(None) 141 142 # Record the attribute details in the list. 143 144 for i, attr in enumerate(attributes): 145 if attr is not None: 146 147 # Each entry is of the form (attribute number, attribute). 148 149 self.displaced[offset+i] = i, attr 150 151 # Image production. 152 153 def as_raw(self): 154 155 "Return the raw contents of the table as a list of values." 156 157 result = [] 158 for entry in self.displaced: 159 if entry is None: 160 result.append(None) 161 else: 162 result.append(self.entry_as_raw(entry)) 163 164 return result 165 166 class ObjectList(List): 167 168 "An object list." 169 170 def entry_as_raw(self, entry): 171 attr_index, attr = entry 172 173 # Support descendants. 174 175 if isinstance(attr, (Class, Module)): 176 return (attr_index, None, None) 177 178 # Get the absolute location for classes and modules. 179 180 if attr.parent is not None and attr.is_static_attribute(): 181 location = attr.parent.location or 0 182 else: 183 location = 0 184 185 if attr.position is not None: 186 position = attr.position + location + 1 # skip structure header 187 else: 188 position = None # NOTE: Should fix unpositioned attributes. 189 190 # Attribute index/code, attribute type, location/position. 191 192 return (attr_index, attr.is_static_attribute(), position) 193 194 class ParameterList(List): 195 196 "A parameter list." 197 198 def entry_as_raw(self, entry): 199 # param_index, position = entry 200 return entry 201 202 class Table: 203 204 "A lookup table." 205 206 TableError = TableError 207 list_class = None # overridden 208 209 def __init__(self): 210 self.attributes = set() 211 self.table = {} 212 self.objnames = [] 213 self.names = [] 214 self.displaced_list = None 215 self.raw = None 216 217 # Caches. 218 219 self.all_cache = {} 220 self.any_cache = {} 221 222 def access(self, objname, attrname): 223 224 "Return the attribute entry for the given 'objname' and 'attrname'." 225 226 try: 227 entry = self.table[objname] 228 except KeyError: 229 raise TableError, "Name %r is not registered as an object in the table." % objname 230 231 try: 232 return entry[attrname] 233 except KeyError: 234 raise TableError, "Name %r is not registered as an attribute in the table." % attrname 235 236 def has(self, objname): 237 238 "Return whether the table has a definition for 'objname'." 239 240 return self.table.has_key(objname) 241 242 def get(self, objname): 243 244 "Return the attributes for 'objname'." 245 246 return self.table[objname] 247 248 def add(self, objname, attributes): 249 250 "For the given 'objname' add the given 'attributes' to the table." 251 252 self.table[objname] = attributes 253 for name, origin in attributes.items(): 254 self.attributes.add(name) 255 256 if self.displaced_list is not None: 257 self.displaced_list.add(objname, self.matrix_row(attributes)) 258 259 def object_names(self): 260 261 "Return the object names used in the table." 262 263 self.objnames = self.objnames or list(self.table.keys()) 264 return self.objnames 265 266 def attribute_names(self): 267 268 "Return the attribute names used in the table." 269 270 self.names = self.names or list(self.attributes) 271 return self.names 272 273 def get_index(self, name): 274 275 "Return the index of the given 'name'." 276 277 try: 278 return self.attribute_names().index(name) 279 except ValueError: 280 raise TableError, "Name %r is not registered as an attribute in the table." % name 281 282 def as_matrix(self): 283 284 """ 285 Return the table as a matrix mapping object names to lists of attributes 286 arranged in the order of the recorded attribute names. 287 """ 288 289 matrix = {} 290 for objname, attributes in self.table.items(): 291 matrix[objname] = self.matrix_row(attributes) 292 return matrix 293 294 def matrix_row(self, attributes): 295 296 "Return a matrix row for the given 'attributes'." 297 298 row = [] 299 for name in self.attribute_names(): 300 row.append(attributes.get(name)) 301 return row 302 303 def all_attribute_positions(self, name): 304 305 """ 306 Return a list of positions for the attribute with the given 'name' from 307 all known objects. 308 """ 309 310 all = set() 311 for attributes in self.table.values(): 312 if attributes.has_key(name): 313 all.add(attributes[name]) 314 return all 315 316 def all_possible_objects(self, names): 317 318 """ 319 Return a list of object names supporting the given attribute 'names'. 320 """ 321 322 if not names: 323 return self.table.keys() 324 325 possible = [] 326 for objname, attributes in self.table.items(): 327 found = True 328 for name in names: 329 if not attributes.has_key(name): 330 found = False 331 break 332 if found: 333 possible.append(objname) 334 return possible 335 336 def any_possible_objects(self, names): 337 338 """ 339 Return a list of object names supporting any of the given attribute 'names'. 340 """ 341 342 if not names: 343 return [] 344 345 possible = [] 346 for objname, attributes in self.table.items(): 347 found = False 348 for name in names: 349 if attributes.has_key(name): 350 found = True 351 break 352 if found: 353 possible.append(objname) 354 return possible 355 356 def as_list(self): 357 358 """ 359 Return a displaced list object encoding the table in a more compact form 360 than that provided by the matrix representation. This list will be 361 updated with new entries if added to this object using the 'add' method. 362 """ 363 364 if self.displaced_list is None: 365 self.displaced_list = self.list_class(self.attribute_names()) 366 367 # Visit each row of the matrix. 368 369 matrix_by_usage = [] 370 size = len(self.attributes) 371 372 # Add rows in descending order of utilisation. 373 374 for objname, attributes in self.as_matrix().items(): 375 matrix_by_usage.append((size - attributes.count(None), objname, attributes)) 376 377 matrix_by_usage.sort() 378 matrix_by_usage.reverse() 379 380 for usage, objname, attributes in matrix_by_usage: 381 self.displaced_list.add(objname, attributes) 382 383 return self.displaced_list 384 385 def as_raw(self): 386 387 "Return the raw contents of the table as a list of values." 388 389 if self.raw is None: 390 self.raw = self.as_list().as_raw() 391 return self.raw 392 393 class ObjectTable(Table): 394 395 "An object table." 396 397 list_class = ObjectList 398 399 def _objects_plus_status(self, names, fn): 400 401 """ 402 Return objects supporting attributes with the given 'names' plus whether 403 such attributes can be exclusively static or may belong to instances. A 404 list of tuples of the form (object name, is_static) is thus returned. 405 406 The given 'fn' is employed to retrieve objects having the given 'names'. 407 """ 408 409 possible = [] 410 for objname in fn(names): 411 attributes = self.table[objname] 412 413 is_static = False 414 is_instance = False 415 416 for name in names: 417 if not attributes.has_key(name): 418 continue 419 420 attr = attributes[name] 421 if isinstance(attr, (Class, Module)): 422 pass 423 elif attr.is_static_attribute(): 424 is_static = True 425 else: 426 is_instance = True 427 428 if is_static and not is_instance: 429 is_static = True 430 else: 431 is_static = False 432 433 possible.append((objname, is_static)) 434 435 return possible 436 437 def all_possible_objects_plus_status(self, names): 438 439 """ 440 Return all objects supporting attributes with the given 'names' plus 441 whether such attributes can be exclusively static or may belong to 442 instances. A list of tuples of the form (object name, is_static) is thus 443 returned. 444 """ 445 446 names = tuple(names) 447 if not self.all_cache.has_key(names): 448 self.all_cache[names] = self._objects_plus_status(names, self.all_possible_objects) 449 return self.all_cache[names] 450 451 def any_possible_objects_plus_status(self, names): 452 453 """ 454 Return any objects supporting attributes with the given 'names' plus 455 whether such attributes can be exclusively static or may belong to 456 instances. A list of tuples of the form (object name, is_static) is thus 457 returned. 458 """ 459 460 names = tuple(names) 461 if not self.any_cache.has_key(names): 462 self.any_cache[names] = self._objects_plus_status(names, self.any_possible_objects) 463 return self.any_cache[names] 464 465 def get_object(self, objname): 466 467 """ 468 Return the object for the given 'objname' using a special entry in the 469 table. 470 """ 471 472 # NOTE: This depends on a special entry in the table for class 473 # NOTE: equivalence tests. 474 475 return self.access(objname, "#" + objname) 476 477 class ParameterTable(Table): 478 479 "A parameter table." 480 481 list_class = ParameterList 482 483 # vim: tabstop=4 expandtab shiftwidth=4