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

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