#include <PatternMatchEngine.h>

Collaboration diagram for opencog::PatternMatchEngine:

Public Member Functions
	PatternMatchEngine (PatternMatchCallback &, const Variables &, const Pattern &)

bool	explore_neighborhood (const Handle &, const Handle &, const Handle &)

Static Public Member Functions
static void	print_solution (const std::map< Handle, Handle > &vars, const std::map< Handle, Handle > &clauses)

static void	print_term (const std::set< Handle > &vars, const std::vector< Handle > &clauses)

Private Types
enum	Caller { CALL_QUOTE, CALL_ORDER, CALL_UNORDER, CALL_CHOICE, CALL_COMP, CALL_SOLN }

typedef std::pair < PatternTermPtr, Handle >	Choice

typedef std::map< Choice, size_t >	ChoiceState

typedef std::pair < PatternTermPtr, Handle >	Unorder

typedef PatternTermSeq	Permutation

typedef std::map< Unorder, Permutation >	PermState

typedef std::set< Handle >	IssuedSet

typedef std::map< Handle, Handle >	SolnMap

Private Member Functions
bool	explore_redex (const Handle &, const Handle &, const Handle &)

bool	is_optional (const Handle &h)

bool	is_evaluatable (const Handle &h)

bool	is_black (const Handle &h)

void	push_redex (void)

void	pop_redex (void)

void	clear_current_state (void)

size_t	curr_choice (const PatternTermPtr &, const Handle &, bool &)

bool	have_choice (const PatternTermPtr &, const Handle &)

Permutation	curr_perm (const PatternTermPtr &, const Handle &, bool &)

bool	have_perm (const PatternTermPtr &, const Handle &)

bool	do_next_clause (void)

void	get_next_untried_clause (void)

bool	get_next_thinnest_clause (bool, bool, bool)

unsigned int	thickness (const Handle &, const std::set< Handle > &)

void	solution_push (void)

void	solution_pop (void)

void	solution_drop (void)

void	perm_push (void)

void	perm_pop (void)

void	clause_stacks_push (void)

void	clause_stacks_pop (void)

void	clause_stacks_clear (void)

bool	tree_compare (const PatternTermPtr &, const Handle &, Caller)

bool	quote_compare (const PatternTermPtr &, const Handle &)

bool	variable_compare (const Handle &, const Handle &)

bool	self_compare (const Handle &)

bool	node_compare (const Handle &, const Handle &)
	Compare two nodes, one in the pattern, one proposed grounding. More...

bool	redex_compare (const LinkPtr &, const LinkPtr &)

bool	choice_compare (const PatternTermPtr &, const Handle &, const LinkPtr &, const LinkPtr &)

bool	ordered_compare (const PatternTermPtr &, const Handle &, const LinkPtr &, const LinkPtr &)

bool	unorder_compare (const PatternTermPtr &, const Handle &, const LinkPtr &, const LinkPtr &)

bool	explore_clause (const Handle &, const Handle &, const Handle &)

bool	explore_term_branches (const Handle &, const Handle &, const Handle &)

bool	explore_up_branches (const PatternTermPtr &, const Handle &, const Handle &)

bool	explore_link_branches (const PatternTermPtr &, const Handle &, const Handle &)

bool	explore_choice_branches (const PatternTermPtr &, const Handle &, const Handle &)

bool	explore_single_branch (const PatternTermPtr &, const Handle &, const Handle &)

bool	do_term_up (const PatternTermPtr &, const Handle &, const Handle &)

bool	clause_accept (const Handle &, const Handle &)

Private Attributes
PatternMatchCallback &	_pmc

ClassServer &	_classserver

const Variables *	_varlist

const Pattern *	_pat

std::stack< const Variables * >	_stack_variables

std::stack< const Pattern * >	_stack_pattern

std::map< Handle, Handle >	var_grounding

std::map< Handle, Handle >	clause_grounding

ChoiceState	_choice_state

bool	_need_choice_push

bool	choose_next

PermState	_perm_state

bool	take_step

bool	have_more

bool	clause_accepted

Handle	next_clause

Handle	next_joint

IssuedSet	issued

std::stack< SolnMap >	var_solutn_stack

std::stack< SolnMap >	term_solutn_stack

std::stack< IssuedSet >	issued_stack

std::stack< ChoiceState >	choice_stack

std::stack< PermState >	perm_stack

unsigned int	_clause_stack_depth

unsigned int	depth

bool	in_quote

Detailed Description

Definition at line 39 of file PatternMatchEngine.h.

Member Typedef Documentation

typedef std::pair<PatternTermPtr, Handle> opencog::PatternMatchEngine::Choice

private

Definition at line 97 of file PatternMatchEngine.h.

typedef std::map<Choice, size_t> opencog::PatternMatchEngine::ChoiceState

private

Definition at line 98 of file PatternMatchEngine.h.

typedef std::set<Handle> opencog::PatternMatchEngine::IssuedSet

private

Definition at line 140 of file PatternMatchEngine.h.

typedef std::map<Unorder, Permutation> opencog::PatternMatchEngine::PermState

private

Definition at line 114 of file PatternMatchEngine.h.

typedef PatternTermSeq opencog::PatternMatchEngine::Permutation

private

Definition at line 113 of file PatternMatchEngine.h.

typedef std::map<Handle, Handle> opencog::PatternMatchEngine::SolnMap

private

Definition at line 154 of file PatternMatchEngine.h.

typedef std::pair<PatternTermPtr, Handle> opencog::PatternMatchEngine::Unorder

private

Definition at line 112 of file PatternMatchEngine.h.

Member Enumeration Documentation

enum opencog::PatternMatchEngine::Caller

private

Enumerator
CALL_QUOTE
CALL_ORDER
CALL_UNORDER
CALL_CHOICE
CALL_COMP
CALL_SOLN

Definition at line 176 of file PatternMatchEngine.h.

Constructor & Destructor Documentation

PatternMatchEngine::PatternMatchEngine	(	PatternMatchCallback &	pmcb,
		const Variables &	v,
		const Pattern &	p
	)

Definition at line 1846 of file PatternMatchEngine.cc.

References _clause_stack_depth, _need_choice_push, choose_next, depth, have_more, in_quote, and take_step.

Member Function Documentation

bool PatternMatchEngine::choice_compare	(	const PatternTermPtr &	ptm,
		const Handle &	hg,
		const LinkPtr &	lp,
		const LinkPtr &	lg
	)

private

Compare a ChoiceLink in the pattern to the proposed grounding. hp points at the ChoiceLink.

CHOICE_LINK's are multiple-choice links. As long as we can can match one of the sub-expressions of the ChoiceLink, then the ChoiceLink as a whole can be considered to be grounded.

Definition at line 315 of file PatternMatchEngine.cc.

References _choice_state, _pmc, CALL_CHOICE, choose_next, curr_choice(), dbgprt, opencog::Atom::getHandle(), opencog::PatternMatchCallback::post_link_match(), solution_drop(), solution_pop(), solution_push(), tree_compare(), and var_grounding.

Here is the caller graph for this function:

bool PatternMatchEngine::clause_accept	(	const Handle &	clause_root,
		const Handle &	hg
	)

private

This is called when we've navigated to the top of a clause, and so it is fully grounded, and we're essentially done. However, let the callbacks have the final say on whether to proceed onwards, or to backtrack.

Definition at line 1291 of file PatternMatchEngine.cc.

References _pmc, clause_accepted, clause_grounding, opencog::PatternMatchCallback::clause_match(), dbgprt, do_next_clause(), is_optional(), opencog::PatternMatchCallback::optional_clause_match(), and prtmsg().

Here is the caller graph for this function:

void PatternMatchEngine::clause_stacks_clear ( void )

private

Unconditionally clear all graph traversal stacks XXX TODO – if the algo is working correctly, then all of these should already be empty, when this method is called. So really, we should check the stack size, and assert if it is not zero ...

Definition at line 1692 of file PatternMatchEngine.cc.

References _clause_stack_depth, choice_stack, issued_stack, perm_stack, term_solutn_stack, and var_solutn_stack.

Here is the caller graph for this function:

void PatternMatchEngine::clause_stacks_pop ( void )

private

Pop all clause-traversal-related stacks. This restores state so that the traversal of a single clause can resume where it left off. These do NOT affect any of the redex stacks (which are assumed to be empty at this point.)

Definition at line 1667 of file PatternMatchEngine.cc.

References _choice_state, _clause_stack_depth, _pmc, choice_stack, clause_grounding, dbgprt, issued, issued_stack, perm_pop(), opencog::PatternMatchCallback::pop(), POPSTK, term_solutn_stack, var_grounding, and var_solutn_stack.

Here is the caller graph for this function:

void PatternMatchEngine::clause_stacks_push ( void )

private

Push all stacks related to the grounding of a clause. This push is meant to be done only when a grounding for a clause has been found, and the next clause is about the be attempted. It saves all of the traversal data associated with the current clause, so that, later on, traversal can be resumed where it was left off.

This does NOT push and of the redex stacks because (with the current redex design), all redex substitutions should have terminatated by now, and returned to the main clause. i.e. the redex stack is assumed to be empty, at this point. (Its possible this design may change in in the future if multi-clause redexes are allowed, whatever the heck that may be!?)

Definition at line 1643 of file PatternMatchEngine.cc.

References _choice_state, _clause_stack_depth, _pmc, choice_stack, clause_grounding, dbgprt, in_quote, issued, issued_stack, perm_push(), opencog::PatternMatchCallback::push(), term_solutn_stack, var_grounding, and var_solutn_stack.

Here is the caller graph for this function:

void PatternMatchEngine::clear_current_state ( void )

private

Clear current traversal state. This gets us into a state where we can start traversing a set of clauses.

Definition at line 1824 of file PatternMatchEngine.cc.

References _choice_state, _need_choice_push, _perm_state, choose_next, clause_grounding, depth, have_more, in_quote, issued, take_step, and var_grounding.

Here is the caller graph for this function:

size_t PatternMatchEngine::curr_choice	(	const PatternTermPtr &	ptm,
		const Handle &	hg,
		bool &	fresh
	)

private

Return the current choice state for the given pattern & ground combination.

Definition at line 379 of file PatternMatchEngine.cc.

References _choice_state.

Here is the caller graph for this function:

PatternMatchEngine::Permutation PatternMatchEngine::curr_perm	(	const PatternTermPtr &	ptm,
		const Handle &	hg,
		bool &	fresh
	)

private

Return the saved unordered-link permutation for this particular point in the tree comparison (i.e. for the particular unordered link hp in the pattern.)

Definition at line 677 of file PatternMatchEngine.cc.

References _perm_state, and dbgprt.

Here is the caller graph for this function:

bool PatternMatchEngine::do_next_clause ( void )

private

Definition at line 1321 of file PatternMatchEngine.cc.

References _pmc, clause_accepted, clause_grounding, clause_stacks_pop(), clause_stacks_push(), dbgprt, explore_clause(), explore_term_branches(), get_next_untried_clause(), opencog::PatternMatchCallback::grounding(), is_evaluatable(), is_optional(), next_clause, next_joint, opencog::PatternMatchCallback::optional_clause_match(), print_solution(), prtmsg(), opencog::Handle::UNDEFINED, and var_grounding.

Here is the caller graph for this function:

bool PatternMatchEngine::do_term_up	(	const PatternTermPtr &	ptm,
		const Handle &	hg,
		const Handle &	clause_root
	)

private

do_term_up() – move upwards from the current term.

Given the current term, in hp, find its parent in the clause, and then call explore_up_branches() to see if the term's parent has corresponding match in the solution graph.

Note that, in the "normal" case, a given term has only one, unique parent in the given root_clause, and so its easy to find; one just looks at the path from the root clause down to the term, and the parent is the link immediately above it.

There are five exceptions to this "unique parent" case:

The term is already the root clause; it has no parent. In this case, we send it off to the machinery that explores the next clause.
Exactly the same term may appear twice, 3 times, etc. in the clause, all at different locations. This is very rare, but can happen. In essence, it has multiple parents; each needs to be checked. We loop over these.
The term is a part of a larger, evaluatable term. In this case, we don't want to go to the immediate parent, we want to go to the larger evaluatable term, and offer that up as the thing to match (i.e. to evaluate, to invoke callbacks, etc.)
The parent is an ChoiceLink. In this case, the ChoiceLink itself cannot be directly matched, as is; only its children can be. So in this case, we fetch the ChoiceLink's parent, instead.
Some crazy combination of the above.

If it weren't for these complications, this method would be small and simple: it would send the parent to explore_up_branches(), and then explore_up_branches() would respond as to whether it is satisfiable (solvable) or not.

Takes as an argument an atom hp in the pattern, and its matching grounding hg. Thus, hp's parent will need to be matched to hg's parent.

Returns true if a grounding for the term's parent was found.

Definition at line 1160 of file PatternMatchEngine.cc.

References _need_choice_push, _pat, _pmc, clause_accept(), dbgprt, depth, opencog::PatternMatchCallback::evaluate_sentence(), explore_up_branches(), opencog::Atom::getHandle(), opencog::Atom::getType(), have_choice(), opencog::Pattern::in_evaluatable, opencog::is_unquoted_in_tree(), prtmsg(), opencog::PatternTerm::UNDEFINED, opencog::Handle::value(), and var_grounding.

Here is the caller graph for this function:

bool PatternMatchEngine::explore_choice_branches	(	const PatternTermPtr &	ptm,
		const Handle &	hg,
		const Handle &	clause_root
	)

private

See explore_link_branches() for a general explanation. This method handles the ChoiceLink branch alternatives only. It assumes that the caller had handled the unordered-link alternative branches.

Definition at line 1038 of file PatternMatchEngine.cc.

References _choice_state, _need_choice_push, choice_stack, choose_next, dbgprt, explore_single_branch(), opencog::Atom::getHandle(), opencog::Atom::getType(), have_choice(), and POPSTK.

Here is the caller graph for this function:

bool PatternMatchEngine::explore_clause	(	const Handle &	term,
		const Handle &	grnd,
		const Handle &	clause
	)

private

Every clause in a pattern is one of two types: it either specifies a pattern to be matched, or it specifies an evaluatable atom that must be evaluated to determine if it is to be accepted. (In the default callback, evaluatable atoms are always crisp boolean-logic formulas, although the infrastructure is designed to handle other situations as well, e.g. Bayesian formulas, etc.)

This method simply dispatches a given clause to be eitther pattern matched, or to be evaluated.

Definition at line 1793 of file PatternMatchEngine.cc.

References _pmc, clause_accept(), dbgprt, opencog::PatternMatchCallback::evaluate_sentence(), explore_term_branches(), is_evaluatable(), and var_grounding.

Here is the caller graph for this function:

bool PatternMatchEngine::explore_link_branches	(	const PatternTermPtr &	ptm,
		const Handle &	hg,
		const Handle &	clause_root
	)

private

explore_link_branches – verify the suggested grounding.

There are two ways to understand this method. In the "simple" case, where there are no unordered links, and no ChoiceLinks, this becomes a simple wrapper around tree_compare(), and it just returns true or false to indicate if the suggested grounding hg actually is a match for the current term being grounded. Before calling tree_compare(), it pushes all current state, and then pops it upon return. In other words, this encapsulates a single up-branch (incoming-set branch): grounding of that single branch succeeds or fails. Failure backtracks to the caller of this method; upon return, the current state has been restored; this routine leaves the current state as it found it. For the simple case, this method is mis-named: it should be called "explore_one_branch".

The non-simple case is a pattern that includes ChoiceLinks or unordered links. These links represent branch-points themselves. A ChoiceLink of arity N wraps N different possible branches to be explored. An unordered link of arity N wraps N-factorial different possible permuations, each of which must be explored. This method controls the exploration of these different branches. For each possible branch, it saves state, explores the branch, and pops the state. If the exploration yielded nothing, then the next branch is explored, until exhaustion of the possibilities. Upon exhaustion, it returns to the caller.

This method is part of a recursive chain that only terminates when a grounding for the entire pattern was found (and the grounding was accepted) or if all possibilities were exhaustively explored. Thus, this returns true only if entire pattern was grounded.

Definition at line 1001 of file PatternMatchEngine.cc.

References _classserver, dbgprt, explore_choice_branches(), opencog::Atom::getHandle(), opencog::Atom::getType(), have_more, have_perm(), is_evaluatable(), opencog::ClassServer::isA(), and take_step.

Here is the caller graph for this function:

bool PatternMatchEngine::explore_neighborhood	(	const Handle &	do_clause,
		const Handle &	term,
		const Handle &	grnd
	)

explore_neighborhood - explore the local (connected) neighborhood of the starter clause, looking for a match. The idea here is that it is much easier to traverse a connected graph looking for the appropriate subgraph (pattern) than it is to try to explore the whole atomspace, at random. The user callback initiate_search() should call this method, suggesting a clause to start with, and where in the clause the search should begin.

Inputs: do_clause: must be one of the clauses previously specified in the clause list of the match() method. starter: must be a sub-clause of do_clause; that is, must be a link that appears in do_clause. ah: must be a (non-variable) node in the "starter" clause. That is, this must be one of the outgoing atoms of the "starter" link, it must be a node, and it must not be a variable node.

Returns true if one (or more) matches are found

This routine is meant to be invoked on every candidate atom taken from the atom space. That atom is assumed to anchor some part of a graph that hopefully will match the pattern.

Definition at line 1755 of file PatternMatchEngine.cc.

References clause_stacks_clear(), and explore_redex().

Here is the caller graph for this function:

bool PatternMatchEngine::explore_redex	(	const Handle &	term,
		const Handle &	grnd,
		const Handle &	first_clause
	)

private

Same as above, obviously; we just pick up the graph context where we last left it.

Definition at line 1767 of file PatternMatchEngine.cc.

References clear_current_state(), explore_clause(), issued, and opencog::Handle::UNDEFINED.

Here is the caller graph for this function:

bool PatternMatchEngine::explore_single_branch	(	const PatternTermPtr &	ptm,
		const Handle &	hg,
		const Handle &	clause_root
	)

private

Check the proposed grounding hg for pattern term hp.

As the name implies, this will explore only one single potential (proposed) grounding for the current pattern term. This is meant to be called after a viable branch has been identified for exploration.

This is wrapper around tree compare; if tree_compare returns false, then this returns immediately.

However, this method is part of the upwards-recursion chain, so if tree_compare approves the proposed grounding, this will recurse upwards, calling do_term_up to get the next pattern term. Thus, this method will return true ONLY if ALL OF the terms and clauses in the pattern are satisfiable (are accepted matches).

Definition at line 1089 of file PatternMatchEngine.cc.

References CALL_SOLN, dbgprt, do_term_up(), perm_pop(), perm_push(), solution_pop(), solution_push(), tree_compare(), and opencog::Handle::value().

Here is the caller graph for this function:

bool PatternMatchEngine::explore_term_branches	(	const Handle &	term,
		const Handle &	hg,
		const Handle &	clause_root
	)

private

Definition at line 902 of file PatternMatchEngine.cc.

References _pat, opencog::Pattern::connected_terms_map, and explore_link_branches().

Here is the caller graph for this function:

bool PatternMatchEngine::explore_up_branches	(	const PatternTermPtr &	ptm,
		const Handle &	hg,
		const Handle &	clause_root
	)

private

explore_up_branches – look for groundings for the given term.

The argument passed to this function is a term that needs to be grounded. One of this term's children has already been grounded: the term's child is in hp, and the corresponding grounding is in hg. Thus, if the argument is going to be grounded, it will be grounded by some atom in the incoming set of hg. Viz, we are walking upwards in these trees, in lockstep.

This method wraps the major branch-point of the entire pattern matching process. Each element of the incoming set is the start of a different possible branch to be explored; each one might yeild a grounding. Thus, when backtracking, after a failed grounding in one branch, we backtrack to here, and try another branch. When backtracking, all state must be popped and pushed again, to enter the new branch. We don't pushd & pop here, we push-n-pop in the explore_link_branches() method.

This method is part of a recursive chain that only terminates when a grounding for the entire pattern was found (and the grounding was accepted) or if all possibilities were exhaustively explored. Thus, this returns true only if entire pattern was grounded.

Definition at line 948 of file PatternMatchEngine.cc.

References _pmc, dbgprt, explore_link_branches(), opencog::PatternMatchCallback::get_incoming_set(), and opencog::Handle::value().

Here is the caller graph for this function:

bool PatternMatchEngine::get_next_thinnest_clause	(	bool	search_virtual,
		bool	search_black,
		bool	search_optionals
	)

private

Same as above, but with three boolean flags: if not set, then only those clauses satsifying the criterion are considered, else all clauses are considered.

Return true if we found the next ungrounded clause.

Definition at line 1536 of file PatternMatchEngine.cc.

References _pat, _varlist, opencog::Pattern::connectivity_map, opencog::Atom::getIncomingSetSize(), is_black(), is_evaluatable(), is_optional(), issued, next_clause, next_joint, thickness(), opencog::Handle::UNDEFINED, var_grounding, and opencog::Variables::varset.

Here is the caller graph for this function:

void PatternMatchEngine::get_next_untried_clause ( void )

private

Search for the next untried, (thus ungrounded, unsolved) clause.

The "issued" set contains those clauses which are currently in play, i.e. those for which a grounding is currently being explored. Both grounded, and as-yet-ungrounded clauses may be in this set. The sole reason of this set is to avoid infinite resursion, i.e. of re-identifying the same clause over and over as unsolved.

The words "solved" and "grounded" are used as synonyms throught the code.

Additional complications are introduced by the presence of evaluatable terms, black-box terms, and optional clauses. An evaluatable term is any term that needs to be evaluated to determine if it matches: such terms typically do not exist in the atomspace; they are "virtual", and "exist" only when the evaluation returns "true". Thus, these can only be grounded after all other possible clauses are grounded; thus these are saved for last. It is always possible to save these for last, because earlier stages have guaranteed that all of he non-virtual clauses are connected. Anyway, evaluatables come in two forms: those that can be evaluated quickly, and those that require a "black-box" evaluation of some scheme or python code. Of the two, we save "black-box" for last.

Then, after grounding all of the mandatory clauses (virtual or not), we look for optional clauses, if any. Again, these might be virtual, and they might be black...

Thus, we use a helper function to broaden the search in each case.

Definition at line 1454 of file PatternMatchEngine.cc.

References _pat, opencog::Pattern::black, opencog::Pattern::evaluatable_holders, get_next_thinnest_clause(), next_clause, next_joint, opencog::Pattern::optionals, and opencog::Handle::UNDEFINED.

Here is the caller graph for this function:

bool PatternMatchEngine::have_choice	(	const PatternTermPtr &	ptm,
		const Handle &	hg
	)

private

Definition at line 389 of file PatternMatchEngine.cc.

References _choice_state.

Here is the caller graph for this function:

bool PatternMatchEngine::have_perm	(	const PatternTermPtr &	ptm,
		const Handle &	hg
	)

private

Return true if there are more permutations to explore. Else return false.

Definition at line 699 of file PatternMatchEngine.cc.

References _perm_state.

Here is the caller graph for this function:

bool opencog::PatternMatchEngine::is_black ( const Handle & h )

inlineprivate

Definition at line 67 of file PatternMatchEngine.h.

References _pat, and opencog::Pattern::black.

Here is the caller graph for this function:

bool opencog::PatternMatchEngine::is_evaluatable ( const Handle & h )

inlineprivate

Definition at line 64 of file PatternMatchEngine.h.

References _pat, and opencog::Pattern::evaluatable_holders.

Here is the caller graph for this function:

bool opencog::PatternMatchEngine::is_optional ( const Handle & h )

inlineprivate

Definition at line 61 of file PatternMatchEngine.h.

References _pat, and opencog::Pattern::optionals.

Here is the caller graph for this function:

bool PatternMatchEngine::node_compare	(	const Handle &	hp,
		const Handle &	hg
	)

private

Compare two nodes, one in the pattern, one proposed grounding.

Definition at line 222 of file PatternMatchEngine.cc.

References _pmc, dbgprt, opencog::PatternMatchCallback::node_match(), prtmsg(), and var_grounding.

Here is the caller graph for this function:

bool PatternMatchEngine::ordered_compare	(	const PatternTermPtr &	ptm,
		const Handle &	hg,
		const LinkPtr &	lp,
		const LinkPtr &	lg
	)

private

If the two links are both ordered, its enough to compare them "side-by-side".

Definition at line 241 of file PatternMatchEngine.cc.

References _pmc, CALL_UNORDER, dbgprt, depth, opencog::Atom::getHandle(), opencog::PatternMatchCallback::post_link_match(), tree_compare(), opencog::PatternTerm::UNDEFINED, opencog::Handle::UNDEFINED, and var_grounding.

Here is the caller graph for this function:

void PatternMatchEngine::perm_pop ( void )

private

Definition at line 715 of file PatternMatchEngine.cc.

References _perm_state, perm_stack, and POPSTK.

Here is the caller graph for this function:

void PatternMatchEngine::perm_push ( void )

private

Definition at line 707 of file PatternMatchEngine.cc.

References _perm_state, and perm_stack.

Here is the caller graph for this function:

void PatternMatchEngine::pop_redex ( void )

private

Definition at line 81 of file Composition.cc.

References _pat, _stack_pattern, _stack_variables, and _varlist.

Here is the caller graph for this function:

void PatternMatchEngine::print_solution	(	const std::map< Handle, Handle > &	vars,
		const std::map< Handle, Handle > &	clauses
	)

static

Definition at line 1872 of file PatternMatchEngine.cc.

References opencog::Atom::getType(), reorder_log::m, prtmsg(), opencog::Atom::toShortString(), and opencog::Handle::UNDEFINED.

Here is the caller graph for this function:

void PatternMatchEngine::print_term	(	const std::set< Handle > &	vars,
		const std::vector< Handle > &	clauses
	)

static

For debug printing only

Definition at line 1922 of file PatternMatchEngine.cc.

References prt().

void PatternMatchEngine::push_redex ( void )

private

Definition at line 75 of file Composition.cc.

References _pat, _stack_pattern, _stack_variables, and _varlist.

Here is the caller graph for this function:

bool PatternMatchEngine::quote_compare	(	const PatternTermPtr &	ptm,
		const Handle &	hg
	)

private

If the pattern link is a quote, then we compare the quoted contents. This is done recursively, of course. The QuoteLink must have only one child; anything else beyond that is ignored (as its not clear what else could possibly be done).

Definition at line 117 of file PatternMatchEngine.cc.

References CALL_QUOTE, in_quote, opencog::LinkCast(), and tree_compare().

Here is the caller graph for this function:

bool PatternMatchEngine::redex_compare	(	const LinkPtr &	lp,
		const LinkPtr &	lg
	)

private

Definition at line 90 of file Composition.cc.

References _pat, _varlist, clause_accepted, clause_stacks_pop(), clause_stacks_push(), clear_current_state(), opencog::Pattern::cnf_clauses, dbgprt, opencog::PatternLinkCast(), pop_redex(), prtmsg(), push_redex(), opencog::Handle::UNDEFINED, and var_grounding.

bool PatternMatchEngine::self_compare ( const Handle & hp )

private

Compare an atom to itself. Amazingly, this is more complicated that what it might seem to be ...

If they're the same atom, then clearly they match. ... but only if hp is a constant (i.e. contains no bound variables)

This is screwed up. Right now, quoted variables are dealt with using a different mechanism, and bound beta redex varaiables are ... just broken, at the moment.

Definition at line 199 of file PatternMatchEngine.cc.

References _varlist, in_quote, var_grounding, and opencog::Variables::varset.

Here is the caller graph for this function:

void PatternMatchEngine::solution_drop ( void )

private

Definition at line 1722 of file PatternMatchEngine.cc.

References term_solutn_stack, and var_solutn_stack.

Here is the caller graph for this function:

void PatternMatchEngine::solution_pop ( void )

private

Definition at line 1716 of file PatternMatchEngine.cc.

References clause_grounding, POPSTK, term_solutn_stack, var_grounding, and var_solutn_stack.

Here is the caller graph for this function:

void PatternMatchEngine::solution_push ( void )

private

Definition at line 1710 of file PatternMatchEngine.cc.

References clause_grounding, term_solutn_stack, var_grounding, and var_solutn_stack.

Here is the caller graph for this function:

unsigned int PatternMatchEngine::thickness	(	const Handle &	clause,
		const std::set< Handle > &	live
	)

private

Definition at line 1516 of file PatternMatchEngine.cc.

References opencog::is_unquoted_in_tree().

Here is the caller graph for this function:

bool PatternMatchEngine::tree_compare	(	const PatternTermPtr &	ptm,
		const Handle &	hg,
		Caller	caller
	)

private

tree_compare compares two trees, side-by-side.

Compare two incidence trees, side-by-side. The incidence tree is given by following the "outgoing set" of the links appearing in the tree. The incidence tree is the so-called "Levi graph" of the hypergraph. The first arg should be a handle to a clause in the pattern, while the second arg is a handle to a candidate grounding. The pattern (template) clause is compared to the candidate grounding, returning true if there is a mis-match.

The comparison is recursive, so this method calls itself on each subtree (term) of the template clause, performing comparisons until a match is found (or not found).

Return false if there's a mis-match. The goal here is to walk over the entire tree, without mismatches. Since a return value of false stops the iteration, false is used to signal a mismatch.

The pattern clause may contain quotes (QuoteLinks), which signify that what follows must be treated as a literal (constant), rather than being interpreted. Thus, quotes can be used to search for expressions containing variables (since a quoted variable is no longer a variable, but a constant). Quotes can also be used to search for GroundedPredicateNodes (since a quoted GPN will be treated as a constant, and not as a function). Quotes can be nested, only the first quote is used to escape into the literal context, and so quotes can be used to search for expressions containing quotes. It is assumed that the QuoteLink has an arity of one, as its quite unclear what an arity of more than one could ever mean.

That method have side effects. The main one is to insert variable groundings (and in fact sub-clauses grounding as well) in var_grounding when encountering variables (and sub-clauses) in the pattern.

Definition at line 760 of file PatternMatchEngine.cc.

References _classserver, _pmc, _varlist, opencog::any_unquoted_in_tree(), choice_compare(), dbgprt, depth, opencog::PatternMatchCallback::fuzzy_match(), opencog::Atom::getHandle(), opencog::Atom::getType(), in_quote, is_evaluatable(), opencog::is_quoted_in_tree(), opencog::is_unquoted_in_tree(), opencog::ClassServer::isA(), opencog::PatternMatchCallback::link_match(), opencog::LinkCast(), node_compare(), opencog::NodeCast(), ordered_compare(), prtmsg(), quote_compare(), self_compare(), opencog::Handle::UNDEFINED, unorder_compare(), variable_compare(), and opencog::Variables::varset.

Here is the caller graph for this function:

bool PatternMatchEngine::unorder_compare	(	const PatternTermPtr &	ptm,
		const Handle &	hg,
		const LinkPtr &	lp,
		const LinkPtr &	lg
	)

private

Unordered link comparison

Compare two unordered links, side by side. In some ways, this is similar to the ordered link compare: for a given, fixed permuation of the unordered link, the compare is side by side. However, if that compare fails, the next permuation must then be tried, until a match is found or all permuations are exhausted. But there's a problem: if there are multiple, nested unordered links, or if they are peers (siblings) in the tree, then if one takes a step, the other must not. Coordinating this is difficult, and requires a long explanation. So here goes:

Definition at line 549 of file PatternMatchEngine.cc.

References _pat, _perm_state, _pmc, CALL_UNORDER, curr_perm(), dbgprt, opencog::Pattern::evaluatable_holders, opencog::Atom::getHandle(), have_more, opencog::PatternMatchCallback::post_link_match(), solution_drop(), solution_pop(), solution_push(), take_step, tree_compare(), opencog::PatternTerm::UNDEFINED, opencog::Handle::UNDEFINED, and var_grounding.

Here is the caller graph for this function:

bool PatternMatchEngine::variable_compare	(	const Handle &	hp,
		const Handle &	hg
	)

private

Compare a VariableNode in the pattern to the proposed grounding.

Handle hp is from the pattern clause.

Definition at line 135 of file PatternMatchEngine.cc.

References _pmc, _varlist, dbgprt, opencog::Atom::getType(), opencog::NodeCast(), prtmsg(), opencog::Atom::toShortString(), opencog::Handle::UNDEFINED, var_grounding, opencog::PatternMatchCallback::variable_match(), and opencog::Variables::varset.

Here is the caller graph for this function:

Member Data Documentation

ChoiceState opencog::PatternMatchEngine::_choice_state

private

Definition at line 100 of file PatternMatchEngine.h.

ClassServer& opencog::PatternMatchEngine::_classserver

private

Definition at line 44 of file PatternMatchEngine.h.

unsigned int opencog::PatternMatchEngine::_clause_stack_depth

private

Definition at line 169 of file PatternMatchEngine.h.

bool opencog::PatternMatchEngine::_need_choice_push

private

Definition at line 101 of file PatternMatchEngine.h.

const Pattern* opencog::PatternMatchEngine::_pat

private

Definition at line 59 of file PatternMatchEngine.h.

PermState opencog::PatternMatchEngine::_perm_state

private

Definition at line 116 of file PatternMatchEngine.h.

PatternMatchCallback& opencog::PatternMatchEngine::_pmc

private

Definition at line 43 of file PatternMatchEngine.h.

std::stack<const Pattern*> opencog::PatternMatchEngine::_stack_pattern

private

Definition at line 74 of file PatternMatchEngine.h.

std::stack<const Variables*> opencog::PatternMatchEngine::_stack_variables

private

Definition at line 73 of file PatternMatchEngine.h.

const Variables* opencog::PatternMatchEngine::_varlist

private

Definition at line 58 of file PatternMatchEngine.h.

std::stack<ChoiceState> opencog::PatternMatchEngine::choice_stack

private

Definition at line 159 of file PatternMatchEngine.h.

bool opencog::PatternMatchEngine::choose_next

private

Definition at line 108 of file PatternMatchEngine.h.

bool opencog::PatternMatchEngine::clause_accepted

private

Definition at line 133 of file PatternMatchEngine.h.

std::map<Handle, Handle> opencog::PatternMatchEngine::clause_grounding

private

Definition at line 91 of file PatternMatchEngine.h.

unsigned int opencog::PatternMatchEngine::depth

private

Definition at line 173 of file PatternMatchEngine.h.

bool opencog::PatternMatchEngine::have_more

private

Definition at line 123 of file PatternMatchEngine.h.

bool opencog::PatternMatchEngine::in_quote

private

Definition at line 174 of file PatternMatchEngine.h.

IssuedSet opencog::PatternMatchEngine::issued

private

Definition at line 141 of file PatternMatchEngine.h.

std::stack<IssuedSet> opencog::PatternMatchEngine::issued_stack

private

Definition at line 158 of file PatternMatchEngine.h.

Handle opencog::PatternMatchEngine::next_clause

private

Definition at line 137 of file PatternMatchEngine.h.

Handle opencog::PatternMatchEngine::next_joint

private

Definition at line 138 of file PatternMatchEngine.h.

std::stack<PermState> opencog::PatternMatchEngine::perm_stack

private

Definition at line 161 of file PatternMatchEngine.h.

bool opencog::PatternMatchEngine::take_step

private

Definition at line 122 of file PatternMatchEngine.h.

std::stack<SolnMap> opencog::PatternMatchEngine::term_solutn_stack

private

Definition at line 156 of file PatternMatchEngine.h.

std::map<Handle, Handle> opencog::PatternMatchEngine::var_grounding

private

Definition at line 89 of file PatternMatchEngine.h.

std::stack<SolnMap> opencog::PatternMatchEngine::var_solutn_stack

private

Definition at line 155 of file PatternMatchEngine.h.

The documentation for this class was generated from the following files:

opencog/query/PatternMatchEngine.h
opencog/query/Composition.cc
opencog/query/PatternMatchEngine.cc

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation