Merge branch 'terencehill/il_loop_fix' into 'master'

Implement safe removal of elements of an intrusive list while looping over them

Closes #2790

See merge request xonotic/xonotic-data.pk3dir!1148

diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml
index 887b0691ef2e1423e6d9642be74126d733985390..8ba5c18061a8b807617a4ab4c6b602c2ae7c154a 100644 (file)
--- a/.gitlab-ci.yml
+++ b/.gitlab-ci.yml
@@ -75,7 +75,7 @@ test_sv_game:
     - wget -nv -O data/maps/stormkeep.waypoints https://gitlab.com/xonotic/xonotic-maps.pk3dir/raw/master/maps/stormkeep.waypoints\r
     - wget -nv -O data/maps/stormkeep.waypoints.cache https://gitlab.com/xonotic/xonotic-maps.pk3dir/raw/master/maps/stormkeep.waypoints.cache\r
 \r
-    - EXPECT=55338fabce73c671336171e6cb055f74\r
+    - EXPECT=fe5dec36cb304c55acee73afd1e09c0a\r
     - HASH=$(${ENGINE} +timestamps 1 +exec serverbench.cfg\r
       | tee /dev/stderr\r
       | sed -e 's,^\[[^]]*\] ,,'\r

diff --git a/qcsrc/lib/intrusivelist.qh b/qcsrc/lib/intrusivelist.qh
index 63a21565601085c4e34ce72c8aff021ae5fa70e6..d3a56ba4df9f0b1e499bf0efc1f67d980487635e 100644 (file)
--- a/qcsrc/lib/intrusivelist.qh
+++ b/qcsrc/lib/intrusivelist.qh
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "iter.qh"
+#include "test.qh"
 
 /**
  * Maximum amount of creatable lists.
@@ -27,6 +28,7 @@ CLASS(IntrusiveList, Object)
        ATTRIB(IntrusiveList, il_tail, entity);
        ATTRIB(IntrusiveList, il_nextfld, .entity, nil);
        ATTRIB(IntrusiveList, il_prevfld, .entity, nil);
+       ATTRIB(IntrusiveList, il_loop_item, entity, NULL);
        INIT(IntrusiveList) { IL_INIT(this); }
        DESTRUCTOR(IntrusiveList) { IL_DTOR(this); }
 ENDCLASS(IntrusiveList)
@@ -104,6 +106,9 @@ entity IL_POP(IntrusiveList this)
        entity prev = it.(il_prev);
        if (prev) (this.il_tail = prev).(il_next) = NULL;
        else this.il_head = this.il_tail = NULL;
+       if (this.il_loop_item == it)
+               this.il_loop_item = NULL;
+       it.(il_prev) = NULL;
        return it;
 }
 
@@ -122,6 +127,9 @@ entity IL_SHIFT(IntrusiveList this)
        entity next = it.(il_next);
        if (next) (this.il_head = next).(il_prev) = NULL;
        else this.il_head = this.il_tail = NULL;
+       if (this.il_loop_item == it)
+               this.il_loop_item = it.(il_next);
+       it.(il_next) = NULL;
        return it;
 }
 
@@ -142,6 +150,8 @@ void IL_REMOVE(IntrusiveList this, entity it)
        next ? next.(il_prev) = prev : this.il_tail = prev;
        prev ? prev.(il_next) = next : this.il_head = next;
        LOG_DEBUGF("remove %i (%i :: %i), head: %i -> %i, tail: %i -> %i", it, it.(il_prev), it.(il_next), ohead, this.il_head, otail, this.il_tail);
+       if (this.il_loop_item == it)
+               this.il_loop_item = it.(il_next);
        it.(il_next) = it.(il_prev) = NULL;
 }
 
@@ -150,11 +160,17 @@ void IL_REMOVE(IntrusiveList this, entity it)
  */
 #define IL_CLEAR(this) \
        MACRO_BEGIN \
-               IntrusiveList __il = this; \
-               assert(__il); \
-               .entity il_prev = __il.il_prevfld; \
-               IL_EACH(__il, true, it.(il_next) = it.(il_prev) = NULL); \
-               __il.il_head = __il.il_tail = NULL; \
+               IntrusiveList _il = this; \
+               assert(_il); \
+               .entity il_prev = _il.il_prevfld; \
+               .entity il_next = _il.il_nextfld; \
+               noref int i = 0; \
+               for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
+               { \
+                       _next = _it.(il_next); \
+                       _it.(il_next) = _it.(il_prev) = NULL; \
+               } \
+               _il.il_head = _il.il_tail = NULL; \
        MACRO_END
 
 /**
@@ -172,12 +188,20 @@ void IL_REMOVE(IntrusiveList this, entity it)
                assert(_il); \
                .entity il_next = _il.il_nextfld; \
                noref int i = 0; \
+               entity il_loop_item_save = this.il_loop_item; \
+               this.il_loop_item = NULL; \
                for (entity _next, _it = _il.il_head; _it; (_it = _next, ++i)) \
                { \
                        const noref entity it = _it; \
+                       this.il_loop_item = it; \
                        _next = it.(il_next); \
                        if (cond) { LAMBDA(body) } \
+                       if (this.il_loop_item != it) /* current item removed? */ \
+                               _next = this.il_loop_item; \
+                       else \
+                               _next = it.(il_next); /* in case next item has changed */ \
                } \
+               this.il_loop_item = il_loop_item_save; \
        MACRO_END
 
 .int il_id;
@@ -246,6 +270,15 @@ void IL_ENDFRAME()
 #endif
 }
 
+// clears any IL data from an entity (not an intrusive list)
+// it should be used only in very particular cases such as after a copyentity call
+void IL_REMOVE_RAW(entity it)
+{
+       it.il_lists = '0 0 0';
+       for (int i = 0; i < IL_MAX * 2; ++i)
+               it.il_links_flds[i] = nil;
+}
+
 // called when an entity is deleted with delete() / remove()
 // or when a player disconnects
 void ONREMOVE(entity this)
@@ -261,3 +294,78 @@ void ONREMOVE(entity this)
                }
        }
 }
+
+
+#define IL_TEST_BUILD() s = il_test_build(il_test, ent1, ent2, ent3, ent4, ent5)
+
+string il_test_build(entity il_test, entity ent1, entity ent2, entity ent3, entity ent4, entity ent5)
+{
+       IL_CLEAR(il_test);
+       IL_PUSH(il_test, ent1);
+       IL_PUSH(il_test, ent2);
+       IL_PUSH(il_test, ent3);
+       IL_PUSH(il_test, ent4);
+       IL_PUSH(il_test, ent5);
+       return "";
+}
+
+TEST(intrusivelist, ModificationsWhileLooping)
+{
+       IntrusiveList il_test = IL_NEW();
+       entity ent1 = new(1), ent2 = new(2), ent3 = new(3), ent4 = new(4), ent5 = new(5);
+       string s;
+
+       IL_TEST_BUILD();
+       IL_EACH(il_test, true,
+       {
+               s = strcat(s, it.classname);
+               if (it == ent2) IL_REMOVE(il_test, ent3);
+               if (it == ent4) IL_PUSH(il_test, ent3);
+       });
+       EXPECT_TRUE(s == "12453");
+
+       IL_TEST_BUILD();
+       IL_EACH(il_test, true,
+       {
+               s = strcat(s, it.classname);
+               if (it == ent2) IL_REMOVE(il_test, ent2);
+               if (it == ent3) IL_REMOVE(il_test, ent3);
+               if (it == ent3) IL_REMOVE(il_test, ent4);
+               if (it == ent5) IL_POP(il_test);
+       });
+       EXPECT_TRUE(s == "1235");
+
+       IL_TEST_BUILD();
+       IL_REMOVE(il_test, ent5);
+       IL_EACH(il_test, true,
+       {
+               s = strcat(s, it.classname);
+               if (it == ent1) IL_SHIFT(il_test);
+               if (it == ent4) IL_POP(il_test);
+       });
+       EXPECT_TRUE(s == "1234");
+
+       IL_TEST_BUILD();
+       IL_EACH(il_test, true,
+       {
+               s = strcat(s, it.classname);
+               if (it == ent2)
+                       IL_EACH(il_test, true,
+                       {
+                               s = strcat(s, it.classname);
+                               if (it == ent3)
+                                       IL_EACH(il_test, true,
+                                       {
+                                               s = strcat(s, it.classname);
+                                       });
+                               if (it == ent4)
+                                       break;
+                       });
+       });
+       EXPECT_TRUE(s == "12123123454345");
+
+       IL_DELETE(il_test);
+       delete(ent1); delete(ent2); delete(ent3); delete(ent4); delete(ent5);
+
+       SUCCEED();
+}

diff --git a/qcsrc/lib/oo.qh b/qcsrc/lib/oo.qh
index a2cef664bad3b72f9936ab371b12087c1e362027..9048202fe28f1da4b5ce0fb753cda1b6aca830b1 100644 (file)
--- a/qcsrc/lib/oo.qh
+++ b/qcsrc/lib/oo.qh
@@ -77,6 +77,13 @@ ACCUMULATE void ONREMOVE(entity this) {}
     /* this = NULL; */  \
 MACRO_END
 
+void IL_REMOVE_RAW(entity it);
+void copyentity_qc(entity src, entity dst)
+{
+       copyentity(src, dst); // builtin function
+       IL_REMOVE_RAW(dst);
+}
+
 entity _clearentity_ent;
 STATIC_INIT(clearentity)
 {
@@ -88,7 +95,7 @@ void clearentity(entity e)
                int n = e.entnum;
 #endif
        bool was_pure = is_pure(e);
-       copyentity(_clearentity_ent, e);
+       copyentity_qc(_clearentity_ent, e);
        if (!was_pure) make_impure(e);
 #ifdef CSQC
                e.entnum = n;
@@ -175,7 +182,7 @@ void clearentity(entity e)
        {                                                                                              \
                if (cname##_vtbl && !this.transmute)                                                       \
                {                                                                                          \
-                       copyentity(cname##_vtbl, this);                                                        \
+                       copyentity_qc(cname##_vtbl, this);                                                     \
                        return;                                                                                \
                }                                                                                          \
                spawn##base##_static(this);                                                                \

diff --git a/qcsrc/lib/spawnfunc.qh b/qcsrc/lib/spawnfunc.qh
index c9bfebabd415c4414eea269638f686fbd4a94f6b..2d9392dada941f7f921fe839bcb67891a8c14148 100644 (file)
--- a/qcsrc/lib/spawnfunc.qh
+++ b/qcsrc/lib/spawnfunc.qh
@@ -73,7 +73,7 @@ noref string __fullspawndata;
     void __spawnfunc_spawn(entity prototype)
     {
         entity e = new(clone);
-        copyentity(prototype, e);
+        copyentity_qc(prototype, e);
         IL_PUSH(g_map_entities, e);
         #define X(T, fld, def) { e.fld = e.__spawnfunc_##fld; e.__spawnfunc_##fld = def; }
         SPAWNFUNC_INTERNAL_FIELDS(X);

diff --git a/qcsrc/server/weapons/spawning.qc b/qcsrc/server/weapons/spawning.qc
index 0685062f58787167e8a463576ba98638becf72eb..dc7b110e2cc2857da219b18290871de34cc515f0 100644 (file)
--- a/qcsrc/server/weapons/spawning.qc
+++ b/qcsrc/server/weapons/spawning.qc
@@ -61,8 +61,6 @@ void weapon_defaultspawnfunc(entity this, Weapon wpn)
                                {
                                        entity replacement = spawn();
                                        Item_CopyFields(this, replacement);
-                                       // DO NOT USE, causes #2792
-                                       //copyentity(this, replacement);
                                        replacement.m_isreplaced = true;
                                        weapon_defaultspawnfunc(replacement, wep);
                                }

diff --git a/qcsrc/server/weapons/weaponsystem.qc b/qcsrc/server/weapons/weaponsystem.qc
index fc2c3979c2b15226d5242fc95fdc641ad658b53e..df6490128aa993ac84239930a0a477336d078fc0 100644 (file)
--- a/qcsrc/server/weapons/weaponsystem.qc
+++ b/qcsrc/server/weapons/weaponsystem.qc
@@ -670,7 +670,7 @@ void W_AttachToShotorg(entity actor, .entity weaponentity, entity flash, vector
        setorigin(flash, offset);
 
        entity xflash = spawn();
-       copyentity(flash, xflash);
+       copyentity_qc(flash, xflash);
 
        flash.viewmodelforclient = actor;