Hierarchical dependency analysis enhancements using disjoint-or trees

Patent metadata

Field	Value
Publication number	US-9547478-B1
Application number	US-201514871961-A
Country	US
Kind code	B1
Filing date	Sep 30, 2015
Priority date	Sep 30, 2015
Publication date	Jan 17, 2017
Grant date	Jan 17, 2017

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for performing hierarchical dependency analysis using disjoint-or trees. One of the methods includes receiving, from a user, a request to remove a node from a hierarchy, wherein the hierarchy is a directed graph having nodes and links, wherein each node in the hierarchy represents a software element in the project and each directed link in the hierarchy connects a corresponding pair of nodes and represents containment of a child software element represented by a first node of the pair by a parent software element represented by a second node of the pair. If a parent element of a disjoint-or tree corresponds to a parent node of the removed node, a union of dependencies for the removed node is determined. The union of dependencies is then subtracted from the parent element and from every ancestor element of the parent element.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving, from a user, a request to add a node to a hierarchy of software elements, wherein the hierarchy of software elements is a directed graph having nodes and directed links, wherein each node in the hierarchy of software elements represents a software element in a software project and each directed link in the hierarchy of software elements connects a corresponding pair of nodes and represents containment of a child software element represented by a first node of the corresponding pair of nodes by a parent software element represented by a second node of the corresponding pair of nodes, and
wherein one or more elements of a disjoint-or tree each cache a previously computed portion of a union of dependencies over a corresponding node and any descendants of the corresponding node in the hierarchy of software elements;
determining that the added node of the hierarchy of software elements is not important enough to cache in the disjoint-or tree and that a parent element of the disjoint-or tree corresponding to a parent element of the added node has a status indicator of complete, wherein the status indicator of complete represents that a set of dependencies cached with an element represents a complete set of dependencies for the corresponding node or any descendants of the corresponding node in the hierarchy of software elements;
in response to determining that the added node of the hierarchy of software elements is not important enough to cache in the disjoint-or tree and that the parent element of the disjoint-or tree corresponding to the parent element of the added node has the status indicator of complete, generating a compound element of the disjoint-or tree, wherein the compound element of the disjoint-or tree is a child element of the parent element of the disjoint-or tree, and wherein the compound element stores a set of dependencies for the added node; and
maintaining cached data in the disjoint-or tree including propagating the set of dependencies for the added node to all ancestor elements of the compound element of the disjoint-or tree.

2. The computer-implemented method of claim 1 , wherein the disjoint-or tree satisfies two properties:
a first property that each element of the disjoint-or tree is associated with a set of dependencies that is a union of one or more sets of dependencies associated with the element and any descendant elements of the element of the disjoint-or tree, and
a second property that children elements of each parent element of the disjoint-or tree are associated with disjoint sets of dependencies.

3. The computer-implemented method of claim 1 , further comprising:
determining whether the added node of the hierarchy of software elements is important enough to cache in the disjoint-or tree by:
computing a weight for the added node based on a number of descendants of the added node, a number of dependencies associated with the added node, or both; and
determining that the weight for the added node satisfies a threshold.

4. A computer-implemented method comprising:
receiving, from a user, a request to add a node to a hierarchy of software elements, wherein the hierarchy of software elements is a directed graph having nodes and directed links, wherein each node in the hierarchy of software elements represents a software element in a software project and each directed link in the hierarchy of software elements connects a corresponding pair of nodes and represents containment of a child software element represented by a first node of the corresponding pair of nodes by a parent software element represented by a second node of the corresponding pair of nodes, and
wherein one or more elements of a disjoint-or tree each cache a previously computed portion of a union of dependencies over a corresponding node and any descendants of the corresponding node in the hierarchy of software elements;
caching the added node of the hierarchy of software elements with a corresponding added element of the disjoint-or tree;
determining that a parent element of the corresponding added element of the disjoint-or tree has a status indicator of complete, wherein the status indicator of complete represents that a set of dependencies cached with an element represents a complete set of dependencies for the corresponding node or any descendants of the corresponding node in the hierarchy of software elements; and
in response to determining that the parent element of the corresponding added element of the disjoint-or tree has the status indicator of complete, generating a compound element of the disjoint-or tree, wherein the compound element of the disjoint-or tree is a child element of the parent element of the disjoint-or tree, and wherein the compound element stores a set difference between a set of the corresponding added element and the parent element of the corresponding added element of the disjoint-or tree.

5. The computer-implemented method of claim 4 , wherein the disjoint-or tree satisfies two properties:
a first property that each element of the disjoint-or tree is associated with a set of dependencies that is a union of one or more sets of dependencies associated with the element and any descendant elements of the element of the disjoint-or tree, and
a second property that children elements of each parent element of the disjoint-or tree are associated with disjoint sets of dependencies.

6. The computer-implemented method of claim 4 , wherein the set difference stored with the compound element includes a set of dependencies for one or more uncached sibling nodes of the added node of the hierarchy of software elements.

7. The computer-implemented method of claim 4 , further comprising:
determining whether the added node of the hierarchy of software elements is important enough to cache in the disjoint-or tree by:
computing a weight for the added node based on a number of descendants of the added node, a number of dependencies associated with the added node, or both; and
determining that the weight for the added node satisfies a threshold.

8. A computer-implemented method comprising:
receiving, from a user, a request to remove a node from a hierarchy of software elements, wherein the hierarchy of software elements is a directed graph having nodes and directed links, wherein each node in the hierarchy of software elements represents a software element in a software project and each directed link in the hierarchy of software elements connects a corresponding pair of nodes and represents containment of a child software element represented by a first node of the corresponding pair of nodes by a parent software element represented by a second node of the corresponding pair of nodes, and
wherein one or more elements of a disjoint-or tree each cache a previously computed portion of a union of dependencies over a corresponding node and any descendants of the corresponding node in the hierarchy of software elements;
determining that a parent element of the disjoint-or tree corresponds to a parent node of the removed node from the hierarchy of software elements;
computing a union of dependencies for the removed node from the hierarchy of software elements; and
in response to computing the union of dependencies for the removed node from the hierarchy of software elements, subtracting the union of dependencies from the parent element of the disjoint-or tree and from every ancestor element of the parent element of the disjoint-or tree.

9. The computer-implemented method of claim 8 , wherein the removed node from the hierarchy of software elements has a corresponding element in the disjoint-or tree, and wherein computing the union of dependencies for

Assignees

• Semmle Ltd

Inventors

• Hale Joshua George

Classifications

• G06T11/26

  Drawing of charts or graphs · CPC title

• G06F8/433 Primary

  Dependency analysis; Data or control flow analysis · CPC title

• G06F8/22 Primary

  Procedural · CPC title

• G06F11/3604

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

• G06F8/75

  Structural analysis for program understanding · CPC title