Lichen

Annotated common.py

869:ef74fed1f5c4
2019-01-24 Paul Boddie Merged the tuple-optimisations branch into the default branch.
paul@0 1
#!/usr/bin/env python
paul@0 2
paul@0 3
"""
paul@0 4
Common functions.
paul@0 5
paul@866 6
Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016,
paul@866 7
              2017, 2018, 2019 Paul Boddie <paul@boddie.org.uk>
paul@0 8
paul@0 9
This program is free software; you can redistribute it and/or modify it under
paul@0 10
the terms of the GNU General Public License as published by the Free Software
paul@0 11
Foundation; either version 3 of the License, or (at your option) any later
paul@0 12
version.
paul@0 13
paul@0 14
This program is distributed in the hope that it will be useful, but WITHOUT
paul@0 15
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
paul@0 16
FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
paul@0 17
details.
paul@0 18
paul@0 19
You should have received a copy of the GNU General Public License along with
paul@0 20
this program.  If not, see <http://www.gnu.org/licenses/>.
paul@0 21
"""
paul@0 22
paul@512 23
from compiler.transformer import Transformer
paul@430 24
from errors import InspectError
paul@0 25
from os import listdir, makedirs, remove
paul@609 26
from os.path import exists, getmtime, isdir, join, split
paul@11 27
from results import ConstantValueRef, LiteralSequenceRef, NameRef
paul@405 28
import compiler.ast
paul@0 29
paul@0 30
class CommonOutput:
paul@0 31
paul@0 32
    "Common output functionality."
paul@0 33
paul@617 34
    def check_output(self, options=None):
paul@0 35
paul@0 36
        "Check the existing output and remove it if irrelevant."
paul@0 37
paul@0 38
        if not exists(self.output):
paul@0 39
            makedirs(self.output)
paul@0 40
paul@0 41
        details = self.importer.get_cache_details()
paul@0 42
        recorded_details = self.get_output_details()
paul@0 43
paul@617 44
        # Combine cache details with any options.
paul@617 45
paul@617 46
        full_details = options and (details + " " + options) or details
paul@617 47
paul@617 48
        if recorded_details != full_details:
paul@0 49
            self.remove_output()
paul@0 50
paul@617 51
        writefile(self.get_output_details_filename(), full_details)
paul@0 52
paul@0 53
    def get_output_details_filename(self):
paul@0 54
paul@0 55
        "Return the output details filename."
paul@0 56
paul@0 57
        return join(self.output, "$details")
paul@0 58
paul@0 59
    def get_output_details(self):
paul@0 60
paul@0 61
        "Return details of the existing output."
paul@0 62
paul@0 63
        details_filename = self.get_output_details_filename()
paul@0 64
paul@0 65
        if not exists(details_filename):
paul@0 66
            return None
paul@0 67
        else:
paul@0 68
            return readfile(details_filename)
paul@0 69
paul@0 70
    def remove_output(self, dirname=None):
paul@0 71
paul@0 72
        "Remove the output."
paul@0 73
paul@0 74
        dirname = dirname or self.output
paul@0 75
paul@0 76
        for filename in listdir(dirname):
paul@0 77
            path = join(dirname, filename)
paul@0 78
            if isdir(path):
paul@0 79
                self.remove_output(path)
paul@0 80
            else:
paul@0 81
                remove(path)
paul@0 82
paul@609 83
def copy(source, target, only_if_newer=True):
paul@609 84
paul@609 85
    "Copy a text file from 'source' to 'target'."
paul@609 86
paul@609 87
    if isdir(target):
paul@609 88
        target = join(target, split(source)[-1])
paul@609 89
paul@609 90
    if only_if_newer and not is_newer(source, target):
paul@609 91
        return
paul@609 92
paul@609 93
    infile = open(source)
paul@609 94
    outfile = open(target, "w")
paul@609 95
paul@609 96
    try:
paul@609 97
        outfile.write(infile.read())
paul@609 98
    finally:
paul@609 99
        outfile.close()
paul@609 100
        infile.close()
paul@609 101
paul@609 102
def is_newer(source, target):
paul@609 103
paul@609 104
    "Return whether 'source' is newer than 'target'."
paul@609 105
paul@609 106
    if exists(target):
paul@609 107
        target_mtime = getmtime(target)
paul@609 108
        source_mtime = getmtime(source)
paul@609 109
        return source_mtime > target_mtime
paul@609 110
paul@609 111
    return True
paul@609 112
paul@0 113
class CommonModule:
paul@0 114
paul@0 115
    "A common module representation."
paul@0 116
paul@0 117
    def __init__(self, name, importer):
paul@0 118
paul@0 119
        """
paul@0 120
        Initialise this module with the given 'name' and an 'importer' which is
paul@0 121
        used to provide access to other modules when required.
paul@0 122
        """
paul@0 123
paul@0 124
        self.name = name
paul@0 125
        self.importer = importer
paul@0 126
        self.filename = None
paul@0 127
paul@0 128
        # Inspection-related attributes.
paul@0 129
paul@0 130
        self.astnode = None
paul@405 131
        self.encoding = None
paul@0 132
        self.temp = {}
paul@0 133
        self.lambdas = {}
paul@0 134
paul@0 135
        # Constants, literals and values.
paul@0 136
paul@0 137
        self.constants = {}
paul@0 138
        self.constant_values = {}
paul@0 139
        self.literals = {}
paul@0 140
        self.literal_types = {}
paul@0 141
paul@0 142
        # Nested namespaces.
paul@0 143
paul@0 144
        self.namespace_path = []
paul@0 145
        self.in_function = False
paul@0 146
paul@124 147
        # Retain the assignment value expression and track invocations.
paul@124 148
paul@124 149
        self.in_assignment = None
paul@553 150
        self.in_invocation = None
paul@124 151
paul@124 152
        # Attribute chain state management.
paul@0 153
paul@0 154
        self.attrs = []
paul@124 155
        self.chain_assignment = []
paul@124 156
        self.chain_invocation = []
paul@0 157
paul@0 158
    def __repr__(self):
paul@0 159
        return "CommonModule(%r, %r)" % (self.name, self.importer)
paul@0 160
paul@0 161
    def parse_file(self, filename):
paul@0 162
paul@0 163
        "Parse the file with the given 'filename', initialising attributes."
paul@0 164
paul@0 165
        self.filename = filename
paul@405 166
paul@405 167
        # Use the Transformer directly to obtain encoding information.
paul@405 168
paul@405 169
        t = Transformer()
paul@405 170
        f = open(filename)
paul@405 171
paul@405 172
        try:
paul@405 173
            self.astnode = t.parsesuite(f.read() + "\n")
paul@405 174
            self.encoding = t.encoding
paul@405 175
        finally:
paul@405 176
            f.close()
paul@0 177
paul@0 178
    # Module-relative naming.
paul@0 179
paul@0 180
    def get_global_path(self, name):
paul@0 181
        return "%s.%s" % (self.name, name)
paul@0 182
paul@0 183
    def get_namespace_path(self):
paul@0 184
        return ".".join([self.name] + self.namespace_path)
paul@0 185
paul@0 186
    def get_object_path(self, name):
paul@0 187
        return ".".join([self.name] + self.namespace_path + [name])
paul@0 188
paul@0 189
    # Namespace management.
paul@0 190
paul@0 191
    def enter_namespace(self, name):
paul@0 192
paul@0 193
        "Enter the namespace having the given 'name'."
paul@0 194
paul@0 195
        self.namespace_path.append(name)
paul@0 196
paul@0 197
    def exit_namespace(self):
paul@0 198
paul@0 199
        "Exit the current namespace."
paul@0 200
paul@0 201
        self.namespace_path.pop()
paul@0 202
paul@0 203
    # Constant reference naming.
paul@0 204
paul@406 205
    def get_constant_name(self, value, value_type, encoding=None):
paul@0 206
paul@397 207
        """
paul@397 208
        Add a new constant to the current namespace for 'value' with
paul@397 209
        'value_type'.
paul@397 210
        """
paul@0 211
paul@0 212
        path = self.get_namespace_path()
paul@0 213
        init_item(self.constants, path, dict)
paul@406 214
        return "$c%d" % add_counter_item(self.constants[path], (value, value_type, encoding))
paul@0 215
paul@0 216
    # Literal reference naming.
paul@0 217
paul@0 218
    def get_literal_name(self):
paul@0 219
paul@0 220
        "Add a new literal to the current namespace."
paul@0 221
paul@0 222
        path = self.get_namespace_path()
paul@0 223
        init_item(self.literals, path, lambda: 0)
paul@0 224
        return "$C%d" % self.literals[path]
paul@0 225
paul@0 226
    def next_literal(self):
paul@0 227
        self.literals[self.get_namespace_path()] += 1
paul@0 228
paul@0 229
    # Temporary variable naming.
paul@0 230
paul@0 231
    def get_temporary_name(self):
paul@0 232
        path = self.get_namespace_path()
paul@0 233
        init_item(self.temp, path, lambda: 0)
paul@0 234
        return "$t%d" % self.temp[path]
paul@0 235
paul@0 236
    def next_temporary(self):
paul@0 237
        self.temp[self.get_namespace_path()] += 1
paul@0 238
paul@0 239
    # Arbitrary function naming.
paul@0 240
paul@0 241
    def get_lambda_name(self):
paul@0 242
        path = self.get_namespace_path()
paul@0 243
        init_item(self.lambdas, path, lambda: 0)
paul@0 244
        name = "$l%d" % self.lambdas[path]
paul@0 245
        self.lambdas[path] += 1
paul@0 246
        return name
paul@0 247
paul@0 248
    def reset_lambdas(self):
paul@0 249
        self.lambdas = {}
paul@0 250
paul@0 251
    # Constant and literal recording.
paul@0 252
paul@537 253
    def get_constant_value(self, value, literals=None):
paul@394 254
paul@406 255
        """
paul@406 256
        Encode the 'value' if appropriate, returning a value, a typename and any
paul@406 257
        encoding.
paul@406 258
        """
paul@394 259
paul@394 260
        if isinstance(value, unicode):
paul@406 261
            return value.encode("utf-8"), "unicode", self.encoding
paul@405 262
paul@405 263
        # Attempt to convert plain strings to text.
paul@405 264
paul@405 265
        elif isinstance(value, str) and self.encoding:
paul@513 266
            try:
paul@537 267
                return get_string_details(literals, self.encoding)
paul@513 268
            except UnicodeDecodeError:
paul@513 269
                pass
paul@405 270
paul@406 271
        return value, value.__class__.__name__, None
paul@394 272
paul@406 273
    def get_constant_reference(self, ref, value, encoding=None):
paul@0 274
paul@406 275
        """
paul@406 276
        Return a constant reference for the given 'ref' type and 'value', with
paul@406 277
        the optional 'encoding' applying to text values.
paul@406 278
        """
paul@0 279
paul@406 280
        constant_name = self.get_constant_name(value, ref.get_origin(), encoding)
paul@0 281
paul@0 282
        # Return a reference for the constant.
paul@0 283
paul@0 284
        objpath = self.get_object_path(constant_name)
paul@338 285
        name_ref = ConstantValueRef(constant_name, ref.instance_of(objpath), value)
paul@0 286
paul@0 287
        # Record the value and type for the constant.
paul@0 288
paul@406 289
        self._reserve_constant(objpath, name_ref.value, name_ref.get_origin(), encoding)
paul@0 290
        return name_ref
paul@0 291
paul@406 292
    def reserve_constant(self, objpath, value, origin, encoding=None):
paul@251 293
paul@251 294
        """
paul@251 295
        Reserve a constant within 'objpath' with the given 'value' and having a
paul@406 296
        type with the given 'origin', with the optional 'encoding' applying to
paul@406 297
        text values.
paul@251 298
        """
paul@251 299
paul@397 300
        constant_name = self.get_constant_name(value, origin)
paul@251 301
        objpath = self.get_object_path(constant_name)
paul@406 302
        self._reserve_constant(objpath, value, origin, encoding)
paul@251 303
paul@406 304
    def _reserve_constant(self, objpath, value, origin, encoding):
paul@251 305
paul@406 306
        """
paul@406 307
        Store a constant for 'objpath' with the given 'value' and 'origin', with
paul@406 308
        the optional 'encoding' applying to text values.
paul@406 309
        """
paul@251 310
paul@406 311
        self.constant_values[objpath] = value, origin, encoding
paul@251 312
paul@0 313
    def get_literal_reference(self, name, ref, items, cls):
paul@0 314
paul@11 315
        """
paul@11 316
        Return a literal reference for the given type 'name', literal 'ref',
paul@11 317
        node 'items' and employing the given 'cls' as the class of the returned
paul@11 318
        reference object.
paul@11 319
        """
paul@11 320
paul@0 321
        # Construct an invocation using the items as arguments.
paul@0 322
paul@0 323
        typename = "$L%s" % name
paul@0 324
paul@0 325
        invocation = compiler.ast.CallFunc(
paul@0 326
            compiler.ast.Name(typename),
paul@0 327
            items
paul@0 328
            )
paul@0 329
paul@0 330
        # Get a name for the actual literal.
paul@0 331
paul@0 332
        instname = self.get_literal_name()
paul@0 333
        self.next_literal()
paul@0 334
paul@0 335
        # Record the type for the literal.
paul@0 336
paul@0 337
        objpath = self.get_object_path(instname)
paul@0 338
        self.literal_types[objpath] = ref.get_origin()
paul@0 339
paul@0 340
        # Return a wrapper for the invocation exposing the items.
paul@0 341
paul@0 342
        return cls(
paul@0 343
            instname,
paul@0 344
            ref.instance_of(),
paul@0 345
            self.process_structure_node(invocation),
paul@0 346
            invocation.args
paul@0 347
            )
paul@0 348
paul@0 349
    # Node handling.
paul@0 350
paul@0 351
    def process_structure(self, node):
paul@0 352
paul@0 353
        """
paul@0 354
        Within the given 'node', process the program structure.
paul@0 355
paul@0 356
        During inspection, this will process global declarations, adjusting the
paul@0 357
        module namespace, and import statements, building a module dependency
paul@0 358
        hierarchy.
paul@0 359
paul@0 360
        During translation, this will consult deduced program information and
paul@0 361
        output translated code.
paul@0 362
        """
paul@0 363
paul@0 364
        l = []
paul@0 365
        for n in node.getChildNodes():
paul@0 366
            l.append(self.process_structure_node(n))
paul@0 367
        return l
paul@0 368
paul@0 369
    def process_augassign_node(self, n):
paul@0 370
paul@0 371
        "Process the given augmented assignment node 'n'."
paul@0 372
paul@0 373
        op = operator_functions[n.op]
paul@0 374
paul@0 375
        if isinstance(n.node, compiler.ast.Getattr):
paul@0 376
            target = compiler.ast.AssAttr(n.node.expr, n.node.attrname, "OP_ASSIGN")
paul@0 377
        elif isinstance(n.node, compiler.ast.Name):
paul@0 378
            target = compiler.ast.AssName(n.node.name, "OP_ASSIGN")
paul@0 379
        else:
paul@0 380
            target = n.node
paul@0 381
paul@0 382
        assignment = compiler.ast.Assign(
paul@0 383
            [target],
paul@0 384
            compiler.ast.CallFunc(
paul@0 385
                compiler.ast.Name("$op%s" % op),
paul@0 386
                [n.node, n.expr]))
paul@0 387
paul@0 388
        return self.process_structure_node(assignment)
paul@0 389
paul@320 390
    def process_assignment_for_object(self, original_name, source):
paul@0 391
paul@0 392
        """
paul@0 393
        Return an assignment operation making 'original_name' refer to the given
paul@196 394
        'source'.
paul@0 395
        """
paul@0 396
paul@0 397
        assignment = compiler.ast.Assign(
paul@0 398
            [compiler.ast.AssName(original_name, "OP_ASSIGN")],
paul@196 399
            source
paul@0 400
            )
paul@0 401
paul@0 402
        return self.process_structure_node(assignment)
paul@0 403
paul@0 404
    def process_assignment_node_items(self, n, expr):
paul@0 405
paul@0 406
        """
paul@0 407
        Process the given assignment node 'n' whose children are to be assigned
paul@0 408
        items of 'expr'.
paul@0 409
        """
paul@0 410
paul@0 411
        name_ref = self.process_structure_node(expr)
paul@0 412
paul@509 413
        # Either unpack the items and present them directly to each assignment
paul@509 414
        # node.
paul@509 415
paul@509 416
        if isinstance(name_ref, LiteralSequenceRef) and \
paul@509 417
           self.process_literal_sequence_items(n, name_ref):
paul@0 418
paul@509 419
            pass
paul@509 420
paul@509 421
        # Or have the assignment nodes access each item via the sequence API.
paul@509 422
paul@509 423
        else:
paul@509 424
            self.process_assignment_node_items_by_position(n, expr, name_ref)
paul@0 425
paul@0 426
    def process_assignment_node_items_by_position(self, n, expr, name_ref):
paul@0 427
paul@0 428
        """
paul@0 429
        Process the given sequence assignment node 'n', converting the node to
paul@0 430
        the separate assignment of each target using positional access on a
paul@0 431
        temporary variable representing the sequence. Use 'expr' as the assigned
paul@0 432
        value and 'name_ref' as the reference providing any existing temporary
paul@0 433
        variable.
paul@0 434
        """
paul@0 435
paul@835 436
        statements = []
paul@0 437
paul@508 438
        # Employ existing names to access the sequence.
paul@508 439
        # Literal sequences do not provide names of accessible objects.
paul@508 440
paul@508 441
        if isinstance(name_ref, NameRef) and not isinstance(name_ref, LiteralSequenceRef):
paul@0 442
            temp = name_ref.name
paul@508 443
paul@508 444
        # For other expressions, create a temporary name to reference the items.
paul@508 445
paul@0 446
        else:
paul@0 447
            temp = self.get_temporary_name()
paul@0 448
            self.next_temporary()
paul@0 449
paul@835 450
            statements.append(
paul@0 451
                compiler.ast.Assign([compiler.ast.AssName(temp, "OP_ASSIGN")], expr)
paul@0 452
                )
paul@0 453
paul@835 454
        # Generate a test for the length of the expression object.
paul@835 455
paul@835 456
        statements.append(compiler.ast.Discard(
paul@835 457
            compiler.ast.CallFunc(compiler.ast.Name("$seq_test_length"),
paul@835 458
                [compiler.ast.Name(temp), compiler.ast.Const(len(n.nodes))])))
paul@835 459
paul@508 460
        # Assign the items to the target nodes.
paul@508 461
paul@0 462
        for i, node in enumerate(n.nodes):
paul@835 463
            statements.append(
paul@836 464
                compiler.ast.Assign([node], compiler.ast.CallFunc(
paul@845 465
                    compiler.ast.Getattr(compiler.ast.Name(temp),
paul@845 466
                                         "__get_single_item_unchecked__",
paul@845 467
                                         privileged=True),
paul@836 468
                    [compiler.ast.Const(i, str(i))]))
paul@0 469
                )
paul@0 470
paul@835 471
        return self.process_structure_node(compiler.ast.Stmt(statements))
paul@0 472
paul@0 473
    def process_literal_sequence_items(self, n, name_ref):
paul@0 474
paul@0 475
        """
paul@0 476
        Process the given assignment node 'n', obtaining from the given
paul@0 477
        'name_ref' the items to be assigned to the assignment targets.
paul@509 478
paul@509 479
        Return whether this method was able to process the assignment node as
paul@509 480
        a sequence of direct assignments.
paul@0 481
        """
paul@0 482
paul@0 483
        if len(n.nodes) == len(name_ref.items):
paul@509 484
            assigned_names, count = get_names_from_nodes(n.nodes)
paul@509 485
            accessed_names, _count = get_names_from_nodes(name_ref.items)
paul@509 486
paul@509 487
            # Only assign directly between items if all assigned names are
paul@509 488
            # plain names (not attribute assignments), and if the assigned names
paul@509 489
            # do not appear in the accessed names.
paul@509 490
paul@509 491
            if len(assigned_names) == count and \
paul@509 492
               not assigned_names.intersection(accessed_names):
paul@509 493
paul@509 494
                for node, item in zip(n.nodes, name_ref.items):
paul@509 495
                    self.process_assignment_node(node, item)
paul@509 496
paul@509 497
                return True
paul@509 498
paul@509 499
            # Otherwise, use the position-based mechanism to obtain values.
paul@509 500
paul@509 501
            else:
paul@509 502
                return False
paul@0 503
        else:
paul@0 504
            raise InspectError("In %s, item assignment needing %d items is given %d items." % (
paul@0 505
                self.get_namespace_path(), len(n.nodes), len(name_ref.items)))
paul@0 506
paul@0 507
    def process_compare_node(self, n):
paul@0 508
paul@0 509
        """
paul@0 510
        Process the given comparison node 'n', converting an operator sequence
paul@0 511
        from...
paul@0 512
paul@0 513
        <expr1> <op1> <expr2> <op2> <expr3>
paul@0 514
paul@0 515
        ...to...
paul@0 516
paul@0 517
        <op1>(<expr1>, <expr2>) and <op2>(<expr2>, <expr3>)
paul@0 518
        """
paul@0 519
paul@0 520
        invocations = []
paul@0 521
        last = n.expr
paul@0 522
paul@0 523
        for op, op_node in n.ops:
paul@0 524
            op = operator_functions.get(op)
paul@0 525
paul@0 526
            invocations.append(compiler.ast.CallFunc(
paul@0 527
                compiler.ast.Name("$op%s" % op),
paul@0 528
                [last, op_node]))
paul@0 529
paul@0 530
            last = op_node
paul@0 531
paul@0 532
        if len(invocations) > 1:
paul@0 533
            result = compiler.ast.And(invocations)
paul@0 534
        else:
paul@0 535
            result = invocations[0]
paul@0 536
paul@0 537
        return self.process_structure_node(result)
paul@0 538
paul@0 539
    def process_dict_node(self, node):
paul@0 540
paul@0 541
        """
paul@0 542
        Process the given dictionary 'node', returning a list of (key, value)
paul@0 543
        tuples.
paul@0 544
        """
paul@0 545
paul@0 546
        l = []
paul@0 547
        for key, value in node.items:
paul@0 548
            l.append((
paul@0 549
                self.process_structure_node(key),
paul@0 550
                self.process_structure_node(value)))
paul@0 551
        return l
paul@0 552
paul@0 553
    def process_for_node(self, n):
paul@0 554
paul@0 555
        """
paul@0 556
        Generate attribute accesses for {n.list}.__iter__ and the next method on
paul@0 557
        the iterator, producing a replacement node for the original.
paul@0 558
        """
paul@0 559
paul@705 560
        t0 = self.get_temporary_name()
paul@705 561
        self.next_temporary()
paul@705 562
        t1 = self.get_temporary_name()
paul@705 563
        self.next_temporary()
paul@832 564
        t2 = self.get_temporary_name()
paul@832 565
        self.next_temporary()
paul@704 566
paul@0 567
        node = compiler.ast.Stmt([
paul@0 568
paul@705 569
            # <t0> = {n.list}
paul@705 570
            # <t1> = <t0>.__iter__()
paul@705 571
paul@705 572
            compiler.ast.Assign(
paul@705 573
                [compiler.ast.AssName(t0, "OP_ASSIGN")],
paul@705 574
                n.list),
paul@705 575
paul@705 576
            compiler.ast.Assign(
paul@705 577
                [compiler.ast.AssName(t1, "OP_ASSIGN")],
paul@705 578
                compiler.ast.CallFunc(
paul@705 579
                    compiler.ast.Getattr(compiler.ast.Name(t0), "__iter__"),
paul@705 580
                    [])),
paul@0 581
paul@832 582
            # <t2> = <t1>.next
paul@0 583
            # try:
paul@0 584
            #     while True:
paul@868 585
            #         try:
paul@868 586
            #             <var>... = <t2>()
paul@868 587
            #         except StopIteration:
paul@868 588
            #             raise LoopExit
paul@868 589
            #         {n.body}
paul@868 590
            # except LoopExit:
paul@866 591
            #     {n.else_}
paul@0 592
            #     pass
paul@0 593
paul@832 594
            compiler.ast.Assign(
paul@832 595
                [compiler.ast.AssName(t2, "OP_ASSIGN")],
paul@832 596
                compiler.ast.Getattr(compiler.ast.Name(t1), "next")),
paul@832 597
paul@0 598
            compiler.ast.TryExcept(
paul@0 599
                compiler.ast.While(
paul@0 600
                    compiler.ast.Name("True"),
paul@0 601
                    compiler.ast.Stmt([
paul@868 602
                        compiler.ast.TryExcept(
paul@868 603
                            compiler.ast.Assign(
paul@868 604
                                [n.assign],
paul@868 605
                                compiler.ast.CallFunc(
paul@868 606
                                    compiler.ast.Name(t2),
paul@868 607
                                    [])),
paul@868 608
                            [(compiler.ast.Name("StopIteration"), None,
paul@868 609
                              compiler.ast.Raise(compiler.ast.Name("LoopExit")))],
paul@868 610
                            None),
paul@0 611
                        n.body]),
paul@0 612
                    None),
paul@868 613
                [(compiler.ast.Name("LoopExit"), None, n.else_ or compiler.ast.Pass())],
paul@0 614
                None)
paul@0 615
            ])
paul@0 616
paul@0 617
        self.process_structure_node(node)
paul@0 618
paul@0 619
    def process_literal_sequence_node(self, n, name, ref, cls):
paul@0 620
paul@0 621
        """
paul@0 622
        Process the given literal sequence node 'n' as a function invocation,
paul@0 623
        with 'name' indicating the type of the sequence, and 'ref' being a
paul@0 624
        reference to the type. The 'cls' is used to instantiate a suitable name
paul@0 625
        reference.
paul@0 626
        """
paul@0 627
paul@0 628
        if name == "dict":
paul@0 629
            items = []
paul@0 630
            for key, value in n.items:
paul@0 631
                items.append(compiler.ast.Tuple([key, value]))
paul@0 632
        else: # name in ("list", "tuple"):
paul@0 633
            items = n.nodes
paul@0 634
paul@0 635
        return self.get_literal_reference(name, ref, items, cls)
paul@0 636
paul@0 637
    def process_operator_node(self, n):
paul@0 638
paul@0 639
        """
paul@0 640
        Process the given operator node 'n' as an operator function invocation.
paul@0 641
        """
paul@0 642
paul@797 643
        opname = n.__class__.__name__
paul@797 644
        operands = n.getChildNodes()
paul@797 645
paul@797 646
        # Convert a unary operation to an invocation.
paul@797 647
paul@797 648
        op = unary_operator_functions.get(opname)
paul@797 649
paul@797 650
        if op:
paul@797 651
            invocation = compiler.ast.CallFunc(
paul@797 652
                compiler.ast.Name("$op%s" % op),
paul@797 653
                [operands[0]]
paul@797 654
                )
paul@797 655
paul@797 656
        # Convert a single operator with a list of operands to a combination of
paul@797 657
        # pairwise operations.
paul@797 658
paul@797 659
        else:
paul@797 660
            op = operator_functions[opname]
paul@797 661
            invocation = self._process_operator_node(op, operands)
paul@797 662
paul@797 663
        return self.process_structure_node(invocation)
paul@797 664
paul@797 665
    def _process_operator_node(self, op, operands):
paul@797 666
paul@797 667
        """
paul@797 668
        Process the given 'op', being an operator function, together with the
paul@797 669
        supplied 'operands', returning either a single remaining operand or an
paul@797 670
        invocation combining the operands.
paul@797 671
        """
paul@797 672
paul@797 673
        remaining = operands[1:]
paul@797 674
        if not remaining:
paul@797 675
            return operands[0]
paul@797 676
paul@797 677
        return compiler.ast.CallFunc(
paul@0 678
            compiler.ast.Name("$op%s" % op),
paul@797 679
            [operands[0], self._process_operator_node(op, remaining)]
paul@0 680
            )
paul@0 681
paul@173 682
    def process_print_node(self, n):
paul@173 683
paul@173 684
        """
paul@173 685
        Process the given print node 'n' as an invocation on a stream of the
paul@173 686
        form...
paul@173 687
paul@173 688
        $print(dest, args, nl)
paul@173 689
paul@173 690
        The special function name will be translated elsewhere.
paul@173 691
        """
paul@173 692
paul@173 693
        nl = isinstance(n, compiler.ast.Printnl)
paul@173 694
        invocation = compiler.ast.CallFunc(
paul@173 695
            compiler.ast.Name("$print"),
paul@173 696
            [n.dest or compiler.ast.Name("None"),
paul@173 697
             compiler.ast.List(list(n.nodes)),
paul@359 698
             nl and compiler.ast.Name("True") or compiler.ast.Name("False")]
paul@173 699
            )
paul@173 700
        return self.process_structure_node(invocation)
paul@173 701
paul@0 702
    def process_slice_node(self, n, expr=None):
paul@0 703
paul@0 704
        """
paul@784 705
        Process the given slice node 'n' as a method invocation.
paul@0 706
        """
paul@0 707
paul@784 708
        if n.flags == "OP_ASSIGN": op = "__setslice__"
paul@784 709
        elif n.flags == "OP_DELETE": op = "__delslice__"
paul@784 710
        else: op = "__getslice__"
paul@548 711
paul@0 712
        invocation = compiler.ast.CallFunc(
paul@784 713
            compiler.ast.Getattr(n.expr, op),
paul@784 714
            [n.lower or compiler.ast.Name("None"), n.upper or compiler.ast.Name("None")] +
paul@0 715
                (expr and [expr] or [])
paul@0 716
            )
paul@548 717
paul@548 718
        # Fix parse tree structure.
paul@548 719
paul@784 720
        if op == "__delslice__":
paul@548 721
            invocation = compiler.ast.Discard(invocation)
paul@548 722
paul@0 723
        return self.process_structure_node(invocation)
paul@0 724
paul@0 725
    def process_sliceobj_node(self, n):
paul@0 726
paul@0 727
        """
paul@0 728
        Process the given slice object node 'n' as a slice constructor.
paul@0 729
        """
paul@0 730
paul@0 731
        op = "slice"
paul@0 732
        invocation = compiler.ast.CallFunc(
paul@0 733
            compiler.ast.Name("$op%s" % op),
paul@0 734
            n.nodes
paul@0 735
            )
paul@0 736
        return self.process_structure_node(invocation)
paul@0 737
paul@0 738
    def process_subscript_node(self, n, expr=None):
paul@0 739
paul@0 740
        """
paul@784 741
        Process the given subscript node 'n' as a method invocation.
paul@0 742
        """
paul@0 743
paul@784 744
        if n.flags == "OP_ASSIGN": op = "__setitem__"
paul@784 745
        elif n.flags == "OP_DELETE": op = "__delitem__"
paul@784 746
        else: op = "__getitem__"
paul@548 747
paul@0 748
        invocation = compiler.ast.CallFunc(
paul@784 749
            compiler.ast.Getattr(n.expr, op),
paul@784 750
            list(n.subs) + (expr and [expr] or [])
paul@0 751
            )
paul@548 752
paul@548 753
        # Fix parse tree structure.
paul@548 754
paul@784 755
        if op == "__delitem__":
paul@548 756
            invocation = compiler.ast.Discard(invocation)
paul@548 757
paul@0 758
        return self.process_structure_node(invocation)
paul@0 759
paul@0 760
    def process_attribute_chain(self, n):
paul@0 761
paul@0 762
        """
paul@0 763
        Process the given attribute access node 'n'. Return a reference
paul@0 764
        describing the expression.
paul@0 765
        """
paul@0 766
paul@0 767
        # AssAttr/Getattr are nested with the outermost access being the last
paul@0 768
        # access in any chain.
paul@0 769
paul@0 770
        self.attrs.insert(0, n.attrname)
paul@0 771
        attrs = self.attrs
paul@0 772
paul@0 773
        # Break attribute chains where non-access nodes are found.
paul@0 774
paul@0 775
        if not self.have_access_expression(n):
paul@110 776
            self.reset_attribute_chain()
paul@0 777
paul@0 778
        # Descend into the expression, extending backwards any existing chain,
paul@0 779
        # or building another for the expression.
paul@0 780
paul@0 781
        name_ref = self.process_structure_node(n.expr)
paul@0 782
paul@0 783
        # Restore chain information applying to this node.
paul@0 784
paul@110 785
        if not self.have_access_expression(n):
paul@110 786
            self.restore_attribute_chain(attrs)
paul@0 787
paul@0 788
        # Return immediately if the expression was another access and thus a
paul@0 789
        # continuation backwards along the chain. The above processing will
paul@0 790
        # have followed the chain all the way to its conclusion.
paul@0 791
paul@0 792
        if self.have_access_expression(n):
paul@0 793
            del self.attrs[0]
paul@0 794
paul@0 795
        return name_ref
paul@0 796
paul@124 797
    # Attribute chain handling.
paul@124 798
paul@110 799
    def reset_attribute_chain(self):
paul@110 800
paul@110 801
        "Reset the attribute chain for a subexpression of an attribute access."
paul@110 802
paul@110 803
        self.attrs = []
paul@124 804
        self.chain_assignment.append(self.in_assignment)
paul@124 805
        self.chain_invocation.append(self.in_invocation)
paul@124 806
        self.in_assignment = None
paul@553 807
        self.in_invocation = None
paul@110 808
paul@110 809
    def restore_attribute_chain(self, attrs):
paul@110 810
paul@110 811
        "Restore the attribute chain for an attribute access."
paul@110 812
paul@110 813
        self.attrs = attrs
paul@124 814
        self.in_assignment = self.chain_assignment.pop()
paul@124 815
        self.in_invocation = self.chain_invocation.pop()
paul@110 816
paul@0 817
    def have_access_expression(self, node):
paul@0 818
paul@0 819
        "Return whether the expression associated with 'node' is Getattr."
paul@0 820
paul@0 821
        return isinstance(node.expr, compiler.ast.Getattr)
paul@0 822
paul@678 823
    def get_name_for_tracking(self, name, name_ref=None, is_global=False):
paul@0 824
paul@0 825
        """
paul@0 826
        Return the name to be used for attribute usage observations involving
paul@603 827
        the given 'name' in the current namespace.
paul@603 828
paul@603 829
        If the name is being used outside a function, and if 'name_ref' is
paul@678 830
        given and indicates a global or if 'is_global' is specified as a true
paul@678 831
        value, a path featuring the name in the global namespace is returned.
paul@678 832
        Otherwise, a path computed using the current namespace and the given
paul@678 833
        name is returned.
paul@0 834
paul@0 835
        The intention of this method is to provide a suitably-qualified name
paul@0 836
        that can be tracked across namespaces. Where globals are being
paul@0 837
        referenced in class namespaces, they should be referenced using their
paul@0 838
        path within the module, not using a path within each class.
paul@0 839
paul@0 840
        It may not be possible to identify a global within a function at the
paul@0 841
        time of inspection (since a global may appear later in a file).
paul@0 842
        Consequently, globals are identified by their local name rather than
paul@0 843
        their module-qualified path.
paul@0 844
        """
paul@0 845
paul@0 846
        # For functions, use the appropriate local names.
paul@0 847
paul@0 848
        if self.in_function:
paul@0 849
            return name
paul@0 850
paul@603 851
        # For global names outside functions, use a global name.
paul@597 852
paul@678 853
        elif is_global or name_ref and name_ref.is_global_name():
paul@603 854
            return self.get_global_path(name)
paul@0 855
paul@152 856
        # Otherwise, establish a name in the current namespace.
paul@0 857
paul@0 858
        else:
paul@0 859
            return self.get_object_path(name)
paul@0 860
paul@0 861
    def get_path_for_access(self):
paul@0 862
paul@0 863
        "Outside functions, register accesses at the module level."
paul@0 864
paul@0 865
        if not self.in_function:
paul@0 866
            return self.name
paul@0 867
        else:
paul@0 868
            return self.get_namespace_path()
paul@0 869
paul@0 870
    def get_module_name(self, node):
paul@0 871
paul@0 872
        """
paul@0 873
        Using the given From 'node' in this module, calculate any relative import
paul@0 874
        information, returning a tuple containing a module to import along with any
paul@0 875
        names to import based on the node's name information.
paul@0 876
paul@0 877
        Where the returned module is given as None, whole module imports should
paul@0 878
        be performed for the returned modules using the returned names.
paul@0 879
        """
paul@0 880
paul@0 881
        # Absolute import.
paul@0 882
paul@0 883
        if node.level == 0:
paul@0 884
            return node.modname, node.names
paul@0 885
paul@0 886
        # Relative to an ancestor of this module.
paul@0 887
paul@0 888
        else:
paul@0 889
            path = self.name.split(".")
paul@0 890
            level = node.level
paul@0 891
paul@0 892
            # Relative imports treat package roots as submodules.
paul@0 893
paul@0 894
            if split(self.filename)[-1] == "__init__.py":
paul@0 895
                level -= 1
paul@0 896
paul@0 897
            if level > len(path):
paul@0 898
                raise InspectError("Relative import %r involves too many levels up from module %r" % (
paul@0 899
                    ("%s%s" % ("." * node.level, node.modname or "")), self.name))
paul@0 900
paul@0 901
            basename = ".".join(path[:len(path)-level])
paul@0 902
paul@0 903
        # Name imports from a module.
paul@0 904
paul@0 905
        if node.modname:
paul@0 906
            return "%s.%s" % (basename, node.modname), node.names
paul@0 907
paul@0 908
        # Relative whole module imports.
paul@0 909
paul@0 910
        else:
paul@0 911
            return basename, node.names
paul@0 912
paul@0 913
def get_argnames(args):
paul@0 914
paul@0 915
    """
paul@0 916
    Return a list of all names provided by 'args'. Since tuples may be
paul@0 917
    employed, the arguments are traversed depth-first.
paul@0 918
    """
paul@0 919
paul@0 920
    l = []
paul@0 921
    for arg in args:
paul@0 922
        if isinstance(arg, tuple):
paul@0 923
            l += get_argnames(arg)
paul@0 924
        else:
paul@0 925
            l.append(arg)
paul@0 926
    return l
paul@0 927
paul@509 928
def get_names_from_nodes(nodes):
paul@509 929
paul@509 930
    """
paul@509 931
    Return the names employed in the given 'nodes' along with the number of
paul@509 932
    nodes excluding sequences.
paul@509 933
    """
paul@509 934
paul@509 935
    names = set()
paul@509 936
    count = 0
paul@509 937
paul@509 938
    for node in nodes:
paul@509 939
paul@509 940
        # Add names and count them.
paul@509 941
paul@509 942
        if isinstance(node, (compiler.ast.AssName, compiler.ast.Name)):
paul@509 943
            names.add(node.name)
paul@509 944
            count += 1
paul@509 945
paul@509 946
        # Add names from sequences and incorporate their counts.
paul@509 947
paul@509 948
        elif isinstance(node, (compiler.ast.AssList, compiler.ast.AssTuple,
paul@509 949
                               compiler.ast.List, compiler.ast.Set,
paul@509 950
                               compiler.ast.Tuple)):
paul@509 951
            _names, _count = get_names_from_nodes(node.nodes)
paul@509 952
            names.update(_names)
paul@509 953
            count += _count
paul@509 954
paul@509 955
        # Count non-name, non-sequence nodes.
paul@509 956
paul@509 957
        else:
paul@509 958
            count += 1
paul@509 959
paul@509 960
    return names, count
paul@509 961
paul@791 962
# Location classes.
paul@791 963
paul@791 964
class Location:
paul@791 965
paul@791 966
    "A generic program location."
paul@791 967
paul@791 968
    def __init__(self, path, name, attrnames=None, version=None, access_number=None):
paul@791 969
        self.path = path
paul@791 970
        self.name = name
paul@791 971
        self.attrnames = attrnames
paul@791 972
        self.version = version
paul@791 973
        self.access_number = access_number
paul@791 974
paul@791 975
    def __repr__(self):
paul@791 976
        return "Location(%r, %r, %r, %r, %r)" % self.as_tuple()
paul@791 977
paul@791 978
    def as_tuple(self):
paul@791 979
        return (self.path, self.name, self.attrnames, self.version, self.access_number)
paul@791 980
paul@791 981
    def __hash__(self):
paul@791 982
        return hash(self.as_tuple())
paul@791 983
paul@791 984
    def __eq__(self, other):
paul@791 985
        return self.as_tuple() == other.as_tuple()
paul@791 986
paul@791 987
    def __cmp__(self, other):
paul@791 988
        return cmp(self.as_tuple(), other.as_tuple())
paul@791 989
paul@791 990
    def get_attrname(self):
paul@791 991
paul@791 992
        """
paul@791 993
        Extract the first attribute from the attribute names employed in this
paul@791 994
        location.
paul@791 995
        """
paul@791 996
paul@791 997
        attrnames = self.attrnames
paul@791 998
        if not attrnames:
paul@791 999
            return attrnames
paul@791 1000
        return get_attrnames(attrnames)[0]
paul@791 1001
paul@791 1002
class AccessLocation(Location):
paul@791 1003
paul@791 1004
    "A specialised access location."
paul@791 1005
paul@791 1006
    def __init__(self, path, name, attrnames, access_number):
paul@791 1007
paul@791 1008
        """
paul@791 1009
        Initialise an access location featuring 'path', 'name', 'attrnames' and
paul@791 1010
        'access_number'.
paul@791 1011
        """
paul@791 1012
paul@791 1013
        Location.__init__(self, path, name, attrnames, None, access_number)
paul@791 1014
paul@791 1015
    def __repr__(self):
paul@791 1016
        return "AccessLocation(%r, %r, %r, %r)" % (self.path, self.name, self.attrnames, self.access_number)
paul@791 1017
paul@491 1018
# Result classes.
paul@491 1019
paul@491 1020
class InstructionSequence:
paul@491 1021
paul@491 1022
    "A generic sequence of instructions."
paul@491 1023
paul@491 1024
    def __init__(self, instructions):
paul@491 1025
        self.instructions = instructions
paul@491 1026
paul@491 1027
    def get_value_instruction(self):
paul@491 1028
        return self.instructions[-1]
paul@491 1029
paul@491 1030
    def get_init_instructions(self):
paul@491 1031
        return self.instructions[:-1]
paul@491 1032
paul@0 1033
# Dictionary utilities.
paul@0 1034
paul@0 1035
def init_item(d, key, fn):
paul@0 1036
paul@0 1037
    """
paul@0 1038
    Add to 'd' an entry for 'key' using the callable 'fn' to make an initial
paul@0 1039
    value where no entry already exists.
paul@0 1040
    """
paul@0 1041
paul@0 1042
    if not d.has_key(key):
paul@0 1043
        d[key] = fn()
paul@0 1044
    return d[key]
paul@0 1045
paul@0 1046
def dict_for_keys(d, keys):
paul@0 1047
paul@0 1048
    "Return a new dictionary containing entries from 'd' for the given 'keys'."
paul@0 1049
paul@0 1050
    nd = {}
paul@0 1051
    for key in keys:
paul@0 1052
        if d.has_key(key):
paul@0 1053
            nd[key] = d[key]
paul@0 1054
    return nd
paul@0 1055
paul@0 1056
def make_key(s):
paul@0 1057
paul@0 1058
    "Make sequence 's' into a tuple-based key, first sorting its contents."
paul@0 1059
paul@0 1060
    l = list(s)
paul@0 1061
    l.sort()
paul@0 1062
    return tuple(l)
paul@0 1063
paul@0 1064
def add_counter_item(d, key):
paul@0 1065
paul@0 1066
    """
paul@0 1067
    Make a mapping in 'd' for 'key' to the number of keys added before it, thus
paul@0 1068
    maintaining a mapping of keys to their order of insertion.
paul@0 1069
    """
paul@0 1070
paul@0 1071
    if not d.has_key(key):
paul@0 1072
        d[key] = len(d.keys())
paul@0 1073
    return d[key] 
paul@0 1074
paul@0 1075
def remove_items(d1, d2):
paul@0 1076
paul@0 1077
    "Remove from 'd1' all items from 'd2'."
paul@0 1078
paul@0 1079
    for key in d2.keys():
paul@0 1080
        if d1.has_key(key):
paul@0 1081
            del d1[key]
paul@0 1082
paul@0 1083
# Set utilities.
paul@0 1084
paul@0 1085
def first(s):
paul@0 1086
    return list(s)[0]
paul@0 1087
paul@0 1088
def same(s1, s2):
paul@0 1089
    return set(s1) == set(s2)
paul@0 1090
paul@724 1091
def order_dependencies(all_depends):
paul@724 1092
paul@724 1093
    """
paul@724 1094
    Produce a dependency ordering for the 'all_depends' mapping. This mapping
paul@724 1095
    has the form "A depends on B, C...". The result will order A, B, C, and so
paul@724 1096
    on.
paul@724 1097
    """
paul@724 1098
paul@726 1099
    usage = init_reverse_dependencies(all_depends)
paul@726 1100
paul@726 1101
    # Produce an ordering by obtaining exposed items (required by items already
paul@726 1102
    # processed) and putting them at the start of the list.
paul@726 1103
paul@726 1104
    ordered = []
paul@726 1105
paul@726 1106
    while usage:
paul@726 1107
        have_next = False
paul@726 1108
paul@726 1109
        for key, n in usage.items():
paul@726 1110
paul@726 1111
            # Add items needed by no other items to the ordering.
paul@726 1112
paul@726 1113
            if not n:
paul@726 1114
                remove_dependency(key, all_depends, usage, ordered)
paul@726 1115
                have_next = True
paul@726 1116
paul@726 1117
        if not have_next:
paul@726 1118
            raise ValueError, usage
paul@726 1119
paul@726 1120
    return ordered
paul@726 1121
paul@726 1122
def order_dependencies_partial(all_depends):
paul@726 1123
paul@726 1124
    """
paul@726 1125
    Produce a dependency ordering for the 'all_depends' mapping. This mapping
paul@726 1126
    has the form "A depends on B, C...". The result will order A, B, C, and so
paul@726 1127
    on. Where cycles exist, they will be broken and a partial ordering returned.
paul@726 1128
    """
paul@726 1129
paul@726 1130
    usage = init_reverse_dependencies(all_depends)
paul@726 1131
paul@726 1132
    # Duplicate the dependencies for subsequent modification.
paul@726 1133
paul@726 1134
    new_depends = {}
paul@726 1135
    for key, values in all_depends.items():
paul@726 1136
        new_depends[key] = set(values)
paul@726 1137
paul@726 1138
    all_depends = new_depends
paul@726 1139
paul@726 1140
    # Produce an ordering by obtaining exposed items (required by items already
paul@726 1141
    # processed) and putting them at the start of the list.
paul@726 1142
paul@726 1143
    ordered = []
paul@726 1144
paul@726 1145
    while usage:
paul@726 1146
        least = None
paul@726 1147
        least_key = None
paul@726 1148
paul@726 1149
        for key, n in usage.items():
paul@726 1150
paul@726 1151
            # Add items needed by no other items to the ordering.
paul@726 1152
paul@726 1153
            if not n:
paul@726 1154
                remove_dependency(key, all_depends, usage, ordered)
paul@726 1155
                least = 0
paul@726 1156
paul@726 1157
            # When breaking cycles, note the least used items.
paul@726 1158
paul@726 1159
            elif least is None or len(n) < least:
paul@726 1160
                least_key = key
paul@726 1161
                least = len(n)
paul@726 1162
paul@726 1163
        if least:
paul@726 1164
            transfer_dependencies(least_key, all_depends, usage, ordered)
paul@726 1165
paul@726 1166
    return ordered
paul@726 1167
paul@726 1168
def init_reverse_dependencies(all_depends):
paul@726 1169
paul@726 1170
    """
paul@726 1171
    From 'all_depends', providing a mapping of the form "A depends on B, C...",
paul@726 1172
    record the reverse dependencies, making a mapping of the form
paul@726 1173
    "B is needed by A", "C is needed by A", and so on.
paul@726 1174
    """
paul@724 1175
paul@724 1176
    usage = {}
paul@724 1177
paul@724 1178
    # Record path-based dependencies.
paul@724 1179
paul@724 1180
    for key in all_depends.keys():
paul@724 1181
        usage[key] = set()
paul@724 1182
paul@724 1183
    for key, depends in all_depends.items():
paul@724 1184
        for depend in depends:
paul@724 1185
            init_item(usage, depend, set)
paul@724 1186
            usage[depend].add(key)
paul@724 1187
paul@726 1188
    return usage
paul@726 1189
paul@726 1190
def transfer_dependencies(key, all_depends, usage, ordered):
paul@726 1191
paul@726 1192
    """
paul@726 1193
    Transfer items needed by 'key' to those items needing 'key', found using
paul@726 1194
    'all_depends', and updating 'usage'. Insert 'key' into the 'ordered'
paul@726 1195
    collection of dependencies.
paul@724 1196
paul@726 1197
    If "A is needed by X" and "B is needed by A", then transferring items needed
paul@726 1198
    by A will cause "B is needed by X" to be recorded as a consequence.
paul@726 1199
paul@726 1200
    Transferring items also needs to occur in the reverse mapping, so that
paul@726 1201
    "A needs B" and "X needs A", then the consequence must be recorded as
paul@726 1202
    "X needs B".
paul@726 1203
    """
paul@726 1204
paul@726 1205
    ordered.insert(0, key)
paul@724 1206
paul@726 1207
    needing = usage[key]                        # A is needed by X
paul@726 1208
    needed = all_depends.get(key)               # A needs B
paul@726 1209
paul@726 1210
    if needing:
paul@726 1211
        for depend in needing:
paul@726 1212
            l = all_depends.get(depend)
paul@726 1213
            if not l:
paul@726 1214
                continue
paul@724 1215
paul@726 1216
            l.remove(key)                       # X needs (A)
paul@726 1217
paul@726 1218
            if needed:
paul@726 1219
                l.update(needed)                # X needs B...
paul@726 1220
paul@726 1221
                # Prevent self references.
paul@726 1222
paul@726 1223
                if depend in needed:
paul@726 1224
                    l.remove(depend)
paul@724 1225
paul@726 1226
    if needed:
paul@726 1227
        for depend in needed:
paul@726 1228
            l = usage.get(depend)
paul@726 1229
            if not l:
paul@726 1230
                continue
paul@726 1231
paul@726 1232
            l.remove(key)                       # B is needed by (A)
paul@726 1233
            l.update(needing)                   # B is needed by X...
paul@724 1234
paul@726 1235
            # Prevent self references.
paul@726 1236
paul@726 1237
            if depend in needing:
paul@726 1238
                l.remove(depend)
paul@726 1239
paul@726 1240
    if needed:
paul@726 1241
        del all_depends[key]
paul@726 1242
    del usage[key]
paul@726 1243
paul@726 1244
def remove_dependency(key, all_depends, usage, ordered):
paul@724 1245
paul@726 1246
    """
paul@726 1247
    Remove 'key', found in 'all_depends', from 'usage', inserting it into the
paul@726 1248
    'ordered' collection of dependencies.
paul@726 1249
paul@726 1250
    Given that 'usage' for a given key A would indicate that "A needs <nothing>"
paul@726 1251
    upon removing A from 'usage', the outcome is that all keys needing A will
paul@726 1252
    have A removed from their 'usage' records.
paul@726 1253
paul@726 1254
    So, if "B needs A", removing A will cause "B needs <nothing>" to be recorded
paul@726 1255
    as a consequence.
paul@726 1256
    """
paul@724 1257
paul@726 1258
    ordered.insert(0, key)
paul@726 1259
paul@726 1260
    depends = all_depends.get(key)
paul@726 1261
paul@726 1262
    # Reduce usage of the referenced items.
paul@724 1263
paul@726 1264
    if depends:
paul@726 1265
        for depend in depends:
paul@726 1266
            usage[depend].remove(key)
paul@726 1267
paul@726 1268
    del usage[key]
paul@724 1269
paul@0 1270
# General input/output.
paul@0 1271
paul@0 1272
def readfile(filename):
paul@0 1273
paul@0 1274
    "Return the contents of 'filename'."
paul@0 1275
paul@0 1276
    f = open(filename)
paul@0 1277
    try:
paul@0 1278
        return f.read()
paul@0 1279
    finally:
paul@0 1280
        f.close()
paul@0 1281
paul@0 1282
def writefile(filename, s):
paul@0 1283
paul@0 1284
    "Write to 'filename' the string 's'."
paul@0 1285
paul@0 1286
    f = open(filename, "w")
paul@0 1287
    try:
paul@0 1288
        f.write(s)
paul@0 1289
    finally:
paul@0 1290
        f.close()
paul@0 1291
paul@0 1292
# General encoding.
paul@0 1293
paul@0 1294
def sorted_output(x):
paul@0 1295
paul@0 1296
    "Sort sequence 'x' and return a string with commas separating the values."
paul@0 1297
paul@0 1298
    x = map(str, x)
paul@0 1299
    x.sort()
paul@0 1300
    return ", ".join(x)
paul@0 1301
paul@537 1302
def get_string_details(literals, encoding):
paul@512 1303
paul@512 1304
    """
paul@537 1305
    Determine whether 'literals' represent Unicode strings or byte strings,
paul@537 1306
    using 'encoding' to reproduce byte sequences.
paul@537 1307
paul@537 1308
    Each literal is the full program representation including prefix and quotes
paul@537 1309
    recoded by the parser to UTF-8. Thus, any literal found to represent a byte
paul@537 1310
    string needs to be translated back to its original encoding.
paul@537 1311
paul@537 1312
    Return a single encoded literal value, a type name, and the original
paul@537 1313
    encoding as a tuple.
paul@537 1314
    """
paul@537 1315
paul@537 1316
    typename = "unicode"
paul@537 1317
paul@537 1318
    l = []
paul@537 1319
paul@537 1320
    for s in literals:
paul@537 1321
        out, _typename = get_literal_details(s)
paul@537 1322
        if _typename == "str":
paul@537 1323
            typename = "str"
paul@537 1324
        l.append(out)
paul@537 1325
paul@537 1326
    out = "".join(l)
paul@537 1327
paul@537 1328
    # For Unicode values, convert to the UTF-8 program representation.
paul@537 1329
paul@537 1330
    if typename == "unicode":
paul@537 1331
        return out.encode("utf-8"), typename, encoding
paul@537 1332
paul@537 1333
    # For byte string values, convert back to the original encoding.
paul@537 1334
paul@537 1335
    else:
paul@537 1336
        return out.encode(encoding), typename, encoding
paul@537 1337
paul@537 1338
def get_literal_details(s):
paul@537 1339
paul@537 1340
    """
paul@537 1341
    Determine whether 's' represents a Unicode string or a byte string, where
paul@537 1342
    's' contains the full program representation of a literal including prefix
paul@537 1343
    and quotes, recoded by the parser to UTF-8.
paul@512 1344
paul@512 1345
    Find and convert Unicode values starting with <backslash>u or <backslash>U,
paul@512 1346
    and byte or Unicode values starting with <backslash><octal digit> or
paul@512 1347
    <backslash>x.
paul@512 1348
paul@512 1349
    Literals prefixed with "u" cause <backslash><octal digit> and <backslash>x
paul@512 1350
    to be considered as Unicode values. Otherwise, they produce byte values and
paul@512 1351
    cause unprefixed strings to be considered as byte strings.
paul@512 1352
paul@512 1353
    Literals prefixed with "r" do not have their backslash-encoded values
paul@512 1354
    converted unless also prefixed with "u", in which case only the above value
paul@512 1355
    formats are converted, not any of the other special sequences for things
paul@512 1356
    like newlines.
paul@512 1357
paul@537 1358
    Return the literal value as a Unicode object together with the appropriate
paul@537 1359
    type name in a tuple.
paul@512 1360
    """
paul@512 1361
paul@512 1362
    l = []
paul@512 1363
paul@512 1364
    # Identify the quote character and use it to identify the prefix.
paul@512 1365
paul@512 1366
    quote_type = s[-1]
paul@512 1367
    prefix_end = s.find(quote_type)
paul@512 1368
    prefix = s[:prefix_end].lower()
paul@512 1369
paul@512 1370
    if prefix not in ("", "b", "br", "r", "u", "ur"):
paul@512 1371
        raise ValueError, "String literal does not have a supported prefix: %s" % s
paul@512 1372
paul@513 1373
    if "b" in prefix:
paul@513 1374
        typename = "str"
paul@513 1375
    else:
paul@513 1376
        typename = "unicode"
paul@513 1377
paul@512 1378
    # Identify triple quotes or single quotes.
paul@512 1379
paul@512 1380
    if len(s) >= 6 and s[-2] == quote_type and s[-3] == quote_type:
paul@512 1381
        quote = s[prefix_end:prefix_end+3]
paul@512 1382
        current = prefix_end + 3
paul@512 1383
        end = len(s) - 3
paul@512 1384
    else:
paul@512 1385
        quote = s[prefix_end]
paul@512 1386
        current = prefix_end + 1
paul@512 1387
        end = len(s) - 1
paul@512 1388
paul@512 1389
    # Conversions of some quoted values.
paul@512 1390
paul@512 1391
    searches = {
paul@512 1392
        "u" : (6, 16),
paul@512 1393
        "U" : (10, 16),
paul@512 1394
        "x" : (4, 16),
paul@512 1395
        }
paul@512 1396
paul@512 1397
    octal_digits = map(str, range(0, 8))
paul@512 1398
paul@512 1399
    # Translations of some quoted values.
paul@512 1400
paul@512 1401
    escaped = {
paul@512 1402
        "\\" : "\\", "'" : "'", '"' : '"',
paul@512 1403
        "a" : "\a", "b" : "\b", "f" : "\f",
paul@512 1404
        "n" : "\n", "r" : "\r", "t" : "\t",
paul@512 1405
        }
paul@512 1406
paul@512 1407
    while current < end:
paul@512 1408
paul@512 1409
        # Look for quoted values.
paul@512 1410
paul@512 1411
        index = s.find("\\", current)
paul@512 1412
        if index == -1 or index + 1 == end:
paul@512 1413
            l.append(s[current:end])
paul@512 1414
            break
paul@512 1415
paul@512 1416
        # Add the preceding text.
paul@512 1417
paul@512 1418
        l.append(s[current:index])
paul@512 1419
paul@512 1420
        # Handle quoted text.
paul@512 1421
paul@512 1422
        term = s[index+1]
paul@512 1423
paul@512 1424
        # Add Unicode values. Where a string is u-prefixed, even \o and \x
paul@512 1425
        # produce Unicode values.
paul@512 1426
paul@513 1427
        if typename == "unicode" and (
paul@513 1428
            term in ("u", "U") or 
paul@513 1429
            "u" in prefix and (term == "x" or term in octal_digits)):
paul@512 1430
paul@512 1431
            needed, base = searches.get(term, (4, 8))
paul@512 1432
            value = convert_quoted_value(s, index, needed, end, base, unichr)
paul@512 1433
            l.append(value)
paul@512 1434
            current = index + needed
paul@512 1435
paul@512 1436
        # Add raw byte values, changing the string type.
paul@512 1437
paul@512 1438
        elif "r" not in prefix and (
paul@512 1439
             term == "x" or term in octal_digits):
paul@512 1440
paul@512 1441
            needed, base = searches.get(term, (4, 8))
paul@512 1442
            value = convert_quoted_value(s, index, needed, end, base, chr)
paul@512 1443
            l.append(value)
paul@512 1444
            typename = "str"
paul@512 1445
            current = index + needed
paul@512 1446
paul@512 1447
        # Add other escaped values.
paul@512 1448
paul@512 1449
        elif "r" not in prefix and escaped.has_key(term):
paul@512 1450
            l.append(escaped[term])
paul@512 1451
            current = index + 2
paul@512 1452
paul@512 1453
        # Add other text as found.
paul@512 1454
paul@512 1455
        else:
paul@512 1456
            l.append(s[index:index+2])
paul@512 1457
            current = index + 2
paul@512 1458
paul@537 1459
    # Collect the components into a single Unicode object. Since the literal
paul@537 1460
    # text was already in UTF-8 form, interpret plain strings as UTF-8
paul@537 1461
    # sequences.
paul@512 1462
paul@537 1463
    out = []
paul@512 1464
paul@537 1465
    for value in l:
paul@537 1466
        if isinstance(value, unicode):
paul@537 1467
            out.append(value)
paul@537 1468
        else:
paul@537 1469
            out.append(unicode(value, "utf-8"))
paul@512 1470
paul@537 1471
    return "".join(out), typename
paul@512 1472
paul@512 1473
def convert_quoted_value(s, index, needed, end, base, fn):
paul@512 1474
paul@512 1475
    """
paul@512 1476
    Interpret a quoted value in 's' at 'index' with the given 'needed' number of
paul@512 1477
    positions, and with the given 'end' indicating the first position after the
paul@512 1478
    end of the actual string content.
paul@512 1479
paul@512 1480
    Use 'base' as the numerical base when interpreting the value, and use 'fn'
paul@512 1481
    to convert the value to an appropriate type.
paul@512 1482
    """
paul@512 1483
paul@512 1484
    s = s[index:min(index+needed, end)]
paul@512 1485
paul@512 1486
    # Not a complete occurrence.
paul@512 1487
paul@512 1488
    if len(s) < needed:
paul@512 1489
        return s
paul@512 1490
paul@512 1491
    # Test for a well-formed value.
paul@512 1492
paul@512 1493
    try:
paul@512 1494
        first = base == 8 and 1 or 2
paul@512 1495
        value = int(s[first:needed], base)
paul@512 1496
    except ValueError:
paul@512 1497
        return s
paul@512 1498
    else:
paul@512 1499
        return fn(value)
paul@512 1500
paul@0 1501
# Attribute chain decoding.
paul@0 1502
paul@0 1503
def get_attrnames(attrnames):
paul@11 1504
paul@11 1505
    """
paul@11 1506
    Split the qualified attribute chain 'attrnames' into its components,
paul@11 1507
    handling special attributes starting with "#" that indicate type
paul@11 1508
    conformance.
paul@11 1509
    """
paul@11 1510
paul@0 1511
    if attrnames.startswith("#"):
paul@0 1512
        return [attrnames]
paul@0 1513
    else:
paul@0 1514
        return attrnames.split(".")
paul@0 1515
paul@85 1516
def get_name_path(path, name):
paul@85 1517
paul@85 1518
    "Return a suitable qualified name from the given 'path' and 'name'."
paul@85 1519
paul@85 1520
    if "." in name:
paul@85 1521
        return name
paul@85 1522
    else:
paul@85 1523
        return "%s.%s" % (path, name)
paul@85 1524
paul@90 1525
# Usage-related functions.
paul@89 1526
paul@89 1527
def get_types_for_usage(attrnames, objects):
paul@89 1528
paul@89 1529
    """
paul@89 1530
    Identify the types that can support the given 'attrnames', using the
paul@89 1531
    given 'objects' as the catalogue of type details.
paul@89 1532
    """
paul@89 1533
paul@89 1534
    types = []
paul@89 1535
    for name, _attrnames in objects.items():
paul@89 1536
        if set(attrnames).issubset(_attrnames):
paul@89 1537
            types.append(name)
paul@89 1538
    return types
paul@89 1539
paul@90 1540
def get_invoked_attributes(usage):
paul@90 1541
paul@90 1542
    "Obtain invoked attribute from the given 'usage'."
paul@90 1543
paul@90 1544
    invoked = []
paul@90 1545
    if usage:
paul@107 1546
        for attrname, invocation, assignment in usage:
paul@90 1547
            if invocation:
paul@90 1548
                invoked.append(attrname)
paul@90 1549
    return invoked
paul@90 1550
paul@107 1551
def get_assigned_attributes(usage):
paul@107 1552
paul@107 1553
    "Obtain assigned attribute from the given 'usage'."
paul@107 1554
paul@107 1555
    assigned = []
paul@107 1556
    if usage:
paul@107 1557
        for attrname, invocation, assignment in usage:
paul@107 1558
            if assignment:
paul@107 1559
                assigned.append(attrname)
paul@107 1560
    return assigned
paul@107 1561
paul@366 1562
# Type and module functions.
paul@538 1563
# NOTE: This makes assumptions about the __builtins__ structure.
paul@366 1564
paul@366 1565
def get_builtin_module(name):
paul@366 1566
paul@366 1567
    "Return the module name containing the given type 'name'."
paul@366 1568
paul@394 1569
    if name == "string":
paul@538 1570
        modname = "str"
paul@394 1571
    elif name == "utf8string":
paul@538 1572
        modname = "unicode"
paul@394 1573
    elif name == "NoneType":
paul@538 1574
        modname = "none"
paul@394 1575
    else:
paul@538 1576
        modname = name
paul@538 1577
paul@538 1578
    return "__builtins__.%s" % modname
paul@366 1579
paul@366 1580
def get_builtin_type(name):
paul@366 1581
paul@366 1582
    "Return the type name provided by the given Python value 'name'."
paul@366 1583
paul@394 1584
    if name == "str":
paul@394 1585
        return "string"
paul@394 1586
    elif name == "unicode":
paul@394 1587
        return "utf8string"
paul@394 1588
    else:
paul@394 1589
        return name
paul@366 1590
paul@538 1591
def get_builtin_class(name):
paul@538 1592
paul@538 1593
    "Return the full name of the built-in class having the given 'name'."
paul@538 1594
paul@538 1595
    typename = get_builtin_type(name)
paul@538 1596
    module = get_builtin_module(typename)
paul@538 1597
    return "%s.%s" % (module, typename)
paul@538 1598
paul@0 1599
# Useful data.
paul@0 1600
paul@11 1601
predefined_constants = "False", "None", "NotImplemented", "True"
paul@0 1602
paul@845 1603
privileged_attributes = [
paul@845 1604
    "__get_single_item_unchecked__",
paul@845 1605
    ]
paul@845 1606
paul@797 1607
unary_operator_functions = {
paul@797 1608
paul@797 1609
    # Unary operations.
paul@797 1610
paul@797 1611
    "Invert" : "invert",
paul@797 1612
    "UnaryAdd" : "pos",
paul@797 1613
    "UnarySub" : "neg",
paul@797 1614
    }
paul@797 1615
paul@0 1616
operator_functions = {
paul@0 1617
paul@0 1618
    # Fundamental operations.
paul@0 1619
paul@0 1620
    "is" : "is_",
paul@0 1621
    "is not" : "is_not",
paul@0 1622
paul@0 1623
    # Binary operations.
paul@0 1624
paul@0 1625
    "in" : "in_",
paul@0 1626
    "not in" : "not_in",
paul@0 1627
    "Add" : "add",
paul@0 1628
    "Bitand" : "and_",
paul@0 1629
    "Bitor" : "or_",
paul@0 1630
    "Bitxor" : "xor",
paul@0 1631
    "Div" : "div",
paul@0 1632
    "FloorDiv" : "floordiv",
paul@0 1633
    "LeftShift" : "lshift",
paul@0 1634
    "Mod" : "mod",
paul@0 1635
    "Mul" : "mul",
paul@0 1636
    "Power" : "pow",
paul@0 1637
    "RightShift" : "rshift",
paul@0 1638
    "Sub" : "sub",
paul@0 1639
paul@0 1640
    # Augmented assignment.
paul@0 1641
paul@0 1642
    "+=" : "iadd",
paul@0 1643
    "-=" : "isub",
paul@0 1644
    "*=" : "imul",
paul@0 1645
    "/=" : "idiv",
paul@0 1646
    "//=" : "ifloordiv",
paul@0 1647
    "%=" : "imod",
paul@0 1648
    "**=" : "ipow",
paul@0 1649
    "<<=" : "ilshift",
paul@0 1650
    ">>=" : "irshift",
paul@0 1651
    "&=" : "iand",
paul@0 1652
    "^=" : "ixor",
paul@0 1653
    "|=" : "ior",
paul@0 1654
paul@0 1655
    # Comparisons.
paul@0 1656
paul@0 1657
    "==" : "eq",
paul@0 1658
    "!=" : "ne",
paul@0 1659
    "<" : "lt",
paul@0 1660
    "<=" : "le",
paul@0 1661
    ">=" : "ge",
paul@0 1662
    ">" : "gt",
paul@0 1663
    }
paul@0 1664
paul@797 1665
operator_functions.update(unary_operator_functions)
paul@797 1666
paul@0 1667
# vim: tabstop=4 expandtab shiftwidth=4