re2c::Skeleton Struct Reference

#include <skeleton.h>

Collaboration diagram for re2c::Skeleton:

Public Member Functions
	Skeleton (const dfa_t &dfa, const charset_t &cs, const rules_t &rs, const std::string &dfa_name, const std::string &dfa_cond, uint32_t dfa_line)
	~Skeleton ()
void	warn_undefined_control_flow ()
void	warn_unreachable_rules ()
void	warn_match_empty ()
void	emit_data (const char *fname)
void	emit_start (OutputFile &o, size_t maxfill, bool backup, bool backupctx, bool accept) const
void	emit_end (OutputFile &o, bool backup, bool backupctx) const
void	emit_action (OutputFile &o, uint32_t ind, rule_rank_t rank) const
uint32_t	rule2key (rule_rank_t r) const

Static Public Member Functions
static void	emit_prolog (OutputFile &o)
static void	emit_epilog (OutputFile &o, const std::set< std::string > &names)
template<typename key_t >
static key_t	rule2key (rule_rank_t r)

Public Attributes
const std::string	name
const std::string	cond
const uint32_t	line
const size_t	nodes_count
Node *	nodes
size_t	sizeof_key
rules_t	rules

Detailed Description

Definition at line 107 of file skeleton.h.

Constructor & Destructor Documentation

re2c::Skeleton::Skeleton	(	const dfa_t &	dfa,
		const charset_t &	cs,
		const rules_t &	rs,
		const std::string &	dfa_name,
		const std::string &	dfa_cond,
		uint32_t	dfa_line
	)

Definition at line 73 of file skeleton.cc.

    : name (dfa_name)
    , cond (dfa_cond)
    , line (dfa_line)
    , nodes_count (dfa.states.size())
    , nodes (new Node [nodes_count + 1]) // +1 for default state
    , sizeof_key (4)
    , rules (rs)
{
    const size_t nc = cs.size() - 1;

    // initialize skeleton nodes
    Node *nil = &nodes[nodes_count];
    for (size_t i = 0; i < nodes_count; ++i)
    {
        dfa_state_t *s = dfa.states[i];
        std::vector<std::pair<Node*, uint32_t> > arcs;
        for (size_t c = 0; c < nc;)
        {
            const size_t j = s->arcs[c];
            for (;++c < nc && s->arcs[c] == j;);
            Node *to = j == dfa_t::NIL
                ? nil
                : &nodes[j];
            arcs.push_back(std::make_pair(to, cs[c]));
        }
        // all arcs go to default node => this node is final, drop arcs
        if (arcs.size() == 1 && arcs[0].first == nil)
        {
            arcs.clear();
        }
        nodes[i].init(s->ctx, s->rule, arcs);
    }

    // calculate maximal path length, check overflow
    nodes->calc_dist ();
    const uint32_t maxlen = nodes->dist;
    if (maxlen == Node::DIST_MAX)
    {
        error ("DFA path %sis too long", incond (cond).c_str ());
        exit (1);
    }

    // calculate maximal rule rank (disregarding default and none rules)
    uint32_t maxrule = 0;
    for (uint32_t i = 0; i < nodes_count; ++i)
    {
        const rule_rank_t r = nodes[i].rule.rank;
        if (!r.is_none () && !r.is_def ())
        {
            maxrule = std::max (maxrule, r.uint32 ());
        }
    }
    // two upper values reserved for default and none rules)
    maxrule += 2;

    // initialize size of key
    const uint32_t max = std::max (maxlen, maxrule);
    if (max <= std::numeric_limits<uint8_t>::max())
    {
        sizeof_key = 1;
    }
    else if (max <= std::numeric_limits<uint16_t>::max())
    {
        sizeof_key = 2;
    }
}

Here is the call graph for this function:

re2c::Skeleton::~Skeleton

(

)

Definition at line 147 of file skeleton.cc.

{
    delete [] nodes;
}

Member Function Documentation

void re2c::Skeleton::emit_action	(	OutputFile &	o,
		uint32_t	ind,
		rule_rank_t	rank
	)		const

Definition at line 317 of file generate_code.cc.

{
    o.wind(ind).ws("status = action_").wstring(name).ws("(i, keys, input, token, &cursor, ").wu32(rule2key (rank)).ws(");\n");
    o.wind(ind).ws("continue;\n");
}

Here is the call graph for this function:

Here is the caller graph for this function:

void re2c::Skeleton::emit_data

(

const char *

fname

)

Definition at line 127 of file generate_data.cc.

{
    const std::string input_name = std::string (fname) + "." + name + ".input";
    FILE * input = fopen (input_name.c_str (), "wb");
    if (!input)
    {
        error ("cannot open file: %s", input_name.c_str ());
        exit (1);
    }
    const std::string keys_name = std::string (fname) + "." + name + ".keys";
    FILE * keys = fopen (keys_name.c_str (), "wb");
    if (!keys)
    {
        error ("cannot open file: %s", keys_name.c_str ());
        exit (1);
    }

    generate_paths (input, keys);

    fclose (input);
    fclose (keys);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void re2c::Skeleton::emit_end	(	OutputFile &	o,
		bool	backup,
		bool	backupctx
	)		const

Definition at line 256 of file generate_code.cc.

{
    o.ws("\n").wind(1).ws("}");
    o.ws("\n").wind(1).ws("if (status == 0) {");
    o.ws("\n").wind(2).ws("if (cursor != eof) {");
    o.ws("\n").wind(3).ws("status = 1;");
    o.ws("\n").wind(3).ws("const long pos = token - input;");
    o.ws("\n").wind(3).ws("fprintf(stderr, \"error: lex_").wstring(name).ws(": unused input strings left at position %ld\\n\", pos);");
    o.ws("\n").wind(2).ws("}");
    o.ws("\n").wind(2).ws("if (i != keys_count) {");
    o.ws("\n").wind(3).ws("status = 1;");
    o.ws("\n").wind(3).ws("fprintf(stderr, \"error: lex_").wstring(name).ws(": unused keys left after %u iterations\\n\", i);");
    o.ws("\n").wind(2).ws("}");
    o.ws("\n").wind(1).ws("}");
    o.ws("\n");
    o.ws("\nend:");
    o.ws("\n").wind(1).ws("free(input);");
    o.ws("\n").wind(1).ws("free(keys);");
    o.ws("\n");
    o.ws("\n").wind(1).ws("return status;");
    o.ws("\n}");
    o.ws("\n");
    o.ws("\n#undef YYCTYPE");
    o.ws("\n#undef YYKEYTYPE");
    o.ws("\n#undef YYPEEK");
    o.ws("\n#undef YYSKIP");
    if (backup)
    {
        o.ws("\n#undef YYBACKUP");
        o.ws("\n#undef YYRESTORE");
    }
    if (backupctx)
    {
        o.ws("\n#undef YYBACKUPCTX");
        o.ws("\n#undef YYRESTORECTX");
    }
    o.ws("\n#undef YYLESSTHAN");
    o.ws("\n#undef YYFILL");
    o.ws("\n");
}

Here is the call graph for this function:

Here is the caller graph for this function:

void re2c::Skeleton::emit_epilog ( OutputFile &  o, const std::set< std::string > &  names  )

static

Definition at line 300 of file generate_code.cc.

{
    o.ws("\n").ws("int main()");
    o.ws("\n").ws("{");

    for (std::set<std::string>::const_iterator i = names.begin (); i != names.end (); ++i)
    {
        o.ws("\n").wind(1).ws("if(lex_").wstring(*i).ws("() != 0) {");
        o.ws("\n").wind(2).ws("return 1;");
        o.ws("\n").wind(1).ws("}");
    }

    o.ws("\n").wind(1).ws("return 0;");
    o.ws("\n}");
    o.ws("\n");
}

Here is the call graph for this function:

void re2c::Skeleton::emit_prolog ( OutputFile &  o )

static

Definition at line 54 of file generate_code.cc.

{
    o.ws("\n#include <stdio.h>");
    o.ws("\n#include <stdlib.h> /* malloc, free */");
    o.ws("\n");
    o.ws("\nstatic void *read_file");
    o.ws("\n").wind(1).ws("( const char *fname");
    o.ws("\n").wind(1).ws(", size_t unit");
    o.ws("\n").wind(1).ws(", size_t padding");
    o.ws("\n").wind(1).ws(", size_t *pfsize");
    o.ws("\n").wind(1).ws(")");
    o.ws("\n{");
    o.ws("\n").wind(1).ws("void *buffer = NULL;");
    o.ws("\n").wind(1).ws("size_t fsize = 0;");
    o.ws("\n");
    o.ws("\n").wind(1).ws("/* open file */");
    o.ws("\n").wind(1).ws("FILE *f = fopen(fname, \"rb\");");
    o.ws("\n").wind(1).ws("if(f == NULL) {");
    o.ws("\n").wind(2).ws("goto error;");
    o.ws("\n").wind(1).ws("}");
    o.ws("\n");
    o.ws("\n").wind(1).ws("/* get file size */");
    o.ws("\n").wind(1).ws("fseek(f, 0, SEEK_END);");
    o.ws("\n").wind(1).ws("fsize = (size_t) ftell(f) / unit;");
    o.ws("\n").wind(1).ws("fseek(f, 0, SEEK_SET);");
    o.ws("\n");
    o.ws("\n").wind(1).ws("/* allocate memory for file and padding */");
    o.ws("\n").wind(1).ws("buffer = malloc(unit * (fsize + padding));");
    o.ws("\n").wind(1).ws("if (buffer == NULL) {");
    o.ws("\n").wind(2).ws("goto error;");
    o.ws("\n").wind(1).ws("}");
    o.ws("\n");
    o.ws("\n").wind(1).ws("/* read the whole file in memory */");
    o.ws("\n").wind(1).ws("if (fread(buffer, unit, fsize, f) != fsize) {");
    o.ws("\n").wind(2).ws("goto error;");
    o.ws("\n").wind(1).ws("}");
    o.ws("\n");
    o.ws("\n").wind(1).ws("fclose(f);");
    o.ws("\n").wind(1).ws("*pfsize = fsize;");
    o.ws("\n").wind(1).ws("return buffer;");
    o.ws("\n");
    o.ws("\nerror:");
    o.ws("\n").wind(1).ws("fprintf(stderr, \"error: cannot read file '%s'\\n\", fname);");
    o.ws("\n").wind(1).ws("free(buffer);");
    o.ws("\n").wind(1).ws("if (f != NULL) {");
    o.ws("\n").wind(2).ws("fclose(f);");
    o.ws("\n").wind(1).ws("}");
    o.ws("\n").wind(1).ws("return NULL;");
    o.ws("\n}");
    o.ws("\n");
}

Here is the call graph for this function:

void re2c::Skeleton::emit_start	(	OutputFile &	o,
		size_t	maxfill,
		bool	backup,
		bool	backupctx,
		bool	accept
	)		const

Definition at line 107 of file generate_code.cc.

{
    const size_t sizeof_cunit = opts->encoding.szCodeUnit();
    const uint32_t default_rule = rule2key (rule_rank_t::none ());

    o.ws("\n#define YYCTYPE ");
    exact_uint (o, sizeof_cunit);
    o.ws("\n#define YYKEYTYPE ");
    exact_uint (o, sizeof_key);
    o.ws("\n#define YYPEEK() *cursor");
    o.ws("\n#define YYSKIP() ++cursor");
    if (backup)
    {
        o.ws("\n#define YYBACKUP() marker = cursor");
        o.ws("\n#define YYRESTORE() cursor = marker");
    }
    if (backupctx)
    {
        o.ws("\n#define YYBACKUPCTX() ctxmarker = cursor");
        o.ws("\n#define YYRESTORECTX() cursor = ctxmarker");
    }
    o.ws("\n#define YYLESSTHAN(n) (limit - cursor) < n");
    o.ws("\n#define YYFILL(n) { break; }");
    o.ws("\n");
    o.ws("\nstatic int action_").wstring(name);
    o.ws("\n").wind(1).ws("( unsigned int i");
    o.ws("\n").wind(1).ws(", const YYKEYTYPE *keys");
    o.ws("\n").wind(1).ws(", const YYCTYPE *start");
    o.ws("\n").wind(1).ws(", const YYCTYPE *token");
    o.ws("\n").wind(1).ws(", const YYCTYPE **cursor");
    o.ws("\n").wind(1).ws(", YYKEYTYPE rule_act");
    o.ws("\n").wind(1).ws(")");
    o.ws("\n{");
    o.ws("\n").wind(1).ws("const long pos = token - start;");
    o.ws("\n").wind(1).ws("const long len_act = *cursor - token;");
    o.ws("\n").wind(1).ws("const long len_exp = (long) keys [3 * i + 1];");
    o.ws("\n").wind(1).ws("const YYKEYTYPE rule_exp = keys [3 * i + 2];");
    o.ws("\n").wind(1).ws("if (rule_exp == ").wu32(default_rule).ws(") {");
    o.ws("\n").wind(2).ws("fprintf");
    o.ws("\n").wind(3).ws("( stderr");
    o.ws("\n").wind(3).ws(", \"warning: lex_").wstring(name).ws(": control flow is undefined for input\"");
    o.ws("\n").wind(4).ws("\" at position %ld, rerun re2c with '-W'\\n\"");
    o.ws("\n").wind(3).ws(", pos");
    o.ws("\n").wind(3).ws(");");
    o.ws("\n").wind(1).ws("}");
    o.ws("\n").wind(1).ws("if (len_act == len_exp && rule_act == rule_exp) {");
    o.ws("\n").wind(2).ws("const YYKEYTYPE offset = keys[3 * i];");
    o.ws("\n").wind(2).ws("*cursor = token + offset;");
    o.ws("\n").wind(2).ws("return 0;");
    o.ws("\n").wind(1).ws("} else {");
    o.ws("\n").wind(2).ws("fprintf");
    o.ws("\n").wind(3).ws("( stderr");
    o.ws("\n").wind(3).ws(", \"error: lex_").wstring(name).ws(": at position %ld (iteration %u):\\n\"");
    o.ws("\n").wind(4).ws("\"\\texpected: match length %ld, rule %u\\n\"");
    o.ws("\n").wind(4).ws("\"\\tactual:   match length %ld, rule %u\\n\"");
    o.ws("\n").wind(3).ws(", pos");
    o.ws("\n").wind(3).ws(", i");
    o.ws("\n").wind(3).ws(", len_exp");
    o.ws("\n").wind(3).ws(", rule_exp");
    o.ws("\n").wind(3).ws(", len_act");
    o.ws("\n").wind(3).ws(", rule_act");
    o.ws("\n").wind(3).ws(");");
    o.ws("\n").wind(2).ws("return 1;");
    o.ws("\n").wind(1).ws("}");
    o.ws("\n}");
    o.ws("\n");
    o.ws("\nint lex_").wstring(name).ws("()");
    o.ws("\n{");
    o.ws("\n").wind(1).ws("const size_t padding = ").wu64(maxfill).ws("; /* YYMAXFILL */");
    o.ws("\n").wind(1).ws("int status = 0;");
    o.ws("\n").wind(1).ws("size_t input_len = 0;");
    o.ws("\n").wind(1).ws("size_t keys_count = 0;");
    o.ws("\n").wind(1).ws("YYCTYPE *input = NULL;");
    o.ws("\n").wind(1).ws("YYKEYTYPE *keys = NULL;");
    o.ws("\n").wind(1).ws("const YYCTYPE *cursor = NULL;");
    o.ws("\n").wind(1).ws("const YYCTYPE *limit = NULL;");
    o.ws("\n").wind(1).ws("const YYCTYPE *token = NULL;");
    o.ws("\n").wind(1).ws("const YYCTYPE *eof = NULL;");
    o.ws("\n").wind(1).ws("unsigned int i = 0;");
    o.ws("\n");
    o.ws("\n").wind(1).ws("input = (YYCTYPE *) read_file");
    o.ws("\n").wind(2).ws("(\"").wstring(o.file_name).ws(".").wstring(name).ws(".input\"");
    o.ws("\n").wind(2).ws(", sizeof (YYCTYPE)");
    o.ws("\n").wind(2).ws(", padding");
    o.ws("\n").wind(2).ws(", &input_len");
    o.ws("\n").wind(2).ws(");");
    o.ws("\n").wind(1).ws("if (input == NULL) {");
    o.ws("\n").wind(2).ws("status = 1;");
    o.ws("\n").wind(2).ws("goto end;");
    o.ws("\n").wind(1).ws("}");
    o.ws("\n");
    if (sizeof_cunit > 1)
    {
        o.ws("\n").wind(1).ws("for (i = 0; i < input_len; ++i) {");
        from_le(o, 2, sizeof_cunit, "input[i]");
        o.ws("\n").wind(1).ws("}");
        o.ws("\n");
    }
    o.ws("\n").wind(1).ws("keys = (YYKEYTYPE *) read_file");
    o.ws("\n").wind(2).ws("(\"").wstring(o.file_name).ws(".").wstring(name).ws(".keys\"");
    o.ws("\n").wind(2).ws(", 3 * sizeof (YYKEYTYPE)");
    o.ws("\n").wind(2).ws(", 0");
    o.ws("\n").wind(2).ws(", &keys_count");
    o.ws("\n").wind(2).ws(");");
    o.ws("\n").wind(1).ws("if (keys == NULL) {");
    o.ws("\n").wind(2).ws("status = 1;");
    o.ws("\n").wind(2).ws("goto end;");
    o.ws("\n").wind(1).ws("}");
    o.ws("\n");
    if (sizeof_key > 1)
    {
        o.ws("\n").wind(1).ws("for (i = 0; i < 3 * keys_count; ++i) {");
        from_le(o, 2, sizeof_key, "keys[i]");
        o.ws("\n").wind(1).ws("}");
        o.ws("\n");
    }
    o.ws("\n").wind(1).ws("cursor = input;");
    o.ws("\n").wind(1).ws("limit = input + input_len + padding;");
    o.ws("\n").wind(1).ws("eof = input + input_len;");
    o.ws("\n");
    o.ws("\n").wind(1).ws("for (i = 0; status == 0 && i < keys_count; ++i) {");
    o.ws("\n").wind(2).ws("token = cursor;");
    if (backup)
    {
        o.ws("\n").wind(2).ws("const YYCTYPE *marker = NULL;");
    }
    if (backupctx)
    {
        o.ws("\n").wind(2).ws("const YYCTYPE *ctxmarker = NULL;");
    }
    o.ws("\n").wind(2).ws("YYCTYPE yych;");
    if (accept)
    {
        o.ws("\n").wind(2).ws("unsigned int yyaccept = 0;");
    }
    o.ws("\n");
    if (opts->bFlag && BitMap::first)
    {
        BitMap::gen (o, 2, 0, std::min (0x100u, opts->encoding.nCodeUnits ()));
    }
    o.ws("\n");
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename key_t >

key_t re2c::Skeleton::rule2key ( rule_rank_t  r )

static

Definition at line 160 of file skeleton.h.

{
    if (r.is_none()) {
        return std::numeric_limits<key_t>::max();
    } else if (r.is_def()) {
        key_t k = std::numeric_limits<key_t>::max();
        return --k;
    } else {
        return static_cast<key_t>(r.uint32());
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

uint32_t re2c::Skeleton::rule2key

(

rule_rank_t

r

)

const

Definition at line 152 of file skeleton.cc.

{
    switch (sizeof_key)
    {
        default: // shouldn't happen
        case 4: return rule2key<uint32_t> (r);
        case 2: return rule2key<uint16_t> (r);
        case 1: return rule2key<uint8_t>  (r);
    }
}

void re2c::Skeleton::warn_match_empty

(

)

Definition at line 14 of file match_empty.cc.

{
    Node & head = nodes[0];

    head.calc_reachable ();
    const std::set<rule_t> & reach = head.reachable;

    // warn about rules that match empty string
    if (!head.rule.rank.is_none ())
    {
        bool reachable = head.end ();
        for (std::set<rule_t>::const_iterator i = reach.begin ();
            !reachable && i != reach.end (); ++i)
        {
            reachable |= i->rank.is_none ();
        }
        if (reachable)
        {
            warn.match_empty_string (rules[head.rule.rank].line);
        }
    }

    // warn about rules that match empty string with nonempty trailing context
    if (head.ctx)
    {
        for (std::set<rule_t>::const_iterator i = reach.begin (); i != reach.end (); ++i)
        {
            if (i->restorectx)
            {
                warn.match_empty_string (rules[i->rank].line);
            }
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void re2c::Skeleton::warn_undefined_control_flow

(

)

Definition at line 43 of file control_flow.cc.

{
    way_t prefix;
    std::vector<way_t> ways;
    Node::nakeds_t size = Node::nakeds_t::from32(0u);

    nodes->naked_ways (prefix, ways, size);

    if (!ways.empty ())
    {
        warn.undefined_control_flow (line, cond, ways, size.overflow ());
    }
    else if (size.overflow ())
    {
        warn.fail (Warn::UNDEFINED_CONTROL_FLOW, line, "DFA is too large to check undefined control flow");
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void re2c::Skeleton::warn_unreachable_rules

(

)

Definition at line 37 of file unreachable.cc.

{
    nodes->calc_reachable ();
    for (uint32_t i = 0; i < nodes_count; ++i)
    {
        const rule_rank_t r1 = nodes[i].rule.rank;
        const std::set<rule_t> & rs = nodes[i].reachable;
        for (std::set<rule_t>::const_iterator j = rs.begin (); j != rs.end (); ++j)
        {
            const rule_rank_t r2 = j->rank;
            if (r1 == r2 || r2.is_none ())
            {
                rules[r1].reachable = true;
            }
            else
            {
                rules[r1].shadow.insert (r2);
            }
        }
    }

    // warn about unreachable rules:
    //   - rules that are shadowed by other rules, e.g. rule '[a]' is shadowed by '[a] [^]'
    //   - infinite rules that consume infinitely many characters and fail on YYFILL, e.g. '[^]*'
    //   - rules that contain never-matching link, e.g. '[]' with option '--empty-class match-none'
    // default rule '*' should not be reported
    for (rules_t::const_iterator i = rules.begin (); i != rules.end (); ++i)
    {
        const rule_rank_t r = i->first;
        if (!r.is_none () && !r.is_def () && !rules[r].reachable)
        {
            warn.unreachable_rule (cond, i->second, rules);
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

const std::string re2c::Skeleton::cond

Definition at line 110 of file skeleton.h.

const uint32_t re2c::Skeleton::line

Definition at line 111 of file skeleton.h.

const std::string re2c::Skeleton::name

Definition at line 109 of file skeleton.h.

Node* re2c::Skeleton::nodes

Definition at line 114 of file skeleton.h.

const size_t re2c::Skeleton::nodes_count

Definition at line 113 of file skeleton.h.

rules_t re2c::Skeleton::rules

Definition at line 116 of file skeleton.h.

size_t re2c::Skeleton::sizeof_key

Definition at line 115 of file skeleton.h.

---

The documentation for this struct was generated from the following files:

• ir/skeleton/skeleton.h
• ir/skeleton/control_flow.cc
• ir/skeleton/generate_code.cc
• ir/skeleton/generate_data.cc
• ir/skeleton/match_empty.cc
• ir/skeleton/skeleton.cc
• ir/skeleton/unreachable.cc