Don't step off the end of the index buffer

simdjson · lemire · Mar 20, 2021 · Mar 21, 2021 · Mar 21, 2021 · Mar 22, 2021
commit a3343031192147e759e1dac5d3b8815a1f10d221
diff --git a/include/simdjson/generic/ondemand/json_iterator-inl.h b/include/simdjson/generic/ondemand/json_iterator-inl.h
@@ -26,6 +26,7 @@ simdjson_really_inline json_iterator::json_iterator(const uint8_t *buf, ondemand
     _depth{1}
 {
   logger::log_headers();
+  assert_more_tokens(1);
 }
 
 // GCC 7 warns when the first line of this function is inlined away into oblivion due to the caller
@@ -36,6 +37,7 @@ SIMDJSON_DISABLE_STRICT_OVERFLOW_WARNING
 simdjson_warn_unused simdjson_really_inline error_code json_iterator::skip_child(depth_t parent_depth) noexcept {
   if (depth() <= parent_depth) { return SUCCESS; }
 
+  SIMDJSON_TRY( require_tokens(1) );
   switch (*advance()) {
     // TODO consider whether matching braces is a requirement: if non-matching braces indicates
     // *missing* braces, then future lookups are not in the object/arrays they think they are,
@@ -111,6 +113,17 @@ simdjson_really_inline void json_iterator::assert_at_root() const noexcept {
 #endif
 }
 
+simdjson_really_inline void json_iterator::assert_more_tokens(uint32_t required_tokens) const noexcept {
+  assert_valid_position(token.position() + required_tokens - 1);
+}
+
+simdjson_really_inline void json_iterator::assert_valid_position(token_position position) const noexcept {
+#ifndef SIMDJSON_CLANG_VISUAL_STUDIO
+  SIMDJSON_ASSUME( position >= &parser->implementation->structural_indexes[0] );
+  SIMDJSON_ASSUME( position < &parser->implementation->structural_indexes[parser->implementation->n_structural_indexes] );
+#endif
+}
+
 simdjson_really_inline bool json_iterator::at_end() const noexcept {
   return position() == end_position();
 }
@@ -129,22 +142,42 @@ simdjson_really_inline void json_iterator::abandon() noexcept {
 }
 
 simdjson_really_inline const uint8_t *json_iterator::advance() noexcept {
+  assert_more_tokens();
   return token.advance();
 }
 
+simdjson_really_inline simdjson_result<const uint8_t *> json_iterator::try_advance(uint32_t required_tokens) noexcept {
+  const uint8_t *json = token.advance();
+  // Check this *after* we get the pointer, since getting the pointer is more time-sensitive than the branch.
+  // Also resolves nicely to 0 in the common case of required_tokens == 1.
+  SIMDJSON_TRY( require_tokens(required_tokens - 1) );
+  return json;
+}
+
+simdjson_really_inline error_code json_iterator::require_tokens(uint32_t required_tokens) noexcept {
+  if (position() + required_tokens > end_position()) {
+    return report_error(TAPE_ERROR, "Document ended early");
+  }
+  return SUCCESS;
+}
+
 simdjson_really_inline const uint8_t *json_iterator::peek(int32_t delta) const noexcept {
+  assert_more_tokens(delta+1);
   return token.peek(delta);
 }
 
 simdjson_really_inline uint32_t json_iterator::peek_length(int32_t delta) const noexcept {
+  assert_more_tokens(delta+1);
   return token.peek_length(delta);
 }
 
 simdjson_really_inline const uint8_t *json_iterator::peek(token_position position) const noexcept {
+  assert_valid_position(position);
   return token.peek(position);
 }
 
 simdjson_really_inline uint32_t json_iterator::peek_length(token_position position) const noexcept {
+  assert_valid_position(position);
   return token.peek_length(position);
 }
 
@@ -190,6 +223,7 @@ simdjson_really_inline error_code json_iterator::report_error(error_code _error,
 simdjson_really_inline token_position json_iterator::position() const noexcept {
   return token.position();
 }
+
 simdjson_really_inline void json_iterator::reenter_child(token_position position, depth_t child_depth) noexcept {
   SIMDJSON_ASSUME(child_depth >= 1 && child_depth < INT32_MAX);
   SIMDJSON_ASSUME(_depth == child_depth - 1);
@@ -203,9 +237,11 @@ simdjson_really_inline void json_iterator::reenter_child(token_position position
 }
 
 #ifdef SIMDJSON_DEVELOPMENT_CHECKS
+
 simdjson_really_inline token_position json_iterator::start_position(depth_t depth) const noexcept {
   return parser->start_positions[depth];
 }
+
 simdjson_really_inline void json_iterator::set_start_position(depth_t depth, token_position position) noexcept {
   parser->start_positions[depth] = position;
 }

diff --git a/include/simdjson/generic/ondemand/json_iterator.h b/include/simdjson/generic/ondemand/json_iterator.h
@@ -88,10 +88,38 @@ class json_iterator {
   simdjson_really_inline void abandon() noexcept;
 
   /**
-   * Advance the current token.
+   * Advance the current token without modifying depth.
    */
   simdjson_really_inline const uint8_t *advance() noexcept;
 
+  /**
+   * Advance the current token by one, without modifying depth.
+   *
+   * @param requiremed_tokens The number of tokens that must exist. Only advances one token.
+   *
+   * @error TAPE_ERROR If there are not at least required_tokens tokens remaining.
+   */
+  simdjson_really_inline simdjson_result<const uint8_t *> try_advance(uint32_t required_tokens=1) noexcept;
+
+  /**
+   * Return an error unless there are enough tokens left.
+   *
+   * @param required_tokens The number of tokens that must exist.
+   * @error TAPE_ERROR If there are not at least required_tokens tokens remaining.
+   */
+  simdjson_really_inline error_code require_tokens(uint32_t required_tokens=1) noexcept;
+  /**
+   * Assert that there are at least the given number of tokens left.
+   *
+   * Has no effect in release builds.
+   */
+  simdjson_really_inline void assert_more_tokens(uint32_t required_tokens=1) const noexcept;
+  /**
+   * Assert that the given position addresses an actual token (is within bounds).
+   *
+   * Has no effect in release builds.
+   */
+  simdjson_really_inline void assert_valid_position(token_position position) const noexcept;
   /**
    * Get the JSON text for a given token (relative).
    *

diff --git a/include/simdjson/generic/ondemand/object-inl.h b/include/simdjson/generic/ondemand/object-inl.h
@@ -34,20 +34,16 @@ simdjson_really_inline simdjson_result<value> object::find_field(const std::stri
 }
 
 simdjson_really_inline simdjson_result<object> object::start(value_iterator &iter) noexcept {
-  // We don't need to know if the object is empty to start iteration, but we do want to know if there
-  // is an error--thus `simdjson_unused`.
-  simdjson_unused bool has_value;
-  SIMDJSON_TRY( iter.start_object().get(has_value) );
+  SIMDJSON_TRY( iter.start_object().error() );
   return object(iter);
 }
 simdjson_really_inline simdjson_result<object> object::start_root(value_iterator &iter) noexcept {
-  simdjson_unused bool has_value;
-  SIMDJSON_TRY( iter.start_root_object().get(has_value) );
+  SIMDJSON_TRY( iter.start_root_object().error() );
   return object(iter);
 }
-simdjson_really_inline object object::started(value_iterator &iter) noexcept {
-  simdjson_unused bool has_value = iter.started_object();
-  return iter;
+simdjson_really_inline simdjson_result<object> object::started(value_iterator &iter) noexcept {
+  SIMDJSON_TRY( iter.started_object().error() );
+  return object(iter);
 }
 simdjson_really_inline object object::resume(const value_iterator &iter) noexcept {
   return iter;

diff --git a/include/simdjson/generic/ondemand/object.h b/include/simdjson/generic/ondemand/object.h
@@ -78,7 +78,7 @@ class object {
 protected:
   static simdjson_really_inline simdjson_result<object> start(value_iterator &iter) noexcept;
   static simdjson_really_inline simdjson_result<object> start_root(value_iterator &iter) noexcept;
-  static simdjson_really_inline object started(value_iterator &iter) noexcept;
+  static simdjson_really_inline simdjson_result<object> started(value_iterator &iter) noexcept;
   static simdjson_really_inline object resume(const value_iterator &iter) noexcept;
   simdjson_really_inline object(const value_iterator &iter) noexcept;
 

diff --git a/include/simdjson/generic/ondemand/token_iterator-inl.h b/include/simdjson/generic/ondemand/token_iterator-inl.h
@@ -4,8 +4,8 @@ namespace ondemand {
 
 simdjson_really_inline token_iterator::token_iterator(
   const uint8_t *_buf,
-  token_position _position
-) noexcept : buf{_buf}, _position{_position}
+  token_position position
+) noexcept : buf{_buf}, _position{position}
 {
 }
 

diff --git a/include/simdjson/generic/ondemand/value_iterator-inl.h b/include/simdjson/generic/ondemand/value_iterator-inl.h
@@ -20,19 +20,22 @@ simdjson_warn_unused simdjson_really_inline simdjson_result<bool> value_iterator
 simdjson_warn_unused simdjson_really_inline simdjson_result<bool> value_iterator::start_root_object() noexcept {
   bool result;
   SIMDJSON_TRY( start_object().get(result) );
-  if (*_json_iter->peek_last() != '}') { return _json_iter->report_error(TAPE_ERROR, "object invalid: { at beginning of document unmatched by } at end of document"); }
+  if (*_json_iter->peek_last() != '}') {
+    return _json_iter->report_error(TAPE_ERROR, "object invalid: { at beginning of document unmatched by } at end of document");
+  }
   return result;
 }
 
-simdjson_warn_unused simdjson_really_inline bool value_iterator::started_object() noexcept {
+simdjson_warn_unused simdjson_really_inline simdjson_result<bool> value_iterator::started_object() noexcept {
   assert_at_container_start();
+  SIMDJSON_TRY( _json_iter->require_tokens(1) );
   if (*_json_iter->peek() == '}') {
     logger::log_value(*_json_iter, "empty object");
     _json_iter->advance();
     _json_iter->ascend_to(depth()-1);
     return false;
   }
-  logger::log_start_value(*_json_iter, "object");
+  SIMDJSON_TRY( _json_iter->require_tokens(3) ); // Make sure we have three tokens: "x" : value
 #ifdef SIMDJSON_DEVELOPMENT_CHECKS
   _json_iter->set_start_position(_depth, start_position());
 #endif
@@ -42,12 +45,14 @@ simdjson_warn_unused simdjson_really_inline bool value_iterator::started_object(
 simdjson_warn_unused simdjson_really_inline simdjson_result<bool> value_iterator::has_next_field() noexcept {
   assert_at_next();
 
+  SIMDJSON_TRY( error_unless_more_tokens() );
   switch (*_json_iter->advance()) {
     case '}':
       logger::log_end_value(*_json_iter, "object");
       _json_iter->ascend_to(depth()-1);
       return false;
     case ',':
+      SIMDJSON_TRY( error_unless_more_tokens(3) ); // Make sure we have three tokens: "x" : value
       return true;
     default:
       return _json_iter->report_error(TAPE_ERROR, "Missing comma between object fields");
@@ -252,7 +257,7 @@ simdjson_warn_unused simdjson_really_inline simdjson_result<bool> value_iterator
   // don't check errors in this bit.)
   _json_iter->reenter_child(start_position() + 1, _depth);
 
-  has_value = started_object();
+  SIMDJSON_TRY( started_object().get(has_value) );
   while (_json_iter->position() < search_start) {
     SIMDJSON_ASSUME(has_value); // we should reach search_start before ever reaching the end of the object
     SIMDJSON_ASSUME( _json_iter->_depth == _depth ); // We must be at the start of a field
@@ -290,6 +295,7 @@ simdjson_warn_unused simdjson_really_inline simdjson_result<bool> value_iterator
 simdjson_warn_unused simdjson_really_inline simdjson_result<raw_json_string> value_iterator::field_key() noexcept {
   assert_at_next();
 
+  // started_object() and has_next_field() already checked that we have a key
   const uint8_t *key = _json_iter->advance();
   if (*(key++) != '"') { return _json_iter->report_error(TAPE_ERROR, "Object key is not a string"); }
   return raw_json_string(key);
@@ -298,6 +304,7 @@ simdjson_warn_unused simdjson_really_inline simdjson_result<raw_json_string> val
 simdjson_warn_unused simdjson_really_inline error_code value_iterator::field_value() noexcept {
   assert_at_next();
 
+  // started_object() and has_next_field() already checked that we have a : and a value token
   if (*_json_iter->advance() != ':') { return _json_iter->report_error(TAPE_ERROR, "Missing colon in object field"); }
   _json_iter->descend_to(depth()+1);
   return SUCCESS;
@@ -319,13 +326,13 @@ simdjson_warn_unused simdjson_really_inline simdjson_result<bool> value_iterator
 
 simdjson_warn_unused simdjson_really_inline bool value_iterator::started_array() noexcept {
   assert_at_container_start();
+  SIMDJSON_TRY( _json_iter->require_tokens(1) );
   if (*_json_iter->peek() == ']') {
     logger::log_value(*_json_iter, "empty array");
     _json_iter->advance();
     _json_iter->ascend_to(depth()-1);
     return false;
   }
-  logger::log_start_value(*_json_iter, "array");
   _json_iter->descend_to(depth()+1);
 #ifdef SIMDJSON_DEVELOPMENT_CHECKS
   _json_iter->set_start_position(_depth, start_position());
@@ -336,12 +343,16 @@ simdjson_warn_unused simdjson_really_inline bool value_iterator::started_array()
 simdjson_warn_unused simdjson_really_inline simdjson_result<bool> value_iterator::has_next_element() noexcept {
   assert_at_next();
 
-  switch (*_json_iter->advance()) {
+  const uint8_t *json;
+  logger::log_event(*this, "has_next_element");
+  SIMDJSON_TRY( _json_iter->try_advance().get(json) )
+  switch (*json) {
     case ']':
       logger::log_end_value(*_json_iter, "array");
       _json_iter->ascend_to(depth()-1);
       return false;
     case ',':
+      SIMDJSON_TRY( _json_iter->require_tokens(1) );
       _json_iter->descend_to(depth()+1);
       return true;
     default:
@@ -501,7 +512,7 @@ simdjson_really_inline uint32_t value_iterator::peek_start_length() const noexce
   return _json_iter->peek_length(start_position());
 }
 
-simdjson_really_inline const uint8_t *value_iterator::advance_start(const char *type) const noexcept {
+simdjson_really_inline const uint8_t *value_iterator::advance_start(const char *type) noexcept {
   logger::log_value(*_json_iter, start_position(), depth(), type);
   // If we're not at the position anymore, we don't want to advance the cursor.
   if (!is_at_start()) { return peek_start(); }
@@ -512,7 +523,7 @@ simdjson_really_inline const uint8_t *value_iterator::advance_start(const char *
   _json_iter->ascend_to(depth()-1);
   return result;
 }
-simdjson_really_inline error_code value_iterator::advance_container_start(const char *type, const uint8_t *&json) const noexcept {
+simdjson_really_inline error_code value_iterator::advance_container_start(const char *type, const uint8_t *&json) noexcept {
   logger::log_start_value(*_json_iter, start_position(), depth(), type);
 
   // If we're not at the position anymore, we don't want to advance the cursor.
@@ -524,12 +535,13 @@ simdjson_really_inline error_code value_iterator::advance_container_start(const
     return SUCCESS;
   }
 
-  // Get the JSON and advance the cursor, decreasing depth to signify that we have retrieved the value.
+  // Get the JSON and advance the cursor
   assert_at_start();
   json = _json_iter->advance();
   return SUCCESS;
 }
-simdjson_really_inline const uint8_t *value_iterator::advance_root_scalar(const char *type) const noexcept {
+
+simdjson_really_inline const uint8_t *value_iterator::advance_root_scalar(const char *type) noexcept {
   logger::log_value(*_json_iter, start_position(), depth(), type);
   if (!is_at_start()) { return peek_start(); }
 
@@ -538,7 +550,7 @@ simdjson_really_inline const uint8_t *value_iterator::advance_root_scalar(const
   _json_iter->ascend_to(depth()-1);
   return result;
 }
-simdjson_really_inline const uint8_t *value_iterator::advance_non_root_scalar(const char *type) const noexcept {
+simdjson_really_inline const uint8_t *value_iterator::advance_non_root_scalar(const char *type) noexcept {
   logger::log_value(*_json_iter, start_position(), depth(), type);
   if (!is_at_start()) { return peek_start(); }
 
@@ -553,6 +565,13 @@ simdjson_really_inline error_code value_iterator::incorrect_type_error(const cha
   return INCORRECT_TYPE;
 }
 
+simdjson_really_inline error_code value_iterator::error_unless_more_tokens(uint32_t tokens) const noexcept {
+  if ((position() + tokens) > end_position()) {
+    return _json_iter->report_error(TAPE_ERROR, "Document ended early");
+  }
+  return SUCCESS;
+}
+
 simdjson_really_inline bool value_iterator::is_at_start() const noexcept {
   return position() == start_position();
 }
@@ -633,7 +652,19 @@ simdjson_really_inline token_position value_iterator::start_position() const noe
 }
 
 simdjson_really_inline token_position value_iterator::position() const noexcept {
-  return _json_iter->token.position();
+  return _json_iter->position();
+}
+
+simdjson_really_inline token_position value_iterator::end_position() const noexcept {
+  return _json_iter->end_position();
+}
+
+simdjson_really_inline token_position value_iterator::last_position() const noexcept {
+  return _json_iter->last_position();
+}
+
+simdjson_really_inline error_code value_iterator::report_error(error_code error, const char *message) noexcept {
+  return _json_iter->report_error(error, message);
 }
 
 } // namespace ondemand