A Tour of Go(Exercise: Web Crawler)をツアーで学習したことだけで解答

# 目的
A Tour of Goは、Goを始める人なら誰でも通る道かと思うが、Exerciseは初見では結構頭を捻った。
仮に解けなくても、多くの解答がWebにあるので、理解して進めることができる。
ただし、最後の問題だけは、探しても`ツアーの中で学んだものだけ`で解かれたものがなかった。# 探し方が悪いだけかもしれないが。。。
今回、ツアーで学んだものだけで解いたので、(スマートではないだろうが)残しておく。

# 問題内容
[A Tour of Go | Exercise: Web Crawler](https://go-tour-jp.appspot.com/concurrency/10)
> 同じURLを2度取ってくることなく並列してURLを取ってくるように、 Crawl 関数を修正してみてください(注1)。

> 補足: 工夫すれば Crawl 関数のみの修正で実装できますが、無理に Crawl 関数内部に収める必要はありません。

> ひとこと: mapにフェッチしたURLのキャッシュを保持できますが、mapだけでは並行実行時の安全性はありません!

<details><summary>問題となるコード</summary><div>

```golang:exercise-web-crawler.go
package main

import (
	"fmt"
)

type Fetcher interface {
	// Fetch returns the body of URL and
	// a slice of URLs found on that page.
	Fetch(url string) (body string, urls []string, err error)
}

// Crawl uses fetcher to recursively crawl
// pages starting with url, to a maximum of depth.
func Crawl(url string, depth int, fetcher Fetcher) {
	// TODO: Fetch URLs in parallel.
	// TODO: Don't fetch the same URL twice.
	// This implementation doesn't do either:
	if depth <= 0 {
		return
	}
	body, urls, err := fetcher.Fetch(url)
	if err != nil {
		fmt.Println(err)
		return
	}
	fmt.Printf("found: %s %q\n", url, body)
	for _, u := range urls {
		Crawl(u, depth-1, fetcher)
	}
	return
}

func main() {
	Crawl("https://golang.org/", 4, fetcher)
}

// fakeFetcher is Fetcher that returns canned results.
type fakeFetcher map[string]*fakeResult

type fakeResult struct {
	body string
	urls []string
}

func (f fakeFetcher) Fetch(url string) (string, []string, error) {
	if res, ok := f[url]; ok {
		return res.body, res.urls, nil
	}
	return "", nil, fmt.Errorf("not found: %s", url)
}

// fetcher is a populated fakeFetcher.
var fetcher = fakeFetcher{
	"https://golang.org/": &fakeResult{
		"The Go Programming Language",
		[]string{
			"https://golang.org/pkg/",
			"https://golang.org/cmd/",
		},
	},
	"https://golang.org/pkg/": &fakeResult{
		"Packages",
		[]string{
			"https://golang.org/",
			"https://golang.org/cmd/",
			"https://golang.org/pkg/fmt/",
			"https://golang.org/pkg/os/",
		},
	},
	"https://golang.org/pkg/fmt/": &fakeResult{
		"Package fmt",
		[]string{
			"https://golang.org/",
			"https://golang.org/pkg/",
		},
	},
	"https://golang.org/pkg/os/": &fakeResult{
		"Package os",
		[]string{
			"https://golang.org/",
			"https://golang.org/pkg/",
		},
	},
}
```
</div></details>

## このコードは何をやっているのか
まず`mail()`では、`Crawl("https://golang.org/", 4, fetcher)`を呼んでいる。
また、`fetcher.Fetch(url)`で取得した複数のURLに対して、`Crawl(u, depth-1, fetcher)`を呼んでいることがわかる。
`Crawl()`関数を見てみると、`depth <= 0`で`return`しており、`Crawl()`関数を呼ぶ度に`depth-1`している。
つまり、各URLに対して最大で3回`Crawl()`関数が呼ばれてる。

次に、`fetcher`の形と値を照らし合わせて見てみる。

```golang:39-44L
type fakeFetcher map[string]*fakeResult

type fakeResult struct {
	body string
	urls []string
}
```

```golang:54-61L
var fetcher = fakeFetcher{
	"https://golang.org/": &fakeResult{
		"The Go Programming Language",
		[]string{
			"https://golang.org/pkg/",
			"https://golang.org/cmd/",
		},
	},
```

1つ目を見ると`fetcher`は、`map[key]{ body, urls[XXX, YYY] }`の形をしてることがわかる。

`fetcher["https://golang.org/"].body`を呼ぶと、`The Go Programming Language`
`fetcher["https://golang.org/"].urls`を呼ぶと、`[https://golang.org/pkg/ https://golang.org/cmd/]`
が出力される。
ここまで分かると、`fetcher.Fetch(url)`はつまるところ、上記を返しているに過ぎないことがわかる。

そして、`urls`の各々に対して、同じことを最大3回、もしくはmapのkey(url)が存在しない(=not found)と分かるまで繰り返している。

# 解答までの道のり

問題内容から、やることとしては大きく2つ

1. URL取得の並列化
2. URLを1度しか呼ばない

1.に関しては、`goroutine`を使えば可能。また、同期を取るために`chanel`を使えばよさそう。
2.に関しては、`ひとこと`に書いてあるとおり、`map`を使えばできそう。
ただし、並列実行するので排他制御`mutex(Lock(),Unlock())`する必要がありそう。

まずは`main()`で呼ばれている`Crawl()`を見てみる。

```golang
func Crawl(url string, depth int, fetcher Fetcher) {
	// TODO: Fetch URLs in parallel.
	// TODO: Don't fetch the same URL twice.
	// This implementation doesn't do either:
	if depth <= 0 {
		return
	}
	body, urls, err := fetcher.Fetch(url)
	if err != nil {
		fmt.Println(err)
		return
	}
	fmt.Printf("found: %s %q\n", url, body)
	for _, u := range urls {
		Crawl(u, depth-1, fetcher)
	}
	return
}
```

再帰呼び出しとなっているが、`chanel`を使うとなると、もう1つ関数を中で作ればよさそう。


元の処理をまるっと`crawlChild()`に入れてみた。

```golang
func Crawl(url string, depth int, fetcher Fetcher) {
	// TODO: Fetch URLs in parallel.
	// TODO: Don't fetch the same URL twice.
	// This implementation doesn't do either:
	var crawlChild func(string, int)
	crawlChild = func(url string, depth int) {
		if depth <= 0 {
			return
		}
		body, urls, err := fetcher.Fetch(url)
		if err != nil {
			fmt.Println(err)
			return
		}
		fmt.Printf("found: %s %q\n", url, body)
		for _, u := range urls {
			go crawlChild(u, depth-1)
		}
	}
	crawlChild(url, depth)
	return
}
```

これで実行すると、1つしか出力されない。他の`goroutine`を待たずして終わってしまうから。

```
found: https://golang.org/ "The Go Programming Language"
```

`chanel`を使うように修正してみる。

```golang
func Crawl(url string, depth int, fetcher Fetcher) {
	// TODO: Fetch URLs in parallel.
	// TODO: Don't fetch the same URL twice.
	// This implementation doesn't do either:
    // 追加
	ch := make(chan string, depth*depth)
	var prev int

	var crawlChild func(string, int)
	crawlChild = func(url string, depth int) {
		if depth <= 0 {
			return
		}
        // 追加
		ch <- url
		body, urls, err := fetcher.Fetch(url)
		if err != nil {
			fmt.Println(err)
			return
		}
		fmt.Printf("found: %s %q\n", url, body)
		for _, u := range urls {
			go crawlChild(u, depth-1)
		}
	}
	crawlChild(url, depth)
    // 追加
	for {
		if len(ch) != prev {
			prev = len(ch)
		} else {
			break
		}
		time.Sleep(time.Millisecond)
	}
	return
}
```
`make()`でサイズを指定しないと、deadlockとなるので指定してますが、適したサイズがわからないので、`depth*depth`としてみた。
そして、return前に、本来の使い方ではないけど、`chanel`数がこれ以上増えないと分かるまで無限ループで待つようにする。

この状態で実行すると、ようやっと最初と同じ結果が得られた。
あとは、URLを1度しか呼ばないようにするだけ。URLをkeyとした、`map[string]bool`で、URLを呼ぶ前にT/F判定させればよさそう。

```golang
func Crawl(url string, depth int, fetcher Fetcher) {
	// TODO: Fetch URLs in parallel.
	// TODO: Don't fetch the same URL twice.
	// This implementation doesn't do either:
    // 追加
	ch := make(chan string, depth*depth)
	var prev int
    // 追加
	cache := make(map[string]bool)
	var mutex sync.Mutex

	var crawlChild func(string, int)
	crawlChild = func(url string, depth int) {
		if depth <= 0 {
			return
		}
		// 追加
		if cache[url] == true {
			return
		}
		mutex.Lock()
		defer mutex.Unlock()
		cache[url] = true

    	// 追加
		ch <- url
		body, urls, err := fetcher.Fetch(url)
		if err != nil {
			fmt.Println(err)
			return
		}
		fmt.Printf("found: %s %q\n", url, body)
		for _, u := range urls {
			go crawlChild(u, depth-1)
		}
	}
	crawlChild(url, depth)
    // 追加
	for {
		if len(ch) != prev {
			prev = len(ch)
		} else {
			break
		}
		time.Sleep(time.Millisecond)
	}
	return
}
```

実行すると、見事に1度しか呼ばれないようになった。

```
found: https://golang.org/ "The Go Programming Language"
found: https://golang.org/pkg/ "Packages"
found: https://golang.org/pkg/os/ "Package os"
not found: https://golang.org/cmd/
found: https://golang.org/pkg/fmt/ "Package fmt"

Program exited.
```

全体のコードは、下記にあります。
[a-tour-of-go/exercise-web-crawler.go at master · hirano00o/a-tour-of-go](https://github.com/hirano00o/a-tour-of-go/blob/master/exercise-web-crawler.go)

# 最後に
A Tour of Goは、中々に長い道のりですが、一通り基本は身につくので、やったほうが良いかと思います。
これが終わったら、実際になにか作るか、go Wiki(英語)、CodeReviewCommentsを見てくかですかね。

CodeReviewCommentに関しては、和訳してくれた方がいるので、そちらを見ればいいのかなと思います。

## 参考
- [Home · golang/go Wiki](https://github.com/golang/go/wiki#getting-started-with-go)
- [#golang CodeReviewComments 日本語翻訳 - Qiita](https://qiita.com/knsh14/items/8b73b31822c109d4c497)