Gitiles
Code Review Sign In
gerrit-public.fairphone.software / toolchain / llvm-project / f196dbb65c55ab4b7bcc04aaaffcaa06ec83e77c / . / llvm / docs / CodingStandards.html
blob: 0785448ff73f2f11362d5ebff095cfa1b841cc78 [file] [log] [blame]
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3<html>
4<head>
5 <link rel="stylesheet" href="llvm.css" type="text/css">
6 <title>A Few Coding Standards</title>
7</head>
8<body>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]9
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]10<div class="doc_title">
11 A Few Coding Standards
12</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]13
14<ol>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]15 <li><a href="#introduction">Introduction</a></li>
Chris Lattner85014f42001-07-23 20:40:41 +0000[diff] [blame]16 <li><a href="#mechanicalissues">Mechanical Source Issues</a>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]17 <ol>
18 <li><a href="#sourceformating">Source Code Formatting</a>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]19 <ol>
20 <li><a href="#scf_commenting">Commenting</a></li>
21 <li><a href="#scf_commentformat">Comment Formatting</a></li>
22 <li><a href="#scf_includes">#include Style</a></li>
23 <li><a href="#scf_codewidth">Source Code Width</a></li>
24 <li><a href="#scf_spacestabs">Use Spaces Instead of Tabs</a></li>
25 <li><a href="#scf_indentation">Indent Code Consistently</a></li>
26 </ol></li>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]27 <li><a href="#compilerissues">Compiler Issues</a>
28 <ol>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]29 <li><a href="#ci_warningerrors">Treat Compiler Warnings Like
30 Errors</a></li>
31 <li><a href="#ci_cpp_features">Which C++ features can I use?</a></li>
32 <li><a href="#ci_portable_code">Write Portable Code</a></li>
33 </ol></li>
34 </ol></li>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]35 <li><a href="#styleissues">Style Issues</a>
36 <ol>
37 <li><a href="#macro">The High Level Issues</a>
38 <ol>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]39 <li><a href="#hl_module">A Public Header File <b>is</b> a
40 Module</a></li>
41 <li><a href="#hl_dontinclude">#include as Little as Possible</a></li>
42 <li><a href="#hl_privateheaders">Keep "internal" Headers
43 Private</a></li>
44 </ol></li>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]45 <li><a href="#micro">The Low Level Issues</a>
46 <ol>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]47 <li><a href="#hl_assert">Assert Liberally</a></li>
48 <li><a href="#hl_preincrement">Prefer Preincrement</a></li>
49 <li><a href="#hl_avoidendl">Avoid endl</a></li>
50 <li><a href="#hl_exploitcpp">Exploit C++ to its Fullest</a></li>
51 </ol></li>
52 <li><a href="#iterators">Writing Iterators</a></li>
53 </ol></li>
54 <li><a href="#seealso">See Also</a></li>
55</ol>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]56
57
58<!-- *********************************************************************** -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]59<div class="doc_section">
60 <a name="introduction">Introduction</a>
61</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]62<!-- *********************************************************************** -->
63
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]64<div class="doc_text">
65
66<p>This document attempts to describe a few coding standards that are being used
67in the LLVM source tree. Although no coding standards should be regarded as
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]68absolute requirements to be followed in all instances, coding standards can be
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]69useful.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]70
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]71<p>This document intentionally does not prescribe fixed standards for religious
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]72issues such as brace placement and space usage. For issues like this, follow
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]73the golden rule:</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]74
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]75<blockquote>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]76
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]77<p><b><a name="goldenrule">If you are adding a significant body of source to a
78project, feel free to use whatever style you are most comfortable with. If you
79are extending, enhancing, or bug fixing already implemented code, use the style
80that is already being used so that the source is uniform and easy to
81follow.</a></b></p>
82
83</blockquote>
84
85<p>The ultimate goal of these guidelines is the increase readability and
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]86maintainability of our common source base. If you have suggestions for topics to
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]87be included, please mail them to <a
88href="mailto:sabre@nondot.org">Chris</a>.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]89
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]90</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]91
92<!-- *********************************************************************** -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]93<div class="doc_section">
94 <a name="mechanicalissues">Mechanical Source Issues</a>
95</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]96<!-- *********************************************************************** -->
97
98<!-- ======================================================================= -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]99<div class="doc_subsection">
100 <a name="sourceformating">Source Code Formatting</a>
101</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]102
103<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]104<div class="doc_subsubsection">
105 <a name="scf_commenting">Commenting</a>
106</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]107
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]108<div class="doc_text">
109
110<p>Comments are one critical part of readability and maintainability. Everyone
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]111knows they should comment, so should you. :) Although we all should probably
112comment our code more than we do, there are a few very critical places that
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]113documentation is very useful:</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]114
115<ol>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]116<li><h4>File Headers</h4>
117
118<p>Every source file should have a header on it that
119describes the basic purpose of the file. If a file does not have a header, it
120should not be checked into CVS. Most source trees will probably have a standard
121file header format. The standard format for the LLVM source tree looks like
122this:</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]123
124<pre>
Chris Lattnere6f4e072003-10-13 14:58:11 +0000[diff] [blame]125//===-- llvm/Instruction.h - Instruction class definition -------*- C++ -*-===//
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]126//
127// This file contains the declaration of the Instruction class, which is the
128// base class for all of the VM instructions.
129//
130//===----------------------------------------------------------------------===//
131</pre>
132
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]133<p>A few things to note about this particular format. The "<tt>-*- C++
134-*-</tt>" string on the first line is there to tell Emacs that the source file
135is a C++ file, not a C file (Emacs assumes .h files are C files by default [Note
136that tag this is not necessary in .cpp files]). The name of the file is also on
137the first line, along with a very short description of the purpose of the file.
138This is important when printing out code and flipping though lots of pages.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]139
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]140<p>The main body of the description does not have to be very long in most cases.
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]141Here it's only two lines. If an algorithm is being implemented or something
142tricky is going on, a reference to the paper where it is published should be
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]143included, as well as any notes or "gotchas" in the code to watch out for.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]144
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]145</li>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]146
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]147<li><h4>Class overviews</h4>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]148
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]149<p>Classes are one fundemental part of a good object oriented design. As such,
150a class definition should have a comment block that explains what the class is
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]151used for... if it's not obvious. If it's so completely obvious your grandma
152could figure it out, it's probably safe to leave it out. Naming classes
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]153something sane goes a long ways towards avoiding writing documentation. :)</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]154
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]155</li>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]156
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]157<li><h4>Method information</h4>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]158
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]159<p>Methods defined in a class (as well as any global functions) should also be
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]160documented properly. A quick note about what it does any a description of the
161borderline behaviour is all that is necessary here (unless something
162particularly tricky or insideous is going on). The hope is that people can
163figure out how to use your interfaces without reading the code itself... that is
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]164the goal metric.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]165
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]166<p>Good things to talk about here are what happens when something unexpected
167happens: does the method return null? Abort? Format your hard disk?</p>
168
169</li>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]170</ol>
171
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]172</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]173
174<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]175<div class="doc_subsubsection">
176 <a name="scf_commentformat">Comment Formatting</a>
177</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]178
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]179<div class="doc_text">
180
181<p>In general, prefer C++ style (<tt>//</tt>) comments. They take less space,
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]182require less typing, don't have nesting problems, etc. There are a few cases
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]183when it is useful to use C style (<tt>/* */</tt>) comments however:</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]184
185<ol>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]186 <li>When writing a C code: Obviously if you are writing C code, use C style
187 comments. :)</li>
188 <li>When writing a header file that may be #included by a C source file.</li>
189 <li>When writing a source file that is used by a tool that only accepts C
190 style comments.</li>
191</ol>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]192
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]193<p>To comment out a large block of code, use <tt>#if 0</tt> and <tt>#endif</tt>.
194These nest properly and are better behaved in general than C style comments.</p>
195
196</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]197
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]198<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]199<div class="doc_subsubsection">
200 <a name="scf_includes">#include Style</a>
201</div>
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]202
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]203<div class="doc_text">
204
205<p>Immediately after the <a href="#scf_commenting">header file comment</a> (and
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]206include guards if working on a header file), the <a
207href="hl_dontinclude">minimal</a> list of #includes required by the file should
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]208be listed. We prefer these #includes to be listed in this order:</p>
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]209
210<ol>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]211 <li><a href="#mmheader">Main Module header</a></li>
212 <li><a href="#hl_privateheaders">Local/Private Headers</a></li>
213 <li>llvm/*</li>
214 <li>llvm/Analysis/*</li>
215 <li>llvm/Assembly/*</li>
216 <li>llvm/Bytecode/*</li>
217 <li>llvm/CodeGen/*</li>
218 <li>...</li>
219 <li>Support/*</li>
220 <li>Config/*</li>
221 <li>System #includes</li>
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]222</ol>
223
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]224<p>... and each catagory should be sorted by name.</p>
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]225
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]226<p><a name="mmheader">The "Main Module Header"</a> file applies to .cpp file
227which implement an interface defined by a .h file. This #include should always
228be included <b>first</b> regardless of where it lives on the file system. By
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]229including a header file first in the .cpp files that implement the interfaces,
230we ensure that the header does not have any hidden dependencies which are not
231explicitly #included in the header, but should be. It is also a form of
232documentation in the .cpp file to indicate where the interfaces it implements
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]233are defined.</p>
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]234
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]235</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]236
237<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]238<div class="doc_subsubsection">
239 <a name="scf_codewidth">Source Code Width</a>
240</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]241
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]242<div class="doc_text">
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]243
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]244<p>Write your code to fit within 80 columns of text. This helps those of us who
245like to print out code and look at your code in an xterm without resizing
246it.</p>
247
248</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]249
250<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]251<div class="doc_subsubsection">
252 <a name="scf_spacestabs">Use Spaces Instead of Tabs</a>
253</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]254
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]255<div class="doc_text">
256
257<p>In all cases, prefer spaces to tabs in source files. People have different
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]258prefered indentation levels, and different styles of indentation that they
259like... this is fine. What isn't is that different editors/viewers expand tabs
260out to different tab stops. This can cause your code to look completely
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]261unreadable, and it is not worth dealing with.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]262
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]263<p>As always, follow the <a href="#goldenrule">Golden Rule</a> above: follow the
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]264style of existing code if your are modifying and extending it. If you like four
265spaces of indentation, <b>DO NOT</b> do that in the middle of a chunk of code
266with two spaces of indentation. Also, do not reindent a whole source file: it
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]267makes for incredible diffs that are absolutely worthless.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]268
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]269</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]270
271<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]272<div class="doc_subsubsection">
273 <a name="scf_indentation">Indent Code Consistently</a>
274</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]275
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]276<div class="doc_text">
277
278<p>Okay, your first year of programming you were told that indentation is
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]279important. If you didn't believe and internalize this then, now is the time.
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]280Just do it.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]281
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]282</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]283
284
285<!-- ======================================================================= -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]286<div class="doc_subsection">
287 <a name="compilerissues">Compiler Issues</a>
288</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]289
290
291<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]292<div class="doc_subsubsection">
293 <a name="ci_warningerrors">Treat Compiler Warnings Like Errors</a>
294</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]295
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]296<div class="doc_text">
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]297
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]298<p>If your code has compiler warnings in it, something is wrong: you aren't
299casting values correctly, your have "questionable" constructs in your code, or
300you are doing something legitimately wrong. Compiler warnings can cover up
301legitimate errors in output and make dealing with a translation unit
302difficult.</p>
303
304<p>It is not possible to prevent all warnings from all compilers, nor is it
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]305desirable. Instead, pick a standard compiler (like <tt>gcc</tt>) that provides
306a good thorough set of warnings, and stick to them. At least in the case of
307<tt>gcc</tt>, it is possible to work around any spurious errors by changing the
308syntax of the code slightly. For example, an warning that annoys me occurs when
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]309I write code like this:</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]310
311<pre>
312 if (V = getValue()) {
313 ..
314 }
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]315</pre>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]316
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]317<p><tt>gcc</tt> will warn me that I probably want to use the <tt>==</tt>
318operator, and that I probably mistyped it. In most cases, I haven't, and I
319really don't want the spurious errors. To fix this particular problem, I
320rewrite the code like this:</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]321
322<pre>
323 if ((V = getValue())) {
324 ..
325 }
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]326</pre>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]327
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]328<p>...which shuts <tt>gcc</tt> up. Any <tt>gcc</tt> warning that annoys you can
329be fixed by massaging the code appropriately.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]330
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]331<p>These are the <tt>gcc</tt> warnings that I prefer to enable: <tt>-Wall
332-Winline -W -Wwrite-strings -Wno-unused</tt></p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]333
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]334</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]335
336<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]337<div class="doc_subsubsection">
338 <a name="ci_cpp_features">Which C++ features can I use?</a>
339</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]340
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]341<div class="doc_text">
342
343<p>Compilers are finally catching up to the C++ standard. Most compilers
344implement most features, so you can use just about any features that you would
345like. In the LLVM source tree, I have chosen to not use these features:</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]346
347<ol>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]348<li><p>Exceptions: Exceptions are very useful for error reporting and handling
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]349exceptional conditions. I do not use them in LLVM because they do have an
350associated performance impact (by restricting restructuring of code), and parts
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]351of LLVM are designed for performance critical purposes.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]352
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]353<p>Just like most of the rules in this document, this isn't a hard and fast
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]354requirement. Exceptions are used in the Parser, because it simplifies error
355reporting <b>significantly</b>, and the LLVM parser is not at all in the
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]356critical path.</p>
357</li>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]358
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]359<li>RTTI: RTTI has a large cost in terms of executable size, and compilers are
360not yet very good at stomping out "dead" class information blocks. Because of
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]361this, typeinfo and dynamic cast are not used.</li>
362</ol>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]363
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]364<p>Other features, such as templates (without partial specialization) can be
365used freely. The general goal is to have clear, consise, performant code... if
366a technique assists with that then use it.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]367
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]368</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]369
370<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]371<div class="doc_subsubsection">
372 <a name="ci_portable_code">Write Portable Code</a>
373</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]374
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]375<div class="doc_text">
376
377<p>In almost all cases, it is possible and within reason to write completely
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]378portable code. If there are cases where it isn't possible to write portable
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]379code, isolate it behind a well defined (and well documented) interface.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]380
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]381<p>In practice, this means that you shouldn't assume much about the host
382compiler, including its support for "high tech" features like partial
383specialization of templates. In fact, Visual C++ 6 could be an important target
384for our work in the future, and we don't want to have to rewrite all of our code
385to support it.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]386
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]387</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]388
389<!-- *********************************************************************** -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]390<div class="doc_section">
391 <a name="styleissues">Style Issues</a>
392</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]393<!-- *********************************************************************** -->
394
395
396<!-- ======================================================================= -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]397<div class="doc_subsection">
398 <a name="macro">The High Level Issues</a>
399</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]400
401
402<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]403<div class="doc_subsubsection">
404 <a name="hl_module">A Public Header File <b>is</b> a Module</a>
405</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]406
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]407<div class="doc_text">
408
409<p>C++ doesn't do too well in the modularity department. There is no real
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]410encapsulation or data hiding (unless you use expensive protocol classes), but it
411is what we have to work with. When you write a public header file (in the LLVM
412source tree, they live in the top level "include" directory), you are defining a
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]413module of functionality.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]414
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]415<p>Ideally, modules should be completely independent of each other, and their
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]416header files should only include the absolute minimum number of headers
417possible. A module is not just a class, a function, or a namespace: <a
418href="http://www.cuj.com/articles/2000/0002/0002c/0002c.htm">it's a collection
419of these</a> that defines an interface. This interface may be several
420functions, classes or data structures, but the important issue is how they work
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]421together.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]422
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]423<p>In general, a module should be implemented with one or more <tt>.cpp</tt>
424files. Each of these <tt>.cpp</tt> files should include the header that defines
425their interface first. This ensure that all of the dependences of the module
426header have been properly added to the module header itself, and are not
427implicit. System headers should be included after user headers for a
428translation unit.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]429
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]430</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]431
432<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]433<div class="doc_subsubsection">
434 <a name="hl_dontinclude">#include as Little as Possible</a>
435</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]436
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]437<div class="doc_text">
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]438
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]439<p><tt>#include</tt> hurts compile time performance. Don't do it unless you
440have to, especially in header files.</p>
441
442<p>But wait, sometimes you need to have the definition of a class to use it, or
443to inherit from it. In these cases go ahead and #include that header file. Be
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]444aware however that there are many cases where you don't need to have the full
445definition of a class. If you are using a pointer or reference to a class, you
446don't need the header file. If you are simply returning a class instance from a
447prototyped function or method, you don't need it. In fact, for most cases, you
448simply don't need the definition of a class... and not <tt>#include</tt>'ing
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]449speeds up compilation.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]450
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]451<p>It is easy to try to go too overboard on this recommendation, however. You
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]452<b>must</b> include all of the header files that you are using, either directly
453or indirectly (through another header file). To make sure that you don't
454accidently forget to include a header file in your module header, make sure to
455include your module header <b>first</b> in the implementation file (as mentioned
456above). This way there won't be any hidden dependencies that you'll find out
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]457about later...</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]458
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]459</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]460
461<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]462<div class="doc_subsubsection">
463 <a name="hl_privateheaders">Keep "internal" Headers Private</a>
464</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]465
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]466<div class="doc_text">
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]467
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]468<p>Many modules have a complex implementation that causes them to use more than
469one implementation (<tt>.cpp</tt>) file. It is often tempting to put the
470internal communication interface (helper classes, extra functions, etc) in the
471public module header file. Don't do this. :)</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]472
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]473<p>If you really need to do something like this, put a private header file in
474the same directory as the source files, and include it locally. This ensures
475that your private interface remains private and undisturbed by outsiders.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]476
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]477<p>Note however, that it's okay to put extra implementation methods a public
478class itself... just make them private (or protected), and all is well.</p>
479
480</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]481
482<!-- ======================================================================= -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]483<div class="doc_text">
484 <a name="micro">The Low Level Issues</a>
485</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]486
487
488<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]489<div class="doc_subsubsection">
490 <a name="hl_assert">Assert Liberally</a>
491</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]492
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]493<div class="doc_text">
494
495<p>Use the "<tt>assert</tt>" function to its fullest. Check all of your
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]496preconditions and assumptions, you never know when a bug (not neccesarily even
497yours) might be caught early by an assertion, which reduces debugging time
498dramatically. The "<tt>&lt;cassert&gt;</tt>" header file is probably already
499included by the header files you are using, so it doesn't cost anything to use
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]500it.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]501
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]502<p>To further assist with debugging, make sure to put some kind of error message
503in the assertion statement (which is printed if the assertion is tripped). This
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]504helps the poor debugging make sense of why an assertion is being made and
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]505enforced, and hopefully what to do about it. Here is one complete example:</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]506
507<pre>
508 inline Value *getOperand(unsigned i) {
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]509 assert(i &lt; Operands.size() &amp;&amp; "getOperand() out of range!");
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]510 return Operands[i];
511 }
512</pre>
513
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]514<p>Here are some examples:</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]515
516<pre>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]517 assert(Ty-&gt;isPointerType() &amp;&amp; "Can't allocate a non pointer type!");
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]518
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]519 assert((Opcode == Shl || Opcode == Shr) &amp;&amp; "ShiftInst Opcode invalid!");
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]520
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]521 assert(idx &lt; getNumSuccessors() &amp;&amp; "Successor # out of range!");
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]522
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]523 assert(V1.getType() == V2.getType() &amp;&amp; "Constant types must be identical!");
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]524
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]525 assert(isa&lt;PHINode&gt;(Succ-&gt;front()) &amp;&amp; "Only works on PHId BBs!");
526</pre>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]527
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]528<p>You get the idea...</p>
529
530</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]531
532
533<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]534<div class="doc_subsubsection">
535 <a name="hl_preincrement">Prefer Preincrement</a>
536</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]537
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]538<div class="doc_text">
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]539
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]540<p>Hard fast rule: Preincrement (++X) may be no slower than postincrement (X++)
541and could very well be a lot faster than it. Use preincrementation whenever
542possible.</p>
543
544<p>The semantics of postincrement include making a copy of the value being
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]545incremented, returning it, and then preincrementing the "work value". For
546primitive types, this isn't a big deal... but for iterators, it can be a huge
547issue (for example, some iterators contains stack and set objects in them...
548copying an iterator could invoke the copy ctor's of these as well). In general,
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]549get in the habit of always using preincrement, and you won't have a problem.</p>
550
551</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]552
553
554<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]555<div class="doc_subsubsection">
556 <a name="hl_avoidendl">Avoid endl</a>
557</div>
Chris Lattner850d4f62002-01-20 19:01:26 +0000[diff] [blame]558
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]559<div class="doc_text">
560
561<p>The <tt>endl</tt> modifier, when used with iostreams outputs a newline to the
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]562output stream specified. In addition to doing this, however, it also flushes
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]563the output stream. In other words, these are equivalent:</p>
Chris Lattner850d4f62002-01-20 19:01:26 +0000[diff] [blame]564
565<pre>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]566 cout &lt;&lt; endl;
567 cout &lt;&lt; "\n" &lt;&lt; flush;
Chris Lattner850d4f62002-01-20 19:01:26 +0000[diff] [blame]568</pre>
569
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]570<p>Most of the time, you probably have no reason to flush the output stream, so
571it's better to use a literal <tt>"\n"</tt>.</p>
Chris Lattner850d4f62002-01-20 19:01:26 +0000[diff] [blame]572
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]573</div>
Chris Lattner850d4f62002-01-20 19:01:26 +0000[diff] [blame]574
575<!-- _______________________________________________________________________ -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]576<div class="doc_subsubsection">
577 <a name="hl_exploitcpp">Exploit C++ to its Fullest</a>
578</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]579
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]580<div class="doc_text">
581
582<p>C++ is a powerful language. With a firm grasp on its capabilities, you can make
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]583write effective, consise, readable and maintainable code all at the same time.
584By staying consistent, you reduce the amount of special cases that need to be
585remembered. Reducing the total number of lines of code you write is a good way
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]586to avoid documentation, and avoid giving bugs a place to hide.</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]587
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]588<p>For these reasons, come to know and love the contents of your local
Misha Brukmanc3e78932003-07-28 21:57:18 +0000[diff] [blame]589&lt;algorithm&gt; header file. Know about &lt;functional&gt; and what it can do
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]590for you. C++ is just a tool that wants you to master it. :)</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]591
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]592</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]593
594<!-- ======================================================================= -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]595<div class="doc_subsection">
596 <a name="iterators">Writing Iterators</a>
597</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]598
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]599<div class="doc_text">
600
601<p>Here's a pretty good summary of how to write your own data structure iterators
Misha Brukman0cedb1f2003-10-06 19:26:00 +0000[diff] [blame]602in a way that is compatible with the STL, and with a lot of other code out there
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]603(slightly edited by Chris):</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]604
605<pre>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]606From: Ross Smith &lt;ross.s@ihug.co.nz&gt;
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]607Newsgroups: comp.lang.c++.moderated
608Subject: Writing iterators (was: Re: Non-template functions that take iterators)
609Date: 28 Jun 2001 12:07:10 -0400
610
611Andre Majorel wrote:
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]612&gt; Any pointers handy on "writing STL-compatible iterators for
613&gt; dummies ?"
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]614
615I'll give it a try...
616
617The usual situation requiring user-defined iterators is that you have
618a type that bears some resemblance to an STL container, and you want
619to provide iterators so it can be used with STL algorithms. You need
620to ask three questions:
621
622First, is this simply a wrapper for an underlying collection of
623objects that's held somewhere as a real STL container, or is it a
624"virtual container" for which iteration is (under the hood) more
625complicated than simply incrementing some underlying iterator (or
626pointer or index or whatever)? In the former case you can frequently
627get away with making your container's iterators simply typedefs for
628those of the underlying container; your begin() function would call
629member_container.begin(), and so on.
630
631Second, do you only need read-only iterators, or do you need separate
632read-only (const) and read-write (non-const) iterators?
633
634Third, which kind of iterator (input, output, forward, bidirectional,
635or random access) is appropriate? If you're familiar with the
636properties of the iterator types (if not, visit
637<a href="http://www.sgi.com/tech/stl/">http://www.sgi.com/tech/stl/</a>), the appropriate choice should be
638obvious from the semantics of the container.
639
640I'll start with forward iterators, as the simplest case that's likely
641to come up in normal code. Input and output iterators have some odd
642properties and rarely need to be implemented in user code; I'll leave
643them out of discussion. Bidirectional and random access iterators are
644covered below.
645
646The exact behaviour of a forward iterator is spelled out in the
647Standard in terms of a set of expressions with specified behaviour,
648rather than a set of member functions, which leaves some leeway in how
649you actually implement it. Typically it looks something like this
650(I'll start with the const-iterator-only situation):
651
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]652 #include &lt;iterator&gt;
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]653
654 class container {
655 public:
656 typedef something_or_other value_type;
657 class const_iterator:
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]658 public std::iterator&lt;std::forward_iterator_tag, value_type&gt; {
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]659 friend class container;
660 public:
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]661 const value_type&amp; operator*() const;
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]662 const value_type* operator-&gt;() const;
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]663 const_iterator&amp; operator++();
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]664 const_iterator operator++(int);
665 friend bool operator==(const_iterator lhs,
666 const_iterator rhs);
667 friend bool operator!=(const_iterator lhs,
668 const_iterator rhs);
669 private:
670 //...
671 };
672 //...
673 };
674
675An iterator should always be derived from an instantiation of the
676std::iterator template. The iterator's life cycle functions
677(constructors, destructor, and assignment operator) aren't declared
678here; in most cases the compiler-generated ones are sufficient. The
679container needs to be a friend of the iterator so that the container's
680begin() and end() functions can fill in the iterator's private members
681with the appropriate values.
682
683<i>[Chris's Note: I prefer to not make my iterators friends. Instead, two
684ctor's are provided for the iterator class: one to start at the end of the
685container, and one at the beginning. Typically this is done by providing
686two constructors with different signatures.]</i>
687
688There are normally only three member functions that need nontrivial
689implementations; the rest are just boilerplate.
690
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]691 const container::value_type&amp;
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]692 container::const_iterator::operator*() const {
693 // find the element and return a reference to it
694 }
695
696 const container::value_type*
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]697 container::const_iterator::operator-&gt;() const {
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]698 return &amp;**this;
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]699 }
700
701If there's an underlying real container, operator*() can just return a
702reference to the appropriate element. If there's no actual container
703and the elements need to be generated on the fly -- what I think of as
704a "virtual container" -- things get a bit more complicated; you'll
705probably need to give the iterator a value_type member object, and
706fill it in when you need to. This might be done as part of the
707increment operator (below), or if the operation is nontrivial, you
708might choose the "lazy" approach and only generate the actual value
709when one of the dereferencing operators is called.
710
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]711The operator-&gt;() function is just boilerplate around a call to
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]712operator*().
713
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]714 container::const_iterator&amp;
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]715 container::const_iterator::operator++() {
716 // the incrementing logic goes here
717 return *this;
718 }
719
720 container::const_iterator
721 container::const_iterator::operator++(int) {
722 const_iterator old(*this);
723 ++*this;
724 return old;
725 }
726
727Again, the incrementing logic will usually be trivial if there's a
728real container involved, more complicated if you're working with a
729virtual container. In particular, watch out for what happens when you
730increment past the last valid item -- this needs to produce an
731iterator that will compare equal to container.end(), and making this
732work is often nontrivial for virtual containers.
733
734The post-increment function is just boilerplate again (and
735incidentally makes it obvious why all the experts recommend using
736pre-increment wherever possible).
737
738 bool operator==(container::const_iterator lhs,
739 container::const_iterator rhs) {
740 // equality comparison goes here
741 }
742
743 bool operator!=(container::const_iterator lhs,
744 container::const_iterator rhs) {
745 return !(lhs == rhs);
746 }
747
748For a real container, the equality comparison will usually just
749compare the underlying iterators (or pointers or indices or whatever).
750The semantics of comparisons for virtual container iterators are often
751tricky. Remember that iterator comparison only needs to be defined for
752iterators into the same container, so you can often simplify things by
753taking for granted that lhs and rhs both point into the same container
754object. Again, the second function is just boilerplate.
755
756It's a matter of taste whether iterator arguments are passed by value
757or reference; I've shown tham passed by value to reduce clutter, but
758if the iterator contains several data members, passing by reference
759may be better.
760
761That convers the const-iterator-only situation. When we need separate
762const and mutable iterators, one small complication is added beyond
763the simple addition of a second class.
764
765 class container {
766 public:
767 typedef something_or_other value_type;
768 class const_iterator;
769 class iterator:
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]770 public std::iterator&lt;std::forward_iterator_tag, value_type&gt; {
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]771 friend class container;
772 friend class container::const_iterator;
773 public:
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]774 value_type&amp; operator*() const;
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]775 value_type* operator-&gt;() const;
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]776 iterator&amp; operator++();
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]777 iterator operator++(int);
778 friend bool operator==(iterator lhs, iterator rhs);
779 friend bool operator!=(iterator lhs, iterator rhs);
780 private:
781 //...
782 };
783 class const_iterator:
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]784 public std::iterator&lt;std::forward_iterator_tag, value_type&gt; {
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]785 friend class container;
786 public:
787 const_iterator();
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]788 const_iterator(const iterator&amp; i);
789 const value_type&amp; operator*() const;
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]790 const value_type* operator-&gt;() const;
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]791 const_iterator&amp; operator++();
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]792 const_iterator operator++(int);
793 friend bool operator==(const_iterator lhs,
794 const_iterator rhs);
795 friend bool operator!=(const_iterator lhs,
796 const_iterator rhs);
797 private:
798 //...
799 };
800 //...
801 };
802
803There needs to be a conversion from iterator to const_iterator (so
804that mixed-type operations, such as comparison between an iterator and
805a const_iterator, will work). This is done here by giving
806const_iterator a conversion constructor from iterator (equivalently,
807we could have given iterator an operator const_iterator()), which
808requires const_iterator to be a friend of iterator, so it can copy its
809data members. (It also requires the addition of an explicit default
810constructor to const_iterator, since the existence of another
811user-defined constructor inhibits the compiler-defined one.)
812
813Bidirectional iterators add just two member functions to forward
814iterators:
815
816 class iterator:
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]817 public std::iterator&lt;std::bidirectional_iterator_tag, value_type&gt; {
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]818 public:
819 //...
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]820 iterator&amp; operator--();
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]821 iterator operator--(int);
822 //...
823 };
824
825I won't detail the implementations, they're obvious variations on
826operator++().
827
828Random access iterators add several more member and friend functions:
829
830 class iterator:
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]831 public std::iterator&lt;std::random_access_iterator_tag, value_type&gt; {
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]832 public:
833 //...
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]834 iterator&amp; operator+=(difference_type rhs);
835 iterator&amp; operator-=(difference_type rhs);
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]836 friend iterator operator+(iterator lhs, difference_type rhs);
837 friend iterator operator+(difference_type lhs, iterator rhs);
838 friend iterator operator-(iterator lhs, difference_type rhs);
839 friend difference_type operator-(iterator lhs, iterator rhs);
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]840 friend bool operator&lt;(iterator lhs, iterator rhs);
841 friend bool operator&gt;(iterator lhs, iterator rhs);
842 friend bool operator&lt;=(iterator lhs, iterator rhs);
843 friend bool operator&gt;=(iterator lhs, iterator rhs);
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]844 //...
845 };
846
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]847 container::iterator&amp;
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]848 container::iterator::operator+=(container::difference_type rhs) {
849 // add rhs to iterator position
850 return *this;
851 }
852
Chris Lattner5033c4c2003-04-23 16:25:38 +0000[diff] [blame]853 container::iterator&amp;
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]854 container::iterator::operator-=(container::difference_type rhs) {
855 // subtract rhs from iterator position
856 return *this;
857 }
858
859 container::iterator operator+(container::iterator lhs,
860 container::difference_type rhs) {
861 return iterator(lhs) += rhs;
862 }
863
864 container::iterator operator+(container::difference_type lhs,
865 container::iterator rhs) {
866 return iterator(rhs) += lhs;
867 }
868
869 container::iterator operator-(container::iterator lhs,
870 container::difference_type rhs) {
871 return iterator(lhs) -= rhs;
872 }
873
874 container::difference_type operator-(container::iterator lhs,
875 container::iterator rhs) {
876 // calculate distance between iterators
877 }
878
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]879 bool operator&lt;(container::iterator lhs, container::iterator rhs) {
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]880 // perform less-than comparison
881 }
882
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]883 bool operator&gt;(container::iterator lhs, container::iterator rhs) {
884 return rhs &lt; lhs;
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]885 }
886
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]887 bool operator&lt;=(container::iterator lhs, container::iterator rhs) {
888 return !(rhs &lt; lhs);
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]889 }
890
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]891 bool operator&gt;=(container::iterator lhs, container::iterator rhs) {
892 return !(lhs &lt; rhs);
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]893 }
894
895Four of the functions (operator+=(), operator-=(), the second
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]896operator-(), and operator&lt;()) are nontrivial; the rest are
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]897boilerplate.
898
899One feature of the above code that some experts may disapprove of is
900the declaration of all the free functions as friends, when in fact
901only a few of them need direct access to the iterator's private data.
902I originally got into the habit of doing this simply to keep the
903declarations together; declaring some functions inside the class and
904some outside seemed awkward. Since then, though, I've been told that
905there's a subtle difference in the way name lookup works for functions
906declared inside a class (as friends) and outside, so keeping them
907together in the class is probably a good idea for practical as well as
908aesthetic reasons.
909
910I hope all this is some help to anyone who needs to write their own
911STL-like containers and iterators.
912
913--
Chris Lattner245b5252003-08-07 21:45:47 +0000[diff] [blame]914Ross Smith &lt;ross.s@ihug.co.nz&gt; The Internet Group, Auckland, New Zealand
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]915</pre>
916
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]917</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]918
919<!-- *********************************************************************** -->
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]920<div class="doc_section">
921 <a name="seealso">See Also</a>
922</div>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]923<!-- *********************************************************************** -->
924
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]925<div class="doc_text">
926
927<p>A lot of these comments and recommendations have been culled for other
928sources. Two particularly important books for our work are:</p>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]929
930<ol>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]931
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]932<li><a href="http://www.aw.com/product/0,2627,0201924889,00.html">Effective
933C++</a> by Scott Meyers. There is an online version of the book (only some
934chapters though) <a
935href="http://www.awlonline.com/cseng/meyerscddemo/">available as well</a>.</li>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]936
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]937<li><a href="http://cseng.aw.com/book/0,3828,0201633620,00.html">Large-Scale C++
938Software Design</a> by John Lakos</li>
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]939
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]940</ol>
941
942<p>If you get some free time, and you haven't read them: do so, you might learn
943something. :)</p>
944
945</div>
946
Chris Lattnerac457c42001-07-09 03:27:08 +0000[diff] [blame]947<!-- *********************************************************************** -->
948
949<hr>
Misha Brukmanf196dbb2003-10-24 17:57:33 +0000[diff] [blame^]950
951<div class="doc_footer">
952 <address><a href="mailto:sabre@nondot.org">Chris Lattner</a></address>
953 Last modified: $Date$
954</div>
955
956</body>
957</html>