<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Jun 18, 2014 at 12:37 PM, Dmitry Olshansky via Digitalmars-d <span dir="ltr"><<a href="mailto:digitalmars-d@puremagic.com" target="_blank">digitalmars-d@puremagic.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">18-Jun-2014 21:38, Timothee Cour via Digitalmars-d пишет:<div class="">
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
I made a simple modification to std.regex to allow an option to prefix<br>
match a regex.<br>
Formally, if L(R) is the language recognized by a regex R, the language<br>
recognized by prefix matching of R  is:<br>
<br>
L(p(R)) = prefix(L(R)) = {u : uv in L(R) for some v}<br>
Trying to come up (by hand or algorithmically) with a regex R' such that<br>
L(R') L(p(R)) is awkward and inefficient, eg:<br>
<br>
</blockquote></div>
So essentially it's just a set of all partial matches?</blockquote><div><br></div><div>Not sure, that depends on your definition of partial matches; how do you formally define partial matches?</div><div><br></div><div>
There's a subtlety, let's call my proposal prefixMatch:<br></div><div><div><div>"hel".prefixMatch("^hello") //true</div></div></div><div><div><div>"".prefixMatch("^hello") //true</div>
</div></div><div><div>"mel".prefixMatch("^hello") //false</div></div><div><br></div><div>But if the regex doesn't start with `^` then it is not useful:</div><div><div><br></div><div>"whatever".prefixMatch("hello") //true</div>
<div>because the scanner will try each position in the input string and fail, except for the last one where it'll succeed trivially ("" is a prefix of "hello"). </div><div><br></div><div>In other words, this is more useful for one shot matching. </div>
<div><br></div><div>But we can also consider partial partial matches if we provide additional constraints given via a lambda:</div><div><br></div><div>"blabla hel blabla".partialMatch!(a=>a.hit.length>=3) ("hello")</div>
<div>=> finds a match ("hel") because the lambda succeeds on this match.</div><div><br></div><div>partialMatch could also be used to find the longest partial match (either in terms of length of matching string or length of the regex):<br>
</div><div><br></div><div>auto longestPartialMatch(R)(string input, R regex){</div><div>string longest;</div><div>while(true){</div><div>auto m=partialMatch!(a=>a.hit.length>longest.length) (input,regex);<br></div><div>
if(m) longest=a.hit; else return longest;</div><div>}</div><div><br></div><div>This could be useful for debugging complex regex to see why it didn't capture a given string for example.</div><div> <br></div></div><div>
<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div class="">
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
R='hello';<br>
R'=`|h|he|hell|hello` = `(h(e(l(l(o)?)?)?)?)?`;<br>
<br>
However thinking in terms of state machine this is much easier and<br>
efficient.<br>
<br>
It looks like this:<br>
assert("hel".match(`hello\d+`.<u></u>regex("p")); //p for prefix match<br>
<br>
</blockquote>
<br></div>
Well, since "p" would apply to operation rather then regex I think adding a partialMatch function would be simpler.<br></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<br>
Plus it may need to return extended information like where in the pattern it stopped, so the return type/API may need to be different from normal match.</blockquote><div><br></div><div> Good point, I agree.</div><div><br>
</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div class=""><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
If there's interest in adding this I can prepare a pull request and we<br>
can discuss more.<br>
<br>
</blockquote></div>
Sure partial matching wold be nice to have and any help in this direction is warmly welcome.<br></blockquote><div><br></div><div>ok, I wanted to make sure there was interest.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">

<br>
Would be cool if you could take a look at<br>
<a href="https://github.com/D-Programming-Language/phobos/pull/2216" target="_blank">https://github.com/D-<u></u>Programming-Language/phobos/<u></u>pull/2216</a><br>
<br>
It's nothing special except splitting up std.regex into a package but it's a stepping stone of going forward with it.</blockquote><div><br></div><div>That's a very welcome change, this module is too big currently. That seems like it would be the 1st phobos module to take advantage of package feature? </div>
<div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div class=""><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
Example use case:<br>
I wrote a function to search a file given a regex, and it is optimized<br>
to prune directories early on if they fail to prefix match the regex, eg:<br>
</blockquote>
<br></div>
I'm not sure I follow - a normal regex match would do essentially the same by first checking the prefix and failing on wrong ones. Where is optimization?<br>
<br></blockquote><div><br></div><div>The optimization is avoiding unnecessary file system access by pruning early on directories that we can prove will not contain any file which will match the regex. Without optimization, you have to consider (and reject) `abc/bad_subfolder/file_1`. With optimization, you never have to consider that file (nor ask the file system to list it), as `abc/bad_subfolder/` fails the prefix regex test (see my example). A normal regex needs to be applied to the whole path, and you need prefix matching to reject partial paths (ie, directories).</div>
<div><div><br></div></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
What could be interesting is to limit matching to not go beyond say 80 code units and report if it's (partial) match of given pattern.</blockquote><div><br></div><div>That'd be nice; it needs to be as generic as possible; I propose using a user defined lambda (see above).</div>
<div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div class=""><div class="h5">
<br></div></div><span class=""><font color="#888888">
-- <br>
Dmitry Olshansky<br>
</font></span></blockquote></div><br></div></div>