1.1 --- a/micropython/data.py Sun Feb 21 22:26:08 2010 +0100
1.2 +++ b/micropython/data.py Tue Feb 23 01:30:51 2010 +0100
1.3 @@ -131,33 +131,14 @@
1.4 # Specific namespaces should define known names during initialisation.
1.5 # For example, functions can define names belonging to parameters.
1.6
1.7 - # Attribute usage, defining a consensus for each name.
1.8 -
1.9 - self.attributes_used = [{}] # stack of usage
1.10 - self.attribute_shelves = [] # stack of unmerged definitions
1.11 -
1.12 - # Attribute usage abandonment, where the usage will not contribute to
1.13 - # the consensus.
1.14 -
1.15 - self.abandon_attributes = 0 # used when a block will never contribute
1.16 -
1.17 - # Speculative attribute usage where names may not contribute to a
1.18 - # consensus beyond a branch, but where the usage will still influence
1.19 - # acceptable types for a name.
1.20 -
1.21 - self.speculative_attributes = [{}] # stack of speculative usage
1.22 - self.speculative_shelves = [] # stack of unmerged speculative definitions
1.23 -
1.24 # Attribute users, defining names which use attributes.
1.25
1.26 self.attribute_users = [{}] # stack of assignments
1.27 - self.all_attribute_users = [{}] # stack of assignments (to record any usage)
1.28 self.user_shelves = []
1.29
1.30 # Define attribute usage to identify active program sections.
1.31
1.32 - self.all_usage_shelves = [] # stack of unmerged coverage-related definitions
1.33 - self.all_attributes_used = []
1.34 + self.all_attribute_users = set()
1.35
1.36 # Attribute/name definition and access.
1.37
1.38 @@ -328,8 +309,9 @@
1.39 """
1.40
1.41 usage = set()
1.42 - for names in self.all_attributes_used:
1.43 - usage.add(tuple(names))
1.44 + for user in self.all_attribute_users:
1.45 + for name, attrnames in user._attrnames.items():
1.46 + usage.add(tuple(attrnames))
1.47 return usage
1.48
1.49 def use_attribute(self, name, attrname):
1.50 @@ -348,25 +330,16 @@
1.51 with the given 'attrname'.
1.52 """
1.53
1.54 - defs = self.attributes_used[-1]
1.55 users = self.attribute_users[-1]
1.56
1.57 - # Permit the unforeseen definition of names since some names are likely
1.58 - # to be defined by things (such as class definitions) which will not
1.59 - # require access optimisations, but which still need to be monitored.
1.60 -
1.61 - if not defs.has_key(name):
1.62 - defs[name] = set()
1.63 -
1.64 - defs[name].add(attrname)
1.65 -
1.66 # Add the usage to all current users.
1.67
1.68 if users.has_key(name):
1.69 for user in users[name]:
1.70 user._attrnames[name].add(attrname)
1.71 -
1.72 - return defs[name]
1.73 + return users[name]
1.74 + else:
1.75 + return []
1.76
1.77 def _define_attribute_user(self, node):
1.78
1.79 @@ -382,41 +355,22 @@
1.80
1.81 "Define 'node' as the user of attributes for the given 'name'."
1.82
1.83 - defs = self.attributes_used[-1]
1.84 users = self.attribute_users[-1]
1.85 - all_users = self.all_attribute_users[-1]
1.86 - speculative = self.speculative_attributes[-1]
1.87 -
1.88 - # Record the current name usage as speculative since it will not be
1.89 - # propagated any further.
1.90 -
1.91 - if not speculative.has_key(name):
1.92 - speculative[name] = defs.get(name, set())
1.93 -
1.94 - # Where speculative usage has already been recorded, just note the usage
1.95 - # for coverage purposes.
1.96 -
1.97 - else:
1.98 - self.all_usage_shelves[-1].append({name : defs[name]})
1.99
1.100 # This node overrides previous definitions.
1.101
1.102 - all_users[name] = set([node])
1.103 users[name] = set([node])
1.104 - defs[name] = set()
1.105
1.106 # Record the attribute combinations for the name.
1.107
1.108 if not hasattr(node, "_attrnames"):
1.109 node._attrnames = {}
1.110 - node._alternative_attrnames = {}
1.111
1.112 node._attrnames[name] = set()
1.113 - node._alternative_attrnames[name] = set()
1.114
1.115 - # Remember all attribute combinations.
1.116 + # Remember this user.
1.117
1.118 - self.all_attributes_used.append(defs[name])
1.119 + self.all_attribute_users.add(node)
1.120
1.121 def _new_branchpoint(self):
1.122
1.123 @@ -425,9 +379,6 @@
1.124 and subsequently converge.
1.125 """
1.126
1.127 - self.attribute_shelves.append([])
1.128 - self.speculative_shelves.append([])
1.129 - self.all_usage_shelves.append([])
1.130 self.user_shelves.append([])
1.131
1.132 def _new_branch(self):
1.133 @@ -437,28 +388,14 @@
1.134 the new branch so that it may be augmented for each name locally.
1.135 """
1.136
1.137 - d = {}
1.138 - for name, attrnames in self.attributes_used[-1].items():
1.139 - d[name] = set(attrnames)
1.140 - self.attributes_used.append(d)
1.141 -
1.142 - # In the new branch, usage does not necessarily feed back to the users
1.143 - # immediately.
1.144 -
1.145 - self.attribute_users.append({})
1.146 -
1.147 - # Retain a record of all active users.
1.148 + # Retain a record of active users.
1.149
1.150 d = {}
1.151 - d.update(self.all_attribute_users[-1])
1.152 - self.all_attribute_users.append(d)
1.153 -
1.154 - # Speculative attributes are recorded for subsequent feedback to users.
1.155 -
1.156 - self.speculative_attributes.append({})
1.157 + d.update(self.attribute_users[-1])
1.158 + self.attribute_users.append(d)
1.159
1.160 def _abandon_branch(self):
1.161 - self.abandon_attributes = 1
1.162 + pass
1.163
1.164 def _shelve_branch(self):
1.165
1.166 @@ -469,137 +406,49 @@
1.167 observations after a merge.
1.168 """
1.169
1.170 - usage = self.attributes_used.pop()
1.171 - speculative = self.speculative_attributes.pop()
1.172 -
1.173 - # Record contributing usage.
1.174 -
1.175 - if not self.abandon_attributes:
1.176 - self.attribute_shelves[-1].append(usage)
1.177 -
1.178 - # Record all usage (for coverage).
1.179 -
1.180 - self.all_usage_shelves[-1].append(usage)
1.181 -
1.182 - # Record speculative usage.
1.183 -
1.184 - if self.abandon_attributes:
1.185 - for name, attrnames in usage.items():
1.186 - if not speculative.has_key(name):
1.187 - speculative[name] = attrnames
1.188 -
1.189 - self.speculative_shelves[-1].append(speculative)
1.190 -
1.191 - # NOTE: Could record contributing usage as speculative usage.
1.192 -
1.193 - #self.speculative_shelves[-1].append(usage)
1.194 -
1.195 - # Forget about any nodes which defined names employing attributes in
1.196 - # this branch if the branch is abandoned.
1.197 -
1.198 users = self.attribute_users.pop()
1.199 -
1.200 - if not self.abandon_attributes:
1.201 - self.user_shelves[-1].append(users)
1.202 -
1.203 - self.all_attribute_users.pop()
1.204 - self.abandon_attributes = 0
1.205 + self.user_shelves[-1].append(users)
1.206
1.207 def _merge_branches(self):
1.208
1.209 """
1.210 - Merge control-flow branches. This should find the intersection of the
1.211 - usage contributions from each branch, which have been "shelved", and
1.212 - update the active usage dictionary with these contributions.
1.213 -
1.214 - Where branches are "abandoned", their attribute usage will not affect
1.215 - the subsequent usage observations, but such usage will be recorded in
1.216 - order to deduce function usage.
1.217 + Merge control-flow branches. This should find the users active within
1.218 + each branch, which have been "shelved", and update the active users
1.219 + dictionary with these contributions.
1.220 """
1.221
1.222 - # The active dictionary holds the usage for names defined before the
1.223 - # branches. The users dictionary holds the active users defining each
1.224 - # name.
1.225 -
1.226 - active = self.attributes_used[-1]
1.227 - users = self.attribute_users[-1]
1.228 - all_users = self.all_attribute_users[-1]
1.229 - speculative = self.speculative_attributes[-1]
1.230 -
1.231 - # Take each alternative branch, currently shelved, and find the
1.232 - # intersection of their contributions for each name.
1.233 -
1.234 - # Where branches contribute attribute usage observations, process these
1.235 - # as described above. Otherwise, preserve the previous observations.
1.236 -
1.237 - shelved_defs = self.attribute_shelves.pop()
1.238 -
1.239 - if shelved_defs:
1.240 - defs = dict(shelved_defs[0])
1.241 -
1.242 - for next_defs in shelved_defs[1:]:
1.243 - for name, attrnames in next_defs.items():
1.244 - if defs.has_key(name):
1.245 - defs[name] = defs[name].intersection(attrnames)
1.246 -
1.247 - # Intersect the contributions with the previous state for each name.
1.248 -
1.249 - for name, attrnames in defs.items():
1.250 - if active.has_key(name):
1.251 - active[name].intersection_update(attrnames)
1.252 - else:
1.253 - active[name] = attrnames
1.254 -
1.255 - # Feed speculative definitions back to the users previously known.
1.256 -
1.257 - speculative_defs = self.speculative_shelves.pop()
1.258 -
1.259 - if speculative_defs:
1.260 - for defs in speculative_defs:
1.261 - for name, attrnames in defs.items():
1.262 -
1.263 - # Where users are active for a name, produce alternatives.
1.264 -
1.265 - if all_users.has_key(name):
1.266 - for node in all_users[name]:
1.267 -
1.268 - # Add the usage to the alternatives.
1.269 -
1.270 - if not node._alternative_attrnames.has_key(name):
1.271 - node._alternative_attrnames[name] = set([tuple(attrnames)])
1.272 - else:
1.273 - node._alternative_attrnames[name].add(tuple(attrnames))
1.274 -
1.275 # Combine the attribute users. This ensures that a list of users
1.276 # affected by attribute usage is maintained for the current branch.
1.277
1.278 - for shelved_users in self.user_shelves.pop():
1.279 - for name, nodes in shelved_users.items():
1.280 + users = self.attribute_users[-1]
1.281 + new_users = {}
1.282
1.283 - # Handle cases where the name is not known at this level.
1.284 + all_shelved_users = self.user_shelves.pop()
1.285 + all_user_names = set()
1.286
1.287 - if users.has_key(name):
1.288 - users[name].update(nodes)
1.289 - else:
1.290 - users[name] = nodes
1.291 + # Find all the names defined by the branches.
1.292
1.293 - # Where each shelved set of definitions is a superset of the eventual
1.294 - # definitions for a name, record these specialised sets of usage.
1.295 + for shelved_users in all_shelved_users:
1.296 + all_user_names.update(shelved_users.keys())
1.297 +
1.298 + # Copy all definitions from the branches for the names, maintaining
1.299 + # the existing users where a branch does not redefine a name.
1.300
1.301 - # Note that abandoned definitions contribute to sets of usage, since
1.302 - # although they do not contribute to further usage in a namespace, any
1.303 - # attribute combinations do indicate function usage.
1.304 + for shelved_users in all_shelved_users:
1.305 + for name in all_user_names:
1.306
1.307 - all_usage_defs = self.all_usage_shelves.pop()
1.308 + if shelved_users.has_key(name):
1.309 + nodes = shelved_users[name]
1.310 + else:
1.311 + nodes = users.get(name, set())
1.312
1.313 - for defs in all_usage_defs:
1.314 - for name, attrnames in defs.items():
1.315 + if nodes:
1.316 + if not new_users.has_key(name):
1.317 + new_users[name] = nodes
1.318 + else:
1.319 + new_users[name].update(nodes)
1.320
1.321 - # Check for isolated pockets of attribute usage as well as more
1.322 - # specific usage.
1.323 -
1.324 - if not active.has_key(name) or attrnames.issuperset(active[name]):
1.325 - self.all_attributes_used.append(attrnames)
1.326 + self.attribute_users[-1] = new_users
1.327
1.328 # Program data structures.
1.329