题目
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?