1 /*
2  * Copyright (C) 2019 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 
17 package androidx.constraintlayout.core.widgets.analyzer;
18 
19 import static androidx.constraintlayout.core.widgets.ConstraintWidget.DimensionBehaviour.FIXED;
20 import static androidx.constraintlayout.core.widgets.ConstraintWidget.DimensionBehaviour.MATCH_CONSTRAINT;
21 import static androidx.constraintlayout.core.widgets.ConstraintWidget.DimensionBehaviour.MATCH_PARENT;
22 import static androidx.constraintlayout.core.widgets.ConstraintWidget.DimensionBehaviour.WRAP_CONTENT;
23 import static androidx.constraintlayout.core.widgets.ConstraintWidget.GONE;
24 import static androidx.constraintlayout.core.widgets.ConstraintWidget.HORIZONTAL;
25 import static androidx.constraintlayout.core.widgets.ConstraintWidget.MATCH_CONSTRAINT_PERCENT;
26 import static androidx.constraintlayout.core.widgets.ConstraintWidget.MATCH_CONSTRAINT_RATIO;
27 import static androidx.constraintlayout.core.widgets.ConstraintWidget.MATCH_CONSTRAINT_SPREAD;
28 import static androidx.constraintlayout.core.widgets.ConstraintWidget.MATCH_CONSTRAINT_WRAP;
29 import static androidx.constraintlayout.core.widgets.ConstraintWidget.UNKNOWN;
30 import static androidx.constraintlayout.core.widgets.ConstraintWidget.VERTICAL;
31 
32 import androidx.constraintlayout.core.widgets.Barrier;
33 import androidx.constraintlayout.core.widgets.ConstraintWidget;
34 import androidx.constraintlayout.core.widgets.ConstraintWidgetContainer;
35 import androidx.constraintlayout.core.widgets.Guideline;
36 import androidx.constraintlayout.core.widgets.HelperWidget;
37 
38 import java.util.ArrayList;
39 import java.util.HashSet;
40 
41 public class DependencyGraph {
42     private static final boolean USE_GROUPS = true;
43     private ConstraintWidgetContainer mWidgetcontainer;
44     private boolean mNeedBuildGraph = true;
45     private boolean mNeedRedoMeasures = true;
46     private ConstraintWidgetContainer mContainer;
47     private ArrayList<WidgetRun> mRuns = new ArrayList<>();
48     private static final boolean DEBUG = false;
49 
50     // TODO: Unused, should we delete?
51     @SuppressWarnings("unused") private ArrayList<RunGroup> mRunGroups = new ArrayList<>();
52 
DependencyGraph(ConstraintWidgetContainer container)53     public DependencyGraph(ConstraintWidgetContainer container) {
54         this.mWidgetcontainer = container;
55         mContainer = container;
56     }
57 
58     private BasicMeasure.Measurer mMeasurer = null;
59     private BasicMeasure.Measure mMeasure = new BasicMeasure.Measure();
60 
setMeasurer(BasicMeasure.Measurer measurer)61     public void setMeasurer(BasicMeasure.Measurer measurer) {
62         mMeasurer = measurer;
63     }
64 
computeWrap(ConstraintWidgetContainer container, int orientation)65     private int computeWrap(ConstraintWidgetContainer container, int orientation) {
66         final int count = mGroups.size();
67         long wrapSize = 0;
68         for (int i = 0; i < count; i++) {
69             RunGroup run = mGroups.get(i);
70             long size = run.computeWrapSize(container, orientation);
71             wrapSize = Math.max(wrapSize, size);
72         }
73         return (int) wrapSize;
74     }
75 
76     /**
77      * Find and mark terminal widgets (trailing widgets) -- they are the only
78      * ones we need to care for wrap_content checks
79      */
defineTerminalWidgets(ConstraintWidget.DimensionBehaviour horizontalBehavior, ConstraintWidget.DimensionBehaviour verticalBehavior)80     public void defineTerminalWidgets(ConstraintWidget.DimensionBehaviour horizontalBehavior,
81             ConstraintWidget.DimensionBehaviour verticalBehavior) {
82         if (mNeedBuildGraph) {
83             buildGraph();
84 
85             if (USE_GROUPS) {
86                 boolean hasBarrier = false;
87                 for (ConstraintWidget widget : mWidgetcontainer.mChildren) {
88                     widget.isTerminalWidget[HORIZONTAL] = true;
89                     widget.isTerminalWidget[VERTICAL] = true;
90                     if (widget instanceof Barrier) {
91                         hasBarrier = true;
92                     }
93                 }
94                 if (!hasBarrier) {
95                     for (RunGroup group : mGroups) {
96                         group.defineTerminalWidgets(horizontalBehavior == WRAP_CONTENT,
97                                 verticalBehavior == WRAP_CONTENT);
98                     }
99                 }
100             }
101         }
102     }
103 
104     /**
105      * Try to measure the layout by solving the graph of constraints directly
106      *
107      * @param optimizeWrap use the wrap_content optimizer
108      * @return true if all widgets have been resolved
109      */
directMeasure(boolean optimizeWrap)110     public boolean directMeasure(boolean optimizeWrap) {
111         optimizeWrap &= USE_GROUPS;
112 
113         if (mNeedBuildGraph || mNeedRedoMeasures) {
114             for (ConstraintWidget widget : mWidgetcontainer.mChildren) {
115                 widget.ensureWidgetRuns();
116                 widget.measured = false;
117                 widget.mHorizontalRun.reset();
118                 widget.mVerticalRun.reset();
119             }
120             mWidgetcontainer.ensureWidgetRuns();
121             mWidgetcontainer.measured = false;
122             mWidgetcontainer.mHorizontalRun.reset();
123             mWidgetcontainer.mVerticalRun.reset();
124             mNeedRedoMeasures = false;
125         }
126 
127         boolean avoid = basicMeasureWidgets(mContainer);
128         if (avoid) {
129             return false;
130         }
131 
132         mWidgetcontainer.setX(0);
133         mWidgetcontainer.setY(0);
134 
135         ConstraintWidget.DimensionBehaviour originalHorizontalDimension =
136                 mWidgetcontainer.getDimensionBehaviour(HORIZONTAL);
137         ConstraintWidget.DimensionBehaviour originalVerticalDimension =
138                 mWidgetcontainer.getDimensionBehaviour(VERTICAL);
139 
140         if (mNeedBuildGraph) {
141             buildGraph();
142         }
143 
144         int x1 = mWidgetcontainer.getX();
145         int y1 = mWidgetcontainer.getY();
146 
147         mWidgetcontainer.mHorizontalRun.start.resolve(x1);
148         mWidgetcontainer.mVerticalRun.start.resolve(y1);
149 
150         // Let's do the easy steps first -- anything that can be immediately measured
151         // Whatever is left for the dimension will be match_constraints.
152         measureWidgets();
153 
154         // If we have to support wrap, let's see if we can compute it directly
155         if (originalHorizontalDimension == WRAP_CONTENT
156                 || originalVerticalDimension == WRAP_CONTENT) {
157             if (optimizeWrap) {
158                 for (WidgetRun run : mRuns) {
159                     if (!run.supportsWrapComputation()) {
160                         optimizeWrap = false;
161                         break;
162                     }
163                 }
164             }
165 
166             if (optimizeWrap && originalHorizontalDimension == WRAP_CONTENT) {
167                 mWidgetcontainer.setHorizontalDimensionBehaviour(FIXED);
168                 mWidgetcontainer.setWidth(computeWrap(mWidgetcontainer, HORIZONTAL));
169                 mWidgetcontainer.mHorizontalRun.mDimension.resolve(mWidgetcontainer.getWidth());
170             }
171             if (optimizeWrap && originalVerticalDimension == WRAP_CONTENT) {
172                 mWidgetcontainer.setVerticalDimensionBehaviour(FIXED);
173                 mWidgetcontainer.setHeight(computeWrap(mWidgetcontainer, VERTICAL));
174                 mWidgetcontainer.mVerticalRun.mDimension.resolve(mWidgetcontainer.getHeight());
175             }
176         }
177 
178         boolean checkRoot = false;
179 
180         // Now, depending on our own dimension behavior, we may want to solve
181         // one dimension before the other
182 
183         if (mWidgetcontainer.mListDimensionBehaviors[HORIZONTAL]
184                 == ConstraintWidget.DimensionBehaviour.FIXED
185                 || mWidgetcontainer.mListDimensionBehaviors[HORIZONTAL]
186                 == ConstraintWidget.DimensionBehaviour.MATCH_PARENT) {
187 
188             // solve horizontal dimension
189             int x2 = x1 + mWidgetcontainer.getWidth();
190             mWidgetcontainer.mHorizontalRun.end.resolve(x2);
191             mWidgetcontainer.mHorizontalRun.mDimension.resolve(x2 - x1);
192             measureWidgets();
193             if (mWidgetcontainer.mListDimensionBehaviors[VERTICAL] == FIXED
194                     || mWidgetcontainer.mListDimensionBehaviors[VERTICAL] == MATCH_PARENT) {
195                 int y2 = y1 + mWidgetcontainer.getHeight();
196                 mWidgetcontainer.mVerticalRun.end.resolve(y2);
197                 mWidgetcontainer.mVerticalRun.mDimension.resolve(y2 - y1);
198             }
199             measureWidgets();
200             checkRoot = true;
201         } else {
202             // we'll bail out to the solver...
203         }
204 
205         // Let's apply what we did resolve
206         for (WidgetRun run : mRuns) {
207             if (run.mWidget == mWidgetcontainer && !run.mResolved) {
208                 continue;
209             }
210             run.applyToWidget();
211         }
212 
213         boolean allResolved = true;
214         for (WidgetRun run : mRuns) {
215             if (!checkRoot && run.mWidget == mWidgetcontainer) {
216                 continue;
217             }
218             if (!run.start.resolved) {
219                 allResolved = false;
220                 break;
221             }
222             if (!run.end.resolved && !(run instanceof GuidelineReference)) {
223                 allResolved = false;
224                 break;
225             }
226             if (!run.mDimension.resolved
227                     && !(run instanceof ChainRun) && !(run instanceof GuidelineReference)) {
228                 allResolved = false;
229                 break;
230             }
231         }
232 
233         mWidgetcontainer.setHorizontalDimensionBehaviour(originalHorizontalDimension);
234         mWidgetcontainer.setVerticalDimensionBehaviour(originalVerticalDimension);
235 
236         return allResolved;
237     }
238 
239     // @TODO: add description
directMeasureSetup(boolean optimizeWrap)240     public boolean directMeasureSetup(boolean optimizeWrap) {
241         if (mNeedBuildGraph) {
242             for (ConstraintWidget widget : mWidgetcontainer.mChildren) {
243                 widget.ensureWidgetRuns();
244                 widget.measured = false;
245                 widget.mHorizontalRun.mDimension.resolved = false;
246                 widget.mHorizontalRun.mResolved = false;
247                 widget.mHorizontalRun.reset();
248                 widget.mVerticalRun.mDimension.resolved = false;
249                 widget.mVerticalRun.mResolved = false;
250                 widget.mVerticalRun.reset();
251             }
252             mWidgetcontainer.ensureWidgetRuns();
253             mWidgetcontainer.measured = false;
254             mWidgetcontainer.mHorizontalRun.mDimension.resolved = false;
255             mWidgetcontainer.mHorizontalRun.mResolved = false;
256             mWidgetcontainer.mHorizontalRun.reset();
257             mWidgetcontainer.mVerticalRun.mDimension.resolved = false;
258             mWidgetcontainer.mVerticalRun.mResolved = false;
259             mWidgetcontainer.mVerticalRun.reset();
260             buildGraph();
261         }
262 
263         boolean avoid = basicMeasureWidgets(mContainer);
264         if (avoid) {
265             return false;
266         }
267 
268         mWidgetcontainer.setX(0);
269         mWidgetcontainer.setY(0);
270         mWidgetcontainer.mHorizontalRun.start.resolve(0);
271         mWidgetcontainer.mVerticalRun.start.resolve(0);
272         return true;
273     }
274 
275     // @TODO: add description
directMeasureWithOrientation(boolean optimizeWrap, int orientation)276     public boolean directMeasureWithOrientation(boolean optimizeWrap, int orientation) {
277         optimizeWrap &= USE_GROUPS;
278 
279         ConstraintWidget.DimensionBehaviour originalHorizontalDimension =
280                 mWidgetcontainer.getDimensionBehaviour(HORIZONTAL);
281         ConstraintWidget.DimensionBehaviour originalVerticalDimension =
282                 mWidgetcontainer.getDimensionBehaviour(VERTICAL);
283 
284         int x1 = mWidgetcontainer.getX();
285         int y1 = mWidgetcontainer.getY();
286 
287         // If we have to support wrap, let's see if we can compute it directly
288         if (optimizeWrap && (originalHorizontalDimension == WRAP_CONTENT
289                 || originalVerticalDimension == WRAP_CONTENT)) {
290             for (WidgetRun run : mRuns) {
291                 if (run.orientation == orientation
292                         && !run.supportsWrapComputation()) {
293                     optimizeWrap = false;
294                     break;
295                 }
296             }
297 
298             if (orientation == HORIZONTAL) {
299                 if (optimizeWrap && originalHorizontalDimension == WRAP_CONTENT) {
300                     mWidgetcontainer.setHorizontalDimensionBehaviour(FIXED);
301                     mWidgetcontainer.setWidth(computeWrap(mWidgetcontainer, HORIZONTAL));
302                     mWidgetcontainer.mHorizontalRun.mDimension.resolve(mWidgetcontainer.getWidth());
303                 }
304             } else {
305                 if (optimizeWrap && originalVerticalDimension == WRAP_CONTENT) {
306                     mWidgetcontainer.setVerticalDimensionBehaviour(FIXED);
307                     mWidgetcontainer.setHeight(computeWrap(mWidgetcontainer, VERTICAL));
308                     mWidgetcontainer.mVerticalRun.mDimension.resolve(mWidgetcontainer.getHeight());
309                 }
310             }
311         }
312 
313         boolean checkRoot = false;
314 
315         // Now, depending on our own dimension behavior, we may want to solve
316         // one dimension before the other
317 
318         if (orientation == HORIZONTAL) {
319             if (mWidgetcontainer.mListDimensionBehaviors[HORIZONTAL] == FIXED
320                     || mWidgetcontainer.mListDimensionBehaviors[HORIZONTAL] == MATCH_PARENT) {
321                 int x2 = x1 + mWidgetcontainer.getWidth();
322                 mWidgetcontainer.mHorizontalRun.end.resolve(x2);
323                 mWidgetcontainer.mHorizontalRun.mDimension.resolve(x2 - x1);
324                 checkRoot = true;
325             }
326         } else {
327             if (mWidgetcontainer.mListDimensionBehaviors[VERTICAL] == FIXED
328                     || mWidgetcontainer.mListDimensionBehaviors[VERTICAL] == MATCH_PARENT) {
329                 int y2 = y1 + mWidgetcontainer.getHeight();
330                 mWidgetcontainer.mVerticalRun.end.resolve(y2);
331                 mWidgetcontainer.mVerticalRun.mDimension.resolve(y2 - y1);
332                 checkRoot = true;
333             }
334         }
335         measureWidgets();
336 
337         // Let's apply what we did resolve
338         for (WidgetRun run : mRuns) {
339             if (run.orientation != orientation) {
340                 continue;
341             }
342             if (run.mWidget == mWidgetcontainer && !run.mResolved) {
343                 continue;
344             }
345             run.applyToWidget();
346         }
347 
348         boolean allResolved = true;
349         for (WidgetRun run : mRuns) {
350             if (run.orientation != orientation) {
351                 continue;
352             }
353             if (!checkRoot && run.mWidget == mWidgetcontainer) {
354                 continue;
355             }
356             if (!run.start.resolved) {
357                 allResolved = false;
358                 break;
359             }
360             if (!run.end.resolved) {
361                 allResolved = false;
362                 break;
363             }
364             if (!(run instanceof ChainRun) && !run.mDimension.resolved) {
365                 allResolved = false;
366                 break;
367             }
368         }
369 
370         mWidgetcontainer.setHorizontalDimensionBehaviour(originalHorizontalDimension);
371         mWidgetcontainer.setVerticalDimensionBehaviour(originalVerticalDimension);
372 
373         return allResolved;
374     }
375 
376     /**
377      * Convenience function to fill in the measure spec
378      *
379      * @param widget the widget to measure
380      */
measure(ConstraintWidget widget, ConstraintWidget.DimensionBehaviour horizontalBehavior, int horizontalDimension, ConstraintWidget.DimensionBehaviour verticalBehavior, int verticalDimension)381     private void measure(ConstraintWidget widget,
382             ConstraintWidget.DimensionBehaviour horizontalBehavior,
383             int horizontalDimension,
384             ConstraintWidget.DimensionBehaviour verticalBehavior,
385             int verticalDimension) {
386         mMeasure.horizontalBehavior = horizontalBehavior;
387         mMeasure.verticalBehavior = verticalBehavior;
388         mMeasure.horizontalDimension = horizontalDimension;
389         mMeasure.verticalDimension = verticalDimension;
390         mMeasurer.measure(widget, mMeasure);
391         widget.setWidth(mMeasure.measuredWidth);
392         widget.setHeight(mMeasure.measuredHeight);
393         widget.setHasBaseline(mMeasure.measuredHasBaseline);
394         widget.setBaselineDistance(mMeasure.measuredBaseline);
395     }
396 
basicMeasureWidgets(ConstraintWidgetContainer constraintWidgetContainer)397     private boolean basicMeasureWidgets(ConstraintWidgetContainer constraintWidgetContainer) {
398         for (ConstraintWidget widget : constraintWidgetContainer.mChildren) {
399             ConstraintWidget.DimensionBehaviour horizontal =
400                     widget.mListDimensionBehaviors[HORIZONTAL];
401             ConstraintWidget.DimensionBehaviour vertical = widget.mListDimensionBehaviors[VERTICAL];
402 
403             if (widget.getVisibility() == GONE) {
404                 widget.measured = true;
405                 continue;
406             }
407 
408             // Basic validation
409             // TODO: might move this earlier in the process
410             if (widget.mMatchConstraintPercentWidth < 1 && horizontal == MATCH_CONSTRAINT) {
411                 widget.mMatchConstraintDefaultWidth = MATCH_CONSTRAINT_PERCENT;
412             }
413             if (widget.mMatchConstraintPercentHeight < 1 && vertical == MATCH_CONSTRAINT) {
414                 widget.mMatchConstraintDefaultHeight = MATCH_CONSTRAINT_PERCENT;
415             }
416             if (widget.getDimensionRatio() > 0) {
417                 if (horizontal == MATCH_CONSTRAINT
418                         && (vertical == WRAP_CONTENT || vertical == FIXED)) {
419                     widget.mMatchConstraintDefaultWidth = MATCH_CONSTRAINT_RATIO;
420                 } else if (vertical == MATCH_CONSTRAINT
421                         && (horizontal == WRAP_CONTENT || horizontal == FIXED)) {
422                     widget.mMatchConstraintDefaultHeight = MATCH_CONSTRAINT_RATIO;
423                 } else if (horizontal == MATCH_CONSTRAINT && vertical == MATCH_CONSTRAINT) {
424                     if (widget.mMatchConstraintDefaultWidth == MATCH_CONSTRAINT_SPREAD) {
425                         widget.mMatchConstraintDefaultWidth = MATCH_CONSTRAINT_RATIO;
426                     }
427                     if (widget.mMatchConstraintDefaultHeight == MATCH_CONSTRAINT_SPREAD) {
428                         widget.mMatchConstraintDefaultHeight = MATCH_CONSTRAINT_RATIO;
429                     }
430                 }
431             }
432 
433             if (horizontal == MATCH_CONSTRAINT
434                     && widget.mMatchConstraintDefaultWidth == MATCH_CONSTRAINT_WRAP) {
435                 if (widget.mLeft.mTarget == null || widget.mRight.mTarget == null) {
436                     horizontal = WRAP_CONTENT;
437                 }
438             }
439             if (vertical == MATCH_CONSTRAINT
440                     && widget.mMatchConstraintDefaultHeight == MATCH_CONSTRAINT_WRAP) {
441                 if (widget.mTop.mTarget == null || widget.mBottom.mTarget == null) {
442                     vertical = WRAP_CONTENT;
443                 }
444             }
445 
446             widget.mHorizontalRun.mDimensionBehavior = horizontal;
447             widget.mHorizontalRun.matchConstraintsType = widget.mMatchConstraintDefaultWidth;
448             widget.mVerticalRun.mDimensionBehavior = vertical;
449             widget.mVerticalRun.matchConstraintsType = widget.mMatchConstraintDefaultHeight;
450 
451             if ((horizontal == MATCH_PARENT || horizontal == FIXED || horizontal == WRAP_CONTENT)
452                     && (vertical == MATCH_PARENT
453                     || vertical == FIXED || vertical == WRAP_CONTENT)) {
454                 int width = widget.getWidth();
455                 if (horizontal == MATCH_PARENT) {
456                     width = constraintWidgetContainer.getWidth()
457                             - widget.mLeft.mMargin - widget.mRight.mMargin;
458                     horizontal = FIXED;
459                 }
460                 int height = widget.getHeight();
461                 if (vertical == MATCH_PARENT) {
462                     height = constraintWidgetContainer.getHeight()
463                             - widget.mTop.mMargin - widget.mBottom.mMargin;
464                     vertical = FIXED;
465                 }
466                 measure(widget, horizontal, width, vertical, height);
467                 widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
468                 widget.mVerticalRun.mDimension.resolve(widget.getHeight());
469                 widget.measured = true;
470                 continue;
471             }
472 
473             if (horizontal == MATCH_CONSTRAINT && (vertical == WRAP_CONTENT || vertical == FIXED)) {
474                 if (widget.mMatchConstraintDefaultWidth == MATCH_CONSTRAINT_RATIO) {
475                     if (vertical == WRAP_CONTENT) {
476                         measure(widget, WRAP_CONTENT, 0, WRAP_CONTENT, 0);
477                     }
478                     int height = widget.getHeight();
479                     int width = (int) (height * widget.mDimensionRatio + 0.5f);
480                     measure(widget, FIXED, width, FIXED, height);
481                     widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
482                     widget.mVerticalRun.mDimension.resolve(widget.getHeight());
483                     widget.measured = true;
484                     continue;
485                 } else if (widget.mMatchConstraintDefaultWidth == MATCH_CONSTRAINT_WRAP) {
486                     measure(widget, WRAP_CONTENT, 0, vertical, 0);
487                     widget.mHorizontalRun.mDimension.wrapValue = widget.getWidth();
488                     continue;
489                 } else if (widget.mMatchConstraintDefaultWidth
490                         == ConstraintWidget.MATCH_CONSTRAINT_PERCENT) {
491                     if (constraintWidgetContainer.mListDimensionBehaviors[HORIZONTAL] == FIXED
492                             || constraintWidgetContainer.mListDimensionBehaviors[HORIZONTAL]
493                             == MATCH_PARENT) {
494                         float percent = widget.mMatchConstraintPercentWidth;
495                         int width = (int) (0.5f + percent * constraintWidgetContainer.getWidth());
496                         int height = widget.getHeight();
497                         measure(widget, FIXED, width, vertical, height);
498                         widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
499                         widget.mVerticalRun.mDimension.resolve(widget.getHeight());
500                         widget.measured = true;
501                         continue;
502                     }
503                 } else {
504                     // let's verify we have both constraints
505                     if (widget.mListAnchors[ConstraintWidget.ANCHOR_LEFT].mTarget == null
506                             || widget.mListAnchors[ConstraintWidget.ANCHOR_RIGHT].mTarget == null) {
507                         measure(widget, WRAP_CONTENT, 0, vertical, 0);
508                         widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
509                         widget.mVerticalRun.mDimension.resolve(widget.getHeight());
510                         widget.measured = true;
511                         continue;
512                     }
513                 }
514             }
515             if (vertical == MATCH_CONSTRAINT
516                     && (horizontal == WRAP_CONTENT || horizontal == FIXED)) {
517                 if (widget.mMatchConstraintDefaultHeight == MATCH_CONSTRAINT_RATIO) {
518                     if (horizontal == WRAP_CONTENT) {
519                         measure(widget, WRAP_CONTENT, 0, WRAP_CONTENT, 0);
520                     }
521                     int width = widget.getWidth();
522                     float ratio = widget.mDimensionRatio;
523                     if (widget.getDimensionRatioSide() == UNKNOWN) {
524                         ratio = 1f / ratio;
525                     }
526                     int height = (int) (width * ratio + 0.5f);
527 
528                     measure(widget, FIXED, width, FIXED, height);
529                     widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
530                     widget.mVerticalRun.mDimension.resolve(widget.getHeight());
531                     widget.measured = true;
532                     continue;
533                 } else if (widget.mMatchConstraintDefaultHeight == MATCH_CONSTRAINT_WRAP) {
534                     measure(widget, horizontal, 0, WRAP_CONTENT, 0);
535                     widget.mVerticalRun.mDimension.wrapValue = widget.getHeight();
536                     continue;
537                 } else if (widget.mMatchConstraintDefaultHeight
538                         == ConstraintWidget.MATCH_CONSTRAINT_PERCENT) {
539                     if (constraintWidgetContainer.mListDimensionBehaviors[VERTICAL] == FIXED
540                             || constraintWidgetContainer.mListDimensionBehaviors[VERTICAL]
541                             == MATCH_PARENT) {
542                         float percent = widget.mMatchConstraintPercentHeight;
543                         int width = widget.getWidth();
544                         int height = (int) (0.5f + percent * constraintWidgetContainer.getHeight());
545                         measure(widget, horizontal, width, FIXED, height);
546                         widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
547                         widget.mVerticalRun.mDimension.resolve(widget.getHeight());
548                         widget.measured = true;
549                         continue;
550                     }
551                 } else {
552                     // let's verify we have both constraints
553                     if (widget.mListAnchors[ConstraintWidget.ANCHOR_TOP].mTarget == null
554                             || widget.mListAnchors[ConstraintWidget.ANCHOR_BOTTOM].mTarget
555                             == null) {
556                         measure(widget, WRAP_CONTENT, 0, vertical, 0);
557                         widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
558                         widget.mVerticalRun.mDimension.resolve(widget.getHeight());
559                         widget.measured = true;
560                         continue;
561                     }
562                 }
563             }
564             if (horizontal == MATCH_CONSTRAINT && vertical == MATCH_CONSTRAINT) {
565                 if (widget.mMatchConstraintDefaultWidth == MATCH_CONSTRAINT_WRAP
566                         || widget.mMatchConstraintDefaultHeight == MATCH_CONSTRAINT_WRAP) {
567                     measure(widget, WRAP_CONTENT, 0, WRAP_CONTENT, 0);
568                     widget.mHorizontalRun.mDimension.wrapValue = widget.getWidth();
569                     widget.mVerticalRun.mDimension.wrapValue = widget.getHeight();
570                 } else if (widget.mMatchConstraintDefaultHeight
571                         == ConstraintWidget.MATCH_CONSTRAINT_PERCENT
572                         && widget.mMatchConstraintDefaultWidth
573                         == ConstraintWidget.MATCH_CONSTRAINT_PERCENT
574                         && constraintWidgetContainer.mListDimensionBehaviors[HORIZONTAL] == FIXED
575                         && constraintWidgetContainer.mListDimensionBehaviors[VERTICAL] == FIXED) {
576                     float horizPercent = widget.mMatchConstraintPercentWidth;
577                     float vertPercent = widget.mMatchConstraintPercentHeight;
578                     int width = (int) (0.5f + horizPercent * constraintWidgetContainer.getWidth());
579                     int height = (int) (0.5f + vertPercent * constraintWidgetContainer.getHeight());
580                     measure(widget, FIXED, width, FIXED, height);
581                     widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
582                     widget.mVerticalRun.mDimension.resolve(widget.getHeight());
583                     widget.measured = true;
584                 }
585             }
586         }
587         return false;
588     }
589 
590     // @TODO: add description
measureWidgets()591     public void measureWidgets() {
592         for (ConstraintWidget widget : mWidgetcontainer.mChildren) {
593             if (widget.measured) {
594                 continue;
595             }
596             ConstraintWidget.DimensionBehaviour horiz = widget.mListDimensionBehaviors[HORIZONTAL];
597             ConstraintWidget.DimensionBehaviour vert = widget.mListDimensionBehaviors[VERTICAL];
598             int horizMatchConstraintsType = widget.mMatchConstraintDefaultWidth;
599             int vertMatchConstraintsType = widget.mMatchConstraintDefaultHeight;
600 
601             boolean horizWrap = horiz == WRAP_CONTENT
602                     || (horiz == MATCH_CONSTRAINT
603                     && horizMatchConstraintsType == MATCH_CONSTRAINT_WRAP);
604 
605             boolean vertWrap = vert == WRAP_CONTENT
606                     || (vert == MATCH_CONSTRAINT
607                     && vertMatchConstraintsType == MATCH_CONSTRAINT_WRAP);
608 
609             boolean horizResolved = widget.mHorizontalRun.mDimension.resolved;
610             boolean vertResolved = widget.mVerticalRun.mDimension.resolved;
611 
612             if (horizResolved && vertResolved) {
613                 measure(widget, FIXED, widget.mHorizontalRun.mDimension.value,
614                         FIXED, widget.mVerticalRun.mDimension.value);
615                 widget.measured = true;
616             } else if (horizResolved && vertWrap) {
617                 measure(widget, FIXED, widget.mHorizontalRun.mDimension.value,
618                         WRAP_CONTENT, widget.mVerticalRun.mDimension.value);
619                 if (vert == MATCH_CONSTRAINT) {
620                     widget.mVerticalRun.mDimension.wrapValue = widget.getHeight();
621                 } else {
622                     widget.mVerticalRun.mDimension.resolve(widget.getHeight());
623                     widget.measured = true;
624                 }
625             } else if (vertResolved && horizWrap) {
626                 measure(widget, WRAP_CONTENT, widget.mHorizontalRun.mDimension.value,
627                         FIXED, widget.mVerticalRun.mDimension.value);
628                 if (horiz == MATCH_CONSTRAINT) {
629                     widget.mHorizontalRun.mDimension.wrapValue = widget.getWidth();
630                 } else {
631                     widget.mHorizontalRun.mDimension.resolve(widget.getWidth());
632                     widget.measured = true;
633                 }
634             }
635             if (widget.measured && widget.mVerticalRun.mBaselineDimension != null) {
636                 widget.mVerticalRun.mBaselineDimension.resolve(widget.getBaselineDistance());
637             }
638         }
639     }
640 
641     /**
642      * Invalidate the graph of constraints
643      */
invalidateGraph()644     public void invalidateGraph() {
645         mNeedBuildGraph = true;
646     }
647 
648     /**
649      * Mark the widgets as needing to be remeasured
650      */
invalidateMeasures()651     public void invalidateMeasures() {
652         mNeedRedoMeasures = true;
653     }
654 
655     ArrayList<RunGroup> mGroups = new ArrayList<>();
656 
657     // @TODO: add description
buildGraph()658     public void buildGraph() {
659         // First, let's identify the overall dependency graph
660         buildGraph(mRuns);
661 
662         if (USE_GROUPS) {
663             mGroups.clear();
664             // Then get the horizontal and vertical groups
665             RunGroup.index = 0;
666             findGroup(mWidgetcontainer.mHorizontalRun, HORIZONTAL, mGroups);
667             findGroup(mWidgetcontainer.mVerticalRun, VERTICAL, mGroups);
668         }
669         mNeedBuildGraph = false;
670     }
671 
672     // @TODO: add description
buildGraph(ArrayList<WidgetRun> runs)673     public void buildGraph(ArrayList<WidgetRun> runs) {
674         runs.clear();
675         mContainer.mHorizontalRun.clear();
676         mContainer.mVerticalRun.clear();
677         runs.add(mContainer.mHorizontalRun);
678         runs.add(mContainer.mVerticalRun);
679         HashSet<ChainRun> chainRuns = null;
680         for (ConstraintWidget widget : mContainer.mChildren) {
681             if (widget instanceof Guideline) {
682                 runs.add(new GuidelineReference(widget));
683                 continue;
684             }
685             if (widget.isInHorizontalChain()) {
686                 if (widget.horizontalChainRun == null) {
687                     // build the horizontal chain
688                     widget.horizontalChainRun = new ChainRun(widget, HORIZONTAL);
689                 }
690                 if (chainRuns == null) {
691                     chainRuns = new HashSet<>();
692                 }
693                 chainRuns.add(widget.horizontalChainRun);
694             } else {
695                 runs.add(widget.mHorizontalRun);
696             }
697             if (widget.isInVerticalChain()) {
698                 if (widget.verticalChainRun == null) {
699                     // build the vertical chain
700                     widget.verticalChainRun = new ChainRun(widget, VERTICAL);
701                 }
702                 if (chainRuns == null) {
703                     chainRuns = new HashSet<>();
704                 }
705                 chainRuns.add(widget.verticalChainRun);
706             } else {
707                 runs.add(widget.mVerticalRun);
708             }
709             if (widget instanceof HelperWidget) {
710                 runs.add(new HelperReferences(widget));
711             }
712         }
713         if (chainRuns != null) {
714             runs.addAll(chainRuns);
715         }
716         for (WidgetRun run : runs) {
717             run.clear();
718         }
719         for (WidgetRun run : runs) {
720             if (run.mWidget == mContainer) {
721                 continue;
722             }
723             run.apply();
724         }
725         if (DEBUG) {
726             displayGraph();
727         }
728     }
729 
730 
displayGraph()731     private void displayGraph() {
732         String content = "digraph {\n";
733         for (WidgetRun run : mRuns) {
734             content = generateDisplayGraph(run, content);
735         }
736         content += "\n}\n";
737         System.out.println("content:<<\n" + content + "\n>>");
738     }
739 
applyGroup(DependencyNode node, int orientation, int direction, DependencyNode end, ArrayList<RunGroup> groups, RunGroup group)740     private void applyGroup(DependencyNode node,
741             int orientation,
742             int direction,
743             DependencyNode end,
744             ArrayList<RunGroup> groups,
745             RunGroup group) {
746         WidgetRun run = node.mRun;
747         if (run.mRunGroup != null
748                 || run == mWidgetcontainer.mHorizontalRun || run == mWidgetcontainer.mVerticalRun) {
749             return;
750         }
751 
752         if (group == null) {
753             group = new RunGroup(run, direction);
754             groups.add(group);
755         }
756 
757         run.mRunGroup = group;
758         group.add(run);
759         for (Dependency dependent : run.start.mDependencies) {
760             if (dependent instanceof DependencyNode) {
761                 applyGroup((DependencyNode) dependent,
762                         orientation, RunGroup.START, end, groups, group);
763             }
764         }
765         for (Dependency dependent : run.end.mDependencies) {
766             if (dependent instanceof DependencyNode) {
767                 applyGroup((DependencyNode) dependent,
768                         orientation, RunGroup.END, end, groups, group);
769             }
770         }
771         if (orientation == VERTICAL && run instanceof VerticalWidgetRun) {
772             for (Dependency dependent : ((VerticalWidgetRun) run).baseline.mDependencies) {
773                 if (dependent instanceof DependencyNode) {
774                     applyGroup((DependencyNode) dependent,
775                             orientation, RunGroup.BASELINE, end, groups, group);
776                 }
777             }
778         }
779         for (DependencyNode target : run.start.mTargets) {
780             if (target == end) {
781                 group.dual = true;
782             }
783             applyGroup(target, orientation, RunGroup.START, end, groups, group);
784         }
785         for (DependencyNode target : run.end.mTargets) {
786             if (target == end) {
787                 group.dual = true;
788             }
789             applyGroup(target, orientation, RunGroup.END, end, groups, group);
790         }
791         if (orientation == VERTICAL && run instanceof VerticalWidgetRun) {
792             for (DependencyNode target : ((VerticalWidgetRun) run).baseline.mTargets) {
793                 applyGroup(target, orientation, RunGroup.BASELINE, end, groups, group);
794             }
795         }
796     }
797 
findGroup(WidgetRun run, int orientation, ArrayList<RunGroup> groups)798     private void findGroup(WidgetRun run, int orientation, ArrayList<RunGroup> groups) {
799         for (Dependency dependent : run.start.mDependencies) {
800             if (dependent instanceof DependencyNode) {
801                 DependencyNode node = (DependencyNode) dependent;
802                 applyGroup(node, orientation, RunGroup.START, run.end, groups, null);
803             } else if (dependent instanceof WidgetRun) {
804                 WidgetRun dependentRun = (WidgetRun) dependent;
805                 applyGroup(dependentRun.start, orientation, RunGroup.START, run.end, groups, null);
806             }
807         }
808         for (Dependency dependent : run.end.mDependencies) {
809             if (dependent instanceof DependencyNode) {
810                 DependencyNode node = (DependencyNode) dependent;
811                 applyGroup(node, orientation, RunGroup.END, run.start, groups, null);
812             } else if (dependent instanceof WidgetRun) {
813                 WidgetRun dependentRun = (WidgetRun) dependent;
814                 applyGroup(dependentRun.end, orientation, RunGroup.END, run.start, groups, null);
815             }
816         }
817         if (orientation == VERTICAL) {
818             for (Dependency dependent : ((VerticalWidgetRun) run).baseline.mDependencies) {
819                 if (dependent instanceof DependencyNode) {
820                     DependencyNode node = (DependencyNode) dependent;
821                     applyGroup(node, orientation, RunGroup.BASELINE, null, groups, null);
822                 }
823             }
824         }
825     }
826 
827 
generateDisplayNode(DependencyNode node, boolean centeredConnection, String content)828     private String generateDisplayNode(DependencyNode node,
829             boolean centeredConnection,
830             String content) {
831         StringBuilder contentBuilder = new StringBuilder(content);
832         for (DependencyNode target : node.mTargets) {
833             String constraint = "\n" + node.name();
834             constraint += " -> " + target.name();
835             if (node.mMargin > 0 || centeredConnection || node.mRun instanceof HelperReferences) {
836                 constraint += "[";
837                 if (node.mMargin > 0) {
838                     constraint += "label=\"" + node.mMargin + "\"";
839                     if (centeredConnection) {
840                         constraint += ",";
841                     }
842                 }
843                 if (centeredConnection) {
844                     constraint += " style=dashed ";
845                 }
846                 if (node.mRun instanceof HelperReferences) {
847                     constraint += " style=bold,color=gray ";
848                 }
849                 constraint += "]";
850             }
851             constraint += "\n";
852             contentBuilder.append(constraint);
853         }
854         content = contentBuilder.toString();
855 //        for (DependencyNode dependency : node.dependencies) {
856 //            content = generateDisplayNode(dependency, content);
857 //        }
858         return content;
859     }
860 
nodeDefinition(WidgetRun run)861     private String nodeDefinition(WidgetRun run) {
862         int orientation = run instanceof VerticalWidgetRun ? VERTICAL : HORIZONTAL;
863         String name = run.mWidget.getDebugName();
864         StringBuilder definition = new StringBuilder(name);
865         ConstraintWidget.DimensionBehaviour behaviour =
866                 orientation == HORIZONTAL ? run.mWidget.getHorizontalDimensionBehaviour()
867                         : run.mWidget.getVerticalDimensionBehaviour();
868         RunGroup runGroup = run.mRunGroup;
869 
870         if (orientation == HORIZONTAL) {
871             definition.append("_HORIZONTAL");
872         } else {
873             definition.append("_VERTICAL");
874         }
875         definition.append(" [shape=none, label=<");
876         definition.append("<TABLE BORDER=\"0\" CELLSPACING=\"0\" CELLPADDING=\"2\">");
877         definition.append("  <TR>");
878         if (orientation == HORIZONTAL) {
879             definition.append("    <TD ");
880             if (run.start.resolved) {
881                 definition.append(" BGCOLOR=\"green\"");
882             }
883             definition.append(" PORT=\"LEFT\" BORDER=\"1\">L</TD>");
884         } else {
885             definition.append("    <TD ");
886             if (run.start.resolved) {
887                 definition.append(" BGCOLOR=\"green\"");
888             }
889             definition.append(" PORT=\"TOP\" BORDER=\"1\">T</TD>");
890         }
891         definition.append("    <TD BORDER=\"1\" ");
892         if (run.mDimension.resolved && !run.mWidget.measured) {
893             definition.append(" BGCOLOR=\"green\" ");
894         } else if (run.mDimension.resolved) {
895             definition.append(" BGCOLOR=\"lightgray\" ");
896         } else if (run.mWidget.measured) {
897             definition.append(" BGCOLOR=\"yellow\" ");
898         }
899         if (behaviour == MATCH_CONSTRAINT) {
900             definition.append("style=\"dashed\"");
901         }
902         definition.append(">");
903         definition.append(name);
904         if (runGroup != null) {
905             definition.append(" [");
906             definition.append(runGroup.mGroupIndex + 1);
907             definition.append("/");
908             definition.append(RunGroup.index);
909             definition.append("]");
910         }
911         definition.append(" </TD>");
912         if (orientation == HORIZONTAL) {
913             definition.append("    <TD ");
914             if (run.end.resolved) {
915                 definition.append(" BGCOLOR=\"green\"");
916             }
917             definition.append(" PORT=\"RIGHT\" BORDER=\"1\">R</TD>");
918         } else {
919             definition.append("    <TD ");
920             if (((VerticalWidgetRun) run).baseline.resolved) {
921                 definition.append(" BGCOLOR=\"green\"");
922             }
923             definition.append(" PORT=\"BASELINE\" BORDER=\"1\">b</TD>");
924             definition.append("    <TD ");
925             if (run.end.resolved) {
926                 definition.append(" BGCOLOR=\"green\"");
927             }
928             definition.append(" PORT=\"BOTTOM\" BORDER=\"1\">B</TD>");
929         }
930         definition.append("  </TR></TABLE>");
931         definition.append(">];\n");
932         return definition.toString();
933     }
934 
generateChainDisplayGraph(ChainRun chain, String content)935     private String generateChainDisplayGraph(ChainRun chain, String content) {
936         int orientation = chain.orientation;
937         StringBuilder subgroup = new StringBuilder("subgraph ");
938         subgroup.append("cluster_");
939         subgroup.append(chain.mWidget.getDebugName());
940         if (orientation == HORIZONTAL) {
941             subgroup.append("_h");
942         } else {
943             subgroup.append("_v");
944         }
945         subgroup.append(" {\n");
946         String definitions = "";
947         for (WidgetRun run : chain.mWidgets) {
948             subgroup.append(run.mWidget.getDebugName());
949             if (orientation == HORIZONTAL) {
950                 subgroup.append("_HORIZONTAL");
951             } else {
952                 subgroup.append("_VERTICAL");
953             }
954             subgroup.append(";\n");
955             definitions = generateDisplayGraph(run, definitions);
956         }
957         subgroup.append("}\n");
958         return content + definitions + subgroup;
959     }
960 
isCenteredConnection(DependencyNode start, DependencyNode end)961     private boolean isCenteredConnection(DependencyNode start, DependencyNode end) {
962         int startTargets = 0;
963         int endTargets = 0;
964         for (DependencyNode s : start.mTargets) {
965             if (s != end) {
966                 startTargets++;
967             }
968         }
969         for (DependencyNode e : end.mTargets) {
970             if (e != start) {
971                 endTargets++;
972             }
973         }
974         return startTargets > 0 && endTargets > 0;
975     }
976 
generateDisplayGraph(WidgetRun root, String content)977     private String generateDisplayGraph(WidgetRun root, String content) {
978         DependencyNode start = root.start;
979         DependencyNode end = root.end;
980         StringBuilder sb = new StringBuilder(content);
981 
982         if (!(root instanceof HelperReferences) && start.mDependencies.isEmpty()
983                 && end.mDependencies.isEmpty() && start.mTargets.isEmpty()
984                 && end.mTargets.isEmpty()) {
985             return content;
986         }
987         sb.append(nodeDefinition(root));
988 
989         boolean centeredConnection = isCenteredConnection(start, end);
990         content = generateDisplayNode(start, centeredConnection, content);
991         content = generateDisplayNode(end, centeredConnection, content);
992         if (root instanceof VerticalWidgetRun) {
993             DependencyNode baseline = ((VerticalWidgetRun) root).baseline;
994             content = generateDisplayNode(baseline, centeredConnection, content);
995         }
996 
997         if (root instanceof HorizontalWidgetRun
998                 || (root instanceof ChainRun && ((ChainRun) root).orientation == HORIZONTAL)) {
999             ConstraintWidget.DimensionBehaviour behaviour =
1000                     root.mWidget.getHorizontalDimensionBehaviour();
1001             if (behaviour == ConstraintWidget.DimensionBehaviour.FIXED
1002                     || behaviour == ConstraintWidget.DimensionBehaviour.WRAP_CONTENT) {
1003                 if (!start.mTargets.isEmpty() && end.mTargets.isEmpty()) {
1004                     sb.append("\n");
1005                     sb.append(end.name());
1006                     sb.append(" -> ");
1007                     sb.append(start.name());
1008                     sb.append("\n");
1009                 } else if (start.mTargets.isEmpty() && !end.mTargets.isEmpty()) {
1010                     sb.append("\n");
1011                     sb.append(start.name());
1012                     sb.append(" -> ");
1013                     sb.append(end.name());
1014                     sb.append("\n");
1015                 }
1016             } else {
1017                 if (behaviour == MATCH_CONSTRAINT && root.mWidget.getDimensionRatio() > 0) {
1018                     sb.append("\n");
1019                     sb.append(root.mWidget.getDebugName());
1020                     sb.append("_HORIZONTAL -> ");
1021                     sb.append(root.mWidget.getDebugName());
1022                     sb.append("_VERTICAL;\n");
1023                 }
1024             }
1025         } else if (root instanceof VerticalWidgetRun
1026                 || (root instanceof ChainRun && ((ChainRun) root).orientation == VERTICAL)) {
1027             ConstraintWidget.DimensionBehaviour behaviour =
1028                     root.mWidget.getVerticalDimensionBehaviour();
1029             if (behaviour == ConstraintWidget.DimensionBehaviour.FIXED
1030                     || behaviour == ConstraintWidget.DimensionBehaviour.WRAP_CONTENT) {
1031                 if (!start.mTargets.isEmpty() && end.mTargets.isEmpty()) {
1032                     sb.append("\n");
1033                     sb.append(end.name());
1034                     sb.append(" -> ");
1035                     sb.append(start.name());
1036                     sb.append("\n");
1037                 } else if (start.mTargets.isEmpty() && !end.mTargets.isEmpty()) {
1038                     sb.append("\n");
1039                     sb.append(start.name());
1040                     sb.append(" -> ");
1041                     sb.append(end.name());
1042                     sb.append("\n");
1043                 }
1044             } else {
1045                 if (behaviour == MATCH_CONSTRAINT && root.mWidget.getDimensionRatio() > 0) {
1046                     sb.append("\n");
1047                     sb.append(root.mWidget.getDebugName());
1048                     sb.append("_VERTICAL -> ");
1049                     sb.append(root.mWidget.getDebugName());
1050                     sb.append("_HORIZONTAL;\n");
1051                 }
1052             }
1053         }
1054         if (root instanceof ChainRun) {
1055             return generateChainDisplayGraph((ChainRun) root, content);
1056         }
1057         return sb.toString();
1058     }
1059 
1060 }
1061