fix routing bugs, some optimization on trie

6 files changed, 232 insertions, 16 deletions

diff --git a/.gitignore b/.gitignore
index e86bfe6..2837b7f 100644
--- a/.gitignore
+++ b/.gitignore
@@ -27,8 +27,5 @@ unittest
 *.gcov
 
 covtest
-unittest.gcda
-unittest.gcno
-
-http_parser.gcda
-http_parser.gcno
+*.gcda
+*.gcno
diff --git a/Makefile b/Makefile
index 5e34a02..ff23cb6 100644
--- a/Makefile
+++ b/Makefile
@@ -15,7 +15,8 @@ unittest: unittest.cpp routing.h
 	./unittest
 
 covtest: unittest.cpp routing.h utility.h flask.h http_server.h http_connection.h parser.h http_response.h common.h
-	g++ -Wall -g -std=c++11 -fno-default-inline -fno-inline-small-functions --coverage -o covtest unittest.cpp http-parser/http_parser.c -pthread -lboost_system -lboost_thread -I http-parser/
+	g++ -O2 -Wall -g -std=c++11 -fno-default-inline -fno-inline-small-functions --coverage -o covtest unittest.cpp http-parser/http_parser.c -pthread -lboost_system -lboost_thread -I http-parser/
+	#clang++ -O2 -Wall -g -std=c++11 -o covtest unittest.cpp http-parser/http_parser.c -pthread -lboost_system -lboost_thread -I http-parser/
 	./covtest
 	gcov -r unittest.cpp
 
diff --git a/common.h b/common.h
index ff63e9f..c028ee4 100644
--- a/common.h
+++ b/common.h
@@ -22,6 +22,23 @@ namespace flask
         std::vector<double> double_params;
         std::vector<std::string> string_params;
 
+        void debug_print() const
+        {
+            std::cerr << "routing_params" << std::endl;
+            for(auto i:int_params)
+                std::cerr<<i <<", " ;
+            std::cerr<<std::endl;
+            for(auto i:uint_params)
+                std::cerr<<i <<", " ;
+            std::cerr<<std::endl;
+            for(auto i:double_params)
+                std::cerr<<i <<", " ;
+            std::cerr<<std::endl;
+            for(auto& i:string_params)
+                std::cerr<<i <<", " ;
+            std::cerr<<std::endl;
+        }
+
         template <typename T>
         T get(unsigned) const;
 
diff --git a/flask.h b/flask.h
index ec14f9a..ddc91e8 100644
--- a/flask.h
+++ b/flask.h
@@ -59,6 +59,12 @@ namespace flask
             Server<Flask> server(this, port_);
             server.run();
         }
+        void debug_print()
+        {
+            std::cerr << "Routing:" << std::endl;
+            router_.debug_print();
+        }
+
     private:
         uint16_t port_ = 80;
 
diff --git a/routing.h b/routing.h
index fd8c475..4b3c812 100644
--- a/routing.h
+++ b/routing.h
@@ -122,7 +122,7 @@ namespace flask
         {
             response operator()(F& handler, const routing_params& params)
             {
-                using pushed = typename black_magic::S<Args2...>::template push_back<call_pair<uint64_t, NInt>>;
+                using pushed = typename black_magic::S<Args2...>::template push_back<call_pair<uint64_t, NUint>>;
                 return call<F, NInt, NUint+1, NDouble, NString,
                        black_magic::S<Args1...>, pushed>()(handler, params);
             }
@@ -133,7 +133,7 @@ namespace flask
         {
             response operator()(F& handler, const routing_params& params)
             {
-                using pushed = typename black_magic::S<Args2...>::template push_back<call_pair<double, NInt>>;
+                using pushed = typename black_magic::S<Args2...>::template push_back<call_pair<double, NDouble>>;
                 return call<F, NInt, NUint, NDouble+1, NString,
                        black_magic::S<Args1...>, pushed>()(handler, params);
             }
@@ -144,7 +144,7 @@ namespace flask
         {
             response operator()(F& handler, const routing_params& params)
             {
-                using pushed = typename black_magic::S<Args2...>::template push_back<call_pair<std::string, NInt>>;
+                using pushed = typename black_magic::S<Args2...>::template push_back<call_pair<std::string, NString>>;
                 return call<F, NInt, NUint, NDouble, NString+1,
                        black_magic::S<Args1...>, pushed>()(handler, params);
             }
@@ -158,7 +158,6 @@ namespace flask
                 return handler(
                     params.get<typename Args1::type>(Args1::pos)... 
                 );
-                //return response(500);
             }
         };
     public:
@@ -182,6 +181,8 @@ namespace flask
         {
             static_assert(black_magic::CallHelper<Func, black_magic::S<Args...>>::value, 
                 "Handler type is mismatched with URL paramters");
+            static_assert(!std::is_same<void, decltype(f(std::declval<Args>()...))>::value, 
+                "Handler function cannot have void return type; valid return types: string, int, flask::resposne");
             handler_ = [f = std::move(f)](Args ... args){
                 return response(f(args...));
             };
@@ -192,6 +193,8 @@ namespace flask
         {
             static_assert(black_magic::CallHelper<Func, black_magic::S<Args...>>::value, 
                 "Handler type is mismatched with URL paramters");
+            static_assert(!std::is_same<void, decltype(f(std::declval<Args>()...))>::value, 
+                "Handler function cannot have void return type; valid return types: string, int, flask::resposne");
             name_ = std::move(name);
             handler_ = [f = std::move(f)](Args ... args){
                 return response(f(args...));
@@ -222,9 +225,10 @@ namespace flask
     public:
         struct Node
         {
-            std::unordered_map<std::string, unsigned> children;
             unsigned rule_index{};
             std::array<unsigned, (int)ParamType::MAX> param_childrens{};
+            std::unordered_map<std::string, unsigned> children;
+
             bool IsSimpleNode() const
             {
                 return 
@@ -243,10 +247,46 @@ namespace flask
 private:
         void optimizeNode(Node* node)
         {
+            for(auto x : node->param_childrens)
+            {
+                if (!x)
+                    continue;
+                Node* child = &nodes_[x];
+                optimizeNode(child);
+            }
+            if (node->children.empty())
+                return;
+            bool mergeWithChild = true;
             for(auto& kv : node->children)
             {
                 Node* child = &nodes_[kv.second];
-                optimizeNode(child);
+                if (!child->IsSimpleNode())
+                {
+                    mergeWithChild = false;
+                    break;
+                }
+            }
+            if (mergeWithChild)
+            {
+                decltype(node->children) merged;
+                for(auto& kv : node->children)
+                {
+                    Node* child = &nodes_[kv.second];
+                    for(auto& child_kv : child->children)
+                    {
+                        merged[kv.first + child_kv.first] = child_kv.second;
+                    }
+                }
+                node->children = std::move(merged);
+                optimizeNode(node);
+            }
+            else
+            {
+                for(auto& kv : node->children)
+                {
+                    Node* child = &nodes_[kv.second];
+                    optimizeNode(child);
+                }
             }
         }
 
@@ -383,7 +423,7 @@ public:
                 }
             }
 
-            return {found, std::move(match_params)};
+            return {found, match_params};
         }
 
         void add(const std::string& url, unsigned rule_index)
@@ -416,7 +456,12 @@ public:
                     {
                         if (url.compare(i, it->name.size(), it->name) == 0)
                         {
-                            idx = nodes_[idx].param_childrens[(int)it->type] = new_node();
+                            if (!nodes_[idx].param_childrens[(int)it->type])
+                            {
+                                auto new_node_idx = new_node();
+                                nodes_[idx].param_childrens[(int)it->type] = new_node_idx;
+                            }
+                            idx = nodes_[idx].param_childrens[(int)it->type];
                             i += it->name.size();
                             found = true;
                             break;
@@ -425,7 +470,8 @@ public:
 
                     if (!found)
                     {
-                        throw std::runtime_error("Invalid parameter type: " + url + " (" + boost::lexical_cast<std::string>(i) + ")");
+                        throw std::runtime_error("Invalid parameter type: " + url + 
+                            " (" + boost::lexical_cast<std::string>(i) + ")");
                     }
                     i --;
                 }
@@ -434,7 +480,8 @@ public:
                     std::string piece(&c, 1);
                     if (!nodes_[idx].children.count(piece))
                     {
-                        nodes_[idx].children.emplace(piece, new_node());
+                        auto new_node_idx = new_node();
+                        nodes_[idx].children.emplace(piece, new_node_idx);
                     }
                     idx = nodes_[idx].children[piece];
                 }
@@ -444,6 +491,52 @@ public:
             nodes_[idx].rule_index = rule_index;
         }
     private:
+        void debug_node_print(Node* n, int level)
+        {
+            for(int i = 0; i < (int)ParamType::MAX; i ++)
+            {
+                if (n->param_childrens[i])
+                {
+                    std::cerr << std::string(2*level, ' ') /*<< "("<<n->param_childrens[i]<<") "*/;
+                    switch((ParamType)i)
+                    {
+                        case ParamType::INT:
+                            std::cerr << "<int>";
+                            break;
+                        case ParamType::UINT:
+                            std::cerr << "<uint>";
+                            break;
+                        case ParamType::DOUBLE:
+                            std::cerr << "<float>";
+                            break;
+                        case ParamType::STRING:
+                            std::cerr << "<str>";
+                            break;
+                        case ParamType::PATH:
+                            std::cerr << "<path>";
+                            break;
+                        default:
+                            std::cerr << "<ERROR>";
+                            break;
+                    }
+                    std::cerr << std::endl;
+                    debug_node_print(&nodes_[n->param_childrens[i]], level+1);
+                }
+            }
+            for(auto& kv : n->children)
+            {
+                std::cerr << std::string(2*level, ' ') /*<< "(" << kv.second << ") "*/ << kv.first << std::endl;
+                debug_node_print(&nodes_[kv.second], level+1);
+            }
+        }
+
+    public:
+        void debug_print()
+        {
+            debug_node_print(head(), 0);
+        }
+
+    private:
         const Node* head() const
         {
             return &nodes_.front();
@@ -498,6 +591,7 @@ public:
         response handle(const request& req)
         {
             auto found = trie_.find(req);
+
             unsigned rule_index = found.first;
 
             if (!rule_index)
@@ -508,6 +602,12 @@ public:
 
             return rules_[rule_index]->handle(req, found.second);
         }
+
+        void debug_print()
+        {
+            trie_.debug_print();
+        }
+
     private:
         std::vector<std::unique_ptr<BaseRule>> rules_;
         Trie trie_;
diff --git a/unittest.cpp b/unittest.cpp
index b573b13..c0a45b7 100644
--- a/unittest.cpp
+++ b/unittest.cpp
@@ -30,6 +30,8 @@ void fail(Args...args) { error_print(args...);failed__ = true; }
 #define ASSERT_NOTEQUAL(a, b) if (a != b) fail("Assert fail: not expected ", (a), ", " #a " != " #b ", at " __FILE__ ":",__LINE__)
 #define TEST(x) struct test##x:public Test{void test();}x##_; \
     void test##x::test()
+#define DISABLE_TEST(x) struct test##x{void test();}x##_; \
+    void test##x::test()
 
 TEST(Rule)
 {
@@ -79,6 +81,99 @@ TEST(ParameterTagging)
     static_assert(std::is_same<black_magic::S<uint64_t, double, int64_t>, black_magic::arguments<6*6+6*3+2>::type>::value, "tag to type container");
 }
 
+TEST(RoutingTest)
+{
+    Flask app;
+    int A{};
+    uint32_t B{};
+    double C{};
+    string D{};
+    string E{};
+
+    FLASK_ROUTE(app, "/0/<uint>")
+    ([&](uint32_t b){
+        B = b;
+        return "OK";
+    });
+
+    FLASK_ROUTE(app, "/1/<int>/<uint>")
+    ([&](int a, uint32_t b){
+        A = a; B = b;
+        return "OK";
+    });
+
+    FLASK_ROUTE(app, "/4/<int>/<uint>/<double>/<string>")
+    ([&](int a, uint32_t b, double c, string d){
+        A = a; B = b; C = c; D = d;
+        return "OK";
+    });
+
+    FLASK_ROUTE(app, "/5/<int>/<uint>/<double>/<string>/<path>")
+    ([&](int a, uint32_t b, double c, string d, string e){
+        A = a; B = b; C = c; D = d; E = e;
+        return "OK";
+    });
+
+    app.validate();
+    app.debug_print();
+
+    {
+        request req;
+
+        req.url = "/0/1001999";
+
+        auto res = app.handle(req);
+
+        ASSERT_EQUAL(200, res.code);
+
+        ASSERT_EQUAL(1001999, B);
+    }
+
+    {
+        request req;
+
+        req.url = "/1/-100/1999";
+
+        auto res = app.handle(req);
+
+        ASSERT_EQUAL(200, res.code);
+
+        ASSERT_EQUAL(-100, A);
+        ASSERT_EQUAL(1999, B);
+    }
+    {
+        request req;
+
+        req.url = "/4/5000/3/-2.71828/hellhere";
+        req.headers["TestHeader"] = "Value";
+
+        auto res = app.handle(req);
+
+        ASSERT_EQUAL(200, res.code);
+
+        ASSERT_EQUAL(5000, A);
+        ASSERT_EQUAL(3, B);
+        ASSERT_EQUAL(-2.71828, C);
+        ASSERT_EQUAL("hellhere", D);
+    }
+    {
+        request req;
+
+        req.url = "/5/-5/999/3.141592/hello_there/a/b/c/d";
+        req.headers["TestHeader"] = "Value";
+
+        auto res = app.handle(req);
+
+        ASSERT_EQUAL(200, res.code);
+
+        ASSERT_EQUAL(-5, A);
+        ASSERT_EQUAL(999, B);
+        ASSERT_EQUAL(3.141592, C);
+        ASSERT_EQUAL("hello_there", D);
+        ASSERT_EQUAL("a/b/c/d", E);
+    }
+}
+
 TEST(simple_response_routing_params)
 {
     ASSERT_EQUAL(100, response(100).code);