// Copyright (c) 2022, the Dart project authors.  Please see the AUTHORS file
// for details. 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:math';

import 'package:dart2wasm/translator.dart';

import 'package:kernel/ast.dart';

import 'package:wasm_builder/wasm_builder.dart' as w;

/// Wasm struct field indices for fields that are accessed explicitly from Wasm
/// code, e.g. in intrinsics.
///
/// The values are validated by asserts, typically either through
/// [ClassInfo._addField] (for manually added fields) or by a line in
/// [FieldIndex.validate] (for fields declared in Dart code).
class FieldIndex {
  static const asyncSuspendStateResume = 2;
  static const asyncSuspendStateContext = 3;
  static const asyncSuspendStateTargetIndex = 4;
  static const asyncSuspendStateCompleter = 5;
  static const asyncSuspendStateCurrentException = 6;
  static const asyncSuspendStateCurrentExceptionStackTrace = 7;
  static const asyncSuspendStateCurrentReturnValue = 8;

  static const classId = 0;
  static const boxValue = 1;
  static const identityHash = 1;
  static const objectFieldBase = 2;
  static const stringArray = 2;
  static const listLength = 3;
  static const listArray = 4;
  static const hashBaseIndex = 2;
  static const hashBaseData = 4;
  static const closureContext = 2;
  static const closureVtable = 3;
  static const closureRuntimeType = 4;
  static const vtableDynamicCallEntry = 0;
  static const vtableInstantiationTypeComparisonFunction = 1;
  static const vtableInstantiationFunction = 2;
  static const instantiationContextInner = 0;
  static const instantiationContextTypeArgumentsBase = 1;
  static const typeIsDeclaredNullable = 2;
  static const interfaceTypeTypeArguments = 4;
  static const functionTypeNamedParameters = 9;
  static const recordTypeNames = 3;
  static const recordTypeFieldTypes = 4;
  static const suspendStateIterator = 4;
  static const suspendStateContext = 5;
  static const suspendStateTargetIndex = 6;
  static const syncStarIteratorCurrent = 3;
  static const syncStarIteratorYieldStarIterable = 4;
  static const recordFieldBase = 2;
  static const jsStringImplRef = 2;

  static void validate(Translator translator) {
    void check(Class cls, String name, int expectedIndex) {
      assert(
          translator.fieldIndex[
                  cls.fields.firstWhere((f) => f.name.text == name)] ==
              expectedIndex,
          "Unexpected field index for ${cls.name}.$name");
    }

    check(translator.asyncSuspendStateClass, "_resume",
        FieldIndex.asyncSuspendStateResume);
    check(translator.asyncSuspendStateClass, "_context",
        FieldIndex.asyncSuspendStateContext);
    check(translator.asyncSuspendStateClass, "_targetIndex",
        FieldIndex.asyncSuspendStateTargetIndex);
    check(translator.asyncSuspendStateClass, "_completer",
        FieldIndex.asyncSuspendStateCompleter);
    check(translator.asyncSuspendStateClass, "_currentException",
        FieldIndex.asyncSuspendStateCurrentException);
    check(translator.asyncSuspendStateClass, "_currentExceptionStackTrace",
        FieldIndex.asyncSuspendStateCurrentExceptionStackTrace);
    check(translator.asyncSuspendStateClass, "_currentReturnValue",
        FieldIndex.asyncSuspendStateCurrentReturnValue);

    check(translator.boxedBoolClass, "value", FieldIndex.boxValue);
    check(translator.boxedIntClass, "value", FieldIndex.boxValue);
    check(translator.boxedDoubleClass, "value", FieldIndex.boxValue);
    if (!translator.options.jsCompatibility) {
      check(translator.oneByteStringClass, "_array", FieldIndex.stringArray);
      check(translator.twoByteStringClass, "_array", FieldIndex.stringArray);
    }
    check(translator.listBaseClass, "_length", FieldIndex.listLength);
    check(translator.listBaseClass, "_data", FieldIndex.listArray);
    check(translator.hashFieldBaseClass, "_indexNullable",
        FieldIndex.hashBaseIndex);
    check(translator.hashFieldBaseClass, "_data", FieldIndex.hashBaseData);
    check(translator.closureClass, "context", FieldIndex.closureContext);
    check(translator.typeClass, "isDeclaredNullable",
        FieldIndex.typeIsDeclaredNullable);
    check(translator.interfaceTypeClass, "typeArguments",
        FieldIndex.interfaceTypeTypeArguments);
    check(translator.functionTypeClass, "namedParameters",
        FieldIndex.functionTypeNamedParameters);
    check(translator.recordTypeClass, "names", FieldIndex.recordTypeNames);
    check(translator.recordTypeClass, "fieldTypes",
        FieldIndex.recordTypeFieldTypes);
    check(translator.suspendStateClass, "_iterator",
        FieldIndex.suspendStateIterator);
    check(translator.suspendStateClass, "_context",
        FieldIndex.suspendStateContext);
    check(translator.suspendStateClass, "_targetIndex",
        FieldIndex.suspendStateTargetIndex);
    check(translator.syncStarIteratorClass, "_current",
        FieldIndex.syncStarIteratorCurrent);
    check(translator.syncStarIteratorClass, "_yieldStarIterable",
        FieldIndex.syncStarIteratorYieldStarIterable);
  }
}

/// Initial value for the hash code field of objects. This value is recognized
/// by `Object._objectHashCode` wich updates the field first time it's read.
const int initialIdentityHash = 0;

/// Information about the Wasm representation for a class.
class ClassInfo {
  /// The Dart class that this info corresponds to. The top type does not have
  /// an associated Dart class.
  final Class? cls;

  /// The Class ID of this class, stored in every instance of the class.
  final int classId;

  /// Depth of this class in the Wasm type hierarchy.
  final int depth;

  /// The Wasm struct used to represent instances of this class. A class will
  /// sometimes use the same struct as its superclass.
  final w.StructType struct;

  /// The superclass for this class. This will usually be the Dart superclass,
  /// but there are a few exceptions, where the Wasm type hierarchy does not
  /// follow the Dart class hierarchy.
  final ClassInfo? superInfo;

  /// The class that this class masquerades as via `runtimeType`, if any.
  ClassInfo? masquerade = null;

  /// For every type parameter which is directly mapped to a type parameter in
  /// the superclass, this contains the corresponding superclass type
  /// parameter. These will reuse the corresponding type parameter field of
  /// the superclass.
  final Map<TypeParameter, TypeParameter> typeParameterMatch;

  /// The class whose struct is used as the type for variables of this type.
  /// This is a type which is a superclass of all subtypes of this type.
  late final ClassInfo repr = upperBound(
      implementedBy.map((c) => identical(c, this) ? this : c.repr).toSet());

  /// All classes which implement this class. This is used to compute `repr`.
  final List<ClassInfo> implementedBy = [];

  /// Nullabe Wasm ref type for this class.
  final w.RefType nullableType;

  /// Non-nullable Wasm ref type for this class.
  final w.RefType nonNullableType;

  /// Get Wasm ref type for this class with given nullability.
  w.RefType typeWithNullability(bool nullable) =>
      nullable ? nullableType : nonNullableType;

  ClassInfo(this.cls, this.classId, this.depth, this.struct, this.superInfo,
      {this.typeParameterMatch = const {}})
      : nullableType = w.RefType.def(struct, nullable: true),
        nonNullableType = w.RefType.def(struct, nullable: false) {
    implementedBy.add(this);
  }

  void _addField(w.FieldType fieldType, [int? expectedIndex]) {
    assert(expectedIndex == null || expectedIndex == struct.fields.length);
    struct.fields.add(fieldType);
  }

  // This returns the types of all the class's fields (including
  // superclass fields), except for the class id and the identity hash
  List<w.ValueType> getClassFieldTypes() => [
        for (var fieldType in struct.fields.skip(FieldIndex.objectFieldBase))
          fieldType.type.unpacked
      ];
}

ClassInfo upperBound(Set<ClassInfo> classes) {
  while (classes.length > 1) {
    Set<ClassInfo> newClasses = {};
    int minDepth = 999999999;
    int maxDepth = 0;
    for (ClassInfo info in classes) {
      minDepth = min(minDepth, info.depth);
      maxDepth = max(maxDepth, info.depth);
    }
    int targetDepth = minDepth == maxDepth ? minDepth - 1 : minDepth;
    for (ClassInfo info in classes) {
      while (info.depth > targetDepth) {
        info = info.superInfo!;
      }
      newClasses.add(info);
    }
    classes = newClasses;
  }
  return classes.single;
}

/// Constructs the Wasm type hierarchy.
class ClassInfoCollector {
  final Translator translator;
  late final ClassInfo topInfo;

  /// Maps number of record fields to the struct type to be used for a record
  /// shape class with that many fields.
  final Map<int, w.StructType> _recordStructs = {};

  /// Any subtype of these needs to masqueraded (modulo special js-compatibility
  /// mode semantics) or specially treated due to being from a different type
  /// (e.g. record, closure)
  late final Set<Class> masqueraded = _computeMasquerades();

  Set<Class> _computeMasquerades() {
    final values = {
      translator.coreTypes.boolClass,
      translator.coreTypes.intClass,
      translator.coreTypes.doubleClass,
      translator.coreTypes.stringClass,
      translator.coreTypes.functionClass,
      translator.coreTypes.recordClass,
      translator.index.getClass("dart:core", "_Type"),
      translator.index.getClass("dart:core", "_ListBase"),
    };
    for (final name in const <String>[
      "ByteBuffer",
      "ByteData",
      "Int8List",
      "Uint8List",
      "Uint8ClampedList",
      "Int16List",
      "Uint16List",
      "Int32List",
      "Uint32List",
      "Int64List",
      "Uint64List",
      "Float32List",
      "Float64List",
      "Int32x4List",
      "Float32x4List",
      "Float64x2List",
    ]) {
      final Class? cls = translator.index.tryGetClass("dart:typed_data", name);
      if (cls != null) values.add(cls);
    }
    return values;
  }

  /// Wasm field type for fields with type [_Type]. Fields of this type are
  /// added to classes for type parameters.
  ///
  /// This field is initialized when a class with a type parameter is first
  /// encountered. Initialization depends on [Translator] visiting the [_Type]
  /// class first and creating a [ClassInfo] for it.
  late final w.FieldType typeType = w.FieldType(
      translator.classInfo[translator.typeClass]!.nonNullableType,
      mutable: false);

  ClassInfoCollector(this.translator);

  w.ModuleBuilder get m => translator.m;

  TranslatorOptions get options => translator.options;

  void _createStructForClassTop(int classCount) {
    final w.StructType struct = m.types.defineStruct("#Top");
    topInfo = ClassInfo(null, 0, 0, struct, null);
    translator.classForHeapType[struct] = topInfo;
  }

  void _createStructForClass(Map<Class, int> classIds, Class cls) {
    ClassInfo? info = translator.classInfo[cls];
    if (info != null) return;

    final classId = classIds[cls]!;
    Class? superclass = cls.superclass;
    if (superclass == null) {
      ClassInfo superInfo = topInfo;
      final w.StructType struct =
          m.types.defineStruct(cls.name, superType: superInfo.struct);
      info = ClassInfo(cls, classId, superInfo.depth + 1, struct, superInfo);
      // Mark Top type as implementing Object to force the representation
      // type of Object to be Top.
      info.implementedBy.add(topInfo);
    } else {
      // Recursively initialize all supertypes before initializing this class.
      _createStructForClass(classIds, superclass);
      for (Supertype interface in cls.implementedTypes) {
        _createStructForClass(classIds, interface.classNode);
      }

      // In the Wasm type hierarchy, Object, bool and num sit directly below
      // the Top type. The implementation classes WasmStringBase and _Type sit
      // directly below the public classes they implement.
      // All other classes sit below their superclass.
      ClassInfo superInfo = cls == translator.coreTypes.boolClass ||
              cls == translator.coreTypes.numClass
          ? topInfo
          : (!translator.options.jsCompatibility &&
                      cls == translator.wasmStringBaseClass) ||
                  cls == translator.typeClass
              ? translator.classInfo[cls.implementedTypes.single.classNode]!
              : translator.classInfo[superclass]!;

      // Figure out which type parameters can reuse a type parameter field of
      // the superclass.
      Map<TypeParameter, TypeParameter> typeParameterMatch = {};
      if (cls.typeParameters.isNotEmpty) {
        Supertype supertype = cls.superclass == superInfo.cls
            ? cls.supertype!
            : cls.implementedTypes.single;
        for (TypeParameter parameter in cls.typeParameters) {
          for (int i = 0; i < supertype.typeArguments.length; i++) {
            DartType arg = supertype.typeArguments[i];
            if (arg is TypeParameterType && arg.parameter == parameter) {
              typeParameterMatch[parameter] = superInfo.cls!.typeParameters[i];
              break;
            }
          }
        }
      }

      w.StructType struct =
          m.types.defineStruct(cls.name, superType: superInfo.struct);
      info = ClassInfo(cls, classId, superInfo.depth + 1, struct, superInfo,
          typeParameterMatch: typeParameterMatch);

      // Mark all interfaces as being implemented by this class. This is
      // needed to calculate representation types.
      for (Supertype interface in cls.implementedTypes) {
        ClassInfo? interfaceInfo = translator.classInfo[interface.classNode];
        while (interfaceInfo != null) {
          interfaceInfo.implementedBy.add(info);
          interfaceInfo = interfaceInfo.superInfo;
        }
      }
    }
    translator.classesSupersFirst.add(info);
    translator.classes[classId] = info;
    translator.classInfo[cls] = info;
    translator.classForHeapType.putIfAbsent(info.struct, () => info!);
  }

  void _createStructForRecordClass(Map<Class, int> classIds, Class cls) {
    final numFields = cls.fields.length;

    final struct = _recordStructs.putIfAbsent(
        numFields,
        () => m.types.defineStruct(
              'Record$numFields',
              superType: translator.recordInfo.struct,
            ));

    final ClassInfo superInfo = translator.recordInfo;

    final classId = classIds[cls]!;
    final info =
        ClassInfo(cls, classId, superInfo.depth + 1, struct, superInfo);

    translator.classesSupersFirst.add(info);
    translator.classes[classId] = info;
    translator.classInfo[cls] = info;
    translator.classForHeapType.putIfAbsent(info.struct, () => info);
  }

  void _generateFields(ClassInfo info) {
    ClassInfo? superInfo = info.superInfo;
    if (superInfo == null) {
      // Top - add class id field
      info._addField(
          w.FieldType(w.NumType.i32, mutable: false), FieldIndex.classId);
    } else {
      // Copy fields from superclass
      for (w.FieldType fieldType in superInfo.struct.fields) {
        info._addField(fieldType);
      }
      if (info.cls!.superclass == null) {
        // Object - add identity hash code field
        info._addField(w.FieldType(w.NumType.i32), FieldIndex.identityHash);
      }
      // Add fields for type variables
      for (TypeParameter parameter in info.cls!.typeParameters) {
        TypeParameter? match = info.typeParameterMatch[parameter];
        if (match != null) {
          // Reuse supertype type variable
          translator.typeParameterIndex[parameter] =
              translator.typeParameterIndex[match]!;
        } else {
          translator.typeParameterIndex[parameter] = info.struct.fields.length;
          info._addField(typeType);
        }
      }
      // Add fields for Dart instance fields
      for (Field field in info.cls!.fields) {
        if (field.isInstanceMember) {
          w.ValueType wasmType = translator.translateType(field.type);
          translator.fieldIndex[field] = info.struct.fields.length;
          info._addField(w.FieldType(wasmType, mutable: !field.isFinal));
        }
      }
    }
  }

  void _generateRecordFields(ClassInfo info) {
    final struct = info.struct;
    final ClassInfo superInfo = info.superInfo!;
    assert(identical(superInfo, translator.recordInfo));

    // Different record classes can share the same struct, check if the struct
    // is already initialized
    if (struct.fields.isEmpty) {
      // Copy fields from superclass
      for (w.FieldType fieldType in superInfo.struct.fields) {
        info._addField(fieldType);
      }

      for (Field _ in info.cls!.fields) {
        info._addField(w.FieldType(topInfo.nullableType));
      }
    }

    int fieldIdx = superInfo.struct.fields.length;
    for (Field field in info.cls!.fields) {
      translator.fieldIndex[field] = fieldIdx++;
    }
  }

  /// Create class info and Wasm struct for all classes.
  void collect() {
    // `0` is occupied by artificial non-Dart top class.
    const int firstClassId = 1;

    translator.classIdNumbering =
        ClassIdNumbering._number(translator, masqueraded, firstClassId);
    final classIds = translator.classIdNumbering.classIds;
    final dfsOrder = translator.classIdNumbering.dfsOrder;

    _createStructForClassTop(dfsOrder.length);

    // Class infos by class-id, will be populated by the calls to
    // [_createStructForClass] and [_createStructForRecordClass] below.
    translator.classes = List<ClassInfo>.filled(1 + dfsOrder.length, topInfo);

    // Class infos in different order: Infos of super class and super interfaces
    // before own info.
    translator.classesSupersFirst = [topInfo];

    // Subclasses of the `_Closure` class are generated on the fly as fields
    // with function types are encountered. Therefore, `_Closure` class must
    // be early in the initialization order.
    _createStructForClass(classIds, translator.closureClass);

    // Similarly `_Type` is needed for type parameter fields in classes and
    // needs to be initialized before we encounter a class with type
    // parameters.
    _createStructForClass(classIds, translator.typeClass);

    // Similarly the `Record` class needs to be handled before the loop below as
    // the [_createStructForRecordClass] needs it.
    _createStructForClass(classIds, translator.coreTypes.recordClass);

    for (final cls in dfsOrder) {
      if (cls.superclass == translator.coreTypes.recordClass) {
        _createStructForRecordClass(classIds, cls);
      } else {
        _createStructForClass(classIds, cls);
      }
    }

    // Now that the representation types for all classes have been computed,
    // fill in the types of the fields in the generated Wasm structs.
    for (final info in translator.classesSupersFirst) {
      if (info.superInfo == translator.recordInfo) {
        _generateRecordFields(info);
      } else {
        _generateFields(info);
      }
    }

    // Validate that all internally used fields have the expected indices.
    FieldIndex.validate(translator);
  }
}

class ClassIdNumbering {
  final Map<Class, List<Class>> _subclasses;
  final Map<Class, List<Class>> _implementors;
  final List<Range> _concreteSubclassIdRanges;
  final Set<Class> _masqueraded;

  final List<Class> dfsOrder;
  final Map<Class, int> classIds;

  ClassIdNumbering._(
      this._subclasses,
      this._implementors,
      this._concreteSubclassIdRanges,
      this._masqueraded,
      this.dfsOrder,
      this.classIds);

  final Map<Class, Set<Class>> _transitiveImplementors = {};
  Set<Class> _getTransitiveImplementors(Class klass) {
    var transitiveImplementors = _transitiveImplementors[klass];
    if (transitiveImplementors != null) return transitiveImplementors;

    transitiveImplementors = {};

    List<Class>? classes = _subclasses[klass];
    if (classes != null) {
      for (final cls in classes) {
        transitiveImplementors.addAll(_getTransitiveImplementors(cls));
      }
    }
    classes = _implementors[klass];
    if (classes != null) {
      for (final cls in classes) {
        transitiveImplementors.add(cls);
        transitiveImplementors.addAll(_getTransitiveImplementors(cls));
      }
    }

    return _transitiveImplementors[klass] = transitiveImplementors;
  }

  // Maps a class to a list of class id ranges that implement/extend the given
  // class directly or transitively.
  final Map<Class, List<Range>> _concreteClassIdRanges = {};
  List<Range> getConcreteClassIdRanges(Class klass) {
    var ranges = _concreteClassIdRanges[klass];
    if (ranges != null) return ranges;

    ranges = [];
    final transitiveImplementors = _getTransitiveImplementors(klass);
    final range = _concreteSubclassIdRanges[classIds[klass]!];
    if (!range.isEmpty) ranges.add(range);
    for (final implementor in transitiveImplementors) {
      final range = _concreteSubclassIdRanges[classIds[implementor]!];
      if (!range.isEmpty) ranges.add(range);
    }
    ranges.normalize();

    return _concreteClassIdRanges[klass] = ranges;
  }

  late final int firstNonMasqueradedInterfaceClassCid = (() {
    int lastMasqueradedClassId = 0;
    for (final cls in _masqueraded) {
      final ranges = getConcreteClassIdRanges(cls);
      if (ranges.isNotEmpty) {
        lastMasqueradedClassId = max(lastMasqueradedClassId, ranges.last.end);
      }
    }
    return lastMasqueradedClassId + 1;
  })();

  static ClassIdNumbering _number(
      Translator translator, Set<Class> masqueraded, int firstClassId) {
    // Make graph from class to its subclasses.
    late final Class root;
    final subclasses = <Class, List<Class>>{};
    final implementors = <Class, List<Class>>{};
    int abstractClassCount = 0;
    int concreteClassCount = 0;
    for (final library in translator.component.libraries) {
      for (final cls in library.classes) {
        cls.isAbstract ? abstractClassCount++ : concreteClassCount++;
        final superClass = cls.superclass;
        if (superClass == null) {
          root = cls;
        } else {
          subclasses.putIfAbsent(superClass, () => []).add(cls);
        }
        for (final interface in cls.implementedTypes) {
          implementors.putIfAbsent(interface.classNode, () => []).add(cls);
        }
      }
    }
    final int classCount = abstractClassCount + concreteClassCount;

    // We have a preference in which order we explore the direct subclasses of
    // `Object` as that allows us to keep class ids of certain hierarchies
    // low.
    // TODO: If we had statistics (e.g. number of class allocations, number of
    // times class is mentioned in type, ...) we'd have an estimate of how often
    // we have to encode a class-id. Then we could reorder the subclasses
    // depending on usage count of the subclass trees.
    final fixedOrder = <Class, int>{
      translator.coreTypes.boolClass: -10,
      translator.coreTypes.numClass: -9,
      if (!translator.options.jsCompatibility)
        translator.wasmStringBaseClass: -8,
      translator.jsStringClass: -7,
      translator.typeClass: -6,
      translator.listBaseClass: -5,
      translator.hashFieldBaseClass: -4,
    };
    int order(Class klass) {
      final order = fixedOrder[klass];
      if (order != null) return order;

      final importUri = klass.enclosingLibrary.importUri.toString();
      if (importUri.startsWith('dart:')) {
        if (masqueraded.contains(klass)) return -1;
        // Bundle the typed data and collection together, they may not have
        // common base class except for `Object` but most of them have similar
        // selectors.
        if (importUri.startsWith('dart:typed_data')) return 0;
        if (importUri.startsWith('dart:collection')) return 1;
        if (importUri.startsWith('dart:core')) return 2;

        // The dart:wasm classes are marked as entrypoints, therefore retained by
        // TFA but they can never be instantiated, as they represent raw wasm
        // types that aren't part of the dart object hierarchy.
        // Move them to the very end of the class table.
        if (klass.name.startsWith('_WasmBase')) return 0xffffff;
        return 3;
      }
      return 10;
    }

    subclasses[root]!.sort((Class a, Class b) => order(a).compareTo(order(b)));

    // Traverse class inheritence graph in depth-first pre-order.
    void dfs(
        Class root, int Function(Class) pre, void Function(Class, int) post) {
      final classId = pre(root);
      final children = subclasses[root];
      if (children != null) {
        for (final sub in children) {
          dfs(sub, pre, post);
        }
      }
      post(root, classId);
    }

    // Make a list of the depth-first pre-order traversal.
    final dfsOrder = <Class>[];
    final classIds = <Class, int>{};

    // Maps any class to a dense range of concrete class ids that are subclasses
    // of that class.
    final concreteSubclassRanges = List<Range>.filled(
        firstClassId + classCount, Range.empty(),
        growable: false);

    int nextConcreteClassId = firstClassId;
    int nextAbstractClassId = firstClassId + concreteClassCount;
    dfs(root, (Class cls) {
      dfsOrder.add(cls);
      if (cls.isAbstract) {
        var classId = classIds[cls];
        if (classId == null) classIds[cls] = nextAbstractClassId++;
        return nextConcreteClassId;
      }

      assert(classIds[cls] == null);
      classIds[cls] = nextConcreteClassId++;
      return nextConcreteClassId - 1;
    }, (Class cls, int firstClassId) {
      final range = Range(firstClassId, nextConcreteClassId - 1);
      if (!cls.isAbstract) {
        assert(classIds[cls] == firstClassId);
        concreteSubclassRanges[firstClassId] = range;
      } else {
        concreteSubclassRanges[classIds[cls]!] = range;
      }
    });

    return ClassIdNumbering._(subclasses, implementors, concreteSubclassRanges,
        masqueraded, dfsOrder, classIds);
  }
}

// A range of class ids, both ends inclusive.
class Range {
  final int start;
  final int end;

  Range._(this.start, this.end) : assert(start <= end);
  const Range.empty()
      : start = 0,
        end = -1;
  factory Range(int start, int end) {
    if (end < start) return Range.empty();
    return Range._(start, end);
  }

  int get length => 1 + (end - start);
  bool get isEmpty => length == 0;

  bool contains(int id) => start <= id && id <= end;
  bool containsRange(Range other) => start <= other.start && other.end <= end;

  Range shiftBy(int offset) {
    if (isEmpty) return this;
    return Range(start + offset, end + offset);
  }

  String toString() => isEmpty ? '[]' : '[$start, $end]';
}

extension RangeListExtention on List<Range> {
  void normalize() {
    if (isEmpty) return;

    // Ensure we sort ranges by start of the range.
    sort((a, b) => a.start.compareTo(b.start));

    int current = 0;
    Range currentRange = this[0];
    for (int read = 1; read < length; ++read) {
      final nextRange = this[read];
      if (currentRange.isEmpty) {
        currentRange = nextRange;
        continue;
      }
      if (nextRange.isEmpty) continue;
      if (currentRange.containsRange(nextRange)) continue;
      if (currentRange.contains(nextRange.start)) {
        currentRange = Range(currentRange.start, nextRange.end);
        continue;
      }

      this[current++] = currentRange;
      currentRange = nextRange;
    }
    this[current++] = currentRange;
    this.length = current;
  }
}