[Python-Dev] another dict crasher

Tim Peters tim.one@home.com
Tue, 5 Jun 2001 00:07:27 -0400

[Michael Hudson, taking a break from exams]
> I left it running overnight, and it terminated!  (with a KeyError).  I
> can't say I really understand what's going on, but I'm in Exam Hell at
> the moment (for the last time!  Yippee!), so don't have any spare
> cycles to think about it hard.

Good luck!  I really shouldn't tell you this now, but the real reason people
dread turning 30, 40, 50, 60-- and so on --is that every 10th birthday
starting at 30 they test you *again*!  On every course you ever took.  It's
grueling.  The penalty for failure is severe:  flunk just one review exam,
and they pick a date at random over the following 10 years for you to die.
No point fighting it, it's just civilization's nasty little secret.  This is
why life expectancy correlates with education, but it does appear that the
human limit for remembering both plane geometry and the names of hundreds of
dead psychopaths is about 120 years.

In the meantime, I built a test case to tickle stack overflow directly, and
it does so quickly:

class Yuck:
    def __init__(self):
        self.i = 0

    def make_dangerous(self):
        self.i = 1

    def __hash__(self):
        # direct to slot 4 in table of size 8; slot 12 when size 16
        return 4 + 8

    def __eq__(self, other):
        if self.i == 0:
            # leave dict alone
        elif self.i == 1:
            # fiddle to 16 slots
            self.i = 2
            # fiddle to 8 slots
            self.i = 1

        return 1

    def __fill_dict(self, n):
        self.i = 0
        for i in range(n):
            dict[i] = i
        dict[self] = "OK!"

y = Yuck()
dict = {y: "OK!"}

z = Yuck()
print dict[z]

It just arranges to move y to a different slot in a different-sized table
each time __eq__ is invoked, alternating between slot 4 in a size-8 table
and slot 12 in a size-16 table.

However, if I stick "print self.i" at the start of __eq__, it dies with a
KeyError instead!  That's why I'm mentioning it -- could be the same
misdirection you're seeing.  I can't account for the KeyError in any
rational way:  under Windows, it's actually hitting a stack overflow in the
bowels of the system malloc() then.  Windows "recovers" from that and
presses on.  Everything that happens after appears to be an accident.

win98-as-usual-ly y'rs  - tim

PS:  You'll be tested on this, too <wink>.