generators_prototype.py

C++的一个好库。。。现在很流行

# Copyright David Abrahams 2003. Permission to copy, use,
# modify, sell and distribute this software is granted provided this
# copyright notice appears in all copies. This software is provided
# "as is" without express or implied warranty, and with no claim as
# to its suitability for any purpose.

# Importing by a different name keeps PyChecker happy
from __future__ import generators as generators_ 
import sys

    
class Generator(object):
    """Representation of a transformation from source to target types.
    
       sources and targets may be either strings or sequences of
       strings.

       >>> print Generator(('obj*', 'lib*'), 'exe')
       exe <- obj*,lib*

       >>> assert Generator('c','o').unary
    """
    
    def __init__(self, sources, targets):
        """
        >>> g = Generator(['obj*', 'z', 'cpp'], ['lib','dll'])
        >>> g.signature
        [('cpp', 1, 1), ('obj', 0, '*'), ('z', 1, 1)]
        >>> g = Generator('cpp', 'obj')
        >>> g.signature
        [('cpp', 1, 1)]
        """
        self.sources = _sequence_of_strings(sources)
        self.targets =_sequence_of_strings(targets)
        self.targets_ = _string_multiset(targets)

        signature = {}
        stars = {}
        for s in self.sources:
            if s.endswith('*'):
                stars[s[:-1]] = 1
                signature.setdefault(s[:-1],0)
            else:
                signature[s] = signature.get(s,0) + 1

        self.signature = []
        for t, n in signature.items():
            if t in stars:
                self.signature.append((t, n, '*'))
            else:
                self.signature.append((t, n, n))

        self.signature.sort() # makes doctests nicer
        
        # Remember whether the signature is strictly unary
        self.unary = not stars and len(self.sources) == 1

    def match(self, group):
        """If group satisfies an element of the signature, returns an
        amended signature that consists of all other elements.
        Otherwise, returns None.
        >>> g = Generator(['obj*', 'z', 'cpp', 'z'], ['lib','dll'])
        >>> g.match(TargetTypeGroup('obj',12))
        [('cpp', 1, 1), ('z', 2, 2)]
        >>> g.match(TargetTypeGroup('cpp',12)) # None
        
        >>> g.match(TargetTypeGroup('cpp',1))
        [('obj', 0, '*'), ('z', 2, 2)]

        >>> g.match(TargetTypeGroup('z',2))
        [('cpp', 1, 1), ('obj', 0, '*')]
        
        >>> Generator('cpp','obj').match(TargetTypeGroup('cpp',1))
        []

        >>> Generator('cpp','obj').match(TargetTypeGroup('cpp',12))
        []
        """
        if self in group.generators:
            return None
        
        for i in range(len(self.signature)):
            e = self.signature[i]
            if e[0] == group.target_type:
                if self.unary:
                    return []
                if e[1] > group.size or e[2] < group.size:
                    return None
                else:
                    return self.signature[:i] + self.signature[i+1:]
        return None

    def __str__(self):
        """Make a nice human-readable representation
        >>> g = Generator(['obj*', 'z', 'cpp'], ['lib','dll'])
        >>> print g
        lib,dll <- obj*,z,cpp
        """
        return ','.join(self.targets) + ' <- ' + ','.join(self.sources)

    def __type_list_rep(self, type_list):
        if len(type_list) == 1:
            return repr(type_list[0])
        else:
            return repr(type_list)
        
    def __repr__(self):
        return (
            self.__module__ + '.' + type(self).__name__ + '(' +
            self.__type_list_rep(self.sources)
            + ', ' + self.__type_list_rep(self.targets) + ')'
            )

def _dict_tuple(d):
    l = d.items()
    l.sort()
    return tuple(l)

def _sorted(list):
    list.sort()
    return list

class GeneratorSet(object):
    def __init__(self):
        self.all_generators = {}
        self.generators_by_type = {}
        
    def __iadd__(self, generator):
        """Add a generator to the set

        >>> s = GeneratorSet()
        >>> s += Generator('foo', 'bar')
        >>> s += Generator('foo', 'baz')
        >>> s += Generator(['foo','bar'], 'baz')
        >>> s += Generator('bar', ['baz', 'mumble'])
        >>> s += Generator('bar*', ['bing'])
        >>> print s
        {
          bar:
            baz <- foo,bar
            baz,mumble <- bar
            bing <- bar*
          foo:
            bar <- foo
            baz <- foo
            baz <- foo,bar
        }

        """
        if not generator in self.all_generators:
            self.all_generators[generator] = 1
            for t in generator.sources:
                if t.endswith('*'):
                    t = t[:-1]
                l = self[t]
                l.append(generator)
        return self

    def __isub__(self, generator):
        for t in generator.sources:
            if t.endswith('*'):
                t = t[:-1]
            self[t].remove(generator)
        return self
    
    def __getitem__(self, t):
        """Given a target type, return a list of all the generators
        which can consume that target type.
        """
        return self.generators_by_type.setdefault(t,[])

    def __str__(self):
        # import pprint
        # return pprint.pformat(self.generators_by_type)
    
        s = []
        
        for k,v in _sorted(self.generators_by_type.items()):
            s += [ '  ' + k + ':\n    ' + '\n    '.join([ str(x) for x in v ]) ]

        return '{\n' + '\n'.join(s) + '\n}'

def _dicts_intersect(d1, d2):
    """True iff d1 and d2 have a key in common

    >>> assert _dicts_intersect({1:0, 2:0}, {2:0})
    >>> assert _dicts_intersect({2:0}, {1:0, 2:0})
    >>> assert not _dicts_intersect({1:0, 3:0}, {2:0})
    >>> assert not _dicts_intersect({2:0}, {1:0, 3:0})
    """
    if len(d2) < len(d1):
        tmp = d1
        d1 = d2
        d2 = tmp
    for k in d1.iterkeys():
        if k in d2:
            return True
    return False
    
class TargetTypeGroup(object):
    instances = 0
    
    def __init__(
        self
        , target_type
        , size       # how many of that type are in the group.
        , parents = ()
        , generator = None):
        """
        >>> g1 = TargetTypeGroup('x', 1)
        >>> assert not g1.extra_targets
        >>> assert g1.consumed_sources == { g1:1 }
        >>> g2 = TargetTypeGroup('x', 1)
        
        >>> g3 = TargetTypeGroup('x', 1, [g1,g2])
        >>> assert g1 in g3.consumed_sources
        >>> assert g2 in g3.consumed_sources
        >>> assert not g3 in g3.consumed_sources
        """
        self.target_type = target_type
        self.size = size
        self.parents = parents
        self.generator = generator
        self.siblings = None
        self.id = TargetTypeGroup.instances
        self.ambiguous = reduce(lambda x,y: x or y.ambiguous and 1,
                                parents, None)

        self.generators = { generator : 1 } # it doesn't hurt to store None here
        ignored = [ self.generators.update(p.generators) for p in parents ]
        
        self.__constituents = None
        self.__extra_targets = None
        
        TargetTypeGroup.instances += 1

        if generator:
            self.moves = { (id(generator),id(parents)) : 1 }
        else:
            self.moves = {}
        
        if not parents:
            self.consumed_sources = {self:1}
            self.__extra_targets = ()
        else:
            ignored = [ self.moves.update(p.moves) for p in parents ]
            
            if len(parents) == 1:
                self.consumed_sources = parents[0].consumed_sources
            else:
                self.consumed_sources = {}
                for c in parents:
                    self.consumed_sources.update(c.consumed_sources)

    # constituents property - the set of all target groups consumed in
    # creating this group
    def __get_constituents(self):
        if self.__constituents is None:
            self.__constituents = {self:1}
            for c in self.parents:
                self.__constituents.update(c.constituents)
        return self.__constituents
            
    constituents = property(__get_constituents)

    cost = property(lambda self: len(self.moves))
    
    # extra targets property - in general, every target group sits at
    # the root of a DAG.  The extra targets are the ones produced by
    # generators that run in this DAG but which are not part of the
    # DAG, i.e. are not constituents.  In the example below, X and Y
    # are extra targets of A.
    #
    #           A   X       B,C <- D
    #          / \ /        C,Y <- E
    #         B   C   Y     A,X <- B,C
    #          \ / \ /      
    # Sources:  D   E
    #
    # We use the extra targets to determine the equivalence of two
    # search States
    def __get_extra_targets(self):
        if self.__extra_targets is None:
            
            if len(self.parents) == 1 and not self.siblings:
                self.__extra_targets = self.parents[0].extra_targets
            else:
                # all siblings are created incidentally
                if self.siblings:
                    t = tuple([s for s in self.siblings if s != self])
                else:
                    t = ()
                    
                # Any groups created incidentally as part of generating my
                # parents are also incidental to my generation
                for c in self.parents:
                    for i in c.extra_targets:
                        if i not in self.constituents:
                            t += (i,)

                self.__extra_targets = _sort_tuple(t)
        return self.__extra_targets

    extra_targets = property(__get_extra_targets)
    
    def set_siblings(self, sibs):
        assert self.__extra_targets is None, \
               "can't set siblings after extra targets already computed."

        assert self.parents, "original source nodes don't have siblings"
        self.siblings = sibs

    def __repr__(self):
        return '%s.%s(#%s$%s)' % (self.size,self.target_type,self.id,self.cost)
    
    def is_compatible_with(self, other):
        """True iff self and other can be used to trigger a generator.
        
        >>> g1 = TargetTypeGroup('x', 1)
        >>> g2 = TargetTypeGroup('x', 1)
        >>> assert g1.is_compatible_with(g2)
        
        >>> g3 = TargetTypeGroup('x', 1, [g1])
        >>> g4 = TargetTypeGroup('x', 1, [g2])
        >>> assert g3.is_compatible_with(g4)
        >>> assert g3.is_compatible_with(g2)
        >>> assert not g3.is_compatible_with(g1)
        >>> assert not g2.is_compatible_with(g4)

        >>> g5 = TargetTypeGroup('x', 1, [g3])
        >>> assert not g5.is_compatible_with(g1)
        """
        return not _dicts_intersect(
            self.constituents, other.constituents)

    def all_compatible(self, others):
        """True iff self is_compatible with every element of other
        """
        for o in others:
            if not self.is_compatible_with(o):
                return False
        return True

    def atoms(self):
        """If this group was formed by combining other groups without
        a generator, return a set of its nearest parent groups which
        were not formed that way.  Otherwise, return a set
        containing only this group.

        >>> g1 = TargetTypeGroup('x',1)
        >>> g2 = TargetTypeGroup('x',1)
        >>> a = TargetTypeGroup('x',2, [g1,g2]).atoms()
        >>> assert g1 in a and g2 in a and len(a) == 2
        """
        if self.generator or not self.parents:
            return (self,)
        x = ()
        for p in self.parents:
            x += p.atoms()
        return x

    
    def consumes(self, others):
        """True iff not self is_compatible with every element of other
        """
        for o in others:
            if self.is_compatible_with(o):