backoff.dart

backoff.dart

//

main.dart

import 'dart:async';
import 'dart:collection';
import 'dart:math';

import 'package:collection/collection.dart';

class BackoffDelay {
  static const zero = BackoffDelay(
    baseDuration: Duration.zero,
    jitterDuration: Duration.zero,
    duration: Duration.zero,
  );

  /// O tempo de espera atual.
  final Duration baseDuration;

  /// O tempo de espera atual.
  final Duration jitterDuration;

  /// O tempo de espera atual.
  final Duration duration;

  /// Contagem de quantas chamadas foram realizadas até o momento.
  ///
  /// Se não foi realizada nenhuma **chamada** até o momento, `retryCount == 0`.
  /// (ie. não houve nenhuma tentativa, esta será a primeira chamada).
  ///
  /// Se não foi realizada nenhuma **espera** até o momento, `retryCount == 1`.
  /// (ie. houve ao menos uma tentativa, e esta será a primeira espera/retentativa).
  final int retryCount;

  const BackoffDelay({
    required this.baseDuration,
    required this.jitterDuration,
    required this.duration,
    this.retryCount = 0,
  });

  const BackoffDelay.ofBaseDuration(this.baseDuration, {this.retryCount = 0})
      : duration = baseDuration,
        jitterDuration = Duration.zero;

  BackoffDelay next({
    required Duration duration,
    required Duration baseDuration,
    required Duration jitterDuration,
  }) {
    return BackoffDelay(
      baseDuration: baseDuration,
      jitterDuration: jitterDuration,
      duration: duration,
      retryCount: retryCount + 1,
    );
  }
}

abstract class Backoff {
  /// Reinicia a contagem e valor dos delays.
  ///
  /// Após a execução de `resetDelays()`, a próxima chamada à
  /// `getNextDelay()` terá resultado similar à primeira execução deste.
  /// (ie. como se fosse a primeira chamada à `getNextDelay()`).
  void reset();

  /// Calcula o próximo tempo de espera.
  BackoffDelay nextDelay();
}

typedef OnCalculateBackoffDelay = Duration Function(
    BackoffDelay previousDelay, CustomizableBackoff backoff);

typedef OnCalculateBackoffJitter = Duration Function(
    Duration currentBaseDuration, CustomizableBackoff backoff);

typedef OnGenerateValue<T> = FutureOr<T> Function();

typedef OnStopIf<T> = FutureOr<bool> Function(
  T result,
  BackoffDelay current,
);

typedef OnRetryIf<T> = FutureOr<bool> Function(
  dynamic error,
  BackoffDelay current,
);

typedef OnRegenerateIf<T> = FutureOr<bool> Function(
  T result,
  BackoffDelay current,
);

class CustomizableBackoff extends Backoff {
  /// Tempo de espera base, ou inicial.
  final Duration initialDuration;

  /// Tempo de espera mínimo, se houver.
  final Duration? minDuration;

  /// Tempo de espera máximo, se houver.
  final Duration? maxDuration;

  /// Tempo de espera adicionado a cada cálculo.
  final OnCalculateBackoffJitter onCalculateJitter;

  /// Tempo de espera adicionado a cada cálculo.
  final OnCalculateBackoffDelay onCalculateDelay;

  /// Indica se a primeira execução deve ser imediata.
  final bool immediate;

  /// Número máximo de execuções armazenadas.
  final int maxHistorySize;

  QueueList<BackoffDelay> get history => _history;

  int get retryCount => _current != null ? _current!.retryCount : 0;

  final QueueList<BackoffDelay> _history = QueueList<BackoffDelay>();

  BackoffDelay? _current;

  CustomizableBackoff({
    Duration? initialDuration,
    this.minDuration,
    this.maxDuration = defaultMaxDelayDuration,
    this.maxHistorySize = defaultMaxHistorySize,
    OnCalculateBackoffDelay? onCalculateDelay,
    this.onCalculateJitter = defaultJitter,
    this.immediate = _defaultImmediate,
  })  : initialDuration = initialDuration ?? defaultInitialDelayDuration,
        this.onCalculateDelay = onCalculateDelay ?? defaultDelay();

  @override
  void reset() {
    _current = null;
    _history.clear();
  }

  @override
  BackoffDelay nextDelay() {
    if (_current != null) {
      _addToHistory(_current!);

      if (immediate && _current!.retryCount == 0) {
        _current = BackoffDelay.ofBaseDuration(
          initialDuration,
          retryCount: 1,
        );
      } else {
        _current = _calculateNextDelay(_current!);
      }
    } else if (immediate) {
      _current = BackoffDelay.zero;
    } else {
      _current = BackoffDelay.ofBaseDuration(initialDuration);
    }

    return _current!;
  }

  Duration clampDuration(Duration duration) {
    return _clampDuration(
      duration,
      minDuration ?? duration,
      maxDuration ?? duration,
    );
  }

  BackoffDelay _calculateNextDelay(BackoffDelay previousDelay) {
    assert(_current != null);

    Duration baseDuration = _doCalculateDuration(previousDelay);
    Duration jitterDuration = _doCalculateJitter(baseDuration);
    Duration duration = baseDuration + jitterDuration;
    duration = clampDuration(duration);

    return _current!.next(
      baseDuration: baseDuration,
      jitterDuration: jitterDuration,
      duration: duration,
    );
  }

  Duration _doCalculateDuration(BackoffDelay previousDelay) {
    return onCalculateDelay(previousDelay, this);
  }

  Duration _doCalculateJitter(Duration currentDuration) {
    return onCalculateJitter(currentDuration, this);
  }

  void _addToHistory(BackoffDelay delay) async {
    _history.add(delay);
    int endIndex = _history.length - maxHistorySize;
    if (endIndex > 0) {
      _history.removeRange(0, endIndex);
    }
  }
}

const Duration defaultInitialDelayDuration = Duration(milliseconds: 100);
const Duration defaultMaxDelayDuration =
    Duration(microseconds: 9007199254740991);
const double defaultJitterFactor = 0.20;
const int unlimitedRetries = -1;
const bool _defaultImmediate = true;
const int defaultMaxHistorySize = 5;
const defaultJitter = defaultRandomJitter;

Duration _minDurationOf(Duration lhs, Duration rhs) {
  return lhs == rhs
      ? lhs
      : lhs.compareTo(rhs) <= 0
          ? lhs
          : rhs;
}

Duration _maxDurationOf(Duration lhs, Duration rhs) {
  return lhs == rhs
      ? lhs
      : lhs.compareTo(rhs) >= 0
          ? lhs
          : rhs;
}

Duration _clampDuration(Duration duration, Duration min, Duration max) {
  return _minDurationOf(_maxDurationOf(duration, min), max);
}

Duration _generateRandomDuration(Duration min, Duration max) {
  assert(max >= min);

  if (max == min) {
    return max;
  }

  int usMin = min.inMicroseconds;
  int usMax = max.inMicroseconds;
  int usDiff = (usMax - usMin).abs();
  int usValue = usMin + Random().nextInt(usDiff);
  Duration value = Duration(microseconds: usValue);

  return value;
}

OnCalculateBackoffDelay defaultDelay() {
  return fibonacciDelay();
}

Duration noDelay(
  BackoffDelay previousDelay,
  CustomizableBackoff backoff,
) {
  return Duration.zero;
}

Duration sameDelay(
  BackoffDelay previousDelay,
  CustomizableBackoff backoff,
) {
  return previousDelay.baseDuration;
}

OnCalculateBackoffDelay fibonacciDelay() {
  return (BackoffDelay previousDelay, CustomizableBackoff backoff) {
    BackoffDelay first = backoff.history.length > 1
        ? backoff.history[backoff.history.length - 2]
        : BackoffDelay.zero;
    BackoffDelay second = backoff.history.isNotEmpty
        ? backoff.history.last
        : BackoffDelay.ofBaseDuration(backoff.initialDuration);
    return first.baseDuration + second.baseDuration;
  };
}

OnCalculateBackoffDelay incrementalDelay({
  Duration add = Duration.zero,
  bool exponential = false,
}) {
  return (BackoffDelay previousDelay, CustomizableBackoff backoff) {
    num factorInc = boolToInt(!backoff.immediate) + boolToInt(!exponential);
    num factor = min(backoff.retryCount + factorInc, pow(2, 31));
    num mult = factor;
    if (exponential) {
      mult = pow(2, min(factor, 31));
    }
    Duration delay = backoff.initialDuration * mult;
    delay += add;
    return delay;
  };
}

OnCalculateBackoffDelay cumulativeDelay({
  Duration add = Duration.zero,
  bool exponential = false,
}) {
  return (BackoffDelay previousDelay, CustomizableBackoff backoff) {
    num factorInc = boolToInt(!!backoff.immediate) + boolToInt(!exponential);
    num factor = min(backoff.retryCount + factorInc, pow(2, 31));
    num mult = factor;
    if (exponential) {
      mult = pow(2, min(factor, 31));
    }
    Duration previousDuration = previousDelay.baseDuration;
    previousDuration += backoff.initialDuration * mult;
    previousDuration += add;
    return previousDuration;
  };
}

Duration noJitter(
  Duration delay,
  CustomizableBackoff backoff,
) {
  return Duration.zero;
}

OnCalculateBackoffJitter randomJitter({
  List<Duration Function(Duration)>? limits,
  List<double>? factors,
  double? factor,
  List<Duration>? absoluteLimits,
}) {
  assert(factor == null || (factor <= 1 && factor >= 0));

  return (Duration duration, CustomizableBackoff backoff) {
    Duration minJitter = duration - duration * defaultJitterFactor;
    Duration maxJitter = duration + duration * defaultJitterFactor;

    if (limits != null) {
      minJitter = limits[0](duration);
      maxJitter = limits[1](duration);
    } else if (factors != null) {
      minJitter = duration * factors[0];
      maxJitter = duration * factors[1];
    } else if (factor != null) {
      minJitter = duration - duration * factor;
      maxJitter = duration + duration * factor;
    }

    if (absoluteLimits != null) {
      minJitter = _maxDurationOf(minJitter, absoluteLimits[0]);
      maxJitter = _minDurationOf(maxJitter, absoluteLimits[1]);
    }

    Duration jitter = _generateRandomDuration(minJitter, maxJitter);
    return jitter;
  };
}

Duration defaultRandomJitter(
  Duration currentDuration,
  CustomizableBackoff backoff,
) {
  Duration jitter = _generateRandomDuration(
    currentDuration - currentDuration * defaultJitterFactor,
    currentDuration + currentDuration * defaultJitterFactor,
  );
  return jitter;
}

Backoff backoff({
  Duration? initialDuration,
  Duration? minDuration,
  Duration? maxDuration,
  OnCalculateBackoffDelay? delay,
  OnCalculateBackoffJitter jitter = defaultJitter,
  bool immediate = _defaultImmediate,
  int maxHistorySize = defaultMaxHistorySize,
}) {
  return CustomizableBackoff(
    onCalculateDelay: delay ?? defaultDelay(),
    onCalculateJitter: jitter,
    initialDuration: initialDuration,
    minDuration: minDuration,
    maxDuration: maxDuration,
    immediate: immediate,
    maxHistorySize: maxHistorySize,
  );
}

int boolToInt(bool value) {
  return value ? 1 : 0;
}

FutureOr<bool> _selectFirst<T>(
  T result,
  BackoffDelay current,
) {
  return true;
}

FutureOr<bool> _rethrowIfError<T>(
  dynamic error,
  BackoffDelay current,
) {
  return error != null;
}

FutureOr<bool> _regenerateIfNoError<T>(
  T? result,
  dynamic error,
  BackoffDelay current,
) {
  return error != null;
}

FutureOr<bool> _noRegenerate<T>(
  T result,
  BackoffDelay current,
) {
  return false;
}

const _defaultBackoff = backoff;

Backoff noBackoff({
  OnCalculateBackoffJitter jitter = noJitter,
}) {
  return backoff(
    delay: noDelay,
    jitter: jitter,
    immediate: true,
    initialDuration: Duration.zero,
    maxHistorySize: 0,
  );
}

Future<T> tryGet<T>(
  OnGenerateValue<T> generator, {
  Backoff? backoff,
  OnStopIf<T>? stopIf,
  OnRetryIf<T>? retryIf,
  OnRegenerateIf<T>? regenerateIf,
  int maxRetries = unlimitedRetries,
}) async {
  backoff ??= _defaultBackoff();
  stopIf ??= _selectFirst;
  retryIf ??= _rethrowIfError;
  regenerateIf ??= _noRegenerate;

  while (true) {
    BackoffDelay current = backoff.nextDelay();
    await Future.delayed(current.duration);
    bool maxRetriesExceeded =
        (maxRetries >= 0 && current.retryCount >= maxRetries);

    dynamic error;
    bool generated = false;

    try {
      T currentResult = await generator();
      generated = true;

      bool stopping = await stopIf(
        currentResult,
        current,
      );

      if (stopping) {
        return currentResult;
      }

      bool regenerating = await regenerateIf(
        currentResult,
        current,
      );

      if (!regenerating) {
        throw Exception("Could not fetch a suitable value.");
      }
    } catch (e) {
      if (!generated) {
        rethrow;
      }

      bool retrying = await error(
        error,
        current,
      );

      if (!retrying) {
        rethrow;
      }

      error = e;
    }

    if (maxRetriesExceeded) {
      throw Exception("Maximum number of tries reached or exceeded.");
    }
  }
}

Future<void> waitForCondition(
  OnGenerateValue<bool> condition, {
  Backoff? backoff,
  OnRetryIf<bool>? retryIf,
  OnRegenerateIf<bool>? regenerateIf,
  int maxRetries = unlimitedRetries,
}) async {
  await tryGet(
    condition,
    backoff: backoff,
    stopIf: (bool result, _) => result,
    retryIf: retryIf,
    regenerateIf: regenerateIf,
    maxRetries: maxRetries,
  );
}

void main() {
  Backoff b = backoff(
    initialDuration: Duration(seconds: 1),
    delay: incrementalDelay(exponential: true),
    jitter: noJitter,
    immediate: true,
  );
  for (int i = 0; i < 8; ++i) {
    BackoffDelay delay = b.nextDelay();
    print([ delay.retryCount, delay.duration ]);
  }
}