| # -*- Mode:python; c-file-style:"gnu"; indent-tabs-mode:nil -*- */ |
| # |
| # Copyright (c) 2013, Regents of the University of California |
| # Yingdi Yu, Alexander Afanasyev |
| # |
| # BSD license, See the doc/LICENSE file for more information |
| # |
| # Author: Yingdi Yu <yingdi@cs.ucla.edu> |
| # Alexander Afanasyev <alexander.afanasyev@ucla.edu> |
| # |
| |
| import sys |
| import re |
| import logging |
| from Name import Name |
| |
| _LOG = logging.getLogger ("ndn.nre") |
| |
| class RegexError(Exception): |
| def __init__(self, msg): |
| self.msg = msg |
| def __str__(self): |
| return self.msg |
| |
| class BaseMatcher(object): |
| def __init__(self, expr, backRef, exact=True): |
| _LOG.debug(self.__class__.__name__ + ".Constructor") |
| self.expr = expr |
| self.backRef = backRef |
| self.exact = exact |
| self.matchResult = [] |
| self.matcherList = [] |
| |
| def match(self, name, offset, len): |
| _LOG.debug(self.__class__.__name__ + ".match(): " + "expr: " + self.expr + " offset: " + str(offset) + " length: " + str(len)) |
| self.matchResult = [] |
| |
| if self._recursiveMatch(0, name, offset, len): |
| for i in range(offset, offset + len): |
| self.matchResult.append(name[i]) |
| return True |
| else: |
| return False |
| |
| def _recursiveMatch(self, mId, name, offset, length): |
| _LOG.debug(self.__class__.__name__ + "._recursiveMatch(): " + self.expr) |
| _LOG.debug("mId: " + str(mId) + " name: " + str(name) + " offset: " + str(offset) + " length: " + str(length) + " matcherListSize: " + str(len(self.matcherList))) |
| tried = 0 |
| |
| if mId >= len(self.matcherList) : |
| if length != 0 : |
| _LOG.debug("Fail " + self.__class__.__name__ + "._recursiveMatch(): no more matcher, but more components") |
| return False |
| else: |
| _LOG.debug("Succeed " + self.__class__.__name__ + "._recursiveMatch(): no more matcher, no more components") |
| return True |
| |
| matcher = self.matcherList[mId] |
| |
| while tried <= length: |
| if matcher.match(name, offset, tried) and self._recursiveMatch(mId + 1, name, offset + tried, length - tried) : |
| return True |
| _LOG.debug(self.__class__.__name__ + " expr: " + self.expr + " mId: " + str(mId) + " tried: " + str(tried) + " length: " + str(length)) |
| tried += 1 |
| |
| return False |
| |
| |
| def aggressiveMatch(self, name, offset, len): |
| _LOG.debug(self.__class__.__name__ + ".aggressiveMatch(): " + "expr: " + self.expr + " offset: " + str(offset) + " length: " + str(len)) |
| self.matchResult = [] |
| |
| if self._aRecursiveMatch(0, name, offset, len): |
| for i in range(offset, offset + len): |
| self.matchResult.append(name[i]) |
| return True |
| else: |
| return False |
| |
| def _aRecursiveMatch(self, mId, name, offset, length): |
| _LOG.debug(self.__class__.__name__ + "._aRecursiveMatch(): " + self.expr) |
| _LOG.debug("mId: " + str(mId) + " name: " + str(name) + " offset: " + str(offset) + " length: " + str(length) + " matcherListSize: " + str(len(self.matcherList))) |
| |
| tried = length |
| |
| if mId >= len(self.matcherList) : |
| if length != 0 : |
| _LOG.debug("Fail " + self.__class__.__name__ + "._recursiveMatch(): no more matcher, but more components") |
| return False |
| else: |
| _LOG.debug("Succeed " + self.__class__.__name__ + "._recursiveMatch(): no more matcher, no more components") |
| return True |
| |
| matcher = self.matcherList[mId] |
| |
| while tried >= 0: |
| if matcher.aggressiveMatch(name, offset, tried) and self._aRecursiveMatch(mId + 1, name, offset + tried, length - tried): |
| return True |
| _LOG.debug(self.__class__.__name__ + " expr: " + self.expr + " mId: " + str(mId) + " tried: " + str(tried) + " length: " + str(length)) |
| tried -= 1 |
| |
| return False |
| |
| |
| class ComponentMatcher(BaseMatcher): |
| def __init__(self, expr, backRef, exact=True): |
| _LOG.debug(self.__class__.__name__ + ".Constructor") |
| _LOG.debug("expr " + expr) |
| |
| super(ComponentMatcher, self).__init__(expr, backRef, exact) |
| |
| pattern = re.compile(self.expr) |
| self.pseudoBackRefMatcher = [] |
| for i in range(0, pattern.groups): |
| pseudoMatcher = BaseMatcher("", self.backRef) |
| self.pseudoBackRefMatcher.append(pseudoMatcher) |
| self.backRef.append(pseudoMatcher) |
| |
| def _appendBackRef(self, res): |
| if res and 0 < len(res.groups()): |
| |
| group = res.groups() |
| for i in range(0, len(group)): |
| self.pseudoBackRefMatcher[i].matchResult = [] |
| self.pseudoBackRefMatcher[i].matchResult.append(group[i]) |
| |
| def match(self, name, offset, len): |
| _LOG.debug(self.__class__.__name__ + ".match(): " + self.expr) |
| _LOG.debug("Name " + str(name) + " offset " + str(offset) + " len " +str(len)) |
| |
| self.matchResult = [] |
| |
| if "" == self.expr: |
| res = self.matchResult.append(name[offset]) |
| self._appendBackRef(res) |
| _LOG.debug("Succeed " + self.__class__.__name__ + ".match() ") |
| return True |
| |
| matcher = re.compile(self.expr) |
| if self.exact: |
| res = matcher.match(name[offset]) |
| if res: |
| self._appendBackRef(res) |
| self.matchResult.append(name[offset]) |
| _LOG.debug("Succeed " + self.__class__.__name__ + ".match() ") |
| return True |
| else: |
| res = matcher.search(name[offset]) |
| if res: |
| self._appendBackRef(res) |
| self.matchResult.append(name[offset]) |
| return True |
| |
| return False |
| |
| def aggressiveMatch(self, name, offset, len): |
| return self.match(name, offset, len) |
| |
| |
| class ComponentSetMatcher(BaseMatcher): |
| def __init__(self, expr, backRef, exact=True): |
| _LOG.debug(self.__class__.__name__ + ".Constructor") |
| |
| errMsg = "Error: ComponentSetMatcher.Constructor: " |
| self.include = True |
| |
| super(ComponentSetMatcher, self).__init__(expr, backRef, exact) |
| |
| if '<' == self.expr[0]: |
| self._compileSingleComponent() |
| elif '[' == self.expr[0]: |
| lastIndex = len(self.expr) - 1 |
| if ']' != self.expr[lastIndex]: |
| raise RegexError(errMsg + " No matched ']' " + self.expr) |
| if '^' == self.expr[1]: |
| self.include = False |
| |
| self._compileMultipleComponents(2, lastIndex) |
| else: |
| self._compileMultipleComponents(1, lastIndex) |
| |
| |
| def _compileSingleComponent(self): |
| _LOG.debug(self.__class__.__name__ + "._compileSingleComponent") |
| |
| errMsg = "Error: ComponentSetMatcher.CompileSingleComponent(): " |
| |
| end = self._extractComponent(1) |
| |
| if len(self.expr) != end: |
| raise RegexError(errMsg + "out of bound " + self.expr) |
| else: |
| self.matcherList.append(ComponentMatcher(self.expr[1:end-1], self.backRef)) |
| |
| def _compileMultipleComponents(self, start, lastIndex): |
| _LOG.debug(self.__class__.__name__ + "._compileMultipleComponents") |
| |
| errMsg = "Error: ComponentSetMatcher.CompileMultipleComponents(): " |
| |
| index = start |
| tmp_index = start |
| |
| while index < lastIndex: |
| if '<' != self.expr[index]: |
| raise RegexError(errMsg + "Component expr error " + self.expr) |
| tmp_index = index + 1 |
| index = self._extractComponent(tmp_index) |
| self.matcherList.append(ComponentMatcher(self.expr[tmp_index:index-1], self.backRef)) |
| |
| if index != lastIndex: |
| raise RegexError(errMsg + "Not sufficient expr to parse " + self.expr) |
| |
| def _extractComponent(self, index): |
| _LOG.debug(self.__class__.__name__ + "._extractComponent") |
| lcount = 1 |
| rcount = 0 |
| |
| while lcount > rcount : |
| if len(self.expr) == index: |
| break |
| elif '<' == self.expr[index]: |
| lcount += 1 |
| elif '>' == self.expr[index]: |
| rcount += 1 |
| |
| index += 1 |
| |
| return index |
| |
| def match(self, name, offset, len): |
| _LOG.debug(self.__class__.__name__ + ".match(): " + self.expr) |
| |
| self.matchResult = [] |
| |
| matched = False |
| |
| if 1 != len: |
| return False |
| |
| for matcher in self.matcherList: |
| res = matcher.match(name, offset, len) |
| if True == res: |
| matched = True |
| break |
| |
| if(matched if self.include else (not matched)): |
| self.matchResult.append(name[offset]) |
| return True |
| else: |
| return False |
| |
| def aggressiveMatch(self, name, offset, len): |
| return self.match(name, offset, len) |
| |
| class BackRefMatcher(BaseMatcher): |
| def __init__(self, expr, backRef, exact=True): |
| _LOG.debug (self.__class__.__name__ + ".Constructor") |
| super(BackRefMatcher, self).__init__(expr, backRef, exact) |
| |
| errMsg = "Error: BackRefMatcher Constructor: " |
| |
| _LOG.debug ("expr: " + self.expr); |
| _LOG.debug ("backRefManager " + str(self.backRef) + " size: " + str(len(self.backRef))) |
| |
| lastIndex = len(self.expr) - 1 |
| |
| if '(' == self.expr[0] and ')' == self.expr[lastIndex]: |
| self.backRef.append(self) |
| self.matcherList.append(PatternListMatcher(self.expr[1:lastIndex], self.backRef, self.exact)) |
| else: |
| raise RegexError(errMsg + " Unrecognoized format " + self.expr) |
| |
| |
| class PatternListMatcher(BaseMatcher): |
| def __init__(self, expr, backRef, exact=True): |
| _LOG.debug(self.__class__.__name__ + ".Constructor") |
| super(PatternListMatcher, self).__init__(expr, backRef, exact) |
| _LOG.debug("expr: " + self.expr) |
| |
| exprSize = len(self.expr) |
| index = 0 |
| subHead = index |
| |
| while index < exprSize: |
| subHead = index |
| (r_res, r_index) = self._extractPattern(subHead, index) |
| index = r_index |
| if not r_res: |
| raise RegexError("Fail to create PatternListMatcher") |
| |
| |
| def _extractPattern(self, index, next): |
| _LOG.debug(self.__class__.__name__ + "._extractPattern") |
| |
| errMsg = "Error: PatternListMatcher._extractPattern: " |
| |
| start = index |
| End = index |
| indicator = index |
| |
| _LOG.debug ("expr: " + self.expr + " index: " + str(index)) |
| |
| if '(' == self.expr[index]: |
| index += 1 |
| index = self._extractSubPattern('(', ')', index) |
| indicator = index |
| end = self._extractRepetition(index) |
| if indicator == end: |
| self.matcherList.append(BackRefMatcher(self.expr[start:end], self.backRef, self.exact)) |
| else: |
| self.matcherList.append(RepeatMatcher(self.expr[start:end], self.backRef, indicator-start, self.exact)) |
| elif '<' == self.expr[index]: |
| index += 1 |
| index = self._extractSubPattern('<', '>', index) |
| indicator = index |
| end = self._extractRepetition(index) |
| self.matcherList.append(RepeatMatcher(self.expr[start:end], self.backRef, indicator-start, self.exact)) |
| _LOG.debug("start: " + str(start) + " end: " + str(end) + " indicator: " + str(indicator)) |
| elif '[' == self.expr[index]: |
| index += 1 |
| index = self._extractSubPattern('[', ']', index) |
| indicator = index |
| end = self._extractRepetition(index) |
| self.matcherList.append(RepeatMatcher(self.expr[start:end], self.backRef, indicator-start, self.exact)) |
| _LOG.debug("start: " + str(start) + " end: " + str(end) + " indicator: " + str(indicator)) |
| else: |
| raise RegexError(errMsg +"unexpected syntax") |
| |
| |
| |
| return (True, end) |
| |
| def _extractSubPattern(self, left, right, index): |
| _LOG.debug(self.__class__.__name__ + "._extractSubPattern") |
| |
| lcount = 1 |
| rcount = 0 |
| |
| while lcount > rcount: |
| if index >= len(self.expr): |
| raise RegexError("Error: parenthesis mismatch") |
| if left == self.expr[index]: |
| lcount += 1 |
| if right == self.expr[index]: |
| rcount += 1 |
| index += 1 |
| |
| return index |
| |
| def _extractRepetition(self, index): |
| _LOG.debug(self.__class__.__name__ + "._extractRepetition") |
| |
| exprSize = len(self.expr) |
| |
| _LOG.debug("expr: " + self.expr + " index: " + str(index)) |
| |
| errMsg = "Error: PatternListMatcher._extractRepetition: " |
| |
| if index == exprSize: |
| return index |
| |
| if '+' == self.expr[index] or '?' == self.expr[index] or '*' == self.expr[index] : |
| index += 1 |
| return index |
| |
| if '{' == self.expr[index]: |
| while '}' != self.expr[index]: |
| index += 1 |
| if index == exprSize: |
| break |
| if index == exprSize: |
| raise RegexError(errMsg + "Missing right brace bracket") |
| else: |
| index += 1 |
| return index |
| else: |
| _LOG.debug ("return index: " + str(index)) |
| return index |
| |
| class RepeatMatcher(BaseMatcher): |
| def __init__(self, expr, backRef, indicator, exact=True): |
| _LOG.debug(self.__class__.__name__ + ".Constructor") |
| _LOG.debug("expr: " + expr); |
| super(RepeatMatcher, self).__init__(expr, backRef, exact) |
| self.indicator = indicator |
| if '(' == self.expr[0]: |
| self.matcherList.append(BackRefMatcher(self.expr[0:self.indicator], self.backRef)) |
| else: |
| self.matcherList.append(ComponentSetMatcher(self.expr[0:self.indicator], self.backRef)) |
| |
| self._parseRepetition() |
| _LOG.debug("repeatMin: " + str(self.repeatMin) + " repeatMax: " + str(self.repeatMax)) |
| |
| def _parseRepetition(self): |
| _LOG.debug(self.__class__.__name__ + "._parseRepetition") |
| |
| errMsg = "Error: RepeatMatcher._parseRepetition(): "; |
| |
| exprSize = len(self.expr) |
| intMax = sys.maxint |
| |
| if exprSize == self.indicator: |
| self.repeatMin = 1 |
| self.repeatMax = 1 |
| return |
| else: |
| if exprSize == (self.indicator + 1): |
| if '?' == self.expr[self.indicator]: |
| self.repeatMin = 0 |
| self.repeatMax = 1 |
| if '+' == self.expr[self.indicator]: |
| self.repeatMin = 1 |
| self.repeatMax = intMax |
| if '*' == self.expr[self.indicator]: |
| self.repeatMin = 0 |
| self.repeatMax = intMax |
| return |
| else: |
| repeatStruct = self.expr[self.indicator:exprSize] |
| min = 0 |
| max = 0 |
| |
| if re.match('{[0-9]+,[0-9]+}$', repeatStruct): |
| repeats = repeatStruct[1:-1].split(',') |
| min = int(repeats[0]) |
| max = int(repeats[1]) |
| elif re.match('{[0-9]+,}$', repeatStruct): |
| repeats = repeatStruct[1:-1].split(',') |
| min = int(repeats[0]) |
| max = intMax |
| elif re.match('{,[0-9]+}$', repeatStruct): |
| repeats = repeatStruct[1:-1].split(',') |
| min = 0 |
| max = int(repeats[1]) |
| elif re.match('{[0-9]+}$', repeatStruct): |
| min = int(repeatStruct[1:- 1]) |
| max = min; |
| else: |
| raise RegexError(errMsg + "Unrecognized format "+ self.expr); |
| |
| if min > intMax or max > intMax or min > max: |
| raise RegexError(errMsg + "Wrong number " + self.expr); |
| |
| self.repeatMin = min |
| self.repeatMax = max |
| |
| def match(self, name, offset, len): |
| _LOG.debug(self.__class__.__name__ + ".match(): " + "expr: " + self.expr + " offset: " + str(offset) + " len: " + str(len) + " repeatMin: " + str(self.repeatMin)) |
| self.matchResult = [] |
| |
| if 0 == self.repeatMin: |
| if 0 == len: |
| return True |
| |
| if self._recursiveMatch(0, name, offset, len): |
| for i in range(offset, offset+len): |
| self.matchResult.append(name[i]) |
| return True |
| else: |
| return False |
| |
| def _recursiveMatch(self, repeat, name, offset, len): |
| _LOG.debug (self.__class__.__name__ + "._recursiveMatch()" + " repeat: " + str(repeat) + " offset: " + str(offset) + " len: " + str(len) + " rMin: " + str(self.repeatMin) + " rMax: " + str(self.repeatMax)) |
| tried = 0 |
| matcher = self.matcherList[0] |
| |
| if 0 < len and repeat >= self.repeatMax: |
| _LOG.debug("Match Fail: Reach m_repeatMax && More components") |
| return False |
| |
| if 0 == len and repeat < self.repeatMin: |
| _LOG.debug("Match Fail: No more components && have NOT reached m_repeatMin " + str(len) + ", " + str(self.repeatMin)) |
| return False |
| |
| if 0 == len and repeat >= self.repeatMin: |
| _LOG.debug("Match Succeed: No more components && reach m_repeatMin") |
| return True |
| |
| while tried <= len: |
| _LOG.debug("Attempt tried: " + str(tried)) |
| |
| if matcher.match(name, offset, tried) and self._recursiveMatch(repeat + 1, name, offset + tried, len - tried): |
| return True; |
| _LOG.debug("Failed at tried: " + str(tried)); |
| tried += 1 |
| |
| return False |
| |
| |
| def aggressiveMatch(self, name, offset, len): |
| _LOG.debug(self.__class__.__name__ + ".aggressiveMatch(): " + "expr: " + self.expr + " offset: " + str(offset) + " len: " + str(len) + " repeatMin: " + str(self.repeatMin)) |
| self.matchResult = [] |
| |
| if 0 == self.repeatMin: |
| if 0 == len: |
| return True |
| |
| if self._aRecursiveMatch(0, name, offset, len): |
| for i in range(offset, offset+len): |
| self.matchResult.append(name[i]) |
| return True |
| else: |
| return False |
| |
| def _aRecursiveMatch(self, repeat, name, offset, len): |
| _LOG.debug (self.__class__.__name__ + "._aRecursiveMatch()" + " repeat: " + str(repeat) + " offset: " + str(offset) + " len: " + str(len) + " rMin: " + str(self.repeatMin) + " rMax: " + str(self.repeatMax)) |
| tried = len |
| matcher = self.matcherList[0] |
| |
| if 0 < len and repeat >= self.repeatMax: |
| _LOG.debug("Match Fail: Reach m_repeatMax && More components") |
| return False |
| |
| if 0 == len and repeat < self.repeatMin: |
| _LOG.debug("Match Fail: No more components && have NOT reached m_repeatMin " + str(len) + ", " + str(self.repeatMin)) |
| return False |
| |
| if 0 == len and repeat >= self.repeatMin: |
| _LOG.debug("Match Succeed: No more components && reach m_repeatMin") |
| return True |
| |
| while tried >= 0: |
| _LOG.debug("Attempt tried: " + str(tried)) |
| |
| if matcher.aggressiveMatch(name, offset, tried) and self._aRecursiveMatch(repeat + 1, name, offset + tried, len - tried): |
| return True; |
| _LOG.debug("Failed at tried: " + str(tried)); |
| tried -= 1 |
| |
| return False |
| |
| |
| |
| class RegexMatcher(BaseMatcher): |
| def __init__(self, expr, exact=True): |
| _LOG.debug(self.__class__.__name__ + ".Constructor") |
| super(RegexMatcher, self).__init__(expr, None, exact) |
| |
| self.backRef = [] |
| self.second_backRef = [] |
| |
| self.secondaryMatcher = None |
| |
| |
| errMsg = "Error: RegexTopMatcher Constructor: " |
| tmp_expr = self.expr |
| |
| if '$' != tmp_expr[-1]: |
| tmp_expr = tmp_expr + "<.*>*"; |
| else: |
| tmp_expr = tmp_expr[0:-1] |
| |
| if '^' != tmp_expr[0]: |
| self.secondaryMatcher = PatternListMatcher("<.*>*" + tmp_expr, self.second_backRef, self.exact) |
| else: |
| tmp_expr = tmp_expr[1:] |
| |
| _LOG.debug ("reconstructed expr " + tmp_expr); |
| |
| self.primaryMatcher = PatternListMatcher(tmp_expr, self.backRef, self.exact) |
| |
| |
| |
| def firstMatcher(): |
| return None |
| |
| def matchName(self, name): |
| _LOG.debug(self.__class__.__name__ + ".matchName") |
| |
| self.secondaryUsed = False |
| |
| res = self.primaryMatcher.match(name, 0, len(name)) |
| self.matchResult += self.primaryMatcher.matchResult |
| if False == res and None != self.secondaryMatcher: |
| res = self.secondaryMatcher.match(name, 0, len(name)) |
| self.matchResult += self.secondaryMatcher.matchResult |
| self.secondaryUsed = True |
| return res |
| |
| def extract(self, rule): |
| _LOG.debug(self.__class__.__name__ + ".extract") |
| |
| if not re.match('(\\\\[0-9]+)+$', rule): |
| raise RegexError("Wrong format of rule") |
| |
| refs = rule.split('\\') |
| refs.pop(0) |
| |
| backRef = self.backRef |
| if self.secondaryUsed: |
| backRef = self.second_backRef |
| |
| result = [] |
| for index in refs: |
| i = int(index) - 1 |
| |
| if len(backRef) <= i or 0 > i: |
| raise RegexError("Wrong back reference number!") |
| |
| result += backRef[i].matchResult |
| |
| return result |
| |
| def matchN(self, name): |
| _LOG.debug(self.__class__.__name__ + ".matchN") |
| |
| self.secondaryUsed = False |
| |
| res = self.primaryMatcher.aggressiveMatch(name, 0, len(name)) |
| self.matchResult += self.primaryMatcher.matchResult |
| if False == res and None != self.secondaryMatcher: |
| res = self.secondaryMatcher.aggressiveMatch(name, 0, len(name)) |
| self.matchResult += self.secondaryMatcher.matchResult |
| self.secondaryUsed = True |
| return res |
| |
| def expand (self, rule): |
| return self.extract (rule) |
| |
| def match (pattern, name, flags=0): |
| """ |
| If zero or more characters at the beginning of string match the regular expression pattern, return a corresponding matches as a list. Return None if the string does not match the pattern. |
| """ |
| if not isinstance (name, Name): |
| raise TypeError ("name is not ndn.Name type") |
| |
| m = RegexMatcher (pattern) |
| res = m.matchN (Name (name)) |
| if not res: |
| return None |
| return m |