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