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