tools/qmlprofiler/qmlprofilerdata.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtQml module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include "qmlprofilerdata.h"
  43
  44 #include <QStringList>
  45 #include <QUrl>
  46 #include <QHash>
  47 #include <QFile>
  48 #include <QXmlStreamReader>
  49
  50 namespace Constants {
  51     const char TYPE_PAINTING_STR[] = "Painting";
  52     const char TYPE_COMPILING_STR[] = "Compiling";
  53     const char TYPE_CREATING_STR[] = "Creating";
  54     const char TYPE_BINDING_STR[] = "Binding";
  55     const char TYPE_HANDLINGSIGNAL_STR[] = "HandlingSignal";
  56     const char PROFILER_FILE_VERSION[] = "1.02";
  57 }
  58
  59 struct QmlRangeEventData {
  60     QmlRangeEventData() {} // never called
  61     QmlRangeEventData(const QString &_displayName,
  62                  const QQmlProfilerService::BindingType &_bindingType,
  63                  const QString &_eventHashStr,
  64                  const QmlEventLocation &_location,
  65                  const QString &_details,
  66                  const QQmlProfilerService::RangeType &_eventType)
  67         : displayName(_displayName),eventHashStr(_eventHashStr),location(_location),
  68           details(_details),eventType(_eventType),bindingType(_bindingType) {}
  69     QString displayName;
  70     QString eventHashStr;
  71     QmlEventLocation location;
  72     QString details;
  73     QQmlProfilerService::RangeType eventType;
  74     QQmlProfilerService::BindingType bindingType;
  75 };
  76
  77 struct QmlRangeEventStartInstance {
  78     QmlRangeEventStartInstance() {} // never called
  79     QmlRangeEventStartInstance(qint64 _startTime, qint64 _duration, int _frameRate,
  80                   int _animationCount, QmlRangeEventData *_data)
  81         : startTime(_startTime), duration(_duration), frameRate(_frameRate),
  82           animationCount(_animationCount), data(_data)
  83         { }
  84     qint64 startTime;
  85     qint64 duration;
  86     int frameRate;
  87     int animationCount;
  88     QmlRangeEventData *data;
  89 };
  90
  91 QT_BEGIN_NAMESPACE
  92 Q_DECLARE_TYPEINFO(QmlRangeEventData, Q_MOVABLE_TYPE);
  93 Q_DECLARE_TYPEINFO(QmlRangeEventStartInstance, Q_MOVABLE_TYPE);
  94 QT_END_NAMESPACE
  95
  96 struct QV8EventInfo {
  97     QString displayName;
  98     QString eventHashStr;
  99     QString functionName;
 100     QString fileName;
 101     int line;
 102     qint64 totalTime;
 103     qint64 selfTime;
 104
 105     QHash<QString, qint64> v8children;
 106 };
 107
 108 /////////////////////////////////////////////////////////////////
 109 class QmlProfilerDataPrivate
 110 {
 111 public:
 112     QmlProfilerDataPrivate(QmlProfilerData *qq){ Q_UNUSED(qq); }
 113
 114     // data storage
 115     QHash<QString, QmlRangeEventData *> eventDescriptions;
 116     QVector<QmlRangeEventStartInstance> startInstanceList;
 117     QHash<QString, QV8EventInfo *> v8EventHash;
 118
 119     qint64 traceStartTime;
 120     qint64 traceEndTime;
 121
 122     // internal state while collecting events
 123     QmlRangeEventStartInstance *lastFrameEvent;
 124     qint64 qmlMeasuredTime;
 125     qint64 v8MeasuredTime;
 126     QHash<int, QV8EventInfo *> v8parents;
 127     void clearV8RootEvent();
 128     QV8EventInfo v8RootEvent;
 129
 130     QmlProfilerData::State state;
 131 };
 132
 133 /////////////////////////////////////////////////////////////////
 134 QmlProfilerData::QmlProfilerData(QObject *parent) :
 135     QObject(parent),d(new QmlProfilerDataPrivate(this))
 136 {
 137     d->state = Empty;
 138     clear();
 139 }
 140
 141 QmlProfilerData::~QmlProfilerData()
 142 {
 143     clear();
 144     delete d;
 145 }
 146
 147 void QmlProfilerData::clear()
 148 {
 149     qDeleteAll(d->eventDescriptions.values());
 150     d->eventDescriptions.clear();
 151     d->startInstanceList.clear();
 152
 153     qDeleteAll(d->v8EventHash.values());
 154     d->v8EventHash.clear();
 155     d->v8parents.clear();
 156     d->clearV8RootEvent();
 157     d->v8MeasuredTime = 0;
 158
 159     d->traceEndTime = 0;
 160     d->traceStartTime = -1;
 161     d->qmlMeasuredTime = 0;
 162
 163     d->lastFrameEvent = 0;
 164
 165     setState(Empty);
 166 }
 167
 168 QString QmlProfilerData::getHashStringForQmlEvent(const QmlEventLocation &location, int eventType)
 169 {
 170     return QString(QStringLiteral("%1:%2:%3:%4")).arg(
 171                 location.filename,
 172                 QString::number(location.line),
 173                 QString::number(location.column),
 174                 QString::number(eventType));
 175 }
 176
 177 QString QmlProfilerData::getHashStringForV8Event(const QString &displayName, const QString &function)
 178 {
 179     return QString(QStringLiteral("%1:%2")).arg(displayName, function);
 180 }
 181
 182 QString QmlProfilerData::qmlRangeTypeAsString(QQmlProfilerService::RangeType typeEnum)
 183 {
 184     switch (typeEnum) {
 185     case QQmlProfilerService::Painting:
 186         return QLatin1String(Constants::TYPE_PAINTING_STR);
 187         break;
 188     case QQmlProfilerService::Compiling:
 189         return QLatin1String(Constants::TYPE_COMPILING_STR);
 190         break;
 191     case QQmlProfilerService::Creating:
 192         return QLatin1String(Constants::TYPE_CREATING_STR);
 193         break;
 194     case QQmlProfilerService::Binding:
 195         return QLatin1String(Constants::TYPE_BINDING_STR);
 196         break;
 197     case QQmlProfilerService::HandlingSignal:
 198         return QLatin1String(Constants::TYPE_HANDLINGSIGNAL_STR);
 199         break;
 200     default:
 201         return QString::number((int)typeEnum);
 202     }
 203 }
 204
 205 void QmlProfilerData::setTraceStartTime(qint64 time)
 206 {
 207     d->traceStartTime = time;
 208 }
 209
 210 void QmlProfilerData::setTraceEndTime(qint64 time)
 211 {
 212     d->traceEndTime = time;
 213 }
 214
 215 qint64 QmlProfilerData::traceStartTime() const
 216 {
 217     return d->traceStartTime;
 218 }
 219
 220 qint64 QmlProfilerData::traceEndTime() const
 221 {
 222     return d->traceEndTime;
 223 }
 224
 225 void QmlProfilerData::addQmlEvent(QQmlProfilerService::RangeType type,
 226                                   QQmlProfilerService::BindingType bindingType,
 227                                   qint64 startTime,
 228                                   qint64 duration,
 229                                   const QStringList &data,
 230                                   const QmlEventLocation &location)
 231 {
 232     setState(AcquiringData);
 233
 234     QString details;
 235     // generate details string
 236     if (data.isEmpty())
 237         details = tr("Source code not available");
 238     else {
 239         details = data.join(QStringLiteral(" ")).replace(
 240                     QLatin1Char('\n'),QStringLiteral(" ")).simplified();
 241         QRegExp rewrite(QStringLiteral("\\(function \\$(\\w+)\\(\\) \\{ (return |)(.+) \\}\\)"));
 242         bool match = rewrite.exactMatch(details);
 243         if (match) {
 244             details = rewrite.cap(1) +QLatin1String(": ") + rewrite.cap(3);
 245         }
 246         if (details.startsWith(QLatin1String("file://")))
 247             details = details.mid(details.lastIndexOf(QLatin1Char('/')) + 1);
 248     }
 249
 250     QmlEventLocation eventLocation = location;
 251     QString displayName, eventHashStr;
 252     // generate hash
 253     if (eventLocation.filename.isEmpty()) {
 254         displayName = tr("<bytecode>");
 255         eventHashStr = getHashStringForQmlEvent(eventLocation, type);
 256     } else {
 257         const QString filePath = QUrl(eventLocation.filename).path();
 258         displayName = filePath.mid(
 259                     filePath.lastIndexOf(QLatin1Char('/')) + 1) +
 260                     QLatin1Char(':') + QString::number(eventLocation.line);
 261         eventHashStr = getHashStringForQmlEvent(eventLocation, type);
 262     }
 263
 264     QmlRangeEventData *newEvent;
 265     if (d->eventDescriptions.contains(eventHashStr)) {
 266         newEvent = d->eventDescriptions[eventHashStr];
 267     } else {
 268         newEvent = new QmlRangeEventData(displayName, bindingType, eventHashStr, location, details, type);
 269         d->eventDescriptions.insert(eventHashStr, newEvent);
 270     }
 271
 272     QmlRangeEventStartInstance rangeEventStartInstance(startTime, duration, 1e9/duration, -1, newEvent);
 273
 274     d->startInstanceList.append(rangeEventStartInstance);
 275 }
 276
 277 void QmlProfilerData::addFrameEvent(qint64 time, int framerate, int animationcount)
 278 {
 279     setState(AcquiringData);
 280
 281     QString details = tr("Animation Timer Update");
 282     QString displayName = tr("<Animation Update>");
 283     QString eventHashStr = displayName;
 284
 285     QmlRangeEventData *newEvent;
 286     if (d->eventDescriptions.contains(eventHashStr)) {
 287         newEvent = d->eventDescriptions[eventHashStr];
 288     } else {
 289         newEvent = new QmlRangeEventData(displayName, QQmlProfilerService::QmlBinding, eventHashStr, QmlEventLocation(), details, QQmlProfilerService::Painting);
 290         d->eventDescriptions.insert(eventHashStr, newEvent);
 291     }
 292
 293     qint64 duration = 1e9/framerate;
 294     // avoid overlap
 295     if (d->lastFrameEvent &&
 296             d->lastFrameEvent->startTime + d->lastFrameEvent->duration >= time) {
 297         d->lastFrameEvent->duration = time - 1 - d->lastFrameEvent->startTime;
 298     }
 299
 300     QmlRangeEventStartInstance rangeEventStartInstance(time, duration, framerate, animationcount, newEvent);
 301
 302     d->startInstanceList.append(rangeEventStartInstance);
 303
 304     d->lastFrameEvent = &d->startInstanceList.last();
 305 }
 306
 307 QString QmlProfilerData::rootEventName()
 308 {
 309     return tr("<program>");
 310 }
 311
 312 QString QmlProfilerData::rootEventDescription()
 313 {
 314     return tr("Main Program");
 315 }
 316
 317 void QmlProfilerDataPrivate::clearV8RootEvent()
 318 {
 319     v8RootEvent.displayName = QmlProfilerData::rootEventName();
 320     v8RootEvent.eventHashStr = QmlProfilerData::rootEventName();
 321     v8RootEvent.functionName = QmlProfilerData::rootEventDescription();
 322     v8RootEvent.line = -1;
 323     v8RootEvent.totalTime = 0;
 324     v8RootEvent.selfTime = 0;
 325     v8RootEvent.v8children.clear();
 326 }
 327
 328 void QmlProfilerData::addV8Event(int depth, const QString &function, const QString &filename,
 329                                  int lineNumber, double totalTime, double selfTime)
 330 {
 331     QString displayName = filename.mid(filename.lastIndexOf(QLatin1Char('/')) + 1) +
 332             QLatin1Char(':') + QString::number(lineNumber);
 333     QString hashStr = getHashStringForV8Event(displayName, function);
 334
 335     setState(AcquiringData);
 336
 337     // time is given in milliseconds, but internally we store it in microseconds
 338     totalTime *= 1e6;
 339     selfTime *= 1e6;
 340
 341     // accumulate information
 342     QV8EventInfo *eventData = d->v8EventHash[hashStr];
 343     if (!eventData) {
 344         eventData = new QV8EventInfo;
 345         eventData->displayName = displayName;
 346         eventData->eventHashStr = hashStr;
 347         eventData->fileName = filename;
 348         eventData->functionName = function;
 349         eventData->line = lineNumber;
 350         eventData->totalTime = totalTime;
 351         eventData->selfTime = selfTime;
 352         d->v8EventHash[hashStr] = eventData;
 353     } else {
 354         eventData->totalTime += totalTime;
 355         eventData->selfTime += selfTime;
 356     }
 357     d->v8parents[depth] = eventData;
 358
 359     QV8EventInfo *parentEvent = 0;
 360     if (depth == 0) {
 361         parentEvent = &d->v8RootEvent;
 362         d->v8MeasuredTime += totalTime;
 363     }
 364     if (depth > 0 && d->v8parents.contains(depth-1)) {
 365         parentEvent = d->v8parents.value(depth-1);
 366     }
 367
 368     if (parentEvent != 0) {
 369         if (!parentEvent->v8children.contains(eventData->eventHashStr)) {
 370             parentEvent->v8children[eventData->eventHashStr] = totalTime;
 371         } else {
 372             parentEvent->v8children[eventData->eventHashStr] += totalTime;
 373         }
 374     }
 375 }
 376
 377 void QmlProfilerData::computeQmlTime()
 378 {
 379     // compute levels
 380     QHash<int, qint64> endtimesPerLevel;
 381     int minimumLevel = 1;
 382     int level = minimumLevel;
 383
 384     for (int i = 0; i < d->startInstanceList.count(); i++) {
 385         qint64 st = d->startInstanceList[i].startTime;
 386         int type = d->startInstanceList[i].data->eventType;
 387
 388         if (type == QQmlProfilerService::Painting) {
 389             continue;
 390         }
 391
 392         // general level
 393         if (endtimesPerLevel[level] > st) {
 394             level++;
 395         } else {
 396             while (level > minimumLevel && endtimesPerLevel[level-1] <= st)
 397                 level--;
 398         }
 399         endtimesPerLevel[level] = st + d->startInstanceList[i].duration;
 400
 401         if (level == minimumLevel) {
 402             d->qmlMeasuredTime += d->startInstanceList[i].duration;
 403         }
 404     }
 405 }
 406
 407 bool compareStartTimes(const QmlRangeEventStartInstance &t1, const QmlRangeEventStartInstance &t2)
 408 {
 409     return t1.startTime < t2.startTime;
 410 }
 411
 412 void QmlProfilerData::sortStartTimes()
 413 {
 414     if (d->startInstanceList.count() < 2)
 415         return;
 416
 417     // assuming startTimes is partially sorted
 418     // identify blocks of events and sort them with quicksort
 419     QVector<QmlRangeEventStartInstance>::iterator itFrom = d->startInstanceList.end() - 2;
 420     QVector<QmlRangeEventStartInstance>::iterator itTo = d->startInstanceList.end() - 1;
 421
 422     while (itFrom != d->startInstanceList.begin() && itTo != d->startInstanceList.begin()) {
 423         // find block to sort
 424         while ( itFrom != d->startInstanceList.begin()
 425                 && itTo->startTime > itFrom->startTime ) {
 426             itTo--;
 427             itFrom = itTo - 1;
 428         }
 429
 430         // if we're at the end of the list
 431         if (itFrom == d->startInstanceList.begin())
 432             break;
 433
 434         // find block length
 435         while ( itFrom != d->startInstanceList.begin()
 436                 && itTo->startTime <= itFrom->startTime )
 437             itFrom--;
 438
 439         if (itTo->startTime <= itFrom->startTime)
 440             qSort(itFrom, itTo + 1, compareStartTimes);
 441         else
 442             qSort(itFrom + 1, itTo + 1, compareStartTimes);
 443
 444         // move to next block
 445         itTo = itFrom;
 446         itFrom = itTo - 1;
 447     }
 448 }
 449
 450 void QmlProfilerData::complete()
 451 {
 452     setState(ProcessingData);
 453     sortStartTimes();
 454     computeQmlTime();
 455     setState(Done);
 456     emit dataReady();
 457 }
 458
 459 bool QmlProfilerData::isEmpty() const
 460 {
 461     return d->startInstanceList.isEmpty() && d->v8EventHash.isEmpty();
 462 }
 463
 464 bool QmlProfilerData::save(const QString &filename)
 465 {
 466     if (isEmpty()) {
 467         emit error(tr("No data to save"));
 468         return false;
 469     }
 470
 471     QFile file(filename);
 472     if (!file.open(QIODevice::WriteOnly)) {
 473         emit error(tr("Could not open %1 for writing").arg(filename));
 474         return false;
 475     }
 476
 477     QXmlStreamWriter stream(&file);
 478     stream.setAutoFormatting(true);
 479     stream.writeStartDocument();
 480
 481     stream.writeStartElement(QStringLiteral("trace"));
 482     stream.writeAttribute(QStringLiteral("version"), QLatin1String(Constants::PROFILER_FILE_VERSION));
 483
 484     stream.writeAttribute(QStringLiteral("traceStart"), QString::number(traceStartTime()));
 485     stream.writeAttribute(QStringLiteral("traceEnd"), QString::number(traceEndTime()));
 486
 487     stream.writeStartElement(QStringLiteral("eventData"));
 488     stream.writeAttribute(QStringLiteral("totalTime"), QString::number(d->qmlMeasuredTime));
 489
 490     foreach (const QmlRangeEventData *eventData, d->eventDescriptions.values()) {
 491         stream.writeStartElement(QStringLiteral("event"));
 492         stream.writeAttribute(QStringLiteral("index"), QString::number(d->eventDescriptions.keys().indexOf(eventData->eventHashStr)));
 493         stream.writeTextElement(QStringLiteral("displayname"), eventData->displayName);
 494         stream.writeTextElement(QStringLiteral("type"), qmlRangeTypeAsString(eventData->eventType));
 495         if (!eventData->location.filename.isEmpty()) {
 496             stream.writeTextElement(QStringLiteral("filename"), eventData->location.filename);
 497             stream.writeTextElement(QStringLiteral("line"), QString::number(eventData->location.line));
 498             stream.writeTextElement(QStringLiteral("column"), QString::number(eventData->location.column));
 499         }
 500         stream.writeTextElement(QStringLiteral("details"), eventData->details);
 501         if (eventData->eventType == QQmlProfilerService::Binding)
 502             stream.writeTextElement(QStringLiteral("bindingType"), QString::number((int)eventData->bindingType));
 503         stream.writeEndElement();
 504     }
 505     stream.writeEndElement(); // eventData
 506
 507     stream.writeStartElement(QStringLiteral("profilerDataModel"));
 508     foreach (const QmlRangeEventStartInstance &rangedEvent, d->startInstanceList) {
 509         stream.writeStartElement(QStringLiteral("range"));
 510         stream.writeAttribute(QStringLiteral("startTime"), QString::number(rangedEvent.startTime));
 511         stream.writeAttribute(QStringLiteral("duration"), QString::number(rangedEvent.duration));
 512         stream.writeAttribute(QStringLiteral("eventIndex"), QString::number(d->eventDescriptions.keys().indexOf(rangedEvent.data->eventHashStr)));
 513         if (rangedEvent.data->eventType == QQmlProfilerService::Painting && rangedEvent.animationCount >= 0) {
 514             // animation frame
 515             stream.writeAttribute(QStringLiteral("framerate"), QString::number(rangedEvent.frameRate));
 516             stream.writeAttribute(QStringLiteral("animationcount"), QString::number(rangedEvent.animationCount));
 517         }
 518         stream.writeEndElement();
 519     }
 520     stream.writeEndElement(); // profilerDataModel
 521
 522     stream.writeStartElement(QStringLiteral("v8profile")); // v8 profiler output
 523     stream.writeAttribute(QStringLiteral("totalTime"), QString::number(d->v8MeasuredTime));
 524     foreach (QV8EventInfo *v8event, d->v8EventHash.values()) {
 525         stream.writeStartElement(QStringLiteral("event"));
 526         stream.writeAttribute(QStringLiteral("index"), QString::number(d->v8EventHash.keys().indexOf(v8event->eventHashStr)));
 527         stream.writeTextElement(QStringLiteral("displayname"), v8event->displayName);
 528         stream.writeTextElement(QStringLiteral("functionname"), v8event->functionName);
 529         if (!v8event->fileName.isEmpty()) {
 530             stream.writeTextElement(QStringLiteral("filename"), v8event->fileName);
 531             stream.writeTextElement(QStringLiteral("line"), QString::number(v8event->line));
 532         }
 533         stream.writeTextElement(QStringLiteral("totalTime"), QString::number(v8event->totalTime));
 534         stream.writeTextElement(QStringLiteral("selfTime"), QString::number(v8event->selfTime));
 535         if (!v8event->v8children.isEmpty()) {
 536             stream.writeStartElement(QStringLiteral("childrenEvents"));
 537             QStringList childrenIndexes;
 538             QStringList childrenTimes;
 539             foreach (const QString &childHash, v8event->v8children.keys()) {
 540                 childrenIndexes << QString::number(v8EventIndex(childHash));
 541                 childrenTimes << QString::number(v8event->v8children[childHash]);
 542             }
 543
 544             stream.writeAttribute(QStringLiteral("list"), childrenIndexes.join(QString(", ")));
 545             stream.writeAttribute(QStringLiteral("childrenTimes"), childrenTimes.join(QString(", ")));
 546             stream.writeEndElement();
 547         }
 548         stream.writeEndElement();
 549     }
 550     stream.writeEndElement(); // v8 profiler output
 551
 552     stream.writeEndElement(); // trace
 553     stream.writeEndDocument();
 554
 555     file.close();
 556     return true;
 557 }
 558
 559 int QmlProfilerData::v8EventIndex(const QString &hashStr)
 560 {
 561     if (!d->v8EventHash.contains(hashStr)) {
 562         emit error("Trying to index nonexisting v8 event");
 563         return -1;
 564     }
 565     return d->v8EventHash.keys().indexOf( hashStr );
 566 }
 567
 568 void QmlProfilerData::setState(QmlProfilerData::State state)
 569 {
 570     // It's not an error, we are continuously calling "AcquiringData" for example
 571     if (d->state == state)
 572         return;
 573
 574     switch (state) {
 575     case Empty:
 576         // if it's not empty, complain but go on
 577         if (!isEmpty())
 578             emit error("Invalid qmlprofiler state change (Empty)");
 579         break;
 580     case AcquiringData:
 581         // we're not supposed to receive new data while processing older data
 582         if (d->state == ProcessingData)
 583             emit error("Invalid qmlprofiler state change (AcquiringData)");
 584         break;
 585     case ProcessingData:
 586         if (d->state != AcquiringData)
 587             emit error("Invalid qmlprofiler state change (ProcessingData)");
 588         break;
 589     case Done:
 590         if (d->state != ProcessingData && d->state != Empty)
 591             emit error("Invalid qmlprofiler state change (Done)");
 592         break;
 593     default:
 594         emit error("Trying to set unknown state in events list");
 595         break;
 596     }
 597
 598     d->state = state;
 599     emit stateChanged();
 600
 601     // special: if we were done with an empty list, clean internal data and go back to empty
 602     if (d->state == Done && isEmpty()) {
 603         clear();
 604     }
 605     return;
 606 }
 607