Read about our upcoming Code of Conduct on this issue

annrpython.py 27.5 KB
Newer Older
Greg Price's avatar
Greg Price committed
1
2
from __future__ import absolute_import

3
import types
Ronan Lamy's avatar
Ronan Lamy committed
4
from collections import defaultdict
5
from contextlib import contextmanager
Brian Kearns's avatar
Brian Kearns committed
6

7
from rpython.tool.ansi_print import AnsiLogger
8
from rpython.tool.pairtype import pair
9
from rpython.tool.error import (format_blocked_annotation_error,
10
                             gather_error, source_lines)
Ronan Lamy's avatar
Ronan Lamy committed
11
from rpython.flowspace.model import Variable, Constant, checkgraph
Alexander Hesse's avatar
Alexander Hesse committed
12
from rpython.translator import simplify, transform
13
from rpython.annotator import model as annmodel, signature
Ronan Lamy's avatar
Ronan Lamy committed
14
from rpython.annotator.model import (
15
    typeof, s_ImpossibleValue, SomeInstance, intersection, difference)
Alexander Hesse's avatar
Alexander Hesse committed
16
from rpython.annotator.bookkeeper import Bookkeeper
17
from rpython.rtyper.normalizecalls import perform_normalizations
Brian Kearns's avatar
Brian Kearns committed
18

19
log = AnsiLogger("annrpython")
20
21


22
class RPythonAnnotator(object):
23
    """Block annotator for RPython.
24
    See description in doc/translation.txt."""
25

26
27
    def __init__(self, translator=None, policy=None, bookkeeper=None,
            keepgoing=False):
Alexander Hesse's avatar
Alexander Hesse committed
28
        import rpython.rtyper.extfuncregistry # has side effects
Michael Hudson's avatar
Michael Hudson committed
29

30
31
        if translator is None:
            # interface for tests
Alexander Hesse's avatar
Alexander Hesse committed
32
            from rpython.translator.translator import TranslationContext
33
34
            translator = TranslationContext()
            translator.annotator = self
35
        self.translator = translator
36
        self.genpendingblocks=[{}] # [{block: graph-containing-it}] * generation
37
        self.annotated = {}      # set of blocks already seen
38
        self.added_blocks = None # see processblock() below
39
40
        self.links_followed = {} # set of links that have ever been followed
        self.notify = {}        # {block: {positions-to-reflow-from-when-done}}
Armin Rigo's avatar
Armin Rigo committed
41
        self.fixed_graphs = {}  # set of graphs not to annotate again
42
        self.blocked_blocks = {} # set of {blocked_block: (graph, index)}
Armin Rigo's avatar
Armin Rigo committed
43
        # --- the following information is recorded for debugging ---
44
        self.blocked_graphs = {} # set of graphs that have blocked blocks
45
46
47
        # --- end of debugging information ---
        self.frozen = False
        if policy is None:
Alexander Hesse's avatar
Alexander Hesse committed
48
            from rpython.annotator.policy import AnnotatorPolicy
49
            self.policy = AnnotatorPolicy()
50
51
        else:
            self.policy = policy
Armin Rigo's avatar
Armin Rigo committed
52
53
54
        if bookkeeper is None:
            bookkeeper = Bookkeeper(self)
        self.bookkeeper = bookkeeper
55
56
57
        self.keepgoing = keepgoing
        self.failed_blocks = set()
        self.errors = []
58
59

    def __getstate__(self):
60
        attrs = """translator genpendingblocks annotated links_followed
Samuele Pedroni's avatar
Samuele Pedroni committed
61
        notify bookkeeper frozen policy added_blocks""".split()
62
63
64
        ret = self.__dict__.copy()
        for key, value in ret.items():
            if key not in attrs:
65
66
67
                assert type(value) is dict, (
                    "%r is not dict. please update %s.__getstate__" %
                    (key, self.__class__.__name__))
68
69
70
71
72
                ret[key] = {}
        return ret

    #___ convenience high-level interface __________________

73
74
    def build_types(self, function, input_arg_types, complete_now=True,
                    main_entry_point=False):
75
        """Recursively build annotations about the specific entry point."""
76
        assert isinstance(function, types.FunctionType), "fix that!"
77

Alexander Hesse's avatar
Alexander Hesse committed
78
        from rpython.annotator.policy import AnnotatorPolicy
79
        policy = AnnotatorPolicy()
80
        # make input arguments and set their type
81
        args_s = [self.typeannotation(t) for t in input_arg_types]
82

83
84
85
86
        # XXX hack
        annmodel.TLS.check_str_without_nul = (
            self.translator.config.translation.check_str_without_nul)

87
88
        with self.using_policy(policy):
            flowgraph, inputs_s = self.get_call_parameters(function, args_s)
89

90
91
        if main_entry_point:
            self.translator.entry_point_graph = flowgraph
92
        return self.build_graph_types(flowgraph, inputs_s, complete_now=complete_now)
93

94
95
96
97
    def get_call_parameters(self, function, args_s):
        with self.bookkeeper.at_position(None):
            desc = self.bookkeeper.getdesc(function)
            return desc.get_call_parameters(args_s)
Armin Rigo's avatar
Armin Rigo committed
98
99
100

    def annotate_helper(self, function, args_s, policy=None):
        if policy is None:
Alexander Hesse's avatar
Alexander Hesse committed
101
            from rpython.annotator.policy import AnnotatorPolicy
Armin Rigo's avatar
Armin Rigo committed
102
            policy = AnnotatorPolicy()
103
104
105
            # XXX hack
            annmodel.TLS.check_str_without_nul = (
                self.translator.config.translation.check_str_without_nul)
106
107
108
109
        with self.using_policy(policy):
            graph, inputcells = self.get_call_parameters(function, args_s)
            self.build_graph_types(graph, inputcells, complete_now=False)
            self.complete_helpers()
110
        return graph
111

112
    def complete_helpers(self):
113
114
        saved = self.added_blocks
        self.added_blocks = {}
115
116
117
118
119
120
        try:
            self.complete()
            # invoke annotation simplifications for the new blocks
            self.simplify(block_subset=self.added_blocks)
        finally:
            self.added_blocks = saved
121
122
123
124
125

    @contextmanager
    def using_policy(self, policy):
        """A context manager that temporarily replaces the annotator policy"""
        old_policy = self.policy
Armin Rigo's avatar
Armin Rigo committed
126
        self.policy = policy
127
128
        yield
        self.policy = old_policy
129

Armin Rigo's avatar
Armin Rigo committed
130
    def build_graph_types(self, flowgraph, inputcells, complete_now=True):
131
132
        checkgraph(flowgraph)

133
        nbarg = len(flowgraph.getargs())
134
        assert len(inputcells) == nbarg # wrong number of args
135

136
        # register the entry point
Armin Rigo's avatar
Armin Rigo committed
137
        self.addpendinggraph(flowgraph, inputcells)
138
        # recursively proceed until no more pending block is left
Armin Rigo's avatar
Armin Rigo committed
139
140
        if complete_now:
            self.complete()
141
        return self.annotation(flowgraph.getreturnvar())
142
143
144
145
146
147
148

    def gettype(self, variable):
        """Return the known type of a control flow graph variable,
        defaulting to 'object'."""
        if isinstance(variable, Constant):
            return type(variable.value)
        elif isinstance(variable, Variable):
149
150
151
            s_variable = variable.annotation
            if s_variable:
                return s_variable.knowntype
152
153
154
            else:
                return object
        else:
155
            raise TypeError("Variable or Constant instance expected, "
156
157
158
159
                              "got %r" % (variable,))

    def getuserclassdefinitions(self):
        """Return a list of ClassDefs."""
160
        return self.bookkeeper.classdefs
161
162
163

    #___ medium-level interface ____________________________

Armin Rigo's avatar
Armin Rigo committed
164
165
166
    def addpendinggraph(self, flowgraph, inputcells):
        self.addpendingblock(flowgraph, flowgraph.startblock, inputcells)

Armin Rigo's avatar
Armin Rigo committed
167
    def addpendingblock(self, graph, block, cells):
168
        """Register an entry point into block with the given input cells."""
Armin Rigo's avatar
Armin Rigo committed
169
170
171
172
173
        if graph in self.fixed_graphs:
            # special case for annotating/rtyping in several phases: calling
            # a graph that has already been rtyped.  Safety-check the new
            # annotations that are passed in, and don't annotate the old
            # graph -- it's already low-level operations!
174
            for a, s_newarg in zip(block.inputargs, cells):
175
                s_oldarg = a.annotation
176
177
178
                # XXX: Should use s_oldarg.contains(s_newarg) but that breaks
                # PyPy translation
                if annmodel.unionof(s_oldarg, s_newarg) != s_oldarg:
179
180
181
182
183
                    raise annmodel.AnnotatorError(
                        "Late-stage annotation is not allowed to modify the "
                        "existing annotation for variable %s: %s" %
                            (a, s_oldarg))

184
        else:
Armin Rigo's avatar
Armin Rigo committed
185
186
            assert not self.frozen
            if block not in self.annotated:
Armin Rigo's avatar
Armin Rigo committed
187
                self.bindinputargs(graph, block, cells)
Armin Rigo's avatar
Armin Rigo committed
188
            else:
Armin Rigo's avatar
Armin Rigo committed
189
                self.mergeinputargs(graph, block, cells)
Armin Rigo's avatar
Armin Rigo committed
190
            if not self.annotated[block]:
191
192
193
194
195
196
197
198
199
200
201
                self.schedulependingblock(graph, block)

    def schedulependingblock(self, graph, block):
        # 'self.genpendingblocks' is a list of dictionaries which is
        # logically equivalent to just one dictionary.  But we keep a
        # 'generation' number on each block (=key), and whenever we
        # process a block, we increase its generation number.  The
        # block is added to the 'genpendingblocks' indexed by its
        # generation number.  See complete_pending_blocks() below.
        generation = getattr(block, 'generation', 0)
        self.genpendingblocks[generation][block] = graph
202

203
    def complete_pending_blocks(self):
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
        while True:
            # Find the first of the dictionaries in 'self.genpendingblocks'
            # which is not empty
            gen = 0
            for pendingblocks in self.genpendingblocks:
                if pendingblocks:
                    break
                gen += 1
            else:
                return    # all empty => done

            gen += 1   # next generation number
            if len(self.genpendingblocks) == gen:
                self.genpendingblocks.append({})

            # Process all blocks at this level
            # (if any gets re-inserted, it will be into the next level)
            while pendingblocks:
                block, graph = pendingblocks.popitem()
                block.generation = gen
224
                self.processblock(graph, block)
225
226
227

    def complete(self):
        """Process pending blocks until none is left."""
Armin Rigo's avatar
Armin Rigo committed
228
        while True:
229
            self.complete_pending_blocks()
Armin Rigo's avatar
Armin Rigo committed
230
            self.policy.no_more_blocks_to_annotate(self)
231
            if not any(self.genpendingblocks):
Armin Rigo's avatar
Armin Rigo committed
232
                break   # finished
233
234
235
236
237
238
239
240
        # make sure that the return variables of all graphs is annotated
        if self.added_blocks is not None:
            newgraphs = [self.annotated[block] for block in self.added_blocks]
            newgraphs = dict.fromkeys(newgraphs)
            got_blocked_blocks = False in newgraphs
        else:
            newgraphs = self.translator.graphs  #all of them
            got_blocked_blocks = False in self.annotated.values()
241
242
243
244
245
246
        if self.failed_blocks:
            text = ('Annotation failed, %s errors were recorded:' %
                    len(self.errors))
            text += '\n-----'.join(str(e) for e in self.errors)
            raise annmodel.AnnotatorError(text)

247
        if got_blocked_blocks:
Armin Rigo's avatar
Armin Rigo committed
248
249
            for graph in self.blocked_graphs.values():
                self.blocked_graphs[graph] = True
250

Armin Rigo's avatar
Armin Rigo committed
251
252
            blocked_blocks = [block for block, done in self.annotated.items()
                                    if done is False]
Armin Rigo's avatar
Armin Rigo committed
253
            assert len(blocked_blocks) == len(self.blocked_blocks)
254

Armin Rigo's avatar
Armin Rigo committed
255
            text = format_blocked_annotation_error(self, self.blocked_blocks)
256
            #raise SystemExit()
257
            raise annmodel.AnnotatorError(text)
258
259
        for graph in newgraphs:
            v = graph.getreturnvar()
260
            if v.annotation is None:
Ronan Lamy's avatar
Ronan Lamy committed
261
                self.setbinding(v, s_ImpossibleValue)
262
263
264
265
266
267
            v = graph.exceptblock.inputargs[1]
            if v.annotation is not None and v.annotation.can_be_none():
                raise annmodel.AnnotatorError(
                    "%r is found by annotation to possibly raise None, "
                    "but the None was not suppressed by the flow space" %
                        (graph,))
268
269
270

    def validate(self):
        """Check that the annotation results are valid"""
271
        self.bookkeeper.check_no_flags_on_instances()
272

273
    def annotation(self, arg):
274
275
        "Gives the SomeValue corresponding to the given Variable or Constant."
        if isinstance(arg, Variable):
276
            return arg.annotation
277
        elif isinstance(arg, Constant):
Ronan Lamy's avatar
Ronan Lamy committed
278
            return self.bookkeeper.immutablevalue(arg.value)
279
        else:
280
            raise TypeError('Variable or Constant expected, got %r' % (arg,))
281

282
283
284
285
286
287
288
    def binding(self, arg):
        "Gives the SomeValue corresponding to the given Variable or Constant."
        s_arg = self.annotation(arg)
        if s_arg is None:
            raise KeyError
        return s_arg

289
    def typeannotation(self, t):
290
        return signature.annotation(t, self.bookkeeper)
291

Armin Rigo's avatar
Armin Rigo committed
292
    def setbinding(self, arg, s_value):
293
294
        s_old = arg.annotation
        if s_old is not None:
Amaury Forgeot d'Arc's avatar
Amaury Forgeot d'Arc committed
295
296
            if not s_value.contains(s_old):
                log.WARNING("%s does not contain %s" % (s_value, s_old))
297
                log.WARNING("%s" % annmodel.union(s_value, s_old))
Amaury Forgeot d'Arc's avatar
Amaury Forgeot d'Arc committed
298
                assert False
299
        arg.annotation = s_value
300

301
302
303
304
305
306
307
308
    def warning(self, msg, pos=None):
        if pos is None:
            try:
                pos = self.bookkeeper.position_key
            except AttributeError:
                pos = '?'
        if pos != '?':
            pos = self.whereami(pos)
309

310
        log.WARNING("%s/ %s" % (pos, msg))
311
312


313
314
    #___ interface for annotator.bookkeeper _______

Armin Rigo's avatar
Armin Rigo committed
315
    def recursivecall(self, graph, whence, inputcells):
Ronan Lamy's avatar
Ronan Lamy committed
316
        if whence is not None:
Armin Rigo's avatar
Armin Rigo committed
317
            parent_graph, parent_block, parent_index = whence
318
319
            tag = parent_block, parent_index
            self.translator.update_call_graph(parent_graph, graph, tag)
Ronan Lamy's avatar
Ronan Lamy committed
320
321
322
323
            # self.notify[graph.returnblock] is a set of call
            # points to this func which triggers a reflow whenever the
            # return block of this graph has been analysed.
            returnpositions = self.notify.setdefault(graph.returnblock, set())
324
            returnpositions.add(whence)
325
326

        # generalize the function's input arguments
Armin Rigo's avatar
Armin Rigo committed
327
        self.addpendingblock(graph, graph.startblock, inputcells)
328
329
330
331

        # get the (current) return value
        v = graph.getreturnvar()
        try:
332
            return self.binding(v)
333
        except KeyError:
334
335
            # the function didn't reach any return statement so far.
            # (some functions actually never do, they always raise exceptions)
Ronan Lamy's avatar
Ronan Lamy committed
336
            return s_ImpossibleValue
337
338

    def reflowfromposition(self, position_key):
339
340
        graph, block, index = position_key
        self.reflowpendingblock(graph, block)
341

342
343
344
345
346
347
348
349
350
351
352
353
    def call_sites(self):
        newblocks = self.added_blocks
        if newblocks is None:
            newblocks = self.annotated  # all of them
        for block in newblocks:
            for op in block.operations:
                if op.opname in ('simple_call', 'call_args'):
                    yield op

                # some blocks are partially annotated
                if op.result.annotation is None:
                    break   # ignore the unannotated part
354
355
356

    #___ simplification (should be moved elsewhere?) _______

Samuele Pedroni's avatar
Samuele Pedroni committed
357
    def simplify(self, block_subset=None, extra_passes=None):
358
        # Generic simplifications
Samuele Pedroni's avatar
Samuele Pedroni committed
359
360
        transform.transform_graph(self, block_subset=block_subset,
                                  extra_passes=extra_passes)
361
        if block_subset is None:
362
            graphs = self.translator.graphs
363
364
365
        else:
            graphs = {}
            for block in block_subset:
366
367
368
                graph = self.annotated.get(block)
                if graph:
                    graphs[graph] = True
369
        for graph in graphs:
370
            simplify.eliminate_empty_blocks(graph)
371
        self.bookkeeper.compute_at_fixpoint()
372
373
        if block_subset is None:
            perform_normalizations(self)
374
375
376
377


    #___ flowing annotations in blocks _____________________

378
    def processblock(self, graph, block):
379
380
381
382
383
384
        # Important: this is not called recursively.
        # self.flowin() can only issue calls to self.addpendingblock().
        # The analysis of a block can be in three states:
        #  * block not in self.annotated:
        #      never seen the block.
        #  * self.annotated[block] == False:
385
        #      the input variables of the block have bindings but we
386
        #      still have to consider all the operations in the block.
387
        #  * self.annotated[block] == graph-containing-block:
388
389
390
391
        #      analysis done (at least until we find we must generalize the
        #      input variables).

        #print '* processblock', block, cells
392
        self.annotated[block] = graph
393
394
        if block in self.failed_blocks:
            return
Armin Rigo's avatar
Armin Rigo committed
395
396
        if block in self.blocked_blocks:
            del self.blocked_blocks[block]
397
        try:
398
            self.flowin(graph, block)
399
        except BlockedInference as e:
400
            self.annotated[block] = False   # failed, hopefully temporarily
401
            self.blocked_blocks[block] = (graph, e.opindex)
402
        except Exception as e:
403
404
405
406
407
            # hack for debug tools only
            if not hasattr(e, '__annotator_block'):
                setattr(e, '__annotator_block', block)
            raise

408
409
410
411
412
413
        # The dict 'added_blocks' is used by rpython.annlowlevel to
        # detect which are the new blocks that annotating an additional
        # small helper creates.
        if self.added_blocks is not None:
            self.added_blocks[block] = True

414
    def reflowpendingblock(self, graph, block):
415
        assert not self.frozen
Armin Rigo's avatar
Armin Rigo committed
416
        assert graph not in self.fixed_graphs
417
        self.schedulependingblock(graph, block)
418
419
        assert block in self.annotated
        self.annotated[block] = False  # must re-flow
420
        self.blocked_blocks[block] = (graph, None)
421

Armin Rigo's avatar
Armin Rigo committed
422
    def bindinputargs(self, graph, block, inputcells):
423
424
425
        # Create the initial bindings for the input args of a block.
        assert len(block.inputargs) == len(inputcells)
        for a, cell in zip(block.inputargs, inputcells):
Armin Rigo's avatar
Armin Rigo committed
426
            self.setbinding(a, cell)
427
        self.annotated[block] = False  # must flowin.
428
        self.blocked_blocks[block] = (graph, None)
429

Armin Rigo's avatar
Armin Rigo committed
430
    def mergeinputargs(self, graph, block, inputcells):
431
432
433
        # Merge the new 'cells' with each of the block's existing input
        # variables.
        oldcells = [self.binding(a) for a in block.inputargs]
434
435
        try:
            unions = [annmodel.unionof(c1,c2) for c1, c2 in zip(oldcells,inputcells)]
436
        except annmodel.UnionError as e:
437
438
            # Add source code to the UnionError
            e.source = '\n'.join(source_lines(graph, block, None, long=True))
439
440
441
442
            if self.keepgoing:
                self.errors.append(e)
                self.failed_blocks.add(block)
                return
443
            raise
444
445
        # if the merged cells changed, we must redo the analysis
        if unions != oldcells:
Armin Rigo's avatar
Armin Rigo committed
446
            self.bindinputargs(graph, block, unions)
447

448
449
450
451
    def apply_renaming(self, s_out, renaming):
        if hasattr(s_out, 'is_type_of'):
            renamed_is_type_of = []
            for v in s_out.is_type_of:
Ronan Lamy's avatar
Ronan Lamy committed
452
                renamed_is_type_of += renaming[v]
453
            assert s_out.knowntype is type
454
            newcell = typeof(renamed_is_type_of)
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
            if s_out.is_constant():
                newcell.const = s_out.const
            s_out = newcell

        if hasattr(s_out, 'knowntypedata'):
            renamed_knowntypedata = {}
            for value, constraints in s_out.knowntypedata.items():
                renamed_knowntypedata[value] = {}
                for v, s in constraints.items():
                    new_vs = renaming.get(v, [])
                    for new_v in new_vs:
                        renamed_knowntypedata[value][new_v] = s
            assert isinstance(s_out, annmodel.SomeBool)
            newcell = annmodel.SomeBool()
            if s_out.is_constant():
                newcell.const = s_out.const
            s_out = newcell
            s_out.set_knowntypedata(renamed_knowntypedata)
        return s_out


476
    def whereami(self, position_key):
477
        graph, block, i = position_key
478
479
480
481
482
483
484
485
        blk = ""
        if block:
            at = block.at()
            if at:
                blk = " block"+at
        opid=""
        if i is not None:
            opid = " op=%d" % i
486
        return repr(graph) + blk + opid
487

488
    def flowin(self, graph, block):
489
        try:
490
491
492
            i = 0
            while i < len(block.operations):
                op = block.operations[i]
493
                with self.bookkeeper.at_position((graph, block, i)):
494
495
496
497
498
499
500
                    new_ops = op.transform(self)
                    if new_ops is not None:
                        block.operations[i:i+1] = new_ops
                        if not new_ops:
                            continue
                        new_ops[-1].result = op.result
                        op = new_ops[0]
501
                    self.consider_op(op)
502
                i += 1
503

504
        except BlockedInference as e:
505
            if e.op is block.raising_op:
506
507
508
509
510
511
512
                # this is the case where the last operation of the block will
                # always raise an exception which is immediately caught by
                # an exception handler.  We then only follow the exceptional
                # branches.
                exits = [link for link in block.exits
                              if link.exitcase is not None]

513
            elif e.op.opname in ('simple_call', 'call_args', 'next'):
514
515
516
517
                # XXX warning, keep the name of the call operations in sync
                # with the flow object space.  These are the operations for
                # which it is fine to always raise an exception.  We then
                # swallow the BlockedInference and that's it.
518
                # About 'next': see test_annotate_iter_empty_container().
519
520
521
522
523
524
                return

            else:
                # other cases are problematic (but will hopefully be solved
                # later by reflowing).  Throw the BlockedInference up to
                # processblock().
525
                e.opindex = i
526
                raise
Armin Rigo's avatar
Armin Rigo committed
527
528
529
530

        except annmodel.HarmlesslyBlocked:
            return

531
532
        except annmodel.AnnotatorError as e: # note that UnionError is a subclass
            e.source = gather_error(self, graph, block, i)
533
534
535
536
            if self.keepgoing:
                self.errors.append(e)
                self.failed_blocks.add(block)
                return
537
538
            raise

539
540
541
542
543
        else:
            # dead code removal: don't follow all exits if the exitswitch
            # is known
            exits = block.exits
            if isinstance(block.exitswitch, Variable):
544
                s_exitswitch = self.binding(block.exitswitch)
545
546
547
548
                if s_exitswitch.is_constant():
                    exits = [link for link in exits
                                  if link.exitcase == s_exitswitch.const]

549
550
        if block.canraise:
            op = block.raising_op
551
552
553
554
555
556
557
558
            s_exception = self.get_exception(op)
            for link in exits:
                case = link.exitcase
                if case is None:
                    self.follow_link(graph, link, {})
                    continue
                if s_exception == s_ImpossibleValue:
                    break
559
                s_case = SomeInstance(self.bookkeeper.getuniqueclassdef(case))
560
                s_matching_exc = intersection(s_exception, s_case)
561
562
                if s_matching_exc != s_ImpossibleValue:
                    self.follow_raise_link(graph, link, s_matching_exc)
563
                s_exception = difference(s_exception, s_case)
564
565
        else:
            if isinstance(block.exitswitch, Variable):
566
567
                knowntypedata = getattr(
                    block.exitswitch.annotation, "knowntypedata", {})
568
569
570
571
572
            else:
                knowntypedata = {}
            for link in exits:
                constraints = knowntypedata.get(link.exitcase, {})
                self.follow_link(graph, link, constraints)
573
574

        if block in self.notify:
575
576
            for position in self.notify[block]:
                self.reflowfromposition(position)
577

578

579
    def follow_link(self, graph, link, constraints):
580
581
582
583
584
        assert not (isinstance(link.exitcase, (types.ClassType, type)) and
                issubclass(link.exitcase, BaseException))

        ignore_link = False
        inputs_s = []
Ronan Lamy's avatar
Ronan Lamy committed
585
        renaming = defaultdict(list)
586
        for v_out, v_input in zip(link.args, link.target.inputargs):
Ronan Lamy's avatar
Ronan Lamy committed
587
588
            renaming[v_out].append(v_input)

589
590
591
592
593
594
        for v_out in link.args:
            s_out = self.annotation(v_out)
            if v_out in constraints:
                s_constraint = constraints[v_out]
                s_out = pair(s_out, s_constraint).improve()
                # ignore links that try to pass impossible values
Ronan Lamy's avatar
Ronan Lamy committed
595
                if s_out == s_ImpossibleValue:
596
                    ignore_link = True
597
            s_out = self.apply_renaming(s_out, renaming)
598
599
600
601
602
603
604
            inputs_s.append(s_out)
        if ignore_link:
            return

        self.links_followed[link] = True
        self.addpendingblock(graph, link.target, inputs_s)

605
    def follow_raise_link(self, graph, link, s_last_exc_value):
606
607
608
609
610
611
612
        v_last_exc_type = link.last_exception
        v_last_exc_value = link.last_exc_value

        assert (isinstance(link.exitcase, (types.ClassType, type)) and
                issubclass(link.exitcase, BaseException))

        assert v_last_exc_type and v_last_exc_value
613

614
615
616
617
        if isinstance(v_last_exc_value, Variable):
            self.setbinding(v_last_exc_value, s_last_exc_value)

        if isinstance(v_last_exc_type, Variable):
618
            self.setbinding(v_last_exc_type, typeof([v_last_exc_value]))
Ronan Lamy's avatar
Ronan Lamy committed
619

620
        inputs_s = []
Ronan Lamy's avatar
Ronan Lamy committed
621
        renaming = defaultdict(list)
622
        for v_out, v_input in zip(link.args, link.target.inputargs):
Ronan Lamy's avatar
Ronan Lamy committed
623
624
            renaming[v_out].append(v_input)

625
626
        for v_out, v_input in zip(link.args, link.target.inputargs):
            if v_out == v_last_exc_type:
627
                s_out = typeof(renaming[v_last_exc_value])
Ronan Lamy's avatar
Ronan Lamy committed
628
629
                if isinstance(v_last_exc_type, Constant):
                    s_out.const = v_last_exc_type.value
630
631
                elif v_last_exc_type.annotation.is_constant():
                    s_out.const = v_last_exc_type.annotation.const
Ronan Lamy's avatar
Ronan Lamy committed
632
                inputs_s.append(s_out)
Ronan Lamy's avatar
Ronan Lamy committed
633
            else:
634
                s_out = self.annotation(v_out)
635
                s_out = self.apply_renaming(s_out, renaming)
636
                inputs_s.append(s_out)
Ronan Lamy's avatar
Ronan Lamy committed
637
638

        self.links_followed[link] = True
639
        self.addpendingblock(graph, link.target, inputs_s)
Ronan Lamy's avatar
Ronan Lamy committed
640

641
642
    #___ creating the annotations based on operations ______

643
    def consider_op(self, op):
644
645
646
647
648
649
        # let's be careful about avoiding propagated SomeImpossibleValues
        # to enter an op; the latter can result in violations of the
        # more general results invariant: e.g. if SomeImpossibleValue enters is_
        #  is_(SomeImpossibleValue, None) -> SomeBool
        #  is_(SomeInstance(not None), None) -> SomeBool(const=False) ...
        # boom -- in the assert of setbinding()
650
651
        for arg in op.args:
            if isinstance(self.annotation(arg), annmodel.SomeImpossibleValue):
652
                raise BlockedInference(self, op, -1)
653
        resultcell = op.consider(self)
654
        if resultcell is None:
Ronan Lamy's avatar
Ronan Lamy committed
655
656
            resultcell = s_ImpossibleValue
        elif resultcell == s_ImpossibleValue:
657
            raise BlockedInference(self, op, -1) # the operation cannot succeed
658
659
660
661
        assert isinstance(resultcell, annmodel.SomeObject)
        assert isinstance(op.result, Variable)
        self.setbinding(op.result, resultcell)  # bind resultcell to op.result

662
663
664
665
666
667
668
669
670
671
    def get_exception(self, operation):
        """
        Return the annotation for all exceptions that `operation` may raise.
        """
        can_only_throw = operation.get_can_only_throw(self)
        if can_only_throw is None:
            return SomeInstance(self.bookkeeper.getuniqueclassdef(Exception))
        else:
            return self.bookkeeper.new_exception(can_only_throw)

672
673
674
675
676

class BlockedInference(Exception):
    """This exception signals the type inference engine that the situation
    is currently blocked, and that it should try to progress elsewhere."""

677
    def __init__(self, annotator, op, opindex):
678
679
680
681
682
683
        self.annotator = annotator
        try:
            self.break_at = annotator.bookkeeper.position_key
        except AttributeError:
            self.break_at = None
        self.op = op
684
        self.opindex = opindex
685
686
687
688
689
690
691
692
693

    def __repr__(self):
        if not self.break_at:
            break_at = "?"
        else:
            break_at = self.annotator.whereami(self.break_at)
        return "<BlockedInference break_at %s [%s]>" %(break_at, self.op)

    __str__ = __repr__