实战组合式设计

需求

leetcode 上有一道关于强密码校验器的练习题，如下所述：

一个强密码应满足以下所有条件：

• 由至少6个，至多20个字符组成。
• 至少包含一个小写字母，一个大写字母，和一个数字。
• 同一字符不能连续出现三次 (比如 "...aaa..." 是不允许的, 但是 "...aa...a..." 是可以的)。

编写函数 strongPasswordChecker(s)，s 代表输入字符串，如果 s 已经符合强密码条件，则返回0；否则返回要将 s 修改为满足强密码条件的字符串所需要进行修改的最小步数（插入、删除、替换任一字符都算作一次修改）。

需求分析

需求中有两个要点：

• 强密码考虑了三个维度：长度、连续性、字符种类
• 允许使用三种修改方法：插入、删除、替换

我们下面使用表格来分析一下这几种修改方法对这几个纬度的影响：

修改方法	长度	字符种类	连续性
插入	+1	+1 (if < 3)	连续性长度-2
删除	-1	不影响	连续性长度-1 （连续性长度%3的值越小优先级越高）
替换	不影响	+1 (if < 3)	连续性长度-3

说明如下：

• 修改长度：对长度的修改是确定的（长了就删除，短了就插入），但是要注意插入和删除也会修改连续性和字符种类，所以要先让密码满足长度的要求，然后使用替换来改进连续性和字符种类
• 修改字符种类：在修改长度和修改连续性后，如果字符种类还不是3，则应该通过替换增加字符种类
• 修改连续性：对于插入来说，密码长度肯定小于6，那么只可能有一个连续性字符子串（3<=子串长度<=5），而插入一个字符会使得该子串长度减2，这时要么已没有连续性字符子串，要么还有一个长度为3的连续性字符子串（再做一次替换即可）；对于删除来说，密码长度肯定大于20，那么连续性字符子串可能有多个，这时应该选择子串长度模3的值最小的子串，然后将该子串长度减1

软件设计

组合式设计概述

七巧板，是大家熟知的一种源自中国的古老智力游戏：

由这么七块简单的小素材，可以拼出变化无穷的图案，受限的只是你的想象力：

这个简单的游戏，蕴含这一种极具价值的设计思想：组合。

基本语义规则都是小素材，基本语义规则通过组合形成新的对用户有价值的语义规则就是图案。对于强密码校验器这个需求来说，要实践组合式设计，首先要拆出小素材，然后再将小素材层层组合成强密码校验器图案。其实，软件设计就是一门研究系统“如何分”和“怎么合”的学问，目的是为了在让软件在长期范围内容易应对变化，而组合式设计就是将系统正交拆分且低成本组合的最佳软件设计实践。

于是，问题来了，系统究竟该如何分？在回答这个问题之前，我们先看看什么是好的软件设计。

我们在软件开发中，经常随口就说简单设计，但简单设计不是一句语义模糊的无法评判的空洞口号，而是具有明确的衡量标尺。
关于这个标尺的定义，Kent Beck 给出了清晰的答案：

• 通过所有测试（Passes all tests）
• 尽可能消除重复 (Minimizes duplication)
• 尽可能清晰表达 (Maximizes clarity)
• 更少代码元素 (Has fewer elements)

以上四个原则的重要程度依次降低。

这就是简单设计四原则，只有第四条强调简单，其他三条分别从需求、易修改性和可理解性方面对简单进行了约束：

• 你不能为了简单而不去实现客户需求
• 你不能为了简单而不去消除重复
• 你不能为了简单而不注重清晰表达

固然前面三条的价值比简单这个价值更重要，但是简单也同样会约束前面三条：

• 为了简单，不要实现客户暂时还用不到的需求
• 为了简单，不要在变化方向未出现之前就对类进行额外的抽象
• 为了简单，不要增加额外的代码元素，除非能增强表达力

我们在工作中应按照需求、易修改性、可理解性和复杂度这四个纬度的重要程度由高到底对任务进行排序。比如，我们重构时，先消除重复，然后再增强代码的表达力。

如果一个软件设计满足简单设计四原则的要求，我们就说这个软件设计是好的软件设计。

为了让简单设计四原则中的第二条（尽可能消除重复）的达成有章可循，袁英杰大师提出了正交设计四原则：

• 消除重复
• 分离不同的变化方向
• 缩小依赖范围
• 向着稳定的方向依赖

第一条是重复出现之后被动的消除重复，而后面三条是重复出现之前的主动预防策略。同时，前面两条是为了驱动模块内向高内聚方向演进，后面两条是为了驱动模块间向低耦合方向演进。

于是，我们给出组合式设计的定义：应用正交设计四原则，将系统分解成很多单一职责的小类或函数（函数式），然后再将它们根据需要而灵活的组合起来。

对于组合手段来说，最常见且通用的手段是依赖注入，其他手段与编程语言相关，比如 C++ 可以使用多重继承来实现组合。

语义模型

我们对强密码校验器这个需求的通用语言进行一下梳理：

1. 强密码考虑了三个纬度：长度记作 len，连续性记作 cont，字符种类记作 types；
2. 允许使用三种修改方法：插入记作 insert，删除记作 delete，替换记作 replace；
3. 原子操作记作 atom，需求中有四个原子操作，分别为密码长度小于 6 的操作 len_less_than_atom， 密码长度大于 20 的操作，len_more_than_atom， 字符种类小于 3 的操作 types_atom，同一个字符连续出现 3 次的操作 cont_atom
4. 每个原子操作 atom 包含两部分，即匹配器和执行器二元组，记作(matcher, action)，那么针对四个原子操作，就有(len_less_than_matcher, insert_action)、(len_more_than_matcher, delete_action)、 (types_matcher, replace_action) 和 (cont_matcher, replace_action)
5. 需求中有多个规则 rule，atom 是最基本的 rule，repeat（多次执行） 是修饰语义的 rule，allof （“与”的关系）和 anyof（“或”的关系）是组合语义的 rule，rule 通过组合可以产生新 rule

我们使用统一语言形式化表达一下需求：

password = newPassword(s)
len_less_than_atom_rule = atom(len_less_than_matcher, insert_action)
len_more_than_atom_rule = atom(len_more_than_matcher, delete_action)
types_atom_rule = atom(types_matcher, replace_action)
cont_atom_rule = atom(cont_matcher, replace_action)

len_rule = anyof(repeat(len_less_than_atom_rule), repeat(len_more_than_atom_rule))
types_rule = repeat(types_atom_rule)
cont_rule = repeat(cont_atom_rule)

rule = allof(len_rule, types_rule, cont_rule)
steps = rule(password)

从上面的形式化描述，可以很容易的得到强密码校验器的语义模型：

rule: Password -> int
matcher: Password -> bool
action: Password -> int

rule 的几种形态：

rule: atom | repeat | allof | anyof

我们用类图表达一下强密码校验器的组合式设计：

我们再用表格来表达一下 Rule 的分类：

分类	Rule
原子语义	LenLessThanAtom LenMoreThanAtom TypesAtom ContAtom
修饰语义	Repeat
组合语义	AnyOf AllOf

软件实现

在《聊聊编程范式》一文中，我们梳阐述了常见的三种编程范式（结构化编程、面向对象编程和函数式）的基本设计和架构风格，梳理了编程范式之间的关系。

从结构化编程到面向对象编程，再到函数式编程，离图灵机模型越来越远，但抽象程度越来越高，与领域问题的距离越来越近。

对于组合式设计的实现，我们既可以选择面向对象编程，也可以选择函数式编程。函数式编程更抽象一些，但代码更简洁；面向对象编程部分代码稍显繁杂，但相对来说易于理解。本文选择以函数式编程为例来实践组合式设计，读者可以自行使用面向对象编程来尝试一下，大同小异。

API 实现

需求中给出了 API 的定义：

strongPasswordChecker(s)

Golang 代码的实现如下：与统一语言的形式化表达基本一样

func StrongPasswordChecker(s string) int {
    password := newPassword(s)

    len_less_than_atom_rule := atom(len_less_than_matcher, insert_action)
    len_more_than_atom_rule := atom(len_more_than_matcher, delete_action)
    types_atom_rule := atom(types_matcher, replace_action)
    cont_atom_rule := atom(cont_matcher, replace_action)

    len_rule := anyof(repeat(len_less_than_atom_rule), repeat(len_more_than_atom_rule))
    types_rule := repeat(types_atom_rule)
    cont_rule := repeat(cont_atom_rule)

    rule := allof(len_rule, types_rule, cont_rule)
    steps := rule(password)
    return steps
}

函数式设计的基本方法为：借助闭包的单一接口的标准化和高阶函数的可组合性，通过规则串联设计，完成数据从源到结果的映射描述。这里的映射是通过多个高阶函数的形式化组合完成，描述就像写数学公式一样放在那，等源数据从一头传入，然后经过层层函数公式的处理，最后变成你想要的结果。数据在形式化转移的过程中，不仅仅包括数据本身，还包括规则的创建、返回和传递。

数据（对象）实现

我们下面看看数据本身 Password 的设计，该数据的表现形式是一个对象。

Password 数据结构

type Password struct {
    initialStr   string
    Len          int
    Steps        int
    TypesNum     int
    hasDigital   bool
    hasLowerCase bool
    hasUpperCase bool
    contNumbers []*ContNumber
}

type ContNumber struct {
    initialChar  byte
    initialIndex int
    times        int
}

Password 结构中包括了密码字符串的原始信息、预处理信息和改造过程中的信息。密码中可能包括多个连续性字符组成的数，我们通过 []*ContNumber 来表示。

Password 对象的构造

func newPassword(s string) *Password {
    pwd := &Password{initialStr: s, Len: len(s), Steps: 0, TypesNum: 0,
        contNumbers: make([]*ContNumber, 0)}
    typesInit(pwd)
    contInit(pwd)
    return pwd
}

说明：共有三步

• 构造 Password 数据，记录密码字符串 s 的初始值和长度
• 遍历密码字符串，初始化字符种类
• 遍历密码字符串，初始化连续性数的数组

Password 对象的方法

下面这些方法都是在 TDD 的实践过程中，为了达成正交设计四原则的目标，通过 extract 重构手法逐步提炼出来的：

func (p *Password) increaseLen() {
    p.Len++
}

func (p *Password) decreaseLen() {
    p.Len--
}

func (p *Password) increaseSteps() {
    p.Steps++
}

func (p *Password) increaseTypesNum() {
    if p.TypesNum < maxTypesNum {
        p.TypesNum++
    }
}

func (p *Password) consumeContNumber(quota int) {
    ...
}

func (p *Password) consumeContNumberByPrio() {
    ...
}

rule 的实现

这一部分是组合式设计的核心。

数据在形式化转移过程中，源数据是 Password，层层函数的输入输出数据都是 Password ，同时目标数据也是 Password 的 Steps 字段，所以我们使用 Password 指针类型来表达数据类型。

rule 的抽象表达

我们知道，rule 包含两部分，即匹配器和执行器二元组：

type Matcher func(pwd *Password) bool
type Action func(pwd *Password) int
type Rule func(mather Matcher, action Action) func(pwd *Password) int

原子语义的实现

atom 的实现很简单，就是返回一个闭包：当匹配器满足时，就返回执行器的结果（steps）

func atom(matcher Matcher, action Action) func(pwd *Password) int {
    return func(pwd *Password) int {
        if matcher(pwd) {
            return action(pwd)
        }
        return 0
    }
}

原子语义的 rule 有四个，分别为 LenLessThanAtom、LenMoreThanAtom、TypesAtom 和 ContAtom，核心是设计它们的匹配器（4个）和执行器（3个）。

匹配器实现：

func len_less_than_matcher(pwd *Password) bool {
    if pwd.Len < minLen {
        return true
    }
    return false
}

func len_more_than_matcher(pwd *Password) bool {
    if pwd.Len > maxLen {
        return true
    }
    return false
}

func types_matcher(pwd *Password) bool {
    if pwd.TypesNum < 3 {
        return true
    }
    return false
}

func cont_matcher(pwd *Password) bool {
    if len(pwd.contNumbers) > 0 {
        return true
    }
    return false
}

执行器实现：

func insert_action(pwd *Password) int {
    pwd.increaseLen()
    pwd.increaseTypesNum()
    pwd.consumeContNumber(2)
    pwd.increaseSteps()
    return pwd.Steps
}

func delete_action(pwd *Password) int {
    pwd.decreaseLen()
    pwd.consumeContNumberByPrio()
    pwd.increaseSteps()
    return pwd.Steps
}

func replace_action(pwd *Password) int {
    pwd.increaseTypesNum()
    pwd.consumeContNumber(3)
    pwd.increaseSteps()
    return pwd.Steps
}

修饰语义的实现

修饰语义的 rule （新）只有一个，即 repeat，含义是重复执行被修饰的 rule（旧），直到符合预期：

func repeat(rule func(pwd *Password) int) func(pwd *Password) int {
    return func(pwd *Password) int {
        for ;; {
            ret :=  rule(pwd)
            if ret == 0 {
                return pwd.Steps
            }
        }
    }
}

组合语义的实现

组合语义的 rule 有两个，即 allof 和 anyof，分别表达“与”的关系和“或”的关系：

func allof(rules... func(pwd *Password) int) func(pwd *Password) int {
    return func(pwd *Password) int {
        steps := 0
        for _, rule := range rules {
            pwd.Steps = 0
            steps += rule(pwd)
        }
        return steps
    }

}

func anyof(rules... func(pwd *Password) int) func(pwd *Password) int {
    return func(pwd *Password) int {
        steps := 0
        for _, rule := range rules {
            steps += rule(pwd)
            if steps > 0 {
                return steps
            }
        }
        return 0
    }
}

小结

本文概述了组合式设计的要点，并通过实战强密码校验器的案例，向读者展示了组合式设计落地的主要过程和步骤，希望对读者有一定的收益。

如果说正交设计是软件设计的皇冠，那么组合式设计就是皇冠上的明珠。应用组合式设计产出的代码扩展性强且易于理解，你是否深有感触？如果你也曾写过或读过强密码校验器的实现代码，你都发现过哪些坏味道？欢迎大家留言探讨！

本文实战过程中的源码及 TDD 用例，作者都放到 github 了：https://github.com/agiledragon/strong-password，感兴趣的同学可以查阅。

---