//go:build linux && !appengine

package fsnotify

import (
        "errors"
        "fmt"
        "io"
        "io/fs"
        "os"
        "path/filepath"
        "strings"
        "sync"
        "time"
        "unsafe"

        "github.com/fsnotify/fsnotify/internal"
        "golang.org/x/sys/unix"
)

type inotify struct {
        *shared
        Events chan Event
        Errors chan error

        // Store fd here as os.File.Read() will no longer return on close after
        // calling Fd(). See: https://github.com/golang/go/issues/26439
        fd          int
        inotifyFile *os.File
        watches     *watches
        doneResp    chan struct{} // Channel to respond to Close

        // Store rename cookies in an array, with the index wrapping to 0. Almost
        // all of the time what we get is a MOVED_FROM to set the cookie and the
        // next event inotify sends will be MOVED_TO to read it. However, this is
        // not guaranteed – as described in inotify(7) – and we may get other events
        // between the two MOVED_* events (including other MOVED_* ones).
        //
        // A second issue is that moving a file outside the watched directory will
        // trigger a MOVED_FROM to set the cookie, but we never see the MOVED_TO to
        // read and delete it. So just storing it in a map would slowly leak memory.
        //
        // Doing it like this gives us a simple fast LRU-cache that won't allocate.
        // Ten items should be more than enough for our purpose, and a loop over
        // such a short array is faster than a map access anyway (not that it hugely
        // matters since we're talking about hundreds of ns at the most, but still).
        cookies     [10]koekje
        cookieIndex uint8
        cookiesMu   sync.Mutex
}

type (
        watches struct {
                wd   map[uint32]*watch // wd → watch
                path map[string]uint32 // pathname → wd
        }
        watch struct {
                wd         uint32 // Watch descriptor (as returned by the inotify_add_watch() syscall)
                flags      uint32 // inotify flags of this watch (see inotify(7) for the list of valid flags)
                path       string // Watch path.
                watchFlags watchFlag
        }
        koekje struct {
                cookie uint32
                path   string
        }
)

func (w watch) byUser() bool  { return w.watchFlags&flagByUser != 0 }
func (w watch) recurse() bool { return w.watchFlags&flagRecurse != 0 }

func newWatches() *watches {
        return &watches{
                wd:   make(map[uint32]*watch),
                path: make(map[string]uint32),
        }
}

func (w *watches) byPath(path string) *watch { return w.wd[w.path[path]] }
func (w *watches) byWd(wd uint32) *watch     { return w.wd[wd] }
func (w *watches) len() int                  { return len(w.wd) }
func (w *watches) add(ww *watch)             { w.wd[ww.wd] = ww; w.path[ww.path] = ww.wd }
func (w *watches) remove(watch *watch)       { delete(w.path, watch.path); delete(w.wd, watch.wd) }

func (w *watches) removePath(path string) ([]uint32, error) {
        path, recurse := recursivePath(path)
        wd, ok := w.path[path]
        if !ok {
                return nil, fmt.Errorf("%w: %s", ErrNonExistentWatch, path)
        }

        watch := w.wd[wd]
        if recurse && !watch.recurse() {
                return nil, fmt.Errorf("can't use /... with non-recursive watch %q", path)
        }

        delete(w.path, path)
        delete(w.wd, wd)
        if !watch.recurse() {
                return []uint32{wd}, nil
        }

        wds := make([]uint32, 0, 8)
        wds = append(wds, wd)
        for p, rwd := range w.path {
                if strings.HasPrefix(p, path) {
                        delete(w.path, p)
                        delete(w.wd, rwd)
                        wds = append(wds, rwd)
                }
        }
        return wds, nil
}

func (w *watches) updatePath(path string, f func(*watch) (*watch, error)) error {
        var existing *watch
        wd, ok := w.path[path]
        if ok {
                existing = w.wd[wd]
        }

        upd, err := f(existing)
        if err != nil {
                return err
        }
        if upd != nil {
                w.wd[upd.wd] = upd
                w.path[upd.path] = upd.wd

                if upd.wd != wd {
                        delete(w.wd, wd)
                }
        }

        return nil
}

var defaultBufferSize = 0

func newBackend(ev chan Event, errs chan error) (backend, error) {
        // Need to set nonblocking mode for SetDeadline to work, otherwise blocking
        // I/O operations won't terminate on close.
        fd, errno := unix.InotifyInit1(unix.IN_CLOEXEC | unix.IN_NONBLOCK)
        if fd == -1 {
                return nil, errno
        }

        w := &inotify{
                shared:      newShared(ev, errs),
                Events:      ev,
                Errors:      errs,
                fd:          fd,
                inotifyFile: os.NewFile(uintptr(fd), ""),
                watches:     newWatches(),
                doneResp:    make(chan struct{}),
        }

        go w.readEvents()
        return w, nil
}

func (w *inotify) Close() error {
        if w.shared.close() {
                return nil
        }

        // Causes any blocking reads to return with an error, provided the file
        // still supports deadline operations.
        err := w.inotifyFile.Close()
        if err != nil {
                return err
        }

        <-w.doneResp // Wait for readEvents() to finish.
        return nil
}

func (w *inotify) Add(name string) error { return w.AddWith(name) }

func (w *inotify) AddWith(path string, opts ...addOpt) error {
        if w.isClosed() {
                return ErrClosed
        }
        if debug {
                fmt.Fprintf(os.Stderr, "FSNOTIFY_DEBUG: %s  AddWith(%q)\n",
                        time.Now().Format("15:04:05.000000000"), path)
        }

        with := getOptions(opts...)
        if !w.xSupports(with.op) {
                return fmt.Errorf("%w: %s", xErrUnsupported, with.op)
        }

        add := func(path string, with withOpts, wf watchFlag) error {
                var flags uint32
                if with.op.Has(Create) {
                        flags |= unix.IN_CREATE
                }
                if with.op.Has(Write) {
                        flags |= unix.IN_MODIFY
                }
                if with.op.Has(Remove) {
                        flags |= unix.IN_DELETE | unix.IN_DELETE_SELF
                }
                if with.op.Has(Rename) {
                        flags |= unix.IN_MOVED_TO | unix.IN_MOVED_FROM | unix.IN_MOVE_SELF
                }
                if with.op.Has(Chmod) {
                        flags |= unix.IN_ATTRIB
                }
                if with.op.Has(xUnportableOpen) {
                        flags |= unix.IN_OPEN
                }
                if with.op.Has(xUnportableRead) {
                        flags |= unix.IN_ACCESS
                }
                if with.op.Has(xUnportableCloseWrite) {
                        flags |= unix.IN_CLOSE_WRITE
                }
                if with.op.Has(xUnportableCloseRead) {
                        flags |= unix.IN_CLOSE_NOWRITE
                }
                return w.register(path, flags, wf)
        }

        w.mu.Lock()
        defer w.mu.Unlock()
        path, recurse := recursivePath(path)
        if recurse {
                return filepath.WalkDir(path, func(root string, d fs.DirEntry, err error) error {
                        if err != nil {
                                return err
                        }
                        if !d.IsDir() {
                                if root == path {
                                        return fmt.Errorf("fsnotify: not a directory: %q", path)
                                }
                                return nil
                        }

                        // Send a Create event when adding new directory from a recursive
                        // watch; this is for "mkdir -p one/two/three". Usually all those
                        // directories will be created before we can set up watchers on the
                        // subdirectories, so only "one" would be sent as a Create event and
                        // not "one/two" and "one/two/three" (inotifywait -r has the same
                        // problem).
                        if with.sendCreate && root != path {
                                w.sendEvent(Event{Name: root, Op: Create})
                        }

                        wf := flagRecurse
                        if root == path {
                                wf |= flagByUser
                        }
                        return add(root, with, wf)
                })
        }

        return add(path, with, 0)
}

func (w *inotify) register(path string, flags uint32, wf watchFlag) error {
        return w.watches.updatePath(path, func(existing *watch) (*watch, error) {
                if existing != nil {
                        flags |= existing.flags | unix.IN_MASK_ADD
                }

                wd, err := unix.InotifyAddWatch(w.fd, path, flags)
                if wd == -1 {
                        return nil, err
                }

                if e, ok := w.watches.wd[uint32(wd)]; ok {
                        return e, nil
                }

                if existing == nil {
                        return &watch{
                                wd:         uint32(wd),
                                path:       path,
                                flags:      flags,
                                watchFlags: wf,
                        }, nil
                }

                existing.wd = uint32(wd)
                existing.flags = flags
                return existing, nil
        })
}

func (w *inotify) Remove(name string) error {
        if w.isClosed() {
                return nil
        }
        if debug {
                fmt.Fprintf(os.Stderr, "FSNOTIFY_DEBUG: %s  Remove(%q)\n",
                        time.Now().Format("15:04:05.000000000"), name)
        }

        w.mu.Lock()
        defer w.mu.Unlock()
        return w.remove(filepath.Clean(name))
}

func (w *inotify) remove(name string) error {
        wds, err := w.watches.removePath(name)
        if err != nil {
                return err
        }

        for _, wd := range wds {
                _, err := unix.InotifyRmWatch(w.fd, wd)
                if err != nil {
                        // TODO: Perhaps it's not helpful to return an error here in every
                        // case; the only two possible errors are:
                        //
                        // EBADF, which happens when w.fd is not a valid file descriptor of
                        // any kind.
                        //
                        // EINVAL, which is when fd is not an inotify descriptor or wd is
                        // not a valid watch descriptor. Watch descriptors are invalidated
                        // when they are removed explicitly or implicitly; explicitly by
                        // inotify_rm_watch, implicitly when the file they are watching is
                        // deleted.
                        return err
                }
        }
        return nil
}

func (w *inotify) WatchList() []string {
        if w.isClosed() {
                return nil
        }

        w.mu.Lock()
        defer w.mu.Unlock()
        entries := make([]string, 0, w.watches.len())
        for pathname := range w.watches.path {
                entries = append(entries, pathname)
        }
        return entries
}

// readEvents reads from the inotify file descriptor, converts the
// received events into Event objects and sends them via the Events channel
func (w *inotify) readEvents() {
        defer func() {
                close(w.doneResp)
                close(w.Errors)
                close(w.Events)
        }()

        var buf [unix.SizeofInotifyEvent * 4096]byte // Buffer for a maximum of 4096 raw events
        for {
                if w.isClosed() {
                        return
                }

                n, err := w.inotifyFile.Read(buf[:])
                if err != nil {
                        if errors.Is(err, os.ErrClosed) {
                                return
                        }
                        if !w.sendError(err) {
                                return
                        }
                        continue
                }

                if n < unix.SizeofInotifyEvent {
                        err := errors.New("notify: short read in readEvents()") // Read was too short.
                        if n == 0 {
                                err = io.EOF // If EOF is received. This should really never happen.
                        }
                        if !w.sendError(err) {
                                return
                        }
                        continue
                }

                // We don't know how many events we just read into the buffer While the
                // offset points to at least one whole event.
                var offset uint32
                for offset <= uint32(n-unix.SizeofInotifyEvent) {
                        // Point to the event in the buffer.
                        inEvent := (*unix.InotifyEvent)(unsafe.Pointer(&buf[offset]))

                        if inEvent.Mask&unix.IN_Q_OVERFLOW != 0 {
                                if !w.sendError(ErrEventOverflow) {
                                        return
                                }
                        }

                        ev, ok := w.handleEvent(inEvent, &buf, offset)
                        if !ok {
                                return
                        }
                        if !w.sendEvent(ev) {
                                return
                        }

                        // Move to the next event in the buffer
                        offset += unix.SizeofInotifyEvent + inEvent.Len
                }
        }
}

func (w *inotify) handleEvent(inEvent *unix.InotifyEvent, buf *[65536]byte, offset uint32) (Event, bool) {
        w.mu.Lock()
        defer w.mu.Unlock()

        /// If the event happened to the watched directory or the watched file, the
        /// kernel doesn't append the filename to the event, but we would like to
        /// always fill the the "Name" field with a valid filename. We retrieve the
        /// path of the watch from the "paths" map.
        ///
        /// Can be nil if Remove() was called in another goroutine for this path
        /// inbetween reading the events from the kernel and reading the internal
        /// state. Not much we can do about it, so just skip. See #616.
        watch := w.watches.byWd(uint32(inEvent.Wd))
        if watch == nil {
                return Event{}, true
        }

        var (
                name    = watch.path
                nameLen = uint32(inEvent.Len)
        )
        if nameLen > 0 {
                /// Point "bytes" at the first byte of the filename
                bb := *buf
                bytes := (*[unix.PathMax]byte)(unsafe.Pointer(&bb[offset+unix.SizeofInotifyEvent]))[:nameLen:nameLen]
                /// The filename is padded with NULL bytes. TrimRight() gets rid of those.
                name += "/" + strings.TrimRight(string(bytes[0:nameLen]), "\x00")
        }

        if debug {
                internal.Debug(name, inEvent.Mask, inEvent.Cookie)
        }

        if inEvent.Mask&unix.IN_IGNORED != 0 || inEvent.Mask&unix.IN_UNMOUNT != 0 {
                w.watches.remove(watch)
                return Event{}, true
        }

        // inotify will automatically remove the watch on deletes; just need
        // to clean our state here.
        if inEvent.Mask&unix.IN_DELETE_SELF == unix.IN_DELETE_SELF {
                w.watches.remove(watch)
        }

        // We can't really update the state when a watched path is moved; only
        // IN_MOVE_SELF is sent and not IN_MOVED_{FROM,TO}. So remove the watch.
        if inEvent.Mask&unix.IN_MOVE_SELF == unix.IN_MOVE_SELF {
                // Watch is set up as part of recurse: do nothing as the move gets
                // registered from the parent directory.
                if watch.recurse() && !watch.byUser() {
                        return Event{}, true
                }

                err := w.remove(watch.path)
                if err != nil && !errors.Is(err, ErrNonExistentWatch) {
                        if !w.sendError(err) {
                                return Event{}, false
                        }
                }

                if watch.recurse() {
                        return Event{Name: watch.path, Op: Rename}, true
                }
        }

        /// Skip if we're watching both this path and the parent; the parent will
        /// already send a delete so no need to do it twice.
        if inEvent.Mask&unix.IN_DELETE_SELF != 0 {
                _, ok := w.watches.path[filepath.Dir(watch.path)]
                if ok {
                        return Event{}, true
                }
        }

        ev := w.newEvent(name, inEvent.Mask, inEvent.Cookie)
        // Need to update watch path for recurse.
        if watch.recurse() {
                isDir := inEvent.Mask&unix.IN_ISDIR == unix.IN_ISDIR
                /// New directory created: set up watch on it.
                if isDir && ev.Has(Create) {
                        err := w.register(ev.Name, watch.flags, flagRecurse)
                        if !w.sendError(err) {
                                return Event{}, false
                        }

                        // This was a directory rename, so we need to update all the
                        // children.
                        //
                        // TODO: this is of course pretty slow; we should use a better data
                        // structure for storing all of this, e.g. store children in the
                        // watch. I have some code for this in my kqueue refactor we can use
                        // in the future. For now I'm okay with this as it's not publicly
                        // available. Correctness first, performance second.
                        if ev.renamedFrom != "" {
                                for k, ww := range w.watches.wd {
                                        if k == watch.wd || ww.path == ev.Name {
                                                continue
                                        }
                                        if strings.HasPrefix(ww.path, ev.renamedFrom) {
                                                ww.path = strings.Replace(ww.path, ev.renamedFrom, ev.Name, 1)
                                                w.watches.wd[k] = ww
                                        }
                                }
                        }
                }
        }

        return ev, true
}

func (w *inotify) newEvent(name string, mask, cookie uint32) Event {
        e := Event{Name: name}
        if mask&unix.IN_CREATE == unix.IN_CREATE || mask&unix.IN_MOVED_TO == unix.IN_MOVED_TO {
                e.Op |= Create
        }
        if mask&unix.IN_DELETE_SELF == unix.IN_DELETE_SELF || mask&unix.IN_DELETE == unix.IN_DELETE {
                e.Op |= Remove
        }
        if mask&unix.IN_MODIFY == unix.IN_MODIFY {
                e.Op |= Write
        }
        if mask&unix.IN_OPEN == unix.IN_OPEN {
                e.Op |= xUnportableOpen
        }
        if mask&unix.IN_ACCESS == unix.IN_ACCESS {
                e.Op |= xUnportableRead
        }
        if mask&unix.IN_CLOSE_WRITE == unix.IN_CLOSE_WRITE {
                e.Op |= xUnportableCloseWrite
        }
        if mask&unix.IN_CLOSE_NOWRITE == unix.IN_CLOSE_NOWRITE {
                e.Op |= xUnportableCloseRead
        }
        if mask&unix.IN_MOVE_SELF == unix.IN_MOVE_SELF || mask&unix.IN_MOVED_FROM == unix.IN_MOVED_FROM {
                e.Op |= Rename
        }
        if mask&unix.IN_ATTRIB == unix.IN_ATTRIB {
                e.Op |= Chmod
        }

        if cookie != 0 {
                if mask&unix.IN_MOVED_FROM == unix.IN_MOVED_FROM {
                        w.cookiesMu.Lock()
                        w.cookies[w.cookieIndex] = koekje{cookie: cookie, path: e.Name}
                        w.cookieIndex++
                        if w.cookieIndex > 9 {
                                w.cookieIndex = 0
                        }
                        w.cookiesMu.Unlock()
                } else if mask&unix.IN_MOVED_TO == unix.IN_MOVED_TO {
                        w.cookiesMu.Lock()
                        var prev string
                        for _, c := range w.cookies {
                                if c.cookie == cookie {
                                        prev = c.path
                                        break
                                }
                        }
                        w.cookiesMu.Unlock()
                        e.renamedFrom = prev
                }
        }
        return e
}

func (w *inotify) xSupports(op Op) bool {
        return true // Supports everything.
}

func (w *inotify) state() {
        w.mu.Lock()
        defer w.mu.Unlock()
        for wd, ww := range w.watches.wd {
                fmt.Fprintf(os.Stderr, "%4d: %q  watchFlags=0x%x\n", wd, ww.path, ww.watchFlags)
        }
}

// Package fsnotify provides a cross-platform interface for file system
// notifications.
//
// Currently supported systems:
//
//   - Linux      via inotify
//   - BSD, macOS via kqueue
//   - Windows    via ReadDirectoryChangesW
//   - illumos    via FEN
//
// # FSNOTIFY_DEBUG
//
// Set the FSNOTIFY_DEBUG environment variable to "1" to print debug messages to
// stderr. This can be useful to track down some problems, especially in cases
// where fsnotify is used as an indirect dependency.
//
// Every event will be printed as soon as there's something useful to print,
// with as little processing from fsnotify.
//
// Example output:
//
//        FSNOTIFY_DEBUG: 11:34:23.633087586   256:IN_CREATE            → "/tmp/file-1"
//        FSNOTIFY_DEBUG: 11:34:23.633202319     4:IN_ATTRIB            → "/tmp/file-1"
//        FSNOTIFY_DEBUG: 11:34:28.989728764   512:IN_DELETE            → "/tmp/file-1"
package fsnotify

import (
        "errors"
        "fmt"
        "os"
        "path/filepath"
        "strings"
)

// Watcher watches a set of paths, delivering events on a channel.
//
// A watcher should not be copied (e.g. pass it by pointer, rather than by
// value).
//
// # Linux notes
//
// When a file is removed a Remove event won't be emitted until all file
// descriptors are closed, and deletes will always emit a Chmod. For example:
//
//        fp := os.Open("file")
//        os.Remove("file")        // Triggers Chmod
//        fp.Close()               // Triggers Remove
//
// This is the event that inotify sends, so not much can be changed about this.
//
// The fs.inotify.max_user_watches sysctl variable specifies the upper limit
// for the number of watches per user, and fs.inotify.max_user_instances
// specifies the maximum number of inotify instances per user. Every Watcher you
// create is an "instance", and every path you add is a "watch". Reaching the
// limit will result in a "no space left on device" or "too many open files"
// error.
//
// These are also exposed in /proc as /proc/sys/fs/inotify/max_user_watches and
// /proc/sys/fs/inotify/max_user_instances. The default values differ per distro
// and available memory.
//
// To increase them you can use sysctl or write the value to the /proc file:
//
//        sysctl fs.inotify.max_user_watches=200000
//        sysctl fs.inotify.max_user_instances=256
//
// To make the changes persist on reboot edit /etc/sysctl.conf or
// /usr/lib/sysctl.d/50-default.conf (details differ per Linux distro; check
// your distro's documentation):
//
//        fs.inotify.max_user_watches=200000
//        fs.inotify.max_user_instances=256
//
// # kqueue notes (macOS, BSD)
//
// kqueue requires opening a file descriptor for every file that's being watched;
// so if you're watching a directory with five files then that's six file
// descriptors. You will run in to your system's "max open files" limit faster on
// these platforms.
//
// The sysctl variables kern.maxfiles and kern.maxfilesperproc can be used to
// control the maximum number of open files, as well as /etc/login.conf on BSD
// systems.
//
// # Windows notes
//
// Paths can be added as "C:\\path\\to\\dir", but forward slashes
// ("C:/path/to/dir") will also work.
//
// When a watched directory is removed it will always send an event for the
// directory itself, but may not send events for all files in that directory.
// Sometimes it will send events for all files, sometimes it will send no
// events, and often only for some files.
//
// The default ReadDirectoryChangesW() buffer size is 64K, which is the largest
// value that is guaranteed to work with SMB filesystems. If you have many
// events in quick succession this may not be enough, and you will have to use
// [WithBufferSize] to increase the value.
type Watcher struct {
        b backend

        // Events sends the filesystem change events.
        //
        // fsnotify can send the following events; a "path" here can refer to a
        // file, directory, symbolic link, or special file like a FIFO.
        //
        //   fsnotify.Create    A new path was created; this may be followed by one
        //                      or more Write events if data also gets written to a
        //                      file.
        //
        //   fsnotify.Remove    A path was removed.
        //
        //   fsnotify.Rename    A path was renamed. A rename is always sent with the
        //                      old path as Event.Name, and a Create event will be
        //                      sent with the new name. Renames are only sent for
        //                      paths that are currently watched; e.g. moving an
        //                      unmonitored file into a monitored directory will
        //                      show up as just a Create. Similarly, renaming a file
        //                      to outside a monitored directory will show up as
        //                      only a Rename.
        //
        //   fsnotify.Write     A file or named pipe was written to. A Truncate will
        //                      also trigger a Write. A single "write action"
        //                      initiated by the user may show up as one or multiple
        //                      writes, depending on when the system syncs things to
        //                      disk. For example when compiling a large Go program
        //                      you may get hundreds of Write events, and you may
        //                      want to wait until you've stopped receiving them
        //                      (see the dedup example in cmd/fsnotify).
        //
        //                      Some systems may send Write event for directories
        //                      when the directory content changes.
        //
        //   fsnotify.Chmod     Attributes were changed. On Linux this is also sent
        //                      when a file is removed (or more accurately, when a
        //                      link to an inode is removed). On kqueue it's sent
        //                      when a file is truncated. On Windows it's never
        //                      sent.
        Events chan Event

        // Errors sends any errors.
        Errors chan error
}

// Event represents a file system notification.
type Event struct {
        // Path to the file or directory.
        //
        // Paths are relative to the input; for example with Add("dir") the Name
        // will be set to "dir/file" if you create that file, but if you use
        // Add("/path/to/dir") it will be "/path/to/dir/file".
        Name string

        // File operation that triggered the event.
        //
        // This is a bitmask and some systems may send multiple operations at once.
        // Use the Event.Has() method instead of comparing with ==.
        Op Op

        // Create events will have this set to the old path if it's a rename. This
        // only works when both the source and destination are watched. It's not
        // reliable when watching individual files, only directories.
        //
        // For example "mv /tmp/file /tmp/rename" will emit:
        //
        //   Event{Op: Rename, Name: "/tmp/file"}
        //   Event{Op: Create, Name: "/tmp/rename", RenamedFrom: "/tmp/file"}
        renamedFrom string
}

// Op describes a set of file operations.
type Op uint32

// The operations fsnotify can trigger; see the documentation on [Watcher] for a
// full description, and check them with [Event.Has].
const (
        // A new pathname was created.
        Create Op = 1 << iota

        // The pathname was written to; this does *not* mean the write has finished,
        // and a write can be followed by more writes.
        Write

        // The path was removed; any watches on it will be removed. Some "remove"
        // operations may trigger a Rename if the file is actually moved (for
        // example "remove to trash" is often a rename).
        Remove

        // The path was renamed to something else; any watches on it will be
        // removed.
        Rename

        // File attributes were changed.
        //
        // It's generally not recommended to take action on this event, as it may
        // get triggered very frequently by some software. For example, Spotlight
        // indexing on macOS, anti-virus software, backup software, etc.
        Chmod

        // File descriptor was opened.
        //
        // Only works on Linux and FreeBSD.
        xUnportableOpen

        // File was read from.
        //
        // Only works on Linux and FreeBSD.
        xUnportableRead

        // File opened for writing was closed.
        //
        // Only works on Linux and FreeBSD.
        //
        // The advantage of using this over Write is that it's more reliable than
        // waiting for Write events to stop. It's also faster (if you're not
        // listening to Write events): copying a file of a few GB can easily
        // generate tens of thousands of Write events in a short span of time.
        xUnportableCloseWrite

        // File opened for reading was closed.
        //
        // Only works on Linux.
        xUnportableCloseRead
)

var (
        // ErrNonExistentWatch is used when Remove() is called on a path that's not
        // added.
        ErrNonExistentWatch = errors.New("fsnotify: can't remove non-existent watch")

        // ErrClosed is used when trying to operate on a closed Watcher.
        ErrClosed = errors.New("fsnotify: watcher already closed")

        // ErrEventOverflow is reported from the Errors channel when there are too
        // many events:
        //
        //  - inotify:      inotify returns IN_Q_OVERFLOW – because there are too
        //                  many queued events (the fs.inotify.max_queued_events
        //                  sysctl can be used to increase this).
        //  - windows:      The buffer size is too small; WithBufferSize() can be used to increase it.
        //  - kqueue, fen:  Not used.
        ErrEventOverflow = errors.New("fsnotify: queue or buffer overflow")

        // ErrUnsupported is returned by AddWith() when WithOps() specified an
        // Unportable event that's not supported on this platform.
        //lint:ignore ST1012 not relevant
        xErrUnsupported = errors.New("fsnotify: not supported with this backend")
)

// NewWatcher creates a new Watcher.
func NewWatcher() (*Watcher, error) {
        ev, errs := make(chan Event, defaultBufferSize), make(chan error)
        b, err := newBackend(ev, errs)
        if err != nil {
                return nil, err
        }
        return &Watcher{b: b, Events: ev, Errors: errs}, nil
}

// NewBufferedWatcher creates a new Watcher with a buffered Watcher.Events
// channel.
//
// The main use case for this is situations with a very large number of events
// where the kernel buffer size can't be increased (e.g. due to lack of
// permissions). An unbuffered Watcher will perform better for almost all use
// cases, and whenever possible you will be better off increasing the kernel
// buffers instead of adding a large userspace buffer.
func NewBufferedWatcher(sz uint) (*Watcher, error) {
        ev, errs := make(chan Event, sz), make(chan error)
        b, err := newBackend(ev, errs)
        if err != nil {
                return nil, err
        }
        return &Watcher{b: b, Events: ev, Errors: errs}, nil
}

// Add starts monitoring the path for changes.
//
// A path can only be watched once; watching it more than once is a no-op and will
// not return an error. Paths that do not yet exist on the filesystem cannot be
// watched.
//
// A watch will be automatically removed if the watched path is deleted or
// renamed. The exception is the Windows backend, which doesn't remove the
// watcher on renames.
//
// Notifications on network filesystems (NFS, SMB, FUSE, etc.) or special
// filesystems (/proc, /sys, etc.) generally don't work.
//
// Returns [ErrClosed] if [Watcher.Close] was called.
//
// See [Watcher.AddWith] for a version that allows adding options.
//
// # Watching directories
//
// All files in a directory are monitored, including new files that are created
// after the watcher is started. Subdirectories are not watched (i.e. it's
// non-recursive).
//
// # Watching files
//
// Watching individual files (rather than directories) is generally not
// recommended as many programs (especially editors) update files atomically: it
// will write to a temporary file which is then moved to destination,
// overwriting the original (or some variant thereof). The watcher on the
// original file is now lost, as that no longer exists.
//
// The upshot of this is that a power failure or crash won't leave a
// half-written file.
//
// Watch the parent directory and use Event.Name to filter out files you're not
// interested in. There is an example of this in cmd/fsnotify/file.go.
func (w *Watcher) Add(path string) error { return w.b.Add(path) }

// AddWith is like [Watcher.Add], but allows adding options. When using Add()
// the defaults described below are used.
//
// Possible options are:
//
//   - [WithBufferSize] sets the buffer size for the Windows backend; no-op on
//     other platforms. The default is 64K (65536 bytes).
func (w *Watcher) AddWith(path string, opts ...addOpt) error { return w.b.AddWith(path, opts...) }

// Remove stops monitoring the path for changes.
//
// Directories are always removed non-recursively. For example, if you added
// /tmp/dir and /tmp/dir/subdir then you will need to remove both.
//
// Removing a path that has not yet been added returns [ErrNonExistentWatch].
//
// Returns nil if [Watcher.Close] was called.
func (w *Watcher) Remove(path string) error { return w.b.Remove(path) }

// Close removes all watches and closes the Events channel.
func (w *Watcher) Close() error { return w.b.Close() }

// WatchList returns all paths explicitly added with [Watcher.Add] (and are not
// yet removed).
//
// The order is undefined, and may differ per call. Returns nil if
// [Watcher.Close] was called.
func (w *Watcher) WatchList() []string { return w.b.WatchList() }

// Supports reports if all the listed operations are supported by this platform.
//
// Create, Write, Remove, Rename, and Chmod are always supported. It can only
// return false for an Op starting with Unportable.
func (w *Watcher) xSupports(op Op) bool { return w.b.xSupports(op) }

func (o Op) String() string {
        var b strings.Builder
        if o.Has(Create) {
                b.WriteString("|CREATE")
        }
        if o.Has(Remove) {
                b.WriteString("|REMOVE")
        }
        if o.Has(Write) {
                b.WriteString("|WRITE")
        }
        if o.Has(xUnportableOpen) {
                b.WriteString("|OPEN")
        }
        if o.Has(xUnportableRead) {
                b.WriteString("|READ")
        }
        if o.Has(xUnportableCloseWrite) {
                b.WriteString("|CLOSE_WRITE")
        }
        if o.Has(xUnportableCloseRead) {
                b.WriteString("|CLOSE_READ")
        }
        if o.Has(Rename) {
                b.WriteString("|RENAME")
        }
        if o.Has(Chmod) {
                b.WriteString("|CHMOD")
        }
        if b.Len() == 0 {
                return "[no events]"
        }
        return b.String()[1:]
}

// Has reports if this operation has the given operation.
func (o Op) Has(h Op) bool { return o&h != 0 }

// Has reports if this event has the given operation.
func (e Event) Has(op Op) bool { return e.Op.Has(op) }

// String returns a string representation of the event with their path.
func (e Event) String() string {
        if e.renamedFrom != "" {
                return fmt.Sprintf("%-13s %q ← %q", e.Op.String(), e.Name, e.renamedFrom)
        }
        return fmt.Sprintf("%-13s %q", e.Op.String(), e.Name)
}

type (
        backend interface {
                Add(string) error
                AddWith(string, ...addOpt) error
                Remove(string) error
                WatchList() []string
                Close() error
                xSupports(Op) bool
        }
        addOpt   func(opt *withOpts)
        withOpts struct {
                bufsize    int
                op         Op
                sendCreate bool
        }
)

var debug = func() bool {
        // Check for exactly "1" (rather than mere existence) so we can add
        // options/flags in the future. I don't know if we ever want that, but it's
        // nice to leave the option open.
        return os.Getenv("FSNOTIFY_DEBUG") == "1"
}()

var defaultOpts = withOpts{
        bufsize: 65536, // 64K
        op:      Create | Write | Remove | Rename | Chmod,
}

func getOptions(opts ...addOpt) withOpts {
        with := defaultOpts
        for _, o := range opts {
                if o != nil {
                        o(&with)
                }
        }
        return with
}

// WithBufferSize sets the [ReadDirectoryChangesW] buffer size.
//
// This only has effect on Windows systems, and is a no-op for other backends.
//
// The default value is 64K (65536 bytes) which is the highest value that works
// on all filesystems and should be enough for most applications, but if you
// have a large burst of events it may not be enough. You can increase it if
// you're hitting "queue or buffer overflow" errors ([ErrEventOverflow]).
//
// [ReadDirectoryChangesW]: https://learn.microsoft.com/en-gb/windows/win32/api/winbase/nf-winbase-readdirectorychangesw
func WithBufferSize(bytes int) addOpt {
        return func(opt *withOpts) { opt.bufsize = bytes }
}

// WithOps sets which operations to listen for. The default is [Create],
// [Write], [Remove], [Rename], and [Chmod].
//
// Excluding operations you're not interested in can save quite a bit of CPU
// time; in some use cases there may be hundreds of thousands of useless Write
// or Chmod operations per second.
//
// This can also be used to add unportable operations not supported by all
// platforms; unportable operations all start with "Unportable":
// [UnportableOpen], [UnportableRead], [UnportableCloseWrite], and
// [UnportableCloseRead].
//
// AddWith returns an error when using an unportable operation that's not
// supported. Use [Watcher.Support] to check for support.
func withOps(op Op) addOpt {
        return func(opt *withOpts) { opt.op = op }
}

// "Internal" option for recursive watches on inotify.
func withCreate() addOpt {
        return func(opt *withOpts) { opt.sendCreate = true }
}

var enableRecurse = false

// Check if this path is recursive (ends with "/..." or "\..."), and return the
// path with the /... stripped.
func recursivePath(path string) (string, bool) {
        path = filepath.Clean(path)
        if !enableRecurse { // Only enabled in tests for now.
                return path, false
        }
        if filepath.Base(path) == "..." {
                return filepath.Dir(path), true
        }
        return path, false
}

type watchFlag uint8

const (
        // Added by user with Add(), rather than an internal watch.
        flagByUser = watchFlag(0x01)
        // Part of recursive watch; as the top-level path added by the user or an
        // "internal" watch.
        flagRecurse = watchFlag(0x02)
)

package internal

import (
        "fmt"
        "os"
        "strings"
        "time"

        "golang.org/x/sys/unix"
)

func Debug(name string, mask, cookie uint32) {
        names := []struct {
                n string
                m uint32
        }{
                {"IN_ACCESS", unix.IN_ACCESS},
                {"IN_ATTRIB", unix.IN_ATTRIB},
                {"IN_CLOSE", unix.IN_CLOSE},
                {"IN_CLOSE_NOWRITE", unix.IN_CLOSE_NOWRITE},
                {"IN_CLOSE_WRITE", unix.IN_CLOSE_WRITE},
                {"IN_CREATE", unix.IN_CREATE},
                {"IN_DELETE", unix.IN_DELETE},
                {"IN_DELETE_SELF", unix.IN_DELETE_SELF},
                {"IN_IGNORED", unix.IN_IGNORED},
                {"IN_ISDIR", unix.IN_ISDIR},
                {"IN_MODIFY", unix.IN_MODIFY},
                {"IN_MOVE", unix.IN_MOVE},
                {"IN_MOVED_FROM", unix.IN_MOVED_FROM},
                {"IN_MOVED_TO", unix.IN_MOVED_TO},
                {"IN_MOVE_SELF", unix.IN_MOVE_SELF},
                {"IN_OPEN", unix.IN_OPEN},
                {"IN_Q_OVERFLOW", unix.IN_Q_OVERFLOW},
                {"IN_UNMOUNT", unix.IN_UNMOUNT},
        }

        var (
                l       []string
                unknown = mask
        )
        for _, n := range names {
                if mask&n.m == n.m {
                        l = append(l, n.n)
                        unknown ^= n.m
                }
        }
        if unknown > 0 {
                l = append(l, fmt.Sprintf("0x%x", unknown))
        }
        var c string
        if cookie > 0 {
                c = fmt.Sprintf("(cookie: %d) ", cookie)
        }
        fmt.Fprintf(os.Stderr, "FSNOTIFY_DEBUG: %s  %-30s → %s%q\n",
                time.Now().Format("15:04:05.000000000"), strings.Join(l, "|"), c, name)
}

//go:build !windows && !darwin && !freebsd && !plan9

package internal

import (
        "syscall"

        "golang.org/x/sys/unix"
)

var (
        ErrSyscallEACCES = syscall.EACCES
        ErrUnixEACCES    = unix.EACCES
)

var maxfiles uint64

func Maxfiles() uint64                              { return maxfiles }
func Mkfifo(path string, mode uint32) error         { return unix.Mkfifo(path, mode) }
func Mknod(path string, mode uint32, dev int) error { return unix.Mknod(path, mode, dev) }

//go:build !windows

package internal

import "syscall"

func HasPrivilegesForSymlink() bool {
        return true
}

// IgnoringEINTR makes a function call and repeats it if it returns an
// EINTR error. This appears to be required even though we install all
// signal handlers with SA_RESTART: see #22838, #38033, #38836, #40846.
// Also #20400 and #36644 are issues in which a signal handler is
// installed without setting SA_RESTART. None of these are the common case,
// but there are enough of them that it seems that we can't avoid
// an EINTR loop.
func IgnoringEINTR[T any](fn func() (T, error)) (T, error) {
        for {
                v, err := fn()
                if err != syscall.EINTR {
                        return v, err
                }
        }
}

// This code is based on https://github.com/pmezard/go-difflib
//
// Copyright (c) 2013, Patrick Mezard
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//     The names of its contributors may not be used to endorse or promote
// products derived from this software without specific prior written
// permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
// TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// Package ztest is a copy of https://github.com/arp242/zstd/tree/master/ztest –
// vendored here so we don't add a dependency for just one file used in tests.
//
// DiffXML was removed as it depends on zgo.at/zstd/zxml.
package ztest

import (
        "encoding/json"
        "fmt"
        "regexp"
        "strings"
        "sync"
        "time"
)

type DiffOpt int

const (
        // Normalize whitespace: remove all whitespace at the start and end of every
        // line.
        DiffNormalizeWhitespace DiffOpt = iota + 1

        // Treat arguments as JSON: format them before diffing.
        DiffJSON
)

// Diff two strings and format as a unified diff.
func Diff(have, want string, opt ...DiffOpt) string {
        have, want = applyOpt(have, want, opt...)

        d := makeUnifiedDiff(unifiedDiff{
                A:       splitLines(strings.TrimSpace(have)),
                B:       splitLines(strings.TrimSpace(want)),
                Context: 3,
        })
        if len(d) == 0 {
                return ""
        }
        return "\n" + d
}

// DiffMatch formats a unified diff, but accepts various patterns in the want
// string:
//
//        %(YEAR)      current year in UTC
//        %(MONTH)     current month in UTC
//        %(DAY)       current day in UTC
//        %(UUID)      UUID format (any version).
//
//        %(ANY)       any text: .+?
//        %(ANY 5)     any text of exactly 5 characters: .{5}?
//        %(ANY 5,)    any text of at least 5 characters: .{5,}?
//        %(ANY 5,10)  any text between 5 and 10 characters: .{5,10}?
//        %(ANY 10)    any text at most 10 characters: .{,10}?
//        %(NUMBER)    any number; also allows length like ANY.
//
//        %(..)        any regular expression, but \ is not allowed.
func DiffMatch(have, want string, opt ...DiffOpt) string {
        // TODO: %(..) syntax is somewhat unfortunate, as it conflicts with fmt
        // formatting strings. Would be better to use $(..), #(..), @(..), or
        // anything else really.
        have, want = applyOpt(have, want, opt...)

        now := time.Now().UTC()
        r := strings.NewReplacer(
                `%(YEAR)`, fmt.Sprintf("%d", now.Year()),
                `%(MONTH)`, fmt.Sprintf("%02d", now.Month()),
                `%(DAY)`, fmt.Sprintf("%02d", now.Day()),
        )

        wantRe := regexp.MustCompile(`%\\\(.+?\\\)`).ReplaceAllStringFunc(
                regexp.QuoteMeta(r.Replace(want)),
                func(m string) string {
                        switch {
                        case m == `%\(UUID\)`:
                                return `[[:xdigit:]]{8}-[[:xdigit:]]{4}-[[:xdigit:]]{4}-[[:xdigit:]]{4}-[[:xdigit:]]{12}`
                        case m == `%\(ANY\)`:
                                return `.+?`
                        case m == `%\(NUMBER\)`:
                                return `\d+?`
                        case strings.HasPrefix(m, `%\(ANY `):
                                return fmt.Sprintf(`.{%s}?`, m[7:len(m)-2])
                        case strings.HasPrefix(m, `%\(NUMBER `):
                                return fmt.Sprintf(`\d{%s}?`, m[10:len(m)-2])
                        default:
                                // TODO: we need to undo the \ from QuoteMeta() here, but this
                                // means we won't be allowed to use \. Be a bit smarter about
                                // this. TODO: doesn't quite seem to work?
                                return strings.ReplaceAll(m[3:len(m)-2], `\`, ``)
                        }
                })

        // Quick check for exact match.
        if m := regexp.MustCompile(`^` + wantRe + `$`).MatchString(have); m {
                return ""
        }

        diff := unifiedDiff{
                A:       splitLines(strings.TrimSpace(have)),
                B:       splitLines(strings.TrimSpace(wantRe)),
                Context: 3,
        }
        m := newMatcher(diff.A, diff.B)
        m.cmp = func(a, b string) bool { return regexp.MustCompile(b).MatchString(a) }
        diff.Matcher = m

        d := makeUnifiedDiff(diff)
        if len(d) == 0 {
                return "ztest.DiffMatch: strings didn't match but no diff?" // Should never happen.
        }
        return "\n" + d
}

var (
        reNormalizeWhitespace     *regexp.Regexp
        reNormalizeWhitespaceOnce sync.Once
)

func applyOpt(have, want string, opt ...DiffOpt) (string, string) {
        for _, o := range opt {
                switch o {
                case DiffNormalizeWhitespace:
                        reNormalizeWhitespaceOnce.Do(func() {
                                reNormalizeWhitespace = regexp.MustCompile(`(?m)(^\s+|\s+$)`)
                        })
                        have = reNormalizeWhitespace.ReplaceAllString(have, "")
                        want = reNormalizeWhitespace.ReplaceAllString(want, "")
                case DiffJSON:
                        if have == "" {
                                have = "{}"
                        }
                        if want == "" {
                                want = "{}"
                        }

                        var h any
                        haveJ, err := indentJSON([]byte(have), &h, "", "    ")
                        if err != nil {
                                have = fmt.Sprintf("ztest.Diff: ERROR formatting have: %s\ntext: %s", err, have)
                        } else {
                                have = string(haveJ)
                        }
                        var w any
                        wantJ, err := indentJSON([]byte(want), &w, "", "    ")
                        if err != nil {
                                want = fmt.Sprintf("ztest.Diff: ERROR formatting want: %s\ntext: %s", err, want)
                        } else {
                                want = string(wantJ)
                        }
                }
        }
        return have, want
}

type match struct{ A, B, Size int }

type opCode struct {
        Tag            byte
        I1, I2, J1, J2 int
}

// sequenceMatcher compares sequence of strings. The basic
// algorithm predates, and is a little fancier than, an algorithm
// published in the late 1980's by Ratcliff and Obershelp under the
// hyperbolic name "gestalt pattern matching".  The basic idea is to find
// the longest contiguous matching subsequence.
//
// Timing:  Basic R-O is cubic time worst case and quadratic time expected
// case.  sequenceMatcher is quadratic time for the worst case and has
// expected-case behavior dependent in a complicated way on how many
// elements the sequences have in common; best case time is linear.
type sequenceMatcher struct {
        a, b []string
        cmp  func(a, b string) bool
}

func newMatcher(a, b []string) *sequenceMatcher {
        return &sequenceMatcher{
                a:   a,
                b:   b,
                cmp: func(a, b string) bool { return a == b },
        }
}

// Find longest matching block in a[alo:ahi] and b[blo:bhi].
//
// Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
//
//        alo <= i <= i+k <= ahi
//        blo <= j <= j+k <= bhi
//
// and for all (i',j',k') meeting those conditions,
//
//        k >= k'
//        i <= i'
//        and if i == i', j <= j'
//
// In other words, of all maximal matching blocks, return one that
// starts earliest in a, and of all those maximal matching blocks that
// start earliest in a, return the one that starts earliest in b.
//
// If no blocks match, return (alo, blo, 0).
func (m *sequenceMatcher) findLongestMatch(alo, ahi, blo, bhi int) match {
        // Populate line -> index mapping
        b2j := make(map[string][]int)
        for i, s := range m.b {
                b2j[s] = append(b2j[s], i)
        }

        // CAUTION:  stripping common prefix or suffix would be incorrect.
        // E.g.,
        //    ab
        //    acab
        // Longest matching block is "ab", but if common prefix is
        // stripped, it's "a" (tied with "b").  UNIX(tm) diff does so
        // strip, so ends up claiming that ab is changed to acab by
        // inserting "ca" in the middle.  That's minimal but unintuitive:
        // "it's obvious" that someone inserted "ac" at the front.
        // Windiff ends up at the same place as diff, but by pairing up
        // the unique 'b's and then matching the first two 'a's.
        besti, bestj, bestsize := alo, blo, 0

        // find longest match. During an iteration of the loop, j2len[j] = length of
        // longest match ending with a[i-1] and b[j]
        j2len := map[int]int{}
        for i := alo; i != ahi; i++ {
                // look at all instances of a[i] in b.
                newj2len := map[int]int{}
                for _, j := range b2j[m.a[i]] {
                        // a[i] matches b[j]
                        if j < blo {
                                continue
                        }
                        if j >= bhi {
                                break
                        }
                        k := j2len[j-1] + 1
                        newj2len[j] = k
                        if k > bestsize {
                                besti, bestj, bestsize = i-k+1, j-k+1, k
                        }
                }
                j2len = newj2len
        }

        // Extend the best by elements on each end.  In particular, "popular"
        // elements aren't in b2j, which greatly speeds the inner loop above.
        for besti > alo && bestj > blo && m.cmp(m.a[besti-1], m.b[bestj-1]) {
                besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
        }
        for besti+bestsize < ahi && bestj+bestsize < bhi && m.cmp(m.a[besti+bestsize], m.b[bestj+bestsize]) {
                bestsize += 1
        }

        return match{A: besti, B: bestj, Size: bestsize}
}

// Return list of triples describing matching subsequences.
//
// Each triple is of the form (i, j, n), and means that
// a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
// i and in j. It's also guaranteed that if (i, j, n) and (i', j', n') are
// adjacent triples in the list, and the second is not the last triple in the
// list, then i+n != i' or j+n != j'. IOW, adjacent triples never describe
// adjacent equal blocks.
//
// The last triple is a dummy, (len(a), len(b), 0), and is the only
// triple with n==0.
func (m *sequenceMatcher) matchingBlocks() []match {
        var matchBlocks func(alo, ahi, blo, bhi int, matched []match) []match
        matchBlocks = func(alo, ahi, blo, bhi int, matched []match) []match {
                match := m.findLongestMatch(alo, ahi, blo, bhi)
                i, j, k := match.A, match.B, match.Size
                if match.Size > 0 {
                        if alo < i && blo < j {
                                matched = matchBlocks(alo, i, blo, j, matched)
                        }
                        matched = append(matched, match)
                        if i+k < ahi && j+k < bhi {
                                matched = matchBlocks(i+k, ahi, j+k, bhi, matched)
                        }
                }
                return matched
        }
        matched := matchBlocks(0, len(m.a), 0, len(m.b), nil)

        // It's possible that we have adjacent equal blocks in the
        // matching_blocks list now.
        nonAdjacent := []match{}
        i1, j1, k1 := 0, 0, 0
        for _, b := range matched {
                // Is this block adjacent to i1, j1, k1?
                i2, j2, k2 := b.A, b.B, b.Size
                if i1+k1 == i2 && j1+k1 == j2 {
                        // Yes, so collapse them -- this just increases the length of
                        // the first block by the length of the second, and the first
                        // block so lengthened remains the block to compare against.
                        k1 += k2
                } else {
                        // Not adjacent.  Remember the first block (k1==0 means it's
                        // the dummy we started with), and make the second block the
                        // new block to compare against.
                        if k1 > 0 {
                                nonAdjacent = append(nonAdjacent, match{i1, j1, k1})
                        }
                        i1, j1, k1 = i2, j2, k2
                }
        }
        if k1 > 0 {
                nonAdjacent = append(nonAdjacent, match{i1, j1, k1})
        }

        return append(nonAdjacent, match{len(m.a), len(m.b), 0})
}

// Return list of 5-tuples describing how to turn a into b.
//
// Each tuple is of the form (tag, i1, i2, j1, j2).  The first tuple
// has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the
// tuple preceding it, and likewise for j1 == the previous j2.
//
// The tags are characters, with these meanings:
//
// 'r' (replace):  a[i1:i2] should be replaced by b[j1:j2]
//
// 'd' (delete):   a[i1:i2] should be deleted, j1==j2 in this case.
//
// 'i' (insert):   b[j1:j2] should be inserted at a[i1:i1], i1==i2 in this case.
//
// 'e' (equal):    a[i1:i2] == b[j1:j2]
func (m *sequenceMatcher) GetOpCodes() []opCode {
        matching := m.matchingBlocks()
        opCodes := make([]opCode, 0, len(matching))

        var i, j int
        for _, m := range matching {
                //  invariant:  we've pumped out correct diffs to change
                //  a[:i] into b[:j], and the next matching block is
                //  a[ai:ai+size] == b[bj:bj+size]. So we need to pump
                //  out a diff to change a[i:ai] into b[j:bj], pump out
                //  the matching block, and move (i,j) beyond the match
                ai, bj, size := m.A, m.B, m.Size
                tag := byte(0)
                if i < ai && j < bj {
                        tag = 'r'
                } else if i < ai {
                        tag = 'd'
                } else if j < bj {
                        tag = 'i'
                }
                if tag > 0 {
                        opCodes = append(opCodes, opCode{tag, i, ai, j, bj})
                }

                i, j = ai+size, bj+size
                // the list of matching blocks is terminated by a
                // sentinel with size 0
                if size > 0 {
                        opCodes = append(opCodes, opCode{'e', ai, i, bj, j})
                }
        }

        return opCodes
}

// Isolate change clusters by eliminating ranges with no changes.
//
// Return a generator of groups with up to n lines of context.
// Each group is in the same format as returned by GetOpCodes().
func (m *sequenceMatcher) GetGroupedOpCodes(n int) [][]opCode {
        if n < 0 {
                n = 3
        }
        codes := m.GetOpCodes()
        if len(codes) == 0 {
                codes = []opCode{opCode{'e', 0, 1, 0, 1}}
        }

        // Fixup leading and trailing groups if they show no changes.
        if codes[0].Tag == 'e' {
                c := codes[0]
                i1, i2, j1, j2 := c.I1, c.I2, c.J1, c.J2
                codes[0] = opCode{c.Tag, max(i1, i2-n), i2, max(j1, j2-n), j2}
        }

        if codes[len(codes)-1].Tag == 'e' {
                c := codes[len(codes)-1]
                i1, i2, j1, j2 := c.I1, c.I2, c.J1, c.J2
                codes[len(codes)-1] = opCode{c.Tag, i1, min(i2, i1+n), j1, min(j2, j1+n)}
        }

        nn := n + n
        groups := [][]opCode{}
        group := []opCode{}
        for _, c := range codes {
                i1, i2, j1, j2 := c.I1, c.I2, c.J1, c.J2
                // End the current group and start a new one whenever
                // there is a large range with no changes.
                if c.Tag == 'e' && i2-i1 > nn {
                        group = append(group, opCode{c.Tag, i1, min(i2, i1+n),
                                j1, min(j2, j1+n)})
                        groups = append(groups, group)
                        group = []opCode{}
                        i1, j1 = max(i1, i2-n), max(j1, j2-n)
                }
                group = append(group, opCode{c.Tag, i1, i2, j1, j2})
        }

        if len(group) > 0 && !(len(group) == 1 && group[0].Tag == 'e') {
                groups = append(groups, group)
        }
        return groups
}

// Convert range to the "ed" format
func formatRangeUnified(start, stop int) string {
        // Per the diff spec at http://www.unix.org/single_unix_specification/
        beginning := start + 1 // lines start numbering with one
        length := stop - start
        if length == 1 {
                return fmt.Sprintf("%d", beginning)
        }

        if length == 0 {
                beginning -= 1 // empty ranges begin at line just before the range
        }
        return fmt.Sprintf("%d,%d", beginning, length)
}

// Unified diff parameters
type unifiedDiff struct {
        A, B    []string
        Context int
        Matcher *sequenceMatcher
}

// Compare two sequences of lines; generate the delta as a unified diff.
//
// Unified diffs are a compact way of showing line changes and a few
// lines of context.  The number of context lines is set by 'n' which
// defaults to three.
//
// By default, the diff control lines (those with ---, +++, or @@) are
// created with a trailing newline.  This is helpful so that inputs
// created from file.readlines() result in diffs that are suitable for
// file.writelines() since both the inputs and outputs have trailing
// newlines.
//
// For inputs that do not have trailing newlines, set the lineterm
// argument to "" so that the output will be uniformly newline free.
//
// The unidiff format normally has a header for filenames and modification
// times.  Any or all of these may be specified using strings for
// 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.
// The modification times are normally expressed in the ISO 8601 format.
func makeUnifiedDiff(diff unifiedDiff) string {
        if diff.Matcher == nil {
                diff.Matcher = newMatcher(diff.A, diff.B)
        }

        var (
                out     strings.Builder
                started bool
        )
        for _, g := range diff.Matcher.GetGroupedOpCodes(diff.Context) {
                if !started {
                        started = true
                        out.WriteString("--- have\n")
                        out.WriteString("+++ want\n")
                }

                first, last := g[0], g[len(g)-1]
                out.WriteString(fmt.Sprintf("@@ -%s +%s @@\n",
                        formatRangeUnified(first.I1, last.I2),
                        formatRangeUnified(first.J1, last.J2)))

                for _, c := range g {
                        i1, i2, j1, j2 := c.I1, c.I2, c.J1, c.J2
                        if c.Tag == 'e' {
                                for _, line := range diff.A[i1:i2] {
                                        out.WriteString("      " + line)
                                }
                                continue
                        }

                        if c.Tag == 'r' || c.Tag == 'd' {
                                for _, line := range diff.A[i1:i2] {
                                        out.WriteString("-have " + line)
                                }
                        }

                        if c.Tag == 'r' || c.Tag == 'i' {
                                for _, line := range diff.B[j1:j2] {
                                        out.WriteString("+want " + line)
                                }
                        }
                }
        }

        return out.String()
}

func min(a, b int) int {
        if a < b {
                return a
        }
        return b
}
func max(a, b int) int {
        if a > b {
                return a
        }
        return b
}
func splitLines(s string) []string {
        lines := strings.SplitAfter(s, "\n")
        lines[len(lines)-1] += "\n"
        return lines
}

func indentJSON(data []byte, v any, prefix, indent string) ([]byte, error) {
        err := json.Unmarshal(data, v)
        if err != nil {
                return nil, err
        }
        return json.MarshalIndent(v, prefix, indent)
}

package fsnotify

import "sync"

type shared struct {
        Events chan Event
        Errors chan error
        done   chan struct{}
        mu     sync.Mutex
}

func newShared(ev chan Event, errs chan error) *shared {
        return &shared{
                Events: ev,
                Errors: errs,
                done:   make(chan struct{}),
        }
}

// Returns true if the event was sent, or false if watcher is closed.
func (w *shared) sendEvent(e Event) bool {
        if e.Op == 0 {
                return true
        }
        select {
        case <-w.done:
                return false
        case w.Events <- e:
                return true
        }
}

// Returns true if the error was sent, or false if watcher is closed.
func (w *shared) sendError(err error) bool {
        if err == nil {
                return true
        }
        select {
        case <-w.done:
                return false
        case w.Errors <- err:
                return true
        }
}

func (w *shared) isClosed() bool {
        select {
        case <-w.done:
                return true
        default:
                return false
        }
}

// Mark as closed; returns true if it was already closed.
func (w *shared) close() bool {
        w.mu.Lock()
        defer w.mu.Unlock()
        if w.isClosed() {
                return true
        }
        close(w.done)
        return false
}