# # Copyright (c) 2012 RightScale Inc # # Permission is hereby granted, free of charge, to any person obtaining # a copy of this software and associated documentation files (the # "Software"), to deal in the Software without restriction, including # without limitation the rights to use, copy, modify, merge, publish, # distribute, sublicense, and/or sell copies of the Software, and to # permit persons to whom the Software is furnished to do so, subject to # the following conditions: # # The above copyright notice and this permission notice shall be # included in all copies or substantial portions of the Software. # # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE # LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION # OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION # WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. module RightSupport::Data # various tools for manipulating hash-like classes. module HashTools # require checks HAS_JSON = require_succeeds?('json') # exceptions class NoJson < ::StandardError; end # Determines if given object is hashable (i.e. object responds to hash methods). # # === Parameters # @param [Object] object to be tested # # === Return # @return [TrueClass|FalseClass] true if object is hashable, false otherwise def self.hashable?(object) # note that we could obviously be more critical here, but this test has always been # sufficient and excludes Arrays and Strings which respond to [] but not has_key? # # what we specifically don't want to do is .kind_of?(Hash) because that excludes the # range of hash-like classes (such as Chef::Node::Attribute) object.respond_to?(:has_key?) end # Determines if given class is hash-like (i.e. instance of class responds to hash methods). # # === Parameters # @param [Class] clazz to be tested # # === Return # @return [TrueClass|FalseClass] true if clazz is hash-like, false otherwise def self.hash_like?(clazz) clazz.public_method_defined?('has_key?') end # Gets a value from a (deep) hash using a path given as an array of keys. # # === Parameters # @param [Hash] hash for lookup or nil or empty # @param [Array] path to existing value as array of keys or nil or empty # # === Return # @return [Object] value or nil def self.deep_get(hash, path) hash ||= {} path ||= [] last_index = path.size - 1 path.each_with_index do |key, index| value = hash[key] if index == last_index return value elsif hashable?(value) hash = value else break end end nil end # Set a given value on a (deep) hash using a path given as an array of keys. # # === Parameters # @param [Hash] hash for insertion # @param [Array] path to new value as array of keys # @param [Object] value to insert # @param [Class] clazz to allocate as needed when building deep hash or nil to infer from hash argument # # === Return # @return [TrueClass] always true def self.deep_set!(hash, path, value, clazz=nil) raise ArgumentError.new("hash is invalid") unless hashable?(hash) raise ArgumentError.new("path is invalid") if path.empty? clazz ||= hash.class raise ArgumentError.new("clazz is invalid") unless hash_like?(clazz) last_index = path.size - 1 path.each_with_index do |key, index| if index == last_index hash[key] = value else subhash = hash[key] unless hashable?(subhash) subhash = clazz.new hash[key] = subhash end hash = subhash end end true end # Creates a deep clone of the given hash. # # @deprecated in favor of more robust deep_clone2 # # note that not all objects are clonable in Ruby even though all respond to clone # (which is completely counter-intuitive and contrary to all other managed languages). # Java, for example, has the built-in Cloneable marker interface which we will simulate # here with .duplicable? (because cloneable isn't actually a word) in case you need # non-hash values to be deep-cloned by this method. # # also note that .duplicable? may imply caling .dup instead of .clone but developers tend # to override .clone and totally forget to override .dup (and having two names for the # same method is, yes, a bad idea in any language). # # === Parameters # @param [Hash] original hash to clone # # === Block # @yieldparam [Object] value of leaf # @yieldreturn [Object] cloned value of leaf or original value # # === Return # @return [Hash] deep cloned hash def self.deep_clone(original, &leaf_callback) # note that .clone preserves .frozen? state so this legacy method will # attempt to modify a still-frozen hash/array and raise an exception. # see deep_clone2 which clones by creating a new instance of the object # class and produce an unfrozen clone of the hash/array. # as a side note, calling .dup does not preserve .frozen? state but is has # its own side effects, which is why we have more specific logic like # leaf_callback and .duplicable? result = original.clone result.each do |k, v| if hashable?(v) # HACK: we should have passed &leaf_callback here but never did before # so it is techincally a bug. we are not going to change it due to not # wanting to break legacy code so use deep_clone2 instead. result[k] = deep_clone(v) elsif leaf_callback result[k] = leaf_callback.call(v) elsif v.respond_to?(:duplicable?) result[k] = (v.duplicable? ? v.clone : v) else result[k] = v end end result end # Deeply duplicates (clones) a hashable object containing other hashes or # arrays of hashes but passing other types through. # # Optionally changes the target hashable type to 'normalize' to a specific # hashable class (such as Mash). # # Optionally traverses arrays (default) in an attempt to deep-clone any # sub-hashes instead of simply associating them. # # === Parameters # @param [Object] any kind of object # @param [Hash] options # @option [Class] :class for cloned hashables or nil for same as source # # === Block # @yieldparam [Object] value of leaf # @yieldreturn [Object] cloned value of leaf or original value # # === Return # @return [Object] depends on input type def self.deep_clone2(any, options = {}, &leaf_callback) if hashable?(any) # clone to a new instance of hashable class with deep cloning. any.inject((options[:class] || any.class).new) do |m, (k, v)| m[k] = deep_clone2(v, options, &leaf_callback) m end elsif any.kind_of?(::Array) # traverse arrays any.map { |e| deep_clone2(e, options, &leaf_callback) } elsif leaf_callback leaf_callback.call(any) elsif any.respond_to?(:duplicable?) # see #deep_clone for remarks any.duplicable? ? any.clone : any else any # whatever end end # Deeply freezes the given hash/array and all of their non-hierarchical # elements in a hierarchichal data structure such that an attempt to modify # any part of it will raise an exception. # # === Parameters # @param [Object] any kind of object # # === Return # @return [Object] deeply frozen object def self.deep_freeze!(any) if hashable?(any) # clone to a new instance of hashable class with deep cloning. any.each do |k, v| # notes: # a) either key or value of a hash could be a complex type. # b) Hash freezes simple type keys upon insertion out of necessity to # avoid spontaneous rehashing. Hash will not freeze complex types # used as keys so we will (re)freeze all keys for safety. deep_freeze!(k) deep_freeze!(v) end elsif any.kind_of?(::Array) # traverse arrays any.each { |e| deep_freeze!(e) } end any.freeze end # Deeply mashes and duplicates (clones) a hashable using deep_clone2 and our # own version of Mash. # # The advantage of Mash over Hash is, of course, to be able to use either # a String or Symbol as a key for the same value. # # Note that Mash.new(my_mash) will convert child hashes to mashes but not # with the guarantee of cloning and detaching the deep mash. In other words. # if any part of the hash is already a mash then it is not cloned by # invoking Mash.new() # # === Parameters # @param [Object] any kind of object # # === Block # @yieldparam [Object] value of leaf # @yieldreturn [Object] cloned value of leaf or original value # # === Return # @return [Object] depends on input type def self.deep_mash(any, &leaf_callback) options = { :class => RightSupport::Data::Mash } deep_clone2(any, options, &leaf_callback) end # Performs a deep clone and merge of one hash into another, similar in # behavior to Hash#merge # # === Parameters # @param [Hash] target hash containing original data to be replaced in the # resulting hash # @param [Hash] source hash containing data to recursively assign or nil or # empty # # === Return # @return [Hash] to_hash result of merge def self.deep_merge(target, source) # merge or replace any values that appear in source. result = target.class.new (source || {}).each do |k, v| if hashable?(target[k]) && hashable?(v) result[k] = deep_merge(target[k], v) else result[k] = v end end # deep clone any target-only value. target.each do |k, v| unless result.has_key?(k) result[k] = deep_clone2(v) end end result end # Performs a deep merge (but not a deep clone) of one hash into another, # similar in behavior to Hash#merge! # # === Parameters # @param [Hash] target hash to contain original and merged data # @param [Hash] source hash containing data to recursively assign or nil or empty # # === Return # @return [Hash] to_hash result of merge def self.deep_merge!(target, source) source.each do |k, v| if hashable?(target[k]) && hashable?(v) deep_merge!(target[k], v) else target[k] = v end end if source target end # Remove recursively values that exist equivalently in the match hash. # # === Parameters # @param [Hash] target hash from which to remove matching values # @param [Hash] source hash to compare against target for removal or nil or empty # # === Return # @return [Hash] target hash with matching values removed, if any def self.deep_remove!(target, source) source.each do |k, v| if target.has_key?(k) if target[k] == v target.delete(k) elsif hashable?(v) && hashable?(target[k]) deep_remove!(target[k], v) end end end if source target end # Produce a difference from two hashes. The difference excludes any values which are # common to both hashes. # # The result is a hash with the following keys: # - :diff = hash with key common to both input hashes and value composed of the corresponding different values: { :left => , :right => } # - :left_only = hash composed of items only found in left hash # - :right_only = hash composed of items only found in right hash # # === Parameters # @param [Hash] left side # @param [Hash] right side # # === Return # @return [Hash] result as hash of diffage def self.deep_create_patch(left, right) result = { :diff=>{}, :left_only=>{}, :right_only=>{} } right.each do |k, v| if left.include?(k) if hashable?(v) && hashable?(left[k]) subdiff = deep_create_patch(left[k], v) result[:right_only].merge!(k=>subdiff[:right_only]) unless subdiff[:right_only].empty? result[:left_only].merge!(k=>subdiff[:left_only]) unless subdiff[:left_only].empty? result[:diff].merge!(k=>subdiff[:diff]) unless subdiff[:diff].empty? elsif v != left[k] result[:diff].merge!(k=>{:left => left[k], :right=>v}) end else result[:right_only].merge!({ k => v }) end end left.each { |k, v| result[:left_only].merge!({ k => v }) unless right.include?(k) } result end # Perform 3-way merge using given target and a patch hash (generated by deep_create_patch, etc.). # values in target whose keys are in :left_only component of patch are removed # values in :right_only component of patch get deep merged into target # values in target whose keys are in :diff component of patch and which are identical to left # side of diff get overwritten with right side of patch # # === Parameters # @param [Hash] target hash where patch will be applied. # @param [Hash] patch hash containing changes to apply. # # === Return # @param [Hash] target hash with patch applied. def self.deep_apply_patch!(target, patch) deep_remove!(target, patch[:left_only]) deep_merge!(target, patch[:right_only]) deep_apply_diff!(target, patch[:diff]) target end # Recursively apply diff portion of a patch (generated by deep_create_patch, etc.). # # === Parameters # @param [Hash] target hash where diff will be applied. # @param [Hash] diff hash containing changes to apply. # # === Return # @param [Hash] target hash with diff applied. def self.deep_apply_diff!(target, diff) diff.each do |k, v| if v[:left] && v[:right] target[k] = v[:right] if v[:left] == target[k] elsif target.has_key?(k) deep_apply_diff!(target[k], v) end end target end class DeepSortedJsonState # Initializer. # # === Parameters # @param [TrueClass|FalseClass] pretty is true to invoke JSON::pretty_generate, false to call JSON::dump def initialize(pretty) # copy one of the JSON state prototypes in order to agree with recursive # depth and other state variables. @state = (pretty ? JSON::PRETTY_STATE_PROTOTYPE : JSON::FAST_STATE_PROTOTYPE).dup # note that the native JSON extension *may* keep the following state # strings as internal ruby strings in which case the state accessor (i.e. # state.object_nl) returns a pointer to a char array instead of a String # object. the trivial solution is to hardcode the 'pretty' strings here # instead of trying to infer the proper string objects. if pretty @object_nl = "\n" @indent = ' ' @space = ' ' else @object_nl = '' @indent = '' @space = '' end end # Generates a JSONified hash string where key/value pairs are sorted by # the stringified key. # # Note that this algoritm is loosely based on the json_pure implementation # for Hash. # # === Parameters # @param [Hash] hash from which to generate JSON # # === Return # @return [String] result as sorted JSONified hash def generate(hash) delim = ',' delim << @object_nl result = '{' result << @object_nl depth = @state.depth += 1 first = true sorted_pairs = hash.to_a.map { |key, value| [key.to_s, value] }.sort sorted_pairs.each do |key, value| result << delim unless first result << @indent * depth result << key.to_s.to_json(@state) result << ':' result << @space if ::RightSupport::Data::HashTools.hashable?(value) result << generate(value) else result << value.to_json(@state) end first = false end depth = @state.depth -= 1 result << @object_nl result << @indent * depth result << '}' result end end # Generates JSON from the given hash (of hashes) that is sorted by key at # all levels. Does not handle case of hash to array of hashes, etc. # # === Parameters # @param [Hash] hash from which to generate JSON # @param [TrueClass|FalseClass] pretty is true to invoke JSON::pretty_generate, false to call JSON::dump # # === Return # @return [String] result as a deep-sorted JSONized hash def self.deep_sorted_json(hash, pretty=false) if HAS_JSON raise ArgumentError("'hash' was not hashable") unless hashable?(hash) state = ::RightSupport::Data::HashTools::DeepSortedJsonState.new(pretty) state.generate(hash) else raise NoJson, "JSON is unavailable" end end # provides a canonical representation of a header key that is acceptable to # Rack, etc. the web standard for canonical header keys is all lowercase # except with the first character capitalized at the start and after each # dash. underscores are converted to dash characters. def self.canonicalize_header_key(key) key.to_s.downcase.gsub('_', '-').gsub(/(^|-)(.)/) { $1 + $2.upcase } end # @return [String] header value by canonical key name, if present. def self.header_value_get(headers, key) return nil unless headers canonical_key = canonicalize_header_key(key) value = nil headers.each do |k, v| if canonicalize_header_key(k) == canonical_key value = v break end end value end # safely sets a header value by first locating any existing key by canonical # search. if you know that the header hash is already canonical then you can # alternatively set by using the canonicalized key. # # @param [Hash] headers to modify # @param [String] key for header # @param [String] value for header # # @return [Hash] updated headers def self.header_value_set(headers, key, value) headers ||= {} canonical_key = canonicalize_header_key(key) headers.each do |k, v| if canonicalize_header_key(k) == canonical_key key = k break end end headers[key] = value headers end # duplicates the given headers hash after canonicalizing header keys. # # @param [Hash] headers to canonicalize # # @return [Hash] canonicalized headers def self.canonicalize_headers(headers) headers.inject({}) do |h, (k, v)| h[canonicalize_header_key(k)] = v h end end # merges source headers hash into the duplicated target headers canonically. # also supports removal of a target header when the source value is nil. # # @param [Hash] target to merge to # @param [String] source to merge from # @return [Hash] merged headers def self.merge_headers(target, source) target = canonicalize_headers(target) (source || {}).each do |k, v| canonical_key = canonicalize_header_key(k) if v.nil? target.delete(canonical_key) else target[canonical_key] = v end end target end end end