Home

Trevil - Tree Visualization Language

Trevil is a language for composing visualizations of unordered trees, such as the calling context trees produced by standard profilers.

Trevil is based on Trevis. It provides a language with which users can configure Trevis visualizations. Trevil is modeled after the ideas behind Conditional XPath, and it uses syntactic aspects of LPath. However, given that Trevis trees are unordered, Trevil does not support concepts in XPath related to document-order.

Types

Trevil supports four primitive types: long, double, boolean, and String. The four types correspond to the Java types of the same names, however, in Trevil String is a value type (Trevil does not support references). Trevil is strongly typed, that is, the type of an expression is known statically.

Node-Local Expressions

Trevil supports a simple expression language, inspired by Java. In addition to the standard Java equality operators (== and !=), Trevil also provides special String comparison operators:

  • a=~b -- Does String a match String b (b must contain a legal regular expression)?
  • a=^b -- Does String a start with String b?
  • a=$b -- Does String a end with String b?

Aggregation Expressions

An aggregation expression computes an aggregate value over a set of nodes selected by a path expression.

Trevil supports the following aggregation (aka reduction) constructs (which were inspired to some degree by DTrace and XPath 2.0):

  • @and -- boolean
  • @or -- boolean
  • @sum -- double and long
  • @max -- double and long
  • @min -- double and long
  • @concat -- String
  • @count -- syntactic sugar: @count(path) == @sum(path, 1)
  • @each -- syntactic sugar: @each(path, cond) == @and(path, cond)
  • @some -- syntactic sugar: @some(path) == @or(path, true)
  • @no -- syntactic sugar: @no(path) == @and(path, false) == !some(path)

Path Expressions

A PathExpression consists of a sequence of steps. A step is built from an axis, a step condition, and an optional closure operator:

  • step ::= axis condition closure
  • axis ::= '.' | '/' | '//' | '//.' | '\' | '\\' | '\\.' | '^'
  • condition ::= '_' | '[' expression ']'
  • closure ::= ( '*' | '+' )?

A condition can be an arbitrary Trevil expression (which may itself contain aggregation expressions), surrounded by square brackets. An underscore is syntactic sugar for [true].

Trevil supports transitive closure on steps as follows:

  • step a subpath containing the step exactly once
  • step* a subpath containing the step zero or more times
  • step+ a subpath containing the step one or more times

Axes

Trevil path expressions support the following immediate axes:

  • . -- self (the context node)
  • / -- child
  • \ -- parent

Given the fact that Trevil supports transitive closure on steps (as introduced by Conditional XPath), the transitive XPath axes (e.g., ancestor) can be expressed by combining the above immediate (e.g., parent) axes with closures.

The following table shows those XPath axes that are meaningful for unordered trees together with the corresponding Trevil notation.

XPath axis Trevil (axis and condition) Trevil (using immediate axis and closure)
self .[cond]
child /[cond]
descendant //[cond] /_*/[cond]
descendant_or_self //.[cond] /_*.[cond]
parent \[cond]
ancestor \\[cond] \_*\[cond]
ancestor_or_self \\.[cond] \_*.[cond]
root (not part of XPath) ^[cond] \\.[@no(\_) && cond]

Examples queries

Returns true if there is some (transitive) caller (an ancestor in the CCT) where the class name matches "[Ll]istener"?
@some(\\[Class=~"[Ll]istener"])
@or(\\[Class=~"[Ll]istener"], true)
@or(\\[true], Class=~"[Ll]istener")
@or(\\_, Class=~"[Ll]istener")
@count(\\[Class=~"[Ll]istener"])>0
@sum(\\[Class=~"[Ll]istener"], 1)>0

Returns true if there is some immediate caller (the parent in the CCT) where the class name matches "[Ll]istener"?
@some(\[Class=~"[Ll]istener"])
@or(\[Class=~"[Ll]istener"], true)

Are all transitive callers (the parent in the CCT) in a package starting with "org.eclipse."?
@each(\\[true], Package=^"org.eclipse.")
@each(\\_, Package=^"org.eclipse.")

Does this method call some method in class "java.util.HashMap"?
@some(/[Class=="java.util.HashMap"])

Does this method call some method that calls a method called "exit"?
@some(/[true]/[Method=="exit"])
@some(/_/[Method=="exit"])

Is there some descendant in a package starting with "org.eclipse." that calls a callee in a package starting with "java.awt."
@some(//[Package=^"org.eclipse"]/[Package=^"java.awt"])

Is this method in class "Main"?
@some(.[Class=="Main"])
Class=="Main"

Does this method call somebody?
@some(/_)

Does this method call nobody? (is it a leaf)
@no(/_)
! @some(/_)

Is this method called by somebody?
@some(\_)

Is this method called by nobody? (is it the root)
@no(\_)
! @some(\_)

Height of the node (number of ancestors, excluding self)?
@count(\\_)
@count(\_+)

Height of the node, plus one (number of ancestors, including self)?
@count(\\._)
@count(\_*)
@count(\\_) + 1

Inclusive sample count (this node's plus all its descendants)?
@sum(//._, ExclusiveSamples)
@sum(//_, ExclusiveSamples) + @sum(._, ExclusiveSamples)
@sum(//_, ExclusiveSamples) + ExclusiveSamples

Sample count of descendants and self in package java.util.**?
@sum(//.[Package=^"java.util."], ExclusiveSamples)

Sample count of callees (and their descendants) in package "org.eclipse.swt" invoked by a caller in package "org.eclipse.jdt"?
@sum(//[package=="org.eclipse.jdt"], @sum(//.[package=="org.eclipse.swt"], samples))
-- buggy: double-counts in cases of nesting!!!

Is there a descendant or self called "foo"?
@some(//.[Method=="packPopup"])
@some(/_*.[Method=="packPopup"])
@some(/_*/[Method=="packPopup"]) || @some(.[Method=="packPopup"])
@some(/_+/[Method=="packPopup"]) || @some(/[Method=="packPopup"]) || @some(.[Method=="packPopup"])

Is there a descendant called "foo"?
@some(//[Method=="packPopup"])
@some(/_*/[Method=="packPopup"])
@some(/_+/[Method=="packPopup"]) || @some(/[Method=="packPopup"])

What is the sample count of this node (which may be a loop node), excluding nested loop trees?
ExclusiveSamples + @sum(/[Kind!="loop"]+, ExclusiveSamples)

How many immediately nested loops exist?
@count(/[Kind=="loop"]/[Kind=="loop])

What is sum of the exclusive number of samples in method "objc_msgSendSuper" across all contexts where it invokes "windowProc"?
@sum(//[Method=="objc_msgSendSuper" && @some(/[Method=="windowProc"])], ExclusiveSamples)

What is the inclusive number of samples in method "play" in contexts where it invokes "control"?
@sum(//[Method=="objc_msgSendSuper" && @some(/[Method=="windowProc"])], @sum(//._, ExclusiveSamples))
-- buggy, double-counts in cases of nesting!!

What is my inclusive sample count divided by the root node's inclusive sample count?
@sum(//._, ExclusiveSamples) / (double)@sum(^_, @sum(//._, ExclusiveSamples) )
@sum(//._, ExclusiveSamples) / (double)@sum(\\.[@no(\_)], @sum(//._, ExclusiveSamples) )

A Note on Path Expressions for Unordered vs. Ordered Trees

Given that Trevis trees are unordered, (unlike XML or linguistic trees), Trevil does not (need to) support the following axes supported e.g. by LPath:

  • "following" (-->), "preceding" (<--),
  • "immediate_following" (->), "immediate_preceding" (<-),
  • "following_sibling" (==>), and "preceding_sibling" (<==),
  • "immeditate_following_sibling" (=>), and "immediate_preceding_sibling" (<=),