屈原《离骚》中云：“路漫漫其修远兮，吾将上下而求索”，其实，学习软件编程，学习SDN技术也是一个路漫漫，上下求索的过程。
闲言少叙，本期的内容就是和路径有关。在计算机中，我们最熟悉的路径就是文件系统的目录路径，其表示方式是由"/"分割若干文件夹。另外还有一个可能是大家不怎么常见的-XPath，XPath(XML Path language)也是一种用类似目录树的方法来描述在XML文档中的路径，也使用"/"来表示上下层级间的间隔。但在XPath中，我们还能使用运算符(带谓语的表达式)，类似于/bookstore/book[price>35.0]这样。
说到路径，那路径有什么特点呢？首先是路径具有相对性，我们描述一条路径一定是说从哪个节点（树的根节点也是节点）到哪个节点的路径；其次，把若干条路径拼接起来，其形式还是路径，把一条路径从分割符"/"处拆成几部分，每一部分还是路径的形式，也就是说路径在形式上是自包含的。在ODL中，定义了一个Path接口，以描述上面的特性，看一下Path接口的定义：
public interface Path<P extends Path<P>> {
boolean contains(@Nonnull P other);
}
有没有感觉到这个接口定义的很简洁，精练。
那实现这个接口的类有哪些，在yangtools的项目源码中，可以搜索到YangInstanceIdentifier抽象类及其子类FixedYangInstanceIdentifier和StackedYangInstanceIdentifier，在mdsal项目中可以搜索到InstanceIdentifier类，为什么ODL中对数据访问的路径实现类这样命名呢？其实，这个名称来源于YANG语言，YANG语言里有一个内建类型(Built-In Type)instance-identifier，用来表示用YANG定义的数据树中的路径，其语法格式是XPath的简化格式的子集。
我们先看一下YANG语言规范RFC 6020里关于intsance-identifier的例子，了解它的形式和组成。如下的YANG模型
module example {
namespace "ii:example";
prefix "ex";
container system {
description "Contains various system parameters";
container services {
description "Configure externally available services";
container "ssh" {
leaf port {
type uint16;
}
}
}
list user {
key "name";
config true;
description "This is a list of users in the system.";
leaf name {
type string;
}
leaf full-name {
type string;
}
}
container stats {
list ports {
leaf port-number {
type uint16;
}
leaf port-status {
type uint16;
}
}
}
}
}
对于按照上述模型定义写入的数据，我们可以通过下面的instance-identifier索引其中的数据节点。
/* instance-identifier for a container */
/ex:system/ex:services/ex:ssh
/* instance-identifier for a leaf */
/ex:system/ex:services/ex:ssh/ex:port
/* instance-identifier for a list entry */
/ex:system/ex:user[ex:name='fred']
/* instance-identifier for a list entry without keys */
/ex:system/ex:stats/ex:ports[3]
我们可以看到，其表示形式类似于一个文件路径，都是以"/"进行分割，而两个"/"之间，是我们上一篇讲到的QName+附加条件，即带谓语的表达式。
YangInstanceIdentifier的类定义
好，接下来，我们一起看一下yangtools项目里的YangInstanceIdentifier类定义，其源码路径在yang/yang-data-api目录下。
public abstract class YangInstanceIdentifier implements Path<YangInstanceIdentifier>, Immutable, Serializable {
private final int hash;
......
public abstract List<PathArgument> getPathArguments();
boolean contains(@Nonnull final YangInstanceIdentifier other){...}
......
}
这是一个抽象类，为了简洁，上面省略了一些方法声明。从前面我们知道文件系统的目录路径由文件夹名称组成，XPath由XML的元素名称+谓语表达式组成，在ODL中，YangInstanceIdentifier由PathArgument组成，即PathArgument就是组成YangInstanceIdentifier的要素，其定义如下:
public interface PathArgument extends Comparable<PathArgument>, Immutable, Serializable {
QName getNodeType();
String toRelativeString(PathArgument previous);
}
从PathArgument定义能看到，它定义了两个方法 QName getNodeType()和String toRelativeString(PathArgument previous)，第一个方法表示它由QName组成，第二个方法表示它包含关系字符串。实际的实现代码中，toRelativeString()方法默认会按照QName的toString()方法返回，但如果previous与当前PathArgument对象的QName属于同一个namespace，则该方法直接返回当前PathArgument对象的QName的localName值；如果其中的QName标识的是一个带key的list，该方法会在原来的返回值基础上附加上"[key-name='key-value']"进行返回；如果其中的QName标识的是一个leaf节点，该方法会在原来的返回值基础上附加上['value']进行返回。以上即具体实现PathArgument这个接口的三个子类NodeIdentifier，NodeIdentifierWithPredicates，NodeWithValue在实现toRelativeString方法时的实现逻辑。实现方法分别见下面
● NodeIdentifier：
public String toRelativeString(final PathArgument previous) {
if (previous instanceof AbstractPathArgument) {
final QNameModule mod = previous.getNodeType().getModule();
if (getNodeType().getModule().equals(mod)) {
return getNodeType().getLocalName();
}
}
return getNodeType().toString();
}
● NodeIdentifierWithPredicates：
public String toRelativeString(final PathArgument previous) {
return super.toRelativeString(previous) + '[' + keyValues + ']';
}
NodeWithValue：
public String toRelativeString(final PathArgument previous) {
return super.toRelativeString(previous) + '[' + value + ']';
}
画一下PathArgument接口及其实现类的类图，见下面：
另外，我们通过路径主要想快速的对数据树进行查询，根据节点的路径快速定位到节点，因此在YangInstanceIdentifier类里也定义里了若干抽象方法访问路径，我们在处理YangInstanceIdentifier时也可以直接调用，主要方法方法包括：
YangInstanceIdentifier createRelativeIdentifier(int skipFromRoot);
Collection<PathArgument> tryPathArguments();
Collection<PathArgument> tryReversePathArguments();
boolean isEmpty();
YangInstanceIdentifier getParent();
YangInstanceIdentifier getAncestor(int depth);
List<PathArgument> getPathArguments();
List<PathArgument> getReversePathArguments();
PathArgument getLastPathArgument();
由于YangInstanceIdentifier只是一个抽象类，那肯定就必须要有具体实现类。在yangtools项目源码中，其实现类有两个：FixedYangInstanceIdentifier和StackedYangInstanceIdentifier。这两个实现类主要区别是其内部实现一个按照普通的列表的处理方式实现的，一个是把按照栈的逻辑实现的。这两个实现类不是public的，因此在其定义的package外面是无法访问的。
YangInstanceIdentifier类提供了多个方法方便我们创建YangInstanceIdentifier对象，如下：
YangInstanceIdentifier create(final Iterable<? extends PathArgument> path);
YangInstanceIdentifier create(final PathArgument... path);
YangInstanceIdentifier node(final QName name);
YangInstanceIdentifier node(final PathArgument arg);
YangInstanceIdentifier of(final QName name);
大家可以使用上面的方法创建YangInstanceIdentifier对象。另外，YangInstanceIdentifier类还提供了一个builder()方法，该方法会创建一个`YangInstanceIdentifierBuilder对象，通过这个builder，也可以方便的构建YangInstanceIdentifier对象。
构建YangInstanceIdentifier对象的方法的入参如果是PathArgument类型，我们需要创建该接口的实现类NodeIdentifier或NodeIdentifierWithPredicates或NodeWithValue的实例，作为方法入参。
下面就是本人绘制的YangInstanceIdentifier类及YangInstanceIdentifierBuilder类的类图，供大家参考。
YangInstanceIdentifier的比较
由于YangInstanceIdentifier本质是路经，那在查询和检索数据树时，就避免不了进行YangInstanceIdentifier对象的比较。YangInstanceIdentifier有两个方法进行比较，一个是equals，其实现代码如下：
public boolean equals(final Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof YangInstanceIdentifier)) {
return false;
}
YangInstanceIdentifier other = (YangInstanceIdentifier) obj;
if (this.hashCode() != obj.hashCode()) {
return false;
}
return pathArgumentsEqual(other);
}
这个方法覆写了Object的equals()方法，实现代码里第一个if判断即如果引用一致，则两个对象一定相等；第二个if判断，如果两者类型不一致，则肯定不相等，也对后面的强制类型转换作了保护，避免出现异常。再看上面红色部分代码，比较两个对象的hash值，如果两者hash值不同，则两者肯定不相等，最后才调用一个方法去比较YangInstanceIdentifier的PathArgument是否都相同。这段实现代码充分考虑到了效率和异常保护，值得我们参考借鉴。
另外一个比较方法就是Path接口定义的contains()方法,实现代码如下
public final boolean contains(@Nonnull final YangInstanceIdentifier other) {
if (this == other) {
return true;
}
checkArgument(other != null, "other should not be null");
final Iterator<PathArgument> lit = getPathArguments().iterator();
final Iterator<PathArgument> oit = other.getPathArguments().iterator();
while (lit.hasNext()) {
if (!oit.hasNext()) {
return false;
}
if (!lit.next().equals(oit.next())) {
return false;
}
}
return true;
}
从这段代码实现上，可以看出其比较的过程，从第一个PathArgument开始比较，依次迭代进行比较所有源路经里PathArgument是否与目标路径（方法入参other）里的PathArgument相等，如果两者比较过程中源路径已到末尾，源路径最后一个PathArgument仍然相等，则返回true。简单理解上述处理逻辑就是PathArgument依次比较都相等的情况下，短的路经包含长的路经。
InstanceIdentifier解读
其实，我们在基于ODL进行开发时，经常使用的基本上是binding接口，而binding接口的定义，并没有直接使用YangInstanceIdentifier这个类，而是用的类InstanceIdentifier，这个类的定义不在yangtools项目中，而是在mdsal项目的binding/yang-binding目录下，看它的定义:
public class InstanceIdentifier<T extends DataObject> implements Path<InstanceIdentifier<? extends DataObject>>, Immutable, Serializable {
......
final Iterable<PathArgument> pathArguments;
private final Class<T> targetType;
......
}
这个类表示的也是路径，其内部包含了一个迭代器，可以看作就是PathArgument列表。但这个类定义里包含了一个Class类型的变量targetType，把路经与根据yang文件生成的Java类关联了起来，以方便大家可以直接使用根据yang生成的类。
InstanceIdentifier也提供了一个builder类以实现InstanceIdentifier对象的创建，使用方法如下面的形式：
InstanceIdentifierBuilder.builder(Nodes.class).child(Node.class, new NodeKey(new NodeId("openflow:1")).build();
InstanceIdentifier类的代码实现细节比较复杂，待后续整理《从dom到binding》这篇时，可能会再讲一下相关内容。
本篇主要介绍了对应YANG中instance-identifier这个类型，也即数据树中的路径的类的实现源代码，还介绍了它的构造方法及比较的实现机制，这样大家再碰到这个类，在使用这个类的对象时，就会心中有数了。
原文发布时间为：2018-09-9
