summaryrefslogtreecommitdiffstats
path: root/spec/unit/simple_graph_spec.rb
blob: 17e382fccc527427269ecca77dbc1cd64522a60e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
#!/usr/bin/env rspec
#
#  Created by Luke Kanies on 2007-11-1.
#  Copyright (c) 2006. All rights reserved.

require 'spec_helper'
require 'puppet/simple_graph'

describe Puppet::SimpleGraph do
  it "should return the number of its vertices as its length" do
    @graph = Puppet::SimpleGraph.new
    @graph.add_vertex("one")
    @graph.add_vertex("two")
    @graph.size.should == 2
  end

  it "should consider itself a directed graph" do
    Puppet::SimpleGraph.new.directed?.should be_true
  end

  it "should provide a method for reversing the graph" do
    @graph = Puppet::SimpleGraph.new
    @graph.add_edge(:one, :two)
    @graph.reversal.edge?(:two, :one).should be_true
  end

  it "should be able to produce a dot graph" do
    @graph = Puppet::SimpleGraph.new
    @graph.add_edge(:one, :two)

    proc { @graph.to_dot_graph }.should_not raise_error
  end

  describe "when managing vertices" do
    before do
      @graph = Puppet::SimpleGraph.new
    end

    it "should provide a method to add a vertex" do
      @graph.add_vertex(:test)
      @graph.vertex?(:test).should be_true
    end

    it "should reset its reversed graph when vertices are added" do
      rev = @graph.reversal
      @graph.add_vertex(:test)
      @graph.reversal.should_not equal(rev)
    end

    it "should ignore already-present vertices when asked to add a vertex" do
      @graph.add_vertex(:test)
      proc { @graph.add_vertex(:test) }.should_not raise_error
    end

    it "should return true when asked if a vertex is present" do
      @graph.add_vertex(:test)
      @graph.vertex?(:test).should be_true
    end

    it "should return false when asked if a non-vertex is present" do
      @graph.vertex?(:test).should be_false
    end

    it "should return all set vertices when asked" do
      @graph.add_vertex(:one)
      @graph.add_vertex(:two)
      @graph.vertices.length.should == 2
      @graph.vertices.should include(:one)
      @graph.vertices.should include(:two)
    end

    it "should remove a given vertex when asked" do
      @graph.add_vertex(:one)
      @graph.remove_vertex!(:one)
      @graph.vertex?(:one).should be_false
    end

    it "should do nothing when a non-vertex is asked to be removed" do
      proc { @graph.remove_vertex!(:one) }.should_not raise_error
    end
  end

  describe "when managing edges" do
    before do
      @graph = Puppet::SimpleGraph.new
    end

    it "should provide a method to test whether a given vertex pair is an edge" do
      @graph.should respond_to(:edge?)
    end

    it "should reset its reversed graph when edges are added" do
      rev = @graph.reversal
      @graph.add_edge(:one, :two)
      @graph.reversal.should_not equal(rev)
    end

    it "should provide a method to add an edge as an instance of the edge class" do
      edge = Puppet::Relationship.new(:one, :two)
      @graph.add_edge(edge)
      @graph.edge?(:one, :two).should be_true
    end

    it "should provide a method to add an edge by specifying the two vertices" do
      @graph.add_edge(:one, :two)
      @graph.edge?(:one, :two).should be_true
    end

    it "should provide a method to add an edge by specifying the two vertices and a label" do
      @graph.add_edge(:one, :two, :callback => :awesome)
      @graph.edge?(:one, :two).should be_true
    end

    describe "when retrieving edges between two nodes" do
      it "should handle the case of nodes not in the graph" do
        @graph.edges_between(:one, :two).should == []
      end

      it "should handle the case of nodes with no edges between them" do
        @graph.add_vertex(:one)
        @graph.add_vertex(:two)
        @graph.edges_between(:one, :two).should == []
      end

      it "should handle the case of nodes connected by a single edge" do
        edge = Puppet::Relationship.new(:one, :two)
        @graph.add_edge(edge)
        @graph.edges_between(:one, :two).length.should == 1
        @graph.edges_between(:one, :two)[0].should equal(edge)
      end

      it "should handle the case of nodes connected by multiple edges" do
        edge1 = Puppet::Relationship.new(:one, :two, :callback => :foo)
        edge2 = Puppet::Relationship.new(:one, :two, :callback => :bar)
        @graph.add_edge(edge1)
        @graph.add_edge(edge2)
        Set.new(@graph.edges_between(:one, :two)).should == Set.new([edge1, edge2])
      end
    end

    it "should add the edge source as a vertex if it is not already" do
      edge = Puppet::Relationship.new(:one, :two)
      @graph.add_edge(edge)
      @graph.vertex?(:one).should be_true
    end

    it "should add the edge target as a vertex if it is not already" do
      edge = Puppet::Relationship.new(:one, :two)
      @graph.add_edge(edge)
      @graph.vertex?(:two).should be_true
    end

    it "should return all edges as edge instances when asked" do
      one = Puppet::Relationship.new(:one, :two)
      two = Puppet::Relationship.new(:two, :three)
      @graph.add_edge(one)
      @graph.add_edge(two)
      edges = @graph.edges
      edges.should be_instance_of(Array)
      edges.length.should == 2
      edges.should include(one)
      edges.should include(two)
    end

    it "should remove an edge when asked" do
      edge = Puppet::Relationship.new(:one, :two)
      @graph.add_edge(edge)
      @graph.remove_edge!(edge)
      @graph.edge?(edge.source, edge.target).should be_false
    end

    it "should remove all related edges when a vertex is removed" do
      one = Puppet::Relationship.new(:one, :two)
      two = Puppet::Relationship.new(:two, :three)
      @graph.add_edge(one)
      @graph.add_edge(two)
      @graph.remove_vertex!(:two)
      @graph.edge?(:one, :two).should be_false
      @graph.edge?(:two, :three).should be_false
      @graph.edges.length.should == 0
    end
  end

  describe "when finding adjacent vertices" do
    before do
      @graph = Puppet::SimpleGraph.new
      @one_two = Puppet::Relationship.new(:one, :two)
      @two_three = Puppet::Relationship.new(:two, :three)
      @one_three = Puppet::Relationship.new(:one, :three)
      @graph.add_edge(@one_two)
      @graph.add_edge(@one_three)
      @graph.add_edge(@two_three)
    end

    it "should return adjacent vertices" do
      adj = @graph.adjacent(:one)
      adj.should be_include(:three)
      adj.should be_include(:two)
    end

    it "should default to finding :out vertices" do
      @graph.adjacent(:two).should == [:three]
    end

    it "should support selecting :in vertices" do
      @graph.adjacent(:two, :direction => :in).should == [:one]
    end

    it "should default to returning the matching vertices as an array of vertices" do
      @graph.adjacent(:two).should == [:three]
    end

    it "should support returning an array of matching edges" do
      @graph.adjacent(:two, :type => :edges).should == [@two_three]
    end

    # Bug #2111
    it "should not consider a vertex adjacent just because it was asked about previously" do
      @graph = Puppet::SimpleGraph.new
      @graph.add_vertex("a")
      @graph.add_vertex("b")
      @graph.edge?("a", "b")
      @graph.adjacent("a").should == []
    end
  end

  describe "when clearing" do
    before do
      @graph = Puppet::SimpleGraph.new
      one = Puppet::Relationship.new(:one, :two)
      two = Puppet::Relationship.new(:two, :three)
      @graph.add_edge(one)
      @graph.add_edge(two)

      @graph.clear
    end

    it "should remove all vertices" do
      @graph.vertices.should be_empty
    end

    it "should remove all edges" do
      @graph.edges.should be_empty
    end
  end

  describe "when reversing graphs" do
    before do
      @graph = Puppet::SimpleGraph.new
    end

    it "should provide a method for reversing the graph" do
      @graph.add_edge(:one, :two)
      @graph.reversal.edge?(:two, :one).should be_true
    end

    it "should add all vertices to the reversed graph" do
      @graph.add_edge(:one, :two)
      @graph.vertex?(:one).should be_true
      @graph.vertex?(:two).should be_true
    end

    it "should retain labels on edges" do
      @graph.add_edge(:one, :two, :callback => :awesome)
      edge = @graph.reversal.edges_between(:two, :one)[0]
      edge.label.should == {:callback => :awesome}
    end
  end

  describe "when reporting cycles in the graph" do
    before do
      @graph = Puppet::SimpleGraph.new
    end

    def add_edges(hash)
      hash.each do |a,b|
        @graph.add_edge(a, b)
      end
    end

    it "should fail on two-vertex loops" do
      add_edges :a => :b, :b => :a
      proc { @graph.report_cycles_in_graph }.should raise_error(Puppet::Error)
    end

    it "should fail on multi-vertex loops" do
      add_edges :a => :b, :b => :c, :c => :a
      proc { @graph.report_cycles_in_graph }.should raise_error(Puppet::Error)
    end

    it "should fail when a larger tree contains a small cycle" do
      add_edges :a => :b, :b => :a, :c => :a, :d => :c
      proc { @graph.report_cycles_in_graph }.should raise_error(Puppet::Error)
    end

    it "should succeed on trees with no cycles" do
      add_edges :a => :b, :b => :e, :c => :a, :d => :c
      proc { @graph.report_cycles_in_graph }.should_not raise_error
    end

    it "should produce the correct relationship text" do
      add_edges :a => :b, :b => :a
      # cycle detection starts from a or b randomly
      # so we need to check for either ordering in the error message
      want = %r{Found 1 dependency cycle:\n\((a => b => a|b => a => b)\)\nTry}
      expect { @graph.report_cycles_in_graph }.to raise_error(Puppet::Error, want)
    end

    it "cycle discovery should be the minimum cycle for a simple graph" do
      add_edges "a" => "b"
      add_edges "b" => "a"
      add_edges "b" => "c"

      cycles = nil
      expect { cycles = @graph.find_cycles_in_graph.sort }.should_not raise_error
      cycles.should be == [["a", "b"]]
    end

    it "cycle discovery should handle two distinct cycles" do
      add_edges "a" => "a1", "a1" => "a"
      add_edges "b" => "b1", "b1" => "b"

      cycles = nil
      expect { cycles = @graph.find_cycles_in_graph.sort }.should_not raise_error
      cycles.should be == [["a", "a1"], ["b", "b1"]]
    end

    it "cycle discovery should handle two cycles in a connected graph" do
      add_edges "a" => "b", "b" => "c", "c" => "d"
      add_edges "a" => "a1", "a1" => "a"
      add_edges "c" => "c1", "c1" => "c2", "c2" => "c3", "c3" => "c"

      cycles = nil
      expect { cycles = @graph.find_cycles_in_graph.sort }.should_not raise_error
      cycles.should be == [%w{a a1}, %w{c c1 c2 c3}]
    end

    it "cycle discovery should handle a complicated cycle" do
      add_edges "a" => "b", "b" => "c"
      add_edges "a" => "c"
      add_edges "c" => "c1", "c1" => "a"
      add_edges "c" => "c2", "c2" => "b"

      cycles = nil
      expect { cycles = @graph.find_cycles_in_graph.sort }.should_not raise_error
      cycles.should be == [%w{a b c c1 c2}]
    end

    it "cycle discovery should not fail with large data sets" do
      limit = 3000
      (1..(limit - 1)).each do |n| add_edges n.to_s => (n+1).to_s end

      cycles = nil
      expect { cycles = @graph.find_cycles_in_graph.sort }.should_not raise_error
      cycles.should be == []
    end

    it "path finding should work with a simple cycle" do
      add_edges "a" => "b", "b" => "c", "c" => "a"

      cycles = @graph.find_cycles_in_graph.sort
      paths = @graph.paths_in_cycle(cycles.first, 100)
      paths.should be == [%w{a b c a}]
    end

    it "path finding should work with two independent cycles" do
      add_edges "a" => "b1"
      add_edges "a" => "b2"
      add_edges "b1" => "a", "b2" => "a"

      cycles = @graph.find_cycles_in_graph.sort
      cycles.length.should be == 1

      paths = @graph.paths_in_cycle(cycles.first, 100)
      paths.sort.should be == [%w{a b1 a}, %w{a b2 a}]
    end

    it "path finding should prefer shorter paths in cycles" do
      add_edges "a" => "b", "b" => "c", "c" => "a"
      add_edges "b" => "a"

      cycles = @graph.find_cycles_in_graph.sort
      cycles.length.should be == 1

      paths = @graph.paths_in_cycle(cycles.first, 100)
      paths.should be == [%w{a b a}, %w{a b c a}]
    end

    it "path finding should respect the max_path value" do
      (1..20).each do |n| add_edges "a" => "b#{n}", "b#{n}" => "a" end

      cycles = @graph.find_cycles_in_graph.sort
      cycles.length.should be == 1

      (1..20).each do |n|
        paths = @graph.paths_in_cycle(cycles.first, n)
        paths.length.should be == n
      end

      paths = @graph.paths_in_cycle(cycles.first, 21)
      paths.length.should be == 20
    end
  end

  describe "when writing dot files" do
    before do
      @graph = Puppet::SimpleGraph.new
      @name = :test
      @file = File.join(Puppet[:graphdir], @name.to_s + ".dot")
    end

    it "should only write when graphing is enabled" do
      File.expects(:open).with(@file).never
      Puppet[:graph] = false
      @graph.write_graph(@name)
    end

    it "should write a dot file based on the passed name" do
      File.expects(:open).with(@file, "w").yields(stub("file", :puts => nil))
      @graph.expects(:to_dot).with("name" => @name.to_s.capitalize)
      Puppet[:graph] = true
      @graph.write_graph(@name)
    end

    after do
      Puppet.settings.clear
    end
  end

  describe Puppet::SimpleGraph do
    before do
      @graph = Puppet::SimpleGraph.new
    end

    it "should correctly clear vertices and edges when asked" do
      @graph.add_edge("a", "b")
      @graph.add_vertex "c"
      @graph.clear
      @graph.vertices.should be_empty
      @graph.edges.should be_empty
    end
  end

  describe "when matching edges", :'fails_on_ruby_1.9.2' => true do
    before do
      @graph = Puppet::SimpleGraph.new
      @event = Puppet::Transaction::Event.new(:name => :yay, :resource => "a")
      @none = Puppet::Transaction::Event.new(:name => :NONE, :resource => "a")

      @edges = {}
      @edges["a/b"] = Puppet::Relationship.new("a", "b", {:event => :yay, :callback => :refresh})
      @edges["a/c"] = Puppet::Relationship.new("a", "c", {:event => :yay, :callback => :refresh})
      @graph.add_edge(@edges["a/b"])
    end

    it "should match edges whose source matches the source of the event" do
      @graph.matching_edges(@event).should == [@edges["a/b"]]
    end

    it "should match always match nothing when the event is :NONE" do
      @graph.matching_edges(@none).should be_empty
    end

    it "should match multiple edges" do
      @graph.add_edge(@edges["a/c"])
      edges = @graph.matching_edges(@event)
      edges.should be_include(@edges["a/b"])
      edges.should be_include(@edges["a/c"])
    end
  end

  describe "when determining dependencies" do
    before do
      @graph = Puppet::SimpleGraph.new

      @graph.add_edge("a", "b")
      @graph.add_edge("a", "c")
      @graph.add_edge("b", "d")
    end

    it "should find all dependents when they are on multiple levels" do
      @graph.dependents("a").sort.should == %w{b c d}.sort
    end

    it "should find single dependents" do
      @graph.dependents("b").sort.should == %w{d}.sort
    end

    it "should return an empty array when there are no dependents" do
      @graph.dependents("c").sort.should == [].sort
    end

    it "should find all dependencies when they are on multiple levels" do
      @graph.dependencies("d").sort.should == %w{a b}
    end

    it "should find single dependencies" do
      @graph.dependencies("c").sort.should == %w{a}
    end

    it "should return an empty array when there are no dependencies" do
      @graph.dependencies("a").sort.should == []
    end
  end

  require 'puppet/util/graph'

  class Container < Puppet::Type::Component
    include Puppet::Util::Graph
    include Enumerable
    attr_accessor :name
    def each
      @children.each do |c| yield c end
    end

    def initialize(name, ary)
      @name = name
      @children = ary
    end

    def push(*ary)
      ary.each { |c| @children.push(c)}
    end

    def to_s
      @name
    end

    def ref
      "Container[#{self}]"
    end
  end

  require "puppet/resource/catalog"
  describe "when splicing the graph" do
    def container_graph
      @one = Container.new("one", %w{a b})
      @two = Container.new("two", ["c", "d"])
      @three = Container.new("three", ["i", "j"])
      @middle = Container.new("middle", ["e", "f", @two])
      @top = Container.new("top", ["g", "h", @middle, @one, @three])
      @empty = Container.new("empty", [])

      @whit  = Puppet::Type.type(:whit)
      @stage = Puppet::Type.type(:stage).new(:name => "foo")

      @contgraph = @top.to_graph(Puppet::Resource::Catalog.new)

      # We have to add the container to the main graph, else it won't
      # be spliced in the dependency graph.
      @contgraph.add_vertex(@empty)
    end

    def containers
      @contgraph.vertices.select { |x| !x.is_a? String }
    end

    def contents_of(x)
      @contgraph.direct_dependents_of(x)
    end

    def dependency_graph
      @depgraph = Puppet::SimpleGraph.new
      @contgraph.vertices.each do |v|
        @depgraph.add_vertex(v)
      end

      # We have to specify a relationship to our empty container, else it
      # never makes it into the dep graph in the first place.
      @explicit_dependencies = {@one => @two, "f" => "c", "h" => @middle, "c" => @empty}
      @explicit_dependencies.each do |source, target|
        @depgraph.add_edge(source, target, :callback => :refresh)
      end
    end

    def splice
      @contgraph.splice!(@depgraph)
    end

    def whit_called(name)
      x = @depgraph.vertices.find { |v| v.is_a?(@whit) && v.name =~ /#{Regexp.escape(name)}/ }
      x.should_not be_nil
      def x.to_s
        "Whit[#{name}]"
      end
      def x.inspect
        to_s
      end
      x
    end

    def admissible_sentinal_of(x)
      @depgraph.vertex?(x) ? x : whit_called("admissible_#{x.ref}")
    end

    def completed_sentinal_of(x)
      @depgraph.vertex?(x) ? x : whit_called("completed_#{x.ref}")
    end

    before do
      container_graph
      dependency_graph
      splice
    end

    # This is the real heart of splicing -- replacing all containers X in our
    # relationship graph with a pair of whits { admissible_X and completed_X }
    # such that that
    #
    #    0) completed_X depends on admissible_X
    #    1) contents of X each depend on admissible_X
    #    2) completed_X depends on each on the contents of X
    #    3) everything which depended on X depends on completed_X
    #    4) admissible_X depends on everything X depended on
    #    5) the containers and their edges must be removed
    #
    # Note that this requires attention to the possible case of containers
    # which contain or depend on other containers.
    #
    # Point by point:

    #    0) completed_X depends on admissible_X
    #
    it "every container's completed sentinal should depend on its admissible sentinal" do
      containers.each { |container|
        @depgraph.path_between(admissible_sentinal_of(container),completed_sentinal_of(container)).should be
      }
    end

    #    1) contents of X each depend on admissible_X
    #
    it "all contained objects should depend on their container's admissible sentinal" do
      containers.each { |container|
        contents_of(container).each { |leaf|
          @depgraph.should be_edge(admissible_sentinal_of(container),admissible_sentinal_of(leaf))
        }
      }
    end

    #    2) completed_X depends on each on the contents of X
    #
    it "completed sentinals should depend on their container's contents" do
      containers.each { |container|
        contents_of(container).each { |leaf|
          @depgraph.should be_edge(completed_sentinal_of(leaf),completed_sentinal_of(container))
        }
      }
    end

    #
    #    3) everything which depended on X depends on completed_X

    #
    #    4) admissible_X depends on everything X depended on

    #    5) the containers and their edges must be removed
    #
    it "should remove all Container objects from the dependency graph" do
      @depgraph.vertices.find_all { |v| v.is_a?(Container) }.should be_empty
    end

    it "should remove all Stage resources from the dependency graph" do
      @depgraph.vertices.find_all { |v| v.is_a?(Puppet::Type.type(:stage)) }.should be_empty
    end

    it "should no longer contain anything but the non-container objects" do
      @depgraph.vertices.find_all { |v| ! v.is_a?(String) and ! v.is_a?(@whit)}.should be_empty
    end

    it "should retain labels on non-containment edges" do
      @explicit_dependencies.each { |f,t|
        @depgraph.edges_between(completed_sentinal_of(f),admissible_sentinal_of(t))[0].label.should == {:callback => :refresh}
      }
    end

    it "should not add labels to edges that have none" do
      @depgraph.add_edge(@two, @three)
      splice
      @depgraph.path_between("c", "i").any? {|segment| segment.all? {|e| e.label == {} }}.should be
    end

    it "should copy labels over edges that have none" do
      @depgraph.add_edge("c", @three, {:callback => :refresh})
      splice
      # And make sure the label got copied.
      @depgraph.path_between("c", "i").flatten.select {|e| e.label == {:callback => :refresh} }.should_not be_empty
    end

    it "should not replace a label with a nil label" do
      # Lastly, add some new label-less edges and make sure the label stays.
      @depgraph.add_edge(@middle, @three)
      @depgraph.add_edge("c", @three, {:callback => :refresh})
      splice
      @depgraph.path_between("c","i").flatten.select {|e| e.label == {:callback => :refresh} }.should_not be_empty
    end

    it "should copy labels to all created edges" do
      @depgraph.add_edge(@middle, @three)
      @depgraph.add_edge("c", @three, {:callback => :refresh})
      splice
      @three.each do |child|
        edge = Puppet::Relationship.new("c", child)
        (path = @depgraph.path_between(edge.source, edge.target)).should be
        path.should_not be_empty
        path.flatten.select {|e| e.label == {:callback => :refresh} }.should_not be_empty
      end
    end
  end

  it "should serialize to YAML using the old format by default" do
    Puppet::SimpleGraph.use_new_yaml_format.should == false
  end

  describe "(yaml tests)" do
    def empty_graph(graph)
    end

    def one_vertex_graph(graph)
      graph.add_vertex(:a)
    end

    def graph_without_edges(graph)
      [:a, :b, :c].each { |x| graph.add_vertex(x) }
    end

    def one_edge_graph(graph)
      graph.add_edge(:a, :b)
    end

    def many_edge_graph(graph)
      graph.add_edge(:a, :b)
      graph.add_edge(:a, :c)
      graph.add_edge(:b, :d)
      graph.add_edge(:c, :d)
    end

    def labeled_edge_graph(graph)
      graph.add_edge(:a, :b, :callback => :foo, :event => :bar)
    end

    def overlapping_edge_graph(graph)
      graph.add_edge(:a, :b, :callback => :foo, :event => :bar)
      graph.add_edge(:a, :b, :callback => :biz, :event => :baz)
    end

    def self.all_test_graphs
      [:empty_graph, :one_vertex_graph, :graph_without_edges, :one_edge_graph, :many_edge_graph, :labeled_edge_graph,
       :overlapping_edge_graph]
    end

    def object_ids(enumerable)
      # Return a sorted list of the object id's of the elements of an
      # enumerable.
      enumerable.collect { |x| x.object_id }.sort
    end

    def graph_to_yaml(graph, which_format)
      previous_use_new_yaml_format = Puppet::SimpleGraph.use_new_yaml_format
      Puppet::SimpleGraph.use_new_yaml_format = (which_format == :new)
      ZAML.dump(graph)
    ensure
      Puppet::SimpleGraph.use_new_yaml_format = previous_use_new_yaml_format
    end

    # Test serialization of graph to YAML.
    [:old, :new].each do |which_format|
      all_test_graphs.each do |graph_to_test|
        it "should be able to serialize #{graph_to_test} to YAML (#{which_format} format)" do
          graph = Puppet::SimpleGraph.new
          send(graph_to_test, graph)
          yaml_form = graph_to_yaml(graph, which_format)

          # Hack the YAML so that objects in the Puppet namespace get
          # changed to YAML::DomainType objects.  This lets us inspect
          # the serialized objects easily without invoking any
          # yaml_initialize hooks.
          yaml_form.gsub!('!ruby/object:Puppet::', '!hack/object:Puppet::')
          serialized_object = YAML.load(yaml_form)

          # Check that the object contains instance variables @edges and
          # @vertices only.  @reversal is also permitted, but we don't
          # check it, because it is going to be phased out.
          serialized_object.type_id.should == 'object:Puppet::SimpleGraph'
          serialized_object.value.keys.reject { |x| x == 'reversal' }.sort.should == ['edges', 'vertices']

          # Check edges by forming a set of tuples (source, target,
          # callback, event) based on the graph and the YAML and make sure
          # they match.
          edges = serialized_object.value['edges']
          edges.should be_a(Array)
          expected_edge_tuples = graph.edges.collect { |edge| [edge.source, edge.target, edge.callback, edge.event] }
          actual_edge_tuples = edges.collect do |edge|
            edge.type_id.should == 'object:Puppet::Relationship'
            %w{source target}.each { |x| edge.value.keys.should include(x) }
            edge.value.keys.each { |x| ['source', 'target', 'callback', 'event'].should include(x) }
            %w{source target callback event}.collect { |x| edge.value[x] }
          end
          Set.new(actual_edge_tuples).should == Set.new(expected_edge_tuples)
          actual_edge_tuples.length.should == expected_edge_tuples.length

          # Check vertices one by one.
          vertices = serialized_object.value['vertices']
          if which_format == :old
            vertices.should be_a(Hash)
            Set.new(vertices.keys).should == Set.new(graph.vertices)
            vertices.each do |key, value|
              value.type_id.should == 'object:Puppet::SimpleGraph::VertexWrapper'
              value.value.keys.sort.should == %w{adjacencies vertex}
              value.value['vertex'].should equal(key)
              adjacencies = value.value['adjacencies']
              adjacencies.should be_a(Hash)
              Set.new(adjacencies.keys).should == Set.new([:in, :out])
              [:in, :out].each do |direction|
                adjacencies[direction].should be_a(Hash)
                expected_adjacent_vertices = Set.new(graph.adjacent(key, :direction => direction, :type => :vertices))
                Set.new(adjacencies[direction].keys).should == expected_adjacent_vertices
                adjacencies[direction].each do |adj_key, adj_value|
                  # Since we already checked edges, just check consistency
                  # with edges.
                  desired_source = direction == :in ? adj_key : key
                  desired_target = direction == :in ? key : adj_key
                  expected_edges = edges.select do |edge|
                    edge.value['source'] == desired_source && edge.value['target'] == desired_target
                  end
                  adj_value.should be_a(Set)
                  if object_ids(adj_value) != object_ids(expected_edges)
                    raise "For vertex #{key.inspect}, direction #{direction.inspect}: expected adjacencies #{expected_edges.inspect} but got #{adj_value.inspect}"
                  end
                end
              end
            end
          else
            vertices.should be_a(Array)
            Set.new(vertices).should == Set.new(graph.vertices)
            vertices.length.should == graph.vertices.length
          end
        end
      end

      # Test deserialization of graph from YAML.  This presumes the
      # correctness of serialization to YAML, which has already been
      # tested.
      all_test_graphs.each do |graph_to_test|
        it "should be able to deserialize #{graph_to_test} from YAML (#{which_format} format)" do
          reference_graph = Puppet::SimpleGraph.new
          send(graph_to_test, reference_graph)
          yaml_form = graph_to_yaml(reference_graph, which_format)
          recovered_graph = YAML.load(yaml_form)

          # Test that the recovered vertices match the vertices in the
          # reference graph.
          expected_vertices = reference_graph.vertices.to_a
          recovered_vertices = recovered_graph.vertices.to_a
          Set.new(recovered_vertices).should == Set.new(expected_vertices)
          recovered_vertices.length.should == expected_vertices.length

          # Test that the recovered edges match the edges in the
          # reference graph.
          expected_edge_tuples = reference_graph.edges.collect do |edge|
            [edge.source, edge.target, edge.callback, edge.event]
          end
          recovered_edge_tuples = recovered_graph.edges.collect do |edge|
            [edge.source, edge.target, edge.callback, edge.event]
          end
          Set.new(recovered_edge_tuples).should == Set.new(expected_edge_tuples)
          recovered_edge_tuples.length.should == expected_edge_tuples.length

          # We ought to test that the recovered graph is self-consistent
          # too.  But we're not going to bother with that yet because
          # the internal representation of the graph is about to change.
        end
      end

      it "should be able to serialize a graph where the vertices contain backreferences to the graph (#{which_format} format)" do
        reference_graph = Puppet::SimpleGraph.new
        vertex = Object.new
        vertex.instance_eval { @graph = reference_graph }
        reference_graph.add_edge(vertex, :other_vertex)
        yaml_form = graph_to_yaml(reference_graph, which_format)
        recovered_graph = YAML.load(yaml_form)

        recovered_graph.vertices.length.should == 2
        recovered_vertex = recovered_graph.vertices.reject { |x| x.is_a?(Symbol) }[0]
        recovered_vertex.instance_eval { @graph }.should equal(recovered_graph)
        recovered_graph.edges.length.should == 1
        recovered_edge = recovered_graph.edges[0]
        recovered_edge.source.should equal(recovered_vertex)
        recovered_edge.target.should == :other_vertex
      end
    end

    it "should serialize properly when used as a base class" do
      class Puppet::TestDerivedClass < Puppet::SimpleGraph
        attr_accessor :foo
      end
      derived = Puppet::TestDerivedClass.new
      derived.add_edge(:a, :b)
      derived.foo = 1234
      recovered_derived = YAML.load(YAML.dump(derived))
      recovered_derived.class.should equal(Puppet::TestDerivedClass)
      recovered_derived.edges.length.should == 1
      recovered_derived.edges[0].source.should == :a
      recovered_derived.edges[0].target.should == :b
      recovered_derived.vertices.length.should == 2
      recovered_derived.foo.should == 1234
    end
  end
end