src/bindings/lua/lua_state_cloner.c

   1 /* Copyright (c) 2010. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   4 /* This program is free software; you can redistribute it and/or modify it
   5  * under the terms of the license (GNU LGPL) which comes with this package. */
   6
   7 /* SimGrid Lua state management                                             */
   8
   9 #include "lua_state_cloner.h"
  10 #include "lua_utils.h"
  11 #include "xbt.h"
  12 #include "xbt/log.h"
  13 #include <lauxlib.h>
  14 #include <lualib.h>
  15
  16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(lua_state_cloner, lua, "Lua state management");
  17
  18 static lua_State* sglua_get_father(lua_State* L);
  19 static int l_get_from_father(lua_State* L);
  20
  21 static void sglua_move_value_impl(lua_State* src, lua_State* dst, const char* name);
  22 static void sglua_copy_nil(lua_State* src, lua_State* dst);
  23 static void sglua_copy_number(lua_State* src, lua_State* dst);
  24 static void sglua_copy_boolean(lua_State* src, lua_State* dst);
  25 static void sglua_copy_string(lua_State* src, lua_State* dst);
  26 static void sglua_copy_table(lua_State* src, lua_State* dst);
  27 static void sglua_copy_function(lua_State* src, lua_State* dst);
  28 static void sglua_copy_lightuserdata(lua_State* src, lua_State* dst);
  29 static void sglua_copy_userdata(lua_State* src, lua_State* dst);
  30 static void sglua_copy_thread(lua_State* src, lua_State* dst);
  31
  32 /**
  33  * @brief Returns the father of a state, i.e. the state that created it.
  34  * @param L a Lua state
  35  * @return its father, or NULL if the state was not created by sglua_clone_state()
  36  */
  37 static lua_State* sglua_get_father(lua_State* L) {
  38
  39                                   /* ... */
  40   lua_pushstring(L, "simgrid.father");
  41                                   /* ... "simgrid.father" */
  42   lua_rawget(L, LUA_REGISTRYINDEX);
  43                                   /* ... father */
  44   lua_State* father = lua_touserdata(L, -1);
  45   lua_pop(L, 1);
  46                                   /* ... */
  47   return father;
  48 }
  49
  50 /**
  51  * @brief Pops a value from a state and pushes it onto the stack of another
  52  * state.
  53  *
  54  * @param src the source state
  55  * @param dst the destination state
  56  */
  57 void sglua_move_value(lua_State* src, lua_State* dst) {
  58
  59   if (src != dst) {
  60
  61     /* get the list of visited tables from father at index 1 of dst */
  62                                   /* src: ... value
  63                                      dst: ... */
  64     lua_getfield(dst, LUA_REGISTRYINDEX, "simgrid.father_visited_tables");
  65                                   /* dst: ... visited */
  66     lua_insert(dst, 1);
  67                                   /* dst: visited ... */
  68
  69     sglua_move_value_impl(src, dst, sglua_tostring(src, -1));
  70                                   /* src: ...
  71                                      dst: visited ... value */
  72     lua_remove(dst, 1);
  73                                   /* dst: ... value */
  74     sglua_stack_dump("src after xmove: ", src);
  75     sglua_stack_dump("dst after xmove: ", dst);
  76   }
  77 }
  78
  79 /**
  80  * @brief Pops a value from the stack of a source state and pushes it on the
  81  * stack of another state.
  82  *
  83  * If the value is a table, its content is copied recursively. To avoid cycles,
  84  * a table of previously visited tables must be present at index 1 of dst.
  85  * Its keys are pointers to visited tables in src and its values are the tables
  86  * already built.
  87  *
  88  * TODO: add support of closures
  89  *
  90  * @param src the source state
  91  * @param dst the destination state, with a list of visited tables at index 1
  92  * @param name a name describing the value (for debugging purposes)
  93  */
  94 static void sglua_move_value_impl(lua_State* src, lua_State *dst, const char* name) {
  95
  96   luaL_checkany(src, -1);                  /* check the value to copy */
  97   luaL_checktype(dst, 1, LUA_TTABLE);      /* check the presence of a table of
  98                                               previously visited tables */
  99
 100   int indent = (lua_gettop(dst) - 1) * 6;
 101   XBT_DEBUG("%sCopying data %s", sglua_get_spaces(indent), name);
 102
 103   sglua_stack_dump("src before copying a value (should be ... value): ", src);
 104   sglua_stack_dump("dst before copying a value (should be visited ...): ", dst);
 105
 106   switch (lua_type(src, -1)) {
 107
 108     case LUA_TNIL:
 109       sglua_copy_nil(src, dst);
 110       break;
 111
 112     case LUA_TNUMBER:
 113       sglua_copy_number(src, dst);
 114       break;
 115
 116     case LUA_TBOOLEAN:
 117       sglua_copy_boolean(src, dst);
 118       break;
 119
 120     case LUA_TSTRING:
 121       sglua_copy_string(src, dst);
 122       break;
 123
 124     case LUA_TFUNCTION:
 125       sglua_copy_function(src, dst);
 126       break;
 127
 128     case LUA_TTABLE:
 129       sglua_copy_table(src, dst);
 130       break;
 131
 132     case LUA_TLIGHTUSERDATA:
 133       sglua_copy_lightuserdata(src, dst);
 134       break;
 135
 136     case LUA_TUSERDATA:
 137       sglua_copy_userdata(src, dst);
 138       break;
 139
 140     case LUA_TTHREAD:
 141       sglua_copy_thread(src, dst);
 142       break;
 143   }
 144
 145   /* the value has been copied to dst: remove it from src */
 146   lua_pop(src, 1);
 147
 148   indent -= 2;
 149   XBT_DEBUG("%sData copied", sglua_get_spaces(indent));
 150
 151   sglua_stack_dump("src after copying a value (should be ...): ", src);
 152   sglua_stack_dump("dst after copying a value (should be visited ... value): ", dst);
 153 }
 154
 155 /**
 156  * @brief Copies the nil value on the top of src to the top of dst.
 157  * @param src source state
 158  * @param dst destination state
 159  */
 160 static void sglua_copy_nil(lua_State* src, lua_State* dst) {
 161   lua_pushnil(dst);
 162 }
 163
 164 /**
 165  * @brief Copies the number value on the top of src to the top of dst.
 166  * @param src source state
 167  * @param dst destination state
 168  */
 169 static void sglua_copy_number(lua_State* src, lua_State* dst) {
 170   lua_pushnumber(dst, lua_tonumber(src, -1));
 171 }
 172
 173 /**
 174  * @brief Copies the boolean value on the top of src to the top of dst.
 175  * @param src source state
 176  * @param dst destination state
 177  */
 178 static void sglua_copy_boolean(lua_State* src, lua_State* dst) {
 179   lua_pushboolean(dst, lua_toboolean(src, -1));
 180 }
 181
 182 static void sglua_copy_string(lua_State* src, lua_State* dst) {
 183
 184   /* no worries about memory: lua_pushstring makes a copy */
 185   lua_pushstring(dst, lua_tostring(src, -1));
 186 }
 187
 188 /**
 189  * @brief Copies the table value on the top of src to the top of dst.
 190  *
 191  * A deep copy of the table is made. If the table has a metatable, the
 192  * metatable is also copied.
 193  * If the table is already known by the destination state, nothing is
 194  * done.
 195  *
 196  * @param src source state
 197  * @param dst destination state
 198  */
 199 static void sglua_copy_table(lua_State* src, lua_State* dst) {
 200
 201   int indent = (lua_gettop(dst) - 1) * 6  + 2;
 202
 203   /* first register the table in the source state itself */
 204   lua_getfield(src, LUA_REGISTRYINDEX, "simgrid.visited_tables");
 205                               /* src: ... table visited */
 206   lua_pushvalue(src, -2);
 207                               /* src: ... table visited table */
 208   lua_pushlightuserdata(src, (void*) lua_topointer(src, -1));
 209                               /* src: ... table visited table psrctable */
 210   lua_pushvalue(src, -1);
 211                               /* src: ... table visited table psrctable psrctable */
 212   lua_pushvalue(src, -3);
 213                               /* src: ... table visited table psrctable psrctable table */
 214   lua_settable(src, -5);
 215                               /* src: ... table visited table psrctable */
 216   lua_settable(src, -3);
 217                               /* src: ... table visited */
 218   lua_pop(src, 1);
 219                               /* src: ... table */
 220
 221   /* see if this table was already known by dst */
 222   lua_pushlightuserdata(dst, (void*) lua_topointer(src, -1));
 223                               /* dst: visited ... psrctable */
 224   lua_gettable(dst, 1);
 225                               /* dst: visited ... table/nil */
 226   if (lua_istable(dst, -1)) {
 227     XBT_DEBUG("%sNothing to do: table already visited (%p)",
 228         sglua_get_spaces(indent), lua_topointer(src, -1));
 229                               /* dst: visited ... table */
 230   }
 231   else {
 232     XBT_DEBUG("%sFirst visit of this table (%p)", sglua_get_spaces(indent),
 233         lua_topointer(src, -1));
 234                               /* dst: visited ... nil */
 235     lua_pop(dst, 1);
 236                               /* dst: visited ... */
 237
 238     /* first visit: create the new table in dst */
 239     lua_newtable(dst);
 240                               /* dst: visited ... table */
 241
 242     /* mark the table as visited right now to avoid infinite recursion */
 243     lua_pushlightuserdata(dst, (void*) lua_topointer(src, -1));
 244                               /* dst: visited ... table psrctable */
 245     lua_pushvalue(dst, -2);
 246                               /* dst: visited ... table psrctable table */
 247     lua_pushvalue(dst, -1);
 248                               /* dst: visited ... table psrctable table table */
 249     lua_pushvalue(dst, -3);
 250                               /* dst: visited ... table psrctable table table psrctable */
 251     lua_settable(dst, 1);
 252                               /* dst: visited ... table psrctable table */
 253     lua_settable(dst, 1);
 254                               /* dst: visited ... table */
 255     XBT_DEBUG("%sTable marked as visited", sglua_get_spaces(indent));
 256
 257     sglua_stack_dump("dst after marking the table as visited (should be visited ... table): ", dst);
 258
 259     /* copy the metatable if any */
 260     int has_meta_table = lua_getmetatable(src, -1);
 261                               /* src: ... table mt? */
 262     if (has_meta_table) {
 263       XBT_DEBUG("%sCopying metatable", sglua_get_spaces(indent));
 264                               /* src: ... table mt */
 265       sglua_copy_table(src, dst);
 266                               /* dst: visited ... table mt */
 267       lua_pop(src, 1);
 268                               /* src: ... table */
 269       lua_setmetatable(dst, -2);
 270                               /* dst: visited ... table */
 271     }
 272     else {
 273       XBT_DEBUG("%sNo metatable", sglua_get_spaces(indent));
 274     }
 275
 276     sglua_stack_dump("src before traversing the table (should be ... table): ", src);
 277     sglua_stack_dump("dst before traversing the table (should be visited ... table): ", dst);
 278
 279     /* traverse the table of src and copy each element */
 280     lua_pushnil(src);
 281                               /* src: ... table nil */
 282     while (lua_next(src, -2) != 0) {
 283                               /* src: ... table key value */
 284
 285       XBT_DEBUG("%sCopying table element %s", sglua_get_spaces(indent),
 286           sglua_keyvalue_tostring(src, -2, -1));
 287
 288       sglua_stack_dump("src before copying table element (should be ... table key value): ", src);
 289       sglua_stack_dump("dst before copying table element (should be visited ... table): ", dst);
 290
 291       /* copy the key */
 292       lua_pushvalue(src, -2);
 293                               /* src: ... table key value key */
 294       indent += 2;
 295       XBT_DEBUG("%sCopying the key part of the table element",
 296           sglua_get_spaces(indent));
 297       sglua_move_value_impl(src, dst, sglua_tostring(src, -1));
 298                               /* src: ... table key value
 299                                  dst: visited ... table key */
 300       XBT_DEBUG("%sCopied the key part of the table element",
 301           sglua_get_spaces(indent));
 302
 303       /* copy the value */
 304       XBT_DEBUG("%sCopying the value part of the table element",
 305           sglua_get_spaces(indent));
 306       sglua_move_value_impl(src, dst, sglua_tostring(src, -1));
 307                               /* src: ... table key
 308                                  dst: visited ... table key value */
 309       XBT_DEBUG("%sCopied the value part of the table element",
 310           sglua_get_spaces(indent));
 311       indent -= 2;
 312
 313       /* set the table element */
 314       lua_settable(dst, -3);
 315                               /* dst: visited ... table */
 316
 317       /* the key stays on top of src for next iteration */
 318       sglua_stack_dump("src before next iteration (should be ... table key): ", src);
 319       sglua_stack_dump("dst before next iteration (should be visited ... table): ", dst);
 320
 321       XBT_DEBUG("%sTable element copied", sglua_get_spaces(indent));
 322     }
 323     XBT_DEBUG("%sFinished traversing the table", sglua_get_spaces(indent));
 324   }
 325 }
 326
 327 /**
 328  * @brief Copies the function on the top of src to the top of dst.
 329  *
 330  * It can be a Lua function or a C function.
 331  * Copying upvalues is not implemented yet (TODO).
 332  *
 333  * @param src source state
 334  * @param dst destination state
 335  */
 336 static void sglua_copy_function(lua_State* src, lua_State* dst) {
 337
 338   if (lua_iscfunction(src, -1)) {
 339     /* it's a C function: just copy the pointer */
 340     lua_CFunction f = lua_tocfunction(src, -1);
 341     lua_pushcfunction(dst, f);
 342   }
 343   else {
 344     /* it's a Lua function: dump it from src */
 345
 346     s_sglua_buffer_t buffer;
 347     buffer.capacity = 64;
 348     buffer.size = 0;
 349     buffer.data = xbt_new(char, buffer.capacity);
 350
 351     /* copy the binary chunk from src into a buffer */
 352     int error = lua_dump(src, sglua_memory_writer, &buffer);
 353     xbt_assert(!error, "Failed to dump the function from the source state: error %d",
 354         error);
 355
 356     /* load the chunk into dst */
 357     error = luaL_loadbuffer(dst, buffer.data, buffer.size, "(dumped function)");
 358     xbt_assert(!error, "Failed to load the function into the destination state: %s",
 359         lua_tostring(dst, -1));
 360   }
 361 }
 362
 363 /**
 364  * @brief Copies the light userdata on the top of src to the top of dst.
 365  * @param src source state
 366  * @param dst destination state
 367  */
 368 static void sglua_copy_lightuserdata(lua_State* src, lua_State* dst) {
 369   lua_pushlightuserdata(dst, lua_touserdata(src, -1));
 370 }
 371
 372 /**
 373  * @brief Copies the full userdata on the top of src to the top of dst.
 374  *
 375  * If the userdata has a metatable, the metatable is also copied.
 376  *
 377  * @param src source state
 378  * @param dst destination state
 379  */
 380 static void sglua_copy_userdata(lua_State* src, lua_State* dst) {
 381
 382   int indent = (lua_gettop(dst) - 1) * 6  + 2;
 383
 384   /* copy the data */
 385                                   /* src: ... udata
 386                                      dst: visited ... */
 387   size_t size = lua_objlen(src, -1);
 388   void* src_block = lua_touserdata(src, -1);
 389   void* dst_block = lua_newuserdata(dst, size);
 390                                   /* dst: visited ... udata */
 391   memcpy(dst_block, src_block, size);
 392
 393   /* copy the metatable if any */
 394   int has_meta_table = lua_getmetatable(src, -1);
 395                                   /* src: ... udata mt? */
 396   if (has_meta_table) {
 397     XBT_DEBUG("%sCopying metatable of userdata (%p)",
 398         sglua_get_spaces(indent), lua_topointer(src, -1));
 399                                   /* src: ... udata mt */
 400     lua_State* father = sglua_get_father(dst);
 401
 402     if (father != NULL && src != father && sglua_get_father(src) == father) {
 403       XBT_DEBUG("%sGet the metatable from my father",
 404           sglua_get_spaces(indent));
 405       /* I don't want the metatable of src, I want the father's copy of the
 406          same metatable */
 407
 408       /* get from src the pointer to the father's copy of this metatable */
 409       lua_pushstring(src, "simgrid.father_visited_tables");
 410                                   /* src: ... udata mt "simgrid.visited_tables" */
 411       lua_rawget(src, LUA_REGISTRYINDEX);
 412                                   /* src: ... udata mt visited */
 413       lua_pushvalue(src, -2);
 414                                   /* src: ... udata mt visited mt */
 415       lua_gettable(src, -2);
 416                                   /* src: ... udata mt visited pfathermt */
 417
 418       /* copy the metatable from the father world into dst */
 419       lua_pushstring(father, "simgrid.visited_tables");
 420                                   /* father: ... "simgrid.visited_tables" */
 421       lua_rawget(father, LUA_REGISTRYINDEX);
 422                                   /* father: ... visited */
 423       lua_pushlightuserdata(father, (void*) lua_topointer(src, -1));
 424                                   /* father: ... visited pfathermt */
 425       lua_gettable(father, -2);
 426                                   /* father: ... visited mt */
 427       sglua_move_value_impl(father, dst, "(father metatable)");
 428                                   /* father: ... visited
 429                                      dst: visited ... udata mt */
 430       lua_pop(father, 1);
 431                                   /* father: ... */
 432       lua_pop(src, 3);
 433                                   /* src: ... udata */
 434
 435       /* TODO make helper functions for this kind of operations */
 436     }
 437     else {
 438       XBT_DEBUG("%sI have no father", sglua_get_spaces(indent));
 439       sglua_move_value_impl(src, dst, "metatable");
 440                                   /* src: ... udata
 441                                      dst: visited ... udata mt */
 442     }
 443     lua_setmetatable(dst, -2);
 444                                   /* dst: visited ... udata */
 445
 446     XBT_DEBUG("%sMetatable of userdata copied", sglua_get_spaces(indent));
 447   }
 448   else {
 449     XBT_DEBUG("%sNo metatable for this userdata",
 450         sglua_get_spaces(indent));
 451                                   /* src: ... udata */
 452   }
 453 }
 454
 455 /**
 456  * @brief This operation is not supported (yet?) so this function pushes nil.
 457  *
 458  * @param src source state
 459  * @param dst destination state
 460  */
 461 static void sglua_copy_thread(lua_State* src, lua_State* dst) {
 462
 463   XBT_WARN("Cannot copy a thread from the source state.");
 464   lua_pushnil(dst);
 465 }
 466
 467 /**
 468  * @brief Copies a global value or a registry value from the father state.
 469  *
 470  * The state L must have a father, i.e. it should have been created by
 471  * clone_lua_state().
 472  * This function is meant to be an __index metamethod.
 473  * Consequently, it assumes that the stack has two elements:
 474  * a table (either the environment or the registry of L) and the string key of
 475  * a value that does not exist yet in this table. It copies the corresponding
 476  * value from the father state and pushes it on the stack of L.
 477  * If the value does not exist in the father state either, nil is pushed.
 478  *
 479  * TODO: make this function thread safe. If the simulation runs in parallel,
 480  * several simulated processes may trigger this __index metamethod at the same
 481  * time and get globals from maestro.
 482  *
 483  * @param L the current state
 484  * @return number of return values pushed (always 1)
 485  */
 486 static int l_get_from_father(lua_State *L) {
 487
 488   /* check the arguments */
 489   luaL_checktype(L, 1, LUA_TTABLE);
 490   const char* key = luaL_checkstring(L, 2);
 491                                                /* L:      table key */
 492   XBT_DEBUG("__index of '%s' begins", key);
 493
 494   /* want a global or a registry value? */
 495   int pseudo_index;
 496   if (lua_equal(L, 1, LUA_REGISTRYINDEX)) {
 497     /* registry */
 498     pseudo_index = LUA_REGISTRYINDEX;
 499     XBT_DEBUG("Will get the value from the registry of the father");
 500   }
 501   else {
 502     /* global */
 503     pseudo_index = LUA_GLOBALSINDEX;
 504     XBT_DEBUG("Will get the value from the globals of the father");
 505   }
 506
 507   /* get the father */
 508   lua_State* father = sglua_get_father(L);
 509
 510   if (father == NULL) {
 511     XBT_WARN("This state has no father");
 512     lua_pop(L, 3);
 513     lua_pushnil(L);
 514     return 1;
 515   }
 516                                   /* L:      table key */
 517
 518   /* get the list of visited tables */
 519   lua_pushstring(L, "simgrid.father_visited_tables");
 520                                   /* L:      table key "simgrid.father_visited_tables" */
 521   lua_rawget(L, LUA_REGISTRYINDEX);
 522                                   /* L:      table key visited */
 523   lua_insert(L, 1);
 524                                   /* L:      visited table key */
 525
 526   /* get the value from the father */
 527   lua_getfield(father, pseudo_index, key);
 528                                   /* father: ... value */
 529
 530   /* push the value onto the stack of L */
 531   sglua_move_value_impl(father, L, key);
 532                                   /* father: ...
 533                                      L:      visited table key value */
 534   lua_remove(L, 1);
 535                                   /* L:      table key value */
 536
 537   /* prepare the return value of __index */
 538   lua_pushvalue(L, -1);
 539                                   /* L:      table key value value */
 540   lua_insert(L, 1);
 541                                   /* L:      value table key value */
 542
 543   /* save the copied value in the table for subsequent accesses */
 544   lua_settable(L, -3);
 545                                   /* L:      value table */
 546   lua_settop(L, 1);
 547                                   /* L:      value */
 548
 549   XBT_DEBUG("__index of '%s' returns %s", key, sglua_tostring(L, -1));
 550
 551   return 1;
 552 }
 553
 554 /**
 555  * @brief Creates a new Lua state and get its environment from an existing state.
 556  *
 557  * The state created is independent from the existing one and has its own
 558  * copies of global and registry values.
 559  * However, the global and registry values are not copied right now from
 560  * the original state; they are copied only the first time they are accessed.
 561  * This behavior saves time and memory, and is okay for Simgrid's needs.
 562  *
 563  * TODO: if the simulation runs in parallel, copy everything right now?
 564  *
 565  * @param father an existing state
 566  * @return the state created
 567  */
 568 lua_State* sglua_clone_state(lua_State *father) {
 569
 570   /* create the new state */
 571   lua_State *L = luaL_newstate();
 572
 573   /* set its environment and its registry:
 574    * - create a table newenv
 575    * - create a metatable mt
 576    * - set mt.__index = a function that copies the global from the father state
 577    * - set mt as the metatable of the registry
 578    * - set mt as the metatable of newenv
 579    * - set newenv as the environment of the new state
 580    */
 581   lua_pushthread(L);                        /* thread */
 582   lua_newtable(L);                          /* thread newenv */
 583   lua_newtable(L);                          /* thread newenv mt */
 584   lua_pushvalue(L, LUA_REGISTRYINDEX);      /* thread newenv mt reg */
 585   lua_pushcfunction(L, l_get_from_father);  /* thread newenv mt reg f */
 586   lua_setfield(L, -3, "__index");           /* thread newenv mt reg */
 587   lua_pushvalue(L, -2);                     /* thread newenv mt reg mt */
 588   lua_setmetatable(L, -2);                  /* thread newenv mt reg */
 589   lua_pop(L, 1);                            /* thread newenv mt */
 590   lua_setmetatable(L, -2);                  /* thread newenv */
 591   lua_setfenv(L, -2);                       /* thread */
 592   lua_pop(L, 1);                            /* -- */
 593
 594   /* set a pointer to the father */
 595   lua_pushstring(L, "simgrid.father");      /* "simgrid.father" */
 596   lua_pushlightuserdata(L, father);         /* "simgrid.father" father */
 597   lua_rawset(L, LUA_REGISTRYINDEX);
 598                                             /* -- */
 599
 600   /* create the table of visited tables from the father */
 601   lua_pushstring(L, "simgrid.father_visited_tables");
 602                                             /* "simgrid.father_visited_tables" */
 603   lua_newtable(L);                          /* "simgrid.father_visited_tables" visited */
 604   lua_rawset(L, LUA_REGISTRYINDEX);
 605                                             /* -- */
 606
 607   /* create the table of my own visited tables */
 608   lua_pushstring(L, "simgrid.visited_tables");
 609                                             /* "simgrid.visited_tables" */
 610   lua_newtable(L);                          /* "simgrid.visited_tables" visited */
 611   lua_rawset(L, LUA_REGISTRYINDEX);
 612                                             /* -- */
 613
 614   /* open the standard libs (theoretically, this is not necessary as they can
 615    * be inherited like any global values, but without a proper support of
 616    * closures, iterators like ipairs don't work). */
 617   XBT_DEBUG("Metatable of globals and registry set, opening standard libraries now");
 618   luaL_openlibs(L);
 619
 620   XBT_DEBUG("New state created");
 621
 622   return L;
 623 }