Composite — Practice Tasks¶

package fs

import (
    "fmt"
    "strings"
)

// Senior decision: minimal Node interface. Anything more (Parent, Path,
// ModTime) belongs to specific node types and gets feature-detected
// with a type assertion. Bloating Node forces leaves to implement
// methods they don't need.
type Node interface {
    Name() string
    Size() int64
    Children() []Node
}

type File struct {
    name string
    size int64
}

func NewFile(name string, size int64) *File { return &File{name, size} }
func (f *File) Name() string                { return f.name }
func (f *File) Size() int64                 { return f.size }
func (f *File) Children() []Node            { return nil }

type Folder struct {
    name     string
    children []Node
}

func NewFolder(name string) *Folder { return &Folder{name: name} }
func (d *Folder) Name() string      { return d.name }
func (d *Folder) Children() []Node  { return d.children }

// Senior decision: Size recurses through Children() (the interface),
// not d.children (the concrete slice). A future SymlinkFolder slots
// in without changing this method.
func (d *Folder) Size() int64 {
    var total int64
    for _, c := range d.Children() {
        total += c.Size()
    }
    return total
}

func (d *Folder) Add(n Node) { d.children = append(d.children, n) }

func Print(n Node) string {
    var b strings.Builder
    var walk func(Node, int)
    walk = func(n Node, depth int) {
        fmt.Fprintf(&b, "%s%s (%d)\n", strings.Repeat("  ", depth), n.Name(), n.Size())
        for _, c := range n.Children() {
            walk(c, depth+1)
        }
    }
    walk(n, 0)
    return b.String()
}

type Folder struct {
    name     string
    children []Node
    // Senior decision: cache only the LOCAL recursive sum. A child
    // added deep down invalidates only this folder; ancestors return
    // stale until Invalidate is called explicitly. The full fix needs
    // parent pointers (Task 13). Document the limitation; do not bolt
    // on a half-correct invalidation chain.
    cachedSize int64
    sizeValid  bool
}

func (d *Folder) Size() int64 {
    if d.sizeValid {
        return d.cachedSize
    }
    var total int64
    for _, c := range d.Children() {
        total += c.Size()
    }
    d.cachedSize = total
    d.sizeValid = true
    return total
}

func (d *Folder) Add(n Node) {
    d.children = append(d.children, n)
    d.sizeValid = false
}

func (d *Folder) Remove(n Node) bool {
    for i, c := range d.children {
        if c == n {
            d.children = append(d.children[:i], d.children[i+1:]...)
            d.sizeValid = false
            return true
        }
    }
    return false
}

// Senior decision: Invalidate is exported so callers who DID wire up
// parent pointers can bubble invalidation themselves.
func (d *Folder) Invalidate() { d.sizeValid = false }

// Senior decision: DFS pre-order matches go/ast.Inspect and
// filepath.Walk. If you need post-order, expose a second function —
// overloading one with a flag bloats the API and surprises readers.
func Walk(n Node, fn func(Node)) {
    fn(n)
    for _, c := range n.Children() {
        Walk(c, fn)
    }
}

func Count(n Node) int {
    var c int
    Walk(n, func(Node) { c++ })
    return c
}

// Senior decision: TotalSize sums LEAVES only. Summing folders too
// would double-count. The type switch is the canonical "consumer
// downcasts at the leaf" idiom.
func TotalSize(n Node) int64 {
    var total int64
    Walk(n, func(x Node) {
        if f, ok := x.(*File); ok {
            total += f.Size()
        }
    })
    return total
}

func FindByName(root Node, name string) Node {
    var found Node
    Walk(root, func(n Node) {
        if found == nil && n.Name() == name {
            found = n
        }
    })
    return found
}

func Filter(n Node, pred func(Node) bool) []Node {
    var out []Node
    Walk(n, func(x Node) {
        if pred(x) {
            out = append(out, x)
        }
    })
    return out
}

// Senior decision: don't write FilterByExt — once Filter exists, the
// caller composes predicates. Keeping the kernel small is half the
// point of building Walk and Filter as separate combinators.

func IsFile(n Node) bool   { _, ok := n.(*File); return ok }
func IsFolder(n Node) bool { _, ok := n.(*Folder); return ok }

func HasExt(ext string) func(Node) bool {
    return func(n Node) bool { return IsFile(n) && strings.HasSuffix(n.Name(), ext) }
}
func IsEmptyFolder(n Node) bool {
    f, ok := n.(*Folder)
    return ok && len(f.Children()) == 0
}
func MoreThan(k int) func(Node) bool {
    return func(n Node) bool { return len(n.Children()) > k }
}
func And(ps ...func(Node) bool) func(Node) bool {
    return func(n Node) bool {
        for _, p := range ps {
            if !p(n) {
                return false
            }
        }
        return true
    }
}

// goFiles  := Filter(root, HasExt(".go"))
// bigDirs  := Filter(root, And(IsFolder, MoreThan(5)))

type Visitor interface {
    Visit(n Node) (descend bool)
}

// Senior decision: Visit returns descend bool. That's the smallest
// extension over closure-Walk that lets the visitor prune subtrees —
// the single most important capability for analysis tools.
func Accept(n Node, v Visitor) {
    if !v.Visit(n) {
        return
    }
    for _, c := range n.Children() {
        Accept(c, v)
    }
}

type CountVisitor struct{ Count int }

func (v *CountVisitor) Visit(n Node) bool {
    v.Count++
    return true
}

// Senior decision: skipping subtrees is the day-one win of visitor
// over closure. A linter that wants to ignore vendor/.git/node_modules
// returns false on those folders and never pays for the subtree walk.
type SkipNoise struct{ Found []Node }

func (v *SkipNoise) Visit(n Node) bool {
    name := n.Name()
    if name == "vendor" || name == ".git" || name == "node_modules" {
        return false
    }
    if _, ok := n.(*File); ok {
        v.Found = append(v.Found, n)
    }
    return true
}

// Senior decision: sealed interface via unexported method. External
// packages can hold Expr values but cannot fabricate new variants.
// That keeps Eval's type switch exhaustive — no "default" case
// panicking on user-defined types. Cost: AST closed to user
// extension. For a DSL evaluator, right trade.
type Expr interface{ isExpr() }

type Num struct{ V int }
type Add struct{ L, R Expr }
type Sub struct{ L, R Expr }
type Mul struct{ L, R Expr }
type Div struct{ L, R Expr }
type Neg struct{ X Expr }

func (Num) isExpr() {}
func (Add) isExpr() {}
func (Sub) isExpr() {}
func (Mul) isExpr() {}
func (Div) isExpr() {}
func (Neg) isExpr() {}

func Eval(e Expr) int {
    switch x := e.(type) {
    case Num: return x.V
    case Add: return Eval(x.L) + Eval(x.R)
    case Sub: return Eval(x.L) - Eval(x.R)
    case Mul: return Eval(x.L) * Eval(x.R)
    case Div: return Eval(x.L) / Eval(x.R)
    case Neg: return -Eval(x.X)
    default:  panic(fmt.Sprintf("arith: unknown Expr %T", e))
    }
}

// Senior decision: Print is a second visitor over the same tree.
// Adding "optimize" or "typecheck" is another. The day you add a
// new operation, write one function. The day you add a new node,
// touch every operation. Open-closed only one way at a time.
func Print(e Expr) string {
    switch x := e.(type) {
    case Num: return fmt.Sprintf("%d", x.V)
    case Add: return "(" + Print(x.L) + " + " + Print(x.R) + ")"
    case Sub: return "(" + Print(x.L) + " - " + Print(x.R) + ")"
    case Mul: return "(" + Print(x.L) + " * " + Print(x.R) + ")"
    case Div: return "(" + Print(x.L) + " / " + Print(x.R) + ")"
    case Neg: return "-" + Print(x.X)
    }
    return "?"
}

type Kind int

const (
    KindScalar Kind = iota
    KindMapping
    KindSequence
)

// Senior decision: one struct, Kind discriminator. Mapping uses
// Children in pairs (key, value, ...) the way yaml.v3 does — the
// alternative (separate KeyChildren/ValChildren slices) fragments
// the shape, which matters when you marshal.
type Node struct {
    Kind     Kind    `json:"kind"`
    Value    string  `json:"value,omitempty"`
    Children []*Node `json:"children,omitempty"`
}

// Senior decision: constructors per Kind. The zero Node compiles as
// KindScalar with empty Value — that's silently produced bugs in the
// yaml code this is modelled after. Constructors make intent visible.
func Scalar(v string) *Node     { return &Node{Kind: KindScalar, Value: v} }
func Sequence(items ...*Node) *Node { return &Node{Kind: KindSequence, Children: items} }
func Mapping(kvs ...*Node) *Node {
    if len(kvs)%2 != 0 {
        panic("ynode: Mapping needs key,value pairs")
    }
    return &Node{Kind: KindMapping, Children: kvs}
}

// JSON works out of the box — flat struct, no interfaces. THE thing
// pure-interface Composite makes hard (compare with Task 11).
//
//   root := Mapping(Scalar("name"), Scalar("alice"),
//                   Scalar("tags"), Sequence(Scalar("dev"), Scalar("go")))
//   b, _ := json.Marshal(root)
//   var back Node; _ = json.Unmarshal(b, &back)

// Senior decision: Tree[T] over any. Methods that DON'T touch T's
// structure stay on the receiver (Add). Methods that DO (Map, Fold)
// become top-level functions because Go still disallows type
// parameters on methods.
type Tree[T any] struct {
    Value    T
    Children []*Tree[T]
}

func New[T any](v T) *Tree[T]   { return &Tree[T]{Value: v} }
func (t *Tree[T]) Add(v T) *Tree[T] {
    c := New(v)
    t.Children = append(t.Children, c)
    return c
}
func (t *Tree[T]) AddTree(c *Tree[T]) *Tree[T] {
    t.Children = append(t.Children, c)
    return c
}

func Walk[T any](t *Tree[T], fn func(*Tree[T])) {
    if t == nil { return }
    fn(t)
    for _, c := range t.Children {
        Walk(c, fn)
    }
}

// Senior decision: Map allocates — never mutates input. Matches
// slices/maps conventions. In-place is faster but invites aliasing
// bugs.
func Map[T, U any](t *Tree[T], fn func(T) U) *Tree[U] {
    if t == nil { return nil }
    out := New(fn(t.Value))
    for _, c := range t.Children {
        out.AddTree(Map(c, fn))
    }
    return out
}

func Fold[T, U any](t *Tree[T], init U, fn func(U, T) U) U {
    if t == nil { return init }
    acc := fn(init, t.Value)
    for _, c := range t.Children {
        acc = Fold(c, acc, fn)
    }
    return acc
}

func Count[T any](t *Tree[T]) int {
    return Fold(t, 0, func(n int, _ T) int { return n + 1 })
}

// Senior decision: cycle-safe by default? No. The unsafe Walk is 5
// lines and adequate for genuinely tree-shaped data. Charging every
// caller a map allocation for a footgun they don't have is wrong.
// Expose both; document when each is right.
func WalkSafe(n Node, fn func(Node)) {
    seen := map[Node]bool{}
    var walk func(Node)
    walk = func(n Node) {
        if n == nil || seen[n] {
            return
        }
        seen[n] = true
        fn(n)
        for _, c := range n.Children() {
            walk(c)
        }
    }
    walk(n)
}

// Senior decision: a path-set distinguishes back-edge (real cycle)
// from shared subtree (DAG). WalkSafe alone treats shared subtrees
// as cycles and prunes them — fine for traversal, wrong for analysis.
func DetectCycle(n Node) []Node {
    var cycle []Node
    seen := map[Node]bool{}
    var walk func(Node, map[Node]bool) bool
    walk = func(n Node, path map[Node]bool) bool {
        if path[n] {
            cycle = append(cycle, n)
            return true
        }
        if seen[n] {
            return false
        }
        seen[n] = true
        path[n] = true
        defer delete(path, n)
        for _, c := range n.Children() {
            if walk(c, path) {
                return true
            }
        }
        return false
    }
    walk(n, map[Node]bool{})
    return cycle
}

// Senior decision: errgroup over hand-rolled WaitGroup + error chan.
// errgroup gives cancel-on-first-error and concurrency limit for free.
// The home-grown equivalent is ~30 lines and gets the race against
// ctx cancel wrong on the first try.
func WalkParallel(
    ctx context.Context, root Node,
    fn func(context.Context, Node) error, parallelism int,
) error {
    g, gctx := errgroup.WithContext(ctx)
    if parallelism > 0 {
        g.SetLimit(parallelism)
    }
    var walk func(Node)
    walk = func(n Node) {
        n := n
        // Senior decision: per-node dispatch. Per-subtree is identical
        // for shallow-wide trees, MUCH worse for deep-narrow because
        // recursion serialises. Per-node is the right default.
        g.Go(func() error {
            if err := gctx.Err(); err != nil {
                return err
            }
            if err := fn(gctx, n); err != nil {
                return err
            }
            for _, c := range n.Children() {
                walk(c)
            }
            return nil
        })
    }
    walk(root)
    return g.Wait()
}

// Concurrent fn must be safe — that's the caller's job:
//   var total atomic.Int64
//   WalkParallel(ctx, root, func(_ context.Context, n Node) error {
//       if f, ok := n.(*File); ok { total.Add(f.Size()) }
//       return nil
//   }, 16)

type Node interface { Type() string; Children() []Node }
type File   struct{ Name string; Size int64 }
type Folder struct{ Name string; Kids []Node }

func (f *File) Type() string     { return "file" }
func (f *File) Children() []Node { return nil }
func (d *Folder) Type() string     { return "folder" }
func (d *Folder) Children() []Node { return d.Kids }

// Senior decision: package-level registry — concrete types known at
// compile time. Plugin discovery would put it on a *Registry.
var factories = map[string]func() Node{
    "file":   func() Node { return &File{} },
    "folder": func() Node { return &Folder{} },
}

// Senior decision: discriminator + payload as SEPARATE fields.
// Embedding works until a payload has its own "type" field.
type envelope struct {
    Type    string          `json:"type"`
    Payload json.RawMessage `json:"payload"`
}

func Marshal(n Node) ([]byte, error) {
    var payload []byte
    var err error
    switch x := n.(type) {
    case *File:
        payload, err = json.Marshal(x)
    case *Folder:
        kids := make([]json.RawMessage, 0, len(x.Kids))
        for _, c := range x.Kids {
            b, err := Marshal(c)
            if err != nil { return nil, err }
            kids = append(kids, b)
        }
        payload, err = json.Marshal(struct {
            Name string            `json:"Name"`
            Kids []json.RawMessage `json:"Kids"`
        }{x.Name, kids})
    default:
        return nil, fmt.Errorf("cannot marshal %T", n)
    }
    if err != nil { return nil, err }
    return json.Marshal(envelope{n.Type(), payload})
}

func Unmarshal(data []byte) (Node, error) {
    var env envelope
    if err := json.Unmarshal(data, &env); err != nil { return nil, err }
    factory, ok := factories[env.Type]
    if !ok { return nil, fmt.Errorf("unknown type %q", env.Type) }
    node := factory()
    switch x := node.(type) {
    case *File:
        if err := json.Unmarshal(env.Payload, x); err != nil { return nil, err }
    case *Folder:
        var w struct {
            Name string
            Kids []json.RawMessage
        }
        if err := json.Unmarshal(env.Payload, &w); err != nil { return nil, err }
        x.Name = w.Name
        for _, raw := range w.Kids {
            child, err := Unmarshal(raw)
            if err != nil { return nil, err }
            x.Kids = append(x.Kids, child)
        }
    }
    return node, nil
}

// Senior decision: Command is one struct, no interface. Pure-interface
// is overdesigned for a CLI — every command is data plus a Run
// closure. Tagged-struct also wrong because there's only one Kind.
// "One struct, no interface" is what cobra.Command is.
type Command struct {
    Name        string
    Use         string
    Run         func(args []string) error
    Subcommands []*Command
    parent      *Command
}

func (c *Command) Add(sub *Command) {
    sub.parent = c
    c.Subcommands = append(c.Subcommands, sub)
}

func (c *Command) findSub(name string) *Command {
    for _, s := range c.Subcommands {
        if s.Name == name { return s }
    }
    return nil
}

// Senior decision: Execute is iterative, not recursive. The arg list
// is a flat stream; matching one subcommand at a time and looping is
// clearer than threading state through recursion. Recursion navigates
// STRUCTURE; iteration consumes STREAM.
func (c *Command) Execute(args []string) error {
    cmd, rest := c, args
    for len(rest) > 0 {
        if rest[0] == "-h" || rest[0] == "--help" || rest[0] == "help" {
            fmt.Print(cmd.Help())
            return nil
        }
        sub := cmd.findSub(rest[0])
        if sub == nil { break }
        cmd = sub
        rest = rest[1:]
    }
    if cmd.Run == nil {
        fmt.Print(cmd.Help())
        if cmd == c && len(args) > 0 {
            return fmt.Errorf("unknown command: %s", args[0])
        }
        return nil
    }
    return cmd.Run(rest)
}

func (c *Command) Help() string {
    var b strings.Builder
    fmt.Fprintf(&b, "%s — %s\n\n", c.fullPath(), c.Use)
    if len(c.Subcommands) > 0 {
        fmt.Fprintln(&b, "Subcommands:")
        subs := append([]*Command(nil), c.Subcommands...)
        sort.Slice(subs, func(i, j int) bool { return subs[i].Name < subs[j].Name })
        max := 0
        for _, s := range subs {
            if len(s.Name) > max { max = len(s.Name) }
        }
        for _, s := range subs {
            fmt.Fprintf(&b, "  %-*s  %s\n", max, s.Name, s.Use)
        }
    }
    return b.String()
}

func (c *Command) fullPath() string {
    if c.parent == nil { return c.Name }
    return c.parent.fullPath() + " " + c.Name
}

type Node struct {
    Tag      string
    Attrs    map[string]string
    Text     string
    Children []*Node
    Parent   *Node
}

func New(tag string) *Node {
    return &Node{Tag: tag, Attrs: map[string]string{}}
}

// Senior decision: Append manages parent linkage on BOTH sides.
// Forgetting to detach from the old parent leaves the child in two
// parent.Children lists — classic DOM bug.
func (n *Node) Append(child *Node) {
    if child == nil { return }
    if child.Parent != nil { child.Detach() }
    child.Parent = n
    n.Children = append(n.Children, child)
}

func (n *Node) Detach() {
    p := n.Parent
    if p == nil { return }
    for i, c := range p.Children {
        if c == n {
            p.Children = append(p.Children[:i], p.Children[i+1:]...)
            break
        }
    }
    n.Parent = nil
}

// Senior decision: Closest INCLUDES self. Same semantics as browser
// Element.closest(). "Starts from parent" surprises are a perennial
// source of jQuery bugs.
func (n *Node) Closest(tag string) *Node {
    for cur := n; cur != nil; cur = cur.Parent {
        if cur.Tag == tag { return cur }
    }
    return nil
}

func (n *Node) Path() string {
    if n.Parent == nil { return "/" + n.Tag }
    return n.Parent.Path() + "/" + n.Tag
}

// Senior decision: invariant check that tests must run after every
// mutation. The parent-pointer model is brittle; fuzz it hard.
func (n *Node) CheckInvariants() error {
    for _, c := range n.Children {
        if c.Parent != n {
            return fmt.Errorf("node %s child %s has wrong parent", n.Path(), c.Tag)
        }
        if err := c.CheckInvariants(); err != nil { return err }
    }
    return nil
}

type Node interface {
    Name() string
    Children() []Node
    Hash() string
}

type ChangeKind int
const ( Added ChangeKind = iota; Removed; Modified; Moved )

type Change struct {
    Kind   ChangeKind
    Path   string
    From   string // for Moved
    Before Node
    After  Node
}

// Senior decision: path-based matching makes this O(N). Right for
// filesystems, config trees, sitemaps. For AST/DOM diff (no stable
// names, order matters) you need Zhang-Shasha. Be honest about model.
func Diff(before, after Node) []Change {
    bm, am := flatten(before), flatten(after)
    return diffMaps(bm, am)
}

func flatten(n Node) map[string]Node {
    out := map[string]Node{}
    var walk func(Node, string)
    walk = func(n Node, p string) {
        path := p + "/" + n.Name()
        if p == "" { path = n.Name() }
        out[path] = n
        for _, c := range n.Children() { walk(c, path) }
    }
    walk(n, "")
    return out
}

func diffMaps(before, after map[string]Node) []Change {
    var changes []Change

    // Senior decision: a node is "moved" only if EXACTLY one removal
    // and one addition share its content hash. Multi-match means we
    // can't tell; report as add+remove. Arbitrary pairing creates
    // noisy diffs.
    rmHash, addHash := map[string][]string{}, map[string][]string{}
    for p, n := range before {
        if _, ok := after[p]; !ok { rmHash[n.Hash()] = append(rmHash[n.Hash()], p) }
    }
    for p, n := range after {
        if _, ok := before[p]; !ok { addHash[n.Hash()] = append(addHash[n.Hash()], p) }
    }
    movedFrom, movedTo := map[string]string{}, map[string]string{}
    for h, rms := range rmHash {
        if ads := addHash[h]; len(rms) == 1 && len(ads) == 1 {
            movedFrom[ads[0]], movedTo[rms[0]] = rms[0], ads[0]
        }
    }

    var rms, adds []string
    for p := range before {
        if _, ok := after[p]; !ok && movedTo[p] == "" { rms = append(rms, p) }
    }
    for p := range after {
        if _, ok := before[p]; !ok && movedFrom[p] == "" { adds = append(adds, p) }
    }
    sort.Strings(rms)
    sort.Strings(adds)
    for _, p := range rms {
        changes = append(changes, Change{Kind: Removed, Path: p, Before: before[p]})
    }
    for _, p := range adds {
        changes = append(changes, Change{Kind: Added, Path: p, After: after[p]})
    }

    var moved []string
    for np := range movedFrom { moved = append(moved, np) }
    sort.Strings(moved)
    for _, np := range moved {
        op := movedFrom[np]
        changes = append(changes, Change{Kind: Moved, From: op, Path: np,
            Before: before[op], After: after[np]})
    }

    var shared []string
    for p := range before {
        if _, ok := after[p]; ok { shared = append(shared, p) }
    }
    sort.Strings(shared)
    for _, p := range shared {
        if before[p].Hash() != after[p].Hash() {
            changes = append(changes, Change{Kind: Modified, Path: p,
                Before: before[p], After: after[p]})
        }
    }
    return changes
}