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