Internal error

[Franklin Chen <chen at gs204 dot sp dot cs dot cmu dot edu>]

76 ~/c++ chen@gs204$ c++ -O repmin.cc
repmin.cc: In function `const class Pair<Tree<Suspend<T> >,Suspend<B> > & replaceAndMin(const class Suspend<T> &, const class Tree<Suspend<B> > &)':
repmin.cc:179: Internal compiler error.
repmin.cc:179: Please submit a full bug report to `egcs-bugs@cygnus.com'.
77 ~/c++ chen@gs204$ uname -a
Linux gs204.sp.cs.cmu.edu 2.0.30 #1 Wed Jun 4 15:02:33 EDT 1997 i686 unknown
78 ~/c++ chen@gs204$ gcc -v
Reading specs from /usr/home/egcs/lib/gcc-lib/i686-pc-linux-gnulibc1/egcs-2.90.23/specs
gcc version egcs-2.90.23 980102 (egcs-1.0.1 release)


Files:

// Lazy tree replacement.

#include <iostream.h>

// Do not worry about leaked memory.
#if 0
#include <gc_cpp.h>
#endif


// Not yet ANSI
#if 0
#define mutable
#endif

template<class T>
inline const T&
min(const T& a, const T& b)
{
  return a < b ? a : b;
}

template<class A, class B>
class Pair
#if 0
: public gc
#endif
{
public:
  Pair(const A &first, const B &second)
      : aFirst(first), aSecond(second) {}

  const A &first() const {
    return aFirst;
  }
  const B &second() const {
    return aSecond;
  }
public:
  const A &aFirst;
  const B &aSecond;
};

template<class A, class B>
inline
const Pair<A, B> &
mkPair(const A &a, const B &b)
{
  return *new Pair<A, B>(a, b);
}


// Function returning T.
// Use NULL pointer to indicate value not yet forced.
template<class T>
class Function
#if 0
: public gc
#endif
{
public:
  typedef T ReturnType;

  virtual const ReturnType &operator()() const = 0;
};


// For simplicity, mandate use of function objects.  A better design
// might be to provide an abstract interface and implement it.
template<class T>
class Suspend
#if 0
: public gc
#endif
{
public:
  Suspend(const Function<T> &func)
      : aFunc(func), aValue(0) {}

  const T &force() const {
    if (aValue == 0) {
#ifdef mutable
      // Cast away const for now.
      ((Suspend<T>*)this)->aValue = &aFunc();
#else
      aValue = &aFunc();
#endif
    }
    return *aValue;
  }
private:
  const Function<T> &aFunc;
  mutable const T *aValue;
};


template<class T>
inline
const Suspend<T> &
mkSuspend(const Function<T> &f)
{
  return *new Suspend<T>(f);
}


// Done in a quick and dirty way, rather than clean algebraic or
// object-oriented way.
template<class T>
class Tree
#if 0
: public gc
#endif
{
public:
  enum Kind {
    LEAF,
    TREE
  };

  // Constructors.
  // Awful NULL initializations because of lack of union.
  Tree(const T &leaf)
      : aLeaf(&leaf), aLeft(0), aRight(0) {}
  Tree(const Tree<T> &left, const Tree<T> &right)
      : aLeaf(0), aLeft(&left), aRight(&right) {}

  // Accessors.
  Kind kind() const {
    return aLeaf != 0 ? LEAF : TREE;
  }
  const T &leaf() const {
    return *aLeaf;
  }
  const Tree<T>       &left() const {
    return *aLeft;
  }
  const Tree<T>       &right() const {
    return *aRight;
  }
private:
  // Should really be union.
  const T   *const aLeaf;
  const Tree<T>   *const aLeft;
  const Tree<T>   *const aRight;
};

template<class T>
inline
const Tree<T> &
mkLeaf(const T &leaf)
{
  return *new Tree<T>(leaf);
}

template<class T>
inline
const Tree<T> &
mkTree(const Tree<T> &left, const Tree<T> &right)
{
  return *new Tree<T>(left, right);
}



template<class A, class B>
const Pair<Tree<Suspend<A> >, Suspend<B> > &
replaceAndMin(const Suspend<A> &a, const Tree<Suspend<B> > &b)
{
  typedef Suspend<B> MySuspend;
  typedef Pair<Tree<Suspend<A> >, MySuspend> MyReturnType;

  switch (b.kind()) {
  case Tree<MySuspend>::LEAF:
    return mkPair(mkLeaf(a), b.leaf());
  case Tree<MySuspend>::TREE: {
    const MyReturnType &replaceLeft = replaceAndMin(a, b.left());
    const MyReturnType &replaceRight = replaceAndMin(a, b.right());

    class Foo : public Function<A> {
    public:
      Foo(const MySuspend &ml, const MySuspend &mr)
          : aMl(ml), aMr(mr) {}
      virtual const ReturnType &operator()() const {
        return min(aMl.force(), aMr.force());
      }
    public:
      const MySuspend &aMl;
      const MySuspend &aMr;
    } &f(*new Foo(replaceLeft.second(),
                  replaceRight.second()));

    return mkPair(mkTree(replaceLeft.first(),
                         replaceRight.first()),
                  mkSuspend(f));
  }
  }
}



// The key.
template<class T>
const Tree<Suspend<T> > &
replaceWithMin(const Tree<Suspend<T> > &t)
{
  typedef Function<T> MyFunction;
  typedef Suspend<T> MySuspend;
  typedef Tree<MySuspend> MyTree;
  typedef Pair<MyTree, MySuspend> MyPair;
  typedef Function<MyPair> MyPairFunction;

  // Because of mutual recursion of function objects, need to mutate
  // one to point to the other.
  class Foo : public MyPairFunction {
  public:
    Foo(const MyTree &t)
        : aT(t) {}
    void setM(const MyFunction &m) const {
#ifdef mutable
      // Cast away const for now.
      ((Foo*)this)->aM = &m;
#else
      aM = &m;
#endif
    }
    virtual const ReturnType &operator()() const {
      return replaceAndMin(mkSuspend(*aM), aT);
    }
  private:
    mutable const MyFunction *aM;
    const MyTree &aT;
  };
  const Foo &foo = *new Foo(t);

  class M : public MyFunction {
  public:
    M(const MyPairFunction &foo)
        : aFoo(foo) {}
    virtual const ReturnType &operator()() const {
      return aFoo().second().force();
    }
  private:
    const MyPairFunction &aFoo;
  };
  const M &m = *new M(foo);

  // Tie the knot.
  foo.setM(m);

  return foo().first();
}


// For convenience.
template<class T>
const Tree<T> &
forceTree(const Tree<Suspend<T> > &t)
{
  switch (t.kind()) {
  case Tree<Suspend<T> >::LEAF:
    return mkLeaf(t.leaf().force());
  case Tree<Suspend<T> >::TREE:
    return mkTree(forceTree(t.left()),
                  forceTree(t.right()));
  }
}


// Simple pretty-printer.
// Relies on T being printable.
template<class T>
ostream &
operator<<(ostream &os, const Tree<T> &t)
{
  switch (t.kind()) {
  case Tree<T>::LEAF:
    return os << "Leaf " << t.leaf();
  case Tree<T>::TREE:
    return os << "Tree(" << t.left() << ", " << t.right() << ")";
  }
}



// Example.

template<class T>
class ValueThunk : public Function<T> {
public:
  ValueThunk(const ReturnType &value)
      : aValue(value) {}
  virtual const ReturnType &operator()() const {
    return aValue;
  }
private:
  const ReturnType    &aValue;
};

template<class T>
inline
const ValueThunk<T> &
mkValueThunk(const T &value)
{
  return *new ValueThunk<T>(value);
}



int
main(int,
     char *[])
{
  typedef ValueThunk<int> IntThunk;
  typedef Suspend<int> IntSusp;
  typedef Tree<IntSusp> IntSuspTree;
  typedef Tree<int> IntTree;

  const IntSuspTree &sample
    = mkTree(mkTree(mkLeaf(mkSuspend(mkValueThunk(*new int(12)))),
                    mkTree(mkLeaf(mkSuspend(mkValueThunk(*new int(23)))),
                           mkLeaf(mkSuspend(mkValueThunk(*new int(13)))))),
             mkLeaf(mkSuspend(mkValueThunk(*new int(10)))));
  const IntSuspTree &sample2 = mkTree(sample, sample);
  const IntSuspTree &sample4 = mkTree(sample2, sample2);

  const IntTree &forcedSample = forceTree(sample);
  cout << forcedSample << endl;

  cout << forceTree(replaceAndMin(mkSuspend(mkValueThunk(*new int(5))),
                                  sample).first())
       << endl;

  const IntSuspTree &minSample = replaceWithMin(sample);
  cout << forceTree(minSample) << endl;

  return 0;
}