prepare.cc

Go to the documentation of this file.

#include "src/util/c99_stdint.h"
#include <string.h>
#include <map>

#include "src/codegen/bitmap.h"
#include "src/codegen/go.h"
#include "src/globals.h"
#include "src/ir/adfa/action.h"
#include "src/ir/adfa/adfa.h"
#include "src/ir/regexp/regexp_rule.h"
#include "src/ir/rule_rank.h"
#include "src/util/allocate.h"

namespace re2c {

void DFA::split(State *s)
{
    State *move = new State;
    addState(move, s);
    move->action.set_move ();
    move->rule = s->rule;
    move->fill = s->fill;
    move->go = s->go;
    s->rule = NULL;
    s->go.nSpans = 1;
    s->go.span = allocate<Span> (1);
    s->go.span[0].ub = ubChar;
    s->go.span[0].to = move;
}

static uint32_t merge(Span *x0, State *fg, State *bg)
{
    Span *x = x0, *f = fg->go.span, *b = bg->go.span;
    uint32_t 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 static_cast<uint32_t> (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;
        }
    }
}

void DFA::findBaseState()
{
    Span *span = allocate<Span> (ubChar - lbChar);

    for (State *s = head; s; s = s->next)
    {
        if (s->fill == 0)
        {
            for (uint32_t i = 0; i < s->go.nSpans; ++i)
            {
                State *to = s->go.span[i].to;

                if (to->isBase)
                {
                    to = to->go.span[0].to;
                    uint32_t nSpans = merge(span, s, to);

                    if (nSpans < s->go.nSpans)
                    {
                        operator delete (s->go.span);
                        s->go.nSpans = nSpans;
                        s->go.span = allocate<Span> (nSpans);
                        memcpy(s->go.span, span, nSpans*sizeof(Span));
                    }

                    break;
                }
            }
        }
    }

    operator delete (span);
}

void DFA::prepare ()
{
    bUsedYYBitmap = false;

    // create rule states
    std::map<rule_rank_t, State *> rules;
    for (State * s = head; s; s = s->next)
    {
        if (s->rule)
        {
            if (rules.find (s->rule->rank) == rules.end ())
            {
                State *n = new State;
                n->action.set_rule (s->rule);
                rules[s->rule->rank] = n;
                addState(n, s);
            }
            for (uint32_t i = 0; i < s->go.nSpans; ++i)
            {
                if (!s->go.span[i].to)
                {
                    s->go.span[i].to = rules[s->rule->rank];
                }
            }
        }
    }

    // create default state (if needed)
    State * default_state = NULL;
    for (State * s = head; s; s = s->next)
    {
        for (uint32_t i = 0; i < s->go.nSpans; ++i)
        {
            if (!s->go.span[i].to)
            {
                if (!default_state)
                {
                    default_state = new State;
                    addState(default_state, s);
                }
                s->go.span[i].to = default_state;
            }
        }
    }

    // find backup states and create accept state (if needed)
    if (default_state)
    {
        for (State * s = head; s; s = s->next)
        {
            if (s->rule)
            {
                for (uint32_t i = 0; i < s->go.nSpans; ++i)
                {
                    if (!s->go.span[i].to->rule && s->go.span[i].to->action.type != Action::RULE)
                    {
                        const uint32_t accept = static_cast<uint32_t> (accepts.find_or_add (rules[s->rule->rank]));
                        s->action.set_save (accept);
                    }
                }
            }
        }
        default_state->action.set_accept (&accepts);
    }

    // split ``base'' states into two parts
    for (State * s = head; s; s = s->next)
    {
        s->isBase = false;

        if (s->fill != 0)
        {
            for (uint32_t i = 0; i < s->go.nSpans; ++i)
            {
                if (s->go.span[i].to == s)
                {
                    s->isBase = true;
                    split(s);

                    if (opts->bFlag)
                    {
                        BitMap::find(&s->next->go, s);
                    }

                    s = s->next;
                    break;
                }
            }
        }
    }

    // find ``base'' state, if possible
    findBaseState();

    for (State * s = head; s; s = s->next)
    {
        s->go.init (s);
    }
}

void DFA::calc_stats ()
{
    // calculate 'YYMAXFILL'
    max_fill = 0;
    for (State * s = head; s; s = s->next)
    {
        if (max_fill < s->fill)
        {
            max_fill = s->fill;
        }
    }

    // determine if 'YYMARKER' or 'YYBACKUP'/'YYRESTORE' pair is used
    need_backup = accepts.size () > 0;

    // determine if 'YYCTXMARKER' or 'YYBACKUPCTX'/'YYRESTORECTX' pair is used
    for (State * s = head; s; s = s->next)
    {
        if (s->isPreCtxt)
        {
            need_backupctx = true;
        }
    }

    // determine if 'yyaccept' variable is used
    need_accept = accepts.size () > 1;
}

} // namespace re2c