1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113
 114
 115
 116
 117
 118
 119
 120
 121
 122
 123
 124
 125
 126
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146
 147
 148
 149
 150
 151
 152
 153
 154
 155
 156
 157
 158
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246
 247
 248
 249
 250
 251
 252
 253
 254
 255
 256
 257
 258
 259
 260
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286
 287
 288
 289
 290
 291
 292
 293
 294
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
//! Generate files suitable for use with [Graphviz](http://www.graphviz.org/)
//!
//! The `render` function generates output (e.g., an `output.dot` file) for
//! use with [Graphviz](http://www.graphviz.org/) by walking a labeled
//! graph. (Graphviz can then automatically lay out the nodes and edges
//! of the graph, and also optionally render the graph as an image or
//! other [output formats](
//! http://www.graphviz.org/content/output-formats), such as SVG.)
//!
//! Rather than impose some particular graph data structure on clients,
//! this library exposes two traits that clients can implement on their
//! own structs before handing them over to the rendering function.
//!
//! Note: This library does not yet provide access to the full
//! expressiveness of the [DOT language](
//! http://www.graphviz.org/doc/info/lang.html). For example, there are
//! many [attributes](http://www.graphviz.org/content/attrs) related to
//! providing layout hints (e.g., left-to-right versus top-down, which
//! algorithm to use, etc). The current intention of this library is to
//! emit a human-readable .dot file with very regular structure suitable
//! for easy post-processing.
//!
//! # Examples
//!
//! The first example uses a very simple graph representation: a list of
//! pairs of ints, representing the edges (the node set is implicit).
//! Each node label is derived directly from the int representing the node,
//! while the edge labels are all empty strings.
//!
//! This example also illustrates how to use `Cow<[T]>` to return
//! an owned vector or a borrowed slice as appropriate: we construct the
//! node vector from scratch, but borrow the edge list (rather than
//! constructing a copy of all the edges from scratch).
//!
//! The output from this example renders five nodes, with the first four
//! forming a diamond-shaped acyclic graph and then pointing to the fifth
//! which is cyclic.
//!
//! ```rust
//! #![feature(rustc_private)]
//!
//! use std::io::Write;
//! use graphviz as dot;
//!
//! type Nd = isize;
//! type Ed = (isize,isize);
//! struct Edges(Vec<Ed>);
//!
//! pub fn render_to<W: Write>(output: &mut W) {
//!     let edges = Edges(vec![(0,1), (0,2), (1,3), (2,3), (3,4), (4,4)]);
//!     dot::render(&edges, output).unwrap()
//! }
//!
//! impl<'a> dot::Labeller<'a> for Edges {
//!     type Node = Nd;
//!     type Edge = Ed;
//!     fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example1").unwrap() }
//!
//!     fn node_id(&'a self, n: &Nd) -> dot::Id<'a> {
//!         dot::Id::new(format!("N{}", *n)).unwrap()
//!     }
//! }
//!
//! impl<'a> dot::GraphWalk<'a> for Edges {
//!     type Node = Nd;
//!     type Edge = Ed;
//!     fn nodes(&self) -> dot::Nodes<'a,Nd> {
//!         // (assumes that |N| \approxeq |E|)
//!         let &Edges(ref v) = self;
//!         let mut nodes = Vec::with_capacity(v.len());
//!         for &(s,t) in v {
//!             nodes.push(s); nodes.push(t);
//!         }
//!         nodes.sort();
//!         nodes.dedup();
//!         nodes.into()
//!     }
//!
//!     fn edges(&'a self) -> dot::Edges<'a,Ed> {
//!         let &Edges(ref edges) = self;
//!         (&edges[..]).into()
//!     }
//!
//!     fn source(&self, e: &Ed) -> Nd { let &(s,_) = e; s }
//!
//!     fn target(&self, e: &Ed) -> Nd { let &(_,t) = e; t }
//! }
//!
//! # pub fn main() { render_to(&mut Vec::new()) }
//! ```
//!
//! ```no_run
//! # pub fn render_to<W:std::io::Write>(output: &mut W) { unimplemented!() }
//! pub fn main() {
//!     use std::fs::File;
//!     let mut f = File::create("example1.dot").unwrap();
//!     render_to(&mut f)
//! }
//! ```
//!
//! Output from first example (in `example1.dot`):
//!
//! ```dot
//! digraph example1 {
//!     N0[label="N0"];
//!     N1[label="N1"];
//!     N2[label="N2"];
//!     N3[label="N3"];
//!     N4[label="N4"];
//!     N0 -> N1[label=""];
//!     N0 -> N2[label=""];
//!     N1 -> N3[label=""];
//!     N2 -> N3[label=""];
//!     N3 -> N4[label=""];
//!     N4 -> N4[label=""];
//! }
//! ```
//!
//! The second example illustrates using `node_label` and `edge_label` to
//! add labels to the nodes and edges in the rendered graph. The graph
//! here carries both `nodes` (the label text to use for rendering a
//! particular node), and `edges` (again a list of `(source,target)`
//! indices).
//!
//! This example also illustrates how to use a type (in this case the edge
//! type) that shares substructure with the graph: the edge type here is a
//! direct reference to the `(source,target)` pair stored in the graph's
//! internal vector (rather than passing around a copy of the pair
//! itself). Note that this implies that `fn edges(&'a self)` must
//! construct a fresh `Vec<&'a (usize,usize)>` from the `Vec<(usize,usize)>`
//! edges stored in `self`.
//!
//! Since both the set of nodes and the set of edges are always
//! constructed from scratch via iterators, we use the `collect()` method
//! from the `Iterator` trait to collect the nodes and edges into freshly
//! constructed growable `Vec` values (rather than using `Cow` as in the
//! first example above).
//!
//! The output from this example renders four nodes that make up the
//! Hasse-diagram for the subsets of the set `{x, y}`. Each edge is
//! labeled with the &sube; character (specified using the HTML character
//! entity `&sube`).
//!
//! ```rust
//! #![feature(rustc_private)]
//!
//! use std::io::Write;
//! use graphviz as dot;
//!
//! type Nd = usize;
//! type Ed<'a> = &'a (usize, usize);
//! struct Graph { nodes: Vec<&'static str>, edges: Vec<(usize,usize)> }
//!
//! pub fn render_to<W: Write>(output: &mut W) {
//!     let nodes = vec!["{x,y}","{x}","{y}","{}"];
//!     let edges = vec![(0,1), (0,2), (1,3), (2,3)];
//!     let graph = Graph { nodes: nodes, edges: edges };
//!
//!     dot::render(&graph, output).unwrap()
//! }
//!
//! impl<'a> dot::Labeller<'a> for Graph {
//!     type Node = Nd;
//!     type Edge = Ed<'a>;
//!     fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example2").unwrap() }
//!     fn node_id(&'a self, n: &Nd) -> dot::Id<'a> {
//!         dot::Id::new(format!("N{}", n)).unwrap()
//!     }
//!     fn node_label<'b>(&'b self, n: &Nd) -> dot::LabelText<'b> {
//!         dot::LabelText::LabelStr(self.nodes[*n].into())
//!     }
//!     fn edge_label<'b>(&'b self, _: &Ed) -> dot::LabelText<'b> {
//!         dot::LabelText::LabelStr("&sube;".into())
//!     }
//! }
//!
//! impl<'a> dot::GraphWalk<'a> for Graph {
//!     type Node = Nd;
//!     type Edge = Ed<'a>;
//!     fn nodes(&self) -> dot::Nodes<'a,Nd> { (0..self.nodes.len()).collect() }
//!     fn edges(&'a self) -> dot::Edges<'a,Ed<'a>> { self.edges.iter().collect() }
//!     fn source(&self, e: &Ed) -> Nd { let & &(s,_) = e; s }
//!     fn target(&self, e: &Ed) -> Nd { let & &(_,t) = e; t }
//! }
//!
//! # pub fn main() { render_to(&mut Vec::new()) }
//! ```
//!
//! ```no_run
//! # pub fn render_to<W:std::io::Write>(output: &mut W) { unimplemented!() }
//! pub fn main() {
//!     use std::fs::File;
//!     let mut f = File::create("example2.dot").unwrap();
//!     render_to(&mut f)
//! }
//! ```
//!
//! The third example is similar to the second, except now each node and
//! edge now carries a reference to the string label for each node as well
//! as that node's index. (This is another illustration of how to share
//! structure with the graph itself, and why one might want to do so.)
//!
//! The output from this example is the same as the second example: the
//! Hasse-diagram for the subsets of the set `{x, y}`.
//!
//! ```rust
//! #![feature(rustc_private)]
//!
//! use std::io::Write;
//! use graphviz as dot;
//!
//! type Nd<'a> = (usize, &'a str);
//! type Ed<'a> = (Nd<'a>, Nd<'a>);
//! struct Graph { nodes: Vec<&'static str>, edges: Vec<(usize,usize)> }
//!
//! pub fn render_to<W: Write>(output: &mut W) {
//!     let nodes = vec!["{x,y}","{x}","{y}","{}"];
//!     let edges = vec![(0,1), (0,2), (1,3), (2,3)];
//!     let graph = Graph { nodes: nodes, edges: edges };
//!
//!     dot::render(&graph, output).unwrap()
//! }
//!
//! impl<'a> dot::Labeller<'a> for Graph {
//!     type Node = Nd<'a>;
//!     type Edge = Ed<'a>;
//!     fn graph_id(&'a self) -> dot::Id<'a> { dot::Id::new("example3").unwrap() }
//!     fn node_id(&'a self, n: &Nd<'a>) -> dot::Id<'a> {
//!         dot::Id::new(format!("N{}", n.0)).unwrap()
//!     }
//!     fn node_label<'b>(&'b self, n: &Nd<'b>) -> dot::LabelText<'b> {
//!         let &(i, _) = n;
//!         dot::LabelText::LabelStr(self.nodes[i].into())
//!     }
//!     fn edge_label<'b>(&'b self, _: &Ed<'b>) -> dot::LabelText<'b> {
//!         dot::LabelText::LabelStr("&sube;".into())
//!     }
//! }
//!
//! impl<'a> dot::GraphWalk<'a> for Graph {
//!     type Node = Nd<'a>;
//!     type Edge = Ed<'a>;
//!     fn nodes(&'a self) -> dot::Nodes<'a,Nd<'a>> {
//!         self.nodes.iter().map(|s| &s[..]).enumerate().collect()
//!     }
//!     fn edges(&'a self) -> dot::Edges<'a,Ed<'a>> {
//!         self.edges.iter()
//!             .map(|&(i,j)|((i, &self.nodes[i][..]),
//!                           (j, &self.nodes[j][..])))
//!             .collect()
//!     }
//!     fn source(&self, e: &Ed<'a>) -> Nd<'a> { let &(s,_) = e; s }
//!     fn target(&self, e: &Ed<'a>) -> Nd<'a> { let &(_,t) = e; t }
//! }
//!
//! # pub fn main() { render_to(&mut Vec::new()) }
//! ```
//!
//! ```no_run
//! # pub fn render_to<W:std::io::Write>(output: &mut W) { unimplemented!() }
//! pub fn main() {
//!     use std::fs::File;
//!     let mut f = File::create("example3.dot").unwrap();
//!     render_to(&mut f)
//! }
//! ```
//!
//! # References
//!
//! * [Graphviz](http://www.graphviz.org/)
//!
//! * [DOT language](http://www.graphviz.org/doc/info/lang.html)

#![doc(html_root_url = "https://doc.rust-lang.org/nightly/",
       test(attr(allow(unused_variables), deny(warnings))))]

#![deny(rust_2018_idioms)]

#![feature(rustc_private, nll)]

use LabelText::*;

use std::borrow::Cow;
use std::io::prelude::*;
use std::io;

/// The text for a graphviz label on a node or edge.
pub enum LabelText<'a> {
    /// This kind of label preserves the text directly as is.
    ///
    /// Occurrences of backslashes (`\`) are escaped, and thus appear
    /// as backslashes in the rendered label.
    LabelStr(Cow<'a, str>),

    /// This kind of label uses the graphviz label escString type:
    /// <http://www.graphviz.org/content/attrs#kescString>
    ///
    /// Occurrences of backslashes (`\`) are not escaped; instead they
    /// are interpreted as initiating an escString escape sequence.
    ///
    /// Escape sequences of particular interest: in addition to `\n`
    /// to break a line (centering the line preceding the `\n`), there
    /// are also the escape sequences `\l` which left-justifies the
    /// preceding line and `\r` which right-justifies it.
    EscStr(Cow<'a, str>),

    /// This uses a graphviz [HTML string label][html]. The string is
    /// printed exactly as given, but between `<` and `>`. **No
    /// escaping is performed.**
    ///
    /// [html]: http://www.graphviz.org/content/node-shapes#html
    HtmlStr(Cow<'a, str>),
}

/// The style for a node or edge.
/// See <http://www.graphviz.org/doc/info/attrs.html#k:style> for descriptions.
/// Note that some of these are not valid for edges.
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub enum Style {
    None,
    Solid,
    Dashed,
    Dotted,
    Bold,
    Rounded,
    Diagonals,
    Filled,
    Striped,
    Wedged,
}

impl Style {
    pub fn as_slice(self) -> &'static str {
        match self {
            Style::None => "",
            Style::Solid => "solid",
            Style::Dashed => "dashed",
            Style::Dotted => "dotted",
            Style::Bold => "bold",
            Style::Rounded => "rounded",
            Style::Diagonals => "diagonals",
            Style::Filled => "filled",
            Style::Striped => "striped",
            Style::Wedged => "wedged",
        }
    }
}

// There is a tension in the design of the labelling API.
//
// For example, I considered making a `Labeller<T>` trait that
// provides labels for `T`, and then making the graph type `G`
// implement `Labeller<Node>` and `Labeller<Edge>`. However, this is
// not possible without functional dependencies. (One could work
// around that, but I did not explore that avenue heavily.)
//
// Another approach that I actually used for a while was to make a
// `Label<Context>` trait that is implemented by the client-specific
// Node and Edge types (as well as an implementation on Graph itself
// for the overall name for the graph). The main disadvantage of this
// second approach (compared to having the `G` type parameter
// implement a Labelling service) that I have encountered is that it
// makes it impossible to use types outside of the current crate
// directly as Nodes/Edges; you need to wrap them in newtype'd
// structs. See e.g., the `No` and `Ed` structs in the examples. (In
// practice clients using a graph in some other crate would need to
// provide some sort of adapter shim over the graph anyway to
// interface with this library).
//
// Another approach would be to make a single `Labeller<N,E>` trait
// that provides three methods (graph_label, node_label, edge_label),
// and then make `G` implement `Labeller<N,E>`. At first this did not
// appeal to me, since I had thought I would need separate methods on
// each data variant for dot-internal identifiers versus user-visible
// labels. However, the identifier/label distinction only arises for
// nodes; graphs themselves only have identifiers, and edges only have
// labels.
//
// So in the end I decided to use the third approach described above.

/// `Id` is a Graphviz `ID`.
pub struct Id<'a> {
    name: Cow<'a, str>,
}

impl<'a> Id<'a> {
    /// Creates an `Id` named `name`.
    ///
    /// The caller must ensure that the input conforms to an
    /// identifier format: it must be a non-empty string made up of
    /// alphanumeric or underscore characters, not beginning with a
    /// digit (i.e., the regular expression `[a-zA-Z_][a-zA-Z_0-9]*`).
    ///
    /// (Note: this format is a strict subset of the `ID` format
    /// defined by the DOT language. This function may change in the
    /// future to accept a broader subset, or the entirety, of DOT's
    /// `ID` format.)
    ///
    /// Passing an invalid string (containing spaces, brackets,
    /// quotes, ...) will return an empty `Err` value.
    pub fn new<Name: Into<Cow<'a, str>>>(name: Name) -> Result<Id<'a>, ()> {
        let name = name.into();
        match name.chars().next() {
            Some(c) if c.is_ascii_alphabetic() || c == '_' => {}
            _ => return Err(()),
        }
        if !name.chars().all(|c| c.is_ascii_alphanumeric() || c == '_' ) {
            return Err(());
        }

        Ok(Id { name })
    }

    pub fn as_slice(&'a self) -> &'a str {
        &*self.name
    }

    pub fn name(self) -> Cow<'a, str> {
        self.name
    }
}

/// Each instance of a type that implements `Label<C>` maps to a
/// unique identifier with respect to `C`, which is used to identify
/// it in the generated .dot file. They can also provide more
/// elaborate (and non-unique) label text that is used in the graphviz
/// rendered output.

/// The graph instance is responsible for providing the DOT compatible
/// identifiers for the nodes and (optionally) rendered labels for the nodes and
/// edges, as well as an identifier for the graph itself.
pub trait Labeller<'a> {
    type Node;
    type Edge;

    /// Must return a DOT compatible identifier naming the graph.
    fn graph_id(&'a self) -> Id<'a>;

    /// Maps `n` to a unique identifier with respect to `self`. The
    /// implementor is responsible for ensuring that the returned name
    /// is a valid DOT identifier.
    fn node_id(&'a self, n: &Self::Node) -> Id<'a>;

    /// Maps `n` to one of the [graphviz `shape` names][1]. If `None`
    /// is returned, no `shape` attribute is specified.
    ///
    /// [1]: http://www.graphviz.org/content/node-shapes
    fn node_shape(&'a self, _node: &Self::Node) -> Option<LabelText<'a>> {
        None
    }

    /// Maps `n` to a label that will be used in the rendered output.
    /// The label need not be unique, and may be the empty string; the
    /// default is just the output from `node_id`.
    fn node_label(&'a self, n: &Self::Node) -> LabelText<'a> {
        LabelStr(self.node_id(n).name)
    }

    /// Maps `e` to a label that will be used in the rendered output.
    /// The label need not be unique, and may be the empty string; the
    /// default is in fact the empty string.
    fn edge_label(&'a self, _e: &Self::Edge) -> LabelText<'a> {
        LabelStr("".into())
    }

    /// Maps `n` to a style that will be used in the rendered output.
    fn node_style(&'a self, _n: &Self::Node) -> Style {
        Style::None
    }

    /// Maps `e` to a style that will be used in the rendered output.
    fn edge_style(&'a self, _e: &Self::Edge) -> Style {
        Style::None
    }
}

/// Escape tags in such a way that it is suitable for inclusion in a
/// Graphviz HTML label.
pub fn escape_html(s: &str) -> String {
    s.replace("&", "&amp;")
     .replace("\"", "&quot;")
     .replace("<", "&lt;")
     .replace(">", "&gt;")
}

impl<'a> LabelText<'a> {
    pub fn label<S: Into<Cow<'a, str>>>(s: S) -> LabelText<'a> {
        LabelStr(s.into())
    }

    pub fn escaped<S: Into<Cow<'a, str>>>(s: S) -> LabelText<'a> {
        EscStr(s.into())
    }

    pub fn html<S: Into<Cow<'a, str>>>(s: S) -> LabelText<'a> {
        HtmlStr(s.into())
    }

    fn escape_char<F>(c: char, mut f: F)
        where F: FnMut(char)
    {
        match c {
            // not escaping \\, since Graphviz escString needs to
            // interpret backslashes; see EscStr above.
            '\\' => f(c),
            _ => {
                for c in c.escape_default() {
                    f(c)
                }
            }
        }
    }
    fn escape_str(s: &str) -> String {
        let mut out = String::with_capacity(s.len());
        for c in s.chars() {
            LabelText::escape_char(c, |c| out.push(c));
        }
        out
    }

    /// Renders text as string suitable for a label in a .dot file.
    /// This includes quotes or suitable delimiters.
    pub fn to_dot_string(&self) -> String {
        match *self {
            LabelStr(ref s) => format!("\"{}\"", s.escape_default()),
            EscStr(ref s) => format!("\"{}\"", LabelText::escape_str(&s)),
            HtmlStr(ref s) => format!("<{}>", s),
        }
    }

    /// Decomposes content into string suitable for making EscStr that
    /// yields same content as self. The result obeys the law
    /// render(`lt`) == render(`EscStr(lt.pre_escaped_content())`) for
    /// all `lt: LabelText`.
    fn pre_escaped_content(self) -> Cow<'a, str> {
        match self {
            EscStr(s) => s,
            LabelStr(s) => {
                if s.contains('\\') {
                    (&*s).escape_default().to_string().into()
                } else {
                    s
                }
            }
            HtmlStr(s) => s,
        }
    }

    /// Puts `prefix` on a line above this label, with a blank line separator.
    pub fn prefix_line(self, prefix: LabelText<'_>) -> LabelText<'static> {
        prefix.suffix_line(self)
    }

    /// Puts `suffix` on a line below this label, with a blank line separator.
    pub fn suffix_line(self, suffix: LabelText<'_>) -> LabelText<'static> {
        let mut prefix = self.pre_escaped_content().into_owned();
        let suffix = suffix.pre_escaped_content();
        prefix.push_str(r"\n\n");
        prefix.push_str(&suffix);
        EscStr(prefix.into())
    }
}

pub type Nodes<'a,N> = Cow<'a,[N]>;
pub type Edges<'a,E> = Cow<'a,[E]>;

// (The type parameters in GraphWalk should be associated items,
// when/if Rust supports such.)

/// GraphWalk is an abstraction over a directed graph = (nodes,edges)
/// made up of node handles `N` and edge handles `E`, where each `E`
/// can be mapped to its source and target nodes.
///
/// The lifetime parameter `'a` is exposed in this trait (rather than
/// introduced as a generic parameter on each method declaration) so
/// that a client impl can choose `N` and `E` that have substructure
/// that is bound by the self lifetime `'a`.
///
/// The `nodes` and `edges` method each return instantiations of
/// `Cow<[T]>` to leave implementors the freedom to create
/// entirely new vectors or to pass back slices into internally owned
/// vectors.
pub trait GraphWalk<'a> {
    type Node: Clone;
    type Edge: Clone;

    /// Returns all the nodes in this graph.
    fn nodes(&'a self) -> Nodes<'a, Self::Node>;
    /// Returns all of the edges in this graph.
    fn edges(&'a self) -> Edges<'a, Self::Edge>;
    /// The source node for `edge`.
    fn source(&'a self, edge: &Self::Edge) -> Self::Node;
    /// The target node for `edge`.
    fn target(&'a self, edge: &Self::Edge) -> Self::Node;
}

#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub enum RenderOption {
    NoEdgeLabels,
    NoNodeLabels,
    NoEdgeStyles,
    NoNodeStyles,
}

/// Returns vec holding all the default render options.
pub fn default_options() -> Vec<RenderOption> {
    vec![]
}

/// Renders directed graph `g` into the writer `w` in DOT syntax.
/// (Simple wrapper around `render_opts` that passes a default set of options.)
pub fn render<'a,N,E,G,W>(g: &'a G, w: &mut W) -> io::Result<()>
    where N: Clone + 'a,
          E: Clone + 'a,
          G: Labeller<'a, Node=N, Edge=E> + GraphWalk<'a, Node=N, Edge=E>,
          W: Write
{
    render_opts(g, w, &[])
}

/// Renders directed graph `g` into the writer `w` in DOT syntax.
/// (Main entry point for the library.)
pub fn render_opts<'a, N, E, G, W>(g: &'a G,
                                   w: &mut W,
                                   options: &[RenderOption])
                                   -> io::Result<()>
    where N: Clone + 'a,
          E: Clone + 'a,
          G: Labeller<'a, Node=N, Edge=E> + GraphWalk<'a, Node=N, Edge=E>,
          W: Write
{
    writeln!(w, "digraph {} {{", g.graph_id().as_slice())?;
    for n in g.nodes().iter() {
        write!(w, "    ")?;
        let id = g.node_id(n);

        let escaped = &g.node_label(n).to_dot_string();

        let mut text = Vec::new();
        write!(text, "{}", id.as_slice()).unwrap();

        if !options.contains(&RenderOption::NoNodeLabels) {
            write!(text, "[label={}]", escaped).unwrap();
        }

        let style = g.node_style(n);
        if !options.contains(&RenderOption::NoNodeStyles) && style != Style::None {
            write!(text, "[style=\"{}\"]", style.as_slice()).unwrap();
        }

        if let Some(s) = g.node_shape(n) {
            write!(text, "[shape={}]", &s.to_dot_string()).unwrap();
        }

        writeln!(text, ";").unwrap();
        w.write_all(&text[..])?;
    }

    for e in g.edges().iter() {
        let escaped_label = &g.edge_label(e).to_dot_string();
        write!(w, "    ")?;
        let source = g.source(e);
        let target = g.target(e);
        let source_id = g.node_id(&source);
        let target_id = g.node_id(&target);

        let mut text = Vec::new();
        write!(text, "{} -> {}", source_id.as_slice(), target_id.as_slice()).unwrap();

        if !options.contains(&RenderOption::NoEdgeLabels) {
            write!(text, "[label={}]", escaped_label).unwrap();
        }

        let style = g.edge_style(e);
        if !options.contains(&RenderOption::NoEdgeStyles) && style != Style::None {
            write!(text, "[style=\"{}\"]", style.as_slice()).unwrap();
        }

        writeln!(text, ";").unwrap();
        w.write_all(&text[..])?;
    }

    writeln!(w, "}}")
}

#[cfg(test)]
mod tests {
    use NodeLabels::*;
    use super::{Id, Labeller, Nodes, Edges, GraphWalk, render, Style};
    use super::LabelText::{self, LabelStr, EscStr, HtmlStr};
    use std::io;
    use std::io::prelude::*;

    /// each node is an index in a vector in the graph.
    type Node = usize;
    struct Edge {
        from: usize,
        to: usize,
        label: &'static str,
        style: Style,
    }

    fn edge(from: usize, to: usize, label: &'static str, style: Style) -> Edge {
        Edge {
            from,
            to,
            label,
            style,
        }
    }

    struct LabelledGraph {
        /// The name for this graph. Used for labeling generated `digraph`.
        name: &'static str,

        /// Each node is an index into `node_labels`; these labels are
        /// used as the label text for each node. (The node *names*,
        /// which are unique identifiers, are derived from their index
        /// in this array.)
        ///
        /// If a node maps to None here, then just use its name as its
        /// text.
        node_labels: Vec<Option<&'static str>>,

        node_styles: Vec<Style>,

        /// Each edge relates a from-index to a to-index along with a
        /// label; `edges` collects them.
        edges: Vec<Edge>,
    }

    // A simple wrapper around LabelledGraph that forces the labels to
    // be emitted as EscStr.
    struct LabelledGraphWithEscStrs {
        graph: LabelledGraph,
    }

    enum NodeLabels<L> {
        AllNodesLabelled(Vec<L>),
        UnlabelledNodes(usize),
        SomeNodesLabelled(Vec<Option<L>>),
    }

    type Trivial = NodeLabels<&'static str>;

    impl NodeLabels<&'static str> {
        fn to_opt_strs(self) -> Vec<Option<&'static str>> {
            match self {
                UnlabelledNodes(len) => vec![None; len],
                AllNodesLabelled(lbls) => lbls.into_iter().map(|l| Some(l)).collect(),
                SomeNodesLabelled(lbls) => lbls.into_iter().collect(),
            }
        }

        fn len(&self) -> usize {
            match self {
                &UnlabelledNodes(len) => len,
                &AllNodesLabelled(ref lbls) => lbls.len(),
                &SomeNodesLabelled(ref lbls) => lbls.len(),
            }
        }
    }

    impl LabelledGraph {
        fn new(name: &'static str,
               node_labels: Trivial,
               edges: Vec<Edge>,
               node_styles: Option<Vec<Style>>)
               -> LabelledGraph {
            let count = node_labels.len();
            LabelledGraph {
                name,
                node_labels: node_labels.to_opt_strs(),
                edges,
                node_styles: match node_styles {
                    Some(nodes) => nodes,
                    None => vec![Style::None; count],
                },
            }
        }
    }

    impl LabelledGraphWithEscStrs {
        fn new(name: &'static str,
               node_labels: Trivial,
               edges: Vec<Edge>)
               -> LabelledGraphWithEscStrs {
            LabelledGraphWithEscStrs { graph: LabelledGraph::new(name, node_labels, edges, None) }
        }
    }

    fn id_name<'a>(n: &Node) -> Id<'a> {
        Id::new(format!("N{}", *n)).unwrap()
    }

    impl<'a> Labeller<'a> for LabelledGraph {
        type Node = Node;
        type Edge = &'a Edge;
        fn graph_id(&'a self) -> Id<'a> {
            Id::new(self.name).unwrap()
        }
        fn node_id(&'a self, n: &Node) -> Id<'a> {
            id_name(n)
        }
        fn node_label(&'a self, n: &Node) -> LabelText<'a> {
            match self.node_labels[*n] {
                Some(l) => LabelStr(l.into()),
                None => LabelStr(id_name(n).name()),
            }
        }
        fn edge_label(&'a self, e: &&'a Edge) -> LabelText<'a> {
            LabelStr(e.label.into())
        }
        fn node_style(&'a self, n: &Node) -> Style {
            self.node_styles[*n]
        }
        fn edge_style(&'a self, e: &&'a Edge) -> Style {
            e.style
        }
    }

    impl<'a> Labeller<'a> for LabelledGraphWithEscStrs {
        type Node = Node;
        type Edge = &'a Edge;
        fn graph_id(&'a self) -> Id<'a> {
            self.graph.graph_id()
        }
        fn node_id(&'a self, n: &Node) -> Id<'a> {
            self.graph.node_id(n)
        }
        fn node_label(&'a self, n: &Node) -> LabelText<'a> {
            match self.graph.node_label(n) {
                LabelStr(s) | EscStr(s) | HtmlStr(s) => EscStr(s),
            }
        }
        fn edge_label(&'a self, e: &&'a Edge) -> LabelText<'a> {
            match self.graph.edge_label(e) {
                LabelStr(s) | EscStr(s) | HtmlStr(s) => EscStr(s),
            }
        }
    }

    impl<'a> GraphWalk<'a> for LabelledGraph {
        type Node = Node;
        type Edge = &'a Edge;
        fn nodes(&'a self) -> Nodes<'a, Node> {
            (0..self.node_labels.len()).collect()
        }
        fn edges(&'a self) -> Edges<'a, &'a Edge> {
            self.edges.iter().collect()
        }
        fn source(&'a self, edge: &&'a Edge) -> Node {
            edge.from
        }
        fn target(&'a self, edge: &&'a Edge) -> Node {
            edge.to
        }
    }

    impl<'a> GraphWalk<'a> for LabelledGraphWithEscStrs {
        type Node = Node;
        type Edge = &'a Edge;
        fn nodes(&'a self) -> Nodes<'a, Node> {
            self.graph.nodes()
        }
        fn edges(&'a self) -> Edges<'a, &'a Edge> {
            self.graph.edges()
        }
        fn source(&'a self, edge: &&'a Edge) -> Node {
            edge.from
        }
        fn target(&'a self, edge: &&'a Edge) -> Node {
            edge.to
        }
    }

    fn test_input(g: LabelledGraph) -> io::Result<String> {
        let mut writer = Vec::new();
        render(&g, &mut writer).unwrap();
        let mut s = String::new();
        Read::read_to_string(&mut &*writer, &mut s)?;
        Ok(s)
    }

    // All of the tests use raw-strings as the format for the expected outputs,
    // so that you can cut-and-paste the content into a .dot file yourself to
    // see what the graphviz visualizer would produce.

    #[test]
    fn empty_graph() {
        let labels: Trivial = UnlabelledNodes(0);
        let r = test_input(LabelledGraph::new("empty_graph", labels, vec![], None));
        assert_eq!(r.unwrap(),
r#"digraph empty_graph {
}
"#);
    }

    #[test]
    fn single_node() {
        let labels: Trivial = UnlabelledNodes(1);
        let r = test_input(LabelledGraph::new("single_node", labels, vec![], None));
        assert_eq!(r.unwrap(),
r#"digraph single_node {
    N0[label="N0"];
}
"#);
    }

    #[test]
    fn single_node_with_style() {
        let labels: Trivial = UnlabelledNodes(1);
        let styles = Some(vec![Style::Dashed]);
        let r = test_input(LabelledGraph::new("single_node", labels, vec![], styles));
        assert_eq!(r.unwrap(),
r#"digraph single_node {
    N0[label="N0"][style="dashed"];
}
"#);
    }

    #[test]
    fn single_edge() {
        let labels: Trivial = UnlabelledNodes(2);
        let result = test_input(LabelledGraph::new("single_edge",
                                                   labels,
                                                   vec![edge(0, 1, "E", Style::None)],
                                                   None));
        assert_eq!(result.unwrap(),
r#"digraph single_edge {
    N0[label="N0"];
    N1[label="N1"];
    N0 -> N1[label="E"];
}
"#);
    }

    #[test]
    fn single_edge_with_style() {
        let labels: Trivial = UnlabelledNodes(2);
        let result = test_input(LabelledGraph::new("single_edge",
                                                   labels,
                                                   vec![edge(0, 1, "E", Style::Bold)],
                                                   None));
        assert_eq!(result.unwrap(),
r#"digraph single_edge {
    N0[label="N0"];
    N1[label="N1"];
    N0 -> N1[label="E"][style="bold"];
}
"#);
    }

    #[test]
    fn test_some_labelled() {
        let labels: Trivial = SomeNodesLabelled(vec![Some("A"), None]);
        let styles = Some(vec![Style::None, Style::Dotted]);
        let result = test_input(LabelledGraph::new("test_some_labelled",
                                                   labels,
                                                   vec![edge(0, 1, "A-1", Style::None)],
                                                   styles));
        assert_eq!(result.unwrap(),
r#"digraph test_some_labelled {
    N0[label="A"];
    N1[label="N1"][style="dotted"];
    N0 -> N1[label="A-1"];
}
"#);
    }

    #[test]
    fn single_cyclic_node() {
        let labels: Trivial = UnlabelledNodes(1);
        let r = test_input(LabelledGraph::new("single_cyclic_node",
                                              labels,
                                              vec![edge(0, 0, "E", Style::None)],
                                              None));
        assert_eq!(r.unwrap(),
r#"digraph single_cyclic_node {
    N0[label="N0"];
    N0 -> N0[label="E"];
}
"#);
    }

    #[test]
    fn hasse_diagram() {
        let labels = AllNodesLabelled(vec!["{x,y}", "{x}", "{y}", "{}"]);
        let r = test_input(LabelledGraph::new("hasse_diagram",
                                              labels,
                                              vec![edge(0, 1, "", Style::None),
                                                   edge(0, 2, "", Style::None),
                                                   edge(1, 3, "", Style::None),
                                                   edge(2, 3, "", Style::None)],
                                              None));
        assert_eq!(r.unwrap(),
r#"digraph hasse_diagram {
    N0[label="{x,y}"];
    N1[label="{x}"];
    N2[label="{y}"];
    N3[label="{}"];
    N0 -> N1[label=""];
    N0 -> N2[label=""];
    N1 -> N3[label=""];
    N2 -> N3[label=""];
}
"#);
    }

    #[test]
    fn left_aligned_text() {
        let labels = AllNodesLabelled(vec![
            "if test {\
           \\l    branch1\
           \\l} else {\
           \\l    branch2\
           \\l}\
           \\lafterward\
           \\l",
            "branch1",
            "branch2",
            "afterward"]);

        let mut writer = Vec::new();

        let g = LabelledGraphWithEscStrs::new("syntax_tree",
                                              labels,
                                              vec![edge(0, 1, "then", Style::None),
                                                   edge(0, 2, "else", Style::None),
                                                   edge(1, 3, ";", Style::None),
                                                   edge(2, 3, ";", Style::None)]);

        render(&g, &mut writer).unwrap();
        let mut r = String::new();
        Read::read_to_string(&mut &*writer, &mut r).unwrap();

        assert_eq!(r,
r#"digraph syntax_tree {
    N0[label="if test {\l    branch1\l} else {\l    branch2\l}\lafterward\l"];
    N1[label="branch1"];
    N2[label="branch2"];
    N3[label="afterward"];
    N0 -> N1[label="then"];
    N0 -> N2[label="else"];
    N1 -> N3[label=";"];
    N2 -> N3[label=";"];
}
"#);
    }

    #[test]
    fn simple_id_construction() {
        let id1 = Id::new("hello");
        match id1 {
            Ok(_) => {}
            Err(..) => panic!("'hello' is not a valid value for id anymore"),
        }
    }

    #[test]
    fn badly_formatted_id() {
        let id2 = Id::new("Weird { struct : ure } !!!");
        match id2 {
            Ok(_) => panic!("graphviz id suddenly allows spaces, brackets and stuff"),
            Err(..) => {}
        }
    }
}