Getting a table's value path

I’m trying to create a code that prints a path of a non table value in a table, for an example:

``````local tbl = {
Apple = 3;
Banana = {
foo = "E";
test = {
lol = "F";
};
};
};
``````

And I want an output of:

``````{"Apple"}
{"Banana", "foo"}
{"Bannaa", "test", "lol"}
``````

I tried using a simple table loop but it won’t work as expected since the `path` will be overrided when looping a new table, any solutions to this? I’d like to keep only looping the entire table once, but not looping the entire table again when creating a new path.

``````local path = {}
local function loop(loopTbl)
for i,v in pairs (loopTbl) do
table.insert(path, i)
if type(v) == "table" then
loop(v)
else
print(path)
end
end
end
loop(tbl)``````

I started writing a response awhile ago but decided to come back because this question interested me so I took a look into it.

Anyway, you’re able to do this with recursion. I had fun writing this:

``````local tbl = {
Apple = 3;
Banana = {
foo = "E";
test = {
lol = "F";
};
};
};

local hierarchy = {} -- this is what we are going to store the hierarchy in

local function getHierarchy(value, tbl, attempt, level)
local level = level or 1 -- this determines the index of the hierarchy table
local found
for i,v in pairs(tbl) do
if type(v) ~= 'table' and v == value then -- if v isn't a table and v is equal to the value then we can set the idnex to the value'
hierarchy[level] = i
return true
elseif type(v) == 'table' then -- if the v is a table then
found = getHierarchy(value, v, attempt, level + 1) -- call the functiom with the index as the last index plus 1, pass the current table
if found then
hierarchy[level] = i -- if it's found, set the index to i
return found -- return the found value, assuming this is calling itself (we don't really have any way to know)
end
end
end
end

local found = getHierarchy('F', tbl)

print(hierarchy) -- [1] = 'Banana'; [2] = 'test'; [3] = 'lol'
``````

You can do this as much as you want, with any level.

``````local tbl = { -- this is the base
Apple = 3;
Banana = {
foo = "E";
test = {
lol = "F";
};
moreTest = {
wow = {
this = {
can = {
go = {
really = {
really = {
really = {
andIMean = {
REALLY = {
far = {
down = {
because = {
of = {
our = {
good = {
friend = {
recursion = ':)'
}
};
look = {
it = {
even = {
works = {
with = {
multiple = {
tables = ':O'
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
};
moreMoreTest = {};
};
};

--...

local found = getHierarchy(':O', tbl)
--[[
▼  {
[1] = "Banana",
[2] = "moreTest",
[3] = "wow",
[4] = "this",
[5] = "can",
[6] = "go",
[7] = "really",
[8] = "really",
[9] = "really",
[10] = "andIMean",
[11] = "REALLY",
[12] = "far",
[13] = "down",
[14] = "because",
[15] = "of",
[16] = "our",
[17] = "look",
[18] = "it",
[19] = "even",
[20] = "works",
[21] = "with",
[22] = "multiple",
[23] = "tables"
}  -  Edit
]]
--
local found = getHierarchy(':)', tbl)

print(hierarchy)
--[[ ▼  {
[1] = "Banana",
[2] = "moreTest",
[3] = "wow",
[4] = "this",
[5] = "can",
[6] = "go",
[7] = "really",
[8] = "really",
[9] = "really",
[10] = "andIMean",
[11] = "REALLY",
[12] = "far",
[13] = "down",
[14] = "because",
[15] = "of",
[16] = "our",
[17] = "good",
[18] = "friend",
[19] = "recursion"
}  -  Edit
]]
``````
2 Likes

as this is very cool to see
it doesn’t output this

so I decided to take your function to make it achieve this!

``````local Table = {
Apple = 3,
Banana = {
foo = "E",
test = {
lol = "F"
}
}
}

function GetAllTablePaths(Table)
local function Hierarchy(Value1, Table1)
local Hierarchy = {}
local function GetHierarchy(Value2, Table2, Attempt, Level)
local Level = Level or 1
local Found = nil
for i, v in pairs(Table2) do
if type(v) ~= 'table' and v == Value2 then
Hierarchy[Level] = i
return true
elseif type(v) == 'table' then
Found = GetHierarchy(Value2, v, Attempt, Level + 1)
if Found then
Hierarchy[Level] = i
return Found
end
end
end
end
GetHierarchy(Value1, Table1)
return Hierarchy
end
local Paths = {}
local function LoopTable(Table1)
for i, v in pairs(Table1) do
if type(v) == "table" then
LoopTable(v)
else
table.insert(Paths, Hierarchy(v, Table))
end
end
end
LoopTable(Table)
return Paths
end

print(GetAllTablePaths(Table))
``````

now I know the variable names like Table, Table1, Table2 can obviously be different
but here is the output of `print(GetAllTablePaths(Table))`

EDIT1: I am 100% sure this can be improved and be more efficient, if anyone wants to improve this code please do so!
EDIT2: I fixed a small bug in the code

I’m late to the party, but I think there might be another slight issue with your implementation . Because you are finding the value first–then going in reverse to ultimately find its path, issues would arrive when there are duplicate values present. Such as cases like:

``````local Table = {
Banana = 'F',
Orange = 'F'
}
``````

It wouldn’t likely return what it’s supposed to because each time that `Hierarchy` function runs and encounters an `'F'` it will assume that’s the same `'F'` we wanted to find the path of (rather than being a different one that we haven’t found yet).

One might be able to fix this, as the Hierarchy function is building, by checking if the Hierarchy doesn’t exist already, but that would mean checking through each previous hierarchy each subsequent iteration of the source table. I don’t think that would scale well, so maybe instead one could remove all margin of possibility that the “same” value can be encountered twice altogether.

Here’s my implementation:

``````local function generate_tree(t)
local hierarchy = {}

local function next(t, trace) --//trace can be moved above(to upvalue)
local depth = #trace
for index, value in pairs(t) do
if type(value) == 'table' then
trace[depth+1] = index
next(value, trace)
else
local new_table = table.move(trace, 1, depth, 1, {})
new_table[#new_table + 1] = index
hierarchy[#hierarchy+1]  = new_table
end
end
end

next(t, {}); return hierarchy
end
``````

The only difference here, is as we descended into the depths of recursion, we don’t return and also keep a variable on the stackframe, `depth`, so that later we can use it as an end point for a newly found non-table value. it’s so cases like this work (and can recursively):

``````local Table = {
Banana = {lol = 'F'}, -- iterated first
Orange = 'E' -- iterated second
}
``````

4 Likes

it is fine if you are late
also I simply used @7z99’s function because I saw a way to use it
thank you for improving the existing code

this is definitly what I was thinking, since 7z99’s code was based on getting a value and if two values were the same it would mess up
and the fact that you made this go in order makes it even better

this is awesome

EDIT: I only have one problem with your code, you named the local function “next” when it is already a global variable

1 Like

I did indeed do this, but I don’t think it really affects much–other than syntax highlighting. As far as I know all that would happen is that the global next would get overshadowed by its local counterpart (with no run-time performance penalties). But of course, anyone could always just change it.

1 Like