Fix line endlings

1 files changed, 1083 insertions, 1083 deletions

diff --git a/indra/llcommon/llsdutil.cpp b/indra/llcommon/llsdutil.cpp
index 4dd47ad1ac..dd3a58c26d 100644
--- a/indra/llcommon/llsdutil.cpp
+++ b/indra/llcommon/llsdutil.cpp
@@ -1,1083 +1,1083 @@
-/**

- * @file llsdutil.cpp

- * @author Phoenix

- * @date 2006-05-24

- * @brief Implementation of classes, functions, etc, for using structured data.

- *

- * $LicenseInfo:firstyear=2006&license=viewerlgpl$

- * Second Life Viewer Source Code

- * Copyright (C) 2010, Linden Research, Inc.

- *

- * This library is free software; you can redistribute it and/or

- * modify it under the terms of the GNU Lesser General Public

- * License as published by the Free Software Foundation;

- * version 2.1 of the License only.

- *

- * This library is distributed in the hope that it will be useful,

- * but WITHOUT ANY WARRANTY; without even the implied warranty of

- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

- * Lesser General Public License for more details.

- *

- * You should have received a copy of the GNU Lesser General Public

- * License along with this library; if not, write to the Free Software

- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

- *

- * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA

- * $/LicenseInfo$

- */

-

-#include "linden_common.h"

-

-#include "llsdutil.h"

-#include <sstream>

-

-#if LL_WINDOWS

-#   define WIN32_LEAN_AND_MEAN

-#   include <winsock2.h>    // for htonl

-#elif LL_LINUX

-#   include <netinet/in.h>

-#elif LL_DARWIN

-#   include <arpa/inet.h>

-#endif

-

-#include "llsdserialize.h"

-#include "stringize.h"

-#include "is_approx_equal_fraction.h"

-

-#include <map>

-#include <set>

-#include <boost/range.hpp>

-

-// U32

-LLSD ll_sd_from_U32(const U32 val)

-{

-    std::vector<U8> v;

-    U32 net_order = htonl(val);

-

-    v.resize(4);

-    memcpy(&(v[0]), &net_order, 4);     /* Flawfinder: ignore */

-

-    return LLSD(v);

-}

-

-U32 ll_U32_from_sd(const LLSD& sd)

-{

-    U32 ret;

-    std::vector<U8> v = sd.asBinary();

-    if (v.size() < 4)

-    {

-        return 0;

-    }

-    memcpy(&ret, &(v[0]), 4);       /* Flawfinder: ignore */

-    ret = ntohl(ret);

-    return ret;

-}

-

-//U64

-LLSD ll_sd_from_U64(const U64 val)

-{

-    std::vector<U8> v;

-    U32 high, low;

-

-    high = (U32)(val >> 32);

-    low = (U32)val;

-    high = htonl(high);

-    low = htonl(low);

-

-    v.resize(8);

-    memcpy(&(v[0]), &high, 4);      /* Flawfinder: ignore */

-    memcpy(&(v[4]), &low, 4);       /* Flawfinder: ignore */

-

-    return LLSD(v);

-}

-

-U64 ll_U64_from_sd(const LLSD& sd)

-{

-    U32 high, low;

-    std::vector<U8> v = sd.asBinary();

-

-    if (v.size() < 8)

-    {

-        return 0;

-    }

-

-    memcpy(&high, &(v[0]), 4);      /* Flawfinder: ignore */

-    memcpy(&low, &(v[4]), 4);       /* Flawfinder: ignore */

-    high = ntohl(high);

-    low = ntohl(low);

-

-    return ((U64)high) << 32 | low;

-}

-

-// IP Address (stored in net order in a U32, so don't need swizzling)

-LLSD ll_sd_from_ipaddr(const U32 val)

-{

-    std::vector<U8> v;

-

-    v.resize(4);

-    memcpy(&(v[0]), &val, 4);       /* Flawfinder: ignore */

-

-    return LLSD(v);

-}

-

-U32 ll_ipaddr_from_sd(const LLSD& sd)

-{

-    U32 ret;

-    std::vector<U8> v = sd.asBinary();

-    if (v.size() < 4)

-    {

-        return 0;

-    }

-    memcpy(&ret, &(v[0]), 4);       /* Flawfinder: ignore */

-    return ret;

-}

-

-// Converts an LLSD binary to an LLSD string

-LLSD ll_string_from_binary(const LLSD& sd)

-{

-    std::vector<U8> value = sd.asBinary();

-    std::string str;

-    str.resize(value.size());

-    memcpy(&str[0], &value[0], value.size());

-    return str;

-}

-

-// Converts an LLSD string to an LLSD binary

-LLSD ll_binary_from_string(const LLSD& sd)

-{

-    std::vector<U8> binary_value;

-

-    std::string string_value = sd.asString();

-    for (const U8 c : string_value)

-    {

-        binary_value.push_back(c);

-    }

-

-    binary_value.push_back('\0');

-

-    return binary_value;

-}

-

-char* ll_print_sd(const LLSD& sd)

-{

-    const U32 bufferSize = 10 * 1024;

-    static char buffer[bufferSize];

-    std::ostringstream stream;

-    //stream.rdbuf()->pubsetbuf(buffer, bufferSize);

-    stream << LLSDOStreamer<LLSDXMLFormatter>(sd);

-    stream << std::ends;

-    strncpy(buffer, stream.str().c_str(), bufferSize);

-    buffer[bufferSize - 1] = '\0';

-    return buffer;

-}

-

-char* ll_pretty_print_sd_ptr(const LLSD* sd)

-{

-    if (sd)

-    {

-        return ll_pretty_print_sd(*sd);

-    }

-    return NULL;

-}

-

-char* ll_pretty_print_sd(const LLSD& sd)

-{

-    const U32 bufferSize = 100 * 1024;

-    static char buffer[bufferSize];

-    std::ostringstream stream;

-    //stream.rdbuf()->pubsetbuf(buffer, bufferSize);

-    stream << LLSDOStreamer<LLSDXMLFormatter>(sd, LLSDFormatter::OPTIONS_PRETTY);

-    stream << std::ends;

-    strncpy(buffer, stream.str().c_str(), bufferSize);

-    buffer[bufferSize - 1] = '\0';

-    return buffer;

-}

-

-std::string ll_stream_notation_sd(const LLSD& sd)

-{

-    std::ostringstream stream;

-    stream << LLSDOStreamer<LLSDNotationFormatter>(sd);

-    return stream.str();

-}

-

-

-//compares the structure of an LLSD to a template LLSD and stores the

-//"valid" values in a 3rd LLSD.  Default values pulled from the template

-//if the tested LLSD does not contain the key/value pair.

-//Excess values in the test LLSD are ignored in the resultant_llsd.

-//If the llsd to test has a specific key to a map and the values

-//are not of the same type, false is returned or if the LLSDs are not

-//of the same value.  Ordering of arrays matters

-//Otherwise, returns true

-bool compare_llsd_with_template(

-    const LLSD& llsd_to_test,

-    const LLSD& template_llsd,

-    LLSD& resultant_llsd)

-{

-    LL_PROFILE_ZONE_SCOPED

-

-    if (

-        llsd_to_test.isUndefined() &&

-        template_llsd.isDefined() )

-    {

-        resultant_llsd = template_llsd;

-        return true;

-    }

-    else if ( llsd_to_test.type() != template_llsd.type() )

-    {

-        resultant_llsd = LLSD();

-        return false;

-    }

-

-    if ( llsd_to_test.isArray() )

-    {

-        //they are both arrays

-        //we loop over all the items in the template

-        //verifying that the to_test has a subset (in the same order)

-        //any shortcoming in the testing_llsd are just taken

-        //to be the rest of the template

-        LLSD data;

-        LLSD::array_const_iterator test_iter;

-        LLSD::array_const_iterator template_iter;

-

-        resultant_llsd = LLSD::emptyArray();

-        test_iter = llsd_to_test.beginArray();

-

-        for (

-            template_iter = template_llsd.beginArray();

-            (template_iter != template_llsd.endArray() &&

-             test_iter != llsd_to_test.endArray());

-            ++template_iter)

-        {

-            if ( !compare_llsd_with_template(

-                     *test_iter,

-                     *template_iter,

-                     data) )

-            {

-                resultant_llsd = LLSD();

-                return false;

-            }

-            else

-            {

-                resultant_llsd.append(data);

-            }

-

-            ++test_iter;

-        }

-

-        //so either the test or the template ended

-        //we do another loop now to the end of the template

-        //grabbing the default values

-        for (;

-             template_iter != template_llsd.endArray();

-             ++template_iter)

-        {

-            resultant_llsd.append(*template_iter);

-        }

-    }

-    else if ( llsd_to_test.isMap() )

-    {

-        //now we loop over the keys of the two maps

-        //any excess is taken from the template

-        //excess is ignored in the test

-        LLSD value;

-        LLSD::map_const_iterator template_iter;

-

-        resultant_llsd = LLSD::emptyMap();

-        for (

-            template_iter = template_llsd.beginMap();

-            template_iter != template_llsd.endMap();

-            ++template_iter)

-        {

-            if ( llsd_to_test.has(template_iter->first) )

-            {

-                //the test LLSD has the same key

-                if ( !compare_llsd_with_template(

-                         llsd_to_test[template_iter->first],

-                         template_iter->second,

-                         value) )

-                {

-                    resultant_llsd = LLSD();

-                    return false;

-                }

-                else

-                {

-                    resultant_llsd[template_iter->first] = value;

-                }

-            }

-            else

-            {

-                //test llsd doesn't have it...take the

-                //template as default value

-                resultant_llsd[template_iter->first] =

-                    template_iter->second;

-            }

-        }

-    }

-    else

-    {

-        //of same type...take the test llsd's value

-        resultant_llsd = llsd_to_test;

-    }

-

-

-    return true;

-}

-

-// filter_llsd_with_template() is a direct clone (copy-n-paste) of

-// compare_llsd_with_template with the following differences:

-// (1) bool vs BOOL return types

-// (2) A map with the key value "*" is a special value and maps any key in the

-//     test llsd that doesn't have an explicitly matching key in the template.

-// (3) The element of an array with exactly one element is taken as a template

-//     for *all* the elements of the test array.  If the template array is of

-//     different size, compare_llsd_with_template() semantics apply.

-bool filter_llsd_with_template(

-    const LLSD & llsd_to_test,

-    const LLSD & template_llsd,

-    LLSD & resultant_llsd)

-{

-    LL_PROFILE_ZONE_SCOPED

-

-    if (llsd_to_test.isUndefined() && template_llsd.isDefined())

-    {

-        resultant_llsd = template_llsd;

-        return true;

-    }

-    else if (llsd_to_test.type() != template_llsd.type())

-    {

-        resultant_llsd = LLSD();

-        return false;

-    }

-

-    if (llsd_to_test.isArray())

-    {

-        //they are both arrays

-        //we loop over all the items in the template

-        //verifying that the to_test has a subset (in the same order)

-        //any shortcoming in the testing_llsd are just taken

-        //to be the rest of the template

-        LLSD data;

-        LLSD::array_const_iterator test_iter;

-        LLSD::array_const_iterator template_iter;

-

-        resultant_llsd = LLSD::emptyArray();

-        test_iter = llsd_to_test.beginArray();

-

-        if (1 == template_llsd.size())

-        {

-            // If the template has a single item, treat it as

-            // the template for *all* items in the test LLSD.

-            template_iter = template_llsd.beginArray();

-

-            for (; test_iter != llsd_to_test.endArray(); ++test_iter)

-            {

-                if (! filter_llsd_with_template(*test_iter, *template_iter, data))

-                {

-                    resultant_llsd = LLSD();

-                    return false;

-                }

-                else

-                {

-                    resultant_llsd.append(data);

-                }

-            }

-        }

-        else

-        {

-            // Traditional compare_llsd_with_template matching

-

-            for (template_iter = template_llsd.beginArray();

-                 template_iter != template_llsd.endArray() &&

-                     test_iter != llsd_to_test.endArray();

-                 ++template_iter, ++test_iter)

-            {

-                if (! filter_llsd_with_template(*test_iter, *template_iter, data))

-                {

-                    resultant_llsd = LLSD();

-                    return false;

-                }

-                else

-                {

-                    resultant_llsd.append(data);

-                }

-            }

-

-            //so either the test or the template ended

-            //we do another loop now to the end of the template

-            //grabbing the default values

-            for (;

-                 template_iter != template_llsd.endArray();

-                 ++template_iter)

-            {

-                resultant_llsd.append(*template_iter);

-            }

-        }

-    }

-    else if (llsd_to_test.isMap())

-    {

-        resultant_llsd = LLSD::emptyMap();

-

-        //now we loop over the keys of the two maps

-        //any excess is taken from the template

-        //excess is ignored in the test

-

-        // Special tag for wildcarded LLSD map key templates

-        const LLSD::String wildcard_tag("*");

-

-        const bool template_has_wildcard = template_llsd.has(wildcard_tag);

-        LLSD wildcard_value;

-        LLSD value;

-

-        const LLSD::map_const_iterator template_iter_end(template_llsd.endMap());

-        for (LLSD::map_const_iterator template_iter(template_llsd.beginMap());

-             template_iter_end != template_iter;

-             ++template_iter)

-        {

-            if (wildcard_tag == template_iter->first)

-            {

-                wildcard_value = template_iter->second;

-            }

-            else if (llsd_to_test.has(template_iter->first))

-            {

-                //the test LLSD has the same key

-                if (! filter_llsd_with_template(llsd_to_test[template_iter->first],

-                                                template_iter->second,

-                                                value))

-                {

-                    resultant_llsd = LLSD();

-                    return false;

-                }

-                else

-                {

-                    resultant_llsd[template_iter->first] = value;

-                }

-            }

-            else if (! template_has_wildcard)

-            {

-                // test llsd doesn't have it...take the

-                // template as default value

-                resultant_llsd[template_iter->first] = template_iter->second;

-            }

-        }

-        if (template_has_wildcard)

-        {

-            LLSD sub_value;

-            LLSD::map_const_iterator test_iter;

-

-            for (test_iter = llsd_to_test.beginMap();

-                 test_iter != llsd_to_test.endMap();

-                 ++test_iter)

-            {

-                if (resultant_llsd.has(test_iter->first))

-                {

-                    // Final value has test key, assume more specific

-                    // template matched and we shouldn't modify it again.

-                    continue;

-                }

-                else if (! filter_llsd_with_template(test_iter->second,

-                                                     wildcard_value,

-                                                     sub_value))

-                {

-                    // Test value doesn't match wildcarded template

-                    resultant_llsd = LLSD();

-                    return false;

-                }

-                else

-                {

-                    // Test value matches template, add the actuals.

-                    resultant_llsd[test_iter->first] = sub_value;

-                }

-            }

-        }

-    }

-    else

-    {

-        //of same type...take the test llsd's value

-        resultant_llsd = llsd_to_test;

-    }

-

-    return true;

-}

-

-/*****************************************************************************

-*   Helpers for llsd_matches()

-*****************************************************************************/

-// raw data used for LLSD::Type lookup

-struct Data

-{

-    LLSD::Type type;

-    const char* name;

-} typedata[] =

-{

-#define def(type) { LLSD::type, &#type[4] }

-    def(TypeUndefined),

-    def(TypeBoolean),

-    def(TypeInteger),

-    def(TypeReal),

-    def(TypeString),

-    def(TypeUUID),

-    def(TypeDate),

-    def(TypeURI),

-    def(TypeBinary),

-    def(TypeMap),

-    def(TypeArray)

-#undef  def

-};

-

-// LLSD::Type lookup class into which we load the above static data

-class TypeLookup

-{

-    typedef std::map<LLSD::Type, std::string> MapType;

-

-public:

-    TypeLookup()

-    {

-        LL_PROFILE_ZONE_SCOPED

-

-        for (const Data *di(boost::begin(typedata)), *dend(boost::end(typedata)); di != dend; ++di)

-        {

-            mMap[di->type] = di->name;

-        }

-    }

-

-    std::string lookup(LLSD::Type type) const

-    {

-        LL_PROFILE_ZONE_SCOPED

-

-        MapType::const_iterator found = mMap.find(type);

-        if (found != mMap.end())

-        {

-            return found->second;

-        }

-        return STRINGIZE("<unknown LLSD type " << type << ">");

-    }

-

-private:

-    MapType mMap;

-};

-

-// static instance of the lookup class

-static const TypeLookup sTypes;

-

-// describe a mismatch; phrasing may want tweaking

-const std::string op(" required instead of ");

-

-// llsd_matches() wants to identify specifically where in a complex prototype

-// structure the mismatch occurred. This entails passing a prefix string,

-// empty for the top-level call. If the prototype contains an array of maps,

-// and the mismatch occurs in the second map in a key 'foo', we want to

-// decorate the returned string with: "[1]['foo']: etc." On the other hand, we

-// want to omit the entire prefix -- including colon -- if the mismatch is at

-// top level. This helper accepts the (possibly empty) recursively-accumulated

-// prefix string, returning either empty or the original string with colon

-// appended.

-static std::string colon(const std::string& pfx)

-{

-    if (pfx.empty())

-        return pfx;

-    return pfx + ": ";

-}

-

-// param type for match_types

-typedef std::vector<LLSD::Type> TypeVector;

-

-// The scalar cases in llsd_matches() use this helper. In most cases, we can

-// accept not only the exact type specified in the prototype, but also other

-// types convertible to the expected type. That implies looping over an array

-// of such types. If the actual type doesn't match any of them, we want to

-// provide a list of acceptable conversions as well as the exact type, e.g.:

-// "Integer (or Boolean, Real, String) required instead of UUID". Both the

-// implementation and the calling logic are simplified by separating out the

-// expected type from the convertible types.

-static std::string match_types(LLSD::Type expect, // prototype.type()

-                               const TypeVector& accept, // types convertible to that type

-                               LLSD::Type actual,        // type we're checking

-                               const std::string& pfx)   // as for llsd_matches

-{

-    LL_PROFILE_ZONE_SCOPED

-

-    // Trivial case: if the actual type is exactly what we expect, we're good.

-    if (actual == expect)

-        return "";

-

-    // For the rest of the logic, build up a suitable error string as we go so

-    // we only have to make a single pass over the list of acceptable types.

-    // If we detect success along the way, we'll simply discard the partial

-    // error string.

-    std::ostringstream out;

-    out << colon(pfx) << sTypes.lookup(expect);

-

-    // If there are any convertible types, append that list.

-    if (! accept.empty())

-    {

-        out << " (";

-        const char* sep = "or ";

-        for (TypeVector::const_iterator ai(accept.begin()), aend(accept.end());

-             ai != aend; ++ai, sep = ", ")

-        {

-            // Don't forget to return success if we match any of those types...

-            if (actual == *ai)

-                return "";

-            out << sep << sTypes.lookup(*ai);

-        }

-        out << ')';

-    }

-    // If we got this far, it's because 'actual' was not one of the acceptable

-    // types, so we must return an error. 'out' already contains colon(pfx)

-    // and the formatted list of acceptable types, so just append the mismatch

-    // phrase and the actual type.

-    out << op << sTypes.lookup(actual);

-    return out.str();

-}

-

-// see docstring in .h file

-std::string llsd_matches(const LLSD& prototype, const LLSD& data, const std::string& pfx)

-{

-    LL_PROFILE_ZONE_SCOPED

-

-    // An undefined prototype means that any data is valid.

-    // An undefined slot in an array or map prototype means that any data

-    // may fill that slot.

-    if (prototype.isUndefined())

-        return "";

-    // A prototype array must match a data array with at least as many

-    // entries. Moreover, every prototype entry must match the

-    // corresponding data entry.

-    if (prototype.isArray())

-    {

-        if (! data.isArray())

-        {

-            return STRINGIZE(colon(pfx) << "Array" << op << sTypes.lookup(data.type()));

-        }

-        if (data.size() < prototype.size())

-        {

-            return STRINGIZE(colon(pfx) << "Array size " << prototype.size() << op

-                             << "Array size " << data.size());

-        }

-        for (LLSD::Integer i = 0; i < prototype.size(); ++i)

-        {

-            std::string match(llsd_matches(prototype[i], data[i], STRINGIZE('[' << i << ']')));

-            if (! match.empty())

-            {

-                return match;

-            }

-        }

-        return "";

-    }

-    // A prototype map must match a data map. Every key in the prototype

-    // must have a corresponding key in the data map; every value in the

-    // prototype must match the corresponding key's value in the data.

-    if (prototype.isMap())

-    {

-        if (! data.isMap())

-        {

-            return STRINGIZE(colon(pfx) << "Map" << op << sTypes.lookup(data.type()));

-        }

-        // If there are a number of keys missing from the data, it would be

-        // frustrating to a coder to discover them one at a time, with a big

-        // build each time. Enumerate all missing keys.

-        std::ostringstream out;

-        out << colon(pfx);

-        const char* init = "Map missing keys: ";

-        const char* sep = init;

-        for (LLSD::map_const_iterator mi = prototype.beginMap(); mi != prototype.endMap(); ++mi)

-        {

-            if (! data.has(mi->first))

-            {

-                out << sep << mi->first;

-                sep = ", ";

-            }

-        }

-        // So... are we missing any keys?

-        if (sep != init)

-        {

-            return out.str();

-        }

-        // Good, the data block contains all the keys required by the

-        // prototype. Now match the prototype entries.

-        for (LLSD::map_const_iterator mi2 = prototype.beginMap(); mi2 != prototype.endMap(); ++mi2)

-        {

-            std::string match(llsd_matches(mi2->second, data[mi2->first],

-                                           STRINGIZE("['" << mi2->first << "']")));

-            if (! match.empty())

-            {

-                return match;

-            }

-        }

-        return "";

-    }

-    // A String prototype can match String, Boolean, Integer, Real, UUID,

-    // Date and URI, because any of these can be converted to String.

-    if (prototype.isString())

-    {

-        static LLSD::Type accept[] =

-        {

-            LLSD::TypeBoolean,

-            LLSD::TypeInteger,

-            LLSD::TypeReal,

-            LLSD::TypeUUID,

-            LLSD::TypeDate,

-            LLSD::TypeURI

-        };

-        return match_types(prototype.type(),

-                           TypeVector(boost::begin(accept), boost::end(accept)),

-                           data.type(),

-                           pfx);

-    }

-    // Boolean, Integer, Real match each other or String. TBD: ensure that

-    // a String value is numeric.

-    if (prototype.isBoolean() || prototype.isInteger() || prototype.isReal())

-    {

-        static LLSD::Type all[] =

-        {

-            LLSD::TypeBoolean,

-            LLSD::TypeInteger,

-            LLSD::TypeReal,

-            LLSD::TypeString

-        };

-        // Funny business: shuffle the set of acceptable types to include all

-        // but the prototype's type. Get the acceptable types in a set.

-        std::set<LLSD::Type> rest(boost::begin(all), boost::end(all));

-        // Remove the prototype's type because we pass that separately.

-        rest.erase(prototype.type());

-        return match_types(prototype.type(),

-                           TypeVector(rest.begin(), rest.end()),

-                           data.type(),

-                           pfx);

-    }

-    // UUID, Date and URI match themselves or String.

-    if (prototype.isUUID() || prototype.isDate() || prototype.isURI())

-    {

-        static LLSD::Type accept[] =

-        {

-            LLSD::TypeString

-        };

-        return match_types(prototype.type(),

-                           TypeVector(boost::begin(accept), boost::end(accept)),

-                           data.type(),

-                           pfx);

-    }

-    // We don't yet know the conversion semantics associated with any new LLSD

-    // data type that might be added, so until we've been extended to handle

-    // them, assume it's strict: the new type matches only itself. (This is

-    // true of Binary, which is why we don't handle that case separately.) Too

-    // bad LLSD doesn't define isConvertible(Type to, Type from).

-    return match_types(prototype.type(), TypeVector(), data.type(), pfx);

-}

-

-bool llsd_equals(const LLSD& lhs, const LLSD& rhs, int bits)

-{

-    LL_PROFILE_ZONE_SCOPED

-

-    // We're comparing strict equality of LLSD representation rather than

-    // performing any conversions. So if the types aren't equal, the LLSD

-    // values aren't equal.

-    if (lhs.type() != rhs.type())

-    {

-        return false;

-    }

-

-    // Here we know both types are equal. Now compare values.

-    switch (lhs.type())

-    {

-    case LLSD::TypeUndefined:

-        // Both are TypeUndefined. There's nothing more to know.

-        return true;

-

-    case LLSD::TypeReal:

-        // This is where the 'bits' argument comes in handy. If passed

-        // explicitly, it means to use is_approx_equal_fraction() to compare.

-        if (bits >= 0)

-        {

-            return is_approx_equal_fraction(lhs.asReal(), rhs.asReal(), bits);

-        }

-        // Otherwise we compare bit representations, and the usual caveats

-        // about comparing floating-point numbers apply. Omitting 'bits' when

-        // comparing Real values is only useful when we expect identical bit

-        // representation for a given Real value, e.g. for integer-valued

-        // Reals.

-        return (lhs.asReal() == rhs.asReal());

-

-#define COMPARE_SCALAR(type)                                    \

-    case LLSD::Type##type:                                      \

-        /* LLSD::URI has operator!=() but not operator==() */   \

-        /* rely on the optimizer for all others */              \

-        return (! (lhs.as##type() != rhs.as##type()))

-

-    COMPARE_SCALAR(Boolean);

-    COMPARE_SCALAR(Integer);

-    COMPARE_SCALAR(String);

-    COMPARE_SCALAR(UUID);

-    COMPARE_SCALAR(Date);

-    COMPARE_SCALAR(URI);

-    COMPARE_SCALAR(Binary);

-

-#undef COMPARE_SCALAR

-

-    case LLSD::TypeArray:

-    {

-        LLSD::array_const_iterator

-            lai(lhs.beginArray()), laend(lhs.endArray()),

-            rai(rhs.beginArray()), raend(rhs.endArray());

-        // Compare array elements, walking the two arrays in parallel.

-        for ( ; lai != laend && rai != raend; ++lai, ++rai)

-        {

-            // If any one array element is unequal, the arrays are unequal.

-            if (! llsd_equals(*lai, *rai, bits))

-                return false;

-        }

-        // Here we've reached the end of one or the other array. They're equal

-        // only if they're BOTH at end: that is, if they have equal length too.

-        return (lai == laend && rai == raend);

-    }

-

-    case LLSD::TypeMap:

-    {

-        // Build a set of all rhs keys.

-        std::set<LLSD::String> rhskeys;

-        for (LLSD::map_const_iterator rmi(rhs.beginMap()), rmend(rhs.endMap());

-             rmi != rmend; ++rmi)

-        {

-            rhskeys.insert(rmi->first);

-        }

-        // Now walk all the lhs keys.

-        for (LLSD::map_const_iterator lmi(lhs.beginMap()), lmend(lhs.endMap());

-             lmi != lmend; ++lmi)

-        {

-            // Try to erase this lhs key from the set of rhs keys. If rhs has

-            // no such key, the maps are unequal. erase(key) returns count of

-            // items erased.

-            if (rhskeys.erase(lmi->first) != 1)

-                return false;

-            // Both maps have the current key. Compare values.

-            if (! llsd_equals(lmi->second, rhs[lmi->first], bits))

-                return false;

-        }

-        // We've now established that all the lhs keys have equal values in

-        // both maps. The maps are equal unless rhs contains a superset of

-        // those keys.

-        return rhskeys.empty();

-    }

-

-    default:

-        // We expect that every possible type() value is specifically handled

-        // above. Failing to extend this switch to support a new LLSD type is

-        // an error that must be brought to the coder's attention.

-        LL_ERRS("llsd_equals") << "llsd_equals(" << lhs << ", " << rhs << ", " << bits << "): "

-            "unknown type " << lhs.type() << LL_ENDL;

-        return false;               // pacify the compiler

-    }

-}

-

-/*****************************************************************************

-*   llsd::drill()

-*****************************************************************************/

-namespace llsd

-{

-

-LLSD& drill_ref(LLSD& blob, const LLSD& rawPath)

-{

-    LL_PROFILE_ZONE_SCOPED

-

-    // Treat rawPath uniformly as an array. If it's not already an array,

-    // store it as the only entry in one. (But let's say Undefined means an

-    // empty array.)

-    LLSD path;

-    if (rawPath.isArray() || rawPath.isUndefined())

-    {

-        path = rawPath;

-    }

-    else

-    {

-        path.append(rawPath);

-    }

-

-    // Need to indicate a current destination -- but that current destination

-    // must change as we step through the path array. Where normally we'd use

-    // an LLSD& to capture a subscripted LLSD lvalue, this time we must

-    // instead use a pointer -- since it must be reassigned.

-    // Start by pointing to the input blob exactly as is.

-    LLSD* located{&blob};

-

-    // Extract the element of interest by walking path. Use an explicit index

-    // so that, in case of a bogus type in path, we can identify the specific

-    // path entry that's bad.

-    for (LLSD::Integer i = 0; i < path.size(); ++i)

-    {

-        LL_PROFILE_ZONE_NUM( i )

-

-        const LLSD& key{path[i]};

-        if (key.isString())

-        {

-            // a string path element is a map key

-            located = &((*located)[key.asString()]);

-        }

-        else if (key.isInteger())

-        {

-            // an integer path element is an array index

-            located = &((*located)[key.asInteger()]);

-        }

-        else

-        {

-            // What do we do with Real or Array or Map or ...?

-            // As it's a coder error -- not a user error -- rub the coder's

-            // face in it so it gets fixed.

-            LL_ERRS("llsdutil") << "drill(" << blob << ", " << rawPath

-                                << "): path[" << i << "] bad type "

-                                << sTypes.lookup(key.type()) << LL_ENDL;

-        }

-    }

-

-    // dereference the pointer to return a reference to the element we found

-    return *located;

-}

-

-LLSD drill(const LLSD& blob, const LLSD& path)

-{

-    LL_PROFILE_ZONE_SCOPED

-

-    // drill_ref() does exactly what we want. Temporarily cast away

-    // const-ness and use that.

-    return drill_ref(const_cast<LLSD&>(blob), path);

-}

-

-} // namespace llsd

-

-// Construct a deep partial clone of of an LLSD object. primitive types share

-// references, however maps, arrays and binary objects are duplicated. An optional

-// filter may be include to exclude/include keys in a map.

-LLSD llsd_clone(LLSD value, LLSD filter)

-{

-    LL_PROFILE_ZONE_SCOPED

-

-    LLSD clone;

-    bool has_filter(filter.isMap());

-

-    switch (value.type())

-    {

-    case LLSD::TypeMap:

-        clone = LLSD::emptyMap();

-        for (LLSD::map_const_iterator itm = value.beginMap(); itm != value.endMap(); ++itm)

-        {

-            if (has_filter)

-            {

-                if (filter.has((*itm).first))

-                {

-                    if (!filter[(*itm).first].asBoolean())

-                        continue;

-                }

-                else if (filter.has("*"))

-                {

-                    if (!filter["*"].asBoolean())

-                        continue;

-                }

-                else

-                {

-                    continue;

-                }

-            }

-            clone[(*itm).first] = llsd_clone((*itm).second, filter);

-        }

-        break;

-    case LLSD::TypeArray:

-        clone = LLSD::emptyArray();

-        for (LLSD::array_const_iterator ita = value.beginArray(); ita != value.endArray(); ++ita)

-        {

-            clone.append(llsd_clone(*ita, filter));

-        }

-        break;

-

-    case LLSD::TypeBinary:

-    {

-        LLSD::Binary bin(value.asBinary().begin(), value.asBinary().end());

-        clone = LLSD::Binary(bin);

-        break;

-    }

-    default:

-        clone = value;

-    }

-

-    return clone;

-}

-

-LLSD llsd_shallow(LLSD value, LLSD filter)

-{

-    LLSD shallow;

-    bool has_filter(filter.isMap());

-

-    if (value.isMap())

-    {

-        shallow = LLSD::emptyMap();

-        for (LLSD::map_const_iterator itm = value.beginMap(); itm != value.endMap(); ++itm)

-        {

-            if (has_filter)

-            {

-                if (filter.has((*itm).first))

-                {

-                    if (!filter[(*itm).first].asBoolean())

-                        continue;

-                }

-                else if (filter.has("*"))

-                {

-                    if (!filter["*"].asBoolean())

-                        continue;

-                }

-                else

-                {

-                    continue;

-                }

-            }

-            shallow[(*itm).first] = (*itm).second;

-        }

-    }

-    else if (value.isArray())

-    {

-        shallow = LLSD::emptyArray();

-        for (LLSD::array_const_iterator ita = value.beginArray(); ita != value.endArray(); ++ita)

-        {

-            shallow.append(*ita);

-        }

-    }

-    else

-    {

-        return value;

-    }

-

-    return shallow;

-}

-

-LLSD LL::apply_llsd_fix(size_t arity, const LLSD& args)

-{

-    // LLSD supports a number of types, two of which are aggregates: Map and

-    // Array. We don't try to support Map: supporting Map would seem to

-    // promise that we could somehow match the string key to 'func's parameter

-    // names. Uh sorry, maybe in some future version of C++ with reflection.

-    if (args.isMap())

-    {

-        LLTHROW(LL::apply_error("LL::apply(function, Map LLSD) unsupported"));

-    }

-    // We expect an LLSD array, but what the heck, treat isUndefined() as a

-    // zero-length array for calling a nullary 'func'.

-    if (args.isUndefined() || args.isArray())

-    {

-        // this works because LLSD().size() == 0

-        if (args.size() != arity)

-        {

-            LLTHROW(LL::apply_error(stringize("LL::apply(function(", arity, " args), ",

-                                              args.size(), "-entry LLSD array)")));

-        }

-        return args;

-    }

-

-    // args is one of the scalar types

-    // scalar_LLSD.size() == 0, so don't test that here.

-    // You can pass a scalar LLSD only to a unary 'func'.

-    if (arity != 1)

-    {

-        LLTHROW(LL::apply_error(stringize("LL::apply(function(", arity, " args), "

-                                          "LLSD ", LLSD::typeString(args.type()), ")")));

-    }

-    // make an array of it

-    return llsd::array(args);

-}

+/**
+ * @file llsdutil.cpp
+ * @author Phoenix
+ * @date 2006-05-24
+ * @brief Implementation of classes, functions, etc, for using structured data.
+ *
+ * $LicenseInfo:firstyear=2006&license=viewerlgpl$
+ * Second Life Viewer Source Code
+ * Copyright (C) 2010, Linden Research, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation;
+ * version 2.1 of the License only.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
+ * $/LicenseInfo$
+ */
+
+#include "linden_common.h"
+
+#include "llsdutil.h"
+#include <sstream>
+
+#if LL_WINDOWS
+#   define WIN32_LEAN_AND_MEAN
+#   include <winsock2.h>    // for htonl
+#elif LL_LINUX
+#   include <netinet/in.h>
+#elif LL_DARWIN
+#   include <arpa/inet.h>
+#endif
+
+#include "llsdserialize.h"
+#include "stringize.h"
+#include "is_approx_equal_fraction.h"
+
+#include <map>
+#include <set>
+#include <boost/range.hpp>
+
+// U32
+LLSD ll_sd_from_U32(const U32 val)
+{
+    std::vector<U8> v;
+    U32 net_order = htonl(val);
+
+    v.resize(4);
+    memcpy(&(v[0]), &net_order, 4);     /* Flawfinder: ignore */
+
+    return LLSD(v);
+}
+
+U32 ll_U32_from_sd(const LLSD& sd)
+{
+    U32 ret;
+    std::vector<U8> v = sd.asBinary();
+    if (v.size() < 4)
+    {
+        return 0;
+    }
+    memcpy(&ret, &(v[0]), 4);       /* Flawfinder: ignore */
+    ret = ntohl(ret);
+    return ret;
+}
+
+//U64
+LLSD ll_sd_from_U64(const U64 val)
+{
+    std::vector<U8> v;
+    U32 high, low;
+
+    high = (U32)(val >> 32);
+    low = (U32)val;
+    high = htonl(high);
+    low = htonl(low);
+
+    v.resize(8);
+    memcpy(&(v[0]), &high, 4);      /* Flawfinder: ignore */
+    memcpy(&(v[4]), &low, 4);       /* Flawfinder: ignore */
+
+    return LLSD(v);
+}
+
+U64 ll_U64_from_sd(const LLSD& sd)
+{
+    U32 high, low;
+    std::vector<U8> v = sd.asBinary();
+
+    if (v.size() < 8)
+    {
+        return 0;
+    }
+
+    memcpy(&high, &(v[0]), 4);      /* Flawfinder: ignore */
+    memcpy(&low, &(v[4]), 4);       /* Flawfinder: ignore */
+    high = ntohl(high);
+    low = ntohl(low);
+
+    return ((U64)high) << 32 | low;
+}
+
+// IP Address (stored in net order in a U32, so don't need swizzling)
+LLSD ll_sd_from_ipaddr(const U32 val)
+{
+    std::vector<U8> v;
+
+    v.resize(4);
+    memcpy(&(v[0]), &val, 4);       /* Flawfinder: ignore */
+
+    return LLSD(v);
+}
+
+U32 ll_ipaddr_from_sd(const LLSD& sd)
+{
+    U32 ret;
+    std::vector<U8> v = sd.asBinary();
+    if (v.size() < 4)
+    {
+        return 0;
+    }
+    memcpy(&ret, &(v[0]), 4);       /* Flawfinder: ignore */
+    return ret;
+}
+
+// Converts an LLSD binary to an LLSD string
+LLSD ll_string_from_binary(const LLSD& sd)
+{
+    std::vector<U8> value = sd.asBinary();
+    std::string str;
+    str.resize(value.size());
+    memcpy(&str[0], &value[0], value.size());
+    return str;
+}
+
+// Converts an LLSD string to an LLSD binary
+LLSD ll_binary_from_string(const LLSD& sd)
+{
+    std::vector<U8> binary_value;
+
+    std::string string_value = sd.asString();
+    for (const U8 c : string_value)
+    {
+        binary_value.push_back(c);
+    }
+
+    binary_value.push_back('\0');
+
+    return binary_value;
+}
+
+char* ll_print_sd(const LLSD& sd)
+{
+    const U32 bufferSize = 10 * 1024;
+    static char buffer[bufferSize];
+    std::ostringstream stream;
+    //stream.rdbuf()->pubsetbuf(buffer, bufferSize);
+    stream << LLSDOStreamer<LLSDXMLFormatter>(sd);
+    stream << std::ends;
+    strncpy(buffer, stream.str().c_str(), bufferSize);
+    buffer[bufferSize - 1] = '\0';
+    return buffer;
+}
+
+char* ll_pretty_print_sd_ptr(const LLSD* sd)
+{
+    if (sd)
+    {
+        return ll_pretty_print_sd(*sd);
+    }
+    return NULL;
+}
+
+char* ll_pretty_print_sd(const LLSD& sd)
+{
+    const U32 bufferSize = 100 * 1024;
+    static char buffer[bufferSize];
+    std::ostringstream stream;
+    //stream.rdbuf()->pubsetbuf(buffer, bufferSize);
+    stream << LLSDOStreamer<LLSDXMLFormatter>(sd, LLSDFormatter::OPTIONS_PRETTY);
+    stream << std::ends;
+    strncpy(buffer, stream.str().c_str(), bufferSize);
+    buffer[bufferSize - 1] = '\0';
+    return buffer;
+}
+
+std::string ll_stream_notation_sd(const LLSD& sd)
+{
+    std::ostringstream stream;
+    stream << LLSDOStreamer<LLSDNotationFormatter>(sd);
+    return stream.str();
+}
+
+
+//compares the structure of an LLSD to a template LLSD and stores the
+//"valid" values in a 3rd LLSD.  Default values pulled from the template
+//if the tested LLSD does not contain the key/value pair.
+//Excess values in the test LLSD are ignored in the resultant_llsd.
+//If the llsd to test has a specific key to a map and the values
+//are not of the same type, false is returned or if the LLSDs are not
+//of the same value.  Ordering of arrays matters
+//Otherwise, returns true
+bool compare_llsd_with_template(
+    const LLSD& llsd_to_test,
+    const LLSD& template_llsd,
+    LLSD& resultant_llsd)
+{
+    LL_PROFILE_ZONE_SCOPED
+
+    if (
+        llsd_to_test.isUndefined() &&
+        template_llsd.isDefined() )
+    {
+        resultant_llsd = template_llsd;
+        return true;
+    }
+    else if ( llsd_to_test.type() != template_llsd.type() )
+    {
+        resultant_llsd = LLSD();
+        return false;
+    }
+
+    if ( llsd_to_test.isArray() )
+    {
+        //they are both arrays
+        //we loop over all the items in the template
+        //verifying that the to_test has a subset (in the same order)
+        //any shortcoming in the testing_llsd are just taken
+        //to be the rest of the template
+        LLSD data;
+        LLSD::array_const_iterator test_iter;
+        LLSD::array_const_iterator template_iter;
+
+        resultant_llsd = LLSD::emptyArray();
+        test_iter = llsd_to_test.beginArray();
+
+        for (
+            template_iter = template_llsd.beginArray();
+            (template_iter != template_llsd.endArray() &&
+             test_iter != llsd_to_test.endArray());
+            ++template_iter)
+        {
+            if ( !compare_llsd_with_template(
+                     *test_iter,
+                     *template_iter,
+                     data) )
+            {
+                resultant_llsd = LLSD();
+                return false;
+            }
+            else
+            {
+                resultant_llsd.append(data);
+            }
+
+            ++test_iter;
+        }
+
+        //so either the test or the template ended
+        //we do another loop now to the end of the template
+        //grabbing the default values
+        for (;
+             template_iter != template_llsd.endArray();
+             ++template_iter)
+        {
+            resultant_llsd.append(*template_iter);
+        }
+    }
+    else if ( llsd_to_test.isMap() )
+    {
+        //now we loop over the keys of the two maps
+        //any excess is taken from the template
+        //excess is ignored in the test
+        LLSD value;
+        LLSD::map_const_iterator template_iter;
+
+        resultant_llsd = LLSD::emptyMap();
+        for (
+            template_iter = template_llsd.beginMap();
+            template_iter != template_llsd.endMap();
+            ++template_iter)
+        {
+            if ( llsd_to_test.has(template_iter->first) )
+            {
+                //the test LLSD has the same key
+                if ( !compare_llsd_with_template(
+                         llsd_to_test[template_iter->first],
+                         template_iter->second,
+                         value) )
+                {
+                    resultant_llsd = LLSD();
+                    return false;
+                }
+                else
+                {
+                    resultant_llsd[template_iter->first] = value;
+                }
+            }
+            else
+            {
+                //test llsd doesn't have it...take the
+                //template as default value
+                resultant_llsd[template_iter->first] =
+                    template_iter->second;
+            }
+        }
+    }
+    else
+    {
+        //of same type...take the test llsd's value
+        resultant_llsd = llsd_to_test;
+    }
+
+
+    return true;
+}
+
+// filter_llsd_with_template() is a direct clone (copy-n-paste) of
+// compare_llsd_with_template with the following differences:
+// (1) bool vs BOOL return types
+// (2) A map with the key value "*" is a special value and maps any key in the
+//     test llsd that doesn't have an explicitly matching key in the template.
+// (3) The element of an array with exactly one element is taken as a template
+//     for *all* the elements of the test array.  If the template array is of
+//     different size, compare_llsd_with_template() semantics apply.
+bool filter_llsd_with_template(
+    const LLSD & llsd_to_test,
+    const LLSD & template_llsd,
+    LLSD & resultant_llsd)
+{
+    LL_PROFILE_ZONE_SCOPED
+
+    if (llsd_to_test.isUndefined() && template_llsd.isDefined())
+    {
+        resultant_llsd = template_llsd;
+        return true;
+    }
+    else if (llsd_to_test.type() != template_llsd.type())
+    {
+        resultant_llsd = LLSD();
+        return false;
+    }
+
+    if (llsd_to_test.isArray())
+    {
+        //they are both arrays
+        //we loop over all the items in the template
+        //verifying that the to_test has a subset (in the same order)
+        //any shortcoming in the testing_llsd are just taken
+        //to be the rest of the template
+        LLSD data;
+        LLSD::array_const_iterator test_iter;
+        LLSD::array_const_iterator template_iter;
+
+        resultant_llsd = LLSD::emptyArray();
+        test_iter = llsd_to_test.beginArray();
+
+        if (1 == template_llsd.size())
+        {
+            // If the template has a single item, treat it as
+            // the template for *all* items in the test LLSD.
+            template_iter = template_llsd.beginArray();
+
+            for (; test_iter != llsd_to_test.endArray(); ++test_iter)
+            {
+                if (! filter_llsd_with_template(*test_iter, *template_iter, data))
+                {
+                    resultant_llsd = LLSD();
+                    return false;
+                }
+                else
+                {
+                    resultant_llsd.append(data);
+                }
+            }
+        }
+        else
+        {
+            // Traditional compare_llsd_with_template matching
+
+            for (template_iter = template_llsd.beginArray();
+                 template_iter != template_llsd.endArray() &&
+                     test_iter != llsd_to_test.endArray();
+                 ++template_iter, ++test_iter)
+            {
+                if (! filter_llsd_with_template(*test_iter, *template_iter, data))
+                {
+                    resultant_llsd = LLSD();
+                    return false;
+                }
+                else
+                {
+                    resultant_llsd.append(data);
+                }
+            }
+
+            //so either the test or the template ended
+            //we do another loop now to the end of the template
+            //grabbing the default values
+            for (;
+                 template_iter != template_llsd.endArray();
+                 ++template_iter)
+            {
+                resultant_llsd.append(*template_iter);
+            }
+        }
+    }
+    else if (llsd_to_test.isMap())
+    {
+        resultant_llsd = LLSD::emptyMap();
+
+        //now we loop over the keys of the two maps
+        //any excess is taken from the template
+        //excess is ignored in the test
+
+        // Special tag for wildcarded LLSD map key templates
+        const LLSD::String wildcard_tag("*");
+
+        const bool template_has_wildcard = template_llsd.has(wildcard_tag);
+        LLSD wildcard_value;
+        LLSD value;
+
+        const LLSD::map_const_iterator template_iter_end(template_llsd.endMap());
+        for (LLSD::map_const_iterator template_iter(template_llsd.beginMap());
+             template_iter_end != template_iter;
+             ++template_iter)
+        {
+            if (wildcard_tag == template_iter->first)
+            {
+                wildcard_value = template_iter->second;
+            }
+            else if (llsd_to_test.has(template_iter->first))
+            {
+                //the test LLSD has the same key
+                if (! filter_llsd_with_template(llsd_to_test[template_iter->first],
+                                                template_iter->second,
+                                                value))
+                {
+                    resultant_llsd = LLSD();
+                    return false;
+                }
+                else
+                {
+                    resultant_llsd[template_iter->first] = value;
+                }
+            }
+            else if (! template_has_wildcard)
+            {
+                // test llsd doesn't have it...take the
+                // template as default value
+                resultant_llsd[template_iter->first] = template_iter->second;
+            }
+        }
+        if (template_has_wildcard)
+        {
+            LLSD sub_value;
+            LLSD::map_const_iterator test_iter;
+
+            for (test_iter = llsd_to_test.beginMap();
+                 test_iter != llsd_to_test.endMap();
+                 ++test_iter)
+            {
+                if (resultant_llsd.has(test_iter->first))
+                {
+                    // Final value has test key, assume more specific
+                    // template matched and we shouldn't modify it again.
+                    continue;
+                }
+                else if (! filter_llsd_with_template(test_iter->second,
+                                                     wildcard_value,
+                                                     sub_value))
+                {
+                    // Test value doesn't match wildcarded template
+                    resultant_llsd = LLSD();
+                    return false;
+                }
+                else
+                {
+                    // Test value matches template, add the actuals.
+                    resultant_llsd[test_iter->first] = sub_value;
+                }
+            }
+        }
+    }
+    else
+    {
+        //of same type...take the test llsd's value
+        resultant_llsd = llsd_to_test;
+    }
+
+    return true;
+}
+
+/*****************************************************************************
+*   Helpers for llsd_matches()
+*****************************************************************************/
+// raw data used for LLSD::Type lookup
+struct Data
+{
+    LLSD::Type type;
+    const char* name;
+} typedata[] =
+{
+#define def(type) { LLSD::type, &#type[4] }
+    def(TypeUndefined),
+    def(TypeBoolean),
+    def(TypeInteger),
+    def(TypeReal),
+    def(TypeString),
+    def(TypeUUID),
+    def(TypeDate),
+    def(TypeURI),
+    def(TypeBinary),
+    def(TypeMap),
+    def(TypeArray)
+#undef  def
+};
+
+// LLSD::Type lookup class into which we load the above static data
+class TypeLookup
+{
+    typedef std::map<LLSD::Type, std::string> MapType;
+
+public:
+    TypeLookup()
+    {
+        LL_PROFILE_ZONE_SCOPED
+
+        for (const Data *di(boost::begin(typedata)), *dend(boost::end(typedata)); di != dend; ++di)
+        {
+            mMap[di->type] = di->name;
+        }
+    }
+
+    std::string lookup(LLSD::Type type) const
+    {
+        LL_PROFILE_ZONE_SCOPED
+
+        MapType::const_iterator found = mMap.find(type);
+        if (found != mMap.end())
+        {
+            return found->second;
+        }
+        return STRINGIZE("<unknown LLSD type " << type << ">");
+    }
+
+private:
+    MapType mMap;
+};
+
+// static instance of the lookup class
+static const TypeLookup sTypes;
+
+// describe a mismatch; phrasing may want tweaking
+const std::string op(" required instead of ");
+
+// llsd_matches() wants to identify specifically where in a complex prototype
+// structure the mismatch occurred. This entails passing a prefix string,
+// empty for the top-level call. If the prototype contains an array of maps,
+// and the mismatch occurs in the second map in a key 'foo', we want to
+// decorate the returned string with: "[1]['foo']: etc." On the other hand, we
+// want to omit the entire prefix -- including colon -- if the mismatch is at
+// top level. This helper accepts the (possibly empty) recursively-accumulated
+// prefix string, returning either empty or the original string with colon
+// appended.
+static std::string colon(const std::string& pfx)
+{
+    if (pfx.empty())
+        return pfx;
+    return pfx + ": ";
+}
+
+// param type for match_types
+typedef std::vector<LLSD::Type> TypeVector;
+
+// The scalar cases in llsd_matches() use this helper. In most cases, we can
+// accept not only the exact type specified in the prototype, but also other
+// types convertible to the expected type. That implies looping over an array
+// of such types. If the actual type doesn't match any of them, we want to
+// provide a list of acceptable conversions as well as the exact type, e.g.:
+// "Integer (or Boolean, Real, String) required instead of UUID". Both the
+// implementation and the calling logic are simplified by separating out the
+// expected type from the convertible types.
+static std::string match_types(LLSD::Type expect, // prototype.type()
+                               const TypeVector& accept, // types convertible to that type
+                               LLSD::Type actual,        // type we're checking
+                               const std::string& pfx)   // as for llsd_matches
+{
+    LL_PROFILE_ZONE_SCOPED
+
+    // Trivial case: if the actual type is exactly what we expect, we're good.
+    if (actual == expect)
+        return "";
+
+    // For the rest of the logic, build up a suitable error string as we go so
+    // we only have to make a single pass over the list of acceptable types.
+    // If we detect success along the way, we'll simply discard the partial
+    // error string.
+    std::ostringstream out;
+    out << colon(pfx) << sTypes.lookup(expect);
+
+    // If there are any convertible types, append that list.
+    if (! accept.empty())
+    {
+        out << " (";
+        const char* sep = "or ";
+        for (TypeVector::const_iterator ai(accept.begin()), aend(accept.end());
+             ai != aend; ++ai, sep = ", ")
+        {
+            // Don't forget to return success if we match any of those types...
+            if (actual == *ai)
+                return "";
+            out << sep << sTypes.lookup(*ai);
+        }
+        out << ')';
+    }
+    // If we got this far, it's because 'actual' was not one of the acceptable
+    // types, so we must return an error. 'out' already contains colon(pfx)
+    // and the formatted list of acceptable types, so just append the mismatch
+    // phrase and the actual type.
+    out << op << sTypes.lookup(actual);
+    return out.str();
+}
+
+// see docstring in .h file
+std::string llsd_matches(const LLSD& prototype, const LLSD& data, const std::string& pfx)
+{
+    LL_PROFILE_ZONE_SCOPED
+
+    // An undefined prototype means that any data is valid.
+    // An undefined slot in an array or map prototype means that any data
+    // may fill that slot.
+    if (prototype.isUndefined())
+        return "";
+    // A prototype array must match a data array with at least as many
+    // entries. Moreover, every prototype entry must match the
+    // corresponding data entry.
+    if (prototype.isArray())
+    {
+        if (! data.isArray())
+        {
+            return STRINGIZE(colon(pfx) << "Array" << op << sTypes.lookup(data.type()));
+        }
+        if (data.size() < prototype.size())
+        {
+            return STRINGIZE(colon(pfx) << "Array size " << prototype.size() << op
+                             << "Array size " << data.size());
+        }
+        for (LLSD::Integer i = 0; i < prototype.size(); ++i)
+        {
+            std::string match(llsd_matches(prototype[i], data[i], STRINGIZE('[' << i << ']')));
+            if (! match.empty())
+            {
+                return match;
+            }
+        }
+        return "";
+    }
+    // A prototype map must match a data map. Every key in the prototype
+    // must have a corresponding key in the data map; every value in the
+    // prototype must match the corresponding key's value in the data.
+    if (prototype.isMap())
+    {
+        if (! data.isMap())
+        {
+            return STRINGIZE(colon(pfx) << "Map" << op << sTypes.lookup(data.type()));
+        }
+        // If there are a number of keys missing from the data, it would be
+        // frustrating to a coder to discover them one at a time, with a big
+        // build each time. Enumerate all missing keys.
+        std::ostringstream out;
+        out << colon(pfx);
+        const char* init = "Map missing keys: ";
+        const char* sep = init;
+        for (LLSD::map_const_iterator mi = prototype.beginMap(); mi != prototype.endMap(); ++mi)
+        {
+            if (! data.has(mi->first))
+            {
+                out << sep << mi->first;
+                sep = ", ";
+            }
+        }
+        // So... are we missing any keys?
+        if (sep != init)
+        {
+            return out.str();
+        }
+        // Good, the data block contains all the keys required by the
+        // prototype. Now match the prototype entries.
+        for (LLSD::map_const_iterator mi2 = prototype.beginMap(); mi2 != prototype.endMap(); ++mi2)
+        {
+            std::string match(llsd_matches(mi2->second, data[mi2->first],
+                                           STRINGIZE("['" << mi2->first << "']")));
+            if (! match.empty())
+            {
+                return match;
+            }
+        }
+        return "";
+    }
+    // A String prototype can match String, Boolean, Integer, Real, UUID,
+    // Date and URI, because any of these can be converted to String.
+    if (prototype.isString())
+    {
+        static LLSD::Type accept[] =
+        {
+            LLSD::TypeBoolean,
+            LLSD::TypeInteger,
+            LLSD::TypeReal,
+            LLSD::TypeUUID,
+            LLSD::TypeDate,
+            LLSD::TypeURI
+        };
+        return match_types(prototype.type(),
+                           TypeVector(boost::begin(accept), boost::end(accept)),
+                           data.type(),
+                           pfx);
+    }
+    // Boolean, Integer, Real match each other or String. TBD: ensure that
+    // a String value is numeric.
+    if (prototype.isBoolean() || prototype.isInteger() || prototype.isReal())
+    {
+        static LLSD::Type all[] =
+        {
+            LLSD::TypeBoolean,
+            LLSD::TypeInteger,
+            LLSD::TypeReal,
+            LLSD::TypeString
+        };
+        // Funny business: shuffle the set of acceptable types to include all
+        // but the prototype's type. Get the acceptable types in a set.
+        std::set<LLSD::Type> rest(boost::begin(all), boost::end(all));
+        // Remove the prototype's type because we pass that separately.
+        rest.erase(prototype.type());
+        return match_types(prototype.type(),
+                           TypeVector(rest.begin(), rest.end()),
+                           data.type(),
+                           pfx);
+    }
+    // UUID, Date and URI match themselves or String.
+    if (prototype.isUUID() || prototype.isDate() || prototype.isURI())
+    {
+        static LLSD::Type accept[] =
+        {
+            LLSD::TypeString
+        };
+        return match_types(prototype.type(),
+                           TypeVector(boost::begin(accept), boost::end(accept)),
+                           data.type(),
+                           pfx);
+    }
+    // We don't yet know the conversion semantics associated with any new LLSD
+    // data type that might be added, so until we've been extended to handle
+    // them, assume it's strict: the new type matches only itself. (This is
+    // true of Binary, which is why we don't handle that case separately.) Too
+    // bad LLSD doesn't define isConvertible(Type to, Type from).
+    return match_types(prototype.type(), TypeVector(), data.type(), pfx);
+}
+
+bool llsd_equals(const LLSD& lhs, const LLSD& rhs, int bits)
+{
+    LL_PROFILE_ZONE_SCOPED
+
+    // We're comparing strict equality of LLSD representation rather than
+    // performing any conversions. So if the types aren't equal, the LLSD
+    // values aren't equal.
+    if (lhs.type() != rhs.type())
+    {
+        return false;
+    }
+
+    // Here we know both types are equal. Now compare values.
+    switch (lhs.type())
+    {
+    case LLSD::TypeUndefined:
+        // Both are TypeUndefined. There's nothing more to know.
+        return true;
+
+    case LLSD::TypeReal:
+        // This is where the 'bits' argument comes in handy. If passed
+        // explicitly, it means to use is_approx_equal_fraction() to compare.
+        if (bits >= 0)
+        {
+            return is_approx_equal_fraction(lhs.asReal(), rhs.asReal(), bits);
+        }
+        // Otherwise we compare bit representations, and the usual caveats
+        // about comparing floating-point numbers apply. Omitting 'bits' when
+        // comparing Real values is only useful when we expect identical bit
+        // representation for a given Real value, e.g. for integer-valued
+        // Reals.
+        return (lhs.asReal() == rhs.asReal());
+
+#define COMPARE_SCALAR(type)                                    \
+    case LLSD::Type##type:                                      \
+        /* LLSD::URI has operator!=() but not operator==() */   \
+        /* rely on the optimizer for all others */              \
+        return (! (lhs.as##type() != rhs.as##type()))
+
+    COMPARE_SCALAR(Boolean);
+    COMPARE_SCALAR(Integer);
+    COMPARE_SCALAR(String);
+    COMPARE_SCALAR(UUID);
+    COMPARE_SCALAR(Date);
+    COMPARE_SCALAR(URI);
+    COMPARE_SCALAR(Binary);
+
+#undef COMPARE_SCALAR
+
+    case LLSD::TypeArray:
+    {
+        LLSD::array_const_iterator
+            lai(lhs.beginArray()), laend(lhs.endArray()),
+            rai(rhs.beginArray()), raend(rhs.endArray());
+        // Compare array elements, walking the two arrays in parallel.
+        for ( ; lai != laend && rai != raend; ++lai, ++rai)
+        {
+            // If any one array element is unequal, the arrays are unequal.
+            if (! llsd_equals(*lai, *rai, bits))
+                return false;
+        }
+        // Here we've reached the end of one or the other array. They're equal
+        // only if they're BOTH at end: that is, if they have equal length too.
+        return (lai == laend && rai == raend);
+    }
+
+    case LLSD::TypeMap:
+    {
+        // Build a set of all rhs keys.
+        std::set<LLSD::String> rhskeys;
+        for (LLSD::map_const_iterator rmi(rhs.beginMap()), rmend(rhs.endMap());
+             rmi != rmend; ++rmi)
+        {
+            rhskeys.insert(rmi->first);
+        }
+        // Now walk all the lhs keys.
+        for (LLSD::map_const_iterator lmi(lhs.beginMap()), lmend(lhs.endMap());
+             lmi != lmend; ++lmi)
+        {
+            // Try to erase this lhs key from the set of rhs keys. If rhs has
+            // no such key, the maps are unequal. erase(key) returns count of
+            // items erased.
+            if (rhskeys.erase(lmi->first) != 1)
+                return false;
+            // Both maps have the current key. Compare values.
+            if (! llsd_equals(lmi->second, rhs[lmi->first], bits))
+                return false;
+        }
+        // We've now established that all the lhs keys have equal values in
+        // both maps. The maps are equal unless rhs contains a superset of
+        // those keys.
+        return rhskeys.empty();
+    }
+
+    default:
+        // We expect that every possible type() value is specifically handled
+        // above. Failing to extend this switch to support a new LLSD type is
+        // an error that must be brought to the coder's attention.
+        LL_ERRS("llsd_equals") << "llsd_equals(" << lhs << ", " << rhs << ", " << bits << "): "
+            "unknown type " << lhs.type() << LL_ENDL;
+        return false;               // pacify the compiler
+    }
+}
+
+/*****************************************************************************
+*   llsd::drill()
+*****************************************************************************/
+namespace llsd
+{
+
+LLSD& drill_ref(LLSD& blob, const LLSD& rawPath)
+{
+    LL_PROFILE_ZONE_SCOPED
+
+    // Treat rawPath uniformly as an array. If it's not already an array,
+    // store it as the only entry in one. (But let's say Undefined means an
+    // empty array.)
+    LLSD path;
+    if (rawPath.isArray() || rawPath.isUndefined())
+    {
+        path = rawPath;
+    }
+    else
+    {
+        path.append(rawPath);
+    }
+
+    // Need to indicate a current destination -- but that current destination
+    // must change as we step through the path array. Where normally we'd use
+    // an LLSD& to capture a subscripted LLSD lvalue, this time we must
+    // instead use a pointer -- since it must be reassigned.
+    // Start by pointing to the input blob exactly as is.
+    LLSD* located{&blob};
+
+    // Extract the element of interest by walking path. Use an explicit index
+    // so that, in case of a bogus type in path, we can identify the specific
+    // path entry that's bad.
+    for (LLSD::Integer i = 0; i < path.size(); ++i)
+    {
+        LL_PROFILE_ZONE_NUM( i )
+
+        const LLSD& key{path[i]};
+        if (key.isString())
+        {
+            // a string path element is a map key
+            located = &((*located)[key.asString()]);
+        }
+        else if (key.isInteger())
+        {
+            // an integer path element is an array index
+            located = &((*located)[key.asInteger()]);
+        }
+        else
+        {
+            // What do we do with Real or Array or Map or ...?
+            // As it's a coder error -- not a user error -- rub the coder's
+            // face in it so it gets fixed.
+            LL_ERRS("llsdutil") << "drill(" << blob << ", " << rawPath
+                                << "): path[" << i << "] bad type "
+                                << sTypes.lookup(key.type()) << LL_ENDL;
+        }
+    }
+
+    // dereference the pointer to return a reference to the element we found
+    return *located;
+}
+
+LLSD drill(const LLSD& blob, const LLSD& path)
+{
+    LL_PROFILE_ZONE_SCOPED
+
+    // drill_ref() does exactly what we want. Temporarily cast away
+    // const-ness and use that.
+    return drill_ref(const_cast<LLSD&>(blob), path);
+}
+
+} // namespace llsd
+
+// Construct a deep partial clone of of an LLSD object. primitive types share
+// references, however maps, arrays and binary objects are duplicated. An optional
+// filter may be include to exclude/include keys in a map.
+LLSD llsd_clone(LLSD value, LLSD filter)
+{
+    LL_PROFILE_ZONE_SCOPED
+
+    LLSD clone;
+    bool has_filter(filter.isMap());
+
+    switch (value.type())
+    {
+    case LLSD::TypeMap:
+        clone = LLSD::emptyMap();
+        for (LLSD::map_const_iterator itm = value.beginMap(); itm != value.endMap(); ++itm)
+        {
+            if (has_filter)
+            {
+                if (filter.has((*itm).first))
+                {
+                    if (!filter[(*itm).first].asBoolean())
+                        continue;
+                }
+                else if (filter.has("*"))
+                {
+                    if (!filter["*"].asBoolean())
+                        continue;
+                }
+                else
+                {
+                    continue;
+                }
+            }
+            clone[(*itm).first] = llsd_clone((*itm).second, filter);
+        }
+        break;
+    case LLSD::TypeArray:
+        clone = LLSD::emptyArray();
+        for (LLSD::array_const_iterator ita = value.beginArray(); ita != value.endArray(); ++ita)
+        {
+            clone.append(llsd_clone(*ita, filter));
+        }
+        break;
+
+    case LLSD::TypeBinary:
+    {
+        LLSD::Binary bin(value.asBinary().begin(), value.asBinary().end());
+        clone = LLSD::Binary(bin);
+        break;
+    }
+    default:
+        clone = value;
+    }
+
+    return clone;
+}
+
+LLSD llsd_shallow(LLSD value, LLSD filter)
+{
+    LLSD shallow;
+    bool has_filter(filter.isMap());
+
+    if (value.isMap())
+    {
+        shallow = LLSD::emptyMap();
+        for (LLSD::map_const_iterator itm = value.beginMap(); itm != value.endMap(); ++itm)
+        {
+            if (has_filter)
+            {
+                if (filter.has((*itm).first))
+                {
+                    if (!filter[(*itm).first].asBoolean())
+                        continue;
+                }
+                else if (filter.has("*"))
+                {
+                    if (!filter["*"].asBoolean())
+                        continue;
+                }
+                else
+                {
+                    continue;
+                }
+            }
+            shallow[(*itm).first] = (*itm).second;
+        }
+    }
+    else if (value.isArray())
+    {
+        shallow = LLSD::emptyArray();
+        for (LLSD::array_const_iterator ita = value.beginArray(); ita != value.endArray(); ++ita)
+        {
+            shallow.append(*ita);
+        }
+    }
+    else
+    {
+        return value;
+    }
+
+    return shallow;
+}
+
+LLSD LL::apply_llsd_fix(size_t arity, const LLSD& args)
+{
+    // LLSD supports a number of types, two of which are aggregates: Map and
+    // Array. We don't try to support Map: supporting Map would seem to
+    // promise that we could somehow match the string key to 'func's parameter
+    // names. Uh sorry, maybe in some future version of C++ with reflection.
+    if (args.isMap())
+    {
+        LLTHROW(LL::apply_error("LL::apply(function, Map LLSD) unsupported"));
+    }
+    // We expect an LLSD array, but what the heck, treat isUndefined() as a
+    // zero-length array for calling a nullary 'func'.
+    if (args.isUndefined() || args.isArray())
+    {
+        // this works because LLSD().size() == 0
+        if (args.size() != arity)
+        {
+            LLTHROW(LL::apply_error(stringize("LL::apply(function(", arity, " args), ",
+                                              args.size(), "-entry LLSD array)")));
+        }
+        return args;
+    }
+
+    // args is one of the scalar types
+    // scalar_LLSD.size() == 0, so don't test that here.
+    // You can pass a scalar LLSD only to a unary 'func'.
+    if (arity != 1)
+    {
+        LLTHROW(LL::apply_error(stringize("LL::apply(function(", arity, " args), "
+                                          "LLSD ", LLSD::typeString(args.type()), ")")));
+    }
+    // make an array of it
+    return llsd::array(args);
+}