By

第一次遇到JJEncode, 代码与如下类似，一堆的奇奇怪怪的字符，特征是结尾有两个括号

1
$=~[];$={___:++$,$$$$:(![]+"")[$],__$:++$,$_$_:(![]+"")[$],_$_:++$,$_$$:({}+"")[$],$$_$:($[$]+"")[$],_$$:++$,$$$_:(!""+"")[$],$__:++$,$_$:++$,$$__:({}+"")[$],$$_:++$,$$$:++$,$___:++$,$__$:++$};$.$_=($.$_=$+"")[$.$_$]+($._$=$.$_[$.__$])+($.$$=($.$+"")[$.__$])+((!$)+"")[$._$$]+($.__=$.$_[$.$$_])+($.$=(!""+"")[$.__$])+($._=(!""+"")[$._$_])+$.$_[$.$_$]+$.__+$._$+$.$;$.$$=$.$+(!""+"")[$._$$]+$.__+$._+$.$+$.$$;$.$=($.___)[$.$_][$.$_];$.$($.$($.$$+"\""+$.$_$_+(![]+"")[$._$_]+$.$$$_+"\\"+$.__$+$.$$_+$._$_+$.__+"(\\\"\\"+$.__$+$.__$+$.___+$.$$$_+(![]+"")[$._$_]+(![]+"")[$._$_]+$._$+",\\"+$.$__+$.___+"\\"+$.__$+$.__$+$._$_+$.$_$_+"\\"+$.__$+$.$$_+$.$$_+$.$_$_+"\\"+$.__$+$._$_+$._$$+$.$$__+"\\"+$.__$+$.$$_+$._$_+"\\"+$.__$+$.$_$+$.__$+"\\"+$.__$+$.$$_+$.___+$.__+"\\\"\\"+$.$__+$.___+");\\"+$.__$+$._$_+"\\"+$.__$+$.__$+"\\"+$.__$+$.__$+"\\"+$.__$+$.__$+"\"")())();

结果我想的复杂了，想着用AST去解决，实际上非常简单，只需要把代码放在浏览器console里，把最后的括号去掉，就能还原代码，上述代码可以得到如下代码

1
2
3
4
5
(function anonymous(
) {
	alert("Hello, JavaScript" );
			
})

与JJEncode类似的还有AAEncode, JSFuck，这里就不一一列举了

联系作者

By

有段时间，对APP逆向热情高涨，尝试了多个APP的逆向，对APP逆向有了大致的了解。和Web逆向一样，首先得抓包，不同的是，APP抓包难度更大一些。有一些APP抓包容易，有一些APP抓包难。

对于简单的APP，用一些抓包软件，设置下HTTPS代理即可。可以直接在手机上进行抓包，也可以在电脑上进行抓包。

在手机端抓包比较容易，直接安装抓包APP就行，如iOS系统中的Stream, Android系统中HttpCanary都是很好的手机端抓包软件。

在电脑端抓包需要设置的更多一些，但设置好之后，更容易找到对应的接口，因为你在APP中操作的时候，请求包也同时发出，同时电脑端的抓包软件功能也更强大一些，便于查找。电脑端可以使用Fiddler，Charles等抓包软件，需要将手机和电脑在同一个网络中，并在手机上设置代理，将请求代理到电脑上，并在手机上安装抓包软件的证书。设置好之后即可进行抓包。

有一些复杂的APP，用上面的抓包软件抓不到包，有一些是因为APP里忽略代理，有一些是因为APP设置了证书双向认证，要解决这些问题，要使用其它的方法，目前在学习中。

联系作者

By

想在Node环境中实现浏览器的操作，寻寻觅觅，最终找到了jsdom。

试用了jsdom后，发现是真的方便，实现了绝大多数的浏览器操作，几乎可以当作浏览器来使用。这就是刚来搞逆向时，那时还停留在扣代码的阶段，就想要一个Node库来帮助我模拟出浏览器环境，如浏览器指纹，鼠标键盘事件和滑动轨迹等等。虽然现在还不知道用jsdom怎么添加鼠标键盘事件，但对于大多数网站已经足够用。

熟悉使用后，可以用于大多数网站，省去了很多时间。对于不会自己补环境的逆向工程师，真是省心又省力，值得一学。

联系作者

By

前些天在看David Beazley的Python3 metaprogramming视频，觉得是时候总结下视频中学到的内容, 这篇文章主要是这个视频的笔记，以及关于metaclass的一些思考.

装饰器

首先看一个需求，就是想在函数被调用时，记录一下，可以简单的加个print

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def add(x, y):
    print('add')
    return x + y

def sub(x, y):
    print('sub')
    return x - y

def mul(x, y):
    print('mul')
    return x * y

def div(x, y):
    print('div')
    return x / y

print(add(3, 5))
print(sub(5, 2))

输出
add
8
sub
3

但是这样的话, print语句就重复了, 每个函数里都得加print, 于是我们可以使用装饰器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 一个简单的装饰器
def debug(func):
    def wrapper(*args, **kwargs):
        print(func.__name__)
        return func(*args, **kwargs)
    return wrapper

@debug
def add(x, y):
    return x + y

@debug
def sub(x, y):
    return x - y

@debug
def mul(x, y):
    return x * y

@debug
def div(x, y):
    return x / y

print(add(3, 5))
print(sub(5, 2))

输出
add
8
sub
3

使用functools

但是这个简单的装饰器是存在问题的，它会忽略被装饰的函数

1
2
3
4
print(add)

输出
<function debug.<locals>.wrapper at 0x1037a6bf8>

这里add函数经过debug装饰器装饰后，函数名都被忽略了，这个时候functools模块就派上用场了, 里面的wraps装饰器就是用来解决这个问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from functools import wraps

def debug(func):
    msg = func.__qualname__
    @wraps(func)
    def wrapper(*args, **kwargs):
        print(msg)
        return func(*args, **kwargs)
    return wrapper
    
@debug
def add(x, y):
    return x + y

@debug
def sub(x, y):
    return x - y

@debug
def mul(x, y):
    return x * y

@debug
def div(x, y):
    return x / y

print(add(3, 5))
print(sub(5, 2))

输出
add
8
sub
3

print(add)
输出
<function add at 0x1037afa60>

带参数的装饰器

有时候装饰器里想传入一些参数, 这时就可以写带参数的装饰器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# decorators with args
from functools import wraps

def debug(prefix=''):
    def decroate(func):
        msg = prefix + func.__qualname__
        @wraps(func)
        def wrapper(*args, **kwargs):
            print(msg)
            return func(*args, **kwargs)
        return wrapper
    return decroate

@debug('###')
def add(x, y):
    return x + y

print(add(3, 2))
输出
###add
5

这种带参数的装饰器有一个头疼的问题是, 使用装饰器时, 如果不想传参数, 也得加上括号, 不然会报错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@debug
def sub(x, y):
    return x - y

sub(5, 3)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-40-9a93be17056c> in <module>
      3     return x - y
      4 
----> 5 sub(5, 3)

TypeError: decroate() takes 1 positional argument but 2 were given

加上括号后, 就不报错, 这很丑陋

1
2
3
4
5
@debug()
def sub(x, y):
    return x - y

print(sub(5, 3))

这里有一个小技巧, 实现如下

1
2
3
4
5
6
7
8
9
10
11
from functools import wraps, partial

def debug(func=None, prefix=''):
    if func is None:
        return partial(debug, prefix=prefix)
    msg = prefix + func.__qualname__
    @wraps(func)
    def wrapper(*args, **kwargs):     
        print(msg)
        return func(*args, **kwargs)
    return wrapper

如此, 当使用默认参数时, 即便不带括号时，也不会报错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
@debug(prefix='###')
def add(x, y):
    return x + y


@debug
def sub(x, y):
    return x - y

print(add(3, 2))
print(sub(5, 3))
输出
###add
5
sub
2

类装饰器

以下我们定义一个Spam类,

1
2
3
4
5
6
7
8
9
10
11
class Spam:
    def a(self):
        pass
    def b(self):
        pass
    @classmethod
    def c(cls):
        pass
    @staticmethod
    def d():
        pass

然后我们想在类的方法被调用时, 能够记录下, 想上面的函数被调用时一样, 这时我们就会可以编写一个类装饰器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def debugmethods(cls):
    # cls is class
    for key, val in vars(cls).items():
        if callable(val):
            setattr(cls, key, debug(val))
    return cls

@debugmethods
class Spam:
    def a(self):
        pass
    def b(self):
        pass
    @classmethod
    def c(cls):
        pass
    @staticmethod
    def d():
        pass

spam = Spam()
spam.a()
spam.b()
spam.c()
spam.d()
输出
Spam.a
Spam.b

这里只打印了a和b, 没有打印c和d, 这什么原因呢? 这是因为classmethod和staticmethod都是descriptor, 也就是描述器, 它们没有实现__call__方法，也就不是callable的

我们也可以编写一个类装饰器, 当获取一个属性时, 打印日志

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# debug access
def debugattr(cls):
    orig_getattribute = cls.__getattribute__
    def __getattribute__(self, name):
        print('Get:', name)
        return orig_getattribute(self, name)
    cls.__getattribute__ = __getattribute__
    return cls

@debugattr
class Spam:
    def __init__(self, x, y):
        self.x = x
        self.y = y

spam = Spam(2, 3)
print(spam.x)
输出
Get: x
2

metaclass

现在我们想对所有的类都能打印日志，一个解决的办法是在所有的类前面都加上类装饰器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@debugmethods
class Base:
    def a(self):
        pass
    def b(self):
        pass
    
@debugmethods
class Spam(Base):
    def a(self):
        pass
b = Base()
b.a()
s = Spam()
s.a()
输出
Base.a
Spam.a

但这样很麻烦，于是metaclass派上用场了, metaclass最强的地方是可以控制类的创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# a metaclass
class debugmeta(type):
    def __new__(cls, clsname, bases, clsdict):
        clsobj = super().__new__(cls, clsname, bases, clsdict)
#         print("here", cls, clsname, type(clsobj), clsobj)
        clsobj = debugmethods(clsobj)
#         print(vars(clsobj))
        return clsobj

class Base(metaclass=debugmeta):
    def a(self):
        pass
    def b(self):
        pass

    
class Spam(Base):
    def __init__(self, name):
        self.name = name
        
    def a(self):
        pass
    
b = Base()
b.a()
s = Spam('name')
s.a()

输出
Base.a
Spam.__init__
Spam.a

从上面的例子中我们看到，有一个类有metaclass, 它的所有子类都有metaclass, 这说明metaclass是会被继承的。结合蔡元楠的《metaclass, 是潘多拉魔盒还是阿拉丁神灯》, 可以知道，这里debugmeta其实不只一种写法，在__init__函数里实现也是可以的。重载__init__的实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# a metaclass
class debugmeta(type):
     def __init__(cls, name, bases, kwds):
        super(debugmeta, cls).__init__(name, bases, kwds)
        cls = debugmethods(cls)

class Base(metaclass=debugmeta):
    def a(self):
        pass
    def b(self):
        pass

    
class Spam(Base):
    def __init__(self, name):
        self.name = name
        
    def a(self):
        pass
b = Base()
b.a()
s = Spam('lala')
s.a()
输出
Base.a
Spam.__init__
Spam.a

这是因为, 所有的类都是type的实例, 都是对type的__call__方法进行重载, 而type的__call__方法会调用type.__new__(typeclass, classname, superclasses, attributedict)和type.__init__(class, classname, superclasses, attributedict), 所以上面重写__new__和重写__init__都是可以的。

学到这里，我脑海里冒出了一个想法，就是为啥这里一定要用metaclass呢? 用继承的方式难道不行吗？于是自己尝试写了个继承的方式, 发现也是跑得通的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# a baseclass
class debugmeta:
    def __new__(cls, *args, **kwargs):
        cls = debugmethods(cls)
        clsobj = object.__new__(cls)
#         clsobj = debugmethods(clsobj)
#         print('aaa', type(clsobj), clsobj)
#         print('aaa', clsobj, type(clsobj), vars(clsobj), dir(clsobj), type(clsobj.a), callable(clsobj.a))
        return clsobj
    
class Base(debugmeta):
    def a(self):
        pass

    
class Spam(Base):
    def __init__(self, name):
        self.name = name
    def a(self):
        pass

    
b = Base()
b.a()
s = Spam('name')
s.a()
输出
Base.a
Spam.__init__
Spam.a

但实际上，这样做法是有问题的，后面等到后面我们来纠正这个问题。

既然如此，那么蔡元楠在《metaclass, 是潘多拉魔盒还是阿拉丁神灯》介绍的yaml的动态序列化和逆序列化的能力又为何要用metaclass实现呢？用继承难道不行吗？于是也写了一个继承的版本, 代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import yaml


class MyYAMLObjectBaseclass(object):
    """
    The metaclass for YAMLObject.
    """
    def __new__(cls, *args, **kwargs):
        if cls.yaml_tag:
            cls.yaml_loader.add_constructor(cls.yaml_tag, cls.from_yaml)
            cls.yaml_dumper.add_representer(cls, cls.to_yaml)
        return object.__new__(cls)

class MyYAMLObject(MyYAMLObjectBaseclass):
    """
    An object that can dump itself to a YAML stream
    and load itself from a YAML stream.
    """

    __slots__ = ()  # no direct instantiation, so allow immutable subclasses

    yaml_loader = yaml.Loader
    yaml_dumper = yaml.Dumper

    yaml_tag = None
    yaml_flow_style = None

    @classmethod
    def from_yaml(cls, loader, node):
        """
        Convert a representation node to a Python object.
        """
        return loader.construct_yaml_object(node, cls)

    @classmethod
    def to_yaml(cls, dumper, data):
        """
        Convert a Python object to a representation node.
        """
        return dumper.represent_yaml_object(cls.yaml_tag, data, cls,
                flow_style=cls.yaml_flow_style)


class Monster(MyYAMLObject):
    yaml_tag = '!Monster'

    def __init__(self, name, hp, ac, attacks):
        self.name = name
        self.hp = hp
        self.ac = ac
        self.attacks = attacks

    def __repr__(self):
        return "{}(name={}, hp={}, ac={}, attacks={}".format(self.__class__.__name__, self.name, self.hp,
                                                             self.ac, self.attacks)


class Dragon(Monster):
    yaml_tag = '!Dragon'

    def __init__(self, name, hp, ac, attacks, energy):
        super(Dragon, self).__init__(name, hp, ac, attacks)
        self.energy = energy

    def __repr__(self):
        return "{}(name={}, hp={}, ac={}, attacks={}, energy={})".format(self.__class__.__name__, self.name, self.hp,
                                                             self.ac, self.attacks, self.energy)

m = Monster(name='Cave spider', hp=[2, 6], ac=16, attacks=['BITE', 'HURT'])
ms = yaml.dump(m)
# print(ms)
d = Dragon(name='Cave spider', hp=[2, 6], ac=17, attacks=['BITE', 'HURT'], energy=5000)
ds = yaml.dump(d)
# print(ds)

print(yaml.load(ms, Loader=yaml.Loader))
print(yaml.load(ds, Loader=yaml.Loader))
输出
Monster(name=Cave spider, hp=[2, 6], ac=16, attacks=['BITE', 'HURT']
Dragon(name=Cave spider, hp=[2, 6], ac=17, attacks=['BITE', 'HURT'], energy=5000)

所以其实到这里我还是没有明白为啥yaml要用metaclass来实现这个功能, 直到把子类的yaml_tag去掉, 才发现问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import yaml


class Monster(MyYAMLObject):
    yaml_tag = '!Monster'

    def __init__(self, name, hp, ac, attacks):
        self.name = name
        self.hp = hp
        self.ac = ac
        self.attacks = attacks

    def __repr__(self):
        return "{}(name={}, hp={}, ac={}, attacks={}".format(self.__class__.__name__, self.name, self.hp,
                                                             self.ac, self.attacks)


class Dragon(Monster):

    def __init__(self, name, hp, ac, attacks, energy):
        super(Dragon, self).__init__(name, hp, ac, attacks)
        self.energy = energy

    def __repr__(self):
        return "{}(name={}, hp={}, ac={}, attacks={}, energy={})".format(self.__class__.__name__, self.name, self.hp,
                                                             self.ac, self.attacks, self.energy)

m = Monster(name='Cave spider', hp=[2, 6], ac=16, attacks=['BITE', 'HURT'])
ms = yaml.dump(m)
# print(ms)
d = Dragon(name='Cave spider', hp=[2, 6], ac=17, attacks=['BITE', 'HURT'], energy=5000)
ds = yaml.dump(d)
# print(ds)

print(yaml.load(ms, Loader=yaml.Loader))
print(yaml.load(ds, Loader=yaml.Loader))
输出
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-58-1e3c4c44fbaf> in <module>
     33 # print(ds)
     34 
---> 35 print(yaml.load(ms, Loader=yaml.Loader))
     36 print(yaml.load(ds, Loader=yaml.Loader))

<ipython-input-58-1e3c4c44fbaf> in __repr__(self)
     24     def __repr__(self):
     25         return "{}(name={}, hp={}, ac={}, attacks={}, energy={})".format(self.__class__.__name__, self.name, self.hp,
---> 26                                                              self.ac, self.attacks, self.energy)
     27 
     28 m = Monster(name='Cave spider', hp=[2, 6], ac=16, attacks=['BITE', 'HURT'])

AttributeError: 'Dragon' object has no attribute 'energy'

这是因为Dragon这里没有yaml_tag的时候, 会继承父类Monster的yaml_tag, 这时Dragon.yaml_tag就是非空, 然后就会将!Monster这个标记与Dragon绑定到一起了, 覆盖了前面!Monster与Monster的绑定, 这时再去加载Monster类dump出来的内容, 就会报没有energy. 而使用metaclass就不存在这个问题, 因为在创建Dragon类时, 传入的属性字典里不会带有yaml_tag, 也就不会将!Monster这个标记与Dragon绑定到一起. 写代码测试如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
import yaml


class MyYAMLObjectMetaclass(type):
    """
    The metaclass for YAMLObject.
    """
    def __new__(cls, name, bases, kwds):
        print(cls, name, bases, kwds.get('yaml_tag', 'hahaha'))
        clsobj = super().__new__(cls, name, bases, kwds)
        if 'yaml_tag' in kwds and kwds['yaml_tag'] is not None:
            clsobj.yaml_loader.add_constructor(clsobj.yaml_tag, clsobj.from_yaml)
            clsobj.yaml_dumper.add_representer(clsobj, clsobj.to_yaml)
        return clsobj

class ThisYAMLObjectMetaclass(type):
    """
    The metaclass for YAMLObject.
    """
    def __init__(cls, name, bases, kwds):
        print(cls, name, bases, kwds.get('yaml_tag', 'hahaha'))
        super(ThisYAMLObjectMetaclass, cls).__init__(name, bases, kwds)
        if 'yaml_tag' in kwds and kwds['yaml_tag'] is not None:
            cls.yaml_loader.add_constructor(cls.yaml_tag, cls.from_yaml)
            cls.yaml_dumper.add_representer(cls, cls.to_yaml)


class ThisYAMLObjectBaseclass(object):
    """
    The metaclass for YAMLObject.
    """
    def __new__(cls, *args, **kwargs):
        print('base __new__', cls, args, kwargs)
        if cls.yaml_tag:
            cls.yaml_loader.add_constructor(cls.yaml_tag, cls.from_yaml)
            cls.yaml_dumper.add_representer(cls, cls.to_yaml)
        return object.__new__(cls)


class MyYAMLObject(metaclass=ThisYAMLObjectMetaclass):
# class MyYAMLObject(ThisYAMLObjectBaseclass):
# class MyYAMLObject(metaclass=MyYAMLObjectMetaclass):
    """
    An object that can dump itself to a YAML stream
    and load itself from a YAML stream.
    """

    __slots__ = ()  # no direct instantiation, so allow immutable subclasses

    yaml_loader = yaml.Loader
    yaml_dumper = yaml.Dumper

    yaml_tag = None
    yaml_flow_style = None

    @classmethod
    def from_yaml(cls, loader, node):
        """
        Convert a representation node to a Python object.
        """
        return loader.construct_yaml_object(node, cls)

    @classmethod
    def to_yaml(cls, dumper, data):
        """
        Convert a Python object to a representation node.
        """
        return dumper.represent_yaml_object(cls.yaml_tag, data, cls,
                flow_style=cls.yaml_flow_style)


class Monster(MyYAMLObject):
    yaml_tag = '!Monster'

    def __init__(self, name, hp, ac, attacks):
        self.name = name
        self.hp = hp
        self.ac = ac
        self.attacks = attacks

    def __repr__(self):
        return "{}(name={}, hp={}, ac={}, attacks={}".format(self.__class__.__name__, self.name, self.hp,
                                                             self.ac, self.attacks)


class Dragon(Monster):
    # yaml_tag = '!Dragon'

    def __init__(self, name, hp, ac, attacks, energy):
        super(Dragon, self).__init__(name, hp, ac, attacks)
        self.energy = energy

    def __repr__(self):
        return "{}(name={}, hp={}, ac={}, attacks={}, energy={})".format(self.__class__.__name__, self.name, self.hp,
                                                             self.ac, self.attacks, self.energy)

m = Monster(name='Cave spider', hp=[2, 6], ac=16, attacks=['BITE', 'HURT'])
ms = yaml.dump(m)
# print(ms)
d = Dragon(name='Cave spider', hp=[2, 6], ac=17, attacks=['BITE', 'HURT'], energy=5000)
ds = yaml.dump(d)
# print(ds)

print(yaml.load(ms, Loader=yaml.Loader))
print(yaml.load(ds, Loader=yaml.Loader))
输出
<class '__main__.MyYAMLObject'> MyYAMLObject () {'__module__': '__main__', '__qualname__': 'MyYAMLObject', '__doc__': '\n    An object that can dump itself to a YAML stream\n    and load itself from a YAML stream.\n    ', '__slots__': (), 'yaml_loader': <class 'yaml.loader.Loader'>, 'yaml_dumper': <class 'yaml.dumper.Dumper'>, 'yaml_tag': None, 'yaml_flow_style': None, 'from_yaml': <classmethod object at 0x1038e9320>, 'to_yaml': <classmethod object at 0x1038e9390>}
<class '__main__.Monster'> Monster (<class '__main__.MyYAMLObject'>,) {'__module__': '__main__', '__qualname__': 'Monster', 'yaml_tag': '!Monster', '__init__': <function Monster.__init__ at 0x1038d2f28>, '__repr__': <function Monster.__repr__ at 0x1038ce048>}
<class '__main__.Dragon'> Dragon (<class '__main__.Monster'>,) {'__module__': '__main__', '__qualname__': 'Dragon', '__init__': <function Dragon.__init__ at 0x1038ce0d0>, '__repr__': <function Dragon.__repr__ at 0x1038ce158>, '__classcell__': <cell at 0x103837af8: ThisYAMLObjectMetaclass object at 0x7fc8fb130de8>}
Monster(name=Cave spider, hp=[2, 6], ac=16, attacks=['BITE', 'HURT']
Dragon(name=Cave spider, hp=[2, 6], ac=17, attacks=['BITE', 'HURT'], energy=5000)

从上面的结果里可以看到, yaml_tag是没有在Dragon类的属性字典里的，即便是Dragon类会从Monster那里继承yaml_tag.

回到前面的用基类来实现对所有类使用debugmethods进行装饰的例子。这里因为每次创建对象的时候都会调用__new__方法, 会导致多次调用debugmethods装饰器, 这样会导致创建多少个对象, 调用一次类的方法就会输出多次, 测试如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# a baseclass
class debugmeta:
    def __new__(cls, *args, **kwargs):
        cls = debugmethods(cls)
        clsobj = object.__new__(cls)
#         clsobj = debugmethods(clsobj)
#         print('aaa', type(clsobj), clsobj)
#         print('aaa', clsobj, type(clsobj), vars(clsobj), dir(clsobj), type(clsobj.a), callable(clsobj.a))
        return clsobj
    
class Base(debugmeta):
    def a(self):
        pass

    
class Spam(Base):
    def __init__(self, name):
        self.name = name
    def a(self):
        pass

    
b = Base()
b.a()
s = Spam('name')
s.a()
print('-------')
s = Spam('lblb')
s.a()
输出如下
here <class '__main__.Base'>
Base.a
here <class '__main__.Spam'>
Spam.__init__
Spam.a
-------
here <class '__main__.Spam'>
Spam.__init__
Spam.__init__
Spam.a
Spam.a

这里Spam类创建了两个对象, 就调用了两次debugmethods, 所以会有多次输出。

到了这里, 我终于明白为什么要用metaclass来解决对于所有类使用debugmethods来装饰的问题，因为在metaclass里实现，则只会调用一次，因为一个类的创建只需要一次。也明白为什么yaml要使用metaclass, 而不是继承了。

总的来说, metaclass并不是什么奇淫巧技，简单来说就是一种改变类创建过程的能力。当然, 绝大多数情况下都不需要用到它。

联系作者

By

学习了Python程序设计入门第0讲后，对Python有了一定的了解，接下来我们来学习程序设计里一个重要的技巧，那就是递归。

什么是递归呢？简单来说，就是函数自己调用自己，只不过调用参数不同。

一个经典的例子是求正整数的阶乘, 计算某个整数的阶乘，就是求所有小于等于这个数的正整数的和，例如3的阶乘等于6, 5的阶乘等于120。另外还特别规定, 0的阶乘是1

普通的循环写法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
def factorial(n):
    s = 1
    for i in range(1, n + 1):
        s *= i
    return s
print(factorial(1))
print(factorial(3))
print(factorial(5))

1
6
120
40320

递归写法如下

1
2
3
4
def factorial(n):
    return n * factorial(n - 1)

print(factorial(3))

然而上面的写法会陷入死循环，因为它没有结束条件。加上结束条件后，递归求阶乘如下

1
2
3
4
5
6
7
8
9
10
11
def factorial(n):
    if n == 1 or n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(0))
print(factorial(3))
print(factorial(5))
1
6
120

如此我们知道递归程序的一个重要条件是要有结束条件

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …….., 写成公式就是 F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3)

接下来我们用写一个递归程序来计算斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(1, 10):
    print(i, fibonacci(i))
    
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34

如果仔细观察上面的fibonacci函数，会发现很多计算会重复了，例如求fibonacci(5)时，会计算fibonacci(4)和fibonacci(3), 而求fibonacci(4)时会计算fibonacci(3)和fibonacci(2), 这里fibonacci(3)就会重复计算了，这就导致这个递归函数会特别慢，下面我们测试下fibonacci(35)的速度, 可以看到计算fibonacci(35)差不多要2.82s，这是无法接受的，这种情况可以写成非递归的fibonacci函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def fibonacci(n):
    a = 1
    b = 1
    i = 2
    while i < n:
        c = a + b
        a = b
        b = c
        i += 1
    return b
    
    
for i in range(1, 10):
    print(i, fibonacci(i))

1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34

此时再计算fibonacci(35)就会很快了

既然递归算法的执行效率不高，那为什么还要用递归？这是因为，一些很难的问题，有时候用递归会变得很简单。一个经典的例子是Hanoi塔问题

汉诺塔(Towers of Hanoi)是一个在入门书籍中常见的例题或习题, 它是说: 有3根柱子, 1、2与3,在柱子1上串了从上到下编号是1, 2, …, m的圆片, 号码小的圆片也小. 问题是, 请写一个程序, 把柱子1上的圆片搬到柱子3去。在搬的时候有3个要求: 第一, 每次只能搬一个圆片; 第二, 要搬的圆片得从某个柱子取出, 并且放到另一根柱子上; 第三, 任何时刻、任何柱子上的圆片, 从上到下都是从小到大排列。

要写出一个非递归算法，是相当有挑战的，参见非递归汉诺塔, 而用递归的话，却非常容易。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def hanoi_tower(n):
    return _hanoi_tower(n, 1, 2, 3)


def _hanoi_tower(n, start, mid, end):
    """
    把n块圆片从start柱子，借助mid柱子, 搬到end柱子
    """
    if n == 1:
        print("Move disk %d from %d to %d" % (n, start, end))
    else:
        _hanoi_tower(n - 1, start, end, mid)
        print("Move disk %d from %d to %d" % (n, start, end))
        _hanoi_tower(n - 1, mid, start, end)
        
hanoi_tower(3)

Move disk 1 from 1 to 3
Move disk 2 from 1 to 2
Move disk 1 from 3 to 2
Move disk 3 from 1 to 3
Move disk 1 from 2 to 1
Move disk 2 from 2 to 3
Move disk 1 from 1 to 3

总的来说，递归算法要满足以下两个条件

  1. 要有结束条件，像factorial和fibonacci中的两个if判断
  2. 递归的规模要越来越小，像factorial中，求factorial(n)是通过factorial(n-1)得到，fibonacci中求fibonacci(n)是通过求fibonacci(n-1)和fibonacci(n-2)得到，这里传入递归函数的参数都越来越小。

掌握了递归，就掌握了程序设计里非常强大武器之一。

联系作者

By

读者可以找一本书, 研究一下快速排列法(Quick Sort)的概念, 并且写成程序

说明: 快速排列法是CAR. Hoare提出来的方法, 它需用到递归的技巧。它的概念是这样的, 有一个数组x[], 它有n个元素。如果能够在x[]中找出一个元素x[k], 使得在x[k]左边都比x[k]小或相等, 在x[k]右边的则大于或等于x[k].

因此, 只要把x[1]~x[k-1], x[k+1]~x[n]分别排列好, 两者合并, 就可以把整个x[]排好了

所以为x[1]…x[n]排序就分成两个部分, 第一部分是找出一个分界点x[k], 满足上述的条件, 第二部分是递归地去排x[1], … x[k-1], 与x[k+1], …, x[n], 排好后结果就出来了

所有快速排列法程序的差异都在第一步, 如何找出分界点x[k]

解答见quick_sort.py

联系作者

By

汉诺塔(Towers of Hanoi)是一个在入门书籍中常见的例题或习题, 它是说: 有3根柱子, 1、2与3,在柱子1上串了从上到下编号是1, 2, …, m的圆片, 号码小的圆片包小. 问题是, 请写一个程序,把柱子1上的圆片搬到柱子3去。在搬的时候有3个要求:第一, 每次只能搬一个圆片; 第二, 要搬的圆片得从某个柱子取出, 并且放到另一根柱子上; 第三,任何时刻、任何柱子上的圆片, 从上到下都是从小到大排列。书上的解法都是递归的, 请写一个非递归且不用堆栈来仿真的程序.

说明: 如果用教科书中的解法, 那么递归是个非常好且效率非常高的技巧, 程序大致如程下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#coding: utf-8

def hanoi_tower(n):
    return _hanoi_tower(n, 1, 2, 3)


def _hanoi_tower(n, start, mid, end):
    if n == 1:
        print("Move disk %d from %d to %d" % (n, start, end))
    else:
        _hanoi_tower(n - 1, start, end, mid)
        print("Move disk %d from %d to %d" % (n, start, end))
        _hanoi_tower(n - 1, mid, start, end)


if __name__ == "__main__":
    hanoi_tower(3)

这个观点是, 先把在start柱子上的n-1个圆片搬到mid柱子上去(用end柱子作中继站), 于是在strt柱子上就留下3在最下方, 也就是最大的一个圆片, 即第n号, 把它从start搬到end去(见print); 现在的情况是, 最大的已经到了目的地, 但在上方的第1 ~ n－1号还停留在mid柱子上; 第三步就是把mid上的n-1个圆片搬到end柱子上, 用start柱作中继站。当然, start、mid、end就是题目中的3根柱子, n是要搬的圆片数目.

递归的解不但漂亮, 而且容易懂; 不过了解了递归解法之后产能够由它而发展出一个非递归的解吗? 当然, 用堆栈来仿真并不是所期望的, 应该把递归动作中在什么时候搬那个圆片, 从何处搬到何处这一层关系弄清楚, 那么问题就不难了。

参考文献: 河内之塔(Towers of Hanoi)是法国人 M. Claus( Lucas)在1883年从泰国带到法国的(越南那个时候是法国属地), 河内曾经是越战时北越的首都, 现在的胡志明市。有很多人译成“汉诺威塔”是不对的, 音虽相差不远, 但却显然地误解了Hanoi这个字。河内之塔有一个起源的故事, 这是De Parville在1884年讲的。在Benares地方有一座神庙,从天神创世起, 就在神庙地底、大地的中心处立了3根钻石的针, 一根针上串了64个用金子铸成的圆片,从上到下圆片愈来愈大,神庙的僧侣按照前面提过的方法把这64个金圆片搬到第三根钻石针上,一旦工作完成,这些针、圆片、神庙以及这个世界都会随之消失。这段时间有2-1长, 亦即18446744073709551615步,纵使僧侣毫不犯错,恐怕也得花几百亿年才能搬得完。以上的史料出自下面两本书:

  1. W.W. Rouse Ball and H.S. M Coxeter. Mathematical Recreations and Essays. 13th ed, Dover, 1987
  2. M. Kraitchik Mathematical Recreations. 2nd ed. Dover. 1953 不用递归法来解河内之塔,曾经是一个很热门的业余问题,文献相当多,本文不打算一列举,与Gay码的联系也陆续地被人们一再“发现”,本书方法是取自 H. Mayer(加州圣地亚哥州立大学教授)与 Don Perkins(美制四年级,等于中国的高一学生)在1985年的一篇文章, Mayer教授指出这是Perkins想出来的方法,但他们两位都不曾指出这个方法与Gray码的联系,不过 Perkins不知道Gray码是可以预见的
  3. H Mayer and D. Perkins. Towers of Hanoi Revisited, A Nonrecursive Surprise, SIGPLAN Notices.Vol.19(1984),No.2,pp.80~84 这方面的中文文献并不多,前几年笔者在《Mcmo随笔》上一连写过3个月的介绍或许可以提供参考。那3篇文章入手比较浅,也不曾提到Gray码, 所以有些地方说得不很清楚,如果现在有机会重写, 一定可以做得更好。在那一系列的第三篇中, 还有另一个有的公式与进一步的参考文献, 有兴趣的朋友可以一看
  4. 冼镜光.谈河内之塔《Micro随笔》,微电脑时代.1986年9月 pp.170~174; 1980年10月, pp156~163; 1986年11月, pp.159~163

解答见hanoi_tower.py

联系作者

By

自从负责CMDB后，很多问题都得自己亲自去面对，于是就得开始动动大脑，这时就发现之前设计不合理的地方。

如下是之前设计的应用表

1
2
3
4
class Application(Model):
    '''应用信息'''
    name = models.CharField(max_length=100, unique=True, help_text='应用名')
    language = models.CharField(max_length=64, help_text='应用语言')

这里数据是同步自另外一个系统，同步的时候只是把语言当做一个字段，这样也看不出什么问题。但是当应用数据源迁移自CMDB后，问题就来了。此时如果要创建一个应用，要有个应用语言列表供选择，然而CMDB里表设计的时候没有考虑语言表，所以没法提供相应的API。

综合考虑后，添加了语言表，并且在应用表下添加应用语言外键

1
2
3
4
5
6
7
8
9
10
class Language(Model):
    '''应用语言'''
    name = models.CharField(max_length=50, help_text='语言', unique=True)  
    
    
class Application(Model):
    '''应用信息'''
    name = models.CharField(max_length=100, unique=True, help_text='应用名')
    language = models.CharField(max_length=64, help_text='应用语言')
    language_fk = models.ForeignKey(Language, on_delete=models.SET_NULL, null=True, db_constraint=False, help_text='语言')

最初的时候是考虑直接将应用表里的language改成外键，但想想这样修改会对之前提供出去的API有影响，所以还是决定添加language_fk外键。

这样修改后，需要创建应用时，写入language_fk的同时，也写入language即可，这个在Django里不难实现。

联系作者

By

遍写一个程序,读入一道正确的算术式, 把它转译成反向波兰形式(Reversed Polish), 为了方便起见, 假设整道算术式在同一列上, 并且变量只有一个英文字母,不含常数(换言之,所有运算都是一个字母的变量). 目前,只需要处理+, -, *, /, (, )即可, 没有正负号.

说明: 反向波兰形式是用来表示一道表达式的常见写法, 是由波兰学派的逻辑学家发展出来表示逻辑式子用的。它有一个很重要的特性,就是不会用到括号, 在寻常的算术式子中, 运算是写在两个操作数之间, 但反向波兰形式则是把运写在对应的操作数后方。例如a+b写成ab+, a+bc 写成abc+, ab+c写成abc+。对a+b而言, +的操作数是a与b, 所以写成ab+是很明显的; 再看a+bc, 最先算的是bc, 因而写成bc, +的两个操数是a与bc,因此就写成abc+; 同理,ab+c写成abc+就不必解说了

如果算术式子中有括号, 括号中的部分对某个运算而言就是一个完整的操作数。在(a+b)(c+d)中, a+b的写法是ab+, c+d的写法是cd+, 但ab+与cd+又是的操作数, 因此得到ab+cd+, 再看一例, a(b+c)-(e+f)/g, a与bc+是的操作数, 所以这一部分可以写成abc, 同理(c+f)/g可以写成ef+g/, 因此整个式子就是abc+*ef+g/-

从上面的说明可以看到, 一旦写成反向波兰形式, 括号就没有了, 这是它方便的地方. 但是如何把算术式转变成反波兰式呢? 如果仔细研究上述的结果可以有下面的结论:

  1. 反向波兰形式中变量的顺序与原来算术式中的顺序相同
  2. 运算永远出现在它的两个操作数后方

因为上述的第一点理由, 当读到一个操作数的时候, 就可以把它输出, 因为操作数在输入与输出中顺序相同。运算又如何呢? 运算是比较麻烦的, 先不管左、右括号, 因为在自左向右地读取输入时, 看到了一个+号, 此时不但还没有见到它的右边操作数, 更看不到下一个运算, 于是无法决定这个+号是不是可以计算。例如a+bc, 如果现在才读入+,就没有办法知道这个加法能不能计算, 一直到出现才能作决定(也就是不能算); 同样, 看到了也不表示它能够算, 为什么呢? 如果输入是a+b(x+y), 把x+y算出来之后才能算法。换句话说, 在下一个运算出现之前, 并不知道目前这个运算可不可以算; 回想一下先乘除后加减的规则, 如果下一个运算(例如+)的优先级比现在的(例如)低, 那么就可以算现在的这个。正因为如此, 用堆栈是个好方法, 把不能算的运算先推到堆栈中, 于是现在的这一个就在顶上, 当下一个运算出现了, 就看看顶上那一个与下一个的关系, 如果顶上(现在)的这一个可以算, 就把它输出。如果碰到左、右括号又怎么办呢?

以上就是个简单的提示。其实, 可以在其他的书中找到解答,但建议不要这样做,因为在计算机刚问世时这是个难题, 如果能够独立解决它而不求助外力的话, 是很值得自豪的, 但如果学过了这方面的知识, 就不妨跳过去, 做一做后面的习题。注意,以上的方法与提示并不是最好的,可以参看有关编译程序的专业书籍来寻求更好、更普遍性的解法

解答见polish.py

联系作者

By

如果有n个对象, 它们的计量单位各为k1, k2, …, kn; 现在有一个可以容纳K单位的背包, 请写一个程序, 找出有没有办法在1, 2, …, n中选P个元素出来, 使得计量单位的总和为K, 可以刚好把背包装满。这就是有名的背包问题(Knapsack Problem)

说明:以计量单位分别是1, 2, 4, 7, 10, 12, 13, 15, 17这9个对象来看好了, 若背包的容量是27, 可以取4,10与13, 因为4 + 10 + 13 = 27; 但也可以取2, 12, 13, 因为27 = 2 + 12 + 13; 更可以取10与17, 因为27 = 10 + 17;当然还有其他的可能解答。不过,这个题目却是不一定有解的。例如, 若对象的计量单位是1, 5, 10, 15, 20; 而背包是14, 物件中比14小的有1, 5, 10, 无论如何选择, 都不可能加出一个14来的。

就像上一题找零钱的问题一样, 可以用动态规划的技巧来解这个问题, 不过会复杂, 但基本道理是完全相同的. 这里要求有解的时候，找出一个解。

解答见knapsack.py

联系作者