移転しました

別に新年だからという訳でもないですがはてなブログの方に移転しました．ついでになんとなくアカウント名も一新.
こちらの記事はそのまま残しておきます．

http://mmi.hatenablog.com/

PyQt5でさくっとGUIを作る

普段GUIを作成する場合はC++withQtで作成してます．実のところQtを使えば簡単にGUIが作成できるんですが，わざわざQtプロジェクトを作るのもあれだなーという時
にPython用のQtバインディングであるPyQt5を使うともっとお手軽にできるのではないかと思って試してみました．（ちなみに，PyQt5は全然ドキュメントがないです．）

最初に一つ言っておくと，Python用のQtバインディングは2種類あって，1つがPyQt，もう一つがPySideです．PySideの方はQt開発元のNokiaがサポートしてます．今回PyQtを利用した理由としたのは2014/11/12現在Qt5をサポートしているのはPyQtのみだったからです．（Python3は両方サポートしてます）．重要な点ですが，PyQt5のライセンスはGPLもしくは商用ライセンスです（Qt自体はLGPLもしくは商用ライセンス）．PyQt4では，GPLに例外事項が設けられていて，PyQt4を用いて作成したスクリプトだけであればMITやBSDライセンスで配布することが許可されていましたが，どうやらPyQt5ではこの例外事項が削除されたようです．PySideの方はLGPLで利用できます．機能的にPyQtとPySideでそれほど大きな差はないようですが，特にシグナルとスロットを自分で定義する場合に違いがあるようです．基本的にはQtの関数をラップしてあるだけなので，GUIの機能の詳細についてはQtのドキュメントを参照することになります．

以下に載せてある今回作成したプログラムはGitHub - mmisono/pyqt5-example: PyQt5 exampleにあります．

インストール

(python3.4, Qt5.3.1を使ってMac OS Xにインストールしました）．インストールは公式からSIPとPyQt5のソースを落とします．
まずSIPをインストールします．

$ python configure.py
$ make
$ make install (virtualenvを使っている場合そのままmake installでokです)

SIPというのはC++プログラムをpythonで利用できるようにラップしてくれるもので，
これを利用してPyQt5はQtをPythonから使えるようにします．
SIPがインストールできたらPyQt5をインストールします．configure時にオプションでqmakeの場所を
教えて上げます．

$ python configure.py --qmake /usr/local/Cellar/qt5/5.3.1/bin/qmake
$ make (ちょっと時間がかかる)
$ make install

2014/11/12現在ではまだQt5.3.2はサポートされていないようです(makeに失敗する)．

ちなみに，作業ディレクトリに日本語パスが含まれていると上手くいきません．windowsの場合はインストーラを使えばよさそうです．

例1: フロントエンドとしての利用

さて，それでは実際にPyQt5でプログラムを作ってみます．PyQt5で作るときには何よりも楽に速く作れることを目指すことにします（大きいの書くならC++使いますからね）．

まず，よくありそうなパターンの1つである，フロントエンドとしてのPyQt5アプリケーションを作ってみました．階乗を計算するだけ(笑)のプログラムです．

pyqt5-example/factorial.py at master · mmisono/pyqt5-example · GitHub

#!/usr/bin/env python

from PyQt5.QtWidgets import (QApplication, QWidget,
                             QGridLayout, QVBoxLayout, QHBoxLayout,
                             QLabel, QLineEdit, QPushButton)

def factorial(n):
    if n < 0:
        return -1
    elif n == 0:
        return 1
    else:
        return n * factorial(n-1)

class MainWindow(QWidget):
    def __init__(self, parent=None):
        super(MainWindow, self).__init__(parent)

        self.inputLine = QLineEdit()
        self.outputLine = QLineEdit()
        self.outputLine.setReadOnly(True)

        self.calcButton = QPushButton("&Calc")
        self.calcButton.clicked.connect(self.calc)

        lineLayout = QGridLayout()
        lineLayout.addWidget(QLabel("num"), 0, 0)
        lineLayout.addWidget(self.inputLine, 0, 1)
        lineLayout.addWidget(QLabel("result"), 1, 0)
        lineLayout.addWidget(self.outputLine, 1, 1)

        buttonLayout = QVBoxLayout()
        buttonLayout.addWidget(self.calcButton)

        mainLayout = QHBoxLayout()
        mainLayout.addLayout(lineLayout)
        mainLayout.addLayout(buttonLayout)

        self.setLayout(mainLayout)
        self.setWindowTitle("Factorial")

    def calc(self):
        n = int(self.inputLine.text())
        r = factorial(n)
        self.outputLine.setText(str(r))

if __name__ == '__main__':
    import sys
    app = QApplication(sys.argv)
    main_window = MainWindow()

    main_window.show()
    sys.exit(app.exec_())

この場合は，QWidgetをメインウィンドウとして利用します．コンストラクタでボタンや入力フィールドの配置とシグナルのセットアップをおこないます．Qtを使ったことがあればほぼ違和感なくソースが読めると思います．Qtで書いてるように書けばだいたいOKです．Qtを使ってなくてもやってることは分かりやすいと思います．レイアウトはQHBoxLayoutやQVBoxLayoutに任せるのが楽でいいです．アプリケーションとして重要なのがself.calcButton.clicked.connect(self.calc)の部分で，ここでcalcボタンを押したときにcalcが呼ばれます．

例2: 簡単に描画する

先ほどの例では描画機能がありませんでしたが，実際にGUIが欲しくなるのは何かを描画したいときが多いと思います．ということで今度は描画メインのプログラムを作ってみました．簡単なマルバツです．

pyqt5-example/tic_tac_toe.py at master · mmisono/pyqt5-example · GitHub

#!/usr/bin/env python

from PyQt5.QtCore import (QLineF, QPointF, QRectF, Qt)
from PyQt5.QtGui import (QBrush, QColor, QPainter)
from PyQt5.QtWidgets import (QApplication, QGraphicsView, QGraphicsScene, QGraphicsItem,
                             QGridLayout, QVBoxLayout, QHBoxLayout,
                             QLabel, QLineEdit, QPushButton)

class TicTacToe(QGraphicsItem):
    def __init__(self):
        super(TicTacToe, self).__init__()
        self.board = [[-1, -1, -1],[-1, -1, -1], [-1, -1, -1]]
        self.O = 0
        self.X = 1
        self.turn = self.O

    def reset(self):
        for y in range(3):
            for x in range(3):
                self.board[y][x] = -1
        self.turn = self.O
        self.update()

    def select(self, x, y):
        if x < 0 or y < 0 or x >= 3 or y >= 3:
            return
        if self.board[y][x] == -1:
            self.board[y][x] = self.turn
            self.turn = 1 - self.turn

    def paint(self, painter, option, widget):
        painter.setPen(Qt.black)
        painter.drawLine(0,100,300,100)
        painter.drawLine(0,200,300,200)
        painter.drawLine(100,0,100,300)
        painter.drawLine(200,0,200,300)

        for y in range(3):
            for x in range(3):
                if self.board[y][x] == self.O:
                    painter.setPen(Qt.red)
                    painter.drawEllipse(QPointF(50+x*100, 50+y*100), 30, 30)
                elif self.board[y][x] == self.X:
                    painter.setPen(Qt.blue)
                    painter.drawLine(20+x*100, 20+y*100, 80+x*100, 80+y*100)
                    painter.drawLine(20+x*100, 80+y*100, 80+x*100, 20+y*100)

    def boundingRect(self):
        return QRectF(0,0,300,300)

    def mousePressEvent(self, event):
        pos = event.pos()
        self.select(int(pos.x()/100), int(pos.y()/100))
        self.update()
        super(TicTacToe, self).mousePressEvent(event)

class MainWindow(QGraphicsView):
    def __init__(self):
        super(MainWindow, self).__init__()
        scene = QGraphicsScene(self)
        self.tic_tac_toe = TicTacToe()
        scene.addItem(self.tic_tac_toe)
        scene.setSceneRect(0, 0, 300, 300)
        self.setScene(scene)
        self.setCacheMode(QGraphicsView.CacheBackground)
        self.setWindowTitle("Tic Tac Toe")

    def keyPressEvent(self, event):
        key = event.key()
        if key == Qt.Key_R:
            self.tic_tac_toe.reset()
        super(MainWindow, self).keyPressEvent(event)

if __name__ == '__main__':
    import sys
    app = QApplication(sys.argv)
    mainWindow = MainWindow()

    mainWindow.show()
    sys.exit(app.exec_())

今回はメインウィンドウとしてQGraphicsViewを利用しています（QGraphicsViewはQWidgetを継承してます）．Qtの描画機能は，大雑把にいうとQGraphicsSceneを作って，その中にQGraphicsItemを配置して，最終的にQGraphicsSceneをQGraphicsViewにセットすることでおこないます．そこで，マルバツの本体はQGraphicsItemを継承する形で作成しています．QGraphicsItemで大事なのはpaint()関数とboudingRect()関数で，これを定義してあげることで描画がおこなわれます．また，mousePressEvent()を実装することでマウスイベントを，keyPressEvent()を実装することキーイベントがキャッチできます．今回はQGraphicsItemは一つしか使ってませんが，もちろん複数のQGraphicsItemを使う事ができます．QGraphicsItemを使うと，マウスイベントのディスパッチや衝突判定をQt側でおこなってくれるので，例えばグラフを可視化するプログラムを作って，グラフの頂点をマウスドラッグで動かせるようにするといったことが簡単にできます．ボタンや入力フィールドが無い場合はこの構成で十分だと思います．

例3: QWidgetとQGraphicsViewの組み合わせ

個人的にこれが一番使うかもしれません．メインウィンドウをQWidgetで作成して，その中にQGraphicsViewと操作用のボタンや入力フィールドを配置します．例として，1次元のセルオートマトンをシミュレートするプログラムを作ってみました．

pyqt5-example/cellular_automaton.py at master · mmisono/pyqt5-example · GitHub

このプログラムでは，QTimerを利用することでアニメーションをしています．QTimerの使い方は，Qtimerのインスタンスを作成してtimeoutシグナルに対し呼び出したい関数をconnectし，timerを起動させるという流れになります．このとき，QGraphicsItem自体はQObjectを継承していないためシグナルを扱う事が出来ないので*1，メインウィンドウ側でQTimerを実行し，定期的に描画をおこなう構成にしています．いろいろやり方はありますがこれがシンプルなんじゃないかなと思います．

例4: matplotlibtとの連携

PyQt5を使ってうれしい機能の一つに，matplotlibと簡単に連携できることがあげられます．matplotlibは1.4.0からPyQt5をサポートしてます．以下がmatplotlibをPyQt5から使用する例です．

pyqt5-example/plot.py at master · mmisono/pyqt5-example · GitHub

#!/usr/bin/env python

import random
import numpy as np
from matplotlib.backends.backend_qt5agg import FigureCanvasQTAgg as FigureCanvas
from matplotlib.figure import Figure

from PyQt5.QtCore import (QLineF, QPointF, QRectF, Qt, QTimer)
from PyQt5.QtGui import (QBrush, QColor, QPainter)
from PyQt5.QtWidgets import (QApplication, QGraphicsView, QGraphicsScene, QGraphicsItem,
                             QGridLayout, QVBoxLayout, QHBoxLayout, QSizePolicy,
                             QLabel, QLineEdit, QPushButton)

# FigureCanvas inherits QWidget
class MainWindow(FigureCanvas):
    def __init__(self, parent=None, width=4, height=3, dpi=100):
        fig = Figure(figsize=(width, height), dpi=dpi)
        self.axes = fig.add_subplot(111)
        self.axes.hold(False)

        super(MainWindow, self).__init__(fig)
        self.setParent(parent)

        FigureCanvas.setSizePolicy(self,
                                   QSizePolicy.Expanding,
                                   QSizePolicy.Expanding)
        FigureCanvas.updateGeometry(self)

        timer = QTimer(self)
        timer.timeout.connect(self.update_figure)
        timer.start(50)

        self.x  = np.arange(0, 4*np.pi, 0.1)
        self.y  = np.sin(self.x)

        self.setWindowTitle("Sin Curve")

    def update_figure(self):
        self.axes.plot(self.x, self.y)
        self.y = np.roll(self.y,-1)
        self.draw()

if __name__ == '__main__':
    import sys
    app = QApplication(sys.argv)
    mainWindow = MainWindow()

    mainWindow.show()
    sys.exit(app.exec_())

matplotlibのFigureCanvasQTAggを継承してクラスを作って，その中でdraw()を呼ぶとグラフが描画されます．アニメーションをしたければQTimerを使ってdraw()を定期的に呼ぶようにすればokです（簡単!）．こんなことができるのはFigureCanvasQTAggが（QGraphicsItemではなく）QWidgetを継承しているからです．QWidgetを継承しているのでQTimerのtimeoutシグナルも使えます．もちろんこれは一番単純な例で，セルオートマトンの例のように自分でQWidgetを使ってメインウィンドウを作り，その中にmatplotlibを埋め込むことができます．

例4: uiファイル(Qt Designer)を使う

さて，これまではQtのuiファイルを活用してきませんでしたが，ボタンや入力フィールドがたくさんあるような場合だと やはりQt Designerでuiファイルを作成した方が楽です． uiファイルをPyQt5で使う方法は単純で，まずQt Designerを使ってuiファイルを作成した後，pyuic5コマンドを利用してuiファイルをpythonスクリプトに変換します．以下に例を示します．

https://github.com/mfumi/pyqt5-example/tree/master/echo

echo_ui.py

# -*- coding: utf-8 -*-

# Form implementation generated from reading ui file 'echo.ui'
#
# Created: Wed Nov 12 18:33:05 2014
#      by: PyQt5 UI code generator 5.3.2
#
# WARNING! All changes made in this file will be lost!

from PyQt5 import QtCore, QtGui, QtWidgets

class Ui_Echo(object):
    def setupUi(self, Echo):
        Echo.setObjectName("Echo")
        Echo.resize(250, 200)
        self.textBrowser = QtWidgets.QTextBrowser(Echo)
        self.textBrowser.setGeometry(QtCore.QRect(40, 90, 180, 79))
        self.textBrowser.setObjectName("textBrowser")
        self.horizontalLayoutWidget = QtWidgets.QWidget(Echo)
        self.horizontalLayoutWidget.setGeometry(QtCore.QRect(40, 30, 180, 41))
        self.horizontalLayoutWidget.setObjectName("horizontalLayoutWidget")
        self.horizontalLayout = QtWidgets.QHBoxLayout(self.horizontalLayoutWidget)
        self.horizontalLayout.setContentsMargins(0, 0, 0, 0)
        self.horizontalLayout.setObjectName("horizontalLayout")
        self.inputEdit = QtWidgets.QLineEdit(self.horizontalLayoutWidget)
        self.inputEdit.setObjectName("inputEdit")
        self.horizontalLayout.addWidget(self.inputEdit)
        self.submitButton = QtWidgets.QPushButton(self.horizontalLayoutWidget)
        self.submitButton.setObjectName("submitButton")
        self.horizontalLayout.addWidget(self.submitButton)

        self.retranslateUi(Echo)
        QtCore.QMetaObject.connectSlotsByName(Echo)

    def retranslateUi(self, Echo):
        _translate = QtCore.QCoreApplication.translate
        Echo.setWindowTitle(_translate("Echo", "Echo"))
        self.submitButton.setText(_translate("Echo", "Submit"))

echo.py

#!/usr/bin/env python

from PyQt5.QtWidgets import (QApplication, QWidget,
                             QGridLayout, QVBoxLayout, QHBoxLayout,
                             QLabel, QLineEdit, QPushButton)
import echo_ui

class MainWindow(QWidget):
    def __init__(self, parent=None):
        super(MainWindow, self).__init__(parent)
        self.ui = echo_ui.Ui_Echo()
        self.ui.setupUi(self)
        self.ui.submitButton.clicked.connect(self.submit)

    def submit(self):
        text = self.ui.inputEdit.text()
        self.ui.textBrowser.append(text)

if __name__ == '__main__':
    import sys
    app = QApplication(sys.argv)
    main_window = MainWindow()

    main_window.show()
    sys.exit(app.exec_())

pyuic5で生成されたファイルは見ればわかるようにUIをセットアップする関数を含んでいるので，あとはこれを呼ぶだけです．便利!!!

まとめ

ということで実際にPyQt5を使っていくつかアプリケーションを作ってみました．ここにあるのはどれも慣れれば数十分で作成できます．まぁ，これはPyQt5というよりそもそもQt5が使いやすいからというのが大部分を占めてると思いますが．Qtはqmakeあるいはcmakeを前提にしているとはいえ，Qt Creatorを使えばかなり簡単に作成できるので，PyQt5を使うのと速度的にそれほど大きな差はないかもしれません．でも小さいものではやはりコンパイル無しの1ファイルで作れるPyQt5は楽だと思いますし，pythonで何か描画したいというときに重宝すると思いました*2．今回作ったサンプルもベースとして結構活用できるんじゃないかなと思います．

*1:QGraphicsObjectを使えばできますが

*2:勿論，もっと複雑なものも作れます

goのstructとinterface辺りのメモ

・ポインタはよしなにdereferenceしてくれる
http://golang.org/ref/spec#Selectors
http://play.golang.org/p/WtCuLsr824

package main

type T0 struct {
	x int
}

func (recv *T0) M0(){
	println("*T0:",recv.x)
}

type T1 struct {
	y int
}

func (recv T1) M1(){
	println("M1:",recv.y)
}

type T2 struct {
	z int
	T1
	*T0
}

func (recv *T2) M2(){
	println("*T2:",recv.z)
}

func main(){

	var p *T2 = &T2{3,T1{2},&T0{1}}

	println(p.z)
	println((*p).z)
	(*p).M2()
	p.M2()
	(*p).T1.M1()
	p.M1()
	(*(*p).T0).M0()
	p.M0()
	(*p).M0()
	
	(*T2).M2(p)
	(T1).M1(p.T1)
	(*T0).M0(p.T0)
}

3
3
*T2: 3
*T2: 3
M1: 2
M1: 2
*T0: 1
*T0: 1
*T0: 1
*T2: 3
M1: 2
*T0: 1

ポインタをよしなに扱ってくれるので以下のように呼び出せる (ただし当然M0()内でのrecvの変更は呼び出し元に影響しない)
http://play.golang.org/p/DE_2nzUOsq

package main

type T0 struct {
	x int
}

func (recv T0) M0(){
	recv.x = 4;
	println("*T0:",recv.x)
}

func main(){
	var t *T0 = &T0{2}
	t.M0()
	println(t.x)
}

*T0: 4
2

・interface type にはinterfaceを実装するものが入れられる．interace type から呼び出せるのはinterfaceで宣言されたメソッドのみ．interface type から特定のtypeに変換したい場合はtype assertionを使う
・以下の例では &Bar{}をtype Fooの変数に代入しているが， *Bar をレシーバとしてFoo()が定義されており interface Fooを満足しているでok．このとき別に type Foo のポインタを使うわけではない．
http://golang.org/ref/spec#Type_assertions
http://play.golang.org/p/aItoeCpxqx

package main

import "fmt"

type Foo interface {
	Foo() string
}

type Bar struct{}

type Boo struct{}

func (b *Bar) Foo() string {
	return "Bar: Foo()"
}

func (b *Bar) Bar() string {
	return "Bar: Bar()"
}

func (b *Boo) Foo() string {
	return "Boo: Foo()"
}

func (b *Boo) Boo() string {
	return "Boo: Boo()"
}

func main() {
	var f Foo = &Bar{}
	fmt.Println(f.Foo())
	if b, ok := f.(*Bar); ok {
		fmt.Println(b.Bar())
	}
	if b, ok := f.(*Boo); ok {
		fmt.Println(b.Boo())
	}
	
}

Bar: Foo()
Bar: Bar()

interface typeのポインタを使う例 (使い道ある?)
http://play.golang.org/p/-WK_XHE3lX

package main

import "fmt"

type Foo interface {
	Foo() string
}

type Bar struct{}

type Boo struct{}

func (b *Bar) Foo() string {
	return "Bar: Foo()"
}

func (b *Bar) Bar() string {
	return "Bar: Bar()"
}

func main() {
	var b *Bar = &Bar{}
	var pf *Foo = new(Foo)
	*pf = b
	fmt.Println((*pf).Foo())
}

・あるtypeの変数が特定のinterface typeを満足しているか調べるには，調べたい変数をinterface{}にキャストしてtype assertionを使う (type assertionできるのは interface typeのみ)
http://play.golang.org/p/brB8FOHjgc

package main

import "fmt"

type Foo interface {
	Foo() string
}

type Bar struct{}

type Boo struct{}

func (b *Bar) Foo() string {
	return "Bar: Foo()"
}

func (b *Bar) Bar() string {
	return "Bar: Bar()"
}

func main() {
	var b *Bar = &Bar{}
	if f, ok := interface{}(b).(Foo); ok {
		fmt.Println(f.Foo())
	}
}

Bar: Foo()

・type assertionするのにswitch文が使える
http://golang.org/ref/spec#Switch_statements
http://play.golang.org/p/owDgNUWLGC

package main

import "fmt"

type Foo interface {
	Foo() string
}

type Bar struct{}

type Boo struct{}

func (b *Bar) Foo() string {
	return "Bar: Foo()"
}

func (b *Bar) Bar() string {
	return "Bar: Bar()"
}

func (b *Boo) Foo() string {
	return "Boo: Foo()"
}

func (b *Boo) Boo() string {
	return "Boo: Boo()"
}

func main() {
	var f Foo = &Bar{}
	switch f.(type) {
		case (*Bar) : {
			fmt.Println(f.(*Bar).Bar())
		}
		case (*Boo) : {
			fmt.Println(f.(*Boo).Boo())
		}
		default :{
			fmt.Println("unkown type")
		}
	}
}

Bar: Bar()

まとめ: 普通に公式のspecが分かりやすい

木を綺麗に描画するアルゴリズム

少し前に作ってそのままにしてたんですが，木(特に2分木)を綺麗に描画するかというアルゴリズムについて少し資料にまとめました．

木を綺麗に描画するアルゴリズム from mfumi

スライドで紹介している reingold tilford アルゴリズムを実際にjavascriptで実装してみたのが以下です．
GitHub - mmisono/tree-algo: binary tree implementation & Reingold-Tilford algorithm
yield文を使っているのでyieldを有効にしたchromeでないと多分動きません．あと実装怪しめ

本当は赤黒木を実装しようとしていて，そのとき描画方法に困ったので描画アルゴリズムについて調べたんですが，結局描画アルゴリズムを実装してからそのまま..

IPSC2014 D問題について

昨日おこなわれたIPSC2014にひっそり参加していました．IPSCとはInternet Problem Solving Contestの略で，ひとくくりにいってしまえば競技プロコンですが，普通の競技プロコンと違って，単純なアルゴリズム系でない問題もでます．

僕はCとDを解いた(というか解けなかった..)のですが，D問題は回答者が少なかったようなので，僕自身の解法の説明をしようと思います．ということで自分で解きたい人は以下は見ない方がいいと思います．

D問題の問題文はこれです．問題を要約してしまえば，ずばりあるテキストファイルを数回bzip2で圧縮してできたファイルがあるので，そのファイルからテキストを抽出せよという問題です．ただし，テキストファイルのほとんどは0(ヌル文字)で，元は1TBを超える大きさです．問題はeasyとhardの2種類あり，それぞれファイルはd1.inとd2.inです．

CPythonのgrennlet(グリーンスレッド)の実装について

OSが管理するスレッドと違って，ユーザのプログラムによって管理されるスレッドのことをグリーンスレッドといいます．他にもマイクロスレッドとか軽量スレッドとかいったりすることもあるようです．ネイティブスレッド(OSが管理するスレッド)と比較したときのグリーンスレッドの特徴として．
・スケジューリングをユーザプログラム自身がおこなう
・一般にスレッドの切り替えコストはネイティブスレッドより低い
・一つのプログラム内において実行されるグリーンスレッドは一つ (マルチコアでも，OSから見るとあくまでユーザプログラムは一つなので，グリーンスレッドが並列実行されることがない）などが上げられます．

greenletとは，PythonのC言語実装であるCPythonにおけるグリーンスレッドの実装の一つです．(2014/4/29現在，greenletはpython2.xのみをサポートしています．また，以下での説明でgreenletのバージョンは0.4.2です．)
greenletを使用することでプログラムの処理を一旦停止して別の処理をおこなうコルーチンが簡単に実現できます．公式のサンプルコードそのままですが，

    from greenlet import greenlet

    def test1():
        print 12
        gr2.switch()
        print 34

    def test2():
        print 56
        gr1.switch()
        print 78

    gr1 = greenlet(test1)
    gr2 = greenlet(test2)
    gr1.switch()

このようにして実行すると，

12
56
34

が表示されます．greenlet()で新たなグリーンスレッド(greenletと呼びます)を作成し，switch()でそのgreenletに処理を切り替えます．greenletには親子関係が存在し，子が終了したら親の処理が再開されます．特に親を指定しない場合はメインスレッドが親になります．この例ではtest1()が終了したあと，メインスレッドに戻ってプログラムが終了します（test2()の残りの部分は実行されずに終わります）.
プログラムを一旦停止するだけならpythonにはジェネレータがあるのでyieldを使えばできますが，greenletを使うことで関数の呼び出し階層にかかわらず同一スレッド内なら任意のgreenletへ処理を切り替える事が出来ます．

さて，このgreenletの中身ですが，pythonで実装されているのではなく，CPythonのモジュール(C言語拡張)として実装されています．CPythonの拡張方法の詳細はここに書いてあります．
greenletのオブジェクト(PyGrrenlet)は以下のように定義されています．

greenlet.h

typedef struct _greenlet {
    PyObject_HEAD
    char* stack_start;
    char* stack_stop;
    char* stack_copy;
    intptr_t stack_saved;
    struct _greenlet* stack_prev;
    struct _greenlet* parent;
    PyObject* run_info;
    struct _frame* top_frame;
    int recursion_depth;
    PyObject* weakreflist;
    PyObject* exc_type;
    PyObject* exc_value;
    PyObject* exc_traceback;
    PyObject* dict;
} PyGreenlet;

ここで特に重要なのが，stack_start, stack_stop, stack_copy, stack_prev, parentあたりです．一般にプログラムの処理を切り替える（コンテキストスイッチ）ために何が必要かというと，各種レジスタを保存することと，スタックを切り替えることです．greenletでもスタック上にレジスタを退避させ，そしてそのスタックを切り替えることで，コンテキストスイッチを実現します．greenletにおけるスタックレイアウトは以下のようになっています(ソースコードのコメントより)

Stack layout for a greenlet:

               |     ^^^       |
               |  older data   |
               |               |
  stack_stop . |_______________|
        .      |               |
        .      | greenlet data |
        .      |   in stack    |
        .    * |_______________| . .  _____________  stack_copy + stack_saved
        .      |               |     |             |
        .      |     data      |     |greenlet data|
        .      |   unrelated   |     |    saved    |
        .      |      to       |     |   in heap   |
 stack_start . |     this      | . . |_____________| stack_copy
               |   greenlet    |
               |               |
               |  newer data   |
               |     vvv       |

PyGreenletのstack_stopがそのgreenletのスタックの一番下，stack_startがスタックの一番上を指します．またスタック領域の一部は他のgreenletを実行する際にはヒープに退避されます．ヒープ領域を覚えるために必要なのがstack_copyとstack_savedです．全ての領域をヒープに退避せずに一部だけ退避させるのはメモリ効率のためでしょうか．

greenletのsiwtch()を呼んだとき，一般に以下のような順番で関数が呼ばれます．

g_switch() => g_switchstack() => g_slp_switch() => SLP_SAVESTATE => SLP_RESTORE_STATE

まずはg_switch()から見てきます．

static PyObject *
g_switch(PyGreenlet* target, PyObject* args, PyObject* kwargs)
{
    ...
    /* find the real target by ignoring dead greenlets,
       and if necessary starting a greenlet. */
    while (target) {
        if (PyGreenlet_ACTIVE(target)) {
            ts_target = target;
            err = g_switchstack();  # スタックの切り替え
            break;
        }
        if (!PyGreenlet_STARTED(target)) {
            void* dummymarker;
            ts_target = target;
            err = g_initialstub(&dummymarker);
            if (err == 1) {
                continue; /* retry the switch */
            }
            break;
        }
        target = target->parent;
    }
    ...
}

PyGreenlet_ACTIVE(target)が真のとき，つまり切り替え対象のgreenletが既に一度は実行されているとき，g_switchstack()を呼びます．

static int g_switchstack(void)
{
    ...
    int err;
    {   /* save state */
        PyGreenlet* current = ts_current;   // ts_currentが現在のgreenlet
        PyThreadState* tstate = PyThreadState_GET();
        current->recursion_depth = tstate->recursion_depth;
        current->top_frame = tstate->frame;
        current->exc_type = tstate->exc_type;
        current->exc_value = tstate->exc_value;
        current->exc_traceback = tstate->exc_traceback;
    }
    err = slp_switch();
    if (err < 0) {   /* error */
        ...
    }
    else {
        PyGreenlet* target = ts_target;
        PyGreenlet* origin = ts_current;
        ...
    }
    return err;
}

g_switchstack()では現在の状態をcurrentに保存したあと，slp_switch()を呼びます．このslp_switch()が実際のレジスタの退避とスタックの切り替えを行いますが，そういった処理はアセンブラを使わなければできないため，CPUごとにplatform/switch_amd64_unix.c のように定義されています．

switch_amd64_unix.c

#define REGS_TO_SAVE "r12", "r13", "r14", "r15"

static int
slp_switch(void)
{
    int err = 0;
    void* rbp;
    void* rbx;
    unsigned int csr;
    unsigned short cw;
    register long *stackref, stsizediff;
    __asm__ volatile ("" : : : REGS_TO_SAVE);
    __asm__ volatile ("fstcw %0" : "=m" (cw));
    __asm__ volatile ("stmxcsr %0" : "=m" (csr));
    __asm__ volatile ("movq %%rbp, %0" : "=m" (rbp));
    __asm__ volatile ("movq %%rbx, %0" : "=m" (rbx));
    __asm__ ("movq %%rsp, %0" : "=g" (stackref));
    {
        SLP_SAVE_STATE(stackref, stsizediff);
        __asm__ volatile (
            "addq %0, %%rsp\n"
            "addq %0, %%rbp\n"
            :
            : "r" (stsizediff)
            );
        SLP_RESTORE_STATE();
        err = fancy_return_zero();
    }
    __asm__ volatile ("movq %0, %%rbx" : : "m" (rbx));
    __asm__ volatile ("movq %0, %%rbp" : : "m" (rbp));
    __asm__ volatile ("ldmxcsr %0" : : "m" (csr));
    __asm__ volatile ("fldcw %0" : : "m" (cw));
    __asm__ volatile ("" : : : REGS_TO_SAVE);
    return err;
}

前半部分でスタック上に必要なレジスタを退避し，SLP_SAVE_STATE()とその次の部分でスタックの切り替えをおこないます．

    __asm__ volatile ("" : : : REGS_TO_SAVE);

とするとgccインラインアセンブラの記述によってREGS_TO_SAVEで指定したレジスタがワーカレジスタであることがコンパイラに伝わるので，これらのレジスタを退避するコードをコンパイラが生成してくれます．具体的には，

 0x100000f54:  pushq  %r15
 0x100000f56:  pushq  %r14
 0x100000f58:  pushq  %r13
 0x100000f5a:  pushq  %r12
 ... (処理)
 0x100000f72:  popq   %r12
 0x100000f74:  popq   %r13
 0x100000f76:  popq   %r14
 0x100000f78:  popq   %r15

のようになります．r12-r15を退避させているのはx64の呼び出し規約によります．fstcwでFPUの制御レジスタの退避，stmxcsrでSSE関連の制御レジスタの退避をします．"=m"(cw)のようにしているので，スタック上のローカル変数に値が退避されていることが分かります．スタックが切り替わった後半部分ではレジスタの復元をおこないます．スタックが切り替わっているのでこの関数から戻った時点で既に切り替え対象だったgreenletに処理が移っています．分かりにくいですが前半部分で処理を停止したgreenletが次に再開されるときはSLP_RESTORE_STATE()からということです．(ところで一番最後のREGS_TO_SAVEの文はいらないような..?)

SLP_SAVE_STATE()とSLP_RESTORE_STATE()で一体何をしているかというと，この2つはマクロとしてgreenlet.cに定義されています．

#define SLP_SAVE_STATE(stackref, stsizediff)        \
  stackref += STACK_MAGIC;              \
  if (slp_save_state((char*)stackref)) return -1;   \
  if (!PyGreenlet_ACTIVE(ts_target)) return 1;      \
  stsizediff = ts_target->stack_start - (char*)stackref

#define SLP_RESTORE_STATE()         \
  slp_restore_state()

既にgreenletが存在している場合(switch()の呼び出しが2回目以降)，SLP_SAVE_STATE()はslp_save_state()関数を呼び，さらにstsizediffに切り替え先のgreenletと現在のスタックの先頭との差を格納します．SLP_SAVE_STATE()の次にあるインラインアセンブラ部分で%rspと%rbpにその差を加える事でスタックの切り替えを実現している訳です．
slp_save_state()では，ヒープに必要なだけスタックの退避をおこないます．つまり，切り替え先のstack_stop(target_stop)が，現在のstack_stopよりも上にあるなら，その分をヒープに格納します．

static int GREENLET_NOINLINE(slp_save_state)(char* stackref)
{
    /* must free all the C stack up to target_stop */
    char* target_stop = ts_target->stack_stop; # 切り替え先のスタックの下限
    PyGreenlet* owner = ts_current;
    assert(owner->stack_saved == 0);
    if (owner->stack_start == NULL)
        owner = owner->stack_prev;  /* not saved if dying */
    else
        owner->stack_start = stackref;
    
    while (owner->stack_stop < target_stop) {
        /* ts_current is entierely within the area to free */
        if (g_save(owner, owner->stack_stop))
            return -1;  /* XXX */
        owner = owner->stack_prev;
    }
    if (owner != ts_target) {
        if (g_save(owner, target_stop))
            return -1;  /* XXX */
    }
    return 0;
}

g_save()で実際にヒープへのコピーをおこないます．

static int g_save(PyGreenlet* g, char* stop)
{
    /* Save more of g's stack into the heap -- at least up to 'stop'

       g->stack_stop |________|
                     |        |
                     |    __ stop       . . . . .
                     |        |    ==>  .       .
                     |________|          _______
                     |        |         |       |
                     |        |         |       |
      g->stack_start |        |         |_______| g->stack_copy

     */
    intptr_t sz1 = g->stack_saved;
    intptr_t sz2 = stop - g->stack_start;
    assert(g->stack_start != NULL);
    if (sz2 > sz1) {
        char* c = (char*)PyMem_Realloc(g->stack_copy, sz2);
        if (!c) {
            PyErr_NoMemory();
            return -1;
        }
        memcpy(c+sz1, g->stack_start+sz1, sz2-sz1);
        g->stack_copy = c;
        g->stack_saved = sz2;
    }
    return 0;
}

slp_restore_state()では逆にヒープに退避していたスタック領域をスタックに復元します．実行するgreenletのスタック領域は必ず全てスタックになければいけないため，ヒープに退避していたもの全てを復元します(復元しても良いように事前にslp_save_state()で重複する部分はヒープに退避されています)．

static void GREENLET_NOINLINE(slp_restore_state)(void)
{
    PyGreenlet* g = ts_target;
    PyGreenlet* owner = ts_current;
    
    /* Restore the heap copy back into the C stack */
    if (g->stack_saved != 0) {
        memcpy(g->stack_start, g->stack_copy, g->stack_saved);
        PyMem_Free(g->stack_copy);
        g->stack_copy = NULL;
        g->stack_saved = 0;
    }
    if (owner->stack_start == NULL)
        owner = owner->stack_prev; /* greenlet is dying, skip it */
    while (owner && owner->stack_stop <= g->stack_stop)
        owner = owner->stack_prev; /* find greenlet with more stack */
    g->stack_prev = owner;
}

ということで以上がgreenletにおけるコンテキストスイッチの概要ですが， 一番最初に greenletを作って実行するときはどのようになっているでしょうか.

まず，最初にgreeletオブジェクトを作成するときにはgreen_new()が呼ばれます．

static PyObject* green_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
    PyObject* o;
    if (!STATE_OK)
        return NULL;
    
    o = type->tp_alloc(type, 0);
    if (o != NULL) {
        Py_INCREF(ts_current);
        ((PyGreenlet*) o)->parent = ts_current;
    }
    return o;
}

ここで，STATE_OKは以下のマクロで，

#define STATE_OK    (ts_current->run_info == PyThreadState_GET()->dict \
            || !green_updatecurrent())

最初はgreen_updatecurrent()が呼ばれます．

static int green_updatecurrent(void)
{
    ...
    /* first time we see this tstate */
    current = green_create_main();
    ...
    ts_current = current;
    ...
    return 0;
}

この中でgreen_create_main()が呼ばれ，メインスレッドのgreenletが作成され，それがts_currentになります．

static PyGreenlet* green_create_main(void)
{
    PyGreenlet* gmain;
    PyObject* dict = PyThreadState_GetDict();
    if (dict == NULL) {
        if (!PyErr_Occurred())
            PyErr_NoMemory();
        return NULL;
    }

    /* create the main greenlet for this thread */
    gmain = (PyGreenlet*) PyType_GenericAlloc(&PyGreenlet_Type, 0);
    if (gmain == NULL)
        return NULL;
    gmain->stack_start = (char*) 1;
    gmain->stack_stop = (char*) -1;
    gmain->run_info = dict;
    Py_INCREF(dict);
    return gmain;
}

したがって，最初に作成したgreenletの親はメインスレッドのgreenletになります．(その後green_init()が呼ばれ，明示的に親を指定した場合はそれが親になります)．さて，新規のgreenletに対してswitch()をした場合，g_switch()内からg_initialstub()が呼ばれます．

static PyObject *
g_switch(PyGreenlet* target, PyObject* args, PyObject* kwargs)
{
    ...
    /* find the real target by ignoring dead greenlets,
       and if necessary starting a greenlet. */
    while (target) {
        if (PyGreenlet_ACTIVE(target)) {
            ts_target = target;
            err = g_switchstack()
            break;
        }
        if (!PyGreenlet_STARTED(target)) {
            void* dummymarker;
            ts_target = target;
            err = g_initialstub(&dummymarker); # 初めてgreenletを実行する場合
            if (err == 1) {
                continue; /* retry the switch */
            }
            break;
        }
        target = target->parent;
    }
    ...
}

g_initialstub()では，初期設定ののち，g_switchstack()をしてスタックを切り替えます．

static int GREENLET_NOINLINE(g_initialstub)(void* mark)
{
    ...
    /* start the greenlet */
    self->stack_start = NULL;
    self->stack_stop = (char*) mark;
    if (ts_current->stack_start == NULL) {
        /* ts_current is dying */
        self->stack_prev = ts_current->stack_prev;
    }
    else {
        self->stack_prev = ts_current;
    }
    ...

    /* restore arguments in case they are clobbered */
    ts_target = self;
    ts_passaround_args = args;
    ts_passaround_kwargs = kwargs;

    /* perform the initial switch */
    err = g_switchstack();   # スタックの切り替え

    /* returns twice!
       The 1st time with err=1: we are in the new greenlet
       The 2nd time with err=0: back in the caller's greenlet
    */
    if (err == 1) {
        ...

        if (args == NULL) {
            /* pending exception */
            result = NULL;
        } else {
            /* call g.run(*args, **kwargs) */
            result = PyEval_CallObjectWithKeywords(   # 実際の処理の開始
                run, args, kwargs);
            ...
        }
        ...
        # greenletの処理が終了したので，親を再開させる
        /* jump back to parent */
        self->stack_start = NULL;  /* dead */
        for (parent = self->parent; parent != NULL; parent = parent->parent) {
            result = g_switch(parent, result, NULL);  # ここで親に処理を切り替える．成功すればもう戻ってこない
            /* Return here means switch to parent failed,
             * in which case we throw *current* exception
             * to the next parent in chain.
             */
            assert(result == NULL);
        }
        /* We ran out of parents, cannot continue */
        PyErr_WriteUnraisable((PyObject *) self);
        Py_FatalError("greenlets cannot continue");
    }
    ...
    return err;
}

ここで，重要なのが，ソースコメントにも書いてあるとおり，g_switchstack()からは2回リターンするということです(...!!!)．
どういう事かというと，g_switchstack()を実行してスタックを切り替えると，スタックが切り替わった時点で既に実行は新しいgreenletになっていますが，この新しいgreenletの状態でg_switchstack()がリターンします．そしてしばらくした後，その新しいgreenletが終了(あるいは明示的にswitch()した場合)，切り替え元のgreenletの処理が再開されるわけですが，その切り替え元のgreenletの状態でg_switchstack()が再びリターンするということです．g_switchstack()から戻ってきたとき，新しいgreenletなのか，それとも切り替えもとのgreenletなのかでg_switchstack()の戻り値は異なります．
これはslp_switch()をよく見ればわかります．slp_switch()で通常の切り替えが発生した場合，その戻り値は0です．しかし，切り替え先のgreenletが新しい場合，つまりヒープやスタックから情報を復元する必要がない場合，SLP_SAVE_STATE()でreturn 1が返されます．

#define SLP_SAVE_STATE(stackref, stsizediff)		\
  stackref += STACK_MAGIC;				\
  if (slp_save_state((char*)stackref)) return -1;	\
  if (!PyGreenlet_ACTIVE(ts_target)) return 1;		\  # ここが新しいgreenletの場合実行される
  stsizediff = ts_target->stack_start - (char*)stackref

g_switchstack()の戻り値が1の場合，新しいgreenletなのでそのgreenletを実行します．そして，そのgreenletが終了した場合親の処理を再開させます．勿論．そのgreenletが新たに別のswitch()を呼んで処理を切り替えることもあるでしょう．

ということで以上がgreenletの処理の概要になります．つくづくよくできてますね (´ρ`)

vimのconcealを使ってJavadocを奇麗に表示

この記事はVim Advent Calender 2013 118日目の記事です．VACは2011,2012と書いていたのですが気づいたらこんな時期になっていました．まぁまだ2013年度ですし何の問題もないですね．過去2回はよく分からないことを書いてしまったんですが今回は普通です．

• -

最近Javaを書いています．実を言うとJavaを書くときはvim以外にEclipseを併用することが多いんですが，やはりコーディングそのものはvimの方がしやすいと思います．
さて，JavaにはJavadocと言ってソースのコメントを一定の形式(HTML+α)に従って書いておくとそこからドキュメントを生成してくれるものがあります．そういう風にソースのコメントからドキュメントを生成する考えはすてきだなと思いますが，いかんせんJavadocを考えて書かれたコメントは読みにくいです..

いくら生成されるドキュメントが奇麗でもソースのコメントを読む気を減少させるようなのはちょっとあれですね．今回は表示させたくないものを隠したいのでこういうときはvim7.3から正式に導入されたconcealの出番です．concealは指定したsyntaxを隠したり，任意の一文字のように表示させたりします．
以下の内容を.vimrcに書いておくとjavaファイルを読み込んだときにconcealでタグを隠すようになります．
ソース: https://gist.github.com/mfumi/9814303
ちなみに，末尾で定義しているautocmdは本来であるならば何か適当なaurgoupを指定するべきです．やってることはjavadocとhtmlのシンタックスを強制的に書き換えています．本来ならば after/syntax 以下に書くべきかと思いますが個人的にファイルはなるべく作らない主義なので.vimrcに書いています．syntaxの内容は基本的にconceal属性をつけているだけです．あとは一部のハイライトを変更しています．
言い訳ですが久しぶりにsyntaxファイルを見たら何がなんだか分からなかったのでかなり適当です...

さて，これを使うと

これが

こうなります．それなりに見やすくなったと思います．concealの機能はあくまで表示を変えるだけですので本来のテキストは何も変わっていません．もとの内容を表示させたければ:setl conceallevel=0 にします．上の画像のconceallevelは2です．また，concealさせていても現在カーソルがある行の内容についてはconcealされていない状態の物が表示されます．

• -

concealは割と面白い機能だと思いますが，実際に公式で配布されているsyntaxで使用されているのはhelpとtexだけです．helpで使われてるの知らなかったって人は適当なhelpを開いて :set conceallevel=0 してみると面白いと思います．

ちなみにtexは:let g:tex_conceal="admgs" とかしておくと

これが

こうなって数式がそれなりに読めるようになります．まぁ\frac{}とかは駄目ですけど.

• -

ちなみに，concealを使っているプラグインの例としては以下のようなものがあります．

GitHub - tyok/js-mask: More concise JavaScript using Vim's "conceal" feature
javascriptのfunctionをfに変えます．

これが

こう... (＃＾ω＾)
類似のものとしてGitHub - c9s/perl-conceal.vim等があります．

GitHub - Twinside/vim-haskellConceal: Conceal operator for haskell
js-maskより少しconcealする文字が多いhaskell用プラグイン．

これが

若干スタイリッシュになります．

GitHub - chrisbra/csv.vim: A Filetype plugin for csv files
csv.vimはCSVを扱うプラグインですが，syntaxにconcealを使っています．

こういうCSVがあったとして，csv.vimのsyntaxでは区切り文字が|で表されます．

また，:VFold num とすると num列より左の文字がconcealされます．以下はVfold 1 の結果です．

AnsiEsc.vim - ansi escape sequences concealed, but highlighted as specified (conceal) : vim online
ANSIのエスケープシーケンスを含んだテキストを奇麗に表示してくれるプラグインです．

こういうファイルがあったとして，AnsiEsc.vimをインストールして:AnsiEscとすると，

こういう風に表示してくれます．これはgoodですね．(ちなみにファイルの生成元はこれです)

• -

個人的にはconcealでソースの見た目そのものを変えてもかえって混乱するだけなような気がします．concealの使い方としては奇麗にテキスト(ドキュメント)を表示するような目的で使った方が良いと思います．テキストに何か目印になるようなタグや記号が含まれている場合，vimのsyntaxを使って奇麗に色づけできるので，それにconcealを組み合わせることでより奇麗に表示させることができます．まぁ，そもそも表示させたくない文字がテキストに含まれている時点で何かが間違っているのかもしれませんが．

ところで，concealを使ってHTMLをいい感じに表示させるsyntaxとかあっても良いような気がするんですけどどっかにあるんでしょうか．