content: /*
   * Copyright (C) 2020 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package androidx.constraintlayout.core.widgets.analyzer;
  
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.GONE;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.HORIZONTAL;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.MATCH_CONSTRAINT_WRAP;
  import static androidx.constraintlayout.core.widgets.ConstraintWidget.VERTICAL;
  
  import androidx.constraintlayout.core.LinearSystem;
  import androidx.constraintlayout.core.widgets.Barrier;
  import androidx.constraintlayout.core.widgets.ChainHead;
  import androidx.constraintlayout.core.widgets.ConstraintAnchor;
  import androidx.constraintlayout.core.widgets.ConstraintWidget;
  import androidx.constraintlayout.core.widgets.ConstraintWidgetContainer;
  import androidx.constraintlayout.core.widgets.Guideline;
  
  import java.util.ArrayList;
  
  /**
   * Direct resolution engine
   *
   * This walks through the graph of dependencies and infer final position. This allows
   * us to skip the linear solver in many situations, as well as skipping intermediate measure passes.
   *
   * Widgets are solved independently in horizontal and vertical. Any widgets not fully resolved
   * will be computed later on by the linear solver.
   */
  public class Direct {
  
      private static final boolean DEBUG = LinearSystem.FULL_DEBUG;
      private static final boolean APPLY_MATCH_PARENT = false;
      private static BasicMeasure.Measure sMeasure = new BasicMeasure.Measure();
      private static final boolean EARLY_TERMINATION = true; // feature flag -- remove after release.
  
      private static int sHcount = 0;
      private static int sVcount = 0;
  
      /**
       * Walk the dependency graph and solves it.
       *
       * @param layout   the container we want to optimize
       * @param measurer the measurer used to measure the widget
       */
      public static void solvingPass(ConstraintWidgetContainer layout,
              BasicMeasure.Measurer measurer) {
          ConstraintWidget.DimensionBehaviour horizontal = layout.getHorizontalDimensionBehaviour();
          ConstraintWidget.DimensionBehaviour vertical = layout.getVerticalDimensionBehaviour();
          sHcount = 0;
          sVcount = 0;
          long time = 0;
          if (DEBUG) {
              time = System.nanoTime();
              System.out.println("#### SOLVING PASS (horiz " + horizontal
                      + ", vert " + vertical + ") ####");
          }
          layout.resetFinalResolution();
          ArrayList<ConstraintWidget> children = layout.getChildren();
          final int count = children.size();
          if (DEBUG) {
              System.out.println("#### SOLVING PASS on " + count + " widgeets ####");
          }
          for (int i = 0; i < count; i++) {
              ConstraintWidget child = children.get(i);
              child.resetFinalResolution();
          }
  
          boolean isRtl = layout.isRtl();
  
          // First, let's solve the horizontal dependencies, as it's a lot more common to have
          // a container with a fixed horizontal dimension (e.g. match_parent) than the opposite.
  
          // If we know our size, we can fully set the entire dimension, but if not we can
          // still solve what we can starting from the left.
          if (horizontal == ConstraintWidget.DimensionBehaviour.FIXED) {
              layout.setFinalHorizontal(0, layout.getWidth());
          } else {
              layout.setFinalLeft(0);
          }
  
          if (DEBUG) {
              System.out.println("\n### Let's solve horizontal dependencies ###\n");
          }
  
          // Then let's first try to solve horizontal guidelines,
          // as they only depends on the container
          boolean hasGuideline = false;
          boolean hasBarrier = false;
          for (int i = 0; i < count; i++) {
              ConstraintWidget child = children.get(i);
              if (child instanceof Guideline) {
                  Guideline guideline = (Guideline) child;
                  if (guideline.getOrientation() == Guideline.VERTICAL) {
                      if (guideline.getRelativeBegin() != -1) {
                          guideline.setFinalValue(guideline.getRelativeBegin());
                      } else if (guideline.getRelativeEnd() != -1
                              && layout.isResolvedHorizontally()) {
                          guideline.setFinalValue(layout.getWidth() - guideline.getRelativeEnd());
                      } else if (layout.isResolvedHorizontally()) {
                          int position =
                                  (int) (0.5f + guideline.getRelativePercent() * layout.getWidth());
                          guideline.setFinalValue(position);
                      }
                      hasGuideline = true;
                  }
              } else if (child instanceof Barrier) {
                  Barrier barrier = (Barrier) child;
                  if (barrier.getOrientation() == HORIZONTAL) {
                      hasBarrier = true;
                  }
              }
          }
          if (hasGuideline) {
              if (DEBUG) {
                  System.out.println("\n#### VERTICAL GUIDELINES CHECKS ####");
              }
              for (int i = 0; i < count; i++) {
                  ConstraintWidget child = children.get(i);
                  if (child instanceof Guideline) {
                      Guideline guideline = (Guideline) child;
                      if (guideline.getOrientation() == Guideline.VERTICAL) {
                          horizontalSolvingPass(0, guideline, measurer, isRtl);
                      }
                  }
              }
              if (DEBUG) {
                  System.out.println("### Done solving guidelines.");
              }
          }
  
          if (DEBUG) {
              System.out.println("\n#### HORIZONTAL SOLVING PASS ####");
          }
  
          // Now let's resolve what we can in the dependencies of the container
          horizontalSolvingPass(0, layout, measurer, isRtl);
  
          // Finally, let's go through barriers, as they depends on widgets that may have been solved.
          if (hasBarrier) {
              if (DEBUG) {
                  System.out.println("\n#### HORIZONTAL BARRIER CHECKS ####");
              }
              for (int i = 0; i < count; i++) {
                  ConstraintWidget child = children.get(i);
                  if (child instanceof Barrier) {
                      Barrier barrier = (Barrier) child;
                      if (barrier.getOrientation() == HORIZONTAL) {
                          solveBarrier(0, barrier, measurer, HORIZONTAL, isRtl);
                      }
                  }
              }
              if (DEBUG) {
                  System.out.println("#### DONE HORIZONTAL BARRIER CHECKS ####");
              }
          }
  
          if (DEBUG) {
              System.out.println("\n### Let's solve vertical dependencies now ###\n");
          }
  
          // Now we are done with the horizontal axis, let's see what we can do vertically
          if (vertical == ConstraintWidget.DimensionBehaviour.FIXED) {
              layout.setFinalVertical(0, layout.getHeight());
          } else {
              layout.setFinalTop(0);
          }
  
          // Same thing as above -- let's start with guidelines...
          hasGuideline = false;
          hasBarrier = false;
          for (int i = 0; i < count; i++) {
              ConstraintWidget child = children.get(i);
              if (child instanceof Guideline) {
                  Guideline guideline = (Guideline) child;
                  if (guideline.getOrientation() == Guideline.HORIZONTAL) {
                      if (guideline.getRelativeBegin() != -1) {
                          guideline.setFinalValue(guideline.getRelativeBegin());
                      } else if (guideline.getRelativeEnd() != -1 && layout.isResolvedVertically()) {
                          guideline.setFinalValue(layout.getHeight() - guideline.getRelativeEnd());
                      } else if (layout.isResolvedVertically()) {
                          int position =
                                  (int) (0.5f + guideline.getRelativePercent() * layout.getHeight());
                          guideline.setFinalValue(position);
                      }
                      hasGuideline = true;
                  }
              } else if (child instanceof Barrier) {
                  Barrier barrier = (Barrier) child;
                  if (barrier.getOrientation() == ConstraintWidget.VERTICAL) {
                      hasBarrier = true;
                  }
              }
          }
          if (hasGuideline) {
              if (DEBUG) {
                  System.out.println("\n#### HORIZONTAL GUIDELINES CHECKS ####");
              }
              for (int i = 0; i < count; i++) {
                  ConstraintWidget child = children.get(i);
                  if (child instanceof Guideline) {
                      Guideline guideline = (Guideline) child;
                      if (guideline.getOrientation() == Guideline.HORIZONTAL) {
                          verticalSolvingPass(1, guideline, measurer);
                      }
                  }
              }
              if (DEBUG) {
                  System.out.println("\n### Done solving guidelines.");
              }
          }
  
          if (DEBUG) {
              System.out.println("\n#### VERTICAL SOLVING PASS ####");
          }
  
          // ...then solve the vertical dependencies...
          verticalSolvingPass(0, layout, measurer);
  
          // ...then deal with any barriers left.
          if (hasBarrier) {
              if (DEBUG) {
                  System.out.println("#### VERTICAL BARRIER CHECKS ####");
              }
              for (int i = 0; i < count; i++) {
                  ConstraintWidget child = children.get(i);
                  if (child instanceof Barrier) {
                      Barrier barrier = (Barrier) child;
                      if (barrier.getOrientation() == ConstraintWidget.VERTICAL) {
                          solveBarrier(0, barrier, measurer, VERTICAL, isRtl);
                      }
                  }
              }
          }
  
          if (DEBUG) {
              System.out.println("\n#### LAST PASS ####");
          }
          // We can do a last pass to see any widget that could still be measured
          for (int i = 0; i < count; i++) {
              ConstraintWidget child = children.get(i);
              if (child.isMeasureRequested() && canMeasure(0, child)) {
                  ConstraintWidgetContainer.measure(0, child,
                          measurer, sMeasure, BasicMeasure.Measure.SELF_DIMENSIONS);
                  if (child instanceof Guideline) {
                      if (((Guideline) child).getOrientation() == Guideline.HORIZONTAL) {
                          verticalSolvingPass(0, child, measurer);
                      } else {
                          horizontalSolvingPass(0, child, measurer, isRtl);
                      }
                  } else {
                      horizontalSolvingPass(0, child, measurer, isRtl);
                      verticalSolvingPass(0, child, measurer);
                  }
              }
          }
  
          if (DEBUG) {
              time = System.nanoTime() - time;
              System.out.println("\n*** THROUGH WITH DIRECT PASS in " + time + " ns ***\n");
              System.out.println("hcount: " + sHcount + " vcount: " + sVcount);
          }
      }
  
      /**
       * Ask the barrier if it's resolved, and if so do a solving pass
       */
      private static void solveBarrier(int level,
              Barrier barrier,
              BasicMeasure.Measurer measurer,
              int orientation,
              boolean isRtl) {
          if (barrier.allSolved()) {
              if (orientation == HORIZONTAL) {
                  horizontalSolvingPass(level + 1, barrier, measurer, isRtl);
              } else {
                  verticalSolvingPass(level + 1, barrier, measurer);
              }
          }
      }
  
      /**
       * Small utility function to indent logs depending on the level
       *
       * @return a formatted string for the indentation
       */
      public static String ls(int level) {
          StringBuilder builder = new StringBuilder();
          for (int i = 0; i < level; i++) {
              builder.append("  ");
          }
          builder.append("+-(" + level + ") ");
          return builder.toString();
      }
  
      /**
       * Does an horizontal solving pass for the given widget. This will walk through the widget's
       * horizontal dependencies and if they can be resolved directly, do so.
       *
       * @param layout   the widget we want to solve the dependencies
       * @param measurer the measurer object to measure the widgets.
       */
      private static void horizontalSolvingPass(int level,
              ConstraintWidget layout,
              BasicMeasure.Measurer measurer,
              boolean isRtl) {
          if (EARLY_TERMINATION && layout.isHorizontalSolvingPassDone()) {
              if (DEBUG) {
                  System.out.println(ls(level) + "HORIZONTAL SOLVING PASS ON "
                          + layout.getDebugName() + " ALREADY CALLED");
              }
              return;
          }
          sHcount++;
          if (DEBUG) {
              System.out.println(ls(level) + "HORIZONTAL SOLVING PASS ON " + layout.getDebugName());
          }
  
          if (!(layout instanceof ConstraintWidgetContainer) && layout.isMeasureRequested()
                  && canMeasure(level + 1, layout)) {
              BasicMeasure.Measure measure = new BasicMeasure.Measure();
              ConstraintWidgetContainer.measure(level + 1, layout,
                      measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
          }
  
          ConstraintAnchor left = layout.getAnchor(ConstraintAnchor.Type.LEFT);
          ConstraintAnchor right = layout.getAnchor(ConstraintAnchor.Type.RIGHT);
          int l = left.getFinalValue();
          int r = right.getFinalValue();
  
          if (left.getDependents() != null && left.hasFinalValue()) {
              for (ConstraintAnchor first : left.getDependents()) {
                  ConstraintWidget widget = first.mOwner;
                  int x1 = 0;
                  int x2 = 0;
                  boolean canMeasure = canMeasure(level + 1, widget);
                  if (widget.isMeasureRequested() && canMeasure) {
                      BasicMeasure.Measure measure = new BasicMeasure.Measure();
                      ConstraintWidgetContainer.measure(level + 1, widget,
                              measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
                  }
  
                  boolean bothConnected = (first == widget.mLeft && widget.mRight.mTarget != null
                          && widget.mRight.mTarget.hasFinalValue())
                          || (first == widget.mRight && widget.mLeft.mTarget != null
                          && widget.mLeft.mTarget.hasFinalValue());
                  if (widget.getHorizontalDimensionBehaviour()
                          != ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT || canMeasure) {
                      if (widget.isMeasureRequested()) {
                          // Widget needs to be measured
                          if (DEBUG) {
                              System.out.println(ls(level + 1) + "(L) We didn't measure "
                                      + widget.getDebugName() + ", let's bail");
                          }
                          continue;
                      }
                      if (first == widget.mLeft && widget.mRight.mTarget == null) {
                          x1 = l + widget.mLeft.getMargin();
                          x2 = x1 + widget.getWidth();
                          widget.setFinalHorizontal(x1, x2);
                          horizontalSolvingPass(level + 1, widget, measurer, isRtl);
                      } else if (first == widget.mRight && widget.mLeft.mTarget == null) {
                          x2 = l - widget.mRight.getMargin();
                          x1 = x2 - widget.getWidth();
                          widget.setFinalHorizontal(x1, x2);
                          horizontalSolvingPass(level + 1, widget, measurer, isRtl);
                      } else if (bothConnected && !widget.isInHorizontalChain()) {
                          solveHorizontalCenterConstraints(level + 1, measurer, widget, isRtl);
                      } else if (APPLY_MATCH_PARENT && widget.getHorizontalDimensionBehaviour()
                              == ConstraintWidget.DimensionBehaviour.MATCH_PARENT) {
                          widget.setFinalHorizontal(0, widget.getWidth());
                          horizontalSolvingPass(level + 1, widget, measurer, isRtl);
                      }
                  } else if (widget.getHorizontalDimensionBehaviour()
                          == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
                          && widget.mMatchConstraintMaxWidth >= 0
                          && widget.mMatchConstraintMinWidth >= 0
                          && (widget.getVisibility() == ConstraintWidget.GONE
                          || ((widget.mMatchConstraintDefaultWidth
                          == ConstraintWidget.MATCH_CONSTRAINT_SPREAD)
                          && widget.getDimensionRatio() == 0))
                          && !widget.isInHorizontalChain() && !widget.isInVirtualLayout()) {
                      if (bothConnected && !widget.isInHorizontalChain()) {
                          solveHorizontalMatchConstraint(level + 1, layout, measurer, widget, isRtl);
                      }
                  }
              }
          }
          if (layout instanceof Guideline) {
              return;
          }
          if (right.getDependents() != null && right.hasFinalValue()) {
              for (ConstraintAnchor first : right.getDependents()) {
                  ConstraintWidget widget = first.mOwner;
                  boolean canMeasure = canMeasure(level + 1, widget);
                  if (widget.isMeasureRequested() && canMeasure) {
                      BasicMeasure.Measure measure = new BasicMeasure.Measure();
                      ConstraintWidgetContainer.measure(level + 1, widget,
                              measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
                  }
  
                  int x1 = 0;
                  int x2 = 0;
                  boolean bothConnected = (first == widget.mLeft && widget.mRight.mTarget != null
                          && widget.mRight.mTarget.hasFinalValue())
                          || (first == widget.mRight && widget.mLeft.mTarget != null
                          && widget.mLeft.mTarget.hasFinalValue());
                  if (widget.getHorizontalDimensionBehaviour()
                          != ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT || canMeasure) {
                      if (widget.isMeasureRequested()) {
                          // Widget needs to be measured
                          if (DEBUG) {
                              System.out.println(ls(level + 1) + "(R) We didn't measure "
                                      + widget.getDebugName() + ", le'ts bail");
                          }
                          continue;
                      }
                      if (first == widget.mLeft && widget.mRight.mTarget == null) {
                          x1 = r + widget.mLeft.getMargin();
                          x2 = x1 + widget.getWidth();
                          widget.setFinalHorizontal(x1, x2);
                          horizontalSolvingPass(level + 1, widget, measurer, isRtl);
                      } else if (first == widget.mRight && widget.mLeft.mTarget == null) {
                          x2 = r - widget.mRight.getMargin();
                          x1 = x2 - widget.getWidth();
                          widget.setFinalHorizontal(x1, x2);
                          horizontalSolvingPass(level + 1, widget, measurer, isRtl);
                      } else if (bothConnected && !widget.isInHorizontalChain()) {
                          solveHorizontalCenterConstraints(level + 1, measurer, widget, isRtl);
                      }
                  } else if (widget.getHorizontalDimensionBehaviour()
                          == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
                          && widget.mMatchConstraintMaxWidth >= 0
                          && widget.mMatchConstraintMinWidth >= 0
                          && (widget.getVisibility() == ConstraintWidget.GONE
                          || ((widget.mMatchConstraintDefaultWidth
                          == ConstraintWidget.MATCH_CONSTRAINT_SPREAD)
                          && widget.getDimensionRatio() == 0))
                          && !widget.isInHorizontalChain() && !widget.isInVirtualLayout()) {
                      if (bothConnected && !widget.isInHorizontalChain()) {
                          solveHorizontalMatchConstraint(level + 1, layout, measurer, widget, isRtl);
                      }
                  }
              }
          }
          layout.markHorizontalSolvingPassDone();
      }
  
      /**
       * Does an vertical solving pass for the given widget. This will walk through the widget's
       * vertical dependencies and if they can be resolved directly, do so.
       *
       * @param layout   the widget we want to solve the dependencies
       * @param measurer the measurer object to measure the widgets.
       */
      private static void verticalSolvingPass(int level,
              ConstraintWidget layout,
              BasicMeasure.Measurer measurer) {
          if (EARLY_TERMINATION && layout.isVerticalSolvingPassDone()) {
              if (DEBUG) {
                  System.out.println(ls(level) + "VERTICAL SOLVING PASS ON "
                          + layout.getDebugName() + " ALREADY CALLED");
              }
              return;
          }
          sVcount++;
          if (DEBUG) {
              System.out.println(ls(level) + "VERTICAL SOLVING PASS ON " + layout.getDebugName());
          }
  
          if (!(layout instanceof ConstraintWidgetContainer)
                  && layout.isMeasureRequested() && canMeasure(level + 1, layout)) {
              BasicMeasure.Measure measure = new BasicMeasure.Measure();
              ConstraintWidgetContainer.measure(level + 1, layout,
                      measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
          }
  
          ConstraintAnchor top = layout.getAnchor(ConstraintAnchor.Type.TOP);
          ConstraintAnchor bottom = layout.getAnchor(ConstraintAnchor.Type.BOTTOM);
          int t = top.getFinalValue();
          int b = bottom.getFinalValue();
  
          if (top.getDependents() != null && top.hasFinalValue()) {
              for (ConstraintAnchor first : top.getDependents()) {
                  ConstraintWidget widget = first.mOwner;
                  int y1 = 0;
                  int y2 = 0;
                  boolean canMeasure = canMeasure(level + 1, widget);
                  if (widget.isMeasureRequested() && canMeasure) {
                      BasicMeasure.Measure measure = new BasicMeasure.Measure();
                      ConstraintWidgetContainer.measure(level + 1, widget,
                              measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
                  }
  
                  boolean bothConnected = (first == widget.mTop && widget.mBottom.mTarget != null
                          && widget.mBottom.mTarget.hasFinalValue())
                          || (first == widget.mBottom && widget.mTop.mTarget != null
                          && widget.mTop.mTarget.hasFinalValue());
                  if (widget.getVerticalDimensionBehaviour()
                          != ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
                          || canMeasure) {
                      if (widget.isMeasureRequested()) {
                          // Widget needs to be measured
                          if (DEBUG) {
                              System.out.println(ls(level + 1) + "(T) We didn't measure "
                                      + widget.getDebugName() + ", le'ts bail");
                          }
                          continue;
                      }
                      if (first == widget.mTop && widget.mBottom.mTarget == null) {
                          y1 = t + widget.mTop.getMargin();
                          y2 = y1 + widget.getHeight();
                          widget.setFinalVertical(y1, y2);
                          verticalSolvingPass(level + 1, widget, measurer);
                      } else if (first == widget.mBottom && widget.mTop.mTarget == null) {
                          y2 = t - widget.mBottom.getMargin();
                          y1 = y2 - widget.getHeight();
                          widget.setFinalVertical(y1, y2);
                          verticalSolvingPass(level + 1, widget, measurer);
                      } else if (bothConnected && !widget.isInVerticalChain()) {
                          solveVerticalCenterConstraints(level + 1, measurer, widget);
                      } else if (APPLY_MATCH_PARENT && widget.getVerticalDimensionBehaviour()
                              == ConstraintWidget.DimensionBehaviour.MATCH_PARENT) {
                          widget.setFinalVertical(0, widget.getHeight());
                          verticalSolvingPass(level + 1, widget, measurer);
                      }
                  } else if (widget.getVerticalDimensionBehaviour()
                          == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
                          && widget.mMatchConstraintMaxHeight >= 0
                          && widget.mMatchConstraintMinHeight >= 0
                          && (widget.getVisibility() == ConstraintWidget.GONE
                          || ((widget.mMatchConstraintDefaultHeight
                          == ConstraintWidget.MATCH_CONSTRAINT_SPREAD)
                          && widget.getDimensionRatio() == 0))
                          && !widget.isInVerticalChain() && !widget.isInVirtualLayout()) {
                      if (bothConnected && !widget.isInVerticalChain()) {
                          solveVerticalMatchConstraint(level + 1, layout, measurer, widget);
                      }
                  }
              }
          }
          if (layout instanceof Guideline) {
              return;
          }
          if (bottom.getDependents() != null && bottom.hasFinalValue()) {
              for (ConstraintAnchor first : bottom.getDependents()) {
                  ConstraintWidget widget = first.mOwner;
                  boolean canMeasure = canMeasure(level + 1, widget);
                  if (widget.isMeasureRequested() && canMeasure) {
                      BasicMeasure.Measure measure = new BasicMeasure.Measure();
                      ConstraintWidgetContainer.measure(level + 1, widget,
                              measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
                  }
  
                  int y1 = 0;
                  int y2 = 0;
                  boolean bothConnected = (first == widget.mTop && widget.mBottom.mTarget != null
                          && widget.mBottom.mTarget.hasFinalValue())
                          || (first == widget.mBottom && widget.mTop.mTarget != null
                          && widget.mTop.mTarget.hasFinalValue());
                  if (widget.getVerticalDimensionBehaviour()
                          != ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT || canMeasure) {
                      if (widget.isMeasureRequested()) {
                          // Widget needs to be measured
                          if (DEBUG) {
                              System.out.println(ls(level + 1) + "(B) We didn't measure "
                                      + widget.getDebugName() + ", le'ts bail");
                          }
                          continue;
                      }
                      if (first == widget.mTop && widget.mBottom.mTarget == null) {
                          y1 = b + widget.mTop.getMargin();
                          y2 = y1 + widget.getHeight();
                          widget.setFinalVertical(y1, y2);
                          verticalSolvingPass(level + 1, widget, measurer);
                      } else if (first == widget.mBottom && widget.mTop.mTarget == null) {
                          y2 = b - widget.mBottom.getMargin();
                          y1 = y2 - widget.getHeight();
                          widget.setFinalVertical(y1, y2);
                          verticalSolvingPass(level + 1, widget, measurer);
                      } else if (bothConnected && !widget.isInVerticalChain()) {
                          solveVerticalCenterConstraints(level + 1, measurer, widget);
                      }
                  } else if (widget.getVerticalDimensionBehaviour()
                          == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
                          && widget.mMatchConstraintMaxHeight >= 0
                          && widget.mMatchConstraintMinHeight >= 0
                          && (widget.getVisibility() == ConstraintWidget.GONE
                          || ((widget.mMatchConstraintDefaultHeight
                          == ConstraintWidget.MATCH_CONSTRAINT_SPREAD)
                          && widget.getDimensionRatio() == 0))
                          && !widget.isInVerticalChain() && !widget.isInVirtualLayout()) {
                      if (bothConnected && !widget.isInVerticalChain()) {
                          solveVerticalMatchConstraint(level + 1, layout, measurer, widget);
                      }
                  }
              }
          }
  
          ConstraintAnchor baseline = layout.getAnchor(ConstraintAnchor.Type.BASELINE);
          if (baseline.getDependents() != null && baseline.hasFinalValue()) {
              int baselineValue = baseline.getFinalValue();
              for (ConstraintAnchor first : baseline.getDependents()) {
                  ConstraintWidget widget = first.mOwner;
                  boolean canMeasure = canMeasure(level + 1, widget);
                  if (widget.isMeasureRequested() && canMeasure) {
                      BasicMeasure.Measure measure = new BasicMeasure.Measure();
                      ConstraintWidgetContainer.measure(level + 1, widget,
                              measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
                  }
                  if (widget.getVerticalDimensionBehaviour()
                          != ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT || canMeasure) {
                      if (widget.isMeasureRequested()) {
                          // Widget needs to be measured
                          if (DEBUG) {
                              System.out.println(ls(level + 1) + "(B) We didn't measure "
                                      + widget.getDebugName() + ", le'ts bail");
                          }
                          continue;
                      }
                      if (first == widget.mBaseline) {
                          widget.setFinalBaseline(baselineValue + first.getMargin());
                          verticalSolvingPass(level + 1, widget, measurer);
                      }
                  }
              }
          }
          layout.markVerticalSolvingPassDone();
      }
  
      /**
       * Solve horizontal centering constraints
       */
      private static void solveHorizontalCenterConstraints(int level,
              BasicMeasure.Measurer measurer,
              ConstraintWidget widget,
              boolean isRtl) {
          // TODO: Handle match constraints here or before calling this
          int x1;
          int x2;
          float bias = widget.getHorizontalBiasPercent();
          int start = widget.mLeft.mTarget.getFinalValue();
          int end = widget.mRight.mTarget.getFinalValue();
          int s1 = start + widget.mLeft.getMargin();
          int s2 = end - widget.mRight.getMargin();
          if (start == end) {
              bias = 0.5f;
              s1 = start;
              s2 = end;
          }
          int width = widget.getWidth();
          int distance = s2 - s1 - width;
          if (s1 > s2) {
              distance = s1 - s2 - width;
          }
          int d1;
          if (distance > 0) {
              d1 = (int) (0.5f + bias * distance);
          } else {
              d1 = (int) (bias * distance);
          }
          x1 = s1 + d1;
          x2 = x1 + width;
          if (s1 > s2) {
              x1 = s1 + d1;
              x2 = x1 - width;
          }
          widget.setFinalHorizontal(x1, x2);
          horizontalSolvingPass(level + 1, widget, measurer, isRtl);
      }
  
      /**
       * Solve vertical centering constraints
       */
      private static void solveVerticalCenterConstraints(int level,
              BasicMeasure.Measurer measurer,
              ConstraintWidget widget) {
          // TODO: Handle match constraints here or before calling this
          int y1;
          int y2;
          float bias = widget.getVerticalBiasPercent();
          int start = widget.mTop.mTarget.getFinalValue();
          int end = widget.mBottom.mTarget.getFinalValue();
          int s1 = start + widget.mTop.getMargin();
          int s2 = end - widget.mBottom.getMargin();
          if (start == end) {
              bias = 0.5f;
              s1 = start;
              s2 = end;
          }
          int height = widget.getHeight();
          int distance = s2 - s1 - height;
          if (s1 > s2) {
              distance = s1 - s2 - height;
          }
          int d1;
          if (distance > 0) {
              d1 = (int) (0.5f + bias * distance);
          } else {
              d1 = (int) (bias * distance);
          }
          y1 = s1 + d1;
          y2 = y1 + height;
          if (s1 > s2) {
              y1 = s1 - d1;
              y2 = y1 - height;
          }
          widget.setFinalVertical(y1, y2);
          verticalSolvingPass(level + 1, widget, measurer);
      }
  
      /**
       * Solve horizontal match constraints
       */
      private static void solveHorizontalMatchConstraint(int level,
              ConstraintWidget layout,
              BasicMeasure.Measurer measurer,
              ConstraintWidget widget,
              boolean isRtl) {
          int x1;
          int x2;
          float bias = widget.getHorizontalBiasPercent();
          int s1 = widget.mLeft.mTarget.getFinalValue() + widget.mLeft.getMargin();
          int s2 = widget.mRight.mTarget.getFinalValue() - widget.mRight.getMargin();
          if (s2 >= s1) {
              int width = widget.getWidth();
              if (widget.getVisibility() != ConstraintWidget.GONE) {
                  if (widget.mMatchConstraintDefaultWidth
                          == ConstraintWidget.MATCH_CONSTRAINT_PERCENT) {
                      int parentWidth = 0;
                      if (layout instanceof ConstraintWidgetContainer) {
                          parentWidth = layout.getWidth();
                      } else {
                          parentWidth = layout.getParent().getWidth();
                      }
                      width = (int) (0.5f * widget.getHorizontalBiasPercent() * parentWidth);
                  } else if (widget.mMatchConstraintDefaultWidth
                          == ConstraintWidget.MATCH_CONSTRAINT_SPREAD) {
                      width = s2 - s1;
                  }
                  width = Math.max(widget.mMatchConstraintMinWidth, width);
                  if (widget.mMatchConstraintMaxWidth > 0) {
                      width = Math.min(widget.mMatchConstraintMaxWidth, width);
                  }
              }
              int distance = s2 - s1 - width;
              int d1 = (int) (0.5f + bias * distance);
              x1 = s1 + d1;
              x2 = x1 + width;
              widget.setFinalHorizontal(x1, x2);
              horizontalSolvingPass(level + 1, widget, measurer, isRtl);
          }
      }
  
      /**
       * Solve vertical match constraints
       */
      private static void solveVerticalMatchConstraint(int level,
              ConstraintWidget layout,
              BasicMeasure.Measurer measurer,
              ConstraintWidget widget) {
          int y1;
          int y2;
          float bias = widget.getVerticalBiasPercent();
          int s1 = widget.mTop.mTarget.getFinalValue() + widget.mTop.getMargin();
          int s2 = widget.mBottom.mTarget.getFinalValue() - widget.mBottom.getMargin();
          if (s2 >= s1) {
              int height = widget.getHeight();
              if (widget.getVisibility() != ConstraintWidget.GONE) {
                  if (widget.mMatchConstraintDefaultHeight
                          == ConstraintWidget.MATCH_CONSTRAINT_PERCENT) {
                      int parentHeight = 0;
                      if (layout instanceof ConstraintWidgetContainer) {
                          parentHeight = layout.getHeight();
                      } else {
                          parentHeight = layout.getParent().getHeight();
                      }
                      height = (int) (0.5f * bias * parentHeight);
                  } else if (widget.mMatchConstraintDefaultHeight
                          == ConstraintWidget.MATCH_CONSTRAINT_SPREAD) {
                      height = s2 - s1;
                  }
                  height = Math.max(widget.mMatchConstraintMinHeight, height);
                  if (widget.mMatchConstraintMaxHeight > 0) {
                      height = Math.min(widget.mMatchConstraintMaxHeight, height);
                  }
              }
              int distance = s2 - s1 - height;
              int d1 = (int) (0.5f + bias * distance);
              y1 = s1 + d1;
              y2 = y1 + height;
              widget.setFinalVertical(y1, y2);
              verticalSolvingPass(level + 1, widget, measurer);
          }
      }
  
      /**
       * Returns true if the dimensions of the given widget are computable directly
       *
       * @param layout the widget to check
       * @return true if both dimensions are knowable by a single measure pass
       */
      private static boolean canMeasure(int level, ConstraintWidget layout) {
          ConstraintWidget.DimensionBehaviour horizontalBehaviour =
                  layout.getHorizontalDimensionBehaviour();
          ConstraintWidget.DimensionBehaviour verticalBehaviour =
                  layout.getVerticalDimensionBehaviour();
          ConstraintWidgetContainer parent = layout.getParent() != null
                  ? (ConstraintWidgetContainer) layout.getParent() : null;
          boolean isParentHorizontalFixed = parent != null && parent.getHorizontalDimensionBehaviour()
                  == ConstraintWidget.DimensionBehaviour.FIXED;
          boolean isParentVerticalFixed = parent != null && parent.getVerticalDimensionBehaviour()
                  == ConstraintWidget.DimensionBehaviour.FIXED;
          boolean isHorizontalFixed = horizontalBehaviour == ConstraintWidget.DimensionBehaviour.FIXED
                  || layout.isResolvedHorizontally()
                  || (APPLY_MATCH_PARENT && horizontalBehaviour
                  == ConstraintWidget.DimensionBehaviour.MATCH_PARENT && isParentHorizontalFixed)
                  || horizontalBehaviour == ConstraintWidget.DimensionBehaviour.WRAP_CONTENT
                  || (horizontalBehaviour == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
                  && layout.mMatchConstraintDefaultWidth
                  == ConstraintWidget.MATCH_CONSTRAINT_SPREAD
                  && layout.mDimensionRatio == 0
                  && layout.hasDanglingDimension(HORIZONTAL))
                  || (horizontalBehaviour == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
                  && layout.mMatchConstraintDefaultWidth == MATCH_CONSTRAINT_WRAP
                  && layout.hasResolvedTargets(HORIZONTAL, layout.getWidth()));
          boolean isVerticalFixed = verticalBehaviour == ConstraintWidget.DimensionBehaviour.FIXED
                  || layout.isResolvedVertically()
                  || (APPLY_MATCH_PARENT && verticalBehaviour
                  == ConstraintWidget.DimensionBehaviour.MATCH_PARENT && isParentVerticalFixed)
                  || verticalBehaviour == ConstraintWidget.DimensionBehaviour.WRAP_CONTENT
                  || (verticalBehaviour == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
                  && layout.mMatchConstraintDefaultHeight
                  == ConstraintWidget.MATCH_CONSTRAINT_SPREAD
                  && layout.mDimensionRatio == 0
                  && layout.hasDanglingDimension(ConstraintWidget.VERTICAL))
                  || (verticalBehaviour == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
                  && layout.mMatchConstraintDefaultHeight == MATCH_CONSTRAINT_WRAP
                  && layout.hasResolvedTargets(VERTICAL, layout.getHeight()));
          if (layout.mDimensionRatio > 0 && (isHorizontalFixed || isVerticalFixed)) {
              return true;
          }
          if (DEBUG) {
              System.out.println(ls(level) + "can measure " + layout.getDebugName() + " ? "
                      + (isHorizontalFixed && isVerticalFixed) + "  [ "
                      + isHorizontalFixed + " (horiz " + horizontalBehaviour + ") & "
                      + isVerticalFixed + " (vert " + verticalBehaviour + ") ]");
          }
          return isHorizontalFixed && isVerticalFixed;
      }
  
      /**
       * Try to directly resolve the chain
       *
       * @return true if fully resolved
       */
      public static boolean solveChain(ConstraintWidgetContainer container, LinearSystem system,
              int orientation, int offset, ChainHead chainHead,
              boolean isChainSpread, boolean isChainSpreadInside,
              boolean isChainPacked) {
          if (LinearSystem.FULL_DEBUG) {
              System.out.println("\n### SOLVE CHAIN ###");
          }
          if (isChainPacked) {
              return false;
          }
          if (orientation == HORIZONTAL) {
              if (!container.isResolvedHorizontally()) {
                  return false;
              }
          } else {
              if (!container.isResolvedVertically()) {
                  return false;
              }
          }
          int level = 0; // nested level (used for debugging)
          boolean isRtl = container.isRtl();
  
          ConstraintWidget first = chainHead.getFirst();
          ConstraintWidget last = chainHead.getLast();
          ConstraintWidget firstVisibleWidget = chainHead.getFirstVisibleWidget();
          ConstraintWidget lastVisibleWidget = chainHead.getLastVisibleWidget();
          ConstraintWidget head = chainHead.getHead();
  
          ConstraintWidget widget = first;
          ConstraintWidget next;
          boolean done = false;
  
          ConstraintAnchor begin = first.mListAnchors[offset];
          ConstraintAnchor end = last.mListAnchors[offset + 1];
          if (begin.mTarget == null || end.mTarget == null) {
              return false;
          }
          if (!begin.mTarget.hasFinalValue() || !end.mTarget.hasFinalValue()) {
              return false;
          }
  
          if (firstVisibleWidget == null || lastVisibleWidget == null) {
              return false;
          }
  
          int startPoint = begin.mTarget.getFinalValue()
                  + firstVisibleWidget.mListAnchors[offset].getMargin();
          int endPoint = end.mTarget.getFinalValue()
                  - lastVisibleWidget.mListAnchors[offset + 1].getMargin();
  
          int distance = endPoint - startPoint;
          if (distance <= 0) {
              return false;
          }
          int totalSize = 0;
          BasicMeasure.Measure measure = new BasicMeasure.Measure();
  
          int numWidgets = 0;
          int numVisibleWidgets = 0;
  
          while (!done) {
              boolean canMeasure = canMeasure(level + 1, widget);
              if (!canMeasure) {
                  return false;
              }
              if (widget.mListDimensionBehaviors[orientation]
                      == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT) {
                  return false;
              }
  
              if (widget.isMeasureRequested()) {
                  ConstraintWidgetContainer.measure(level + 1, widget,
                          container.getMeasurer(), measure, BasicMeasure.Measure.SELF_DIMENSIONS);
              }
  
              totalSize += widget.mListAnchors[offset].getMargin();
              if (orientation == HORIZONTAL) {
                  totalSize += +widget.getWidth();
              } else {
                  totalSize += widget.getHeight();
              }
              totalSize += widget.mListAnchors[offset + 1].getMargin();
  
              numWidgets++;
              if (widget.getVisibility() != ConstraintWidget.GONE) {
                  numVisibleWidgets++;
              }
  
  
              // go to the next widget
              ConstraintAnchor nextAnchor = widget.mListAnchors[offset + 1].mTarget;
              if (nextAnchor != null) {
                  next = nextAnchor.mOwner;
                  if (next.mListAnchors[offset].mTarget == null
                          || next.mListAnchors[offset].mTarget.mOwner != widget) {
                      next = null;
                  }
              } else {
                  next = null;
              }
              if (next != null) {
                  widget = next;
              } else {
                  done = true;
              }
          }
  
          if (numVisibleWidgets == 0) {
              return false;
          }
  
          if (numVisibleWidgets != numWidgets) {
              return false;
          }
  
          if (distance < totalSize) {
              return false;
          }
  
          int gap = distance - totalSize;
          if (isChainSpread) {
              gap = gap / (numVisibleWidgets + 1);
          } else if (isChainSpreadInside) {
              if (numVisibleWidgets > 2) {
                  gap = gap / numVisibleWidgets - 1;
              }
          }
  
          if (numVisibleWidgets == 1) {
              float bias;
              if (orientation == ConstraintWidget.HORIZONTAL) {
                  bias = head.getHorizontalBiasPercent();
              } else {
                  bias = head.getVerticalBiasPercent();
              }
              int p1 = (int) (0.5f + startPoint + gap * bias);
              if (orientation == HORIZONTAL) {
                  firstVisibleWidget.setFinalHorizontal(p1, p1 + firstVisibleWidget.getWidth());
              } else {
                  firstVisibleWidget.setFinalVertical(p1, p1 + firstVisibleWidget.getHeight());
              }
              Direct.horizontalSolvingPass(level + 1,
                      firstVisibleWidget, container.getMeasurer(), isRtl);
              return true;
          }
  
          if (isChainSpread) {
              done = false;
  
              int current = startPoint + gap;
              widget = first;
              while (!done) {
                  if (widget.getVisibility() == GONE) {
                      if (orientation == HORIZONTAL) {
                          widget.setFinalHorizontal(current, current);
                          Direct.horizontalSolvingPass(level + 1,
                                  widget, container.getMeasurer(), isRtl);
                      } else {
                          widget.setFinalVertical(current, current);
                          Direct.verticalSolvingPass(level + 1, widget, container.getMeasurer());
                      }
                  } else {
                      current += widget.mListAnchors[offset].getMargin();
                      if (orientation == HORIZONTAL) {
                          widget.setFinalHorizontal(current, current + widget.getWidth());
                          Direct.horizontalSolvingPass(level + 1,
                                  widget, container.getMeasurer(), isRtl);
                          current += widget.getWidth();
                      } else {
                          widget.setFinalVertical(current, current + widget.getHeight());
                          Direct.verticalSolvingPass(level + 1, widget, container.getMeasurer());
                          current += widget.getHeight();
                      }
                      current += widget.mListAnchors[offset + 1].getMargin();
                      current += gap;
                  }
  
                  widget.addToSolver(system, false);
  
                  // go to the next widget
                  ConstraintAnchor nextAnchor = widget.mListAnchors[offset + 1].mTarget;
                  if (nextAnchor != null) {
                      next = nextAnchor.mOwner;
                      if (next.mListAnchors[offset].mTarget == null
                              || next.mListAnchors[offset].mTarget.mOwner != widget) {
                          next = null;
                      }
                  } else {
                      next = null;
                  }
                  if (next != null) {
                      widget = next;
                  } else {
                      done = true;
                  }
              }
          } else if (isChainSpreadInside) {
              if (numVisibleWidgets == 2) {
                  if (orientation == HORIZONTAL) {
                      firstVisibleWidget.setFinalHorizontal(startPoint,
                              startPoint + firstVisibleWidget.getWidth());
                      lastVisibleWidget.setFinalHorizontal(endPoint - lastVisibleWidget.getWidth(),
                              endPoint);
                      Direct.horizontalSolvingPass(level + 1,
                              firstVisibleWidget, container.getMeasurer(), isRtl);
                      Direct.horizontalSolvingPass(level + 1,
                              lastVisibleWidget, container.getMeasurer(), isRtl);
                  } else {
                      firstVisibleWidget.setFinalVertical(startPoint,
                              startPoint + firstVisibleWidget.getHeight());
                      lastVisibleWidget.setFinalVertical(endPoint - lastVisibleWidget.getHeight(),
                              endPoint);
                      Direct.verticalSolvingPass(level + 1,
                              firstVisibleWidget, container.getMeasurer());
                      Direct.verticalSolvingPass(level + 1,
                              lastVisibleWidget, container.getMeasurer());
                  }
                  return true;
              }
              return false;
          }
          return true;
      }
  }
  