1 /* $Id: traversal_pattern_match_callback.cpp 512472 2016-08-31 12:38:54Z ivanov $
2 * ===========================================================================
3 *
4 * PUBLIC DOMAIN NOTICE
5 * National Center for Biotechnology Information
6 *
7 * This software/database is a "United States Government Work" under the
8 * terms of the United States Copyright Act. It was written as part of
9 * the author's official duties as a United States Government employee and
10 * thus cannot be copyrighted. This software/database is freely available
11 * to the public for use. The National Library of Medicine and the U.S.
12 * Government have not placed any restriction on its use or reproduction.
13 *
14 * Although all reasonable efforts have been taken to ensure the accuracy
15 * and reliability of the software and data, the NLM and the U.S.
16 * Government do not and cannot warrant the perfors54mance or results that
17 * may be obtained by using this software or data. The NLM and the U.S.
18 * Government disclaim all warranties, express or implied, including
19 * warranties of performance, merchantability or fitness for any particular
20 * purpose.
21 *
22 * Please cite the author in any work or product based on this material.
23 *
24 * ===========================================================================
25 *
26 * Author: Michael Kornbluh
27 *
28 * File Description:
29 * Used to attach user functions to be called by the traversal.
30 */
31
32 #include <ncbi_pch.hpp>
33
34 #include "traversal_pattern_match_callback.hpp"
35
36 #include <serial/error_codes.hpp>
37
38 #define NCBI_USE_ERRCODE_X Serial_DataTool
39
40 BEGIN_NCBI_SCOPE
41
42 // CTraversalPatternMatchCallback::TPatternVec CTraversalPatternMatchCallback::kEmptyPatternVec;
43
CTraversalPatternMatchCallback(CTraversalSpecFileParser & spec_file_parser,CTraversalNode::TNodeSet & nodesWithFunctions)44 CTraversalPatternMatchCallback::CTraversalPatternMatchCallback(
45 CTraversalSpecFileParser &spec_file_parser,
46 CTraversalNode::TNodeSet &nodesWithFunctions )
47 : m_NodesWithFunctions(nodesWithFunctions)
48 {
49 // go through every node ever created and put it into bins based on the typename and varname and class-name
50 ITERATE( CTraversalNode::TNodeRawSet, node_iter, CTraversalNode::GetEveryNode() ) {
51
52 // we can't match references
53 if( x_NodeIsUnmatchable(**node_iter) ) {
54 continue;
55 }
56
57 CRef<CTraversalNode> node_ref = (*node_iter)->Ref();
58 m_LeafToPossibleNodes[(*node_iter)->GetTypeName()].push_back( node_ref );
59 m_LeafToPossibleNodes[(*node_iter)->GetInputClassName()].push_back( node_ref );
60
61 m_LeafToPossibleNodes[ x_GetNodeVarName(**node_iter) ].push_back( node_ref );
62 }
63
64 // now, go through every pattern and try to match it to nodes
65 ITERATE( std::vector<CTraversalSpecFileParser::CDescFileNodeRef>, pattern_iter, spec_file_parser.GetDescFileNodes() ) {
66 x_TryToAttachPattern( *pattern_iter );
67 }
68
69 // destroy nodes that match the "deprecated" pattern
70 CTraversalNode::TNodeSet nodes_to_destroy;
71 ITERATE( CTraversalSpecFileParser::TPatternVec, deprec_pattern_iter, spec_file_parser.GetDeprecatedPatterns() )
72 {
73 x_TryToDeprecatePatternMatchers( *deprec_pattern_iter, nodes_to_destroy );
74 }
75
76 // destroy the nodes we should
77 NON_CONST_ITERATE( CTraversalNode::TNodeSet, node_iter, nodes_to_destroy ) {
78 CRef<CTraversalNode> node = *node_iter;
79 node->Clear();
80 }
81 }
82
x_TryToAttachPattern(CTraversalSpecFileParser::CDescFileNodeRef pattern)83 void CTraversalPatternMatchCallback::x_TryToAttachPattern( CTraversalSpecFileParser::CDescFileNodeRef pattern )
84 {
85 const string &last_node_in_pattern = pattern->GetPattern().back();
86 bool pattern_was_used = false;
87 bool except_pattern_was_used = false;
88
89 // if there's no except_pattern, it's always considered used
90 if( pattern->GetExceptPatterns().empty() ) {
91 except_pattern_was_used = true;
92 }
93
94 NON_CONST_ITERATE( CTraversalNode::TNodeVec, node_iter, m_LeafToPossibleNodes[last_node_in_pattern] ) {
95 if( x_PatternMatches( (*node_iter), pattern->GetPattern().rbegin(), pattern->GetPattern().rend() ) ) {
96 // if pattern matches, make sure none of the EXCEPT patterns match.
97 if( x_AnyPatternMatches( *node_iter, pattern->GetExceptPatterns() ) ) {
98 except_pattern_was_used = true;
99 } else {
100 // Actually attach the node (This could still fail and throw exception for certain cases,
101 // but such failure is considered fatal)
102 pattern_was_used = true;
103 x_DoAttachment( *node_iter,pattern );
104 }
105 }
106 }
107
108 // warn the user on unused patterns or unused exceptions, since there's
109 // a high chance the user made a typo
110 if( ! pattern_was_used ) {
111 ERR_POST_X(2, Warning << "Pattern was unused: " << pattern->ToString() );
112 } else if( ! except_pattern_was_used ) {
113 ERR_POST_X(2, Warning << "Pattern exception was unused: " << pattern->ToString() );
114 }
115 }
116
x_TryToDeprecatePatternMatchers(const CTraversalSpecFileParser::TPattern & deprec_pattern,CTraversalNode::TNodeSet & nodes_to_destroy)117 void CTraversalPatternMatchCallback::x_TryToDeprecatePatternMatchers(
118 const CTraversalSpecFileParser::TPattern & deprec_pattern,
119 CTraversalNode::TNodeSet & nodes_to_destroy )
120 {
121 const string &last_node_in_pattern = deprec_pattern.back();
122 bool pattern_was_used = false;
123
124 NON_CONST_ITERATE( CTraversalNode::TNodeVec, node_iter, m_LeafToPossibleNodes[last_node_in_pattern] ) {
125 if( x_PatternMatches( (*node_iter), deprec_pattern.rbegin(), deprec_pattern.rend() ) ) {
126 pattern_was_used = true;
127 nodes_to_destroy.insert( *node_iter );
128 }
129 }
130
131 // warn the user on unused patterns, since there's
132 // a high chance the user made a typo
133 if( ! pattern_was_used ) {
134 ERR_POST_X(2, Warning << "Deprecation pattern was unused: " << NStr::Join( deprec_pattern, "." ) );
135 }
136 }
137
138 bool
x_PatternMatches(CRef<CTraversalNode> node,TPatternIter pattern_start,TPatternIter pattern_end)139 CTraversalPatternMatchCallback::x_PatternMatches(
140 CRef<CTraversalNode> node,
141 TPatternIter pattern_start, TPatternIter pattern_end )
142 {
143 // this func is recursive
144
145 // skip over references
146 if( x_NodeIsUnmatchable(*node) ) {
147 ITERATE( CTraversalNode::TNodeCallSet, caller_iter, node->GetCallers() ) {
148 if( x_PatternMatches( (*caller_iter)->GetNode(), pattern_start, pattern_end ) ) { // notice *no* " + 1"
149 return true;
150 }
151 }
152 return false;
153 }
154
155 // shouldn't happen
156 _ASSERT( pattern_start != pattern_end );
157
158 // where we are in the pattern
159 const std::string ¤t_leaf = *pattern_start;
160
161 // if this node matches by certain criteria, we check all callers
162 if( current_leaf == "?" || // "?" matches anything
163 current_leaf == node->GetTypeName() ||
164 current_leaf == node->GetInputClassName() ||
165 current_leaf == x_GetNodeVarName(*node) )
166 {
167 // Everything matched
168 if( (pattern_start + 1) == pattern_end ) {
169 return true;
170 }
171
172 // more pattern so check all callers
173 ITERATE( CTraversalNode::TNodeCallSet, caller_iter, node->GetCallers() ) {
174 if( x_PatternMatches( (*caller_iter)->GetNode(), pattern_start + 1, pattern_end ) ) { // notice the " + 1"
175 return true;
176 }
177 }
178 }
179
180 // couldn't match anything
181 return false;
182 }
183
x_AnyPatternMatches(CRef<CTraversalNode> node,const CTraversalSpecFileParser::TPatternVec & patterns)184 bool CTraversalPatternMatchCallback::x_AnyPatternMatches(
185 CRef<CTraversalNode> node,
186 const CTraversalSpecFileParser::TPatternVec &patterns )
187 {
188 // straightforward: just try to match any pattern
189 ITERATE( CTraversalSpecFileParser::TPatternVec, pattern_iter, patterns ) {
190 if( x_PatternMatches( node, pattern_iter->rbegin(), pattern_iter->rend() ) ) {
191 return true;
192 }
193 }
194 return false;
195 }
196
x_DoAttachment(CRef<CTraversalNode> node,CTraversalSpecFileParser::CDescFileNodeRef pattern)197 void CTraversalPatternMatchCallback::x_DoAttachment(
198 CRef<CTraversalNode> node,
199 CTraversalSpecFileParser::CDescFileNodeRef pattern )
200 {
201 // do the attachment that binds the user function to this node
202
203 vector< CRef<CTraversalNode> > extra_arg_nodes;
204
205 // for any extra args the node requires, find the node whose value this corresponds to.
206 ITERATE( CTraversalSpecFileParser::TPatternVec, extra_arg_iter, pattern->GetArgPatterns() ) {
207 CRef<CTraversalNode> arg_node =
208 x_TranslateArgToNode(node, pattern->GetPattern(), *extra_arg_iter);
209 extra_arg_nodes.push_back( arg_node );
210 arg_node->SetDoStoreArg();
211 }
212
213 // create and bind the user call
214 CRef<CTraversalNode::CUserCall> user_call(
215 new CTraversalNode::CUserCall(pattern->GetFunc(), extra_arg_nodes, pattern->GetConstantArgs() ) );
216 if( pattern->GetWhen() == CTraversalSpecFileParser::CDescFileNode::eWhen_afterCallees ) {
217 node->AddPostCalleesUserCall( user_call );
218 } else {
219 node->AddPreCalleesUserCall( user_call );
220 }
221
222 // add the node to the set that have functions
223 m_NodesWithFunctions.insert( node->Ref() );
224 }
225
x_TranslateArgToNode(CRef<CTraversalNode> node,const CTraversalSpecFileParser::TPattern & main_pattern,const CTraversalSpecFileParser::TPattern & extra_arg_pattern)226 CRef<CTraversalNode> CTraversalPatternMatchCallback::x_TranslateArgToNode(
227 CRef<CTraversalNode> node,
228 const CTraversalSpecFileParser::TPattern &main_pattern,
229 const CTraversalSpecFileParser::TPattern &extra_arg_pattern )
230 {
231 // how many levels do we have to climb up to find the extra_arg_pattern?
232 const int levels_to_climb = (int)(main_pattern.size() - extra_arg_pattern.size());
233
234 // climb up
235 int level_up = 0;
236 CRef<CTraversalNode> current_node = node;
237 for( ; level_up < levels_to_climb; ++level_up ) {
238 if( current_node->GetCallers().size() != 1 ) {
239 // I'm not entirely sure this can even happen.
240 string msg("when using extra args, the extra args ");
241 msg += "must come from a 'direct' parent node. ";
242 msg += "That is, there must be only ONE path from the node ";
243 msg += "supplying the extra args to ";
244 msg += "the node that needs the extra arg, with only one ";
245 msg += "caller up to the top. ";
246 msg += "Main pattern: '";
247 msg += NStr::Join(main_pattern, ".");
248 msg += "', extra arg pattern: '";
249 msg += NStr::Join(extra_arg_pattern, ".");
250 msg += "'";
251 throw runtime_error( msg );
252 }
253 current_node = (*(current_node->GetCallers().begin()))->GetNode();
254 // skip unmatchable nodes
255 if( x_NodeIsUnmatchable(*current_node) ) {
256 --level_up;
257 }
258 }
259
260 // make sure the node we reached matches the given pattern, which it should unless we've
261 // made a coding error.
262 _ASSERT( x_PatternMatches( current_node, extra_arg_pattern.rbegin(), extra_arg_pattern.rend() ) );
263
264 return current_node;
265 }
266
x_NodeIsUnmatchable(const CTraversalNode & node)267 bool CTraversalPatternMatchCallback::x_NodeIsUnmatchable( const CTraversalNode& node )
268 {
269 if( (node.GetType() == CTraversalNode::eType_Reference) && ! node.GetCallees().empty() ) {
270 const CTraversalNode& node_child = *(**node.GetCallees().begin()).GetNode();
271 return ( x_UseRefOrChild( node, node_child ) == eRefChoice_ChildOnly );
272 } else if( ! node.GetCallers().empty() ) {
273 const CTraversalNode& node_parent = *(**node.GetCallers().begin()).GetNode();
274 if( node_parent.GetType() == CTraversalNode::eType_Reference ) {
275 return ( x_UseRefOrChild( node_parent, node ) == eRefChoice_RefOnly );
276 }
277 }
278
279 return false;
280 }
281
282 const string &
x_GetNodeVarName(const CTraversalNode & node)283 CTraversalPatternMatchCallback::x_GetNodeVarName( const CTraversalNode &node )
284 {
285 const CTraversalNode::TNodeCallSet &callers = node.GetCallers();
286 if( callers.empty() ) {
287 return kEmptyStr;
288 } else {
289 const string &result = (*callers.begin())->GetVarName();
290 return result;
291 }
292 }
293
294 CTraversalPatternMatchCallback::ERefChoice
x_UseRefOrChild(const CTraversalNode & parent_ref,const CTraversalNode & child)295 CTraversalPatternMatchCallback::x_UseRefOrChild(
296 const CTraversalNode& parent_ref,
297 const CTraversalNode& child )
298 {
299 if( x_GetNodeVarName(parent_ref) != x_GetNodeVarName(child) ) {
300 return eRefChoice_Both;
301 }
302
303 if( ! parent_ref.IsTemplate() && child.IsTemplate() ) {
304 return eRefChoice_RefOnly;
305 }
306
307 // the usual case is to skip references
308 return eRefChoice_ChildOnly;
309 }
310
311 END_NCBI_SCOPE
312
313