1// Copyright 2014 The Cayley Authors. All rights reserved. 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 15package iterator_test 16 17// Tests relating to methods in and-iterator-optimize. Many are pretty simplistic, but 18// nonetheless cover a lot of basic cases. 19 20import ( 21 "reflect" 22 "sort" 23 "testing" 24 25 "github.com/cayleygraph/cayley/graph" 26 "github.com/cayleygraph/cayley/graph/graphmock" 27 . "github.com/cayleygraph/cayley/graph/iterator" 28) 29 30func TestIteratorPromotion(t *testing.T) { 31 qs := &graphmock.Oldstore{ 32 Data: []string{}, 33 Iter: NewFixed(), 34 } 35 all := NewInt64(1, 3, true) 36 fixed := NewFixed(Int64Node(3)) 37 a := NewAnd(qs, all, fixed) 38 all.Tagger().Add("a") 39 fixed.Tagger().Add("b") 40 a.Tagger().Add("c") 41 newIt, changed := a.Optimize() 42 if !changed { 43 t.Error("Iterator didn't optimize") 44 } 45 if newIt.Type() != graph.Fixed { 46 t.Error("Expected fixed iterator") 47 } 48 tagsExpected := []string{"a", "b", "c"} 49 tags := newIt.Tagger().Tags() 50 sort.Strings(tags) 51 if !reflect.DeepEqual(tags, tagsExpected) { 52 t.Fatal("Tags don't match") 53 } 54} 55 56func TestNullIteratorAnd(t *testing.T) { 57 qs := &graphmock.Oldstore{ 58 Data: []string{}, 59 Iter: NewFixed(), 60 } 61 all := NewInt64(1, 3, true) 62 null := NewNull() 63 a := NewAnd(qs, all, null) 64 newIt, changed := a.Optimize() 65 if !changed { 66 t.Error("Didn't change") 67 } 68 if newIt.Type() != graph.Null { 69 t.Error("Expected null iterator, got ", newIt.Type()) 70 } 71} 72 73func TestAllPromotion(t *testing.T) { 74 qs := &graphmock.Oldstore{ 75 Data: []string{}, 76 Iter: NewFixed(), 77 } 78 all := NewInt64(100, 300, true) 79 all.Tagger().Add("good") 80 all2 := NewInt64(1, 30000, true) 81 all2.Tagger().Add("slow") 82 a := NewAnd(qs) 83 // Make all2 the default iterator 84 a.AddSubIterator(all2) 85 a.AddSubIterator(all) 86 87 newIt, changed := a.Optimize() 88 if !changed { 89 t.Error("Expected new iterator") 90 } 91 if newIt.Type() != graph.All { 92 t.Error("Should have promoted the All iterator") 93 } 94 expectedTags := []string{"good", "slow"} 95 tagsOut := make([]string, 0) 96 for _, x := range newIt.Tagger().Tags() { 97 tagsOut = append(tagsOut, x) 98 } 99 sort.Strings(tagsOut) 100 if !reflect.DeepEqual(expectedTags, tagsOut) { 101 t.Fatalf("Tags don't match: expected: %#v, got: %#v", expectedTags, tagsOut) 102 } 103} 104 105func TestReorderWithTag(t *testing.T) { 106 qs := &graphmock.Oldstore{ 107 Data: []string{}, 108 Iter: NewFixed(), 109 } 110 all := NewFixed(Int64Node(3)) 111 all.Tagger().Add("good") 112 all2 := NewFixed( 113 Int64Node(3), 114 Int64Node(4), 115 Int64Node(5), 116 Int64Node(6), 117 ) 118 all2.Tagger().Add("slow") 119 a := NewAnd(qs) 120 // Make all2 the default iterator 121 a.AddSubIterator(all2) 122 a.AddSubIterator(all) 123 124 newIt, changed := a.Optimize() 125 if !changed { 126 t.Error("Expected new iterator") 127 } 128 expectedTags := []string{"good", "slow"} 129 tagsOut := make([]string, 0) 130 for _, sub := range newIt.SubIterators() { 131 for _, x := range sub.Tagger().Tags() { 132 tagsOut = append(tagsOut, x) 133 } 134 } 135 for _, x := range newIt.Tagger().Tags() { 136 tagsOut = append(tagsOut, x) 137 } 138 sort.Strings(tagsOut) 139 if !reflect.DeepEqual(expectedTags, tagsOut) { 140 t.Fatalf("Tags don't match: expected: %#v, got: %#v", expectedTags, tagsOut) 141 } 142} 143 144func TestAndStatistics(t *testing.T) { 145 qs := &graphmock.Oldstore{ 146 Data: []string{}, 147 Iter: NewFixed(), 148 } 149 all := NewInt64(100, 300, true) 150 all.Tagger().Add("good") 151 all2 := NewInt64(1, 30000, true) 152 all2.Tagger().Add("slow") 153 a := NewAnd(qs) 154 // Make all2 the default iterator 155 a.AddSubIterator(all2) 156 a.AddSubIterator(all) 157 stats1 := a.Stats() 158 newIt, changed := a.Optimize() 159 if !changed { 160 t.Error("Didn't optimize") 161 } 162 stats2 := newIt.Stats() 163 if stats2.NextCost > stats1.NextCost { 164 t.Error("And didn't optimize. Next cost old ", stats1.NextCost, "and new ", stats2.NextCost) 165 } 166} 167