src
fillpoints.cc
Go to the documentation of this file.
1 #include <limits>
2 #include <stack>
3 #include <vector>
4 
5 #include "src/ir/dfa/dfa.h"
6 
7 namespace re2c
8 {
9 
10 static const size_t INFINITY = std::numeric_limits<size_t>::max();
11 static const size_t UNDEFINED = INFINITY - 1;
12 
13 static bool loopback(size_t node, size_t narcs, const size_t *arcs)
14 {
15  for (size_t i = 0; i < narcs; ++i)
16  {
17  if (arcs[i] == node)
18  {
19  return true;
20  }
21  }
22  return false;
23 }
24 
25 /*
26  * node [finding strongly connected components of DFA]
27  *
28  * A slight modification of Tarjan's algorithm.
29  *
30  * The algorithm walks graph in deep-first order. It maintains a stack
31  * of nodes that have already been visited but haven't been assigned to
32  * SCC yet. For each node the algorithm calculates 'lowlink': index of
33  * the highest ancestor node reachable in one step from a descendant of
34  * the node. Lowlink is used to determine when a set of nodes should be
35  * popped off the stack into a new SCC.
36  *
37  * We use lowlink to hold different kinds of information:
38  * - values in range [0 .. stack size] mean that this node is on stack
39  * (link to a node with the smallest index reachable from this one)
40  * - UNDEFINED means that this node has not been visited yet
41  * - INFINITY means that this node has already been popped off stack
42  *
43  * We use stack size (rather than topological sort index) as unique index
44  * of a node on stack. This is safe because indices of nodes on stack are
45  * still unique and less than indices of nodes that have been popped off
46  * stack (INFINITY).
47  *
48  */
49 static void scc(
50  const dfa_t &dfa,
51  std::stack<size_t> &stack,
52  std::vector<size_t> &lowlink,
53  std::vector<bool> &trivial,
54  size_t i)
55 {
56  const size_t link = stack.size();
57  lowlink[i] = link;
58  stack.push(i);
59 
60  const size_t *arcs = dfa.states[i]->arcs;
61  for (size_t c = 0; c < dfa.nchars; ++c)
62  {
63  const size_t j = arcs[c];
64  if (j != dfa_t::NIL)
65  {
66  if (lowlink[j] == UNDEFINED)
67  {
68  scc(dfa, stack, lowlink, trivial, j);
69  }
70  if (lowlink[j] < lowlink[i])
71  {
72  lowlink[i] = lowlink[j];
73  }
74  }
75  }
76 
77  if (lowlink[i] == link)
78  {
79  // SCC is non-trivial (has loops) iff it either:
80  // - consists of multiple nodes (they all must be interconnected)
81  // - consists of single node which loops back to itself
82  trivial[i] = i == stack.top()
83  && !loopback(i, dfa.nchars, arcs);
84 
85  size_t j;
86  do
87  {
88  j = stack.top();
89  stack.pop();
90  lowlink[j] = INFINITY;
91  }
92  while (j != i);
93  }
94 }
95 
96 static void calc_fill(
97  const dfa_t &dfa,
98  const std::vector<bool> &trivial,
99  std::vector<size_t> &fill,
100  size_t i)
101 {
102  if (fill[i] == UNDEFINED)
103  {
104  fill[i] = 0;
105  const size_t *arcs = dfa.states[i]->arcs;
106  for (size_t c = 0; c < dfa.nchars; ++c)
107  {
108  const size_t j = arcs[c];
109  if (j != dfa_t::NIL)
110  {
111  calc_fill(dfa, trivial, fill, j);
112  size_t max = 1;
113  if (trivial[j])
114  {
115  max += fill[j];
116  }
117  if (max > fill[i])
118  {
119  fill[i] = max;
120  }
121  }
122  }
123  }
124 }
125 
126 void fillpoints(const dfa_t &dfa, std::vector<size_t> &fill)
127 {
128  const size_t size = dfa.states.size();
129 
130  // find DFA states that belong to non-trivial SCC
131  std::stack<size_t> stack;
132  std::vector<size_t> lowlink(size, UNDEFINED);
133  std::vector<bool> trivial(size, false);
134  scc(dfa, stack, lowlink, trivial, 0);
135 
136  // for each DFA state, calculate YYFILL argument:
137  // maximal path length to the next YYFILL state
138  fill.resize(size, UNDEFINED);
139  calc_fill(dfa, trivial, fill, 0);
140 
141  // The following states must trigger YYFILL:
142  // - inital state
143  // - all states in non-trivial SCCs
144  // for other states, reset YYFILL argument to zero
145  for (size_t i = 1; i < size; ++i)
146  {
147  if (trivial[i])
148  {
149  fill[i] = 0;
150  }
151  }
152 }
153 
154 } // namespace re2c
static void scc(const dfa_t &dfa, std::stack< size_t > &stack, std::vector< size_t > &lowlink, std::vector< bool > &trivial, size_t i)
Definition: fillpoints.cc:49
std::vector< dfa_state_t * > states
Definition: dfa.h:40
static void calc_fill(const dfa_t &dfa, const std::vector< bool > &trivial, std::vector< size_t > &fill, size_t i)
Definition: fillpoints.cc:96
void fillpoints(const dfa_t &dfa, std::vector< size_t > &fill)
Definition: fillpoints.cc:126
static const size_t UNDEFINED
Definition: fillpoints.cc:11
static const size_t INFINITY
Definition: fillpoints.cc:10
const size_t nchars
Definition: dfa.h:41
static const size_t NIL
Definition: dfa.h:38
static bool loopback(size_t node, size_t narcs, const size_t *arcs)
Definition: fillpoints.cc:13
Definition: bitmap.cc:10