changeset 427:622a8e15ff40

Merge Worked ?
author one
date Sat, 02 Jan 2010 03:20:23 +0900
parents 1acc3dfde5d3
children b5f1bcc8a156
files Test.mf Todo build.xml rep/handler/Editor.java rep/handler/Translator.java test/sematest/TestEditor.java
diffstat 6 files changed, 126 insertions(+), 57 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Test.mf	Sat Jan 02 03:20:23 2010 +0900
@@ -0,0 +1,4 @@
+Manifest-Version: 1.0
+Created-By: 0.1.0 (Shinji KONO @ University of the Ryukyus)
+Main-Class: test.sematest.TestSessionManager
+
--- a/Todo	Fri Jan 01 00:06:23 2010 +0900
+++ b/Todo	Sat Jan 02 03:20:23 2010 +0900
@@ -1,3 +1,62 @@
+Sat Jan  2 00:02:41 JST 2010
+
+Todo:
+    writeLog に level/flag を付けるか?
+
+Selector.select() のフラグは意味がない。その後、必ず、
+selectedKeys() を調べる必要がある。これは、Simulator
+と実ソケットの動作が異なる部分。Warning とか出せないものか?
+
+確かに、Merge 変かも。unMerged を undo するのは良いが、
+sort するのは、unMerged であって、undo を付加したものではないはず。
+
+いや、それは正しく出来ている。output に先にundoを入れて、
+cmd には、そのまま残している。(順序は sort されるので関係ない)
+
+でも、sortedCmds1 に add する時に、Comparator で順序付けされて
+しまう。getPrecedence() は必要な列の切出しに使う。
+
+Self Merge case
+    E_{00} E_{12} E_{01} E_{23} E_{02} (E_{00})
+Other Merge case
+    E_{10} E_{11} E_{23} E_{01} E_{02} (Eack_{10})
+
+ack が間に入ることはない(merge で消されるから)
+original command の存在しない ack もない。
+    (あったら、エラー。無視して良い)
+ack の来ない original command は sequence エラーとなるなず。
+    (あるいは time out)
+
+ということは、getPrecedence せずに、うむを言わせず
+全部 sort すれば良いってこと? ってことは実は、E_{12}
+が来た段階で追い越せるかどうかはわかる?
+
+Ack を受け取ったら、それは、必ず先頭にあるはず。
+
+    E_{00} E_{10} E_{11} E_{23} E_{01} E_{02} (Eack_{10})
+
+とかはない。ack は追い越せないから。この間の入力は確定で、
+優先順位にしたがって順序付しsortする。次は、
+
+           E_{10} E_{11} E_{23} E_{01} E_{02} (Eack_{10})
+                  E_{11} E_{23} E_{01} E_{02} E_{12} (Eack_{11})
+
+で、これは、E_{12} までをsort すれば良い。ということは、
+取れるのは最初の一個だけってこと。
+
+nop の場合は、command が着いた直後に出力されるけど、
+ack の場合は、それは出力されないで、もう一周する
+ack が流される。ack は、一つ前のエディタが出力した
+nop に相当する。
+
+この方法だと、編集コマンドの干渉を気にする必要はない。それは、
+最適化フェーズで自動的に排除される。(はず) ということは、
+getPrecedece の方で sort してやって、今の lineno の比較は
+無意味なので排除ということですね。
+
+2方向をスター型/木型に順々に処理する方法でも良いのか。
+
+
 Wed Nov 26 15:15:16 JST 2008
 
 Ring 構造なので、一部のeidtorで止まると全体が止まってしまう。
--- a/build.xml	Fri Jan 01 00:06:23 2010 +0900
+++ b/build.xml	Sat Jan 02 03:20:23 2010 +0900
@@ -34,6 +34,11 @@
     <jar jarfile="${jar}" basedir="${classes}"  manifest="${src}/REPSessionManager.mf"></jar>
   </target>
 
+  <!-- test jarファイルの作成 -->
+  <target name="test-jar" depends="compile">
+    <jar jarfile="test.jar" basedir="${classes}"  manifest="${src}/Test.mf"></jar>
+  </target>
+
 
   <!-- コンパイル -->
   <target name="compile">
@@ -58,4 +63,4 @@
     <delete dir="${javadoc}" />
     <delete file="${jar}" />
   </target>
-</project>
\ No newline at end of file
+</project>
--- a/rep/handler/Editor.java	Fri Jan 01 00:06:23 2010 +0900
+++ b/rep/handler/Editor.java	Sat Jan 02 03:20:23 2010 +0900
@@ -39,6 +39,44 @@
 		translator = new Translator(eid,optimizer);
 	}
 	
+	/*
+	 *  Merge Protocol
+	(1) Editor CommandをSession Ring 上に流し、それが戻って来るまでに、他のEditorから
+	    受け取った Editor Command をキューに入れておく。
+	(2) 戻って来たタイミングで、キュー上のEditor Commandを、eid とCommandの
+	    順序を基にソートする。(self merge)
+	(3) 他のEditorにソートのタイミングを与えるために、Editor Command の
+	    ack を、もう一周させる。
+	(4) 他のEditorのCommandを受け取ってから、ack が来るまでのCommandをキューに
+		入れておき、ack が来たら、eid とCommandの順序を基にソートする。(other merge)
+
+		Editor には、ソートした編集結果になるように、それまで行なった編集をUndo
+		して、ソートした編集結果を適用する。Undo が無駄な動作をしないように最適化する。
+		
+		handle()   
+		   セッションの処理 
+		   manage()
+		       編集コマンドは translate() へ
+		       		一周して来た編集コマンドのACKは廃棄 (merge queue から削除)
+		          一周して来た自分のコマンドならself merge
+		       		他のエディタの編集コマンドのACK->other merge
+		       			それ以外は、そのまま実行、merge queue へ格納
+		          merge は checkReturnedCommand() から
+		             startMerge() へ 
+		        			まず、接続されている Editor に START_MERGE を送る
+		        			邪魔されないように、他のcommand は block する
+		   manager()		
+		      START_MERGE_ACK が来たら、translator.mergeAck() で教えて、
+		   		merge()->
+		   			translator.checkOwnCommand() へ 
+		   				ここで、sort されて、Merge Command をEditorへ送信 
+		   			checkEndMerge()から
+		   				endMerge() が呼ばれる。
+		   					自分のエディタにEND_MERGE で Merge終了を通知 
+		   					自分のコマンドは、ACKに変えて送信 (3)
+		   					それ以外は、そのまま送信 (一周させる)
+		       
+	 */
 
 	public void translate(REPCommand command){				
 		switch(command.cmd) {
@@ -217,7 +255,7 @@
 		// Session Manager 側で、このeditorへの他のeditorからの
 		// 入力を止めて、merge にそなえる。merge は、eidtor 側から
 		// ACKが来てから始まる。
-		translator.startMerge(cmd);
+		translator.startMerge(command);
 	}
 
 	@Override
@@ -360,6 +398,7 @@
 				+" from "+manager.editorList.editorByChannel(channel));
 		if (command.cmd==REP.SMCMD_JOIN||command.cmd==REP.SMCMD_PUT) {
 			// assert false;
+			// 一つのエディタ上に複数のセッションが作られた場合。
 			// 若干問題があるらしい
 			next = new Forwarder(manager,next.channel);
 			REPNode first = new FirstConnector(manager,channel);
--- a/rep/handler/Translator.java	Fri Jan 01 00:06:23 2010 +0900
+++ b/rep/handler/Translator.java	Sat Jan 02 03:20:23 2010 +0900
@@ -1,6 +1,5 @@
 package rep.handler;
 
-import java.util.Collection;
 import java.util.Comparator;
 import java.util.LinkedList;
 import java.util.List;
@@ -55,22 +54,18 @@
 	 * @param cmd
 	 */
 	public boolean catchOwnCommand(REPNode editor){
-		logger.writeLog("beforeMarge:"+unMergedCmds);
+		logger.writeLog("beforeMerge:"+unMergedCmds);
 		LinkedList<REPCommand> output = new LinkedList<REPCommand>();
-		LinkedList<REPCommand> cmds = new LinkedList<REPCommand>();
-				//スタック上にあるコマンドを全部undoコマンドにする
-		while ( !unMergedCmds.isEmpty() ){
-			REPCommand cmd0 = unMergedCmds.removeLast();
+		TreeSet<REPCommand> cmds = new TreeSet<REPCommand>(new REPCommandComparator());
+		// merge queue上にあるコマンドを全部undoコマンドするのと同時に
+		// sort したコマンド列を生成する
+		for( REPCommand cmd0 : unMergedCmds) {
 			output.add( createUndo(cmd0) );
 			cmds.add(cmd0);
 		}
-
-		/* 必要な分だけソートして返却用のリストに追加  */
-		output.addAll( sortCmds(cmds) );
-
-		/* 残ったコマンドも再び実行させるが、まだマージされてないのでunMergedにも入れる  */
 		output.addAll(cmds);
-		unMergedCmds.addAll(cmds);
+		// ACKが来たものは必ず先頭
+		unMergedCmds.removeFirst();
 		logger.writeLog("outputMerge:"+output);
 		logger.writeLog("afterMerge:"+unMergedCmds);
 		return optimizedSend(editor,output);
@@ -109,52 +104,15 @@
 	class REPCommandComparator implements Comparator<REPCommand>{
 
 		public int compare(REPCommand o1, REPCommand o2) {
-			
-			if ( o2.lineno > o1.lineno ) return 1;
-			else if ( o2.lineno < o1.lineno 
-					|| o2.eid > o1.eid )
-				return -1;
-
-			return 1;
+			if ( o1.eid<o2.eid ) return -1;
+			if ( o1.eid>o2.eid ) return 1;
+			if ( o1.seq<o2.seq ) return -1;
+			if ( o1.seq>o2.seq ) return 1;
+			assert(false);
+			return 0;
 		}
-		
 	}
 	
-	private Collection<REPCommand> sortCmds(LinkedList<REPCommand> cmds) {
-		TreeSet<REPCommand> sortedCmds1 = new TreeSet<REPCommand>(new REPCommandComparator());
-		int top;
-		int prevEid=-1;
-		while ( -1 != (top=getPrecedence(cmds, prevEid+1)) ){
-			REPCommand tmp = cmds.remove(top); 
-			sortedCmds1.add(tmp);
-			prevEid = tmp.eid;
-		}
-		
-		return sortedCmds1;
-	}
-
-	/* search cmd. ordering by  min EID that is lower lowEid and min SEQ.  */
-	private int getPrecedence(LinkedList<REPCommand> cmds, int lowEid) {
-		int cEid, cSeq;
-		cEid=cSeq=Integer.MAX_VALUE;
-		int ret=-1;
-		for (int i=0; i<cmds.size(); i++){
-			REPCommand c = cmds.get(i);
-			if ( c.eid<lowEid ) continue;
-			else if ( c.eid>cEid ) continue;
-			else if ( c.eid==cEid ) {
-				if ( c.seq>cSeq ) continue;
-				cSeq=c.seq;
-				ret = i;
-			} else { /* tmp.eid<cEid */
-				cEid = c.eid;
-				cSeq = c.seq;
-				ret = i;
-			}
-		}
-		return ret;
-	}
-
 	/**
 	 * Translate Command cmd that was received from SeMa.
 	 * @param cmd the command to be translated.
@@ -225,6 +183,7 @@
 	}
 
 	public void startMerge(REPCommand cmd) {
+		logger.writeLog("START MERGE command ="+cmd+" and top of unMergedCmds = "+ unMergedCmds.getFirst());
 		merge_mode = true;
 	}
 
--- a/test/sematest/TestEditor.java	Fri Jan 01 00:06:23 2010 +0900
+++ b/test/sematest/TestEditor.java	Sat Jan 02 03:20:23 2010 +0900
@@ -56,6 +56,7 @@
 		port = _port;
 		semaIP = new InetSocketAddress(_host, _port);
 		ns = REPLogger.singleton();
+		// ns.setLogLevel(10);
 		this.name = name;
 		cmds = cmdList;
 		if (master) {
@@ -284,10 +285,12 @@
 			// lock user input during merge (optional)
 			inputLock = hasInputLock;
 			cmd.cmd = REP.SMCMD_START_MERGE_ACK;
+			ns.writeLog("BeforeMerge "+text);
 			sendCommand(cmd);
 			break;
 		case SMCMD_END_MERGE :
 			inputLock = false;
+			ns.writeLog("AfterMerge "+text);
 			break;
 		case SMCMD_QUIT_2 :
 			if (cmd.eid!=eid) {