CVE-2023-35933 (Go, published 2023-06-26T20:15Z)
Description: value: OPenFGA is an open source authorization/permission engine built for developers. OpenFGA versions v1.1.0 and prior are vulnerable to a DoS attack when Check and ListObjects calls are executed against authorization models that contain circular relationship definitions. Users are affected by this vulnerability if they are using OpenFGA v1.1.0 or earlier, and if you are executing `Check` or `ListObjects` calls against a vulnerable authorization model. Users are advised to upgrade to version 1.1.1. There are no known workarounds for this vulnerability. Users that do not have circular relationships in their models are not affected.
Severity: nan (CVSS v3 base score: 7.5)
Weakness: CWE-835 \u2014 Loop with Unreachable Exit Condition ('Infinite Loop')
The product contains an iteration or loop with an exit condition that cannot be reached, i.e., an infinite loop.
Repository: https://github.com/openfga/openfga
Files changed:
cmd/validatemodels/validate_models.go
pkg/server/commands/expand.go
pkg/server/commands/write_authzmodel.go
pkg/server/server.go
pkg/server/server_test.go
pkg/server/test/connected_objects.go
pkg/server/test/expand.go
pkg/server/test/list_objects.go
pkg/server/test/server.go
pkg/server/test/write_authzmodel.go
pkg/typesystem/typesystem.go
pkg/typesystem/typesystem_test.go
Commit message: Merge pull request from GHSA-hr9r-8phq-5x8j

* fix: validate models with no entrypoints correctly

* chore: fix map clone on union case

* fix: clone visited map for base and subtract set in exclusion

* fix: tidy up godoc and resolve issues with tests

* test: drop duplicate test cases

* test: add another valid model to the WriteAuthorizationModel test cases

* fix: add more model validations on empty type name and relations

* fix: add in model validation for check, list object and expand

* chore: fix linter warnings

* chore: fix usage of NewAndValidate

---------

Co-authored-by: Adrian Tam <adrian.tam@okta.com>

Vulnerable code:
					_, err := typesystem.NewAndValidate(model)
	typesys := typesystem.New(model)
	_, err := typesystem.NewAndValidate(model)
	typesys := typesystem.New(model)
	typesys := typesystem.New(model)
	typesys := typesystem.New(model)
		ResolveNodeLimit: 25,
		ResolveNodeLimit: 25,
		ResolveNodeLimit:      25,
		ResolveNodeLimit:      25,
		ResolveNodeLimit:      25,
			ResolveNodeLimit:      25,
				test.resolveNodeLimit = defaultResolveNodeLimit
							},
						},
					},
				},
			},
			tuples: []*openfgapb.TupleKey{
				tuple.NewTupleKey("document:1", "parent", "document:2#editor"),
			},
			request: &openfgapb.ExpandRequest{
				TupleKey: tuple.NewTupleKey("document:1", "parent", ""),
			},
			expected: &openfgapb.ExpandResponse{
				Tree: &openfgapb.UsersetTree{
					Root: &openfgapb.UsersetTree_Node{
						Name: "document:1#parent",
						Value: &openfgapb.UsersetTree_Node_Leaf{
							Leaf: &openfgapb.UsersetTree_Leaf{
								Value: &openfgapb.UsersetTree_Leaf_Users{
									Users: &openfgapb.UsersetTree_Users{
										Users: []string{"document:2#editor"},
									},
								},
							},
						},
					},
				},
			},
		},
		{
			name: "1.1_TupleToUserset_involving_wildcard_is_skipped",
			model: &openfgapb.AuthorizationModel{
				Id:            ulid.Make().String(),
				SchemaVersion: typesystem.SchemaVersion1_1,
				TypeDefinitions: []*openfgapb.TypeDefinition{
					{
						Type: "user",
					},
					{
						Type: "document",
						Relations: map[string]*openfgapb.Userset{
							"parent": typesystem.This(),
							"viewer": typesystem.Union(
								typesystem.This(),
								typesystem.TupleToUserset("parent", "viewer"),
							),
						},
						Metadata: &openfgapb.Metadata{
							Relations: map[string]*openfgapb.RelationMetadata{
								"parent": {
										typesystem.WildcardRelationReference("user"),
			tuples: []*openfgapb.TupleKey{
				tuple.NewTupleKey("document:1", "parent", "user:*"),
				tuple.NewTupleKey("document:X", "viewer", "user:jon"),
			},
			request: &openfgapb.ExpandRequest{
				TupleKey: tuple.NewTupleKey("document:1", "viewer", ""),
			},
			expected: &openfgapb.ExpandResponse{
				Tree: &openfgapb.UsersetTree{
					Root: &openfgapb.UsersetTree_Node{
						Name: "document:1#viewer",
						Value: &openfgapb.UsersetTree_Node_Union{
							Union: &openfgapb.UsersetTree_Nodes{
								Nodes: []*openfgapb.UsersetTree_Node{
									{
										Name: "document:1#viewer",
										Value: &openfgapb.UsersetTree_Node_Leaf{
											Leaf: &openfgapb.UsersetTree_Leaf{
												Value: &openfgapb.UsersetTree_Leaf_Users{},
											},
										},
									},
									{
										Name: "document:1#viewer",
										Value: &openfgapb.UsersetTree_Node_Leaf{
											Leaf: &openfgapb.UsersetTree_Leaf{
												Value: &openfgapb.UsersetTree_Leaf_TupleToUserset{
													TupleToUserset: &openfgapb.UsersetTree_TupleToUserset{
														Tupleset: "document:1#parent",
													},
												},
											},
										},
									},
								},
							},
						},
					},
				},
			},
		},
		{
			name: "1.1_Tuple_involving_userset_skipped_if_it_is_referenced_in_a_TTU_rewrite",
			model: &openfgapb.AuthorizationModel{
				Id:            ulid.Make().String(),
				SchemaVersion: typesystem.SchemaVersion1_1,
				TypeDefinitions: []*openfgapb.TypeDefinition{
					{
						Type: "folder",
						Relations: map[string]*openfgapb.Userset{
							"viewer": typesystem.This(),
						},
					},
					{
						Type: "document",
						Relations: map[string]*openfgapb.Userset{
							"parent": typesystem.This(),
							"editor": typesystem.This(),
							"viewer": typesystem.TupleToUserset("parent", "viewer"),
						},
						Metadata: &openfgapb.Metadata{
							Relations: map[string]*openfgapb.RelationMetadata{
								"parent": {
									DirectlyRelatedUserTypes: []*openfgapb.RelationReference{
										typesystem.DirectRelationReference("document", "editor"),
									},
								},
							},
						},
					},
				},
			},
				TupleKey: tuple.NewTupleKey("document:1", "viewer", ""),
						Name: "document:1#viewer",
								Value: &openfgapb.UsersetTree_Leaf_TupleToUserset{
									TupleToUserset: &openfgapb.UsersetTree_TupleToUserset{
										Tupleset: "document:1#parent",
									},
								},
							},
						},
					},
				},
			},
		},
		{
			name: "1.1_Tuple_involving_userset_skipped_if_same_ComputedUserset_involved_in_TTU_rewrite",
			model: &openfgapb.AuthorizationModel{
				Id:            ulid.Make().String(),
				SchemaVersion: typesystem.SchemaVersion1_1,
				TypeDefinitions: []*openfgapb.TypeDefinition{
					{
						Type: "user",
					},
					{
						Type: "document",
						Relations: map[string]*openfgapb.Userset{
							"parent": typesystem.This(),
							"viewer": typesystem.Union(
								typesystem.This(),
								typesystem.TupleToUserset("parent", "viewer"),
							),
						},
						Metadata: &openfgapb.Metadata{
							Relations: map[string]*openfgapb.RelationMetadata{
								"viewer": {
									DirectlyRelatedUserTypes: []*openfgapb.RelationReference{
										{Type: "user"},
									},
								},
								"parent": {
									DirectlyRelatedUserTypes: []*openfgapb.RelationReference{
										typesystem.DirectRelationReference("document", "viewer"),
									},
								},
							},
						},
					},
				},
			},
			tuples: []*openfgapb.TupleKey{
				tuple.NewTupleKey("document:1", "parent", "document:2#viewer"),
				tuple.NewTupleKey("document:2", "viewer", "user:jon"),
			},
			request: &openfgapb.ExpandRequest{
				TupleKey: tuple.NewTupleKey("document:1", "viewer", ""),
			},
			expected: &openfgapb.ExpandResponse{
				Tree: &openfgapb.UsersetTree{
					Root: &openfgapb.UsersetTree_Node{
						Name: "document:1#viewer",
						Value: &openfgapb.UsersetTree_Node_Union{
							Union: &openfgapb.UsersetTree_Nodes{
								Nodes: []*openfgapb.UsersetTree_Node{
									{
										Name: "document:1#viewer",
										Value: &openfgapb.UsersetTree_Node_Leaf{
											Leaf: &openfgapb.UsersetTree_Leaf{
												Value: &openfgapb.UsersetTree_Leaf_Users{},
											},
										},
									},
									{
										Name: "document:1#viewer",
										Value: &openfgapb.UsersetTree_Node_Leaf{
											Leaf: &openfgapb.UsersetTree_Leaf{
												Value: &openfgapb.UsersetTree_Leaf_TupleToUserset{
													TupleToUserset: &openfgapb.UsersetTree_TupleToUserset{
														Tupleset: "document:1#parent",
													},
												},
											},
										},
									},
								},
							},
						},
					},
				},
			},
		},
		{
			name: "1.1_Tupleset_relation_involving_rewrite_skipped",
			model: &openfgapb.AuthorizationModel{
				Id:            ulid.Make().String(),
				SchemaVersion: typesystem.SchemaVersion1_1,
				TypeDefinitions: []*openfgapb.TypeDefinition{
					{
						Type: "user",
					},
					{
						Type: "document",
						Relations: map[string]*openfgapb.Userset{
							"parent": typesystem.ComputedUserset("editor"),
							"editor": typesystem.This(),
							"viewer": typesystem.Union(
								typesystem.This(), typesystem.TupleToUserset("parent", "viewer"),
							),
						},
						Metadata: &openfgapb.Metadata{
							Relations: map[string]*openfgapb.RelationMetadata{
								"editor": {
									DirectlyRelatedUserTypes: []*openfgapb.RelationReference{
										{Type: "document"},
									},
								},
								"viewer": {
									DirectlyRelatedUserTypes: []*openfgapb.RelationReference{
										{Type: "user"},
									},
								},
							},
						},
					},
				},
			},
			tuples: []*openfgapb.TupleKey{
				tuple.NewTupleKey("document:1", "editor", "document:2"),
				tuple.NewTupleKey("document:2", "viewer", "user:jon"),
			},
			request: &openfgapb.ExpandRequest{
				TupleKey: tuple.NewTupleKey("document:1", "viewer", ""),
			},
			expected: &openfgapb.ExpandResponse{
				Tree: &openfgapb.UsersetTree{
					Root: &openfgapb.UsersetTree_Node{
						Name: "document:1#viewer",
						Value: &openfgapb.UsersetTree_Node_Union{
							Union: &openfgapb.UsersetTree_Nodes{
								Nodes: []*openfgapb.UsersetTree_Node{
									{
										Name: "document:1#viewer",
										Value: &openfgapb.UsersetTree_Node_Leaf{
											Leaf: &openfgapb.UsersetTree_Leaf{
												Value: &openfgapb.UsersetTree_Leaf_Users{},
											},
										},
									},
									{
										Name: "document:1#viewer",
										Value: &openfgapb.UsersetTree_Node_Leaf{
											Leaf: &openfgapb.UsersetTree_Leaf{
												Value: &openfgapb.UsersetTree_Leaf_TupleToUserset{
													TupleToUserset: &openfgapb.UsersetTree_TupleToUserset{
														Tupleset: "document:1#parent",
													},
												},
											},
										},
				ResolveNodeLimit:      defaultResolveNodeLimit,
		ResolveNodeLimit: defaultResolveNodeLimit,
		ResolveNodeLimit: defaultResolveNodeLimit,
	defaultResolveNodeLimit = 25

		tds[td.GetType()] = td
		relations[td.GetType()] = tdRelations
func NewAndValidate(model *openfgapb.AuthorizationModel) (*TypeSystem, error) {
	// Validate the userset rewrites
	for _, td := range t.typeDefinitions {
		for relation, rewrite := range td.GetRelations() {
			err := t.isUsersetRewriteValid(td.GetType(), relation, rewrite)
	if schemaVersion == SchemaVersion1_1 {
		if err := t.validateRelationTypeRestrictions(); err != nil {
			return nil, err
	return t, nil
func (t *TypeSystem) validateRelationTypeRestrictions() error {
	for objectType := range t.typeDefinitions {
		relations, err := t.GetRelations(objectType)
		if err != nil {
			return err
		}
		for name, relation := range relations {
			relatedTypes := relation.GetTypeInfo().GetDirectlyRelatedUserTypes()
			assignable := t.IsDirectlyAssignable(relation)
			if assignable && len(relatedTypes) == 0 {
				return AssignableRelationError(objectType, name)
			}
			if assignable && len(relatedTypes) == 1 {
				relatedObjectType := relatedTypes[0].GetType()
				relatedRelation := relatedTypes[0].GetRelation()
				if objectType == relatedObjectType && name == relatedRelation {
					return &InvalidRelationError{ObjectType: objectType, Relation: name, Cause: ErrCycle}
				}
			}
			if !assignable && len(relatedTypes) != 0 {
				return NonAssignableRelationError(objectType, name)
			}
			for _, related := range relatedTypes {
				relatedObjectType := related.GetType()
				relatedRelation := related.GetRelation()
				if _, err := t.GetRelations(relatedObjectType); err != nil {
					return InvalidRelationTypeError(objectType, name, relatedObjectType, relatedRelation)
				}
				if related.GetRelationOrWildcard() != nil {
					// The type of the relation cannot contain a userset or wildcard if the relation is a tupleset relation.
					if ok, _ := t.IsTuplesetRelation(objectType, name); ok {
						return InvalidRelationTypeError(objectType, name, relatedObjectType, relatedRelation)
					}
					if relatedRelation != "" {
						if _, err := t.GetRelation(relatedObjectType, relatedRelation); err != nil {
							return InvalidRelationTypeError(objectType, name, relatedObjectType, relatedRelation)
						}
					}

			_, err := NewAndValidate(test.model)
			err: ErrCycle,
			_, err := NewAndValidate(test.model)
			_, err := NewAndValidate(test.model)
			_, err := NewAndValidate(test.model)

Fixed code:
					_, err := typesystem.NewAndValidate(context.Background(), model)
	typesys, err := typesystem.NewAndValidate(ctx, model)
	if err != nil {
		return nil, serverErrors.ValidationError(typesystem.ErrInvalidModel)
	}
	_, err := typesystem.NewAndValidate(ctx, model)
	typesys, err := typesystem.NewAndValidate(ctx, model)
	if err != nil {
		return nil, serverErrors.ValidationError(typesystem.ErrInvalidModel)
	}
	typesys, err := typesystem.NewAndValidate(ctx, model)
	if err != nil {
		return serverErrors.ValidationError(typesystem.ErrInvalidModel)
	}
	typesys, err := typesystem.NewAndValidate(ctx, model)
	if err != nil {
		return nil, serverErrors.ValidationError(typesystem.ErrInvalidModel)
	}
		ResolveNodeLimit: test.DefaultResolveNodeLimit,
func TestOperationsWithInvalidModel(t *testing.T) {
	ctx := context.Background()
	storeID := ulid.Make().String()
	modelID := ulid.Make().String()

	// The model is invalid
	typedefs := parser.MustParse(`
	type user

	type repo
	  relations
        define admin: [user] as self
	    define r1: [user] as self and r2 and r3
	    define r2: [user] as self and r1 and r3
	    define r3: [user] as self and r1 and r2
	`)

	tk := tuple.NewTupleKey("repo:openfga", "r1", "user:anne")
	mockController := gomock.NewController(t)
	defer mockController.Finish()

	mockDatastore := mockstorage.NewMockOpenFGADatastore(mockController)

	mockDatastore.EXPECT().
		ReadAuthorizationModel(gomock.Any(), storeID, modelID).
		AnyTimes().
		Return(&openfgapb.AuthorizationModel{
			SchemaVersion:   typesystem.SchemaVersion1_1,
			TypeDefinitions: typedefs,
		}, nil)

	// the model is error and err should return

	s := New(&Dependencies{
		Datastore: mockDatastore,
		Logger:    logger.NewNoopLogger(),
		Transport: gateway.NewNoopTransport(),
	}, &Config{
		ResolveNodeLimit: test.DefaultResolveNodeLimit,
	})

	_, err := s.Check(ctx, &openfgapb.CheckRequest{
		StoreId:              storeID,
		TupleKey:             tk,
		AuthorizationModelId: modelID,
	})
	require.Error(t, err)
	e, ok := status.FromError(err)
	require.True(t, ok)
	require.Equal(t, codes.Code(openfgapb.ErrorCode_validation_error), e.Code())

	_, err = s.ListObjects(ctx, &openfgapb.ListObjectsRequest{
		StoreId:              storeID,
		AuthorizationModelId: modelID,
		Type:                 "repo",
		Relation:             "r1",
		User:                 "user:anne",
	})
	require.Error(t, err)
	e, ok = status.FromError(err)
	require.True(t, ok)
	require.Equal(t, codes.Code(openfgapb.ErrorCode_validation_error), e.Code())

	err = s.StreamedListObjects(&openfgapb.StreamedListObjectsRequest{
		StoreId:              storeID,
		AuthorizationModelId: modelID,
		Type:                 "repo",
		Relation:             "r1",
		User:                 "user:anne",
	}, NewMockStreamServer())
	require.Error(t, err)
	e, ok = status.FromError(err)
	require.True(t, ok)
	require.Equal(t, codes.Code(openfgapb.ErrorCode_validation_error), e.Code())

	_, err = s.Expand(ctx, &openfgapb.ExpandRequest{
		StoreId:              storeID,
		AuthorizationModelId: modelID,
		TupleKey:             tk,
	})
	require.Error(t, err)
	e, ok = status.FromError(err)
	require.True(t, ok)
	require.Equal(t, codes.Code(openfgapb.ErrorCode_validation_error), e.Code())

}

		ResolveNodeLimit: test.DefaultResolveNodeLimit,
		ResolveNodeLimit:      test.DefaultResolveNodeLimit,
		ResolveNodeLimit:      test.DefaultResolveNodeLimit,
		ResolveNodeLimit:      test.DefaultResolveNodeLimit,
			ResolveNodeLimit:      test.DefaultResolveNodeLimit,
				test.resolveNodeLimit = DefaultResolveNodeLimit
					{
						Type: "user",
					},
					{
						Type: "user",
					},
								"editor": {
				TupleKey: tuple.NewTupleKey("document:1", "parent", ""),
						Name: "document:1#parent",
								Value: &openfgapb.UsersetTree_Leaf_Users{
									Users: &openfgapb.UsersetTree_Users{
										Users: []string{"document:2#editor"},
				ResolveNodeLimit:      DefaultResolveNodeLimit,
		ResolveNodeLimit: DefaultResolveNodeLimit,
		ResolveNodeLimit: DefaultResolveNodeLimit,
	DefaultResolveNodeLimit = 25
	parser "github.com/craigpastro/openfga-dsl-parser/v2"
		{
			name: "self_referencing_type_restriction_with_entrypoint",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type document
				  relations
				    define editor: [user] as self
				    define viewer: [document#viewer] as self or editor
				`),
				SchemaVersion: typesystem.SchemaVersion1_1,
			},
		},
		{
			name: "self_referencing_type_restriction_without_entrypoint_1",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user
				type document
				  relations
				    define viewer: [document#viewer] as self
				`),
				SchemaVersion: typesystem.SchemaVersion1_1,
			},
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "viewer",
				Cause:      typesystem.ErrCycle,
			}),
		},
		{
			name: "self_referencing_type_restriction_without_entrypoint_2",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user
				type document
				  relations
				    define editor: [user] as self
				    define viewer: [document#viewer] as self and editor
				`),
				SchemaVersion: typesystem.SchemaVersion1_1,
			},
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "viewer",
				Cause:      typesystem.ErrNoEntrypoints,
			}),
		},
		{
			name: "self_referencing_type_restriction_without_entrypoint_3",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user
				type document
				  relations
				    define restricted: [user] as self
				    define viewer: [document#viewer] as self but not restricted
				`),
				SchemaVersion: typesystem.SchemaVersion1_1,
			},
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "viewer",
				Cause:      typesystem.ErrCycle,
			}),
		},
		{
			name: "rewritten_relation_in_intersection_unresolvable",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type document
				  relations
				    define admin: [user] as self
				    define action1 as admin and action2 and action3
				    define action2 as admin and action1 and action3
				    define action3 as admin and action1 and action2
				`),
				SchemaVersion: typesystem.SchemaVersion1_1,
			},
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "action1",
				Cause:      typesystem.ErrNoEntrypoints,
			}),
		},
		{
			name: "direct_relationship_with_entrypoint",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type document
				  relations
				    define viewer: [user] as self
				`),
			},
		},
		{
			name: "computed_relationship_with_entrypoint",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type document
				  relations
				    define editor: [user] as self
				    define viewer as editor
				`),
			},
		},

		{
			name: "rewritten_relation_in_exclusion_unresolvable",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type document
				  relations
				    define admin: [user] as self
				    define action1 as admin but not action2
				    define action2 as admin but not action3
				    define action3 as admin but not action1
				`),
			},
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "action1",
				Cause:      typesystem.ErrNoEntrypoints,
			}),
		},
		{
			name: "no_entrypoint_3a",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type document
				  relations
				    define viewer: [document#viewer] as self and editor
				    define editor: [user] as self
				`),
			},
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "viewer",
				Cause:      typesystem.ErrNoEntrypoints,
			}),
		},

		{
			name: "no_entrypoint_3b",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type document
				  relations
				    define viewer: [document#viewer] as self but not editor
				    define editor: [user] as self
				`),
			},
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "viewer",
				Cause:      typesystem.ErrNoEntrypoints,
			}),
		},
		{
			name: "no_entrypoint_4",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type folder
				  relations
				    define parent: [document] as self
				    define viewer as editor from parent

				type document
				  relations
				    define parent: [folder] as self
				    define editor as viewer
				    define viewer as editor from parent
				`),
			},
			err: serverErrors.InvalidAuthorizationModelInput(&typesystem.InvalidRelationError{
				ObjectType: "document",
				Relation:   "editor",
				Cause:      typesystem.ErrNoEntrypoints,
			}),
		},
		{
			name: "self_referencing_type_restriction_with_entrypoint_1",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type document
				  relations
				    define restricted: [user] as self
				    define editor: [user] as self
				    define viewer: [document#viewer] as self or editor
				    define can_view as viewer but not restricted
				    define can_view_actual as can_view
				`),
			},
		},
		{
			name: "self_referencing_type_restriction_with_entrypoint_2",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user

				type document
				  relations
				    define editor: [user] as self
				    define viewer: [document#viewer] as self or editor
				`),
			},
		},
		{
			name: "relation_with_union_of_ttu_rewrites",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: parser.MustParse(`
				type user
				type org
				  relations
				    define admin: [user] as self
				    define member: [user] as self
				type group
				  relations
				    define member: [user] as self
				type feature
				  relations
				    define accessible as admin from subscriber_org or member from subscriber_group
				    define subscriber_group: [group] as self
				    define subscriber_org: [org] as self
				`),
			},
		},
		{
			name: "type_name_is_empty_string",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: []*openfgapb.TypeDefinition{
					{
						Type: "",
					},
				},
			},
			err: serverErrors.InvalidAuthorizationModelInput(
				fmt.Errorf("the type name of a type definition cannot be an empty string"),
			),
		},
		{
			name: "relation_name_is_empty_string",
			request: &openfgapb.WriteAuthorizationModelRequest{
				StoreId: storeID,
				TypeDefinitions: []*openfgapb.TypeDefinition{
					{
						Type: "user",
						Relations: map[string]*openfgapb.Userset{
							"": typesystem.This(),
						},
					},
					{
						Type: "other",
					},
				},
			},
			err: serverErrors.InvalidAuthorizationModelInput(
				fmt.Errorf("type 'user' defines a relation with an empty string for a name"),
			),
		},
	"sort"
	"go.opentelemetry.io/otel"
	"golang.org/x/exp/maps"
var tracer = otel.Tracer("openfga/pkg/typesystem")

	ErrNoEntrypoints         = errors.New("no entrypoints defined")
		typeName := td.GetType()

		tds[typeName] = td
		relations[typeName] = tdRelations
// hasEntrypoints recursively walks the rewrite definition for the given relation to determine if there is at least
// one path in the rewrite rule that could relate to at least one concrete object type. If there is no such path that
// could lead to at least one relationship with some object type, then false is returned along with an error indicating
// no entrypoints were found. If at least one relationship with a specific object type is found while walking the rewrite,
// then true is returned along with a nil error.
func hasEntrypoints(
	typedefs map[string]map[string]*openfgapb.Relation,
	typeName, relationName string,
	rewrite *openfgapb.Userset,
	visitedRelations map[string]map[string]struct{},
) (bool, error) {

	v := maps.Clone(visitedRelations)

	if val, ok := v[typeName]; ok {
		val[relationName] = struct{}{}
	} else {
		v[typeName] = map[string]struct{}{
			relationName: {},
		}
	}

	relation, ok := typedefs[typeName][relationName]
	if !ok {
		return false, fmt.Errorf("undefined type definition for '%s#%s'", typeName, relationName)
	}

	switch rw := rewrite.Userset.(type) {
	case *openfgapb.Userset_This:
		for _, assignableType := range relation.GetTypeInfo().GetDirectlyRelatedUserTypes() {
			if assignableType.GetRelationOrWildcard() == nil || assignableType.GetWildcard() != nil {
				return true, nil
			}

			assignableTypeName := assignableType.GetType()
			assignableRelationName := assignableType.GetRelation()

			assignableRelation, ok := typedefs[assignableTypeName][assignableRelationName]
			if !ok {
				return false, fmt.Errorf("undefined type definition for '%s#%s'", assignableTypeName, assignableRelationName)
			}

			if _, ok := v[assignableTypeName][assignableRelationName]; ok {
				continue
			}

			hasEntrypoint, err := hasEntrypoints(typedefs, assignableTypeName, assignableRelationName, assignableRelation.GetRewrite(), v)
			if err != nil {
				return false, err
			}

			if hasEntrypoint {
				return true, nil
			}
		}

		return false, nil
	case *openfgapb.Userset_ComputedUserset:

		computedRelationName := rw.ComputedUserset.GetRelation()
		computedRelation, ok := typedefs[typeName][computedRelationName]
		if !ok {
			return false, fmt.Errorf("undefined type definition for '%s#%s'", typeName, computedRelationName)
		}

		if _, ok := v[typeName][computedRelationName]; ok {
			return false, nil
		}

		hasEntrypoint, err := hasEntrypoints(typedefs, typeName, computedRelationName, computedRelation.GetRewrite(), v)
		if err != nil {
			return false, err
		}

		return hasEntrypoint, nil
	case *openfgapb.Userset_TupleToUserset:
		tuplesetRelationName := rw.TupleToUserset.GetTupleset().GetRelation()
		computedRelationName := rw.TupleToUserset.ComputedUserset.GetRelation()

		tuplesetRelation, ok := typedefs[typeName][tuplesetRelationName]
		if !ok {
			return false, fmt.Errorf("undefined type definition for '%s#%s'", typeName, tuplesetRelationName)
		}

		for _, assignableType := range tuplesetRelation.GetTypeInfo().GetDirectlyRelatedUserTypes() {
			assignableTypeName := assignableType.GetType()

			if assignableRelation, ok := typedefs[assignableTypeName][computedRelationName]; ok {
				if _, ok := v[assignableTypeName][computedRelationName]; ok {
					continue
				}

				hasEntrypoint, err := hasEntrypoints(typedefs, assignableTypeName, computedRelationName, assignableRelation.GetRewrite(), v)
				if err != nil {
					return false, err
				}

				if hasEntrypoint {
					return true, nil
				}
			}
		}

		return false, nil

	case *openfgapb.Userset_Union:

		for _, child := range rw.Union.Child {

			hasEntrypoints, err := hasEntrypoints(typedefs, typeName, relationName, child, maps.Clone(visitedRelations))
			if err != nil {
				return false, err
			}

			if hasEntrypoints {
				return true, nil
			}
		}

		return false, nil
	case *openfgapb.Userset_Intersection:

		for _, child := range rw.Intersection.Child {

			// all of the children must have an entrypoint
			hasEntrypoints, err := hasEntrypoints(typedefs, typeName, relationName, child, maps.Clone(visitedRelations))
			if err != nil {
				return false, err
			}

			if !hasEntrypoints {
				return false, nil
			}
		}

		return true, nil
	case *openfgapb.Userset_Difference:

		v := maps.Clone(visitedRelations)

		hasEntrypoint, err := hasEntrypoints(typedefs, typeName, relationName, rw.Difference.GetBase(), v)
		if err != nil {
			return false, err
		}

		if !hasEntrypoint {
			return false, nil
		}

		hasEntrypoint, err = hasEntrypoints(typedefs, typeName, relationName, rw.Difference.GetSubtract(), v)
		if err != nil {
			return false, err
		}

		if !hasEntrypoint {
			return false, nil
		}

		return true, nil
	}

	return false, nil
}

func NewAndValidate(ctx context.Context, model *openfgapb.AuthorizationModel) (*TypeSystem, error) {
	_, span := tracer.Start(ctx, "typesystem.NewAndValidate")
	defer span.End()

	typedefsMap := t.typeDefinitions

	typeNames := make([]string, 0, len(typedefsMap))
	for typeName := range typedefsMap {
		typeNames = append(typeNames, typeName)
	}

	// range over the type definitions in sorted order to produce a deterministic outcome
	sort.Strings(typeNames)

	for _, typeName := range typeNames {
		typedef := typedefsMap[typeName]

		relationMap := typedef.GetRelations()
		relationNames := make([]string, 0, len(relationMap))
		for relationName := range relationMap {
			relationNames = append(relationNames, relationName)
		}

		// range over the relations in sorted order to produce a deterministic outcome
		sort.Strings(relationNames)

		for _, relationName := range relationNames {

			err := t.validateRelation(typeName, relationName, relationMap)
	return t, nil
}

// validateRelation applies all of the validation rules to a relation definition in a model. A relation
// must meet all of the rewrite validation, type restriction valdiation, and entrypoint validation criteria
// for it to be valid. Otherrwise an error is returned.
func (t *TypeSystem) validateRelation(typeName, relationName string, relationMap map[string]*openfgapb.Userset) error {

	rewrite := relationMap[relationName]

	err := t.isUsersetRewriteValid(typeName, relationName, rewrite)
	if err != nil {
		return err
	}

	err = t.validateTypeRestrictions(typeName, relationName)
	if err != nil {
		return err
	}

	visitedRelations := map[string]map[string]struct{}{}

	hasEntrypoints, err := hasEntrypoints(t.relations, typeName, relationName, rewrite, visitedRelations)
	if err != nil {
		return err
	}

	if !hasEntrypoints {
		return &InvalidRelationError{
			ObjectType: typeName,
			Relation:   relationName,
			Cause:      fmt.Errorf("no entrypoints found for relation '%s#%s': %w", typeName, relationName, ErrNoEntrypoints),
	return nil

		if objectType == "" {
			return fmt.Errorf("the type name of a type definition cannot be an empty string")
		}

			if relation == "" {
				return fmt.Errorf("type '%s' defines a relation with an empty string for a name", objectType)
			}

// validateTypeRestrictions validates the type restrictions of a given relation using the following rules:
//  1. An assignable relation must have one or more type restrictions.
//  2. A non-assignable relation must not have any type restrictions.
//  3. For each type restriction referenced for an assignable relation, each of the referenced types and relations
//     must be defined in the model.
//  4. If the provided relation is a tupleset relation, then the type restriction must be on a direct object.
func (t *TypeSystem) validateTypeRestrictions(objectType string, relationName string) error {
	relation, err := t.GetRelation(objectType, relationName)
	if err != nil {
		return err
	}
	relatedTypes := relation.GetTypeInfo().GetDirectlyRelatedUserTypes()
	assignable := t.IsDirectlyAssignable(relation)
	if assignable && len(relatedTypes) == 0 {
		return AssignableRelationError(objectType, relationName)
	}
	if !assignable && len(relatedTypes) != 0 {
		return NonAssignableRelationError(objectType, relationName)
	}
	for _, related := range relatedTypes {
		relatedObjectType := related.GetType()
		relatedRelation := related.GetRelation()
		if _, err := t.GetRelations(relatedObjectType); err != nil {
			return InvalidRelationTypeError(objectType, relationName, relatedObjectType, relatedRelation)
		}
		if related.GetRelationOrWildcard() != nil {
			// The type of the relation cannot contain a userset or wildcard if the relation is a tupleset relation.
			if ok, _ := t.IsTuplesetRelation(objectType, relationName); ok {
				return InvalidRelationTypeError(objectType, relationName, relatedObjectType, relatedRelation)
			}
			if relatedRelation != "" {
				if _, err := t.GetRelation(relatedObjectType, relatedRelation); err != nil {
					return InvalidRelationTypeError(objectType, relationName, relatedObjectType, relatedRelation)
	"context"
func TestNewAndValidate(t *testing.T) {

	tests := []struct {
		name          string
		model         string
		expectedError error
	}{
		{
			name: "direct_relationship_with_entrypoint",
			model: `
			type user

			type document
			  relations
			    define viewer: [user] as self
			`,
		},
		{
			name: "computed_relationship_with_entrypoint",
			model: `
			type user

			type document
			  relations
			    define editor: [user] as self
			    define viewer as editor
			`,
		},
		{
			name: "no_entrypoint_1",
			model: `
			type user

			type document
			  relations
			    define admin: [user] as self
			    define action1 as admin and action2 and action3
			    define action2 as admin and action1 and action3
			    define action3 as admin and action1 and action2
			`,
			expectedError: ErrNoEntrypoints,
		},
		{
			name: "no_entrypoint_2",
			model: `
			type user

			type document
			  relations
				define admin: [user] as self
				define action1 as admin but not action2
				define action2 as admin but not action3
				define action3 as admin but not action1
			`,
			expectedError: ErrNoEntrypoints,
		},
		{
			name: "no_entrypoint_3a",
			model: `
			type user

			type document
			  relations
			    define viewer: [document#viewer] as self and editor
			    define editor: [user] as self
			`,
			expectedError: ErrNoEntrypoints,
		},
		{
			name: "no_entrypoint_3b",
			model: `
			type user

			type document
			  relations
			    define viewer: [document#viewer] as self but not editor
			    define editor: [user] as self
			`,
			expectedError: ErrNoEntrypoints,
		},
		{
			name: "no_entrypoint_4",
			model: `
			type user

			type folder
			  relations
			    define parent: [document] as self
			    define viewer as editor from parent

			type document
			  relations
			    define parent: [folder] as self
				define editor as viewer
			    define viewer as editor from parent
			`,
			expectedError: ErrNoEntrypoints,
		},
		{
			name: "self_referencing_type_restriction_with_entrypoint_1",
			model: `
			type user

			type document
			  relations
			    define restricted: [user] as self
			    define editor: [user] as self
			    define viewer: [document#viewer] as self or editor
			    define can_view as viewer but not restricted
			    define can_view_actual as can_view
			`,
		},
		{
			name: "self_referencing_type_restriction_with_entrypoint_2",
			model: `
			type user

			type document
			  relations
			    define editor: [user] as self
			    define viewer: [document#viewer] as self or editor
			`,
		},
	}

	for _, test := range tests {
		t.Run(test.name, func(t *testing.T) {
			_, err := NewAndValidate(context.Background(), &openfgapb.AuthorizationModel{
				SchemaVersion:   SchemaVersion1_1,
				TypeDefinitions: parser.MustParse(test.model),
			})
			require.ErrorIs(t, err, test.expectedError)
		})
	}
}

		{
			name: "self_referencing_type_restriction_with_entrypoint",
			model: &openfgapb.AuthorizationModel{
				TypeDefinitions: parser.MustParse(`
				type user

				type document
				  relations
				    define editor: [user] as self
				    define viewer: [document#viewer] as self or editor
				`),
				SchemaVersion: SchemaVersion1_1,
			},
		},
		{
			name: "intersection_may_contain_repeated_relations",
			model: &openfgapb.AuthorizationModel{
				TypeDefinitions: parser.MustParse(`
				type user
				type document
				  relations
					define editor: [user] as self
					define viewer as editor and editor
				`),
				SchemaVersion: SchemaVersion1_1,
			},
		},
		{
			name: "exclusion_may_contain_repeated_relations",
			model: &openfgapb.AuthorizationModel{
				TypeDefinitions: parser.MustParse(`
				type user
				type document
				  relations
					define editor: [user] as self
					define viewer as editor but not editor
				`),
				SchemaVersion: SchemaVersion1_1,
			},
		},
			_, err := NewAndValidate(context.Background(), test.model)
			err: ErrNoEntrypoints,
			_, err := NewAndValidate(context.Background(), test.model)
			_, err := NewAndValidate(context.Background(), test.model)
			_, err := NewAndValidate(context.Background(), test.model)