<?xml version="1.0" encoding="utf-8"?>
<feed xmlns="http://www.w3.org/2005/Atom">

  <title><![CDATA[Meta-Interpretation]]></title>
  <link href="http://pfmiles.github.io/atom.xml" rel="self"/>
  <link href="http://pfmiles.github.io/"/>
  <updated>2015-08-15T17:22:27+08:00</updated>
  <id>http://pfmiles.github.io/</id>
  <author>
    <name><![CDATA[pf_miles]]></name>
    <email><![CDATA[miles.wy.1@gmail.com]]></email>
  </author>
  <generator uri="http://octopress.org/">Octopress</generator>

  
  <entry>
    <title type="html"><![CDATA[java与groovy混编 —— 一种兼顾接口清晰和实现敏捷的开发方式]]></title>
    <link href="http://pfmiles.github.io/blog/java-groovy-mixed"/>
    <updated>2015-03-14T16:07:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/java-groovy-mixed</id>
    <content type="html"><![CDATA[<ol>
<li>有大量平均水平左右的“工人”可被选择、参与进来 —— 这意味着好招人</li>
<li>有成熟的、大量的程序库可供选择 —— 这意味着大多数项目都是既有程序库的拼装，标准化程度高而定制化场景少</li>
<li>开发工具、测试工具、问题排查工具完善，成熟 —— 基本上没有团队愿意在时间紧、任务重的项目情况下去做没有把握的、基础开发工具类的技术试探</li>
<li>有面向对象特性, 适合大型项目开发 —— 无数大型项目已向世人述说，“面向对象”是开发大型软件的优秀代码组织结构</li>
<li>能适应大型团队、多人协作开发 —— 代码需要简单易懂，起码在接口、api层面是这样</li>
</ol>


<p> —— 这是我所理解的“工业化开发编程语言”的概念</p>

<p>很显然, java就是种典型的“工业语言”, 非常流行，很多企业靠它赚钱，很实际；<br/>
但java也是常年被人黑，光是对其开发效率的诟病就已经足够多，不过java始终屹立不倒；</p>

<p>这样的局面其实无所谓高兴还是担忧，理性的程序员有很多种，其中一种是向“钱”看的 —— 我写java代码，就是因为工作需要而已，能帮助我的组织搞定业务，做出项目，这很好；<br/>
当有人说java语言不好的时候，理性的程序员不会陷入宗教式的语言战争之中，他会思考这些人说的是否有道理；如果真的发现整个java平台大势已去，他会毫不犹豫地扭头就走，不过直到目前为止，还没有这种迹象出现;</p>

<p>那么，从这些无数次的口水之争中，我们能否从别人的“战场”上发现一些有用的东西, 来改进我们的开发方式，从而使得java这种已经成为一个“平台”的东西走得更远，赚更多的钱呢？<br/>
答案是“有的”，感谢那些参与口水战争的、各种阵营的年轻程序员们，有了你们，java speaker们才有了更多的思考;</p>

<!-- more -->


<p>我就只谈一个最实际的问题：</p>

<h2>java被吐槽的这些年, 就开发效率这一点而言，到底有哪些东西是值得借鉴的？</h2>

<p>也就是说，到底是哪些主要特性直接导致了某些其它语言在语法上相对于java的优越感？</p>

<h3>丰富的literal定义</h3>

<p>在groovy中定义map和list的惯用方式：</p>

<pre><code>def list = [a, 2 ,3]
def map = [a:0, b:1]
</code></pre>

<p>而java呢？只能先<code>new</code>一个list或map，再一个个add或put进去; 上面这种literal(字面量)形式的写法便捷得多;</p>

<p>而javascript在这方面做得更绝, 我们都用过json，而json其实就是literal形式的object</p>

<p>极端情况下，一门编程语言里的所有数据类型，包括&#8221;内建&#8221;的和用户自定义的，统统可以写成literal形式;<br/>
在这种情形下，其实这种语言连额外的对象序列化、反序列化机制都不需要了 —— 数据的序列化形式就是代码本身, “代码”和“数据”在形式上被统一了</p>

<p>java对这方面几乎没有任何支持，对于提高编码效率来讲，这是值得学习的一点, 起码“内建”数据结构需要literal写法支持</p>

<h3>first-class function &amp; higher-order function &amp; function literal(lambda)</h3>

<p>无论是js, 还是python/ruby，或是groovy，都可以将函数作为另一个函数的参数传入，以便后者根据执行情况判断是否要调用前者<br/>
或者能够将一个函数作为另一个函数的返回值返回，以便后续再对其进行调用<br/>
这种高阶函数特性，就不要再说java的匿名内部类“能够”实现了, 如果认为匿名内部类已经&#8221;够用&#8221;了的话，其实就已经与现在的话题“开发效率”相悖了</p>

<p>高阶函数显然是一种值得借鉴的特性，它会让你少写很多很多无聊的“包装”代码;</p>

<p>还有就是匿名函数(lambda)了<br/>
我不喜欢lambda、lambda地称呼这个东西，我更喜欢把它叫做“匿名函数”或者“函数字面量(literal)”, 因为它跟数学上的lambda演算还是有本质区别，叫&#8221;lambda&#8221;有误导的危险</p>

<p>函数字面量的意思就是说，你可以在任何地方，甚至另一个函数体的调用实参或内部，随时随地地定义另一个新的函数<br/>
这种定义函数的形式，除了“这个函数我只想在这里用一次，所以没必要给它起个名字”这种理由之外，还有一个更重要的理由就是“闭包”了</p>

<p>所谓闭包，其实也是一个函数，但是在这个函数被定义时，其内部所出现的所有&#8221;自由变量(即未出现在该函数的参数列表中的变量)&#8221;已被当前外层上下文给确定下来了(lexical), 这时候，这个函数拥有的东西不仅仅是一套代码逻辑，还带有被确定下来的、包含那些“自由变量”的一个上下文, 这样这个函数就成为了一个闭包</p>

<p>那么闭包这种东西有什么好呢？其实如果懒散而钻牛角尖地想，闭包的所有能力，是严格地小于等于一个普通的java对象的，也就是说，凡是可以用一个闭包实现的功能，就一定可以通过传入一个对象来实现，但反过来却不行 —— 因为闭包只有一套函数逻辑，而对象可以有很多套，其次很多语言实现的闭包其内部上下文不可变但对象内部属性可变</p>

<p>既然这样，java还要闭包这种东西来干嘛？其实这就又陷入了&#8221;匿名内部类可以实现高阶函数&#8221;的困境里了 —— 如果我在需要一个闭包的时候，都可以通过定义一个接口再传入一个对象来实现的话，这根本就跟今天的话题“开发效率”背道而驰了</p>

<p>显然，java是需要闭包的</p>

<h3>强大而复杂的静态类型系统</h3>

<p>这和开发效率有关么？<br/>
编程语言不是越“动态”，开发效率越高么？还需要强大而复杂的静态类型系统么？</p>

<p>试想一下这种api定义：</p>

<pre><code>def eat(foo) {
    ...
}
</code></pre>

<p>这里面你认识的东西可能只有&#8217;吃&#8217;了, 你知道foo是什么么？你知道它想吃什么么？吃完后要不要产出点什么东西？ —— 你什么都不知道<br/>
这种api极易调用出错，这就好比我去买饭，问你想吃什么你说“随便”，但买回肯德基你却说你实际想吃的是麦当劳一样</p>

<p>可能你还会反驳说，不是还有文档么？你把文档写好点不就行了么？ —— 不要逼我再提“匿名内部类”的例子，如果给每个函数写上复杂详尽的文档是个好办法，那就显然 —— again, 与“开发效率”背道而驰了</p>

<p>那么，静态类型系统，这里显然就该用上了</p>

<p>静态类型系统在多人协作开发、甚至团队、组织间协作开发是非常有意义的；<br/>
拥有静态类型系统的编程语言通常都有强大的、带语法提示功能的IDE，这很正常，因为静态类型语言的语法提示功能好做;<br/>
只要把别人的库拿过来，导入IDE，各种函数签名只需扫一眼 —— 很多情况下根本不需要仔细看文档 —— 就已经知道这个函数是干嘛用的了, 合作效率成倍提升;</p>

<p>而且，作为&#8221;api&#8221;，作为“模块边界”，作为与其它程序员合作的“门面”, 函数签名上能将参数和返回值类型“卡”得越紧越好 —— 这样别人不用猜你这个函数需要传入什么类型，甚至他在IDE里一“点”，这里就给自动填上了 :)</p>

<p>要做到“卡得紧”，光有静态类型系统还不够，这个系统还需强大, 试想一下这个例子:</p>

<pre><code>/**
 * 我只吃香蕉和猪肉，请勿投食其它物品
 */
public void eat(List&lt;Object&gt; list) {
    for(Object o: list) {
        if(o instanceof Banana){
            ... // eating banana
        } else if(o instanceof Pork) {
            ... // eating pork
        } else {
            throw new RuntimeException("System err.");
        }
    }
}
</code></pre>

<p>这段纯java代码已经是“定义精确”的静态类型了<br/>
但如果没有上面那行注释，你很可能会被<code>System err.</code>无数次<br/>
而这行注释之所以是必需的，完全是因为我找不到一个比<code>List&lt;Object&gt;</code>更好的表达“香蕉或猪肉”的形式, 这种情形足以让人开始想念haskell的either monad</p>

<p>在“强大而复杂的类型系统”这一点上，jvm平台上令人瞩目的当属scala了，可惜java没有，这是值得借鉴的</p>

<p>不过这一点的“借鉴”还需java的compiler team发力，我等也只是说说(按照java保守的改进速度，估计<code>HM</code>类型系统是指望不上了)</p>

<h3>动态类型系统，duck-typing</h3>

<p>刚说完静态类型，现在又来说动态类型系统合适么？</p>

<p>然而这与节操无关，我想表达的是，只要是有助于“开发效率”的，都能够借鉴，这是一个理性的java speaker的基本素质</p>

<p>我们在开发项目的时候，大量的编码发生在“函数”或“方法”的内部 —— 这就好比你在屋子里、在家里宅着一样, 是不是应该少一些拘束，多一些直截了当？<br/>
在这种情形下，动态类型系统要不要太爽？ ——</p>

<pre><code>Void visitAssert(AssertTree node, Void arg1) {
    def ahooks = this.hooks[VisitAssertHook.class]
    ahooks.each {it.beforeVisitCondition(node, errMsgs, this.ctx, resolveRowAndCol, setError)}
    scan((Tree)node.getCondition(), arg1);
    ahooks.each {it.afterVisitConditionAndBeforeDetail(node, errMsgs, this.ctx, resolveRowAndCol, setError)}
    scan((Tree)node.getDetail(), arg1);
    ahooks.each {it.afterVisitDetail(node, errMsgs, this.ctx, resolveRowAndCol, setError)}
    return null;
}
</code></pre>

<p>你知道ahooks是什么类型么？你不知道但我(我是编码的人)知道<br/>
你知道ahooks身上有些什么方法可以调么？你同样不知道但我知道</p>

<p>你不知道没关系，只要我知道就行了，因为现在是我在写这段代码；<br/>
这段代码写完以后，我只会把<code>Void visitAssert(AssertTree node, Void arg1)</code>这个类型明确的方法签名提供给你调用，我并不会给你看函数体里面的那坨东西，因此你知不知道上面这些真的没关系</p>

<p>方法内部满是def, 不用书写繁复的<code>List&lt;Map&lt;String, List&lt;Map&lt;Banana, Foo&gt;&gt;&gt;&gt;</code>这种反人类反社会标语, 每个对象我知道它们身上能“点”出些什么来，我只管“点”，跑起来之后<code>invokedynamic</code>会为我搞定一切</p>

<p>动态类型系统 —— 这就是方法内部实现应该有的样子<br/>
哪怕你的方法内部实现就是一坨shi，你也希望这坨shi能尽可能小只一点，这样看起来更清爽是吧？</p>

<p>不要说我太分裂，我要笑你看不穿 —— 静态类型和动态类型既然都有好处，那么他们能放在一起么？<br/>
能的，这里就需要点明这篇文章的政治目的了： “java与groovy混编”<br/>
而且，目前来看，jvm平台上，只有它二者的结合，才能完成动态静态混编的任务</p>

<p>曾经我发出过这样一段感叹：</p>

<blockquote><p>公共api、对外接口声明、应用程序边界&#8230;这些对外的“脸面”部分代码，如果拥有scala般强大的类型系统&#8230;就好了；而私有代码、内部实现、各种内部算法、逻辑，如果拥有groovy般的动态、简单的类型系统&#8230;就好了；综上，如果有门语言，在接口和实现层面分别持有上述特性,就好了</p></blockquote>

<p>这种“理想”中的语言或许某天我有空了会考虑实现一个</p>

<p>而现在，虽说不是scala，但我终于想要在java和groovy身上来试验一把这种开发方式了<br/>
这里我坦白一下为什么没用scala，原因很简单，我在技术选型方面是势利的，scala还不被大多数平均水平的java开发人员(参见&#8221;工业化开发编程语言&#8221;定义第一条)接受，这直接导致项目的推进会遇到困难<br/>
而相对来讲，我暂且相信大多数java开发人员都还算愿意跨出<code>groovy</code>这一小步，当然这还需要时间证明</p>

<p>好了，下面还剩下一点点无关痛痒的牢骚 ——</p>

<h3>元编程能力</h3>

<p>macro, eval, 编译过程切入, 甚至method missing机制，这些都算“元编程”</p>

<p>元编程能力的强弱直接决定了使用这种语言创作“内部DSL”的能力<br/>
java在元编程方面的能力，几乎为0</p>

<p>这是值得借鉴的</p>

<p>与groovy的混编，顺便也能把groovy的元编程也带进来</p>

<h3>各种奇巧的语法糖</h3>

<p>语法糖，关起门来吃最美味，这也是一种使得“方法内部实现更敏捷”的附加手段<br/>
网上随便下载一份groovy的cheat sheet, 都会列举groovy的那些写代码方面的奇技淫巧<br/>
这些奇技淫巧，在各种脚本语言之间其实都大同小异, 因为他们本来就是抄来抄去的<br/>
结合方法内部的动态类型环境，这一定会进一步缩小方法内部实现代码的体积</p>

<h2>java &amp; groovy混编：一种最“势利”的折衷</h2>

<p>我不去讨论什么语言才是The True Heir of Java, 那会使这篇文章变成一封战书，我只关心如何更好地利用现有开发资源完成项目，高效地帮组织实现利益<br/>
所以说java和groovy的混编是一种最“势利”的折衷，我不想强迫平均水平的开发人员去学习一种完全不同的语言，短期内不会对项目有任何好处，真正想去学的人他自己会找时间去学<br/>
而groovy，说它是java++也不为过，因为java代码直接就可以被groovy编译, groovy完全兼容java语法, 对一般java开发人员来说，这真是太亲切了</p>

<p>这里我要提一下我对“java和groovy混编”的一个个人性质的小尝试 —— <a href="https://github.com/pfmiles/kan-java" title="kan-java">kan-java项目</a></p>

<p>kan-java这个小工具，凡是用户在编码使用过程中能“碰”到的类和接口，全部都由java定义, 这确保用户拿到的东西都有精确的类型定义</p>

<p>凡是对上述接口的实现，都以groovy代码的形式存在</p>

<p>这贯彻了&#8221;接口静态类型，内部实现动态类型&#8221;的宗旨, 或者说“凡是要提供给另外一个人看、调用的地方(接口或接口类)，使用java，否则就用groovy”</p>

<p>当然了，单元测试也完全由groovy代码实现</p>

<p>将kan-java的jar包引入到项目中使用时，就跟使用其它任何纯java实现的jar包一样 —— 接口清晰，参数类型明确，返回类型明确, 你不会也没有必要知道开发人员在具体实现的时候，使用动态语言爽过一把</p>

<p>对于java和groovy的混编，项目的pom.xml如何配置，除了可以参考kan-java的配置外，还可以参考这个gist: <a href="https://gist.github.com/pfmiles/2f2ab77f06d48384f113">https://gist.github.com/pfmiles/2f2ab77f06d48384f113</a>, 里面举例了两种配置方式，各有特色</p>

<p>具体的效果，还需要真正地去实际项目中体会<br/>
另外，kan-java也是一个有趣的工具，这个工具所实现的功能我也是从未见到java世界内有其它地方讨论过的，它可以辅助java做“内部DSL”，有场景的可以一试</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[安全的免登方案]]></title>
    <link href="http://pfmiles.github.io/blog/safe-sso-solution"/>
    <updated>2014-03-27T19:26:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/safe-sso-solution</id>
    <content type="html"><![CDATA[<h2>免登</h2>

<ul>
<li>也就是用户在网站A已经登录，希望不必再重复登录过程，即可以登录状态访问网站B</li>
<li>这其实是一种“信任交换”，即用户已经取得了网站A的信任，希望以一种安全的方式也取得网站B的信任</li>
<li>从网站A免登到网站B的信任交换其实就是交换“登录cookie”, 很显然“交换登录cookie”只是“信任交换”的一种情形；从普遍意义上讲，用户在系统A和系统B之间做“信任交换”，其实可以交换任意“信任凭证”，他们的原理都是大同小异的</li>
</ul>


<!-- more -->


<h2>面临的问题及解决方案</h2>

<p>想要安全地做“信任交换”，以从网站A免登到网站B举例，其实主要是要解决如下几个问题：</p>

<ol>
<li>免登目标地址的合法性</li>
<li>在任何一次跳转的过程中防止参数被篡改</li>
<li>任何一次跳转链接都要具有短效性和一次性(除了最后一次跳往目标地址的跳转)</li>
<li>免登目标所接受的参数的合法性(如果有的话)</li>
<li>在任意一次跳转的前后相邻两次请求之间，保证客户端不被顶替(即请求间保证ip一致或设备指纹一致)</li>
</ol>


<p>第一个问题，“免登目标地址的合法性”，这是需要网站A解决的；建议网站A建立一个“合法的免登目标地址”列表，用以检测用户发起的免登请求的目标地址是否合法<br/>
需要注意的是，一个“合法”的免登目标地址，不仅仅是域名合法就行了，也包括path部份；因为不排除会有人将用户骗至一个执行重要操作的目标url进行免登，比如&#8221;www.B.com/resetPassword.do&#8221;，这是应当避免的<br/>
一般来讲，免登的目标地址应该是一个“无副作用”，无任何额外操作的类似于“主页”的地方，这样能杜绝上述情况发生</p>

<p>第二个问题，“在任何一次跳转的过程中防止参数被篡改”，这显然是必要的；从http跳转这种行为本身来讲，每一次跳转，服务器端都失去一次对该请求行为的控制，客户端想要更改跳转请求的任何属性都轻而易举<br/>
可以采用&#8221;数字签名&#8221;技术防止这种篡改；需要考虑的是，哪些数据需要被签名？这取决于该免登需求“在意”哪些数据被更改，一般来讲，都会对请求参数进行签名，当然其它数据，如path也可以被包含在内，如果path带有业务信息的话<br/>
由网站A负责加签，等请求经由客户端，在转发到网站B时，网站B会对请求进行验签; 这需要网站A和网站B事先约定好加签验签的密钥，一般来讲，对称的密钥串已经足够安全，只要密钥不被泄漏<br/>
另外，如果需要确保每次跳转后，访问服务器的仍是同一个客户端，那么这个签名步骤也可将客户端的ip地址或“设备指纹”等数据一并加签，以便验证请求在跳转过程中是否被劫持;不过这么做的风险是，并不仅仅只有被劫持的情况才会在跳转过程中改变客户端的ip，也可能是其它正常情况，比如A、B网站之间不同的网络架构造成的获取客户端ip地址误差等等，需三思而后行</p>

<p>第三个问题，“任何一次跳转链接都要具有短效性和一次性”，这也是显而易见的，否则客户端或搜索引擎只要将某个跳转中间阶段的url给收录下来，那么就随时可以免登了；有不少实力雄厚的大网站都出过这样的问题<br/>
这个问题可以通过“一次性令牌”方案简单解决，也就是说，跳转之前生成一个唯一的、一次性的、短期时效性的一个“令牌”，跳转到目标网站后在验证、作废该令牌<br/>
至于是网站A还是网站B负责生成这个令牌，其实无所谓，只要保证令牌的生成过程是私密的就行了：</p>

<ul>
<li>若网站A生成令牌，则直接将该令牌放入跳转请求中，客户端跳转到网站B后，由网站B调用网站A暴露的令牌验证接口(比如http形式的接口)验证并作废该令牌</li>
<li>若网站B生成令牌，则跳转前网站A调用网站B的服务请求该令牌(注意该请求过程必须私密，一般不走http接口，若要走也需要有保密手段)，跳转后由网站B验证并作废该令牌</li>
</ul>


<p>上述两种策略都可以，但看起来显然由跳转发起方来做令牌的生成和提供验证接口比较好，这样省去远程调用令牌生成接口的麻烦<br/>
注意，最后一次跳转，也就是跳转到最终目标页面的那次跳转，由于有登录验证，因此不需要一次性令牌验证了，但仍然需要签名验证(如果带有业务参数的话)</p>

<p>第四个问题，“免登目标所接受的参数的合法性”；一般来讲，免登目标url是不建议带有参数的，但如果一定要带，那么是必需要网站B验证这些参数的业务合法性，以免恶意用户从一开始就传送一些非法参数过来</p>

<p>第五个问题，在多次跳转请求间“保证客户端不被顶替”，这个听起来概念复杂，但实现起来挺简单：只要在加签、验签的时候把客户端ip也算在里面就行了，当然如果网站已经实现了“设备指纹”技术那就更好了，这个问题就转化为：“多次请求跳转期间，通过签名、验签保证客户端设备指纹不被篡改”</p>

<p>解决好了上述几个问题，也就是几次跳转，写好cookie，最终跳到目标页面上的事情了。</p>

<p>综上，一个典型的，由网站A免登到网站B，其跳转执行流程如下：<br/>
<img src="http://pfmiles.github.io/images/sso_seq.png" alt="免登流程" /></p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[动态的Java - 无废话JavaCompilerAPI中文指南]]></title>
    <link href="http://pfmiles.github.io/blog/dynamic-java"/>
    <updated>2013-09-24T11:54:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/dynamic-java</id>
    <content type="html"><![CDATA[<h1>JavaCompiler API</h1>

<p>1.6之后JDK提供了一套compiler API，定义在<a href="http://jcp.org/en/jsr/detail?id=199">JSR199</a>中, 提供在运行期动态编译java代码为字节码的功能<br/>
简单说来，这一套API就好比是在java程序中模拟javac程序，将java源文件编译为class文件；其提供的默认实现也正是在文件系统上进行查找、编译工作的，用起来感觉与javac基本一致;<br/>
不过，我们可以通过一些关键类的继承、方法重写和扩展，来达到一些特殊的目的，常见的就是“与文件系统解耦”(就是在内存或别的地方完成源文件的查找、读取和class编译)<br/>
需要强调的是，compiler API的相关实现被放在tools.jar中，JDK默认会将tools.jar放入classpath而jre没有，因此如果发现compiler API相关类找不到，那么请检查一下tools.jar是否已经在classpath中；<br/>
当然我指的是jdk1.6以上的版本提供的tools.jar包</p>

<!-- more -->


<h2>基本使用</h2>

<h3>一个基本的例子</h3>

<pre><code>public static CompilationResult compile(String qualifiedName, String sourceCode,
                                        Iterable&lt;? extends Processor&gt; processors) {
    JavaStringSource source = new JavaStringSource(qualifiedName, sourceCode);
    List&lt;JavaStringSource&gt; ss = Arrays.asList(source);
    List&lt;String&gt; options = Arrays.asList("-classpath", HotCompileConstants.CLASSPATH);
    JavaCompiler compiler = ToolProvider.getSystemJavaCompiler();

    MemClsFileManager fileManager = null;
    Map&lt;String, JavaMemCls&gt; clses = new HashMap&lt;String, JavaMemCls&gt;();
    Map&lt;String, JavaStringSource&gt; srcs = new HashMap&lt;String, JavaStringSource&gt;();
    srcs.put(source.getClsName(), source);
    try {
        fileManager = new MemClsFileManager(compiler.getStandardFileManager(null, null, null), clses, srcs);
        DiagnosticCollector&lt;JavaFileObject&gt; diagnostics = new DiagnosticCollector&lt;JavaFileObject&gt;();
        StringWriter out = new StringWriter();
        CompilationTask task = compiler.getTask(out, fileManager, diagnostics, options, null, ss);
        if (processors != null) task.setProcessors(processors);
        boolean sucess = task.call();
        if (!sucess) {
            for (Diagnostic&lt;? extends JavaFileObject&gt; diagnostic : diagnostics.getDiagnostics()) {
                out.append("Error on line " + diagnostic.getLineNumber() + " in " + diagnostic).append('\n');
            }
            return new CompilationResult(out.toString());
        }
    } finally {
        try {
            fileManager.close();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
    // every parser class should be loaded by a new specific class loader
    HotCompileClassLoader loader = new HotCompileClassLoader(Util.getParentClsLoader(), clses);
    Class&lt;?&gt; cls = null;
    try {
        cls = loader.loadClass(qualifiedName);
    } catch (ClassNotFoundException e) {
        throw new RuntimeException(e);
    }
    return new CompilationResult(cls, loader);
}
</code></pre>

<p>解释一下这段程序：<br/>
这个static方法提供这样一种功能：输入希望的类名和String形式的java代码内容，动态编译并返回编译好的class对象; 其中<code>CompilationResult</code>只是一个简单的pojo封装，用于包装返回结果和可能的错误信息<br/>
类名和源码首先被包装成一个<code>JavaStringSource</code>对象, 该对象继承自<code>javax.tools.SimpleJavaFileObject</code>类，是compiler API对一个“Java文件”(即源文件或class文件)的抽象；将源文件包装成这个类也就实现了“将java源文件放在内存中”的想法<br/>
<code>JavaCompiler compiler = ToolProvider.getSystemJavaCompiler();</code>这是取得一个默认的JavaCompiler工具的实例<br/>
由于我打算将编译好的class文件直接存放在内存中，因此我自定义了一个<code>MemClsFileManager</code>:</p>

<pre><code>public class MemClsFileManager extends ForwardingJavaFileManager&lt;StandardJavaFileManager&gt; {

    private Map&lt;String, JavaMemCls&gt;       destFiles;
    private Map&lt;String, JavaStringSource&gt; srcFiles;

    protected MemClsFileManager(StandardJavaFileManager fileManager, Map&lt;String, JavaMemCls&gt; destFiles,
                                Map&lt;String, JavaStringSource&gt; srcFiles){
        super(fileManager);
        this.destFiles = destFiles;
        this.srcFiles = srcFiles;
    }

    public JavaFileObject getJavaFileForOutput(Location location, String className, Kind kind, FileObject sibling)
                                                                                                                  throws IOException {
        if (!(Kind.CLASS.equals(kind) &amp;&amp; StandardLocation.CLASS_OUTPUT.equals(location))) return super.getJavaFileForOutput(location,
                                                                                                                            className,
                                                                                                                            kind,
                                                                                                                            sibling);
        if (destFiles.containsKey(className)) {
            return destFiles.get(className);
        } else {
            JavaMemCls file = new JavaMemCls(className);
            this.destFiles.put(className, file);
            return file;
        }
    }

    public void close() throws IOException {
        super.close();
        this.destFiles = null;
    }

    public Iterable&lt;JavaFileObject&gt; list(Location location, String packageName, Set&lt;Kind&gt; kinds, boolean recurse)
                                                                                                                 throws IOException {
        List&lt;JavaFileObject&gt; ret = new ArrayList&lt;JavaFileObject&gt;();
        if ((StandardLocation.CLASS_OUTPUT.equals(location) || StandardLocation.CLASS_PATH.equals(location))
            &amp;&amp; kinds.contains(Kind.CLASS)) {
            for (Map.Entry&lt;String, JavaMemCls&gt; e : destFiles.entrySet()) {
                String pkgName = resolvePkgName(e.getKey());
                if (recurse) {
                    if (pkgName.contains(packageName)) ret.add(e.getValue());
                } else {
                    if (pkgName.equals(packageName)) ret.add(e.getValue());
                }
            }
        } else if (StandardLocation.SOURCE_PATH.equals(location) &amp;&amp; kinds.contains(Kind.SOURCE)) {
            for (Map.Entry&lt;String, JavaStringSource&gt; e : srcFiles.entrySet()) {
                String pkgName = resolvePkgName(e.getKey());
                if (recurse) {
                    if (pkgName.contains(packageName)) ret.add(e.getValue());
                } else {
                    if (pkgName.equals(packageName)) ret.add(e.getValue());
                }
            }
        }
        // 也包含super.list
        Iterable&lt;JavaFileObject&gt; superList = super.list(location, packageName, kinds, recurse);
        if (superList != null) for (JavaFileObject f : superList)
            ret.add(f);
        return ret;
    }

    private String resolvePkgName(String fullQualifiedClsName) {
        return fullQualifiedClsName.substring(0, fullQualifiedClsName.lastIndexOf('.'));
    }

    public String inferBinaryName(Location location, JavaFileObject file) {
        if (file instanceof JavaMemCls) {
            return ((JavaMemCls) file).getClsName();
        } else if (file instanceof JavaStringSource) {
            return ((JavaStringSource) file).getClsName();
        } else {
            return super.inferBinaryName(location, file);
        }
    }

}
</code></pre>

<p>其中最主要的步骤就是重写了<code>getJavaFileForOutput</code>方法，使其使用内存中的map来作为生成文件(class文件)的输出位置</p>

<pre><code>CompilationTask task = compiler.getTask(out, fileManager, diagnostics, options, null, ss);
boolean sucess = task.call();
</code></pre>

<p>上面这两行是创建了一个编译task，并调用<br/>
最后使用自定义ClassLoader来加载编译好的类并返回：</p>

<pre><code>HotCompileClassLoader loader = new HotCompileClassLoader(Util.getParentClsLoader(), clses);
Class&lt;?&gt; cls = null;
try {
    cls = loader.loadClass(qualifiedName);
} catch (ClassNotFoundException e) {
    throw new RuntimeException(e);
}
return new CompilationResult(cls, loader);
</code></pre>

<p>而该ClassLoader的实现关键在于“到内存中(即之前存放编译好的class的map中)加载字节码”：</p>

<pre><code>public class HotCompileClassLoader extends ClassLoader {

    private Map&lt;String, JavaMemCls&gt; inMemCls;

    public HotCompileClassLoader(ClassLoader parent, Map&lt;String, JavaMemCls&gt; clses){
        super(parent);
        this.inMemCls = clses;
    }

    protected Class&lt;?&gt; findClass(String name) throws ClassNotFoundException {
        byte[] b = this.inMemCls.get(name).getClsBytes();
        return defineClass(name, b, 0, b.length);
    }

}
</code></pre>

<p>之后只要调用方法<code>compile(className, source, null)</code>这样就算完成了一个基本的、不依赖实际的文件系统的动态编译过程</p>

<h3>JavaFileManager的意义</h3>

<p>一个广义的、管理“文件”资源的接口，并不一定指“操作系统的磁盘文件系统”<br/>
其实<code>JavaFileManager</code>只是一个接口，只要行为正确，那么就无所谓“文件”到底以何种形式、实际被存放在哪里</p>

<h2>StandardJavaFileManager的默认行为</h2>

<p>这是基于磁盘文件的JavaFileManager实现, 所有的文件查找、新文件输出位置都在磁盘上完成；也就是说，如果直接使用默认的<code>StandardJavaFileManager</code>来做动态编译，那么得到的效果就跟命令行中直接使用javac编译差不多</p>

<h2>继承ForwardingJavaFileManager类，让compiler API脱离对文件系统的依赖</h2>

<p>如果想要将编译好的class文件放在内存中而不是磁盘上，那么需要使用一个<code>ForwardingJavaFileManager</code>来包装默认的<code>StandardJavaFileManager</code>并重写<code>getJavaFileForOutput</code>方法，将其实现改为内存操作；这个实现可参考上面的<code>MemClsFileManager</code>类<br/>
不过<code>ForwardingJavaFileManager</code>还有许多别的方法，没有文档说明动态编译过程中到底那些方法会被调用,原则上讲，所有方法都有可能被调用<br/>
但具体哪些方法被调用了可以被实测出来，这样可以有选择性地重写其中一些方法<br/>
比如<code>MemClsFileManager</code>中，重写了<code>inferBinaryName</code>, <code>list</code>, <code>close</code>, <code>getJavaFileForOutput</code>方法，因为这些方法都会被“class文件放在内存中”这一策略所影响，所以需要兼容</p>

<h1>JavaCompiler Tree API</h1>

<p>下面想介绍的其实是另一个更进一步的话题：如何在动态编译的过程中分析被编译的源代码<br/>
因为几乎所有打算用到java动态编译的应用场景，都会想要对被编译的代码做一些检查、review，以防编译运行了让人出乎意料的代码从而对系统造成破坏<br/>
那么这个事情，除了人工review之外，一些简单的验证，完全可以在编译期自动地做到；而JavaCompiler Tree API就是用来做这个静态编译期检查的<br/>
它的基本思路很简单，就是hook进编译的过程中，在java源码被parse成<a href="http://en.wikipedia.org/wiki/Abstract_syntax_tree">AST</a>的时候，使用visitor模式对该AST做遍历分析，以找出你需要定位的语法结构，这样来达到验证目的; 比如&#8221;如果发现assert语句就报错&#8221;或“不允许定义嵌套类”这样的检查都很容易做<br/>
这之中的关键，当然是java的AST和其对应的visitor的实现了</p>

<h2>Java的AST:</h2>

<p><a href="http://docs.oracle.com/javase/7/docs/jdk/api/javac/tree/com/sun/source/tree/package-summary.html">http://docs.oracle.com/javase/7/docs/jdk/api/javac/tree/com/sun/source/tree/package-summary.html</a><br/>
上述链接给出了java的AST类结构，所有语法元素的节点都有<br/>
而对应的visitor接口<code>TreeVisitor&lt;R,P&gt;</code>与AST形成了标准的visitor模式<br/>
<code>TreeVisitor&lt;R,P&gt;</code>的默认实现及其用途:</p>

<ol>
<li>SimpleTreeVisitor: 简单的、“消极”的visitor实现，当访问一个分支节点时不会默认“往下”继续遍历它的所有子节点, 若想要遍历所有子节点需要继承、编码实现</li>
<li>TreeScanner: 默认会遍历所有子节点的“积极”的visitor实现，还能让当前节点的遍历逻辑取到上一个被访问的邻接兄弟节点被访问的返回结果(换句话说能够拿到最近的、刚才被访问过的兄弟节点对象，或其它等效的自定义返回值)</li>
<li>TreePathScanner: 跟TreeScanner一样“积极”，且除了能拿到前一个邻接兄弟节点的访问返回结果外，还能拿到父亲节点(这样来追踪该节点的路径)</li>
</ol>


<p>有了上面这个visitor模式的脚手架，我们就能通过实现一个visitor来达到对java源码的分析了<br/>
比如下面这个visitor, 它继承自<code>TreePathScanner</code>(<code>ExprCodeChecker</code>是我自定义的一个<code>TreePathScanner</code>的子类)：</p>

<pre><code>public class ForbiddenStructuresChecker extends ExprCodeChecker&lt;Void, FbdStructContext&gt; {

    private StringBuilder errMsg = new StringBuilder();

    public String getErrorMsg() {
        return this.errMsg.toString();
    }

    public FbdStructContext getInitParam() {
        return new FbdStructContext();
    }

    /**
     * 禁止定义内部类
     */
    public Void visitClass(ClassTree node, FbdStructContext p) {
        if (p.isInClass) {
            // 已经位于另一个外层class定义中了，直接报错返回，不再继续遍历子节点
            this.errMsg.append("Nested class is not allowed in api expressions. Position: " + resolveRowAndCol(node)).append('\n');
            return null;
        } else {
            boolean oldInClass = p.isInClass;
            p.isInClass = true;
            // 继续遍历子节点
            super.visitClass(node, p);
            p.isInClass = oldInClass;
            return null;
        }

    }

    /**
     * 禁止定义'assert'语句
     */
    public Void visitAssert(AssertTree node, FbdStructContext p) {
        this.errMsg.append("Assertions are not allowed in api expressions. Position: " + this.resolveRowAndCol(node)).append('\n');
        return null;
    }

    /**
     * 禁止定义goto(break or continue followed by a label)语句
     */
    public Void visitBreak(BreakTree node, FbdStructContext p) {
        if (node.getLabel() != null) {
            this.errMsg.append("'break' followed by a label is not allowed in api expressions. Position: "
                                       + this.resolveRowAndCol(node)).append('\n');
            return null;
        } else {
            return super.visitBreak(node, p);
        }
    }

    public Void visitContinue(ContinueTree node, FbdStructContext p) {
        if (node.getLabel() != null) {
            this.errMsg.append("'continue' followed by a label is not allowed in api expressions. Position: "
                                       + this.resolveRowAndCol(node)).append('\n');
            return null;
        } else {
            return super.visitContinue(node, p);
        }
    }

    // *************禁止定义goto end*************

    /**
     * 禁止定义死循环，for/while/do-while loop, 只限制常量类型的循环条件造成的明显死循环; 这种静态校验是不完善的，要做完善很复杂，没必要加大投入；若要做到更精确的控制应从动态期方案的方向考虑
     */
    public Void visitDoWhileLoop(DoWhileLoopTree node, FbdStructContext p) {
        boolean condTemp = p.isConstantTrueCondition;
        boolean isLoopExpTemp = p.isLoopConditionExpr;

        p.isLoopConditionExpr = true;
        node.getCondition().accept(this, p);

        if (p.isConstantTrueCondition) {
            // 死循环
            this.errMsg.append("Dead loop is not allowed in api expressions. Position: " + this.resolveRowAndCol(node)).append('\n');
        }
        p.isConstantTrueCondition = condTemp;
        p.isLoopConditionExpr = isLoopExpTemp;

        return super.visitDoWhileLoop(node, p);
    }

    public Void visitForLoop(ForLoopTree node, FbdStructContext p) {
        if (node.getCondition() == null) {
            // 无条件，相当于'true'
            this.errMsg.append("Dead loop is not allowed in api expressions. Position: " + this.resolveRowAndCol(node)).append('\n');
        } else {
            boolean condTemp = p.isConstantTrueCondition;
            boolean isLoopExpTemp = p.isLoopConditionExpr;

            p.isLoopConditionExpr = true;
            node.getCondition().accept(this, p);

            if (p.isConstantTrueCondition) {
                // 死循环
                this.errMsg.append("Dead loop is not allowed in api expressions. Position: "
                                           + this.resolveRowAndCol(node)).append('\n');
            }
            p.isConstantTrueCondition = condTemp;
            p.isLoopConditionExpr = isLoopExpTemp;
        }
        return super.visitForLoop(node, p);
    }

    public Void visitWhileLoop(WhileLoopTree node, FbdStructContext p) {
        boolean condTemp = p.isConstantTrueCondition;
        boolean isLoopExpTemp = p.isLoopConditionExpr;

        p.isLoopConditionExpr = true;
        node.getCondition().accept(this, p);

        if (p.isConstantTrueCondition) {
            // 死循环
            this.errMsg.append("Dead loop is not allowed in api expressions. Position: " + this.resolveRowAndCol(node)).append('\n');
        }

        p.isConstantTrueCondition = condTemp;
        p.isLoopConditionExpr = isLoopExpTemp;

        return super.visitWhileLoop(node, p);
    }

    // 处理循环条件, 需要关心结果为boolean值的表达式
    // 二元表达式
    public Void visitBinary(BinaryTree node, FbdStructContext p) {
        boolean isLoopCondTemp = p.isLoopConditionExpr;

        // 求左值
        p.isLoopConditionExpr = false;
        node.getLeftOperand().accept(this, p);
        p.isLoopConditionExpr = isLoopCondTemp;
        Object leftVal = p.expValue;

        // 求右值
        p.isLoopConditionExpr = false;
        node.getRightOperand().accept(this, p);
        p.isLoopConditionExpr = isLoopCondTemp;
        Object rightVal = p.expValue;

        // 求整体值
        Object val = null;
        if (leftVal != null &amp;&amp; rightVal != null) switch (node.getKind()) {
            case MULTIPLY:
                val = ((Number) leftVal).doubleValue() * ((Number) rightVal).doubleValue();
                break;
            case DIVIDE:
                val = ((Number) leftVal).doubleValue() / ((Number) rightVal).doubleValue();
                break;
            case REMAINDER:
                val = ((Number) leftVal).intValue() % ((Number) rightVal).intValue();
                break;
            case PLUS:
                if (leftVal instanceof Number &amp;&amp; rightVal instanceof Number) {
                    val = ((Number) leftVal).doubleValue() + ((Number) rightVal).doubleValue();
                } else {
                    val = String.valueOf(leftVal) + String.valueOf(rightVal);
                }
                break;
            case MINUS:
                val = ((Number) leftVal).doubleValue() - ((Number) rightVal).doubleValue();
                break;
            case LEFT_SHIFT:
                val = ((Number) leftVal).longValue() &lt;&lt; ((Number) rightVal).intValue();
                break;
            case RIGHT_SHIFT:
                val = ((Number) leftVal).longValue() &gt;&gt; ((Number) rightVal).intValue();
                break;
            case UNSIGNED_RIGHT_SHIFT:
                val = ((Number) leftVal).longValue() &gt;&gt;&gt; ((Number) rightVal).intValue();
                break;
            case LESS_THAN:
                val = ((Number) leftVal).doubleValue() &lt; ((Number) rightVal).doubleValue();
                break;
            case GREATER_THAN:
                val = ((Number) leftVal).doubleValue() &gt; ((Number) rightVal).doubleValue();
                break;
            case LESS_THAN_EQUAL:
                val = ((Number) leftVal).doubleValue() &lt;= ((Number) rightVal).doubleValue();
                break;
            case GREATER_THAN_EQUAL:
                val = ((Number) leftVal).doubleValue() &gt;= ((Number) rightVal).doubleValue();
                break;
            case EQUAL_TO:
                val = leftVal == rightVal;
                break;
            case NOT_EQUAL_TO:
                val = leftVal != rightVal;
                break;
            case AND:
                if (leftVal instanceof Number) {
                    val = ((Number) leftVal).longValue() &amp; ((Number) rightVal).longValue();
                } else {
                    val = ((Boolean) leftVal) &amp; ((Boolean) rightVal);
                }
                break;
            case XOR:
                if (leftVal instanceof Number) {
                    val = ((Number) leftVal).longValue() ^ ((Number) rightVal).longValue();
                } else {
                    val = ((Boolean) leftVal) ^ ((Boolean) rightVal);
                }
                break;
            case OR:
                if (leftVal instanceof Number) {
                    val = ((Number) leftVal).longValue() | ((Number) rightVal).longValue();
                } else {
                    val = ((Boolean) leftVal) | ((Boolean) rightVal);
                }
                break;
            case CONDITIONAL_AND:
                val = ((Boolean) leftVal) &amp;&amp; ((Boolean) rightVal);
                break;
            case CONDITIONAL_OR:
                val = ((Boolean) leftVal) || ((Boolean) rightVal);
                break;
            default:
                val = null;
        }

        if (p.isLoopConditionExpr) {
            if (val != null &amp;&amp; val instanceof Boolean &amp;&amp; (Boolean) val) p.isConstantTrueCondition = true;
        } else {
            p.expValue = val;
        }
        return null;
    }

    // 3元条件表达式
    public Void visitConditionalExpression(ConditionalExpressionTree node, FbdStructContext p) {
        boolean isLoopCondTemp = p.isLoopConditionExpr;

        p.isLoopConditionExpr = false;
        node.getCondition().accept(this, p);
        p.isLoopConditionExpr = isLoopCondTemp;

        Object val = null;
        if (p.expValue != null) {
            if ((Boolean) p.expValue) {
                // 取true expr值
                p.isLoopConditionExpr = false;
                node.getTrueExpression().accept(this, p);
                p.isLoopConditionExpr = isLoopCondTemp;
                val = p.expValue;
            } else {
                // 取false expr值
                p.isLoopConditionExpr = false;
                node.getFalseExpression().accept(this, p);
                p.isLoopConditionExpr = isLoopCondTemp;
                val = p.expValue;
            }
        }

        if (p.isLoopConditionExpr) {
            p.isConstantTrueCondition = val != null &amp;&amp; val instanceof Boolean &amp;&amp; (Boolean) val;
        } else {
            p.expValue = val;
        }
        return null;
    }

    // 常量
    public Void visitLiteral(LiteralTree node, FbdStructContext p) {
        if (p.isLoopConditionExpr) {
            p.isConstantTrueCondition = Boolean.TRUE.equals(node.getValue());
        } else {
            p.expValue = node.getValue();
        }
        return null;
    }

    // 括起来的表达式
    public Void visitParenthesized(ParenthesizedTree node, FbdStructContext p) {
        boolean isLoopCondTemp = p.isLoopConditionExpr;
        if (p.isLoopConditionExpr) {
            // 求值子表达式
            p.isLoopConditionExpr = false;
            node.getExpression().accept(this, p);
            p.isLoopConditionExpr = isLoopCondTemp;
            if (p.expValue != null &amp;&amp; Boolean.TRUE.equals(p.expValue)) p.isConstantTrueCondition = true;
        } else {
            // 直接以子表达式的结果作为括号表达式的结果
            p.isLoopConditionExpr = false;
            node.getExpression().accept(this, p);
            p.isLoopConditionExpr = isLoopCondTemp;
        }
        return null;
    }

    // 类型转换表达式
    public Void visitTypeCast(TypeCastTree node, FbdStructContext p) {
        boolean isLoopCondTemp = p.isLoopConditionExpr;

        if (p.isLoopConditionExpr) {
            p.isLoopConditionExpr = false;
            node.getExpression().accept(this, p);
            p.isLoopConditionExpr = isLoopCondTemp;

            if (p.expValue != null
                &amp;&amp; ("Boolean".equals(node.getType().toString()) || "boolean".equals(node.getType().toString()))) p.isConstantTrueCondition = true;
        } else {
            p.isLoopConditionExpr = false;
            node.getExpression().accept(this, p);
            p.isLoopConditionExpr = isLoopCondTemp;
        }
        return null;
    }

    // 一元表达式
    public Void visitUnary(UnaryTree node, FbdStructContext p) {
        boolean isLoopCondTemp = p.isLoopConditionExpr;

        // 求子表达式值
        p.isLoopConditionExpr = false;
        node.getExpression().accept(this, p);
        p.isLoopConditionExpr = isLoopCondTemp;

        Object val = null;
        if (p.expValue != null) {
            switch (node.getKind()) {
                case POSTFIX_INCREMENT:
                case POSTFIX_DECREMENT:
                case PREFIX_INCREMENT:
                case PREFIX_DECREMENT:
                    val = null;
                    break;
                case UNARY_PLUS:
                    val = p.expValue;
                    break;
                case UNARY_MINUS:
                    val = -((Number) p.expValue).doubleValue();
                    break;
                case BITWISE_COMPLEMENT:
                    val = ~((Number) p.expValue).longValue();
                    break;
                case LOGICAL_COMPLEMENT:
                    val = !((Boolean) p.expValue);
                    break;
                default:
                    val = null;
            }
        }
        if (p.isLoopConditionExpr) {
            if (val != null &amp;&amp; val instanceof Boolean &amp;&amp; (Boolean) val) p.isConstantTrueCondition = true;
        } else {
            p.expValue = val;
        }
        return null;
    }
    // *************禁止定义死循环end*************
}
</code></pre>

<ul>
<li>上述visitor通过对<code>visitClass</code>的处理，对“定义嵌套类”这种行为进行了报错</li>
<li>通过对<code>visitAssert</code>的处理，凡是遇到代码中出现<code>assert</code>语句的，均给出错误信息</li>
<li>通过对<code>visitBreak</code>和<code>visitContinue</code>的处理禁止了goto语句(即带label的break和continue语句)</li>
<li>通过对<code>visitDoWhileLoop</code>等循环语法结构的访问，以及部分表达式结构的访问(如<code>visitBinary</code>、<code>visitLiteral</code>)，禁止了如<code>while(true)</code>、<code>for(;;)</code>或<code>while(1&lt;2)</code>等明显死循环</li>
</ul>


<h2>在什么阶段能将Java代码转化为AST从而被TreeVisitor分析？</h2>

<p>接下来的问题就是：我们有了处理AST的visitor，那么到底要在什么时候运行它呢？<br/>
答案就是使用jdk1.6的PluggableAnnotationProcessor机制, 在创建compilerTask时设置对应的Processor, 然后在该Processor中调用我们的visitor<br/>
下面是我们的processor实现：</p>

<pre><code>@SupportedSourceVersion(SourceVersion.RELEASE_6)
@SupportedAnnotationTypes("*")
public class ExprCodeCheckProcessor extends AbstractProcessor {

    // 工具实例类，用于将CompilerAPI, CompilerTreeAPI和AnnotationProcessing框架粘合起来
    private Trees                       trees;
    // 分析过程中可用的日志、信息打印工具
    private Messager                    messager;

    // 所有的CodeChecker
    private List&lt;ExprCodeChecker&lt;?, ?&gt;&gt; codeCheckers = new ArrayList&lt;ExprCodeChecker&lt;?, ?&gt;&gt;();

    // 搜集错误信息
    private StringBuilder               errMsg       = new StringBuilder();

    // 代码检查是否成功, 若false, 则'errMsg'里应该有具体错误信息
    private boolean                     success      = true;

    /**
     * ==============在这里列出所有的checker实例==============
     */
    public ExprCodeCheckProcessor(){
        // 检查 —— 禁止定义一些不必要的结构，如内部类
        this.codeCheckers.add(new ForbiddenStructuresChecker());
    }

    public synchronized void init(ProcessingEnvironment processingEnv) {
        super.init(processingEnv);
        this.trees = Trees.instance(processingEnv);
        this.messager = processingEnv.getMessager();
        // 为所有checker置入工具实例
        for (ExprCodeChecker&lt;?, ?&gt; c : this.codeCheckers) {
            c.setTrees(trees);
            c.setMessager(messager);
        }
    }

    public boolean process(Set&lt;? extends TypeElement&gt; annotations, RoundEnvironment env) {
        if (!env.processingOver()) for (Element e : env.getRootElements()) {
            for (ExprCodeChecker&lt;?, ?&gt; c : this.codeCheckers) {
                c.check(this.trees.getPath(e));
                if (!c.isSuccess()) {
                    this.success = false;
                    this.errMsg.append(c.getErrorMsg()).append('\n');
                }
            }
        }
        /*
         * 这里若return true将阻止任何后续可能存在的Processor的运行，因此这里可以固定返回false
         */
        return false;
    }

    /**
     * 获取代码检查的错误信息
     * 
     * @return
     */
    public String getErrMsg() {
        return errMsg.toString();
    }

    /**
     * 指示代码检查过程是否成功，若为false，则可调用getErrMsg取得具体错误信息
     * 
     * @return
     */
    public boolean isSuccess() {
        return success;
    }
}
</code></pre>

<p>这里面关键的就是实现<code>init</code>方法和<code>process</code>方法<br/>
<code>init</code>方法初始化了<code>Trees</code>工具并将其设置到了所有的<code>ExprCodeChecker</code>(其实就是visitor)中; Trees是一个很重要的工具类实例，它能帮助我们获取AST结构对应的行号、列号等重要信息<br/>
<code>process</code>方法则是真正对源码进行处理，在这里，真正调用了所有的<code>ExprCodeChecker</code>(也就是visitor)<br/>
然后在使用Compiler API的时候，将processor设置到<code>CompilationTask</code>中即可：</p>

<pre><code>CompilationTask task = compiler.getTask(out, fileManager, diagnostics, options, null, ss);
if (processors != null) task.setProcessors(processors);
</code></pre>

<p>顺便贴下<code>ExprCodeChecker</code>的代码如下，它就是一个对<code>TreePathScanner</code>的简单继承，封装了一些代码分析过程中的基本属性和常用方法, 所有的visitor只要继承自它就可以了:</p>

<pre><code>public abstract class ExprCodeChecker&lt;R, P&gt; extends TreePathScanner&lt;R, P&gt; {

    // 当前被扫描代码对应的节点转换工具类, 运行时由Processor负责置入
    protected Trees    trees;
    // 错误信息打印、处理流程控制工具, 运行时由Processor负责置入
    protected Messager messager;

    /**
     * 取得代码检查的错误信息, 返回结果为null或空字符串串则表示无错误, 否则认为有错误发生
     * 
     * @return
     */
    public abstract String getErrorMsg();

    /**
     * 取得初始参数
     * 
     * @return 用于遍历代码树的初始参数
     */
    protected abstract P getInitParam();

    /**
     * 代码检查是否成功
     * 
     * @return true - 成功，无问题； false - 失败，调用getErrorMsg可获取错误信息
     */
    final boolean isSuccess() {
        String err = this.getErrorMsg();
        return err == null || err.length() == 0;
    }

    /**
     * package访问权限，专门用于由Processor置入Trees工具实例
     * 
     * @param trees
     */
    final void setTrees(Trees trees) {
        this.trees = trees;
    }

    /**
     * package访问权限，专门用于由Processor置入Messager工具实例
     * 
     * @param messager
     */
    final void setMessager(Messager messager) {
        this.messager = messager;
    }

    /**
     * 开始遍历处理传入的代码树节点
     * 
     * @param path
     */
    final void check(TreePath path) {
        this.scan(path, getInitParam());
    }

    /**
     * 获取指定语法节点缩在源文件中的行号和列号信息, 用于错误信息输出
     * 
     * @param node
     * @return
     */
    protected final String resolveRowAndCol(Tree node) {
        CompilationUnitTree unit = this.getCurrentPath().getCompilationUnit();
        long pos = this.trees.getSourcePositions().getStartPosition(unit, node);
        LineMap m = unit.getLineMap();
        return "row: " + m.getLineNumber(pos) + ", col: " + m.getColumnNumber(pos);
    }

}
</code></pre>

<p>其中<code>check</code>方法是遍历分析的起点，由processor调用<br/>
<code>resolveRowAndCol</code>则是获取AST节点对应的行号、列号的方法，用于输出错误信息</p>

<h2>使用trees.getSourcePositions()获取节点的源码位置,以及LineMap获得指定位置的行号、列号</h2>

<p>在processor的init方法中被置入的Trees工具实例，最大的用处就是获取对应AST节点的行号、列号，具体代码参见上述<code>resolveRowAndCol</code>方法</p>

<h2>JavaCompiler Tree API的限制</h2>

<p>有必要讨论下什么样的控制，适合用Tree API来做？<br/>
总结起来应该是：静态的、简单的<br/>
比如“不能定义内部类”、“不能写annotation”、“不能写assert语句”等<br/>
随着需求的复杂度增高，使用Tree API的编码成本也会增高，毕竟使用visitor来分析复杂的AST模式并非十分容易的事情<br/>
比如上面的例子，“限制死循环”这种需求；如果说非常简单的死循环，比如<code>while(true)</code>，这种是非常好做的<br/>
但如果稍微复杂一点, 比如<code>while(1&lt;2)</code>，那么这里势必会牵涉到一个&#8221;计算&#8221;过程，我们需要在分析过程中对<code>1&lt;2</code>这个表达式做出计算，从而知晓该循环语句是否死循环;虽然人眼对<code>1&lt;2</code>的结果一目了然，但这里靠程序来做的话，增加的复杂度还是相当可观的<br/>
如果在继续复杂下去，可以想象，其开发成本会越来越高，且这个分析过程本身的“运行”成本也会越来越接近真正运行这段被分析的代码的成本，这个时候使用Tree API来做分析就不划算了  <br/>
所以说，考虑到成本因素，Tree API并不适合做太复杂的分析<br/>
其次就是&#8221;静态的&#8221;代码，才能在编译期做分析，如果是这样的代码:<code>while(x&lt;1)</code>，而<code>x</code>又是从方法参数中传入，那么<code>x</code>的值就完全在运行期才能确定，那么Tree API就无法判断该循环是否是死循环</p>

<p>还有就是Tree API很容易让人联想到一个问题：可否在遍历AST的过程中改变AST的结构？<br/>
这是个激动人心的话题，运行期改变源码的AST是一个想象空间很大的想法，就像在groovy和ruby中能办到的那样，这能成为一种强大的元编程机制<br/>
不过，从java的Tree API规范上讲，是不能在遍历AST过程中修改AST的结构的，但目前有一个bug可以做到：<a href="http://scg.unibe.ch/archive/projects/Erni08b.pdf">Erni08b.pdf</a><br/>
并且目前的<a href="http://projectlombok.org/">Project Lombok</a>就是基于此bug实现; 就未来的版本发展来讲，利用此bug来实现功能是不可靠的, Project Lombok的开发者对此也表示担心<br/>
不过这个bug也不失为一种必要时的选择，毕竟通过它能实现的功能很酷</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[近期hessian反序列化问题总结与ThreadPoolExecutor使用心得]]></title>
    <link href="http://pfmiles.github.io/blog/recently-hessian-deserialize-problem-and-thread-pool-executor-experience"/>
    <updated>2013-05-05T14:53:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/recently-hessian-deserialize-problem-and-thread-pool-executor-experience</id>
    <content type="html"><![CDATA[<p>最近工作中遇到一个诡异的问题：别人远程调用我们的系统暴露的服务，同步调用，底层使用hessian协议做序列化；<br/>
调用方系统报空指针，反序列化失败：</p>

<!-- more -->


<pre><code>2013-04-18 16:52:10,308 [AvatarRuleChargeService.java:74] [com.alibaba.itbu.billing.biz.adaptor.avatar.AvatarRuleChargeService] ERROR com.alibaba.itbu.billing.biz.adaptor.crm.ChargeProxy :: avatar charge sys error
com.alibaba.dubbo.rpc.RpcException: Failed to invoke the method match in the service com.alibaba.china.ruleservice.RuleService. Tried 3 times of the providers [172.22.6.83:20980, 172.22.6.80:20980, 172.22.9.76:20980] (3/3) from the registry dubbo-reg1.hst.xyi.cn.alidc.net:9090 on the consumer 172.30.118.26 using the dubbo version 2.4.9. Last error is: Failed to invoke remote method: match, provider: dubbo://172.22.6.83:20980/com.alibaba.china.ruleservice.RuleService?anyhost=true&amp;application=billing&amp;check=false&amp;default.reference.filter=dragoon&amp;dubbo=2.4.9&amp;interface=com.alibaba.china.ruleservice.RuleService&amp;methods=match&amp;pid=18616&amp;revision=1.0-SNAPSHOT&amp;side=consumer&amp;timeout=5000&amp;timestamp=1366275108588&amp;version=1.0.0, cause: com.alibaba.com.caucho.hessian.io.HessianProtocolException: 'com.alibaba.china.ruleservice.RuleServiceImpl$DynamicPluginInvocationMatchedResult' could not be instantiated
com.alibaba.com.caucho.hessian.io.HessianProtocolException: 'com.alibaba.china.ruleservice.RuleServiceImpl$DynamicPluginInvocationMatchedResult' could not be instantiated
    at com.alibaba.com.caucho.hessian.io.JavaDeserializer.instantiate(JavaDeserializer.java:275)
    at com.alibaba.com.caucho.hessian.io.JavaDeserializer.readObject(JavaDeserializer.java:155)
    at com.alibaba.com.caucho.hessian.io.SerializerFactory.readObject(SerializerFactory.java:396)
    at com.alibaba.com.caucho.hessian.io.Hessian2Input.readObjectInstance(Hessian2Input.java:2070)
    at com.alibaba.com.caucho.hessian.io.Hessian2Input.readObject(Hessian2Input.java:2005)
    at com.alibaba.com.caucho.hessian.io.Hessian2Input.readObject(Hessian2Input.java:1990)
    at com.alibaba.com.caucho.hessian.io.Hessian2Input.readObject(Hessian2Input.java:1538)
    at com.alibaba.dubbo.common.serialize.support.hessian.Hessian2ObjectInput.readObject(Hessian2ObjectInput.java:94)
    at com.alibaba.dubbo.common.serialize.support.hessian.Hessian2ObjectInput.readObject(Hessian2ObjectInput.java:99)
    at com.alibaba.dubbo.rpc.protocol.dubbo.DecodeableRpcResult.decode(DecodeableRpcResult.java:83)
    at com.alibaba.dubbo.rpc.protocol.dubbo.DecodeableRpcResult.decode(DecodeableRpcResult.java:109)
    at com.alibaba.dubbo.rpc.protocol.dubbo.DubboCodec.decodeBody(DubboCodec.java:97)
    at com.alibaba.dubbo.remoting.exchange.codec.ExchangeCodec.decode(ExchangeCodec.java:128)
    at com.alibaba.dubbo.remoting.exchange.codec.ExchangeCodec.decode(ExchangeCodec.java:87)
    at com.alibaba.dubbo.rpc.protocol.dubbo.DubboCountCodec.decode(DubboCountCodec.java:49)
    at com.alibaba.dubbo.remoting.transport.netty.NettyCodecAdapter$InternalDecoder.messageReceived(NettyCodecAdapter.java:135)
    at org.jboss.netty.channel.SimpleChannelUpstreamHandler.handleUpstream(SimpleChannelUpstreamHandler.java:80)
    at org.jboss.netty.channel.DefaultChannelPipeline.sendUpstream(DefaultChannelPipeline.java:564)
    at org.jboss.netty.channel.DefaultChannelPipeline.sendUpstream(DefaultChannelPipeline.java:559)
    at org.jboss.netty.channel.Channels.fireMessageReceived(Channels.java:274)
    at org.jboss.netty.channel.Channels.fireMessageReceived(Channels.java:261)
    at org.jboss.netty.channel.socket.nio.NioWorker.read(NioWorker.java:349)
    at org.jboss.netty.channel.socket.nio.NioWorker.processSelectedKeys(NioWorker.java:280)
    at org.jboss.netty.channel.socket.nio.NioWorker.run(NioWorker.java:200)
    at org.jboss.netty.util.ThreadRenamingRunnable.run(ThreadRenamingRunnable.java:108)
    at org.jboss.netty.util.internal.DeadLockProofWorker$1.run(DeadLockProofWorker.java:44)
    at java.util.concurrent.ThreadPoolExecutor$Worker.runTask(ThreadPoolExecutor.java:886)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:908)
    at java.lang.Thread.run(Thread.java:662)
Caused by: java.lang.reflect.InvocationTargetException
    at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
    at sun.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:39)
    at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:27)
    at java.lang.reflect.Constructor.newInstance(Constructor.java:513)
    at com.alibaba.com.caucho.hessian.io.JavaDeserializer.instantiate(JavaDeserializer.java:271)
    ... 28 more
Caused by: java.lang.NullPointerException
    at com.alibaba.china.ruleservice.RuleServiceImpl$DynamicPluginInvocationMatchedResult.&lt;init&gt;(RuleServiceImpl.java:163)
    ... 33 more

    at com.alibaba.dubbo.rpc.cluster.support.FailoverClusterInvoker.doInvoke(FailoverClusterInvoker.java:101)
    at com.alibaba.dubbo.rpc.cluster.support.AbstractClusterInvoker.invoke(AbstractClusterInvoker.java:226)
    at com.alibaba.dubbo.rpc.cluster.support.wrapper.MockClusterInvoker.invoke(MockClusterInvoker.java:72)
    at com.alibaba.dubbo.rpc.proxy.InvokerInvocationHandler.invoke(InvokerInvocationHandler.java:52)
    at com.alibaba.dubbo.common.bytecode.proxy1.match(proxy1.java)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
    at java.lang.reflect.Method.invoke(Method.java:597)
    at org.springframework.aop.support.AopUtils.invokeJoinpointUsingReflection(AopUtils.java:307)
    at org.springframework.aop.framework.ReflectiveMethodInvocation.invokeJoinpoint(ReflectiveMethodInvocation.java:182)
    at org.springframework.aop.framework.ReflectiveMethodInvocation.proceed(ReflectiveMethodInvocation.java:149)
    at org.springframework.aop.aspectj.MethodInvocationProceedingJoinPoint.proceed(MethodInvocationProceedingJoinPoint.java:88)
    at com.alibaba.itbu.billing.framework.aop.OpenApiLogAspect.logExecuteTime(OpenApiLogAspect.java:38)
    at sun.reflect.GeneratedMethodAccessor199.invoke(Unknown Source)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
    at java.lang.reflect.Method.invoke(Method.java:597)
    at org.springframework.aop.aspectj.AbstractAspectJAdvice.invokeAdviceMethodWithGivenArgs(AbstractAspectJAdvice.java:627)
    at org.springframework.aop.aspectj.AbstractAspectJAdvice.invokeAdviceMethod(AbstractAspectJAdvice.java:616)
    at org.springframework.aop.aspectj.AspectJAroundAdvice.invoke(AspectJAroundAdvice.java:64)
    at org.springframework.aop.framework.ReflectiveMethodInvocation.proceed(ReflectiveMethodInvocation.java:171)
    at org.springframework.aop.interceptor.ExposeInvocationInterceptor.invoke(ExposeInvocationInterceptor.java:89)
    at org.springframework.aop.framework.ReflectiveMethodInvocation.proceed(ReflectiveMethodInvocation.java:171)
    at org.springframework.aop.framework.JdkDynamicAopProxy.invoke(JdkDynamicAopProxy.java:204)
    at $Proxy107.match(Unknown Source)
    at com.alibaba.itbu.billing.biz.adaptor.avatar.AvatarRuleChargeService.chargeByFactor(AvatarRuleChargeService.java:72)
    at com.alibaba.itbu.billing.biz.charge.times.RuleChargeByTimesProcessor.getChargeResult(RuleChargeByTimesProcessor.java:62)
    at com.alibaba.itbu.billing.biz.charge.times.ChargeByTimesProcessor.charge(ChargeByTimesProcessor.java:117)
    at com.alibaba.itbu.billing.biz.task.ChargeByIncInstantTimesTask.charge(ChargeByIncInstantTimesTask.java:174)
    at com.alibaba.itbu.billing.biz.task.ChargeByIncInstantTimesTask$1.run(ChargeByIncInstantTimesTask.java:109)
    at java.util.concurrent.ThreadPoolExecutor$Worker.runTask(ThreadPoolExecutor.java:886)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:908)
    at java.lang.Thread.run(Thread.java:662)
Caused by: com.alibaba.dubbo.remoting.RemotingException: com.alibaba.com.caucho.hessian.io.HessianProtocolException: 'com.alibaba.china.ruleservice.RuleServiceImpl$DynamicPluginInvocationMatchedResult' could not be instantiated
com.alibaba.com.caucho.hessian.io.HessianProtocolException: 'com.alibaba.china.ruleservice.RuleServiceImpl$DynamicPluginInvocationMatchedResult' could not be instantiated
    at com.alibaba.com.caucho.hessian.io.JavaDeserializer.instantiate(JavaDeserializer.java:275)
    at com.alibaba.com.caucho.hessian.io.JavaDeserializer.readObject(JavaDeserializer.java:155)
    at com.alibaba.com.caucho.hessian.io.SerializerFactory.readObject(SerializerFactory.java:396)
    at com.alibaba.com.caucho.hessian.io.Hessian2Input.readObjectInstance(Hessian2Input.java:2070)
    at com.alibaba.com.caucho.hessian.io.Hessian2Input.readObject(Hessian2Input.java:2005)
    at com.alibaba.com.caucho.hessian.io.Hessian2Input.readObject(Hessian2Input.java:1990)
    at com.alibaba.com.caucho.hessian.io.Hessian2Input.readObject(Hessian2Input.java:1538)
    at com.alibaba.dubbo.common.serialize.support.hessian.Hessian2ObjectInput.readObject(Hessian2ObjectInput.java:94)
    at com.alibaba.dubbo.common.serialize.support.hessian.Hessian2ObjectInput.readObject(Hessian2ObjectInput.java:99)
    at com.alibaba.dubbo.rpc.protocol.dubbo.DecodeableRpcResult.decode(DecodeableRpcResult.java:83)
    at com.alibaba.dubbo.rpc.protocol.dubbo.DecodeableRpcResult.decode(DecodeableRpcResult.java:109)
    at com.alibaba.dubbo.rpc.protocol.dubbo.DubboCodec.decodeBody(DubboCodec.java:97)
    at com.alibaba.dubbo.remoting.exchange.codec.ExchangeCodec.decode(ExchangeCodec.java:128)
    at com.alibaba.dubbo.remoting.exchange.codec.ExchangeCodec.decode(ExchangeCodec.java:87)
    at com.alibaba.dubbo.rpc.protocol.dubbo.DubboCountCodec.decode(DubboCountCodec.java:49)
    at com.alibaba.dubbo.remoting.transport.netty.NettyCodecAdapter$InternalDecoder.messageReceived(NettyCodecAdapter.java:135)
    at org.jboss.netty.channel.SimpleChannelUpstreamHandler.handleUpstream(SimpleChannelUpstreamHandler.java:80)
    at org.jboss.netty.channel.DefaultChannelPipeline.sendUpstream(DefaultChannelPipeline.java:564)
    at org.jboss.netty.channel.DefaultChannelPipeline.sendUpstream(DefaultChannelPipeline.java:559)
    at org.jboss.netty.channel.Channels.fireMessageReceived(Channels.java:274)
    at org.jboss.netty.channel.Channels.fireMessageReceived(Channels.java:261)
    at org.jboss.netty.channel.socket.nio.NioWorker.read(NioWorker.java:349)
    at org.jboss.netty.channel.socket.nio.NioWorker.processSelectedKeys(NioWorker.java:280)
    at org.jboss.netty.channel.socket.nio.NioWorker.run(NioWorker.java:200)
    at org.jboss.netty.util.ThreadRenamingRunnable.run(ThreadRenamingRunnable.java:108)
    at org.jboss.netty.util.internal.DeadLockProofWorker$1.run(DeadLockProofWorker.java:44)
    at java.util.concurrent.ThreadPoolExecutor$Worker.runTask(ThreadPoolExecutor.java:886)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:908)
    at java.lang.Thread.run(Thread.java:662)
Caused by: java.lang.reflect.InvocationTargetException
    at sun.reflect.NativeConstructorAccessorImpl.newInstance0(Native Method)
    at sun.reflect.NativeConstructorAccessorImpl.newInstance(NativeConstructorAccessorImpl.java:39)
    at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(DelegatingConstructorAccessorImpl.java:27)
    at java.lang.reflect.Constructor.newInstance(Constructor.java:513)
    at com.alibaba.com.caucho.hessian.io.JavaDeserializer.instantiate(JavaDeserializer.java:271)
    ... 28 more
Caused by: java.lang.NullPointerException
    at com.alibaba.china.ruleservice.RuleServiceImpl$DynamicPluginInvocationMatchedResult.&lt;init&gt;(RuleServiceImpl.java:163)
    ... 33 more

    at com.alibaba.dubbo.remoting.exchange.support.DefaultFuture.returnFromResponse(DefaultFuture.java:190)
    at com.alibaba.dubbo.remoting.exchange.support.DefaultFuture.get(DefaultFuture.java:110)
    at com.alibaba.dubbo.remoting.exchange.support.DefaultFuture.get(DefaultFuture.java:84)
    at com.alibaba.dubbo.rpc.protocol.dubbo.DubboInvoker.doInvoke(DubboInvoker.java:96)
    at com.alibaba.dubbo.rpc.protocol.AbstractInvoker.invoke(AbstractInvoker.java:144)
    at com.alibaba.dubbo.rpc.listener.ListenerInvokerWrapper.invoke(ListenerInvokerWrapper.java:74)
    at com.alibaba.dubbo.monitor.dragoon.filter.DragoonFilter.invoke0(DragoonFilter.java:82)
    at com.alibaba.dubbo.monitor.dragoon.filter.DragoonFilter.invoke(DragoonFilter.java:34)
    at com.alibaba.dubbo.rpc.protocol.ProtocolFilterWrapper$1.invoke(ProtocolFilterWrapper.java:91)
    at com.alibaba.dubbo.monitor.support.MonitorFilter.invoke(MonitorFilter.java:75)
    at com.alibaba.dubbo.rpc.protocol.ProtocolFilterWrapper$1.invoke(ProtocolFilterWrapper.java:91)
    at com.alibaba.dubbo.rpc.protocol.dubbo.filter.FutureFilter.invoke(FutureFilter.java:53)
    at com.alibaba.dubbo.rpc.protocol.ProtocolFilterWrapper$1.invoke(ProtocolFilterWrapper.java:91)
    at com.alibaba.dubbo.rpc.filter.ConsumerContextFilter.invoke(ConsumerContextFilter.java:48)
    at com.alibaba.dubbo.rpc.protocol.ProtocolFilterWrapper$1.invoke(ProtocolFilterWrapper.java:91)
    at com.alibaba.dubbo.rpc.protocol.InvokerWrapper.invoke(InvokerWrapper.java:53)
    at com.alibaba.dubbo.rpc.cluster.support.FailoverClusterInvoker.doInvoke(FailoverClusterInvoker.java:77)
    ... 32 more
</code></pre>

<p>看到这个日志第一反映是觉得<code>RuleServiceImpl.java:163</code>数据错误，抛空指针，但检查那块代码发现那个地方根本不可能抛空指针 —— 所有用到的变量都是<code>new</code>出来的；<br/>
而且，依据调用方提供的错误日志的抛出时间，我在被调用方系统的所有机器的日志里查找了一遍，没有发现对应的服务端日志；照理说服务端抛空指针，服务端也会有对应日志，但没有任何线索&#8230;</p>

<p>因此只好翻开了<code>JavaDeserializer.java:275</code>作检查，发现有这么一段：</p>

<pre><code>  public JavaDeserializer(Class cl)
  {
    _type = cl;
    _fieldMap = getFieldMap(cl);

    _readResolve = getReadResolve(cl);

    if (_readResolve != null) {
      _readResolve.setAccessible(true);
    }

    Constructor []constructors = cl.getDeclaredConstructors();
    long bestCost = Long.MAX_VALUE;

    for (int i = 0; i &lt; constructors.length; i++) {
      Class []param = constructors[i].getParameterTypes();
      long cost = 0;

      for (int j = 0; j &lt; param.length; j++) {
    cost = 4 * cost;

    if (Object.class.equals(param[j]))
      cost += 1;
    else if (String.class.equals(param[j]))
      cost += 2;
    else if (int.class.equals(param[j]))
      cost += 3;
    else if (long.class.equals(param[j]))
      cost += 4;
    else if (param[j].isPrimitive())
      cost += 5;
    else
      cost += 6;
      }

      if (cost &lt; 0 || cost &gt; (1 &lt;&lt; 48))
    cost = 1 &lt;&lt; 48;

      cost += param.length &lt;&lt; 48;

      if (cost &lt; bestCost) {
        _constructor = constructors[i];
        bestCost = cost;
      }
    }

    if (_constructor != null) {
      _constructor.setAccessible(true);
      Class []params = _constructor.getParameterTypes();
      _constructorArgs = new Object[params.length];
      for (int i = 0; i &lt; params.length; i++) {
        _constructorArgs[i] = getParamArg(params[i]);
      }
    }
  }
</code></pre>

<p>看完这段后，再结合远程调用的返回结果类后恍然大悟：<br/>
上面这段代码，是hessian在反序列化的时候，用于在被反序列化的类里面找一个“得分最低”的构造函数，反序列化时会加以调用;<br/>
构造函数的“得分”规则大致是：参数越少得分越低；参数个数相同时，参数类型越接近JDK内置类得分越低<br/>
而我们的调用返回的类只有一个构造函数，当然只有这个构造函数会被选中<br/>
但是，hessian反序列化调用被选中的构造函数时，是这样来创造该构造函数需要的参数的：</p>

<pre><code>protected static Object getParamArg(Class cl)
  {
    if (! cl.isPrimitive())
      return null;
    else if (boolean.class.equals(cl))
      return Boolean.FALSE;
    else if (byte.class.equals(cl))
      return new Byte((byte) 0);
    else if (short.class.equals(cl))
      return new Short((short) 0);
    else if (char.class.equals(cl))
      return new Character((char) 0);
    else if (int.class.equals(cl))
      return new Integer(0);
    else if (long.class.equals(cl))
      return new Long(0);
    else if (float.class.equals(cl))
      return new Float(0);
    else if (double.class.equals(cl))
      return new Double(0);
    else
      throw new UnsupportedOperationException();
  }
</code></pre>

<p>可以看到，如果参数不是<code>primitive</code>类型，会被<code>null</code>代替；但不巧的是我们的构造函数内部对该参数调用了一个方法，因此抛出了空指针&#8230;<br/>
也就是说这个空指针是抛在客户端反序列化的时候而不是服务端内部，因此服务端当然找不到对应的错误日志了；<br/>
解决的办法也很简单：可以新增一个无参构造函数(无参构造函数肯定“得分”最低一定会被选中)；或者修改代码保证任意参数为<code>null</code>的时候都不会出问题</p>

<hr />

<p>下面这个问题更有意思，说的是<code>ThreadPoolExecutor</code>的<code>RejectedExecutionHandler</code>的使用：</p>

<pre><code>threadPool = new ThreadPoolExecutor(5, maxThreadNum, 5, TimeUnit.MINUTES, new SynchronousQueue&lt;Runnable&gt;(), tf,
            new RejectedExecutionHandler() {
                public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
                    logger.error("Ep thread pool exhausted, epId: " + id + "!!");
                    r.run();
                }
            });
</code></pre>

<p>这个代码是说，当我这个ThreadPool不够用，又不能再新增线程数的时候，由调用方线程自己来执行这个<code>Runnable</code>任务&#8230;<br/>
本来这看上去没什么问题，问题出在这个<code>Runnable</code>本身的实现上 —— 它内部将执行它的线程block到了一个blocking queue上面，当调用方主线程亲自来执行它时，使得主线程再也回不去做它自己该做的事情了，因此会出大问题&#8230;<br/>
所以这么看来，“当线程池不够用就让调用方线程自己来干”的这个策略在实际使用时要非常谨慎</p>

<p>这个问题是通过一个方便的thread dump分析工具: <a href="https://java.net/projects/tda">tda</a>来查找的，因为出问题的这个应用是个多线程程序，有1600多个常驻线程，thread dump非常之大，肉眼直接看很不方便，但tda能将thread dump变得更友好易读，方便排查问题，在此推荐一下</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[使用'Tsukuba Help'观看国外免费在线网络课程(android篇)]]></title>
    <link href="http://pfmiles.github.io/blog/watch-mooc-videos-with-tsukuba-help-android-version"/>
    <updated>2013-03-17T11:56:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/watch-mooc-videos-with-tsukuba-help-android-version</id>
    <content type="html"><![CDATA[<p>目前在<a href="https://www.coursera.org/">Coursera.org</a>, <a href="https://www.udacity.com/">udacity.com</a>, <a href="https://www.edx.org/">edx.org</a>等网站都提供有丰富的、高质量的在线视频课程可学习；<br/>
虽然国内也有网易公开课等视频课程项目(其课程来源仍是上述国外网站)，但数量相对较少且翻译也跟不上，而且，更重要的是，这些在线课程往往随堂提供有课后作业，如果你想同一时间与来自世界各地的同学一起交作业、一起讨论的话，用网易公开课平台是无法达到的；<br/>
(当然我没有说网易公开课不好，在这里我要向网易致敬！)<br/>
但由于网速、网络等各种原因，直接观看上述国外网站的在线课程有些困难，为此我推荐一种快速有效的办法，在android手机上，直接观看国外在线课程视频。</p>

<!-- more -->


<p>以目前的android街机三星Galaxy Note2为例(Android 4.1)：</p>

<ol>
<li>打开浏览器，访问如图所示的网页: <img src="http://pfmiles.github.io/images/tsukuba/android_tsukuba1.png" alt="android 1" /><br/>
这个页面上面有许多ip地址等信息，并且每过2小时会刷新&#8230;而且越靠上的ip地址其服务质量越好&#8230;</li>
<li>对于android，要使用L2TP/IPSEC方式连接，因此我们找到&#8221;Support L2TP/IPSEC&#8221;这一列： <img src="http://pfmiles.github.io/images/tsukuba/android_tsukuba2.png" alt="android 2" /><br/>
注意这一列中标有&#8221;yes&#8221;字样的行，就是你的目标！</li>
<li>将刚才看到的&#8221;Support L2TP/IPSEC&#8221;这一列为“yes”的这一行的ip地址拷下来: <img src="http://pfmiles.github.io/images/tsukuba/android_tsukuba3.png" alt="android 2" /></li>
<li>打开“设定”， 点击“更多设置”: <img src="http://pfmiles.github.io/images/tsukuba/android_tsukuba4.png" alt="android 2" /></li>
<li>点开如图所示的选项后进去“新建”: <img src="http://pfmiles.github.io/images/tsukuba/android_tsukuba5.png" alt="android 2" /></li>
<li>如下图般设置：<br/>
<img src="http://pfmiles.github.io/images/tsukuba/android_tsukuba6.png" alt="android 2" /><br/>
&#8220;名称&#8221;随便起一个；<br/>
“类型”选“L2TP/IPSec PSK”;<br/>
&#8220;服务器地址&#8221;就粘帖你上一步复制的ip地址;<br/>
屏幕继续滑动往下走(要点开“高级选项”)：</li>
<li><img src="http://pfmiles.github.io/images/tsukuba/android_tsukuba7.png" alt="android 2" /><br/>
“IPsec预共享密钥”填：<img src="http://pfmiles.github.io/images/tsukuba/v.png" alt="android 2" />, 全小写;<br/>
“转发路由”填上图所示的值;<br/>
然后其它不用管，保存吧！</li>
<li>点击连接你刚才建立的网络，若要求输入用户名密码，则均填: <img src="http://pfmiles.github.io/images/tsukuba/v.png" alt="android 2" />, 全小写：<br/>
<img src="http://pfmiles.github.io/images/tsukuba/android_tsukuba8.png" alt="android 2" /></li>
<li>连接成功后，左上角会有一个小钥匙的图标，这时候就已经成功了！<br/>
<img src="http://pfmiles.github.io/images/tsukuba/android_tsukuba9.png" alt="android 2" /></li>
<li>打开浏览器试试吧：<br/>
<img src="http://pfmiles.github.io/images/tsukuba/android_tsukuba10.png" alt="android 2" /></li>
</ol>


<p>常见FAQ：</p>

<ul>
<li>这个工具由谁提供？

<ul>
<li>A: 这是日本筑波大学的研究生们发起的一个实验(社会实验？), 邀请全世界范围内的服务器，参与这个活动，免费为人们提供连接服务; 因此你最初用浏览器打开的那个服务器列表中的ip地址来自世界各地; 但由于日本同学普遍网络技术不好，导致原本的页面网络故障，我国国内的人们无法直接访问筑波大学的活动页面，因此我使用了一些技术手段把这些信息呈现到了国内，以方便爱学习的同学们使用</li>
</ul>
</li>
<li>服务质量如何？

<ul>
<li>A: 很快，从可以看视频这一点就能体会到</li>
</ul>
</li>
<li>这个服务能用多久？

<ul>
<li>A: 没有规定这个服务能用多久，如果断掉的话，重新连接或再去服务器列表中找一个来用就是了，换服务器的话, 所有配置都一样，只是覆盖一个ip地址而已，很方便；如果你关心的是这个免费服务的活动能进行多久，那我也不知道，总之我们目前能好好利用它帮助我们学习就OK了</li>
</ul>
</li>
<li>除了android，其它平台能够使用这个服务么？

<ul>
<li>A: 当然可以，由于我中午还没吃饭，所以后面再介绍windows下如何使用该服务；linux众们我就忽略你们了吧，我知道你们自己能搞定的:)</li>
</ul>
</li>
</ul>


<p>&#8230;&#8230;</p>

<p>有任何问题可发邮件至： <img src="http://pfmiles.github.io/images/email.png" alt="email" />, 不定期可能会回复(当我心血来潮查看垃圾箱时)<br/>
若有与服务器列表页面相关的任何问题，可到此<a href="https://gitcafe.com/tsukubahelp/tsukubahelp/tickets">页面</a>提交问题记录，会有人处理&#8230;</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[用于代码生成的模板引擎应该是什么样子？]]></title>
    <link href="http://pfmiles.github.io/blog/what-does-a-template-engine-for-code-generation-look-like"/>
    <updated>2012-09-13T15:27:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/what-does-a-template-engine-for-code-generation-look-like</id>
    <content type="html"><![CDATA[<p>以前在做一个涉及代码生成的项目的时候，使用了velocity模板引擎来做这个代码生成；<br/>
而事后发现，velocity有大部分的语法是我在代码生成过程中没有用到的；<br/>
且velocity的引入，也导致引入了一些看起来很多余的jar包；<br/>
后来我看了看<code>StringTemplate</code>这个东西，发现它不仅包含velocity几乎全部的语法，还有模板继承机制！这岂不是更复杂？虽然标榜为“为了代码生成”的模板引擎&#8230;但鉴于<code>velocity</code>的复杂印象，我并没有使用它.  <br/>
再后来，我为了包管理上的简洁(对于某些项目我承认我有洁癖)，我直接使用了java标准库里的<code>java.text.MessageFormat</code>来做代码生成；这也确实可行！不过，缺点也是很快就能遇到的：</p>

<ol>
<li>大括号<code>{</code>和<code>}</code>在<code>MessageFormat</code>中是关键字！所以输出时必须转义；这两个东西在目标代码中(比如java)很常见，遇到一个就要转义一个是很不爽的事情;</li>
<li>除了字符串替换之外，没有任何分支逻辑判断、循环结构支持，这使得所有的分支逻辑和循环结构都要写在调用这些<code>MessageFormat</code>的java代码里；虽然很多时候确实可以这么做并且很合适，但是还是有一些情况，如果能写在模板里会明显比写在java代码里好;</li>
<li><code>MessageFormat</code>的placeholder是数字，渲染时是根据传入参数的位置来做值替换，这很不直观，更好的用户体验应该是依据名字来替换，就像所有的、普遍意义上人们所见过的模板引擎那样;</li>
</ol>


<p>总结性地思考一下：我在做代码生成的时候，需要的模板引擎大概应该是：</p>

<ul>
<li>简单，这意味着只需要拥有简单的语法以及简单的jar包依赖(或者不需要jar包依赖)</li>
<li>高效，最好直接编译成字节码执行，而非像velocity那样每次渲染都遍历AST</li>
</ul>


<p>而重点就在于第一点：简单，这需要我好好总结一份“用作代码生成的模板引擎所必须的语法特性”列表, 并且除此以外，不能有更多其它的东西;<br/>
至于高效，只要确保最终被反复执行的逻辑是一个编译好的java类就行了，而非遍历AST，这很容易办到;<br/>
而且..正好之前开发的<a href="https://github.com/pfmiles/dropincc.java">dropincc.java</a>需要为用户提供一个模板引擎，因为语法解析与代码生成在很多任务中是一对好基友，常常是伴随着出现；那么在dropincc.java中内建一个针对代码生成的模板引擎也就是非常有必要的了；它之于dropincc.java，就好比StringTemplate之于antlr，都是为了方便用户做代码生成创造的;<br/>
并且，这个模板引擎应该随着dropincc.java一起发布，不需要引入新的jar包依赖;<br/>
计划中，这个模板引擎的基本特性：</p>

<!-- more -->


<ol>
<li>编译为java字节码，常驻内存</li>
<li>语法简单，只支持<code>if-else</code>语句和<code>foreach</code>语句, <code>foreach</code>语句支持数组和<code>Collection</code>的遍历, 也支持对&#8221;range常量&#8221;的遍历</li>
<li>兼容velocity语法的一个子集, 但语义不一样(即只实现其<code>if-else</code>和<code>foreach</code>语法，一方面这是为了利用已有的、强大的velocity语法高亮插件)</li>
<li>任何元素的输出结果总是与<code>String.valueOf(obj)</code>的结果一致</li>
<li>逻辑判断只支持<code>==</code>、<code>!</code>, 支持<code>&amp;&amp;</code>或<code>||</code>和括号优先级，因为我认为，用于代码生成的模板引擎的语法应该全是“开关”形式的，即“已经是判断的结果了”，非<code>true</code>即<code>false</code>(顶多再加上<code>==</code>比较)，不应该有过多的动态的复杂逻辑判断，这些判断其实应该放到调用这个模板引擎的java代码里, 而在模板里，只应该存在对这些bool值的与、或、非的各种组合判断</li>
<li><code>==</code>操作符的判断结果与java中<code>==</code> + <code>equals</code>函数的判断逻辑一致</li>
<li>模板context支持map和javabean两种形式, 可使用<code>.</code>操作读取bean或map中的属性值，但不支持方法调用</li>
<li>没有赋值语句，context中的所有东西，要么是要输出的元素，要么是作为输出控制的bool开关，它们在渲染过程中是不可变的</li>
<li>模板引擎接口简单、清晰，只有4个static方法：

<ul>
<li><code>public static String merge(String filePath, Object context, Class&lt;?&gt; cls)</code></li>
<li><code>public static byte[] mergeAsBytes(String filePath, Object context, Class&lt;?&gt; cls)</code></li>
<li><code>public static String merge(String filePath, Object context, Class&lt;?&gt; cls, String encoding)</code></li>
<li><code>public static byte[] mergeAsBytes(String filePath, Object context, Class&lt;?&gt; cls, String encoding)</code></li>
<li>其中，<code>filePath</code>是模板路径; <code>context</code>可是javabean或map，为模板上下文，包含要输出的元素和控制条件; <code>cls</code>是用于加载模板资源的class类，模板资源查找规律与<code>Class.getResourceAsStream</code>方法一致; <code>encoding</code>是指定模板所使用的编码格式; 返回<code>String</code>的方法即返回渲染后的字符串结果；返回<code>byte[]</code>的接口则是直接返回带编码格式的、<code>byte</code>的数组，这个结果可直接用作写入外部存储或流，而无需再应用编码格式;</li>
</ul>
</li>
</ol>


<p>而基本上就是这些，不需要太多东西，可能第一眼会觉得“功能是不是太少”？但是，我已经见过了许多过重的逻辑被放在模板语法里的情况，与其增加这种不必要的、很可能是错误的使用方式(因为这样做确实不好维护)，还不如一开始就不提供了；<br/>
并且，代码生成所需要的模板引擎，相比起做web页面所需要的模板引擎来讲，一定要简单许多；因为大部分的逻辑是应该放在java代码中(比如负责翻译代码的visitor)而不是模板里。</p>

<p>ok, 下面需要给出这个模板引擎的<a href="http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form">EBNF</a>,这是最重要的准绳，几乎框定了绝大部分东西：</p>

<pre><code>template ::= content $
content ::= renderable*
renderable ::= PLAIN_TEXT
          | '#if' '(' boolExpr ')' renderable ('#elseif' '(' boolExpr ')' renderable)* ('#else' renderable)? '#end'
          | '#foreach' '(' REF 'in' (REF|RANGE) ')' renderable '#end'
          | REF
boolExpr ::= andExpr ('||' andExpr)*
andExpr ::= term ('&amp;&amp;' term)*
term ::= '!'* REF
       | value '==' value
       | '!'* '(' boolExpr ')'
value ::= '-'?[0-9]+('.'[0-9]+)?
        | '\'' .* '\''
</code></pre>

<p>语法就是这样，应该已经足够;上述规则中，全大写字母的元素是terminal，一部分terminal的定义未在上面给出，补充在下面：</p>

<pre><code>REF ::= '${' ID('.'ID)* '}'
ID ::= [a-zA-Z_][a-zA-Z0-9_]*
RANGE ::= '[' [0-9]+ '..' [0-9]+ ']'
</code></pre>

<p>总结起来讲，这个模板语法支持<code>if</code>和<code>foreach</code>语句，以及引用值的输出，其余的元素一律被看作<code>PLAIN_TEXT</code>直接输出;<br/>
在<code>if</code>语句中，逻辑表达式支持<code>==</code>比较，以及“非”逻辑<code>!</code>;支持添加圆括号调整运算优先级;<br/>
<code>foreach</code>语句中，可以支持对引用(必须是<code>Collection</code>或<code>Array</code>)或<code>RANGE</code>表达式的遍历; <code>RANGE</code>表达式即生成一个数字序列的表达式，步长为1，如<code>[1..10]</code>表示一个由1到10的数字序列;</p>

<p>至于具体的实现方式，仍然采用与dropincc.java一致的jdk1.6 compiler API的动态编译的形式，编译为字节码运行。<br/>
这个模板引擎将作为dropincc.java内部自己做一些代码生成，也同时提供给用户做代码生成工作，这样既能避免过多jar包的引入，又能施行一些最佳实践(&#8220;最佳&#8221;的意思是我这里定义的，在我看来是在“什么逻辑放在模板中”和“什么逻辑放在java代码中”找到一个平衡点，当然不同人可以有不同理解)。</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[Prime Numbers Less Than N]]></title>
    <link href="http://pfmiles.github.io/blog/prime-numbers-less-than-n"/>
    <updated>2012-09-03T13:57:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/prime-numbers-less-than-n</id>
    <content type="html"><![CDATA[<ul>
<li>Sieve方法: <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes</a></li>
<li>优化1：初始化list时，预先排除2,3,5,7的倍数, 得到一个初始化list</li>
<li>优化2：在筛除合数时，不必一个一个挨着筛，只需在列表中剔除： p * x 即可(x是从p开始，初始list中的数字), 直到p*p > 初始化list中的最大数</li>
</ul>


<p>资料：
用作测试，素数个数对照表： <a href="http://primes.utm.edu/howmany.shtml">http://primes.utm.edu/howmany.shtml</a></p>

<p>扩展：
也许下一篇文章介绍一下“素数测试”？ <a href="http://en.wikipedia.org/wiki/Primality_tests">http://en.wikipedia.org/wiki/Primality_tests</a></p>

<p>TODO 后面再完成本文，反正有版本管理～</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[Growing a Full-Featured Calculator in 15 Minutes Using Dropincc.java]]></title>
    <link href="http://pfmiles.github.io/blog/growing-a-full-featured-calculator-in-15-minutes-using-dropincc-dot-java"/>
    <updated>2012-08-12T15:58:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/growing-a-full-featured-calculator-in-15-minutes-using-dropincc-dot-java</id>
    <content type="html"><![CDATA[<p>First, let&#8217;s create a empty java project in eclipse IDE, download newest playable dropincc.java jar file from <a href="https://github.com/pfmiles/dropincc.java/releases">here</a>. Adding it to the build path of the project, like this(note: jdk1.6 or above required):<br/>
<img src="http://pfmiles.github.io/images/dropincc/calc/emptyProjWithJar.png" alt="emptyProjWithJar" /><br/>
And then, create a new java source file to build our grammar, for example, <code>Calculator.java</code>.<br/>
We start by specifying the EBNF form of our expected calculator language. The calculator expression would do addition and subtraction operations and also multiplication and division operations which have a greater priority.<br/>
Also, we expect the calculator could handle parentheses to do priority adjustment.<br/>
We could write the EBNF grammar rules in a top-down pattern:</p>

<pre><code>calc ::= expr $
expr ::= addend (('+'|'-') addend)*
</code></pre>

<p>We specified that the overall <code>expression</code> consists one or more <code>addend</code> sub-expressions with <code>'+'</code> or <code>'-'</code> symbol delimited.<br/>
And for every single <code>addend</code> expression:</p>

<pre><code>addend ::= factor (('\*'|'/') factor)*
</code></pre>

<p>consists one or more <code>factor</code> separated by <code>'*'</code> or <code>'/'</code>.<br/>
And finally, for any single <code>factor</code>, is either a single digit or a quoted expression:</p>

<pre><code>factor ::= '\d+(\.\d+)?'
         | '(' expr ')'
</code></pre>

<p>Ok, we&#8217;ve done defining the EBNF of our calculator. This is what it look like all over:</p>

<pre><code>calc ::= expr $
expr ::= addend (('+'|'-') addend)*
addend ::= factor (('\*'|'/') factor)*
factor ::= '\d+(\.\d+)?'
         | '(' expr ')'
</code></pre>

<!-- more -->


<p>It&#8217;s quite short because it utilized the kleene notation to represent &#8216;zero or more&#8217;. And a shorter EBNF ends up a shorter dropincc.java program!<br/>
Now let&#8217;s &#8216;translate&#8217; the EBNF into dropincc.java program. I say &#8216;translate&#8217; here because it&#8217;s a really straightforward step:</p>

<pre><code>// some elements' pre-definitions in order to call the methods
Lang calc = new Lang("Calc");
TokenDef a = calc.newToken("\\+");
TokenDef m = calc.newToken("\\*");
Grule expr = calc.newGrule();
Grule addend = calc.newGrule();
Grule factor = calc.newGrule();

// grammar definition section start
calc.defineGrule(expr, CC.EOF);
expr.define(addend, CC.ks(a.or("\\-"), addend));
addend.define(factor, CC.ks(m.or("/"), factor));
factor.define("\\d+(\\.\\d+)?")
.alt("\\(", expr, "\\)");
// grammar definition end
</code></pre>

<p>The &#8216;grammar definition&#8217; part is as many lines as the EBNF. In fact it&#8217;s a line-by-line translation of the EBNF(please look at the &#8216;grammar definition&#8217; section carefully).</p>

<p>Just a little more explanation:</p>

<ul>
<li>The basic elements of grammar rule is <code>TokenDef</code>s and <code>Grule</code>s.(In fact <code>Grule</code> means &#8216;grammar rule&#8217;) <code>TokenDef</code>s are defined using java built-in regular expression currently.</li>
<li>Rule production&#8217;s match sequence is represented as comma separated elements list. Like <code>expr, CC.EOF</code> means <code>expr $</code>, <code>addend, CC.ks(a.or("\\-"), addend)</code> means <code>addend (('+'|'-') addend)*</code>.</li>
<li>Note the <code>CC.EOF</code> constant, it&#8217;s a predefined constant provided by dropincc.java to represent <code>EOF</code> token definition.</li>
<li>And the <code>CC.ks</code> method call means all elements passed in as parameters are enclosed in a kleene star node(kleene star node means zero or more multiplication of its enclosing elements, the same as you learnt from using a regular expression). And <code>ks</code> in fact means &#8216;kleene star&#8217;.</li>
<li>Likewise, there are <code>CC.kc</code> method and <code>CC.op</code> method which means <code>kleene cross</code>(one or more) and <code>optional</code>(zero or one) respectively but not used in the above example, you can browse them from source code.</li>
<li>Rule alternative productions are represented by an <code>alt</code> method call. Look at the <code>factor</code> rule definition, the <code>factor</code> rule has two productions. And, respectively, in java code, it has an additional <code>alt</code> call besides <code>define</code>.</li>
</ul>


<p>&#8216;Comma separated match sequence&#8217;, &#8216;CC.EOF&#8217;, &#8216;CC.ks/kc/op&#8217; and &#8216;alt&#8217;, those are almost all you need to know to define a non-trivial DSL grammar in dropincc.java.</p>

<p>Ok, after we have defined the grammar, it&#8217;s time to add <code>Action</code>s to process the elements the parser matched while parsing. It&#8217;s also achieved by a very intuitive way:</p>

<ul>
<li>One <code>alternative production</code>(note: not one rule) could have only one action. That&#8217;s, the <code>calc</code> rule could have only one action because it has only one alternative production. While <code>factor</code> rule could have two actions because it has two alternative productions.</li>
<li>Let&#8217;s add actions for the <code>factor</code> rule first:</li>
</ul>


<p>For the first alternative production:</p>

<pre><code>factor.define("\\d+(\\.\\d+)?").action(new Action&lt;String&gt;(){
    public Double act(String matched) {
        return Double.parseDouble(matched);
    }})
</code></pre>

<p>The first alt of <code>factor</code> rule only matches a single string which have a &#8216;digit&#8217; format. So the <code>act</code> method of the <code>Action</code> interface should be a single <code>String</code> object holding the matched digit string. And, also, the generic type argument of <code>Action</code> interface should be <code>String</code>, to provide a strong type safety for the actually matched element.<br/>
We just parse the matched digit string to a number and returned it. So the return type of this action is <code>Double</code>.</p>

<p>And the <code>Action</code> for the second alt:</p>

<pre><code>.alt("\\(", expr, "\\)").action(new Action&lt;Object[]&gt;(){
    public Double act(Object[] ms) {
        return (Double) ms[1];
    }
});
</code></pre>

<p>The second alt is an expression enclosed by parentheses. There are three element in the match sequence: <code>(</code>, enclosing <code>expr</code>, and <code>)</code>.<br/>
The type argument of <code>Action</code> interface should be <code>Object[]</code> since the matched element will be passed in as an object array of length 3. With first element <code>(</code>, second element the returned value of the enclosing <code>expr</code> rule&#8217;s action, and third element <code>)</code>.<br/>
All we care about is the second element: the returned value of the enclosing <code>expr</code>&#8217;s action. So we just return <code>ms[1]</code> here, ignoring <code>(</code> and <code>)</code>. Note that we confidently converted the <code>ms[1]</code> to a <code>Double</code> object, that&#8217;s because we knew the return value of <code>expr</code> rule&#8217;s action is definitely a <code>Double</code> value.</p>

<ul>
<li>Then, let&#8217;s add action for the <code>addend</code> rule:</li>
</ul>


<p>It has only one production, so it could have only one corresponding action:</p>

<pre><code>addend.define(factor, CC.ks(m.or("/"), factor)).action(new Action&lt;Object[]&gt;() {
    public Double act(Object[] ms) {
        Double f0 = (Double) ms[0];
        Object[] others = (Object[]) ms[1];
        for (Object other : others) {
            Object[] opAndFactor = (Object[]) other;
            if ("*".equals(opAndFactor[0])) {
                f0 *= (Double) opAndFactor[1];
            } else {
                f0 /= (Double) opAndFactor[1];
            }
        }
        return f0;
    }
});
</code></pre>

<p>The argument of <code>act</code> method is an object array of length 2. Its first element is the returned value from the matched <code>factor</code> rule&#8217;s action,<br/>
and the second are other operator &amp; factor pairs.<br/>
If there&#8217;s only one factor matched here, the &#8216;operator &amp; factor&#8217; pairs would be an array of length 0, otherwise it contains all other matched operators and factors.<br/>
You can see that the argument structure of method <code>act</code> is highly consistent to the defined match sequence of the corresponding alternative production.</p>

<p>We wrote some logic to compute the total multiplication or division of all matched factors, and finally, returned the result as the result of this action.</p>

<ul>
<li>Then, we add action for the <code>expr</code> rule. It&#8217;s almost the same as the action of <code>addend</code> rule, but in an <code>add</code> or <code>subtract</code> manner when computing the matched elements:</li>
</ul>


<p>The <code>expr</code> rule also could have only one action:</p>

<pre><code>expr.define(addend, CC.ks(a.or("\\-"), addend)).action(new Action&lt;Object[]&gt;() {
    public Double act(Object[] ms) {
        Double a0 = (Double) ms[0];
        Object[] others = (Object[]) ms[1];
        for (Object other : others) {
            Object[] opAndFactor = (Object[]) other;
            if ("+".equals(opAndFactor[0])) {
                a0 += (Double) opAndFactor[1];
            } else {
                a0 -= (Double) opAndFactor[1];
            }
        }
        return a0;
    }
});
</code></pre>

<p>Finally, we add action for the <code>calc</code> rule. It&#8217;s the starter rule. All computations should have been done at this point. So all we need to do in its action is return the final result, ignoring the <code>EOF</code>:</p>

<pre><code>calc.defineGrule(expr, CC.EOF).action(new Action&lt;Object[]&gt;() {
    public Double act(Object[] ms) {
        return (Double) ms[0];
    }
});
</code></pre>

<p>Now, we have done defining a calculator and added proper actions for it, we could <code>compile</code> it now:</p>

<pre><code>Exe exe = calc.compile();
</code></pre>

<p>Then, enjoy with our new calculator:</p>

<pre><code>// this should print the result: 3389.0
System.out.println(exe.eval("1 +2+3+(4 +5*6*7*(64/8/2/(2/1 )/1)*8  +9  )+   10"));
</code></pre>

<p>It&#8217;s quite simple isn&#8217;t it? If you are already familiar with the API, 15 min is too much for defining such a calculator!<br/>
And the follow is all the code in a gist, you could copy and try it in your own IDE:</p>

<div><script src='https://gist.github.com/3339604.js?file='></script>
<noscript><pre><code>import com.github.pfmiles.dropincc.Action;
import com.github.pfmiles.dropincc.CC;
import com.github.pfmiles.dropincc.Exe;
import com.github.pfmiles.dropincc.Grule;
import com.github.pfmiles.dropincc.Lang;
import com.github.pfmiles.dropincc.TokenDef;

public class Calculator {
    private static Exe exe = null;
    /**
     * &lt;pre&gt;
     * calc ::= expr $
     * expr ::= addend (('+'|'-') addend)*
     * addend ::= factor (('\*'|'/') factor)*
     * factor ::= '\d+(\.\d+)?'
     *          | '(' expr ')'
     * &lt;/pre&gt;
     */
    static {
        // some elements' pre-definitions in order to call the methods
        Lang calc = new Lang(&quot;Calc&quot;);
        TokenDef a = calc.newToken(&quot;\\+&quot;);
        TokenDef m = calc.newToken(&quot;\\*&quot;);
        Grule expr = calc.newGrule();
        Grule addend = calc.newGrule();
        Grule factor = calc.newGrule();

        // grammar definition starts here
        calc.defineGrule(expr, CC.EOF).action(new Action&lt;Object[]&gt;() {
            public Double act(Object[] ms) {
                return (Double) ms[0];
            }
        });
        expr.define(addend, CC.ks(a.or(&quot;\\-&quot;), addend)).action(new Action&lt;Object[]&gt;() {
            public Double act(Object[] ms) {
                Double a0 = (Double) ms[0];
                Object[] others = (Object[]) ms[1];
                for (Object other : others) {
                    Object[] opAndFactor = (Object[]) other;
                    if (&quot;+&quot;.equals(opAndFactor[0])) {
                        a0 += (Double) opAndFactor[1];
                    } else {
                        a0 -= (Double) opAndFactor[1];
                    }
                }
                return a0;
            }
        });
        addend.define(factor, CC.ks(m.or(&quot;/&quot;), factor)).action(new Action&lt;Object[]&gt;() {
            public Double act(Object[] ms) {
                Double f0 = (Double) ms[0];
                Object[] others = (Object[]) ms[1];
                for (Object other : others) {
                    Object[] opAndFactor = (Object[]) other;
                    if (&quot;*&quot;.equals(opAndFactor[0])) {
                        f0 *= (Double) opAndFactor[1];
                    } else {
                        f0 /= (Double) opAndFactor[1];
                    }
                }
                return f0;
            }
        });
        factor.define(&quot;\\d+(\\.\\d+)?&quot;).action(new Action&lt;String&gt;() {
            public Double act(String matched) {
                return Double.parseDouble(matched);
            }
        }).alt(&quot;\\(&quot;, expr, &quot;\\)&quot;).action(new Action&lt;Object[]&gt;() {
            public Double act(Object[] ms) {
                return (Double) ms[1];
            }
        });
        // grammar definition end

        exe = calc.compile();
    }

    public static void main(String... args) {
        System.out.println(exe.eval(&quot;1 +2+3+(4 +5*6*7*(64/8/2/(2/1 )/1)*8  +9  )+   10&quot;));
    }
}
</code></pre></noscript></div>



]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[Ideas and Concepts behind Dropincc.java]]></title>
    <link href="http://pfmiles.github.io/blog/ideas-and-concepts-behind-dropincc-dot-java"/>
    <updated>2012-08-10T00:40:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/ideas-and-concepts-behind-dropincc-dot-java</id>
    <content type="html"><![CDATA[<h3>DSLs in java is hard.</h3>

<p>DSLs are rarely discussed in java community. Or, at least comparing to other dynamic languages&#8217; world, DSLs in java is much harder to create.</p>

<p>Why does this happen?</p>

<p>According to <a href="http://martinfowler.com/bliki/DomainSpecificLanguage.html">Martin Fowler&#8217;s comments on DSLs</a>, they are separated mainly to two kinds: internal and external DSLs.</p>

<p>I believe that, the ability of how a specific general purposed programming language could be customized to an internal DSL relies on the language&#8217;s <a href="http://en.wikipedia.org/wiki/Metaprogramming">meta-programming</a> features.</p>

<p>Some languages, especially dynamic typed ones, have ability to customize its syntactical appearance at runtime. By intercepting their class defining life-cycles, executing fail-over strategies when method or field missings, or doing presentation substitutions via sophisticated macro systems or even, directly change their parse tree at runtime. All those incredible features are the magic behind internal DSLs.</p>

<p>But, we sadly found that java has none of those magic stuff to help building internal DSLs. There&#8217;s little meta-programming features in java. Annotations? Perhaps one rare creature, but its not enough.<br/>
Maybe the only way to create internal DSLs in java is to design a set of <a href="http://www.martinfowler.com/bliki/FluentInterface.html">Fluent Interface</a> API. It&#8217;s great, but you won&#8217;t have much space on customizing the syntax of your DSL.</p>

<p>Then, seems that the possible ways to create real-world, sophisticated DSLs in java are always turns out to be external-DSLs. But, this won&#8217;t be easy, always, since the creation of computer world.</p>

<!-- more -->


<p>Creating external DSLs means doing lexical &amp; syntactical analyzing all by ourselves. There is a whole bunch of open sourced tools, say, <a href="http://en.wikipedia.org/wiki/Compiler-compiler">parser generators</a>, to help doing so, but there&#8217;s too much unnecessary efforts must be made before you get your grammar run.</p>

<p>Those traditional parser generators are great but in fact not suitable for DSL creating. Like lex&amp;bison, javacc, jcup and antlr etc. They usually have their own grammar you must learn to define grammar rules, this is some what big learning cost.<br/>
After you have done writing your grammar, they usually requires you to run a specific compiling tool in command-line to &#8216;compile&#8217; the rules you just wrote. And finally gives you a couple of source files in your host language and telling you to place them into somewhere of your project directory. Then you could run your program. If errors occur, you would re-do those steps by frequently switching between command-line and your IDE.</p>

<p>These steps are troublesome in practice. Especially for those first using a parser generator. I&#8217;ve seen one of my colleague struggled against antlr for one month, in order to build a SQL-like DSL. And much of his time was spent on getting familiar with antlr&#8217;s grammar, its &#8216;antlrWorks&#8217; IDE and some command-line tools. It was painful when recall on this month.</p>

<p>So I think one must not have to carry so much burden when he just want to create a relatively simple DSL. And <a href="https://github.com/pfmiles/dropincc.java">dropincc.java</a> is something I create to ease the building process of external DSL in java.</p>

<h3>If all done in one place.</h3>

<ul>
<li>I don&#8217;t think additional grammar must be created to describe grammar rules, this could be done in internal DSL in java, a.k.a fluent interfaces. Creating a <a href="http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form">EBNF</a> like internal DSL in java is affordable.</li>
<li>I don&#8217;t think additional command-line tools or individual specific IDE is needed since we are adopting internal DSL to describe grammar rules. Just a commonly used java IDE is sufficient.</li>
<li>Also, I don&#8217;t think we must repeat the compile-copy, and run cycle when we trying and debugging our new creating language. Grammar may be run directly just after we defined it. Like we edit and test java program instantly in most modern IDEs.</li>
</ul>


<p>And, all in all, in summary&#8230; dropincc.java ends up such a tool with those missions. I hope this small lib could help a lot in building external DSLs.</p>

<p>For a starter dummy example, please refer to <a href="http://pfmiles.github.io/blog/dropincc-dot-java-the-ultimate-tool-to-create-dsls-in-java/">this post</a>.</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[Dropincc.java, The Ultimate Tool to Create DSLs in Java]]></title>
    <link href="http://pfmiles.github.io/blog/dropincc-dot-java-the-ultimate-tool-to-create-dsls-in-java"/>
    <updated>2012-08-04T17:22:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/dropincc-dot-java-the-ultimate-tool-to-create-dsls-in-java</id>
    <content type="html"><![CDATA[<h3>Initial version released.</h3>

<p>Dropincc.java is a dynamic parser generator which allows you crafting your DSLs in pure java, using your favorite editor.<br/>
Now it reached its initial release version 0.1.0. You can download it from the <a href="https://github.com/pfmiles/dropincc.java">project page</a> and play around with it.<br/>
There&#8217;s a detailed <em>Quick Start</em> guide on the project page, it could guide you through to have a overall feeling on using dropincc.java.</p>

<h3>Main attributes of Dropincc.java.</h3>

<ul>
<li>It&#8217;s not just &#8216;yet another compiler compiler&#8217;. It aims to help you building DSLs in java <strong>Dynamically</strong>.</li>
<li><strong>Dynamic</strong> means you can use your newly defined DSL immediately after you have just finished its definition. No other steps required, no additional command-line instructions needed to type.</li>
<li>Very close to EBNF grammar syntactically when defining grammar rules using dropincc.java. With the fluent interface API, you can feel as if you are writing EBNF directly. Syntactically  close to EBNF is very nice for a parser generator.</li>
<li>It generates LL(*) parser for your language, dynamically, using java 1.6&#8217;s compiler API. And it provide powerful <em>semantic predicate</em> mechanics to handle even context-sensitive situations.</li>
<li>It won&#8217;t generate a parser source file to you and telling you to place the file into some where of your project directory. Instead, it handles all those generation &amp; compiling staff in the background and only provides you a executable object which you can invoke.</li>
<li>No other dependencies except for the built-in java library. Requires JDK 1.6 or above.</li>
</ul>


<h3>A dummy language example.</h3>

<!-- more -->


<p>Requires JDK 1.6 or above. Firstly, place the dropincc <a href="https://github.com/pfmiles/dropincc.java/releases">jar file</a> in your class path.</p>

<p>And then, crafting your language&#8217;s <a href="http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form">EBNF</a> definition:<br/>
Let&#8217;s define a language which accepts arbitrary numbers of quoted &#8216;a&#8217; or &#8216;bc&#8217;. For example: &#8216;(a)(bc)&#8217;, &#8216;(bc)((a))&#8217; or &#8216;(((bc)))(bc)&#8217;, the numbers of pairs of parentheses is unlimited.<br/>
The EBNF of this dummy language:</p>

<pre><code>S ::= L $
L ::= Q*
Q ::= 'a'
    | 'bc'
    | '(' Q ')'
</code></pre>

<p>Ok, after defining the EBNF representation of our language, it&#8217;s time to <strong>translate</strong> the EBNF into dropincc.java representation. I say &#8216;translate&#8217; here because this is a line-by-line straightforward step:</p>

<pre><code>public static void main(String... args) throws Throwable {
    Lang lang = new Lang("Dummy");
    TokenDef a = lang.newToken("a");
    TokenDef bc =lang.newToken("bc");
    TokenDef lp = lang.newToken("\\(");
    TokenDef rp = lang.newToken("\\)");
    Grule L = lang.newGrule();
    Grule Q = lang.newGrule();

    lang.defineGrule(L, CC.EOF); // S ::= L $
    L.define(CC.ks(Q));// L ::= Q*
    /*
     * Q ::= 'a'
     *     | 'bc'
     *     | '(' Q ')'
     */
    Q.define(a)
    .alt(bc)
    .alt(lp, Q, rp);
}
</code></pre>

<p>Ok, we have done defining the grammar rules of our dummy language, so easy:</p>

<ul>
<li>Define tokens, using built-in java regular expression syntax. And define rules, say, &#8216;Grule&#8217;s in dropincc.java. TokenDefs and Grules are basic elements of defining grammar rules.</li>
<li>You just using your defined TokenDefs and Grules to express your grammar, just like writing EBNF.</li>
<li>Elements concatenations are expressed by comma separated sequences: <code>L, CC.EOF</code> means <code>L $</code>. CC.EOF is a predefined TokenDef provided by dropincc.java.</li>
<li>Alternative productions of a grammar rule is expressed by a <code>alt</code> method call on a grule element. For example, the <code>Q</code> rule has three alternative productions.</li>
<li>The kleene star(means <strong>zero or more</strong>) and kleene cross(<strong>means one or more</strong>) notation is expressed by <code>CC.ks</code> and <code>CC.kc</code> utility functions. See the line: <code>L.define(CC.ks(Q));// L ::= Q*</code>.</li>
</ul>


<p>That&#8217;s almost all you need to learn about how to define a grammar using dropincc.java.<br/>
After that, you can <code>compile</code> your grammar:</p>

<pre><code>Exe exe = lang.compile();
</code></pre>

<p>This step would make you a callable object named &#8216;exe&#8217;. You can use this object to <code>eval</code> and test your newly defined language:</p>

<pre><code>System.out.println(exe.eval("a(a)((bc))"));
</code></pre>

<p>This would print the output: <code>[Ljava.lang.Object;@67a5a19</code>. It&#8217;s an object array which holds the whole parse tree:<br/>
<img src="http://pfmiles.github.io/images/dropincc/dummy.png" alt="Dummy lang parse tree" /></p>

<p>But it&#8217;s useless just getting the parse tree. We should do something to manipulate the parse tree and produce some &#8216;results&#8217; of this parsing.</p>

<p>Ok, suppose we have a dummy task: to remove all parentheses from the input string, leaving only the <code>'a'</code> and <code>'bc'</code>s there. Then at last, return the resulting string as the return value of <code>eval</code> method call on <code>exe</code>.</p>

<p>This involves adding <code>actions</code> to the grammar. The <code>action</code>s are some kind of code block, it should execute when its&#8217; corresponding grammar rule production matches.</p>

<p>In dropincc.java, <code>actions</code> are implemented by <code>closure</code>s, using the <code>Action</code> interface. We try to add an action to the <code>Q</code> rule:</p>

<pre><code>Q.define(a).action(new Action() {
    public String act(Object matched) {
        return (String) matched;// string 'a'
    }
}).alt(bc).action(new Action() {
    public String act(Object matched) {
        return (String) matched;// string 'bc'
    }

}).alt(lp, Q, rp).action(new Action() {
    public String act(Object matched) {
        // returns the middle element matched, that's the returned value of the enclosing 'Q' rule
        return (String) ((Object[]) matched)[1];
    }
});
</code></pre>

<p>Above is the <code>Q</code> rule with three actions, each action for one alternative production. In fact since the first two actions does noting but just returning the matched string, so they are not necessary. The <code>Q</code> rule with action could be defined as follows:</p>

<pre><code>Q.define(a)
.alt(bc)
.alt(lp, Q, rp).action(new Action() {
    public String act(Object matched) {
        // returns the middle element matched, that's the returned value of the enclosing 'Q' rule
        return (String) ((Object[]) matched)[1];
    }
});
</code></pre>

<p>Leaving only the third action there. The third action, returned the middle element matched of its production(ignored left and right parentheses). The middle element matched is the return value of the recursively enclosing <code>Q</code> rule.</p>

<p>The action for <code>L</code> rule is quite simple and significant: it collects all strings matched and concatenates them into a whole large string, then return the resulting string:</p>

<pre><code>L.define(CC.ks(Q)).action(new Action() {
    public String act(Object matched) {
        Object[] ms = (Object[]) matched;
        StringBuilder sb = new StringBuilder();
        for (Object m : ms)
            sb.append(m);
        return sb.toString();
    }
});// L ::= Q*
</code></pre>

<p>Then the last top-level rule&#8217;s action: just return the value of <code>L</code> rule, just ignoring EOF:</p>

<pre><code>lang.defineGrule(L, CC.EOF).action(new Action() {
    public String act(Object matched) {
        return (String) ((Object[]) matched)[0];
    }
}); // S ::= L $
</code></pre>

<p>Ok, we can now run the program again and could see it prints out the output: <code>aabc</code>, with all parentheses removed.</p>

<p>The whole program in a gist:</p>

<div><script src='https://gist.github.com/3257023.js?file='></script>
<noscript><pre><code>package test;

import com.github.pfmiles.dropincc.Action;
import com.github.pfmiles.dropincc.CC;
import com.github.pfmiles.dropincc.Exe;
import com.github.pfmiles.dropincc.Grule;
import com.github.pfmiles.dropincc.Lang;
import com.github.pfmiles.dropincc.TokenDef;

public class Test {

    /**
     * &lt;pre&gt;
     * S ::= L $
     * L ::= Q*
     * Q ::= 'a'
     *     | 'bc'
     *     | '(' Q ')'
     * &lt;/pre&gt;
     */
    public static void main(String... args) throws Throwable {
        Lang lang = new Lang(&quot;Dummy&quot;);
        TokenDef a = lang.newToken(&quot;a&quot;);
        TokenDef bc = lang.newToken(&quot;bc&quot;);
        TokenDef lp = lang.newToken(&quot;\\(&quot;);
        TokenDef rp = lang.newToken(&quot;\\)&quot;);
        Grule L = lang.newGrule();
        Grule Q = lang.newGrule();

        lang.defineGrule(L, CC.EOF).action(new Action() {
            public String act(Object matched) {
                return (String) ((Object[]) matched)[0];
            }
        }); // S ::= L $
        L.define(CC.ks(Q)).action(new Action() {
            public String act(Object matched) {
                Object[] ms = (Object[]) matched;
                StringBuilder sb = new StringBuilder();
                for (Object m : ms)
                    sb.append(m);
                return sb.toString();
            }
        });// L ::= Q*
        /*
         * Q ::= 'a' | 'bc' | '(' Q ')'
         */
        Q.define(a).alt(bc).alt(lp, Q, rp).action(new Action() {
            public String act(Object matched) {
                // returns the middle element matched, that's the returned value
                // of the enclosing 'Q' rule
                return (String) ((Object[]) matched)[1];
            }
        });

        Exe exe = lang.compile();
        System.out.println(exe.eval(&quot;a(a)((bc))&quot;));
    }
}</code></pre></noscript></div>


<p>You can download and play around with it on your own.</p>

<p>Dropincc.java is currently on its very initial stage. It has some major improvements to be done:</p>

<ul>
<li>It uses java&#8217;s built-in regEx implementation to support token definition, so it couldn&#8217;t do &#8216;longest match&#8217; currently. This should be fixed later.</li>
<li>Due to some LL(*) analysis issues, &#8216;Non-LL regular&#8217; exceptions may be thrown when it encounters some special case of grammar rules. This must be fixed soon.</li>
</ul>


<p>There is a more practical <strong>Hello World</strong> example which implements a full-featured calculator in the quick start guide of dropincc.java. On its project <a href="https://github.com/pfmiles/dropincc.java">home page</a>. Go and check out there if you like.</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[The Real World Tree]]></title>
    <link href="http://pfmiles.github.io/blog/the-real-world-tree"/>
    <updated>2012-07-21T23:50:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/the-real-world-tree</id>
    <content type="html"><![CDATA[<h2>冈和金的约见，是在在世界之树的顶端, 这对奇特的父子，让无数人期待了15年&#8230;</h2>

<p><img src="http://pfmiles.github.io/images/worldtree/tree1.png" alt="tree1" /></p>

<!-- more -->


<h2>以冈之见，这是世界最高的树(其实只是道听途说)&#8230;</h2>

<p><img src="http://pfmiles.github.io/images/worldtree/tree2.png" alt="tree1" /></p>

<h2>然而金说：</h2>

<blockquote><p>&#8230;真相是&#8230;它只是停止生长的一棵小树而已&#8230;<br/>
因为..<br/>
..营养不足&#8230;所以“只能成长到这地步”..</p></blockquote>

<p><img src="http://pfmiles.github.io/images/worldtree/tree3.png" alt="tree1" /></p>

<h2>&#8220;真正的世界之树&#8230;&#8221;</h2>

<h2>&#8221;..扎根于山脉&#8230;&#8221;</h2>

<h2>&#8220;&#8230;汲取岩浆..&#8221;</h2>

<h2>&#8220;穿破大气层尚能继续成长&#8230;&#8221;</h2>

<p><img src="http://pfmiles.github.io/images/worldtree/tree4.png" alt="tree1" /></p>

<h2>它就存在于这世界的<em>&#8220;外侧&#8221;</em>..</h2>

<p><img src="http://pfmiles.github.io/images/worldtree/tree5.png" alt="tree1" /></p>

<h2>这才是学校不会教给你们的<strong>&#8220;真相&#8221;</strong>..金对自己的儿子说.</h2>

<p><img src="http://pfmiles.github.io/images/worldtree/tree6.png" alt="tree1" /><br/>
<img src="http://pfmiles.github.io/images/worldtree/tree7.png" alt="tree1" /><br/>
<img src="http://pfmiles.github.io/images/worldtree/tree8.png" alt="tree1" /></p>

<h2>冈恍然：</h2>

<p>原来我们熟知的“这个世界”，只是无比巨大的世界中的&#8230;<br/>
<strong>“一小部分啊”</strong>&#8230;</p>

<p><img src="http://pfmiles.github.io/images/worldtree/tree9.png" alt="tree1" /></p>

<h2>是的，它就在外面，outside .. of ..the world&#8230;</h2>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[LL(*)的概念与实现]]></title>
    <link href="http://pfmiles.github.io/blog/concept-and-implementation-of-ll-star"/>
    <updated>2012-07-14T13:59:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/concept-and-implementation-of-ll-star</id>
    <content type="html"><![CDATA[<h3>概念和起源</h3>

<p>LL(*)是由<a href="http://www.cs.usfca.edu/~parrt/">Terrence Parr</a>教授创造的，为使用<a href="http://en.wikipedia.org/wiki/LL_parsing">LL分析</a>的语法解析器做超前查看(look ahead)的一种算法。按照Parr教授的说法，这个算法从最初的想法至今的完善和调整已经历了15年。目前该算法的一个著名的实现在<a href="http://www.antlr.org/">antlr3</a>中。</p>

<h3>特点，n言以蔽之&#8230;</h3>

<ul>
<li>对于语法产生式分支的预测判断，走LL分析路子的解析器，其能力完全取决于能超前查看多少个token。传统地讲，LL(1), LL(2)直至LL(k)，就是在讲该解析器能够在语法分析过程中超前查看1, 2, k&#8230;个token。</li>
<li>而LL(*)的意思就是，它在语法解析的过程中，超前查看的token个数不是固定的，是可伸缩的，不过这一点LL(k)分析也能做到(在k范围之内&#8230;)；</li>
<li>但是，LL(*)还能越过一些重复出现的token，“到达”这些重复出现的token之后的token来做分析，这一点LL(k)是无法办到的(LL(k)无法意识到有token在循环出现，不管情况如何，它都将在尝试k个token之后放弃)；</li>
<li>如果将超前查看的决策逻辑画成DFA的话，就是这样的一种形式：<img src="http://pfmiles.github.io/images/ll3.png" title="Look Ahead DFA" alt="Look Ahead DFA" />

<ul>
<li>这张图画的是这种语法规则的超前查看决策情况：<code>A ::= a b c | a b e</code>, 显然这是一个LL(3)语法；</li>
<li>但是这样的语法: <code>A ::= a b* c | a b* e</code>是无法被LL(k)识别的，因为中间的<code>b*</code>代表“0个或多个b”(kleene闭包)，这并不是一个固定的重复次数，因此LL(k)无法识别，for any k&#8230;</li>
<li>但是，LL(*)算法能够构造出这样的DFA来识别它：<img src="http://pfmiles.github.io/images/llstar.png" title="LL(*) Look Ahead DFA" alt="LL(*) Look Ahead DFA" /></li>
<li>也就是说，传统LL(k)的look ahead DFA是不带环的，而LL(*)算法能构造出带环的DFA来做判断，它能越过无穷多个存在于环上的token，从而“到达”环之后的token继续做判断。</li>
</ul>
</li>
<li>上面的<code>A ::= a b* c | a b* e</code>语法使用了<a href="http://pfmiles.github.io/blog/left-recursion-removal-using-kleene-closure/">&#8220;kleene闭包&#8221;表示法</a>来表示“0个或多个”，这种表示法在正则表达式中很常见；事实上，基于LL(*)算法实现的语法解析器生成器(比如antlr3)对Kleene闭包表示法特别友好，可以鼓励使用，还能顺便解决一些LL分析法所不允许的“<a href="http://en.wikipedia.org/wiki/Left_recursion">左递归</a>”。</li>
<li>大多数情况来讲，LL(*)的识别能力弱于<a href="http://en.wikipedia.org/wiki/LR_parser">LR(k)</a>，但也有少数情况是LR(k)识别不了但LL(*)可以的，所以LL(*)与LR(k)之间并没有严格的强弱顺序。</li>
<li>LL(*)本身对语法的识别能力也是有限的，比如它无法区分&#8221;具有相同的递归规则前缀&#8221;的多个分支，这种情况是要尽量避免的，大多数能够较容易地改写;</li>
<li>对于LL(*)不能正确分析的情况，还能引入&#8221;Semantic Predicate&#8221;(语义断言)来辅助判断, Semantic Predicate可以是任何逻辑，只要返回一个bool值就行；有了Semantic Predicate的辅助，LL(*)甚至能够parse一些上下文相关的语法，实际上它能parse C++</li>
</ul>


<h3>主要算法及其实现(python)</h3>

<p><strong> Parr教授在2011年发表的paper&#8221;LL(*): The Foundation of the ANTLR Parser Generator&#8221;中详细描述了这个算法，下面就是其主要过程，具体的代码实现(python)在工程<a href="https://github.com/pfmiles/llstar">llstar</a>中 </strong></p>

<!-- more -->


<p>为了简单起见，约定大写字母用来命名non-terminal, 小写字母命名terminal或Semantic Predicate，<code>$</code>表示EOF，假设有如下语法规则：</p>

<pre><code>S ::= A $  
A ::= a c*  
    | b c*  
</code></pre>

<ul>
<li>针对此语法规则，构造Augmented Transition Network(ATN)，其实也就是一个NFA，NFA的边就是terminal或non-terminal或者Semantic predicate：<img src="http://pfmiles.github.io/images/atn.png" alt="ATN network" />, 代码在llstar工程的<code>atn_creation.py</code>的<code>rule.merge_to_atn</code>方法中。</li>
<li>接下来将要对这个ATN实施的算法其实就是经典的<a href="http://en.wikipedia.org/wiki/Powerset_construction">Subset Construction算法</a> —— 的改造版本：在“空边闭包运算(closure)”中加入了压栈、出栈功能，用于处理运算过程中<code>closure</code>函数经过non-terminal边时对其所对应的ATN的调用和返回。<br/>
这个算法的具体描述是比较复杂，在Parr教授的paper中已有精确描述。不过真的要用代码实现起来，某些细节还需稍微修饰，才能正确地实现。<br/>
最后的结果，其实就是使用更改后的版本的Subset Construction算法，将上述ATN(NFA)转化为一个个DFA，每条语法规则都对应一个DFA作为其look ahead DFA。<br/>
例如上面的<code>S</code>规则最后的DFA为：<img src="http://pfmiles.github.io/images/sdfa.png" alt="S DFA" />, well, 就一个终结态，没任何状态转换 —— 这是当然的，S规则只有一个alternative production&#8230; <br/>
而<code>A</code>规则的DFA为：<img src="http://pfmiles.github.io/images/adfa.png" alt="A DFA" />, 意思就是，如果第一个token为<code>a</code>，就选择第一个分支，若是<code>b</code>，就选择第二个分支，这是一个LL(1)的语法。<br/>
简单来说就是这样，具体可以参考llstar的代码&#8230;这花了我不少时间调试出来的代码，还是直接看代码了解最直接:)</li>
</ul>


<h3>实验台及例子介绍</h3>

<p>OK，主要的算法原理了解之后，展示了2个玩具例子，似乎还不能看出LL(*)的特点来。<br/>
下面我将逐步展示一些真正non-trivial的例子，以表明它真的不是过家家&#8230;</p>

<p>LL(3)(更正：或许这该是LL(4)可能我数错了)语法(对应llstar工程中的<code>LL_3_many_alts.py</code>):</p>

<pre><code>S ::= A $
A ::= B a*
    | C a+
    | D a?
B ::= a b c C
    | a b c D
    | d
C ::= e f g D
    | e f g h
D ::= i j k l
    | i j k m
</code></pre>

<p>这个语法是固定的LL(3)，没有什么特别，不过分支比较多, 它的ATN：<img src="http://pfmiles.github.io/images/ll3atn.png" alt="LL(3) ATN" /><br/>
规则<code>A</code>的DFA: <img src="http://pfmiles.github.io/images/llstar/ll3adfa.png" alt="LL(3) Rule A DFA" /><br/>
规则<code>B</code>的DFA: <img src="http://pfmiles.github.io/images/llstar/ll3bdfa.png" alt="LL(3) Rule B DFA" /><br/>
规则<code>C</code>的DFA: <img src="http://pfmiles.github.io/images/llstar/ll3cdfa.png" alt="LL(3) Rule C DFA" /><br/>
规则<code>D</code>的DFA: <img src="http://pfmiles.github.io/images/llstar/ll3ddfa.png" alt="LL(3) Rule D DFA" /></p>

<p>上面这个语法，LL(4)分析也能搞定，而真正体现出LL(*)特点的是下面这样的语法(对应llstar工程中<code>over_kleene.py</code>)：</p>

<pre><code>S ::= A $
A ::= a* b
    | a+ c
</code></pre>

<p>其中，规则<code>A</code>的2条分支拥有共同的kleene闭包前缀，LL(k)是无法识别的，它的ATN:<img src="http://pfmiles.github.io/images/llstar/overkleeneatn.png" alt="Over Kleene ATN" /><br/>
而LL(*)能够为<code>A</code>生成这样的DFA：<img src="http://pfmiles.github.io/images/llstar/overkleeneadfa.png" alt="Over Kleene Rule A DFA" /><br/>
这个DFA能够越过terminal<code>a</code>的任意重复，从而考虑到后面的terminal<code>b</code>和<code>c</code>来做判断<br/>
而下面这个更加&#8221;恶劣&#8221;的列子则更能说明LL(*)的这个特征(对应llstar工程中<code>over_non_recurse_rule.py</code>)：</p>

<pre><code>S ::= A $
A ::= B* b
    | C+ c
B ::= a d
    | e
C ::= a d
    | e
</code></pre>

<p>这个例子中，<code>B</code>和<code>C</code>完全相同，并分别被包含在规则<code>A</code>的2条分支的kleene闭包中，<br/>
最终生成的<code>A</code>的DFA: <img src="http://pfmiles.github.io/images/llstar/nonrecursiveradfa.png" alt="Non-recursive Rule A DFA" /></p>

<p>上面提到过，LL(*)也有不能解决的情况，比如2条分支拥有&#8221;共同的、递归的规则作为前缀&#8221;，比如这样：</p>

<pre><code>S ::= A eof
A ::= E a
    | E b
E ::= c E d
    | e
</code></pre>

<p>上面的<code>A</code>规则的两条分支拥有共同的前缀<code>E</code>，而<code>E</code>本身是一条递归规则，这样的规则是LL(*)无法分析的，在llstar工程中对应<code>experiments/common_recurse_prefix_fail.py</code>, 运行的时候会抛出错误提示。这种情况在antlr3中会将parsing策略退化为LL(1) + 回溯的形式。</p>

<pre><code>Traceback (most recent call last):
  File "/home/pf-miles/myWorkspace/llstar/experiments/common_recurse_prefix_fail.py", line 31, in &lt;module&gt;
    d_a = create_dfa(ra.get_start_state(globals_holder.a_net))
  File "/home/pf-miles/myWorkspace/llstar/algos.py", line 136, in create_dfa
    d_state_new.add_all_confs(closure(d_state, conf))
  File "/home/pf-miles/myWorkspace/llstar/algos.py", line 99, in closure
    raise Exception("Likely non-LL regular, recursive alts: " + str(d_state.recursive_alts) + ", rule: " + str(globals_holder.a_net.get_rule_of_state(p)))
Exception: Likely non-LL regular, recursive alts: set([0, 1]), rule: E
</code></pre>

<p>还有一些特殊情况，比如规则完全就是冲突的，那么这个时候就是Semantic Predicate发挥作用的时候(对应llstar工程中<code>conflicting_with_preds.py</code>)：</p>

<pre><code>S ::= A $
A ::= {pred1}? B
    | {pred2}? b
B ::= b
    | b
</code></pre>

<p>最终<code>A</code>的DFA：<img src="http://pfmiles.github.io/images/llstar/confresolvedwithpredsadfa.png" alt="Conflict Resolved With Preds A DFA" /><br/>
实际开发中，写出这样的规则是坑到爷的&#8230;不过LL(*)还算能很好解决&#8230;其实这里就算没有Semantic Predicate, LL(*)也能按照convention，“选择较早定义的语法分支”来解决。</p>

<p>还有就是在分析的过程中会导致分析栈溢出(不是程序语言的callstack的overflow, 而是LL(*)的closure操作维护的一个规则调用栈溢出)的时候，LL(*)也会使用Semantic Predicate来辅助判断, 比如规则(对应llstar中<code>overflow_with_preds.py</code>):</p>

<pre><code>S ::= A $
A ::= {pred1?} B a
    | {pred2?} b* c
    | {pred3?} b* c
B ::= b+ B
</code></pre>

<p>规则<code>A</code>的三条分支全部存在严重冲突(都拥有能识别无穷个&#8217;b&#8217;的前缀)并且其中一个是另一条递归规则<code>B</code>，这种形式会导致LL(*)的分析栈溢出，不过仍然没关系，这样的情况能在溢出发生时，调用<code>pred1</code>、<code>pred2</code>和<code>pred3</code>来解决(这三个pred就是Semantic Precicate，是能包含任何逻辑但最终返回bool值的表达式)<br/>
生成的规则<code>A</code>的DFA: <img src="http://pfmiles.github.io/images/llstar/overflowadfa.png" alt="Overflow A DFA" /><br/>
这里设定的最大分析递归层数为<code>10</code>，因此，DFA在接受了第10个&#8217;b&#8217;之后达到了溢出状态<code>d14</code>，这时调用了各个alternative附带的几个predicate来解决冲突&#8230;</p>

<blockquote><p>(2012-09-03 注： 实际上上述规则是不正确的，<code>B ::= b+ B</code>是有问题的规则，因为<code>b+</code>会贪婪地match掉所有的连续的<code>'b'</code>，导致后面的<code>B</code>只可能抛错; 所以这个例子也只能用来演示分析栈溢出的情况，实际应用中是不可能写出这样的规则的)</p></blockquote>

<h3>总结</h3>

<p>OK, 大概如是了；上述算法的实现、例子的代码均在<a href="https://github.com/pfmiles/llstar">llstar</a>工程中能找到<br/>
llstar工程是我花了不少时间实现并调试好的一块LL(*)算法的“实验台”，可以在里面慢慢把玩各种变态的、五花八门的语法规则，以验证LL(*)的分析能力<br/>
在工程的<code>experiments</code>文件夹下已经有许多具有代表性的例子&#8230;都是python代码<br/>
另外，llstar工程是在eclipse + pydev环境下开发的，因此如果要在命令行里运行，可能要对例子里面的import路径稍作修改，当然，最好是直接在eclipse + pydev环境下运行它们了<br/>
在linux环境下，llstar的所有例子都能自动生成上文中看到的各种DFA/NFA图像，不过前提是环境中要装有<a href="http://www.graphviz.org/">graphviz</a></p>

<p>现在的所有语法解析器生成器中，似乎都是LR分析的天下，LL分析大多是手写解析器的首选&#8230;<br/>
不过在现有的使用LL分析方式的产品中，也就只有LL(*)和PEG(Packrat)parsing比较常见也比较实用了，能与LR分析一较高下。<br/>
而配上回溯策略的LL(*)是严格强于Packrat parsing的，这样看来大概走LL分析路子的自动化工具也只有LL(*)容易一枝独秀了(想必这也是antlr相对较为流行的原因)。</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[Algo-class第二周小记: Master Method]]></title>
    <link href="http://pfmiles.github.io/blog/algo-class-week2-notes-master-method"/>
    <updated>2012-04-03T11:40:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/algo-class-week2-notes-master-method</id>
    <content type="html"><![CDATA[<p>week2主要讲了master method，感觉从来没有听过如此清晰有条理的介绍master method的讲解，不得不佩服<a href="http://theory.stanford.edu/~tim/">Tim Roughgarden</a>教授的功力。<br/>
从一些随课笔记总结起来，master method是用来预估divide and conquer算法的大O时间复杂度的公式；它要求divide的时候“所有sub-problems的规模都相等”才能适用。<br/>
要使用master method, 首先要将算法的时间消耗函数写成递推公式形式：
$$T(n) &lt;= aT(\frac{n}{b}) + O(n^d)$$
其中T(n)是本层递归所消耗的时间，$T(\frac{n}{b})$自然就是下一层递归所消耗的时间了，b就是每次往“下层”递归调用时问题规模缩小的倍率，a就是代码中递归调用的个数；$O(n^d)$ 是将递归调用之外的其它代码的时间开销写成关于输入规模n的指数形式，d就是这个指数。<br/>
基础情况： 当n足够小时，T(n) &lt;= 一个常数<br/>
a,b,d与输入规模无关。<br/>
那么，根据a,b,d的情况，T(n)可能被表示为三种情况：<br/>
<img src="http://pfmiles.github.io/images/masterMethod.png" title="Master Method" alt="Master Method" /></p>

<!-- more -->


<p>对于这个式子，我个人的、不严格的、直觉的理解就是：</p>

<ol>
<li>当$a = b^d$时，程序规模被divide之后，合并代价增大的幅度与程序规模缩小的幅度相当，所以复杂度公式中合并代价部分和切分、解决部分的复杂度都要算在里面</li>
<li>当$a &lt; b^d$时，合并代价增长快于切分、解决缩小幅度，所以复杂度公式中只算合并代价部分</li>
<li>当$a > b^d$时，切分、解决部分时间代价占主导，忽略递归调用以外的项，只写出divide and conquer递归调用部分的时间开销</li>
</ol>


<p>不过其实这个是有严格的证明的：<br/>
设$T(n) = aT(\frac{n}{b}) + cn^d$<br/>
对于第j层递归 ，运算量为：$a^j \times c \times (\frac{n}{b^j})^d$<br/>
即：$cn^d(\frac{a}{b^d})^j$，所以a和$b^d$的大小关系是关键！<br/>
进而总计算时间： $total work \leqslant cn^d \centerdot \sum\limits_{j=0}^{\log_bn}(\frac{a}{b^d})^j$, 然后通过这个式子，由a和$b^d$的大小关系可以较容易想通为什么master method会是上述这种三段分段函数的形式。<br/>
Week2作业是快排&#8230;写个快排倒是简单，可是作业要求要count快排过程中的比较次数&#8230;在作业论坛里面看到哀嚎声一片&#8230;毕竟实现只要稍微有点偏差，虽然同样是快排，确实很容易比较次数不一样。<br/>
值得一提的是讲解中给出的in-place的快排partition方法，就是不用建立额外的数组来进行partition，python示意代码如下：</p>

<pre><code>def partition(pivotIndex, arr):
    swap(arr, 0, pivotIndex)
    pivot = arr[0]
    i = 1 # index 0...i &lt; pivot
    j = 1 # index i...j &gt; pivot
    for k in range(1, len(arr)):
    if arr[k] &lt;= pivot :
        swap(arr, i, k)
        i += 1
        j += 1
    else:
        j += 1
    return (arr[1:i], pivot, arr[i:j])
</code></pre>

<p>另外，从快排的例子可以看出，若divide and conquer算法是基于某种比较结果，将问题规模初步divide and conquer的话，每一次比较“能否将问题划分为规模差不多均等的子问题”将很大地影响算法实际的执行效率。</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[使用Kleene闭包语法糖消除语法中的左递归]]></title>
    <link href="http://pfmiles.github.io/blog/left-recursion-removal-using-kleene-closure"/>
    <updated>2012-03-28T11:18:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/left-recursion-removal-using-kleene-closure</id>
    <content type="html"><![CDATA[<p>一般来讲，如果使用的解析器生成器是基于LL分析法来解析文本的话(比如antlr)，我们就需要在编写语法规则的时候避免<a href="http://en.wikipedia.org/wiki/Left_recursion">左递归</a>。<br/>
虽然有一套成熟的、公式化的方法来去除左递归，但它会影响原有文法的结合顺序、优先级，或者多出一些本不需要的、额外的产生式。<br/>
例如，有左递归语法规则：</p>

<pre><code>addition ::= addition '+' factor
           | factor
</code></pre>

<p>这个式子其实是想要表达一个“一连串+号组成的和”的表达式，例如<code>1+2+3+4</code>；<br/>
假设目前的输入就是<code>1+2+3+4</code>, 那么超前查看带来的选择应该是<code>addition '+' factor</code>这个产生式；于是在parser的代码中立刻就又直接调用了<code>addition()</code>方法，但注意，整个递归过程没有消耗掉任何token&#8230;也就是说，当流程再次递归到<code>addition</code>函数里时，输入<code>1+2+3+4</code>并没有任何改变，这又会进入下一轮递归&#8230;很快就会overflow。<br/>
这个问题，除了机械性地按照公式来消除左递归外，还可以改写语法规则，使其成为右递归语法：</p>

<pre><code>addition ::= factor '+' addition
           | factor
</code></pre>

<p>这样就不用stackOverFlow了，但是带来另一个问题：这使得我们的&#8217;+&#8217;加法成为了一个&#8217;右结合&#8217;的运算&#8230;<br/>
也就是说，<code>1+2+3+4</code>的计算次序是这样的：<code>1+(2+(3+4))</code><br/>
还好这里是“加法”，整数集合和加法运算构成“阿贝尔群(可交换群)”，满足交换律，所以就算实现成右结合的也能蒙混过关&#8230;但减法呢？除法呢？</p>

<!-- more -->


<p>难道要先生成一个AST，再写个visitor，把节点顺序给rewrite一下，然后再写个visitor求值？这么麻烦就为了实现一个简单的四则运算功能也太坑爹了。</p>

<p>其实，我们在这里使用递归，只是为了表达元素的“重复”这种意思；的确，递归能表示“重复”的概念，但这很容易让人联想到“循环”，因为平时的编程中，我们都通常使用循环来表达“重复”这种东西的。<br/>
更重要的是，循环与<a href="http://en.wikipedia.org/wiki/Tail_call">尾递归</a>在逻辑上是等价的，这使得我们可以将上述左递归改写成某种表示“循环”的形式，在这里，<a href="http://en.wikipedia.org/wiki/Kleene_star">Kleene Closure(克林闭包)</a>就正是一种表达“循环”的标记形式。<br/>
熟悉正则表达式的我们都知道，符号<code>*</code>(kleene star)和符号<code>+</code>(kleene cross)分别用来表示前面临接元素的“0个或多个”和“一个或多个”，如果这种标记用在我们的语法规则中那就酷毙了：</p>

<pre><code>addition ::= (factor '+')* factor
</code></pre>

<p>表达的意义和&#8221;左递归版本&#8221;的语法规则是一样的，但是，这种记法的重大意义就是：在生成的parser程序中可以直接以一个<code>while</code>语句来解析重复的<code>(factor '+')</code>而不用再递归回<code>addition</code>中！这样就避免了parser中的左递归实现带来的问题！<br/>
由于kleene闭包所能表达的所有语法规则形式都能被递归所表达，所以引入kleene闭包并没有从形式上增加语法解析器生成器的表达能力，所以说kleene闭包只是一个“语法糖”。<br/>
但它的实现意义却是重大的：解决了“为了表达‘元素重复’”的这一类左递归问题。
当然，<a href="https://github.com/pfmiles/dropincc.java">dropincc.java</a>也会支持kleene闭包的表达形式，大致的api形式如下：</p>

<pre><code>addition.fillGrammarRule(addend, CC.ks(ADD.or(SUB), addend));
</code></pre>

<p><code>CC.ks</code>方法就是kleene star的意思，当然还有<code>CC.kc</code>，顾名思义。</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[[algo-class]第一周作业——Count Inversions]]></title>
    <link href="http://pfmiles.github.io/blog/algo-class-week-one-assignment-counting-inversions"/>
    <updated>2012-03-25T15:41:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/algo-class-week-one-assignment-counting-inversions</id>
    <content type="html"><![CDATA[<p><a href="http://algo-class.org">algo-class</a>还是挺有意思的，一上来就讲merge sort；介绍了分治法以及&#8221;piggyback&#8221;的思路&#8230;当作是复习吧：</p>

<h3>分治法(divide and conquer)</h3>

<ol>
<li>divide into smaller problems</li>
<li>conquer sub-problems recursively</li>
<li>combine solutions of problems into one for the original problems</li>
</ol>


<p>而&#8221;piggyback&#8221;的意思就是：记住一些经典算法的实现，遇到类似问题的时候，可以将要解决的问题“搭载”到那些经典算法上面，一般都具有和那些经典算法相同的平均时间复杂度；相当于是把那些经典算法当作一个个“模式”或者“骨架”了(所以说平时经常听到的经典算法还是要熟悉熟悉的，很多地方能派上用场)。</p>

<p>这一周围绕merge sort来讲divide and conquer真是再合适不过了；而作业“Count Inversions”就是一个将场景piggyback到merge sort上的一个典型例子；  作业给出了一个包含10W行数据的文本文件，每一行一个随机数字，要求找出这10W个数字中的所有Inversions。我用python实现如下：</p>

<pre><code>def countInversions(arr):
    length = len(arr)
    if length == 0 or length == 1:
    return (0, arr) 
    mid = int(length / 2)
    (leftCount, leftSortedArr) = countInversions(arr[0:mid])
    (rightCount, rightSortedArr) = countInversions(arr[mid:length])
    (mergedCount, mergedSortedArr) = mergeCount(leftSortedArr, rightSortedArr)
    return (leftCount + rightCount + mergedCount, mergedSortedArr)

def mergeCount(lArr, rArr):
    count = 0
    mergedArr = []
    i = 0
    j = 0
    lenl = len(lArr)
    lenr = len(rArr)
    while i &lt; lenl and j &lt; lenr:
    if lArr[i] &gt; rArr[j]:
        count += lenl - i # key line
        mergedArr.append(rArr[j])
        j += 1
    else:
        mergedArr.append(lArr[i])
        i += 1
    if i &lt; lenl:
    mergedArr.extend(lArr[i:lenl])

    if j &lt; lenr:
    mergedArr.extend(rArr[j:lenr])
    return (count, mergedArr)

import sys
if len(sys.argv) &lt; 2:
    print 'usage: python countInversionInAFile path_to_file'
    exit(1)
numbers = [int(line) for line in open(sys.argv[1], 'r')]
print countInversions(numbers)[0]
</code></pre>

<p>程序或许想起来简单但实际上要正确还是要费点功夫的；有些地方没想到的还非得debug才能看清楚为什么，比如程序中标注为&#8221;key line&#8221;那里，本来我写的是<code>count += 1</code>的但怎么都不对，后来debug才看出来应该写<code>count += lenl - i</code>。</p>

<p>另外，本来打算跟2门课程的，但现在看来我这忙碌的程序员完全没有时间&#8230;只好放弃“机器人汽车”那门课目前专门跟这一门了，毕竟“算法”的可操作性要强一些&#8230;</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[dropincc.java API design]]></title>
    <link href="http://pfmiles.github.io/blog/dropincc-dot-java-api-design"/>
    <updated>2012-03-18T16:29:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/dropincc-dot-java-api-design</id>
    <content type="html"><![CDATA[<p><a href="https://github.com/pfmiles/dropincc.java">dropincc.java</a>为了使得用户能够在java语言中直接定义新语言的词法、语法规则，API设计采用了串接与组合(cascading &amp; composition)风格的<a href="http://martinfowler.com/bliki/FluentInterface.html">FluentInterface</a>形式。</p>

<p>这种形式能够使得这一套API看起来更具有“业务语义”，而不需要像antlr等其它工具一样强迫用户去学习全新的另外一种含有业务语义的DSL。<br/>
新语言的词法、语法规则被用户直接在java语句里书写、执行，其实得到的是dropincc.java这个CC工具的内部概念的AST。这个AST其实与“让用户学习一套DSL，然后编写，然后编译这些DSL得到的AST”是一样的。<br/>
也就是说 —— dropincc.java里面很重要的一个理念就是：像书写字面量一样书写CC工具的AST(AST literal???)。</p>

<blockquote><p>注意：强调一下这里说的AST并非用户想要实现的新语言的AST，我指的是dropincc.java这个工具其内部表达词法、语法规则的内部形式。</p></blockquote>

<p>经过一些初步的尝试，我认为在java中定义出这样一套API是完全可行的，其中一些值得列出的、具有代表性的点如下：</p>

<!-- more -->


<ol>
<li>词法规则强制用户限定在正则文法的表达能力之内(即使用正则表达式，例子略)</li>
<li>上下文无关文法的表示主要是解决3种形式的表示：连接、选择、递归;

<ol>
<li>其中“连接”的表示, 若BNF为：<code>term ::= LEFTPAREN expr RIGHTPAREN</code>, 则右边的部分在java中表达为：<code>func(LEFTPAREN, expr, RIGHTPAREN)</code>;即：“以方法传参的自然按顺序排列表达‘连接’的意思”;而其中<code>expr</code>是一个non-terminal，也就是说这里要引用<code>expr</code>这个规则，这也就表达了“递归” —— 要递归地引用<code>expr</code>的话那么直接写在这里就好了；</li>
<li>“选择”的表示，即一个产生式有好几个alternative的情况，若BNF是<code>term ::= DIGIT multail | LEFTPAREN expr RIGHTPAREN | DIGIT;</code>, 则java中表达为：<code>func(DIGIT, mulTail).alt(LEFTPAREN, expr, RIGHTPAREN).alt(DIGIT);</code>。</li>
</ol>
</li>
<li>上述3种基本元素的表达具备之后，其实已经足够表达出复杂的语法了，不过为了“更好的体验”，为了用得更方便，我认为还应该加入“子rule语法糖”。即让使用者能够以“加括号”的方式在产生式中直接定义子规则，而不必每次都单独写成一个产生式，这种做法应该能很受欢迎，比如：

<ul>
<li>第一个产生式是：<code>MUL_DIV ::= MUL | DIV;</code></li>
<li>第二个产生式是：<code>mulTail ::= MUL_DIV term;</code></li>
<li>其实，若是有了前面说的语法糖，那么上述2个产生式就可以合并为：<code>mulTail ::= (MUL | DIV) term;</code>, 少了<code>MUL_DIV</code>这个没太多意义的产生式定义；</li>
<li>在java中表达为：<code>func(MUL.or(DIV), term)</code>; 若子规则中想表达的不是“选择”关系，而是“连接”关系的话，也就是<code>mulTail ::= (MUL DIV) term;</code>的话，在java中表达为：<code>func(MUL.and(DIV), term)</code>; 其中<code>and</code>这个方法就是表达“连接”关系，只不过加了括号，成为了一个子规则而已。</li>
</ul>
</li>
</ol>


<p>OK, dropincc.java的核心FluentInterface形式的API应该就这些了，我相信这是一种很自然的方式，用户需要掌握的东西很少。</p>

<h3>设计FluentInterface风格API过程中的经验总结</h3>

<p>对于这个接口设计，我的经验就是：</p>

<ol>
<li>传入参数尽量“泛化”、“统一接口化”;这个“统一接口”最好不要包含任何方法(也就是说只是一个标记接口)，否则会给FluentInterface带来一些令人困惑的方法选项(当用户敲入&#8217;.&#8217;操作符的时候将会在IDE工具的方法提示里多出很多不必要的方法)。</li>
<li>每个串接方法的返回结果可以随意“具体化”，因为这个返回结果的具体类名是不必展示给用户看的，所以你打算让用户下一步还能串接出什么样的方法，就尽管去返回一个具体的子类；但要注意返回结果不应该有太深的继承层次，否则“下一步串接”(当用户敲入&#8217;.&#8217;操作符的时候)将会在IDE工具里列出令人困惑的方法列表 —— 一般就一层继承关系 —— 继承自Object —— 一个接口实现 —— 就是1中所述的“泛化接口”，这样做方便你将返回值继续传入另一个方法中 —— 实现为所欲为的cascading &amp; composition&#8230;</li>
</ol>


<h3>以闭包的形式嵌入动作代码</h3>

<p>几乎所有的CC工具都提供一种“在match到特定的节点或树模式时允许执行一段用户自定义代码”的功能；这种自定义代码我把它叫做“动作代码”, “action”。无论是lex &amp; yacc或是antlr都是这样。<br/>
这个功能几乎是必须的，这提供了一种自由度相当高的形式让用户可以自定义AST节点，或是直接在parse的过程当中做一些自定义的计算，然后当整个parse结束时直接输出的就是整个的计算结果。<br/>
动作代码一般来讲，都是用该CC工具所要生成的程序所使用的语言来写的；比如lex要生成C代码，他们的动作代码就是C来写的；antlr要生成java代码，那么它的动作代码自然就是java写的（当然antlr也能生成其它语言代码，相对应的，就使用那种语言来编写动作代码）。
dropincc.java既然设计目标是要嵌入到java语言中去使用，自然就是要用java语言来写动作代码了；<br/>
但是，跟lex &amp; yacc或者antlr不同的是，我并不打算让用户写一些残缺不全的动作代码放在某个约定的位置然后在生成目标程序的过程中将它们“编织”到目标程序中，这样的话就跟传统的CC工具没有任何区别了，没有什么实质上的改进；<br/>
既然dropincc.java是“嵌入”到普通的java应用程序代码中间工作的，那么它完全有理由使用“闭包(closure)”的形式来组织“动作代码”！为什么用“闭包”？因为dropincc.java是“嵌入”到业务代码中使用的，用闭包来写动作代码可以capture一些业务代码上下文信息，这对构建DSL来讲是非常大的便利！<br/>
比如，你的业务代码上下文里面有个<code>OrderService</code>对象，它负责一些&#8221;订单&#8221;业务逻辑，而当你编写一个闭包作为动作代码的时候，你完全可以&#8221;capture&#8221;上下文中的这个<code>OrderService</code>对象，从而使得你创造的语言在执行逻辑上与订单业务紧密、无缝地结合 —— 这是一种非常平滑的构建DSL的方式。</p>

<h3>最终的样子</h3>

<blockquote><p>注：此段代码只代表示意的风格、API情况，虽然能编译通过、运行，但不一定是行为完全正确四则运算表达式计算器</p></blockquote>

<pre><code>// 3.define lexical rules
Lang calculator = new Lang();
Token DIGIT = calculator.addToken("\\d+");
Token ADD = calculator.addToken("\\+");
Token SUB = calculator.addToken("\\-");
Token MUL = calculator.addToken("\\*");
Token DIV = calculator.addToken("/");
Token LEFTPAREN = calculator.addToken("\\(");
Token RIGHTPAREN = calculator.addToken("\\)");
// 2.define grammar rules and corresponding actions
Grule expr = new Grule();
Grule term = new Grule();
Element mulTail = calculator.addGrammarRule(MUL.or(DIV), term).action(
        new Action() {
            public Object act(Object... params) {
                return params;
            }
        });
term.fillGrammarRule(DIGIT, mulTail).action(new Action() {
    public Object act(Object... params) {
        int factor = Integer.parseInt((String) params[0]);
        Object[] mulTailReturn = (Object[]) params[1];
        String op = (String) mulTailReturn[0];
        int factor2 = (Integer) mulTailReturn[1];
        if ("*".equals(op)) {
            return factor * factor2;
        } else if ("/".equals(op)) {
            return factor / factor2;
        } else {
            throw new RuntimeException("Unsupported operator: " + op);
        }
    }
}).alt(LEFTPAREN, expr, RIGHTPAREN).action(new Action() {
    public Object act(Object... params) {
        return params[1];
    }
}).alt(DIGIT).action(new Action() {
    public Object act(Object... params) {
        return Integer.parseInt((String) params[0]);
    }
});
Element addendTail = calculator.addGrammarRule(ADD.or(SUB), term)
        .action(new Action() {
            public Object act(Object... params) {
                return params;
            }
        });
expr.fillGrammarRule(term, addendTail, CC.EOF).action(new Action() {
    public Object act(Object... params) {
        int addend = (Integer) params[0];
        Object[] addendTailReturn = (Object[]) params[1];
        String op = (String) addendTailReturn[0];
        int addend2 = (Integer) addendTailReturn[1];
        if ("+".equals(op)) {
            return addend + addend2;
        } else if ("-".equals(op)) {
            return addend - addend2;
        } else {
            throw new RuntimeException("Unsupported operator: " + op);
        }
    }
});
// 1.compile it!
calculator.compile();
// 0.FIRE!!!
System.out.println(calculator.exe("1+2+3+(4+5*6*7*(64/8/2/(2/1)/1)*8+9)+10"));
</code></pre>

<p>上面约60行java代码实现了一个相当复杂的多项式计算器语言：支持加减乘除四则运算以及括号调整优先级。而以往我们使用antlr来实现这个功能的话，最终生成、放到项目中工作的java代码会以千行计。</p>

<ul>
<li>这段代码是能够完全嵌入到任何普通的java业务系统程序代码当中的，是完全语法合格、能编译通过的，这是与传统CC工具的“代码残片”表示的动作代码所不同的地方</li>
<li>其中用到了上面介绍的“以正则语言来定义词法规则”、“以FluentInterfaces来定义语法规则”，以及“以闭包的形式来书写动作代码”（java中的闭包以“匿名内部类”的形式表示，道理一样）</li>
<li>其中，动作代码是一段段由<code>Action</code>接口实现的闭包（匿名内部类），里面的代码显然可以随意引用当前上下文中的所有变量、对象，这样实现了对上下文的capture，跟业务系统的无缝结合。</li>
<li><code>Action</code>闭包带有一个方法，参数是<code>Object... params</code>，这个参数里的值以位置顺序的方式对应于该action代码所附着的产生式里面的语法元素在parsing的时候所match到的值，听起来比较绕口，但实际上很简单，比如上面的 :</li>
</ul>


<p>带括号的表达式的action:</p>

<pre><code>.alt(LEFTPAREN, expr, RIGHTPAREN).action(new Action() {
    public Object act(Object... params) {
        return params[1];
    }
</code></pre>

<p>它的<code>params</code>的长度为3，分别是<code>["(", expr子规则匹配所返回的值, ")"]</code>，而这里我们的“业务(四则运算)”只需要关心<code>expr</code>的返回值，所以动作代码直接将<code>params[1]</code>（expr的返回值）返回给上一级匹配。<br/>
就是这样，实际上你可以在动作代码里面做任何事情，只要符合java语法的、你能想到的。</p>

<p>第一个版本的API设计基本就是这样了，往后可能还会加入一些语法糖，比如“Kleen闭包”来进一步方便语法规则的定义，不过会很慎重，因为dropincc.java是以小巧、易用为设计目标的，语法糖太多很可能会帮倒忙。</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[Dropincc.java的概念与设计]]></title>
    <link href="http://pfmiles.github.io/blog/the-main-ideas-and-concepts-of-dropincc-dot-java"/>
    <updated>2012-03-17T17:40:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/the-main-ideas-and-concepts-of-dropincc-dot-java</id>
    <content type="html"><![CDATA[<h3>做这么个小lib的动机？</h3>

<p>其实由于java语言先天缺陷的元编程能力，在java的圈子里很少有人提到“DSL”的概念，就算有也是说说而已。与之相比，一些其它语言ruby, python, lisp等等，得益于其强大的元编程能力，直接利用自身语法特性，取一块语法子集，利用一些对象、类生命周期切入函数或者宏系统两三下就DSL &#8216;on-the-fly&#8217;了，这种便利性可能由java的设计目标来看，恐怕永远也无法达到了。<br/>
那么，在java里面想实现一个DSL，恐怕就得走“外部DSL(详见Fowler的文章: <a href="http://martinfowler.com/bliki/DomainSpecificLanguage.html">DomainSpecificLanguage</a>)”的路子。<br/>
而“外部DSL”这条路并不好走，说白了也就是自己做词法、语法、语义分析，自己生成目标语言代码去执行真正的逻辑；也就是做一个编译器前端外加一段解释执行逻辑；编译器前端，虽然业界看上去有很多很多工具可以直接采用，但是这些工具，目前看来，我认为还是太“General purpose”了，它们往往要求使用者学习它们自己规定的一套用作表达词法、语法规则的DSL，然后提供一个特殊的编译程序，用作编译你用它的DSL写的这些词法、语法文件，最终生成你想要的、基本不可读的编译器前端代码 —— 放到你的项目中去使用；<br/>
这种形式的工具在目前的编译器前端生成器中占大多数，使用上绝对称不上是“便利”。除了它用作描述规则的DSL需要使用者学习之外，其使用过程涉及好几个步骤与环境，是很麻烦的一件事情。<br/>
曾经有一次，一个同学试图使用antlr来做一个类似SQL子集的DSL，他花很多时间与antlr本身的语法文件、IDE “antlrworks”作斗争&#8230;频繁地在eclipse, 命令行, antlrWorks之间切换；我就想，做一个这样的DSL，是否真的用得上这么多工具？是否真的用得上号称能parse C++的antlr？这些事情能否全部在一个工作环境内搞定？比如eclipse？
而来自<a href="https://github.com/luikore/rsec">rsec</a>的启发让我觉得java似乎更应该有这样一个东西：</p>

<ol>
<li>以java的语法来新增词法、语法规则，不需要学习新的语法；</li>
<li>不需要依赖外部环境，仅在java开发环境中就能完成新语言的定义与编译器前端程序的生成；</li>
<li>虽然java是静态类型编译型语言，但整个新语言构建过程应该看上去是“动态的”、“解释性”的，这样“体验”才会好；</li>
<li>这个库要小、要没有其它三方库依赖，仅依靠JDK自带库就能使用；</li>
<li>在使用过程中尝试推行一些好的实践，确保大多数普通青年不会“自找麻烦”，比如“限制词法规则必须为正规文法(或者说乔姆斯基3型文法)”。</li>
</ol>


<p>而<a href="https://github.com/pfmiles/dropincc.java">Dropincc.java</a>正是以上述几点为设计目标的一个小巧(但足够强大)的编译器生成器。</p>

<!-- more -->


<h3>设计与实现思路</h3>

<p>以上第一点，基本上的想法就是，设计一套“串接与组合(cascading &amp; composition)”风格的API，模拟出一套parser combinator，让用户使用这套“貌似带有CC的语义”的java方法API来做词法、语法规则的添加(CC即：&#8221;compiler-compiler, 就是&#8217;编译器生成器&#8217;&#8221;)。<br/>
比如我想创建一套支持加减乘除的表达式计算器，还能使用括号调整运算优先级，我大概能用下面这样的形式直接在java代码中定义其词法、语法规则：</p>

<blockquote><p>注：下面的代码只是示意说明整体API风格，不一定是最终能运行的代码。</p></blockquote>

<pre><code>Lang lang = new Lang();
Token DIGIT = lang.addToken("\\d+");
Token ADD = lang.addToken("\\+");
Token SUB = lang.addToken("\\-");
Token MUL = lang.addToken("\\*");
Token DIV = lang.addToken("/");
Token LEFTPAREN = lang.addToken("\\(");
Token RIGHTPAREN = lang.addToken("\\)");

Grule expr = new Grule(); // grammar root
Grule term = new Grule();

Element mulTail = lang.addGrammarRule(MUL.or(DIV), term);
term.addGrammarRule(DIGIT, mulTail)
        .alt(LEFTPAREN, expr, RIGHTPAREN)
        .alt(DIGIT);
Element addendTail = lang.addGrammarRule(ADD.or(SUB), term);
expr.addGrammarRule(term , addendTail, CC.EOF);
</code></pre>

<p>其实想要表达的规则写成类似&#8221;BNF&#8221;的形式就是：</p>

<pre><code>// token rules
DIGIT ::= '\d+';
ADD ::= '+';
SUB ::= '-';
MUL ::= '*';
DIV ::= '/';
LEFTPAREN ::= '(';
RIGHTPAREN ::= ')';

// grammar rules
mulTail ::= (MUL | DIV) term;
term ::= DIGIT multail
       | LEFTPAREN expr RIGHTPAREN
       | DIGIT
       ;
addendTail ::= (ADD | SUB) term;
expr ::= term addendTail EOF;
</code></pre>

<p>这简直就是“line to line”的直译，而<a href="https://github.com/pfmiles/dropincc.java">Dropincc.java</a>的目标也就是要达到这样的效果；<br/>
这么做的目的并不是实现一套标准意义上的BNF；它使用了正则表达式来描述词法规则(token)，也就是上面提到的“目标”的第5点：“限制词法规则必须为正规文法”，这么做的意思也就是建议用户在“若词法规则中出现正规文法无法解决的意义冲突时”，将冲突“推后”到后面的语法、甚至语义分析阶段去解决；这种推荐的“较好实践”能够保持词法规则足够简单，使用正则表达式就能清晰地描述；如果用户不理解“保持词法规则足够简单”的重要性，只需要让他思考一下“为什么java的标识符不能由数字开头”应该就能想通了。<br/>
事实上就是：如果你不想自找麻烦，那么就应该保持词法规则足够简单 —— 你不应该在词法解析阶段耗费太多的实现精力 —— 这里用正则表达式就好了 —— 后面还有更麻烦、更有意义的活儿等着你去干呢&#8230;你不应该卡在词法分析这里太久&#8230;<br/>
好了，上面的这种约束一方面推行了一种“较好的实践”，另一方面也使得我们的这个工具更加直观、好用、简单，并且并不降低其实现语言的能力。</p>

<p>第二、三点，打算使用JDK1.6的新compiler API来实现；目前业界中的大多数CC工具都是“生成一个源文件”，让用户直接在项目中使用这个源文件；其实我认为这个东西以“源文件”的形式出现在项目中意义并不大，因为它几乎不可读(不可读的源代码有什么意义呢？)。只要有一个可执行的内存表示即可，“源文件”其实就不必了&#8230;这样也似乎使得项目代码看上去更“干净”。</p>

<p>至于第四点，也是很重要的，实现过程中一直保持“不依赖JDK以外的库”即可。</p>

<p>当所有的规则都定义完毕，只要在代码中触发&#8221;compile&#8221;，立刻就能基于定义的规则在内存中生成一个可执行的编译器前端，没有“源代码”，因为那没有意义，用户需要做的就只是拿它去执行新出生的语言的代码逻辑：</p>

<pre><code>lang.compile();
lang.exe("1+2+3*4/(5*6*7+8)");
</code></pre>

<p>当然，还有“action代码”的具体组织形式示例，上面没有给出，在<a href="dropincc-dot-java-api-design/">dropincc.java API Design</a>里面有详尽的阐述。<br/>
基本上对于这个工具的最终输出形式，计划中应该有两种：</p>

<ol>
<li>AST</li>
<li>直接执行的action</li>
</ol>


<p>输出AST其实是灵活度最大的一种形式，有了AST，那么后面是想解释执行？还是做翻译？那就交由用户去考虑了，dropincc.java的工作到这里也就结束了；<br/>
而“直接执行action”的方式适合像上面这种简单的诸如“四则运算”这样的简单表达式语言，在创建解析树的过程中就把对应的动作代码给执行了，解析结束后直接就能得到结果。</p>

<p>根据dropincc.java的后续设想，上述2种方式在dropincc.java中实现应该“几乎没有差别”，这两种输出形式虽然目的可能不一样，但在dropincc.java中实现起来应该是高度统一、一致的，这也是为了实现“足够简单”的目标，尽量不要让用户过多地去学习一些概念，增加上手成本。</p>

<p>至于dropincc.java能够用来识别哪种级别的语法？我的设想中dropincc.java是一个LL解析器生成器，最终要能识别LL(*)的语法，也就是跟antlr具有同等能力；不过初期的实现可能还识别不了那种程度的不确定性，这个可以一步一步随着版本推进慢慢来改进。其它一些诸如解决左递归的一些算法改进都可以排在计划中&#8230;</p>

<p>OK，前期的设想也就暂时介绍到这里，希望dropincc.java的努力能够将java圈子里的DSL应用甚至<a href="http://en.wikipedia.org/wiki/Language-oriented_programming">LOP</a>编程往前推进一步，这是相当令人振奋的事情。</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[Liquid Error about regexp match when using octopress-tagcloud]]></title>
    <link href="http://pfmiles.github.io/blog/liquid-error-about-regexp-match-when-using-octopress-tagcloud"/>
    <updated>2012-03-14T19:33:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/liquid-error-about-regexp-match-when-using-octopress-tagcloud</id>
    <content type="html"><![CDATA[<p>Octopress插件：<a href="https://github.com/tokkonopapa/octopress-tagcloud">octopress-tagcloud</a>相当nice，不过在使用的时候，若是blog整体采用了非ascii码的编码格式(比如utf-8)就会出现类似这样的错误：</p>

<pre><code>Liquid error: incompatible encoding regexp match (ascii-8bit regexp with utf-8 string)
</code></pre>

<p>其实是由于octopress-tagcloud的插件文件：<code>plugins/tag_cloud.rb</code>文件本身是ascii编码所致:</p>

<pre><code>$ chardet tag_cloud.rb
tag_cloud.rb: ascii (confidence: 1.00)
</code></pre>

<p><code>tag_cloud.rb</code>中很多地方用到了ruby的正则表达式，而ruby的正则表达式在匹配的时候，默认是按照“代码源文件”的编码格式(在这里是ascii)进行匹配的，而若我的blog是utf-8编码的话就会出现上述错误。</p>

<p>解决办法有二：</p>

<ol>
<li>将<code>tag_cloud.rb</code>转成utf-8&#8230;</li>
<li>更改<code>tag_cloud.rb</code>中所有的正则表达式声明，加上<code>u</code>选项(根据<a href="http://www.ruby-doc.org/core-1.9.3/Regexp.html">这里</a>的说明，<code>u</code>的意思就是以utf-8编码格式来进行匹配)，即，若原正则式是：<code>/regexp/</code>, 则改成：<code>/regexp/u</code></li>
</ol>


<!-- more -->


<p>这里是我改好的<code>tag_cloud.rb</code>：</p>

<div><script src='https://gist.github.com/2036006.js?file='></script>
<noscript><pre><code># Tag Cloud for Octopress, modified by pf_miles, for use with utf-8 encoded blogs(all regexp added 'u' option).
# =======================
# 
# Description:
# ------------
# Easy output tag cloud and category list.
# 
# Syntax:
# -------
#     {% tag_cloud [counter:true] %}
#     {% category_list [counter:true] %}
# 
# Example:
# --------
# In some template files, you can add the following markups.
# 
# ### source/_includes/custom/asides/tag_cloud.html ###
# 
#     &lt;section&gt;
#       &lt;h1&gt;Tag Cloud&lt;/h1&gt;
#         &lt;span id=&quot;tag-cloud&quot;&gt;{% tag_cloud %}&lt;/span&gt;
#     &lt;/section&gt;
# 
# ### source/_includes/custom/asides/category_list.html ###
# 
#     &lt;section&gt;
#       &lt;h1&gt;Categories&lt;/h1&gt;
#         &lt;ul id=&quot;category-list&quot;&gt;{% category_list counter:true %}&lt;/ul&gt;
#     &lt;/section&gt;
# 
# Notes:
# ------
# Be sure to insert above template files into `default_asides` array in `_config.yml`.
# And also you can define styles for 'tag-cloud' or 'category-list' in a `.scss` file.
# (ex: `sass/custom/_styles.scss`)
# 
# Licence:
# --------
# Distributed under the [MIT License][MIT].
# 
# [MIT]: http://www.opensource.org/licenses/mit-license.php
# 
module Jekyll

  class TagCloud &lt; Liquid::Tag

    def initialize(tag_name, markup, tokens)
      @opts = {}
      if markup.strip =~ /\s*counter:(\w+)/iu
        @opts['counter'] = $1
        markup = markup.strip.sub(/counter:\w+/iu,'')
      end
      super
    end

    def render(context)
      lists = {}
      max, min = 1, 1
      config = context.registers[:site].config
      category_dir = config['root'] + config['category_dir'] + '/'
      categories = context.registers[:site].categories
      categories.keys.sort_by{ |str| str.downcase }.each do |category|
        count = categories[category].count
        lists[category] = count
        max = count if count &gt; max
      end

      html = ''
      lists.each do | category, counter |
        url = category_dir + category.gsub(/_|\P{Word}/u, '-').gsub(/-{2,}/u, '-').downcase
        style = &quot;font-size: #{100 + (60 * Float(counter)/max)}%&quot;
        html &lt;&lt; &quot;&lt;a href='#{url}' style='#{style}'&gt;#{category.capitalize}&quot;
        if @opts['counter']
          html &lt;&lt; &quot;(#{categories[category].count})&quot;
        end
        html &lt;&lt; &quot;&lt;/a&gt; &quot;
      end
      html
    end
  end

  class CategoryList &lt; Liquid::Tag

    def initialize(tag_name, markup, tokens)
      @opts = {}
      if markup.strip =~ /\s*counter:(\w+)/iu
        @opts['counter'] = $1
        markup = markup.strip.sub(/counter:\w+/iu,'')
      end
      super
    end

    def render(context)
      html = &quot;&quot;
      config = context.registers[:site].config
      category_dir = config['root'] + config['category_dir'] + '/'
      categories = context.registers[:site].categories
      categories.keys.sort_by{ |str| str.downcase }.each do |category|
        url = category_dir + category.gsub(/_|\P{Word}/u, '-').gsub(/-{2,}/u, '-').downcase
        html &lt;&lt; &quot;&lt;li&gt;&lt;a href='#{url}'&gt;#{category.capitalize}&quot;
        if @opts['counter']
          html &lt;&lt; &quot; (#{categories[category].count})&quot;
        end
        html &lt;&lt; &quot;&lt;/a&gt;&lt;/li&gt;&quot;
      end
      html
    end
  end

end

Liquid::Template.register_tag('tag_cloud', Jekyll::TagCloud)
Liquid::Template.register_tag('category_list', Jekyll::CategoryList)</code></pre></noscript></div>



]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[帮表妹和姑姑攒的台式机]]></title>
    <link href="http://pfmiles.github.io/blog/pc-assembled-for-my-cousin-and-aunt"/>
    <updated>2012-03-10T20:18:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/pc-assembled-for-my-cousin-and-aunt</id>
    <content type="html"><![CDATA[<p>其实早就看好的，不过一直没仔细上淘宝询问和调查；<br/>
现在在网上买电脑其实也还不错的；<br/>
她们平时也就拿电脑来偷偷菜，看看电影，玩玩小游戏逛逛taobao，这样的电脑跑到“电脑城”一问，人家跟他说要4k+才能拿下&#8230;我说这不坑爹么？行了，网上搞一套吧，拿回来自己装，心理预期价格2k左右 —— 反正不用买显示器。<br/>
对于这些“平民级”的PC需求，我好像一直对AMD体系情有独钟，包括我自己的台式也是AMD&#8230;话说我对台式机的需求还真是平民中的平民啊，反正我又不玩什么高端的游戏:)</p>

<h3>好了， 配置列表:</h3>

<ol>
<li>AMD a6-3650, 盒装带风扇，648元(小贵哦，不过看在它4核再加上显示核心的份上还行)</li>
<li>映泰a75 MH，全固态，小板子，主要是拿来配CPU的FM1插口，不管怎么说主板作为最重要的配件可要弄好一点，模拟/数字/HDMI接口都有(445元)</li>
<li>内存威刚 2G DDR3 1333 * 2 (152元, 2根用来组成双通道的，4g他们装个32位win7应该够了吧&#8230;)</li>
<li>硬盘WD500G WD5000AAKX 16M蓝盘 SATA3 (539元！好贵啊&#8230;最近硬盘水患涨价，不过总不能不要硬盘吧&#8230;)</li>
<li>电源航嘉冷钻2.3+, 300w (199元, 这玩意儿只能装进大机箱&#8230;)</li>
<li>华硕DVDRW DRW-24D1ST, 24x/SATA (135元，姑姑说她“想刻东西”&#8230;好吧&#8230;)<br/>
<strong><em>总：2118元</em></strong><br/>
木有键鼠，木有机箱（机箱在运输过程中怕容易坏所以没买），木有显示器（暂时用旧的），OK。哦，还有运费40&#8230;</li>
</ol>


<h3>总结</h3>

<p>久了不攒机真是out了啊out，殊不知现在流行显示核心嵌到CPU里面&#8230;而且也没想到硬盘由于工厂发大水涨价涨得厉害&#8230;哎<br/>
不过电脑这东西，平民级的用途的话，啥时候想用啥时候就买就行了，没有必要等，而且买了之后就没有什么好后悔的，因为这个行业的新产品出得太快了&#8230;当然也有人等着硬盘降价、等着显卡降价的，人家那不一样，人家那是发烧友，那是高玩，人家一个显卡就几千块的&#8230;能不等等么。</p>
]]></content>
  </entry>
  
  <entry>
    <title type="html"><![CDATA[[面试中的算法]编程判断两个链表是否相交]]></title>
    <link href="http://pfmiles.github.io/blog/algorithms-in-job-interview-test-if-two-linked-lists-intersected"/>
    <updated>2012-03-06T23:30:00+08:00</updated>
    <id>http://pfmiles.github.io/blog/algorithms-in-job-interview-test-if-two-linked-lists-intersected</id>
    <content type="html"><![CDATA[<p>这是一道广为流传的题目: <a href="http://bop1.wikispaces.com/%E7%AC%AC%E4%B8%89%E7%AB%A0+%E7%BB%93%E6%9E%84%E4%B9%8B%E6%B3%95#x-%E7%AC%AC3%E7%AB%A0%20%E7%BB%93%E6%9E%84%E4%B9%8B%E6%B3%95%E2%80%94%E2%80%94%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8F%8A%E9%93%BE%E8%A1%A8%E7%9A%84%E6%8E%A2%E7%B4%A2-3.6%E7%BC%96%E7%A8%8B%E5%88%A4%E6%96%AD%E4%B8%A4%E4%B8%AA%E9%93%BE%E8%A1%A8%E6%98%AF%E5%90%A6%E7%9B%B8%E4%BA%A4">编程判断两个链表是否相交</a>;原题假设“不带环”，所以只要想通了之后很简单；但是，若要考虑带环的情况，那么要注意的点就很多了。
其实可以把无环和有环的情况全都包括在一个方法实现内解决。</p>

<h3>分析</h3>

<p>首先，无环的情况；无环是《编程之美》原书里的题目，很多人都反应说这个题相对书中其它题来讲太过于简单了。也确实，只要在纸上把“所有单向链表相交的情况”画出来很容易就能想通解法了（只要正确理解题意，那么“两个无环单向链表”画出来只可能是2条不相干的链表或一个&#8221;Y&#8221;字形） —— 所以，判断两个不带环的链表是否相交，只要将两个链表的头指针都移到链表尾，然后比较尾指针地址是否相等就可以了。
如果带环，个人总结，要明白以下几点：</p>

<ol>
<li>无环链表和有环链表是不可能相交的;</li>
<li>两个有环链表若相交，其“整个环上”的所有node一定都重合;</li>
<li>有环链表的相交，情况只有2种：相交于&#8221;环上&#8221;或相交于&#8221;不是环的部分&#8221;,即下图所示;两种情况都需要使用“两个指针的追逐”方法来判断两个链表的环部分是否相交;
<img src="http://pfmiles.github.io/images/circledLinkedListsIntersections.png" title="带环单向链表相交只有2种情况" alt="带环单向链表相交只有2种情况" /></li>
<li>有关链表追逐的考虑: 相对速度、距离、时间要算好，否则很容易漏掉几种边界情况;</li>
</ol>


<!-- more -->


<h3>代码</h3>

<pre><code>#include &lt;stdio.h&gt;

// define the node struct of links
typedef struct Node {
    struct Node* next;
} Node;

int is_intersected(Node* p1, Node* p2);

Node* has_circle(Node* head);

int main(int args, char** argv) {
    Node end1 = { NULL };
    Node end2 = { NULL };
    // 定义几种链表情况
    // two links not intersect with each other, no circle
    Node link_1_n =
            {
                    &amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;end1}}}}}}}}};
    Node link_2_n =
            {
                    &amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;end2}}}}}}}}};

    // two links intersect with each other, no circle
    Node common_n = { &amp;(Node) {&amp;(Node) {&amp;end1}}};

    Node link_1_y = { &amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;common_n}}}}}};
    Node link_2_y = { &amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;common_n}}}}}};

    // two links, has circle, not intersected.
    Node circle1 = { &amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;circle1}}}}};
    Node link_c1_n = { &amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;circle1}}}}};

    Node circle2 = { &amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;circle2}}}}};
    Node link_c2_n = { &amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;circle2}}}}};

    // two links, has circle, intersected at a non-circle position
    Node common_c = { &amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;common_c}}}}};
    Node common_part = { &amp;(Node) {&amp;common_c}};

    Node link_c1_y = { &amp;(Node) {&amp;(Node) {&amp;common_part}}};
    Node link_c2_y = { &amp;(Node) {&amp;(Node) {&amp;common_part}}};
    // two links, has common circle, but different 'joint-points'.

    Node jp1 = { NULL };
    Node jp2 = { NULL };
    // 'weave' the joint-points into a circle:
    jp1.next = &amp;(Node) {&amp;(Node) {&amp;jp2}};
    jp2.next = &amp;(Node) {&amp;jp1};

    Node link_c1_y2 = { &amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;jp1}}}}};
    Node link_c2_y2 = { &amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;(Node) {&amp;jp2}}}}};

    if (is_intersected(&amp;link_1_n, &amp;link_2_n)) {
        printf("link_1_n and link_2_n Intersected!\n");
    }

    if (is_intersected(&amp;link_1_y, &amp;link_2_y)) {
        printf("link_1_y and link_2_y Intersected!\n");
    }

    if (is_intersected(&amp;link_c1_n, &amp;link_c2_n)) {
        printf("link_c1_n and link_c2_n Intersected!\n");
    }

    if (is_intersected(&amp;link_c1_y, &amp;link_c2_y)) {
        printf("link_c1_y and link_c2_y Intersected!\n");
    }

    if (is_intersected(&amp;link_c1_y2, &amp;link_c2_y2)) {
        printf("link_c1_y2 and link_c2_y2 Intersected!\n");
    }
    return 0;
}

int is_intersected(Node* p1, Node* p2) {
    Node* has_circle_1 = has_circle(p1);
    Node* has_circle_2 = has_circle(p2);

    if (has_circle_1) {
        if (has_circle_2) {
            Node* pp1 = has_circle_1;
            Node* pp2 = has_circle_2;
            if (pp1 == pp2 || pp1-&gt;next == pp2)
                return 1;
            while (pp1-&gt;next != has_circle_1) {
                pp1 = pp1-&gt;next;
                pp2 = pp2-&gt;next-&gt;next;
                if (pp1 == pp2)
                    return 1;
            }
            return 0;
        } else {
            return 0;
        }
    } else {
        if (has_circle_2) {
            return 0;
        } else {
            while (p1-&gt;next)
                p1 = p1-&gt;next;
            while (p2-&gt;next)
                p2 = p2-&gt;next;
            return p1 == p2;
        }
    }
    return 0;
}

Node* has_circle(Node* head) {
    Node* p1;
    Node* p2;
    p1 = p2 = head;
    if (p2-&gt;next != NULL) {
        p2 = p2-&gt;next;
    } else {
        return NULL;
    }
    while (p2-&gt;next != NULL &amp;&amp; p2-&gt;next-&gt;next != NULL) {
        p1 = p1-&gt;next;
        p2 = p2-&gt;next-&gt;next;
        if (p1 == p2)
            return p1;
    }
    return NULL;
}
</code></pre>

<p>其中，<code>has_circle</code>方法是判断一个单向链表是否带环的，基本原理就是设置2个“速度”不同的链表，快的去追慢的，追上就是带环，直到较快指针遇到null还没追上就是没有环；假设环包含n个节点，指针<code>p2</code>的&#8221;速度&#8221;是2，<code>p1</code>的速度是1，相对速度就是1，从相同一点出发的话，<code>p2</code>追上<code>p1</code>至少要n步；若再假设该链表除了环的部分外还带有一个长度为k的“尾巴”，那么追上的步数最多是n+k;也就是线性时间复杂度内就能完成这个判断。</p>

<p>这提供了一种很好的判断是否&#8221;环状&#8221;的思路；以前我只写过“用一个栈来记录”的方式，弱爆了&#8230;(时间复杂度为O(n<sup>2</sup>))</p>

<p>在<code>has_circle_1</code>和<code>has_circle_2</code>都满足的时候，也就是说2个链表都带环的时候，要分别取2个环上的一点来玩“追逐游戏”来判断是否相交；在这段程序里是<code>pp1</code>和<code>pp2</code>;然后一个速度为2一个速度为1开始玩“追逐游戏”，当慢的那个走完环上所有节点时快的那个还没追上它的话，说明不相交(此时耗费时间n——即环节点数;因为快慢指针的相对速度为1，快指针理应在时间n以内追上慢链表，否则不相交)。</p>

<h3>总结</h3>

<p>单向链表的问题&#8230;着实不简单，可以相当复杂&#8230;对于这种关乎“形状”的问题，在纸上画一画会很有帮助。</p>
]]></content>
  </entry>
  
</feed>
