Next Actionable Critical Dependency Example

main.go

package main

import (
	"context"
	"fmt"
	"log"
	"net/http"
	"sort"
	"time"

	"github.com/Khan/genqlient/graphql"
	model "github.com/guacsec/guac/pkg/assembler/clients/generated"
	"github.com/guacsec/guac/pkg/logging"
)

type dependencyNode struct {
	dependents map[string]bool // map of the name of the dependent to whether it is a dependent of the current node
}

type packageName struct {
	name     string
	depCount int
}

type node struct {
	id           string
	name         string
	dependencies []string
}

func main() {
	startTime := time.Now()

	go func() {
		log.Println(http.ListenAndServe("localhost:6060", nil))
	}()

	graphqlEndpoint := "http://localhost:8080/query"

	httpClient := http.Client{}
	gqlClient := graphql.NewClient(graphqlEndpoint, &httpClient)

	ctx := context.Background()
	logger := logging.FromContext(ctx)

	pkgResponse, err := model.Packages(ctx, gqlClient, model.PkgSpec{})
	if err != nil {
		logger.Fatalf("error querying for package: %v", err)
	}
	if len(pkgResponse.Packages) < 1 {
		logger.Fatalf("failed to located package based on purl")
	}

	packages := map[string]dependencyNode{}

	// memory is used as a DP to avoid re-iterating over packages that we have already seen in a previous iteration
	memory := map[string]dependencyNode{}

	for _, p := range pkgResponse.Packages {
		for _, namespace := range p.Namespaces {
			for _, name := range namespace.Names {
				for _, version := range name.Versions {
					for _, id := range []string{version.Id, name.Id} {
						pName := p.Type + "_" + namespace.Namespace + "_" + name.Name

						// We don't want to re-calculate findDependentsDFS on a node that we have already seen because we will
						// have to add the value that we have already calculated to the number of dependencies for that node again.
						if _, alreadyCalculatedNode := memory[id]; !alreadyCalculatedNode {
							// depth is the depth that we want to traverse the tree
							// a depth of -1 means that we traverse the entire tree
							depth := -1
							visited := make(map[string]bool)
							dependencies, _ := findDependentsBFS(ctx, gqlClient, id, pName, visited, memory, depth)

							for n, dependents := range dependencies {
								// n is the package name
								if _, ok := packages[n]; !ok {
									packages[n] = dependencyNode{
										dependents: map[string]bool{},
									}
								}
								for d := range dependents.dependents {
									packages[n].dependents[d] = true
								}
								memory[n] = packages[n]
							}
						}
					}
				}
			}
		}
	}

	// packages and memory have the same information, but packages is an array while memory is a map

	var packagesArr []packageName

	for n, d := range packages {
		packagesArr = append(packagesArr, packageName{name: n, depCount: len(d.dependents)})
	}

	sort.Slice(packagesArr, func(i, j int) bool {
		return packagesArr[i].depCount > packagesArr[j].depCount
	})

	fmt.Println("the number of dependencies : the package name")
	fmt.Println("---------------------------------------------")

	for _, d := range packagesArr {
		if d.depCount > 0 {
			fmt.Println(d.depCount, d.name)
		}
	}

	endTime := time.Now()

	// Calculate the duration
	duration := endTime.Sub(startTime)

	fmt.Println("---------------------------------------------")
	fmt.Println("Execution Time: ", duration)
}

func findDependentsBFS(ctx context.Context, gqlClient graphql.Client, subjectQueryID, subjectQueryName string, visited map[string]bool, memory map[string]dependencyNode, depth int) (map[string]dependencyNode, error) {
	queue := []node{{id: subjectQueryID, name: subjectQueryName}}

	res := map[string]dependencyNode{}

	for len(queue) > 0 && depth != 0 {
		n := len(queue)

		for i := 0; i < n; i++ {
			pop := queue[0]
			queue = queue[1:]

			if visited[pop.id] {
				continue
			}
			visited[pop.id] = true

			if val, ok := memory[subjectQueryName]; ok {
				if _, ok := res[subjectQueryName]; !ok {
					res[subjectQueryName] = dependencyNode{
						dependents: map[string]bool{},
					}
				}
				for a := range val.dependents {
					if _, ok := res[a]; !ok {
						res[a] = dependencyNode{
							dependents: map[string]bool{},
						}
					}
					res[subjectQueryName].dependents[a] = true
					res[a] = memory[a]
				}
				continue
			}

			dependencyResponse, err := model.Dependencies(ctx, gqlClient, model.IsDependencySpec{
				Package: &model.PkgSpec{
					Id: &pop.id,
				},
			})
			if err != nil {
				return nil, fmt.Errorf("error getting dependencies: %v", err)
			}

			if _, ok := res[pop.name]; !ok {
				res[pop.name] = dependencyNode{
					dependents: map[string]bool{},
				}
			}
			for _, d := range pop.dependencies {
				res[pop.name].dependents[d] = true
			}

			for _, dependency := range dependencyResponse.IsDependency {
				name := dependency.Package.Type + "_" + dependency.Package.Namespaces[0].Namespace + "_" + dependency.Package.Namespaces[0].Names[0].Name

				if len(dependency.DependencyPackage.Namespaces[0].Names[0].Versions) > 0 {
					queue = append(queue, node{
						id:           dependency.DependencyPackage.Namespaces[0].Names[0].Versions[0].Id,
						name:         name,
						dependencies: append(pop.dependencies, pop.name),
					})
				}

				//queue = append(queue, node{
				//	id:           dependency.DependencyPackage.Namespaces[0].Names[0].Id,
				//	name:         name,
				//	dependencies: append(pop.dependencies, pop.name),
				//})
			}
		}

		depth = max(depth-1, -1)
	}

	return res, nil
}

Design doc: https://docs.google.com/document/d/1892EPekBkHbOSV2iL_61HGV0uzJHsO205mEKkHIonZ0/edit