experimental

include/simdjson/generic/ondemand/key_selector.h

@@ -13,6 +13,7 @@
 #include <cstddef>
 #include <cstdint>
 #include <cstring>
+#include <utility>
 
 #if defined(__aarch64__) || defined(__ARM_NEON)
   #include <arm_neon.h>
@@ -37,10 +38,7 @@ namespace key_selector_detail {
 
 // ============================================================================
 // Compile-time perfect-hash generator.
-//
-// This is a port of the ConstexprCore perfect-hash generator
-// (https://github.com/ConstexprCore/perfect_hash). It scales to ~100 keys at
-// compile time by determining association values one (position, character)
+// It scales to ~100 keys at compile time by determining association values one (position, character)
 // symbol at a time (gperf-style) instead of an exhaustive offset search, and
 // falls back to a Hash-and-Displace construction for large/awkward key sets.
 //
@@ -915,6 +913,57 @@ struct key_selector {
         return ki;
     }
 
+    /**
+     * Compare the JSON key at `p` (just past the opening quote, in a padded
+     * buffer) against the compile-time key at selector index I. Because keys[I]
+     * has a compile-time-constant length and bytes, the length check and memcmp
+     * fully inline to a handful of fixed-width loads/compares -- the same cheap
+     * comparison the ordered obj[key] path performs. The trailing-quote check
+     * disambiguates keys that are prefixes of one another and of longer JSON keys.
+     */
+    template <std::size_t I>
+    static simdjson_really_inline bool matches_at(const char* p) noexcept {
+        constexpr std::string_view k = keys[I];
+        return p[k.size()] == '"' && std::memcmp(p, k.data(), k.size()) == 0;
+    }
+
+    /**
+     * Order-independent linear match: try each key in turn with a fully inlined,
+     * compile-time-sized comparison, stopping at the first hit. For a small number
+     * of keys this is cheaper than the perfect hash (no length scan, no table
+     * loads), which matters because deserialization is dominated by many small
+     * structs. Returns the selector index in [0, N) on match, or N on miss.
+     */
+    static simdjson_really_inline std::size_t match_linear(raw_json_string rjs) noexcept {
+        const char* p = rjs.raw();
+        std::size_t idx = N;
+        [&]<std::size_t... Is>(std::index_sequence<Is...>) {
+            (void)((matches_at<Is>(p) ? (idx = Is, true) : false) || ...);
+        }(std::make_index_sequence<N>{});
+        return idx;
+    }
+
+    // Selectors no larger than this use the unrolled linear matcher; larger ones
+    // use the perfect hash. The crossover comes from a microbenchmark of both
+    // matchers: for in-order hits (the deserialization case) linear wins up to
+    // ~N=10, and for a pure miss the crossover is ~N=8, so 8 captures the small-
+    // struct win without regressing larger or miss-heavy selectors. match_raw and
+    // match_linear remain available if a caller wants to force one.
+    static constexpr std::size_t linear_match_max = 8;
+
+    /**
+     * Look up a JSON key, choosing the cheaper matcher for this selector's size:
+     * the unrolled linear comparison for small selectors, the perfect hash for
+     * large ones. Returns the selector index in [0, N) on match, or N on miss.
+     */
+    static simdjson_really_inline std::size_t match(raw_json_string rjs) noexcept {
+        if constexpr (N <= linear_match_max) {
+            return match_linear(rjs);
+        } else {
+            return match_raw(rjs);
+        }
+    }
+
     /** Return the key text at selector index i (i in [0, N)). */
     static constexpr std::string_view key_at(std::size_t i) noexcept {
         return keys[i];

include/simdjson/generic/ondemand/object-inl.h

@@ -65,18 +65,18 @@ simdjson_inline simdjson_result<value> object::find_field(const std::string_view
 
 #if SIMDJSON_SUPPORTS_CONCEPTS
 template <typename Selector, typename Func>
-simdjson_inline error_code object::for_each(Func&& on_match) noexcept {
+simdjson_flatten simdjson_inline for_each_result object::for_each(Func&& on_match) noexcept {
   auto first = this->begin();
-  if (first.error()) { return first.error(); }
+  if (first.error()) { return {first.error(), 0}; }
   object_iterator it = first.value_unsafe();
   object_iterator last{};
   std::array<bool, Selector::size()> seen{};
   std::size_t matched = 0;
   while (it != last) {
     auto field_res = *it;
-    if (field_res.error()) { return field_res.error(); }
+    if (field_res.error()) { return {field_res.error(), matched}; }
     field f = field_res.value_unsafe();
-    std::size_t idx = Selector::match_raw(f.key());
+    std::size_t idx = Selector::match(f.key());
     if (idx < Selector::size() && !seen[idx]) {
       seen[idx] = true;
       value matched_value = f.value();
@@ -87,7 +87,7 @@ simdjson_inline error_code object::for_each(Func&& on_match) noexcept {
       // handling its own errors.
       if constexpr (std::is_same_v<decltype(on_match(idx, matched_value)), error_code>) {
         error_code e = on_match(idx, matched_value);
-        if (e) { return e; }
+        if (e) { return {e, matched}; }
       } else {
         on_match(idx, matched_value);
       }
@@ -95,7 +95,7 @@ simdjson_inline error_code object::for_each(Func&& on_match) noexcept {
     }
     ++it;
   }
-  return SUCCESS;
+  return {SUCCESS, matched};
 }
 #endif
 

include/simdjson/generic/ondemand/object.h

@@ -16,6 +16,22 @@ namespace simdjson {
 namespace SIMDJSON_IMPLEMENTATION {
 namespace ondemand {
 
+#if SIMDJSON_SUPPORTS_CONCEPTS
+/**
+ * Result of object::for_each: the first error encountered (SUCCESS if none) and
+ * the number of distinct selector keys that matched during the walk. A
+ * matched_count equal to Selector::size() means every selected key was present
+ * in the object. Implicitly converts to error_code so existing callers that only
+ * care about the error (including SIMDJSON_TRY and the test ASSERT_* macros) keep
+ * working unchanged.
+ */
+struct for_each_result {
+  error_code error{SUCCESS};
+  std::size_t matched_count{0};
+  constexpr operator error_code() const noexcept { return error; }
+};
+#endif
+
 /**
  * A forward-only JSON object field iterator.
  */
@@ -148,11 +164,14 @@ public:
    * error_code, the walk stops at the first non-SUCCESS result and that error is
    * returned, which lets the callback surface value-parse errors.
    *
-   * @returns SUCCESS, or the first error encountered while walking the object
-   *          (including any error returned by the callback).
+   * @returns a for_each_result holding the first error encountered while walking
+   *          the object (including any error returned by the callback, SUCCESS if
+   *          none) and the number of distinct selector keys that matched. The
+   *          result converts implicitly to error_code, so callers that only need
+   *          the error can ignore the count.
    */
   template <typename Selector, typename Func>
-  simdjson_inline error_code for_each(Func&& on_match) noexcept;
+  simdjson_inline for_each_result for_each(Func&& on_match) noexcept;
 #endif
 
   /**

include/simdjson/generic/ondemand/std_deserialize.h

@@ -309,6 +309,22 @@ template <typename T>
 using selector_for = typename [: std::meta::substitute(
     ^^SIMDJSON_IMPLEMENTATION::ondemand::key_selector, selector_key_args<T>()) :];
 
+// True when none of T's eligible members is an optional type, i.e. every member
+// is required. In that case presence can be checked with a single match count
+// instead of a per-member "seen" array.
+template <typename T>
+consteval bool all_eligible_members_required() {
+  bool all_required = true;
+  template for (constexpr auto mem : std::define_static_array(std::meta::nonstatic_data_members_of(^^T, std::meta::access_context::unchecked()))) {
+    if constexpr (is_eligible_member(mem)) {
+      if constexpr (concepts::optional_type<typename [: std::meta::type_of(mem) :]>) {
+        all_required = false;
+      }
+    }
+  }
+  return all_required;
+}
+
 } // namespace key_selector_reflection_detail
 
 template <typename T, typename ValT>
@@ -321,40 +337,63 @@ error_code tag_invoke(deserialize_tag, ValT &val, T &out) noexcept {
     SIMDJSON_TRY(val.get_object().get(obj));
   }
   using selector = key_selector_reflection_detail::selector_for<T>;
-  std::array<bool, selector::size()> seen_member{};
-  // Single pass over the object: each field whose key matches a member yields its
-  // selector index, which we map back to the corresponding member. The callback
-  // returns an error_code so that a value-parse error (e.g. a type mismatch on a
-  // matched field) is propagated by for_each instead of being silently dropped.
-  error_code walk_error = obj.template for_each<selector>(
-      [&](std::size_t matched_index, SIMDJSON_IMPLEMENTATION::ondemand::value field_value) -> error_code {
-    std::size_t counter = 0;
-    error_code field_error = SUCCESS;
+  if constexpr (key_selector_reflection_detail::all_eligible_members_required<T>()) {
+    // Fast path: every member is required. A single for_each pass parses each
+    // matched field; the returned match count then tells us whether every member
+    // was present (matched_count == selector::size()) without a per-member "seen"
+    // array. A value-parse error (e.g. a type mismatch) is propagated by for_each.
+    auto walk = obj.template for_each<selector>(
+        [&](std::size_t matched_index, SIMDJSON_IMPLEMENTATION::ondemand::value field_value) -> error_code {
+      std::size_t counter = 0;
+      template for (constexpr auto mem : std::define_static_array(std::meta::nonstatic_data_members_of(^^T, std::meta::access_context::unchecked()))) {
+        if constexpr (key_selector_reflection_detail::is_eligible_member(mem)) {
+          if (matched_index == counter) { return field_value.get(out.[:mem:]); }
+          ++counter;
+        }
+      }
+      return SUCCESS;
+    });
+    if (walk.error) { return walk.error; }
+    // A missing required member shows up as a short match count and is reported as
+    // NO_SUCH_FIELD, mirroring the ordered obj[key] path.
+    if (walk.matched_count != selector::size()) { return NO_SUCH_FIELD; }
+    return SUCCESS;
+  } else {
+    std::array<bool, selector::size()> seen_member{};
+    // Single pass over the object: each field whose key matches a member yields its
+    // selector index, which we map back to the corresponding member. The callback
+    // returns an error_code so that a value-parse error (e.g. a type mismatch on a
+    // matched field) is propagated by for_each instead of being silently dropped.
+    error_code walk_error = obj.template for_each<selector>(
+        [&](std::size_t matched_index, SIMDJSON_IMPLEMENTATION::ondemand::value field_value) -> error_code {
+      std::size_t counter = 0;
+      error_code field_error = SUCCESS;
+      template for (constexpr auto mem : std::define_static_array(std::meta::nonstatic_data_members_of(^^T, std::meta::access_context::unchecked()))) {
+        if constexpr (key_selector_reflection_detail::is_eligible_member(mem)) {
+          if (matched_index == counter) {
+            seen_member[counter] = true;
+            field_error = field_value.get(out.[:mem:]);
+          }
+          ++counter;
+        }
+      }
+      return field_error;
+    });
+    if (walk_error) { return walk_error; }
+    // Required (non-optional) members must be present: a missing one is reported as
+    // NO_SUCH_FIELD, mirroring the ordered obj[key] path. Optional members may be
+    // absent.
+    std::size_t check_counter = 0;
     template for (constexpr auto mem : std::define_static_array(std::meta::nonstatic_data_members_of(^^T, std::meta::access_context::unchecked()))) {
       if constexpr (key_selector_reflection_detail::is_eligible_member(mem)) {
-        if (matched_index == counter) {
-          seen_member[counter] = true;
-          field_error = field_value.get(out.[:mem:]);
+        if constexpr (!concepts::optional_type<decltype(out.[:mem:])>) {
+          if (!seen_member[check_counter]) { return NO_SUCH_FIELD; }
         }
-        ++counter;
+        ++check_counter;
       }
     }
-    return field_error;
-  });
-  if (walk_error) { return walk_error; }
-  // Required (non-optional) members must be present: a missing one is reported as
-  // NO_SUCH_FIELD, mirroring the ordered obj[key] path. Optional members may be
-  // absent.
-  std::size_t check_counter = 0;
-  template for (constexpr auto mem : std::define_static_array(std::meta::nonstatic_data_members_of(^^T, std::meta::access_context::unchecked()))) {
-    if constexpr (key_selector_reflection_detail::is_eligible_member(mem)) {
-      if constexpr (!concepts::optional_type<decltype(out.[:mem:])>) {
-        if (!seen_member[check_counter]) { return NO_SUCH_FIELD; }
-      }
-      ++check_counter;
-    }
+    return SUCCESS;
   }
-  return SUCCESS;
 }
 
 #else

tests/ondemand/ondemand_object_find_field_tests.cpp

@@ -344,6 +344,48 @@ namespace object_tests {
   }
 #endif
 
+#if SIMDJSON_SUPPORTS_CONCEPTS
+  // The key_selector exposes two matchers -- the perfect hash (match_raw) and the
+  // unrolled linear scan (match_linear) -- and match() dispatches between them by
+  // size. They must return identical selector indices for every key, including
+  // tricky cases: keys that are prefixes of one another, keys that extend a real
+  // key, a long key, and misses. This guards the linear matcher's prefix/length
+  // disambiguation (the trailing-quote check) against the hash.
+  bool key_selector_matchers_agree() {
+    TEST_START();
+    // Probe builds "<key>\"" in a padded buffer and checks the three matchers agree.
+    auto probe = [](auto sel_tag, std::string_view key) -> bool {
+      using sel = decltype(sel_tag);
+      char buf[64] = {};
+      for (size_t i = 0; i < key.size(); ++i) { buf[i] = key[i]; }
+      buf[key.size()] = '"';
+      ondemand::raw_json_string r(reinterpret_cast<const uint8_t*>(buf));
+      std::size_t raw = sel::match_raw(r);
+      ASSERT_EQUAL(sel::match_linear(r), raw);
+      ASSERT_EQUAL(sel::match(r), raw);
+      return true;
+    };
+    // Small selector (<= linear_match_max, so match() uses the linear scan),
+    // with prefix keys and a 30-character key.
+    using small_sel = ondemand::key_selector<"a", "ab", "abc", "id", "name",
+                                              "abcdefghijklmnopqrstuvwxyz1234">;
+    for (auto k : {"a", "ab", "abc", "id", "name", "abcdefghijklmnopqrstuvwxyz1234"}) {
+      if (!probe(small_sel{}, k)) { return false; }
+    }
+    for (auto k : {"x", "abcd", "nam", "names", "i", "ids", "zzzzz", ""}) {
+      if (!probe(small_sel{}, k)) { return false; }
+    }
+    // Large selector (> linear_match_max, so match() uses the perfect hash);
+    // match_linear must still agree with the hash.
+    using big_sel = ondemand::key_selector<"k00","k01","k02","k03","k04","k05",
+                                            "k06","k07","k08","k09","k10","k11">;
+    for (auto k : {"k00","k05","k11","k12","nope",""}) {
+      if (!probe(big_sel{}, k)) { return false; }
+    }
+    TEST_SUCCEED();
+  }
+#endif
+
   bool run() {
     return
            object_find_field_unordered() &&
@@ -355,6 +397,7 @@ namespace object_tests {
 #if SIMDJSON_SUPPORTS_CONCEPTS
            object_find_field_key_selector() &&
            object_for_each_callback_error() &&
+           key_selector_matchers_agree() &&
 #endif
 #if SIMDJSON_EXCEPTIONS && SIMDJSON_SUPPORTS_CONCEPTS
            key_selector_example_toplevel() &&