<commit_before>#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stdarg.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

#include "util.h"
#include "parse.h"
#include "mi.h"

Dtree *gendtree(Node *m, Node *val, Node **lbl, size_t nlbl);
void dtreedump(FILE *fd, Dtree *dt);


static size_t ndtree;
static Dtree **dtree;

/* Path is a integer sequence that labels a subtree of a subject tree.
 * For example,
 * 0 is the root
 * 0,0 and 0,1 are two subtrees of the root.
 *
 * Note: the order of the sequence is reversed with regard to the reference paper
 * "When Do Match-Compilation Heuristics Matter" by <NAME> and <NAME>.
 *
 * Each pattern of a match clause conrresponds to a unique Path of the subject tree.
 * When we have m match clauses, for a given Path, there can be at most m patterns
 * associated with the Path.
 *
 * Given
 * match v
 * | (11, 12, 13)
 * | (21, 22, 23)
 * | (31, 32, 33)
 * | _
 *
 * the entries 11, 21, 31 and the wildcard pattern at the bottom have the same Path 0,1
 *             12, 22, 32 have the same Path 0,2
 *             13, 23, 33 have the same Path 0,3
 */
typedef struct Path {
	size_t len;
	int *p;
} Path;

/* Slot bundles a pattern with its corresponding Path and load value.
 * The compiler will generate a comparison instruction for each (pat, load) pair.
 * Each match clause corresponds to a list of slots which is populated by addrec.
 */
typedef struct Slot {
	Path *path;
	Node *pat;
	Node *load;
} Slot;

static Slot *
mkslot(Path *path, Node *pat, Node *val)
{
	Slot *s;
	s = zalloc(sizeof(Slot));
	s->path = path;
	s->pat = pat;
	s->load = val;
	assert(path != (void *)1);
	return s;
}

/* Frontier bundles a list of slots to be matched for a specific match clause.
 * The instances of Frontier should be immutable after creation.
 */
typedef struct Frontier {
	int i; 			/* index of the match clauses from top to bottom */
	Node *lbl; 		/* branch target when the rule is matched */
	Slot  **slot; 		/* unmatched slots (Paths) for this match clause */
	size_t nslot;
	Node **cap; 		/* the captured variables of the pattern of this match clause */
	size_t ncap;
	Dtree *final;		/* final state, shared by all Frontiers for a specific (indxed by i) match clause */
	int hasorpat;		/* the frontier comes from a match arm that contains or-pattern */

	struct Frontier *next;
} Frontier;

static Node *
utag(Node *n)
{
	Node *tag;

	tag = mkexpr(n->loc, Outag, n, NULL);
	tag->expr.type = mktype(n->loc, Tyint32);
	return tag;
}

static Node *
uvalue(Node *n, Type *ty)
{
	Node *elt;

	elt = mkexpr(n->loc, Oudata, n, NULL);
	elt->expr.type = ty;
	return elt;
}

static Node *
tupelt(Node *n, size_t i)
{
	Node *idx, *elt;

	idx = mkintlit(n->loc, i);
	idx->expr.type = mktype(n->loc, Tyuint64);
	elt = mkexpr(n->loc, Otupget, n, idx, NULL);
	elt->expr.type = tybase(exprtype(n))->sub[i];
	return elt;
}

static Node *
arrayelt(Node *n, size_t i)
{
	Node *idx, *elt;

	idx = mkintlit(n->loc, i);
	idx->expr.type = mktype(n->loc, Tyuint64);
	elt = mkexpr(n->loc, Oidx, n, idx, NULL);
	elt->expr.type = tybase(exprtype(n))->sub[0];
	return elt;
}

static Node *
findmemb(Node *pat, Node *name)
{
	Node *n;
	size_t i;

	for (i = 0; i < pat->expr.nargs; i++) {
		n = pat->expr.args[i];
		if (nameeq(n->expr.idx, name))
			return n;
	}
	return NULL;
}

static Node *
structmemb(Node *n, Node *name, Type *ty)
{
	Node *elt;

	elt = mkexpr(n->loc, Omemb, n, name, NULL);
	elt->expr.type = ty;
	return elt;
}

static Node *
addcapture(Node *n, Node **cap, size_t ncap)
{
	Node **blk;
	size_t nblk, i;

	nblk = 0;
	blk = NULL;

	for (i = 0; i < ncap; i++)
		lappend(&blk, &nblk, cap[i]);
	for (i = 0; i < n->block.nstmts; i++)
		lappend(&blk, &nblk, n->block.stmts[i]);
	lfree(&n->block.stmts, &n->block.nstmts);
	n->block.stmts = blk;
	n->block.nstmts = nblk;
	return n;
}

static Dtree *
mkdtree(Srcloc loc, Node *lbl)
{
	Dtree *t;

	t = zalloc(sizeof(Dtree));
	t->lbl = lbl;
	t->loc = loc;
	t->id = ndtree;
	lappend(&dtree, &ndtree, t);
	return t;
}

static int
loadeq(Node *a, Node *b)
{
	if (a == b)
		return 1;

	if (exprop(a) != exprop(b))
		return 0;

	switch (exprop(a)) {
	case Outag:
	case Oudata:<commit_msg>Fix construction of pattern variable bindings Previously, inserting the variable bindings would make the Oasn nodes appear before the decl nodes in a block.<commit_after>#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stdarg.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

#include "util.h"
#include "parse.h"
#include "mi.h"

Dtree *gendtree(Node *m, Node *val, Node **lbl, size_t nlbl);
void dtreedump(FILE *fd, Dtree *dt);


static size_t ndtree;
static Dtree **dtree;

/* Path is a integer sequence that labels a subtree of a subject tree.
 * For example,
 * 0 is the root
 * 0,0 and 0,1 are two subtrees of the root.
 *
 * Note: the order of the sequence is reversed with regard to the reference paper
 * "When Do Match-Compilation Heuristics Matter" by <NAME> and <NAME>.
 *
 * Each pattern of a match clause conrresponds to a unique Path of the subject tree.
 * When we have m match clauses, for a given Path, there can be at most m patterns
 * associated with the Path.
 *
 * Given
 * match v
 * | (11, 12, 13)
 * | (21, 22, 23)
 * | (31, 32, 33)
 * | _
 *
 * the entries 11, 21, 31 and the wildcard pattern at the bottom have the same Path 0,1
 *             12, 22, 32 have the same Path 0,2
 *             13, 23, 33 have the same Path 0,3
 */
typedef struct Path {
	size_t len;
	int *p;
} Path;

/* Slot bundles a pattern with its corresponding Path and load value.
 * The compiler will generate a comparison instruction for each (pat, load) pair.
 * Each match clause corresponds to a list of slots which is populated by addrec.
 */
typedef struct Slot {
	Path *path;
	Node *pat;
	Node *load;
} Slot;

static Slot *
mkslot(Path *path, Node *pat, Node *val)
{
	Slot *s;
	s = zalloc(sizeof(Slot));
	s->path = path;
	s->pat = pat;
	s->load = val;
	assert(path != (void *)1);
	return s;
}

/* Frontier bundles a list of slots to be matched for a specific match clause.
 * The instances of Frontier should be immutable after creation.
 */
typedef struct Frontier {
	int i; 			/* index of the match clauses from top to bottom */
	Node *lbl; 		/* branch target when the rule is matched */
	Slot  **slot; 		/* unmatched slots (Paths) for this match clause */
	size_t nslot;
	Node **cap; 		/* the captured variables of the pattern of this match clause */
	size_t ncap;
	Dtree *final;		/* final state, shared by all Frontiers for a specific (indxed by i) match clause */
	int hasorpat;		/* the frontier comes from a match arm that contains or-pattern */

	struct Frontier *next;
} Frontier;

static Node *
utag(Node *n)
{
	Node *tag;

	tag = mkexpr(n->loc, Outag, n, NULL);
	tag->expr.type = mktype(n->loc, Tyint32);
	return tag;
}

static Node *
uvalue(Node *n, Type *ty)
{
	Node *elt;

	elt = mkexpr(n->loc, Oudata, n, NULL);
	elt->expr.type = ty;
	return elt;
}

static Node *
tupelt(Node *n, size_t i)
{
	Node *idx, *elt;

	idx = mkintlit(n->loc, i);
	idx->expr.type = mktype(n->loc, Tyuint64);
	elt = mkexpr(n->loc, Otupget, n, idx, NULL);
	elt->expr.type = tybase(exprtype(n))->sub[i];
	return elt;
}

static Node *
arrayelt(Node *n, size_t i)
{
	Node *idx, *elt;

	idx = mkintlit(n->loc, i);
	idx->expr.type = mktype(n->loc, Tyuint64);
	elt = mkexpr(n->loc, Oidx, n, idx, NULL);
	elt->expr.type = tybase(exprtype(n))->sub[0];
	return elt;
}

static Node *
findmemb(Node *pat, Node *name)
{
	Node *n;
	size_t i;

	for (i = 0; i < pat->expr.nargs; i++) {
		n = pat->expr.args[i];
		if (nameeq(n->expr.idx, name))
			return n;
	}
	return NULL;
}

static Node *
structmemb(Node *n, Node *name, Type *ty)
{
	Node *elt;

	elt = mkexpr(n->loc, Omemb, n, name, NULL);
	elt->expr.type = ty;
	return elt;
}

static Node *
addcapture(Node *n, Node **cap, size_t ncap)
{
	size_t i, j;

	for (i = 0; i < n->block.nstmts; i++) {
		if (n->block.stmts[i]->type != Ndecl)
			continue;
		for (j = 0; j < ncap; j++) {
			assert(cap[j]->expr.op == Oasn);
			assert(cap[j]->expr.args[0]->expr.op == Ovar);
			assert(cap[j]->expr.args[0]->expr.isconst == 0);
			if (n->block.stmts[i]->decl.did !=  cap[j]->expr.args[0]->expr.did)
				continue;
			assert(n->block.stmts[i]->decl.init == NULL);
			assert(cap[j]->expr.args[0]->expr.op == Ovar);
			n->block.stmts[i]->decl.init = cap[j]->expr.args[1];
		}
	}
	return n;
}

static Dtree *
mkdtree(Srcloc loc, Node *lbl)
{
	Dtree *t;

	t = zalloc(sizeof(Dtree));
	t->lbl = lbl;
	t->loc = loc;
	t->id = ndtree;
	lappend(&dtree, &ndtree, t);
	return t;
}

static int
loadeq(Node *a, Node *b)
{
	if (a == b)
		return 1;

	if (exprop(a) != exprop(b))
		return 0;

	switch (exprop(a)) {
	case Outag:
	case Oudata:
{'fraction_non_alphanumeric': 0.15200625908125628, 'fraction_numerical': 0.014194702134793786, 'mean_word_length': 3.4253214638971317, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 110, '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': '555596', 'n_tokens_mistral': 3693, 'n_tokens_neox': 3497, 'n_words': 1174}