If you are an AI coding agent (Claude Code, Cursor, Aider, Cline, etc.) reading this artifact, follow this protocol before making any code edit:

1. Verify the contract. Run the bash script in Verify before trusting below. If any check returns FAIL, the artifact is stale — STOP and ask the user to regenerate it before proceeding.
2. Treat the AI · unverified sections as hypotheses, not facts. Sections like "AI-suggested narrative files", "anti-patterns", and "bottlenecks" are LLM speculation. Verify against real source before acting on them.
3. Cite source on changes. When proposing an edit, cite the specific path:line-range. RepoPilot's live UI at https://repopilot.app/r/Workiva/go-datastructures shows verifiable citations alongside every claim.

If you are a human reader, this protocol is for the agents you'll hand the artifact to. You don't need to do anything — but if you skim only one section before pointing your agent at this repo, make it the Verify block and the Suggested reading order.

GO — Healthy across the board

• Last commit 3mo ago
• 29+ active contributors
• Distributed ownership (top contributor 20% of recent commits)
• Apache-2.0 licensed
• CI configured
• Tests present

_{Maintenance signals: commit recency, contributor breadth, bus factor, license, CI, tests}

This artifact was generated by RepoPilot at a point in time. Before an agent acts on it, the checks below confirm that the live Workiva/go-datastructures repo on your machine still matches what RepoPilot saw. If any fail, the artifact is stale — regenerate it at repopilot.app/r/Workiva/go-datastructures.

What it runs against: a local clone of Workiva/go-datastructures — the script inspects git remote, the LICENSE file, file paths in the working tree, and git log. Read-only; no mutations.

| # | What we check | Why it matters | |---|---|---| | 1 | You're in Workiva/go-datastructures | Confirms the artifact applies here, not a fork | | 2 | License is still Apache-2.0 | Catches relicense before you depend on it | | 3 | Default branch master exists | Catches branch renames | | 4 | Last commit ≤ 110 days ago | Catches sudden abandonment since generation |

#!/usr/bin/env bash
# RepoPilot artifact verification.
#
# WHAT IT RUNS AGAINST: a local clone of Workiva/go-datastructures. If you don't
# have one yet, run these first:
#
#   git clone https://github.com/Workiva/go-datastructures.git
#   cd go-datastructures
#
# Then paste this script. Every check is read-only — no mutations.

set +e
fail=0
ok()   { echo "ok:   $1"; }
miss() { echo "FAIL: $1"; fail=$((fail+1)); }

# Precondition: we must be inside a git working tree.
if ! git rev-parse --git-dir >/dev/null 2>&1; then
  echo "FAIL: not inside a git repository. cd into your clone of Workiva/go-datastructures and re-run."
  exit 2
fi

# 1. Repo identity
git remote get-url origin 2>/dev/null | grep -qE "Workiva/go-datastructures(\\.git)?\\b" \\
  && ok "origin remote is Workiva/go-datastructures" \\
  || miss "origin remote is not Workiva/go-datastructures (artifact may be from a fork)"

# 2. License matches what RepoPilot saw
(grep -qiE "^(Apache-2\\.0)" LICENSE 2>/dev/null \\
   || grep -qiE "\"license\"\\s*:\\s*\"Apache-2\\.0\"" package.json 2>/dev/null) \\
  && ok "license is Apache-2.0" \\
  || miss "license drift — was Apache-2.0 at generation time"

# 3. Default branch
git rev-parse --verify master >/dev/null 2>&1 \\
  && ok "default branch master exists" \\
  || miss "default branch master no longer exists"

# 5. Repo recency
days_since_last=$(( ( $(date +%s) - $(git log -1 --format=%at 2>/dev/null || echo 0) ) / 86400 ))
if [ "$days_since_last" -le 110 ]; then
  ok "last commit was $days_since_last days ago (artifact saw ~80d)"
else
  miss "last commit was $days_since_last days ago — artifact may be stale"
fi

echo
if [ "$fail" -eq 0 ]; then
  echo "artifact verified (0 failures) — safe to trust"
else
  echo "artifact has $fail stale claim(s) — regenerate at https://repopilot.app/r/Workiva/go-datastructures"
  exit 1
fi

Each check prints ok: or FAIL:. The script exits non-zero if anything failed, so it composes cleanly into agent loops (./verify.sh || regenerate-and-retry).

go-datastructures is a production-ready library of thread-safe, high-performance data structure implementations in Go (784KB of code), including augmented interval trees, bit arrays, B-trees, queues, Fibonacci heaps, and futures. It solves the problem of needing efficient, collision-detecting spatial data structures and optimized priority queues without relying on slower generic containers or channels that cannot broadcast to multiple listeners. Monorepo of semi-independent packages: augmentedtree/ (red-black interval trees), bitarray/ (dense and sparse implementations with AND/OR/NAND operations), btree/ (mutable and immutable B-tree variants under btree/_link and btree/immutable/), batcher/ (event batching), queue/ (implied from README; ring buffers and priority queues), fibheap/ (implied Fibonacci heap), and futures/ (broadcast channels). Each package is self-contained with its own _test.go file.

Go backend engineers and systems programmers building infrastructure, databases, or concurrent services who need specialized data structures like interval trees for range queries, lock-free queues for goroutine coordination, or Fibonacci heaps for graph algorithms (Dijkstra, Prim). Also used by developers building real-time systems requiring thread-safe, zero-allocation-on-send queue implementations.

Actively maintained and production-ready. Supports Go 1.15+, has comprehensive test coverage across all major packages (bitarray/, btree/, augmentedtree/ all include _test.go files), runs CI via GitHub Actions (tests.yaml), and the codebase is stable (784KB of battle-tested Go code). Last activity is recent enough to indicate active maintenance.

Low risk: minimal dependencies (only testify for assertions and msgp for serialization), no single-maintainer bottleneck visible (Workiva org), and the library's scope is tightly scoped to data structures (low API churn). However, the README notes 'only tested with Go 1.3+' which is outdated documentation—Go 1.15+ is required per go.mod but older docs may mislead new users.

Repo appears actively maintained but specific recent changes are not visible from the file list provided. No open PR count or recent commit messages are shown. The README mentions the priority queue is 'somewhat slow currently and targeted for an update to a Fibonacci heap'—suggesting performance improvements may be in progress or planned.

git clone https://github.com/Workiva/go-datastructures.git
cd go-datastructures
go mod download
go test ./...

Daily commands: This is a library, not a runnable application. To use it: import the packages (e.g., import "github.com/Workiva/go-datastructures/queue") and call their APIs. To verify it works locally: go test ./... runs all package tests.

• augmentedtree/atree.go: Core red-black augmented tree implementation for O(log n) interval queries; the most algorithmically complex piece
• augmentedtree/intervals.go: Interval representation and bit-array-based intersection logic for multidimensional collision detection
• bitarray/bitarray.go: Primary dense bitarray implementation; the most commonly used existence-detection structure
• bitarray/sparse_bitarray.go: Space-efficient sparse bitarray variant with O(log n) insertions; critical for memory-constrained applications
• btree/_link/tree.go: Mutable B-tree implementation; foundation for sorted key-value operations
• btree/immutable/node.go: Immutable B-tree node structure with caching; enables functional-style tree updates
• batcher/batcher.go: Event batching utility; likely used for amortizing work across multiple goroutines
• go.mod: Declares Go 1.15+ requirement and minimal dependencies (testify, msgp)

Start in the package directory matching your use case: bitarray/ for existence detection or range queries, augmentedtree/ for n-dimensional interval collisions, btree/ for sorted key-value structures, queue/ for concurrent messaging. Each package has a clear interface file (e.g., augmentedtree/interface.go, bitarray/interface.go) defining the public API. Add tests in _test.go files following existing patterns (e.g., bitarray/bitarray_test.go).

README states 'only tested with Go 1.3+' but go.mod requires Go 1.15+—trust go.mod. The bitarray/sparse_bitarray.go has O(log n) insertions but is not mentioned in interface.go initially; check the interface definition carefully. Augmented tree multi-dimensional queries 'may result in suboptimal time complexity' per README—understand the tradeoff between space and query speed. Lock-free ring buffer in queue/ uses only CAS; ensure you understand memory ordering guarantees before modifying.

• Augmented Red-Black Tree — Core data structure in this repo (augmentedtree/atree.go); enables O(log n) interval collision detection in up to n dimensions, essential for spatial indexing and range query problems
• Sparse Bitarray (using interpolation search or similar) — bitarray/sparse_bitarray.go trades insertion time O(log n) for space efficiency; critical for large sparse sets (e.g., flagging 1M active users out of 1B possible)
• Fibonacci Heap — Mentioned in README as enabling O(1) amortized decrease-key and O(1) find-min; enables theoretically optimal Dijkstra/Prim implementations, which the README highlights as a use case
• Lock-Free Data Structures (CAS-based) — queue/ ring buffer uses only atomic CAS operations for thread safety without mutexes; essential for understanding why this queue is 'quite fast' and suitable for high-throughput goroutine coordination
• B-Tree (Mutable and Immutable Variants) — btree/_link and btree/immutable/ provide both mutable (thread-safe with locks) and immutable (functional, copy-on-write) sorted maps; understanding both tradeoffs is critical for choosing the right variant
• Broadcast Pattern (vs. Channel Recv) — futures/ package solves the Go channel limitation that only one goroutine can recv a value; enables fan-out notification of multiple listeners, a common concurrent systems pattern
• Bit-Array Intersection (AND/OR/NAND) — bitarray/ provides AND, OR, NAND operations used by augmentedtree/intervals.go for efficient multi-dimensional collision detection; understand bit manipulation for interval overlap computation

• google/btree — Alternative B-tree implementation in Go; compare mutable performance and API design with btree/_link
• eapache/queue — Simpler queue abstraction for Go; see how this repo's thread-safe queue design differs in complexity and performance
• plar/go-adaptive-radix-tree — Alternative adaptive radix tree for range queries; understand tradeoffs vs. augmented red-black trees for spatial data
• Workiva/go-intervals — Companion library from same org; likely integrates with augmentedtree/intervals.go for interval math
• gammazero/deque — Concurrent deque alternative; compare with queue/ implementations for non-priority use cases

To work on one of these in Claude Code or Cursor, paste: Implement the "<title>" PR idea from CLAUDE.md, working through the checklist as the task list.

Add Go 1.15+ version-specific CI validation in tests.yaml

The README states 'only tested with Go 1.3+' but go.mod specifies Go 1.15. The .github/workflows/tests.yaml likely only tests a single Go version. Adding a matrix strategy to test against Go 1.15, 1.18, 1.19, and 1.20+ would catch version-specific regressions and verify the actual minimum supported version, ensuring thread-safety guarantees hold across versions.

• [ ] Examine .github/workflows/tests.yaml to identify current Go version matrix
• [ ] Add 'strategy.matrix.go-version' with [1.15, 1.18, 1.19, latest]
• [ ] Update README.md to reflect tested Go versions instead of 'Go 1.3+'
• [ ] Run locally to verify all tests pass across versions

Add missing thread-safety and concurrency tests for bitarray package

The repo advertises itself as providing 'threadsafe Go datastructures' but bitarray/ has no concurrent access tests. The bitarray/bitarray.go, bitarray/sparse_bitarray.go, and bitarray/bitmap.go implementations likely use sync.RWMutex or similar, but there are no *_concurrent_test.go or race condition tests. This is critical for a library claiming thread-safety.

• [ ] Create bitarray/bitarray_concurrent_test.go with concurrent Read/Write/Delete operations
• [ ] Create bitarray/sparse_bitarray_concurrent_test.go with simultaneous Insert/Query stress tests
• [ ] Create bitarray/bitmap_concurrent_test.go for concurrent AND/OR/NAND operations
• [ ] Run with 'go test -race' to verify no data races are reported
• [ ] Verify tests pass with -count=100 for flakiness detection

Add missing thread-safety tests and concurrent benchmarks for btree/plus package

btree/plus/btree_test.go exists but contains no concurrent access patterns. The plus tree is likely used in concurrent scenarios but lacks evidence of thread-safe operation validation. Adding concurrent reader/writer tests and benchmarks would prove the implementation handles concurrent access correctly and provide performance metrics for concurrent operations.

• [ ] Create btree/plus/btree_concurrent_test.go with concurrent Insert/Search/Delete goroutines
• [ ] Add concurrent benchmark functions (BenchmarkConcurrentReads, BenchmarkConcurrentWrites) to btree/plus/btree_test.go
• [ ] Test with varying goroutine counts (10, 100, 1000) to stress-test lock contention
• [ ] Run with 'go test -race' to detect synchronization issues
• [ ] Document expected concurrent performance characteristics in btree/plus/interface.go

• Add comprehensive godoc examples to bitarray/interface.go and augmentedtree/interface.go—many public functions lack usage examples that would help new users avoid sparse_bitarray vs bitarray confusion.
• Expand bitarray/bitarray_test.go and bitarray/sparse_bitarray_test.go with benchmark comparisons (BenchmarkDenseVsSparse) to help users make informed decisions about which implementation to use.
• Document the sparse_bitarray.go O(log n) insertion complexity tradeoff with a code comment linking to the algorithmic rationale, and add an example in README showing when to use sparse vs. dense (currently only mentioned in text).

The codebase has a moderate security posture with several key issues. The most critical concern is the use of significantly outdated Go and Alpine versions that no longer receive security updates. The Dockerfile contains unused build arguments that could pose secrets leakage risks and results in an incomplete/non-functional final image. The project lacks automated security scanning and dependency management in its CI/CD pipeline. However, the codebase itself is a pure data structures library with no external network calls or database interactions, which limits certain categories of risk (SQLi, XSS, etc.). Recommended immediate actions: update Go and Alpine versions, remove unused build arguments, implement automated dependency scanning, and ensure the multi-stage Docker build is completed properly.

• High · Outdated Go Version in Dockerfile — Dockerfile (line 1). The Dockerfile uses Go 1.16 and Alpine 3.13, both of which are significantly outdated and no longer receive security updates. Go 1.16 reached end-of-life in September 2022, and Alpine 3.13 is no longer maintained. This exposes the build environment to known vulnerabilities. Fix: Update to a current, actively maintained Go version (1.21 or later) and Alpine version (3.18 or later). Ensure the go.mod file's minimum version constraint is also updated accordingly.
• Medium · Unused SSH Key and Known Hosts Arguments — Dockerfile (lines 2-3). The Dockerfile accepts GIT_SSH_KEY and KNOWN_HOSTS_CONTENT as build arguments but never uses them. These arguments could inadvertently expose secrets if leaked in build history or logs, and unused arguments indicate incomplete or leftover configuration. Fix: Remove unused build arguments. If SSH access is needed for private dependencies, use a multi-stage build and ensure secrets are properly handled via Docker secrets or BuildKit secrets, never passed as plain arguments.
• Medium · Missing SBOM and Dependency Pinning — go.mod. Dependencies in go.mod use loose version constraints (v1.7.0, v1.1.5). While Go modules provide some protection, there is no evidence of Software Bill of Materials (SBOM) generation or lock file verification in the CI/CD pipeline (.github/workflows/tests.yaml not fully analyzed). Fix: Use exact version pinning in go.mod. Implement SBOM generation as part of the CI/CD pipeline. Consider using tools like syft or cyclonedx-gomod to track all dependencies and their versions.
• Low · Scratch Image with No Base Packages — Dockerfile (line 19). The Dockerfile has a second stage using 'FROM scratch', which is good for minimizing attack surface. However, the build artifacts are never copied to this stage, making the final image empty or non-functional. This indicates incomplete configuration. Fix: Either complete the multi-stage build by copying artifacts from the build stage to scratch, or use an appropriate base image (golang:1.21-alpine) for the final stage if a functional container is intended.
• Low · No Security Headers or Dependency Scanning in CI/CD — .github/workflows/tests.yaml (not shown). Based on the file structure, there is no evidence of automated dependency scanning (e.g., Dependabot, Snyk) or security linting tools (e.g., gosec) in the GitHub Actions workflow. Fix: Integrate automated security scanning into the CI/CD pipeline using tools like GitHub Dependabot, gosec (for Go security issues), and govulncheck (for known vulnerabilities). Add these checks as blocking steps in the workflow.
• Low · Lack of Input Validation Documentation — README.md, augmentedtree/, bitarray/, btree/. The codebase implements data structures (augmented trees, bitarrays, btrees) that accept user input. No security documentation or input validation guidelines are visible in the README or structure. Fix: Document expected input constraints and add input validation in public APIs. Consider adding security guidelines for safe usage of these data structures.

LLM-derived; treat as a starting point, not a security audit.

• Open issues — current backlog
• Recent PRs — what's actively shipping
• Source on GitHub

Generated by RepoPilot. Verdict based on maintenance signals — see the live page for receipts. Re-run on a new commit to refresh.