Hatena::Groupcoders

ラシウラ出張所 このページをアンテナに追加 RSSフィード

2007/06/06

[] A* アルゴリズム完全版  A* アルゴリズム完全版 - ラシウラ出張所 を含むブックマーク はてなブックマーク -  A* アルゴリズム完全版 - ラシウラ出張所  A* アルゴリズム完全版 - ラシウラ出張所 のブックマークコメント

コード片の全体です。Java 6でかいてます。

ただし、PointやFieldの具体型を作ると、キャストで警告が出るのがいやだったので、全部genericsに書き換えました。generic typeの配列はnew T[]すると警告が出るので、そのへんも全部List<T>に書き換えることになりました。余計なところで複雑になっている。計算機科学教育Javaを避けるようになったのもわかる気がします。

Point.java

// 位置
public interface Point {
    // 同値判定できる必要がある
    boolean equals(Object point);
    int hashCode();
}

これだけは変わってません。

Field.java

import java.util.*;

// マップ
public interface Field<TPoint extends Point> {
    // その位置に入れるかどうか
    boolean canWalkIn(TPoint point);
    // その位置に隣接する位置一覧
    List<TPoint> neighbors(TPoint point);
    // その位置の目標からのスコア。
    // パスが伸びればその合計スコアは増えるように、正の整数である
    int score(TPoint goal, TPoint point);
}

Listが入り、ジェネリクス化しました。でもまだまだ単純です。

Solver.java

import java.util.*;

public interface Solver<TPoint extends Point, TField extends Field<TPoint>> {
    List<TPoint> calc(TField map, TPoint start, TPoint goal);
}

GenericsGenericsで使うとクラスの型宣言は長くなります。<TField extends Field<TPoint extends Point>> って書きたいところだけど無理っぽい。

AStar.java

import java.util.*;

class AStar<TPoint extends Point, TField extends Field<TPoint>>
    implements Solver<TPoint, TField> {
    public List<TPoint> calc(TField map, TPoint start, TPoint goal) {
        // 再入、並行実行可能にするためインスタンス生成し、実行
        return new AStar<TPoint, TField>().solve(map, start, goal);
    }
    
    private List<TPoint> solve(TField map, TPoint start, TPoint goal) {
        this.map = map;
        this.goal = goal;
        visitedCache = new HashSet<TPoint>();
        pathes = new ArrayList<ScoredPath>();

        // 初期ポイント: (0, [start])
        visitedCache.add(start);
        ArrayList<TPoint> path = new ArrayList<TPoint>();
        path.add(start);
        ScoredPath spath = new ScoredPath(0, path);
        pathes.add(spath);

        return astar();
    }

    private List<TPoint> astar() {
        while (pathes.size() > 0) {
            // 一番スコアの低いパスを取り出し進める
            ScoredPath spath = pathes.remove(0);
            TPoint current = spath.path.get(spath.path.size() - 1);
            // ゴールに着いていたら終了
            if (current.equals(goal)) {
                return spath.path;
            }
            for (TPoint next: map.neighbors(current)) {
                // すでに通ってたらスルー
                if (visitedCache.contains(next)) continue;
                // 通ったことにする
                visitedCache.add(next);
                // 入れなければスルー
                if (!map.canWalkIn(next)) continue;
                // パスに追加し、そのパスのスコアを計算
                ArrayList<TPoint> path = new ArrayList<TPoint>(spath.path);
                path.add(next);
                int score = spath.score + map.score(goal, next);
                // スコア順になるよう、この新たなパスを挿入
                insert(score, path);
            }
        }
        // もう行ける場所がなく、到達不能。
        return null;
    }

    private void insert(int score, ArrayList<TPoint> path) {
        for (int i = 0; i < pathes.size(); i += 1) {
            ScoredPath spath = pathes.get(i);
            if (spath.score >= score) {
                pathes.add(i, new ScoredPath(score, path));
                return;
            }
        }
        pathes.add(new ScoredPath(score, path));
    }
    private TField map;
    private TPoint goal;
    private ArrayList<ScoredPath> pathes;
    private Set<TPoint> visitedCache;

    private class ScoredPath {
        ScoredPath(int score, ArrayList<TPoint> path) {
            this.score = score;
            this.path = path;
        }
        int score;
        ArrayList<TPoint> path;
    }
}

手続きメインなので、ほとんど変わらないけど、privateとか入れたので、地味にめんどくさくなってます。結局、警告の出ないtoArrayの使い方がわからなかったのでList化したのです。

以下は2DでのPointやFieldの実装です。

Point2D.java

座標としてxとyを持った単純なポイントです。

public class Point2D implements Point {
    public Point2D(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public boolean equals(Object o) {
        if (o instanceof Point2D) {
            Point2D p = (Point2D) o;
            return p.x == x && p.y == y;
        }
        return false;
    }
    public int hashCode() {
        return x + y;
    }
    public int x() { return x;}
    public int y() { return y;}
    private int x;
    private int y;
}

情報隠蔽はきちっとしておきました。

equalsのなかでキャストを使ってますが、この場合は警告は出ないようです。

Field2D.java

有限マップです。A*自体はスコアリングがしっかりしてれば無限境界のマップでもいけるはずですが、今回は表示の簡略化(回り込まれると面倒なので)と、壁を省略するため、境界壁の構造にしてます。

import java.util.*;

public class Field2D implements Field<Point2D> {
    public Field2D(String[] data, int width) {
        this.data = data.clone();
        this.width = width;
        this.height = data.length / width;
    }

    public boolean canWalkIn(Point2D point) {
        if (0 <= point.x() && point.x() < width &&
            0 <= point.y() && point.y() < height &&
            " ".equals(get(data, point))) return true;
        return false;
    }

    public List<Point2D> neighbors(Point2D point) {
        List<Point2D> result = new ArrayList<Point2D>(4);
        result.add(new Point2D(point.x() - 1, point.y()));
        result.add(new Point2D(point.x() + 1, point.y()));
        result.add(new Point2D(point.x(), point.y() - 1));
        result.add(new Point2D(point.x(), point.y() + 1));
        return result;
    }

    public int score(Point2D goal, Point2D point) {
        return Math.abs(point.x() - goal.x()) +
            Math.abs(point.y() - goal.y());
    }
    
    public Field2D walk(List<Point2D> path) {
        String[] newData = data.clone();
        for (Point2D point: path) {
            set(newData, point, "*");
        }
        return new Field2D(newData, width);
    }

    public void print() {
        printWall();
        for (int y = 0; y < height; y += 1) {
            System.out.print("#");
            for (int x = 0; x < width; x += 1) {
                Point2D point = new Point2D(x, y);
                System.out.print(get(data, point));
            }
            System.out.println("#");
        }
        printWall();
    }

    private void printWall() {
        for (int x = 0; x < width + 2; x += 1) {
            System.out.print("#");
        }
        System.out.println();
    }

    private void set(String[] data, Point2D point, String value) {
        data[point.y() * width + point.x()] = value;
    }

    private String get(String[] data, Point2D point) {
        return data[point.y() * width + point.x()];
    }

    private String[] data;
    private int width;
    private int height;
}

スコアはgoalからの絶対距離です。壁は無視します。

それ以降はユーティリティです。walkはパスをたどって、マークをつけたマップを返します。printマップを壁付きで標準出力に出します。

cloneで代入してもキャストが不要なのはちょっとだけいいかもしれません。

Main.java

例題実行します。

import java.util.*;

class Main {
    public static void main(String[] args) {
        String[] mapData = new String[] {
            " ", " ", " ", " ", " ",
            " ", " ", " ", " ", " ",
            "#", "#", "#", "#", " ",
            " ", " ", " ", " ", " ",
            "#", "#", " ", "#", "#",
            " ", "#", " ", " ", " ",
            " ", "#", "#", " ", " ",
            " ", " ", " ", " ", " ",
            " ", " ", " ", " ", " ",
        };
        int width = 5;
        Field2D map = new Field2D(mapData, width);
        System.out.println("[source map]");
        map.print();

        Point2D start = new Point2D(1, 1);
        Point2D goal = new Point2D(0, 5);

        AStar<Point2D, Field2D> astar = new AStar<Point2D, Field2D>();
        List<Point2D> path = astar.calc(map, start, goal);
        Field2D walked = map.walk(path);

        System.out.println("[result map]");
        walked.print();
    }
}

実行結果

$ java Main
[source map]
#######
#     #
#     #
##### #
#     #
### ###
# #   #
# ##  #
#     #
#     #
#######
[result map]
#######
#     #
# ****#
#####*#
#  ***#
###*###
#*#** #
#*##* #
#**** #
#     #
#######

2007/05/19

[] 左結合な中置演算子の作り方  左結合な中置演算子の作り方 - ラシウラ出張所 を含むブックマーク はてなブックマーク -  左結合な中置演算子の作り方 - ラシウラ出張所  左結合な中置演算子の作り方 - ラシウラ出張所 のブックマークコメント

より、無駄を減らして

class infix:
    def __init__(self, func):
        self.func = func
        pass
    def __call__(self, left, right):
        return self.func(left, right)
    def __ror__(self, left):
        return boundleft(lambda right: self.func(left, right))
    pass

class boundleft:
    def __init__(self, func):
        self.func = func
        pass
    def __call__(self, right):
        return self.func(right)
    def __or__(self, right):
        return self.func(right)
    pass

Python-2.5では使い方は以下のようになる。infixが使えるのは二引数で呼び出しできるものでなくてはいけない:

@infix
def mul(a, b):
    return a * b

@infix
def add(a, b):
    return a + b

print 2 |add| 3 |mul| 4 #=> (2 + 3) * 4 = 20

結果から左結合の二項演算子になっていることを確認できる。

旧来の使い方も可能

isa = infix(lambda a, b: a.__class__ == b.__class__)

print [1,2,3] |isa| [] #=> True

右結合は?

Pythonの右結合演算子は、代入関係と**だけになる。まず、代入演算はa += b += cのような連続はパーズエラーになるため、使えない。

唯一**が__pow__や__rpow__で上書きできる。ただし、それを有効にするためにはinstance型は、__coerce__で引数側の型を変換しなくてはいけない。

class infixr:
    def __init__(self, func):
        self.func = func
        pass
    def __call__(self, left, right):
        return self.func(left, right)
    def __pow__(self, right):
        return boundright(lambda left: self.func(left, right.obj))
    def __coerce__(self, other):
        return (self, wrap(other))
    pass

class wrap:
    def __init__(self, obj):
        self.obj = obj

class boundright:
    def __init__(self, func):
        self.func = func
        pass
    def __call__(self, left):
        return self.func(left)
    def __rpow__(self, left):
        return self.func(left.obj)
    def __coerce__(self, other):
        return (self, wrap(other))
    pass

使い方例

@infixr
def comp(f, g):
    return lambda a: f(g(a))

add2 = lambda a : a + 2
mul3 = lambda a : a * 3
add4 = lambda a : a + 4

print (add4 **comp**  mul3 **comp** add2)(1) #=> (1 +2) *3) +4 = 13

実際のところ、右結合演算子が必要な状況はほとんどない。代入、pow演算子、(Rubyのように括弧のいらない)関数適用くらいだが、それは組み込まれている。関数型言語だと、例でも使った関数合成は右結合になる。 foo.bar.buzz はfoo.(bar.buzz)である。関数適用ではfoo (bar (buzz x)))であってほしいからだ。これはpythonにもほしくなるかもしれない。

あと(遅延型)関数型言語リストの結合も右結合になる。これはリスト[a,b,c,...]が意味的に(a,(b,(c,(...,()...))))のように、(","を中置演算子としてみれば)右結合になっているからだろうか。っと思ったが、このリストPythonでいうところのgenerator/iteratorであるため、右結合が自然なのだろう。右結合のappend(alist, append(blist, append(clist, dlist))))は、自然に頭のリストをたどってそれが尽きたら次のappendに入れる。一方、左結合のappend(append(append(append(alist, blist), clist), dlist)は先頭の要素を取り出すにも一番奥のappendにいかなくてはいかなくなる。

pythonリストは左結合の+を使って連結するが、右左どちらでもかまわない。

2007/05/11

[][] 関数の不動点  関数の不動点 - ラシウラ出張所 を含むブックマーク はてなブックマーク -  関数の不動点 - ラシウラ出張所  関数の不動点 - ラシウラ出張所 のブックマークコメント

OCaml:

type ('a, 'b) wrappedFun = Wrap of (('a, 'b) wrappedFun -> ('a -> 'b))

let fixpoint = fun funDef ->
  let unwrap = function Wrap(func) -> func in
  let genFunc = fun wrapped -> funDef (fun n -> (unwrap wrapped) wrapped n) in
  let wrapped = Wrap(genFunc) in
  genFunc wrapped

(* example *)
let factorial = fixpoint (fun fact n -> if n = 0 then 1 else n * fact (n - 1))

open Printf;;
printf "%d\n" (factorial 5)

Haskell:

fix f = f (fix f)

fact = fix $ \fn n -> if n < 1 then 1 else n * fn (n - 1)

main = do
    putStrLn $ show (fact 5)
    return ()

上のMLのようにhaskellで書くとghcでコンパイルがとまらなくなりました。

data Wrap a = Wrap ((Wrap a) -> a)

-- cannot compile, compiler infinit loop
fix f = genfunc wrapped
    where
      unwrap (Wrap g) = g
      genfunc wrapped = f ((unwrap wrapped) wrapped)
      wrapped = Wrap genfunc

fact = fix (\fact -> (\n -> if n == 0 then 1 else n * (fact (n - 1))))
main = putStrLn $ show (fact 10)

[] UTF8でLaTeX(pLaTeX)を使う方法  UTF8でLaTeX(pLaTeX)を使う方法 - ラシウラ出張所 を含むブックマーク はてなブックマーク -  UTF8でLaTeX(pLaTeX)を使う方法 - ラシウラ出張所  UTF8でLaTeX(pLaTeX)を使う方法 - ラシウラ出張所 のブックマークコメント

(追記: platexをやめてxelatexを使おう - ラシウラplatexではなくxelatexを使うやり方を書きました)

いまさらSJISとかEUC-JPとかISO-2022-JPとか使う時代じゃないってことで。

\documentclass[a4j]{jarticle}
\usepackage{url}

\title{UTF8で \LaTeX を使う方法}
\author{bellbind}


\begin{document}
\sffamily
\maketitle

\begin{abstract}
UTF-8でp\LaTeX を処理する方法。
\end{abstract}

\section{環境}

最近の p\LaTeX が入っているならたぶん大丈夫。

debianの場合は、debパッケージのptexがUTF-8に対応していません。
ptetex3
\footnote{\url{http://www.nn.iij4u.or.jp/~tutimura/tex/ptetex.html}}
をローカルにでも入れて使いましょう。
ptetexにも付いてきますが、dvipdfmxはdebパッケージのものでもUTF8に対応できています。

例:
\begin{itemize}
\item TeXインストーラー
\footnote{\url{http://www.ms.u-tokyo.ac.jp/~abenori/mycreate/index.html}}
からWindows上にインストール
\end{itemize}

\section{\TeX ソース}

ふつうの p\LaTeX のソースと同様に記述する。
ただし、ファイルのエンコーディングはutf8にする。
\begin{itemize}
\item xyzzy \footnote{\url{http://www.jsdlab.co.jp/~kamei/}} なら "utf8n"
\end{itemize}

\section{コマンドライン}

コンパイル時に {\tt --kanji=utf8} オプションをつけるだけ。

Windowsの場合:
\begin{verbatim}
$ platex --kanji=utf8 test.tex
$ dvipdfm test.pdf
\end{verbatim}

debianの場合:
\begin{verbatim}
$ platex --kanji=utf8 test.tex
$ dvipdfmx test.pdf
\end{verbatim}


\end{document}

↑をtest.texという名前のファイルにUTF8Nで保存して上記コマンドでビルドできます。

オプション--kanji=utf8はaliasしてもいいくらい

alias platex='platex --kanji=utf8'

ptetex3のdebianへのインストール

サイトの説明どおりに行けば普通にビルド&インストールできます。

自分の場合、~/util/ptetexに入れてます。


問題になるのはmy_optionと必要なパッケージでしょうか。

ビルドに必要なdebパッケージ

このあたりがあらかじめ入れてあればビルド可能です。

まず、指定してある3つのアーカイブをひとつのディレクトリ内にダウンロードします。ptetexアーカイブだけ展開し、ディレクトリを移動します。

my_optionはmy_option.sampleからコピーし作り、一部コメントアウトをはずしていく

  • KANJI_CODE=UTF8
  • XDVI=echo
  • PXDVI=echo
  • PREFIX=/home/bellbind/util/ptetex

$PREFIX/bin/platexになります。

makeはotf、babel含めすべて行うといいです。

で最後はmake install。~/util/ptetex/binにPATHを通して、alias platex='platexr--kanji=utf8'して終わり

2007/04/20

[][] tracのPluginの書き方  tracのPluginの書き方 - ラシウラ出張所 を含むブックマーク はてなブックマーク -  tracのPluginの書き方 - ラシウラ出張所  tracのPluginの書き方 - ラシウラ出張所 のブックマークコメント

tracは0.9以降、pluginシステムを持つようになりました。pluginをつくり組み込むことで、機能拡張だけでなく、システムの振る舞いを変更するようなことまでできるようになります。

tracの外部リンクを変えるようにしたい機会があったので、それができるような簡単なpluginを作りました。tracサイトを作るとき適用したpluginがあるコミュニティTrac Hacksに登録しておきました:

このExtLLinkRewriterPluginを例にします。

setuptoolsによるeggパッケージ形式

tracではsetuptoolsを使ったeggパッケージでpluginを管理します。

setuptoolsは、.NETのアセンブリ、もしくはJavajarファイルバージョン管理をつけたもの、らと同じ位置づけにあるツールライブラリです。パッケージ作成は、Python標準のdistutilsと同様、setup.pyを使うようになっています。実際distutils用のsetup.pyのほとんどは、importするモジュールをsetuptoolsに変えるだけで使えるようになります。

setuptools用のsetup.pyはbdist_eggというコマンドを提供しeggパッケージを作成できます。作成されるeggパッケージは、PKZIP形式で、中にはメタデータ情報ファイルと対象のPythonコードが入っています(このあたりはjarに似ています)。これはunzipで確認できます。

trac pluginとextension point

tracはextension pointで機能のフックを管理できるようになっており、pluginは主にextension pointに対して機能を提供していくことになります。

たとえば、ExtLinkRewriterPluginでは、trac.wiki.api.IWikiSyntaxProviderを提供しています。

ExtLinkRewriterPluginの構成

READMEやサンプルredirectorを除くと、以下の構成です:

  • setup.py
  • ExtLinkRewriter/__init__.py
  • ExtLinkRewriter/provider.py

このうち__init__.pyはExtLinkRewriterモジュール用で、中は空です。

ExtLinkRewriter/provider.pyにはExtLinkRewriter.provider.ExtLinkRewriterProviderクラスがあり、それが前述のIWikiSyntaxProvider extension pointにむけた機能を実装しています。

setup.pyにはtrac pluginのためのメタデータを設定しています。

setup.py

from setuptools import setup

setup(
    name="ExtLinkRewriter",
    version="0.4",
    packages=['ExtLinkRewriter'],
    entry_points = {'trac.plugins':
                    ['ExtLinkRewriter.provider = ExtLinkRewriter.provider',],},
    license = "BSD")

ほぼdistutilsのsetup.pyと同じです

[trac.plugins]
ExtLinkRewriter.provider = ExtLinkRewriter.provider

trac.pluginカテゴリに、左辺はプラグインID、右辺は後述するComponentのサブクラスを取り出せるモジュール名を書くようです。

ExtLinkRewriter/provider.py

このモジュールでは、Extension point機能を提供するクラス記述します。このクラスtrac.core.Componentのサブクラスである必要があります。


from trac.core import *
from trac.wiki import IWikiSyntaxProvider
from trac.util.html import html


class ExtLinkRewriterProvider(Component):
    """Rewrite External Link URL
    """
    implements(IWikiSyntaxProvider)

    _rewrite_format = "http://del.icio.us/url?url=%s"
    _rewrite_namespaces = "http,https,ftp"
    _rewrite_target = ""

    def get_wiki_syntax(self):
        """IWikiSyntaxProvider#get_wiki_syntax
        """
        return []

    def get_link_resolvers(self):
        """IWikiSyntaxProvider#get_link_resolvers
        """
        self._load_config()
        return [(ns.strip(), self._link_formatter)
                for ns in self._rewrite_namespaces.split(",")]

    def _link_formatter(self, formatter, ns, target, label):
        try:
            newtarget = self._rewrite_format % (ns + ":" + target,)
        except:
            newtarget = ns + ":" + target
            msg = "ExtLinkRewriter Plugin format error: %s"
            msg %= (self._rewrite_format,)
            self.log.error(msg)
            pass
        return self._make_ext_link(formatter, newtarget, label,
                                   self._rewrite_target)

    def _make_ext_link(self, formatter, url, text, target=""):
        """Formatter._make_ext_link with target attr
        """
        if not url.startswith(formatter._local):
            return html.A(html.SPAN(text, class_="icon"),
                          class_="ext-link", href=url, target=target or None)
        else:
            return html.A(text, href=url, target=target or None)
        pass

    def _load_config(self):
        self._update_config("format")
        self._update_config("namespaces")
        self._update_config("target")
        pass

    def _update_config(self, key):
        attrname = "_rewrite_" + key
        oldval = getattr(self, attrname)
        newval = self.config.get("extlinkrewriter", key, oldval)
        setattr(self, attrname, newval)
        pass
    pass
implements(IWikiSyntaxProvider)

implements()関数引数はExtension pointのクラスを列挙します。それによって、システムが対応するextension pointを使うときに、このコンポーネントを使ってくれるようになります。

IWikiSyntaxProviderは以下のメソッドを提供しなくてはいけません

  • get_wiki_syntax(): 今回は何もしない
  • get_link_resolvers(): 今回のメイン機能

以下のソースにはそれらメソッドの説明が書いてあります(IWikiSyntaxProviderは96行目くらい)

get_link_resolvers

このメソッドの仕様は、

    def get_link_resolvers():
         """Return an iterable over (namespace, formatter) tuples.
 
         Each formatter should be a function of the form
         fmt(formatter, ns, target, label), and should
         return some HTML fragment.
         The `label` is already HTML escaped, whereas the `target` is not.
         """

返すのは[(namespace,formatter),...](もしくはgenerator)であり、formatterは、formatter(formatter, namespace, target, label)という引数関数になります。

    def get_link_resolvers(self):
        """IWikiSyntaxProvider#get_link_resolvers
        """
        self._load_config()
        return [(ns.strip(), self._link_formatter)
                for ns in self._rewrite_namespaces.split(",")]

で、最初のself._load_config()は、trac.iniのデータを取り込む。うしろは、pluginで処理するnamespace(http,https,ftpなど)とフォーマッターself._rewrite_namespaceのペアのタプルを返しています。

_link_formatter, _make_ext_link

これはプライベートメソッドです。

このフォーマッタはリンクに関する情報を受け取り、処理した結果であるHTML文字列を返すメソッドです。

    def _link_formatter(self, formatter, ns, target, label):
        try:
            newtarget = self._rewrite_format % (ns + ":" + target,)
        except:
            newtarget = ns + ":" + target
            msg = "ExtLinkRewriter Plugin format error: %s"
            msg %= (self._rewrite_format,)
            self.log.error(msg)
            pass
        return self._make_ext_link(formatter, newtarget, label,
                                   self._rewrite_target)

    def _make_ext_link(self, formatter, url, text, target=""):
        """Formatter._make_ext_link with target attr
        """
        if not url.startswith(formatter._local):
            return html.A(html.SPAN(text, class_="icon"),
                          class_="ext-link", href=url, target=target or None)
        else:
            return html.A(text, href=url, target=target or None)
        pass

この中でURL書き換えと、リンク部分だけのHTML生成を行っています。

HTMLレンダリング部分は、Trac標準のFormatterを参考にしています:

_load_config, _update_config

これもプライベートメソッドです。

trac.iniの情報を読み込んで、メンバーフィールドの上書きしていっています。

self.configはComponentのフィールドで、getメソッド等で、trac.iniから文字列やその他形式でデータを取り出すことができます。

たとえば、

self.config.get("extlinkrewriter", "format", "")

trac.iniの

[extlinkrewriter]
format = ...

の右辺を文字列として(strip()された状態で)取り出します(項目がない場合は第三引数の値が渡されます)。

ちなみにiniの右辺をダブルクオートでくくったりすると、ダブルクオート入りのstringが入りますので注意します。

パッケージ化とインストール

ソースが出来上がったらsetup.pyを使ってeggパッケージを作成します。

python setup.py bdist_egg

すると、dist/ExtLinkRewriter-0.4-py2.5.eggのような形式でeggパッケージが作られます。

tracで使うにはこのeggファイルをtrachomeのpluginsディレクトリコピーします。

プラグイン有効化

実際にプラグインを使うにはtrac.iniのcomponentsカテゴリモジュールをenableにするような記述をする必要があります

[components]
ExtLinkRewriter.* = enabled

つぎにtracアクセスしたら、pluginが有効になっているはずです(mod_pythonだと再起動が必要かも)。

まとめ

ExtLinkRewriterは単純なプラグインですが、plugin開発で何をすればいいかを一通りたどっています。

あとExtLinkRewriterの詳細な仕様は、以下のページに書いてあります。

リソース

2007/04/18

[] RSpecことはじめ  RSpecことはじめ - ラシウラ出張所 を含むブックマーク はてなブックマーク -  RSpecことはじめ - ラシウラ出張所  RSpecことはじめ - ラシウラ出張所 のブックマークコメント

(記述を1.0.0対応しました)

RSpecRubyでBehaviour Driven Development(BDD)を行うための環境

BDDとは、Test Driven Developmentの発展形というか、より新機能開発に特化したもの。

Testは(assert_equalsのように)ふつう条件を満たすという視点で記述を行なうが、BDD仕様を宣言し、それはこうこうあるべき(should)という視点で記述する、という違いになります。

インストール

gemから

gem install rspec

rspecを入れると、binにspecというコマンドが追加されます。

RSpecことはじめ

Ruby組み込みクラスArrayを使ってspecを書いてみます。

ArraySpec.rb

describe "An Array" do
  before do
    @array = []
  end
  it "shoud be empty" do
    @array.should be_empty
  end
  it "shoud append at last when send #<<" do
    @array << "0"
    a = "a"
    @array << a
    @array.last.should equal(a)
  end
end

describeではArrayといった仕様対象のオブジェクトを書き、itでは仕様記述します。(0.8.2のころはdescribe/itcontext/specifyでしたが、deprecatedになりました)。

beforeで、コンテキスト対象のオブジェクトフィールド初期化するブロックをおきます(以前はsetupでしたが、beforeが基本になりました)。itごとに行うbefore(:each)describeごとに行うbefore(:all)があります。

仕様は二つ書きました。

  • 何もしないとき空
  • <<で送ったものは最後にある

最初の仕様の中身

    @array.should be_empty

shouldRSpecのコアクラス拡張で受け付けるようになったメソッドです。be_emptyはこのdoの実行オブジェクトが受け付けるメソッドで、shouldと連携しているようです。@array.empty?trueであることをチェックするものになります(block中のこのメソッドの使い方はとても面白い)。


以前は、

    @array.should_be_empty

と書けたのですが、0.9以降ではこの記法は受け付けなくなりました。

(Spec::Expectationsの)メソッドはshouldshould_notだけになりました。


二つ目の仕様

    @array.last.should equal(a)

    @array.last.should_equal a

でも0.8.2時代はいけたのですが、これらも同様に受け付けなくなりました。

実行したら以下のように失敗なく終わるでしょう

$ spec ArraySpec.rb

..

Finished in 0.002134 seconds

2 specifications, 0 failures

should ~のありか

shouldで受け付けるものの解説ドキュメント

ですが、ここにはshouldshould_notだけになりました。

~の仕様Spec::Matchersにあるものになります:

複数のコンテキストは分割する

先ほどのspecでは、ひとつのdescribeの中にbeforeで空のインスタンス作成、emptyの仕様記述、appendの仕様記述が入っていました。

もし、中の入ったArrayインスタンスの場合どうなるでしょうか。emptyの仕様は別のもの。appendの仕様記述は同じものになります。

このような状況で仕様を書くには、インスタンス化して入力条件を作る部分と、アクションと事後条件チェックする部分を分割し、組み合わせるのが理知的です。RSpecでは以下のようにdescribeの分割、組み合わせが可能です。

require "array_ext"

# 振る舞い、事後条件の記述
describe "empty array", :shared => true do
  it do
    @array.should be_empty
  end
end

describe "array", :shared => true do
  it "shoud append at last when send #<<" do
    a = "a"
    @array << a
    @array.last.should equal(a)
  end
end

# コンテキスト、事前条件の記述と、事後条件の組み合わせ
describe Array, "empty" do
  before(:each) do
    @array = []
  end

  it_should_behave_like "empty array"
  it_should_behave_like "array"
end

describe Array, "has items" do
  before(:each) do
    @array = [2,3,4]
  end

  it_should_behave_like "array"
end

事後条件セット側は、describeで、shared => :trueをし、事前条件用意側で、it_should_behave_like 「事後条件セット名」を呼ぶ必要があります。

また、itに名前を渡さない場合は、処理内容から自動生成されます。前記の場合、"should be empty"になるでしょう。

実行すると:

$ RUBYLIB=$RUBYLIB:lib/ spec ArraySpec.rb
...

Finished in 0.009816 seconds

3 examples, 0 failures

specチェックもひとつ増えました。

BDDしてみる

前述のArrayのついでに右から走査していくfoldrArrayのメソッドとして作ってみましょう。

require "array_ext"

# 振る舞い、事後条件の記述
describe "empty array", :shared => true do
  it do
    @array.should be_empty
  end
end

describe "array", :shared => true do
  it "shoud append at last when send #<<" do
    @array << "0"
    a = "a"
    @array << a
    @array.last.should equal(a)
  end
  it "should be iterate from last when send #foldr" do
    @array.foldr(@to_list_init, &@to_list_block).should == @to_list_result
  end
end

# コンテキスト、事前条件の記述と、事後条件の組み合わせ
describe Array, "empty" do
  before(:each) do
    @array = []
    @to_list_init = "nil"
    @to_list_block = proc do
      |a, b|
      "[" + a.to_s + "," + b + "]"
    end
    @to_list_result = "nil"
  end

  it_should_behave_like "empty array"
  it_should_behave_like "array"
end

describe Array, "has items" do
  before(:each) do
    @array = [2,3,4]
    @to_list_init = "nil"
    @to_list_block = proc do
      |a, b|
      "[" + a.to_s + "," + b + "]"
    end
    @to_list_result = "[2,[3,[4,nil]]]"
  end

  it_should_behave_like "array"
end

specでは[1,2,3,4].foldr("nil"){|l,r| "[" + l.to_s + "," + r + "]"}が期待する文字列"[2,[3,[4,nil]"になるべきだと書くことをします。

まず、@arrayだけでなく、foldr引数二つと結果もコンテキストで変わります。そのため、まず振る舞い側でそれらをすべてフィールドで渡すよう記述します。そして、コンテキスト側でbeforeでその値を用意します。

そしてとりあえず、lib/array_ext.rbを空にしてつくり、このままspec実行します

$ RUBYLIB=$RUBYLIB:lib/ spec ArraySpec.rb
..F.F

1)
NoMethodError in 'Array empty should be iterate from last when send #foldr'
undefined method `foldr' for []:Array
./ArraySpec.rb:17:

2)
NoMethodError in 'Array has items should be iterate from last when send #foldr'
undefined method `foldr' for [2, 3, 4]:Array
./ArraySpec.rb:17:

Finished in 0.011838 seconds

5 examples, 2 failures

foldrがないと言われています。で、array_ext.rbを以下のように書きます。

class Array
  def foldr(v, &block)
    v
  end
end

んで実行します。

$ RUBYLIB=$RUBYLIB:lib/ spec ArraySpec.rb
....F

1)
'Array has items should be iterate from last when send #foldr' FAILED
expected "[2,[3,[4,nil]]]", got "nil" (using ==)
./ArraySpec.rb:17:

Finished in 0.011083 seconds

5 examples, 1 failure

こんどは期待値と違うといわれます。

で、正しい動くコードをいれましょう。

class Array
  def foldr(v, &block)
    return v if empty?
    block.call(self[0], self[1..size].foldr(v, &block))
  end
end

で、実行すると

$ RUBYLIB=$RUBYLIB:lib/ spec ArraySpec.rb
.....

Finished in 0.011391 seconds

5 examples, 0 failures

と、成功しました。

次はfoldrメソッドをリファクタリングして、このままのspec実行して通ることもチェックすることを確認します。

class Array
  def rest
    if empty? then [] else self[1..size] end
  end
  def foldr(v, &block)
    return v if empty?
    block.call(first, rest.foldr(v, &block))
  end
  def foldl(v, &block)
    return v if empty?
    rest.foldl(block.call(v, first), &block)
  end
end

mockを使う

@to_list~というフィールドが3つできましたが、Mockオブジェクトを使えば以下のようにひとつにまとめられます。

  it "should be iterate from last when send #foldr" do
    @array.foldr(@to_list.init) do |a, b|
      @to_list.block(a, b)
    end.should == @to_list.result
  end

mockは以下の@to_listのように作ります。

describe Array, "empty" do
  before(:each) do
    @array = []
    @to_list = mock("to_list")
    @to_list.should_receive(:init).any_number_of_times.and_return("nil")
    @to_list.should_receive(:block).any_number_of_times do |a, b|
      "[" + a.to_s + "," + b + "]"
    end
    @to_list.should_receive(:result).any_number_of_times.and_return("nil")
  end

  it_should_behave_like "empty array"
  it_should_behave_like "array"
end

describe Array, "has items" do
  before(:each) do
    @array = [2,3,4]
    @to_list = mock("to_list")
    @to_list.should_receive(:init).any_number_of_times.and_return("nil")
    @to_list.should_receive(:block).any_number_of_times do |a, b|
      "[" + a.to_s + "," + b + "]"
    end
    @to_list.should_receive(:result).any_number_of_times.and_return("[2,[3,[4,nil]]]")
  end

  it_should_behave_like "array"
end

mockメソッドで名前指定でオブジェクトを作成します。mockはshould_receiveメッセージ名を指定し、呼び出され回数any_number_of_times(任意回)を指定し、戻り値を指定しています。呼び出され任意回にしたのは、emptyなどでもmockの実行回数チェックが起きてしまうからです。

同様のもので呼び出され回数をチェックしないものとしてstubもあるのですが、こちらはキーと値のペアだけになります(引数を受け付けるメッセージは作れない)。

mockの配置

入力は共通化されることから、mockは、振る舞い側で定義し、結果だけインスタンス側で定義するのがいいでしょう。

  it "should be iterate from last when send #foldr" do
    to_list = mock("to_list")
    to_list.should_receive(:block).exactly(@to_list_call).times do |a, b|
      "[" + a.to_s + "," + b + "]"
    end
    @array.foldr("nil") do |a, b|
      to_list.block(a, b)
    end.should == @to_list_result
  end

こうすることで、exactlyによって、チェックで使う実行回数を設定します。

実行回数、結果は、コンテキスト側に書きます。

describe Array, "empty" do
  before(:each) do
    @array = []
    @to_list_call = 0
    @to_list_result = "nil"
  end

  it_should_behave_like "empty array"
  it_should_behave_like "array"
end

describe Array, "has items" do
  before(:each) do
    @array = [2,3,4]
    @to_list_call = 3
    @to_list_result = "[2,[3,[4,nil]]]"
  end

  it_should_behave_like "array"
end

mockチェック要素を生成的に導く

@to_list_call@array.sizeそのものであり、@to_list_result@arrayの要素のループから生成できる。そこで、これらをitの側にうつしてやる。

require "array_ext"

describe "empty array", :shared => true do
  it do
    @array.should be_empty
  end
end

describe "array", :shared => true do
  it "shoud append at last when send #<<" do
    @array << "0"
    a = "a"
    @array << a
    @array.last.should equal(a)
  end
  it "should be iterate from last when send #foldr" do
    item_proc = proc do |a, b|
      "[" + a.to_s + "," + b + "]"
    end
    to_list = mock("to_list")
    to_list.should_receive(:block).exactly(@array.size).times(&item_proc)
    init = "nil"
    result = init
    @array.reverse.each do |item|
      result = item_proc.call(item, result)
    end

    #action
    @array.foldr(init) do |a, b|
      to_list.block(a, b)
    end.should == result
  end
end

describe Array, "empty" do
  before(:each) do
    @array = []
  end

  it_should_behave_like "empty array"
  it_should_behave_like "array"
end

describe Array, "has items" do
  before(:each) do
    @array = [2,3,4]
  end

  it_should_behave_like "array"
end

これはテストとその対象が近くにおける反面、チェックする結果の要素が直接的でなくなる。ただ、BDDは実装前に必ずspecチェックするので、結果的に失敗メッセージの中に結果値が埋め込まれるので、それでチェックできなくもない。

ただし、処理と結果導出があまりにもそっくりな場合、コード変更が同時影響すると、チェックは効かなくなるという面には注意したい。例ではfoldr自体もreverseを使って実装されていると、reverseが狂っている場合は、このspecチェックは多分通ってしまう。つまり、使用するメソッドは何らかの形で直接的なspecが入ってないといけないということになる。

rakeでspec実行するためのRakefile

rspecrake用taskを生成するライブラリも含んでいます。

たとえば、lib/以下においたライブラリ開発用のspecがspec/以下にある場合、そのspecを実行するtask runspecは以下のようにRakefileに書けばよいです。

begin
  gem "rspec"
  require 'spec/rake/spectask'
  desc "Run all specs"
  Spec::Rake::SpecTask.new('runspecs') do |t|
    t.libs << "lib"
    t.spec_files = FileList['spec/**/*.rb']
  end
ensure
end

rspecが入ってる環境なら

rake runspecs

で実行されます。

感想

BDD自体は、普通テストでも書き方を注意すればできることですが、このようにDSL風にすることでいろいろ機能を埋め込めるし、みやすいかもしれないです。

個人的に面白かったのは should be_emptyのようなDSL風メソッドの使い方でした。ブロックを使うことで、仕様に文字列を使えるのもいいです(そのかわりreturnが使えなくなるが)。

rspec自体についていえば、specコマンドruby同様の-Iオプションが使えればいいのにと思いました。bin/specを直接起動ではなく、rubyコマンドに食わせればいいのですが、それもださいし。

名前汚染の注意が必要

rspec-0.8.2では、specの中でグローバル変数classを定義すると、spec実行を同時に行うすべてのspecでそれらの名前が共有されるようです。

将来改善させるとは思いますが、現状spec中でそれらを行う場合は注意が必要です。