Per-container deep merge caching

Replaces the one-big top level deep merge cache with individual deep
merge caches in every container.  The Immutable container state becomes
the deep merge cache.

- Does not use a pure decorator style approach since that failed before
because of ruby internals breaking things like `===` and `=~` on
decorated objects, so we inherit (ultimately from Hash + Array).
- The state being the container state is useful in ruby since APIs on
Hash and Array poke around in internal state to make things fast.  If
we inherit from Hash/Array but don't have the correct internal state
things go wonky.
- Throwing away the internal state is equivalent to flushing the cache.
- Since we throw away all linked objects when we do that, we flush at
every level below the level being flushed (which is correct semantics).
- If a user has a pointer to an old immutable object from a sub-level,
that isn't mutated so the old object still contains the old view of
the data (which I think is correct, although I have some doubts that
its necessary, but it came along free for the ride).
- When we reset the cache we do mutate the cache being reset, which
might change data in held references.  If this becomes an issue the fix would
be to reset the cache at the level above by creating a new, "empty"
ImmutableHash/ImmutableArray object and inserting it into the
deep_merge_cache datastructure instead of clearing the internal state
of the child object.  I don't know practically how anyone would hit
this, though, so would prefer to wait on doing that work until we see
an actual bug report.
- Because of the way ruby pokes around internally there's some
weirdnesses like the pre-generation of the cache for all the values of
a subarray when #each is called, which is due to the way that ruby
walks through array-serialized hashes when called like:
`Array#each { key, value| ... }` (which is an undocumented(?) thing
in ruby).

Signed-off-by: Lamont Granquist <lamont@scriptkiddie.org>

3 files changed, 111 insertions, 47 deletions

diff --git a/spec/unit/node/attribute_spec.rb b/spec/unit/node/attribute_spec.rb
index cf8d4d4a4f..90b3f1fe51 100644
--- a/spec/unit/node/attribute_spec.rb
+++ b/spec/unit/node/attribute_spec.rb
@@ -171,6 +171,7 @@ describe Chef::Node::Attribute do
     }
     @automatic_hash = { "week" => "friday" }
     @attributes = Chef::Node::Attribute.new(@attribute_hash, @default_hash, @override_hash, @automatic_hash, node)
+    allow(node).to receive(:attributes).and_return(@attributes)
   end
 
   describe "initialize" do
@@ -179,13 +180,14 @@ describe Chef::Node::Attribute do
     end
 
     it "should take an Automatioc, Normal, Default and Override hash" do
-      expect { Chef::Node::Attribute.new({}, {}, {}, {}) }.not_to raise_error
+      expect { Chef::Node::Attribute.new({}, {}, {}, {}, node) }.not_to raise_error
     end
 
     [ :normal, :default, :override, :automatic ].each do |accessor|
       it "should set #{accessor}" do
-        na = Chef::Node::Attribute.new({ :normal => true }, { :default => true }, { :override => true }, { :automatic => true })
-        expect(na.send(accessor)).to eq({ accessor.to_s => true })
+        @attributes = Chef::Node::Attribute.new({ :normal => true }, { :default => true }, { :override => true }, { :automatic => true }, node)
+        allow(node).to receive(:attributes).and_return(@attributes)
+        expect(@attributes.send(accessor)).to eq({ accessor.to_s => true })
       end
     end
 
@@ -330,7 +332,8 @@ describe Chef::Node::Attribute do
     end
 
     it "merges nested hashes between precedence levels" do
-      @attributes = Chef::Node::Attribute.new({}, {}, {}, {})
+      @attributes = Chef::Node::Attribute.new({}, {}, {}, {}, node)
+      allow(node).to receive(:attributes).and_return(@attributes)
       @attributes.env_default = { "a" => { "b" => { "default" => "default" } } }
       @attributes.normal = { "a" => { "b" => { "normal" => "normal" } } }
       @attributes.override = { "a" => { "override" => "role" } }
@@ -584,8 +587,10 @@ describe Chef::Node::Attribute do
           "one" => { "six" => "seven" },
           "snack" => "cookies",
         },
-        {}
+        {},
+        node
       )
+      allow(node).to receive(:attributes).and_return(@attributes)
     end
 
     it "should yield each top level key" do
@@ -632,8 +637,10 @@ describe Chef::Node::Attribute do
           "one" => "six",
           "snack" => "cookies",
         },
-        {}
+        {},
+        node
       )
+      allow(node).to receive(:attributes).and_return(@attributes)
     end
 
     it "should yield each top level key and value, post merge rules" do
@@ -670,8 +677,10 @@ describe Chef::Node::Attribute do
           "one" => "six",
           "snack" => "cookies",
         },
-        {}
+        {},
+        node
       )
+      allow(node).to receive(:attributes).and_return(@attributes)
     end
 
     it "should respond to each_key" do
@@ -706,8 +715,10 @@ describe Chef::Node::Attribute do
           "one" => "six",
           "snack" => "cookies",
         },
-        {}
+        {},
+        node
       )
+      allow(node).to receive(:attributes).and_return(@attributes)
     end
 
     it "should respond to each_pair" do
@@ -742,8 +753,10 @@ describe Chef::Node::Attribute do
           "one" => "six",
           "snack" => "cookies",
         },
-        {}
+        {},
+        node
       )
+      allow(node).to receive(:attributes).and_return(@attributes)
     end
 
     it "should respond to each_value" do
@@ -786,9 +799,10 @@ describe Chef::Node::Attribute do
           "one" => "six",
           "snack" => "cookies",
         },
-        {}
+        {},
+        node
       )
-      @empty = Chef::Node::Attribute.new({}, {}, {}, {})
+      allow(node).to receive(:attributes).and_return(@attributes)
     end
 
     it "should respond to empty?" do
@@ -796,7 +810,9 @@ describe Chef::Node::Attribute do
     end
 
     it "should return true when there are no keys" do
-      expect(@empty.empty?).to eq(true)
+      @attributes = Chef::Node::Attribute.new({}, {}, {}, {}, node)
+      allow(node).to receive(:attributes).and_return(@attributes)
+      expect(@attributes.empty?).to eq(true)
     end
 
     it "should return false when there are keys" do
@@ -820,8 +836,10 @@ describe Chef::Node::Attribute do
           "one" => "six",
           "snack" => "cookies",
         },
-        {}
+        {},
+        node
       )
+      allow(node).to receive(:attributes).and_return(@attributes)
     end
 
     it "should respond to fetch" do
@@ -877,8 +895,10 @@ describe Chef::Node::Attribute do
           "one" => "six",
           "snack" => "cookies",
         },
-        {}
+        {},
+        node
       )
+      allow(node).to receive(:attributes).and_return(@attributes)
     end
 
     it "should respond to has_value?" do
@@ -922,8 +942,10 @@ describe Chef::Node::Attribute do
           "one" => "six",
           "snack" => "cookies",
         },
-        {}
+        {},
+        node
       )
+      allow(node).to receive(:attributes).and_return(@attributes)
     end
 
     it "should respond to index" do
@@ -963,8 +985,10 @@ describe Chef::Node::Attribute do
           "one" => "six",
           "snack" => "cookies",
         },
-        {}
+        {},
+        node
       )
+      allow(node).to receive(:attributes).and_return(@attributes)
     end
 
     it "should respond to values" do
@@ -999,8 +1023,10 @@ describe Chef::Node::Attribute do
           "one" => "six",
           "snack" => "cookies",
         },
-        {}
+        {},
+        node
       )
+      allow(node).to receive(:attributes).and_return(@attributes)
     end
 
     it "should respond to select" do
@@ -1049,10 +1075,11 @@ describe Chef::Node::Attribute do
           "one" => "six",
           "snack" => "cookies",
         },
-        {}
+        {},
+        node
       )
+      allow(node).to receive(:attributes).and_return(@attributes)
 
-      @empty = Chef::Node::Attribute.new({}, {}, {}, {})
     end
 
     it "should respond to size" do
@@ -1064,7 +1091,9 @@ describe Chef::Node::Attribute do
     end
 
     it "should return 0 for an empty attribute" do
-      expect(@empty.size).to eq(0)
+      @attributes = Chef::Node::Attribute.new({}, {}, {}, {}, node)
+      allow(node).to receive(:attributes).and_return(@attributes)
+      expect(@attributes.size).to eq(0)
     end
 
     it "should return the number of pairs" do
@@ -1092,8 +1121,9 @@ describe Chef::Node::Attribute do
 
   describe "to_s" do
     it "should output simple attributes" do
-      attributes = Chef::Node::Attribute.new(nil, nil, nil, nil)
-      expect(attributes.to_s).to eq("{}")
+      @attributes = Chef::Node::Attribute.new(nil, nil, nil, nil, node)
+      allow(node).to receive(:attributes).and_return(@attributes)
+      expect(@attributes.to_s).to eq("{}")
     end
 
     it "should output merged attributes" do
@@ -1105,8 +1135,9 @@ describe Chef::Node::Attribute do
           "b" => 3,
           "c" => 4,
       }
-      attributes = Chef::Node::Attribute.new(nil, default_hash, override_hash, nil)
-      expect(attributes.to_s).to eq('{"a"=>1, "b"=>3, "c"=>4}')
+      @attributes = Chef::Node::Attribute.new(nil, default_hash, override_hash, nil, node)
+      allow(node).to receive(:attributes).and_return(@attributes)
+      expect(@attributes.to_s).to eq('{"b"=>3, "c"=>4, "a"=>1}')
     end
   end
 
diff --git a/spec/unit/node/immutable_collections_spec.rb b/spec/unit/node/immutable_collections_spec.rb
index 2d3392041c..c8e664a652 100644
--- a/spec/unit/node/immutable_collections_spec.rb
+++ b/spec/unit/node/immutable_collections_spec.rb
@@ -20,13 +20,18 @@ require "spec_helper"
 require "chef/node/immutable_collections"
 
 describe Chef::Node::ImmutableMash do
+
   before do
-    @data_in = { "top" => { "second_level" => "some value" },
-                 "top_level_2" => %w{array of values},
-                 "top_level_3" => [{ "hash_array" => 1, "hash_array_b" => 2 }],
-                 "top_level_4" => { "level2" => { "key" => "value" } },
+    @data_in = { "key" =>
+                 { "top" => { "second_level" => "some value" },
+                   "top_level_2" => %w{array of values},
+                   "top_level_3" => [{ "hash_array" => 1, "hash_array_b" => 2 }],
+                   "top_level_4" => { "level2" => { "key" => "value" } },
+                 },
     }
-    @immutable_mash = Chef::Node::ImmutableMash.new(@data_in)
+    @node = Chef::Node.new()
+    @node.attributes.default = @data_in
+    @immutable_mash = @node["key"]
   end
 
   it "element references like regular hash" do
@@ -57,9 +62,9 @@ describe Chef::Node::ImmutableMash do
   # we only ever absorb VividMashes from other precedence levels, which already have
   # been coerced to only have string keys, so we do not need to do that work twice (performance).
   it "does not call convert_value like Mash/VividMash" do
-    @mash = Chef::Node::ImmutableMash.new({ test: "foo", "test2" => "bar" })
-    expect(@mash[:test]).to eql("foo")
-    expect(@mash["test2"]).to eql("bar")
+    @node.attributes.default = { test: "foo", "test2" => "bar" }
+    expect(@node[:test]).to eql("foo")
+    expect(@node["test2"]).to eql("bar")
   end
 
   describe "to_hash" do
@@ -80,7 +85,9 @@ describe Chef::Node::ImmutableMash do
     end
 
     it "should create a mash with the same content" do
-      expect(@copy).to eq(@immutable_mash)
+      puts @copy.class
+      puts @immutable_mash.class
+      expect(@immutable_mash).to eq(@copy)
     end
 
     it "should allow mutation" do
@@ -175,9 +182,11 @@ end
 describe Chef::Node::ImmutableArray do
 
   before do
-    @immutable_array = Chef::Node::ImmutableArray.new(%w{foo bar baz} + Array(1..3) + [nil, true, false, [ "el", 0, nil ] ])
-    immutable_mash = Chef::Node::ImmutableMash.new({ "m" => "m" })
-    @immutable_nested_array = Chef::Node::ImmutableArray.new(["level1", @immutable_array, immutable_mash])
+    @node = Chef::Node.new()
+    @node.attributes.default = { "key" => ["level1", %w{foo bar baz} + Array(1..3) + [nil, true, false, [ "el", 0, nil ] ], { "m" => "m" }] }
+    @immutable_array = @node["key"][1]
+    @immutable_mash = @node["key"][2]
+    @immutable_nested_array = @node["key"]
   end
 
   ##
@@ -249,7 +258,7 @@ describe Chef::Node::ImmutableArray do
     end
 
     it "should create an array with the same content" do
-      expect(@copy).to eq(@immutable_nested_array)
+      expect(@immutable_nested_array).to eq(@copy)
     end
 
     it "should allow mutation" do
@@ -314,4 +323,11 @@ describe Chef::Node::ImmutableArray do
       expect(@immutable_array[1, 2]).to eql(%w{bar baz})
     end
   end
+
+  describe "uniq" do
+    it "works" do
+      @node.attributes.default = { "key" => %w{foo bar foo baz bar} }
+      expect(@node["key"].uniq).to eql(%w{foo bar baz})
+    end
+  end
 end
diff --git a/spec/unit/node/vivid_mash_spec.rb b/spec/unit/node/vivid_mash_spec.rb
index 4898c22380..651cfa0058 100644
--- a/spec/unit/node/vivid_mash_spec.rb
+++ b/spec/unit/node/vivid_mash_spec.rb
@@ -1,5 +1,5 @@
 #
-# Copyright:: Copyright 2016, Chef Software Inc.
+# Copyright:: Copyright 2016-2017, Chef Software Inc.
 # License:: Apache License, Version 2.0
 #
 # Licensed under the Apache License, Version 2.0 (the "License");
@@ -60,7 +60,7 @@ describe Chef::Node::VividMash do
     end
 
     it "deep converts values through arrays" do
-      expect(root).to receive(:reset_cache).with("foo")
+      expect(root).to receive(:reset_cache).with(no_args)
       vivid["foo"] = [ { :bar => true } ]
       expect(vivid["foo"].class).to eql(Chef::Node::AttrArray)
       expect(vivid["foo"][0].class).to eql(Chef::Node::VividMash)
@@ -68,7 +68,7 @@ describe Chef::Node::VividMash do
     end
 
     it "deep converts values through nested arrays" do
-      expect(root).to receive(:reset_cache).with("foo")
+      expect(root).to receive(:reset_cache).with(no_args)
       vivid["foo"] = [ [ { :bar => true } ] ]
       expect(vivid["foo"].class).to eql(Chef::Node::AttrArray)
       expect(vivid["foo"][0].class).to eql(Chef::Node::AttrArray)
@@ -77,7 +77,7 @@ describe Chef::Node::VividMash do
     end
 
     it "deep converts values through hashes" do
-      expect(root).to receive(:reset_cache).with("foo")
+      expect(root).to receive(:reset_cache).with(no_args)
       vivid["foo"] = { baz: { :bar => true } }
       expect(vivid["foo"]).to be_an_instance_of(Chef::Node::VividMash)
       expect(vivid["foo"]["baz"]).to be_an_instance_of(Chef::Node::VividMash)
@@ -184,42 +184,55 @@ describe Chef::Node::VividMash do
 
     it "should deeply autovivify" do
       expect(root).to receive(:reset_cache).at_least(:once).with("one")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "five")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "five", "six")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "five", "six", "seven")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "five", "six", "seven", "eight")
       vivid.write("one", "five", "six", "seven", "eight", "nine", "ten")
       expect(vivid["one"]["five"]["six"]["seven"]["eight"]["nine"]).to eql("ten")
     end
 
     it "should raise an exception if you overwrite an array with a hash" do
+      expect(root).to receive(:reset_cache).at_least(:once).with(no_args)
       expect(root).to receive(:reset_cache).at_least(:once).with("array")
       vivid.write("array", "five", "six")
       expect(vivid).to eql({ "one" => { "two" => { "three" => "four" } }, "array" => { "five" => "six" }, "nil" => nil })
     end
 
     it "should raise an exception if you traverse through an array with a hash" do
+      expect(root).to receive(:reset_cache).at_least(:once).with(no_args)
       expect(root).to receive(:reset_cache).at_least(:once).with("array")
+      expect(root).to receive(:reset_cache).at_least(:once).with("array", "five")
       vivid.write("array", "five", "six", "seven")
       expect(vivid).to eql({ "one" => { "two" => { "three" => "four" } }, "array" => { "five" => { "six" => "seven" } }, "nil" => nil })
     end
 
     it "should raise an exception if you overwrite a string with a hash" do
-      expect(root).to receive(:reset_cache).at_least(:once).with("one")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "two")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "two", "three")
       vivid.write("one", "two", "three", "four", "five")
       expect(vivid).to eql({ "one" => { "two" => { "three" => { "four" => "five" } } }, "array" => [ 0, 1, 2 ], "nil" => nil })
     end
 
     it "should raise an exception if you traverse through a string with a hash" do
-      expect(root).to receive(:reset_cache).at_least(:once).with("one")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "two")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "two", "three")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "two", "three", "four")
       vivid.write("one", "two", "three", "four", "five", "six")
       expect(vivid).to eql({ "one" => { "two" => { "three" => { "four" => { "five" => "six" } } } }, "array" => [ 0, 1, 2 ], "nil" => nil })
     end
 
     it "should raise an exception if you overwrite a nil with a hash" do
+      expect(root).to receive(:reset_cache).at_least(:once).with(no_args)
       expect(root).to receive(:reset_cache).at_least(:once).with("nil")
       vivid.write("nil", "one", "two")
       expect(vivid).to eql({ "one" => { "two" => { "three" => "four" } }, "array" => [ 0, 1, 2 ], "nil" => { "one" => "two" } })
     end
 
     it "should raise an exception if you traverse through a nil with a hash" do
+      expect(root).to receive(:reset_cache).at_least(:once).with(no_args)
       expect(root).to receive(:reset_cache).at_least(:once).with("nil")
+      expect(root).to receive(:reset_cache).at_least(:once).with("nil", "one")
       vivid.write("nil", "one", "two", "three")
       expect(vivid).to eql({ "one" => { "two" => { "three" => "four" } }, "array" => [ 0, 1, 2 ], "nil" => { "one" => { "two" => "three" } } })
     end
@@ -240,6 +253,10 @@ describe Chef::Node::VividMash do
 
     it "should deeply autovivify" do
       expect(root).to receive(:reset_cache).at_least(:once).with("one")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "five")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "five", "six")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "five", "six", "seven")
+      expect(root).to receive(:reset_cache).at_least(:once).with("one", "five", "six", "seven", "eight")
       vivid.write!("one", "five", "six", "seven", "eight", "nine", "ten")
       expect(vivid["one"]["five"]["six"]["seven"]["eight"]["nine"]).to eql("ten")
     end
@@ -295,7 +312,7 @@ describe Chef::Node::VividMash do
     end
 
     it "should unlink hashes" do
-      expect(root).to receive(:reset_cache).at_least(:once).with("one")
+      expect(root).to receive(:reset_cache).at_least(:once).with(no_args)
       expect( vivid.unlink("one") ).to eql({ "two" => { "three" => "four" } })
       expect(vivid).to eql({ "array" => [ 0, 1, 2 ], "nil" => nil })
     end
@@ -307,7 +324,7 @@ describe Chef::Node::VividMash do
     end
 
     it "should unlink nil" do
-      expect(root).to receive(:reset_cache).at_least(:once).with("nil")
+      expect(root).to receive(:reset_cache).at_least(:once).with(no_args)
       expect(vivid.unlink("nil")).to eql(nil)
       expect(vivid).to eql({ "one" => { "two" => { "three" => "four" } }, "array" => [ 0, 1, 2 ] })
     end
@@ -327,7 +344,7 @@ describe Chef::Node::VividMash do
     end
 
     it "should unlink! hashes" do
-      expect(root).to receive(:reset_cache).at_least(:once).with("one")
+      expect(root).to receive(:reset_cache).at_least(:once).with(no_args)
       expect( vivid.unlink!("one") ).to eql({ "two" => { "three" => "four" } })
       expect(vivid).to eql({ "array" => [ 0, 1, 2 ], "nil" => nil })
     end
@@ -339,7 +356,7 @@ describe Chef::Node::VividMash do
     end
 
     it "should unlink! nil" do
-      expect(root).to receive(:reset_cache).at_least(:once).with("nil")
+      expect(root).to receive(:reset_cache).at_least(:once).with(no_args)
       expect(vivid.unlink!("nil")).to eql(nil)
       expect(vivid).to eql({ "one" => { "two" => { "three" => "four" } }, "array" => [ 0, 1, 2 ] })
     end