I am soft and recursion is hard

Mikael Henriksson

February 6, 20243 min read

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:

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.

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

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.

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).

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

You're offline — that change wasn't saved. Try again once you're connected.