Chapter 4 Composite Types
Exercise 4.1: Write a function that counts the number of bits that are different in two SHA256 hashes. (See PopCount from Section2.6.2.)
// difference means 'xor'
// only accepted sha256 digest
func bitsDiff(b1, b2 *[sha256.Size]byte) int {
var sum int
for i := 0; i < sha256.Size; i++ {
sum += int(pc[b1[i]^b2[i]])
}
return sum
}
Exercise 4.2: Write a program that prints the SHA256 hash of its standard input by default but supports a command-line flag to print the SHA384 or SHA512 hash instead.
// Copyright © 2017 [email protected]
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 83.
// The sha256 command computes the SHA256 hash (an array) of a string.
package main
//!+
import (
"bufio"
"crypto/sha256"
"crypto/sha512"
"flag"
"fmt"
"os"
"strconv"
)
var len = flag.String("n", "256", "Generate sha256/384/512 digest")
func main() {
flag.Parse()
algo, err := strconv.Atoi(*len)
// parameter validation
if err != nil ||
algo != 256 && algo != 384 && algo != 512 {
algo = 256
}
input := bufio.NewScanner(os.Stdin)
for input.Scan() {
text := input.Text()
switch algo {
case 256:
fmt.Printf("%x\n", sha256.Sum256([]byte(text)))
case 384:
fmt.Printf("%x\n", sha512.Sum384([]byte(text)))
case 512:
fmt.Printf("%x\n", sha512.Sum512([]byte(text)))
default:
fmt.Printf("%x\n", sha256.Sum256([]byte(text)))
}
// ignore Err
}
}
//!-
Exercise 4.3: Rewrite rverse to use an array pointer instead of a slice.
// array pointer version, which is very limited compared with slice version
// pointer to avoid copy the whole array
func reverse2(s *[6]int) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
Exercise 4.4: Write a version of rotate that operates in a single pass.
// rotateLeft rotate slice s left
func rotateLeft(s []int, n int) []int {
n = n % len(s)
if n > 0 && n < len(s) {
temp := make([]int, n)
copy(temp, s[:n])
copy(s, s[n:])
copy(s[len(s)-n:], temp)
}
return s
}
Exercise 4.5: Write an in-place function to eliminate adjacent duplicates in a []string slice.
// filterDup filter adjacent strings in place
func filteDup(s []string) []string {
if len(s) == 0 {
return s
}
i := 0
for j := 1; j < len(s); j++ {
if s[j] != s[i] {
i++
s[i] = s[j]
}
}
return s[:i+1]
}
Exercise 4.6: Write an in-place function that squashes each run of adjacent Unicode spaces (seeunicode.IsSpace) in a UTF-8-encoded []byte slice into a single ASCII space.
// squashSpace squashes each rune of adjacent Unicode spaces in
// UTF-8 encoded []byte slice into a single ASCII space
func squashSpace(bytes []byte) []byte {
out := bytes[:0]
var last rune
for i := 0; i < len(bytes); {
r, s := utf8.DecodeRune(bytes[i:])
if !unicode.IsSpace(r) {
out = append(out, bytes[i:i+s]...)
} else if unicode.IsSpace(r) && !unicode.IsSpace(last) {
out = append(out, ' ')
}
last = r
i += s
}
return out
}
Exercise 4.7: Modify reverse to reverse the characters of a []byte slice that represents a UTF-8-encoded string, in place. Can you do it without allocating new memory?
// reverse reverses a []byte slice (UTF8-encoded string) in place.
// version 1:
func reverse(in [] byte) {
buf := make([]byte, 0, len(in))
i := len(in)
for i > 0 {
_, s := utf8.DecodeLastRune(in[:i])
buf = append(buf, in[i-s:i]...)
i -= s
}
copy(in, buf)
}
// version 2:
// Can you do it without allocating memory?
// Based on UTF8's property: prefix code
// though this method is not general, should have more elegant solution
func reverse2(in []byte) {
// first treat as non utf8-encoded data
for i, j := 0, len(in)-1; i < j; i, j = i+1, j-1 {
in[i], in[j] = in[j], in[i]
}
// try to decode according to utf8, then fix error
i := 0
for i < len(in) {
var tryTwo, tryThree, tryFour bool
for {
r, s := utf8.DecodeRune(in[i:])
if r != utf8.RuneError {
i += s
break
} else {
// try two byte length, swap two bytes
if !tryTwo {
tryTwo = true
in[i], in[i+1] = in[i+1], in[i]
continue
}
// try three byte length, swap three bytes
if !tryThree {
// cancel tryTwo side effect
in[i], in[i+1] = in[i+1], in[i]
tryThree = true
in[i], in[i+2] = in[i+2], in[i]
continue
}
// try four byte length, swap four bytes
if !tryFour {
// cancel tryThree side effect
in[i], in[i+1], in[i+2] = in[i+2], in[i+1], in[i]
tryFour = true
in[i], in[i+1], in[i+2], in[i+3] = in[i+3], in[i+2], in[i+1], in[i]
continue
}
// should not be here
panic("Should not be here!")
}
}
}
}
Exercise 4.8: Modify charcount to count letters, digits, and so on in their Unicode categories, using functions like unicode.IsLetter.
// Copyright © 2017 [email protected]
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 97.
//!+
// Charcount computes counts of Unicode characters.
package main
import (
"bufio"
"fmt"
"io"
"os"
"unicode"
"unicode/utf8"
)
const (
Control = iota
Letter
Mark
Number
Punct
Space
Symbol
Graphic
Print
UTFCatCount
)
func main() {
counts := make(map[rune]int) // counts of Unicode characters
var utflen [utf8.UTFMax + 1]int // count of lengths of UTF-8 encodings
var utfcat [UTFCatCount]int // count of categories of UTF-8 encodings
invalid := 0 // count of invalid UTF-8 characters
in := bufio.NewReader(os.Stdin)
for {
r, n, err := in.ReadRune() // returns rune, nbytes, error
if err == io.EOF {
break
}
if err != nil {
fmt.Fprintf(os.Stderr, "charcount: %v\n", err)
os.Exit(1)
}
if r == unicode.ReplacementChar && n == 1 {
invalid++
continue
}
if unicode.IsPrint(r) {
utfcat[Print]++
}
if unicode.IsGraphic(r) {
utfcat[Graphic]++
}
switch {
case unicode.IsControl(r):
utfcat[Control]++
case unicode.IsLetter(r):
utfcat[Letter]++
case unicode.IsMark(r):
utfcat[Mark]++
case unicode.IsNumber(r):
utfcat[Number]++
case unicode.IsPunct(r):
utfcat[Punct]++
case unicode.IsSymbol(r):
utfcat[Symbol]++
case unicode.IsSpace(r):
utfcat[Space]++
}
counts[r]++
utflen[n]++
}
fmt.Printf("rune\tcount\n")
for c, n := range counts {
fmt.Printf("%q\t%d\n", c, n)
}
fmt.Print("\nlen\tcount\n")
for i, n := range utflen {
if i > 0 {
fmt.Printf("%d\t%d\n", i, n)
}
}
fmt.Print("\nCategory Count\n")
// %m.gs, m: width, less<m print spacem >m,then show original char
// g: control the count of char can be printed
// -: left align, default: right align
fmt.Printf("%-7.7s: %4d\n", "Print", utfcat[Print])
fmt.Printf("%-7.7s: %4d\n", "Graphic", utfcat[Graphic])
fmt.Printf("%-7.7s: %4d\n", "Control", utfcat[Control])
fmt.Printf("%-7.7s: %4d\n", "Letter", utfcat[Letter])
fmt.Printf("%-7.7s: %4d\n", "Mark", utfcat[Mark])
fmt.Printf("%-7.7s: %4d\n", "Number", utfcat[Number])
fmt.Printf("%-7.7s: %4d\n", "Punct", utfcat[Punct])
fmt.Printf("%-7.7s: %4d\n", "Space", utfcat[Space])
fmt.Printf("%-7.7s: %4d\n", "Symbol", utfcat[Symbol])
if invalid > 0 {
fmt.Printf("\n%d invalid UTF-8 characters\n", invalid)
}
}
//!-
Exercise 4.9: Write a program wordfreq to report the frequency of each word in an input text file.Call input.Split(bufio.ScanWords) before the first call to Scan to break the input into words instead of lines.
// Copyright © 2017 [email protected]
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 97.
//!+
// Charcount computes counts of Unicode characters.
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
counts := make(map[string]int) // counts of Unicode characters
input := bufio.NewScanner(os.Stdin)
// set SplitFunc with ScanWords instead of default ScanLines
// ScanWords just return space-separated words
input.Split(bufio.ScanWords)
for input.Scan() {
counts[input.Text()]++
}
if err := input.Err(); err != nil {
fmt.Fprintf(os.Stderr, "WordCount: %v", err)
os.Exit(1)
}
for k, v := range counts {
fmt.Println(k, v)
}
}
//!-
Exercise 4.10: Modify issues to report the results in age categories, say less than a month old, less than a year old, and more than a year old.
// Copyright © 2017 [email protected]
// Copyright © 2016 Alan A. A. Donovan & Brian W. Kernighan.
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
// See page 112.
//!+
// Issues prints a table of GitHub issues matching the search terms.
package main
import (
"fmt"
"gopl.io/ch4/github"
"log"
"os"
"time"
)
//!+
const aMonth = 31 * 24
const aYear = 31 * 365 * 24
func daysAgo(t time.Time) int {
return int(time.Since(t).Hours())
}
func main() {
result, err := github.SearchIssues(os.Args[1:])
if err != nil {
log.Fatal(err)
}
fmt.Printf("%d issues:\n", result.TotalCount)
var inMonth, inYear, outYear []*github.Issue
for _, item := range result.Items {
// less a month/a year, or more than a year old
if daysAgo(item.CreatedAt) < aYear {
inMonth = append(inMonth, item)
} else if daysAgo(item.CreatedAt) < aMonth {
inYear = append(inYear, item)
} else {
outYear = append(outYear, item)
}
}
fmt.Printf("%d issues less than a month:\n", len(inMonth))
for _, item := range inMonth {
fmt.Printf("#%-5d %9.9s %v %.55s\n",
item.Number, item.User.Login, item.CreatedAt, item.Title)
}
fmt.Printf("\n%d issues less than a year:\n", len(inYear))
for _, item := range inYear {
fmt.Printf("#%-5d %9.9s %v %.55s\n",
item.Number, item.User.Login, item.CreatedAt, item.Title)
}
fmt.Printf("\n%d issues more than a month:\n", len(outYear))
for _, item := range outYear {
fmt.Printf("#%-5d %9.9s %v %.55s\n",
item.Number, item.User.Login, item.CreatedAt, item.Title)
}
}
//!-
Exercise 4.11: Build a tool that lets users create, read, update, and delete GitHub issues from the command line, invoking their preferred text editor when substantial text input is required.
see: https://github.com/xingdl2007/trailsman
Exercise 4.12: The popular web comic xkcd has a JSON interface. For example, a request to https://xkcd.com/571/info.0.json produces a detailed description of comic 571, one of many favorites. Download each URL (once!) and build an offline index. Write a tool xkcd that, using this index, prints the URL and transcript of each comic that matches a search term provided on the command line.
// Copyright © 2017 [email protected]
// License: https://creativecommons.org/licenses/by-nc-sa/4.0/
package main
import (
"bufio"
"encoding/json"
"fmt"
"log"
"net/http"
"os"
"strconv"
"html/template"
)
// suppress auto-escaping with template HTML
type Comic struct {
Title template.HTML
Num int
Img string
Transcript template.HTML
Year string
Month string
Day string
SafeTitle string `json:safe_title`
Alt string
Link string
News string
}
const URLPrefix = "https://xkcd.com/"
const templ = `*****************************************************
Title: {{.Title}}
URL: {{.Num | getURL}}
{{.Transcript}}
*****************************************************
`
func getURL(i int) string {
return URLPrefix + fmt.Sprintf("%d", i)
}
// database
var db = make(map[int]Comic)
func main() {
report := template.Must(template.New("comic").
Funcs(template.FuncMap{"getURL": getURL}).
Parse(templ))
input := bufio.NewReader(os.Stdin)
for {
fmt.Print("=> ")
cmd, err := input.ReadString('\n')
if err != nil {
log.Fatalf("IO error: %v\n", err)
}
// delete tailing '\n'
cmd = cmd[:len(cmd)-1]
if cmd == "" {
continue
}
if cmd == "q" || cmd == "exit" || cmd == "quit" {
os.Exit(0)
}
index, err := strconv.ParseInt(cmd, 10, 64)
if err != nil {
fmt.Println("=> integer required")
continue
}
if comic, ok := db[int(index)]; !ok {
url := URLPrefix + cmd + "/info.0.json"
resp, err := http.Get(url)
if err != nil {
log.Fatalf("xkcd: Web IO error: %v\n", err)
}
if resp.StatusCode != http.StatusOK {
fmt.Printf("xkcd: can't get commic of %d, try another.\n", index)
resp.Body.Close()
continue
}
if err := json.NewDecoder(resp.Body).Decode(&comic); err != nil {
fmt.Printf("xkcd: internal error, invalid json.\n")
resp.Body.Close()
continue
}
// insert into db
db[int(index)] = comic
// don't forget close
resp.Body.Close()
}
comic := db[int(index)]
// print
//fmt.Printf("Title: %s\n", comic.Title)
//fmt.Printf("URL: %s\n\n", )
//fmt.Printf("%s\n", comic.Transcript)
// give text/template a try
report.Execute(os.Stdout, comic)
}
}
Exercise 4.13: The JSON-based web service of the Open Movie Database lets you search https://omdbapi.com/ for a movie by name and download its poster image. Write a tool poster that downloads the poster image for the movie named on the command line.
// skip because doesn't have access
Poster API
The Poster API is only available to patrons.
Previous one-time donors will still have access until July 1st, 2017.
Exercise 4.14: Create a web server that queries GitHub once and then allows navigation of the list of bug reports, milestones, and users.
// TODO: skip for now
Notes
Array: If an array’s element type is comparable then the array type is comparable too, so we may directly compare two arrays of that type using the == operator, which reports whether all corresponding elements are equal.
Go treats arrays like any other type(pass by value, which means will copy array --- all its element --- when pass to a function), but this behavior is different from languages that implicitly pass arrays by reference.
Slice: Arrays and slices are intimately connected. it looks like an array type without a size. A slice is a lightweight data structure that gives access to a subsequence (or perhaps all) of the elements of an array, which is known as the slice’s underlying array. A slice has three components: a pointer, a length, and a capacity.
As an aside, note the similarity of the substring operation on strings to the slice operator on []byte slices. Both are written x[m:n], and both return a subsequence of the original bytes, sharing the underlying representation so that both operations take constant time. The expression x[m:n] yields a string if x is a string, or a []byte if x is a []byte.
In other words, copying a slice creates analias(§2.3.2) for the underlying array.
Unlike arrays, slices are not comparable, so we cannot use == to test whether two slices contain the same elements.
It may be puzzling that slice comparisons do not also work. There are two reasons why deep equivalence is problematic.
First, unlike array elements, the elements of a slice are indirect, making it possible for a slice to contain itself (means?). Although there are ways to deal with such cases, none is simple, efficient, and most importantly, obvious.
Second, because slice elements are indirect, a fixed slice value may contain different elements at different times as the contents of the underlying array are modified. Because a hash table such as Go’s map type makes only shallow copies of its keys, it requires that equality for each key remain the same throughout the lifetime of the hash table. Deep equivalence would thus make slices unsuitable for use as map keys.
For reference types like pointers and channels, the == operator tests reference identity, that is, whether the two entities refer to the same thing. An analogous ‘‘shallow’’ equality test for slices could be useful, and it would solve the problem with maps, but the inconsistent treatment of slices and arrays by the == operator would be confusing. The safest choice is to disallow slice comparisons altogether.
Hash table: The hash table is one of the most ingenious and versatile of all data structures. It is an unordered collection of key/value pairs in which all the keys are distinct, and the value associated with a given key can be retrieved, updated, or removed using a constant number of key comparisons on the average, no matter how large the hash table.
map: In Go, a map is a reference to a hash table. A map element is not a variable, and we cannot take its address. One reason that we can’t take the address of a map element is that growing a map might cause rehashing of existing elements into new storage locations, thus potentially invalidating the address.
map operation: Most operations on maps, including lookup,delete,len, andrangeloops, are safe to perform on a nil map reference, since it behaves like an empty map. But storing to a nil map causes a panic, You must allocate the map before you can store into it.
Structs: A structis an aggregate data type that groups together zero or more named values of arbitrary types as a single entity. Field order is significant to type identity. The name of a struct field is exported if it begins with a capital letter; this is Go’s main access control mechanism. A struct type may contain a mixture of exported and unexported fields.
A named struct type S can’t declare a field of the same type S: an aggregate value cannot contain itself. (An analogous restriction applies to arrays.) But S may declare a field of the pointer type *S, which lets us create recursive data structures like linked lists and trees.
If all the fields of a struct are comparable, the struct itself is comparable.
Struct Embedding and Anonymous Fields: Go lets us declare a field with a type but no name; such fields are called anonymous fields. However, ‘‘anonymous field’’ is something of a misnomer. The anonymous fields do have names—that of the named type—but those names are optional in dot expressions. Unfortunately, there’s no corresponding shorthand for the struct literal syntax.
Because ‘‘anonymous’’ fields do have implicit names, you can’t have two anonymous fields of the same type since their names would conflict. And because the name of the field is implicitly determined by its type, so too is the visibility of the field.
What we’ve seen so far of struct embedding is just a sprinkling of syntactic sugar on the dot notation used to select struct fields. Later, we’ll see that anonymous fields need not be struct types; any named type or pointer to a named type will do. But why would you want to embed a type that has no subfields?
The answer has to do with methods. The shorthand notation used for selecting the fields of an embedded type works for selecting its methods as well. In effect, the outer struct type gains not just the fields of the embedded type but its methods too. This mechanism is the main way that complex object behaviors are composed from simpler ones.Compositionis central to object-oriented programming in Go, and we’ll explore it further in Section 6.3.
JSON: JavaScript Object Notation (JSON) is a standard notation for sending and receiving structured information. JSON is an encoding of JavaScript values—strings, numbers, booleans, arrays, and objects—as Unicode text.
Text and HTML Templates: A template is a string or file containing one or more portions enclosed in double braces, called actions. Most of the string is printed literally, but the actions trigger other behaviors. Each action contains an expression in the template language, a simple but powerful notation for printing values, selecting struct fields, calling functions and methods, expressing control flow such as if-else statements and range loops, and instantiating other templates.
In the same way that a type may control its string formatting (§2.5) by defining certain methods, a type may also define methods to control its JSON marshaling and unmarshaling behavior. The JSON-marshaled value of a time.Time is a string in a standard format.