2 files changed, 60 insertions, 0 deletions
diff --git a/src/fix-ng/fix-expr.cc b/src/fix-ng/fix-expr.cc
new file mode 100644
index 000000000000..00795da4c427
--- /dev/null
+++ b/src/fix-ng/fix-expr.cc
@@ -0,0 +1,33 @@
+#include "fix-expr.hh"
+#include "expr.hh"
+
+
+ATerm bottomupRewrite(TermFun & f, ATerm e)
+{
+    e = f(e);
+
+    if (ATgetType(e) == AT_APPL) {
+        AFun fun = ATgetAFun(e);
+        int arity = ATgetArity(fun);
+        ATermList args = ATempty;
+
+        for (int i = arity - 1; i >= 0; i--)
+            args = ATinsert(args, bottomupRewrite(f, ATgetArgument(e, i)));
+        
+        return (ATerm) ATmakeApplList(fun, args);
+    }
+
+    if (ATgetType(e) == AT_LIST) {
+        ATermList in = (ATermList) e;
+        ATermList out = ATempty;
+
+        while (!ATisEmpty(in)) {
+            out = ATinsert(out, bottomupRewrite(f, ATgetFirst(in)));
+            in = ATgetNext(in);
+        }
+
+        return (ATerm) ATreverse(out);
+    }
+
+    throw badTerm("cannot rewrite", e);
+}
diff --git a/src/fix-ng/fix-expr.hh b/src/fix-ng/fix-expr.hh
new file mode 100644
index 000000000000..5c50e9170fe5
--- /dev/null
+++ b/src/fix-ng/fix-expr.hh
@@ -0,0 +1,27 @@
+#ifndef __FIXEXPR_H
+#define __FIXEXPR_H
+
+#include <aterm2.h>
+
+#include "util.hh"
+
+
+/* Fix expressions are represented as ATerms.  The maximal sharing
+   property of the ATerm library allows us to implement caching of
+   normals forms efficiently. */
+typedef ATerm Expr;
+
+
+/* Generic bottomup traversal over ATerms.  The traversal first
+   recursively descends into subterms, and then applies the given term
+   function to the resulting term. */
+
+struct TermFun
+{
+    virtual ATerm operator () (ATerm e) = 0;
+};
+
+ATerm bottomupRewrite(TermFun & f, ATerm e);
+
+
+#endif /* !__FIXEXPR_H */