blob: 30b755f35d7d91eb57e1ed331b9bb2fd29f2f71c [file] [log] [blame]
Alexander Afanasyevc169a812014-05-20 20:37:29 -04001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
Yingdi Yu5e974202014-01-29 16:59:06 -08002/**
Alexander Afanasyevc169a812014-05-20 20:37:29 -04003 * Copyright (c) 2013-2014 Regents of the University of California.
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -07004 *
5 * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -07006 *
Alexander Afanasyevc169a812014-05-20 20:37:29 -04007 * ndn-cxx library is free software: you can redistribute it and/or modify it under the
8 * terms of the GNU Lesser General Public License as published by the Free Software
9 * Foundation, either version 3 of the License, or (at your option) any later version.
10 *
11 * ndn-cxx library is distributed in the hope that it will be useful, but WITHOUT ANY
12 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
13 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
14 *
15 * You should have received copies of the GNU General Public License and GNU Lesser
16 * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
17 * <http://www.gnu.org/licenses/>.
18 *
19 * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -070020 *
21 * @author Yingdi Yu <http://irl.cs.ucla.edu/~yingdi/>
Yingdi Yu5e974202014-01-29 16:59:06 -080022 */
23
Yingdi Yu5e974202014-01-29 16:59:06 -080024#include "regex-top-matcher.hpp"
25
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080026#include "regex-backref-manager.hpp"
27#include "regex-pattern-list-matcher.hpp"
Yingdi Yu5e974202014-01-29 16:59:06 -080028
Alexander Afanasyev258ec2b2014-05-14 16:15:37 -070029#include <boost/lexical_cast.hpp>
30
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080031namespace ndn {
Yingdi Yu5e974202014-01-29 16:59:06 -080032
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080033RegexTopMatcher::RegexTopMatcher(const std::string& expr, const std::string& expand)
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070034 : RegexMatcher(expr, EXPR_TOP)
35 , m_expand(expand)
36 , m_isSecondaryUsed(false)
Yingdi Yu5e974202014-01-29 16:59:06 -080037{
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070038 m_primaryBackrefManager = make_shared<RegexBackrefManager>();
39 m_secondaryBackrefManager = make_shared<RegexBackrefManager>();
Yingdi Yu5e974202014-01-29 16:59:06 -080040 compile();
Yingdi Yu5e974202014-01-29 16:59:06 -080041}
42
43RegexTopMatcher::~RegexTopMatcher()
44{
Yingdi Yu5e974202014-01-29 16:59:06 -080045}
46
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070047void
Yingdi Yu5e974202014-01-29 16:59:06 -080048RegexTopMatcher::compile()
49{
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080050 std::string errMsg = "Error: RegexTopMatcher.Compile(): ";
Yingdi Yu5e974202014-01-29 16:59:06 -080051
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080052 std::string expr = m_expr;
Yingdi Yu5e974202014-01-29 16:59:06 -080053
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070054 if ('$' != expr[expr.size() - 1])
Yingdi Yu5e974202014-01-29 16:59:06 -080055 expr = expr + "<.*>*";
56 else
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070057 expr = expr.substr(0, expr.size() - 1);
Yingdi Yu5e974202014-01-29 16:59:06 -080058
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070059 if ('^' != expr[0]) {
60 m_secondaryMatcher = make_shared<RegexPatternListMatcher>(
61 "<.*>*" + expr,
Alexander Afanasyevf73f0632014-05-12 18:02:37 -070062 m_secondaryBackrefManager);
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070063 }
64 else {
65 expr = expr.substr(1, expr.size() - 1);
66 }
Yingdi Yu5e974202014-01-29 16:59:06 -080067
Alexander Afanasyevf73f0632014-05-12 18:02:37 -070068 // On OSX 10.9, boost, and C++03 the following doesn't work without ndn::
69 // because the argument-dependent lookup prefers STL to boost
70 m_primaryMatcher = ndn::make_shared<RegexPatternListMatcher>(expr,
71 m_primaryBackrefManager);
Yingdi Yu5e974202014-01-29 16:59:06 -080072}
73
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070074bool
75RegexTopMatcher::match(const Name& name)
Yingdi Yu5e974202014-01-29 16:59:06 -080076{
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070077 m_isSecondaryUsed = false;
Yingdi Yu5e974202014-01-29 16:59:06 -080078
79 m_matchResult.clear();
80
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070081 if (m_primaryMatcher->match(name, 0, name.size()))
Yingdi Yu5e974202014-01-29 16:59:06 -080082 {
83 m_matchResult = m_primaryMatcher->getMatchResult();
84 return true;
85 }
86 else
87 {
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070088 if (static_cast<bool>(m_secondaryMatcher) && m_secondaryMatcher->match(name, 0, name.size()))
Yingdi Yu5e974202014-01-29 16:59:06 -080089 {
90 m_matchResult = m_secondaryMatcher->getMatchResult();
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070091 m_isSecondaryUsed = true;
Yingdi Yu5e974202014-01-29 16:59:06 -080092 return true;
93 }
94 return false;
95 }
96}
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070097
98bool
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070099RegexTopMatcher::match(const Name& name, size_t, size_t)
Yingdi Yu5e974202014-01-29 16:59:06 -0800100{
101 return match(name);
102}
103
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700104Name
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700105RegexTopMatcher::expand(const std::string& expandStr)
Yingdi Yu5e974202014-01-29 16:59:06 -0800106{
Yingdi Yu5e974202014-01-29 16:59:06 -0800107 Name result;
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700108
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700109 shared_ptr<RegexBackrefManager> backrefManager =
110 (m_isSecondaryUsed ? m_secondaryBackrefManager : m_primaryBackrefManager);
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700111
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700112 size_t backrefNo = backrefManager->size();
Yingdi Yu5e974202014-01-29 16:59:06 -0800113
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800114 std::string expand;
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700115
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700116 if (!expandStr.empty())
Yingdi Yu5e974202014-01-29 16:59:06 -0800117 expand = expandStr;
118 else
119 expand = m_expand;
120
Alexander Afanasyev1dd95c52014-03-22 19:11:36 -0700121 size_t offset = 0;
122 while (offset < expand.size())
Yingdi Yu5e974202014-01-29 16:59:06 -0800123 {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800124 std::string item = getItemFromExpand(expand, offset);
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700125 if (item[0] == '<')
Yingdi Yu5e974202014-01-29 16:59:06 -0800126 {
127 result.append(item.substr(1, item.size() - 2));
128 }
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700129 if (item[0] == '\\')
Yingdi Yu5e974202014-01-29 16:59:06 -0800130 {
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700131 size_t index = boost::lexical_cast<size_t>(item.substr(1, item.size() - 1));
Yingdi Yu5e974202014-01-29 16:59:06 -0800132
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700133 if (0 == index) {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800134 std::vector<name::Component>::iterator it = m_matchResult.begin();
135 std::vector<name::Component>::iterator end = m_matchResult.end();
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700136 for (; it != end; it++)
137 result.append(*it);
Yingdi Yu5e974202014-01-29 16:59:06 -0800138 }
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700139 else if (index <= backrefNo)
Yingdi Yu5e974202014-01-29 16:59:06 -0800140 {
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -0700141 std::vector<name::Component>::const_iterator it =
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700142 backrefManager->getBackref(index - 1)->getMatchResult().begin();
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -0700143 std::vector<name::Component>::const_iterator end =
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700144 backrefManager->getBackref(index - 1)->getMatchResult().end();
145 for (; it != end; it++)
146 result.append(*it);
Yingdi Yu5e974202014-01-29 16:59:06 -0800147 }
148 else
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700149 BOOST_THROW_EXCEPTION(RegexMatcher::Error("Exceed the range of back reference"));
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700150 }
Yingdi Yu5e974202014-01-29 16:59:06 -0800151 }
152 return result;
153}
154
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800155std::string
Alexander Afanasyev1dd95c52014-03-22 19:11:36 -0700156RegexTopMatcher::getItemFromExpand(const std::string& expand, size_t& offset)
Yingdi Yu5e974202014-01-29 16:59:06 -0800157{
Alexander Afanasyev1dd95c52014-03-22 19:11:36 -0700158 size_t begin = offset;
Yingdi Yu5e974202014-01-29 16:59:06 -0800159
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700160 if (expand[offset] == '\\')
Yingdi Yu5e974202014-01-29 16:59:06 -0800161 {
162 offset++;
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700163 if (offset >= expand.size())
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700164 BOOST_THROW_EXCEPTION(RegexMatcher::Error("wrong format of expand string!"));
Yingdi Yu5e974202014-01-29 16:59:06 -0800165
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700166 while (expand[offset] <= '9' and expand[offset] >= '0') {
Yingdi Yu5e974202014-01-29 16:59:06 -0800167 offset++;
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700168 if (offset > expand.size())
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700169 BOOST_THROW_EXCEPTION(RegexMatcher::Error("wrong format of expand string!"));
Yingdi Yu5e974202014-01-29 16:59:06 -0800170 }
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700171 if (offset > begin + 1)
Yingdi Yu5e974202014-01-29 16:59:06 -0800172 return expand.substr(begin, offset - begin);
173 else
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700174 BOOST_THROW_EXCEPTION(RegexMatcher::Error("wrong format of expand string!"));
Yingdi Yu5e974202014-01-29 16:59:06 -0800175 }
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700176 else if (expand[offset] == '<')
Yingdi Yu5e974202014-01-29 16:59:06 -0800177 {
178 offset++;
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700179 if (offset >= expand.size())
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700180 BOOST_THROW_EXCEPTION(RegexMatcher::Error("wrong format of expand string!"));
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700181
Alexander Afanasyev1dd95c52014-03-22 19:11:36 -0700182 size_t left = 1;
183 size_t right = 0;
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700184 while (right < left)
Yingdi Yu5e974202014-01-29 16:59:06 -0800185 {
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700186 if (expand[offset] == '<')
Yingdi Yu5e974202014-01-29 16:59:06 -0800187 left++;
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700188 if (expand[offset] == '>')
189 right++;
Yingdi Yu5e974202014-01-29 16:59:06 -0800190 offset++;
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700191 if (offset >= expand.size())
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700192 BOOST_THROW_EXCEPTION(RegexMatcher::Error("wrong format of expand string!"));
Yingdi Yu5e974202014-01-29 16:59:06 -0800193 }
194 return expand.substr(begin, offset - begin);
195 }
196 else
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700197 BOOST_THROW_EXCEPTION(RegexMatcher::Error("wrong format of expand string!"));
Yingdi Yu5e974202014-01-29 16:59:06 -0800198}
199
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800200shared_ptr<RegexTopMatcher>
Yingdi Yu5e974202014-01-29 16:59:06 -0800201RegexTopMatcher::fromName(const Name& name, bool hasAnchor)
202{
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800203 std::string regexStr("^");
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700204
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700205 for (Name::const_iterator it = name.begin(); it != name.end(); it++)
Yingdi Yu5e974202014-01-29 16:59:06 -0800206 {
207 regexStr.append("<");
Alexander Afanasyev9c578182014-05-14 17:28:28 -0700208 regexStr.append(convertSpecialChar(it->toUri()));
Yingdi Yu5e974202014-01-29 16:59:06 -0800209 regexStr.append(">");
210 }
211
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700212 if (hasAnchor)
Yingdi Yu5e974202014-01-29 16:59:06 -0800213 regexStr.append("$");
214
Alexander Afanasyevf73f0632014-05-12 18:02:37 -0700215 // On OSX 10.9, boost, and C++03 the following doesn't work without ndn::
216 // because the argument-dependent lookup prefers STL to boost
217 return ndn::make_shared<RegexTopMatcher>(regexStr);
Yingdi Yu5e974202014-01-29 16:59:06 -0800218}
219
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800220std::string
221RegexTopMatcher::convertSpecialChar(const std::string& str)
Yingdi Yu5e974202014-01-29 16:59:06 -0800222{
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800223 std::string newStr;
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700224 for (size_t i = 0; i < str.size(); i++)
Yingdi Yu5e974202014-01-29 16:59:06 -0800225 {
226 char c = str[i];
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700227 switch (c)
Yingdi Yu5e974202014-01-29 16:59:06 -0800228 {
229 case '.':
230 case '[':
231 case '{':
232 case '}':
233 case '(':
234 case ')':
235 case '\\':
236 case '*':
237 case '+':
238 case '?':
239 case '|':
240 case '^':
241 case '$':
242 newStr.push_back('\\');
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700243 // Fallthrough
Yingdi Yu5e974202014-01-29 16:59:06 -0800244 default:
245 newStr.push_back(c);
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700246 break;
Yingdi Yu5e974202014-01-29 16:59:06 -0800247 }
248 }
249
250 return newStr;
251}
252
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700253} // namespace ndn