且听疯吟 如此生活三十年

这个问题之前很好解决,使用浏览器 plugin 即可。
但是随着 Chrome 和 Firefox 都先后放弃了 NPAPI plugin,这一方法也行不通了,而且很多人是很讨厌 plugin 的。
但是在默认禁止了 NPAPI 的 Chrome 版本,QQ 依然可以实现快速登录(一键登录),是怎么做到的呢?

原理

其实不难猜。既然不存在 plugin,无法以此来实现浏览器内和本地客户端的直接通信,那么排除其他的黑科技,有一种很简单的方法可以实现这个效果。
那就是在客户端开一个 Server,在浏览器里面请求这个地址。
理论上这样是可以实现的,至于 QQ 是不是用的这种方法,稍微验证下好了。

验证

  • 找一个有 QQ 快速登陆的页面,比如 mail.qq.com

  • 登陆 QQ 客户端

  • 打开浏览器的 Developer Tools -> Network

  • 刷新页面,观察所有请求的 domain

  • 好明显,这就是我们要找的了

    • 完整请求 url 是这样的

      https://localhost.ptlogin2.qq.com:4301/pt_get_uins?callback=ptui_getuins_CB&r=0.22949112393586502&pt_local_tk=-2027291081
      
    • 看看这个请求的 Response Content

      var var_sso_uin_list = [
          {
              account: "xxxxxx",
              client_type: 65793,
              face_index: 0,
              gender: 1,
              nickname: "xxx",
              uin: "xxx",
              uin_flag: xxxxx,
          },
      ];
      ptui_getuins_CB(var_sso_uin_list);
      

      很明显是当前登录的用户信息

    • ping 一下这个请求的 domain
      不出所料结果是 127.0.0.1

      ping localhost.ptlogin2.qq.com
      :: Pinging localhost.ptlogin2.qq.com [127.0.0.1] with 32 bytes of data
      
  • 现在我们验证下是否是 QQ 开了这个 Server

    • 查看哪个程序占用了 4301 端口

      netstat -ano | findstr "4301"
      ::  TCP    127.0.0.1:4301   0.0.0.0:0   LISTENING   14516
      
    • 得到 pid 我们就可以看否是 QQ 在监听这个端口了

      tasklist | findstr "14516"
      :: QQ.exe  14516 Console   2     87,892 K
      

安全

可能有人担心会不会有安全问题,会不会其他网站访问这个 url 就拿走用户信息?其实挺容易解决,存一个 token 到服务端,获取的时候校验下就好了。
但是归根到底取决于腾讯对这方面安全的重视程度和意愿了,至少之前是确实存在从网页上获取当前登录的 QQ 信息的方法,虽然问题不是出在快速登录这部分。

越来越多的网站开始更加关注安全问题了,比如,Facebook 会在你把密码从 abc123 改为 Abc123 的时候的时候提示你

Your new password is too similar to your current password. Please try another password.

很贴心是不是?但是,他们是怎么做到的?难道 Facebook 保存了用户的明文密码么?

编辑距离

计算两个字符串的相似性,或者说「编辑距离」很容易,我们有很多现成的算法和代码。
但是,显然 Facebook 不会傻到存储明文密码,存储的肯定是 hash("abc123")
而字符串中的差别和 hash 结果并不是一一对应的。两个相近的字符串,其 hash 结果可能差别很大。

simhash

可能你听说过 simhash 算法。Google 就是使用这种算法来做网页查重的。
传统的 hash 算法如 md5,一般尽可能要求结果分布均匀,因此,原始字符串的微小变动也会导致 hash 结果出现很大差异。
而 simhash 是一种局部敏感的 hash 算法,选定位数,提取特征,然后对每一段特征值计算 hash,然后将每一段值处理到 simhash 结果,得到最后的 simhash 值。比较海明距离就可以大概知道两个文档的相似度了。
具体的算法懂得不多就不瞎说了……大概可以推测,对于长文档这种方法是有效的,但是对于短文本,如 password 来说,效果可能不会太好。

Facebook 的做法

事实上这个问题好奇的人也很多,Stack Exchange 上有一个回答 http://security.stackexchange.com/questions/53481/does-facebook-store-plain-text-passwords,下面有一个自称接触过密码验证这部分代码的人肯定了这个猜测。
我觉得这种做法看起来还是挺合理的。

Facebook 用了一种看起来很「土」的方法,操作方法类似这样:

  1. 用户注册,密码 abc123,Facebook 保存了 `hash(“abc123”)
  2. 用户修改密码,提交新密码 Abc123
  3. Facebook 拿到新密码,根据这个密码,生成一堆类似于 ABC123abc123 这样相近的密码,使用同样的 hash 方法,去和 1 中的 hash 比对,一旦发现有相同的,那么可以判定新密码与旧密码是相似的。

很好的反向思维,不是去计算相似性,而是通过生成一堆相似密码来「暴力」尝试。

其他想法

事实上最初想到这个问题的时候,我考虑过这样的做法:

  1. 用户修改密码操作时,提示输入原密码
  2. server 临时记录用户的原密码
  3. 用户输入新密码,server 比对新旧密码
  4. 完成修改或过期后,销毁临时记录

不过即使是临时记录依然可能存在风险,如果需要较高的安全性的话这种方法是不可取的。

无意中翻到 Joe Armstrong 发在 erlang-questions 里的文章,Ways to get started 以及 history of erlang
如果你不知道 Joe Armstrong 是谁,我们给他的另一个称呼是 the father of Erlang :)
大概没有人比他更有资格写这种文章了吧。
在高手眼中大道至简,我们不一定学的来,但是听听还是很有启发的

随便瞎扯几句

忘掉工具

Forget about git/IDEs/rebar etc.
Forget about the tools

如果没有 IDE,没有自动打包工具,我们怎么编写和运行代码?
记住,shell 和文本编辑器对任何语言都是适用的。
当然我并不觉得这意味着需要放弃 IDE 之类的工具,而是在 get started 的时候,对程序怎么工作的有基本的了解是有好处的。
某种意义上来说,过于复杂的工具链意味着,一旦它没有按照你想象的运行,就需要花费更多的时间去解决它。

  • rebar!

    当然,不能忘了 rebar!
    事实上 rebar 已经快要成为 erlang project 的标配了。

Tools like rebar etc are under to automate something but if you don’t
know what it is that you are automating and if the tool doesn’t work
you will just end up being incredible confused.

「像 rebar 这样的工具会自动生成一些东西,但如果你不知道自动生成了什么,如果这些工具无法使用了,你将会变得困惑不已。」
说得好!
但是在更好的解决办法出现之前,也只能这么用了,寄希望于 OTP 组的改进吧,这一块也是我最不喜欢 erlang 的地方。

我一直觉得好的语言应该是某种程度上符合直觉的。这种直觉也许来自逻辑也许来自经验。
比如 erlang。
要举个反例也很容易,比如「世界上最好的语言」。
Joe Armstrong 是这么不经意的黑

Notice there is no quick fix here - if you want a quick fix go buy
“learn PHP in ten minutes”
and spend the next twenty years googling for
“how do I compute the length of a string”

hmm, well done!

the father of Erlang

Joe Armstrong 是个有趣的老头,也是真正的大师,推荐他的 blog,内容远远不止 erlang,可以看他讲讲信手拈来言简意赅的道理,喜欢八卦的话可以看他学 js 顺手黑黑其他语言 :)
以及他的 twitter @joeerl

最后是一段以前放在 erlang.org 上的话,如果学完 erlang 你还不懂这段话,可能你需要从头再来一遍 :)

The world is concurrent.
Things in the world don’t share data.
Things communicate with messages.
Things fail.
                      - Joe Armstrong

btw,Joe Armstrong 的邮箱地址是 erlang#gmail.com,是不是比 「I Wrote Python」 低调多了 :)

升级到 Windows 10 之后,很糟心的是通过 Microsoft Account 登录的时候,默认创建的账户文件夹居然不是 Microsoft Account 的 name,明明是 [email protected],结果创建出来的却是 nic …… 完全不知道这帮人怎么做到的 =-=
不管有没有强迫症,每次看到这个错的名字都实在不能忍,找到个修改的方法
参考了来自 superuser 的解决方法,原文针对的是 Windows 8,不过对 Windows 10 依然有效
原文地址 http://superuser.com/questions/495290/how-to-rename-user-folder-in-windows-8

步骤如下:

  • 用 nic 代表原来的账户名
  • 用 nick 代表新的账户名
  • 下面的操作中用你自己的需求替换 nic 和 nick

1. 创建一个本地管理员账户

Windows 10 中创建本地账户的选项藏得更深了,可以按如下方法操作

  • 打开 Setting
  • 找到 Family & other users
  • 点击 Add someone else to this PC
  • 弹出添加对话框,选择下面的 the person I want to add doesn't have an email address
  • 继续选择 Add a user without a Microsoft Account
  • 填写用户名密码,创建本地账户
  • 点击创建的用户,Change Account TypeAdministrator

2. 重命名账户名称

  • 退出当前账户,登录刚才创建的本地账户
  • 打开 Computer Management,快捷键 Win + X, G
  • 打开 System Tools
  • 找到 Local Users and Groups
  • 打开 Users,找到需要修改的用户 nic
  • 右键点击,Rename,修改为你想要的 nick

3. 重命名账户文件夹

  • 打开管理员权限的 Cmd,快捷键 Win + X, A
  • 输入 ren C:\Users\nic nick

4. 修改注册表关联

  • 打开注册表编辑器,快捷键 Win + X, R 打开运行,然后输入 regedit 回车
  • 找到 HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\ProfileList\
  • 一个个点开所有以 S-1-5 类似的字符开头的键,查看 ProfileImagePath
  • ProfileImagePath 值为 C:\Users\nic 的就是我们需要修改的账户,点击它,修改为 C:\Users\nick

5. 重新登录

  • 使用原来的 Microsoft Acount 登录原先的账号
  • 确定一切正常,账户文件夹也已经修改成功
  • 可以删除创建的本地账户了

hope it’s helpful.

最近又从头看 XMPP 的 RFC1,有时候也考虑如果是自己来设计,会如何做。
之前的印象是 XMPP 的繁琐和低效,现在看来,作为通用的协议,XMPP 确实有做得不错的地方,从头看下来还是有不少收获的。

现在项目告一段落,回头整理下 XMPP 服务端安全方面的一些简单想法,大概想到哪写到哪吧,安全方面懂得不多,欢迎指正。
考虑到安全,我们的初始目标大概包括这些:

  • 与服务端通信安全(不被窃听/篡改)
  • 鉴别用户身份
  • 保护用户数据

TLS

TLS2 用于在两个通信应用程序之间提供保密性和数据完整性,是必须开启的。

SASL

SASL3 是一种验证用户身份的框架。XMPP 本身没有办法分辨用户身份,必须借助于 SASL 协议。
SASL 协议确定了客户端和服务端沟通的应答机制及传输的编码方法,剩下的就需要自己实现了。
要识别用户身份,你需要在 SASL 的框架下定义和服务端交换的具体身份信息(比如用户名、密码),以及实现身份信息的存储和验证方式,而不需要考虑其他细节。
具体到 XMPP 下 SASL 的验证流程(如果建立了 TLS 连接,此时是在 TLS 连接上的):
一般不必支持所有的 SASL mechanisms ,选择安全性更可靠的,比如 SCRAM-SHA-1 (尽量不要使用 plain):

详细登录流程可以参考 ejabberd: Login

SCRAM-SHA-1

SCRAM4(Salted Challenge Response Authentication Mechanism) 是近年才开始使用的更安全的一种加密验证机制,可以很好的在 Server 和 Client 之间做双向的验证,已经有很多的服务开始使用这种方式验证了,比如 MongoDB。XMPP 也在协议中提供了这种方式的说明。
不讨论详细的加密算法细节,客户端验证登录时,大概流程如下:

  1. client 发送想要登录的 username 到 server (即 auth)
  2. server 为该 username 生成/查找出 salt(s),和 iteration count(i)、server nonce (r) 一并发回给 client (challenge,base64 编码)
  3. client 使用给定的 salt 和 iteration count 加密持有的 password,发回给 server (如果服务端对该 client 使用的 salt 和 iteration count 是固定的话,可以存储下生成的 client key,从而避免在 client 明文存储密码,会更安全)
  4. server 验证结果,如果成功则返回 success,并附上计算值
  5. client 校验 success 中返回的值,通过则证明 server 拥有 client 的验证

end_to_end

如果有非常严格的安全需求,可以考虑 OpenPGP ,XMPP 协议也提供了有限的支持
不过我个人觉得这种方法也不是那么完美:

  • 需要额外的交换 key 的渠道,而这些渠道不一定可信
  • 杜绝不了伪造身份,你没法确定 id 对应的绑定的就一定是 key 的拥有者
  • 信息冗长,加密的信息可能字节数会扩大到 10 倍甚至以上

文件服务

文件传输基本是现在 IM 客户端的基础功能了。
一般我们不会选择通过文本方式直接在消息中发送文件/图片,而是选择先上传到 HTTP 文件服务器,然后发送链接的形式。但是 HTTP 是无状态的,我们也不能每次在用户对资源操作的时候要求用户输入用户名密码。

首先考虑上传:

  • 上传通道泄露可能会带来滥用
  • AWS 可以使用 key 和 secret 校验上传请求
  • 将 secret key 存放在客户端可能被逆向
  • XMPP 服务端可以看作可信的已鉴权服务

所以可以考虑这样操作:

  • 已鉴权的客户端从 XMPP 服务端申请上传
  • 文件服务器生成一个上传用的 token,生成方式可能是
    token = hash(user + id + nonce + expire_stamp + secret)
  • XMPP 服务端从文件服务器获取生成的 token 并返回给客户端(假设 XMPP 服务端与文件服务器之间的通信是可信的,比如处于同一个内网。当然也可以 XMPP 服务端使用同样的 secret 和算法来计算 token 而不请求文件服务器)
  • 客户端向文件服务器提交上传请求,并带上 token, user, id, expire_stamp, nonce
  • 文件服务器校验是否过期以及
    hash(user + id + nonce + expire_stamp + secret) == token
  • 校验通过,上传文件到 AWS S3 或其他存储服务,返回文件 id 给客户端

然后是下载:
出于安全考虑,我们通常不会允许固定的 url 访问,而是通过增加验证和过期的方式来做一些限制。
一方面防止文件抓取,同时降低私密文件意外公开的风险,甚至可以通过更换 secret key,让公开的链接失效,强制客户端重新向服务端请求鉴权。
和上传文件类似:

  • 客户端提交请求的文件 id 给 XMPP 服务端-
  • XMPP 服务端用类似的方式生成一个 token 返回给客户端
  • 客户端使用链接 + token 的形式访问文件资源
  • 文件服务器校验 token, 以及是否过期等等,通过则返回资源

当然现实情况可能用不到复杂的机制,也可以根据情况适当放松要求。
btw, 至少我抓包验证不止一个重量级的 App 使用的就是类似于 http://xxxxx/uuid 的永久文件地址= =。

业务逻辑

即使在完善的安全机制下,也不要完全信任用户的输入
不像网页上按按 F12 就可以拿到很多信息,可能移动设备给人一种难以 hack 的错觉,但是决定有没有人来搞的是值不值得,还有运气 :)

有些问题可能看起来无所谓,但是开开脑洞还是挺有意思的

比如,最近碰到一个问题,简化形式是这样的:

IEnumerable<int> Range(int n) {
    var i = 0;
    while (i <= n) {
        // DoSomething1...
        yield return i;
        i++;
    }
}

Range(n).ForEach(x => DoSomething2(x));

void DoSomething2(x) {
}

看出问题了么?

  • IEnumerable 接口是没有 ForEach 方法的,ForEachList<T> 的方法,所以只能写成

    ```csharp
    Enumerable.Range(0, n).ToList().ForEach(x => DoSomething(x));
    ```
    

    但是显然这样就失去了延迟执行的意义了

  • 我们也可以尝试使用 IEnumerableSelect 方法,变成这样:

    ```csharp
    Enumerable.Range(0, n).Select(x => DoSomething2(x));
    ```
    

    当然这样也行不通,因为我们的 DoSomething2 方法是 void 类型的

  • 最后只能粗暴的给 DoSomething2 包装一个返回值

    Enumerable.Range(0, n).Select(x => { DoSomething2(x); return true; });
    

如果 IEnumerable 支持 ForEach 方法就好了?

  • 事实上 C# 设计者对此作了解释:“foreach” vs “ForEach”
  • 总之来说,List<T>.ForEachList<T> 本身的方法, Linq 不会提供有副作用的方法,它违反了 Linq side-effect-free 的设计理念
  • Mmm,听起来好像很有道理 :(

当然,这个例子本身不具有太大的意义,但是——

不妨开个脑洞

如果可以用 void 作为泛型参数呢?

  • 这样的代码不再有问题了

    Enumerable.Range(0, n).Select<int, void>(x => DoSomething2(x));
    
  • 也并没有违反 Linq 的设计理念(当然,取决于你怎么看了 :(

  • 更大的好处在于:
    如果把 void 看作泛型的一种,可以在不增加复杂度的前提下简化一些问题
    比如不需要为 MyClassMyClass<T> 写两次相同的代码了
    因为 MyClass 就相当于 MyClass<void>,我们可以统一所有处理逻辑,不再需要大堆的重载了。


搜索的时候发现有很多大牛讨论过这个问题了,受益匪浅
比如 C#的设计缺陷(2):不能以 void 作为泛型参数

1. tuple and record

现在有一些键值对,它们和给定 record 的项一一对应,如何转换成 record?

-record(test, {
    a::binary(),
    b::binary()
}).

KeyValuePairs = [{a, <<"a">>},{b, <<"b">>}].

很基础的问题,我们这样做:

Result = #test{
    a = get_value(a, KeyValuePairs),
    b = get_value(a, KeyValuePairs)
}.

如果 record 有一百个项呢?
重复的写 a = get_value(a, KeyValuePairs) 这样的代码一百次大概会让人怀疑「猿」生吧 :(

虽然 Erlang 并没有提供动态生成 record 的方法,但是我们知道

  • Erlang 的 record 实际上是用 tuple 来表示的,即 #test{a = <<"a">>, b = <<"b">>} 实际上是 {test, <<"a">>, <<"b">>}
  • 所有在运行时对 record 的操作实际上都是对 tuple 的操作
  • Result#test.a 实际上是 tuple 的 index
  • 可以使用 record_info(fields, record) 获取 Record 的 fields 信息

所以我们可以这样

Result = list_to_tuple([test |
    [get_value(X, KeyValuePairs) || X <- record_info(fields, test)]]).

Result#test.a.
%% <<"a">>

2. record_info

很容易想到,我们要是把处理函数抽象出来,不是多了一个 kvpairs_to_record 的接口了么?

-spec kvpairs_to_record(kvpairs(), atom()) -> rec().
kvpairs_to_record(KeyValuePairs, Record) ->
	list_to_tuple([Record |
        [get_value(X, KeyValuePairs) || X <- record_info(fields, Record)]]).

很遗憾,行不通。编译的时候会报出 illegal record info 错误。

WTF?

  • record_info 并不是一个通常意义上的 BIF,它不能接受变量
  • 其原因在于 record structure 只存在于编译期,在运行时是不可见的,编译完成后,record 就已经被表示成为 tuple 了,自然没有办法在运行时再获取 record info 了

所以你只能这么「曲线救国」了

kvpairs_to_record(KeyValuePairs, Record, RecordInfo) ->
	list_to_tuple([Record | [get_value(X, KeyValuePairs) || X <- RecordInfo]]).

Result = kvpairs_to_record(KeyValuePairs, test, record_info(fields, test)).

3. macro and record

所以就这样放弃了?
当然不,为了「代码洁癖」我们可以「不择手段」。
考虑到 define macro 也是编译期的,我们可以这样 trick

-module(test).
-export([do/0]).

-define(fuxk(Record, Val),
    fun() ->
        list_to_tuple([Record | [get(X, Val)
            || X <- record_info(fields, Record)]])
    end
).

-record(test, {
    a :: binary(),
    b :: binary()
}).

do() ->
    KV = [{a, <<"a">>},{b, <<"b">>}],
    Result = ?fuxk(test, KV)(),
    Result#test.a.
    % <<"a">>

get(Key, KeyValuePairs) ->
    proplists:get_value(Key, KeyValuePairs, undefined).

Goodness gracious - it works!

4. beam and record

当然像上面那样写实际上也没有好多少,依然还是不完美。
如果一定需要在运行时得到 record info 呢?
比如我们热升级代码,需要更新 record 定义怎么办?

幸好,record structure 会被写入到 beam 中,我们只需要 load beam 然后解析它,还是可以达到运行时获取 record info 的效果的。
具体实现可以参考 https://github.com/esl/parse_trans

当然,除非知道自己在做什么,否则不推荐这么做。

5. 最后

实际上我很好奇为什么 Erlang 不提供运行时访问 record structure 呢?信息已经存在于 beam 中了,实现一下不难吧。
最后,如果不需要考虑兼容,推荐使用 map 来替代 recordmap 在运行时数据结构可见并且可以增删成员。

mptt

1. 预排序遍历树算法

  • mptt (Modified Preorder Tree Traversal)1
  • 优点
    查询效率高,只需要一次查询即可获得层级结构中某个节点的所有子节点,无需递归查询
  • 缺点
    插入、删除、移动节点效率较低
  • 适用
    在传统关系数据库中实现层级树结构
    • 读压力 > 写压力, mptt 算法可以提高效率
    • 写压力 > 读压力,使用传统的邻接表 (adjacency list model)

2. 增删查改

  • Create

    • 假设增加的节点为 c, 该节点前一节点为 p
    • 节点 c 左值为 p 的右值 +1,右值为 p 右值 +2
    • 所有左值大于节点 c 的左值的节点,其左值均 +2
    • 所有右值大于节点 c 的右值的节点,其右值均 +2
    • 写入节点 c 到数据库
    SELECT @cRight := rgt FROM mptt	WHERE name = 'p';
    UPDATE mptt SET rgt = rgt + 2 WHERE rgt > @cRight ;
    UPDATE mptt SET lft = lft + 2 WHERE lft > @cRight ;
    INSERT INTO mptt(name, lft, rgt) VALUES('c', @cRight+ 1, @cRight+ 2);
    
  • Read

    • 查询节点 c 的子节点:

      • 查询所有左值大于 c 的左值且右值小于 c 的右值的节点

        SELECT * FROM mptt WHERE lft BETWEEN @cLeft and @cRight;
        
    • 查询节点 c 的父节点:

      • 查询所有左值小于 c 的左值且右值大于 c 的右值(或左值)的节点

        SELECT * FROM mptt WHERE lft < @cLeft and rgt > @cLeft;
        
    • 节点 c 的子节点个数:

      • (c.right - c.left - 1) / 2
  • Update
    移动节点即:

    • 删除节点
    • 在指定位置新增节点
  • Delete

    • 删除节点 c
    • 所有右值大于 c 右值的节点,右值 -2
    • 所有左值大于 c 左值的节点,左值 -2
    DELETE FROM mptty WHERE lft BETWEEN @cLeft AND @cRight;
    UPDATE mptt SET rgt = rgt - 2 WHERE rgt > @cRight;
    UPDATE mptt SET lft = lft - 2 WHERE lft > @cLeft;
    

3. 重建树结构

很容易推断,对排序好的 mptt tree,仅需要一次遍历,即可根据所有节点的左右值记录重建树结构
以 python 为例:

# Node class
class Node(object):

    def __init__(self, left, right):
        super(Node, self).__init__()
        self.left = left
        self.right = right
        self.depth = 1
        self.children = []

 # arg: Node List
 def rebuild(l):
		# 节点按左值排序,即遍历顺序
        l.sort(key=lambda x: x.left)

		# 使用列表暂存每层子树的父节点
        # 如 pi[0] 表示第 2 层的节点的父节点在 l 中的 index
        pi = [0]

        for i, c in enumerate(l):
            if c.left != 1:
                p = l[i - 1]

                # 使用 c 表示此节点,p 表示 c 的前一节点
                # 如果连续的两个节点 c 和 p 的左值增加幅度为 1,则说明其深度增加了 1
                # 且 p 为 c 及 c 的兄弟节点的父节点
                if c.left == p.left + 1:
                    c.depth = p.depth + 1
                    if c.depth - 1 > len(pi):
                        pi.append(i - 1)
                    else:
                        pi[c.depth - 2] = i - 1

                # 如果 c 的左值大于 p 的父节点的右值,则说明 p 与 c 并非兄弟节点
                # 并可以计算出两节点的深度差为 c 的左值与 p 的右值之差减 1
                elif c.left > l[pi[p.depth - 2]].right:
                    c.depth = p.depth - (c.left - p.right - 1)

                # 不满足以上两个条件,说明 c 是 p 的兄弟节点
                else:
                    c.depth = p.depth

			    # 将 c 作为 pi 中记录的父节点的子节点
                l[pi[c.depth - 2]].children.append(c)

        return l

Update

完整代码及生成 Json 和基于 D3.js2 的树状图:
https://gist.github.com/caoyue/704e472215af29b08a27

对这些概念头疼了很久,尝试简单的整理下,不确切的地方欢迎指正~

1. Unicode

  • Unicode 是一个字符集,而不是一种编码方案
  • 简单来说 Unicode 是希望给地球上每一个字符一个数字编号,从而解决不同编码之间不统一的问题
  • Unicode 是没法直接拿来用的,我们使用的是它的编码方案

2. 编码方案

  • 通常使用的 UTF-8UTF-16 等等都是 Unicode 的编码方案
  • 所谓编码方案就是按一定的规则对 Unicode 的字符编号进行编码
  • 当然不同的编码的同一个字符,最后解析成 Unicode 字符编号都是一样的

3. 字体与 Unicode

  • 计算机使用字符的 Unicode 编号去寻找字体内的字符
  • 字体内部的特殊数据结构存储了 Unicode 编号和字符的对应关系

4. 例子

  • 汉字 的 Unicode 编号 10 进制为 26376
  • Unicode 编号表示为 16 进制 是 U+6708
  • 在 python 中用 u"\u6708" 表示
  • 在 UTF-8 中的编码是 0xE6 0x9C 0x88 ,使用了 3 个 Byte 来表示

5. UTF-8 和 Unicode 转换

  • Unicode 转 UTF-8

    • 汉字 的 Unicode 是 26376,转换为二进制是 1100111 00001000
    • 根据值大于 0x800 小于 0x10000 可以判断为三字节存储
    • 将 Unicode 二进制从低位往高位取出二进制数字,每次取 6 位,并按一定的规则进行填补

    转换

    110 011100 001000
    11100110 10011100 10001000
    0xE6 0x9C 0x88

  • UTF-8 转 Unicode
    同理进行逆运算即可

6. 遗留编码

  • ASCIIGB 2312Big5GBKGB 18030 这些都属于遗留编码方案
  • GB 2312 通常认为是字符集编码方案一体的
  • 将 GB 2313 编码转换为 Unicode 编号,需要通过转换表查询,无法像 UTF-8 一样直接根据编码规则转换
  • 2015-04-28

6. 编译并运行程序

  • (略)

7. 并发

  • 机制
    • Erlang 程序由成百上千个 Process 组成,这些 Process 之间可以互发消息
    • Process 能否接收到或者理解消息是不确定的,要知道结果必须向该 Process 发送消息询问并等待
    • Process 之间可以互相 Link ,当 Process 消亡时与之相连的 Process 会收到消息

8. 并发编程

  • 并发原语

    • Pid = spawn(Module, FuncName, Args)
      创建一个新的 Process,用于对 Func 求值,并返回该 Process 的 pid
    • Pid ! Message
      • 向指定 Pid 的 Process 发送消息,返回值为 Message 本身
      • 消息发送是异步的,无需等待即可进行其他操作
    • receive ... end
      • 接收一个发给当前进程的消息
    • self()
      获取自己的 pid
  • 注册进程

    • register(AnAtom, Pid)
    • unregiseter(AnAtom)
      进程死亡时会自动 unregiseter
  • 编写并发程序的一般模式

    -module (concurrency).
    -compile(export_all).
    
    start() ->
        spawn(?MODULE, loop, []).
    
    rpc(Pid, Request) ->
        Pid ! {self(), Request},
        receive
             {Pid, Response} ->
                 {Pid, Response}
         end.
    
    loop(X) ->
        receive
            {From, Any} ->
                From ! {self(), "Received!"},
                io:format("Received: ~p~n", [Any]),
                loop(X)
        end.
    
    %% run in erlang shell
    Pid = concurrency:start().
    %% <0.33.0>
    concurrency:rpc(Pid, "test!")
    %% Received: "test"
    %% {<0.56.0>,"Received!"}