<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Hi Pushkar,<div class=""><br class=""></div><div class="">Yes, let’s get this into a PR and we can finish reviewing it there. Thanks!</div><div class=""><br class=""></div><div class="">- Tony</div><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Mar 3, 2016, at 12:23 PM, Pushkar N Kulkarni via swift-corelibs-dev <<a href="mailto:swift-corelibs-dev@swift.org" class="">swift-corelibs-dev@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><font face="Verdana,Arial,Helvetica,sans-serif" size="2" class=""><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">Hi Philippe, other interested people:</font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">Here is the detailed description of an apparent bug in NSRegularExpression along with a possible solution. Request you to comment on the solution, in the context of correctness and performance. </font></p><div style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class=""> </font><br class="webkit-block-placeholder"></div><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">This is long - please bear with me! Alternatively, we could discuss this over a pull request if you concur.</font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">---> </font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">The following test case has been borrowed from some of those tests in TestNSRegularExpression that aren’t exercised (test_complexRegularExpression) as of today:</font></p><p style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class="">import Foundation</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier; min-height: 17px;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class="">let searchStr = "This this is the theway."</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class="">let testRegex = try NSRegularExpression(pattern: "\\b(th[a-z]+) \\1\\b", options: [])</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class="">let fm = testRegex.firstMatchInString(searchStr, options: .WithTransparentBounds, range: NSMakeRange(0,20))</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class="">let str = NSString.init(string: searchStr)</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class="">if let match = fm {</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class=""> print("Test failed")</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class=""> print(str.substringWithRange(match.range))</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class="">} else {</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class=""> print("Test passed")</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class="">}</font></p><p style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">The test fails on Linux - a false match is reported. The substring “the the” matches pattern “\b(th[a-z]+) \1\b” which is wrong because the second “the” does not occur on a word boundary. Note that we are using the option: WithTransparentBounds. This means the matcher can look beyond the search range, for word boundaries. </font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">The question is why the word boundary metacharacter at the end of the patter isn’t being honoured. I studied the functions _CFRegularExpressionEnumerateMatchesInString() and prepareRegularExpression() from CFRegularExpression.c and these are my findings that provide an explanation for a possible reason:</font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">1. We first try to get the search text - a UniChar* - using CFStringGetCharactersPtr(). I guess this is done to try improve performance. We copy the entire search text and set regionStart and regionLimit to the search range.</font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">2. Alternatively, if CFStringGetCharactersPtr() fails, we try to fill the UniChar buffer using CFStringGetCharacters(). Here we try to reduce the size of the search text so that it matches the search range. We use an “enclosingRange” for this. For “transparentBounds” we use the entire text. For nonAnchoringBounds we just take the searchRange plus one character to the left (to match ^) plus one to the right (to match $) : <span style="font-family: Courier;" class="">enclosingRange = range; </span><span style="font-family: Courier;" class=""> </span></font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class="">if (transparentBounds) {</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class=""> enclosingRange = CFRangeMake(0, length);</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class="">} else if (nonAnchoringBounds) {</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class=""> if (enclosingRange.location > 0) {</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class=""> enclosingRange.location--;</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class=""> enclosingRange.length++;</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class=""> }</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class=""> if (enclosingRange.location + enclosingRange.length < length) enclosingRange.length++;</font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class="">}</font></p><p style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">We then set regionStart and regionLimit to the search range.</font></p><p style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">3. Further we set the search text using the ICU function uregex_setText() like this: </font></p><p style="font-size: 14px; line-height: normal; font-family: Courier;" class=""><font color="#454545" class=""> uregex_setText(regex, (const UChar *)stringBuffer, (int32_t)regionLimit, &errorCode);</font></p><div style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><font color="#454545" class=""> </font><br class="webkit-block-placeholder"></div><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">Note that we use “regionLimit” for the “textLength”, which seems questionable. This truncates the search text down to a substring matching the specified search range. So, in the above case where the search text is : "<b class="">This this is the theway.</b>" , using a search range of {0,20} the search text that we actually pass to ICU is “<b class="">This this is the the</b>” which matches “\b(th[a-z]+) \1\b”. Though this may not be a problem in most searches, the <b class="">WithTransparentBounds</b> option fails to take effect. </font></p><p style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><font color="#454545" class=""><br class=""></font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">Proposed solution</font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">————————</font></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class="">The straightforward solution is to simply set the length of the search text to the actual length in <font class="">prepareRegularExpression()</font> of the search string as follows: </font></p><div style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><font color="#454545" class=""> </font><br class="webkit-block-placeholder"></div><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""><font color="#454545" class=""> </font><b class="">int32_t textLength = length; //proposed fix</b></p><p style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><br class=""></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> …</p><p style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><br class=""></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> if (range.location + range.length <= INT_MAX) stringBuffer = (UniChar *)CFStringGetCharactersPtr(string);</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> if (stringBuffer) {</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> regionStart = (int64_t)range.location;</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> regionLimit = (int64_t)(range.location + range.length);</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> *offset = 0;</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> } else {</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> enclosingRange = range;</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> if (transparentBounds) {</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> enclosingRange = CFRangeMake(0, length);</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> } else if (nonAnchoringBounds) {</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> if (enclosingRange.location > 0) {</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> enclosingRange.location--;</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> enclosingRange.length++;</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> }</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> if (enclosingRange.location + enclosingRange.length < length) enclosingRange.length++;</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> }</p><p style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><br class=""></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> …</p><p style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><br class=""></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> regionStart = (int64_t)(range.location - enclosingRange.location);</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> regionLimit = (int64_t)((range.location + range.length) - enclosingRange.location);</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> *offset = enclosingRange.location;</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> if (enclosingRange.length <= STACK_BUFFER_SIZE) {</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> stringBuffer = stackBuffer;</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> if (enclosingRange.length > 0) {</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> CFStringGetCharacters(string, enclosingRange, stringBuffer);</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> }</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> } else {</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> stringBuffer = (UniChar *)malloc(sizeof(UniChar) * enclosingRange.length);</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> if (stringBuffer) {</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> CFStringGetCharacters(string, enclosingRange, stringBuffer);</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> *bufferToFree = stringBuffer;</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> }</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> }</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> <b class="">textLength = enclosingRange.length; //proposed fix</b></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> }</p><p style="font-size: 14px; line-height: normal; font-family: Arial; min-height: 16px;" class=""><br class=""></p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> if (stringBuffer) {</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> regex = checkOutRegularExpression(internal, checkout, checkedOutRegex);</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> uregex_setText(regex, (const UChar *)stringBuffer, <b class="">textLength</b>, &errorCode); //proposed fix</p><p style="font-size: 14px; line-height: normal; font-family: Arial;" class=""> }</p><div class=""><br class=""></div><font face="Default Sans Serif,Verdana,Arial,Helvetica,sans-serif" size="2" class=""><div class="socmaildefaultfont" dir="ltr" style="font-family:Arial;font-size:10.5pt"><div class="socmaildefaultfont" dir="ltr" style="font-family:Arial;font-size:10.5pt"><div class="socmaildefaultfont" dir="ltr" style="font-family:Arial;font-size:10.5pt"><div dir="ltr" class=""><br class=""></div><div dir="ltr" class=""><br class=""></div><div dir="ltr" class=""><br class=""></div><div dir="ltr" class="">Thanks!</div><div dir="ltr" class=""><br class=""></div><div dir="ltr" class=""><br class=""><span style="font-family:georgia,serif;" class=""><span style="font-size: 1.143em;" class="">Pushkar N Kulkarni,</span></span></div>
<div dir="ltr" class=""><span style="font-family:georgia,serif;" class=""><span style="font-size: 1.143em;" class="">IBM Runtimes</span></span></div>
<div dir="ltr" class=""> </div>
<div dir="ltr" class=""><em class=""><span style="font-family:georgia,serif;" class=""><span style="font-size: 0.857em;" class="">"Any sufficiently advanced technology is indistinguishable from magic." - Arthur Clarke</span></span></em></div></div></div></div></font></font><br class="">
_______________________________________________<br class="">swift-corelibs-dev mailing list<br class=""><a href="mailto:swift-corelibs-dev@swift.org" class="">swift-corelibs-dev@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-corelibs-dev<br class=""></div></blockquote></div><br class=""></div></body></html>