Recursive Hash transformation function in ruby

Question

I have the following swagger (openAPI) definition of a response schema:

h = { "type"=>"object",
      "properties"=>{
        "books"=>{
          "type"=>"array",
          "items"=>{
            "type"=>"object",
            "properties"=>{
              "urn"  =>{ "type"=>"string" },
              "title"=>{ "type"=>"string" }
            }
          }
        }
      }
    }

And would like to transform this into the following format, so as to be able to display this response as a tree:

{ "name"=>"200",
  "children"=> [
    {
      "name"=>"books (array)",
      "children"=> [
        {"name"=>"urn (string)" },
        {"name"=>"title (string)" }
      ]
    }
  ]
}

In the swagger schema format, a node can either be an object (with properties), or an array of items, which are themselves objects. Here is the function I have written: the schema parameter is the hash in the swagger format shown above, and the tree variable contains {name: "200"}

      def build_tree(schema, tree)
        if schema.class == ActiveSupport::HashWithIndifferentAccess
          case schema[:type]
          when 'object'
            tree[:children] = []
            schema[:properties].each do |property_name, property_schema|
               tree[:children] <<
                 { name: property_name, children: build_tree(property_schema, tree) }
            end
          when 'array'
            schema[:items].each do |property_name, property_schema|
              tree[:children] <<
                { name: property_name, children: build_tree(property_schema, tree) }
            end
          when nil
            tree[:name] == schema
          end
          else
            tree[:name] == schema
          end
        end

Unfortunately I think I'm making an error somewhere, as this returns the following Hash:

{ :name=>"200",
  :children=>[
    { :name=>"type", :children=>false },
    { :name=>"properties", :children=>false },
    { :name=>"books",
      :children=>{
        "type"=>"object",
        "properties"=>{
          "urn"=>{"type"=>"string"},
          "title"=>{"type"=>"string"}
        }
      }
    }
  ]
}

I must be missing a step in the recursion or passing the tree in the wrong way, but I'm afraid I don't have enough brainpower to figure it out :) maybe a kind soul with a gift for writing beautiful ruby code will give me a hand!

Answer 1

Recursion ! Try Elixir :-)

To trace a recursive method, I write plenty of puts and add a level number.

As I don't have Rails, I have removed the Rails stuff. With this slight modification, your input (where the array of books is not an array !) and your code :

schema = 
    { "type"=>"object",
      "properties"=>{
        "books"=>{
          "type"=>"array",
          "items"=>{
            "type"=>"object",
            "properties"=>{
              "urn"  =>{ "type"=>"string" },
              "title"=>{ "type"=>"string" }
            }
          }
        }
      }
    }

tree = {}

def build_tree(schema, tree, level)
    puts "level=#{level} schema[:type]=#{schema['type'].inspect}, schema class is #{schema.class}"
    case schema['type']
    when 'object'
        puts "in when object for #{schema['properties'].size} properties :"
        i = 0
        schema['properties'].each_key{ | name | puts "#{i+=1}. #{name}" }
        tree[:children] = []
        schema['properties'].each do | property_name, property_schema |
            puts "level=#{level} property_name=#{property_name}"
            tree[:children] << { name: property_name, children: build_tree(property_schema, tree, level + 1) }
        end
    when 'array'
        puts "in when array for #{schema['items'].size} items will process following items :"
        i = 0
        schema['items'].each_key{ | name | puts "#{i+=1}. #{name}" }
        schema['items'].each do | property_name, property_schema |
            puts "level=#{level} property_name=#{property_name}, property_schema=#{property_schema.inspect}"
            tree[:children] << { name: property_name, children: build_tree(property_schema, tree, level + 1) }
        end
    when nil
        puts "in when nil"
        tree[:name] == schema
    end
end

build_tree(schema, tree, 1)
puts tree

the result is what you have obtained :

$ ruby -w t_a.rb 
level=1 schema[:type]="object", schema class is Hash
in when object for 1 properties :
1. books
level=1 property_name=books
level=2 schema[:type]="array", schema class is Hash
in when array for 2 items will process following items :
1. type
2. properties
level=2 property_name=type, property_schema="object"
level=3 schema[:type]=nil, schema class is String
in when nil
level=2 property_name=properties, property_schema={"urn"=>{"type"=>"string"}, "title"=>{"type"=>"string"}}
level=3 schema[:type]=nil, schema class is Hash
in when nil
{:children=>[
    { :name=>"type", :children=>false}, 
    { :name=>"properties", :children=>false}, 
    { :name=>"books", 
      :children=>{
        "type"=>"object", 
        "properties"=>{
            "urn"=>{"type"=>"string"}, 
            "title"=>{"type"=>"string"}
        }
      }
    }
  ]
}

(Note : I have manually pretty printed the resulting tree).

The trace shows what's going on : in when 'array' when you write schema['items'].each you probably want to iterate over several items. But there are no items, there is a single hash. So schema['items'].each becomes iterating over the keys. Then you recurs with a schema which has no 'type' key, hence case schema['type'] falls into when nil.

Note that if when 'object'had been recursively called instead of when nil, tree[:children] = [] would have erased previous results, because you use always the same initial tree. To stack intermediate results, you need to provide new variables in the recursive calls.

The best way to understand recursion is not to loop to the beginning of the method, but to imagine a cascade of calls :

method_1
   |
   +------> method_2
               |
               +------> method_3

If you pass the same initial parameter as argument to the recursive call, it is erased by the last returned value. But if you pass a new variable, you can use it in an accumulation operation.

If you had checked that schema['items']is really an array, as I do in my solution, you would have seen that the input does not correspond to the expectation :

$ ruby -w t.rb 
level=1 schema[:type]="object", schema class is Hash
in when object for 1 properties :
1. books
level=1 property_name=books
level=2 schema[:type]="array", schema class is Hash
in when array
oops ! Array expected
{:children=>[{:name=>"books", :children=>"oops ! Array expected"}]}

Now my solution. I leave cosmetic details up to you.

schema = 
    { "type"=>"object",
      "properties"=>{
        "books"=>{
          "type"=>"array",
          "items"=> [ # <----- added [
            { "type"=>"object",
              "properties" => {
                "urn"   => { "type"=>"string" },
                "title" => { "type"=>"string" }
                              }
            },
            { "type"=>"object",
              "properties" => {
                "urn2"   => { "type"=>"string" },
                "title2" => { "type"=>"string" }
                              }
            }
                    ] # <----- added ]
        } # end books
      } # end properties
    } # end schema

tree = {"name"=>"200", children: []}

def build_tree(schema, tree, level)
    puts
    puts "level=#{level} schema[:type]=#{schema['type'].inspect}, schema class is #{schema.class}"
    puts "level=#{level} tree=#{tree}"
    case schema['type']
    when 'object'
        puts "in when object for #{schema['properties'].size} properties :"
        i = 0
        schema['properties'].each_key{ | name | puts "#{i+=1}. #{name}" }
        schema['properties'].each do | property_name, property_schema |
            puts "object level=#{level}, property_name=#{property_name}"
            type, sub_tree = build_tree(property_schema, {children: []}, level + 1)
            puts "object level=#{level} after recursion, type=#{type} sub_tree=#{sub_tree}"
            child = { name: property_name + type }
            child[:children] = sub_tree unless sub_tree.empty?
            tree[:children] << child
        end
        puts "object level=#{level} about to return tree=#{tree}"
        tree
    when 'array'
        puts "in when array"
        case schema['items']
        when Array
            puts "in when Array for #{schema['items'].size} items"
            i     = 0
            items = []
            schema['items'].each do | a_hash |
                puts "item #{i+=1} has #{a_hash.keys.size} keys :"
                a_hash.keys.each{ | key | puts key }
                # if the item has "type"=>"object" and "properties"=>{ ... }, then
                # the whole item must be passed as argument to the next recursion
                puts "level=#{level} about to recurs for item #{i}"
                answer = build_tree(a_hash, {children: []}, level + 1)
                puts "level=#{level} after recurs, answer=#{answer}"
                items << { "item #{i}" => answer }
            end
            return ' (array)', items
        else
            puts "oops ! Array expected"
            "oops ! Array expected"
        end
    when 'string'
        puts "in when string, schema=#{schema}"
        return ' (string)', []
    else
        puts "in else"
        tree[:name] == schema
    end
end

build_tree(schema, tree, 1)
puts 'final result :'
puts tree

Execution :

$ ruby -w t.rb 

level=1 schema[:type]="object", schema class is Hash
level=1 tree={"name"=>"200", :children=>[]}
in when object for 1 properties :
1. books
object level=1, property_name=books

level=2 schema[:type]="array", schema class is Hash
level=2 tree={:children=>[]}
in when array
in when Array for 2 items
item 1 has 2 keys :
type
properties
level=2 about to recurs for item 1

level=3 schema[:type]="object", schema class is Hash
level=3 tree={:children=>[]}
in when object for 2 properties :
1. urn
2. title
object level=3, property_name=urn

level=4 schema[:type]="string", schema class is Hash
level=4 tree={:children=>[]}
in when string, schema={"type"=>"string"}
object level=3 after recursion, type= (string) sub_tree=[]
object level=3, property_name=title

level=4 schema[:type]="string", schema class is Hash
level=4 tree={:children=>[]}
in when string, schema={"type"=>"string"}
object level=3 after recursion, type= (string) sub_tree=[]
object level=3 about to return tree={:children=>[{:name=>"urn (string)"}, {:name=>"title (string)"}]}
level=2 after recurs, answer={:children=>[{:name=>"urn (string)"}, {:name=>"title (string)"}]}
item 2 has 2 keys :
type
properties
level=2 about to recurs for item 2

level=3 schema[:type]="object", schema class is Hash
level=3 tree={:children=>[]}
in when object for 2 properties :
1. urn2
2. title2
object level=3, property_name=urn2

level=4 schema[:type]="string", schema class is Hash
level=4 tree={:children=>[]}
in when string, schema={"type"=>"string"}
object level=3 after recursion, type= (string) sub_tree=[]
object level=3, property_name=title2

level=4 schema[:type]="string", schema class is Hash
level=4 tree={:children=>[]}
in when string, schema={"type"=>"string"}
object level=3 after recursion, type= (string) sub_tree=[]
object level=3 about to return tree={:children=>[{:name=>"urn2 (string)"}, {:name=>"title2 (string)"}]}
level=2 after recurs, answer={:children=>[{:name=>"urn2 (string)"}, {:name=>"title2 (string)"}]}
object level=1 after recursion, type= (array) sub_tree=[{"item 1"=>{:children=>[{:name=>"urn (string)"}, {:name=>"title (string)"}]}}, {"item 2"=>{:children=>[{:name=>"urn2 (string)"}, {:name=>"title2 (string)"}]}}]
object level=1 about to return tree={"name"=>"200", :children=>[{:name=>"books (array)", :children=>[{"item 1"=>{:children=>[{:name=>"urn (string)"}, {:name=>"title (string)"}]}}, {"item 2"=>{:children=>[{:name=>"urn2 (string)"}, {:name=>"title2 (string)"}]}}]}]}
final result :
{"name"=>"200", :children=>[{:name=>"books (array)", :children=>[{"item 1"=>{:children=>[{:name=>"urn (string)"}, {:name=>"title (string)"}]}}, {"item 2"=>{:children=>[{:name=>"urn2 (string)"}, {:name=>"title2 (string)"}]}}]}]}

Result edited :

{"name"=>"200", 
 :children=>[
   {
     :name=>"books (array)",
     :children=>[
       {"item 1"=>{
         :children=>[
           {:name=>"urn (string)"}, 
           {:name=>"title (string)"}
         ]
        }
       },
       {"item 2"=>{
         :children=>[
           {:name=>"urn2 (string)"}, 
           {:name=>"title2 (string)"}
         ]
        }
       }
     ]
   }
 ]
}

Answer 2

So array of items is not an array of items but an array of properties of the sub-schema. This is the new solution to take this fact into account :

schema = 
    { "type"=>"object",
      "properties"=>{
        "books"=>{
          "type"=>"array",
          "items"=> {
              "type"=>"object",
              "properties" => {
                "urn"   => { "type"=>"string" },
                "title" => { "type"=>"string" }
                              }
          } # end items
        } # end books
      } # end properties
    } # end schema

tree = {"name"=>"200"}

def build_tree(schema, tree, level)
    puts
    puts "level=#{level} schema[:type]=#{schema['type'].inspect}, schema class is #{schema.class}"
    puts "level=#{level} tree=#{tree}"
    case schema['type']
    when 'object'
        puts "in when object for #{schema['properties'].size} properties :"
        i = 0
        schema['properties'].each_key{ | name | puts "#{i+=1}. #{name}" }
        tree[:children] = []
        schema['properties'].each do | property_name, property_schema |
            puts "object level=#{level}, property_name=#{property_name}"
            type, sub_tree = build_tree(property_schema, {}, level + 1)
            puts "object level=#{level} after recursion, type=#{type} sub_tree=#{sub_tree}"
            child = { name: property_name + type }
            sub_tree.each { | k, v | child[k] = v }
            tree[:children] << child
        end
        puts "object level=#{level} about to return tree=#{tree}"
        tree
    when 'array'
        puts "in when array"
        case schema['items']
        when Hash
            puts "in when Hash"
            puts "the schema has #{schema['items'].keys.size} keys :"
            schema['items'].keys.each{ | key | puts key }
            # here you could raise an error if the two keys are NOT "type"=>"object" and "properties"=>{ ... }
            puts "Hash level=#{level} about to recurs"
            return ' (array)', build_tree(schema['items'], {}, level + 1)
        else
            puts "oops ! Hash expected"
            "oops ! Hash expected"
        end
    when 'string'
        puts "in when string, schema=#{schema}"
        return ' (string)', {}
    else
        puts "in else"
        tree[:name] == schema # ???? comparison ?
    end
end

build_tree(schema, tree, 1)
puts 'final result :'
puts tree

Result edited (tested with ruby 2.3.3p222) :

{ "name"=>"200", 
  :children=> [
    {
      :name=>"books (array)", 
      :children=> [
        {:name=>"urn (string)"}, 
        {:name=>"title (string)"}
      ]
    }
  ]
}

Don't take it as brilliant code. I write Ruby code every earthquake of magnitude 12. The purpose was to explain what didn't work in your code and draw attention on using new variables (now an empty Hash) in the recursive call. There are plenty of cases that should be tested and raise an error.

The right way is BDD as did @moveson : first write RSpec tests for all cases, especially edge cases, then write the code. I know it gives the feeling to be too slow, but in the long term it pays and replaces the debugging and printing of traces.

More on tests

This code is brittle : for example if a type key is not associated with a properties key, it will fail at schema['properties'].each : undefined method 'each' for nil:NilClass. A spec like context 'when a type object has no properties' do let(:schema) { {"type" => "object", "xyz" => ...

would help adding code to check pre-conditions. I'm also lazy using RSpec for small scripts, but for serious development, I make the effort because I have recognized the benefits. The time spent in debugging is lost forever, the time invested in specs gives security in case of changes and a nice legible indented report about what the code does or does not. I recommend the brand new Rspec 3 book.

One more word on accessing hashes : if you have a mix of strings and symbols, it's a source of problems.

some_key = some_data # sometimes string, sometimes symbol
schema[some_key]...

will not find the element if the internal keys are not of the same type as the external data. Choose a type, for example symbol, when you create the hash, and systematically convert access variables to symbol :

some_key = some_data # sometimes string, sometimes symbol
schema[some_key.to_sym]...

or all to strings :

some_key = some_data # sometimes string, sometimes symbol
schema[some_key.to_s]...

Answer 3

The solution suggested by @BernardK is impressive in its length, but I could not get it to work. Here's my more humble solution. I wrapped it in a class so I could test it properly.

One problem with your code is that in a couple of places, you are returning tree[:name] == schema, which evaluates to false. I think you meant to assign tree[:name] = schema and then return tree.

Like @BernardK, I assumed that a schema of type 'array' would have, as its value, an array of things. If that's not how it works, then could you please provide an example where 'array' is something more than an additional layer around an 'object'?

Hopefully between this answer and the other, you can make something out of it that works for you.

# swagger.rb

class Swagger

  def self.build_tree(schema, tree)
    if schema.class == ActiveSupport::HashWithIndifferentAccess
      case schema['type']
      when 'object'
        tree['children'] = schema['properties'].map do |property_name, property_schema|
          build_tree(property_schema, {'name' => property_name})
        end
        tree
      when 'array'
        schema['items'].map do |item|
          build_tree(item, {'name' => "#{tree['name']} (array)"})
        end
      when 'string'
        {'name' => "#{tree['name']} (string)"}
      end
    else
      raise ArgumentError, "Expected a HashWithIndifferentAccess but got #{schema.class}: #{schema}"
    end
  end
end

Here is the spec file:

# /spec/swagger_spec.rb

require_relative '../swagger'

describe Swagger do
  describe '.build_tree' do
    context 'when given a Hash whose type is string' do
      let(:tree) { {"name" => "urn"} }
      let(:schema) { {"type" => "string"}.with_indifferent_access }
      let(:expected) { {"name" => "urn (string)"} }

      it 'returns a Hash with "name" as the key and the tree value and its type as the value' do
        expect(Swagger.build_tree(schema, tree)).to eq(expected)
      end
    end

    context 'when given a simple schema' do
      let(:tree) { {"name" => "200"} }
      let(:schema) { {"type" => "object",
                      "properties" => {
                          "urn" => {"type" => "string"},
                          "title" => {"type" => "string"}
                      }}.with_indifferent_access }

      let(:expected) { {"name" => "200",
                        "children" => [{"name" => "urn (string)"},
                                       {"name" => "title (string)"}
                        ]} }

      it 'transforms the tree into swagger (openAPI) format' do
        expect(Swagger.build_tree(schema, tree)).to eq(expected)
      end
    end

    context 'when given a complicated schema' do
      let(:tree) { {"name" => "200"} }
      let(:schema) { {"type" => "object",
                      "properties" =>
                          {"books" =>
                               {"type" => "array",
                                "items" =>
                                    [{"type" => "object",
                                      "properties" =>
                                          {"urn" => {"type" => "string"}, "title" => {"type" => "string"}}
                                     }] # <-- added brackets
                               }
                          }
      }.with_indifferent_access }

      let(:expected) { {"name" => "200",
                        "children" =>
                            [[{"name" => "books (array)",
                              "children" => [{"name" => "urn (string)"}, {"name" => "title (string)"}]
                              }]]
      } }

      it 'transforms the tree into swagger (openAPI) format' do
        expect(Swagger.build_tree(schema, tree)).to eq(expected)
      end
    end

    context 'when given a schema that is not a HashWithIndifferentAccess' do
      let(:tree) { {"name" => "200"} }
      let(:schema) { ['random array'] }

      it 'raises an error' do
        expect { Swagger.build_tree(schema, tree) }.to raise_error ArgumentError
      end
    end
  end
end