From 0df55a731aa3330f82d22b010a7a2a4d66521972 Mon Sep 17 00:00:00 2001 From: Stefan Majewsky Date: Sun, 29 Apr 2018 21:19:14 +0200 Subject: initial support for large objects This has gone through a lot of iterations on my branch, and I'm quite happy with the parts of the API that exist now. Test coverage can still be better, and will get better in the following commits. The API is not yet finished: I want to add Options arguments to Object.Upload(), Object.Copy(), Object.Move() and Object.Delete() that specify how each of these operations affect existing segments (and, later, also existing symlinks). For Upload(), uploading in segments shall become as easy as flipping a single switch. --- .gitignore | 4 + Makefile | 16 +- errors.go | 11 + headers.go | 21 + largeobject.go | 689 +++++++++++++++++++++ largeobject_test.go | 64 ++ object.go | 22 +- tests/largeobject_test.go | 362 +++++++++++ tests/object_test.go | 4 +- tests/shared_test.go | 13 + util/gocovcat.go | 87 +++ vendor/github.com/jpillora/longestcommon/README.md | 45 ++ vendor/github.com/jpillora/longestcommon/lc.go | 82 +++ .../github.com/jpillora/longestcommon/lc_test.go | 111 ++++ vendor/pins/github.com_jpillora_longestcommon | 1 + vendor/skip/github.com_gophercloud_gophercloud | 0 16 files changed, 1522 insertions(+), 10 deletions(-) create mode 100644 largeobject.go create mode 100644 largeobject_test.go create mode 100644 tests/largeobject_test.go create mode 100755 util/gocovcat.go create mode 100644 vendor/github.com/jpillora/longestcommon/README.md create mode 100644 vendor/github.com/jpillora/longestcommon/lc.go create mode 100644 vendor/github.com/jpillora/longestcommon/lc_test.go create mode 100644 vendor/pins/github.com_jpillora_longestcommon create mode 100644 vendor/skip/github.com_gophercloud_gophercloud diff --git a/.gitignore b/.gitignore index 60fe31d..3f22794 100644 --- a/.gitignore +++ b/.gitignore @@ -1,3 +1,7 @@ # test artifacts cover.out +cover.out.* cover.html + +# vendoring +.golangvend-cache/ diff --git a/Makefile b/Makefile index fa49b20..c6b78c5 100644 --- a/Makefile +++ b/Makefile @@ -23,11 +23,23 @@ static-tests: FORCE @echo '>> govet...' @go vet ./... -cover.out: FORCE +PKG = github.com/majewsky/schwift +TESTPKGS = $(PKG) $(PKG)/tests # space-separated list of packages containing tests +COVERPKGS = $(PKG),$(PKG)/gopherschwift # comma-separated list of packages for which to measure coverage + +cover.out.%: FORCE @echo '>> go test...' - @go test -covermode count -coverpkg github.com/majewsky/schwift/... -coverprofile $@ github.com/majewsky/schwift/tests + go test -covermode count -coverpkg $(COVERPKGS) -coverprofile $@ $(subst _,/,$*) +cover.out: $(addprefix cover.out.,$(subst /,_,$(TESTPKGS))) + util/gocovcat.go $^ > $@ cover.html: cover.out @echo '>> rendering cover.html...' @go tool cover -html=$< -o $@ +################################################################################ + +# vendoring by https://github.com/holocm/golangvend +vendor: FORCE + @golangvend + .PHONY: FORCE diff --git a/errors.go b/errors.go index 5784126..2826df7 100644 --- a/errors.go +++ b/errors.go @@ -43,6 +43,17 @@ var ( //objects as arguments, if (some of) the provided objects are located in a //different account. ErrAccountMismatch = errors.New("some of the given objects are not in this account") + //ErrContainerMismatch is returned by operations on a container that accept + //objects as arguments, if (some of) the provided objects are located in a + //different container. + ErrContainerMismatch = errors.New("some of the given objects are not in this container") + //ErrNotLarge is returned by Object.AsLargeObject() if the object exists, but + //is not a large object that is composed out of segments. + ErrNotLarge = errors.New("not a large object") + //ErrSegmentInvalid is returned by LargeObject.AddSegment() if the segment + //provided is malformed or uses features not supported by the LargeObject's + //strategy. See documentation for LargeObject.AddSegment() for details. + ErrSegmentInvalid = errors.New("segment invalid or incompatible with large object strategy") ) //UnexpectedStatusCodeError is generated when a request to Swift does not yield diff --git a/headers.go b/headers.go index 88c1a63..c1119ae 100644 --- a/headers.go +++ b/headers.go @@ -101,3 +101,24 @@ func headersFromHTTP(src http.Header) Headers { } return h } + +//////////////////////////////////////////////////////////////////////////////// +// specialized accessors on Headers subtypes that are not autogenerated + +//IsDynamicLargeObject returns true if this set of headers belongs to a Dynamic +//Large Object (DLO). +func (h ObjectHeaders) IsDynamicLargeObject() bool { + return h.Headers.Get("X-Object-Manifest") != "" +} + +//IsStaticLargeObject returns true if this set of headers belongs to a Static +//Large Object (SLO). +func (h ObjectHeaders) IsStaticLargeObject() bool { + return h.Headers.Get("X-Static-Large-Object") == "True" +} + +//IsLargeObject returns true if this set of headers belongs to a large object +//(either an SLO or a DLO). +func (h ObjectHeaders) IsLargeObject() bool { + return h.IsDynamicLargeObject() || h.IsStaticLargeObject() +} diff --git a/largeobject.go b/largeobject.go new file mode 100644 index 0000000..493671d --- /dev/null +++ b/largeobject.go @@ -0,0 +1,689 @@ +/****************************************************************************** +* +* Copyright 2018 Stefan Majewsky +* +* 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 schwift + +import ( + "bufio" + "bytes" + "crypto/md5" + "encoding/base64" + "encoding/hex" + "encoding/json" + "errors" + "fmt" + "io" + "math" + "net/http" + "net/url" + "path" + "regexp" + "strconv" + "strings" + + "github.com/jpillora/longestcommon" +) + +//SegmentInfo describes a segment of a large object. +// +//For .RangeLength == 0, the segment consists of all the bytes in the backing +//object, after skipping the first .RangeOffset bytes. The default +//(.RangeOffset == 0) includes the entire contents of the backing object. +// +//For .RangeLength > 0, the segment consists of that many bytes from the +//backing object, again after skipping the first .RangeOffset bytes. +// +//However, for .RangeOffset < 0, the segment consists of .RangeLength many bytes +//from the *end* of the backing object. (The concrete value for .RangeOffset is +//disregarded.) .RangeLength must be non-zero in this case. +// +//Sorry that specifying a range is that involved. I was just following orders ^W +//RFC 7233, section 3.1 here. +type SegmentInfo struct { + Object *Object + SizeBytes uint64 + Etag string + RangeLength uint64 + RangeOffset int64 + //Static Large Objects support data segments that are not backed by actual + //objects. For those kinds of segments, only the Data attribute is set and + //all other attributes are set to their default values (esp. .Object == nil). + // + //Data segments can only be used for small chunks of data because the SLO + //manifest (the list of all SegmentInfo encoded as JSON) is severely limited + //in size (usually to 8 MiB). + Data []byte +} + +type sloSegmentInfo struct { + Path string `json:"path,omitempty"` + SizeBytes uint64 `json:"size_bytes,omitempty"` + Etag string `json:"etag,omitempty"` + Range string `json:"range,omitempty"` + DataBase64 string `json:"data,omitempty"` +} + +//LargeObjectOpenMode is a set of flags that can be given to +//LargeObject.Open(). +type LargeObjectOpenMode int + +const ( + //OpenTruncate indicates that all existing segments in this object shall be + //deleted by Open(). + OpenTruncate LargeObjectOpenMode = 0 + //OpenAppend indicates that Open() shall set up the writer to append new + //content to the existing segments. + OpenAppend LargeObjectOpenMode = 1 << 0 + //OpenKeepSegments indicates that, when truncating an existing object, the + //segments shall not be deleted even though they are no longer referenced by + //this object. This flag has no effect when combined with OpenAppend. + OpenKeepSegments LargeObjectOpenMode = 1 << 1 +) + +//LargeObjectStrategy is an enum of segmenting strategies supported by Swift. +type LargeObjectStrategy int + +const ( + //StaticLargeObject is the default LargeObjectStrategy used by Schwift. + StaticLargeObject LargeObjectStrategy = iota + //DynamicLargeObject is an older LargeObjectStrategy that is not recommended + //for new applications because of eventual consistency problems and missing + //support for several newer features (e.g. data segments, range specifications). + DynamicLargeObject +) + +//////////////////////////////////////////////////////////////////////////////// + +//LargeObject is a wrapper for type Object that performs operations specific to +//large objects. +// +//This type should only be constructed through the Object.AsLargeObject() +//method. If the object does not exist yet, the SegmentContainerName and +//SegmentPrefix must be specified before this object can be written to, and the +//Strategy can be adjusted in the unlikely case that an SLO is not desired. +type LargeObject struct { + Object *Object + SegmentContainer *Container + SegmentPrefix string + Strategy LargeObjectStrategy + //This is private so that we can later optimize this to load the segments + //only on demand. + segments []SegmentInfo +} + +//AsLargeObject prepares a LargeObject instance. If the given object exists, +//but is not a large object, ErrNotLarge will be returned. If the given object +//does not yet exist, the SegmentContainer and SegmentPrefix attributes need to +//be filled in before the LargeObject can be used. +func (o *Object) AsLargeObject() (*LargeObject, error) { + exists, err := o.Exists() + if err != nil { + return nil, err + } + if !exists { + return &LargeObject{Object: o, Strategy: StaticLargeObject}, nil + } + + h := o.headers + if h.IsDynamicLargeObject() { + return o.asDLO(h.Get("X-Object-Manifest")) + } + if h.IsStaticLargeObject() { + return o.asSLO() + } + return nil, ErrNotLarge +} + +func (o *Object) asDLO(manifestStr string) (*LargeObject, error) { + manifest := strings.SplitN(manifestStr, "/", 2) + if len(manifest) < 2 { + return nil, ErrNotLarge + } + + lo := &LargeObject{ + Object: o, + SegmentContainer: o.c.a.Container(manifest[0]), + SegmentPrefix: manifest[1], + Strategy: DynamicLargeObject, + } + + iter := lo.SegmentContainer.Objects() + iter.Prefix = lo.SegmentPrefix + segmentInfos, err := iter.CollectDetailed() + if err != nil { + return nil, err + } + lo.segments = make([]SegmentInfo, 0, len(segmentInfos)) + for _, info := range segmentInfos { + lo.segments = append(lo.segments, SegmentInfo{ + Object: info.Object, + SizeBytes: info.SizeBytes, + Etag: info.Etag, + }) + } + + return lo, nil +} + +func (o *Object) asSLO() (*LargeObject, error) { + opts := RequestOptions{ + Values: make(url.Values), + } + opts.Values.Set("multipart-manifest", "get") + opts.Values.Set("format", "raw") + buf, err := o.Download(&opts).AsByteSlice() + if err != nil { + return nil, err + } + + var data []sloSegmentInfo + err = json.Unmarshal(buf, &data) + if err != nil { + return nil, errors.New("invalid SLO manifest: " + err.Error()) + } + + lo := &LargeObject{ + Object: o, + Strategy: StaticLargeObject, + } + if len(data) == 0 { + return lo, nil + } + + //read the segments first, then deduce the SegmentContainer/SegmentPrefix from these + lo.segments = make([]SegmentInfo, 0, len(data)) + for _, info := range data { + //option 1: data segment + if info.DataBase64 != "" { + data, err := base64.StdEncoding.DecodeString(info.DataBase64) + if err != nil { + return nil, errors.New("invalid SLO data segment: " + err.Error()) + } + lo.segments = append(lo.segments, SegmentInfo{Data: data}) + continue + } + + //option 2: segment backed by object + pathElements := strings.SplitN(strings.TrimPrefix(info.Path, "/"), "/", 2) + if len(pathElements) != 2 { + return nil, errors.New("invalid SLO segment: malformed path: " + info.Path) + } + s := SegmentInfo{ + Object: o.c.a.Container(pathElements[0]).Object(pathElements[1]), + SizeBytes: info.SizeBytes, + Etag: info.Etag, + } + if info.Range != "" { + var ok bool + s.RangeOffset, s.RangeLength, ok = parseHTTPRange(info.Range) + if !ok { + return nil, errors.New("invalid SLO segment: malformed range: " + info.Range) + } + } + lo.segments = append(lo.segments, s) + } + + //choose the SegmentContainer by majority vote (in the spirit of "be liberal + //in what you accept") + containerNames := make(map[string]uint) + for _, s := range lo.segments { + if s.Object == nil { //can happen for data segments + continue + } + containerNames[s.Object.c.Name()]++ + } + maxName := "" + maxVotes := uint(0) + for name, votes := range containerNames { + if votes > maxVotes { + maxName = name + maxVotes = votes + } + } + lo.SegmentContainer = lo.Object.c.a.Container(maxName) + + //choose the SegmentPrefix as the longest common prefix of all segments in + //the chosen SegmentContainer... + names := make([]string, 0, len(lo.segments)) + for _, s := range lo.segments { + if s.Object == nil { //can happen for data segments + continue + } + name := s.Object.c.Name() + if name == maxName { + names = append(names, s.Object.Name()) + } + } + lo.SegmentPrefix = longestcommon.Prefix(names) + + //..BUT if the prefix is a path with slashes, do not consider the part after + //the last slash; e.g. if we have segments "foo/bar/0001" and "foo/bar/0002", + //the longest common prefix is "foo/bar/000", but we actually want "foo/bar/" + if strings.Contains(lo.SegmentPrefix, "/") { + lo.SegmentPrefix = path.Dir(lo.SegmentPrefix) + "/" + } + + return lo, nil +} + +func parseHTTPRange(str string) (offsetVal int64, lengthVal uint64, ok bool) { + fields := strings.SplitN(str, "-", 2) + if len(fields) != 2 { + return 0, 0, false + } + + if fields[0] == "" { + //case 1: "-" + if fields[1] == "" { + return 0, 0, true + } + + //case 2: "-N" + numBytes, err := strconv.ParseUint(fields[1], 10, 64) + if err != nil { + return 0, 0, false + } + return -1, numBytes, true + } + + firstByte, err := strconv.ParseUint(fields[0], 10, 63) //not 64; needs to be unsigned, but also fit into int64 + if err != nil { + return 0, 0, false + } + if fields[1] == "" { + //case 3: "N-" + return int64(firstByte), 0, true + } + //case 4: "M-N" + lastByte, err := strconv.ParseUint(fields[1], 10, 64) + if err != nil || lastByte < firstByte { + return 0, 0, false + } + return int64(firstByte), lastByte - firstByte + 1, true +} + +//Open returns an io.WriteCloser that can be used to replace or extend the +//contents of this large object. +// +//This call returns ErrNoContainerName if o.SegmentContainer is not set, or +//ErrAccountMismatch if it is not in the same account as the large object. +//For existing objects, SegmentContainer and SegmentPrefix will be filled by +//Object.AsLargeObject(). For new objects, they need to be filled by the +//caller. +// +//WARNING: Every call to Write() on the returned writer will create a new +//segment. To ensure a uniform segment size, wrap the writer returned from this +//call in a bufio.Writer, for example by using the schwift.SetSegmentSize() +//convenience function: +// +// dlo, err := account.Container("public").Object("archive27.zip").AsLargeObject() +// dlo.SegmentContainer = account.Container("segments") +// dlo.SegmentPrefix = "archive27/" +// w, err := dlo.Open(schwift.OpenTruncate) +// w, err = schwift.SetSegmentSize(w, 1<<30) //segment size 1<<30 byte = 1 GiB +// _, err = bw.Write(archiveContents) +// err = w.Close() +// +func (lo *LargeObject) Open(mode LargeObjectOpenMode) (io.WriteCloser, error) { + if lo.SegmentContainer == nil { + return nil, ErrNoContainerName + } + if !lo.SegmentContainer.a.isEqualTo(lo.Object.c.a) { + return nil, ErrAccountMismatch + } + + if mode&OpenAppend == 0 { + if mode&OpenKeepSegments == 0 { + segmentObjects := make([]*Object, len(lo.segments)) + for idx, segment := range lo.segments { + segmentObjects[idx] = segment.Object + } + _, _, err := lo.Object.c.a.BulkDelete(segmentObjects, nil, nil) + if err != nil { + return nil, err + } + } + lo.segments = nil + } + + return largeObjectWriter{lo}, nil +} + +//Segments returns a list of all segments for this object, in order. +func (lo *LargeObject) Segments() ([]SegmentInfo, error) { + //NOTE: This method has an error return value because we might later switch + //to loading segments lazily inside this method. + return lo.segments, nil +} + +//NextSegmentObject suggests where to upload the next segment. +// +//WARNING: This is a low-level function. Most callers will want to use the +//io.WriteCloser provided by Open(). You will only need to upload segments +//manually when you want to control the segments' metadata. +// +//If the name of the current final segment ends with a counter, that counter is +//incremented, otherwise a counter is appended to its name. When looking for a +//counter in an existing segment name, the regex /[0-9]+$/ is used. For example, +//given: +// +// segments := lo.Segments() +// lastSegmentName := segments[len(segments)-1].Name() +// nextSegmentName := lo.NextSegmentObject().Name() +// +//If lastSegmentName is "segments/archive/segment0001", then nextSegmentName is +//"segments/archive/segment0002". If lastSegmentName is +//"segments/archive/first", then nextSegmentName is +//"segments/archive/first0000000000000001". +// +//However, the last segment's name will only be considered if it lies within +//lo.SegmentContainer below lo.SegmentPrefix. If that is not the case, the name +//of the last segment that does will be used instead. +// +//If there are no segments yet, or if all segments are located outside the +//lo.SegmentContainer and lo.SegmentPrefix, the first segment name is chosen as +//lo.SegmentPrefix + "0000000000000001". +func (lo *LargeObject) NextSegmentObject() *Object { + //find the name of the last-most segment that is within the designated + //segment container and prefix + var prevSegmentName string + for _, s := range lo.segments { + o := s.Object + if o == nil { //can happen for data segments + continue + } + if lo.SegmentContainer.isEqualTo(o.c) && strings.HasPrefix(o.Name(), lo.SegmentPrefix) { + prevSegmentName = s.Object.Name() + //keep going, we want to find the last such segment + } + } + + //choose the next segment name based on the previous one + var segmentName string + if prevSegmentName == "" { + segmentName = lo.SegmentPrefix + initialIndex + } else { + segmentName = nextSegmentName(prevSegmentName) + } + + return lo.SegmentContainer.Object(segmentName) +} + +var splitSegmentIndexRx = regexp.MustCompile(`^(.*?)([0-9]+$)`) +var initialIndex = "0000000000000001" + +//Given the object name of a previous large object segment, compute a suitable +//name for the next segment. See doc for LargeObject.NextSegmentObject() +//for how this works. +func nextSegmentName(segmentName string) string { + match := splitSegmentIndexRx.FindStringSubmatch(segmentName) + if match == nil { + return segmentName + initialIndex + } + base, idxStr := match[1], match[2] + + idx, err := strconv.ParseUint(idxStr, 10, 64) + if err != nil || idx == math.MaxUint64 { //overflow + //start from one again, but separate with a dash to ensure that the new + //index can be parsed properly in the next call to this function + return segmentName + "-" + initialIndex + } + + //print next index with same number of digits as previous index, + //e.g. "00001" -> "00002" (except if overflow, e.g. "9999" -> "10000") + formatStr := fmt.Sprintf("%%0%dd", len(idxStr)) + return base + fmt.Sprintf(formatStr, idx+1) +} + +//AddSegment appends a segment to this object. The segment must already have +//been uploaded. +// +//WARNING: This is a low-level function. Most callers will want to use the +//io.WriteCloser provided by Open(). You will only need to add segments +//manually when you want to control the segments' metadata, or when using +//advanced features such as range-limited segments or data segments. +// +//This method returns ErrAccountMismatch if the segment is not located in a +//container in the same account. +// +//For dynamic large objects, this method returns ErrContainerMismatch if the +//segment is not located in the correct container below the correct prefix. +// +//This method returns ErrSegmentInvalid if: +// +//- a range is specified in the SegmentInfo, but it is invalid or the +//LargeObject is a dynamic large object (DLOs do not support ranges), or +// +//- the SegmentInfo's Data attribute is set and any other attribute is also +//set (segments cannot be backed by objects and be data segments at the same +//time), or +// +//- the SegmentInfo's Data attribute is set, but the LargeObject is a dynamic +//large objects (DLOs do not support data segments). +func (lo *LargeObject) AddSegment(segment SegmentInfo) error { + if len(segment.Data) == 0 { + //validate segments backed by objects + o := segment.Object + if o == nil { + //required attributes + return ErrSegmentInvalid + } + if !o.c.a.isEqualTo(lo.SegmentContainer.a) { + return ErrAccountMismatch + } + + switch lo.Strategy { + case DynamicLargeObject: + if segment.RangeLength != 0 || segment.RangeOffset != 0 { + //not supported for DLO + return ErrSegmentInvalid + } + + if !o.c.isEqualTo(lo.SegmentContainer) { + return ErrContainerMismatch + } + if !strings.HasPrefix(o.name, lo.SegmentPrefix) { + return ErrContainerMismatch + } + + case StaticLargeObject: + if segment.RangeLength == 0 && segment.RangeOffset < 0 { + //malformed range + return ErrSegmentInvalid + } + } + } else { + //validate plain-data segments + if lo.Strategy != StaticLargeObject { + //not supported for DLO + return ErrSegmentInvalid + } + if segment.Object != nil || segment.SizeBytes != 0 || segment.Etag != "" || segment.RangeLength != 0 || segment.RangeOffset != 0 { + //all other attributes must be unset + return ErrSegmentInvalid + } + } + + lo.segments = append(lo.segments, segment) + return nil +} + +//WriteManifest creates this large object by writing a manifest to its +//location using a PUT request. +// +//For dynamic large objects, this method does not generate a PUT request +//if the object already exists and has the correct manifest (i.e. +//SegmentContainer and SegmentPrefix have not been changed). +func (lo *LargeObject) WriteManifest(opts *RequestOptions) error { + switch lo.Strategy { + case StaticLargeObject: + return lo.writeSLOManifest(opts) + case DynamicLargeObject: + return lo.writeDLOManifest(opts) + default: + panic("no such strategy") + } +} + +func (lo *LargeObject) writeDLOManifest(opts *RequestOptions) error { + manifest := lo.SegmentContainer.Name() + "/" + lo.SegmentPrefix + + //check if the manifest is already set correctly + headers, err := lo.Object.Headers() + if err != nil && !Is(err, http.StatusNotFound) { + return err + } + if headers.Get("X-Object-Manifest") == manifest { + return nil + } + + //write manifest; make sure that this is a DLO + opts = cloneRequestOptions(opts, nil) + opts.Headers.Set("X-Object-Manifest", manifest) + return lo.Object.Upload(nil, opts) +} + +func (lo *LargeObject) writeSLOManifest(opts *RequestOptions) error { + sloSegments := make([]sloSegmentInfo, len(lo.segments)) + for idx, s := range lo.segments { + if len(s.Data) > 0 { + sloSegments[idx] = sloSegmentInfo{ + DataBase64: base64.StdEncoding.EncodeToString(s.Data), + } + } else { + si := sloSegmentInfo{ + Path: "/" + s.Object.FullName(), + SizeBytes: s.SizeBytes, + Etag: s.Etag, + } + + if s.RangeOffset < 0 { + si.Range = "-" + strconv.FormatUint(s.RangeLength, 10) + } else { + firstByteStr := strconv.FormatUint(uint64(s.RangeOffset), 10) + lastByteStr := strconv.FormatUint(uint64(s.RangeOffset)+s.RangeLength-1, 10) + si.Range = firstByteStr + "-" + lastByteStr + } + + sloSegments[idx] = si + } + } + + manifest, err := json.Marshal(sloSegments) + if err != nil { + //failing json.Marshal() on such a trivial data structure is alarming + panic(err.Error()) + } + + opts = cloneRequestOptions(opts, nil) + opts.Headers.Del("X-Object-Manifest") //ensure sanity :) + opts.Values.Set("multipart-manifest", "put") + return lo.Object.Upload(bytes.NewReader(manifest), opts) +} + +//////////////////////////////////////////////////////////////////////////////// + +type largeObjectWriter struct { + lo *LargeObject +} + +//Write implements the io.WriteCloser interface. +func (w largeObjectWriter) Write(buf []byte) (int, error) { + segment := w.lo.NextSegmentObject() + //TODO: split write into multiple segments if len(buf) > max object size + err := segment.Upload(bytes.NewReader(buf), nil) + if err != nil { + return 0, err + } + + sum := md5.Sum(buf) + return len(buf), w.lo.AddSegment(SegmentInfo{ + Object: segment, + SizeBytes: uint64(len(buf)), + Etag: hex.EncodeToString(sum[:]), + }) +} + +//Close implements the io.WriteCloser interface. +func (w largeObjectWriter) Close() error { + return w.lo.WriteManifest(nil) +} + +//////////////////////////////////////////////////////////////////////////////// + +type largeObjectBufferedWriter struct { + bw *bufio.Writer + w io.WriteCloser +} + +//SetSegmentSize creates a bufio.Writer around an io.WriteCloser and returns +//an interface to it that works like the original io.WriteCloser. +// +//This is intended to be used when writing segments into a large object. +//The writer returned by LargeObject.Open() does not ensure a uniform segment +//size by default, so one would have to wrap it in a bufio.Writer like so: +// +// dlo, err := account.Container("public").Object("archive27.zip").AsLargeObject() +// dlo.SegmentContainer = account.Container("segments") +// dlo.SegmentPrefix = "archive27/" +// +// w, err := largeObject.Open(schwift.OpenTruncate) +// bw, err := bufio.NewWriterSize(w, 1<<30) //segment size 1<<30 byte = 1 GiB +// _, err = bw.Write(archiveContents) +// err = bw.Flush() +// err = w.Close() +// +//This function reduces the boilerplate to: +// +// w, err := largeObject.Open(schwift.OpenTruncate) +// w, err = schwift.SetSegmentSize(w, 1<<30) //segment size 1<<30 byte = 1 GiB +// _, err = w.Write(archiveContents) +// err = w.Close() +// +//Another advantage of this function is that the returned writer implements +//io.WriteCloser, which bufio.Writer does not. So you can pass it into +//consuming functions that use io.WriteCloser to close the object once they're +//done writing to it, and it will be ensured that the buffer is flushed before +//closing the underlying writer. +func SetSegmentSize(w io.WriteCloser, segmentSizeBytes int) io.WriteCloser { + switch w := w.(type) { + case *largeObjectBufferedWriter: + //never chain multiple largeObjectBufferedWriter together + w.bw.Flush() //ensure that previous calls to `w.Write()` are durable + return SetSegmentSize(w.w, segmentSizeBytes) + default: + return &largeObjectBufferedWriter{ + bw: bufio.NewWriterSize(w, segmentSizeBytes), + w: w, + } + } +} + +//Write implements the io.WriteCloser interface. +func (bw *largeObjectBufferedWriter) Write(buf []byte) (int, error) { + return bw.bw.Write(buf) +} + +//Close implements the io.WriteCloser interface. +func (bw *largeObjectBufferedWriter) Close() error { + err := bw.bw.Flush() + if err != nil { + return err + } + return bw.w.Close() +} diff --git a/largeobject_test.go b/largeobject_test.go new file mode 100644 index 0000000..fe781ab --- /dev/null +++ b/largeobject_test.go @@ -0,0 +1,64 @@ +/****************************************************************************** +* +* Copyright 2018 Stefan Majewsky +* +* 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 schwift + +import "testing" + +func TestParseHTTPRange(t *testing.T) { + testCases := []struct { + input string + ok bool + offset int64 + length uint64 + }{ + //all the testcases from RFC 7233, section 3.1 + {"0-499", true, 0, 500}, + {"500-999", true, 500, 500}, + {"-500", true, -1, 500}, + {"9500-", true, 9500, 0}, + {"0-0", true, 0, 1}, + {"-1", true, -1, 1}, + //and then some more + {"0-", true, 0, 0}, + {"-", true, 0, 0}, + //some error cases for 100% coverage + {"no dash", false, 0, 0}, + {"what-the-heck", false, 0, 0}, + {"-X", false, 0, 0}, + {"X-X", false, 0, 0}, + {"X-", false, 0, 0}, + {"999-500", false, 0, 0}, + } + + for _, tc := range testCases { + o, l, ok := parseHTTPRange(tc.input) + + if tc.ok && !ok { + t.Errorf("expected %q to parse, but did not", tc.input) + } + if !tc.ok && ok { + t.Errorf("expected %q to fail, but parsed into (%d, %d)", + tc.input, o, l) + } + if o != tc.offset || l != tc.length { + t.Errorf("expected %q to parse as (%d, %d), but (%d, %d)", + tc.input, tc.offset, tc.length, o, l) + } + } +} diff --git a/object.go b/object.go index 8ef314a..4ff1f4f 100644 --- a/object.go +++ b/object.go @@ -167,15 +167,23 @@ func (o *Object) Update(headers ObjectHeaders, opts *RequestOptions) error { func (o *Object) Upload(content io.Reader, opts *RequestOptions) error { opts = cloneRequestOptions(opts, nil) hdr := ObjectHeaders{opts.Headers} - tryComputeContentLength(content, hdr) - tryComputeEtag(content, hdr) - //could not compute Etag in advance -> need to check on the fly + //do not attempt to add the Etag header when we're writing a large object + //manifest; the header refers to the content, but we would be computing the + //manifest's hash instead + isManifestUpload := opts.Values.Get("multipart-manifest") == "put" || hdr.IsDynamicLargeObject() + var hasher hash.Hash - if !hdr.Etag().Exists() { - hasher = md5.New() - if content != nil { - content = io.TeeReader(content, hasher) + tryComputeContentLength(content, hdr) + if !isManifestUpload { + tryComputeEtag(content, hdr) + + //could not compute Etag in advance -> need to check on the fly + if !hdr.Etag().Exists() { + hasher = md5.New() + if content != nil { + content = io.TeeReader(content, hasher) + } } } diff --git a/tests/largeobject_test.go b/tests/largeobject_test.go new file mode 100644 index 0000000..8e57e0d --- /dev/null +++ b/tests/largeobject_test.go @@ -0,0 +1,362 @@ +/****************************************************************************** +* +* Copyright 2018 Stefan Majewsky +* +* 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 tests + +import ( + "bytes" + "fmt" + "strings" + "testing" + + "github.com/majewsky/schwift" +) + +func foreachLargeObjectStrategy(action func(schwift.LargeObjectStrategy, string)) { + action(schwift.StaticLargeObject, "slo") + action(schwift.DynamicLargeObject, "dlo") +} + +func TestLargeObjectsBasic(t *testing.T) { + testWithContainer(t, func(c *schwift.Container) { + foreachLargeObjectStrategy(func(strategy schwift.LargeObjectStrategy, strategyStr string) { + + obj := c.Object(strategyStr + "-largeobject") + lo, err := obj.AsLargeObject() + expectSuccess(t, err) + + //Open fails when SegmentContainer is not set + _, err = lo.Open(schwift.OpenTruncate) + expectError(t, err, schwift.ErrNoContainerName.Error()) + + lo.SegmentContainer = c + lo.SegmentPrefix = strategyStr + "-segments/" + lo.Strategy = strategy + + segment1 := getRandomSegmentContent(128) + segment2 := getRandomSegmentContent(128) + segment3 := getRandomSegmentContent(128) + segment4 := getRandomSegmentContent(128) + + //basic write example + w, err := lo.Open(schwift.OpenTruncate) + expectSuccess(t, err) + if w == nil { + t.FailNow() + } + _, err = w.Write([]byte(segment1)) + expectSuccess(t, err) + _, err = w.Write([]byte(segment2)) + expectSuccess(t, err) + expectSuccess(t, w.Close()) + + expectObjectContent(t, obj, []byte(segment1+segment2)) + expectLargeObject(t, obj, []schwift.SegmentInfo{ + { + Object: c.Object(strategyStr + "-segments/0000000000000001"), + SizeBytes: 128, + Etag: etagOfString(segment1), + }, + { + Object: c.Object(strategyStr + "-segments/0000000000000002"), + SizeBytes: 128, + Etag: etagOfString(segment2), + }, + }) + + //basic append example + lo, err = obj.AsLargeObject() + expectSuccess(t, err) + expectLargeObjectSetup(t, lo, strategy, + fmt.Sprintf("%s/%s-segments/", c.Name(), strategyStr)) + w, err = lo.Open(schwift.OpenAppend) + expectSuccess(t, err) + if w == nil { + t.FailNow() + } + _, err = w.Write([]byte(segment3)) + expectSuccess(t, err) + _, err = w.Write([]byte(segment4)) + expectSuccess(t, err) + expectSuccess(t, w.Close()) + + expectObjectContent(t, obj, []byte(segment1+segment2+segment3+segment4)) + expectLargeObject(t, obj, []schwift.SegmentInfo{ + { + Object: c.Object(strategyStr + "-segments/0000000000000001"), + SizeBytes: 128, + Etag: etagOfString(segment1), + }, + { + Object: c.Object(strategyStr + "-segments/0000000000000002"), + SizeBytes: 128, + Etag: etagOfString(segment2), + }, + { + Object: c.Object(strategyStr + "-segments/0000000000000003"), + SizeBytes: 128, + Etag: etagOfString(segment3), + }, + { + Object: c.Object(strategyStr + "-segments/0000000000000004"), + SizeBytes: 128, + Etag: etagOfString(segment4), + }, + }) + + //basic truncate example + lo, err = obj.AsLargeObject() + expectSuccess(t, err) + expectLargeObjectSetup(t, lo, strategy, + fmt.Sprintf("%s/%s-segments/", c.Name(), strategyStr)) + w, err = lo.Open(schwift.OpenTruncate) + expectSuccess(t, err) + if w == nil { + t.FailNow() + } + + //verify that segments were deleted + iter := c.Objects() + iter.Prefix = lo.SegmentPrefix + names, err := iter.Collect() + expectSuccess(t, err) + expectObjectNames(t, names) + + _, err = w.Write([]byte(segment3)) + expectSuccess(t, err) + _, err = w.Write([]byte(segment4)) + expectSuccess(t, err) + expectSuccess(t, w.Close()) + + expectObjectContent(t, obj, []byte(segment3+segment4)) + expectLargeObject(t, obj, []schwift.SegmentInfo{ + { + Object: c.Object(strategyStr + "-segments/0000000000000001"), + SizeBytes: 128, + Etag: etagOfString(segment3), + }, + { + Object: c.Object(strategyStr + "-segments/0000000000000002"), + SizeBytes: 128, + Etag: etagOfString(segment4), + }, + }) + + }) + }) +} + +func TestOpenRegularObjectAsLargeObject(t *testing.T) { + testWithContainer(t, func(c *schwift.Container) { + o := c.Object("foo") + expectSuccess(t, o.Upload(bytes.NewReader(objectExampleContent), nil)) + _, err := o.AsLargeObject() + expectError(t, err, schwift.ErrNotLarge.Error()) + }) +} + +func TestSLOWithDataSegment(t *testing.T) { + testWithContainer(t, func(c *schwift.Container) { + o := c.Object("foo") + lo, err := o.AsLargeObject() + expectSuccess(t, err) + lo.SegmentContainer = c + lo.SegmentPrefix = "segments/" + lo.Strategy = schwift.StaticLargeObject + + segment1 := getRandomSegmentContent(128) + segment2 := getRandomSegmentContent(128) + w, err := lo.Open(schwift.OpenTruncate) + expectSuccess(t, err) + if w == nil { + t.FailNow() + } + _, err = w.Write([]byte(segment1)) + expectSuccess(t, err) + + dataSegment := schwift.SegmentInfo{Data: []byte("---")} + err = lo.AddSegment(dataSegment) + expectSuccess(t, err) + + _, err = w.Write([]byte(segment2)) + expectSuccess(t, err) + expectSuccess(t, w.Close()) + + expectObjectContent(t, o, []byte(segment1+string(dataSegment.Data)+segment2)) + expectLargeObject(t, o, []schwift.SegmentInfo{ + { + Object: c.Object("segments/0000000000000001"), + SizeBytes: 128, + Etag: etagOfString(segment1), + }, + dataSegment, + { + Object: c.Object("segments/0000000000000002"), + SizeBytes: 128, + Etag: etagOfString(segment2), + }, + }) + }) +} + +func TestSLOWithRangeSegments(t *testing.T) { + testWithContainer(t, func(c *schwift.Container) { + segmentStr := "XX" + segmentObj := c.Object("segment") + expectSuccess(t, segmentObj.Upload(bytes.NewReader([]byte(segmentStr)), nil)) + + o := c.Object("largeobject") + lo, err := o.AsLargeObject() + expectSuccess(t, err) + lo.SegmentContainer = c + lo.SegmentPrefix = "segments/" + lo.Strategy = schwift.StaticLargeObject + + //the large object is composed out of three ranges such that the "X" are precisely cut out of segmentStr + expectSuccess(t, lo.AddSegment(schwift.SegmentInfo{ + Object: segmentObj, + RangeLength: 5, + })) + expectSuccess(t, lo.AddSegment(schwift.SegmentInfo{ + Object: segmentObj, + RangeOffset: 6, + RangeLength: 5, + })) + expectSuccess(t, lo.AddSegment(schwift.SegmentInfo{ + Object: segmentObj, + RangeOffset: -1, + RangeLength: 5, + })) + expectSuccess(t, lo.WriteManifest(nil)) + + expectObjectContent(t, o, []byte( + strings.Replace(segmentStr, "X", "", -1), + )) + expectLargeObject(t, o, []schwift.SegmentInfo{ + { + Object: segmentObj, + Etag: etagOfString(segmentStr), + SizeBytes: uint64(len(segmentStr)), + RangeLength: 5, + }, + { + Object: segmentObj, + Etag: etagOfString(segmentStr), + SizeBytes: uint64(len(segmentStr)), + RangeOffset: 6, + RangeLength: 5, + }, + { + Object: segmentObj, + Etag: etagOfString(segmentStr), + SizeBytes: uint64(len(segmentStr)), + RangeOffset: -1, + RangeLength: 5, + }, + }) + }) +} + +func TestSLOGuessSegmentPrefix(t *testing.T) { + testWithContainer(t, func(c *schwift.Container) { + obj := c.Object("largeobject") + + //setup phase: create an SLO + lo, err := obj.AsLargeObject() + expectSuccess(t, err) + lo.SegmentContainer = c + lo.SegmentPrefix = "foo/bar/baz/" + w, err := lo.Open(schwift.OpenTruncate) + expectSuccess(t, err) + + segment1 := getRandomSegmentContent(128) + segment2 := getRandomSegmentContent(128) + _, err = w.Write([]byte(segment1)) + expectSuccess(t, err) + _, err = w.Write([]byte(segment2)) + expectSuccess(t, err) + expectSuccess(t, w.Close()) + + //now create a fresh SLO and check if it infers the correct SegmentPrefix + lo, err = obj.AsLargeObject() + expectSuccess(t, err) + expectString(t, lo.SegmentContainer.Name(), c.Name()) + expectString(t, lo.SegmentPrefix, "foo/bar/baz/") + }) +} + +func expectLargeObject(t *testing.T, obj *schwift.Object, expected []schwift.SegmentInfo) { + t.Helper() + expectObjectExistence(t, obj, true) + lo, err := obj.AsLargeObject() + expectSuccess(t, err) + if lo == nil { + t.FailNow() + } + + actual, err := lo.Segments() + expectSuccess(t, err) + if len(actual) != len(expected) { + t.Errorf("expected %s to have %d segments, got %d segments", + obj.FullName(), len(expected), len(actual)) + return + } + + for idx, as := range actual { + es := expected[idx] + if len(es.Data) > 0 { + //expecting data segment + if string(es.Data) != string(as.Data) { + t.Errorf("expected segments[%d].Data == %q, got %q", + idx, string(es.Data), string(as.Data)) + } + } else { + //expecting segment backed by object + if as.Object.FullName() != es.Object.FullName() { + t.Errorf("expected segments[%d].Object.FullName() == %q, got %q", + idx, es.Object.FullName(), as.Object.FullName()) + } + if es.SizeBytes != 0 && as.SizeBytes != es.SizeBytes { + t.Errorf("expected segments[%d].SizeBytes == %d, got %d", + idx, es.SizeBytes, as.SizeBytes) + } + if es.Etag != "" && as.Etag != es.Etag { + t.Errorf("expected segments[%d].Etag == %q, got %q", + idx, es.Etag, as.Etag) + } + } + } +} + +func expectLargeObjectSetup(t *testing.T, lo *schwift.LargeObject, strategy schwift.LargeObjectStrategy, segmentFullPrefix string) { + if strategy != lo.Strategy { + t.Errorf("expected %s to use LargeObjectStrategy %d, got %d", + lo.Object.FullName(), strategy, lo.Strategy) + } + + if lo.SegmentContainer == nil { + t.Errorf("expected %s to use segment container+prefix %q, got no container", + lo.Object.FullName(), segmentFullPrefix) + } else { + fullPrefix := lo.SegmentContainer.Name() + "/" + lo.SegmentPrefix + if fullPrefix != segmentFullPrefix { + t.Errorf("expected %s to use segment container+prefix %q, got %q", + lo.Object.FullName(), segmentFullPrefix, fullPrefix) + } + } +} diff --git a/tests/object_test.go b/tests/object_test.go index 1bbf953..39fdba2 100644 --- a/tests/object_test.go +++ b/tests/object_test.go @@ -225,5 +225,7 @@ func expectObjectContent(t *testing.T, obj *schwift.Object, expected []byte) { obj.Invalidate() hdr, err := obj.Headers() expectSuccess(t, err) - expectString(t, hdr.Etag().Get(), etagOf(expected)) + if !hdr.IsLargeObject() { + expectString(t, hdr.Etag().Get(), etagOf(expected)) + } } diff --git a/tests/shared_test.go b/tests/shared_test.go index c35951f..7867d70 100644 --- a/tests/shared_test.go +++ b/tests/shared_test.go @@ -114,6 +114,10 @@ func etagOf(buf []byte) string { return hex.EncodeToString(hash[:]) } +func etagOfString(buf string) string { + return etagOf([]byte(buf)) +} + func getRandomName() string { var buf [16]byte _, err := rand.Read(buf[:]) @@ -123,6 +127,15 @@ func getRandomName() string { return hex.EncodeToString(buf[:]) } +func getRandomSegmentContent(length int) string { + buf := make([]byte, length/2) + _, err := rand.Read(buf) + if err != nil { + panic(err.Error()) + } + return hex.EncodeToString(buf) +} + //////////////////////////////////////////////////////////////////////////////// func expectBool(t *testing.T, actual, expected bool) { diff --git a/util/gocovcat.go b/util/gocovcat.go new file mode 100755 index 0000000..bb03f87 --- /dev/null +++ b/util/gocovcat.go @@ -0,0 +1,87 @@ +///usr/bin/env go run "$0" "$@"; exit $? + +// Copyright 2017 Luke Shumaker +// +// This program is free software: you can redistribute it and/or modify +// it under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// This program is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this program. If not, see . + +// Command gocovcat combines multiple go cover runs, and prints the +// result on stdout. +package main + +import ( + "bufio" + "fmt" + "os" + "sort" + "strconv" + "strings" +) + +func handleErr(err error) { + if err != nil { + fmt.Fprintf(os.Stderr, "%v\n", err) + os.Exit(1) + } +} + +func main() { + modeBool := false + blocks := map[string]int{} + for _, filename := range os.Args[1:] { + file, err := os.Open(filename) + handleErr(err) + buf := bufio.NewScanner(file) + for buf.Scan() { + line := buf.Text() + + if strings.HasPrefix(line, "mode: ") { + m := strings.TrimPrefix(line, "mode: ") + switch m { + case "set": + modeBool = true + case "count", "atomic": + // do nothing + default: + fmt.Fprintf(os.Stderr, "Unrecognized mode: %s\n", m) + os.Exit(1) + } + } else { + sp := strings.LastIndexByte(line, ' ') + block := line[:sp] + cntStr := line[sp+1:] + cnt, err := strconv.Atoi(cntStr) + handleErr(err) + blocks[block] += cnt + } + } + handleErr(buf.Err()) + } + keys := make([]string, 0, len(blocks)) + for key := range blocks { + keys = append(keys, key) + } + sort.Strings(keys) + modeStr := "count" + if modeBool { + modeStr = "set" + } + fmt.Printf("mode: %s\n", modeStr) + for _, block := range keys { + cnt := blocks[block] + if modeBool && cnt > 1 { + cnt = 1 + } + fmt.Printf("%s %d\n", block, cnt) + } +} diff --git a/vendor/github.com/jpillora/longestcommon/README.md b/vendor/github.com/jpillora/longestcommon/README.md new file mode 100644 index 0000000..f32d865 --- /dev/null +++ b/vendor/github.com/jpillora/longestcommon/README.md @@ -0,0 +1,45 @@ +# longestcommon + +Find the longest common prefix/suffix across of list of strings in Go (Golang). Runs in `O(n)`. + +[![GoDoc](https://godoc.org/github.com/jpillora/longestcommon?status.svg)](https://godoc.org/github.com/jpillora/longestcommon) [![Circle CI](https://circleci.com/gh/jpillora/longestcommon.svg?style=shield)](https://circleci.com/gh/jpillora/longestcommon) + +### Install + +``` +$ go get -v github.com/jpillora/longestcommon +``` + +### Usage + +``` go +longestcommon.Prefix([]string{"flower","flow","fleet"}) //"fl" +longestcommon.Suffix([]string{"flower","power","lower"}) //"ower" +``` + +### TODO + +* Include [Longest Common Subsequence](https://github.com/jpillora/lcs) with its TODOs completed + +#### MIT License + +Copyright © 2015 Jaime Pillora <dev@jpillora.com> + +Permission is hereby granted, free of charge, to any person obtaining +a copy of this software and associated documentation files (the +'Software'), to deal in the Software without restriction, including +without limitation the rights to use, copy, modify, merge, publish, +distribute, sublicense, and/or sell copies of the Software, and to +permit persons to whom the Software is furnished to do so, subject to +the following conditions: + +The above copyright notice and this permission notice shall be +included in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. diff --git a/vendor/github.com/jpillora/longestcommon/lc.go b/vendor/github.com/jpillora/longestcommon/lc.go new file mode 100644 index 0000000..788a7a6 --- /dev/null +++ b/vendor/github.com/jpillora/longestcommon/lc.go @@ -0,0 +1,82 @@ +package longestcommon + +import "strings" + +//TrimPrefix removes the longest common prefix from all provided strings +func TrimPrefix(strs []string) { + p := Prefix(strs) + if p == "" { + return + } + for i, s := range strs { + strs[i] = strings.TrimPrefix(s, p) + } +} + +//TrimSuffix removes the longest common suffix from all provided strings +func TrimSuffix(strs []string) { + p := Suffix(strs) + if p == "" { + return + } + for i, s := range strs { + strs[i] = strings.TrimSuffix(s, p) + } +} + +//Prefix returns the longest common prefix of the provided strings +func Prefix(strs []string) string { + return longestCommonXfix(strs, true) +} + +//Suffix returns the longest common suffix of the provided strings +func Suffix(strs []string) string { + return longestCommonXfix(strs, false) +} + +func longestCommonXfix(strs []string, pre bool) string { + //short-circuit empty list + if len(strs) == 0 { + return "" + } + xfix := strs[0] + //short-circuit single-element list + if len(strs) == 1 { + return xfix + } + //compare first to rest + for _, str := range strs[1:] { + xfixl := len(xfix) + strl := len(str) + //short-circuit empty strings + if xfixl == 0 || strl == 0 { + return "" + } + //maximum possible length + maxl := xfixl + if strl < maxl { + maxl = strl + } + //compare letters + if pre { + //prefix, iterate left to right + for i := 0; i < maxl; i++ { + if xfix[i] != str[i] { + xfix = xfix[:i] + break + } + } + } else { + //suffix, iternate right to left + for i := 0; i < maxl; i++ { + xi := xfixl - i - 1 + si := strl - i - 1 + if xfix[xi] != str[si] { + xfix = xfix[xi+1:] + break + } + } + } + } + return xfix +} diff --git a/vendor/github.com/jpillora/longestcommon/lc_test.go b/vendor/github.com/jpillora/longestcommon/lc_test.go new file mode 100644 index 0000000..136e3ff --- /dev/null +++ b/vendor/github.com/jpillora/longestcommon/lc_test.go @@ -0,0 +1,111 @@ +package longestcommon + +import ( + "strings" + "testing" +) + +func doTest(t *testing.T, lines, pre, suf string) { + strs := []string{} + if lines != "" { + strs = strings.Split(lines, "\n") + } + p := Prefix(strs) + if p != pre { + t.Fatalf("fail: expected prefix '%s', got '%s'", pre, p) + } + s := Suffix(strs) + if s != suf { + t.Fatalf("fail: expected suffix '%s', got '%s'", suf, s) + } +} + +func TestXFix1(t *testing.T) { + doTest(t, ``, "", "") +} + +func TestXFix2(t *testing.T) { + doTest(t, `single`, "single", "single") +} + +func TestXFix3(t *testing.T) { + doTest(t, "single\ndouble", "", "le") +} + +func TestXFix4(t *testing.T) { + doTest(t, "flower\nflow\nfleet", "fl", "") +} + +func TestXFix5(t *testing.T) { + doTest(t, `My Awesome Album - 01.mp3 +My Awesome Album - 11.mp3 +My Awesome Album - 03.mp3 +My Awesome Album - 04.mp3 +My Awesome Album - 05.mp3 +My Awesome Album - 06.mp3 +My Awesome Album - 07.mp3 +My Awesome Album - 08.mp3 +My Awesome Album - 09.mp3 +My Awesome Album - 10.mp3 +My Awesome Album - 11.mp3 +My Awesome Album - 12.mp3 +My Awesome Album - 13.mp3 +My Awesome Album - 14.mp3 +My Awesome Album - 15.mp3 +My Awesome Album - 16.mp3 +My Awesome Album - 17.mp3 +My Awesome Album - 18.mp3 +My Awesome Album - 19.mp3 +My Awesome Album - 20.mp3 +My Awesome Album - 21.mp3 +My Awesome Album - 22.mp3 +My Awesome Album - 23.mp3 +My Awesome Album - 24.mp3 +My Awesome Album - 25.mp3 +My Awesome Album - 26.mp3 +My Awesome Album - 27.mp3 +My Awesome Album - 28.mp3 +My Awesome Album - 29.mp3 +My Awesome Album - 30.mp3 +My Awesome Album - 31.mp3 +My Awesome Album - 32.mp3 +My Awesome Album - 33.mp3 +My Awesome Album - 34.mp3 +My Awesome Album - 35.mp3 +My Awesome Album - 36.mp3 +My Awesome Album - 37.mp3 +My Awesome Album - 38.mp3 +My Awesome Album - 39.mp3`, "My Awesome Album - ", ".mp3") +} + +func TestTrimPrefix1(t *testing.T) { + strs := []string{"flower", "flow", "fleet"} + TrimPrefix(strs) + if strs[0] != "ower" { + t.Fatalf("fail: expected result string to be 'ower', got '%s'", strs[0]) + } +} + +func TestTrimPrefix2(t *testing.T) { + strs := []string{"flower", "tree"} + TrimPrefix(strs) //no common prefix + if strs[0] != "flower" { + t.Fatalf("fail: expected result string to be 'flower', got '%s'", strs[0]) + } +} + +func TestTrimSuffix1(t *testing.T) { + strs := []string{"flower", "power"} + TrimSuffix(strs) + if strs[0] != "fl" { + t.Fatalf("fail: expected result string to be 'fl', got '%s'", strs[0]) + } +} + +func TestTrimSuffix2(t *testing.T) { + strs := []string{"flower", "tree"} + TrimSuffix(strs) //no common suffix + if strs[0] != "flower" { + t.Fatalf("fail: expected result string to be 'flower', got '%s'", strs[0]) + } +} diff --git a/vendor/pins/github.com_jpillora_longestcommon b/vendor/pins/github.com_jpillora_longestcommon new file mode 100644 index 0000000..28c3fec --- /dev/null +++ b/vendor/pins/github.com_jpillora_longestcommon @@ -0,0 +1 @@ +adb9d91ee629dd8304c9f9d7c91977b9d7e61a35 diff --git a/vendor/skip/github.com_gophercloud_gophercloud b/vendor/skip/github.com_gophercloud_gophercloud new file mode 100644 index 0000000..e69de29 -- cgit v1.2.3