<commit_before>/*
 * InitiateSearchCB.cc
 *
 * Copyright (C) 2015 <NAME>
 *
 * Author: <NAME> <<EMAIL>>  April 2015
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License v3 as
 * published by the Free Software Foundation and including the exceptions
 * at http://opencog.org/wiki/Licenses
 *
 * 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 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, write to:
 * Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

#include <opencog/atomspace/AtomSpace.h>

#include <opencog/atoms/bind/PatternLink.h>
#include <opencog/atoms/core/DefineLink.h>
#include <opencog/atoms/core/LambdaLink.h>
#include <opencog/atoms/execution/EvaluationLink.h>
#include <opencog/atomutils/FindUtils.h>
#include <opencog/atomutils/Substitutor.h>

#include "InitiateSearchCB.h"
#include "PatternMatchEngine.h"

using namespace opencog;

/* ======================================================== */

InitiateSearchCB::InitiateSearchCB(AtomSpace* as) :
	_classserver(classserver()),
	_variables(NULL),
	_pattern(NULL),
	_type_restrictions(NULL),
	_dynamic(NULL),
	_as(as)
{
}

void InitiateSearchCB::set_pattern(const Variables& vars,
                                   const Pattern& pat)
{
	_search_fail = false;

	_variables = &vars;
	_pattern = &pat;
	_type_restrictions = &vars.typemap;
	_dynamic = &pat.evaluatable_terms;
}


/* ======================================================== */

// Find a good place to start the search.
//
// The handle h points to a clause.  In principle, it is enough to
// simply find a constant in the clause, and just start there. In
// practice, this can be an awful way to do things. So, for example,
// most "typical" clauses will be of the form
//
//    EvaluationLink
//        PredicateNode "blah"
//        ListLink
//            VariableNode $var
//            ConceptNode  "item"
//
// Typically, the incoming set for "blah" will be huge, so starting the
// search there would be a poor choice. Typically, the incoming set to
// "item" will be much smaller, and so makes a better choice.  The code
// below tries to pass over "blah" and pick "item" instead.  It does so
// by comparing the size of the incoming sets of the two constants, and
// picking the one with the smaller ("thinner") incoming set. Note that
// this is a form of "greedy" search.
//
// Atoms that are inside of dynamically-evaluatable terms are not
// considered. That's because groundings for such terms might not exist
// in the atomspace, so a search that starts there is doomed to fail.
//
// Note that the algo explores the clause to its greatest depth. That's
// OK, because typical clauses are never very deep.
//
// A variant of this algo could incorporate the Attentional focus
// into the "thinnest" calculation, so that only high-AF atoms are
// considered.
//
// Note that the size of the incoming set really is a better measure,
// and not the depth.  So, for example, if "item" has a huge incoming
// set, but "blah" does not, then "blah" is a much better place to
// start.
//
// size_t& depth will be set to the depth of the thinnest constant found.
// Handle& start will be set to the link containing that constant.
// size_t& width will be set to the incoming-set size of the thinnest
//               constant found.
// The returned value will be the constant at which to start the search.
// If no constant is found, then the returned value is the undefnied
// handle.
//

Handle
InitiateSearchCB::find_starter(const Handle& h, size_t& depth,
                                     Handle& startrm, size_t& width)
{
	// If its a node, then we are done.
	Type t = h->getType();
	if (_classserver.isNode(t)) {
		if (t != VARIABLE_NODE) {
			width = h->getIncomingSetSize();
			startrm = h; // XXX wtf ???
			return h;
		}
		return Handle::UNDEFINED;
	}

	// If its a link, then find recursively
	return find_starter_recursive(h, depth, startrm, width);
}

Handle
InitiateSearchCB::find_starter_recursive(const Handle& h, size_t& depth,
                                         Handle& startrm, size_t& width)
{
	// If its a node, then we are done. Don't modify either depth or
	// start.
	Type t = h->getType();
	if (_classserver.isNode(t)) {
		if (t != VARIABLE_NODE) {
			width = h->getIncomingSetSize();
			return h;
		}
		return Handle::UNDEFINED;
	}

	// Ignore all dynamically-evaluatable links up front.
	if (_dynamic->find(h) != _dynamic->end())
		return Handle::UNDEFINED;

	// Iterate over all the handles in the outgoing set.
	// Find the deepest one that contains a constant, and start
	// the search there.  If there are two at the same depth,
	// then start with the skinnier one.
	size_t deepest = depth;
	startrm = Handle::UNDEFINED;
	Handle hdeepest(Handle::UNDEFINED);
	size_t thinnest = SIZE_MAX;

	LinkPtr ll(LinkCast(h));
	for (Handle hunt : ll->getOutgoingSet())
	{
		size_t brdepth = depth + 1;
		size_t brwid = SIZE_MAX;
		Handle sbr(h);

		// Blow past the QuoteLinks, since they just screw up the search start.
		if (QUOTE_LINK == hunt->getType())
			hunt = LinkCast(hunt)->getOutgoingAtom(0);

		Handle s(find_starter_recursive(hunt, brdepth, sbr, brwid));<commit_msg>Fix up pattern search initiation<commit_after>/*
 * InitiateSearchCB.cc
 *
 * Copyright (C) 2015 <NAME>
 *
 * Author: <NAME> <<EMAIL>>  April 2015
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License v3 as
 * published by the Free Software Foundation and including the exceptions
 * at http://opencog.org/wiki/Licenses
 *
 * 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 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, write to:
 * Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

#include <opencog/atomspace/AtomSpace.h>

#include <opencog/atoms/bind/PatternLink.h>
#include <opencog/atoms/core/DefineLink.h>
#include <opencog/atoms/core/LambdaLink.h>
#include <opencog/atoms/execution/EvaluationLink.h>
#include <opencog/atomutils/FindUtils.h>
#include <opencog/atomutils/Substitutor.h>

#include "InitiateSearchCB.h"
#include "PatternMatchEngine.h"

using namespace opencog;

/* ======================================================== */

InitiateSearchCB::InitiateSearchCB(AtomSpace* as) :
	_classserver(classserver()),
	_variables(NULL),
	_pattern(NULL),
	_type_restrictions(NULL),
	_dynamic(NULL),
	_as(as)
{
}

void InitiateSearchCB::set_pattern(const Variables& vars,
                                   const Pattern& pat)
{
	_search_fail = false;

	_variables = &vars;
	_pattern = &pat;
	_type_restrictions = &vars.typemap;
	_dynamic = &pat.evaluatable_terms;
}


/* ======================================================== */

// Find a good place to start the search.
//
// The handle h points to a clause.  In principle, it is enough to
// simply find a constant in the clause, and just start there. In
// practice, this can be an awful way to do things. So, for example,
// most "typical" clauses will be of the form
//
//    EvaluationLink
//        PredicateNode "blah"
//        ListLink
//            VariableNode $var
//            ConceptNode  "item"
//
// Typically, the incoming set for "blah" will be huge, so starting the
// search there would be a poor choice. Typically, the incoming set to
// "item" will be much smaller, and so makes a better choice.  The code
// below tries to pass over "blah" and pick "item" instead.  It does so
// by comparing the size of the incoming sets of the two constants, and
// picking the one with the smaller ("thinner") incoming set. Note that
// this is a form of "greedy" search.
//
// Atoms that are inside of dynamically-evaluatable terms are not
// considered. That's because groundings for such terms might not exist
// in the atomspace, so a search that starts there is doomed to fail.
//
// Note that the algo explores the clause to its greatest depth. That's
// OK, because typical clauses are never very deep.
//
// A variant of this algo could incorporate the Attentional focus
// into the "thinnest" calculation, so that only high-AF atoms are
// considered.
//
// Note that the size of the incoming set really is a better measure,
// and not the depth.  So, for example, if "item" has a huge incoming
// set, but "blah" does not, then "blah" is a much better place to
// start.
//
// size_t& depth will be set to the depth of the thinnest constant found.
// Handle& start will be set to the link containing that constant.
// size_t& width will be set to the incoming-set size of the thinnest
//               constant found.
// The returned value will be the constant at which to start the search.
// If no constant is found, then the returned value is the undefnied
// handle.
//

Handle
InitiateSearchCB::find_starter(const Handle& h, size_t& depth,
                                     Handle& startrm, size_t& width)
{
	// If its a node, then we are done.
	Type t = h->getType();
	if (_classserver.isNode(t))
	{
		if (VARIABLE_NODE != t and GLOB_NODE != t)
		{
			width = h->getIncomingSetSize();
			startrm = h; // XXX wtf ???
			return h;
		}
		return Handle::UNDEFINED;
	}

	// If its a link, then find recursively
	return find_starter_recursive(h, depth, startrm, width);
}

Handle
InitiateSearchCB::find_starter_recursive(const Handle& h, size_t& depth,
                                         Handle& startrm, size_t& width)
{
	// If its a node, then we are done. Don't modify either depth or
	// start.
	Type t = h->getType();
	if (_classserver.isNode(t))
	{
		if (VARIABLE_NODE != t and GLOB_NODE != t)
		{
			width = h->getIncomingSetSize();
			return h;
		}
		return Handle::UNDEFINED;
	}

	// Ignore all dynamically-evaluatable links up front.
	if (_dynamic->find(h) != _dynamic->end())
		return Handle::UNDEFINED;

	// Iterate over all the handles in the outgoing set.
	// Find the deepest one that contains a constant, and start
	// the search there.  If there are two at the same depth,
	// then start with the skinnier one.
	size_t deepest = depth;
	startrm = Handle::UNDEFINED;
	Handle hdeepest(Handle::UNDEFINED);
	size_t thinnest = SIZE_MAX;

	LinkPtr ll(LinkCast(h));
	for (Handle hunt : ll->getOutgoingSet())
	{
		size_t brdepth = depth + 1;
		size_t brwid = SIZE_MAX;
		Handle sbr(h);

		// Blow past the QuoteLinks, since they just screw up the search start.
		if (QUOTE_LINK == hunt->getType())
			hunt = LinkCast(hunt)->getOutgoingAtom(0);

		Handle s(find_starter_recursive(hunt, brdepth, sbr, brwid));
{'fraction_non_alphanumeric': 0.11893443358148713, 'fraction_numerical': 0.0039465422907884115, 'mean_word_length': 3.3133462282398454, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 43, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5195894', 'n_tokens_mistral': 3528, 'n_tokens_neox': 3338, 'n_words': 1339}