4 # Make the environment more like Python 3.0
6 from itertools import izip as zip
22 Dynamically overloaded functions.
24 This is an implementation of (dynamically, or run-time) overloaded
25 functions; also known as generic functions or multi-methods.
27 The dispatch algorithm uses the types of all argument for dispatch,
28 similar to (compile-time) overloaded functions or methods in C++ and
31 Most of the complexity in the algorithm comes from the need to support
32 subclasses in call signatures. For example, if an function is
33 registered for a signature (T1, T2), then a call with a signature (S1,
34 S2) is acceptable, assuming that S1 is a subclass of T1, S2 a subclass
35 of T2, and there are no other more specific matches (see below).
37 If there are multiple matches and one of those doesn't *dominate* all
38 others, the match is deemed ambiguous and an exception is raised. A
39 subtlety here: if, after removing the dominated matches, there are
40 still multiple matches left, but they all map to the same function,
41 then the match is not deemed ambiguous and that function is used.
42 Read the method find_func() below for details.
44 @note Python 2.5 is required due to the use of predicates any() and all().
45 @note only supports positional arguments
47 @author http://www.artima.com/weblogs/viewpost.jsp?thread=155514
50 >>> misc.validate_decorator (overloaded)
56 >>> #Basics, with reusing names and without
62 >>> @foo.register(int)
64 ... "prints the hex representation of x"
67 >>> from types import DictType
68 >>> @foo.register(DictType)
70 ... "prints the keys of x"
71 ... print [k for k in x.iterkeys()]
73 >>> #combines all of the doc strings to help keep track of the specializations
74 >>> foo.__doc__ # doctest: +ELLIPSIS
75 "prints x\\n\\n...overloading.foo (<type 'int'>):\\n\\tprints the hex representation of x\\n\\n...overloading.foo_dict (<type 'dict'>):\\n\\tprints the keys of x"
78 >>> foo (10) #calling the specialized foo
80 >>> foo ({3:5, 6:7}) #calling the specialization foo_dict
82 >>> foo_dict ({3:5, 6:7}) #with using a unique name, you still have the option of calling the function directly
89 >>> #Multiple arguments, accessing the default, and function finding
91 ... def two_arg (x, y):
94 >>> @two_arg.register(int, int)
95 ... def two_arg_int_int (x, y):
96 ... print hex(x), hex(y)
98 >>> @two_arg.register(float, int)
99 ... def two_arg_float_int (x, y):
102 >>> @two_arg.register(int, float)
103 ... def two_arg_int_float (x, y):
106 >>> two_arg.__doc__ # doctest: +ELLIPSIS
107 "...overloading.two_arg_int_int (<type 'int'>, <type 'int'>):\\n\\n...overloading.two_arg_float_int (<type 'float'>, <type 'int'>):\\n\\n...overloading.two_arg_int_float (<type 'int'>, <type 'float'>):"
112 >>> two_arg(15, 16.0)
114 >>> two_arg.default_func(9, 10)
116 >>> two_arg.find_func ((int, float)) == two_arg_int_float
118 >>> (int, float) in two_arg
120 >>> (str, int) in two_arg
125 >>> #################
127 >>> @two_arg.register(AnyType, str)
128 ... def two_arg_any_str (x, y):
129 ... print x, y.lower()
131 >>> two_arg("Hello", "World")
133 >>> two_arg(500, "World")
137 def __init__(self, default_func):
138 # Decorator to declare new overloaded function.
141 self.default_func = default_func
142 self.__name__ = self.default_func.__name__
143 self.__doc__ = self.default_func.__doc__
144 self.__dict__.update (self.default_func.__dict__)
146 def __get__(self, obj, type=None):
149 return new.instancemethod(self, obj)
151 def register(self, *types):
153 Decorator to register an implementation for a specific set of types.
155 .register(t1, t2)(f) is equivalent to .register_func((t1, t2), f).
159 self.register_func(types, func)
161 originalDoc = self.__doc__ if self.__doc__ is not None else ""
162 typeNames = ", ".join ([str(type) for type in types])
163 typeNames = "".join ([func.__module__+".", func.__name__, " (", typeNames, "):"])
165 if func.__doc__ is not None:
166 overloadedDoc = textwrap.fill (func.__doc__, width=60, initial_indent="\t", subsequent_indent="\t")
167 self.__doc__ = "\n".join ([originalDoc, "", typeNames, overloadedDoc]).strip()
171 #Masking the function, so we want to take on its traits
172 if func.__name__ == self.__name__:
173 self.__dict__.update (func.__dict__)
179 def register_func(self, types, func):
180 """Helper to register an implementation."""
181 self.registry[tuple(types)] = func
182 self.cache = {} # Clear the cache (later we can optimize this).
184 def __call__(self, *args):
185 """Call the overloaded function."""
186 types = tuple(map(type, args))
187 func = self.cache.get(types)
189 self.cache[types] = func = self.find_func(types)
192 def __contains__ (self, types):
193 return self.find_func(types) is not self.default_func
195 def find_func(self, types):
196 """Find the appropriate overloaded function; don't call it.
198 @note This won't work for old-style classes or classes without __mro__
200 func = self.registry.get(types)
202 # Easy case -- direct hit in registry.
205 # Phillip Eby suggests to use issubclass() instead of __mro__.
206 # There are advantages and disadvantages.
208 # I can't help myself -- this is going to be intense functional code.
209 # Find all possible candidate signatures.
210 mros = tuple(inspect.getmro(t) for t in types)
212 candidates = [sig for sig in self.registry
214 all(t in mro for t, mro in zip(sig, mros))]
217 # No match at all -- use the default function.
218 return self.default_func
219 elif len(candidates) == 1:
220 # Unique match -- that's an easy case.
221 return self.registry[candidates[0]]
223 # More than one match -- weed out the subordinate ones.
225 def dominates(dom, sub,
226 orders=tuple(dict((t, i) for i, t in enumerate(mro))
228 # Predicate to decide whether dom strictly dominates sub.
229 # Strict domination is defined as domination without equality.
230 # The arguments dom and sub are type tuples of equal length.
231 # The orders argument is a precomputed auxiliary data structure
232 # giving dicts of ordering information corresponding to the
233 # positions in the type tuples.
234 # A type d dominates a type s iff order[d] <= order[s].
235 # A type tuple (d1, d2, ...) dominates a type tuple of equal length
236 # (s1, s2, ...) iff d1 dominates s1, d2 dominates s2, etc.
239 return all(order[d] <= order[s] for d, s, order in zip(dom, sub, orders))
241 # I suppose I could inline dominates() but it wouldn't get any clearer.
243 for cand in candidates
244 if not any(dominates(dom, cand) for dom in candidates)]
245 if len(candidates) == 1:
246 # There's exactly one candidate left.
247 return self.registry[candidates[0]]
249 # Perhaps these multiple candidates all have the same implementation?
250 funcs = set(self.registry[cand] for cand in candidates)
254 # No, the situation is irreducibly ambiguous.
255 raise TypeError("ambigous call; types=%r; candidates=%r" %