File indexing completed on 2024-04-28 09:36:46
0001 /* 0002 This file is part of KCachegrind. 0003 0004 SPDX-FileCopyrightText: 2002-2016 Josef Weidendorfer <Josef.Weidendorfer@gmx.de> 0005 0006 SPDX-License-Identifier: GPL-2.0-only 0007 */ 0008 0009 #include "eventtype.h" 0010 0011 #include <QRegularExpression> 0012 #include <QDebug> 0013 0014 #include "globalconfig.h" 0015 0016 //--------------------------------------------------- 0017 // EventType 0018 0019 QList<EventType*>* EventType::_knownTypes = nullptr; 0020 0021 EventType::EventType(const QString& name, const QString& longName, 0022 const QString& formula) 0023 { 0024 _name = name; 0025 _longName = longName; 0026 _formula = formula; 0027 _isReal = formula.isEmpty(); 0028 _set = nullptr; 0029 _realIndex = ProfileCostArray::InvalidIndex; 0030 _parsed = false; 0031 _inParsing = false; 0032 0033 for (int i=0; i<ProfileCostArray::MaxRealIndex;i++) 0034 _coefficient[i] = 0; 0035 } 0036 0037 void EventType::setFormula(const QString& formula) 0038 { 0039 _formula = formula; 0040 _realIndex = ProfileCostArray::InvalidIndex; 0041 _parsed = false; 0042 _isReal = false; 0043 } 0044 0045 void EventType::setEventTypeSet(EventTypeSet* m) 0046 { 0047 _parsed = false; 0048 _set = m; 0049 } 0050 0051 // setting the index to ProfileCostArray::MaxRealIndex makes it a 0052 // real type with unspecified index 0053 void EventType::setRealIndex(int i) 0054 { 0055 if (i<0 || i>ProfileCostArray::MaxRealIndex) 0056 i=ProfileCostArray::InvalidIndex; 0057 0058 _realIndex = i; 0059 _formula = QString(); 0060 _isReal = true; 0061 } 0062 0063 // checks for existing types and sets coefficients 0064 bool EventType::parseFormula() 0065 { 0066 if (isReal()) return true; 0067 if (_parsed) return true; 0068 0069 if (_inParsing) { 0070 qDebug("TraceEventType::parseFormula: Recursion detected."); 0071 return false; 0072 } 0073 0074 if (!_set) { 0075 qDebug("TraceEventType::parseFormula: Container of this event type unknown!"); 0076 return false; 0077 } 0078 0079 _inParsing = true; 0080 0081 for (int i=0; i<ProfileCostArray::MaxRealIndex;i++) 0082 _coefficient[i] = 0; 0083 _parsedFormula = QString(); 0084 0085 QRegularExpression rx( QStringLiteral("((?:\\+|\\-)?)\\s*(\\d*)\\s*\\*?\\s*(\\w+)") ); 0086 0087 int factor, found, matching; 0088 QString costName; 0089 EventType* eventType; 0090 0091 found = 0; // how many types are referenced in formula 0092 matching = 0; // how many types actually are defined in profile data 0093 qsizetype from = 0; 0094 QRegularExpressionMatch match; 0095 while ((from = _formula.indexOf(rx, from, &match)) != -1) { 0096 from += match.capturedLength(); 0097 if (match.captured(0).isEmpty()) break; 0098 found++; 0099 0100 //qDebug("parseFormula: matched '%s','%s','%s'", 0101 // qPrintable(rx.cap(1)), qPrintable(rx.cap(2)), qPrintable(rx.cap(3))); 0102 0103 costName = match.captured(3); 0104 eventType = _set->type(costName); 0105 if (!eventType) { 0106 //qDebug("Cost type '%s': In formula cost '%s' unknown.", 0107 // qPrintable(_name), qPrintable(costName)); 0108 continue; 0109 } 0110 0111 factor = (match.captured(2).isEmpty()) ? 1 : match.captured(2).toInt(); 0112 if (match.captured(1) == QLatin1String("-")) factor = -factor; 0113 if (factor == 0) continue; 0114 0115 matching++; 0116 0117 if (!_parsedFormula.isEmpty()) { 0118 _parsedFormula += QStringLiteral(" %1 ").arg((factor>0) ? '+':'-'); 0119 } 0120 else if (factor<0) 0121 _parsedFormula += QLatin1String("- "); 0122 if ((factor!=-1) && (factor!=1)) 0123 _parsedFormula += QString::number( (factor>0)?factor:-factor ) + ' '; 0124 _parsedFormula += costName; 0125 0126 if (eventType->isReal()) 0127 _coefficient[eventType->realIndex()] += factor; 0128 else { 0129 eventType->parseFormula(); 0130 for (int i=0; i<ProfileCostArray::MaxRealIndex;i++) 0131 _coefficient[i] += factor * eventType->_coefficient[i]; 0132 } 0133 } 0134 0135 _inParsing = false; 0136 if (found == 0) { 0137 // empty formula 0138 _parsedFormula = QStringLiteral("0"); 0139 _parsed = true; 0140 return true; 0141 } 0142 if (matching>0) { 0143 _parsed = true; 0144 return true; 0145 } 0146 return false; 0147 } 0148 0149 0150 QString EventType::parsedFormula() 0151 { 0152 if (isReal()) return QString(); 0153 0154 parseFormula(); 0155 return _parsedFormula; 0156 } 0157 0158 QString EventType::parsedRealFormula() 0159 { 0160 QString res; 0161 0162 if (!parseFormula()) return res; 0163 0164 for (int i=0; i<ProfileCostArray::MaxRealIndex;i++) { 0165 int c = _coefficient[i]; 0166 if (c == 0) continue; 0167 0168 if (!res.isEmpty()) { 0169 res += ' '; 0170 if (c>0) res += QLatin1String("+ "); 0171 } 0172 if (c<0) { res += QLatin1String("- "); c = -c; } 0173 res += QString::number(c); 0174 0175 EventType* t = _set->type(i); 0176 if (!t) continue; 0177 0178 if (!t->name().isEmpty()) 0179 res += QStringLiteral(" * %1").arg(t->name()); 0180 } 0181 0182 return res; 0183 } 0184 0185 SubCost EventType::subCost(ProfileCostArray* c) 0186 { 0187 if (_realIndex != ProfileCostArray::InvalidIndex) 0188 return c->subCost(_realIndex); 0189 0190 if (!_parsed) { 0191 if (!parseFormula()) return 0; 0192 } 0193 SubCost res = 0; 0194 0195 int rc = _set->realCount(); 0196 for (int i = 0;i<rc;i++) 0197 if (_coefficient[i] != 0) 0198 res += _coefficient[i] * c->subCost(i); 0199 0200 return res; 0201 } 0202 0203 int EventType::histCost(ProfileCostArray* c, double total, double* hist) 0204 { 0205 if (total == 0.0) return 0; 0206 0207 if (!_parsed) { 0208 if (!parseFormula()) return 0; 0209 } 0210 0211 int rc = _set->realCount(); 0212 for (int i = 0;i<rc;i++) { 0213 if (_coefficient[i] != 0) 0214 hist[i] = _coefficient[i] * c->subCost(i) / total; 0215 else 0216 hist[i] = 0.0; 0217 } 0218 0219 return rc; 0220 } 0221 0222 0223 bool EventType::hasKnownRealType(const QString& n) 0224 { 0225 if (!_knownTypes) return false; 0226 0227 foreach (EventType* t, *_knownTypes) 0228 if (t->isReal() && (t->name() == n)) 0229 return true; 0230 0231 return false; 0232 } 0233 0234 bool EventType::hasKnownDerivedType(const QString& n) 0235 { 0236 if (!_knownTypes) return false; 0237 0238 foreach (EventType* t, *_knownTypes) 0239 if (!t->isReal() && (t->name() == n)) 0240 return true; 0241 0242 return false; 0243 } 0244 0245 EventType* EventType::cloneKnownRealType(const QString& n) 0246 { 0247 if (!_knownTypes) return nullptr; 0248 0249 foreach (EventType* t, *_knownTypes) 0250 if (t->isReal() && (t->name() == n)) { 0251 EventType* type = new EventType(*t); 0252 return type; 0253 } 0254 0255 return nullptr; 0256 } 0257 0258 0259 EventType* EventType::cloneKnownDerivedType(const QString& n) 0260 { 0261 if (!_knownTypes) return nullptr; 0262 0263 foreach (EventType* t, *_knownTypes) 0264 if (!t->isReal() && (t->name() == n)) { 0265 EventType* type = new EventType(*t); 0266 return type; 0267 } 0268 0269 return nullptr; 0270 } 0271 0272 // we take ownership 0273 void EventType::add(EventType* t, bool overwriteExisting) 0274 { 0275 if (!t) return; 0276 0277 t->setEventTypeSet(nullptr); 0278 0279 if (!_knownTypes) 0280 _knownTypes = new QList<EventType*>; 0281 0282 /* Already known? */ 0283 foreach (EventType* kt, *_knownTypes) 0284 if (kt->name() == t->name()) { 0285 if (overwriteExisting) { 0286 // Overwrite old type 0287 if (!t->longName().isEmpty() && (t->longName() != t->name())) 0288 kt->setLongName(t->longName()); 0289 if (!t->formula().isEmpty()) 0290 kt->setFormula(t->formula()); 0291 } 0292 delete t; 0293 return; 0294 } 0295 0296 if (t->longName().isEmpty()) t->setLongName(t->name()); 0297 _knownTypes->append(t); 0298 } 0299 0300 0301 int EventType::knownTypeCount() 0302 { 0303 if (!_knownTypes) return 0; 0304 0305 return _knownTypes->count(); 0306 } 0307 0308 bool EventType::remove(const QString& n) 0309 { 0310 if (!_knownTypes) return false; 0311 0312 foreach (EventType* t, *_knownTypes) 0313 if (!t->isReal() && (t->name() == n)) { 0314 _knownTypes->removeAll(t); 0315 delete t; 0316 return true; 0317 } 0318 0319 return false; 0320 } 0321 0322 EventType* EventType::knownType(int i) 0323 { 0324 if (!_knownTypes) return nullptr; 0325 if (i<0 || i>=(int)_knownTypes->count()) return nullptr; 0326 0327 return _knownTypes->at(i); 0328 } 0329 0330 0331 //--------------------------------------------------- 0332 // EventTypeSet 0333 0334 EventTypeSet::EventTypeSet() 0335 { 0336 _realCount = 0; 0337 _derivedCount = 0; 0338 for (int i=0;i<ProfileCostArray::MaxRealIndex;i++) _real[i] = nullptr; 0339 for (int i=0;i<ProfileCostArray::MaxRealIndex;i++) _derived[i] = nullptr; 0340 } 0341 0342 EventTypeSet::~EventTypeSet() 0343 { 0344 for (int i=0;i<ProfileCostArray::MaxRealIndex;i++) 0345 delete _real[i]; 0346 0347 for (int i=0;i<ProfileCostArray::MaxRealIndex;i++) 0348 delete _derived[i]; 0349 } 0350 0351 EventTypeMapping* EventTypeSet::createMapping(const QString& types) 0352 { 0353 // first check if there is enough space in the set 0354 int newCount = 0; 0355 int pos = 0, pos2, len = types.length(); 0356 0357 while (1) { 0358 // skip space 0359 while((pos<len) && types[pos].isSpace()) pos++; 0360 0361 pos2 = pos; 0362 while((pos2<len) && !types[pos2].isSpace()) pos2++; 0363 if (pos2 == pos) break; 0364 0365 if (realIndex(types.mid(pos,pos2-pos)) == ProfileCostArray::InvalidIndex) 0366 newCount++; 0367 0368 pos = pos2; 0369 } 0370 0371 if (newCount+_realCount > ProfileCostArray::MaxRealIndex) { 0372 qDebug() << "EventTypeSet::createMapping: No space for " 0373 << newCount << " cost entries."; 0374 qDebug() << "Increase MaxRealIndexValue in libcore/costitem.h and recompile."; 0375 return nullptr; 0376 } 0377 0378 EventTypeMapping* mapping = new EventTypeMapping(this); 0379 0380 pos = 0; 0381 while (1) { 0382 // skip space 0383 while((pos<len) && types[pos].isSpace()) pos++; 0384 0385 pos2 = pos; 0386 while((pos2<len) && !types[pos2].isSpace()) pos2++; 0387 if (pos2 == pos) break; 0388 0389 mapping->append(addReal(types.mid(pos,pos2-pos))); 0390 0391 pos = pos2; 0392 } 0393 0394 return mapping; 0395 } 0396 0397 int EventTypeSet::addReal(const QString& t) 0398 { 0399 int index = realIndex(t); 0400 if (index>=0) return index; 0401 0402 EventType* ct = EventType::cloneKnownRealType(t); 0403 if (!ct) ct = new EventType(t, t); 0404 0405 // make it real 0406 ct->setRealIndex(); 0407 0408 return add(ct); 0409 } 0410 0411 // add an event type to a set 0412 // this transfers ownership of the type! 0413 int EventTypeSet::add(EventType* et) 0414 { 0415 if (!et) return ProfileCostArray::InvalidIndex; 0416 0417 et->setEventTypeSet(this); 0418 0419 if (et->isReal()) { 0420 if (_realCount >= ProfileCostArray::MaxRealIndex) { 0421 qDebug("WARNING: Maximum for real event types reached (on adding '%s')", 0422 qPrintable(et->name())); 0423 return ProfileCostArray::InvalidIndex; 0424 } 0425 _real[_realCount] = et; 0426 et->setRealIndex(_realCount); 0427 0428 _realCount++; 0429 return _realCount-1; 0430 } 0431 0432 if (_derivedCount >= ProfileCostArray::MaxRealIndex) { 0433 qDebug("WARNING: Maximum for virtual event types reached (on adding '%s')", 0434 qPrintable(et->name())); 0435 return ProfileCostArray::InvalidIndex; 0436 } 0437 _derived[_derivedCount] = et; 0438 _derivedCount++; 0439 return _derivedCount-1; 0440 } 0441 0442 // we delete the type: t is invalid when returning true! 0443 bool EventTypeSet::remove(EventType* t) 0444 { 0445 if (!t) return false; 0446 if (t->set() != this) return false; 0447 0448 // do not delete real types 0449 if (t->isReal()) return false; 0450 0451 int i; 0452 for(i=0;i<_derivedCount;i++) 0453 if (_derived[i] == t) break; 0454 0455 // not found? 0456 if (i == _derivedCount) return false; 0457 0458 // delete known type with same name 0459 EventType::remove(t->name()); 0460 0461 // delete this type 0462 _derived[i] = nullptr; 0463 delete t; 0464 if (i+1 == _derivedCount) { 0465 // we can reuse the last index 0466 _derivedCount--; 0467 } 0468 return true; 0469 } 0470 0471 0472 EventType* EventTypeSet::realType(int t) 0473 { 0474 if (t<0 || t>=_realCount) return nullptr; 0475 return _real[t]; 0476 } 0477 0478 EventType* EventTypeSet::derivedType(int t) 0479 { 0480 if (t<0 || t>=_derivedCount) return nullptr; 0481 return _derived[t]; 0482 } 0483 0484 0485 EventType* EventTypeSet::type(int t) 0486 { 0487 if (t<0) return nullptr; 0488 if (t<_realCount) return _real[t]; 0489 0490 t -= ProfileCostArray::MaxRealIndex; 0491 if (t<0) return nullptr; 0492 if (t<_derivedCount) return _derived[t]; 0493 0494 return nullptr; 0495 } 0496 0497 EventType* EventTypeSet::type(const QString& name) 0498 { 0499 for (int i=0;i<_realCount;i++) 0500 if (_real[i] && (_real[i]->name() == name)) 0501 return _real[i]; 0502 0503 for (int i=0;i<_derivedCount;i++) 0504 if (_derived[i] && (_derived[i]->name() == name)) 0505 return _derived[i]; 0506 0507 return nullptr; 0508 } 0509 0510 EventType* EventTypeSet::typeForLong(const QString& name) 0511 { 0512 for (int i=0;i<_realCount;i++) 0513 if (_real[i] && (_real[i]->longName() == name)) 0514 return _real[i]; 0515 0516 for (int i=0;i<_derivedCount;i++) 0517 if (_derived[i] && (_derived[i]->longName() == name)) 0518 return _derived[i]; 0519 0520 return nullptr; 0521 } 0522 0523 0524 int EventTypeSet::realIndex(const QString& name) 0525 { 0526 for (int i=0;i<_realCount;i++) 0527 if (_real[i] && (_real[i]->name() == name)) 0528 return i; 0529 0530 return ProfileCostArray::InvalidIndex; 0531 } 0532 0533 int EventTypeSet::index(const QString& name) 0534 { 0535 for (int i=0;i<_realCount;i++) 0536 if (_real[i] && (_real[i]->name() == name)) 0537 return i; 0538 0539 for (int i=0;i<_derivedCount;i++) 0540 if (_derived[i] && (_derived[i]->name() == name)) 0541 return ProfileCostArray::MaxRealIndex + 1 + i; 0542 0543 return ProfileCostArray::InvalidIndex; 0544 } 0545 0546 int EventTypeSet::addKnownDerivedTypes() 0547 { 0548 int addCount = 0; 0549 int addDiff, i; 0550 int knownCount = EventType::knownTypeCount(); 0551 0552 while (1) { 0553 addDiff = 0; 0554 for (i=0; i<knownCount; ++i) { 0555 EventType* t = EventType::knownType(i); 0556 if (t->isReal()) continue; 0557 if (index(t->name()) != ProfileCostArray::InvalidIndex) continue; 0558 t->setEventTypeSet(this); 0559 if (t->parseFormula()) { 0560 addDiff++; 0561 add(new EventType(t->name(), t->longName(), t->formula())); 0562 } 0563 t->setEventTypeSet(nullptr); 0564 } 0565 if (addDiff == 0) break; 0566 addCount += addDiff; 0567 } 0568 return addCount; 0569 } 0570 0571 0572 //--------------------------------------------------- 0573 // EventTypeMapping 0574 0575 EventTypeMapping::EventTypeMapping(EventTypeSet* set) 0576 { 0577 _set = set; 0578 clear(); 0579 } 0580 0581 void EventTypeMapping::clear() 0582 { 0583 _count = 0; 0584 _isIdentity = true; 0585 _firstUnused = 0; 0586 for(int i=0;i<ProfileCostArray::MaxRealIndex;i++) { 0587 _realIndex[i] = ProfileCostArray::InvalidIndex; 0588 _nextUnused[i] = i+1; 0589 } 0590 } 0591 0592 int EventTypeMapping::maxRealIndex(int count) 0593 { 0594 if (count > _count) count = _count; 0595 if (_isIdentity) return count-1; 0596 0597 int maxIndex = -1; 0598 for(int j=0; j<count; j++) 0599 if (maxIndex < _realIndex[j]) 0600 maxIndex = _realIndex[j]; 0601 return maxIndex; 0602 } 0603 0604 bool EventTypeMapping::append(const QString& type, bool create) 0605 { 0606 if (!_set) return false; 0607 int index = create ? _set->addReal(type) : _set->realIndex(type); 0608 0609 return append(index); 0610 } 0611 0612 bool EventTypeMapping::append(int type) 0613 { 0614 if (!_set) return false; 0615 if ((type<0) || (type >= _set->realCount())) return false; 0616 0617 if ( _count >= ProfileCostArray::MaxRealIndex) return false; 0618 0619 _realIndex[_count] = type; 0620 0621 if (_isIdentity && (_count != type)) _isIdentity = false; 0622 if (type == _firstUnused) 0623 _firstUnused = _nextUnused[type]; 0624 for(int i=0;i<type;i++) 0625 if (_nextUnused[i] == type) 0626 _nextUnused[i]=_nextUnused[type]; 0627 0628 _count++; 0629 return true; 0630 }