paul@622 | 1 | #!/usr/bin/env python |
paul@622 | 2 | |
paul@622 | 3 | """ |
paul@622 | 4 | Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012 Paul Boddie <paul@boddie.org.uk> |
paul@622 | 5 | |
paul@622 | 6 | This program is free software; you can redistribute it and/or modify it under |
paul@622 | 7 | the terms of the GNU General Public License as published by the Free Software |
paul@622 | 8 | Foundation; either version 3 of the License, or (at your option) any later |
paul@622 | 9 | version. |
paul@622 | 10 | |
paul@622 | 11 | This program is distributed in the hope that it will be useful, but WITHOUT |
paul@622 | 12 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS |
paul@622 | 13 | FOR A PARTICULAR PURPOSE. See the GNU General Public License for more |
paul@622 | 14 | details. |
paul@622 | 15 | |
paul@622 | 16 | You should have received a copy of the GNU General Public License along with |
paul@622 | 17 | this program. If not, see <http://www.gnu.org/licenses/>. |
paul@622 | 18 | """ |
paul@622 | 19 | |
paul@622 | 20 | from micropython.errors import * |
paul@622 | 21 | from micropython.objectset import * |
paul@622 | 22 | from micropython.types import * |
paul@622 | 23 | |
paul@622 | 24 | try: |
paul@622 | 25 | set |
paul@622 | 26 | except NameError: |
paul@622 | 27 | from sets import Set as set |
paul@622 | 28 | |
paul@622 | 29 | class AttributeUsage: |
paul@622 | 30 | |
paul@622 | 31 | "Management of attribute usage in a program unit." |
paul@622 | 32 | |
paul@622 | 33 | def __init__(self): |
paul@622 | 34 | |
paul@622 | 35 | # Attributes accessed on objects, potentially narrowing their types. |
paul@622 | 36 | # Specific namespaces should define known names during initialisation. |
paul@622 | 37 | # For example, functions can define names belonging to parameters. |
paul@622 | 38 | |
paul@622 | 39 | # Attribute users, defining names which use attributes. |
paul@622 | 40 | |
paul@622 | 41 | self.attribute_users = [{}] # stack of assignments and branches |
paul@622 | 42 | |
paul@622 | 43 | # Define attribute usage to identify active program sections. |
paul@622 | 44 | # Attribute users are AST nodes defining names. |
paul@622 | 45 | |
paul@622 | 46 | self.all_attribute_users = set() |
paul@622 | 47 | |
paul@622 | 48 | # Finalisation of a program unit's information. |
paul@622 | 49 | |
paul@622 | 50 | def finalise_attribute_usage(self): |
paul@622 | 51 | |
paul@622 | 52 | "Propagate attribute usage for the namespace to the importer." |
paul@622 | 53 | |
paul@622 | 54 | module = self.module |
paul@622 | 55 | importer = module and module.importer |
paul@622 | 56 | |
paul@622 | 57 | if importer is not None: |
paul@622 | 58 | |
paul@622 | 59 | # Visit each user and examine the attribute usage for each name. |
paul@622 | 60 | |
paul@622 | 61 | for user in self.all_attribute_users: |
paul@622 | 62 | |
paul@622 | 63 | # First, visit the contributors and combine their attribute |
paul@622 | 64 | # usage with the usage recorded directly on the user. |
paul@622 | 65 | |
paul@622 | 66 | self.get_usage_from_contributors(user) |
paul@622 | 67 | |
paul@622 | 68 | # Record the defining user on each contributor. |
paul@622 | 69 | |
paul@622 | 70 | for contributor in user._attrcontributors: |
paul@622 | 71 | contributor._attrdefs.append(user) |
paul@622 | 72 | |
paul@622 | 73 | # Then, tell the importer about the usage. |
paul@622 | 74 | |
paul@622 | 75 | for name in user._attrnames.keys(): |
paul@622 | 76 | |
paul@622 | 77 | # Only provide information about names defined by this user. |
paul@622 | 78 | |
paul@622 | 79 | usage = user._attrcombined.get(name, []) |
paul@622 | 80 | |
paul@622 | 81 | # Skip reporting where no actual usage occurs. |
paul@622 | 82 | |
paul@622 | 83 | if usage is None: |
paul@622 | 84 | continue |
paul@622 | 85 | |
paul@622 | 86 | # Eliminate non-usage. |
paul@622 | 87 | |
paul@622 | 88 | importer.use_names(user, name, tuple([attrnames for attrnames in usage if attrnames]), self.full_name()) |
paul@622 | 89 | |
paul@622 | 90 | def finalise_users(self, objtable): |
paul@622 | 91 | |
paul@622 | 92 | "Record the object types for generating guards." |
paul@622 | 93 | |
paul@622 | 94 | # Visit each user and examine the attribute usage for each name. |
paul@622 | 95 | |
paul@622 | 96 | for user in self.all_attribute_users: |
paul@622 | 97 | user._attrtypes = self._deduce_types(user._attrcombined, objtable) |
paul@622 | 98 | self._finalise_contributor(user, objtable) |
paul@622 | 99 | |
paul@622 | 100 | def _finalise_contributors(self, node, objtable): |
paul@622 | 101 | |
paul@622 | 102 | """ |
paul@622 | 103 | Visit the contributing branches of 'node', finalising them using the |
paul@622 | 104 | given 'objtable'. |
paul@622 | 105 | """ |
paul@622 | 106 | |
paul@622 | 107 | for contributor in node._attrbranches: |
paul@622 | 108 | self._finalise_contributor(contributor, objtable) |
paul@622 | 109 | |
paul@622 | 110 | def _finalise_contributor(self, node, objtable): |
paul@622 | 111 | |
paul@622 | 112 | """ |
paul@622 | 113 | Record the specific object types being used in various regions of a |
paul@622 | 114 | program unit. |
paul@622 | 115 | """ |
paul@622 | 116 | |
paul@622 | 117 | if node._attrspecifictypes is None: |
paul@622 | 118 | merged = {} |
paul@622 | 119 | |
paul@622 | 120 | # Get the combined usage information from the user definitions. |
paul@622 | 121 | |
paul@622 | 122 | for user in node._attrdefs or [node]: |
paul@622 | 123 | |
paul@622 | 124 | # Filter the usage for each name using the local usage |
paul@622 | 125 | # information. |
paul@622 | 126 | |
paul@622 | 127 | for name, usage in user._attrcombined.items(): |
paul@622 | 128 | localusage = node._attrnames.get(name) |
paul@622 | 129 | |
paul@622 | 130 | if usage and localusage: |
paul@622 | 131 | if not merged.has_key(name): |
paul@622 | 132 | merged[name] = ObjectSet() |
paul@622 | 133 | |
paul@622 | 134 | for attrnames, value in usage.items(): |
paul@622 | 135 | if attrnames and localusage.issubset(attrnames): |
paul@622 | 136 | merged[name][attrnames] = value |
paul@622 | 137 | |
paul@622 | 138 | node._attrmerged = merged |
paul@622 | 139 | node._attrspecifictypes = self._deduce_types(node._attrmerged, objtable) |
paul@622 | 140 | |
paul@622 | 141 | self._finalise_contributors(node, objtable) |
paul@622 | 142 | |
paul@622 | 143 | def _deduce_types(self, usage, objtable): |
paul@622 | 144 | |
paul@622 | 145 | """ |
paul@622 | 146 | Deduce the types for names from the given attribute 'usage' and using |
paul@622 | 147 | the given 'objtable'. |
paul@622 | 148 | """ |
paul@622 | 149 | |
paul@622 | 150 | attrtypes = {} |
paul@622 | 151 | for name, combined_usage in usage.items(): |
paul@622 | 152 | if combined_usage is not None: |
paul@622 | 153 | objtypes = get_object_types_for_usage(combined_usage, objtable, name, self.full_name(), True, self.module.importer) |
paul@622 | 154 | if objtypes: |
paul@622 | 155 | if self.is_method() and name == "self": |
paul@622 | 156 | objtypes = filter_using_self(objtypes, self.parent) |
paul@622 | 157 | attrtypes[name] = objtypes |
paul@622 | 158 | return attrtypes |
paul@622 | 159 | |
paul@622 | 160 | def get_usage_from_contributors(self, node): |
paul@622 | 161 | |
paul@622 | 162 | """ |
paul@622 | 163 | Obtain usage information from the given 'node', combined with usage |
paul@622 | 164 | details from its contributors, returning a tuple containing a set of all |
paul@622 | 165 | contributors employed along with a dictionary mapping names to lists of |
paul@622 | 166 | usage possibilities (each a collection of attribute names). |
paul@622 | 167 | """ |
paul@622 | 168 | |
paul@622 | 169 | unfinished = {} |
paul@622 | 170 | |
paul@622 | 171 | # Process any unprocessed contributors, indicating the unfinished state |
paul@622 | 172 | # of the associated data. |
paul@622 | 173 | |
paul@622 | 174 | if node._attrcombined is None: |
paul@622 | 175 | node._attrcombined = Unset |
paul@622 | 176 | |
paul@622 | 177 | for contributor in node._attrbranches: |
paul@622 | 178 | |
paul@622 | 179 | # Get contributor details. |
paul@622 | 180 | |
paul@622 | 181 | unfinished_contributors = self.get_usage_from_contributors(contributor) |
paul@622 | 182 | |
paul@622 | 183 | # Collect unfinished contributors and affected nodes. |
paul@622 | 184 | |
paul@622 | 185 | # Where the contributor is already set to Unset, a loop has |
paul@622 | 186 | # occurred and this node will need to have its usage |
paul@622 | 187 | # recalculated later for the unfinished contributor. |
paul@622 | 188 | |
paul@622 | 189 | if contributor._attrcombined is Unset: |
paul@622 | 190 | if not unfinished.has_key(contributor): |
paul@622 | 191 | unfinished[contributor] = [] |
paul@622 | 192 | unfinished[contributor].append(node) |
paul@622 | 193 | continue |
paul@622 | 194 | |
paul@622 | 195 | # Where the contributor provides usage details, it may also |
paul@622 | 196 | # communicate unfinished contributor information. As a |
paul@622 | 197 | # consequence, this node is also affected. |
paul@622 | 198 | |
paul@622 | 199 | for unfinished_contributor, nodes in unfinished_contributors.items(): |
paul@622 | 200 | if not unfinished.has_key(unfinished_contributor): |
paul@622 | 201 | unfinished[unfinished_contributor] = nodes |
paul@622 | 202 | else: |
paul@622 | 203 | unfinished[unfinished_contributor] += nodes |
paul@622 | 204 | |
paul@622 | 205 | if node not in unfinished[unfinished_contributor]: |
paul@622 | 206 | unfinished[unfinished_contributor].append(node) |
paul@622 | 207 | |
paul@622 | 208 | # Set the current state of the usage on this node. |
paul@622 | 209 | |
paul@622 | 210 | node._attrcombined, node._attrcontributors = \ |
paul@622 | 211 | self.get_usage_from_contributors_for_node(node) |
paul@622 | 212 | |
paul@622 | 213 | # Complete unfinished contributors relying on this node. |
paul@622 | 214 | |
paul@622 | 215 | if unfinished.has_key(node): |
paul@622 | 216 | processed = set() |
paul@622 | 217 | for contributor in unfinished[node]: |
paul@622 | 218 | if not contributor in processed: |
paul@622 | 219 | processed.add(contributor) |
paul@622 | 220 | |
paul@622 | 221 | contributor._attrcombined, contributor._attrcontributors = \ |
paul@622 | 222 | self.get_usage_from_contributors_for_node(contributor) |
paul@622 | 223 | |
paul@622 | 224 | del unfinished[node] |
paul@622 | 225 | |
paul@622 | 226 | return unfinished |
paul@622 | 227 | |
paul@622 | 228 | def get_usage_from_contributors_for_node(self, node): |
paul@622 | 229 | |
paul@622 | 230 | # Visit each contributor, gathering usage for each name. |
paul@622 | 231 | |
paul@622 | 232 | contributor_usage = {} |
paul@622 | 233 | all_contributions = [] |
paul@622 | 234 | all_contributors = set() |
paul@622 | 235 | |
paul@622 | 236 | for contributor in node._attrbranches: |
paul@622 | 237 | usage = contributor._attrcombined |
paul@622 | 238 | if usage is not Unset: |
paul@622 | 239 | all_contributions.append(usage) |
paul@622 | 240 | |
paul@622 | 241 | all_contributors.add(contributor) |
paul@622 | 242 | contributors = contributor._attrcontributors |
paul@622 | 243 | if contributors is not None: |
paul@622 | 244 | all_contributors.update(contributors) |
paul@622 | 245 | |
paul@622 | 246 | # Get contributed usage for each contributor. |
paul@622 | 247 | # This gathers usage for each name such as {(a, b), (c, d)} and |
paul@622 | 248 | # {(a, b), (e, f)} into a single set {(a, b), (c, d), (e, f)}. |
paul@622 | 249 | |
paul@622 | 250 | update_mapping_dict(contributor_usage, all_contributions) |
paul@622 | 251 | |
paul@622 | 252 | # Then get the resulting usage. |
paul@622 | 253 | # First, make the current usage compatible with the contributed |
paul@622 | 254 | # usage: this makes the attribute usage for each name merely one |
paul@622 | 255 | # member in a list of many possibilities. |
paul@622 | 256 | # Then, combine the current usage with the contributed usage. |
paul@622 | 257 | # Thus, usage of {(f, g)} combined with {(a, b), (c, d)} would give |
paul@622 | 258 | # {(f, g, a, b), (f, g, c, d)}. |
paul@622 | 259 | |
paul@622 | 260 | return combine_mapping_dicts(deepen_mapping_dict(node._attrnames), contributor_usage), all_contributors |
paul@622 | 261 | |
paul@622 | 262 | # Attribute usage methods. |
paul@622 | 263 | |
paul@622 | 264 | def use_attribute(self, name, attrname, value=None): |
paul@622 | 265 | |
paul@622 | 266 | """ |
paul@622 | 267 | Note usage on the attribute user 'name' of the attribute 'attrname', |
paul@622 | 268 | noting an assignment if 'value' is specified. |
paul@622 | 269 | """ |
paul@622 | 270 | |
paul@622 | 271 | return self._use_attribute(name, attrname, value) |
paul@622 | 272 | |
paul@622 | 273 | def use_specific_attribute(self, objname, attrname): |
paul@622 | 274 | |
paul@622 | 275 | "Declare the usage on 'objname' of the given 'attrname'." |
paul@622 | 276 | |
paul@622 | 277 | self._use_specific_attribute(objname, attrname) |
paul@622 | 278 | |
paul@622 | 279 | # These shadow various methods in the InspectedModule class, and provide |
paul@622 | 280 | # implementations generally. |
paul@622 | 281 | |
paul@622 | 282 | def _use_specific_attribute(self, objname, attrname, from_name=None): |
paul@622 | 283 | |
paul@622 | 284 | """ |
paul@622 | 285 | Note attribute usage specifically on 'objname' - an object which is |
paul@622 | 286 | known at inspection time - or in the current unit if 'objname' is None, |
paul@622 | 287 | nominating a specific attribute 'attrname'. |
paul@622 | 288 | |
paul@622 | 289 | This bypasses attribute user mechanisms. |
paul@622 | 290 | """ |
paul@622 | 291 | |
paul@622 | 292 | from_name = from_name or self.full_name() |
paul@622 | 293 | objname = objname or from_name |
paul@622 | 294 | module = self.module |
paul@622 | 295 | importer = module and module.importer |
paul@622 | 296 | |
paul@622 | 297 | if importer is not None: |
paul@622 | 298 | importer.use_specific_name(objname, attrname, from_name) |
paul@622 | 299 | |
paul@622 | 300 | def _use_attribute(self, name, attrname, value=None): |
paul@622 | 301 | |
paul@622 | 302 | """ |
paul@622 | 303 | Indicate the use of the given 'name' in this namespace of an attribute |
paul@622 | 304 | with the given 'attrname'. If the optional 'value' is specified, an |
paul@622 | 305 | assignment using the given 'value' is recorded. |
paul@622 | 306 | """ |
paul@622 | 307 | |
paul@622 | 308 | users = self.attribute_users[-1] |
paul@622 | 309 | |
paul@622 | 310 | # If no users are defined for the name, it cannot be handled. |
paul@622 | 311 | |
paul@622 | 312 | if not users.has_key(name): |
paul@622 | 313 | return [] |
paul@622 | 314 | |
paul@622 | 315 | # Add the usage to all current users. |
paul@622 | 316 | |
paul@622 | 317 | for user in users[name]: |
paul@622 | 318 | values = user._attrnames[name] |
paul@622 | 319 | if values is None: |
paul@622 | 320 | values = user._attrnames[name] = ObjectSet() |
paul@622 | 321 | |
paul@622 | 322 | # Add an entry for the attribute, optionally with an assigned |
paul@622 | 323 | # value. |
paul@622 | 324 | |
paul@622 | 325 | values.add(attrname) |
paul@622 | 326 | if value is not None: |
paul@622 | 327 | values[attrname].add(value) |
paul@622 | 328 | |
paul@622 | 329 | return users[name] |
paul@622 | 330 | |
paul@622 | 331 | def _define_attribute_user(self, node): |
paul@622 | 332 | |
paul@622 | 333 | """ |
paul@622 | 334 | Define 'node' as the user of attributes, indicating the point where the |
paul@622 | 335 | user is defined. |
paul@622 | 336 | """ |
paul@622 | 337 | |
paul@622 | 338 | name = node.name |
paul@622 | 339 | self._define_attribute_user_for_name(node, name) |
paul@622 | 340 | |
paul@622 | 341 | def _define_attribute_user_for_name(self, node, name): |
paul@622 | 342 | |
paul@622 | 343 | "Define 'node' as the user of attributes for the given 'name'." |
paul@622 | 344 | |
paul@622 | 345 | users = self.attribute_users[-1] |
paul@622 | 346 | |
paul@622 | 347 | # This node overrides previous definitions. |
paul@622 | 348 | |
paul@622 | 349 | users[name] = set([node]) |
paul@622 | 350 | |
paul@622 | 351 | # Record the attribute combinations for the name. |
paul@622 | 352 | |
paul@622 | 353 | self._init_attribute_user_for_name(node, name) |
paul@622 | 354 | |
paul@622 | 355 | # Remember this user. |
paul@622 | 356 | |
paul@622 | 357 | self.all_attribute_users.add(node) |
paul@622 | 358 | |
paul@622 | 359 | def _init_attribute_user_for_name(self, node, name): |
paul@622 | 360 | |
paul@622 | 361 | "Make sure that 'node' is initialised for 'name'." |
paul@622 | 362 | |
paul@622 | 363 | self._init_attribute_user(node) |
paul@622 | 364 | node._attrnames[name] = None |
paul@622 | 365 | |
paul@622 | 366 | def _init_attribute_user(self, node): |
paul@622 | 367 | |
paul@622 | 368 | # Attribute usage for names. |
paul@622 | 369 | |
paul@622 | 370 | if node._attrnames is None: |
paul@622 | 371 | node._attrnames = {} |
paul@622 | 372 | node._attrmerged = {} |
paul@622 | 373 | |
paul@622 | 374 | # Branches contributing usage to this node. |
paul@622 | 375 | |
paul@622 | 376 | if node._attrbranches is None: |
paul@622 | 377 | node._attrbranches = [] |
paul@622 | 378 | |
paul@622 | 379 | # Definitions receiving usage from this node. |
paul@622 | 380 | |
paul@622 | 381 | if node._attrdefs is None: |
paul@622 | 382 | node._attrdefs = [] |
paul@622 | 383 | |
paul@622 | 384 | def _define_attribute_accessor(self, name, attrname, node, value): |
paul@622 | 385 | |
paul@622 | 386 | # NOTE: Revisiting of nodes may occur for loops. |
paul@622 | 387 | |
paul@622 | 388 | if node._attrusers is None: |
paul@622 | 389 | node._attrusers = set() |
paul@622 | 390 | |
paul@622 | 391 | node._attrusers.update(self.use_attribute(name, attrname, value)) |
paul@622 | 392 | node._username = name |
paul@622 | 393 | |
paul@622 | 394 | class ScopeUsage: |
paul@622 | 395 | |
paul@622 | 396 | "Scope usage tracking." |
paul@622 | 397 | |
paul@622 | 398 | def __init__(self): |
paul@622 | 399 | |
paul@622 | 400 | # Scope usage, indicating the origin of names. |
paul@622 | 401 | |
paul@622 | 402 | self.scope_usage = [{}] # stack of scope usage |
paul@622 | 403 | |
paul@622 | 404 | def define_scope(self, name, scope): |
paul@622 | 405 | |
paul@622 | 406 | """ |
paul@622 | 407 | Define 'name' as being from the given 'scope' in the current namespace. |
paul@622 | 408 | """ |
paul@622 | 409 | |
paul@622 | 410 | self.scope_usage[-1][name] = scope |
paul@622 | 411 | |
paul@622 | 412 | def note_scope(self, name, scope): |
paul@622 | 413 | |
paul@622 | 414 | """ |
paul@622 | 415 | Note usage of 'name' from the given 'scope' in the current namespace. |
paul@622 | 416 | If a conflict has been recorded previously, raise an exception. |
paul@622 | 417 | """ |
paul@622 | 418 | |
paul@622 | 419 | scope_usage = self.scope_usage[-1] |
paul@622 | 420 | |
paul@622 | 421 | if scope_usage.has_key(name): |
paul@622 | 422 | found_scope = scope_usage[name] |
paul@622 | 423 | if isinstance(found_scope, ScopeConflict): |
paul@622 | 424 | raise InspectError("Scope conflict for %r: defined as %s." % ( |
paul@622 | 425 | name, ", ".join(found_scope.scopes))) |
paul@622 | 426 | |
paul@622 | 427 | scope_usage[name] = scope |
paul@622 | 428 | |
paul@622 | 429 | def used_in_scope(self, name, scope): |
paul@622 | 430 | |
paul@622 | 431 | """ |
paul@622 | 432 | Return whether 'name' is used from the given 'scope' in the current |
paul@622 | 433 | namespace. |
paul@622 | 434 | """ |
paul@622 | 435 | |
paul@622 | 436 | scope_usage = self.scope_usage[-1] |
paul@622 | 437 | return scope_usage.get(name) == scope |
paul@622 | 438 | |
paul@622 | 439 | class BranchTracking(AttributeUsage, ScopeUsage): |
paul@622 | 440 | |
paul@622 | 441 | """ |
paul@622 | 442 | Management of branches, relying on attribute usage support. |
paul@622 | 443 | """ |
paul@622 | 444 | |
paul@622 | 445 | def __init__(self): |
paul@622 | 446 | AttributeUsage.__init__(self) |
paul@622 | 447 | ScopeUsage.__init__(self) |
paul@622 | 448 | |
paul@622 | 449 | # Details of attribute users at each active branch level. |
paul@622 | 450 | |
paul@622 | 451 | self.attribute_user_shelves = [] |
paul@622 | 452 | |
paul@622 | 453 | # Details of name scopes at each active branch level. |
paul@622 | 454 | |
paul@622 | 455 | self.scope_shelves = [] |
paul@622 | 456 | |
paul@622 | 457 | # Suspended user details plus loop details. |
paul@622 | 458 | |
paul@622 | 459 | self.suspended_broken_users = [] # stack of lists of user dicts |
paul@622 | 460 | self.suspended_continuing_users = [] # stack of lists of user dicts |
paul@622 | 461 | |
paul@622 | 462 | # Abandoned usage, useful for reviving usage for exception handlers. |
paul@622 | 463 | |
paul@622 | 464 | self.abandoned_users = [[]] # stack of lists of users |
paul@622 | 465 | |
paul@622 | 466 | # Methods shadowing the convenience methods provided during inspection. |
paul@622 | 467 | |
paul@622 | 468 | def _new_branchpoint(self, loop_node=None): |
paul@622 | 469 | |
paul@622 | 470 | """ |
paul@622 | 471 | Establish a new branchpoint where several control-flow branches diverge |
paul@622 | 472 | and subsequently converge. |
paul@622 | 473 | """ |
paul@622 | 474 | |
paul@622 | 475 | self.attribute_user_shelves.append([]) |
paul@622 | 476 | self.scope_shelves.append([]) |
paul@622 | 477 | |
paul@622 | 478 | if loop_node is not None: |
paul@622 | 479 | self.suspended_broken_users.append([]) |
paul@622 | 480 | self.suspended_continuing_users.append((loop_node, [])) |
paul@622 | 481 | |
paul@622 | 482 | def _new_branch(self, node): |
paul@622 | 483 | |
paul@622 | 484 | """ |
paul@622 | 485 | Establish a new control-flow branch, transferring attribute usage to |
paul@622 | 486 | the new branch so that it may be augmented for each name locally. |
paul@622 | 487 | |
paul@622 | 488 | Add the given 'node' as an active user to be informed of attribute |
paul@622 | 489 | usage. |
paul@622 | 490 | """ |
paul@622 | 491 | |
paul@622 | 492 | attribute_users = self.attribute_users[-1] |
paul@622 | 493 | |
paul@622 | 494 | # Define this node as the active attribute user for all currently |
paul@622 | 495 | # defined names. |
paul@622 | 496 | |
paul@622 | 497 | new_users = {} |
paul@622 | 498 | |
paul@622 | 499 | for name in attribute_users.keys(): |
paul@622 | 500 | new_users[name] = [node] |
paul@622 | 501 | self._init_attribute_user_for_name(node, name) |
paul@622 | 502 | |
paul@622 | 503 | self._init_attribute_user(node) |
paul@622 | 504 | self.attribute_users.append(new_users) |
paul@622 | 505 | |
paul@622 | 506 | # Add this user as a contributor to the previously active users. |
paul@622 | 507 | |
paul@622 | 508 | self._connect_users_to_branch(attribute_users, node) |
paul@622 | 509 | |
paul@622 | 510 | # Retain a record of scope usage. |
paul@622 | 511 | |
paul@622 | 512 | scope_usage = {} |
paul@622 | 513 | scope_usage.update(self.scope_usage[-1]) |
paul@622 | 514 | self.scope_usage.append(scope_usage) |
paul@622 | 515 | |
paul@622 | 516 | # Retain a record of abandoned branch users. |
paul@622 | 517 | |
paul@622 | 518 | self.abandoned_users.append([]) |
paul@622 | 519 | |
paul@622 | 520 | def _connect_users_to_branch(self, attribute_users, node): |
paul@622 | 521 | |
paul@622 | 522 | """ |
paul@622 | 523 | Given the 'attribute_users' mapping, connect the users referenced in the |
paul@622 | 524 | mapping to the given branch 'node'. |
paul@622 | 525 | """ |
paul@622 | 526 | |
paul@622 | 527 | all_users = set() |
paul@622 | 528 | |
paul@622 | 529 | for users in attribute_users.values(): |
paul@622 | 530 | all_users.update(users) |
paul@622 | 531 | |
paul@622 | 532 | for user in all_users: |
paul@622 | 533 | self._init_attribute_user(user) |
paul@622 | 534 | user._attrbranches.append(node) |
paul@622 | 535 | |
paul@622 | 536 | def _abandon_branch(self, retain_branch=True): |
paul@622 | 537 | |
paul@622 | 538 | """ |
paul@622 | 539 | Abandon scope usage, permitting locally different scopes for names, |
paul@622 | 540 | provided these cannot "escape" from the branch. |
paul@622 | 541 | """ |
paul@622 | 542 | |
paul@622 | 543 | attribute_users = self.attribute_users[-1] |
paul@622 | 544 | |
paul@622 | 545 | self.attribute_users[-1] = {} |
paul@622 | 546 | self.scope_usage[-1] = abandoned_branch_scope |
paul@622 | 547 | |
paul@622 | 548 | if retain_branch: |
paul@622 | 549 | self.abandoned_users[-1].append(attribute_users) |
paul@622 | 550 | |
paul@622 | 551 | def _suspend_broken_branch(self): |
paul@622 | 552 | |
paul@622 | 553 | """ |
paul@622 | 554 | Suspend a branch for resumption after the current loop. |
paul@622 | 555 | """ |
paul@622 | 556 | |
paul@622 | 557 | attribute_users = self.attribute_users[-1] |
paul@622 | 558 | |
paul@622 | 559 | users = self.suspended_broken_users[-1] |
paul@622 | 560 | users.append(attribute_users) |
paul@622 | 561 | self._abandon_branch(False) |
paul@622 | 562 | |
paul@622 | 563 | def _suspend_continuing_branch(self): |
paul@622 | 564 | |
paul@622 | 565 | """ |
paul@622 | 566 | Suspend a branch for resumption after the current iteration. |
paul@622 | 567 | """ |
paul@622 | 568 | |
paul@622 | 569 | attribute_users = self.attribute_users[-1] |
paul@622 | 570 | |
paul@622 | 571 | loop_node, users = self.suspended_continuing_users[-1] |
paul@622 | 572 | users.append(attribute_users) |
paul@622 | 573 | self._abandon_branch(False) |
paul@622 | 574 | |
paul@622 | 575 | def _shelve_branch(self): |
paul@622 | 576 | |
paul@622 | 577 | """ |
paul@622 | 578 | Shelve the current control-flow branch, recording the attribute usage |
paul@622 | 579 | for subsequent merging. If this branch should be abandoned, the usage |
paul@622 | 580 | observations are still recorded but will not contribute to subsequent |
paul@622 | 581 | observations after a merge. |
paul@622 | 582 | """ |
paul@622 | 583 | |
paul@622 | 584 | users = self.attribute_users.pop() |
paul@622 | 585 | self.attribute_user_shelves[-1].append(users) |
paul@622 | 586 | |
paul@622 | 587 | scope_usage = self.scope_usage.pop() |
paul@622 | 588 | self.scope_shelves[-1].append(scope_usage) |
paul@622 | 589 | |
paul@622 | 590 | def _merge_branches(self): |
paul@622 | 591 | |
paul@622 | 592 | """ |
paul@622 | 593 | Merge control-flow branches. This should find the users active within |
paul@622 | 594 | each branch, which have been "shelved", and update the active users |
paul@622 | 595 | dictionary with these contributions. |
paul@622 | 596 | """ |
paul@622 | 597 | |
paul@622 | 598 | # Combine the attribute users. This ensures that a list of users |
paul@622 | 599 | # affected by attribute usage is maintained for the current branch. |
paul@622 | 600 | |
paul@622 | 601 | all_shelved_users = self.attribute_user_shelves.pop() |
paul@622 | 602 | new_users = merge_mapping_dicts(all_shelved_users) |
paul@622 | 603 | self.attribute_users[-1] = new_users |
paul@622 | 604 | |
paul@622 | 605 | # Abandoned users are retained for exception handling purposes. |
paul@622 | 606 | |
paul@622 | 607 | all_abandoned_users = self.abandoned_users.pop() |
paul@622 | 608 | new_abandoned_users = merge_mapping_dicts(all_abandoned_users) |
paul@622 | 609 | self.abandoned_users[-1].append(new_abandoned_users) |
paul@622 | 610 | |
paul@622 | 611 | # Combine the scope usage. |
paul@622 | 612 | |
paul@622 | 613 | scope_usage = self.scope_usage[-1] |
paul@622 | 614 | new_scope_usage = {} |
paul@622 | 615 | |
paul@622 | 616 | all_scope_usage = self.scope_shelves.pop() |
paul@622 | 617 | all_scope_names = set() |
paul@622 | 618 | |
paul@622 | 619 | # Find all the names for whom scope information has been defined. |
paul@622 | 620 | |
paul@622 | 621 | for shelved_usage in all_scope_usage: |
paul@622 | 622 | all_scope_names.update(shelved_usage.keys()) |
paul@622 | 623 | |
paul@622 | 624 | for shelved_usage in all_scope_usage: |
paul@622 | 625 | for name in all_scope_names: |
paul@622 | 626 | |
paul@622 | 627 | # Find the recorded scope for the name. |
paul@622 | 628 | |
paul@622 | 629 | if shelved_usage.has_key(name): |
paul@622 | 630 | scope = shelved_usage[name] |
paul@622 | 631 | elif scope_usage.has_key(name): |
paul@622 | 632 | scope = scope_usage[name] |
paul@622 | 633 | |
paul@622 | 634 | # For abandoned branches, no scope is asserted for a name. |
paul@622 | 635 | |
paul@622 | 636 | elif isinstance(shelved_usage, AbandonedBranchScope): |
paul@622 | 637 | scope = None |
paul@622 | 638 | |
paul@622 | 639 | # If no scope is recorded, find a suitable external source. |
paul@622 | 640 | |
paul@622 | 641 | else: |
paul@622 | 642 | attr, scope, full_name = self._get_with_scope(name, external=1) |
paul@622 | 643 | |
paul@622 | 644 | # Attempt to record the scope, testing for conflicts. |
paul@622 | 645 | |
paul@622 | 646 | if scope: |
paul@622 | 647 | if not new_scope_usage.has_key(name): |
paul@622 | 648 | new_scope_usage[name] = scope |
paul@622 | 649 | else: |
paul@622 | 650 | new_scope = new_scope_usage[name] |
paul@622 | 651 | if new_scope != scope: |
paul@622 | 652 | if isinstance(new_scope, ScopeConflict): |
paul@622 | 653 | if isinstance(scope, ScopeConflict): |
paul@622 | 654 | scopes = scope.scopes.union(new_scope.scopes) |
paul@622 | 655 | else: |
paul@622 | 656 | scopes = new_scope.scopes.union(set([scope])) |
paul@622 | 657 | elif isinstance(scope, ScopeConflict): |
paul@622 | 658 | scopes = scope.scopes.union(set([new_scope])) |
paul@622 | 659 | else: |
paul@622 | 660 | scopes = set([scope, new_scope]) |
paul@622 | 661 | new_scope_usage[name] = ScopeConflict(scopes) |
paul@622 | 662 | |
paul@622 | 663 | self.scope_usage[-1] = new_scope_usage |
paul@622 | 664 | |
paul@622 | 665 | def _resume_broken_branches(self): |
paul@622 | 666 | |
paul@622 | 667 | """ |
paul@622 | 668 | Incorporate users from suspended broken branches into the current set of |
paul@622 | 669 | active users. |
paul@622 | 670 | """ |
paul@622 | 671 | |
paul@622 | 672 | suspended_users = self.suspended_broken_users.pop() |
paul@622 | 673 | current_users = self.attribute_users[-1] |
paul@622 | 674 | new_users = merge_mapping_dicts(suspended_users + [current_users]) |
paul@622 | 675 | self.attribute_users[-1] = new_users |
paul@622 | 676 | |
paul@622 | 677 | def _resume_continuing_branches(self): |
paul@622 | 678 | |
paul@622 | 679 | """ |
paul@622 | 680 | Incorporate users from suspended continuing branches into the current |
paul@622 | 681 | set of active users, merging usage from the latter with the former. |
paul@622 | 682 | """ |
paul@622 | 683 | |
paul@622 | 684 | loop_node, suspended_users = self.suspended_continuing_users.pop() |
paul@622 | 685 | current_users = self.attribute_users[-1] |
paul@622 | 686 | |
paul@622 | 687 | # Connect the suspended users to the loop node. |
paul@622 | 688 | |
paul@622 | 689 | for users in suspended_users: |
paul@622 | 690 | self._connect_users_to_branch(users, loop_node) |
paul@622 | 691 | |
paul@622 | 692 | # Merge suspended branches with the current branch. |
paul@622 | 693 | |
paul@622 | 694 | new_users = merge_mapping_dicts(suspended_users + [current_users]) |
paul@622 | 695 | self.attribute_users[-1] = new_users |
paul@622 | 696 | |
paul@622 | 697 | def _resume_abandoned_branches(self): |
paul@622 | 698 | |
paul@622 | 699 | """ |
paul@622 | 700 | Incorporate users from abandoned branches into the current set of active |
paul@622 | 701 | users. The abandoned branches are taken from the containing branch. |
paul@622 | 702 | """ |
paul@622 | 703 | |
paul@622 | 704 | current_users = self.attribute_users[-1] |
paul@622 | 705 | abandoned_users = self.abandoned_users[-2] |
paul@622 | 706 | new_users = merge_mapping_dicts(abandoned_users + [current_users]) |
paul@622 | 707 | self.attribute_users[-1] = new_users |
paul@622 | 708 | |
paul@622 | 709 | # Special helper classes for usage and scope resolution. |
paul@622 | 710 | |
paul@622 | 711 | class EmptyDict: |
paul@622 | 712 | |
paul@622 | 713 | "A class providing dictionaries which retain no information." |
paul@622 | 714 | |
paul@622 | 715 | def has_key(self, name): |
paul@622 | 716 | return False |
paul@622 | 717 | |
paul@622 | 718 | def __setitem__(self, name, value): |
paul@622 | 719 | pass |
paul@622 | 720 | |
paul@622 | 721 | def __getitem__(self, name): |
paul@622 | 722 | raise KeyError, name |
paul@622 | 723 | |
paul@622 | 724 | def get(self, name, default=None): |
paul@622 | 725 | return default |
paul@622 | 726 | |
paul@622 | 727 | def keys(self): |
paul@622 | 728 | return [] |
paul@622 | 729 | |
paul@622 | 730 | values = items = keys |
paul@622 | 731 | |
paul@622 | 732 | class AbandonedBranchScope(EmptyDict): |
paul@622 | 733 | |
paul@622 | 734 | """ |
paul@622 | 735 | A class providing a value or state for an abandoned branch distinct from an |
paul@622 | 736 | empty scope dictionary. |
paul@622 | 737 | """ |
paul@622 | 738 | |
paul@622 | 739 | pass |
paul@622 | 740 | |
paul@622 | 741 | abandoned_branch_scope = AbandonedBranchScope() |
paul@622 | 742 | |
paul@622 | 743 | class ScopeConflict: |
paul@622 | 744 | |
paul@622 | 745 | """ |
paul@622 | 746 | A scope conflict caused when different code branches contribute different |
paul@622 | 747 | sources of names. |
paul@622 | 748 | """ |
paul@622 | 749 | |
paul@622 | 750 | def __init__(self, scopes): |
paul@622 | 751 | self.scopes = scopes |
paul@622 | 752 | |
paul@622 | 753 | class UnsetType: |
paul@622 | 754 | |
paul@622 | 755 | "A None-like value." |
paul@622 | 756 | |
paul@622 | 757 | def __nonzero__(self): |
paul@622 | 758 | return False |
paul@622 | 759 | |
paul@622 | 760 | Unset = UnsetType() |
paul@622 | 761 | |
paul@622 | 762 | # vim: tabstop=4 expandtab shiftwidth=4 |