Fix AppVeyor failures from the Zmij double writer

MSVC 2015 warns C4554 on the shifts with casts in the fractional part
of zmij::to_shortest despite the parentheses; with /WX every target
fails to build. Name the shift amounts as constants instead.

The shortest-digits test built the candidates with one digit fewer via
a stream with std::setprecision(digits.size() - 2); the standard library
of MSVC 2017 ignores a precision of 0, so for two-digit values the
"shorter" candidates were the value itself. Truncate the digits
instead: the value lies within half a unit of the last digit, so the
truncated digits and their successor are the closest candidates.

Signed-off-by: Niels Lohmann <mail@nlohmann.me>

include/nlohmann/detail/conversions/zmij.hpp

@@ -184,7 +184,10 @@ JSON_HEDLEY_ALWAYS_INLINE shortest_decimal to_shortest(std::uint64_t bits) noexc
     const uint128_parts p10 = pow10(-dec_exp - 1);
     const uint128_parts p = umul192_hi128(p10.high, p10.low, bin_sig << static_cast<unsigned>(shift));
     std::uint64_t integral = p.high >> static_cast<unsigned>(extra_shift);
-    const std::uint64_t fractional = (p.high << static_cast<unsigned>(64 - extra_shift)) | (p.low >> static_cast<unsigned>(extra_shift));
+    // (no casts in the shifts: MSVC 2015 warns C4554 on them despite the parentheses)
+    constexpr unsigned fractional_low_shift = static_cast<unsigned>(extra_shift);
+    constexpr unsigned fractional_high_shift = 64u - fractional_low_shift;
+    const std::uint64_t fractional = (p.high << fractional_high_shift) | (p.low >> fractional_low_shift);
     std::uint64_t digit = 0;
     bool round_up = false;
     bool round_down = false;

include/nlohmann/detail/input/json_sax.hpp

@@ -674,19 +674,16 @@ class json_sax_dom_callback_parser
         if (keep && ref_stack.back())
         {
             auto& obj = *ref_stack.back()->m_data.m_value.object;
-            // a single lookup: insert the placeholder, or find the existing member
+            const auto it = obj.find(val);
-            const auto inserted = obj.emplace(val, discarded);
+            if (it != obj.end())
-            const auto it = inserted.first;
-            if (!inserted.second)
             {
                 // this is a duplicate key (legal in JSON); remember its
                 // current value so it can be restored later if the new
                 // value is rejected by the callback, instead of being
                 // erased together with the discarded placeholder
                 duplicate_key_stash.emplace_back(&(it->second), it->second);
-                it->second = discarded;
             }
-            object_element = &(it->second);
+            object_element = &(obj[val] = discarded);
         }
 
         return true;

include/nlohmann/detail/json_pointer.hpp

@@ -16,6 +16,8 @@
     #include <iosfwd> // ostream
 #endif  // JSON_NO_IO
 #include <limits> // max
+#include <map> // map
+#include <numeric> // accumulate
 #include <string> // string
 #include <utility> // move
 #include <vector> // vector
@@ -67,21 +69,12 @@ class json_pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/to_string/
     string_t to_string() const
     {
-        // one buffer: every token adds its escaped form (at least its length) and a slash
+        return std::accumulate(reference_tokens.begin(), reference_tokens.end(),
-        std::size_t length = 0;
+                               string_t{},
-        for (const auto& reference_token : reference_tokens)
+                               [](const string_t& a, const string_t& b)
         {
-            length += reference_token.size() + 1;
+            return detail::concat<string_t>(a, '/', detail::escape(b));
-        }
+        });
-
-        string_t result;
-        result.reserve(length);
-        for (const auto& reference_token : reference_tokens)
-        {
-            result.append("/", 1);
-            detail::escape_into(result, reference_token);
-        }
-        return result;
     }
 
     /// @brief return a string representation of the JSON pointer
@@ -136,29 +129,21 @@ class json_pointer
     friend json_pointer operator/(const json_pointer& lhs,
                                   const json_pointer& rhs)
     {
-        json_pointer result;
+        return json_pointer(lhs) /= rhs;
-        result.reference_tokens.reserve(lhs.reference_tokens.size() + rhs.reference_tokens.size());
-        result.reference_tokens.insert(result.reference_tokens.end(), lhs.reference_tokens.begin(), lhs.reference_tokens.end());
-        result.reference_tokens.insert(result.reference_tokens.end(), rhs.reference_tokens.begin(), rhs.reference_tokens.end());
-        return result;
     }
 
     /// @brief create a new JSON pointer by appending the unescaped token at the end of the JSON pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/operator_slash/
     friend json_pointer operator/(const json_pointer& lhs, string_t token) // NOLINT(performance-unnecessary-value-param)
     {
-        json_pointer result;
+        return json_pointer(lhs) /= std::move(token);
-        result.reference_tokens.reserve(lhs.reference_tokens.size() + 1);
-        result.reference_tokens.insert(result.reference_tokens.end(), lhs.reference_tokens.begin(), lhs.reference_tokens.end());
-        result.reference_tokens.push_back(std::move(token));
-        return result;
     }
 
     /// @brief create a new JSON pointer by appending the array-index-token at the end of the JSON pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/operator_slash/
     friend json_pointer operator/(const json_pointer& lhs, std::size_t array_idx)
     {
-        return lhs / detail::to_string<string_t>(array_idx);
+        return json_pointer(lhs) /= array_idx;
     }
 
     /// @brief returns the parent of this JSON pointer
@@ -170,8 +155,8 @@ class json_pointer
             return *this;
         }
 
-        json_pointer res;
+        json_pointer res = *this;
-        res.reference_tokens = std::vector<string_t>(reference_tokens.begin(), reference_tokens.end() - 1);
+        res.pop_back();
         return res;
     }
 
@@ -260,14 +245,14 @@ class json_pointer
 
   private:
     /// @throw out_of_range.405 always
-    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_no_parent()
+    JSON_HEDLEY_NO_RETURN static void throw_no_parent()
     {
         JSON_THROW(detail::out_of_range::create(detail::exception_id::patch_on_root, "JSON pointer has no parent", nullptr));
     }
 
     /// @throw out_of_range.404 always
     template<typename BasicJsonContext>
-    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_unresolved(const string_t& reference_token, BasicJsonContext context)
+    JSON_HEDLEY_NO_RETURN static void throw_unresolved(const string_t& reference_token, BasicJsonContext context)
     {
         static_cast<void>(reference_token); // unused when JSON_NOEXCEPTION is defined
         static_cast<void>(context);
@@ -320,28 +305,6 @@ class json_pointer
             return array_index_status::not_a_number;
         }
 
-        // fast path: up to 18 decimal digits cannot overflow unsigned long long or
-        // size_type (9 digits for a 32-bit size_type), so strtoull and errno are not needed
-        constexpr std::size_t max_fast_digits = sizeof(size_type) >= 8 ? 18 : 9;
-        if (!s.empty() && s.size() <= max_fast_digits)
-        {
-            size_type acc = 0;
-            for (std::size_t i = 0; i < s.size(); ++i)
-            {
-                const char c = s[i];
-                if (JSON_HEDLEY_UNLIKELY(c < '0' || c > '9'))
-                {
-                    break; // not a plain number: let strtoull decide
-                }
-                acc = static_cast<size_type>(acc * 10 + static_cast<size_type>(c - '0'));
-                if (JSON_HEDLEY_UNLIKELY(i == s.size() - 1))
-                {
-                    idx = acc;
-                    return array_index_status::ok;
-                }
-            }
-        }
-
         const char* p = s.data();
         char* p_end = nullptr; // NOLINT(misc-const-correctness)
         errno = 0; // strtoull doesn't reset errno
@@ -398,83 +361,6 @@ class json_pointer
         return idx;
     }
 
-    /*!
-    @brief compare with a JSON pointer string without splitting it into tokens
-
-    @throw parse_error.107  if the string is not empty or begins with '/'
-    @throw parse_error.108  if character '~' is not followed by '0' or '1'
-    */
-    bool equals_string(const string_t& reference_string) const
-    {
-        if (reference_string.empty())
-        {
-            return reference_tokens.empty();
-        }
-
-        if (JSON_HEDLEY_UNLIKELY(reference_string[0] != '/'))
-        {
-            JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_missing_slash, 1, detail::concat("JSON pointer must be empty or begin with '/' - was: '", reference_string, "'"), nullptr));
-        }
-
-        // the whole string is validated, whether or not it matches
-        const std::size_t size = reference_string.size();
-        for (std::size_t pos = reference_string.find_first_of('~');
-                pos != string_t::npos;
-                pos = reference_string.find_first_of('~', pos + 1))
-        {
-            if (JSON_HEDLEY_UNLIKELY(pos == size - 1 || (reference_string[pos + 1] != '0' && reference_string[pos + 1] != '1')))
-            {
-                JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_invalid_escape, 0, "escape character '~' must be followed with '0' or '1'", nullptr));
-            }
-        }
-
-        // compare token by token, unescaping the string on the fly
-        std::size_t pos = 0; // the slash in front of the next token
-        for (const auto& reference_token : reference_tokens)
-        {
-            if (pos >= size)
-            {
-                return false;
-            }
-
-            std::size_t i = pos + 1;
-            std::size_t j = 0;
-            const std::size_t token_size = reference_token.size();
-            while (i < size && reference_string[i] != '/')
-            {
-                char c = reference_string[i++];
-                if (c == '~')
-                {
-                    c = (reference_string[i++] == '0') ? '~' : '/';
-                }
-                if (j == token_size || reference_token[j] != c)
-                {
-                    return false;
-                }
-                ++j;
-            }
-            if (j != token_size)
-            {
-                return false;
-            }
-            pos = i;
-        }
-        return pos == size;
-    }
-
-    /// @brief object member access with a key that is only copied if it is inserted
-    template<typename BasicJsonType>
-    static BasicJsonType& object_member(BasicJsonType& object, const string_t& key)
-    {
-        auto& members = *object.m_data.m_value.object;
-        const auto it = members.find(key);
-        if (it != members.end())
-        {
-            return it->second;
-        }
-        return object.operator[](key);
-    }
-
   JSON_PRIVATE_UNLESS_TESTED:
     json_pointer top() const
     {
@@ -498,141 +384,84 @@ class json_pointer
     the result independent of the order in which the flattened object is
     iterated, which is unspecified for some object types.
 
-    The prefixes form a tree and are numbered (number 0 is the empty prefix),
+    The prefixes form a tree and are numbered, so each of them is stored only
-    so each of them is stored only once (as a node) rather than as a copy of
+    once (as a node) rather than as a copy of all of its reference tokens.
-    all of its reference tokens. The tree does not own the reference tokens:
-    it refers to the tokens of the parsed keys, which must outlive it.
     */
     struct prefix_tree
     {
-        // open-addressing hash table from (parent, last reference token) to
+        // children[id] maps a reference token to the number of the prefix
-        // the number of the node; empty slots have token == nullptr
+        // extended by that token; number 0 is the empty prefix
-        struct slot
+        std::vector<std::map<string_t, std::size_t>> children;
-        {
-            std::size_t hash;
-            std::size_t parent;
-            const string_t* token;
-            std::size_t id;
-
-            slot() noexcept
-                : hash(0), parent(0), token(nullptr), id(0)
-            {}
-
-            slot(std::size_t h, std::size_t p, const string_t* t, std::size_t i) noexcept
-                : hash(h), parent(p), token(t), id(i)
-            {}
-        };
-
-        std::vector<slot> slots;
-        std::size_t used = 0;
-
-        static std::size_t hash_of(std::size_t parent, const string_t& token) noexcept
-        {
-            std::size_t h = parent * static_cast<std::size_t>(0x9E3779B97F4A7C15ULL);
-            for (std::size_t i = 0; i < token.size(); ++i)
-            {
-                h = (h ^ static_cast<unsigned char>(token[i])) * static_cast<std::size_t>(0x100000001B3ULL);
-            }
-            return h ^ (h >> 29u);
-        }
-
-        void grow()
-        {
-            std::vector<slot> old(slots.size() * 2);
-            old.swap(slots);
-            const std::size_t mask = slots.size() - 1;
-            for (const auto& s : old)
-            {
-                if (s.token != nullptr)
-                {
-                    std::size_t i = s.hash & mask;
-                    while (slots[i].token != nullptr)
-                    {
-                        i = (i + 1) & mask;
-                    }
-                    slots[i] = s;
-                }
-            }
-        }
-
-        // parent[id] is the number of the prefix without its last token
-        std::vector<std::size_t> parent;
         // is_array[id] is true iff some flattened key has the reference token
         // 0 directly below the prefix with number id
         std::vector<bool> is_array;
 
         // start with the empty prefix only
         prefix_tree()
-            : slots(16)
+            : children(1)
-            , parent(1, 0)
             , is_array(1, false)
         {}
 
         // return the number of the prefix with number id extended by
         // reference_token, adding it if it is new
-        std::size_t add_child(std::size_t id, const string_t& reference_token)
+        std::size_t add_child(std::size_t id, string_t&& reference_token)
         {
-            const std::size_t hash = hash_of(id, reference_token);
-            const std::size_t mask = slots.size() - 1;
-            std::size_t i = hash & mask;
-            while (slots[i].token != nullptr)
-            {
-                if (slots[i].hash == hash && slots[i].parent == id && *slots[i].token == reference_token)
-                {
-                    return slots[i].id;
-                }
-                i = (i + 1) & mask;
-            }
-
-            // new prefix
-            const std::size_t child = parent.size();
-            slots[i] = slot(hash, id, &reference_token, child);
             if (reference_token == "0")
             {
                 is_array[id] = true;
             }
-            parent.push_back(id);
-            is_array.push_back(false);
 
-            // keep the load factor below 1/2
+            // read the number before the emplace_back below, which may
-            if (++used * 2 > slots.size())
+            // reallocate children and invalidate the iterator
+            const std::size_t next = children.size();
+            const auto inserted = children[id].emplace(std::move(reference_token), next);
+            const std::size_t child = inserted.first->second;
+            if (inserted.second)
             {
-                grow();
+                children.emplace_back();
+                is_array.push_back(false);
             }
             return child;
         }
+
+        // return the number of the prefix with number id extended by
+        // reference_token, which must have been added before
+        std::size_t find_child(std::size_t id, const string_t& reference_token) const
+        {
+            const auto it = children[id].find(reference_token);
+            JSON_ASSERT(it != children[id].end());
+            return it->second;
+        }
     };
 
     /*!
     @brief create and return a reference to the pointed to value
 
-    @param[in] j  the value to create the pointed to value in
+    Complexity: Linear in the number of reference tokens (times the logarithm
-    @param[in] tokens  the reference tokens of the pointer
+    of the number of siblings for the prefix lookup).
-    @param[in] prefixes  prefixes[i] is the number in @a tree of the prefix
-                         consisting of the first i reference tokens
-
-    Complexity: Linear in the number of reference tokens.
 
     @throw parse_error.106 if an array index begins with '0'
     @throw parse_error.109 if array index is not a number
     @throw type_error.313 if value cannot be unflattened
     */
     template<typename BasicJsonType>
-    static BasicJsonType& get_and_create(BasicJsonType& j, const std::vector<string_t>& tokens,
+    BasicJsonType& get_and_create(BasicJsonType& j, const prefix_tree& tree) const
-                                         const std::vector<std::size_t>& prefixes, const prefix_tree& tree)
     {
         auto* result = &j;
 
+        // the number of the prefix consumed so far; used to look up whether
+        // the value to be created below is an array or an object
+        std::size_t id = 0;
+
         // in case no reference tokens exist, return a reference to the JSON value
         // j which will be overwritten by a primitive value
-        for (std::size_t i = 0; i < tokens.size(); ++i)
+        for (const auto& reference_token : reference_tokens)
         {
-            const auto& reference_token = tokens[i];
             switch (result->type())
             {
                 case detail::value_t::null:
                 {
-                    if (tree.is_array[prefixes[i]])
+                    if (tree.is_array[id])
                     {
                         // some reference token below this position is 0, so the
                         // value is an array
@@ -649,7 +478,7 @@ class json_pointer
                 case detail::value_t::object:
                 {
                     // create an entry in the object
-                    result = &object_member(*result, reference_token);
+                    result = &result->operator[](reference_token);
                     break;
                 }
 
@@ -676,6 +505,8 @@ class json_pointer
                 default:
                     JSON_THROW(detail::type_error::create(detail::exception_id::unflatten_invalid_value, "invalid value to unflatten", &j));
             }
+
+            id = tree.find_child(id, reference_token);
         }
 
         return *result;
@@ -727,7 +558,7 @@ class json_pointer
                 case detail::value_t::object:
                 {
                     // use unchecked object access
-                    ptr = &object_member(*ptr, reference_token);
+                    ptr = &ptr->operator[](reference_token);
                     break;
                 }
 
@@ -777,13 +608,8 @@ class json_pointer
             {
                 case detail::value_t::object:
                 {
-                    const auto it = ptr->m_data.m_value.object->find(reference_token);
+                    // note: at performs range check
-                    if (JSON_HEDLEY_UNLIKELY(it == ptr->m_data.m_value.object->end()))
+                    ptr = &ptr->at(reference_token);
-                    {
-                        // at() throws out_of_range.403 with the usual message
-                        ptr->at(reference_token);
-                    }
-                    ptr = &it->second;
                     break;
                 }
 
@@ -804,7 +630,7 @@ class json_pointer
                         JSON_THROW(detail::out_of_range::create(detail::exception_id::array_index_out_of_range, detail::concat(
                                 "array index ", std::to_string(idx), " is out of range"), ptr));
                     }
-                    ptr = &(*ptr->m_data.m_value.array)[idx];
+                    ptr = &ptr->operator[](idx);
                     break;
                 }
 
@@ -852,9 +678,7 @@ class json_pointer
                 {
                     // use unchecked object access; the const operator[]
                     // asserts that the key exists
-                    const auto it = ptr->m_data.m_value.object->find(reference_token);
+                    ptr = &ptr->operator[](reference_token);
-                    JSON_ASSERT(it != ptr->m_data.m_value.object->end());
-                    ptr = &it->second;
                     break;
                 }
 
@@ -868,9 +692,7 @@ class json_pointer
 
                     // use unchecked array access; the const operator[]
                     // asserts that the index exists
-                    const auto idx = array_index<BasicJsonType>(reference_token);
+                    ptr = &ptr->operator[](array_index<BasicJsonType>(reference_token));
-                    JSON_ASSERT(idx < ptr->m_data.m_value.array->size());
-                    ptr = &(*ptr->m_data.m_value.array)[idx];
                     break;
                 }
 
@@ -911,12 +733,12 @@ class json_pointer
             {
                 case detail::value_t::object:
                 {
-                    const auto it = ptr->m_data.m_value.object->find(reference_token);
+                    const auto it = ptr->find(reference_token);
-                    if (JSON_HEDLEY_UNLIKELY(it == ptr->m_data.m_value.object->end()))
+                    if (JSON_HEDLEY_UNLIKELY(it == ptr->end()))
                     {
                         return nullptr;
                     }
-                    ptr = &it->second;
+                    ptr = &*it;
                     break;
                 }
 
@@ -953,7 +775,7 @@ class json_pointer
                     {
                         return nullptr;
                     }
-                    ptr = &(*ptr->m_data.m_value.array)[idx];
+                    ptr = &ptr->operator[](idx);
                     break;
                 }
 
@@ -986,14 +808,13 @@ class json_pointer
             {
                 case detail::value_t::object:
                 {
-                    const auto it = ptr->m_data.m_value.object->find(reference_token);
+                    if (!ptr->contains(reference_token))
-                    if (it == ptr->m_data.m_value.object->end())
                     {
                         // we did not find the key in the object
                         return false;
                     }
 
-                    ptr = &it->second;
+                    ptr = &ptr->operator[](reference_token);
                     break;
                 }
 
@@ -1015,13 +836,13 @@ class json_pointer
                         return false;
                     }
 
-                    if (idx >= ptr->m_data.m_value.array->size())
+                    if (idx >= ptr->size())
                     {
                         // index out of range
                         return false;
                     }
 
-                    ptr = &(*ptr->m_data.m_value.array)[idx];
+                    ptr = &ptr->operator[](idx);
                     break;
                 }
 
@@ -1071,15 +892,6 @@ class json_pointer
             JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_missing_slash, 1, detail::concat("JSON pointer must be empty or begin with '/' - was: '", reference_string, "'"), nullptr));
         }
 
-        // every slash starts a reference token
-        const std::size_t size = reference_string.size();
-        std::size_t token_count = 0;
-        for (std::size_t i = 0; i < size; ++i)
-        {
-            token_count += (reference_string[i] == '/') ? 1 : 0;
-        }
-        result.reserve(token_count);
-
         // extract the reference tokens:
         // - slash: position of the last read slash (or end of string)
         // - start: position after the previous slash
@@ -1101,52 +913,31 @@ class json_pointer
             const auto count = (slash == string_t::npos ? reference_string.size() : slash) - start;
             auto reference_token = string_t(reference_string.data() + start, count);
 
-            // check reference tokens are properly escaped; a token without
+            // check reference tokens are properly escaped
-            // a '~' (the common case) needs neither check nor unescaping
+            for (std::size_t pos = reference_token.find_first_of('~');
-            std::size_t pos = reference_token.find_first_of('~');
+                    pos != string_t::npos;
-            if (pos != string_t::npos)
+                    pos = reference_token.find_first_of('~', pos + 1))
             {
-                for (; pos != string_t::npos; pos = reference_token.find_first_of('~', pos + 1))
+                JSON_ASSERT(reference_token[pos] == '~');
+
+                // ~ must be followed by 0 or 1
+                if (JSON_HEDLEY_UNLIKELY(pos == reference_token.size() - 1 ||
+                                         (reference_token[pos + 1] != '0' &&
+                                          reference_token[pos + 1] != '1')))
                 {
-                    JSON_ASSERT(reference_token[pos] == '~');
+                    JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_invalid_escape, 0, "escape character '~' must be followed with '0' or '1'", nullptr));
-
-                    // ~ must be followed by 0 or 1
-                    if (JSON_HEDLEY_UNLIKELY(pos == reference_token.size() - 1 ||
-                                             (reference_token[pos + 1] != '0' &&
-                                              reference_token[pos + 1] != '1')))
-                    {
-                        JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_invalid_escape, 0, "escape character '~' must be followed with '0' or '1'", nullptr));
-                    }
                 }
-
-                detail::unescape(reference_token);
             }
 
             // finally, store the reference token
-            result.push_back(std::move(reference_token));
+            detail::unescape(reference_token);
+            result.push_back(reference_token);
         }
 
         return result;
     }
 
   private:
-    // Add the entry (key, v) to the object `obj`. Flattened paths are pairwise
-    // distinct, so objects that can append a key known to be absent
-    // (ordered_map) skip the lookup, which is linear and would make flatten
-    // quadratic; all other object types use operator[].
-    template<typename ObjectType, typename ValueType>
-    static auto add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, int /*unused*/)
-    -> decltype(obj.emplace_new_key(key, std::forward<ValueType>(v)), void())
-    {
-        obj.emplace_new_key(key, std::forward<ValueType>(v));
-    }
-
-    template<typename ObjectType, typename ValueType>
-    static void add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, ...)
-    {
-        obj[key] = std::forward<ValueType>(v);
-    }
-
     /*!
     @param[in] reference_string  the reference string to the current value
     @param[in] value             the value to consider
@@ -1191,8 +982,7 @@ class json_pointer
 
         // flatten `v`, whose path is `path`: primitives and empty containers
         // are added to the result right away; other containers get a frame
-        auto& object = *result.m_data.m_value.object;
+        const auto enter = [&stack, &path, &result](const BasicJsonType & v)
-        const auto enter = [&stack, &path, &object](const BasicJsonType & v)
         {
             switch (v.type())
             {
@@ -1201,7 +991,7 @@ class json_pointer
                     if (v.m_data.m_value.array->empty())
                     {
                         // flatten empty array as null
-                        add_flattened(object, path, nullptr, 0);
+                        result[path] = nullptr;
                     }
                     else
                     {
@@ -1215,7 +1005,7 @@ class json_pointer
                     if (v.m_data.m_value.object->empty())
                     {
                         // flatten empty object as null
-                        add_flattened(object, path, nullptr, 0);
+                        result[path] = nullptr;
                     }
                     else
                     {
@@ -1235,7 +1025,7 @@ class json_pointer
                 default:
                 {
                     // add a primitive value with its reference string
-                    add_flattened(object, path, v, 0);
+                    result[path] = v;
                     return;
                 }
             }
@@ -1281,10 +1071,6 @@ class json_pointer
                 enter(it->second);
             }
         }
-
-        // the entries were added without going through basic_json, so the
-        // parent pointers (JSON_DIAGNOSTICS) have to be set now
-        result.set_parents();
     }
 
     /*!
@@ -1308,53 +1094,21 @@ class json_pointer
 
         BasicJsonType result;
 
-        // parse every key once; the reference tokens are kept for the second
-        // pass (the vectors are never resized, so the tree may refer to them)
-        std::vector<std::vector<string_t>> keys;
-        keys.reserve(value.m_data.m_value.object->size());
-        for (const auto& element : *value.m_data.m_value.object)
-        {
-            json_pointer ptr(element.first);
-            keys.push_back(std::move(ptr.reference_tokens));
-        }
-
         // collect the pointer prefixes that have a reference token 0 among
         // their children; the values below them are arrays, all others are
         // objects (see prefix_tree)
         prefix_tree tree;
-        // the number of the prefix with i + 1 tokens of the previous key; keys
+        for (const auto& element : *value.m_data.m_value.object)
-        // are often sorted, so most of the prefix is the same as for the
-        // previous key and need not be looked up again
-        std::vector<std::size_t> path;
-        const std::vector<string_t>* previous = nullptr;
-        // the number of the complete prefix (i.e., the key) of each key
-        std::vector<std::size_t> leaves;
-        leaves.reserve(keys.size());
-        for (const auto& tokens : keys)
         {
-            std::size_t common = 0;
+            json_pointer ptr(element.first);
-            if (previous != nullptr)
+            std::size_t id = 0;
+            for (auto& reference_token : ptr.reference_tokens)
             {
-                const std::size_t limit = (std::min)(tokens.size(), previous->size());
+                id = tree.add_child(id, std::move(reference_token));
-                while (common < limit && tokens[common] == (*previous)[common])
-                {
-                    ++common;
-                }
             }
-            path.resize(common);
-            std::size_t id = common == 0 ? 0 : path[common - 1];
-            for (std::size_t i = common; i < tokens.size(); ++i)
-            {
-                id = tree.add_child(id, tokens[i]);
-                path.push_back(id);
-            }
-            leaves.push_back(id);
-            previous = &tokens;
         }
 
         // iterate the JSON object values
-        std::vector<std::size_t> prefixes;
-        std::size_t key_index = 0;
         for (const auto& element : *value.m_data.m_value.object)
         {
             if (JSON_HEDLEY_UNLIKELY(!element.second.is_primitive()))
@@ -1362,21 +1116,11 @@ class json_pointer
                 JSON_THROW(detail::type_error::create(detail::exception_id::unflatten_value_not_primitive, "values in object must be primitive", &element.second));
             }
 
-            const auto& tokens = keys[key_index];
-            // number the prefixes of this key from its last one to the first
-            prefixes.resize(tokens.size());
-            for (std::size_t i = tokens.size(), id = leaves[key_index]; i > 0; --i)
-            {
-                id = tree.parent[id];
-                prefixes[i - 1] = id;
-            }
-            ++key_index;
-
             // Assign the value to the reference pointed to by JSON pointer. Note
             // that if the JSON pointer is "" (i.e., points to the whole value),
             // function get_and_create returns a reference to the result itself.
             // An assignment will then create a primitive value.
-            get_and_create(result, tokens, prefixes, tree) = element.second;
+            json_pointer(element.first).get_and_create(result, tree) = element.second;
         }
 
         return result;
@@ -1415,7 +1159,7 @@ class json_pointer
         = delete;
 #else
     {
-        return equals_string(rhs);
+        return *this == json_pointer(rhs);
     }
 #endif
 
@@ -1499,7 +1243,7 @@ inline bool operator==(const json_pointer<RefStringTypeLhs>& lhs,
     = delete;
 #else
 {
-    return lhs.equals_string(rhs);
+    return lhs == json_pointer<RefStringTypeLhs>(rhs);
 }
 #endif
 
@@ -1512,7 +1256,7 @@ inline bool operator==(const StringType& lhs,
     = delete;
 #else
 {
-    return rhs.equals_string(lhs);
+    return json_pointer<RefStringTypeRhs>(lhs) == rhs;
 }
 #endif
 

include/nlohmann/detail/string_escape.hpp

@@ -9,7 +9,6 @@
 #pragma once
 
 #include <cstddef> // size_t
-#include <utility> // move
 
 #include <nlohmann/detail/abi_macros.hpp>
 
@@ -25,46 +24,39 @@ namespace detail
  * Note the order of escaping "~" to "~0" and "/" to "~1" is important.
  *
  * The string is rebuilt in a single pass, appending whole runs between the
- * characters that need escaping, while repeated replace() calls would move
+ * characters that need escaping. Scanning with find_first_of() keeps the
- * the tail of the string once per escaped character. @ref escape_into appends
+ * common case -- nothing to escape -- as fast as a single search, while
- * the escaped string to an existing one.
+ * repeated replace() calls would move the tail of the string once per
+ * escaped character.
  */
-template<typename StringType>
-inline void escape_into(StringType& out, const StringType& s)
-{
-    const std::size_t size = s.size();
-    std::size_t run = 0;
-    for (std::size_t i = 0; i < size; ++i)
-    {
-        const char c = s[i];
-        if (c == '~' || c == '/')
-        {
-            out.append(s.data() + run, i - run);
-            out.append(c == '~' ? "~0" : "~1", 2);
-            run = i + 1;
-        }
-    }
-    out.append(s.data() + run, size - run);
-}
-
 template<typename StringType>
 inline StringType escape(const StringType& s)
 {
-    // a single scan for both special characters; nothing to escape is the common case
+    auto next_special = [&s](std::size_t from)
-    const std::size_t size = s.size();
-    std::size_t i = 0;
-    while (i < size && s[i] != '~' && s[i] != '/')
     {
-        ++i;
+        const auto tilde = s.find_first_of('~', from);
-    }
+        const auto slash = s.find_first_of('/', from);
-    if (i == size)
+        return tilde < slash ? tilde : slash; // npos is the largest value
+    };
+
+    auto pos = next_special(0);
+    if (pos == StringType::npos)
     {
         return s;
     }
 
     StringType result;
-    result.reserve(size + 2);
+    result.reserve(s.size() + 2);
-    escape_into(result, s);
+
+    std::size_t run = 0;
+    while (pos != StringType::npos)
+    {
+        result.append(s.data() + run, pos - run);
+        result.append(s[pos] == '~' ? "~0" : "~1", 2);
+        run = pos + 1;
+        pos = next_special(run);
+    }
+    result.append(s.data() + run, s.size() - run);
     return result;
 }
 
@@ -109,7 +101,7 @@ inline void unescape(StringType& s)
         pos = s.find_first_of('~', run);
     }
     result.append(s.data() + run, s.size() - run);
-    s = std::move(result);
+    s = result;
 }
 
 }  // namespace detail

include/nlohmann/json.hpp

@@ -6562,18 +6562,24 @@ public:
         };
 
         // wrapper for "add" operation; add value at ptr
-        const auto operation_add = [&result](json_pointer & ptr, basic_json val)
+        const auto operation_add = [&result](json_pointer & ptr, const basic_json & val)
         {
             // adding to the root of the target document means replacing it
             if (ptr.empty())
             {
-                result = std::move(val);
+                result = val;
                 return;
             }
 
-            // get reference to the parent of the JSON pointer ptr; a missing
+            // make sure the top element of the pointer exists
-            // parent (or one of its ancestors) is reported by at()
+            json_pointer const top_pointer = ptr.top();
-            auto last_path = std::move(ptr.reference_tokens.back());
+            if (top_pointer != ptr)
+            {
+                result.at(top_pointer);
+            }
+
+            // get reference to the parent of the JSON pointer ptr
+            const auto last_path = ptr.back();
             ptr.pop_back();
             // parent must exist when performing patch add per RFC6902 specs
             basic_json& parent = result.at(ptr);
@@ -6584,7 +6590,7 @@ public:
                 case value_t::object:
                 {
                     // use operator[] to add value
-                    parent[std::move(last_path)] = std::move(val);
+                    parent[last_path] = val;
                     break;
                 }
 
@@ -6593,7 +6599,7 @@ public:
                     if (last_path == "-")
                     {
                         // special case: append to back
-                        parent.push_back(std::move(val));
+                        parent.push_back(val);
                     }
                     else
                     {
@@ -6605,7 +6611,7 @@ public:
                         }
 
                         // default case: insert add offset
-                        parent.insert(parent.begin() + static_cast<difference_type>(idx), std::move(val));
+                        parent.insert(parent.begin() + static_cast<difference_type>(idx), val);
                     }
                     break;
                 }
@@ -6628,8 +6634,7 @@ public:
         const auto operation_remove = [this, & result](json_pointer & ptr)
         {
             // get reference to the parent of the JSON pointer ptr
-            static_cast<void>(ptr.back()); // throws out_of_range.405 if ptr is the root
+            const auto last_path = ptr.back();
-            const auto last_path = std::move(ptr.reference_tokens.back());
             ptr.pop_back();
             basic_json& parent = result.at(ptr);
 
@@ -6729,8 +6734,8 @@ public:
             }
 
             // collect mandatory members
-            const string_t& op = *get_value("op", "op", true).m_data.m_value.string;
+            const auto op = get_value("op", "op", true).template get<string_t>();
-            const string_t& path = *get_value(op, "path", true).m_data.m_value.string;
+            const auto path = get_value(op, "path", true).template get<string_t>();
             json_pointer ptr(path);
 
             switch (get_op(op))
@@ -6756,7 +6761,7 @@ public:
 
                 case patch_operations::move:
                 {
-                    const string_t& from_path = *get_value("move", "from", true).m_data.m_value.string;
+                    const auto from_path = get_value("move", "from", true).template get<string_t>();
                     json_pointer from_ptr(from_path);
 
                     if (JSON_HEDLEY_UNLIKELY(is_proper_prefix(from_ptr, ptr)))
@@ -6765,28 +6770,29 @@ public:
                     }
 
                     // the "from" location must exist - use at()
-                    // a root "from" is rejected by operation_remove below, which must leave result intact
+                    basic_json const v = result.at(from_ptr);
-                    basic_json v = from_ptr.empty() ? basic_json(result) : std::move(result.at(from_ptr));
 
                     // The move operation is functionally identical to a
                     // "remove" operation on the "from" location, followed
                     // immediately by an "add" operation at the target
                     // location with the value that was just removed.
                     operation_remove(from_ptr);
-                    operation_add(ptr, std::move(v));
+                    operation_add(ptr, v);
                     break;
                 }
 
                 case patch_operations::copy:
                 {
-                    const string_t& from_path = *get_value("copy", "from", true).m_data.m_value.string;
+                    const auto from_path = get_value("copy", "from", true).template get<string_t>();
                     const json_pointer from_ptr(from_path);
 
+                    // the "from" location must exist - use at()
+                    basic_json const v = result.at(from_ptr);
+
                     // The copy is functionally identical to an "add"
                     // operation at the target location using the value
-                    // specified in the "from" member; the "from" location
+                    // specified in the "from" member.
-                    // must exist - use at()
+                    operation_add(ptr, v);
-                    operation_add(ptr, result.at(from_ptr));
                     break;
                 }
 

include/nlohmann/ordered_map.hpp

@@ -143,17 +143,6 @@ public:
         return {std::prev(this->end()), true};
     }
 
-    /// @brief add an element at the end without checking whether the key exists
-    /// @note The caller must guarantee that @a key is not yet contained, otherwise
-    ///       the container holds duplicate keys. This avoids the linear search of
-    ///       emplace() and operator[] when many keys known to be new are added.
-    template<class V, detail::enable_if_t<
-                 detail::is_constructible<T, V>::value, int> = 0>
-    void emplace_new_key(const key_type& key, V && t)
-    {
-        append(key, std::forward<V>(t));
-    }
-
     T& operator[](const key_type& key)
     {
         return emplace(key, T{}).first->second;

single_include/nlohmann/json.hpp

@@ -3415,7 +3415,6 @@ NLOHMANN_JSON_NAMESPACE_END
 
 
 #include <cstddef> // size_t
-#include <utility> // move
 
 // #include <nlohmann/detail/abi_macros.hpp>
 
@@ -3432,46 +3431,39 @@ namespace detail
  * Note the order of escaping "~" to "~0" and "/" to "~1" is important.
  *
  * The string is rebuilt in a single pass, appending whole runs between the
- * characters that need escaping, while repeated replace() calls would move
+ * characters that need escaping. Scanning with find_first_of() keeps the
- * the tail of the string once per escaped character. @ref escape_into appends
+ * common case -- nothing to escape -- as fast as a single search, while
- * the escaped string to an existing one.
+ * repeated replace() calls would move the tail of the string once per
+ * escaped character.
  */
-template<typename StringType>
-inline void escape_into(StringType& out, const StringType& s)
-{
-    const std::size_t size = s.size();
-    std::size_t run = 0;
-    for (std::size_t i = 0; i < size; ++i)
-    {
-        const char c = s[i];
-        if (c == '~' || c == '/')
-        {
-            out.append(s.data() + run, i - run);
-            out.append(c == '~' ? "~0" : "~1", 2);
-            run = i + 1;
-        }
-    }
-    out.append(s.data() + run, size - run);
-}
-
 template<typename StringType>
 inline StringType escape(const StringType& s)
 {
-    // a single scan for both special characters; nothing to escape is the common case
+    auto next_special = [&s](std::size_t from)
-    const std::size_t size = s.size();
-    std::size_t i = 0;
-    while (i < size && s[i] != '~' && s[i] != '/')
     {
-        ++i;
+        const auto tilde = s.find_first_of('~', from);
-    }
+        const auto slash = s.find_first_of('/', from);
-    if (i == size)
+        return tilde < slash ? tilde : slash; // npos is the largest value
+    };
+
+    auto pos = next_special(0);
+    if (pos == StringType::npos)
     {
         return s;
     }
 
     StringType result;
-    result.reserve(size + 2);
+    result.reserve(s.size() + 2);
-    escape_into(result, s);
+
+    std::size_t run = 0;
+    while (pos != StringType::npos)
+    {
+        result.append(s.data() + run, pos - run);
+        result.append(s[pos] == '~' ? "~0" : "~1", 2);
+        run = pos + 1;
+        pos = next_special(run);
+    }
+    result.append(s.data() + run, s.size() - run);
     return result;
 }
 
@@ -3516,7 +3508,7 @@ inline void unescape(StringType& s)
         pos = s.find_first_of('~', run);
     }
     result.append(s.data() + run, s.size() - run);
-    s = std::move(result);
+    s = result;
 }
 
 }  // namespace detail
@@ -13858,19 +13850,16 @@ class json_sax_dom_callback_parser
         if (keep && ref_stack.back())
         {
             auto& obj = *ref_stack.back()->m_data.m_value.object;
-            // a single lookup: insert the placeholder, or find the existing member
+            const auto it = obj.find(val);
-            const auto inserted = obj.emplace(val, discarded);
+            if (it != obj.end())
-            const auto it = inserted.first;
-            if (!inserted.second)
             {
                 // this is a duplicate key (legal in JSON); remember its
                 // current value so it can be restored later if the new
                 // value is rejected by the callback, instead of being
                 // erased together with the discarded placeholder
                 duplicate_key_stash.emplace_back(&(it->second), it->second);
-                it->second = discarded;
             }
-            object_element = &(it->second);
+            object_element = &(obj[val] = discarded);
         }
 
         return true;
@@ -20642,6 +20631,8 @@ NLOHMANN_JSON_NAMESPACE_END
     #include <iosfwd> // ostream
 #endif  // JSON_NO_IO
 #include <limits> // max
+#include <map> // map
+#include <numeric> // accumulate
 #include <string> // string
 #include <utility> // move
 #include <vector> // vector
@@ -20699,21 +20690,12 @@ class json_pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/to_string/
     string_t to_string() const
     {
-        // one buffer: every token adds its escaped form (at least its length) and a slash
+        return std::accumulate(reference_tokens.begin(), reference_tokens.end(),
-        std::size_t length = 0;
+                               string_t{},
-        for (const auto& reference_token : reference_tokens)
+                               [](const string_t& a, const string_t& b)
         {
-            length += reference_token.size() + 1;
+            return detail::concat<string_t>(a, '/', detail::escape(b));
-        }
+        });
-
-        string_t result;
-        result.reserve(length);
-        for (const auto& reference_token : reference_tokens)
-        {
-            result.append("/", 1);
-            detail::escape_into(result, reference_token);
-        }
-        return result;
     }
 
     /// @brief return a string representation of the JSON pointer
@@ -20768,29 +20750,21 @@ class json_pointer
     friend json_pointer operator/(const json_pointer& lhs,
                                   const json_pointer& rhs)
     {
-        json_pointer result;
+        return json_pointer(lhs) /= rhs;
-        result.reference_tokens.reserve(lhs.reference_tokens.size() + rhs.reference_tokens.size());
-        result.reference_tokens.insert(result.reference_tokens.end(), lhs.reference_tokens.begin(), lhs.reference_tokens.end());
-        result.reference_tokens.insert(result.reference_tokens.end(), rhs.reference_tokens.begin(), rhs.reference_tokens.end());
-        return result;
     }
 
     /// @brief create a new JSON pointer by appending the unescaped token at the end of the JSON pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/operator_slash/
     friend json_pointer operator/(const json_pointer& lhs, string_t token) // NOLINT(performance-unnecessary-value-param)
     {
-        json_pointer result;
+        return json_pointer(lhs) /= std::move(token);
-        result.reference_tokens.reserve(lhs.reference_tokens.size() + 1);
-        result.reference_tokens.insert(result.reference_tokens.end(), lhs.reference_tokens.begin(), lhs.reference_tokens.end());
-        result.reference_tokens.push_back(std::move(token));
-        return result;
     }
 
     /// @brief create a new JSON pointer by appending the array-index-token at the end of the JSON pointer
     /// @sa https://json.nlohmann.me/api/json_pointer/operator_slash/
     friend json_pointer operator/(const json_pointer& lhs, std::size_t array_idx)
     {
-        return lhs / detail::to_string<string_t>(array_idx);
+        return json_pointer(lhs) /= array_idx;
     }
 
     /// @brief returns the parent of this JSON pointer
@@ -20802,8 +20776,8 @@ class json_pointer
             return *this;
         }
 
-        json_pointer res;
+        json_pointer res = *this;
-        res.reference_tokens = std::vector<string_t>(reference_tokens.begin(), reference_tokens.end() - 1);
+        res.pop_back();
         return res;
     }
 
@@ -20892,14 +20866,14 @@ class json_pointer
 
   private:
     /// @throw out_of_range.405 always
-    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_no_parent()
+    JSON_HEDLEY_NO_RETURN static void throw_no_parent()
     {
         JSON_THROW(detail::out_of_range::create(detail::exception_id::patch_on_root, "JSON pointer has no parent", nullptr));
     }
 
     /// @throw out_of_range.404 always
     template<typename BasicJsonContext>
-    JSON_HEDLEY_NEVER_INLINE JSON_HEDLEY_NO_RETURN static void throw_unresolved(const string_t& reference_token, BasicJsonContext context)
+    JSON_HEDLEY_NO_RETURN static void throw_unresolved(const string_t& reference_token, BasicJsonContext context)
     {
         static_cast<void>(reference_token); // unused when JSON_NOEXCEPTION is defined
         static_cast<void>(context);
@@ -20952,28 +20926,6 @@ class json_pointer
             return array_index_status::not_a_number;
         }
 
-        // fast path: up to 18 decimal digits cannot overflow unsigned long long or
-        // size_type (9 digits for a 32-bit size_type), so strtoull and errno are not needed
-        constexpr std::size_t max_fast_digits = sizeof(size_type) >= 8 ? 18 : 9;
-        if (!s.empty() && s.size() <= max_fast_digits)
-        {
-            size_type acc = 0;
-            for (std::size_t i = 0; i < s.size(); ++i)
-            {
-                const char c = s[i];
-                if (JSON_HEDLEY_UNLIKELY(c < '0' || c > '9'))
-                {
-                    break; // not a plain number: let strtoull decide
-                }
-                acc = static_cast<size_type>(acc * 10 + static_cast<size_type>(c - '0'));
-                if (JSON_HEDLEY_UNLIKELY(i == s.size() - 1))
-                {
-                    idx = acc;
-                    return array_index_status::ok;
-                }
-            }
-        }
-
         const char* p = s.data();
         char* p_end = nullptr; // NOLINT(misc-const-correctness)
         errno = 0; // strtoull doesn't reset errno
@@ -21030,83 +20982,6 @@ class json_pointer
         return idx;
     }
 
-    /*!
-    @brief compare with a JSON pointer string without splitting it into tokens
-
-    @throw parse_error.107  if the string is not empty or begins with '/'
-    @throw parse_error.108  if character '~' is not followed by '0' or '1'
-    */
-    bool equals_string(const string_t& reference_string) const
-    {
-        if (reference_string.empty())
-        {
-            return reference_tokens.empty();
-        }
-
-        if (JSON_HEDLEY_UNLIKELY(reference_string[0] != '/'))
-        {
-            JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_missing_slash, 1, detail::concat("JSON pointer must be empty or begin with '/' - was: '", reference_string, "'"), nullptr));
-        }
-
-        // the whole string is validated, whether or not it matches
-        const std::size_t size = reference_string.size();
-        for (std::size_t pos = reference_string.find_first_of('~');
-                pos != string_t::npos;
-                pos = reference_string.find_first_of('~', pos + 1))
-        {
-            if (JSON_HEDLEY_UNLIKELY(pos == size - 1 || (reference_string[pos + 1] != '0' && reference_string[pos + 1] != '1')))
-            {
-                JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_invalid_escape, 0, "escape character '~' must be followed with '0' or '1'", nullptr));
-            }
-        }
-
-        // compare token by token, unescaping the string on the fly
-        std::size_t pos = 0; // the slash in front of the next token
-        for (const auto& reference_token : reference_tokens)
-        {
-            if (pos >= size)
-            {
-                return false;
-            }
-
-            std::size_t i = pos + 1;
-            std::size_t j = 0;
-            const std::size_t token_size = reference_token.size();
-            while (i < size && reference_string[i] != '/')
-            {
-                char c = reference_string[i++];
-                if (c == '~')
-                {
-                    c = (reference_string[i++] == '0') ? '~' : '/';
-                }
-                if (j == token_size || reference_token[j] != c)
-                {
-                    return false;
-                }
-                ++j;
-            }
-            if (j != token_size)
-            {
-                return false;
-            }
-            pos = i;
-        }
-        return pos == size;
-    }
-
-    /// @brief object member access with a key that is only copied if it is inserted
-    template<typename BasicJsonType>
-    static BasicJsonType& object_member(BasicJsonType& object, const string_t& key)
-    {
-        auto& members = *object.m_data.m_value.object;
-        const auto it = members.find(key);
-        if (it != members.end())
-        {
-            return it->second;
-        }
-        return object.operator[](key);
-    }
-
   JSON_PRIVATE_UNLESS_TESTED:
     json_pointer top() const
     {
@@ -21130,141 +21005,84 @@ class json_pointer
     the result independent of the order in which the flattened object is
     iterated, which is unspecified for some object types.
 
-    The prefixes form a tree and are numbered (number 0 is the empty prefix),
+    The prefixes form a tree and are numbered, so each of them is stored only
-    so each of them is stored only once (as a node) rather than as a copy of
+    once (as a node) rather than as a copy of all of its reference tokens.
-    all of its reference tokens. The tree does not own the reference tokens:
-    it refers to the tokens of the parsed keys, which must outlive it.
     */
     struct prefix_tree
     {
-        // open-addressing hash table from (parent, last reference token) to
+        // children[id] maps a reference token to the number of the prefix
-        // the number of the node; empty slots have token == nullptr
+        // extended by that token; number 0 is the empty prefix
-        struct slot
+        std::vector<std::map<string_t, std::size_t>> children;
-        {
-            std::size_t hash;
-            std::size_t parent;
-            const string_t* token;
-            std::size_t id;
-
-            slot() noexcept
-                : hash(0), parent(0), token(nullptr), id(0)
-            {}
-
-            slot(std::size_t h, std::size_t p, const string_t* t, std::size_t i) noexcept
-                : hash(h), parent(p), token(t), id(i)
-            {}
-        };
-
-        std::vector<slot> slots;
-        std::size_t used = 0;
-
-        static std::size_t hash_of(std::size_t parent, const string_t& token) noexcept
-        {
-            std::size_t h = parent * static_cast<std::size_t>(0x9E3779B97F4A7C15ULL);
-            for (std::size_t i = 0; i < token.size(); ++i)
-            {
-                h = (h ^ static_cast<unsigned char>(token[i])) * static_cast<std::size_t>(0x100000001B3ULL);
-            }
-            return h ^ (h >> 29u);
-        }
-
-        void grow()
-        {
-            std::vector<slot> old(slots.size() * 2);
-            old.swap(slots);
-            const std::size_t mask = slots.size() - 1;
-            for (const auto& s : old)
-            {
-                if (s.token != nullptr)
-                {
-                    std::size_t i = s.hash & mask;
-                    while (slots[i].token != nullptr)
-                    {
-                        i = (i + 1) & mask;
-                    }
-                    slots[i] = s;
-                }
-            }
-        }
-
-        // parent[id] is the number of the prefix without its last token
-        std::vector<std::size_t> parent;
         // is_array[id] is true iff some flattened key has the reference token
         // 0 directly below the prefix with number id
         std::vector<bool> is_array;
 
         // start with the empty prefix only
         prefix_tree()
-            : slots(16)
+            : children(1)
-            , parent(1, 0)
             , is_array(1, false)
         {}
 
         // return the number of the prefix with number id extended by
         // reference_token, adding it if it is new
-        std::size_t add_child(std::size_t id, const string_t& reference_token)
+        std::size_t add_child(std::size_t id, string_t&& reference_token)
         {
-            const std::size_t hash = hash_of(id, reference_token);
-            const std::size_t mask = slots.size() - 1;
-            std::size_t i = hash & mask;
-            while (slots[i].token != nullptr)
-            {
-                if (slots[i].hash == hash && slots[i].parent == id && *slots[i].token == reference_token)
-                {
-                    return slots[i].id;
-                }
-                i = (i + 1) & mask;
-            }
-
-            // new prefix
-            const std::size_t child = parent.size();
-            slots[i] = slot(hash, id, &reference_token, child);
             if (reference_token == "0")
             {
                 is_array[id] = true;
             }
-            parent.push_back(id);
-            is_array.push_back(false);
 
-            // keep the load factor below 1/2
+            // read the number before the emplace_back below, which may
-            if (++used * 2 > slots.size())
+            // reallocate children and invalidate the iterator
+            const std::size_t next = children.size();
+            const auto inserted = children[id].emplace(std::move(reference_token), next);
+            const std::size_t child = inserted.first->second;
+            if (inserted.second)
             {
-                grow();
+                children.emplace_back();
+                is_array.push_back(false);
             }
             return child;
         }
+
+        // return the number of the prefix with number id extended by
+        // reference_token, which must have been added before
+        std::size_t find_child(std::size_t id, const string_t& reference_token) const
+        {
+            const auto it = children[id].find(reference_token);
+            JSON_ASSERT(it != children[id].end());
+            return it->second;
+        }
     };
 
     /*!
     @brief create and return a reference to the pointed to value
 
-    @param[in] j  the value to create the pointed to value in
+    Complexity: Linear in the number of reference tokens (times the logarithm
-    @param[in] tokens  the reference tokens of the pointer
+    of the number of siblings for the prefix lookup).
-    @param[in] prefixes  prefixes[i] is the number in @a tree of the prefix
-                         consisting of the first i reference tokens
-
-    Complexity: Linear in the number of reference tokens.
 
     @throw parse_error.106 if an array index begins with '0'
     @throw parse_error.109 if array index is not a number
     @throw type_error.313 if value cannot be unflattened
     */
     template<typename BasicJsonType>
-    static BasicJsonType& get_and_create(BasicJsonType& j, const std::vector<string_t>& tokens,
+    BasicJsonType& get_and_create(BasicJsonType& j, const prefix_tree& tree) const
-                                         const std::vector<std::size_t>& prefixes, const prefix_tree& tree)
     {
         auto* result = &j;
 
+        // the number of the prefix consumed so far; used to look up whether
+        // the value to be created below is an array or an object
+        std::size_t id = 0;
+
         // in case no reference tokens exist, return a reference to the JSON value
         // j which will be overwritten by a primitive value
-        for (std::size_t i = 0; i < tokens.size(); ++i)
+        for (const auto& reference_token : reference_tokens)
         {
-            const auto& reference_token = tokens[i];
             switch (result->type())
             {
                 case detail::value_t::null:
                 {
-                    if (tree.is_array[prefixes[i]])
+                    if (tree.is_array[id])
                     {
                         // some reference token below this position is 0, so the
                         // value is an array
@@ -21281,7 +21099,7 @@ class json_pointer
                 case detail::value_t::object:
                 {
                     // create an entry in the object
-                    result = &object_member(*result, reference_token);
+                    result = &result->operator[](reference_token);
                     break;
                 }
 
@@ -21308,6 +21126,8 @@ class json_pointer
                 default:
                     JSON_THROW(detail::type_error::create(detail::exception_id::unflatten_invalid_value, "invalid value to unflatten", &j));
             }
+
+            id = tree.find_child(id, reference_token);
         }
 
         return *result;
@@ -21359,7 +21179,7 @@ class json_pointer
                 case detail::value_t::object:
                 {
                     // use unchecked object access
-                    ptr = &object_member(*ptr, reference_token);
+                    ptr = &ptr->operator[](reference_token);
                     break;
                 }
 
@@ -21409,13 +21229,8 @@ class json_pointer
             {
                 case detail::value_t::object:
                 {
-                    const auto it = ptr->m_data.m_value.object->find(reference_token);
+                    // note: at performs range check
-                    if (JSON_HEDLEY_UNLIKELY(it == ptr->m_data.m_value.object->end()))
+                    ptr = &ptr->at(reference_token);
-                    {
-                        // at() throws out_of_range.403 with the usual message
-                        ptr->at(reference_token);
-                    }
-                    ptr = &it->second;
                     break;
                 }
 
@@ -21436,7 +21251,7 @@ class json_pointer
                         JSON_THROW(detail::out_of_range::create(detail::exception_id::array_index_out_of_range, detail::concat(
                                 "array index ", std::to_string(idx), " is out of range"), ptr));
                     }
-                    ptr = &(*ptr->m_data.m_value.array)[idx];
+                    ptr = &ptr->operator[](idx);
                     break;
                 }
 
@@ -21484,9 +21299,7 @@ class json_pointer
                 {
                     // use unchecked object access; the const operator[]
                     // asserts that the key exists
-                    const auto it = ptr->m_data.m_value.object->find(reference_token);
+                    ptr = &ptr->operator[](reference_token);
-                    JSON_ASSERT(it != ptr->m_data.m_value.object->end());
-                    ptr = &it->second;
                     break;
                 }
 
@@ -21500,9 +21313,7 @@ class json_pointer
 
                     // use unchecked array access; the const operator[]
                     // asserts that the index exists
-                    const auto idx = array_index<BasicJsonType>(reference_token);
+                    ptr = &ptr->operator[](array_index<BasicJsonType>(reference_token));
-                    JSON_ASSERT(idx < ptr->m_data.m_value.array->size());
-                    ptr = &(*ptr->m_data.m_value.array)[idx];
                     break;
                 }
 
@@ -21543,12 +21354,12 @@ class json_pointer
             {
                 case detail::value_t::object:
                 {
-                    const auto it = ptr->m_data.m_value.object->find(reference_token);
+                    const auto it = ptr->find(reference_token);
-                    if (JSON_HEDLEY_UNLIKELY(it == ptr->m_data.m_value.object->end()))
+                    if (JSON_HEDLEY_UNLIKELY(it == ptr->end()))
                     {
                         return nullptr;
                     }
-                    ptr = &it->second;
+                    ptr = &*it;
                     break;
                 }
 
@@ -21585,7 +21396,7 @@ class json_pointer
                     {
                         return nullptr;
                     }
-                    ptr = &(*ptr->m_data.m_value.array)[idx];
+                    ptr = &ptr->operator[](idx);
                     break;
                 }
 
@@ -21618,14 +21429,13 @@ class json_pointer
             {
                 case detail::value_t::object:
                 {
-                    const auto it = ptr->m_data.m_value.object->find(reference_token);
+                    if (!ptr->contains(reference_token))
-                    if (it == ptr->m_data.m_value.object->end())
                     {
                         // we did not find the key in the object
                         return false;
                     }
 
-                    ptr = &it->second;
+                    ptr = &ptr->operator[](reference_token);
                     break;
                 }
 
@@ -21647,13 +21457,13 @@ class json_pointer
                         return false;
                     }
 
-                    if (idx >= ptr->m_data.m_value.array->size())
+                    if (idx >= ptr->size())
                     {
                         // index out of range
                         return false;
                     }
 
-                    ptr = &(*ptr->m_data.m_value.array)[idx];
+                    ptr = &ptr->operator[](idx);
                     break;
                 }
 
@@ -21703,15 +21513,6 @@ class json_pointer
             JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_missing_slash, 1, detail::concat("JSON pointer must be empty or begin with '/' - was: '", reference_string, "'"), nullptr));
         }
 
-        // every slash starts a reference token
-        const std::size_t size = reference_string.size();
-        std::size_t token_count = 0;
-        for (std::size_t i = 0; i < size; ++i)
-        {
-            token_count += (reference_string[i] == '/') ? 1 : 0;
-        }
-        result.reserve(token_count);
-
         // extract the reference tokens:
         // - slash: position of the last read slash (or end of string)
         // - start: position after the previous slash
@@ -21733,52 +21534,31 @@ class json_pointer
             const auto count = (slash == string_t::npos ? reference_string.size() : slash) - start;
             auto reference_token = string_t(reference_string.data() + start, count);
 
-            // check reference tokens are properly escaped; a token without
+            // check reference tokens are properly escaped
-            // a '~' (the common case) needs neither check nor unescaping
+            for (std::size_t pos = reference_token.find_first_of('~');
-            std::size_t pos = reference_token.find_first_of('~');
+                    pos != string_t::npos;
-            if (pos != string_t::npos)
+                    pos = reference_token.find_first_of('~', pos + 1))
             {
-                for (; pos != string_t::npos; pos = reference_token.find_first_of('~', pos + 1))
+                JSON_ASSERT(reference_token[pos] == '~');
+
+                // ~ must be followed by 0 or 1
+                if (JSON_HEDLEY_UNLIKELY(pos == reference_token.size() - 1 ||
+                                         (reference_token[pos + 1] != '0' &&
+                                          reference_token[pos + 1] != '1')))
                 {
-                    JSON_ASSERT(reference_token[pos] == '~');
+                    JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_invalid_escape, 0, "escape character '~' must be followed with '0' or '1'", nullptr));
-
-                    // ~ must be followed by 0 or 1
-                    if (JSON_HEDLEY_UNLIKELY(pos == reference_token.size() - 1 ||
-                                             (reference_token[pos + 1] != '0' &&
-                                              reference_token[pos + 1] != '1')))
-                    {
-                        JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_invalid_escape, 0, "escape character '~' must be followed with '0' or '1'", nullptr));
-                    }
                 }
-
-                detail::unescape(reference_token);
             }
 
             // finally, store the reference token
-            result.push_back(std::move(reference_token));
+            detail::unescape(reference_token);
+            result.push_back(reference_token);
         }
 
         return result;
     }
 
   private:
-    // Add the entry (key, v) to the object `obj`. Flattened paths are pairwise
-    // distinct, so objects that can append a key known to be absent
-    // (ordered_map) skip the lookup, which is linear and would make flatten
-    // quadratic; all other object types use operator[].
-    template<typename ObjectType, typename ValueType>
-    static auto add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, int /*unused*/)
-    -> decltype(obj.emplace_new_key(key, std::forward<ValueType>(v)), void())
-    {
-        obj.emplace_new_key(key, std::forward<ValueType>(v));
-    }
-
-    template<typename ObjectType, typename ValueType>
-    static void add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, ...)
-    {
-        obj[key] = std::forward<ValueType>(v);
-    }
-
     /*!
     @param[in] reference_string  the reference string to the current value
     @param[in] value             the value to consider
@@ -21823,8 +21603,7 @@ class json_pointer
 
         // flatten `v`, whose path is `path`: primitives and empty containers
         // are added to the result right away; other containers get a frame
-        auto& object = *result.m_data.m_value.object;
+        const auto enter = [&stack, &path, &result](const BasicJsonType & v)
-        const auto enter = [&stack, &path, &object](const BasicJsonType & v)
         {
             switch (v.type())
             {
@@ -21833,7 +21612,7 @@ class json_pointer
                     if (v.m_data.m_value.array->empty())
                     {
                         // flatten empty array as null
-                        add_flattened(object, path, nullptr, 0);
+                        result[path] = nullptr;
                     }
                     else
                     {
@@ -21847,7 +21626,7 @@ class json_pointer
                     if (v.m_data.m_value.object->empty())
                     {
                         // flatten empty object as null
-                        add_flattened(object, path, nullptr, 0);
+                        result[path] = nullptr;
                     }
                     else
                     {
@@ -21867,7 +21646,7 @@ class json_pointer
                 default:
                 {
                     // add a primitive value with its reference string
-                    add_flattened(object, path, v, 0);
+                    result[path] = v;
                     return;
                 }
             }
@@ -21913,10 +21692,6 @@ class json_pointer
                 enter(it->second);
             }
         }
-
-        // the entries were added without going through basic_json, so the
-        // parent pointers (JSON_DIAGNOSTICS) have to be set now
-        result.set_parents();
     }
 
     /*!
@@ -21940,53 +21715,21 @@ class json_pointer
 
         BasicJsonType result;
 
-        // parse every key once; the reference tokens are kept for the second
-        // pass (the vectors are never resized, so the tree may refer to them)
-        std::vector<std::vector<string_t>> keys;
-        keys.reserve(value.m_data.m_value.object->size());
-        for (const auto& element : *value.m_data.m_value.object)
-        {
-            json_pointer ptr(element.first);
-            keys.push_back(std::move(ptr.reference_tokens));
-        }
-
         // collect the pointer prefixes that have a reference token 0 among
         // their children; the values below them are arrays, all others are
         // objects (see prefix_tree)
         prefix_tree tree;
-        // the number of the prefix with i + 1 tokens of the previous key; keys
+        for (const auto& element : *value.m_data.m_value.object)
-        // are often sorted, so most of the prefix is the same as for the
-        // previous key and need not be looked up again
-        std::vector<std::size_t> path;
-        const std::vector<string_t>* previous = nullptr;
-        // the number of the complete prefix (i.e., the key) of each key
-        std::vector<std::size_t> leaves;
-        leaves.reserve(keys.size());
-        for (const auto& tokens : keys)
         {
-            std::size_t common = 0;
+            json_pointer ptr(element.first);
-            if (previous != nullptr)
+            std::size_t id = 0;
+            for (auto& reference_token : ptr.reference_tokens)
             {
-                const std::size_t limit = (std::min)(tokens.size(), previous->size());
+                id = tree.add_child(id, std::move(reference_token));
-                while (common < limit && tokens[common] == (*previous)[common])
-                {
-                    ++common;
-                }
             }
-            path.resize(common);
-            std::size_t id = common == 0 ? 0 : path[common - 1];
-            for (std::size_t i = common; i < tokens.size(); ++i)
-            {
-                id = tree.add_child(id, tokens[i]);
-                path.push_back(id);
-            }
-            leaves.push_back(id);
-            previous = &tokens;
         }
 
         // iterate the JSON object values
-        std::vector<std::size_t> prefixes;
-        std::size_t key_index = 0;
         for (const auto& element : *value.m_data.m_value.object)
         {
             if (JSON_HEDLEY_UNLIKELY(!element.second.is_primitive()))
@@ -21994,21 +21737,11 @@ class json_pointer
                 JSON_THROW(detail::type_error::create(detail::exception_id::unflatten_value_not_primitive, "values in object must be primitive", &element.second));
             }
 
-            const auto& tokens = keys[key_index];
-            // number the prefixes of this key from its last one to the first
-            prefixes.resize(tokens.size());
-            for (std::size_t i = tokens.size(), id = leaves[key_index]; i > 0; --i)
-            {
-                id = tree.parent[id];
-                prefixes[i - 1] = id;
-            }
-            ++key_index;
-
             // Assign the value to the reference pointed to by JSON pointer. Note
             // that if the JSON pointer is "" (i.e., points to the whole value),
             // function get_and_create returns a reference to the result itself.
             // An assignment will then create a primitive value.
-            get_and_create(result, tokens, prefixes, tree) = element.second;
+            json_pointer(element.first).get_and_create(result, tree) = element.second;
         }
 
         return result;
@@ -22047,7 +21780,7 @@ class json_pointer
         = delete;
 #else
     {
-        return equals_string(rhs);
+        return *this == json_pointer(rhs);
     }
 #endif
 
@@ -22131,7 +21864,7 @@ inline bool operator==(const json_pointer<RefStringTypeLhs>& lhs,
     = delete;
 #else
 {
-    return lhs.equals_string(rhs);
+    return lhs == json_pointer<RefStringTypeLhs>(rhs);
 }
 #endif
 
@@ -22144,7 +21877,7 @@ inline bool operator==(const StringType& lhs,
     = delete;
 #else
 {
-    return rhs.equals_string(lhs);
+    return json_pointer<RefStringTypeRhs>(lhs) == rhs;
 }
 #endif
 
@@ -26141,7 +25874,10 @@ JSON_HEDLEY_ALWAYS_INLINE shortest_decimal to_shortest(std::uint64_t bits) noexc
     const uint128_parts p10 = pow10(-dec_exp - 1);
     const uint128_parts p = umul192_hi128(p10.high, p10.low, bin_sig << static_cast<unsigned>(shift));
     std::uint64_t integral = p.high >> static_cast<unsigned>(extra_shift);
-    const std::uint64_t fractional = (p.high << static_cast<unsigned>(64 - extra_shift)) | (p.low >> static_cast<unsigned>(extra_shift));
+    // (no casts in the shifts: MSVC 2015 warns C4554 on them despite the parentheses)
+    constexpr unsigned fractional_low_shift = static_cast<unsigned>(extra_shift);
+    constexpr unsigned fractional_high_shift = 64u - fractional_low_shift;
+    const std::uint64_t fractional = (p.high << fractional_high_shift) | (p.low >> fractional_low_shift);
     std::uint64_t digit = 0;
     bool round_up = false;
     bool round_down = false;
@@ -29425,17 +29161,6 @@ public:
         return {std::prev(this->end()), true};
     }
 
-    /// @brief add an element at the end without checking whether the key exists
-    /// @note The caller must guarantee that @a key is not yet contained, otherwise
-    ///       the container holds duplicate keys. This avoids the linear search of
-    ///       emplace() and operator[] when many keys known to be new are added.
-    template<class V, detail::enable_if_t<
-                 detail::is_constructible<T, V>::value, int> = 0>
-    void emplace_new_key(const key_type& key, V && t)
-    {
-        append(key, std::forward<V>(t));
-    }
-
     T& operator[](const key_type& key)
     {
         return emplace(key, T{}).first->second;
@@ -36188,18 +35913,24 @@ public:
         };
 
         // wrapper for "add" operation; add value at ptr
-        const auto operation_add = [&result](json_pointer & ptr, basic_json val)
+        const auto operation_add = [&result](json_pointer & ptr, const basic_json & val)
         {
             // adding to the root of the target document means replacing it
             if (ptr.empty())
             {
-                result = std::move(val);
+                result = val;
                 return;
             }
 
-            // get reference to the parent of the JSON pointer ptr; a missing
+            // make sure the top element of the pointer exists
-            // parent (or one of its ancestors) is reported by at()
+            json_pointer const top_pointer = ptr.top();
-            auto last_path = std::move(ptr.reference_tokens.back());
+            if (top_pointer != ptr)
+            {
+                result.at(top_pointer);
+            }
+
+            // get reference to the parent of the JSON pointer ptr
+            const auto last_path = ptr.back();
             ptr.pop_back();
             // parent must exist when performing patch add per RFC6902 specs
             basic_json& parent = result.at(ptr);
@@ -36210,7 +35941,7 @@ public:
                 case value_t::object:
                 {
                     // use operator[] to add value
-                    parent[std::move(last_path)] = std::move(val);
+                    parent[last_path] = val;
                     break;
                 }
 
@@ -36219,7 +35950,7 @@ public:
                     if (last_path == "-")
                     {
                         // special case: append to back
-                        parent.push_back(std::move(val));
+                        parent.push_back(val);
                     }
                     else
                     {
@@ -36231,7 +35962,7 @@ public:
                         }
 
                         // default case: insert add offset
-                        parent.insert(parent.begin() + static_cast<difference_type>(idx), std::move(val));
+                        parent.insert(parent.begin() + static_cast<difference_type>(idx), val);
                     }
                     break;
                 }
@@ -36254,8 +35985,7 @@ public:
         const auto operation_remove = [this, & result](json_pointer & ptr)
         {
             // get reference to the parent of the JSON pointer ptr
-            static_cast<void>(ptr.back()); // throws out_of_range.405 if ptr is the root
+            const auto last_path = ptr.back();
-            const auto last_path = std::move(ptr.reference_tokens.back());
             ptr.pop_back();
             basic_json& parent = result.at(ptr);
 
@@ -36355,8 +36085,8 @@ public:
             }
 
             // collect mandatory members
-            const string_t& op = *get_value("op", "op", true).m_data.m_value.string;
+            const auto op = get_value("op", "op", true).template get<string_t>();
-            const string_t& path = *get_value(op, "path", true).m_data.m_value.string;
+            const auto path = get_value(op, "path", true).template get<string_t>();
             json_pointer ptr(path);
 
             switch (get_op(op))
@@ -36382,7 +36112,7 @@ public:
 
                 case patch_operations::move:
                 {
-                    const string_t& from_path = *get_value("move", "from", true).m_data.m_value.string;
+                    const auto from_path = get_value("move", "from", true).template get<string_t>();
                     json_pointer from_ptr(from_path);
 
                     if (JSON_HEDLEY_UNLIKELY(is_proper_prefix(from_ptr, ptr)))
@@ -36391,28 +36121,29 @@ public:
                     }
 
                     // the "from" location must exist - use at()
-                    // a root "from" is rejected by operation_remove below, which must leave result intact
+                    basic_json const v = result.at(from_ptr);
-                    basic_json v = from_ptr.empty() ? basic_json(result) : std::move(result.at(from_ptr));
 
                     // The move operation is functionally identical to a
                     // "remove" operation on the "from" location, followed
                     // immediately by an "add" operation at the target
                     // location with the value that was just removed.
                     operation_remove(from_ptr);
-                    operation_add(ptr, std::move(v));
+                    operation_add(ptr, v);
                     break;
                 }
 
                 case patch_operations::copy:
                 {
-                    const string_t& from_path = *get_value("copy", "from", true).m_data.m_value.string;
+                    const auto from_path = get_value("copy", "from", true).template get<string_t>();
                     const json_pointer from_ptr(from_path);
 
+                    // the "from" location must exist - use at()
+                    basic_json const v = result.at(from_ptr);
+
                     // The copy is functionally identical to an "add"
                     // operation at the target location using the value
-                    // specified in the "from" member; the "from" location
+                    // specified in the "from" member.
-                    // must exist - use at()
+                    operation_add(ptr, v);
-                    operation_add(ptr, result.at(from_ptr));
                     break;
                 }
 

tests/src/unit-algorithms.cpp

@@ -9,7 +9,6 @@
 #include "doctest_compatibility.h"
 
 #include <algorithm>
-#include <numeric>
 #include <nlohmann/json.hpp>
 using nlohmann::json;
 

tests/src/unit-json_pointer.cpp

@@ -23,14 +23,8 @@ using nlohmann::json;
     using namespace nlohmann::literals; // NOLINT(google-build-using-namespace)
 #endif
 
-#include <cerrno>
-#include <cstdlib>
-#include <limits>
 #include <map>
-#include <random>
 #include <sstream>
-#include <string>
-#include <vector>
 
 TEST_CASE("JSON pointers")
 {
@@ -1077,242 +1071,3 @@ TEST_CASE("flatten of structured values")
               R"({"/z":"s","/a~1b/~0":1,"/a~1b/k":null,"/a/0":1,"/a/1/c":null,"/a/1/b":null,"/a/2/0/x~0~1/0":true,"/a/2/0/x~0~1/1":null,"/a/2/0/w":2})");
     }
 }
-
-TEST_CASE("flatten of ordered_json")
-{
-    using nlohmann::ordered_json;
-
-    SECTION("keeps the document order of the leaves")
-    {
-        const ordered_json j = ordered_json::parse(R"({
-            "z": 1, "a": {"y": [true, null, {}], "b": "x", "": []},
-            "m~n": 2.5, "o/p": {"k": {}}, "0": [[1], [2, 3]]
-        })");
-
-        const ordered_json flat = j.flatten();
-        std::vector<std::string> keys;
-        for (const auto& el : flat.items())
-        {
-            keys.push_back(el.key());
-        }
-        const std::vector<std::string> expected =
-        {
-            "/z", "/a/y/0", "/a/y/1", "/a/y/2", "/a/b", "/a/", "/m~0n", "/o~1p/k", "/0/0/0", "/0/1/0", "/0/1/1"
-        };
-        CHECK(keys == expected);
-        CHECK(flat.size() == expected.size());
-        CHECK(flat["/m~0n"] == 2.5);
-        CHECK(flat["/a/y/2"].is_null());
-    }
-
-    SECTION("round-trips and agrees with json")
-    {
-        ordered_json j;
-        for (int i = 0; i < 200; ++i)
-        {
-            j["k" + std::to_string(i)] = {{"v", i}, {"l", {i, i + 1, "s"}}};
-        }
-        const ordered_json flat = j.flatten();
-        CHECK(flat.size() == 800);
-        CHECK(flat.unflatten() == j);
-
-        // same entries as for a sorted object
-        const nlohmann::json plain = nlohmann::json::parse(j.dump());
-        CHECK(nlohmann::json::parse(flat.dump()) == plain.flatten());
-    }
-
-    SECTION("primitive and empty root")
-    {
-        CHECK(ordered_json(1).flatten() == ordered_json({{"", 1}}));
-        CHECK(ordered_json::array().flatten() == ordered_json({{"", nullptr}}));
-    }
-}
-namespace
-{
-// reference implementation of the array index rules (RFC 6901, Sect. 4) based on strtoull
-enum class index_class
-{
-    ok,
-    leading_zero,
-    not_a_number,
-    unresolved,
-    exceeds_size_type
-};
-
-index_class classify_index(const std::string& s, std::size_t& idx)
-{
-    if (s.size() > 1 && s[0] == '0')
-    {
-        return index_class::leading_zero;
-    }
-    if (!s.empty() && s != "-" && !(s[0] >= '0' && s[0] <= '9'))
-    {
-        return index_class::not_a_number;
-    }
-    char* end = nullptr;
-    errno = 0;
-    const unsigned long long res = std::strtoull(s.c_str(), &end, 10); // NOLINT(runtime/int)
-    if (end == s.c_str() || errno == ERANGE || static_cast<std::size_t>(end - s.c_str()) != s.size())
-    {
-        return index_class::unresolved;
-    }
-    if (res >= static_cast<unsigned long long>((std::numeric_limits<std::size_t>::max)())) // NOLINT(runtime/int)
-    {
-        return index_class::exceeds_size_type;
-    }
-    idx = static_cast<std::size_t>(res);
-    return index_class::ok;
-}
-
-// the observable behavior of json_pointer::at() and contains() for an array index token
-void check_index_token(const std::string& token)
-{
-    const json array = {10, 20, 30};
-    const json::json_pointer ptr("/" + token);
-
-    std::size_t idx = 0;
-    const auto cls = classify_index(token, idx);
-    const bool exists = cls == index_class::ok && idx < array.size();
-
-    CAPTURE(token)
-    CHECK(array.contains(ptr) == (exists && token != "-"));
-
-    if (token == "-")
-    {
-        CHECK_THROWS_AS(array.at(ptr), json::out_of_range&);
-        return;
-    }
-
-    switch (cls)
-    {
-        case index_class::leading_zero:
-            CHECK_THROWS_AS(array.at(ptr), json::parse_error&);
-            break;
-        case index_class::not_a_number:
-            CHECK_THROWS_AS(array.at(ptr), json::parse_error&);
-            break;
-        case index_class::unresolved:
-        case index_class::exceeds_size_type:
-            CHECK_THROWS_AS(array.at(ptr), json::out_of_range&);
-            break;
-        case index_class::ok:
-        default:
-            if (exists)
-            {
-                CHECK(array.at(ptr) == array[idx]);
-            }
-            else
-            {
-                CHECK_THROWS_AS(array.at(ptr), json::out_of_range&);
-            }
-            break;
-    }
-}
-} // namespace
-
-TEST_CASE("JSON pointer array index tokens match strtoull semantics")
-{
-    SECTION("boundary values")
-    {
-        const std::string max_digits = std::to_string((std::numeric_limits<std::size_t>::max)());
-        const std::vector<std::string> tokens =
-        {
-            "", "-", "0", "1", "2", "3", "00", "01", "007", "+1", "-1", " 1", "1 ", "1a", "a1", "0x1", "1e1", "1.0",
-            "999999999", "1000000000", "99999999999999999", "999999999999999999", "1000000000000000000",
-            "9999999999999999999", "18446744073709551614", max_digits, "18446744073709551616",
-            "99999999999999999999999", "000000000000000000000"
-        };
-        for (const auto& token : tokens)
-        {
-            check_index_token(token);
-        }
-    }
-
-    SECTION("random tokens")
-    {
-        std::mt19937 gen(42);
-        const std::string alphabet = "0123456789012345678901234567890123456789-+ ex";
-        for (int i = 0; i < 5000; ++i)
-        {
-            std::string token(static_cast<std::size_t>(gen() % 23), '0');
-            for (auto& c : token)
-            {
-                c = alphabet[gen() % alphabet.size()];
-            }
-            check_index_token(token);
-        }
-    }
-}
-
-TEST_CASE("JSON pointer operations on pointers with escaped tokens")
-{
-    const std::vector<std::string> strings =
-    {
-        "", "/", "//", "/a", "/a/b", "/a~1b", "/~0", "/~01", "/~10", "/a~0~1/b/", "/0/1/2", "/ ", "/a/", "/~1/~0"
-    };
-
-    for (const auto& str : strings)
-    {
-        CAPTURE(str)
-        const json::json_pointer ptr(str);
-        CHECK(ptr.to_string() == str);
-        CHECK(ptr / "x" / "y" / std::size_t{3} == json::json_pointer(str + "/x/y/3"));
-        CHECK(ptr.parent_pointer() == (str.empty() ? ptr : json::json_pointer(str.substr(0, str.rfind('/')))));
-
-        // comparison with a string, in place, and with every other pointer
-#if !defined(JSON_TEST_DEPRECATED_FUNCTIONS_DELETED)
-        for (const auto& other : strings)
-        {
-            CAPTURE(other)
-            CHECK((ptr == other) == (str == other));
-            CHECK((other == ptr) == (str == other));
-            CHECK((ptr != other) == (str != other));
-        }
-        CHECK_THROWS_AS(ptr == "x", json::parse_error&);
-        CHECK_THROWS_AS(ptr == "/~", json::parse_error&);
-        CHECK_THROWS_AS(ptr == "/b/~2", json::parse_error&);
-#endif
-    }
-}
-
-TEST_CASE("JSON pointer lookups")
-{
-    json j = {{"a", {{"b", {1, 2, 3}}}}, {"", 7}, {"~/", {{"x", nullptr}}}};
-    const json& cj = j;
-
-    CHECK(cj[json::json_pointer("/a/b/2")] == 3);
-    CHECK(cj.at(json::json_pointer("/a/b/1")) == 2);
-    CHECK(cj.at(json::json_pointer("/")) == 7);
-    CHECK(cj.contains(json::json_pointer("/~0~1/x")));
-    CHECK(!cj.contains(json::json_pointer("/a/c")));
-    CHECK(cj.value(json::json_pointer("/a/b/0"), 5) == 1);
-    CHECK(cj.value(json::json_pointer("/a/b/3"), 5) == 5);
-    CHECK(cj.value(json::json_pointer("/a/zz"), 5) == 5);
-
-    CHECK_THROWS_AS(cj.at(json::json_pointer("/a/c")), json::out_of_range&);
-    CHECK_THROWS_AS(cj.at(json::json_pointer("/a/b/3")), json::out_of_range&);
-
-    // non-const access reuses existing entries and creates missing ones
-    j[json::json_pointer("/a/b/1")] = 20;
-    j[json::json_pointer("/n/m")] = 1;
-    CHECK(j["a"]["b"] == json({1, 20, 3}));
-    CHECK(j["n"]["m"] == 1);
-}
-
-TEST_CASE("JSON patch with moves and copies")
-{
-    json doc = {{"a", {{"b", {1, 2, 3}}}}, {"c", {{"d", "x"}}}};
-
-    CHECK(doc.patch(json::parse(R"([{"op":"move","from":"/a/b","path":"/c/e"}])")) ==
-          json::parse(R"({"a":{},"c":{"d":"x","e":[1,2,3]}})"));
-    CHECK(doc.patch(json::parse(R"([{"op":"copy","from":"/a/b","path":"/c/e"}])")) ==
-          json::parse(R"({"a":{"b":[1,2,3]},"c":{"d":"x","e":[1,2,3]}})"));
-    CHECK(doc.patch(json::parse(R"([{"op":"move","from":"/a/b/0","path":"/a/b/2"}])")) ==
-          json::parse(R"({"a":{"b":[2,3,1]},"c":{"d":"x"}})"));
-
-    // a failing move leaves a copy-patched document untouched
-    CHECK_THROWS_AS(doc.patch(json::parse(R"([{"op":"move","from":"","path":""}])")), json::out_of_range&);
-    json inplace = doc;
-    CHECK_THROWS_AS(inplace.patch_inplace(json::parse(R"([{"op":"move","from":"","path":""}])")), json::out_of_range&);
-    CHECK(inplace == doc);
-}

tests/src/unit-to_chars.cpp

@@ -21,11 +21,8 @@ using nlohmann::detail::dtoa_impl::reinterpret_bits;
 #include <cstdint>
 #include <cstdio>
 #include <cstdlib>
-#include <iomanip>
 #include <limits>
-#include <locale>
 #include <random>
-#include <sstream>
 #include <string>
 #include <utility>
 #include <vector>
@@ -689,20 +686,13 @@ void check_shortest(double v)
     const std::string& digits = de.first;
     if (digits.size() > 1)
     {
-        // the decimals of one digit fewer next to the value
+        // the decimals of one digit fewer next to the value: v lies within
-        // (a stream rather than snprintf("%.*e"), whose output GCC cannot bound)
+        // half a unit of the last digit of text, so the closest ones are the
-        std::ostringstream shorter;
+        // truncated digits and their successor
-        shorter.imbue(std::locale::classic());
+        // (not a stream with std::setprecision(digits.size() - 2): the
-        shorter << std::scientific << std::setprecision(static_cast<int>(digits.size()) - 2) << v;
+        // standard library of MSVC 2017 ignores a precision of 0)
-        const auto near = digits_and_exponent(shorter.str());
+        const std::string m = digits.substr(0, digits.size() - 1);
-        // as an integer with digits.size() - 1 digits
+        const int e = de.second + 1;
-        std::string m = near.first;
-        int e = near.second;
-        while (m.size() < digits.size() - 1)
-        {
-            m += '0';
-            --e;
-        }
         const std::uint64_t mid = std::stoull(m);
         for (const std::uint64_t candidate :
                 {