Merge pull request #4947 from xmake-io/runjobs

Improve runjobs

7 files changed, 253 insertions, 175 deletions

diff --git a/xmake/core/base/dlist.lua b/xmake/core/base/list.lua
index 7967d2afe..e6958f74d 100644
--- a/xmake/core/base/dlist.lua
+++ b/xmake/core/base/list.lua
@@ -15,41 +15,26 @@
 -- Copyright (C) 2015-present, TBOOX Open Source Group.
 --
 -- @author      ruki
--- @file        dlist.lua
+-- @file        list.lua
 --
 
 -- load modules
 local object = require("base/object")
 
 -- define module
-local dlist = dlist or object { _init = {"_length"} } {0}
+local list = list or object { _init = {"_length"} } {0}
 
 -- clear list
-function dlist:clear()
+function list:clear()
     self._length = 0
     self._first  = nil
     self._last   = nil
 end
 
--- push item to tail
-function dlist:push(t)
-    assert(t)
-    if self._last then
-        self._last._next = t
-        t._prev = self._last
-        self._last = t
-    else
-        self._first = t
-        self._last = t
-    end
-    self._length = self._length + 1
-end
-
 -- insert item after the given item
-function dlist:insert(t, after)
-    assert(t)
+function list:insert(t, after)
     if not after then
-        return self:push(t)
+        return self:insert_last(t)
     end
     assert(t ~= after)
     if after._next then
@@ -63,41 +48,8 @@ function dlist:insert(t, after)
     self._length = self._length + 1
 end
 
--- pop item from tail
-function dlist:pop()
-    if not self._last then return end
-    local t = self._last
-    if t._prev then
-        t._prev._next = nil
-        self._last = t._prev
-        t._prev = nil
-    else
-        self._first = nil
-        self._last = nil
-    end
-    self._length = self._length - 1
-    return t
-end
-
--- shift item: 1 2 3 <- 2 3
-function dlist:shift()
-    if not self._first then return end
-    local t = self._first
-    if t._next then
-        t._next._prev = nil
-        self._first = t._next
-        t._next = nil
-    else
-        self._first = nil
-        self._last = nil
-    end
-    self._length = self._length - 1
-    return t
-end
-
--- unshift item: 1 2 -> t 1 2
-function dlist:unshift(t)
-    assert(t)
+-- insert the first item in head
+function list:insert_first(t)
     if self._first then
         self._first._prev = t
         t._next = self._first
@@ -109,9 +61,21 @@ function dlist:unshift(t)
     self._length = self._length + 1
 end
 
+-- insert the last item in tail
+function list:insert_last(t)
+    if self._last then
+        self._last._next = t
+        t._prev = self._last
+        self._last = t
+    else
+        self._first = t
+        self._last = t
+    end
+    self._length = self._length + 1
+end
+
 -- remove item
-function dlist:remove(t)
-    assert(t)
+function list:remove(t)
     if t._next then
         if t._prev then
             t._next._prev = t._prev
@@ -136,18 +100,74 @@ function dlist:remove(t)
     return t
 end
 
+-- remove the first item
+function list:remove_first()
+    if not self._first then
+        return
+    end
+    local t = self._first
+    if t._next then
+        t._next._prev = nil
+        self._first = t._next
+        t._next = nil
+    else
+        self._first = nil
+        self._last = nil
+    end
+    self._length = self._length - 1
+    return t
+end
+
+-- remove last item
+function list:remove_last()
+    if not self._last then
+        return
+    end
+    local t = self._last
+    if t._prev then
+        t._prev._next = nil
+        self._last = t._prev
+        t._prev = nil
+    else
+        self._first = nil
+        self._last = nil
+    end
+    self._length = self._length - 1
+    return t
+end
+
+-- push item to tail
+function list:push(t)
+    self:insert_last(t)
+end
+
+-- pop item from tail
+function list:pop()
+    self:remove_last()
+end
+
+-- shift item: 1 2 3 <- 2 3
+function list:shift()
+    self:remove_first()
+end
+
+-- unshift item: 1 2 -> t 1 2
+function list:unshift(t)
+    self:insert_first(t)
+end
+
 -- get first item
-function dlist:first()
+function list:first()
     return self._first
 end
 
 -- get last item
-function dlist:last()
+function list:last()
     return self._last
 end
 
 -- get next item
-function dlist:next(last)
+function list:next(last)
     if last then
         return last._next
     else
@@ -156,7 +176,7 @@ function dlist:next(last)
 end
 
 -- get the previous item
-function dlist:prev(last)
+function list:prev(last)
     if last then
         return last._prev
     else
@@ -165,12 +185,12 @@ function dlist:prev(last)
 end
 
 -- get list size
-function dlist:size()
+function list:size()
     return self._length
 end
 
 -- is empty?
-function dlist:empty()
+function list:empty()
     return self:size() == 0
 end
 
@@ -178,37 +198,29 @@ end
 --
 -- e.g.
 --
--- for item in dlist:items() do
+-- for item in list:items() do
 --     print(item)
 -- end
 --
-function dlist:items()
-
-    -- init iterator
+function list:items()
     local iter = function (list, item)
         return list:next(item)
     end
-
-    -- return iterator and initialized state
     return iter, self, nil
 end
 
 -- get reverse items
-function dlist:ritems()
-
-    -- init iterator
+function list:ritems()
     local iter = function (list, item)
         return list:prev(item)
     end
-
-    -- return iterator and initialized state
     return iter, self, nil
 end
 
--- new dlist
-function dlist.new()
-    return dlist()
+-- new list
+function list.new()
+    return list()
 end
 
--- return module: dlist
-return dlist
+-- return module: list
+return list
diff --git a/xmake/core/sandbox/modules/import/core/base/dlist.lua b/xmake/core/sandbox/modules/import/core/base/dlist.lua
index 25047206d..924d27ab1 100644
--- a/xmake/core/sandbox/modules/import/core/base/dlist.lua
+++ b/xmake/core/sandbox/modules/import/core/base/dlist.lua
@@ -19,4 +19,4 @@
 --
 
 -- return module
-return require("base/dlist")
+return require("base/list")
diff --git a/xmake/core/sandbox/modules/import/core/base/list.lua b/xmake/core/sandbox/modules/import/core/base/list.lua
new file mode 100644
index 000000000..852fd5231
--- /dev/null
+++ b/xmake/core/sandbox/modules/import/core/base/list.lua
@@ -0,0 +1,22 @@
+--!A cross-platform build utility based on Lua
+--
+-- Licensed under the Apache License, Version 2.0 (the "License");
+-- you may not use this file except in compliance with the License.
+-- You may obtain a copy of the License at
+--
+--     http://www.apache.org/licenses/LICENSE-2.0
+--
+-- Unless required by applicable law or agreed to in writing, software
+-- distributed under the License is distributed on an "AS IS" BASIS,
+-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+-- See the License for the specific language governing permissions and
+-- limitations under the License.
+--
+-- Copyright (C) 2015-present, TBOOX Open Source Group.
+--
+-- @author      ruki
+-- @file        list.lua
+--
+
+-- return module
+return require("base/list")
diff --git a/xmake/core/ui/panel.lua b/xmake/core/ui/panel.lua
index 7baef5c3a..244aae073 100644
--- a/xmake/core/ui/panel.lua
+++ b/xmake/core/ui/panel.lua
@@ -26,7 +26,7 @@ local event  = require("ui/event")
 local point  = require("ui/point")
 local curses = require("ui/curses")
 local action = require("ui/action")
-local dlist  = require("base/dlist")
+local list   = require("base/list")
 
 -- define module
 local panel = panel or view()
@@ -44,7 +44,7 @@ function panel:init(name, bounds)
     self:option_set("selectable", true)
 
     -- init child views
-    self._VIEWS = dlist.new()
+    self._VIEWS = list.new()
 
     -- init views cache
     self._VIEWS_CACHE = {}
diff --git a/xmake/modules/async/runjobs.lua b/xmake/modules/async/runjobs.lua
index 299b868df..1f59a7359 100644
--- a/xmake/modules/async/runjobs.lua
+++ b/xmake/modules/async/runjobs.lua
@@ -154,9 +154,6 @@ function main(name, jobs, opt)
     -- run jobs
     local index = 0
     local count = 0
-    local priority_prev = 0
-    local priority_curr = 0
-    local job_pending = nil
     local abort = false
     local abort_errors
     local progress_wrapper = {}
@@ -190,44 +187,29 @@ function main(name, jobs, opt)
             while index < total_max do
 
                 -- uses job pool?
+                local job
                 local jobname
                 local distccjob = false
                 if not jobs_cb then
 
-                    -- get job priority
-                    local job, priority
-                    if job_pending then
-                        job = job_pending
-                        priority = priority_prev
-                    else
-                        job, priority = jobs:pop()
-                    end
-                    if not job then
-                        break
-                    end
-
-                    -- priority changed? we need to wait all running jobs exited
-                    priority_curr = priority or priority_prev
-                    assert(priority_curr >= priority_prev, "runjobs: invalid priority(%d < %d)!", priority_curr, priority_prev)
-                    if priority_curr > priority_prev then
-                        job_pending = job
-                        break
-                    end
-
                     -- we can only continue to run the job with distcc if local jobs are full
                     if distcc and index >= local_max then
                         if job.distcc then
                             distccjob = true
                         else
-                            job_pending = job
                             break
                         end
                     end
 
+                    -- get free job
+                    job = jobs:getfree()
+                    if not job then
+                        break
+                    end
+
                     -- get run function
                     jobfunc = job.run
                     jobname = job.name
-                    job_pending = nil
                 else
                     jobname = tostring(index)
                 end
@@ -287,20 +269,22 @@ function main(name, jobs, opt)
                                     end
                                 end
                             end
+                        },
+                        finally
+                        {
+                            function ()
+                                if job then
+                                    jobs:remove(job)
+                                end
+                            end
                         }
                     }
                 end, index)
             end
         end)
 
-        -- only need one job exited if be same priority
-        if priority_curr == priority_prev then
-            scheduler.co_group_wait(group_name, {limit = 1})
-        else
-            -- need to wait all running jobs exited first if be different priority
-            scheduler.co_group_wait(group_name)
-            priority_prev = priority_curr
-        end
+        -- wait for free jobs
+        scheduler.co_group_wait(group_name, {limit = 1})
     end
 
     -- wait all jobs exited
diff --git a/xmake/modules/private/async/jobpool.lua b/xmake/modules/private/async/jobpool.lua
index 7f9067343..1358e0e12 100644
--- a/xmake/modules/private/async/jobpool.lua
+++ b/xmake/modules/private/async/jobpool.lua
@@ -20,10 +20,16 @@
 
 -- imports
 import("core.base.object")
+import("core.base.list")
 import("core.base.hashset")
 
 -- define module
-local jobpool = jobpool or object {_init = {"_size", "_rootjob", "_leafjobs", "_poprefs"}}
+local jobpool = jobpool or object {_init = {"_size", "_rootjob", "_leafjobs"}}
+
+-- the job status
+local JOB_STATUS_FREE     = 1
+local JOB_STATUS_PENDING  = 2
+local JOB_STATUS_FINISHED = 3
 
 -- get jobs size
 function jobpool:size()
@@ -45,7 +51,7 @@ end
 --
 function jobpool:newjob(name, run, opt)
     opt = opt or {}
-    return {name = name, run = run, distcc = opt.distcc}
+    return {name = name, run = run, distcc = opt.distcc, status = JOB_STATUS_FREE}
 end
 
 -- add run job to the given job node
@@ -60,7 +66,7 @@ end
 --
 function jobpool:addjob(name, run, opt)
     opt = opt or {}
-    return self:add({name = name, run = run, distcc = opt.distcc}, opt.rootjob)
+    return self:add({name = name, run = run, distcc = opt.distcc, status = JOB_STATUS_FREE}, opt.rootjob)
 end
 
 -- add job to the given job node
@@ -95,30 +101,73 @@ function jobpool:add(job, rootjob)
     return job
 end
 
--- pop job without deps at leaf node
-function jobpool:pop()
-
-    -- no jobs?
+-- get a free job from the leaf jobs
+function jobpool:getfree()
     if self:size() == 0 then
         return
     end
 
-    -- init leaf jobs first
-    local leafjobs = self._leafjobs
-    if #leafjobs == 0 then
-        local refs = {}
-        self:_genleafjobs(self:rootjob(), leafjobs, refs)
+    -- get a free job from the leaf jobs
+    local leafjobs = self:_getleafjobs()
+    if not leafjobs:empty() then
+        -- try to get next free job fastly
+        if self._nextfree then
+            local job = self._nextfree
+            local nextfree = leafjobs:prev(job)
+            if nextfree ~= job and self:_isfree(nextfree) then
+                self._nextfree = nextfree
+            else
+                self._nextfree = nil
+            end
+            job.status = JOB_STATUS_PENDING
+            return job
+        end
+        -- find the next free job
+        local removed_jobs = {}
+        for job in leafjobs:ritems() do
+            if self:_isfree(job) then
+                local nextfree = leafjobs:prev(job)
+                if nextfree ~= job and self:_isfree(nextfree) then
+                    self._nextfree = nextfree
+                end
+                job.status = JOB_STATUS_PENDING
+                return job
+            elseif job.group or job.status == JOB_STATUS_FINISHED then
+                table.insert(removed_jobs, job)
+            end
+        end
+        -- not found? if remove group and referenced node exist,
+        -- we try to remove them and find the next free job again
+        if #removed_jobs > 0 then
+            for _, job in ipairs(removed_jobs) do
+                self:remove(job)
+            end
+            for job in leafjobs:ritems() do
+                if self:_isfree(job) then
+                    local nextfree = leafjobs:prev(job)
+                    if nextfree ~= job and self:_isfree(nextfree) then
+                        self._nextfree = nextfree
+                    end
+                    job.status = JOB_STATUS_PENDING
+                    return job
+                end
+            end
+        end
     end
+end
 
-    -- pop a job from the leaf jobs
-    if #leafjobs > 0 then
+-- remove the given job from the leaf jobs
+function jobpool:remove(job)
+    assert(self:size() > 0)
+    local leafjobs = self:_getleafjobs()
+    if not leafjobs:empty() then
+        assert(job ~= self._nextfree)
 
-        -- get job
-        local job = leafjobs[#leafjobs]
-        table.remove(leafjobs, #leafjobs)
+        -- remove this job from leaf jobs
+        job.status = JOB_STATUS_FINISHED
+        leafjobs:remove(job)
 
-        -- get priority and parents node
-        local priority = job._priority or 0
+        -- get parents node
         local parents = assert(job._parents, "invalid job without parents node!")
 
         -- update all parents nodes
@@ -126,27 +175,13 @@ function jobpool:pop()
             -- we need to avoid adding it to leafjobs repeatly, it will cause dead-loop when poping group job
             -- @see https://github.com/xmake-io/xmake/issues/2740
             if not p._leaf then
-                p._priority = math.max(p._priority or 0, priority + 1)
                 p._deps:remove(job)
                 if p._deps:empty() and self._size > 0 then
                     p._leaf = true
-                    table.insert(leafjobs, 1, p)
+                    leafjobs:insert_first(p)
                 end
             end
         end
-
-        -- is group node or referenced node (it has been popped once) ?
-        local poprefs = self._poprefs
-        local jobkey = tostring(job)
-        if job.group or poprefs[jobkey] then
-            -- pop the next real job
-            return self:pop()
-        else
-            -- pop this job
-            self._size = self._size - 1
-            poprefs[jobkey] = true
-            return job, priority
-        end
     end
 end
 
@@ -178,6 +213,26 @@ function jobpool:group_leave()
     end
 end
 
+-- is free job?
+-- we need to ignore group node (empty job) and referenced node (finished job)
+function jobpool:_isfree(job)
+    if job and job.status == JOB_STATUS_FREE and not job.group then
+        return true
+    end
+end
+
+-- get leaf jobs
+function jobpool:_getleafjobs()
+    local leafjobs = self._leafjobs
+    if leafjobs == nil then
+        leafjobs = list.new()
+        local refs = {}
+        self:_genleafjobs(self:rootjob(), leafjobs, refs)
+        self._leafjobs = leafjobs
+    end
+    return leafjobs
+end
+
 -- generate all leaf jobs from the given job
 function jobpool:_genleafjobs(job, leafjobs, refs)
     local deps = job._deps
@@ -191,7 +246,7 @@ function jobpool:_genleafjobs(job, leafjobs, refs)
         end
     else
         job._leaf = true
-        table.insert(leafjobs, job)
+        leafjobs:insert_last(job)
     end
 end
 
@@ -232,5 +287,5 @@ end
 
 -- new a jobpool
 function new()
-    return jobpool {0, {name = "root"}, {}, {}}
+    return jobpool {0, {name = "root"}, nil}
 end
diff --git a/xmake/rules/c++/modules/modules_support/builder.lua b/xmake/rules/c++/modules/modules_support/builder.lua
index c56ac0731..f651e2b69 100644
--- a/xmake/rules/c++/modules/modules_support/builder.lua
+++ b/xmake/rules/c++/modules/modules_support/builder.lua
@@ -80,30 +80,29 @@ end
 
 -- check if flags are compatible for module reuse
 function _are_flags_compatible(target, other, cppfile)
-  local compinst1 = target:compiler("cxx")
-  local flags1 = compinst1:compflags({sourcefile = cppfile, target = target})
+    local compinst1 = target:compiler("cxx")
+    local flags1 = compinst1:compflags({sourcefile = cppfile, target = target})
 
-  local compinst2 = other:compiler("cxx")
-  local flags2 = compinst2:compflags({sourcefile = cppfile, target = other})
+    local compinst2 = other:compiler("cxx")
+    local flags2 = compinst2:compflags({sourcefile = cppfile, target = other})
 
-  -- strip unrelevent flags
-  flags1 = compiler_support.strip_flags(target, flags1)
-  flags2 = compiler_support.strip_flags(target, flags2)
+    -- strip unrelevent flags
+    flags1 = compiler_support.strip_flags(target, flags1)
+    flags2 = compiler_support.strip_flags(target, flags2)
 
-  if #flags1 ~= #flags2 then
-      return false
-  end
-
-  table.sort(flags1)
-  table.sort(flags2)
+    if #flags1 ~= #flags2 then
+        return false
+    end
 
-  for i = 1, #flags1 do
-      if flags1[i] ~= flags2[i] then
-          return false
-      end
-  end
+    table.sort(flags1)
+    table.sort(flags2)
 
-  return true
+    for i = 1, #flags1 do
+        if flags1[i] ~= flags2[i] then
+            return false
+        end
+    end
+    return true
 end
 
 -- try to reuse modules from other target
@@ -264,12 +263,18 @@ function build_modules_for_batchjobs(target, batchjobs, sourcebatch, modules, op
     opt.rootjob = batchjobs:group_leave() or opt.rootjob
     batchjobs:group_enter(target:name() .. "/build_modules", {rootjob = opt.rootjob})
 
-    batchjobs:addjob(target:name() .. "_populate_module_map", function(_, _)
-        _try_reuse_modules(target, modules)
-        _builder(target).populate_module_map(target, modules)
-    end, {rootjob = opt.rootjob})
-
+    -- add populate module job
     local modulesjobs = {}
+    local populate_jobname = target:name() .. "_populate_module_map"
+    modulesjobs[populate_jobname] = {
+        name = populate_jobname,
+        job = batchjobs:newjob(populate_jobname, function(_, _)
+            _try_reuse_modules(target, modules)
+            _builder(target).populate_module_map(target, modules)
+        end)
+    }
+
+    -- add module jobs
     _build_modules(target, sourcebatch, modules, table.join(opt, {
        build_module = function(deps, module, name, objectfile, cppfile)
         local job_name = name and target:name() .. name or cppfile