CVE-2024-31452 (Go, published 2024-04-16T22:15Z)
Description: value: OpenFGA is a high-performance and flexible authorization/permission engine. Some end users of OpenFGA v1.5.0 or later are vulnerable to authorization bypass when calling Check or ListObjects APIs. You are very likely affected if your model involves exclusion (e.g. `a but not b`) or intersection (e.g. `a and b`). This vulnerability is fixed in v1.5.3.
Severity: nan (CVSS v3 base score: )
Weakness: NVD-CWE-noinfo \u2014 Insufficient Information
There is insufficient information about the issue to classify it; details are unkown or unspecified.
Repository: https://github.com/openfga/openfga
Files changed:
assets/tests/consolidated_1_1_tests.yaml
internal/graph/cached_resolver.go
internal/graph/cached_resolver_test.go
internal/graph/check.go
internal/graph/check_test.go
internal/graph/cycle_check_resolver.go
internal/graph/cycle_check_resolver_test.go
internal/graph/graph.go
pkg/server/commands/list_objects.go
pkg/server/server.go
pkg/server/server_test.go
Commit message: Merge pull request from GHSA-8cph-m685-6v6r

* fix: error handling leading to false positives

* test: add a failing test due to Check and ListObjects differences

* test: change test expectation for ListObjects assertion

* fix: union CheckFuncReducer and associated tests

* fix: intersection CheckFuncReducer

* fix: exclusion CheckFuncReducer

* fix: rewire the cycle detection mechanics to avoid error propagation

* test: add more edge case tests for cyclical evaluations

* test: rename new test that was poorly named

* chore: revert minor change that was unintended

* chore: tidy up changes and drop commented out code

* chore: minor touchups based on some feedback

* test: add test for CloneResolveCheckResponse

* test: add more tests for error around intersection

* test: more test assertions around cloned cached response

* test: add unit test to make sure we cache CycleDetected

* test: add more assertions around CycleDetected field

* chore: rename test names

* chore: fix datastore query count under reporting in intersection reducer

Vulnerable code:
// CachedResolveCheckResponse is very similar to ResolveCheckResponse except we
// do not store the ResolutionData. This is due to the fact that the resolution metadata
// will be incorrect as data is served from cache instead of actual database read.
type CachedResolveCheckResponse struct {
	Allowed bool
}

func (c *CachedResolveCheckResponse) convertToResolveCheckResponse() *ResolveCheckResponse {
	return &ResolveCheckResponse{
		Allowed: c.Allowed,
		ResolutionMetadata: &ResolveCheckResponseMetadata{
			DatastoreQueryCount: 0,
		},
	}
}

func newCachedResolveCheckResponse(r *ResolveCheckResponse) *CachedResolveCheckResponse {
	return &CachedResolveCheckResponse{
		Allowed: r.Allowed,
	}
}

	cache        *ccache.Cache[*CachedResolveCheckResponse]
func WithExistingCache(cache *ccache.Cache[*CachedResolveCheckResponse]) CachedCheckResolverOpt {
			ccache.Configure[*CachedResolveCheckResponse]().MaxSize(checker.maxCacheSize),
		return cachedResp.Value().convertToResolveCheckResponse(), nil
	c.cache.Set(cacheKey, newCachedResolveCheckResponse(resp), c.cacheTTL)
		ccache.Configure[*CachedResolveCheckResponse]().MaxSize(100),
var (
	ErrCycleDetected = errors.New("a cycle has been detected")
)

				if errors.Is(result.err, ErrCycleDetected) {
					continue
				}
	}, err

				if errors.Is(result.err, ErrCycleDetected) {
					return &ResolveCheckResponse{
						Allowed: false,
						ResolutionMetadata: &ResolveCheckResponseMetadata{
							DatastoreQueryCount: dbReads,
						},
					}, nil
				}

			if !result.resp.GetAllowed() {
	}, err

				if errors.Is(baseResult.err, ErrCycleDetected) {
					return &ResolveCheckResponse{
						Allowed: false,
						ResolutionMetadata: &ResolveCheckResponseMetadata{
							DatastoreQueryCount: dbReads,
						},
					}, nil
				}


				if !errors.Is(subResult.err, ErrCycleDetected) {
					subErr = subResult.err
				}

	if baseErr != nil && subErr != nil {
		return &ResolveCheckResponse{
			Allowed: false,
			ResolutionMetadata: &ResolveCheckResponseMetadata{
				DatastoreQueryCount: 0,
			},
		}, errors.Join(baseErr, subErr)
			return resp, err
	resp, err := union(ctx, c.concurrencyLimit, c.checkRewrite(ctx, req, rel.GetRewrite()))
				return response, err
				return response, err
					return response, err
		response := &ResolveCheckResponse{
			Allowed: false,
			ResolutionMetadata: &ResolveCheckResponseMetadata{
				DatastoreQueryCount: req.GetRequestMetadata().DatastoreQueryCount + 1,
			},
		}
			return response, err
				return response, err
		return nil, ErrCycleDetected
	t.Run("base_handler_is_falsy_return_allowed:false", func(t *testing.T) {
	t.Run("base_handler_is_falsy_subtract_handler_with_error_return_allowed:false", func(t *testing.T) {
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(1+2))
	t.Run("base_handler_with_error_subtract_handler_is_truthy_return_allowed:false", func(t *testing.T) {
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(2+1))
	t.Run("base_handler_with_error_subtract_handler_with_error_return_error", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, depthExceededHandler, depthExceededHandler)
		require.ErrorIs(t, err, ErrResolutionDepthExceeded)
		require.Equal(t, uint32(0), resp.GetResolutionMetadata().DatastoreQueryCount)
	t.Run("base_handler_with_cycle_subtract_handler_is_falsy_return_allowed:false_with_a_nil_error", func(t *testing.T) {
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(2+1))
	t.Run("base_handler_with_cycle_subtract_handler_is_truthy_return_allowed:false_with_a_nil_error", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, cyclicErrorHandler, trueHandler)
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(2+1))
	t.Run("base_handler_is_falsy_subtract_handler_with_cycle_return_allowed:false_with_a_nil_error", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, falseHandler, cyclicErrorHandler)
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(1+2))
	t.Run("base_handler_is_truthy_subtract_handler_with_cycle_return_allowed:true_with_a_nil_error", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, trueHandler, cyclicErrorHandler)
		require.True(t, resp.GetAllowed())
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(1+2))
	t.Run("base_handler_with_cycle_subtract_handler_with_cycle_return_allowed:false_with_a_nil_error", func(t *testing.T) {
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(2+2))
		slowHandler := func(context.Context) (*ResolveCheckResponse, error) {
			return nil, nil
		resp, err := exclusion(ctx, concurrencyLimit, slowHandler, slowHandler)
		require.False(t, resp.GetAllowed())
			return nil, nil
		require.False(t, resp.GetAllowed())
	t.Run("no_handlers_return_allowed:false", func(t *testing.T) {
	t.Run("one_handler_is_falsy_return_allowed:false", func(t *testing.T) {
	t.Run("one_handler_is_truthy_and_others_are_falsy_return_allowed:false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, trueHandler, falseHandler, falseHandler)
	t.Run("all_handlers_are_falsy_return_allowed:false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, falseHandler, falseHandler, falseHandler)
	t.Run("all_handlers_with_error_return_error", func(t *testing.T) {
		_, err := intersection(ctx, concurrencyLimit, depthExceededHandler, depthExceededHandler)
	t.Run("one_handler_returns_error_but_other_handler_is_truthy_return_error_and_allowed:false", func(t *testing.T) {
		_, err := intersection(ctx, concurrencyLimit, depthExceededHandler, trueHandler)
	t.Run("one_handler_returns_error_but_other_handler_is_falsy_return_allowed:false_with_a_nil_error", func(t *testing.T) {
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(1+2))
	t.Run("one_handler_errors_with_cycle_but_other_handler_is_falsy_return_allowed:false_with_a_nil_error", func(t *testing.T) {
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(1+2))
	t.Run("one_handler_errors_with_cycle_but_other_handler_is_truthy_return_allowed:false_with_a_nil_error", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, cyclicErrorHandler, trueHandler)
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(1))
	t.Run("both_handlers_errors_with_cycle_return_allowed:false_with_a_nil_error", func(t *testing.T) {
		require.Equal(t, uint32(0), resp.GetResolutionMetadata().DatastoreQueryCount)
		slowHandler := func(context.Context) (*ResolveCheckResponse, error) {
			return nil, nil
		resp, err := intersection(ctx, concurrencyLimit, slowHandler)
		require.False(t, resp.GetAllowed())
		slowHandler := func(context.Context) (*ResolveCheckResponse, error) {
			return nil, nil
		resp, err := intersection(ctx, concurrencyLimit, slowHandler)
		require.False(t, resp.GetAllowed())
// TestCheckWithUnexpectedCycle tests the LocalChecker to make sure that if a model includes a cycle
// that should have otherwise been invalid according to the typesystem, then the check resolution will
// consider the cycle a falsey allowed result and not bubble-up a cycle detected error.
func TestCheckWithUnexpectedCycle(t *testing.T) {
	ds := memory.New()
	defer ds.Close()

	storeID := ulid.Make().String()

	err := ds.Write(context.Background(), storeID, nil, []*openfgav1.TupleKey{
		tuple.NewTupleKey("resource:1", "parent", "resource:1"),
	})
	require.NoError(t, err)

	tests := []struct {
		name     string
		model    string
		tupleKey *openfgav1.TupleKey
	}{
		{
			name: "test_1",
			model: `model
	schema 1.1
type user

type resource
  relations
	define x: [user] but not y
	define y: [user] but not z
	define z: [user] or x`,
			tupleKey: tuple.NewTupleKey("resource:1", "x", "user:jon"),
		},
		{
			name: "test_2",
			model: `model
	schema 1.1
type user

type resource
  relations
	define x: [user] and y
	define y: [user] and z
	define z: [user] or x`,
			tupleKey: tuple.NewTupleKey("resource:1", "x", "user:jon"),
		},
		{
			name: "test_3",
			model: `model
	schema 1.1
type resource
  relations
	define x: y
	define y: x`,
			tupleKey: tuple.NewTupleKey("resource:1", "x", "user:jon"),
		},
		{
			name: "test_4",
			model: `model
	schema 1.1
type resource
  relations
	define parent: [resource]
	define x: [user] or x from parent`,
			tupleKey: tuple.NewTupleKey("resource:1", "x", "user:jon"),
		},
	}

	checker := NewLocalCheckerWithCycleDetection()
	t.Cleanup(checker.Close)

	for _, test := range tests {
		t.Run(test.name, func(t *testing.T) {
			model := testutils.MustTransformDSLToProtoWithID(test.model)

			ctx := typesystem.ContextWithTypesystem(
				context.Background(),
				typesystem.New(model),
			)
			ctx = storage.ContextWithRelationshipTupleReader(ctx, ds)

			resp, err := checker.ResolveCheck(ctx, &ResolveCheckRequest{
				StoreID:         storeID,
				TupleKey:        test.tupleKey,
				RequestMetadata: NewCheckRequestMetadata(25),
			})

			require.NoError(t, err)
			require.False(t, resp.GetAllowed())

			require.GreaterOrEqual(t, resp.ResolutionMetadata.DatastoreQueryCount, uint32(0)) // min of 0 (x) if x is cycle. TODO: accurately report datastore query count of cycle branches
			require.LessOrEqual(t, resp.ResolutionMetadata.DatastoreQueryCount, uint32(3))    // max of 3 (x, y, z) before the cycle
		})
	}
}

	
	
  	
	t.Run("if_no_handlers_return_allowed_false", func(t *testing.T) {
	t.Run("if_one_handler_is_truthy_and_others_are_falsey_return_allowed_true", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, trueHandler, falseHandler, falseHandler)
	t.Run("if_all_handlers_are_falsey_return_allowed_false", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, falseHandler, falseHandler, falseHandler)
	t.Run("if_a_handler_errors_but_other_handler_are_truthy_return_allowed_true", func(t *testing.T) {
		depthExceededHandler := func(context.Context) (*ResolveCheckResponse, error) {
			return nil, ErrResolutionDepthExceeded
		}
		resp, err := union(ctx, concurrencyLimit, depthExceededHandler, trueHandler)
	t.Run("if_a_handler_errors_but_other_handler_is_falsey_return_error_and_allowed_false", func(t *testing.T) {
		depthExceededHandler := func(context.Context) (*ResolveCheckResponse, error) {
			return nil, ErrResolutionDepthExceeded
		}
		resp, err := union(ctx, concurrencyLimit, depthExceededHandler, falseHandler)
		require.ErrorIs(t, ErrResolutionDepthExceeded, err)
	t.Run("if_a_handler_errors_with_cycle_but_other_handler_is_falsey_return_allowed_false_with_a_nil_error", func(t *testing.T) {
		cyclicErrorHandler := func(context.Context) (*ResolveCheckResponse, error) {
			return nil, ErrCycleDetected
		}
	t.Run("both_handlers_with_cycle_return_allowed_false_with_nil_error", func(t *testing.T) {
		cyclicErrorHandler := func(context.Context) (*ResolveCheckResponse, error) {
			return nil, ErrCycleDetected
		}
	t.Run("if_a_handler_errors_with_cycle_but_other_handler_is_truthy_return_allowed_true_with_a_nil_error", func(t *testing.T) {
		cyclicErrorHandler := func(context.Context) (*ResolveCheckResponse, error) {
			return nil, ErrCycleDetected
		}
		resp, err := union(ctx, concurrencyLimit, cyclicErrorHandler, trueHandler)
		require.NoError(t, err)
		require.True(t, resp.GetAllowed())
	t.Run("should_aggregate_DatastoreQueryCount_of_non_error handlers", func(t *testing.T) {
			return nil, nil
		require.False(t, resp.GetAllowed())
		require.False(t, resp.GetAllowed())
		return nil, ErrCycleDetected
		require.ErrorIs(t, err, ErrCycleDetected)
	require.True(t, resp.GetAllowed())
						if errors.Is(err, graph.ErrResolutionDepthExceeded) || errors.Is(err, graph.ErrCycleDetected) {
				if errors.Is(err, graph.ErrResolutionDepthExceeded) || errors.Is(err, graph.ErrCycleDetected) {
		if errors.Is(err, graph.ErrResolutionDepthExceeded) || errors.Is(err, graph.ErrCycleDetected) {
	wg.Add(2)
	require.False(t, resp2.GetAllowed())

Fixed code:
  - name: cycle_or_cycle_return_false
    stages:
      - model: |
          model
            schema 1.1
          type user

          type document
            relations
              define editor: [user, document#viewer]
              define viewer: [document#editor] or editor
        tuples:
          - user: document:1#viewer
            relation: editor
            object: document:1
          - user: document:1#editor
            relation: viewer
            object: document:1
        checkAssertions:
          - tuple:
              object: document:1
              relation: viewer
              user: user:jon
            expectation: false
        listObjectsAssertions:
          - request:
              user: user:jon
              type: document
              relation: viewer
            expectation:
  - name: immediate_cycle_through_computed_userset
    stages:
      - model: |
          model
            schema 1.1
          type user

          type document
            relations
              define editor: [user, document#viewer]
              define viewer: editor
        tuples:
          - user: document:1#viewer
            relation: editor
            object: document:1
        checkAssertions:
          - tuple:
              object: document:1
              relation: viewer
              user: user:jon
            expectation: false
        listObjectsAssertions:
          - request:
              user: user:jon
              type: document
              relation: viewer
            expectation:
  - name: immediate_cycle_through_computed_userset
    stages:
      - model: |
          model
            schema 1.1
          type user

          type document
            relations
              define editor: [user, document#viewer]
              define viewer: editor
        tuples:
          - user: document:1#viewer
            relation: editor
            object: document:1
        checkAssertions:
          - tuple:
              object: document:1
              relation: viewer
              user: user:jon
            expectation: false
        listObjectsAssertions:
          - request:
              user: user:jon
              type: document
              relation: viewer
            expectation:
  - name: true_butnot_cycle_return_false
    stages:
      - model: |
          model
            schema 1.1
          type user

          type document
            relations
              define restricted: [user, document#viewer]
              define viewer: [user] but not restricted
        tuples:
          - user: user:jon
            relation: viewer
            object: document:1
          - user: document:1#viewer
            relation: restricted
            object: document:1
        checkAssertions:
          - tuple:
              object: document:1
              relation: viewer
              user: user:jon
            expectation: false
        listObjectsAssertions:
          - request:
              user: user:jon
              type: document
              relation: viewer
            expectation:
  - name: cycle_and_cycle_return_false
    stages:
      - model: |
          model
            schema 1.1

          type user

          type document
            relations
              define editor: [user, document#viewer]
              define viewer: [user, document#editor] and editor
        tuples:
          - user: document:1#editor
            relation: viewer
            object: document:1
          - user: document:1#viewer
            relation: editor
            object: document:1
        checkAssertions:
          - tuple:
              object: document:1
              relation: viewer
              user: user:jon
            expectation: false
        listObjectsAssertions:
          - request:
              user: user:jon
              type: document
              relation: viewer
            expectation:
  - name: cycle_and_true_return_false
    stages:
      - model: |
          model
            schema 1.1

          type user

          type document
            relations
              define allowed: [user]
              define viewer: [user, document#viewer] and allowed
        tuples:
          - user: user:jon
            relation: allowed
            object: document:1
          - user: document:1#viewer
            relation: viewer
            object: document:1
        checkAssertions:
          - tuple:
              object: document:1
              relation: viewer
              user: user:jon
            expectation: false
        listObjectsAssertions:
          - request:
              user: user:jon
              type: document
              relation: viewer
            expectation:
  - name: immediate_cycle_return_false
    stages:
      - model: |
          model
            schema 1.1

          type user

          type document
            relations
              define viewer: [user, document#viewer]
        tuples:
          - user: document:1#viewer
            relation: viewer
            object: document:1
        checkAssertions:
          - tuple:
              object: document:1
              relation: viewer
              user: user:jon
            expectation: false
        listObjectsAssertions:
          - request:
              user: user:jon
              type: document
              relation: viewer
            expectation:
  - name: cycle_butnot_false_return_false
    stages:
      - model: |
          model
            schema 1.1

          type user

          type document
            relations
              define restricted: [user]
              define viewer: [user, document#viewer] but not restricted
        tuples:
          - user: document:1#viewer
            relation: viewer
            object: document:1
        checkAssertions:
          - tuple:
              object: document:1
              relation: viewer
              user: user:jon
            expectation: false
        listObjectsAssertions:
          - request:
              user: user:jon
              type: document
              relation: viewer
            expectation:
  - name: false_butnot_cycle_return_false
    stages:
      - model: |
          model
            schema 1.1

          type user

          type document
            relations
              define restricted: [user, document#viewer]
              define viewer: [user] but not restricted
        tuples:
          - user: document:1#viewer
            relation: restricted
            object: document:1
        checkAssertions:
          - tuple:
              object: document:1
              relation: viewer
              user: user:jon
            expectation: false
        listObjectsAssertions:
          - request:
              user: user:jon
              type: document
              relation: viewer
            expectation:
  - name: err_and_err_return_err
    stages:
      - model: |
          model
            schema 1.1
          type user
          type resource
            relations
              define a1: a2
              define a2: a3
              define a3: a4
              define a4: a5
              define a5: a6
              define a6: a7
              define a7: a8
              define a8: a9
              define a9: a10
              define a10: a11
              define a11: a12
              define a12: a13
              define a13: a14
              define a14: a15
              define a15: a16
              define a16: a17
              define a17: a18
              define a18: a19
              define a19: a20
              define a20: a21
              define a21: a22
              define a22: a23
              define a23: a24
              define a24: a25
              define a25: a26
              define a26: [user]
              define can_view: a1 and a1
        tuples:
          - object: resource:abc
            relation: a26
            user: user:maria
        checkAssertions:
          - tuple:
              object: resource:abc
              relation: can_view
              user: user:maria
            errorCode: 2002
        listObjectsAssertions:
          - request:
              type: resource
              relation: can_view
              user: user:maria
            errorCode: 2002
  - name: err_and_true_return_err
    stages:
      - model: |
          model
            schema 1.1
          type user
          type resource
            relations
              define a1: a2
              define a2: a3
              define a3: a4
              define a4: a5
              define a5: a6
              define a6: a7
              define a7: a8
              define a8: a9
              define a9: a10
              define a10: a11
              define a11: a12
              define a12: a13
              define a13: a14
              define a14: a15
              define a15: a16
              define a16: a17
              define a17: a18
              define a18: a19
              define a19: a20
              define a20: a21
              define a21: a22
              define a22: a23
              define a23: a24
              define a24: a25
              define a25: a26
              define a26: [user]
              define can_view: a1 and a26
        tuples:
          - object: resource:abc
            relation: a26
            user: user:maria
        checkAssertions:
          - tuple:
              object: resource:abc
              relation: can_view
              user: user:maria
            errorCode: 2002
        listObjectsAssertions:
          - request:
              type: resource
              relation: can_view
              user: user:maria
            errorCode: 2002
	cache        *ccache.Cache[*ResolveCheckResponse]
func WithExistingCache(cache *ccache.Cache[*ResolveCheckResponse]) CachedCheckResolverOpt {
			ccache.Configure[*ResolveCheckResponse]().MaxSize(checker.maxCacheSize),

		return cachedResp.Value(), nil
	// the cached subproblem's resolution metadata doesn't necessarily reflect
	// the actual number of database reads for the inflight request, so set it
	// to 0 so it doesn't bias the resolution metadata negatively
	clonedResp := CloneResolveCheckResponse(resp)
	clonedResp.ResolutionMetadata.DatastoreQueryCount = 0

	c.cache.Set(cacheKey, clonedResp, c.cacheTTL)
func TestCachedCheckResolver_CycleDetected(t *testing.T) {
	cachedCheckResolver := NewCachedCheckResolver()
	defer cachedCheckResolver.Close()

	mockCtrl := gomock.NewController(t)
	t.Cleanup(mockCtrl.Finish)

	mockCheckResolver := NewMockCheckResolver(mockCtrl)
	cachedCheckResolver.SetDelegate(mockCheckResolver)

	mockCheckResolver.EXPECT().
		ResolveCheck(gomock.Any(), gomock.Any()).
		Return(&ResolveCheckResponse{
			Allowed: false,
			ResolutionMetadata: &ResolveCheckResponseMetadata{
				DatastoreQueryCount: 1,
				CycleDetected:       true,
			},
		}, nil)

	resp, err := cachedCheckResolver.ResolveCheck(context.Background(), &ResolveCheckRequest{})
	require.NoError(t, err)
	require.NotNil(t, resp)
	require.Equal(t, uint32(1), resp.GetResolutionMetadata().DatastoreQueryCount)
	require.True(t, resp.GetResolutionMetadata().CycleDetected)

	resp, err = cachedCheckResolver.ResolveCheck(context.Background(), &ResolveCheckRequest{})
	require.NoError(t, err)
	require.NotNil(t, resp)
	require.Equal(t, uint32(0), resp.GetResolutionMetadata().DatastoreQueryCount)
	require.True(t, resp.GetResolutionMetadata().CycleDetected)
}

		ccache.Configure[*ResolveCheckResponse]().MaxSize(100),
// CloneResolveCheckResponse clones the provided ResolveCheckResponse.
//
// If 'r' defines a nil ResolutionMetadata then this function returns
// an empty value struct for the resolution metadata instead of nil.
func CloneResolveCheckResponse(r *ResolveCheckResponse) *ResolveCheckResponse {
	resolutionMetadata := &ResolveCheckResponseMetadata{
		DatastoreQueryCount: 0,
		CycleDetected:       false,
	}

	if r.GetResolutionMetadata() != nil {
		resolutionMetadata.DatastoreQueryCount = r.GetResolutionMetadata().DatastoreQueryCount
		resolutionMetadata.CycleDetected = r.GetResolutionMetadata().CycleDetected
	}

	return &ResolveCheckResponse{
		Allowed:            r.GetAllowed(),
		ResolutionMetadata: resolutionMetadata,
	}
}

func (r *ResolveCheckResponse) GetCycleDetected() bool {
	if r != nil {
		return r.GetResolutionMetadata().CycleDetected
	}

	return false
}

	var cycleDetected bool

			if result.resp.GetCycleDetected() {
				cycleDetected = true
			}

	if err != nil {
		return nil, err
	}

			CycleDetected:       cycleDetected,
	}, nil
			if result.resp.GetCycleDetected() || !result.resp.GetAllowed() {
	// all operands are either truthy or we've seen at least one error
	if err != nil {
		return nil, err
	}

	}, nil
			if baseResult.resp.GetCycleDetected() {
				return &ResolveCheckResponse{
					Allowed: false,
					ResolutionMetadata: &ResolveCheckResponseMetadata{
						DatastoreQueryCount: dbReads,
						CycleDetected:       true,
					},
				}, nil
			}

				subErr = subResult.err
			if subResult.resp.GetCycleDetected() {
				return &ResolveCheckResponse{
					Allowed: false,
					ResolutionMetadata: &ResolveCheckResponseMetadata{
						DatastoreQueryCount: dbReads,
						CycleDetected:       true,
					},
				}, nil
			}

	// base is either (true) or error, sub is either (false) or error:
	// true, false - true
	// true, error - error
	// error, false - error
	// error, error - error
	if baseErr != nil || subErr != nil {
		return nil, errors.Join(baseErr, subErr)
			return nil, err
	resp, err := c.checkRewrite(ctx, req, rel.GetRewrite())(ctx)
				return nil, err
				return nil, err
					return nil, err
			return nil, err
				return nil, err
	"errors"
		return &ResolveCheckResponse{
			Allowed: false,
			ResolutionMetadata: &ResolveCheckResponseMetadata{
				DatastoreQueryCount: 1,
				CycleDetected:       true,
			},
		}, nil
	}

	simulatedDBErrorMessage = "simulated db error"

	generalErrorHandler = func(context.Context) (*ResolveCheckResponse, error) {
		return nil, errors.New(simulatedDBErrorMessage)
	t.Run("true_butnot_true_return_false", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, trueHandler, trueHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(1+1))
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("true_butnot_false_return_true", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, trueHandler, falseHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.True(t, resp.GetAllowed())
		require.Equal(t, uint32(1+1), resp.GetResolutionMetadata().DatastoreQueryCount)
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("false_butnot_true_return_false", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, falseHandler, trueHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(1+1))
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("false_butnot_false_return_false", func(t *testing.T) {
		require.NotNil(t, resp)
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("true_butnot_err_return_err", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, trueHandler, generalErrorHandler)
		require.EqualError(t, err, simulatedDBErrorMessage)
		require.Nil(t, resp)
	})

	t.Run("true_butnot_errResolutionDepth_return_errResolutionDepth", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, trueHandler, depthExceededHandler)
		require.ErrorIs(t, err, ErrResolutionDepthExceeded)
		require.Nil(t, resp)
	t.Run("true_butnot_cycle_return_false", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, trueHandler, cyclicErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.True(t, resp.GetCycleDetected())
	})

	t.Run("false_butnot_err_return_false", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, falseHandler, generalErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("false_butnot_errResolutionDepth_return_false", func(t *testing.T) {
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("false_butnot_cycle_return_false", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, falseHandler, cyclicErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
	t.Run("err_butnot_true_return_false", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, generalErrorHandler, trueHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("errResolutionDepth_butnot_true_return_false", func(t *testing.T) {
		require.NotNil(t, resp)
		require.False(t, resp.GetCycleDetected())
	t.Run("cycle_butnot_true_return_false", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, cyclicErrorHandler, trueHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
	t.Run("err_butnot_false_return_err", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, generalErrorHandler, falseHandler)
		require.EqualError(t, err, simulatedDBErrorMessage)
		require.Nil(t, resp)
	})

	t.Run("errResolutionDepth_butnot_false_return_errResolutionDepth", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, depthExceededHandler, falseHandler)
		require.ErrorIs(t, err, ErrResolutionDepthExceeded)
		require.Nil(t, resp)
	})

	t.Run("cycle_butnot_false_return_false", func(t *testing.T) {
		require.NotNil(t, resp)
		require.True(t, resp.GetCycleDetected())
	t.Run("cycle_butnot_err_return_false", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, cyclicErrorHandler, generalErrorHandler)
		require.NotNil(t, resp)
		require.True(t, resp.GetCycleDetected())
	t.Run("cycle_butnot_errResolutionDepth_return_false", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, cyclicErrorHandler, depthExceededHandler)
		require.NotNil(t, resp)
		require.True(t, resp.GetCycleDetected())
	t.Run("err_butnot_cycle_return_false", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, generalErrorHandler, cyclicErrorHandler)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.True(t, resp.GetCycleDetected())
	})

	t.Run("errResolutionDepth_butnot_cycle_return_false", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, depthExceededHandler, cyclicErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.True(t, resp.GetCycleDetected())
	t.Run("cycle_butnot_cycle_return_false", func(t *testing.T) {
		require.NotNil(t, resp)
		require.True(t, resp.GetCycleDetected())
	})

	t.Run("err_butnot_err_return_err", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, generalErrorHandler, generalErrorHandler)
		require.ErrorContains(t, err, simulatedDBErrorMessage)
		require.Nil(t, resp)
	})

	t.Run("errResolutionDepth_butnot_errResolutionDepth_return_errResolutionDepth", func(t *testing.T) {
		resp, err := exclusion(ctx, concurrencyLimit, depthExceededHandler, depthExceededHandler)
		require.ErrorIs(t, err, ErrResolutionDepthExceeded)
		require.Nil(t, resp)
	t.Run("return_allowed:false_if_sub_handler_evaluated_before_context_cancelled", func(t *testing.T) {
		ctx, cancel := context.WithCancel(context.Background())
		t.Cleanup(cancel)

		var wg sync.WaitGroup

		wg.Add(1)
		go func() {
			defer wg.Done()
			time.Sleep(10 * time.Millisecond)
			cancel()
		}()

		resp, err := exclusion(ctx, concurrencyLimit, trueHandler, trueHandler)
		require.NoError(t, err)
		require.False(t, resp.GetAllowed())

		wg.Wait() // just to make sure to avoid test leaks
	})

	t.Run("return_allowed:false_if_sub_handler_evaluated_before_base_cancelled", func(t *testing.T) {
		ctx, cancel := context.WithCancel(context.Background())
		t.Cleanup(cancel)

		var wg sync.WaitGroup

		slowTrueHandler := func(context.Context) (*ResolveCheckResponse, error) {
			time.Sleep(50 * time.Millisecond)

			return &ResolveCheckResponse{
				Allowed: true,
			}, nil
		}

		wg.Add(1)
		go func() {
			defer wg.Done()
			time.Sleep(10 * time.Millisecond)
			cancel()
		}()

		resp, err := exclusion(ctx, concurrencyLimit, slowTrueHandler, trueHandler)
		require.NoError(t, err)
		require.False(t, resp.GetAllowed())

		wg.Wait() // just to make sure to avoid test leaks
	})

		slowTrueHandler := func(context.Context) (*ResolveCheckResponse, error) {
			return &ResolveCheckResponse{
				Allowed: true,
			}, nil
		slowFalseHandler := func(context.Context) (*ResolveCheckResponse, error) {
			time.Sleep(50 * time.Millisecond)
			return &ResolveCheckResponse{
				Allowed: false,
			}, nil
		}

		resp, err := exclusion(ctx, concurrencyLimit, slowTrueHandler, slowFalseHandler)
		require.Nil(t, resp)
			return &ResolveCheckResponse{}, nil
		require.Nil(t, resp)
	t.Run("no_handlers_return_false", func(t *testing.T) {
		require.False(t, resp.GetCycleDetected())
	t.Run("false_return_false", func(t *testing.T) {
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("true_and_true_return_true", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, trueHandler, trueHandler)
		require.NoError(t, err)
		require.True(t, resp.GetAllowed())
		require.Equal(t, uint32(2), resp.GetResolutionMetadata().DatastoreQueryCount)
		require.False(t, resp.GetCycleDetected())
	t.Run("true_and_false_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, trueHandler, falseHandler)
		require.False(t, resp.GetCycleDetected())
	t.Run("false_and_true_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, falseHandler, trueHandler)
		require.NoError(t, err)
		require.False(t, resp.GetAllowed())
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(2))
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("false_and_false_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, falseHandler, falseHandler)
		require.False(t, resp.GetCycleDetected())
	t.Run("true_and_err_return_err", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, trueHandler, generalErrorHandler)
		require.EqualError(t, err, simulatedDBErrorMessage)
		require.Nil(t, resp)
	})

	t.Run("true_and_errResolutionDepth_return_err", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, trueHandler, depthExceededHandler)
		require.Nil(t, resp)
	})

	t.Run("true_and_cycle_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, trueHandler, cyclicErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.True(t, resp.GetCycleDetected())
	})

	t.Run("false_and_err_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, falseHandler, generalErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("false_and_errResolutionDepth_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, falseHandler, depthExceededHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("false_and_cycle_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, falseHandler, cyclicErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
	})

	t.Run("err_and_true_return_err", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, generalErrorHandler, trueHandler)
		require.EqualError(t, err, simulatedDBErrorMessage)
		require.Nil(t, resp)
	t.Run("errResolutionDepth_and_true_return_err", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, depthExceededHandler, trueHandler)
		require.Nil(t, resp)
	t.Run("cycle_and_true_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, cyclicErrorHandler, trueHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.True(t, resp.GetCycleDetected())
	})

	t.Run("err_and_false_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, generalErrorHandler, falseHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("errResolutionDepth_and_false_return_false", func(t *testing.T) {
		require.NotNil(t, resp)
		require.False(t, resp.GetCycleDetected())
	t.Run("cycle_and_false_return_false", func(t *testing.T) {
		require.NotNil(t, resp)
	t.Run("cycle_and_err_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, cyclicErrorHandler, generalErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.True(t, resp.GetCycleDetected())
	})

	t.Run("cycle_and_errResolutionDepth_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, cyclicErrorHandler, depthExceededHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.True(t, resp.GetCycleDetected())
	})

	t.Run("err_and_cycle_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, generalErrorHandler, cyclicErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.True(t, resp.GetCycleDetected())
	})

	t.Run("errResolutionDepth_and_cycle_return_false", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, depthExceededHandler, cyclicErrorHandler)
		require.NotNil(t, resp)
		require.True(t, resp.GetCycleDetected())
	t.Run("cycle_and_cycle_return_false", func(t *testing.T) {
		require.NotNil(t, resp)
		require.True(t, resp.GetCycleDetected())
	})

	t.Run("err_and_err_return_err", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, generalErrorHandler, generalErrorHandler)
		require.ErrorContains(t, err, simulatedDBErrorMessage)
		require.Nil(t, resp)
	})

	t.Run("errResolutionDepth_and_errResolutionDepth_return_errResolutionDepth", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, depthExceededHandler, depthExceededHandler)
		require.ErrorIs(t, err, ErrResolutionDepthExceeded)
		require.Nil(t, resp)
	})

	t.Run("true_and_cycle_and_err_return_err", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, trueHandler, cyclicErrorHandler, generalErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetAllowed())
		require.True(t, resp.GetCycleDetected())
	t.Run("cycle_and_false_reports_correct_datastore_query_count", func(t *testing.T) {
		resp, err := intersection(ctx, concurrencyLimit, cyclicErrorHandler, falseHandler)
		require.NoError(t, err)
		require.False(t, resp.GetAllowed())
		require.LessOrEqual(t, resp.GetResolutionMetadata().DatastoreQueryCount, uint32(1+1))
	})

	t.Run("return_true_if_truthy_handler_evaluated_before_context_deadline", func(t *testing.T) {
		ctx, cancel := context.WithTimeout(context.Background(), 10*time.Millisecond)
		t.Cleanup(cancel)

		resp, err := intersection(ctx, concurrencyLimit, trueHandler)
		require.NoError(t, err)
		require.True(t, resp.GetAllowed())
	})

	t.Run("return_error_if_context_deadline_before_truthy_handler", func(t *testing.T) {
		ctx, cancel := context.WithTimeout(context.Background(), 10*time.Millisecond)
		t.Cleanup(cancel)

		slowTrueHandler := func(context.Context) (*ResolveCheckResponse, error) {
			time.Sleep(50 * time.Millisecond)
			return &ResolveCheckResponse{
				Allowed: true,
			}, nil
		}

		resp, err := intersection(ctx, concurrencyLimit, slowTrueHandler)
		require.ErrorIs(t, err, context.DeadlineExceeded)
		require.Nil(t, resp)
	})

		slowTrueHandler := func(context.Context) (*ResolveCheckResponse, error) {
			return &ResolveCheckResponse{
				Allowed: true,
			}, nil
		resp, err := intersection(ctx, concurrencyLimit, slowTrueHandler)
		require.Nil(t, resp)
		slowTrueHandler := func(context.Context) (*ResolveCheckResponse, error) {
			return &ResolveCheckResponse{
				Allowed: true,
			}, nil
		resp, err := intersection(ctx, concurrencyLimit, slowTrueHandler)
		require.Nil(t, resp)
func TestNonStratifiableCheckQueries(t *testing.T) {
	t.Run("example_1", func(t *testing.T) {
		ds := memory.New()

		storeID := ulid.Make().String()

		err := ds.Write(context.Background(), storeID, nil, []*openfgav1.TupleKey{
			tuple.NewTupleKey("document:1", "viewer", "user:jon"),
			tuple.NewTupleKey("document:1", "restricted", "document:1#viewer"),
		})
		require.NoError(t, err)

		checker := NewLocalCheckerWithCycleDetection()
		t.Cleanup(checker.Close)

		model := testutils.MustTransformDSLToProtoWithID(`model
	schema 1.1
	type user


	type document
	  relations
		define viewer: [user] but not restricted
		define restricted: [user, document#viewer]`)

		ctx := typesystem.ContextWithTypesystem(
			context.Background(),
			typesystem.New(model),
		)

		ctx = storage.ContextWithRelationshipTupleReader(ctx, ds)

		resp, err := checker.ResolveCheck(ctx, &ResolveCheckRequest{
			StoreID:         storeID,
			TupleKey:        tuple.NewTupleKey("document:1", "viewer", "user:jon"),
			RequestMetadata: NewCheckRequestMetadata(10),
		})
		require.NoError(t, err)
		require.False(t, resp.GetAllowed())
	})

	t.Run("example_2", func(t *testing.T) {
		ds := memory.New()

		storeID := ulid.Make().String()

		err := ds.Write(context.Background(), storeID, nil, []*openfgav1.TupleKey{
			tuple.NewTupleKey("document:1", "viewer", "user:jon"),
			tuple.NewTupleKey("document:1", "restrictedb", "document:1#viewer"),
		})
		require.NoError(t, err)

		checker := NewLocalCheckerWithCycleDetection()
		t.Cleanup(checker.Close)

		model := testutils.MustTransformDSLToProtoWithID(`model
	schema 1.1
	type user


	type document
	  relations
		define viewer: [user] but not restricteda
		define restricteda: restrictedb
		define restrictedb: [user, document#viewer]
	`)

		ctx := typesystem.ContextWithTypesystem(
			context.Background(),
			typesystem.New(model),
		)

		ctx = storage.ContextWithRelationshipTupleReader(ctx, ds)

		resp, err := checker.ResolveCheck(ctx, &ResolveCheckRequest{
			StoreID:         storeID,
			TupleKey:        tuple.NewTupleKey("document:1", "viewer", "user:jon"),
			RequestMetadata: NewCheckRequestMetadata(10),
		})
		require.NoError(t, err)
		require.False(t, resp.GetAllowed())
	})
}




	t.Run("no_handlers_return_allowed_false", func(t *testing.T) {
		require.NotNil(t, resp)
		require.False(t, resp.GetCycleDetected())
	t.Run("true_or_true_return_true", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, trueHandler, trueHandler)
		require.NotNil(t, resp)
		require.False(t, resp.GetCycleDetected())
	t.Run("true_or_false_return_true", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, trueHandler, falseHandler)
		require.NotNil(t, resp)
		require.True(t, resp.GetAllowed())
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("false_or_true_return_true", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, falseHandler, trueHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.True(t, resp.GetAllowed())
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("false_or_false_return_false", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, falseHandler, falseHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.False(t, resp.GetCycleDetected())
	t.Run("true_or_err_return_true", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, trueHandler, generalErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.True(t, resp.GetAllowed())
		require.False(t, resp.GetCycleDetected())
	})
	t.Run("true_or_errResolutionDepth_return_true", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, trueHandler, depthExceededHandler)
		require.NotNil(t, resp)
		require.False(t, resp.GetCycleDetected())
	t.Run("true_or_cycle_return_true", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, trueHandler, cyclicErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.True(t, resp.GetAllowed())
		require.False(t, resp.GetCycleDetected())
	})
	t.Run("false_or_err_return_err", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, falseHandler, generalErrorHandler)
		require.EqualError(t, err, simulatedDBErrorMessage)
		require.Nil(t, resp)
	})

	t.Run("false_or_errResolutionDepth_return_err", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, falseHandler, depthExceededHandler)
		require.ErrorIs(t, err, ErrResolutionDepthExceeded)
		require.Nil(t, resp)
	})

	t.Run("false_or_cycle_return_false", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, falseHandler, cyclicErrorHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.True(t, resp.GetCycleDetected())
	t.Run("err_or_true_return_true", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, generalErrorHandler, trueHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.True(t, resp.GetAllowed())
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("cycle_or_true_return_true", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, cyclicErrorHandler, trueHandler)
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.True(t, resp.GetAllowed())
		require.False(t, resp.GetCycleDetected())
	})

	t.Run("err_or_false_return_err", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, generalErrorHandler, falseHandler)
		require.EqualError(t, err, simulatedDBErrorMessage)
		require.Nil(t, resp)
	})

	t.Run("errResolutionDepth_or_false_return_err", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, depthExceededHandler, falseHandler)
		require.ErrorIs(t, err, ErrResolutionDepthExceeded)
		require.Nil(t, resp)
	})
	t.Run("cycle_or_false_return_false", func(t *testing.T) {
		require.NotNil(t, resp)
		require.True(t, resp.GetCycleDetected())
	t.Run("cycle_or_err_return_err", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, cyclicErrorHandler, generalErrorHandler)
		require.EqualError(t, err, simulatedDBErrorMessage)
		require.Nil(t, resp)
	})

	t.Run("cycle_or_errResolutionDepth_return_err", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, cyclicErrorHandler, depthExceededHandler)
		require.ErrorIs(t, err, ErrResolutionDepthExceeded)
		require.Nil(t, resp)
	})

	t.Run("err_or_cycle_return_err", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, generalErrorHandler, cyclicErrorHandler)
		require.EqualError(t, err, simulatedDBErrorMessage)
		require.Nil(t, resp)
	})

	t.Run("errResolutionDepth_or_cycle_return_err", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, depthExceededHandler, cyclicErrorHandler)
		require.ErrorIs(t, err, ErrResolutionDepthExceeded)
		require.Nil(t, resp)
	})
	t.Run("cycle_or_cycle_return_false", func(t *testing.T) {
		require.NotNil(t, resp)
		require.True(t, resp.GetCycleDetected())
	t.Run("false_or_cycle_or_err", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, falseHandler, cyclicErrorHandler, generalErrorHandler)
		require.EqualError(t, err, simulatedDBErrorMessage)
		require.Nil(t, resp)
	})
	t.Run("err_or_err_return_err", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, falseHandler, generalErrorHandler, generalErrorHandler)
		require.ErrorContains(t, err, simulatedDBErrorMessage)
		require.Nil(t, resp)
	t.Run("errResolutionDepth_or_errResolutionDepth_return_errResolutionDepth", func(t *testing.T) {
		resp, err := union(ctx, concurrencyLimit, falseHandler, depthExceededHandler, depthExceededHandler)
		require.ErrorIs(t, err, ErrResolutionDepthExceeded)
		require.Nil(t, resp)
	})

	t.Run("should_aggregate_DatastoreQueryCount_of_non_error_handlers", func(t *testing.T) {
			return &ResolveCheckResponse{}, nil
		require.Nil(t, resp)
		require.Nil(t, resp)

	t.Run("should_return_true_with_slow_falsey_handler", func(t *testing.T) {
		ctx, cancel := context.WithTimeout(ctx, 10*time.Millisecond)
		t.Cleanup(cancel)

		falseSlowHandler := func(context.Context) (*ResolveCheckResponse, error) {
			time.Sleep(25 * time.Millisecond)
			return &ResolveCheckResponse{
				Allowed: false,
			}, nil
		}

		resp, err := union(ctx, concurrencyLimit, trueHandler, falseSlowHandler)
		require.NoError(t, err)
		require.True(t, resp.GetAllowed())
	})

	t.Run("return_error_if_context_cancelled_before_resolution", func(t *testing.T) {
		ctx, cancel := context.WithCancel(context.Background())
		t.Cleanup(cancel)

		var wg sync.WaitGroup

		wg.Add(1)
		go func() {
			defer wg.Done()
			time.Sleep(10 * time.Millisecond)
			cancel()
		}()

		slowTrueHandler := func(context.Context) (*ResolveCheckResponse, error) {
			time.Sleep(50 * time.Millisecond)
			return &ResolveCheckResponse{
				Allowed: true,
			}, nil
		}

		resp, err := union(ctx, concurrencyLimit, slowTrueHandler)
		require.ErrorIs(t, err, context.Canceled)
		require.Nil(t, resp)

		wg.Wait() // just to make sure to avoid test leaks
	})

	t.Run("return_allowed:true_if_truthy_handler_evaluated_before_context_cancelled", func(t *testing.T) {
		ctx, cancel := context.WithCancel(context.Background())
		t.Cleanup(cancel)

		var wg sync.WaitGroup

		wg.Add(1)
		go func() {
			defer wg.Done()
			time.Sleep(10 * time.Millisecond)
			cancel()
		}()

		resp, err := intersection(ctx, concurrencyLimit, trueHandler)
		require.NoError(t, err)
		require.True(t, resp.GetAllowed())

		wg.Wait() // just to make sure to avoid test leaks
	})
}

func TestCloneResolveCheckResponse(t *testing.T) {
	resp1 := &ResolveCheckResponse{
		Allowed: true,
		ResolutionMetadata: &ResolveCheckResponseMetadata{
			DatastoreQueryCount: 1,
			CycleDetected:       false,
		},
	}
	clonedResp1 := CloneResolveCheckResponse(resp1)

	require.Equal(t, resp1, clonedResp1)
	require.NotSame(t, resp1, clonedResp1)

	// mutate the clone and ensure the original reference is
	// unchanged
	clonedResp1.Allowed = false
	clonedResp1.ResolutionMetadata.DatastoreQueryCount = 2
	clonedResp1.ResolutionMetadata.CycleDetected = true
	require.True(t, resp1.GetAllowed())
	require.Equal(t, uint32(1), resp1.GetResolutionMetadata().DatastoreQueryCount)
	require.False(t, resp1.GetResolutionMetadata().CycleDetected)

	resp2 := &ResolveCheckResponse{
		Allowed: true,
	}
	clonedResp2 := CloneResolveCheckResponse(resp2)

	require.NotSame(t, resp2, clonedResp2)
	require.Equal(t, resp2.GetAllowed(), clonedResp2.GetAllowed())
	require.NotNil(t, clonedResp2.ResolutionMetadata)
	require.Equal(t, uint32(0), clonedResp2.GetResolutionMetadata().DatastoreQueryCount)
	require.False(t, clonedResp2.GetResolutionMetadata().CycleDetected)
		return &ResolveCheckResponse{
			Allowed: false,
			ResolutionMetadata: &ResolveCheckResponseMetadata{
				CycleDetected: true,
			},
		}, nil
		require.NoError(t, err)
		require.NotNil(t, resp)
		require.True(t, resp.GetCycleDetected())
		require.NotNil(t, resp.ResolutionMetadata)
	require.NotNil(t, resp)
	require.False(t, resp.GetAllowed())

	// Indicates if the ResolveCheck subproblem that was evaluated involved
	// a cycle in the evaluation.
	CycleDetected bool
						if errors.Is(err, graph.ErrResolutionDepthExceeded) {
				if errors.Is(err, graph.ErrResolutionDepthExceeded) {
		if errors.Is(err, graph.ErrResolutionDepthExceeded) {
	wg.Add(3)
	var resp3 *openfgav1.CheckResponse
	var err3 error
	go func() {
		defer wg.Done()

		resp3, err3 = s.Check(context.Background(), &openfgav1.CheckRequest{
			StoreId:              storeID,
			AuthorizationModelId: modelID,
			TupleKey:             tuple.NewCheckRequestTupleKey("document:1", "viewer", "user:andres"),
		})
	}()

	require.NotNil(t, resp1)
	require.NotNil(t, resp2)

	require.NoError(t, err3)
	require.NotNil(t, resp3)
	require.True(t, resp3.GetAllowed())

	require.NotNil(t, resp)