Mercurial > hg > Papers > 2009 > pin-gn
view merger.tex @ 2:4742b1e4da3a default tip
modify merge,
and remove eclipse, debug
author | one |
---|---|
date | Thu, 19 Feb 2009 01:26:01 +0900 |
parents | 39af8ab46cbb |
children |
line wrap: on
line source
\section{マージ} REPでは、それぞれのエディタでのテキストへの編集を非同期に行うため、エディタ間で編集コマンドの衝突が起こることがある。 例えば、エディタAとエディタBでほぼ同時に同じテキストの同じ行を編集した場合、 2つのエディタ間で編集の順番が逆になってしまい、編集結果に差が出てしまう (図\ref{fig:conflict3})。 \begin{figure}[htpb] \begin{center} \includegraphics[scale=.4]{figure/conflict3.pdf} \end{center} \caption{コマンドの衝突} \label{fig:conflict3} \end{figure} このような編集コマンドの衝突による編集結果の不整合をマージにより修正する。 \subsection{Session Ring} 実際にはエディタはSession Managerにスター型に接続されるが、同じSession内(同じテキストに対する編集を行っているエディタ同士)でのREPコマンドの送受信は仮想的なリングネットワークを構成し、このリング上をREPコマンドを1方向に送信する(図\ref{fig:new_merge})。これをSession Ringと呼ぶ。 テキスト編集をREPコマンドに変換し、このREPコマンドをリングネットワーク上に巡回させることにより、全てのエディタで起こった編集をREPコマンド列として、それぞれのエディタで収集する。 このSession Ringを用いると、全てのエディタで起こったテキスト編集の履歴をREPコマンド列としてそれぞれのエディタで蓄積できる。 この蓄積されたコマンド列を利用してマージを行う。 \begin{figure}[htpb] \begin{center} \includegraphics[scale=.3]{figure/new_merge.pdf} \end{center} \caption{Session Ring上のREPコマンドの送信} \label{fig:new_merge} \end{figure} \subsection{マージアルゴリズム} それぞれのエディタに蓄積されたREPコマンド列は順番が異なる。図\ref{fig:new_merge}を例に見ると、Editor1ではeid=1,3,2の順に蓄積されているが、Editor2ではeid=2,1,3の順番である。 これをソートして順番を一致させてエディタへ反映すれば編集結果を一致させることができる。 しかしエディタには既に、それぞれのエディタ間で異なった順番でREPコマンドが反映されてしまっているので、エディタ側のテキストに対してUndoの処理を行う。 これにより、それぞれのエディタは、編集前の状態に戻り、テキストは一致している状態である。 その後、ソートされたREPコマンド列をテキストへ反映させ全てのテキストを一致させる。 Undoコマンドはエディタに蓄積されたREPコマンド列から生成する。 まず、このコマンド列を逆順にし、次に、insertコマンドはdeleteコマンドに、deleteコマンドはinsertコマンドに変換する(図\ref{fig:undo_command})。 この生成されたUndoコマンド列をテキストに反映させることでテキストの状態を編集前の状態に戻す。 \begin{figure}[htpb] \begin{center} \includegraphics[scale=.3]{figure/undo_command.pdf} \end{center} \caption{Undoコマンドの生成} \label{fig:undo_command} \end{figure} 次に、行番号とエディタ番号によってREPコマンド列をソートする。これによってそれぞれのエディタ間でのコマンド列の順序が一致する(図\ref{fig:sort_command})。 \begin{figure}[htpb] \begin{center} \includegraphics[scale=.3]{figure/sort_command.pdf} \end{center} \caption{コマンド列のソート} \label{fig:sort_command} \end{figure} この、Undoコマンド列とソートコマンド列をそれぞれのエディタに反映することにより、テキストを一致させる。 マージを開始するタイミングは、エディタ自身が発行したREPコマンドがSession Ringを巡回して戻ってきたときである。 テキストへと編集が起こらずにコマンドを発行しなかった場合は、他のエディタから発行されるinsert\_ack、delete\_ackッコマンドを受け取った時にマージを開始する。 \subsection{マージ処理のSession Managerへの移行} マージの処理はこれまで、エディタ側で実装されていたが、マージはREP共通の処理であるため、それぞれのテキストエディタへ個別に実装するよりは、Session Managerへ実装する方が望ましいと考えた。 しかし、エディタとSession Managerとの間では非同期に通信を行っているため、マージコマンドとエディタコマンドとの間で衝突が起こってしまうことがある(図\ref{fig:remerge})。マージ中にエディタからの割り込みがあった場合である。 これを解決するため、マージコマンドとエディタコマンドとの間マージを行うリマージコマンドの生成を提案した。%(図\ref{fig:remerge})。 \begin{figure}[htpb] \begin{center} \includegraphics[scale=.3]{figure/remerge.pdf} \end{center} \caption{リマージ} \label{fig:remerge} \end{figure} %リマージコマンドもマージコマンドと同様にUndoを行うが、コマンドのソートは行わずに、エディタからの割り込みのみを排除して、もう一度同様のマージコマンド列をテキストへ反映させる。 %その後、排除したエディタ割り込みコマンドをテキストへ反映させる。 まず、コマンドの割り込みがあったかどうかをチェックするために、マージャが受け取ったこまんどを確認する(表\ref{tab:received_command})。 この表では、マージコマンドをcomman1からcommand4とし、エディタからの割り込みコマンドをuser\_commandとしている。 \begin{table}[htdp] \caption{received command} \begin{center} \begin{tabular}{|c|c|} \hline 1 & command1 \\ \hline 2 & command2 \\ \hline 3 & user\_command \\ \hline 4 & command3 \\ \hline 5 & command4 \\ \hline \end{tabular} \end{center} \label{tab:received_command} \end{table} これにより、3番目に割り込みがあったことがわかるので、5、4、3番目をUndoする。そして、command3、command4、をもう一度redoして最後にuser\_commandを反映する。 \begin{table}[htdp] \caption{remerge command} \begin{center} \begin{tabular}{|c|c|} \hline 1 & undo(command4) \\ \hline 2 & undo(command3) \\ \hline 3 & undo(user\_command) \\ \hline 4 & command3 \\ \hline 5 & command4 \\ \hline 6 & user\_command \\ \hline \end{tabular} \end{center} \label{tab:remerge_command} \end{table}