Quelle  exported-sql-viewer.py   Sprache: Python

#!/usr/bin/env python
# SPDX-License-Identifier: GPL-2.0
# exported-sql-viewer.py: view data from sql database
# Copyright (c) 2014-2018, Intel Corporation.

# To use this script you will need to have exported data using either the
# export-to-sqlite.py or the export-to-postgresql.py script.  Refer to those
# scripts for details.
#
# Following on from the example in the export scripts, a
# call-graph can be displayed for the pt_example database like this:
#
# python tools/perf/scripts/python/exported-sql-viewer.py pt_example
#
# Note that for PostgreSQL, this script supports connecting to remote databases
# by setting hostname, port, username, password, and dbname e.g.
#
# python tools/perf/scripts/python/exported-sql-viewer.py "hostname=myhost username=myuser password=mypassword dbname=pt_example"
#
# The result is a GUI window with a tree representing a context-sensitive
# call-graph.  Expanding a couple of levels of the tree and adjusting column
# widths to suit will display something like:
#
#                                         Call Graph: pt_example
# Call Path                          Object      Count   Time(ns)  Time(%)  Branch Count   Branch Count(%)
# v- ls
#     v- 2638:2638
#         v- _start                  ld-2.19.so    1     10074071   100.0         211135            100.0
#           |- unknown               unknown       1        13198     0.1              1              0.0
#           >- _dl_start             ld-2.19.so    1      1400980    13.9          19637              9.3
#           >- _d_linit_internal     ld-2.19.so    1       448152     4.4          11094              5.3
#           v-__libc_start_main@plt  ls            1      8211741    81.5         180397             85.4
#              >- _dl_fixup          ld-2.19.so    1         7607     0.1            108              0.1
#              >- __cxa_atexit       libc-2.19.so  1        11737     0.1             10              0.0
#              >- __libc_csu_init    ls            1        10354     0.1             10              0.0
#              |- _setjmp            libc-2.19.so  1            0     0.0              4              0.0
#              v- main               ls            1      8182043    99.6         180254             99.9
#
# Points to note:
# The top level is a command name (comm)
# The next level is a thread (pid:tid)
# Subsequent levels are functions
# 'Count' is the number of calls
# 'Time' is the elapsed time until the function returns
# Percentages are relative to the level above
# 'Branch Count' is the total number of branches for that function and all
#       functions that it calls

# There is also a "All branches" report, which displays branches and
# possibly disassembly.  However, presently, the only supported disassembler is
# Intel XED, and additionally the object code must be present in perf build ID
# cache. To use Intel XED, libxed.so must be present. To build and install
# libxed.so:
#            git clone https://github.com/intelxed/mbuild.git mbuild
#            git clone https://github.com/intelxed/xed
#            cd xed
#            ./mfile.py --share
#            sudo ./mfile.py --prefix=/usr/local install
#            sudo ldconfig
#
# Example report:
#
# Time           CPU  Command  PID    TID    Branch Type            In Tx  Branch
# 8107675239590  2    ls       22011  22011  return from interrupt  No     ffffffff86a00a67 native_irq_return_iret ([kernel]) -> 7fab593ea260 _start (ld-2.19.so)
#                                                                              7fab593ea260 48 89 e7                                        mov %rsp, %rdi
# 8107675239899  2    ls       22011  22011  hardware interrupt     No         7fab593ea260 _start (ld-2.19.so) -> ffffffff86a012e0 page_fault ([kernel])
# 8107675241900  2    ls       22011  22011  return from interrupt  No     ffffffff86a00a67 native_irq_return_iret ([kernel]) -> 7fab593ea260 _start (ld-2.19.so)
#                                                                              7fab593ea260 48 89 e7                                        mov %rsp, %rdi
#                                                                              7fab593ea263 e8 c8 06 00 00                                  callq  0x7fab593ea930
# 8107675241900  2    ls       22011  22011  call                   No         7fab593ea263 _start+0x3 (ld-2.19.so) -> 7fab593ea930 _dl_start (ld-2.19.so)
#                                                                              7fab593ea930 55                                              pushq  %rbp
#                                                                              7fab593ea931 48 89 e5                                        mov %rsp, %rbp
#                                                                              7fab593ea934 41 57                                           pushq  %r15
#                                                                              7fab593ea936 41 56                                           pushq  %r14
#                                                                              7fab593ea938 41 55                                           pushq  %r13
#                                                                              7fab593ea93a 41 54                                           pushq  %r12
#                                                                              7fab593ea93c 53                                              pushq  %rbx
#                                                                              7fab593ea93d 48 89 fb                                        mov %rdi, %rbx
#                                                                              7fab593ea940 48 83 ec 68                                     sub $0x68, %rsp
#                                                                              7fab593ea944 0f 31                                           rdtsc
#                                                                              7fab593ea946 48 c1 e2 20                                     shl $0x20, %rdx
#                                                                              7fab593ea94a 89 c0                                           mov %eax, %eax
#                                                                              7fab593ea94c 48 09 c2                                        or %rax, %rdx
#                                                                              7fab593ea94f 48 8b 05 1a 15 22 00                            movq  0x22151a(%rip), %rax
# 8107675242232  2    ls       22011  22011  hardware interrupt     No         7fab593ea94f _dl_start+0x1f (ld-2.19.so) -> ffffffff86a012e0 page_fault ([kernel])
# 8107675242900  2    ls       22011  22011  return from interrupt  No     ffffffff86a00a67 native_irq_return_iret ([kernel]) -> 7fab593ea94f _dl_start+0x1f (ld-2.19.so)
#                                                                              7fab593ea94f 48 8b 05 1a 15 22 00                            movq  0x22151a(%rip), %rax
#                                                                              7fab593ea956 48 89 15 3b 13 22 00                            movq  %rdx, 0x22133b(%rip)
# 8107675243232  2    ls       22011  22011  hardware interrupt     No         7fab593ea956 _dl_start+0x26 (ld-2.19.so) -> ffffffff86a012e0 page_fault ([kernel])

from __future__ import print_function

import sys
# Only change warnings if the python -W option was not used
if not sys.warnoptions:
 import warnings
 # PySide2 causes deprecation warnings, ignore them.
 warnings.filterwarnings("ignore", category=DeprecationWarning)
import argparse
import weakref
import threading
import string
try:
 # Python2
 import cPickle as pickle
 # size of pickled integer big enough for record size
 glb_nsz = 8
except ImportError:
 import pickle
 glb_nsz = 16
import re
import os
import random
import copy
import math
from libxed import LibXED

pyside_version_1 = True
if not "--pyside-version-1" in sys.argv:
 try:
  from PySide2.QtCore import *
  from PySide2.QtGui import *
  from PySide2.QtSql import *
  from PySide2.QtWidgets import *
  pyside_version_1 = False
 except:
  pass

if pyside_version_1:
 from PySide.QtCore import *
 from PySide.QtGui import *
 from PySide.QtSql import *

from decimal import Decimal, ROUND_HALF_UP
from ctypes import CDLL, Structure, create_string_buffer, addressof, sizeof, \
     c_void_p, c_bool, c_byte, c_char, c_int, c_uint, c_longlong, c_ulonglong
from multiprocessing import Process, Array, Value, Event

# xrange is range in Python3
try:
 xrange
except NameError:
 xrange = range

def printerr(*args, **keyword_args):
 print(*args, file=sys.stderr, **keyword_args)

# Data formatting helpers

def tohex(ip):
 if ip < 0:
  ip += 1 << 64
 return "%x" % ip

def offstr(offset):
 if offset:
  return "+0x%x" % offset
 return ""

def dsoname(name):
 if name == "[kernel.kallsyms]":
  return "[kernel]"
 return name

def findnth(s, sub, n, offs=0):
 pos = s.find(sub)
 if pos < 0:
  return pos
 if n <= 1:
  return offs + pos
 return findnth(s[pos + 1:], sub, n - 1, offs + pos + 1)

# Percent to one decimal place

def PercentToOneDP(n, d):
 if not d:
  return "0.0"
 x = (n * Decimal(100)) / d
 return str(x.quantize(Decimal(".1"), rounding=ROUND_HALF_UP))

# Helper for queries that must not fail

def QueryExec(query, stmt):
 ret = query.exec_(stmt)
 if not ret:
  raise Exception("Query failed: " + query.lastError().text())

# Background thread

class Thread(QThread):

 done = Signal(object)

 def __init__(self, task, param=None, parent=None):
  super(Thread, self).__init__(parent)
  self.task = task
  self.param = param

 def run(self):
  while True:
   if self.param is None:
    done, result = self.task()
   else:
    done, result = self.task(self.param)
   self.done.emit(result)
   if done:
    break

# Tree data model

class TreeModel(QAbstractItemModel):

 def __init__(self, glb, params, parent=None):
  super(TreeModel, self).__init__(parent)
  self.glb = glb
  self.params = params
  self.root = self.GetRoot()
  self.last_row_read = 0

 def Item(self, parent):
  if parent.isValid():
   return parent.internalPointer()
  else:
   return self.root

 def rowCount(self, parent):
  result = self.Item(parent).childCount()
  if result < 0:
   result = 0
   self.dataChanged.emit(parent, parent)
  return result

 def hasChildren(self, parent):
  return self.Item(parent).hasChildren()

 def headerData(self, section, orientation, role):
  if role == Qt.TextAlignmentRole:
   return self.columnAlignment(section)
  if role != Qt.DisplayRole:
   return None
  if orientation != Qt.Horizontal:
   return None
  return self.columnHeader(section)

 def parent(self, child):
  child_item = child.internalPointer()
  if child_item is self.root:
   return QModelIndex()
  parent_item = child_item.getParentItem()
  return self.createIndex(parent_item.getRow(), 0, parent_item)

 def index(self, row, column, parent):
  child_item = self.Item(parent).getChildItem(row)
  return self.createIndex(row, column, child_item)

 def DisplayData(self, item, index):
  return item.getData(index.column())

 def FetchIfNeeded(self, row):
  if row > self.last_row_read:
   self.last_row_read = row
   if row + 10 >= self.root.child_count:
    self.fetcher.Fetch(glb_chunk_sz)

 def columnAlignment(self, column):
  return Qt.AlignLeft

 def columnFont(self, column):
  return None

 def data(self, index, role):
  if role == Qt.TextAlignmentRole:
   return self.columnAlignment(index.column())
  if role == Qt.FontRole:
   return self.columnFont(index.column())
  if role != Qt.DisplayRole:
   return None
  item = index.internalPointer()
  return self.DisplayData(item, index)

# Table data model

class TableModel(QAbstractTableModel):

 def __init__(self, parent=None):
  super(TableModel, self).__init__(parent)
  self.child_count = 0
  self.child_items = []
  self.last_row_read = 0

 def Item(self, parent):
  if parent.isValid():
   return parent.internalPointer()
  else:
   return self

 def rowCount(self, parent):
  return self.child_count

 def headerData(self, section, orientation, role):
  if role == Qt.TextAlignmentRole:
   return self.columnAlignment(section)
  if role != Qt.DisplayRole:
   return None
  if orientation != Qt.Horizontal:
   return None
  return self.columnHeader(section)

 def index(self, row, column, parent):
  return self.createIndex(row, column, self.child_items[row])

 def DisplayData(self, item, index):
  return item.getData(index.column())

 def FetchIfNeeded(self, row):
  if row > self.last_row_read:
   self.last_row_read = row
   if row + 10 >= self.child_count:
    self.fetcher.Fetch(glb_chunk_sz)

 def columnAlignment(self, column):
  return Qt.AlignLeft

 def columnFont(self, column):
  return None

 def data(self, index, role):
  if role == Qt.TextAlignmentRole:
   return self.columnAlignment(index.column())
  if role == Qt.FontRole:
   return self.columnFont(index.column())
  if role != Qt.DisplayRole:
   return None
  item = index.internalPointer()
  return self.DisplayData(item, index)

# Model cache

model_cache = weakref.WeakValueDictionary()
model_cache_lock = threading.Lock()

def LookupCreateModel(model_name, create_fn):
 model_cache_lock.acquire()
 try:
  model = model_cache[model_name]
 except:
  model = None
 if model is None:
  model = create_fn()
  model_cache[model_name] = model
 model_cache_lock.release()
 return model

def LookupModel(model_name):
 model_cache_lock.acquire()
 try:
  model = model_cache[model_name]
 except:
  model = None
 model_cache_lock.release()
 return model

# Find bar

class FindBar():

 def __init__(self, parent, finder, is_reg_expr=False):
  self.finder = finder
  self.context = []
  self.last_value = None
  self.last_pattern = None

  label = QLabel("Find:")
  label.setSizePolicy(QSizePolicy.Fixed, QSizePolicy.Fixed)

  self.textbox = QComboBox()
  self.textbox.setEditable(True)
  self.textbox.currentIndexChanged.connect(self.ValueChanged)

  self.progress = QProgressBar()
  self.progress.setRange(0, 0)
  self.progress.hide()

  if is_reg_expr:
   self.pattern = QCheckBox("Regular Expression")
  else:
   self.pattern = QCheckBox("Pattern")
  self.pattern.setSizePolicy(QSizePolicy.Fixed, QSizePolicy.Fixed)

  self.next_button = QToolButton()
  self.next_button.setIcon(parent.style().standardIcon(QStyle.SP_ArrowDown))
  self.next_button.released.connect(lambda: self.NextPrev(1))

  self.prev_button = QToolButton()
  self.prev_button.setIcon(parent.style().standardIcon(QStyle.SP_ArrowUp))
  self.prev_button.released.connect(lambda: self.NextPrev(-1))

  self.close_button = QToolButton()
  self.close_button.setIcon(parent.style().standardIcon(QStyle.SP_DockWidgetCloseButton))
  self.close_button.released.connect(self.Deactivate)

  self.hbox = QHBoxLayout()
  self.hbox.setContentsMargins(0, 0, 0, 0)

  self.hbox.addWidget(label)
  self.hbox.addWidget(self.textbox)
  self.hbox.addWidget(self.progress)
  self.hbox.addWidget(self.pattern)
  self.hbox.addWidget(self.next_button)
  self.hbox.addWidget(self.prev_button)
  self.hbox.addWidget(self.close_button)

  self.bar = QWidget()
  self.bar.setLayout(self.hbox)
  self.bar.hide()

 def Widget(self):
  return self.bar

 def Activate(self):
  self.bar.show()
  self.textbox.lineEdit().selectAll()
  self.textbox.setFocus()

 def Deactivate(self):
  self.bar.hide()

 def Busy(self):
  self.textbox.setEnabled(False)
  self.pattern.hide()
  self.next_button.hide()
  self.prev_button.hide()
  self.progress.show()

 def Idle(self):
  self.textbox.setEnabled(True)
  self.progress.hide()
  self.pattern.show()
  self.next_button.show()
  self.prev_button.show()

 def Find(self, direction):
  value = self.textbox.currentText()
  pattern = self.pattern.isChecked()
  self.last_value = value
  self.last_pattern = pattern
  self.finder.Find(value, direction, pattern, self.context)

 def ValueChanged(self):
  value = self.textbox.currentText()
  pattern = self.pattern.isChecked()
  index = self.textbox.currentIndex()
  data = self.textbox.itemData(index)
  # Store the pattern in the combo box to keep it with the text value
  if data == None:
   self.textbox.setItemData(index, pattern)
  else:
   self.pattern.setChecked(data)
  self.Find(0)

 def NextPrev(self, direction):
  value = self.textbox.currentText()
  pattern = self.pattern.isChecked()
  if value != self.last_value:
   index = self.textbox.findText(value)
   # Allow for a button press before the value has been added to the combo box
   if index < 0:
    index = self.textbox.count()
    self.textbox.addItem(value, pattern)
    self.textbox.setCurrentIndex(index)
    return
   else:
    self.textbox.setItemData(index, pattern)
  elif pattern != self.last_pattern:
   # Keep the pattern recorded in the combo box up to date
   index = self.textbox.currentIndex()
   self.textbox.setItemData(index, pattern)
  self.Find(direction)

 def NotFound(self):
  QMessageBox.information(self.bar, "Find", "'" + self.textbox.currentText() + "' not found")

# Context-sensitive call graph data model item base

class CallGraphLevelItemBase(object):

 def __init__(self, glb, params, row, parent_item):
  self.glb = glb
  self.params = params
  self.row = row
  self.parent_item = parent_item
  self.query_done = False
  self.child_count = 0
  self.child_items = []
  if parent_item:
   self.level = parent_item.level + 1
  else:
   self.level = 0

 def getChildItem(self, row):
  return self.child_items[row]

 def getParentItem(self):
  return self.parent_item

 def getRow(self):
  return self.row

 def childCount(self):
  if not self.query_done:
   self.Select()
   if not self.child_count:
    return -1
  return self.child_count

 def hasChildren(self):
  if not self.query_done:
   return True
  return self.child_count > 0

 def getData(self, column):
  return self.data[column]

# Context-sensitive call graph data model level 2+ item base

class CallGraphLevelTwoPlusItemBase(CallGraphLevelItemBase):

 def __init__(self, glb, params, row, comm_id, thread_id, call_path_id, time, insn_cnt, cyc_cnt, branch_count, parent_item):
  super(CallGraphLevelTwoPlusItemBase, self).__init__(glb, params, row, parent_item)
  self.comm_id = comm_id
  self.thread_id = thread_id
  self.call_path_id = call_path_id
  self.insn_cnt = insn_cnt
  self.cyc_cnt = cyc_cnt
  self.branch_count = branch_count
  self.time = time

 def Select(self):
  self.query_done = True
  query = QSqlQuery(self.glb.db)
  if self.params.have_ipc:
   ipc_str = ", SUM(insn_count), SUM(cyc_count)"
  else:
   ipc_str = ""
  QueryExec(query, "SELECT call_path_id, name, short_name, COUNT(calls.id), SUM(return_time - call_time)" + ipc_str + ", SUM(branch_count)"
     " FROM calls"
     " INNER JOIN call_paths ON calls.call_path_id = call_paths.id"
     " INNER JOIN symbols ON call_paths.symbol_id = symbols.id"
     " INNER JOIN dsos ON symbols.dso_id = dsos.id"
     " WHERE parent_call_path_id = " + str(self.call_path_id) +
     " AND comm_id = " + str(self.comm_id) +
     " AND thread_id = " + str(self.thread_id) +
     " GROUP BY call_path_id, name, short_name"
     " ORDER BY call_path_id")
  while query.next():
   if self.params.have_ipc:
    insn_cnt = int(query.value(5))
    cyc_cnt = int(query.value(6))
    branch_count = int(query.value(7))
   else:
    insn_cnt = 0
    cyc_cnt = 0
    branch_count = int(query.value(5))
   child_item = CallGraphLevelThreeItem(self.glb, self.params, self.child_count, self.comm_id, self.thread_id, query.value(0), query.value(1), query.value(2), query.value(3), int(query.value(4)), insn_cnt, cyc_cnt, branch_count, self)
   self.child_items.append(child_item)
   self.child_count += 1

# Context-sensitive call graph data model level three item

class CallGraphLevelThreeItem(CallGraphLevelTwoPlusItemBase):

 def __init__(self, glb, params, row, comm_id, thread_id, call_path_id, name, dso, count, time, insn_cnt, cyc_cnt, branch_count, parent_item):
  super(CallGraphLevelThreeItem, self).__init__(glb, params, row, comm_id, thread_id, call_path_id, time, insn_cnt, cyc_cnt, branch_count, parent_item)
  dso = dsoname(dso)
  if self.params.have_ipc:
   insn_pcnt = PercentToOneDP(insn_cnt, parent_item.insn_cnt)
   cyc_pcnt = PercentToOneDP(cyc_cnt, parent_item.cyc_cnt)
   br_pcnt = PercentToOneDP(branch_count, parent_item.branch_count)
   ipc = CalcIPC(cyc_cnt, insn_cnt)
   self.data = [ name, dso, str(count), str(time), PercentToOneDP(time, parent_item.time), str(insn_cnt), insn_pcnt, str(cyc_cnt), cyc_pcnt, ipc, str(branch_count), br_pcnt ]
  else:
   self.data = [ name, dso, str(count), str(time), PercentToOneDP(time, parent_item.time), str(branch_count), PercentToOneDP(branch_count, parent_item.branch_count) ]
  self.dbid = call_path_id

# Context-sensitive call graph data model level two item

class CallGraphLevelTwoItem(CallGraphLevelTwoPlusItemBase):

 def __init__(self, glb, params, row, comm_id, thread_id, pid, tid, parent_item):
  super(CallGraphLevelTwoItem, self).__init__(glb, params, row, comm_id, thread_id, 1, 0, 0, 0, 0, parent_item)
  if self.params.have_ipc:
   self.data = [str(pid) + ":" + str(tid), "", "", "", "", "", "", "", "", "", "", ""]
  else:
   self.data = [str(pid) + ":" + str(tid), "", "", "", "", "", ""]
  self.dbid = thread_id

 def Select(self):
  super(CallGraphLevelTwoItem, self).Select()
  for child_item in self.child_items:
   self.time += child_item.time
   self.insn_cnt += child_item.insn_cnt
   self.cyc_cnt += child_item.cyc_cnt
   self.branch_count += child_item.branch_count
  for child_item in self.child_items:
   child_item.data[4] = PercentToOneDP(child_item.time, self.time)
   if self.params.have_ipc:
    child_item.data[6] = PercentToOneDP(child_item.insn_cnt, self.insn_cnt)
    child_item.data[8] = PercentToOneDP(child_item.cyc_cnt, self.cyc_cnt)
    child_item.data[11] = PercentToOneDP(child_item.branch_count, self.branch_count)
   else:
    child_item.data[6] = PercentToOneDP(child_item.branch_count, self.branch_count)

# Context-sensitive call graph data model level one item

class CallGraphLevelOneItem(CallGraphLevelItemBase):

 def __init__(self, glb, params, row, comm_id, comm, parent_item):
  super(CallGraphLevelOneItem, self).__init__(glb, params, row, parent_item)
  if self.params.have_ipc:
   self.data = [comm, "", "", "", "", "", "", "", "", "", "", ""]
  else:
   self.data = [comm, "", "", "", "", "", ""]
  self.dbid = comm_id

 def Select(self):
  self.query_done = True
  query = QSqlQuery(self.glb.db)
  QueryExec(query, "SELECT thread_id, pid, tid"
     " FROM comm_threads"
     " INNER JOIN threads ON thread_id = threads.id"
     " WHERE comm_id = " + str(self.dbid))
  while query.next():
   child_item = CallGraphLevelTwoItem(self.glb, self.params, self.child_count, self.dbid, query.value(0), query.value(1), query.value(2), self)
   self.child_items.append(child_item)
   self.child_count += 1

# Context-sensitive call graph data model root item

class CallGraphRootItem(CallGraphLevelItemBase):

 def __init__(self, glb, params):
  super(CallGraphRootItem, self).__init__(glb, params, 0, None)
  self.dbid = 0
  self.query_done = True
  if_has_calls = ""
  if IsSelectable(glb.db, "comms", columns = "has_calls"):
   if_has_calls = " WHERE has_calls = " + glb.dbref.TRUE
  query = QSqlQuery(glb.db)
  QueryExec(query, "SELECT id, comm FROM comms" + if_has_calls)
  while query.next():
   if not query.value(0):
    continue
   child_item = CallGraphLevelOneItem(glb, params, self.child_count, query.value(0), query.value(1), self)
   self.child_items.append(child_item)
   self.child_count += 1

# Call graph model parameters

class CallGraphModelParams():

 def __init__(self, glb, parent=None):
  self.have_ipc = IsSelectable(glb.db, "calls", columns = "insn_count, cyc_count")

# Context-sensitive call graph data model base

class CallGraphModelBase(TreeModel):

 def __init__(self, glb, parent=None):
  super(CallGraphModelBase, self).__init__(glb, CallGraphModelParams(glb), parent)

 def FindSelect(self, value, pattern, query):
  if pattern:
   # postgresql and sqlite pattern patching differences:
   #   postgresql LIKE is case sensitive but sqlite LIKE is not
   #   postgresql LIKE allows % and _ to be escaped with \ but sqlite LIKE does not
   #   postgresql supports ILIKE which is case insensitive
   #   sqlite supports GLOB (text only) which uses * and ? and is case sensitive
   if not self.glb.dbref.is_sqlite3:
    # Escape % and _
    s = value.replace("%", "\\%")
    s = s.replace("_", "\\_")
    # Translate * and ? into SQL LIKE pattern characters % and _
    if sys.version_info[0] == 3:
     trans = str.maketrans("*?", "%_")
    else:
     trans = string.maketrans("*?", "%_")
    match = " LIKE '" + str(s).translate(trans) + "'"
   else:
    match = " GLOB '" + str(value) + "'"
  else:
   match = " = '" + str(value) + "'"
  self.DoFindSelect(query, match)

 def Found(self, query, found):
  if found:
   return self.FindPath(query)
  return []

 def FindValue(self, value, pattern, query, last_value, last_pattern):
  if last_value == value and pattern == last_pattern:
   found = query.first()
  else:
   self.FindSelect(value, pattern, query)
   found = query.next()
  return self.Found(query, found)

 def FindNext(self, query):
  found = query.next()
  if not found:
   found = query.first()
  return self.Found(query, found)

 def FindPrev(self, query):
  found = query.previous()
  if not found:
   found = query.last()
  return self.Found(query, found)

 def FindThread(self, c):
  if c.direction == 0 or c.value != c.last_value or c.pattern != c.last_pattern:
   ids = self.FindValue(c.value, c.pattern, c.query, c.last_value, c.last_pattern)
  elif c.direction > 0:
   ids = self.FindNext(c.query)
  else:
   ids = self.FindPrev(c.query)
  return (True, ids)

 def Find(self, value, direction, pattern, context, callback):
  class Context():
   def __init__(self, *x):
    self.value, self.direction, self.pattern, self.query, self.last_value, self.last_pattern = x
   def Update(self, *x):
    self.value, self.direction, self.pattern, self.last_value, self.last_pattern = x + (self.value, self.pattern)
  if len(context):
   context[0].Update(value, direction, pattern)
  else:
   context.append(Context(value, direction, pattern, QSqlQuery(self.glb.db), None, None))
  # Use a thread so the UI is not blocked during the SELECT
  thread = Thread(self.FindThread, context[0])
  thread.done.connect(lambda ids, t=thread, c=callback: self.FindDone(t, c, ids), Qt.QueuedConnection)
  thread.start()

 def FindDone(self, thread, callback, ids):
  callback(ids)

# Context-sensitive call graph data model

class CallGraphModel(CallGraphModelBase):

 def __init__(self, glb, parent=None):
  super(CallGraphModel, self).__init__(glb, parent)

 def GetRoot(self):
  return CallGraphRootItem(self.glb, self.params)

 def columnCount(self, parent=None):
  if self.params.have_ipc:
   return 12
  else:
   return 7

 def columnHeader(self, column):
  if self.params.have_ipc:
   headers = ["Call Path", "Object", "Count ", "Time (ns) ", "Time (%) ", "Insn Cnt", "Insn Cnt (%)", "Cyc Cnt", "Cyc Cnt (%)", "IPC", "Branch Count ", "Branch Count (%) "]
  else:
   headers = ["Call Path", "Object", "Count ", "Time (ns) ", "Time (%) ", "Branch Count ", "Branch Count (%) "]
  return headers[column]

 def columnAlignment(self, column):
  if self.params.have_ipc:
   alignment = [ Qt.AlignLeft, Qt.AlignLeft, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight ]
  else:
   alignment = [ Qt.AlignLeft, Qt.AlignLeft, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight ]
  return alignment[column]

 def DoFindSelect(self, query, match):
  QueryExec(query, "SELECT call_path_id, comm_id, thread_id"
      " FROM calls"
      " INNER JOIN call_paths ON calls.call_path_id = call_paths.id"
      " INNER JOIN symbols ON call_paths.symbol_id = symbols.id"
      " WHERE calls.id <> 0"
      " AND symbols.name" + match +
      " GROUP BY comm_id, thread_id, call_path_id"
      " ORDER BY comm_id, thread_id, call_path_id")

 def FindPath(self, query):
  # Turn the query result into a list of ids that the tree view can walk
  # to open the tree at the right place.
  ids = []
  parent_id = query.value(0)
  while parent_id:
   ids.insert(0, parent_id)
   q2 = QSqlQuery(self.glb.db)
   QueryExec(q2, "SELECT parent_id"
     " FROM call_paths"
     " WHERE id = " + str(parent_id))
   if not q2.next():
    break
   parent_id = q2.value(0)
  # The call path root is not used
  if ids[0] == 1:
   del ids[0]
  ids.insert(0, query.value(2))
  ids.insert(0, query.value(1))
  return ids

# Call tree data model level 2+ item base

class CallTreeLevelTwoPlusItemBase(CallGraphLevelItemBase):

 def __init__(self, glb, params, row, comm_id, thread_id, calls_id, call_time, time, insn_cnt, cyc_cnt, branch_count, parent_item):
  super(CallTreeLevelTwoPlusItemBase, self).__init__(glb, params, row, parent_item)
  self.comm_id = comm_id
  self.thread_id = thread_id
  self.calls_id = calls_id
  self.call_time = call_time
  self.time = time
  self.insn_cnt = insn_cnt
  self.cyc_cnt = cyc_cnt
  self.branch_count = branch_count

 def Select(self):
  self.query_done = True
  if self.calls_id == 0:
   comm_thread = " AND comm_id = " + str(self.comm_id) + " AND thread_id = " + str(self.thread_id)
  else:
   comm_thread = ""
  if self.params.have_ipc:
   ipc_str = ", insn_count, cyc_count"
  else:
   ipc_str = ""
  query = QSqlQuery(self.glb.db)
  QueryExec(query, "SELECT calls.id, name, short_name, call_time, return_time - call_time" + ipc_str + ", branch_count"
     " FROM calls"
     " INNER JOIN call_paths ON calls.call_path_id = call_paths.id"
     " INNER JOIN symbols ON call_paths.symbol_id = symbols.id"
     " INNER JOIN dsos ON symbols.dso_id = dsos.id"
     " WHERE calls.parent_id = " + str(self.calls_id) + comm_thread +
     " ORDER BY call_time, calls.id")
  while query.next():
   if self.params.have_ipc:
    insn_cnt = int(query.value(5))
    cyc_cnt = int(query.value(6))
    branch_count = int(query.value(7))
   else:
    insn_cnt = 0
    cyc_cnt = 0
    branch_count = int(query.value(5))
   child_item = CallTreeLevelThreeItem(self.glb, self.params, self.child_count, self.comm_id, self.thread_id, query.value(0), query.value(1), query.value(2), query.value(3), int(query.value(4)), insn_cnt, cyc_cnt, branch_count, self)
   self.child_items.append(child_item)
   self.child_count += 1

# Call tree data model level three item

class CallTreeLevelThreeItem(CallTreeLevelTwoPlusItemBase):

 def __init__(self, glb, params, row, comm_id, thread_id, calls_id, name, dso, call_time, time, insn_cnt, cyc_cnt, branch_count, parent_item):
  super(CallTreeLevelThreeItem, self).__init__(glb, params, row, comm_id, thread_id, calls_id, call_time, time, insn_cnt, cyc_cnt, branch_count, parent_item)
  dso = dsoname(dso)
  if self.params.have_ipc:
   insn_pcnt = PercentToOneDP(insn_cnt, parent_item.insn_cnt)
   cyc_pcnt = PercentToOneDP(cyc_cnt, parent_item.cyc_cnt)
   br_pcnt = PercentToOneDP(branch_count, parent_item.branch_count)
   ipc = CalcIPC(cyc_cnt, insn_cnt)
   self.data = [ name, dso, str(call_time), str(time), PercentToOneDP(time, parent_item.time), str(insn_cnt), insn_pcnt, str(cyc_cnt), cyc_pcnt, ipc, str(branch_count), br_pcnt ]
  else:
   self.data = [ name, dso, str(call_time), str(time), PercentToOneDP(time, parent_item.time), str(branch_count), PercentToOneDP(branch_count, parent_item.branch_count) ]
  self.dbid = calls_id

# Call tree data model level two item

class CallTreeLevelTwoItem(CallTreeLevelTwoPlusItemBase):

 def __init__(self, glb, params, row, comm_id, thread_id, pid, tid, parent_item):
  super(CallTreeLevelTwoItem, self).__init__(glb, params, row, comm_id, thread_id, 0, 0, 0, 0, 0, 0, parent_item)
  if self.params.have_ipc:
   self.data = [str(pid) + ":" + str(tid), "", "", "", "", "", "", "", "", "", "", ""]
  else:
   self.data = [str(pid) + ":" + str(tid), "", "", "", "", "", ""]
  self.dbid = thread_id

 def Select(self):
  super(CallTreeLevelTwoItem, self).Select()
  for child_item in self.child_items:
   self.time += child_item.time
   self.insn_cnt += child_item.insn_cnt
   self.cyc_cnt += child_item.cyc_cnt
   self.branch_count += child_item.branch_count
  for child_item in self.child_items:
   child_item.data[4] = PercentToOneDP(child_item.time, self.time)
   if self.params.have_ipc:
    child_item.data[6] = PercentToOneDP(child_item.insn_cnt, self.insn_cnt)
    child_item.data[8] = PercentToOneDP(child_item.cyc_cnt, self.cyc_cnt)
    child_item.data[11] = PercentToOneDP(child_item.branch_count, self.branch_count)
   else:
    child_item.data[6] = PercentToOneDP(child_item.branch_count, self.branch_count)

# Call tree data model level one item

class CallTreeLevelOneItem(CallGraphLevelItemBase):

 def __init__(self, glb, params, row, comm_id, comm, parent_item):
  super(CallTreeLevelOneItem, self).__init__(glb, params, row, parent_item)
  if self.params.have_ipc:
   self.data = [comm, "", "", "", "", "", "", "", "", "", "", ""]
  else:
   self.data = [comm, "", "", "", "", "", ""]
  self.dbid = comm_id

 def Select(self):
  self.query_done = True
  query = QSqlQuery(self.glb.db)
  QueryExec(query, "SELECT thread_id, pid, tid"
     " FROM comm_threads"
     " INNER JOIN threads ON thread_id = threads.id"
     " WHERE comm_id = " + str(self.dbid))
  while query.next():
   child_item = CallTreeLevelTwoItem(self.glb, self.params, self.child_count, self.dbid, query.value(0), query.value(1), query.value(2), self)
   self.child_items.append(child_item)
   self.child_count += 1

# Call tree data model root item

class CallTreeRootItem(CallGraphLevelItemBase):

 def __init__(self, glb, params):
  super(CallTreeRootItem, self).__init__(glb, params, 0, None)
  self.dbid = 0
  self.query_done = True
  if_has_calls = ""
  if IsSelectable(glb.db, "comms", columns = "has_calls"):
   if_has_calls = " WHERE has_calls = " + glb.dbref.TRUE
  query = QSqlQuery(glb.db)
  QueryExec(query, "SELECT id, comm FROM comms" + if_has_calls)
  while query.next():
   if not query.value(0):
    continue
   child_item = CallTreeLevelOneItem(glb, params, self.child_count, query.value(0), query.value(1), self)
   self.child_items.append(child_item)
   self.child_count += 1

# Call Tree data model

class CallTreeModel(CallGraphModelBase):

 def __init__(self, glb, parent=None):
  super(CallTreeModel, self).__init__(glb, parent)

 def GetRoot(self):
  return CallTreeRootItem(self.glb, self.params)

 def columnCount(self, parent=None):
  if self.params.have_ipc:
   return 12
  else:
   return 7

 def columnHeader(self, column):
  if self.params.have_ipc:
   headers = ["Call Path", "Object", "Call Time", "Time (ns) ", "Time (%) ", "Insn Cnt", "Insn Cnt (%)", "Cyc Cnt", "Cyc Cnt (%)", "IPC", "Branch Count ", "Branch Count (%) "]
  else:
   headers = ["Call Path", "Object", "Call Time", "Time (ns) ", "Time (%) ", "Branch Count ", "Branch Count (%) "]
  return headers[column]

 def columnAlignment(self, column):
  if self.params.have_ipc:
   alignment = [ Qt.AlignLeft, Qt.AlignLeft, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight ]
  else:
   alignment = [ Qt.AlignLeft, Qt.AlignLeft, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight, Qt.AlignRight ]
  return alignment[column]

 def DoFindSelect(self, query, match):
  QueryExec(query, "SELECT calls.id, comm_id, thread_id"
      " FROM calls"
      " INNER JOIN call_paths ON calls.call_path_id = call_paths.id"
      " INNER JOIN symbols ON call_paths.symbol_id = symbols.id"
      " WHERE calls.id <> 0"
      " AND symbols.name" + match +
      " ORDER BY comm_id, thread_id, call_time, calls.id")

 def FindPath(self, query):
  # Turn the query result into a list of ids that the tree view can walk
  # to open the tree at the right place.
  ids = []
  parent_id = query.value(0)
  while parent_id:
   ids.insert(0, parent_id)
   q2 = QSqlQuery(self.glb.db)
   QueryExec(q2, "SELECT parent_id"
     " FROM calls"
     " WHERE id = " + str(parent_id))
   if not q2.next():
    break
   parent_id = q2.value(0)
  ids.insert(0, query.value(2))
  ids.insert(0, query.value(1))
  return ids

# Vertical layout

class HBoxLayout(QHBoxLayout):

 def __init__(self, *children):
  super(HBoxLayout, self).__init__()

  self.layout().setContentsMargins(0, 0, 0, 0)
  for child in children:
   if child.isWidgetType():
    self.layout().addWidget(child)
   else:
    self.layout().addLayout(child)

# Horizontal layout

class VBoxLayout(QVBoxLayout):

 def __init__(self, *children):
  super(VBoxLayout, self).__init__()

  self.layout().setContentsMargins(0, 0, 0, 0)
  for child in children:
   if child.isWidgetType():
    self.layout().addWidget(child)
   else:
    self.layout().addLayout(child)

# Vertical layout widget

class VBox():

 def __init__(self, *children):
  self.vbox = QWidget()
  self.vbox.setLayout(VBoxLayout(*children))

 def Widget(self):
  return self.vbox

# Tree window base

class TreeWindowBase(QMdiSubWindow):

 def __init__(self, parent=None):
  super(TreeWindowBase, self).__init__(parent)

  self.model = None
  self.find_bar = None

  self.view = QTreeView()
  self.view.setSelectionMode(QAbstractItemView.ContiguousSelection)
  self.view.CopyCellsToClipboard = CopyTreeCellsToClipboard

  self.context_menu = TreeContextMenu(self.view)

 def DisplayFound(self, ids):
  if not len(ids):
   return False
  parent = QModelIndex()
  for dbid in ids:
   found = False
   n = self.model.rowCount(parent)
   for row in xrange(n):
    child = self.model.index(row, 0, parent)
    if child.internalPointer().dbid == dbid:
     found = True
     self.view.setExpanded(parent, True)
     self.view.setCurrentIndex(child)
     parent = child
     break
   if not found:
    break
  return found

 def Find(self, value, direction, pattern, context):
  self.view.setFocus()
  self.find_bar.Busy()
  self.model.Find(value, direction, pattern, context, self.FindDone)

 def FindDone(self, ids):
  found = True
  if not self.DisplayFound(ids):
   found = False
  self.find_bar.Idle()
  if not found:
   self.find_bar.NotFound()


# Context-sensitive call graph window

class CallGraphWindow(TreeWindowBase):

 def __init__(self, glb, parent=None):
  super(CallGraphWindow, self).__init__(parent)

  self.model = LookupCreateModel("Context-Sensitive Call Graph", lambda x=glb: CallGraphModel(x))

  self.view.setModel(self.model)

  for c, w in ((0, 250), (1, 100), (2, 60), (3, 70), (4, 70), (5, 100)):
   self.view.setColumnWidth(c, w)

  self.find_bar = FindBar(self, self)

  self.vbox = VBox(self.view, self.find_bar.Widget())

  self.setWidget(self.vbox.Widget())

  AddSubWindow(glb.mainwindow.mdi_area, self, "Context-Sensitive Call Graph")

# Call tree window

class CallTreeWindow(TreeWindowBase):

 def __init__(self, glb, parent=None, thread_at_time=None):
  super(CallTreeWindow, self).__init__(parent)

  self.model = LookupCreateModel("Call Tree", lambda x=glb: CallTreeModel(x))

  self.view.setModel(self.model)

  for c, w in ((0, 230), (1, 100), (2, 100), (3, 70), (4, 70), (5, 100)):
   self.view.setColumnWidth(c, w)

  self.find_bar = FindBar(self, self)

  self.vbox = VBox(self.view, self.find_bar.Widget())

  self.setWidget(self.vbox.Widget())

  AddSubWindow(glb.mainwindow.mdi_area, self, "Call Tree")

  if thread_at_time:
   self.DisplayThreadAtTime(*thread_at_time)

 def DisplayThreadAtTime(self, comm_id, thread_id, time):
  parent = QModelIndex()
  for dbid in (comm_id, thread_id):
   found = False
   n = self.model.rowCount(parent)
   for row in xrange(n):
    child = self.model.index(row, 0, parent)
    if child.internalPointer().dbid == dbid:
     found = True
     self.view.setExpanded(parent, True)
     self.view.setCurrentIndex(child)
     parent = child
     break
   if not found:
    return
  found = False
  while True:
   n = self.model.rowCount(parent)
   if not n:
    return
   last_child = None
   for row in xrange(n):
    self.view.setExpanded(parent, True)
    child = self.model.index(row, 0, parent)
    child_call_time = child.internalPointer().call_time
    if child_call_time < time:
     last_child = child
    elif child_call_time == time:
     self.view.setCurrentIndex(child)
     return
    elif child_call_time > time:
     break
   if not last_child:
    if not found:
     child = self.model.index(0, 0, parent)
     self.view.setExpanded(parent, True)
     self.view.setCurrentIndex(child)
    return
   found = True
   self.view.setExpanded(parent, True)
   self.view.setCurrentIndex(last_child)
   parent = last_child

# ExecComm() gets the comm_id of the command string that was set when the process exec'd i.e. the program name

def ExecComm(db, thread_id, time):
 query = QSqlQuery(db)
 QueryExec(query, "SELECT comm_threads.comm_id, comms.c_time, comms.exec_flag"
    " FROM comm_threads"
    " INNER JOIN comms ON comms.id = comm_threads.comm_id"
    " WHERE comm_threads.thread_id = " + str(thread_id) +
    " ORDER BY comms.c_time, comms.id")
 first = None
 last = None
 while query.next():
  if first is None:
   first = query.value(0)
  if query.value(2) and Decimal(query.value(1)) <= Decimal(time):
   last = query.value(0)
 if not(last is None):
  return last
 return first

# Container for (x, y) data

class XY():
 def __init__(self, x=0, y=0):
  self.x = x
  self.y = y

 def __str__(self):
  return "XY({}, {})".format(str(self.x), str(self.y))

# Container for sub-range data

class Subrange():
 def __init__(self, lo=0, hi=0):
  self.lo = lo
  self.hi = hi

 def __str__(self):
  return "Subrange({}, {})".format(str(self.lo), str(self.hi))

# Graph data region base class

class GraphDataRegion(object):

 def __init__(self, key, title = "", ordinal = ""):
  self.key = key
  self.title = title
  self.ordinal = ordinal

# Function to sort GraphDataRegion

def GraphDataRegionOrdinal(data_region):
 return data_region.ordinal

# Attributes for a graph region

class GraphRegionAttribute():

 def __init__(self, colour):
  self.colour = colour

# Switch graph data region represents a task

class SwitchGraphDataRegion(GraphDataRegion):

 def __init__(self, key, exec_comm_id, pid, tid, comm, thread_id, comm_id):
  super(SwitchGraphDataRegion, self).__init__(key)

  self.title = str(pid) + " / " + str(tid) + " " + comm
  # Order graph legend within exec comm by pid / tid / time
  self.ordinal = str(pid).rjust(16) + str(exec_comm_id).rjust(8) + str(tid).rjust(16)
  self.exec_comm_id = exec_comm_id
  self.pid = pid
  self.tid = tid
  self.comm = comm
  self.thread_id = thread_id
  self.comm_id = comm_id

# Graph data point

class GraphDataPoint():

 def __init__(self, data, index, x, y, altx=None, alty=None, hregion=None, vregion=None):
  self.data = data
  self.index = index
  self.x = x
  self.y = y
  self.altx = altx
  self.alty = alty
  self.hregion = hregion
  self.vregion = vregion

# Graph data (single graph) base class

class GraphData(object):

 def __init__(self, collection, xbase=Decimal(0), ybase=Decimal(0)):
  self.collection = collection
  self.points = []
  self.xbase = xbase
  self.ybase = ybase
  self.title = ""

 def AddPoint(self, x, y, altx=None, alty=None, hregion=None, vregion=None):
  index = len(self.points)

  x = float(Decimal(x) - self.xbase)
  y = float(Decimal(y) - self.ybase)

  self.points.append(GraphDataPoint(self, index, x, y, altx, alty, hregion, vregion))

 def XToData(self, x):
  return Decimal(x) + self.xbase

 def YToData(self, y):
  return Decimal(y) + self.ybase

# Switch graph data (for one CPU)

class SwitchGraphData(GraphData):

 def __init__(self, db, collection, cpu, xbase):
  super(SwitchGraphData, self).__init__(collection, xbase)

  self.cpu = cpu
  self.title = "CPU " + str(cpu)
  self.SelectSwitches(db)

 def SelectComms(self, db, thread_id, last_comm_id, start_time, end_time):
  query = QSqlQuery(db)
  QueryExec(query, "SELECT id, c_time"
     " FROM comms"
     " WHERE c_thread_id = " + str(thread_id) +
     " AND exec_flag = " + self.collection.glb.dbref.TRUE +
     " AND c_time >= " + str(start_time) +
     " AND c_time <= " + str(end_time) +
     " ORDER BY c_time, id")
  while query.next():
   comm_id = query.value(0)
   if comm_id == last_comm_id:
    continue
   time = query.value(1)
   hregion = self.HRegion(db, thread_id, comm_id, time)
   self.AddPoint(time, 1000, None, None, hregion)

 def SelectSwitches(self, db):
  last_time = None
  last_comm_id = None
  last_thread_id = None
  query = QSqlQuery(db)
  QueryExec(query, "SELECT time, thread_out_id, thread_in_id, comm_out_id, comm_in_id, flags"
     " FROM context_switches"
     " WHERE machine_id = " + str(self.collection.machine_id) +
     " AND cpu = " + str(self.cpu) +
     " ORDER BY time, id")
  while query.next():
   flags = int(query.value(5))
   if flags & 1:
    # Schedule-out: detect and add exec's
    if last_thread_id == query.value(1) and last_comm_id is not None and last_comm_id != query.value(3):
     self.SelectComms(db, last_thread_id, last_comm_id, last_time, query.value(0))
    continue
   # Schedule-in: add data point
   if len(self.points) == 0:
    start_time = self.collection.glb.StartTime(self.collection.machine_id)
    hregion = self.HRegion(db, query.value(1), query.value(3), start_time)
    self.AddPoint(start_time, 1000, None, None, hregion)
   time = query.value(0)
   comm_id = query.value(4)
   thread_id = query.value(2)
   hregion = self.HRegion(db, thread_id, comm_id, time)
   self.AddPoint(time, 1000, None, None, hregion)
   last_time = time
   last_comm_id = comm_id
   last_thread_id = thread_id

 def NewHRegion(self, db, key, thread_id, comm_id, time):
  exec_comm_id = ExecComm(db, thread_id, time)
  query = QSqlQuery(db)
  QueryExec(query, "SELECT pid, tid FROM threads WHERE id = " + str(thread_id))
  if query.next():
   pid = query.value(0)
   tid = query.value(1)
  else:
   pid = -1
   tid = -1
  query = QSqlQuery(db)
  QueryExec(query, "SELECT comm FROM comms WHERE id = " + str(comm_id))
  if query.next():
   comm = query.value(0)
  else:
   comm = ""
  return SwitchGraphDataRegion(key, exec_comm_id, pid, tid, comm, thread_id, comm_id)

 def HRegion(self, db, thread_id, comm_id, time):
  key = str(thread_id) + ":" + str(comm_id)
  hregion = self.collection.LookupHRegion(key)
  if hregion is None:
   hregion = self.NewHRegion(db, key, thread_id, comm_id, time)
   self.collection.AddHRegion(key, hregion)
  return hregion

# Graph data collection (multiple related graphs) base class

class GraphDataCollection(object):

 def __init__(self, glb):
  self.glb = glb
  self.data = []
  self.hregions = {}
  self.xrangelo = None
  self.xrangehi = None
  self.yrangelo = None
  self.yrangehi = None
  self.dp = XY(0, 0)

 def AddGraphData(self, data):
  self.data.append(data)

 def LookupHRegion(self, key):
  if key in self.hregions:
   return self.hregions[key]
  return None

 def AddHRegion(self, key, hregion):
  self.hregions[key] = hregion

# Switch graph data collection (SwitchGraphData for each CPU)

class SwitchGraphDataCollection(GraphDataCollection):

 def __init__(self, glb, db, machine_id):
  super(SwitchGraphDataCollection, self).__init__(glb)

  self.machine_id = machine_id
  self.cpus = self.SelectCPUs(db)

  self.xrangelo = glb.StartTime(machine_id)
  self.xrangehi = glb.FinishTime(machine_id)

  self.yrangelo = Decimal(0)
  self.yrangehi = Decimal(1000)

  for cpu in self.cpus:
   self.AddGraphData(SwitchGraphData(db, self, cpu, self.xrangelo))

 def SelectCPUs(self, db):
  cpus = []
  query = QSqlQuery(db)
  QueryExec(query, "SELECT DISTINCT cpu"
     " FROM context_switches"
     " WHERE machine_id = " + str(self.machine_id))
  while query.next():
   cpus.append(int(query.value(0)))
  return sorted(cpus)

# Switch graph data graphics item displays the graphed data

class SwitchGraphDataGraphicsItem(QGraphicsItem):

 def __init__(self, data, graph_width, graph_height, attrs, event_handler, parent=None):
  super(SwitchGraphDataGraphicsItem, self).__init__(parent)

  self.data = data
  self.graph_width = graph_width
  self.graph_height = graph_height
  self.attrs = attrs
  self.event_handler = event_handler
  self.setAcceptHoverEvents(True)

 def boundingRect(self):
  return QRectF(0, 0, self.graph_width, self.graph_height)

 def PaintPoint(self, painter, last, x):
  if not(last is None or last.hregion.pid == 0 or x < self.attrs.subrange.x.lo):
   if last.x < self.attrs.subrange.x.lo:
    x0 = self.attrs.subrange.x.lo
   else:
    x0 = last.x
   if x > self.attrs.subrange.x.hi:
    x1 = self.attrs.subrange.x.hi
   else:
    x1 = x - 1
   x0 = self.attrs.XToPixel(x0)
   x1 = self.attrs.XToPixel(x1)

   y0 = self.attrs.YToPixel(last.y)

   colour = self.attrs.region_attributes[last.hregion.key].colour

   width = x1 - x0 + 1
   if width < 2:
    painter.setPen(colour)
    painter.drawLine(x0, self.graph_height - y0, x0, self.graph_height)
   else:
    painter.fillRect(x0, self.graph_height - y0, width, self.graph_height - 1, colour)

 def paint(self, painter, option, widget):
  last = None
  for point in self.data.points:
   self.PaintPoint(painter, last, point.x)
   if point.x > self.attrs.subrange.x.hi:
    break;
   last = point
  self.PaintPoint(painter, last, self.attrs.subrange.x.hi + 1)

 def BinarySearchPoint(self, target):
  lower_pos = 0
  higher_pos = len(self.data.points)
  while True:
   pos = int((lower_pos + higher_pos) / 2)
   val = self.data.points[pos].x
   if target >= val:
    lower_pos = pos
   else:
    higher_pos = pos
   if higher_pos <= lower_pos + 1:
    return lower_pos

 def XPixelToData(self, x):
  x = self.attrs.PixelToX(x)
  if x < self.data.points[0].x:
   x = 0
   pos = 0
   low = True
  else:
   pos = self.BinarySearchPoint(x)
   low = False
  return (low, pos, self.data.XToData(x))

 def EventToData(self, event):
  no_data = (None,) * 4
  if len(self.data.points) < 1:
   return no_data
  x = event.pos().x()
  if x < 0:
   return no_data
  low0, pos0, time_from = self.XPixelToData(x)
  low1, pos1, time_to = self.XPixelToData(x + 1)
  hregions = set()
  hregion_times = []
  if not low1:
   for i in xrange(pos0, pos1 + 1):
    hregion = self.data.points[i].hregion
    hregions.add(hregion)
    if i == pos0:
     time = time_from
    else:
     time = self.data.XToData(self.data.points[i].x)
    hregion_times.append((hregion, time))
  return (time_from, time_to, hregions, hregion_times)

 def hoverMoveEvent(self, event):
  time_from, time_to, hregions, hregion_times = self.EventToData(event)
  if time_from is not None:
   self.event_handler.PointEvent(self.data.cpu, time_from, time_to, hregions)

 def hoverLeaveEvent(self, event):
  self.event_handler.NoPointEvent()

 def mousePressEvent(self, event):
  if event.button() != Qt.RightButton:
   super(SwitchGraphDataGraphicsItem, self).mousePressEvent(event)
   return
  time_from, time_to, hregions, hregion_times = self.EventToData(event)
  if hregion_times:
   self.event_handler.RightClickEvent(self.data.cpu, hregion_times, event.screenPos())

# X-axis graphics item

class XAxisGraphicsItem(QGraphicsItem):

 def __init__(self, width, parent=None):
  super(XAxisGraphicsItem, self).__init__(parent)

  self.width = width
  self.max_mark_sz = 4
  self.height = self.max_mark_sz + 1

 def boundingRect(self):
  return QRectF(0, 0, self.width, self.height)

 def Step(self):
  attrs = self.parentItem().attrs
  subrange = attrs.subrange.x
  t = subrange.hi - subrange.lo
  s = (3.0 * t) / self.width
  n = 1.0
  while s > n:
   n = n * 10.0
  return n

 def PaintMarks(self, painter, at_y, lo, hi, step, i):
  attrs = self.parentItem().attrs
  x = lo
  while x <= hi:
   xp = attrs.XToPixel(x)
   if i % 10:
    if i % 5:
     sz = 1
    else:
     sz = 2
   else:
    sz = self.max_mark_sz
    i = 0
   painter.drawLine(xp, at_y, xp, at_y + sz)
   x += step
   i += 1

 def paint(self, painter, option, widget):
  # Using QPainter::drawLine(int x1, int y1, int x2, int y2) so x2 = width -1
  painter.drawLine(0, 0, self.width - 1, 0)
  n = self.Step()
  attrs = self.parentItem().attrs
  subrange = attrs.subrange.x
  if subrange.lo:
   x_offset = n - (subrange.lo % n)
  else:
   x_offset = 0.0
  x = subrange.lo + x_offset
  i = (x / n) % 10
  self.PaintMarks(painter, 0, x, subrange.hi, n, i)

 def ScaleDimensions(self):
  n = self.Step()
  attrs = self.parentItem().attrs
  lo = attrs.subrange.x.lo
  hi = (n * 10.0) + lo
  width = attrs.XToPixel(hi)
  if width > 500:
   width = 0
  return (n, lo, hi, width)

 def PaintScale(self, painter, at_x, at_y):
  n, lo, hi, width = self.ScaleDimensions()
  if not width:
   return
  painter.drawLine(at_x, at_y, at_x + width, at_y)
  self.PaintMarks(painter, at_y, lo, hi, n, 0)

 def ScaleWidth(self):
  n, lo, hi, width = self.ScaleDimensions()
  return width

 def ScaleHeight(self):
  return self.height

 def ScaleUnit(self):
  return self.Step() * 10

# Scale graphics item base class

class ScaleGraphicsItem(QGraphicsItem):

 def __init__(self, axis, parent=None):
  super(ScaleGraphicsItem, self).__init__(parent)
  self.axis = axis

 def boundingRect(self):
  scale_width = self.axis.ScaleWidth()
  if not scale_width:
   return QRectF()
  return QRectF(0, 0, self.axis.ScaleWidth() + 100, self.axis.ScaleHeight())

 def paint(self, painter, option, widget):
  scale_width = self.axis.ScaleWidth()
  if not scale_width:
   return
  self.axis.PaintScale(painter, 0, 5)
  x = scale_width + 4
  painter.drawText(QPointF(x, 10), self.Text())

 def Unit(self):
  return self.axis.ScaleUnit()

 def Text(self):
  return ""

# Switch graph scale graphics item

class SwitchScaleGraphicsItem(ScaleGraphicsItem):

 def __init__(self, axis, parent=None):
  super(SwitchScaleGraphicsItem, self).__init__(axis, parent)

 def Text(self):
  unit = self.Unit()
  if unit >= 1000000000:
   unit = int(unit / 1000000000)
   us = "s"
  elif unit >= 1000000:
   unit = int(unit / 1000000)
   us = "ms"
  elif unit >= 1000:
   unit = int(unit / 1000)
   us = "us"
  else:
   unit = int(unit)
   us = "ns"
  return " = " + str(unit) + " " + us

# Switch graph graphics item contains graph title, scale, x/y-axis, and the graphed data

class SwitchGraphGraphicsItem(QGraphicsItem):

 def __init__(self, collection, data, attrs, event_handler, first, parent=None):
  super(SwitchGraphGraphicsItem, self).__init__(parent)
  self.collection = collection
  self.data = data
  self.attrs = attrs
  self.event_handler = event_handler

  margin = 20
  title_width = 50

  self.title_graphics = QGraphicsSimpleTextItem(data.title, self)

  self.title_graphics.setPos(margin, margin)
  graph_width = attrs.XToPixel(attrs.subrange.x.hi) + 1
  graph_height = attrs.YToPixel(attrs.subrange.y.hi) + 1

  self.graph_origin_x = margin + title_width + margin
  self.graph_origin_y = graph_height + margin

  x_axis_size = 1
  y_axis_size = 1
  self.yline = QGraphicsLineItem(0, 0, 0, graph_height, self)

  self.x_axis = XAxisGraphicsItem(graph_width, self)
  self.x_axis.setPos(self.graph_origin_x, self.graph_origin_y + 1)

  if first:
   self.scale_item = SwitchScaleGraphicsItem(self.x_axis, self)
   self.scale_item.setPos(self.graph_origin_x, self.graph_origin_y + 10)

  self.yline.setPos(self.graph_origin_x - y_axis_size, self.graph_origin_y - graph_height)

  self.axis_point = QGraphicsLineItem(0, 0, 0, 0, self)
  self.axis_point.setPos(self.graph_origin_x - 1, self.graph_origin_y +1)

  self.width = self.graph_origin_x + graph_width + margin
  self.height = self.graph_origin_y + margin

  self.graph = SwitchGraphDataGraphicsItem(data, graph_width, graph_height, attrs, event_handler, self)
  self.graph.setPos(self.graph_origin_x, self.graph_origin_y - graph_height)

  if parent and 'EnableRubberBand' in dir(parent):
   parent.EnableRubberBand(self.graph_origin_x, self.graph_origin_x + graph_width - 1, self)

 def boundingRect(self):
  return QRectF(0, 0, self.width, self.height)

 def paint(self, painter, option, widget):
  pass

 def RBXToPixel(self, x):
  return self.attrs.PixelToX(x - self.graph_origin_x)

 def RBXRangeToPixel(self, x0, x1):
  return (self.RBXToPixel(x0), self.RBXToPixel(x1 + 1))

 def RBPixelToTime(self, x):
  if x < self.data.points[0].x:
   return self.data.XToData(0)
  return self.data.XToData(x)

 def RBEventTimes(self, x0, x1):
  x0, x1 = self.RBXRangeToPixel(x0, x1)
  time_from = self.RBPixelToTime(x0)
  time_to = self.RBPixelToTime(x1)
  return (time_from, time_to)

 def RBEvent(self, x0, x1):
  time_from, time_to = self.RBEventTimes(x0, x1)
  self.event_handler.RangeEvent(time_from, time_to)

 def RBMoveEvent(self, x0, x1):
  if x1 < x0:
   x0, x1 = x1, x0
  self.RBEvent(x0, x1)

 def RBReleaseEvent(self, x0, x1, selection_state):
  if x1 < x0:
   x0, x1 = x1, x0
  x0, x1 = self.RBXRangeToPixel(x0, x1)
  self.event_handler.SelectEvent(x0, x1, selection_state)

# Graphics item to draw a vertical bracket (used to highlight "forward" sub-range)

class VerticalBracketGraphicsItem(QGraphicsItem):

 def __init__(self, parent=None):
  super(VerticalBracketGraphicsItem, self).__init__(parent)

  self.width = 0
  self.height = 0
  self.hide()

 def SetSize(self, width, height):
  self.width = width + 1
  self.height = height + 1

 def boundingRect(self):
  return QRectF(0, 0, self.width, self.height)

 def paint(self, painter, option, widget):
  colour = QColor(255, 255, 0, 32)
  painter.fillRect(0, 0, self.width, self.height, colour)
  x1 = self.width - 1
  y1 = self.height - 1
  painter.drawLine(0, 0, x1, 0)
  painter.drawLine(0, 0, 0, 3)
  painter.drawLine(x1, 0, x1, 3)
  painter.drawLine(0, y1, x1, y1)
  painter.drawLine(0, y1, 0, y1 - 3)
  painter.drawLine(x1, y1, x1, y1 - 3)

# Graphics item to contain graphs arranged vertically

class VertcalGraphSetGraphicsItem(QGraphicsItem):

 def __init__(self, collection, attrs, event_handler, child_class, parent=None):
  super(VertcalGraphSetGraphicsItem, self).__init__(parent)

  self.collection = collection

  self.top = 10

  self.width = 0
  self.height = self.top

  self.rubber_band = None
  self.rb_enabled = False

  first = True
  for data in collection.data:
   child = child_class(collection, data, attrs, event_handler, first, self)
   child.setPos(0, self.height + 1)
   rect = child.boundingRect()
   if rect.right() > self.width:
    self.width = rect.right()
   self.height = self.height + rect.bottom() + 1
   first = False

  self.bracket = VerticalBracketGraphicsItem(self)

 def EnableRubberBand(self, xlo, xhi, rb_event_handler):
  if self.rb_enabled:
   return
  self.rb_enabled = True
  self.rb_in_view = False
  self.setAcceptedMouseButtons(Qt.LeftButton)
  self.rb_xlo = xlo
  self.rb_xhi = xhi
  self.rb_event_handler = rb_event_handler
  self.mousePressEvent = self.MousePressEvent
  self.mouseMoveEvent = self.MouseMoveEvent
  self.mouseReleaseEvent = self.MouseReleaseEvent

 def boundingRect(self):
  return QRectF(0, 0, self.width, self.height)

 def paint(self, painter, option, widget):
  pass

 def RubberBandParent(self):
  scene = self.scene()
  view = scene.views()[0]
  viewport = view.viewport()
  return viewport

 def RubberBandSetGeometry(self, rect):
  scene_rectf = self.mapRectToScene(QRectF(rect))
  scene = self.scene()
  view = scene.views()[0]
  poly = view.mapFromScene(scene_rectf)
  self.rubber_band.setGeometry(poly.boundingRect())

 def SetSelection(self, selection_state):
  if self.rubber_band:
   if selection_state:
    self.RubberBandSetGeometry(selection_state)
    self.rubber_band.show()
   else:
    self.rubber_band.hide()

 def SetBracket(self, rect):
  if rect:
   x, y, width, height = rect.x(), rect.y(), rect.width(), rect.height()
   self.bracket.setPos(x, y)
   self.bracket.SetSize(width, height)
   self.bracket.show()
  else:
   self.bracket.hide()

 def RubberBandX(self, event):
  x = event.pos().toPoint().x()
  if x < self.rb_xlo:
   x = self.rb_xlo
  elif x > self.rb_xhi:
   x = self.rb_xhi
  else:
   self.rb_in_view = True
  return x

 def RubberBandRect(self, x):
  if self.rb_origin.x() <= x:
   width = x - self.rb_origin.x()
   rect = QRect(self.rb_origin, QSize(width, self.height))
  else:
   width = self.rb_origin.x() - x
   top_left = QPoint(self.rb_origin.x() - width, self.rb_origin.y())
   rect = QRect(top_left, QSize(width, self.height))
  return rect

 def MousePressEvent(self, event):
  self.rb_in_view = False
  x = self.RubberBandX(event)
  self.rb_origin = QPoint(x, self.top)
  if self.rubber_band is None:
   self.rubber_band = QRubberBand(QRubberBand.Rectangle, self.RubberBandParent())
  self.RubberBandSetGeometry(QRect(self.rb_origin, QSize(0, self.height)))
  if self.rb_in_view:
   self.rubber_band.show()
   self.rb_event_handler.RBMoveEvent(x, x)
  else:
   self.rubber_band.hide()

 def MouseMoveEvent(self, event):
  x = self.RubberBandX(event)
  rect = self.RubberBandRect(x)
  self.RubberBandSetGeometry(rect)
  if self.rb_in_view:
   self.rubber_band.show()
   self.rb_event_handler.RBMoveEvent(self.rb_origin.x(), x)

 def MouseReleaseEvent(self, event):
  x = self.RubberBandX(event)
  if self.rb_in_view:
   selection_state = self.RubberBandRect(x)
  else:
   selection_state = None
  self.rb_event_handler.RBReleaseEvent(self.rb_origin.x(), x, selection_state)

# Switch graph legend data model

class SwitchGraphLegendModel(QAbstractTableModel):

 def __init__(self, collection, region_attributes, parent=None):
  super(SwitchGraphLegendModel, self).__init__(parent)

  self.region_attributes = region_attributes

  self.child_items = sorted(collection.hregions.values(), key=GraphDataRegionOrdinal)
  self.child_count = len(self.child_items)

  self.highlight_set = set()

  self.column_headers = ("pid", "tid", "comm")

 def rowCount(self, parent):
  return self.child_count

 def headerData(self, section, orientation, role):
  if role != Qt.DisplayRole:
   return None
  if orientation != Qt.Horizontal:
   return None
  return self.columnHeader(section)

 def index(self, row, column, parent):
  return self.createIndex(row, column, self.child_items[row])

 def columnCount(self, parent=None):
  return len(self.column_headers)

 def columnHeader(self, column):
  return self.column_headers[column]

 def data(self, index, role):
  if role == Qt.BackgroundRole:
   child = self.child_items[index.row()]
   if child in self.highlight_set:
    return self.region_attributes[child.key].colour
   return None
  if role == Qt.ForegroundRole:
   child = self.child_items[index.row()]
   if child in self.highlight_set:
    return QColor(255, 255, 255)
   return self.region_attributes[child.key].colour
  if role != Qt.DisplayRole:
   return None
  hregion = self.child_items[index.row()]
  col = index.column()
  if col == 0:
   return hregion.pid
  if col == 1:
   return hregion.tid
  if col == 2:
   return hregion.comm
  return None

 def SetHighlight(self, row, set_highlight):
  child = self.child_items[row]
  top_left = self.createIndex(row, 0, child)
  bottom_right = self.createIndex(row, len(self.column_headers) - 1, child)
  self.dataChanged.emit(top_left, bottom_right)

 def Highlight(self, highlight_set):
  for row in xrange(self.child_count):
   child = self.child_items[row]
   if child in self.highlight_set:
    if child not in highlight_set:
     self.SetHighlight(row, False)
   elif child in highlight_set:
    self.SetHighlight(row, True)
  self.highlight_set = highlight_set

# Switch graph legend is a table

class SwitchGraphLegend(QWidget):

 def __init__(self, collection, region_attributes, parent=None):
  super(SwitchGraphLegend, self).__init__(parent)

  self.data_model = SwitchGraphLegendModel(collection, region_attributes)

  self.model = QSortFilterProxyModel()
  self.model.setSourceModel(self.data_model)

  self.view = QTableView()
  self.view.setModel(self.model)
  self.view.setEditTriggers(QAbstractItemView.NoEditTriggers)
  self.view.verticalHeader().setVisible(False)
  self.view.sortByColumn(-1, Qt.AscendingOrder)
  self.view.setSortingEnabled(True)
  self.view.resizeColumnsToContents()
  self.view.resizeRowsToContents()

  self.vbox = VBoxLayout(self.view)
  self.setLayout(self.vbox)

  sz1 = self.view.columnWidth(0) + self.view.columnWidth(1) + self.view.columnWidth(2) + 2
  sz1 = sz1 + self.view.verticalScrollBar().sizeHint().width()
  self.saved_size = sz1

 def resizeEvent(self, event):
  self.saved_size = self.size().width()
  super(SwitchGraphLegend, self).resizeEvent(event)

 def Highlight(self, highlight_set):
  self.data_model.Highlight(highlight_set)
  self.update()

 def changeEvent(self, event):
  if event.type() == QEvent.FontChange:
   self.view.resizeRowsToContents()
   self.view.resizeColumnsToContents()
   # Need to resize rows again after column resize
   self.view.resizeRowsToContents()
  super(SwitchGraphLegend, self).changeEvent(event)

# Random colour generation

def RGBColourTooLight(r, g, b):
 if g > 230:
  return True
 if g <= 160:
  return False
 if r <= 180 and g <= 180:
  return False
 if r < 60:
  return False
 return True

def GenerateColours(x):
 cs = [0]
 for i in xrange(1, x):
  cs.append(int((255.0 / i) + 0.5))
 colours = []
 for r in cs:
  for g in cs:
   for b in cs:
    # Exclude black and colours that look too light against a white background
--> --------------------

--> maximum size reached

--> --------------------