analysis/org.eclipse.tracecompass.analysis.os.linux.ui/src/org/eclipse/tracecompass/internal/analysis/os/linux/ui/views/controlflow/ControlFlowView.java

   1 /*******************************************************************************
   2  * Copyright (c) 2012, 2016 Ericsson, École Polytechnique de Montréal and others.
   3  *
   4  * All rights reserved. This program and the accompanying materials are
   5  * made available under the terms of the Eclipse Public License v1.0 which
   6  * accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *   Patrick Tasse - Initial API and implementation
  11  *   Geneviève Bastien - Move code to provide base classes for time graph view
  12  *   Christian Mansky - Add check active / uncheck inactive buttons
  13  *   Mahdi Zolnouri & Samuel Gagnon - Add flat / hierarchical button
  14  *******************************************************************************/
  15
  16 package org.eclipse.tracecompass.internal.analysis.os.linux.ui.views.controlflow;
  17
  18 import java.util.ArrayList;
  19 import java.util.Collections;
  20 import java.util.Comparator;
  21 import java.util.HashMap;
  22 import java.util.HashSet;
  23 import java.util.List;
  24 import java.util.Map;
  25 import java.util.Set;
  26 import java.util.function.Predicate;
  27 import java.util.stream.Collectors;
  28 import java.util.stream.Stream;
  29
  30 import org.eclipse.core.runtime.IProgressMonitor;
  31 import org.eclipse.core.runtime.IStatus;
  32 import org.eclipse.core.runtime.Status;
  33 import org.eclipse.core.runtime.jobs.Job;
  34 import org.eclipse.jdt.annotation.NonNull;
  35 import org.eclipse.jdt.annotation.Nullable;
  36 import org.eclipse.jface.action.Action;
  37 import org.eclipse.jface.action.IAction;
  38 import org.eclipse.jface.action.IMenuManager;
  39 import org.eclipse.jface.action.IToolBarManager;
  40 import org.eclipse.jface.action.MenuManager;
  41 import org.eclipse.jface.dialogs.IDialogSettings;
  42 import org.eclipse.jface.viewers.ISelection;
  43 import org.eclipse.jface.viewers.StructuredSelection;
  44 import org.eclipse.swt.widgets.Composite;
  45 import org.eclipse.tracecompass.analysis.os.linux.core.kernel.KernelAnalysisModule;
  46 import org.eclipse.tracecompass.analysis.os.linux.core.kernel.KernelTidAspect;
  47 import org.eclipse.tracecompass.common.core.StreamUtils.StreamFlattener;
  48 import org.eclipse.tracecompass.internal.analysis.os.linux.core.kernel.Attributes;
  49 import org.eclipse.tracecompass.internal.analysis.os.linux.ui.Activator;
  50 import org.eclipse.tracecompass.internal.analysis.os.linux.ui.Messages;
  51 import org.eclipse.tracecompass.internal.analysis.os.linux.ui.actions.FollowThreadAction;
  52 import org.eclipse.tracecompass.statesystem.core.ITmfStateSystem;
  53 import org.eclipse.tracecompass.statesystem.core.exceptions.AttributeNotFoundException;
  54 import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException;
  55 import org.eclipse.tracecompass.statesystem.core.exceptions.StateValueTypeException;
  56 import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException;
  57 import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval;
  58 import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue;
  59 import org.eclipse.tracecompass.tmf.core.event.ITmfEvent;
  60 import org.eclipse.tracecompass.tmf.core.signal.TmfSelectionRangeUpdatedSignal;
  61 import org.eclipse.tracecompass.tmf.core.signal.TmfSignalHandler;
  62 import org.eclipse.tracecompass.tmf.core.signal.TmfSignalManager;
  63 import org.eclipse.tracecompass.tmf.core.signal.TmfTraceSelectedSignal;
  64 import org.eclipse.tracecompass.tmf.core.statesystem.TmfStateSystemAnalysisModule;
  65 import org.eclipse.tracecompass.tmf.core.timestamp.ITmfTimestamp;
  66 import org.eclipse.tracecompass.tmf.core.trace.ITmfContext;
  67 import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace;
  68 import org.eclipse.tracecompass.tmf.core.trace.TmfTraceManager;
  69 import org.eclipse.tracecompass.tmf.core.trace.TmfTraceUtils;
  70 import org.eclipse.tracecompass.tmf.core.util.Pair;
  71 import org.eclipse.tracecompass.tmf.ui.views.timegraph.AbstractStateSystemTimeGraphView;
  72 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ILinkEvent;
  73 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ITimeEvent;
  74 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ITimeGraphEntry;
  75 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.NullTimeEvent;
  76 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.TimeEvent;
  77 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.TimeGraphEntry;
  78 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.TimeLinkEvent;
  79 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.widgets.TimeGraphControl;
  80 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.widgets.Utils;
  81 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.widgets.Utils.Resolution;
  82 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.widgets.Utils.TimeFormat;
  83
  84 import com.google.common.collect.ImmutableList;
  85
  86 /**
  87  * The Control Flow view main object
  88  *
  89  */
  90 public class ControlFlowView extends AbstractStateSystemTimeGraphView {
  91
  92     // ------------------------------------------------------------------------
  93     // Constants
  94     // ------------------------------------------------------------------------
  95     /**
  96      * View ID.
  97      */
  98     public static final String ID = "org.eclipse.tracecompass.analysis.os.linux.views.controlflow"; //$NON-NLS-1$
  99
 100     private static final String PROCESS_COLUMN = Messages.ControlFlowView_processColumn;
 101     private static final String TID_COLUMN = Messages.ControlFlowView_tidColumn;
 102     private static final String PTID_COLUMN = Messages.ControlFlowView_ptidColumn;
 103     private static final String BIRTH_TIME_COLUMN = Messages.ControlFlowView_birthTimeColumn;
 104
 105     private static final String NEXT_EVENT_ICON_PATH = "icons/obj16/shift_r_edit.gif"; //$NON-NLS-1$
 106     private static final String PREV_EVENT_ICON_PATH = "icons/obj16/shift_l_edit.gif"; //$NON-NLS-1$
 107
 108     private static final String[] COLUMN_NAMES = new String[] {
 109             PROCESS_COLUMN,
 110             TID_COLUMN,
 111             PTID_COLUMN,
 112             BIRTH_TIME_COLUMN
 113     };
 114
 115     private static final String[] FILTER_COLUMN_NAMES = new String[] {
 116             PROCESS_COLUMN,
 117             TID_COLUMN
 118     };
 119
 120     // Timeout between updates in the build thread in ms
 121     private static final long BUILD_UPDATE_TIMEOUT = 500;
 122
 123     private static final Comparator<ITimeGraphEntry>[] COLUMN_COMPARATORS;
 124
 125     private static final int INITIAL_SORT_COLUMN_INDEX = 3;
 126
 127     static {
 128         ImmutableList.Builder<Comparator<ITimeGraphEntry>> builder = ImmutableList.builder();
 129         builder.add(ControlFlowColumnComparators.PROCESS_NAME_COLUMN_COMPARATOR)
 130             .add(ControlFlowColumnComparators.TID_COLUMN_COMPARATOR)
 131             .add(ControlFlowColumnComparators.PTID_COLUMN_COMPARATOR)
 132             .add(ControlFlowColumnComparators.BIRTH_TIME_COLUMN_COMPARATOR);
 133         List<Comparator<ITimeGraphEntry>> l = builder.build();
 134         COLUMN_COMPARATORS = l.toArray(new Comparator[l.size()]);
 135     }
 136
 137     private final Set<ITmfTrace> fFlatTraces = new HashSet<>();
 138
 139     private IAction fFlatAction;
 140
 141     private IAction fHierarchicalAction;
 142
 143     // ------------------------------------------------------------------------
 144     // Constructors
 145     // ------------------------------------------------------------------------
 146
 147     /**
 148      * Constructor
 149      */
 150     public ControlFlowView() {
 151         super(ID, new ControlFlowPresentationProvider());
 152         setTreeColumns(COLUMN_NAMES, COLUMN_COMPARATORS, INITIAL_SORT_COLUMN_INDEX);
 153         setTreeLabelProvider(new ControlFlowTreeLabelProvider());
 154         setFilterColumns(FILTER_COLUMN_NAMES);
 155         setFilterLabelProvider(new ControlFlowFilterLabelProvider());
 156         setEntryComparator(ControlFlowColumnComparators.BIRTH_TIME_COLUMN_COMPARATOR);
 157     }
 158
 159     @Override
 160     public void createPartControl(Composite parent) {
 161         super.createPartControl(parent);
 162         // add "Check active" Button to TimeGraphFilterDialog
 163         super.getTimeGraphCombo().addTimeGraphFilterCheckActiveButton(
 164                 new ControlFlowCheckActiveProvider(Messages.ControlFlowView_checkActiveLabel, Messages.ControlFlowView_checkActiveToolTip));
 165         // add "Uncheck inactive" Button to TimeGraphFilterDialog
 166         super.getTimeGraphCombo().addTimeGraphFilterUncheckInactiveButton(
 167                 new ControlFlowCheckActiveProvider(Messages.ControlFlowView_uncheckInactiveLabel, Messages.ControlFlowView_uncheckInactiveToolTip));
 168     }
 169
 170     /**
 171      * @since 2.0
 172      */
 173     @Override
 174     protected void fillTimeGraphEntryContextMenu(@NonNull IMenuManager menuManager) {
 175         ISelection selection = getSite().getSelectionProvider().getSelection();
 176         if (selection instanceof StructuredSelection) {
 177             StructuredSelection sSel = (StructuredSelection) selection;
 178             if (sSel.getFirstElement() instanceof ControlFlowEntry) {
 179                 ControlFlowEntry entry = (ControlFlowEntry) sSel.getFirstElement();
 180                 menuManager.add(new FollowThreadAction(ControlFlowView.this, entry.getName(), entry.getThreadId(), entry.getTrace()));
 181             }
 182         }
 183     }
 184
 185     @Override
 186     protected void fillLocalToolBar(IToolBarManager manager) {
 187         super.fillLocalToolBar(manager);
 188         IDialogSettings settings = Activator.getDefault().getDialogSettings();
 189         IDialogSettings section = settings.getSection(getClass().getName());
 190         if (section == null) {
 191             section = settings.addNewSection(getClass().getName());
 192         }
 193
 194         IAction hideArrowsAction = getTimeGraphCombo().getTimeGraphViewer().getHideArrowsAction(section);
 195         manager.add(hideArrowsAction);
 196
 197         IAction followArrowBwdAction = getTimeGraphCombo().getTimeGraphViewer().getFollowArrowBwdAction();
 198         followArrowBwdAction.setText(Messages.ControlFlowView_followCPUBwdText);
 199         followArrowBwdAction.setToolTipText(Messages.ControlFlowView_followCPUBwdText);
 200         manager.add(followArrowBwdAction);
 201
 202         IAction followArrowFwdAction = getTimeGraphCombo().getTimeGraphViewer().getFollowArrowFwdAction();
 203         followArrowFwdAction.setText(Messages.ControlFlowView_followCPUFwdText);
 204         followArrowFwdAction.setToolTipText(Messages.ControlFlowView_followCPUFwdText);
 205         manager.add(followArrowFwdAction);
 206
 207         IAction previousEventAction = new SearchEventAction(false, PackageMessages.ControlFlowView_PreviousEventJobName);
 208         previousEventAction.setText(PackageMessages.ControlFlowView_PreviousEventActionName);
 209         previousEventAction.setToolTipText(PackageMessages.ControlFlowView_PreviousEventActionTooltip);
 210         previousEventAction.setImageDescriptor(Activator.getDefault().getImageDescripterFromPath(PREV_EVENT_ICON_PATH));
 211         manager.add(previousEventAction);
 212
 213         IAction nextEventAction = new SearchEventAction(true, PackageMessages.ControlFlowView_NextEventJobName);
 214         nextEventAction.setText(PackageMessages.ControlFlowView_NextEventActionName);
 215         nextEventAction.setToolTipText(PackageMessages.ControlFlowView_NextEventActionTooltip);
 216         nextEventAction.setImageDescriptor(Activator.getDefault().getImageDescripterFromPath(NEXT_EVENT_ICON_PATH));
 217         manager.add(nextEventAction);
 218     }
 219
 220     @Override
 221     protected void fillLocalMenu(IMenuManager manager) {
 222         super.fillLocalMenu(manager);
 223         final MenuManager item = new MenuManager(Messages.ControlFlowView_threadPresentation);
 224         fFlatAction = createFlatAction();
 225         item.add(fFlatAction);
 226
 227         fHierarchicalAction = createHierarchicalAction();
 228         item.add(fHierarchicalAction);
 229         manager.add(item);
 230
 231     }
 232
 233     /**
 234      * Base Action for the "Go to Next/Previous Event for thread" actions
 235      */
 236     private class SearchEventAction extends Action {
 237
 238         private final boolean ifDirection;
 239         private final String ifJobName;
 240
 241         /**
 242          * Constructor
 243          *
 244          * @param direction
 245          *            The direction of the search, "true" for forwards and
 246          *            "false" for backwards.
 247          * @param jobName
 248          *            The name of the job that will be spawned
 249          */
 250         public SearchEventAction(boolean direction, String jobName) {
 251             ifDirection = direction;
 252             ifJobName = jobName;
 253         }
 254
 255         @Override
 256         public void run() {
 257             TimeGraphControl ctrl = getTimeGraphViewer().getTimeGraphControl();
 258
 259             ITimeGraphEntry traceEntry = ctrl.getSelectedTrace();
 260             long ts = ctrl.getTimeDataProvider().getSelectionBegin();
 261             ITmfTimestamp ts2 = TmfTraceManager.getInstance().getCurrentTraceContext().getSelectionRange().getStartTime();
 262             ITimeEvent selectedState = Utils.findEvent(traceEntry, ts, 0);
 263
 264             if (selectedState == null) {
 265                 return;
 266             }
 267             ITimeGraphEntry entry = selectedState.getEntry();
 268             if (!(entry instanceof ControlFlowEntry)) {
 269                 return;
 270             }
 271             ControlFlowEntry cfEntry = (ControlFlowEntry) entry;
 272             int tid = cfEntry.getThreadId();
 273
 274             Job job = new Job(ifJobName) {
 275                 @Override
 276                 protected IStatus run(IProgressMonitor monitor) {
 277                     ITmfTrace trace = cfEntry.getTrace();
 278                     ITmfContext ctx = trace.seekEvent(ts2);
 279                     long rank = ctx.getRank();
 280
 281                     Predicate<@NonNull ITmfEvent> predicate = event -> {
 282                         Integer eventTid = KernelTidAspect.INSTANCE.resolve(event);
 283                         return (eventTid != null && eventTid.intValue() == tid);
 284                     };
 285
 286                     ITmfEvent event = (ifDirection ?
 287                             TmfTraceUtils.getNextEventMatching(cfEntry.getTrace(), rank, predicate) :
 288                             TmfTraceUtils.getPreviousEventMatching(cfEntry.getTrace(), rank, predicate));
 289                     if (event != null) {
 290                         TmfSignalManager.dispatchSignal(new TmfSelectionRangeUpdatedSignal(this, event.getTimestamp()));
 291                     }
 292                     return Status.OK_STATUS;
 293                 }
 294             };
 295             job.schedule();
 296         }
 297     }
 298
 299     private IAction createHierarchicalAction() {
 300         IAction action = new Action(Messages.ControlFlowView_hierarchicalViewLabel, IAction.AS_RADIO_BUTTON) {
 301             @Override
 302             public void run() {
 303                 ITmfTrace parentTrace = getTrace();
 304                 synchronized (fFlatTraces) {
 305                     fFlatTraces.remove(parentTrace);
 306                     for (ITmfTrace trace : TmfTraceManager.getTraceSet(parentTrace)) {
 307                         final ITmfStateSystem ss = TmfStateSystemAnalysisModule.getStateSystem(trace, KernelAnalysisModule.ID);
 308                         for (TimeGraphEntry traceEntry : getEntryList(ss)) {
 309                             List<ControlFlowEntry> currentRootList = traceEntry.getChildren().stream()
 310                                     .filter(e -> e instanceof ControlFlowEntry)
 311                                     .map(e -> (ControlFlowEntry) e).collect(Collectors.toList());
 312                             addEntriesToHierarchicalTree(currentRootList, traceEntry);
 313                         }
 314                     }
 315                 }
 316                 refresh();
 317             }
 318         };
 319         action.setChecked(true);
 320         action.setToolTipText(Messages.ControlFlowView_hierarchicalViewToolTip);
 321         return action;
 322     }
 323
 324     private IAction createFlatAction() {
 325         IAction action = new Action(Messages.ControlFlowView_flatViewLabel, IAction.AS_RADIO_BUTTON) {
 326             @Override
 327             public void run() {
 328                 ITmfTrace parentTrace = getTrace();
 329                 synchronized (fFlatTraces) {
 330                     fFlatTraces.add(parentTrace);
 331                     for (ITmfTrace trace : TmfTraceManager.getTraceSet(parentTrace)) {
 332                         final ITmfStateSystem ss = TmfStateSystemAnalysisModule.getStateSystem(trace, KernelAnalysisModule.ID);
 333                         for (TimeGraphEntry traceEntry : getEntryList(ss)) {
 334                             hierarchicalToFlatTree(traceEntry);
 335                         }
 336                     }
 337                 }
 338                 refresh();
 339             }
 340         };
 341         action.setToolTipText(Messages.ControlFlowView_flatViewToolTip);
 342         return action;
 343     }
 344
 345     @Override
 346     protected String getNextText() {
 347         return Messages.ControlFlowView_nextProcessActionNameText;
 348     }
 349
 350     @Override
 351     protected String getNextTooltip() {
 352         return Messages.ControlFlowView_nextProcessActionToolTipText;
 353     }
 354
 355     @Override
 356     protected String getPrevText() {
 357         return Messages.ControlFlowView_previousProcessActionNameText;
 358     }
 359
 360     @Override
 361     protected String getPrevTooltip() {
 362         return Messages.ControlFlowView_previousProcessActionToolTipText;
 363     }
 364
 365     /**
 366      * @author gbastien
 367      *
 368      */
 369     protected static class ControlFlowTreeLabelProvider extends TreeLabelProvider {
 370
 371         @Override
 372         public String getColumnText(Object element, int columnIndex) {
 373             if (element instanceof TraceEntry) {
 374                 if (columnIndex == 0) {
 375                     return ((TraceEntry) element).getName();
 376                 }
 377                 return ""; //$NON-NLS-1$
 378             }
 379             ControlFlowEntry entry = (ControlFlowEntry) element;
 380
 381             if (COLUMN_NAMES[columnIndex].equals(Messages.ControlFlowView_processColumn)) {
 382                 return entry.getName();
 383             } else if (COLUMN_NAMES[columnIndex].equals(Messages.ControlFlowView_tidColumn)) {
 384                 return Integer.toString(entry.getThreadId());
 385             } else if (COLUMN_NAMES[columnIndex].equals(Messages.ControlFlowView_ptidColumn)) {
 386                 if (entry.getParentThreadId() > 0) {
 387                     return Integer.toString(entry.getParentThreadId());
 388                 }
 389             } else if (COLUMN_NAMES[columnIndex].equals(Messages.ControlFlowView_birthTimeColumn)) {
 390                 return Utils.formatTime(entry.getStartTime(), TimeFormat.CALENDAR, Resolution.NANOSEC);
 391             }
 392             return ""; //$NON-NLS-1$
 393         }
 394
 395     }
 396
 397     private static class ControlFlowFilterLabelProvider extends TreeLabelProvider {
 398
 399         @Override
 400         public String getColumnText(Object element, int columnIndex) {
 401             if (element instanceof TraceEntry) {
 402                 if (columnIndex == 0) {
 403                     return ((TraceEntry) element).getName();
 404                 }
 405                 return ""; //$NON-NLS-1$
 406             }
 407             ControlFlowEntry entry = (ControlFlowEntry) element;
 408
 409             if (columnIndex == 0) {
 410                 return entry.getName();
 411             } else if (columnIndex == 1) {
 412                 return Integer.toString(entry.getThreadId());
 413             }
 414             return ""; //$NON-NLS-1$
 415         }
 416
 417     }
 418
 419     private static class TraceEntry extends TimeGraphEntry {
 420
 421         public TraceEntry(String name, long startTime, long endTime) {
 422             super(name, startTime, endTime);
 423         }
 424
 425         @Override
 426         public boolean hasTimeEvents() {
 427             return false;
 428         }
 429     }
 430
 431     @TmfSignalHandler
 432     @Override
 433     public void traceClosed(org.eclipse.tracecompass.tmf.core.signal.TmfTraceClosedSignal signal) {
 434         super.traceClosed(signal);
 435         synchronized (fFlatTraces) {
 436             fFlatTraces.remove(signal.getTrace());
 437         }
 438     }
 439
 440     @TmfSignalHandler
 441     @Override
 442     public void traceSelected(TmfTraceSelectedSignal signal) {
 443         super.traceSelected(signal);
 444         synchronized (fFlatTraces) {
 445             if (fFlatTraces.contains(signal.getTrace())) {
 446                 fHierarchicalAction.setChecked(false);
 447                 fFlatAction.setChecked(true);
 448             } else {
 449                 fFlatAction.setChecked(false);
 450                 fHierarchicalAction.setChecked(true);
 451             }
 452         }
 453     }
 454
 455     // ------------------------------------------------------------------------
 456     // Internal
 457     // ------------------------------------------------------------------------
 458
 459     @Override
 460     protected void buildEntryList(final ITmfTrace trace, final ITmfTrace parentTrace, final IProgressMonitor monitor) {
 461         final ITmfStateSystem ssq = TmfStateSystemAnalysisModule.getStateSystem(trace, KernelAnalysisModule.ID);
 462         if (ssq == null) {
 463             return;
 464         }
 465
 466         final List<ControlFlowEntry> entryList = new ArrayList<>();
 467         /** Map of trace entries */
 468         Map<ITmfTrace, TraceEntry> traceEntryMap = new HashMap<>();
 469         /** Map of control flow entries, key is a pair [threadId, cpuId] */
 470         final Map<Pair<Integer, Integer>, ControlFlowEntry> entryMap = new HashMap<>();
 471
 472         long start = ssq.getStartTime();
 473         setStartTime(Math.min(getStartTime(), start));
 474
 475         boolean complete = false;
 476         while (!complete) {
 477             if (monitor.isCanceled()) {
 478                 return;
 479             }
 480             complete = ssq.waitUntilBuilt(BUILD_UPDATE_TIMEOUT);
 481             if (ssq.isCancelled()) {
 482                 return;
 483             }
 484             long end = ssq.getCurrentEndTime();
 485             if (start == end && !complete) { // when complete execute one last time regardless of end time
 486                 continue;
 487             }
 488
 489             TraceEntry aTraceEntry = traceEntryMap.get(trace);
 490             if (aTraceEntry == null) {
 491                 aTraceEntry = new TraceEntry(trace.getName(), start, end + 1);
 492                 traceEntryMap.put(trace, aTraceEntry);
 493                 addToEntryList(parentTrace, ssq, Collections.singletonList(aTraceEntry));
 494             } else {
 495                 aTraceEntry.updateEndTime(end + 1);
 496             }
 497             final TraceEntry traceEntry = aTraceEntry;
 498
 499             final long resolution = Math.max(1, (end - ssq.getStartTime()) / getDisplayWidth());
 500             setEndTime(Math.max(getEndTime(), end + 1));
 501             final List<Integer> threadQuarks = ssq.getQuarks(Attributes.THREADS, "*"); //$NON-NLS-1$
 502             queryFullStates(ssq, start, end, resolution, monitor, new IQueryHandler() {
 503                 @Override
 504                 public void handle(List<List<ITmfStateInterval>> fullStates, List<ITmfStateInterval> prevFullState) {
 505                     for (int threadQuark : threadQuarks) {
 506                         String threadAttributeName = ssq.getAttributeName(threadQuark);
 507
 508                         Pair<Integer, Integer> entryKey = Attributes.parseThreadAttributeName(threadAttributeName);
 509                         int threadId = entryKey.getFirst();
 510
 511                         if (threadId < 0) { // ignore the 'unknown' (-1) thread
 512                             continue;
 513                         }
 514
 515                         int execNameQuark;
 516                         int ppidQuark;
 517                         try {
 518                             execNameQuark = ssq.getQuarkRelative(threadQuark, Attributes.EXEC_NAME);
 519                             ppidQuark = ssq.getQuarkRelative(threadQuark, Attributes.PPID);
 520                         } catch (AttributeNotFoundException e) {
 521                             /* No information on this thread (yet?), skip it for now */
 522                             continue;
 523                         }
 524                         ITmfStateInterval lastExecNameInterval = prevFullState == null || execNameQuark >= prevFullState.size() ? null : prevFullState.get(execNameQuark);
 525                         long lastExecNameStartTime = lastExecNameInterval == null ? -1 : lastExecNameInterval.getStartTime();
 526                         long lastExecNameEndTime = lastExecNameInterval == null ? -1 : lastExecNameInterval.getEndTime() + 1;
 527                         long lastPpidStartTime = prevFullState == null || ppidQuark >= prevFullState.size() ? -1 : prevFullState.get(ppidQuark).getStartTime();
 528                         for (List<ITmfStateInterval> fullState : fullStates) {
 529                             if (monitor.isCanceled()) {
 530                                 return;
 531                             }
 532                             if (execNameQuark >= fullState.size() || ppidQuark >= fullState.size()) {
 533                                 /* No information on this thread (yet?), skip it for now */
 534                                 continue;
 535                             }
 536                             ITmfStateInterval execNameInterval = fullState.get(execNameQuark);
 537                             ITmfStateInterval ppidInterval = fullState.get(ppidQuark);
 538                             long startTime = execNameInterval.getStartTime();
 539                             long endTime = execNameInterval.getEndTime() + 1;
 540                             if (startTime == lastExecNameStartTime && ppidInterval.getStartTime() == lastPpidStartTime) {
 541                                 continue;
 542                             }
 543                             boolean isNull = execNameInterval.getStateValue().isNull();
 544                             if (isNull && lastExecNameEndTime < startTime && lastExecNameEndTime != -1) {
 545                                 /*
 546                                  * There was a non-null interval in between the
 547                                  * full states, try to use it.
 548                                  */
 549                                 try {
 550                                     execNameInterval = ssq.querySingleState(startTime - 1, execNameQuark);
 551                                     ppidInterval = ssq.querySingleState(startTime - 1, ppidQuark);
 552                                     startTime = execNameInterval.getStartTime();
 553                                     endTime = execNameInterval.getEndTime() + 1;
 554                                 } catch (StateSystemDisposedException e) {
 555                                     /* ignored */
 556                                 }
 557                             }
 558                             if (!execNameInterval.getStateValue().isNull() &&
 559                                     execNameInterval.getStateValue().getType() == ITmfStateValue.Type.STRING) {
 560                                 String execName = execNameInterval.getStateValue().unboxStr();
 561                                 int ppid = ppidInterval.getStateValue().unboxInt();
 562                                 ControlFlowEntry entry = entryMap.get(entryKey);
 563                                 if (entry == null) {
 564                                     entry = new ControlFlowEntry(threadQuark, trace, execName, threadId, ppid, startTime, endTime);
 565                                     entryList.add(entry);
 566                                     entryMap.put(entryKey, entry);
 567                                 } else {
 568                                     /*
 569                                      * Update the name of the entry to the
 570                                      * latest execName and the parent thread id
 571                                      * to the latest ppid.
 572                                      */
 573                                     entry.setName(execName);
 574                                     entry.setParentThreadId(ppid);
 575                                     entry.updateEndTime(endTime);
 576                                 }
 577                             }
 578                             if (isNull) {
 579                                 entryMap.remove(entryKey);
 580                             }
 581                             lastExecNameStartTime = startTime;
 582                             lastExecNameEndTime = endTime;
 583                             lastPpidStartTime = ppidInterval.getStartTime();
 584                         }
 585                     }
 586                     synchronized (fFlatTraces) {
 587                         if (fFlatTraces.contains(parentTrace)) {
 588                             addEntriesToFlatTree(entryList, traceEntry);
 589                         } else {
 590                             addEntriesToHierarchicalTree(entryList, traceEntry);
 591                         }
 592                     }
 593                 }
 594             });
 595
 596             queryFullStates(ssq, ssq.getStartTime(), end, resolution, monitor, new IQueryHandler() {
 597                 @Override
 598                 public void handle(@NonNull List<List<ITmfStateInterval>> fullStates, @Nullable List<ITmfStateInterval> prevFullState) {
 599                     for (final TimeGraphEntry entry : traceEntry.getChildren()) {
 600                         if (monitor.isCanceled()) {
 601                             return;
 602                         }
 603                         buildStatusEvents(trace, parentTrace, ssq, fullStates, prevFullState, (ControlFlowEntry) entry, monitor, ssq.getStartTime(), end);
 604                     }
 605                 }
 606             });
 607
 608             if (parentTrace.equals(getTrace())) {
 609                 refresh();
 610             }
 611
 612             start = end;
 613         }
 614     }
 615
 616     /**
 617      * Add entries to the traces's child list in a flat fashion (no hierarchy).
 618      * If one entry has children, we do a depth first search to add each child
 619      * to the trace's child list and update the parent and child relations.
 620      */
 621     private static void hierarchicalToFlatTree(TimeGraphEntry traceEntry) {
 622         List<@NonNull TimeGraphEntry> rootList = traceEntry.getChildren();
 623         // We visit the children of every entry to add
 624         StreamFlattener<TimeGraphEntry> sf = new StreamFlattener<>(entry -> entry.getChildren().stream());
 625         Stream<TimeGraphEntry> allEntries = rootList.stream().flatMap(entry -> sf.flatten(entry));
 626
 627         // We add every entry that is missing from the trace's entry list
 628         List<@NonNull TimeGraphEntry> rootListToAdd = allEntries
 629                 .filter(entry -> !rootList.contains(entry))
 630                 .collect(Collectors.toList());
 631         rootList.forEach(entry -> {
 632             entry.clearChildren();
 633         });
 634         rootListToAdd.forEach(entry -> {
 635             traceEntry.addChild(entry);
 636             entry.clearChildren();
 637         });
 638     }
 639
 640     /**
 641      * Add entries to the traces's child list in a flat fashion (no hierarchy).
 642      */
 643     private static void addEntriesToFlatTree(List<@NonNull ControlFlowEntry> entryList, TimeGraphEntry traceEntry) {
 644         List<TimeGraphEntry> rootList = traceEntry.getChildren();
 645         for (ControlFlowEntry entry : entryList) {
 646             if (!rootList.contains(entry)) {
 647                 traceEntry.addChild(entry);
 648             }
 649         }
 650     }
 651
 652     /**
 653      * Add entries to the trace's child list in a hierarchical fashion.
 654      */
 655     private static void addEntriesToHierarchicalTree(List<ControlFlowEntry> entryList, TimeGraphEntry traceEntry) {
 656         List<TimeGraphEntry> rootList = traceEntry.getChildren();
 657
 658         for (ControlFlowEntry entry : entryList) {
 659             boolean root = (entry.getParent() == null || entry.getParent() == traceEntry);
 660             if (root && entry.getParentThreadId() > 0) {
 661                 for (ControlFlowEntry parent : entryList) {
 662                     /*
 663                      * Associate the parent entry only if their time overlap. A
 664                      * child entry may start before its parent, for example at
 665                      * the beginning of the trace if a parent has not yet
 666                      * appeared in the state system. We just want to make sure
 667                      * that the entry didn't start after the parent ended or
 668                      * ended before the parent started.
 669                      */
 670                     if (parent.getThreadId() == entry.getParentThreadId() &&
 671                             !(entry.getStartTime() > parent.getEndTime() ||
 672                             entry.getEndTime() < parent.getStartTime())) {
 673                         parent.addChild(entry);
 674                         root = false;
 675                         if (rootList.contains(entry)) {
 676                             traceEntry.removeChild(entry);
 677                         }
 678                         break;
 679                     }
 680                 }
 681             }
 682             if (root && (!rootList.contains(entry))) {
 683                 traceEntry.addChild(entry);
 684             }
 685         }
 686     }
 687
 688     private void buildStatusEvents(ITmfTrace trace, ITmfTrace parentTrace, ITmfStateSystem ss, @NonNull List<List<ITmfStateInterval>> fullStates,
 689             @Nullable List<ITmfStateInterval> prevFullState, ControlFlowEntry entry, @NonNull IProgressMonitor monitor, long start, long end) {
 690         if (start < entry.getEndTime() && end > entry.getStartTime()) {
 691             List<ITimeEvent> eventList = getEventList(entry, ss, fullStates, prevFullState, monitor);
 692             if (eventList == null) {
 693                 return;
 694             }
 695             /* Start a new event list on first iteration, then append to it */
 696             if (prevFullState == null) {
 697                 entry.setEventList(eventList);
 698             } else {
 699                 for (ITimeEvent event : eventList) {
 700                     entry.addEvent(event);
 701                 }
 702             }
 703             if (parentTrace.equals(getTrace())) {
 704                 redraw();
 705             }
 706         }
 707         for (ITimeGraphEntry child : entry.getChildren()) {
 708             if (monitor.isCanceled()) {
 709                 return;
 710             }
 711             buildStatusEvents(trace, parentTrace, ss, fullStates, prevFullState, (ControlFlowEntry) child, monitor, start, end);
 712         }
 713     }
 714
 715     @Override
 716     protected @Nullable List<ITimeEvent> getEventList(@NonNull TimeGraphEntry tgentry, ITmfStateSystem ss,
 717             @NonNull List<List<ITmfStateInterval>> fullStates, @Nullable List<ITmfStateInterval> prevFullState, @NonNull IProgressMonitor monitor) {
 718         List<ITimeEvent> eventList = null;
 719         if (!(tgentry instanceof ControlFlowEntry)) {
 720             return eventList;
 721         }
 722         ControlFlowEntry entry = (ControlFlowEntry) tgentry;
 723         try {
 724             int threadQuark = entry.getThreadQuark();
 725             int statusQuark = ss.getQuarkRelative(threadQuark, Attributes.STATUS);
 726             eventList = new ArrayList<>(fullStates.size());
 727             ITmfStateInterval lastInterval = prevFullState == null || statusQuark >= prevFullState.size() ? null : prevFullState.get(statusQuark);
 728             long lastStartTime = lastInterval == null ? -1 : lastInterval.getStartTime();
 729             long lastEndTime = lastInterval == null ? -1 : lastInterval.getEndTime() + 1;
 730             for (List<ITmfStateInterval> fullState : fullStates) {
 731                 if (monitor.isCanceled()) {
 732                     return null;
 733                 }
 734                 if (statusQuark >= fullState.size()) {
 735                     /* No information on this thread (yet?), skip it for now */
 736                     continue;
 737                 }
 738                 ITmfStateInterval statusInterval = fullState.get(statusQuark);
 739                 long time = statusInterval.getStartTime();
 740                 if (time == lastStartTime) {
 741                     continue;
 742                 }
 743                 long duration = statusInterval.getEndTime() - time + 1;
 744                 int status = -1;
 745                 try {
 746                     status = statusInterval.getStateValue().unboxInt();
 747                 } catch (StateValueTypeException e) {
 748                     Activator.getDefault().logError(e.getMessage());
 749                 }
 750                 if (lastEndTime != time && lastEndTime != -1) {
 751                     eventList.add(new TimeEvent(entry, lastEndTime, time - lastEndTime));
 752                 }
 753                 if (!statusInterval.getStateValue().isNull()) {
 754                     eventList.add(new TimeEvent(entry, time, duration, status));
 755                 } else {
 756                     eventList.add(new NullTimeEvent(entry, time, duration));
 757                 }
 758                 lastStartTime = time;
 759                 lastEndTime = time + duration;
 760             }
 761         } catch (AttributeNotFoundException | TimeRangeException e) {
 762             Activator.getDefault().logError(e.getMessage());
 763         }
 764         return eventList;
 765     }
 766
 767     /**
 768      * Returns a value corresponding to the selected entry.
 769      *
 770      * Used in conjunction with synchingToTime to change the selected entry. If
 771      * one of these methods is overridden in child class, then both should be.
 772      *
 773      * @param time
 774      *            The currently selected time
 775      * @return a value identifying the entry
 776      */
 777     private int getSelectionValue(long time) {
 778         int thread = -1;
 779         for (ITmfTrace trace : TmfTraceManager.getTraceSet(getTrace())) {
 780             if (thread > 0) {
 781                 break;
 782             }
 783             ITmfStateSystem ssq = TmfStateSystemAnalysisModule.getStateSystem(trace, KernelAnalysisModule.ID);
 784             if (ssq == null) {
 785                 continue;
 786             }
 787             if (time >= ssq.getStartTime() && time <= ssq.getCurrentEndTime()) {
 788                 List<Integer> currentThreadQuarks = ssq.getQuarks(Attributes.CPUS, "*", Attributes.CURRENT_THREAD); //$NON-NLS-1$
 789                 for (int currentThreadQuark : currentThreadQuarks) {
 790                     try {
 791                         ITmfStateInterval currentThreadInterval = ssq.querySingleState(time, currentThreadQuark);
 792                         int currentThread = currentThreadInterval.getStateValue().unboxInt();
 793                         if (currentThread > 0) {
 794                             int statusQuark = ssq.getQuarkAbsolute(Attributes.THREADS, Integer.toString(currentThread), Attributes.STATUS);
 795                             ITmfStateInterval statusInterval = ssq.querySingleState(time, statusQuark);
 796                             if (statusInterval.getStartTime() == time) {
 797                                 thread = currentThread;
 798                                 break;
 799                             }
 800                         }
 801                     } catch (AttributeNotFoundException | TimeRangeException | StateValueTypeException e) {
 802                         Activator.getDefault().logError(e.getMessage());
 803                     } catch (StateSystemDisposedException e) {
 804                         /* Ignored */
 805                     }
 806                 }
 807             }
 808         }
 809         return thread;
 810     }
 811
 812     @Override
 813     protected void synchingToTime(long time) {
 814         int selected = getSelectionValue(time);
 815         if (selected > 0) {
 816             for (Object element : getTimeGraphViewer().getExpandedElements()) {
 817                 if (element instanceof ControlFlowEntry) {
 818                     ControlFlowEntry entry = (ControlFlowEntry) element;
 819                     if (entry.getThreadId() == selected) {
 820                         getTimeGraphCombo().setSelection(entry);
 821                         break;
 822                     }
 823                 }
 824             }
 825         }
 826     }
 827
 828     @Override
 829     protected @NonNull List<ILinkEvent> getLinkList(ITmfStateSystem ss,
 830             @NonNull List<List<ITmfStateInterval>> fullStates, @Nullable List<ITmfStateInterval> prevFullState, @NonNull IProgressMonitor monitor) {
 831         List<ILinkEvent> list = new ArrayList<>();
 832         List<TimeGraphEntry> entryList = getEntryList(ss);
 833         if (entryList == null) {
 834             return list;
 835         }
 836         for (ITmfTrace trace : TmfTraceManager.getTraceSet(getTrace())) {
 837             List<Integer> currentThreadQuarks = ss.getQuarks(Attributes.CPUS, "*", Attributes.CURRENT_THREAD); //$NON-NLS-1$
 838             for (int currentThreadQuark : currentThreadQuarks) {
 839                 if (currentThreadQuark >= fullStates.get(0).size()) {
 840                     /* No information on this cpu (yet?), skip it for now */
 841                     continue;
 842                 }
 843                 List<ITmfStateInterval> currentThreadIntervals = new ArrayList<>(fullStates.size() + 2);
 844                 try {
 845                     /*
 846                      * Add the previous interval if it is the first query
 847                      * iteration and the first interval has currentThread=0. Add
 848                      * the following interval if the last interval has
 849                      * currentThread=0. These are diagonal arrows crossing the
 850                      * query iteration range.
 851                      */
 852                     if (prevFullState == null) {
 853                         ITmfStateInterval currentThreadInterval = fullStates.get(0).get(currentThreadQuark);
 854                         if (currentThreadInterval.getStateValue().unboxInt() == 0) {
 855                             long start = Math.max(currentThreadInterval.getStartTime() - 1, ss.getStartTime());
 856                             currentThreadIntervals.add(ss.querySingleState(start, currentThreadQuark));
 857                         }
 858                     }
 859                     for (List<ITmfStateInterval> fullState : fullStates) {
 860                         currentThreadIntervals.add(fullState.get(currentThreadQuark));
 861                     }
 862                     ITmfStateInterval currentThreadInterval = fullStates.get(fullStates.size() - 1).get(currentThreadQuark);
 863                     if (currentThreadInterval.getStateValue().unboxInt() == 0) {
 864                         long end = Math.min(currentThreadInterval.getEndTime() + 1, ss.getCurrentEndTime());
 865                         currentThreadIntervals.add(ss.querySingleState(end, currentThreadQuark));
 866                     }
 867                 } catch (StateSystemDisposedException e) {
 868                     /* Ignored */
 869                     return list;
 870                 }
 871                 int prevThread = 0;
 872                 long prevEnd = 0;
 873                 long lastEnd = 0;
 874                 for (ITmfStateInterval currentThreadInterval : currentThreadIntervals) {
 875                     if (monitor.isCanceled()) {
 876                         return list;
 877                     }
 878                     if (currentThreadInterval.getEndTime() + 1 == lastEnd) {
 879                         continue;
 880                     }
 881                     long time = currentThreadInterval.getStartTime();
 882                     if (time != lastEnd) {
 883                         // don't create links where there are gaps in intervals due to the resolution
 884                         prevThread = 0;
 885                         prevEnd = 0;
 886                     }
 887                     int thread = currentThreadInterval.getStateValue().unboxInt();
 888                     if (thread > 0 && prevThread > 0) {
 889                         ITimeGraphEntry prevEntry = findEntry(entryList, trace, prevThread);
 890                         ITimeGraphEntry nextEntry = findEntry(entryList, trace, thread);
 891                         list.add(new TimeLinkEvent(prevEntry, nextEntry, prevEnd, time - prevEnd, 0));
 892                     }
 893                     lastEnd = currentThreadInterval.getEndTime() + 1;
 894                     if (thread != 0) {
 895                         prevThread = thread;
 896                         prevEnd = lastEnd;
 897                     }
 898                 }
 899             }
 900         }
 901         return list;
 902     }
 903
 904     private ControlFlowEntry findEntry(List<TimeGraphEntry> entryList, ITmfTrace trace, int threadId) {
 905         for (TimeGraphEntry entry : entryList) {
 906             if (entry instanceof ControlFlowEntry) {
 907                 ControlFlowEntry controlFlowEntry = (ControlFlowEntry) entry;
 908                 if (controlFlowEntry.getThreadId() == threadId && controlFlowEntry.getTrace() == trace) {
 909                     return controlFlowEntry;
 910                 }
 911             }
 912             if (entry.hasChildren()) {
 913                 ControlFlowEntry controlFlowEntry = findEntry(entry.getChildren(), trace, threadId);
 914                 if (controlFlowEntry != null) {
 915                     return controlFlowEntry;
 916                 }
 917             }
 918         }
 919         return null;
 920     }
 921 }