// Get the index keys for elements that are GeoJSON.
    void S2AccessMethod::getGeoKeys(const BSONElementSet& elements, BSONObjSet* out) const {
        for (BSONElementSet::iterator i = elements.begin(); i != elements.end(); ++i) {
            uassert(16754, "Can't parse geometry from element: " + i->toString(),
                    i->isABSONObj());
            const BSONObj &obj = i->Obj();

            vector<string> cells;
            bool succeeded = S2SearchUtil::getKeysForObject(obj, _params, &cells);
            uassert(16755, "Can't extract geo keys from object, malformed geometry?:"
                           + obj.toString(), succeeded);

            uassert(16756, "Unable to generate keys for (likely malformed) geometry: "
                    + obj.toString(),
                    cells.size() > 0);

            for (vector<string>::const_iterator it = cells.begin(); it != cells.end(); ++it) {
                BSONObjBuilder b;
                b.append("", *it);
                out->insert(b.obj());
            }
        }

        if (0 == out->size()) {
            BSONObjBuilder b;
            b.appendNull("");
            out->insert(b.obj());
        }
    }

    // Get the index keys for elements that are GeoJSON.
    void S2AccessMethod::getGeoKeys(const BSONElementSet& elements, BSONObjSet* out) const {
        S2RegionCoverer coverer;
        _params.configureCoverer(&coverer);

        // See here for GeoJSON format: geojson.org/geojson-spec.html
        for (BSONElementSet::iterator i = elements.begin(); i != elements.end(); ++i) {
            uassert(16754, "Can't parse geometry from element: " + i->toString(),
                    i->isABSONObj());
            const BSONObj &obj = i->Obj();

            vector<string> cells;
            S2Polyline line;
            S2Cell point;
            // We only support GeoJSON polygons.  Why?:
            // 1. we don't automagically do WGS84/flat -> WGS84, and
            // 2. the old polygon format must die.
            if (GeoParser::isGeoJSONPolygon(obj)) {
                S2Polygon polygon;
                GeoParser::parseGeoJSONPolygon(obj, &polygon);
                keysFromRegion(&coverer, polygon, &cells);
            } else if (GeoParser::parseLineString(obj, &line)) {
                keysFromRegion(&coverer, line, &cells);
            } else if (GeoParser::parsePoint(obj, &point)) {
                S2CellId parent(point.id().parent(_params.finestIndexedLevel));
                cells.push_back(parent.toString());
            } else {
                uasserted(16755, "Can't extract geo keys from object, malformed geometry?:"
                        + obj.toString());
            }
            uassert(16756, "Unable to generate keys for (likely malformed) geometry: "
                    + obj.toString(),
                    cells.size() > 0);

            for (vector<string>::const_iterator it = cells.begin(); it != cells.end(); ++it) {
                BSONObjBuilder b;
                b.append("", *it);
                out->insert(b.obj());
            }
        }

        if (0 == out->size()) {
            BSONObjBuilder b;
            b.appendNull("");
            out->insert(b.obj());
        }
    }

    // This is the actual search.
    bool S2Cursor::advance() {
        if (_numToReturn <= 0) { return false; }
        for (; _btreeCursor->ok(); _btreeCursor->advance()) {
            ++_nscanned;
            if (_seen.end() != _seen.find(_btreeCursor->currLoc())) { continue; }
            _seen.insert(_btreeCursor->currLoc());

            ++_matchTested;
            MatchDetails details;
            bool matched = _matcher->matchesCurrent(_btreeCursor.get(), &details);
            if (!matched) { continue; }

            const BSONObj &indexedObj = _btreeCursor->currLoc().obj();

            ++_geoTested;
            size_t geoFieldsMatched = 0;
            // OK, cool, non-geo match satisfied.  See if the object actually overlaps w/the geo
            // query fields.
            for (size_t i = 0; i < _fields.size(); ++i) {
                BSONElementSet geoFieldElements;
                indexedObj.getFieldsDotted(_fields[i].getField(), geoFieldElements, false);
                if (geoFieldElements.empty()) { continue; }

                bool match = false;

                for (BSONElementSet::iterator oi = geoFieldElements.begin();
                     !match && (oi != geoFieldElements.end()); ++oi) {
                    if (!oi->isABSONObj()) { continue; }
                    const BSONObj &geoObj = oi->Obj();
                    GeometryContainer geoContainer;
                    uassert(16698, "malformed geometry: " + geoObj.toString(),
                            geoContainer.parseFrom(geoObj));
                    match = _fields[i].satisfiesPredicate(geoContainer);
                }

                if (match) { ++geoFieldsMatched; }
            }

            if (geoFieldsMatched == _fields.size()) {
                // We have a winner!  And we point at it.
                --_numToReturn;
                return true;
            }
        }
        return false;
    }

        // Get the index keys for elements that are GeoJSON.
        void getGeoKeys(const BSONElementSet &elements, BSONObjSet *out) const {
            S2RegionCoverer coverer;
            _params.configureCoverer(&coverer);

            // See here for GeoJSON format: geojson.org/geojson-spec.html
            for (BSONElementSet::iterator i = elements.begin(); i != elements.end(); ++i) {
                if (!i->isABSONObj()) { continue; }  // error?
                const BSONObj &obj = i->Obj();

                vector<string> cells;
                S2Polygon polygon;
                S2Polyline line;
                S2Cell point;
                if (GeoParser::parsePolygon(obj, &polygon)) {
                    keysFromRegion(&coverer, polygon, &cells);
                } else if (GeoParser::parseLineString(obj, &line)) {
                    keysFromRegion(&coverer, line, &cells);
                } else if (GeoParser::parsePoint(obj, &point)) {
                    keysFromRegion(&coverer, point, &cells);
                } else {
                    uasserted(16572, "Can't extract geo keys from object, malformed geometry?:"
                                     + obj.toString());
                }

                for (vector<string>::const_iterator it = cells.begin(); it != cells.end(); ++it) {
                    BSONObjBuilder b;
                    b.append("", *it);
                    out->insert(b.obj());
                }
            }

            if (0 == out->size()) {
                BSONObjBuilder b;
                b.appendNull("");
                out->insert(b.obj());
            }
        }

    PlanStage::StageState S2NearStage::addResultToQueue(WorkingSetID* out) {
        PlanStage::StageState state = _child->work(out);

        // All done reading from _child.
        if (PlanStage::IS_EOF == state) {
            _child.reset();
            _keyGeoFilter.reset();

            // Adjust the annulus size depending on how many results we got.
            if (_results.empty()) {
                _radiusIncrement *= 2;
            } else if (_results.size() < 300) {
                _radiusIncrement *= 2;
            } else if (_results.size() > 600) {
                _radiusIncrement /= 2;
            }

            // Make a new ixscan next time.
            return PlanStage::NEED_TIME;
        }

        // Nothing to do unless we advance.
        if (PlanStage::ADVANCED != state) { return state; }

        WorkingSetMember* member = _ws->get(*out);
        // Must have an object in order to get geometry out of it.
        verify(member->hasObj());

        // The scans we use don't dedup so we must dedup them ourselves.  We only put locs into here
        // if we know for sure whether or not we'll return them in this annulus.
        if (member->hasLoc()) {
            if (_seenInScan.end() != _seenInScan.find(member->loc)) {
                return PlanStage::NEED_TIME;
            }
        }

        // Get all the fields with that name from the document.
        BSONElementSet geom;
        member->obj.getFieldsDotted(_params.nearQuery.field, geom, false);
        if (geom.empty()) {
            return PlanStage::NEED_TIME;
        }

        // Some value that any distance we can calculate will be less than.
        double minDistance = numeric_limits<double>::max();
        BSONObj minDistanceObj;
        for (BSONElementSet::iterator git = geom.begin(); git != geom.end(); ++git) {
            if (!git->isABSONObj()) {
                mongoutils::str::stream ss;
                ss << "s2near stage read invalid geometry element " << *git << " from child";
                Status status(ErrorCodes::InternalError, ss);
                *out = WorkingSetCommon::allocateStatusMember( _ws, status);
                return PlanStage::FAILURE;
            }
            BSONObj obj = git->Obj();

            double distToObj;
            if (S2SearchUtil::distanceBetween(_params.nearQuery.centroid.point, obj, &distToObj)) {
                if (distToObj < minDistance) {
                    minDistance = distToObj;
                    minDistanceObj = obj;
                }
            }
            else {
                warning() << "unknown geometry: " << obj.toString();
            }
        }

        // If we're here we'll either include the doc in this annulus or reject it.  It's safe to
        // ignore it if it pops up again in this annulus.
        if (member->hasLoc()) {
            _seenInScan.insert(member->loc);
        }

        // If the distance to the doc satisfies our distance criteria, add it to our buffered
        // results.
        if (minDistance >= _innerRadius &&
            (_outerRadiusInclusive ? minDistance <= _outerRadius : minDistance < _outerRadius)) {
            _results.push(Result(*out, minDistance));
            if (_params.addDistMeta) {
                // FLAT implies the output distances are in radians.  Convert to meters.
                if (FLAT == _params.nearQuery.centroid.crs) {
                    member->addComputed(new GeoDistanceComputedData(minDistance
                                                                    / kRadiusOfEarthInMeters));
                }
                else {
                    member->addComputed(new GeoDistanceComputedData(minDistance));
                }
            }
            if (_params.addPointMeta) {
                member->addComputed(new GeoNearPointComputedData(minDistanceObj));
            }
            if (member->hasLoc()) {
                _invalidationMap[member->loc] = *out;
            }
        }

        return PlanStage::NEED_TIME;
    }

        static bool run2DSphereGeoNear(NamespaceDetails* nsDetails, int idxNo, BSONObj& cmdObj,
                                       const GeoNearArguments &parsedArgs, string& errmsg,
                                       BSONObjBuilder& result) {
            auto_ptr<IndexDescriptor> descriptor(CatalogHack::getDescriptor(nsDetails, idxNo));
            auto_ptr<S2AccessMethod> sam(new S2AccessMethod(descriptor.get()));
            const S2IndexingParams& params = sam->getParams();
            auto_ptr<S2NearIndexCursor> nic(new S2NearIndexCursor(descriptor.get(), params));

            vector<string> geoFieldNames;
            BSONObjIterator i(descriptor->keyPattern());
            while (i.more()) {
                BSONElement e = i.next();
                if (e.type() == String && IndexNames::GEO_2DSPHERE == e.valuestr()) {
                    geoFieldNames.push_back(e.fieldName());
                }
            }

            // NOTE(hk): If we add a new argument to geoNear, we could have a
            // 2dsphere index with multiple indexed geo fields, and the geoNear
            // could pick the one to run over.  Right now, we just require one.
            uassert(16552, "geoNear requires exactly one indexed geo field", 1 == geoFieldNames.size());
            NearQuery nearQuery(geoFieldNames[0]);
            uassert(16679, "Invalid geometry given as arguments to geoNear: " + cmdObj.toString(),
                    nearQuery.parseFromGeoNear(cmdObj, params.radius));
            uassert(16683, "geoNear on 2dsphere index requires spherical",
                    parsedArgs.isSpherical);

            // NOTE(hk): For a speedup, we could look through the query to see if
            // we've geo-indexed any of the fields in it.
            vector<GeoQuery> regions;

            nic->seek(parsedArgs.query, nearQuery, regions);

            // We do pass in the query above, but it's just so we can possibly use it in our index
            // scan.  We have to do our own matching.
            auto_ptr<Matcher> matcher(new Matcher(parsedArgs.query));

            double totalDistance = 0;
            BSONObjBuilder resultBuilder(result.subarrayStart("results"));
            double farthestDist = 0;

            int results;
            for (results = 0; results < parsedArgs.numWanted && !nic->isEOF(); ++results) {
                BSONObj currObj = nic->getValue().obj();
                if (!matcher->matches(currObj)) {
                    --results;
                    nic->next();
                    continue;
                }

                double dist = nic->currentDistance();
                // If we got the distance in radians, output it in radians too.
                if (nearQuery.fromRadians) { dist /= params.radius; }
                dist *= parsedArgs.distanceMultiplier;
                totalDistance += dist;
                if (dist > farthestDist) { farthestDist = dist; }

                BSONObjBuilder oneResultBuilder(
                    resultBuilder.subobjStart(BSONObjBuilder::numStr(results)));
                oneResultBuilder.append("dis", dist);
                if (parsedArgs.includeLocs) {
                    BSONElementSet geoFieldElements;
                    currObj.getFieldsDotted(geoFieldNames[0], geoFieldElements, false);
                    for (BSONElementSet::iterator oi = geoFieldElements.begin();
                            oi != geoFieldElements.end(); ++oi) {
                        if (oi->isABSONObj()) {
                            oneResultBuilder.appendAs(*oi, "loc");
                        }
                    }
                }

                oneResultBuilder.append("obj", currObj);
                oneResultBuilder.done();
                nic->next();
            }

            resultBuilder.done();

            BSONObjBuilder stats(result.subobjStart("stats"));
            stats.appendNumber("nscanned", nic->nscanned());
            stats.append("avgDistance", totalDistance / results);
            stats.append("maxDistance", farthestDist);
            stats.append("time", cc().curop()->elapsedMillis());
            stats.done();

            return true;
        }

// Fill _results with all of the results in the annulus defined by _innerRadius and
// _outerRadius.  If no results are found, grow the annulus and repeat until success (or
// until the edge of the world).
void S2NearIndexCursor::fillResults() {
    verify(_results.empty());
    if (_innerRadius >= _outerRadius) {
        return;
    }
    if (_innerRadius > _maxDistance) {
        return;
    }

    // We iterate until 1. our search radius is too big or 2. we find results.
    do {
        // Some of these arguments are opaque, look at the definitions of the involved classes.
        FieldRangeSet frs(_descriptor->parentNS().c_str(), makeFRSObject(), false, false);
        shared_ptr<FieldRangeVector> frv(new FieldRangeVector(frs, _specForFRV, 1));
        scoped_ptr<BtreeCursor> cursor(BtreeCursor::make(nsdetails(_descriptor->parentNS()),
                                       _descriptor->getOnDisk(), frv, 0, 1));

        // The cursor may return the same obj more than once for a given
        // FRS, so we make sure to only consider it once in any given annulus.
        //
        // We don't want this outside of the 'do' loop because the covering
        // for an annulus may return an object whose distance to the query
        // point is actually contained in a subsequent annulus.  If we
        // didn't consider every object in a given annulus we might miss
        // the point.
        //
        // We don't use a global 'seen' because we get that by requiring
        // the distance from the query point to the indexed geo to be
        // within our 'current' annulus, and I want to dodge all yield
        // issues if possible.
        unordered_set<DiskLoc, DiskLoc::Hasher> seen;

        LOG(1) << "looking at annulus from " << _innerRadius << " to " << _outerRadius << endl;
        LOG(1) << "Total # returned: " << _stats._numReturned << endl;
        // Do the actual search through this annulus.
        for (; cursor->ok(); cursor->advance()) {
            // Don't bother to look at anything we've returned.
            if (_returned.end() != _returned.find(cursor->currLoc())) {
                ++_stats._returnSkip;
                continue;
            }

            ++_stats._nscanned;
            if (seen.end() != seen.find(cursor->currLoc())) {
                ++_stats._btreeDups;
                continue;
            }

            // Get distance interval from our query point to the cell.
            // If it doesn't overlap with our current shell, toss.
            BSONObj currKey(cursor->currKey());
            BSONObjIterator it(currKey);
            BSONElement geoKey;
            for (int i = 0; i <= _nearFieldIndex; ++i) {
                geoKey = it.next();
            }

            S2Cell keyCell = S2Cell(S2CellId::FromString(geoKey.String()));
            if (!_annulus.MayIntersect(keyCell)) {
                ++_stats._keyGeoSkip;
                continue;
            }

            // We have to add this document to seen *AFTER* the key intersection test.
            // A geometry may have several keys, one of which may be in our search shell and one
            // of which may be outside of it.  We don't want to ignore a document just because
            // one of its covers isn't inside this annulus.
            seen.insert(cursor->currLoc());

            // At this point forward, we will not examine the document again in this annulus.

            const BSONObj& indexedObj = cursor->currLoc().obj();

            // Match against indexed geo fields.
            ++_stats._geoMatchTested;
            size_t geoFieldsMatched = 0;
            // See if the object actually overlaps w/the geo query fields.
            for (size_t i = 0; i < _indexedGeoFields.size(); ++i) {
                BSONElementSet geoFieldElements;
                indexedObj.getFieldsDotted(_indexedGeoFields[i].getField(), geoFieldElements,
                                           false);
                if (geoFieldElements.empty()) {
                    continue;
                }

                bool match = false;

                for (BSONElementSet::iterator oi = geoFieldElements.begin();
                        !match && (oi != geoFieldElements.end()); ++oi) {
                    if (!oi->isABSONObj()) {
                        continue;
                    }
                    const BSONObj &geoObj = oi->Obj();
                    GeometryContainer geoContainer;
                    uassert(16762, "ill-formed geometry: " + geoObj.toString(),
                            geoContainer.parseFrom(geoObj));
                    match = _indexedGeoFields[i].satisfiesPredicate(geoContainer);
//.........这里部分代码省略.........

    PlanStage::StageState S2NearStage::addResultToQueue(WorkingSetID* out) {
        PlanStage::StageState state = _child->work(out);

        // All done reading from _child.
        if (PlanStage::IS_EOF == state) {
            _child.reset();

            // Adjust the annulus size depending on how many results we got.
            if (_results.empty()) {
                _radiusIncrement *= 2;
            } else if (_results.size() < 300) {
                _radiusIncrement *= 2;
            } else if (_results.size() > 600) {
                _radiusIncrement /= 2;
            }

            // Make a new ixscan next time.
            return PlanStage::NEED_TIME;
        }

        // Nothing to do unless we advance.
        if (PlanStage::ADVANCED != state) { return state; }

        // TODO Speed improvements:
        //
        // 0. Modify fetch to preserve key data and test for intersection w/annulus.
        //
        // 1. keep track of what we've seen in this scan and possibly ignore it.
        //
        // 2. keep track of results we've returned before and ignore them.

        WorkingSetMember* member = _ws->get(*out);
        // Must have an object in order to get geometry out of it.
        verify(member->hasObj());

        // Get all the fields with that name from the document.
        BSONElementSet geom;
        member->obj.getFieldsDotted(_params.nearQuery.field, geom, false);
        if (geom.empty()) {return PlanStage::NEED_TIME; }

        // Some value that any distance we can calculate will be less than.
        double minDistance = numeric_limits<double>::max();
        BSONObj minDistanceObj;
        for (BSONElementSet::iterator git = geom.begin(); git != geom.end(); ++git) {
            if (!git->isABSONObj()) {
                mongoutils::str::stream ss;
                ss << "s2near stage read invalid geometry element " << *git << " from child";
                Status status(ErrorCodes::InternalError, ss);
                *out = WorkingSetCommon::allocateStatusMember( _ws, status);
                return PlanStage::FAILURE;
            }
            BSONObj obj = git->Obj();

            double distToObj;
            if (S2SearchUtil::distanceBetween(_params.nearQuery.centroid.point, obj, &distToObj)) {
                if (distToObj < minDistance) {
                    minDistance = distToObj;
                    minDistanceObj = obj;
                }
            }
            else {
                warning() << "unknown geometry: " << obj.toString();
            }
        }

        // If the distance to the doc satisfies our distance criteria, add it to our buffered
        // results.
        if (minDistance >= _innerRadius &&
            (_outerRadiusInclusive ? minDistance <= _outerRadius : minDistance < _outerRadius)) {
            _results.push(Result(*out, minDistance));
            if (_params.addDistMeta) {
                member->addComputed(new GeoDistanceComputedData(minDistance));
            }
            if (_params.addPointMeta) {
                member->addComputed(new GeoNearPointComputedData(minDistanceObj));
            }
            if (member->hasLoc()) {
                _invalidationMap[member->loc] = *out;
            }
        }

        return PlanStage::NEED_TIME;
    }

    // Fill _results with the next shell of results.  We may have to search several times to do
    // this.  If _results.empty() after calling fillResults, there are no more possible results.
    void S2NearCursor::fillResults() {
        verify(_results.empty());
        if (_innerRadius >= _outerRadius) { return; }
        if (_innerRadius > _maxDistance) { return; }

        // We iterate until 1. our search radius is too big or 2. we find results.
        do {
            // Some of these arguments are opaque, look at the definitions of the involved classes.
            FieldRangeSet frs(_details->parentNS().c_str(), makeFRSObject(), false, false);
            shared_ptr<FieldRangeVector> frv(new FieldRangeVector(frs, _specForFRV, 1));
            scoped_ptr<BtreeCursor> cursor(BtreeCursor::make(nsdetails(_details->parentNS().c_str()),
                                                             *_details, frv, 0, 1));

            // Do the actual search through this annulus.
            size_t considered = 0;
            for (; cursor->ok(); cursor->advance()) {
                ++_nscanned;
                ++considered;

                MatchDetails details;
                bool matched = _matcher->matchesCurrent(cursor.get(), &details);
                if (!matched) { continue; }

                const BSONObj& indexedObj = cursor->currLoc().obj();

                size_t geoFieldsInRange = 0;
                double minMatchingDistance = 1e20;

                // Calculate the distance from our query point(s) to the geo field(s).
                for (size_t i = 0; i < _fields.size(); ++i) {
                    const GeoQueryField& field = _fields[i];

                    BSONElementSet geoFieldElements;
                    indexedObj.getFieldsDotted(field.field, geoFieldElements);
                    if (geoFieldElements.empty()) { continue; }

                    S2Point us = field.getCentroid();
                    for (BSONElementSet::iterator oi = geoFieldElements.begin();
                            oi != geoFieldElements.end(); ++oi) {
                        const BSONObj &geoObj = oi->Obj();
                        double dist = -1;
                        S2Point them;
                        if (GeoJSONParser::isPolygon(geoObj)) {
                            S2Polygon shape;
                            GeoJSONParser::parsePolygon(geoObj, &shape);
                            them = shape.Project(us);
                        } else if (GeoJSONParser::isLineString(geoObj)) {
                            S2Polyline shape;
                            GeoJSONParser::parseLineString(geoObj, &shape);
                            int tmp;
                            them = shape.Project(us, &tmp);
                        } else if (GeoJSONParser::isPoint(geoObj)) {
                            S2Cell point;
                            GeoJSONParser::parsePoint(geoObj, &point);
                            them = point.GetCenter();
                        }
                        S1Angle angle(us, them);
                        dist = angle.radians() * _params.radius;
                        if (dist >= _innerRadius && dist <= _outerRadius) {
                            ++geoFieldsInRange;
                            minMatchingDistance = min(dist, minMatchingDistance);
                        }
                    }
                }
                if (_fields.size() == geoFieldsInRange) {
                    if (_returned.end() == _returned.find(cursor->currLoc())) {
                        _results.push(Result(cursor->currLoc(), cursor->currKey(), minMatchingDistance));
                    }
                }
            }
            if (_results.empty()) {
                _radiusIncrement *= 2;
                nextAnnulus();
            }
        } while (_results.empty() && _innerRadius < M_PI  * _params.radius);
        // TODO: consider shrinking _radiusIncrement if _results.size() meets some criteria.
    }

    // Fill _results with the next shell of results.  We may have to search several times to do
    // this.  If _results.empty() after calling fillResults, there are no more possible results.
    void S2NearCursor::fillResults() {
        verify(_results.empty());
        if (_innerRadius >= _outerRadius) { return; }
        if (_innerRadius > _maxDistance) { return; }

        // We iterate until 1. our search radius is too big or 2. we find results.
        do {
            // Some of these arguments are opaque, look at the definitions of the involved classes.
            FieldRangeSet frs(_details->parentNS().c_str(), makeFRSObject(), false, false);
            shared_ptr<FieldRangeVector> frv(new FieldRangeVector(frs, _specForFRV, 1));
            scoped_ptr<BtreeCursor> cursor(BtreeCursor::make(nsdetails(_details->parentNS().c_str()),
                                                             *_details, frv, 0, 1));

            // Do the actual search through this annulus.
            size_t considered = 0;
            for (; cursor->ok(); cursor->advance()) {
                ++considered;

                MatchDetails details;
                bool matched = _matcher->matchesCurrent(cursor.get(), &details);
                if (!matched) { continue; }

                const BSONObj& indexedObj = cursor->currLoc().obj();

                size_t geoFieldsInRange = 0;
                double minMatchingDistance = 1e20;

                // Calculate the distance from our query point(s) to the geo field(s).
                // For each geo field in the query...
                for (size_t i = 0; i < _fields.size(); ++i) {
                    const QueryGeometry& field = _fields[i];

                    // Get all the fields with that name from the document.
                    BSONElementSet geoFieldElements;
                    indexedObj.getFieldsDotted(field.field, geoFieldElements, false);
                    if (geoFieldElements.empty()) { continue; }

                    // For each field with that name in the document...
                    for (BSONElementSet::iterator oi = geoFieldElements.begin();
                            oi != geoFieldElements.end(); ++oi) {
                        if (!oi->isABSONObj()) { continue; }
                        double dist = distanceBetween(field, oi->Obj());
                        // If it satisfies our distance criteria...
                        if (dist >= _innerRadius && dist <= _outerRadius) {
                            // Success!  For this field.
                            ++geoFieldsInRange;
                            minMatchingDistance = min(dist, minMatchingDistance);
                        }
                    }
                }
                // If all the geo query fields had something in range
                if (_fields.size() == geoFieldsInRange) {
                    // The result is valid.  We have to de-dup ourselves here.
                    if (_returned.end() == _returned.find(cursor->currLoc())) {
                        _results.push(Result(cursor->currLoc(), cursor->currKey(),
                                             minMatchingDistance));
                    }
                }
            }
            if (_results.empty()) {
                _radiusIncrement *= 2;
                nextAnnulus();
            }
        } while (_results.empty()
                 && _innerRadius < _maxDistance
                 && _innerRadius < _outerRadius
                 && _innerRadius < M_PI  * _params.radius);
        // TODO: consider shrinking _radiusIncrement if _results.size() meets some criteria.
    }

    bool run2DSphereGeoNear(const IndexDetails &id, BSONObj& cmdObj, string& errmsg,
                            BSONObjBuilder& result) {
        S2IndexType *idxType = static_cast<S2IndexType*>(id.getSpec().getType());
        verify(&id == idxType->getDetails());

        // We support both "num" and "limit" options to control limit
        int numWanted = 100;
        const char* limitName = cmdObj["num"].isNumber() ? "num" : "limit";
        if (cmdObj[limitName].isNumber()) {
            numWanted = cmdObj[limitName].numberInt();
            verify(numWanted >= 0);
        }

        // Don't count any docs twice.  Isn't this default behavior?  Or will yields screw this up?
        //bool uniqueDocs = false;
        //if (!cmdObj["uniqueDocs"].eoo()) uniqueDocs = cmdObj["uniqueDocs"].trueValue();

        // Add the location information to each result as a field with name 'loc'.
        bool includeLocs = false;
        if (!cmdObj["includeLocs"].eoo()) includeLocs = cmdObj["includeLocs"].trueValue();

        // The actual query point
        uassert(16551, "'near' param missing/invalid", !cmdObj["near"].eoo());
        BSONObj nearObj = cmdObj["near"].embeddedObject();

        // nearObj must be a point.
        uassert(16571, "near must be called with a point, called with " + nearObj.toString(),
                GeoParser::isPoint(nearObj));

        // The non-near query part.
        BSONObj query;
        if (cmdObj["query"].isABSONObj())
            query = cmdObj["query"].embeddedObject();

        // The farthest away we're willing to look.
        double maxDistance = numeric_limits<double>::max();
        if (cmdObj["maxDistance"].isNumber())
            maxDistance = cmdObj["maxDistance"].number();

        vector<string> geoFieldNames;
        idxType->getGeoFieldNames(&geoFieldNames);
        uassert(16552, "geoNear called but no indexed geo fields?", 1 == geoFieldNames.size());
        QueryGeometry queryGeo(geoFieldNames[0]);
        uassert(16553, "geoNear couldn't parse geo: " + nearObj.toString(), queryGeo.parseFrom(nearObj));
        vector<QueryGeometry> regions;
        regions.push_back(queryGeo);

        scoped_ptr<S2NearCursor> cursor(new S2NearCursor(idxType->keyPattern(), idxType->getDetails(),
                                                         query, regions, idxType->getParams(),
                                                         numWanted, maxDistance));

        double totalDistance = 0;
        int results = 0;
        BSONObjBuilder resultBuilder(result.subarrayStart("results"));
        double farthestDist = 0;

        while (cursor->ok()) {
            double dist = cursor->currentDistance();
            totalDistance += dist;
            if (dist > farthestDist) { farthestDist = dist; }

            BSONObjBuilder oneResultBuilder(resultBuilder.subobjStart(BSONObjBuilder::numStr(results)));
            oneResultBuilder.append("dis", dist);
            if (includeLocs) {
                BSONElementSet geoFieldElements;
                cursor->current().getFieldsDotted(geoFieldNames[0], geoFieldElements, false);
                for (BSONElementSet::iterator oi = geoFieldElements.begin();
                        oi != geoFieldElements.end(); ++oi) {
                    if (oi->isABSONObj()) {
                        oneResultBuilder.appendAs(*oi, "loc");
                    }
                }
            }

            oneResultBuilder.append("obj", cursor->current());
            oneResultBuilder.done();
            ++results;
            cursor->advance();
        }

        resultBuilder.done();

        BSONObjBuilder stats(result.subobjStart("stats"));
        stats.append("time", cc().curop()->elapsedMillis());
        stats.appendNumber("nscanned", cursor->nscanned());
        stats.append("avgDistance", totalDistance / results);
        stats.append("maxDistance", farthestDist);
        stats.done();

        return true;
    }

    // Fill _results with the next shell of results.  We may have to search several times to do
    // this.  If _results.empty() after calling fillResults, there are no more possible results.
    void S2NearCursor::fillResults() {
        verify(_results.empty());
        if (_innerRadius >= _outerRadius) { return; }
        if (_innerRadius > _maxDistance) { return; }
        if (0 == _numToReturn) { return; }

        // We iterate until 1. our search radius is too big or 2. we find results.
        do {
            // Some of these arguments are opaque, look at the definitions of the involved classes.
            FieldRangeSet frs(_details->parentNS().c_str(), makeFRSObject(), false, false);
            shared_ptr<FieldRangeVector> frv(new FieldRangeVector(frs, _specForFRV, 1));
            scoped_ptr<BtreeCursor> cursor(BtreeCursor::make(nsdetails(_details->parentNS()),
                                                             *_details, frv, 0, 1));

            // The cursor may return the same obj more than once for a given
            // FRS, so we make sure to only consider it once in any given annulus.
            //
            // We don't want this outside of the 'do' loop because the covering
            // for an annulus may return an object whose distance to the query
            // point is actually contained in a subsequent annulus.  If we
            // didn't consider every object in a given annulus we might miss
            // the point.
            //
            // We don't use a global 'seen' because we get that by requiring
            // the distance from the query point to the indexed geo to be
            // within our 'current' annulus, and I want to dodge all yield
            // issues if possible.
            set<DiskLoc> seen;

            LOG(1) << "looking at annulus from " << _innerRadius << " to " << _outerRadius << endl;
            // Do the actual search through this annulus.
            for (; cursor->ok(); cursor->advance()) {
                ++_nscanned;
                if (seen.end() != seen.find(cursor->currLoc())) { continue; }
                seen.insert(cursor->currLoc());

                // Match against non-indexed fields.
                ++_matchTested;
                MatchDetails details;
                bool matched = _matcher->matchesCurrent(cursor.get(), &details);
                if (!matched) { continue; }

                const BSONObj& indexedObj = cursor->currLoc().obj();

                ++_geoTested;
                // Match against indexed geo fields.
                size_t geoFieldsMatched = 0;
                // OK, cool, non-geo match satisfied.  See if the object actually overlaps w/the geo
                // query fields.
                for (size_t i = 0; i < _indexedGeoFields.size(); ++i) {
                    BSONElementSet geoFieldElements;
                    indexedObj.getFieldsDotted(_indexedGeoFields[i].getField(), geoFieldElements,
                                               false);
                    if (geoFieldElements.empty()) { continue; }

                    bool match = false;

                    for (BSONElementSet::iterator oi = geoFieldElements.begin();
                            !match && (oi != geoFieldElements.end()); ++oi) {
                        if (!oi->isABSONObj()) { continue; }
                        const BSONObj &geoObj = oi->Obj();
                        GeometryContainer geoContainer;
                        uassert(16699, "ill-formed geometry: " + geoObj.toString(),
                                geoContainer.parseFrom(geoObj));
                        match = _indexedGeoFields[i].satisfiesPredicate(geoContainer);
                    }

                    if (match) { ++geoFieldsMatched; }
                }

                if (geoFieldsMatched != _indexedGeoFields.size()) { continue; }

                // Finally, see if the item is in our search annulus.
                size_t geoFieldsInRange = 0;
                double minMatchingDistance = 1e20;

                // Get all the fields with that name from the document.
                BSONElementSet geoFieldElements;
                indexedObj.getFieldsDotted(_nearQuery.field, geoFieldElements, false);
                if (geoFieldElements.empty()) { continue; }

                // For each field with that name in the document...
                for (BSONElementSet::iterator oi = geoFieldElements.begin();
                        oi != geoFieldElements.end(); ++oi) {
                    if (!oi->isABSONObj()) { continue; }
                    double dist = distanceTo(oi->Obj());
                    // If it satisfies our distance criteria...
                    if (dist >= _innerRadius && dist <= _outerRadius) {
                        // Success!  For this field.
                        ++geoFieldsInRange;
                        minMatchingDistance = min(dist, minMatchingDistance);
                    }
                }
                // If all the geo query fields had something in range
                if (geoFieldsInRange > 0) {
                    // The result is valid.  We have to de-dup ourselves here.
                    if (_returned.end() == _returned.find(cursor->currLoc())) {
                        _results.push(Result(cursor->currLoc(), cursor->currKey(),
//.........这里部分代码省略.........