7 Mar
2011
7 Mar
'11
10:21 a.m.
Hi,
This answer confirms you didn't understand the algorithm. So, let's throw some
light on it.
The principle of that algorithm is simple: linear search on name using wildcards. This
leads to the first and major assertion. This algorithm will determine if a name is
matching an expression in at max n iterations[1] (where n is of course name length).
Once you know that, the return just look obvious. When you reach return, you compare how
much in both strings you accepted. If you reach end of both string, then name is matching
expression. If not, some chars weren't accepted.
Given that, you clearly understand that if you give two null strings, then it will be
accepted as both string browsing won't have started, and both string will have
0-length. If you give only one not null, then, the main loop won't even start,
you'll just reach the return statement. That will return false as one string won't
have been browsed.
The return statement is perhaps 119 chars long, but it's just a stupid logical AND.
So, who care about its length?
If you prefer, I can even come back with my "i", "j", "k"
vars. Return statement will be shorter.
Regarding the "how many", I'd simply say... If you try to understand the
algorithm before committing your stuff on it, then chances to break it are lowered.
And even if you fail to understand the algorithm, it's worth contacting the author to
get details about how it works, isn't it?
Finally, about your second shortcut, in worse case, you're browsing expression twice,
name once.
Main algorithm, in worse case is browsing expression once, name once.
Still sure about the term "shortcut"?
And we may wonder why you upcase expression in your test, whereas you're not supposed
to do so, and you even asserted it was not needed.
And first shortcut is already in current code. Proof: it enters the loop, reads the *.
Checks it's end. Accepts name. And leaves. No iteration.
Line 100, line 160, line 163, line 165, line 166, line 204.
I'm deeply sorry, I'm not a genius. When first designing the algorithm, I
didn't took into account all the possible cases. And when new cases were reported, I
just improved the algorithm to make it handle them. So, yes, I somehow proceed by
trials-and-errors, but don't forget to look at kmtest, we now have a really complete
test case there.
Your remark only raises an error I did, I didn't commented code. Definitely true, huge
mistake. Thus, I can be asked to do so.
For pool overruns issue, that's the poorest excuse I've ever seen. In my commit
message there were several lines. Surely one reads: "This fixes potential buffer
overruns.". Yeah, great, I coded poor algorithm you won!
Actually, you should have read line right upper that reads: "As both UNICODE_STRING
& ANSI_STRING might not be NULL-termined, don't attempt to read null char.".
Here is the explanation. I did the wrong explanation that strings were always
null-terminated, so, if the algorithm was reading one char farther, it was no problem as
string were null-terminated. In fact, as they're not always null-terminated (thanks
here go to MSDN), I was reading outside of the buffer. My mistake. It's now fixed. You
can check bug #5923 to ensure that (http://www.reactos.org/bugzilla/show_bug.cgi?id=5923).
A C++ program will help you that way.
Let me correct one broken sentence here: "Also, if it looked fine for me a year
ago". It didn't. You didn't ever read it. I finally committed to trunk on
some dev advice.
Surely 7+ years of hacking this kernel give you some idea of what is correct. Still to
ensure something is correct, don't you need to understand it?
And actually, that algorithm is not really about kernel. As you can see, it's easy to
get it in user-mode, so you may be skilled as much as you want about kernel, it's no
help here.
And with a so excellent résumé, I would advice you switch to PnP. It's really broken,
badly designed, and not that working, and in the kernel. I heard at least two persons
working in two different areas complaining about PnP being broken. You would really help
them doing that, instead of fixing working code.
Which bug? Any link where to read bout that bug? Any serious proof?
And if that guy was that documented, he wouldn't have suggested to use grep source
code. Glob isn't regexp. Both are using expressions to match names, but expressions
have nothing in common. It would have been more accurate to advice using libc glob source
code.
So, to let you know, I already thought about using libc source code. But:
1 - libc source code is even uglier that code we currently have. It eats memory, is
recursive, and handles many things we don't need.
2 - On the other side, it doesn't handle enough things we need. Microsoft in that
function is using particular wildcards that aren't in "standard" glob.
That's why rewriting looked like the best solution. And I still think it is.
Now given all the information, I kindly ask you to revert both r50981 & r50982.
Feel free to review to whole algorithm, I'm sure you'll find issues. In fact, you
wouldn't fine some (serious) issues, I would say you badly reviewed it.
Because yes, that algorithm still has issues, but we're not likely to hit them before
a while. So, no worries. I'll fix them in time. I'll explain them if you wish. To
whom it may interest, your commit doesn't tends to fix those issues at all, it even
don't concern them.
Anyway, back to the demand, so, revert, review. If you find something wrong then contact
me telling something like: "Timo wouldn't have said better, your code sucks. This
looks wrong to me because bla, see this, I suggest that".
Do not forget I wrote all that code, and I think I might knew it a bit better than you
believe.
Last part of that mail, is dedicated to Ged.
I'm deeply sorry for previous mail. It wasn't nice, you're definitely true.
I won't say I was right writing that way, but I'll give at least to pieces of
information regarding that.
1 - I was really exhausted (yeah, I shouldn't have written, then. But it really pisses
me off).
2 - I announced to Aleksey less than a week ago (still...), that I was thinking about
retiring from active devs due to some internal issues. I was taking a break (vacations,
trains, small coding in an other ReactOS area, just to cool down). And here is the result:
starting of rewrite of code I wrote, without even asking whereas before everything was
cool. This not-that-fair behaviour just made me quite *angry*.
Especially with the idea of "yet you're almost done with your code, let's
review it", whereas I asked for such a review a long while ago without any success!
Remember pierre-fsd branch ~
I know I could have write better email, less rude. But all those points cumulated
didn't help leading to "let's suggest he may be wrong with his commit"
mind-state.
Think twice before pushing send... (either for a commit or an email).
Finally, if one of you felt offended, I beg your pardon.
Regards,
P.
[1]: There is one case where the algorithm is a bit worse than n iterations. I let find
you where and why. I left that case in the algorithm since it's not linkely to happen
and would reveal a coding error on caller side. And in such case, it's just doing n +
small constant iterations. It could be optimised in current, but I made choice not to
optimise, as it would make code a bit less clear, and wouldn't bring that much
improvements.
this commits
just shows you didn't understand how that function
works. If you had, you wouldn't have said:
"- Implement parameters checking in FsRtlIsNameInExpressionPrivate."
It's already done.
Enlighten me please, where? Is it crypted in the last
return
statement? If so, how many of you would decipher, it should return
TRUE if both Name and Expression are empty, and false if any of them
is not empty? And how many of you would break this in an attempt to
improve the algorithm and thus break that nice 119 chars return
statement?
"- Add two shortcuts for common wildcard invocations to make the
function faster."
If you look at the algorithm, it will take at maximum as much loop
iterations as name length.
Yeah, but not making those loop iterations is even
better for,
probably, 90% of function invocations. Also I will be honest: I'm not
sure that loop is correct but I'm not sure it's incorrect either ("a
joke about Schroedinger cat could be funny and not funny at the same
moment of time").
Constants updates to the code making it less and less readable only
add up to my concerns, with latest pool overruns too.
And in contrary, at the very least I am sure those parts I committed
are perfectly working code.
"- Second (main part of the function) is still under review."
Thanks for discussing the issue with the original author of the
algorithm, especially since you don't understand it. Furthermore,
if you're not happy with said algorithm, you were asked to review
it more than a year ago, and for at least 6 months. Thing that you
NEVER did.
I review my own code too, what's the matter? Also, if it looked
fine
for me a year ago, it doesn't mean it's perfect and it should never
be reviewed again. For your information, I review even the most
perfectly working code in the kernel, and sometimes that's rewarded
by finding nice typos leading to unpredicted results in a not very
often executed branch of a code.
So, now you discovered what my mail address is, contact me before
committing anything wrong/useless to current code.
And as you said less than a week ago, focus on fixing things that
don't work, instead of rewriting working code.
Somehow I thought that 7+ years
of hacking this kernel (starting from
revision 4578, and 522 kernel commits over time) give me some idea of
what is correct, what is useful and what does not work.
And as someone else also said once: 1:1 isn't the solution
everywhere. Or if you think so, start dropping arwinss.
Yeah, I don't disagree
with my own words, however it was the case
when it's a good addition to the code. Maxim Shatskih even outlined
there is a bug in the original Windows implementation of that
function and suggested (no, not to us, suggested to someone in some
forum thread) to use something better "like grep source code".