// 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 is GLOBSTAR // // handle the case where the globstar match is empty // // by pruning it out, and testing the resulting pattern // PROCESS(pattern + 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 + ENTRY + pattern[n .. $], true) // // else // not globstar // for ENTRY in ENTRIES (not dotfiles, unless pattern is dot) // Test ENTRY against pattern // If fails, continue // If passes, PROCESS(pattern + 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)

}