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