[Scummvm-cvs-logs] SF.net SVN: scummvm:[41819] tools/branches/gsoc2009-decompiler/decompiler

kjdf at users.sourceforge.net kjdf at users.sourceforge.net
Tue Jun 23 22:56:36 CEST 2009


Revision: 41819
          http://scummvm.svn.sourceforge.net/scummvm/?rev=41819&view=rev
Author:   kjdf
Date:     2009-06-23 20:56:36 +0000 (Tue, 23 Jun 2009)

Log Message:
-----------
decompiler: tests for collapsing

Modified Paths:
--------------
    tools/branches/gsoc2009-decompiler/decompiler/Makefile
    tools/branches/gsoc2009-decompiler/decompiler/graph.h
    tools/branches/gsoc2009-decompiler/decompiler/test/test_graph.h

Modified: tools/branches/gsoc2009-decompiler/decompiler/Makefile
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/Makefile	2009-06-23 20:56:20 UTC (rev 41818)
+++ tools/branches/gsoc2009-decompiler/decompiler/Makefile	2009-06-23 20:56:36 UTC (rev 41819)
@@ -68,7 +68,7 @@
 
 test:
 	cxxtest/cxxtestgen.pl --error-printer --abort-on-fail --have-eh -o test_runner.cpp test/test_graph.h
-	g++ -I. -Icxxtest -o test_runner test_runner.cpp
+	g++ -g -I. -Icxxtest -o test_runner test_runner.cpp
 	./test_runner
 
 

Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h	2009-06-23 20:56:20 UTC (rev 41818)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h	2009-06-23 20:56:36 UTC (rev 41819)
@@ -51,6 +51,10 @@
 		}
 	};
 
+	const std::list<Node*> &nodes() const {
+		return _nodes;
+	}
+
 	mutable std::list<Node*> _nodes;
 	Node *_entry;
 

Modified: tools/branches/gsoc2009-decompiler/decompiler/test/test_graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/test/test_graph.h	2009-06-23 20:56:20 UTC (rev 41818)
+++ tools/branches/gsoc2009-decompiler/decompiler/test/test_graph.h	2009-06-23 20:56:36 UTC (rev 41819)
@@ -1,9 +1,14 @@
 #include <cxxtest/TestSuite.h>
 #include <graph.h>
 
+#include <list>
 #include <vector>
 using namespace std;
 
+#include <boost/foreach.hpp>
+#ifndef foreach
+#define foreach BOOST_FOREACH
+#endif
 
 typedef Graph<int> IntGraph;
 typedef IntGraph::Node IntNode;
@@ -11,95 +16,171 @@
 
 class GraphTestSuite : public CxxTest::TestSuite {
 
+	IntGraph g1, g2, g3;
+
 public:
 
+	void setUp() {
+		g1 = makeGraph1();
+		g2 = makeGraph2();
+		g3 = makeGraph3();
+	}
+
 	void test_intervals() {
-		vector<IntNode*> nodes1;
-		IntGraph *g1 = makeGraph1(nodes1);
-		g1->intervals();
-		TS_ASSERT_EQUALS(nodes1[0]->interval()->_data, nodes1[0]->_data);
-		TS_ASSERT_EQUALS(nodes1[1]->interval()->_data, nodes1[1]->_data);
-		TS_ASSERT_EQUALS(nodes1[2]->interval()->_data, nodes1[1]->_data);
-		TS_ASSERT_EQUALS(nodes1[3]->interval()->_data, nodes1[1]->_data);
-		TS_ASSERT_EQUALS(nodes1[4]->interval()->_data, nodes1[1]->_data);
-		TS_ASSERT_EQUALS(nodes1[5]->interval()->_data, nodes1[1]->_data);
-		vector<IntNode*> nodes2;
-		IntGraph *g2 = makeGraph2(nodes2);
-		g2->intervals();
-		TS_ASSERT_EQUALS(nodes2[0]->interval()->_data, nodes2[0]->_data);
-		TS_ASSERT_EQUALS(nodes2[1]->interval()->_data, nodes2[0]->_data);
-		TS_ASSERT_EQUALS(nodes2[2]->interval()->_data, nodes2[0]->_data);
-		TS_ASSERT_EQUALS(nodes2[3]->interval()->_data, nodes2[0]->_data);
-		TS_ASSERT_EQUALS(nodes2[4]->interval()->_data, nodes2[0]->_data);
-		TS_ASSERT_EQUALS(nodes2[5]->interval()->_data, nodes2[5]->_data);
-		TS_ASSERT_EQUALS(nodes2[6]->interval()->_data, nodes2[5]->_data);
-		TS_ASSERT_EQUALS(nodes2[7]->interval()->_data, nodes2[5]->_data);
-		TS_ASSERT_EQUALS(nodes2[8]->interval()->_data, nodes2[5]->_data);
-		TS_ASSERT_EQUALS(nodes2[9]->interval()->_data, nodes2[5]->_data);
-		TS_ASSERT_EQUALS(nodes2[10]->interval()->_data, nodes2[5]->_data);
-		TS_ASSERT_EQUALS(nodes2[11]->interval()->_data, nodes2[5]->_data);
-		TS_ASSERT_EQUALS(nodes2[12]->interval()->_data, nodes2[12]->_data);
-		TS_ASSERT_EQUALS(nodes2[13]->interval()->_data, nodes2[12]->_data);
-		TS_ASSERT_EQUALS(nodes2[14]->interval()->_data, nodes2[12]->_data);
+		g1.intervals();
+		TS_ASSERT_EQUALS(findNode(g1, 1)->interval()->_data, findNode(g1, 1)->_data);
+		TS_ASSERT_EQUALS(findNode(g1, 2)->interval()->_data, findNode(g1, 2)->_data);
+		TS_ASSERT_EQUALS(findNode(g1, 3)->interval()->_data, findNode(g1, 2)->_data);
+		TS_ASSERT_EQUALS(findNode(g1, 4)->interval()->_data, findNode(g1, 2)->_data);
+		TS_ASSERT_EQUALS(findNode(g1, 5)->interval()->_data, findNode(g1, 2)->_data);
+		TS_ASSERT_EQUALS(findNode(g1, 6)->interval()->_data, findNode(g1, 2)->_data);
+		g2.intervals();
+		TS_ASSERT_EQUALS(findNode(g2, 1)->interval()->_data, findNode(g2, 1)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 2)->interval()->_data, findNode(g2, 1)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 3)->interval()->_data, findNode(g2, 1)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 4)->interval()->_data, findNode(g2, 1)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 5)->interval()->_data, findNode(g2, 1)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 6)->interval()->_data, findNode(g2, 6)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 7)->interval()->_data, findNode(g2, 6)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 8)->interval()->_data, findNode(g2, 6)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 9)->interval()->_data, findNode(g2, 6)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 10)->interval()->_data, findNode(g2, 6)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 11)->interval()->_data, findNode(g2, 6)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 12)->interval()->_data, findNode(g2, 6)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 13)->interval()->_data, findNode(g2, 13)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 14)->interval()->_data, findNode(g2, 13)->_data);
+		TS_ASSERT_EQUALS(findNode(g2, 15)->interval()->_data, findNode(g2, 13)->_data);
+		g3.intervals();
+		TS_ASSERT_EQUALS(findNode(g3, 1)->interval()->_data, findNode(g3, 1)->_data);
+		TS_ASSERT_EQUALS(findNode(g3, 2)->interval()->_data, findNode(g3, 2)->_data);
+		TS_ASSERT_EQUALS(findNode(g3, 3)->interval()->_data, findNode(g3, 3)->_data);
 	}
 
+	void test_derive() {
+		IntGraph g1d = g1.derive();
+		TS_ASSERT_EQUALS(g1d.nodes().size(), 2);
+		TS_ASSERT(findNode(g1d, 1));
+		TS_ASSERT(findNode(g1d, 2));
+		TS_ASSERT_EQUALS(outEdgesCount(g1d, 1), 1);
+		TS_ASSERT_EQUALS(outEdgesCount(g1d, 2), 1);
+		TS_ASSERT(pointsTo(g1d, 1, 2));
+		TS_ASSERT(pointsTo(g1d, 1, 2));
+		IntGraph g1dd = g1d.derive();
+		TS_ASSERT_EQUALS(g1dd.nodes().size(), 1);
+		TS_ASSERT(findNode(g1d, 1));
+		TS_ASSERT_EQUALS(outEdgesCount(g1dd, 1), 0);
+		IntGraph g2d = g2.derive();
+		TS_ASSERT_EQUALS(g2d.nodes().size(), 3);
+		TS_ASSERT(findNode(g2d, 1));
+		TS_ASSERT(findNode(g2d, 6));
+		TS_ASSERT(findNode(g2d, 13));
+		TS_ASSERT_EQUALS(outEdgesCount(g2d, 1), 1);
+		TS_ASSERT_EQUALS(outEdgesCount(g2d, 6), 1);
+		TS_ASSERT_EQUALS(outEdgesCount(g2d, 13), 1);
+		TS_ASSERT(pointsTo(g2d, 1, 6));
+		TS_ASSERT(pointsTo(g2d, 6, 13));
+		TS_ASSERT(pointsTo(g2d, 13, 6));
+		IntGraph g3d = g3.derive();
+		TS_ASSERT_EQUALS(g3d.nodes().size(), 3);
+		TS_ASSERT(findNode(g3d, 1));
+		TS_ASSERT(findNode(g3d, 2));
+		TS_ASSERT(findNode(g3d, 3));
+		TS_ASSERT_EQUALS(outEdgesCount(g3d, 1), 2);
+		TS_ASSERT_EQUALS(outEdgesCount(g3d, 2), 1);
+		TS_ASSERT_EQUALS(outEdgesCount(g3d, 3), 1);
+		TS_ASSERT(pointsTo(g3d, 1, 2));
+		TS_ASSERT(pointsTo(g3d, 1, 3));
+		TS_ASSERT(pointsTo(g3d, 2, 3));
+		TS_ASSERT(pointsTo(g3d, 3, 2));
+	}
+
 private:
 
-	IntGraph *makeGraph1(vector<IntNode*> &nodes) {
-    	IntGraph *g = new IntGraph;
-		nodes.push_back(g->addNode(0));
-		nodes.push_back(g->addNode(1));
-		nodes.push_back(g->addNode(2));
-		nodes.push_back(g->addNode(3));
-		nodes.push_back(g->addNode(4));
-		nodes.push_back(g->addNode(5));
-		g->addEdge(nodes[0], nodes[1]);
-		g->addEdge(nodes[1], nodes[2]);
-		g->addEdge(nodes[1], nodes[4]);
-		g->addEdge(nodes[2], nodes[3]);
-		g->addEdge(nodes[3], nodes[1]);
-		g->addEdge(nodes[4], nodes[0]);
-		g->addEdge(nodes[4], nodes[5]);
+	IntNode *findNode(IntGraph &g, int data) {
+		foreach (IntNode *u, g.nodes())
+			if (u->_data == data)
+				return u;
+		return 0;
+	}
+
+	int outEdgesCount(IntGraph &g, int data) {
+		return findNode(g, data)->out().size();
+	}
+
+	bool pointsTo(IntGraph &g, int dataFrom, int dataTo) {
+		foreach (IntNode *u, findNode(g, dataFrom)->out())
+			if (u->_data == dataTo)
+				return true;
+		return false;
+	}
+
+	IntGraph makeGraph1() {
+    	IntGraph g;;
+		g.addNode(1);
+		g.addNode(2);
+		g.addNode(3);
+		g.addNode(4);
+		g.addNode(5);
+		g.addNode(6);
+		g.addEdge(findNode(g, 1), findNode(g, 2));
+		g.addEdge(findNode(g, 2), findNode(g, 3));
+		g.addEdge(findNode(g, 2), findNode(g, 5));
+		g.addEdge(findNode(g, 3), findNode(g, 4));
+		g.addEdge(findNode(g, 4), findNode(g, 2));
+		g.addEdge(findNode(g, 5), findNode(g, 1));
+		g.addEdge(findNode(g, 5), findNode(g, 6));
 		return g;
 	}
 
-	IntGraph *makeGraph2(vector<IntNode*> &nodes) {
-		IntGraph *g = new IntGraph;
-		nodes.push_back(g->addNode(0));
-		nodes.push_back(g->addNode(1));
-		nodes.push_back(g->addNode(2));
-		nodes.push_back(g->addNode(3));
-		nodes.push_back(g->addNode(4));
-		nodes.push_back(g->addNode(5));
-		nodes.push_back(g->addNode(6));
-		nodes.push_back(g->addNode(7));
-		nodes.push_back(g->addNode(8));
-		nodes.push_back(g->addNode(9));
-		nodes.push_back(g->addNode(10));
-		nodes.push_back(g->addNode(11));
-		nodes.push_back(g->addNode(12));
-		nodes.push_back(g->addNode(13));
-		nodes.push_back(g->addNode(14));
-		g->addEdge(nodes[0], nodes[1]);
-		g->addEdge(nodes[0], nodes[4]);
-		g->addEdge(nodes[1], nodes[2]);
-		g->addEdge(nodes[1], nodes[3]);
-		g->addEdge(nodes[2], nodes[4]);
-		g->addEdge(nodes[3], nodes[4]);
-		g->addEdge(nodes[4], nodes[5]);
-		g->addEdge(nodes[5], nodes[6]);
-		g->addEdge(nodes[5], nodes[11]);
-		g->addEdge(nodes[6], nodes[7]);
-		g->addEdge(nodes[6], nodes[8]);
-		g->addEdge(nodes[7], nodes[8]);
-		g->addEdge(nodes[7], nodes[9]);
-		g->addEdge(nodes[8], nodes[9]);
-		g->addEdge(nodes[9], nodes[10]);
-		g->addEdge(nodes[11], nodes[12]);
-		g->addEdge(nodes[12], nodes[13]);
-		g->addEdge(nodes[13], nodes[12]);
-		g->addEdge(nodes[13], nodes[14]);
-		g->addEdge(nodes[14], nodes[5]);
+	IntGraph makeGraph2() {
+		IntGraph g;
+		g.addNode(1);
+		g.addNode(2);
+		g.addNode(3);
+		g.addNode(4);
+		g.addNode(5);
+		g.addNode(6);
+		g.addNode(7);
+		g.addNode(8);
+		g.addNode(9);
+		g.addNode(10);
+		g.addNode(11);
+		g.addNode(12);
+		g.addNode(13);
+		g.addNode(14);
+		g.addNode(15);
+		g.addEdge(findNode(g, 1), findNode(g, 2));
+		g.addEdge(findNode(g, 1), findNode(g, 5));
+		g.addEdge(findNode(g, 2), findNode(g, 3));
+		g.addEdge(findNode(g, 2), findNode(g, 4));
+		g.addEdge(findNode(g, 3), findNode(g, 5));
+		g.addEdge(findNode(g, 4), findNode(g, 5));
+		g.addEdge(findNode(g, 5), findNode(g, 6));
+		g.addEdge(findNode(g, 6), findNode(g, 7));
+		g.addEdge(findNode(g, 6), findNode(g, 12));
+		g.addEdge(findNode(g, 7), findNode(g, 8));
+		g.addEdge(findNode(g, 7), findNode(g, 9));
+		g.addEdge(findNode(g, 8), findNode(g, 9));
+		g.addEdge(findNode(g, 8), findNode(g, 10));
+		g.addEdge(findNode(g, 9), findNode(g, 10));
+		g.addEdge(findNode(g, 10), findNode(g, 11));
+		g.addEdge(findNode(g, 12), findNode(g, 13));
+		g.addEdge(findNode(g, 13), findNode(g, 14));
+		g.addEdge(findNode(g, 14), findNode(g, 13));
+		g.addEdge(findNode(g, 14), findNode(g, 15));
+		g.addEdge(findNode(g, 15), findNode(g, 6));
 		return g;
 	}
+
+	IntGraph makeGraph3() {
+		IntGraph g;
+		g.addNode(1);
+		g.addNode(2);
+		g.addNode(3);
+		g.addEdge(findNode(g, 1), findNode(g, 2));
+		g.addEdge(findNode(g, 1), findNode(g, 3));
+		g.addEdge(findNode(g, 2), findNode(g, 3));
+		g.addEdge(findNode(g, 3), findNode(g, 2));
+		return g;
+	}
 };


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.




More information about the Scummvm-git-logs mailing list