1 /*
2  * Copyright (C) 2020 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package androidx.constraintlayout.core.widgets.analyzer;
17 
18 import static androidx.constraintlayout.core.widgets.ConstraintWidget.GONE;
19 import static androidx.constraintlayout.core.widgets.ConstraintWidget.HORIZONTAL;
20 import static androidx.constraintlayout.core.widgets.ConstraintWidget.MATCH_CONSTRAINT_WRAP;
21 import static androidx.constraintlayout.core.widgets.ConstraintWidget.VERTICAL;
22 
23 import androidx.constraintlayout.core.LinearSystem;
24 import androidx.constraintlayout.core.widgets.Barrier;
25 import androidx.constraintlayout.core.widgets.ChainHead;
26 import androidx.constraintlayout.core.widgets.ConstraintAnchor;
27 import androidx.constraintlayout.core.widgets.ConstraintWidget;
28 import androidx.constraintlayout.core.widgets.ConstraintWidgetContainer;
29 import androidx.constraintlayout.core.widgets.Guideline;
30 
31 import java.util.ArrayList;
32 
33 /**
34  * Direct resolution engine
35  *
36  * This walks through the graph of dependencies and infer final position. This allows
37  * us to skip the linear solver in many situations, as well as skipping intermediate measure passes.
38  *
39  * Widgets are solved independently in horizontal and vertical. Any widgets not fully resolved
40  * will be computed later on by the linear solver.
41  */
42 public class Direct {
43 
44     private static final boolean DEBUG = LinearSystem.FULL_DEBUG;
45     private static final boolean APPLY_MATCH_PARENT = false;
46     private static BasicMeasure.Measure sMeasure = new BasicMeasure.Measure();
47     private static final boolean EARLY_TERMINATION = true; // feature flag -- remove after release.
48 
49     private static int sHcount = 0;
50     private static int sVcount = 0;
51 
52     /**
53      * Walk the dependency graph and solves it.
54      *
55      * @param layout   the container we want to optimize
56      * @param measurer the measurer used to measure the widget
57      */
solvingPass(ConstraintWidgetContainer layout, BasicMeasure.Measurer measurer)58     public static void solvingPass(ConstraintWidgetContainer layout,
59             BasicMeasure.Measurer measurer) {
60         ConstraintWidget.DimensionBehaviour horizontal = layout.getHorizontalDimensionBehaviour();
61         ConstraintWidget.DimensionBehaviour vertical = layout.getVerticalDimensionBehaviour();
62         sHcount = 0;
63         sVcount = 0;
64         long time = 0;
65         if (DEBUG) {
66             time = System.nanoTime();
67             System.out.println("#### SOLVING PASS (horiz " + horizontal
68                     + ", vert " + vertical + ") ####");
69         }
70         layout.resetFinalResolution();
71         ArrayList<ConstraintWidget> children = layout.getChildren();
72         final int count = children.size();
73         if (DEBUG) {
74             System.out.println("#### SOLVING PASS on " + count + " widgeets ####");
75         }
76         for (int i = 0; i < count; i++) {
77             ConstraintWidget child = children.get(i);
78             child.resetFinalResolution();
79         }
80 
81         boolean isRtl = layout.isRtl();
82 
83         // First, let's solve the horizontal dependencies, as it's a lot more common to have
84         // a container with a fixed horizontal dimension (e.g. match_parent) than the opposite.
85 
86         // If we know our size, we can fully set the entire dimension, but if not we can
87         // still solve what we can starting from the left.
88         if (horizontal == ConstraintWidget.DimensionBehaviour.FIXED) {
89             layout.setFinalHorizontal(0, layout.getWidth());
90         } else {
91             layout.setFinalLeft(0);
92         }
93 
94         if (DEBUG) {
95             System.out.println("\n### Let's solve horizontal dependencies ###\n");
96         }
97 
98         // Then let's first try to solve horizontal guidelines,
99         // as they only depends on the container
100         boolean hasGuideline = false;
101         boolean hasBarrier = false;
102         for (int i = 0; i < count; i++) {
103             ConstraintWidget child = children.get(i);
104             if (child instanceof Guideline) {
105                 Guideline guideline = (Guideline) child;
106                 if (guideline.getOrientation() == Guideline.VERTICAL) {
107                     if (guideline.getRelativeBegin() != -1) {
108                         guideline.setFinalValue(guideline.getRelativeBegin());
109                     } else if (guideline.getRelativeEnd() != -1
110                             && layout.isResolvedHorizontally()) {
111                         guideline.setFinalValue(layout.getWidth() - guideline.getRelativeEnd());
112                     } else if (layout.isResolvedHorizontally()) {
113                         int position =
114                                 (int) (0.5f + guideline.getRelativePercent() * layout.getWidth());
115                         guideline.setFinalValue(position);
116                     }
117                     hasGuideline = true;
118                 }
119             } else if (child instanceof Barrier) {
120                 Barrier barrier = (Barrier) child;
121                 if (barrier.getOrientation() == HORIZONTAL) {
122                     hasBarrier = true;
123                 }
124             }
125         }
126         if (hasGuideline) {
127             if (DEBUG) {
128                 System.out.println("\n#### VERTICAL GUIDELINES CHECKS ####");
129             }
130             for (int i = 0; i < count; i++) {
131                 ConstraintWidget child = children.get(i);
132                 if (child instanceof Guideline) {
133                     Guideline guideline = (Guideline) child;
134                     if (guideline.getOrientation() == Guideline.VERTICAL) {
135                         horizontalSolvingPass(0, guideline, measurer, isRtl);
136                     }
137                 }
138             }
139             if (DEBUG) {
140                 System.out.println("### Done solving guidelines.");
141             }
142         }
143 
144         if (DEBUG) {
145             System.out.println("\n#### HORIZONTAL SOLVING PASS ####");
146         }
147 
148         // Now let's resolve what we can in the dependencies of the container
149         horizontalSolvingPass(0, layout, measurer, isRtl);
150 
151         // Finally, let's go through barriers, as they depends on widgets that may have been solved.
152         if (hasBarrier) {
153             if (DEBUG) {
154                 System.out.println("\n#### HORIZONTAL BARRIER CHECKS ####");
155             }
156             for (int i = 0; i < count; i++) {
157                 ConstraintWidget child = children.get(i);
158                 if (child instanceof Barrier) {
159                     Barrier barrier = (Barrier) child;
160                     if (barrier.getOrientation() == HORIZONTAL) {
161                         solveBarrier(0, barrier, measurer, HORIZONTAL, isRtl);
162                     }
163                 }
164             }
165             if (DEBUG) {
166                 System.out.println("#### DONE HORIZONTAL BARRIER CHECKS ####");
167             }
168         }
169 
170         if (DEBUG) {
171             System.out.println("\n### Let's solve vertical dependencies now ###\n");
172         }
173 
174         // Now we are done with the horizontal axis, let's see what we can do vertically
175         if (vertical == ConstraintWidget.DimensionBehaviour.FIXED) {
176             layout.setFinalVertical(0, layout.getHeight());
177         } else {
178             layout.setFinalTop(0);
179         }
180 
181         // Same thing as above -- let's start with guidelines...
182         hasGuideline = false;
183         hasBarrier = false;
184         for (int i = 0; i < count; i++) {
185             ConstraintWidget child = children.get(i);
186             if (child instanceof Guideline) {
187                 Guideline guideline = (Guideline) child;
188                 if (guideline.getOrientation() == Guideline.HORIZONTAL) {
189                     if (guideline.getRelativeBegin() != -1) {
190                         guideline.setFinalValue(guideline.getRelativeBegin());
191                     } else if (guideline.getRelativeEnd() != -1 && layout.isResolvedVertically()) {
192                         guideline.setFinalValue(layout.getHeight() - guideline.getRelativeEnd());
193                     } else if (layout.isResolvedVertically()) {
194                         int position =
195                                 (int) (0.5f + guideline.getRelativePercent() * layout.getHeight());
196                         guideline.setFinalValue(position);
197                     }
198                     hasGuideline = true;
199                 }
200             } else if (child instanceof Barrier) {
201                 Barrier barrier = (Barrier) child;
202                 if (barrier.getOrientation() == ConstraintWidget.VERTICAL) {
203                     hasBarrier = true;
204                 }
205             }
206         }
207         if (hasGuideline) {
208             if (DEBUG) {
209                 System.out.println("\n#### HORIZONTAL GUIDELINES CHECKS ####");
210             }
211             for (int i = 0; i < count; i++) {
212                 ConstraintWidget child = children.get(i);
213                 if (child instanceof Guideline) {
214                     Guideline guideline = (Guideline) child;
215                     if (guideline.getOrientation() == Guideline.HORIZONTAL) {
216                         verticalSolvingPass(1, guideline, measurer);
217                     }
218                 }
219             }
220             if (DEBUG) {
221                 System.out.println("\n### Done solving guidelines.");
222             }
223         }
224 
225         if (DEBUG) {
226             System.out.println("\n#### VERTICAL SOLVING PASS ####");
227         }
228 
229         // ...then solve the vertical dependencies...
230         verticalSolvingPass(0, layout, measurer);
231 
232         // ...then deal with any barriers left.
233         if (hasBarrier) {
234             if (DEBUG) {
235                 System.out.println("#### VERTICAL BARRIER CHECKS ####");
236             }
237             for (int i = 0; i < count; i++) {
238                 ConstraintWidget child = children.get(i);
239                 if (child instanceof Barrier) {
240                     Barrier barrier = (Barrier) child;
241                     if (barrier.getOrientation() == ConstraintWidget.VERTICAL) {
242                         solveBarrier(0, barrier, measurer, VERTICAL, isRtl);
243                     }
244                 }
245             }
246         }
247 
248         if (DEBUG) {
249             System.out.println("\n#### LAST PASS ####");
250         }
251         // We can do a last pass to see any widget that could still be measured
252         for (int i = 0; i < count; i++) {
253             ConstraintWidget child = children.get(i);
254             if (child.isMeasureRequested() && canMeasure(0, child)) {
255                 ConstraintWidgetContainer.measure(0, child,
256                         measurer, sMeasure, BasicMeasure.Measure.SELF_DIMENSIONS);
257                 if (child instanceof Guideline) {
258                     if (((Guideline) child).getOrientation() == Guideline.HORIZONTAL) {
259                         verticalSolvingPass(0, child, measurer);
260                     } else {
261                         horizontalSolvingPass(0, child, measurer, isRtl);
262                     }
263                 } else {
264                     horizontalSolvingPass(0, child, measurer, isRtl);
265                     verticalSolvingPass(0, child, measurer);
266                 }
267             }
268         }
269 
270         if (DEBUG) {
271             time = System.nanoTime() - time;
272             System.out.println("\n*** THROUGH WITH DIRECT PASS in " + time + " ns ***\n");
273             System.out.println("hcount: " + sHcount + " vcount: " + sVcount);
274         }
275     }
276 
277     /**
278      * Ask the barrier if it's resolved, and if so do a solving pass
279      */
solveBarrier(int level, Barrier barrier, BasicMeasure.Measurer measurer, int orientation, boolean isRtl)280     private static void solveBarrier(int level,
281             Barrier barrier,
282             BasicMeasure.Measurer measurer,
283             int orientation,
284             boolean isRtl) {
285         if (barrier.allSolved()) {
286             if (orientation == HORIZONTAL) {
287                 horizontalSolvingPass(level + 1, barrier, measurer, isRtl);
288             } else {
289                 verticalSolvingPass(level + 1, barrier, measurer);
290             }
291         }
292     }
293 
294     /**
295      * Small utility function to indent logs depending on the level
296      *
297      * @return a formatted string for the indentation
298      */
ls(int level)299     public static String ls(int level) {
300         StringBuilder builder = new StringBuilder();
301         for (int i = 0; i < level; i++) {
302             builder.append("  ");
303         }
304         builder.append("+-(" + level + ") ");
305         return builder.toString();
306     }
307 
308     /**
309      * Does an horizontal solving pass for the given widget. This will walk through the widget's
310      * horizontal dependencies and if they can be resolved directly, do so.
311      *
312      * @param layout   the widget we want to solve the dependencies
313      * @param measurer the measurer object to measure the widgets.
314      */
horizontalSolvingPass(int level, ConstraintWidget layout, BasicMeasure.Measurer measurer, boolean isRtl)315     private static void horizontalSolvingPass(int level,
316             ConstraintWidget layout,
317             BasicMeasure.Measurer measurer,
318             boolean isRtl) {
319         if (EARLY_TERMINATION && layout.isHorizontalSolvingPassDone()) {
320             if (DEBUG) {
321                 System.out.println(ls(level) + "HORIZONTAL SOLVING PASS ON "
322                         + layout.getDebugName() + " ALREADY CALLED");
323             }
324             return;
325         }
326         sHcount++;
327         if (DEBUG) {
328             System.out.println(ls(level) + "HORIZONTAL SOLVING PASS ON " + layout.getDebugName());
329         }
330 
331         if (!(layout instanceof ConstraintWidgetContainer) && layout.isMeasureRequested()
332                 && canMeasure(level + 1, layout)) {
333             BasicMeasure.Measure measure = new BasicMeasure.Measure();
334             ConstraintWidgetContainer.measure(level + 1, layout,
335                     measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
336         }
337 
338         ConstraintAnchor left = layout.getAnchor(ConstraintAnchor.Type.LEFT);
339         ConstraintAnchor right = layout.getAnchor(ConstraintAnchor.Type.RIGHT);
340         int l = left.getFinalValue();
341         int r = right.getFinalValue();
342 
343         if (left.getDependents() != null && left.hasFinalValue()) {
344             for (ConstraintAnchor first : left.getDependents()) {
345                 ConstraintWidget widget = first.mOwner;
346                 int x1 = 0;
347                 int x2 = 0;
348                 boolean canMeasure = canMeasure(level + 1, widget);
349                 if (widget.isMeasureRequested() && canMeasure) {
350                     BasicMeasure.Measure measure = new BasicMeasure.Measure();
351                     ConstraintWidgetContainer.measure(level + 1, widget,
352                             measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
353                 }
354 
355                 boolean bothConnected = (first == widget.mLeft && widget.mRight.mTarget != null
356                         && widget.mRight.mTarget.hasFinalValue())
357                         || (first == widget.mRight && widget.mLeft.mTarget != null
358                         && widget.mLeft.mTarget.hasFinalValue());
359                 if (widget.getHorizontalDimensionBehaviour()
360                         != ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT || canMeasure) {
361                     if (widget.isMeasureRequested()) {
362                         // Widget needs to be measured
363                         if (DEBUG) {
364                             System.out.println(ls(level + 1) + "(L) We didn't measure "
365                                     + widget.getDebugName() + ", let's bail");
366                         }
367                         continue;
368                     }
369                     if (first == widget.mLeft && widget.mRight.mTarget == null) {
370                         x1 = l + widget.mLeft.getMargin();
371                         x2 = x1 + widget.getWidth();
372                         widget.setFinalHorizontal(x1, x2);
373                         horizontalSolvingPass(level + 1, widget, measurer, isRtl);
374                     } else if (first == widget.mRight && widget.mLeft.mTarget == null) {
375                         x2 = l - widget.mRight.getMargin();
376                         x1 = x2 - widget.getWidth();
377                         widget.setFinalHorizontal(x1, x2);
378                         horizontalSolvingPass(level + 1, widget, measurer, isRtl);
379                     } else if (bothConnected && !widget.isInHorizontalChain()) {
380                         solveHorizontalCenterConstraints(level + 1, measurer, widget, isRtl);
381                     } else if (APPLY_MATCH_PARENT && widget.getHorizontalDimensionBehaviour()
382                             == ConstraintWidget.DimensionBehaviour.MATCH_PARENT) {
383                         widget.setFinalHorizontal(0, widget.getWidth());
384                         horizontalSolvingPass(level + 1, widget, measurer, isRtl);
385                     }
386                 } else if (widget.getHorizontalDimensionBehaviour()
387                         == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
388                         && widget.mMatchConstraintMaxWidth >= 0
389                         && widget.mMatchConstraintMinWidth >= 0
390                         && (widget.getVisibility() == ConstraintWidget.GONE
391                         || ((widget.mMatchConstraintDefaultWidth
392                         == ConstraintWidget.MATCH_CONSTRAINT_SPREAD)
393                         && widget.getDimensionRatio() == 0))
394                         && !widget.isInHorizontalChain() && !widget.isInVirtualLayout()) {
395                     if (bothConnected && !widget.isInHorizontalChain()) {
396                         solveHorizontalMatchConstraint(level + 1, layout, measurer, widget, isRtl);
397                     }
398                 }
399             }
400         }
401         if (layout instanceof Guideline) {
402             return;
403         }
404         if (right.getDependents() != null && right.hasFinalValue()) {
405             for (ConstraintAnchor first : right.getDependents()) {
406                 ConstraintWidget widget = first.mOwner;
407                 boolean canMeasure = canMeasure(level + 1, widget);
408                 if (widget.isMeasureRequested() && canMeasure) {
409                     BasicMeasure.Measure measure = new BasicMeasure.Measure();
410                     ConstraintWidgetContainer.measure(level + 1, widget,
411                             measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
412                 }
413 
414                 int x1 = 0;
415                 int x2 = 0;
416                 boolean bothConnected = (first == widget.mLeft && widget.mRight.mTarget != null
417                         && widget.mRight.mTarget.hasFinalValue())
418                         || (first == widget.mRight && widget.mLeft.mTarget != null
419                         && widget.mLeft.mTarget.hasFinalValue());
420                 if (widget.getHorizontalDimensionBehaviour()
421                         != ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT || canMeasure) {
422                     if (widget.isMeasureRequested()) {
423                         // Widget needs to be measured
424                         if (DEBUG) {
425                             System.out.println(ls(level + 1) + "(R) We didn't measure "
426                                     + widget.getDebugName() + ", le'ts bail");
427                         }
428                         continue;
429                     }
430                     if (first == widget.mLeft && widget.mRight.mTarget == null) {
431                         x1 = r + widget.mLeft.getMargin();
432                         x2 = x1 + widget.getWidth();
433                         widget.setFinalHorizontal(x1, x2);
434                         horizontalSolvingPass(level + 1, widget, measurer, isRtl);
435                     } else if (first == widget.mRight && widget.mLeft.mTarget == null) {
436                         x2 = r - widget.mRight.getMargin();
437                         x1 = x2 - widget.getWidth();
438                         widget.setFinalHorizontal(x1, x2);
439                         horizontalSolvingPass(level + 1, widget, measurer, isRtl);
440                     } else if (bothConnected && !widget.isInHorizontalChain()) {
441                         solveHorizontalCenterConstraints(level + 1, measurer, widget, isRtl);
442                     }
443                 } else if (widget.getHorizontalDimensionBehaviour()
444                         == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
445                         && widget.mMatchConstraintMaxWidth >= 0
446                         && widget.mMatchConstraintMinWidth >= 0
447                         && (widget.getVisibility() == ConstraintWidget.GONE
448                         || ((widget.mMatchConstraintDefaultWidth
449                         == ConstraintWidget.MATCH_CONSTRAINT_SPREAD)
450                         && widget.getDimensionRatio() == 0))
451                         && !widget.isInHorizontalChain() && !widget.isInVirtualLayout()) {
452                     if (bothConnected && !widget.isInHorizontalChain()) {
453                         solveHorizontalMatchConstraint(level + 1, layout, measurer, widget, isRtl);
454                     }
455                 }
456             }
457         }
458         layout.markHorizontalSolvingPassDone();
459     }
460 
461     /**
462      * Does an vertical solving pass for the given widget. This will walk through the widget's
463      * vertical dependencies and if they can be resolved directly, do so.
464      *
465      * @param layout   the widget we want to solve the dependencies
466      * @param measurer the measurer object to measure the widgets.
467      */
verticalSolvingPass(int level, ConstraintWidget layout, BasicMeasure.Measurer measurer)468     private static void verticalSolvingPass(int level,
469             ConstraintWidget layout,
470             BasicMeasure.Measurer measurer) {
471         if (EARLY_TERMINATION && layout.isVerticalSolvingPassDone()) {
472             if (DEBUG) {
473                 System.out.println(ls(level) + "VERTICAL SOLVING PASS ON "
474                         + layout.getDebugName() + " ALREADY CALLED");
475             }
476             return;
477         }
478         sVcount++;
479         if (DEBUG) {
480             System.out.println(ls(level) + "VERTICAL SOLVING PASS ON " + layout.getDebugName());
481         }
482 
483         if (!(layout instanceof ConstraintWidgetContainer)
484                 && layout.isMeasureRequested() && canMeasure(level + 1, layout)) {
485             BasicMeasure.Measure measure = new BasicMeasure.Measure();
486             ConstraintWidgetContainer.measure(level + 1, layout,
487                     measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
488         }
489 
490         ConstraintAnchor top = layout.getAnchor(ConstraintAnchor.Type.TOP);
491         ConstraintAnchor bottom = layout.getAnchor(ConstraintAnchor.Type.BOTTOM);
492         int t = top.getFinalValue();
493         int b = bottom.getFinalValue();
494 
495         if (top.getDependents() != null && top.hasFinalValue()) {
496             for (ConstraintAnchor first : top.getDependents()) {
497                 ConstraintWidget widget = first.mOwner;
498                 int y1 = 0;
499                 int y2 = 0;
500                 boolean canMeasure = canMeasure(level + 1, widget);
501                 if (widget.isMeasureRequested() && canMeasure) {
502                     BasicMeasure.Measure measure = new BasicMeasure.Measure();
503                     ConstraintWidgetContainer.measure(level + 1, widget,
504                             measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
505                 }
506 
507                 boolean bothConnected = (first == widget.mTop && widget.mBottom.mTarget != null
508                         && widget.mBottom.mTarget.hasFinalValue())
509                         || (first == widget.mBottom && widget.mTop.mTarget != null
510                         && widget.mTop.mTarget.hasFinalValue());
511                 if (widget.getVerticalDimensionBehaviour()
512                         != ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
513                         || canMeasure) {
514                     if (widget.isMeasureRequested()) {
515                         // Widget needs to be measured
516                         if (DEBUG) {
517                             System.out.println(ls(level + 1) + "(T) We didn't measure "
518                                     + widget.getDebugName() + ", le'ts bail");
519                         }
520                         continue;
521                     }
522                     if (first == widget.mTop && widget.mBottom.mTarget == null) {
523                         y1 = t + widget.mTop.getMargin();
524                         y2 = y1 + widget.getHeight();
525                         widget.setFinalVertical(y1, y2);
526                         verticalSolvingPass(level + 1, widget, measurer);
527                     } else if (first == widget.mBottom && widget.mTop.mTarget == null) {
528                         y2 = t - widget.mBottom.getMargin();
529                         y1 = y2 - widget.getHeight();
530                         widget.setFinalVertical(y1, y2);
531                         verticalSolvingPass(level + 1, widget, measurer);
532                     } else if (bothConnected && !widget.isInVerticalChain()) {
533                         solveVerticalCenterConstraints(level + 1, measurer, widget);
534                     } else if (APPLY_MATCH_PARENT && widget.getVerticalDimensionBehaviour()
535                             == ConstraintWidget.DimensionBehaviour.MATCH_PARENT) {
536                         widget.setFinalVertical(0, widget.getHeight());
537                         verticalSolvingPass(level + 1, widget, measurer);
538                     }
539                 } else if (widget.getVerticalDimensionBehaviour()
540                         == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
541                         && widget.mMatchConstraintMaxHeight >= 0
542                         && widget.mMatchConstraintMinHeight >= 0
543                         && (widget.getVisibility() == ConstraintWidget.GONE
544                         || ((widget.mMatchConstraintDefaultHeight
545                         == ConstraintWidget.MATCH_CONSTRAINT_SPREAD)
546                         && widget.getDimensionRatio() == 0))
547                         && !widget.isInVerticalChain() && !widget.isInVirtualLayout()) {
548                     if (bothConnected && !widget.isInVerticalChain()) {
549                         solveVerticalMatchConstraint(level + 1, layout, measurer, widget);
550                     }
551                 }
552             }
553         }
554         if (layout instanceof Guideline) {
555             return;
556         }
557         if (bottom.getDependents() != null && bottom.hasFinalValue()) {
558             for (ConstraintAnchor first : bottom.getDependents()) {
559                 ConstraintWidget widget = first.mOwner;
560                 boolean canMeasure = canMeasure(level + 1, widget);
561                 if (widget.isMeasureRequested() && canMeasure) {
562                     BasicMeasure.Measure measure = new BasicMeasure.Measure();
563                     ConstraintWidgetContainer.measure(level + 1, widget,
564                             measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
565                 }
566 
567                 int y1 = 0;
568                 int y2 = 0;
569                 boolean bothConnected = (first == widget.mTop && widget.mBottom.mTarget != null
570                         && widget.mBottom.mTarget.hasFinalValue())
571                         || (first == widget.mBottom && widget.mTop.mTarget != null
572                         && widget.mTop.mTarget.hasFinalValue());
573                 if (widget.getVerticalDimensionBehaviour()
574                         != ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT || canMeasure) {
575                     if (widget.isMeasureRequested()) {
576                         // Widget needs to be measured
577                         if (DEBUG) {
578                             System.out.println(ls(level + 1) + "(B) We didn't measure "
579                                     + widget.getDebugName() + ", le'ts bail");
580                         }
581                         continue;
582                     }
583                     if (first == widget.mTop && widget.mBottom.mTarget == null) {
584                         y1 = b + widget.mTop.getMargin();
585                         y2 = y1 + widget.getHeight();
586                         widget.setFinalVertical(y1, y2);
587                         verticalSolvingPass(level + 1, widget, measurer);
588                     } else if (first == widget.mBottom && widget.mTop.mTarget == null) {
589                         y2 = b - widget.mBottom.getMargin();
590                         y1 = y2 - widget.getHeight();
591                         widget.setFinalVertical(y1, y2);
592                         verticalSolvingPass(level + 1, widget, measurer);
593                     } else if (bothConnected && !widget.isInVerticalChain()) {
594                         solveVerticalCenterConstraints(level + 1, measurer, widget);
595                     }
596                 } else if (widget.getVerticalDimensionBehaviour()
597                         == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
598                         && widget.mMatchConstraintMaxHeight >= 0
599                         && widget.mMatchConstraintMinHeight >= 0
600                         && (widget.getVisibility() == ConstraintWidget.GONE
601                         || ((widget.mMatchConstraintDefaultHeight
602                         == ConstraintWidget.MATCH_CONSTRAINT_SPREAD)
603                         && widget.getDimensionRatio() == 0))
604                         && !widget.isInVerticalChain() && !widget.isInVirtualLayout()) {
605                     if (bothConnected && !widget.isInVerticalChain()) {
606                         solveVerticalMatchConstraint(level + 1, layout, measurer, widget);
607                     }
608                 }
609             }
610         }
611 
612         ConstraintAnchor baseline = layout.getAnchor(ConstraintAnchor.Type.BASELINE);
613         if (baseline.getDependents() != null && baseline.hasFinalValue()) {
614             int baselineValue = baseline.getFinalValue();
615             for (ConstraintAnchor first : baseline.getDependents()) {
616                 ConstraintWidget widget = first.mOwner;
617                 boolean canMeasure = canMeasure(level + 1, widget);
618                 if (widget.isMeasureRequested() && canMeasure) {
619                     BasicMeasure.Measure measure = new BasicMeasure.Measure();
620                     ConstraintWidgetContainer.measure(level + 1, widget,
621                             measurer, measure, BasicMeasure.Measure.SELF_DIMENSIONS);
622                 }
623                 if (widget.getVerticalDimensionBehaviour()
624                         != ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT || canMeasure) {
625                     if (widget.isMeasureRequested()) {
626                         // Widget needs to be measured
627                         if (DEBUG) {
628                             System.out.println(ls(level + 1) + "(B) We didn't measure "
629                                     + widget.getDebugName() + ", le'ts bail");
630                         }
631                         continue;
632                     }
633                     if (first == widget.mBaseline) {
634                         widget.setFinalBaseline(baselineValue + first.getMargin());
635                         verticalSolvingPass(level + 1, widget, measurer);
636                     }
637                 }
638             }
639         }
640         layout.markVerticalSolvingPassDone();
641     }
642 
643     /**
644      * Solve horizontal centering constraints
645      */
solveHorizontalCenterConstraints(int level, BasicMeasure.Measurer measurer, ConstraintWidget widget, boolean isRtl)646     private static void solveHorizontalCenterConstraints(int level,
647             BasicMeasure.Measurer measurer,
648             ConstraintWidget widget,
649             boolean isRtl) {
650         // TODO: Handle match constraints here or before calling this
651         int x1;
652         int x2;
653         float bias = widget.getHorizontalBiasPercent();
654         int start = widget.mLeft.mTarget.getFinalValue();
655         int end = widget.mRight.mTarget.getFinalValue();
656         int s1 = start + widget.mLeft.getMargin();
657         int s2 = end - widget.mRight.getMargin();
658         if (start == end) {
659             bias = 0.5f;
660             s1 = start;
661             s2 = end;
662         }
663         int width = widget.getWidth();
664         int distance = s2 - s1 - width;
665         if (s1 > s2) {
666             distance = s1 - s2 - width;
667         }
668         int d1;
669         if (distance > 0) {
670             d1 = (int) (0.5f + bias * distance);
671         } else {
672             d1 = (int) (bias * distance);
673         }
674         x1 = s1 + d1;
675         x2 = x1 + width;
676         if (s1 > s2) {
677             x1 = s1 + d1;
678             x2 = x1 - width;
679         }
680         widget.setFinalHorizontal(x1, x2);
681         horizontalSolvingPass(level + 1, widget, measurer, isRtl);
682     }
683 
684     /**
685      * Solve vertical centering constraints
686      */
solveVerticalCenterConstraints(int level, BasicMeasure.Measurer measurer, ConstraintWidget widget)687     private static void solveVerticalCenterConstraints(int level,
688             BasicMeasure.Measurer measurer,
689             ConstraintWidget widget) {
690         // TODO: Handle match constraints here or before calling this
691         int y1;
692         int y2;
693         float bias = widget.getVerticalBiasPercent();
694         int start = widget.mTop.mTarget.getFinalValue();
695         int end = widget.mBottom.mTarget.getFinalValue();
696         int s1 = start + widget.mTop.getMargin();
697         int s2 = end - widget.mBottom.getMargin();
698         if (start == end) {
699             bias = 0.5f;
700             s1 = start;
701             s2 = end;
702         }
703         int height = widget.getHeight();
704         int distance = s2 - s1 - height;
705         if (s1 > s2) {
706             distance = s1 - s2 - height;
707         }
708         int d1;
709         if (distance > 0) {
710             d1 = (int) (0.5f + bias * distance);
711         } else {
712             d1 = (int) (bias * distance);
713         }
714         y1 = s1 + d1;
715         y2 = y1 + height;
716         if (s1 > s2) {
717             y1 = s1 - d1;
718             y2 = y1 - height;
719         }
720         widget.setFinalVertical(y1, y2);
721         verticalSolvingPass(level + 1, widget, measurer);
722     }
723 
724     /**
725      * Solve horizontal match constraints
726      */
solveHorizontalMatchConstraint(int level, ConstraintWidget layout, BasicMeasure.Measurer measurer, ConstraintWidget widget, boolean isRtl)727     private static void solveHorizontalMatchConstraint(int level,
728             ConstraintWidget layout,
729             BasicMeasure.Measurer measurer,
730             ConstraintWidget widget,
731             boolean isRtl) {
732         int x1;
733         int x2;
734         float bias = widget.getHorizontalBiasPercent();
735         int s1 = widget.mLeft.mTarget.getFinalValue() + widget.mLeft.getMargin();
736         int s2 = widget.mRight.mTarget.getFinalValue() - widget.mRight.getMargin();
737         if (s2 >= s1) {
738             int width = widget.getWidth();
739             if (widget.getVisibility() != ConstraintWidget.GONE) {
740                 if (widget.mMatchConstraintDefaultWidth
741                         == ConstraintWidget.MATCH_CONSTRAINT_PERCENT) {
742                     int parentWidth = 0;
743                     if (layout instanceof ConstraintWidgetContainer) {
744                         parentWidth = layout.getWidth();
745                     } else {
746                         parentWidth = layout.getParent().getWidth();
747                     }
748                     width = (int) (0.5f * widget.getHorizontalBiasPercent() * parentWidth);
749                 } else if (widget.mMatchConstraintDefaultWidth
750                         == ConstraintWidget.MATCH_CONSTRAINT_SPREAD) {
751                     width = s2 - s1;
752                 }
753                 width = Math.max(widget.mMatchConstraintMinWidth, width);
754                 if (widget.mMatchConstraintMaxWidth > 0) {
755                     width = Math.min(widget.mMatchConstraintMaxWidth, width);
756                 }
757             }
758             int distance = s2 - s1 - width;
759             int d1 = (int) (0.5f + bias * distance);
760             x1 = s1 + d1;
761             x2 = x1 + width;
762             widget.setFinalHorizontal(x1, x2);
763             horizontalSolvingPass(level + 1, widget, measurer, isRtl);
764         }
765     }
766 
767     /**
768      * Solve vertical match constraints
769      */
solveVerticalMatchConstraint(int level, ConstraintWidget layout, BasicMeasure.Measurer measurer, ConstraintWidget widget)770     private static void solveVerticalMatchConstraint(int level,
771             ConstraintWidget layout,
772             BasicMeasure.Measurer measurer,
773             ConstraintWidget widget) {
774         int y1;
775         int y2;
776         float bias = widget.getVerticalBiasPercent();
777         int s1 = widget.mTop.mTarget.getFinalValue() + widget.mTop.getMargin();
778         int s2 = widget.mBottom.mTarget.getFinalValue() - widget.mBottom.getMargin();
779         if (s2 >= s1) {
780             int height = widget.getHeight();
781             if (widget.getVisibility() != ConstraintWidget.GONE) {
782                 if (widget.mMatchConstraintDefaultHeight
783                         == ConstraintWidget.MATCH_CONSTRAINT_PERCENT) {
784                     int parentHeight = 0;
785                     if (layout instanceof ConstraintWidgetContainer) {
786                         parentHeight = layout.getHeight();
787                     } else {
788                         parentHeight = layout.getParent().getHeight();
789                     }
790                     height = (int) (0.5f * bias * parentHeight);
791                 } else if (widget.mMatchConstraintDefaultHeight
792                         == ConstraintWidget.MATCH_CONSTRAINT_SPREAD) {
793                     height = s2 - s1;
794                 }
795                 height = Math.max(widget.mMatchConstraintMinHeight, height);
796                 if (widget.mMatchConstraintMaxHeight > 0) {
797                     height = Math.min(widget.mMatchConstraintMaxHeight, height);
798                 }
799             }
800             int distance = s2 - s1 - height;
801             int d1 = (int) (0.5f + bias * distance);
802             y1 = s1 + d1;
803             y2 = y1 + height;
804             widget.setFinalVertical(y1, y2);
805             verticalSolvingPass(level + 1, widget, measurer);
806         }
807     }
808 
809     /**
810      * Returns true if the dimensions of the given widget are computable directly
811      *
812      * @param layout the widget to check
813      * @return true if both dimensions are knowable by a single measure pass
814      */
canMeasure(int level, ConstraintWidget layout)815     private static boolean canMeasure(int level, ConstraintWidget layout) {
816         ConstraintWidget.DimensionBehaviour horizontalBehaviour =
817                 layout.getHorizontalDimensionBehaviour();
818         ConstraintWidget.DimensionBehaviour verticalBehaviour =
819                 layout.getVerticalDimensionBehaviour();
820         ConstraintWidgetContainer parent = layout.getParent() != null
821                 ? (ConstraintWidgetContainer) layout.getParent() : null;
822         boolean isParentHorizontalFixed = parent != null && parent.getHorizontalDimensionBehaviour()
823                 == ConstraintWidget.DimensionBehaviour.FIXED;
824         boolean isParentVerticalFixed = parent != null && parent.getVerticalDimensionBehaviour()
825                 == ConstraintWidget.DimensionBehaviour.FIXED;
826         boolean isHorizontalFixed = horizontalBehaviour == ConstraintWidget.DimensionBehaviour.FIXED
827                 || layout.isResolvedHorizontally()
828                 || (APPLY_MATCH_PARENT && horizontalBehaviour
829                 == ConstraintWidget.DimensionBehaviour.MATCH_PARENT && isParentHorizontalFixed)
830                 || horizontalBehaviour == ConstraintWidget.DimensionBehaviour.WRAP_CONTENT
831                 || (horizontalBehaviour == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
832                 && layout.mMatchConstraintDefaultWidth
833                 == ConstraintWidget.MATCH_CONSTRAINT_SPREAD
834                 && layout.mDimensionRatio == 0
835                 && layout.hasDanglingDimension(HORIZONTAL))
836                 || (horizontalBehaviour == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
837                 && layout.mMatchConstraintDefaultWidth == MATCH_CONSTRAINT_WRAP
838                 && layout.hasResolvedTargets(HORIZONTAL, layout.getWidth()));
839         boolean isVerticalFixed = verticalBehaviour == ConstraintWidget.DimensionBehaviour.FIXED
840                 || layout.isResolvedVertically()
841                 || (APPLY_MATCH_PARENT && verticalBehaviour
842                 == ConstraintWidget.DimensionBehaviour.MATCH_PARENT && isParentVerticalFixed)
843                 || verticalBehaviour == ConstraintWidget.DimensionBehaviour.WRAP_CONTENT
844                 || (verticalBehaviour == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
845                 && layout.mMatchConstraintDefaultHeight
846                 == ConstraintWidget.MATCH_CONSTRAINT_SPREAD
847                 && layout.mDimensionRatio == 0
848                 && layout.hasDanglingDimension(ConstraintWidget.VERTICAL))
849                 || (verticalBehaviour == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT
850                 && layout.mMatchConstraintDefaultHeight == MATCH_CONSTRAINT_WRAP
851                 && layout.hasResolvedTargets(VERTICAL, layout.getHeight()));
852         if (layout.mDimensionRatio > 0 && (isHorizontalFixed || isVerticalFixed)) {
853             return true;
854         }
855         if (DEBUG) {
856             System.out.println(ls(level) + "can measure " + layout.getDebugName() + " ? "
857                     + (isHorizontalFixed && isVerticalFixed) + "  [ "
858                     + isHorizontalFixed + " (horiz " + horizontalBehaviour + ") & "
859                     + isVerticalFixed + " (vert " + verticalBehaviour + ") ]");
860         }
861         return isHorizontalFixed && isVerticalFixed;
862     }
863 
864     /**
865      * Try to directly resolve the chain
866      *
867      * @return true if fully resolved
868      */
solveChain(ConstraintWidgetContainer container, LinearSystem system, int orientation, int offset, ChainHead chainHead, boolean isChainSpread, boolean isChainSpreadInside, boolean isChainPacked)869     public static boolean solveChain(ConstraintWidgetContainer container, LinearSystem system,
870             int orientation, int offset, ChainHead chainHead,
871             boolean isChainSpread, boolean isChainSpreadInside,
872             boolean isChainPacked) {
873         if (LinearSystem.FULL_DEBUG) {
874             System.out.println("\n### SOLVE CHAIN ###");
875         }
876         if (isChainPacked) {
877             return false;
878         }
879         if (orientation == HORIZONTAL) {
880             if (!container.isResolvedHorizontally()) {
881                 return false;
882             }
883         } else {
884             if (!container.isResolvedVertically()) {
885                 return false;
886             }
887         }
888         int level = 0; // nested level (used for debugging)
889         boolean isRtl = container.isRtl();
890 
891         ConstraintWidget first = chainHead.getFirst();
892         ConstraintWidget last = chainHead.getLast();
893         ConstraintWidget firstVisibleWidget = chainHead.getFirstVisibleWidget();
894         ConstraintWidget lastVisibleWidget = chainHead.getLastVisibleWidget();
895         ConstraintWidget head = chainHead.getHead();
896 
897         ConstraintWidget widget = first;
898         ConstraintWidget next;
899         boolean done = false;
900 
901         ConstraintAnchor begin = first.mListAnchors[offset];
902         ConstraintAnchor end = last.mListAnchors[offset + 1];
903         if (begin.mTarget == null || end.mTarget == null) {
904             return false;
905         }
906         if (!begin.mTarget.hasFinalValue() || !end.mTarget.hasFinalValue()) {
907             return false;
908         }
909 
910         if (firstVisibleWidget == null || lastVisibleWidget == null) {
911             return false;
912         }
913 
914         int startPoint = begin.mTarget.getFinalValue()
915                 + firstVisibleWidget.mListAnchors[offset].getMargin();
916         int endPoint = end.mTarget.getFinalValue()
917                 - lastVisibleWidget.mListAnchors[offset + 1].getMargin();
918 
919         int distance = endPoint - startPoint;
920         if (distance <= 0) {
921             return false;
922         }
923         int totalSize = 0;
924         BasicMeasure.Measure measure = new BasicMeasure.Measure();
925 
926         int numWidgets = 0;
927         int numVisibleWidgets = 0;
928 
929         while (!done) {
930             boolean canMeasure = canMeasure(level + 1, widget);
931             if (!canMeasure) {
932                 return false;
933             }
934             if (widget.mListDimensionBehaviors[orientation]
935                     == ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT) {
936                 return false;
937             }
938 
939             if (widget.isMeasureRequested()) {
940                 ConstraintWidgetContainer.measure(level + 1, widget,
941                         container.getMeasurer(), measure, BasicMeasure.Measure.SELF_DIMENSIONS);
942             }
943 
944             totalSize += widget.mListAnchors[offset].getMargin();
945             if (orientation == HORIZONTAL) {
946                 totalSize += +widget.getWidth();
947             } else {
948                 totalSize += widget.getHeight();
949             }
950             totalSize += widget.mListAnchors[offset + 1].getMargin();
951 
952             numWidgets++;
953             if (widget.getVisibility() != ConstraintWidget.GONE) {
954                 numVisibleWidgets++;
955             }
956 
957 
958             // go to the next widget
959             ConstraintAnchor nextAnchor = widget.mListAnchors[offset + 1].mTarget;
960             if (nextAnchor != null) {
961                 next = nextAnchor.mOwner;
962                 if (next.mListAnchors[offset].mTarget == null
963                         || next.mListAnchors[offset].mTarget.mOwner != widget) {
964                     next = null;
965                 }
966             } else {
967                 next = null;
968             }
969             if (next != null) {
970                 widget = next;
971             } else {
972                 done = true;
973             }
974         }
975 
976         if (numVisibleWidgets == 0) {
977             return false;
978         }
979 
980         if (numVisibleWidgets != numWidgets) {
981             return false;
982         }
983 
984         if (distance < totalSize) {
985             return false;
986         }
987 
988         int gap = distance - totalSize;
989         if (isChainSpread) {
990             gap = gap / (numVisibleWidgets + 1);
991         } else if (isChainSpreadInside) {
992             if (numVisibleWidgets > 2) {
993                 gap = gap / numVisibleWidgets - 1;
994             }
995         }
996 
997         if (numVisibleWidgets == 1) {
998             float bias;
999             if (orientation == ConstraintWidget.HORIZONTAL) {
1000                 bias = head.getHorizontalBiasPercent();
1001             } else {
1002                 bias = head.getVerticalBiasPercent();
1003             }
1004             int p1 = (int) (0.5f + startPoint + gap * bias);
1005             if (orientation == HORIZONTAL) {
1006                 firstVisibleWidget.setFinalHorizontal(p1, p1 + firstVisibleWidget.getWidth());
1007             } else {
1008                 firstVisibleWidget.setFinalVertical(p1, p1 + firstVisibleWidget.getHeight());
1009             }
1010             Direct.horizontalSolvingPass(level + 1,
1011                     firstVisibleWidget, container.getMeasurer(), isRtl);
1012             return true;
1013         }
1014 
1015         if (isChainSpread) {
1016             done = false;
1017 
1018             int current = startPoint + gap;
1019             widget = first;
1020             while (!done) {
1021                 if (widget.getVisibility() == GONE) {
1022                     if (orientation == HORIZONTAL) {
1023                         widget.setFinalHorizontal(current, current);
1024                         Direct.horizontalSolvingPass(level + 1,
1025                                 widget, container.getMeasurer(), isRtl);
1026                     } else {
1027                         widget.setFinalVertical(current, current);
1028                         Direct.verticalSolvingPass(level + 1, widget, container.getMeasurer());
1029                     }
1030                 } else {
1031                     current += widget.mListAnchors[offset].getMargin();
1032                     if (orientation == HORIZONTAL) {
1033                         widget.setFinalHorizontal(current, current + widget.getWidth());
1034                         Direct.horizontalSolvingPass(level + 1,
1035                                 widget, container.getMeasurer(), isRtl);
1036                         current += widget.getWidth();
1037                     } else {
1038                         widget.setFinalVertical(current, current + widget.getHeight());
1039                         Direct.verticalSolvingPass(level + 1, widget, container.getMeasurer());
1040                         current += widget.getHeight();
1041                     }
1042                     current += widget.mListAnchors[offset + 1].getMargin();
1043                     current += gap;
1044                 }
1045 
1046                 widget.addToSolver(system, false);
1047 
1048                 // go to the next widget
1049                 ConstraintAnchor nextAnchor = widget.mListAnchors[offset + 1].mTarget;
1050                 if (nextAnchor != null) {
1051                     next = nextAnchor.mOwner;
1052                     if (next.mListAnchors[offset].mTarget == null
1053                             || next.mListAnchors[offset].mTarget.mOwner != widget) {
1054                         next = null;
1055                     }
1056                 } else {
1057                     next = null;
1058                 }
1059                 if (next != null) {
1060                     widget = next;
1061                 } else {
1062                     done = true;
1063                 }
1064             }
1065         } else if (isChainSpreadInside) {
1066             if (numVisibleWidgets == 2) {
1067                 if (orientation == HORIZONTAL) {
1068                     firstVisibleWidget.setFinalHorizontal(startPoint,
1069                             startPoint + firstVisibleWidget.getWidth());
1070                     lastVisibleWidget.setFinalHorizontal(endPoint - lastVisibleWidget.getWidth(),
1071                             endPoint);
1072                     Direct.horizontalSolvingPass(level + 1,
1073                             firstVisibleWidget, container.getMeasurer(), isRtl);
1074                     Direct.horizontalSolvingPass(level + 1,
1075                             lastVisibleWidget, container.getMeasurer(), isRtl);
1076                 } else {
1077                     firstVisibleWidget.setFinalVertical(startPoint,
1078                             startPoint + firstVisibleWidget.getHeight());
1079                     lastVisibleWidget.setFinalVertical(endPoint - lastVisibleWidget.getHeight(),
1080                             endPoint);
1081                     Direct.verticalSolvingPass(level + 1,
1082                             firstVisibleWidget, container.getMeasurer());
1083                     Direct.verticalSolvingPass(level + 1,
1084                             lastVisibleWidget, container.getMeasurer());
1085                 }
1086                 return true;
1087             }
1088             return false;
1089         }
1090         return true;
1091     }
1092 }
1093