code.cc

a little DFA compiler.

/* $Id: code.cc 717 2007-04-29 22:29:59Z helly $ */
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <iomanip>
#include <iostream>
#include "substr.h"
#include "globals.h"
#include "dfa.h"
#include "parser.h"
#include "code.h"

namespace re2c
{

// there must be at least one span in list;  all spans must cover
// same range

std::string indent(uint ind)
{
	std::string str;

	while (ind-- > 0)
	{
		str += indString;
	}
	return str;
}

static std::string space(uint this_label)
{
	int nl = next_label > 999999 ? 6 : next_label > 99999 ? 5 : next_label > 9999 ? 4 : next_label > 999 ? 3 : next_label > 99 ? 2 : next_label > 9 ? 1 : 0;
	int tl = this_label > 999999 ? 6 : this_label > 99999 ? 5 : this_label > 9999 ? 4 : this_label > 999 ? 3 : this_label > 99 ? 2 : this_label > 9 ? 1 : 0;

	return std::string(std::max(1, nl - tl + 1), ' ');
}

void Go::compact()
{
	// arrange so that adjacent spans have different targets
	uint i = 0;

	for (uint j = 1; j < nSpans; ++j)
	{
		if (span[j].to != span[i].to)
		{
			++i;
			span[i].to = span[j].to;
		}

		span[i].ub = span[j].ub;
	}

	nSpans = i + 1;
}

void Go::unmap(Go *base, const State *x)
{
	Span *s = span, *b = base->span, *e = &b[base->nSpans];
	uint lb = 0;
	s->ub = 0;
	s->to = NULL;

	for (; b != e; ++b)
	{
		if (b->to == x)
		{
			if ((s->ub - lb) > 1)
			{
				s->ub = b->ub;
			}
		}
		else
		{
			if (b->to != s->to)
			{
				if (s->ub)
				{
					lb = s->ub;
					++s;
				}

				s->to = b->to;
			}

			s->ub = b->ub;
		}
	}

	s->ub = e[ -1].ub;
	++s;
	nSpans = s - span;
}

void doGen(const Go *g, const State *s, uint *bm, uint f, uint m)
{
	Span *b = g->span, *e = &b[g->nSpans];
	uint lb = 0;

	for (; b < e; ++b)
	{
		if (b->to == s)
		{
			for (; lb < b->ub && lb < 256; ++lb)
			{
				bm[lb-f] |= m;
			}
		}

		lb = b->ub;
	}
}

void prt(std::ostream& o, const Go *g, const State *s)
{
	Span *b = g->span, *e = &b[g->nSpans];
	uint lb = 0;

	for (; b < e; ++b)
	{
		if (b->to == s)
		{
			printSpan(o, lb, b->ub);
		}

		lb = b->ub;
	}
}

bool matches(const Go *g1, const State *s1, const Go *g2, const State *s2)
{
	Span *b1 = g1->span, *e1 = &b1[g1->nSpans];
	uint lb1 = 0;
	Span *b2 = g2->span, *e2 = &b2[g2->nSpans];
	uint lb2 = 0;

	for (;;)
	{
		for (; b1 < e1 && b1->to != s1; ++b1)
		{
			lb1 = b1->ub;
		}

		for (; b2 < e2 && b2->to != s2; ++b2)
		{
			lb2 = b2->ub;
		}

		if (b1 == e1)
		{
			return b2 == e2;
		}

		if (b2 == e2)
		{
			return false;
		}

		if (lb1 != lb2 || b1->ub != b2->ub)
		{
			return false;
		}

		++b1;
		++b2;
	}
}

BitMap *BitMap::first = NULL;

BitMap::BitMap(const Go *g, const State *x)
	: go(g)
	, on(x)
	, next(first)
	, i(0)
	, m(0)
{
	first = this;
}

BitMap::~BitMap()
{
	delete next;
}

const BitMap *BitMap::find(const Go *g, const State *x)
{
	for (const BitMap *b = first; b; b = b->next)
	{
		if (matches(b->go, b->on, g, x))
		{
			return b;
		}
	}

	return new BitMap(g, x);
}

const BitMap *BitMap::find(const State *x)
{
	for (const BitMap *b = first; b; b = b->next)
	{
		if (b->on == x)
		{
			return b;
		}
	}

	return NULL;
}

void BitMap::gen(std::ostream &o, uint ind, uint lb, uint ub)
{
	if (first && bLastPass)
	{
		o << indent(ind) << "static const unsigned char " << mapCodeName["yybm"] << "[] = {";

		uint c = 1, n = ub - lb;
		const BitMap *cb = first;

		while((cb = cb->next) != NULL) {
			++c;
		}
		BitMap *b = first;

		uint *bm = new uint[n];
		
		for (uint i = 0, t = 1; b; i += n, t += 8)
		{
			memset(bm, 0, n * sizeof(uint));

			for (uint m = 0x80; b && m; m >>= 1)
			{
				b->i = i;
				b->m = m;
				doGen(b->go, b->on, bm, lb, m);
				b = const_cast<BitMap*>(b->next);
			}

			if (c > 8)
			{
				o << "\n" << indent(ind+1) << "/* table " << t << " .. " << std::min(c, t+7) << ": " << i << " */";
			}

			for (uint j = 0; j < n; ++j)
			{
				if (j % 8 == 0)
				{
					o << "\n" << indent(ind+1);
				}

				if (yybmHexTable)
				{
					prtHex(o, bm[j], false);
				}
				else
				{
					o << std::setw(3) << (uint)bm[j];
				}
				o  << ", ";
			}
		}

		o << "\n" << indent(ind) << "};\n";
		/* stats(); */
		
		delete[] bm;
	}
}

void BitMap::stats()
{
	uint n = 0;

	for (const BitMap *b = first; b; b = b->next)
	{
		prt(std::cerr, b->go, b->on);
		std::cerr << std::endl;
		++n;
	}

	std::cerr << n << " bitmaps\n";
	first = NULL;
}

void genGoTo(std::ostream &o, uint ind, const State *from, const State *to, bool & readCh)
{
	if (readCh && from->label + 1 != to->label)
	{
		o << indent(ind) << mapCodeName["yych"] << " = " << yychConversion << "*" << mapCodeName["YYCURSOR"] << ";\n";
		readCh = false;
	}

	o << indent(ind) << "goto " << labelPrefix << to->label << ";\n";
	vUsedLabels.insert(to->label);
}

void genIf(std::ostream &o, uint ind, const char *cmp, uint v, bool &readCh)
{
	o << indent(ind) << "if(";
	if (readCh)
	{
		o << "(" << mapCodeName["yych"] << " = " << yychConversion << "*" << mapCodeName["YYCURSOR"] << ")";
		readCh = false;
	}
	else
	{
		o << mapCodeName["yych"];
	}

	o << " " << cmp << " ";
	prtChOrHex(o, v);
	o << ") ";
}

static void need(std::ostream &o, uint ind, uint n, bool & readCh, bool bSetMarker)
{
	uint fillIndex = next_fill_index;

	if (fFlag)
	{
		next_fill_index++;
		o << indent(ind) << mapCodeName["YYSETSTATE"] << "(" << fillIndex << ");\n";
	}

	if (bUseYYFill)
	{
		if (n == 1)
		{
			o << indent(ind) << "if(" << mapCodeName["YYLIMIT"] << " == " << mapCodeName["YYCURSOR"] << ") " << mapCodeName["YYFILL"];
		}
		else
		{
			o << indent(ind) << "if((" << mapCodeName["YYLIMIT"] << " - " << mapCodeName["YYCURSOR"] << ") < " << n << ") " << mapCodeName["YYFILL"];
		}
		if (bUseYYFillParam)
		{
			o << "(" << n << ")";
		}
		o << ";\n";
	}

	if (fFlag)
	{
		o << mapCodeName["yyFillLabel"] << fillIndex << ":\n";
	}

	if (bSetMarker)
	{
		o << indent(ind) << mapCodeName["yych"] << " = " << yychConversion << "*(" << mapCodeName["YYMARKER"] << " = " << mapCodeName["YYCURSOR"] << ");\n";
	}
	else
	{
		o << indent(ind) << mapCodeName["yych"] << " = " << yychConversion << "*" << mapCodeName["YYCURSOR"] << ";\n";
	}
	readCh = false;
}

void Match::emit(std::ostream &o, uint ind, bool &readCh) const
{
	if (state->link)
	{
		o << indent(ind) << "++" << mapCodeName["YYCURSOR"] << ";\n";
	}
	else if (!readAhead())
	{
		/* do not read next char if match */
		o << indent(ind) << "++" << mapCodeName["YYCURSOR"] << ";\n";
		readCh = true;
	}
	else
	{
		o << indent(ind) << mapCodeName["yych"] << " = " << yychConversion << "*++" << mapCodeName["YYCURSOR"] << ";\n";
		readCh = false;
	}

	if (state->link)
	{
		need(o, ind, state->depth, readCh, false);
	}
}

void Enter::emit(std::ostream &o, uint ind, bool &readCh) const
{
	if (state->link)
	{
		o << indent(ind) << "++" << mapCodeName["YYCURSOR"] << ";\n";
		if (vUsedLabels.count(label))
		{
			o << labelPrefix << label << ":\n";
		}
		need(o, ind, state->depth, readCh, false);
	}
	else
	{
		/* we shouldn't need 'rule-following' protection here */
		o << indent(ind) << mapCodeName["yych"] << " = " << yychConversion << "*++" << mapCodeName["YYCURSOR"] << ";\n";
		if (vUsedLabels.count(label))
		{
			o << labelPrefix << label << ":\n";
		}
		readCh = false;
	}
}

void Initial::emit(std::ostream &o, uint ind, bool &readCh) const
{
	if (!startLabelName.empty())
	{
		o << startLabelName << ":\n";
	}

	if (vUsedLabels.count(1))
	{
		if (state->link)
		{
			o << indent(ind) << "++" << mapCodeName["YYCURSOR"] << ";\n";
		}
		else
		{
			o << indent(ind) << mapCodeName["yych"] << " = " << yychConversion << "*++" << mapCodeName["YYCURSOR"] << ";\n";
		}
	}

	if (vUsedLabels.count(label))
	{
		o << labelPrefix << label << ":\n";
	}
	else if (!label)
	{
		o << "\n";
	}

	if (dFlag)
	{
		o << indent(ind) << mapCodeName["YYDEBUG"] << "(" << label << ", *" << mapCodeName["YYCURSOR"] << ");\n";
	}

	if (state->link)
	{
		need(o, ind, state->depth, readCh, setMarker && bUsedYYMarker);
	}
	else
	{
		if (setMarker && bUsedYYMarker)
		{
			o << indent(ind) << mapCodeName["YYMARKER"] << " = " << mapCodeName["YYCURSOR"] << ";\n";
		}
		readCh = false;
	}
}

void Save::emit(std::ostream &o, uint ind, bool &readCh) const
{
	if (bUsedYYAccept)
	{
		o << indent(ind) << mapCodeName["yyaccept"] << " = " << selector << ";\n";
	}

	if (state->link)
	{
		if (bUsedYYMarker)
		{
			o << indent(ind) << mapCodeName["YYMARKER"] << " = ++" << mapCodeName["YYCURSOR"] << ";\n";
		}
		need(o, ind, state->depth, readCh, false);
	}
	else
	{
		if (bUsedYYMarker)
		{
			o << indent(ind) << mapCodeName["yych"] << " = " << yychConversion << "*(" << mapCodeName["YYMARKER"] << " = ++" << mapCodeName["YYCURSOR"] << ");\n";
		}
		else
		{
			o << indent(ind) << mapCodeName["yych"] << " = " << yychConversion << "*++" << mapCodeName["YYCURSOR"] << ";\n";
		}
		readCh = false;
	}
}

Move::Move(State *s) : Action(s)
{
	;
}

void Move::emit(std::ostream &, uint, bool &) const
{
	;
}

Accept::Accept(State *x, uint n, uint *s, State **r)
		: Action(x), nRules(n), saves(s), rules(r)
{
	;
}

void Accept::genRuleMap()
{
	for (uint i = 0; i < nRules; ++i)
	{
		if (saves[i] != ~0u)
		{
			mapRules[saves[i]] = rules[i];
		}
	}
}

void Accept::emitBinary(std::ostream &o, uint ind, uint l, uint r, bool &readCh) const
{
	if (l < r)
	{
		uint m = (l + r) >> 1;

		o << indent(ind) << "if(" << mapCodeName["yyaccept"] << " <= " << m << ") {\n";
		emitBinary(o, ++ind, l, m, readCh);
		o << indent(--ind) << "} else {\n";
		emitBinary(o, ++ind, m + 1, r, readCh);
		o << indent(--ind) << "}\n";
	}
	else
	{
		genGoTo(o, ind, state, mapRules.find(l)->second, readCh);
	}
}

void Accept::emit(std::ostream &o, uint ind, bool &readCh) const
{
	if (mapRules.size() > 0)
	{
		bUsedYYMarker = true;
		o << indent(ind) << mapCodeName["YYCURSOR"] << " = " << mapCodeName["YYMARKER"] << ";\n";

		if (readCh) // shouldn't be necessary, but might become at some point
		{
			o << indent(ind) << mapCodeName["yych"] << " = " << yychConversion << "*" << mapCodeName["YYCURSOR"] << ";\n";
			readCh = false;
		}

		if (mapRules.size() > 1)
		{
			bUsedYYAccept = true;

			if (gFlag && mapRules.size() >= cGotoThreshold)
			{
				o << indent(ind++) << "{\n";
				o << indent(ind++) << "static void *" << mapCodeName["yytarget"] << "[" << mapRules.size() << "] = {\n";
				for (RuleMap::const_iterator it = mapRules.begin(); it != mapRules.end(); ++it)
				{
					o << indent(ind) << "&&" << labelPrefix << it->second->label << ",\n";
					vUsedLabels.insert(it->second->label);
				}
				o << indent(--ind) << "};\n";
				o << indent(ind) << "goto *" << mapCodeName["yytarget"] << "[" << mapCodeName["yyaccept"] << "];\n";
				o << indent(--ind) << "}\n";
			}
			else if (sFlag)
			{
				emitBinary(o, ind, 0, mapRules.size() - 1, readCh);
			}
			else
			{
				o << indent(ind) << "switch(" << mapCodeName["yyaccept"] << ") {\n";
		
				for (RuleMap::const_iterator it = mapRules.begin(); it != mapRules.end(); ++it)
				{
					o << indent(ind) << "case " << it->first << ": \t";
					genGoTo(o, 0, state, it->second, readCh);
				}
			
				o << indent(ind) << "}\n";
			}
		}
		else
		{
			// no need to write if statement here since there is only case 0.
			genGoTo(o, ind, state, mapRules.find(0)->second, readCh);
		}
	}
}

Rule::Rule(State *s, RuleOp *r) : Action(s), rule(r)
{
	;
}

void Rule::emit(std::ostream &o, uint ind, bool &) const
{
	uint back = rule->ctx->fixedLength();

	if (back != 0u)
	{
		o << indent(ind) << mapCodeName["YYCURSOR"] << " = " << mapCodeName["YYCTXMARKER"] << ";\n";
	}

	RuleLine rl(*rule);

	o << file_info(sourceFileInfo, &rl);
	o << indent(ind);
	o << rule->code->text;
	o << "\n";
	o << outputFileInfo;
}