diff options
Diffstat (limited to 'reachability')
| -rw-r--r-- | reachability/domain.go | 11 | ||||
| -rw-r--r-- | reachability/errors.go | 37 | ||||
| -rw-r--r-- | reachability/helpers.go | 64 | ||||
| -rw-r--r-- | reachability/integration_test.go (renamed from reachability/reachability_integration_test.go) | 0 | ||||
| -rw-r--r-- | reachability/peel.go | 35 | ||||
| -rw-r--r-- | reachability/reachability.go | 315 | ||||
| -rw-r--r-- | reachability/unit_test.go (renamed from reachability/reachability_unit_test.go) | 0 | ||||
| -rw-r--r-- | reachability/walk.go | 195 |
8 files changed, 344 insertions, 313 deletions
diff --git a/reachability/domain.go b/reachability/domain.go new file mode 100644 index 00000000..9fcf721e --- /dev/null +++ b/reachability/domain.go @@ -0,0 +1,11 @@ +package reachability + +// Domain specifies which graph edges are traversed. +type Domain uint8 + +const ( + // DomainCommits traverses commit-parent edges and annotated-tag target edges. + DomainCommits Domain = iota + // DomainObjects traverses full commit/tree/blob objects. + DomainObjects +) diff --git a/reachability/errors.go b/reachability/errors.go new file mode 100644 index 00000000..e52bf0a4 --- /dev/null +++ b/reachability/errors.go @@ -0,0 +1,37 @@ +package reachability + +import ( + "fmt" + + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objecttype" +) + +// ErrObjectMissing indicates that a referenced object is absent from the store. +type ErrObjectMissing struct { + OID objectid.ObjectID +} + +func (e *ErrObjectMissing) Error() string { + return fmt.Sprintf("reachability: missing object %s", e.OID) +} + +// ErrObjectType indicates that a referenced object has a different type than +// what traversal expected on that edge. +type ErrObjectType struct { + OID objectid.ObjectID + Got objecttype.Type + Want objecttype.Type +} + +func (e *ErrObjectType) Error() string { + gotName, gotOK := objecttype.Name(e.Got) + if !gotOK { + gotName = fmt.Sprintf("type(%d)", e.Got) + } + wantName, wantOK := objecttype.Name(e.Want) + if !wantOK { + wantName = fmt.Sprintf("type(%d)", e.Want) + } + return fmt.Sprintf("reachability: object %s has type %s, want %s", e.OID, gotName, wantName) +} diff --git a/reachability/helpers.go b/reachability/helpers.go new file mode 100644 index 00000000..1368a3f1 --- /dev/null +++ b/reachability/helpers.go @@ -0,0 +1,64 @@ +package reachability + +import ( + "errors" + "fmt" + + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objectstore" + "codeberg.org/lindenii/furgit/objecttype" +) + +func validateDomain(domain Domain) error { + switch domain { + case DomainCommits, DomainObjects: + return nil + default: + return fmt.Errorf("reachability: invalid domain %d", domain) + } +} + +func containsOID(set map[objectid.ObjectID]struct{}, id objectid.ObjectID) bool { + if len(set) == 0 { + return false + } + _, ok := set[id] + return ok +} + +// The following helpers exist because we don't have unified error handling across the entire project. +// This will be fixed later. + +func (walk *Walk) readHeaderType(id objectid.ObjectID) (objecttype.Type, error) { + return walk.reachability.readHeaderType(id) +} + +func (r *Reachability) readHeaderType(id objectid.ObjectID) (objecttype.Type, error) { + ty, _, err := r.store.ReadHeader(id) + if err != nil { + if errors.Is(err, objectstore.ErrObjectNotFound) { + return objecttype.TypeInvalid, &ErrObjectMissing{OID: id} + } + return objecttype.TypeInvalid, err + } + return ty, nil +} + +func (walk *Walk) readBytesContent(id objectid.ObjectID) ([]byte, error) { + content, err := walk.reachability.readBytesContent(id) + if err != nil { + return nil, err + } + return content, nil +} + +func (r *Reachability) readBytesContent(id objectid.ObjectID) ([]byte, error) { + _, content, err := r.store.ReadBytesContent(id) + if err != nil { + if errors.Is(err, objectstore.ErrObjectNotFound) { + return nil, &ErrObjectMissing{OID: id} + } + return nil, err + } + return content, nil +} diff --git a/reachability/reachability_integration_test.go b/reachability/integration_test.go index 10668006..10668006 100644 --- a/reachability/reachability_integration_test.go +++ b/reachability/integration_test.go diff --git a/reachability/peel.go b/reachability/peel.go new file mode 100644 index 00000000..9df9bb4d --- /dev/null +++ b/reachability/peel.go @@ -0,0 +1,35 @@ +package reachability + +import ( + "codeberg.org/lindenii/furgit/object" + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objecttype" +) + +func (r *Reachability) peelRootToDomain(id objectid.ObjectID, domain Domain) (objectid.ObjectID, error) { + if err := validateDomain(domain); err != nil { + return objectid.ObjectID{}, err + } + for { + ty, err := r.readHeaderType(id) + if err != nil { + return objectid.ObjectID{}, err + } + if ty != objecttype.TypeTag { + if domain == DomainCommits && ty != objecttype.TypeCommit { + return objectid.ObjectID{}, &ErrObjectType{OID: id, Got: ty, Want: objecttype.TypeCommit} + } + return id, nil + } + + content, err := r.readBytesContent(id) + if err != nil { + return objectid.ObjectID{}, err + } + tag, err := object.ParseTag(content, id.Algorithm()) + if err != nil { + return objectid.ObjectID{}, err + } + id = tag.Target + } +} diff --git a/reachability/reachability.go b/reachability/reachability.go index 5ab41944..0bec055f 100644 --- a/reachability/reachability.go +++ b/reachability/reachability.go @@ -1,36 +1,20 @@ package reachability import ( - "errors" - "fmt" - "iter" - - "codeberg.org/lindenii/furgit/object" "codeberg.org/lindenii/furgit/objectid" "codeberg.org/lindenii/furgit/objectstore" - "codeberg.org/lindenii/furgit/objecttype" -) - -// Domain specifies which graph edges are traversed. -type Domain uint8 - -const ( - // DomainCommits traverses commit-parent edges and annotated-tag target edges. - DomainCommits Domain = iota - // DomainObjects traverses full commit/tree/blob objects. - DomainObjects ) // Reachability provides graph traversal over objects in one object store. // // It is not safe for concurrent use. type Reachability struct { - Store objectstore.Store + store objectstore.Store } // New builds a Reachability over one object store. func New(store objectstore.Store) *Reachability { - return &Reachability{Store: store} + return &Reachability{store: store} } // IsAncestor reports whether ancestor is reachable from descendant via commit @@ -85,298 +69,3 @@ func (r *Reachability) Walk(domain Domain, haves, wants map[objectid.ObjectID]st } return walk } - -// ErrObjectMissing indicates that a referenced object is absent from the store. -type ErrObjectMissing struct { - OID objectid.ObjectID -} - -func (e *ErrObjectMissing) Error() string { - return fmt.Sprintf("reachability: missing object %s", e.OID) -} - -// ErrObjectType indicates that a referenced object has a different type than -// what traversal expected on that edge. -type ErrObjectType struct { - OID objectid.ObjectID - Got objecttype.Type - Want objecttype.Type -} - -func (e *ErrObjectType) Error() string { - gotName, gotOK := objecttype.Name(e.Got) - if !gotOK { - gotName = fmt.Sprintf("type(%d)", e.Got) - } - wantName, wantOK := objecttype.Name(e.Want) - if !wantOK { - wantName = fmt.Sprintf("type(%d)", e.Want) - } - return fmt.Sprintf("reachability: object %s has type %s, want %s", e.OID, gotName, wantName) -} - -// Walk is one single-use iterator-style traversal. -type Walk struct { - reachability *Reachability - domain Domain - haves map[objectid.ObjectID]struct{} - wants map[objectid.ObjectID]struct{} - - seqUsed bool - err error -} - -// Seq returns the traversal sequence. It is single-use. -func (walk *Walk) Seq() iter.Seq[objectid.ObjectID] { - if walk.seqUsed { - return func(yield func(objectid.ObjectID) bool) { - _ = yield - if walk.err == nil { - walk.err = errors.New("reachability: walk sequence already consumed") - } - } - } - walk.seqUsed = true - return func(yield func(objectid.ObjectID) bool) { - if walk.err != nil { - return - } - stack := walk.initialStack() - var err error - visited := make(map[objectid.ObjectID]struct{}, len(stack)) - for len(stack) > 0 { - item := stack[len(stack)-1] - stack = stack[:len(stack)-1] - - if containsOID(walk.haves, item.id) { - continue - } - if _, ok := visited[item.id]; ok { - continue - } - visited[item.id] = struct{}{} - - var next []walkItem - next, err = walk.expand(item) - if err != nil { - walk.err = err - return - } - if !yield(item.id) { - return - } - stack = append(stack, next...) - } - } -} - -// Err returns the terminal error, if any, once Seq has been consumed. -func (walk *Walk) Err() error { - return walk.err -} - -type walkItem struct { - id objectid.ObjectID - want objecttype.Type -} - -func (walk *Walk) initialStack() []walkItem { - if len(walk.wants) == 0 { - return nil - } - stack := make([]walkItem, 0, len(walk.wants)) - for want := range walk.wants { - stack = append(stack, walkItem{id: want, want: objecttype.TypeInvalid}) - } - return stack -} - -func (walk *Walk) expand(item walkItem) ([]walkItem, error) { - if walk.domain == DomainCommits { - return walk.expandCommits(item) - } - return walk.expandObjects(item) -} - -func (walk *Walk) expandCommits(item walkItem) ([]walkItem, error) { - ty, err := walk.readHeaderType(item.id) - if err != nil { - return nil, err - } - switch ty { - case objecttype.TypeCommit: - content, err := walk.readBytesContent(item.id) - if err != nil { - return nil, err - } - commit, err := object.ParseCommit(content, item.id.Algorithm()) - if err != nil { - return nil, err - } - next := make([]walkItem, 0, len(commit.Parents)) - for _, parent := range commit.Parents { - next = append(next, walkItem{id: parent, want: objecttype.TypeInvalid}) - } - return next, nil - case objecttype.TypeTag: - content, err := walk.readBytesContent(item.id) - if err != nil { - return nil, err - } - tag, err := object.ParseTag(content, item.id.Algorithm()) - if err != nil { - return nil, err - } - return []walkItem{{id: tag.Target, want: objecttype.TypeInvalid}}, nil - case objecttype.TypeTree, objecttype.TypeBlob, objecttype.TypeInvalid, - objecttype.TypeFuture, objecttype.TypeOfsDelta, objecttype.TypeRefDelta: - return nil, &ErrObjectType{OID: item.id, Got: ty, Want: objecttype.TypeCommit} - } - return nil, fmt.Errorf("reachability: unreachable object type %d", ty) -} - -func (walk *Walk) expandObjects(item walkItem) ([]walkItem, error) { - ty, err := walk.readHeaderType(item.id) - if err != nil { - return nil, err - } - if item.want != objecttype.TypeInvalid && ty != item.want { - return nil, &ErrObjectType{OID: item.id, Got: ty, Want: item.want} - } - - switch ty { - case objecttype.TypeBlob: - return nil, nil - case objecttype.TypeCommit: - content, err := walk.readBytesContent(item.id) - if err != nil { - return nil, err - } - commit, err := object.ParseCommit(content, item.id.Algorithm()) - if err != nil { - return nil, err - } - next := make([]walkItem, 0, len(commit.Parents)+1) - next = append(next, walkItem{id: commit.Tree, want: objecttype.TypeTree}) - for _, parent := range commit.Parents { - next = append(next, walkItem{id: parent, want: objecttype.TypeCommit}) - } - return next, nil - case objecttype.TypeTree: - content, err := walk.readBytesContent(item.id) - if err != nil { - return nil, err - } - tree, err := object.ParseTree(content, item.id.Algorithm()) - if err != nil { - return nil, err - } - next := make([]walkItem, 0, len(tree.Entries)) - for _, entry := range tree.Entries { - switch entry.Mode { - case object.FileModeGitlink: - continue - case object.FileModeDir: - next = append(next, walkItem{id: entry.ID, want: objecttype.TypeTree}) - case object.FileModeRegular, object.FileModeExecutable, object.FileModeSymlink: - next = append(next, walkItem{id: entry.ID, want: objecttype.TypeBlob}) - } - } - return next, nil - case objecttype.TypeTag: - content, err := walk.readBytesContent(item.id) - if err != nil { - return nil, err - } - tag, err := object.ParseTag(content, item.id.Algorithm()) - if err != nil { - return nil, err - } - return []walkItem{{id: tag.Target, want: tag.TargetType}}, nil - case objecttype.TypeInvalid, objecttype.TypeFuture, objecttype.TypeOfsDelta, objecttype.TypeRefDelta: - return nil, &ErrObjectType{OID: item.id, Got: ty, Want: item.want} - } - return nil, fmt.Errorf("reachability: unreachable object type %d", ty) -} - -func (r *Reachability) peelRootToDomain(id objectid.ObjectID, domain Domain) (objectid.ObjectID, error) { - if err := validateDomain(domain); err != nil { - return objectid.ObjectID{}, err - } - for { - ty, err := r.readHeaderType(id) - if err != nil { - return objectid.ObjectID{}, err - } - if ty != objecttype.TypeTag { - if domain == DomainCommits && ty != objecttype.TypeCommit { - return objectid.ObjectID{}, &ErrObjectType{OID: id, Got: ty, Want: objecttype.TypeCommit} - } - return id, nil - } - - content, err := r.readBytesContent(id) - if err != nil { - return objectid.ObjectID{}, err - } - tag, err := object.ParseTag(content, id.Algorithm()) - if err != nil { - return objectid.ObjectID{}, err - } - id = tag.Target - } -} - -func validateDomain(domain Domain) error { - switch domain { - case DomainCommits, DomainObjects: - return nil - default: - return fmt.Errorf("reachability: invalid domain %d", domain) - } -} - -func containsOID(set map[objectid.ObjectID]struct{}, id objectid.ObjectID) bool { - if len(set) == 0 { - return false - } - _, ok := set[id] - return ok -} - -// The following helpers exist because we don't have unified error handling across the entire project. -// This will be fixed later. - -func (walk *Walk) readHeaderType(id objectid.ObjectID) (objecttype.Type, error) { - return walk.reachability.readHeaderType(id) -} - -func (r *Reachability) readHeaderType(id objectid.ObjectID) (objecttype.Type, error) { - ty, _, err := r.Store.ReadHeader(id) - if err != nil { - if errors.Is(err, objectstore.ErrObjectNotFound) { - return objecttype.TypeInvalid, &ErrObjectMissing{OID: id} - } - return objecttype.TypeInvalid, err - } - return ty, nil -} - -func (walk *Walk) readBytesContent(id objectid.ObjectID) ([]byte, error) { - content, err := walk.reachability.readBytesContent(id) - if err != nil { - return nil, err - } - return content, nil -} - -func (r *Reachability) readBytesContent(id objectid.ObjectID) ([]byte, error) { - _, content, err := r.Store.ReadBytesContent(id) - if err != nil { - if errors.Is(err, objectstore.ErrObjectNotFound) { - return nil, &ErrObjectMissing{OID: id} - } - return nil, err - } - return content, nil -} diff --git a/reachability/reachability_unit_test.go b/reachability/unit_test.go index ec177938..ec177938 100644 --- a/reachability/reachability_unit_test.go +++ b/reachability/unit_test.go diff --git a/reachability/walk.go b/reachability/walk.go new file mode 100644 index 00000000..2b592a45 --- /dev/null +++ b/reachability/walk.go @@ -0,0 +1,195 @@ +package reachability + +import ( + "errors" + "fmt" + "iter" + + "codeberg.org/lindenii/furgit/object" + "codeberg.org/lindenii/furgit/objectid" + "codeberg.org/lindenii/furgit/objecttype" +) + +// Walk is one single-use iterator-style traversal. +type Walk struct { + reachability *Reachability + domain Domain + haves map[objectid.ObjectID]struct{} + wants map[objectid.ObjectID]struct{} + + seqUsed bool + err error +} + +// Seq returns the traversal sequence. It is single-use. +func (walk *Walk) Seq() iter.Seq[objectid.ObjectID] { + if walk.seqUsed { + return func(yield func(objectid.ObjectID) bool) { + _ = yield + if walk.err == nil { + walk.err = errors.New("reachability: walk sequence already consumed") + } + } + } + walk.seqUsed = true + return func(yield func(objectid.ObjectID) bool) { + if walk.err != nil { + return + } + stack := walk.initialStack() + var err error + visited := make(map[objectid.ObjectID]struct{}, len(stack)) + for len(stack) > 0 { + item := stack[len(stack)-1] + stack = stack[:len(stack)-1] + + if containsOID(walk.haves, item.id) { + continue + } + if _, ok := visited[item.id]; ok { + continue + } + visited[item.id] = struct{}{} + + var next []walkItem + next, err = walk.expand(item) + if err != nil { + walk.err = err + return + } + if !yield(item.id) { + return + } + stack = append(stack, next...) + } + } +} + +// Err returns the terminal error, if any, once Seq has been consumed. +func (walk *Walk) Err() error { + return walk.err +} + +type walkItem struct { + id objectid.ObjectID + want objecttype.Type +} + +func (walk *Walk) initialStack() []walkItem { + if len(walk.wants) == 0 { + return nil + } + stack := make([]walkItem, 0, len(walk.wants)) + for want := range walk.wants { + stack = append(stack, walkItem{id: want, want: objecttype.TypeInvalid}) + } + return stack +} + +func (walk *Walk) expand(item walkItem) ([]walkItem, error) { + if walk.domain == DomainCommits { + return walk.expandCommits(item) + } + return walk.expandObjects(item) +} + +func (walk *Walk) expandCommits(item walkItem) ([]walkItem, error) { + ty, err := walk.readHeaderType(item.id) + if err != nil { + return nil, err + } + switch ty { + case objecttype.TypeCommit: + content, err := walk.readBytesContent(item.id) + if err != nil { + return nil, err + } + commit, err := object.ParseCommit(content, item.id.Algorithm()) + if err != nil { + return nil, err + } + next := make([]walkItem, 0, len(commit.Parents)) + for _, parent := range commit.Parents { + next = append(next, walkItem{id: parent, want: objecttype.TypeInvalid}) + } + return next, nil + case objecttype.TypeTag: + content, err := walk.readBytesContent(item.id) + if err != nil { + return nil, err + } + tag, err := object.ParseTag(content, item.id.Algorithm()) + if err != nil { + return nil, err + } + return []walkItem{{id: tag.Target, want: objecttype.TypeInvalid}}, nil + case objecttype.TypeTree, objecttype.TypeBlob, objecttype.TypeInvalid, + objecttype.TypeFuture, objecttype.TypeOfsDelta, objecttype.TypeRefDelta: + return nil, &ErrObjectType{OID: item.id, Got: ty, Want: objecttype.TypeCommit} + } + return nil, fmt.Errorf("reachability: unreachable object type %d", ty) +} + +func (walk *Walk) expandObjects(item walkItem) ([]walkItem, error) { + ty, err := walk.readHeaderType(item.id) + if err != nil { + return nil, err + } + if item.want != objecttype.TypeInvalid && ty != item.want { + return nil, &ErrObjectType{OID: item.id, Got: ty, Want: item.want} + } + + switch ty { + case objecttype.TypeBlob: + return nil, nil + case objecttype.TypeCommit: + content, err := walk.readBytesContent(item.id) + if err != nil { + return nil, err + } + commit, err := object.ParseCommit(content, item.id.Algorithm()) + if err != nil { + return nil, err + } + next := make([]walkItem, 0, len(commit.Parents)+1) + next = append(next, walkItem{id: commit.Tree, want: objecttype.TypeTree}) + for _, parent := range commit.Parents { + next = append(next, walkItem{id: parent, want: objecttype.TypeCommit}) + } + return next, nil + case objecttype.TypeTree: + content, err := walk.readBytesContent(item.id) + if err != nil { + return nil, err + } + tree, err := object.ParseTree(content, item.id.Algorithm()) + if err != nil { + return nil, err + } + next := make([]walkItem, 0, len(tree.Entries)) + for _, entry := range tree.Entries { + switch entry.Mode { + case object.FileModeGitlink: + continue + case object.FileModeDir: + next = append(next, walkItem{id: entry.ID, want: objecttype.TypeTree}) + case object.FileModeRegular, object.FileModeExecutable, object.FileModeSymlink: + next = append(next, walkItem{id: entry.ID, want: objecttype.TypeBlob}) + } + } + return next, nil + case objecttype.TypeTag: + content, err := walk.readBytesContent(item.id) + if err != nil { + return nil, err + } + tag, err := object.ParseTag(content, item.id.Algorithm()) + if err != nil { + return nil, err + } + return []walkItem{{id: tag.Target, want: tag.TargetType}}, nil + case objecttype.TypeInvalid, objecttype.TypeFuture, objecttype.TypeOfsDelta, objecttype.TypeRefDelta: + return nil, &ErrObjectType{OID: item.id, Got: ty, Want: item.want} + } + return nil, fmt.Errorf("reachability: unreachable object type %d", ty) +} |