diff options
Diffstat (limited to 'src/mongo/db/fts/fts_element_iterator.cpp')
| -rw-r--r-- | src/mongo/db/fts/fts_element_iterator.cpp | 186 |
1 files changed, 186 insertions, 0 deletions
diff --git a/src/mongo/db/fts/fts_element_iterator.cpp b/src/mongo/db/fts/fts_element_iterator.cpp new file mode 100644 index 00000000000..477822371a4 --- /dev/null +++ b/src/mongo/db/fts/fts_element_iterator.cpp @@ -0,0 +1,186 @@ +// fts_element_iterator.cpp +/** +* Copyright (C) 2014 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. +*/ + +#include "mongo/db/fts/fts_element_iterator.h" +#include "mongo/db/fts/fts_spec.h" +#include "mongo/db/fts/fts_util.h" +#include "mongo/util/mongoutils/str.h" +#include "mongo/util/stringutils.h" + +#include <stack> + +namespace mongo { + + namespace fts { + + extern const double DEFAULT_WEIGHT; + extern const double MAX_WEIGHT; + + std::ostream& operator<<( std::ostream& os, FTSElementIterator::FTSIteratorFrame& frame ) { + BSONObjIterator it = frame._it; + return os << "FTSIteratorFrame[" + " element=" << (*it).toString() << + ", _language=" << frame._language->str() << + ", _parentPath=" << frame._parentPath << + ", _isArray=" << frame._isArray << "]"; + } + + FTSElementIterator::FTSElementIterator( const FTSSpec& spec, const BSONObj& obj ) + : _frame( obj, spec, &spec.defaultLanguage(), "", false ), + _spec( spec ), + _currentValue( advance() ) + { } + + namespace { + /** Check for exact match or path prefix match. */ + inline bool _matchPrefix( const string& dottedName, const string& weight ) { + if ( weight == dottedName ) { + return true; + } + return mongoutils::str::startsWith( weight, dottedName + '.' ); + } + } + + bool FTSElementIterator::more() { + //_currentValue = advance(); + return _currentValue.valid(); + } + + FTSIteratorValue FTSElementIterator::next() { + FTSIteratorValue result = _currentValue; + _currentValue = advance(); + return result; + } + + /** + * Helper method: + * if (current object iterator not exhausted) return true; + * while (frame stack not empty) { + * resume object iterator popped from stack; + * if (resumed iterator not exhausted) return true; + * } + * return false; + */ + bool FTSElementIterator::moreFrames() { + if (_frame._it.more()) return true; + while (!_frameStack.empty()) { + _frame = _frameStack.top(); + _frameStack.pop(); + if (_frame._it.more()) { + return true; + } + } + return false; + } + + FTSIteratorValue FTSElementIterator::advance() { + while ( moreFrames() ) { + + BSONElement elem = _frame._it.next(); + string fieldName = elem.fieldName(); + + // Skip "language" specifier fields if wildcard. + if ( _spec.wildcard() && _spec.languageOverrideField() == fieldName ) { + continue; + } + + // Compose the dotted name of the current field: + // 1. parent path empty (top level): use the current field name + // 2. parent path non-empty and obj is an array: use the parent path + // 3. parent path non-empty and obj is a sub-doc: append field name to parent path + string dottedName = ( _frame._parentPath.empty() ? fieldName + : _frame._isArray ? _frame._parentPath + : _frame._parentPath + '.' + fieldName ); + + // Find lower bound of dottedName in _weights. lower_bound leaves us at the first + // weight that could possibly match or be a prefix of dottedName. And if this + // element fails to match, then no subsequent weight can match, since the weights + // are lexicographically ordered. + Weights::const_iterator i = _spec.weights().lower_bound( elem.type() == Object + ? dottedName + '.' + : dottedName ); + + // possibleWeightMatch is set if the weight map contains either a match or some item + // lexicographically larger than fieldName. This boolean acts as a guard on + // dereferences of iterator 'i'. + bool possibleWeightMatch = ( i != _spec.weights().end() ); + + // Optimize away two cases, when not wildcard: + // 1. lower_bound seeks to end(): no prefix match possible + // 2. lower_bound seeks to a name which is not a prefix + if ( !_spec.wildcard() ) { + if ( !possibleWeightMatch ) { + continue; + } + else if ( !_matchPrefix( dottedName, i->first ) ) { + continue; + } + } + + // Is the current field an exact match on a weight? + bool exactMatch = ( possibleWeightMatch && i->first == dottedName ); + double weight = ( possibleWeightMatch ? i->second : DEFAULT_WEIGHT ); + + switch ( elem.type() ) { + case String: + // Only index strings on exact match or wildcard. + if ( exactMatch || _spec.wildcard() ) { + return FTSIteratorValue( elem.valuestr(), _frame._language, weight ); + } + break; + + case Object: + // Only descend into a sub-document on proper prefix or wildcard. Note that + // !exactMatch is a sufficient test for proper prefix match, because of + // if ( !matchPrefix( dottedName, i->first ) ) continue; + // block above. + if ( !exactMatch || _spec.wildcard() ) { + _frameStack.push( _frame ); + _frame = FTSIteratorFrame( elem.Obj(), _spec, _frame._language, dottedName, false ); + } + break; + + case Array: + // Only descend into arrays from non-array parents or on wildcard. + if ( !_frame._isArray || _spec.wildcard() ) { + _frameStack.push( _frame ); + _frame = FTSIteratorFrame( elem.Obj(), _spec, _frame._language, dottedName, true ); + } + break; + + default: + // Skip over all other BSON types. + break; + } + } + return FTSIteratorValue(); // valid()==false + } + + } // namespace fts +} // namespace mongo |