evaluator.go

Documentation: github.com/launchdarkly/go-server-sdk-evaluation/v2

     1  package evaluation
     2  
     3  import (
     4  	"github.com/launchdarkly/go-server-sdk-evaluation/v2/ldmodel"
     5  
     6  	"github.com/launchdarkly/go-sdk-common/v3/ldcontext"
     7  	"github.com/launchdarkly/go-sdk-common/v3/ldlog"
     8  	"github.com/launchdarkly/go-sdk-common/v3/ldreason"
     9  	"github.com/launchdarkly/go-sdk-common/v3/ldvalue"
    10  )
    11  
    12  // Notes on some implementation details in this file:
    13  //
    14  // - We are often passing structs by address rather than by value, even if the usual reasons for using
    15  // a pointer (allowing mutation of the value, or using nil to represent "no value") do not apply. This
    16  // is an optimization to avoid the small but nonzero overhead of copying a struct by value across many
    17  // nested function/method calls; passing a pointer instead is faster. It is safe for us to do this
    18  // as long as the pointer value is not being retained outside the scope of this call.
    19  //
    20  // - In some for loops, we are deliberately taking the address of the range variable and using a
    21  // "//nolint:gosec" directive to turn off the usual linter warning about this:
    22  //       for _, x := range someThings {
    23  //           doSomething(&x) //nolint:gosec
    24  //       }
    25  // The rationale is the same as above, and is safe as long as the same conditions apply.
    26  
    27  // Result encapsulates all information returned by Evaluator.Evaluate.
    28  type Result struct {
    29  	// Detail contains the evaluation detail fields.
    30  	Detail ldreason.EvaluationDetail
    31  
    32  	// IsExperiment is true if this evaluation result was determined by an experiment. Normally if
    33  	// this is true, then Detail.Reason will also communicate that fact, but there are some cases
    34  	// related to the older experimentation model where this field may be true even if Detail.Reason
    35  	// does not say anything special. When the SDK submits evaluation information to the event
    36  	// processor, it should set the RequireReason field in ldevents.FlagEventProperties to this value.
    37  	IsExperiment bool
    38  }
    39  
    40  type evaluator struct {
    41  	dataProvider       DataProvider
    42  	bigSegmentProvider BigSegmentProvider
    43  	errorLogger        ldlog.BaseLogger
    44  	enableSecondaryKey bool
    45  }
    46  
    47  const ( // See Evaluate() regarding the use of these constants
    48  	preallocatedPrerequisiteChainSize = 20
    49  	preallocatedSegmentChainSize      = 20
    50  )
    51  
    52  // NewEvaluator creates an Evaluator, specifying a DataProvider that it will use if it needs to
    53  // query additional feature flags or user segments during an evaluation.
    54  //
    55  // To support big segments, you must use NewEvaluatorWithOptions and EvaluatorOptionBigSegmentProvider.
    56  func NewEvaluator(dataProvider DataProvider) Evaluator {
    57  	return NewEvaluatorWithOptions(dataProvider)
    58  }
    59  
    60  // NewEvaluatorWithOptions creates an Evaluator, specifying a DataProvider that it will use if it
    61  // needs to query additional feature flags or user segments during an evaluation, and also
    62  // any number of EvaluatorOption modifiers.
    63  func NewEvaluatorWithOptions(dataProvider DataProvider, options ...EvaluatorOption) Evaluator {
    64  	e := &evaluator{
    65  		dataProvider: dataProvider,
    66  	}
    67  	for _, o := range options {
    68  		if o != nil {
    69  			o.apply(e)
    70  		}
    71  	}
    72  	return e
    73  }
    74  
    75  // Used internally to hold the parameters of an evaluation, to avoid repetitive parameter passing.
    76  // Its methods use a pointer receiver for efficiency, even though it is allocated on the stack and
    77  // its fields are never modified.
    78  type evaluationScope struct {
    79  	owner                         *evaluator
    80  	flag                          *ldmodel.FeatureFlag
    81  	context                       ldcontext.Context
    82  	prerequisiteFlagEventRecorder PrerequisiteFlagEventRecorder
    83  	// These bigSegments properties start out unset. They are computed lazily if we encounter
    84  	// big segment references during an evaluation. See evaluator_segment.go.
    85  	bigSegmentsMemberships map[string]BigSegmentMembership
    86  	bigSegmentsStatus      ldreason.BigSegmentsStatus
    87  }
    88  
    89  type evaluationStack struct {
    90  	prerequisiteFlagChain []string
    91  	segmentChain          []string
    92  }
    93  
    94  // Implementation of the Evaluator interface.
    95  func (e *evaluator) Evaluate(
    96  	flag *ldmodel.FeatureFlag,
    97  	context ldcontext.Context,
    98  	prerequisiteFlagEventRecorder PrerequisiteFlagEventRecorder,
    99  ) Result {
   100  	if context.Err() != nil {
   101  		return Result{Detail: ldreason.NewEvaluationDetailForError(ldreason.EvalErrorUserNotSpecified, ldvalue.Null())}
   102  	}
   103  
   104  	es := evaluationScope{
   105  		owner:                         e,
   106  		flag:                          flag,
   107  		context:                       context,
   108  		prerequisiteFlagEventRecorder: prerequisiteFlagEventRecorder,
   109  	}
   110  
   111  	// Preallocate some space for prerequisiteFlagChain and segmentChain on the stack. We can
   112  	// get up to that many levels of nested prerequisites or nested segments before appending
   113  	// to the slice will cause a heap allocation.
   114  	stack := evaluationStack{
   115  		prerequisiteFlagChain: make([]string, 0, preallocatedPrerequisiteChainSize),
   116  		segmentChain:          make([]string, 0, preallocatedSegmentChainSize),
   117  	}
   118  
   119  	detail, _ := es.evaluate(stack)
   120  	if es.bigSegmentsStatus != "" {
   121  		detail.Reason = ldreason.NewEvalReasonFromReasonWithBigSegmentsStatus(detail.Reason,
   122  			es.bigSegmentsStatus)
   123  	}
   124  	return Result{Detail: detail, IsExperiment: isExperiment(flag, detail.Reason)}
   125  }
   126  
   127  // Entry point for evaluating a flag which could be either the original flag or a prerequisite.
   128  // The second return value is normally true. If it is false, it means we should immediately
   129  // terminate the whole current stack of evaluations and not do any more checking or recursing.
   130  //
   131  // Note that the evaluationStack is passed by value-- unlike other structs such as the FeatureFlag
   132  // which we reference by address for the sake of efficiency (see comments at top of file). One
   133  // reason for this is described in the comments at each point where we modify one of its fields
   134  // with append(). The other is that Go's escape analysis is not quite clever enough to let the
   135  // slices that we preallocated in Evaluate() remain on the stack if we pass that struct by address.
   136  func (es *evaluationScope) evaluate(stack evaluationStack) (ldreason.EvaluationDetail, bool) {
   137  	if !es.flag.On {
   138  		return es.getOffValue(ldreason.NewEvalReasonOff()), true
   139  	}
   140  
   141  	prereqErrorReason, ok := es.checkPrerequisites(stack)
   142  	if !ok {
   143  		// Is this an actual error, like a malformed flag? Then return an error with default value.
   144  		if prereqErrorReason.GetKind() == ldreason.EvalReasonError {
   145  			return ldreason.NewEvaluationDetailForError(prereqErrorReason.GetErrorKind(), ldvalue.Null()), false
   146  		}
   147  		// No, it's presumably just "prerequisite failed", which gets the off value.
   148  		return es.getOffValue(prereqErrorReason), true
   149  	}
   150  
   151  	// Check to see if targets match
   152  	if variation := es.anyTargetMatchVariation(); variation.IsDefined() {
   153  		return es.getVariation(variation.IntValue(), ldreason.NewEvalReasonTargetMatch()), true
   154  	}
   155  
   156  	// Now walk through the rules and see if any match
   157  	for ruleIndex, rule := range es.flag.Rules {
   158  		match, err := es.ruleMatchesContext(&rule, stack) //nolint:gosec // see comments at top of file
   159  		if err != nil {
   160  			es.logEvaluationError(err)
   161  			return ldreason.NewEvaluationDetailForError(errorKindForError(err), ldvalue.Null()), false
   162  		}
   163  		if match {
   164  			reason := ldreason.NewEvalReasonRuleMatch(ruleIndex, rule.ID)
   165  			return es.getValueForVariationOrRollout(rule.VariationOrRollout, reason), true
   166  		}
   167  	}
   168  
   169  	return es.getValueForVariationOrRollout(es.flag.Fallthrough, ldreason.NewEvalReasonFallthrough()), true
   170  }
   171  
   172  // Do a nested evaluation for a prerequisite of the current scope's flag. The second return value is
   173  // normally true; it is false only in the case where we've detected a circular reference, in which
   174  // case we want the entire evaluation to fail with a MalformedFlag error.
   175  func (es *evaluationScope) evaluatePrerequisite(
   176  	prereqFlag *ldmodel.FeatureFlag,
   177  	stack evaluationStack,
   178  ) (ldreason.EvaluationDetail, bool) {
   179  	for _, p := range stack.prerequisiteFlagChain {
   180  		if prereqFlag.Key == p {
   181  			err := circularPrereqReferenceError(prereqFlag.Key)
   182  			es.logEvaluationError(err)
   183  			return ldreason.EvaluationDetail{}, false
   184  		}
   185  	}
   186  	subScope := *es
   187  	subScope.flag = prereqFlag
   188  	result, ok := subScope.evaluate(stack)
   189  	es.bigSegmentsStatus = computeUpdatedBigSegmentsStatus(es.bigSegmentsStatus, subScope.bigSegmentsStatus)
   190  	return result, ok
   191  }
   192  
   193  // Returns an empty reason if all prerequisites are OK, otherwise constructs an error reason that describes the failure
   194  func (es *evaluationScope) checkPrerequisites(stack evaluationStack) (ldreason.EvaluationReason, bool) {
   195  	if len(es.flag.Prerequisites) == 0 {
   196  		return ldreason.EvaluationReason{}, true
   197  	}
   198  
   199  	stack.prerequisiteFlagChain = append(stack.prerequisiteFlagChain, es.flag.Key)
   200  	// Note that the change to stack.prerequisiteFlagChain does not persist after returning from
   201  	// this method. That means we don't ever need to explicitly remove the last item-- but, it
   202  	// introduces a potential edge-case inefficiency with deeply nested prerequisites: if the
   203  	// original slice had a capacity of 20, and then the 20th prerequisite has 5 prerequisites of
   204  	// its own, when checkPrerequisites is called for each of those it will end up hitting the
   205  	// capacity of the slice each time and allocating a new backing array each time. The way
   206  	// around that would be to pass a *pointer* to the slice, so the backing array would be
   207  	// retained. However, doing so appears to defeat Go's escape analysis and cause heap escaping
   208  	// of the slice every time, which would be worse in more typical use cases. We do not expect
   209  	// the preallocated capacity to be reached in typical usage.
   210  
   211  	for _, prereq := range es.flag.Prerequisites {
   212  		prereqFeatureFlag := es.owner.dataProvider.GetFeatureFlag(prereq.Key)
   213  		if prereqFeatureFlag == nil {
   214  			return ldreason.NewEvalReasonPrerequisiteFailed(prereq.Key), false
   215  		}
   216  		prereqOK := true
   217  
   218  		prereqResultDetail, prereqValid := es.evaluatePrerequisite(prereqFeatureFlag, stack)
   219  		if !prereqValid {
   220  			// In this case we want to immediately exit with an error and not check any more prereqs
   221  			return ldreason.NewEvalReasonError(ldreason.EvalErrorMalformedFlag), false
   222  		}
   223  		if !prereqFeatureFlag.On || prereqResultDetail.IsDefaultValue() ||
   224  			prereqResultDetail.VariationIndex.IntValue() != prereq.Variation {
   225  			// Note that if the prerequisite flag is off, we don't consider it a match no matter what its
   226  			// off variation was. But we still need to evaluate it in order to generate an event.
   227  			prereqOK = false
   228  		}
   229  
   230  		if es.prerequisiteFlagEventRecorder != nil {
   231  			event := PrerequisiteFlagEvent{es.flag.Key, es.context, prereqFeatureFlag, Result{
   232  				Detail:       prereqResultDetail,
   233  				IsExperiment: isExperiment(prereqFeatureFlag, prereqResultDetail.Reason),
   234  			}}
   235  			es.prerequisiteFlagEventRecorder(event)
   236  		}
   237  
   238  		if !prereqOK {
   239  			return ldreason.NewEvalReasonPrerequisiteFailed(prereq.Key), false
   240  		}
   241  	}
   242  	return ldreason.EvaluationReason{}, true
   243  }
   244  
   245  func (es *evaluationScope) getVariation(index int, reason ldreason.EvaluationReason) ldreason.EvaluationDetail {
   246  	if index < 0 || index >= len(es.flag.Variations) {
   247  		err := badVariationError(index)
   248  		es.logEvaluationError(err)
   249  		return ldreason.NewEvaluationDetailForError(err.errorKind(), ldvalue.Null())
   250  	}
   251  	return ldreason.NewEvaluationDetail(es.flag.Variations[index], index, reason)
   252  }
   253  
   254  func (es *evaluationScope) getOffValue(reason ldreason.EvaluationReason) ldreason.EvaluationDetail {
   255  	if !es.flag.OffVariation.IsDefined() {
   256  		return ldreason.EvaluationDetail{Reason: reason}
   257  	}
   258  	return es.getVariation(es.flag.OffVariation.IntValue(), reason)
   259  }
   260  
   261  func (es *evaluationScope) getValueForVariationOrRollout(
   262  	vr ldmodel.VariationOrRollout,
   263  	reason ldreason.EvaluationReason,
   264  ) ldreason.EvaluationDetail {
   265  	index, inExperiment, err := es.variationOrRolloutResult(vr, es.flag.Key, es.flag.Salt)
   266  	if err != nil {
   267  		es.logEvaluationError(err)
   268  		return ldreason.NewEvaluationDetailForError(errorKindForError(err), ldvalue.Null())
   269  	}
   270  	if inExperiment {
   271  		reason = reasonToExperimentReason(reason)
   272  	}
   273  	return es.getVariation(index, reason)
   274  }
   275  
   276  func (es *evaluationScope) anyTargetMatchVariation() ldvalue.OptionalInt {
   277  	if len(es.flag.ContextTargets) == 0 {
   278  		// If ContextTargets is empty but Targets is not empty, then this is flag data that originally
   279  		// came from a non-context-aware LD endpoint or SDK. In that case, just look at Targets.
   280  		for _, t := range es.flag.Targets {
   281  			if variation := es.targetMatchVariation(&t); variation.IsDefined() { //nolint:gosec // see comments at top of file
   282  				return variation
   283  			}
   284  		}
   285  	} else {
   286  		// If ContextTargets is provided, we iterate through it-- but, for any target of the default
   287  		// kind (user), if there are no Values, we check for a corresponding target in Targets.
   288  		for _, t := range es.flag.ContextTargets {
   289  			var variation ldvalue.OptionalInt
   290  			if (t.ContextKind == "" || t.ContextKind == ldcontext.DefaultKind) && len(t.Values) == 0 {
   291  				for _, t1 := range es.flag.Targets {
   292  					if t1.Variation == t.Variation {
   293  						variation = es.targetMatchVariation(&t1) //nolint:gosec // see comments at top of file
   294  						break
   295  					}
   296  				}
   297  			} else {
   298  				variation = es.targetMatchVariation(&t) //nolint:gosec // see comments at top of file
   299  			}
   300  			if variation.IsDefined() {
   301  				return variation
   302  			}
   303  		}
   304  	}
   305  	return ldvalue.OptionalInt{}
   306  }
   307  
   308  func (es *evaluationScope) targetMatchVariation(t *ldmodel.Target) ldvalue.OptionalInt {
   309  	if context := es.context.IndividualContextByKind(t.ContextKind); context.IsDefined() {
   310  		if ldmodel.EvaluatorAccessors.TargetFindKey(t, context.Key()) {
   311  			return ldvalue.NewOptionalInt(t.Variation)
   312  		}
   313  	}
   314  	return ldvalue.OptionalInt{}
   315  }
   316  
   317  func (es *evaluationScope) ruleMatchesContext(rule *ldmodel.FlagRule, stack evaluationStack) (bool, error) {
   318  	// Note that rule is passed by reference only for efficiency; we do not modify it
   319  	for _, clause := range rule.Clauses {
   320  		match, err := es.clauseMatchesContext(&clause, stack) //nolint:gosec // see comments at top of file
   321  		if !match || err != nil {
   322  			return match, err
   323  		}
   324  	}
   325  	return true, nil
   326  }
   327  
   328  func (es *evaluationScope) variationOrRolloutResult(
   329  	r ldmodel.VariationOrRollout, key, salt string) (variationIndex int, inExperiment bool, err error) {
   330  	if r.Variation.IsDefined() {
   331  		return r.Variation.IntValue(), false, nil
   332  	}
   333  	if len(r.Rollout.Variations) == 0 {
   334  		// This is an error (malformed flag); either Variation or Rollout must be non-nil.
   335  		return -1, false, emptyRolloutError{}
   336  	}
   337  
   338  	isExperiment := r.Rollout.IsExperiment()
   339  
   340  	bucketVal, problem, err := es.computeBucketValue(isExperiment, r.Rollout.Seed, r.Rollout.ContextKind,
   341  		key, r.Rollout.BucketBy, salt)
   342  	if err != nil {
   343  		return -1, false, err
   344  	}
   345  	var sum float32
   346  
   347  	for _, bucket := range r.Rollout.Variations {
   348  		sum += float32(bucket.Weight) / 100000.0
   349  		if bucketVal < sum {
   350  			resultInExperiment := isExperiment && !bucket.Untracked &&
   351  				problem != bucketingFailureContextLacksDesiredKind
   352  			return bucket.Variation, resultInExperiment, nil
   353  		}
   354  	}
   355  
   356  	// The user's bucket value was greater than or equal to the end of the last bucket. This could happen due
   357  	// to a rounding error, or due to the fact that we are scaling to 100000 rather than 99999, or the flag
   358  	// data could contain buckets that don't actually add up to 100000. Rather than returning an error in
   359  	// this case (or changing the scaling, which would potentially change the results for *all* users), we
   360  	// will simply put the user in the last bucket.
   361  	lastBucket := r.Rollout.Variations[len(r.Rollout.Variations)-1]
   362  	return lastBucket.Variation, isExperiment && !lastBucket.Untracked, nil
   363  }
   364  
   365  func (es *evaluationScope) logEvaluationError(err error) {
   366  	if err == nil || es.owner.errorLogger == nil {
   367  		return
   368  	}
   369  	es.owner.errorLogger.Printf("Invalid flag configuration detected in flag %q: %s",
   370  		es.flag.Key,
   371  		err,
   372  	)
   373  }
   374  
   375  func getApplicableContextKeyByKind(baseContext *ldcontext.Context, kind ldcontext.Kind) (string, bool) {
   376  	if mc := baseContext.IndividualContextByKind(kind); mc.IsDefined() {
   377  		return mc.Key(), true
   378  	}
   379  	return "", false
   380  }
   381  
   382  func reasonToExperimentReason(reason ldreason.EvaluationReason) ldreason.EvaluationReason {
   383  	switch reason.GetKind() {
   384  	case ldreason.EvalReasonFallthrough:
   385  		return ldreason.NewEvalReasonFallthroughExperiment(true)
   386  	case ldreason.EvalReasonRuleMatch:
   387  		return ldreason.NewEvalReasonRuleMatchExperiment(reason.GetRuleIndex(), reason.GetRuleID(), true)
   388  	default:
   389  		return reason // COVERAGE: unreachable
   390  	}
   391  }
   392  
   393  func isExperiment(flag *ldmodel.FeatureFlag, reason ldreason.EvaluationReason) bool {
   394  	// If the reason says we're in an experiment, we are. Otherwise, apply
   395  	// the legacy rule exclusion logic.
   396  	if reason.IsInExperiment() {
   397  		return true
   398  	}
   399  
   400  	switch reason.GetKind() {
   401  	case ldreason.EvalReasonFallthrough:
   402  		return flag.TrackEventsFallthrough
   403  	case ldreason.EvalReasonRuleMatch:
   404  		i := reason.GetRuleIndex()
   405  		if i >= 0 && i < len(flag.Rules) {
   406  			return flag.Rules[i].TrackEvents
   407  		}
   408  	}
   409  	return false
   410  }
   411
View as plain text