Clone parent-child tree in PHP, start from child and avoid endless recursion

I have an object-oriented parent-child tree in PHP that I want to clone. The difficult part is that the access to the tree is not always through the root, but sometimes through a child of the root, like this:

[Root]
  -- [Element1] START CLONE
       -- [Element3]
       -- [Element4]
  -- [Element2]
       -- [Element5]

So what I want to do is to clone the entire tree, by calling $new = clone $element1;

The __clone() method states that each of the children must also be cloned, and, if the illustrated situation occurs*, also the parent must be cloned.

* Root is explicitly set as parent in Element1, so the system can identify this situation and do something with it.

The problem is that, starting the clone operation from Element1, Root must also be cloned. The cloning procedure for Root prescribes that all child elements must be cloned and therefore the clone operation for Element1 is called again, which then repeats the same cloning procedure, producing an endless loop.

Furthermore, the Root will not contain the first clone of Element1, but it will produce its own clone to add as a child. Element1 will then have Root as its parent, but Root will not have the same Element1 as a child.

I hope I presented the problem in a clear way and that someone can help me find a solution.

EDIT:

Final solution:

/**
 * The $replace and $with arguments allow a custom cloning procedure. Instead of
 * being cloned, the original child $replace will be replaced by $with.
 */
public function duplicate($replace = null, $with = null) {
    // Basic cloning
    $clone = clone $this;
    // If parent is set
    if(isset($this->parent)) {
        // Clone parent, replace this element by its clone
        $parentClone = $this->parent->duplicate($this, $clone);
        $clone->parent = $parentClone;
    }

    // Remove all children in the clone
    $clone->clear();

    // Add cloned children from original to clone
    foreach($this->getChildren() as $child) {
        if($child === $replace)
            // If cloning was initiated from this child, replace with given clone
            $childClone = $with;
        else
            // Else duplicate child normally
            $childClone = $child->duplicate();

        // Add cloned child to this clone
        $clone->add($childClone);
    }

    return $clone;
}

Solution

First of all, simplify your example:

[Root]
  -- [Element1] START CLONE
       -- [Element3]

Then differ between what you do, I think you have got three operations

public clone method.
A self-clone operation that returns a clone with children, but not the parent.
A single-clone operation that returns a clone w/o children.

Code outside of your classes is using the public clone method. But the __clone() method must not use that method, otherwise you run into the circular looping problem you've described. So the __clone() implementation must use other methods.

Add a cloneSelf and cloneSingle method to your class, make them protected, so inherited classes can call them but they are not publicly available.

Then make use of them in the __clone() implementation:

public function clone()
{
    // clone the parent
    $parent = $this->getParent();
    $parentClone = $parent->cloneSingle();

    // clone all children of parent which includes $this
    $selfClone = NULL;
    foreach($parent->getChildren() as $child)
    {
        $childClone = $child->cloneSelf();
        if (!$selfClone && $child === $this)
            $selfClone = $childClone;
        $parentClone->addChild($childClone);

    }

    assert('$selfClone');

    return $selfClone;
}

public function __clone()
{
    $message = 'Clone operator is not allowed, use clone() method instead.';
    throw new BadMethodCallException($message);
}

These methods will also help you to clone in case there is no parent.