`Check` should detect and break on cycles

[ihasdapie]

Check currently will recurse indefinitely until MAX_DEPTH is reached if no access can be found for an access check. Instead, permify should track if a cycle is found, and if so, deny the check request.

Cycles are bad, and they shouldn't happen, but checking permissions when one exists should fail gracefully and not take excessive compute.

It would also be useful if these cycles can be reported (maybe just via a log) for downstream diagnostics.

Reproducible via this test under internal/engines

package engines

import (
	"context"
	"testing"

	"github.com/Permify/permify/internal/config"
	"github.com/Permify/permify/internal/factories"
	"github.com/Permify/permify/internal/invoke"
	"github.com/Permify/permify/pkg/database"
	base "github.com/Permify/permify/pkg/pb/base/v1"
	"github.com/Permify/permify/pkg/token"
	"github.com/Permify/permify/pkg/tuple"
	. "github.com/onsi/ginkgo/v2"
	. "github.com/onsi/gomega"
)

func TestCheckRec(t *testing.T) {
	RegisterFailHandler(Fail)

	schema := `

entity user {
    relation viewers @user
    relation owners @user

    action read = viewers or owner
    action readwrite = owner
    action readwriteshare = owner
    action owner = owners
}

entity document {
    relation owning_entity @user
    relation parent @document

    relation readers @user @group
    relation readwriters @user @group
    relation readwritesharers @user @group

    action read = readers or parent.read or readers.read or owning_entity.read or owner
    action owner = owning_entity
}


	`
	db, err := factories.DatabaseFactory(
		config.Database{
			Engine: "memory",
		},
	)

	Expect(err).ShouldNot(HaveOccurred())

	conf, err := newSchema(schema)
	Expect(err).ShouldNot(HaveOccurred())

	schemaWriter := factories.SchemaWriterFactory(db)
	err = schemaWriter.WriteSchema(context.Background(), conf)

	Expect(err).ShouldNot(HaveOccurred())

	type check struct {
		entity     string
		subject    string
		assertions map[string]base.CheckResult
	}

	tests := struct {
		relationships []string
		checks        []check
	}{
		relationships: []string{
			"document:0#parent@document:1",
			"document:0#owning_entity@user:1",
			"document:1#parent@document:0",
			"document:1#owning_entity@user:1",
		},
		checks: []check{
			{
				// works correctly as expected
				entity:  "document:1",
				subject: "user:1",
				assertions: map[string]base.CheckResult{
					"read": base.CheckResult_CHECK_RESULT_ALLOWED,
				},
			},
			{
				// problem: there can be an infinite loop during the no-access case
				// which only terminates when the depth is reached
				entity:  "document:0",
				subject: "user:2",
				assertions: map[string]base.CheckResult{
					"read": base.CheckResult_CHECK_RESULT_ALLOWED,
				},
			},
		},
	}

	schemaReader := factories.SchemaReaderFactory(db)
	dataReader := factories.DataReaderFactory(db)
	dataWriter := factories.DataWriterFactory(db)

	checkEngine := NewCheckEngine(schemaReader, dataReader)

	invoker := invoke.NewDirectInvoker(
		schemaReader,
		dataReader,
		checkEngine,
		nil,
		nil,
		nil,
	)

	checkEngine.SetInvoker(invoker)

	var tuples []*base.Tuple

	for _, relationship := range tests.relationships {
		t, err := tuple.Tuple(relationship)
		Expect(err).ShouldNot(HaveOccurred())
		tuples = append(tuples, t)
	}

	_, err = dataWriter.Write(context.Background(), "t1", database.NewTupleCollection(tuples...), database.NewAttributeCollection())
	Expect(err).ShouldNot(HaveOccurred())

	for _, check := range tests.checks {
		entity, err := tuple.E(check.entity)
		Expect(err).ShouldNot(HaveOccurred())

		ear, err := tuple.EAR(check.subject)
		Expect(err).ShouldNot(HaveOccurred())

		subject := &base.Subject{
			Type:     ear.GetEntity().GetType(),
			Id:       ear.GetEntity().GetId(),
			Relation: ear.GetRelation(),
		}

		for permission, res := range check.assertions {
			println("asserting permission: ", permission)

			response, err := invoker.Check(context.Background(), &base.PermissionCheckRequest{
				TenantId:   "t1",
				Entity:     entity,
				Subject:    subject,
				Permission: permission,
				Metadata: &base.PermissionCheckRequestMetadata{
					SnapToken:     token.NewNoopToken().Encode().String(),
					SchemaVersion: "",
					Depth:         100,
				},
			})
			/* println("---------------")
			fmt.Printf("err: %+v\n", err)
			fmt.Printf("response: %+v\n", response)
			println("---------------") */

			Expect(err).ShouldNot(HaveOccurred())
			Expect(res).Should(Equal(response.GetCan()))
		}
	}

}

[Charlotte1959]

Release