Rust 练习册 :DOT领域特定语言与构建器模式
在软件开发中,领域特定语言(Domain Specific Language, DSL)是一种专门为特定领域设计的计算机语言。DOT语言是用于描述图形结构的声明性语言,常用于Graphviz工具中。在 Exercism 的 “dot-dsl” 练习中,我们需要构建一个Rust DSL来生成DOT语言描述的图形。这不仅能帮助我们掌握构建器模式和DSL设计,还能深入学习Rust中的模块系统和面向对象设计。
什么是DOT语言?
DOT是一种图形描述语言,用于描述有向图和无向图。它具有简洁的语法结构:
graph {
a -- b -- c;
b -- d;
}
这个例子描述了一个无向图,包含节点a、b、c、d和连接它们的边。
在我们的练习中,需要实现一个Rust DSL来构建这样的图形结构。
让我们先看看练习提供的初始结构:
pub mod graph {
pub struct Graph;
impl Graph {
pub fn new() -> Self {
unimplemented!("Construct a new Graph struct.");
}
}
}
我们需要扩展这个结构,使其支持节点、边和属性的构建。
设计分析
1. 模块结构
通过测试用例可以看出,我们需要以下模块和结构:
Graph- 图结构,包含节点、边和属性Node- 节点结构,有名称和属性Edge- 边结构,连接两个节点,有属性
2. 构建器模式
为了提供流畅的API,我们将使用构建器模式:
let graph = Graph::new()
.with_nodes(&nodes)
.with_edges(&edges)
.with_attrs(&attrs);
完整实现
1. Graph模块实现
pub mod graph {
use std::collections::HashMap;
pub mod graph_items {
pub mod node {
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq)]
pub struct Node {
pub name: String,
pub attrs: HashMap<String, String>,
}
impl Node {
pub fn new(name: &str) -> Self {
Node {
name: name.to_string(),
attrs: HashMap::new(),
}
}
pub fn with_attrs(mut self, attrs: &[(&str, &str)]) -> Self {
for &(key, value) in attrs {
self.attrs.insert(key.to_string(), value.to_string());
}
self
}
pub fn get_attr(&self, attr: &str) -> Option<&str> {
self.attrs.get(attr).map(|s| s.as_str())
}
}
}
pub mod edge {
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq)]
pub struct Edge {
src: String,
dst: String,
attrs: HashMap<String, String>,
}
impl Edge {
pub fn new(src: &str, dst: &str) -> Self {
Edge {
src: src.to_string(),
dst: dst.to_string(),
attrs: HashMap::new(),
}
}
pub fn with_attrs(mut self, attrs: &[(&str, &str)]) -> Self {
for &(key, value) in attrs {
self.attrs.insert(key.to_string(), value.to_string());
}
self
}
pub fn get_attr(&self, attr: &str) -> Option<&str> {
self.attrs.get(attr).map(|s| s.as_str())
}
}
impl Edge {
pub fn src(&self) -> &str {
&self.src
}
pub fn dst(&self) -> &str {
&self.dst
}
}
}
}
use graph_items::node::Node;
use graph_items::edge::Edge;
#[derive(Debug, Clone, PartialEq)]
pub struct Graph {
pub nodes: Vec<Node>,
pub edges: Vec<Edge>,
pub attrs: HashMap<String, String>,
}
impl Graph {
pub fn new() -> Self {
Graph {
nodes: Vec::new(),
edges: Vec::new(),
attrs: HashMap::new(),
}
}
pub fn with_nodes(mut self, nodes: &[Node]) -> Self {
self.nodes = nodes.to_vec();
self
}
pub fn with_edges(mut self, edges: &[Edge]) -> Self {
self.edges = edges.to_vec();
self
}
pub fn with_attrs(mut self, attrs: &[(&str, &str)]) -> Self {
for &(key, value) in attrs {
self.attrs.insert(key.to_string(), value.to_string());
}
self
}
pub fn get_node(&self, name: &str) -> Option<&Node> {
self.nodes.iter().find(|node| node.name == name)
}
}
}
测试用例分析
通过查看测试用例,我们可以更好地理解需求:
#[test]
fn test_empty_graph() {
let graph = Graph::new();
assert!(graph.nodes.is_empty());
assert!(graph.edges.is_empty());
assert!(graph.attrs.is_empty());
}
空图应该没有任何节点、边或属性。
#[test]
fn test_graph_with_one_node() {
let nodes = vec![Node::new("a")];
let graph = Graph::new().with_nodes(&nodes);
assert!(graph.edges.is_empty());
assert!(graph.attrs.is_empty());
assert_eq!(graph.nodes, vec![Node::new("a")]);
}
图可以包含节点。
#[test]
fn test_graph_with_one_node_with_keywords() {
let nodes = vec![Node::new("a").with_attrs(&[("color", "green")])];
let graph = Graph::new().with_nodes(&nodes);
assert!(graph.edges.is_empty());
assert!(graph.attrs.is_empty());
assert_eq!(
graph.nodes,
vec![Node::new("a").with_attrs(&[("color", "green")])]
);
}
节点可以有属性。
#[test]
fn test_graph_with_one_edge() {
let edges = vec![Edge::new("a", "b")];
let graph = Graph::new().with_edges(&edges);
assert!(graph.nodes.is_empty());
assert!(graph.attrs.is_empty());
assert_eq!(graph.edges, vec![Edge::new("a", "b")]);
}
图可以包含边。
#[test]
fn test_graph_with_attributes() {
let nodes = vec![
Node::new("a").with_attrs(&[("color", "green")]),
Node::new("c"),
Node::new("b").with_attrs(&[("label", "Beta!")]),
];
let edges = vec![
Edge::new("b", "c"),
Edge::new("a", "b").with_attrs(&[("color", "blue")]),
];
let attrs = vec![("foo", "1"), ("title", "Testing Attrs"), ("bar", "true")];
let expected_attrs = hashmap! {
"foo".to_string() => "1".to_string(),
"title".to_string() => "Testing Attrs".to_string(),
"bar".to_string() => "true".to_string(),
};
let graph = Graph::new()
.with_nodes(&nodes)
.with_edges(&edges)
.with_attrs(&attrs);
assert_eq!(
graph.nodes,
vec![
Node::new("a").with_attrs(&[("color", "green")]),
Node::new("c"),
Node::new("b").with_attrs(&[("label", "Beta!")]),
]
);
assert_eq!(
graph.edges,
vec![
Edge::new("b", "c"),
Edge::new("a", "b").with_attrs(&[("color", "blue")]),
]
);
assert_eq!(graph.attrs, expected_attrs);
}
图可以同时包含节点、边和属性。
#[test]
fn test_graph_stores_attributes() {
let attributes = [("foo", "bar"), ("bat", "baz"), ("bim", "bef")];
let graph = Graph::new().with_nodes(
&["a", "b", "c"]
.iter()
.zip(attributes.iter())
.map(|(name, &attr)| Node::new(&name).with_attrs(&[attr]))
.collect::<Vec<_>>(),
);
assert_eq!(
graph
.get_node("c")
.expect("node must be stored")
.get_attr("bim"),
Some("bef")
);
}
可以通过名称检索节点及其属性。
性能优化版本
考虑性能的优化实现:
pub mod graph {
use std::collections::HashMap;
pub mod graph_items {
pub mod node {
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq)]
pub struct Node {
pub name: String,
pub attrs: HashMap<String, String>,
}
impl Node {
pub fn new(name: &str) -> Self {
Node {
name: name.to_string(),
attrs: HashMap::with_capacity(4), // 预分配容量
}
}
pub fn with_attrs(mut self, attrs: &[(&str, &str)]) -> Self {
self.attrs.reserve(attrs.len()); // 预分配容量
for &(key, value) in attrs {
self.attrs.insert(key.to_string(), value.to_string());
}
self
}
pub fn get_attr(&self, attr: &str) -> Option<&str> {
self.attrs.get(attr).map(|s| s.as_str())
}
// 添加获取名称的方法
pub fn name(&self) -> &str {
&self.name
}
}
}
pub mod edge {
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq)]
pub struct Edge {
src: String,
dst: String,
attrs: HashMap<String, String>,
}
impl Edge {
pub fn new(src: &str, dst: &str) -> Self {
Edge {
src: src.to_string(),
dst: dst.to_string(),
attrs: HashMap::with_capacity(2), // 预分配容量
}
}
pub fn with_attrs(mut self, attrs: &[(&str, &str)]) -> Self {
self.attrs.reserve(attrs.len()); // 预分配容量
for &(key, value) in attrs {
self.attrs.insert(key.to_string(), value.to_string());
}
self
}
pub fn get_attr(&self, attr: &str) -> Option<&str> {
self.attrs.get(attr).map(|s| s.as_str())
}
pub fn src(&self) -> &str {
&self.src
}
pub fn dst(&self) -> &str {
&self.dst
}
}
}
}
use graph_items::node::Node;
use graph_items::edge::Edge;
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq)]
pub struct Graph {
pub nodes: Vec<Node>,
pub edges: Vec<Edge>,
pub attrs: HashMap<String, String>,
// 添加节点索引以提高查找性能
node_index: HashMap<String, usize>,
}
impl Graph {
pub fn new() -> Self {
Graph {
nodes: Vec::new(),
edges: Vec::new(),
attrs: HashMap::new(),
node_index: HashMap::new(),
}
}
pub fn with_nodes(mut self, nodes: &[Node]) -> Self {
self.nodes = nodes.to_vec();
// 构建节点索引
self.node_index.clear();
for (index, node) in self.nodes.iter().enumerate() {
self.node_index.insert(node.name.clone(), index);
}
self
}
pub fn with_edges(mut self, edges: &[Edge]) -> Self {
self.edges = edges.to_vec();
self
}
pub fn with_attrs(mut self, attrs: &[(&str, &str)]) -> Self {
self.attrs.reserve(attrs.len()); // 预分配容量
for &(key, value) in attrs {
self.attrs.insert(key.to_string(), value.to_string());
}
self
}
pub fn get_node(&self, name: &str) -> Option<&Node> {
// 使用索引提高查找性能
self.node_index
.get(name)
.and_then(|&index| self.nodes.get(index))
}
}
}
错误处理和边界情况
考虑更多边界情况的实现:
pub mod graph {
use std::collections::HashMap;
#[derive(Debug, PartialEq)]
pub enum GraphError {
NodeNotFound(String),
DuplicateNode(String),
}
pub mod graph_items {
pub mod node {
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq)]
pub struct Node {
pub name: String,
pub attrs: HashMap<String, String>,
}
impl Node {
pub fn new(name: &str) -> Self {
Node {
name: name.to_string(),
attrs: HashMap::new(),
}
}
pub fn with_attrs(mut self, attrs: &[(&str, &str)]) -> Self {
for &(key, value) in attrs {
self.attrs.insert(key.to_string(), value.to_string());
}
self
}
pub fn get_attr(&self, attr: &str) -> Option<&str> {
self.attrs.get(attr).map(|s| s.as_str())
}
pub fn name(&self) -> &str {
&self.name
}
// 添加属性修改方法
pub fn set_attr(&mut self, key: &str, value: &str) {
self.attrs.insert(key.to_string(), value.to_string());
}
}
}
pub mod edge {
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq)]
pub struct Edge {
src: String,
dst: String,
attrs: HashMap<String, String>,
}
impl Edge {
pub fn new(src: &str, dst: &str) -> Self {
Edge {
src: src.to_string(),
dst: dst.to_string(),
attrs: HashMap::new(),
}
}
pub fn with_attrs(mut self, attrs: &[(&str, &str)]) -> Self {
for &(key, value) in attrs {
self.attrs.insert(key.to_string(), value.to_string());
}
self
}
pub fn get_attr(&self, attr: &str) -> Option<&str> {
self.attrs.get(attr).map(|s| s.as_str())
}
pub fn src(&self) -> &str {
&self.src
}
pub fn dst(&self) -> &str {
&self.dst
}
// 添加属性修改方法
pub fn set_attr(&mut self, key: &str, value: &str) {
self.attrs.insert(key.to_string(), value.to_string());
}
}
}
}
use graph_items::node::Node;
use graph_items::edge::Edge;
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq)]
pub struct Graph {
pub nodes: Vec<Node>,
pub edges: Vec<Edge>,
pub attrs: HashMap<String, String>,
node_index: HashMap<String, usize>,
}
impl Graph {
pub fn new() -> Self {
Graph {
nodes: Vec::new(),
edges: Vec::new(),
attrs: HashMap::new(),
node_index: HashMap::new(),
}
}
pub fn with_nodes(mut self, nodes: &[Node]) -> Self {
self.nodes = nodes.to_vec();
self.rebuild_node_index();
self
}
pub fn with_edges(mut self, edges: &[Edge]) -> Self {
self.edges = edges.to_vec();
self
}
pub fn with_attrs(mut self, attrs: &[(&str, &str)]) -> Self {
for &(key, value) in attrs {
self.attrs.insert(key.to_string(), value.to_string());
}
self
}
pub fn get_node(&self, name: &str) -> Option<&Node> {
self.node_index
.get(name)
.and_then(|&index| self.nodes.get(index))
}
// 添加节点
pub fn add_node(&mut self, node: Node) -> Result<(), GraphError> {
if self.node_index.contains_key(&node.name) {
return Err(GraphError::DuplicateNode(node.name));
}
let index = self.nodes.len();
self.node_index.insert(node.name.clone(), index);
self.nodes.push(node);
Ok(())
}
// 添加边
pub fn add_edge(&mut self, edge: Edge) {
self.edges.push(edge);
}
// 添加属性
pub fn add_attr(&mut self, key: &str, value: &str) {
self.attrs.insert(key.to_string(), value.to_string());
}
// 重建节点索引
fn rebuild_node_index(&mut self) {
self.node_index.clear();
for (index, node) in self.nodes.iter().enumerate() {
self.node_index.insert(node.name.clone(), index);
}
}
}
}
扩展功能
基于基础实现,我们可以添加更多功能:
pub mod graph {
use std::collections::HashMap;
pub mod graph_items {
pub mod node {
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq)]
pub struct Node {
pub name: String,
pub attrs: HashMap<String, String>,
}
impl Node {
pub fn new(name: &str) -> Self {
Node {
name: name.to_string(),
attrs: HashMap::new(),
}
}
pub fn with_attrs(mut self, attrs: &[(&str, &str)]) -> Self {
for &(key, value) in attrs {
self.attrs.insert(key.to_string(), value.to_string());
}
self
}
pub fn get_attr(&self, attr: &str) -> Option<&str> {
self.attrs.get(attr).map(|s| s.as_str())
}
pub fn name(&self) -> &str {
&self.name
}
pub fn set_attr(&mut self, key: &str, value: &str) {
self.attrs.insert(key.to_string(), value.to_string());
}
// 获取所有属性
pub fn attrs(&self) -> &HashMap<String, String> {
&self.attrs
}
}
}
pub mod edge {
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq)]
pub struct Edge {
src: String,
dst: String,
attrs: HashMap<String, String>,
}
impl Edge {
pub fn new(src: &str, dst: &str) -> Self {
Edge {
src: src.to_string(),
dst: dst.to_string(),
attrs: HashMap::new(),
}
}
pub fn with_attrs(mut self, attrs: &[(&str, &str)]) -> Self {
for &(key, value) in attrs {
self.attrs.insert(key.to_string(), value.to_string());
}
self
}
pub fn get_attr(&self, attr: &str) -> Option<&str> {
self.attrs.get(attr).map(|s| s.as_str())
}
pub fn src(&self) -> &str {
&self.src
}
pub fn dst(&self) -> &str {
&self.dst
}
pub fn set_attr(&mut self, key: &str, value: &str) {
self.attrs.insert(key.to_string(), value.to_string());
}
// 获取所有属性
pub fn attrs(&self) -> &HashMap<String, String> {
&self.attrs
}
}
}
}
use graph_items::node::Node;
use graph_items::edge::Edge;
use std::collections::HashMap;
#[derive(Debug, Clone, PartialEq)]
pub struct Graph {
pub nodes: Vec<Node>,
pub edges: Vec<Edge>,
pub attrs: HashMap<String, String>,
node_index: HashMap<String, usize>,
}
impl Graph {
pub fn new() -> Self {
Graph {
nodes: Vec::new(),
edges: Vec::new(),
attrs: HashMap::new(),
node_index: HashMap::new(),
}
}
pub fn with_nodes(mut self, nodes: &[Node]) -> Self {
self.nodes = nodes.to_vec();
self.rebuild_node_index();
self
}
pub fn with_edges(mut self, edges: &[Edge]) -> Self {
self.edges = edges.to_vec();
self
}
pub fn with_attrs(mut self, attrs: &[(&str, &str)]) -> Self {
for &(key, value) in attrs {
self.attrs.insert(key.to_string(), value.to_string());
}
self
}
pub fn get_node(&self, name: &str) -> Option<&Node> {
self.node_index
.get(name)
.and_then(|&index| self.nodes.get(index))
}
// 生成DOT语言表示
pub fn to_dot(&self) -> String {
let mut result = String::from("graph {\n");
// 添加图属性
for (key, value) in &self.attrs {
result.push_str(&format!(" {}={};\n", key, value));
}
// 添加节点
for node in &self.nodes {
if node.attrs.is_empty() {
result.push_str(&format!(" {};\n", node.name));
} else {
let attrs: Vec<String> = node.attrs
.iter()
.map(|(k, v)| format!("{}={}", k, v))
.collect();
result.push_str(&format!(" {} [{}];\n", node.name, attrs.join(", ")));
}
}
// 添加边
for edge in &self.edges {
if edge.attrs.is_empty() {
result.push_str(&format!(" {} -- {};\n", edge.src(), edge.dst()));
} else {
let attrs: Vec<String> = edge.attrs
.iter()
.map(|(k, v)| format!("{}={}", k, v))
.collect();
result.push_str(&format!(" {} -- {} [{}];\n", edge.src(), edge.dst(), attrs.join(", ")));
}
}
result.push_str("}\n");
result
}
// 从DOT字符串解析(简化版)
pub fn from_dot(dot_str: &str) -> Result<Self, &'static str> {
// 这是一个简化的实现,实际解析DOT语言会更复杂
if !dot_str.contains("graph {") {
return Err("Invalid DOT format");
}
Ok(Graph::new())
}
// 获取所有节点
pub fn nodes(&self) -> &[Node] {
&self.nodes
}
// 获取所有边
pub fn edges(&self) -> &[Edge] {
&self.edges
}
// 获取图属性
pub fn attrs(&self) -> &HashMap<String, String> {
&self.attrs
}
fn rebuild_node_index(&mut self) {
self.node_index.clear();
for (index, node) in self.nodes.iter().enumerate() {
self.node_index.insert(node.name.clone(), index);
}
}
}
}
实际应用场景
DOT DSL在实际开发中有以下应用:
- 图形可视化:与Graphviz集成生成图形可视化
- 依赖关系图:表示软件模块间的依赖关系
- 网络拓扑:描述网络节点和连接关系
- 状态机:定义有限状态机的状态和转换
- 流程图:生成业务流程图
- 社交网络:表示用户间的关系网络
- 电路设计:描述电子电路的连接关系
算法复杂度分析
-
时间复杂度:
- 节点查找:O(1)(使用哈希索引)
- 添加节点:O(1)
- 添加边:O(1)
- 生成DOT表示:O(n+m),其中n是节点数,m是边数
-
空间复杂度:O(n+m+k)
- n个节点
- m条边
- k个属性
与其他实现方式的比较
// 使用宏简化构建过程
macro_rules! graph {
(nodes: [$($node:expr),*], edges: [$($edge:expr),*], attrs: [$($attr:tt),*]) => {
{
let nodes = vec![$(Node::new($node)),*];
let edges = vec![$($edge),*];
let attrs = vec![$(stringify!($attr).split('=').collect::<Vec<&str>>().as_slice()),*];
Graph::new()
.with_nodes(&nodes)
.with_edges(&edges)
.with_attrs(&attrs.iter().map(|a| (a[0], a[1])).collect::<Vec<_>>())
}
};
(nodes: [$($node:expr),*], edges: [$($edge:expr),*]) => {
{
let nodes = vec![$(Node::new($node)),*];
let edges = vec![$($edge),*];
Graph::new()
.with_nodes(&nodes)
.with_edges(&edges)
}
};
}
// 使用Builder模式的替代实现
pub struct GraphBuilder {
nodes: Vec<Node>,
edges: Vec<Edge>,
attrs: HashMap<String, String>,
}
impl GraphBuilder {
pub fn new() -> Self {
GraphBuilder {
nodes: Vec::new(),
edges: Vec::new(),
attrs: HashMap::new(),
}
}
pub fn node(mut self, name: &str) -> Self {
self.nodes.push(Node::new(name));
self
}
pub fn edge(mut self, src: &str, dst: &str) -> Self {
self.edges.push(Edge::new(src, dst));
self
}
pub fn attr(mut self, key: &str, value: &str) -> Self {
self.attrs.insert(key.to_string(), value.to_string());
self
}
pub fn build(self) -> Graph {
Graph {
nodes: self.nodes,
edges: self.edges,
attrs: self.attrs,
node_index: HashMap::new(),
}
}
}
总结
通过 dot-dsl 练习,我们学到了:
- 领域特定语言:掌握了DSL设计的基本原则
- 构建器模式:理解了流畅API的设计方法
- 模块系统:学会了Rust中的模块组织方式
- 数据结构:熟练使用HashMap进行高效数据存储
- 面向对象设计:理解了Rust中面向对象的设计模式
- 性能优化:了解了预分配和索引优化等技巧
这些技能在实际开发中非常有用,特别是在设计API、构建配置系统和实现领域特定语言时。DOT DSL虽然是一个相对简单的练习,但它涉及到了API设计、模块组织和数据结构设计等许多核心概念,是学习Rust系统设计的良好起点。
通过这个练习,我们也看到了Rust在DSL设计和API构建方面的强大能力,以及如何用安全且高效的方式实现复杂的系统。这种结合了安全性和性能的语言特性正是Rust的魅力所在。
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念,把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起,为开发者提供从开发、训练到部署的一站式体验。
更多推荐
所有评论(0)