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