Skip to content

Commit bfa6ab4

Browse files
jbardinjbardin
committed
Fix removeEdge test failures
The removeEdge test could fail intermittently with the wrong order. The precondition of a 1->2->3 order wasn't met, because there was no edge from 1->3, so 3->1->2 was also a valid ordering. The other failure was a bookkeeping error, were the recorded order may not match the visited order. What happened in this case was the gateCh was closed by V2, allowing V3 to run which could beat V2 to recording its visit. Now the visit is recorded as part of the vertex walk, and the gate is released as the final operation. The order is deterministic now, so remove the brute-force test loop.
1 parent d01b0b0 commit bfa6ab4

1 file changed

Lines changed: 50 additions & 50 deletions

File tree

‎dag/walk_test.go‎

Lines changed: 50 additions & 50 deletions
Original file line numberDiff line numberDiff line change
@@ -215,63 +215,63 @@ func TestWalker_newEdge(t *testing.T) {
215215
}
216216

217217
func TestWalker_removeEdge(t *testing.T) {
218-
// Run it a bunch of times since it is timing dependent
219-
for i := 0; i < 50; i++ {
220-
var g AcyclicGraph
221-
g.Add(1)
222-
g.Add(2)
223-
g.Add(3)
224-
g.Connect(BasicEdge(1, 2))
225-
g.Connect(BasicEdge(3, 2))
226-
227-
// Record function
228-
var order []interface{}
229-
recordF := walkCbRecord(&order)
230-
231-
// The way this works is that our original graph forces
232-
// the order of 1 => 3 => 2. During the execution of 1, we
233-
// remove the edge forcing 3 before 2. Then, during the execution
234-
// of 3, we wait on a channel that is only closed by 2, implicitly
235-
// forcing 2 before 3 via the callback (and not the graph). If
236-
// 2 cannot execute before 3 (edge removal is non-functional), then
237-
// this test will timeout.
238-
var w *Walker
239-
gateCh := make(chan struct{})
240-
cb := func(v Vertex) error {
241-
if v == 1 {
242-
g.RemoveEdge(BasicEdge(3, 2))
243-
w.Update(&g)
244-
}
218+
var g AcyclicGraph
219+
g.Add(1)
220+
g.Add(2)
221+
g.Add(3)
222+
g.Connect(BasicEdge(1, 2))
223+
g.Connect(BasicEdge(1, 3))
224+
g.Connect(BasicEdge(3, 2))
245225

246-
if v == 2 {
247-
close(gateCh)
248-
}
226+
// Record function
227+
var order []interface{}
228+
recordF := walkCbRecord(&order)
249229

250-
if v == 3 {
251-
select {
252-
case <-gateCh:
253-
case <-time.After(50 * time.Millisecond):
254-
return fmt.Errorf("timeout 3 waiting for 2")
255-
}
256-
}
230+
// The way this works is that our original graph forces
231+
// the order of 1 => 3 => 2. During the execution of 1, we
232+
// remove the edge forcing 3 before 2. Then, during the execution
233+
// of 3, we wait on a channel that is only closed by 2, implicitly
234+
// forcing 2 before 3 via the callback (and not the graph). If
235+
// 2 cannot execute before 3 (edge removal is non-functional), then
236+
// this test will timeout.
237+
var w *Walker
238+
gateCh := make(chan struct{})
239+
cb := func(v Vertex) error {
240+
switch v {
241+
case 1:
242+
g.RemoveEdge(BasicEdge(3, 2))
243+
w.Update(&g)
257244

258-
return recordF(v)
245+
case 2:
246+
// this visit isn't completed until we've recorded it
247+
// Once the visit is official, we can then close the gate to
248+
// let 3 continue.
249+
defer close(gateCh)
250+
251+
case 3:
252+
select {
253+
case <-gateCh:
254+
case <-time.After(50 * time.Millisecond):
255+
return fmt.Errorf("timeout 3 waiting for 2")
256+
}
259257
}
260258

261-
// Add the initial vertices
262-
w = &Walker{Callback: cb}
263-
w.Update(&g)
259+
return recordF(v)
260+
}
264261

265-
// Wait
266-
if err := w.Wait(); err != nil {
267-
t.Fatalf("err: %s", err)
268-
}
262+
// Add the initial vertices
263+
w = &Walker{Callback: cb}
264+
w.Update(&g)
269265

270-
// Check
271-
expected := []interface{}{1, 2, 3}
272-
if !reflect.DeepEqual(order, expected) {
273-
t.Fatalf("bad: %#v", order)
274-
}
266+
// Wait
267+
if err := w.Wait(); err != nil {
268+
t.Fatalf("err: %s", err)
269+
}
270+
271+
// Check
272+
expected := []interface{}{1, 2, 3}
273+
if !reflect.DeepEqual(order, expected) {
274+
t.Fatalf("bad: %#v", order)
275275
}
276276
}
277277

0 commit comments

Comments
 (0)