public/dart/sledge/lib/src/document/values/ordered_list_value.dart

// Copyright 2018 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

import 'dart:async';
import 'dart:collection';
import 'dart:typed_data';

import '../change.dart';
import '../leaf_value.dart';
import '../value_observer.dart';
import 'converted_change.dart';
import 'converter.dart';
import 'key_value_storage.dart';
import 'ordered_list_tree_path.dart';

/// Implementation of Ordered List CRDT.
///
/// The ordered List CRDT can be changed concurrently by multiple instances, each
/// associated with an instance ID. Changes from other instances are applied when
/// calling [applyChange], while changes from this instance can be retrieved by
/// calling [getChange].
//
// The contents of the list are stored using a KeyValueStorage. The values of
// the KeyValueStorage are the elements of the list, while the keys are created
// in such a way that their lexicographic order corresponds to the order of the
// elements of the list.
//
//  Key generation is based on an implicit tree structure, where edges are
//  directed from parent nodes towards child nodes. For each edge (v, u) there
//  is an associated bytelist f(v, u). For each node v there is an associated
//  bytelist F(v), which is the concatenation of bytelists associated with the
//  edges on path from root to v.
//
//  Example:
//
//    root -----> a -----> b -----> v
//                |
//                -------> u
//
//    F(v) = f(root, a) f(a, b) f(b, v)
//    F(u) = f(root, a) f(a, u)
//
//  The tree has nodes of two types:
//    Value nodes, for which:
//      f(p, v) = {1}{timestamp}
//
//    Implicit nodes, for which:
//      f(p, v) = {0|2}{instanceId}
//    The prefix of f(p, v) is 0 if (v) is a left child of (p) or 2 if it is a
//    right child.
//
//  Value nodes correspond to leaves, while implicit nodes are the internal
//  ones. There is a one-to-one correspondence between the elements of the list
//  and the set of value nodes. Every value node has an implicit node as a
//  parent that is created on the same instance as that value node.
//
//  Every implicit node has exactly one value child node. It might also have one
//  left and one right (implicit) nodes per instance.
//
//  Insertion:
//    In the most common case, a new element is inserted between two existing
//    ones. Let (v) be the new value node, and (left) and (right) be the nodes
//    of the previous and next elements correspondingly. Also, let (pleft) and
//    (pright) be their corresponding parents, both of them being, by
//    definition, implicit nodes.
//
//    If (pleft) is not an ancestor of (pright), then we add a new implicit node
//    (par_v) as a right child of (pleft) and (v) as the value node of (par_v):
//
//        root -----> pleft -----> left
//             |            |
//             |            - - -> par(v) - - -> v
//             |
//             -----> pright ----> right
//
//      We have now defined:
//
//        F(v) = F(pleft){2}{instanceId}{1}{timestamp}
//
//      The invariant of the keys being ordered in lexicographic order is maintained as:
//        1. F(left) = F(pleft){1}{timestamp}. So F(left) < F(v).
//        2. F(right) > F(pleft), and F(pleft) is not a prefix of F(right).
//          So F(right) > F(v).
//
//    Otherwise, i.e. when (pleft) is an ancestor of (pright), we insert a new
//    implicit node (par_v) as the left child of (pleft) and (v) as the value of
//    that node:
//
//        root -----> pleft -----> left
//                          |
//                          |             - - -> par(v) - - -> v
//                          |             |
//                          ------> pright ----> right
//
//      We have now defined:
//
//        F(v) = F(pright){0}{instanceId}{1}{timestamp}
//
//      The invariant of the lexicographic order of the keys is still maintained since:
//        1. F(right) = F(pright){1}{timestamp}. So F(right) > F(v).
//        2. F(left) < F(right), and F(left) can't start with F(pright),
//          so F(left) < F(pright) < F(v).
//
//
//  instanceId:
//    instanceIds are introduced to handle concurrent insertions on different
//    instances. Last instanceId in the path to the node should correspond to
//    the instance that created that node.
//
//  timestamp:
//    timestamps are introduced to avoid tombstones. If some key is deleted,
//    then it should never be inserted again. In other case conflict might
//    happen. The same key may be inserted only on the same instance, so
//    incremental timer per instance is applicable.
//
// TODO:
// Now each implicit node have only one value child. It should be changed. And
// at the same time value nodes should get able to have implicit node as a
// child. And left/right edges should have no id written on them.
//
// TODO: handle null values in CRDT methods.

// ignore: private_collision_in_mixin_application
class OrderedListValue<E> extends ListBase<E> implements LeafValue {
  //with ListMixin<E> {
  final KeyValueStorage<OrderedListTreePath, E> _storage;
  final Uint8List _instanceId;
  int _incrementalTime = 0;
  final OrderedListTreePath _root = OrderedListTreePath.root();
  final StreamController<OrderedListChange<E>> _changeController =
      StreamController<OrderedListChange<E>>.broadcast();
  final MapToKVListConverter _converter;
  final bool Function(E, E) _equals;

  /// Default constructor.
  OrderedListValue(this._instanceId, {bool equals(E element1, E element2)})
      : _converter = MapToKVListConverter<OrderedListTreePath, E>(
            keyConverter: orderedListTreePathConverter),
        _storage = KeyValueStorage<OrderedListTreePath, E>(),
        _equals = equals ?? ((E element1, E element2) => element1 == element2);

  @override
  Stream<OrderedListChange<E>> get onChange => _changeController.stream;

  @override
  void insert(int index, E element) {
    final sortedKeys = _sortedKeysList();
    if (index < 0 || index > sortedKeys.length) {
      throw RangeError.value(index, 'index', 'Index is out of range.');
    }

    OrderedListTreePath newKey;
    if (sortedKeys.isEmpty) {
      newKey = _root.getChild(ChildType.value, _instanceId, _timestamp);
    } else {
      bool becomeRightChild = (index != 0 &&
          (index == sortedKeys.length ||
              !sortedKeys[index].isDescendant(sortedKeys[index - 1])));

      if (becomeRightChild) {
        newKey = sortedKeys[index - 1]
            .getChild(ChildType.right, _instanceId, _timestamp);
      } else {
        newKey =
            sortedKeys[index].getChild(ChildType.left, _instanceId, _timestamp);
      }
    }
    _storage[newKey] = element;
  }

  @override
  void insertAll(int index, Iterable<E> iterable) {
    if (index < 0 || index > length) {
      throw RangeError.value(index, 'index', 'Index is out of range.');
    }
    int insertIndex = index;
    for (final element in iterable) {
      insert(insertIndex++, element);
    }
  }

  @override
  int indexOf(Object element, [int start = 0]) {
    final values = _valuesList();
    for (int i = start; i < values.length; i++) {
      if (_equals(values[i], element)) {
        return i;
      }
    }
    return -1;
  }

  @override
  int lastIndexOf(Object element, [int start]) {
    final values = _valuesList();
    start ??= values.length - 1;
    for (int i = start; i >= 0; i--) {
      if (_equals(values[i], element)) {
        return i;
      }
    }
    return -1;
  }

  @override
  E removeAt(int index) {
    return _storage.remove(_sortedKeysList()[index]);
  }

  @override
  bool remove(Object element) {
    final keys = _sortedKeysList();
    final values = _valuesList();
    for (int i = 0; i < values.length; i++) {
      if (_equals(values[i], element)) {
        _storage.remove(keys[i]);
        return true;
      }
    }
    return false;
  }

  @override
  E removeLast() => removeAt(length - 1);

  @override
  void removeRange(int start, int end) {
    _sortedKeysList().getRange(start, end).forEach(_storage.remove);
  }

  @override
  void removeWhere(bool test(E element)) {
    final keys = _sortedKeysList();
    final values = _valuesList();
    for (int i = 0; i < values.length; i++) {
      if (test(values[i])) {
        _storage.remove(keys[i]);
      }
    }
  }

  @override
  void replaceRange(int start, int end, Iterable<E> replacement) {
    removeRange(start, end);
    insertAll(start, replacement);
  }

  @override
  void retainWhere(bool test(E element)) {
    removeWhere((element) => !test(element));
  }

  @override
  E operator [](int index) {
    return _valuesList()[index];
  }

  @override
  void operator []=(int index, E element) {
    removeAt(index);
    insert(index, element);
  }

  @override
  int get length => _storage.length;

  @override
  set length(int newLength) {
    // This list is not fixed length.
    // However, it does not support the length setter because [null] cannot be stored.
    throw UnsupportedError('Length setter is not supported.');
  }

  @override
  void add(E element) {
    insert(length, element);
  }

  @override
  void addAll(Iterable<E> iterable) {
    iterable.forEach(add);
  }

  @override
  void clear() {
    _storage.clear();
  }

  @override
  bool contains(Object element) {
    return indexOf(element) != -1;
  }

  List<OrderedListTreePath> _sortedKeysList() {
    return _storage.keys.toList()..sort();
  }

  List<E> _valuesList() {
    return _sortedKeysList().map((key) => _storage[key]).toList();
  }

  @override
  Change getChange() => _converter.serialize(_storage.getChange());

  @override
  void completeTransaction() {
    _storage.completeTransaction();
  }

  @override
  void applyChange(Change input) {
    final ConvertedChange<OrderedListTreePath, E> change =
        _converter.deserialize(input);
    final keys = _sortedKeysList();
    // We are add deleted keys in case this change is done on our
    // connection. In other cases deletedKeys should be in keys.
    final startKeys = (SplayTreeSet<OrderedListTreePath>()
          ..addAll(keys)
          ..addAll(change.deletedKeys))
        .toList();

    final deletedPositions = <int>[];
    for (int i = 0; i < startKeys.length; i++) {
      if (change.deletedKeys.contains(startKeys[i])) {
        deletedPositions.add(i);
      }
    }
    _storage.applyChange(change);
    final keysFinal = _sortedKeysList();
    final insertedElements = SplayTreeMap<int, E>();
    for (int i = 0; i < keysFinal.length; i++) {
      if (change.changedEntries.containsKey(keysFinal[i])) {
        insertedElements[i] = change.changedEntries[keysFinal[i]];
      }
    }
    _changeController
        .add(OrderedListChange(deletedPositions, insertedElements));
  }

  @override
  void rollbackChange() {
    _storage.rollbackChange();
  }

  @override
  set observer(ValueObserver observer) {
    _storage.observer = observer;
  }

  Uint8List get _timestamp {
    _incrementalTime += 1;
    return Uint8List(8)..buffer.asByteData().setUint64(0, _incrementalTime);
  }
}