\section{ Protocol の構成}

ここでは、REPをSession manager(SM), Session manager接続プロトコル、
Session 接続プロトコル、Editor Command、Mergeプロトコル、
MergeのSession Managerへの移動の順に説明する。

\subsection{ Session managerの導入}

従来のREPはエディタ間を直接結んでいたが、その場合は相手の
エディタのホスト名やファイル名を直接入力する必要があった。
これは、ユーザに取って繁雑なだけでなく、個々のエディタでの
実装に複雑なUIを含める必要がある。

Session manager(SM)はエディタの動作するホストに一つあり、エディタ
は自動的に決まったポートを通してSMに接続(join/put)する。このようにすれば、
エディタ上でホスト名を入力する必要はない。一つのホスト上では、
単一のSMに複数のエディタが接続する。離れたホスト同士のエディタを
接続する場合は、まず、それぞれのホスト同士のSMを接続する。そして、
それぞれエディタがSMに接続した後で、ホスト間の接続を選択(select)する
(\figref{Session Managerの導入})。

\begin{figure}[tb]
  \begin{center}
    \includegraphics[width=12cm]{fig/one_session_manager.pdf}
    \caption{Session Managerの導入} 
    \label{Session Managerの導入}
  \end{center}
\end{figure}


\subsection{ Session managerの接続protocol}

SM同士の接続は、{\tt sm\_join}コマンドをSMに送ることによる
(\figref{Session Manager同士の接続})。
接続により、接続したSM間でuniqueな session manager id
が決められる。SM同士の接続は木構造(SM木)になるようになっており、
唯一のmaster SMが存在する。

同時に相互に{\tt sm\_join} 
が発行される場合もあるので、リングを避けるために、
{\tt sm\_join} はmaster SMまで転送される。自分自身に
{\tt sm\_join} が戻って来た場合は、その{\tt sm\_join} は
廃棄される。現在は、既にsession/editorを持つSMは、他のSMに
接続することは出来ない。

\begin{figure}[tb]
  \begin{center}
    \includegraphics[width=12cm]{fig/many_session_manager.pdf}
    \caption{Session Manager同士の接続}
    \label{Session Manager同士の接続}
  \end{center}
\end{figure}

\subsection{ Session 接続 protocol}

SMに接続したエディタは、自分の既にオープンしたファイルを持って接続する
{\tt put}と、他のエディタへ空のバッファを接続する{\tt join}の二種類の
接続を行なう。

接続が行なわれると、SMからeditor idをACKとして受け取る。editor idは、
session manager id (SM id)を含んでおり、全てのSM上でユニークとなる。

{\tt put}したファイルを持つエディタは、そのsessionのmasterとなる。
ファイルを共有するeditor群をsession と呼ぶ。session には、
SM id を含む session id が割り振られ、全てのSM上
でユニークとなる。

ユニークな SM id を使うので、editor id/sesison id はmaster SMに問い合わせる
ことなく生成が可能となる。

{\tt put}されたファイルはSM木を{\tt put｝コマンドで遡り、{\tt put\_ack}
によって、すべてのSMに通知される。このファイルの編集に参加したい場合は、
まず、Editorを空のバッファの状態でSMに{\tt join}コマンドで接続する。
すると、{\tt put}と同様に{\tt join}したEditorがすべてのSM上に通知される。
SMのGUI上の操作{\tt select}により、{\tt put}されたファイルと{\tt join}
したEditorが結びつけられる (\figref{join コマンド})。

\begin{figure}[tb]
  \begin{center}
    \includegraphics[width=12cm]{fig/sm_join.pdf}
    \caption{join コマンド}
    \label{join コマンド}
  \end{center}
\end{figure}


{\tt select}操作では、{\tt join}したEditorと{\tt put}したエディタを
探し出す必要がある。そのために、SM木上にSM同士に到達するための
routing tableを構築している。これは、{\tt sm\_join}時に作成される。
まず{\tt put}したEditorを探し、見つかったら{\tt select\_ack}を、
session ring を構築しながら{\tt join}したEditorを探す。見つかったら
{\tt join\_ack}がEditorに返される。
この時に、必要があれば、{\tt join}側、{\tt put}側の認証を行なう。

{\tt join}したエディタは空のバッファを持っているので、Session master
({\tt put}したEditor)に、必要な編集行を要求する{\tt sync}コマンドを
session ring に送る。Session master は、次のEditor Command を使って
必要な行を送信する (\figref{Session Managerを介したエディタの接続})。

\begin{figure}[tb]
  \begin{center}
    \includegraphics[width=12cm]{fig/use_case_put_join_over_sm.pdf}
    \caption{Session Managerを介したエディタの接続}
    \label{Session Managerを介したエディタの接続}
  \end{center}
\end{figure}

\subsection{ Editor Command}

Editorのコマンドは、すべて、{\tt insert},{\tt delete} に分解される。
SM上での混乱を避けるために、Editorが直接SMに送ったユーザが生成した
Editor Command {\tt user\_inert, user\_delete}と SM経由で送られた他のEditor Command は異なる
コマンドとして扱っている。

Editor は複数のsession を持つことも可能であるが、一つのEditor
が同じSessionに複数回{\tt join}すると、Editorの通信経路とEditor
id が対応しなくなる。問題はないが、実装はより複雑となる。

次のMerge Protocolでは、SM上でEditorのコマンドのundoを計算する
必要があるので、{\tt  user\_delete}には、削除した行の内容が
付加されてSMに送られる。したがって、{\tt  user\_delete}と
{\tt  user\_insert}と見掛け上対称となる。

全文置換なども{\tt user\_inert, user\_delete}に分解する必要が
あり、その分解はEditorによって行なわれる。REPは歴史的理由で行指向の
プロトコルであり、行指向でないEditorでも行番号を付加する
必要がある。

{\tt sync}に対しては、要求された行に対して、
{\tt delete, insert}を順に送ることで、{\tt join}したEditorに
行を転送する。特別なバッファ転送コマンドはない。

置換を特別扱いすることによるコマンド短縮の利点があるように
思えるが、SMではundoを生成する必要があるので、変更前の行と
変更後の行を送る必要があり、
{\tt delete, insert}を順に送る場合との差は無視できる。

\subsection{ Merge Protocol}

一つのSessionの上で、複数のEditorが同時に編集を行なった場合には、
その結果は、最終的に、Session 上で同じになる必要がある。

REPでは、二つのEditorの場合の編集の衝突の解決を行なう
手法を提案して来た。この方法(Merge Protocol (A))では自分のEditor Commandを
相手に送り、戻って来るまでのEditor Commandをキューに入れておく。
他のEditorのCommandを受け取った時には、その
キューと、そのCommandの可換性を調べて、キューを変更する\cite{kono04g}。
しかし、この方法は、三つ以上のEditorの場合はうまく動作しない。

そこで、以下のようなMerge Protocol (B)を導入する。(1) Editor Command
をSession Ring 上に流し、それが戻って来るまでに、他のEditorから
受け取った Editor Command をキューに入れておく。
(2) 戻って来たタイミングで、キュー上のEditor Commandを、eid とCommandの
順序を基にソートする。
(3) Editor Command がなくても、他のEditorからCommand を受け取ったら、
NOP Command を生成して、それが戻って来た時にソートを行なう。

\begin{figure}[tb]
  \begin{center}
    \includegraphics[width=12cm]{fig/new_merge.pdf}
    \caption{Session Ring上のREPコマンドの送信}
    \label{Session Ring上のREPコマンドの送信}
  \end{center}
\end{figure}

この手法では、EditorがN個あるSessionの場合、一つのEditor Commandに対して、N-1
個のNOP Command が生成される。

そこで、以下のようなMerge Protocol (C)を導入する。(1) Editor Command
をSession Ring 上に流し、それが戻って来るまでに、他のEditorから
受け取った Editor Command をキューに入れておく。
(2) 戻って来たタイミングで、キュー上のEditor Commandを、eid とCommandの
順序を基にソートする。
(3) 他のEditorにソートのタイミングを与えるために、Editor Command の
ack を、もう一周させる。
(4) 他のEditorのCommandを受け取ってから、ack が来るまでのCommandをキューに
入れておき、ack が来たら、eid とCommandの順序を基にソートする。

Editor には、ソートした編集結果になるように、それまで行なった編集をUndo
して、ソートした編集結果を適用する。

\subsection{ Merge のSession Managerへの移動}

Merge Protocol は、かなり複雑であり、すべてのEditor実装に対して
実装する必要がある。我々のターゲット(Vim, Emacs, Eclipse)は、
すべて異なる言語(C,Emacs Lisp,Java)で実装されており、そのすべてで、
複雑なプロトコルを実装するのは不可能ではないが、コストがかかる。

今回は、SMが一つのEditorに対して必ず存在するので、Merge Procotol
をSMに実装すると、SMの実装言語(Java)に実装するので十分になる。
しかし、Merge Protocol は編集バッファに対して複雑な操作をするので、
それをEditor Command を通して実装する必要がある。

まず、Editor Command がUndo(取消し)可能でなければならない。
このために、{\tt user\_delete} Command に削除した行の内容を
付加することにした。

次に、SMがMerge Protocolでソートした編集結果を適用した結果は、
(可能な最適化をした)Editor Command 列でEditorに反映する必要がある。
この時に、ユーザが編集コマンドを割り込ませる可能性がある。

これを防ぐ一つの方法は、Merge 作業が始まった段階で、ユーザ入力を
block してやれば良い(a)。もう一つの方法は、ユーザ入力の割り込みが
あった場合は、その入力込みで、もう一度、ソートを実行すれば良い(b)。
これはリマージと呼ばれる (\figref{リマージ})。

\begin{figure}[tb]
  \begin{center}
    \includegraphics[width=12cm]{fig/reMerge.pdf}
    \caption{リマージ}
    \label{リマージ}
  \end{center}
\end{figure}

Merge 作業中には、他のSM/Editorからの入力をblockすることは問題ない。
それは、もともと非同期で動作しており、遅延は許容されるように
なっている。

ユーザ入力のlock(a)は、エディタの実装に依存していて、実装はさまざまで
ある。また、REP設計の一つの目標であるlocalな編集を妨げないという
点では問題が残る。(b) は、Merge Protocol の実装が繁雑になるが、
ユーザの入力を妨げることはない。また、エディタのlockを実装しなくて
すむ。(a),(b)はお互いに干渉しないので、エディタのlockの実装は
REPを実装する時の選択肢の一つとなる。lock がある方が大量の変更(コピー
ペースト)がある場合にスムースな動作が期待できる。