blob: ce0abb1b8d8766ac0c18b1579b71df457b76b2ec [file] [log] [blame]
Yingdi Yu5e974202014-01-29 16:59:06 -08001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
2/**
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -07003 * Copyright (c) 2013-2014, Regents of the University of California.
4 * All rights reserved.
5 *
6 * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
7 * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
8 *
9 * This file licensed under New BSD License. See COPYING for detailed information about
10 * ndn-cxx library copyright, permissions, and redistribution restrictions.
11 *
12 * @author Yingdi Yu <http://irl.cs.ucla.edu/~yingdi/>
Yingdi Yu5e974202014-01-29 16:59:06 -080013 */
14
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080015#ifndef NDN_UTIL_REGEX_REGEX_REPEAT_MATCHER_HPP
16#define NDN_UTIL_REGEX_REGEX_REPEAT_MATCHER_HPP
17
18#include "../../common.hpp"
19
20#include <boost/regex.hpp>
Yingdi Yu5e974202014-01-29 16:59:06 -080021
22#include "regex-matcher.hpp"
23
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080024namespace ndn {
Yingdi Yu5e974202014-01-29 16:59:06 -080025
26class RegexRepeatMatcher : public RegexMatcher
27{
28public:
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -070029 RegexRepeatMatcher(const std::string& expr,
30 shared_ptr<RegexBackrefManager> backRefManager,
31 int indicator);
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070032
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -070033 virtual
34 ~RegexRepeatMatcher(){}
Yingdi Yu5e974202014-01-29 16:59:06 -080035
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070036 virtual bool
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080037 match(const Name& name, const int& offset, const int& len);
Yingdi Yu5e974202014-01-29 16:59:06 -080038
39protected:
40 /**
41 * @brief Compile the regular expression to generate the more matchers when necessary
42 * @returns true if compiling succeeds
43 */
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070044 virtual void
Yingdi Yu5e974202014-01-29 16:59:06 -080045 compile();
46
Yingdi Yu5e974202014-01-29 16:59:06 -080047private:
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070048 bool
Yingdi Yu5e974202014-01-29 16:59:06 -080049 parseRepetition();
50
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070051 bool
Yingdi Yu5e974202014-01-29 16:59:06 -080052 recursiveMatch (int repeat,
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070053 const Name& name,
54 const int& offset,
55 const int&len);
56
Yingdi Yu5e974202014-01-29 16:59:06 -080057private:
58 int m_indicator;
59 int m_repeatMin;
60 int m_repeatMax;
61};
62
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080063} // namespace ndn
Yingdi Yu5e974202014-01-29 16:59:06 -080064
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080065#include "regex-backref-matcher.hpp"
66#include "regex-component-set-matcher.hpp"
67
68namespace ndn {
69
70inline
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -070071RegexRepeatMatcher::RegexRepeatMatcher(const std::string& expr,
72 shared_ptr<RegexBackrefManager> backrefManager,
73 int indicator)
74 : RegexMatcher (expr, EXPR_REPEAT_PATTERN, backrefManager)
75 , m_indicator(indicator)
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080076{
77 // _LOG_TRACE ("Enter RegexRepeatMatcher Constructor");
78 compile();
79 // _LOG_TRACE ("Exit RegexRepeatMatcher Constructor");
80}
81
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070082inline void
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080083RegexRepeatMatcher::compile()
84{
85 // _LOG_TRACE ("Enter RegexRepeatMatcher::compile");
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070086
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080087 shared_ptr<RegexMatcher> matcher;
88
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070089 if ('(' == m_expr[0]){
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080090 matcher = make_shared<RegexBackrefMatcher>(m_expr.substr(0, m_indicator), m_backrefManager);
91 m_backrefManager->pushRef(matcher);
Alexander Afanasyevb67090a2014-04-29 22:31:01 -070092 dynamic_pointer_cast<RegexBackrefMatcher>(matcher)->lateCompile();
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080093 }
94 else{
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -070095 matcher = make_shared<RegexComponentSetMatcher>(m_expr.substr(0, m_indicator),
96 m_backrefManager);
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -080097 }
98 m_matcherList.push_back(matcher);
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -070099
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800100 parseRepetition();
101
102 // _LOG_TRACE ("Exit RegexRepeatMatcher::compile");
103
104}
105
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700106inline bool
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800107RegexRepeatMatcher::parseRepetition()
108{
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800109 int exprSize = m_expr.size();
110 int intMax = std::numeric_limits<int>::max();
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700111
112 if (exprSize == m_indicator){
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800113 m_repeatMin = 1;
114 m_repeatMax = 1;
115
116 return true;
117 }
118 else{
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700119 if (exprSize == (m_indicator + 1)){
120 if ('?' == m_expr[m_indicator]){
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800121 m_repeatMin = 0;
122 m_repeatMax = 1;
123 return true;
124 }
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700125 if ('+' == m_expr[m_indicator]){
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800126 m_repeatMin = 1;
127 m_repeatMax = intMax;
128 return true;
129 }
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700130 if ('*' == m_expr[m_indicator]){
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800131 m_repeatMin = 0;
132 m_repeatMax = intMax;
133 return true;
134 }
135 }
136 else{
137 std::string repeatStruct = m_expr.substr(m_indicator, exprSize - m_indicator);
138 int rsSize = repeatStruct.size();
139 int min = 0;
140 int max = 0;
141
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700142 if (boost::regex_match(repeatStruct, boost::regex("\\{[0-9]+,[0-9]+\\}"))){
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800143 int separator = repeatStruct.find_first_of(',', 0);
144 min = atoi(repeatStruct.substr(1, separator - 1).c_str());
145 max = atoi(repeatStruct.substr(separator + 1, rsSize - separator - 2).c_str());
146 }
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700147 else if (boost::regex_match(repeatStruct, boost::regex("\\{,[0-9]+\\}"))){
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800148 int separator = repeatStruct.find_first_of(',', 0);
149 min = 0;
150 max = atoi(repeatStruct.substr(separator + 1, rsSize - separator - 2).c_str());
151 }
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700152 else if (boost::regex_match(repeatStruct, boost::regex("\\{[0-9]+,\\}"))){
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800153 int separator = repeatStruct.find_first_of(',', 0);
154 min = atoi(repeatStruct.substr(1, separator).c_str());
155 max = intMax;
156 }
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700157 else if (boost::regex_match(repeatStruct, boost::regex("\\{[0-9]+\\}"))){
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800158 min = atoi(repeatStruct.substr(1, rsSize - 1).c_str());
159 max = min;
160 }
161 else
162 throw RegexMatcher::Error(std::string("Error: RegexRepeatMatcher.ParseRepetition(): ")
163 + "Unrecognized format "+ m_expr);
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700164
165 if (min > intMax || max > intMax || min > max)
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800166 throw RegexMatcher::Error(std::string("Error: RegexRepeatMatcher.ParseRepetition(): ")
167 + "Wrong number " + m_expr);
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700168
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800169 m_repeatMin = min;
170 m_repeatMax = max;
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700171
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800172 return true;
173 }
174 }
175 return false;
176}
177
178inline bool
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700179RegexRepeatMatcher::match(const Name& name, const int& offset, const int& len)
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800180{
181 // _LOG_TRACE ("Enter RegexRepeatMatcher::match");
182
183 m_matchResult.clear();
184
185 if (0 == m_repeatMin)
186 if (0 == len)
187 return true;
188
189 if (recursiveMatch(0, name, offset, len))
190 {
191 for (int i = offset; i < offset + len; i++)
192 m_matchResult.push_back(name.get(i));
193 return true;
194 }
195 else
196 return false;
197}
198
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700199inline bool
200RegexRepeatMatcher::recursiveMatch(int repeat, const Name& name, const int& offset, const int& len)
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800201{
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800202 int tried = len;
203 shared_ptr<RegexMatcher> matcher = m_matcherList[0];
204
205 if (0 < len && repeat >= m_repeatMax)
206 {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800207 return false;
208 }
209
210 if (0 == len && repeat < m_repeatMin)
211 {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800212 return false;
213 }
214
215 if (0 == len && repeat >= m_repeatMin)
216 {
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800217 return true;
218 }
Alexander Afanasyevfdbfc6d2014-04-14 15:12:11 -0700219
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800220 while(tried >= 0)
221 {
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -0700222 if (matcher->match(name, offset, tried) and recursiveMatch(repeat + 1, name,
223 offset + tried, len - tried))
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800224 return true;
Alexander Afanasyev36b84cf2014-02-17 19:34:18 -0800225 tried --;
226 }
227
228 return false;
229}
230
231
232} // namespace ndn
233
234#endif // NDN_UTIL_REGEX_REGEX_REPEAT_MATCHER_HPP