Can a grandparent add itself to a son?

You discovered a bug in the engine, and you are sure that it is not a problem of your code? Just post it in here. Please read the bug posting guidelines first.
Post Reply
Mel
Competition winner
Posts: 2292
Joined: Wed May 07, 2008 11:40 am
Location: Granada, Spain

Can a grandparent add itself to a son?

Post by Mel »

Seems that currently the ISceneNode have a really weak form of cycle prevention (the scene manager handles the scene as a tree, so it is vital that the data structure remains a tree)

Supose for an ill programmed routine that a node A is attached to node B and that the node B is attached to node C, currently, it is possible to attach node A again to node C because the only check the scene nodes do is that the parent node of a given node isn't the one that is going to be inserted, how is prevented that A is attached to C? This could create a loop within the tree, and force a stack overflow because of the traversing routine, and end the program.

Shouldn't all the ancestors be checked first? eventhough it is a linear check, it is unlikely it lasts long so it could be worth, something like this:

Code: Select all

 
...
    //Preventing cycles in the tree, node is the node to be inserted, which we already checked is not null
    ISceneNode* ancestor = this; //We start by ourselves...
    while (ancestor != nullptr) //the root of the tree has no more ancestors, thus is safe to insert
        if (ancestor == node)
            return; //The node we want to insert is already one of our ancestors, prevent the insertion!
        else
            ancestor = ancestor->parent; //move up the hierarchy
...
//do something else, like inserting the node as a child of ours...
 
"There is nothing truly useless, it always serves as a bad example". Arthur A. Schmitt
CuteAlien
Admin
Posts: 9628
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: Can a grandparent add itself to a son?

Post by CuteAlien »

If you do that then the nodes fall out of the scenemanager (as that can no longer be parent then).
I guess one could make that error ... should we really check that? (we do a simple self-check so far)
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
MartinVee
Posts: 139
Joined: Tue Aug 02, 2016 3:38 pm
Location: Québec, Canada

Re: Can a grandparent add itself to a son?

Post by MartinVee »

I was under the impression that a node can have only a single parent as a time, and that calling addChild() removed the child node from it's previous parent. So, in your example (again, as I understand it) :

1) Node A is created and attached to a hypotetical Node X.
2) Node B is created and attached to Node A.
3) Node C is created and attached to Node B.
4) Node A is attached to Node C, thus detaching itself from the hypotetical Node X.

So you end up with two trees :

i) SceneManager -> NodeX;
ii) NodeC -> NodeA -> NodeB -> NodeC -> ...;

Your second tree is indeed circular, but since it's not attached to the SceneManager, it should never be traversed (unless you traverse it by hand). Trying to re-attach a circular tree a SceneManger's node will always end up breaking the circularity, so I think we're safe here.
devsh
Competition winner
Posts: 2057
Joined: Tue Dec 09, 2008 6:00 pm
Location: UK
Contact:

Re: Can a grandparent add itself to a son?

Post by devsh »

as long as there is absolutely no support for the scenemanager or root scene node being the child of anything... we're good
Mel
Competition winner
Posts: 2292
Joined: Wed May 07, 2008 11:40 am
Location: Granada, Spain

Re: Can a grandparent add itself to a son?

Post by Mel »

True, i didn't take into consideration that the parent nodes changed when inserted. My bad :)
"There is nothing truly useless, it always serves as a bad example". Arthur A. Schmitt
CuteAlien
Admin
Posts: 9628
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: Can a grandparent add itself to a son?

Post by CuteAlien »

Well, devsh mentioned one way to mess it up (you can probably do that by setting a parent for the rootscenenode).
But - it's kinda the stuff where users deliberately abuse the structures. It's the kind of stuff you really have to protect against in a user-application. But I don't think the library is the correct level to check for this (it also wouldn't be wrong to do that... gray area stuff... when in doubt I prefer to leave it out).
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Mel
Competition winner
Posts: 2292
Joined: Wed May 07, 2008 11:40 am
Location: Granada, Spain

Re: Can a grandparent add itself to a son?

Post by Mel »

At least, served to raise a bit of awareness :) Still, i don't like much leaving some nodes floating around just because they've gone cyclic
"There is nothing truly useless, it always serves as a bad example". Arthur A. Schmitt
Post Reply