Commit: 8bbb7dd2cd5f95dcde868515c1d1ac76f8ec00cd - cit_bach (git)

Testcase generation tool for combinatorial interaction testing

Commit MetaInfo

• Revision: 8bbb7dd2cd5f95dcde868515c1d1ac76f8ec00cd (tree)
• Time: 2015-11-02 19:26:30
• Author: t-tutiya <tatsuhiro@ieee...>
• Commiter: t-tutiya

Log Message

Somewhat big changes are made. Now only the parameters involved in the
constraints are taken into account when building the BDD. This results
in a substantial reduction of computation time.
TO DO: The current version does not work when the constraints induce an
empty test space. This must be corrected soon.

Change Summary

• modified: inputsamples/ins10.txt
• modified: src/v1/ConstraintHandler.java
• modified: src/v1/Generator.java
• modified: src/v1/Main.java
• modified: src/v1/Node.java
• modified: src/v1/Parameter.java

Incremental Difference

--- a/inputsamples/ins10.txt
+++ b/inputsamples/ins10.txt
@@ -3,7 +3,7 @@
 OS (Windows7 Windows7_64 Vista) 
 メモリ (4.0 2 1 8 8.0 NA)
 SDD (4  2.0 2)
-# CPU ( Corei7  Corei5 Atom )
+CPU ( Corei7  Corei5 Atom )
 Disk (SDD HDD)
 Disk2 (SDD HDD)
 
@@ -16,7 +16,7 @@ Disk2 (SDD HDD)
 
 (<> [メモリ] 4.0)
 (<> [SDD] 4)
-(if (and (=== [メモリ] 8) (== [Disk] HDD) ) (or (== Vista [OS]) (<> [OS] Windows7) (<> [Disk] [Disk2]) ))
+# (if (and (=== [メモリ] 8) (== [Disk] HDD) ) (or (== Vista [OS]) (<> [OS] Windows7) (<> [Disk] [Disk2]) ))
 
 #(ite (== [Disk] [Disk2]) (== [メモリ] 4) (<> [メモリ] 2))
 

--- a/src/v1/ConstraintHandler.java
+++ b/src/v1/ConstraintHandler.java
@@ -40,7 +40,11 @@ class ConstraintHandler {
 		this.constrainedParameters = constrainedParameters;
 
 		// parameterのリスト
-		parameters = setBDDforParameter(parameterList);
+		PList constrainedParameterList = new PList();
+		for (Integer factor: constrainedParameters) {
+			constrainedParameterList.add(parameterList.get(factor));
+		}
+		parameters = setBDDforParameter(constrainedParameterList);
 
 		// contrainListから、ノードを呼ぶ
 		bddConstraint = setBddConstraint(constraintList);
@@ -140,7 +144,7 @@ class ConstraintHandler {
 		int f = bdd.getOne();
 		bdd.ref(f);
 
-		// パラメータでつかわない領域をfalseにする
+		// パラメータでつかわない値をとった場合にfalseとなるようにする
 		for (VariableAndBDD vb : parameters) {
 			int tmp = bdd.ref(bdd.and(f, vb.constraint));
 			bdd.deref(f);
@@ -148,63 +152,21 @@ class ConstraintHandler {
 		}
 
 		// 制約式の論理積をとる
-		for (Node n : constraintList) {
-			int g = n.evaluate(bdd, parameters);
-			int tmp = bdd.ref(bdd.and(f, g));
-			bdd.deref(f);
-			bdd.deref(g);
-			f = tmp;
-		}
-
-		// *を付加
-		f = extendBddConstraint(f);
-
-		return f;
-	}
-
-	
-	private int setBddConstraintNewBuggy(List<Node> constraintList) {
-		int f = bdd.getOne();
-		bdd.ref(f);
-
-		// 制約式の論理積をとる
-		for (Node n : constraintList) {
-			int g = n.evaluate(bdd, parameters);
+		for (Node n : constraintList) {		
+			int g = n.evaluate(bdd, parameters, constrainedParameters);
 			int tmp = bdd.ref(bdd.and(f, g));
 			bdd.deref(f);
 			bdd.deref(g);
 			f = tmp;
 		}
 
-		// パラメータでつかわない領域をfalseにする
-		int fordebug = 0;
-		for (VariableAndBDD vb : parameters) {
-			int cube = vb.var[0];
-			bdd.ref(cube);
-			for (int i = 1; i < vb.var.length; i++) {
-				int tmp = bdd.ref(bdd.and(cube, vb.var[i]));
-				bdd.deref(cube);
-				cube = tmp;
-			}
-			int tmp = bdd.ref(bdd.exists(f, cube));
-			// 制約に関係する場合のみ
-			if (tmp != f) {
-				fordebug++;
-				int tmp1 = bdd.ref(bdd.and(f, vb.constraint));
-				bdd.deref(f);
-				f = tmp1;
-			}
-			bdd.deref(cube);
-			bdd.deref(tmp);
-		}
-		System.out.println(fordebug);
 		// *を付加
 		f = extendBddConstraint(f);
 
 		return f;
 	}
 
-	
+		
 	private int extendBddConstraint(int constraint) {
 		int f = constraint;
 		for (VariableAndBDD p : parameters) {
@@ -229,7 +191,7 @@ class ConstraintHandler {
 	}
 
 	// テストケースが制約を満たすか
-	boolean isPossible(Testcase test) {
+	boolean isPossibleOld(Testcase test) {
 		int node = bddConstraint;
 		boolean[] bv = binarize(test);
 
@@ -248,6 +210,25 @@ class ConstraintHandler {
 		}
 	}
 
+	boolean isPossible(Testcase test) {
+		int node = bddConstraint;
+		boolean[] bv = binarizeReduced(test);
+
+		while (true) {
+			// 恒真，恒偽
+			if (node == 0)
+				return false;
+			else if (node == 1)
+				return true;
+
+			// このposの0, 1はノードなし
+			if (bv[bdd.getVar(node)] == true)
+				node = bdd.getHigh(node);
+			else
+				node = bdd.getLow(node);
+		}
+	}
+	
 	private boolean[] binarize(Testcase test) {
 		// assert(testcaseの長さ = parameterの数)
 		boolean[] res = new boolean[numOfBDDvariables];
@@ -271,10 +252,49 @@ class ConstraintHandler {
 			}
 			pos += p.var.length;
 		}
-		/*
-		 * this.print(); for (int k = 0; k < res.length; k++)
-		 * System.out.print(res[k] ? 1 : 0); System.out.println("<-");
+		
+		/* for debug
+		 for (int k = 0; k < res.length; k++)
+		 System.err.print(res[k] ? 1 : 0); System.err.println("<-");
+		 */
+		
+		return res;
+	}
+	
+	// TreeSet<Integer> constrainedParameters にあるparameterだけを2値化
+	private boolean[] binarizeReduced(Testcase test) {
+		boolean[] res = new boolean[numOfBDDvariables];
+		int pos = 0;
+		int i = 0;
+		for (Integer factor: constrainedParameters) {
+			// VariableAndBDD p = parameters.get(i); <- 
+			// parameters が relevantなものだけになれば，上記に変更
+			VariableAndBDD p = parameters.get(i);
+
+			int lv = test.get(factor);
+			if (lv < 0) {
+				for (int j = 0; j < p.var.length; j++) 
+					res[pos + j] = true;
+			} else {
+				int j0 = 0;
+				for (int j = p.var.length -1; j >=0; j--) {
+					if ((lv & (0x01 << j)) > 0) 
+						res[pos + j0] = true;
+					else
+						res[pos + j0] = false;
+					j0++;
+				}
+			}
+			pos += p.var.length;
+			i++;
+		}
+		
+		
+		/* for debug
+		 test.print(); for (int k = 0; k < res.length; k++)
+		 System.err.print(res[k] ? 1 : 0); System.err.println("<*");
 		 */
+		 
 		return res;
 	}
 }

--- a/src/v1/Generator.java
+++ b/src/v1/Generator.java
@@ -132,8 +132,9 @@ class Generator2 extends Generator {
 	 * Random(randomseed); }
 	 */
 
-//	final int NumOfIterationForEachTest = 20;
-	final int NumOfIterationForEachTest = 1;
+	// for regression testing  it should be reduced to 1
+	final int NumOfIterationForEachTest = 20;
+//	final int NumOfIterationForEachTest = 1;
 
 	Generator2(ParameterModel parametermodel, GList groupList,
 			ConstraintHandler constrainthandler, List<Testcase> seed,

--- a/src/v1/Main.java
+++ b/src/v1/Main.java
@@ -40,15 +40,17 @@ public class Main {
 			if (errorMessage != null)
 				Error.printError(errorMessage);
 
-			System.err.println("starting reading model");
 			// モデル読み込み
+			// System.err.println("starting reading model");
 			InputFileData inputfiledata = Inputer.readModel(modelFile);
 
-			System.err.println("starting building bdd");
 			// 制約処理 BDD作成
-// old version where all parameters are considered in BDD
+			// System.err.println("starting building bdd");
+			
+			// old version where all parameters are considered in BDD
 			//			ConstraintHandler conhndl = new ConstraintHandler(
-//					inputfiledata.parameterList, inputfiledata.constraintList);
+			//					inputfiledata.parameterList, inputfiledata.constraintList);
+
 			// newer version
 			ConstraintHandler conhndl = new ConstraintHandler(
 					inputfiledata.parameterList, inputfiledata.constraintList, inputfiledata.constrainedParameters);
@@ -58,8 +60,8 @@ public class Main {
 			// 　シード読み込み
 			List<Testcase> seed = Inputer.readSeed(seedFile, inputfiledata);
 
-			System.err.println("starting test suite construction");
 			// テストケース生成
+			// System.err.println("starting test suite construction");
 			List<Testcase> testSet = null;
 			if (strength == -1) {
 				// 全網羅

--- a/src/v1/Node.java
+++ b/src/v1/Node.java
@@ -6,6 +6,7 @@ import java.util.*;
 
 abstract class Node {
 	abstract int evaluate(BDD bdd, List<VariableAndBDD> parameters);
+	abstract int evaluate(BDD bdd, List<VariableAndBDD> parameters, Set<Integer> restricted);
 }
 
 abstract class BooleanOperator extends Node {
@@ -23,6 +24,14 @@ class NotOperator extends BooleanUnaryOperator {
 		bdd.deref(tmp);
 		return res;
 	}
+
+	int evaluate(BDD bdd, List<VariableAndBDD> parameters, Set<Integer> restricted) {
+		int tmp = Child.evaluate(bdd, parameters, restricted);
+		int res = bdd.not(tmp);
+		bdd.ref(res);
+		bdd.deref(tmp);
+		return res;
+	}
 }
 
 abstract class BooleanBinaryOperator extends BooleanOperator {
@@ -39,6 +48,16 @@ class IfOperator extends BooleanBinaryOperator {
 		bdd.deref(f2);
 		return f;
 	}
+
+	int evaluate(BDD bdd, List<VariableAndBDD> parameters, Set<Integer> restricted) {
+		int f1 = Left.evaluate(bdd, parameters, restricted);
+		int f2 = Right.evaluate(bdd, parameters, restricted);
+		int f = bdd.imp(f1, f2);
+		bdd.ref(f);
+		bdd.deref(f1);
+		bdd.deref(f2);
+		return f;
+	}
 }
 
 class EqualityOperator extends BooleanBinaryOperator {
@@ -51,6 +70,16 @@ class EqualityOperator extends BooleanBinaryOperator {
 		bdd.deref(f2);
 		return f;
 	}
+	
+	int evaluate(BDD bdd, List<VariableAndBDD> parameters, Set<Integer> restricted) {
+		int f1 = Left.evaluate(bdd, parameters, restricted);
+		int f2 = Right.evaluate(bdd, parameters, restricted);
+		int f = bdd.not(bdd.xor(f1, f2));
+		bdd.ref(f);
+		bdd.deref(f1);
+		bdd.deref(f2);
+		return f;
+	}
 }
 
 class InequalityOperator extends BooleanBinaryOperator {
@@ -63,6 +92,16 @@ class InequalityOperator extends BooleanBinaryOperator {
 		bdd.deref(f2);
 		return f;
 	}
+
+	int evaluate(BDD bdd, List<VariableAndBDD> parameters, Set<Integer> restricted) {
+		int f1 = Left.evaluate(bdd, parameters, restricted);
+		int f2 = Right.evaluate(bdd, parameters, restricted);
+		int f = bdd.xor(f1, f2);
+		bdd.ref(f);
+		bdd.deref(f1);
+		bdd.deref(f2);
+		return f;
+	}
 }
 
 abstract class BooleanTrinaryOperator extends BooleanOperator {
@@ -81,6 +120,18 @@ class IfthenelseOperator extends BooleanTrinaryOperator {
 		bdd.deref(f3);
 		return f;
 	}
+
+	int evaluate(BDD bdd, List<VariableAndBDD> parameters, Set<Integer> restricted) {
+		int f1 = Left.evaluate(bdd, parameters, restricted);
+		int f2 = Middle.evaluate(bdd, parameters, restricted);
+		int f3 = Right.evaluate(bdd, parameters, restricted);
+		int f = bdd.ite(f1, f2, f3);
+		bdd.ref(f);
+		bdd.deref(f1);
+		bdd.deref(f2);
+		bdd.deref(f3);
+		return f;
+	}
 }
 
 abstract class BooleanMultinaryOperator extends BooleanOperator {
@@ -107,6 +158,25 @@ class OrOperator extends BooleanMultinaryOperator {
 		}
 		return f;
 	}
+	
+	int evaluate(BDD bdd, List<VariableAndBDD> parameters, Set<Integer> restricted) {
+		int f1 = ChildList.get(0).evaluate(bdd, parameters, restricted);
+		int f2 = ChildList.get(1).evaluate(bdd, parameters, restricted);
+		int f = bdd.or(f1, f2);
+		bdd.ref(f);
+		bdd.deref(f1);
+		bdd.deref(f2);
+
+		for (int i = 2; i < ChildList.size(); i++) {
+			f1 = f;
+			f2 = ChildList.get(i).evaluate(bdd, parameters, restricted);
+			f = bdd.or(f1, f2);
+			bdd.ref(f);
+			bdd.deref(f1);
+			bdd.deref(f2);
+		}
+		return f;
+	}
 }
 
 class AndOperator extends BooleanMultinaryOperator {
@@ -128,6 +198,25 @@ class AndOperator extends BooleanMultinaryOperator {
 		}
 		return f;
 	}
+	
+	int evaluate(BDD bdd, List<VariableAndBDD> parameters, Set<Integer> restricted) {
+		int f1 = ChildList.get(0).evaluate(bdd, parameters, restricted);
+		int f2 = ChildList.get(1).evaluate(bdd, parameters, restricted);
+		int f = bdd.and(f1, f2);
+		bdd.ref(f);
+		bdd.deref(f1);
+		bdd.deref(f2);
+
+		for (int i = 2; i < ChildList.size(); i++) {
+			f1 = f;
+			f2 = ChildList.get(i).evaluate(bdd, parameters, restricted);
+			f = bdd.and(f1, f2);
+			bdd.ref(f);
+			bdd.deref(f1);
+			bdd.deref(f2);
+		}
+		return f;
+	}
 }
 
 abstract class AtomicExpression extends Node {
@@ -143,6 +232,13 @@ class TrueValue extends Constant {
 		bdd.ref(f);
 		return f;
 	}
+	
+	int evaluate(BDD bdd, List<VariableAndBDD> parameters, Set<Integer> restricted) {
+
+		int f = bdd.getOne();
+		bdd.ref(f);
+		return f;
+	}
 }
 
 class FalseValue extends Constant {
@@ -151,6 +247,12 @@ class FalseValue extends Constant {
 		bdd.ref(f);
 		return f;
 	}
+	
+	int evaluate(BDD bdd, List<VariableAndBDD> parameters, Set<Integer> restricted) {
+		int f = bdd.getZero();
+		bdd.ref(f);
+		return f;
+	}
 }
 
 abstract class ComparisonOfValueAndValue extends AtomicExpression {
@@ -178,6 +280,8 @@ class EqualityOfParameterAndValue extends ComparisonOfParameterAndValue {
 	int evaluate(BDD bdd, List<VariableAndBDD> parameters) {
 		int res = bdd.getOne();
 		bdd.ref(res);
+		// pは（絶対値で）パラメータの番号が既にはいっている
+		// 
 		int[] var = parameters.get(this.p).var;
 		for (int i = var.length - 1; i >= 0; i--) {
 			if ((this.v & (0x01 << i)) > 0) {
@@ -193,4 +297,32 @@ class EqualityOfParameterAndValue extends ComparisonOfParameterAndValue {
 		bdd.ref(res);
 		return res;
 	}
+	
+	
+	int evaluate(BDD bdd, List<VariableAndBDD> parameters, Set<Integer> restricted) {
+		int res = bdd.getOne();
+		bdd.ref(res);
+		// pは（絶対値で）パラメータの番号が既にはいっている
+		int num = 0;
+		for (Integer i: restricted) {
+			if (i == this.p) 
+				break;
+			num++;
+		}
+		
+		int[] var = parameters.get(num).var;
+		for (int i = var.length - 1; i >= 0; i--) {
+			if ((this.v & (0x01 << i)) > 0) {
+				int tmp = bdd.ref(bdd.and(res, var[i]));
+				bdd.deref(res);
+				res = tmp;
+			} else {
+				int tmp = bdd.ref(bdd.and(res, bdd.not(var[i])));
+				bdd.deref(res);
+				res = tmp;
+			}
+		}
+		bdd.ref(res);
+		return res;
+	}
 }
\ No newline at end of file

--- a/src/v1/Parameter.java
+++ b/src/v1/Parameter.java
@@ -104,6 +104,24 @@ class PList extends LinkedList<Parameter> {
 		}
 		throw new NoParameterNameException();
 	}
+	
+	// useless?
+	int getRestrictedID(String str, TreeSet<Integer> RestrictedParameters) 
+		throws NoParameterNameException {
+		try {
+			int parameter = this.getID(str);
+			int num = 0;
+			for (Integer i: RestrictedParameters) {
+				if (i == parameter)
+					return num;
+				num++;
+			}
+		} catch (NoParameterNameException e) {
+			throw e;
+		}
+		// if the parameter is not a relevant one
+		throw new NoParameterNameException();
+	}
 }
 
 class NoParameterNameException extends Exception {