ASPN : Python Cookbook : Recursion/loop prevention function decorator

引数を監視して無限ループを検出するデコレータ。

状態を持つデコレータはこうすればきれいに書けるのか。
return decorate()でインスタンスを返す。こいつに__call__を実装しとけばデコレータ関数として呼ばれる。

__call__は、引数がすでに使われているかどうか、毎回インスタンス変数のリストを見てチェックしている。リストは前もって渡しておくことも可能。
チェックが通ればリストに引数を追加し、本体の処理をして終わったら削除。

@norec(0, -99, [])
def traverse(list):
    print "traversing %s" % str(list)
    return traverse(list[1])

p = [1]
c = [2, p]
p.append(c)
traverse(p)

を実行してみると、

traversing [1, [2, [...]]]
traversing [2, [1, [...]]]
recursion detected at '[1, [2, [...]]]' in 1, [2, [...], [2, [1, [...]]]]

で停止。
次はうまく行かない例。

@norec(0, -99, [])
def traverse(list):
    print "traversing %s" % str(list)
    return traverse(list[0])

p = []
c = [p]
p.append(c)
traverse(p)

これだとチェック自体がうまく動かない。

traverse [...]
Traceback (most recent call last):
File "norec.py", line 42, in ?
traverse(p)
File "norec.py", line 26, in new_f
x = f(*args, **kwds)
File "norec.py", line 36, in traverse
return traverse(list[0])
File "norec.py", line 21, in new_f
if id in self.cs:
RuntimeError: maximum recursion depth exceeded in cmp

リストに対するinとかremoveの効率はどうなのかあとで調べよう。