Merge pull request #7027 from xmake-io/graph

Improve graph

4 files changed, 237 insertions, 38 deletions

diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua
index fe1d63e8d..7c17a4fec 100644
--- a/tests/modules/graph/test.lua
+++ b/tests/modules/graph/test.lua
@@ -170,6 +170,48 @@ function test_paritail_topo_sort_dynamic(t)
     end
 end
 
+function test_remove_edge_and_vertex(t)
+    local gh = graph.new(true)
+    gh:add_edge("a", "b")
+    gh:add_edge("b", "c")
+    gh:add_edge("c", "d")
+    gh:add_edge("a", "d")
+
+    t:require(gh:has_edge("a", "b"))
+    gh:remove_edge("a", "b")
+    t:require(not gh:has_edge("a", "b"))
+    t:require(gh:has_edge("a", "d"))
+
+    gh:remove_vertex("c")
+    t:require(not gh:has_edge("b", "c"))
+    t:require(not gh:has_edge("c", "d"))
+    t:are_equal(#gh:vertices(), 3)
+    local order = gh:topo_sort()
+    t:require(#order == 3)
+
+    gh:add_edge("b", "a")
+    gh:add_edge("d", "b")
+    local _, has_cycle = gh:topo_sort()
+    t:require(has_cycle)
+end
+
+function test_clone_reverse_undirected(t)
+    local ug = graph.new(false)
+    ug:add_edge(1, 2)
+    ug:add_edge(2, 3)
+    ug:add_edge(3, 1)
+
+    local clone = ug:clone()
+    t:require(#clone:edges() == #ug:edges())
+    t:require(clone:has_edge(1, 2))
+    t:require(clone:has_edge(2, 1))
+
+    local rev = ug:reverse()
+    t:require(rev:has_edge(1, 2))
+    t:require(rev:has_edge(2, 1))
+    t:require(#rev:edges() == #ug:edges())
+end
+
 function test_find_cycle(t)
     local edges = {
         {9, 1},
diff --git a/tests/modules/jobgraph/test.lua b/tests/modules/jobgraph/test.lua
new file mode 100644
index 000000000..ba01d38da
--- /dev/null
+++ b/tests/modules/jobgraph/test.lua
@@ -0,0 +1,45 @@
+import("async.jobgraph")
+
+local function dummy_job() end
+
+function test_group_bridge_reuse(t)
+    local jobs = jobgraph.new()
+    jobs:group("foo", function ()
+        jobs:add("foo/1", dummy_job)
+        jobs:add("foo/2", dummy_job)
+    end)
+    jobs:group("bar", function ()
+        jobs:add("bar/1", dummy_job)
+    end)
+    jobs:add_orders("foo", "bar")
+    local vertices_before = #jobs._dag:vertices()
+    jobs:add_orders("foo", "bar")
+    local vertices_after = #jobs._dag:vertices()
+    t:are_equal(vertices_before, vertices_after)
+end
+
+function test_group_bridge_updates_with_new_job(t)
+    local jobs = jobgraph.new()
+    jobs:group("foo", function ()
+        jobs:add("foo/1", dummy_job)
+    end)
+    jobs:group("bar", function ()
+        jobs:add("bar/1", dummy_job)
+    end)
+    jobs:add_orders("foo", "bar")
+    jobs:group("foo", function ()
+        jobs:add("foo/2", dummy_job)
+    end)
+
+    local queue = jobs:build()
+    local first = queue:getfree()
+    t:require(first.name == "foo/1" or first.name == "foo/2")
+    queue:remove(first)
+    local second = queue:getfree()
+    t:require(second.name == "foo/1" or second.name == "foo/2")
+    t:require(second.name ~= first.name)
+    queue:remove(second)
+    local third = queue:getfree()
+    t:are_equal(third.name, "bar/1")
+end
+
diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua
index 64dfa3b31..be0035394 100644
--- a/xmake/core/base/graph.lua
+++ b/xmake/core/base/graph.lua
@@ -116,20 +116,18 @@ function graph:remove_vertex(v)
         end
     end)
     if contains then
-        self._edges_map[v] = nil
-        self._adjacent_edges[v] = nil
-        -- remove the adjacent edge with this vertex in the other vertices
-        for _, w in ipairs(self:vertices()) do
-            local edges = self:adjacent_edges(w)
-            if edges then
-                table.remove_if(edges, function (_, e)
-                    if e:other(w) == v then
-                        self._edges_map[w] = nil
-                        return true
-                    end
-                end)
+        -- remove all touching edges
+        local touching = {}
+        for _, e in ipairs(self._edges) do
+            if e:from() == v or e:to() == v then
+                table.insert(touching, {e:from(), e:to()})
             end
         end
+        for _, pair in ipairs(touching) do
+            self:remove_edge(pair[1], pair[2])
+        end
+        self._edges_map[v] = nil
+        self._adjacent_edges[v] = nil
 
         -- reset partial topological sort state since graph structure changed
         self._partial_topo_dirty = true
@@ -398,6 +396,59 @@ function graph:add_edge(from, to)
     self._partial_topo_dirty = true
 end
 
+-- remove edge
+function graph:remove_edge(from, to)
+    if not self:has_edge(from, to) then
+        return
+    end
+    local directed = self:is_directed()
+    local edges = self._edges
+    local target_index
+    local target_edge
+    for idx, e in ipairs(edges) do
+        local match = (e:from() == from and e:to() == to)
+        if not directed then
+            match = match or (e:from() == to and e:to() == from)
+        end
+        if match then
+            target_index = idx
+            target_edge = e
+            break
+        end
+    end
+    assert(target_edge, string.format("graph.remove_edge(%s, %s): edge not found", tostring(from), tostring(to)))
+
+    table.remove(edges, target_index)
+
+    local function remove_from_adj(vertex)
+        local adj = self._adjacent_edges[vertex]
+        if adj then
+            table.remove_if(adj, function (_, e) return e == target_edge end)
+        end
+    end
+
+    remove_from_adj(target_edge:from())
+    remove_from_adj(target_edge:to())
+
+    local edges_map = self._edges_map
+    local function clear_map(u, v)
+        local map = edges_map[u]
+        if map then
+            map[v] = nil
+            if not next(map) then
+                edges_map[u] = nil
+            end
+        end
+    end
+
+    clear_map(target_edge:from(), target_edge:to())
+    if not directed then
+        clear_map(target_edge:to(), target_edge:from())
+    end
+
+    self._partial_topo_dirty = true
+end
+
 -- has the given edge?
 function graph:has_edge(from, to)
     local edges_map = self._edges_map
@@ -413,13 +464,8 @@ end
 -- clone graph
 function graph:clone()
     local gh = graph.new(self:is_directed())
-    for _, v in ipairs(self:vertices()) do
-        local edges = self:adjacent_edges(v)
-        if edges then
-            for _, e in ipairs(edges) do
-                gh:add_edge(e:from(), e:to())
-            end
-        end
+    for _, e in ipairs(self._edges) do
+        gh:add_edge(e:from(), e:to())
     end
     return gh
 end
@@ -430,13 +476,8 @@ function graph:reverse()
         return self:clone()
     end
     local gh = graph.new(self:is_directed())
-    for _, v in ipairs(self:vertices()) do
-        local edges = self:adjacent_edges(v)
-        if edges then
-            for _, e in ipairs(edges) do
-                gh:add_edge(e:to(), e:from())
-            end
-        end
+    for _, e in ipairs(self._edges) do
+        gh:add_edge(e:to(), e:from())
     end
     return gh
 end
diff --git a/xmake/modules/async/jobgraph.lua b/xmake/modules/async/jobgraph.lua
index 67fe836c1..a1abbf86d 100644
--- a/xmake/modules/async/jobgraph.lua
+++ b/xmake/modules/async/jobgraph.lua
@@ -26,7 +26,51 @@ import("core.base.hashset")
 
 -- define module
 local jobqueue = jobqueue or object {_init = {"_jobgraph", "_dag"}}
-local jobgraph = jobgraph or object {_init = {"_name", "_jobs", "_size", "_dag", "_groups"}}
+local jobgraph = jobgraph or object {_init = {"_name", "_jobs", "_size", "_dag", "_groups", "_bridge_nodes", "_bridge_from", "_bridge_to"}}
+
+-- attach a job to existing bridge nodes of its group (if any)
+function jobgraph:_attach_job_to_bridges(job, group_name)
+    local outbound = self._bridge_from[group_name]
+    local inbound = self._bridge_to[group_name]
+    if not outbound and not inbound then
+        return
+    end
+    if outbound then
+        for _, bridge in ipairs(outbound) do
+            self._dag:add_edge(job, bridge)
+        end
+    end
+    if inbound then
+        for _, bridge in ipairs(inbound) do
+            self._dag:add_edge(bridge, job)
+        end
+    end
+end
+
+-- ensure a reusable bridge node exists between two groups
+function jobgraph:_ensure_bridge(from_group, to_group)
+    local key = from_group .. "->" .. to_group
+    local bridge = self._bridge_nodes[key]
+    if bridge then
+        return bridge
+    end
+    bridge = {from_group = from_group, to_group = to_group}
+    self._bridge_nodes[key] = bridge
+    self._dag:add_vertex(bridge)
+    local from_members = self._groups[from_group] or {}
+    for _, member in ipairs(from_members) do
+        self._dag:add_edge(member, bridge)
+    end
+    local to_members = self._groups[to_group] or {}
+    for _, member in ipairs(to_members) do
+        self._dag:add_edge(bridge, member)
+    end
+    self._bridge_from[from_group] = self._bridge_from[from_group] or {}
+    table.insert(self._bridge_from[from_group], bridge)
+    self._bridge_to[to_group] = self._bridge_to[to_group] or {}
+    table.insert(self._bridge_to[to_group], bridge)
+    return bridge
+end
 
 -- remove the finished job
 function jobqueue:remove(job)
@@ -79,15 +123,37 @@ function jobgraph:add(name, run, opt)
         self._size = self._size + 1
 
         if self._current_groups or opt.groups then
-            local job_groups = table.join(self._current_groups or {}, opt.groups)
-            for _, group_name in ipairs(job_groups) do
+            local seen
+            local job_groups
+            local function add_group(group_name)
+                if not group_name then
+                    return
+                end
+                seen = seen or {}
+                if seen[group_name] then
+                    return
+                end
+                seen[group_name] = true
+                job_groups = job_groups or {}
+                table.insert(job_groups, group_name)
                 local groups = self._groups[group_name]
                 if not groups then
                     groups = {}
                     self._groups[group_name] = groups
                 end
                 table.insert(groups, job)
+                -- ensure bridges (if any) are updated for new members
+                self:_attach_job_to_bridges(job, group_name)
+            end
+            for _, group_name in ipairs(self._current_groups or {}) do
+                add_group(group_name)
+            end
+            if opt.groups then
+                for _, group_name in ipairs(opt.groups) do
+                    add_group(group_name)
+                end
             end
+            job._groups = job_groups
         end
     else
         wprint("job(%s): has already been added!", name)
@@ -103,6 +169,17 @@ function jobgraph:remove(name)
         assert(self._size > 0)
         jobs[name] = nil
         dag:remove_vertex(job)
+        if job._groups then
+            for _, group_name in ipairs(job._groups) do
+                local members = self._groups[group_name]
+                if members then
+                    table.remove_if(members, function (_, item) return item == job end)
+                    if #members == 0 then
+                        self._groups[group_name] = nil
+                    end
+                end
+            end
+        end
         self._size = self._size - 1
     end
 end
@@ -164,14 +241,8 @@ function jobgraph:add_orders(...)
             assert(curr, "job(%s) not found in jobgraph(%s)", name, self)
             if prev then
                 if prev_is_group and curr_is_group then
-                    -- we use a bridge job as a node to bridge the two groups.
-                    local bridge = {from_group = prev_name, to_group = name}
-                    for _, job in ipairs(prev) do
-                        dag:add_edge(job, bridge)
-                    end
-                    for _, job in ipairs(curr) do
-                        dag:add_edge(bridge, job)
-                    end
+                    -- we use (and reuse) a bridge job as a node to bridge the two groups.
+                    self:_ensure_bridge(prev_name, name)
                 elseif curr_is_group then
                     for _, job in ipairs(curr) do
                         dag:add_edge(prev, job)
@@ -249,5 +320,5 @@ end
 
 -- new a jobgraph
 function new(name)
-    return jobgraph {name, {}, 0, graph.new(true), {}}
+    return jobgraph {name, {}, 0, graph.new(true), {}, {}, {}, {}}
 end