bug in Stream find

[MauroMombelli]

IF the buffer contains "1211121110" and you are looking for "121110" with actual findUntil() implementation (all all function using it, like find() ) you'll get a false!

[Xuth]

I just found this bug myself. To be able to handle this the find function would need to either allocate a buffer which is problematic to do behind the scenes in a low memory environment or to require the user to pass in a buffer (which contradicts the "simple" aspect of the arduino libraries). But without this, the functions genuinely are broken. I ended up writing my own find routine that is more functional and requires the user pass in a buffer but it's more complicated to call than the arduino libraries.

[matthijskooijman]

Can you clarify why it needs a buffer? It would just need to backtrack to the start of a failed find attempt, right?

[Xuth]

Well, to backtrack it would need as long a buffer as the failed find attempt. However as I think about it more, we already effectively have that buffer since, if we've gone N characters into the target word, we know what the last N characters were and can use that to "look back into the buffer" to find a new starting point.

After looking through the Stream library (since the documentation on the Arduino site was insufficient to actually write code doing things like describing target of the find functions as a char rather than a char * and lots of other details) and seeing this as the most egregious bug and a couple more minor bugs while I was at it, I was thinking about refactoring the module and maybe some of the documentation and figuring out how to get someone to look at it for inclusion here.

[MauroMombelli]

well a solution may be to use ONE variable witch is increased until you find the first letter and the index of the number of letter matched is > 0 (in my example the first value should be the index 2). That way we keep track of where it COULD start the next recursive sequence. if the match fail, instead of continuing from the current position, as you do now, you'll have to fall back to that stored value.

do you like it?i'm planning to write down some code when i'll have time

whoops, seems like we don't have a way to call a reset on the stream, or to do a peek() of multiple position. In that case a buffer is the solution, start to save it when you would had set the possible start of recursive sequence.

[Xuth]

You can actually do better than that and you can do so with minimal variables on the stack.

[peabo7]

On February 22, 2015 at 11:49 AM Xuth notifications@github.com wrote:

Well, to backtrack it would need as long a buffer as the failed find attempt.
However as I think about it more, we already effectively have that buffer
since, if we've gone N characters into the target word, we know what the last
N characters were and can use that to "look back into the buffer" to find a
new starting point.

You might like to look at the KMP algorithm:

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

It does require some auxiliary memory similar in size to the string being
searched for, but it never has to look at an input character more than once.

Peter Olson

[Xuth]

Well, a couple of hours ago, I rewrote my find function so that a) it allows searching for arbitrary number of strings, b) doesn't need any buffer space (except you need an index integer per string searched and that is passed into the lowest level function transparently by the high level functions that specifically only search for one or two strings), and c) fixes the bug with the timeouts (that I haven't really talked about above but is one of the other bugs I ran into while looking at the Stream library). When I'm not busy I can take some time to merge my code into the library (it currently sits along side the library and isn't integrated in it) and make it visible to anyone.

[Xuth]

I've written up a fix for both the issue of find not dealing with the case described above and for the fact that timeouts were getting reset every time the Stream library had to do a read() rather than at the beginning of each of the public functions (and run against a dozen or so tests). I'm currently trying to fork this beast (taking way too long to download) and figure out the proper procedure to propose a fix. While that's going on, I've posted my code for Stream.cpp and Stream.h at http://xuth.net/xuth/ArduinoStream/ if anyone wants to look at it.

Is there a pointer to general policies and procedures and courtesies for how to suggest fixes anywhere? Not only does the Stream library have the bugs that I (think I) wrote a fix for, but the web documentation isn't adequate for trying to program to it and I'd like to propose some edits for that as well.

[matthijskooijman]

@Xuth, just for historical reference - I now see what you mean with requiring a buffer. I was thinking about String::find, but I now see this is about Stream::find instead.

The KMP algorithm is indeed interesting for its observation that you don't have to actually buffer previous characters - since they matched your search-word, you already know them. AFAICS the KMP algorithm requires a bit of extra memory because it precalculates a table that says "if matching fails at this point in the word, skip back to this other point". Of course you can leave out the table and just look back everytime the matching fails - I believe this is waht @Xuth's code does.

Looking at the code, I'm not sure I like the findMulti much. It's certainly useful, but the API isn't very Arduino-like (passing an array of structs) and the code is fairly complicated. However, I don't think I have any alternative proposals other than not supporting a multiple-search-word find. Note that I'm certainly not authoritative here, perhaps @cmaglie has an idea about this?

As for submitting a fix like this - Creating a pull request is indeed the way to go. It's a bit of a big repo indeed, though you could try to use a shallow clone, which might be a bit smaller (but doesn't have all the history).

For fixes to the documentation, just submit a (separate) github issue and it will be picked up. The more specific you can be the better - if you can add text proposals, that's even better.

[Xuth]

I agree that passing structs in isn't a normal arduino library thing. There are three reasons I left the code that way though. a) it is the absolute lowest level function in the library. All of the old routines in the library keep the exact same interface and everything uses a constant amount of stack space. b) I believe that the absolute minimum work space required for searching for an arbitrary number of strings in a stream is either one counter (int) per search target or a single buffer that is the length of the longest search target (plus a constant for temp variables on the stack). And finally c) my personal need when I initially went traipsing through the string library required being able to search for more than one target and be able to differentiate between a timeout and any other target as well.

So when wrote this I had to do either of three things a) only allow constant numbers of find targets which is what the current interface does and anyone wanting to be able to deal with even the simple and common case of distinguishing "OK" from "ERROR" from a timeout would need to write their own interface (and the ESP8266 wifi module, being completely absurd, tries to look like an AT telephony device but adds several additional strings you need to look for such as "no change" which is what sent me down this rabbit hole), b) allow the user to pass in the set of counters (which is what I do as part of the struct that is passed in) or c) have the function allocate space dynamically.

So if anyone would like to provide further guidance, I'm happy to write code to do any of the things above and submit a pull request (or I can bow out but right now I'm presuming that what I'm doing here is viewed as useful even if I'm completely new to this community).

[matthijskooijman]

@Xuth, thanks for your enlightening overview. Considering it again, I actually think this might be a good compromise between simplicity and performance :-)

[Xuth]

I've just come up with an algorithm that will support multiple search targets in a constant memory space. It is convoluted, ugly, and horribly inefficient and I'm not even going to try to write it because it would be very easy to get wrong and I don't think it's worth it. Roughly speaking, you keep an index to the target with the current longest match (not necessarily the one that would match first) and an index to how far that is matched. Everything can be calculated from there. If someone wants to write it and have it carefully checked over, go nuts. It would be a significant processor hit for the cost of a few bytes of stack space in most cases and more convoluted code and I don't think it's worth it.