flow: Closed <feature> 'use_crawler_workers'.

* so now http://a.com/index.html and http://a.com/ are understood equivalents
* as are http://a.com/x.html#blog and http://a.com/x.html (etc.)
* this meant a little more bookkeeping in docrawler, but not horrible
* stripAnchorFromURL because stripURL because it now handles anchor and path suffix stripping
* and url tests were written to support this

docs/Design.md

@@ -2,38 +2,38 @@
 
 ## Minimum Features
 
-This is the assignment (directly) from DO.
+This is the assignment (directly) from **REDACTED**.
 
-* We do ask that you put a heavy emphasis on testing in the assignment.
-* written in a modern language
-* limited to one domain - so when crawling digitalocean.com it would crawl all pages within the digitalocean.com domain, but not follow the links to our Facebook or Instagram accounts or subdomains like cloud.digitalocean.com. 
-* It should be Given a URL
-* it should output a site map
-* it should show which static assets each page depends on, and the links between pages.
-* Choose the most appropriate data structure to store & display this site map.
-* Build this as you would build something for production - it's fine if you don't finish everything, but focus on code quality and write tests.
-* We're interested in how you code and how you test your code.
+✓ We do ask that you put a heavy emphasis on testing in the assignment.
+ written in a modern language
+✓ limited to one domain - so when crawling REDACTED.com it would crawl all pages within the REDACTED.com domain, but not follow the links to our Facebook or Instagram accounts or subdomains like cloud.REDACTED.com. 
+✓ It should be Given a URL
+✓ it should output a site map
+✓ it should show which static assets each page depends on, and the links between pages.
+✓ Choose the most appropriate data structure to store & display this site map.
+✓ Build this as you would build something for production - it's fine if you don't finish everything, but focus on code quality and write tests.
+✓ We're interested in how you code and how you test your code.
 
 ## Desired
 
 These are features I'd like to include.
 
 * efficient, optimal
-* handles base URL properly (for root & relative links)
-* documented
-* uses standard Go practices
-* uses Go stdlib (only!)
-* thoroughly tested
+✓ handles base URL properly (for root & relative links)
+✓ documented
+✓ uses standard Go practices
+✓ uses Go stdlib (only!)
+✓ thoroughly tested
 * configurable on command line (defaults are for company specs)
 * variable output formats: json, dot
-* adheres to URL RFC (as far as case sensitivity, acceptable character sets, etc.)
+✓ adheres to URL RFC (as far as case sensitivity, acceptable character sets, etc.)
 * go gettable
-* go fmt'ed, vet'ed, lint'ed
+✓ go fmt'ed, vet'ed, lint'ed
 * polite - robots.txt support
-* robust - detect infinite loops
+✓ robust - detect infinite loops
 * throttling
 * use Go context pattern
-* supports http & https
+✓ supports http & https
 
 ## Architecture
 
@@ -41,8 +41,8 @@ These are features I'd like to include.
 * pipeline chain should be such that when there's no more work to do the job dispatcher closes the next channel in the pipeline, thereby closing the entire chain of channels (and exiting all goroutines)
 * pipeline may allows us to scale concurrency at the bottlenecks
 * could use Interfaces for things like Parser, Getter, but I think best avoided until needed
-* launch goroutine per fetch
-* when there's no Jobs left, and nothing being fetched or parsed, convert the data struct into something useful and output it
+✓ launch goroutine per fetch
+✓ when there's no Jobs left, and nothing being fetched or parsed, convert the data struct into something useful and output it
 
 ## Wishlist
 

docs/TODO.md

@@ -2,17 +2,12 @@
 
 ## Bugs
 
-* deal with anchor issue (repeatedly crawling index.html#about, index.html#contact, etc.)
-  * should only crawl these pages once
-  * but should be included in the links part
-* when sorting links, "uniq" them as well
-* be smart about index.html?
-
 ## Cleanup
 
 * helper function to do the whole crawl process
 * document code better
   * test with godoc
+* omit fields in json when nil? (Broken, etc.)
 
 ## Features
 

src/docrawler/docrawler.go

@@ -7,16 +7,24 @@ import (
 	"time"
 )
 
-// docrawl begins crawling the site at "homeurl"
-func docrawl(homeurl string) itemSlice {
-	// set of what we have already crawled
-	crawled := make(map[string]struct{})
+// doCrawl begins crawling the site at "homeurl"
+func doCrawl(homeurl string) itemSlice {
+	// set of what we have already crawled, our results
+	crawled := make(itemMap)
 
-	// map (of urlString -> httpItem) of our results
-	results := make(itemMap)
+	// a set of crawled URLs which have been cleaned
+	// useful so that we don't crawl http://a.com/index.html#about if we've
+	// already crawled http://a.com/index.html, or vice versa
+	crawledStripped := make(itemMap)
 
-	// a channel to receive our results on
-	rchan := make(chan *httpItem)
+	// channels to send work to and receive our results on
+	rxchan := make(chan *httpItem)
+	txchan := make(chan *httpItem)
+
+	// spin up our crawler workers
+	for i := 0; i < 10; i++ {
+		go crawlListner(txchan, rxchan)
+	}
 
 	// start a ticker which we'll use to output status and check for completion
 	ticker := time.Tick(250 * time.Millisecond)
@@ -24,52 +32,75 @@ func docrawl(homeurl string) itemSlice {
 	// create first page's httpItem
 	homeitem, err := newHTTPItem(nil, homeurl)
 	if err != nil {
-		log.Fatal("unable to create httpItem for homeurl")
+		return nil
 	}
 
 	// set our number of outstanding pages (initially 1 to account for first page)
 	crawlingCount := 1
 
 	// start the home page crawl
-	crawled[homeitem.url.String()] = struct{}{}
-	go crawlItem(homeitem, rchan)
+	crawled[homeitem.url.String()] = homeitem
+	crawledStripped[stripURL(homeitem.url)] = homeitem
+	txchan <- homeitem
 
 	// wait for results
 	for {
 		select {
-		case r := <-rchan: // new results?
+		case r := <-rxchan: // new results?
 			// add result to our results map
-			results[r.url.String()] = r
+			crawled[r.url.String()] = r
 
 			// decrease the outstanding page count by 1
 			crawlingCount--
 
 			// start crawly any new child pages we haven't yet crawled
 			for i, c := range r.children {
-				// see if we already have a result for this page, if so, point to that result
-				if existing, ok := results[c.url.String()]; ok {
+				// see if we already have a result for this page
+				// if so, point to that result
+				if existing, ok := crawled[c.url.String()]; ok {
 					r.children[i] = existing
 					continue
 				}
 
 				// see if we're already crawling this page (but maybe don't have results yet)
-				if _, ok := crawled[c.url.String()]; !ok {
-					// haven't crawled this one yet, do so now
-					crawlingCount++
-					crawled[c.url.String()] = struct{}{}
-					go crawlItem(c, rchan)
+				// if so, point to that item (we will have it as a result later!)
+				if existing, ok := crawled[c.url.String()]; ok {
+					r.children[i] = existing
+					continue
 				}
+				if existing, ok := crawledStripped[stripURL(c.url)]; ok {
+					// we crawled a different version of this same page
+					// i.e. same page, different anchor. we don't need to crawl it again
+					// but we do need to keep it in our results, so copy the existing
+					// struct over for everything except the URLs
+					r.children[i].title = existing.title
+					r.children[i].linkType = existing.linkType
+					r.children[i].children = existing.children
+					continue
+				}
+
+				// haven't crawled this one yet, do so now
+				crawlingCount++
+				crawled[c.url.String()] = c
+				crawledStripped[stripURL(c.url)] = c
+				go func(newItem *httpItem) {
+					txchan <- newItem
+				}(c)
 			}
 
 		case <-ticker: // our regular ticker. for status output and checking for completion.
 			// output status to console
-			log.Printf("Crawled %v links, have %v left.\n", len(results), crawlingCount)
+			log.Printf("Crawled %v links, have %v left.\n", len(crawled), crawlingCount)
 
 			// see if we're finished
 			if crawlingCount == 0 {
+				// close our channels, signalling any workers to exit
+				close(txchan)
+				close(rxchan)
+
 				// finished! convert results map to a slice and return it
 				rslice := itemSlice{}
-				for _, v := range results {
+				for _, v := range crawled {
 					rslice = append(rslice, v)
 				}
 				return rslice
@@ -78,31 +109,40 @@ func docrawl(homeurl string) itemSlice {
 	}
 }
 
+// crawlListner is a for+select wrapper around crawlItem that listens
+// for new jobs and sends them off to crawlItem
+func crawlListner(txchan <-chan *httpItem, rxchan chan<- *httpItem) {
+	for {
+		select {
+		case newJob, ok := <-txchan:
+			if !ok {
+				// channel closed, finish
+				return
+			}
+			// perform the crawl
+			rxchan <- crawlItem(newJob)
+		}
+	}
+}
+
 // crawlItem crawls a single httpItem, fetching the header, hte page, parsing it,
 // and filling out its structure as much as possible
-func crawlItem(item *httpItem, rchan chan<- *httpItem) {
+func crawlItem(item *httpItem) *httpItem {
 	// make sure this item is the same domain (i.e. URL "host part") as its referrer
 	if item.refurl != nil && item.url.Host != item.refurl.Host {
 		// skip URLs associated with other Hosts
 		item.linkType = tRemote
-		rchan <- item
-		return
+		return item
 	}
 
 	// fetch page
 	text, err := fetchPage(item)
 	if err != nil {
-		rchan <- item
-		return
+		return item
 	}
 
 	// parse links
-	title, links, _ := parseLinks(text) // TODO remove error from parseLinks, not needed
-	if err != nil {
-		item.linkType = tBroken
-		rchan <- item
-		return
-	}
+	title, links := parseLinks(text)
 	item.title = title
 
 	// walk links and add them as children to the current item
@@ -115,13 +155,22 @@ func crawlItem(item *httpItem, rchan chan<- *httpItem) {
 	}
 
 	// send back our item struct now that it's all filled out
-	rchan <- item
+	return item
 }
 
 func main() {
+	// see if we've got no arguments
+	if len(os.Args) == 1 {
+		fmt.Printf("\nD.O. Crawler 1.0  Copyright (c) 2015 Stephen Waits <steve@waits.net>  2015-02-17\n\n")
+		fmt.Printf("usage: %v <URLs...>\n\n", os.Args[0])
+		os.Exit(1)
+	}
 	// crawl each URL on the command line
 	for _, u := range os.Args[1:] {
-		pages := docrawl(u)
+		pages := doCrawl(u)
+		if pages == nil {
+			log.Fatalf("unable to crawl %q, may be an invalid URL\n", u)
+		}
 		l := sitemapToLocations(pages)
 		j, _ := locationsToJSON(l)
 		fmt.Println(j)

src/docrawler/docrawler_test.go

@@ -76,7 +76,7 @@ func TestSimpleFetch(t *testing.T) {
 
 // TestSimpleMap figures out the site map for the site in baseURL
 func TestSimpleMap(t *testing.T) {
-	pages := docrawl(baseURL)
+	pages := doCrawl(baseURL)
 
 	// because our crawl is non-deterministic, we have to do a complete
 	// cycle through every page, counting stuff, finding specific pages
@@ -102,7 +102,7 @@ func TestSimpleMap(t *testing.T) {
 		t.Logf("got %v, wanted %v\n", len(pages), 6)
 		t.Fatal("got wrong number of pages")
 	}
-	if children != 8 {
+	if children != 9 {
 		t.Logf("got %v, wanted %v\n", children, 8)
 		t.Fatal("got wrong number of total children")
 	}
@@ -117,7 +117,7 @@ func TestSimpleMap(t *testing.T) {
 	}
 
 	// specific page number of children
-	if len(homepage.children) != 4 {
+	if len(homepage.children) != 5 {
 		t.Logf("got %v, wanted %v\n", len(homepage.children), 4)
 		t.Fatal("got wrong number of links")
 	}
@@ -185,7 +185,7 @@ func TestHeaderFetching(t *testing.T) {
 
 // TestJsonOutput gets a sitemap and then converts it to json
 func TestJsonOutput(t *testing.T) {
-	pages := docrawl(baseURL)
+	pages := doCrawl(baseURL)
 	l := sitemapToLocations(pages)
 	if len(l) != 2 {
 		t.Error("sitemapToLocations has the wrong number of locations")
@@ -229,7 +229,38 @@ func TestJsonOutput(t *testing.T) {
 	// this is a cheater test because the output is from a run of the code being
 	// test itself. but, it's been examined and I think it's right. and, there's not
 	// many other ways to test this without some significant pain
-	cheaterTest := `[{"URL":"http://localhost:8765/","Title":"Home","Links":["http://localhost:8765/about.html"],"Assets":["http://localhost:8765/assets/image.png","http://localhost:8765/scripts/blah.js"],"Broken":["http://localhost:8765/zzzbroken.html"],"Remote":null},{"URL":"http://localhost:8765/about.html","Title":"About Test","Links":["http://localhost:8765/"],"Assets":["http://localhost:8765/assets/image.png","http://localhost:8765/scripts/blah.js"],"Broken":null,"Remote":["http://doesntexist23492387492837492374982734.com/"]}]`
+	cheaterTest := `[
+  {
+    "URL": "http://localhost:8765/",
+    "Title": "Home",
+    "Links": [
+      "http://localhost:8765/about.html"
+    ],
+    "Assets": [
+      "http://localhost:8765/assets/image.png",
+      "http://localhost:8765/scripts/blah.js"
+    ],
+    "Broken": [
+      "http://localhost:8765/zzzbroken.html"
+    ],
+    "Remote": null
+  },
+  {
+    "URL": "http://localhost:8765/about.html",
+    "Title": "About Test",
+    "Links": [
+      "http://localhost:8765/"
+    ],
+    "Assets": [
+      "http://localhost:8765/assets/image.png",
+      "http://localhost:8765/scripts/blah.js"
+    ],
+    "Broken": null,
+    "Remote": [
+      "http://doesntexist23492387492837492374982734.com/"
+    ]
+  }
+]`
 	j, err := locationsToJSON(l)
 	if err != nil {
 		t.Error("locationsToJSON failed")

src/docrawler/fetch.go

@@ -7,6 +7,7 @@ import (
 	"net/http"
 )
 
+// custom errors
 var (
 	errContentTypeNotFound = errors.New("no Content-Type header found")
 	errFetchError          = errors.New("couldn't fetch item")

src/docrawler/item.go

@@ -13,6 +13,7 @@ type itemMap map[string]*httpItem
 // itemType is an enum so we know how to classify each item
 type itemType int
 
+// enums for itemType
 const (
 	tUnknown itemType = iota
 	tHTMLPage

src/docrawler/output.go

@@ -48,12 +48,20 @@ func sitemapToLocations(pages itemSlice) []*Location {
 					l.Links = append(l.Links, c.url.String())
 				} else if c.linkType == tBroken {
 					l.Broken = append(l.Broken, c.url.String())
-				} else {
+				} else if c.linkType == tAsset {
 					l.Assets = append(l.Assets, c.url.String())
+				} else {
+					// unknown link here, which means it failed to crawl, let's call it "broken"
+					l.Broken = append(l.Broken, c.url.String())
 				}
+
 			}
 
-			// now sort the children slices
+			// now uniq & sort the children slices
+			l.Remote = uniqStrings(l.Remote)
+			l.Links = uniqStrings(l.Links)
+			l.Broken = uniqStrings(l.Broken)
+			l.Assets = uniqStrings(l.Assets)
 			sort.Strings(l.Remote)
 			sort.Strings(l.Links)
 			sort.Strings(l.Broken)
@@ -69,8 +77,9 @@ func sitemapToLocations(pages itemSlice) []*Location {
 	return locations
 }
 
+// locationsToJSON takes a *Location slice and marshals it into a JSON string
 func locationsToJSON(locations []*Location) (string, error) {
-	b, err := json.Marshal(locations)
+	b, err := json.MarshalIndent(locations, "", "  ")
 	if err != nil {
 		return "", err
 	}

src/docrawler/parse.go

@@ -11,7 +11,7 @@ var reTitle = regexp.MustCompile(`(?i)<\s*title\s*>([^<]*)<\s*\/\s*title`)
 
 // parseLinks takes a string and attempts to parse any html title and all links out of it,
 // and returns a slice of the captures found
-func parseLinks(s string) (string, []string, error) {
+func parseLinks(s string) (string, []string) {
 	// find the title, or default to empty
 	title := ""
 	titleMatches := reTitle.FindStringSubmatch(s)
@@ -25,5 +25,5 @@ func parseLinks(s string) (string, []string, error) {
 	for _, match := range reURL.FindAllStringSubmatch(s, -1) {
 		results = append(results, match[2])
 	}
-	return title, results, nil
+	return title, results
 }

src/docrawler/parse_test.go

@@ -16,10 +16,7 @@ func TestSimpleParse(t *testing.T) {
 		<script href="scripts/blah.js"/>
 	</body>
 </html>`
-	title, matches, err := parseLinks(doc)
-	if err != nil {
-		t.Error(err)
-	}
+	title, matches := parseLinks(doc)
 	if title != "Test Page" {
 		t.Error("got wrong title")
 	}

src/docrawler/testsite/index.html

@@ -5,6 +5,7 @@
 	<body>
 		<img src="/assets/image.png"/>
 		<a href="/about.html">fooey!</a>
+		<a href="/about.html">duplicate!</a>
 		<script src="scripts/blah.js"/>
 		<a href="/zzzbroken.html">oops!</a>
 	</body>

src/docrawler/url.go

@@ -6,6 +6,7 @@ import (
 	"strings"
 )
 
+// custom errors
 var (
 	errInvalidURL = errors.New("this URL can't be parsed successfully")
 )
@@ -49,3 +50,27 @@ func resolveURL(referringURL string, currentURL string) (*url.URL, error) {
 	// return the URL we ended up with, and the error from checkURL
 	return uResolved, checkURL(uResolved)
 }
+
+// stripURL returns a version of the URL without the "Fragment" part,
+// which is anything after the '#' character, so:
+// http://a.com/blah.html#anchor becomes http://a.com/blah.html
+// ... and without files like "index.htm" in the Path (since that's
+// equivalent to "/"
+func stripURL(u *url.URL) string {
+	// copy the url locally
+	ucopy := *u
+
+	// blank out the anchor, return URI string
+	ucopy.Fragment = ""
+
+	// remove index.html if it exists
+	suffixes := []string{"index.html", "index.htm"}
+	for _, s := range suffixes {
+		if strings.HasSuffix(strings.ToLower(ucopy.Path), s) {
+			ucopy.Path = ucopy.Path[0 : len(ucopy.Path)-len(s)]
+		}
+	}
+
+	// return new stripped down URL string
+	return ucopy.String()
+}

src/docrawler/url_test.go

@@ -68,3 +68,37 @@ func TestBadResolve(t* testing.T) {
 	}
 }
 */
+
+// TestURLStripAnchor tests the stripURL() function
+func TestURLStripAnchor(t *testing.T) {
+	{
+		u, err := url.Parse("http://swaits:pass@somehost.com:8765/blah/blah.html?x=y#foo")
+		if err != nil {
+			t.Fatal("couldn't parse a URL")
+		}
+		stripped := stripURL(u)
+		if stripped != "http://swaits:pass@somehost.com:8765/blah/blah.html?x=y" {
+			t.Error("stripping anchor #foo from URL failed")
+		}
+	}
+	{
+		u, err := url.Parse("http://swaits:pass@somehost.com:8765/blah/index.html?x=y#foo")
+		if err != nil {
+			t.Fatal("couldn't parse a URL")
+		}
+		stripped := stripURL(u)
+		if stripped != "http://swaits:pass@somehost.com:8765/blah/?x=y" {
+			t.Error("stripping anchor #foo from URL failed")
+		}
+	}
+	{
+		u, err := url.Parse("http://swaits:pass@somehost.com:8765/blah/index.htm?x=y#foo")
+		if err != nil {
+			t.Fatal("couldn't parse a URL")
+		}
+		stripped := stripURL(u)
+		if stripped != "http://swaits:pass@somehost.com:8765/blah/?x=y" {
+			t.Error("stripping anchor #foo from URL failed")
+		}
+	}
+}

src/docrawler/util.go

@@ -0,0 +1,23 @@
+package main
+
+// uniqStrings takes a slice of strings and removes any duplicates
+// note: does not guarantee any order (or stability of order)
+func uniqStrings(strs []string) []string {
+	// handle special case of a nil parameter
+	if strs == nil {
+		return nil
+	}
+
+	// add each string to the slice as keys (used like a "set")
+	set := make(map[string]struct{})
+	for _, s := range strs {
+		set[s] = struct{}{}
+	}
+
+	// now copy all the keys over to a new slice and return it
+	result := []string{}
+	for key := range set {
+		result = append(result, key)
+	}
+	return result
+}

src/docrawler/util_test.go

@@ -0,0 +1,28 @@
+package main
+
+import (
+	"sort"
+	"testing"
+)
+
+// TestUniqStrings passes a slice of strings to uniqStrings() to see if it removes
+// all duplicates
+func TestUniqStrings(t *testing.T) {
+	strs := []string{"a", "a", "b", "a", "b", "c", "d", "a", "b", "e", "d"}
+	uniq := uniqStrings(strs)
+	if len(uniq) != 5 {
+		t.Error("wrong number of strings after uniq'ing")
+	}
+	sort.Strings(uniq)
+	if uniq[0] != "a" || uniq[1] != "b" || uniq[2] != "c" || uniq[3] != "d" || uniq[4] != "e" {
+		t.Error("uniq values are in correct!")
+	}
+}
+
+// TestUniqStringsNilParm passes a nil slice to uniqStrings to be sure it returns nil
+func TestUniqStringsNilParm(t *testing.T) {
+	uniq := uniqStrings(nil)
+	if uniq != nil {
+		t.Error("uniqStrings should return a nil slice when passed a nil slice")
+	}
+}

util/testfilter.sh

@@ -2,6 +2,6 @@
 
 # colorize the output of "go test"
 
-sed ''/ok/s//$(printf "\033[32;1m&\033[0m")/''       | \
+sed ''/^ok/s//$(printf "\033[32;1m&\033[0m")/''       | \
 	sed ''/PASS/s//$(printf "\033[32;1m&\033[0m")/''   | \
 	sed ''/FAIL/s//$(printf "\033[31;1m&\033[0m")/''