state_test.go

Documentation: k8s.io/kube-openapi/pkg/internal/third_party/go-json-experiment/json

     1  // Copyright 2020 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package json
     6  
     7  import (
     8  	"fmt"
     9  	"reflect"
    10  	"strings"
    11  	"testing"
    12  )
    13  
    14  func TestStateMachine(t *testing.T) {
    15  	// To test a state machine, we pass an ordered sequence of operations and
    16  	// check whether the current state is as expected.
    17  	// The operation type is a union type of various possible operations,
    18  	// which either call mutating methods on the state machine or
    19  	// call accessor methods on state machine and verify the results.
    20  	type operation any
    21  	type (
    22  		// stackLengths checks the results of stateEntry.length accessors.
    23  		stackLengths []int
    24  
    25  		// appendTokens is sequence of token kinds to append where
    26  		// none of them are expected to fail.
    27  		//
    28  		// For example: `[nft]` is equivalent to the following sequence:
    29  		//
    30  		//	pushArray()
    31  		//	appendLiteral()
    32  		//	appendString()
    33  		//	appendNumber()
    34  		//	popArray()
    35  		//
    36  		appendTokens string
    37  
    38  		// appendToken is a single token kind to append with the expected error.
    39  		appendToken struct {
    40  			kind Kind
    41  			want error
    42  		}
    43  
    44  		// needDelim checks the result of the needDelim accessor.
    45  		needDelim struct {
    46  			next Kind
    47  			want byte
    48  		}
    49  	)
    50  
    51  	// Each entry is a sequence of tokens to pass to the state machine.
    52  	tests := []struct {
    53  		label string
    54  		ops   []operation
    55  	}{{
    56  		"TopLevelValues",
    57  		[]operation{
    58  			stackLengths{0},
    59  			needDelim{'n', 0},
    60  			appendTokens(`nft`),
    61  			stackLengths{3},
    62  			needDelim{'"', 0},
    63  			appendTokens(`"0[]{}`),
    64  			stackLengths{7},
    65  		},
    66  	}, {
    67  		"ArrayValues",
    68  		[]operation{
    69  			stackLengths{0},
    70  			needDelim{'[', 0},
    71  			appendTokens(`[`),
    72  			stackLengths{1, 0},
    73  			needDelim{'n', 0},
    74  			appendTokens(`nft`),
    75  			stackLengths{1, 3},
    76  			needDelim{'"', ','},
    77  			appendTokens(`"0[]{}`),
    78  			stackLengths{1, 7},
    79  			needDelim{']', 0},
    80  			appendTokens(`]`),
    81  			stackLengths{1},
    82  		},
    83  	}, {
    84  		"ObjectValues",
    85  		[]operation{
    86  			stackLengths{0},
    87  			needDelim{'{', 0},
    88  			appendTokens(`{`),
    89  			stackLengths{1, 0},
    90  			needDelim{'"', 0},
    91  			appendTokens(`"`),
    92  			stackLengths{1, 1},
    93  			needDelim{'n', ':'},
    94  			appendTokens(`n`),
    95  			stackLengths{1, 2},
    96  			needDelim{'"', ','},
    97  			appendTokens(`"f"t`),
    98  			stackLengths{1, 6},
    99  			appendTokens(`"""0"[]"{}`),
   100  			stackLengths{1, 14},
   101  			needDelim{'}', 0},
   102  			appendTokens(`}`),
   103  			stackLengths{1},
   104  		},
   105  	}, {
   106  		"ObjectCardinality",
   107  		[]operation{
   108  			appendTokens(`{`),
   109  
   110  			// Appending any kind other than string for object name is an error.
   111  			appendToken{'n', errMissingName},
   112  			appendToken{'f', errMissingName},
   113  			appendToken{'t', errMissingName},
   114  			appendToken{'0', errMissingName},
   115  			appendToken{'{', errMissingName},
   116  			appendToken{'[', errMissingName},
   117  			appendTokens(`"`),
   118  
   119  			// Appending '}' without first appending any value is an error.
   120  			appendToken{'}', errMissingValue},
   121  			appendTokens(`"`),
   122  
   123  			appendTokens(`}`),
   124  		},
   125  	}, {
   126  		"MismatchingDelims",
   127  		[]operation{
   128  			appendToken{'}', errMismatchDelim}, // appending '}' without preceding '{'
   129  			appendTokens(`[[{`),
   130  			appendToken{']', errMismatchDelim}, // appending ']' that mismatches preceding '{'
   131  			appendTokens(`}]`),
   132  			appendToken{'}', errMismatchDelim}, // appending '}' that mismatches preceding '['
   133  			appendTokens(`]`),
   134  			appendToken{']', errMismatchDelim}, // appending ']' without preceding '['
   135  		},
   136  	}}
   137  
   138  	for _, tt := range tests {
   139  		t.Run(tt.label, func(t *testing.T) {
   140  			// Flatten appendTokens to sequence of appendToken entries.
   141  			var ops []operation
   142  			for _, op := range tt.ops {
   143  				if toks, ok := op.(appendTokens); ok {
   144  					for _, k := range []byte(toks) {
   145  						ops = append(ops, appendToken{Kind(k), nil})
   146  					}
   147  					continue
   148  				}
   149  				ops = append(ops, op)
   150  			}
   151  
   152  			// Append each token to the state machine and check the output.
   153  			var state stateMachine
   154  			state.reset()
   155  			var sequence []Kind
   156  			for _, op := range ops {
   157  				switch op := op.(type) {
   158  				case stackLengths:
   159  					var got []int
   160  					for i := 0; i < state.depth(); i++ {
   161  						e := state.index(i)
   162  						got = append(got, e.length())
   163  					}
   164  					want := []int(op)
   165  					if !reflect.DeepEqual(got, want) {
   166  						t.Fatalf("%s: stack lengths mismatch:\ngot  %v\nwant %v", sequence, got, want)
   167  					}
   168  				case appendToken:
   169  					got := state.append(op.kind)
   170  					if !reflect.DeepEqual(got, op.want) {
   171  						t.Fatalf("%s: append('%c') = %v, want %v", sequence, op.kind, got, op.want)
   172  					}
   173  					if got == nil {
   174  						sequence = append(sequence, op.kind)
   175  					}
   176  				case needDelim:
   177  					if got := state.needDelim(op.next); got != op.want {
   178  						t.Fatalf("%s: needDelim('%c') = '%c', want '%c'", sequence, op.next, got, op.want)
   179  					}
   180  				default:
   181  					panic(fmt.Sprintf("unknown operation: %T", op))
   182  				}
   183  			}
   184  		})
   185  	}
   186  }
   187  
   188  // append is a thin wrapper over the other append, pop, or push methods
   189  // based on the token kind.
   190  func (s *stateMachine) append(k Kind) error {
   191  	switch k {
   192  	case 'n', 'f', 't':
   193  		return s.appendLiteral()
   194  	case '"':
   195  		return s.appendString()
   196  	case '0':
   197  		return s.appendNumber()
   198  	case '{':
   199  		return s.pushObject()
   200  	case '}':
   201  		return s.popObject()
   202  	case '[':
   203  		return s.pushArray()
   204  	case ']':
   205  		return s.popArray()
   206  	default:
   207  		panic(fmt.Sprintf("invalid token kind: '%c'", k))
   208  	}
   209  }
   210  
   211  func TestObjectNamespace(t *testing.T) {
   212  	type operation any
   213  	type (
   214  		insert struct {
   215  			name         string
   216  			wantInserted bool
   217  		}
   218  		removeLast struct{}
   219  	)
   220  
   221  	// Sequence of insert operations to perform (order matters).
   222  	ops := []operation{
   223  		insert{`""`, true},
   224  		removeLast{},
   225  		insert{`""`, true},
   226  		insert{`""`, false},
   227  
   228  		// Test insertion of the same name with different formatting.
   229  		insert{`"alpha"`, true},
   230  		insert{`"ALPHA"`, true}, // case-sensitive matching
   231  		insert{`"alpha"`, false},
   232  		insert{`"\u0061\u006c\u0070\u0068\u0061"`, false}, // unescapes to "alpha"
   233  		removeLast{},                                      // removes "ALPHA"
   234  		insert{`"alpha"`, false},
   235  		removeLast{}, // removes "alpha"
   236  		insert{`"alpha"`, true},
   237  		removeLast{},
   238  
   239  		// Bulk insert simple names.
   240  		insert{`"alpha"`, true},
   241  		insert{`"bravo"`, true},
   242  		insert{`"charlie"`, true},
   243  		insert{`"delta"`, true},
   244  		insert{`"echo"`, true},
   245  		insert{`"foxtrot"`, true},
   246  		insert{`"golf"`, true},
   247  		insert{`"hotel"`, true},
   248  		insert{`"india"`, true},
   249  		insert{`"juliet"`, true},
   250  		insert{`"kilo"`, true},
   251  		insert{`"lima"`, true},
   252  		insert{`"mike"`, true},
   253  		insert{`"november"`, true},
   254  		insert{`"oscar"`, true},
   255  		insert{`"papa"`, true},
   256  		insert{`"quebec"`, true},
   257  		insert{`"romeo"`, true},
   258  		insert{`"sierra"`, true},
   259  		insert{`"tango"`, true},
   260  		insert{`"uniform"`, true},
   261  		insert{`"victor"`, true},
   262  		insert{`"whiskey"`, true},
   263  		insert{`"xray"`, true},
   264  		insert{`"yankee"`, true},
   265  		insert{`"zulu"`, true},
   266  
   267  		// Test insertion of invalid UTF-8.
   268  		insert{`"` + "\ufffd" + `"`, true},
   269  		insert{`"` + "\ufffd" + `"`, false},
   270  		insert{`"\ufffd"`, false},         // unescapes to Unicode replacement character
   271  		insert{`"\uFFFD"`, false},         // unescapes to Unicode replacement character
   272  		insert{`"` + "\xff" + `"`, false}, // mangles as Unicode replacement character
   273  		removeLast{},
   274  		insert{`"` + "\ufffd" + `"`, true},
   275  
   276  		// Test insertion of unicode characters.
   277  		insert{`"☺☻☹"`, true},
   278  		insert{`"☺☻☹"`, false},
   279  		removeLast{},
   280  		insert{`"☺☻☹"`, true},
   281  	}
   282  
   283  	// Execute the sequence of operations twice:
   284  	// 1) on a fresh namespace and 2) on a namespace that has been reset.
   285  	var ns objectNamespace
   286  	wantNames := []string{}
   287  	for _, reset := range []bool{false, true} {
   288  		if reset {
   289  			ns.reset()
   290  			wantNames = nil
   291  		}
   292  
   293  		// Execute the operations and ensure the state is consistent.
   294  		for i, op := range ops {
   295  			switch op := op.(type) {
   296  			case insert:
   297  				gotInserted := ns.insertQuoted([]byte(op.name), false)
   298  				if gotInserted != op.wantInserted {
   299  					t.Fatalf("%d: objectNamespace{%v}.insert(%v) = %v, want %v", i, strings.Join(wantNames, " "), op.name, gotInserted, op.wantInserted)
   300  				}
   301  				if gotInserted {
   302  					b, _ := unescapeString(nil, []byte(op.name))
   303  					wantNames = append(wantNames, string(b))
   304  				}
   305  			case removeLast:
   306  				ns.removeLast()
   307  				wantNames = wantNames[:len(wantNames)-1]
   308  			default:
   309  				panic(fmt.Sprintf("unknown operation: %T", op))
   310  			}
   311  
   312  			// Check that the namespace is consistent.
   313  			gotNames := []string{}
   314  			for i := 0; i < ns.length(); i++ {
   315  				gotNames = append(gotNames, string(ns.getUnquoted(i)))
   316  			}
   317  			if !reflect.DeepEqual(gotNames, wantNames) {
   318  				t.Fatalf("%d: objectNamespace = {%v}, want {%v}", i, strings.Join(gotNames, " "), strings.Join(wantNames, " "))
   319  			}
   320  		}
   321  
   322  		// Verify that we have not switched to using a Go map.
   323  		if ns.mapNames != nil {
   324  			t.Errorf("objectNamespace.mapNames = non-nil, want nil")
   325  		}
   326  
   327  		// Insert a large number of names.
   328  		for i := 0; i < 64; i++ {
   329  			ns.insertUnquoted([]byte(fmt.Sprintf(`name%d`, i)))
   330  		}
   331  
   332  		// Verify that we did switch to using a Go map.
   333  		if ns.mapNames == nil {
   334  			t.Errorf("objectNamespace.mapNames = nil, want non-nil")
   335  		}
   336  	}
   337  }
   338  
   339  func TestUintSet(t *testing.T) {
   340  	type operation any // has | insert
   341  	type has struct {
   342  		in   uint
   343  		want bool
   344  	}
   345  	type insert struct {
   346  		in   uint
   347  		want bool
   348  	}
   349  
   350  	// Sequence of operations to perform (order matters).
   351  	ops := []operation{
   352  		has{0, false},
   353  		has{63, false},
   354  		has{64, false},
   355  		has{1234, false},
   356  		insert{3, true},
   357  		has{2, false},
   358  		has{3, true},
   359  		has{4, false},
   360  		has{63, false},
   361  		insert{3, false},
   362  		insert{63, true},
   363  		has{63, true},
   364  		insert{64, true},
   365  		insert{64, false},
   366  		has{64, true},
   367  		insert{3264, true},
   368  		has{3264, true},
   369  		insert{3, false},
   370  		has{3, true},
   371  	}
   372  
   373  	var us uintSet
   374  	for i, op := range ops {
   375  		switch op := op.(type) {
   376  		case has:
   377  			if got := us.has(op.in); got != op.want {
   378  				t.Fatalf("%d: uintSet.has(%v) = %v, want %v", i, op.in, got, op.want)
   379  			}
   380  		case insert:
   381  			if got := us.insert(op.in); got != op.want {
   382  				t.Fatalf("%d: uintSet.insert(%v) = %v, want %v", i, op.in, got, op.want)
   383  			}
   384  		default:
   385  			panic(fmt.Sprintf("unknown operation: %T", op))
   386  		}
   387  	}
   388  }
   389
View as plain text