File indexing completed on 2024-05-05 10:03:09
0001 /* 0002 This file is part of KCachegrind. 0003 0004 SPDX-FileCopyrightText: 2003-2016 Josef Weidendorfer <Josef.Weidendorfer@gmx.de> 0005 0006 SPDX-License-Identifier: GPL-2.0-only 0007 */ 0008 0009 #include "stackbrowser.h" 0010 0011 0012 // Stack 0013 0014 Stack::Stack(TraceFunction* top, TraceCallList calls) 0015 { 0016 _refCount = 0; 0017 _top = top; 0018 _calls = calls; 0019 0020 extendBottom(); 0021 } 0022 0023 Stack::Stack(TraceFunction* f) 0024 { 0025 _refCount = 0; 0026 _top = f; 0027 0028 extendBottom(); 0029 extendTop(); 0030 } 0031 0032 void Stack::extendBottom() 0033 { 0034 SubCost most; 0035 TraceFunction* f; 0036 0037 if (!_calls.isEmpty()) 0038 f = _calls.last()->called(); 0039 else 0040 f = _top; 0041 0042 if (!f) return; 0043 // do not follow calls from cycles 0044 if (f->cycle() == f) return; 0045 0046 // event type to use for the "most probable" call stack 0047 // we simply take the first real event type 0048 if ((_top->data() == nullptr) || 0049 (_top->data()->eventTypes()->realCount() <1)) return; 0050 EventType* e = _top->data()->eventTypes()->realType(0); 0051 0052 int max = 30; 0053 0054 // try to extend to lower stack frames 0055 while (f && (max-- >0)) { 0056 TraceCall* call = nullptr; 0057 most = 0; 0058 foreach(TraceCall* c, f->callings()) { 0059 // no cycle calls in stack: could be deleted without notice 0060 if (c->called()->cycle() == c->called()) continue; 0061 // no simple recursions 0062 if (c->called() == _top) continue; 0063 0064 if (c->called()->name().isEmpty()) continue; 0065 SubCost sc = c->subCost(e); 0066 if (sc == 0) continue; 0067 0068 if (sc > most) { 0069 most = sc; 0070 call = c; 0071 } 0072 } 0073 if (!call) 0074 break; 0075 0076 _calls.append(call); 0077 f = call->called(); 0078 } 0079 } 0080 0081 0082 void Stack::extendTop() 0083 { 0084 SubCost most; 0085 0086 int max = 10; 0087 0088 // do not follow calls from cycles 0089 if (_top->cycle() == _top) return; 0090 0091 // event type to use for the "most probable" call stack 0092 // we simply take the first real event type 0093 if ((_top->data() == nullptr) || 0094 (_top->data()->eventTypes()->realCount() <1)) return; 0095 EventType* e = _top->data()->eventTypes()->realType(0); 0096 0097 // try to extend to upper stack frames 0098 while (_top && (max-- >0)) { 0099 TraceCall* call = nullptr; 0100 most = 0; 0101 foreach(TraceCall* c, _top->callers()) { 0102 // no cycle calls in stack: could be deleted without notice 0103 if (c->caller()->cycle() == c->caller()) continue; 0104 // no simple recursions 0105 if (c->caller() == _top) continue; 0106 0107 if (c->caller()->name().isEmpty()) continue; 0108 SubCost sc = c->subCost(e); 0109 if (sc == 0) continue; 0110 0111 if (sc > most) { 0112 most = sc; 0113 call = c; 0114 } 0115 } 0116 if (!call) 0117 break; 0118 0119 _calls.prepend(call); 0120 _top = call->caller(); 0121 } 0122 } 0123 0124 TraceFunction* Stack::caller(TraceFunction* fn, bool extend) 0125 { 0126 TraceFunction* f; 0127 0128 if (extend && (_top == fn)) { 0129 // extend at top 0130 extendTop(); 0131 f = _top; 0132 } 0133 0134 foreach(TraceCall* c, _calls) { 0135 f = c->called(); 0136 if (f == fn) 0137 return c->caller(); 0138 } 0139 return nullptr; 0140 } 0141 0142 TraceFunction* Stack::called(TraceFunction* fn, bool extend) 0143 { 0144 TraceFunction* f; 0145 0146 foreach(TraceCall* c, _calls) { 0147 f = c->caller(); 0148 if (f == fn) 0149 return c->called(); 0150 } 0151 0152 if (extend) { 0153 // extend at bottom 0154 extendBottom(); 0155 0156 // and search again 0157 foreach(TraceCall* c, _calls) { 0158 f = c->caller(); 0159 if (f == fn) 0160 return c->called(); 0161 } 0162 } 0163 0164 return nullptr; 0165 } 0166 0167 bool Stack::contains(TraceFunction* fn) 0168 { 0169 // cycles are listed on there own 0170 if (fn->cycle() == fn) return false; 0171 if (_top->cycle() == _top) return false; 0172 0173 if (fn == _top) 0174 return true; 0175 0176 TraceFunction* f = _top; 0177 0178 foreach(TraceCall* c, _calls) { 0179 f = c->called(); 0180 if (f == fn) 0181 return true; 0182 } 0183 0184 // try to extend at bottom (even if callCount 0) 0185 foreach(TraceCall* c, f->callings()) { 0186 f = c->called(); 0187 if (f == fn) { 0188 _calls.append(c); 0189 0190 // extend at bottom after found one 0191 extendBottom(); 0192 return true; 0193 } 0194 } 0195 0196 // try to extend at top (even if callCount 0) 0197 foreach(TraceCall* c, _top->callers()) { 0198 f = c->caller(); 0199 if (f == fn) { 0200 _calls.prepend(c); 0201 0202 // extend at top after found one 0203 extendTop(); 0204 return true; 0205 } 0206 } 0207 0208 return false; 0209 } 0210 0211 Stack* Stack::split(TraceFunction* f) 0212 { 0213 TraceCallList calls = _calls; 0214 0215 // cycles are listed on there own 0216 if (f->cycle() == f) return nullptr; 0217 if (_top->cycle() == _top) return nullptr; 0218 0219 foreach(TraceCall* c, calls) { 0220 foreach(TraceCall* c2, c->called()->callings()) { 0221 if (c2 == c) continue; 0222 if (c2->called() != f) continue; 0223 0224 // remove bottom part 0225 while (!calls.isEmpty() && (calls.last()!=c)) 0226 calls.removeLast(); 0227 0228 calls.append(c2); 0229 return new Stack(_top, calls); 0230 } 0231 } 0232 return nullptr; 0233 } 0234 0235 QString Stack::toString() 0236 { 0237 QString res = _top->name(); 0238 foreach(TraceCall *c, _calls) 0239 res += "\n > " + c->called()->name(); 0240 0241 return res; 0242 } 0243 0244 0245 // HistoryItem 0246 0247 HistoryItem::HistoryItem(Stack* stack, TraceFunction* function) 0248 { 0249 _stack = stack; 0250 _function = function; 0251 if (_stack) 0252 _stack->ref(); 0253 0254 _last = nullptr; 0255 _next = nullptr; 0256 0257 /* 0258 qDebug("New Stack History Item (sRef %d): %s\n %s", 0259 _stack->refCount(), qPrintable(_function->name()), 0260 qPrintable(_stack->toString())); 0261 */ 0262 } 0263 0264 HistoryItem::~HistoryItem() 0265 { 0266 if (0) qDebug("Deleting Stack History Item (sRef %d): %s", 0267 _stack->refCount(), 0268 qPrintable(_function->name())); 0269 0270 if (_last) 0271 _last->_next = _next; 0272 if (_stack) { 0273 if (_stack->deref() == 0) 0274 delete _stack; 0275 } 0276 } 0277 0278 0279 // StackBrowser 0280 0281 StackBrowser::StackBrowser() 0282 { 0283 _current = nullptr; 0284 } 0285 0286 StackBrowser::~StackBrowser() 0287 { 0288 delete _current; 0289 } 0290 0291 HistoryItem* StackBrowser::select(TraceFunction* f) 0292 { 0293 if (!_current) { 0294 Stack* s = new Stack(f); 0295 _current = new HistoryItem(s, f); 0296 } 0297 else if (_current->function() != f) { 0298 // make current item the last one 0299 HistoryItem* item = _current; 0300 if (item->next()) { 0301 item = item->next(); 0302 item->last()->setNext(nullptr); 0303 0304 while (item->next()) { 0305 item = item->next(); 0306 delete item->last(); 0307 } 0308 delete item; 0309 } 0310 0311 Stack* s = _current->stack(); 0312 if (!s->contains(f)) { 0313 s = s->split(f); 0314 if (!s) 0315 s = new Stack(f); 0316 } 0317 0318 item = _current; 0319 _current = new HistoryItem(s, f); 0320 item->setNext(_current); 0321 _current->setLast(item); 0322 } 0323 0324 // qDebug("Selected %s in StackBrowser", qPrintable(f->name())); 0325 0326 return _current; 0327 } 0328 0329 HistoryItem* StackBrowser::goBack() 0330 { 0331 if (_current && _current->last()) 0332 _current = _current->last(); 0333 0334 return _current; 0335 } 0336 0337 HistoryItem* StackBrowser::goForward() 0338 { 0339 if (_current && _current->next()) 0340 _current = _current->next(); 0341 0342 return _current; 0343 } 0344 0345 HistoryItem* StackBrowser::goUp() 0346 { 0347 if (_current) { 0348 TraceFunction* f = _current->stack()->caller(_current->function(), true); 0349 if (f) 0350 _current = select(f); 0351 } 0352 0353 return _current; 0354 } 0355 0356 HistoryItem* StackBrowser::goDown() 0357 { 0358 if (_current) { 0359 TraceFunction* f = _current->stack()->called(_current->function(), true); 0360 if (f) 0361 _current = select(f); 0362 } 0363 0364 return _current; 0365 } 0366 0367 bool StackBrowser::canGoBack() 0368 { 0369 return _current && _current->last(); 0370 } 0371 0372 bool StackBrowser::canGoForward() 0373 { 0374 return _current && _current->next(); 0375 } 0376 0377 bool StackBrowser::canGoUp() 0378 { 0379 if (!_current) return false; 0380 0381 return _current->stack()->caller(_current->function(), false); 0382 } 0383 0384 bool StackBrowser::canGoDown() 0385 { 0386 if (!_current) return false; 0387 0388 return _current->stack()->called(_current->function(), false); 0389 }