mirror of
https://github.com/gohugoio/hugo.git
synced 2024-12-13 07:45:59 -05:00
241b21b0fd
Primary motivation is documentation, but it will also hopefully simplify the code. Also, * Lower case the default output format names; this is in line with the custom ones (map keys) and how it's treated all the places. This avoids doing `stringds.EqualFold` everywhere. Closes #10896 Closes #10620
631 lines
16 KiB
Go
631 lines
16 KiB
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: IndicesConfig{
|
|
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.
|
|
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 IndicesConfig
|
|
}
|
|
|
|
// 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
|
|
}
|
|
|
|
// IndicesConfig holds a set of index configurations.
|
|
type IndicesConfig []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
|
|
}
|
|
|
|
// 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
|
|
// Counts the number of documents added to each index.
|
|
indexDocCount map[string]int
|
|
|
|
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), indexDocCount: make(map[string]int), 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
|
|
for _, config := range idx.cfg.Indices {
|
|
if config.Weight == 0 {
|
|
// Disabled
|
|
continue
|
|
}
|
|
setm := idx.index[config.Name]
|
|
|
|
for _, doc := range docs {
|
|
var added bool
|
|
var words []Keyword
|
|
words, err = doc.RelatedKeywords(config)
|
|
if err != nil {
|
|
continue
|
|
}
|
|
|
|
for _, keyword := range words {
|
|
added = true
|
|
setm[keyword] = append(setm[keyword], doc)
|
|
}
|
|
|
|
if config.Type == TypeFragments {
|
|
if fp, ok := doc.(FragmentProvider); ok {
|
|
for _, fragment := range fp.Fragments(ctx).Identifiers {
|
|
added = true
|
|
setm[FragmentKeyword(fragment)] = append(setm[FragmentKeyword(fragment)], doc)
|
|
}
|
|
}
|
|
}
|
|
|
|
if added {
|
|
idx.indexDocCount[config.Name]++
|
|
}
|
|
}
|
|
}
|
|
|
|
return err
|
|
}
|
|
|
|
func (idx *InvertedIndex) Finalize(ctx context.Context) error {
|
|
if idx.finalized {
|
|
return nil
|
|
}
|
|
|
|
for _, config := range idx.cfg.Indices {
|
|
if config.CardinalityThreshold == 0 {
|
|
continue
|
|
}
|
|
setm := idx.index[config.Name]
|
|
if idx.indexDocCount[config.Name] == 0 {
|
|
continue
|
|
}
|
|
|
|
// Remove high cardinality terms.
|
|
numDocs := idx.indexDocCount[config.Name]
|
|
for k, v := range setm {
|
|
percentageWithKeyword := int(math.Ceil(float64(len(v)) / float64(numDocs) * 100))
|
|
if percentageWithKeyword > config.CardinalityThreshold {
|
|
delete(setm, k)
|
|
}
|
|
}
|
|
|
|
}
|
|
|
|
idx.finalized = true
|
|
|
|
return nil
|
|
|
|
}
|
|
|
|
// queryElement holds the index name and keywords that can be used to compose a
|
|
// search for related content.
|
|
type queryElement struct {
|
|
Index string
|
|
Keywords []Keyword
|
|
}
|
|
|
|
func newQueryElement(index string, keywords ...Keyword) queryElement {
|
|
return queryElement{Index: index, Keywords: keywords}
|
|
}
|
|
|
|
type ranks []*rank
|
|
|
|
type rank struct {
|
|
Doc Document
|
|
Weight int
|
|
Matches int
|
|
}
|
|
|
|
func (r *rank) addWeight(w int) {
|
|
r.Weight += w
|
|
r.Matches++
|
|
}
|
|
|
|
var rankPool = sync.Pool{
|
|
New: func() interface{} {
|
|
return &rank{}
|
|
},
|
|
}
|
|
|
|
func getRank(doc Document, weight int) *rank {
|
|
r := rankPool.Get().(*rank)
|
|
r.Doc = doc
|
|
r.Weight = weight
|
|
r.Matches = 1
|
|
return r
|
|
}
|
|
|
|
func putRank(r *rank) {
|
|
rankPool.Put(r)
|
|
}
|
|
|
|
func (r ranks) Len() int { return len(r) }
|
|
func (r ranks) Swap(i, j int) { r[i], r[j] = r[j], r[i] }
|
|
func (r ranks) Less(i, j int) bool {
|
|
if r[i].Weight == r[j].Weight {
|
|
if r[i].Doc.PublishDate() == r[j].Doc.PublishDate() {
|
|
return r[i].Doc.Name() < r[j].Doc.Name()
|
|
}
|
|
return r[i].Doc.PublishDate().After(r[j].Doc.PublishDate())
|
|
}
|
|
return r[i].Weight > r[j].Weight
|
|
}
|
|
|
|
// SearchOpts holds the options for a related search.
|
|
type SearchOpts struct {
|
|
// The Document to search for related content for.
|
|
Document Document
|
|
|
|
// The keywords to search for.
|
|
NamedSlices []types.KeyValues
|
|
|
|
// The indices to search in.
|
|
Indices []string
|
|
|
|
// Fragments holds a a list of special keywords that is used
|
|
// for indices configured as type "fragments".
|
|
// This will match the fragment identifiers of the documents.
|
|
Fragments []string
|
|
}
|
|
|
|
// Search finds the documents matching any of the keywords in the given indices
|
|
// against query options in opts.
|
|
// The resulting document set will be sorted according to number of matches
|
|
// and the index weights, and any matches with a rank below the configured
|
|
// threshold (normalize to 0..100) will be removed.
|
|
// If an index name is provided, only that index will be queried.
|
|
func (idx *InvertedIndex) Search(ctx context.Context, opts SearchOpts) ([]Document, error) {
|
|
|
|
var (
|
|
queryElements []queryElement
|
|
configs IndicesConfig
|
|
)
|
|
|
|
if len(opts.Indices) == 0 {
|
|
configs = idx.cfg.Indices
|
|
} else {
|
|
configs = make(IndicesConfig, len(opts.Indices))
|
|
for i, indexName := range opts.Indices {
|
|
cfg, found := idx.getIndexCfg(indexName)
|
|
if !found {
|
|
return nil, fmt.Errorf("index %q not found", indexName)
|
|
}
|
|
configs[i] = cfg
|
|
}
|
|
}
|
|
|
|
for _, cfg := range configs {
|
|
var keywords []Keyword
|
|
if opts.Document != nil {
|
|
k, err := opts.Document.RelatedKeywords(cfg)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
keywords = append(keywords, k...)
|
|
}
|
|
if cfg.Type == TypeFragments {
|
|
for _, fragment := range opts.Fragments {
|
|
keywords = append(keywords, FragmentKeyword(fragment))
|
|
}
|
|
if opts.Document != nil {
|
|
|
|
if fp, ok := opts.Document.(FragmentProvider); ok {
|
|
for _, fragment := range fp.Fragments(ctx).Identifiers {
|
|
keywords = append(keywords, FragmentKeyword(fragment))
|
|
}
|
|
}
|
|
}
|
|
|
|
}
|
|
queryElements = append(queryElements, newQueryElement(cfg.Name, keywords...))
|
|
}
|
|
for _, slice := range opts.NamedSlices {
|
|
var keywords []Keyword
|
|
key := slice.KeyString()
|
|
if key == "" {
|
|
return nil, fmt.Errorf("index %q not valid", slice.Key)
|
|
}
|
|
conf, found := idx.getIndexCfg(key)
|
|
if !found {
|
|
return nil, fmt.Errorf("index %q not found", key)
|
|
}
|
|
|
|
for _, val := range slice.Values {
|
|
k, err := conf.ToKeywords(val)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
keywords = append(keywords, k...)
|
|
}
|
|
queryElements = append(queryElements, newQueryElement(conf.Name, keywords...))
|
|
}
|
|
|
|
if opts.Document != nil {
|
|
return idx.searchDate(ctx, opts.Document, opts.Document.PublishDate(), queryElements...)
|
|
}
|
|
return idx.search(ctx, queryElements...)
|
|
}
|
|
|
|
func (cfg IndexConfig) stringToKeyword(s string) Keyword {
|
|
if cfg.ToLower {
|
|
s = strings.ToLower(s)
|
|
}
|
|
if cfg.Type == TypeFragments {
|
|
return FragmentKeyword(s)
|
|
}
|
|
return StringKeyword(s)
|
|
}
|
|
|
|
// ToKeywords returns a Keyword slice of the given input.
|
|
func (cfg IndexConfig) ToKeywords(v any) ([]Keyword, error) {
|
|
var keywords []Keyword
|
|
|
|
switch vv := v.(type) {
|
|
case string:
|
|
keywords = append(keywords, cfg.stringToKeyword(vv))
|
|
case []string:
|
|
vvv := make([]Keyword, len(vv))
|
|
for i := 0; i < len(vvv); i++ {
|
|
vvv[i] = cfg.stringToKeyword(vv[i])
|
|
}
|
|
keywords = append(keywords, vvv...)
|
|
case []any:
|
|
return cfg.ToKeywords(cast.ToStringSlice(vv))
|
|
case time.Time:
|
|
layout := "2006"
|
|
if cfg.Pattern != "" {
|
|
layout = cfg.Pattern
|
|
}
|
|
keywords = append(keywords, StringKeyword(vv.Format(layout)))
|
|
case nil:
|
|
return keywords, nil
|
|
default:
|
|
return keywords, fmt.Errorf("indexing currently not supported for index %q and type %T", cfg.Name, vv)
|
|
}
|
|
|
|
return keywords, nil
|
|
}
|
|
|
|
func (idx *InvertedIndex) search(ctx context.Context, query ...queryElement) ([]Document, error) {
|
|
return idx.searchDate(ctx, nil, zeroDate, query...)
|
|
}
|
|
|
|
func (idx *InvertedIndex) searchDate(ctx context.Context, self Document, upperDate time.Time, query ...queryElement) ([]Document, error) {
|
|
matchm := make(map[Document]*rank, 200)
|
|
defer func() {
|
|
for _, r := range matchm {
|
|
putRank(r)
|
|
}
|
|
}()
|
|
|
|
applyDateFilter := !idx.cfg.IncludeNewer && !upperDate.IsZero()
|
|
var fragmentsFilter collections.SortedStringSlice
|
|
|
|
for _, el := range query {
|
|
setm, found := idx.index[el.Index]
|
|
if !found {
|
|
return []Document{}, fmt.Errorf("index for %q not found", el.Index)
|
|
}
|
|
|
|
config, found := idx.getIndexCfg(el.Index)
|
|
if !found {
|
|
return []Document{}, fmt.Errorf("index config for %q not found", el.Index)
|
|
}
|
|
|
|
for _, kw := range el.Keywords {
|
|
if docs, found := setm[kw]; found {
|
|
for _, doc := range docs {
|
|
if compare.Eq(doc, self) {
|
|
continue
|
|
}
|
|
|
|
if applyDateFilter {
|
|
// Exclude newer than the limit given
|
|
if doc.PublishDate().After(upperDate) {
|
|
continue
|
|
}
|
|
}
|
|
|
|
if config.Type == TypeFragments && config.ApplyFilter {
|
|
if fkw, ok := kw.(FragmentKeyword); ok {
|
|
fragmentsFilter = append(fragmentsFilter, string(fkw))
|
|
}
|
|
}
|
|
|
|
r, found := matchm[doc]
|
|
if !found {
|
|
r = getRank(doc, config.Weight)
|
|
matchm[doc] = r
|
|
} else {
|
|
r.addWeight(config.Weight)
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if len(matchm) == 0 {
|
|
return []Document{}, nil
|
|
}
|
|
|
|
matches := make(ranks, 0, 100)
|
|
|
|
for _, v := range matchm {
|
|
avgWeight := v.Weight / v.Matches
|
|
weight := norm(avgWeight, idx.minWeight, idx.maxWeight)
|
|
threshold := idx.cfg.Threshold / v.Matches
|
|
|
|
if weight >= threshold {
|
|
matches = append(matches, v)
|
|
}
|
|
}
|
|
|
|
sort.Stable(matches)
|
|
sort.Strings(fragmentsFilter)
|
|
|
|
result := make([]Document, len(matches))
|
|
|
|
for i, m := range matches {
|
|
result[i] = m.Doc
|
|
|
|
if len(fragmentsFilter) > 0 {
|
|
if dp, ok := result[i].(FragmentProvider); ok {
|
|
result[i] = dp.ApplyFilterToHeadings(ctx, func(h *tableofcontents.Heading) bool {
|
|
return fragmentsFilter.Contains(h.ID)
|
|
})
|
|
}
|
|
}
|
|
}
|
|
|
|
return result, nil
|
|
}
|
|
|
|
// normalizes num to a number between 0 and 100.
|
|
func norm(num, min, max int) int {
|
|
if min > max {
|
|
panic("min > max")
|
|
}
|
|
return int(math.Floor((float64(num-min) / float64(max-min) * 100) + 0.5))
|
|
}
|
|
|
|
// DecodeConfig decodes a slice of map into Config.
|
|
func DecodeConfig(m maps.Params) (Config, error) {
|
|
if m == nil {
|
|
return Config{}, errors.New("no related config provided")
|
|
}
|
|
|
|
if len(m) == 0 {
|
|
return Config{}, errors.New("empty related config provided")
|
|
}
|
|
|
|
var c Config
|
|
|
|
if err := mapstructure.WeakDecode(m, &c); err != nil {
|
|
return c, err
|
|
}
|
|
|
|
if c.Threshold < 0 || c.Threshold > 100 {
|
|
return Config{}, errors.New("related threshold must be between 0 and 100")
|
|
}
|
|
|
|
if c.ToLower {
|
|
for i := range c.Indices {
|
|
c.Indices[i].ToLower = true
|
|
}
|
|
}
|
|
for i := range c.Indices {
|
|
icfg := c.Indices[i]
|
|
if icfg.Type == "" {
|
|
c.Indices[i].Type = TypeBasic
|
|
}
|
|
if !validTypes[c.Indices[i].Type] {
|
|
return c, fmt.Errorf("invalid index type %q. Must be one of %v", c.Indices[i].Type, xmaps.Keys(validTypes))
|
|
}
|
|
if icfg.CardinalityThreshold < 0 || icfg.CardinalityThreshold > 100 {
|
|
return Config{}, errors.New("cardinalityThreshold threshold must be between 0 and 100")
|
|
}
|
|
}
|
|
|
|
return c, nil
|
|
}
|
|
|
|
// StringKeyword is a string search keyword.
|
|
type StringKeyword string
|
|
|
|
func (s StringKeyword) String() string {
|
|
return string(s)
|
|
}
|
|
|
|
// FragmentKeyword represents a document fragment.
|
|
type FragmentKeyword string
|
|
|
|
func (f FragmentKeyword) String() string {
|
|
return string(f)
|
|
}
|
|
|
|
// Keyword is the interface a keyword in the search index must implement.
|
|
type Keyword interface {
|
|
String() string
|
|
}
|
|
|
|
// StringsToKeywords converts the given slice of strings to a slice of Keyword.
|
|
func (cfg IndexConfig) StringsToKeywords(s ...string) []Keyword {
|
|
kw := make([]Keyword, len(s))
|
|
|
|
for i := 0; i < len(s); i++ {
|
|
kw[i] = cfg.stringToKeyword(s[i])
|
|
}
|
|
|
|
return kw
|
|
}
|