util: Adding regex support.
Change-Id: I33d84f4ae9076ff5a9db5232f2955f4be0ed820c
diff --git a/src/util/regex.hpp b/src/util/regex.hpp
new file mode 100644
index 0000000..0e7d6a0
--- /dev/null
+++ b/src/util/regex.hpp
@@ -0,0 +1,21 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_HPP
+#define NDN_REGEX_HPP
+
+#include "regex/regex-top-matcher.hpp"
+
+namespace ndn
+{
+
+typedef RegexTopMatcher Regex;
+
+}
+
+#endif
+
diff --git a/src/util/regex/regex-backref-manager.cpp b/src/util/regex/regex-backref-manager.cpp
new file mode 100644
index 0000000..ed17250
--- /dev/null
+++ b/src/util/regex/regex-backref-manager.cpp
@@ -0,0 +1,29 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "regex-backref-manager.hpp"
+
+namespace ndn
+{
+
+RegexBackrefManager::~RegexBackrefManager()
+{ m_backRefs.clear(); }
+
+int
+RegexBackrefManager::pushRef(ptr_lib::shared_ptr<RegexMatcher> matcher)
+{
+ int last = m_backRefs.size();
+ m_backRefs.push_back(matcher);
+
+ return last;
+}
+
+void
+RegexBackrefManager::popRef()
+{ m_backRefs.pop_back(); }
+
+}//ndn
diff --git a/src/util/regex/regex-backref-manager.hpp b/src/util/regex/regex-backref-manager.hpp
new file mode 100644
index 0000000..7604b42
--- /dev/null
+++ b/src/util/regex/regex-backref-manager.hpp
@@ -0,0 +1,46 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_BACKREF_MANAGER_HPP
+#define NDN_REGEX_BACKREF_MANAGER_HPP
+
+#include <vector>
+#include "../../common.hpp"
+
+namespace ndn
+{
+
+class RegexMatcher;
+
+class RegexBackrefManager
+{
+public:
+ RegexBackrefManager(){}
+
+ virtual ~RegexBackrefManager();
+
+ int
+ pushRef(ptr_lib::shared_ptr<RegexMatcher> matcher);
+
+ void
+ popRef();
+
+ int
+ size()
+ { return m_backRefs.size(); }
+
+ ptr_lib::shared_ptr<RegexMatcher>
+ getBackRef(int i)
+ { return m_backRefs[i]; }
+
+private:
+ std::vector<ptr_lib::shared_ptr<RegexMatcher> > m_backRefs;
+};
+
+}//ndn
+
+#endif
diff --git a/src/util/regex/regex-backref-matcher.cpp b/src/util/regex/regex-backref-matcher.cpp
new file mode 100644
index 0000000..1982623
--- /dev/null
+++ b/src/util/regex/regex-backref-matcher.cpp
@@ -0,0 +1,57 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include <boost/regex.hpp>
+
+#include "regex-backref-matcher.hpp"
+#include "regex-pattern-list-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexBackrefMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+
+RegexBackrefMatcher::RegexBackrefMatcher(const string expr, ptr_lib::shared_ptr<RegexBackrefManager> backRefManager)
+ : RegexMatcher (expr, EXPR_BACKREF, backRefManager)
+{
+ // _LOG_TRACE ("Enter RegexBackrefMatcher Constructor: ");
+ // compile();
+ // _LOG_TRACE ("Exit RegexBackrefMatcher Constructor: ");
+}
+
+void
+RegexBackrefMatcher::compile()
+{
+ // _LOG_TRACE ("Enter RegexBackrefMatcher::compile()");
+
+ string errMsg = "Error: RegexBackrefMatcher.Compile(): ";
+
+ // _LOG_DEBUG ("m_backRefManager: " << m_backRefManager);
+
+ int lastIndex = m_expr.size() - 1;
+ if('(' == m_expr[0] && ')' == m_expr[lastIndex]){
+ // m_backRefManager->pushRef(this);
+
+ ptr_lib::shared_ptr<RegexMatcher> matcher = ptr_lib::make_shared<RegexPatternListMatcher>(m_expr.substr(1, lastIndex - 1), m_backrefManager);
+ m_matcherList.push_back(matcher);
+
+ }
+ else
+ throw RegexMatcher::Error(errMsg + " Unrecognoized format " + m_expr);
+
+ // _LOG_TRACE ("Exit RegexBackrefMatcher::compile");
+}
+
+}//ndn
+
+
+
+
diff --git a/src/util/regex/regex-backref-matcher.hpp b/src/util/regex/regex-backref-matcher.hpp
new file mode 100644
index 0000000..de04b19
--- /dev/null
+++ b/src/util/regex/regex-backref-matcher.hpp
@@ -0,0 +1,43 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_BACKREF_MATCHER_HPP
+#define NDN_REGEX_BACKREF_MATCHER_HPP
+
+#include "regex-matcher.hpp"
+
+#include <boost/enable_shared_from_this.hpp>
+
+namespace ndn
+{
+
+class RegexBackrefMatcher : public RegexMatcher
+{
+public:
+ RegexBackrefMatcher(const std::string expr, ptr_lib::shared_ptr<RegexBackrefManager> backRefManager);
+
+ virtual ~RegexBackrefMatcher(){}
+
+ void
+ lateCompile()
+ {
+ compile();
+ }
+
+protected:
+ virtual void
+ compile();
+
+private:
+ int m_refNum;
+};
+
+}//ndn
+
+#endif
+
+
diff --git a/src/util/regex/regex-component-matcher.cpp b/src/util/regex/regex-component-matcher.cpp
new file mode 100644
index 0000000..e3bbe0e
--- /dev/null
+++ b/src/util/regex/regex-component-matcher.cpp
@@ -0,0 +1,87 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "regex-component-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexComponentMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+
+RegexComponentMatcher::RegexComponentMatcher (const string & expr,
+ ptr_lib::shared_ptr<RegexBackrefManager> backRefManager,
+ bool exact)
+ : RegexMatcher (expr, EXPR_COMPONENT, backRefManager),
+ m_exact(exact)
+{
+ // _LOG_TRACE ("Enter RegexComponentMatcher Constructor: ");
+ compile();
+ // _LOG_TRACE ("Exit RegexComponentMatcher Constructor: ");
+}
+
+void
+RegexComponentMatcher::compile ()
+{
+ // _LOG_TRACE ("Enter RegexComponentMatcher::compile");
+
+ m_componentRegex = boost::regex (m_expr);
+
+ m_pseudoMatcher.clear();
+ m_pseudoMatcher.push_back(ptr_lib::make_shared<RegexPseudoMatcher>());
+
+ for (int i = 1; i < m_componentRegex.mark_count(); i++)
+ {
+ ptr_lib::shared_ptr<RegexPseudoMatcher> pMatcher = ptr_lib::make_shared<RegexPseudoMatcher>();
+ m_pseudoMatcher.push_back(pMatcher);
+ m_backrefManager->pushRef(ptr_lib::static_pointer_cast<RegexMatcher>(pMatcher));
+ }
+
+
+ // _LOG_TRACE ("Exit RegexComponentMatcher::compile");
+}
+
+bool
+RegexComponentMatcher::match (const Name & name, const int & offset, const int & len)
+{
+ // _LOG_TRACE ("Enter RegexComponentMatcher::match ");
+
+ m_matchResult.clear();
+
+ if("" == m_expr)
+ {
+ m_matchResult.push_back(name.get(offset));
+ return true;
+ }
+
+ if(true == m_exact)
+ {
+ boost::smatch subResult;
+ string targetStr = name.get(offset).toEscapedString();
+ if(boost::regex_match(targetStr, subResult, m_componentRegex))
+ {
+ for (int i = 1; i < m_componentRegex.mark_count(); i++)
+ {
+ m_pseudoMatcher[i]->resetMatchResult();
+ m_pseudoMatcher[i]->setMatchResult(subResult[i]);
+ }
+ m_matchResult.push_back(name.get(offset));
+ return true;
+ }
+ }
+ else
+ {
+ throw RegexMatcher::Error("Non-exact component search is not supported yet!");
+ }
+
+ return false;
+}
+
+} //ndn
diff --git a/src/util/regex/regex-component-matcher.hpp b/src/util/regex/regex-component-matcher.hpp
new file mode 100644
index 0000000..830b45c
--- /dev/null
+++ b/src/util/regex/regex-component-matcher.hpp
@@ -0,0 +1,54 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_COMPONENT_HPP
+#define NDN_REGEX_COMPONENT_HPP
+
+#include <boost/regex.hpp>
+
+#include "regex-matcher.hpp"
+#include "regex-pseudo-matcher.hpp"
+
+
+namespace ndn
+{
+class RegexComponentMatcher : public RegexMatcher
+{
+public:
+ /**
+ * @brief Create a RegexComponent matcher from expr
+ * @param expr The standard regular expression to match a component
+ * @param backRefManager The back reference manager
+ * @param exact The flag to provide exact match
+ */
+ RegexComponentMatcher(const std::string& expr,
+ ptr_lib::shared_ptr<RegexBackrefManager> backRefManager,
+ bool exact = true);
+
+ virtual ~RegexComponentMatcher() {};
+
+ virtual bool
+ match(const Name & name, const int & offset, const int &len = 1);
+
+protected:
+ /**
+ * @brief Compile the regular expression to generate the more matchers when necessary
+ * @returns true if compiling succeeds
+ */
+ virtual void
+ compile();
+
+private:
+ bool m_exact;
+ boost::regex m_componentRegex;
+ std::vector<ptr_lib::shared_ptr<RegexPseudoMatcher> > m_pseudoMatcher;
+
+};
+
+}//ndn
+
+#endif
diff --git a/src/util/regex/regex-component-set-matcher.cpp b/src/util/regex/regex-component-set-matcher.cpp
new file mode 100644
index 0000000..dddebfc
--- /dev/null
+++ b/src/util/regex/regex-component-set-matcher.cpp
@@ -0,0 +1,179 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "regex-component-set-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexComponentSetMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+RegexComponentSetMatcher::RegexComponentSetMatcher(const string expr, ptr_lib::shared_ptr<RegexBackrefManager> backRefManager)
+ : RegexMatcher(expr, EXPR_COMPONENT_SET, backRefManager),
+ m_include(true)
+{
+ // _LOG_TRACE ("Enter RegexComponentSetMatcher Constructor");
+ compile();
+ // _LOG_TRACE ("Exit RegexComponentSetMatcher Constructor");
+}
+
+RegexComponentSetMatcher::~RegexComponentSetMatcher()
+{
+ // set<Ptr<RegexComponent> >::iterator it = m_components.begin();
+
+ // for(; it != m_components.end(); it++)
+ // delete *it;
+}
+
+void
+RegexComponentSetMatcher::compile()
+{
+ // _LOG_TRACE ("Enter RegexComponentSetMatcher::compile");
+
+ string errMsg = "Error: RegexComponentSetMatcher.compile(): ";
+ int index = 0;
+
+
+ switch(m_expr[0]){
+ case '<':
+ return compileSingleComponent();
+ case '[':
+ {
+ int lastIndex = m_expr.size() - 1;
+ if(']' != m_expr[lastIndex])
+ throw RegexMatcher::Error(errMsg + " No matched ']' " + m_expr);
+
+ if('^' == m_expr[1]){
+ m_include = false;
+ compileMultipleComponents(2, lastIndex);
+ }
+ else
+ compileMultipleComponents(1, lastIndex);
+ break;
+ }
+ default:
+ throw RegexMatcher::Error(errMsg + "Parsing error in expr " + m_expr);
+ }
+
+ // _LOG_TRACE ("Exit RegexComponentSetMatcher::compile");
+}
+
+void
+RegexComponentSetMatcher::compileSingleComponent()
+{
+ // _LOG_TRACE ("Enter RegexComponentSetMatcher::compileSingleComponent");
+
+ string errMsg = "Error: RegexComponentSetMatcher.compileSingleComponent: ";
+
+ int end = extractComponent(1);
+
+ if(m_expr.size() != end)
+ throw RegexMatcher::Error(errMsg + m_expr);
+ else{
+ // _LOG_DEBUG ("RegexComponentSetMatcher::compileSingleComponent expr: " << m_expr.substr(1, end - 2));
+ ptr_lib::shared_ptr<RegexComponentMatcher> component = ptr_lib::make_shared<RegexComponentMatcher>(m_expr.substr(1, end - 2), m_backrefManager);
+ m_components.insert(component);
+
+ }
+
+ // _LOG_TRACE ("Exit RegexComponentSetMatcher::compileSingleComponent");
+}
+
+void
+RegexComponentSetMatcher::compileMultipleComponents(const int start, const int lastIndex)
+{
+ // _LOG_TRACE ("Enter RegexComponentSetMatcher::compileMultipleComponents");
+
+ string errMsg = "Error: RegexComponentSetMatcher.compileMultipleComponents: ";
+
+ int index = start;
+ int tmp_index = start;
+
+ while(index < lastIndex){
+ if('<' != m_expr[index])
+ throw RegexMatcher::Error(errMsg + "Component expr error " + m_expr);
+
+ tmp_index = index + 1;
+ index = extractComponent(tmp_index);
+
+ ptr_lib::shared_ptr<RegexComponentMatcher> component = ptr_lib::make_shared<RegexComponentMatcher>(m_expr.substr(tmp_index, index - tmp_index - 1), m_backrefManager);
+ m_components.insert(component);
+ }
+
+ if(index != lastIndex)
+ throw RegexMatcher::Error(errMsg + "Not sufficient expr to parse " + m_expr);
+
+ // _LOG_TRACE ("Exit RegexComponentSetMatcher::compileMultipleComponents");
+}
+
+bool
+RegexComponentSetMatcher::match(const Name & name, const int & offset, const int & len)
+{
+ // _LOG_TRACE ("Enter RegexComponentSetMatcher::match");
+
+ bool matched = false;
+
+ /* componentset only matches one component */
+ if(len != 1){
+ // _LOG_DEBUG ("Match Fail: ComponentSet matches only one component");
+ return false;
+ }
+
+ set<ptr_lib::shared_ptr<RegexComponentMatcher> >::iterator it = m_components.begin();
+
+ for(; it != m_components.end(); it++){
+ if((*it)->match(name, offset, len)){
+ matched = true;
+ break;
+ }
+ }
+
+ m_matchResult.clear();
+
+ if(m_include ? matched : !matched){
+ m_matchResult.push_back(name.get(offset));
+ return true;
+ }
+ else
+ return false;
+}
+
+int
+RegexComponentSetMatcher::extractComponent(int index)
+{
+ // _LOG_TRACE ("Enter RegexComponentSetMatcher::extractComponent");
+
+ int lcount = 1;
+ int rcount = 0;
+
+ while(lcount > rcount){
+ switch(m_expr[index]){
+ case '<':
+ lcount++;
+ break;
+
+ case '>':
+ rcount++;
+ break;
+
+ case 0:
+ throw RegexMatcher::Error("Error: square brackets mismatch");
+ break;
+ }
+ index++;
+
+ }
+
+ // _LOG_TRACE ("Exit RegexComponentSetMatcher::extractComponent");
+ return index;
+
+}
+
+}//ndn
diff --git a/src/util/regex/regex-component-set-matcher.hpp b/src/util/regex/regex-component-set-matcher.hpp
new file mode 100644
index 0000000..d4c576e
--- /dev/null
+++ b/src/util/regex/regex-component-set-matcher.hpp
@@ -0,0 +1,61 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef REGEX_COMPONENT_SET_MATCHER_HPP
+#define REGEX_COMPONENT_SET_MATCHER_HPP
+
+#include <set>
+
+#include "regex-matcher.hpp"
+#include "regex-component-matcher.hpp"
+
+namespace ndn
+{
+
+class RegexComponentSetMatcher : public RegexMatcher
+{
+
+public:
+ /**
+ * @brief Create a RegexComponentSetMatcher matcher from expr
+ * @param expr The standard regular expression to match a component
+ * @param exact The flag to provide exact match
+ * @param backRefNum The starting back reference number
+ */
+ RegexComponentSetMatcher(const std::string expr, ptr_lib::shared_ptr<RegexBackrefManager> backRefManager);
+
+ virtual ~RegexComponentSetMatcher();
+
+ virtual bool
+ match(const Name & name, const int & offset, const int & len = 1);
+
+protected:
+ /**
+ * @brief Compile the regular expression to generate the more matchers when necessary
+ * @returns true if compiling succeeds
+ */
+ virtual void
+ compile();
+
+private:
+ int
+ extractComponent(int index);
+
+ void
+ compileSingleComponent();
+
+ void
+ compileMultipleComponents(const int start, const int lastIndex);
+
+private:
+ std::set<ptr_lib::shared_ptr<RegexComponentMatcher> > m_components;
+ bool m_include;
+};
+
+}//ndn
+
+#endif
diff --git a/src/util/regex/regex-matcher.cpp b/src/util/regex/regex-matcher.cpp
new file mode 100644
index 0000000..b83aa2e
--- /dev/null
+++ b/src/util/regex/regex-matcher.cpp
@@ -0,0 +1,78 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "regex-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+RegexMatcher::RegexMatcher(const std::string& expr,
+ const RegexExprType& type,
+ ptr_lib::shared_ptr<RegexBackrefManager> backrefManager)
+ : m_expr(expr),
+ m_type(type),
+ m_backrefManager(backrefManager)
+{
+ if(NULL == m_backrefManager)
+ m_backrefManager = ptr_lib::shared_ptr<RegexBackrefManager>(new RegexBackrefManager);
+}
+
+RegexMatcher::~RegexMatcher()
+{}
+
+bool
+RegexMatcher::match (const Name& name, const int& offset, const int& len)
+{
+ // _LOG_TRACE ("Enter RegexMatcher::match");
+ bool result = false;
+
+ m_matchResult.clear();
+
+ if(recursiveMatch(0, name, offset, len))
+ {
+ for(int i = offset; i < offset + len ; i++)
+ m_matchResult.push_back(name.get(i));
+ result = true;
+ }
+ else
+ {
+ result = false;
+ }
+
+ // _LOG_TRACE ("Exit RegexMatcher::match");
+ return result;
+}
+
+bool
+RegexMatcher::recursiveMatch(const int& mId, const Name& name, const int& offset, const int& len)
+{
+ // _LOG_TRACE ("Enter RegexMatcher::recursiveMatch");
+
+ int tried = len;
+
+ if(mId >= m_matcherList.size())
+ return (len != 0 ? false : true);
+
+ ptr_lib::shared_ptr<RegexMatcher> matcher = m_matcherList[mId];
+
+ while(tried >= 0)
+ {
+ if(matcher->match(name, offset, tried) && recursiveMatch(mId + 1, name, offset + tried, len - tried))
+ return true;
+ tried--;
+ }
+
+ return false;
+}
+
+}//ndn
+
diff --git a/src/util/regex/regex-matcher.hpp b/src/util/regex/regex-matcher.hpp
new file mode 100644
index 0000000..ba465ac
--- /dev/null
+++ b/src/util/regex/regex-matcher.hpp
@@ -0,0 +1,85 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+
+#ifndef NDN_REGEX_MATCHER_H
+#define NDN_REGEX_MATCHER_H
+
+#include <string>
+#include "../../name.hpp"
+#include "regex-backref-manager.hpp"
+
+namespace ndn
+{
+class RegexMatcher;
+
+class RegexMatcher
+{
+public:
+ struct Error : public std::runtime_error { Error(const std::string &what) : std::runtime_error(what) {} };
+
+ enum RegexExprType{
+ EXPR_TOP,
+
+ EXPR_PATTERNLIST,
+
+ EXPR_REPEAT_PATTERN,
+
+ EXPR_BACKREF,
+ EXPR_COMPONENT_SET,
+ EXPR_COMPONENT,
+
+ EXPR_PSEUDO
+ };
+
+ RegexMatcher(const std::string& expr,
+ const RegexExprType& type,
+ ptr_lib::shared_ptr<RegexBackrefManager> backrefManager = ptr_lib::shared_ptr<RegexBackrefManager>());
+
+ virtual
+ ~RegexMatcher();
+
+ virtual bool
+ match(const Name& name, const int& offset, const int& len);
+
+ /**
+ * @brief get the matched name components
+ * @returns the matched name components
+ */
+ const std::vector<Name::Component>&
+ getMatchResult() const
+ { return m_matchResult; }
+
+ const std::string&
+ getExpr() const
+ { return m_expr; }
+
+protected:
+ /**
+ * @brief Compile the regular expression to generate the more matchers when necessary
+ * @returns true if compiling succeeds
+ */
+ virtual void
+ compile() = 0;
+
+private:
+ bool
+ recursiveMatch(const int& mId, const Name& name, const int& offset, const int& len);
+
+
+protected:
+ const std::string m_expr;
+ const RegexExprType m_type;
+ ptr_lib::shared_ptr<RegexBackrefManager> m_backrefManager;
+ std::vector<ptr_lib::shared_ptr<RegexMatcher> > m_matcherList;
+ std::vector<Name::Component> m_matchResult;
+
+};
+}//ndn
+
+
+#endif
diff --git a/src/util/regex/regex-pattern-list-matcher.cpp b/src/util/regex/regex-pattern-list-matcher.cpp
new file mode 100644
index 0000000..28f0037
--- /dev/null
+++ b/src/util/regex/regex-pattern-list-matcher.cpp
@@ -0,0 +1,162 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "regex-pattern-list-matcher.hpp"
+#include "regex-backref-matcher.hpp"
+#include "regex-repeat-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexPatternListMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+RegexPatternListMatcher::RegexPatternListMatcher(const string expr, ptr_lib::shared_ptr<RegexBackrefManager> backrefManager)
+ :RegexMatcher(expr, EXPR_PATTERNLIST, backrefManager)
+{
+ // _LOG_TRACE ("Enter RegexPatternListMatcher Constructor");
+ compile();
+ // _LOG_TRACE ("Exit RegexPatternListMatcher Constructor");
+}
+
+void
+RegexPatternListMatcher::compile()
+{
+ // _LOG_TRACE ("Enter RegexPatternListMatcher::compile");
+
+ const int len = m_expr.size();
+ int index = 0;
+ int subHead = index;
+
+ while(index < len){
+ subHead = index;
+
+ if(!extractPattern(subHead, &index))
+ throw RegexMatcher::Error("RegexPatternListMatcher compile: cannot compile");
+ }
+ // _LOG_TRACE ("Exit RegexPatternListMatcher::compile");
+}
+
+bool
+RegexPatternListMatcher::extractPattern(int index, int* next)
+{
+ // _LOG_DEBUG ("Enter RegexPatternListMatcher::ExtractPattern()");
+
+ string errMsg = "Error: RegexPatternListMatcher.ExtractSubPattern(): ";
+
+ const int start = index;
+ int end = index;
+ int indicator = index;
+
+
+ // _LOG_DEBUG ("m_expr: " << m_expr << " index: " << index);
+
+ switch(m_expr[index]){
+ case '(':
+ index++;
+ index = extractSubPattern('(', ')', index);
+ indicator = index;
+ end = extractRepetition(index);
+ if(indicator == end){
+ ptr_lib::shared_ptr<RegexMatcher> matcher = ptr_lib::make_shared<RegexBackrefMatcher>(m_expr.substr(start, end - start), m_backrefManager);
+ m_backrefManager->pushRef(matcher);
+ boost::dynamic_pointer_cast<RegexBackrefMatcher>(matcher)->lateCompile();
+
+ m_matcherList.push_back(matcher);
+ }
+ else
+ m_matcherList.push_back(ptr_lib::make_shared<RegexRepeatMatcher>(m_expr.substr(start, end - start), m_backrefManager, indicator - start));
+ break;
+
+ case '<':
+ index++;
+ index = extractSubPattern ('<', '>', index);
+ indicator = index;
+ end = extractRepetition(index);
+ m_matcherList.push_back(ptr_lib::make_shared<RegexRepeatMatcher>(m_expr.substr(start, end - start), m_backrefManager, indicator - start));
+ break;
+
+ case '[':
+ index++;
+ index = extractSubPattern ('[', ']', index);
+ indicator = index;
+ end = extractRepetition(index);
+ m_matcherList.push_back(ptr_lib::make_shared<RegexRepeatMatcher>(m_expr.substr(start, end - start), m_backrefManager, indicator - start));
+ break;
+
+ default:
+ throw RegexMatcher::Error("Error: unexpected syntax");
+ }
+
+ *next = end;
+
+ return true;
+}
+
+int
+RegexPatternListMatcher::extractSubPattern(const char left, const char right, int index)
+{
+ // _LOG_DEBUG ("Enter RegexPatternListMatcher::ExtractSubPattern()");
+
+ int lcount = 1;
+ int rcount = 0;
+
+ while(lcount > rcount){
+
+ if(index >= m_expr.size())
+ throw RegexMatcher::Error("Error: parenthesis mismatch");
+
+ if(left == m_expr[index])
+ lcount++;
+
+ if(right == m_expr[index])
+ rcount++;
+
+ index++;
+ }
+ return index;
+}
+
+int
+RegexPatternListMatcher::extractRepetition(int index)
+{
+ // _LOG_DEBUG ("Enter RegexPatternListMatcher::ExtractRepetition()");
+
+ int exprSize = m_expr.size();
+
+ // _LOG_DEBUG ("expr: " << m_expr << " index: " << index << " char: " << (index == exprSize ? 0 : m_expr[index]));
+
+ string errMsg = "Error: RegexPatternListMatcher.ExtractRepetition(): ";
+
+ if(index == exprSize)
+ return index;
+
+ if(('+' == m_expr[index] || '?' == m_expr[index] || '*' == m_expr[index])){
+ return ++index;
+ }
+
+
+ if('{' == m_expr[index]){
+ while('}' != m_expr[index]){
+ index++;
+ if(index == exprSize)
+ break;
+ }
+ if(index == exprSize)
+ throw RegexMatcher::Error(errMsg + "Missing right brace bracket");
+ else
+ return ++index;
+ }
+ else{
+ // _LOG_DEBUG ("return index: " << index);
+ return index;
+ }
+}
+
+}//ndn
diff --git a/src/util/regex/regex-pattern-list-matcher.hpp b/src/util/regex/regex-pattern-list-matcher.hpp
new file mode 100644
index 0000000..7240905
--- /dev/null
+++ b/src/util/regex/regex-pattern-list-matcher.hpp
@@ -0,0 +1,44 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_PATTERN_LIST_MATCHER_HPP
+#define NDN_REGEX_PATTERN_LIST_MATCHER_HPP
+
+#include <string>
+
+#include "regex-matcher.hpp"
+
+namespace ndn
+{
+
+class RegexPatternListMatcher : public RegexMatcher
+{
+public:
+ RegexPatternListMatcher(const std::string expr, ptr_lib::shared_ptr<RegexBackrefManager> backRefManager);
+
+ virtual ~RegexPatternListMatcher(){};
+
+protected:
+ virtual void
+ compile();
+
+private:
+ bool
+ extractPattern(int index, int* next);
+
+ int
+ extractSubPattern(const char left, const char right, int index);
+
+ int
+ extractRepetition(int index);
+
+private:
+
+};
+}//ndn
+
+#endif
diff --git a/src/util/regex/regex-pseudo-matcher.cpp b/src/util/regex/regex-pseudo-matcher.cpp
new file mode 100644
index 0000000..abebaff
--- /dev/null
+++ b/src/util/regex/regex-pseudo-matcher.cpp
@@ -0,0 +1,30 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include "regex-pseudo-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexPseudoMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+RegexPseudoMatcher::RegexPseudoMatcher()
+ :RegexMatcher ("", EXPR_PSEUDO)
+{}
+
+void
+RegexPseudoMatcher::setMatchResult(const string & str)
+{ m_matchResult.push_back(Name::Component((const uint8_t *)str.c_str(), str.size())); }
+
+void
+RegexPseudoMatcher::resetMatchResult()
+{ m_matchResult.clear(); }
+
+}//ndn
diff --git a/src/util/regex/regex-pseudo-matcher.hpp b/src/util/regex/regex-pseudo-matcher.hpp
new file mode 100644
index 0000000..9bb1e9f
--- /dev/null
+++ b/src/util/regex/regex-pseudo-matcher.hpp
@@ -0,0 +1,36 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_PSEUDO_MATCHER_HPP
+#define NDN_REGEX_PSEUDO_MATCHER_HPP
+
+#include "regex-matcher.hpp"
+
+namespace ndn
+{
+class RegexPseudoMatcher : public RegexMatcher
+{
+public:
+ RegexPseudoMatcher();
+
+ ~RegexPseudoMatcher()
+ {}
+
+ virtual void
+ compile()
+ {}
+
+ void
+ setMatchResult(const std::string& str);
+
+ void
+ resetMatchResult();
+};
+
+}//ndn
+
+#endif
diff --git a/src/util/regex/regex-repeat-matcher.cpp b/src/util/regex/regex-repeat-matcher.cpp
new file mode 100644
index 0000000..d121b9e
--- /dev/null
+++ b/src/util/regex/regex-repeat-matcher.cpp
@@ -0,0 +1,193 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include <limits>
+#include <stdlib.h>
+
+#include <boost/regex.hpp>
+
+#include "regex-repeat-matcher.hpp"
+#include "regex-backref-matcher.hpp"
+#include "regex-component-set-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexRepeatMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+RegexRepeatMatcher::RegexRepeatMatcher(const string expr, ptr_lib::shared_ptr<RegexBackrefManager> backrefManager, int indicator)
+ : RegexMatcher (expr, EXPR_REPEAT_PATTERN, backrefManager),
+ m_indicator(indicator)
+{
+ // _LOG_TRACE ("Enter RegexRepeatMatcher Constructor");
+ compile();
+ // _LOG_TRACE ("Exit RegexRepeatMatcher Constructor");
+}
+
+void
+RegexRepeatMatcher::compile()
+{
+ // _LOG_TRACE ("Enter RegexRepeatMatcher::compile");
+
+ ptr_lib::shared_ptr<RegexMatcher> matcher;
+
+ if('(' == m_expr[0]){
+ matcher = ptr_lib::make_shared<RegexBackrefMatcher>(m_expr.substr(0, m_indicator), m_backrefManager);
+ m_backrefManager->pushRef(matcher);
+ boost::dynamic_pointer_cast<RegexBackrefMatcher>(matcher)->lateCompile();
+ }
+ else{
+ matcher = ptr_lib::make_shared<RegexComponentSetMatcher>(m_expr.substr(0, m_indicator), m_backrefManager);
+ }
+ m_matcherList.push_back(matcher);
+
+ parseRepetition();
+
+ // _LOG_TRACE ("Exit RegexRepeatMatcher::compile");
+
+}
+
+bool
+RegexRepeatMatcher::parseRepetition()
+{
+ // _LOG_DEBUG ("Enter RegexRepeatMatcher::ParseRepetition()" << m_expr << " indicator: " << m_indicator);
+
+ string errMsg = "Error: RegexRepeatMatcher.ParseRepetition(): ";
+
+ int exprSize = m_expr.size();
+ int intMax = numeric_limits<int>::max();
+
+ if(exprSize == m_indicator){
+ m_repeatMin = 1;
+ m_repeatMax = 1;
+
+ return true;
+ }
+ else{
+ if(exprSize == (m_indicator + 1)){
+ if('?' == m_expr[m_indicator]){
+ m_repeatMin = 0;
+ m_repeatMax = 1;
+ return true;
+ }
+ if('+' == m_expr[m_indicator]){
+ m_repeatMin = 1;
+ m_repeatMax = intMax;
+ return true;
+ }
+ if('*' == m_expr[m_indicator]){
+ m_repeatMin = 0;
+ m_repeatMax = intMax;
+ return true;
+ }
+ }
+ else{
+ string repeatStruct = m_expr.substr(m_indicator, exprSize - m_indicator);
+ int rsSize = repeatStruct.size();
+ int min = 0;
+ int max = 0;
+
+ if(boost::regex_match(repeatStruct, boost::regex("\\{[0-9]+,[0-9]+\\}"))){
+ int separator = repeatStruct.find_first_of(',', 0);
+ min = atoi(repeatStruct.substr(1, separator - 1).c_str());
+ max = atoi(repeatStruct.substr(separator + 1, rsSize - separator - 2).c_str());
+ }
+ else if(boost::regex_match(repeatStruct, boost::regex("\\{,[0-9]+\\}"))){
+ int separator = repeatStruct.find_first_of(',', 0);
+ min = 0;
+ max = atoi(repeatStruct.substr(separator + 1, rsSize - separator - 2).c_str());
+ }
+ else if(boost::regex_match(repeatStruct, boost::regex("\\{[0-9]+,\\}"))){
+ int separator = repeatStruct.find_first_of(',', 0);
+ min = atoi(repeatStruct.substr(1, separator).c_str());
+ max = intMax;
+ }
+ else if(boost::regex_match(repeatStruct, boost::regex("\\{[0-9]+\\}"))){
+ min = atoi(repeatStruct.substr(1, rsSize - 1).c_str());
+ max = min;
+ }
+ else
+ throw RegexMatcher::Error(errMsg + "Unrecognized format "+ m_expr);
+
+ if(min > intMax || max > intMax || min > max)
+ throw RegexMatcher::Error(errMsg + "Wrong number " + m_expr);
+
+ m_repeatMin = min;
+ m_repeatMax = max;
+
+ return true;
+ }
+ }
+ return false;
+}
+
+bool
+RegexRepeatMatcher::match(const Name & name, const int & offset, const int & len)
+{
+ // _LOG_TRACE ("Enter RegexRepeatMatcher::match");
+
+ m_matchResult.clear();
+
+ if (0 == m_repeatMin)
+ if (0 == len)
+ return true;
+
+ if (recursiveMatch(0, name, offset, len))
+ {
+ for (int i = offset; i < offset + len; i++)
+ m_matchResult.push_back(name.get(i));
+ return true;
+ }
+ else
+ return false;
+}
+
+bool
+RegexRepeatMatcher::recursiveMatch(int repeat, const Name & name, const int & offset, const int & len)
+{
+ // _LOG_TRACE ("Enter RegexRepeatMatcher::recursiveMatch");
+
+ // _LOG_DEBUG ("repeat: " << repeat << " offset: " << offset << " len: " << len);
+ // _LOG_DEBUG ("m_repeatMin: " << m_repeatMin << " m_repeatMax: " << m_repeatMax);
+
+ int tried = len;
+ ptr_lib::shared_ptr<RegexMatcher> matcher = m_matcherList[0];
+
+ if (0 < len && repeat >= m_repeatMax)
+ {
+ // _LOG_DEBUG("Match Fail: Reach m_repeatMax && More components");
+ return false;
+ }
+
+ if (0 == len && repeat < m_repeatMin)
+ {
+ // _LOG_DEBUG("Match Fail: No more components && have NOT reached m_repeatMin " << len << ", " << m_repeatMin);
+ return false;
+ }
+
+ if (0 == len && repeat >= m_repeatMin)
+ {
+ // _LOG_DEBUG("Match Succeed: No more components && reach m_repeatMin");
+ return true;
+ }
+
+ while(tried >= 0)
+ {
+ // _LOG_DEBUG("Attempt tried: " << tried);
+
+ if (matcher->match(name, offset, tried) and recursiveMatch(repeat + 1, name, offset + tried, len - tried))
+ return true;
+ // _LOG_DEBUG("Failed at tried: " << tried);
+ tried --;
+ }
+
+ return false;
+}
+}//ndn
diff --git a/src/util/regex/regex-repeat-matcher.hpp b/src/util/regex/regex-repeat-matcher.hpp
new file mode 100644
index 0000000..9cc0212
--- /dev/null
+++ b/src/util/regex/regex-repeat-matcher.hpp
@@ -0,0 +1,53 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_REPEAT_MATCHER_HPP
+#define NDN_REGEX_REPEAT_MATCHER_HPP
+
+#include "regex-matcher.hpp"
+
+namespace ndn
+{
+
+class RegexRepeatMatcher : public RegexMatcher
+{
+public:
+ RegexRepeatMatcher(const std::string expr, ptr_lib::shared_ptr<RegexBackrefManager> backRefManager, int indicator);
+
+ virtual ~RegexRepeatMatcher(){}
+
+ virtual bool
+ match(const Name & name, const int & offset, const int & len);
+
+protected:
+ /**
+ * @brief Compile the regular expression to generate the more matchers when necessary
+ * @returns true if compiling succeeds
+ */
+ virtual void
+ compile();
+
+
+private:
+ bool
+ parseRepetition();
+
+ bool
+ recursiveMatch (int repeat,
+ const Name & name,
+ const int & offset,
+ const int &len);
+
+private:
+ int m_indicator;
+ int m_repeatMin;
+ int m_repeatMax;
+};
+
+}//ndn
+
+#endif
diff --git a/src/util/regex/regex-top-matcher.cpp b/src/util/regex/regex-top-matcher.cpp
new file mode 100644
index 0000000..3e7d4ce
--- /dev/null
+++ b/src/util/regex/regex-top-matcher.cpp
@@ -0,0 +1,246 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#include <stdlib.h>
+
+#include "regex-top-matcher.hpp"
+
+#include "../logging.hpp"
+
+INIT_LOGGER ("RegexTopMatcher");
+
+using namespace std;
+
+namespace ndn
+{
+
+RegexTopMatcher::RegexTopMatcher(const string & expr, const string & expand)
+ : RegexMatcher(expr, EXPR_TOP),
+ m_expand(expand),
+ m_secondaryUsed(false)
+{
+ // _LOG_TRACE ("Enter RegexTopMatcher Constructor");
+
+ m_primaryBackRefManager = ptr_lib::make_shared<RegexBackrefManager>();
+ m_secondaryBackRefManager = ptr_lib::make_shared<RegexBackrefManager>();
+ compile();
+
+ // _LOG_TRACE ("Exit RegexTopMatcher Constructor");
+}
+
+RegexTopMatcher::~RegexTopMatcher()
+{
+ // delete m_backRefManager;
+}
+
+void
+RegexTopMatcher::compile()
+{
+ // _LOG_TRACE ("Enter RegexTopMatcher::compile");
+
+ string errMsg = "Error: RegexTopMatcher.Compile(): ";
+
+ string expr = m_expr;
+
+ if('$' != expr[expr.size() - 1])
+ expr = expr + "<.*>*";
+ else
+ expr = expr.substr(0, expr.size()-1);
+
+ if('^' != expr[0])
+ m_secondaryMatcher = ptr_lib::make_shared<RegexPatternListMatcher>("<.*>*" + expr, m_secondaryBackRefManager);
+ else
+ expr = expr.substr(1, expr.size()-1);
+
+ // _LOG_DEBUG ("reconstructed expr: " << expr);
+
+
+ m_primaryMatcher = ptr_lib::make_shared<RegexPatternListMatcher>(expr, m_primaryBackRefManager);
+
+ // _LOG_TRACE ("Exit RegexTopMatcher::compile");
+}
+
+bool
+RegexTopMatcher::match(const Name & name)
+{
+ // _LOG_DEBUG("Enter RegexTopMatcher::match");
+
+ m_secondaryUsed = false;
+
+ m_matchResult.clear();
+
+ if(m_primaryMatcher->match(name, 0, name.size()))
+ {
+ m_matchResult = m_primaryMatcher->getMatchResult();
+ return true;
+ }
+ else
+ {
+ if (NULL != m_secondaryMatcher && m_secondaryMatcher->match(name, 0, name.size()))
+ {
+ m_matchResult = m_secondaryMatcher->getMatchResult();
+ m_secondaryUsed = true;
+ return true;
+ }
+ return false;
+ }
+}
+
+bool
+RegexTopMatcher::match (const Name & name, const int & offset, const int & len)
+{
+ return match(name);
+}
+
+Name
+RegexTopMatcher::expand (const string & expandStr)
+{
+ // _LOG_TRACE("Enter RegexTopMatcher::expand");
+
+ Name result;
+
+ ptr_lib::shared_ptr<RegexBackrefManager> backRefManager = (m_secondaryUsed ? m_secondaryBackRefManager : m_primaryBackRefManager);
+
+ int backRefNum = backRefManager->size();
+
+ string expand;
+
+ if(expandStr != "")
+ expand = expandStr;
+ else
+ expand = m_expand;
+
+ int offset = 0;
+ while(offset < expand.size())
+ {
+ string item = getItemFromExpand(expand, offset);
+ if(item[0] == '<')
+ {
+ result.append(item.substr(1, item.size() - 2));
+ }
+ if(item[0] == '\\')
+ {
+
+ int index = atoi(item.substr(1, item.size() - 1).c_str());
+
+ if(0 == index){
+ vector<Name::Component>::iterator it = m_matchResult.begin();
+ vector<Name::Component>::iterator end = m_matchResult.end();
+ for(; it != end; it++)
+ result.append (*it);
+ }
+ else if(index <= backRefNum)
+ {
+ vector<Name::Component>::const_iterator it = backRefManager->getBackRef (index - 1)->getMatchResult ().begin();
+ vector<Name::Component>::const_iterator end = backRefManager->getBackRef (index - 1)->getMatchResult ().end();
+ for(; it != end; it++)
+ result.append (*it);
+ }
+ else
+ throw RegexMatcher::Error("Exceed the range of back reference!");
+ }
+ }
+ return result;
+}
+
+string
+RegexTopMatcher::getItemFromExpand(const string & expand, int & offset)
+{
+ // _LOG_TRACE("Enter RegexTopMatcher::getItemFromExpand ");
+ int begin = offset;
+
+ if(expand[offset] == '\\')
+ {
+ offset++;
+ if(offset >= expand.size())
+ throw RegexMatcher::Error("wrong format of expand string!");
+
+ while(expand[offset] <= '9' and expand[offset] >= '0'){
+ offset++;
+ if(offset > expand.size())
+ throw RegexMatcher::Error("wrong format of expand string!");
+ }
+ if(offset > begin + 1)
+ return expand.substr(begin, offset - begin);
+ else
+ throw RegexMatcher::Error("wrong format of expand string!");
+ }
+ else if(expand[offset] == '<')
+ {
+ offset++;
+ if(offset >= expand.size())
+ throw RegexMatcher::Error("wrong format of expand string!");
+
+ int left = 1;
+ int right = 0;
+ while(right < left)
+ {
+ if(expand[offset] == '<')
+ left++;
+ if(expand[offset] == '>')
+ right++;
+ offset++;
+ if(offset >= expand.size())
+ throw RegexMatcher::Error("wrong format of expand string!");
+ }
+ return expand.substr(begin, offset - begin);
+ }
+ else
+ throw RegexMatcher::Error("wrong format of expand string!");
+}
+
+ptr_lib::shared_ptr<RegexTopMatcher>
+RegexTopMatcher::fromName(const Name& name, bool hasAnchor)
+{
+ Name::const_iterator it = name.begin();
+ string regexStr("^");
+
+ for(; it != name.end(); it++)
+ {
+ regexStr.append("<");
+ regexStr.append(convertSpecialChar(it->toEscapedString()));
+ regexStr.append(">");
+ }
+
+ if(hasAnchor)
+ regexStr.append("$");
+
+ return ptr_lib::make_shared<RegexTopMatcher>(regexStr);
+}
+
+string
+RegexTopMatcher::convertSpecialChar(const string& str)
+{
+ string newStr;
+ for(int i = 0; i < str.size(); i++)
+ {
+ char c = str[i];
+ switch(c)
+ {
+ case '.':
+ case '[':
+ case '{':
+ case '}':
+ case '(':
+ case ')':
+ case '\\':
+ case '*':
+ case '+':
+ case '?':
+ case '|':
+ case '^':
+ case '$':
+ newStr.push_back('\\');
+ default:
+ newStr.push_back(c);
+ }
+ }
+
+ return newStr;
+}
+
+}//ndn
diff --git a/src/util/regex/regex-top-matcher.hpp b/src/util/regex/regex-top-matcher.hpp
new file mode 100644
index 0000000..764726f
--- /dev/null
+++ b/src/util/regex/regex-top-matcher.hpp
@@ -0,0 +1,60 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
+/**
+ * Copyright (C) 2013 Regents of the University of California.
+ * @author: Yingdi Yu <yingdi@cs.ucla.edu>
+ * See COPYING for copyright and distribution information.
+ */
+
+#ifndef NDN_REGEX_TOP_MATCHER_HPP
+#define NDN_REGEX_TOP_MATCHER_HPP
+
+#include <string>
+
+#include "regex-matcher.hpp"
+#include "regex-pattern-list-matcher.hpp"
+
+namespace ndn
+{
+class RegexTopMatcher: public RegexMatcher
+{
+public:
+ RegexTopMatcher(const std::string & expr, const std::string & expand = "");
+
+ virtual ~RegexTopMatcher();
+
+ bool
+ match(const Name & name);
+
+ virtual bool
+ match (const Name & name, const int & offset, const int & len);
+
+ virtual Name
+ expand (const std::string & expand = "");
+
+ static ptr_lib::shared_ptr<RegexTopMatcher>
+ fromName(const Name& name, bool hasAnchor=false);
+
+protected:
+ virtual void
+ compile();
+
+private:
+ std::string
+ getItemFromExpand(const std::string & expand, int & offset);
+
+ static std::string
+ convertSpecialChar(const std::string& str);
+
+private:
+ const std::string m_expand;
+ ptr_lib::shared_ptr<RegexPatternListMatcher> m_primaryMatcher;
+ ptr_lib::shared_ptr<RegexPatternListMatcher> m_secondaryMatcher;
+ ptr_lib::shared_ptr<RegexBackrefManager> m_primaryBackRefManager;
+ ptr_lib::shared_ptr<RegexBackrefManager> m_secondaryBackRefManager;
+ bool m_secondaryUsed;
+};
+
+}
+
+#endif
+