mhenrixon | I am soft and recursion is hard

We all need recursion sometimes, but we can often wait a while. This is one of those situations when I do a slight bit of TDD. I start with the most banal example possible:

lang-ruby
RSpec.describe Mongo::LineConverter do
  let(:converter)   { described_class.new(conversions, data) }
  let(:conversions) { [{ from: "_id.$oid", to: "mongo_id" }] }
  let(:data) do
    {
      "_id" => { "$oid" => "12345" },
      "name" => "Test Name",
    }
  end

  describe "#convert" do
    subject(:convert) { converter.convert }

    it "converts data according to conversions" do
      expect(convert["mongo_id"]).to eq("12345")
      expect(convert["name"]).to eq("Test Name")
      expect(convert).not_to include("_id")
    end
  end
end

I designed the following code; the TDD part has yet to start.

lang-ruby
module Mongo
  class LineConverter
    def self.convert(...)
      new(...).convert
    end

    attr_reader :data, :conversions

    def initialize(conversions, data)
      @conversions = conversions
      @data = data
    end

    def convert
      data.each_with_object({}) do |(key, value), memo|
        conversions.each do |conversion|
          froms = conversion[:from].split(".")
          from  = froms.first # I can't accept .first twice
          to    = conversion[:to]

          if key == from
            memo[to] = data.dig(*froms)
          else
            memo[key] = value
          end
        end
      end
    end
  end
end

Obviously, this code only satisfies when the key is at the root level. We need to check this. I loaded a more complete example, and low and behold, I discovered some nested "_id" keys that I didn't want.

This is one of the very few times I reach for test-driven design. I have a solid design, but I need to expand on it. From here, adding tests to cover new scenarios is a way to verify that my design holds up.

This time it didn't hold up, so let's get into the details.

Adding test coverage

lang-ruby
it "converts data according to conversions" do
  expect(convert["mongo_id"]).to eq("12345")
  expect(convert).not_to include("_id")

  expect(convert["nested"]["mongo_id"]).to eq("54321")
  expect(convert["nested"]).not_to include("_id")
      
  expect(convert["name"]).to eq("Test Name")
end

First, I need to add recursion, but it is too complex with the existing implementation.

Can you spot the problem?

The convert method isn't recursive because it does not accept parameters! I could add a separate method or I change the methods signature. Personally, I prefer the latter, so let's go ahead and do that, and let's start with the test.

lang-ruby
RSpec.describe Mongo::LineConverter do
  let(:converter)   { described_class.new(conversions) }
  let(:conversions) { [{ from: "_id.$oid", to: "mongo_id" }] }
  let(:data) do
    {
      "_id" => { "$oid" => "12345" },
      "nested" => { "_id" => { "$oid" => "12345" } },
      "name" => "Test Name",
    }
  end

  describe "#convert" do
    subject(:convert) { converter.convert(data) }

    it "converts data according to conversions" do
      expect(convert["mongo_id"]).to eq("12345")
      expect(convert).not_to include("_id")

      expect(convert["nested"]["mongo_id"]).to eq("54321")
      expect(convert["nested"]).not_to include("_id")
          
      expect(convert["name"]).to eq("Test Name")
    end
  end
end

I struggled a little; I asked ChatGPT to help because I am soft, and recursion is hard. Unfortunately, ChatGPT was less than helpful. Its way of dealing with recursion could have been more comprehensible.

I ended up with the following (which I am super proud of as it is all mine).

lang-ruby
module Mongo
  class LineConverter
    def self.convert(conversions, data)
      new(conversions).convert(data)
    end

    attr_reader :conversions

    def initialize(conversions)
      @conversions = conversions
    end

    def convert(data)
      case data
      when Hash
        data.each_with_object({}) do |(key, value), memo|
          # NOTE: We need to track the state of conversion.
          converted = false

          # NOTE: Loop through the conversions and convert the data.
          conversions.each do |conversion|
            # NOTE: To support nested lookups we suppport "_id.$oid" as a from key.
            froms = conversion[:from].split(".")
            from  = froms.first
            to    = conversion[:to]

            # NOTE: This key needs no conversion.
            next unless from == key

            new_value = data.dig(*froms)
            memo[to]  = convert(new_value)
            # NOTE: This key was converted, which ensures we can skip it below
            converted = true
            break # no need to continue the loop
          end

          # NOTE: If this key wasn't converted, recursively convert its value.
          memo[key] = convert(value) unless converted
        end
      when Array
        data.map { |element| convert(element) }
      else
        data
      end
    end
  end
end

I am soft and recursion is hard

Comments