Yearly Archives: 2024

2024-06-07 ,

複数サブパス(複合パス)への対応

別のプロジェクトで簡単な絵が必要になったので自作の作図ツールを使って描いていたら色々不満があったので最近はちょくちょくいじっていました。そのプロジェクトはそっちのけで(笑)。

misohena/el-easydraw: Embedded drawing tool for Emacs

特に複数のサブパスを含むパスへの対応をいい加減やらなきゃな、と。

複数のサブパスとは

複数のサブパスというのは、一つのパスデータ(path要素のd属性:<path d=>)の中に複数の内部的なパス(サブパス)が表現されているような状況のことです。例えば <path d="M0,-100 L100,100 L-100,100 Z M0,-50 L-50,50 L50,50 Z" /> と書くと一つのpath要素で大小二つの三角形が表現できます。実際に表示してみるとこんな感じになります。

図1: d="M0,-100 L100,100 L-100,100 Z M0,-50 L-50,50 L50,50 Z"

複数のパスを表現したいなら複数のpath要素を使えばいいじゃないかと思うかもしれませんが、上のような「穴あき」を表現するには一つのパスデータの中の複数のパス(サブパス)が必要になります。複数のpath要素を重ねて配置しただけでは塗りつぶした大きな三角形の上に小さな三角形を塗りつぶすことしか出来ません。一つのパスの中に大小の三角形が一緒に入っていてはじめてこのような「穴あき」が作れます。

一つのパスの中に二つのパスが並んでいるだけでなぜ中が抜けるんだろうかと疑問に思う方もいると思いますが、これはこの図形をレンダリングすることを考えれば分かります。レンダリングの基本は画像を上から下へ一行ずつ、そして一行の中を左から右へ1ピクセルずつ色を決めて点を打っていくことです。例えばこの図形の真ん中らへんの一行(1ライン)をレンダリングするとします。画像の左端から右端へ向かって1ピクセルごと処理していきます。このとき各線分(segment)との交差判定をしながら進んでいくことがポイントです。一番最初は図形の外なので点を打ちません。右へ向かっていくと、最初の線分を跨ぎます。なので、それ以降は灰色のfill色を打ちます。さらに進むとまた線分を跨ぎます。なので、それ以降は図形の外にあると認識して点を打ちません。さらに進むとまた線分を跨ぐ(奇数回目)ので色を塗り始めます。そしてまた線分を跨いだら(偶数回目)塗るのを止めます。と、このように図形の内外を判定しながらレンダリングしていくのですが、このアルゴリズムで真ん中に穴あきがあるドーナツ形を作るには外側の線も内側の線も同じ判定対象(線分集合)の中に存在していなければなりません。凹形なら一つのパスでも作れるのでその上側をくっつけてしまうという回避策もありますが、strokeを指定するとボロが出たりと問題もあります。

ということで、一つのパスの中に複数のパス(サブパス)が必要になるわけです。

対応してこなかった理由

これまで対応してこなかった理由はひとえにデータ構造の悪さからでした。SVGのd=属性を解析して内部的な表現に変換してから編集するのですが、その内部的な表現の構造が悪すぎました。その表現は、d属性を解析したほぼそのままのコマンドリストでした。なので、一つアンカーを打てばMコマンド(最初の点を指定する)、Lコマンド(直線)、Cコマンド(カーブ)、Zコマンド(閉じる)を前後の状況に応じて判別して追加するような複雑なことをしなければなりませんでした。もちろんその複雑さを緩和するような層があって、上の層は下の層に処理を投げるだけなのですが、複数のサブパスに対応するには下の層を改善しなければならず、そしてそれは複雑なのでやりたくなかったわけです。

この構造のまま複数のサブパスにも(ユーザーからの様々な操作に対してちゃんと)対応しようとすると細かい条件分けが複雑すぎて大変でした。実は実際最後まで書き切ったのですが、どこかにバグがあっても不思議ではない、これからの改善も全くしたくないようなコードにしかなりませんでした。ウンザリしてすぐにその辺りのを構造(edraw-path.el)を書き直すことにしました。

新しい構造と内部・外部表現の変換

新しい構造はパス(パスデータ)、サブパス、アンカー、ハンドルを素直に表現したものとなりました。これによって様々な処理が驚くほどシンプルに素直に書けるようになりました。

そして新しい構造とSVGのd属性(コマンド文字列)との間の変換処理も用意して、必要に応じて変換します。これは従来の構造(コマンドリスト)でもそのような作りになっていました。

ただし、内部的な構造と実際のd属性の文字列(外部表現)との変換は必要最小限にする必要があります。それはどちらの方向でも失う情報があるからです。

SVGのd属性で表現できないもの

内→外で失うものとしては、開サブパスの端点の外側のハンドルがあります。何を言っているのかよく分からないかもしれませんが、次図の通りです。

閉(サブ)パス開(サブ)パス端点端点の外側のハンドル端点を持たない
図2: 開サブパスの端点の外側のハンドル

つまり、線の端っこのさらに外にあるハンドルです。実際のところこれは描画には全く影響を及ぼしません。なのでSVGのd属性で表す方法がありません。しかし編集においては、その端点の次にアンカー点を打ったときに、その端点と新しい端点とを結ぶ曲線の曲がり具合に影響します。描画側から見たら「まだ存在しない曲線の属性なんて知らん」ですが、編集側から見たら「いやいや、線がその端点を通過したときの出て行く先を示すんだからその端点の属性だろ」というわけです。というわけで、編集用の内部表現をd属性へ変換するとそのハンドルは失われます。まぁ、独自の属性に持たせるといった方法もありますが。

新しい構造で表現できないもの

外→内で失うものとしては、各コマンドの細かいニュアンスだと思います。

SVGのパスデータには沢山のコマンドが用意されています。

M m Z z L l H h V v C c S s Q q T t A a

これだけのコマンドがあります(Paths ― SVG 2を参照のこと)。

これだけあると同じ形を描画するのにも沢山の表現方法があります。これらのコマンドの使い分けは、ほとんどの場合データサイズを削減することが目的だと思われますが、誰かがそこにそれ以外の意図を込めていないと言い切れるでしょうか。相対表現(小文字)は前の点からの相対関係を維持してほしいという意図があったり、水平線や垂直線はその性質を維持してほしいと考えてはいないでしょうか。Aコマンドは特に意図が現れやすいです。しかし内部表現に変換すれば、それは全て無味乾燥な三次ベジェ曲線のアンカーとハンドルに集約されてしまいます。

私が一番頭を悩ませていたのは一つのMコマンドが複数のサブパスで共有されうることです。例えば次のようなd属性があった場合:

M0,0 L40,-20 L40,20 Z L20,40 L-20,40 Z L-40,20 L-40,-20 Z L0,-40

(ちなみにこれは分かりやすくするためにあえて無駄な書き方をしていますが、実際には次のように書けます)

M0 0 40-20V20ZL20 40H-20ZL-40 20V-20ZV-40
図3: 一つのMコマンドが複数のサブパスで共有されている例

これは上のような図形ですが、中央の点、つまり0,0の表記はd属性中に一つしか現れていません。このd属性の中には4つのサブパスが含まれています。しかしその開始点は最初に現れる M0,0 ただ一つにまとめられています。

これは単なるケチ表現なのかもしれません。しかし同じ点になっていることには何か必然的な理由があるのかもしれません。その点をドラッグしたとき、4つ全てのサブパスの開始点が動いた方が親切かもしれません。

まぁ、そんなことを全てのコマンドに対してやっていたら大変なので諦めることにしたわけです。

そして今

今では上のようなデータも正しく編集できるようになりました。もちろんバラバラの4つのサブパスとしてです。

私が間違った設計判断をしてしまった原因はこの割り切りをためらったからかもしれません。SVGパスデータの元々の表現の性質をできるだけ残しておきたかったわけです。しかしすでに相対表現やら二次ベジェ、水平線、垂直線などは絶対表現のLとCに変換してしまっていましたから、今更なわけですが。

実はこの問題は作り始めのかなり初期から気がついていました。でも頑張れば何とかなるだろうと思っていたわけです。

私は近年山を歩くことがありますが、登山道を歩いていると不意に道がおかしいな? と気がつくことがあります。妙に道が荒れている、障害となる草木や岩石が多い、越えられないことはないが一般登山道のレベルとは思えない、など。もちろんそこまで至るまでには「分岐など見当たらなかった」「正しい道を進んでいる」と思っているものです。しかしそういった異変に気がついたら地図を確認してすぐに引き返すことです。頑張れば行ける。そう思って先に行くと取り返しの付かないことになるかもしれません。

2024-03-23

Emacs Lispで文字列内の特定の位置が正規表現にマッチしているか判定する

Emacs Lispで、文字列の中の特定の位置が正規表現とマッチしているか判定するにはどうしたらよいでしょうか。

例えば "{ name: 'Taro' }" という文字列があったとして、3文字目の位置が正規表現 "\\([a-z]+\\)" にマッチしているか判定するにはどうしたら良いでしょうか(もちろんこの文字列や位置は色々と変わるものとします)。

Emacs Lispの正規表現マッチングの関数には大きく分けてバッファ用と文字列用があります。POSIX版ではない標準的なマッチング関数だと次のものがあります(Emacs 29.2時点でのRegexp Search (GNU Emacs Lisp Reference Manual)より):

  • バッファ用
    • re-search-forward
    • re-search-backward
    • looking-at
    • looking-at-p
    • looking-back
  • 文字列用
    • string-match
    • string-match-p

バッファ上のテキストであれば、現在のポイントから続くテキストが正規表現とマッチしているかを判定するにはlooking-atやlooking-at-pが使えます。他にも正規表現にポイントの位置とマッチするバックスラッシュ記法 \= があるので、それを使って (re-search-forward "\\=[a-z]+") などと書くことも出来ます(計測してみるとre-search-forwardの方が若干遅いようです)。

しかしながら文字列版の方にはそのような関数がありません。string-matchは文字列版のre-search-forwardです。検索を開始する位置こそ指定出来ますが、末尾までの間に正規表現がマッチする部分を探し、見つかったらその先頭位置を返します。例えば (string-match "\\([a-z]+\\)" "{ },{name: 'Taro' }" 2) を評価したら、 },{ の部分を飛ばして6文字目にマッチしてしまうわけです。指定した位置そのものがマッチしているかを判定するようなstring-looking-atのような関数はありません。 \= もバッファのポイントに対するもので、文字列には効きません。文字列の先頭を示す \` は本当に文字列の先頭(index=0)にしかマッチしませんし、 ^ も文字列の先頭か行頭(\nの直後)にしかマッチしません。

Emacs Lispというのは基本的にはバッファ用の関数の方が充実していて文字列用の関数が貧弱な傾向にあるような気がします。

仕方ないのでこれまで私はどうしていたかというと、

(eq (string-match "\\([a-z]+\\)" text pos) pos)

のようにしてマッチした位置が検索を開始した位置と同じであることを確認したり、

(string-match "\\`\\([a-z]+\\)" (substring text pos))

substringを使って検索開始位置を文字列の先頭に持ってきた上で \\` を使うなどしていたわけです(実際には前者ばかりで後者はほとんどしていないと思います)。

後はまぁ、

(string-match (format "\\`.\\{%d\\}\\([a-z]+\\)" pos) text)

みたいな手はあるかもしれません。

しかし、最近edraw-dom-svg.elでstyle属性の解析をしていたときに次のようなコードを書きました。

(defconst edraw-css-re-token
  (concat
   edraw-css-re-comment "*"
   "\\(?:\\(" edraw-css-re-ws "\\)"
   "\\|\\(" edraw-css-re-string "\\)"  ;; " '
   "\\|\\(" edraw-css-re-hash "\\)"  ;; #
   "\\|\\(" edraw-css-re-at-keyword "\\)"  ;; @
   "\\|\\(" edraw-css-re-dimension "\\)"
   "\\|\\(" edraw-css-re-percentage "\\)"
   "\\|\\(" edraw-css-re-number "\\)"
   "\\|\\(" edraw-css-re-function "\\)"
   "\\|\\(" edraw-css-re-ident "\\)"
   "\\|\\(" "[]({}),:;[]" "\\)"
   "\\|\\(" "." "\\)" ;; delim
   "\\)"))

(defun edraw-css-token (str pos)
  (unless (eq (string-match edraw-css-re-token str pos) pos)
    (error "CSS Syntax Error: %s `%s'" pos str))
  (cond
   ((match-beginning 1) ... )
   ((match-beginning 2) ... )
   ((match-beginning 3) ... )
   ...))

そのときに、「あれ、これって最後に . が入ってるんだから(末尾以外)必ずposの位置でマッチするんじゃないの?」と思ったわけです。

正規表現の最後が . ではなく空文字列の "略\\|" で終わっていれば、本当に必ずposの位置でマッチすることになります。

なので、最初の問いの答えは、

(progn
  (string-match "\\([a-z]+\\)\\|" text pos)
  (match-beginning 1))

でいいじゃないかということになったわけです。要するに必ずマッチさせてしまうわけです。これなら末尾まで無駄な検索は起こりませんし、substringで新しい文字列を作る必要もありません(substringがCopy-on-Writeだったりはしませんよね?)。で、実際に肝心の部分がマッチしているかは (match-beginning 1) が非nil(この場合はpos)を返すかどうかで確かめればいいわけです。正規表現に括弧が無いなら (match-end 0) がpos(つまり (match-beginning 0))と同じかどうかで確認しても良いでしょう。

分かっている人から見ればなんだ当たり前じゃ無いか、こんなことが分からないなんてバカなんじゃないか? と思われるかもしれませんが、何だかキツネにつままれたような不思議な気分になってしまいました。

大丈夫ですよね? 一応計測もしていてパフォーマンスも悪くは無さそうです。

ちなみにEmacsの \| は左がダメだったら右を試すという意味です。実際の実装がどうなってるのかは知りませんので、左が優先されると言った方が良いでしょうか。どちらか長い方という意味ではないのでご注意ください。

ところでel-easydrawの方は現在インポートまわりの作業をしていて、dvisvgmやdot、Inkscapeが出力したSVGを取りこんで遊んだりしています。org-babelのような仕組みが出来ると良いのですが……。

2024-03-23 ,

org-elisp-linkでcl-defmethodへのリンクを書けるようにする

以前書いたorg-elisp-linkで、cl-defmethodで定義したメソッドへのリンクを書けるようにしました。

misohena/org-elisp-link: Org-mode Link Types for Emacs Lisp Elements

例えばlistを引数に取るseq-takeへのリンクは [[elisp-function:seq-take;method-args=(nil list t)]] のように書きます。

method-args= オプションの書式は ( qualifiers . specializers ) になります。 qualifiers はあまり指定されないのでnilの場合が多いかと思います。 specializers はcl-defmethodで指定する引数列の引数名を除いたものと考えれば良いでしょう。

qualifiers を使用する例としては、例えばelp.elの中にあるloadhist-unload-elementへのリンクなんてどうでしょう(lispディレクトリでgrepして探しました)。

(cl-defmethod loadhist-unload-element :extra "elp" :before ((x (head defun)))
  "Un-instrument before unloading a function."
  (elp-restore-function (cdr x)))

elp.elの中に上のような定義があるのですが、そこへのリンクは次のように書くことになります。

[[elisp-function:loadhist-unload-element;method-args=((:extra "elp" :before) (head defun));library=elp]]

実装はelisp-mode.elのxrefバックエンド、特にelisp--xref-find-definitionsあたりを利用しています。

xrefを使ってelispの関数やら変数やらの定義へジャンプするには、次のようにすればできます。

(let ((xref-backend-functions '(elisp--xref-backend))) ;; 強制的にelispバックエンドを使うようにする
  (xref-find-definitions "find-file"))

cl-defmethodによって複数の選択肢がある場合はxrefのメニューが出ます。

(let ((xref-backend-functions '(elisp--xref-backend)))
  (xref-find-definitions "seq-take"))

今回リンクの上でC-c C-o(org-open-at-point)したときはこの方法で定義位置へジャンプするようにしてみました。従来はこのような場合に必ずcl-defgenericの方へジャンプしてしまったり、それが無ければジャンプできなかったりしていました。

エクスポートの時はジャンプせずに定義の場所を取得する必要があります。

ジャンプせずに定義の候補を取得するには次のようにすればできます。

(elisp--xref-find-definitions 'seq-take)
(#s(xref-item
    #("(cl-defgeneric seq-take)" 1 14 (face font-lock-keyword-face) 15 23 (face font-lock-function-name-face))
    #s(xref-elisp-location
       seq-take
       cl-defgeneric "c:/...path-to-emacs.../share/emacs/29.2/lisp/emacs-lisp/seq.el"))
 #s(xref-item
    #("(cl-defmethod seq-take ((list list) n))" 1 13 (face font-lock-keyword-face) 14 22 (face font-lock-function-name-face))
    #s(xref-elisp-location
       (seq-take nil list t)
       cl-defmethod "c:/...path-to-emacs.../share/emacs/29.2/lisp/emacs-lisp/seq.el")))

結果はxref-itemというレコードになります。xref-itemはsummaryとlocationという二つの要素から成ります。

summaryの方は単なる文字列(テキストプロパティ付き)です。

locationの方は場所を特定するための情報で、elisp--xref-find-definitionsが返す場合はxref-elisp-locationというレコードになります。xref-elisp-locationはsymbol、type、fileから成ります。

試しにseq-takeの2番目の候補の場所を取得してみましょう。

(let ((loc (xref-item-location (nth 1 (elisp--xref-find-definitions 'seq-take)))))
  (list
   (xref-elisp-location-type loc)
   (xref-elisp-location-symbol loc)
   (xref-elisp-location-file loc)))
(cl-defmethod ; type
 (seq-take nil list t) ; symbol
 "c:/...path-to-emacs.../share/emacs/29.2/lisp/emacs-lisp/seq.el" ; file
 )

定義位置へジャンプするとき、これらの情報はそのままfind-function-search-for-symbolに引き渡されます。

typeの cl-defmethodfind-function-regexp-alistのキーです。このalistからcl--generic-search-method関数が求められ、symbolがそのcl--generic-search-method関数に引き渡されて実際の検索が行われます。symbolは (seq-take nil list t) なので、メソッド名が seq-take 、qualifier無し、引数の型がlistであるようなcl-defmethodが(re-search-forwardで)検索されます。

今回追加したmethod-args=オプションの形式は、このsymbolのメソッド名を除いた残りの部分と一致するようになっています。