src/tracerestrict.cpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   6  */
   7
   8 /** @file tracerestrict.cpp Main file for Trace Restrict */
   9
  10 #include "stdafx.h"
  11 #include "tracerestrict.h"
  12 #include "train.h"
  13 #include "core/bitmath_func.hpp"
  14 #include "core/pool_func.hpp"
  15 #include "command_func.h"
  16 #include "company_func.h"
  17 #include "viewport_func.h"
  18 #include "window_func.h"
  19 #include "order_base.h"
  20 #include "cargotype.h"
  21 #include "group.h"
  22 #include "string_func.h"
  23 #include "pathfinder/yapf/yapf_cache.h"
  24
  25 #include "safeguards.h"
  26
  27 #include <vector>
  28 #include <algorithm>
  29
  30 /** @file
  31  *
  32  * Trace Restrict Data Storage Model Notes:
  33  *
  34  * Signals may have 0, 1 or 2 trace restrict programs attached to them,
  35  * up to one for each track. Two-way signals share the same program.
  36  *
  37  * The mapping between signals and programs is defined in terms of
  38  * TraceRestrictRefId to TraceRestrictProgramID,
  39  * where TraceRestrictRefId is formed of the tile index and track,
  40  * and TraceRestrictProgramID is an index into the program pool.
  41  *
  42  * If one or more mappings exist for a given signal tile, bit 12 of M3 will be set to 1.
  43  * This is updated whenever mappings are added/removed for that tile. This is to avoid
  44  * needing to do a mapping lookup for the common case where there is no trace restrict
  45  * program mapping for the given tile.
  46  *
  47  * Programs in the program pool are refcounted based on the number of mappings which exist.
  48  * When this falls to 0, the program is deleted from the pool.
  49  * If a program has a refcount greater than 1, it is a shared program.
  50  *
  51  * In all cases, an empty program is evaluated the same as the absence of a program.
  52  * Therefore it is not necessary to store mappings to empty unshared programs.
  53  * Any editing action which would otherwise result in a mapping to an empty program
  54  * which has no other references, instead removes the mapping.
  55  * This is not done for shared programs as this would delete the shared aspect whenever
  56  * the program became empty.
  57  *
  58  * Special case: In the case where an empty program with refcount 2 has one of its
  59  * mappings removed, the other mapping is left pointing to an empty unshared program.
  60  * This other mapping is then removed by performing a linear search of the mappings,
  61  * and removing the reference to that program ID.
  62  */
  63
  64 TraceRestrictProgramPool _tracerestrictprogram_pool("TraceRestrictProgram");
  65 INSTANTIATE_POOL_METHODS(TraceRestrictProgram)
  66
  67 TraceRestrictSlotPool _tracerestrictslot_pool("TraceRestrictSlot");
  68 INSTANTIATE_POOL_METHODS(TraceRestrictSlot)
  69
  70 /**
  71  * TraceRestrictRefId --> TraceRestrictProgramID (Pool ID) mapping
  72  * The indirection is mainly to enable shared programs
  73  * TODO: use a more efficient container/indirection mechanism
  74  */
  75 TraceRestrictMapping _tracerestrictprogram_mapping;
  76
  77 /**
  78  * List of pre-defined pathfinder penalty values
  79  * This is indexed by TraceRestrictPathfinderPenaltyPresetIndex
  80  */
  81 const uint16 _tracerestrict_pathfinder_penalty_preset_values[] = {
  82         500,
  83         2000,
  84         8000,
  85 };
  86
  87 assert_compile(lengthof(_tracerestrict_pathfinder_penalty_preset_values) == TRPPPI_END);
  88
  89 /**
  90  * This should be used when all pools have been or are immediately about to be also cleared
  91  * Calling this at other times will leave dangling refcounts
  92  */
  93 void ClearTraceRestrictMapping() {
  94         _tracerestrictprogram_mapping.clear();
  95 }
  96
  97 /**
  98  * Flags used for the program execution condition stack
  99  * Each 'if' pushes onto the stack
 100  * Each 'end if' pops from the stack
 101  * Elif/orif/else may modify the stack top
 102  */
 103 enum TraceRestrictCondStackFlags {
 104         TRCSF_DONE_IF         = 1<<0,       ///< The if/elif/else is "done", future elif/else branches will not be executed
 105         TRCSF_SEEN_ELSE       = 1<<1,       ///< An else branch has been seen already, error if another is seen afterwards
 106         TRCSF_ACTIVE          = 1<<2,       ///< The condition is currently active
 107         TRCSF_PARENT_INACTIVE = 1<<3,       ///< The parent condition is not active, thus this condition is also not active
 108 };
 109 DECLARE_ENUM_AS_BIT_SET(TraceRestrictCondStackFlags)
 110
 111 /**
 112  * Helper function to handle condition stack manipulatoin
 113  */
 114 static void HandleCondition(std::vector<TraceRestrictCondStackFlags> &condstack, TraceRestrictCondFlags condflags, bool value)
 115 {
 116         if (condflags & TRCF_OR) {
 117                 assert(!condstack.empty());
 118                 if (condstack.back() & TRCSF_ACTIVE) {
 119                         // leave TRCSF_ACTIVE set
 120                         return;
 121                 }
 122         }
 123
 124         if (condflags & (TRCF_OR | TRCF_ELSE)) {
 125                 assert(!condstack.empty());
 126                 if (condstack.back() & (TRCSF_DONE_IF | TRCSF_PARENT_INACTIVE)) {
 127                         condstack.back() &= ~TRCSF_ACTIVE;
 128                         return;
 129                 }
 130         } else {
 131                 if (!condstack.empty() && !(condstack.back() & TRCSF_ACTIVE)) {
 132                         //this is a 'nested if', the 'parent if' is not active
 133                         condstack.push_back(TRCSF_PARENT_INACTIVE);
 134                         return;
 135                 }
 136                 condstack.push_back(static_cast<TraceRestrictCondStackFlags>(0));
 137         }
 138
 139         if (value) {
 140                 condstack.back() |= TRCSF_DONE_IF | TRCSF_ACTIVE;
 141         } else {
 142                 condstack.back() &= ~TRCSF_ACTIVE;
 143         }
 144 }
 145
 146 /**
 147  * Integer condition testing
 148  * Test value op condvalue
 149  */
 150 static bool TestCondition(int value, TraceRestrictCondOp condop, int condvalue)
 151 {
 152         switch (condop) {
 153                 case TRCO_IS:
 154                         return value == condvalue;
 155                 case TRCO_ISNOT:
 156                         return value != condvalue;
 157                 case TRCO_LT:
 158                         return value < condvalue;
 159                 case TRCO_LTE:
 160                         return value <= condvalue;
 161                 case TRCO_GT:
 162                         return value > condvalue;
 163                 case TRCO_GTE:
 164                         return value >= condvalue;
 165                 default:
 166                         NOT_REACHED();
 167                         return false;
 168         }
 169 }
 170
 171 /**
 172  * Binary condition testing helper function
 173  */
 174 static bool TestBinaryConditionCommon(TraceRestrictItem item, bool input)
 175 {
 176         switch (GetTraceRestrictCondOp(item)) {
 177                 case TRCO_IS:
 178                         return input;
 179
 180                 case TRCO_ISNOT:
 181                         return !input;
 182
 183                 default:
 184                         NOT_REACHED();
 185                         return false;
 186         }
 187 }
 188
 189 /**
 190  * Test order condition
 191  * @p order may be NULL
 192  */
 193 static bool TestOrderCondition(const Order *order, TraceRestrictItem item)
 194 {
 195         bool result = false;
 196
 197         if (order) {
 198                 DestinationID condvalue = GetTraceRestrictValue(item);
 199                 switch (static_cast<TraceRestrictOrderCondAuxField>(GetTraceRestrictAuxField(item))) {
 200                         case TROCAF_STATION:
 201                                 result = order->IsType(OT_GOTO_STATION) && order->GetDestination() == condvalue;
 202                                 break;
 203
 204                         case TROCAF_WAYPOINT:
 205                                 result = order->IsType(OT_GOTO_WAYPOINT) && order->GetDestination() == condvalue;
 206                                 break;
 207
 208                         case OT_GOTO_DEPOT:
 209                                 result = order->IsType(OT_GOTO_DEPOT) && order->GetDestination() == condvalue;
 210                                 break;
 211
 212                         default:
 213                                 NOT_REACHED();
 214                 }
 215         }
 216         return TestBinaryConditionCommon(item, result);
 217 }
 218
 219 /**
 220  * Test station condition
 221  */
 222 static bool TestStationCondition(StationID station, TraceRestrictItem item)
 223 {
 224         bool result = (GetTraceRestrictAuxField(item) == TROCAF_STATION) && (station == GetTraceRestrictValue(item));
 225         return TestBinaryConditionCommon(item, result);
 226
 227 }
 228
 229 /**
 230  * Execute program on train and store results in out
 231  * @p v may not be NULL
 232  * @p out should be zero-initialised
 233  */
 234 void TraceRestrictProgram::Execute(const Train* v, const TraceRestrictProgramInput &input, TraceRestrictProgramResult& out) const
 235 {
 236         // static to avoid needing to re-alloc/resize on each execution
 237         static std::vector<TraceRestrictCondStackFlags> condstack;
 238         condstack.clear();
 239
 240         bool have_previous_signal = false;
 241         TileIndex previous_signal_tile = INVALID_TILE;
 242
 243         size_t size = this->items.size();
 244         for (size_t i = 0; i < size; i++) {
 245                 TraceRestrictItem item = this->items[i];
 246                 TraceRestrictItemType type = GetTraceRestrictType(item);
 247
 248                 if (IsTraceRestrictConditional(item)) {
 249                         TraceRestrictCondFlags condflags = GetTraceRestrictCondFlags(item);
 250                         TraceRestrictCondOp condop = GetTraceRestrictCondOp(item);
 251
 252                         if (type == TRIT_COND_ENDIF) {
 253                                 assert(!condstack.empty());
 254                                 if (condflags & TRCF_ELSE) {
 255                                         // else
 256                                         assert(!(condstack.back() & TRCSF_SEEN_ELSE));
 257                                         HandleCondition(condstack, condflags, true);
 258                                         condstack.back() |= TRCSF_SEEN_ELSE;
 259                                 } else {
 260                                         // end if
 261                                         condstack.pop_back();
 262                                 }
 263                         } else {
 264                                 uint16 condvalue = GetTraceRestrictValue(item);
 265                                 bool result = false;
 266                                 switch(type) {
 267                                         case TRIT_COND_UNDEFINED:
 268                                                 result = false;
 269                                                 break;
 270
 271                                         case TRIT_COND_TRAIN_LENGTH:
 272                                                 result = TestCondition(CeilDiv(v->gcache.cached_total_length, TILE_SIZE), condop, condvalue);
 273                                                 break;
 274
 275                                         case TRIT_COND_MAX_SPEED:
 276                                                 result = TestCondition(v->GetDisplayMaxSpeed(), condop, condvalue);
 277                                                 break;
 278
 279                                         case TRIT_COND_CURRENT_ORDER:
 280                                                 result = TestOrderCondition(&(v->current_order), item);
 281                                                 break;
 282
 283                                         case TRIT_COND_NEXT_ORDER: {
 284                                                 if (v->GetNumOrders() == 0) break;
 285
 286                                                 const Order *current_order = v->GetOrder(v->cur_real_order_index);
 287                                                 for (const Order *order = v->GetNextOrder(current_order); order != current_order; order = v->GetNextOrder(order)) {
 288                                                         if (order->IsGotoOrder()) {
 289                                                                 result = TestOrderCondition(order, item);
 290                                                                 break;
 291                                                         }
 292                                                 }
 293                                                 break;
 294                                         }
 295
 296                                         case TRIT_COND_LAST_STATION:
 297                                                 result = TestStationCondition(v->last_station_visited, item);
 298                                                 break;
 299
 300                                         case TRIT_COND_CARGO: {
 301                                                 bool have_cargo = false;
 302                                                 for (const Vehicle *v_iter = v; v_iter != NULL; v_iter = v_iter->Next()) {
 303                                                         if (v_iter->cargo_type == GetTraceRestrictValue(item) && v_iter->cargo_cap > 0) {
 304                                                                 have_cargo = true;
 305                                                                 break;
 306                                                         }
 307                                                 }
 308                                                 result = TestBinaryConditionCommon(item, have_cargo);
 309                                                 break;
 310                                         }
 311
 312                                         case TRIT_COND_ENTRY_DIRECTION: {
 313                                                 bool direction_match;
 314                                                 switch (GetTraceRestrictValue(item)) {
 315                                                         case TRNTSV_NE:
 316                                                         case TRNTSV_SE:
 317                                                         case TRNTSV_SW:
 318                                                         case TRNTSV_NW:
 319                                                                 direction_match = (static_cast<DiagDirection>(GetTraceRestrictValue(item)) == TrackdirToExitdir(ReverseTrackdir(input.trackdir)));
 320                                                                 break;
 321
 322                                                         case TRDTSV_FRONT:
 323                                                                 direction_match = IsTileType(input.tile, MP_RAILWAY) && HasSignalOnTrackdir(input.tile, input.trackdir);
 324                                                                 break;
 325
 326                                                         case TRDTSV_BACK:
 327                                                                 direction_match = IsTileType(input.tile, MP_RAILWAY) && !HasSignalOnTrackdir(input.tile, input.trackdir);
 328                                                                 break;
 329
 330                                                         default:
 331                                                                 NOT_REACHED();
 332                                                                 break;
 333                                                 }
 334                                                 result = TestBinaryConditionCommon(item, direction_match);
 335                                                 break;
 336                                         }
 337
 338                                         case TRIT_COND_PBS_ENTRY_SIGNAL: {
 339                                                 // TRVT_TILE_INDEX value type uses the next slot
 340                                                 i++;
 341                                                 uint32_t signal_tile = this->items[i];
 342                                                 if (!have_previous_signal) {
 343                                                         if (input.previous_signal_callback) {
 344                                                                 previous_signal_tile = input.previous_signal_callback(v, input.previous_signal_ptr);
 345                                                         }
 346                                                         have_previous_signal = true;
 347                                                 }
 348                                                 bool match = (signal_tile != INVALID_TILE)
 349                                                                 && (previous_signal_tile == signal_tile);
 350                                                 result = TestBinaryConditionCommon(item, match);
 351                                                 break;
 352                                         }
 353
 354                                         case TRIT_COND_TRAIN_GROUP: {
 355                                                 result = TestBinaryConditionCommon(item, GroupIsInGroup(v->group_id, GetTraceRestrictValue(item)));
 356                                                 break;
 357                                         }
 358
 359                                         case TRIT_COND_TRAIN_IN_SLOT: {
 360                                                 const TraceRestrictSlot *slot = TraceRestrictSlot::GetIfValid(GetTraceRestrictValue(item));
 361                                                 result = TestBinaryConditionCommon(item, slot != NULL && slot->IsOccupant(v->index));
 362                                                 break;
 363                                         }
 364
 365                                         case TRIT_COND_SLOT_OCCUPANCY: {
 366                                                 // TRIT_COND_SLOT_OCCUPANCY value type uses the next slot
 367                                                 i++;
 368                                                 uint32_t value = this->items[i];
 369                                                 const TraceRestrictSlot *slot = TraceRestrictSlot::GetIfValid(GetTraceRestrictValue(item));
 370                                                 switch (static_cast<TraceRestrictSlotOccupancyCondAuxField>(GetTraceRestrictAuxField(item))) {
 371                                                         case TRSOCAF_OCCUPANTS:
 372                                                                 result = TestCondition(slot != NULL ? slot->occupants.size() : 0, condop, value);
 373                                                                 break;
 374
 375                                                         case TRSOCAF_REMAINING:
 376                                                                 result = TestCondition(slot != NULL ? slot->max_occupancy - slot->occupants.size() : 0, condop, value);
 377                                                                 break;
 378
 379                                                         default:
 380                                                                 NOT_REACHED();
 381                                                                 break;
 382                                                 }
 383                                                 break;
 384                                         }
 385
 386                                         default:
 387                                                 NOT_REACHED();
 388                                 }
 389                                 HandleCondition(condstack, condflags, result);
 390                         }
 391                 } else {
 392                         if (condstack.empty() || condstack.back() & TRCSF_ACTIVE) {
 393                                 switch(type) {
 394                                         case TRIT_PF_DENY:
 395                                                 if (GetTraceRestrictValue(item)) {
 396                                                         out.flags &= ~TRPRF_DENY;
 397                                                 } else {
 398                                                         out.flags |= TRPRF_DENY;
 399                                                 }
 400                                                 break;
 401
 402                                         case TRIT_PF_PENALTY:
 403                                                 switch (static_cast<TraceRestrictPathfinderPenaltyAuxField>(GetTraceRestrictAuxField(item))) {
 404                                                         case TRPPAF_VALUE:
 405                                                                 out.penalty += GetTraceRestrictValue(item);
 406                                                                 break;
 407
 408                                                         case TRPPAF_PRESET: {
 409                                                                 uint16 index = GetTraceRestrictValue(item);
 410                                                                 assert(index < TRPPPI_END);
 411                                                                 out.penalty += _tracerestrict_pathfinder_penalty_preset_values[index];
 412                                                                 break;
 413                                                         }
 414
 415                                                         default:
 416                                                                 NOT_REACHED();
 417                                                 }
 418                                                 break;
 419
 420                                         case TRIT_RESERVE_THROUGH:
 421                                                 if (GetTraceRestrictValue(item)) {
 422                                                         out.flags &= ~TRPRF_RESERVE_THROUGH;
 423                                                 } else {
 424                                                         out.flags |= TRPRF_RESERVE_THROUGH;
 425                                                 }
 426                                                 break;
 427
 428                                         case TRIT_LONG_RESERVE:
 429                                                 if (GetTraceRestrictValue(item)) {
 430                                                         out.flags &= ~TRPRF_LONG_RESERVE;
 431                                                 } else {
 432                                                         out.flags |= TRPRF_LONG_RESERVE;
 433                                                 }
 434                                                 break;
 435
 436                                         case TRIT_WAIT_AT_PBS:
 437                                                 if (GetTraceRestrictValue(item)) {
 438                                                         out.flags &= ~TRPRF_WAIT_AT_PBS;
 439                                                 } else {
 440                                                         out.flags |= TRPRF_WAIT_AT_PBS;
 441                                                 }
 442                                                 break;
 443
 444                                         case TRIT_SLOT: {
 445                                                 if (!input.permitted_slot_operations) break;
 446                                                 TraceRestrictSlot *slot = TraceRestrictSlot::GetIfValid(GetTraceRestrictValue(item));
 447                                                 if (slot == NULL) break;
 448                                                 switch (static_cast<TraceRestrictSlotCondOpField>(GetTraceRestrictCondOp(item))) {
 449                                                         case TRSCOF_ACQUIRE_WAIT:
 450                                                                 if (input.permitted_slot_operations & TRPISP_ACQUIRE) {
 451                                                                         if (!slot->Occupy(v->index)) out.flags |= TRPRF_WAIT_AT_PBS;
 452                                                                 }
 453                                                                 break;
 454
 455                                                         case TRSCOF_ACQUIRE_TRY:
 456                                                                 if (input.permitted_slot_operations & TRPISP_ACQUIRE) slot->Occupy(v->index);
 457                                                                 break;
 458
 459                                                         case TRSCOF_RELEASE_BACK:
 460                                                                 if (input.permitted_slot_operations & TRPISP_RELEASE_BACK) slot->Vacate(v->index);
 461                                                                 break;
 462
 463                                                         case TRSCOF_RELEASE_FRONT:
 464                                                                 if (input.permitted_slot_operations & TRPISP_RELEASE_FRONT) slot->Vacate(v->index);
 465                                                                 break;
 466
 467                                                         default:
 468                                                                 NOT_REACHED();
 469                                                                 break;
 470                                                 }
 471                                                 break;
 472                                         }
 473
 474                                         default:
 475                                                 NOT_REACHED();
 476                                 }
 477                         }
 478                 }
 479         }
 480         assert(condstack.empty());
 481 }
 482
 483 /**
 484  * Decrement ref count, only use when removing a mapping
 485  */
 486 void TraceRestrictProgram::DecrementRefCount() {
 487         assert(this->refcount > 0);
 488         this->refcount--;
 489         if (this->refcount == 0) {
 490                 delete this;
 491         }
 492 }
 493
 494 /**
 495  * Validate a instruction list
 496  * Returns successful result if program seems OK
 497  * This only validates that conditional nesting is correct,
 498  * and that all instructions have a known type, at present
 499  */
 500 CommandCost TraceRestrictProgram::Validate(const std::vector<TraceRestrictItem> &items, TraceRestrictProgramActionsUsedFlags &actions_used_flags) {
 501         // static to avoid needing to re-alloc/resize on each execution
 502         static std::vector<TraceRestrictCondStackFlags> condstack;
 503         condstack.clear();
 504         actions_used_flags = static_cast<TraceRestrictProgramActionsUsedFlags>(0);
 505
 506         size_t size = items.size();
 507         for (size_t i = 0; i < size; i++) {
 508                 TraceRestrictItem item = items[i];
 509                 TraceRestrictItemType type = GetTraceRestrictType(item);
 510
 511                 // check multi-word instructions
 512                 if (IsTraceRestrictDoubleItem(item)) {
 513                         i++;
 514                         if (i >= size) {
 515                                 return_cmd_error(STR_TRACE_RESTRICT_ERROR_OFFSET_TOO_LARGE); // instruction ran off end
 516                         }
 517                 }
 518
 519                 if (IsTraceRestrictConditional(item)) {
 520                         TraceRestrictCondFlags condflags = GetTraceRestrictCondFlags(item);
 521
 522                         if (type == TRIT_COND_ENDIF) {
 523                                 if (condstack.empty()) {
 524                                         return_cmd_error(STR_TRACE_RESTRICT_ERROR_VALIDATE_NO_IF); // else/endif with no starting if
 525                                 }
 526                                 if (condflags & TRCF_ELSE) {
 527                                         // else
 528                                         if (condstack.back() & TRCSF_SEEN_ELSE) {
 529                                                 return_cmd_error(STR_TRACE_RESTRICT_ERROR_VALIDATE_DUP_ELSE); // Two else clauses
 530                                         }
 531                                         HandleCondition(condstack, condflags, true);
 532                                         condstack.back() |= TRCSF_SEEN_ELSE;
 533                                 } else {
 534                                         // end if
 535                                         condstack.pop_back();
 536                                 }
 537                         } else {
 538                                 if (condflags & (TRCF_OR | TRCF_ELSE)) { // elif/orif
 539                                         if (condstack.empty()) {
 540                                                 return_cmd_error(STR_TRACE_RESTRICT_ERROR_VALIDATE_ELIF_NO_IF); // Pre-empt assertions in HandleCondition
 541                                         }
 542                                         if (condstack.back() & TRCSF_SEEN_ELSE) {
 543                                                 return_cmd_error(STR_TRACE_RESTRICT_ERROR_VALIDATE_DUP_ELSE); // else clause followed by elif/orif
 544                                         }
 545                                 }
 546                                 HandleCondition(condstack, condflags, true);
 547                         }
 548
 549                         switch (GetTraceRestrictType(item)) {
 550                                 case TRIT_COND_ENDIF:
 551                                 case TRIT_COND_UNDEFINED:
 552                                 case TRIT_COND_TRAIN_LENGTH:
 553                                 case TRIT_COND_MAX_SPEED:
 554                                 case TRIT_COND_CURRENT_ORDER:
 555                                 case TRIT_COND_NEXT_ORDER:
 556                                 case TRIT_COND_LAST_STATION:
 557                                 case TRIT_COND_CARGO:
 558                                 case TRIT_COND_ENTRY_DIRECTION:
 559                                 case TRIT_COND_PBS_ENTRY_SIGNAL:
 560                                 case TRIT_COND_TRAIN_GROUP:
 561                                 case TRIT_COND_TRAIN_IN_SLOT:
 562                                 case TRIT_COND_SLOT_OCCUPANCY:
 563                                         break;
 564
 565                                 default:
 566                                         return_cmd_error(STR_TRACE_RESTRICT_ERROR_VALIDATE_UNKNOWN_INSTRUCTION);
 567                         }
 568                 } else {
 569                         switch (GetTraceRestrictType(item)) {
 570                                 case TRIT_PF_DENY:
 571                                 case TRIT_PF_PENALTY:
 572                                         actions_used_flags |= TRPAUF_PF;
 573                                         break;
 574
 575                                 case TRIT_RESERVE_THROUGH:
 576                                         actions_used_flags |= TRPAUF_RESERVE_THROUGH;
 577                                         break;
 578
 579                                 case TRIT_LONG_RESERVE:
 580                                         actions_used_flags |= TRPAUF_LONG_RESERVE;
 581                                         break;
 582
 583                                 case TRIT_WAIT_AT_PBS:
 584                                         actions_used_flags |= TRPAUF_WAIT_AT_PBS;
 585                                         break;
 586
 587                                 case TRIT_SLOT:
 588                                         switch (static_cast<TraceRestrictSlotCondOpField>(GetTraceRestrictCondOp(item))) {
 589                                                 case TRSCOF_ACQUIRE_WAIT:
 590                                                         actions_used_flags |= TRPAUF_SLOT_ACQUIRE | TRPAUF_WAIT_AT_PBS;
 591                                                         break;
 592
 593                                                 case TRSCOF_ACQUIRE_TRY:
 594                                                         actions_used_flags |= TRPAUF_SLOT_ACQUIRE;
 595                                                         break;
 596
 597                                                 case TRSCOF_RELEASE_BACK:
 598                                                         actions_used_flags |= TRPAUF_SLOT_RELEASE_BACK;
 599                                                         break;
 600
 601                                                 case TRSCOF_RELEASE_FRONT:
 602                                                         actions_used_flags |= TRPAUF_SLOT_RELEASE_FRONT;
 603                                                         break;
 604
 605                                                 default:
 606                                                         NOT_REACHED();
 607                                                         break;
 608                                         }
 609                                         break;
 610
 611                                 default:
 612                                         return_cmd_error(STR_TRACE_RESTRICT_ERROR_VALIDATE_UNKNOWN_INSTRUCTION);
 613                         }
 614                 }
 615         }
 616         if (!condstack.empty()) {
 617                 return_cmd_error(STR_TRACE_RESTRICT_ERROR_VALIDATE_END_CONDSTACK);
 618         }
 619         return CommandCost();
 620 }
 621
 622 /**
 623  * Convert an instruction index into an item array index
 624  */
 625 size_t TraceRestrictProgram::InstructionOffsetToArrayOffset(const std::vector<TraceRestrictItem> &items, size_t offset)
 626 {
 627         size_t output_offset = 0;
 628         size_t size = items.size();
 629         for (size_t i = 0; i < offset && output_offset < size; i++, output_offset++) {
 630                 if (IsTraceRestrictDoubleItem(items[output_offset])) {
 631                         output_offset++;
 632                 }
 633         }
 634         return output_offset;
 635 }
 636
 637 /**
 638  * Convert an item array index into an instruction index
 639  */
 640 size_t TraceRestrictProgram::ArrayOffsetToInstructionOffset(const std::vector<TraceRestrictItem> &items, size_t offset)
 641 {
 642         size_t output_offset = 0;
 643         for (size_t i = 0; i < offset; i++, output_offset++) {
 644                 if (IsTraceRestrictDoubleItem(items[i])) {
 645                         i++;
 646                 }
 647         }
 648         return output_offset;
 649 }
 650
 651 /**
 652  * Set the value and aux field of @p item, as per the value type in @p value_type
 653  */
 654 void SetTraceRestrictValueDefault(TraceRestrictItem &item, TraceRestrictValueType value_type)
 655 {
 656         switch (value_type) {
 657                 case TRVT_NONE:
 658                 case TRVT_INT:
 659                 case TRVT_DENY:
 660                 case TRVT_SPEED:
 661                 case TRVT_TILE_INDEX:
 662                 case TRVT_RESERVE_THROUGH:
 663                 case TRVT_LONG_RESERVE:
 664                 case TRVT_WAIT_AT_PBS:
 665                         SetTraceRestrictValue(item, 0);
 666                         if (!IsTraceRestrictTypeAuxSubtype(GetTraceRestrictType(item))) {
 667                                 SetTraceRestrictAuxField(item, 0);
 668                         }
 669                         break;
 670
 671                 case TRVT_ORDER:
 672                         SetTraceRestrictValue(item, INVALID_STATION);
 673                         SetTraceRestrictAuxField(item, TROCAF_STATION);
 674                         break;
 675
 676                 case TRVT_CARGO_ID:
 677                         assert(_sorted_standard_cargo_specs_size > 0);
 678                         SetTraceRestrictValue(item, _sorted_cargo_specs[0]->Index());
 679                         SetTraceRestrictAuxField(item, 0);
 680                         break;
 681
 682                 case TRVT_DIRECTION:
 683                         SetTraceRestrictValue(item, TRDTSV_FRONT);
 684                         SetTraceRestrictAuxField(item, 0);
 685                         break;
 686
 687                 case TRVT_PF_PENALTY:
 688                         SetTraceRestrictValue(item, TRPPPI_SMALL);
 689                         SetTraceRestrictAuxField(item, TRPPAF_PRESET);
 690                         break;
 691
 692                 case TRVT_GROUP_INDEX:
 693                         SetTraceRestrictValue(item, INVALID_GROUP);
 694                         SetTraceRestrictAuxField(item, 0);
 695                         break;
 696
 697                 case TRVT_SLOT_INDEX:
 698                         SetTraceRestrictValue(item, INVALID_TRACE_RESTRICT_SLOT_ID);
 699                         SetTraceRestrictAuxField(item, 0);
 700                         break;
 701
 702                 case TRVT_SLOT_INDEX_INT:
 703                         SetTraceRestrictValue(item, INVALID_TRACE_RESTRICT_SLOT_ID);
 704                         break;
 705
 706                 default:
 707                         NOT_REACHED();
 708                         break;
 709         }
 710 }
 711
 712 /**
 713 * Set the type field of a TraceRestrictItem, and resets any other fields which are no longer valid/meaningful to sensible defaults
 714 */
 715 void SetTraceRestrictTypeAndNormalise(TraceRestrictItem &item, TraceRestrictItemType type, uint8 aux_data)
 716 {
 717         if (item != 0) {
 718                 assert(GetTraceRestrictType(item) != TRIT_NULL);
 719                 assert(IsTraceRestrictConditional(item) == IsTraceRestrictTypeConditional(type));
 720         }
 721         assert(type != TRIT_NULL);
 722
 723         TraceRestrictTypePropertySet old_properties = GetTraceRestrictTypeProperties(item);
 724         SetTraceRestrictType(item, type);
 725         bool set_aux_field = false;
 726         if (IsTraceRestrictTypeAuxSubtype(type)) {
 727                 SetTraceRestrictAuxField(item, aux_data);
 728                 set_aux_field = true;
 729         }
 730         else {
 731                 assert(aux_data == 0);
 732         }
 733         TraceRestrictTypePropertySet new_properties = GetTraceRestrictTypeProperties(item);
 734
 735         if (old_properties.cond_type != new_properties.cond_type ||
 736                 old_properties.value_type != new_properties.value_type) {
 737                 SetTraceRestrictCondOp(item, TRCO_IS);
 738                 SetTraceRestrictValueDefault(item, new_properties.value_type);
 739                 if (set_aux_field) {
 740                         SetTraceRestrictAuxField(item, aux_data);
 741                 }
 742         }
 743         if (GetTraceRestrictType(item) == TRIT_COND_LAST_STATION && GetTraceRestrictAuxField(item) != TROCAF_STATION) {
 744                 // if changing type from another order type to last visited station, reset value if not currently a station
 745                 SetTraceRestrictValueDefault(item, TRVT_ORDER);
 746         }
 747 }
 748
 749 /**
 750  * Sets the "signal has a trace restrict mapping" bit
 751  * This looks for mappings with that tile index
 752  */
 753 void SetIsSignalRestrictedBit(TileIndex t)
 754 {
 755         // First mapping for this tile, or later
 756         TraceRestrictMapping::iterator lower_bound = _tracerestrictprogram_mapping.lower_bound(MakeTraceRestrictRefId(t, static_cast<Track>(0)));
 757
 758         // First mapping for next tile, or later
 759         TraceRestrictMapping::iterator upper_bound = _tracerestrictprogram_mapping.lower_bound(MakeTraceRestrictRefId(t + 1, static_cast<Track>(0)));
 760
 761         // If iterators are the same, there are no mappings for this tile
 762         SetRestrictedSignal(t, lower_bound != upper_bound);
 763 }
 764
 765 /**
 766  * Create a new program mapping to an existing program
 767  * If a mapping already exists, it is removed
 768  */
 769 void TraceRestrictCreateProgramMapping(TraceRestrictRefId ref, TraceRestrictProgram *prog)
 770 {
 771         std::pair<TraceRestrictMapping::iterator, bool> insert_result =
 772                         _tracerestrictprogram_mapping.insert(std::make_pair(ref, TraceRestrictMappingItem(prog->index)));
 773
 774         if (!insert_result.second) {
 775                 // value was not inserted, there is an existing mapping
 776                 // unref the existing mapping before updating it
 777                 _tracerestrictprogram_pool.Get(insert_result.first->second.program_id)->DecrementRefCount();
 778                 insert_result.first->second = prog->index;
 779         }
 780         prog->IncrementRefCount();
 781
 782         TileIndex tile = GetTraceRestrictRefIdTileIndex(ref);
 783         Track track = GetTraceRestrictRefIdTrack(ref);
 784         SetIsSignalRestrictedBit(tile);
 785         MarkTileDirtyByTile(tile);
 786         YapfNotifyTrackLayoutChange(tile, track);
 787 }
 788
 789 /**
 790  * Remove a program mapping
 791  * @return true if a mapping was actually removed
 792  */
 793 bool TraceRestrictRemoveProgramMapping(TraceRestrictRefId ref)
 794 {
 795         TraceRestrictMapping::iterator iter = _tracerestrictprogram_mapping.find(ref);
 796         if (iter != _tracerestrictprogram_mapping.end()) {
 797                 // Found
 798                 TraceRestrictProgram *prog = _tracerestrictprogram_pool.Get(iter->second.program_id);
 799
 800                 // check to see if another mapping needs to be removed as well
 801                 // do this before decrementing the refcount
 802                 bool remove_other_mapping = prog->refcount == 2 && prog->items.empty();
 803
 804                 prog->DecrementRefCount();
 805                 _tracerestrictprogram_mapping.erase(iter);
 806
 807                 TileIndex tile = GetTraceRestrictRefIdTileIndex(ref);
 808                 Track track = GetTraceRestrictRefIdTrack(ref);
 809                 SetIsSignalRestrictedBit(tile);
 810                 MarkTileDirtyByTile(tile);
 811                 YapfNotifyTrackLayoutChange(tile, track);
 812
 813                 if (remove_other_mapping) {
 814                         TraceRestrictProgramID id = prog->index;
 815                         for (TraceRestrictMapping::iterator rm_iter = _tracerestrictprogram_mapping.begin();
 816                                         rm_iter != _tracerestrictprogram_mapping.end(); ++rm_iter) {
 817                                 if (rm_iter->second.program_id == id) {
 818                                         TraceRestrictRemoveProgramMapping(rm_iter->first);
 819                                         break;
 820                                 }
 821                         }
 822                 }
 823                 return true;
 824         }
 825         else {
 826                 return false;
 827         }
 828 }
 829
 830 /**
 831  * Gets the signal program for the tile ref @p ref
 832  * An empty program will be constructed if none exists, and @p create_new is true, unless the pool is full
 833  */
 834 TraceRestrictProgram *GetTraceRestrictProgram(TraceRestrictRefId ref, bool create_new)
 835 {
 836         // Optimise for lookup, creating doesn't have to be that fast
 837
 838         TraceRestrictMapping::iterator iter = _tracerestrictprogram_mapping.find(ref);
 839         if (iter != _tracerestrictprogram_mapping.end()) {
 840                 // Found
 841                 return _tracerestrictprogram_pool.Get(iter->second.program_id);
 842         } else if (create_new) {
 843                 // Not found
 844
 845                 // Create new pool item
 846                 if (!TraceRestrictProgram::CanAllocateItem()) {
 847                         return NULL;
 848                 }
 849                 TraceRestrictProgram *prog = new TraceRestrictProgram();
 850
 851                 // Create new mapping to pool item
 852                 TraceRestrictCreateProgramMapping(ref, prog);
 853                 return prog;
 854         } else {
 855                 return NULL;
 856         }
 857 }
 858
 859 /**
 860  * Notify that a signal is being removed
 861  * Remove any trace restrict mappings associated with it
 862  */
 863 void TraceRestrictNotifySignalRemoval(TileIndex tile, Track track)
 864 {
 865         TraceRestrictRefId ref = MakeTraceRestrictRefId(tile, track);
 866         bool removed = TraceRestrictRemoveProgramMapping(ref);
 867         DeleteWindowById(WC_TRACE_RESTRICT, ref);
 868         if (removed) InvalidateWindowClassesData(WC_TRACE_RESTRICT);
 869 }
 870
 871 /**
 872  * Helper function to perform parameter bit-packing and call DoCommandP, for instruction modification actions
 873  */
 874 void TraceRestrictDoCommandP(TileIndex tile, Track track, TraceRestrictDoCommandType type, uint32 offset, uint32 value, StringID error_msg)
 875 {
 876         uint32 p1 = 0;
 877         SB(p1, 0, 3, track);
 878         SB(p1, 3, 5, type);
 879         assert(offset < (1 << 16));
 880         SB(p1, 8, 16, offset);
 881         DoCommandP(tile, p1, value, CMD_PROGRAM_TRACERESTRICT_SIGNAL | CMD_MSG(error_msg));
 882 }
 883
 884 /**
 885  * Check whether a tile/tracl pair contains a usable signal
 886  */
 887 static CommandCost TraceRestrictCheckTileIsUsable(TileIndex tile, Track track)
 888 {
 889         // Check that there actually is a signal here
 890         if (!IsPlainRailTile(tile) || !HasTrack(tile, track)) {
 891                 return_cmd_error(STR_ERROR_THERE_IS_NO_RAILROAD_TRACK);
 892         }
 893         if (!HasSignalOnTrack(tile, track)) {
 894                 return_cmd_error(STR_ERROR_THERE_ARE_NO_SIGNALS);
 895         }
 896
 897         // Check tile ownership, do this afterwards to avoid tripping up on house/industry tiles
 898         CommandCost ret = CheckTileOwnership(tile);
 899         if (ret.Failed()) {
 900                 return ret;
 901         }
 902
 903         return CommandCost();
 904 }
 905
 906 /**
 907  * Returns an appropriate default value for the second item of a dual-item instruction
 908  * @p item is the first item of the instruction
 909  */
 910 static uint32 GetDualInstructionInitialValue(TraceRestrictItem item)
 911 {
 912         switch (GetTraceRestrictType(item)) {
 913                 case TRIT_COND_PBS_ENTRY_SIGNAL:
 914                         return INVALID_TILE;
 915
 916                 case TRIT_COND_SLOT_OCCUPANCY:
 917                         return 0;
 918
 919                 default:
 920                         NOT_REACHED();
 921         }
 922 }
 923
 924 template <typename T> T InstructionIteratorNext(T iter)
 925 {
 926         return IsTraceRestrictDoubleItem(*iter) ? iter + 2 : iter + 1;
 927 }
 928
 929 template <typename T> void InstructionIteratorAdvance(T &iter)
 930 {
 931         iter = InstructionIteratorNext(iter);
 932 }
 933
 934 CommandCost TraceRestrictProgramRemoveItemAt(std::vector<TraceRestrictItem> &items, uint32 offset, bool shallow_mode)
 935 {
 936         TraceRestrictItem old_item = *TraceRestrictProgram::InstructionAt(items, offset);
 937         if (IsTraceRestrictConditional(old_item) && GetTraceRestrictCondFlags(old_item) != TRCF_OR) {
 938                 bool remove_whole_block = false;
 939                 if (GetTraceRestrictCondFlags(old_item) == 0) {
 940                         if (GetTraceRestrictType(old_item) == TRIT_COND_ENDIF) {
 941                                 // this is an end if, can't remove these
 942                                 return_cmd_error(STR_TRACE_RESTRICT_ERROR_CAN_T_REMOVE_ENDIF);
 943                         } else {
 944                                 // this is an opening if
 945                                 remove_whole_block = true;
 946                         }
 947                 }
 948
 949                 uint32 recursion_depth = 1;
 950                 std::vector<TraceRestrictItem>::iterator remove_start = TraceRestrictProgram::InstructionAt(items, offset);
 951                 std::vector<TraceRestrictItem>::iterator remove_end = InstructionIteratorNext(remove_start);
 952
 953                 // iterate until matching end block found
 954                 for (; remove_end != items.end(); InstructionIteratorAdvance(remove_end)) {
 955                         TraceRestrictItem current_item = *remove_end;
 956                         if (IsTraceRestrictConditional(current_item)) {
 957                                 if (GetTraceRestrictCondFlags(current_item) == 0) {
 958                                         if (GetTraceRestrictType(current_item) == TRIT_COND_ENDIF) {
 959                                                 // this is an end if
 960                                                 recursion_depth--;
 961                                                 if (recursion_depth == 0) {
 962                                                         if (remove_whole_block) {
 963                                                                 if (shallow_mode) {
 964                                                                         // must erase endif first, as it is later in the vector
 965                                                                         items.erase(remove_end, InstructionIteratorNext(remove_end));
 966                                                                 } else {
 967                                                                         // inclusively remove up to here
 968                                                                         InstructionIteratorAdvance(remove_end);
 969                                                                 }
 970                                                                 break;
 971                                                         } else {
 972                                                                 // exclusively remove up to here
 973                                                                 break;
 974                                                         }
 975                                                 }
 976                                         } else {
 977                                                 // this is an opening if
 978                                                 recursion_depth++;
 979                                         }
 980                                 } else {
 981                                         // this is an else/or type block
 982                                         if (recursion_depth == 1 && !remove_whole_block) {
 983                                                 // exclusively remove up to here
 984                                                 recursion_depth = 0;
 985                                                 break;
 986                                         }
 987                                         if (recursion_depth == 1 && remove_whole_block && shallow_mode) {
 988                                                 // shallow-removing whole if block, and it contains an else/or if, bail out
 989                                                 return_cmd_error(STR_TRACE_RESTRICT_ERROR_CAN_T_SHALLOW_REMOVE_IF_ELIF);
 990                                         }
 991                                 }
 992                         }
 993                 }
 994                 if (recursion_depth != 0) return CMD_ERROR; // ran off the end
 995                 if (shallow_mode) {
 996                         items.erase(remove_start, InstructionIteratorNext(remove_start));
 997                 } else {
 998                         items.erase(remove_start, remove_end);
 999                 }
1000         } else {
1001                 std::vector<TraceRestrictItem>::iterator remove_start = TraceRestrictProgram::InstructionAt(items, offset);
1002                 std::vector<TraceRestrictItem>::iterator remove_end = InstructionIteratorNext(remove_start);
1003
1004                 items.erase(remove_start, remove_end);
1005         }
1006         return CommandCost();
1007 }
1008
1009 CommandCost TraceRestrictProgramMoveItemAt(std::vector<TraceRestrictItem> &items, uint32 &offset, bool up, bool shallow_mode)
1010 {
1011         std::vector<TraceRestrictItem>::iterator move_start = TraceRestrictProgram::InstructionAt(items, offset);
1012         std::vector<TraceRestrictItem>::iterator move_end = InstructionIteratorNext(move_start);
1013
1014         TraceRestrictItem old_item = *move_start;
1015         if (!shallow_mode) {
1016                 if (IsTraceRestrictConditional(old_item)) {
1017                         if (GetTraceRestrictCondFlags(old_item) != 0) {
1018                                 // can't move or/else blocks
1019                                 return_cmd_error(STR_TRACE_RESTRICT_ERROR_CAN_T_MOVE_ITEM);
1020                         }
1021                         if (GetTraceRestrictType(old_item) == TRIT_COND_ENDIF) {
1022                                 // this is an end if, can't move these
1023                                 return_cmd_error(STR_TRACE_RESTRICT_ERROR_CAN_T_MOVE_ITEM);
1024                         }
1025
1026                         uint32 recursion_depth = 1;
1027                         // iterate until matching end block found
1028                         for (; move_end != items.end(); InstructionIteratorAdvance(move_end)) {
1029                                 TraceRestrictItem current_item = *move_end;
1030                                 if (IsTraceRestrictConditional(current_item)) {
1031                                         if (GetTraceRestrictCondFlags(current_item) == 0) {
1032                                                 if (GetTraceRestrictType(current_item) == TRIT_COND_ENDIF) {
1033                                                         // this is an end if
1034                                                         recursion_depth--;
1035                                                         if (recursion_depth == 0) {
1036                                                                 // inclusively remove up to here
1037                                                                 InstructionIteratorAdvance(move_end);
1038                                                                 break;
1039                                                         }
1040                                                 } else {
1041                                                         // this is an opening if
1042                                                         recursion_depth++;
1043                                                 }
1044                                         }
1045                                 }
1046                         }
1047                         if (recursion_depth != 0) return CMD_ERROR; // ran off the end
1048                 }
1049         }
1050
1051         if (up) {
1052                 if (move_start == items.begin()) return_cmd_error(STR_TRACE_RESTRICT_ERROR_CAN_T_MOVE_ITEM);
1053                 std::rotate(TraceRestrictProgram::InstructionAt(items, offset - 1), move_start, move_end);
1054                 offset--;
1055         } else {
1056                 if (move_end == items.end()) return_cmd_error(STR_TRACE_RESTRICT_ERROR_CAN_T_MOVE_ITEM);
1057                 std::rotate(move_start, move_end, InstructionIteratorNext(move_end));
1058                 offset++;
1059         }
1060         return CommandCost();
1061 }
1062
1063 /**
1064  * The main command for editing a signal tracerestrict program.
1065  * @param tile The tile which contains the signal.
1066  * @param flags Internal command handler stuff.
1067  * Below apply for instruction modification actions only
1068  * @param p1 Bitstuffed items
1069  * @param p2 Item, for insert and modify operations. Flags for instruction move operations
1070  * @return the cost of this operation (which is free), or an error
1071  */
1072 CommandCost CmdProgramSignalTraceRestrict(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text)
1073 {
1074         TraceRestrictDoCommandType type = static_cast<TraceRestrictDoCommandType>(GB(p1, 3, 5));
1075
1076         if (type >= TRDCT_PROG_COPY) {
1077                 return CmdProgramSignalTraceRestrictProgMgmt(tile, flags, p1, p2, text);
1078         }
1079
1080         Track track = static_cast<Track>(GB(p1, 0, 3));
1081         uint32 offset = GB(p1, 8, 16);
1082         TraceRestrictItem item = static_cast<TraceRestrictItem>(p2);
1083
1084         CommandCost ret = TraceRestrictCheckTileIsUsable(tile, track);
1085         if (ret.Failed()) {
1086                 return ret;
1087         }
1088
1089         bool can_make_new = (type == TRDCT_INSERT_ITEM) && (flags & DC_EXEC);
1090         bool need_existing = (type != TRDCT_INSERT_ITEM);
1091         TraceRestrictProgram *prog = GetTraceRestrictProgram(MakeTraceRestrictRefId(tile, track), can_make_new);
1092         if (need_existing && !prog) {
1093                 return_cmd_error(STR_TRACE_RESTRICT_ERROR_NO_PROGRAM);
1094         }
1095
1096         uint32 offset_limit_exclusive = ((type == TRDCT_INSERT_ITEM) ? 1 : 0);
1097         if (prog) offset_limit_exclusive += (uint32)prog->items.size();
1098
1099         if (offset >= offset_limit_exclusive) {
1100                 return_cmd_error(STR_TRACE_RESTRICT_ERROR_OFFSET_TOO_LARGE);
1101         }
1102
1103         // copy program
1104         std::vector<TraceRestrictItem> items;
1105         if (prog) items = prog->items;
1106
1107         switch (type) {
1108                 case TRDCT_INSERT_ITEM:
1109                         items.insert(TraceRestrictProgram::InstructionAt(items, offset), item);
1110                         if (IsTraceRestrictConditional(item) &&
1111                                         GetTraceRestrictCondFlags(item) == 0 &&
1112                                         GetTraceRestrictType(item) != TRIT_COND_ENDIF) {
1113                                 // this is an opening if block, insert a corresponding end if
1114                                 TraceRestrictItem endif_item = 0;
1115                                 SetTraceRestrictType(endif_item, TRIT_COND_ENDIF);
1116                                 items.insert(TraceRestrictProgram::InstructionAt(items, offset) + 1, endif_item);
1117                         } else if (IsTraceRestrictDoubleItem(item)) {
1118                                 items.insert(TraceRestrictProgram::InstructionAt(items, offset) + 1, GetDualInstructionInitialValue(item));
1119                         }
1120                         break;
1121
1122                 case TRDCT_MODIFY_ITEM: {
1123                         std::vector<TraceRestrictItem>::iterator old_item = TraceRestrictProgram::InstructionAt(items, offset);
1124                         if (IsTraceRestrictConditional(*old_item) != IsTraceRestrictConditional(item)) {
1125                                 return_cmd_error(STR_TRACE_RESTRICT_ERROR_CAN_T_CHANGE_CONDITIONALITY);
1126                         }
1127                         bool old_is_dual = IsTraceRestrictDoubleItem(*old_item);
1128                         bool new_is_dual = IsTraceRestrictDoubleItem(item);
1129                         *old_item = item;
1130                         if (old_is_dual && !new_is_dual) {
1131                                 items.erase(old_item + 1);
1132                         } else if (!old_is_dual && new_is_dual) {
1133                                 items.insert(old_item + 1, GetDualInstructionInitialValue(item));
1134                         }
1135                         break;
1136                 }
1137
1138                 case TRDCT_MODIFY_DUAL_ITEM: {
1139                         std::vector<TraceRestrictItem>::iterator old_item = TraceRestrictProgram::InstructionAt(items, offset);
1140                         if (!IsTraceRestrictDoubleItem(*old_item)) {
1141                                 return CMD_ERROR;
1142                         }
1143                         *(old_item + 1) = p2;
1144                         break;
1145                 }
1146
1147                 case TRDCT_REMOVE_ITEM:
1148                 case TRDCT_SHALLOW_REMOVE_ITEM: {
1149                         CommandCost res = TraceRestrictProgramRemoveItemAt(items, offset, type == TRDCT_SHALLOW_REMOVE_ITEM);
1150                         if (res.Failed()) return res;
1151                         break;
1152                 }
1153
1154                 case TRDCT_MOVE_ITEM: {
1155                         CommandCost res = TraceRestrictProgramMoveItemAt(items, offset, p2 & 1, p2 & 2);
1156                         if (res.Failed()) return res;
1157                         break;
1158                 }
1159
1160                 default:
1161                         NOT_REACHED();
1162                         break;
1163         }
1164
1165         TraceRestrictProgramActionsUsedFlags actions_used_flags;
1166         CommandCost validation_result = TraceRestrictProgram::Validate(items, actions_used_flags);
1167         if (validation_result.Failed()) {
1168                 return validation_result;
1169         }
1170
1171         if (flags & DC_EXEC) {
1172                 assert(prog);
1173
1174                 // move in modified program
1175                 prog->items.swap(items);
1176                 prog->actions_used_flags = actions_used_flags;
1177
1178                 if (prog->items.size() == 0 && prog->refcount == 1) {
1179                         // program is empty, and this tile is the only reference to it
1180                         // so delete it, as it's redundant
1181                         TraceRestrictRemoveProgramMapping(MakeTraceRestrictRefId(tile, track));
1182                 }
1183
1184                 // update windows
1185                 InvalidateWindowClassesData(WC_TRACE_RESTRICT);
1186         }
1187
1188         return CommandCost();
1189 }
1190
1191 /**
1192  * Helper function to perform parameter bit-packing and call DoCommandP, for program management actions
1193  */
1194 void TraceRestrictProgMgmtWithSourceDoCommandP(TileIndex tile, Track track, TraceRestrictDoCommandType type,
1195                 TileIndex source_tile, Track source_track, StringID error_msg)
1196 {
1197         uint32 p1 = 0;
1198         SB(p1, 0, 3, track);
1199         SB(p1, 3, 5, type);
1200         SB(p1, 8, 3, source_track);
1201         DoCommandP(tile, p1, source_tile, CMD_PROGRAM_TRACERESTRICT_SIGNAL | CMD_MSG(error_msg));
1202 }
1203
1204 /**
1205  * Sub command for copy/share/unshare operations on signal tracerestrict programs.
1206  * @param tile The tile which contains the signal.
1207  * @param flags Internal command handler stuff.
1208  * @param p1 Bitstuffed items
1209  * @param p2 Source tile, for share/copy operations
1210  * @return the cost of this operation (which is free), or an error
1211  */
1212 CommandCost CmdProgramSignalTraceRestrictProgMgmt(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text)
1213 {
1214         TraceRestrictDoCommandType type = static_cast<TraceRestrictDoCommandType>(GB(p1, 3, 5));
1215         Track track = static_cast<Track>(GB(p1, 0, 3));
1216         Track source_track = static_cast<Track>(GB(p1, 8, 3));
1217         TileIndex source_tile = static_cast<TileIndex>(p2);
1218
1219         TraceRestrictRefId self = MakeTraceRestrictRefId(tile, track);
1220         TraceRestrictRefId source = MakeTraceRestrictRefId(source_tile, source_track);
1221
1222         assert(type >= TRDCT_PROG_COPY);
1223
1224         CommandCost ret = TraceRestrictCheckTileIsUsable(tile, track);
1225         if (ret.Failed()) {
1226                 return ret;
1227         }
1228
1229         if (type == TRDCT_PROG_SHARE || type == TRDCT_PROG_COPY) {
1230                 if (self == source) {
1231                         return_cmd_error(STR_TRACE_RESTRICT_ERROR_SOURCE_SAME_AS_TARGET);
1232                 }
1233         }
1234         if (type == TRDCT_PROG_SHARE || type == TRDCT_PROG_COPY || type == TRDCT_PROG_COPY_APPEND) {
1235                 ret = TraceRestrictCheckTileIsUsable(source_tile, source_track);
1236                 if (ret.Failed()) {
1237                         return ret;
1238                 }
1239         }
1240
1241         if (type != TRDCT_PROG_RESET && !TraceRestrictProgram::CanAllocateItem()) {
1242                 return CMD_ERROR;
1243         }
1244
1245         if (!(flags & DC_EXEC)) {
1246                 return CommandCost();
1247         }
1248
1249         switch (type) {
1250                 case TRDCT_PROG_COPY: {
1251                         TraceRestrictRemoveProgramMapping(self);
1252                         TraceRestrictProgram *source_prog = GetTraceRestrictProgram(source, false);
1253                         if (source_prog && !source_prog->items.empty()) {
1254                                 TraceRestrictProgram *prog = GetTraceRestrictProgram(self, true);
1255                                 if (!prog) {
1256                                         // allocation failed
1257                                         return CMD_ERROR;
1258                                 }
1259                                 prog->items = source_prog->items; // copy
1260                                 prog->Validate();
1261                         }
1262                         break;
1263                 }
1264
1265                 case TRDCT_PROG_COPY_APPEND: {
1266                         TraceRestrictProgram *source_prog = GetTraceRestrictProgram(source, false);
1267                         if (source_prog && !source_prog->items.empty()) {
1268                                 TraceRestrictProgram *prog = GetTraceRestrictProgram(self, true);
1269                                 if (!prog) {
1270                                         // allocation failed
1271                                         return CMD_ERROR;
1272                                 }
1273                                 prog->items.reserve(prog->items.size() + source_prog->items.size()); // this is in case prog == source_prog
1274                                 prog->items.insert(prog->items.end(), source_prog->items.begin(), source_prog->items.end()); // append
1275                                 prog->Validate();
1276                         }
1277                         break;
1278                 }
1279
1280                 case TRDCT_PROG_SHARE: {
1281                         TraceRestrictRemoveProgramMapping(self);
1282                         TraceRestrictProgram *source_prog = GetTraceRestrictProgram(source, true);
1283                         if (!source_prog) {
1284                                 // allocation failed
1285                                 return CMD_ERROR;
1286                         }
1287
1288                         TraceRestrictCreateProgramMapping(self, source_prog);
1289                         break;
1290                 }
1291
1292                 case TRDCT_PROG_UNSHARE: {
1293                         std::vector<TraceRestrictItem> items;
1294                         TraceRestrictProgram *prog = GetTraceRestrictProgram(self, false);
1295                         if (prog) {
1296                                 // copy program into temporary
1297                                 items = prog->items;
1298                         }
1299                         // remove old program
1300                         TraceRestrictRemoveProgramMapping(self);
1301
1302                         if (items.size()) {
1303                                 // if prog is non-empty, create new program and move temporary in
1304                                 TraceRestrictProgram *new_prog = GetTraceRestrictProgram(self, true);
1305                                 if (!new_prog) {
1306                                         // allocation failed
1307                                         return CMD_ERROR;
1308                                 }
1309
1310                                 new_prog->items.swap(items);
1311                                 new_prog->Validate();
1312                         }
1313                         break;
1314                 }
1315
1316                 case TRDCT_PROG_RESET: {
1317                         TraceRestrictRemoveProgramMapping(self);
1318                         break;
1319                 }
1320
1321                 default:
1322                         NOT_REACHED();
1323                         break;
1324         }
1325
1326         // update windows
1327         InvalidateWindowClassesData(WC_TRACE_RESTRICT);
1328
1329         return CommandCost();
1330 }
1331
1332 /**
1333  * This is called when a station, waypoint or depot is about to be deleted
1334  * Scan program pool and change any references to it to the invalid station ID, to avoid dangling references
1335  */
1336 void TraceRestrictRemoveDestinationID(TraceRestrictOrderCondAuxField type, uint16 index)
1337 {
1338         TraceRestrictProgram *prog;
1339
1340         FOR_ALL_TRACE_RESTRICT_PROGRAMS(prog) {
1341                 for (size_t i = 0; i < prog->items.size(); i++) {
1342                         TraceRestrictItem &item = prog->items[i]; // note this is a reference,
1343                         if (GetTraceRestrictType(item) == TRIT_COND_CURRENT_ORDER ||
1344                                         GetTraceRestrictType(item) == TRIT_COND_NEXT_ORDER ||
1345                                         GetTraceRestrictType(item) == TRIT_COND_LAST_STATION) {
1346                                 if (GetTraceRestrictAuxField(item) == type && GetTraceRestrictValue(item) == index) {
1347                                         SetTraceRestrictValueDefault(item, TRVT_ORDER); // this updates the instruction in-place
1348                                 }
1349                         }
1350                         if (IsTraceRestrictDoubleItem(item)) i++;
1351                 }
1352         }
1353
1354         // update windows
1355         InvalidateWindowClassesData(WC_TRACE_RESTRICT);
1356 }
1357
1358 /**
1359  * This is called when a group is about to be deleted
1360  * Scan program pool and change any references to it to the invalid group ID, to avoid dangling references
1361  */
1362 void TraceRestrictRemoveGroupID(GroupID index)
1363 {
1364         TraceRestrictProgram *prog;
1365
1366         FOR_ALL_TRACE_RESTRICT_PROGRAMS(prog) {
1367                 for (size_t i = 0; i < prog->items.size(); i++) {
1368                         TraceRestrictItem &item = prog->items[i]; // note this is a reference,
1369                         if (GetTraceRestrictType(item) == TRIT_COND_TRAIN_GROUP && GetTraceRestrictValue(item) == index) {
1370                                 SetTraceRestrictValueDefault(item, TRVT_GROUP_INDEX); // this updates the instruction in-place
1371                         }
1372                         if (IsTraceRestrictDoubleItem(item)) i++;
1373                 }
1374         }
1375
1376         // update windows
1377         InvalidateWindowClassesData(WC_TRACE_RESTRICT);
1378 }
1379
1380 static std::unordered_multimap<VehicleID, TraceRestrictSlotID> slot_vehicle_index;
1381
1382 /**
1383  * Add vehicle ID to occupants if possible and not already an occupant
1384  * @param id Vehicle ID
1385  * @param force Add the vehicle even if the slot is at/over capacity
1386  * @return whether vehicle ID is now an occupant
1387  */
1388 bool TraceRestrictSlot::Occupy(VehicleID id, bool force)
1389 {
1390         if (this->IsOccupant(id)) return true;
1391         if (this->occupants.size() >= this->max_occupancy && !force) return false;
1392         this->occupants.push_back(id);
1393         slot_vehicle_index.emplace(id, this->index);
1394         SetBit(Train::Get(id)->flags, VRF_HAVE_SLOT);
1395         SetWindowDirty(WC_VEHICLE_DETAILS, id);
1396         InvalidateWindowClassesData(WC_TRACE_RESTRICT_SLOTS);
1397         return true;
1398 }
1399
1400 /**
1401  * Remove vehicle ID from occupants
1402  * @param id Vehicle ID
1403  */
1404 void TraceRestrictSlot::Vacate(VehicleID id)
1405 {
1406         if (container_unordered_remove(this->occupants, id)) {
1407                 this->DeIndex(id);
1408         }
1409 }
1410
1411 /** Remove all occupants */
1412 void TraceRestrictSlot::Clear()
1413 {
1414         for (VehicleID id : this->occupants) {
1415                 this->DeIndex(id);
1416         }
1417         this->occupants.clear();
1418 }
1419
1420 void TraceRestrictSlot::DeIndex(VehicleID id)
1421 {
1422         auto range = slot_vehicle_index.equal_range(id);
1423         for (auto it = range.first; it != range.second; ++it) {
1424                 if (it->second == this->index) {
1425                         bool is_first_in_range = (it == range.first);
1426
1427                         auto next = slot_vehicle_index.erase(it);
1428
1429                         if (is_first_in_range && next == range.second) {
1430                                 /* Only one item, which we've just erased, clear the vehicle flag */
1431                                 ClrBit(Train::Get(id)->flags, VRF_HAVE_SLOT);
1432                         }
1433                         break;
1434                 }
1435         }
1436         SetWindowDirty(WC_VEHICLE_DETAILS, id);
1437         InvalidateWindowClassesData(WC_TRACE_RESTRICT_SLOTS);
1438 }
1439
1440 /** Rebuild slot vehicle index after loading */
1441 void TraceRestrictSlot::RebuildVehicleIndex()
1442 {
1443         slot_vehicle_index.clear();
1444         const TraceRestrictSlot *slot;
1445         FOR_ALL_TRACE_RESTRICT_SLOTS(slot) {
1446                 for (VehicleID id : slot->occupants) {
1447                         slot_vehicle_index.emplace(id, slot->index);
1448                 }
1449         }
1450 }
1451
1452 /** Slot pool is about to be cleared */
1453 void TraceRestrictSlot::PreCleanPool()
1454 {
1455         slot_vehicle_index.clear();
1456 }
1457
1458 /** Remove vehicle ID from all slot occupants */
1459 void TraceRestrictRemoveVehicleFromAllSlots(VehicleID id)
1460 {
1461         auto range = slot_vehicle_index.equal_range(id);
1462         for (auto it = range.first; it != range.second; ++it) {
1463                 TraceRestrictSlot *slot = TraceRestrictSlot::Get(it->second);
1464                 container_unordered_remove(slot->occupants, id);
1465         }
1466         slot_vehicle_index.erase(range.first, range.second);
1467         if (range.first != range.second) InvalidateWindowClassesData(WC_TRACE_RESTRICT_SLOTS);
1468 }
1469
1470 /** Replace all instance of a vehicle ID with another, in all slot occupants */
1471 void TraceRestrictTransferVehicleOccupantInAllSlots(VehicleID from, VehicleID to)
1472 {
1473         auto range = slot_vehicle_index.equal_range(from);
1474         std::vector<TraceRestrictSlotID> slots;
1475         for (auto it = range.first; it != range.second; ++it) {
1476                 slots.push_back(it->second);
1477         }
1478         slot_vehicle_index.erase(range.first, range.second);
1479         for (TraceRestrictSlotID slot_id : slots) {
1480                 TraceRestrictSlot *slot = TraceRestrictSlot::Get(slot_id);
1481                 for (VehicleID &id : slot->occupants) {
1482                         if (id == from) {
1483                                 id = to;
1484                                 slot_vehicle_index.emplace(to, slot_id);
1485                         }
1486                 }
1487         }
1488         if (!slots.empty()) InvalidateWindowClassesData(WC_TRACE_RESTRICT_SLOTS);
1489 }
1490
1491 /** Get list of slots occupied by a vehicle ID */
1492 void TraceRestrictGetVehicleSlots(VehicleID id, std::vector<TraceRestrictSlotID> &out)
1493 {
1494         auto range = slot_vehicle_index.equal_range(id);
1495         for (auto it = range.first; it != range.second; ++it) {
1496                 out.push_back(it->second);
1497         }
1498 }
1499
1500 /**
1501  * This is called when a slot is about to be deleted
1502  * Scan program pool and change any references to it to the invalid group ID, to avoid dangling references
1503  */
1504 void TraceRestrictRemoveSlotID(TraceRestrictSlotID index)
1505 {
1506         TraceRestrictProgram *prog;
1507
1508         FOR_ALL_TRACE_RESTRICT_PROGRAMS(prog) {
1509                 for (size_t i = 0; i < prog->items.size(); i++) {
1510                         TraceRestrictItem &item = prog->items[i]; // note this is a reference,
1511                         if ((GetTraceRestrictType(item) == TRIT_SLOT || GetTraceRestrictType(item) == TRIT_COND_TRAIN_IN_SLOT) && GetTraceRestrictValue(item) == index) {
1512                                 SetTraceRestrictValueDefault(item, TRVT_SLOT_INDEX); // this updates the instruction in-place
1513                         }
1514                         if ((GetTraceRestrictType(item) == TRIT_COND_SLOT_OCCUPANCY) && GetTraceRestrictValue(item) == index) {
1515                                 SetTraceRestrictValueDefault(item, TRVT_SLOT_INDEX_INT); // this updates the instruction in-place
1516                         }
1517                         if (IsTraceRestrictDoubleItem(item)) i++;
1518                 }
1519         }
1520 }
1521
1522 static bool IsUniqueSlotName(const char *name)
1523 {
1524         const TraceRestrictSlot *slot;
1525         FOR_ALL_TRACE_RESTRICT_SLOTS(slot) {
1526                 if (slot->name == name) return false;
1527         }
1528         return true;
1529 }
1530
1531 /**
1532  * Create a new slot.
1533  * @param tile unused
1534  * @param flags type of operation
1535  * @param p1   unused
1536  * @param p2   unused
1537  * @param text new slot name
1538  * @return the cost of this operation or an error
1539  */
1540 CommandCost CmdCreateTraceRestrictSlot(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text)
1541 {
1542         if (!TraceRestrictSlot::CanAllocateItem()) return CMD_ERROR;
1543         if (StrEmpty(text)) return CMD_ERROR;
1544
1545         size_t length = Utf8StringLength(text);
1546         if (length <= 0) return CMD_ERROR;
1547         if (length >= MAX_LENGTH_TRACE_RESTRICT_SLOT_NAME_CHARS) return CMD_ERROR;
1548         if (!IsUniqueSlotName(text)) return_cmd_error(STR_ERROR_NAME_MUST_BE_UNIQUE);
1549
1550         if (flags & DC_EXEC) {
1551                 TraceRestrictSlot *slot = new TraceRestrictSlot(_current_company);
1552                 slot->name = text;
1553
1554                 // update windows
1555                 InvalidateWindowClassesData(WC_TRACE_RESTRICT);
1556                 InvalidateWindowClassesData(WC_TRACE_RESTRICT_SLOTS);
1557         }
1558
1559         return CommandCost();
1560 }
1561
1562
1563 /**
1564  * Deletes a slot.
1565  * @param tile unused
1566  * @param flags type of operation
1567  * @param p1   index of array group
1568  *      - p1 bit 0-15 : Slot ID
1569  * @param p2   unused
1570  * @param text unused
1571  * @return the cost of this operation or an error
1572  */
1573 CommandCost CmdDeleteTraceRestrictSlot(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text)
1574 {
1575         TraceRestrictSlot *slot = TraceRestrictSlot::GetIfValid(p1);
1576         if (slot == NULL || slot->owner != _current_company) return CMD_ERROR;
1577
1578         if (flags & DC_EXEC) {
1579                 /* notify tracerestrict that group is about to be deleted */
1580                 TraceRestrictRemoveSlotID(slot->index);
1581
1582                 delete slot;
1583
1584                 InvalidateWindowClassesData(WC_TRACE_RESTRICT);
1585                 InvalidateWindowClassesData(WC_TRACE_RESTRICT_SLOTS);
1586                 InvalidateWindowClassesData(WC_VEHICLE_ORDERS);
1587         }
1588
1589         return CommandCost();
1590 }
1591
1592 /**
1593  * Alter a slot
1594  * @param tile unused
1595  * @param flags type of operation
1596  * @param p1   index of array group
1597  *   - p1 bit 0-15 : GroupID
1598  *   - p1 bit 16: 0 - Rename grouop
1599  *                1 - Change max occupancy
1600  * @param p2   new max occupancy
1601  * @param text the new name
1602  * @return the cost of this operation or an error
1603  */
1604 CommandCost CmdAlterTraceRestrictSlot(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text)
1605 {
1606         TraceRestrictSlot *slot = TraceRestrictSlot::GetIfValid(GB(p1, 0, 16));
1607         if (slot == NULL || slot->owner != _current_company) return CMD_ERROR;
1608
1609         if (!HasBit(p1, 16)) {
1610                 /* Rename slot */
1611
1612                 if (StrEmpty(text)) return CMD_ERROR;
1613                 size_t length = Utf8StringLength(text);
1614                 if (length <= 0) return CMD_ERROR;
1615                 if (length >= MAX_LENGTH_TRACE_RESTRICT_SLOT_NAME_CHARS) return CMD_ERROR;
1616                 if (!IsUniqueSlotName(text)) return_cmd_error(STR_ERROR_NAME_MUST_BE_UNIQUE);
1617
1618                 if (flags & DC_EXEC) {
1619                         slot->name = text;
1620                 }
1621         } else {
1622                 /* Change max occupancy */
1623
1624                 if (flags & DC_EXEC) {
1625                         slot->max_occupancy = p2;
1626                 }
1627         }
1628
1629         if (flags & DC_EXEC) {
1630                 // update windows
1631                 InvalidateWindowClassesData(WC_TRACE_RESTRICT);
1632                 InvalidateWindowClassesData(WC_TRACE_RESTRICT_SLOTS);
1633                 InvalidateWindowClassesData(WC_VEHICLE_ORDERS);
1634         }
1635
1636         return CommandCost();
1637 }
1638
1639 /**
1640  * Add a vehicle to a slot
1641  * @param tile unused
1642  * @param flags type of operation
1643  * @param p1   index of array group
1644  *   - p1 bit 0-15 : GroupID
1645  * @param p2   index of vehicle
1646  *   - p2 bit 0-19 : VehicleID
1647  * @param text unused
1648  * @return the cost of this operation or an error
1649  */
1650 CommandCost CmdAddVehicleTraceRestrictSlot(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text)
1651 {
1652         TraceRestrictSlot *slot = TraceRestrictSlot::GetIfValid(p1);
1653         Vehicle *v = Vehicle::GetIfValid(p2);
1654         if (slot == NULL || slot->owner != _current_company) return CMD_ERROR;
1655         if (v == NULL || v->owner != _current_company) return CMD_ERROR;
1656
1657         if (flags & DC_EXEC) {
1658                 slot->Occupy(v->index, true);
1659         }
1660
1661         return CommandCost();
1662 }
1663
1664 /**
1665  * Remove a vehicle from a slot
1666  * @param tile unused
1667  * @param flags type of operation
1668  * @param p1   index of array group
1669  *   - p1 bit 0-15 : GroupID
1670  * @param p2   index of vehicle
1671  *   - p2 bit 0-19 : VehicleID
1672  * @param text unused
1673  * @return the cost of this operation or an error
1674  */
1675 CommandCost CmdRemoveVehicleTraceRestrictSlot(TileIndex tile, DoCommandFlag flags, uint32 p1, uint32 p2, const char *text)
1676 {
1677         TraceRestrictSlot *slot = TraceRestrictSlot::GetIfValid(p1);
1678         Vehicle *v = Vehicle::GetIfValid(p2);
1679         if (slot == NULL || slot->owner != _current_company) return CMD_ERROR;
1680         if (v == NULL) return CMD_ERROR; // permit removing vehicles of other owners from your own slot
1681
1682         if (flags & DC_EXEC) {
1683                 slot->Vacate(v->index);
1684         }
1685
1686         return CommandCost();
1687 }