<commit_before>/*
 * BackwardChainer.cc
 *
 * Copyright (C) 2014 <NAME>
 *
 * Author: <NAME> <<EMAIL>>  October 2014
 *
 * 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 "BackwardChainer.h"
#include "BCPatternMatch.h"

#include <opencog/atomutils/AtomUtils.h>
#include <opencog/atoms/bind/BindLink.h>

using namespace opencog;

BackwardChainer::BackwardChainer(AtomSpace* as, std::vector<Rule> rs)
    : _as(as)
{
	_commons = new PLNCommons(_as);
	_rules_set = rs;
}

BackwardChainer::~BackwardChainer()
{
	delete _commons;
}

/**
 * The public entry point for backward chaining.
 *
 * @param init_target  the initial atom to start the chaining
 */
void BackwardChainer::do_chain(Handle init_target)
{
	_chaining_result.clear();
	_chaining_result = do_bc(init_target);

	//clean variables
	remove_generated_rules();
}

map<Handle, HandleSeq>& BackwardChainer::get_chaining_result()
{
	return _chaining_result;
}


/**
 * The main recursive backward chaining method.
 *
 * @param hgoal  the atom to do backward chaining on
 * @return       ???
 */
map<Handle, HandleSeq> BackwardChainer::do_bc(Handle& hgoal)
{
	// TODO filter grounded representations so the next condition would never be fooled
	// XXX what does the above meant?
	HandleSeq kb_match = filter_grounded_experssions(hgoal);

	if (kb_match.empty())
	{
		logger().debug("[BackwardChainer] Knowledge base empty");

		// find all rules whose implicand can be unified to hgoal
		std::vector<Rule> acceptable_rules = filter_rules(hgoal);

		// if no rules to backward chain on
		if (acceptable_rules.empty())
			return unify_to_empty_set(hgoal);

		// TODO use all rules for found here.
		Rule stadardized_rule = select_rule(rules).standardize_apart();

		//for later removal
//		_bc_generated_rules.push_back(stadardized_rule);

		Handle implicand = stadardized_rule.get_implicand();

		// XXX TODO check unify return value
		map<Handle, HandleSeq> out;
		unify(hgoal, implicand, out);
		_inference_list.push_back(out);

		map<Handle, HandleSeq> solution = apply_rule(implicand, stadardized_rule);
		_inference_list.push_back(solution);

		return ground_target_vars(hgoal, _inference_list);
	}

	vector<map<Handle, HandleSeq>> kb_results;

	map<Handle, HandleSeq> out;
	for (Handle soln : kb_match)
	{
		// XXX TODO check unify return value
		unify(hgoal, soln, out);
		kb_results.push_back(out);
	}

	return ground_target_vars(hgoal, kb_results);
}

/**
 * Apply a rule to an atom.
 *
 * @param htarget   the atom in which the rule will be applied
 * @param rule      the rule to apply    // XXX originally an ImplicationLink
 * @return          ???
 */
map<Handle, HandleSeq> BackwardChainer::apply_rule(Handle& htarget, Rule& rule)
{
	vector<map<Handle, HandleSeq>> results;

	Handle himplicant = rule.get_implicant();

	// if the implicant is a normal link and not a logical conditions
	// eg. (ImplicationLink (Inheritance $x "human") (InheritanceLink "$x" "bipedal"))
	if (find(_logical_link_types.begin(), _logical_link_types.end(), himplicant->getType()) == _logical_link_types.end())
		return do_bc(himplicant);

	// build a tree of the the logical links and premises( premises could by themselves be a logical link) as a map
	map<Handle, HandleSeq> logical_link_premise_map = get_logical_link_premises_map(himplicant);
	map<Handle, map<Handle, HandleSeq>> premise_var_ground_map;

	std::stack<Handle> visited_logical_link;
	HandleSeq evaluated_premises;
	visited_logical_link.push(himplicant); //start from the root

	// go down deep until a logical link maps only to set of premises in the logical_link_premise_map object
	// e.g start from (and x y) instead of (and (and x y) x) and start backward chaining  from there. i.e bottom up.
	while (not visited_logical_link.empty())
	{
		Handle logical_link = visited_logical_link.top();
		visited_logical_link.pop();

		HandleSeq premises = logical_link_premise_map[logical_link];

		// check each premise
		for (Handle premise : premises)
		{
			// if premise already evaluated, skip it
			if (find(evaluated_premises.begin(), evaluated_premises.end(), premise) == evaluated_premises.end())
				continue;

			// if it is another logical link, add it to the stack for future visit
			if (logical_link_premise_map.count(premise) != 0)
			{
				visited_logical_link.push(premise);
				continue;
			}

			auto var_grounding = do_bc(premise);
			premise_var_ground_map[premise] = var_grounding;
			evaluated_premises.push_back(premise);
		}

		// XXX TODO logical_link premises might get evaluated multiple times

		auto v = join_premise_vgrounding_maps(logical_link,	premise_var_ground_map);

		results.push_back(v);		//add to results

		evaluated_premises.push_back(logical_link);
	}

	return ground_target_vars(htarget, results);
}

/**
 * Find all rules in which the input could be an output.
 *
 * @param htarget   an input atom to match<commit_msg>Simplified apply_rule and improve/correct algorithm<commit_after>/*
 * BackwardChainer.cc
 *
 * Copyright (C) 2014 <NAME>
 *
 * Author: <NAME> <<EMAIL>>  October 2014
 *
 * 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 "BackwardChainer.h"
#include "BCPatternMatch.h"

#include <opencog/atomutils/AtomUtils.h>
#include <opencog/atoms/bind/BindLink.h>

using namespace opencog;

BackwardChainer::BackwardChainer(AtomSpace* as, std::vector<Rule> rs)
    : _as(as)
{
	_commons = new PLNCommons(_as);
	_rules_set = rs;
}

BackwardChainer::~BackwardChainer()
{
	delete _commons;
}

/**
 * The public entry point for backward chaining.
 *
 * @param init_target  the initial atom to start the chaining
 */
void BackwardChainer::do_chain(Handle init_target)
{
	_chaining_result.clear();
	_chaining_result = do_bc(init_target);

	//clean variables
	remove_generated_rules();
}

map<Handle, HandleSeq>& BackwardChainer::get_chaining_result()
{
	return _chaining_result;
}


/**
 * The main recursive backward chaining method.
 *
 * @param hgoal  the atom to do backward chaining on
 * @return       ???
 */
map<Handle, HandleSeq> BackwardChainer::do_bc(Handle& hgoal)
{
	// TODO filter grounded representations so the next condition would never be fooled
	// XXX what does the above meant?
	HandleSeq kb_match = filter_grounded_experssions(hgoal);

	if (kb_match.empty())
	{
		logger().debug("[BackwardChainer] Knowledge base empty");

		// find all rules whose implicand can be unified to hgoal
		std::vector<Rule> acceptable_rules = filter_rules(hgoal);

		// if no rules to backward chain on
		if (acceptable_rules.empty())
			return unify_to_empty_set(hgoal);

		// TODO use all rules for found here.
		Rule stadardized_rule = select_rule(rules).standardize_apart();

		//for later removal
//		_bc_generated_rules.push_back(stadardized_rule);

		Handle implicand = stadardized_rule.get_implicand();

		// XXX TODO check unify return value
		map<Handle, HandleSeq> out;
		unify(hgoal, implicand, out);
		_inference_list.push_back(out);

		map<Handle, HandleSeq> solution = apply_rule(implicand, stadardized_rule);
		_inference_list.push_back(solution);

		return ground_target_vars(hgoal, _inference_list);
	}

	vector<map<Handle, HandleSeq>> kb_results;

	map<Handle, HandleSeq> out;
	for (Handle soln : kb_match)
	{
		// XXX TODO check unify return value
		unify(hgoal, soln, out);
		kb_results.push_back(out);
	}

	return ground_target_vars(hgoal, kb_results);
}

/**
 * Apply a rule to an atom by first backward chaining the rule's implicant.
 *
 * @param htarget   the atom in which the rule will be applied
 * @param rule      the rule to apply
 * @return          ???
 */
map<Handle, HandleSeq> BackwardChainer::apply_rule(Handle& htarget, Rule& rule)
{
	vector<map<Handle, HandleSeq>> results;

	std::stack<Handle> visit_stack;
	visit_stack.push(rule.get_implicant());

	map<Handle, HandleSeq> logical_link_premise_map = get_logical_link_premises_map(himplicant);
	map<Handle, map<Handle, HandleSeq>> premise_var_ground_map;
	UnorderedHandleSet evaluated_premises;

	while (not visit_stack.empty())
	{
		Handle premise = visit_stack.top();
		visit_stack.pop();

		// check if premise was already visited
		if (evaluated_premises.count(premise) == 1)
			continue;

		// if premise has more sub-premises
		if (logical_link_premise_map.count(premise) == 1)
		{
			HandleSeq sub_premises = logical_link_premise_map[premise];

			// check if all its sub-premises are already evaluated
			if (std::all_of(sub_premises.begin(), sub_premises.end(), [](const Handle& h) { evaluated_premises.count(h) == 1; }))
			{
				auto v = join_premise_vgrounding_maps(premise, premise_var_ground_map);

				results.push_back(v);
				evaluated_premises.emplace(premise);

				continue;
			}

			// if not all evaluated, add this premise back into the stack, but
			// put all its sub-premises on top
			visit_stack.push(premise);

			for (auto p : sub_premises)
				visit_stack.push(p);

			continue;
		}

		// if premise has no sub-premises (ie. not a logical condition), just
		// backward chain on it
		auto var_grounding = do_bc(premise);
		premise_var_ground_map[premise] = var_grounding;
		evaluated_premises.emplace(premise);
	}

	return ground_target_vars(htarget, results);
}

/**
 * Find all rules in which the input could be an output.
 *
 * @param htarget   an input atom to match
{'fraction_non_alphanumeric': 0.09935957807496704, 'fraction_numerical': 0.004143906573742701, 'mean_word_length': 4.420622766717713, 'pattern_counts': {'":': 0, '<': 47, '<?xml version=': 0, '>': 48, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2653692', 'n_tokens_mistral': 3734, 'n_tokens_neox': 3394, 'n_words': 1023}