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