deepwalk is a Golang implementation of the code documented here which was originally written in Python.
The goal of deepwalk is to traverse an arbitrarily-nested map and retrieve the value associated with a given key.
This project was mostly done to hack on some Go after spending awhile way from it. That said, this package is still useful aside from the "see if it works" perspective.
Usage examples can be found in pkg/traverse/traverse_test.go, but because code is only as good as its documentation, examples will be added (and added to) below.
To install deepwalk, run the following:
go install github.com/egibs/deepwalk/v2@latestImport traverse like so:
import (
"github.com/egibs/deepwalk/pkg/v2/traverse"
)Or, use the provided Dockerfile:
make build-docker
then:
docker run deepwalk:latest
The original use-case for this in Python was to traverse Python dictionaries. While Golang has different names and conventions for this, the approach remains the same.
Cobra is used to provide CLI support for deepwalk.
To get started, build the deepwalk binary with make build.
Then, run deepwalk to see the available commands:
❯ ./deepwalk -h
Usage:
deepwalk [command]
Available Commands:
completion Generate the autocompletion script for the specified shell
help Help about any command
traverse Traverse an object for the specified key and return the value associated with that key
Flags:
-h, --help help for deepwalk
Use "deepwalk [command] --help" for more information about a command.To use Traverse, use the traverse command:
./deepwalk traverse -h
traverse utilizes the Traverse function which requires a ReturnControl value to determine what to return.
First will return the first value found, Last will return the last value found, and All will return all values found.
Usage:
deepwalk traverse --object <filename or JSON string> --search-key <search key> --default-value <default value> --return-value <return value> [flags]
Flags:
--default-value string Default value to return if search fails (default "NO_VALUE")
-h, --help help for traverse
--object string Object to search
--return-value string Value to return if search succeeds (default "all")
--search-key string Key to search forExamples of using traverse:
search:
❯ ./deepwalk traverse --object complex.json --search-key name
[
"Tamra Bennett",
"Alana Hoover",
"Ewing Williamson",
"Webster Serrano",
"Lea Bryant",
"Sylvia Parks",
"Hubbard Delgado",
"Townsend Calderon",
"Knapp Patton",
"Barr Floyd",
"Haynes Osborn",
"Rebecca Walters",
"Muriel Lindsay",
"Osborne Reid",
"Lois Chaney",
"Contreras Wolfe",
"Goodwin Christensen",
"Rosa Luna",
"Tabitha Moreno",
"Oneil Carlson"
]
❯ ./deepwalk traverse --object '{"a": {"b": "c"}}' --search-key b
"c"Given a simple JSON object like this:
var exampleJSON = []byte(`{
"key": [
{
"inner_key": "value"
}
]
}`)The value of inner_key can be retrieved like so:
var object map[string]interface{}
err := json.Unmarshal(exampleJSON, &object)
if err != nil {
fmt.Println(err)
}
value, err := deepwalk.Traverse(object, "key", "<NO_VALUE>", traverse.All)
if err != nil {
fmt.Println(err)
}
fmt.Println(value)which will result in value being printed.
To add some color to the aruguments used when calling Traverse --
objectis the starting map to traversekeyis the target key to search for in the structure<NO_VALUE>is the default value to return if the desired value is not foundallspecifies the values to return, if foundfirstandlastare also available which will return the first and last found values, respectively
Maps can be used directly as well (this example is taken from the tests) --
var exampleMap = map[string]interface{}{
"key": map[string]interface{}{
"inner_key": []interface{}{
[]interface{}{
[]interface{}{
map[string]interface{}{
"very_nested_key": "very_nested_value",
},
},
},
},
},
}
value, err := deepwalk.Traverse(obj, "very_nested_key", "<NO_VALUE>", traverse.All)
if err != nil {
fmt.Println(err)
}
fmt.Println(value)Structs can also be traversed with Traverse:
type TestStruct struct {
Field1 string
Field2 int
NestedStruct struct {
NestedStruct2 struct {
NestedField1 string
NestedField2 int
}
NestedField1 string
NestedField2 int
}
}
testStruct := TestStruct{
Field1: "test",
Field2: 123,
NestedStruct: struct {
NestedStruct2 struct {
NestedField1 string
NestedField2 int
}
NestedField1 string
NestedField2 int
}{
NestedStruct2: struct {
NestedField1 string
NestedField2 int
}{
NestedField1: "nested",
NestedField2: 456,
},
NestedField1: "nested",
NestedField2: 456,
},
}
value, err := deepwalk.Traverse(testStruct, "NestedField1", "<NO_VALUE>", traverse.All)
if err != nil {
fmt.Println(err)
}
fmt.Println(value)Several categories of tests are included:
- 7 test cases covering a variety of uses
- Randomly-generated test cases for successful path-based traversal
- Randomly-generated test cases for traversals that return a default value
Categories three and four run one-thousand iterations of each variant and each distinct case uses a randomly-generated map structure, list of keys, and desired value (in the case of the path-based traversal tests)
Run all of the included tests by running make test:
❯ make test
go test ./... -v
go: downloading github.com/wk8/go-ordered-map/v2 v2.1.8
go: downloading github.com/spf13/cobra v1.8.0
go: downloading github.com/spf13/pflag v1.0.5
go: downloading gopkg.in/yaml.v3 v3.0.1
go: downloading github.com/bahlo/generic-list-go v0.2.0
go: downloading github.com/buger/jsonparser v1.1.1
go: downloading github.com/mailru/easyjson v0.7.7
? github.com/egibs/deepwalk/v2 [no test files]
? github.com/egibs/deepwalk/v2/cmd [no test files]
? github.com/egibs/deepwalk/v2/internal/util [no test files]
=== RUN TestTraverse
=== RUN TestTraverse/Test_case_1_-_key_found_in_map
=== RUN TestTraverse/Test_case_2_-_key_not_found_in_map
=== RUN TestTraverse/Test_case_3_-_key_found_in_nested_map
=== RUN TestTraverse/Test_case_4_-_key_not_found_in_nested_map
=== RUN TestTraverse/Test_case_5_-_key_found_in_struct
=== RUN TestTraverse/Test_case_6_-_key_not_found_in_struct
=== RUN TestTraverse/Test_case_7_-_duplicate_key_found_in_map
--- PASS: TestTraverse (0.00s)
--- PASS: TestTraverse/Test_case_1_-_key_found_in_map (0.00s)
--- PASS: TestTraverse/Test_case_2_-_key_not_found_in_map (0.00s)
--- PASS: TestTraverse/Test_case_3_-_key_found_in_nested_map (0.00s)
--- PASS: TestTraverse/Test_case_4_-_key_not_found_in_nested_map (0.00s)
--- PASS: TestTraverse/Test_case_5_-_key_found_in_struct (0.00s)
--- PASS: TestTraverse/Test_case_6_-_key_not_found_in_struct (0.00s)
--- PASS: TestTraverse/Test_case_7_-_duplicate_key_found_in_map (0.00s)
PASS
ok github.com/egibs/deepwalk/v2/pkg/traverse 0.002sRun the included benchmarks by running make bench:
❯ make bench
go test ./... -bench=. -benchmem
? github.com/egibs/deepwalk/v2 [no test files]
? github.com/egibs/deepwalk/v2/cmd [no test files]
? github.com/egibs/deepwalk/v2/internal/util [no test files]
goos: linux
goarch: amd64
pkg: github.com/egibs/deepwalk/v2/pkg/traverse
cpu: 12th Gen Intel(R) Core(TM) i9-12900K
BenchmarkTraverse-24 1000000 1020 ns/op 764 B/op 28 allocs/op
BenchmarkTraverseSuccess-24 7668 156473 ns/op 27399 B/op 1525 allocs/op
BenchmarkTraverseDefault-24 706 1739258 ns/op 297695 B/op 16732 allocs/op
PASS
ok github.com/egibs/deepwalk/v2/pkg/traverse 3.652sTo cut a release for this package, do the following:
- Update the
VERSIONfile- For now this is aesthetic but offers an easy way to reference the version outside of GitHub
- Update
CHANGELOG.mdwith a new entry matching the new version - Commit and push any changes to
main(either directly or via PR) - Run
git tag vX.Y.Z - Run
git push origin --tags - Create a new release using the new tag
0 CVEs c/o Wolfi:
❯ grype deepwalk:latest
✔ Vulnerability DB [no update available]
✔ Loaded image deepwalk:latest
✔ Parsed image sha256:15776b55889a5e6500937a6ee1d9c8b0c5f6dea8f2e9631e324f27fa48a7077c
✔ Cataloged contents a89b0db2a340569633d593f81c58297e103de4b8ca80f97459ed5678809c4f24
├── ✔ Packages [14 packages]
├── ✔ File digests [397 files]
├── ✔ File metadata [397 locations]
└── ✔ Executables [1 executables]
✔ Scanned for vulnerabilities [0 vulnerability matches]
├── by severity: 0 critical, 0 high, 0 medium, 0 low, 0 negligible
└── by status: 0 fixed, 0 not-fixed, 0 ignored
No vulnerabilities found
wk8 for their extremely handy go-ordered-map package
- It is easy to take
collections.OrderedDictfor granted in Python and this was extremely easy to implement