1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
// Copyright (c) 2014-2017 Dr. Colin Hirsch and Daniel Frey
// Please see LICENSE for license or visit https://github.com/taocpp/PEGTL/
#ifndef TAOCPP_PEGTL_INCLUDE_ANALYSIS_ANALYZE_CYCLES_HPP
#define TAOCPP_PEGTL_INCLUDE_ANALYSIS_ANALYZE_CYCLES_HPP
#include <cassert>
#include <map>
#include <set>
#include <iostream>
#include <utility>
#include "../config.hpp"
#include "grammar_info.hpp"
#include "insert_guard.hpp"
namespace tao
{
namespace TAOCPP_PEGTL_NAMESPACE
{
namespace analysis
{
class analyze_cycles_impl
{
protected:
explicit analyze_cycles_impl( const bool verbose ) noexcept
: m_verbose( verbose ),
m_problems( 0 )
{
}
const bool m_verbose;
unsigned m_problems;
grammar_info m_info;
std::set< std::string > m_stack;
std::map< std::string, bool > m_cache;
std::map< std::string, bool > m_results;
const std::map< std::string, rule_info >::const_iterator find( const std::string& name ) const noexcept
{
const auto iter = m_info.map.find( name );
assert( iter != m_info.map.end() );
return iter;
}
bool work( const std::map< std::string, rule_info >::const_iterator& start, const bool accum )
{
const auto j = m_cache.find( start->first );
if( j != m_cache.end() ) {
return j->second;
}
if( const auto g = make_insert_guard( m_stack, start->first ) ) {
switch( start->second.type ) {
case rule_type::ANY: {
bool a = false;
for( const auto& r : start->second.rules ) {
a = a || work( find( r ), accum || a );
}
return m_cache[ start->first ] = true;
}
case rule_type::OPT: {
bool a = false;
for( const auto& r : start->second.rules ) {
a = a || work( find( r ), accum || a );
}
return m_cache[ start->first ] = false;
}
case rule_type::SEQ: {
bool a = false;
for( const auto& r : start->second.rules ) {
a = a || work( find( r ), accum || a );
}
return m_cache[ start->first ] = a;
}
case rule_type::SOR: {
bool a = true;
for( const auto& r : start->second.rules ) {
a = a && work( find( r ), accum );
}
return m_cache[ start->first ] = a;
}
}
throw std::runtime_error( "code should be unreachable" ); // LCOV_EXCL_LINE
}
if( !accum ) {
++m_problems;
if( m_verbose ) {
std::cout << "problem: cycle without progress detected at rule class " << start->first << std::endl;
}
}
return m_cache[ start->first ] = accum;
}
};
template< typename Grammar >
class analyze_cycles
: private analyze_cycles_impl
{
public:
explicit analyze_cycles( const bool verbose )
: analyze_cycles_impl( verbose )
{
Grammar::analyze_t::template insert< Grammar >( m_info );
}
std::size_t problems()
{
for( auto i = m_info.map.begin(); i != m_info.map.end(); ++i ) {
m_results[ i->first ] = work( i, false );
m_cache.clear();
}
return m_problems;
}
template< typename Rule >
bool consumes() const noexcept
{
const auto i = m_results.find( internal::demangle< Rule >() );
assert( i != m_results.end() );
return i->second;
}
};
} // namespace analysis
} // namespace TAOCPP_PEGTL_NAMESPACE
} // namespace tao
#endif
|
