stapregex-dfa.h

// -*- C++ -*-
// Copyright (C) 2012-2013 Red Hat Inc.
//
// This file is part of systemtap, and is free software.  You can
// redistribute it and/or modify it under the terms of the GNU General
// Public License (GPL); either version 2, or (at your option) any
// later version.
//
// ---
//
// This file incorporates code from the re2c project; please see
// the file README.stapregex for details.

#ifndef STAPREGEX_DFA_H
#define STAPREGEX_DFA_H

#include <string>
#include <iostream>
#include <set>
#include <list>
#include <vector>
#include <queue>
#include <utility>

class translator_output; /* from translator-output.h */

namespace stapregex {

struct regexp; /* from stapregex-tree.h */
union ins; /* from stapregex-tree.h */

struct dfa;
struct state;

/* Coordinates of a subexpression map item m[t,s]: */
typedef std::pair<unsigned, unsigned> map_item;

/* A tagged DFA transition can have a number of these instructions
   attached, which are able to assign the current position to specific
   map items, or to reorder the existing elements of the map: */
struct tdfa_insn {
  map_item to, from;
  bool save_pos; // -- if true, assign position; if false, copy from's value
};
typedef std::list<tdfa_insn> tdfa_action;

std::ostream& operator << (std::ostream &o, const tdfa_action& a);

/* The arc_priority data type is a cunning way to represent transition
   priorities, necessitated by the fact that we have FORK opcodes (two
   outgoing e-transitions) which can lead to further FORK opcodes, &c,
   requiring a binary-subdivision style of priority assignment:

                -> 3/4 ... and so forth
               /
        -> 1/2 --> 2/4 ... and so forth
       /
      /       ---> 1/4 ... and so forth
     /       /
   0 ----> 0 ----> 0   ... and so forth

   Our trick is pretty much just to allocate the possible values of an
   unsigned long in binary-search fashion.

   XXX: For a 64-bit unsigned long type, this allows a chain of FORK
   opcodes around 64 units long (without intervening CHAR match
   insns), at which point things start to get funky. Be sure to keep
   an eye on whether this turns out to be enough in practice. */
typedef std::pair<unsigned long, unsigned> arc_priority;
arc_priority refine_higher(const arc_priority& a);
arc_priority refine_lower(const arc_priority& a);
int arc_compare(const arc_priority& a, const arc_priority& b);

std::ostream& operator << (std::ostream &o, const arc_priority& p);

/* When constructing tagged DFA sets from ins, we need to keep track
   of a set of instructions together with further bookkeeping
   information (relative preference/priority, map items affected). */
struct kernel_point {
  ins *i;
  arc_priority priority; // -- used in tagged e-closure computation
  std::list<map_item> map_items;
  std::set<ins *> parents; // -- used for infinite-loop-detection
};
typedef std::list<kernel_point> state_kernel;

/* Corresponds to a tagged-DFA transition arc, complete with
   subexpression map reordering and such. */
struct span {
  char lb, ub; // -- segment [lb, ub]
  state *to;
  tdfa_action action;
  state_kernel *reach_pairs; // -- for the subset-construction
                             // -- algorithm

  void emit_jump (translator_output *o, const dfa *d) const;
  void emit_final (translator_output *o, const dfa *d) const;
};

struct state {
  unsigned label; // -- index of state in dfa
  state *next;    // -- store dfa states as a linked list
  state_kernel *kernel; // -- set of corresponding ins coordinates
  /* NB: our usage of the term 'kernel' differs from re2c's slightly
     -- there is no real need to distinguish NFA edges inside the
     state from outgoing edges, (XXX) as far as I am aware. */

  bool accepts;   // -- is this a final state?
  unsigned accept_outcome;
  tdfa_action finalizer; // -- run after accepting

  std::list<span> spans;

  state (state_kernel *kernel);

  void emit (translator_output *o, const dfa *d) const;

  void print (translator_output *o) const;
};

// ------------------------------------------------------------------------

struct dfa {
  ins *orig_nfa;
  state *first, *last; // -- store dfa states as a linked list
  unsigned nstates;

  // Infrastructure to deal with tagging:
  unsigned ntags;
  tdfa_action initializer; // -- run before entering start state
  std::vector<std::string> outcome_snippets;

  dfa (ins *i, int ntags, std::vector<std::string>& outcome_snippets);
  ~dfa ();

  void emit (translator_output *o) const;
  void emit_tagsave (translator_output *o, std::string tag_states,
                     std::string tag_vals, std::string tag_count) const;

  void print (translator_output *o) const;
  void print (std::ostream& o) const;

private:
  state *add_state (state* s);
  state *find_equivalent (state *s, tdfa_action &r);
};

std::ostream& operator << (std::ostream &o, const dfa& d);
std::ostream& operator << (std::ostream &o, const dfa* d);

/* Produces a dfa that runs the specified code snippets based on match
   or fail outcomes for an unanchored (by default) match of re. */
dfa *stapregex_compile (regexp *re, const std::string& match_snippet, const std::string& fail_snippet);

};

#endif

/* vim: set sw=2 ts=8 cino=>4,n-2,{2,^-2,t0,(0,u0,w1,M1 : */