set.go

Documentation: github.com/opencontainers/go-digest/digestset

     1  // Copyright 2020, 2020 OCI Contributors
     2  // Copyright 2017 Docker, Inc.
     3  //
     4  // Licensed under the Apache License, Version 2.0 (the "License");
     5  // you may not use this file except in compliance with the License.
     6  // You may obtain a copy of the License at
     7  //
     8  //     https://www.apache.org/licenses/LICENSE-2.0
     9  //
    10  // Unless required by applicable law or agreed to in writing, software
    11  // distributed under the License is distributed on an "AS IS" BASIS,
    12  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  // See the License for the specific language governing permissions and
    14  // limitations under the License.
    15  
    16  package digestset
    17  
    18  import (
    19  	"errors"
    20  	"sort"
    21  	"strings"
    22  	"sync"
    23  
    24  	digest "github.com/opencontainers/go-digest"
    25  )
    26  
    27  var (
    28  	// ErrDigestNotFound is used when a matching digest
    29  	// could not be found in a set.
    30  	ErrDigestNotFound = errors.New("digest not found")
    31  
    32  	// ErrDigestAmbiguous is used when multiple digests
    33  	// are found in a set. None of the matching digests
    34  	// should be considered valid matches.
    35  	ErrDigestAmbiguous = errors.New("ambiguous digest string")
    36  )
    37  
    38  // Set is used to hold a unique set of digests which
    39  // may be easily referenced by easily  referenced by a string
    40  // representation of the digest as well as short representation.
    41  // The uniqueness of the short representation is based on other
    42  // digests in the set. If digests are omitted from this set,
    43  // collisions in a larger set may not be detected, therefore it
    44  // is important to always do short representation lookups on
    45  // the complete set of digests. To mitigate collisions, an
    46  // appropriately long short code should be used.
    47  type Set struct {
    48  	mutex   sync.RWMutex
    49  	entries digestEntries
    50  }
    51  
    52  // NewSet creates an empty set of digests
    53  // which may have digests added.
    54  func NewSet() *Set {
    55  	return &Set{
    56  		entries: digestEntries{},
    57  	}
    58  }
    59  
    60  // checkShortMatch checks whether two digests match as either whole
    61  // values or short values. This function does not test equality,
    62  // rather whether the second value could match against the first
    63  // value.
    64  func checkShortMatch(alg digest.Algorithm, hex, shortAlg, shortHex string) bool {
    65  	if len(hex) == len(shortHex) {
    66  		if hex != shortHex {
    67  			return false
    68  		}
    69  		if len(shortAlg) > 0 && string(alg) != shortAlg {
    70  			return false
    71  		}
    72  	} else if !strings.HasPrefix(hex, shortHex) {
    73  		return false
    74  	} else if len(shortAlg) > 0 && string(alg) != shortAlg {
    75  		return false
    76  	}
    77  	return true
    78  }
    79  
    80  // Lookup looks for a digest matching the given string representation.
    81  // If no digests could be found ErrDigestNotFound will be returned
    82  // with an empty digest value. If multiple matches are found
    83  // ErrDigestAmbiguous will be returned with an empty digest value.
    84  func (dst *Set) Lookup(d string) (digest.Digest, error) {
    85  	dst.mutex.RLock()
    86  	defer dst.mutex.RUnlock()
    87  	if len(dst.entries) == 0 {
    88  		return "", ErrDigestNotFound
    89  	}
    90  	var (
    91  		searchFunc func(int) bool
    92  		alg        digest.Algorithm
    93  		hex        string
    94  	)
    95  	dgst, err := digest.Parse(d)
    96  	if err == digest.ErrDigestInvalidFormat {
    97  		hex = d
    98  		searchFunc = func(i int) bool {
    99  			return dst.entries[i].val >= d
   100  		}
   101  	} else {
   102  		hex = dgst.Hex()
   103  		alg = dgst.Algorithm()
   104  		searchFunc = func(i int) bool {
   105  			if dst.entries[i].val == hex {
   106  				return dst.entries[i].alg >= alg
   107  			}
   108  			return dst.entries[i].val >= hex
   109  		}
   110  	}
   111  	idx := sort.Search(len(dst.entries), searchFunc)
   112  	if idx == len(dst.entries) || !checkShortMatch(dst.entries[idx].alg, dst.entries[idx].val, string(alg), hex) {
   113  		return "", ErrDigestNotFound
   114  	}
   115  	if dst.entries[idx].alg == alg && dst.entries[idx].val == hex {
   116  		return dst.entries[idx].digest, nil
   117  	}
   118  	if idx+1 < len(dst.entries) && checkShortMatch(dst.entries[idx+1].alg, dst.entries[idx+1].val, string(alg), hex) {
   119  		return "", ErrDigestAmbiguous
   120  	}
   121  
   122  	return dst.entries[idx].digest, nil
   123  }
   124  
   125  // Add adds the given digest to the set. An error will be returned
   126  // if the given digest is invalid. If the digest already exists in the
   127  // set, this operation will be a no-op.
   128  func (dst *Set) Add(d digest.Digest) error {
   129  	if err := d.Validate(); err != nil {
   130  		return err
   131  	}
   132  	dst.mutex.Lock()
   133  	defer dst.mutex.Unlock()
   134  	entry := &digestEntry{alg: d.Algorithm(), val: d.Hex(), digest: d}
   135  	searchFunc := func(i int) bool {
   136  		if dst.entries[i].val == entry.val {
   137  			return dst.entries[i].alg >= entry.alg
   138  		}
   139  		return dst.entries[i].val >= entry.val
   140  	}
   141  	idx := sort.Search(len(dst.entries), searchFunc)
   142  	if idx == len(dst.entries) {
   143  		dst.entries = append(dst.entries, entry)
   144  		return nil
   145  	} else if dst.entries[idx].digest == d {
   146  		return nil
   147  	}
   148  
   149  	entries := append(dst.entries, nil)
   150  	copy(entries[idx+1:], entries[idx:len(entries)-1])
   151  	entries[idx] = entry
   152  	dst.entries = entries
   153  	return nil
   154  }
   155  
   156  // Remove removes the given digest from the set. An err will be
   157  // returned if the given digest is invalid. If the digest does
   158  // not exist in the set, this operation will be a no-op.
   159  func (dst *Set) Remove(d digest.Digest) error {
   160  	if err := d.Validate(); err != nil {
   161  		return err
   162  	}
   163  	dst.mutex.Lock()
   164  	defer dst.mutex.Unlock()
   165  	entry := &digestEntry{alg: d.Algorithm(), val: d.Hex(), digest: d}
   166  	searchFunc := func(i int) bool {
   167  		if dst.entries[i].val == entry.val {
   168  			return dst.entries[i].alg >= entry.alg
   169  		}
   170  		return dst.entries[i].val >= entry.val
   171  	}
   172  	idx := sort.Search(len(dst.entries), searchFunc)
   173  	// Not found if idx is after or value at idx is not digest
   174  	if idx == len(dst.entries) || dst.entries[idx].digest != d {
   175  		return nil
   176  	}
   177  
   178  	entries := dst.entries
   179  	copy(entries[idx:], entries[idx+1:])
   180  	entries = entries[:len(entries)-1]
   181  	dst.entries = entries
   182  
   183  	return nil
   184  }
   185  
   186  // All returns all the digests in the set
   187  func (dst *Set) All() []digest.Digest {
   188  	dst.mutex.RLock()
   189  	defer dst.mutex.RUnlock()
   190  	retValues := make([]digest.Digest, len(dst.entries))
   191  	for i := range dst.entries {
   192  		retValues[i] = dst.entries[i].digest
   193  	}
   194  
   195  	return retValues
   196  }
   197  
   198  // ShortCodeTable returns a map of Digest to unique short codes. The
   199  // length represents the minimum value, the maximum length may be the
   200  // entire value of digest if uniqueness cannot be achieved without the
   201  // full value. This function will attempt to make short codes as short
   202  // as possible to be unique.
   203  func ShortCodeTable(dst *Set, length int) map[digest.Digest]string {
   204  	dst.mutex.RLock()
   205  	defer dst.mutex.RUnlock()
   206  	m := make(map[digest.Digest]string, len(dst.entries))
   207  	l := length
   208  	resetIdx := 0
   209  	for i := 0; i < len(dst.entries); i++ {
   210  		var short string
   211  		extended := true
   212  		for extended {
   213  			extended = false
   214  			if len(dst.entries[i].val) <= l {
   215  				short = dst.entries[i].digest.String()
   216  			} else {
   217  				short = dst.entries[i].val[:l]
   218  				for j := i + 1; j < len(dst.entries); j++ {
   219  					if checkShortMatch(dst.entries[j].alg, dst.entries[j].val, "", short) {
   220  						if j > resetIdx {
   221  							resetIdx = j
   222  						}
   223  						extended = true
   224  					} else {
   225  						break
   226  					}
   227  				}
   228  				if extended {
   229  					l++
   230  				}
   231  			}
   232  		}
   233  		m[dst.entries[i].digest] = short
   234  		if i >= resetIdx {
   235  			l = length
   236  		}
   237  	}
   238  	return m
   239  }
   240  
   241  type digestEntry struct {
   242  	alg    digest.Algorithm
   243  	val    string
   244  	digest digest.Digest
   245  }
   246  
   247  type digestEntries []*digestEntry
   248  
   249  func (d digestEntries) Len() int {
   250  	return len(d)
   251  }
   252  
   253  func (d digestEntries) Less(i, j int) bool {
   254  	if d[i].val != d[j].val {
   255  		return d[i].val < d[j].val
   256  	}
   257  	return d[i].alg < d[j].alg
   258  }
   259  
   260  func (d digestEntries) Swap(i, j int) {
   261  	d[i], d[j] = d[j], d[i]
   262  }
   263
View as plain text