// 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 .
*
* 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/db/matcher/expression_geo.h"
#include "mongo/bson/simple_bsonobj_comparator.h"
#include "mongo/db/geo/geoparser.h"
#include "mongo/db/matcher/expression_parser.h"
#include "mongo/platform/basic.h"
#include "mongo/util/log.h"
#include "mongo/util/mongoutils/str.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());
}
auto keyword = MatchExpressionParser::parsePathAcceptingKeyword(queryElt);
if (PathAcceptingKeyword::GEO_INTERSECTS == keyword) {
predicate = GeoExpression::INTERSECT;
} else if (PathAcceptingKeyword::WITHIN == keyword) {
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: " << redact(obj);
} 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::max()),
isNearSphere(false),
unitsAreRadians(false),
isWrappingQuery(false) {}
GeoNearExpression::GeoNearExpression(const std::string& f)
: field(f),
minDistance(0),
maxDistance(std::numeric_limits::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";
} else {
// In a query document, $near queries can have no non-geo sibling parameters.
uasserted(34413,
str::stream() << "invalid argument in geo near query: " << e.fieldName());
}
}
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");
}
if (PathAcceptingKeyword::GEO_NEAR != MatchExpressionParser::parsePathAcceptingKeyword(e)) {
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);
} else {
// Return an error if a bad argument was passed inside the query document.
return Status(ErrorCodes::BadValue,
str::stream() << "invalid argument in geo near query: " << e.fieldName());
}
}
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::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 setPath(path);
}
bool GeoMatchExpression::matchesSingleElement(const BSONElement& e, MatchDetails* details) const {
if (!e.isABSONObj())
return false;
GeometryContainer geometry;
if (!geometry.parseFromStorage(e, _canSkipValidation).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);
BSONObjBuilder builder;
serialize(&builder);
debug << "GEO raw = " << builder.obj().toString();
MatchExpression::TagData* td = getTag();
if (NULL != td) {
debug << " ";
td->debugString(&debug);
}
debug << "\n";
}
void GeoMatchExpression::serialize(BSONObjBuilder* out) const {
BSONObjBuilder subobj(out->subobjStart(path()));
subobj.appendElements(_rawObj);
subobj.doneFast();
}
bool GeoMatchExpression::equivalent(const MatchExpression* other) const {
if (matchType() != other->matchType())
return false;
const GeoMatchExpression* realOther = static_cast(other);
if (path() != realOther->path())
return false;
return SimpleBSONObjComparator::kInstance.evaluate(_rawObj == realOther->_rawObj);
}
std::unique_ptr GeoMatchExpression::shallowClone() const {
std::unique_ptr next = stdx::make_unique();
next->init(path(), NULL, _rawObj).transitional_ignore();
next->_query = _query;
next->_canSkipValidation = _canSkipValidation;
if (getTag()) {
next->setTag(getTag()->clone());
}
return std::move(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 setPath(path);
}
bool GeoNearMatchExpression::matchesSingleElement(const BSONElement& e,
MatchDetails* details) const {
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::serialize(BSONObjBuilder* out) const {
BSONObjBuilder subobj(out->subobjStart(path()));
subobj.appendElements(_rawObj);
subobj.doneFast();
}
bool GeoNearMatchExpression::equivalent(const MatchExpression* other) const {
if (matchType() != other->matchType())
return false;
const GeoNearMatchExpression* realOther = static_cast(other);
if (path() != realOther->path())
return false;
return SimpleBSONObjComparator::kInstance.evaluate(_rawObj == realOther->_rawObj);
}
std::unique_ptr GeoNearMatchExpression::shallowClone() const {
std::unique_ptr next = stdx::make_unique();
next->init(path(), NULL, _rawObj).transitional_ignore();
next->_query = _query;
if (getTag()) {
next->setTag(getTag()->clone());
}
return std::move(next);
}
}