path: root/src/mongo/db/matcher/expression_geo.cpp

// expression_geo.cpp

/**
 *    Copyright (C) 2013 10gen 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::kDefault

#include "mongo/platform/basic.h"
#include "mongo/db/matcher/expression_geo.h"
#include "mongo/db/geo/geoparser.h"
#include "mongo/util/mongoutils/str.h"
#include "mongo/util/log.h"

namespace mongo {


    using mongoutils::str::equals;

    //
    // GeoExpression
    //

    // Put simple constructors here for unique_ptr.
    GeoExpression::GeoExpression() : field(""), predicate(INVALID) {}
    GeoExpression::GeoExpression(const std::string& f) : field(f), predicate(INVALID) {}

    Status GeoExpression::parseQuery(const BSONObj &obj) {
        BSONObjIterator outerIt(obj);
        // "within" / "geoWithin" / "geoIntersects"
        BSONElement queryElt = outerIt.next();
        if (outerIt.more()) {
            return Status(ErrorCodes::BadValue,
                          str::stream() << "can't parse extra field: " << outerIt.next());
        }

        BSONObj::MatchType matchType = static_cast<BSONObj::MatchType>(queryElt.getGtLtOp());
        if (BSONObj::opGEO_INTERSECTS == matchType) {
            predicate = GeoExpression::INTERSECT;
        } else if (BSONObj::opWITHIN == matchType) {
            predicate = GeoExpression::WITHIN;
        } else {
            // eoo() or unknown query predicate.
            return Status(ErrorCodes::BadValue,
                          str::stream() << "invalid geo query predicate: " << obj);
        }

        // Parse geometry after predicates.
        if (Object != queryElt.type()) return Status(ErrorCodes::BadValue, "geometry must be an object");
        BSONObj geoObj = queryElt.Obj();

        BSONObjIterator geoIt(geoObj);

        while (geoIt.more()) {
            BSONElement elt = geoIt.next();
            if (str::equals(elt.fieldName(), "$uniqueDocs")) {
                // Deprecated "$uniqueDocs" field
                warning() << "deprecated $uniqueDocs option: " << obj.toString() << endl;
            } else {
                // The element must be a geo specifier. "$box", "$center", "$geometry", etc.
                geoContainer.reset(new GeometryContainer());
                Status status = geoContainer->parseFromQuery(elt);
                if (!status.isOK()) return status;
            }
        }

        if (geoContainer == NULL) {
            return Status(ErrorCodes::BadValue, "geo query doesn't have any geometry");
        }

        return Status::OK();
    }

    Status GeoExpression::parseFrom(const BSONObj &obj) {
        // Initialize geoContainer and parse BSON object
        Status status = parseQuery(obj);
        if (!status.isOK()) return status;

        // Why do we only deal with $within {polygon}?
        // 1. Finding things within a point is silly and only valid
        // for points and degenerate lines/polys.
        //
        // 2. Finding points within a line is easy but that's called intersect.
        // Finding lines within a line is kind of tricky given what S2 gives us.
        // Doing line-within-line is a valid yet unsupported feature,
        // though I wonder if we want to preserve orientation for lines or
        // allow (a,b),(c,d) to be within (c,d),(a,b).  Anyway, punt on
        // this for now.
        if (GeoExpression::WITHIN == predicate && !geoContainer->supportsContains()) {
            return Status(ErrorCodes::BadValue,
                          str::stream() << "$within not supported with provided geometry: " << obj);
        }

        // Big polygon with strict winding order is represented as an S2Loop in SPHERE CRS.
        // So converting the query to SPHERE CRS makes things easier than projecting all the data
        // into STRICT_SPHERE CRS.
        if (STRICT_SPHERE == geoContainer->getNativeCRS()) {
            if (!geoContainer->supportsProject(SPHERE)) {
                return Status(ErrorCodes::BadValue,
                              "only polygon supported with strict winding order");
            }
            geoContainer->projectInto(SPHERE);
        }

        // $geoIntersect queries are hardcoded to *always* be in SPHERE CRS
        // TODO: This is probably bad semantics, should not do this
        if (GeoExpression::INTERSECT == predicate) {
            if (!geoContainer->supportsProject(SPHERE)) {
                return Status(ErrorCodes::BadValue,
                              str::stream()
                                      << "$geoIntersect not supported with provided geometry: "
                                      << obj);
            }
            geoContainer->projectInto(SPHERE);
        }

        return Status::OK();
    }

    //
    // GeoNearExpression
    //

    GeoNearExpression::GeoNearExpression()
        : minDistance(0),
          maxDistance(std::numeric_limits<double>::max()),
          isNearSphere(false),
          unitsAreRadians(false),
          isWrappingQuery(false) { }

    GeoNearExpression::GeoNearExpression(const std::string& f)
        : field(f),
          minDistance(0),
          maxDistance(std::numeric_limits<double>::max()),
          isNearSphere(false),
          unitsAreRadians(false),
          isWrappingQuery(false) { }

    bool GeoNearExpression::parseLegacyQuery(const BSONObj &obj) {

        bool hasGeometry = false;

        // First, try legacy near, e.g.:
        // t.find({ loc : { $nearSphere: [0,0], $minDistance: 1, $maxDistance: 3 }})
        // t.find({ loc : { $nearSphere: [0,0] }})
        // t.find({ loc : { $near : [0, 0, 1] } });
        // t.find({ loc : { $near: { someGeoJSONPoint}})
        // t.find({ loc : { $geoNear: { someGeoJSONPoint}})
        BSONObjIterator it(obj);
        while (it.more()) {
            BSONElement e = it.next();
            if (equals(e.fieldName(), "$near") || equals(e.fieldName(), "$geoNear")
                                               || equals(e.fieldName(), "$nearSphere")) {
                if (!e.isABSONObj()) { return false; }
                BSONObj embeddedObj = e.embeddedObject();

                if (GeoParser::parseQueryPoint(e, centroid.get()).isOK()
                    || GeoParser::parsePointWithMaxDistance(embeddedObj, centroid.get(), &maxDistance)) {
                    uassert(18522, "max distance must be non-negative", maxDistance >= 0.0);
                    hasGeometry = true;
                    isNearSphere = equals(e.fieldName(), "$nearSphere");
                }
            } else if (equals(e.fieldName(), "$minDistance")) {
                uassert(16893, "$minDistance must be a number", e.isNumber());
                minDistance = e.Number();
                uassert(16894, "$minDistance must be non-negative", minDistance >= 0.0);
            } else if (equals(e.fieldName(), "$maxDistance")) {
                uassert(16895, "$maxDistance must be a number", e.isNumber());
                maxDistance = e.Number();
                uassert(16896, "$maxDistance must be non-negative", maxDistance >= 0.0);
            } else if (equals(e.fieldName(), "$uniqueDocs")) {
                warning() << "ignoring deprecated option $uniqueDocs";
            }
        }

        return hasGeometry;
    }

    Status GeoNearExpression::parseNewQuery(const BSONObj &obj) {
        bool hasGeometry = false;

        BSONObjIterator objIt(obj);
        if (!objIt.more()) {
            return Status(ErrorCodes::BadValue, "empty geo near query object");
        }
        BSONElement e = objIt.next();
        // Just one arg. to $geoNear.
        if (objIt.more()) {
            return Status(ErrorCodes::BadValue, mongoutils::str::stream() <<
                          "geo near accepts just one argument when querying for a GeoJSON " <<
                          "point. Extra field found: " << objIt.next());
        }

        // Parse "new" near:
        // t.find({"geo" : {"$near" : {"$geometry": pointA, $minDistance: 1, $maxDistance: 3}}})
        // t.find({"geo" : {"$geoNear" : {"$geometry": pointA, $minDistance: 1, $maxDistance: 3}}})
        if (!e.isABSONObj()) {
            return Status(ErrorCodes::BadValue, "geo near query argument is not an object");
        }
        BSONObj::MatchType matchType = static_cast<BSONObj::MatchType>(e.getGtLtOp());
        if (BSONObj::opNEAR != matchType) {
            return Status(ErrorCodes::BadValue, mongoutils::str::stream() <<
                          "invalid geo near query operator: " << e.fieldName());
        }

        // Iterate over the argument.
        BSONObjIterator it(e.embeddedObject());
        while (it.more()) {
            BSONElement e = it.next();
            if (equals(e.fieldName(), "$geometry")) {
                if (e.isABSONObj()) {
                    BSONObj embeddedObj = e.embeddedObject();
                    Status status = GeoParser::parseQueryPoint(e, centroid.get());
                    if (!status.isOK()) {
                        return Status(ErrorCodes::BadValue,
                                      str::stream()
                                              << "invalid point in geo near query $geometry argument: "
                                              << embeddedObj << "  " << status.reason());
                    }
                    uassert(16681, "$near requires geojson point, given " + embeddedObj.toString(),
                            (SPHERE == centroid->crs));
                    hasGeometry = true;
                }
            } else if (equals(e.fieldName(), "$minDistance")) {
                uassert(16897, "$minDistance must be a number", e.isNumber());
                minDistance = e.Number();
                uassert(16898, "$minDistance must be non-negative", minDistance >= 0.0);
            } else if (equals(e.fieldName(), "$maxDistance")) {
                uassert(16899, "$maxDistance must be a number", e.isNumber());
                maxDistance = e.Number();
                uassert(16900, "$maxDistance must be non-negative", maxDistance >= 0.0);
            }
        }

        if (!hasGeometry) {
            return Status(ErrorCodes::BadValue, "$geometry is required for geo near query");
        }

        return Status::OK();
    }


    Status GeoNearExpression::parseFrom(const BSONObj &obj) {

        Status status = Status::OK();
        centroid.reset(new PointWithCRS());

        if (!parseLegacyQuery(obj)) {
            // Clear out any half-baked data.
            minDistance = 0;
            isNearSphere = false;
            maxDistance = std::numeric_limits<double>::max();
            // ...and try parsing new format.
            status = parseNewQuery(obj);
        }

        if (!status.isOK())
            return status;

        // Fixup the near query for anonoyances caused by $nearSphere
        if (isNearSphere) {

            // The user-provided point can be flat for a spherical query - needs to be projectable
            uassert(17444,
                    "Legacy point is out of bounds for spherical query",
                    ShapeProjection::supportsProject(*centroid, SPHERE));

            unitsAreRadians = SPHERE != centroid->crs;
            // GeoJSON points imply wrapping queries
            isWrappingQuery = SPHERE == centroid->crs;

            // Project the point to a spherical CRS now that we've got the settings we need
            // We need to manually project here since we aren't using GeometryContainer
            ShapeProjection::projectInto(centroid.get(), SPHERE);
        }
        else {
            unitsAreRadians = false;
            isWrappingQuery = SPHERE == centroid->crs;
        }

        return status;
    }

    //
    // GeoMatchExpression and GeoNearMatchExpression
    //

    //
    // Geo queries we don't need an index to answer: geoWithin and geoIntersects
    //

    Status GeoMatchExpression::init( StringData path, const GeoExpression* query,
                                     const BSONObj& rawObj ) {
        _query.reset(query);
        _rawObj = rawObj;
        return initPath( path );
    }

    bool GeoMatchExpression::matchesSingleElement( const BSONElement& e ) const {
        if ( !e.isABSONObj())
            return false;

        GeometryContainer geometry;
        if ( !geometry.parseFromStorage( e ).isOK() )
                return false;

        // Never match big polygon
        if (geometry.getNativeCRS() == STRICT_SPHERE)
            return false;

        // Project this geometry into the CRS of the query
        if (!geometry.supportsProject(_query->getGeometry().getNativeCRS()))
            return false;

        geometry.projectInto(_query->getGeometry().getNativeCRS());

        if (GeoExpression::WITHIN == _query->getPred()) {
            return _query->getGeometry().contains(geometry);
        }
        else {
            verify(GeoExpression::INTERSECT == _query->getPred());
            return _query->getGeometry().intersects(geometry);
        }
    }

    void GeoMatchExpression::debugString( StringBuilder& debug, int level ) const {
        _debugAddSpace( debug, level );
        debug << "GEO raw = " << _rawObj.toString();
        MatchExpression::TagData* td = getTag();
        if (NULL != td) {
            debug << " ";
            td->debugString(&debug);
        }
        debug << "\n";
    }

    void GeoMatchExpression::toBSON(BSONObjBuilder* out) const {
        out->appendElements(_rawObj);
    }

    bool GeoMatchExpression::equivalent( const MatchExpression* other ) const {
        if ( matchType() != other->matchType() )
            return false;

        const GeoMatchExpression* realOther = static_cast<const GeoMatchExpression*>( other );

        if ( path() != realOther->path() )
            return false;

        return _rawObj == realOther->_rawObj;
    }

    LeafMatchExpression* GeoMatchExpression::shallowClone() const {
        GeoMatchExpression* next = new GeoMatchExpression();
        next->init( path(), NULL, _rawObj);
        next->_query = _query;
        if (getTag()) {
            next->setTag(getTag()->clone());
        }
        return next;
    }

    //
    // Parse-only geo expressions: geoNear (formerly known as near).
    //

    Status GeoNearMatchExpression::init( StringData path, const GeoNearExpression* query,
                                         const BSONObj& rawObj ) {
        _query.reset(query);
        _rawObj = rawObj;
        return initPath( path );
    }

    bool GeoNearMatchExpression::matchesSingleElement( const BSONElement& e ) const {
        // See ops/update.cpp.
        // This node is removed by the query planner.  It's only ever called if we're getting an
        // elemMatchKey.
        return true;
    }

    void GeoNearMatchExpression::debugString( StringBuilder& debug, int level ) const {
        _debugAddSpace( debug, level );
        debug << "GEONEAR " << _query->toString();
        MatchExpression::TagData* td = getTag();
        if (NULL != td) {
            debug << " ";
            td->debugString(&debug);
        }
        debug << "\n";
    }

    void GeoNearMatchExpression::toBSON(BSONObjBuilder* out) const {
        out->appendElements(_rawObj);
    }

    bool GeoNearMatchExpression::equivalent( const MatchExpression* other ) const {
        if ( matchType() != other->matchType() )
            return false;

        const GeoNearMatchExpression* realOther = static_cast<const GeoNearMatchExpression*>(other);

        if ( path() != realOther->path() )
            return false;

        return _rawObj == realOther->_rawObj;
    }

    LeafMatchExpression* GeoNearMatchExpression::shallowClone() const {
        GeoNearMatchExpression* next = new GeoNearMatchExpression();
        next->init( path(), NULL, _rawObj );
        next->_query = _query;
        if (getTag()) {
            next->setTag(getTag()->clone());
        }
        return next;
    }

}