text:
/**
 * Copyright (C) 2017 MongoDB Inc.
 *
 * This program is free software: you can redistribute it and/or  modify
 * it under the terms of the GNU Affero General Public License, version 3,
 * as published by the Free Software Foundation.
 *
 * This program 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 Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * As a special exception, the copyright holders give permission to link the
 * code of portions of this program with the OpenSSL library under certain
 * conditions as described in each individual source file and distribute
 * linked combinations including the program with the OpenSSL library. You
 * must comply with the GNU Affero General Public License in all respects
 * for all of the code used other than as permitted herein. If you modify
 * file(s) with this exception, you may extend this exception to your
 * version of the file(s), but you are not obligated to do so. If you do not
 * wish to do so, delete this exception statement from your version. If you
 * delete this exception statement from all source files in the program,
 * then also delete it in the license file.
 */

#define MONGO_LOG_DEFAULT_COMPONENT ::mongo::logger::LogComponent::kQuery

#include "mongo/platform/basic.h"

#include "mongo/db/matcher/schema/json_schema_parser.h"

#include <boost/container/flat_set.hpp>

#include "mongo/bson/bsontypes.h"
#include "mongo/bson/unordered_fields_bsonelement_comparator.h"
#include "mongo/db/matcher/expression_always_boolean.h"
#include "mongo/db/matcher/expression_parser.h"
#include "mongo/db/matcher/matcher_type_set.h"
#include "mongo/db/matcher/schema/expression_internal_schema_all_elem_match_from_index.h"
#include "mongo/db/matcher/schema/expression_internal_schema_allowed_properties.h"
#include "mongo/db/matcher/schema/expression_internal_schema_cond.h"
#include "mongo/db/matcher/schema/expression_internal_schema_eq.h"
#include "mongo/db/matcher/schema/expression_internal_schema_fmod.h"
#include "mongo/db/matcher/schema/expression_internal_schema_match_array_index.h"
#include "mongo/db/matcher/schema/expression_internal_schema_max_items.h"
#include "mongo/db/matcher/schema/expression_internal_schema_max_length.h"
#include "mongo/db/matcher/schema/expression_internal_schema_max_properties.h"
#include "mongo/db/matcher/schema/expression_internal_schema_min_items.h"
#include "mongo/db/matcher/schema/expression_internal_schema_min_length.h"
#include "mongo/db/matcher/schema/expression_internal_schema_min_properties.h"
#include "mongo/db/matcher/schema/expression_internal_schema_object_match.h"
#include "mongo/db/matcher/schema/expression_internal_schema_root_doc_eq.h"
#include "mongo/db/matcher/schema/expression_internal_schema_unique_items.h"
#include "mongo/db/matcher/schema/expression_internal_schema_xor.h"
#include "mongo/logger/log_component_settings.h"
#include "mongo/stdx/memory.h"
#include "mongo/util/log.h"
#include "mongo/util/string_map.h"

namespace mongo {

using PatternSchema = InternalSchemaAllowedPropertiesMatchExpression::PatternSchema;
using Pattern = InternalSchemaAllowedPropertiesMatchExpression::Pattern;

namespace {
// Standard JSON Schema keyword constants.
constexpr StringData kSchemaAdditionalItemsKeyword = "additionalItems"_sd;
constexpr StringData kSchemaAdditionalPropertiesKeyword = "additionalProperties"_sd;
constexpr StringData kSchemaAllOfKeyword = "allOf"_sd;
constexpr StringData kSchemaAnyOfKeyword = "anyOf"_sd;
constexpr StringData kSchemaDependenciesKeyword = "dependencies"_sd;
constexpr StringData kSchemaDescriptionKeyword = "description"_sd;
constexpr StringData kSchemaEnumKeyword = "enum"_sd;
constexpr StringData kSchemaExclusiveMaximumKeyword = "exclusiveMaximum"_sd;
constexpr StringData kSchemaExclusiveMinimumKeyword = "exclusiveMinimum"_sd;
constexpr StringData kSchemaItemsKeyword = "items"_sd;
constexpr StringData kSchemaMaxItemsKeyword = "maxItems"_sd;
constexpr StringData kSchemaMaxLengthKeyword = "maxLength"_sd;
constexpr StringData kSchemaMaxPropertiesKeyword = "maxProperties"_sd;
constexpr StringData kSchemaMaximumKeyword = "maximum"_sd;
constexpr StringData kSchemaMinItemsKeyword = "minItems"_sd;
constexpr StringData kSchemaMinLengthKeyword = "minLength"_sd;
constexpr StringData kSchemaMinPropertiesKeyword = "minProperties"_sd;
constexpr StringData kSchemaMinimumKeyword = "minimum"_sd;
constexpr StringData kSchemaMultipleOfKeyword = "multipleOf"_sd;
constexpr StringData kSchemaNotKeyword = "not"_sd;
constexpr StringData kSchemaOneOfKeyword = "oneOf"_sd;
constexpr StringData kSchemaPatternKeyword = "pattern"_sd;
constexpr StringData kSchemaPatternPropertiesKeyword = "patternProperties"_sd;
constexpr StringData kSchemaPropertiesKeyword = "properties"_sd;
constexpr StringData kSchemaRequiredKeyword = "required"_sd;
constexpr StringData kSchemaTitleKeyword = "title"_sd;
constexpr StringData kSchemaTypeKeyword = "type"_sd;
constexpr StringData kSchemaUniqueItemsKeyword = "uniqueItems"_sd;

// MongoDB-specific (non-standard) JSON Schema keyword constants.
constexpr StringData kSchemaBsonTypeKeyword = "bsonType"_sd;

// Explicitly unsupported JSON Schema keywords.
const std::set<StringData> unsupportedKeywords{
    "$ref"_sd, "$schema"_sd, "default"_sd, "definitions"_sd, "format"_sd, "id"_sd,
};

constexpr StringData kNamePlaceholder = "i"_sd;

/**
 * Parses 'schema' to the semantically equivalent match expression. If the schema has an associated
 * path, e.g. if we are parsing the nested schema for property "myProp" in
 *
 *    {properties: {myProp: <nested-schema>}}
 *
 * then this is passed in 'path'. In this example, the value of 'path' is "myProp". If there is no
 * path, e.g. for top-level schemas, then 'path' is empty.
 */
StatusWithMatchExpression _parse(StringData path, BSONObj schema, bool ignoreUnknownKeywords);

/**
 * Constructs and returns a match expression to evaluate a JSON Schema restriction keyword.
 *
 * This handles semantic differences between the MongoDB query language and JSON Schema. MongoDB
 * match expressions which apply to a particular type will reject non-matching types, whereas JSON
 * Schema restriction keywords allow non-matching types. As an example, consider the maxItems
 * keyword. This keyword only applies in JSON Schema if the type is an array, whereas the
 * $_internalSchemaMaxItems match expression node rejects non-arrays.
 *
 * The 'restrictionType' expresses the type to which the JSON Schema restriction applies (e.g.
 * arrays for maxItems). The 'restrictionExpr' is the match expression node which can be used to
 * enforce this restriction, should the types match (e.g. $_internalSchemaMaxItems). 'statedType' is
 * a parsed representation of the JSON Schema type keyword which is in effect.
 */
std::unique_ptr<MatchExpression> makeRestriction(const MatcherTypeSet& restrictionType,
                                                 StringData path,
                                                 std::unique_ptr<MatchExpression> restrictionExpr,
                                                 InternalSchemaTypeExpression* statedType) {
    invariant(restrictionType.isSingleType());

    if (statedType && statedType->typeSet().isSingleType()) {
        // Use NumberInt in the "number" case as a stand-in.
        BSONType statedBSONType = statedType->typeSet().allNumbers
            ? BSONType::NumberInt
            : *statedType->typeSet().bsonTypes.begin();

        if (restrictionType.hasType(statedBSONType)) {
            // This restriction applies to the type that is already being enforced. We return the
            // restriction unmodified.
            return restrictionExpr;
        } else {
            // This restriction doesn't take any effect, since the type of the schema is different
            // from the type to which this retriction applies.
            return stdx::make_unique<AlwaysTrueMatchExpression>();
        }
    }

    // Generate and return the following expression tree:
    //
    //  (OR (<restrictionExpr>) (NOT (INTERNAL_SCHEMA_TYPE <restrictionType>))
    //
    // We need to do this because restriction keywords do not apply when a field is either not
    // present or of a different type.
    auto typeExpr = stdx::make_unique<InternalSchemaTypeExpression>(path, restrictionType);

    auto notExpr = stdx::make_unique<NotMatchExpression>(typeExpr.release());

    auto orExpr = stdx::make_unique<OrMatchExpression>();
    orExpr->add(notExpr.release());
    orExpr->add(restrictionExpr.release());

    return std::move(orExpr);
}

StatusWith<std::unique_ptr<InternalSchemaTypeExpression>> parseType(
    StringData path,
    StringData keywordName,
    BSONElement typeElt,
    const StringMap<BSONType>& aliasMap) {
    if (typeElt.type() != BSONType::String && typeElt.type() != BSONType::Array) {
        return {Status(ErrorCodes::TypeMismatch,
                       str::stream() << "$jsonSchema keyword '" << keywordName
                                     << "' must be either a string or an array of strings")};
    }

    std::set<StringData> aliases;
    if (typeElt.type() == BSONType::String) {
        if (typeElt.valueStringData() == JSONSchemaParser::kSchemaTypeInteger) {
            return {ErrorCodes::FailedToParse,
                    str::stream() << "$jsonSchema type '" << JSONSchemaParser::kSchemaTypeInteger
                                  << "' is not currently supported."};
        }
        aliases.insert(typeElt.valueStringData());
    } else {
        for (auto&& typeArrayEntry : typeElt.embeddedObject()) {
            if (typeArrayEntry.type() != BSONType::String) {
                return {Status(ErrorCodes::TypeMismatch,
                               str::stream() << "$jsonSchema keyword '" << keywordName
                                             << "' array elements must be strings")};
            }

            if (typeArrayEntry.valueStringData() == JSONSchemaParser::kSchemaTypeInteger) {
                return {ErrorCodes::FailedToParse,
                        str::stream() << "$jsonSchema type '"
                                      << JSONSchemaParser::kSchemaTypeInteger
                                      << "' is not currently supported."};
            }

            auto insertionResult = aliases.insert(typeArrayEntry.valueStringData());
            if (!insertionResult.second) {
                return {Status(ErrorCodes::FailedToParse,
                               str::stream() << "$jsonSchema keyword '" << keywordName
                                             << "' has duplicate value: "
                                             << typeArrayEntry.valueStringData())};
            }
        }
    }

    auto typeSet = MatcherTypeSet::fromStringAliases(std::move(aliases), aliasMap);
    if (!typeSet.isOK()) {
        return typeSet.getStatus();
    }

    if (typeSet.getValue().isEmpty()) {
        return {Status(ErrorCodes::FailedToParse,
                       str::stream() << "$jsonSchema keyword '" << keywordName
                                     << "' must name at least one type")};
    }

    auto typeExpr =
        stdx::make_unique<InternalSchemaTypeExpression>(path, std::move(typeSet.getValue()));

    return {std::move(typeExpr)};
}

StatusWithMatchExpression parseMaximum(StringData path,
                                       BSONElement maximum,
                                       InternalSchemaTypeExpression* typeExpr,
                                       bool isExclusiveMaximum) {
    if (!maximum.isNumber()) {
        return {Status(ErrorCodes::TypeMismatch,
                       str::stream() << "$jsonSchema keyword '" << kSchemaMaximumKeyword
                                     << "' must be a number")};
    }

    if (path.empty()) {
        // This restriction has no effect in a top-level schema, since we only store objects.
        return {stdx::make_unique<AlwaysTrueMatchExpression>()};
    }

    std::unique_ptr<ComparisonMatchExpression> expr;
    if (isExclusiveMaximum) {
        expr = stdx::make_unique<LTMatchExpression>(path, maximum);
    } else {
        expr = stdx::make_unique<LTEMatchExpression>(path, maximum);
    }

    MatcherTypeSet restrictionType;
    restrictionType.allNumbers = true;
    return makeRestriction(restrictionType, path, std::move(expr), typeExpr);
}

StatusWithMatchExpression parseMinimum(StringData path,
                                       BSONElement minimum,
                                       InternalSchemaTypeExpression* typeExpr,
                                       bool isExclusiveMinimum) {
    if (!minimum.isNumber()) {
        return {Status(ErrorCodes::TypeMismatch,
                       str::stream() << "$jsonSchema keyword '" << kSchemaMinimumKeyword
                                     << "' must be a number")};
    }

    if (path.empty()) {
        // This restriction has no effect in a top-level schema, since we only store objects.
        return {stdx::make_unique<AlwaysTrueMatchExpression>()};
    }

    std::unique_ptr<ComparisonMatchExpression> expr;
    if (isExclusiveMinimum) {
        expr = stdx::make_unique<GTMatchExpression>(path, minimum);
    } else {
        expr = stdx::make_unique<GTEMatchExpression>(path, minimum);
    }

    MatcherTypeSet restrictionType;
    restrictionType.allNumbers = true;
    return makeRestriction(restrictionType, path, std::move(expr), typeExpr);
}

/**
 * Parses length-related keywords that expect a nonnegative long as an argument.
 */
template <class T>
StatusWithMatchExpression parseLength(StringData path,
                                      BSONElement length,
                                      InternalSchemaTypeExpression* typeExpr,
                                      BSONType restrictionType) {
    auto parsedLength = MatchExpressionParser::parseIntegerElementToNonNegativeLong(length);
    if (!parsedLength.isOK()) {
        return parsedLength.getStatus();
    }

    if (path.empty()) {
        return {stdx::make_unique<AlwaysTrueMatchExpression>()};
    }

    auto expr = stdx::make_unique<T>(path, parsedLength.getValue());
    return makeRestriction(restrictionType, path, std::move(expr), typeExpr);
}

StatusWithMatchExpression parsePattern(StringData path,
                                       BSONElement pattern,
                                       InternalSchemaTypeExpression* typeExpr) {
    if (pattern.type() != BSONType::String) {
        return {Status(ErrorCodes::TypeMismatch,
                       str::stream() << "$jsonSchema keyword '" << kSchemaPatternKeyword
                                     << "' must be a string")};
    }

    if (path.empty()) {
        return {stdx::make_unique<AlwaysTrueMatchExpression>()};
    }

    // JSON Schema does not allow regex flags to be specified.
    constexpr auto emptyFlags = "";
    auto expr =
        stdx::make_unique<RegexMatchExpression>(path, pattern.valueStringData(), emptyFlags);

    return makeRestriction(BSONType::String, path, std::move(expr), typeExpr);
}

StatusWithMatchExpression parseMultipleOf(StringData path,
                                          BSONElement multipleOf,
                                          InternalSchemaTypeExpression* typeExpr) {
    if (!multipleOf.isNumber()) {
        return {Status(ErrorCodes::TypeMismatch,
                       str::stream() << "$jsonSchema keyword '" << kSchemaMultipleOfKeyword
                                     << "' must be a number")};
    }

    if (multipleOf.numberDecimal().isNegative() || multipleOf.numberDecimal().isZero()) {
        return {Status(ErrorCodes::FailedToParse,
                       str::stream() << "$jsonSchema keyword '" << kSchemaMultipleOfKeyword
                                     << "' must have a positive value")};
    }
    if (path.empty()) {
        return {stdx::make_unique<AlwaysTrueMatchExpression>()};
    }

    auto expr = stdx::make_unique<InternalSchemaFmodMatchExpression>(
        path, multipleOf.numberDecimal(), Decimal128(0));

    MatcherTypeSet restrictionType;
    restrictionType.allNumbers = true;
    return makeRestriction(restrictionType, path, std::move(expr), typeExpr);
}

template <class T>
StatusWithMatchExpression parseLogicalKeyword(StringData path,
                                              BSONElement logicalElement,
                                              bool ignoreUnknownKeywords) {
    if (logicalElement.type() != BSONType::Array) {
        return {ErrorCodes::TypeMismatch,
                str::stream() << "$jsonSchema keyword '" << logicalElement.fieldNameStringData()
                              << "' must be an array"};
    }

    auto logicalElementObj = logicalElement.embeddedObject();
    if (logicalElementObj.isEmpty()) {
        return {ErrorCodes::BadValue,
                str::stream() << "$jsonSchema keyword '" << logicalElement.fieldNameStringData()
                              << "' must be a non-empty array"};
    }

    std::unique_ptr<T> listOfExpr = stdx::make_unique<T>();
    for (const auto& elem : logicalElementObj) {
        if (elem.type() != BSONType::Object) {
            return {ErrorCodes::TypeMismatch,
                    str::stream() << "$jsonSchema keyword '" << logicalElement.fieldNameStringData()
                                  << "' must be an array of objects, but found an element of type "
                                  << elem.type()};
        }

        auto nestedSchemaMatch = _parse(path, elem.embeddedObject(), ignoreUnknownKeywords);
        if (!nestedSchemaMatch.isOK()) {
            return nestedSchemaMatch.getStatus();
        }

        listOfExpr->add(nestedSchemaMatch.getValue().release());
    }

    return {std::move(listOfExpr)};
}

StatusWithMatchExpression parseEnum(StringData path, BSONElement enumElement) {
    if (enumElement.type() != BSONType::Array) {
        return {ErrorCodes::TypeMismatch,
                str::stream() << "$jsonSchema keyword '" << kSchemaEnumKeyword
                              << "' must be an array, but found an element of type "
                              << enumElement.type()};
    }

    auto enumArray = enumElement.embeddedObject();
    if (enumArray.isEmpty()) {
        return {ErrorCodes::FailedToParse,
                str::stream() << "$jsonSchema keyword '" << kSchemaEnumKeyword
                              << "' cannot be an empty array"};
    }

    auto orExpr = stdx::make_unique<OrMatchExpression>();
    UnorderedFieldsBSONElementComparator eltComp;
    BSONEltSet eqSet = eltComp.makeBSONEltSet();
    for (auto&& arrayElem : enumArray) {
        auto insertStatus = eqSet.insert(arrayElem);
        if (!insertStatus.second) {
            return {ErrorCodes::FailedToParse,
                    str::stream() << "$jsonSchema keyword '" << kSchemaEnumKeyword
                                  << "' array cannot contain duplicate values."};
        }

        // 'enum' at the top-level implies a literal object match on the root document.
        if (path.empty()) {
            // Top-level non-object enum values can be safely ignored, since MongoDB only stores
            // objects, not scalars or arrays.
            if (arrayElem.type() == BSONType::Object) {
                auto rootDocEq = stdx::make_unique<InternalSchemaRootDocEqMatchExpression>(
                    arrayElem.embeddedObject());
                orExpr->add(rootDocEq.release());
            }
        } else {
            auto eqExpr = stdx::make_unique<InternalSchemaEqMatchExpression>(path, arrayElem);

            orExpr->add(eqExpr.release());
        }
    }

    // Make sure that the OR expression has at least 1 child.
    if (orExpr->numChildren() == 0) {
        return {stdx::make_unique<AlwaysFalseMatchExpression>()};
    }

    return {std::move(orExpr)};
}

/**
 * Given a BSON element corresponding to the $jsonSchema "required" keyword, returns the set of
 * required property names. If the contents of the "required" keyword are invalid, returns a non-OK
 * status.
 */
StatusWith<boost::container::flat_set<StringData>> parseRequired(BSONElement requiredElt) {
    if (requiredElt.type() != BSONType::Array) {
        return {ErrorCodes::TypeMismatch,
                str::stream() << "$jsonSchema keyword '" << kSchemaRequiredKeyword
                              << "' must be an array, but found an element of type "
                              << requiredElt.type()};
    }

    std::vector<StringData> propertyVec;
    for (auto&& propertyName : requiredElt.embeddedObject()) {
        if (propertyName.type() != BSONType::String) {
            return {ErrorCodes::TypeMismatch,
                    str::stream() << "$jsonSchema keyword '" << kSchemaRequiredKeyword
                                  << "' must be an array of strings, but found an element of type: "
                                  << propertyName.type()};
        }

        propertyVec.push_back(propertyName.valueStringData());
    }

    if (propertyVec.empty()) {
        return {ErrorCodes::FailedToParse,
                str::stream() << "$jsonSchema keyword '" << kSchemaRequiredKeyword
                              << "' cannot be an empty array"};
    }

    boost::container::flat_set<StringData> requiredProperties{propertyVec.begin(),
                                                              propertyVec.end()};
    if (requiredProperties.size() != propertyVec.size()) {
        return {ErrorCodes::FailedToParse,
                str::stream() << "$jsonSchema keyword '" << kSchemaRequiredKeyword
                              << "' array cannot contain duplicate values"};
    }
    return requiredProperties;
}

/**
 * Given the already-parsed set of required properties, returns a MatchExpression which ensures that
 * those properties exist. Returns a parsing error if the translation fails.
 */
StatusWithMatchExpression translateRequired(
    const boost::container::flat_set<StringData>& requiredProperties,
    StringData path,
    InternalSchemaTypeExpression* typeExpr) {
    auto andExpr = stdx::make_unique<AndMatchExpression>();

    for (auto&& propertyName : requiredProperties) {
        andExpr->add(new ExistsMatchExpression(propertyName));
    }

    // If this is a top-level schema, then we know that we are matching against objects, and there
    // is no need to worry about ensuring that non-objects match.
    if (path.empty()) {
        return {std::move(andExpr)};
    }

    auto objectMatch =
        stdx::make_unique<InternalSchemaObjectMatchExpression>(path, std::move(andExpr));

    return makeRestriction(BSONType::Object, path, std::move(objectMatch), typeExpr);
}

StatusWithMatchExpression parseProperties(
    StringData path,
    BSONElement propertiesElt,
    InternalSchemaTypeExpression* typeExpr,
    const boost::container::flat_set<StringData>& requiredProperties,
    bool ignoreUnknownKeywords) {
    if (propertiesElt.type() != BSONType::Object) {
        return {Status(ErrorCodes::TypeMismatch,
                       str::stream() << "$jsonSchema keyword '" << kSchemaPropertiesKeyword
                                     << "' must be an object")};
    }
    auto propertiesObj = propertiesElt.embeddedObject();

    auto andExpr = stdx::make_unique<AndMatchExpression>();
    for (auto&& property : propertiesObj) {
        if (property.type() != BSONType::Object) {
            return {ErrorCodes::TypeMismatch,
                    str::stream() << "Nested schema for $jsonSchema property '"
                                  << property.fieldNameStringData()
                                  << "' must be an object"};
        }

        auto nestedSchemaMatch = _parse(
            property.fieldNameStringData(), property.embeddedObject(), ignoreUnknownKeywords);
        if (!nestedSchemaMatch.isOK()) {
            return nestedSchemaMatch.getStatus();
        }

        if (requiredProperties.find(property.fieldNameStringData()) != requiredProperties.end()) {
            // The field name for which we created the nested schema is a required property. This
            // property must exist and therefore must match 'nestedSchemaMatch'.
            andExpr->add(nestedSchemaMatch.getValue().release());
        } else {
            // This property either must not exist or must match the nested schema. Therefore, we
            // generate the match expression (OR (NOT (EXISTS)) <nestedSchemaMatch>).
            auto existsExpr =
                stdx::make_unique<ExistsMatchExpression>(property.fieldNameStringData());

            auto notExpr = stdx::make_unique<NotMatchExpression>(existsExpr.release());

            auto orExpr = stdx::make_unique<OrMatchExpression>();
            orExpr->add(notExpr.release());
            orExpr->add(nestedSchemaMatch.getValue().release());

            andExpr->add(orExpr.release());
        }
    }

    // If this is a top-level schema, then we have no path and there is no need for an
    // explicit object match node.
    if (path.empty()) {
        return {std::move(andExpr)};
    }

    auto objectMatch =
        stdx::make_unique<InternalSchemaObjectMatchExpression>(path, std::move(andExpr));

    return makeRestriction(BSONType::Object, path, std::move(objectMatch), typeExpr);
}

StatusWith<std::vector<PatternSchema>> parsePatternProperties(BSONElement patternPropertiesElt,
                                                              bool ignoreUnknownKeywords) {
    std::vector<PatternSchema> patternProperties;
    if (!patternPropertiesElt) {
        return {std::move(patternProperties)};
    }

    if (patternPropertiesElt.type() != BSONType::Object) {
        return {Status(ErrorCodes::TypeMismatch,
                       str::stream() << "$jsonSchema keyword '" << kSchemaPatternPropertiesKeyword
                                     << "' must be an object")};
    }

    for (auto&& patternSchema : patternPropertiesElt.embeddedObject()) {
        if (patternSchema.type() != BSONType::Object) {
            return {Status(ErrorCodes::TypeMismatch,
                           str::stream() << "$jsonSchema keyword '"
                                         << kSchemaPatternPropertiesKeyword
                                         << "' has property '"
                                         << patternSchema.fieldNameStringData()
                                         << "' which is not an object")};
        }

        // Parse the nested schema using a placeholder as the path, since we intend on using the
        // resulting match expression inside an ExpressionWithPlaceholder.
        auto nestedSchemaMatch =
            _parse(kNamePlaceholder, patternSchema.embeddedObject(), ignoreUnknownKeywords);
        if (!nestedSchemaMatch.isOK()) {
            return nestedSchemaMatch.getStatus();
        }

        auto exprWithPlaceholder = stdx::make_unique<ExpressionWithPlaceholder>(
            kNamePlaceholder.toString(), std::move(nestedSchemaMatch.getValue()));
        Pattern pattern{patternSchema.fieldNameStringData()};
        patternProperties.emplace_back(std::move(pattern), std::move(exprWithPlaceholder));
    }

    return {std::move(patternProperties)};
}

StatusWithMatchExpression parseAdditionalProperties(BSONElement additionalPropertiesElt,
                                                    bool ignoreUnknownKeywords) {
    if (!additionalPropertiesElt) {
        // The absence of the 'additionalProperties' keyword is identical in meaning to the presence
        // of 'additionalProperties' with a value of true.
        return {stdx::make_unique<AlwaysTrueMatchExpression>()};
    }

    if (additionalPropertiesElt.type() != BSONType::Bool &&
        additionalPropertiesElt.type() != BSONType::Object) {
        return {Status(ErrorCodes::TypeMismatch,
                       str::stream() << "$jsonSchema keyword '"
                                     << kSchemaAdditionalPropertiesKeyword
                                     << "' must be an object or a boolean")};
    }

    if (additionalPropertiesElt.type() == BSONType::Bool) {
        if (additionalPropertiesElt.boolean()) {
            return {stdx::make_unique<AlwaysTrueMatchExpression>()};
        } else {
            return {stdx::make_unique<AlwaysFalseMatchExpression>()};
        }
    }

    // Parse the nested schema using a placeholder as the path, since we intend on using the
    // resulting match expression inside an ExpressionWithPlaceholder.
    auto nestedSchemaMatch =
        _parse(kNamePlaceholder, additionalPropertiesElt.embeddedObject(), ignoreUnknownKeywords);
    if (!nestedSchemaMatch.isOK()) {
        return nestedSchemaMatch.getStatus();
    }

    return {std::move(nestedSchemaMatch.getValue())};
}

/**
 * Returns a match expression which handles both the 'additionalProperties' and 'patternProperties'
 * keywords.
 */
StatusWithMatchExpression parseAllowedProperties(StringData path,
                                                 BSONElement propertiesElt,
                                                 BSONElement patternPropertiesElt,
                                                 BSONElement additionalPropertiesElt,
                                                 InternalSchemaTypeExpression* typeExpr,
                                                 bool ignoreUnknownKeywords) {
    // Collect the set of properties named by the 'properties' keyword.
    boost::container::flat_set<StringData> propertyNames;
    if (propertiesElt) {
        std::vector<StringData> propertyNamesVec;
        for (auto&& elem : propertiesElt.embeddedObject()) {
            propertyNamesVec.push_back(elem.fieldNameStringData());
        }
        propertyNames = boost::container::flat_set<StringData>(propertyNamesVec.begin(),
                                                               propertyNamesVec.end());
    }

    auto patternProperties = parsePatternProperties(patternPropertiesElt, ignoreUnknownKeywords);
    if (!patternProperties.isOK()) {
        return patternProperties.getStatus();
    }

    auto otherwiseExpr = parseAdditionalProperties(additionalPropertiesElt, ignoreUnknownKeywords);
    if (!otherwiseExpr.isOK()) {
        return otherwiseExpr.getStatus();
    }
    auto otherwiseWithPlaceholder = stdx::make_unique<ExpressionWithPlaceholder>(
        kNamePlaceholder.toString(), std::move(otherwiseExpr.getValue()));

    auto allowedPropertiesExpr = stdx::make_unique<InternalSchemaAllowedPropertiesMatchExpression>(
        std::move(propertyNames),
        kNamePlaceholder,
        std::move(patternProperties.getValue()),
        std::move(otherwiseWithPlaceholder));

    // If this is a top-level schema, then we have no path and there is no need for an explicit
    // object match node.
    if (path.empty()) {
        return {std::move(allowedPropertiesExpr)};
    }

    auto objectMatch = stdx::make_unique<InternalSchemaObjectMatchExpression>(
        path, std::move(allowedPropertiesExpr));

    return makeRestriction(BSONType::Object, path, std::move(objectMatch), typeExpr);
}

/**
 * Parses 'minProperties' and 'maxProperties' JSON Schema keywords.
 */
template <class T>
StatusWithMatchExpression parseNumProperties(StringData path,
                                             BSONElement numProperties,
                                             InternalSchemaTypeExpression* typeExpr) {
    auto parsedNumProps =
        MatchExpressionParser::parseIntegerElementToNonNegativeLong(numProperties);
    if (!parsedNumProps.isOK()) {
        return parsedNumProps.getStatus();
    }

    auto expr = stdx::make_unique<T>(parsedNumProps.getValue());

    if (path.empty()) {
        // This is a top-level schema.
        return {std::move(expr)};
    }

    auto objectMatch =
        stdx::make_unique<InternalSchemaObjectMatchExpression>(path, std::move(expr));

    return makeRestriction(BSONType::Object, path, std::move(objectMatch), typeExpr);
}

StatusWithMatchExpression makeDependencyExistsClause(StringData path, StringData dependencyName) {
    auto existsExpr = stdx::make_unique<ExistsMatchExpression>(dependencyName);

    if (path.empty()) {
        return {std::move(existsExpr)};
    }

    auto objectMatch =
        stdx::make_unique<InternalSchemaObjectMatchExpression>(path, std::move(existsExpr));

    return {std::move(objectMatch)};
}

StatusWithMatchExpression translateSchemaDependency(StringData path,
                                                    BSONElement dependency,
                                                    bool ignoreUnknownKeywords) {
    invariant(dependency.type() == BSONType::Object);

    auto nestedSchemaMatch = _parse(path, dependency.embeddedObject(), ignoreUnknownKeywords);
    if (!nestedSchemaMatch.isOK()) {
        return nestedSchemaMatch.getStatus();
    }

    auto ifClause = makeDependencyExistsClause(path, dependency.fieldNameStringData());
    if (!ifClause.isOK()) {
        return ifClause.getStatus();
    }

    std::array<std::unique_ptr<MatchExpression>, 3> expressions = {
        std::move(ifClause.getValue()),
        std::move(nestedSchemaMatch.getValue()),
        stdx::make_unique<AlwaysTrueMatchExpression>()};

    auto condExpr = stdx::make_unique<InternalSchemaCondMatchExpression>(std::move(expressions));
    return {std::move(condExpr)};
}

StatusWithMatchExpression translatePropertyDependency(StringData path, BSONElement dependency) {
    invariant(dependency.type() == BSONType::Array);

    if (dependency.embeddedObject().isEmpty()) {
        return {ErrorCodes::FailedToParse,
                str::stream() << "property '" << dependency.fieldNameStringData()
                              << "' in $jsonSchema keyword '"
                              << kSchemaDependenciesKeyword
                              << "' cannot be an empty array"};
    }

    auto propertyDependencyExpr = stdx::make_unique<AndMatchExpression>();
    std::set<StringData> propertyDependencyNames;
    for (auto&& propertyDependency : dependency.embeddedObject()) {
        if (propertyDependency.type() != BSONType::String) {
            return {ErrorCodes::TypeMismatch,
                    str::stream() << "array '" << dependency.fieldNameStringData()
                                  << "' in $jsonSchema keyword '"
                                  << kSchemaDependenciesKeyword
                                  << "' can only contain strings, but found element of type: "
                                  << typeName(propertyDependency.type())};
        }

        auto insertionResult = propertyDependencyNames.insert(propertyDependency.valueStringData());
        if (!insertionResult.second) {
            return {ErrorCodes::FailedToParse,
                    str::stream() << "array '" << dependency.fieldNameStringData()
                                  << "' in $jsonSchema keyword '"
                                  << kSchemaDependenciesKeyword
                                  << "' contains duplicate element: "
                                  << propertyDependency.valueStringData()};
        }

        auto propertyExistsExpr =
            makeDependencyExistsClause(path, propertyDependency.valueStringData());
        if (!propertyExistsExpr.isOK()) {
            return propertyExistsExpr.getStatus();
        }

        propertyDependencyExpr->add(propertyExistsExpr.getValue().release());
    }

    auto ifClause = makeDependencyExistsClause(path, dependency.fieldNameStringData());
    if (!ifClause.isOK()) {
        return ifClause.getStatus();
    }

    std::array<std::unique_ptr<MatchExpression>, 3> expressions = {
        {std::move(ifClause.getValue()),
         std::move(propertyDependencyExpr),
         stdx::make_unique<AlwaysTrueMatchExpression>()}};

    auto condExpr = stdx::make_unique<InternalSchemaCondMatchExpression>(std::move(expressions));
    return {std::move(condExpr)};
}

StatusWithMatchExpression parseDependencies(StringData path,
                                            BSONElement dependencies,
                                            bool ignoreUnknownKeywords) {
    if (dependencies.type() != BSONType::Object) {
        return {ErrorCodes::TypeMismatch,
                str::stream() << "$jsonSchema keyword '" << kSchemaDependenciesKeyword
                              << "' must be an object"};
    }

    auto andExpr = stdx::make_unique<AndMatchExpression>();
    for (auto&& dependency : dependencies.embeddedObject()) {
        if (dependency.type() != BSONType::Object && dependency.type() != BSONType::Array) {
            return {ErrorCodes::TypeMismatch,
                    str::stream() << "property '" << dependency.fieldNameStringData()
                                  << "' in $jsonSchema keyword '"
                                  << kSchemaDependenciesKeyword
                                  << "' must be either an object or an array"};
        }

        auto dependencyExpr = (dependency.type() == BSONType::Object)
            ? translateSchemaDependency(path, dependency, ignoreUnknownKeywords)
            : translatePropertyDependency(path, dependency);
        if (!dependencyExpr.isOK()) {
            return dependencyExpr.getStatus();
        }

        andExpr->add(dependencyExpr.getValue().release());
    }

    return {std::move(andExpr)};
}

StatusWithMatchExpression parseUniqueItems(BSONElement uniqueItemsElt,
                                           StringData path,
                                           InternalSchemaTypeExpression* typeExpr) {
    if (!uniqueItemsElt.isBoolean()) {
        return {ErrorCodes::TypeMismatch,
                str::stream() << "$jsonSchema keyword '" << kSchemaUniqueItemsKeyword
                              << "' must be a boolean"};
    } else if (path.empty()) {
        return {stdx::make_unique<AlwaysTrueMatchExpression>()};
    } else if (uniqueItemsElt.boolean()) {
        auto uniqueItemsExpr = stdx::make_unique<InternalSchemaUniqueItemsMatchExpression>(path);
        return makeRestriction(BSONType::Array, path, std::move(uniqueItemsExpr), typeExpr);
    }

    return {stdx::make_unique<AlwaysTrueMatchExpression>()};
}

/**
 * Parses 'itemsElt' into a match expression and adds it to 'andExpr'. On success, returns the index
 * from which the "additionalItems" schema should be enforced, if needed.
 */
StatusWith<boost::optional<long long>> parseItems(StringData path,
                                                  BSONElement itemsElt,
                                                  bool ignoreUnknownKeywords,
                                                  InternalSchemaTypeExpression* typeExpr,
                                                  AndMatchExpression* andExpr) {
    boost::optional<long long> startIndexForAdditionalItems;
    if (itemsElt.type() == BSONType::Array) {
        // When "items" is an array, generate match expressions for each subschema for each position
        // in the array, which are bundled together in an AndMatchExpression.
        auto andExprForSubschemas = stdx::make_unique<AndMatchExpression>();
        auto index = 0LL;
        for (auto subschema : itemsElt.embeddedObject()) {
            if (subschema.type() != BSONType::Object) {
                return {ErrorCodes::TypeMismatch,
                        str::stream() << "$jsonSchema keyword '" << kSchemaItemsKeyword
                                      << "' requires that each element of the array is an "
                                         "object, but found a "
                                      << subschema.type()};
            }

            // We want to make an ExpressionWithPlaceholder for $_internalSchemaMatchArrayIndex,
            // so we use our default placeholder as the path.
            auto parsedSubschema =
                _parse(kNamePlaceholder, subschema.embeddedObject(), ignoreUnknownKeywords);
            if (!parsedSubschema.isOK()) {
                return parsedSubschema.getStatus();
            }
            auto exprWithPlaceholder = stdx::make_unique<ExpressionWithPlaceholder>(
                kNamePlaceholder.toString(), std::move(parsedSubschema.getValue()));
            auto matchArrayIndex = stdx::make_unique<InternalSchemaMatchArrayIndexMatchExpression>(
                path, index, std::move(exprWithPlaceholder));
            andExprForSubschemas->add(matchArrayIndex.release());
            ++index;
        }
        startIndexForAdditionalItems = index;

        if (path.empty()) {
            andExpr->add(stdx::make_unique<AlwaysTrueMatchExpression>().release());
        } else {
            andExpr->add(
                makeRestriction(BSONType::Array, path, std::move(andExprForSubschemas), typeExpr)
                    .release());
        }
    } else if (itemsElt.type() == BSONType::Object) {
        // When "items" is an object, generate a single AllElemMatchFromIndex that applies to every
        // element in the array to match. The parsed expression is intended for an
        // ExpressionWithPlaceholder, so we use the default placeholder as the path.
        auto nestedItemsSchema =
            _parse(kNamePlaceholder, itemsElt.embeddedObject(), ignoreUnknownKeywords);
        if (!nestedItemsSchema.isOK()) {
            return nestedItemsSchema.getStatus();
        }
        auto exprWithPlaceholder = stdx::make_unique<ExpressionWithPlaceholder>(
            kNamePlaceholder.toString(), std::move(nestedItemsSchema.getValue()));

        if (path.empty()) {
            andExpr->add(stdx::make_unique<AlwaysTrueMatchExpression>().release());
        } else {
            constexpr auto startIndexForItems = 0LL;
            auto allElemMatch =
                stdx::make_unique<InternalSchemaAllElemMatchFromIndexMatchExpression>(
                    path, startIndexForItems, std::move(exprWithPlaceholder));
            andExpr->add(makeRestriction(BSONType::Array, path, std::move(allElemMatch), typeExpr)
                             .release());
        }
    } else {
        return {ErrorCodes::TypeMismatch,
                str::stream() << "$jsonSchema keyword '" << kSchemaItemsKeyword
                              << "' must be an array or an object, not "
                              << itemsElt.type()};
    }

    return startIndexForAdditionalItems;
}

Status parseAdditionalItems(StringData path,
                            BSONElement additionalItemsElt,
                            boost::optional<long long> startIndexForAdditionalItems,
                            bool ignoreUnknownKeywords,
                            InternalSchemaTypeExpression* typeExpr,
                            AndMatchExpression* andExpr) {
    std::unique_ptr<ExpressionWithPlaceholder> otherwiseExpr;
    if (additionalItemsElt.type() == BSONType::Bool) {
        const auto emptyPlaceholder = boost::none;
        if (additionalItemsElt.boolean()) {
            otherwiseExpr = stdx::make_unique<ExpressionWithPlaceholder>(
                emptyPlaceholder, stdx::make_unique<AlwaysTrueMatchExpression>());
        } else {
            otherwiseExpr = stdx::make_unique<ExpressionWithPlaceholder>(
                emptyPlaceholder, stdx::make_unique<AlwaysFalseMatchExpression>());
        }
    } else if (additionalItemsElt.type() == BSONType::Object) {
        auto parsedOtherwiseExpr =
            _parse(kNamePlaceholder, additionalItemsElt.embeddedObject(), ignoreUnknownKeywords);
        if (!parsedOtherwiseExpr.isOK()) {
            return parsedOtherwiseExpr.getStatus();
        }
        otherwiseExpr = stdx::make_unique<ExpressionWithPlaceholder>(
            kNamePlaceholder.toString(), std::move(parsedOtherwiseExpr.getValue()));
    } else {
        return {ErrorCodes::TypeMismatch,
                str::stream() << "$jsonSchema keyword '" << kSchemaAdditionalItemsKeyword
                              << "' must be either an object or a boolean, but got a "
                              << additionalItemsElt.type()};
    }

    // Only generate a match expression if needed.
    if (startIndexForAdditionalItems) {
        if (path.empty()) {
            andExpr->add(stdx::make_unique<AlwaysTrueMatchExpression>().release());
        } else {
            auto allElemMatch =
                stdx::make_unique<InternalSchemaAllElemMatchFromIndexMatchExpression>(
                    path, *startIndexForAdditionalItems, std::move(otherwiseExpr));
            andExpr->add(makeRestriction(BSONType::Array, path, std::move(allElemMatch), typeExpr)
                             .release());
        }
    }
    return Status::OK();
}

Status parseItemsAndAdditionalItems(StringMap<BSONElement>* keywordMap,
                                    StringData path,
                                    bool ignoreUnknownKeywords,
                                    InternalSchemaTypeExpression* typeExpr,
                                    AndMatchExpression* andExpr) {
    boost::optional<long long> startIndexForAdditionalItems;
    if (auto itemsElt = keywordMap->get(kSchemaItemsKeyword)) {
        auto index = parseItems(path, itemsElt, ignoreUnknownKeywords, typeExpr, andExpr);
        if (!index.isOK()) {
            return index.getStatus();
        }
        startIndexForAdditionalItems = index.getValue();
    }

    if (auto additionalItemsElt = keywordMap->get(kSchemaAdditionalItemsKeyword)) {
        return parseAdditionalItems(path,
                                    additionalItemsElt,
                                    startIndexForAdditionalItems,
                                    ignoreUnknownKeywords,
                                    typeExpr,
                                    andExpr);
    }
    return Status::OK();
}

/**
 * Parses the logical keywords in 'keywordMap' to their equivalent match expressions
 * and, on success, adds the results to 'andExpr'.
 *
 * This function parses the following keywords:
 *  - allOf
 *  - anyOf
 *  - oneOf
 *  - not
 *  - enum
 */
Status translateLogicalKeywords(StringMap<BSONElement>* keywordMap,
                                StringData path,
                                AndMatchExpression* andExpr,
                                bool ignoreUnknownKeywords) {
    if (auto allOfElt = keywordMap->get(kSchemaAllOfKeyword)) {
        auto allOfExpr =
            parseLogicalKeyword<AndMatchExpression>(path, allOfElt, ignoreUnknownKeywords);
        if (!allOfExpr.isOK()) {
            return allOfExpr.getStatus();
        }
        andExpr->add(allOfExpr.getValue().release());
    }

    if (auto anyOfElt = keywordMap->get(kSchemaAnyOfKeyword)) {
        auto anyOfExpr =
            parseLogicalKeyword<OrMatchExpression>(path, anyOfElt, ignoreUnknownKeywords);
        if (!anyOfExpr.isOK()) {
            return anyOfExpr.getStatus();
        }
        andExpr->add(anyOfExpr.getValue().release());
    }

    if (auto oneOfElt = keywordMap->get(kSchemaOneOfKeyword)) {
        auto oneOfExpr = parseLogicalKeyword<InternalSchemaXorMatchExpression>(
            path, oneOfElt, ignoreUnknownKeywords);
        if (!oneOfExpr.isOK()) {
            return oneOfExpr.getStatus();
        }
        andExpr->add(oneOfExpr.getValue().release());
    }

    if (auto notElt = keywordMap->get(kSchemaNotKeyword)) {
        if (notElt.type() != BSONType::Object) {
            return {ErrorCodes::TypeMismatch,
                    str::stream() << "$jsonSchema keyword '" << kSchemaNotKeyword
                                  << "' must be an object, but found an element of type "
                                  << notElt.type()};
        }

        auto parsedExpr = _parse(path, notElt.embeddedObject(), ignoreUnknownKeywords);
        if (!parsedExpr.isOK()) {
            return parsedExpr.getStatus();
        }

        auto notMatchExpr = stdx::make_unique<NotMatchExpression>(parsedExpr.getValue().release());
        andExpr->add(notMatchExpr.release());
    }

    if (auto enumElt = keywordMap->get(kSchemaEnumKeyword)) {
        auto enumExpr = parseEnum(path, enumElt);
        if (!enumExpr.isOK()) {
            return enumExpr.getStatus();
        }
        andExpr->add(enumExpr.getValue().release());
    }

    return Status::OK();
}

/**
 * Parses JSON Schema array keywords in 'keywordMap' and adds them to 'andExpr'. Returns a non-OK
 * status if an error occurs during parsing.
 *
 * This function parses the following keywords:
 *  - minItems
 *  - maxItems
 *  - uniqueItems
 *  - items
 *  - additionalItems
 */
Status translateArrayKeywords(StringMap<BSONElement>* keywordMap,
                              StringData path,
                              bool ignoreUnknownKeywords,
                              InternalSchemaTypeExpression* typeExpr,
                              AndMatchExpression* andExpr) {
    if (auto minItemsElt = keywordMap->get(kSchemaMinItemsKeyword)) {
        auto minItemsExpr = parseLength<InternalSchemaMinItemsMatchExpression>(
            path, minItemsElt, typeExpr, BSONType::Array);
        if (!minItemsExpr.isOK()) {
            return minItemsExpr.getStatus();
        }
        andExpr->add(minItemsExpr.getValue().release());
    }

    if (auto maxItemsElt = keywordMap->get(kSchemaMaxItemsKeyword)) {
        auto maxItemsExpr = parseLength<InternalSchemaMaxItemsMatchExpression>(
            path, maxItemsElt, typeExpr, BSONType::Array);
        if (!maxItemsExpr.isOK()) {
            return maxItemsExpr.getStatus();
        }
        andExpr->add(maxItemsExpr.getValue().release());
    }

    if (auto uniqueItemsElt = keywordMap->get(kSchemaUniqueItemsKeyword)) {
        auto uniqueItemsExpr = parseUniqueItems(uniqueItemsElt, path, typeExpr);
        if (!uniqueItemsExpr.isOK()) {
            return uniqueItemsExpr.getStatus();
        }
        andExpr->add(uniqueItemsExpr.getValue().release());
    }

    return parseItemsAndAdditionalItems(keywordMap, path, ignoreUnknownKeywords, typeExpr, andExpr);
}

/**
 * Parses JSON Schema keywords related to objects in 'keywordMap' and adds them to 'andExpr'.
 * Returns a non-OK status if an error occurs during parsing.
 *
 * This function parses the following keywords:
 *  - additionalProperties
 *  - dependencies
 *  - maxProperties
 *  - minProperties
 *  - patternProperties
 *  - properties
 *  - required
 */
Status translateObjectKeywords(StringMap<BSONElement>* keywordMap,
                               StringData path,
                               InternalSchemaTypeExpression* typeExpr,
                               AndMatchExpression* andExpr,
                               bool ignoreUnknownKeywords) {
    boost::container::flat_set<StringData> requiredProperties;
    if (auto requiredElt = keywordMap->get(kSchemaRequiredKeyword)) {
        auto requiredStatus = parseRequired(requiredElt);
        if (!requiredStatus.isOK()) {
            return requiredStatus.getStatus();
        }
        requiredProperties = std::move(requiredStatus.getValue());
    }

    if (auto propertiesElt = keywordMap->get(kSchemaPropertiesKeyword)) {
        auto propertiesExpr = parseProperties(
            path, propertiesElt, typeExpr, requiredProperties, ignoreUnknownKeywords);
        if (!propertiesExpr.isOK()) {
            return propertiesExpr.getStatus();
        }
        andExpr->add(propertiesExpr.getValue().release());
    }

    {
        auto propertiesElt = keywordMap->get(kSchemaPropertiesKeyword);
        auto patternPropertiesElt = keywordMap->get(kSchemaPatternPropertiesKeyword);
        auto additionalPropertiesElt = keywordMap->get(kSchemaAdditionalPropertiesKeyword);

        if (patternPropertiesElt || additionalPropertiesElt) {
            auto allowedPropertiesExpr = parseAllowedProperties(path,
                                                                propertiesElt,
                                                                patternPropertiesElt,
                                                                additionalPropertiesElt,
                                                                typeExpr,
                                                                ignoreUnknownKeywords);
            if (!allowedPropertiesExpr.isOK()) {
                return allowedPropertiesExpr.getStatus();
            }
            andExpr->add(allowedPropertiesExpr.getValue().release());
        }
    }

    if (!requiredProperties.empty()) {
        auto requiredExpr = translateRequired(requiredProperties, path, typeExpr);
        if (!requiredExpr.isOK()) {
            return requiredExpr.getStatus();
        }
        andExpr->add(requiredExpr.getValue().release());
    }

    if (auto minPropertiesElt = keywordMap->get(kSchemaMinPropertiesKeyword)) {
        auto minPropExpr = parseNumProperties<InternalSchemaMinPropertiesMatchExpression>(
            path, minPropertiesElt, typeExpr);
        if (!minPropExpr.isOK()) {
            return minPropExpr.getStatus();
        }
        andExpr->add(minPropExpr.getValue().release());
    }

    if (auto maxPropertiesElt = keywordMap->get(kSchemaMaxPropertiesKeyword)) {
        auto maxPropExpr = parseNumProperties<InternalSchemaMaxPropertiesMatchExpression>(
            path, maxPropertiesElt, typeExpr);
        if (!maxPropExpr.isOK()) {
            return maxPropExpr.getStatus();
        }
        andExpr->add(maxPropExpr.getValue().release());
    }

    if (auto dependenciesElt = keywordMap->get(kSchemaDependenciesKeyword)) {
        auto dependenciesExpr = parseDependencies(path, dependenciesElt, ignoreUnknownKeywords);
        if (!dependenciesExpr.isOK()) {
            return dependenciesExpr.getStatus();
        }
        andExpr->add(dependenciesExpr.getValue().release());
    }

    return Status::OK();
}

/**
 * Parses JSON Schema scalar keywords in 'keywordMap' and adds them to 'andExpr'. Returns a non-OK
 * status if an error occurs during parsing.
 *
 * This function parses the following keywords:
 *  - minimum
 *  - exclusiveMinimum
 *  - maximum
 *  - exclusiveMaximum
 *  - minLength
 *  - maxLength
 *  - pattern
 */
Status translateScalarKeywords(StringMap<BSONElement>* keywordMap,
                               StringData path,
                               InternalSchemaTypeExpression* typeExpr,
                               AndMatchExpression* andExpr) {
    // String keywords.
    if (auto patternElt = keywordMap->get(kSchemaPatternKeyword)) {
        auto patternExpr = parsePattern(path, patternElt, typeExpr);
        if (!patternExpr.isOK()) {
            return patternExpr.getStatus();
        }
        andExpr->add(patternExpr.getValue().release());
    }

    if (auto maxLengthElt = keywordMap->get(kSchemaMaxLengthKeyword)) {
        auto maxLengthExpr = parseLength<InternalSchemaMaxLengthMatchExpression>(
            path, maxLengthElt, typeExpr, BSONType::String);
        if (!maxLengthExpr.isOK()) {
            return maxLengthExpr.getStatus();
        }
        andExpr->add(maxLengthExpr.getValue().release());
    }

    if (auto minLengthElt = keywordMap->get(kSchemaMinLengthKeyword)) {
        auto minLengthExpr = parseLength<InternalSchemaMinLengthMatchExpression>(
            path, minLengthElt, typeExpr, BSONType::String);
        if (!minLengthExpr.isOK()) {
            return minLengthExpr.getStatus();
        }
        andExpr->add(minLengthExpr.getValue().release());
    }

    // Numeric keywords.
    if (auto multipleOfElt = keywordMap->get(kSchemaMultipleOfKeyword)) {
        auto multipleOfExpr = parseMultipleOf(path, multipleOfElt, typeExpr);
        if (!multipleOfExpr.isOK()) {
            return multipleOfExpr.getStatus();
        }
        andExpr->add(multipleOfExpr.getValue().release());
    }

    if (auto maximumElt = keywordMap->get(kSchemaMaximumKeyword)) {
        bool isExclusiveMaximum = false;
        if (auto exclusiveMaximumElt = keywordMap->get(kSchemaExclusiveMaximumKeyword)) {
            if (!exclusiveMaximumElt.isBoolean()) {
                return {Status(ErrorCodes::TypeMismatch,
                               str::stream() << "$jsonSchema keyword '"
                                             << kSchemaExclusiveMaximumKeyword
                                             << "' must be a boolean")};
            } else {
                isExclusiveMaximum = exclusiveMaximumElt.boolean();
            }
        }
        auto maxExpr = parseMaximum(path, maximumElt, typeExpr, isExclusiveMaximum);
        if (!maxExpr.isOK()) {
            return maxExpr.getStatus();
        }
        andExpr->add(maxExpr.getValue().release());
    } else if (keywordMap->get(kSchemaExclusiveMaximumKeyword)) {
        // If "exclusiveMaximum" is present, "maximum" must also be present.
        return {ErrorCodes::FailedToParse,
                str::stream() << "$jsonSchema keyword '" << kSchemaMaximumKeyword
                              << "' must be a present if "
                              << kSchemaExclusiveMaximumKeyword
                              << " is present"};
    }

    if (auto minimumElt = keywordMap->get(kSchemaMinimumKeyword)) {
        bool isExclusiveMinimum = false;
        if (auto exclusiveMinimumElt = keywordMap->get(kSchemaExclusiveMinimumKeyword)) {
            if (!exclusiveMinimumElt.isBoolean()) {
                return {ErrorCodes::TypeMismatch,
                        str::stream() << "$jsonSchema keyword '" << kSchemaExclusiveMinimumKeyword
                                      << "' must be a boolean"};
            } else {
                isExclusiveMinimum = exclusiveMinimumElt.boolean();
            }
        }
        auto minExpr = parseMinimum(path, minimumElt, typeExpr, isExclusiveMinimum);
        if (!minExpr.isOK()) {
            return minExpr.getStatus();
        }
        andExpr->add(minExpr.getValue().release());
    } else if (keywordMap->get(kSchemaExclusiveMinimumKeyword)) {
        // If "exclusiveMinimum" is present, "minimum" must also be present.
        return {ErrorCodes::FailedToParse,
                str::stream() << "$jsonSchema keyword '" << kSchemaMinimumKeyword
                              << "' must be a present if "
                              << kSchemaExclusiveMinimumKeyword
                              << " is present"};
    }

    return Status::OK();
}

/**
 * Validates that the following metadata keywords have the correct type:
 *  - description
 *  - title
 */
Status validateMetadataKeywords(StringMap<BSONElement>* keywordMap) {
    if (auto descriptionElem = keywordMap->get(kSchemaDescriptionKeyword)) {
        if (descriptionElem.type() != BSONType::String) {
            return Status(ErrorCodes::TypeMismatch,
                          str::stream() << "$jsonSchema keyword '" << kSchemaDescriptionKeyword
                                        << "' must be of type string");
        }
    }

    if (auto titleElem = keywordMap->get(kSchemaTitleKeyword)) {
        if (titleElem.type() != BSONType::String) {
            return Status(ErrorCodes::TypeMismatch,
                          str::stream() << "$jsonSchema keyword '" << kSchemaTitleKeyword
                                        << "' must be of type string");
        }
    }
    return Status::OK();
}

StatusWithMatchExpression _parse(StringData path, BSONObj schema, bool ignoreUnknownKeywords) {
    // Map from JSON Schema keyword to the corresponding element from 'schema', or to an empty
    // BSONElement if the JSON Schema keyword is not specified.
    StringMap<BSONElement> keywordMap{
        {kSchemaAdditionalItemsKeyword, {}},
        {kSchemaAdditionalPropertiesKeyword, {}},
        {kSchemaAllOfKeyword, {}},
        {kSchemaAnyOfKeyword, {}},
        {kSchemaBsonTypeKeyword, {}},
        {kSchemaDependenciesKeyword, {}},
        {kSchemaDescriptionKeyword, {}},
        {kSchemaEnumKeyword, {}},
        {kSchemaExclusiveMaximumKeyword, {}},
        {kSchemaExclusiveMinimumKeyword, {}},
        {kSchemaItemsKeyword, {}},
        {kSchemaMaxItemsKeyword, {}},
        {kSchemaMaxLengthKeyword, {}},
        {kSchemaMaxPropertiesKeyword, {}},
        {kSchemaMaximumKeyword, {}},
        {kSchemaMinItemsKeyword, {}},
        {kSchemaMinLengthKeyword, {}},
        {kSchemaMinPropertiesKeyword, {}},
        {kSchemaMinimumKeyword, {}},
        {kSchemaMultipleOfKeyword, {}},
        {kSchemaNotKeyword, {}},
        {kSchemaOneOfKeyword, {}},
        {kSchemaPatternKeyword, {}},
        {kSchemaPatternPropertiesKeyword, {}},
        {kSchemaPropertiesKeyword, {}},
        {kSchemaRequiredKeyword, {}},
        {kSchemaTitleKeyword, {}},
        {kSchemaTypeKeyword, {}},
        {kSchemaUniqueItemsKeyword, {}},
    };

    for (auto&& elt : schema) {
        auto it = keywordMap.find(elt.fieldNameStringData());
        if (it == keywordMap.end()) {
            if (unsupportedKeywords.find(elt.fieldNameStringData()) != unsupportedKeywords.end()) {
                return Status(ErrorCodes::FailedToParse,
                              str::stream() << "$jsonSchema keyword '" << elt.fieldNameStringData()
                                            << "' is not currently supported");
            } else if (!ignoreUnknownKeywords) {
                return Status(ErrorCodes::FailedToParse,
                              str::stream() << "Unknown $jsonSchema keyword: "
                                            << elt.fieldNameStringData());
            }
            continue;
        }

        if (it->second) {
            return Status(ErrorCodes::FailedToParse,
                          str::stream() << "Duplicate $jsonSchema keyword: "
                                        << elt.fieldNameStringData());
        }

        keywordMap[elt.fieldNameStringData()] = elt;
    }

    auto metadataStatus = validateMetadataKeywords(&keywordMap);
    if (!metadataStatus.isOK()) {
        return metadataStatus;
    }

    auto typeElem = keywordMap[kSchemaTypeKeyword];
    auto bsonTypeElem = keywordMap[kSchemaBsonTypeKeyword];
    if (typeElem && bsonTypeElem) {
        return Status(ErrorCodes::FailedToParse,
                      str::stream() << "Cannot specify both $jsonSchema keywords '"
                                    << kSchemaTypeKeyword
                                    << "' and '"
                                    << kSchemaBsonTypeKeyword
                                    << "'");
    }

    std::unique_ptr<InternalSchemaTypeExpression> typeExpr;
    if (typeElem) {
        auto parseTypeResult =
            parseType(path, kSchemaTypeKeyword, typeElem, MatcherTypeSet::kJsonSchemaTypeAliasMap);
        if (!parseTypeResult.isOK()) {
            return parseTypeResult.getStatus();
        }
        typeExpr = std::move(parseTypeResult.getValue());
    } else if (bsonTypeElem) {
        auto parseBsonTypeResult =
            parseType(path, kSchemaBsonTypeKeyword, bsonTypeElem, MatcherTypeSet::kTypeAliasMap);
        if (!parseBsonTypeResult.isOK()) {
            return parseBsonTypeResult.getStatus();
        }
        typeExpr = std::move(parseBsonTypeResult.getValue());
    }

    auto andExpr = stdx::make_unique<AndMatchExpression>();

    auto translationStatus =
        translateScalarKeywords(&keywordMap, path, typeExpr.get(), andExpr.get());
    if (!translationStatus.isOK()) {
        return translationStatus;
    }

    translationStatus = translateArrayKeywords(
        &keywordMap, path, ignoreUnknownKeywords, typeExpr.get(), andExpr.get());
    if (!translationStatus.isOK()) {
        return translationStatus;
    }

    translationStatus = translateObjectKeywords(
        &keywordMap, path, typeExpr.get(), andExpr.get(), ignoreUnknownKeywords);
    if (!translationStatus.isOK()) {
        return translationStatus;
    }

    translationStatus =
        translateLogicalKeywords(&keywordMap, path, andExpr.get(), ignoreUnknownKeywords);
    if (!translationStatus.isOK()) {
        return translationStatus;
    }

    if (path.empty() && typeExpr && !typeExpr->typeSet().hasType(BSONType::Object)) {
        // This is a top-level schema which requires that the type is something other than
        // "object". Since we only know how to store objects, this schema matches nothing.
        return {stdx::make_unique<AlwaysFalseMatchExpression>()};
    }

    if (!path.empty() && typeExpr) {
        andExpr->add(typeExpr.release());
    }
    return {std::move(andExpr)};
}
}  // namespace

constexpr StringData JSONSchemaParser::kSchemaTypeArray;
constexpr StringData JSONSchemaParser::kSchemaTypeBoolean;
constexpr StringData JSONSchemaParser::kSchemaTypeInteger;
constexpr StringData JSONSchemaParser::kSchemaTypeNull;
constexpr StringData JSONSchemaParser::kSchemaTypeObject;
constexpr StringData JSONSchemaParser::kSchemaTypeString;

StatusWithMatchExpression JSONSchemaParser::parse(BSONObj schema, bool ignoreUnknownKeywords) {
    LOG(5) << "Parsing JSON Schema: " << schema.jsonString();
    try {
        auto translation = _parse(""_sd, schema, ignoreUnknownKeywords);
        if (shouldLog(logger::LogSeverity::Debug(5)) && translation.isOK()) {
            LOG(5) << "Translated schema match expression: " << translation.getValue()->toString();
        }
        return translation;
    } catch (const DBException& ex) {
        return {ex.toStatus()};
    }
}
}  // namespace mongo

max_stars_repo_name: BlakeIsBlake/mongo

max_issues_repo_name: BlakeIsBlake/mongo

max_forks_repo_name: BlakeIsBlake/mongo


text:
// Copyright 2009 (c) Tarro, Inc.
// Copyright 2009 (c) Dean Michael Berris <mikhailberis@gmail.com>
// Copyright 2003-2008 (c) Chris Kholhoff
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//

#ifndef BOOST_NETWORK_HTTP_SERVER_HPP_
#define BOOST_NETWORK_HTTP_SERVER_HPP_

#include <boost/shared_ptr.hpp>
#include <boost/bind.hpp>
#include <string>
#include <boost/asio.hpp>
#include <boost/network/protocol/http/connection.hpp>

namespace boost { namespace network { namespace http {

    using boost::shared_ptr;
    using std::string;
    using boost::asio::ip::tcp;
    using boost::bind;

    template <class Tag, class Handler>
    struct basic_server {
        typedef basic_request<Tag> request;
        typedef basic_response<Tag> response;

        basic_server(string const & address, string const & port, Handler & handler)
        : handler_(handler)
        , service_()
        , acceptor_(service_)
        , new_connection(new connection<Tag,Handler>(service_, handler))
        {
            tcp::resolver resolver(service_);
            tcp::resolver::query query(address, port);
            tcp::endpoint endpoint = *resolver.resolve(query);
            acceptor_.open(endpoint.protocol());
            acceptor_.set_option(tcp::acceptor::reuse_address(true));
            acceptor_.bind(endpoint);
            acceptor_.listen();
            acceptor_.async_accept(new_connection->socket(),
                bind(&basic_server<Tag,Handler>::handle_accept, this, boost::asio::placeholders::error));
        }

        void run() {
            service_.run();
        }

        void stop() {
            // TODO Graceful stop here?
            service_.stop();
        }

        private:

        Handler & handler_;
        io_service service_;
        tcp::acceptor acceptor_;
        shared_ptr<connection<Tag,Handler> > new_connection;

        void handle_accept(boost::system::error_code const & ec) {
            if (!ec) {
                new_connection->start();
                new_connection.reset(new connection<Tag,Handler>(service_, handler_));
                acceptor_.async_accept(new_connection->socket(),
                    bind(&basic_server<Tag,Handler>::handle_accept, this, boost::asio::placeholders::error));
            }
        }
    };

    template <class Handler>
    struct server : basic_server<tags::http_server, Handler> {
        server(string const & address, string const & port, Handler & handler)
        : basic_server<tags::http_server,Handler>(address, port, handler) {}

        typedef typename basic_server<tags::http_server,Handler>::request request;
        typedef typename basic_server<tags::http_server,Handler>::response response;
    };

} // namespace http

} // namespace network

} // namespace boost

#endif // BOOST_NETWORK_HTTP_SERVER_HPP_

ext: hpp

max_stars_repo_name: mclow/cpp-netlib

max_issues_repo_name: mclow/cpp-netlib

max_forks_repo_name: mclow/cpp-netlib


text:
//
// Copyright (c) 2015-2017, Deutsches Forschungszentrum für Künstliche Intelligenz GmbH.
// Copyright (c) 2015-2017, University of Bremen
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice, this
//   list of conditions and the following disclaimer.
//
// * Redistributions in binary form must reproduce the above copyright notice,
//   this list of conditions and the following disclaimer in the documentation
//   and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
#define BOOST_TEST_MODULE VizTest
#include <boost/test/included/unit_test.hpp>
#include <boost/archive/polymorphic_binary_oarchive.hpp>

#include <Eigen/Geometry>

#include "StandaloneVisualizer.hpp"
#include <maps/grid/MLSMap.hpp>

#include <maps/operations/CoverageMapGeneration.hpp>

using namespace ::maps::grid;

template<class MLSMap>
static void show_MLS(const MLSMap& mls)
{
    std::cout << "update finish" << std::endl;
    StandaloneVisualizer app;
    app.updateData(mls);

    while (app.wait(1000))
    {
    }
}

BOOST_AUTO_TEST_CASE(mls_coverage)
{
    //    GridConfig conf(150, 150, 0.1, 0.1, -7.5, -7.5);
    Eigen::Vector2d res(0.1, 0.1);
    Vector2ui numCells(150, 150);

    MLSConfig mls_config;
    mls_config.updateModel = MLSConfig::KALMAN;
    mls_config.gapSize = 0.05f;
    mls_config.useNegativeInformation = false;
    MLSMapKalman mls(numCells, res, mls_config);

    maps::operations::CoverageTracker coverage;

    mls.getLocalFrame().translation() << 0.5*mls.getSize(), 0;

    coverage.setFrame(mls);

    StandaloneVisualizer app;

    Eigen::ArrayXXd ranges;
    PointCloud pointcloud;
    base::Pose trafo;
    int loop = 0;
    while (app.wait(1000))
    {
        if(++loop & 1023) continue;
        trafo.position +=Eigen::Vector3d::Random() * 0.5;
        Eigen::Quaterniond q; q.coeffs().setRandom(); q.normalize();
        trafo.orientation = q;

        coverage.addCoverage(2.0, base::AngleSegment(), trafo);

        app.updateData(coverage.getCoverage());
    }
}

ext: cpp

max_stars_repo_name: skasperski/slam-maps

max_issues_repo_name: skasperski/slam-maps

max_forks_repo_name: skasperski/slam-maps


text:
#include <ros/ros.h>
#include <vector>
#include <math.h>
#include <sensor_msgs/PointCloud2.h>
#include <pcl_ros/point_cloud.h>
#include <pcl/point_types.h>
#include <pcl/sample_consensus/method_types.h>
#include <pcl/sample_consensus/model_types.h>
#include <pcl/sample_consensus/ransac.h>
#include <pcl/sample_consensus/sac_model_plane.h>
#include <pcl/segmentation/sac_segmentation.h>
#include <pcl/segmentation/extract_clusters.h>
#include <boost/foreach.hpp>
#include <pcl/visualization/pcl_visualizer.h>
#include <boost/thread/thread.hpp>
#include <pcl/ModelCoefficients.h>
#include <pcl/filters/extract_indices.h>
#include <pcl/filters/voxel_grid.h>
#include <pcl/features/normal_3d.h>
#include <pcl/features/moment_of_inertia_estimation.h>
#include <pcl/kdtree/kdtree.h>
#include <std_msgs/String.h>
#include <sstream>

typedef pcl::PointCloud<pcl::PointXYZRGB> PointCloud;

void callback(const PointCloud::ConstPtr& msg)
{
  ros::NodeHandle n;
  ros::Publisher pub = n.advertise<std_msgs::String>("/kinect_data",100);
  ROS_INFO("I heard: [%d] [%d]",msg->width, msg->height);
  boost::shared_ptr<pcl::visualization::PCLVisualizer> viewer;
  pcl::VoxelGrid<pcl::PointXYZRGB> vg;
  pcl::PointCloud<pcl::PointXYZRGB>::Ptr filtered (new pcl::PointCloud<pcl::PointXYZRGB>());
  vg.setInputCloud(msg);
  vg.setLeafSize(0.03f, 0.03f, 0.03f);
  vg.filter(*filtered);
  pcl::PointCloud<pcl::PointXYZRGB>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZRGB>);
  std::vector<int> inl;
  pcl::SampleConsensusModelPlane<pcl::PointXYZRGB>::Ptr model_p(new pcl::SampleConsensusModelPlane<pcl::PointXYZRGB> (filtered));
  pcl::RandomSampleConsensus<pcl::PointXYZRGB> ransac(model_p);
  ransac.setDistanceThreshold(0.05);
  ransac.computeModel();
  ransac.getInliers(inl);
  pcl::copyPointCloud<pcl::PointXYZRGB>(*filtered, inl, *cloud);
  pcl::ModelCoefficients::Ptr coefficients (new pcl::ModelCoefficients);
  pcl::PointIndices::Ptr inliers (new pcl::PointIndices);
  pcl::SACSegmentation<pcl::PointXYZRGB> seg;
  pcl::PointCloud<pcl::PointXYZRGB>::Ptr cloud_plane (new pcl::PointCloud<pcl::PointXYZRGB> ()), cloud_f (new pcl::PointCloud<pcl::PointXYZRGB>);
  seg.setOptimizeCoefficients(true);
  seg.setModelType(pcl::SACMODEL_PLANE);
  seg.setMethodType(pcl::SAC_RANSAC);
  //seg.setMaxIterations (100);
  seg.setDistanceThreshold(0.05);
  int i = 0, nr_points = (int)filtered->points.size();
  while(filtered->points.size() > 0.4*nr_points)
  {
    seg.setInputCloud(filtered);
    seg.segment(*inliers, *coefficients);
    pcl::ExtractIndices<pcl::PointXYZRGB> extract;
    extract.setInputCloud(filtered);
    extract.setIndices(inliers);
    extract.setNegative(false);
    extract.filter (*cloud_plane);
    extract.setNegative (true);
    extract.filter (*cloud_f);
    *filtered = *cloud_f;
  }
  // Creating the KdTree object for the search method of the extraction
  pcl::search::KdTree<pcl::PointXYZRGB>::Ptr tree (new pcl::search::KdTree<pcl::PointXYZRGB>);
  tree->setInputCloud (filtered);
  std::vector<pcl::PointIndices> cluster_indices;
  pcl::EuclideanClusterExtraction<pcl::PointXYZRGB> ec;
  ec.setClusterTolerance (0.03); // 2cm
  ec.setMinClusterSize (50);
  ec.setMaxClusterSize (10000);
  ec.setSearchMethod (tree);
  ec.setInputCloud (filtered);
  ec.extract (cluster_indices);
  pcl::PointCloud<pcl::PointXYZRGB>::Ptr cloud_cluster (new pcl::PointCloud<pcl::PointXYZRGB>);
  int j = 0;
  std::vector<std::vector<float> > moi, xcor;
  for (std::vector<pcl::PointIndices>::const_iterator it = cluster_indices.begin (); it != cluster_indices.end (); ++it)
  {
    j++;
    pcl::PointCloud<pcl::PointXYZRGB>::Ptr clusters (new pcl::PointCloud<pcl::PointXYZRGB>);
    for (std::vector<int>::const_iterator pit = it->indices.begin (); pit != it->indices.end (); ++pit)
    {
      clusters->points.push_back (filtered->points[*pit]); //*
      cloud_cluster->points.push_back (filtered->points[*pit]); //*
    }
    pcl::MomentOfInertiaEstimation <pcl::PointXYZRGB> feature_extractor;
    feature_extractor.setInputCloud (clusters);
    feature_extractor.compute ();
    std::vector <float> moment_of_inertia;
    std::vector <float> eccentricity;
    pcl::PointXYZRGB min_point_AABB;
    pcl::PointXYZRGB max_point_AABB;
    pcl::PointXYZRGB min_point_OBB;
    pcl::PointXYZRGB max_point_OBB;
    pcl::PointXYZRGB position_OBB;
    Eigen::Matrix3f rotational_matrix_OBB;
    float major_value, middle_value, minor_value;
    Eigen::Vector3f major_vector, middle_vector, minor_vector;
    Eigen::Vector3f mass_center;
    feature_extractor.getMomentOfInertia (moment_of_inertia);
    feature_extractor.getEccentricity (eccentricity);
    feature_extractor.getAABB (min_point_AABB, max_point_AABB);
    feature_extractor.getOBB (min_point_OBB, max_point_OBB, position_OBB, rotational_matrix_OBB);
    feature_extractor.getEigenValues (major_value, middle_value, minor_value);
    feature_extractor.getEigenVectors (major_vector, middle_vector, minor_vector);
    feature_extractor.getMassCenter (mass_center);
    std::vector<float> row1;
    for(int k=0;k<2;k++)
      row1.push_back(mass_center[k]);
    moi.push_back(row1);
    std::vector<float> row2;
    row2.push_back(min_point_AABB.x);
    row2.push_back(max_point_AABB.x);
    row2.push_back(min_point_AABB.z);
    row2.push_back(max_point_AABB.z);
    row2.push_back(min_point_AABB.y);
    row2.push_back(max_point_AABB.y);
    xcor.push_back(row2);
  }
  std::cout<<endl<<j<<endl;
  std::stringstream ss;
  std_msgs::String kin_val;
  for(int i=0; i<j; i++)
      {
        if(xcor[i][2]<2.0 && xcor[i][5]-xcor[i][4]>0.15)
        {
          if(moi[i][0]>=0)
	  {
            std::cout<<"left\n";
	    ss << "left";
            kin_val.data = ss.str();
	    goto label;
	  }
          else
	  {
            std::cout<<"right\n";
	    ss << "right";
            kin_val.data = ss.str();
	    goto label;
	  }
        }
       }
	std::cout<<"straight\n";
	ss << "straight";
  	kin_val.data = ss.str();
      label:
	pub.publish(kin_val);
}

int main(int argc, char **argv)
{
  ros::init(argc, argv, "obs_av");
  ros::NodeHandle n;
  ros::Subscriber sub = n.subscribe("/camera/depth/color/points", 1, callback);
  ros::spin();
  return 0;
}


text:
#include <boost/asio.hpp>

using namespace boost;

int main()
{
	// Step 1. Allocate simple buffers.
	char part1[6];
	char part2[3];
	char part3[7];

	// Step 2. Create an object representing a composite buffer.
	std::vector<asio::mutable_buffer> composite_buffer;

	// Step 3. Add simple buffers to the composite buffer object.
	composite_buffer.push_back(asio::mutable_buffer(part1,
		sizeof(part1)));
	composite_buffer.push_back(asio::mutable_buffer(part2,
		sizeof(part2)));
	composite_buffer.push_back(asio::mutable_buffer(part3,
		sizeof(part3)));

	// Now composite_buffer can be used with Boost.Asio
	// input operation as if it was a simple buffer
	// represented by contiguous block of memory.

	return 0;
}

max_stars_repo_name: sinomiko/project

max_issues_repo_name: sinomiko/project

max_forks_repo_name: sinomiko/project


text:
#pragma once

#include <ysu/lib/utility.hpp>
#include <ysu/node/common.hpp>
#include <ysu/secure/common.hpp>

#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index_container.hpp>

#include <functional>
#include <memory>

namespace mi = boost::multi_index;

namespace ysu
{
class network;
class alarm;
class worker;
class stat;
namespace transport
{
	class channel;
}

/*
 * Holds a response from a telemetry request
 */
class telemetry_data_response
{
public:
	ysu::telemetry_data telemetry_data;
	ysu::endpoint endpoint;
	bool error{ true };
};

class telemetry_info final
{
public:
	telemetry_info () = default;
	telemetry_info (ysu::endpoint const & endpoint, ysu::telemetry_data const & data, std::chrono::steady_clock::time_point last_response, bool undergoing_request);
	bool awaiting_first_response () const;

	ysu::endpoint endpoint;
	ysu::telemetry_data data;
	std::chrono::steady_clock::time_point last_response;
	bool undergoing_request{ false };
	uint64_t round{ 0 };
};

/*
 * This class requests node telemetry metrics from peers and invokes any callbacks which have been aggregated.
 * All calls to get_metrics return cached data, it does not do any requests, these are periodically done in
 * ongoing_req_all_peers. This can be disabled with the disable_ongoing_telemetry_requests node flag.
 * Calls to get_metrics_single_peer_async will wait until a response is made if it is not within the cache
 * cut off.
 */
class telemetry : public std::enable_shared_from_this<telemetry>
{
public:
	telemetry (ysu::network &, ysu::alarm &, ysu::worker &, ysu::observer_set<ysu::telemetry_data const &, ysu::endpoint const &> &, ysu::stat &, ysu::network_params &, bool);
	void start ();
	void stop ();

	/*
	 * Received telemetry metrics from this peer
	 */
	void set (ysu::telemetry_ack const &, ysu::transport::channel const &);

	/*
	 * This returns what ever is in the cache
	 */
	std::unordered_map<ysu::endpoint, ysu::telemetry_data> get_metrics ();

	/*
	 * This makes a telemetry request to the specific channel.
	 * Error is set for: no response received, no payload received, invalid signature or unsound metrics in message (e.g different genesis block)
	 */
	void get_metrics_single_peer_async (std::shared_ptr<ysu::transport::channel> const &, std::function<void(telemetry_data_response const &)> const &);

	/*
	 * A blocking version of get_metrics_single_peer_async
	 */
	telemetry_data_response get_metrics_single_peer (std::shared_ptr<ysu::transport::channel> const &);

	/*
	 * Return the number of node metrics collected
	 */
	size_t telemetry_data_size ();

	/*
	 * Returns the time for the cache, response and a small buffer for alarm operations to be scheduled and completed
	 */
	std::chrono::milliseconds cache_plus_buffer_cutoff_time () const;

private:
	class tag_endpoint
	{
	};
	class tag_last_updated
	{
	};

	ysu::network & network;
	ysu::alarm & alarm;
	ysu::worker & worker;
	ysu::observer_set<ysu::telemetry_data const &, ysu::endpoint const &> & observers;
	ysu::stat & stats;
	/* Important that this is a reference to the node network_params for tests which want to modify genesis block */
	ysu::network_params & network_params;
	bool disable_ongoing_requests;

	std::atomic<bool> stopped{ false };

	std::mutex mutex;
	// clang-format off
	// This holds the last telemetry data received from peers or can be a placeholder awaiting the first response (check with awaiting_first_response ())
	boost::multi_index_container<ysu::telemetry_info,
	mi::indexed_by<
		mi::hashed_unique<mi::tag<tag_endpoint>,
			mi::member<ysu::telemetry_info, ysu::endpoint, &ysu::telemetry_info::endpoint>>,
		mi::ordered_non_unique<mi::tag<tag_last_updated>,
			mi::member<ysu::telemetry_info, std::chrono::steady_clock::time_point, &ysu::telemetry_info::last_response>>>> recent_or_initial_request_telemetry_data;
	// clang-format on

	// Anything older than this requires requesting metrics from other nodes.
	std::chrono::seconds const cache_cutoff{ ysu::telemetry_cache_cutoffs::network_to_time (network_params.network) };

	// The maximum time spent waiting for a response to a telemetry request
	std::chrono::seconds const response_time_cutoff{ network_params.network.is_dev_network () ? (is_sanitizer_build || ysu::running_within_valgrind () ? 6 : 3) : 10 };

	std::unordered_map<ysu::endpoint, std::vector<std::function<void(telemetry_data_response const &)>>> callbacks;

	void ongoing_req_all_peers (std::chrono::milliseconds);

	void fire_request_message (std::shared_ptr<ysu::transport::channel> const &);
	void channel_processed (ysu::endpoint const &, bool);
	void flush_callbacks_async (ysu::endpoint const &, bool);
	void invoke_callbacks (ysu::endpoint const &, bool);

	bool within_cache_cutoff (ysu::telemetry_info const &) const;
	bool within_cache_plus_buffer_cutoff (telemetry_info const &) const;
	bool verify_message (ysu::telemetry_ack const &, ysu::transport::channel const &);
	friend std::unique_ptr<ysu::container_info_component> collect_container_info (telemetry &, const std::string &);
	friend class telemetry_remove_peer_invalid_signature_Test;
};

std::unique_ptr<ysu::container_info_component> collect_container_info (telemetry & telemetry, const std::string & name);

ysu::telemetry_data consolidate_telemetry_data (std::vector<telemetry_data> const & telemetry_data);
ysu::telemetry_data local_telemetry_data (ysu::block_store &, ysu::ledger_cache const &, ysu::network &, uint64_t, ysu::network_params const &, std::chrono::steady_clock::time_point, uint64_t, ysu::keypair const &);
}


text:
/**
 * @file
 *
 * @brief Implementation of the functions to help reading and writing file for the projects.
 *
 * @author Hendrix Demers <hendrix.demers@mail.mcgill.ca>
 * @since 1.0
 */

// Copyright 2016 Hendrix Demers
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.

// C system headers
// C++ system header
#include <string>
// Library headers
#include <boost/algorithm/string.hpp>
#include <boost/lexical_cast.hpp>
// Precompiled header
#pragma hdrstop
// Current declaration header file of this implementation file.
#include "tools/tools_io.h"
// Project headers
// Project private headers

// Global and constant variables/functions.

double extractDoubleValueFromString(std::string &itemStr)
{
    boost::trim(itemStr);
    const std::string stringValue = itemStr;
    const double value = boost::lexical_cast<double>(stringValue);
    return value;
}

int extractIntegerValueFromString(std::string &itemStr)
{
    boost::trim(itemStr);
    const std::string stringValue = itemStr;
    const int value = boost::lexical_cast<int>(stringValue);
    return value;
}


text:
/**
 * Code to compress an existing DiskVectorLMDB store
 * (c) Rohit Girdhar
 */

#include <chrono>
#include <fstream>
#include <iostream>
#include <boost/program_options.hpp>
#include <boost/filesystem.hpp>
#include "../DiskVectorLMDB.hpp"

using namespace std;
using namespace std::chrono;
namespace po = boost::program_options;
namespace fs = boost::filesystem;

int
main(int argc, char *argv[]) {
  google::InitGoogleLogging(argv[0]);

  po::options_description desc("Allowed options");
  desc.add_options()
    ("help,h", "Show this help")
    ("infeatstor,i", po::value<fs::path>()->required(),
     "Path to feature store to compress")
    ("outfeatstor,o", po::value<fs::path>()->required(),
     "Path to output feature store")
    ("keyslist,k", po::value<fs::path>()->required(),
     "File with images list")
    ("startpos,s", po::value<unsigned long long>()->default_value(1),
     "Position to start reading the file [1 indexed]")
    ;

  po::variables_map vm;
  po::store(po::command_line_parser(argc, argv).options(desc).run(), vm);
  if (vm.count("help")) {
    LOG(INFO) << desc;
    return -1;
  }
  try {
    po::notify(vm);
  } catch(po::error& e) {
    LOG(ERROR) << e.what();
    return -1;
  }

  unsigned long long start_pos = vm["startpos"].as<unsigned long long>();
  fs::path infeatstor_fpath = vm["infeatstor"].as<fs::path>();
  fs::path outfeatstor_fpath = vm["outfeatstor"].as<fs::path>();
  auto infeatstor = std::shared_ptr<DiskVectorLMDB<vector<float>>>(
      new DiskVectorLMDB<vector<float>>(infeatstor_fpath.string(),
        /* readonly= */ 1,
        /* compress= */ 0));
  auto outfeatstor = std::shared_ptr<DiskVectorLMDB<vector<float>>>(
      new DiskVectorLMDB<vector<float>>(outfeatstor_fpath.string(),
        /* readonly= */ 0,
        /* compress= */ 1));

  ifstream fin(vm["keyslist"].as<fs::path>().string());
  if (! fin.is_open()) {
    cerr << "Unable to open the file " << vm["keyslist"].as<fs::path>() << endl;
  }
  long long key;
  high_resolution_clock::time_point start_time =
    high_resolution_clock::now();
  unsigned long long lno = 0;
  while (fin >> key) {
    lno++;
    if (lno < start_pos) {
      continue;
    }
    string feat = infeatstor->directGet(key);
    if (feat.length() < 0 || ! outfeatstor->directPut(key, feat)) {
      cerr << "Couldn't read/write " << key << endl;
    }
    high_resolution_clock::time_point cur_time =
      high_resolution_clock::now();
    if (duration_cast<seconds>(cur_time - start_time).count() > 2) {
      cout << "Done for " << lno << endl;
      start_time = cur_time;
    }
  }
  fin.close();

  return 0;
}

max_stars_repo_name: USCDataScience/cmu-fg-bg-similarity

max_issues_repo_name: USCDataScience/cmu-fg-bg-similarity

max_forks_repo_name: USCDataScience/cmu-fg-bg-similarity


text:
// Copyright (C) 2013 Vicente J. Botet Escriba
//
//  Distributed under the Boost Software License, Version 1.0. (See accompanying
//  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//
// 2013/09 Vicente J. Botet Escriba
//    Adapt to boost from CCIA C++11 implementation

#ifndef BOOST_THREAD_EXECUTOR_HPP
#define BOOST_THREAD_EXECUTOR_HPP

#include <boost/thread/executors/executor.hpp>
#include <boost/thread/executors/executor_adaptor.hpp>

#endif

max_stars_repo_name: cfsengineering/tigl

max_issues_repo_name: cfsengineering/tigl

max_forks_repo_name: cfsengineering/tigl


text:
//
// Created by yalez on 2018/8/21.
//

#define BOOST_TEST_MODULE miner_plugin

#ifndef CELESOS_TEST_MOUDLE_MINER_PLUGIN_ON
#define CELESOS_TEST_MOUDLE_MINER_PLUGIN_ON
#endif //CELESOS_TEST_MOUDLE_MINER_PLUGIN_ON

#include <boost/test/unit_test.hpp>
#include <boost/asio.hpp>
#include <boost/signals2.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <fc/log/logger.hpp>
#include <eosio/testing/tester.hpp>
#include <celesos/pow/ethash.hpp>
#include <celesos/miner_plugin/worker.hpp>
#include <celesos/miner_plugin/miner.hpp>
#include <celesos/miner_plugin/miner_plugin.hpp>
#include <eosio/chain/forest_bank.hpp>

using namespace celesos;
using namespace eosio;

using boost::multiprecision::uint256_t;

BOOST_AUTO_TEST_SUITE(worker_suite)

    BOOST_AUTO_TEST_CASE(worker_test) {
        const static uint32_t HASH_BYTES = 64;
        const static uint64_t CACHE_BYTES = 1024;
        const static uint64_t DATASET_BYTES = 1024 * 32;

        const static auto CACHE_COUNT = static_cast<uint32_t>(CACHE_BYTES / HASH_BYTES);
        const static auto DATASET_COUNT = static_cast<uint32_t>(DATASET_BYTES / HASH_BYTES);

        auto target_ptr = std::make_shared<uint256_t>(197);
        auto &target = *target_ptr;
        target |= uint256_t{90} << 1;
        for (int i = 2; i < 31; ++i) {
            target |= uint256_t{255} << i * 8;
        }

        auto nonce_start_ptr = std::make_shared<uint256_t>();
        miner::miner::gen_random_uint256(*nonce_start_ptr);

        auto retry_count_ptr = std::make_shared<uint256_t>(-1);

        auto io_service_ptr = std::make_shared<boost::asio::io_service>();
        auto signal_ptr = std::make_shared<miner::mine_signal_type>();
        signal_ptr->connect([](auto is_success, auto block_num, auto wood) {
            BOOST_CHECK_EQUAL(is_success, true);
        });

        auto seed_ptr = std::make_shared<std::string>("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
        auto forest_ptr = seed_ptr;

        BOOST_TEST_MESSAGE("begin prepare cache with count: " << CACHE_COUNT);
        auto cache_ptr = std::make_shared<std::vector<ethash::node>>(CACHE_COUNT);
        ethash::calc_cache(*cache_ptr, CACHE_COUNT, *seed_ptr);
        BOOST_TEST_MESSAGE("end prepare cache with count: " << CACHE_COUNT);

        BOOST_TEST_MESSAGE("begin prepare dataset with count: " << DATASET_COUNT);
        auto dataset_ptr = std::make_shared<std::vector<ethash::node>>(DATASET_COUNT);
        ethash::calc_dataset(*dataset_ptr, DATASET_COUNT, *cache_ptr);
        BOOST_TEST_MESSAGE("end prepare dataset with count: " << DATASET_COUNT);

        fc::logger a_logger{};
        miner::worker_ctx ctx{
                .logger = a_logger,
                .dataset_ptr = dataset_ptr,
                .seed_ptr = seed_ptr,
                .forest_ptr = forest_ptr,
                .nonce_start_ptr = nonce_start_ptr,
                .retry_count_ptr = retry_count_ptr,
                .target_ptr = target_ptr,
                .block_num = 1024,
                .io_service_ref = *io_service_ptr,
                .signal_ptr = signal_ptr,
                .sleep_interval_sec = 0,
                .sleep_probability = 0.0f,
        };
        miner::worker worker{std::move(ctx)};
        worker.start();

        BOOST_TEST_MESSAGE("begin solve nonce");
        boost::asio::io_service::work work{*io_service_ptr};
        io_service_ptr->run_one();
        BOOST_TEST_MESSAGE("end solve nonce");
    }

BOOST_AUTO_TEST_SUITE_END()

BOOST_AUTO_TEST_SUITE(miner_suite)

    BOOST_FIXTURE_TEST_CASE(miner_test, testing::tester) {
        auto &controller_ref = *this->control;

        std::mutex mutex{};
        std::unique_lock<std::mutex> lock{mutex};
        std::condition_variable stop_signal{};
        auto bank = forest::forest_bank::getInstance(controller_ref);

        miner::miner miner{fc::logger::get(), app().get_io_service(), 1, 0, 0.0f};
        miner.connect([&stop_signal, bank](bool is_success, chain::block_num_type block_num,
                                           const boost::optional<uint256_t> &wood_opt) {
            BOOST_CHECK_EQUAL(is_success, true);
            std::string wood_hex{};
            ethash::uint256_to_hex(wood_hex, *wood_opt);
            BOOST_CHECK_EQUAL(bank->verify_wood(block_num, "yale", wood_hex.c_str()), true);
            stop_signal.notify_all();
        });

        BOOST_TEST_MESSAGE("begin solve wood by miner");
        chain::account_name relative_account{"yale"};
        miner.start(std::move(relative_account), controller_ref);
        produce_blocks(1024);
        stop_signal.wait(lock);
        BOOST_TEST_MESSAGE("after wait");
        miner.stop();
        BOOST_TEST_MESSAGE("end solve wood by miner");
    }

BOOST_AUTO_TEST_SUITE_END()

//BOOST_AUTO_TEST_SUITE(miner_plugin_suite)
//
//BOOST_AUTO_TEST_SUITE_END()

max_stars_repo_name: celes-dev/celesos

max_issues_repo_name: celes-dev/celesos

max_forks_repo_name: celes-dev/celesos


text:
//==============================================================================
//         Copyright 2003 - 2012 LASMEA UMR 6602 CNRS/Univ. Clermont II
//         Copyright 2009 - 2012 LRI    UMR 8623 CNRS/Univ Paris Sud XI
//
//          Distributed under the Boost Software License, Version 1.0.
//                 See accompanying file LICENSE.txt or copy at
//                     http://www.boost.org/LICENSE_1_0.txt
//==============================================================================
#ifndef BOOST_SIMD_TOOLBOX_SWAR_FUNCTIONS_SIMD_SSE_SSE2_REPEAT_LOWER_HALF_HPP_INCLUDED
#define BOOST_SIMD_TOOLBOX_SWAR_FUNCTIONS_SIMD_SSE_SSE2_REPEAT_LOWER_HALF_HPP_INCLUDED
#ifdef BOOST_SIMD_HAS_SSE2_SUPPORT

#include <boost/simd/toolbox/swar/functions/repeat_lower_half.hpp>
#include <boost/simd/toolbox/swar/functions/details/shuffle.hpp>

namespace boost { namespace simd { namespace ext
{
  BOOST_SIMD_FUNCTOR_IMPLEMENTATION( boost::simd::tag::repeat_lower_half_
                                   , boost::simd::tag::sse2_
                                   , (A0)
                                   , ((simd_<single_<A0>,boost::simd::tag::sse_>))
                                   )
  {
    typedef A0 result_type;

    result_type operator()(__m128 const a0) const
    {
      return _mm_movelh_ps(a0,a0);
    }
  };

  BOOST_SIMD_FUNCTOR_IMPLEMENTATION( boost::simd::tag::repeat_lower_half_
                                   , boost::simd::tag::sse2_
                                   , (A0)
                                   , ((simd_<type32_<A0>,boost::simd::tag::sse_>))
                                   )
  {
    typedef A0 result_type;

    result_type operator()(__m128i const a0) const
    {
      return  details::shuffle<0, 1, 0, 1>(a0, a0);
    }
  };

  BOOST_SIMD_FUNCTOR_IMPLEMENTATION( boost::simd::tag::repeat_lower_half_
                                   , boost::simd::tag::sse2_
                                   , (A0)
                                   , ((simd_<type64_<A0>,boost::simd::tag::sse_>))
                                   )
  {
    typedef A0 result_type;

    result_type operator()(__m128i const a0) const
    {
      return  details::shuffle<0, 1, 0, 1>(a0, a0);
    }
  };

  BOOST_SIMD_FUNCTOR_IMPLEMENTATION( boost::simd::tag::repeat_lower_half_
                                   , boost::simd::tag::sse2_
                                   , (A0)
                                   , ((simd_<double_<A0>,boost::simd::tag::sse_>))
                                   )
  {
    typedef A0 result_type;

    result_type operator()(__m128d const a0) const
    {
      return _mm_unpacklo_pd(a0,a0);
    }
  };
} } }

#endif
#endif


text: #include <boost/beast/version.hpp>

max_stars_repo_name: miathedev/BoostForArduino

max_issues_repo_name: miathedev/BoostForArduino

max_forks_repo_name: miathedev/BoostForArduino