I code it

Code and Life

穷人的持续集成与持续交付(上)

服务器端应用的持续交付

本文将使用一些免费的服务来为你的项目搭建持续交付平台,这些服务包括

  • 持续集成环境
  • 持续部署环境
  • 服务端应用托管

以及一些可以用于本地开发使用的开源工具如:

除此之外,我们在过程中编写的脚本还可以用以本地构建,如果你的团队中正好已经有CI工具/CD工具,将这些脚本集成进去也是一件非常容易的事情。

heroku real time log

背景知识

软件的度量

传统的管理方法论,在软件开发这个领域来说基本上是不工作的。软件项目的不确定性使得人们畏惧,管理者希望通过一些数字,指标来让自己感到某种虚幻的“掌控感”。软件行数,测试覆盖率,代码故障率等数字的名声基本上已经很糟了,经常有人拿来讽刺那些追求虚幻掌控感的“领导”。

但是有一个数字,即使最顽固的“自由主义者”也会认为是有意义的,那就是周期时间(cycle time)。简而言之,就是一个需求从产生到最终上线所需要的时间。其中包括了需求分析,设计,编码,测试,部署,运维等活动,可能还会包含后续的监控。

其实不论是瀑布模型,还是迭代开发的方式,或者其他的方法论,周期时间的缩短都是至关重要的。而具体到周期内,单纯的开发时间变长或者测试时间变长都无关紧要。比如项目A的开发时间是测试时间的2倍,项目B则恰恰反过来,这并不能说A做的比B好,真正有意义的是A的周期时间是否比B更短。

单纯改善项目过程中的某一个阶段的时间,可能并不能达到预期的目的。局部优化并不一定会带来全局的优化。换言之,通过某些策略来提高软件测试的效率未必能减少周期时间!

持续交付

传统情况下,企业要进行软件开发,从用户研究到产品上线,其中会花费数月,甚至数年(我的一位印度同事给我聊起过,他的上家公司做产品,从版本启动到版本上线需要整整两年时间!)。而且一旦软件需求发生变更,又有需要数月才能将变更发布上线。除了为变更提交代码外,还有很多额外的回归测试,发布计划,运维部门的进度等等。而市场机会千变万化,在特定的时间窗口中,企业的竞争者可能早已发布并占领了相当大的市场份额。

在软件工程领域,人们提出了持续交付(continuous delivery)的概念,它旨在减少周期时间,强调在任何时刻软件都处于可发布状态。采用这种实践,我们可以频繁,快速,安全的将需求的变化发布出来,交由真实世界的用户来使用,在为用户带来价值的同时,我们也可以快速,持续的得到反馈,并激励新的变化产生(新的商业创新,新的模式等)。

持续交付包含了自动化构建,自动化测试以及自动化部署等过程,持续改进开发流程中的问题,并促进开发人员,测试人员,运维人员之间的协作,团队可以在分钟级别将变更发布上线。

持续交付相关技术及实践

  • 版本控制(配置管理)
  • 持续集成CI
  • 自动化测试
  • 构建工具及构建脚本
  • 部署流水线

团队通过版本控制来进行协作,所有的代码会在持续集成环境中编译,代码静态检查/分析,自动化测试(还可能产生报告等)。除此之外,CI还还需要有自动化验收测试,自动化回归测试等。

持续交付则更进一步,它将环境准备,持续集成,自动化部署等放在了一起。通过全自动(有些过程可以设置为手动,比如发布到产品环境)的方式,使得软件可以一键发布。如果上线后发现严重defect,还支持一键回滚的机制(其实就是将之前的一个稳定版本做一次发布,由于发布流程已经经过千锤百炼,所以发布本身就变得非常轻松,安全)

这篇文章中,我们会使用git+github作为版本控制工具,travis-ci作为持续集成环境,gradle作为构建工具,Heroku作为应用的部署环境。这些工具都是免费服务,如果你需要更高级的功能(比如更多的并发数,更大的数据库),则可以选择付费套餐。不过对于我们平时的大部分side project来说,免费服务已经足够。

实例

我在《前后端分离了,然后呢?》这篇文章中,提到了一个叫做bookmarks的应用,这个应用是一个前后端分离的非常彻底的应用。

我们这里会再次使用这个应用作为实例,并采用不同的两个免费服务(travis-cisnap-ci)来完成持续部署环境的搭建。

bookmarks服务器

bookmarks-server是一个基于spring-boot的纯粹的API,它可以被打包成一个jar包,然后通过命令行启动运行。在本文中,我们我们将会将这个server部署到heroku平台上。

首先需要定义一个Procfile,这个是我们应用的入口,heroku根据这个文件来明确以何种方式来启动我们的应用:

1
web: java -Dserver.port=$PORT -jar build/libs/bookmarks-server-0.1.0.jar --spring.profiles.active=staging

由于我们在本地使用的使用mysql,而heroku默认的是postgres数据库,因此需要在application.yml中额外配置

1
2
3
4
5
6
7
8
9
10
11
12
13
spring:
  profiles: staging

  datasource:
    driverClassName: org.postgresql.Driver
    url: ${JDBC_DATABASE_URL}
    username: ${DATABASE_USER}
    password: ${DATABASE_PASS}

  jpa:
    database_platform: org.hibernate.dialect.PostgreSQLDialect
    hibernate:
      ddl-auto: update

有了这些配置后,我们需要创建一个heroku应用:

1
2
$ heroku create
Created http://quiet-atoll-8237.herokuapp.com/ | git@heroku.com:quiet-atoll-8237.git

创建之后,我们可以在界面上对这个应用进行一些配置(当然,也可以通过命令行,具体参看heroku help)。为了支持数据库,需要为我们的应用添加一个postgres的AddOn。添加之后,heroku会为我们提供一个postgres的连接地址,格式大概是这样:

1
postgres://username:password@host:port/database

然后我们需要在Heroku的配置界面中配置一些环境变量:

heroku env config

这样,当应用部署到Heroku上之后,我们的应用就可以读到这些配置了(注意application.yml中的环境变量JDBC_DATABASE_URL)。

搭建持续集成环境

持续集成环境,这里我们选用最简单的travis-ci,它可以很容易的与github集成。

  • 在项目X中定义一个.travis.yml的文件
  • 将你的代码push到github上
  • 绑定github帐号到travis
  • travis中启用项目X

这个.travis.yml因项目而异,我们这里的项目是spring-boot,所以只需要指定java即可:

1
language: java

如果是java项目,并且项目中有build.gradletravis-ci会自动执行gradle check任务。

自动化部署

当CI运行成功之后,我们需要travis-ci帮我们将应用程序发布到heroku上,这时候需要做一些修改。最简单的方式是直接安装travis-ci的命令行工具到本地:

1
$ gem install travis -v 1.8.0 --no-rdoc --no-ri

然后通过herokuauth:token命令获得heroku的token,在加密并写入.travis.yml

1
2
3
4
$ heroku auth:token
00xxxxxxxxxxxxx55d11dbd0cxxxxxxxxxxfe067

$ travis encrypt 00xxxxxxxxxxxxx55d11dbd0cxxxxxxxxxxfe067 --add

当然可以合并为一条命令:

1
$ travis encrypt $(heroku auth:token) --add

将加密过的token存入.travis.yml文件。最后的结果大致如下:

1
2
3
4
5
6
language: java
deploy:
  provider: heroku
  api_key:
    secure: ...
  app: quiet-atoll-8237

注意此处的app,正是我们的App的名字。另外,还需要给build.gradle添加一个名叫stage的task,travis在deploy时需要这个task

1
2
3
task stage {
    dependsOn build
}

travis deploy

这样,我们只需要在本地的一个提交,一切都会自动化起来:

  • travis会执行gradle check
  • gradle check会编译并运行自动化测试
  • travis会部署应用到heroku
  • heroku会自动重启服务

我们可以在本地进行简单的测试(注意此处我们的staging环境的URL):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
$ curl https://quiet-atoll-8237.herokuapp.com/api/feeds -s | jq .
[
  {
    "id": 1,
    "url": "http://icodeit.org/2016/01/how-to-summarize-privious-project/",
    "title": "如何持久化你的项目经历",
    "author": "icodit.org",
    "summary": "通常来说,下项目总是一件比较高兴的事(大部分团队还会一起吃个饭庆祝一下)。",
    "publishDate": "2016-01-07"
  },
  {
    "id": 2,
    "url": "http://icodeit.org/2015/11/get-started-with-reflux/",
    "title": "你为什么应该试一试Reflux?",
    "author": "icodit.org",
    "summary": "React在设计之初就只关注在View本身上,其余部分如数据的获取,事件处理等,全然不在考虑之内。",
    "publishDate": "2016-01-09"
  }
]

完整的代码在这里

其他

CI monitor

node-build-monitor是一个非常容易配置,使用的CI monitor,我们只需要进行简单地配置,就可以将travis的状态可视化出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
  "monitor": {
    "interval": 2000,
    "numberOfBuilds": 12,
    "debug": true
  },
  "services": [
    {
      "name": "Travis",
      "configuration": {
        "slug": "abruzzi/bookmarks-server"
      }
    }
  ]
}

不过这个工具会在有网络异常时自动终止,我们可以通过一个简单的脚本来在它终止时自动重启:

1
2
3
4
5
6
#!/bin/bash

until node app/app.js
do
    echo "restarting..."
done

CI Monitor

小结

通过travisheroku这样的免费服务,我们就可以轻松的将自己的项目做到持续集成+持续交付。我们后端的服务相对来说是比较容易的,但是涉及到一个前后端分离的架构,如何做到静态内容的托管,打包,部署,并和后端API集成起来,我会在下一篇文章中详细解释。

如何持久化你的项目经历

下项目之后

通常来说,下项目总是一件比较高兴的事(大部分团队还会一起吃个饭庆祝一下)。这里面既有终于摆脱了厌烦了的技术栈的解脱感,也有对新项目/新技术的向往,可能还有些在旧项目中做的不太满意的事情,可以在新项目重头再来的期望。

可能有点老生常谈了,不过这里我想说说下项目后如何做总结的事儿。对上一个项目的总结,其重要程度可能要远远超过你的想象。我是在2014年初,在一个客户现场的一个会议室和一位同事谈我的Annual Review的时候,才意识到这个问题的。

Annual Review会回顾我们过去一年的项目经历,有哪些方面的进步,同时也会展望未来的计划。但是这其中有几个问题:第一个问题是以年为单位的Review粒度太粗,有些经历已经淡忘,也有人可能一年会换好几个项目;第二个问题是对于大多数人来说,展望未来是一件比较容易的事儿,每个人或多或少都会有一些计划(比如学会前端的某些技术,尝试一些DevOps方面的工作,或者了解一下大数据等等);但是对于回顾过去,我们其实并不擅长;最后一个问题是即使做了回顾,回顾的层次非常浅,作用并不大。

说到回顾过去,更多时候我们关注的是从项目中学到了什么样的新技术,这种浅层次的回忆和记流水帐是容易的,但是对于我们的成长并不会有太大的收益。真正会为帮助我们在将来的项目中做决策,甚至会影响我们学习效率,解决问题能力的是:深度回顾

深度回顾练习

深度回顾可以帮助我们梳理知识,将实际的案例归纳总结为实际可用的知识。要获得这种能力,需要做一些针对性的练习。根据我自己的经验,这些练习大约可以归为3类,难度依次增加。

项目上的直接经验

这个练习比较简单,就是问问自己:“我在项目里学到了什么?

要回答这个问题是很容易的,项目中用到的技术如模板引擎,前端框架,自动化测试套件,build工具等等,总结这些内容的过程,对于我们的PS来说都是“自动”发生的,几乎不需要付出额外的efforts。这些回顾、总结可以帮助我们成为一个“熟手”,即当下一次遇到相同或者类似的场景时,我们可以很容易直接应用这些经验。

更进一步,再问问自己在项目中的其他收获。比如客户关系处理的经历,团队建设的经验,甚至是写英文邮件的技巧等等方面,看看做的有没有问题,有没有提升的可能?

人类最牛逼的技能是:可以审视自己的行为。也就是站在旁观者的角度来看待自己的行为,随波逐流式的在各种琐事中沉浮事实上无法得到提升的。可以经常性的将自己置身事外,以一个旁观者的角度来审视自己做过的事情。并从中找出做得好的地方和不足的地方,然后自己给过去的自己一些建议,并记录下来。这些刻意的练习会帮助你养成回顾,从经验中学习的习惯,而这个习惯正是一个人区别于另一个人的绝对“捷径”。

练习讲故事

这个练习是,假想你遇到了一个同一个办公室的同事,他对你刚做完的这个项目很感兴趣,你来给他描述一下这个项目。描述的内容包括但不限于这些方面:

  • 项目的背景介绍
  • 该项目以何种方式,为那些用户,带来了什么样的价值?(business model是什么)
  • 该项目的实际用户数量是什么级别?
  • 项目的部署,运维是如何操作的?
  • 项目的监控是怎样做的?
  • 当遇到系统故障,项目组是如何反应的?

能把一件事情描述清楚是一件非常了不起的能力。我见过很多的程序员,写起代码来好不含糊,但是却很难将一件简单的事情讲清楚。我们当然要提防那些夸夸其谈,华而不实的“嘴子”,但是也至少得要求自己做到清晰,准确的将自己经历过的事情描述清楚。

描述项目背景需要至少需要交代这样一些内容:客户是谁,最终的消费者是谁,项目以何种方式运作(离岸交付,本地,onsite,咨询,培训等),我们帮助客户为消费者带来了什么样的价值。客户的商业模式是什么,在我们周围有哪些类似的项目。

business canvas

即使在技术方面,也有很多被Dev忽略掉的信息,比如项目在产品环境中如何部署,数据中心建在何处,客户如何运维、监控等。实际的发布周期如何,发布流程如何,客户的内部论坛上都会有很多的这样的信息,但是很少有人关注。从一个项目roll off的时候,这些信息即使做不到了若指掌,至少也能描述清楚,否则难免有些“入宝山而空回”的遗憾。

回顾项目中的挑战

从简单的CRUD系统,到复杂的分布式计算,从企业内部的管理系统,到支持高并发、要求实时处理的交易平台,每个项目都会遇到一些挑战。除了技术上的挑战之外,还有陈旧而无文档的代码库,复杂的业务场景,不配和的客户接口人等等。挑战无处不在,那么作为项目中的一员,你是如何应对这些挑战的呢?最后又是如何解决的?

现实世界是一个充满了trade off的世界,我们需要做种种权衡,代码测试覆盖率和交付压力,性能和客户能负担的机器实例数量,框架A和框架B的优劣等等。我们在采取这个方案的时候,只能舍弃其他方案,由于谁也无法在事先准确预料采取某个方案一定是对的,那么在一个失败的方案背后,其实也是一个很好的教训,至少可以为未来的决策提供帮助。

  • 遇到的最大的挑战是什么?
  • 这个挑战是如何被解决的?
  • 如果有机会重做,你会如何考虑?

其他练习

这里列出了一些我常用的,辅助性的练习。它们可以帮助你更好的梳理项目上学到的技能、知识,并且转换成你自己的知识。这些练习未必一定要等到项目结束之后才做,事实上它们都可以应用在日常的工作中。

  • 记笔记
  • 写博客
  • 在办公室内演讲
  • 去社区贡献话题

很多人都会记笔记,但只有一小部分的人在记录之后会持续翻阅。很多人会使用Evernote/印象笔记之类的工具将一些临时的想法,问题的思路,知识点的细节等记录下来,但是仅仅记录是不够的,笔记需要不断的检索、整理、提炼、修正、总结和归纳。在不断的加工之后,这些笔记可能会得到沉淀,并升华形成一些更有意义的内容(比如个人博客,或者可以发表到InfoQ/IBM DeveloperWorks平台上的文章等)。

除了记录笔记之外,写博客也是一种很好的总结形式。通过将素材不断充实、整理、完善,最终形成一个可供别人直接消费的文章,不但可以锻炼到总结能力,还可以很好的提升表达能力,而且可以帮助你将已有的知识体系化。如果你的博客写成了系列,也很容易通过Gitbook等将其发布为一本电子书,从而影响更多人(说不定还可以赚点咖啡钱)。

写博客/电子书,终究是书面形式的。事实上一个人可以很容易的通过文字将自己的实际情况隐藏起来。举个极端的例子:如果有足够的动机(比如公司的KPI要求),即使不熟悉某种语言/工具,仅仅通过Google,一个人也可以通过这种“作弊”的方式写出一篇“专家级”的文章。但是对于演讲这种面对面的形式,则基本上无法作弊,从而也更具有挑战性。另一方面,对于一个新的知识、技能,自己掌握是一回事儿,要讲出来让别人也能听懂,并从中收益,则完全是另外一回事儿。作为咨询师,语言表达(包括书面和演讲)能力的重要性勿庸赘言。整理知识,并归纳为演讲,会帮助你将体系化后的知识更好的表达出来。

在办公室里讲session有一定的挑战,但受众毕竟是“自己人”,压力相对会小一些(比如在ThoughtWorks,我们非常鼓励员工为其他人讲session,具体可以参看我的这篇文章)。要在社区中演讲则要面临更大的挑战,通过将话题不断锤炼,不断归纳,最终形成可以在社区分享的话题,则不但可以提高内容的质量,也可以更好的锻炼表达能力和临场应变能力。

xian community

不过归根结底,这些活动的重要输入还是对之前项目中的知识、经历的深度回顾。

总结

从项目上下来之后,需要深入思考并总结之前的经验,这种深入思考会帮助你建立比较完整的知识体系,也可以让你在下一项目中更加得心应手,举一反三。如果只是蜻蜓点水般的“经历”了若干个项目,而不进行深入的总结和思考,相当于把相同的项目用不同的技术栈做了很多遍一样,那和我们平时所痛恨的重复代码又有什么不同呢?

我的2015

2015年总结

2015年在不经意间就过去了。又是一年。按照惯例,我会在年末回顾一下这一年自己的进步,收获以及一些感慨(牢骚)。然后对来年做一点展望,看看什么地方可以做的更好。

项目经历

今年基本上经历了三个项目,性质也都不一样:

  • 海外交付
  • 国内交付
  • 国内售前

3月前的项目以及没有什么印象了,依稀觉得项目上的所有实践都是“错”的,可能由于太过与荒诞,所以大脑自行将这段抹去了。

4月到6月在深圳的一个国内交付项目上,交付压力还挺大。不过也是在这个项目上,非常直接的体会到了其他角色的不容易。无论是客户的接口人,客户的项目经理,客户的领导,我们的开发,我们的UX,项目经理,还有交付的lead,所有人都不容易。

《项目经理是大傻逼吗》这篇文章就是为了纪念这个项目,或者说是被这个项目驱动出来的。

6月之后回到办公室,在一个海外交付项目上。说是一个项目,中间其实换了6,7个不同的工作内容(出钱的是同一个客户而已)。总之一片混乱,所幸我们在10月前就结束了和这个客户的合作。这个项目事实上除了锻炼项目上人的耐心外,基本毫无益处。甚至对于很多毕业生来说,是深刻的伤害。

10月之后,我难得的在beach上待了下来,而且一待就是3个月。中间在一个联合国的项目上工作了2周,然后就是为另外一个咨询项目准备了几周方案。当然,闲是不可能闲着的。在beach上,如果不出意外,肯定会比项目上更忙!比如打黑工啊,内部什么系统的改进啊,总是有好多事情。

由于有一些本地的项目机会,而我又不在具体项目上,就来做这个售前的角色。帮助客户梳理需求,分析问题,设计方案,计算工作量等等。但是这个过程往往循环往复,一轮接着一轮,在合同确认之前,需要很多次讨论和交流。这应该不会是我自己的一个方向,在项目上写代码,培养新人,分享自己的学习所得,和他人一起进步,是我自己比较有热情的方向。

技术方面

在海外交付项目上,乏善足陈,项目中用到的也是非常厚重,已经至少10年的技术。通常来看,这样的大组织,没有人对要做的事情真正关心。好不容易遇到一个特别靠谱的人,结果我们的项目又结束了。国内项目上倒是有很多有意思的东西:

  • 如何在前端代码中很好的使用MVC
  • 流畅的前端开发模式
  • 如何做前端的测试

上面这三点,我希望可以找时间整理出一本电子书,可以让没有工程级做过项目的前端工程师能有一个参考。

另一方面,由于项目的压力,和项目人员的特殊性(开发就俩人,一个做前端,一个做后端,要集成就pair一下),所以很多实践都没有应用,比如结对,自动化测试等,做的都不够好。虽然我们很推崇,强调CI/CD的实践,但是当和客户的后端系统集成时,就各种悲剧。

联合国的项目上,技术栈比较新颖,上一家的技术人员使用了他们当时能找到的所有酷炫的新技术,并用在了项目中,然后他们公司被收购。留给我们的在今年来看,依然是比较新的

  • React
  • Reflux
  • ES6
  • mocha/chai

而在国内售前,基本上没有写过一行代码,更多是更高层次(高不一定是好哦)的工作。确认需求,估算工作量,确定方案(前后端测试,开发方式,部署策略,自动化测试等等)。

2016年,我希望可以多学习一些具体的编程知识,比如:

  • mongodb
  • 数据分析,数据挖掘
  • 容器技术如docker

书籍

今年读了一些技术方面的书,更多的则是一些非技术类的。《自私的基因》是在2012年11月去墨尔本时,在广州白云机场买的,路上10个小时,读了几页。直到2015年才又拿起来,读了两章左右,基本上颠覆了我之前建立的对“进化论”的认识。

另外读了一些科普类的,比如《哲学家在干了些什么》,《上帝掷骰子吗》等,又扫了一次盲。再就是一些佛教相关的书籍,《西藏生死书》,《能断:金刚经》,《正见》等,人生观和价值观得到了刷新。

技术类的,主要是一些与具体技术关系不太大的,比如《恰如其分的软件架构》,《企业级应用架构模式》,《发布!》,《实例化需求》,《持续发布》之类。

虽然竣工于2014年,但是我的一本著作和一本译作都是2015年才发布出来,那就算作2015年的吧:

社区

今年在深圳的时候,有幸和ThoughtWorks的首席科学家马丁.福勒在同一次活动中作为讲师。

shenzhen

回到西安之后,在本地社区中还讲过一个前端工程师需要掌握的技能列表的session

xian

2016年希望可以做一些更加深入的topic,以及一些更有意思,可以帮助到更多已经在路上的工程师们。

People Development

这个不知道如何翻译了,但是确实做了一些具体的事情:

  • 给我的sponsee们安排了读书会
  • 组织了一次《编写可维护的JavaScript》的workshop
  • 组织sponsee来做一个side project
  • 组织《Web开发实战》的workshop

我自己总结出来了一套组织workshop的方式,其实很简单:

  1. 做好计划,做好课表,做好课件
  2. 找学员,同时从学员里找出有基础,而且有意愿接着run workshop的人
  3. 讲课,收集feedback,并改进课表,课件
  4. 将run workshop的任务传递给那些有基础,而且有意愿接着run workshop的人

2016年希望可以找到更多的候选人,并帮助他们成为更好的讲师,教练。

总的感悟

总体的感觉是很忙,各种事情千头万绪,没有了清晰的一个vision,也没有了指导,自身的发展方向也变得模糊起来。一部分原因可能是压力的方向变了,在项目上的单一的压力下总是可以找出一些事情来的,但是在项目之外,各种可见不可见的压力都慢慢浮现。对于这些隐形的,不可见的,但是又可以感受到的压力,需要认真思索对策,然后想办法搞定。

学习上有点“半瓶醋”的感觉,很多技术都接触了,但是不见得深入。缺乏空杯心态,这个是2016年希望自己能改进的地方。另一方面,希望在一个IT系统的架构层面有一些积累,以便在考虑项目的问题时,能够更加全面,而不至于陷入细节,只见树木,不见森林。

2016,当然还会很忙,只是希望忙的过程中可以多一些快乐。

使用graphviz绘制流程图(2015版)


2015年11月10日更新 在实践中,我又发现了一些graphviz的有趣的特性,比如时序图rank以及图片节点等。在这里一并更新。

前言

日常的开发工作中,为代码添加注释是代码可维护性的一个重要方面,但是仅仅提供注释是不够的,特别是当系统功能越来越复杂,涉及到的模块越来越多的时候,仅仅靠代码就很难从宏观的层次去理解。因此我们需要图例的支持,图例不仅仅包含功能之间的交互,也可以包含复杂的数据结构的示意图,数据流向等。

但是,常用的UML建模工具,如Visio等都略显复杂,且体积庞大。对于开发人员,特别是后台开发人员来说,命令行,脚本才是最友好的,而图形界面会很大程度的限制开发效率。相对于鼠标,键盘才是开发人员最好的朋友。

graphviz简介

本文介绍一个高效而简洁的绘图工具graphvizgraphviz是贝尔实验室开发的一个开源的工具包,它使用一个特定的DSL(领域特定语言): dot作为脚本语言,然后使用布局引擎来解析此脚本,并完成自动布局。graphviz提供丰富的导出格式,如常用的图片格式,SVG,PDF格式等。

graphviz中包含了众多的布局器:

  • dot 默认布局方式,主要用于有向图
  • neato 基于spring-model(又称force-based)算法
  • twopi 径向布局
  • circo 圆环布局
  • fdp 用于无向图

graphviz的设计初衷是对有向图/无向图等进行自动布局,开发人员使用dot脚本定义图形元素,然后选择算法进行布局,最终导出结果。

首先,在dot脚本中定义图的顶点和边,顶点和边都具有各自的属性,比如形状,颜色,填充模式,字体,样式等。然后使用合适的布局算法进行布局。布局算法除了绘制各个顶点和边之外,需要尽可能的将顶点均匀的分布在画布上,并且尽可能的减少边的交叉(如果交叉过多,就很难看清楚顶点之间的关系了)。所以使用graphviz的一般流程为:

  • 定义一个图,并向图中添加需要的顶点和边
  • 为顶点和边添加样式
  • 使用布局引擎进行绘制

一旦熟悉这种开发模式,就可以快速的将你的想法绘制出来。配合一个良好的编辑器(vim/emacs)等,可以极大的提高开发效率,与常见的GUI应用的所见即所得模式对应,此模式称为所思即所得。比如在我的机器上,使用Sublime Text 编辑dot脚本,然后将F7/Cmd-B映射为调用dot引擎去绘制当前脚本,并打开一个新的窗口来显示运行结果:

workspace

对于开发人员而言,经常会用到的图形绘制可能包括:函数调用关系,一个复杂的数据结构,系统的模块组成,抽象语法树等。

基础知识

graphviz包含3中元素,顶点。每个元素都可以具有各自的属性,用来定义字体,样式,颜色,形状等。下面是一些简单的示例,可以帮助我们快速的了解graphviz的基本用法。

第一个graphviz图

比如,要绘制一个有向图,包含4个节点a,b,c,d。其中a指向bbc指向d。可以定义下列脚本:

1
2
3
4
5
6
7
8
9
10
digraph abc{
  a;
  b;
  c;
  d;
 
  a -> b;
  b -> d;
  c -> d;
}

使用dot布局方式,绘制出来的效果如下:

dot-simple

默认的顶点中的文字为定义顶点变量的名称,形状为椭圆。边的默认样式为黑色实线箭头,我们可以在脚本中做一下修改,将顶点改为方形,边改为虚线

定义顶点和边的样式

digraph的花括号内,添加顶点和边的新定义:

1
2
node [shape="record"];
edge [style="dashed"];

则绘制的效果如下:

dot-simple2

进一步修改顶点和边样式

进一步,我们将顶点a的颜色改为淡绿色,并将cd的边改为红色,脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
digraph abc{
  node [shape="record"];
  edge [style="dashed"];
   
  a [style="filled", color="black", fillcolor="chartreuse"];
  b;
  c;
  d;
   
  a -> b;
  b -> d;
  c -> d [color="red"];
}

绘制的结果如下:

dot-simple3

应当注意到,顶点和边都接受属性的定义,形式为在顶点和边的定义之后加上一个由方括号括起来的key-value列表,每个key-value对由逗号隔开。如果图中顶点和边采用统一的风格,则可以在图定义的首部定义node, edge的属性。比如上图中,定义所有的顶点为方框,所有的边为虚线,在具体的顶点和边之后定义的属性将覆盖此全局属性。如特定与a的绿色,cd的边的红色。

以图片为节点

除了颜色,节点还可以使用图片。不过需要注意的是,在使用图片作为节点的时候,需要将本来的形状设置为none,并且将label置为空字符串,避免出现文字对图片的干扰。

1
2
3
4
5
6
7
8
9
10
11
12
13
digraph abc{
  node [shape="record"];
  edge [style="dashed"];
   
  a [style="filled", color="black", fillcolor="chartreuse"];
  b;
  c [shape="none", image="logos/browser-icon-chrome-resized.png", label=""];
  d;
   
  a -> b;
  b -> d;
  c -> d [color="red"];
}

image-node

子图的绘制

graphviz支持子图,即图中的部分节点和边相对对立(软件的模块划分经常如此)。比如,我们可以将顶点c和d归为一个子图:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
digraph abc{

  node [shape="record"];
  edge [style="dashed"];
   
  a [style="filled", color="black", fillcolor="chartreuse"];
  b;
 
    subgraph cluster_cd{
      label="c and d";
      bgcolor="mintcream";
      c;
      d;
    }
 
  a -> b;
  b -> d;
  c -> d [color="red"];
}

cd划分到cluster_cd这个子图中,标签为c and d,并添加背景色,以方便与主图区分开,绘制结果如下:

cluster

应该注意的是,子图的名称必须以cluster开头,否则graphviz无法设别。

数据结构的可视化

实际开发中,经常要用到的是对复杂数据结构的描述,graphviz提供完善的机制来绘制此类图形。

一个hash表的数据结构

比如一个hash表的内容,可能具有下列结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct st_hash_type {
    int (*compare) ();
    int (*hash) ();
};

struct st_table_entry {
    unsigned int hash;
    char *key;
    char *record;
    st_table_entry *next;
};

struct st_table {
    struct st_hash_type *type;
    int num_bins; /* slot count */
    int num_entries; /* total number of entries */
    struct st_table_entry **bins; /* slot */
};
绘制hash表的数据结构

从代码上看,由于结构体存在引用关系,不够清晰,如果层次较多,则很难以记住各个结构之间的关系,我们可以通过下图来更清楚的展示:

hash-datastruct

脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
digraph st2{
  fontname = "Verdana";
  fontsize = 10;
  rankdir=TB;
  
  node [fontname = "Verdana", fontsize = 10, color="skyblue", shape="record"];
  
  edge [fontname = "Verdana", fontsize = 10, color="crimson", style="solid"];
  
  st_hash_type [label="{<head>st_hash_type|(*compare)|(*hash)}"];
  st_table_entry [label="{<head>st_table_entry|hash|key|record|<next>next}"];
  st_table [label="{st_table|<type>type|num_bins|num_entries|<bins>bins}"];
  
  st_table:bins -> st_table_entry:head;
  st_table:type -> st_hash_type:head;
  st_table_entry:next -> st_table_entry:head [style="dashed", color="forestgreen"];
}

应该注意到,在顶点的形状为record的时候,label属性的语法比较奇怪,但是使用起来非常灵活。比如,用竖线”|”隔开的串会在绘制出来的节点中展现为一条分隔符。用<>括起来的串称为锚点,当一个节点具有多个锚点的时候,这个特性会非常有用,比如节点st_tabletype属性指向st_hash_type,第4个属性指向st_table_entry等,都是通过锚点来实现的。

我们发现,使用默认的dot布局后,绿色的这条边覆盖了数据结构st_table_entry,并不美观,因此可以使用别的布局方式来重新布局,如使用circo算法:

circo

则可以得到更加合理的布局结果。

hash表的实例

另外,这个hash表的一个实例如下:

hash-instance

脚本如下:

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
digraph st{
  fontname = "Verdana";
  fontsize = 10;
  rankdir = LR;
  rotate = 90;
  
  node [ shape="record", width=.1, height=.1];
  node [fontname = "Verdana", fontsize = 10, color="skyblue", shape="record"];
  
  edge [fontname = "Verdana", fontsize = 10, color="crimson", style="solid"];
  node [shape="plaintext"];
  
  st_table [label=<
      <table border="0" cellborder="1" cellspacing="0" align="left">
      <tr>
      <td>st_table</td>
      </tr>
      <tr>
      <td>num_bins=5</td>
      </tr>
      <tr>
      <td>num_entries=3</td>
      </tr>
      <tr>
      <td port="bins">bins</td>
      </tr>
      </table>
  >];
  
  node [shape="record"];
  num_bins [label=" <b1> | <b2> | <b3> | <b4> | <b5> ", height=2];
  node[ width=2 ];
  
  entry_1 [label="{<e>st_table_entry|<next>next}"];
  entry_2 [label="{<e>st_table_entry|<next>null}"];
  entry_3 [label="{<e>st_table_entry|<next>null}"];
  
  st_table:bins -> num_bins:b1;
  num_bins:b1 -> entry_1:e;
  entry_1:next -> entry_2:e;
  num_bins:b3 -> entry_3:e;
}

上例中可以看到,节点的label属性支持类似于HTML语言中的TABLE形式的定义,通过行列的数目来定义节点的形状,从而使得节点的组成更加灵活。

软件模块组成图

Apache httpd 模块关系

httpd

在实际的开发中,随着系统功能的完善,软件整体的结构会越来越复杂,通常开发人员会将软件划分为可理解的多个子模块,各个子模块通过协作,完成各种各样的需求。

下面有个例子,是某软件设计时的一个草稿:

idp

IDP支持层为一个相对独立的子系统,其中包括如数据库管理器,配置信息管理器等模块,另外为了提供更大的灵活性,将很多其他的模块抽取出来作为外部模块,而支持层提供一个模块管理器,来负责加载/卸载这些外部的模块集合。

这些模块间的关系较为复杂,并且有部分模块关系密切,应归类为一个子系统中,上图对应的dot脚本为:

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
digraph idp_modules{

  rankdir = TB;
  fontname = "Microsoft YaHei";
  fontsize = 12;
  
  node [ fontname = "Microsoft YaHei", fontsize = 12, shape = "record" ];
  edge [ fontname = "Microsoft YaHei", fontsize = 12 ];
  
      subgraph cluster_sl{
          label="IDP支持层";
          bgcolor="mintcream";
          node [shape="Mrecord", color="skyblue", style="filled"];
          network_mgr [label="网络管理器"];
          log_mgr [label="日志管理器"];
          module_mgr [label="模块管理器"];
          conf_mgr [label="配置管理器"];
          db_mgr [label="数据库管理器"];
      };
  
      subgraph cluster_md{
          label="可插拔模块集";
          bgcolor="lightcyan";
          node [color="chartreuse2", style="filled"];
          mod_dev [label="开发支持模块"];
          mod_dm [label="数据建模模块"];
          mod_dp [label="部署发布模块"];
      };
  
  mod_dp -> mod_dev [label="依赖..."];
  mod_dp -> mod_dm [label="依赖..."];
  mod_dp -> module_mgr [label="安装...", color="yellowgreen", arrowhead="none"];
  mod_dev -> mod_dm [label="依赖..."];
  mod_dev -> module_mgr [label="安装...", color="yellowgreen", arrowhead="none"];
  mod_dm -> module_mgr [label="安装...", color="yellowgreen", arrowhead="none"];
}

状态图

有限自动机示意图

fsm

上图是一个简易有限自动机,接受aa结尾的任意长度的串。其脚本定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
digraph automata_0 {
  size = "8.5, 11";
  fontname = "Microsoft YaHei";
  fontsize = 10;
  
  node [shape = circle, fontname = "Microsoft YaHei", fontsize = 10];
  edge [fontname = "Microsoft YaHei", fontsize = 10];
  
  0 [ style = filled, color=lightgrey ];
  2 [ shape = doublecircle ];
  
  0 -> 2 [ label = "a " ];
  0 -> 1 [ label = "other " ];
  1 -> 2 [ label = "a " ];
  1 -> 1 [ label = "other " ];
  2 -> 2 [ label = "a " ];
  2 -> 1 [ label = "other " ];
  
  "Machine: a" [ shape = plaintext ];
}

形状值为plaintext的表示不用绘制边框,仅展示纯文本内容,这个在绘图中,绘制指示性的文本时很有用,如上图中的Machine: a

OSGi中模块的生命周期图

OSGi中,模块具有生命周期,从安装到卸载,可能的状态具有已安装,已就绪,正在启动,已启动,正在停止,已卸载等。如下图所示:

osgi

对应的脚本如下:

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
digraph module_lc{
  rankdir=TB;
  fontname = "Microsoft YaHei";
  fontsize = 12;
  
  node [fontname = "Microsoft YaHei", fontsize = 12, shape = "Mrecord", color="skyblue", style="filled"];
  edge [fontname = "Microsoft YaHei", fontsize = 12, color="darkgreen" ];
  
  installed [label="已安装状态"];
  resolved [label="已就绪状态"];
  uninstalled [label="已卸载状态"];
  starting [label="正在启动"];
  active [label="已激活(运行)状态"];
  stopping [label="正在停止"];
  start [label="", shape="circle", width=0.5, fixedsize=true, style="filled", color="black"];
  
  start -> installed [label="安装"];
  installed -> uninstalled [label="卸载"];
  installed -> resolved [label="准备"];
  installed -> installed [label="更新"];
  resolved -> installed [label="更新"];
  resolved -> uninstalled [label="卸载"];
  resolved -> starting [label="启动"];
  starting -> active [label=""];
  active -> stopping [label="停止"];
  stopping -> resolved [label=""];
}

其他实例

一棵简单的抽象语法树(AST)

表达式 (3+4)*5 在编译时期,会形成一棵语法树,一边在计算时,先计算3+4的值,最后与5相乘。

ast-calc

对应的脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
digraph ast{
  fontname = "Microsoft YaHei";
  fontsize = 10;
  
  node [shape = circle, fontname = "Microsoft YaHei", fontsize = 10];
  edge [fontname = "Microsoft YaHei", fontsize = 10];
  node [shape="plaintext"];
  
  mul [label="mul(*)"];
  add [label="add(+)"];
  
  add -> 3
  add -> 4;
  mul -> add;
  mul -> 5;
}

简单的UML类图

下面是一简单的UML类图,DogCat都是Animal的子类,DogCat同属一个包,且有可能有联系(0..n)

uml

脚本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
digraph G{
  
  fontname = "Courier New"
  fontsize = 10
  
  node [ fontname = "Courier New", fontsize = 10, shape = "record" ];
  edge [ fontname = "Courier New", fontsize = 10 ];
  
  Animal [ label = "{Animal |+ name : String\l+ age : int\l|+ die() : void\l}" ];
  
      subgraph clusterAnimalImpl{
          bgcolor="yellow"
          Dog [ label = "{Dog||+ bark() : void\l}" ];
          Cat [ label = "{Cat||+ meow() : void\l}" ];
      };
  
  edge [ arrowhead = "empty" ];
  
  Dog->Animal;
  Cat->Animal;
  Dog->Cat [arrowhead="none", label="0..*"];
}

状态图

status-chart

脚本:

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
digraph finite_state_machine {
  rankdir = LR;
  size = "8,5"
  
  node [shape = doublecircle];
  
  LR_0 LR_3 LR_4 LR_8;
  
  node [shape = circle];
  
  LR_0 -> LR_2 [ label = "SS(B)" ];
  LR_0 -> LR_1 [ label = "SS(S)" ];
  LR_1 -> LR_3 [ label = "S($end)" ];
  LR_2 -> LR_6 [ label = "SS(b)" ];
  LR_2 -> LR_5 [ label = "SS(a)" ];
  LR_2 -> LR_4 [ label = "S(A)" ];
  LR_5 -> LR_7 [ label = "S(b)" ];
  LR_5 -> LR_5 [ label = "S(a)" ];
  LR_6 -> LR_6 [ label = "S(b)" ];
  LR_6 -> LR_5 [ label = "S(a)" ];
  LR_7 -> LR_8 [ label = "S(b)" ];
  LR_7 -> LR_5 [ label = "S(a)" ];
  LR_8 -> LR_6 [ label = "S(b)" ];
  LR_8 -> LR_5 [ label = "S(a)" ];
}

时序图

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
digraph G {
    rankdir="LR";
    node[shape="point", width=0, height=0];
    edge[arrowhead="none", style="dashed"]

    {
        rank="same";
        edge[style="solided"];
        LC[shape="plaintext"];
        LC -> step00 -> step01 -> step02 -> step03 -> step04 -> step05;
    }

    {
        rank="same";
        edge[style="solided"];
        Agency[shape="plaintext"];
        Agency -> step10 -> step11 -> step12 -> step13 -> step14 -> step15;
    }

    {
        rank="same";
        edge[style="solided"];
        Agent[shape="plaintext"];
        Agent -> step20 -> step21 -> step22 -> step23 -> step24 -> step25;
    }

    step00 -> step10 [label="sends email new custumer", arrowhead="normal"];
    step11 -> step01 [label="declines", arrowhead="normal"];
    step12 -> step02 [label="accepts", arrowhead="normal"];
    step13 -> step23 [label="forward to", arrowhead="normal"];
    step24 -> step14;
    step14 -> step04 [arrowhead="normal"];
}

rankdir="LR"表示,布局从左L到右R。可以看到,在代码中有{}括起来的部分。

1
2
3
4
5
6
{
    rank="same";
    edge[style="solided"];
    Agency[shape="plaintext"];
    Agency -> step10 -> step11 -> step12 -> step13 -> step14 -> step15;
}

每一个rank="same"的block中的所有节点都会在同一条线上。我们设置了所有的线为虚线,但是在该block中,将线改为solided

seq

附录

事实上,从dot的语法及上述的示例中,很容易看出,dot脚本很容易被其他语言生成。比如,使用一些简单的数据库查询就可以生成数据库中的ER图的dot脚本。

如果你追求高效的开发速度,并希望快速的将自己的想法画出来,那么graphviz是一个很不错的选择。

当然,graphviz也有一定的局限,比如绘制时序图(序列图)就很难实现。graphviz的节点出现在画布上的位置事实上是不确定的,依赖于所使用的布局算法,而不是在脚本中出现的位置,这可能使刚开始接触graphviz的开发人员有点不适应。graphviz的强项在于自动布局,当图中的顶点和边的数目变得很多的时候,才能很好的体会这一特性的好处:

complex

比如上图,或者较上图更复杂的图,如果采用手工绘制显然是不可能的,只能通过graphviz提供的自动布局引擎来完成。如果仅用于展示模块间的关系,子模块与子模块间通信的方式,模块的逻辑位置等,graphviz完全可以胜任,但是如果图中对象的物理位置必须是准确的,如节点A必须位于左上角,节点B必须与A相邻等特性,使用graphviz则很难做到。毕竟,它的强项是自动布局,事实上,所有的节点对与布局引擎而言,权重在初始时都是相同的,只是在渲染之后,节点的大小,形状等特性才会影响权重。

本文只是初步介绍了graphviz的简单应用,如图的定义,顶点/边的属性定义,如果运行等,事实上还有很多的属性,如画布的大小,字体的选择,颜色列表等,大家可以通过graphviz的官网来找到更详细的资料。

文中的代码都已经在Github上。

你为什么应该试一试Reflux?

一点背景

React在设计之初就只关注在View本身上,其余部分如数据的获取事件处理等,全然不在考虑之内。不过构建大型的Web前端应用,这些点又实在不可避免。所以Facebook的工程师提出了前端的Flux架构,这个架构的最大特点是单向数据流(后面详述)。但是Flux本身的实现有很多不合理的地方,比如单例的Dispatcher会在系统中有多种事件时导致臃肿的switch-cases等。

这里是Facebook官方提供的提供Flux的结构图

Flux Diagram

其实整个Flux背后的思想也不是什么新东西。在很久之前,Win32的消息机制(以及很多的GUI系统)就在使用这个模型,而且这也是一种被证实可以用来构建大型软件的模型。

鉴于Flux本身只是一个架构,而且Facebook提供的参考实现又有一些问题,所以社区有了很多版本的Flux实现。比如我们这里会用到的Reflux

Reflux简介

简而言之,Reflux里有两个组件:Store和Action。Store负责和数据相关的内容:从服务器上获取数据,并更新与其绑定的React组件(view controller);Action是一个事件的集合。Action和Store通过convention来连接起来。

具体来说,一个典型的过程是:

  1. 用户的动作(或者定时器)在组件上触发一个Action
  2. Reflux会调用对应的Store上的callback(自动触发)
  3. 这个callback在执行结束之后,会显式的触发(trigger)一个数据
  4. 对应的组件(可能是多个)的state会被更新
  5. React组件检测到state的变化后,会自动重绘自身

reflux data flow

一个例子

我们这里将使用React/Reflux开发一个实际的例子,从最简单的功能开始,逐步将其构建为一个较为复杂的应用。

这个应用是一个书签展示应用(数据来源于我的Google Bookmarks)。第一个版本的界面是这样的:

bookmarks list

要构建这样一个列表应用,我们需要这样几个部分:

  1. 一个用来fetch数据,存储数据的store (BookmarkStore)
  2. 一个用来表达事件的Action(BookmarkActions)
  3. 一个列表组件(BookmarkList)
  4. 一个组件条目组件(Bookmark)

定义Actions

1
2
3
4
5
6
var Reflux = require('reflux');
var BookmarkActions = Reflux.createActions([
  'fetch'
]);

module.exports = BookmarkActions;

第一个版本,我们只需要定义一个fetch事件即可。然后在Store中编写这个Action的回调:

定义Store

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
var $ = require('jquery');
var Reflux = require('reflux');
var BookmarkActions = require('../actions/bookmark-actions');

var Utils = require('../utils/fetch-client');

var BookmarkStore = Reflux.createStore({
  listenables: [BookmarkActions],

  init: function() {
      this.onFetch();
  },

  onFetch: function() {
      var self = this;
      Utils.fetch('/bookmarks').then(function(bookmarks) {
          self.trigger({
              data: bookmarks,
              match: ''
          });
      });
  }
});

module.exports = BookmarkStore;

此处,我们使用listenables: [BookmarkActions]来将Store和Action关联起来,根据conventionon+事件名称就是回调函数的名称。这样当Action被触发的时候,onFetch会被调用。当获取到数据之后,这里会显式的trigger一个数据。

List组件

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
var React = require('react');
var Reflux = require('reflux');

var BookmarkStore = require('../stores/bookmark-store.js');
var Bookmark = require('./bookmark.js');

var BookmarkList = React.createClass({
  mixins: [Reflux.connect(BookmarkStore, 'bookmarks')],

  getInitialState: function() {
      return {
          bookmarks: {data: []}
      }
  },

  render: function() {
      var list = [];
      this.state.bookmarks.data.forEach(function(item) {
        list.push(<Bookmark title={item.title} created={item.created}/>)
      });
  
      return <ul>
          {list}
      </ul>
  }
});

module.exports = BookmarkList;

在组件中,我们通过mixins: [Reflux.connect(BookmarkStore, 'bookmarks')]将Store和组件关联起来,这样List组件state上的bookmarks就和BookmarkStore连接起来了。当state.bookmarks变化之后,render方法就会被自动调用。

对于每一个书签,就只是简单的展示内容即可:

Bookmark组件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var React = require('react');
var Reflux = require('reflux');
var moment = require('moment');

var Bookmark = React.createClass({

  render: function() {
      var created = new Date(this.props.created * 1000);
      var date = moment(created).format('YYYY-MM-DD');

      return <li>
          <div className='bookmark'>
              <h5 className='title'>{this.props.title}</h5>
              <span className='date'>Created @ {date}</span>
          </div>
      </li>;
  }
});

module.exports = Bookmark;

这里我使用了moment库将unix timestamp转换为日期字符串,然后写在页面上。

最后,Utils只是一个对jQuery的包装:

1
2
3
4
5
6
7
8
9
10
11
12
var $ = require('jquery');
var Promise = require('promise');

module.exports = {
    fetch: function(url) {
        var promise = new Promise(function (resolve, reject) {
            $.get(url).done(resolve).fail(reject);
        });

        return promise;
    }
}

我们再来总结一下,BookmarkStore在初始化的时候,显式地调用了onFetch,这个动作会导致BookmarkList组件的state的更新,这个更新会导致BookmarkList的重绘,BookmarkList会依次迭代所有的Bookmark

更复杂一些

当然,Reflux的好处不仅仅是上面描述的这种单向数据流。当StoreActions以及具体的组件被解耦之后,构建大型的应用才能成为可能。我们来对上面的应用做一下扩展:我们为列表添加一个搜索功能。

随着用户的键入,我们发送请求到服务器,将过滤后的数据渲染为新的列表。我们需要这样几个东西

  1. 一个SearchBox组件
  2. 一个新的Actionsearch
  3. BookmarkStore上的一个新方法onSearch
  4. 组件SearchBox需要和BookmarkActions关联起来

为了让用户看到匹配的效果,我们需要将匹配到的关键字高亮起来,这样我们需要在Bookmark组件中监听BookmarkStore,当BookmarkStore发生变化之后,我们就可以即时修改书签的title了。

搜索框组件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var React = require('react');
var BookmarkActions = require('../actions/bookmark-actions');

var SearchBox = React.createClass({
  performSearch: function() {
      var keyword = this.refs.keyword.value;
      BookmarkActions.search(keyword);
  },

  render: function() {
      return <div className="search">
          <input type='text'
              placeholder='type to search...'
              ref="keyword"
              onChange={this.performSearch} />   
      </div>
  }
});

module.exports = SearchBox;

BookmarkStore

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
var $ = require('jquery');
var Reflux = require('reflux');
var BookmarkActions = require('../actions/bookmark-actions');

var Utils = require('../utils/fetch-client');

var BookmarkStore = Reflux.createStore({
  listenables: [BookmarkActions],

  init: function() {
      this.onFetch();
  },

  onFetch: function() {
      var self = this;
      Utils.fetch('/bookmarks').then(function(bookmarks) {
          self.trigger({
              data: bookmarks,
              match: ''
          });
      });
  },

  onSearch: function(keyword) {
      var self = this;

      Utils.fetch('/bookmarks?keyword='+keyword).then(function(bookmarks) {
          self.trigger({
              data: bookmarks,
              match: keyword
          });
      });
  }
});

module.exports = BookmarkStore;

我们在BookmarkStore中添加了onSearch方法,它会根据关键字来调用后台API进行搜索,并将结果trigger出去。由于数据本身的结构并没有变化(只是数量会由于过滤而变少),因此BookmarkList是无需修改的。

书签高亮

当搜索匹配之后,我们可以将对应的关键字高亮起来,这时候我们需要修改Bookmark组件:

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
var React = require('react');
var Reflux = require('reflux');
var moment = require('moment');

var BookmarkStore = require('../stores/bookmark-store.js');

var Bookmark = React.createClass({
  mixins: [Reflux.listenTo(BookmarkStore, 'onMatch')],

    onMatch: function(data) {
        this.setState({
            match: data.match
        });
    },

  getInitialState: function() {
      return {
          match: ''
      }
  },

  render: function() {
      var created = new Date(this.props.created * 1000);
      var date = moment(created).format('YYYY-MM-DD');

      var title = this.props.title;
      if(this.state.match.length > 0) {
          title = <span
              dangerouslySetInnerHTML={{
                __html : this.props.title.replace(new RegExp('('+this.state.match+')', "gi"), '<span class="highlight">$1</span>')
              }} />
      }

      return <li>
          <div className='bookmark'>
              <h5 className='title'>{title}</h5>
              <span className='date'>Created @ {date}</span>
          </div>
      </li>;
  }
});

module.exports = Bookmark;

mixins: [Reflux.listenTo(BookmarkStore, 'onMatch')]表示,我们需要监听BookmarkStore的变化,当变化发生时,调用OnMatch方法。OnMatch会修改组件的match属性,从而触发render

render中,我们替换关键字为<span class="highlight">$keyword</span>,这样就可以达到预期的效果了:

bookmark search

结论

从上面的例子可以看到,我们从一开始就引入了Reflux。虽然第一个版本和React原生的写法差异并不是很大,但是当加入SearchBox功能之后,需要修改的地方非常清晰:添加Actions,在对应的Store中添加callback,然后在组件中使用。这种方法不仅可以最大程度的使用React的长处(diff render),而且使得代码逻辑变得较为清晰。

随着业务代码的不断增加,Reflux提供的方式确实可以在一定程度上控制代码的复杂性和可读性。

完整的代码地址在这里

其他参考

看看这些年你都学了什么?

数据可视化

多年下来,我的Google Bookmarks里已经有近万条的书签。大部分内容是我在读过一遍之后就收藏起来的,也有很多看了一眼之后,觉得不错,然后收藏起来准备以后读的(当然,你也知道,再也没有打开过)。

有没有一个方法可以让我以可视化的方式,看到这些年我都学了那些东西呢?将书签列表作为源数据,然后将这些信息可视化出来会非常有意思:比如收藏夹中的热门词是什么,哪段时间收藏了多少条的书签(学习投入程度趋势)等等。

下图是我的书签中,排行前30的关键字排序。可以明显的看出,我对于JavaScript的喜爱程度相当高,对美食的喜爱也超过了pythonlinux

bookmarks trending

这里我将使用python,结合python的一些库来实现书签可视化。简而言之,整个过程可以分成这样几个步骤:

  1. 将Google Bookmarks导出为本地文件
  2. 将书签文件解析为容易处理的内部格式(比如python的dict等)
  3. 由于书签中会有中文的句子,所以会涉及到分词
  4. 统计词语的频率,并绘制成图标

数据源

Google Bookmarks本身可以直接导出成HTML文件。该HTML文件包含了时间戳和书签的标题,我们可以通过python的库BeautifulSoup将HTML中的文本抽取出来:

1
2
3
4
5
6
7
8
from bs4 import BeautifulSoup

def load_bookmarks_data():
  soup = BeautifulSoup(open('bookmarks_10_21_15.html').read(), "html.parser")
  return soup.get_text()
  
if __name__ == "__main__":
  print load_bookmarks_data()    

BeautifulSoup提供非常好用的API来抽取结构化文档中的内容。

bookmark titles

分词

BeautifulSoup获得的是一条条独立的句子,我们需要使用分词器将所有的句子分解成片段。这里我使用了jieba结巴分词)分词器来完成这个任务:

1
2
3
4
5
6
7
import jieba

data = "我在出报表,你的博客写的怎么样了"
seg_list = jieba.cut(data, cut_all=False)

for seg in seg_list:
     print seg

将会输出:

1
2
3
4
5
6
7
8
9
10
11
12



报表



博客


怎么样

我们定义一个方法来将上一步中的文本分词:

1
2
3
def extract_segments(data):
  seg_list = jieba.cut(data, cut_all=False)
  return [seg.strip().lower() for seg in seg_list if len(seg) > 1]

分词之后,我们将单词转换为小写,并剔除掉那些长度小于1的字符串。这样可以保证所有的词都是词语。python的list推导式写起来非常简洁,一行代码就完成了过滤映射的工作。

可视化

有了分好的词之后,只需要统计每个词出现的频率,然后按照频率来绘制图表。我们使用python标准库中的Counter来实现:

1
2
3
4
5
from collections import Counter

def tokenize(): 
  filtered = extract_segments(load_bookmarks_data())
  return Counter([word for word in filtered])

要获取前N个,只需要使用most_common(N)即可:

1
tokenize().most_common(10)
1
[(u'and', 552), (u'the', 501), (u'with', 485), (u'to', 446), (u'javascript', 432), (u'in', 330), (u'for', 308), (u'...', 270), (u'java', 270), (u'blog', 269)]

有了数据之后,使用matplotlib做一个简单的bar图标:

1
2
3
4
5
6
7
8
9
10
11
import matplotlib
import matplotlib.pyplot as plt

from pandas import DataFrame

def visualize():
  frame = DataFrame(tokenize().most_common(20), columns=['keywords', 'frequencies'])

  ax = frame.plot(kind='bar')
  
  plt.savefig('bookmarks_trending.png', format='png', dpi=600)

stopwords

不过,上图中有很多噪音信息,如and, the等,这些在所有文章中都会出现的词并没有实际意义,统称为stopwords。通常在计算过程中会将其忽略:

1
2
3
4
5
6
def tokenize():  
  stoplist = ['i', 'me', 'my', 'myself', 'we', 'our', 'ours', 'ourselves', 'you', 'your', 'yours', 'yourself', 'yourselves', 'he', 'him', 'his', 'himself', 'she', 'her', 'hers', 'herself', 'it', 'its', 'itself', 'they', 'them', 'their', 'theirs', 'themselves', 'what', 'which', 'who', 'whom', 'this', 'that', 'these', 'those', 'am', 'is', 'are', 'was', 'were', 'be', 'been', 'being', 'have', 'has', 'had', 'having', 'do', 'does', 'did', 'doing', 'a', 'an', 'the', 'and', 'but', 'if', 'or', 'because', 'as', 'until', 'while', 'of', 'at', 'by', 'for', 'with', 'about', 'against', 'between', 'into', 'through', 'during', 'before', 'after', 'above', 'below', 'to', 'from', 'up', 'down', 'in', 'out', 'on', 'off', 'over', 'under', 'again', 'further', 'then', 'once', 'here', 'there', 'when', 'where', 'why', 'how', 'all', 'any', 'both', 'each', 'few', 'more', 'most', 'other', 'some', 'such', 'no', 'nor', 'not', 'only', 'own', 'same', 'so', 'than', 'too', 'very', 's', 't', 'can', 'will', 'just', 'don', 'should', 'now']
  stoplist.extend(['...', 'com', 'using', u'使用', 'blog', u'博客', u'博客园', u'做法', u'论坛', 'part', u'部分', u'天下'])
  filtered = extract_segments(load_bookmarks_data())
  
  return Counter([word for word in filtered if word not in stoplist])

重新绘制即可获得上文中的图:

bookmarks trending

完整的代码请参考这里

工程中的编译原理 – Mapfile解析器

前言

Mapfile是MapServer用来描述一个地图的配置文件。它是一个很简单的声明式语言,一个地图(Map)可以有多个层(Layer),每个层可以有很多属性(键值对)。在一个层的定义中,还可以定义若干个类(Class),这个类用以管理不同的样式(Style)。而每个类或者样式都可以由若干个属性(键值对)。

这里有一个实际的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LAYER
  NAME         "counties"
  DATA         "counties-in-shaanxi-3857"
  STATUS       default
  TYPE         POLYGON
  TRANSPARENCY 70

  CLASS
    NAME       "polygon"
    STYLE
      COLOR     255 255 255
      OUTLINECOLOR 40 44 52
    END
  END
END

最简单的层的定义

最简单的情形是,我们定义了一个层Layer,但是没有指定任何的属性:

1
2
LAYER
END

我们期望parser可以输出:

1
{layer: null}

要做到这一步,首先需要定义符号LAYEREND,以及一些对空格,非法字符的处理等:

1
2
3
4
5
6
\s+                     /* skip whitespace */
\n|\r\n                 /* skip whitespace */
"LAYER"                 return "LAYER"
"END"                   return "END"
<<EOF>>                 return 'EOF'
.                       return 'INVALID'

对于,空格,回车换行等,我们都直接跳过。对应的BNF也非常简单:

1
2
3
4
5
6
7
expressions
    : decls EOF {return $1;}
    ;

decls
    : LAYER END {$$ = {layer: null}}
    ;

为层添加属性

接下来我们来为层添加Name属性,首先还是添加符号NAME和对字符串的定义。这里的字符串被定义为:由双引号括起来的所有内容。

1
2
3
"NAME"                  return "NAME"
'"'("\\"["]|[^"])*'"'   return 'STRING'
[a-zA-Z]+               return 'WORD'

然后我们就可以为BNF添加一个新的节:

1
2
3
4
5
6
7
8
decls:
  LAYER decl END
  {$$ = {layer: $2}}
  ;

decl:
  NAME STRING
  {$$ = $2.substring(1, $2.length - 1)};

decl中,我们将获得的字符串两头的引号去掉$2.substring。这样decl的值就会是字符串本身,而不是带着双引号的字符串了。修改之后的代码可以解析诸如这样的声明:

1
2
3
LAYER
  NAME "counties"
END

并产生这样的输出:

1
{ layer: 'counties' }

但是如果我们用来解析两个以上的属性:

1
2
3
4
LAYER
  NAME         "counties"
  DATA         "counties-in-shaanxi-3857"
END

解析器会报告一个错误:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
$ node map.js expr

/Users/jtqiu/develop/ideas/jison-demo/mapfile/map.js:106
        throw new Error(str);
              ^
Error: Parse error on line 2:
...       "counties"  DATA         "counti
----------------------^
Expecting 'END', got 'WORD'
    at Object.parseError (/Users/jtqiu/develop/ideas/jison-demo/mapfile/map.js:106:15)
    at Object.parse (/Users/jtqiu/develop/ideas/jison-demo/mapfile/map.js:171:22)
    at Object.commonjsMain [as main] (/Users/jtqiu/develop/ideas/jison-demo/mapfile/map.js:620:27)
    at Object.<anonymous> (/Users/jtqiu/develop/ideas/jison-demo/mapfile/map.js:623:11)
    at Module._compile (module.js:456:26)
    at Object.Module._extensions..js (module.js:474:10)
    at Module.load (module.js:356:32)
    at Function.Module._load (module.js:312:12)
    at Function.Module.runMain (module.js:497:10)
    at startup (node.js:119:16)

即,期望一个END符号,但是却看到了一个WORD符号。我们只需要稍事修改,就可以让当前的语法支持多个属性的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
decls:
  LAYER pairs END
  {$$ = {layer: $2}}
  ;

pairs:
  pair
  {$$ = $1}
  |
  pairs pair
  {$$ = merge($1, $2)}
  ;

pair:
  NAME STRING
  {$$ = {name: $2.substring(1, $2.length - 1)}}
  | DATA STRING
  {$$ = {data: $2.substring(1, $2.length - 1)}};

先看,pair的定义,它由NAME STRING或者DATA STRING组成,是我们语法中的终结符。再来看pairs的定义:

1
pairs: pair | pairs pair;

这个递归的定义可以保证我们可以写一条pair或者多条pairs pair属性定义语句。而对于多条的情况,我们需要将这行属性规约在一起,即当遇到这样的情形时:

1
2
NAME         "counties"
DATA         "counties-in-shaanxi-3857"

我们需要产生这样的输出:{name: "counties", data: "counties-in-shaanxi-3857"}。但是由于符号是逐个匹配的,我们会得到这样的匹配结果:{name: "counties"}{data: "counties-in-shaanxi-3857"},因此我们需要编写一个简单的函数来合并这些属性:

1
2
3
4
5
6
7
8
9
10
11
12
  function merge(o1, o2) {
    var obj = {};

    for(var k in o1) {
      obj[k] = o1[k];
    }
    for(var v in o2) {
      obj[v] = o2[v];
    }

    return obj;
  }

按照惯例,这种自定义的函数需要被定义在%{}%括起来的section中:

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-zA-Z]+               return 'WORD'
[0-9]+("."[0-9]+)?      return 'NUMBER'
<<EOF>>                 return 'EOF'
.                       return 'INVALID'

/lex

%{
  function merge(o1, o2) {
    var obj = {};

    for(var k in o1) {
      obj[k] = o1[k];
    }
    for(var v in o2) {
      obj[v] = o2[v];
    }

    return obj;
  }
%}

%start expressions

%% /* language grammar */
...

现在我们的解析器就可以识别多条属性定义了:

1
2
$ node map.js expr
{ layer: { name: 'counties', data: 'counties-in-shaanxi-3857' } }

嵌套的结构

现在新的问题又来了,我们的解析器现在可以识别对层的对个属性的解析了,不过由于CLASS并不是由简单的键值对定义的,所以还需要进一步的修改:

1
2
3
4
classes:
  CLASS pairs END
  {$$ = {class: $2}}
  ;

类由CLASS关键字和END关键字定义,而类的属性定义和Layer的属性定义并无二致,都可以使用pairs(多条属性)。而classes事实上是pair的另一种形式,就像对属性的定义一样,所以:

1
2
3
4
5
6
7
pair:
  NAME STRING
  {$$ = {name: $2.substring(1, $2.length - 1)}}
  | DATA STRING
  {$$ = {data: $2.substring(1, $2.length - 1)}}
  | classes
  {$$ = $1};

这样,解析器就可以识别CLASS子句了。我们注意到,在CLASS中,还可以定义STYLE,因此又需要稍作扩展:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
pair:
  NAME STRING
  {$$ = {name: $2.substring(1, $2.length - 1)}}
  | DATA STRING
  {$$ = {data: $2.substring(1, $2.length - 1)}}
  | classes
  {$$ = $1}
  | styles
  {$$ = $1};

styles:
  STYLE pairs END
  {$$ = {style: $2}}
  ;

这样,我们的解析器就可以处理样例中的所有语法了:

1
2
3
4
5
6
7
node map.js expr
{ layer:
   { name: 'counties',
     data: 'counties-in-shaanxi-3857',
     status: 'default',
     type: 70,
     class: { name: 'polygon', style: [Object] } } }

完整的代码在github上的这个repo中

总结

使用BNF定义一个复杂配置文件的规则,事实上一个比较容易的工作。要手写这样一个解析器需要花费很多的时间,而且当你需要parser多种配置文件时,这将是一个非常无聊且痛苦的事情。学习jison可以帮助你很快的编写出小巧的解析器,在上面的Mapfile的例子中,所有的代码还不到100行。下一次再遇到诸如复杂的文本解析,配置文件读取的时候,先不要忙着编写正则表达式,试试更高效,更轻便的jison吧。

工程中的编译原理 – Jison入门篇

前言

在代码编写中,很多时候我们都会处理字符串:发现字符串中的某些规律,然后将想要的部分抽取出来。对于发杂一些的场景,我们会使用正则表达式来帮忙,正则表达式强大而灵活,主流的变成语言如JavaRuby的标准库中都对其由很好的支持。

但是有时候,当接收到的字符串结构更加复杂(往往会这样)的时候,正则表达式要么会变的不够用,要么变得超出我们能理解的复杂度。这时候,我们可能借助一些更为强大的工具。

下面是一个实际的例子,这个代码片段是MapServer的配置文件,它用来描述地图中的一个层,其中包含了嵌套的CLASS,而CLASS自身又包含了一个嵌套的STYLE节。显然,正则表达式在解释这样复杂的结构化数据方面,是无法满足需求的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LAYER
  NAME         "counties"
  DATA         "counties-in-shaanxi-3857"
  STATUS       default
  TYPE         POLYGON
  TRANSPARENCY 70

  CLASS
    NAME       "polygon"
    STYLE
      COLOR     255 255 255
      OUTLINECOLOR 40 44 52
    END
  END
END

在UNIX世界,很早的时候,人们就开发出了很多用来生成解释器(parser)的工具,比如早期的lex)/yacc之类的工具和后来的bison。通过这些工具,程序员只需要定义一个结构化的文法,工具就可以自动生成解释器的C代码,非常容易。在JavaScript世界中,有一个非常类似的工具,叫做jison。在本文中,我将以jison为例,说明在JavaScript中自定义一个解释器是何等的方便。

注意,我们这里说的解释器不是一个编译器,编译器有非常复杂的后端(抽象语法树的生成,虚拟机器指令,或者机器码的生成等等),我们这里仅仅讨论一个编译器的前端

一点理论知识

本文稍微需要一点理论知识,当年编译原理课的时候,各种名词诸如规约推导式终结符非终结符等等,

上下文无关文法(Context Free Grammar)

先看看维基上的这段定义:

在计算机科学中,若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式:V -> w,则称之为上下文无关文法(英语:context-free grammar,缩写为CFG),其中 V∈N ,w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换,而无需考虑字符 V 出现的上下文。

基本上跟没说一样。要定义一个上下文无关文法,数学上的精确定义是一个在4元组:G = (N, Σ, P, S),其中

  1. N是“非终结符”的集合
  2. Σ是“终结符”的集合,与N的交集为空(不想交)
  3. P表示规则集(即N中的一些元素以何种方式)
  4. S表示起始变量,是一个“非终结符”

其中,规则集P是重中之重,我们会在下一小节解释。经过这个形式化的解释,基本还是等于没说,在继续之前,我们先来看一下BNF,然后结合一个例子来帮助理解。

话说我上一次写这种学院派的文章还是2009年,时光飞逝。

巴科斯范式(Backus Normal Form)

维基上的解释是:

巴科斯范式(英语:Backus Normal Form,缩写为 BNF),又称为巴科斯-诺尔范式(英语:Backus-Naur Form,也译为巴科斯-瑙尔范式、巴克斯-诺尔范式),是一种用于表示上下文无关文法的语言,上下文无关文法描述了一类形式语言。它是由约翰·巴科斯(John Backus)和彼得·诺尔(Peter Naur)首先引入的用来描述计算机语言语法的符号集。

简而言之,它是由推导公式的集合组成,比如下面这组公式:

1
2
3
4
S -> T + T | T - T | T
T -> F * F | F / F | F
F -> NUMBER | '(' S ')'
NUMBER ->  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

可以被“继续分解”的元素,我们称之为“非终结符”,如上式中的S, T, NUMBER,而无法再细分的如0..9()则被称之为终结符。|表示或的关系。在上面的公式集合中,S可以被其右边的T+T替换,也可以被T-T替换,还可以被T本身替换。回到上一小节最后留的悬疑,在这里:

  1. N就是{S, T, F, NUMBER}
  2. Σ就是{0, 1, …, 9, (, ), +, -, *, /}
  3. P就是上面的BNF式子
  4. S就是这个的S(第一个等式的左边状态)

上面的BNF其实就是四则运算的形式定义了,也就是说,由这个BNF可以解释一切出现在四则运算中的文法,比如:

1
2
3
1+1
8*2+3
(10-6)*4/2

而所谓上下文无关,指的是在推导式的左边,都是非终结符,并且可以无条件的被其右边的式子替换。此处的无条件就是上下文无关。

实现一个四则运算计算器

我们这里要使用jison,jison是一个npm包,所以安装非常容易:

1
npm install -g jison

安装之后,你本地就会有一个命令行工具jison,这个工具可以将你定义的jison文件编译成一个.js文件,这个文件就是解释器的源码。我们先来定义一些符号(token),所谓token就是上述的终结符

第一步:识别数字

创建一个新的文本文件,假设就叫calc.jison,在其中定义一段这样的符号表:

1
2
3
4
\s+                   /* skip whitespace */
[0-9]+("."[0-9]+)?    return 'NUMBER'
<<EOF>>               return 'EOF'
.                     return 'INVALID'

这里我们定义了4个符号,所有的空格(\s+),我们都跳过;如果遇到数字,则返回NUMBER;如果遇到文件结束,则返回EOF;其他的任意字符(.)都返回INVALID

定义好符号之后,我们就可以编写BNF了:

1
2
3
4
5
6
7
expressions
    : NUMBER EOF
        {
        console.log($1);
        return $1;
        }
    ;

这里我们定义了一条规则,即expressions -> NUMBER EOF。在jison中,当匹配到规则之后,可以执行一个代码块,比如此处的输出语句console.log($1)。这个产生式的右侧有几个元素,就可以用$加序号来引用,如$1表示NUMBER实际对应的值,$2EOF

通过命令

1
jison calc.jison

可以在当前目录下生成一个calc.js文件,现在来创建一个文件expr,文件内容为一个数字,然后执行:

1
node calc.js expr

来测试我们的解释器:

1
2
3
$ echo "3.14" > expr
$ node calc.js expr
3.14

目前我们完整的代码仅仅20行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* lexical grammar */
%lex
%%

\s+                   /* skip whitespace */
[0-9]+("."[0-9]+)?    return 'NUMBER'
<<EOF>>               return 'EOF'
.                     return 'INVALID'

/lex

%start expressions

%% /* language grammar */

expressions
    : NUMBER EOF
        {
        console.log($1);
        return $1;
        }
    ;

加法

我们的解析器现在只能计算一个数字(输入给定的数字,给出同样的输出),我们来为它添加一条新的规则:加法。首先我们来扩展目前的BNF,添加一条新的规则:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
expressions
    : statement EOF
        {
        console.log($1);
        return $1;
        }
    ;

statement:
  NUMBER PLUS NUMBER
  {$$ = $1 + $3}
  |
  NUMBER
  {$$ = $1}
  ;

即,expressionsstatement组成,而statement可以有两个规则规约得到,一个就是纯数字,另一个是数字 加号 数字,这里的PLUS是我们定义的一个新的符号:

1
"+"    return "PLUS"

当输入匹配到规则数字 加号 数字时,对应的块{$$ = $1 + $3}会被执行,也就是说,两个NUMBER对应的值会加在一起,然后赋值给整个表达式的值,这样就完成了语义的翻译。

我们在文件expr中写入算式:3.14+1,然后测试:

1
2
3
$ jison calc.jison
$ node calc.js expr
13.14

嗯,结果有点不对劲,两个数字都被当成了字符串而拼接在一起了,这是因为JavaScript中,+的二义性和弱类型的自动转换导致的,我们需要做一点修改:

1
2
3
4
5
6
7
statement:
  NUMBER PLUS NUMBER
  {$$ = parseFloat($1) + parseFloat($3)}
  |
  NUMBER
  {$$ = $1}
  ;

我们使用JavaScript内置的parseFloat将字符串转换为数字类型,再做加法即可:

1
2
3
$ jison calc.jison
$ node calc.js expr
4.140000000000001

更多的规则

剩下的事情基本就是把BNF翻译成jison的语法了:

1
2
3
4
S -> T + T | T - T | T
T -> F * F | F / F | F
F -> NUMBER | '(' S ')'
NUMBER ->  0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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
expressions
    : statement EOF
        {
        console.log($1);
        return $1;
        }
    ;

statement:
  term PLUS term {$$ = $1 + $3}
  |
  term MINUS term {$$ = $1 - $3}
  |
  term {$$ = $1}
  ;

term:
  factor MULTIPLE factor {$$ = $1 * $3}
  |
  factor DIVIDE factor {$$ = $1 / $3}
  |
  factor {$$ = $1}
  ;

factor:
  NUMBER {$$ = parseFloat($1)}
  |
  LP statement RP {$$ = $2}
  ;

这样,像复杂一些的四则运算:(10-2) * 3 + 2/4,我们的计算器也已经有能力来计算出结果了:

1
2
3
$ jison calc.jison
$ node calc.js expr
24.5

总结

我们在本文中讨论了BNF和上下文无关文法,以及这些理论如何与工程实践联系起来。这里的四则运算计算器当然是一个很简单的例子,不过我们从中可以看到将BNF形式文法翻译成实际可以工作的代码是多么方便。我在后续的文章中会介绍jison更高级的用法,以及如何在实际项目中使用jison产生的解释器。

可视化你的足迹 - Web端

可视化你的足迹

上一篇文章讲述了如何在服务器端通过MapServer来生成地图。虽然MapServer发布出来的地图是标准的WMS服务,但是我们还需要一个客户端程序来展现。我们在上一篇中,通过一些小脚本将照片中的地理信息抽取到了一个GeoJSON文件中。GeoJSON是一种向量图层格式,向量数据可以在服务器端绘制成栅格图,也可以直接在客户端canvas上直接绘制出来。当数据量比较大的时候,我们更倾向于在服务器端绘制,这样只需要在网络上传输一张图片(而且可以做缓存)。大数据量的客户端绘制在性能上会比较差(当然现在已经有了一些新的解决方案,我们后续再细谈),特别是有用户交互时,会出现明显的卡顿。

在本文中,我将分别使用客户端和服务端绘制的两种方式来展现两种不同的地图:使用OpenLayers直接在客户端绘制矢量图,以及使用Leaflet来展示在服务器端绘制好的栅格图层。

使用OpenLayers3展示GeoJSON

展示GeoJSON非常容易,也是一种比较直接的方式,只需要将GeoJSON文件发送到前端,然后直接通过客户端渲染即可。使用OpenLayers3的API,代码会是这样:

1
2
3
4
5
6
7
  $.getJSON('data/places-ive-been-3857.json').done(function(geojson) {

    var vectorSource = new ol.source.Vector({
      features: (new ol.format.GeoJSON()).readFeatures(geojson)
    });

  });

客户端发送一个ajax请求,得到GeoJSON数据之后,将其转换成一个向量类型。OpenLayers定义了很多中格式读取器,比如KML的,GML的,GeoJSON的等等。然后我们可以定义一个样式函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  var image = new ol.style.Circle({
    radius: 5,
    fill: null,
    stroke: new ol.style.Stroke({color: '#f04e98', width: 1})
  });

  var styles = {
    'Point': [new ol.style.Style({
      image: image
    })]
  };

  var styleFunction = function(feature, resolution) {
    return styles[feature.getGeometry().getType()];
  };

这个函数会应用到向量集的Point类型,将其绘制为一个红色,半径为5像素的圆圈。有了数据和样式,我们再来创建一个新的向量,然后生成一个新的图层:

1
2
3
4
var vectorLayer = new ol.layer.Vector({
  source: vectorSource,
  style: styleFunction
});

创建地图,为了方便对照,我们加入了另外一个ol.source.Stamen图层作为参照。这样当缩放到较小的区域时,我们可以清楚的知道当前的点和地物的对照,比如道路名称,建筑名称等,从而确定目前的位置。这是一种非常常见的GIS应用的场景,但是需要注意的是,不同的图层需要有相同的空间映射方式,OpenLayers默认才用EPSG:3857,所以需要两者都采用该投影:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var map = new ol.Map({
  layers: [
    new ol.layer.Tile({
      source: new ol.source.Stamen({
        layer: 'toner'
      })
    }),
    vectorLayer
  ],
  target: 'map',
  controls: ol.control.defaults({
    attributionOptions: /** @type {olx.control.AttributionOptions} */ ({
      collapsible: false
    })
  }),
  view: new ol.View({
    center: ol.proj.transform([108.87316667, 34.19216667], 'EPSG:4326', 'EPSG:3857'),
    zoom: 2
  })
});

创建地图时,我们可以通过layers来指定多个图层。在OpenLayers中,有很多类型的TileStamen是一个专注于做非常漂亮的地图的组织

在view中,我们需要将经纬度(EPSG:4326)转换为墨卡托投影(EPSG:3857)。这样我们就可以得到一个很漂亮的地图了:

geojson toner

使用Leaflet展示栅格数据

我们在上一篇中已经生成了MapServer的WMS地图,这里可以用Leaflet来消费该地图(使用OpenLayers也可以消费,不过V3似乎在和WMS集成时有些问题,我此处使用了Leaflet)。

首先创建一个地图:

1
var map = L.map('map').setView([34, 108], 10);

然后就可以直接接入我们在上一篇中生成的地图:

1
2
3
4
5
6
7
  L.tileLayer.wms("http://localhost:9999/cgi-bin/mapserv?map=/data/xian.map", {
            layers: 'places',
            format: 'image/png',
            transparent: true,
            maxZoom: 16,
            minZoom: 2,
        }).addTo(map);

便于对照,我们先添加一个底图:

1
2
3
4
5
L.tileLayer( 'http://{s}.mqcdn.com/tiles/1.0.0/map/{z}/{x}/{y}.png', {
      attribution: '&copy; <a href="http://osm.org/copyright" title="OpenStreetMap" target="_blank">OpenStreetMap</a> contributors | Tiles Courtesy of <a href="http://www.mapquest.com/" title="MapQuest" target="_blank">MapQuest</a> <img src="http://developer.mapquest.com/content/osm/mq_logo.png" width="16" height="16">',
      subdomains: ['otile1','otile2','otile3','otile4'],
      detectRetina: true
  }).addTo( map );

这样就可以看到最终的地图:

xian leaflet

使用Web界面,我们可以自由的拖拽,移动,并且方便的放大缩小。如果观察浏览器的网络标签,在放大地图时,可以看到很多的WMS请求:

xian leaflet

其他

如果你对代码感兴趣,可以参看这个repo

可视化你的足迹 - 服务器端

可视化你的足迹

数据可视化可以让读者以一种轻松的方式来消费数据,人类大脑在处理图形的速度是处理文本的66,000倍,这也是人们常常说的一图胜千言。在本文中,我们通过将日常中很容易收集到的数据,通过一系列的处理,并最终展现在地图上。这仅仅是GIS的一个很简单场景,但是我们可以看到,当空间数据和地图结合在一起时,可以在可视化上得到很好的效果,读者可以很容易从中获取信息。

steps

我们在本文中会制作一个这样的地图,图中灰色的线是城市中的道路,小六边形表示照片拍摄地。颜色表示当时当地拍摄照片的密度,红色表示密集,黄色为稀疏。可以看到,我的活动区域主要集中在左下角,那是公司所在地和我的住处,:)

要展现数据,首先需要采集数据,不过这些已经在日常生活中被不自觉的被记录下来了:

数据来源

如果你开启了iPhone相机中的定位功能,拍照的时候,iPhone会自动把当前的地理信息写入到图片的元数据中,这样我们就可以使用这些数据来做进一步的分析了。

我在去年学习OpenLayers的时候已经玩过一些简单的足迹可视化,另外还有一篇全球地震信息的可视化,但是仅仅是展示矢量信息,并没有深入,而且都是一些前端的JavaScript的代码。最近又在重新整理之前的GIS知识,重新把这个作为例子来练手。当然,这次会涉及一些地图编辑空间计算的内容。

我的照片一般都通过Mac自带的Photos管理(前身iPhoto),手机里照片会定期同步上去。老版本的iPhoto用的是XML文件来存储照片的EXIF数据,新的Photos的实现里,数据被存储在了好几个SQLite数据库文件中,不过问题不大,我们只需要写一点Ruby代码就可以将数据转化为标准格式,这里使用GeoJSON,GeoJSON既可以方便人类阅读,也可以很方便的导入到PostGIS或者直接在客户端展现。

实现步骤

我们现在要绘制照片拍摄的密度图,大概需要这样一些步骤:

  1. 抽取照片的EXIF信息(经度,纬度,创建时间等)
  2. 编写脚本将抽取出来的信息转换成通用格式(GeoJSON)
  3. 使用QGIS将这些点的集合导入为图层
  4. 插入一些由六边形组成的图层(设置合适的大小)
  5. 计算落在各个多边形中的点的个数,并生成新的图层heatmap
  6. 使用MapServer来渲染基本地图

数据抽取

Mac上的Photos会将照片的元数据存储在一个SQLite3格式的数据库中,文件名为Library.apdb,通常位于这个位置~/Pictures/Photos\ Library.photoslibrary/Database/apdb/Library.apdb。这个文件可以通过SQLite3的客户端直接打开,不过由于可能有其他进程(Mac自己的)打开了该文件,所以会有锁文件,你可能需要先将这个文件拷贝到另外一个位置。

然后将表RKVersion中的部分信息导出即可,SQLite内置了很方便的导出功能,通过它提供的shell客户端sqlite3,将信息导出到csv文件中:

1
2
3
4
5
sqlite> .mode csv
sqlite> .headers on
sqlite> .output places-ive-been.csv
sqlite> select datetime(imageDate+978307200, 'unixepoch', 'localtime') as imageDate, exifLatitude, exifLongitude from RKVersion where exifLatitude and exiflongitude;
sqlite> .output stdout

注意这里的日期,苹果的日期偏移和其他公司不同,始于2001年1月1日,所以要在imageDate之后加上这个base值,然后将文件以.csv的格式导出到places-ive-been.csv中,该文件包含3列:时间,纬度,精度。

1
2
3
4
5
6
7
imageDate,exifLatitude,exifLongitude
"2012-10-25 16:34:01",34.19216667,108.87316667
"2012-10-28 14:45:53",35.1795,109.9275
"2012-10-28 14:45:45",35.1795,109.9275
"2012-10-25 16:34:04",34.19216667,108.87316667
"2012-10-19 23:01:05",34.19833333,108.86733333
...

转换为GeoJSON

方便以后的转换起见,我们将这个文件转换成GeoJSON(其实很多客户端工具可以支持CSV的导入,不过GeoJSON更为标准一些)。

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
require 'csv'
require 'json'

lines = CSV.open("places-ive-been.csv").readlines
keys = lines.delete lines.first

File.open("places-ive-been.json", 'w') do |f|
    data = lines.map do |row|
        {
            :type => "Feature",
            :geometry => {
              :type => "Point",
              :coordinates => [row[2].to_f, row[1].to_f]
            },
            :properties => {
              :created_at => row[0]
            }
        }
    end

    f.puts JSON.pretty_generate({
        :type => "FeatureCollection",
        :crs => {
          :type => "name",
          :properties => {
            :name => "EPSG:4326"
          }
        },
        :features => data
    })
end

这段脚本可以将我们的.csv转换成标准的geojson格式,注意此处的空间投影使用的是EPSG:4326

导入为QGIS图层

QGIS是一个开源的GIS套件,包括桌面端的编辑器和服务器端,这里我们只是用器桌面端来进行图层的编辑。

将我们的GeoJSON导入之后,会看到这样的一个可视化的效果!

points

我们还可以导入其他的地图图层,这样可以清楚的看到点所在的区域(国家地图图层可以在此处下载):

points with countries

好了,有了基础数据之后,我们来作进一步的数据分析 – 即生成密度图。首先使用QGIS的插件MMQGIS生成多边形图层功能(Create -> Create Grid Layer),为了处理速度,我们可以将地图放大到一定范围(我选择西安市,我在这里活动比较密集)。

选择六边形hexagon,并设置合适的大小(如果是3857参考系,即按照公里数来设置,会比较容易一些,如果是4326,则需要自己计算)。简而言之,需要保证每个格子都包含一些点,不至于太密,也不至于太稀疏。

hexagon

计算密度

QGIS提供了很多的数据分析功能,我们在这个例子中使用(Vector -> Analysis Tools -> Points in Polygon)工具,这个工具需要两个图层,一个是点集图层,一个是多边形图层。然后会将结果生成到一个新的图层中,我们可以将其命名为places-ive-been-density.shp,同时需要指定一个字段来存储统计出来的值(density)。

这个过程可能会花费一点时间,根据需要计算的点集合多边形的格式(也就是地图上的区域)。

完成之后会得到一个Shapefile(其实是一组,具体可以参看这里)。其实在这个过程中,绝大多数多边形是不包含任何数据的,我们需要过滤掉这些多余的多边形,这样可以缩减绘制地图的时间。

我们可以将这个文件导入到PostGIS中进行简化:

1
2
shp2pgsql -I -s 4326 data/places-ive-been/places-ive-been-3857-density.shp places_density |\
PGUSER=gis PGPASSWORD=gis  psql -h localhost -d playground

这里的shp2pgsql命令是GDAL工具包提供的命令,用以将Shapefile导入到PostGIS中,你可以通过

1
$ brew install gdal --with-postgresql

来安装。

GDAL会提供很多的工具,比如用来转换各种数据格式,投影,查看信息等等。

导入之后,我们可以在PostGIS的客户端查看,编辑这些数据等。比如在过滤之前,

1
select count(*) from places_density;

我们导入的数据中有103166条记录:

1
select count(*) from places_density where density IS NOT NULL;

而过滤之后,我们仅剩下749条数据。

通过GDAL提供的另一个工具ogr2ogr可以方便的执行过滤,并生成新的Shapefile:

1
2
3
4
$ ogr2ogr -f "ESRI Shapefile" data/places-ive-been/places_heatmap.shp \
PG:"host=localhost user=gis dbname=playground pass
word=gis" \
-sql "SELECT density, geom FROM places_density WHERE density IS NOT NULL;"

这条命令可以得到一个新的文件,这个就是最终的用来绘制地图的文件了。

绘制地图

开源世界中有很多的工具可以完成地图的绘制,比如MapServerGeoServerMapnik等等。我们在这篇文章中使用MapServer来完成地图的绘制,MapServer的安装和配置虽然比较容易,但是也需要花费一些时间,所以我将其放到了这个repo中,你可以直接clone下来使用。(需要你在虚拟机中安装ansible来完成provision)。

MapServer的配置很简单,类似于一个XML,不过是自定义的格式:

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
MAP
  IMAGETYPE      PNG
  EXTENT         11859978.732852 3994742.227345 12753503.595559 4580388.268737
  SIZE           8000 6000
  SHAPEPATH      "/data/heatmap"
  IMAGECOLOR     255 255 255

  PROJECTION
    "init=epsg:3857"   ##required
  END

  LAYER # States polygon layer begins here
    NAME         heatmap
    DATA         heatmap_3857
    STATUS       default
    TYPE         POLYGON

    CLASS
      NAME "basic"
      STYLE
        COLOR        255 255 178
        OUTLINECOLOR 255 255 178
      END
    END
  END

END

这些配置基本上都比较自解释,比如设置图片格式,图片大小,Shapefile的路径,图层的名称等,MapServer的文档在开源软件中来说,都算比较烂的,但是对于这些基本概念的解释还比较详尽,大家可以去这里参考

这里我们定义了一个图层,每个Map中可以定义多个图层(我们完成的最终效果图就是西安市的道路图和照片拍摄密度图两个图层的叠加)。

这个配置绘制出来的地图是没有颜色差异的,全部都是255 255 178。不过MapServer的配置提供了很好的样式定义,比如我们可以定义这样的一些规则:

  1. 如果密度为1,则设置颜色为淡黄
  2. 如果密度在1-2,则设置为比淡黄红一点的颜色
  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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
  LAYER
    NAME         heatmap
    DATA         heatmap_3857
    STATUS       default
    TYPE         POLYGON
    #CLASSITEM density

    CLASS
      EXPRESSION ([density] = 1)
      STYLE
        COLOR        255 255 178
        OUTLINECOLOR 255 255 178
      END
    END

    CLASS
      EXPRESSION ([density] > 1 AND [density] <= 2)
      STYLE
        COLOR        254 204 92
        OUTLINECOLOR 254 204 92
      END
    END

    CLASS
      EXPRESSION ([density] > 2 AND [density] <= 3)
      STYLE
        COLOR        253 141 60
        OUTLINECOLOR 253 141 60
      END
    END

    CLASS
      EXPRESSION ([density] > 3 AND [density] <= 10)
      STYLE
        COLOR        240 59 32
        OUTLINECOLOR 240 59 32
      END
    END

    CLASS
      EXPRESSION ([density] > 10 AND [density] < 3438)
      STYLE
        COLOR        189 0 38
        OUTLINECOLOR 189 0 38
      END
    END

  END

这样我们的地图展现出来就会比较有层次感,而且通过颜色的加深,也能体现热图本身的含义。

同样的原理,如果将那些自己创建的多边形替换为行政区域划分的多边形,则可以得到另外一种形式的热图

shaanxi-heatmap

总结

我们通过使用一些开源工具(MapServer,QGis,PostGIS,GDAL等),构建出一个基于GIS的数据可视化框架。在这个stack上,我们可以很容易的将一些其他数据也通过可视化的方式展现出来(公用自行车站点分布,出租车分布等等)。MapServer可以发布标准的WMS服务,因此可以很好的和客户端框架集成,从而带来更加友好的用户体验。