背景

最近在项目中使用 RelativeLayout 的过程当中发现 RelativeLayout 内部的孩子 View 节点会收到两次 measure 消息，导致项目中某个自定义控件的尺寸和预期的不一致。本着出了问题需要知道为什么，并且需要给出合理的解决方案这样的原则，因此在阅读分析完源码的基础上输出个人对 RelativeLayout 的一些理解，在此进行记录和分享。

是什么

• RelativeLayout
  • Android SDK API 1 中添加的一个类，该类用于解决界面中多个控件之间的相对布局问题，可以通过描述当前孩子与其它孩子或者与父节点的相对位置决定的当前孩子布局信息
  • 在类的继承结构上，它是 ViewGroup 的子类
  • 在运行时，它是 View 控件树中的非叶子节点，它可以包含孩子节点
• 拓扑排序
  • 是一种求有向无环图的拓扑序列时使用的排序方法
  • 该方法的输入是有向无环图，输出是拓扑序列

为什么

• 为了解决大量应用层开发者在开发 APP 时需要实现界面中多个控件之间的相对位置的需求，SDK 开发者们设计并实现的一个类/库/模块。
• 思考一下，如果让我设计并实现一个模块来解决这些具有相对位置关系的控件的布局问题，我会怎么做？这是目前我认为能够很好地考验一个人解决问题的能力的思维方式

内部原理

在阅读 RelativeLayout 的源码时，发现其为了解决多个孩子节点之间相对位置的问题，应用了数据结构中图的拓扑排序来确定孩子节点测量的先后顺序。我们一起来看下如何计算出一些具有依赖关系的任务的执行顺序。当然这只是一种参考解法，肯定还有其他解法。

• 数据结构（记录相关信息）
  • 节点
    android.widget.RelativeLayout.DependencyGraph.Node
    依赖关系图中的一个节点，封装了一个 View，以及 View 的依赖节点和被依赖节点。简单来说就是有向图中的一个节点，并且该节点知道自己的入度和出度信息。入度为 0 的节点被称为根节点
  • 弧（边）
    android.widget.RelativeLayout.LayoutParams#mRules
    每个 RelativeLayout 的孩子节点的布局参数中都记录了当前节点依赖于其它节点的信息。孩子节点采用 id 标识，每个节点可以用于描述的相对位置参数有 22 个（android.widget.RelativeLayout#VERB_COUNT）。采用 int 类型的数组记录依赖信息，数组下标是相对位置参数，数组里面的值是依赖节点的 ID
  • 图
    android.widget.RelativeLayout.DependencyGraph
    记录依赖关系的图信息。记录一个 RelativeLayout 实例所持有的孩子节点信息。
• 算法（给定输入/输出，实现计算过程）
  • 添加节点
    android.widget.RelativeLayout.DependencyGraph#add

void add(View view) {
    final int id = view.getId();
    // 把 View 包装到 Node 实例内部
    final Node node = Node.acquire(view);

    if (id != View.NO_ID) {
        // 记录 ID 到 Node 的映射关系，为了接下来的查询效率
        mKeyNodes.put(id, node);
    }

    // 添加一个图节点
    mNodes.add(node);
}

• 添加边
  android.widget.RelativeLayout.LayoutParams#LayoutParams(android.content.Context, android.util.AttributeSet)
  在创建 LayoutParams 对象时，从 AttributeSet 中解析边信息

final int N = a.getIndexCount();
// 遍历属性集合
for (int i = 0; i < N; i++) {
    // 读取属性索引号
    int attr = a.getIndex(i);
    switch (attr) {
        case com.android.internal.R.styleable.RelativeLayout_Layout_layout_alignWithParentIfMissing:
            alignWithParent = a.getBoolean(attr, false);
            break;
        case com.android.internal.R.styleable.RelativeLayout_Layout_layout_toLeftOf:
            // 读取被依赖 View 的 ID
            // 当前节点 LEFT_OF 于 attr 对应的 res id
            rules[LEFT_OF] = a.getResourceId(attr, 0);
            break;
        // 省略其它依赖规则解析
        ...

• 计算拓扑序列
  android.widget.RelativeLayout.DependencyGraph#getSortedViews

// 输出指定边规则后的拓扑序列
void getSortedViews(View[] sorted, int... rules) {
    // 找到所有根节点放进双端队列存放起来
    final ArrayDeque<Node> roots = findRoots(rules);
    int index = 0;

    Node node;
    // 遍历根节点队列
    while ((node = roots.pollLast()) != null) {
        //解封得到 View 对象
        final View view = node.view;
        final int key = view.getId();

        // 输出到拓扑序列数组中
        sorted[index++] = view;

        // 找到当前根节点的出度信息
        final ArrayMap<Node, DependencyGraph> dependents = node.dependents;
        final int count = dependents.size();
        // 遍历出度节点
        for (int i = 0; i < count; i++) {
            final Node dependent = dependents.keyAt(i);
            // 入度信息
            final SparseArray<Node> dependencies = dependent.dependencies;
            // 删除入度
            dependencies.remove(key);
            // 入度为 0 
            if (dependencies.size() == 0) {
                // 成为新的根节点，加入到双端队列中
                roots.add(dependent);
            }
        }
    }

    // 如果拓扑序列中节点个数和图中所有节点的个数不等，则存在环
    if (index < sorted.length) {
        throw new IllegalStateException("Circular dependencies cannot exist"
                + " in RelativeLayout");
    }
}

android.widget.RelativeLayout.DependencyGraph#findRoots

// 根据参数中选择的依赖规则找到所有根节点
private ArrayDeque<Node> findRoots(int[] rulesFilter) {
    final SparseArray<Node> keyNodes = mKeyNodes;
    final ArrayList<Node> nodes = mNodes;
    final int count = nodes.size();

    // Find roots can be invoked several times, so make sure to clear
    // all dependents and dependencies before running the algorithm
    for (int i = 0; i < count; i++) {
        final Node node = nodes.get(i);
        node.dependents.clear();
        node.dependencies.clear();
    }

    // Builds up the dependents and dependencies for each node of the graph
    // 遍历图中所有节点，构建节点的入度和出度信息
    for (int i = 0; i < count; i++) {
        // 读取当前节点
        final Node node = nodes.get(i);

        final LayoutParams layoutParams = (LayoutParams) node.view.getLayoutParams();
        // 从 LayoutParams 中读取依赖信息
        final int[] rules = layoutParams.mRules;
        final int rulesCount = rulesFilter.length;

        // Look only the the rules passed in parameter, this way we build only the
        // dependencies for a specific set of rules
        // 根据参数中选取的部分规则构建依赖信息
        for (int j = 0; j < rulesCount; j++) {
            // 拿到被依赖对象的 ID
            final int rule = rules[rulesFilter[j]];
            if (rule > 0) {
                // The node this node depends on
                final Node dependency = keyNodes.get(rule);
                // Skip unknowns and self dependencies
                if (dependency == null || dependency == node) {
                    continue;
                }
                // Add the current node as a dependent
                // 被依赖节点记录入度信息
                dependency.dependents.put(node, this);
                // Add a dependency to the current node
                // 当前节点记录出度信息
                node.dependencies.put(rule, dependency);
            }
        }
    }

    final ArrayDeque<Node> roots = mRoots;
    // 清理之前的计算结果
    roots.clear();

    // Finds all the roots in the graph: all nodes with no dependencies
    // 遍历所有节点
    for (int i = 0; i < count; i++) {
        final Node node = nodes.get(i);
        if (node.dependencies.size() == 0) 
            // 入度为 0 则为根节点
            roots.addLast(node);
    }

    // 输出根节点队列
    return roots;
}

练习题

• 拷贝 RelativeLayout 的代码和资源到自己的工程中，并应用拷贝过的 RelativeLayout 进行基本使用
• 修改拷贝的 RelativeLayout 代码，打印 RelativeLayout 添加节点、添加边、拓扑排序的工作流程日志信息
• 实现图的邻接矩阵、邻接链表的基本操作
• 根据百科中拓扑排序的算法介绍，手动实现简单的拓扑排序
• 同一个图支持多次根据输入的边信息输出拓扑序列
• 删除 RelativeLayout 中的相关拓扑排序 API 的实现，自己手动实现一遍，并确保测试用例可以跑过
• 输出拓扑排序在 RelativeLayout 中应用的文章

总结

到目前为止，RelativeLayout 已经计算出所有孩子节点的依赖关系，接下来可以根据拓扑序列中的顺序来向孩子节点发送 measure 消息，从而计算出 RelativeLayout 的尺寸信息

参考

RelativeLayout 文档
RelativeLayout 代码
拓扑排序