code.cc

a little DFA compiler.

void doLinear(std::ostream &o, uint ind, Span *s, uint n, const State *from, const State *next, bool &readCh, uint mask)
{
	for (;;)
	{
		State *bg = s[0].to;

		while (n >= 3 && s[2].to == bg && (s[1].ub - s[0].ub) == 1)
		{
			if (s[1].to == next && n == 3)
			{
				if (!mask || (s[0].ub > 0x00FF))
				{
					genIf(o, ind, "!=", s[0].ub, readCh);
					genGoTo(o, 0, from, bg, readCh);
				}
				if (next->label != from->label + 1)
				{
					genGoTo(o, ind, from, next, readCh);
				}
				return ;
			}
			else
			{
				if (!mask || (s[0].ub > 0x00FF))
				{
					genIf(o, ind, "==", s[0].ub, readCh);
					genGoTo(o, 0, from, s[1].to, readCh);
				}
			}

			n -= 2;
			s += 2;
		}

		if (n == 1)
		{
			//	    	if(bg != next){
			if (s[0].to->label != from->label + 1)
			{
				genGoTo(o, ind, from, s[0].to, readCh);
			}
			//	    	}
			return ;
		}
		else if (n == 2 && bg == next)
		{
			if (!mask || (s[0].ub > 0x00FF))
			{
				genIf(o, ind, ">=", s[0].ub, readCh);
				genGoTo(o, 0, from, s[1].to, readCh);
			}
			if (next->label != from->label + 1)
			{
				genGoTo(o, ind, from, next, readCh);
			}
			return ;
		}
		else
		{
			if (!mask || ((s[0].ub - 1) > 0x00FF))
			{
				genIf(o, ind, "<=", s[0].ub - 1, readCh);
				genGoTo(o, 0, from, bg, readCh);
			}
			n -= 1;
			s += 1;
		}
	}

	if (next->label != from->label + 1)
	{
		genGoTo(o, ind, from, next, readCh);
	}
}

void Go::genLinear(std::ostream &o, uint ind, const State *from, const State *next, bool &readCh, uint mask) const
{
	doLinear(o, ind, span, nSpans, from, next, readCh, mask);
}

bool genCases(std::ostream &o, uint ind, uint lb, Span *s, bool &newLine, uint mask)
{
	bool used = false;

	if (!newLine)
	{
		o << "\n";
	}
	newLine = true;
	if (lb < s->ub)
	{
		for (;;)
		{
			if (!mask || lb > 0x00FF)
			{
				o << indent(ind) << "case ";
				prtChOrHex(o, lb);
				o << ":";
				newLine = false;
				used = true;
			}

			if (++lb == s->ub)
			{
				break;
			}

			o << "\n";
			newLine = true;
		}
	}
	return used;
}

void Go::genSwitch(std::ostream &o, uint ind, const State *from, const State *next, bool &readCh, uint mask) const
{
	bool newLine = true;

	if ((mask ? wSpans : nSpans) <= 2)
	{
		genLinear(o, ind, from, next, readCh, mask);
	}
	else
	{
		State *def = span[nSpans - 1].to;
		Span **sP = new Span * [nSpans - 1], **r, **s, **t;

		t = &sP[0];

		for (uint i = 0; i < nSpans; ++i)
		{
			if (span[i].to != def)
			{
				*(t++) = &span[i];
			}
		}

		if (dFlag)
		{
			o << indent(ind) << mapCodeName["YYDEBUG"] << "(-1, " << mapCodeName["yych"] << ");\n";
		}

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

		while (t != &sP[0])
		{
			bool used = false;

			r = s = &sP[0];

			if (*s == &span[0])
			{
				used |= genCases(o, ind, 0, *s, newLine, mask);
			}
			else
			{
				used |= genCases(o, ind, (*s)[ -1].ub, *s, newLine, mask);
			}

			State *to = (*s)->to;

			while (++s < t)
			{
				if ((*s)->to == to)
				{
					used |= genCases(o, ind, (*s)[ -1].ub, *s, newLine, mask);
				}
				else
				{
					*(r++) = *s;
				}
			}

			if (used)
			{
				genGoTo(o, newLine ? ind+1 : 1, from, to, readCh);
				newLine = true;
			}
			t = r;
		}

		o << indent(ind) << "default:";
		genGoTo(o, 1, from, def, readCh);
		o << indent(ind) << "}\n";

		delete [] sP;
	}
}

void doBinary(std::ostream &o, uint ind, Span *s, uint n, const State *from, const State *next, bool &readCh, uint mask)
{
	if (n <= 4)
	{
		doLinear(o, ind, s, n, from, next, readCh, mask);
	}
	else
	{
		uint h = n / 2;

		genIf(o, ind, "<=", s[h - 1].ub - 1, readCh);
		o << "{\n";
		doBinary(o, ind+1, &s[0], h, from, next, readCh, mask);
		o << indent(ind) << "} else {\n";
		doBinary(o, ind+1, &s[h], n - h, from, next, readCh, mask);
		o << indent(ind) << "}\n";
	}
}

void Go::genBinary(std::ostream &o, uint ind, const State *from, const State *next, bool &readCh, uint mask) const
{
	if (mask)
	{
		Span * sc = new Span[wSpans];
		
		for (uint i = 0, j = 0; i < nSpans; i++)
		{
			if (span[i].ub > 0xFF)
			{
				sc[j++] = span[i];
			}
		}

		doBinary(o, ind, sc, wSpans, from, next, readCh, mask);

		delete[] sc;
	}
	else
	{
		doBinary(o, ind, span, nSpans, from, next, readCh, mask);
	}
}

void Go::genBase(std::ostream &o, uint ind, const State *from, const State *next, bool &readCh, uint mask) const
{
	if ((mask ? wSpans : nSpans) == 0)
	{
		return ;
	}

	if (!sFlag)
	{
		genSwitch(o, ind, from, next, readCh, mask);
		return ;
	}

	if ((mask ? wSpans : nSpans) > 8)
	{
		Span *bot = &span[0], *top = &span[nSpans - 1];
		uint util;

		if (bot[0].to == top[0].to)
		{
			util = (top[ -1].ub - bot[0].ub) / (nSpans - 2);
		}
		else
		{
			if (bot[0].ub > (top[0].ub - top[ -1].ub))
			{
				util = (top[0].ub - bot[0].ub) / (nSpans - 1);
			}
			else
			{
				util = top[ -1].ub / (nSpans - 1);
			}
		}

		if (util <= 2)
		{
			genSwitch(o, ind, from, next, readCh, mask);
			return ;
		}
	}

	if ((mask ? wSpans : nSpans) > 5)
	{
		genBinary(o, ind, from, next, readCh, mask);
	}
	else
	{
		genLinear(o, ind, from, next, readCh, mask);
	}
}

void Go::genCpGoto(std::ostream &o, uint ind, const State *from, const State *next, bool &readCh) const
{
	std::string sYych;
	
	if (readCh)
	{
		sYych = "(" + mapCodeName["yych"] + " = " + yychConversion + "*" + mapCodeName["YYCURSOR"] + ")";
	}
	else
	{
		sYych = mapCodeName["yych"];
	}

	readCh = false;
	if (wFlag)
	{
		o << indent(ind) << "if(" << sYych <<" & ~0xFF) {\n";
		genBase(o, ind+1, from, next, readCh, 1);
		o << indent(ind++) << "} else {\n";
		sYych = mapCodeName["yych"];
	}
	else
	{
		o << indent(ind++) << "{\n";
	}
	o << indent(ind++) << "static void *" << mapCodeName["yytarget"] << "[256] = {\n";
	o << indent(ind);

	uint ch = 0;
	for (uint i = 0; i < lSpans; ++i)
	{
		vUsedLabels.insert(span[i].to->label);
		for(; ch < span[i].ub; ++ch)
		{
			o << "&&" << labelPrefix << span[i].to->label;
			if (ch == 255)
			{
				o << "\n";
				i = lSpans;
				break;
			}
			else if (ch % 8 == 7)
			{
				o << ",\n" << indent(ind);
			}
			else
			{
				o << "," << space(span[i].to->label);
			}
		}
	}
	o << indent(--ind) << "};\n";
	o << indent(ind) << "goto *" << mapCodeName["yytarget"] << "[" << sYych << "];\n";
	o << indent(--ind) << "}\n";
}

void Go::genGoto(std::ostream &o, uint ind, const State *from, const State *next, bool &readCh)
{
	if ((gFlag || wFlag) && wSpans == ~0u)
	{
		uint nBitmaps = 0;
		std::set<uint> vTargets;
		wSpans = 0;
		lSpans = 1;
		dSpans = 0;
		for (uint i = 0; i < nSpans; ++i)
		{
			if (span[i].ub > 0xFF)
			{
				wSpans++;
			}
			if (span[i].ub < 0x100 || !wFlag)
			{
				lSpans++;

				State *to = span[i].to;
	
				if (to && to->isBase)
				{
					const BitMap *b = BitMap::find(to);
	
					if (b && matches(b->go, b->on, this, to))
					{
						nBitmaps++;
					}
					else
					{
						dSpans++;
						vTargets.insert(to->label);
					}
				}
				else
				{
					dSpans++;
					vTargets.insert(to->label);
				}
			}
		}
		lTargets = vTargets.size() >> nBitmaps;
	}

	if (gFlag && (lTargets >= cGotoThreshold || dSpans >= cGotoThreshold))
	{
		genCpGoto(o, ind, from, next, readCh);
		return;
	}
	else if (bFlag)
	{
		for (uint i = 0; i < nSpans; ++i)
		{
			State *to = span[i].to;

			if (to && to->isBase)
			{
				const BitMap *b = BitMap::find(to);
				std::string sYych;

				if (b && matches(b->go, b->on, this, to))
				{
					Go go;
					go.span = new Span[nSpans];
					go.unmap(this, to);
					if (readCh)
					{
						sYych = "(" + mapCodeName["yych"] + " = " + yychConversion + "*" + mapCodeName["YYCURSOR"] + ")";
					}
					else
					{
						sYych = mapCodeName["yych"];
					}
					readCh = false;
					if (wFlag)
					{
						o << indent(ind) << "if(" << sYych << " & ~0xFF) {\n";
						sYych = mapCodeName["yych"];
						genBase(o, ind+1, from, next, readCh, 1);
						o << indent(ind) << "} else ";
					}
					else
					{
						o << indent(ind);
					}
					o << "if(" << mapCodeName["yybm"] << "[" << b->i << "+" << sYych << "] & ";
					if (yybmHexTable)
					{
						prtHex(o, b->m, false);
					}
					else
					{
						o << (uint) b->m;
					}
					o << ") {\n";
					genGoTo(o, ind+1, from, to, readCh);
					o << indent(ind) << "}\n";
					go.genBase(o, ind, from, next, readCh, 0);
					delete [] go.span;
					return ;
				}
			}
		}
	}

	genBase(o, ind, from, next, readCh, 0);
}

void State::emit(std::ostream &o, uint ind, bool &readCh) const
{
	if (vUsedLabels.count(label))
	{
		o << labelPrefix << label << ":\n";
	}
	if (dFlag && !action->isInitial())
	{
		o << indent(ind) << mapCodeName["YYDEBUG"] << "(" << label << ", *" << mapCodeName["YYCURSOR"] << ");\n";
	}
	if (isPreCtxt)
	{
		o << indent(ind) << mapCodeName["YYCTXMARKER"] << " = " << mapCodeName["YYCURSOR"] << " + 1;\n";
	}
	action->emit(o, ind, readCh);
}

uint merge(Span *x0, State *fg, State *bg)
{
	Span *x = x0, *f = fg->go.span, *b = bg->go.span;
	uint nf = fg->go.nSpans, nb = bg->go.nSpans;
	State *prev = NULL, *to;
	// NB: we assume both spans are for same range

	for (;;)
	{
		if (f->ub == b->ub)
		{
			to = f->to == b->to ? bg : f->to;

			if (to == prev)
			{
				--x;
			}
			else
			{
				x->to = prev = to;
			}

			x->ub = f->ub;
			++x;
			++f;
			--nf;
			++b;
			--nb;

			if (nf == 0 && nb == 0)
			{
				return x - x0;
			}
		}

		while (f->ub < b->ub)
		{
			to = f->to == b->to ? bg : f->to;

			if (to == prev)
			{
				--x;
			}
			else
			{
				x->to = prev = to;
			}

			x->ub = f->ub;
			++x;
			++f;
			--nf;
		}

		while (b->ub < f->ub)
		{
			to = b->to == f->to ? bg : f->to;

			if (to == prev)
			{
				--x;
			}
			else
			{
				x->to = prev = to;
			}

			x->ub = b->ub;
			++x;
			++b;
			--nb;
		}
	}
}

const uint cInfinity = ~0;

class SCC
{

public:
	State	**top, **stk;

public:
	SCC(uint);
	~SCC();
	void traverse(State*);

#ifdef PEDANTIC
private:
	SCC(const SCC& oth)
		: top(oth.top)
		, stk(oth.stk)
	{
	}
	SCC& operator = (const SCC& oth)
	{
		new(this) SCC(oth);
		return *this;
	}
#endif
};

SCC::SCC(uint size)
	: top(new State * [size])
	, stk(top)
{
}

SCC::~SCC()
{
	delete [] stk;
}

void SCC::traverse(State *x)
{
	*top = x;
	uint k = ++top - stk;
	x->depth = k;

	for (uint i = 0; i < x->go.nSpans; ++i)
	{
		State *y = x->go.span[i].to;

		if (y)
		{
			if (y->depth == 0)
			{
				traverse(y);