题目
Perform the secret knock() to enter…
链接
https://www.codewars.com/kata/secret-knock/train/python
题解
近期做过的一道非常好玩的题目!实际上这道题实在一年前就看过,但是当时CodeWars没有Test Driven Development (TDD) 这个模块,因此被挡在了反汇编那一步。
首先,在solution栏目写一个knock()函数调用,运行结果如下——
knock() #>>Sorry, that's not the secret knock.
那么,这道题要我们做的,就应该是用某种特殊的技巧调用knock()函数,使得Sorry, that’s not the secret knock. 输出不被触发。
在解题界面中的Test Driven Development (TDD) 有如下代码(由于习惯问题,我对于这些代码做了少量修改,使得其能运行在Python3.4.3环境下)——
def knock(): def opendoor(): print("Opened!\n") print("Opened, again!\n") lineCount=0 opendoor() import dis; print("\n<<FUNCTION: KNOCK()"); dis.dis(knock.__code__); print("\n<<FUNCTION: KNOCK>OPENDOOR()"); dis.dis(knock.__code__.co_consts[1]); print("\n<<FUNCTION: KNOCK>CONSTS"); for i,w in enumerate(knock.__code__.co_consts): print(i,w)
这一段代码实际上是解题方法的提示(想到一年前我没有这句话能想到尝试反汇编也已经不错了),这段代码使用 RUN SAMPLE TEST 按钮运行后,得到如下输出——
<<FUNCTION: KNOCK() 4 0 LOAD_CONST 1 (<code object opendoor at 0x7f3e3124a150, file "main.py", line 4>) 3 LOAD_CONST 2 ('knock.<locals>.opendoor') 6 MAKE_FUNCTION 0 9 STORE_FAST 0 (opendoor) 8 12 LOAD_CONST 3 (0) 15 STORE_FAST 1 (lineCount) 10 18 LOAD_FAST 0 (opendoor) 21 CALL_FUNCTION 0 (0 positional, 0 keyword pair) 24 POP_TOP 25 LOAD_CONST 0 (None) 28 RETURN_VALUE <<FUNCTION: KNOCK>OPENDOOR() 5 0 LOAD_GLOBAL 0 (print) 3 LOAD_CONST 1 ('Opened!\n') 6 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 9 POP_TOP 6 10 LOAD_GLOBAL 0 (print) 13 LOAD_CONST 2 ('Opened, again!\n') 16 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 19 POP_TOP 20 LOAD_CONST 0 (None) 23 RETURN_VALUE <<FUNCTION: KNOCK>CONSTS 0 None 1 <code object opendoor at 0x7f3e3124a150, file "main.py", line 4> 2 knock.<locals>.opendoor 3 0
代码中运用到了Python中的反汇编库dis,而使用dis作用到函数的代码储存模块knock.__code__ , 可以输出人类可读的反汇编代码。
为了更加清楚地了解knock.__code__的构造,我们可以使用Python的dir函数查看其具体的成员变量
print(dir(knock.__code__)) #>>['__class__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__le__', '__lt__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', 'co_argcount', 'co_cellvars', 'co_code', 'co_consts', 'co_filename', 'co_firstlineno', 'co_flags', 'co_freevars', 'co_kwonlyargcount', 'co_lnotab', 'co_name', 'co_names', 'co_nlocals', 'co_stacksize', 'co_varnames']
而我们可以在Python的安装目录(本机/anaconda3/envs/default/include/python3.6m)的code.h文件中,可以看到这些量的具体定义——
typedef struct { PyObject_HEAD int co_argcount; /* #arguments, except *args */ int co_kwonlyargcount; /* #keyword only arguments */ int co_nlocals; /* #local variables */ int co_stacksize; /* #entries needed for evaluation stack */ int co_flags; /* CO_..., see below */ int co_firstlineno; /* first source line number */ PyObject *co_code; /* instruction opcodes */ PyObject *co_consts; /* list (constants used) */ PyObject *co_names; /* list of strings (names used) */ PyObject *co_varnames; /* tuple of strings (local variable names) */ PyObject *co_freevars; /* tuple of strings (free variable names) */ PyObject *co_cellvars; /* tuple of strings (cell variable names) */ /* The rest aren't used in either hash or comparisons, except for co_name, used in both. This is done to preserve the name and line number for tracebacks and debuggers; otherwise, constant de-duplication would collapse identical functions/lambdas defined on different lines. */ unsigned char *co_cell2arg; /* Maps cell vars which are arguments. */ PyObject *co_filename; /* unicode (where it was loaded from) */ PyObject *co_name; /* unicode (name, for reference) */ PyObject *co_lnotab; /* string (encoding addr<->lineno mapping) See Objects/lnotab_notes.txt for details. */ void *co_zombieframe; /* for optimization only (see frameobject.c) */ PyObject *co_weakreflist; /* to support weakrefs to code objects */ /* Scratch space for extra data relating to the code object. Type is a void* to keep the format private in codeobject.c to force people to go through the proper APIs. */ void *co_extra; } PyCodeObject;
其中,co_const表示了函数中定义的常量,而co_code表示函数的代码。这时,我们就能明白 Test Driven Development (TDD) 中的代码究竟在干什么了——
- 输出了knock函数的反汇编码
- 输出了knock函数的常量定义
- 发现第一个常量是一个子函数OpenDoor,进而输出其反汇编代码
Test Driven Development (TDD) 中输出的代码是如下knock()函数的反汇编代码(实际上真实的knock()函数肯定会更加复杂)。
def knock(): def opendoor(): print("Opened!\n") lineCount=0 opendoor()
对照反汇编理解Python机器代码的规则——
<<FUNCTION: KNOCK() 4 0 LOAD_CONST 1 (<code object opendoor at 0x7f275adb7150, file "main.py", line 4>) 3 LOAD_CONST 2 ('knock.<locals>.opendoor') 6 MAKE_FUNCTION 0 9 STORE_FAST 0 (opendoor) 7 12 LOAD_CONST 3 (0) 15 STORE_FAST 1 (lineCount) 9 18 LOAD_FAST 0 (opendoor) 21 CALL_FUNCTION 0 (0 positional, 0 keyword pair) 24 POP_TOP 25 LOAD_CONST 0 (None) 28 RETURN_VALUE <<FUNCTION: KNOCK>OPENDOOR() 5 0 LOAD_GLOBAL 0 (print) 3 LOAD_CONST 1 ('Opened!\n') 6 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 9 POP_TOP 10 LOAD_CONST 0 (None) 13 RETURN_VALUE <<FUNCTION: KNOCK>CONSTS (None, <code object opendoor at 0x7f275adb7150, file "main.py", line 4>, 'knock.<locals>.opendoor', 0)
基本上就很容易理解了,唯一可能有点晕的是POP_TOP指令,出现在所有函数调用之后,个人猜测适用于处理函数返回值,只是本题中所有返回值POP出来都没有使用而已。
了解了Python机器代码的规则,我们就可以看真正的knock函数怎么写的了:一下输出源代码程序都是基于如下程序改动的,之后就不会再放了
import dis; print("\n<<FUNCTION: KNOCK()"); dis.dis(knock.__code__); print("\n<<FUNCTION: KNOCK>OPENDOOR()"); dis.dis(knock.__code__.co_consts[1]); print("\n<<FUNCTION: KNOCK>LineCount()"); dis.dis(knock.__code__.co_consts[3]); print("\n<<FUNCTION: KNOCK>deliverLine()"); dis.dis(knock.__code__.co_consts[5]); print("\n<<FUNCTION: KNOCK>CONSTS"); for i,w in enumerate(knock.__code__.co_consts): print(i,w)
整体输出由于太长,放在了文章末尾。不过注意的是,这一次,不只有Opendoor是子函数,还有一个LineCount()和deliverLine()子函数。
knock函数反汇编的结果中,首先注意到有如下几行
27 48 LOAD_FAST 0 (arg) 51 LOAD_GLOBAL 0 (knock) 54 COMPARE_OP 2 (==) 57 POP_JUMP_IF_FALSE 84 28 60 LOAD_GLOBAL 1 (print) 63 LOAD_CONST 7 ('"Knock knock."') 66 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 69 POP_TOP 29 70 LOAD_GLOBAL 1 (print) 73 LOAD_CONST 8 ("Who's there?") 76 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 79 POP_TOP 30 80 LOAD_DEREF 0 (deliverLine) 83 RETURN_VALUE >> 84 LOAD_CONST 0 (None) 87 RETURN_VALUE
其中,将arg和全局变量knock进行了比较,WTF,全局变量knock不是函数自身吗?那是不是我们应该调用knock(knock)?
knock(knock) #>>"Knock knock." #>>Who's there?
程序的输出确实变了!但是我们没有利用到其他任何的子程序啊!仔细重读Knock()函数,两次CALL_FUNCTION操作都制定了调用系统print函数,因此除非修改print函数,否则玩不出什么奇怪的花样。那么另外两个函数是怎么被调用的呢?
我尝试去搞懂Knock函数里面唯一一个自己无法理解的指令STORE_DEREF,在StackOverFlow相关问题的引导下,豁然开朗!看下面的程序
def outer(): var = 1 def inner(): return var return inner
其反汇编代码如下,恰好用到了STORE_DEREF,而上面这个程序的结构,恰好就和knock函数相似,其返回值是一个可调用的程序!
4 0 LOAD_CONST 1 (1) 3 STORE_DEREF 0 (var) 6 6 LOAD_CLOSURE 0 (var) 9 BUILD_TUPLE 1 12 LOAD_CONST 2 (<code object inner at 0x7ff8a7f49150, file "main.py", line 6>) 15 LOAD_CONST 3 ('outer.<locals>.inner') 18 MAKE_CLOSURE 0 21 STORE_FAST 0 (inner) 9 24 LOAD_FAST 0 (inner) 27 RETURN_VALUE
knock(knock)返回了一个deliverLine函数闭包,而deliverLine函数定义如下
<<FUNCTION: KNOCK>deliverLine() 24 0 LOAD_DEREF 1 (lineCount) 3 CALL_FUNCTION 0 (0 positional, 0 keyword pair) 6 LOAD_CONST 1 (2) 9 COMPARE_OP 2 (==) 12 POP_JUMP_IF_FALSE 25 15 LOAD_DEREF 2 (openDoor) 18 CALL_FUNCTION 0 (0 positional, 0 keyword pair) 21 POP_TOP 22 JUMP_FORWARD 0 (to 25) 25 >> 25 LOAD_DEREF 0 (deliverLine) 28 RETURN_VALUE
这个函数最后返回了自身的一个闭包,也就是说返回值又是可调用的。
每一次调用,函数调用都会增加一个变量varLineCount的值,当变量的值分别为1和2时,输出不同的内容,当变量的值为2时,门被打开了。
<<FUNCTION: KNOCK>LineCount() 15 0 LOAD_GLOBAL 0 (lineCountVar) 3 LOAD_CONST 1 (1) 6 INPLACE_ADD 7 STORE_GLOBAL 0 (lineCountVar) 16 10 LOAD_GLOBAL 0 (lineCountVar) 13 LOAD_CONST 1 (1) 16 COMPARE_OP 2 (==) 19 POP_JUMP_IF_FALSE 45 17 22 LOAD_GLOBAL 1 (print) 25 LOAD_CONST 2 ('"Harry."') 28 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 31 POP_TOP 18 32 LOAD_GLOBAL 1 (print) 35 LOAD_CONST 3 ('Harry who?') 38 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 41 POP_TOP 42 JUMP_FORWARD 25 (to 70) 19 >> 45 LOAD_GLOBAL 0 (lineCountVar) 48 LOAD_CONST 4 (2) 51 COMPARE_OP 2 (==) 54 POP_JUMP_IF_FALSE 70 20 57 LOAD_GLOBAL 1 (print) 60 LOAD_CONST 5 ('"Harry up and open the door, it\'s cold out here!"') 63 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 66 POP_TOP 67 JUMP_FORWARD 0 (to 70) 21 >> 70 LOAD_GLOBAL 0 (lineCountVar) 73 RETURN_VALUE
最终答案应该是
knock(knock)()()
顺便说一句,Python版本现在有一些问题,提交了会显示错误,将该答案输出到JavaScript版本的题目中即可。
完整反汇编代码
<<FUNCTION: KNOCK() 5 0 LOAD_CONST 1 (<code object openDoor at 0x7fb0b3296300, file "/home/codewarrior/setup.py", line 5>) 3 LOAD_CONST 2 ('knock.<locals>.openDoor') 6 MAKE_FUNCTION 0 9 STORE_DEREF 2 (openDoor) 13 12 LOAD_CONST 3 (<code object lineCount at 0x7fb0b3296390, file "/home/codewarrior/setup.py", line 13>) 15 LOAD_CONST 4 ('knock.<locals>.lineCount') 18 MAKE_FUNCTION 0 21 STORE_DEREF 1 (lineCount) 23 24 LOAD_CLOSURE 0 (deliverLine) 27 LOAD_CLOSURE 1 (lineCount) 30 LOAD_CLOSURE 2 (openDoor) 33 BUILD_TUPLE 3 36 LOAD_CONST 5 (<code object deliverLine at 0x7fb0b3296420, file "/home/codewarrior/setup.py", line 23>) 39 LOAD_CONST 6 ('knock.<locals>.deliverLine') 42 MAKE_CLOSURE 0 45 STORE_DEREF 0 (deliverLine) 27 48 LOAD_FAST 0 (arg) 51 LOAD_GLOBAL 0 (knock) 54 COMPARE_OP 2 (==) 57 POP_JUMP_IF_FALSE 84 28 60 LOAD_GLOBAL 1 (print) 63 LOAD_CONST 7 ('"Knock knock."') 66 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 69 POP_TOP 29 70 LOAD_GLOBAL 1 (print) 73 LOAD_CONST 8 ("Who's there?") 76 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 79 POP_TOP 30 80 LOAD_DEREF 0 (deliverLine) 83 RETURN_VALUE >> 84 LOAD_CONST 0 (None) 87 RETURN_VALUE <<FUNCTION: KNOCK>OPENDOOR() 7 0 LOAD_CONST 1 ('') 3 LOAD_ATTR 0 (join) 6 LOAD_CONST 2 (<code object <genexpr> at 0x7fb0b3296270, file "/home/codewarrior/setup.py", line 7>) 9 LOAD_CONST 3 ('knock.<locals>.openDoor.<locals>.<genexpr>') 12 MAKE_FUNCTION 0 15 LOAD_GLOBAL 1 (range) 18 LOAD_CONST 4 (16) 21 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 24 GET_ITER 25 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 28 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 31 STORE_GLOBAL 2 (success) 8 34 LOAD_CONST 5 (True) 37 LOAD_GLOBAL 3 (globals) 40 CALL_FUNCTION 0 (0 positional, 0 keyword pair) 43 LOAD_GLOBAL 2 (success) 46 STORE_SUBSCR 9 47 LOAD_GLOBAL 4 (print) 50 LOAD_CONST 1 ('') 53 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 56 POP_TOP 10 57 LOAD_GLOBAL 4 (print) 60 LOAD_CONST 6 ('Groan. That\'s the worst "knock knock" joke I\'ve ever heard.') 63 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 66 POP_TOP 11 67 LOAD_GLOBAL 4 (print) 70 LOAD_CONST 7 ("Oh well, I suppose you'd better come in.") 73 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 76 POP_TOP 12 77 LOAD_GLOBAL 4 (print) 80 LOAD_CONST 8 ('Welcome to the annual meeting of the Knock Knock Joke Society.') 83 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 86 POP_TOP 87 LOAD_CONST 0 (None) 90 RETURN_VALUE <<FUNCTION: KNOCK>LineCount() 15 0 LOAD_GLOBAL 0 (lineCountVar) 3 LOAD_CONST 1 (1) 6 INPLACE_ADD 7 STORE_GLOBAL 0 (lineCountVar) 16 10 LOAD_GLOBAL 0 (lineCountVar) 13 LOAD_CONST 1 (1) 16 COMPARE_OP 2 (==) 19 POP_JUMP_IF_FALSE 45 17 22 LOAD_GLOBAL 1 (print) 25 LOAD_CONST 2 ('"Harry."') 28 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 31 POP_TOP 18 32 LOAD_GLOBAL 1 (print) 35 LOAD_CONST 3 ('Harry who?') 38 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 41 POP_TOP 42 JUMP_FORWARD 25 (to 70) 19 >> 45 LOAD_GLOBAL 0 (lineCountVar) 48 LOAD_CONST 4 (2) 51 COMPARE_OP 2 (==) 54 POP_JUMP_IF_FALSE 70 20 57 LOAD_GLOBAL 1 (print) 60 LOAD_CONST 5 ('"Harry up and open the door, it\'s cold out here!"') 63 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 66 POP_TOP 67 JUMP_FORWARD 0 (to 70) 21 >> 70 LOAD_GLOBAL 0 (lineCountVar) 73 RETURN_VALUE <<FUNCTION: KNOCK>deliverLine() 24 0 LOAD_DEREF 1 (lineCount) 3 CALL_FUNCTION 0 (0 positional, 0 keyword pair) 6 LOAD_CONST 1 (2) 9 COMPARE_OP 2 (==) 12 POP_JUMP_IF_FALSE 25 15 LOAD_DEREF 2 (openDoor) 18 CALL_FUNCTION 0 (0 positional, 0 keyword pair) 21 POP_TOP 22 JUMP_FORWARD 0 (to 25) 25 >> 25 LOAD_DEREF 0 (deliverLine) 28 RETURN_VALUE <<FUNCTION: KNOCK>CONSTS 0 None 1 <code object openDoor at 0x7fb0b3296300, file "/home/codewarrior/setup.py", line 5> 2 knock.<locals>.openDoor 3 <code object lineCount at 0x7fb0b3296390, file "/home/codewarrior/setup.py", line 13> 4 knock.<locals>.lineCount 5 <code object deliverLine at 0x7fb0b3296420, file "/home/codewarrior/setup.py", line 23> 6 knock.<locals>.deliverLine 7 "Knock knock." 8 Who's there?