mergeArrays static method

PredictionContext mergeArrays(ArrayPredictionContext a, ArrayPredictionContext b, bool rootIsWildcard, Map<Pair<PredictionContext, PredictionContext>, PredictionContext>? mergeCache,)

Merge two ArrayPredictionContext instances.

Different tops, different parents.

Shared top, same parents.

Shared top, different parents.

Shared top, all shared parents.

Equal tops, merge parents and reduce top to [SingletonPredictionContext].

Implementation

static PredictionContext mergeArrays(
  ArrayPredictionContext a,
  ArrayPredictionContext b,
  bool rootIsWildcard,
  Map<Pair<PredictionContext, PredictionContext>, PredictionContext>?
      mergeCache,
) {
  if (mergeCache != null) {
    var previous = mergeCache[Pair(a, b)];
    if (previous != null) return previous;
    previous = mergeCache[Pair(b, a)];
    if (previous != null) return previous;
  }

  // merge sorted payloads a + b => M
  var i = 0; // walks a
  var j = 0; // walks b
  var k = 0; // walks target M array

  var mergedReturnStates = List<int>.filled(
    a.returnStates.length + b.returnStates.length,
    0,
  ); // TODO Will it grow?
  var mergedParents = List<PredictionContext?>.filled(
    a.returnStates.length + b.returnStates.length,
    null,
  ); // TODO Will it grow?
  // walk and merge to yield mergedParents, mergedReturnStates
  while (i < a.returnStates.length && j < b.returnStates.length) {
    final a_parent = a.parents[i];
    final b_parent = b.parents[j];
    if (a.returnStates[i] == b.returnStates[j]) {
      // same payload (stack tops are equal), must yield merged singleton
      final payload = a.returnStates[i];
      // $+$ = $
      final both$ = payload == EMPTY_RETURN_STATE &&
          a_parent == null &&
          b_parent == null;
      final ax_ax = (a_parent != null && b_parent != null) &&
          a_parent == b_parent; // ax+ax -> ax
      if (both$ || ax_ax) {
        mergedParents[k] = a_parent; // choose left
        mergedReturnStates[k] = payload;
      } else {
        // ax+ay -> a'[x,y]
        final mergedParent =
            merge(a_parent!, b_parent!, rootIsWildcard, mergeCache);
        mergedParents[k] = mergedParent;
        mergedReturnStates[k] = payload;
      }
      i++; // hop over left one as usual
      j++; // but also skip one in right side since we merge
    } else if (a.returnStates[i] < b.returnStates[j]) {
      // copy a[i] to M
      mergedParents[k] = a_parent;
      mergedReturnStates[k] = a.returnStates[i];
      i++;
    } else {
      // b > a, copy b[j] to M
      mergedParents[k] = b_parent;
      mergedReturnStates[k] = b.returnStates[j];
      j++;
    }
    k++;
  }

  // copy over any payloads remaining in either array
  if (i < a.returnStates.length) {
    for (var p = i; p < a.returnStates.length; p++) {
      mergedParents[k] = a.parents[p];
      mergedReturnStates[k] = a.returnStates[p];
      k++;
    }
  } else {
    for (var p = j; p < b.returnStates.length; p++) {
      mergedParents[k] = b.parents[p];
      mergedReturnStates[k] = b.returnStates[p];
      k++;
    }
  }

  // trim merged if we combined a few that had same stack tops
  if (k < mergedParents.length) {
    // write index < last position; trim
    if (k == 1) {
      // for just one merged element, return singleton top
      PredictionContext a_ = SingletonPredictionContext.create(
        mergedParents[0]!,
        mergedReturnStates[0],
      );
      if (mergeCache != null) mergeCache[Pair(a, b)] = a_;
      return a_;
    }

    mergedParents = List.generate(k, (n) => mergedParents[n]);
    mergedReturnStates = List.generate(k, (n) => mergedReturnStates[n]);
  }

  PredictionContext M = ArrayPredictionContext(
    mergedParents,
    mergedReturnStates,
  );

  // if we created same array as a or b, return that instead
  // TODO: track whether this is possible above during merge sort for speed
  if (M == a) {
    if (mergeCache != null) mergeCache[Pair(a, b)] = a;
    return a;
  }
  if (M == b) {
    if (mergeCache != null) mergeCache[Pair(a, b)] = b;
    return b;
  }

  combineCommonParents(mergedParents);

  if (mergeCache != null) mergeCache[Pair(a, b)] = M;
  return M;
}