semtrex implementation More...

#include "semtrex.h"
#include "def.h"
#include "debug.h"
#include "ansicolor.h"

Include dependency graph for semtrex.c:

Data Structures
union	Ptrlist

struct	BranchPoint

#define	MAX_BRANCH_DEPTH 5000

#define	CURSOR_MAX_DEPTH 100

#define	_PUSH_BRANCH(state, t, crs, c, w)

#define	PUSH_BRANCH(state, t, crs, c) _PUSH_BRANCH(state,t,crs,c,0)

#define	PUSH_WALK_POINT(state, t, crs, c) _PUSH_BRANCH(state,t,crs,c,c)

#define	FAIL {s=0;break;}

#define	TRANSITION(x) if (!t) {FAIL;}; if (!x) {FAIL;}; t=__transition(s->transition,source_t,cursor); s = s->out;

#define	dump_tokens(str)

#define	pbuf(...) sprintf(buf+strlen(buf),__VA_ARGS__)

typedef union Ptrlist	Ptrlist

typedef struct BranchPoint	BranchPoint

SState	matchstate = {NULL,0,StateMatch}
	the final matching state in the FSA can be declared statically and globally

char *	G_s_str [] ={"StateSymbol","StateAny","StateValue","StateSplit","StateMatch","StateGroupOpen","StateGroupClose","StateDescend","StateWalk","StateNot"}

int	G_group_id

char	G_stx_debug_buf [1000]

char	trbuf [255]

SState *	G_cur_stx_state = NULL

char	G_stx_dump_buf [100000]

Ptrlist *	list1 (SState **outp)

void	patch (Ptrlist l, SState s, int level)

Ptrlist *	append (Ptrlist l1, Ptrlist l2)

SState *	state (StateType type, int *statesP, int level)

char *	__stx_makeFA (T t, SState in, Ptrlist out, int level, int statesP)

SState *	_stx_makeFA (T t, int statesP)

int	__stx_freeFA (SState *s, int id)

void	__stx_freeFA2 (SState *s)

void	_stx_freeFA (SState *s)

int	__symbol_set_contains (T s, T t)

int	__symbol_set_does_not_contain (T s, T t)

T *	__transition (TransitionType transition, T source_t, int cursor)

int	_val_match (T t, T t1)

void	__fix (T source_t, T r)

char *	__stx_dump_state (SState s, char buf)

int	__t_match (T semtrex, T source_t, T **rP)

int	_t_matchr (T semtrex, T t, T **rP)

int	_t_match (T semtrex, T t)

T *	_stx_get_matched_node (Symbol s, T match_results, T match_tree, int *sibs)

void	_stx_replace (T semtrex, T t, T *replace)

T *	_t_get_match (T *match, Symbol group)

T *	_t_embody_from_match (SemTable sem, T match, Symbol group, T *t)

T *	__t_embody_from_match (SemTable sem, T match, T *t)

char *	__dump_semtrex (SemTable sem, T s, char *buf)

void	__stxd_multi (SemTable sem, char x, T s, char buf)

void	__stxd_descend (SemTable sem, T s, char v, char buf, int skip)

char *	_dump_semtrex (SemTable sem, T s, char *buf)

T *	__stxcv (T *p, char c)

T *	__stxcvm (T *p, int not, int count,...)

void	_stxcs (T stxx, char an)

void	_stxl (T *stxx)

Symbol	get_symbol (char symbol_name, SemTable sem)

T *	wrap (T tokens, T results, Symbol contents_s, Symbol open_s)

T *	makeASCIITree (char *c)

char *	_asciiT2str (T asciiT, T match, T t, char buf)

T *	asciiT_toi (T asciiT, T match, T *t, Symbol s)

T *	asciiT_tol (T asciiT, T match, T *t, Symbol s)

T *	asciiT_tof (T asciiT, T match, T *t, Symbol s)

T *	asciiT_tos (T asciiT, T match, T *t, Symbol s)

T *	asciiT_toc (T asciiT, T match, T *t, Symbol s)

T *	__sl (T *p, bool not, int count,...)

T *	parseSemtrex (SemTable sem, char stx)

void	__stx_r2fi (SemTable sem, T mr, T mt, T sem_map)

T *	_stx_results2sem_map (SemTable sem, T match_results, T *match_tree)

char *	transition2Str (TransitionType transition)

void	__stx_dump (SState s, char buf)

char *	_stx_dump (SState s, char buf)

void	stx_dump (T *s)

Detailed Description

semtrex implementation

This file implements a regular expression type language usefull for searching semantic trees.

The code to generate finite state automata to match the trees is based heavily on Russ Cox's great work see https://github.com/zippy/ceptr/blob/master/articles/cox2007.pdf

Copyright: Copyright (C) 2013-2016, The MetaCurrency Project (Eric Harris-Braun, Arthur Brock, et. al). This file is part of the Ceptr platform and is released under the terms of the license contained in the file LICENSE (GPLv3).

Definition in file semtrex.c.

Macro Definition Documentation

#define _PUSH_BRANCH	(	state,
		t,
		crs,
		c,
		w
	)

Value:

{                                  \
        G_stx_debug_buf[0]=0;debug(D_STX_MATCH,"pushing split branch for backtracking to state %s\n    with cursor:%s \n",__stx_dump_state(state,G_stx_debug_buf),c?t2s(c):"NULL"); \
    if((depth+1)>=MAX_BRANCH_DEPTH) {raise_error("MAX branch depth exceeded");} \
    stack[depth].s = state;                                             \
    stack[depth].transition = t;                                        \
    _t_pathcpy(stack[depth].cursor,crs);                                \
    stack[depth].walk_root = w;                                         \
    if (w) stack[depth].walk_cursor = NULL;                             \
    if (rP) {                                                           \
        if (*rP) {                                                      \
            stack[depth].match = _t_clone(*rP);                         \
            stack[depth].r_path = _t_get_path(r);                       \
        }                                                               \
        else stack[depth].match = 0;                                    \
    }                                                                   \
    depth++;                                                            \
}

Definition at line 535 of file semtrex.c.

Typedef Documentation

typedef union Ptrlist Ptrlist

Since the out pointers in the list are always uninitialized, we use the pointers themselves as storage for the Ptrlists.

Definition at line 31 of file semtrex.c.

Function Documentation

int __stx_freeFA	(	SState *	s,
		int	id
	)

walks through the FSA clearing pointers that create loops

Definition at line 339 of file semtrex.c.

void __stx_freeFA2 ( SState * s )

walk through FSA freeing the states, assumes __stx_freeFA has been called first so as not to go into loops!

Definition at line 352 of file semtrex.c.

char* __stx_makeFA	(	T *	t,
		SState **	in,
		Ptrlist **	out,
		int	level,
		int *	statesP
	)

Given a Semtrex tree, build a partial FSA (returned via in as a pointer to the starting state, a list of output states, and a count of the total number of states created).

Definition at line 119 of file semtrex.c.

int __symbol_set_contains	(	T *	s,
		T *	t
	)

check that a SEMTREX_SYMBOL_SET contains the given symbol

Parameters

[in]	s	symbol
[in]	t	SEMTREX_SYMBOL_SET tree

Returns: 1 or 0

Definition at line 378 of file semtrex.c.

int __symbol_set_does_not_contain	(	T *	s,
		T *	t
	)

check that a SEMTREX_SYMBOL_SET does not contain the given symbol

Parameters

[in]	s	symbol
[in]	t	SEMTREX_SYMBOL_SET tree

Returns: 1 or 0

Definition at line 394 of file semtrex.c.

int __t_match	(	T *	semtrex,
		T *	source_t,
		T **	rP
	)

build an FSA from semtrex tree and walk it using a recursive backtracing algorithm to match the tree in t.

Parameters

[in]	semtrex	tree to use for matching a tree
[in]	source_t	tree to match against
[in,out]	rP	match results tree being built. (nil if no results needed)

Returns: 1 or 0 if matched or not

Definition at line 567 of file semtrex.c.

int _val_match	(	T *	t,
		T *	t1
	)

Todo:: move this to tree.c

Definition at line 451 of file semtrex.c.

Ptrlist* append	(	Ptrlist *	l1,
		Ptrlist *	l2
	)

Join the two lists l1 and l2, returning the combination.

Definition at line 87 of file semtrex.c.

Ptrlist* list1 ( SState ** outp )

Create singleton list containing just outp.

Definition at line 42 of file semtrex.c.

void patch	(	Ptrlist *	l,
		SState *	s,
		int	level
	)

Patch the list of states at out to point to start.

Definition at line 55 of file semtrex.c.

SState* state	(	StateType	type,
		int *	statesP,
		int	level
	)

utility routine to initialize a state struct

Definition at line 103 of file semtrex.c.

Data Structures

Detailed Description

Macro Definition Documentation

Typedef Documentation

Function Documentation