// 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 {

using std::string;

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
