Skip to main content
gamedev.net
🔒 Locked

[C++] std::const_iterator and bounds checking

Started by klems Apr 10, 2007 at 8:43 AM 5 replies 3.9k views
Original Post
klems
klems
Hi, I'm currently writing a small XML parser in C++ to try to get back into coding, and I've run into a problem with std::wstring::const_iterator. At the start of my parsing routine, I load the entire text to be parsed into a wstring and initialize a wstring::const_iterator to the const_iterator returned by wstring's begin(). I then use this iterator for searching the wstring for tokens, reading text and so on. Problem is, the const_iterator doesn't know where the wstring ends, and happily tries to access memory it shouldn't resulting in my program dying with a segfault. My first reaction to this problem was that I should write a small wrapper class for the const_iterator, that checks the iterator's position against the length of the wstring and raise an exception (I figured exceptions would be a nice solution since checking every iterator increment for an error code would be pretty tedious) if the iterator goes out of bounds. However, since I'm not all that knowledgeable about the standard library I thought I should ask if there perhaps might already be something like this in there?
ToohrVyk
ToohrVyk
Containers provide begin and end iterators. The begin iterator is the first valid one, you should not decrement an iterator which is equal to begin(). The end iterator is the first invalid one, you should not increment or dereference an iterator which is equal to end().
Blog — Facebook
klems
klems
Yeah, I'm aware of that. However, what I'm looking for is some kind of bounds-checked iterator, since checking the iterator against end() before every increment is somewhat unwieldy.
Antheus
Antheus
Quote:
Original post by Valderman
Yeah, I'm aware of that. However, what I'm looking for is some kind of bounds-checked iterator, since checking the iterator against end() before every increment is somewhat unwieldy.


This is abuse of exceptions.

Assume you have a bounds checked iterator, and you simply read until you get an exception. That is *not* an exceptional condition. The fact that you may reach the end of string is a situation that can occur each time you increment the iterator.

Checked iterators are for cases where really weird things happen, and your application shuts down without using the invalid data.

Your code needs to be aware of either length of the string, or check on each increment.

Your iterator must *never* go out of bounds unhandled. If it does, your code is broken.

Simple code to handle this:
template <class T, class CharType>class Parser{  Parser( T &t ) :     : m_curr( t.begin() )    , m_end( t.end() )  {}  bool next_char( CharType *c )  {    bool not_eof = m_curr != m_end;    if (not_eof) {      *c = *m_curr;      m_curr++;    }    return not_eof;  }  Symbol next_symbol()  {    CharType c;    if (next_char(&c)) {      switch (c) {        case '<' : return Symbol::LEFT_BRACE;        case '>' : return Symbol::RIGHT_BRACE;      }    } else {      return Symbol::EOF;    }      }  void parse()  {    Symbol s = next_symbol();    while (s != Symbol::EOF) {      // do the parse            s = next_symbol();    }  }private:  typename T::const_iterator m_curr;  typename T::const_iterator m_end;}std::wstring ws;Parser< std::wstring, wchar_t > parser( ws );parser.parse();


This is the natural way to handle it if you can't use for_each or transform or similar existing algorithms.

Note the code above might not compile, it's just a concept.
klems
klems
Quote:
Assume you have a bounds checked iterator, and you simply read until you get an exception. That is *not* an exceptional condition. The fact that you may reach the end of string is a situation that can occur each time you increment the iterator.
How exceptional does a condition need to be to warrant the use of exceptions? In my case, the end of the string is never passed unless I'm parsing a malformed XML document (someone forgot to close an element, for example), which seems pretty exceptional to me.
Antheus
Antheus
Quote:
Original post by Valderman
How exceptional does a condition need to be to warrant the use of exceptions? In my case, the end of the string is never passed unless I'm parsing a malformed XML document (someone forgot to close an element, for example), which seems pretty exceptional to me.


Exceptions are conditions which surprise you.

Fact that someone forgot to close the tag doesn't surprise you.

You're writing a tokenizer.

Tokenizer always returns a token. If you reach end of stream, that token is EOF. But it never throws an exception.

For parsers, getting an EOF token will cause lexer to put you into ERROR_STATE. Then you check, if your tree building stack is empty - if it's not, EOF was premature, and you can throw an exception and stop parsing, or your stack is empty - you have reached end of properly formatted file.

An exceptional condition would happen when reading binary streams.

Assume you have length specification. 4 bytes, specifying next element length. Malformed stream could use these 4 bytes to say "next element is 79 bytes long", yet your stream only has 43 bytes left. That is exceptional condition, since it cannot be recovered.

But XML is a sequence of tokens. Whether they form a valid XML is not low level question. Each token can still be read right up to the last byte.

Malformed XML is high-level logical error, not low level string problem.
klems
klems
Ah, now I get it. I guess reworking the code in a more sane manner is the way to go then. Thanks.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.