poset_test.go

     1  // Copyright 2018 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 ssa
     6  
     7  import (
     8  	"fmt"
     9  	"testing"
    10  )
    11  
    12  const (
    13  	SetOrder             = "SetOrder"
    14  	SetOrder_Fail        = "SetOrder_Fail"
    15  	SetOrderOrEqual      = "SetOrderOrEqual"
    16  	SetOrderOrEqual_Fail = "SetOrderOrEqual_Fail"
    17  	Ordered              = "Ordered"
    18  	Ordered_Fail         = "Ordered_Fail"
    19  	OrderedOrEqual       = "OrderedOrEqual"
    20  	OrderedOrEqual_Fail  = "OrderedOrEqual_Fail"
    21  	SetEqual             = "SetEqual"
    22  	SetEqual_Fail        = "SetEqual_Fail"
    23  	Equal                = "Equal"
    24  	Equal_Fail           = "Equal_Fail"
    25  	SetNonEqual          = "SetNonEqual"
    26  	SetNonEqual_Fail     = "SetNonEqual_Fail"
    27  	NonEqual             = "NonEqual"
    28  	NonEqual_Fail        = "NonEqual_Fail"
    29  	Checkpoint           = "Checkpoint"
    30  	Undo                 = "Undo"
    31  )
    32  
    33  type posetTestOp struct {
    34  	typ  string
    35  	a, b int
    36  }
    37  
    38  func vconst(i int) int {
    39  	if i < -128 || i >= 128 {
    40  		panic("invalid const")
    41  	}
    42  	return 1000 + 128 + i
    43  }
    44  
    45  func vconst2(i int) int {
    46  	if i < -128 || i >= 128 {
    47  		panic("invalid const")
    48  	}
    49  	return 1000 + 256 + i
    50  }
    51  
    52  func testPosetOps(t *testing.T, unsigned bool, ops []posetTestOp) {
    53  	var v [1512]*Value
    54  	for i := range v {
    55  		v[i] = new(Value)
    56  		v[i].ID = ID(i)
    57  		if i >= 1000 && i < 1256 {
    58  			v[i].Op = OpConst64
    59  			v[i].AuxInt = int64(i - 1000 - 128)
    60  		}
    61  		if i >= 1256 && i < 1512 {
    62  			v[i].Op = OpConst64
    63  			v[i].AuxInt = int64(i - 1000 - 256)
    64  		}
    65  	}
    66  
    67  	po := newPoset()
    68  	po.SetUnsigned(unsigned)
    69  	for idx, op := range ops {
    70  		t.Logf("op%d%v", idx, op)
    71  		switch op.typ {
    72  		case SetOrder:
    73  			if !po.SetOrder(v[op.a], v[op.b]) {
    74  				t.Errorf("FAILED: op%d%v failed", idx, op)
    75  			}
    76  		case SetOrder_Fail:
    77  			if po.SetOrder(v[op.a], v[op.b]) {
    78  				t.Errorf("FAILED: op%d%v passed", idx, op)
    79  			}
    80  		case SetOrderOrEqual:
    81  			if !po.SetOrderOrEqual(v[op.a], v[op.b]) {
    82  				t.Errorf("FAILED: op%d%v failed", idx, op)
    83  			}
    84  		case SetOrderOrEqual_Fail:
    85  			if po.SetOrderOrEqual(v[op.a], v[op.b]) {
    86  				t.Errorf("FAILED: op%d%v passed", idx, op)
    87  			}
    88  		case Ordered:
    89  			if !po.Ordered(v[op.a], v[op.b]) {
    90  				t.Errorf("FAILED: op%d%v failed", idx, op)
    91  			}
    92  		case Ordered_Fail:
    93  			if po.Ordered(v[op.a], v[op.b]) {
    94  				t.Errorf("FAILED: op%d%v passed", idx, op)
    95  			}
    96  		case OrderedOrEqual:
    97  			if !po.OrderedOrEqual(v[op.a], v[op.b]) {
    98  				t.Errorf("FAILED: op%d%v failed", idx, op)
    99  			}
   100  		case OrderedOrEqual_Fail:
   101  			if po.OrderedOrEqual(v[op.a], v[op.b]) {
   102  				t.Errorf("FAILED: op%d%v passed", idx, op)
   103  			}
   104  		case SetEqual:
   105  			if !po.SetEqual(v[op.a], v[op.b]) {
   106  				t.Errorf("FAILED: op%d%v failed", idx, op)
   107  			}
   108  		case SetEqual_Fail:
   109  			if po.SetEqual(v[op.a], v[op.b]) {
   110  				t.Errorf("FAILED: op%d%v passed", idx, op)
   111  			}
   112  		case Equal:
   113  			if !po.Equal(v[op.a], v[op.b]) {
   114  				t.Errorf("FAILED: op%d%v failed", idx, op)
   115  			}
   116  		case Equal_Fail:
   117  			if po.Equal(v[op.a], v[op.b]) {
   118  				t.Errorf("FAILED: op%d%v passed", idx, op)
   119  			}
   120  		case SetNonEqual:
   121  			if !po.SetNonEqual(v[op.a], v[op.b]) {
   122  				t.Errorf("FAILED: op%d%v failed", idx, op)
   123  			}
   124  		case SetNonEqual_Fail:
   125  			if po.SetNonEqual(v[op.a], v[op.b]) {
   126  				t.Errorf("FAILED: op%d%v passed", idx, op)
   127  			}
   128  		case NonEqual:
   129  			if !po.NonEqual(v[op.a], v[op.b]) {
   130  				t.Errorf("FAILED: op%d%v failed", idx, op)
   131  			}
   132  		case NonEqual_Fail:
   133  			if po.NonEqual(v[op.a], v[op.b]) {
   134  				t.Errorf("FAILED: op%d%v passed", idx, op)
   135  			}
   136  		case Checkpoint:
   137  			po.Checkpoint()
   138  		case Undo:
   139  			t.Log("Undo stack", po.undo)
   140  			po.Undo()
   141  		default:
   142  			panic("unimplemented")
   143  		}
   144  
   145  		if false {
   146  			po.DotDump(fmt.Sprintf("op%d.dot", idx), fmt.Sprintf("Last op: %v", op))
   147  		}
   148  
   149  		po.CheckIntegrity()
   150  	}
   151  
   152  	// Check that the poset is completely empty
   153  	if err := po.CheckEmpty(); err != nil {
   154  		t.Error(err)
   155  	}
   156  }
   157  
   158  func TestPoset(t *testing.T) {
   159  	testPosetOps(t, false, []posetTestOp{
   160  		{Ordered_Fail, 123, 124},
   161  
   162  		// Dag #0: 100<101
   163  		{Checkpoint, 0, 0},
   164  		{SetOrder, 100, 101},
   165  		{Ordered, 100, 101},
   166  		{Ordered_Fail, 101, 100},
   167  		{SetOrder_Fail, 101, 100},
   168  		{SetOrder, 100, 101}, // repeat
   169  		{NonEqual, 100, 101},
   170  		{NonEqual, 101, 100},
   171  		{SetEqual_Fail, 100, 101},
   172  
   173  		// Dag #1: 4<=7<12
   174  		{Checkpoint, 0, 0},
   175  		{SetOrderOrEqual, 4, 7},
   176  		{OrderedOrEqual, 4, 7},
   177  		{SetOrder, 7, 12},
   178  		{Ordered, 7, 12},
   179  		{Ordered, 4, 12},
   180  		{Ordered_Fail, 12, 4},
   181  		{NonEqual, 4, 12},
   182  		{NonEqual, 12, 4},
   183  		{NonEqual_Fail, 4, 100},
   184  		{OrderedOrEqual, 4, 12},
   185  		{OrderedOrEqual_Fail, 12, 4},
   186  		{OrderedOrEqual, 4, 7},
   187  		{OrderedOrEqual_Fail, 7, 4},
   188  
   189  		// Dag #1: 1<4<=7<12
   190  		{Checkpoint, 0, 0},
   191  		{SetOrder, 1, 4},
   192  		{Ordered, 1, 4},
   193  		{Ordered, 1, 12},
   194  		{Ordered_Fail, 12, 1},
   195  
   196  		// Dag #1: 1<4<=7<12, 6<7
   197  		{Checkpoint, 0, 0},
   198  		{SetOrder, 6, 7},
   199  		{Ordered, 6, 7},
   200  		{Ordered, 6, 12},
   201  		{SetOrder_Fail, 7, 4},
   202  		{SetOrder_Fail, 7, 6},
   203  		{SetOrder_Fail, 7, 1},
   204  
   205  		// Dag #1: 1<4<=7<12, 1<6<7
   206  		{Checkpoint, 0, 0},
   207  		{Ordered_Fail, 1, 6},
   208  		{SetOrder, 1, 6},
   209  		{Ordered, 1, 6},
   210  		{SetOrder_Fail, 6, 1},
   211  
   212  		// Dag #1: 1<4<=7<12, 1<4<6<7
   213  		{Checkpoint, 0, 0},
   214  		{Ordered_Fail, 4, 6},
   215  		{Ordered_Fail, 4, 7},
   216  		{SetOrder, 4, 6},
   217  		{Ordered, 4, 6},
   218  		{OrderedOrEqual, 4, 6},
   219  		{Ordered, 4, 7},
   220  		{OrderedOrEqual, 4, 7},
   221  		{SetOrder_Fail, 6, 4},
   222  		{Ordered_Fail, 7, 6},
   223  		{Ordered_Fail, 7, 4},
   224  		{OrderedOrEqual_Fail, 7, 6},
   225  		{OrderedOrEqual_Fail, 7, 4},
   226  
   227  		// Merge: 1<4<6, 4<=7<12, 6<101
   228  		{Checkpoint, 0, 0},
   229  		{Ordered_Fail, 6, 101},
   230  		{SetOrder, 6, 101},
   231  		{Ordered, 6, 101},
   232  		{Ordered, 1, 101},
   233  
   234  		// Merge: 1<4<6, 4<=7<12, 6<100<101
   235  		{Checkpoint, 0, 0},
   236  		{Ordered_Fail, 6, 100},
   237  		{SetOrder, 6, 100},
   238  		{Ordered, 1, 100},
   239  
   240  		// Undo: 1<4<6<7<12, 6<101
   241  		{Ordered, 100, 101},
   242  		{Undo, 0, 0},
   243  		{Ordered, 100, 101},
   244  		{Ordered_Fail, 6, 100},
   245  		{Ordered, 6, 101},
   246  		{Ordered, 1, 101},
   247  
   248  		// Undo: 1<4<6<7<12, 100<101
   249  		{Undo, 0, 0},
   250  		{Ordered_Fail, 1, 100},
   251  		{Ordered_Fail, 1, 101},
   252  		{Ordered_Fail, 6, 100},
   253  		{Ordered_Fail, 6, 101},
   254  
   255  		// Merge: 1<4<6<7<12, 6<100<101
   256  		{Checkpoint, 0, 0},
   257  		{Ordered, 100, 101},
   258  		{SetOrder, 6, 100},
   259  		{Ordered, 6, 100},
   260  		{Ordered, 6, 101},
   261  		{Ordered, 1, 101},
   262  
   263  		// Undo 2 times: 1<4<7<12, 1<6<7
   264  		{Undo, 0, 0},
   265  		{Undo, 0, 0},
   266  		{Ordered, 1, 6},
   267  		{Ordered, 4, 12},
   268  		{Ordered_Fail, 4, 6},
   269  		{SetOrder_Fail, 6, 1},
   270  
   271  		// Undo 2 times: 1<4<7<12
   272  		{Undo, 0, 0},
   273  		{Undo, 0, 0},
   274  		{Ordered, 1, 12},
   275  		{Ordered, 7, 12},
   276  		{Ordered_Fail, 1, 6},
   277  		{Ordered_Fail, 6, 7},
   278  		{Ordered, 100, 101},
   279  		{Ordered_Fail, 1, 101},
   280  
   281  		// Undo: 4<7<12
   282  		{Undo, 0, 0},
   283  		{Ordered_Fail, 1, 12},
   284  		{Ordered_Fail, 1, 4},
   285  		{Ordered, 4, 12},
   286  		{Ordered, 100, 101},
   287  
   288  		// Undo: 100<101
   289  		{Undo, 0, 0},
   290  		{Ordered_Fail, 4, 7},
   291  		{Ordered_Fail, 7, 12},
   292  		{Ordered, 100, 101},
   293  
   294  		// Recreated DAG #1 from scratch, reusing same nodes.
   295  		// This also stresses that Undo has done its job correctly.
   296  		// DAG: 1<2<(5|6), 101<102<(105|106<107)
   297  		{Checkpoint, 0, 0},
   298  		{SetOrder, 101, 102},
   299  		{SetOrder, 102, 105},
   300  		{SetOrder, 102, 106},
   301  		{SetOrder, 106, 107},
   302  		{SetOrder, 1, 2},
   303  		{SetOrder, 2, 5},
   304  		{SetOrder, 2, 6},
   305  		{SetEqual_Fail, 1, 6},
   306  		{SetEqual_Fail, 107, 102},
   307  
   308  		// Now Set 2 == 102
   309  		// New DAG: (1|101)<2==102<(5|6|105|106<107)
   310  		{Checkpoint, 0, 0},
   311  		{SetEqual, 2, 102},
   312  		{Equal, 2, 102},
   313  		{SetEqual, 2, 102},         // trivially pass
   314  		{SetNonEqual_Fail, 2, 102}, // trivially fail
   315  		{Ordered, 1, 107},
   316  		{Ordered, 101, 6},
   317  		{Ordered, 101, 105},
   318  		{Ordered, 2, 106},
   319  		{Ordered, 102, 6},
   320  
   321  		// Undo SetEqual
   322  		{Undo, 0, 0},
   323  		{Equal_Fail, 2, 102},
   324  		{Ordered_Fail, 2, 102},
   325  		{Ordered_Fail, 1, 107},
   326  		{Ordered_Fail, 101, 6},
   327  		{Checkpoint, 0, 0},
   328  		{SetEqual, 2, 100},
   329  		{Ordered, 1, 107},
   330  		{Ordered, 100, 6},
   331  
   332  		// SetEqual with new node
   333  		{Undo, 0, 0},
   334  		{Checkpoint, 0, 0},
   335  		{SetEqual, 2, 400},
   336  		{SetEqual, 401, 2},
   337  		{Equal, 400, 401},
   338  		{Ordered, 1, 400},
   339  		{Ordered, 400, 6},
   340  		{Ordered, 1, 401},
   341  		{Ordered, 401, 6},
   342  		{Ordered_Fail, 2, 401},
   343  
   344  		// SetEqual unseen nodes and then connect
   345  		{Checkpoint, 0, 0},
   346  		{SetEqual, 500, 501},
   347  		{SetEqual, 102, 501},
   348  		{Equal, 500, 102},
   349  		{Ordered, 501, 106},
   350  		{Ordered, 100, 500},
   351  		{SetEqual, 500, 501},
   352  		{Ordered_Fail, 500, 501},
   353  		{Ordered_Fail, 102, 501},
   354  
   355  		// SetNonEqual relations
   356  		{Undo, 0, 0},
   357  		{Checkpoint, 0, 0},
   358  		{SetNonEqual, 600, 601},
   359  		{NonEqual, 600, 601},
   360  		{SetNonEqual, 601, 602},
   361  		{NonEqual, 601, 602},
   362  		{NonEqual_Fail, 600, 602}, // non-transitive
   363  		{SetEqual_Fail, 601, 602},
   364  
   365  		// Undo back to beginning, leave the poset empty
   366  		{Undo, 0, 0},
   367  		{Undo, 0, 0},
   368  		{Undo, 0, 0},
   369  		{Undo, 0, 0},
   370  	})
   371  }
   372  
   373  func TestPosetStrict(t *testing.T) {
   374  
   375  	testPosetOps(t, false, []posetTestOp{
   376  		{Checkpoint, 0, 0},
   377  		// Build: 20!=30, 10<20<=30<40. The 20<=30 will become 20<30.
   378  		{SetNonEqual, 20, 30},
   379  		{SetOrder, 10, 20},
   380  		{SetOrderOrEqual, 20, 30}, // this is affected by 20!=30
   381  		{SetOrder, 30, 40},
   382  
   383  		{Ordered, 10, 30},
   384  		{Ordered, 20, 30},
   385  		{Ordered, 10, 40},
   386  		{OrderedOrEqual, 10, 30},
   387  		{OrderedOrEqual, 20, 30},
   388  		{OrderedOrEqual, 10, 40},
   389  
   390  		{Undo, 0, 0},
   391  
   392  		// Now do the opposite: first build the DAG and then learn non-equality
   393  		{Checkpoint, 0, 0},
   394  		{SetOrder, 10, 20},
   395  		{SetOrderOrEqual, 20, 30}, // this is affected by 20!=30
   396  		{SetOrder, 30, 40},
   397  
   398  		{Ordered, 10, 30},
   399  		{Ordered_Fail, 20, 30},
   400  		{Ordered, 10, 40},
   401  		{OrderedOrEqual, 10, 30},
   402  		{OrderedOrEqual, 20, 30},
   403  		{OrderedOrEqual, 10, 40},
   404  
   405  		{Checkpoint, 0, 0},
   406  		{SetNonEqual, 20, 30},
   407  		{Ordered, 10, 30},
   408  		{Ordered, 20, 30},
   409  		{Ordered, 10, 40},
   410  		{OrderedOrEqual, 10, 30},
   411  		{OrderedOrEqual, 20, 30},
   412  		{OrderedOrEqual, 10, 40},
   413  		{Undo, 0, 0},
   414  
   415  		{Checkpoint, 0, 0},
   416  		{SetOrderOrEqual, 30, 35},
   417  		{OrderedOrEqual, 20, 35},
   418  		{Ordered_Fail, 20, 35},
   419  		{SetNonEqual, 20, 35},
   420  		{Ordered, 20, 35},
   421  		{Undo, 0, 0},
   422  
   423  		// Learn <= and >=
   424  		{Checkpoint, 0, 0},
   425  		{SetOrderOrEqual, 50, 60},
   426  		{SetOrderOrEqual, 60, 50},
   427  		{OrderedOrEqual, 50, 60},
   428  		{OrderedOrEqual, 60, 50},
   429  		{Ordered_Fail, 50, 60},
   430  		{Ordered_Fail, 60, 50},
   431  		{Equal, 50, 60},
   432  		{Equal, 60, 50},
   433  		{NonEqual_Fail, 50, 60},
   434  		{NonEqual_Fail, 60, 50},
   435  		{Undo, 0, 0},
   436  
   437  		{Undo, 0, 0},
   438  	})
   439  }
   440  
   441  func TestPosetCollapse(t *testing.T) {
   442  	testPosetOps(t, false, []posetTestOp{
   443  		{Checkpoint, 0, 0},
   444  		// Create a complex graph of <= relations among nodes between 10 and 25.
   445  		{SetOrderOrEqual, 10, 15},
   446  		{SetOrderOrEqual, 15, 20},
   447  		{SetOrderOrEqual, 20, vconst(20)},
   448  		{SetOrderOrEqual, vconst(20), 25},
   449  		{SetOrderOrEqual, 10, 12},
   450  		{SetOrderOrEqual, 12, 16},
   451  		{SetOrderOrEqual, 16, vconst(20)},
   452  		{SetOrderOrEqual, 10, 17},
   453  		{SetOrderOrEqual, 17, 25},
   454  		{SetOrderOrEqual, 15, 18},
   455  		{SetOrderOrEqual, 18, vconst(20)},
   456  		{SetOrderOrEqual, 15, 19},
   457  		{SetOrderOrEqual, 19, 25},
   458  
   459  		// These are other paths not part of the main collapsing path
   460  		{SetOrderOrEqual, 10, 11},
   461  		{SetOrderOrEqual, 11, 26},
   462  		{SetOrderOrEqual, 13, 25},
   463  		{SetOrderOrEqual, 100, 25},
   464  		{SetOrderOrEqual, 101, 15},
   465  		{SetOrderOrEqual, 102, 10},
   466  		{SetOrderOrEqual, 25, 103},
   467  		{SetOrderOrEqual, 20, 104},
   468  
   469  		{Checkpoint, 0, 0},
   470  		// Collapse everything by setting 10 >= 25: this should make everything equal
   471  		{SetOrderOrEqual, 25, 10},
   472  
   473  		// Check that all nodes are pairwise equal now
   474  		{Equal, 10, 12},
   475  		{Equal, 10, 15},
   476  		{Equal, 10, 16},
   477  		{Equal, 10, 17},
   478  		{Equal, 10, 18},
   479  		{Equal, 10, 19},
   480  		{Equal, 10, vconst(20)},
   481  		{Equal, 10, vconst2(20)},
   482  		{Equal, 10, 25},
   483  
   484  		{Equal, 12, 15},
   485  		{Equal, 12, 16},
   486  		{Equal, 12, 17},
   487  		{Equal, 12, 18},
   488  		{Equal, 12, 19},
   489  		{Equal, 12, vconst(20)},
   490  		{Equal, 12, vconst2(20)},
   491  		{Equal, 12, 25},
   492  
   493  		{Equal, 15, 16},
   494  		{Equal, 15, 17},
   495  		{Equal, 15, 18},
   496  		{Equal, 15, 19},
   497  		{Equal, 15, vconst(20)},
   498  		{Equal, 15, vconst2(20)},
   499  		{Equal, 15, 25},
   500  
   501  		{Equal, 16, 17},
   502  		{Equal, 16, 18},
   503  		{Equal, 16, 19},
   504  		{Equal, 16, vconst(20)},
   505  		{Equal, 16, vconst2(20)},
   506  		{Equal, 16, 25},
   507  
   508  		{Equal, 17, 18},
   509  		{Equal, 17, 19},
   510  		{Equal, 17, vconst(20)},
   511  		{Equal, 17, vconst2(20)},
   512  		{Equal, 17, 25},
   513  
   514  		{Equal, 18, 19},
   515  		{Equal, 18, vconst(20)},
   516  		{Equal, 18, vconst2(20)},
   517  		{Equal, 18, 25},
   518  
   519  		{Equal, 19, vconst(20)},
   520  		{Equal, 19, vconst2(20)},
   521  		{Equal, 19, 25},
   522  
   523  		{Equal, vconst(20), vconst2(20)},
   524  		{Equal, vconst(20), 25},
   525  
   526  		{Equal, vconst2(20), 25},
   527  
   528  		// ... but not 11/26/100/101/102, which were on a different path
   529  		{Equal_Fail, 10, 11},
   530  		{Equal_Fail, 10, 26},
   531  		{Equal_Fail, 10, 100},
   532  		{Equal_Fail, 10, 101},
   533  		{Equal_Fail, 10, 102},
   534  		{OrderedOrEqual, 10, 26},
   535  		{OrderedOrEqual, 25, 26},
   536  		{OrderedOrEqual, 13, 25},
   537  		{OrderedOrEqual, 13, 10},
   538  
   539  		{Undo, 0, 0},
   540  		{OrderedOrEqual, 10, 25},
   541  		{Equal_Fail, 10, 12},
   542  		{Equal_Fail, 10, 15},
   543  		{Equal_Fail, 10, 25},
   544  
   545  		{Undo, 0, 0},
   546  	})
   547  
   548  	testPosetOps(t, false, []posetTestOp{
   549  		{Checkpoint, 0, 0},
   550  		{SetOrderOrEqual, 10, 15},
   551  		{SetOrderOrEqual, 15, 20},
   552  		{SetOrderOrEqual, 20, 25},
   553  		{SetOrder, 10, 16},
   554  		{SetOrderOrEqual, 16, 20},
   555  		// Check that we cannot collapse here because of the strict relation 10<16
   556  		{SetOrderOrEqual_Fail, 20, 10},
   557  		{Undo, 0, 0},
   558  	})
   559  }
   560  
   561  func TestPosetSetEqual(t *testing.T) {
   562  	testPosetOps(t, false, []posetTestOp{
   563  		// 10<=20<=30<40,  20<=100<110
   564  		{Checkpoint, 0, 0},
   565  		{SetOrderOrEqual, 10, 20},
   566  		{SetOrderOrEqual, 20, 30},
   567  		{SetOrder, 30, 40},
   568  		{SetOrderOrEqual, 20, 100},
   569  		{SetOrder, 100, 110},
   570  		{OrderedOrEqual, 10, 30},
   571  		{OrderedOrEqual_Fail, 30, 10},
   572  		{Ordered_Fail, 10, 30},
   573  		{Ordered_Fail, 30, 10},
   574  		{Ordered, 10, 40},
   575  		{Ordered_Fail, 40, 10},
   576  
   577  		// Try learning 10==20.
   578  		{Checkpoint, 0, 0},
   579  		{SetEqual, 10, 20},
   580  		{OrderedOrEqual, 10, 20},
   581  		{Ordered_Fail, 10, 20},
   582  		{Equal, 10, 20},
   583  		{SetOrderOrEqual, 10, 20},
   584  		{SetOrderOrEqual, 20, 10},
   585  		{SetOrder_Fail, 10, 20},
   586  		{SetOrder_Fail, 20, 10},
   587  		{Undo, 0, 0},
   588  
   589  		// Try learning 20==10.
   590  		{Checkpoint, 0, 0},
   591  		{SetEqual, 20, 10},
   592  		{OrderedOrEqual, 10, 20},
   593  		{Ordered_Fail, 10, 20},
   594  		{Equal, 10, 20},
   595  		{Undo, 0, 0},
   596  
   597  		// Try learning 10==40 or 30==40 or 10==110.
   598  		{Checkpoint, 0, 0},
   599  		{SetEqual_Fail, 10, 40},
   600  		{SetEqual_Fail, 40, 10},
   601  		{SetEqual_Fail, 30, 40},
   602  		{SetEqual_Fail, 40, 30},
   603  		{SetEqual_Fail, 10, 110},
   604  		{SetEqual_Fail, 110, 10},
   605  		{Undo, 0, 0},
   606  
   607  		// Try learning 40==110, and then 10==40 or 10=110
   608  		{Checkpoint, 0, 0},
   609  		{SetEqual, 40, 110},
   610  		{SetEqual_Fail, 10, 40},
   611  		{SetEqual_Fail, 40, 10},
   612  		{SetEqual_Fail, 10, 110},
   613  		{SetEqual_Fail, 110, 10},
   614  		{Undo, 0, 0},
   615  
   616  		// Try learning 40<20 or 30<20 or 110<10
   617  		{Checkpoint, 0, 0},
   618  		{SetOrder_Fail, 40, 20},
   619  		{SetOrder_Fail, 30, 20},
   620  		{SetOrder_Fail, 110, 10},
   621  		{Undo, 0, 0},
   622  
   623  		// Try learning 30<=20
   624  		{Checkpoint, 0, 0},
   625  		{SetOrderOrEqual, 30, 20},
   626  		{Equal, 30, 20},
   627  		{OrderedOrEqual, 30, 100},
   628  		{Ordered, 30, 110},
   629  		{Undo, 0, 0},
   630  
   631  		{Undo, 0, 0},
   632  	})
   633  }
   634  
   635  func TestPosetConst(t *testing.T) {
   636  	testPosetOps(t, false, []posetTestOp{
   637  		{Checkpoint, 0, 0},
   638  		{SetOrder, 1, vconst(15)},
   639  		{SetOrderOrEqual, 100, vconst(120)},
   640  		{Ordered, 1, vconst(15)},
   641  		{Ordered, 1, vconst(120)},
   642  		{OrderedOrEqual, 1, vconst(120)},
   643  		{OrderedOrEqual, 100, vconst(120)},
   644  		{Ordered_Fail, 100, vconst(15)},
   645  		{Ordered_Fail, vconst(15), 100},
   646  
   647  		{Checkpoint, 0, 0},
   648  		{SetOrderOrEqual, 1, 5},
   649  		{SetOrderOrEqual, 5, 25},
   650  		{SetEqual, 20, vconst(20)},
   651  		{SetEqual, 25, vconst(25)},
   652  		{Ordered, 1, 20},
   653  		{Ordered, 1, vconst(30)},
   654  		{Undo, 0, 0},
   655  
   656  		{Checkpoint, 0, 0},
   657  		{SetOrderOrEqual, 1, 5},
   658  		{SetOrderOrEqual, 5, 25},
   659  		{SetEqual, vconst(-20), 5},
   660  		{SetEqual, vconst(-25), 1},
   661  		{Ordered, 1, 5},
   662  		{Ordered, vconst(-30), 1},
   663  		{Undo, 0, 0},
   664  
   665  		{Checkpoint, 0, 0},
   666  		{SetNonEqual, 1, vconst(4)},
   667  		{SetNonEqual, 1, vconst(6)},
   668  		{NonEqual, 1, vconst(4)},
   669  		{NonEqual_Fail, 1, vconst(5)},
   670  		{NonEqual, 1, vconst(6)},
   671  		{Equal_Fail, 1, vconst(4)},
   672  		{Equal_Fail, 1, vconst(5)},
   673  		{Equal_Fail, 1, vconst(6)},
   674  		{Equal_Fail, 1, vconst(7)},
   675  		{Undo, 0, 0},
   676  
   677  		{Undo, 0, 0},
   678  	})
   679  
   680  	testPosetOps(t, true, []posetTestOp{
   681  		{Checkpoint, 0, 0},
   682  		{SetOrder, 1, vconst(15)},
   683  		{SetOrderOrEqual, 100, vconst(-5)}, // -5 is a very big number in unsigned
   684  		{Ordered, 1, vconst(15)},
   685  		{Ordered, 1, vconst(-5)},
   686  		{OrderedOrEqual, 1, vconst(-5)},
   687  		{OrderedOrEqual, 100, vconst(-5)},
   688  		{Ordered_Fail, 100, vconst(15)},
   689  		{Ordered_Fail, vconst(15), 100},
   690  
   691  		{Undo, 0, 0},
   692  	})
   693  
   694  	testPosetOps(t, false, []posetTestOp{
   695  		{Checkpoint, 0, 0},
   696  		{SetOrderOrEqual, 1, vconst(3)},
   697  		{SetNonEqual, 1, vconst(0)},
   698  		{Ordered_Fail, 1, vconst(0)},
   699  		{Undo, 0, 0},
   700  	})
   701  
   702  	testPosetOps(t, false, []posetTestOp{
   703  		// Check relations of a constant with itself
   704  		{Checkpoint, 0, 0},
   705  		{SetOrderOrEqual, vconst(3), vconst2(3)},
   706  		{Undo, 0, 0},
   707  		{Checkpoint, 0, 0},
   708  		{SetEqual, vconst(3), vconst2(3)},
   709  		{Undo, 0, 0},
   710  		{Checkpoint, 0, 0},
   711  		{SetNonEqual_Fail, vconst(3), vconst2(3)},
   712  		{Undo, 0, 0},
   713  		{Checkpoint, 0, 0},
   714  		{SetOrder_Fail, vconst(3), vconst2(3)},
   715  		{Undo, 0, 0},
   716  
   717  		// Check relations of two constants among them, using
   718  		// different instances of the same constant
   719  		{Checkpoint, 0, 0},
   720  		{SetOrderOrEqual, vconst(3), vconst(4)},
   721  		{OrderedOrEqual, vconst(3), vconst2(4)},
   722  		{Undo, 0, 0},
   723  		{Checkpoint, 0, 0},
   724  		{SetOrder, vconst(3), vconst(4)},
   725  		{Ordered, vconst(3), vconst2(4)},
   726  		{Undo, 0, 0},
   727  		{Checkpoint, 0, 0},
   728  		{SetEqual_Fail, vconst(3), vconst(4)},
   729  		{SetEqual_Fail, vconst(3), vconst2(4)},
   730  		{Undo, 0, 0},
   731  		{Checkpoint, 0, 0},
   732  		{NonEqual, vconst(3), vconst(4)},
   733  		{NonEqual, vconst(3), vconst2(4)},
   734  		{Undo, 0, 0},
   735  		{Checkpoint, 0, 0},
   736  		{Equal_Fail, vconst(3), vconst(4)},
   737  		{Equal_Fail, vconst(3), vconst2(4)},
   738  		{Undo, 0, 0},
   739  		{Checkpoint, 0, 0},
   740  		{SetNonEqual, vconst(3), vconst(4)},
   741  		{SetNonEqual, vconst(3), vconst2(4)},
   742  		{Undo, 0, 0},
   743  	})
   744  }
   745  
   746  func TestPosetNonEqual(t *testing.T) {
   747  	testPosetOps(t, false, []posetTestOp{
   748  		{Equal_Fail, 10, 20},
   749  		{NonEqual_Fail, 10, 20},
   750  
   751  		// Learn 10!=20
   752  		{Checkpoint, 0, 0},
   753  		{SetNonEqual, 10, 20},
   754  		{Equal_Fail, 10, 20},
   755  		{NonEqual, 10, 20},
   756  		{SetEqual_Fail, 10, 20},
   757  
   758  		// Learn again 10!=20
   759  		{Checkpoint, 0, 0},
   760  		{SetNonEqual, 10, 20},
   761  		{Equal_Fail, 10, 20},
   762  		{NonEqual, 10, 20},
   763  
   764  		// Undo. We still know 10!=20
   765  		{Undo, 0, 0},
   766  		{Equal_Fail, 10, 20},
   767  		{NonEqual, 10, 20},
   768  		{SetEqual_Fail, 10, 20},
   769  
   770  		// Undo again. Now we know nothing
   771  		{Undo, 0, 0},
   772  		{Equal_Fail, 10, 20},
   773  		{NonEqual_Fail, 10, 20},
   774  
   775  		// Learn 10==20
   776  		{Checkpoint, 0, 0},
   777  		{SetEqual, 10, 20},
   778  		{Equal, 10, 20},
   779  		{NonEqual_Fail, 10, 20},
   780  		{SetNonEqual_Fail, 10, 20},
   781  
   782  		// Learn again 10==20
   783  		{Checkpoint, 0, 0},
   784  		{SetEqual, 10, 20},
   785  		{Equal, 10, 20},
   786  		{NonEqual_Fail, 10, 20},
   787  		{SetNonEqual_Fail, 10, 20},
   788  
   789  		// Undo. We still know 10==20
   790  		{Undo, 0, 0},
   791  		{Equal, 10, 20},
   792  		{NonEqual_Fail, 10, 20},
   793  		{SetNonEqual_Fail, 10, 20},
   794  
   795  		// Undo. We know nothing
   796  		{Undo, 0, 0},
   797  		{Equal_Fail, 10, 20},
   798  		{NonEqual_Fail, 10, 20},
   799  	})
   800  }
   801
View as plain text