C++ Segfault bei Rekursion

[n006]

Hallo,

ich komme einfach nicht mehr weiter, und hoffe auf eure Unterstützung.
Bei dem Programm handelt es sich um einen Entscheidungsbaumconsultierer.
Für Leute denen das nicht viel sagt: Ein Baum wird eingelesen und Testdaten werden anhand des Baumes ausgewertet. Evtl hat jemand die Muße Folgenden Code durchzusehen. Irgendwo bei der Erzeugung des Subbaums und dem rekursiven Aufruf muss sich ein Fehler eingeschlichen haben.

Was macht main()?
Main ließt zwei Dateien ein die Baumdatei und eine Datei mit zu testenden Instanzen. Beide Dateien sind zu 100% in Ordnung! Dannach wird die Klasse aus der Instanz ausgegeben (letzter Wert der Instanz bzw des instanzvektors). Nun wird durch eval eine Klasse ausgewertet und ebenfalls ausgegeben, um zu vergleichen wie gut der Baum klassifizieren kann.

int
main (int argc, char** argv)
{

	std::string fileName = argv[1];
	std::string treeFileName = "mvar." + fileName + ".tree";
	std::string instanceFileName = fileName + ".test";

	if (fileExists(treeFileName) && fileExists(instanceFileName))
	{

		// load tree
		std::vector<std::vector<std::string> > tree;
		std::ifstream treeFile (treeFileName.c_str());
		std::string str = "";

		while (getline(treeFile, str))
		{
			tree.push_back(stringSplit(str, ","));
		}
		treeFile.close();


		// load instances
		std::vector<std::vector<std::string> > instances;
		std::ifstream instancesFile (instanceFileName.c_str());
		str = "";

		while (getline(instancesFile, str))
		{
			instances.push_back(stringSplit(str, ","));
		}
		instancesFile.close();

		for (unsigned int i = 0; i < instances.size(); i++)
		{
			std::cout << "pol: " << instances[i][instances[i].size()-1];
			std::cout << " | eval: " << eval(&tree, &instances[i]) << std::endl;
		}

		std::cout << "All done!" << std::endl;

	}
	else
	{
		std::cout
			<< "At least one file (\"" << treeFileName << "\" or \""
			<< instanceFileName << "\") does not exist!" << std::endl;
	}

	return 0;
}

Bei der nun folgenden Datei handelt es sich um die besagte rekursive Funktion, die einen Fehler produziert, aber auch nur dann wenn ein neuer Teilbaum (hier subTree) erzeugt werden muss, also immer dann wenn sich die Funktion mit dem Subbaum selbst aufruft.

std::string
eval
(
	std::vector<std::vector<std::string> > *tree,
	std::vector<std::string> *instance
)
{

	for (unsigned int i = 0; i < tree->size(); i++)
	{

		if ((*tree)[i][0] != "|")
		{
			if ((*tree)[i][2] == "discrete")
			{
				// check if value correct (attribute test)
				if ((*tree)[i][3] == (*instance)[atoi((*tree)[i][1].c_str())])
				{
					// if leaf, return policy
					if ((*tree)[i].size() > 4)
					{
						std::cout << " : " << (*tree)[i][4].size() << std::endl;
						return (*tree)[i][4];
					}
					else if ((*tree)[i].size() > 5 || (*tree)[i].size() < 4)
					{
						return "01-Error!";
					}
					else
					{
						std::vector<std::vector<std::string> > subTree;
						++i;

						while (i < tree->size() && (*tree)[i][0] == "|")
						{
							std::vector<std::string> test = (*tree)[i];
							test.erase(test.begin());
							subTree.push_back(test);
							++i;
						}


						if (subTree.empty())
							return "02-Error!";
						else
							return eval(&subTree, instance);
					}
				}
			}
			else
                        	return "Error-00";
		}
	}
}

Ein(e) Baum(datei) sieht so aus:

BotNrOfRegisteredOpponents,16,discrete,0
|,DGIPlayerScore(1),24,discrete,0
|,|,BotInventoryAvailable(4),31,discrete,0
|,|,|,BotInventoryAvailable(8),35,discrete,0
|,|,|,|,DGIPlayerScore(2),25,discrete,0,584
|,|,|,|,DGIPlayerScore(2),25,discrete,1,358
|,|,|,BotInventoryAvailable(8),35,discrete,1,358
|,|,BotInventoryAvailable(4),31,discrete,1,966
|,DGIPlayerScore(1),24,discrete,1
|,|,BotInventoryAvailable(5),32,discrete,0,556
|,|,BotInventoryAvailable(5),32,discrete,1
|,|,|,BotStatus("UB-Karag"),82,multivariate,0,358
|,|,|,BotStatus("UB-Karag"),82,multivariate,1,584
|,|,|,BotStatus("UB-Karag"),82,multivariate,33,584
|,|,|,BotStatus("UB-Karag"),82,multivariate,49,210
|,|,|,BotStatus("UB-Karag"),82,multivariate,31459412,358
|,DGIPlayerScore(1),24,discrete,2,358
|,DGIPlayerScore(1),24,discrete,3,358
|,DGIPlayerScore(1),24,discrete,4,358
|,DGIPlayerScore(1),24,discrete,5,358
|,DGIPlayerScore(1),24,discrete,6,250
|,DGIPlayerScore(1),24,discrete,7,358
BotNrOfRegisteredOpponents,16,discrete,1,40

Zu 100% ausschließen kann ich, das der Fehler in einer der Hilfsfunktionen (die unterwegs auftauchen) liegt.

gdb scheint auch nicht allzusehr zu helfen:

#0  memcpy () at ../sysdeps/x86_64/memcpy.S:511
#1  0x00007ffff7b717be in std::string::_Rep::_M_clone(std::allocator<char> const&, unsigned long) () from /usr/lib/libstdc++.so.6
#2  0x00007ffff7b7204c in std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::string const&) () from /usr/lib/libstdc++.so.6
#3  0x0000000000401abf in eval (tree=0x7fffffffdce0, instance=0x742118) at consult.cpp:50
#4  0x00000000004025a4 in main (argc=2, argv=0x7fffffffe2e8) at consult.cpp:154

System:
Ubuntu 10.04 LTS 64bit
gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5)

Für jede Hilfe bin ich dankbar (schon Mal im Voraus)!

Grüße,
n006

P.S.:
Zum selber testen hier download.
2DO: make -> make run

 

[kuddlmuddl]

Ob das direkt der Fehler ist weiß ich nicht, aber mir fällt (negativ) auf, dass du in deinem 2ten Code-Schnipsel nicht unter allen umständen etwas returnst.
Dh falls "if ((*tree)[0] != "|")" nicht zutrifft gibts keinen else-Pfad der ein return enthält.
Sollte der Compiler da nicht warnen?

edit:
Evtl ist der Fall für die selbstverständlich ausgeschlossen, aber die for-Schleifen muss auch nicht zwangsläufig einmal durchlaufen werden - dh auch wenn du an der Stelle die ich oben erwähnt habe noch ein return ergänzt könnte nach dem for eins fehlen, falls "i < tree->size()" nie zutrifft. Also zB falls tree->size() == 0 ist.

 

[n006]

Er meckert leider nicht, nur das ich einer meiner Hilfsfunktionen mal ne deprected version einer typenumwandlung durchführe. -> unwichtig
Ich habe mal ein kleines Packet geschnürt, damit Ihr es schnell mal selber testen könnt. Hier der Link: http://you.ath.cx/download/consult.tar.bz2
2Do:
make
make run

Danke!

 

[kuddlmuddl]

Guck bitte nochmal mein edit an - es fehlen im prinzip 2 returns.
Ich würde (nur um ganz sicher zu gehen) an den beiden Stellen jeweils ein cout << "FEHLER_1\n"; bzw 2 ergänzen um zu sehen, ob sie evtl. doch mal eintreffen.
(hab hier nur win32xp)

 

[n006]

Falls dieser Fall eintritt (!="|"),
so soll eben weiter geschaut werden ohne etwas auszugeben.
Würde ich da bereits etwas ausgeben (siehe Baumtopologie), so würde niemals ein anderer Wert getestet, als der erste, außer natürlich im spezialfall, wo man nur blattknoten betrachtet.

 

[kuddlmuddl]

Ich hab mir ehrlich gesagt den Code an sich quasi nicht angeguckt aber habe eben diese 2 undefinierten Zustände gesehen. Im Prinzip isses das selbe wie bei:

int add(int a, int b) {
    if (a > 0 && b > 0) {
        return a+b;
    }
}

Rufe ich das nun auf mit -2, 3 (if trifft nicht zu) findet kein return statt, obwohl die Funktion eigtl ein int liefern muss

 

[antred]

Was ist zum Beispiel mit dieser Zeile hier:

while (i <= tree->size() && (*tree)[0] == "|")

Wenn tree->size() z.B. 3 liefert und du dann operator [] mit dem Index 3 verwendest, bist du schon 1 Element zu weit gegangen und langst irgend wo in den Wald hinein.

 

[n006]

Ich verstehe, was du meinst! Ich muss mir das an den beiden Stellen jetzt noch genauer anschauen, scheinen nun wirklich die einzigen "bösen" Stellen zu sein.
Danke dir auf jeden Fall schon mal!

Ergänzung (30. Juni 2011)

@antred: habe ich bereits geändert, gibt nur leider immernoch denselben Fehler aus. THX

 

[antred]

Vielleicht solltest du wenigsten zum Fehlerjagen alle operator [<index>]-Zugriffe durch .at(<index>) ersetzen. Dann bekommtst du sofort eine von std::exception abgeleitete Exception um die Ohren geschmissen, wenn du irgendwo einen ungültigen Index angibst.

 

[n006]

Also,
danke für eure Hilfe! Auch wenn es theoretischerweise, so nicht hätte sein dürfen, hatte kuddlmuddl recht (thx). Ich Falle nämlich bei dem Fall raus, wo die Werte verglichen werden (attribute test). Aus welchem Grund auch immer gibt es Werte in den Instanzen, die beim erlernen das Baumes nicht berücksichtigt wurden.

Danke nochmal an alle!
Jetzt habe ich eine neue Baustelle ;-)

 

[7H3 N4C3R]

Kompilier mal alles mit -g3 -O0 und wirf valgrind's memcheck mit --track-origins=yes drauf.

Falls du valgrind nicht kennst: www.valgrind.org
Entweder fix selbst bauen oder über den Paketmanager deiner Wahl installieren.

So lernst du auch noch direkt was.

Es gibt auch noch die Möglichkeit, über eine Hand voll die Defines die STL in einen netten Debugmodus zu versetzen. Müsste ich aber selbst erstmal was länger suchen, bis ich die wieder zusammen habe. Probier doch erstmal das und berichte mal Erfolg oder Misserfolg.