Re: cool generators insight

From: David Abrahams (gclbb-jamboost_at_[hidden])
Date: 2003-06-05 12:16:11

> David Abrahams <gclbb-jamboost_at_[hidden]> writes:
>
>> and solutions are possible... but they *are* ambiguous, as shown by
>> the output of my algorithm, which shows three solutions with cost 9:
>
> I take it back: my algorithm is failing to eliminate some identical
> states, and all those solutions are equivalent; let me fix that and it
> should run faster.

OK, I did that; It's still taking a very long time for your case,
though I do think your case is unrealistic. I think I can still find
quite a few equivalent states to eliminate, but I'm posting the
prototype here for reference.

 --=-=-= Content-Disposition: attachment; filename=g2.py

# 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

def _sequence_of_strings(s_or_l):
if isinstance(s_or_l, type('')):
return (s_or_l,)
else:
return s_or_l

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')
obj*,lib* -> exe

>>> 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))
[]
"""
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
obj*,z,cpp -> lib,dll
"""
return ','.join(self.sources) + ' -> ' + ','.join(self.targets)

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:
foo,bar -> baz
bar -> baz,mumble
bar* -> bing
foo:
foo -> bar
foo -> baz
foo,bar -> baz
}

"""
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):

self.target_type = target_type
self.size = size
self.parents = parents
self.generator = generator
self.cost = reduce(lambda x,y:x + y.cost, parents, 1)
self.siblings = []

self.id = TargetTypeGroup.instances
TargetTypeGroup.instances += 1

# reference loop, but we have gc
self.constituents = {self:1}
for c in parents:
self.constituents.update(c.constituents)

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 tuple of its nearest parent groups which
were not formed that way. Otherwise, return a tuple
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):
return False
return True

def _string_multiset(s):
x = {}
for t in _sequence_of_strings(s):
x[t] = x.get(t,0) + 1
return x

def parent_sets(chosen, signature, all_groups):
# print 'parent_sets(%s,%s,%s)'% (chosen,signature,all_groups)
if len(signature) == 0:
# The entire signature was satisfied; we can just yield the
# one result
yield chosen
else:
# find all ways to satisfy the next element of the signature
# which are compatible with the already-chosen groups. If
# there are no ways, we will fall off the end here and the
# ultimate result will be empty.
t, min, max = signature[0]
for g in all_groups[t]:

if (g.size >= min and g.size <= max and
g.all_compatible(chosen)): 

for s in parent_sets(
chosen + (g), signature[1:], all_groups
):
yield s

debug = None

def _sort_tuple(t):
l = list(t)
l.sort()
return tuple(l)

def search(target_type, source_types, generators):
# build the multiset of targets sought
all_groups = {}
generated_combinations = {}

q = [ TargetTypeGroup(i[0],i[1]) for i in
_string_multiset(source_types).items() ]

source_groups = tuple(q)

solution_cost = None
while q:
# remove a group from the queue
g = q[0]
del q[0]

if solution_cost is not None and g.cost > solution_cost:
return

global debug
if debug:
print '-------'
print dump(g)

if g.target_type == target_type and g.consumes(source_groups):
solution_cost = g.cost
yield g

# combine with all like groups which are compatible
for g2 in all_groups.get(g.target_type,()):

if g2.is_compatible_with(g):

leaves = _sort_tuple(g.atoms() + g2.atoms())

if leaves not in generated_combinations:
q.append(
TargetTypeGroup(
g.target_type, g2.size + g.size, parents = (g,g2)))
generated_combinations[leaves] = True

if debug:
print 'combined with', g2, 'to make', q[-1]
# else:
# print 'rejected %s + %s due to %s' % (g, new_group, leaves)
# sys.stdout.flush()

# expand with all generators which can be triggered as a
# result of adding this group
for generator in generators[g.target_type]:

match = generator.match(g)
if match is None:
continue

if debug:
print generator,' matched with ', match

# for all sets of parents which match the generator and
# include g
for s in parent_sets((g,), match, all_groups):
if debug:
print list(s), '->',
siblings = ()

for t,n in generator.targets_.items():
if (generator.unary):
n *= g.size
new_group = TargetTypeGroup(t, n, s, generator)
siblings += (new_group,)
q.append(new_group)

# Make sure groups know about their siblings
if len(siblings) > 1:
if debug:
print siblings
for product in siblings:
product.siblings = siblings
else:
if debug:
print new_group

# Add to the set of all groups so that we can combine it with
# others in future iterations
l = all_groups.get(g.target_type)
if l is None:
l = all_groups.setdefault(g.target_type,[])
l.append(g)

# Sort the queue; in 'real life' use a priority queue
q.sort(lambda g1,g2: g1.cost - g2.cost)

def dump(group, indent = 0, visited = None):
if (visited is None):
visited = {}
s = indent * ' '
s += repr(group)
if group in visited:
s += '...\n'
else:
visited[group] = True
s += '[%s]' % group.generator
if group.siblings:
s += ' siblings ' + str([sib for sib in group.siblings if
sib != group])
s += '\n' + '\n'.join(
[dump(g,indent+1,visited) for g in group.parents])
return s

def test():
# EST_EXE <- OBJ*
# OBJ <- CPP
# {CPP,STATIC_DATA} <- NM_ASM
# {CPP,CPP} <- ECPP (only first CPP must be further converted into NM_ASM)
# NM_ASM <- CPP
# {CPP,STATIC_DATA} <- STATIC_DATA*
# STATIC_DATA <- NM_ASM
# NM_OBJ <- NM_ASM
# NM_EXE <- NM_OBJ*
generators = GeneratorSet()
generators += Generator('OBJ*', 'EST_EXE')
generators += Generator('CPP', 'OBJ')
generators += Generator('NM_ASM', ('CPP', 'STATIC_DATA'))
generators += Generator('ECPP', ('CPP','CPP'))
generators += Generator('CPP', 'NM_ASM')
generators += Generator('STATIC_DATA*', ('CPP', 'STATIC_DATA'))
generators += Generator('NM_ASM', 'NM_OBJ')
generators += Generator('NM_OBJ*', 'NM_EXE')

import sys

TargetTypeGroup.instances = 0
for g in search('EST_EXE', ('CPP', 'NM_ASM', 'ECPP'), generators):
print 80 * '='
print dump(g)
print 80 * '='
sys.stdout.flush()

print '\n\n*****\n\n'

TargetTypeGroup.instances = 0
cost = None
for g in search('NM_EXE', ('CPP'), generators):
print 80 * '='
print dump(g)
print 80 * '='
sys.stdout.flush()

def run(args = None):
import doctest

if args is not None:
sys.argv = args
error = doctest.testmod(sys.modules.get(__name__))
if not error[0]:
test()
return error

if __name__ == '__main__':
import sys
sys.exit(run()[0])

 --=-=-= 

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com
 --=-=-=--