feat(core): load and manage modules recursively

[molleweide]

• Adds utils/tree.lua file.
• modifies is_mod_enabled -> pass table as arg with the path to module.
• Modifies core accordingly + whichtree module.
• Allows user to freely structure their modules however they like.
• I have improved documentation. Need feedback. I am not so used to writing documentation.
• !!! I have yet to clean up the logger function so please ignore it for now. Should I split it into another file utils/tree_logger.lua?

I feel like utils/tree now is in a state where it makes sense for you to have a look at it. Comment with a question mark wherever you feel the code is unclear.

Todo:

• Update Doom docs.

Current state of my modules.lua file : https://github.com/molleweide/doom-nvim/blob/moll_mason/modules.lua

[molleweide]

tell me if I need to drop the doom.settings commit

[connorgmeehan]

Hey @molleweide, sorry for the delay reviewing this and thank you for the PR. I think that generalising tree traversal is a good idea but there are some issues with this implementation. I think the big thing is it's a bit too featureful to go in utils right now (meant for lightweight, general, re-usable functions). There are also some issues with seperation of concerns where there tree knows how to handle modules.lua files, loaded modules and keybinds maps, I think it's trying to do too much and it needs to be broken out a bit.

One way of doing this would be to make tree.lua a tree traversal builder. That allows us to easily define tree traversals for whatever our use case. I think this will make it easier to re-use code, make it easier to read and debug, and provide more specific error messages for whatever tree we're traversing.

-- This example implements depth first traversal of doom modules

-- Here we define a new traverser for doom modules, instead of being responsible for the
-- traversal of the tree itself, tree_traverser allows us to build a custom traversal algorithm specifically for our use case.

local modules_traverser = tree_traverser.build({
  -- Builds the traversal function defining how we should move through the tree
  -- @param node any The node itself
  -- @param next function(node: any) Traverse into the traverse_in node, adding the node to the stack
  -- @param traverse_out function() Traverses back a depth, pops the value from the stack
  -- @param err function(message: string) Traverses back a depth, this value is skipped by the handler (see below)
  traverser = function(node, stack, traverse_in, traverse_out, err)
    local parent = stack[#stack]
    local parent_is_section = (parent == nil or (type(parent.key) == "string" and type(parent.node) == "table"))
    if type(node) == "table" and parent_is_section then
      for key, value in pairs(node) do
        traverse_in(key, value) -- Traverse into next layer
      end
    elseif type(node) == "string" and not parent_is_section then
      print(node)
      traverse_out() -- This is a leaf, traverse back a layer
    else
      err(("doom-nvim: Error traversing doom modules in `modules.lua`, unexpected value `%s`."):format(vim.inspect(node))) -- Traverse back a layer but do not pass this value to the handler function.
    end
  end,
  -- Optional debugging function that can be used to
  debug_node = function(node, stack)
    local parent = stack[#stack]
    local indent_str = string.rep("--", #stack)
    local indent_cap = type(node) == "table" and "+" or ">"
    print(("%s%s %s"):format(indent_str, indent_cap, type(node) == "table" and parent.key or node))
  end,
})

-- Example modules
local modules = {
  features = {
    "feature_test",
  },
  langs = {
    "language_test",
    -- 1,
    -- { "error" },
    -- nil,
  },
  -- 2,
  -- { "error" },
  -- nil,
}

-- The second variable is a function to handle each node where we can implement the node handling logic and do the task we need.
-- modules_traverser can be re-used anytime we want to iterate over a modules structure now.
modules_traverser(modules, function(node, stack)
  if type(node) == "string" then
    local path = vim.tbl_map(function(stack_node)
      return type(stack_node.key) == "string" and stack_node.key or stack_node.node
    end, stack)
    local path_string = "doom.modules." .. table.concat(path, ".")

    print(path_string)
  else
  end
end, { debug = doom.logging == "trace" or doom.logging == "debug" })

This also makes the implementation of the tree traversal a lot simpler

local log = require("doom.utils.logging")
local tree_traverser = {
  build = function(builder_opts)
    local traverser = builder_opts.traverser
    local debug_node = builder_opts.debug_node
    local stack = {}
    local result = {}
    -- Traverse out, pops from stack, adds to result
    local traverse_out = function()
      table.remove(stack, #stack)
      table.remove(stack, #stack)
    end
    -- Error does not add to result or anything
    local err = function(message)
      table.remove(stack, #stack)
      local path = vim.tbl_map(function(stack_node)
        return "["..vim.inspect(stack_node.key).."]"
      end, stack)
      print(("%s\n Occursed at key `%s`."):format(message, table.concat(path, "")))
      table.remove(result, #result)
    end
    local traverse_in
    traverse_in = function(key, node)
      table.insert(stack, { key = key, node = node })
      table.insert(result, { node = node, stack = vim.deepcopy(stack) })
      traverser(node, stack, traverse_in, traverse_out, err)
    end

    return function(tree, handler, opts)
      result = {} -- Reset result

      traverser(tree, stack, traverse_in, traverse_out, err)

      if opts.debug and debug_node then
        for _, value in ipairs(result) do
          debug_node(value.node, value.stack)
        end
      end

      for _, value in ipairs(result) do
        handler(value.node, value.stack)
      end
    end
  end,
}

I really appreciate the code that you have written so far and the ideas for this generalised traverser. I think for this to be worth it it needs to be adaptable enough to work for other recursive structures (keymaps, autocommands, commands). Currently this PR feels like it's adding more complexity than needed to doom-nvim (my proposed solution does a bit as well) and I think the goal should be not to increase LOC too much and write something that is a lot simpler to read.

Also some more general feedback

• Use string.rep to build indentation
• I don't think it's worth having multiple logging levels for the debug mode, I think just leave it as trace and debug
• Maybe instead of a filter there can be a skip() function? Not sure if prev() will already cover this use-case.
• Make sure that new functions in utils do not have too specific a use-case, I believe that a lack of structure is a lot better than "too much" structure (i.e. a function can only be used on a very specific data structure).
• Try to clean up code where possible, use more ternarary operators for simple checks, if a function has a lot of if statements or deep nesting see if it can be shortened
• Try to think about the most common use case (in this situation it'd be loading modules as fast as possible, no debugging, no printing, etc) Try to make any computation unrelated to the main use-case optional so we're not running unnecessary code

I hope this isn't too much feedback, I think generally it just needs better seperation of concerns, adaptability and not to run unecessary code for the main use case.

[connorgmeehan]

To add to this, the capabilities of this code are really cool and full featured but I think it's just not a right fit to go into the shared utils folder because it has too many features and code that wont be used by most users. I think it's better to make a really lightweight way of traversing trees in utils and then implement something like this into your dui modules. Kind of the same idea of breaking a monolith into micro services.

Also you don't have to copy my solution but it's just an example of a more stripped down version that can be adapted to different use-cases, keen to see what you come up with :)

[molleweide]

@connorgmeehan allright so now I have tweaked your traversal in a few minor ways to make it work a little bit more flexible. Now I get it to print the whole modules table as it should.

Please try it and check so it works on your end as well. If you run it now with :source % it requires modules.lua and prints everything.

This is awesome! Thanks a lot for showing me your version. Let's go with this and then Ima have to do some more comparisons with my own tree later when I make dui fit with this. I get such a headache from working on recursive type stuff for too long :P

issues solved

1. The modules_traverser func did not travel / pop back up when having finished a subtable. I solved this by adding a traverse_out call att the end of the looping each node table. AND I also reduced the duplicate calls to popping the stack to ONLY one call. Two calls messed things up for me. I dunno what your intention was initially but anyways, now it works as it should.

2. Now I also handle the case of an empty table, so that you don't have to worry about this if you comment all modules out in a table.

Also, as you might notice in my test table:

  FEATURES = {
    "feature_test",
    "feature_test2",
    EMPTY = {}, -- also handles this case, just in case...
    XXX = {
      "x1",
      "x2",

now you can also have modules at the same level as a subtable, so it is fully up to the user. The only thing a user can't do or is discouraged from doing is to have nested init.lua files WITHIN a module directory. (This is also because dui globs the module dirs for init.lua files, so if a module becomes very large, then you cannot use init.lua files in a modules subdir.

In short, now you have maximum flexibility.

links

Here is my modules quick reference: https://github.com/molleweide/doom-nvim/blob/molleweide/modules.lua and here is the code: https://github.com/molleweide/doom-nvim/blob/molleweide/scratch/tree_connor.lua

next steps

Now I need to incorporate this into doom and test so that it actually works. Do you have any suggestions on how we should place these files. My suggestion:

• put the tree_traverser in a service (maybe also under utils?)
• move the modules_traverser to under utils.
• maybe there'll also be some more reusables, like the call to modules_traverser, that we can put into utils so that one can quickly get the list of concatenated paths etc.

Hmmm, now that I think about it. Traversing the loaded doom.modules table will still need another custom function, so maybe we should have a doom/utils/modules.lua file after all where all of these helpers can be located.

What do you think? Then I could merge this together with the module helpers that arose during duidev as well into this modules util.

Finally, then replace every iteration over enabled_modules and doom.modules with the call to the modules_traverser, ie. in:

1. core/config
2. core/modules
3. whichkey module.
4. etc.

Then we're done!!!

After this is, I'll redo the doom.settings PR, so that I can start merging main back into my own daily driver branch which now is dependent on this new pattern.