// Approach:

//

// 1. Get the minimatch set

// 2. For each pattern in the set, PROCESS(pattern, false)

// 3. Store matches per-set, then uniq them

//

// PROCESS(pattern, inGlobStar)

// Get the first [n] items from pattern that are all strings

// Join these together. This is PREFIX.

// If there is no more remaining, then stat(PREFIX) and

// add to matches if it succeeds. END.

//

// If inGlobStar and PREFIX is symlink and points to dir

// set ENTRIES = []

// else readdir(PREFIX) as ENTRIES

// If fail, END

//

// with ENTRIES

// If pattern[n] is GLOBSTAR

// // handle the case where the globstar match is empty

// // by pruning it out, and testing the resulting pattern

// PROCESS(pattern[0..n] + pattern[n+1 .. $], false)

// // handle other cases.

// for ENTRY in ENTRIES (not dotfiles)

// // attach globstar + tail onto the entry

// // Mark that this entry is a globstar match

// PROCESS(pattern[0..n] + ENTRY + pattern[n .. $], true)

//

// else // not globstar

// for ENTRY in ENTRIES (not dotfiles, unless pattern[n] is dot)

// Test ENTRY against pattern[n]

// If fails, continue

// If passes, PROCESS(pattern[0..n] + item + pattern[n+1 .. $])

//

// Caveat:

// Cache all stats and readdirs results to minimize syscall. Since all

// we ever care about is existence and directory-ness, we can just keep

// `true` for files, and [children,...] for directories, or `false` for

// things that don't exist.

module.exports = glob

var fs = require('fs')

var rp = require('fs.realpath')

var minimatch = require('minimatch')

var Minimatch = minimatch.Minimatch

var inherits = require('inherits')

var EE = require('events').EventEmitter

var path = require('path')

var assert = require('assert')

var isAbsolute = require('path-is-absolute')

var globSync = require('./sync.js')

var common = require('./common.js')

var alphasort = common.alphasort

var alphasorti = common.alphasorti

var setopts = common.setopts

var ownProp = common.ownProp

var inflight = require('inflight')

var util = require('util')

var childrenIgnored = common.childrenIgnored

var isIgnored = common.isIgnored

var once = require('once')

function glob (pattern, options, cb) {

if (typeof options === 'function') cb = options, options = {}

if (!options) options = {}

if (options.sync) {

if (cb)

throw new TypeError('callback provided to sync glob')

return globSync(pattern, options)

}

return new Glob(pattern, options, cb)

}

glob.sync = globSync

var GlobSync = glob.GlobSync = globSync.GlobSync

// old api surface

glob.glob = glob

function extend (origin, add) {

if (add === null || typeof add !== 'object') {

return origin

}

var keys = Object.keys(add)

var i = keys.length

while (i--) {

origin[keys[i]] = add[keys[i]]

}

return origin

}

glob.hasMagic = function (pattern, options_) {

var options = extend({}, options_)

options.noprocess = true

var g = new Glob(pattern, options)

var set = g.minimatch.set

if (!pattern)

return false

if (set.length > 1)

return true

for (var j = 0; j < set[0].length; j++) {

if (typeof set[0][j] !== 'string')

return true

}

return false

}

glob.Glob = Glob

inherits(Glob, EE)

function Glob (pattern, options, cb) {

if (typeof options === 'function') {

cb = options

options = null

}

if (options && options.sync) {

if (cb)

throw new TypeError('callback provided to sync glob')

return new GlobSync(pattern, options)

}

if (!(this instanceof Glob))

return new Glob(pattern, options, cb)

setopts(this, pattern, options)

this._didRealPath = false

// process each pattern in the minimatch set

var n = this.minimatch.set.length

// The matches are stored as {<filename>: true,...} so that

// duplicates are automagically pruned.

// Later, we do an Object.keys() on these.

// Keep them as a list so we can fill in when nonull is set.

this.matches = new Array(n)

if (typeof cb === 'function') {

cb = once(cb)

this.on('error', cb)

this.on('end', function (matches) {

cb(null, matches)

})

}

var self = this

this._processing = 0

this._emitQueue = []

this._processQueue = []

this.paused = false

if (this.noprocess)

return this

if (n === 0)

return done()

var sync = true

for (var i = 0; i < n; i ++) {

this._process(this.minimatch.set[i], i, false, done)

}

sync = false

function done () {

--self._processing

if (self._processing <= 0) {

if (sync) {

process.nextTick(function () {

self._finish()

})

} else {

self._finish()

}

}

}

}

Glob.prototype._finish = function () {

assert(this instanceof Glob)

if (this.aborted)

return

if (this.realpath && !this._didRealpath)

return this._realpath()

common.finish(this)

this.emit('end', this.found)

}

Glob.prototype._realpath = function () {

if (this._didRealpath)

return

this._didRealpath = true

var n = this.matches.length

if (n === 0)

return this._finish()

var self = this

for (var i = 0; i < this.matches.length; i++)

this._realpathSet(i, next)

function next () {

if (--n === 0)

self._finish()

}

}

Glob.prototype._realpathSet = function (index, cb) {

var matchset = this.matches[index]

if (!matchset)

return cb()

var found = Object.keys(matchset)

var self = this

var n = found.length

if (n === 0)

return cb()

var set = this.matches[index] = Object.create(null)

found.forEach(function (p, i) {

// If there's a problem with the stat, then it means that

// one or more of the links in the realpath couldn't be

// resolved. just return the abs value in that case.

p = self._makeAbs(p)

rp.realpath(p, self.realpathCache, function (er, real) {

if (!er)

set[real] = true

else if (er.syscall === 'stat')

set[p] = true

else

self.emit('error', er) // srsly wtf right here

if (--n === 0) {

self.matches[index] = set

cb()

}

})

})

}

Glob.prototype._mark = function (p) {

return common.mark(this, p)

}

Glob.prototype._makeAbs = function (f) {

return common.makeAbs(this, f)

}

Glob.prototype.abort = function () {

this.aborted = true

this.emit('abort')

}

Glob.prototype.pause = function () {

if (!this.paused) {

this.paused = true

this.emit('pause')

}

}

Glob.prototype.resume = function () {

if (this.paused) {

this.emit('resume')

this.paused = false

if (this._emitQueue.length) {

var eq = this._emitQueue.slice(0)

this._emitQueue.length = 0

for (var i = 0; i < eq.length; i ++) {

var e = eq[i]

this._emitMatch(e[0], e[1])

}

}

if (this._processQueue.length) {

var pq = this._processQueue.slice(0)

this._processQueue.length = 0

for (var i = 0; i < pq.length; i ++) {

var p = pq[i]

this._processing--

this._process(p[0], p[1], p[2], p[3])

}

}

}

}

Glob.prototype._process = function (pattern, index, inGlobStar, cb) {

assert(this instanceof Glob)

assert(typeof cb === 'function')

if (this.aborted)

return

this._processing++

if (this.paused) {

this._processQueue.push([pattern, index, inGlobStar, cb])

return

}

//console.error('PROCESS %d', this._processing, pattern)

// Get the first [n] parts of pattern that are all strings.

var n = 0

while (typeof pattern[n] === 'string') {

n ++

}

// now n is the index of the first one that is *not* a string.

// see if there's anything else

var prefix

switch (n) {

// if not, then this is rather simple

case pattern.length:

this._processSimple(pattern.join('/'), index, cb)

return

case 0:

// pattern *starts* with some non-trivial item.

// going to readdir(cwd), but not include the prefix in matches.

prefix = null

break

default:

// pattern has some string bits in the front.

// whatever it starts with, whether that's 'absolute' like /foo/bar,

// or 'relative' like '../baz'

prefix = pattern.slice(0, n).join('/')

break

}

var remain = pattern.slice(n)

// get the list of entries.

var read

if (prefix === null)

read = '.'

else if (isAbsolute(prefix) || isAbsolute(pattern.join('/'))) {

if (!prefix || !isAbsolute(prefix))

prefix = '/' + prefix

read = prefix

} else

read = prefix

var abs = this._makeAbs(read)

//if ignored, skip _processing

if (childrenIgnored(this, read))

return cb()

var isGlobStar = remain[0] === minimatch.GLOBSTAR

if (isGlobStar)

this._processGlobStar(prefix, read, abs, remain, index, inGlobStar, cb)

else

this._processReaddir(prefix, read, abs, remain, index, inGlobStar, cb)

}

Glob.prototype._processReaddir = function (prefix, read, abs, remain, index, inGlobStar, cb) {

var self = this

this._readdir(abs, inGlobStar, function (er, entries) {

return self._processReaddir2(prefix, read, abs, remain, index, inGlobStar, entries, cb)

})

}

Glob.prototype._processReaddir2 = function (prefix, read, abs, remain, index, inGlobStar, entries, cb) {

// if the abs isn't a dir, then nothing can match!

if (!entries)

return cb()

// It will only match dot entries if it starts with a dot, or if

// dot is set. Stuff like @(.foo|.bar) isn't allowed.

var pn = remain[0]

var negate = !!this.minimatch.negate

var rawGlob = pn._glob

var dotOk = this.dot || rawGlob.charAt(0) === '.'

var matchedEntries = []

for (var i = 0; i < entries.length; i++) {

var e = entries[i]

if (e.charAt(0) !== '.' || dotOk) {

var m

if (negate && !prefix) {

m = !e.match(pn)

} else {

m = e.match(pn)

}

if (m)

matchedEntries.push(e)

}

}

//console.error('prd2', prefix, entries, remain[0]._glob, matchedEntries)

var len = matchedEntries.length

// If there are no matched entries, then nothing matches.

if (len === 0)

return cb()

// if this is the last remaining pattern bit, then no need for

// an additional stat *unless* the user has specified mark or

// stat explicitly. We know they exist, since readdir returned

// them.

if (remain.length === 1 && !this.mark && !this.stat) {

if (!this.matches[index])

this.matches[index] = Object.create(null)

for (var i = 0; i < len; i ++) {

var e = matchedEntries[i]

if (prefix) {

if (prefix !== '/')

e = prefix + '/' + e

else

e = prefix + e

}

if (e.charAt(0) === '/' && !this.nomount) {

e = path.join(this.root, e)

}

this._emitMatch(index, e)

}

// This was the last one, and no stats were needed

return cb()

}

// now test all matched entries as stand-ins for that part

// of the pattern.

remain.shift()

for (var i = 0; i < len; i ++) {

var e = matchedEntries[i]

var newPattern

if (prefix) {

if (prefix !== '/')

e = prefix + '/' + e

else

e = prefix + e

}

this._process([e].concat(remain), index, inGlobStar, cb)

}

cb()

}

Glob.prototype._emitMatch = function (index, e) {

if (this.aborted)

return

if (isIgnored(this, e))

return

if (this.paused) {

this._emitQueue.push([index, e])

return

}

var abs = isAbsolute(e) ? e : this._makeAbs(e)

if (this.mark)

e = this._mark(e)

if (this.absolute)

e = abs

if (this.matches[index][e])

return

if (this.nodir) {

var c = this.cache[abs]

if (c === 'DIR' || Array.isArray(c))

return

}

this.matches[index][e] = true

var st = this.statCache[abs]

if (st)

this.emit('stat', e, st)

this.emit('match', e)

}

Glob.prototype._readdirInGlobStar = function (abs, cb) {

if (this.aborted)

return

// follow all symlinked directories forever

// just proceed as if this is a non-globstar situation

if (this.follow)

return this._readdir(abs, false, cb)

var lstatkey = 'lstat\0' + abs

var self = this

var lstatcb = inflight(lstatkey, lstatcb_)

if (lstatcb)

fs.lstat(abs, lstatcb)

function lstatcb_ (er, lstat) {

if (er && er.code === 'ENOENT')

return cb()

var isSym = lstat && lstat.isSymbolicLink()

self.symlinks[abs] = isSym

// If it's not a symlink or a dir, then it's definitely a regular file.

// don't bother doing a readdir in that case.

if (!isSym && lstat && !lstat.isDirectory()) {

self.cache[abs] = 'FILE'

cb()

} else

self._readdir(abs, false, cb)

}

}

Glob.prototype._readdir = function (abs, inGlobStar, cb) {

if (this.aborted)

return

cb = inflight('readdir\0'+abs+'\0'+inGlobStar, cb)

if (!cb)

return

//console.error('RD %j %j', +inGlobStar, abs)

if (inGlobStar && !ownProp(this.symlinks, abs))

return this._readdirInGlobStar(abs, cb)

if (ownProp(this.cache, abs)) {

var c = this.cache[abs]

if (!c || c === 'FILE')

return cb()

if (Array.isArray(c))

return cb(null, c)

}

var self = this

fs.readdir(abs, readdirCb(this, abs, cb))

}

function readdirCb (self, abs, cb) {

return function (er, entries) {

if (er)

self._readdirError(abs, er, cb)

else

self._readdirEntries(abs, entries, cb)

}

}

Glob.prototype._readdirEntries = function (abs, entries, cb) {

if (this.aborted)

return

// if we haven't asked to stat everything, then just

// assume that everything in there exists, so we can avoid

// having to stat it a second time.

if (!this.mark && !this.stat) {

for (var i = 0; i < entries.length; i ++) {

var e = entries[i]

if (abs === '/')

e = abs + e

else

e = abs + '/' + e

this.cache[e] = true

}

}

this.cache[abs] = entries

return cb(null, entries)

}

Glob.prototype._readdirError = function (f, er, cb) {

if (this.aborted)

return

// handle errors, and cache the information

switch (er.code) {

case 'ENOTSUP': // https://github.com/isaacs/node-glob/issues/205

case 'ENOTDIR': // totally normal. means it *does* exist.

var abs = this._makeAbs(f)

this.cache[abs] = 'FILE'

if (abs === this.cwdAbs) {

var error = new Error(er.code + ' invalid cwd ' + this.cwd)

error.path = this.cwd

error.code = er.code

this.emit('error', error)

this.abort()

}

break

case 'ENOENT': // not terribly unusual

case 'ELOOP':

case 'ENAMETOOLONG':

case 'UNKNOWN':

this.cache[this._makeAbs(f)] = false

break

default: // some unusual error. Treat as failure.

this.cache[this._makeAbs(f)] = false

if (this.strict) {

this.emit('error', er)

// If the error is handled, then we abort

// if not, we threw out of here

this.abort()

}

if (!this.silent)

console.error('glob error', er)

break

}

return cb()

}

Glob.prototype._processGlobStar = function (prefix, read, abs, remain, index, inGlobStar, cb) {

var self = this

this._readdir(abs, inGlobStar, function (er, entries) {

self._processGlobStar2(prefix, read, abs, remain, index, inGlobStar, entries, cb)

})

}

Glob.prototype._processGlobStar2 = function (prefix, read, abs, remain, index, inGlobStar, entries, cb) {

//console.error('pgs2', prefix, remain[0], entries)

// no entries means not a dir, so it can never have matches

// foo.txt/** doesn't match foo.txt

if (!entries)

return cb()

// test without the globstar, and with every child both below

// and replacing the globstar.

var remainWithoutGlobStar = remain.slice(1)

var gspref = prefix ? [ prefix ] : []

var noGlobStar = gspref.concat(remainWithoutGlobStar)

// the noGlobStar pattern exits the inGlobStar state

this._process(noGlobStar, index, false, cb)

var isSym = this.symlinks[abs]

var len = entries.length

// If it's a symlink, and we're in a globstar, then stop

if (isSym && inGlobStar)

return cb()

for (var i = 0; i < len; i++) {

var e = entries[i]

if (e.charAt(0) === '.' && !this.dot)

continue

// these two cases enter the inGlobStar state

var instead = gspref.concat(entries[i], remainWithoutGlobStar)

this._process(instead, index, true, cb)

var below = gspref.concat(entries[i], remain)

this._process(below, index, true, cb)

}

cb()

}

Glob.prototype._processSimple = function (prefix, index, cb) {

// XXX review this. Shouldn't it be doing the mounting etc

// before doing stat? kinda weird?

var self = this

this._stat(prefix, function (er, exists) {

self._processSimple2(prefix, index, er, exists, cb)

})

}

Glob.prototype._processSimple2 = function (prefix, index, er, exists, cb) {

//console.error('ps2', prefix, exists)

if (!this.matches[index])

this.matches[index] = Object.create(null)

// If it doesn't exist, then just mark the lack of results

if (!exists)

return cb()

if (prefix && isAbsolute(prefix) && !this.nomount) {

var trail = /[\/\\]$/.test(prefix)

if (prefix.charAt(0) === '/') {

prefix = path.join(this.root, prefix)

} else {

prefix = path.resolve(this.root, prefix)

if (trail)

prefix += '/'

}

}

if (process.platform === 'win32')

prefix = prefix.replace(/\\/g, '/')

// Mark this as a match

this._emitMatch(index, prefix)

cb()

}

// Returns either 'DIR', 'FILE', or false

Glob.prototype._stat = function (f, cb) {

var abs = this._makeAbs(f)

var needDir = f.slice(-1) === '/'

if (f.length > this.maxLength)

return cb()

if (!this.stat && ownProp(this.cache, abs)) {

var c = this.cache[abs]

if (Array.isArray(c))

c = 'DIR'

// It exists, but maybe not how we need it

if (!needDir || c === 'DIR')

return cb(null, c)

if (needDir && c === 'FILE')

return cb()

// otherwise we have to stat, because maybe c=true

// if we know it exists, but not what it is.

}

var exists

var stat = this.statCache[abs]

if (stat !== undefined) {

if (stat === false)

return cb(null, stat)

else {

var type = stat.isDirectory() ? 'DIR' : 'FILE'

if (needDir && type === 'FILE')

return cb()

else

return cb(null, type, stat)

}

}

var self = this

var statcb = inflight('stat\0' + abs, lstatcb_)

if (statcb)

fs.lstat(abs, statcb)

function lstatcb_ (er, lstat) {

if (lstat && lstat.isSymbolicLink()) {

// If it's a symlink, then treat it as the target, unless

// the target does not exist, then treat it as a file.

return fs.stat(abs, function (er, stat) {

if (er)

self._stat2(f, abs, null, lstat, cb)

else

self._stat2(f, abs, er, stat, cb)

})

} else {

self._stat2(f, abs, er, lstat, cb)

}

}

}

Glob.prototype._stat2 = function (f, abs, er, stat, cb) {

if (er && (er.code === 'ENOENT' || er.code === 'ENOTDIR')) {

this.statCache[abs] = false

return cb()

}

var needDir = f.slice(-1) === '/'

this.statCache[abs] = stat

if (abs.slice(-1) === '/' && stat && !stat.isDirectory())

return cb(null, false, stat)

var c = true

if (stat)

c = stat.isDirectory() ? 'DIR' : 'FILE'

this.cache[abs] = this.cache[abs] || c

if (needDir && c === 'FILE')

return cb()

return cb(null, c, stat)

}