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