sets.go

Documentation: github.com/GoogleCloudPlatform/k8s-config-connector/pkg/test/resourcefixture

     1  // Copyright 2022 Google LLC
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //      http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package resourcefixture
    16  
    17  import (
    18  	"fmt"
    19  	"testing"
    20  
    21  	"github.com/GoogleCloudPlatform/k8s-config-connector/pkg/apis/core/v1alpha1"
    22  	iamapi "github.com/GoogleCloudPlatform/k8s-config-connector/pkg/apis/iam/v1beta1"
    23  	dclmetadata "github.com/GoogleCloudPlatform/k8s-config-connector/pkg/dcl/metadata"
    24  	"github.com/GoogleCloudPlatform/k8s-config-connector/pkg/k8s"
    25  	"github.com/GoogleCloudPlatform/k8s-config-connector/pkg/servicemapping/servicemappingloader"
    26  	"github.com/GoogleCloudPlatform/k8s-config-connector/pkg/test"
    27  	testservicemapping "github.com/GoogleCloudPlatform/k8s-config-connector/pkg/test/servicemapping"
    28  	testservicemappingloader "github.com/GoogleCloudPlatform/k8s-config-connector/pkg/test/servicemappingloader"
    29  	testyaml "github.com/GoogleCloudPlatform/k8s-config-connector/pkg/test/yaml"
    30  
    31  	"k8s.io/apimachinery/pkg/apis/meta/v1/unstructured"
    32  )
    33  
    34  // GetFilteredSetCover is an implementation of https://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm:
    35  // returns a minimal set cover from the resource fixtures that match the given filters.
    36  //
    37  // The set cover is determined by resource config, that is to say, for every resource config there is at least one
    38  // resource returned in the set cover. The result of this function is useful when you wish to run a test for every
    39  // resource type that is supported, but for performance and quota reasons, not across every fixture. For example,
    40  // when you want to test every resource but don't want to test a given resource more than once. For example, the
    41  // basic/pubsubsubscription fixture covers both the PubSubTopic and PubSubSubscription resources. There is no reason
    42  // to also run a test on the basic/pubsubtopic fixture if covering each unique resource is your goal.
    43  func GetFilteredSetCover(t *testing.T, lightFilterFunc LightFilter, heavyFilterFunc HeavyFilter) []ResourceFixture {
    44  	fixtures := LoadWithFilter(t, lightFilterFunc, heavyFilterFunc)
    45  	smLoader := testservicemappingloader.New(t)
    46  	serviceMetadataLoader := dclmetadata.New()
    47  	fixtureRCIds := buildResourceFixtureRCIdGraph(t, smLoader, serviceMetadataLoader, fixtures)
    48  	minFixtureSet := findSetCover(fixtureRCIds)
    49  	return fixtureRCIdsToFixtures(minFixtureSet)
    50  }
    51  
    52  func GetBasicTypeSetCover(t *testing.T) []ResourceFixture {
    53  	lightFilter := func(name string, testType TestType) bool {
    54  		return testType == Basic
    55  	}
    56  	heavyFilter := func(fixture ResourceFixture) bool {
    57  		// Skip v1alpha1 CRDs when testing set cover as they may not yet be
    58  		// correctly supported.
    59  		return fixture.GVK.Version == k8s.KCCAPIVersion
    60  	}
    61  	return GetFilteredSetCover(t, lightFilter, heavyFilter)
    62  }
    63  
    64  // returns all the resource config ids in use by the resources defined for a given fixture
    65  func getResourceConfigIds(t *testing.T, smLoader *servicemappingloader.ServiceMappingLoader, serviceMetadataLoader dclmetadata.ServiceMetadataLoader, fixture ResourceFixture) map[string]bool {
    66  	resourceConfigIds := make(map[string]bool)
    67  	addResourceConfig(t, smLoader, serviceMetadataLoader, fixture.Create, resourceConfigIds)
    68  	if fixture.Dependencies != nil {
    69  		dependencyYamls := testyaml.SplitYAML(t, fixture.Dependencies)
    70  		for _, d := range dependencyYamls {
    71  			addResourceConfig(t, smLoader, serviceMetadataLoader, d, resourceConfigIds)
    72  		}
    73  	}
    74  	return resourceConfigIds
    75  }
    76  
    77  func addResourceConfig(t *testing.T, smLoader *servicemappingloader.ServiceMappingLoader, serviceMetadataLoader dclmetadata.ServiceMetadataLoader, yamlBytes []byte, resourceConfigIds map[string]bool) {
    78  	u := test.ToUnstruct(t, yamlBytes)
    79  	if !ShouldHaveResourceConfig(u, serviceMetadataLoader) {
    80  		return
    81  	}
    82  	rc := testservicemapping.GetResourceConfig(t, smLoader, u)
    83  	resourceConfigIds[GetUniqueResourceConfigId(*rc)] = true
    84  }
    85  
    86  func ShouldHaveResourceConfig(u *unstructured.Unstructured, serviceMetadataLoader dclmetadata.ServiceMetadataLoader) bool {
    87  	return k8s.IsManagedByKCC(u.GroupVersionKind()) &&
    88  		!iamapi.IsHandwrittenIAM(u.GroupVersionKind()) &&
    89  		!dclmetadata.IsDCLBasedResourceKind(u.GroupVersionKind(), serviceMetadataLoader)
    90  }
    91  
    92  // returns an id that is unique for each resource config
    93  func GetUniqueResourceConfigId(rc v1alpha1.ResourceConfig) string {
    94  	if rc.Locationality != "" {
    95  		return fmt.Sprintf("%v:%v", rc.Kind, rc.Locationality)
    96  	}
    97  	if rc.Name == "google_compute_instance" || rc.Name == "google_compute_instance_from_template" {
    98  		return fmt.Sprintf("%v:%v", rc.Kind, rc.Name)
    99  	}
   100  	return rc.Kind
   101  }
   102  
   103  // this struct is used to construct a graph where the nodes are ResourceFixtures and the edges are resource config IDs
   104  type fixtureRCId struct {
   105  	Fixture ResourceFixture
   106  	RCIds   map[string]bool
   107  }
   108  
   109  func buildResourceFixtureRCIdGraph(t *testing.T, smLoader *servicemappingloader.ServiceMappingLoader, serviceMetadataLoader dclmetadata.ServiceMetadataLoader, fixtures []ResourceFixture) []fixtureRCId {
   110  	fixtureRCIds := make([]fixtureRCId, 0)
   111  	for _, f := range fixtures {
   112  		fRCId := fixtureRCId{
   113  			Fixture: f,
   114  			RCIds:   make(map[string]bool),
   115  		}
   116  		fixtureRCIds = append(fixtureRCIds, fRCId)
   117  		resourceConfigIds := getResourceConfigIds(t, smLoader, serviceMetadataLoader, f)
   118  		for k := range resourceConfigIds {
   119  			fRCId.RCIds[k] = true
   120  		}
   121  	}
   122  	return fixtureRCIds
   123  }
   124  
   125  func findSetCover(fixtureRCIds []fixtureRCId) []fixtureRCId {
   126  	minFixtureSet := make([]fixtureRCId, 0)
   127  	rcIdToCovered := make(map[string]bool)
   128  	for _, f := range fixtureRCIds {
   129  		for rcId := range f.RCIds {
   130  			rcIdToCovered[rcId] = false
   131  		}
   132  	}
   133  	coverCount := 0
   134  	for coverCount < len(rcIdToCovered) {
   135  		// find set with maximum number uncovered
   136  		var maxUncoverFixture fixtureRCId
   137  		maxUncoverFixtureNewCoverCount := 0
   138  		for _, fk := range fixtureRCIds {
   139  			uncoverCount := getUncoveredCount(fk, rcIdToCovered)
   140  			if uncoverCount > maxUncoverFixtureNewCoverCount {
   141  				maxUncoverFixtureNewCoverCount = uncoverCount
   142  				maxUncoverFixture = fk
   143  			}
   144  		}
   145  		for rcId := range maxUncoverFixture.RCIds {
   146  			rcIdToCovered[rcId] = true
   147  		}
   148  		coverCount += maxUncoverFixtureNewCoverCount
   149  		minFixtureSet = append(minFixtureSet, maxUncoverFixture)
   150  	}
   151  	return minFixtureSet
   152  }
   153  
   154  func getUncoveredCount(f fixtureRCId, rcIdToCovered map[string]bool) int {
   155  	count := 0
   156  	for r := range f.RCIds {
   157  		covered, ok := rcIdToCovered[r]
   158  		if !ok {
   159  			panic(fmt.Sprintf("expected resource config id '%v' to be in the map", r))
   160  		}
   161  		if !covered {
   162  			count += 1
   163  		}
   164  	}
   165  	return count
   166  }
   167  
   168  func fixtureRCIdsToFixtures(fixtureRCIds []fixtureRCId) []ResourceFixture {
   169  	resourceFixtures := make([]ResourceFixture, 0, len(fixtureRCIds))
   170  	for _, f := range fixtureRCIds {
   171  		resourceFixtures = append(resourceFixtures, f.Fixture)
   172  	}
   173  	return resourceFixtures
   174  }
   175
View as plain text