[Python-Dev] Re: [Python-checkins] python/dist/src/Pythoncompile.c, 2.343, 2.344

Raymond Hettinger python at rcn.com
Fri Feb 11 01:59:25 CET 2005

> > > Remove the set conversion which didn't work with:  [] in (0,)

> > Why is this a problem?  If there were *any* unhashable objects
> > in the container, then the compiler would have bailed on the
> > initial set-conversion.
> >>> [] in frozenset(["hi", "ho"])
> Traceback (most recent call last):
>   File "<stdin>", line 1, in ?
> TypeError: list objects are unhashable

> The compiler do bail out when there are unhashable objects outside the
> tuple, but not if the LHS is unhashable. I believe that is because
> internally frozenset uses a dict and it does something similar to
> d.has_key([]) in this case. It should be trivial for the compiler to
> also check the LHS for hashability I think.
> That is also why the email unit test failed - LHS was unhashable but
> the RHS was hashable. There is a patch for that (1119016) at SF but
> that may no longer be needed.

Right, that patch only fixes a symptom.  Also, the compiler cannot check
the hashability of the search key because it is likely not known at
compile time (i.e. x in (1,2,3) where x is a function argument).

For the time being, the set conversion concept was removed entirely.  To
go forward with it at some point, it will need a fast search type other
than frozenset, something like:

class FastSearchTuple(tuple):
    """Tuple lookalike that has O(1) search time if both the key and
     tuple elements are hashable; otherwise it reverts to an O(n) linear
     search. Used by compile.c for 'in' tests on tuples of constants.
    def __init__(self, data):
            self.dict = dict.fromkeys(data)
        except TypeError:
            self.dict = None

    def __contains__(self, key):
            return key in self.dict
        except TypeError:
            return tuple.__contains__(self, key)

Raymond Hettinger

More information about the Python-Dev mailing list