blob: 530721e0f426c8a3aa357e4e4e00725bee3e1dc7 [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
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080024#ifndef NDN_UTIL_REGEX_REGEX_REPEAT_MATCHER_HPP
25#define NDN_UTIL_REGEX_REGEX_REPEAT_MATCHER_HPP
26
27#include "../../common.hpp"
28
29#include <boost/regex.hpp>
Yingdi Yu5e974202014-01-29 16:59:06 -080030
31#include "regex-matcher.hpp"
32
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080033namespace ndn {
Yingdi Yu5e974202014-01-29 16:59:06 -080034
35class RegexRepeatMatcher : public RegexMatcher
36{
37public:
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -070038 RegexRepeatMatcher(const std::string& expr,
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070039 shared_ptr<RegexBackrefManager> backrefManager,
40 size_t indicator);
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070041
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -070042 virtual
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070043 ~RegexRepeatMatcher()
44 {
45 }
Yingdi Yu5e974202014-01-29 16:59:06 -080046
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070047 virtual bool
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070048 match(const Name& name, size_t offset, size_t len);
Yingdi Yu5e974202014-01-29 16:59:06 -080049
50protected:
51 /**
52 * @brief Compile the regular expression to generate the more matchers when necessary
53 * @returns true if compiling succeeds
54 */
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070055 virtual void
Yingdi Yu5e974202014-01-29 16:59:06 -080056 compile();
57
Yingdi Yu5e974202014-01-29 16:59:06 -080058private:
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070059 bool
Yingdi Yu5e974202014-01-29 16:59:06 -080060 parseRepetition();
61
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070062 bool
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070063 recursiveMatch(size_t repeat,
64 const Name& name,
65 size_t offset, size_t len);
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070066
Yingdi Yu5e974202014-01-29 16:59:06 -080067private:
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070068 size_t m_indicator;
69 size_t m_repeatMin;
70 size_t m_repeatMax;
Yingdi Yu5e974202014-01-29 16:59:06 -080071};
72
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080073} // namespace ndn
Yingdi Yu5e974202014-01-29 16:59:06 -080074
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080075#include "regex-backref-matcher.hpp"
76#include "regex-component-set-matcher.hpp"
77
78namespace ndn {
79
80inline
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -070081RegexRepeatMatcher::RegexRepeatMatcher(const std::string& expr,
82 shared_ptr<RegexBackrefManager> backrefManager,
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070083 size_t indicator)
84 : RegexMatcher(expr, EXPR_REPEAT_PATTERN, backrefManager)
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -070085 , m_indicator(indicator)
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080086{
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080087 compile();
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080088}
89
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070090inline void
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080091RegexRepeatMatcher::compile()
92{
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080093 shared_ptr<RegexMatcher> matcher;
94
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -070095 if ('(' == m_expr[0]) {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080096 matcher = make_shared<RegexBackrefMatcher>(m_expr.substr(0, m_indicator), m_backrefManager);
97 m_backrefManager->pushRef(matcher);
Alexander Afanasyevb67090a2014-04-29 22:31:01 -070098 dynamic_pointer_cast<RegexBackrefMatcher>(matcher)->lateCompile();
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080099 }
100 else{
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -0700101 matcher = make_shared<RegexComponentSetMatcher>(m_expr.substr(0, m_indicator),
102 m_backrefManager);
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800103 }
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700104 m_matchers.push_back(matcher);
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700105
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800106 parseRepetition();
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800107}
108
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700109inline bool
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800110RegexRepeatMatcher::parseRepetition()
111{
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700112 size_t exprSize = m_expr.size();
113 const size_t MAX_REPETITIONS = std::numeric_limits<size_t>::max();
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700114
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700115 if (exprSize == m_indicator) {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800116 m_repeatMin = 1;
117 m_repeatMax = 1;
118
119 return true;
120 }
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700121 else {
122 if (exprSize == (m_indicator + 1)) {
123 if ('?' == m_expr[m_indicator]) {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800124 m_repeatMin = 0;
125 m_repeatMax = 1;
126 return true;
127 }
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700128 if ('+' == m_expr[m_indicator]) {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800129 m_repeatMin = 1;
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700130 m_repeatMax = MAX_REPETITIONS;
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800131 return true;
132 }
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700133 if ('*' == m_expr[m_indicator]) {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800134 m_repeatMin = 0;
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700135 m_repeatMax = MAX_REPETITIONS;
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800136 return true;
137 }
138 }
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700139 else {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800140 std::string repeatStruct = m_expr.substr(m_indicator, exprSize - m_indicator);
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700141 size_t rsSize = repeatStruct.size();
142 size_t min = 0;
143 size_t max = 0;
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800144
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700145 if (boost::regex_match(repeatStruct, boost::regex("\\{[0-9]+,[0-9]+\\}"))) {
146 size_t separator = repeatStruct.find_first_of(',', 0);
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800147 min = atoi(repeatStruct.substr(1, separator - 1).c_str());
148 max = atoi(repeatStruct.substr(separator + 1, rsSize - separator - 2).c_str());
149 }
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700150 else if (boost::regex_match(repeatStruct, boost::regex("\\{,[0-9]+\\}"))) {
151 size_t separator = repeatStruct.find_first_of(',', 0);
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800152 min = 0;
153 max = atoi(repeatStruct.substr(separator + 1, rsSize - separator - 2).c_str());
154 }
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700155 else if (boost::regex_match(repeatStruct, boost::regex("\\{[0-9]+,\\}"))) {
156 size_t separator = repeatStruct.find_first_of(',', 0);
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800157 min = atoi(repeatStruct.substr(1, separator).c_str());
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700158 max = MAX_REPETITIONS;
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800159 }
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700160 else if (boost::regex_match(repeatStruct, boost::regex("\\{[0-9]+\\}"))) {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800161 min = atoi(repeatStruct.substr(1, rsSize - 1).c_str());
162 max = min;
163 }
164 else
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700165 BOOST_THROW_EXCEPTION(RegexMatcher::Error(std::string("Error: RegexRepeatMatcher.ParseRepetition():")
166 + " Unrecognized format "+ m_expr));
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700167
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700168 if (min > MAX_REPETITIONS || max > MAX_REPETITIONS || min > max)
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700169 BOOST_THROW_EXCEPTION(RegexMatcher::Error(std::string("Error: RegexRepeatMatcher.ParseRepetition():")
170 + " Wrong number " + m_expr));
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700171
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800172 m_repeatMin = min;
173 m_repeatMax = max;
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700174
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800175 return true;
176 }
177 }
178 return false;
179}
180
181inline bool
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700182RegexRepeatMatcher::match(const Name& name, size_t offset, size_t len)
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800183{
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800184 m_matchResult.clear();
185
186 if (0 == m_repeatMin)
187 if (0 == len)
188 return true;
189
190 if (recursiveMatch(0, name, offset, len))
191 {
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700192 for (size_t i = offset; i < offset + len; i++)
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800193 m_matchResult.push_back(name.get(i));
194 return true;
195 }
196 else
197 return false;
198}
199
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700200inline bool
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700201RegexRepeatMatcher::recursiveMatch(size_t repeat, const Name& name, size_t offset, size_t len)
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800202{
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700203 ssize_t tried = len;
204 shared_ptr<RegexMatcher> matcher = m_matchers[0];
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800205
206 if (0 < len && repeat >= m_repeatMax)
207 {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800208 return false;
209 }
210
211 if (0 == len && repeat < m_repeatMin)
212 {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800213 return false;
214 }
215
216 if (0 == len && repeat >= m_repeatMin)
217 {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800218 return true;
219 }
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700220
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700221 while (tried >= 0)
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800222 {
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700223 if (matcher->match(name, offset, tried) &&
224 recursiveMatch(repeat + 1, name, offset + tried, len - tried))
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800225 return true;
Alexander Afanasyevb6b21b32014-04-28 22:38:03 -0700226 tried--;
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800227 }
228
229 return false;
230}
231
232
233} // namespace ndn
234
235#endif // NDN_UTIL_REGEX_REGEX_REPEAT_MATCHER_HPP