1 #!/usr/bin/env python 2 3 """ 4 Preparation of run-time attribute lookup tables. 5 6 Copyright (C) 2007, 2008, 2009, 2010 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.common import * 23 from micropython.data 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 0 128 return 1 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 self.all_cache = {} 217 self.any_cache = {} 218 219 def access(self, objname, attrname): 220 221 "Return the attribute entry for the given 'objname' and 'attrname'." 222 223 try: 224 entry = self.table[objname] 225 except KeyError: 226 raise TableError, "Name %r is not registered as an object in the table." % objname 227 228 try: 229 return entry[attrname] 230 except KeyError: 231 raise TableError, "Name %r is not registered as an attribute in the table." % attrname 232 233 def add(self, objname, attributes): 234 235 "For the given 'objname' add the given 'attributes' to the table." 236 237 self.table[objname] = attributes 238 for name, origin in attributes.items(): 239 self.attributes.add(name) 240 241 if self.displaced_list is not None: 242 self.displaced_list.add(objname, self.matrix_row(attributes)) 243 244 def object_names(self): 245 246 "Return the object names used in the table." 247 248 self.objnames = self.objnames or list(self.table.keys()) 249 return self.objnames 250 251 def attribute_names(self): 252 253 "Return the attribute names used in the table." 254 255 self.names = self.names or list(self.attributes) 256 return self.names 257 258 def get_index(self, name): 259 260 "Return the index of the given 'name'." 261 262 try: 263 return self.attribute_names().index(name) 264 except ValueError: 265 raise TableError, "Name %r is not registered as an attribute in the table." % name 266 267 def as_matrix(self): 268 269 """ 270 Return the table as a matrix mapping object names to lists of attributes 271 arranged in the order of the recorded attribute names. 272 """ 273 274 matrix = {} 275 for objname, attributes in self.table.items(): 276 matrix[objname] = self.matrix_row(attributes) 277 return matrix 278 279 def matrix_row(self, attributes): 280 281 "Return a matrix row for the given 'attributes'." 282 283 row = [] 284 for name in self.attribute_names(): 285 row.append(attributes.get(name)) 286 return row 287 288 def all_attribute_positions(self, name): 289 290 """ 291 Return a list of positions for the attribute with the given 'name' from 292 all known objects. 293 """ 294 295 all = set() 296 for attributes in self.table.values(): 297 if attributes.has_key(name): 298 all.add(attributes[name]) 299 return all 300 301 def all_possible_objects(self, names): 302 303 """ 304 Return a list of object names supporting the given attribute 'names'. 305 """ 306 307 if not names: 308 return self.table.keys() 309 310 possible = [] 311 for objname, attributes in self.table.items(): 312 found = 1 313 for name in names: 314 if not attributes.has_key(name): 315 found = 0 316 break 317 if found: 318 possible.append(objname) 319 return possible 320 321 def any_possible_objects(self, names): 322 323 """ 324 Return a list of object names supporting any of the given attribute 'names'. 325 """ 326 327 if not names: 328 return [] 329 330 possible = [] 331 for objname, attributes in self.table.items(): 332 found = 0 333 for name in names: 334 if attributes.has_key(name): 335 found = 1 336 break 337 if found: 338 possible.append(objname) 339 return possible 340 341 def as_list(self): 342 343 """ 344 Return a displaced list object encoding the table in a more compact form 345 than that provided by the matrix representation. This list will be 346 updated with new entries if added to this object using the 'add' method. 347 """ 348 349 if self.displaced_list is None: 350 self.displaced_list = self.list_class(self.attribute_names()) 351 352 # Visit each row of the matrix. 353 354 matrix_by_usage = [] 355 size = len(self.attributes) 356 357 # Add rows in descending order of utilisation. 358 359 for objname, attributes in self.as_matrix().items(): 360 matrix_by_usage.append((size - attributes.count(None), objname, attributes)) 361 362 matrix_by_usage.sort() 363 matrix_by_usage.reverse() 364 365 for usage, objname, attributes in matrix_by_usage: 366 self.displaced_list.add(objname, attributes) 367 368 return self.displaced_list 369 370 def as_raw(self): 371 372 "Return the raw contents of the table as a list of values." 373 374 if self.raw is None: 375 self.raw = self.as_list().as_raw() 376 return self.raw 377 378 class ObjectTable(Table): 379 380 "An object table." 381 382 list_class = ObjectList 383 384 def _objects_plus_status(self, names, fn): 385 386 """ 387 Return objects supporting attributes with the given 'names' plus whether 388 such attributes can be exclusively static or may belong to instances. A 389 list of tuples of the form (object name, is_static) is thus returned. 390 391 The given 'fn' is employed to retrieve objects having the given 'names'. 392 """ 393 394 possible = [] 395 for objname in fn(names): 396 attributes = self.table[objname] 397 398 is_static = 0 399 is_instance = 0 400 401 for name in names: 402 if not attributes.has_key(name): 403 continue 404 405 attr = attributes[name] 406 if isinstance(attr, (Class, Module)): 407 pass 408 elif attr.is_static_attribute(): 409 is_static = 1 410 else: 411 is_instance = 1 412 413 if is_static and not is_instance: 414 is_static = 1 415 else: 416 is_static = 0 417 418 possible.append((objname, is_static)) 419 420 return possible 421 422 def all_possible_objects_plus_status(self, names): 423 424 """ 425 Return all objects supporting attributes with the given 'names' plus 426 whether such attributes can be exclusively static or may belong to 427 instances. A list of tuples of the form (object name, is_static) is thus 428 returned. 429 """ 430 431 names = tuple(names) 432 if not self.all_cache.has_key(names): 433 self.all_cache[names] = self._objects_plus_status(names, self.all_possible_objects) 434 return self.all_cache[names] 435 436 def any_possible_objects_plus_status(self, names): 437 438 """ 439 Return any objects supporting attributes with the given 'names' plus 440 whether such attributes can be exclusively static or may belong to 441 instances. A list of tuples of the form (object name, is_static) is thus 442 returned. 443 """ 444 445 names = tuple(names) 446 if not self.any_cache.has_key(names): 447 self.any_cache[names] = self._objects_plus_status(names, self.any_possible_objects) 448 return self.any_cache[names] 449 450 class ParameterTable(Table): 451 452 "A parameter table." 453 454 list_class = ParameterList 455 456 # vim: tabstop=4 expandtab shiftwidth=4