def union((d1, d2)):
     assert (d1.eq_func is d2.eq_func is None) or (d1.eq_func.const is d2.eq_func.const)
     assert (d1.hash_func is d2.hash_func is None) or (d1.hash_func.const is d2.hash_func.const)
     s_new = SomeOrderedDict(d1.bookkeeper, d1.eq_func, d1.hash_func)
     s_new.key_type = d1.key_type = model.unionof(d1.key_type, d2.key_type)
     s_new.value_type = d1.value_type = model.unionof(d1.value_type, d2.value_type)
     return s_new

 def update_rdict_annotations(self, s_eqfn, s_hashfn, other=None):
     assert self.custom_eq_hash
     s_eqfn = unionof(s_eqfn, self.s_rdict_eqfn)
     s_hashfn = unionof(s_hashfn, self.s_rdict_hashfn)
     self.s_rdict_eqfn = s_eqfn
     self.s_rdict_hashfn = s_hashfn
     self.emulate_rdict_calls(other=other)

 def update_rdict_annotations(self, s_eqfn, s_hashfn, other=None):
     if not self.custom_eq_hash:
         self.custom_eq_hash = True
     else:
         s_eqfn = unionof(s_eqfn, self.s_rdict_eqfn)
         s_hashfn = unionof(s_hashfn, self.s_rdict_hashfn)
     self.s_rdict_eqfn = s_eqfn
     self.s_rdict_hashfn = s_hashfn
     self.emulate_rdict_calls(other=other)

def normalize_calltable_row_annotation(annotator, graphs):
    if len(graphs) <= 1:
        return False   # nothing to do
    graph_bindings = {}
    for graph in graphs:
        graph_bindings[graph] = [annotator.binding(v)
                                 for v in graph.getargs()]
    iterbindings = graph_bindings.itervalues()
    nbargs = len(iterbindings.next())
    for binding in iterbindings:
        assert len(binding) == nbargs

    generalizedargs = []
    for i in range(nbargs):
        args_s = []
        for graph, bindings in graph_bindings.items():
            args_s.append(bindings[i])
        s_value = annmodel.unionof(*args_s)
        generalizedargs.append(s_value)
    result_s = [annotator.binding(graph.getreturnvar())
                for graph in graph_bindings]
    generalizedresult = annmodel.unionof(*result_s)

    conversion = False
    for graph in graphs:
        bindings = graph_bindings[graph]
        need_conversion = (generalizedargs != bindings)
        if need_conversion:
            conversion = True
            oldblock = graph.startblock
            inlist = []
            for j, s_value in enumerate(generalizedargs):
                v = Variable(graph.getargs()[j])
                annotator.setbinding(v, s_value)
                inlist.append(v)
            newblock = Block(inlist)
            # prepare the output args of newblock and link
            outlist = inlist[:]
            newblock.closeblock(Link(outlist, oldblock))
            oldblock.isstartblock = False
            newblock.isstartblock = True
            graph.startblock = newblock
            # finished
            checkgraph(graph)
            annotator.annotated[newblock] = annotator.annotated[oldblock]
        # convert the return value too
        if annotator.binding(graph.getreturnvar()) != generalizedresult:
            conversion = True
            annotator.setbinding(graph.getreturnvar(), generalizedresult)

    return conversion

    def __init__(self, hrtyper):
        self.hrtyper = hrtyper
        RGenOp = hrtyper.RGenOp
        rtyper = hrtyper.rtyper
        bk = rtyper.annotator.bookkeeper
        s_w_bool = annmodel.unionof(bk.immutablevalue(W_BoolObject.w_False),
                                    bk.immutablevalue(W_BoolObject.w_True))
        r_w_bool = rtyper.getrepr(s_w_bool)
        self.ll_False = r_w_bool.convert_const(W_BoolObject.w_False)
        self.ll_True  = r_w_bool.convert_const(W_BoolObject.w_True)

        A = lltype.Array(lltype.typeOf(self.ll_False))
        self.ll_bools = lltype.malloc(A, 2, immortal=True)
        self.ll_bools[0] = self.ll_False
        self.ll_bools[1] = self.ll_True
        self.gv_bools = RGenOp.constPrebuiltGlobal(self.ll_bools)
        self.boolsToken = RGenOp.arrayToken(A)

        self.bools_gv = [RGenOp.constPrebuiltGlobal(self.ll_False),
                         RGenOp.constPrebuiltGlobal(self.ll_True)]

        self.ptrkind = RGenOp.kindToken(r_w_bool.lowleveltype)
        self.boolkind = RGenOp.kindToken(lltype.Bool)

        ll_BoolObject = r_w_bool.rclass.getvtable()
        self.BoolObjectBox = rvalue.redbox_from_prebuilt_value(RGenOp,
                                                               ll_BoolObject)

        self.Falsebox = rvalue.redbox_from_prebuilt_value(RGenOp, False)
        self.Truebox = rvalue.redbox_from_prebuilt_value(RGenOp, True)
        self.boolboxes = [self.Falsebox, self.Truebox]

    def indirect_call(hs_v1, *args_hs):
        hs_graph_list = args_hs[-1]
        args_hs = args_hs[:-1]
        assert hs_graph_list.is_constant()
        graph_list = hs_graph_list.const
        if graph_list is None:
            # cannot follow indirect calls to unknown targets
            return variableoftype(hs_v1.concretetype.TO.RESULT)

        bookkeeper = getbookkeeper()
        myorigin = bookkeeper.myorigin()
        myorigin.__class__ = CallOpOriginFlags     # thud
        fixed = myorigin.read_fixed()
        tsgraphs_accum = []
        hs_res = bookkeeper.graph_family_call(graph_list, fixed, args_hs,
                                              tsgraphs_accum, hs_v1)
        myorigin.any_called_graph = tsgraphs_accum[0]

        if isinstance(hs_res, SomeLLAbstractConstant):
            hs_res.myorigin = myorigin

        # we need to make sure that hs_res does not become temporarily less
        # general as a result of calling another specialized version of the
        # function
        return annmodel.unionof(hs_res, bookkeeper.current_op_binding())

    def pbc_call(self, pbc, args, emulated=None):
        """Analyse a call to a SomePBC() with the given args (list of
        annotations).
        """
        descs = list(pbc.descriptions)
        if not descs:
            return s_ImpossibleValue
        first = descs[0]
        first.mergecallfamilies(*descs[1:])

        if emulated is None:
            whence = self.position_key
            # fish the existing annotation for the result variable,
            # needed by some kinds of specialization.
            fn, block, i = self.position_key
            op = block.operations[i]
            s_previous_result = self.annotator.binding(op.result,
                                                       s_ImpossibleValue)
        else:
            if emulated is True:
                whence = None
            else:
                whence = emulated # callback case
            op = None
            s_previous_result = s_ImpossibleValue

        def schedule(graph, inputcells):
            return self.annotator.recursivecall(graph, whence, inputcells)

        results = []
        for desc in descs:
            results.append(desc.pycall(schedule, args, s_previous_result, op))
        s_result = unionof(*results)
        return s_result

    def _call_single_graph(hs_f1, graph, RESULT, *args_hs):
        bookkeeper = getbookkeeper()
        if not bookkeeper.annotator.policy.look_inside_graph(graph):
            return cannot_follow_call(bookkeeper, graph, args_hs, RESULT)

        # recursive call from the entry point to itself: ignore them and
        # just hope the annotations are correct
        if (bookkeeper.getdesc(graph)._cache.get(None, None) is
            bookkeeper.annotator.translator.graphs[0]):
            return variableoftype(RESULT)

        myorigin = bookkeeper.myorigin()
        myorigin.__class__ = CallOpOriginFlags     # thud
        fixed = myorigin.read_fixed()
        tsgraphs_accum = []
        hs_res = bookkeeper.graph_call(graph, fixed, args_hs,
                                       tsgraphs_accum)
        myorigin.any_called_graph = tsgraphs_accum[0]

        if isinstance(hs_res, SomeLLAbstractConstant):
            hs_res.myorigin = myorigin        

        # we need to make sure that hs_res does not become temporarily less
        # general as a result of calling another specialized version of the
        # function
        return annmodel.unionof(hs_res, bookkeeper.current_op_binding())

 def __call__(self, funcdesc, inputcells):
     from pypy.rpython.lltypesystem import lltype
     args_s = []
     from pypy.annotation import model as annmodel
     for i, argtype in enumerate(self.argtypes):
         if isinstance(argtype, (types.FunctionType, types.MethodType)):
             argtype = argtype(*inputcells)
         if isinstance(argtype, lltype.LowLevelType) and\
             argtype is lltype.Void:
             # XXX the mapping between Void and annotation
             # is not quite well defined
             s_input = inputcells[i]
             assert isinstance(s_input, annmodel.SomePBC)
             assert s_input.is_constant()
             args_s.append(s_input)
         elif argtype is None:
             args_s.append(inputcells[i])     # no change
         else:
             args_s.append(annotation(argtype, bookkeeper=funcdesc.bookkeeper))
     if len(inputcells) != len(args_s):
         raise Exception("%r: expected %d args, got %d" % (funcdesc,
                                                           len(args_s),
                                                           len(inputcells)))
     for i, (s_arg, s_input) in enumerate(zip(args_s, inputcells)):
         s_input = unionof(s_input, s_arg)
         if not s_arg.contains(s_input):
             raise Exception("%r argument %d:\n"
                             "expected %s,\n"
                             "     got %s" % (funcdesc, i+1,
                                          s_arg,
                                          s_input))
     inputcells[:] = args_s

    def compute_result_annotation(self, **kwds_s):
        from pypy.annotation import model as annmodel

        if self.instance.__name__ == 'jit_merge_point':
            self.annotate_hooks(**kwds_s)

        driver = self.instance.im_self
        keys = kwds_s.keys()
        keys.sort()
        expected = ['s_' + name for name in driver.greens + driver.reds
                                if '.' not in name]
        expected.sort()
        if keys != expected:
            raise JitHintError("%s expects the following keyword "
                               "arguments: %s" % (self.instance,
                                                  expected))

        try:
            cache = self.bookkeeper._jit_annotation_cache[driver]
        except AttributeError:
            cache = {}
            self.bookkeeper._jit_annotation_cache = {driver: cache}
        except KeyError:
            cache = {}
            self.bookkeeper._jit_annotation_cache[driver] = cache
        for key, s_value in kwds_s.items():
            s_previous = cache.get(key, annmodel.s_ImpossibleValue)
            s_value = annmodel.unionof(s_previous, s_value)
            if annmodel.isdegenerated(s_value):
                raise JitHintError("mixing incompatible types in argument %s"
                                   " of jit_merge_point/can_enter_jit" %
                                   key[2:])
            cache[key] = s_value

        return annmodel.s_None

def memo(funcdesc, arglist_s):
    from pypy.annotation.model import SomePBC, SomeImpossibleValue, SomeBool
    from pypy.annotation.model import unionof
    # call the function now, and collect possible results
    argvalues = []
    for s in arglist_s:
        if s.is_constant():
            values = [s.const]
        elif isinstance(s, SomePBC):
            values = []
            assert not s.can_be_None, "memo call: cannot mix None and PBCs"
            for desc in s.descriptions:
                if desc.pyobj is None:
                    raise Exception("memo call with a class or PBC that has no "
                                   "corresponding Python object (%r)" % (desc,))
                values.append(desc.pyobj)
        elif isinstance(s, SomeImpossibleValue):
            return s    # we will probably get more possible args later
        elif isinstance(s, SomeBool):
            values = [False, True]
        else:
            raise Exception("memo call: argument must be a class or a frozen "
                            "PBC, got %r" % (s,))
        argvalues.append(values)
    # the list of all possible tuples of arguments to give to the memo function
    possiblevalues = cartesian_product(argvalues)

    # a MemoTable factory -- one MemoTable per family of arguments that can
    # be called together, merged via a UnionFind.
    bookkeeper = funcdesc.bookkeeper
    try:
        memotables = bookkeeper.all_specializations[funcdesc]
    except KeyError:
        func = funcdesc.pyobj
        if func is None:
            raise Exception("memo call: no Python function object to call "
                            "(%r)" % (funcdesc,))

        def compute_one_result(args):
            value = func(*args)
            memotable = MemoTable(funcdesc, args, value)
            memotable.register_finish()
            return memotable

        memotables = UnionFind(compute_one_result)
        bookkeeper.all_specializations[funcdesc] = memotables

    # merge the MemoTables for the individual argument combinations
    firstvalues = possiblevalues.next()
    _, _, memotable = memotables.find(firstvalues)
    for values in possiblevalues:
        _, _, memotable = memotables.union(firstvalues, values)

    if memotable.graph is not None:
        return memotable.graph   # if already computed
    else:
        # otherwise, for now, return the union of each possible result
        return unionof(*[bookkeeper.immutablevalue(v)
                         for v in memotable.table.values()])

 def union((bltn1, bltn2)):
     if (bltn1.analyser != bltn2.analyser or
         bltn1.methodname != bltn2.methodname or
         bltn1.s_self is None or bltn2.s_self is None):
         raise UnionError("cannot merge two different builtin functions "
                          "or methods:\n  %r\n  %r" % (bltn1, bltn2))
     s_self = unionof(bltn1.s_self, bltn2.s_self)
     return SomeBuiltin(bltn1.analyser, s_self, methodname=bltn1.methodname)

 def enter_tunnel(self, bookkeeper, s_obj):
     dict = self._getdict(bookkeeper)
     s_previousobj, reflowpositions = dict.setdefault(self, (annmodel.s_ImpossibleValue, {}))
     s_obj = annmodel.unionof(s_previousobj, s_obj)
     if s_obj != s_previousobj:
         dict[self] = (s_obj, reflowpositions)
         for position in reflowpositions:
             bookkeeper.annotator.reflowfromposition(position)

 def mergeinputargs(self, graph, block, inputcells, called_from_graph=None):
     # Merge the new 'cells' with each of the block's existing input
     # variables.
     oldcells = [self.binding(a) for a in block.inputargs]
     unions = [annmodel.unionof(c1,c2) for c1, c2 in zip(oldcells,inputcells)]
     # if the merged cells changed, we must redo the analysis
     if unions != oldcells:
         self.bindinputargs(graph, block, unions, called_from_graph)

 def generalize_key(self, s_key):
     new_key_type = model.unionof(self.key_type, s_key)
     updated = new_key_type != self.key_type
     if updated:
         self.key_type = new_key_type
         for position_key in self.key_read_locations:
             self.bookkeeper.annotator.reflowfromposition(position_key)
         self.emulate_rdict_calls()

def unioncheck(*somevalues):
    s_value = unionof(*somevalues)
    if isdegenerated(s_value):
        if not getattr(TLS, 'no_side_effects_in_union', 0):
            bookkeeper = getbookkeeper()
            if bookkeeper is not None:
                bookkeeper.ondegenerated('union', s_value)
    return s_value

 def __call__(self, *args):
     args = args[1:]
     assert len(self.s_args) == len(args),\
         "Function %s expects %d arguments, got %d instead" % (self.name,
                                           len(self.s_args), len(args))
     for num, (arg, expected) in enumerate(zip(args, self.s_args)):
         res = unionof(arg, expected)
         assert expected.contains(res)
     return self.s_retval

 def getitem((tup1, int2)):
     if int2.is_immutable_constant():
         try:
             return tup1.items[int2.const]
         except IndexError:
             return s_ImpossibleValue
     else:
         getbookkeeper().count("tuple_random_getitem", tup1)
         return unionof(*tup1.items)

    def add_constant_source(self, classdef, source):
        s_value = source.s_get_value(classdef, self.name)
        if source.instance_level:
            # a prebuilt instance source forces readonly=False, see above
            self.modified(classdef)
        s_new_value = unionof(self.s_value, s_value)
        if isdegenerated(s_new_value):
            self.bookkeeper.ondegenerated("source %r attr %s" % (source, self.name), s_new_value)

        self.s_value = s_new_value

 def compute_result_annotation(self, *args_s):
     if hasattr(self, 'ann_hook'):
         self.ann_hook()
     if self.signature_args is not None:
         assert len(args_s) == len(self.signature_args),\
                "Argument number mismatch"
         for arg, expected in zip(args_s, self.signature_args):
             arg = unionof(arg, expected)
             assert expected.contains(arg)
     return self.signature_result