<commit_before>/*
 * PatternMatchEngine.cc
 *
 * Copyright (C) 2008,2009,2011,2014 <NAME>
 *
 * Author: <NAME> <<EMAIL>>  February 2008
 *
 * 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/util/oc_assert.h>
#include <opencog/util/foreach.h>
#include <opencog/atomspace/Foreach.h>
#include <opencog/atomspace/ForeachTwo.h>

#include "PatternMatchEngine.h"
#include "PatternUtils.h"

using namespace opencog;

// #define DEBUG 1
#ifdef WIN32
#if DEBUG
	#define dbgprt printf
#else
	// something better?
	#define dbgprt
#endif
#else
#if DEBUG
	#define dbgprt(f, varargs...) printf(f, ##varargs)
#else
	#define dbgprt(f, varargs...)
#endif
#endif

bool PatternMatchEngine::prt(Handle& h)
{
	std::string str = h->toShortString();
	printf ("%s\n", str.c_str());
	return false;
}

inline void PatternMatchEngine::prtmsg(const char * msg, Handle& h)
{
#ifdef DEBUG
	if (h == Handle::UNDEFINED) {
		printf ("%s (invalid handle)\n", msg);
		return;
	}
	std::string str = h->toShortString();
	printf ("%s %s\n", msg, str.c_str());
#endif
}

/* Reset the current variable grounding to the last grounding pushed
 * onto the stack. */
#define POPGND(soln,stack) {         \
   if (stack.empty()) {              \
      printf("ERROR: Unbalanced stack pop!\n"); \
      soln.clear();                  \
   }                                 \
   else soln = stack.top();          \
   stack.pop();                      \
}

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

/**
 * tree_compare compares two trees, side-by-side.
 *
 * Compare two incidence trees, side-by-side. It is assumed that the
 * first of these is a clause in the predicate, and so the comparison
 * is between the clause, and a candidate grounding.
 *
 * The graph/tree refered to here is the incidence graph/tree (aka
 * Levi graph) of the hypergraph (and not the hypergraph itself).
 * The incidence graph is given by the "outgoing set" of the atom.
 *
 * This routine is recursive, calling itself on each subtree of the
 * predicate clause, performing comparisions until a match is found
 * (or not found).
 *
 * Return true if there's a mis-match. The goal here is to walk over
 * the entire tree, without mismatches.  Since a return value of true
 * stops the iteration, true is used to signal a mismatch.
 */
bool PatternMatchEngine::tree_compare(Handle hp, Handle hg)
{
	// Handle hp is from the pattern clause, and it might be one
	// of the bound variables. If so, then declare a match.
	if (_bound_vars.end() != _bound_vars.find(hp))
	{
		// But... if handle hg happens to also be a bound var,
		// then its a mismatch.
		if (_bound_vars.end() != _bound_vars.find(hg)) return true;

		// If we already have a grounding for this variable, the new
		// proposed grounding must match the existing one. Such multiple
		// groundings can occur when traversing graphs with loops in them.
		Handle gnd(var_grounding[hp]);
		if (Handle::UNDEFINED != gnd) {
			return (gnd != hg);
		}

		// VariableNode had better be an actual node!
		// If it's not then we are very very confused ...
		NodePtr np(NodeCast(hp));
		OC_ASSERT (NULL != np,
		      "ERROR: expected variable to be a node, got this: %s\n",
				hp->toShortString().c_str());

		// Else, we have a candidate grounding for this variable.
		// The node_match may implement some tighter variable check,
		// e.g. making sure that grounding is of some certain type.
		if (pmc->variable_match (hp,hg)) return true;

		// Make a record of it.
		dbgprt("Found grounding of variable:\n");
		prtmsg("$$ variable:    ", hp);
		prtmsg("$$ ground term: ", hg);
		var_grounding[hp] = hg;
		return false;
	}

	// If they're the same atom, then clearly they match.
	// ... but only if hg is not a subclause of the current clause.
	if ((hp == hg) && (hg != curr_pred_handle))
	{
		var_grounding[hp] = hg;
		return false;
	}

	// If both are links, compare them as such.
	LinkPtr lp(LinkCast(hp));
	LinkPtr lg(LinkCast(hg));
	if (lp and lg)
	{
		// Let the callback perform basic checking.
		bool mismatch = pmc->link_match(lp, lg);
		if (mismatch) return true;

		dbgprt("depth=%d\n", depth);
		prtmsg("> tree_compare", hp);
		prtmsg(">           to", hg);

		// If the two links are both ordered, its enough to compare
		// them "side-by-side"; the foreach_atom_pair iterator does
		// this. If they are un-ordered, then we have to compare (at
		// most) every possible permutation.
		//
		Type tp = hp->getType();
		if (classserver().isA(tp, GREATER_THAN_LINK))
		{
			return false;
		}
		if (classserver().isA(tp, ORDERED_LINK))
		{
			LinkPtr lp(LinkCast(hp));
			LinkPtr lg(LinkCast(hg));
			const std::vector<Handle> &osp = lp->getOutgoingSet();
			const std::vector<Handle> &osg = lg->getOutgoingSet();

			// The recursion step: traverse down the tree.
			// In principle, we could/should push the current groundings
			// onto the stack before recursing, and then pop them off on
			// return.  Failure to do so could leave some bogus groundings,
			// sitting around, i.e. groundings that were found during
			// recursion but then discarded due to a later mistmatch.
			//
			// In practice, I was unable to come up with any test case
			// where this mattered; any bogus groundings eventually get
			// replaced by valid ones.  Thus, we save some unknown amount<commit_msg>Bug fix<commit_after>/*
 * PatternMatchEngine.cc
 *
 * Copyright (C) 2008,2009,2011,2014 <NAME>
 *
 * Author: <NAME> <<EMAIL>>  February 2008
 *
 * 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/util/oc_assert.h>
#include <opencog/util/foreach.h>
#include <opencog/atomspace/Foreach.h>
#include <opencog/atomspace/ForeachTwo.h>

#include "PatternMatchEngine.h"
#include "PatternUtils.h"

using namespace opencog;

// #define DEBUG 1
#ifdef WIN32
#if DEBUG
	#define dbgprt printf
#else
	// something better?
	#define dbgprt
#endif
#else
#if DEBUG
	#define dbgprt(f, varargs...) printf(f, ##varargs)
#else
	#define dbgprt(f, varargs...)
#endif
#endif

bool PatternMatchEngine::prt(Handle& h)
{
	std::string str = h->toShortString();
	printf ("%s\n", str.c_str());
	return false;
}

inline void PatternMatchEngine::prtmsg(const char * msg, Handle& h)
{
#ifdef DEBUG
	if (h == Handle::UNDEFINED) {
		printf ("%s (invalid handle)\n", msg);
		return;
	}
	std::string str = h->toShortString();
	printf ("%s %s\n", msg, str.c_str());
#endif
}

/* Reset the current variable grounding to the last grounding pushed
 * onto the stack. */
#define POPGND(soln,stack) {         \
   if (stack.empty()) {              \
      printf("ERROR: Unbalanced stack pop!\n"); \
      soln.clear();                  \
   }                                 \
   else soln = stack.top();          \
   stack.pop();                      \
}

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

/**
 * tree_compare compares two trees, side-by-side.
 *
 * Compare two incidence trees, side-by-side. It is assumed that the
 * first of these is a clause in the predicate, and so the comparison
 * is between the clause, and a candidate grounding.
 *
 * The graph/tree refered to here is the incidence graph/tree (aka
 * Levi graph) of the hypergraph (and not the hypergraph itself).
 * The incidence graph is given by the "outgoing set" of the atom.
 *
 * This routine is recursive, calling itself on each subtree of the
 * predicate clause, performing comparisions until a match is found
 * (or not found).
 *
 * Return true if there's a mis-match. The goal here is to walk over
 * the entire tree, without mismatches.  Since a return value of true
 * stops the iteration, true is used to signal a mismatch.
 */
bool PatternMatchEngine::tree_compare(Handle hp, Handle hg)
{
	// Handle hp is from the pattern clause, and it might be one
	// of the bound variables. If so, then declare a match.
	if (_bound_vars.end() != _bound_vars.find(hp))
	{
		// But... if handle hg happens to also be a bound var,
		// then its a mismatch.
		if (_bound_vars.end() != _bound_vars.find(hg)) return true;

		// If we already have a grounding for this variable, the new
		// proposed grounding must match the existing one. Such multiple
		// groundings can occur when traversing graphs with loops in them.
		Handle gnd(var_grounding[hp]);
		if (Handle::UNDEFINED != gnd) {
			return (gnd != hg);
		}

		// VariableNode had better be an actual node!
		// If it's not then we are very very confused ...
		NodePtr np(NodeCast(hp));
		OC_ASSERT (NULL != np,
		      "ERROR: expected variable to be a node, got this: %s\n",
				hp->toShortString().c_str());

		// Else, we have a candidate grounding for this variable.
		// The node_match may implement some tighter variable check,
		// e.g. making sure that grounding is of some certain type.
		if (pmc->variable_match (hp,hg)) return true;

		// Make a record of it.
		dbgprt("Found grounding of variable:\n");
		prtmsg("$$ variable:    ", hp);
		prtmsg("$$ ground term: ", hg);
		var_grounding[hp] = hg;
		return false;
	}

	// If they're the same atom, then clearly they match.
	// ... but only if hg is not a subclause of the current clause.
	if ((hp == hg) && (hg != curr_pred_handle))
	{
		var_grounding[hp] = hg;
		return false;
	}

	// If both are links, compare them as such.
	LinkPtr lp(LinkCast(hp));
	LinkPtr lg(LinkCast(hg));
	if (lp and lg)
	{
		// Let the callback perform basic checking.
		bool mismatch = pmc->link_match(lp, lg);
		if (mismatch) return true;

		dbgprt("depth=%d\n", depth);
		prtmsg("> tree_compare", hp);
		prtmsg(">           to", hg);

		// If the two links are both ordered, its enough to compare
		// them "side-by-side"; the foreach_atom_pair iterator does
		// this. If they are un-ordered, then we have to compare (at
		// most) every possible permutation.
		//
		Type tp = hp->getType();
		if (classserver().isA(tp, VIRTUAL_LINK))
		{
			throw InvalidParamException(TRACE_INFO, "Unexpected virtual link found!");
			return false;
		}
		if (classserver().isA(tp, ORDERED_LINK))
		{
			LinkPtr lp(LinkCast(hp));
			LinkPtr lg(LinkCast(hg));
			const std::vector<Handle> &osp = lp->getOutgoingSet();
			const std::vector<Handle> &osg = lg->getOutgoingSet();

			// The recursion step: traverse down the tree.
			// In principle, we could/should push the current groundings
			// onto the stack before recursing, and then pop them off on
			// return.  Failure to do so could leave some bogus groundings,
			// sitting around, i.e. groundings that were found during
			// recursion but then discarded due to a later mistmatch.
			//
			// In practice, I was unable to come up with any test case
			// where this mattered; any bogus groundings eventually get
			// replaced by valid ones.  Thus, we save some unknown amount
{'fraction_non_alphanumeric': 0.12200778596869047, 'fraction_numerical': 0.005798061790772799, 'mean_word_length': 3.2025757048381482, 'pattern_counts': {'":': 0, '<': 23, '<?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': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4105501', 'n_tokens_mistral': 4027, 'n_tokens_neox': 3702, 'n_words': 1468}