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 24 class List: 25 26 """ 27 A displaced list containing attribute details and an index mapping names to 28 offsets in the list. This is the optimised form of the table initially 29 constructed to record object attributes. 30 """ 31 32 def __init__(self, names): 33 self.names = names 34 self.displaced = [] 35 self.offsets = {} 36 self.offsets_used = set() 37 38 self.names_index = {} 39 for i, name in enumerate(self.names): 40 self.names_index[name] = i 41 42 def __len__(self): 43 return len(self.displaced) 44 45 def __getitem__(self, i): 46 return self.displaced[i] 47 48 # Simulation methods. 49 50 def access(self, objname, attrname): 51 obj_offset = self.offsets.get(objname) 52 attr_index = self.names_index.get(attrname) 53 if obj_offset is None or attr_index is None: 54 return None 55 56 element = self.displaced[obj_offset + attr_index] 57 if element is not None: 58 offset, details = element 59 if offset == obj_offset: 60 return details 61 62 return None 63 64 def dir(self, objname): 65 attributes = {} 66 for name in self.names: 67 attr = self.access(objname, name) 68 if attr is not None: 69 attributes[name] = attr 70 return attributes 71 72 # Update methods. 73 74 def add(self, objname, attributes): 75 76 "Add an entry for 'objname' with the given 'attributes'." 77 78 len_displaced = len(self.displaced) 79 len_attributes = len(attributes) 80 81 # Try to fit the row into the list, starting from the beginning and 82 # skipping places where an existing row has been fitted. 83 84 for offset in xrange(0, len_displaced): 85 if offset in self.offsets_used: 86 continue 87 if self._fit_row(offset, attributes, len_displaced): 88 self.offsets_used.add(offset) 89 self.offsets[objname] = offset 90 self._add_row(offset, attributes, len_displaced) 91 break 92 93 # Where a row could not be fitted within the list, add it to the 94 # end. 95 96 else: 97 self.offsets_used.add(len_displaced) 98 self.offsets[objname] = len_displaced 99 self._add_row(len_displaced, attributes, len_displaced) 100 101 def _fit_row(self, offset, attributes, len_displaced): 102 103 """ 104 Fit, at the given 'offset', the row of 'attributes' in the displaced 105 list having length 'len_displaced'. 106 Return a true value if this succeeded. 107 """ 108 109 for i, attr in enumerate(attributes): 110 if i + offset >= len_displaced: 111 break 112 element = self.displaced[i + offset] 113 if attr is not None and element is not None: 114 return 0 115 return 1 116 117 def _add_row(self, offset, attributes, len_displaced): 118 119 """ 120 Add, at the given 'offset', the row of 'attributes' in the displaced 121 list having length 'len_displaced'. 122 """ 123 124 # Extend the list if necessary. 125 126 for i in xrange(0, offset + len(attributes) - len_displaced): 127 self.displaced.append(None) 128 129 # Record the offset and attribute details in the list. 130 131 for i, attr in enumerate(attributes): 132 if attr is not None: 133 self.displaced[offset+i] = offset, attr 134 135 # Image production. 136 137 def as_raw(self): 138 139 "Return the raw contents of the table as a list of values." 140 141 result = [] 142 for entry in self.displaced: 143 if entry is None: 144 result.append(None) 145 else: 146 offset, attr = entry 147 if attr.parent is not None: 148 location = attr.parent.location or 0 149 else: 150 location = 0 151 if attr.position is not None: 152 position = attr.position + location + 1 # skip structure header 153 else: 154 position = None # NOTE: Should fix unpositioned attributes. 155 156 # Class offset/code, context instance override flag, location/position. 157 158 result.append((offset, attr.defined_within_hierarchy(), position)) 159 160 return result 161 162 class Table: 163 164 "A lookup table." 165 166 TableError = TableError 167 168 def __init__(self): 169 self.attributes = set() 170 self.table = {} 171 self.objnames = [] 172 self.names = [] 173 self.displaced_list = None 174 175 def add(self, objname, attributes): 176 177 "For the given 'objname' add the given 'attributes' to the table." 178 179 self.table[objname] = attributes 180 for name, origin in attributes.items(): 181 self.attributes.add(name) 182 183 if self.displaced_list is not None: 184 self.displaced_list.add(objname, self.matrix_row(attributes)) 185 186 def object_names(self): 187 188 "Return the object names used in the table." 189 190 self.objnames = self.objnames or list(self.table.keys()) 191 return self.objnames 192 193 def attribute_names(self): 194 195 "Return the attribute names used in the table." 196 197 self.names = self.names or list(self.attributes) 198 return self.names 199 200 def get_code(self, name): 201 202 "Return the code of the given 'name'." 203 204 try: 205 return self.object_names().index(name) 206 except ValueError: 207 raise TableError, "Name %r is not registered as an object in the table." % name 208 209 def get_index(self, name): 210 211 "Return the index of the given 'name'." 212 213 try: 214 return self.attribute_names().index(name) 215 except ValueError: 216 raise TableError, "Name %r is not registered as an attribute in the table." % name 217 218 def as_matrix(self): 219 220 """ 221 Return the table as a matrix mapping object names to lists of attributes 222 arranged in the order of the recorded attribute names. 223 """ 224 225 matrix = {} 226 for objname, attributes in self.table.items(): 227 matrix[objname] = self.matrix_row(attributes) 228 return matrix 229 230 def matrix_row(self, attributes): 231 232 "Return a matrix row for the given 'attributes'." 233 234 row = [] 235 for name in self.attribute_names(): 236 row.append(attributes.get(name)) 237 return row 238 239 def all_attribute_positions(self, name): 240 241 """ 242 Return a list of positions for the attribute with the given 'name' from 243 all known objects. 244 """ 245 246 all = set() 247 for attributes in self.table.values(): 248 if attributes.has_key(name): 249 all.add(attributes[name]) 250 return all 251 252 def all_possible_objects(self, names): 253 254 """ 255 Return a list of object names supporting the given attribute 'names'. 256 """ 257 258 possible = [] 259 for objname, attributes in self.table.items(): 260 found = 1 261 for name in names: 262 if not attributes.has_key(name): 263 found = 0 264 break 265 if found: 266 possible.append(objname) 267 return possible 268 269 def as_list(self): 270 271 """ 272 Return a displaced list object encoding the table in a more compact form 273 than that provided by the matrix representation. This list will be 274 updated with new entries if added to this object using the 'add' method. 275 """ 276 277 if self.displaced_list is None: 278 self.displaced_list = List(self.attribute_names()) 279 280 # Visit each row of the matrix. 281 282 for objname, attributes in self.as_matrix().items(): 283 self.displaced_list.add(objname, attributes) 284 285 return self.displaced_list 286 287 # vim: tabstop=4 expandtab shiftwidth=4