data_model_dependencies.go

Documentation: github.com/launchdarkly/go-server-sdk/v6/internal/datasource

     1  package datasource
     2  
     3  import (
     4  	"sort"
     5  
     6  	"github.com/launchdarkly/go-sdk-common/v3/ldvalue"
     7  	"github.com/launchdarkly/go-server-sdk-evaluation/v2/ldmodel"
     8  	"github.com/launchdarkly/go-server-sdk/v6/internal/datakinds"
     9  	"github.com/launchdarkly/go-server-sdk/v6/subsystems/ldstoreimpl"
    10  	st "github.com/launchdarkly/go-server-sdk/v6/subsystems/ldstoretypes"
    11  )
    12  
    13  type kindAndKey struct {
    14  	kind st.DataKind
    15  	key  string
    16  }
    17  
    18  // This set type is implemented as a map, but the values do not matter, just the keys.
    19  type kindAndKeySet map[kindAndKey]bool
    20  
    21  func (s kindAndKeySet) add(value kindAndKey) {
    22  	s[value] = true
    23  }
    24  
    25  func (s kindAndKeySet) contains(value kindAndKey) bool {
    26  	_, ok := s[value]
    27  	return ok
    28  }
    29  
    30  func computeDependenciesFrom(kind st.DataKind, fromItem st.ItemDescriptor) kindAndKeySet {
    31  	// For any given flag or segment, find all the flags/segments that it directly references.
    32  	// Transitive references are handled by recursive logic at a higher level.
    33  	var ret kindAndKeySet
    34  	checkClauses := func(clauses []ldmodel.Clause) {
    35  		for _, c := range clauses {
    36  			if c.Op == ldmodel.OperatorSegmentMatch {
    37  				for _, v := range c.Values {
    38  					if v.Type() == ldvalue.StringType {
    39  						if ret == nil {
    40  							ret = make(kindAndKeySet)
    41  						}
    42  						ret.add(kindAndKey{datakinds.Segments, v.StringValue()})
    43  					}
    44  				}
    45  			}
    46  		}
    47  	}
    48  	switch kind {
    49  	case ldstoreimpl.Features():
    50  		if flag, ok := fromItem.Item.(*ldmodel.FeatureFlag); ok {
    51  			if len(flag.Prerequisites) > 0 {
    52  				ret = make(kindAndKeySet, len(flag.Prerequisites))
    53  				for _, p := range flag.Prerequisites {
    54  					ret.add(kindAndKey{ldstoreimpl.Features(), p.Key})
    55  				}
    56  			}
    57  			for _, r := range flag.Rules {
    58  				checkClauses(r.Clauses)
    59  			}
    60  			return ret
    61  		}
    62  
    63  	case ldstoreimpl.Segments():
    64  		if segment, ok := fromItem.Item.(*ldmodel.Segment); ok {
    65  			for _, r := range segment.Rules {
    66  				checkClauses(r.Clauses)
    67  			}
    68  		}
    69  	}
    70  	return ret
    71  }
    72  
    73  func sortCollectionsForDataStoreInit(allData []st.Collection) []st.Collection {
    74  	colls := make([]st.Collection, 0, len(allData))
    75  	for _, coll := range allData {
    76  		if doesDataKindSupportDependencies(coll.Kind) {
    77  			itemsOut := make([]st.KeyedItemDescriptor, 0, len(coll.Items))
    78  			addItemsInDependencyOrder(coll.Kind, coll.Items, &itemsOut)
    79  			colls = append(colls, st.Collection{Kind: coll.Kind, Items: itemsOut})
    80  		} else {
    81  			colls = append(colls, coll)
    82  		}
    83  	}
    84  	sort.Slice(colls, func(i, j int) bool {
    85  		return dataKindPriority(colls[i].Kind) < dataKindPriority(colls[j].Kind)
    86  	})
    87  	return colls
    88  }
    89  
    90  func doesDataKindSupportDependencies(kind st.DataKind) bool {
    91  	return kind == datakinds.Features //nolint:megacheck
    92  }
    93  
    94  func addItemsInDependencyOrder(
    95  	kind st.DataKind,
    96  	itemsIn []st.KeyedItemDescriptor,
    97  	out *[]st.KeyedItemDescriptor,
    98  ) {
    99  	remainingItems := make(map[string]st.ItemDescriptor, len(itemsIn))
   100  	for _, item := range itemsIn {
   101  		remainingItems[item.Key] = item.Item
   102  	}
   103  	for len(remainingItems) > 0 {
   104  		// pick a random item that hasn't been visited yet
   105  		for firstKey := range remainingItems {
   106  			addWithDependenciesFirst(kind, firstKey, remainingItems, out)
   107  			break
   108  		}
   109  	}
   110  }
   111  
   112  func addWithDependenciesFirst(
   113  	kind st.DataKind,
   114  	startingKey string,
   115  	remainingItems map[string]st.ItemDescriptor,
   116  	out *[]st.KeyedItemDescriptor,
   117  ) {
   118  	startItem := remainingItems[startingKey]
   119  	delete(remainingItems, startingKey) // we won't need to visit this item again
   120  	for dep := range computeDependenciesFrom(kind, startItem) {
   121  		if dep.kind == kind {
   122  			if _, ok := remainingItems[dep.key]; ok {
   123  				addWithDependenciesFirst(kind, dep.key, remainingItems, out)
   124  			}
   125  		}
   126  	}
   127  	*out = append(*out, st.KeyedItemDescriptor{Key: startingKey, Item: startItem})
   128  }
   129  
   130  // Logic for ensuring that segments are processed before features; if we get any other data types that
   131  // haven't been accounted for here, they'll come after those two in an arbitrary order.
   132  func dataKindPriority(kind st.DataKind) int {
   133  	switch kind.GetName() {
   134  	case "segments":
   135  		return 0
   136  	case "features":
   137  		return 1
   138  	default:
   139  		return len(kind.GetName()) + 2
   140  	}
   141  }
   142  
   143  // Maintains a bidirectional dependency graph that can be updated whenever an item has changed.
   144  type dependencyTracker struct {
   145  	dependenciesFrom map[kindAndKey]kindAndKeySet
   146  	dependenciesTo   map[kindAndKey]kindAndKeySet
   147  }
   148  
   149  func newDependencyTracker() *dependencyTracker {
   150  	return &dependencyTracker{make(map[kindAndKey]kindAndKeySet), make(map[kindAndKey]kindAndKeySet)}
   151  }
   152  
   153  // Updates the dependency graph when an item has changed.
   154  func (d *dependencyTracker) updateDependenciesFrom(
   155  	kind st.DataKind,
   156  	fromKey string,
   157  	fromItem st.ItemDescriptor,
   158  ) {
   159  	fromWhat := kindAndKey{kind, fromKey}
   160  	updatedDependencies := computeDependenciesFrom(kind, fromItem)
   161  
   162  	oldDependencySet := d.dependenciesFrom[fromWhat]
   163  	for oldDep := range oldDependencySet {
   164  		depsToThisOldDep := d.dependenciesTo[oldDep]
   165  		if depsToThisOldDep != nil {
   166  			delete(depsToThisOldDep, fromWhat)
   167  		}
   168  	}
   169  
   170  	d.dependenciesFrom[fromWhat] = updatedDependencies
   171  	for newDep := range updatedDependencies {
   172  		depsToThisNewDep := d.dependenciesTo[newDep]
   173  		if depsToThisNewDep == nil {
   174  			depsToThisNewDep = make(kindAndKeySet)
   175  			d.dependenciesTo[newDep] = depsToThisNewDep
   176  		}
   177  		depsToThisNewDep.add(fromWhat)
   178  	}
   179  }
   180  
   181  func (d *dependencyTracker) reset() {
   182  	d.dependenciesFrom = make(map[kindAndKey]kindAndKeySet)
   183  	d.dependenciesTo = make(map[kindAndKey]kindAndKeySet)
   184  }
   185  
   186  // Populates the given set with the union of the initial item and all items that directly or indirectly
   187  // depend on it (based on the current state of the dependency graph).
   188  func (d *dependencyTracker) addAffectedItems(itemsOut kindAndKeySet, initialModifiedItem kindAndKey) {
   189  	if !itemsOut.contains(initialModifiedItem) {
   190  		itemsOut.add(initialModifiedItem)
   191  		affectedItems := d.dependenciesTo[initialModifiedItem]
   192  		for affectedItem := range affectedItems {
   193  			d.addAffectedItems(itemsOut, affectedItem)
   194  		}
   195  	}
   196  }
   197
View as plain text