1 /* 2 * (C) Copyright 2004-2015 Diomidis Spinellis 3 * 4 * This file is part of CScout. 5 * 6 * CScout is free software: you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation, either version 3 of the License, or 9 * (at your option) any later version. 10 * 11 * CScout is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with CScout. If not, see <http://www.gnu.org/licenses/>. 18 * 19 * 20 * Function call graph information 21 * 22 */ 23 24 #ifndef CALL_ 25 #define CALL_ 26 27 #include "funmetrics.h" 28 #include "tokid.h" 29 #include "fchar.h" 30 #include "token.h" 31 32 class FCall; 33 class Sql; 34 class Id; 35 class Ctoken; 36 37 /* 38 * Generic call information of a called/calling entity. 39 * The calls can be to/from macros or functions. 40 * We identify four types of calls: 41 * 1. Macro calls macro 42 * Function like macro-expansion while expanding a macro 43 * 2. Macro calls function 44 * parse.y type.cpp call register_call(id->get_fcall()) 45 * Function call with the identifier token being part of a 46 * (function-like) macro body 47 * 3. Function calls function 48 * parse.y type.cpp call register_call(id->get_fcall()) 49 * Function call with the identifier token not part of a 50 * (function-like) macro body 51 * 4. Function calls macro 52 * Function-like macro expanded while processing a function body 53 * This scheme does not handle: 54 * macros that expand to functions 55 * functions containing function names that are object-like macros 56 * macro names consisting of multiple parts 57 */ 58 class Call { 59 private: 60 61 // Container for storing all declared functions 62 typedef set <Call *> fun_container; 63 /* 64 * When processing the program a Call * is stored with each Id 65 * This allows accurate lookup of calls within a linkage unit. 66 * However, once a linkage unit goes out of scope, we need further 67 * help to reunite functions from varying projects and also locate 68 * function declarations when processing the source code. A function 69 * can be identified well enough by using the Tokid of its declaration. 70 * However, the same Tokid can through token pasting be used for 71 * declaring multiple functions. Therefore we use a multimap, and 72 * as a second step when we lookup a function we compare the 73 * corresponding tokens. 74 */ 75 typedef multimap <Tokid, Call *> fun_map; 76 77 string name; // Function's name 78 fun_container call; // Functions this function calls 79 fun_container caller; // Functions that call this function 80 unsigned char visited; // For calculating transitive closures (bit mask or boolean) 81 bool printed; // For printing a graph's nodes 82 FcharContext begin, end; // Span of definition 83 FunMetrics m; // Metrics for this function 84 int curr_stmt_nesting; // Current level of nesting 85 static int macro_nesting; // Level of nesting through macro tokens 86 add_call(Call * f)87 void add_call(Call *f) { call.insert(f); } add_caller(Call * f)88 void add_caller(Call *f) { caller.insert(f); } 89 90 protected: 91 static fun_map all; // Set of all functions 92 static Call *current_fun; // Function currently being parsed 93 static stack<Call *> nesting; // Nested function definitions 94 95 /* 96 * A token (almost) uniquely identifying the call entity. 97 * (See fun_map comment for more details on the "almost".) 98 * Examples: 99 * Function's first declaration 100 * (could also be reference if implicitly declared) 101 * Macro's definition 102 */ 103 Token token; 104 105 public: 106 // Called when outside a function / macro body scope 107 static void unset_current_fun(); 108 // The current function makes a call to id 109 static void register_call(const Id *id); 110 // The current function makes a call to f 111 static void register_call(Call *f); 112 // The current function (token t) makes a call to f 113 static void register_call(const Token &t, const Id *id); 114 // The current function (tokid t) makes a call to f 115 static void register_call(Tokid t, Call *f); 116 117 // A call from from to to 118 static void register_call(Call *from, Call *to); 119 120 // Clear the visit flags for all functions 121 static void clear_visit_flags(); 122 static void clear_print_flags(); 123 124 // Interface for iterating through all functions 125 typedef fun_map::const_iterator const_fmap_iterator_type; fbegin()126 static const_fmap_iterator_type fbegin() { return all.begin(); } fend()127 static const_fmap_iterator_type fend() { return all.end(); } fsize()128 static int fsize() { return all.size(); } functions()129 static const fun_map &functions() { return all; } 130 131 // Get a call site for a given Token 132 static Call *get_call(const Token &t); 133 // Get a call sites for a given Tokid 134 static pair <const_fmap_iterator_type, const_fmap_iterator_type> get_calls(Tokid t); 135 136 // Dump the data in SQL format 137 static void dumpSql(Sql *db, ostream &of); 138 get_name()139 const string &get_name() const { return name; } 140 bool contains(Eclass *e) const; 141 142 // Interface for iterating through calls and callers 143 typedef fun_container::const_iterator const_fiterator_type; call_begin()144 const_fiterator_type call_begin() const { return call.begin(); } call_end()145 const_fiterator_type call_end() const { return call.end(); } caller_begin()146 const_fiterator_type caller_begin() const { return caller.begin(); } caller_end()147 const_fiterator_type caller_end() const { return caller.end(); } 148 get_num_call()149 int get_num_call() const { return call.size(); } get_num_caller()150 int get_num_caller() const { return caller.size(); } 151 set_visited()152 void set_visited() { visited = true; } 153 // Bit-or the specified visit flag set_visited(unsigned char v)154 void set_visited(unsigned char v) { visited |= v; } is_visited()155 bool is_visited() const { return (bool)visited; } is_visited(unsigned short visit_id)156 bool is_visited(unsigned short visit_id) const { return (bool)(visited & visit_id); } get_visited()157 unsigned char get_visited() const { return visited; } set_printed()158 void set_printed() { printed = true; } is_printed()159 bool is_printed() const { return printed; } 160 161 // Mark the function's span 162 void mark_begin(); get_begin()163 FcharContext get_begin() const { return begin; } 164 // Mark the function's span and add it to the corresponding file 165 void mark_end(); get_end()166 FcharContext get_end() const { return end; } 167 // Return true if the span represents a file region 168 bool is_span_valid() const; 169 // Return a reference to the Metrics class metrics()170 FunMetrics &metrics() { return m; } 171 // Return a reference to the Metrics class const_metrics()172 const FunMetrics &const_metrics() const { return m; } 173 174 // Return a token for the given object get_token()175 const Token &get_token() const {return token; } 176 // Return a tokid for the given object get_tokid()177 Tokid get_tokid() const {return token.get_parts_begin()->get_tokid(); } 178 // Return the function's file-id get_fileid()179 Fileid get_fileid() const {return token.get_parts_begin()->get_tokid().get_fileid(); } 180 181 // Return true if the function is defined 182 virtual bool is_defined() const = 0; 183 // Return true if the function is declared 184 virtual bool is_declared() const = 0; 185 // Return the name of the entity's type 186 virtual const string & entity_type_name() const = 0; 187 // Return true if the function is static (e.g. a macro or a static C function) 188 virtual bool is_file_scoped() const = 0; 189 virtual bool is_cfun() const = 0; 190 virtual bool is_macro() const = 0; 191 192 virtual Tokid get_definition() const = 0; 193 // Return an entry's identifying site get_site()194 Tokid get_site() const { 195 if (is_defined()) 196 return get_definition(); 197 else 198 return get_tokid(); 199 } 200 201 // Set number of arguments set_num_args(int n)202 static inline void set_num_args(int n) { 203 if (current_fun && !current_fun->m.is_processed()) 204 current_fun->m.set_metric(FunMetrics::em_nparam, n); 205 } 206 207 // Process a token destined for preprocessing process_token(const Pltoken & t)208 static inline void process_token(const Pltoken &t) { 209 if (current_fun && !current_fun->m.is_processed()) 210 current_fun->m.process_token(t); 211 } 212 213 // Call the specified metrics function for the current function call_metrics(void (Metrics::* fun)())214 static inline void call_metrics(void (Metrics::*fun)()) { 215 if (current_fun) 216 (current_fun->m.*fun)(); 217 } 218 219 // The following three methods must always be called as a group 220 // See if we have started nesting through macro-expanded tokens 221 static void check_macro_nesting(const Ctoken &t); 222 223 // Increase the current function's level of nesting increase_nesting()224 static inline void increase_nesting() { 225 if (current_fun && !current_fun->m.is_processed() && 226 !macro_nesting) 227 current_fun->m.update_nesting(++(current_fun->curr_stmt_nesting)); 228 } 229 230 // Decrease the current function's level of nesting decrease_nesting()231 static inline void decrease_nesting() { 232 if (!current_fun || current_fun->m.is_processed()) 233 return; 234 if (macro_nesting) 235 macro_nesting--; 236 else 237 current_fun->curr_stmt_nesting--; 238 } 239 240 // ctor; never call it if the call for t already exists 241 Call(const string &s, const Token &t); ~Call()242 virtual ~Call() {} 243 }; 244 245 #endif // CALL_ 246