TTGraph README

TTGraph 是

• 多种数据的容器或数据库，这些数据相互交叉引用，形成类似图的数据结构。
• 类型化图：多个类型节点的集合。每个节点持有一些私有数据，以及指向其他节点的指针/边/引用。
• 事务型图：图上的所有操作都通过事务组织，这意味着一个原子操作组同时应用。

TTGraph 提供

• 不同类型数据的便捷容器，提供一些处理类型的有用方法。
• 一个数据结构来维护节点之间的连接。TTGraph 为所有类型创建反射，以跟踪节点之间的连接，命名为 link。这允许一些复杂的操作，例如重定向链接和保持双向链接。
• 一个干净的接口，以帮助避免一些令人烦恼的编译错误。事务的设计试图防止同时存在同一对象的不可变引用和可变引用，并试图避免生命周期迷宫。
• TTGraph 最初被设计为编译器的中间表示系统，但其潜力并不仅限于此。

TTGraph 目前不提供，但未来可能得到改进

• 非常高的性能。虽然 TTGraph 的操作相对便宜（大部分是 O(log(n)）），但它不是一个高性能数据库。
• 非常大的容量。所有数据都存储在内存中。

动机示例

类型化节点声明

假设有几个工厂、工人和产品，以下示例使用 TTGraph 维护它们的数据。

use tgraph::*;
use std::collections::HashSet;

#[derive(TypedNode)]
struct FactoryNode{
  name: String,
  workers: HashSet<NodeIndex>,
  products: HashSet<NodeIndex>,
}

#[derive(TypedNode)]
struct WorkerNode{
  name: String,
  factory: NodeIndex,
  produced: Vec<NodeIndex>,
}

#[derive(TypedNode)]
struct ProductNode{
  id: usize
}

在这里，一个工厂有一个名称、多个工人和产品。 name 是一个 数据字段，TTGraph 不关心它。它可以属于 Rust 中的任何类型。

workers 和 products 是 链接。链接是到另一个节点的连接。TTGraph 使用 NodeIndex 来索引节点，它实现了 Copy。如果字段是以下类型之一，则被视为链接。（注意：在宏中，类型是通过名称进行匹配的，tgraph::NodeIndex/NodeIndex/std::collections::Vec::<NodeIndex>/Vec::<tgraph::NodeIndex> 都是可接受的。）

• 直接链接：NodeIndex
• 向量链接：Vec<NodeIndex>
• 无序集合链接：HashSet<NodeIndex>
• 有序集合链接：BTreeSet<NodeIndex>

图和事务

下面的例子展示了如何构建一个图。

// Use an node_enum to collect all node types together
node_enum!{
  enum Node{
    Factory(FactoryNode),
    Worker(WorkerNode),
    Product(ProductNode),
  }
}

// Create the context
let ctx = Context::new();
// Create a graph of Node
let mut graph = Graph::<Node>::new(&ctx);

// Does some initial operations with a transaction
// Actual type: Transaction::<Node>, <Node> can be inferenced when commited
let mut trans = Transaction::new(&ctx);
let product1 = trans.insert(Node::Product(ProductNode{ id: 1 }));
let product2 = trans.insert(Node::Product(ProductNode{ id: 2 }));
let worker1 = trans.alloc();
let worker2 = trans.alloc();
let factory = trans.insert(Node::Factory(FactoryNode{
  name: "Factory".to_string(),
  workers: HashSet::from([worker1, worker2]),
  products: HashSet::from([product1, product2]),
}));
trans.fill_back(worker1, Node::Worker(WorkerNode{
  name: "Alice".to_string(),
  factory,
  produced: vec![product2],
}));
trans.fill_back(worker2, Node::Worker(WorkerNode{
  name: "Bob".to_string(),
  factory,
  produced: vec![product1],
}));

// Commit the transaction to the graph
graph.commit(trans);

// Get the factory node back
let factory_node = get_node!(graph, Node::Factory, factory).unwrap();
assert_eq!(factory_node.name, "Factory");
assert_eq!(factory_node.workers, HashSet::from([worker1, worker2]));
assert_eq!(factory_node.products, HashSet::from([product1, product2]));

首先，使用 node_enum! 宏创建一个枚举以收集所有类型的节点。它是一个 proc_macro 而不是 proc_macro_derive，因为在后者的示例中需要可扩展的语法。在 node_enum! 中的枚举将实现 NodeEnum 特性，并且可以在 Graph 中使用。

node_enum!{
  enum Node{
    Factory(FactoryNode),
    Worker(WorkerNode),
    Product(ProductNode),
  }
}

然后，使用该上下文创建一个上下文和一个图。上下文用于确保 NodeIndexes 在所有事务中保持一致。图不保留对上下文的引用，因此用户有责任保持它。

let ctx = Context::new();
let mut graph = Graph::<Node>::new(&ctx);

接下来，使用与图相同的上下文创建一个事务。在事务上完成操作后，可以使用 commit 方法将其提交到图中。事务不保留对图的引用，它们具有独立的生存期。（尽管，如果事务比图存活时间长，则它不会做任何事情）

let mut trans = Transaction::new(&ctx);
// Do something with trans
graph.commit(trans);

现在我们更详细地看看如何构建图。Product 节点是最简单的，它只有一个 id。使用方法 insert 将节点添加到事务中。它返回一个指向新节点的 NodeIndex，这意味着我们稍后可以使用 product1 和 product2 从图中检索节点。

let product1 = trans.insert(Node::Product(ProductNode{ id: 1 }));
let product2 = trans.insert(Node::Product(ProductNode{ id: 2 }));
# graph.commit(trans);

工厂和工人之间有更复杂的关系，因为它们相互引用。这意味着我们不能单独创建 FactoryNode 或 WorkerNode。幸运的是，TTGraph 在事务中进行操作，我们可以首先使用方法 alloc 为工人分配一个 NodeIndex，然后使用方法 fill_back 填充数据。事务通过在提交时检查所有分配的节点都已填充来防止悬挂的 NodeIndex。

let worker1 = trans.alloc();
let worker2 = trans.alloc();
let factory = trans.insert(Node::Factory(FactoryNode{
  name: "Factory".to_string(),
  workers: HashSet::from([worker1, worker2]),
  products: HashSet::from([product1, product2]),
}));
trans.fill_back(worker1, Node::Worker(WorkerNode{
  name: "Alice".to_string(),
  factory,
  produced: vec![product2],
}));
trans.fill_back(worker2, Node::Worker(WorkerNode{
  name: "Bob".to_string(),
  factory,
  produced: vec![product1],
}));

最后，在将事务提交到图中之后，我们得到了上述描述的节点组成的图。我们可以使用 NodeIndex 来获取节点。当节点类型已知时，使用 get_node! 宏，它返回一个 Option<&TypedNode> 来指示节点是否存在。

let factory_node = get_node!(graph, Node::Factory, factory).unwrap();
assert_eq!(factory_node.name, "Factory");
assert_eq!(factory_node.workers, HashSet::from([worker1, worker2]));
assert_eq!(factory_node.products, HashSet::from([product1, product2]));

更多操作请参阅关于 Graph 和 Transcation 结构的文档。

双向链接

TTGraph 支持双向链接声明。在这个例子中，Factory 的 workers 字段和 Worker 的 factory 字段实际上是一对双向链接。我们可以修改 node_enum! 声明以提供更多支持。

node_enum!{
  enum Node{
    Factory(FactoryNode),
    Worker(WorkerNode),
    Product(ProductNode),
  }
  bidirectional!{
    Factory.workers <-> Worker.factory,
  }
}

let ctx = Context::new();
let mut graph = Graph::<Node>::new(&ctx);

let mut trans = Transaction::new(&ctx);
let product1 = trans.insert(Node::Product(ProductNode{ id: 1 }));
let product2 = trans.insert(Node::Product(ProductNode{ id: 2 }));
let factory = trans.insert(Node::Factory(FactoryNode{
  name: "Factory".to_string(),
  workers: HashSet::new(), // Here we leave this set empty to demonstrate it can be automatically filled
  products: HashSet::from([product1, product2]),
}));
let worker1 = trans.insert(Node::Worker(WorkerNode{
  name: "Alice".to_string(),
  factory,
  produced: vec![product2],
}));
let worker2 = trans.insert(Node::Worker(WorkerNode{
  name: "Bob".to_string(),
  factory,
  produced: vec![product1],
}));

graph.commit(trans);

// Get the factory node back
let factory_node = get_node!(graph, Node::Factory, factory).unwrap();
assert_eq!(factory_node.name, "Factory");
assert_eq!(factory_node.workers, HashSet::from([worker1, worker2]));
assert_eq!(factory_node.products, HashSet::from([product1, product2]));

在这里，node_enum! 宏内部的 bidiretional! 宏用于声明双向链接。

• 使用 variant.field <-> variant.field, 来指示一对双向链接。注意：枚举的变体，而不是类型！
• bidiretional! 宏实际上不是一个宏，它只能在 node_enum! 宏内部使用。

接下来，在创建工厂节点时，其工作者字段简单地留空。但是，在提交到图之后，TTGraph 会自动将其双向链接添加进去。

双向链接的规则

• 双向链接可以在以下情况下形成：一对 NodeIndex，在 NodeIndex 和 Set<NodeIndex> 之间，一对 Set<NodeIndex>。（Set 可能是 HashSet 或 BTreeSet，目前不支持 Vec）
• 当添加链接时，会检查双向链接的另一端。如果双向链接已经存在，则不会做任何事情。
• 当删除链接时，会检查双向链接的另一端。如果双向链接存在，则将其删除。如果没有双向链接存在，由于 TTGraph 未知用户是否有意删除，因此假定不会发生任何操作。
• NodeIndex 字段：如果 NodeIndex 为空，则可以添加链接，否则将发生冲突并引发恐慌。链接可以删除，但如果为空则不会引发恐慌。
• NodeIndex 集合字段：可以始终将链接添加到或从集合中删除。
• 在修改现有的双向链接对时，确保修改在同一个事务中发生以防止冲突。TTGraph 在维护双向链接之前执行所有其他操作。

通过名称和组获取数据

TTGraph 支持一些类型擦除操作，针对的是某些节点类型具有一些相似的字段，以及匹配这些字段的枚举非常冗长的情况。

在上一个例子中，假设有两种类型的工人，机器人和人。它们可能有非常不同的数据，但它们都有一个名称。现在我们想要为所有工人创建一个名称列表。典型的解决方案是匹配 NodeEnum，但 TTGraph 提供了另一种解决方案，即通过名称获取数据。

data_ref_by_name::<Type>::(&'static str name) -> Option<&Type> 方法提供了一种通过名称访问数据字段的接口。如果节点具有该字段并且类型匹配（通过 std::any::Any::downcast_ref），则返回 Some(&Type)，否则返回 None。

#[derive(TypedNode)]
struct HumanWorkerNode{
  name: String,
  // ... other data
}
#[derive(TypedNode)]
struct RobotWorkerNode{
  name: String,
  // ... other data
}

node_enum!{
  enum Node{
    Human(HumanWorkerNode),
    Robot(RobotWorkerNode),
    // ... other nodes
  }
}

let ctx = Context::new();
let mut graph = Graph::<Node>::new(&ctx);
// ... building the graph

// idx: NodeIndex, node: &Node
let node = graph.get(idx).unwrap();

// Not so convinient way to get the name
let name = match node {
  Node::Human(human) => Some(&human.name),
  Node::Robot(robot) => Some(&robot.name),
  _ => None,
};

// A simplified solution
// Here, "name" is the field's name
// The "name" field is a String, so this variable is an Option<&str>
let name = node.data_ref_by_name::<String>("name");

此外，如果我们想迭代所有工作节点，跳过其他所有节点，TTGraph 中的分组机制就可以派上用场。

在这里，两种变体 Human 和 Robot 位于 worker 组中。使用 iter_group(&'static str) 方法来迭代组内的所有节点。

注意

• 变体可以位于多个或没有组中。
• 目前，此方法不提供性能提升，因为它只是在根据组名匹配变体时进行包装。

node_enum!{
  enum Node{
    Human(HumanWorkerNode),
    Robot(RobotWorkerNode),
    // ... other nodes
  }
  group!{
    worker{Human, Robot},
  }
}

for (idx, node) in graph.iter_group("worker") {
  let name = node.data_ref_by_name::<String>("name").unwrap();
  // ...
}

链接也可以分组。假设工人可能生产不同类型的产品，并将它们组织成 product 组可以帮助遍历所有这些产品。

注意

• 链接字段可以位于多个或没有组中。语法：#[group(group1, group2, ...)]
• 是的，其形式与 node_enum! 不一致。问题是如果结构体位于宏中，linter（rust-analyzer）将无法显示其内容。作者个人认为 group! 形式更优雅，但不值得破坏 linter。

#[derive(TypedNode)]
struct HumanWorkerNode{
  name: String,
  #[group(product)]
  cooked: BTreeSet<NodeIndex>,
  #[group(product)]
  maked: BTreeSet<NodeIndex>,
  // ... other data
}
#[derive(TypedNode)]
struct RobotWorkerNode{
  name: String,
  #[group(product)]
  manufactured: BTreeSet<NodeIndex>,
  // ... other data
}

let node = graph.get(idx).unwrap();
for idx in node.get_links_by_group("product") {
  // Now idx binds to all NodeIndex inside the product group
}

其他类型擦除方法可在 NodeEnum 和 TypedNode 特性文档中找到。

链接类型检查

在 TTGraph 中，节点通过一个 NodeIndex 链接到其他节点，实际上它是一个弱类型，因为节点枚举中的任何变体都可以由 NodeIndex 指向。

出于调试目的，可以添加一个可选的链接类型检查，使用 link_type!{ #var.#field : #var, ... }。当事务提交时，将检查所有更改。如果 NodeIndex 指向错误的枚举变体，则引发恐慌。

链接类型也可以是一个组。如果组的名称与变体的名称冲突，则将其视为一个组。

需要 debug 功能。否则，将跳过所有检查。

use ttgraph::*;
use std::collections::HashSet;
#[derive(TypedNode)]
struct FactoryNode{
 name: String,
 workers: HashSet<NodeIndex>,
}
#[derive(TypedNode)]
struct HumanWorkerNode{
  name: String,
  factory: NodeIndex,
}
#[derive(TypedNode)]
struct RobotWorkerNode{
  name: String,
  factory: NodeIndex,
}
node_enum!{
  enum Node{
    Factory(FactoryNode),
    Human(HumanWorkerNode),
    Robot(RobotWorkerNode),
  }
  link_type!{
    Factory.workers : {Human, Robot},
    Human.factory: Factory,
    Robot.factory: Factory,
  }
}

在本示例中，工厂的工人可以链接到人类或机器人，而人类和机器人的工厂字段必须链接到工厂。

工作中

• 图形创建宏。一种简化大量alloc_node、fill_back_node和new_node调用的子语言。
• 图形转换。一种方便地将Graph<NodeEnumA>转换为Graph<NodeEnumB>的方法，如果NodeEnumA和NodeEnumB有很多共同变体。

更改

0.2.1

• 修复了IntoIter用于&Graph的问题。
• 增加了更多检查函数。增加带有检查的提交。
• 为mut_node!和update_node!添加了新的重载，以支持move ||。

0.2.2

• 链接类型检查现在可以指定一个组。

0.2.3

• 链接类型检查现在报告更多信息。

许可证

根据您的选择，受以下任一许可证的许可

• Apache许可证第2版 (LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0)
• MIT许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

。

贡献

除非您明确声明，否则您有意提交的任何贡献，根据Apache-2.0许可证定义，均应如上所述双重许可，没有附加条款或条件。