[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