Rope concatenation for Lua 5.1 inspired by SquidDev/Cobalt

lua5.1-ropes.patch

diff -ruN lua-5.1.5-clean/src/Makefile lua-5.1.5-ropes/src/Makefile
--- lua-5.1.5-clean/src/Makefile	2012-02-13 15:41:22.000000000 -0500
+++ lua-5.1.5-ropes/src/Makefile	2021-06-19 08:03:46.000000000 -0400
@@ -135,7 +135,7 @@
 ldo.o: ldo.c lua.h luaconf.h ldebug.h lstate.h lobject.h llimits.h ltm.h \
   lzio.h lmem.h ldo.h lfunc.h lgc.h lopcodes.h lparser.h lstring.h \
   ltable.h lundump.h lvm.h
-ldump.o: ldump.c lua.h luaconf.h lobject.h llimits.h lstate.h ltm.h \
+ldump.o: ldump.c lua.h luaconf.h lobject.h llimits.h lstate.h lstring.h ltm.h \
   lzio.h lmem.h lundump.h
 lfunc.o: lfunc.c lua.h luaconf.h lfunc.h lobject.h llimits.h lgc.h lmem.h \
   lstate.h ltm.h lzio.h
@@ -162,7 +162,7 @@
   ltm.h lzio.h lstring.h lgc.h
 lstrlib.o: lstrlib.c lua.h luaconf.h lauxlib.h lualib.h
 ltable.o: ltable.c lua.h luaconf.h ldebug.h lstate.h lobject.h llimits.h \
-  ltm.h lzio.h lmem.h ldo.h lgc.h ltable.h
+  ltm.h lzio.h lmem.h ldo.h lgc.h ltable.h lstring.h
 ltablib.o: ltablib.c lua.h luaconf.h lauxlib.h lualib.h
 ltm.o: ltm.c lua.h luaconf.h lobject.h llimits.h lstate.h ltm.h lzio.h \
   lmem.h lstring.h lgc.h ltable.h
diff -ruN lua-5.1.5-clean/src/lapi.c lua-5.1.5-ropes/src/lapi.c
--- lua-5.1.5-clean/src/lapi.c	2008-07-04 14:41:18.000000000 -0400
+++ lua-5.1.5-ropes/src/lapi.c	2021-06-19 08:04:27.000000000 -0400
@@ -241,7 +241,7 @@
 
 LUA_API int lua_type (lua_State *L, int idx) {
   StkId o = index2adr(L, idx);
-  return (o == luaO_nilobject) ? LUA_TNONE : ttype(o);
+  return (o == luaO_nilobject) ? LUA_TNONE : (ttisrope(o) ? LUA_TSTRING : ttype(o));
 }
 
 
@@ -260,13 +260,13 @@
 LUA_API int lua_isnumber (lua_State *L, int idx) {
   TValue n;
   const TValue *o = index2adr(L, idx);
-  return tonumber(o, &n);
+  return tonumber(L, o, &n);
 }
 
 
 LUA_API int lua_isstring (lua_State *L, int idx) {
   int t = lua_type(L, idx);
-  return (t == LUA_TSTRING || t == LUA_TNUMBER);
+  return (t == LUA_TSTRING || t == LUA_TNUMBER || t == LUA_TROPE);
 }
 
 
@@ -313,7 +313,7 @@
 LUA_API lua_Number lua_tonumber (lua_State *L, int idx) {
   TValue n;
   const TValue *o = index2adr(L, idx);
-  if (tonumber(o, &n))
+  if (tonumber(L, o, &n))
     return nvalue(o);
   else
     return 0;
@@ -323,7 +323,7 @@
 LUA_API lua_Integer lua_tointeger (lua_State *L, int idx) {
   TValue n;
   const TValue *o = index2adr(L, idx);
-  if (tonumber(o, &n)) {
+  if (tonumber(L, o, &n)) {
     lua_Integer res;
     lua_Number num = nvalue(o);
     lua_number2integer(res, num);
@@ -362,6 +362,7 @@
   StkId o = index2adr(L, idx);
   switch (ttype(o)) {
     case LUA_TSTRING: return tsvalue(o)->len;
+    case LUA_TROPE: return trvalue(o)->len;
     case LUA_TUSERDATA: return uvalue(o)->len;
     case LUA_TTABLE: return luaH_getn(hvalue(o));
     case LUA_TNUMBER: {
@@ -559,7 +560,7 @@
   lua_lock(L);
   t = index2adr(L, idx);
   api_check(L, ttistable(t));
-  setobj2s(L, L->top - 1, luaH_get(hvalue(t), L->top - 1));
+  setobj2s(L, L->top - 1, luaH_get(L, hvalue(t), L->top - 1));
   lua_unlock(L);
 }
 
@@ -597,6 +598,9 @@
     case LUA_TUSERDATA:
       mt = uvalue(obj)->metatable;
       break;
+    case LUA_TROPE:
+      mt = G(L)->mt[LUA_TSTRING];
+      break;
     default:
       mt = G(L)->mt[ttype(obj)];
       break;
diff -ruN lua-5.1.5-clean/src/ldebug.c lua-5.1.5-ropes/src/ldebug.c
--- lua-5.1.5-clean/src/ldebug.c	2008-05-08 12:56:26.000000000 -0400
+++ lua-5.1.5-ropes/src/ldebug.c	2021-06-19 07:59:07.000000000 -0400
@@ -579,15 +579,15 @@ void luaG_typeerror (lua_State *L, const TValue *o, const char *op) {
 
 
 void luaG_concaterror (lua_State *L, StkId p1, StkId p2) {
-  if (ttisstring(p1) || ttisnumber(p1)) p1 = p2;
+  if (ttisstring(p1) || ttisnumber(p1) || ttisrope(p1)) p1 = p2;
   lua_assert(!ttisstring(p1) && !ttisnumber(p1));
   luaG_typeerror(L, p1, "concatenate");
 }
 
 
 void luaG_aritherror (lua_State *L, const TValue *p1, const TValue *p2) {
   TValue temp;
-  if (luaV_tonumber(p1, &temp) == NULL)
+  if (luaV_tonumber(L, p1, &temp) == NULL)
     p2 = p1;  /* first operand is wrong */
   luaG_typeerror(L, p2, "perform arithmetic on");
 }
diff -ruN lua-5.1.5-clean/src/ldump.c lua-5.1.5-ropes/src/ldump.c
--- lua-5.1.5-clean/src/ldump.c	2007-12-27 08:02:25.000000000 -0500
+++ lua-5.1.5-ropes/src/ldump.c	2021-06-19 07:59:07.000000000 -0400
@@ -13,6 +13,7 @@
 
 #include "lobject.h"
 #include "lstate.h"
+#include "lstring.h"
 #include "lundump.h"
 
 typedef struct {
@@ -98,6 +99,9 @@
    case LUA_TSTRING:
 	DumpString(rawtsvalue(o),D);
 	break;
+   case LUA_TROPE:
+   DumpString(luaS_build(D->L, rawtrvalue(o)), D);
+   break;
    default:
 	lua_assert(0);			/* cannot happen */
 	break;
diff -ruN lua-5.1.5-clean/src/lgc.c lua-5.1.5-ropes/src/lgc.c
--- lua-5.1.5-clean/src/lgc.c	2011-03-18 14:05:38.000000000 -0400
+++ lua-5.1.5-ropes/src/lgc.c	2021-06-19 18:47:38.000000000 -0400
@@ -107,6 +107,11 @@
       g->gray = o;
       break;
     }
+    case LUA_TROPE: {
+      gco2tr(o)->gclist = g->gray;
+      g->gray = o;
+      break;
+    }
     default: lua_assert(0);
   }
 }
@@ -188,8 +193,8 @@
       removeentry(n);  /* remove empty entries */
     else {
       lua_assert(!ttisnil(gkey(n)));
-      if (!weakkey) markvalue(g, gkey(n));
-      if (!weakvalue) markvalue(g, gval(n));
+      if (!weakkey || ttisrope(gkey(n))) markvalue(g, gkey(n));
+      if (!weakvalue || ttisrope(gval(n))) markvalue(g, gval(n));
     }
   }
   return weakkey || weakvalue;
@@ -270,6 +275,19 @@
 }
 
 
+static void traverserope (global_State *g, TRope *r) {
+  if (r->tsr.left) {
+    if (r->tsr.left->tsr.tt == LUA_TSTRING) stringmark(cast(TString *, r->tsr.left));
+    else markobject(g, r->tsr.left);
+  }
+  if (r->tsr.right) {
+    if (r->tsr.right->tsr.tt == LUA_TSTRING) stringmark(cast(TString *, r->tsr.right));
+    else markobject(g, r->tsr.right);
+  }
+  if (r->tsr.res) stringmark(r->tsr.res);
+}
+
+
 /*
 ** traverse one gray object, turning it to black.
 ** Returns `quantity' traversed.
@@ -315,6 +328,12 @@
                              sizeof(LocVar) * p->sizelocvars +
                              sizeof(TString *) * p->sizeupvalues;
     }
+    case LUA_TROPE: {
+      TRope *r = rawgco2tr(o);
+      g->gray = r->tsr.gclist;
+      traverserope(g, r);
+      return sizeof(TRope);
+    }
     default: lua_assert(0); return 0;
   }
 }
@@ -334,11 +353,14 @@
 ** other objects: if really collected, cannot keep them; for userdata
 ** being finalized, keep them in keys, but not in values
 */
-static int iscleared (const TValue *o, int iskey) {
+static int iscleared (global_State *g, const TValue *o, int iskey) {
   if (!iscollectable(o)) return 0;
   if (ttisstring(o)) {
     stringmark(rawtsvalue(o));  /* strings are `values', so are never weak */
     return 0;
+  } else if (ttisrope(o)) {
+    markobject(g, o);  /* ropes are strings -> which are values, so are never weak either */
+    return 0;
   }
   return iswhite(gcvalue(o)) ||
     (ttisuserdata(o) && (!iskey && isfinalized(uvalue(o))));
@@ -348,7 +370,7 @@
 /*
 ** clear collected entries from weaktables
 */
-static void cleartable (GCObject *l) {
+static void cleartable (global_State *g, GCObject *l) {
   while (l) {
     Table *h = gco2h(l);
     int i = h->sizearray;
@@ -357,7 +379,7 @@
     if (testbit(h->marked, VALUEWEAKBIT)) {
       while (i--) {
         TValue *o = &h->array[i];
-        if (iscleared(o, 0))  /* value was collected? */
+        if (iscleared(g, o, 0))  /* value was collected? */
           setnilvalue(o);  /* remove value */
       }
     }
@@ -365,7 +387,7 @@
     while (i--) {
       Node *n = gnode(h, i);
       if (!ttisnil(gval(n)) &&  /* non-empty entry? */
-          (iscleared(key2tval(n), 1) || iscleared(gval(n), 0))) {
+          (iscleared(g, key2tval(n), 1) || iscleared(g, gval(n), 0))) {
         setnilvalue(gval(n));  /* remove value ... */
         removeentry(n);  /* remove entry from table */
       }
@@ -380,6 +402,7 @@
     case LUA_TPROTO: luaF_freeproto(L, gco2p(o)); break;
     case LUA_TFUNCTION: luaF_freeclosure(L, gco2cl(o)); break;
     case LUA_TUPVAL: luaF_freeupval(L, gco2uv(o)); break;
+    case LUA_TROPE: luaS_freerope(L, rawgco2tr(o)); break;
     case LUA_TTABLE: luaH_free(L, gco2h(o)); break;
     case LUA_TTHREAD: {
       lua_assert(gco2th(o) != L && gco2th(o) != G(L)->mainthread);
@@ -543,7 +566,7 @@
   udsize = luaC_separateudata(L, 0);  /* separate userdata to be finalized */
   marktmu(g);  /* mark `preserved' userdata */
   udsize += propagateall(g);  /* remark, to propagate `preserveness' */
-  cleartable(g->weak);  /* remove collected objects from weak tables */
+  cleartable(g, g->weak);  /* remove collected objects from weak tables */
   /* flip current white */
   g->currentwhite = cast_byte(otherwhite(g));
   g->sweepstrgc = 0;
diff -ruN lua-5.1.5-clean/src/lobject.c lua-5.1.5-ropes/src/lobject.c
--- lua-5.1.5-clean/src/lobject.c	2007-12-27 08:02:25.000000000 -0500
+++ lua-5.1.5-ropes/src/lobject.c	2021-06-19 11:00:46.000000000 -0400
@@ -165,6 +165,7 @@
   pushstr(L, fmt);
   luaV_concat(L, n+1, cast_int(L->top - L->base) - 1);
   L->top -= n;
+  if (ttisrope(L->top - 1)) setsvalue(L, L->top - 1, luaS_build(L, rawtrvalue(L->top - 1)));
   return svalue(L->top - 1);
 }
 
diff -ruN lua-5.1.5-clean/src/lobject.h lua-5.1.5-ropes/src/lobject.h
--- lua-5.1.5-clean/src/lobject.h	2008-08-06 09:29:48.000000000 -0400
+++ lua-5.1.5-ropes/src/lobject.h	2021-06-19 07:59:07.000000000 -0400
@@ -28,6 +28,7 @@
 #define LUA_TPROTO	(LAST_TAG+1)
 #define LUA_TUPVAL	(LAST_TAG+2)
 #define LUA_TDEADKEY	(LAST_TAG+3)
+#define LUA_TROPE   (LAST_TAG+4)
 
 
 /*
@@ -85,6 +86,7 @@
 #define ttisuserdata(o)	(ttype(o) == LUA_TUSERDATA)
 #define ttisthread(o)	(ttype(o) == LUA_TTHREAD)
 #define ttislightuserdata(o)	(ttype(o) == LUA_TLIGHTUSERDATA)
+#define ttisrope(o) (ttype(o) == LUA_TROPE)
 
 /* Macros to access values */
 #define ttype(o)	((o)->tt)
@@ -99,6 +101,8 @@
 #define hvalue(o)	check_exp(ttistable(o), &(o)->value.gc->h)
 #define bvalue(o)	check_exp(ttisboolean(o), (o)->value.b)
 #define thvalue(o)	check_exp(ttisthread(o), &(o)->value.gc->th)
+#define rawtrvalue(o)  check_exp(ttisrope(o), &(o)->value.gc->r)
+#define trvalue(o)	(&rawtrvalue(o)->tsr)
 
 #define l_isfalse(o)	(ttisnil(o) || (ttisboolean(o) && bvalue(o) == 0))
 
@@ -155,6 +159,11 @@
     i_o->value.gc=cast(GCObject *, (x)); i_o->tt=LUA_TPROTO; \
     checkliveness(G(L),i_o); }
 
+#define setrvalue(L,obj,x) \
+  { TValue *i_o=(obj); \
+    i_o->value.gc=cast(GCObject *, (x)); i_o->tt=LUA_TROPE; \
+    checkliveness(G(L),i_o); }
+
 
 
 
@@ -224,6 +233,17 @@
 
 
 
+typedef union TRope {
+  L_Umaxalign dummy;  /* ensures maximum alignment for ropes */
+  struct {
+    CommonHeader;
+    GCObject *gclist;
+    union TRope * left;
+    union TRope * right;
+    size_t len;
+    TString *res;
+  } tsr;
+} TRope;
 
 /*
 ** Function Prototypes
diff -ruN lua-5.1.5-clean/src/lstate.c lua-5.1.5-ropes/src/lstate.c
--- lua-5.1.5-clean/src/lstate.c	2008-01-03 10:20:39.000000000 -0500
+++ lua-5.1.5-ropes/src/lstate.c	2021-06-19 07:59:07.000000000 -0400
@@ -77,6 +77,7 @@ static void f_luaopen (lua_State *L, void *ud) {
   luaT_init(L);
   luaX_init(L);
   luaS_fix(luaS_newliteral(L, MEMERRMSG));
+  g->ropestack = luaM_newvector(L, g->ropestacksize, TRope *);
   g->GCthreshold = 4*g->totalbytes;
 }
 
@@ -111,6 +112,7 @@ static void close_state (lua_State *L) {
   luaM_freearray(L, G(L)->strt.hash, G(L)->strt.size, TString *);
   luaZ_freebuffer(L, &g->buff);
   freestack(L, L);
+  luaM_freearray(L, g->ropestack, g->ropestacksize, TRope *);
   lua_assert(g->totalbytes == sizeof(LG));
   (*g->frealloc)(g->ud, fromstate(L), state_size(LG), 0);
 }
@@ -178,6 +180,7 @@ LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
   g->gcpause = LUAI_GCPAUSE;
   g->gcstepmul = LUAI_GCMUL;
   g->gcdept = 0;
+  g->ropestacksize = 8;
   for (i=0; i<NUM_TAGS; i++) g->mt[i] = NULL;
   if (luaD_rawrunprotected(L, f_luaopen, NULL) != 0) {
     /* memory allocation error: free partial state */
diff -ruN lua-5.1.5-clean/src/lstate.h lua-5.1.5-ropes/src/lstate.h
--- lua-5.1.5-clean/src/lstate.h	2008-01-03 10:20:39.000000000 -0500
+++ lua-5.1.5-ropes/src/lstate.h	2021-06-19 07:59:07.000000000 -0400
@@ -91,6 +91,8 @@ typedef struct global_State {
   UpVal uvhead;  /* head of double-linked list of all open upvalues */
   struct Table *mt[NUM_TAGS];  /* metatables for basic types */
   TString *tmname[TM_N];  /* array with tag-method names */
+  TRope **ropestack;  /* temporary stack used to store ropes when constructing strings */
+  int ropestacksize;  /* size of above stack */
 } global_State;
 
 
@@ -142,6 +142,7 @@
   struct Proto p;
   struct UpVal uv;
   struct lua_State th;  /* thread */
+  union TRope r;
 };
 
 
@@ -157,6 +158,8 @@
 #define ngcotouv(o) \
 	check_exp((o) == NULL || (o)->gch.tt == LUA_TUPVAL, &((o)->uv))
 #define gco2th(o)	check_exp((o)->gch.tt == LUA_TTHREAD, &((o)->th))
+#define rawgco2tr(o)	check_exp((o)->gch.tt == LUA_TROPE, &((o)->r))
+#define gco2tr(o)	(&rawgco2tr(o)->tsr)
 
 /* macro to convert any Lua object into a GCObject */
 #define obj2gco(v)	(cast(GCObject *, (v)))
diff -ruN lua-5.1.5-clean/src/lstring.c lua-5.1.5-ropes/src/lstring.c
--- lua-5.1.5-clean/src/lstring.c	2007-12-27 08:02:25.000000000 -0500
+++ lua-5.1.5-ropes/src/lstring.c	2021-06-19 18:47:38.000000000 -0400
@@ -18,6 +18,8 @@
 #include "lstring.h"
 
 
+#define ROPE_ALLOC_MIN_SIZE 32768
+
 
 void luaS_resize (lua_State *L, int newsize) {
   GCObject **newhash;
@@ -109,3 +109,72 @@
   return u;
 }
 
+TRope *luaS_concat (lua_State *L, TRope *l, TRope *r) {
+  TRope *rope;
+  rope = cast(TRope *, luaM_malloc(L, sizeof(TRope)));
+  luaC_link(L, obj2gco(rope), LUA_TROPE);
+  rope->tsr.left = l;
+  rope->tsr.right = r;
+  rope->tsr.len = (l->tsr.tt == LUA_TSTRING ? cast(TString *, l)->tsv.len : l->tsr.len) + (r->tsr.tt == LUA_TSTRING ? cast(TString *, r)->tsv.len : r->tsr.len);
+  rope->tsr.res = NULL;
+  return rope;
+}
+
+TString *luaS_build (lua_State *L, TRope *rope) {
+  char *buffer, *cur;
+  TString *s;
+  TRope **stack;
+  TRope *orig = rope;
+  if (rope->tsr.tt == LUA_TSTRING) return cast(TString *, rope);
+  if (rope->tsr.res || rope->tsr.left == NULL || rope->tsr.right == NULL) return rope->tsr.res;
+  if (rope->tsr.len >= ROPE_ALLOC_MIN_SIZE) buffer = cur = luaM_newvector(L, rope->tsr.len, char);
+  else buffer = cur = luaZ_openspace(L, &G(L)->buff, rope->tsr.len);
+  stack = G(L)->ropestack;
+  do {
+    int b = 0;
+    while (rope->tsr.left->tsr.tt == LUA_TROPE && rope->tsr.left->tsr.res == NULL) {
+      if (stack - G(L)->ropestack == G(L)->ropestacksize - 1) {
+        TRope **oldbase = G(L)->ropestack;
+        luaM_reallocvector(L, G(L)->ropestack, G(L)->ropestacksize, G(L)->ropestacksize + G(L)->ropestacksize, TRope *);
+        stack = G(L)->ropestack + (stack - oldbase);
+        G(L)->ropestacksize += G(L)->ropestacksize;
+      }
+      *stack++ = rope;
+      rope = rope->tsr.left;
+    }
+    if (rope->tsr.left->tsr.tt == LUA_TSTRING) {
+      memcpy(cur, getstr(cast(TString *, rope->tsr.left)), cast(TString *, rope->tsr.left)->tsv.len);
+      cur += cast(TString *, rope->tsr.left)->tsv.len;
+    } else {
+      memcpy(cur, getstr(rope->tsr.left->tsr.res), rope->tsr.left->tsr.res->tsv.len);
+      cur += rope->tsr.left->tsr.res->tsv.len;
+    }
+    while (rope->tsr.right->tsr.tt == LUA_TSTRING || rope->tsr.right->tsr.res) {
+      if (rope->tsr.right->tsr.tt == LUA_TSTRING) {
+        memcpy(cur, getstr(cast(TString *, rope->tsr.right)), cast(TString *, rope->tsr.right)->tsv.len);
+        cur += cast(TString *, rope->tsr.right)->tsv.len;
+      } else {
+        memcpy(cur, getstr(rope->tsr.right->tsr.res), rope->tsr.right->tsr.res->tsv.len);
+        cur += rope->tsr.right->tsr.res->tsv.len;
+      }
+      if (stack <= G(L)->ropestack) {b = 1; break;}
+      rope = *--stack;
+    }
+    if (b) break;
+    rope = rope->tsr.right;
+  } while (stack >= G(L)->ropestack);
+  s = luaS_newlstr(L, buffer, cur - buffer);
+  if (orig->tsr.len >= ROPE_ALLOC_MIN_SIZE) luaM_free(L, buffer);
+  orig->tsr.res = s;
+  orig->tsr.left = orig->tsr.right = NULL;  /* release left & right nodes (we don't need them anymore) */
+  /* mark the string as black so it doesn't accidentally get freed */
+  /* (apparently this is a problem?) */
+  resetbits(s->tsv.marked, WHITEBITS);
+  setbits(s->tsv.marked, bitmask(BLACKBIT));
+  return s;
+}
+
+void luaS_freerope (lua_State *L, TRope *rope) {
+  luaM_free(L, rope);
+}
+
diff -ruN lua-5.1.5-clean/src/lstring.h lua-5.1.5-ropes/src/lstring.h
--- lua-5.1.5-clean/src/lstring.h	2007-12-27 08:02:25.000000000 -0500
+++ lua-5.1.5-ropes/src/lstring.h	2021-06-19 07:59:07.000000000 -0400
@@ -26,6 +26,9 @@
 LUAI_FUNC void luaS_resize (lua_State *L, int newsize);
 LUAI_FUNC Udata *luaS_newudata (lua_State *L, size_t s, Table *e);
 LUAI_FUNC TString *luaS_newlstr (lua_State *L, const char *str, size_t l);
+LUAI_FUNC TRope *luaS_concat (lua_State *L, TRope *l, TRope *r);
+LUAI_FUNC TString *luaS_build (lua_State *L, TRope *rope);
+LUAI_FUNC void luaS_freerope (lua_State *L, TRope *rope);
 
 
 #endif
diff -ruN lua-5.1.5-clean/src/lstrlib.c lua-5.1.5-ropes/src/lstrlib.c
--- lua-5.1.5-clean/src/lstrlib.c	2007-12-27 08:02:25.000000000 -0500
+++ lua-5.1.5-ropes/src/lstrlib.c	2021-06-19 07:59:07.000000000 -0400
@@ -18,6 +18,8 @@
 
 #include "lauxlib.h"
 #include "lualib.h"
+
+#include "lstring.h"
 
 
 /* macro to `unsign' a character */
@@ -92,13 +94,17 @@ static int str_upper (lua_State *L) {
 
 static int str_rep (lua_State *L) {
   size_t l;
-  luaL_Buffer b;
+  char * str;
   const char *s = luaL_checklstring(L, 1, &l);
-  int n = luaL_checkint(L, 2);
-  luaL_buffinit(L, &b);
-  while (n-- > 0)
-    luaL_addlstring(&b, s, l);
-  luaL_pushresult(&b);
+  int n = luaL_checkint(L, 2), i;
+  if (n <= 0) lua_pushliteral(L, "");
+  else if (n == 1) lua_pushvalue(L, 1);
+  else {
+    str = luaM_newvector(L, l * n, char);
+    for (i = 0; i < l*n; i+=l) memcpy(str + i, s, l);
+    lua_pushlstring(L, str, l * n);
+    luaM_free(L, str);
+  }
   return 1;
 }
 
diff -ruN lua-5.1.5-clean/src/ltable.c lua-5.1.5-ropes/src/ltable.c
--- lua-5.1.5-clean/src/ltable.c	2007-12-28 10:32:23.000000000 -0500
+++ lua-5.1.5-ropes/src/ltable.c	2021-06-19 07:59:07.000000000 -0400
@@ -32,6 +32,7 @@
 #include "lmem.h"
 #include "lobject.h"
 #include "lstate.h"
+#include "lstring.h"
 #include "ltable.h"
 
 
@@ -466,10 +467,11 @@
 /*
 ** main search function
 */
-const TValue *luaH_get (Table *t, const TValue *key) {
+const TValue *luaH_get (lua_State *L, Table *t, const TValue *key) {
   switch (ttype(key)) {
     case LUA_TNIL: return luaO_nilobject;
     case LUA_TSTRING: return luaH_getstr(t, rawtsvalue(key));
+    case LUA_TROPE: return luaH_getstr(t, luaS_build(L, rawtrvalue(key)));
     case LUA_TNUMBER: {
       int k;
       lua_Number n = nvalue(key);
@@ -492,7 +494,7 @@
 
 
 TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
-  const TValue *p = luaH_get(t, key);
+  const TValue *p = luaH_get(L, t, key);
   t->flags = 0;
   if (p != luaO_nilobject)
     return cast(TValue *, p);
diff -ruN lua-5.1.5-clean/src/ltable.h lua-5.1.5-ropes/src/ltable.h
--- lua-5.1.5-clean/src/ltable.h	2007-12-27 08:02:25.000000000 -0500
+++ lua-5.1.5-ropes/src/ltable.h	2021-06-19 07:59:07.000000000 -0400
@@ -22,7 +22,7 @@
 LUAI_FUNC TValue *luaH_setnum (lua_State *L, Table *t, int key);
 LUAI_FUNC const TValue *luaH_getstr (Table *t, TString *key);
 LUAI_FUNC TValue *luaH_setstr (lua_State *L, Table *t, TString *key);
-LUAI_FUNC const TValue *luaH_get (Table *t, const TValue *key);
+LUAI_FUNC const TValue *luaH_get (lua_State *L, Table *t, const TValue *key);
 LUAI_FUNC TValue *luaH_set (lua_State *L, Table *t, const TValue *key);
 LUAI_FUNC Table *luaH_new (lua_State *L, int narray, int lnhash);
 LUAI_FUNC void luaH_resizearray (lua_State *L, Table *t, int nasize);
diff -ruN lua-5.1.5-clean/src/ltm.c lua-5.1.5-ropes/src/ltm.c
--- lua-5.1.5-clean/src/ltm.c	2007-12-27 08:02:25.000000000 -0500
+++ lua-5.1.5-ropes/src/ltm.c	2021-06-19 07:59:07.000000000 -0400
@@ -23,7 +23,7 @@
 const char *const luaT_typenames[] = {
   "nil", "boolean", "userdata", "number",
   "string", "table", "function", "userdata", "thread",
-  "proto", "upval"
+  "proto", "upval", "dead key", "rope", "substring"
 };
 
 
@@ -67,6 +67,9 @@
     case LUA_TUSERDATA:
       mt = uvalue(o)->metatable;
       break;
+    case LUA_TROPE:
+      mt = G(L)->mt[LUA_TSTRING];
+      break;
     default:
       mt = G(L)->mt[ttype(o)];
   }
diff -ruN lua-5.1.5-clean/src/lvm.c lua-5.1.5-ropes/src/lvm.c
--- lua-5.1.5-clean/src/lvm.c	2011-08-17 16:43:11.000000000 -0400
+++ lua-5.1.5-ropes/src/lvm.c	2021-06-19 10:52:48.000000000 -0400
@@ -32,9 +32,13 @@
 #define MAXTAGLOOP	100
 
 
-const TValue *luaV_tonumber (const TValue *obj, TValue *n) {
+#define resolverope(L, o) {if (ttisrope(o)) setsvalue(L, o, luaS_build(L, rawtrvalue(o)));}
+
+
+const TValue *luaV_tonumber (lua_State *L, const TValue *obj, TValue *n) {
   lua_Number num;
   if (ttisnumber(obj)) return obj;
+  resolverope(L, obj);
   if (ttisstring(obj) && luaO_str2d(svalue(obj), &num)) {
     setnvalue(n, num);
     return n;
@@ -45,7 +49,11 @@
 
 
 int luaV_tostring (lua_State *L, StkId obj) {
-  if (!ttisnumber(obj))
+  if (ttisrope(obj)) {
+    resolverope(L, obj);
+    return 1;
+  }
+  else if (!ttisnumber(obj))
     return 0;
   else {
     char s[LUAI_MAXNUMBER2STR];
@@ -107,11 +115,12 @@
 
 void luaV_gettable (lua_State *L, const TValue *t, TValue *key, StkId val) {
   int loop;
+  resolverope(L, key);
   for (loop = 0; loop < MAXTAGLOOP; loop++) {
     const TValue *tm;
     if (ttistable(t)) {  /* `t' is a table? */
       Table *h = hvalue(t);
-      const TValue *res = luaH_get(h, key); /* do a primitive get */
+      const TValue *res = luaH_get(L, h, key); /* do a primitive get */
       if (!ttisnil(res) ||  /* result is no nil? */
           (tm = fasttm(L, h->metatable, TM_INDEX)) == NULL) { /* or no TM? */
         setobj2s(L, val, res);
@@ -134,6 +143,7 @@
 void luaV_settable (lua_State *L, const TValue *t, TValue *key, StkId val) {
   int loop;
   TValue temp;
+  resolverope(L, key);
   for (loop = 0; loop < MAXTAGLOOP; loop++) {
     const TValue *tm;
     if (ttistable(t)) {  /* `t' is a table? */
@@ -224,6 +234,8 @@
 
 int luaV_lessthan (lua_State *L, const TValue *l, const TValue *r) {
   int res;
+  resolverope(L, l);
+  resolverope(L, r);
   if (ttype(l) != ttype(r))
     return luaG_ordererror(L, l, r);
   else if (ttisnumber(l))
@@ -238,6 +250,8 @@
 
 static int lessequal (lua_State *L, const TValue *l, const TValue *r) {
   int res;
+  resolverope(L, l);
+  resolverope(L, r);
   if (ttype(l) != ttype(r))
     return luaG_ordererror(L, l, r);
   else if (ttisnumber(l))
@@ -254,6 +268,8 @@
 
 int luaV_equalval (lua_State *L, const TValue *t1, const TValue *t2) {
   const TValue *tm;
+  resolverope(L, t1);
+  resolverope(L, t2);
   lua_assert(ttype(t1) == ttype(t2));
   switch (ttype(t1)) {
     case LUA_TNIL: return 1;
@@ -279,34 +295,35 @@
 }
 
 
+static TRope *makerope(lua_State *L, StkId start, int len) {
+  switch (len) {
+    case 1: return cast(TRope *, gcvalue(start)); /* this should never happen */
+    case 2: return luaS_concat(L, cast(TRope *, gcvalue(start)), cast(TRope *, gcvalue(start + 1)));
+    case 3: return luaS_concat(L, cast(TRope *, gcvalue(start)), luaS_concat(L, cast(TRope *, gcvalue(start + 1)), cast(TRope *, gcvalue(start + 2))));
+    default: return luaS_concat(L, makerope(L, start, len / 2), makerope(L, start + (len / 2), len - (len / 2)));
+  }
+}
+
+
 void luaV_concat (lua_State *L, int total, int last) {
   do {
     StkId top = L->base + last + 1;
     int n = 2;  /* number of elements handled in this pass (at least 2) */
-    if (!(ttisstring(top-2) || ttisnumber(top-2)) || !tostring(L, top-1)) {
+    if (!(ttisstring(top-2) || ttisnumber(top-2) || ttisrope(top-2)) || !tostring(L, top-1)) {
       if (!call_binTM(L, top-2, top-1, top-2, TM_CONCAT))
         luaG_concaterror(L, top-2, top-1);
     } else if (tsvalue(top-1)->len == 0)  /* second op is empty? */
       (void)tostring(L, top - 2);  /* result is first op (as string) */
     else {
-      /* at least two string values; get as many as possible */
+      /* concatenate by creating a rope */
       size_t tl = tsvalue(top-1)->len;
-      char *buffer;
-      int i;
       /* collect total length */
-      for (n = 1; n < total && tostring(L, top-n-1); n++) {
-        size_t l = tsvalue(top-n-1)->len;
+      for (n = 1; n < total && (ttisrope(top-n-1) || tostring(L, top-n-1)); n++) {
+        size_t l = ttisrope(top-n-1) ? trvalue(top-n-1)->len : tsvalue(top-n-1)->len;
         if (l >= MAX_SIZET - tl) luaG_runerror(L, "string length overflow");
         tl += l;
       }
-      buffer = luaZ_openspace(L, &G(L)->buff, tl);
-      tl = 0;
-      for (i=n; i>0; i--) {  /* concat all strings */
-        size_t l = tsvalue(top-i)->len;
-        memcpy(buffer+tl, svalue(top-i), l);
-        tl += l;
-      }
-      setsvalue2s(L, top-n, luaS_newlstr(L, buffer, tl));
+      setrvalue(L, top-n, makerope(L, top-n, n));
     }
     total -= n-1;  /* got `n' strings to create 1 new */
     last -= n-1;
@@ -318,8 +335,8 @@
                    const TValue *rc, TMS op) {
   TValue tempb, tempc;
   const TValue *b, *c;
-  if ((b = luaV_tonumber(rb, &tempb)) != NULL &&
-      (c = luaV_tonumber(rc, &tempc)) != NULL) {
+  if ((b = luaV_tonumber(L, rb, &tempb)) != NULL &&
+      (c = luaV_tonumber(L, rc, &tempc)) != NULL) {
     lua_Number nb = nvalue(b), nc = nvalue(c);
     switch (op) {
       case TM_ADD: setnvalue(ra, luai_numadd(nb, nc)); break;
@@ -522,6 +539,10 @@
             setnvalue(ra, cast_num(tsvalue(rb)->len));
             break;
           }
+          case LUA_TROPE: {
+            setnvalue(ra, cast_num(trvalue(rb)->len));
+            break;
+          }
           default: {  /* try metamethod */
             Protect(
               if (!call_binTM(L, rb, luaO_nilobject, ra, TM_LEN))
@@ -545,6 +566,8 @@
       case OP_EQ: {
         TValue *rb = RKB(i);
         TValue *rc = RKC(i);
+        resolverope(L, rb);
+        resolverope(L, rc);
         Protect(
           if (equalobj(L, rb, rc) == GETARG_A(i))
             dojump(L, pc, GETARG_sBx(*pc));
@@ -668,11 +691,11 @@
         const TValue *plimit = ra+1;
         const TValue *pstep = ra+2;
         L->savedpc = pc;  /* next steps may throw errors */
-        if (!tonumber(init, ra))
+        if (!tonumber(L, init, ra))
           luaG_runerror(L, LUA_QL("for") " initial value must be a number");
-        else if (!tonumber(plimit, ra+1))
+        else if (!tonumber(L, plimit, ra+1))
           luaG_runerror(L, LUA_QL("for") " limit must be a number");
-        else if (!tonumber(pstep, ra+2))
+        else if (!tonumber(L, pstep, ra+2))
           luaG_runerror(L, LUA_QL("for") " step must be a number");
         setnvalue(ra, luai_numsub(nvalue(ra), nvalue(pstep)));
         dojump(L, pc, GETARG_sBx(i));
diff -ruN lua-5.1.5-clean/src/lvm.h lua-5.1.5-ropes/src/lvm.h
--- lua-5.1.5-clean/src/lvm.h	2007-12-27 08:02:25.000000000 -0500
+++ lua-5.1.5-ropes/src/lvm.h	2021-06-19 07:59:07.000000000 -0400
@@ -15,8 +15,8 @@
 
 #define tostring(L,o) ((ttype(o) == LUA_TSTRING) || (luaV_tostring(L, o)))
 
-#define tonumber(o,n)	(ttype(o) == LUA_TNUMBER || \
-                         (((o) = luaV_tonumber(o,n)) != NULL))
+#define tonumber(L, o,n)	(ttype(o) == LUA_TNUMBER || \
+                         (((o) = luaV_tonumber(L,o,n)) != NULL))
 
 #define equalobj(L,o1,o2) \
 	(ttype(o1) == ttype(o2) && luaV_equalval(L, o1, o2))
@@ -24,7 +24,7 @@
 
 LUAI_FUNC int luaV_lessthan (lua_State *L, const TValue *l, const TValue *r);
 LUAI_FUNC int luaV_equalval (lua_State *L, const TValue *t1, const TValue *t2);
-LUAI_FUNC const TValue *luaV_tonumber (const TValue *obj, TValue *n);
+LUAI_FUNC const TValue *luaV_tonumber (lua_State *L, const TValue *obj, TValue *n);
 LUAI_FUNC int luaV_tostring (lua_State *L, StkId obj);
 LUAI_FUNC void luaV_gettable (lua_State *L, const TValue *t, TValue *key,
                                             StkId val);