callgraphview.cpp 75.4 KB
Newer Older
1
/* This file is part of KCachegrind.
2
   Copyright (C) 2007 Josef Weidendorfer <Josef.Weidendorfer@gmx.de>
3
4
5
6
7
8
9
10
11
12
13
14

   KCachegrind is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public
   License as published by the Free Software Foundation, version 2.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; see the file COPYING.  If not, write to
15
   the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
Dirk Mueller's avatar
Dirk Mueller committed
16
   Boston, MA 02110-1301, USA.
17
18
19
20
21
22
*/

/*
 * Callgraph View
 */

23
24
#include "callgraphview.h"

25
26
27
#include <stdlib.h>
#include <math.h>

28
#include <QApplication>
29
#include <QDebug>
30
#include <QFile>
31
32
#include <QFileDialog>
#include <QTemporaryFile>
33
34
35
36
37
#include <QTextStream>
#include <QMatrix>
#include <QPair>
#include <QPainter>
#include <QStyle>
38
#include <QScrollBar>
Nicolas Goutte's avatar
Nicolas Goutte committed
39
40
41
42
#include <QResizeEvent>
#include <QMouseEvent>
#include <QFocusEvent>
#include <QKeyEvent>
43
#include <QStyleOptionGraphicsItem>
Nicolas Goutte's avatar
Nicolas Goutte committed
44
#include <QContextMenuEvent>
45
#include <QList>
Nicolas Goutte's avatar
Nicolas Goutte committed
46
#include <QPixmap>
47
#include <QDesktopWidget>
48
#include <QProcess>
49
#include <QMenu>
50
51


52
#include "config.h"
53
#include "globalconfig.h"
54
55
56
#include "listutils.h"


Josef Weidendorfer's avatar
Josef Weidendorfer committed
57
#define DEBUG_GRAPH 0
58
59
60

// CallGraphView defaults

61
62
63
64
65
66
#define DEFAULT_FUNCLIMIT     .05
#define DEFAULT_CALLLIMIT     1.
#define DEFAULT_MAXCALLER     2
#define DEFAULT_MAXCALLEE     -1
#define DEFAULT_SHOWSKIPPED   false
#define DEFAULT_EXPANDCYCLES  false
67
#define DEFAULT_CLUSTERGROUPS false
68
69
70
#define DEFAULT_DETAILLEVEL   1
#define DEFAULT_LAYOUT        GraphOptions::TopDown
#define DEFAULT_ZOOMPOS       Auto
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
// LessThen functors as helpers for sorting of graph edges
// for keyboard navigation. Sorting is done according to
// the angle at which a edge spline goes out or in of a function.

// Sort angles of outgoing edges (edge seen as attached to the caller)
class CallerGraphEdgeLessThan
{
public:
	bool operator()(const GraphEdge* ge1, const GraphEdge* ge2) const
	{
		const CanvasEdge* ce1 = ge1->canvasEdge();
		const CanvasEdge* ce2 = ge2->canvasEdge();

		// sort invisible edges (ie. without matching CanvasEdge) in front
		if (!ce1) return true;
		if (!ce2) return false;

		QPolygon p1 = ce1->controlPoints();
		QPolygon p2 = ce2->controlPoints();
		QPoint d1 = p1.point(1) - p1.point(0);
		QPoint d2 = p2.point(1) - p2.point(0);
		double angle1 = atan2(double(d1.y()), double(d1.x()));
		double angle2 = atan2(double(d2.y()), double(d2.x()));

		return (angle1 < angle2);
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
};

// Sort angles of ingoing edges (edge seen as attached to the callee)
class CalleeGraphEdgeLessThan
{
public:
	bool operator()(const GraphEdge* ge1, const GraphEdge* ge2) const
	{
		const CanvasEdge* ce1 = ge1->canvasEdge();
		const CanvasEdge* ce2 = ge2->canvasEdge();

		// sort invisible edges (ie. without matching CanvasEdge) in front
		if (!ce1) return true;
		if (!ce2) return false;

		QPolygon p1 = ce1->controlPoints();
		QPolygon p2 = ce2->controlPoints();
		QPoint d1 = p1.point(p1.count()-2) - p1.point(p1.count()-1);
		QPoint d2 = p2.point(p2.count()-2) - p2.point(p2.count()-1);
		double angle1 = atan2(double(d1.y()), double(d1.x()));
		double angle2 = atan2(double(d2.y()), double(d2.x()));

		// for ingoing edges sort according to descending angles
		return (angle2 < angle1);
123
	}
124
};
125
126
127
128
129
130
131
132
133



//
// GraphNode
//

GraphNode::GraphNode()
{
134
135
136
	_f=0;
	self = incl = 0;
	_cn = 0;
137

138
	_visible = false;
139
	_lastCallerIndex = _lastCalleeIndex = -1;
140

141
	_lastFromCaller = true;
142
143
}

144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
void GraphNode::clearEdges()
{
	callees.clear();
	callers.clear();
}

CallerGraphEdgeLessThan callerGraphEdgeLessThan;
CalleeGraphEdgeLessThan calleeGraphEdgeLessThan;

void GraphNode::sortEdges()
{
	qSort(callers.begin(), callers.end(), callerGraphEdgeLessThan);
	qSort(callees.begin(), callees.end(), calleeGraphEdgeLessThan);
}

void GraphNode::addCallee(GraphEdge* e)
{
	if (e)
		callees.append(e);
}

void GraphNode::addCaller(GraphEdge* e)
{
	if (e)
		callers.append(e);
}

void GraphNode::addUniqueCallee(GraphEdge* e)
{
	if (e && (callees.count(e) == 0))
		callees.append(e);
}

void GraphNode::addUniqueCaller(GraphEdge* e)
{
	if (e && (callers.count(e) == 0))
		callers.append(e);
}

void GraphNode::removeEdge(GraphEdge* e)
{
	callers.removeAll(e);
	callees.removeAll(e);
}

double GraphNode::calleeCostSum()
{
	double sum = 0.0;

	foreach(GraphEdge* e, callees)
		sum += e->cost;

	return sum;
}

double GraphNode::calleeCountSum()
{
	double sum = 0.0;

	foreach(GraphEdge* e, callees)
		sum += e->count;

	return sum;
}

double GraphNode::callerCostSum()
{
	double sum = 0.0;

	foreach(GraphEdge* e, callers)
		sum += e->cost;

	return sum;
}

double GraphNode::callerCountSum()
{
	double sum = 0.0;

	foreach(GraphEdge* e, callers)
		sum += e->count;

	return sum;
}


230
231
TraceCall* GraphNode::visibleCaller()
{
232
233
234
235
	if (0)
		qDebug("GraphNode::visibleCaller %s: last %d, count %d",
		       _f->prettyName().ascii(), _lastCallerIndex, callers.count());

236
237
	// can not use at(): index can be -1 (out of bounds), result is 0 then
	GraphEdge* e = callers.value(_lastCallerIndex);
238
239
240
241
242
	if (e && !e->isVisible())
		e = 0;
	if (!e) {
		double maxCost = 0.0;
		GraphEdge* maxEdge = 0;
243
244
		for(int i = 0; i<callers.size(); i++) {
			e = callers[i];
245
246
247
			if (e->isVisible() && (e->cost > maxCost)) {
				maxCost = e->cost;
				maxEdge = e;
248
				_lastCallerIndex = i;
249
			}
250
		}
251
252
253
		e = maxEdge;
	}
	return e ? e->call() : 0;
254
255
}

256
TraceCall* GraphNode::visibleCallee()
257
{
258
	if (0)
259
260
		qDebug("GraphNode::visibleCallee %s: last %d, count %d",
		       _f->prettyName().ascii(), _lastCalleeIndex, callees.count());
261

262
	GraphEdge* e = callees.value(_lastCalleeIndex);
263
264
265
266
267
268
	if (e && !e->isVisible())
		e = 0;

	if (!e) {
		double maxCost = 0.0;
		GraphEdge* maxEdge = 0;
269
270
		for(int i = 0; i<callees.size(); i++) {
			e = callees[i];
271
272
273
			if (e->isVisible() && (e->cost > maxCost)) {
				maxCost = e->cost;
				maxEdge = e;
274
				_lastCalleeIndex = i;
275
			}
276
		}
277
278
279
		e = maxEdge;
	}
	return e ? e->call() : 0;
280
281
}

282
void GraphNode::setCallee(GraphEdge* e)
283
{
284
	_lastCalleeIndex = callees.indexOf(e);
285
	_lastFromCaller = false;
286
287
288
289
}

void GraphNode::setCaller(GraphEdge* e)
{
290
	_lastCallerIndex = callers.indexOf(e);
291
	_lastFromCaller = true;
292
293
294
295
}

TraceFunction* GraphNode::nextVisible()
{
296
297
298
	TraceCall* c;

	if (_lastFromCaller) {
299
		c = nextVisibleCaller();
300
301
		if (c)
			return c->called(true);
302
		c = nextVisibleCallee();
303
304
305
		if (c)
			return c->caller(true);
	} else {
306
		c = nextVisibleCallee();
307
308
		if (c)
			return c->caller(true);
309
		c = nextVisibleCaller();
310
311
312
313
		if (c)
			return c->called(true);
	}
	return 0;
314
315
316
317
}

TraceFunction* GraphNode::priorVisible()
{
318
319
320
	TraceCall* c;

	if (_lastFromCaller) {
321
		c = priorVisibleCaller();
322
323
		if (c)
			return c->called(true);
324
		c = priorVisibleCallee();
325
326
327
		if (c)
			return c->caller(true);
	} else {
328
		c = priorVisibleCallee();
329
330
		if (c)
			return c->caller(true);
331
		c = priorVisibleCaller();
332
333
334
335
		if (c)
			return c->called(true);
	}
	return 0;
336
337
}

338
TraceCall* GraphNode::nextVisibleCaller(GraphEdge* e)
339
{
340
341
342
343
	int idx = e ? callers.indexOf(e) : _lastCallerIndex;
	idx++;
	while(idx < callers.size()) {
		if (callers[idx]->isVisible()) {
344
			_lastCallerIndex = idx;
345
			return callers[idx]->call();
346
		}
347
		idx++;
348
	}
349
	return 0;
350
351
}

352
TraceCall* GraphNode::nextVisibleCallee(GraphEdge* e)
353
{
354
355
356
357
358
359
	int idx = e ? callees.indexOf(e) : _lastCalleeIndex;
	idx++;
	while(idx < callees.size()) {
		if (callees[idx]->isVisible()) {
			_lastCalleeIndex = idx;
			return callees[idx]->call();
360
		}
361
		idx++;
362
	}
363
	return 0;
364
365
}

366
TraceCall* GraphNode::priorVisibleCaller(GraphEdge* e)
367
{
368
	int idx = e ? callers.indexOf(e) : _lastCallerIndex;
369

370
371
372
373
374
	idx = (idx<0) ? callers.size()-1 : idx-1;
	while(idx >= 0) {
		if (callers[idx]->isVisible()) {
			_lastCallerIndex = idx;
			return callers[idx]->call();
375
		}
376
		idx--;
377
	}
378
	return 0;
379
380
}

381
TraceCall* GraphNode::priorVisibleCallee(GraphEdge* e)
382
{
383
	int idx = e ? callees.indexOf(e) : _lastCalleeIndex;
384

385
386
387
388
389
	idx = (idx<0) ? callees.size()-1 : idx-1;
	while(idx >= 0) {
		if (callees[idx]->isVisible()) {
			_lastCalleeIndex = idx;
			return callees[idx]->call();
390
		}
391
		idx--;
392
	}
393
	return 0;
394
395
}

396

397
398
399
400
401
402
//
// GraphEdge
//

GraphEdge::GraphEdge()
{
403
404
405
406
407
	_c=0;
	_from = _to = 0;
	_fromNode = _toNode = 0;
	cost = count = 0;
	_ce = 0;
408

409
410
	_visible = false;
	_lastFromCaller = true;
411
412
413
414
}

QString GraphEdge::prettyName()
{
415
416
417
418
	if (_c)
		return _c->prettyName();

	if (_from)
419
	    return QObject::tr("Call(s) from %1").arg(_from->prettyName());
420

421
	if (_to)
422
	    return QObject::tr("Call(s) to %1").arg(_to->prettyName());
423

424
	return QObject::tr("(unknown call)");
425
}
426
427
428

TraceFunction* GraphEdge::visibleCaller()
{
429
430
431
	if (_from) {
		_lastFromCaller = true;
		if (_fromNode)
432
			_fromNode->setCallee(this);
433
434
435
		return _from;
	}
	return 0;
436
437
}

438
TraceFunction* GraphEdge::visibleCallee()
439
{
440
441
442
443
444
445
446
	if (_to) {
		_lastFromCaller = false;
		if (_toNode)
			_toNode->setCaller(this);
		return _to;
	}
	return 0;
447
448
449
450
}

TraceCall* GraphEdge::nextVisible()
{
451
	TraceCall* res = 0;
452

453
	if (_lastFromCaller && _fromNode) {
454
		res = _fromNode->nextVisibleCallee(this);
455
456
457
458
459
		if (!res && _toNode)
			res = _toNode->nextVisibleCaller(this);
	} else if (_toNode) {
		res = _toNode->nextVisibleCaller(this);
		if (!res && _fromNode)
460
			res = _fromNode->nextVisibleCallee(this);
461
462
	}
	return res;
463
464
465
466
}

TraceCall* GraphEdge::priorVisible()
{
467
	TraceCall* res = 0;
468

469
	if (_lastFromCaller && _fromNode) {
470
		res = _fromNode->priorVisibleCallee(this);
471
472
473
474
475
		if (!res && _toNode)
			res = _toNode->priorVisibleCaller(this);
	} else if (_toNode) {
		res = _toNode->priorVisibleCaller(this);
		if (!res && _fromNode)
476
			res = _fromNode->priorVisibleCallee(this);
477
478
	}
	return res;
479
480
481
482
483
484
485
486
487
488
}



//
// GraphOptions
//

QString GraphOptions::layoutString(Layout l)
{
489
490
491
492
493
	if (l == Circular)
		return QString("Circular");
	if (l == LeftRight)
		return QString("LeftRight");
	return QString("TopDown");
494
495
496
497
}

GraphOptions::Layout GraphOptions::layout(QString s)
{
498
499
500
501
502
	if (s == QString("Circular"))
		return Circular;
	if (s == QString("LeftRight"))
		return LeftRight;
	return TopDown;
503
504
505
506
507
508
509
510
511
512
513
514
515
}


//
// StorableGraphOptions
//

StorableGraphOptions::StorableGraphOptions()
{
  // default options
  _funcLimit         = DEFAULT_FUNCLIMIT;
  _callLimit         = DEFAULT_CALLLIMIT;
  _maxCallerDepth    = DEFAULT_MAXCALLER;
516
  _maxCalleeDepth    = DEFAULT_MAXCALLEE;
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
  _showSkipped       = DEFAULT_SHOWSKIPPED;
  _expandCycles      = DEFAULT_EXPANDCYCLES;
  _detailLevel       = DEFAULT_DETAILLEVEL;
  _layout            = DEFAULT_LAYOUT;
}




//
// GraphExporter
//

GraphExporter::GraphExporter()
{
532
533
534
	_go = this;
	_tmpFile = 0;
	_item = 0;
535
	reset(0, 0, 0, ProfileContext::InvalidType, QString());
536
537
}

538
GraphExporter::GraphExporter(TraceData* d, TraceFunction* f,
539
                             EventType* ct, ProfileContext::Type gt,
540
                             QString filename)
541
{
542
543
544
545
	_go = this;
	_tmpFile = 0;
	_item = 0;
	reset(d, f, ct, gt, filename);
546
547
548
549
}

GraphExporter::~GraphExporter()
{
550
	if (_item && _tmpFile) {
Josef Weidendorfer's avatar
Josef Weidendorfer committed
551
#if DEBUG_GRAPH
552
		_tmpFile->setAutoRemove(true);
Josef Weidendorfer's avatar
Josef Weidendorfer committed
553
#endif
554
555
		delete _tmpFile;
	}
556
557
558
}


559
void GraphExporter::reset(TraceData*, CostItem* i, EventType* ct,
560
                          ProfileContext::Type gt, QString filename)
561
{
562
563
564
	_graphCreated = false;
	_nodeMap.clear();
	_edgeMap.clear();
565

566
567
568
569
	if (_item && _tmpFile) {
		_tmpFile->setAutoRemove(true);
		delete _tmpFile;
	}
570

571
572
	if (i) {
		switch (i->type()) {
573
574
575
		case ProfileContext::Function:
		case ProfileContext::FunctionCycle:
		case ProfileContext::Call:
576
577
578
579
580
			break;
		default:
			i = 0;
		}
	}
581

582
583
584
585
586
587
588
	_item = i;
	_eventType = ct;
	_groupType = gt;
	if (!i)
		return;

	if (filename.isEmpty()) {
589
590
		_tmpFile = new QTemporaryFile();
		//_tmpFile->setSuffix(".dot");
591
592
593
594
595
596
597
598
599
		_tmpFile->setAutoRemove(false);
		_tmpFile->open();
		_dotName = _tmpFile->fileName();
		_useBox = true;
	} else {
		_tmpFile = 0;
		_dotName = filename;
		_useBox = false;
	}
600
601
602
603
604
605
}



void GraphExporter::setGraphOptions(GraphOptions* go)
{
606
607
608
	if (go == 0)
		go = this;
	_go = go;
609
610
611
612
}

void GraphExporter::createGraph()
{
613
614
615
616
617
618
	if (!_item)
		return;
	if (_graphCreated)
		return;
	_graphCreated = true;

619
620
	if ((_item->type() == ProfileContext::Function) ||(_item->type()
	        == ProfileContext::FunctionCycle)) {
621
622
623
624
		TraceFunction* f = (TraceFunction*) _item;

		double incl = f->inclusive()->subCost(_eventType);
		_realFuncLimit = incl * _go->funcLimit();
625
		_realCallLimit = _realFuncLimit * _go->callLimit();
626

627
		buildGraph(f, 0, true, 1.0); // down to callees
628
629
630
631
632
633
634
635
636
637
638

		// set costs of function back to 0, as it will be added again
		GraphNode& n = _nodeMap[f];
		n.self = n.incl = 0.0;

		buildGraph(f, 0, false, 1.0); // up to callers
	} else {
		TraceCall* c = (TraceCall*) _item;

		double incl = c->subCost(_eventType);
		_realFuncLimit = incl * _go->funcLimit();
639
		_realCallLimit = _realFuncLimit * _go->callLimit();
640
641
642
643
644
645
646
647
648

		// create edge
		TraceFunction *caller, *called;
		caller = c->caller(false);
		called = c->called(false);
		QPair<TraceFunction*,TraceFunction*> p(caller, called);
		GraphEdge& e = _edgeMap[p];
		e.setCall(c);
		e.setCaller(p.first);
649
		e.setCallee(p.second);
650
651
652
653
		e.cost = c->subCost(_eventType);
		e.count = c->callCount();

		SubCost s = called->inclusive()->subCost(_eventType);
654
		buildGraph(called, 0, true, e.cost / s); // down to callees
655
656
657
		s = caller->inclusive()->subCost(_eventType);
		buildGraph(caller, 0, false, e.cost / s); // up to callers
	}
658
659
}

660

661
void GraphExporter::writeDot(QIODevice* device)
662
{
663
664
665
666
667
668
	if (!_item)
		return;

	QFile* file = 0;
	QTextStream* stream = 0;

669
670
	if (device)
	    stream = new QTextStream(device);
671
	else {
672
673
674
	    if (_tmpFile)
		stream = new QTextStream(_tmpFile);
	    else {
675
676
		file = new QFile(_dotName);
		if ( !file->open(QIODevice::WriteOnly ) ) {
677
678
679
		    qDebug() << "Can not write dot file '"<< _dotName << "'";
		    delete file;
		    return;
680
681
		}
		stream = new QTextStream(file);
682
	    }
683
	}
684

685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
	if (!_graphCreated)
		createGraph();

	/* Generate dot format...
	 * When used for the CallGraphView (in contrast to "Export Callgraph..."),
	 * the labels are only dummy placeholders to reserve space for our own
	 * drawings.
	 */

	*stream << "digraph \"callgraph\" {\n";

	if (_go->layout() == LeftRight) {
		*stream << QString("  rankdir=LR;\n");
	} else if (_go->layout() == Circular) {
		TraceFunction *f = 0;
		switch (_item->type()) {
701
702
		case ProfileContext::Function:
		case ProfileContext::FunctionCycle:
703
704
			f = (TraceFunction*) _item;
			break;
705
		case ProfileContext::Call:
706
707
708
709
710
711
712
713
714
			f = ((TraceCall*)_item)->caller(true);
			break;
		default:
			break;
		}
		if (f)
			*stream << QString("  center=F%1;\n").arg((long)f, 0, 16);
		*stream << QString("  overlap=false;\n  splines=true;\n");
	}
715

716
	// for clustering
717
	QMap<TraceCostItem*,QList<GraphNode*> > nLists;
718
719
720
721
722
723
724
725
726
727
728
729

	GraphNodeMap::Iterator nit;
	for (nit = _nodeMap.begin(); nit != _nodeMap.end(); ++nit ) {
		GraphNode& n = *nit;

		if (n.incl <= _realFuncLimit)
			continue;

		// for clustering: get cost item group of function
		TraceCostItem* g;
		TraceFunction* f = n.function();
		switch (_groupType) {
730
		case ProfileContext::Object:
731
732
			g = f->object();
			break;
733
		case ProfileContext::Class:
734
735
			g = f->cls();
			break;
736
		case ProfileContext::File:
737
738
			g = f->file();
			break;
739
		case ProfileContext::FunctionCycle:
740
741
742
743
744
745
746
747
			g = f->cycle();
			break;
		default:
			g = 0;
			break;
		}
		nLists[g].append(&n);
	}
748

749
	QMap<TraceCostItem*,QList<GraphNode*> >::Iterator lit;
750
751
	int cluster = 0;
	for (lit = nLists.begin(); lit != nLists.end(); ++lit, cluster++) {
752
		QList<GraphNode*>& l = lit.data();
753
754
755
756
		TraceCostItem* i = lit.key();

		if (_go->clusterGroups() && i) {
			QString iabr = i->prettyName();
757
758
			if ((int)iabr.length() > GlobalConfig::maxSymbolLength())
				iabr = iabr.left(GlobalConfig::maxSymbolLength()) + "...";
759
760
761
762
763

			*stream << QString("subgraph \"cluster%1\" { label=\"%2\";\n")
			.arg(cluster).arg(iabr);
		}

764
		foreach(GraphNode* np, l) {
765
766
767
			TraceFunction* f = np->function();

			QString abr = f->prettyName();
768
769
			if ((int)abr.length() > GlobalConfig::maxSymbolLength())
				abr = abr.left(GlobalConfig::maxSymbolLength()) + "...";
770
771
772

			*stream << QString("  F%1 [").arg((long)f, 0, 16);
			if (_useBox) {
773
774
775
				// we want a minimal size for cost display
				if ((int)abr.length() < 8) abr = abr + QString(8 - abr.length(),'_');

776
777
778
779
780
781
782
783
784
785
786
787
788
				// make label 3 lines for CallGraphView
				*stream << QString("shape=box,label=\"** %1 **\\n**\\n%2\"];\n")
				.arg(abr)
				.arg(SubCost(np->incl).pretty());
			} else
				*stream << QString("label=\"%1\\n%2\"];\n")
				.arg(abr)
				.arg(SubCost(np->incl).pretty());
		}

		if (_go->clusterGroups() && i)
			*stream << QString("}\n");
	}
789

790
791
792
793
794
795
796
	GraphEdgeMap::Iterator eit;
	for (eit = _edgeMap.begin(); eit != _edgeMap.end(); ++eit ) {
		GraphEdge& e = *eit;

		if (e.cost < _realCallLimit)
			continue;
		if (!_go->expandCycles()) {
797
			// do not show inner cycle calls
798
799
800
801
802
803
804
805
			if (e.call()->inCycle()>0)
				continue;
		}

		GraphNode& from = _nodeMap[e.from()];
		GraphNode& to = _nodeMap[e.to()];

		e.setCallerNode(&from);
806
		e.setCalleeNode(&to);
807
808
809
810

		if ((from.incl <= _realFuncLimit) ||(to.incl <= _realFuncLimit))
			continue;

811
		// remove dumped edges from n.callers/n.callees
812
		from.removeEdge(&e);
813
		to.removeEdge(&e);
814
815
816
817
818
819

		*stream << QString("  F%1 -> F%2 [weight=%3")
		.arg((long)e.from(), 0, 16)
		.arg((long)e.to(), 0, 16)
		.arg((long)log(log(e.cost)));

820
821
822
823
824
		if (_go->detailLevel() ==1) {
			*stream << QString(",label=\"%1 (%2x)\"")
				.arg(SubCost(e.cost).pretty())
				.arg(SubCost(e.count).pretty());
		    }
825
826
		else if (_go->detailLevel() ==2)
			*stream << QString(",label=\"%3\\n%4 x\"")
827
828
				.arg(SubCost(e.cost).pretty())
				.arg(SubCost(e.count).pretty());
829
830
831

		*stream << QString("];\n");
	}
832

833
834
835
836
837
838
839
840
841
842
	if (_go->showSkipped()) {

		// Create sum-edges for skipped edges
		GraphEdge* e;
		double costSum, countSum;
		for (nit = _nodeMap.begin(); nit != _nodeMap.end(); ++nit ) {
			GraphNode& n = *nit;
			if (n.incl <= _realFuncLimit)
				continue;

843
844
845
			// add edge for all skipped callers if cost sum is high enough
			costSum = n.callerCostSum();
			countSum = n.callerCountSum();
846
847
848
849
			if (costSum > _realCallLimit) {

				QPair<TraceFunction*,TraceFunction*> p(0, n.function());
				e = &(_edgeMap[p]);
850
				e->setCallee(p.second);
851
852
853
854
				e->cost = costSum;
				e->count = countSum;

				*stream << QString("  R%1 [shape=point,label=\"\"];\n")
855
					.arg((long)n.function(), 0, 16);
856
				*stream << QString("  R%1 -> F%2 [label=\"%3\\n%4 x\",weight=%5];\n")
857
858
859
860
861
					.arg((long)n.function(), 0, 16)
					.arg((long)n.function(), 0, 16)
					.arg(SubCost(costSum).pretty())
					.arg(SubCost(countSum).pretty())
					.arg((int)log(costSum));
862
863
			}

864
865
866
			// add edge for all skipped callees if cost sum is high enough
			costSum = n.calleeCostSum();
			countSum = n.calleeCountSum();
867
868
869
870
871
872
873
874
875
			if (costSum > _realCallLimit) {

				QPair<TraceFunction*,TraceFunction*> p(n.function(), 0);
				e = &(_edgeMap[p]);
				e->setCaller(p.first);
				e->cost = costSum;
				e->count = countSum;

				*stream << QString("  S%1 [shape=point,label=\"\"];\n")
876
					.arg((long)n.function(), 0, 16);
877
				*stream << QString("  F%1 -> S%2 [label=\"%3\\n%4 x\",weight=%5];\n")
878
879
880
881
882
					.arg((long)n.function(), 0, 16)
					.arg((long)n.function(), 0, 16)
					.arg(SubCost(costSum).pretty())
					.arg(SubCost(countSum).pretty())
					.arg((int)log(costSum));
883
884
885
			}
		}
	}
886

887
888
889
890
	// clear edges here completely.
	// Visible edges are inserted again on parsing in CallGraphView::refresh
	for (nit = _nodeMap.begin(); nit != _nodeMap.end(); ++nit ) {
		GraphNode& n = *nit;
891
		n.clearEdges();
892
	}
893

894
	*stream << "}\n";
895

896
897
	if (!device) {
	    if (_tmpFile) {
898
899
		stream->flush();
		_tmpFile->seek(0);
900
	    } else {
901
902
		file->close();
		delete file;
903
	    }
904
	}
905
	delete stream;
906
907
908
909
}

void GraphExporter::sortEdges()
{
910
911
912
	GraphNodeMap::Iterator nit;
	for (nit = _nodeMap.begin(); nit != _nodeMap.end(); ++nit ) {
		GraphNode& n = *nit;
913
		n.sortEdges();
914
	}
915
916
917
918
}

TraceFunction* GraphExporter::toFunc(QString s)
{
919
920
921
922
923
924
	if (s[0] != 'F')
		return 0;
	bool ok;
	TraceFunction* f = (TraceFunction*) s.mid(1).toUInt(&ok, 16);
	if (!ok)
		return 0;
925

926
	return f;
927
928
929
930
}

GraphNode* GraphExporter::node(TraceFunction* f)
{
931
932
	if (!f)
		return 0;
933

934
935
936
	GraphNodeMap::Iterator it = _nodeMap.find(f);
	if (it == _nodeMap.end())
		return 0;
937

938
	return &(*it);
939
940
941
942
}

GraphEdge* GraphExporter::edge(TraceFunction* f1, TraceFunction* f2)
{
943
944
945
	GraphEdgeMap::Iterator it = _edgeMap.find(qMakePair(f1, f2));
	if (it == _edgeMap.end())
		return 0;
946

947
	return &(*it);
948
949
950
}

/**
951
 * We do a DFS and do not stop on already visited nodes/edges,
952
953
954
955
956
957
958
 * but add up costs. We only stop if limits/max depth is reached.
 *
 * For a node/edge, it can happen that the first time visited the
 * cost will below the limit, so the search is stopped.
 * If on a further visit of the node/edge the limit is reached,
 * we use the whole node/edge cost and continue search.
 */
959
void GraphExporter::buildGraph(TraceFunction* f, int d, bool toCallees,
960
                               double factor)
961
{
Josef Weidendorfer's avatar
Josef Weidendorfer committed
962
#if DEBUG_GRAPH
963
964
	qDebug() << "buildGraph(" << f->prettyName() << "," << d << "," << factor
	<< ") [to " << (toCallees ? "Callees":"Callers") << "]";
Josef Weidendorfer's avatar
Josef Weidendorfer committed
965
#endif
966

967
968
969
970
971
972
973
974
975
976
977
978
979
980
	double oldIncl = 0.0;
	GraphNode& n = _nodeMap[f];
	if (n.function() == 0) {
		n.setFunction(f);
	} else
		oldIncl = n.incl;

	double incl = f->inclusive()->subCost(_eventType) * factor;
	n.incl += incl;
	n.self += f->subCost(_eventType) * factor;
	if (0)
		qDebug("  Added Incl. %f, now %f", incl, n.incl);

	// A negative depth limit means "unlimited"
981
	int maxDepth = toCallees ? _go->maxCalleeDepth()
982
983
984
985
986
987
	        : _go->maxCallerDepth();
	if ((maxDepth>=0) && (d >= maxDepth)) {
		if (0)
			qDebug("  Cutoff, max depth reached");
		return;
	}
988

989
990
991
992
993
994
995
	// if we just reached the limit by summing, do a DFS
	// from here with full incl. cost because of previous cutoffs
	if ((n.incl >= _realFuncLimit) && (oldIncl < _realFuncLimit))
		incl = n.incl;

	if (f->cycle()) {
		// for cycles members, we never stop on first visit, but always on 2nd
996
		// note: a 2nd visit never should happen, as we do not follow inner-cycle
997
998
999
1000
		//       calls
		if (oldIncl > 0.0) {
			if (0)
				qDebug("  Cutoff, 2nd visit to Cycle Member");
1001
			// and takeback cost addition, as it is added twice
1002
1003
1004
1005
1006
1007
1008
1009
1010
			n.incl = oldIncl;
			n.self -= f->subCost(_eventType) * factor;
			return;
		}
	} else if (incl <= _realFuncLimit) {
		if (0)
			qDebug("  Cutoff, below limit");
		return;
	}
1011

1012
1013
1014
1015
	TraceCall* call;
	TraceFunction* f2;

	// on entering a cycle, only go the FunctionCycle
1016
	TraceCallList l = toCallees ? f->callings(false) : f->callers(false);
1017
1018
1019

	for (call=l.first(); call; call=l.next()) {

1020
		f2 = toCallees ? call->called(false) : call->caller(false);
1021
1022
1023
1024
1025
1026
1027
1028
1029

		double count = call->callCount() * factor;
		double cost = call->subCost(_eventType) * factor;

		// ignore function calls with absolute cost < 3 per call
		// No: This would skip a lot of functions e.g. with L2 cache misses
		// if (count>0.0 && (cost/count < 3)) continue;

		double oldCost = 0.0;
1030
1031
		QPair<TraceFunction*,TraceFunction*> p(toCallees ? f : f2,
		                                       toCallees ? f2 : f);
1032
1033
1034
1035
		GraphEdge& e = _edgeMap[p];
		if (e.call() == 0) {
			e.setCall(call);
			e.setCaller(p.first);
1036
			e.setCallee(p.second);
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
		} else
			oldCost = e.cost;

		e.cost += cost;
		e.count += count;
		if (0)
			qDebug("  Edge to %s, added cost %f, now %f", f2->prettyName().ascii(), cost, e.cost);

		// if this call goes into a FunctionCycle, we also show the real call
		if (f2->cycle() == f2) {
			TraceFunction* realF;
1048
			realF = toCallees ? call->called(true) : call->caller(true);
1049
			QPair<TraceFunction*,TraceFunction*>
1050
			        realP(toCallees ? f : realF, toCallees ? realF : f);
1051
1052
1053
1054
			GraphEdge& e = _edgeMap[realP];
			if (e.call() == 0) {
				e.setCall(call);
				e.setCaller(realP.first);
1055
				e.setCallee(realP.second);
1056
1057
1058
1059
1060
			}
			e.cost += cost;
			e.count += count;
		}

1061
		// - do not do a DFS on calls in recursion/cycle
1062
1063
1064
1065
1066
		if (call->inCycle()>0)
			continue;
		if (call->isRecursion())
			continue;

1067
1068
1069
1070
		if (toCallees)
			n.addUniqueCallee(&e);
		else
			n.addUniqueCaller(&e);
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087

		// if we just reached the call limit (=func limit by summing, do a DFS
		// from here with full incl. cost because of previous cutoffs
		if ((e.cost >= _realCallLimit) && (oldCost < _realCallLimit))
			cost = e.cost;
		if (cost < _realCallLimit) {
			if (0)
				qDebug("  Edge Cutoff, limit not reached");
			continue;
		}

		SubCost s;
		if (call->inCycle())
			s = f2->cycle()->inclusive()->subCost(_eventType);
		else
			s = f2->inclusive()->subCost(_eventType);
		SubCost v = call->subCost(_eventType);
1088
		// FIXME: Can s be 0?
1089
		buildGraph(f2, d+1, toCallees, factor * v / s);
1090
	}
1091
1092
1093
1094
1095
}

//
// PannerView
//
1096
1097
PanningView::PanningView(QWidget * parent)
	: QGraphicsView(parent)
1098
{
1099
	_movingZoomRect = false;
1100

1101
1102
	// FIXME: Why does this not work?
	viewport()->setFocusPolicy(Qt::NoFocus);
1103
1104
}

1105
void PanningView::setZoomRect(const QRectF& r)
1106
{
1107
	_zoomRect = r;
1108
	viewport()->update();
1109
1110
}

1111
void PanningView::drawForeground(QPainter * p, const QRectF&)
1112
{
1113
1114
1115
	if (!_zoomRect.isValid())
		return;

Marc Espie's avatar
Marc Espie committed
1116
1117
	QColor red(Qt::red);
	QPen pen(red.dark());
1118
1119
1120
	pen.setWidthF(2.0 / matrix().m11());
	p->setPen(pen);

Marc Espie's avatar
Marc Espie committed
1121
	QColor c(red.dark());
1122
1123
1124
1125
1126
	c.setAlphaF(0.05);
	p->setBrush(QBrush(c));

	p->drawRect(QRectF(_zoomRect.x(), _zoomRect.y(),
	                   _zoomRect.width()-1, _zoomRect.height()-1));
1127
1128
}

1129
void PanningView::mousePressEvent(QMouseEvent* e)
1130
{
1131
	QPointF sPos = mapToScene(e->pos());
1132

1133
1134
1135
1136
1137
1138
1139
1140
	if (_zoomRect.isValid()) {
		if (!_zoomRect.contains(sPos))
			emit zoomRectMoved(sPos.x() - _zoomRect.center().x(),
			                   sPos.y() - _zoomRect.center().y());

		_movingZoomRect = true;
		_lastPos = sPos;
	}
1141
1142
}

1143
void PanningView::mouseMoveEvent(QMouseEvent* e)
1144
{
1145
1146
1147
1148
1149
1150
	QPointF sPos = mapToScene(e->pos());
	if (_movingZoomRect) {
		emit zoomRectMoved(sPos.x() - _lastPos.x(),
		                   sPos.y() - _lastPos.y());
		_lastPos = sPos;
	}
1151
1152
}

1153
void PanningView::mouseReleaseEvent(QMouseEvent*)
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
{
    _movingZoomRect = false;
    emit zoomRectMoveFinished();
}





//
// CanvasNode
//

1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
CanvasNode::CanvasNode(CallGraphView* v, GraphNode* n, int x, int y, int w,
                       int h) :
	QGraphicsRectItem(QRect(x, y, w, h)), _node(n), _view(v)
{
	setPosition(0, DrawParams::TopCenter);
	setPosition(1, DrawParams::BottomCenter);

	updateGroup();

	if (!_node || !_view)
		return;

	if (_node->function())
		setText(0, _node->function()->prettyName());

1182
	ProfileCostArray* totalCost;
1183
	if (GlobalConfig::showExpanded()) {
1184
1185
1186
1187
1188
1189
		if (_view->activeFunction()) {
			if (_view->activeFunction()->cycle())
				totalCost = _view->activeFunction()->cycle()->inclusive();
			else
				totalCost = _view->activeFunction()->inclusive();
		} else
1190
			totalCost = (ProfileCostArray*) _view->activeItem();
1191
1192
1193
1194
	} else
		totalCost = ((TraceItemView*)_view)->data();
	double total = totalCost->subCost(_view->eventType());
	double inclP = 100.0 * n->incl/ total;
1195
	if (GlobalConfig::showPercentage())
1196
		setText(1, QString("%1 %")
1197
		.arg(inclP, 0, 'f', GlobalConfig::percentPrecision()));
1198
1199
1200
	else
		setText(1, SubCost(n->incl).pretty());
	setPixmap(1, percentagePixmap(25, 10, (int)(inclP+.5), Qt::blue, true));
1201
1202

	setToolTip(QString("%1 (%2)").arg(text(0)).arg(text(1)));
1203
1204
1205
1206
}

void CanvasNode::setSelected(bool s)
{
Josef Weidendorfer's avatar