Add Hugo Modules

This commit implements Hugo Modules.

This is a broad subject, but some keywords include:

* A new `module` configuration section where you can import almost anything. You can configure both your own file mounts nd the file mounts of the modules you import. This is the new recommended way of configuring what you earlier put in `configDir`, `staticDir` etc. And it also allows you to mount folders in non-Hugo-projects, e.g. the `SCSS` folder in the Bootstrap GitHub project.
* A module consists of a set of mounts to the standard 7 component types in Hugo: `static`, `content`, `layouts`, `data`, `assets`, `i18n`, and `archetypes`. Yes, Theme Components can now include content, which should be very useful, especially in bigger multilingual projects.
* Modules not in your local file cache will be downloaded automatically and even "hot replaced" while the server is running.
* Hugo Modules supports and encourages semver versioned modules, and uses the minimal version selection algorithm to resolve versions.
* A new set of CLI commands are provided to manage all of this: `hugo mod init`,  `hugo mod get`,  `hugo mod graph`,  `hugo mod tidy`, and  `hugo mod vendor`.

All of the above is backed by Go Modules.

Fixes #5973
Fixes #5996
Fixes #6010
Fixes #5911
Fixes #5940
Fixes #6074
Fixes #6082
Fixes #6092

9 files changed, 271 insertions, 186 deletions

diff --git a/helpers/content.go b/helpers/content.go
index 6d9f1ca08..f6576c04f 100644
--- a/helpers/content.go
+++ b/helpers/content.go
@@ -511,12 +511,6 @@ func TotalWords(s string) int {
 	return n
 }
 
-// Old implementation only kept for benchmark comparison.
-// TODO(bep) remove
-func totalWordsOld(s string) int {
-	return len(strings.Fields(s))
-}
-
 // TruncateWordsByRune truncates words by runes.
 func (c *ContentSpec) TruncateWordsByRune(in []string) (string, bool) {
 	words := make([]string, len(in))
diff --git a/helpers/content_test.go b/helpers/content_test.go
index 709c81142..04e9466d0 100644
--- a/helpers/content_test.go
+++ b/helpers/content_test.go
@@ -506,13 +506,3 @@ func BenchmarkTotalWords(b *testing.B) {
 		}
 	}
 }
-
-func BenchmarkTotalWordsOld(b *testing.B) {
-	b.ResetTimer()
-	for i := 0; i < b.N; i++ {
-		wordCount := totalWordsOld(totalWordsBenchmarkString)
-		if wordCount != 400 {
-			b.Fatal("Wordcount error")
-		}
-	}
-}
diff --git a/helpers/docshelper.go b/helpers/docshelper.go
index 8ad817d12..66cbfa7d3 100644
--- a/helpers/docshelper.go
+++ b/helpers/docshelper.go
@@ -36,8 +36,7 @@ func init() {
 				}
 			}
 
-			sort.Strings(aliases)
-			aliases = UniqueStrings(aliases)
+			aliases = UniqueStringsSorted(aliases)
 
 			lexerEntry := struct {
 				Name    string
diff --git a/helpers/general.go b/helpers/general.go
index 3cf7ba8af..5eabda3c6 100644
--- a/helpers/general.go
+++ b/helpers/general.go
@@ -22,15 +22,16 @@ import (
 	"net"
 	"os"
 	"path/filepath"
+	"sort"
 	"strings"
 	"sync"
 	"unicode"
 	"unicode/utf8"
 
-	"github.com/gohugoio/hugo/common/hugo"
-
 	"github.com/gohugoio/hugo/hugofs"
 
+	"github.com/gohugoio/hugo/common/hugo"
+
 	"github.com/spf13/afero"
 
 	"github.com/jdkato/prose/transform"
@@ -106,7 +107,7 @@ func FirstUpper(s string) string {
 
 // UniqueStrings returns a new slice with any duplicates removed.
 func UniqueStrings(s []string) []string {
-	var unique []string
+	unique := make([]string, 0, len(s))
 	set := map[string]interface{}{}
 	for _, val := range s {
 		if _, ok := set[val]; !ok {
@@ -117,6 +118,40 @@ func UniqueStrings(s []string) []string {
 	return unique
 }
 
+// UniqueStringsReuse returns a slice with any duplicates removed.
+// It will modify the input slice.
+func UniqueStringsReuse(s []string) []string {
+	set := map[string]interface{}{}
+	result := s[:0]
+	for _, val := range s {
+		if _, ok := set[val]; !ok {
+			result = append(result, val)
+			set[val] = val
+		}
+	}
+	return result
+}
+
+// UniqueStringsReuse returns a sorted slice with any duplicates removed.
+// It will modify the input slice.
+func UniqueStringsSorted(s []string) []string {
+	if len(s) == 0 {
+		return nil
+	}
+	ss := sort.StringSlice(s)
+	ss.Sort()
+	i := 0
+	for j := 1; j < len(s); j++ {
+		if !ss.Less(i, j) {
+			continue
+		}
+		i++
+		s[i] = s[j]
+	}
+
+	return s[:i+1]
+}
+
 // ReaderToBytes takes an io.Reader argument, reads from it
 // and returns bytes.
 func ReaderToBytes(lines io.Reader) []byte {
@@ -459,17 +494,15 @@ func PrintFs(fs afero.Fs, path string, w io.Writer) {
 	if fs == nil {
 		return
 	}
+
 	afero.Walk(fs, path, func(path string, info os.FileInfo, err error) error {
-		if info != nil && !info.IsDir() {
-			s := path
-			if lang, ok := info.(hugofs.LanguageAnnouncer); ok {
-				s = s + "\tLANG: " + lang.Lang()
-			}
-			if fp, ok := info.(hugofs.FilePather); ok {
-				s = s + "\tRF: " + fp.Filename() + "\tBP: " + fp.BaseDir()
-			}
-			fmt.Fprintln(w, "    ", s)
+		var filename string
+		var meta interface{}
+		if fim, ok := info.(hugofs.FileMetaInfo); ok {
+			filename = fim.Meta().Filename()
+			meta = fim.Meta()
 		}
+		fmt.Fprintf(w, "    %q %q\t\t%v\n", path, filename, meta)
 		return nil
 	})
 }
diff --git a/helpers/general_test.go b/helpers/general_test.go
index ed4c3d2c2..dd61d8948 100644
--- a/helpers/general_test.go
+++ b/helpers/general_test.go
@@ -234,6 +234,24 @@ func TestUniqueStrings(t *testing.T) {
 	}
 }
 
+func TestUniqueStringsReuse(t *testing.T) {
+	in := []string{"a", "b", "a", "b", "c", "", "a", "", "d"}
+	output := UniqueStringsReuse(in)
+	expected := []string{"a", "b", "c", "", "d"}
+	if !reflect.DeepEqual(output, expected) {
+		t.Errorf("Expected %#v, got %#v\n", expected, output)
+	}
+}
+
+func TestUniqueStringsSorted(t *testing.T) {
+	assert := require.New(t)
+	in := []string{"a", "a", "b", "c", "b", "", "a", "", "d"}
+	output := UniqueStringsSorted(in)
+	expected := []string{"", "a", "b", "c", "d"}
+	assert.Equal(expected, output)
+	assert.Nil(UniqueStringsSorted(nil))
+}
+
 func TestFindAvailablePort(t *testing.T) {
 	addr, err := FindAvailablePort()
 	assert.Nil(t, err)
@@ -328,3 +346,55 @@ func BenchmarkMD5FromFileFast(b *testing.B) {
 	}
 
 }
+
+func BenchmarkUniqueStrings(b *testing.B) {
+	input := []string{"a", "b", "d", "e", "d", "h", "a", "i"}
+
+	b.Run("Safe", func(b *testing.B) {
+		for i := 0; i < b.N; i++ {
+			result := UniqueStrings(input)
+			if len(result) != 6 {
+				b.Fatal(fmt.Sprintf("invalid count: %d", len(result)))
+			}
+		}
+	})
+
+	b.Run("Reuse slice", func(b *testing.B) {
+		b.StopTimer()
+		inputs := make([][]string, b.N)
+		for i := 0; i < b.N; i++ {
+			inputc := make([]string, len(input))
+			copy(inputc, input)
+			inputs[i] = inputc
+		}
+		b.StartTimer()
+		for i := 0; i < b.N; i++ {
+			inputc := inputs[i]
+
+			result := UniqueStringsReuse(inputc)
+			if len(result) != 6 {
+				b.Fatal(fmt.Sprintf("invalid count: %d", len(result)))
+			}
+		}
+	})
+
+	b.Run("Reuse slice sorted", func(b *testing.B) {
+		b.StopTimer()
+		inputs := make([][]string, b.N)
+		for i := 0; i < b.N; i++ {
+			inputc := make([]string, len(input))
+			copy(inputc, input)
+			inputs[i] = inputc
+		}
+		b.StartTimer()
+		for i := 0; i < b.N; i++ {
+			inputc := inputs[i]
+
+			result := UniqueStringsSorted(inputc)
+			if len(result) != 6 {
+				b.Fatal(fmt.Sprintf("invalid count: %d", len(result)))
+			}
+		}
+	})
+
+}
diff --git a/helpers/path.go b/helpers/path.go
index 36bd3269b..12ddfeb56 100644
--- a/helpers/path.go
+++ b/helpers/path.go
@@ -26,6 +26,8 @@ import (
 
 	"github.com/gohugoio/hugo/config"
 
+	"github.com/gohugoio/hugo/hugofs"
+
 	"github.com/gohugoio/hugo/common/hugio"
 	_errors "github.com/pkg/errors"
 	"github.com/spf13/afero"
@@ -172,32 +174,6 @@ func ReplaceExtension(path string, newExt string) string {
 	return f + "." + newExt
 }
 
-// GetFirstThemeDir gets the root directory of the first theme, if there is one.
-// If there is no theme, returns the empty string.
-func (p *PathSpec) GetFirstThemeDir() string {
-	if p.ThemeSet() {
-		return p.AbsPathify(filepath.Join(p.ThemesDir, p.Themes()[0]))
-	}
-	return ""
-}
-
-// GetThemesDir gets the absolute root theme dir path.
-func (p *PathSpec) GetThemesDir() string {
-	if p.ThemeSet() {
-		return p.AbsPathify(p.ThemesDir)
-	}
-	return ""
-}
-
-// GetRelativeThemeDir gets the relative root directory of the current theme, if there is one.
-// If there is no theme, returns the empty string.
-func (p *PathSpec) GetRelativeThemeDir() string {
-	if p.ThemeSet() {
-		return strings.TrimPrefix(filepath.Join(p.ThemesDir, p.Themes()[0]), FilePathSeparator)
-	}
-	return ""
-}
-
 func makePathRelative(inPath string, possibleDirectories ...string) (string, error) {
 
 	for _, currentPath := range possibleDirectories {
@@ -379,6 +355,107 @@ func prettifyPath(in string, b filepathPathBridge) string {
 	return b.Join(b.Dir(in), name, "index"+ext)
 }
 
+type NamedSlice struct {
+	Name  string
+	Slice []string
+}
+
+func (n NamedSlice) String() string {
+	if len(n.Slice) == 0 {
+		return n.Name
+	}
+	return fmt.Sprintf("%s%s{%s}", n.Name, FilePathSeparator, strings.Join(n.Slice, ","))
+}
+
+func ExtractAndGroupRootPaths(paths []string) []NamedSlice {
+	if len(paths) == 0 {
+		return nil
+	}
+
+	pathsCopy := make([]string, len(paths))
+	hadSlashPrefix := strings.HasPrefix(paths[0], FilePathSeparator)
+
+	for i, p := range paths {
+		pathsCopy[i] = strings.Trim(filepath.ToSlash(p), "/")
+	}
+
+	sort.Strings(pathsCopy)
+
+	pathsParts := make([][]string, len(pathsCopy))
+
+	for i, p := range pathsCopy {
+		pathsParts[i] = strings.Split(p, "/")
+	}
+
+	var groups [][]string
+
+	for i, p1 := range pathsParts {
+		c1 := -1
+
+		for j, p2 := range pathsParts {
+			if i == j {
+				continue
+			}
+
+			c2 := -1
+
+			for i, v := range p1 {
+				if i >= len(p2) {
+					break
+				}
+				if v != p2[i] {
+					break
+				}
+
+				c2 = i
+			}
+
+			if c1 == -1 || (c2 != -1 && c2 < c1) {
+				c1 = c2
+			}
+		}
+
+		if c1 != -1 {
+			groups = append(groups, p1[:c1+1])
+		} else {
+			groups = append(groups, p1)
+		}
+	}
+
+	groupsStr := make([]string, len(groups))
+	for i, g := range groups {
+		groupsStr[i] = strings.Join(g, "/")
+	}
+
+	groupsStr = UniqueStringsSorted(groupsStr)
+
+	var result []NamedSlice
+
+	for _, g := range groupsStr {
+		name := filepath.FromSlash(g)
+		if hadSlashPrefix {
+			name = FilePathSeparator + name
+		}
+		ns := NamedSlice{Name: name}
+		for _, p := range pathsCopy {
+			if !strings.HasPrefix(p, g) {
+				continue
+			}
+
+			p = strings.TrimPrefix(p, g)
+			if p != "" {
+				ns.Slice = append(ns.Slice, p)
+			}
+		}
+
+		ns.Slice = UniqueStrings(ExtractRootPaths(ns.Slice))
+
+		result = append(result, ns)
+	}
+
+	return result
+}
+
 // ExtractRootPaths extracts the root paths from the supplied list of paths.
 // The resulting root path will not contain any file separators, but there
 // may be duplicates.
@@ -425,98 +502,21 @@ func FindCWD() (string, error) {
 	return path, nil
 }
 
-// SymbolicWalk is like filepath.Walk, but it supports the root being a
-// symbolic link. It will still not follow symbolic links deeper down in
-// the file structure.
-func SymbolicWalk(fs afero.Fs, root string, walker filepath.WalkFunc) error {
-
-	// Sanity check
-	if root != "" && len(root) < 4 {
-		return errors.New("path is too short")
-	}
-
-	// Handle the root first
-	fileInfo, realPath, err := getRealFileInfo(fs, root)
-
-	if err != nil {
-		return walker(root, nil, err)
-	}
-
-	if !fileInfo.IsDir() {
-		return fmt.Errorf("cannot walk regular file %s", root)
-	}
-
-	if err := walker(realPath, fileInfo, err); err != nil && err != filepath.SkipDir {
-		return err
-	}
-
-	// Some of Hugo's filesystems represents an ordered root folder, i.e. project first, then theme folders.
-	// Make sure that order is preserved. afero.Walk will sort the directories down in the file tree,
-	// but we don't care about that.
-	rootContent, err := readDir(fs, root, false)
-
-	if err != nil {
-		return walker(root, nil, err)
-	}
-
-	for _, fi := range rootContent {
-		if err := afero.Walk(fs, filepath.Join(root, fi.Name()), walker); err != nil {
-			return err
-		}
+// SymbolicWalk is like filepath.Walk, but it follows symbolic links.
+func SymbolicWalk(fs afero.Fs, root string, walker hugofs.WalkFunc) error {
+	if _, isOs := fs.(*afero.OsFs); isOs {
+		// Mainly to track symlinks.
+		fs = hugofs.NewBaseFileDecorator(fs)
 	}
 
-	return nil
+	w := hugofs.NewWalkway(hugofs.WalkwayConfig{
+		Fs:     fs,
+		Root:   root,
+		WalkFn: walker,
+	})
 
-}
-
-func readDir(fs afero.Fs, dirname string, doSort bool) ([]os.FileInfo, error) {
-	f, err := fs.Open(dirname)
-	if err != nil {
-		return nil, err
-	}
-	list, err := f.Readdir(-1)
-	f.Close()
-	if err != nil {
-		return nil, err
-	}
-	if doSort {
-		sort.Slice(list, func(i, j int) bool { return list[i].Name() < list[j].Name() })
-	}
-	return list, nil
-}
-
-func getRealFileInfo(fs afero.Fs, path string) (os.FileInfo, string, error) {
-	fileInfo, err := LstatIfPossible(fs, path)
-	realPath := path
-
-	if err != nil {
-		return nil, "", err
-	}
-
-	if fileInfo.Mode()&os.ModeSymlink == os.ModeSymlink {
-		link, err := filepath.EvalSymlinks(path)
-		if err != nil {
-			return nil, "", _errors.Wrapf(err, "Cannot read symbolic link %q", path)
-		}
-		fileInfo, err = LstatIfPossible(fs, link)
-		if err != nil {
-			return nil, "", _errors.Wrapf(err, "Cannot stat %q", link)
-		}
-		realPath = link
-	}
-	return fileInfo, realPath, nil
-}
-
-// GetRealPath returns the real file path for the given path, whether it is a
-// symlink or not.
-func GetRealPath(fs afero.Fs, path string) (string, error) {
-	_, realPath, err := getRealFileInfo(fs, path)
-
-	if err != nil {
-		return "", err
-	}
+	return w.Walk()
 
-	return realPath, nil
 }
 
 // LstatIfPossible can be used to call Lstat if possible, else Stat.
diff --git a/helpers/path_test.go b/helpers/path_test.go
index 98291936c..e58a045c1 100644
--- a/helpers/path_test.go
+++ b/helpers/path_test.go
@@ -29,8 +29,6 @@ import (
 
 	"github.com/stretchr/testify/require"
 
-	"github.com/stretchr/testify/assert"
-
 	"github.com/gohugoio/hugo/hugofs"
 	"github.com/spf13/afero"
 	"github.com/spf13/viper"
@@ -73,18 +71,9 @@ func TestMakePath(t *testing.T) {
 }
 
 func TestMakePathSanitized(t *testing.T) {
-	v := viper.New()
-	v.Set("contentDir", "content")
-	v.Set("dataDir", "data")
-	v.Set("i18nDir", "i18n")
-	v.Set("layoutDir", "layouts")
-	v.Set("assetDir", "assets")
-	v.Set("resourceDir", "resources")
-	v.Set("publishDir", "public")
-	v.Set("archetypeDir", "archetypes")
+	v := newTestCfg()
 
-	l := langs.NewDefaultLanguage(v)
-	p, _ := NewPathSpec(hugofs.NewMem(v), l)
+	p, _ := NewPathSpec(hugofs.NewMem(v), v)
 
 	tests := []struct {
 		input    string
@@ -166,33 +155,6 @@ func TestGetRelativePath(t *testing.T) {
 	}
 }
 
-func TestGetRealPath(t *testing.T) {
-	if runtime.GOOS == "windows" && os.Getenv("CI") == "" {
-		t.Skip("Skip TestGetRealPath as os.Symlink needs administrator rights on Windows")
-	}
-
-	d1, _ := ioutil.TempDir("", "d1")
-	defer os.Remove(d1)
-	fs := afero.NewOsFs()
-
-	rp1, err := GetRealPath(fs, d1)
-	require.NoError(t, err)
-	assert.Equal(t, d1, rp1)
-
-	sym := filepath.Join(os.TempDir(), "d1sym")
-	err = os.Symlink(d1, sym)
-	require.NoError(t, err)
-	defer os.Remove(sym)
-
-	rp2, err := GetRealPath(fs, sym)
-	require.NoError(t, err)
-
-	// On OS X, the temp folder is itself a symbolic link (to /private...)
-	// This has to do for now.
-	assert.True(t, strings.HasSuffix(rp2, d1))
-
-}
-
 func TestMakePathRelative(t *testing.T) {
 	type test struct {
 		inPath, path1, path2, output string
@@ -659,6 +621,29 @@ func TestPrettifyPath(t *testing.T) {
 
 }
 
+func TestExtractAndGroupRootPaths(t *testing.T) {
+	in := []string{
+		filepath.FromSlash("/a/b/c/d"),
+		filepath.FromSlash("/a/b/c/e"),
+		filepath.FromSlash("/a/b/e/f"),
+		filepath.FromSlash("/a/b"),
+		filepath.FromSlash("/a/b/c/b/g"),
+		filepath.FromSlash("/c/d/e"),
+	}
+
+	inCopy := make([]string, len(in))
+	copy(inCopy, in)
+
+	result := ExtractAndGroupRootPaths(in)
+
+	assert := require.New(t)
+	assert.Equal(filepath.FromSlash("[/a/b/{c,e} /c/d/e]"), fmt.Sprint(result))
+
+	// Make sure the original is preserved
+	assert.Equal(inCopy, in)
+
+}
+
 func TestExtractRootPaths(t *testing.T) {
 	tests := []struct {
 		input    []string
diff --git a/helpers/pathspec_test.go b/helpers/pathspec_test.go
index 00dd9cd7b..1c27f7e11 100644
--- a/helpers/pathspec_test.go
+++ b/helpers/pathspec_test.go
@@ -14,6 +14,7 @@
 package helpers
 
 import (
+	"path/filepath"
 	"testing"
 
 	"github.com/gohugoio/hugo/hugofs"
@@ -36,8 +37,12 @@ func TestNewPathSpecFromConfig(t *testing.T) {
 	v.Set("workingDir", "thework")
 	v.Set("staticDir", "thestatic")
 	v.Set("theme", "thetheme")
+	langs.LoadLanguageSettings(v, nil)
 
-	p, err := NewPathSpec(hugofs.NewMem(v), l)
+	fs := hugofs.NewMem(v)
+	fs.Source.MkdirAll(filepath.FromSlash("thework/thethemes/thetheme"), 0777)
+
+	p, err := NewPathSpec(fs, l)
 
 	require.NoError(t, err)
 	require.True(t, p.CanonifyURLs)
@@ -50,5 +55,5 @@ func TestNewPathSpecFromConfig(t *testing.T) {
 	require.Equal(t, "http://base.com", p.BaseURL.String())
 	require.Equal(t, "thethemes", p.ThemesDir)
 	require.Equal(t, "thework", p.WorkingDir)
-	require.Equal(t, []string{"thetheme"}, p.Themes())
+
 }
diff --git a/helpers/testhelpers_test.go b/helpers/testhelpers_test.go
index c9da4f129..b74dccfc4 100644
--- a/helpers/testhelpers_test.go
+++ b/helpers/testhelpers_test.go
@@ -5,6 +5,7 @@ import (
 
 	"github.com/gohugoio/hugo/hugofs"
 	"github.com/gohugoio/hugo/langs"
+	"github.com/gohugoio/hugo/modules"
 )
 
 func newTestPathSpec(fs *hugofs.Fs, v *viper.Viper) *PathSpec {
@@ -42,6 +43,14 @@ func newTestCfg() *viper.Viper {
 	v.Set("resourceDir", "resources")
 	v.Set("publishDir", "public")
 	v.Set("archetypeDir", "archetypes")
+	langs.LoadLanguageSettings(v, nil)
+	langs.LoadLanguageSettings(v, nil)
+	mod, err := modules.CreateProjectModule(v)
+	if err != nil {
+		panic(err)
+	}
+	v.Set("allModules", modules.Modules{mod})
+
 	return v
 }