forked from aosabook/500lines
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathchapter.html
More file actions
1767 lines (1667 loc) · 78.5 KB
/
Copy pathchapter.html
File metadata and controls
1767 lines (1667 loc) · 78.5 KB
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
<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.12: http://docutils.sourceforge.net/" />
<title>Contingent: A Fully Dynamic Build System</title>
<style type="text/css">
/*
:Author: David Goodger ([email protected])
:Id: $Id: html4css1.css 7614 2013-02-21 15:55:51Z milde $
:Copyright: This stylesheet has been placed in the public domain.
Default cascading style sheet for the HTML output of Docutils.
See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/
/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
border: 0 }
table.borderless td, table.borderless th {
/* Override padding for "table.docutils td" with "! important".
The right padding separates the table cells. */
padding: 0 0.5em 0 0 ! important }
.first {
/* Override more specific margin styles with "! important". */
margin-top: 0 ! important }
.last, .with-subtitle {
margin-bottom: 0 ! important }
.hidden {
display: none }
a.toc-backref {
text-decoration: none ;
color: black }
blockquote.epigraph {
margin: 2em 5em ; }
dl.docutils dd {
margin-bottom: 0.5em }
object[type="image/svg+xml"], object[type="application/x-shockwave-flash"] {
overflow: hidden;
}
/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
font-weight: bold }
*/
div.abstract {
margin: 2em 5em }
div.abstract p.topic-title {
font-weight: bold ;
text-align: center }
div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
margin: 2em ;
border: medium outset ;
padding: 1em }
div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
font-weight: bold ;
font-family: sans-serif }
div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title, .code .error {
color: red ;
font-weight: bold ;
font-family: sans-serif }
/* Uncomment (and remove this text!) to get reduced vertical space in
compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
margin-bottom: 0.5em }
div.compound .compound-last, div.compound .compound-middle {
margin-top: 0.5em }
*/
div.dedication {
margin: 2em 5em ;
text-align: center ;
font-style: italic }
div.dedication p.topic-title {
font-weight: bold ;
font-style: normal }
div.figure {
margin-left: 2em ;
margin-right: 2em }
div.footer, div.header {
clear: both;
font-size: smaller }
div.line-block {
display: block ;
margin-top: 1em ;
margin-bottom: 1em }
div.line-block div.line-block {
margin-top: 0 ;
margin-bottom: 0 ;
margin-left: 1.5em }
div.sidebar {
margin: 0 0 0.5em 1em ;
border: medium outset ;
padding: 1em ;
background-color: #ffffee ;
width: 40% ;
float: right ;
clear: right }
div.sidebar p.rubric {
font-family: sans-serif ;
font-size: medium }
div.system-messages {
margin: 5em }
div.system-messages h1 {
color: red }
div.system-message {
border: medium outset ;
padding: 1em }
div.system-message p.system-message-title {
color: red ;
font-weight: bold }
div.topic {
margin: 2em }
h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
margin-top: 0.4em }
h1.title {
text-align: center }
h2.subtitle {
text-align: center }
hr.docutils {
width: 75% }
img.align-left, .figure.align-left, object.align-left {
clear: left ;
float: left ;
margin-right: 1em }
img.align-right, .figure.align-right, object.align-right {
clear: right ;
float: right ;
margin-left: 1em }
img.align-center, .figure.align-center, object.align-center {
display: block;
margin-left: auto;
margin-right: auto;
}
.align-left {
text-align: left }
.align-center {
clear: both ;
text-align: center }
.align-right {
text-align: right }
/* reset inner alignment in figures */
div.align-right {
text-align: inherit }
/* div.align-center * { */
/* text-align: left } */
ol.simple, ul.simple {
margin-bottom: 1em }
ol.arabic {
list-style: decimal }
ol.loweralpha {
list-style: lower-alpha }
ol.upperalpha {
list-style: upper-alpha }
ol.lowerroman {
list-style: lower-roman }
ol.upperroman {
list-style: upper-roman }
p.attribution {
text-align: right ;
margin-left: 50% }
p.caption {
font-style: italic }
p.credits {
font-style: italic ;
font-size: smaller }
p.label {
white-space: nowrap }
p.rubric {
font-weight: bold ;
font-size: larger ;
color: maroon ;
text-align: center }
p.sidebar-title {
font-family: sans-serif ;
font-weight: bold ;
font-size: larger }
p.sidebar-subtitle {
font-family: sans-serif ;
font-weight: bold }
p.topic-title {
font-weight: bold }
pre.address {
margin-bottom: 0 ;
margin-top: 0 ;
font: inherit }
pre.literal-block, pre.doctest-block, pre.math, pre.code {
margin-left: 2em ;
margin-right: 2em }
pre.code .ln { color: grey; } /* line numbers */
pre.code, code { background-color: #eeeeee }
pre.code .comment, code .comment { color: #5C6576 }
pre.code .keyword, code .keyword { color: #3B0D06; font-weight: bold }
pre.code .literal.string, code .literal.string { color: #0C5404 }
pre.code .name.builtin, code .name.builtin { color: #352B84 }
pre.code .deleted, code .deleted { background-color: #DEB0A1}
pre.code .inserted, code .inserted { background-color: #A3D289}
span.classifier {
font-family: sans-serif ;
font-style: oblique }
span.classifier-delimiter {
font-family: sans-serif ;
font-weight: bold }
span.interpreted {
font-family: sans-serif }
span.option {
white-space: nowrap }
span.pre {
white-space: pre }
span.problematic {
color: red }
span.section-subtitle {
/* font-size relative to parent (h1..h6 element) */
font-size: 80% }
table.citation {
border-left: solid 1px gray;
margin-left: 1px }
table.docinfo {
margin: 2em 4em }
table.docutils {
margin-top: 0.5em ;
margin-bottom: 0.5em }
table.footnote {
border-left: solid 1px black;
margin-left: 1px }
table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
padding-left: 0.5em ;
padding-right: 0.5em ;
vertical-align: top }
table.docutils th.field-name, table.docinfo th.docinfo-name {
font-weight: bold ;
text-align: left ;
white-space: nowrap ;
padding-left: 0 }
/* "booktabs" style (no vertical lines) */
table.docutils.booktabs {
border: 0px;
border-top: 2px solid;
border-bottom: 2px solid;
border-collapse: collapse;
}
table.docutils.booktabs * {
border: 0px;
}
table.docutils.booktabs th {
border-bottom: thin solid;
text-align: left;
}
h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
font-size: 100% }
ul.auto-toc {
list-style-type: none }
</style>
</head>
<body>
<div class="document" id="contingent-a-fully-dynamic-build-system">
<h1 class="title">Contingent: A Fully Dynamic Build System</h1>
<style>
body {font-size: 1.3em; margin: 1em;}
div.document {margin: 0em auto; max-width: 40em;}
pre {background-color: #eee; padding: 0.6em;}
</style><p>Build systems have long been a standard tool
within computer programming.</p>
<p>The standard <tt class="docutils literal">make</tt> build system,
for which its author won the ACM Software System Award,
was first developed in 1976.
It not only lets you declare
that an output file depends upon one (or more) inputs,
but lets you do this recursively.
A program, for example, might depend upon an object file
which itself depends upon the corresponding source code:</p>
<pre class="literal-block">
prog: main.o
cc -o prog main.o
main.o: main.c
cc -C -o main.o main.c
</pre>
<p>Should <tt class="docutils literal">make</tt> discover, upon its next invocation,
that the <tt class="docutils literal">main.c</tt> source code file
now has a more recent modify time than <tt class="docutils literal">main.o</tt>,
then it will not only rebuild the <tt class="docutils literal">main.o</tt> object file
but will also rebuild <tt class="docutils literal">prog</tt> itself.</p>
<p>Build systems are a common semester project
posed for undergraduate computer science students —
not only because build systems are used in nearly all software projects,
but because their construction involves fundamental data structures
and algorithms involving directed graphs
(which this chapter will later discuss in more detail).
With decades of use and practice behind build systems,
one might expect them to have become completely general-purpose
and ready for even the most extravagant demands.</p>
<p>But, in fact, one kind of common interaction between build artifacts —
the problem of dynamic cross-referencing —
is handled so poorly by most build systems
that in this chapter we are inspired
to not only rehearse the standard solution
and data structures used classically to solve the <tt class="docutils literal">make</tt> problem,
but to extend that solution dramatically to a far more demanding domain.</p>
<p>The problem, again, is cross-referencing.
Where do cross-references tend to emerge?
In text documents, documentation, and printed books!</p>
<div class="section" id="the-problem-building-document-systems">
<h1>The Problem: Building Document Systems</h1>
<p>Systems to rebuild formatted documents from source texts
always seem to do too much work, or too little.</p>
<p>They do too much work
when they respond to a minor edit
by making you wait for unrelated chapters
to be re-parsed and re-formatted.
But they can also rebuild too little,
leaving you with an inconsistent final product.</p>
<p>Consider Sphinx 1.2.3, the current version
of the document builder
that is used for both the official Python language documentation
and many other projects in the Python community.
A Sphinx project’s <tt class="docutils literal">index.rst</tt>
will usually include a table of contents:</p>
<pre class="literal-block">
Table of Contents
=================
.. toctree::
install.rst
tutorial.rst
api.rst
</pre>
<p>This list of chapter filenames
tells Sphinx to include a link to each of the three named chapters
when it builds the <tt class="docutils literal">index.html</tt> output file.
It will also include links to any sections within each chapter.
Stripped of its markup,
the text that results from the above title
and <tt class="docutils literal">toctree</tt> command might be:</p>
<pre class="literal-block">
Table of Contents
• Installation
• Newcomers Tutorial
• Hello, World
• Adding Logging
• API Reference
• Handy Functions
• Obscure Classes
</pre>
<p>This table of contents, as you can see, is a mash-up
of information from four different files.
While its basic order and structure come from <tt class="docutils literal">index.rst</tt>,
the actual title of each chapter and section
is pulled from the three chapter source files themselves.</p>
<p>If you later reconsider the tutorial’s chapter title —
after all, the word “newcomer” sounds so antique,
as if your users are settlers who have just arrived in pioneer Wyoming —
then you would edit the first line of <tt class="docutils literal">tutorial.rst</tt>
and write something better:</p>
<pre class="literal-block">
-Newcomers Tutorial
+Beginners Tutorial
==================
Welcome to the tutorial!
This text will take you through the basics of...
</pre>
<p>When you are ready to rebuild,
Sphinx will do exactly the right thing!
It will rebuild both the tutorial chapter itself,
and also rebuild the index.
(Piping the output into <tt class="docutils literal">cat</tt> makes Sphinx
announce each rebuilt file on a separate line,
instead of using bare carriage returns
to repeatedly overwrite a single line with these progress updates.)</p>
<pre class="literal-block">
$ make html | cat
⋮
writing output... [ 50%] index
writing output... [100%] tutorial
</pre>
<p>Because Sphinx chose to rebuild both documents,
not only will <tt class="docutils literal">tutorial.html</tt> now feature its new title up at the top,
but the output <tt class="docutils literal">index.html</tt> will display the updated chapter title
in the table of contents.
Sphinx has rebuilt everything so that the output is consistent.</p>
<p>What if your edit to <tt class="docutils literal">tutorial.rst</tt> is more minor?</p>
<pre class="literal-block">
Beginners Tutorial
==================
-Welcome to the tutorial!
+Welcome to our project tutorial!
This text will take you through the basics of...
</pre>
<p>In this case there is no need to rebuild <tt class="docutils literal">index.html</tt>
because this minor edit to the interior of a paragraph
does not change any of the information in the table of contents.
But it turns out that Sphinx is not quite as clever
as it might have at first appeared!
It will go ahead and perform the redundant work of rebuilding
<tt class="docutils literal">index.html</tt> even though the resulting contents
will be exactly the same.</p>
<pre class="literal-block">
writing output... [ 50%] index
writing output... [100%] tutorial
</pre>
<p>You can run <tt class="docutils literal">diff</tt>
on the “before” and “after” versions of <tt class="docutils literal">index.html</tt>
to confirm that your small edit
has had zero effect on the project front page —
yet Sphinx made you wait while it was rebuilt anyway.</p>
<p>You might not even notice the extra rebuild effort
for small documents that are easy to compile.
But the delay to your workflow can become significant
when you are making frequent tweaks and edits
to documents that are long, complex, or that involve the generation
of multimedia like plots or animations.
While Sphinx is at least making an effort
not to rebuild every chapter when you make a single change —
it has not, for example, rebuilt <tt class="docutils literal">install.html</tt> or <tt class="docutils literal">api.html</tt>
in response to your <tt class="docutils literal">tutorial.rst</tt> edit —
it is doing more than is necessary.</p>
<p>But it turns out that Sphinx does something even worse:
it sometimes does too little,
leaving you with inconsistent output that could be noticed by users.</p>
<p>To see one of Sphinx’s simplest failure modes,
first add a cross reference to the top of your API documentation:</p>
<pre class="literal-block">
API Reference
=============
+Before reading this, try reading our :doc:`tutorial`!
+
The sections below list every function
and every single class and method offered...
</pre>
<p>With its usual caution as regards the table of contents,
Sphinx will dutifully rebuild both this API reference document
as well as the <tt class="docutils literal">index.html</tt> home page of your project:</p>
<pre class="literal-block">
writing output... [ 50%] api
writing output... [100%] index
</pre>
<p>In the <tt class="docutils literal">api.html</tt> output file you can confirm
that Sphinx has included the attractive human-readable title
of the tutorial chapter into the cross reference’s anchor tag:</p>
<pre class="literal-block">
<p>Before reading this, try reading our
<a class="reference internal" href="tutorial.html">
<em>Beginners Tutorial</em>
</a>!</p>
</pre>
<p>What if you now make another edit
to the title at the top of the <tt class="docutils literal">tutorial.rst</tt> file?
You will have invalidated <em>three</em> output files:</p>
<ol class="arabic simple">
<li>The title at the top of <tt class="docutils literal">tutorial.html</tt> is now out of date,
so the file needs to be rebuilt.</li>
<li>The table of contents in <tt class="docutils literal">index.html</tt> still has the old title,
so that document needs to be rebuilt.</li>
<li>The embedded cross reference in the first paragraph of <tt class="docutils literal">api.html</tt>
still has the old chapter title,
and also needs to be rebuilt.</li>
</ol>
<p>What does Sphinx do?</p>
<pre class="literal-block">
writing output... [ 50%] index
writing output... [100%] tutorial
</pre>
<p>Whoops.</p>
<p>Only two files were rebuilt, not three.
Sphinx has failed to correctly rebuild your documentation.</p>
<p>If you now push your HTML to the web,
users will see the old title in the cross reference
at the top of <tt class="docutils literal">api.html</tt>
but then a different title — the new one —
once the link has carried them to <tt class="docutils literal">tutorial.html</tt> itself.
This can happen for many kinds of cross reference that Sphinx supports:
chapter titles, section titles, paragraphs,
classes, methods, and functions.</p>
</div>
<div class="section" id="build-systems-and-consistency">
<h1>Build Systems and Consistency</h1>
<p>The problem outlined above is not specific to Sphinx.
Not only does it haunt other document systems, like LaTeX,
but it can even plague projects
that are simply trying to direct compilation steps
with the venerable <tt class="docutils literal">make</tt> utility,
if their assets happen to cross-reference in interesting ways.</p>
<p>As the problem is ancient and universal,
its solution is of equally long lineage:</p>
<pre class="literal-block">
$ rm -r _build/
$ make html
</pre>
<p>If you remove all of the output,
you are guaranteed a complete rebuild!
Some projects even alias <tt class="docutils literal">rm</tt> <tt class="docutils literal"><span class="pre">-r</span></tt> a target named <tt class="docutils literal">clean</tt>
so that only a quick <tt class="docutils literal">make</tt> <tt class="docutils literal">clean</tt> is necessary to wipe the slate.</p>
<p>By eliminating every copy of every intermediate or output asset,
a hefty <tt class="docutils literal">rm</tt> <tt class="docutils literal"><span class="pre">-r</span></tt> is able to force the build to start over again
with nothing cached — with no memory of its earlier state
that could possibly lead to a stale product!</p>
<p>But could we develop a better approach?</p>
<p>What if your build system were a persistent process
that noticed every chapter title, every section title,
and every cross referenced phrase
as it passed from the source code of one document
into the text of another?
Its decisions about whether to rebuild other documents
after a change to a single source file could be precise,
instead of mere guesses,
and correct,
instead of leaving the output in an inconsistent state.</p>
<p>The result would be a system like the old static <tt class="docutils literal">make</tt> tool,
but which learned the dependencies between files as they were built —
that added and removed dependencies dynamically
as cross references were added, updated, and then later deleted.</p>
<p>In the sections that follow we will construct such a tool in Python,
named Contingent,
that guarantees correctness in the presence of dynamic dependencies
while performing the fewest possible rebuild steps.
While Contingent can be applied to any problem domain,
we will run it against a small version of the problem outlined above.</p>
</div>
<div class="section" id="linking-tasks-to-make-a-graph">
<h1>Linking Tasks To Make a Graph</h1>
<p>Any build system needs a way to link inputs and outputs.
The three markup texts in our discussion above,
for example,
each produce a corresponding HTML output file.
The most natural way to express these relationships
is as a collection of boxes and arrows —
or, in mathematician terminology, <em>nodes</em> and <em>edges</em>
to form a <em>graph</em>:</p>
<div class="figure">
<img alt="figure1.png" src="figure1.png" />
<p class="caption"><strong>Figure 1.</strong> Three files generated by parsing three input texts.</p>
</div>
<p>Each language in which a programmer
might tackle writing a build system
will offer various data structures
with which such a graph of nodes and edges might be represented.</p>
<p>How could we represent such a graph in Python?</p>
<p>The Python language gives priority to four generic data structures
by giving them direct support in the language syntax.
You can create new instances of these big-four data structures
by simply typing their literal representation into your source code,
and their four type objects are available as built-in symbols
that can be used without being imported.</p>
<ul>
<li><p class="first">The <strong>tuple</strong> is a read-only sequence
used to hold heterogeneous data —
each slot in a tuple typically means something different.
Here, a tuple holds together a hostname and port number,
and would lose its meaning if the elements were re-ordered:</p>
<pre class="literal-block">
('dropbox.com', 443)
</pre>
</li>
<li><p class="first">The <strong>list</strong> is a mutable sequence
used to hold homogenous data —
each item usually has the same structure and meaning as its peers.
Lists can be used either to preserve data’s original input order,
or can be rearranged or sorted
to establish a new and more useful order.</p>
<pre class="literal-block">
['C', 'Awk', 'TCL', 'Python', 'JavaScript']
</pre>
</li>
<li><p class="first">The <strong>set</strong> does not preserve order.
Sets remember only whether a given value has been added,
not how many times,
and are therefore the go-to data structure
for removing duplicates from a data stream.
For example, the following two sets, once the language has built them,
will each have three elements:</p>
<pre class="literal-block">
{3, 4, 5}
{3, 4, 5, 4, 4, 3, 5, 4, 5, 3, 4, 5}
</pre>
</li>
<li><p class="first">The <strong>dict</strong> is an associative data structure for storing values
accessible by a key.
Dicts let the programmer chose the key
by which each value is indexed,
instead of using automatic integer indexing like the tuple and list.
The lookup is backed by a hash table,
which means that dict key lookup runs at the same speed
whether the dict has a dozen or a million keys!</p>
<pre class="literal-block">
{'ssh': 22, 'telnet': 23, 'domain': 53, 'http': 80}
</pre>
</li>
</ul>
<p>A key to Python’s flexibility
is that these four data structures are composable.
The programmer can arbitrarily nest them inside each other
to produce more complex data stores
whose rules and syntax remain the simple ones
of the underlying tuples, lists, sets, and dicts.</p>
<p>Given that each of our graph edges needs
to know at least its origin node and its destination node,
the simplest possible representation would be a tuple.
The top edge in Figure 1 might look like:</p>
<pre class="literal-block">
('tutorial.rst', 'tutorial.html')
</pre>
<p>How can we store several edges?
While our initial impulse might be
to simply throw all of our edge tuples into a list,
that would have disadvantages.
A list is careful to maintain order,
but it is not meaningful to talk about an absolute order
for the edges in a graph.
And a list would be perfectly happy to hold several copies
of exactly the same edge,
even though we only want it to be possible
to draw a single arrow between <tt class="docutils literal">tutorial.rst</tt> and <tt class="docutils literal">tutorial.html</tt>.
The correct choice is thus the set,
which would have us represent Figure 1 as:</p>
<pre class="literal-block">
{('tutorial.rst', 'tutorial.html'),
('index.rst', 'index.html'),
('api.rst', 'api.html')}
</pre>
<p>This would allow quick iteration across all of our edges,
fast insert and delete operations for a single edge,
and a quick way to check whether a particular edge was present.</p>
<!-- TODO: Perhaps demonstrate these operations here? -->
<p>Unfortunately, those are not the only operations we need.</p>
<p>A build system like Contingent
needs to understand the relationship between a given node
and all the nodes connected to it.
For example, when <tt class="docutils literal">api.rst</tt> changes,
Contingent needs to know which assets
are affected by that change, if any,
in order to minimize the work performed
while also ensuring a complete build.
To answer this question —
“what nodes are downstream from <tt class="docutils literal">api.rst</tt>?” —
we need to examine the <em>outgoing</em> edges from <tt class="docutils literal">api.rst</tt>.
But building the dependency graph requires that
Contingent be concerned with a node's <em>inputs</em> as well.
What inputs were used, for example,
when the build system assembled the output document <tt class="docutils literal">tutorial.html</tt>?
It is by watching the input to each node that
Contingent can know that <tt class="docutils literal">api.html</tt> depends on <tt class="docutils literal">api.rst</tt> but
that <tt class="docutils literal">tutorial.html</tt> does not.
As sources change and rebuilds occur,
Contingent rebuilds the incoming edges of each changed node
to remove potentially stale edges
and re-learn which resources a task uses this time around.</p>
<p>Our set-of-tuples does not make answering
either of these questions easy.
If we needed to know the relationship between <tt class="docutils literal">api.html</tt>
and the rest of the graph,
we would need to traverse the entire set
looking for edges that start or end at the <tt class="docutils literal">api.html</tt> node.</p>
<p>An associative data structure like Python's dict
would make these chores easier
by allowing direct lookup of all the edges from a particular node:</p>
<pre class="literal-block">
{'tutorial.rst': {('tutorial.rst', 'tutorial.html')},
'tutorial.html': {('tutorial.rst', 'tutorial.html')},
'index.rst': {('index.rst', 'index.html')},
'index.html': {('index.rst', 'index.html')},
'api.rst': {('api.rst', 'api.html')},
'api.html': {('api.rst', 'api.html')}}
</pre>
<p>Looking up the edges of a particular node would now be blazingly fast,
at the cost of having to store every edge twice:
once in a set of incoming edges,
and once in a set of outgoing edges.
But the edges in each set would have to be examined manually
to see which are incoming and which are outgoing.
It is also slightly redundant to keep naming the node
over and over again in its set of edges.</p>
<p>The solution to both of these objections
is to place incoming and outgoing edges
in their own separate data structures,
which will also absolve us
of having to mention the node over and over again
for every one of the edges in which it is involved.</p>
<pre class="literal-block">
incoming = {
'tutorial.html': {'tutorial.rst'},
'index.html': {'index.rst'},
'api.html': {'api.rst'},
}
outgoing = {
'tutorial.rst': {'tutorial.html'},
'index.rst': {'index.html'},
'api.rst': {'api.html'},
}
</pre>
<p>Notice that <tt class="docutils literal">outgoing</tt> represents, directly in Python syntax,
exactly what we drew in Figure 1 earlier:
the source documents on the left
will be transformed by the build system into the
output documents on the right.
For this simple example each source points to only one output —
all the output sets have only one element —
but we will see examples shortly where a single input node
has multiple downstream consequences.</p>
<p>Every edge in this dictionary-of-sets data structure
does get represented twice,
once as an outgoing edge from one node
(<tt class="docutils literal">tutorial.rst</tt> → <tt class="docutils literal">tutorial.html</tt>)
and again as an incoming edge to the other
(<tt class="docutils literal">tutorial.html</tt> ← <tt class="docutils literal">tutorial.rst</tt>).
These two representations capture precisely the same relationship,
just from the opposite perspectives of the two nodes
at either end of the edge.
But in return for this redundancy,
the data structure supports the fast lookup that Contingent needs.</p>
</div>
<div class="section" id="the-proper-use-of-classes">
<h1>The Proper Use of Classes</h1>
<p>You may have been surprised
by the absence of classes in the above discussion
of Python data structures.
After all, classes are a frequent mechanism for structuring applications
and a hardly less frequent subject of heated debate
among their adherents and detractors.
Classes were once thought important enough that
entire educational curricula were designed around them,
and the majority of popular programming languanges
include dedicated syntax for defining and using them.</p>
<p>But it turns out that classes are often orthogonal
to the question of data structure design.
Rather than offering us an entirely alternative data modeling paradigm,
classes simply repeat data structures that we have already seen:</p>
<ul class="simple">
<li>A class instance is <em>implemented</em> as a dict.</li>
<li>A class instance is <em>used</em> like a mutable tuple.</li>
</ul>
<p>The class offers key lookup into its attribute dictionary
through a prettier syntax,
where you get to say <tt class="docutils literal">graph.incoming</tt>
instead of <tt class="docutils literal"><span class="pre">graph["incoming"]</span></tt>.
But, in practice, class instances are almost never used
as generic key-value stores.
Instead, they are used to organize related but heterogeneous data
by attribute name,
with implementation details encapsulated behind
a consistent and memorable interface.</p>
<p>So instead of putting a hostname and a port number together in a tuple
and having to remember later which came first and which came second,
you create an <tt class="docutils literal">Address</tt> class
whose instances each have a <tt class="docutils literal">host</tt> and a <tt class="docutils literal">port</tt> attribute.
You can then pass <tt class="docutils literal">Address</tt> objects around
where otherwise you would have had anonymous tuples.
Code becomes easier to read and easier to write.
But using a class instance does not really change
any of the questions we faced above when doing data design:
it just provides a prettier and less anonymous container.</p>
<p>The true value of classes, then,
is not that they change the science of data design.
The value of classes
is that they let you <em>hide</em> your data design from the rest of a program!</p>
<p>Successful application design
hinges upon our ability to exploit
the powerful built-in data structures Python offers us
while minimizing the volume of details we are required to
keep in our heads at any one time.
Classes provide the mechanism for resolving this apparent quandary:
used effectively, a class provides a <em>facade</em>
around some small subset of the system's overall design.
When working within one subset — a <tt class="docutils literal">Graph</tt>, for example —
we can forget the implementation details of other subsets
as long as we can remember their interfaces.
In this way, programmers often find themselves navigating
among several levels of abstraction
in the course of writing a system,
now working with the specific data model and implementation details
for a particular subsystem,
now connecting higher-level concepts through their interfaces.</p>
<p>For example, from the outside,
code can simply ask for a new <tt class="docutils literal">Graph</tt> instance:</p>
<pre class="doctest-block">
>>> from contingent import graphlib
>>> g = graphlib.Graph()
</pre>
<p>without needing to understand the details of how <tt class="docutils literal">Graph</tt> works.
Code that is simply using the graph
sees only interface verbs — the method calls —
when manipulating a graph,
as when an edge is added or some other operation performed:</p>
<pre class="doctest-block">
>>> g.add_edge('index.rst', 'index.html')
>>> g.add_edge('tutorial.rst', 'tutorial.html')
>>> g.add_edge('api.rst', 'api.html')
</pre>
<p>Careful readers will have noticed that we added edges to our graph
without explicitly creating “node” and “edge” objects,
and that the nodes themselves in these early examples
are simply strings.
Coming from other languages and traditions,
one might have expected to see
user-defined classes and interfaces for everything in the system:</p>
<pre class="literal-block">
Graph g = new ConcreteGraph();
Node indexRstNode = new StringNode("index.rst");
Node indexHtmlNode = new StringNode("index.html");
Edge indexEdge = new DirectedEdge(indexRstNode, indexHtmlNode);
g.addEdge(indexEdge);
</pre>
<p>The Python language and community explicitly and intentionally emphasize
using simple, generic data structures to solve problems,
instead of creating custom classes for every minute detail
of the problem we want to tackle.
This is one facet of the notion of “Pythonic” solutions that you may
have read about.
Pythonic solutions try to
minimize syntactic overhead
and leverage Python's powerful built-in tools
and extensive standard library.</p>
<p>With these considerations in mind,
let’s return to the <tt class="docutils literal">Graph</tt> class,
examining its design and implmentation to see
the interplay between data structures and class interfaces.
When a new <tt class="docutils literal">Graph</tt> instance is constructed,
a pair of dictionaries has already been built
to store edges using the logic we outlined in the previous section:</p>
<pre class="code python literal-block">
<span class="keyword">class</span> <span class="name class">Graph</span><span class="punctuation">:</span>
<span class="literal string">"""A directed graph of the relationships among build tasks.</span>
</pre>
<pre class="code python literal-block">
<span class="keyword">def</span> <span class="name function">__init__</span><span class="punctuation">(</span><span class="name builtin pseudo">self</span><span class="punctuation">):</span>
<span class="name builtin pseudo">self</span><span class="operator">.</span><span class="name">_inputs_of</span> <span class="operator">=</span> <span class="name">defaultdict</span><span class="punctuation">(</span><span class="name builtin">set</span><span class="punctuation">)</span>
<span class="name builtin pseudo">self</span><span class="operator">.</span><span class="name">_consequences_of</span> <span class="operator">=</span> <span class="name">defaultdict</span><span class="punctuation">(</span><span class="name builtin">set</span><span class="punctuation">)</span>
</pre>
<p>The leading underscore
in front of the attribute names <tt class="docutils literal">_inputs_of</tt> and <tt class="docutils literal">_consequences_of</tt>
is a common convention in the Python community
to signal that an attribute is private.
This convention is one way the community suggests
that programmers pass messages and warnings
through space and time to each other.
Recognizing the need to signal differences among
public versus internal object attributes,
the community adopted the single leading underscore
as a concise and fairly consistent indicator
to other programmers,
including our future selves,
that the attribute is best treated
as part of the invisible internal machinery of the class.</p>
<p>Why are we using a “defaultdict” instead of a standard dict?
A common problem when composing dicts
with other data structures is handling missing keys.
With a normal dict,
retrieving a key that does not exist raises a <tt class="docutils literal">KeyError</tt>:</p>
<pre class="doctest-block">
>>> consequences_of = {}
>>> consequences_of['index.rst'].add('index.html')
Traceback (most recent call last):
...
KeyError: 'index.rst'
</pre>
<p>Using a normal dict requires special checks throughout the code
to handle this specific case, for example when adding a new edge:</p>
<pre class="code python literal-block">
<span class="comment"># Special case to handle “we have not seen this task yet”:</span>
<span class="keyword">if</span> <span class="name">input_task</span> <span class="operator word">not</span> <span class="operator word">in</span> <span class="name builtin pseudo">self</span><span class="operator">.</span><span class="name">_consequences_of</span><span class="punctuation">:</span>
<span class="name builtin pseudo">self</span><span class="operator">.</span><span class="name">_consequences_of</span><span class="punctuation">[</span><span class="name">input_task</span><span class="punctuation">]</span> <span class="operator">=</span> <span class="name builtin">set</span><span class="punctuation">()</span>
<span class="name builtin pseudo">self</span><span class="operator">.</span><span class="name">_consequences_of</span><span class="punctuation">[</span><span class="name">input_task</span><span class="punctuation">]</span><span class="operator">.</span><span class="name">add</span><span class="punctuation">(</span><span class="name">consequence_task</span><span class="punctuation">)</span>
</pre>
<p>This need is so common that Python includes a special utility,
the defaultdict, which lets you provide a function
that returns a value for absent keys.
When we ask about an edge that the <tt class="docutils literal">Graph</tt> hasn't yet seen,
we will get back an empty <tt class="docutils literal">set</tt> instead of an exception:</p>
<pre class="doctest-block">
>>> from collections import defaultdict
>>> consequences_of = defaultdict(set)
>>> consequences_of['api.rst']
set()
</pre>
<p>Structuring our implementation this way means that
each key’s first use can look identical
to second-and-subsequent-times that a particular key is used:</p>
<pre class="doctest-block">
>>> consequences_of['index.rst'].add('index.html')
>>> 'index.html' in consequences_of['index.rst']
True
</pre>
<p>Given these techniques, let’s examine the implementation
of <tt class="docutils literal">add_edge</tt>, which we earlier used
to build the graph for Figure 1:</p>
<pre class="code python literal-block">
<span class="keyword">def</span> <span class="name function">add_edge</span><span class="punctuation">(</span><span class="name builtin pseudo">self</span><span class="punctuation">,</span> <span class="name">input_task</span><span class="punctuation">,</span> <span class="name">consequence_task</span><span class="punctuation">):</span>
<span class="literal string doc">"""Add an edge: `consequence_task` uses the output of `input_task`."""</span>
<span class="name builtin pseudo">self</span><span class="operator">.</span><span class="name">_consequences_of</span><span class="punctuation">[</span><span class="name">input_task</span><span class="punctuation">]</span><span class="operator">.</span><span class="name">add</span><span class="punctuation">(</span><span class="name">consequence_task</span><span class="punctuation">)</span>
<span class="name builtin pseudo">self</span><span class="operator">.</span><span class="name">_inputs_of</span><span class="punctuation">[</span><span class="name">consequence_task</span><span class="punctuation">]</span><span class="operator">.</span><span class="name">add</span><span class="punctuation">(</span><span class="name">input_task</span><span class="punctuation">)</span>
</pre>
<p>This method hides the fact that two, not one,
storage steps are required for each new edge
so that we know about it in both directions.
And notice how <tt class="docutils literal">add_edge()</tt> does not know or care
whether either node has been seen before.
Because the inputs and consequences data structures
are each a <tt class="docutils literal">defaultdict(set)</tt>,
the <tt class="docutils literal">add_edge()</tt> method remains blissfully ignorant
as to the novelty of a node —
the <tt class="docutils literal">defaultdict</tt> takes care of the difference
by creating a new <tt class="docutils literal">set</tt> object on the fly.
As we saw above, <tt class="docutils literal">add_edge()</tt> would be
three times longer had we not used <tt class="docutils literal">defaultdict</tt>.
More importantly, it would be more difficult