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.Collection;
  20 import java.util.Collections;
  21 import java.util.Comparator;
  22 import java.util.HashMap;
  23 import java.util.HashSet;
  24 import java.util.LinkedHashMap;
  25 import java.util.List;
  26 import java.util.Map;
  27 import java.util.Set;
  28 import java.util.function.Function;
  29 import java.util.function.Predicate;
  30 import java.util.stream.Collectors;
  31 import java.util.stream.Stream;
  32
  33 import org.eclipse.core.runtime.IProgressMonitor;
  34 import org.eclipse.core.runtime.IStatus;
  35 import org.eclipse.core.runtime.Status;
  36 import org.eclipse.core.runtime.jobs.ISchedulingRule;
  37 import org.eclipse.core.runtime.jobs.Job;
  38 import org.eclipse.jdt.annotation.NonNull;
  39 import org.eclipse.jdt.annotation.Nullable;
  40 import org.eclipse.jface.action.Action;
  41 import org.eclipse.jface.action.IAction;
  42 import org.eclipse.jface.action.IMenuManager;
  43 import org.eclipse.jface.action.IToolBarManager;
  44 import org.eclipse.jface.action.MenuManager;
  45 import org.eclipse.jface.action.Separator;
  46 import org.eclipse.jface.dialogs.IDialogSettings;
  47 import org.eclipse.jface.viewers.ISelection;
  48 import org.eclipse.jface.viewers.StructuredSelection;
  49 import org.eclipse.swt.widgets.Composite;
  50 import org.eclipse.swt.widgets.Event;
  51 import org.eclipse.tracecompass.analysis.os.linux.core.kernel.KernelAnalysisModule;
  52 import org.eclipse.tracecompass.analysis.os.linux.core.kernel.KernelTidAspect;
  53 import org.eclipse.tracecompass.common.core.StreamUtils.StreamFlattener;
  54 import org.eclipse.tracecompass.internal.analysis.os.linux.core.kernel.Attributes;
  55 import org.eclipse.tracecompass.internal.analysis.os.linux.ui.Activator;
  56 import org.eclipse.tracecompass.internal.analysis.os.linux.ui.Messages;
  57 import org.eclipse.tracecompass.internal.analysis.os.linux.ui.actions.FollowThreadAction;
  58 import org.eclipse.tracecompass.statesystem.core.ITmfStateSystem;
  59 import org.eclipse.tracecompass.statesystem.core.exceptions.AttributeNotFoundException;
  60 import org.eclipse.tracecompass.statesystem.core.exceptions.StateSystemDisposedException;
  61 import org.eclipse.tracecompass.statesystem.core.exceptions.StateValueTypeException;
  62 import org.eclipse.tracecompass.statesystem.core.exceptions.TimeRangeException;
  63 import org.eclipse.tracecompass.statesystem.core.interval.ITmfStateInterval;
  64 import org.eclipse.tracecompass.statesystem.core.statevalue.ITmfStateValue;
  65 import org.eclipse.tracecompass.tmf.core.event.ITmfEvent;
  66 import org.eclipse.tracecompass.tmf.core.signal.TmfSelectionRangeUpdatedSignal;
  67 import org.eclipse.tracecompass.tmf.core.signal.TmfSignalHandler;
  68 import org.eclipse.tracecompass.tmf.core.signal.TmfSignalManager;
  69 import org.eclipse.tracecompass.tmf.core.signal.TmfTraceSelectedSignal;
  70 import org.eclipse.tracecompass.tmf.core.statesystem.TmfStateSystemAnalysisModule;
  71 import org.eclipse.tracecompass.tmf.core.timestamp.TmfTimestamp;
  72 import org.eclipse.tracecompass.tmf.core.trace.ITmfContext;
  73 import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace;
  74 import org.eclipse.tracecompass.tmf.core.trace.TmfTraceManager;
  75 import org.eclipse.tracecompass.tmf.core.trace.TmfTraceUtils;
  76 import org.eclipse.tracecompass.tmf.core.util.Pair;
  77 import org.eclipse.tracecompass.tmf.ui.views.timegraph.AbstractStateSystemTimeGraphView;
  78 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ILinkEvent;
  79 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ITimeEvent;
  80 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ITimeGraphEntry;
  81 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.NullTimeEvent;
  82 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.TimeEvent;
  83 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.TimeGraphEntry;
  84 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.TimeLinkEvent;
  85 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.widgets.TimeGraphControl;
  86 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.widgets.Utils;
  87 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.widgets.Utils.Resolution;
  88 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.widgets.Utils.TimeFormat;
  89
  90 import com.google.common.collect.HashMultiset;
  91 import com.google.common.collect.ImmutableList;
  92 import com.google.common.collect.Multiset;
  93 import com.google.common.collect.Multisets;
  94
  95 /**
  96  * The Control Flow view main object
  97  *
  98  */
  99 public class ControlFlowView extends AbstractStateSystemTimeGraphView {
 100
 101     // ------------------------------------------------------------------------
 102     // Constants
 103     // ------------------------------------------------------------------------
 104     /**
 105      * View ID.
 106      */
 107     public static final String ID = "org.eclipse.tracecompass.analysis.os.linux.views.controlflow"; //$NON-NLS-1$
 108
 109     private static final String ICONS_PATH = "icons/"; //$NON-NLS-1$
 110     private static final String OPTIMIZE_ICON = ICONS_PATH + "elcl16/Optimization.png"; //$NON-NLS-1$
 111
 112     private static final String PROCESS_COLUMN = Messages.ControlFlowView_processColumn;
 113     private static final String TID_COLUMN = Messages.ControlFlowView_tidColumn;
 114     private static final String PTID_COLUMN = Messages.ControlFlowView_ptidColumn;
 115     private static final String BIRTH_TIME_COLUMN = Messages.ControlFlowView_birthTimeColumn;
 116     private static final String INVISIBLE_COLUMN = Messages.ControlFlowView_invisibleColumn;
 117     private Action fOptimizationAction;
 118
 119     private static final String NEXT_EVENT_ICON_PATH = "icons/elcl16/shift_r_edit.gif"; //$NON-NLS-1$
 120     private static final String PREV_EVENT_ICON_PATH = "icons/elcl16/shift_l_edit.gif"; //$NON-NLS-1$
 121
 122     private static final String[] COLUMN_NAMES = new String[] {
 123             PROCESS_COLUMN,
 124             TID_COLUMN,
 125             PTID_COLUMN,
 126             BIRTH_TIME_COLUMN
 127     };
 128
 129     private static final String[] FILTER_COLUMN_NAMES = new String[] {
 130             PROCESS_COLUMN,
 131             TID_COLUMN
 132     };
 133
 134     // Timeout between updates in the build thread in ms
 135     private static final long BUILD_UPDATE_TIMEOUT = 500;
 136
 137     private static final Comparator<ITimeGraphEntry>[] COLUMN_COMPARATORS;
 138
 139     private final Function<Collection<ILinkEvent>, Map<Integer, Long>> UPDATE_SCHEDULING_COLUMN_ALGO = new OptimizationAlgorithm();
 140
 141     private static final int INITIAL_SORT_COLUMN_INDEX = 3;
 142
 143     static {
 144         ImmutableList.Builder<Comparator<ITimeGraphEntry>> builder = ImmutableList.builder();
 145         builder.add(ControlFlowColumnComparators.PROCESS_NAME_COLUMN_COMPARATOR)
 146             .add(ControlFlowColumnComparators.TID_COLUMN_COMPARATOR)
 147             .add(ControlFlowColumnComparators.PTID_COLUMN_COMPARATOR)
 148             .add(ControlFlowColumnComparators.BIRTH_TIME_COLUMN_COMPARATOR);
 149         List<Comparator<ITimeGraphEntry>> l = builder.build();
 150         COLUMN_COMPARATORS = l.toArray(new Comparator[l.size()]);
 151     }
 152
 153     /**
 154      * Mutex rule for search action jobs, making sure they execute sequentially
 155      */
 156     private final ISchedulingRule fSearchActionMutexRule = new ISchedulingRule() {
 157         @Override
 158         public boolean isConflicting(ISchedulingRule rule) {
 159             return (rule == this);
 160         }
 161
 162         @Override
 163         public boolean contains(ISchedulingRule rule) {
 164             return (rule == this);
 165         }
 166     };
 167
 168     private final Set<ITmfTrace> fFlatTraces = new HashSet<>();
 169
 170     private IAction fFlatAction;
 171
 172     private IAction fHierarchicalAction;
 173
 174     // ------------------------------------------------------------------------
 175     // Constructors
 176     // ------------------------------------------------------------------------
 177
 178     /**
 179      * Constructor
 180      */
 181     public ControlFlowView() {
 182         super(ID, new ControlFlowPresentationProvider());
 183         setTreeColumns(COLUMN_NAMES, COLUMN_COMPARATORS, INITIAL_SORT_COLUMN_INDEX);
 184         setTreeLabelProvider(new ControlFlowTreeLabelProvider());
 185         setFilterColumns(FILTER_COLUMN_NAMES);
 186         setFilterLabelProvider(new ControlFlowFilterLabelProvider());
 187         setEntryComparator(ControlFlowColumnComparators.BIRTH_TIME_COLUMN_COMPARATOR);
 188     }
 189
 190     @Override
 191     public void createPartControl(Composite parent) {
 192         super.createPartControl(parent);
 193         // add "Check active" Button to TimeGraphFilterDialog
 194         super.getTimeGraphCombo().addTimeGraphFilterCheckActiveButton(
 195                 new ControlFlowCheckActiveProvider(Messages.ControlFlowView_checkActiveLabel, Messages.ControlFlowView_checkActiveToolTip));
 196         // add "Uncheck inactive" Button to TimeGraphFilterDialog
 197         super.getTimeGraphCombo().addTimeGraphFilterUncheckInactiveButton(
 198                 new ControlFlowCheckActiveProvider(Messages.ControlFlowView_uncheckInactiveLabel, Messages.ControlFlowView_uncheckInactiveToolTip));
 199     }
 200
 201     /**
 202      * @since 2.0
 203      */
 204     @Override
 205     protected void fillTimeGraphEntryContextMenu(@NonNull IMenuManager menuManager) {
 206         ISelection selection = getSite().getSelectionProvider().getSelection();
 207         if (selection instanceof StructuredSelection) {
 208             StructuredSelection sSel = (StructuredSelection) selection;
 209             if (sSel.getFirstElement() instanceof ControlFlowEntry) {
 210                 ControlFlowEntry entry = (ControlFlowEntry) sSel.getFirstElement();
 211                 menuManager.add(new FollowThreadAction(ControlFlowView.this, entry.getName(), entry.getThreadId(), entry.getTrace()));
 212             }
 213         }
 214     }
 215
 216     @Override
 217     protected void fillLocalToolBar(IToolBarManager manager) {
 218         // add "Optimization" Button to local tool bar of Controlflow
 219         IAction optimizationAction = getOptimizationAction();
 220         manager.add(optimizationAction);
 221
 222         // add a separator to local tool bar
 223         manager.add(new Separator());
 224
 225         super.fillLocalToolBar(manager);
 226         IDialogSettings settings = Activator.getDefault().getDialogSettings();
 227         IDialogSettings section = settings.getSection(getClass().getName());
 228         if (section == null) {
 229             section = settings.addNewSection(getClass().getName());
 230         }
 231
 232         IAction hideArrowsAction = getTimeGraphCombo().getTimeGraphViewer().getHideArrowsAction(section);
 233         manager.add(hideArrowsAction);
 234
 235         IAction followArrowBwdAction = getTimeGraphCombo().getTimeGraphViewer().getFollowArrowBwdAction();
 236         followArrowBwdAction.setText(Messages.ControlFlowView_followCPUBwdText);
 237         followArrowBwdAction.setToolTipText(Messages.ControlFlowView_followCPUBwdText);
 238         manager.add(followArrowBwdAction);
 239
 240         IAction followArrowFwdAction = getTimeGraphCombo().getTimeGraphViewer().getFollowArrowFwdAction();
 241         followArrowFwdAction.setText(Messages.ControlFlowView_followCPUFwdText);
 242         followArrowFwdAction.setToolTipText(Messages.ControlFlowView_followCPUFwdText);
 243         manager.add(followArrowFwdAction);
 244
 245         IAction previousEventAction = new SearchEventAction(false, PackageMessages.ControlFlowView_PreviousEventJobName);
 246         previousEventAction.setText(PackageMessages.ControlFlowView_PreviousEventActionName);
 247         previousEventAction.setToolTipText(PackageMessages.ControlFlowView_PreviousEventActionTooltip);
 248         previousEventAction.setImageDescriptor(Activator.getDefault().getImageDescripterFromPath(PREV_EVENT_ICON_PATH));
 249         manager.add(previousEventAction);
 250
 251         IAction nextEventAction = new SearchEventAction(true, PackageMessages.ControlFlowView_NextEventJobName);
 252         nextEventAction.setText(PackageMessages.ControlFlowView_NextEventActionName);
 253         nextEventAction.setToolTipText(PackageMessages.ControlFlowView_NextEventActionTooltip);
 254         nextEventAction.setImageDescriptor(Activator.getDefault().getImageDescripterFromPath(NEXT_EVENT_ICON_PATH));
 255         manager.add(nextEventAction);
 256     }
 257
 258     private IAction getOptimizationAction() {
 259         if (fOptimizationAction == null) {
 260             fOptimizationAction = new OptimizationAction();
 261             fOptimizationAction.setImageDescriptor(Activator.getDefault().getImageDescripterFromPath(OPTIMIZE_ICON));
 262             fOptimizationAction.setText(Messages.ControlFlowView_optimizeLabel);
 263             fOptimizationAction.setToolTipText(Messages.ControlFlowView_optimizeToolTip);
 264         }
 265         return fOptimizationAction;
 266     }
 267
 268     @Override
 269     protected void fillLocalMenu(IMenuManager manager) {
 270         super.fillLocalMenu(manager);
 271         final MenuManager item = new MenuManager(Messages.ControlFlowView_threadPresentation);
 272         fFlatAction = createFlatAction();
 273         item.add(fFlatAction);
 274
 275         fHierarchicalAction = createHierarchicalAction();
 276         item.add(fHierarchicalAction);
 277         manager.add(item);
 278
 279     }
 280
 281     /**
 282      * Base Action for the "Go to Next/Previous Event for thread" actions
 283      */
 284     private class SearchEventAction extends Action {
 285
 286         private final boolean ifDirection;
 287         private final String ifJobName;
 288
 289         /**
 290          * Constructor
 291          *
 292          * @param direction
 293          *            The direction of the search, "true" for forwards and
 294          *            "false" for backwards.
 295          * @param jobName
 296          *            The name of the job that will be spawned
 297          */
 298         public SearchEventAction(boolean direction, String jobName) {
 299             ifDirection = direction;
 300             ifJobName = jobName;
 301         }
 302
 303         @Override
 304         public void run() {
 305             Job job = new Job(ifJobName) {
 306                 @Override
 307                 protected IStatus run(IProgressMonitor monitor) {
 308                     TimeGraphControl ctrl = getTimeGraphViewer().getTimeGraphControl();
 309                     ITimeGraphEntry traceEntry = ctrl.getSelectedTrace();
 310
 311                     long ts = getTimeGraphViewer().getSelectionBegin();
 312                     ITimeEvent selectedState = Utils.findEvent(traceEntry, ts, 0);
 313
 314                     if (selectedState == null) {
 315                         /* No selection currently in the view, do nothing */
 316                         return Status.OK_STATUS;
 317                     }
 318                     ITimeGraphEntry entry = selectedState.getEntry();
 319                     if (!(entry instanceof ControlFlowEntry)) {
 320                         return Status.OK_STATUS;
 321                     }
 322                     ControlFlowEntry cfEntry = (ControlFlowEntry) entry;
 323                     int tid = cfEntry.getThreadId();
 324
 325                     ITmfTrace trace = cfEntry.getTrace();
 326                     ITmfContext ctx = trace.seekEvent(TmfTimestamp.fromNanos(ts));
 327                     long rank = ctx.getRank();
 328                     ctx.dispose();
 329
 330                     Predicate<@NonNull ITmfEvent> predicate = event -> {
 331                         /*
 332                          * TODO Specific to the Control Flow View and kernel
 333                          * traces for now. Could be eventually generalized to
 334                          * anything represented by the time graph row.
 335                          */
 336                         Integer eventTid = KernelTidAspect.INSTANCE.resolve(event);
 337                         return (eventTid != null && eventTid.intValue() == tid);
 338                     };
 339
 340                     ITmfEvent event = (ifDirection ?
 341                             TmfTraceUtils.getNextEventMatching(cfEntry.getTrace(), rank, predicate, monitor) :
 342                             TmfTraceUtils.getPreviousEventMatching(cfEntry.getTrace(), rank, predicate, monitor));
 343                     if (event != null) {
 344                         TmfSignalManager.dispatchSignal(new TmfSelectionRangeUpdatedSignal(this, event.getTimestamp()));
 345                     }
 346                     return Status.OK_STATUS;
 347
 348                 }
 349             };
 350             /*
 351              * Make subsequent jobs not run concurrently, but wait after one
 352              * another.
 353              */
 354             job.setRule(fSearchActionMutexRule);
 355             job.schedule();
 356         }
 357     }
 358
 359     private IAction createHierarchicalAction() {
 360         IAction action = new Action(Messages.ControlFlowView_hierarchicalViewLabel, IAction.AS_RADIO_BUTTON) {
 361             @Override
 362             public void run() {
 363                 ITmfTrace parentTrace = getTrace();
 364                 synchronized (fFlatTraces) {
 365                     fFlatTraces.remove(parentTrace);
 366                     for (ITmfTrace trace : TmfTraceManager.getTraceSet(parentTrace)) {
 367                         final ITmfStateSystem ss = TmfStateSystemAnalysisModule.getStateSystem(trace, KernelAnalysisModule.ID);
 368                         for (TimeGraphEntry traceEntry : getEntryList(ss)) {
 369                             List<ControlFlowEntry> currentRootList = traceEntry.getChildren().stream()
 370                                     .filter(e -> e instanceof ControlFlowEntry)
 371                                     .map(e -> (ControlFlowEntry) e)
 372                                     .collect(Collectors.toList());
 373                             addEntriesToHierarchicalTree(currentRootList, traceEntry);
 374                         }
 375                     }
 376                 }
 377                 refresh();
 378             }
 379         };
 380         action.setChecked(true);
 381         action.setToolTipText(Messages.ControlFlowView_hierarchicalViewToolTip);
 382         return action;
 383     }
 384
 385     private IAction createFlatAction() {
 386         IAction action = new Action(Messages.ControlFlowView_flatViewLabel, IAction.AS_RADIO_BUTTON) {
 387             @Override
 388             public void run() {
 389                 ITmfTrace parentTrace = getTrace();
 390                 synchronized (fFlatTraces) {
 391                     fFlatTraces.add(parentTrace);
 392                     for (ITmfTrace trace : TmfTraceManager.getTraceSet(parentTrace)) {
 393                         final ITmfStateSystem ss = TmfStateSystemAnalysisModule.getStateSystem(trace, KernelAnalysisModule.ID);
 394                         for (TimeGraphEntry traceEntry : getEntryList(ss)) {
 395                             hierarchicalToFlatTree(traceEntry);
 396                         }
 397                     }
 398                 }
 399                 refresh();
 400             }
 401         };
 402         action.setToolTipText(Messages.ControlFlowView_flatViewToolTip);
 403         return action;
 404     }
 405
 406     @Override
 407     protected String getNextText() {
 408         return Messages.ControlFlowView_nextProcessActionNameText;
 409     }
 410
 411     @Override
 412     protected String getNextTooltip() {
 413         return Messages.ControlFlowView_nextProcessActionToolTipText;
 414     }
 415
 416     @Override
 417     protected String getPrevText() {
 418         return Messages.ControlFlowView_previousProcessActionNameText;
 419     }
 420
 421     @Override
 422     protected String getPrevTooltip() {
 423         return Messages.ControlFlowView_previousProcessActionToolTipText;
 424     }
 425
 426     /**
 427      * Get the optimization function for the scheduling column. In the base
 428      * implementation, this optimizes by Line arrows, but can be overidden.
 429      * <p>
 430      * It takes a collection of link events, looking at the entries being
 431      * linked, and returns a list of the proposed order. The list of indexes
 432      * should be in ascending order. There can be duplicates, but the values and
 433      * order should always be the same for the same input.
 434      *
 435      * @return the returned column order, where the integer is the tid of the
 436      *         entry, and the return value is the position, there can be
 437      *         duplicates.
 438      */
 439     public Function<Collection<ILinkEvent>, Map<Integer, Long>> getUpdatedSchedulingColumn() {
 440         return UPDATE_SCHEDULING_COLUMN_ALGO;
 441     }
 442
 443     /**
 444      * This is an optimization action used to find cliques of entries due to
 445      * links and put them closer together
 446      *
 447      * @author Samuel Gagnon
 448      */
 449     private final class OptimizationAction extends Action {
 450
 451         @Override
 452         public void runWithEvent(Event event) {
 453             ITmfTrace trace = getTrace();
 454             if (trace == null) {
 455                 return;
 456             }
 457
 458             createFlatAction().run();
 459
 460             /*
 461              * This method only returns the arrows in the current time interval
 462              * [a,b] of ControlFlowView. Thus, we only optimize for that time
 463              * interval
 464              */
 465             List<ILinkEvent> arrows = getTimeGraphViewer().getTimeGraphControl().getArrows();
 466             final ITmfStateSystem ss = TmfStateSystemAnalysisModule.getStateSystem(trace, KernelAnalysisModule.ID);
 467             List<TimeGraphEntry> currentList = getEntryList(ss);
 468
 469             Map<Integer, Long> orderedTidMap = getUpdatedSchedulingColumn().apply(arrows);
 470
 471             /*
 472              * Now that we have our list of ordered tid, it's time to assign a
 473              * position for each threads in the view. For this, we assign a
 474              * value to an invisible column and sort according to the values in
 475              * this column.
 476              */
 477             for (TimeGraphEntry entry : currentList) {
 478                 if (entry instanceof TraceEntry) {
 479                     for (TimeGraphEntry child : ((TraceEntry) entry).getChildren()) {
 480                         if (child instanceof ControlFlowEntry) {
 481                             ControlFlowEntry cEntry = (ControlFlowEntry) child;
 482                             /*
 483                              * If the thread is in our list, we give it a
 484                              * position. Otherwise, it means there's no activity
 485                              * in the current interval for that thread. We set
 486                              * its position to Long.MAX_VALUE so it goes to the
 487                              * bottom.
 488                              */
 489                             cEntry.setSchedulingPosition(orderedTidMap.getOrDefault(cEntry.getThreadId(), Long.MAX_VALUE));
 490                         }
 491                     }
 492                 }
 493             }
 494
 495             setEntryComparator(ControlFlowColumnComparators.SCHEDULING_COLUMN_COMPARATOR);
 496             refresh();
 497         }
 498
 499     }
 500
 501     /**
 502      * Optimization algorithm, overridable.
 503      *
 504      * @author Matthew Khouzam
 505      * @author Samuel Gagnon
 506      */
 507     public static class OptimizationAlgorithm implements Function<Collection<ILinkEvent>, Map<Integer, Long>> {
 508
 509         /**
 510          * Get the scheduling column order by arrows
 511          *
 512          * @param arrows
 513          *            the list of visible links
 514          * @return the list of weights, by thread ID
 515          */
 516         @Override
 517         public Map<Integer, Long> apply(Collection<ILinkEvent> arrows) {
 518             /*
 519              * "transitions" contains the count of every arrows between two tids
 520              * (Pair<Integer, Integer>). For constructing the Pair, we always
 521              * put the smallest tid first
 522              */
 523             Multiset<Pair<Integer, Integer>> transitions = HashMultiset.<Pair<Integer,Integer>>create();
 524
 525             /*
 526              * We iterate in arrows to count the number of transitions between
 527              * every pair (tid,tid) in the current view
 528              */
 529             for (ILinkEvent arrow : arrows) {
 530                 ITimeGraphEntry from = arrow.getEntry();
 531                 ITimeGraphEntry to = arrow.getDestinationEntry();
 532                 if (!(from instanceof ControlFlowEntry) || !(to instanceof ControlFlowEntry)) {
 533                     continue;
 534                 }
 535                 int fromTid = ((ControlFlowEntry) from).getThreadId();
 536                 int toTid = ((ControlFlowEntry) to).getThreadId();
 537                 if (fromTid != toTid) {
 538                     Pair<Integer, Integer> key = new Pair<>(Math.min(fromTid, toTid), Math.max(fromTid, toTid));
 539                     transitions.add(key);
 540                 }
 541             }
 542
 543             /*
 544              * We now have a transition count for every pair (tid,tid). The next
 545              * step is to sort every pair according to its count in decreasing
 546              * order
 547              */
 548             List<Pair<Integer, Integer>> sortedTransitionsByCount = Multisets.copyHighestCountFirst(transitions).asList();
 549
 550             /*
 551              * Next, we find the order in which we want to display our threads.
 552              * We simply iterate in every pair (tid,tid) in orderedTidList. Each
 553              * time we see a new tid, we add it at the end of orderedTidList.
 554              * This way, threads with lots of transitions will be grouped in the
 555              * top. While very naive, this algorithm is fast, simple and gives
 556              * decent results.
 557              */
 558             Map<Integer, Long> orderedTidMap = new LinkedHashMap<>();
 559             long pos = 0;
 560             for (Pair<Integer, Integer> threadPair : sortedTransitionsByCount) {
 561                 if (orderedTidMap.get(threadPair.getFirst()) == null) {
 562                     orderedTidMap.put(threadPair.getFirst(), pos);
 563                     pos++;
 564                 }
 565                 if (orderedTidMap.get(threadPair.getSecond()) == null) {
 566                     orderedTidMap.put(threadPair.getSecond(), pos);
 567                     pos++;
 568                 }
 569             }
 570
 571             return orderedTidMap;
 572         }
 573     }
 574
 575     /**
 576      * @author gbastien
 577      *
 578      */
 579     protected static class ControlFlowTreeLabelProvider extends TreeLabelProvider {
 580
 581         @Override
 582         public String getColumnText(Object element, int columnIndex) {
 583             if (element instanceof TraceEntry) {
 584                 if (columnIndex == 0) {
 585                     return ((TraceEntry) element).getName();
 586                 }
 587                 return ""; //$NON-NLS-1$
 588             }
 589             ControlFlowEntry entry = (ControlFlowEntry) element;
 590
 591             if (COLUMN_NAMES[columnIndex].equals(Messages.ControlFlowView_processColumn)) {
 592                 return entry.getName();
 593             } else if (COLUMN_NAMES[columnIndex].equals(Messages.ControlFlowView_tidColumn)) {
 594                 return Integer.toString(entry.getThreadId());
 595             } else if (COLUMN_NAMES[columnIndex].equals(Messages.ControlFlowView_ptidColumn)) {
 596                 if (entry.getParentThreadId() > 0) {
 597                     return Integer.toString(entry.getParentThreadId());
 598                 }
 599             } else if (COLUMN_NAMES[columnIndex].equals(Messages.ControlFlowView_birthTimeColumn)) {
 600                 return Utils.formatTime(entry.getStartTime(), TimeFormat.CALENDAR, Resolution.NANOSEC);
 601             } else if (COLUMN_NAMES[columnIndex].equals(Messages.ControlFlowView_traceColumn)) {
 602                 return entry.getTrace().getName();
 603             } else if (COLUMN_NAMES[columnIndex].equals(INVISIBLE_COLUMN)) {
 604                 return Long.toString(entry.getSchedulingPosition());
 605             }
 606             return ""; //$NON-NLS-1$
 607         }
 608
 609     }
 610
 611     private static class ControlFlowFilterLabelProvider extends TreeLabelProvider {
 612
 613         @Override
 614         public String getColumnText(Object element, int columnIndex) {
 615             if (element instanceof TraceEntry) {
 616                 if (columnIndex == 0) {
 617                     return ((TraceEntry) element).getName();
 618                 }
 619                 return ""; //$NON-NLS-1$
 620             }
 621             ControlFlowEntry entry = (ControlFlowEntry) element;
 622
 623             if (columnIndex == 0) {
 624                 return entry.getName();
 625             } else if (columnIndex == 1) {
 626                 return Integer.toString(entry.getThreadId());
 627             }
 628             return ""; //$NON-NLS-1$
 629         }
 630
 631     }
 632
 633     private static class TraceEntry extends TimeGraphEntry {
 634
 635         public TraceEntry(String name, long startTime, long endTime) {
 636             super(name, startTime, endTime);
 637         }
 638
 639         @Override
 640         public boolean hasTimeEvents() {
 641             return false;
 642         }
 643     }
 644
 645     @TmfSignalHandler
 646     @Override
 647     public void traceClosed(org.eclipse.tracecompass.tmf.core.signal.TmfTraceClosedSignal signal) {
 648         super.traceClosed(signal);
 649         synchronized (fFlatTraces) {
 650             fFlatTraces.remove(signal.getTrace());
 651         }
 652     }
 653
 654     @TmfSignalHandler
 655     @Override
 656     public void traceSelected(TmfTraceSelectedSignal signal) {
 657         super.traceSelected(signal);
 658         synchronized (fFlatTraces) {
 659             if (fFlatTraces.contains(signal.getTrace())) {
 660                 fHierarchicalAction.setChecked(false);
 661                 fFlatAction.setChecked(true);
 662             } else {
 663                 fFlatAction.setChecked(false);
 664                 fHierarchicalAction.setChecked(true);
 665             }
 666         }
 667     }
 668
 669     // ------------------------------------------------------------------------
 670     // Internal
 671     // ------------------------------------------------------------------------
 672
 673     @Override
 674     protected void buildEntryList(final ITmfTrace trace, final ITmfTrace parentTrace, final IProgressMonitor monitor) {
 675         final ITmfStateSystem ssq = TmfStateSystemAnalysisModule.getStateSystem(trace, KernelAnalysisModule.ID);
 676         if (ssq == null) {
 677             return;
 678         }
 679
 680         final List<ControlFlowEntry> entryList = new ArrayList<>();
 681         /** Map of trace entries */
 682         Map<ITmfTrace, TraceEntry> traceEntryMap = new HashMap<>();
 683         /** Map of control flow entries, key is a pair [threadId, cpuId] */
 684         final Map<Pair<Integer, Integer>, ControlFlowEntry> entryMap = new HashMap<>();
 685
 686         long start = ssq.getStartTime();
 687         setStartTime(Math.min(getStartTime(), start));
 688
 689         boolean complete = false;
 690         while (!complete) {
 691             if (monitor.isCanceled()) {
 692                 return;
 693             }
 694             complete = ssq.waitUntilBuilt(BUILD_UPDATE_TIMEOUT);
 695             if (ssq.isCancelled()) {
 696                 return;
 697             }
 698             long end = ssq.getCurrentEndTime();
 699             if (start == end && !complete) { // when complete execute one last time regardless of end time
 700                 continue;
 701             }
 702
 703             TraceEntry aTraceEntry = traceEntryMap.get(trace);
 704             if (aTraceEntry == null) {
 705                 aTraceEntry = new TraceEntry(trace.getName(), start, end + 1);
 706                 traceEntryMap.put(trace, aTraceEntry);
 707                 addToEntryList(parentTrace, ssq, Collections.singletonList(aTraceEntry));
 708             } else {
 709                 aTraceEntry.updateEndTime(end + 1);
 710             }
 711             final TraceEntry traceEntry = aTraceEntry;
 712
 713             final long resolution = Math.max(1, (end - ssq.getStartTime()) / getDisplayWidth());
 714             setEndTime(Math.max(getEndTime(), end + 1));
 715             final List<Integer> threadQuarks = ssq.getQuarks(Attributes.THREADS, "*"); //$NON-NLS-1$
 716             queryFullStates(ssq, start, end, resolution, monitor, new IQueryHandler() {
 717                 @Override
 718                 public void handle(List<List<ITmfStateInterval>> fullStates, List<ITmfStateInterval> prevFullState) {
 719                     for (int threadQuark : threadQuarks) {
 720                         String threadAttributeName = ssq.getAttributeName(threadQuark);
 721
 722                         Pair<Integer, Integer> entryKey = Attributes.parseThreadAttributeName(threadAttributeName);
 723                         int threadId = entryKey.getFirst();
 724
 725                         if (threadId < 0) { // ignore the 'unknown' (-1) thread
 726                             continue;
 727                         }
 728
 729                         int execNameQuark;
 730                         int ppidQuark;
 731                         try {
 732                             execNameQuark = ssq.getQuarkRelative(threadQuark, Attributes.EXEC_NAME);
 733                             ppidQuark = ssq.getQuarkRelative(threadQuark, Attributes.PPID);
 734                         } catch (AttributeNotFoundException e) {
 735                             /* No information on this thread (yet?), skip it for now */
 736                             continue;
 737                         }
 738                         ITmfStateInterval lastExecNameInterval = prevFullState == null || execNameQuark >= prevFullState.size() ? null : prevFullState.get(execNameQuark);
 739                         long lastExecNameStartTime = lastExecNameInterval == null ? -1 : lastExecNameInterval.getStartTime();
 740                         long lastExecNameEndTime = lastExecNameInterval == null ? -1 : lastExecNameInterval.getEndTime() + 1;
 741                         long lastPpidStartTime = prevFullState == null || ppidQuark >= prevFullState.size() ? -1 : prevFullState.get(ppidQuark).getStartTime();
 742                         for (List<ITmfStateInterval> fullState : fullStates) {
 743                             if (monitor.isCanceled()) {
 744                                 return;
 745                             }
 746                             if (execNameQuark >= fullState.size() || ppidQuark >= fullState.size()) {
 747                                 /* No information on this thread (yet?), skip it for now */
 748                                 continue;
 749                             }
 750                             ITmfStateInterval execNameInterval = fullState.get(execNameQuark);
 751                             ITmfStateInterval ppidInterval = fullState.get(ppidQuark);
 752                             long startTime = execNameInterval.getStartTime();
 753                             long endTime = execNameInterval.getEndTime() + 1;
 754                             if (startTime == lastExecNameStartTime && ppidInterval.getStartTime() == lastPpidStartTime) {
 755                                 continue;
 756                             }
 757                             boolean isNull = execNameInterval.getStateValue().isNull();
 758                             if (isNull && lastExecNameEndTime < startTime && lastExecNameEndTime != -1) {
 759                                 /*
 760                                  * There was a non-null interval in between the
 761                                  * full states, try to use it.
 762                                  */
 763                                 try {
 764                                     execNameInterval = ssq.querySingleState(startTime - 1, execNameQuark);
 765                                     ppidInterval = ssq.querySingleState(startTime - 1, ppidQuark);
 766                                     startTime = execNameInterval.getStartTime();
 767                                     endTime = execNameInterval.getEndTime() + 1;
 768                                 } catch (StateSystemDisposedException e) {
 769                                     /* ignored */
 770                                 }
 771                             }
 772                             if (!execNameInterval.getStateValue().isNull() &&
 773                                     execNameInterval.getStateValue().getType() == ITmfStateValue.Type.STRING) {
 774                                 String execName = execNameInterval.getStateValue().unboxStr();
 775                                 int ppid = ppidInterval.getStateValue().unboxInt();
 776                                 ControlFlowEntry entry = entryMap.get(entryKey);
 777                                 if (entry == null) {
 778                                     entry = new ControlFlowEntry(threadQuark, trace, execName, threadId, ppid, startTime, endTime);
 779                                     entryList.add(entry);
 780                                     entryMap.put(entryKey, entry);
 781                                 } else {
 782                                     /*
 783                                      * Update the name of the entry to the
 784                                      * latest execName and the parent thread id
 785                                      * to the latest ppid.
 786                                      */
 787                                     entry.setName(execName);
 788                                     entry.setParentThreadId(ppid);
 789                                     entry.updateEndTime(endTime);
 790                                 }
 791                             }
 792                             if (isNull) {
 793                                 entryMap.remove(entryKey);
 794                             }
 795                             lastExecNameStartTime = startTime;
 796                             lastExecNameEndTime = endTime;
 797                             lastPpidStartTime = ppidInterval.getStartTime();
 798                         }
 799                     }
 800                     synchronized (fFlatTraces) {
 801                         if (fFlatTraces.contains(parentTrace)) {
 802                             addEntriesToFlatTree(entryList, traceEntry);
 803                         } else {
 804                             addEntriesToHierarchicalTree(entryList, traceEntry);
 805                         }
 806                     }
 807                 }
 808             });
 809
 810             queryFullStates(ssq, ssq.getStartTime(), end, resolution, monitor, new IQueryHandler() {
 811                 @Override
 812                 public void handle(@NonNull List<List<ITmfStateInterval>> fullStates, @Nullable List<ITmfStateInterval> prevFullState) {
 813                     for (final TimeGraphEntry entry : traceEntry.getChildren()) {
 814                         if (monitor.isCanceled()) {
 815                             return;
 816                         }
 817                         buildStatusEvents(trace, parentTrace, ssq, fullStates, prevFullState, (ControlFlowEntry) entry, monitor, ssq.getStartTime(), end);
 818                     }
 819                 }
 820             });
 821
 822             if (parentTrace.equals(getTrace())) {
 823                 refresh();
 824             }
 825
 826             start = end;
 827         }
 828     }
 829
 830     /**
 831      * Add entries to the traces's child list in a flat fashion (no hierarchy).
 832      * If one entry has children, we do a depth first search to add each child
 833      * to the trace's child list and update the parent and child relations.
 834      */
 835     private static void hierarchicalToFlatTree(TimeGraphEntry traceEntry) {
 836         List<@NonNull TimeGraphEntry> rootList = traceEntry.getChildren();
 837         // We visit the children of every entry to add
 838         StreamFlattener<TimeGraphEntry> sf = new StreamFlattener<>(entry -> entry.getChildren().stream());
 839         Stream<TimeGraphEntry> allEntries = rootList.stream().flatMap(entry -> sf.flatten(entry));
 840
 841         // We add every entry that is missing from the trace's entry list
 842         List<@NonNull TimeGraphEntry> rootListToAdd = allEntries
 843                 .filter(entry -> !rootList.contains(entry))
 844                 .collect(Collectors.toList());
 845         rootList.forEach(entry -> {
 846             entry.clearChildren();
 847         });
 848         rootListToAdd.forEach(entry -> {
 849             traceEntry.addChild(entry);
 850             entry.clearChildren();
 851         });
 852     }
 853
 854     /**
 855      * Add entries to the traces's child list in a flat fashion (no hierarchy).
 856      */
 857     private static void addEntriesToFlatTree(List<@NonNull ControlFlowEntry> entryList, TimeGraphEntry traceEntry) {
 858         List<TimeGraphEntry> rootList = traceEntry.getChildren();
 859         for (ControlFlowEntry entry : entryList) {
 860             if (!rootList.contains(entry)) {
 861                 traceEntry.addChild(entry);
 862             }
 863         }
 864     }
 865
 866     /**
 867      * Add entries to the trace's child list in a hierarchical fashion.
 868      */
 869     private static void addEntriesToHierarchicalTree(List<ControlFlowEntry> entryList, TimeGraphEntry traceEntry) {
 870         List<TimeGraphEntry> rootList = traceEntry.getChildren();
 871
 872         for (ControlFlowEntry entry : entryList) {
 873             boolean root = (entry.getParent() == null || entry.getParent() == traceEntry);
 874             if (root && entry.getParentThreadId() > 0) {
 875                 for (ControlFlowEntry parent : entryList) {
 876                     /*
 877                      * Associate the parent entry only if their time overlap. A
 878                      * child entry may start before its parent, for example at
 879                      * the beginning of the trace if a parent has not yet
 880                      * appeared in the state system. We just want to make sure
 881                      * that the entry didn't start after the parent ended or
 882                      * ended before the parent started.
 883                      */
 884                     if (parent.getThreadId() == entry.getParentThreadId() &&
 885                             !(entry.getStartTime() > parent.getEndTime() ||
 886                             entry.getEndTime() < parent.getStartTime())) {
 887                         parent.addChild(entry);
 888                         root = false;
 889                         if (rootList.contains(entry)) {
 890                             traceEntry.removeChild(entry);
 891                         }
 892                         break;
 893                     }
 894                 }
 895             }
 896             if (root && (!rootList.contains(entry))) {
 897                 traceEntry.addChild(entry);
 898             }
 899         }
 900     }
 901
 902     private void buildStatusEvents(ITmfTrace trace, ITmfTrace parentTrace, ITmfStateSystem ss, @NonNull List<List<ITmfStateInterval>> fullStates,
 903             @Nullable List<ITmfStateInterval> prevFullState, ControlFlowEntry entry, @NonNull IProgressMonitor monitor, long start, long end) {
 904         if (start < entry.getEndTime() && end > entry.getStartTime()) {
 905             List<ITimeEvent> eventList = getEventList(entry, ss, fullStates, prevFullState, monitor);
 906             if (eventList == null) {
 907                 return;
 908             }
 909             /* Start a new event list on first iteration, then append to it */
 910             if (prevFullState == null) {
 911                 entry.setEventList(eventList);
 912             } else {
 913                 for (ITimeEvent event : eventList) {
 914                     entry.addEvent(event);
 915                 }
 916             }
 917             if (parentTrace.equals(getTrace())) {
 918                 redraw();
 919             }
 920         }
 921         for (ITimeGraphEntry child : entry.getChildren()) {
 922             if (monitor.isCanceled()) {
 923                 return;
 924             }
 925             buildStatusEvents(trace, parentTrace, ss, fullStates, prevFullState, (ControlFlowEntry) child, monitor, start, end);
 926         }
 927     }
 928
 929     @Override
 930     protected @Nullable List<ITimeEvent> getEventList(@NonNull TimeGraphEntry tgentry, ITmfStateSystem ss,
 931             @NonNull List<List<ITmfStateInterval>> fullStates, @Nullable List<ITmfStateInterval> prevFullState, @NonNull IProgressMonitor monitor) {
 932         List<ITimeEvent> eventList = null;
 933         if (!(tgentry instanceof ControlFlowEntry)) {
 934             return eventList;
 935         }
 936         ControlFlowEntry entry = (ControlFlowEntry) tgentry;
 937         try {
 938             int threadQuark = entry.getThreadQuark();
 939             int statusQuark = ss.getQuarkRelative(threadQuark, Attributes.STATUS);
 940             eventList = new ArrayList<>(fullStates.size());
 941             ITmfStateInterval lastInterval = prevFullState == null || statusQuark >= prevFullState.size() ? null : prevFullState.get(statusQuark);
 942             long lastStartTime = lastInterval == null ? -1 : lastInterval.getStartTime();
 943             long lastEndTime = lastInterval == null ? -1 : lastInterval.getEndTime() + 1;
 944             for (List<ITmfStateInterval> fullState : fullStates) {
 945                 if (monitor.isCanceled()) {
 946                     return null;
 947                 }
 948                 if (statusQuark >= fullState.size()) {
 949                     /* No information on this thread (yet?), skip it for now */
 950                     continue;
 951                 }
 952                 ITmfStateInterval statusInterval = fullState.get(statusQuark);
 953                 long time = statusInterval.getStartTime();
 954                 if (time == lastStartTime) {
 955                     continue;
 956                 }
 957                 long duration = statusInterval.getEndTime() - time + 1;
 958                 int status = -1;
 959                 try {
 960                     status = statusInterval.getStateValue().unboxInt();
 961                 } catch (StateValueTypeException e) {
 962                     Activator.getDefault().logError(e.getMessage());
 963                 }
 964                 if (lastEndTime != time && lastEndTime != -1) {
 965                     eventList.add(new TimeEvent(entry, lastEndTime, time - lastEndTime));
 966                 }
 967                 if (!statusInterval.getStateValue().isNull()) {
 968                     eventList.add(new TimeEvent(entry, time, duration, status));
 969                 } else {
 970                     eventList.add(new NullTimeEvent(entry, time, duration));
 971                 }
 972                 lastStartTime = time;
 973                 lastEndTime = time + duration;
 974             }
 975         } catch (AttributeNotFoundException | TimeRangeException e) {
 976             Activator.getDefault().logError(e.getMessage());
 977         }
 978         return eventList;
 979     }
 980
 981     /**
 982      * Returns a value corresponding to the selected entry.
 983      *
 984      * Used in conjunction with synchingToTime to change the selected entry. If
 985      * one of these methods is overridden in child class, then both should be.
 986      *
 987      * @param time
 988      *            The currently selected time
 989      * @return a value identifying the entry
 990      */
 991     private int getSelectionValue(long time) {
 992         int thread = -1;
 993         for (ITmfTrace trace : TmfTraceManager.getTraceSet(getTrace())) {
 994             if (thread > 0) {
 995                 break;
 996             }
 997             ITmfStateSystem ssq = TmfStateSystemAnalysisModule.getStateSystem(trace, KernelAnalysisModule.ID);
 998             if (ssq == null) {
 999                 continue;
1000             }
1001             if (time >= ssq.getStartTime() && time <= ssq.getCurrentEndTime()) {
1002                 List<Integer> currentThreadQuarks = ssq.getQuarks(Attributes.CPUS, "*", Attributes.CURRENT_THREAD); //$NON-NLS-1$
1003                 for (int currentThreadQuark : currentThreadQuarks) {
1004                     try {
1005                         ITmfStateInterval currentThreadInterval = ssq.querySingleState(time, currentThreadQuark);
1006                         int currentThread = currentThreadInterval.getStateValue().unboxInt();
1007                         if (currentThread > 0) {
1008                             int statusQuark = ssq.getQuarkAbsolute(Attributes.THREADS, Integer.toString(currentThread), Attributes.STATUS);
1009                             ITmfStateInterval statusInterval = ssq.querySingleState(time, statusQuark);
1010                             if (statusInterval.getStartTime() == time) {
1011                                 thread = currentThread;
1012                                 break;
1013                             }
1014                         }
1015                     } catch (AttributeNotFoundException | TimeRangeException | StateValueTypeException e) {
1016                         Activator.getDefault().logError(e.getMessage());
1017                     } catch (StateSystemDisposedException e) {
1018                         /* Ignored */
1019                     }
1020                 }
1021             }
1022         }
1023         return thread;
1024     }
1025
1026     @Override
1027     protected void synchingToTime(long time) {
1028         int selected = getSelectionValue(time);
1029         if (selected > 0) {
1030             for (Object element : getTimeGraphViewer().getExpandedElements()) {
1031                 if (element instanceof ControlFlowEntry) {
1032                     ControlFlowEntry entry = (ControlFlowEntry) element;
1033                     if (entry.getThreadId() == selected) {
1034                         getTimeGraphCombo().setSelection(entry);
1035                         break;
1036                     }
1037                 }
1038             }
1039         }
1040     }
1041
1042     @Override
1043     protected @NonNull List<ILinkEvent> getLinkList(ITmfStateSystem ss,
1044             @NonNull List<List<ITmfStateInterval>> fullStates, @Nullable List<ITmfStateInterval> prevFullState, @NonNull IProgressMonitor monitor) {
1045         List<ILinkEvent> list = new ArrayList<>();
1046         List<TimeGraphEntry> entryList = getEntryList(ss);
1047         if (entryList == null) {
1048             return list;
1049         }
1050         for (ITmfTrace trace : TmfTraceManager.getTraceSet(getTrace())) {
1051             List<Integer> currentThreadQuarks = ss.getQuarks(Attributes.CPUS, "*", Attributes.CURRENT_THREAD); //$NON-NLS-1$
1052             for (int currentThreadQuark : currentThreadQuarks) {
1053                 if (currentThreadQuark >= fullStates.get(0).size()) {
1054                     /* No information on this cpu (yet?), skip it for now */
1055                     continue;
1056                 }
1057                 List<ITmfStateInterval> currentThreadIntervals = new ArrayList<>(fullStates.size() + 2);
1058                 try {
1059                     /*
1060                      * Add the previous interval if it is the first query
1061                      * iteration and the first interval has currentThread=0. Add
1062                      * the following interval if the last interval has
1063                      * currentThread=0. These are diagonal arrows crossing the
1064                      * query iteration range.
1065                      */
1066                     if (prevFullState == null) {
1067                         ITmfStateInterval currentThreadInterval = fullStates.get(0).get(currentThreadQuark);
1068                         if (currentThreadInterval.getStateValue().unboxInt() == 0) {
1069                             long start = Math.max(currentThreadInterval.getStartTime() - 1, ss.getStartTime());
1070                             currentThreadIntervals.add(ss.querySingleState(start, currentThreadQuark));
1071                         }
1072                     }
1073                     for (List<ITmfStateInterval> fullState : fullStates) {
1074                         currentThreadIntervals.add(fullState.get(currentThreadQuark));
1075                     }
1076                     ITmfStateInterval currentThreadInterval = fullStates.get(fullStates.size() - 1).get(currentThreadQuark);
1077                     if (currentThreadInterval.getStateValue().unboxInt() == 0) {
1078                         long end = Math.min(currentThreadInterval.getEndTime() + 1, ss.getCurrentEndTime());
1079                         currentThreadIntervals.add(ss.querySingleState(end, currentThreadQuark));
1080                     }
1081                 } catch (StateSystemDisposedException e) {
1082                     /* Ignored */
1083                     return list;
1084                 }
1085                 int prevThread = 0;
1086                 long prevEnd = 0;
1087                 long lastEnd = 0;
1088                 for (ITmfStateInterval currentThreadInterval : currentThreadIntervals) {
1089                     if (monitor.isCanceled()) {
1090                         return list;
1091                     }
1092                     if (currentThreadInterval.getEndTime() + 1 == lastEnd) {
1093                         continue;
1094                     }
1095                     long time = currentThreadInterval.getStartTime();
1096                     if (time != lastEnd) {
1097                         // don't create links where there are gaps in intervals due to the resolution
1098                         prevThread = 0;
1099                         prevEnd = 0;
1100                     }
1101                     int thread = currentThreadInterval.getStateValue().unboxInt();
1102                     if (thread > 0 && prevThread > 0) {
1103                         ITimeGraphEntry prevEntry = findEntry(entryList, trace, prevThread);
1104                         ITimeGraphEntry nextEntry = findEntry(entryList, trace, thread);
1105                         list.add(new TimeLinkEvent(prevEntry, nextEntry, prevEnd, time - prevEnd, 0));
1106                     }
1107                     lastEnd = currentThreadInterval.getEndTime() + 1;
1108                     if (thread != 0) {
1109                         prevThread = thread;
1110                         prevEnd = lastEnd;
1111                     }
1112                 }
1113             }
1114         }
1115         return list;
1116     }
1117
1118     private ControlFlowEntry findEntry(List<TimeGraphEntry> entryList, ITmfTrace trace, int threadId) {
1119         for (TimeGraphEntry entry : entryList) {
1120             if (entry instanceof ControlFlowEntry) {
1121                 ControlFlowEntry controlFlowEntry = (ControlFlowEntry) entry;
1122                 if (controlFlowEntry.getThreadId() == threadId && controlFlowEntry.getTrace() == trace) {
1123                     return controlFlowEntry;
1124                 }
1125             }
1126             if (entry.hasChildren()) {
1127                 ControlFlowEntry controlFlowEntry = findEntry(entry.getChildren(), trace, threadId);
1128                 if (controlFlowEntry != null) {
1129                     return controlFlowEntry;
1130                 }
1131             }
1132         }
1133         return null;
1134     }
1135 }