digests.go

Documentation: github.com/containerd/continuity

     1  /*
     2     Copyright The containerd Authors.
     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         http://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  
    17  package continuity
    18  
    19  import (
    20  	"fmt"
    21  	"io"
    22  	"sort"
    23  
    24  	"github.com/opencontainers/go-digest"
    25  )
    26  
    27  // Digester produces a digest for a given read stream
    28  type Digester interface {
    29  	Digest(io.Reader) (digest.Digest, error)
    30  }
    31  
    32  // ContentProvider produces a read stream for a given digest
    33  type ContentProvider interface {
    34  	Reader(digest.Digest) (io.ReadCloser, error)
    35  }
    36  
    37  type simpleDigester struct {
    38  	algorithm digest.Algorithm
    39  }
    40  
    41  func (sd simpleDigester) Digest(r io.Reader) (digest.Digest, error) {
    42  	digester := sd.algorithm.Digester()
    43  
    44  	if _, err := io.Copy(digester.Hash(), r); err != nil {
    45  		return "", err
    46  	}
    47  
    48  	return digester.Digest(), nil
    49  }
    50  
    51  // uniqifyDigests sorts and uniqifies the provided digest, ensuring that the
    52  // digests are not repeated and no two digests with the same algorithm have
    53  // different values. Because a stable sort is used, this has the effect of
    54  // "zipping" digest collections from multiple resources.
    55  func uniqifyDigests(digests ...digest.Digest) ([]digest.Digest, error) {
    56  	sort.Stable(digestSlice(digests)) // stable sort is important for the behavior here.
    57  	seen := map[digest.Digest]struct{}{}
    58  	algs := map[digest.Algorithm][]digest.Digest{} // detect different digests.
    59  
    60  	var out []digest.Digest
    61  	// uniqify the digests
    62  	for _, d := range digests {
    63  		if _, ok := seen[d]; ok {
    64  			continue
    65  		}
    66  
    67  		seen[d] = struct{}{}
    68  		algs[d.Algorithm()] = append(algs[d.Algorithm()], d)
    69  
    70  		if len(algs[d.Algorithm()]) > 1 {
    71  			return nil, fmt.Errorf("conflicting digests for %v found", d.Algorithm())
    72  		}
    73  
    74  		out = append(out, d)
    75  	}
    76  
    77  	return out, nil
    78  }
    79  
    80  // digestsMatch compares the two sets of digests to see if they match.
    81  func digestsMatch(as, bs []digest.Digest) bool {
    82  	all := append(as, bs...)
    83  
    84  	uniqified, err := uniqifyDigests(all...)
    85  	if err != nil {
    86  		// the only error uniqifyDigests returns is when the digests disagree.
    87  		return false
    88  	}
    89  
    90  	disjoint := len(as) + len(bs)
    91  	// if these two sets have the same cardinality, we know both sides
    92  	// didn't share any digests.
    93  	return len(uniqified) != disjoint
    94  }
    95  
    96  type digestSlice []digest.Digest
    97  
    98  func (p digestSlice) Len() int           { return len(p) }
    99  func (p digestSlice) Less(i, j int) bool { return p[i] < p[j] }
   100  func (p digestSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
   101
View as plain text