SA_DiceEvaluator.m

   1 //
   2 //  SA_DiceEvaluator.m
   3 //
   4 //  Copyright 2016-2021 Said Achmiz.
   5 //  See LICENSE and README.md for more info.
   6
   7 #import "SA_DiceEvaluator.h"
   8
   9 #import "SA_DiceBag.h"
  10 #import "SA_DiceParser.h"
  11 #import "SA_DiceExpression.h"
  12 #import "SA_DiceExpressionStringConstants.h"
  13
  14 #import "SA_Utility.h"
  15
  16 /**************************/
  17 #pragma mark Defined values
  18 /**************************/
  19
  20 #define DEFAULT_MAX_DIE_COUNT    1000   // One thousand
  21 #define DEFAULT_MAX_DIE_SIZE    10000   // Ten thousand
  22
  23 /***************************************************/
  24 #pragma mark - SA_DiceEvaluator class implementation
  25 /***************************************************/
  26
  27 @implementation SA_DiceEvaluator {
  28         SA_DiceBag *_diceBag;
  29
  30         NSUInteger _maxDieCount;
  31         NSUInteger _maxDieSize;
  32 }
  33
  34 /************************/
  35 #pragma mark - Properties
  36 /************************/
  37
  38 -(NSUInteger) maxDieCount {
  39         return _maxDieCount;
  40 }
  41 -(void) setMaxDieCount:(NSUInteger)maxDieCount {
  42         if (maxDieCount > (NSUIntegerMax / _maxDieSize)) {
  43                 _maxDieCount = NSUIntegerMax / _maxDieSize;
  44         } else {
  45                 _maxDieCount = maxDieCount;
  46         }
  47 }
  48
  49 -(NSUInteger) maxDieSize {
  50         return _maxDieSize;
  51 }
  52 -(void) setMaxDieSize:(NSUInteger)maxDieSize {
  53         if (   maxDieSize > [_diceBag biggestPossibleDieSize]
  54                 || maxDieSize > (NSIntegerMax / _maxDieCount)) {
  55                 _maxDieSize = (([_diceBag biggestPossibleDieSize] < (NSIntegerMax / _maxDieCount))
  56                                            ? [_diceBag biggestPossibleDieSize]
  57                                            : (NSIntegerMax / _maxDieCount));
  58         } else {
  59                 _maxDieSize = maxDieSize;
  60         }
  61 }
  62
  63 /**************************/
  64 #pragma mark - Initializers
  65 /**************************/
  66
  67 -(instancetype) init {
  68         if (!(self = [super init]))
  69                 return nil;
  70
  71         _maxDieCount = DEFAULT_MAX_DIE_COUNT;
  72         _maxDieSize = DEFAULT_MAX_DIE_SIZE;
  73
  74         _diceBag = [SA_DiceBag new];
  75
  76         return self;
  77 }
  78
  79 /****************************/
  80 #pragma mark - Public methods
  81 /****************************/
  82
  83 // TODO: Possibly refuse to evaluate an expression that’s already evaluated?
  84 // (i.e., it has a  ...  .result?? .value??)
  85 -(SA_DiceExpression *) resultOfExpression:(SA_DiceExpression *)expression {
  86         // Check to see if the expression is erroneous (i.e. the parser has judged
  87         // that it is malformed, etc.). If so, decline to evaluate the expression;
  88         // return (a copy of) it, unchanged.
  89         if (expression.errorBitMask != 0) {
  90                 return [expression copy];
  91         }
  92
  93         /*
  94          NOTE: Even if an expression is not erroneous (i.e. if it has no syntax
  95          errors), it may still not be possible to evaluate it. For example, ‘5d0’
  96          is a perfectly well-formed die string, and will yield an expression tree
  97          as follows:
  98
  99          [ type                 : SA_DiceExpressionTerm_ROLL_COMMAND,
 100            rollCommand  : SA_DiceExpressionRollCommand_SUM,
 101            dieCount             : [ type        : SA_DiceExpressionTerm_VALUE,
 102                                                 value   : @(5)
 103                                                 ],
 104            dieSize              : [ type        : SA_DiceExpressionTerm_VALUE,
 105                                                 value   : @(0)
 106                                                 ]
 107            ]
 108
 109          This is, of course, an illegal expression; we can’t roll a die of size 0
 110          (a die with zero sides?).
 111
 112          If we encounter such an illegal expression, we add an appropriate error to
 113          the -[errorBitMask]. We are not required to set a value (-[value] property)
 114          in such a case.
 115          */
 116
 117         switch (expression.type) {
 118                 case SA_DiceExpressionTerm_OPERATION: {
 119                         return [self resultOfExpressionDescribingOperation:expression];
 120                         break;
 121                 }
 122                 case SA_DiceExpressionTerm_ROLL_COMMAND: {
 123                         return [self resultOfExpressionDescribingRollCommand:expression];
 124                         break;
 125                 }
 126                 case SA_DiceExpressionTerm_ROLL_MODIFIER: {
 127                         return [self resultOfExpressionDescribingRollModifier:expression];
 128                         break;
 129                 }
 130                 case SA_DiceExpressionTerm_VALUE:
 131                 default: {
 132                         return [self resultOfExpressionDescribingValue:expression];
 133                         break;
 134                 }
 135         }
 136 }
 137
 138 /****************************/
 139 #pragma mark - Helper methods
 140 /****************************/
 141
 142 -(SA_DiceExpression *) resultOfExpressionDescribingValue:(SA_DiceExpression *)expression {
 143         SA_DiceExpression *result = [expression copy];
 144
 145         result.result = result.value;
 146
 147         return result;
 148 }
 149
 150 -(SA_DiceExpression *) resultOfExpressionDescribingRollCommand:(SA_DiceExpression *)expression {
 151         SA_DiceExpression *result = [expression copy];
 152
 153         // For now, only sum and exploding sum (i.e., sum but with exploding dice)
 154         // are supported. Other sorts of roll commands may be added later.
 155         switch (result.rollCommand) {
 156                 case SA_DiceExpressionRollCommand_SUM:
 157                 case SA_DiceExpressionRollCommand_SUM_EXPLODING: {
 158                         // First, recursively evaluate the expressions that represent the
 159                         // die count and (for standard dice) the die size.
 160                         result.dieCount = [self resultOfExpression:result.dieCount];
 161                         if (result.dieType == SA_DiceExpressionDice_STANDARD)
 162                                 result.dieSize = [self resultOfExpression:result.dieSize];
 163
 164                         // Evaluating those expressions may have generated an error(s);
 165                         // propagate any errors up to the current term.
 166                         result.errorBitMask |= result.dieCount.errorBitMask;
 167                         if (result.dieType == SA_DiceExpressionDice_STANDARD)
 168                                 result.errorBitMask |= result.dieSize.errorBitMask;
 169
 170                         // If indeed we’ve turned up errors, return.
 171                         if (result.errorBitMask != 0)
 172                                 return result;
 173
 174                         // Evaluating the two sub-expressions didn’t generate errors; this means
 175                         // that we have successfully generated values for both the die count and
 176                         // (for standard dice) the die size...
 177                         NSInteger dieCount = result.dieCount.result.integerValue;
 178                         NSInteger dieSize = 0;
 179                         if (result.dieType == SA_DiceExpressionDice_STANDARD)
 180                                 dieSize = result.dieSize.result.integerValue;
 181
 182                         // ... but, the resulting values of the expressions may make it
 183                         // impossible to evaluate the roll command. Check to see whether the die
 184                         // count and die size have legal values.
 185                         if (dieCount < 0) {
 186                                 result.errorBitMask |= SA_DiceExpressionError_DIE_COUNT_NEGATIVE;
 187                         } else if (dieCount > _maxDieCount) {
 188                                 result.errorBitMask |= SA_DiceExpressionError_DIE_COUNT_EXCESSIVE;
 189                         }
 190
 191                         // Die type only matters for standard dice, not for Fudge dice.
 192                         if (result.dieType == SA_DiceExpressionDice_STANDARD) {
 193                                 if (dieSize < 1) {
 194                                         result.errorBitMask |= SA_DiceExpressionError_DIE_SIZE_INVALID;
 195                                 } else if (dieSize > _maxDieSize) {
 196                                         result.errorBitMask |= SA_DiceExpressionError_DIE_SIZE_EXCESSIVE;
 197                                 }
 198                         }
 199
 200                         // If indeed the die count or die size fall outside of their allowed
 201                         // ranges, return.
 202                         if (result.errorBitMask != 0)
 203                                 return result;
 204
 205                         // The die count and die size have legal values. We can safely roll the
 206                         // requisite number of dice, and take the sum of the rolls (if needed).
 207                         // NOTE: _maxDieSize is guaranteed to be no greater than the largest die
 208                         // size that the SA_DiceBag can roll (this is enforced by the setter
 209                         // method for the maxDieSize property), so we need not check to see
 210                         // if the return value of rollDie: or rollNumber:ofDice: is valid.
 211                         // We are also guaranteed that the product of _maxDieCount and
 212                         // _maxDieSize is no greater than the largest unsigned value that can be
 213                         // stored by whatever numeric type we specify simple value terms (terms
 214                         // of type SA_DiceExpressionTerm_VALUE) to contain (likewise enforced
 215                         // by the setters for both maxDieSize and maxDieCount), therefore we
 216                         // need not worry about overflow here.
 217                         if (dieCount == 0) {
 218                                 result.result = @(0);
 219                                 result.rolls = @[];
 220                         } else {
 221                                 NSArray *rolls;
 222                                 if (result.dieType == SA_DiceExpressionDice_STANDARD) {
 223                                         SA_DiceRollingOptions options = (result.rollCommand == SA_DiceExpressionRollCommand_SUM_EXPLODING) ? SA_DiceRollingExplodingDice : 0;
 224                                         rolls = [_diceBag rollNumber:dieCount
 225                                                                                   ofDice:dieSize
 226                                                                          withOptions:options];
 227                                 } else if (result.dieType == SA_DiceExpressionDice_FUDGE) {
 228                                         rolls = [_diceBag rollFudgeDice:dieCount];
 229                                 }
 230
 231                                 result.result = [rolls valueForKeyPath:@"@sum.self"];
 232                                 result.rolls = rolls;
 233                         }
 234
 235                         break;
 236                 }
 237                 default: {
 238                         result.errorBitMask |= SA_DiceExpressionError_UNKNOWN_ROLL_COMMAND;
 239
 240                         break;
 241                 }
 242         }
 243
 244         return result;
 245 }
 246
 247 -(SA_DiceExpression *) resultOfExpressionDescribingRollModifier:(SA_DiceExpression *)expression {
 248         SA_DiceExpression *result = [expression copy];
 249
 250         switch (result.rollModifier) {
 251                 case SA_DiceExpressionRollModifier_KEEP_HIGHEST:
 252                 case SA_DiceExpressionRollModifier_KEEP_LOWEST: {
 253                         // These roll modifiers takes the highest, or the lowest, N rolls
 254                         // out of all the rolls generated by a roll command, discarding the
 255                         // rest, and summing the kept ones.
 256
 257                         // First, check if the left-hand operand is a roll command (and
 258                         // specifically, a simple sum; though this latter requirement may
 259                         // be dropped later).
 260                         // TODO: re-evaluate this ^
 261                         // If the left-hand operand is not a roll-and-sum, then the KEEP
 262                         // modifier cannot be applied to it. In that case, we add an error
 263                         // and return the result without evaluating.
 264                         if (   result.leftOperand.type != SA_DiceExpressionTerm_ROLL_COMMAND
 265                                 || (   result.leftOperand.rollCommand != SA_DiceExpressionRollCommand_SUM
 266                                         && result.leftOperand.rollCommand != SA_DiceExpressionRollCommand_SUM_EXPLODING)
 267                                 ) {
 268                                 result.errorBitMask |= SA_DiceExpressionError_ROLL_MODIFIER_INAPPLICABLE;
 269                                 return result;
 270                         }
 271
 272                         // We now know the left-hand operand is a roll command. Recursively
 273                         // evaluate the expressions that represent the roll command and the
 274                         // modifier value (the right-hand operand).
 275                         result.leftOperand = [self resultOfExpression:result.leftOperand];
 276                         result.rightOperand = [self resultOfExpression:result.rightOperand];
 277
 278                         // Evaluating the operands may have generated an error(s); propagate any
 279                         // errors up to the current term.
 280                         result.errorBitMask |= result.leftOperand.errorBitMask;
 281                         result.errorBitMask |= result.rightOperand.errorBitMask;
 282
 283                         // If indeed we’ve turned up errors, return.
 284                         if (result.errorBitMask != 0)
 285                                 return result;
 286
 287                         // Evaluating the operands didn’t generate any errors; this means
 288                         // that on the left hand we have a set of rolls (as well as a
 289                         // result, which we are ignoring), and on the right hand we have a
 290                         // result, which specifies how many rolls to keep.
 291                         NSArray <NSNumber *> *rolls = result.leftOperand.rolls;
 292                         NSNumber *keepHowMany = result.rightOperand.result;
 293
 294                         // However, it is now possible that the “keep how many” value
 295                         // exceeds the number of rolls, which would make the expression
 296                         // incoherent. If so, add an error and return.
 297                         if (keepHowMany.unsignedIntegerValue > rolls.count) {
 298                                 result.errorBitMask |= SA_DiceExpressionError_KEEP_COUNT_EXCEEDS_ROLL_COUNT;
 299                                 return result;
 300                         }
 301
 302                         // It is also possible that the “keep how many” value is negative.
 303                         // This, too, would make the expression incoherent. Likewise, add
 304                         // an error and return.
 305                         if (keepHowMany < 0) {
 306                                 result.errorBitMask |= SA_DiceExpressionError_KEEP_COUNT_NEGATIVE;
 307                                 return result;
 308                         }
 309
 310                         // We sort the rolls array...
 311                         BOOL sortAscending = (result.rollModifier == SA_DiceExpressionRollModifier_KEEP_LOWEST);
 312                         result.rolls = [rolls sortedArrayUsingDescriptors:@[ [NSSortDescriptor sortDescriptorWithKey:@"integerValue"
 313                                                                                                                                                                                            ascending:sortAscending] ]];
 314
 315                         // And the ‘result’ property of the result expression is the sum of
 316                         // the first <keepHowMany> elements of the sorted rolls array.
 317                         result.result = [[result.rolls subarrayWithRange:NSRangeMake(0, keepHowMany.unsignedIntegerValue)] valueForKeyPath:@"@sum.self"];
 318
 319                         break;
 320                 }
 321                 default: {
 322                         result.errorBitMask |= SA_DiceExpressionError_UNKNOWN_ROLL_MODIFIER;
 323
 324                         break;
 325                 }
 326         }
 327
 328         return result;
 329 }
 330
 331 -(SA_DiceExpression *) resultOfExpressionDescribingOperation:(SA_DiceExpression *)expression {
 332         SA_DiceExpression *result = [expression copy];
 333
 334         // First, recursively evaluate the expressions that represent the
 335         // left-hand-side and right-hand-side operands.
 336         result.leftOperand = [self resultOfExpression:result.leftOperand];
 337         result.rightOperand = [self resultOfExpression:result.rightOperand];
 338
 339         // Evaluating the operands may have generated an error(s); propagate any
 340         // errors up to the current term.
 341         result.errorBitMask |= result.leftOperand.errorBitMask;
 342         result.errorBitMask |= result.rightOperand.errorBitMask;
 343
 344         // If indeed we’ve turned up errors, return.
 345         if (result.errorBitMask != 0)
 346                 return result;
 347
 348         // Evaluating the operands didn’t generate any errors. We have valid
 349         // operands.
 350         NSInteger leftOperand = result.leftOperand.result.integerValue;
 351         NSInteger rightOperand = result.rightOperand.result.integerValue;
 352
 353         switch (result.operator) {
 354                 case SA_DiceExpressionOperator_MINUS: {
 355                         // First, we check for possible overflow...
 356                         if (   leftOperand > 0
 357                                 && rightOperand < 0
 358                                 && (NSIntegerMax + rightOperand) < leftOperand) {
 359                                 result.errorBitMask |= SA_DiceExpressionError_INTEGER_OVERFLOW_SUBTRACTION;
 360                                 break;
 361                         } else if (   leftOperand < 0
 362                                            && rightOperand > 0
 363                                            && (NSIntegerMin + rightOperand) > leftOperand) {
 364                                 result.errorBitMask |= SA_DiceExpressionError_INTEGER_UNDERFLOW_SUBTRACTION;
 365                                 break;
 366                         }
 367
 368                         // No overflow will occur. We can perform the subtraction operation.
 369                         result.result = @(leftOperand - rightOperand);
 370                         break;
 371                 }
 372                 case SA_DiceExpressionOperator_PLUS: {
 373                         // First, we check for possible overflow...
 374                         if (   rightOperand > 0
 375                                 && leftOperand > 0
 376                                 && (NSIntegerMax - rightOperand) < leftOperand) {
 377                                 result.errorBitMask |= SA_DiceExpressionError_INTEGER_OVERFLOW_ADDITION;
 378                                 break;
 379                         } else if (   rightOperand < 0
 380                                            && leftOperand < 0
 381                                            && (NSIntegerMin - rightOperand) > leftOperand) {
 382                                 result.errorBitMask |= SA_DiceExpressionError_INTEGER_UNDERFLOW_ADDITION;
 383                                 break;
 384                         }
 385
 386                         // No overflow will occur. We can perform the addition operation.
 387                         result.result = @(leftOperand + rightOperand);
 388                         break;
 389                 }
 390                 case SA_DiceExpressionOperator_TIMES: {
 391                         // First, we check for possible overflow...
 392                         if (   (   leftOperand == NSIntegerMin
 393                                         && (   rightOperand != 0
 394                                                 || rightOperand != 1 ))
 395                                 || (   rightOperand == NSIntegerMin
 396                                         && (   leftOperand != 0
 397                                                 || leftOperand != 1 ))
 398                                 || (   leftOperand != 0
 399                                         && ((NSIntegerMax / ABS(leftOperand)) < rightOperand))
 400                                 ) {
 401                                 if (   (   leftOperand > 0
 402                                                 && rightOperand > 0)
 403                                         || (   leftOperand < 0
 404                                                 && rightOperand < 0)) {
 405                                         result.errorBitMask |= SA_DiceExpressionError_INTEGER_OVERFLOW_MULTIPLICATION;
 406                                 } else {
 407                                         result.errorBitMask |= SA_DiceExpressionError_INTEGER_UNDERFLOW_MULTIPLICATION;
 408                                 }
 409                                 break;
 410                         }
 411
 412                         // No overflow will occur. We can perform the multiplication operation.
 413                         result.result = @(leftOperand * rightOperand);
 414                         break;
 415                 }
 416                 default: {
 417                         // We add the appropriate error. We do not set a value for the
 418                         // result property.
 419                         result.errorBitMask |= SA_DiceExpressionError_UNKNOWN_OPERATOR;
 420                         break;
 421                 }
 422         }
 423
 424         return result;
 425 }
 426
 427 @end