Specialize NameMap::visit_children for ordered_map so that order is p…

…reserved when nodes change names or split or whatever.
p4lang · Apr 19, 2016 · 39dcae3 · 39dcae3
1 parent fdfb406
commit 39dcae3
Show file tree

Hide file tree

Showing 5 changed files with 92 additions and 8 deletions.
diff --git a/ir/ir-inline.h b/ir/ir-inline.h
@@ -76,9 +76,35 @@ std::ostream &operator<<(std::ostream &out, const IR::Vector<IR::Expression> &v)
 inline std::ostream &operator<<(std::ostream &out, const IR::Vector<IR::Expression> *v) {
     return v ? out << *v : out << "<null>"; }
 
+#include "lib/ordered_map.h"
+template <class MAP> static inline void
+namemap_insert_helper(typename MAP::iterator, typename MAP::key_type k,
+                      typename MAP::mapped_type v, MAP &, MAP &new_symbols) {
+    new_symbols.emplace(std::move(k), std::move(v));
+}
+
+template <class MAP, class InputIterator> static inline void
+namemap_insert_helper(typename MAP::iterator, InputIterator b, InputIterator e,
+                      MAP &, MAP &new_symbols) {
+    new_symbols.insert(b, e);
+}
+
+template <class T> static inline void
+namemap_insert_helper(typename ordered_map<cstring, T>::iterator it, cstring k, T v,
+                      ordered_map<cstring, T> &symbols, ordered_map<cstring, T> &) {
+    symbols.emplace_hint(it, std::move(k), std::move(v));
+}
+
+template <class T, class InputIterator> static inline void
+namemap_insert_helper(typename ordered_map<cstring, T>::iterator it,
+                      InputIterator b, InputIterator e,
+                      ordered_map<cstring, T> &symbols, ordered_map<cstring, T> &) {
+    symbols.insert(it, b, e);
+}
+
 template<class T, template<class K, class V, class COMP, class ALLOC> class MAP /*= std::map */,
          class COMP /*= std::less<cstring>*/,
-         class ALLOC /*= std::allocator<std::pair<cstring, const T*>>*/>
+         class ALLOC /*= std::allocator<std::pair<const cstring, const T*>>*/>
 void IR::NameMap<T, MAP, COMP, ALLOC>::visit_children(Visitor &v) {
     map_t   new_symbols;
     for (auto i = symbols.begin(); i != symbols.end();) {
@@ -88,14 +114,14 @@ void IR::NameMap<T, MAP, COMP, ALLOC>::visit_children(Visitor &v) {
         } else if (n == i->second) {
             i++;
         } else if (auto m = dynamic_cast<const NameMap *>(n)) {
-            new_symbols.insert(m->symbols.begin(), m->symbols.end());
+            namemap_insert_helper(i, m->symbols.begin(), m->symbols.end(), symbols, new_symbols);
             i = symbols.erase(i);
         } else if (auto s = dynamic_cast<const T *>(n)) {
             if (match_name(i->first, s)) {
                 i->second = s;
                 i++;
             } else {
-                new_symbols.emplace(obj_name(s), std::move(s));
+                namemap_insert_helper(i, cstring(obj_name(s)), std::move(s), symbols, new_symbols);
                 i = symbols.erase(i); }
         } else {
             BUG("visitor returned invalid type %s for NameMap<%s>",

diff --git a/ir/namemap.h b/ir/namemap.h
@@ -5,7 +5,7 @@ namespace IR {
 
 template<class T, template<class K, class V, class COMP, class ALLOC> class MAP = std::map,
          class COMP = std::less<cstring>,
-         class ALLOC = std::allocator<std::pair<cstring, const T*>>>
+         class ALLOC = std::allocator<std::pair<const cstring, const T*>>>
 class NameMap : public Node {
     typedef MAP<cstring, const T *, COMP, ALLOC>        map_t;
     map_t       symbols;

diff --git a/lib/ordered_map.h b/lib/ordered_map.h
@@ -130,22 +130,43 @@ class ordered_map {
         if (it == data.end()) throw std::out_of_range("ordered_map");
         return it->second; }
 
+    std::pair<iterator, bool> emplace(K &&k, V &&v) {
+        auto it = find(k);
+        if (it == data.end()) {
+            it = data.emplace(data.end(), std::move(k), std::move(v));
+            data_map.emplace(&it->first, it);
+            return std::make_pair(it, true); }
+        return std::make_pair(it, false); }
+    std::pair<iterator, bool> emplace_hint(iterator pos, K &&k, V &&v) {
+        /* should be const_iterator pos, but glibc++ std::list is broken */
+        auto it = find(k);
+        if (it == data.end()) {
+            it = data.emplace(pos, std::move(k), std::move(v));
+            data_map.emplace(&it->first, it);
+            return std::make_pair(it, true); }
+        return std::make_pair(it, false); }
+
     std::pair<iterator, bool> insert(const value_type &v) {
         auto it = find(v.first);
         if (it == data.end()) {
             it = data.insert(data.end(), v);
             data_map.emplace(&it->first, it);
             return std::make_pair(it, true); }
         return std::make_pair(it, false); }
-    std::pair<iterator, bool> emplace(K &&k, V &&v) {
-        auto it = find(k);
+    std::pair<iterator, bool> insert(iterator pos, const value_type &v) {
+        /* should be const_iterator pos, but glibc++ std::list is broken */
+        auto it = find(v.first);
         if (it == data.end()) {
-            it = data.emplace(data.end(), std::move(k), std::move(v));
+            it = data.insert(pos, v);
             data_map.emplace(&it->first, it);
             return std::make_pair(it, true); }
         return std::make_pair(it, false); }
     template<class InputIterator> void insert(InputIterator b, InputIterator e) {
         while (b != e) insert(*b++); }
+    template<class InputIterator>
+    void insert(iterator pos, InputIterator b, InputIterator e) {
+        /* should be const_iterator pos, but glibc++ std::list is broken */
+        while (b != e) insert(pos, *b++); }
 
     /* should be erase(const_iterator), but glibc++ std::list::erase is broken */
     iterator erase(iterator pos) {

diff --git a/test/Makefile.am b/test/Makefile.am
@@ -1,7 +1,8 @@
 # Unit tests
 
 check_PROGRAMS = exception_test format_test source_file_test path_test \
-                 enumerator_test default_test unittest_transform1 json_test
+		 enumerator_test default_test unittest_transform1 json_test \
+		 namemap_order_test
 
 default_test_SOURCES = test/unittests/default_test.cpp
 default_test_LDADD = libp4ctoolkit.a
@@ -19,6 +20,8 @@ json_test_SOURCES = test/unittests/json_test.cpp
 json_test_LDADD = libp4ctoolkit.a
 unittest_transform1_SOURCES = $(ir_SOURCES) test/unittests/transform1.cpp
 unittest_transform1_LDADD = libp4ctoolkit.a
+namemap_order_test_SOURCES = $(ir_SOURCES) test/unittests/namemap_order_test.cpp
+namemap_order_test_LDADD = libp4ctoolkit.a
 
 # Compiler tests
 

diff --git a/test/unittests/namemap_order_test.cpp b/test/unittests/namemap_order_test.cpp
@@ -0,0 +1,34 @@
+#include "ir/ir.h"
+#include "ir/visitor.h"
+#include <assert.h>
+
+class TestTrans : public Transform {
+    IR::Node *preorder(IR::TableProperty *a) override {
+        if (!a->isConstant)
+            a->name = "$new$";
+        return a;
+    }
+    IR::Node *postorder(IR::TableProperties *p) override {
+        int count = 0;
+        for (auto &prop : p->properties) {
+            if (prop.first == "$new$")
+                assert(count == 0);
+            else
+                assert(count == 1);
+            ++count; }
+        return p;
+    }
+};
+
+int main() {
+    auto tp = new IR::TableProperties();
+    tp->properties.add("a", new IR::TableProperty(Util::SourceInfo(), "a",
+        new IR::Annotations(new IR::Vector<IR::Annotation>()),
+        new IR::Key(Util::SourceInfo(), new IR::Vector<IR::KeyElement>()),
+        false));
+    tp->properties.add("b", new IR::TableProperty(Util::SourceInfo(), "b",
+        new IR::Annotations(new IR::Vector<IR::Annotation>()),
+        new IR::Key(Util::SourceInfo(), new IR::Vector<IR::KeyElement>()),
+        true));
+    tp->apply(TestTrans());
+}