Stackoverflow - warum?

[White_Fox]

Schönes Wochenende allerseits

Mein Test wirft ständig eine StackOverflow-Exception und ich verstehe nicht warum. Das hier ist der Stacktrace:

java.lang.StackOverflowError
at components.library.tree.TreeItem.getAddress(TreeItem.java:125)
at components.library.tree.TreeItem.getAddress(TreeItem.java:129)

Nun geht es um Folgendes: Ich möchte verschiedene Objekte in einer Baumstruktur halten. Der Plan: es sei eine abstrakte Klasse TreeItem, die alles mitbringt was nötig ist, um im Baum herumzunavigieren.
Jedes TreeItem habe eine einmalige UUID-Objektkonstante und kann beliebig viele Kind-Elemente vom Typ TreeItem halten, und jedes Kind-Element kennt sein Parent-Objekt.

Die Idee ist jetzt, das ich mit Hilfe einer Liste von UUIDs durch den Baum navigieren kann. Diese Liste versteckt sich hinter einem Address-Objekt. Ein Address-Objekt kann von jedem TreeItem direkt angefordert werden. Dazu fragt ein TreeItem seinen Parent nach einem Address-Objekt, der Parent fragt wiederum seinen Parent nach einem Address-Objekt, ... , und am Anfang des Baums stellt das Wurzel-TreeItem fest, daß es keinen Parent hat. Dann erstellt es ein neues Address-Objekt, trägt sich dort ein und gibt das Address-Objekt an seinen Aufrufer zurück, der Aufrufer trägt sich in die Address-Liste ein und gibt das Address-Objekt wieder an seinen Aufrufer weiter, ... bis das Baumelement erreicht ist, an dem die Aufruferkette begann.

Im Prinzip ein einfaches Dekoratormuster -> einige rekursive Aufrufe.

Das hier ist die Methode, in der die Exception kommt:

Address getAddress() {
        Address a;

        if (this.parent == null) {     //Zeile 125
            a = new Address(ME);   //ME: private final UUID ME;
        }
        else {
            a = this.parent.getAddress();     //Zeile 129
            a.addItemToPath(ME);
        }
        return a;
    }

Hat jemand eine Idee, warum es nach dem doch sehr kurzem Trace zu einer Exception kommt? Erkennt die JVM den rekursiven Aufruf automatisch und schiebt deshalb Panik?

 

[mihe7]

Erkennt die JVM den rekursiven Aufruf automatisch und schiebt deshalb Panik?

Nein, warum sollte sie? Allerdings sehe ich in dem Schnipsel auch nicht direkt ein Problem. Evtl. passiert was in addItemToPath oder parent wird nie null. Wirf mal den Debugger an oder füg mal ein paar Ausgaben hinzu.

 

[Thallius]

Ich würde mal sagen da ruft sich getAddress rekursiv unendlich oft auf weil parent immer != null ist

 

[Meniskusschaden]

weil parent immer != null ist

Daraus kann man aber nicht ableiten, dass parent.parent != null ist.

 

[White_Fox]

Hm...doch, Parent wird Null. Gelegentlich. Mit dem Debugger finde ich kein Problem. Allerdings kommt die Exception nur in einem Test vor: dem Test für die Methode addChild(). Wenn ich eine Textausgabe in die zwei If-Zweige setze, läuft der Speicher auch über, dann ist der Trace nur länger. Ich habe damit aber immerhin herausgefunden, daß der Fehler beim Aufruf von getAddress im Test stattfindet. Merkwürdig ist, daß diese Methode auch noch anderswo aufgerufen wird, dort kommt jedoch keine Exception.

Ich werf mal den Sourcecode und den Test der beiden Klassen TreeItem und Address hier rein. Vielleicht seht ihr ja was. Nebenbei: würdet ihr den Test auch so schreiben (z.B. das mit dem TestTreeItem, oder den TestTree, der mit der buildTree-Methode erstellt wird)? Oder würdet ihr das anders machen?

Spoiler

Code von Address:

package components.library.tree;

import java.util.ArrayList;
import java.util.UUID;

public class Address {
    
    private ArrayList<UUID> idPath;

    Address(UUID rootID) {
        this.idPath = new ArrayList<>();
        this.idPath.add(rootID);
    }

    /**
     * Adds the unique id from an TreeItem to the stack. The last
     * added item marks the addressed item, its parent has the
     * next-to-last added item, ...<p>
     * The method checks the resultig path for correctnes, including
     * that there is no doubled item. If the resulting tree path
     * would be uncorrect, the method returns false and will not
     * add the item to tree path.<p>
     * If the method returns true, adding the item UUID was successfull.
     *
     * @param item last item-UUID in queue.
     * @return true, if adding UUID to tree path was successfull,
     * false otherwise.
     */
    boolean addItemToEndOfPath(UUID item){
        if(idPath.contains(item)){
            return false;
        }
        else{
            idPath.add(item);
            return true;
        }
    }
    
    /**
     * Returns true, if the UUID in parameter is part of the tree path.
     * Fals otherwise.
     *
     * @param item the UUID to test.
     * @return true, if item is in path.
     */
    boolean IsInPath(UUID item){
        return idPath.contains(item)? true : false;
    }
    
    /**
     * Feed this method with an UUID, and it returns the UUID from
     * the next following child in tree, in direction from root
     * to destination. If there is no child, including cause the
     * param equals the destination or the UUID in parameter is not
     * part of the path, the method returns null.
     *
     * @param item is the parents UUID.
     * @return the UUID from child.
     */
    UUID getNext(UUID item){
        int i = 0;
        while (i < idPath.size() && !idPath.get(i).equals(item)) {           
            i++;
        }
        
        if(i >= idPath.size() - 1){return null;}
        
        return idPath.get(i + 1);
    }
    
    /**
     * Feed this method with an UUID, and it returns the UUID from
     * the parent in tree, in direction from root
     * to destination. If there is no parent, including cause the
     * param equals the destination or the UUID in parameter is not
     * part of the path, the method returns null.
     *
     * @param item
     * @return
     */
    UUID getBack(UUID item){
        int i = 0;
        while (i < idPath.size() && !idPath.get(i).equals(item)) {           
            i++;
        }
        
        if(i >= idPath.size() || i == 0){return null;}
        
        return idPath.get(i - 1);
        
    }
    
    /**
     * This method returns the last UUID in the path. In other words,
     * that means the UUID from the addressed tree item.
     *
     * @return the UUID from addressed tree item.
     */
    UUID getLast(){
        return idPath.get(idPath.size() - 1);
    }
}

Code von TreeItem:

import java.util.HashMap;
import java.util.UUID;

public abstract class TreeItem {

    private HashMap<UUID, TreeItem> children;
    private final UUID ME;
    private TreeItem parent;

    /**
     * This returns a new TreeItem-object which act as tree root. That
     * causes e.g. that an Address-request from a child stops at this
     * instance.
     */
    public TreeItem() {
        this.children = new HashMap<>();
        this.ME = UUID.randomUUID();
        this.parent = null;
    }

    /**
     * This returns a new TreeItem-object. Its neccessary to announce
     * a TreeItem instance as parent. For the case that parent is
     * null, the instance acts as tree root node. That causes e.g.
     * that an Address-request from a child stops at this instance.
     *
     * @param parent is the parent item in tree
     */
    public TreeItem(TreeItem parent) {
        this.children = new HashMap<>();
        this.ME = UUID.randomUUID();
        this.parent = parent;
    }

    /**
     * This method returns true, if the Addres-object points this
     * instance directly. That means, that the ID of this instance is
     * the last in ID-stack of the Address-object.<p>
     *
     * In any other case, including that this instance is anywhere or
     * not in address path, the method returns false.
     *
     * @param a is the Address-object to test.
     * @return true, if the Address-object points this instance.
     */
    private boolean itMeansMe(Address a) {
        return ME.equals(a.getLast());
    }

    /**
     * This method returns true, if this instance is the parent from
     * the addressed tree item. False otherwiese.
     *
     * @param is an Address-object.
     * @return true, if this instance is the parent from the addressed
     * object.
     */
    private boolean iAmTheParent(Address a) {
        UUID parent;

        parent = a.getBack(a.getLast());
        return parent.equals(ME);
    }

    /**
     * Set the value of parent.
     *
     * @param parent new value of parent.
     */
    void setParent(TreeItem parent) {
        this.parent = parent;
    }

    /**
     * Returns the unique id of this instance as UUID-object.
     *
     * @return the unique id.
     */
    UUID getID() {
        return this.ME;
    }

    /**
     * Returns the parent of the TreeItem-object. In case that there
     * is no parent, the method returns null.
     *
     * @return the parent TreeItem of this object.
     */
    TreeItem getParent() {
        return this.parent;
    }

    /**
     * With this method, the object can be informed that its parent
     * changed.
     *
     * @param newParent is the new parent TreeItem.
     */
    void changeParent(TreeItem newParent) {
        this.parent = newParent;
    }

    /**
     * This method returns the actual address of the object in the
     * item tree.
     *
     * @return the address of the tree item.
     */
    Address getAddress() {
        Address a;

        if (this.parent == null) {
            System.out.println("Parent ist Null");
            a = new Address(ME);
        }
        else {
            System.out.println("Parent ist nicht Null");
            a = this.parent.getAddress();
            a.addItemToEndOfPath(ME);
        }
        return a;
    }

    /**
     * This method returns the child, which is direct addressed by the
     * Address-object or which is the next item in the destination
     * path of the Address-object.<p>
     * In Case that there is no child according to the
     * Address-Parameter, the method returns null.
     *
     * @param a is the Address-object guiding through the tree
     * @return the child which lies in the Address-path
     */
    TreeItem getNext(Address a) {
        //I am part of address path?
        if (!a.IsInPath(ME)) {
            return null;
        }

        if (itMeansMe(a)) {
            return this;
        }
        else {
            return children.containsKey(a.getNext(ME))
                    ? children.get(a.getNext(ME))
                    : null;
        }
    }

    /**
     * This method adds a tree item to the tree, the parent is
     * specified by an Address-object. It returns false, if the
     * Address to parent is faulty, if the item is already added to
     * parent, or if adding goes wrong in an other way. It returns
     * true if adding was successfull.
     *
     * @param item is the new tree item.
     * @param parent is the parent of the new item.
     * @return true, if adding was successfull, false otherwise.
     */
    public boolean addChild(TreeItem item, Address parent) {
        //Check that this item is part of tree path.
        if (!parent.IsInPath(ME)) {
            return false;
        }

        //Check that item is not doubbled.
        if (children.containsKey(item.getID())) {
            return false;
        }

        if (itMeansMe(parent)) {
            children.put(item.getID(), item);
            item.changeParent(this);
        }
        else {
            children.get(parent.getNext(ME)).addChild(item, parent);
        }
        return true;
    }

    /**
     * This method removes a tree item from the tree. It needs an
     * Address-object which points the tree item to remove. If
     * removing fails in any case, e.g. faulty addressing, the method
     * returns null.
     *
     * @param item is the address of item to remove.
     * @return the removed item.
     */
    public TreeItem removeChild(Address item) {
        //Check that this item is part of tree path and that addressing is correct.
        if (!item.IsInPath(ME)
                || (!itMeansMe(item) && !children.containsKey(parent.getNext(item)))) {
            return null;
        }

        if (iAmTheParent(item)) {
            return children.remove(item.getNext(ME));
        }
        else {
            return children.get(item.getNext(ME)).removeChild(item);
        }
    }

    /**
     * This method returns a tree child. The tree child is defined by
     * an Address-object. If the child couldn't be found, the mehtod
     * returns null.
     *
     * @param a Address-object of returned child-element.
     * @return a child-element.
     */
    public TreeItem getChild(Address a) {
        //Check that this item is part of tree path and that addressing is correct.
        if (!a.IsInPath(ME)
                || (!itMeansMe(a) && !children.containsKey(parent.getNext(a)))) {
            return null;
        }

        if (iAmTheParent(a)) {
            return children.get(a.getNext(ME));
        }
        else {
            return children.get(a.getNext(ME)).getChild(a);
        }
    }
}

Test für TreeItem:

import org.junit.Test;
import static org.junit.Assert.*;

public class TreeItemTest {
    
    class TestTreeItem extends TreeItem{
        
        public TestTreeItem(TreeItem parent) {
            super(parent);
        }
        
        public TestTreeItem() {
            super();
        }
    }
    
    public TreeItemTest() {
    }

    TestTreeItem root;
    TestTreeItem item1_1, item1_2, item1_3;
    TestTreeItem item2_1, item2_2, item2_3;
    TestTreeItem item3_1, item3_2, item3_3;

    private void buildTree(){
        Address a;
        
        root = new TestTreeItem();
        
        item1_1 = new TestTreeItem();
        item1_2 = new TestTreeItem();
        item1_3 = new TestTreeItem();
        a = root.getAddress();
        root.addChild(item1_1, a);
        root.addChild(item1_2, a);
        root.addChild(item1_3, a);
        
        item2_1 = new TestTreeItem();
        item2_2 = new TestTreeItem();
        item2_3 = new TestTreeItem();
        a = item1_2.getAddress();
        item1_2.addChild(item2_1, a);
        item1_2.addChild(item2_2, a);
        item1_2.addChild(item2_3, a);
        
        item3_1 = new TestTreeItem();
        item3_2 = new TestTreeItem();
        item3_3 = new TestTreeItem();
        a = item2_2.getAddress();
        item2_2.addChild(item2_1, a);
        item2_2.addChild(item2_2, a);
        item2_2.addChild(item2_3, a);
    }

    /**
     * Test of setParent method, of class TreeItem.
     */
    @Test
    public void testSetParent() {
        TestTreeItem instance;
        TreeItem result, expResult;
        
        System.out.println("setParent");
        
        buildTree();
        instance = new TestTreeItem(root);

        instance.setParent(item3_2);
        expResult = item3_2;
        result = instance.getParent();
        
        assertEquals(expResult, result);
    }

    /**
     * Test of getParent method, of class TreeItem.
     */
    @Test
    public void testGetParent() {
        TestTreeItem instance;
        TreeItem result, expResult;
        
        System.out.println("getParent");
        
        buildTree();
        instance = new TestTreeItem(item2_2);
        expResult = item2_2;
        result = instance.getParent();
        
        assertEquals(expResult, result);
    }

    /**
     * Test of changeParent method, of class TreeItem.
     */
    @Test
    public void testChangeParent() {
        TestTreeItem instance;
        TreeItem result, expResult;
        
        System.out.println("changeParent");
        
        buildTree();
        instance = new TestTreeItem(root);
        
        expResult = item2_2;
        instance.changeParent(expResult);
        result = instance.getParent();
        
        assertEquals(expResult, result);
    }

//    /**
//     * Test of getAddress method, of class TreeItem.
//     */
//    @Test
//    public void testGetAddress() {
//        System.out.println("getAddress");
//        TreeItem instance = null;
//        Address expResult = null;
//        Address result = instance.getAddress();
//        assertEquals(expResult, result);
//        // TODO review the generated test code and remove the default call to fail.
//        fail("The test case is a prototype.");
//    }

    /**
     * Test of getNext method, of class TreeItem.
     */
    @Test
    public void testGetNext() {
        TestTreeItem instance;
        Address a;
        TreeItem result, expResult;
        
        System.out.println("getNext");
        
        buildTree();
        instance = item2_2;
        
        a = item3_2.getAddress();
        expResult = item3_2;
        result = instance.getNext(a);
        assertEquals(expResult, result);
        
        a = item1_3.getAddress();
        expResult = null;
        result = instance.getNext(a);
        assertEquals(expResult, result);
    }

    /**
     * Test of addChild method, of class TreeItem.
     */
    @Test
    public void testAddChild() {
        TestTreeItem instance;
        Address a;
        boolean result, expResult;
        
        System.out.println("addChild");
        
        buildTree();
        //Add instance to the tree
        instance = new TestTreeItem();
        
        a = item2_2.getAddress();             //Fehler tritt hier auf
        result = root.addChild(instance, a);
        expResult = true;
        assertEquals(expResult, result);
        
        root.removeChild(a);
        result = root.addChild(instance, a);
        expResult = false;
        assertEquals(expResult, result);
    }

    /**
     * Test of removeChild method, of class TreeItem.
     */
    @Test
    public void testRemoveChild() {
        Address a;
        TreeItem result, expResult;
        
        System.out.println("removeChild");
        
        buildTree();
        a = item3_2.getAddress();
        
        expResult = item3_2;
        result = root.removeChild(a);
        assertEquals(expResult, result);
        
        expResult = null;
        result = root.removeChild(a);
        assertEquals(expResult, result);
    }

    /**
     * Test of getChild method, of class TreeItem.
     */
    @Test
    public void testGetChild() {
        Address a;
        TreeItem result, expResult;
        
        System.out.println("getChild");
        
        buildTree();
        a = item3_2.getAddress();
        
        expResult = item3_2;
        result = root.getChild(a);
        assertEquals(expResult, result);
        
        root.removeChild(a);
        expResult = null;
        result = root.removeChild(a);
        assertEquals(expResult, result);
    }
}

 

[Meniskusschaden]

Ich glaube, du hast einen Zyklus im Baum. Das sieht verdächtig aus:

        a = item2_2.getAddress();
        item2_2.addChild(item2_1, a);
        item2_2.addChild(item2_2, a);

 

[White_Fox]

Ja, das war es tatsächlich gewesen. Schade daß ich es erst gestern abend gesehen/gelesen habe.
Vielen Dank.

 

[White_Fox]

Ich hätte mal noch eine Frage:

Ich will von den Daten, die ich im Baum halte, ein Modell ausgeben lassen. Das will ich nachher meiner View verfüttern, die View braucht aber keinen Zugriff auf die Daten, die der Baum enthält. Ein String und ein Addressobjekt je TreeItem reicht völlig aus.

Ich möchte den Tree aber auch mit einer TreeView anzeigen.

Hat jemand eine Idee, wie sich das am Besten bewerkstelligen läßt?