path: root/related/inverted_index.go

// Copyright 2019 The Hugo Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Package related holds code to help finding related content.
package related

import (
	"context"
	"errors"
	"fmt"
	"math"
	"sort"
	"strings"
	"sync"
	"time"

	xmaps "golang.org/x/exp/maps"

	"github.com/gohugoio/hugo/common/collections"
	"github.com/gohugoio/hugo/common/maps"
	"github.com/gohugoio/hugo/compare"
	"github.com/gohugoio/hugo/markup/tableofcontents"
	"github.com/spf13/cast"

	"github.com/gohugoio/hugo/common/types"
	"github.com/mitchellh/mapstructure"
)

const (
	TypeBasic     = "basic"
	TypeFragments = "fragments"
)

var validTypes = map[string]bool{
	TypeBasic:     true,
	TypeFragments: true,
}

var (
	_        Keyword = (*StringKeyword)(nil)
	zeroDate         = time.Time{}

	// DefaultConfig is the default related config.
	DefaultConfig = Config{
		Threshold: 80,
		Indices: IndexConfigs{
			IndexConfig{Name: "keywords", Weight: 100, Type: TypeBasic},
			IndexConfig{Name: "date", Weight: 10, Type: TypeBasic},
		},
	}
)

/*
Config is the top level configuration element used to configure how to retrieve
related content in Hugo.

An example site config.toml:

	[related]
	threshold = 1
	[[related.indices]]
	name = "keywords"
	weight = 200
	[[related.indices]]
	name  = "tags"
	weight = 100
	[[related.indices]]
	name  = "date"
	weight = 1
	pattern = "2006"
*/
type Config struct {
	// Only include matches >= threshold, a normalized rank between 0 and 100.
	Threshold int

	// To get stable "See also" sections we, by default, exclude newer related pages.
	IncludeNewer bool

	// Will lower case all string values and queries to the indices.
	// May get better results, but at a slight performance cost.
	ToLower bool

	Indices IndexConfigs
}

// Add adds a given index.
func (c *Config) Add(index IndexConfig) {
	if c.ToLower {
		index.ToLower = true
	}
	c.Indices = append(c.Indices, index)
}

func (c *Config) HasType(s string) bool {
	for _, i := range c.Indices {
		if i.Type == s {
			return true
		}
	}
	return false
}

// IndexConfigs holds a set of index configurations.
type IndexConfigs []IndexConfig

// IndexConfig configures an index.
type IndexConfig struct {
	// The index name. This directly maps to a field or Param name.
	Name string

	// The index type.
	Type string

	// Enable to apply a type specific filter to the results.
	// This is currently only used for the "fragments" type.
	ApplyFilter bool

	// Contextual pattern used to convert the Param value into a string.
	// Currently only used for dates. Can be used to, say, bump posts in the same
	// time frame when searching for related documents.
	// For dates it follows Go's time.Format patterns, i.e.
	// "2006" for YYYY and "200601" for YYYYMM.
	Pattern string

	// This field's weight when doing multi-index searches. Higher is "better".
	Weight int

	// A percentage (0-100) used to remove common keywords from the index.
	// As an example, setting this to 50 will remove all keywords that are
	// used in more than 50% of the documents in the index.
	CardinalityThreshold int

	// Will lower case all string values in and queries tothis index.
	// May get better accurate results, but at a slight performance cost.
	ToLower bool

	// Counts the number of documents in the index.
	numDocs int
}

func (cfg *IndexConfig) incrNumDocs() {
	cfg.numDocs++
}

// Document is the interface an indexable document in Hugo must fulfill.
type Document interface {
	// RelatedKeywords returns a list of keywords for the given index config.
	RelatedKeywords(cfg IndexConfig) ([]Keyword, error)

	// When this document was or will be published.
	PublishDate() time.Time

	// Name is used as an tiebreaker if both Weight and PublishDate are
	// the same.
	Name() string
}

// FragmentProvider is an optional interface that can be implemented by a Document.
type FragmentProvider interface {
	Fragments(context.Context) *tableofcontents.Fragments

	// For internal use.
	ApplyFilterToHeadings(context.Context, func(*tableofcontents.Heading) bool) Document
}

// InvertedIndex holds an inverted index, also sometimes named posting list, which
// lists, for every possible search term, the documents that contain that term.
type InvertedIndex struct {
	cfg   Config
	index map[string]map[Keyword][]Document

	minWeight int
	maxWeight int

	// No modifications after this is set.
	finalized bool
}

func (idx *InvertedIndex) getIndexCfg(name string) (IndexConfig, bool) {
	for _, conf := range idx.cfg.Indices {
		if conf.Name == name {
			return conf, true
		}
	}

	return IndexConfig{}, false
}

// NewInvertedIndex creates a new InvertedIndex.
// Documents to index must be added in Add.
func NewInvertedIndex(cfg Config) *InvertedIndex {
	idx := &InvertedIndex{index: make(map[string]map[Keyword][]Document), cfg: cfg}
	for _, conf := range cfg.Indices {
		idx.index[conf.Name] = make(map[Keyword][]Document)
		if conf.Weight < idx.minWeight {
			// By default, the weight scale starts at 0, but we allow
			// negative weights.
			idx.minWeight = conf.Weight
		}
		if conf.Weight > idx.maxWeight {
			idx.maxWeight = conf.Weight
		}
	}
	return idx
}

// Add documents to the inverted index.
// The value must support == and !=.
func (idx *InvertedIndex) Add(ctx context.Context, docs ...Document) error {
	if idx.finalized {
		panic("index is finalized")
	}
	var err error