tree-match.h

/* Tree pattern matching and checking using concrete syntax.
  Copyright (C) 2006, 2007 Free Software Foundation, Inc.
  Contributed by Nic Volanschi <nic.volanschi@free.fr>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GCC 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 General Public License
along with GCC; see the file COPYING.  If not, write to the Free
Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.  */

#include <stdarg.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#include <sparse/parse.h>

#include "coretypes.h"
#include "statistics.h"
#include "vec.h"

/* At the statement level, a node in the CFG has the following type.  */
//typedef struct tree_statement_list_node *cfg_node;
typedef struct statement *cfg_node;

DEF_VEC_P(cfg_node);
DEF_VEC_ALLOC_P(cfg_node, heap);

/* Accessor for a CFG node.  */
static inline struct statement *cfg_node_stmt(cfg_node node)
{
	return node;
}

/* XXX: Hopefuly, we won't be needing these.. */
#if 0
/* Map a statement iterator to a CFG node.  */
static inline cfg_node bsi_cfg_node(block_stmt_iterator bsi)
{
	return bsi.tsi.ptr;
}

/* Get 1st CFG node in a basic block.  */
static inline cfg_node bb_1st_cfg_node(basic_block bb)
{
	return STATEMENT_LIST_HEAD(bb->stmt_list);
}
#endif

/* XXX: Do we really need a tree_chunk structure? */
struct tree_chunk {
  /* Reference to a subtree.  */
  struct statement *t;
  /* A token.  */
  char *s;
  /* A token of only one char is not stored in a malloc-ed string.  */
  char c;
};

DECLARE_ALLOCATOR(tree_chunk);
DECLARE_PTR_LIST(tree_chunk_list, tree_chunk);

/* XXX */

static inline void *xmalloc(size_t size)
{
	void *ret = malloc(size);
	if (!ret)
		exit(1);
	return ret;
}

static inline char *xstrdup(const char *s)
{
	char *ret = strdup(s);
	if (!ret)
		exit(1);
	return ret;
}

/* Patterns are of 2 kinds:
   1. with named holes, as in: "lock(%X, %Y)"
   2. with anonymous holes, as in: tree_scanf(t, "lock(%t, %t)", &t1, &t2)
 */
typedef struct patt_info_s {
	const char *format_spec;
	int sign;
	va_list *args_ptr;	/* only used for anomymous holes */
	struct patt_info_s *next;	/* next disjunct in the pattern */
} patt_info;

typedef patt_info *pattern;

/* Atomic pattern constructor.  */
static inline pattern mkpat(const char *str)
{
	pattern res = xmalloc(sizeof(patt_info));
	res->format_spec = xstrdup(str);
	res->next = NULL;
	res->args_ptr = NULL;
	return res;
}

/* Disjunctive pattern constructor.  */
static inline pattern pat_or(pattern p1, pattern p2)
{
	p1->next = p2;
	return p1;
}

/* Pattern destructor.  */
static inline void rmpat(pattern p)
{
	if (p->next)
		rmpat(p->next);
	free((char *)p->format_spec);
	free(p);
}

/* Display a pattern to stderr.  */
static inline void pat_print(pattern p)
{
	const char *sign;
	if (!p)
		return;

	sign = (p->sign > 0) ? "+" : (p->sign < 0) ? "-" : "";
	if (!p->next)
		fprintf(stderr, "%s\"%s\"", sign, p->format_spec);
	else {
		fprintf(stderr, "%s\"%s\" or ", sign, p->format_spec);
		pat_print(p->next);
	}
}

/* A "hole" is a pattern variable (aka meta-variable).  It contains a
   tree (which is NULL when the var is unistantiated), and a CFG
   "context" node which points to the stmt containing the tree.  The
   context is useful to interpret temporary variables, or other
   dataflow data.  */
typedef struct hole_s {
	struct statement *tree;
	cfg_node ctx;
} hole;

typedef hole *hole_p;

DEF_VEC_P(hole_p);
DEF_VEC_ALLOC_P(hole_p, heap);

/* Named local holes are noted by a single lowercase letter.  */
#define LOCAL_MAX 26
/* Named global holes are noted by a single capital letter.  */
#define GLOBAL_MAX 26

/* Named local holes are used locally within each pattern.  Thus, a
   variable %x may have different values in different patterns.  */
extern hole local_holes[LOCAL_MAX];
/* Named global holes are shared between all the patterns in a same
   property.  Thus, a variable %X has the same value in different
   patterns.  */
extern hole global_holes[GLOBAL_MAX];

extern bool is_global_hole(char c);
extern hole *get_hole_named(char c);
extern void reset_local_holes(void);
extern void reset_global_holes(void);
extern hole *save_global_holes(void);
extern void restore_global_holes(hole * saved);
extern bool eq_global_holes(hole * holes1, hole * holes2);
extern void print_local_holes(void);
extern void print_global_holes(void);

/* User interface to AST pattern matching.  */
extern bool tree_scanf(struct statement *t, const char *fmt, cfg_node ctx_node, ...);
extern bool tree_match(struct statement *t, const char *fmt, cfg_node ctx_node);
extern bool tree_match_disj(struct statement *t, pattern fmt, cfg_node ctx_node);

/* A "condate" is a program property involving CONtrol, DATa, and
   other aspects such as syntactic and semantic information.  For
   example, '[there is a path] from "lock(%X)" to "unlock(%X)"
   avoiding "return" or "return %_"' is a condate specifying
   lock-unlock bugs.  Thus, condates are built upon patterns, CFG and
   dataflow information.  */
typedef struct condate_s {
	char *name;		/* Used to identify the condate in warning messages.  */
	pattern from;		/* Paths start at nodes matching this pattern.  */
	pattern to;		/* Paths end at nodes matching this pattern.  */
	pattern avoid;		/* Paths must avoid nodes matching this pattern. */
	pattern avoid_then;	/* ... successful conditions matching this pattern. */
	pattern avoid_else;	/* ... and unsuccessful conditions mathing this one.  */
	const char *msg;	/* Message to print if the condate is matched. */
} *condate;

/* Condate constructor.  */
static inline condate
mkcond(const char *name, pattern from, pattern to, pattern avoid,
       pattern avoid_then, pattern avoid_else)
{
	condate cond = xmalloc(sizeof(struct condate_s));
	if (name)
		cond->name = xstrdup(name);
	else
		cond->name = NULL;
	cond->from = from;
	cond->to = to;
	cond->avoid = avoid;
	cond->avoid_then = avoid_then;
	cond->avoid_else = avoid_else;
	cond->msg = NULL;
	return cond;
}

/* Condate destructor.  */
static inline void rmcond(condate cond)
{
	if (cond->name)
		free(cond->name);
	rmpat(cond->from);
	rmpat(cond->to);
	rmpat(cond->avoid);
	rmpat(cond->avoid_then);
	rmpat(cond->avoid_else);
	free(cond);
}

extern void print_cond(condate cond);

#define CONDMAX 100
extern condate conds[CONDMAX];	/* List of condated to check.  */
extern int n_conds;		/* Number of condates to check.  */

extern void normalize_condate(condate cond);
extern void name_condate(condate cond);
extern void add_condate(condate cond);

extern FILE *checkfile;
extern int condate_parse(void);