annotate 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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
39af8ab46cbb (no commit message)
one
parents:
diff changeset
1 \section{マージ}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
2 REPでは、それぞれのエディタでのテキストへの編集を非同期に行うため、エディタ間で編集コマンドの衝突が起こることがある。
39af8ab46cbb (no commit message)
one
parents:
diff changeset
3
39af8ab46cbb (no commit message)
one
parents:
diff changeset
4 例えば、エディタAとエディタBでほぼ同時に同じテキストの同じ行を編集した場合、
39af8ab46cbb (no commit message)
one
parents:
diff changeset
5 2つのエディタ間で編集の順番が逆になってしまい、編集結果に差が出てしまう
39af8ab46cbb (no commit message)
one
parents:
diff changeset
6 (図\ref{fig:conflict3})。
39af8ab46cbb (no commit message)
one
parents:
diff changeset
7
39af8ab46cbb (no commit message)
one
parents:
diff changeset
8 \begin{figure}[htpb]
39af8ab46cbb (no commit message)
one
parents:
diff changeset
9 \begin{center}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
10 \includegraphics[scale=.4]{figure/conflict3.pdf}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
11 \end{center}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
12 \caption{コマンドの衝突}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
13 \label{fig:conflict3}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
14 \end{figure}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
15
39af8ab46cbb (no commit message)
one
parents:
diff changeset
16 このような編集コマンドの衝突による編集結果の不整合をマージにより修正する。
39af8ab46cbb (no commit message)
one
parents:
diff changeset
17
39af8ab46cbb (no commit message)
one
parents:
diff changeset
18 \subsection{Session Ring}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
19 実際にはエディタはSession Managerにスター型に接続されるが、同じSession内(同じテキストに対する編集を行っているエディタ同士)でのREPコマンドの送受信は仮想的なリングネットワークを構成し、このリング上をREPコマンドを1方向に送信する(図\ref{fig:new_merge})。これをSession Ringと呼ぶ。
39af8ab46cbb (no commit message)
one
parents:
diff changeset
20 テキスト編集をREPコマンドに変換し、このREPコマンドをリングネットワーク上に巡回させることにより、全てのエディタで起こった編集をREPコマンド列として、それぞれのエディタで収集する。
39af8ab46cbb (no commit message)
one
parents:
diff changeset
21 このSession Ringを用いると、全てのエディタで起こったテキスト編集の履歴をREPコマンド列としてそれぞれのエディタで蓄積できる。
39af8ab46cbb (no commit message)
one
parents:
diff changeset
22 この蓄積されたコマンド列を利用してマージを行う。
39af8ab46cbb (no commit message)
one
parents:
diff changeset
23
39af8ab46cbb (no commit message)
one
parents:
diff changeset
24 \begin{figure}[htpb]
39af8ab46cbb (no commit message)
one
parents:
diff changeset
25 \begin{center}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
26 \includegraphics[scale=.3]{figure/new_merge.pdf}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
27 \end{center}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
28 \caption{Session Ring上のREPコマンドの送信}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
29 \label{fig:new_merge}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
30 \end{figure}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
31
39af8ab46cbb (no commit message)
one
parents:
diff changeset
32 \subsection{マージアルゴリズム}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
33 それぞれのエディタに蓄積されたREPコマンド列は順番が異なる。図\ref{fig:new_merge}を例に見ると、Editor1ではeid=1,3,2の順に蓄積されているが、Editor2ではeid=2,1,3の順番である。
39af8ab46cbb (no commit message)
one
parents:
diff changeset
34 これをソートして順番を一致させてエディタへ反映すれば編集結果を一致させることができる。
39af8ab46cbb (no commit message)
one
parents:
diff changeset
35 しかしエディタには既に、それぞれのエディタ間で異なった順番でREPコマンドが反映されてしまっているので、エディタ側のテキストに対してUndoの処理を行う。
39af8ab46cbb (no commit message)
one
parents:
diff changeset
36 これにより、それぞれのエディタは、編集前の状態に戻り、テキストは一致している状態である。
39af8ab46cbb (no commit message)
one
parents:
diff changeset
37 その後、ソートされたREPコマンド列をテキストへ反映させ全てのテキストを一致させる。
2
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
38
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
39 Undoコマンドはエディタに蓄積されたREPコマンド列から生成する。
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
40 まず、このコマンド列を逆順にし、次に、insertコマンドはdeleteコマンドに、deleteコマンドはinsertコマンドに変換する(図\ref{fig:undo_command})。
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
41 この生成されたUndoコマンド列をテキストに反映させることでテキストの状態を編集前の状態に戻す。
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
42
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
43 \begin{figure}[htpb]
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
44 \begin{center}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
45 \includegraphics[scale=.3]{figure/undo_command.pdf}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
46 \end{center}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
47 \caption{Undoコマンドの生成}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
48 \label{fig:undo_command}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
49 \end{figure}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
50
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
51
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
52 次に、行番号とエディタ番号によってREPコマンド列をソートする。これによってそれぞれのエディタ間でのコマンド列の順序が一致する(図\ref{fig:sort_command})。
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
53 \begin{figure}[htpb]
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
54 \begin{center}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
55 \includegraphics[scale=.3]{figure/sort_command.pdf}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
56 \end{center}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
57 \caption{コマンド列のソート}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
58 \label{fig:sort_command}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
59 \end{figure}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
60
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
61 この、Undoコマンド列とソートコマンド列をそれぞれのエディタに反映することにより、テキストを一致させる。
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
62
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
63 マージを開始するタイミングは、エディタ自身が発行したREPコマンドがSession Ringを巡回して戻ってきたときである。
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
64 テキストへと編集が起こらずにコマンドを発行しなかった場合は、他のエディタから発行されるinsert\_ack、delete\_ackッコマンドを受け取った時にマージを開始する。
0
39af8ab46cbb (no commit message)
one
parents:
diff changeset
65
39af8ab46cbb (no commit message)
one
parents:
diff changeset
66
39af8ab46cbb (no commit message)
one
parents:
diff changeset
67 \subsection{マージ処理のSession Managerへの移行}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
68 マージの処理はこれまで、エディタ側で実装されていたが、マージはREP共通の処理であるため、それぞれのテキストエディタへ個別に実装するよりは、Session Managerへ実装する方が望ましいと考えた。
2
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
69 しかし、エディタとSession Managerとの間では非同期に通信を行っているため、マージコマンドとエディタコマンドとの間で衝突が起こってしまうことがある(図\ref{fig:remerge})。マージ中にエディタからの割り込みがあった場合である。
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
70 これを解決するため、マージコマンドとエディタコマンドとの間マージを行うリマージコマンドの生成を提案した。%(図\ref{fig:remerge})。
0
39af8ab46cbb (no commit message)
one
parents:
diff changeset
71
39af8ab46cbb (no commit message)
one
parents:
diff changeset
72 \begin{figure}[htpb]
39af8ab46cbb (no commit message)
one
parents:
diff changeset
73 \begin{center}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
74 \includegraphics[scale=.3]{figure/remerge.pdf}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
75 \end{center}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
76 \caption{リマージ}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
77 \label{fig:remerge}
39af8ab46cbb (no commit message)
one
parents:
diff changeset
78 \end{figure}
2
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
79
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
80 %リマージコマンドもマージコマンドと同様にUndoを行うが、コマンドのソートは行わずに、エディタからの割り込みのみを排除して、もう一度同様のマージコマンド列をテキストへ反映させる。
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
81 %その後、排除したエディタ割り込みコマンドをテキストへ反映させる。
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
82
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
83 まず、コマンドの割り込みがあったかどうかをチェックするために、マージャが受け取ったこまんどを確認する(表\ref{tab:received_command})。
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
84 この表では、マージコマンドをcomman1からcommand4とし、エディタからの割り込みコマンドをuser\_commandとしている。
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
85
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
86 \begin{table}[htdp]
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
87 \caption{received command}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
88 \begin{center}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
89 \begin{tabular}{|c|c|}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
90 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
91 1 & command1 \\
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
92 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
93 2 & command2 \\
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
94 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
95 3 & user\_command \\
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
96 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
97 4 & command3 \\
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
98 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
99 5 & command4 \\
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
100 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
101 \end{tabular}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
102 \end{center}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
103 \label{tab:received_command}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
104 \end{table}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
105
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
106 これにより、3番目に割り込みがあったことがわかるので、5、4、3番目をUndoする。そして、command3、command4、をもう一度redoして最後にuser\_commandを反映する。
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
107
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
108 \begin{table}[htdp]
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
109 \caption{remerge command}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
110 \begin{center}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
111 \begin{tabular}{|c|c|}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
112 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
113 1 & undo(command4) \\
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
114 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
115 2 & undo(command3) \\
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
116 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
117 3 & undo(user\_command) \\
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
118 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
119 4 & command3 \\
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
120 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
121 5 & command4 \\
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
122 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
123 6 & user\_command \\
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
124 \hline
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
125 \end{tabular}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
126 \end{center}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
127 \label{tab:remerge_command}
4742b1e4da3a modify merge,
one
parents: 0
diff changeset
128 \end{table}