// Walk walks the file tree rooted at root, calling walkFn for each file or
// directory in the tree, including root. All errors that arise visiting files
// and directories are filtered by walkFn. The files are walked in lexical
// order, which makes the output deterministic but means that for very
// large directories Walk can be inefficient.
// Walk does not follow symbolic links.
func Walk(root string, walkFn WalkFunc) error {
    info, err := os.Lstat(root)
    if err != nil {
        err = walkFn(root, nil, err)
    } else {
        err = walk(root, info, walkFn)
    }
    if err == SkipDir {
        return nil
    }
    return err
}

type FileInfo interface {
    Name() string       // base name of the file
    Size() int64        // length in bytes for regular files; system-dependent for others
    Mode() FileMode     // file mode bits
    ModTime() time.Time // modification time
    IsDir() bool        // abbreviation for Mode().IsDir()
    Sys() interface{}   // underlying data source (can return nil)
}

const (
    // The single letters are the abbreviations
    // used by the String method's formatting.
    ModeDir        FileMode = 1 << (32 - 1 - iota) // d: is a directory
    ModeAppend                                     // a: append-only
    ModeExclusive                                  // l: exclusive use
    ModeTemporary                                  // T: temporary file; Plan 9 only
    ModeSymlink                                    // L: symbolic link
    ModeDevice                                     // D: device file
    ModeNamedPipe                                  // p: named pipe (FIFO)
    ModeSocket                                     // S: Unix domain socket
    ModeSetuid                                     // u: setuid
    ModeSetgid                                     // g: setgid
    ModeCharDevice                                 // c: Unix character device, when ModeDevice is set
    ModeSticky                                     // t: sticky
    ModeIrregular                                  // ?: non-regular file; nothing else is known about this file

    // Mask for the type bits. For regular files, none will be set.
    ModeType = ModeDir | ModeSymlink | ModeNamedPipe | ModeSocket | ModeDevice | ModeCharDevice | ModeIrregular

    ModePerm FileMode = 0777 // Unix permission bits
)

// walk recursively descends path, calling walkFn.
func walk(path string, info os.FileInfo, walkFn WalkFunc) error {
    if !info.IsDir() {
        return walkFn(path, info, nil)
    }

    names, err := readDirNames(path)
    err1 := walkFn(path, info, err)
    // If err != nil, walk can't walk into this directory.
    // err1 != nil means walkFn want walk to skip this directory or stop walking.
    // Therefore, if one of err and err1 isn't nil, walk will return.
    if err != nil || err1 != nil {
        // The caller's behavior is controlled by the return value, which is decided
        // by walkFn. walkFn may ignore err and return nil.
        // If walkFn returns SkipDir, it will be handled by the caller.
        // So walk should return whatever walkFn returns.
        return err1
    }

    for _, name := range names {
        filename := Join(path, name)
        fileInfo, err := lstat(filename)
        if err != nil {
            if err := walkFn(filename, fileInfo, err); err != nil && err != SkipDir {
                return err
            }
        } else {
            err = walk(filename, fileInfo, walkFn)
            if err != nil {
                if !fileInfo.IsDir() || err != SkipDir {
                    return err
                }
            }
        }
    }
    return nil
}