Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Comparing Two Versions

The call graphs of A Call Graph from the Code say which function calls which. A change is easier to judge by its call chains: the paths through the graph from where the service is entered to the functions at the end, each one a thing that happens when a request comes in. This section lists the chains of both versions, compares the graphs and the chains, and writes what changed as a text report, an HTML page and a drawing.

Entries and next calls

A chain starts at an entry, a function that no call of the program reaches, and the graph's queries found one: api.start. A chain is a sequence of call elements, each going on from where the one before it ended. What can follow a chain are the calls of its last function to functions of the program; external calls such as fetch end a chain and are not part of it:

(: The functions no call reaches: where the program is entered. :)
declare function graph:entries($graph as element(graph)) as xs:string* {
  $graph/function[not(@id = $graph/call/@to)]/@id
};

(: The calls a chain can go on with: the calls of its last function to
   functions of the program that the chain has not been through (so a
   cycle ends a chain). A chain is a sequence of calls. :)
declare function graph:next(
  $graph as element(graph),
  $chain as element(call)*
) as element(call)* {
  $graph/call[@from = $chain[last()]/@to][not(@external)]
             [not(@to = $chain/@from)]
};

The test not(@to = $chain/@from) keeps a chain from going through a function twice. The Vane service has no cycles, but a program with a function that calls itself, or two that call each other, would otherwise have chains without end.

Chains with a worklist

The chains can be made without a function that calls itself: keep a list of the chains that are not finished, the worklist, and take one chain off it at a time. A chain that cannot go on is finished; any other is put back once for each next call, one call longer. When the worklist is empty, every chain is finished:

(: Every chain of calls from an entry to a function that calls no other
   function of the program, made with a worklist: each step takes the
   first chain off the list, and either keeps it, when it cannot go on,
   or puts back one longer chain per next call. :)
declare function graph:chains($graph as element(graph)) as element(chain)* {
  let $start := {
    "work": array {
      for $entry in graph:entries($graph)
      for $call in $graph/call[@from = $entry][not(@external)]
      return <chain>{ $call }</chain>
    },
    "done": ()
  }
  let $end := while-do($start, fn { array:size(?work) > 0 }, fn($state) {
    let $chain := array:head($state?work)
    let $next := graph:next($graph, $chain/call)
    return {
      "work": array:join((
        array { $next ! <chain>{ $chain/call, . }</chain> },
        array:tail($state?work))),
      "done": ($state?done, $chain[empty($next)])
    }
  })
  return $end?done
};

The state of the loop is a map with the worklist, an array of chains, and the finished chains. fn:while-do takes a start value, a condition and an action: it applies the action as long as the condition holds and returns the last value. Putting the longer chains at the front of the worklist goes deep first, so the chains come out in the order of the calls in the code.

graph:chain-text writes a chain as the functions it goes through, with a star after a function called in a loop:

(: A chain as text: the functions it goes through, a star after each
   one called in a loop. :)
declare function graph:chain-text($chain as element(chain)) as xs:string {
  string-join(($chain/call[1]/@from,
               $chain/call ! (@to || (if (@repeated) then "*" else ""))),
              " > ")
};

chains.xq prints the chains of a directory:

(: The call chains of the TypeScript files in a directory, one per line:
   one version of the Vane service, before or after. The chains are made
   with a worklist, or with --param=method=recursive by recursion. :)
import module namespace graph = "urn:example:graph" at "graph.xqm";

declare option output:method "text";
declare option output:item-separator "&#10;";

declare variable $directory as xs:string external := "before";
declare variable $method as xs:string external := "worklist";

let $graph := graph:graph(graph:read($directory))
let $chains := if ($method = "recursive") then graph:chains-recursive($graph)
               else graph:chains($graph)
return $chains ! graph:chain-text(.)

$ sxml xquery --allow-file-access --param=directory=before chains.xq
api.start > api.route > flags.listFlags > registry.getFlags > db.query
api.start > api.route > flags.listFlags > flags.summarize
api.start > api.route > flags.killFlag > cache.getFlag
api.start > api.route > flags.killFlag > registry.getFlag > db.query
api.start > api.route > flags.killFlag > flags.isOwner
api.start > api.route > flags.killFlag > registry.setPercentage > db.query
$ sxml xquery --allow-file-access --param=directory=after chains.xq
api.start > api.route > flags.listFlags > registry.getFlagKeys > db.query
api.start > api.route > flags.listFlags > registry.getFlag* > db.query
api.start > api.route > flags.listFlags > flags.summarize
api.start > api.route > flags.killFlag > registry.getFlag > db.query
api.start > api.route > flags.killFlag > flags.isOwner
api.start > api.route > flags.killFlag > registry.setPercentage > db.query
api.start > api.route > flags.killFlag > audit.record > db.query

Six chains before, seven after. Every chain that reaches PostgreSQL ends in db.query, the one function that holds the pool, and cache.getFlag, which reads Redis through a client of its own, ended a chain of its own. The new chain through audit.record ends in db.query too: the module's call to the owners' webhook is fetch, an external call, which ends no chain and is not part of one.

Chains with recursion

The same chains come from a function that calls itself, and it is shorter: the chains that go on from a chain are, for each next call, the chains that go on from the longer chain, and a chain that cannot go on is one chain:

(: The same chains, by a function that calls itself: the chains that
   go on from a chain are those that go on from it and each next call. :)
declare function graph:extend(
  $graph as element(graph),
  $chain as element(call)*
) as element(chain)* {
  let $next := graph:next($graph, $chain)
  return if (empty($next)) then <chain>{ $chain }</chain>
         else $next ! graph:extend($graph, ($chain, .))
};

declare function graph:chains-recursive($graph as element(graph)) as element(chain)* {
  for $entry in graph:entries($graph)
  for $call in $graph/call[@from = $entry][not(@external)]
  return graph:extend($graph, $call)
};

Both are correct, and give the same chains in the same order:

$ sxml xquery --allow-file-access --param=directory=after chains.xq > worklist.txt
$ sxml xquery --allow-file-access --param=directory=after --param=method=recursive chains.xq > recursive.txt
$ cmp worklist.txt recursive.txt && echo same
same

The recursion is the definition of a chain written down. The worklist says how the chains are made, step by step, and holds its state in a value, so it can be stopped, counted or limited without changing the definition: a maximum chain length is one more condition in the while-do. For a graph with thousands of functions, the worklist also keeps the depth of nested function calls flat.

The diff

diff.xq compares two versions. It makes one document with every function, call and chain of either version, each marked with an attribute change: added when only the new version has it, removed when only the old one has it, changed when both have it and it differs, and no attribute when it is the same.

A call of the graph is a call site, with a line. Lines move when code is added above them, so the diff compares calls by caller and callee only, one for each pair, repeated when any of its call sites is in a loop:

(: The calls of a graph, one per caller and callee, keyed by both; a
   call is repeated when any of its calls is in a loop. :)
declare function local:calls($graph as element(graph)) as map(*) {
  map:merge(
    for $call in $graph/call
    group by $key := $call/@from || " > " || $call/@to
    return { $key: <call>{
      $call[1]/(@from, @to, @external),
      if ($call/@repeated) { attribute repeated { "true" } }
    }</call> }
  )
};

A chain is compared by the functions it goes through, without the stars, so that a chain whose call became repeated is changed:

(: The chains of a graph, keyed by the functions they go through. :)
declare function local:chains($graph as element(graph)) as map(*) {
  map:merge(
    for $chain in graph:chains($graph)
    let $text := graph:chain-text($chain)
    return { translate($text, "*", ""): <chain>{ $text }</chain> }
  )
};

One function compares two maps of either kind. It goes through the keys of both, in order, and copies the item of the new version, or of the old one when the new one does not have it, with the change as an attribute. deep-equal on two elements compares their names, attributes and content:

(: Marks each key of either map: added, removed, or changed when the
   two items differ. :)
declare function local:compare($old as map(*), $new as map(*)) as element()* {
  for $key in distinct-values((map:keys($old), map:keys($new)))
  order by $key
  let $item := ($new($key), $old($key))[1]
  let $change :=
    if (not(map:contains($old, $key))) then "added"
    else if (not(map:contains($new, $key))) then "removed"
    else if (not(deep-equal($old($key), $new($key)))) then "changed"
    else ()
  return element { node-name($item) } {
    $item/@*, $change ! attribute change { . }, $item/node()
  }
};

The diff of the functions is the same function on two maps from id to an empty function element. The main expression puts the three together:

let $before := graph:graph(graph:read($old))
let $after := graph:graph(graph:read($new))
let $changes := (
  local:compare(
    map:merge($before/function ! { string(@id): <function id="{ @id }"/> }),
    map:merge($after/function ! { string(@id): <function id="{ @id }"/> })),
  local:compare(local:calls($before), local:calls($after)),
  local:compare(local:chains($before), local:chains($after))
)
return <diff old="{ $old }" new="{ $new }">{
  $changes, local:modules($before, $after)
}</diff>

local:modules is the last part, below. The two versions are external variables, before and after unless they are given:

$ sxml xquery --allow-file-access diff.xq --output=diff.xml
$ sxml xpath --context-item=diff.xml 'for $kind in ("function", "call", "chain") return `{$kind}s: {count(/diff/*[local-name() = $kind][@change = "added"])} added, {count(/diff/*[local-name() = $kind][@change = "removed"])} removed`'
"functions: 2 added, 2 removed"
"calls: 7 added, 5 removed"
"chains: 3 added, 2 removed"

The calls that changed:

$ sxml xpath --context-item=diff.xml '/diff/call[@change] ! `{@change}: {@from} > {@to}{if (@repeated) then " (in a loop)" else ""}`'
"added: audit.record > JSON.stringify"
"added: audit.record > db.query"
"added: audit.record > fetch"
"removed: cache.getFlag > JSON.parse"
"removed: cache.getFlag > client.get"
"added: flags.killFlag > audit.record"
"removed: flags.killFlag > cache.getFlag"
"added: flags.listFlags > registry.getFlag (in a loop)"
"added: flags.listFlags > registry.getFlagKeys"
"removed: flags.listFlags > registry.getFlags"
"added: registry.getFlagKeys > db.query"
"removed: registry.getFlags > db.query"

flags.listFlags > registry.getFlag is added, not changed: before the change, listFlags did not call getFlag at all.

How often a module is called

The question a reviewer asks of this change is how much more work a request makes, and that is a question about modules: a call to the registry module is a query to PostgreSQL, a call to the audit module a query and a request to the owners' webhook, a call to the cache module a read from Redis. For each function of both versions and each other module it calls, local:modules counts the calls before and after. A call in a loop counts as n, once per iteration:

(: How many times a function makes some calls: "2" for two calls, "1 +
   n" when one more is in a loop (n times, once per iteration), "0" for
   none. :)
declare function local:count($calls as element(call)*) as xs:string {
  let $once := count($calls[not(@repeated)])
  let $loops := count($calls[@repeated])
  return string-join((
    if ($once > 0 or $loops = 0) { string($once) },
    if ($loops > 0) { (if ($loops > 1) then $loops else "") || "n" }
  ), " + ")
};

(: For each function of both versions and each other module of the
   program it calls, the calls to that module before and after, where
   they differ. :)
declare function local:modules(
  $before as element(graph),
  $after as element(graph)
) as element(module)* {
  for $function in $before/function/@id[. = $after/function/@id]
  let $module-of := fn($id) { substring-before($id, ".") }
  let $calls := fn($graph as element(graph)) as element(call)* {
    $graph/call[@from = $function][not(@external)]
               [$module-of(@to) ne $module-of($function)]
  }
  for $module in sort(distinct-values(($calls($before), $calls($after))/$module-of(@to)))
  let $old := local:count($calls($before)[$module-of(@to) = $module])
  let $new := local:count($calls($after)[$module-of(@to) = $module])
  where $old ne $new
  return <module from="{ $function }" name="{ $module }" old="{ $old }" new="{ $new }"/>
};

The group by of the calls in local:calls is gone here: two calls to the same function are two calls. $module-of and $calls are inline functions bound with let, used as helpers inside one function. The result is the end of diff.xml:

$ sxml xpath --context-item=diff.xml '/diff/module ! `{@from} > {@name}: {@old} -> {@new}`'
"flags.listFlags > registry: 1 -> 1 + n"
"flags.killFlag > audit: 0 -> 1"
"flags.killFlag > cache: 1 -> 0"

That is the prediction: listing the flags calls the registry module, and so PostgreSQL, once more for each flag, and the kill switch calls the audit module once and the cache module no more.

A text report

report.xq writes the diff for a terminal or a review comment. It reads diff.xml as its context item and only formats:

(: The diff of two versions as a text report: what was added, removed
   and changed, and how often functions call other modules now. :)
declare option output:method "text";
declare option output:item-separator "&#10;";

declare function local:text($item as element()) as xs:string {
  typeswitch ($item)
    case element(call)
      return $item/@from || " > " || $item/@to
             || (if ($item/@repeated) then " (in a loop)" else "")
    case element(function) return string($item/@id)
    default return string($item)
};

for $kind in ("function", "call", "chain")
for $change in ("added", "removed", "changed")
let $items := /diff/*[local-name() = $kind][@change = $change]
where exists($items)
return (`{ $kind }s { $change }:`, $items ! ("  " || local:text(.)), ""),

"Calls to other modules, before and after:",
/diff/module ! `  {@from} > {@name}: {@old} -> {@new}`

$ sxml xquery --context-item=diff.xml report.xq
functions added:
  audit.record
  registry.getFlagKeys

functions removed:
  cache.getFlag
  registry.getFlags

calls added:
  audit.record > JSON.stringify
  audit.record > db.query
  audit.record > fetch
  flags.killFlag > audit.record
  flags.listFlags > registry.getFlag (in a loop)
  flags.listFlags > registry.getFlagKeys
  registry.getFlagKeys > db.query

calls removed:
  cache.getFlag > JSON.parse
  cache.getFlag > client.get
  flags.killFlag > cache.getFlag
  flags.listFlags > registry.getFlags
  registry.getFlags > db.query

chains added:
  api.start > api.route > flags.killFlag > audit.record > db.query
  api.start > api.route > flags.listFlags > registry.getFlag* > db.query
  api.start > api.route > flags.listFlags > registry.getFlagKeys > db.query

chains removed:
  api.start > api.route > flags.killFlag > cache.getFlag
  api.start > api.route > flags.listFlags > registry.getFlags > db.query

Calls to other modules, before and after:
  flags.listFlags > registry: 1 -> 1 + n
  flags.killFlag > audit: 0 -> 1
  flags.killFlag > cache: 1 -> 0

An HTML report

report.xsl writes the same diff as a page: the calls that changed in a table, every chain with the changed ones marked, and the calls to other modules. A template rule for each kind of element, and the classes added, removed and changed for the style sheet to colour:

<?xml version="1.0" encoding="UTF-8"?>
<!-- The diff of two versions as an HTML page: the calls that changed,
     the call chains, and how often functions call other modules. -->
<xsl:stylesheet version="3.0" expand-text="yes"
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

  <xsl:output method="html" html-version="5" indent="yes"/>

  <xsl:template match="/diff">
    <html>
      <head>
        <title>Call chains, {@old} and {@new}</title>
        <style>
          .added {{ background: #dfd; }}
          .removed {{ background: #fdd; text-decoration: line-through; }}
          .changed {{ background: #ffd; }}
        </style>
      </head>
      <body>
        <h1>Call chains, {@old} and {@new}</h1>
        <h2>Calls that changed</h2>
        <table>
          <tr><th>Caller</th><th>Callee</th><th>Change</th></tr>
          <xsl:apply-templates select="call[@change]"/>
        </table>
        <h2>Chains</h2>
        <ul>
          <xsl:apply-templates select="chain"/>
        </ul>
        <h2>Calls to other modules</h2>
        <table>
          <tr><th>Function</th><th>Module</th><th>{@old}</th><th>{@new}</th></tr>
          <xsl:apply-templates select="module"/>
        </table>
      </body>
    </html>
  </xsl:template>

  <xsl:template match="call">
    <tr class="{@change}">
      <td><code>{@from}</code></td>
      <td><code>{@to}</code>{if (@repeated) then ', in a loop' else ()}</td>
      <td>{@change}</td>
    </tr>
  </xsl:template>

  <xsl:template match="chain">
    <li><code>{.}</code></li>
  </xsl:template>

  <xsl:template match="chain[@change]">
    <li class="{@change}"><code>{.}</code> ({@change})</li>
  </xsl:template>

  <xsl:template match="module">
    <tr>
      <td><code>{@from}</code></td>
      <td><code>{@name}</code></td>
      <td>{@old}</td>
      <td>{@new}</td>
    </tr>
  </xsl:template>
</xsl:stylesheet>

With expand-text="yes", braces in text are text value templates, so the braces of the CSS rules are doubled. The rule for chain[@change] wins over the rule for chain because its pattern has a predicate, which gives it a higher default priority.

$ sxml transform report.xsl diff.xml --output=report.html
$ sed -n '/Calls to other modules/,/<\/table>/p' report.html
    <h2>Calls to other modules</h2>
    <table>
      <tr>
        <th>Function</th>
        <th>Module</th>
        <th>before</th>
        <th>after</th>
      </tr>
      <tr>
        <td><code>flags.listFlags</code></td>
        <td><code>registry</code></td>
        <td>1</td>
        <td>1 + n</td>
      </tr>
      <tr>
        <td><code>flags.killFlag</code></td>
        <td><code>audit</code></td>
        <td>0</td>
        <td>1</td>
      </tr>
      <tr>
        <td><code>flags.killFlag</code></td>
        <td><code>cache</code></td>
        <td>1</td>
        <td>0</td>
      </tr>
    </table>

Drawing the diff

The drawing module of Project: Drawing Diagrams with SVG, draw.xqm, draws any diagram description: node and edge elements, each with an optional class that the drawing copies to its SVG group and colours for added, removed and changed. This project's directory has it, and the SVG project's main query draw.xq, as symbolic links to the files in ../svg, so the module stays one file.

So drawing the diff is writing it as a diagram. diagram.xq makes a node for each function and an edge for each call within the program, with the change as the class and the label loop on a repeated call:

(: The diff of two versions (diff.xml, the context item) as a diagram
   for draw.xqm: the functions of the program and the calls between
   them, each with the class of its change. :)
declare option output:indent "yes";

(: The functions in the order the chains first go through them, so that
   the entry is the first node and the drawing reads like the chains. :)
let $order := distinct-values(/diff/chain ! tokenize(translate(., "*", ""), " > "))
return <diagram title="Call graph, { /diff/@old } and { /diff/@new }">{
  for $function in /diff/function
  order by index-of($order, $function/@id)
  return <node id="{ $function/@id }" label="{ $function/@id }">{
    $function/@change ! attribute class { . }
  }</node>,
  for $call in /diff/call[not(@external)]
  return <edge from="{ $call/@from }" to="{ $call/@to }">{
    if ($call/@repeated) { attribute label { "loop" } },
    $call/@change ! attribute class { . }
  }</edge>
}</diagram>

draw.xqm puts the first node in the top row, so the functions are ordered as the chains first go through them: index-of gives each function its position in the distinct functions of all chains, and the entry, api.start, comes first.

$ sxml xquery --context-item=diff.xml diagram.xq --output=diagram.xml
$ sxml xquery --context-item=diagram.xml draw.xq --output=calls.svg
$ sxml xpath --context-item=calls.svg '//*:g[tokenize(@class) = ("added", "removed", "changed")] ! `{@class}: {@id}`'
"edge added: edge-audit.record-db.query"
"edge added: edge-flags.killFlag-audit.record"
"edge removed: edge-flags.killFlag-cache.getFlag"
"edge added: edge-flags.listFlags-registry.getFlag"
"edge added: edge-flags.listFlags-registry.getFlagKeys"
"edge removed: edge-flags.listFlags-registry.getFlags"
"edge added: edge-registry.getFlagKeys-db.query"
"edge removed: edge-registry.getFlags-db.query"
"node service added: node-audit.record"
"node service removed: node-cache.getFlag"
"node service added: node-registry.getFlagKeys"
"node service removed: node-registry.getFlags"

The added functions and calls are drawn green and thick, the removed ones red and dashed, and the call in the loop is labelled. The rows of the drawing are the boxes with the same y:

$ sxml xpath --context-item=calls.svg 'for $y in distinct-values(//*:rect/@y) return `{$y}: {string-join(//*:g[*:rect/@y = $y]/*:text, ", ")}`'
"20: api.start"
"120: api.route"
"220: flags.killFlag, flags.listFlags"
"320: audit.record, cache.getFlag, flags.isOwner, registry.getFlag, registry.setPercentage, flags.summarize, registry.getFlagKeys, registry.getFlags"
"420: db.query"

The entry, the router, the two request handlers, the functions they call, and db.query at the bottom, which every query to PostgreSQL goes through. Before and after are one picture: in the fourth row the new audit.record stands beside the old cache.getFlag, and the new getFlagKeys beside the old getFlags, with getFlag among the functions both versions call.

What the traces will say

The diff predicts, from the code alone, that GET /api/getFlags makes one call to the registry module, one query to PostgreSQL, and then one more per flag; that killing a flag calls the audit module once, which writes to PostgreSQL and calls the owners' webhook; and that it no longer reads Redis. It cannot say how many flags there are, how long each query takes, or whether a call of killFlag found its flag in the cache before the change. Project: Comparing Traces Before and After a Change answers those from traces recorded by the running service. The line they check is flags.listFlags > registry: 1 -> 1 + n, and with four flags, one query to PostgreSQL becomes five.