Implement a Custom context.WithValue in Go

Go's context package provides a way to carry request-scoped values, cancellation signals, and deadlines across API boundaries and between processes. A common pattern is using context.WithValue to associate custom data with a context. Your challenge is to implement a similar functionality, allowing you to create a new context that is derived from a parent context and carries a specific key-value pair.

Problem Description

You need to create a function WithValue that mimics the behavior of context.WithValue. This function should take a parent context.Context, a key interface{}, and a value interface{} as input. It should return a new context.Context that is derived from the parent and carries the provided key-value pair.

Key requirements:

• The returned context must embed the parent context. This means that if the key is not found in the derived context, the lookup should proceed to the parent context.
• The key must be comparable. This is a fundamental requirement for context.WithValue to prevent accidental overwrites and ensure predictable behavior.
• The function should handle cases where the parent context is nil.
• The implementation should allow for multiple key-value pairs to be added sequentially, with each new context wrapping the previous one.

Expected Behavior:

When a context created by WithValue is queried for a key, it should first check if the key matches the one it stores. If it does, the associated value should be returned. If the key does not match, the lookup should be delegated to the parent context.

Examples

Example 1:

package main

import (
	"context"
	"fmt"
)

type contextKey string

const (
	requestIDKey contextKey = "requestID"
)

func main() {
	parentCtx := context.Background()
	ctxWithReqID := WithValue(parentCtx, requestIDKey, "abc-123")

	fmt.Printf("Value for requestIDKey: %v\n", ctxWithReqID.Value(requestIDKey))
	fmt.Printf("Value for nonExistentKey: %v\n", ctxWithReqID.Value("nonExistentKey"))
}

// Expected Output:
// Value for requestIDKey: abc-123
// Value for nonExistentKey: <nil>

Explanation: A background context is created. A new context is derived with requestIDKey and the value "abc-123". When Value(requestIDKey) is called on this new context, it returns "abc-123". When Value("nonExistentKey") is called, the key is not found in the derived context, and it delegates to the parent (background context), which also doesn't have this key, thus returning nil.

Example 2:

package main

import (
	"context"
	"fmt"
)

type contextKey string

const (
	userIDKey    contextKey = "userID"
	sessionIDKey contextKey = "sessionID"
)

func main() {
	parentCtx := context.Background()
	ctxWithSession := WithValue(parentCtx, sessionIDKey, "sess-xyz")
	ctxWithUserAndSession := WithValue(ctxWithSession, userIDKey, 456)

	fmt.Printf("Value for userIDKey: %v\n", ctxWithUserAndSession.Value(userIDKey))
	fmt.Printf("Value for sessionIDKey: %v\n", ctxWithUserAndSession.Value(sessionIDKey))
	fmt.Printf("Value for anotherKey: %v\n", ctxWithUserAndSession.Value("anotherKey"))
}

// Expected Output:
// Value for userIDKey: 456
// Value for sessionIDKey: sess-xyz
// Value for anotherKey: <nil>

Explanation: A context with a session ID is created. Then, another context is derived from that, adding a user ID. When querying for userIDKey, the most recent context returns the value. When querying for sessionIDKey, the most recent context doesn't have it, so it delegates to its parent, which does, returning the session ID. A non-existent key returns nil.

Example 3:

package main

import (
	"context"
	"fmt"
)

type contextKey string

const (
	configKey contextKey = "config"
)

func main() {
	// Demonstrating nil parent context
	nilParentCtx := nil
	ctxFromNil := WithValue(nilParentCtx, configKey, map[string]string{"host": "localhost"})

	fmt.Printf("Value from nil parent: %v\n", ctxFromNil.Value(configKey))
}

// Expected Output:
// Value from nil parent: map[host:localhost]

Explanation: When the parent context is nil, WithValue should still be able to create a valid context containing the key-value pair.

Constraints

• The key provided to WithValue must be comparable (e.g., string, int, custom types that support comparison). The underlying implementation relies on map lookups, which require comparable keys.
• The function should be efficient, with Value lookups typically taking O(1) time on average for the specific context and O(N) in the worst case where N is the depth of context chaining, but significantly faster than manually traversing.
• The WithValue function should not modify the original parent context.

Notes

You will need to define a custom type that implements the context.Context interface. This custom type will need to store the parent context, the key, and the value.

Consider how the Value method of your custom context type will handle both finding the stored key and delegating to the parent context when the key is not found.

The context.WithValue function in the standard library uses an unexported valueCtx type. You can choose to create your own unexported type for this challenge.