1 #!/usr/bin/env python 2 3 """ 4 Preparation of run-time attribute lookup tables. 5 6 Copyright (C) 2007, 2008 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 = set() 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 # Simulation methods. 56 57 def access(self, objname, attrname): 58 obj_offset = self.offsets.get(objname) 59 attr_index = self.names_index.get(attrname) 60 if obj_offset is None or attr_index is None: 61 return None 62 63 element = self.displaced[obj_offset + attr_index] 64 if element is not None: 65 index, details = element 66 if index == attr_index: 67 return details 68 69 return None 70 71 def dir(self, objname): 72 attributes = {} 73 for name in self.names: 74 attr = self.access(objname, name) 75 if attr is not None: 76 attributes[name] = attr 77 return attributes 78 79 # Update methods. 80 81 def add(self, objname, attributes): 82 83 "Add an entry for 'objname' with the given 'attributes'." 84 85 len_displaced = len(self.displaced) 86 len_attributes = len(attributes) 87 88 # Try to fit the row into the list, starting from the beginning and 89 # skipping places where an existing row has been fitted. 90 91 for offset in xrange(0, len_displaced): 92 if offset in self.offsets_used: 93 continue 94 if self._fit_row(offset, attributes, len_displaced): 95 self.offsets_used.add(offset) 96 self.offsets[objname] = offset 97 self._add_row(offset, attributes, len_displaced) 98 break 99 100 # Where a row could not be fitted within the list, add it to the 101 # end. 102 103 else: 104 self.offsets_used.add(len_displaced) 105 self.offsets[objname] = len_displaced 106 self._add_row(len_displaced, attributes, len_displaced) 107 108 def _fit_row(self, offset, attributes, len_displaced): 109 110 """ 111 Fit, at the given 'offset', the row of 'attributes' in the displaced 112 list having length 'len_displaced'. 113 Return a true value if this succeeded. 114 """ 115 116 for i, attr in enumerate(attributes): 117 if i + offset >= len_displaced: 118 break 119 element = self.displaced[i + offset] 120 if attr is not None and element is not None: 121 return 0 122 return 1 123 124 def _add_row(self, offset, attributes, len_displaced): 125 126 """ 127 Add, at the given 'offset', the row of 'attributes' in the displaced 128 list having length 'len_displaced'. 129 """ 130 131 # Extend the list if necessary. 132 133 for i in xrange(0, offset + len(attributes) - len_displaced): 134 self.displaced.append(None) 135 136 # Record the attribute details in the list. 137 138 for i, attr in enumerate(attributes): 139 if attr is not None: 140 141 # Each entry is of the form (attribute number, attribute). 142 143 self.displaced[offset+i] = i, attr 144 145 # Image production. 146 147 def as_raw(self): 148 149 "Return the raw contents of the table as a list of values." 150 151 result = [] 152 for entry in self.displaced: 153 if entry is None: 154 result.append(None) 155 else: 156 result.append(self.entry_as_raw(entry)) 157 158 return result 159 160 class ObjectList(List): 161 162 "An object list." 163 164 def entry_as_raw(self, entry): 165 attr_index, attr = entry 166 167 # Support descendants. 168 169 if isinstance(attr, Class): 170 return attr_index 171 172 if attr.parent is not None: 173 location = attr.parent.location or 0 174 else: 175 location = 0 176 if attr.position is not None: 177 position = attr.position + location + 1 # skip structure header 178 else: 179 position = None # NOTE: Should fix unpositioned attributes. 180 181 # Attribute index/code, attribute type, context instance override flag, location/position. 182 183 return (attr_index, attr.is_class_attribute(), attr.defined_within_hierarchy(), position) 184 185 class ParameterList(List): 186 187 "A parameter list." 188 189 def entry_as_raw(self, entry): 190 return entry 191 192 class Table: 193 194 "A lookup table." 195 196 TableError = TableError 197 list_class = None # overridden 198 199 def __init__(self): 200 self.attributes = set() 201 self.table = {} 202 self.objnames = [] 203 self.names = [] 204 self.displaced_list = None 205 206 def add(self, objname, attributes): 207 208 "For the given 'objname' add the given 'attributes' to the table." 209 210 self.table[objname] = attributes 211 for name, origin in attributes.items(): 212 self.attributes.add(name) 213 214 if self.displaced_list is not None: 215 self.displaced_list.add(objname, self.matrix_row(attributes)) 216 217 def object_names(self): 218 219 "Return the object names used in the table." 220 221 self.objnames = self.objnames or list(self.table.keys()) 222 return self.objnames 223 224 def attribute_names(self): 225 226 "Return the attribute names used in the table." 227 228 self.names = self.names or list(self.attributes) 229 return self.names 230 231 def get_index(self, name): 232 233 "Return the index of the given 'name'." 234 235 try: 236 return self.attribute_names().index(name) 237 except ValueError: 238 raise TableError, "Name %r is not registered as an attribute in the table." % name 239 240 def as_matrix(self): 241 242 """ 243 Return the table as a matrix mapping object names to lists of attributes 244 arranged in the order of the recorded attribute names. 245 """ 246 247 matrix = {} 248 for objname, attributes in self.table.items(): 249 matrix[objname] = self.matrix_row(attributes) 250 return matrix 251 252 def matrix_row(self, attributes): 253 254 "Return a matrix row for the given 'attributes'." 255 256 row = [] 257 for name in self.attribute_names(): 258 row.append(attributes.get(name)) 259 return row 260 261 def all_attribute_positions(self, name): 262 263 """ 264 Return a list of positions for the attribute with the given 'name' from 265 all known objects. 266 """ 267 268 all = set() 269 for attributes in self.table.values(): 270 if attributes.has_key(name): 271 all.add(attributes[name]) 272 return all 273 274 def all_possible_objects(self, names): 275 276 """ 277 Return a list of object names supporting the given attribute 'names'. 278 """ 279 280 possible = [] 281 for objname, attributes in self.table.items(): 282 found = 1 283 for name in names: 284 if not attributes.has_key(name): 285 found = 0 286 break 287 if found: 288 possible.append(objname) 289 return possible 290 291 def as_list(self): 292 293 """ 294 Return a displaced list object encoding the table in a more compact form 295 than that provided by the matrix representation. This list will be 296 updated with new entries if added to this object using the 'add' method. 297 """ 298 299 if self.displaced_list is None: 300 self.displaced_list = self.list_class(self.attribute_names()) 301 302 # Visit each row of the matrix. 303 304 matrix_by_usage = [] 305 size = len(self.attributes) 306 307 # Add rows in descending order of utilisation. 308 309 for objname, attributes in self.as_matrix().items(): 310 matrix_by_usage.append((size - attributes.count(None), objname, attributes)) 311 312 matrix_by_usage.sort() 313 matrix_by_usage.reverse() 314 315 for usage, objname, attributes in matrix_by_usage: 316 self.displaced_list.add(objname, attributes) 317 318 return self.displaced_list 319 320 def as_raw(self): 321 322 "Return the raw contents of the table as a list of values." 323 324 return self.as_list().as_raw() 325 326 class ObjectTable(Table): 327 328 "An object table." 329 330 list_class = ObjectList 331 332 class ParameterTable(Table): 333 334 "A parameter table." 335 336 list_class = ParameterList 337 338 # vim: tabstop=4 expandtab shiftwidth=4