[Bug c++/44172] New: Compiling never ends

[Bug c++/44172] New: Compiling never ends

[rmsalinas at uco dot es]

I was trying to create a tree. I have realized that the following code makes
the g++ compiler to never stop compilation.


#include <iostream>
#include <fstream>
#include <vector>
#include <cassert> 
using namespace std;

namespace gumocap{
namespace core{
namespace tree{
template<class T>
class Node: public  vector< Node<T>* > 
{

  public:
    /**
    */
    Node(){_parent=NULL;}
    /**
    */
    Node(const T& v,Node<T*> Tparent=NULL) {_parent=Tparent;_data=v;}
    /**
    */
    ~Node(){
      for(unsigned int i=0;i<this->size();i++) delete (*this)[i];
    }
    /**
    */
    Node(const Node &TN) {
        _parent=TN._parent;
        _data=TN._data;
         for(unsigned int i=0;i<TN.size();i++){
            Node<T> *n=new Node<T>( *TN[i]);
            n->parent=this;
         }
    }
    /**Adds a new child and returns it
    */
    Node<T> * addChild(T &val){
      Node<T>* n=new Node<T>(val,this);
      push_back(n);
      return n;
    }

    unsigned int getNChildren()const{
      unsigned int nChildren=0;
      for(unsigned int i=0;i<this->size();i++)
        nChildren+=(*this)[i].getNChildren();
      return nChildren+this->size();
    }

    /**
    */
    T&operator ()(){return _data;}
    /**
    */
    T&  getVal(){return _data;}
/**
    */
    bool isLeaf(){return this->size()==0;}
    /**
    */

    unsigned int getDepth()const{
      if (_parent==NULL) return  0;
      else return _parent->getDepth()+1;
    }
    /**
    */
    Node<T>* getParent() {return _parent;}
    /**
    */
    friend ostream & operator<<(ostream &str,const Node<T> &N)
    {
        unsigned int depth=N.getDepth();
        str<<"lll "<< "->"<<depth<<endl;
//      if (N.parent!=NULL)
            str<<"this ="<<&N<<" PARENT="<<N._parent<<endl;
        for(unsigned int i=0;i<depth;i++) str<<" ";
        str<<"( "<< N.size()<<" "<<N._data<<" ";

        for(unsigned int i=0;i<N.size();i++)
            str<< *N[i];

        for(unsigned int i=0;i<depth;i++) str<<" ";
        str<<" ) "<<endl;
        return str;
    }

    /**Saves in a binary streeam
    */
    void toStream(ostream &str)
    {
        int s=this->size();
        str.write((char*)&s,sizeof(int));
        for(unsigned int i=0;i<this->size();i++)
            (*this)[i]->toStream(str);
        str.write((char*)&_data,sizeof(T));
    }
    /**
    */
     void fromStream(istream &str)
    {
        int s;
        str.read((char*)&s,sizeof(int));
        this->resize(s);
        for(unsigned int i=0;i<this->size();i++){
            (*this)[i]=new Node<T>();
            (*this)[i]->parent=this;
            (*this)[i]->fromStream(str);
        }
        str.read((char*)&_data,sizeof(T));
    }    
  private:
  Node *_parent;
  T _data;

};  

template<class T>
class Iterator: public  vector< Node<T>* > 
{
  public:
    /**
    */
    Iterator(){ } 
    /**
    */
    Iterator(const Iterator &it): vector< Node<T>* > (it) {  }

    /**
    */
    T & operator()(unsigned int i){return (*this)[i]->getVal();}

};

/**\brief Simple tree
*/
template<class T>
class Tree
{
public:
  /**
  */
  Tree();

  /**
  */
  ~Tree();
  /**
  */
  Tree(const Tree &Tr);
  /**
  */
  Tree & operator =(const Tree &Tr);
  /**
  */
  Iterator<T> getIterator( )const;
  /**
  */
  Node<T>* setRoot(const T & v);
  /**
  */
  unsigned int  size()const;
  /**
  */
  void clear();
  /**
  */
  void toStream(ostream &str) 
  {
    if (_root==NULL){
      int w=0;
      str.write((char*)&w,sizeof(int));
    }
    else{
      int w=1;
      str.write((char*)&w,sizeof(int));
      _root->toStream(str);
    }
  }
  /**
  */
  void fromStream(istream &str) 
  {
    clear();
    int w=0;
    str.read((char*)&w,sizeof(int));
    if (w==1){
      _root=new Node<T>();
      _root->fromStream(str);
    }
  }
  /**
  */
    friend ostream & operator<<(ostream &str,const Tree &Tr)
    {

        if (Tr._root!=NULL) str<<" 1 "<< *(Tr._root)<<endl;
        else str<<" 0 "<<endl;
        return str;
    }
    /**
    */
    friend istream & operator>>(istream &str,Tree &Tr)
    {
        string parn;
        str>>parn;
        Tr.clear();
        if (parn=="1") str>>Tr;
        return str;
    }

  private:
  /**
  */
  Node<T> * _root;     
  void  getIteratorInDepth_subtree(Node<T> *n,Iterator<T> &It)const;
};

/**
*/
template<class T>
Tree<T>::Tree()
{
_root=NULL;
}

/**
*/
template<class T>
Tree<T>::~Tree()
{
  if (_root!=NULL) delete _root;
}
/**
*/
template<class T>
Tree<T>::Tree(const Tree &Tr)
{
  if (Tr._root!=NULL)  _root=new Node<T>( *Tr._root);
  else _root=NULL;
}

/**
*/
template<class T>
Tree<T> & Tree<T>::operator =(const Tree &Tr)
{
  clear();
  if (Tr._root!=NULL)
      _root=new Node<T>(*Tr._root);
  return *this;
}

/**
*/
template<class T>
Node<T> * Tree<T>::setRoot(const T & v)
{
  if (_root==NULL) _root=new Node<T>( v);
  else (*_root)()=v;
  return _root;
}

/**
*/
template<class T>
Iterator<T>  Tree<T>::getIterator(  )const
{
  Iterator<T> ret; 
  getIteratorInDepth_subtree(_root,ret);
  return ret;
} 
/**
*/
template<class T>
void   Tree<T>::getIteratorInDepth_subtree(Node<T> *n,Iterator<T> &It)const
{
  if( n==NULL) return;
  It.push_back(n);
  for(unsigned int i=0;i<n->size();i++)
      getIteratorInDepth_subtree( (*n)[i],It);
}
/**
*/
template<class T>
void   Tree<T>::clear()
{
 if (_root!=NULL) delete _root; 
 _root=NULL;
}

/**
*/
template<class T>
unsigned int  Tree<T>::size()const
{
  if (_root==NULL) return 0;
  else return _root->getNChildren()+1;      
}

};
};
};
using namespace gumocap::core::tree;
int main()
{
   gumocap::core::tree::Tree<int> T;
   Node<int> * _root=T.setRoot(10);
}


-- 
           Summary: Compiling never ends
           Product: gcc
           Version: 4.4.3
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rmsalinas at uco dot es
 GCC build triplet: i686
  GCC host triplet: i686
GCC target triplet: i686


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44172

[Bug c++/44172] Compiling never ends

[dougsemler at gmail dot com]

------- Comment #1 from dougsemler at gmail dot com  2010-05-17 17:46 -------
This is the offender:

Node(const T& v,Node<T*> Tparent=NULL) {_parent=Tparent;_data=v;}

It looks like you have transposed the *> (it should be the following, right?

Node(const T& v,Node<T>* Tparent=NULL) {_parent=Tparent;_data=v;}

Every iteration of this is producing a new template instantiation attempt
(recursively).


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44172

[Bug c++/44172] Compiling never ends

[rmsalinas at uco dot es]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 733 bytes --]



------- Comment #2 from rmsalinas at uco dot es  2010-05-17 17:50 -------
Subject: Re:  Compiling never ends

My god!  you work really fast!

Yes, I've found the error just few seconds ago.

Great work!

dougsemler at gmail dot com escribió:
> ------- Comment #1 from dougsemler at gmail dot com  2010-05-17 17:46 -------
> This is the offender:
>
> Node(const T& v,Node<T*> Tparent=NULL) {_parent=Tparent;_data=v;}
>
> It looks like you have transposed the *> (it should be the following, right?
>
> Node(const T& v,Node<T>* Tparent=NULL) {_parent=Tparent;_data=v;}
>
> Every iteration of this is producing a new template instantiation attempt
> (recursively).
>
>
>   


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44172

[Bug c++/44172] Compiling never ends

[paolo dot carlini at oracle dot com]

------- Comment #3 from paolo dot carlini at oracle dot com  2010-05-17 18:32 -------
Ok.


-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |INVALID


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44172

[Bug c++/44172] Compiling never ends

[pinskia at gcc dot gnu dot org]

------- Comment #4 from pinskia at gcc dot gnu dot org  2010-05-18 22:46 -------
Well I don't think we should cause an infinite loop on any input.  Note Comeau
C++ also causes an infinite loop.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |UNCONFIRMED
         Resolution|INVALID                     |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44172

[Bug c++/44172] Compiling never ends

[manu at gcc dot gnu dot org]

------- Comment #5 from manu at gcc dot gnu dot org  2010-06-04 16:11 -------
Please fellow GCC maintainers, after checking that a bug is indeed a bug,
please set the status to NEW. What more than 1000 unconfirmed reports!


-- 

manu at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |manu at gcc dot gnu dot org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2010-06-04 16:11:14
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44172

[Bug c++/44172] Compiling never ends

[steven at gcc dot gnu dot org]

------- Comment #6 from steven at gcc dot gnu dot org  2010-08-11 15:27 -------
I don't see how the compiler can know that this input causes an infinite loop.
This is just the halting problem. Not a bug in the sense that there is anything
to fix.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |WORKSFORME


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44172