// Copyright (c) 2011, 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.

part of layout;

/// Implements a grid-based layout system based on:
/// [http://dev.w3.org/csswg/css3-grid-align/]
///
/// This layout is designed to support animations and work on browsers that
/// don't support grid natively. As such, we implement it on top of absolute
/// positioning.
// TODO(jmesserly): the DOM integration still needs work:
//  - The grid assumes it is absolutely positioned in its container.
//    Because of that, the grid doesn't work right unless it has at least one
//    fractional size in each dimension. In other words, only "top down" grids
//    work at the moment, because the grid can't determine its own size.
//    The core algorithm supports computing min breadth; the issue is about how
//    to integrate it into our View layer.
//  - Unless a child element is "display: inline-block" we can't get its
//    horizontal content size.
//  - Once we set an element's size to "position: absolute", we lose the
//    ability to get its original content size. If the width or height gets
//    set to something other than the content size, we can't recover the
//    original content size.
//  - There's some rounding to ints when we want to set the positions of our
//    tracks. I don't think we necessarily need to do that.
//
// TODO(jmesserly): Some features of the spec are unimplemented:
//  - grid-flow & items that have row and column set to 'auto'.
//  - Grid writing modes (right to left languages, etc)
//  - We don't do a second calculation pass if min content size of a grid-item
//    changes due to column width.
//  - The CSS parsing is not 100% complete, see the parser TODOs.
//  - We don't implement error recovery for invalid combinations of CSS
//    properties, or invalid CSS property values. Instead we throw an error.
//
// TODO(jmesserly): high level performance optimizations we could do:
//  - Optimize for the common case of spanCount = 1
//  - Optimize for the vbox/hbox case (1 row or 1 column)
//  - Optimize for the case of no content sized tracks
//  - Optimize for the "incremental update" cases
class GridLayout extends ViewLayout {
  /// Configuration parameters defined in CSS. */
  final GridTrackList? rows;
  final GridTrackList? columns;
  final GridTemplate? template;

  /// The default sizing for new rows. */
  final TrackSizing rowSizing;

  /// The default sizing for new columns. */
  final TrackSizing columnSizing;

  /// This stores the grid's size during a layout.
  /// Used for rows/columns with % or fr units.
  int? _gridWidth, _gridHeight;

  /// During a layout, this stores all row/column size information.
  /// Because grid-items can implicitly specify their own rows/columns, we can't
  /// compute this until we know the set of items.
  late List<GridTrack> _rowTracks, _columnTracks;

  /// During a layout, tracks which dimension we're processing. */
  Dimension? _dimension;

  GridLayout(Positionable view)
      : rows = _GridTrackParser.parse(view.customStyle['grid-rows']),
        columns = _GridTrackParser.parse(view.customStyle['grid-columns']),
        template = _GridTemplateParser.parse(view.customStyle['grid-template']),
        rowSizing = _GridTrackParser.parseTrackSizing(
            view.customStyle['grid-row-sizing']),
        columnSizing = _GridTrackParser.parseTrackSizing(
            view.customStyle['grid-column-sizing']),
        super(view) {
    _rowTracks = rows?.tracks ?? [];
    _columnTracks = columns?.tracks ?? [];
  }

  @override
  int? get currentWidth => _gridWidth;
  @override
  int? get currentHeight => _gridHeight;

  @override
  void cacheExistingBrowserLayout() {
    // We don't need to do anything as we don't rely on the _cachedViewRect
    // when the grid layout is used.
  }

  // TODO(jacobr): cleanup this method so that it returns a Future
  // rather than taking a Completer as an argument.
  /// The main entry point for layout computation. */
  @override
  void measureLayout(Future<Size> size, Completer<bool>? changed) {
    _ensureAllTracks();
    size.then((value) {
      _gridWidth = value.width as int?;
      _gridHeight = value.height as int?;

      if (_rowTracks.isNotEmpty && _columnTracks.isNotEmpty) {
        _measureTracks();
        _setBoundsOfChildren();
        if (changed != null) {
          changed.complete(true);
        }
      }
    });
  }

  /// The top level measurement function.
  /// [http://dev.w3.org/csswg/css3-grid-align/#calculating-size-of-grid-tracks]
  void _measureTracks() {
    // Resolve logical width, then height. Width comes first so we can use
    // the width when determining the content-sized height.
    try {
      _dimension = Dimension.WIDTH;
      _computeUsedBreadthOfTracks(_columnTracks);
      _dimension = Dimension.HEIGHT;
      _computeUsedBreadthOfTracks(_rowTracks);
    } finally {
      _dimension = null;
    }

    // TODO(jmesserly): we're supposed to detect a min-content size change
    // due to our computed width and trigger a new layout.
    // How do we implement that?
  }

  num _getRemainingSpace(List<GridTrack> tracks) {
    num remaining = _getGridContentSize()!;
    remaining -= CollectionUtils.sum(tracks, (t) => t.usedBreadth);
    return Math.max(0, remaining);
  }

  /// This is the core Grid Track sizing algorithm. It is run for Grid columns
  /// and Grid rows. The goal of the function is to ensure:
  ///   1. That each Grid Track satisfies its minSizing
  ///   2. That each Grid Track grows from the breadth which satisfied its
  ///      minSizing to a breadth which satifies its
  ///      maxSizing, subject to RemainingSpace.
  // Note: spec does not correctly doc all the parameters to this function.
  void _computeUsedBreadthOfTracks(List<GridTrack> tracks) {
    // TODO(jmesserly): as a performance optimization we could cache this
    final items = view.childViews.map((view_) => view_.layout).toList();
    CollectionUtils.sortBy(items, (item) => _getSpanCount(item)!);

    // 1. Initialize per Grid Track variables
    for (final t in tracks) {
      // percentage or length sizing functions will return a value
      // min-content, max-content, or a fraction will be set to 0
      t.usedBreadth = t.minSizing.resolveLength(_getGridContentSize());
      t.maxBreadth = t.maxSizing.resolveLength(_getGridContentSize());
      t.updatedBreadth = 0;
    }

    // 2. Resolve content-based MinTrackSizingFunctions
    final USEDBREADTH = const _UsedBreadthAccumulator();
    final MAXBREADTH = const _MaxBreadthAccumulator();

    _distributeSpaceBySpanCount(items, ContentSizeMode.MIN, USEDBREADTH);

    _distributeSpaceBySpanCount(items, ContentSizeMode.MAX, USEDBREADTH);

    // 3. Ensure that maxBreadth is as big as usedBreadth for each track
    for (final t in tracks) {
      if (t.maxBreadth < t.usedBreadth) {
        t.maxBreadth = t.usedBreadth;
      }
    }

    // 4. Resolve content-based MaxTrackSizingFunctions
    _distributeSpaceBySpanCount(items, ContentSizeMode.MIN, MAXBREADTH);

    _distributeSpaceBySpanCount(items, ContentSizeMode.MAX, MAXBREADTH);

    // 5. Grow all Grid Tracks in GridTracks from their usedBreadth up to their
    //    maxBreadth value until RemainingSpace is exhausted.
    // Note: it's not spec'd what to pass as the accumulator, but usedBreadth
    // seems right.
    _distributeSpaceToTracks(
        tracks, _getRemainingSpace(tracks), USEDBREADTH, false);

    // Spec wording is confusing about which direction this assignment happens,
    // but this is the way that makes sense.
    for (final t in tracks) {
      t.usedBreadth = t.updatedBreadth;
    }

    // 6. Grow all Grid Tracks having a fraction as their maxSizing
    final tempBreadth = _calcNormalizedFractionBreadth(tracks);
    for (final t in tracks) {
      t.usedBreadth =
          Math.max(t.usedBreadth, tempBreadth * t.maxSizing.fractionValue);
    }

    _computeTrackPositions(tracks);
  }

  /// Final steps to finish positioning tracks. Takes the track size and uses
  /// it to get start and end positions. Also rounds the positions to integers.
  void _computeTrackPositions(List<GridTrack> tracks) {
    // Compute start positions of tracks, as well as the final position

    num position = 0;
    for (final t in tracks) {
      t.start = position;
      position += t.usedBreadth;
    }

    // Now, go through and round each position to an integer. Then
    // compute the sizes based on those integers.
    num finalPosition = position;

    for (int i = 0; i < tracks.length; i++) {
      int startEdge = tracks[i].start as int;
      int endEdge;
      if (i < tracks.length - 1) {
        endEdge = tracks[i + 1].start.round();
        tracks[i + 1].start = endEdge;
      } else {
        endEdge = finalPosition.round();
      }
      int breadth = endEdge - startEdge;

      // check that we're not off by >= 1px.
      assert((endEdge - startEdge - tracks[i].usedBreadth).abs() < 1);

      tracks[i].usedBreadth = breadth;
    }
  }

  /// This method computes a '1fr' value, referred to as the
  /// tempBreadth, for a set of Grid Tracks. The value computed
  /// will ensure that when the tempBreadth is multiplied by the
  /// fractions associated with tracks, that the UsedBreadths of tracks
  /// will increase by an amount equal to the maximum of zero and the specified
  /// freeSpace less the sum of the current UsedBreadths.
  num _calcNormalizedFractionBreadth(List<GridTrack> tracks) {
    final fractionTracks = tracks.where((t) => t.maxSizing.isFraction).toList();

    // Note: the spec has various bugs in this function, such as mismatched
    // identifiers and names that aren't defined. For the most part it's
    // possible to figure out the meaning. It's also a bit confused about
    // how to compute spaceNeededFromFractionTracks, but that should just be the
    // set to the remaining free space after usedBreadth is accounted for.

    // We use the tempBreadth field to store the normalized fraction breadth
    for (final t in fractionTracks) {
      t.tempBreadth = t.usedBreadth / t.maxSizing.fractionValue;
    }

    CollectionUtils.sortBy(fractionTracks, (t) => t.tempBreadth);

    num spaceNeededFromFractionTracks = _getRemainingSpace(tracks);
    num? currentBandFractionBreadth = 0;
    num accumulatedFractions = 0;
    for (final t in fractionTracks) {
      if (t.tempBreadth != currentBandFractionBreadth) {
        if (t.tempBreadth * accumulatedFractions >
            spaceNeededFromFractionTracks) {
          break;
        }
        currentBandFractionBreadth = t.tempBreadth;
      }
      accumulatedFractions += t.maxSizing.fractionValue;
      spaceNeededFromFractionTracks += t.usedBreadth;
    }
    return spaceNeededFromFractionTracks / accumulatedFractions;
  }

  /// Ensures that for each Grid Track in tracks, a value will be
  /// computed, updatedBreadth, that represents the Grid Track's share of
  /// freeSpace.
  void _distributeSpaceToTracks(List<GridTrack?> tracks, num? freeSpace,
      _BreadthAccumulator breadth, bool ignoreMaxBreadth) {
    // TODO(jmesserly): in some cases it would be safe to sort the passed in
    // list in place. Not always though.
    tracks = CollectionUtils.orderBy(
        tracks, (t) => t.maxBreadth - breadth.getSize(t));

    // Give each Grid Track an equal share of the space, but without exceeding
    // their maxBreadth values. Because there are different MaxBreadths
    // assigned to the different Grid Tracks, this can result in uneven growth.
    for (int i = 0; i < tracks.length; i++) {
      num share = freeSpace! / (tracks.length - i);
      share = Math.min(share, tracks[i]!.maxBreadth);
      tracks[i]!.tempBreadth = share;
      freeSpace -= share;
    }

    // If the first loop completed having grown every Grid Track to its
    // maxBreadth, and there is still freeSpace, then divide that space
    // evenly and assign it to each Grid Track without regard for its
    // maxBreadth. This phase of growth will always be even, but only occurs
    // when the ignoreMaxBreadth flag is true.
    if (freeSpace! > 0 && ignoreMaxBreadth) {
      for (int i = 0; i < tracks.length; i++) {
        final share = freeSpace! / (tracks.length - i);
        tracks[i]!.tempBreadth = tracks[i]!.tempBreadth + share;
        freeSpace -= share;
      }
    }

    // Note: the spec has us updating all grid tracks, not just the passed in
    // tracks, but I think that's a spec bug.
    for (final t in tracks) {
      t!.updatedBreadth = Math.max(t.updatedBreadth, t.tempBreadth);
    }
  }

  /// This function prioritizes the distribution of space driven by Grid Items
  /// in content-sized Grid Tracks by the Grid Item's spanCount. That is, Grid
  /// Items having a lower spanCount have an opportunity to increase the size of
  /// the Grid Tracks they cover before those with larger SpanCounts.
  ///
  /// Note: items are assumed to be already sorted in increasing span count
  void _distributeSpaceBySpanCount(List<ViewLayout> items,
      ContentSizeMode sizeMode, _BreadthAccumulator breadth) {
    items = items
        .where((item) =>
            _hasContentSizedTracks(_getTracks(item), sizeMode, breadth))
        .toList();

    var tracks = [];

    for (int i = 0; i < items.length; i++) {
      final item = items[i];

      final itemTargetSize = item.measureContent(this, _dimension, sizeMode);

      final spannedTracks = _getTracks(item);
      _distributeSpaceToTracks(spannedTracks, itemTargetSize, breadth, true);

      // Remember that we need to update the sizes on these tracks
      tracks.addAll(spannedTracks);

      // Each time we transition to a spanCount, update any modified tracks
      bool spanCountFinished = false;
      if (i + 1 == items.length) {
        spanCountFinished = true;
      } else if (_getSpanCount(item) != _getSpanCount(items[i + 1])) {
        spanCountFinished = true;
      }

      if (spanCountFinished) {
        for (final t in tracks) {
          breadth.setSize(t, Math.max(breadth.getSize(t)!, t.updatedBreadth));
        }
        tracks = [];
      }
    }
  }

  /// Returns true if we have an appropriate content sized dimension, and don't
  /// cross a fractional track.
  static bool _hasContentSizedTracks(Iterable<GridTrack?> tracks,
      ContentSizeMode sizeMode, _BreadthAccumulator breadth) {
    for (final t in tracks) {
      final fn = breadth.getSizingFunction(t);
      if (sizeMode == ContentSizeMode.MAX && fn.isMaxContentSized ||
          sizeMode == ContentSizeMode.MIN && fn.isContentSized) {
        // Make sure we don't cross a fractional track
        return tracks.length == 1 || !tracks.any((t_) => t_!.isFractional);
      }
    }
    return false;
  }

  /// Ensures that the numbered track exists. */
  void _ensureTrack(
      List<GridTrack> tracks, TrackSizing sizing, int start, int span) {
    // Start is 1-based. Make it 0-based.
    start -= 1;

    // Grow the list if needed
    int length = start + span;
    int first = Math.min(start, tracks.length);
    tracks.length = Math.max(tracks.length, length);

    // Fill in tracks
    for (int i = first; i < length; i++) {
      if (tracks[i] == null) {
        tracks[i] = GridTrack(sizing);
      }
    }
  }

  /// Scans children creating GridLayoutParams as needed, and creates all of the
  /// rows and columns that we will need.
  ///
  /// Note: this can potentially create new qrows/columns, so this needs to be
  /// run before the track sizing algorithm.
  void _ensureAllTracks() {
    final items = view.childViews.map((view_) => view_.layout);

    for (final child in items) {
      if (child.layoutParams == null) {
        final p = GridLayoutParams(child.view, this);
        _ensureTrack(_rowTracks, rowSizing, p.row!, p.rowSpan!);
        _ensureTrack(_columnTracks, columnSizing, p.column!, p.columnSpan!);
        child.layoutParams = p;
      }
      child.cacheExistingBrowserLayout();
    }
  }

  /// Given the track sizes that were computed, position children in the grid.
  void _setBoundsOfChildren() {
    final items = view.childViews.map((view_) => view_.layout);

    for (final item in items) {
      GridLayoutParams childLayout = item.layoutParams as GridLayoutParams;
      var xPos = _getTrackLocationX(childLayout);
      var yPos = _getTrackLocationY(childLayout);

      int? left = xPos.start, width = xPos.length;
      int? top = yPos.start, height = yPos.length;

      // Somewhat counterintuitively (at least to me):
      //   grid-col-align is the horizontal alignment
      //   grid-row-align is the vertical alignment
      xPos = childLayout.columnAlign.align(xPos, item.currentWidth);
      yPos = childLayout.rowAlign.align(yPos, item.currentHeight);

      item.setBounds(xPos.start, yPos.start, xPos.length!, yPos.length!);
    }
  }

  num? _getGridContentSize() {
    if (_dimension == Dimension.WIDTH) {
      return _gridWidth;
    } else if (_dimension == Dimension.HEIGHT) {
      return _gridHeight;
    }
    return null;
  }

  _GridLocation _getTrackLocationX(GridLayoutParams childLayout) {
    int start = childLayout.column! - 1;
    int end = start + childLayout.columnSpan! - 1;

    start = _columnTracks[start].start as int;
    end = _columnTracks[end].end as int;

    return _GridLocation(start, end - start);
  }

  _GridLocation _getTrackLocationY(GridLayoutParams childLayout) {
    int start = childLayout.row! - 1;
    int end = start + childLayout.rowSpan! - 1;

    start = _rowTracks[start].start as int;
    end = _rowTracks[end].end as int;

    return _GridLocation(start, end - start);
  }

  /// Gets the tracks that this item crosses. */
  // TODO(jmesserly): might be better to return an iterable
  List<GridTrack?> _getTracks(ViewLayout item) {
    GridLayoutParams? childLayout = item.layoutParams as GridLayoutParams?;

    int? start, span;
    List<GridTrack>? tracks;
    if (_dimension == Dimension.WIDTH) {
      start = childLayout!.column! - 1;
      span = childLayout.columnSpan;
      tracks = _columnTracks;
    } else if (_dimension == Dimension.HEIGHT) {
      start = childLayout!.row! - 1;
      span = childLayout.rowSpan;
      tracks = _rowTracks;
    }

    assert(start! >= 0 && span! >= 1);

    final result = List<GridTrack>.generate(span!, (i) => tracks![start! + i]);
    return result;
  }

  int? _getSpanCount(ViewLayout item) {
    GridLayoutParams? childLayout = item.layoutParams as GridLayoutParams?;
    return (_dimension == Dimension.WIDTH
        ? childLayout!.columnSpan
        : childLayout!.rowSpan);
  }
}