Suggesting candidate removable software dependencies

Patent metadata

Field	Value
Publication number	US-9411706-B1
Application number	US-201514871299-A
Country	US
Kind code	B1
Filing date	Sep 30, 2015
Priority date	Sep 30, 2015
Publication date	Aug 9, 2016
Grant date	Aug 9, 2016

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for generated aggregated dependencies between software elements in a code base. One of the methods includes determining that a cycle exists in the aggregated dependency graph, determining which of the links in the cycle has a lowest weight, and adding a first link in the cycle having the lowest weight to a set of candidate removable links. The links in the set of candidate removable links are classified as candidate removable links, and a user interface presentation is provided that presents the aggregated dependency graph and which visually distinguishes removable links from other links in the aggregated dependency graph.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving data representing an aggregated dependency graph, the aggregated dependency graph having nodes representing selected software elements in a project and having links, the links connecting nodes in the aggregated dependency graph, the links representing respective aggregated dependencies between one or more of the selected software elements in the project, wherein each aggregated dependency between a pair of nodes represents that a first software element represented by a first node of the pair, or a descendant of the first software element in a hierarchy graph of software elements in the project, depends, according to a raw dependency graph of software elements in the project, on a second software element represented by a second node of the pair or a descendant of the second software element in the hierarchy graph of software elements in the project;
computing a respective weight of each link of the aggregated dependency graph, wherein each respective weight of each link between each pair of nodes is based on a count of raw dependencies that exist in the raw dependency graph from a first software element represented by a first node of the pair or any descendant of the first software element in the hierarchy graph to a second software element represented by a second node of the pair or any descendant of the second software element in the hierarchy graph;
determining that a cycle exists in the aggregated dependency graph;
determining which of the links in the cycle has a lowest weight;
adding a first link in the cycle having the lowest weight to a set of candidate removable links;
classifying links in the set of candidate removable links as removable links; and
providing a user interface presentation that presents the aggregated dependency graph and which visually distinguishes removable links from other links in the aggregated dependency graph.

2. The method of claim 1 , further comprising:
receiving a user indication of a particular link that should be discarded if possible from the set of candidate removable links;
determining whether removing the particular link from the set of candidate removable links would reintroduce a cycle in the aggregated dependency graph; and
removing the particular link from the set of candidate removable links if removing the particular link would not reintroduce a cycle in the aggregated dependency graph.

3. The method of claim 1 , further comprising:
receiving, from a user, a selection of one or more dependency types; and
filtering the aggregated dependency graph to contain only aggregated dependencies having the selected one or more dependency types.

4. The method of claim 1 , further comprising:
receiving, from a user, an indication that a particular link is not a candidate for removal,
wherein determining which of the links in the cycle has the lowest weight comprises determining which of the links in the cycle other than the particular link has a lowest weight.

5. The method of claim 1 , wherein the presentation of the aggregated dependency graph has a layout in which all removable links point in a same direction.

6. The method of claim 5 , wherein all other links point in a different direction than the direction of the removable links.

7. The method of claim 6 , wherein the presentation has a layout of software element nodes in multiple layers in which there are no dependencies between software element nodes occurring in a same layer.

8. The method of claim 7 , wherein the presentation presents the layers grouped into clusters, and wherein the presentation includes aggregated dependency links between the clusters.

9. The method of claim 1 , further comprising:
determining that one or more software elements in the aggregated dependency graph are cyclically connected;
generating a tangle node representing the one or more software elements that are cyclically connected,
wherein the presentation presents the tangle node and one or more aggregated dependency links between the tangle node and one or more other software element nodes.

10. The method of claim 9 , wherein the aggregated dependency graph with one or more tangle nodes is an acyclic graph.

11. The method of claim 9 , wherein the presentation presents a cyclic graph within a representation of the tangle node, the cyclic graph representing aggregated dependencies between the one or more software elements that are cyclically connected.

12. The method of claim 1 , wherein the presentation presents removable links in a different color, style, or line thickness than other links.

13. A system comprising:
one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
receiving data representing an aggregated dependency graph, the aggregated dependency graph having nodes representing selected software elements in a project and having links, the links connecting nodes in the aggregated dependency graph, the links representing respective aggregated dependencies between one or more of the selected software elements in the project, wherein each aggregated dependency between a pair of nodes represents that a first software element represented by a first node of the pair, or a descendant of the first software element in a hierarchy graph of software elements in the project, depends, according to a raw dependency graph of software elements in the project, on a second software element represented by a second node of the pair or a descendant of the second software element in the hierarchy graph of software elements in the project;
computing a respective weight of each link of the aggregated dependency graph, wherein each respective weight of each link between each pair of nodes is based on a count of raw dependencies that exist in the raw dependency graph from a first software element represented by a first node of the pair or any descendant of the first software element in the hierarchy graph to a second software element represented by a second node of the pair or any descendant of the second software element in the hierarchy graph;
determining that a cycle exists in the aggregated dependency graph;
determining which of the links in the cycle has a lowest weight;
adding a first link in the cycle having the lowest weight to a set of candidate removable links;
classifying links in the set of candidate removable links as removable links; and
providing a user interface presentation that presents the aggregated dependency graph and which visually distinguishes removable links from other links in the aggregated dependency graph.

14. The system of claim 13 , wherein the operations further comprise:
receiving a user indication of a particular link that should be discarded if possible from the set of candidate removable links;
determining whether removing the particular link from the set of candidate removable links would reintroduce a cycle in the aggregated dependency graph; and
removing the particular link from the set of candidate removable links if removing the particular link would not reintroduce a cycle in the aggregated dependency graph.

15. The system of claim 13 , wherein the operations further comprise:
receiving, from a user, a selection of one or more dependency types; and
filtering the aggregated dependency graph to contain only aggregated dependencies having the selected one or more dependency types.

16. The system of claim 13 , wherein the operations further compri

Assignees

• Semmle Ltd

Inventors

• Van Schaik Sebastiaan Johannes

Classifications

• G06T11/26

  Drawing of charts or graphs · CPC title

• G06F8/433 Primary

  Dependency analysis; Data or control flow analysis · CPC title

• G06F11/3668

  Testing of software · CPC title

• G06F11/3604 Primary

  Analysis of software for verifying properties of programs (testing of software G06F11/3668) · CPC title

• H04L67/133

  Protocols for remote procedure calls [RPC] · CPC title