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, None, None, None) 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 self.raw = None 206 207 def add(self, objname, attributes): 208 209 "For the given 'objname' add the given 'attributes' to the table." 210 211 self.table[objname] = attributes 212 for name, origin in attributes.items(): 213 self.attributes.add(name) 214 215 if self.displaced_list is not None: 216 self.displaced_list.add(objname, self.matrix_row(attributes)) 217 218 def object_names(self): 219 220 "Return the object names used in the table." 221 222 self.objnames = self.objnames or list(self.table.keys()) 223 return self.objnames 224 225 def attribute_names(self): 226 227 "Return the attribute names used in the table." 228 229 self.names = self.names or list(self.attributes) 230 return self.names 231 232 def get_index(self, name): 233 234 "Return the index of the given 'name'." 235 236 try: 237 return self.attribute_names().index(name) 238 except ValueError: 239 raise TableError, "Name %r is not registered as an attribute in the table." % name 240 241 def as_matrix(self): 242 243 """ 244 Return the table as a matrix mapping object names to lists of attributes 245 arranged in the order of the recorded attribute names. 246 """ 247 248 matrix = {} 249 for objname, attributes in self.table.items(): 250 matrix[objname] = self.matrix_row(attributes) 251 return matrix 252 253 def matrix_row(self, attributes): 254 255 "Return a matrix row for the given 'attributes'." 256 257 row = [] 258 for name in self.attribute_names(): 259 row.append(attributes.get(name)) 260 return row 261 262 def all_attribute_positions(self, name): 263 264 """ 265 Return a list of positions for the attribute with the given 'name' from 266 all known objects. 267 """ 268 269 all = set() 270 for attributes in self.table.values(): 271 if attributes.has_key(name): 272 all.add(attributes[name]) 273 return all 274 275 def all_possible_objects(self, names): 276 277 """ 278 Return a list of object names supporting the given attribute 'names'. 279 """ 280 281 possible = [] 282 for objname, attributes in self.table.items(): 283 found = 1 284 for name in names: 285 if not attributes.has_key(name): 286 found = 0 287 break 288 if found: 289 possible.append(objname) 290 return possible 291 292 def as_list(self): 293 294 """ 295 Return a displaced list object encoding the table in a more compact form 296 than that provided by the matrix representation. This list will be 297 updated with new entries if added to this object using the 'add' method. 298 """ 299 300 if self.displaced_list is None: 301 self.displaced_list = self.list_class(self.attribute_names()) 302 303 # Visit each row of the matrix. 304 305 matrix_by_usage = [] 306 size = len(self.attributes) 307 308 # Add rows in descending order of utilisation. 309 310 for objname, attributes in self.as_matrix().items(): 311 matrix_by_usage.append((size - attributes.count(None), objname, attributes)) 312 313 matrix_by_usage.sort() 314 matrix_by_usage.reverse() 315 316 for usage, objname, attributes in matrix_by_usage: 317 self.displaced_list.add(objname, attributes) 318 319 return self.displaced_list 320 321 def as_raw(self): 322 323 "Return the raw contents of the table as a list of values." 324 325 if self.raw is None: 326 self.raw = self.as_list().as_raw() 327 return self.raw 328 329 class ObjectTable(Table): 330 331 "An object table." 332 333 list_class = ObjectList 334 335 class ParameterTable(Table): 336 337 "A parameter table." 338 339 list_class = ParameterList 340 341 # vim: tabstop=4 expandtab shiftwidth=4